A Hidden Markov Preference Model for Online Prediction of Adversary Actions

A Hidden Markov Preference Model for Online Prediction of Adversary Actions∗

arXiv:2611.08445v1 [cs.LG] 5 Nov 2026

Angel Daruna

Michael Cogswell Tixiao Shan Ajay Divakaran SRI International

Yi Yao

Han-Pang Chiu

Abstract A defender anticipating an attacker needs a probability distribution over the attacker’s next action from information available before that action occurs. Two structures complicate this: the attacker’s behavioral regime persists and can switch within an episode, and each action combines an operation with state-dependent arguments whose feasible values change over time. We capture both with a hidden Markov model whose latent state is the active regime and whose regime-conditioned action law is defined on a feasibility-masked tree of executable actions. The same likelihood forms the next-action distribution and updates the regime belief once the action is seen, and a partially observed prefix contributes its resolved local factors. Estimation separates into convex logistic fits that Baum–Welch reuses when regimes are unlabeled. We derive a reach-weighted nodewise KL expression for regime information, a sequence-wise log-loss bound for switching regime paths, and a uniform fallback guarantee. On the CAGE 2 cyber defense benchmark the filtered latent state is worth 0.8 nats per step, and after a controller switch the loss begins to fall in three steps against ten for a recurrent baseline.

Index Terms— Hidden Markov models, discrete choice, online prediction, preference learning, cyber defense

1

Introduction

An observer often needs a probability distribution over another agent’s next action from its own observation record, with a network defender anticipating an intruder as the running example. Because the record omits the agent’s private state and objectives, prediction must rely on structure reflected in observable behavior. Behavioral patterns persist across consecutive steps and can change within an episode, as when an intruder moves from reconnaissance to exploitation or reacts to a defensive move, and each action combines an operation with arguments whose admissible values depend on the current state, leaving much of the nominal action space infeasible. Preference learning estimates a probabilistic choice rule from revealed choices through Bradley–Terry and Luce likelihoods [1, 2], and quantal-response versions are fitted to observed attacks in security games [3, 4]. Hidden context can cause a single fitted choice law to aggregate behavior generated under different unobserved conditions [5]. Latent-class and mixture models capture such heterogeneity at the user or episode level [6, 7], while input–output hidden Markov models [8] and hidden-Markov choice models [9] let the latent class evolve over time. Opponent-modeling methods infer opponent types, goals, or latent representations from interaction [10, 11, 12, 13], and cyber-forecasting methods predict attack stages or red actions from streaming observations [14, 15, 16, 17]. The present setting instead requires a full next-action distribution committed ∗ Preprint. Extended version with complete proofs and additional experimental detail.

Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 1

before each outcome, with within-episode regime changes, state-dependent feasibility, and evaluation under sequential log loss. We represent the active behavioral regime with a conditional hidden Markov model [8, 18] and structured executable actions with a regime-conditioned choice law on the feasible action tree. The same likelihood forms the next-action prediction before the action occurs and updates the regime belief afterwards; for a tree-prefix observation, the resolved local factors give its likelihood and the evidence it contributes about the regime. The construction retains exact filtering, and estimation separates into convex fits that Baum–Welch reuses when regimes are unlabeled. Contributions. The latent dynamics follow the input–output HMM [8] and hidden-Markov choice models [9], and the log-loss bounds are mixture inequalities of the expert-tracking framework [19, 20, 21, 22]; the new elements are (i) a regime-conditioned choice law on a feasibility-masked action tree, with shared and regime-specific terms, whose identification rate is a reach-weighted sum of nodewise KL divergences over the observed action fields; (ii) exact filtering that treats a complete action and a tree-prefix observation through the same local factors; (iii) switching and uniform-fallback guarantees on the feasible tree; and (iv) an attacker-side CAGE Challenge 2 evaluation [23] of a two-stage form of the predictor that separates action structure, latent-state tracking, and soft regime weighting.

2

Problem Formulation

Prediction target. An agent and an observer interact at discrete times 𝑡 = 1, 2, . . . , and the observer predicts each action the agent takes. Let ℎ𝑡− be the observer history available immediately before the agent commits to 𝐴𝑡 , including any observer action taken first at step 𝑡, and ℎ+𝑡 the same history after 𝐴𝑡 is revealed. The prediction target is 𝑝★𝑡 (𝑎) = Pr( 𝐴𝑡 = 𝑎 | ℎ𝑡− ), 𝑥 𝑡 = 𝜓(ℎ𝑡− ) ∈ R𝑑 , (1) with 𝜓 a fixed feature map to a context vector. Given training episodes, the problem is to produce at each 𝑡 a distribution 𝑝b𝑡 over the feasible actions, committed before the step’s outcome is seen, that makes the Í sequential logarithmic loss 𝑡 − log 𝑝b𝑡 (𝑎 𝑡 ) small on the executed actions. In the replay setting logs reveal the complete executed action; in the detection setting the observer receives a coarsened observation of it. Actions and feasibility. Actions are the leaves of a rooted tree T , the action grammar, with internal nodes I, children Ch(𝑣) at an internal node 𝑣, and leaf set A. Each internal node resolves one semantic field of the action, with the operation family at the root and its arguments below. For a leaf 𝑎, write 𝑗 𝑣 (𝑎) for the child taken at 𝑣 on the path to 𝑎, let I (𝑎) ⊆ I be the internal nodes on the root-to-𝑎 path, and write Path(𝑎) = {(𝑣, 𝑗 𝑣 (𝑎)) : 𝑣 ∈ I (𝑎)}. Feasibility at time 𝑡 is a mask 𝑚 𝑡 ,𝑣 ( 𝑗) ∈ {0, 1}; the feasible children at 𝑣 are C𝑡 (𝑣) = { 𝑗 ∈ Ch(𝑣) : 𝑚 𝑡 ,𝑣 ( 𝑗) = 1}, and the feasible leaves A𝑡 are those whose entire path is feasible. Masks are pruned bottom-up, so every feasible child leads to at least one feasible leaf, the local choice laws normalize over C𝑡 (𝑣), and their product induces a normalized distribution over A𝑡 . Masks are computed from the grammar and ℎ𝑡− as conservative supersets of the true support, so every executed action remains feasible under the observer’s model and constraints depending on the agent’s private progress remain part of the modeled uncertainty. Latent regime. The agent’s regime at time 𝑡 is a latent state 𝑍𝑡 ∈ Z with |Z| = 𝐾. The regime is behavioral, for instance a policy family, a stage of an attack, or an operating constraint; it persists over consecutive steps, may change within an episode, and is defined only through its effect on the action distribution. The regime evolves through a context-dependent Markov kernel with an explicit self-transition term,
exp 𝑐 1{𝑧 ′ = 𝑧} + 𝜂⊤𝑧 ′ 𝑥¯𝑡 ′
, 𝑃 𝜂 (𝑧 | 𝑧, 𝑥 𝑡 ) = Í (2) ⊤ 𝑟 exp 𝑐 1{𝑟 = 𝑧} + 𝜂𝑟 𝑥¯ 𝑡 Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 2

in which 𝑧 ′ indexes 𝑍𝑡 , 𝑧 indexes 𝑍𝑡 −1 , 𝑥¯𝑡 = [1, 𝑥 𝑡⊤ ] ⊤ , and 𝑐 ≥ 0 controls persistence. The shared persistence term keeps the transition model small when switch data are sparse, and fixing one 𝜂 𝑧 ′ at zero identifies (𝑐, 𝜂). The transition into 𝑍𝑡 uses 𝑥 𝑡 , which is available before 𝐴𝑡 and can depend on evidence accumulated through step 𝑡 − 1 together with any observer action taken first at step 𝑡. Setting 𝜂 𝑧 ′ ≡ 0 gives the homogeneous persistent kernel ′ 𝑃(𝑧 ′ | 𝑧) = 𝜅 1{𝑧 ′ = 𝑧} + 𝐾1−𝜅 −1 1{𝑧 ≠ 𝑧},

𝜅 ∈ [ 𝐾1 , 1),

(3)

with 𝜅 = 𝑒 𝑐 /(𝑒 𝑐 + 𝐾 − 1) and expected dwell time 1/(1 − 𝜅). The pathwise log-loss result applies to the general kernel in (2), while the explicit switching, fallback, and adaptation bounds use (3). At 𝑐 = 0 every row of (2) equals the contextual gate softmax𝑧 ′ (𝜂⊤𝑧 ′ 𝑥¯𝑡 ), so the filter carries no information across steps and the model reduces to a memoryless mixture of experts with a contextual gate. With 𝜂 = (𝑐, {𝜂 𝑧 ′ }) and Θ the action-model parameters, (2) and the regime-conditioned action law of Section 3 define an HMM [8, 18] whose joint probability, for a predictable context sequence 𝑥 1:𝑇 , regime path 𝑧1:𝑇 , and action sequence 𝑎 1:𝑇 , is 𝜈(𝑧1 ) 𝑝 Θ (𝑎 1 | 𝑥1 , 𝑧1 )

𝑇 Ö

𝑃 𝜂 (𝑧 𝑡 | 𝑧 𝑡 −1 , 𝑥 𝑡 ) 𝑝 Θ (𝑎 𝑡 | 𝑥 𝑡 , 𝑧 𝑡 ),

(4)

𝑡=2

with initial distribution 𝜈.

3

Model, Inference, and Learning

Action model. Conditional on 𝑍𝑡 = 𝑧 and context 𝑥, the action follows a choice model assembled from local decisions at the internal nodes. Each child 𝑗 ∈ Ch(𝑣) carries a descriptor 𝑒 𝑣, 𝑗 ∈ R𝑟𝑣 , and we combine context and child identity through 𝜙 𝑣 (𝑥, 𝑒 𝑣, 𝑗 ) = 𝑥¯ ⊗ 𝑒 𝑣, 𝑗 , allowing the same context to change the relative preference among children at a node. The local score is 𝑢 𝑣,𝑧, 𝑗 (𝑥) = 𝜃 0𝑣 + Δ𝑣,𝑧 , 𝜙 𝑣 (𝑥, 𝑒 𝑣, 𝑗 ) ,

(5)

with the vector 𝜃 0𝑣 shared across regimes and Δ𝑣,𝑧 the per-regime residual. The local choice and the action probabilities are 𝜋 𝑣,𝑧 ( 𝑗 | 𝑥) = Í 𝑝 Θ (𝑎 | 𝑥, 𝑧) =

exp 𝑢 𝑣,𝑧, 𝑗 (𝑥) , 𝑘 ∈ C𝑡 (𝑣) exp 𝑢 𝑣,𝑧,𝑘 (𝑥) Ö 𝜋 𝑣,𝑧 ( 𝑗 𝑣 (𝑎) | 𝑥),

(6) 𝑎 ∈ A𝑡 ,

(7)

(𝑣, 𝑗𝑣 (𝑎) ) ∈Path(𝑎)

and zero for 𝑎 ∉ A𝑡 , with the time dependence induced by the mask left implicit. The factorization (7) is a hierarchical softmax [24] with locally normalized choices along the feasible action path; it yields separate supervised likelihood terms at each node and decomposes regime differences across the visited nodes. The decomposition 𝜃 0𝑣 + Δ𝑣,𝑧 implements partial pooling across regimes that reach the same node: the shared term carries the common choice structure and Δ𝑣,𝑧 the regime-specific departures, which are the only source of evidence about the active regime, so shrinking the residuals increases pooling while reducing identification; Í Section 4 quantifies this trade-off. We impose 𝑧 Δ𝑣,𝑧 = 0 and use centered descriptors and a reference child, which identify 𝜃 0𝑣 as the across-regime mean and, with the quadratic penalties, make each supervised node problem strictly convex.

Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 3

Prediction. Let 𝑏 𝑡− (𝑧) = Pr(𝑍𝑡 = 𝑧 | ℎ𝑡− ) be the posterior over the hidden regime before the agent acts and 𝑏 +𝑡 (𝑧) = Pr(𝑍𝑡 = 𝑧 | ℎ+𝑡 ) the posterior after. The predictor is the one-step predictive distribution of the hidden Markov model, obtained by averaging the regime-conditioned action laws over the current belief, ∑︁ 𝑝b𝑡 (𝑎) = 𝑏 𝑡− (𝑧) 𝑝 Θ (𝑎 | 𝑥 𝑡 , 𝑧), 𝑎 ∈ A𝑡 , (8) 𝑧∈Z

and the belief obeys, with 𝑏 1− = 𝜈 and evidence weight ℓ𝑡 (𝑧) defined below, ℓ𝑡 (𝑧) 𝑏 𝑡− (𝑧) , 𝑏 +𝑡 (𝑧) = Í ℓ (𝑟) 𝑏 𝑡− (𝑟) ∑︁𝑟 𝑡 − 𝑏 𝑡+1 (𝑧 ′ ) = 𝑃 𝜂 (𝑧 ′ | 𝑧, 𝑥 𝑡+1 ) 𝑏 +𝑡 (𝑧).

(9) (10)

𝑧

Í In replay ℓ𝑡 (𝑧) = 𝑝 Θ (𝑎 𝑡 | 𝑥 𝑡 , 𝑧), and in detection ℓ𝑡 (𝑧) is the likelihood 𝑎∈ A𝑡 𝜔(𝑒 𝑡 | 𝑎) 𝑝 Θ (𝑎 | 𝑥 𝑡 , 𝑧) induced by the observation channel 𝜔, with ℓ𝑡 ≡ 1 on an evidence-free step; for a tree-prefix observation it reduces to the product of the resolved local choice probabilities. The prediction (8) is committed before ℓ𝑡 is formed and therefore uses only ℎ𝑡− . One step runs (10), one feasible-tree pass per regime for (6)–(7), the prediction (8), and the update (9), in time linear in 𝐾 under (3) and in the size of the feasible tree; Appendix I gives the per-step cost in full and verifies that 𝑏 +𝑡 is a sufficient statistic of the history. Estimation. When regime labels are observed, the penalized negative log-likelihood of one episode is − log 𝜈(𝑧1 ) −

𝑇 ∑︁ log 𝑃 𝜂 (𝑧 𝑡 | 𝑧 𝑡 −1 , 𝑥 𝑡 ) 𝑡=2

−

𝑇 ∑︁

(11) ∑︁

log 𝜋 𝑣,𝑧𝑡 ( 𝑗 | 𝑥 𝑡 ),

𝑡=1 (𝑣, 𝑗 ) ∈Path(𝑎𝑡 )

summed over episodes with quadratic regularizers on (𝑐, 𝜂) and {𝜃 0𝑣 , Δ𝑣,𝑧 }. Every term is the negative log of a softmax linear in the parameters, so with observed regimes the objective is jointly convex and separates into one transition fit and one choice fit per node, each solved by L-BFGS-B under 𝑐 ≥ 0. With latent regimes the marginal likelihood is nonconvex, and Baum–Welch alternates exact forward–backward responsibilities with weighted versions of the same convex subproblems, increasing the penalized marginal likelihood monotonically to a stationary point. Held-out predictive likelihood selects 𝐾. Single-regime trajectories contain no observed switches, so persistence is selected by validation NLL on separate state-preserving switch episodes. Appendix I records the convexity, separability, and uniqueness argument for (11) and the role of the residual in identifiability. Uniform fallback state. For a finite reference loss that does not depend on the fit of the learned regimes, we add a state ⊥ with node probabilities 𝜋 𝑣,⊥ ( 𝑗 | 𝑥) = 𝑁𝑡 ( 𝑗)/𝑁𝑡 (𝑣), where 𝑁𝑡 (𝑣) counts the feasible leaves below 𝑣. These telescope to 𝑝 Θ (𝑎 | 𝑥, ⊥) = 1/|A𝑡 |, uniform over the feasible actions, while preserving the product form (7). As an ordinary state of (3) on 𝐾+1 states, ⊥ gives the fallback guarantee of Section 4, and 𝑏 +𝑡 (⊥) is the weight assigned to it.

4

Analysis

Conditioning on the fitted parameters, we first quantify how the resolution of an observed action determines the evidence it provides about the active regime, then compare cumulative predictive loss with regime paths that may switch. The arguments are short: (12) sums the local laws below 𝑣 from the leaves up, (13) is the Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 4

chain rule for relative entropy on the tree, and (14) keeps one path of the forward recursion. Complete proofs are given in Appendices B–E, under the conventions of Appendix A. Information from partial observations. Lemma 1 (Tree-prefix likelihood). For a node 𝑣 with ancestors an(𝑣), writing A𝑡 (𝑣) = {𝑎 ∈ A𝑡 : 𝑣 ∈ I (𝑎)}, ∑︁ Ö
𝑝 Θ (𝑎 | 𝑥, 𝑧) = 𝜋 𝑣 ′ ,𝑧 𝑗 𝑣 ′ (𝑣) | 𝑥 , (12) 𝑣 ′ ∈an(𝑣)

𝑎∈ A𝑡 (𝑣)

where 𝑗 𝑣 ′ (𝑣) is the child of 𝑣 ′ toward 𝑣. Taking 𝑣 as the root gives normalization over A𝑡 . An observation that resolves the action path to depth 𝑘 therefore has likelihood equal to the product of the 𝑘 resolved local factors, and each resolved node can contribute evidence about the active regime (proof in Appendix B). Corollary 1 (Regime identification rate). Fix 𝑥 and the feasible tree, let the executed action be drawn from regime 𝑧★, and let the evidence resolve the executed path to depth 𝑘, with V𝑘 the set of feasible internal nodes at depth less than 𝑘. For every regime 𝑧, the expected log-likelihood ratio entering (9) is i h ∑︁
★ 𝜌 𝑣,𝑧★ 𝐷 KL 𝜋 𝑣,𝑧★ ∥ 𝜋 𝑣,𝑧 , (13) E log ℓℓ𝑡𝑡(𝑧(𝑧)) = 𝑣 ∈ V𝑘

with 𝜌 𝑣,𝑧★ the probability under 𝑧★ that the path reaches 𝑣. At full resolution the sum equals 𝐷 KL ( 𝑝 Θ (· | 𝑥, 𝑧★) ∥ 𝑝 Θ (· | 𝑥, 𝑧)), so unresolved nodes remove exactly their terms from the expected one-step increase of the posterior log-odds. Each local term is, to second order, a quadratic form in the difference between regime residuals, so residual shrinkage lowers the identification rate, quantifying the trade-off between pooling and regime separation; Appendix C proves the corollary and Appendix I derives the second-order form. Log-loss guarantees. Theorem 1 (Individual-sequence tracking). Let 𝑝b𝑡 be the predictor (8) produced by (9)–(10) with fixed parameters on the replay sequence. For every predictable context sequence 𝑥 1:𝑇 , every realized action sequence satisfying 𝑎 𝑡 ∈ A𝑡 , and every regime path 𝑧1:𝑇 ∈ Z 𝑇 , 𝑇 ∑︁

− log 𝑝b𝑡 (𝑎 𝑡 ) ≤

𝑡=1

𝑇 ∑︁

− log 𝑝 Θ (𝑎 𝑡 | 𝑥 𝑡 , 𝑧 𝑡 )

𝑡=1 𝑇 ∑︁ − log 𝜈(𝑧 1 ) − log 𝑃 𝜂 (𝑧 𝑡 | 𝑧 𝑡 −1 , 𝑥 𝑡 ).

(14)

𝑡=2

The detection setting obeys the same inequality with ℓ𝑡 in place of the action likelihood. Minimizing the right-hand side over 𝑧 1:𝑇 compares the deployed predictor with the regime path of smallest action loss plus its initial and transition cost under the fitted kernel. Appendix D gives the proof and the corresponding detection-setting inequality. Corollary 2 (Fixed share and uniform fallback). With uniform 𝜈 and the homogeneous kernel (3), a comparator path with 𝑆 switches gives 𝑇 ∑︁ 𝑡=1

− log 𝑝b𝑡 (𝑎 𝑡 ) ≤

𝑇 ∑︁

− log 𝑝 Θ (𝑎 𝑡 | 𝑥 𝑡 , 𝑧 𝑡 ) + log 𝐾

𝑡=1 −1 + (𝑇−1−𝑆) log 1𝜅 + 𝑆 log 𝐾1−𝜅 ,

Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 5

(15)

proposed, 0.96

8

0.96

filtered posterior, hierarchical, 7.4k

+0.79

without state dynamics

1.76

fixed weights, 7.4k

+0.39

without learned state

1.35

policy posterior, 1.5k

Action bigram

1.12

reference, 3.1k

0.8

1.0

1.2

NLL (nats per step)

Proposed model

Fixed weights 4

no recovery (4.4 nats)

Policy posterior 2

recovers to 2.0 nats

1

3-step adaptation, recovers to 1.35 nats

Proposed model

0.5 1.4

1.6

1.8

Stationary NLL (nats per step)

(a)

pre

switch

0–4

5–9

10–14

Steps from the controller switch

(b)

Figure 1: (a) Stationary test set, blue-observation context, 90% intervals; each ablation removes one element of the regime posterior and the arrow gives the change in NLL. (b) Mean NLL before a controller switch, at the switch step, and in three five-step windows after it, on a log scale. the fixed-share penalty for tracking changing experts [20, 25] with the regime-conditioned action laws as the experts. If ⊥ is an ordinary state of (3) on 𝐾+1 regimes, the constant comparator 𝑧 𝑡 ≡ ⊥ gives, for every feasible action sequence, 𝑇 ∑︁ 𝑡=1

− log 𝑝b𝑡 (𝑎 𝑡 ) ≤

𝑇 ∑︁

log |A𝑡 | + log(𝐾+1) + (𝑇−1) log 1𝜅 .

(16)

𝑡=1

A single 𝜅 controls both penalties: by (16) the mean loss exceeds uniform coding over the feasible sets by at most log 1𝜅 + log(𝐾+1)/𝑇, so no feasible action sequence is catastrophic, while carrying ⊥ costs 𝐾 a learned-regime comparator only log 𝐾+1 𝐾 + 𝑆 log 𝐾 −1 per episode; Appendix E proves both bounds and Appendix I works the trade-off out numerically. Greater persistence lowers the penalty for staying in one regime but raises the prior evidence to be overcome after a switch; since (3) floors every 𝑏 𝑡− (𝑧 ′ ) at 𝐾1−𝜅 −1 , a Wald-type
argument bounds the expected time for the posterior log-odds to favor the new regime by −1 log 𝐾1−𝜅 + 𝐵 /𝑟, with 𝑟 a floor on the evidence rate (13) and 𝐵 a bound on a single-step log-likelihood ratio, stated and proved as Remark 1 in Appendix F.

5

Experiments

Setup. We evaluate on CAGE Challenge 2 [23, 26] in the bug-fixed CybORG++ build [27, 28], where a red agent attacks a simulated enterprise network against a fixed reactive blue baseline, a setting studied so far mainly from the defender’s side [29, 30, 31]; the closest precedent, [17], imitates a red policy from network observations and reports accuracy. The action tree has the operation at the root (no-op, system discovery, service discovery, exploitation, escalation, impact) and one operation-dependent argument below it, a subnet for system discovery and a host otherwise, giving 56 executable actions. The generating red policies B line, Meander, and Sleep are the policy classes; Sleep is a point mass on no-op, so all predictors are scored on active steps, those whose executed action is not no-op. We train on 40 episodes of length 100 per policy, validate on 10, and hold out 25 per policy as the stationary test set. Switch episodes replace the red controller once at 𝜏 ∼ Unif{30, . . . , 70} with session state preserved; 60 of them select the persistence 𝜅 of the policy-class chain by validation NLL and a disjoint set of 𝑁 scores regime tracking. The context 𝑥 𝑡 holds the observer-available coordinates of the blue observation and features computed from them before Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 6

Table 1: Stationary test set (25 held-out episodes per policy, active steps) and switch test set. NLL in nats per step, top-1 in percent, 10-bin ECE; stationary NLL carries its 90% bootstrap interval and switch intervals are about ±0.3 nats. Choice models are hierarchical unless marked flat. The second group uses the blue-observation context, the third adds the previous action, and bold rows are the proposed model. Stationary Predictor

NLL↓ [CI]

Switch

Top-1↑ ECE↓ NLL↓ ECE↓

Action bigram Masked GRU

1.119 [1.00, 1.22] 0.872 [0.76, 0.96]

63.8 70.5

0.037 1.946 0.077 0.054 1.821 0.112

Fixed state weights Policy-class posterior Posterior mode Filtered posterior, flat Filtered posterior

1.758 [1.66, 1.85] 1.350 [1.26, 1.43] 0.958 [0.85, 1.05] 0.917 [0.81, 1.01] 0.964 [0.86, 1.05]

44.7 56.7 67.4 68.7 67.0

0.186 0.074 0.052 0.059 0.047

No latent state 1.068 [0.97, 1.16] Policy-class posterior 1.033 [0.93, 1.12] Filtered posterior 0.924 [0.82, 1.01]

63.9 64.5 68.0

0.052 2.122 0.089 0.042 2.201 0.088 0.045 1.951 0.084

2.778 2.634 2.142 1.899 1.971

0.232 0.125 0.107 0.105 0.088

the current red action, and the full context adds the previous red action as a one-hot vector. All runs use the replay setting. Metrics are per-step NLL in nats over the feasible set, top-1 accuracy, and 10-bin ECE of the top-1 confidence, with 90% episode-level bootstrap intervals. Estimator and comparisons. The evaluated estimator is a two-stage form of the predictor with convex fits and inputs shared by every compared choice model. A 48-state HMM over actions with an unconstrained transition matrix is fit to the training action sequences without labels, and its filtered posterior 𝑏 𝑡− enters the node scores of the masked choice model linearly beside the context, one convex logistic regression per node. The posterior thus pools the regime laws in the scores, which coincides with (8) at a one-hot posterior; the choice likelihood does not update the chain, so the bounds of Section 4 describe the joint filter (8) and are not claimed for this estimator. Ablations replace the filtered posterior by fixed state weights, by a one-hot encoding of its mode, or by nothing; the hierarchical choice model by a flat softmax over the 56 actions with the same inputs; and the learned chain by a three-state chain whose states are the policy classes with kernel (3). Reference predictors are a first-order Markov model on actions (the action bigram) and a masked GRU seeing the full context and mask and carrying its own recurrent state. Stationary prediction. Table 1 and Figure 1(a) separate the two design choices. Removing the state dynamics costs 0.79 nats per step and 22 points of top-1 accuracy, and replacing the learned chain by the three policy classes costs 0.39, or 0.11 with the full context. The learned states thus carry information beyond the policy label, part of which the previous action supplies. Replacing the posterior by its mode changes nothing while the regime is stable. The flat softmax gains 0.047 nats at 44% more parameters and is worse calibrated. The GRU, at 7,288 parameters, reaches 0.872 nats and 70.5% against 0.924 and 68.0% for the full-context model, with overlapping intervals, and the choice model is the better calibrated of the two. The action bigram is a strong reference at 1.119 nats because B line is close to deterministic given its last action, while uniform coding of the 56 actions costs 4.03. Over a sweep of the training-set size, the hierarchical model is at or below the flat one up to 60 episodes and behind it from 90 on. Appendix I lists the parameter counts of every predictor and the training-set sweep in full. Regime tracking. The switch columns of Table 1 and Figure 1(b) report the switch episodes. At the switch step every predictor loses between 7.3 and 9.5 nats; the filtered hierarchical model loses 7.81, against 8.13 for its mode and 9.23 for the GRU, and its loss begins to fall after three steps against ten for the GRU. Over the whole episode, weighting by the full posterior is worth 0.17 nats per step over its mode, the same margin Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 7

the full-context model holds over no latent state, with overlapping intervals in both cases, though the paired per-episode differences exclude zero. Ten to fourteen steps after the switch, fixed weights stay at 4.4 nats and the policy-class chain at 2.0, against 1.35 for the proposed model; the GRU recovers further, to 1.05 in that window, and ends the episode at 1.821 against 1.951, again inside the intervals. Calibration favors the proposed model under switching as well, ECE 0.084 against 0.112 for the GRU and 0.105 for the flat softmax. Summary. Across both experiments the accuracy of the next-action distribution is set by how well the predictor represents where the attacker is rather than by the capacity of the action model: the filtered latent state is worth 0.8 nats per step over fixed weights and 0.4 over the known policy classes, whereas the hierarchical and flat choice models are separated by 0.047 and the same-size GRU by less than one interval width. What the latent state buys is a calibrated belief rather than a label, and this is where the structure pays: weighting by the full posterior matches its mode in steady state but gains 0.17 nats per step under switching, and the loss begins to fall three steps after a controller change against ten for the GRU, at 30% fewer parameters than the flat model and better calibration than both baselines. The two open directions follow from the two places the belief is still weakest. Fitting the chain and the choice law jointly, rather than in the two stages evaluated here, would let the action likelihood sharpen the regime posterior and would bring the guarantees of Section 4 to bear on the deployed predictor, including the fallback state ⊥ whose absence explains the overconfidence observed against a held-out red policy (Corollary 2, with the measurements in Appendix I). Beyond replay, the same local factors score a partially resolved action, so (13) predicts how much regime evidence survives coarse detections; testing that in the detection setting is the natural next step towards a defender that acts on the prediction.

Acknowledgments This research was developed with funding from the Defense Advanced Research Projects Agency (DARPA). The views, opinions and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of DARPA or the U.S. Government.

References [1] Ralph Allan Bradley and Milton E Terry, “Rank analysis of incomplete block designs: I. the method of paired comparisons,” Biometrika, vol. 39, no. 3/4, pp. 324–345, 1952. [2] Daniel McFadden, “Conditional logit analysis of qualitative choice behavior,” 1972. [3] Rong Yang, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe, and Richard John, “Improving resource allocation strategy against human adversaries in security games,” in IJCAI ProceedingsInternational Joint Conference on Artificial Intelligence. Barcelona, 2011, vol. 22, p. 458. [4] Thanh Nguyen, Rong Yang, Amos Azaria, Sarit Kraus, and Milind Tambe, “Analyzing the effectiveness of adversary modeling in security games,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2013, vol. 27, pp. 718–724. [5] Anand Siththaranjan, Cassidy Laidlaw, and Dylan Hadfield-Menell, “Distributional preference learning: Understanding and accounting for hidden context in rlhf,” in International Conference on Learning Representations, 2024, vol. 2024, pp. 27448–27471. [6] Kenneth Train et al., Discrete choice methods with simulation, vol. 2, Cambridge university press Cambridge, 2003.

Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 8

[7] Sriyash Poddar, Yanming Wan, Hamish Ivison, Abhishek Gupta, and Natasha Jaques, “Personalizing reinforcement learning from human feedback with variational preference learning,” 2024, vol. 37, pp. 52516–52544. [8] Yoshua Bengio and Paolo Frasconi, “An input output hmm architecture,” 1994, vol. 7. [9] Oded Netzer, James M Lattin, and Vikram Srinivasan, “A hidden markov model of customer relationship dynamics,” Marketing science, vol. 27, no. 2, pp. 185–204, 2008. [10] Stefano V Albrecht and Peter Stone, “Autonomous agents modelling other agents: A comprehensive survey and open problems,” Artificial Intelligence, vol. 258, pp. 66–95, 2018. [11] Samer Nashed and Shlomo Zilberstein, “A survey of opponent modeling in adversarial domains,” Journal of Artificial Intelligence Research, vol. 73, pp. 277–327, 2022. [12] Samer Nashed and Shlomo Zilberstein, “A survey of opponent modeling in adversarial domains,” Journal of Artificial Intelligence Research, vol. 73, pp. 277–327, 2022. [13] Georgios Papoudakis, Filippos Christianos, and Stefano Albrecht, “Agent modelling under partial observability for deep reinforcement learning,” 2021, vol. 34, pp. 19210–19222. [14] Pilar Holgado, Vı́ctor A Villagrá, and Luis Vazquez, “Real-time multistep attack prediction based on hidden markov models,” IEEE Transactions on Dependable and Secure Computing, vol. 17, no. 1, pp. 134–147, 2017. [15] Azqa Nadeem, Sicco Verwer, Stephen Moskal, and Shanchieh Jay Yang, “Alert-driven attack graph generation using s-pdfa,” IEEE transactions on dependable and secure computing, vol. 19, no. 2, pp. 731–746, 2021. [16] Teng Li, Ya Jiang, Chi Lin, Mohammad S Obaidat, Yulong Shen, and Jianfeng Ma, “Deepag: Attack graph construction and threats prediction with bi-directional deep learning,” IEEE Transactions on Dependable and Secure Computing, vol. 20, no. 1, pp. 740–757, 2022. [17] Ankita Samaddar, Sandeep Neema, Daniel Balasubramanian, and Xenofon Koutsoukos, “Learning red agent policy from observations for neurosymbolic autonomous cyber agents,” arXiv preprint arXiv:2606.18223, 2026. [18] Lawrence R Rabiner, “A tutorial on hidden markov models and selected applications in speech recognition,” Proceedings of the IEEE, vol. 77, no. 2, pp. 257–286, 1989. [19] Neri Merhav and Meir Feder, “Universal prediction,” IEEE Transactions on Information Theory, vol. 44, no. 6, pp. 2124–2147, 1998. [20] Mark Herbster and Manfred K Warmuth, “Tracking the best expert,” Machine learning, vol. 32, no. 2, pp. 151–178, 1998. [21] Olivier Bousquet and Manfred K Warmuth, “Tracking a small set of experts by mixing past posteriors,” Journal of Machine Learning Research, vol. 3, no. Nov, pp. 363–396, 2002. [22] Wouter M Koolen and Steven de Rooij, “Universal codes from switching strategies,” IEEE Transactions on Information Theory, vol. 59, no. 11, pp. 7168–7185, 2013. [23] Mitchell Kiely, David Bowman, Maxwell Standen, and Christopher Moir, “On autonomous agents in a cyber defence environment,” arXiv preprint arXiv:2309.07388, 2023. Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 9

[24] Frederic Morin and Yoshua Bengio, “Hierarchical probabilistic neural network language model,” in International workshop on artificial intelligence and statistics. PMLR, 2005, pp. 246–252. [25] Nicolo Cesa-Bianchi, Gábor Lugosi, et al., Prediction, learning, and games, vol. 1, Cambridge university press Cambridge, 2006. [26] TTCP CAGE Working Group, cage-challenge-2, 2022.

“TTCP CAGE Challenge 2,” github.com/cage-challenge/

[27] Harry Emerson, Liz Bates, Chris Hicks, and Vasilios Mavroudis, “Cyborg++: An enhanced gym for the development of autonomous cyber agents,” arXiv preprint arXiv:2410.16324, 2024. [28] Maxwell Standen, Martin Lucas, David Bowman, Toby J Richer, Junae Kim, and Damian Marriott, “Cyborg: A gym for the development of autonomous cyber agents,” arXiv preprint arXiv:2108.09118, 2021. [29] Myles Foley, Chris Hicks, Kate Highnam, and Vasilios Mavroudis, “Autonomous network defence using reinforcement learning,” in Proc. ACM Asia Conference on Computer and Communications Security (ASIA CCS), 2022, pp. 1252–1254. [30] Kim Hammar, Neil Dhir, and Rolf Stadler, “Optimal defender strategies for cage-2 using causal modeling and tree search,” arXiv preprint arXiv:2407.11070, 2024. [31] Sanyam Vyas, Vasilios Mavroudis, and Pete Burnap, “Towards the deployment of realistic autonomous cyber network defence: A systematic review,” ACM Computing Surveys, vol. 58, no. 1, pp. 1–36, 2025. [32] Haikady N Nagaraja, Inference in hidden Markov models, Taylor & Francis, 2006.

Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 10

Appendices Proofs, Omitted Results, and Additional Experimental Detail

These appendices collect complete proofs of the results stated in the body, state the results that were omitted there for length, verify the identities asserted in the text, and record the additional experimental detail referenced from it. Equations numbered (1)–(16) are those of the body; equations numbered by appendix section, such as (B.1), are local to the appendices.

A

Conventions Used in the Proofs

All parameters (𝜈, 𝜂, Θ) are fixed, and 𝑡, the context 𝑥, and the masks are fixed wherever a single step is analyzed. Masks are pruned bottom-up, as stated in Section 2: every feasible child of a node on a feasible path retains at least one feasible leaf in its subtree, so the sets C𝑡 (𝑣) are the child sets of a pruned feasible tree whose leaf set is A𝑡 . Every local law is extended by 𝜋 𝑣,𝑧 ( 𝑗 | 𝑥) = 0 for 𝑗 ∉ C𝑡 (𝑣). The softmax (6) is strictly positive on C𝑡 (𝑣), and the background weights 𝑁𝑡 ( 𝑗)/𝑁𝑡 (𝑣) are positive under pruning, so 𝑝 Θ (𝑎 | 𝑥, 𝑧) > 0 for every 𝑎 ∈ A𝑡 and every regime. The kernels (2) and (3) with 𝜅 < 1 are likewise strictly positive, so every divergence below is finite, with the convention 0 log 0 = 0. Two classical facts are used. Pinsker’s 2 ( 𝑝, 𝑞) [25]. The log-sum inequality states that for nonnegative reals inequality states 𝐷 KL ( 𝑝 ∥ 𝑞) ≥ 2 𝑑TV Í Í Í 𝑎 1 , . . . , 𝑎 𝑛 and 𝑏 1 , . . . , 𝑏 𝑛 with 𝐴 = 𝑖 𝑎 𝑖 and 𝐵 = 𝑖 𝑏 𝑖 > 0, 𝑖 𝑎 𝑖 log(𝑎 𝑖 /𝑏 𝑖 ) ≥ 𝐴 log( 𝐴/𝐵); it follows from Í Í Jensen’s inequality for the convex function 𝜑(𝑡) = 𝑡 log 𝑡, since 𝑖 𝑎 𝑖 log(𝑎 𝑖 /𝑏 𝑖 ) = 𝐵 𝑖 (𝑏 𝑖 /𝐵) 𝜑(𝑎 𝑖 /𝑏 𝑖 ) ≥ 𝐵 𝜑( 𝐴/𝐵) = 𝐴 log( 𝐴/𝐵).

B

Proof of Lemma 1

Lemma 1 (Tree-prefix likelihood, restated). For a node 𝑣 with ancestors an(𝑣), writing A𝑡 (𝑣) = {𝑎 ∈ A𝑡 : 𝑣 lies on the root-to-𝑎 path}, ∑︁ Ö
𝑝 Θ (𝑎 | 𝑥, 𝑧) = 𝜋 𝑣 ′ ,𝑧 𝑗 𝑣 ′ (𝑣) | 𝑥 , (12) 𝑎∈ A𝑡 (𝑣)

𝑣 ′ ∈an(𝑣)

where 𝑗 𝑣 ′ (𝑣) is the child of 𝑣 ′ toward 𝑣, extending the leaf notation 𝑗 𝑣 (𝑎) to internal targets. Taking 𝑣 as the root gives normalization over A𝑡 . Proof. If the path from the root to 𝑣 leaves the pruned feasible tree, then A𝑡 (𝑣) = ∅ and at least one factor on the right vanishes by the zero-extension convention, so both sides are zero. Assume therefore that 𝑣 lies on the pruned tree. For a node 𝑢 of the pruned tree define 𝑅(𝑢) := 1 when 𝑢 is a leaf and, when 𝑢 is internal, ∑︁ Ö
𝑅(𝑢) := 𝜋 𝑤,𝑧 𝑗 𝑤 (𝑎) | 𝑥 , 𝑎∈ A𝑡 (𝑢) 𝑤 ∈ I (𝑎) , 𝑤 in the subtree rooted at 𝑢

the mass of the subtree below 𝑢 under the local factors at 𝑢 and its descendants. We show 𝑅(𝑢) = 1 by induction on the height of 𝑢 in the pruned tree. If every child in C𝑡 (𝑢) is a leaf, then A𝑡 (𝑢) consists of the Í leaf children of 𝑢, the product reduces to the single factor at 𝑢, and 𝑅(𝑢) = 𝑗 ∈ C𝑡 (𝑢) 𝜋𝑢,𝑧 ( 𝑗 | 𝑥) = 1 by (6). Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 11

For a general internal 𝑢, the leaves of A𝑡 (𝑢) partition according to the child taken at 𝑢; write 𝑐 𝑗 for the child of 𝑢 with index 𝑗. For a leaf through 𝑐 𝑗 the product splits as 𝜋𝑢,𝑧 ( 𝑗 | 𝑥) times the corresponding product below 𝑐 𝑗 , which is empty, hence one, when 𝑐 𝑗 is a leaf. Pruning guarantees that every child in C𝑡 (𝑢) supports at least one feasible leaf, so the inductive hypothesis applies to each child and ∑︁ ∑︁ 𝑅(𝑢) = 𝜋𝑢,𝑧 ( 𝑗 | 𝑥) 𝑅(𝑐 𝑗 ) = 𝜋𝑢,𝑧 ( 𝑗 | 𝑥) = 1. 𝑗 ∈ C𝑡 (𝑢)

𝑗 ∈ C𝑡 (𝑢)

For the lemma, every 𝑎 ∈ A𝑡 (𝑣) traverses the same ancestor edges (𝑣 ′ , 𝑗 𝑣 ′ (𝑣)) with 𝑣 ′ ∈ an(𝑣), so (7) factors its probability into the fixed ancestor product times the product at and below 𝑣; summing over A (𝑣) and applying 𝑅(𝑣) = 1 gives (12). At the root the ancestor product is empty and (12) states Í𝑡 □ 𝑎∈ A𝑡 𝑝 Θ (𝑎 | 𝑥, 𝑧) = 1. The same bookkeeping yields an identity used repeatedly below. For an internal node 𝑣 of the pruned tree and 𝑗 ∈ C𝑡 (𝑣), restricting the sum to the leaves that take child 𝑗 at 𝑣 isolates the factor 𝜋 𝑣,𝑧 ( 𝑗 | 𝑥) in front of Î the mass of the subtree below that child, which is one, so with 𝜌 𝑣,𝑧 (𝑥) := 𝑣 ′ ∈an(𝑣) 𝜋 𝑣 ′ ,𝑧 ( 𝑗 𝑣 ′ (𝑣) | 𝑥), ∑︁ 𝑝 Θ (𝑎 | 𝑥, 𝑧) = 𝜌 𝑣,𝑧 (𝑥) 𝜋 𝑣,𝑧 ( 𝑗 | 𝑥). (B.1) 𝑎∈ A𝑡 : 𝑣 ∈ I (𝑎) 𝑗𝑣 (𝑎)= 𝑗

By (12), 𝜌 𝑣,𝑧 (𝑥) is the probability that the action path reaches 𝑣; dividing (B.1) by it shows that, conditionally on reaching 𝑣, the child taken at 𝑣 has law 𝜋 𝑣,𝑧 (· | 𝑥).

C

Proof of Corollary 1

Corollary 1 (Regime identification rate, restated). Fix 𝑥 and the feasible tree, let the executed action be drawn from regime 𝑧★, and let the evidence resolve the executed path to depth 𝑘, with V𝑘 the set of feasible internal nodes at depth less than 𝑘. For every regime 𝑧, the expected log-likelihood ratio entering (9) is h i ∑︁
★ E log ℓℓ𝑡𝑡(𝑧(𝑧)) = 𝜌 𝑣,𝑧★ 𝐷 KL 𝜋 𝑣,𝑧★ ∥ 𝜋 𝑣,𝑧 , (13) 𝑣 ∈ V𝑘

with all local laws at the context 𝑥 and 𝜌 𝑣,𝑧★ the probability under 𝑧★ that the action path reaches 𝑣. At full resolution the sum equals 𝐷 KL ( 𝑝 Θ (· | 𝑥, 𝑧★) ∥ 𝑝 Θ (· | 𝑥, 𝑧)), so unresolved nodes remove exactly their terms from the expected one-step increase of the posterior log-odds. Proof. Let 𝐴 ∼ 𝑝 Θ (· | 𝑥, 𝑧★) and write 𝐽𝑣 := 𝑗 𝑣 ( 𝐴) for the child taken at an internal node 𝑣 ∈ I ( 𝐴). Prefix evidence to depth 𝑘 reveals the resolved edges of the executed path: the compatible leaves form A𝑡 (𝑣 𝑘 ) with 𝑣 𝑘 the deepest resolved node, and when the executed leaf lies at depth at most 𝑘 the evidence reveals the leaf Î itself. In either case Lemma 1 gives ℓ𝑡 (𝑧) = 𝑣 ∈ I ( 𝐴)∩V𝑘 𝜋 𝑣,𝑧 (𝐽𝑣 | 𝑥) for every regime 𝑧, so log

∑︁ 𝜋 𝑣,𝑧★ (𝐽𝑣 | 𝑥) ℓ𝑡 (𝑧★) = 1{𝑣 ∈ I ( 𝐴)} log . ℓ𝑡 (𝑧) 𝜋 𝑣,𝑧 (𝐽𝑣 | 𝑥) 𝑣∈V 𝑘

Take expectations termwise. Identity (B.1) at regime 𝑧★ states that the joint probability of reaching 𝑣 and taking child 𝑗 there factors as 𝜌 𝑣,𝑧★ (𝑥) 𝜋 𝑣,𝑧★ ( 𝑗 | 𝑥); equivalently, conditioned on the event {𝑣 ∈ I ( 𝐴)}, whose probability is 𝜌 𝑣,𝑧★ , the child 𝐽𝑣 has law 𝜋 𝑣,𝑧★ (· | 𝑥). Hence for any function 𝑔, E[1{𝑣 ∈ Í I ( 𝐴)} 𝑔(𝐽𝑣 )] = 𝜌 𝑣,𝑧★ 𝑗 𝜋 𝑣,𝑧★ ( 𝑗 | 𝑥) 𝑔( 𝑗). With 𝑔 the logarithmic ratio the inner sum is 𝐷 KL (𝜋 𝑣,𝑧★ ∥ 𝜋 𝑣,𝑧 ), which proves (13); every term is nonnegative because it is a divergence weighted by a probability. When Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 12

V contains all internal nodes, the same computation applied to log[ 𝑝 Θ ( 𝐴 | 𝑥, 𝑧★)/𝑝 Θ ( 𝐴 | 𝑥, 𝑧)] = Í𝑘 ★ 𝑣 ∈ I ( 𝐴) log[𝜋 𝑣,𝑧★ (𝐽𝑣 | 𝑥)/𝜋 𝑣,𝑧 (𝐽𝑣 | 𝑥)] gives 𝐷 KL ( 𝑝 Θ (· | 𝑥, 𝑧 ) ∥ 𝑝 Θ (· | 𝑥, 𝑧)). Finally, (9) implies + ★ + − ★ − ★ log[𝑏 𝑡 (𝑧 )/𝑏 𝑡 (𝑧)] = log[𝑏 𝑡 (𝑧 )/𝑏 𝑡 (𝑧)] + log[ℓ𝑡 (𝑧 )/ℓ𝑡 (𝑧)], so (13) is the expected increase of the posterior log-odds produced by the measurement update, and unresolved nodes remove exactly their terms. □

D

Proof of Theorem 1

Theorem 1 (Individual-sequence tracking, restated). Let 𝑝b𝑡 be the predictor (8) produced by (9)–(10) with fixed parameters, on the replay sequence. For every context sequence 𝑥 1:𝑇 predictable at each step, meaning each 𝑥 𝑡 is a function of ℎ𝑡− , every action sequence 𝑎 1:𝑇 , and every regime path 𝑧1:𝑇 ∈ Z 𝑇 , 𝑇 ∑︁

− log 𝑝b𝑡 (𝑎 𝑡 ) ≤

𝑡=1

𝑇 ∑︁

− log 𝑝 Θ (𝑎 𝑡 | 𝑥 𝑡 , 𝑧 𝑡 )

𝑡=1 𝑇 ∑︁ − log 𝜈(𝑧 1 ) − log 𝑃 𝜂 (𝑧 𝑡 | 𝑧 𝑡 −1 , 𝑥 𝑡 ).

(14)

𝑡=2

No assumption is placed on the process generating 𝑎 1:𝑇 : the inequality holds pointwise on sequences, so the deployed filter tracks the best regime path in hindsight, and the fallback state of Corollary 2 supplies a nonvacuous comparator even when no learned regime fits. Proof. Fix the realized observer data and the scored sequence 𝑎 1:𝑇 . Predictability means that 𝑥 𝑡 and the masks at step 𝑡 are fixed functions of the realized prefix ℎ𝑡− , which contains 𝑎 1:𝑡 −1 in replay; in particular no 𝑥 𝑠 depends on the hidden path or on actions after step 𝑠. Define 𝑚 0 := 1 and, for 𝑡 ≥ 1, 𝑚 𝑡 :=

∑︁

𝜈(𝑧 1 )

𝑧1:𝑡

𝑡 Ö

𝑃 𝜂 (𝑧 𝑠 | 𝑧 𝑠−1 , 𝑥 𝑠 )

𝑠=2

𝑡 Ö

𝑝 Θ (𝑎 𝑠 | 𝑥 𝑠 , 𝑧 𝑠 ),

𝑠=1

the model probability of 𝑎 1:𝑡 with every factor evaluated at the realized inputs. Introduce the unnormalized forÍ ward variables 𝛼1 (𝑧) := 𝜈(𝑧) 𝑝 Θ (𝑎 1 | 𝑥1 , 𝑧) and, for 𝑡 ≥ 2, 𝛼𝑡 (𝑧) := 𝑝 Θ (𝑎 𝑡 | 𝑥 𝑡 , 𝑧) 𝑧 ′ 𝑃 𝜂 (𝑧 | 𝑧 ′ , 𝑥 𝑡 ) 𝛼𝑡 −1 (𝑧 ′ ); Í summing out the hidden path gives 𝑚 𝑡 = 𝑧 𝛼𝑡 (𝑧). We claim that the recursion (9)–(10), run with the replay evidence ℓ𝑡 (𝑧) = 𝑝 Θ (𝑎 𝑡 | 𝑥 𝑡 , 𝑧), satisfies 𝑏 +𝑡 = 𝛼𝑡 /𝑚 𝑡 and 𝑝b𝑡 (𝑎 𝑡 ) = 𝑚 𝑡 /𝑚 𝑡 −1 for every 𝑡. For 𝑡 = 1, 𝑏 1− = 𝜈 Í gives 𝑝b1 (𝑎 1 ) = 𝑧 𝜈(𝑧) 𝑝 Θ (𝑎 1 | 𝑥 1 , 𝑧) = 𝑚 1 = 𝑚 1 /𝑚 0 and 𝑏 +1 (𝑧) = ℓ1 (𝑧) 𝜈(𝑧)/𝑚 1 = 𝛼1 (𝑧)/𝑚 1 . Assume Í 𝑏 +𝑡 −1 = 𝛼𝑡 −1 /𝑚 𝑡 −1 . Then (10) gives 𝑏 𝑡− (𝑧) = 𝑧 ′ 𝑃 𝜂 (𝑧 | 𝑧 ′ , 𝑥 𝑡 ) 𝛼𝑡 −1 (𝑧 ′ )/𝑚 𝑡 −1 , hence by (8) 1

∑︁

∑︁

𝑃 𝜂 (𝑧 | 𝑧 ′ , 𝑥 𝑡 ) 𝛼𝑡 −1 (𝑧 ′ ) 𝑚 𝑡 −1 𝑧 𝑧′ 𝑚𝑡 , = 𝑚 𝑡 −1 Í − and (9) gives 𝑏 +𝑡 (𝑧) = ℓ𝑡 (𝑧) 𝑏 𝑡− (𝑧) 𝑟 ℓ𝑡 (𝑟) 𝑏 𝑡 (𝑟) = 𝛼𝑡 (𝑧)/𝑚 𝑡 , closing the induction. The product therefore telescopes, 𝑇 Ö ∑︁ Ö 𝑝b𝑡 (𝑎 𝑡 ) = 𝑚 𝑇 = 𝜈(𝑧1′ ) 𝑃 𝜂 (𝑧 ′𝑡 | 𝑧 ′𝑡 −1 , 𝑥 𝑡 ) 𝑝b𝑡 (𝑎 𝑡 ) =

𝑡=1

𝑝 Θ (𝑎 𝑡 | 𝑥 𝑡 , 𝑧)

′ 𝑧1:𝑇

𝑡 ≥2

×

𝑇 Ö

(D.1) 𝑝 Θ (𝑎 𝑡 | 𝑥 𝑡 , 𝑧 ′𝑡 ),

𝑡=1

and every summand of (D.1) is nonnegative, so 𝑚 𝑇 is at least the single summand indexed by the comparator path 𝑧 1:𝑇 . Taking negative logarithms yields (14). All quantities are finite whenever 𝜈(𝑧1 ) > 0: the Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 13

conservative masks keep 𝑎 𝑡 ∈ A𝑡 , so every action-model factor is positive, and the kernels are strictly positive. No property of the mechanism generating 𝑎 1:𝑇 was used, so the inequality holds pointwise on sequences. □ The argument is the standard evaluation of a Bayesian mixture by the forward algorithm, as in the analysis of tracking a changing best expert [20, 25]; it is recorded in full because the input-dependent kernel and the mask-dependent action model enter the bookkeeping. The same telescoping yields the Í corresponding guarantee for the detection evidence of Section 3. Let the channel satisfy 𝑒 𝜔(𝑒 | 𝑎) = 1, and Í − let 𝑞b𝑡 := 𝑧 𝑏 𝑡 (𝑧) ℓ𝑡 (𝑧) be the predictive probability of the received evidence. Replacing every action-model factor by the evidence weight ℓ𝑡 in the argument above gives, for every comparator path, 𝑇 ∑︁

− log 𝑞b𝑡 ≤

𝑡=1

𝑇 ∑︁

− log ℓ𝑡 (𝑧 𝑡 )

𝑡=1

− log 𝜈(𝑧 1 ) −

𝑇 ∑︁

log 𝑃 𝜂 (𝑧 𝑡 | 𝑧 𝑡 −1 , 𝑥 𝑡 ).

𝑡=2

E

Proof of Corollary 2

The two bounds of Corollary 2 are proved in turn. Corollary 2, fixed-share bound (restated). With uniform 𝜈 and the homogeneous kernel (3), a comparator path with 𝑆 switches gives 𝑇 ∑︁

− log 𝑝b𝑡 (𝑎 𝑡 ) ≤

𝑇 ∑︁

𝑡=1

− log 𝑝 Θ (𝑎 𝑡 | 𝑥 𝑡 , 𝑧 𝑡 ) + log 𝐾

𝑡=1

(15)

−1 + (𝑇−1−𝑆) log 1𝜅 + 𝑆 log 𝐾1−𝜅 .

The bound is the fixed-share guarantee for tracking a changing best expert [20, 25], with the regime-conditioned choice laws as the experts. Proof. Under uniform 𝜈, − log 𝜈(𝑧1 ) = log 𝐾. Under (3) the comparator’s 𝑇 − 1 transitions comprise 𝑇 − 1 − 𝑆 −1 self-transitions, each contributing log 1𝜅 , and 𝑆 switches, each contributing log 𝐾1−𝜅 ; substituting into (14) gives (15). The resulting guarantee coincides with the fixed-share bound for tracking a changing best expert [20]. □ Corollary 2, uniform fallback (restated). With ⊥ an ordinary state of the homogeneous kernel (3) on the 𝐾+1 regimes and uniform 𝜈, the constant comparator 𝑧 𝑡 ≡ ⊥ in (14) gives, for every action sequence, 𝑇 ∑︁ 𝑡=1

− log 𝑝b𝑡 (𝑎 𝑡 ) ≤

𝑇 ∑︁

log |A𝑡 | + log(𝐾+1) + (𝑇−1) log 1𝜅 ,

(16)

𝑡=1 log(𝐾+1)

the 𝑆=0 case of (15) at comparator ⊥, so the mean loss exceeds uniform coding by at most log 1𝜅 + . 𝑇 Relative to the model without ⊥, the right side of (15) for a comparator path through the learned regimes 𝐾 with 𝑆 switches increases by exactly log 𝐾+1 𝐾 + 𝑆 log 𝐾 −1 over the episode. Proof. First, the background regime is well defined on the pruned tree. For an internal node 𝑣, the Í feasible leaves below 𝑣 partition among its feasible children, so 𝑗 ∈ C𝑡 (𝑣) 𝑁𝑡 ( 𝑗) = 𝑁𝑡 (𝑣) and the weights 𝜋 𝑣,⊥ ( 𝑗 | 𝑥) = 𝑁𝑡 ( 𝑗)/𝑁𝑡 (𝑣) are positive and sum to one; along the path of any 𝑎 ∈ A𝑡 the ratios telescope, giving 𝑝 Θ (𝑎 | 𝑥, ⊥) = 1/𝑁𝑡 (root) = 1/|A𝑡 |, while ⊥ retains the product form (7) and hence Lemma 1. Apply Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 14

(14) on the homogeneous kernel over 𝐾 + 1 regimes with uniform 𝜈 and the constant comparator 𝑧 𝑡 ≡ ⊥: the initial term is log(𝐾+1), all 𝑇 − 1 transitions are self-transitions contributing log 1𝜅 each, and the emission Í terms are 𝑡 log |A𝑡 |; this is (16) and is the 𝑆=0 case of (15) on 𝐾+1 states. Dividing by 𝑇 and using log(𝐾+1) (𝑇 − 1)/𝑇 ≤ 1 bounds the mean loss by the mean of log |A𝑡 | plus log 1𝜅 + . For the last claim, fix a 𝑇 comparator path through the 𝐾 learned regimes with 𝑆 switches and compare the right side of (15) on 𝐾+1 states with the same quantity on 𝐾 states at the same 𝜅: the emission terms and the 𝑇−1−𝑆 self-transition 𝐾 𝐾 −1 𝐾 terms agree, the initial term grows by log 𝐾+1 𝐾 , and each switch term grows by log 1−𝜅 − log 1−𝜅 = log 𝐾 −1 , giving the stated increase. □

F

Adaptation Delay After a Switch

The following remark is referenced at the end of Section 4, where only its conclusion is quoted. Remark 1 (Adaptation delay). Suppose the regime switches to 𝑧★ and subsequent actions are drawn from 𝑝 Θ (· | 𝑥 𝑡 , 𝑧★) and fully observed. Kernel (3) keeps every 𝑏 𝑡− (𝑧) ≥ (1 − 𝜅)/(𝐾 − 1), so the initial log-odds −1 deficit of 𝑧★ against a fixed regime 𝑧 is at most log 𝐾1−𝜅 . Before 𝑧★ overtakes 𝑧 the homogeneous time update cannot increase this deficit, while each fully observed action contributes the expected evidence in (13). If that rate remains at least 𝑟 > 0 and each single-step
log-likelihood ratio has magnitude at most 𝐵, the expected −1 pairwise crossing time is at most log 𝐾1−𝜅 + 𝐵 /𝑟. Proof. Fix 𝑧 ≠ 𝑧★ and let 𝐷 𝑡 = log[𝑏 𝑡− (𝑧)/𝑏 𝑡− (𝑧★)] denote the log-odds deficit of 𝑧★, with 𝑡 = 0 the first prediction after the switch. The time update under (3) leaves every regime mass at least (1 − 𝜅)/(𝐾 − 1), so −1 𝐷 0 ≤ log 𝐾1−𝜅 . One step consists of the measurement (9) followed by the time update (10). The measurement adds −Λ𝑡 to the log-odds, where Λ𝑡 = log[ℓ𝑡 (𝑧★)/ℓ𝑡 (𝑧)]. Under (3) the time update acts on each belief coordinate as 1−𝜅 𝑏 ↦→ 𝛼𝑏 + 𝛽 with 𝛼 = 𝜅 − 𝐾1−𝜅 −1 ≥ 0 and 𝛽 = 𝐾 −1 > 0. For 𝑏 1 , 𝑏 2 > 0 the ratio (𝛼𝑏 1 + 𝛽)/(𝛼𝑏 2 + 𝛽) is a weighted mediant of 𝑏 1 /𝑏 2 and 1 and lies between them, so the time update moves the log-odds toward zero and preserves their sign. Let 𝜏 = min{𝑡 ≥ 1 : 𝐷 𝑡 ≤ 0}. While 𝜏 > 𝑡+1 the post-measurement odds are still positive, the time Í update shrinks them, and 𝐷 𝑡+1 ≤ 𝐷 𝑡 − Λ𝑡 ; by induction 𝐷 𝑡 ≤ 𝐷 0 − 𝑠<𝑡 Λ𝑠 for 𝑡 < 𝜏. Hence 𝜏 ≤ 𝜏 ′ , where 𝜏 ′ is the first time the partial sums of the Λ𝑠 exceed 𝐷 0 . The action is drawn from 𝑝 Θ (· | 𝑥 𝑡 , 𝑧★), so Corollary 1 gives E[Λ𝑡 | F𝑡 − ] = 𝑟 (𝑥 𝑡 ). Write 𝑟 := inf 𝑡 𝑟 (𝑥 𝑡 ) > Í 0 for the assumed rate floor and let 𝐵 bound |Λ𝑡 |. The sums 𝑠<𝑡 (Λ𝑠 −𝑟 (𝑥 𝑠 )) form a martingale with increments in [−2𝐵, 2𝐵], and Azuma’s inequality gives Pr(𝜏 ′ > 𝑡) ≤ exp{−(𝑟𝑡 − 𝐷 0 )+2 /(8𝑡𝐵2 )}, so E[𝜏 ′ ] < ∞. The Í stopped sum exceeds 𝐷 0 by at most one increment, so optional stopping gives 𝑟 E[𝜏 ′ ] ≤ E 𝑠<𝜏 ′ Λ𝑠 ≤ 𝐷 0 +𝐵.
−1 Therefore E[𝜏] ≤ (𝐷 0 + 𝐵)/𝑟 ≤ log 𝐾1−𝜅 + 𝐵 /𝑟. □ Both constants are finite in the setting of Section 5: the feasible tree has bounded depth and the utilities (5) are bounded on the finite descriptor set, so the per-node log-ratios, and hence Λ𝑡 , are bounded, giving a finite 𝐵; and whenever the post-switch regime 𝑧★ is separated from 𝑧 at some reachable node, the corresponding term of (13) is strictly positive, giving 𝑟 > 0.

G

Cost of Committing to One Regime

Appendices G and H record two results that quantify, respectively, the cost of collapsing the posterior average to a single regime and the exact per-step divergence of the joint model. Neither is used in the body; both are stated and proved here in full.

Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 15

Proposition 1 (Cost of committing to one regime). Fix 𝑥 and a belief 𝑏 with 𝑏(b 𝑧) < 1; write 𝑝 𝑧 = 𝑝 Θ (· | 𝑥, 𝑧), Í 𝑝¯ = 𝑧 𝑏(𝑧) 𝑝 𝑧 , b 𝑧 ∈ arg max𝑧 𝑏(𝑧), let 𝑝¯ −b𝑧 be the remainder renormalized, and let 𝐺 cmt = 𝐷 KL ( 𝑝¯ ∥ 𝑝b𝑧 ) be the excess log-loss of committing to b 𝑧 . Then 𝑝¯ uniquely minimises E 𝑝¯ [− log 𝑞( 𝐴)], the excess of any 𝑞 is 𝐷 KL ( 𝑝¯ ∥ 𝑞), and ∑︁
2 2

2 1 − 𝑏(b 𝑧) 𝑑TV 𝑝b𝑧 , 𝑝¯ −b𝑧 ≤ 𝐺 cmt ≤ 𝑏(𝑧) 𝐷 KL 𝑝 𝑧 ∥ 𝑝b𝑧 . (G.1) 𝑧

Proof. Every 𝑝 𝑧 is positive on A𝑡 , hence so is 𝑝, ¯ and 𝑝¯ −b𝑧 = ( 𝑝¯ − 𝑏(b 𝑧) 𝑝b𝑧 )/(1 − 𝑏(b 𝑧)) is a probability distribution because 𝑏(b 𝑧) < 1 and 𝑝¯ ≥ 𝑏(b 𝑧) 𝑝b𝑧 pointwise. For any distribution 𝑞 on A𝑡 , E 𝑝¯ [− log 𝑞( 𝐴)] = 𝐻 ( 𝑝) ¯ + 𝐷 KL ( 𝑝¯ ∥ 𝑞), which is minimized exactly when 𝐷 KL ( 𝑝¯ ∥ 𝑞) = 0, that is at 𝑞 = 𝑝, ¯ and the excess of any 𝑞 is 𝐷 KL ( 𝑝¯ ∥ 𝑞); taking 𝑞 = 𝑝b𝑧 identifies 𝐺 cmt , finite by positivity of 𝑝b𝑧 . For the lower bound, 𝑝¯ − 𝑝b𝑧 = (1 − 𝑏(b 𝑧)) ( 𝑝¯ −b𝑧 − 𝑝b𝑧 ) pointwise, so 𝑑TV ( 𝑝, ¯ 𝑝b𝑧 ) = (1 − 𝑏(b 𝑧)) 𝑑TV ( 𝑝b𝑧 , 𝑝¯ −b𝑧 ), and Pinsker’s inequality 2 2 2 gives 𝐺 cmt ≥ 2 𝑑TV ( 𝑝, ¯ 𝑝b𝑧 ) = 2(1 − 𝑏(b 𝑧)) 𝑑TV ( 𝑝b𝑧 , 𝑝¯ −b𝑧 ). For the upper bound, apply the log-sum inequality at each 𝑎 with 𝑎 𝑧 = 𝑏(𝑧) 𝑝 𝑧 (𝑎) and 𝑏 𝑧 = 𝑏(𝑧) 𝑝b𝑧 (𝑎): 𝑝(𝑎) ¯ log and summing over 𝑎 gives 𝐺 cmt ≤

H

Í

∑︁ 𝑝 𝑧 (𝑎) 𝑝(𝑎) ¯ 𝑏(𝑧) 𝑝 𝑧 (𝑎) log ≤ , 𝑝b𝑧 (𝑎) 𝑝b𝑧 (𝑎) 𝑧

𝑧 ). 𝑧 𝑏(𝑧) 𝐷 KL ( 𝑝 𝑧 ∥ 𝑝b

□

A Per-Step Divergence Identity

Proposition 2 (Per-step divergence). Fix 𝑥 and a common feasible tree. For joint laws 𝑃(𝑧, 𝑎) = Î 𝑤(𝑧) (𝑣, 𝑗𝑣 (𝑎) ) ∈Path(𝑎) 𝜋 𝑣,𝑧 ( 𝑗 𝑣 (𝑎) | 𝑥) with belief vectors 𝑤★, 𝑤 b and reach probabilities 𝜌★𝑣,𝑧 = 𝑃★ (𝑣 ∈ I ( 𝐴) | 𝑧),

b𝑍 𝐴 = 𝐷 KL 𝑤★ ∥ 𝑤 𝐷 KL 𝑃★𝑍 𝐴 ∥ 𝑃 b ∑︁ ∑︁
(H.1) + 𝑤★ (𝑧) 𝜌★ 𝐷 𝜋★ ∥ b 𝜋 , 𝑣,𝑧

KL

𝑣,𝑧

𝑣,𝑧

𝑣∈I

𝑧

b𝐴) ≤ 𝐷 KL (𝑃★ ∥ 𝑃 b𝑍 𝐴). and 𝐷 KL (𝑃★𝐴 ∥ 𝑃 𝑍𝐴 Proof. Insert 𝑃(𝑧, 𝑎) = 𝑤(𝑧) 𝑃(𝑎 | 𝑧) and split the logarithm:
∑︁ ★ 𝑤★ (𝑧) b𝑍 𝐴 = 𝐷 KL 𝑃★𝑍 𝐴 ∥ 𝑃 𝑤 (𝑧) log 𝑤 b (𝑧) 𝑧 ∑︁
b𝐴| 𝑧 , + 𝑤★ (𝑧) 𝐷 KL 𝑃★𝐴| 𝑧 ∥ 𝑃 𝑧

with all terms finite because 𝑤 b and the local laws are positive on the common feasible tree. Fix 𝑧 and let 𝐴 ∼ 𝑃★𝐴| 𝑧 . As in the proof of Corollary 1, log

𝜋★𝑣,𝑧 ( 𝑗 𝑣 ( 𝐴) | 𝑥) 𝑃★ ( 𝐴 | 𝑧) ∑︁ = 1{𝑣 ∈ I ( 𝐴)} log , b 𝐴 | 𝑧) b 𝜋 𝑣,𝑧 ( 𝑗 𝑣 ( 𝐴) | 𝑥) 𝑃( 𝑣∈I

and taking expectations termwise, using (B.1) at the law 𝜋★𝑣,𝑧 exactly as in the proof of Corollary 1 b𝐴| 𝑧 ) = to factor each term into the reach probability 𝜌★𝑣,𝑧 times a local divergence, gives 𝐷 KL (𝑃★𝐴| 𝑧 ∥ 𝑃 Í ★ ★ 𝜋 𝑣,𝑧 ), which is (H.1). The final inequality is the chain rule in the other direction, 𝑣 ∈ I 𝜌 𝑣,𝑧 𝐷 KL (𝜋 𝑣,𝑧 ∥ b 
 ★ b b𝐴) + E 𝑃★ 𝐷 KL 𝑃★ ∥ 𝑃 b𝑍 | 𝐴 ≥ 𝐷 KL (𝑃★ ∥ 𝑃 b𝐴). 𝐷 KL (𝑃 𝑍 𝐴 ∥ 𝑃 𝑍 𝐴) = 𝐷 KL (𝑃★𝐴 ∥ 𝑃 □ 𝐴 𝑍|𝐴 𝐴 Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 16

I

Details Referenced from the Body

This appendix supplies the derivations, identity checks, and experimental detail that the body asserts or references without developing. The items are grouped by the part of the paper they support.

I.1

Model, inference, and estimation

The persistence mapping (Section 2). With 𝜂 ≡ 0 the numerator of (2) equals 𝑒 𝑐 at 𝑧 ′ = 𝑧 and 1 otherwise, and the denominator equals 𝑒 𝑐 + 𝐾 − 1, so the self-transition probability is 𝜅 = 𝑒 𝑐 /(𝑒 𝑐 + 𝐾 − 1) and every off-diagonal entry is 1/(𝑒 𝑐 + 𝐾 − 1) = (1 − 𝜅)/(𝐾 − 1); moreover 𝑐 ≥ 0 holds exactly when 𝜅 ≥ 1/𝐾, and 𝜅 ↑ 1 as 𝑐 → ∞. Under (3) the holding time of a regime is geometric with parameter 1 − 𝜅, hence the mean dwell 1/(1 − 𝜅). The static restriction at 𝑐 = 0 (Section 2). At 𝑐 = 0 all rows of (2) coincide with softmax𝑧 ′ (𝜂⊤𝑧 ′ 𝑥¯𝑡 ), so for 𝑡 ≥ 2 the time update (10) returns that gate for every 𝑏 +𝑡 −1 ; after the common initialization 𝜈 at 𝑡 = 1 the filter carries no information across steps and the predictor reduces to the static contextual mixture. The persistent and static models are therefore nested and are compared by held-out predictive NLL in Section 5. Identification of the transition parameters (Section 2). The destination coefficients of (2) are determined only up to a common shift, so we set 𝜂 𝑧ref = 0 for one reference regime. Using destination-specific context effects together with a single shared persistence term 𝑐 keeps the transition model at 𝐾 context vectors rather than 𝐾 2 , which matters because switch data are sparse. The mask decomposition (Section 2). Let 𝑆𝑡 be the true support of 𝐴𝑡 and A𝑡 ⊇ 𝑆𝑡 the conservative feasible set. For 𝑎 𝑡 ∈ 𝑆𝑡 the law renormalized to 𝑆𝑡 satisfies 𝑝b𝑡 (𝑎 𝑡 ) = 𝑝b𝑡𝑆 (𝑎 𝑡 ) 𝑝b𝑡 (𝑆𝑡 ), so the log loss splits into the loss on the true support and the log-probability the model assigns to it; a mask that excluded 𝑎 𝑡 would force 𝑝b𝑡 (𝑎 𝑡 ) = 0 by (7) and infinite loss, which is why the masks are conservative. Identifiability through the residual (Section 3). If Δ𝑣,𝑧 ≡ 0 then 𝑝 Θ (· | 𝑥, 𝑧) does not depend on 𝑧, every evidence weight ℓ𝑡 is constant in 𝑧, (9) returns 𝑏 +𝑡 = 𝑏 𝑡− , and the posterior equals the prior propagated by (10): no action sequence moves it. Convexity, separability, and uniqueness of the estimator (Section 3). Each summand of (11) has the form Í log 𝑘 exp 𝑢 𝑘 − 𝑢 𝑗 with utilities affine in the parameters, the composition of the convex log-sum-exp function with an affine map, hence convex; the objective is a sum of such terms and quadratics, is jointly convex, and separates because the parameters of node 𝑣 enter only the terms of node 𝑣 and (𝑐, 𝜂) only the transition terms. Í The ridge penalties make each block strictly convex, so its minimiser is unique; the constraints 𝑧 Δ𝑣,𝑧 = 0, the reference child, and the centered descriptors remove the directions the likelihood cannot see, so that 𝜃 0𝑣 is the across-regime mean preference. In Baum–Welch the maximisation step solves the responsibility-weighted versions of the same convex blocks, and the usual EM argument gives monotone ascent of the penalized marginal likelihood to a stationary point [32]. Sufficiency of the belief (Section 3). Under the model, the conditional law of (𝑍𝑡+1 , 𝐴𝑡+1 ) given F𝑡+ − and depends on the history only through 𝑏 +𝑡 and the forthcoming inputs, because (10) maps (𝑏 +𝑡 , 𝑥 𝑡+1 ) to 𝑏 𝑡+1 the emission depends on (𝑥 𝑡+1 , 𝑍𝑡+1 ) alone; iterating, 𝑏 +𝑡 is a sufficient statistic of the history for the regime given the context process. The per-step cost (Section 3). One filtering step costs 𝑂 (𝐾 2 ) for the time update (10) under the general
Í kernel (2) and 𝑂 𝐾 𝑣 (𝑑 𝑟 𝑣 + |C𝑡 (𝑣)| 𝑟 𝑣 ) for the tree traversals. Reshaping 𝜃 0𝑣 + Δ𝑣,𝑧 as a (𝑑+1) × 𝑟 𝑣 matrix ⊤ Θ𝑣,𝑧 gives 𝑢 𝑣,𝑧, 𝑗 (𝑥) = 𝑥¯ ⊤ Θ𝑣,𝑧 𝑒 𝑣, 𝑗 ; computing 𝑔 := Θ⊤ 𝑣,𝑧 𝑥¯ once costs 𝑂 (𝑑 𝑟 𝑣 ) and each child score 𝑔 𝑒 𝑣, 𝑗 costs 𝑂 (𝑟 𝑣 ), giving the stated 𝑂 (𝑑
𝑟 𝑣 + |C𝑡 (𝑣)| 𝑟 𝑣 ) per node and regime, while under (3) the time update is 1−𝜅 + ′ the affine map 𝑏 − (𝑧 ′ ) = 𝜅 − 𝐾1−𝜅 −1 𝑏 (𝑧 ) + 𝐾 −1 , computed in 𝑂 (𝐾).

Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 17

I.2

Analysis and guarantees

Second-order form of the evidence rate (Corollary 1, Section 4). Fix a node 𝑣 and write 𝑢 𝑗 = 𝑢 𝑣,𝑧★ , 𝑗 (𝑥) and 𝑢 𝑗 − 𝛿 𝑗 = 𝑢 𝑣,𝑧, 𝑗 (𝑥), so that 𝛿 𝑗 = ⟨Δ𝑣,𝑧★ − Δ𝑣,𝑧 , 𝜙 𝑣 (𝑥, 𝑒 𝑣, 𝑗 )⟩ by (5). With 𝑝 = 𝜋 𝑣,𝑧★ (· | 𝑥) = softmax(𝑢) Í Í and 𝑞 = 𝜋 𝑣,𝑧 (· | 𝑥) = softmax(𝑢 − 𝛿), the log-partition expansion log 𝑗 𝑒 𝑢 𝑗 − 𝛿 𝑗 = log 𝑗 𝑒 𝑢 𝑗 − E 𝑝 [𝛿] + Í 𝑢𝑗 − 𝛿𝑗 Í 1 3 − log 𝑗 𝑒 𝑢 𝑗 = 21 Var 𝑝 (𝛿) + 𝑂 (∥𝛿∥ 3 ). 2 Var 𝑝 (𝛿) + 𝑂 (∥𝛿∥ ) gives 𝐷 KL ( 𝑝 ∥ 𝑞) = E 𝑝 [𝛿] + log 𝑗 𝑒 ★ Substituting 𝛿 𝑗 = ⟨Δ𝑣,𝑧★ − Δ𝑣,𝑧 , 𝜙 𝑣 (𝑥, 𝑒 𝑣, 𝑗 )⟩
and weighting by the reach 𝜌 𝑣,𝑧 turns each term of (13) into 1 ⊤ ★ ★ ★ 2 𝜌 𝑣,𝑧 (Δ𝑣,𝑧 − Δ𝑣,𝑧 ) Cov 𝜋𝑣,𝑧★ 𝜙 𝑣 (𝑥, 𝑒 𝑣,· ) (Δ𝑣,𝑧 − Δ𝑣,𝑧 ), a quadratic form in the residual differences; the ridge on Δ therefore shrinks the residual differences and, through this quadratic form, lowers the identification rate directly, which is the trade between pooling and identification discussed in Section 3. The hard-commitment comparison (Section 4). Since (8) averages nonnegative terms, 𝑝b𝑡 (𝑎) ≥ 𝑏 𝑡− (𝑧) 𝑝 Θ (𝑎 | 𝑥 𝑡 , 𝑧) for every 𝑧, whence − log 𝑝b𝑡 (𝑎) ≤ − log 𝑝 Θ (𝑎 | 𝑥 𝑡 , 𝑧) + log(1/𝑏 𝑡− (𝑧)): the posterior average never loses more than log(1/𝑏 𝑡− (𝑧)) per step against any single regime it still gives weight to. A worked example for Corollary 2 (Section 4). At 𝑇 = 100, 𝐾 = 3, and 𝜅 = 0.99, the fallback bound log 4 1 (16) exceeds uniform coding over the feasible sets by at most log 0.99 + 100 = 0.01005 + 0.01386 < 0.024 nats per step. At the same 𝐾 and one switch, carrying ⊥ raises the learned-regime penalty of (15) by 𝐾 4 3 log 𝐾+1 𝐾 + log 𝐾 −1 = log 3 + log 2 = log 2 = 0.693 . . . nats per episode, the 𝑆=1 instance of the premium 𝐾+1 𝐾 log 𝐾 + 𝑆 log 𝐾 −1 . A single 𝜅 therefore buys a cheap worst-case guarantee at a small cost to the switching comparator. Optimality of the posterior weighting (after Proposition 2). Under the model, Pr( 𝐴𝑡 = 𝑎 | F𝑡 − ) = Í Pr(𝑍𝑡 = 𝑧 | F𝑡 − ) 𝑝 Θ (𝑎 | 𝑥 𝑡 , 𝑧) = 𝑝b𝑡 (𝑎). For any F𝑡 − -measurable weighting 𝑤, the mixture 𝑞 𝑤 := Í𝑧 − − b𝑡 ) + 𝐷 KL ( 𝑝b𝑡 ∥ 𝑞 𝑤 ); subtracting the same 𝑧 𝑤(𝑧) 𝑝 𝑧 is F𝑡 -measurable, so E[− log 𝑞 𝑤 ( 𝐴𝑡 ) | F𝑡 ] = 𝐻 ( 𝑝 identity at 𝑞 = 𝑝b𝑡 and taking expectations gives E[− log 𝑞 𝑤 ( 𝐴𝑡 )] − E[− log 𝑝b𝑡 ( 𝐴𝑡 )] = E[𝐷 KL ( 𝑝b𝑡 ∥ 𝑞 𝑤 )] ≥ 0. The Dobrushin coefficient (Section 4). Two distinct rows of (3) differ only in the two coordinates where one places 𝜅 and the other (1− 𝜅)/(𝐾 −1), so their total variation is 𝜅 − (1− 𝜅)/(𝐾 −1) = (𝐾 𝜅 −1)/(𝐾 −1) =: 𝛿(𝑃). For beliefs 𝜇, 𝜈 with 𝜀 := 𝑑TV (𝜇, 𝜈) write 𝜇 − 𝜈 = 𝜀( 𝑝 − 𝑞) with 𝑝, 𝑞 the normalized positive
and Í negative parts; for any coupling 𝛾 of ( 𝑝, 𝑞), 𝑃⊤ 𝜇 − 𝑃⊤ 𝜈 = 𝜀 𝑧,𝑧 ′ 𝛾(𝑧, 𝑧 ′ ) 𝑃(· | 𝑧) − 𝑃(· | 𝑧 ′ ) , so 𝑑TV (𝑃⊤ 𝜇, 𝑃⊤ 𝜈) ≤ 𝛿(𝑃) 𝑑TV (𝜇, 𝜈); geometric forgetting under bounded action likelihood ratios follows as in [32].

I.3

Experimental detail

Model sizes (Table 1, Section 5). Parameter counts are 3.1k for the action bigram, 7.3k for the masked GRU, 7.4k for the hierarchical choice model and 8.7k with the previous action in the context, 10.6k for the flat softmax over the 56 actions, and 1.5k for the policy-class chain and 2.8k with the previous action. The hierarchical model therefore uses about 30% fewer parameters than the flat softmax on the same inputs and is within 2% of the GRU it is compared with. Training-set size (Section 5). Halving the training set to 60 episodes, from 120, the full-context choice model reaches 1.007 nats and 69.5% top-1 against 0.996 nats and 68.3% for the GRU, so the ordering of the two at 120 episodes reverses in likelihood and holds in accuracy. The hierarchical factorization is at or below the flat softmax up to 60 episodes (1.028 against 1.068 nats) and behind it from 90 episodes on, which is the expected pattern for a structural restriction that pays off when data are scarce. Unseen attacker (Section 5). On episodes generated by a red controller absent from training, every learned predictor is overconfident, with ECE above 0.35. The action bigram degrades least, to 3.43 nats per step. The GRU reaches 4.48 nats and the choice models with the filtered posterior reach 5.39 (flat) and 7.19 (hierarchical, full context), all worse than the 4.03 nats of uniform coding over the 56 actions and worse than simply repeating the last action (3.95). This is the failure mode the fallback state ⊥ of Section 3 is built for: in

Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 18

the joint filter, Corollary 2 caps the loss at uniform coding over the feasible sets plus the initial and persistence penalties, so no such sequence can be catastrophic. The two-stage estimator evaluated here does not carry ⊥, so this experiment establishes the failure mode and leaves the guarantee to be tested with the joint filter.

Distribution Statement ‘A’ (Approved for Public Release, Distribution Unlimited) 19

Related documents

• Learning to Attack and Defend: Adaptive Red Teaming of Language Models via GRPO#1247417
• Capacity for Simulation and Mitigation Drives Hedonic and Non-Hedonic Time Biases#737556
• A Bayesian Correlated Equilibrium for Early Insider-Threat Detection#925461
• A Bayesian Correlated Equilibrium for Early Insider-Threat Detection#921225
• Retaliation Rationalized: Gauthier's Solution to the Deterrence Dilemma#750203