Paper deep dive

Efficient Nash Equilibrium Computation for Cybersecurity Games

Michael Lanier, David Farmer, Yevgeniy Vorobeychik

Year: 2026Venue: arXiv preprintArea: cs.GTType: PreprintEmbeddings: 131

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 88%

Last extracted: 9/18/2026, 4:07:11 AM

Summary

This paper introduces Regret-Weighted Payoff Sampling (RWPS), a budgeted estimator for computing Nash equilibria in simulation-based cybersecurity games using Policy-Space Response Oracles (PSRO). RWPS addresses the bottleneck of expensive Monte-Carlo payoff estimation by simulating only cells sensitive to the equilibrium and filling the rest with a surrogate model trained on previous simulations. The authors prove instance-dependent error bounds that are tighter than traditional sup-norm bounds and demonstrate that RWPS achieves lower exploitability than existing methods (like minimum-regret-first search) on CyGym and a new simulator called ANSG (Agentic Network Security Game).

Entities (8)

RWPS · algorithm · 98%PSRO · algorithm · 95%CyGym · simulator · 92%ANSG · simulator · 90%Colonel Blotto · game · 85%CybORG · simulator · 85%MetaDOAR · algorithm · 80%Tuyls et al. · researcher · 80%

Relation Signals (7)

RWPS → improves → Nash Equilibrium Computation

confidence 95% · RWPS reaches lower exploitability than minimum-regret-first search, information-gain search, and progressive sampling at a matched budget

RWPS → appliedto → CyGym

confidence 90% · on the CyGym and ANSG cyber simulators it is lowest at the smallest budgets

RWPS → appliedto → ANSG

confidence 90% · on the CyGym and ANSG cyber simulators it is lowest at the smallest budgets

RWPS → uses → Surrogate Model

confidence 90% · fills the rest with a surrogate trained on every entry simulated earlier in the run

ANSG → extends → CyGym

confidence 85% · We introduce ANSG, which extends CyGym [16] from binary node access to networks of LLM agents

RWPS → outperforms → Minimum-Regret-First Search

confidence 85% · RWPS reaches lower exploitability than minimum-regret-first search

Tuyls et al. → proposed → Sup-norm bound

confidence 80% · We refine the sup-norm bound of Tuyls et al. [32]

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Computing Nash equilibria of simulation-based cybersecurity games with policy-space response oracles (PSRO) is bottlenecked by payoff estimation: every payoff-matrix entry costs Monte-Carlo rollouts of a slow simulator, while policies and restricted-game solves are cheap. We introduce Regret-Weighted Payoff Sampling (RWPS), a budgeted estimator that simulates only the cells an equilibrium is sensitive to and fills the rest with a surrogate trained on every entry simulated earlier in the run. The sup-norm error bound cannot evaluate such an estimator, because it is set by the cells left deliberately inaccurate. We prove an instance-dependent bound that weights error by the opponent's equilibrium mixture, a certificate computable from simulation data alone, and a coverage result showing that once the deviation-relevant set is simulated, surrogate error cannot affect either player's regret. On three 21x21 general-sum games, two synthetic and an asymmetric Colonel Blotto, the refined bounds are four to six times tighter on the estimator's own output, and the coverage result predicts in advance which games are cheap: 18% of the matrix for small-support games against 82% for Blotto. In growing-pool PSRO, RWPS reaches lower exploitability than minimum-regret-first search, information-gain search, and progressive sampling at a matched budget, and on the CyGym and ANSG cyber simulators it is lowest at the smallest budgets.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

127,827 characters extracted from source content.

Expand or collapse full text

Efficient Nash Equilibrium Computation for Cybersecurity Games Michael Lanier David Farmer Yevgeniy Vorobeychik Affiliation: Washington University in St. Louis Abstract Computing Nash equilibria of simulation-based cybersecurity games with policy-space response oracles (PSRO) is bottlenecked by payoff estimation: every payoff-matrix entry costs Monte-Carlo rollouts of a slow simulator, while policies and restricted-game solves are cheap. We introduce Regret-Weighted Payoff Sampling (RWPS), a budgeted estimator that simulates only the cells an equilibrium is sensitive to and fills the rest with a surrogate trained on every entry simulated earlier in the run. The sup-norm error bound cannot evaluate such an estimator, because it is set by the cells left deliberately inaccurate. We prove an instance-dependent bound that weights error by the opponent’s equilibrium mixture, a certificate computable from simulation data alone, and a coverage result showing that once the deviation-relevant set is simulated, surrogate error cannot affect either player’s regret. On three 21×2121× 21 general-sum games, two synthetic and an asymmetric Colonel Blotto, the refined bounds are four to six times tighter on the estimator’s own output, and the coverage result predicts in advance which games are cheap: 18%18\% of the matrix for small-support games against 82%82\% for Blotto. In growing-pool PSRO, RWPS reaches lower exploitability than minimum-regret-first search, information-gain search, and progressive sampling at a matched budget, and on the CyGym and ANSG cyber simulators it is lowest at the smallest budgets. 1 Introduction Autonomous cyber defence is increasingly studied through simulation-based security games: a defender and an attacker act over a network, neither observes full state, and the value of any strategy pair is defined only by executing a simulator. This infrastructure is now standard. The Cyber Operations Research Gym [30, 31] underpins the CAGE challenge series; Yawning Titan [1], CyberBattleSim [18], and FARLAND [20] provide alternatives at varying abstraction; and CyGym [16] casts cyber defence explicitly as a two-player general-sum stochastic game solved by policy-space response oracles (PSRO) [14], with MetaDOAR [15] scaling the best-response step. In this setting PSRO’s three inner operations have costs separated by orders of magnitude. Generating a candidate best response is a bounded reinforcement-learning run and can be restarted at will. Solving the restricted game, once a payoff matrix exists, is a small numerical problem that fictitious play [6] dispatches in milliseconds. Estimating a single payoff entry, by contrast, requires Monte-Carlo rollouts of the full simulator under both policies, and a rebuild touches Θ⁡(nDnA) (n_Dn_A) entries for pools of size nD,nAn_D,n_A, growing quadratically over a run. The community has already identified simulation throughput as the binding constraint: CybORG++ [9] is motivated substantially by execution speed, and its MiniCAGE re-implementation reports up to a thousandfold faster parallel execution precisely so that large-scale training and evaluation become feasible. Making the simulator faster is one response, but the usual route to speed is reduced fidelity: abstracting host, process, and packet-level detail, as in CybORG’s split between its simulator and its virtual-machine emulation [30] and the explicit fidelity–performance trade-offs of network environment design [20]. Lower fidelity is its own problem, since the abstracted detail is often exactly the realism the analysis was commissioned to capture. The complementary response, taken here, is to leave the simulator alone and call it less. The natural design is to spend a fixed rollout budget only on entries whose value can change the equilibrium, and to fill the rest with a learned surrogate; we call the resulting method Regret-Weighted Payoff Sampling (RWPS). It has two parts. A surrogate trained on every entry simulated earlier in the run fills the matrix, so each purchase keeps paying across PSRO iterations. A regret-weighted score decides which entries to buy, and matters most when the budget is smallest. Is the speedup worth its cost? Answering that requires knowing what error the budget induces in the computed equilibrium, and what guarantee survives it. The available answer comes from the analysis of estimated games [32]: an equilibrium of the estimated game is a 2τ2τ-equilibrium of the true game, where τ is the worst payoff error over all cells. Applied to a budgeted surrogate this bound is so loose as to be uninformative. The estimator deliberately concentrates its error on cells it judged unable to affect the equilibrium, and τ is set by exactly those cells. Under the prior analysis, then, the question of how much equilibrium quality the speedup costs is effectively open; answering it requires a bound that distinguishes errors the equilibrium can feel from errors it cannot. What our results ultimately show is that a payoff the equilibrium depends on but which an estimator can predict well is not worth simulating, and neither is an uncertain payoff no equilibrium strategy plays. Our contributions are as follows: 1. Instance-dependent bounds for estimated games. We refine the sup-norm bound of Tuyls et al. [32] so that only payoff errors weighted by the opponent’s equilibrium mixture enter a player’s regret, and a signed form in which only underestimated deviations and overestimated support can hurt (Lemma 1). We show that once the deviation-relevant set of B∗=nDsA+nAsD−sDsAB =n_Ds_A+n_As_D-s_Ds_A cells is simulated, a surrogate of arbitrary quality may fill the rest without affecting either player’s regret (Corollary 2), and give an optimistic certificate computable from simulation data alone (Corollary 1). On three 21×2121× 21 general-sum games the refined bounds are four to six times tighter than the sup-norm bound on the estimator’s own output. 2. Regret-Weighted Payoff Sampling. We give a budgeted payoff estimator for PSRO that fills unsimulated cells with a surrogate trained on every entry simulated earlier in the run, and buys cells by a score built from smoothed bootstrap equilibrium marginals, with forced exploration that Theorem 2 shows is necessary. In growing-pool PSRO it reaches lower exploitability than minimum-regret-first search, information-gain search [12], and progressive sampling at a matched budget. The fill carries 62%62\% of the margin and the score 38%38\%; with the fill held fixed, the score beats Sokota et al. [28] on Colonel Blotto (p=0.038p=0.038, 13/1613/16 seeds). 3. The Agentic Network Security Game. We introduce ANSG, which extends CyGym [16] from binary node access to networks of LLM agents compromised by goal subversion through indirect prompt injection, with general-sum payoffs and partial observability on both sides. In budget sweeps on CyGym and ANSG the estimator reaches the lowest exploitability at the smallest budgets; on ANSG, removing the acquisition score leaves exploitability four to five times higher at budgets 1–3. 2 Related Work Several simulators target cyber defence. CybORG [30, 31] drives the CAGE challenges; Yawning Titan [1], CyberBattleSim [18], and FARLAND [20] model networks at varying fidelity; CyGym [16] adds the game-theoretic layer this paper targets. All share the property that evaluating a strategy pair means running the simulator, and the cost of doing so is a recognised obstacle: CybORG++ [9] reports up to a thousandfold parallel speedup from a lightweight re-implementation, motivated by the infeasibility of large-scale evaluation on the original. We are orthogonal to simulator engineering: we reduce the number of calls the equilibrium computation needs, and the two approaches compose. The double-oracle method [17] and PSRO [14] grow strategy pools by best response to the current meta-game equilibrium; extensions target oracle quality and diversity [4], and structural studies of pools [8] inform what equilibrium supports look like in practice, a quantity our Corollary 2 makes decision-relevant. MetaDOAR [15] scales the best-response step for cyber networks. Little of this line targets the evaluation step, where cost concentrates in simulation-based games. Our theory refines a known result. Tuyls et al. [33], Tuyls et al. [32] prove that a Nash equilibrium of an estimated meta-game is a 2τ2τ-approximate equilibrium of the true game under sup-norm error τ. We take this as our point of departure. Lemma 1 replaces the sup-norm with an opponent-support-weighted error, which makes the bound informative for an estimator that deliberately leaves irrelevant cells inaccurate. Rowland et al. [25] allocate samples for evaluation under incomplete information, primarily for α-rank [22] response graphs, using bandit rules without a generalising surrogate. Query-efficient EGTA attacks the same cost by pruning rather than interpolating. Progressive-sampling algorithms allocate samples adaptively and drop profiles once they can be shown irrelevant to the learning goal [3, 2, 7, 19]. Their objective is a uniform ε -approximation over surviving profiles, and the saving comes from cells that never need sampling to that accuracy. Ours is the complementary regime: every cell is present in the matrix we solve, filled by a surrogate when unsimulated, and the certificate is evaluated at the equilibrium actually returned rather than uniformly over profiles. Neither guarantee subsumes the other. Wellman et al. [38] still describe MRFS-style heuristic search as the practical route where exhaustive evaluation is infeasible, so we treat it as a live baseline. We compare against both algorithms of Jordan et al. [12] and reach lower exploitability than both in a growing pool (Section 6.1). Neither carries information between iterations beyond its cache, whereas our surrogate trains on every cell bought at every previous iteration, so our advantage accumulates over a run. On a fixed pool, where no such history exists, MRFS is stronger at low budgets. Closest to us on the model-learning side, Wang et al. [36] pair double oracle with a learned game model and regularisation for sample efficiency, though for mean-field games and without an explicit payoff matrix, and Wang and Wellman [37] study the complementary axis of which strategies to add rather than which profiles to evaluate. Earlier work in this vein learns payoff or deviation-payoff functions over strategy spaces [34, 28] within EGTA [39, 35]. Sokota et al. [28] pair a learned deviation-payoff model with sampling around candidate equilibria, the closest instinct to ours; they build no payoff table and give no bound. Picheny et al. [23] apply Bayesian optimisation to Nash computation in continuous black-box games with a Gaussian-process surrogate and a fixed game. Adaptive payoff queries for α-rank [25, 24] target a different solution concept. Active learning [26, 27] and deep ensembles [13] supply our acquisition and uncertainty machinery. Appendix A.3.1 compares each in detail. 3 Method 3.1 Preliminaries and problem statement A simulation-based security game is a two-player general-sum game between a defender and an attacker. Each player holds a set of pure strategies; in our setting a pure strategy is a complete policy for the underlying stochastic game, for instance a trained neural controller for the defender’s network actions or the attacker’s intrusion actions. The game is simulation-based because its payoffs are not given analytically: the expected utility of a strategy pair (d,a)(d,a) is UD(d,a)=⁡[u⁡(d,a)],UA(d,a) symmetrically,U^D(d,a)=E [u(d,a) ], U^A(d,a) symmetrically, where the expectation is over the simulator’s stochasticity and each sample of it costs a full rollout. The game is general-sum, UD+UA≢cU^D+U^A ≡ c, reflecting asymmetric valuations of the same outcome; nothing below assumes zero-sum structure. Restricted to finite pools SD=d1,…,dnDS_D=\d_1,…,d_n_D\ and SA=a1,…,anAS_A=\a_1,…,a_n_A\, the game is a bimatrix game with payoff matrices Dij=UD(di,aj)D_ij=U^D(d_i,a_j) and Aji=UA(di,aj)A_ji=U^A(d_i,a_j), scaled without loss of generality to [0,1][0,1]. A solution is a mixed-strategy Nash equilibrium: distributions (p,q)∈ΔnD×ΔnA(p,q)∈ _n_D× _n_A from which neither player can profitably deviate, p⊤Dq≥ei⊤Dq∀i,q⊤Ap≥ej⊤Ap∀j.p Dq≥ e_i Dq\;\;∀ i, q Ap≥ e_j Ap\;\;∀ j. Quality is measured by exploitability, the largest deviation gain either player forgoes, ε⁡(p,q)=max⁡maxi⁡(Dq)i−p⊤Dq,maxj⁡(Ap)j−q⊤Ap, (p,q)= \ _i\,(Dq)_i-p Dq,\;\; _j\,(Ap)_j-q Ap \, (1) so ε=0 =0 is an exact equilibrium and, with scaled payoffs, ε reads as a fraction of the payoff range. A profile whose exploitability is at most ε is called an ε -Nash equilibrium. Policy-space response oracles solve the full game by alternating three operations: solve the current restricted game for (p,q)(p,q); train a best response to the opponent mixture with a reinforcement-learning oracle and add it to the pool; and extend the payoff matrices with the new strategy’s entries. In the simulation-based setting the first operation is nearly free, the second is a bounded training run, and the third costs NMCN_MC rollouts per cell over Θ⁡(nDnA) (n_Dn_A) cells. The problem this paper addresses is the third step under a budget: given pools (SD,SA)(S_D,S_A), a cache of previously simulated entries, and a budget of B≪nDnAB n_Dn_A new cell evaluations, produce estimates (D^,A^)( D, A) whose equilibrium is close, in the sense of Eq. (1), to an equilibrium of the true (D,A)(D,A). The design question is which B cells to simulate, and what to write into the rest. 3.2 The budgeted estimator Algorithm 1 gives the full procedure; its components are explained below in the order they appear, with lines 5–12 constituting the acquisition step and line 14 the forced exploration that Section 4 shows to be load-bearing. We call this Regret-Weighted Payoff Sampling (RWPS): the budget is allocated by each cell’s estimated influence on equilibrium regret, measured through the smoothed bootstrap marginals rather than through per-cell payoff uncertainty. The method has two separable parts, the history-trained fill and the acquisition score. Section 6.3 measures each; the fill carries most of the margin, and the score matters most at the smallest budgets. Algorithm 1 Regret-Weighted Payoff Sampling (RWPS) 1: pools SD,SAS_D,S_A; cache C of simulated entries; budget B; batch size c; exploration probability εx _x; smoothing ν; bootstrap size BbootB_boot; ensemble size M 2: φ⁡(s)← (s)← fingerprint of every s∈SD∪SAs∈ S_D∪ S_A ⊳ Eq. (2): forward passes only, no rollouts 3: B←B−|(i,j)∈|B← B-|\(i,j) \| if B is a coverage target ⊳ spend on the uncovered remainder, not the whole set 4: for r=1,…,⌈B/c⌉r=1,…, B/c do 5: fit ensemble fψ(m)m=1M\f_ψ^(m)\_m=1^M on (φ(di),φ(aj))↦[i,j]\( (d_i), (a_j)) [i,j]\ 6: (u^ij,σ^ij)←( u_ij, σ_ij)← ensemble mean, spread for all (i,j)∉(i,j) 7: for b=1,…,Bbootb=1,…,B_boot do ⊳ uncertainty of the solution, not the cells 8: subsample kD×kAk_D× k_A strategies; draw D~ij∼⁡(u^ij,σ^ij2) D_ij ( u_ij, σ_ij^2) on unsimulated cells, pin cached cells 9: (p(b),q(b),v(b))←(p^(b),q^(b),v^(b))← fictitious play on the realization 10: end for 11: p¯i←meanb⁡pi(b) p_i _b\,p^(b)_i; q¯j←meanb⁡qj(b) q_j _b\,q^(b)_j ⊳ marginals, not the averaged product 12: p~←(1−ν)p¯+ν/|SD| p←(1-ν)\, p+ν/|S_D|; q~←(1−ν)q¯+ν/|SA| q←(1-ν)\, q+ν/|S_A| ⊳ smooth toward uniform 13: α⁡(i,j)←p~iq~jσ^ijα(i,j)← p_i\, q_j\, σ_ij ⊳ zero on cached cells 14: for t=1,…,ct=1,…,c do ⊳ c cells per refit; the surrogate is refit between batches 15: with probability εx _x: simulate a cell drawn uniformly at random, unsimulated first, then revisits averaged by running mean ⊳ Thm. 2 16: otherwise: simulate the unsimulated cell of largest α 17: add to C 18: end for 19: end for 20: D^ij,A^ji←⁡[i,j] D_ij, A_ji [i,j] if cached, else ensemble mean 21: return (D^,A^)( D, A) Line 1 gives each policy a simulation-free representation. Fixing a probe bank Ξ=ξ1,…,ξP =\ _1,…, _P\ of states per role, collected once from a reference trajectory, a policy with actor μπ _π receives φ(π)=[meanpμπ(ξp)∥stdpμπ(ξp)]∈ℝd, (π)= [mean_p _π( _p)\,\|\,std_p _π( _p) ] ^d, (2) at the cost of P forward passes. Non-parametric strategies receive fixed tags. The fingerprint describes behaviour rather than identity. How much payoff information it carries is a property of the game, which Section 5 varies deliberately. Lines 3–4 fit an ensemble of M small networks mapping fingerprint pairs to payoff pairs, on bootstrap resamples of every entry ever simulated. Entries paid for at one PSRO iteration are training data at the next, which amortises simulation across a run. Queries return the mean u^ij u_ij and disagreement σ^ij σ_ij, with a rank-one row-and-column fallback until enough labels exist. Cached entries always override surrogate values. Lines 5–12 measure uncertainty at the level of the solution rather than the cell. Simulating wherever σ σ is large targets the wrong object: the equilibrium is a functional of the whole matrix, and a maximally uncertain cell can be irrelevant because no equilibrium strategy plays it. The cost asymmetry makes the right object affordable. Re-solving is nearly free, so we re-solve BbootB_boot bootstrap realizations of the game, each with a resampled pool and a matrix realization drawn from the surrogate’s predictive distribution. By the envelope theorem ∂v/∂Dij=piqj∂ v/∂ D_ij=p_iq_j at fixed support, so the equilibrium value is first-order sensitive to a cell in proportion to the product of the two players’ probabilities of playing it. Reading that identity off a single re-solve would score only the cells the current support estimate already plays. Two departures spread the score past it. First the product is formed from the bootstrap marginals, p¯iq¯j p_i q_j, rather than from the averaged product meanb⁡pi(b)qj(b)mean_bp^(b)_iq^(b)_j; the two agree only when the marginals are independent across replicates, and they are not, because a replicate that plays did_i tends to be one that plays a particular aja_j against it. The averaged product therefore concentrates on the diagonal block of replicate-consistent pairs, while the marginal product also scores cells that pair a strategy some replicate plays with an opponent strategy a different replicate plays. Those cross pairs are exactly the ones a support estimate errs about. Second each marginal is mixed toward uniform by ν, which places a floor under every cell in a played row or column and bounds the score’s concentration when the bootstrap is confident and wrong. Setting ν=0ν=0 and returning the product inside the average recovers value-sensitivity weighting, the rule used in earlier versions of this work, which Section 6.3 retains as the ν=0ν=0 ablation. Forced exploration is the only mechanism that can cover cells the surrogate cannot know it is wrong about. The sensitivity rule is the correct objective under a calibrated surrogate, but no surrogate is calibrated on cells it has not sampled: perfect targeting would require the very payoffs the budget is meant to discover. Theorem 2 makes this precise. Two policies can share a fingerprint while differing arbitrarily in payoff, so no acquisition rule routed through the embedding carries the asymptotic guarantee, and uniform draws are the only mechanism that does not consult it. The cache persists across PSRO iterations: cached values override the surrogate, every fit trains on all cells bought earlier, and a coverage-target budget pays only for the part of the deviation-relevant set not already held. Sokota et al.’s neighbourhood sampler moves mass toward the simplex edges, whereas ν-smoothing moves it toward uniform; Appendix A.3.2 discusses the contrast, the per-draw exploration form, and consistency, and Appendix A.6 gives the full procedure and hyperparameters. 4 Theory: an Instance-Dependent Bound We now ask what an equilibrium of the estimated game (D^,A^)( D, A) is worth in the true game (D,A)(D,A). The known answer is the sup-norm bound of Tuyls et al. [33], Tuyls et al. [32]. Writing ΔD=D^−D _D= D-D, ΔA=A^−A _A= A-A and τ=max⁡‖ΔD‖∞,‖ΔA‖∞τ= \\| _D\|_∞,\| _A\|_∞\, any exact equilibrium of the estimated game is a 2τ2τ-equilibrium of the true one. This is the wrong instrument for a budgeted estimator. Our estimator is designed to leave irrelevant cells inaccurate, so τ is set by precisely the cells that do not matter, and the resulting certificate is correspondingly loose (see Section 6). The refinements in this section let the equilibrium itself say which errors count. We successively strengthen the certificate from a two-sided worst case to a signed, optimism-compatible bound that can be computed from the data the estimator already holds. All proofs are deferred to Appendix A.1. 4.1 Support-weighted perturbation Lemma 1 (Support-weighted perturbation). Let (p^,q^)( p, q) be an εsolve _solve-approximate Nash equilibrium of (D^,A^)( D, A), meaning neither player gains more than εsolve _solve by deviating in the estimated game. Write ΔD=D^−D _D= D-D and define the opponent-support-weighted errors τD(q^)=maxi⁡(|ΔD|q^)i _D( q)= _i(| _D| q)_i and τA(p^)=maxj⁡(|ΔA|p^)j _A( p)= _j(| _A| p)_j, with |⋅||·| entrywise. Then the defender’s regret in the true game satisfies regD−εsolve _D- _solve ≤maxi⁡(−ΔDq^)i+p^⊤ΔDq^⏟(a) signed ≤\; _i (- _D q )_i+ p _D q_(a) signed (3) ≤τD(q^)+p^⊤|ΔD|q^⏟(b) two-term ≤\; _D( q)+ p | _D| q_(b) two-term ≤2τD(q^)⏟(c) support-weighted≤2τ⏟(d) sup-norm, ≤\; 2\, _D( q)_(c) support-weighted\;≤\; 2\,τ_(d) sup-norm, where τ=max⁡‖ΔD‖∞,‖ΔA‖∞τ= \\| _D\|_∞,\| _A\|_∞\, and symmetrically for the attacker. Consequently (p^,q^)( p, q) is an ε -Nash equilibrium of (D,A)(D,A) for ε equal to εsolve _solve plus the maximum over players of any of (a)–(d). Equality in the last step holds only when a worst-error cell lies in a played column, respectively row. The chain contains four bounds. Form (d) is the sup-norm bound of Tuyls et al. [33], Tuyls et al. [32], recovered as the loosest link. Form (c) is its support-weighted refinement, and form (b) keeps both terms instead of doubling the larger. Form (a) drops the absolute values, so that only underestimated deviations and overestimated support contribute. We use different parts of the chain at different points below, and the parts are not interchangeable. Theorem 1 and Corollary 2 are derived from (b), since the absolute values are what allow a row to be split over simulated and surrogate cells with each class bounded by a magnitude. Corollary 1 instead rests on the sign structure of (a), which is what makes an optimistic fill admissible. Note that the solver term εsolve _solve is computable without ground truth, since it is just the regret of (p^,q^)( p, q) in the matrices the estimator already holds. We report it alongside the bounds in Section 6. It matters most for form (a), which has no slack to absorb it. 4.2 Finite-budget guarantee Under the estimator, entries are of two kinds: simulated cells carry statistical error and surrogate cells carry representational error. The support-weighted bound splits accordingly. Assume rollouts return truth plus independent σ-sub-Gaussian noise, each simulated cell holds an average of at least m visits, and surrogate cells have absolute error at most β (whatever combination of regression error and embedding non-decodability produces it; we make no attempt to certify β a priori and measure it in Section 6). One subtlety requires care: which cells are simulated, and how often, is chosen by the acquisition rule from earlier samples, so the design is adaptive rather than fixed. A fixed-design union bound would be optimistic under adaptive selection. We therefore state the statistical term with a time-uniform concentration bound [11], valid simultaneously for all cells and all stopping times, at the cost of a log⁡log factor in the visit count; the guarantee below then holds regardless of how the acquisition rule selects cells. Theorem 1 (Finite-budget guarantee). With probability at least 1−δ1-δ, simultaneously over all cells and all sample-dependent stopping rules, any εsolve _solve-approximate equilibrium (p^,q^)( p, q) of (D^,A^)( D, A) satisfies ε≤εsolve+2maxπ∈p^,q^[ζ⁡(m,δ)+β⋅wsur(π)], \;≤\; _solve+2 _π∈\ p, q\ [ζ(m,δ)\;+\;β· w_sur(π) ], where ζ⁡(m,δ)=σ2(log⁡(4nDnA/δ)+log⁡log2⁡(2m))mζ(m,δ)=σ 2 ( (4n_Dn_A/δ)+ _2(2m) )m is a time-uniform confidence radius valid under adaptive sampling, and wsur(q^)=maxi∑j:(i,j)surrogateq^jw_sur( q)= _i _j\,:\,(i,j)\ surrogate q_j is the largest opponent-support mass any deviation row places on surrogate cells, and symmetrically for wsur(p^)w_sur( p). The multiplier wsurw_sur is the key quantity here. Representational error is discounted by how much equilibrium mass actually touches surrogate cells, rather than entering at full strength as it does in the sup-norm bound. Two of our later results turn on this. Computing wsurw_sur requires only a cache query against the returned mixture and consumes no rollouts, so its vanishing gives a stopping rule that we can check rather than assume (Proposition 1). Once it vanishes the bound retains only its statistical term, which we can invert to obtain the budget that a target exploitability requires (Corollary 3). 4.3 An optimistic certificate The unsigned forms of Eq. (3) charge errors in both directions, whereas the signed form (a) does not, and an estimator can exploit that sign structure. Only two events produce regret: a deviation row whose true value the estimate understates, and a support whose value the estimate overstates. Errors in the harmless directions are free. This is what makes optimism admissible. If we fill the unsimulated cells of a player’s own matrix at the maximum payoff, in the tradition of R-max [5], then no deviation is ever understated, the first term collapses to statistical noise on simulated cells, and only the support term remains. That term is controlled once the sDsAs_Ds_A support cells are simulated. Optimism enters our analysis in two places, with opposite consequences. Used as a post-hoc fill that only evaluates the bound it is nearly free, and this gives Corollary 1. Used as a fill inside the solve it is not, and we treat that case immediately after. Corollary 1 (Computable optimistic certificate). Let (p^,q^)( p, q) be an εsolve _solve-approximate equilibrium of any estimated matrices (D^,A^)( D, A), and let (Dopt,Aopt)(D^opt,A^opt) equal the measured values on simulated cells and the maximum payoff elsewhere. If rollout noise is σ-sub-Gaussian and each simulated cell averages m visits, then with probability at least 1−δ1-δ, ε≤max \;≤\; \\, maxi⁡(Doptq^)i−p^⊤D^q^, _i (D^opt q )_i- p D q,\;\; maxj(Aoptp^)j−q^⊤A^p^+ 2ζm,δ+εsolve, _j (A^opt p )_j- q A p \\;+\;2\, _m,δ+ _solve, where ζm,δ=ζ⁡(m,δ) _m,δ=ζ(m,δ) is the same time-uniform radius as in Theorem 1, valid under adaptive sampling, and every quantity on the right is computable from simulation data alone. The two uses have opposite cost. In Corollary 1 the optimistic matrices (Dopt,Aopt)(D^opt,A^opt) appear only in the deviation term, which is evaluated once on the equilibrium the estimator has already returned. The fill never influences which strategies are played, and it costs one row-maximum. Used inside the solve, the same fill pulls every best response toward unpaid cells and certifies only after nearly the whole matrix is bought (Appendix A.3.3). Corollary 2 (Deviation-relevant coverage). Let sD=|supp⁡(p^)|s_D=|supp( p)|, sA=|supp⁡(q^)|s_A=|supp( q)|. If every cell of 1:nD×supp⁡(q^)\1:n_D\×supp( q) and of supp⁡(p^)×1:nAsupp( p)×\1:n_A\ is simulated, then wsur(p^)=wsur(q^)=0w_sur( p)=w_sur( q)=0 and the bound of Theorem 1 reduces to its statistical and solver terms, independent of surrogate quality. The set has B∗=nDsA+nAsD−sDsAB \;=\;n_D\,s_A+n_A\,s_D-s_Ds_A cells, against nDnAn_Dn_A for a full rebuild. The principle that a profile’s regret depends only on its unilateral deviations is standard in EGTA [39, 38], and underlies MRFS [12]; setting sD=sA=1s_D=s_A=1 recovers its 2n−12n-1 confirmation set. What we add is the closed-form bimatrix count and the coupling to Theorem 1. In prior treatments the complement of the deviation set is unevaluated; here it is filled by a surrogate the solver reads, and the corollary shows that the fill cannot reach either player’s regret. This is what makes interpolation admissible in place of pruning. Because the supports it needs are estimated by bootstrap re-solves rather than rollouts, B∗B also serves as a screen: a small B∗B says the estimator is worth enabling, a B∗B close to nDnAn_Dn_A says a rebuild is the better option. Appendix A.3.3 prices a target certificate from B∗B (Corollary 3) and gives the extended discussion. Exploration is necessary for the asymptotic guarantee. A fingerprint is a finite summary, so two policies can share one while differing arbitrarily in payoff, and any deterministic acquisition rule reading only fingerprints and the cache can be led to never simulate the cell that matters (Theorem 2, Appendix A.3.3). The uniform draws of Algorithm 1 are the only mechanism that does not consult the embedding. 5 Experimental Setup Every claim is measured against ground truth, which requires games whose true payoff matrix and exact equilibrium are computable. On a cyber simulator neither exists for a growing pool: the true payoff of a pair is the very Monte-Carlo quantity the method avoids computing. The synthetic games below are instruments for measuring the estimator, not threat models. For the two cyber simulators we instead fix a small policy pool, simulate its full matrix once as ground truth, and sweep the budget against it (Section 6.2). 5.1 Games All are 21×2121× 21 (441441 cells), payoffs scaled to [0,1][0,1], rollout noise σ=0.10σ=0.10 of the range, NMC=4N_MC=4 episodes per cell evaluation, so a full rebuild costs 17641764 episodes. They differ in what the fingerprint encodes and in equilibrium support size, the two quantities the theory says matter. Latent-quality, informative embedding. Strategies carry latent qualities qs∼⁡(0,1)q_s (0,1) with bilinear general-sum payoffs Dij=qiDqjA+0.3qiDD_ij=q^D_iq^A_j+0.3q^D_i, Aij=−qiDqjA+0.3qjAA_ij=-q^D_iq^A_j+0.3q^A_j; the fingerprint [q,tanh⁡q,q2,sin⁡q][q, q,q^2, q] makes payoff smooth in φ . Equilibrium supports are (2,2)(2,2), so B∗=80B =80 cells, 18%18\%. Latent-quality, arbitrary embedding. Identical payoffs with fingerprints drawn independently of q; an ablation of the fingerprint, reported in Appendix A.7. Colonel Blotto, asymmetric values. S=5S=5 soldiers over F=3F=3 fields, fields worth different amounts to the two players drawn from [0.5,2][0.5,2], hence general-sum (std⁡(D+A)=0.21std(D+A)=0.21 across cells). The fingerprint is the normalised allocation; payoff is combinatorial in it. Supports are (12,12)(12,12), so B∗=360B =360 cells, 82%82\%: the theory predicts this game is expensive before any run. CyGym and ANSG. CyGym [16] is a network security game in which an attacker compromises nodes by gaining binary access and a defender responds over a partially observed network. The Agentic Network Security Game (ANSG) extends it to networks whose nodes are LLM agents. Compromise becomes goal subversion: an attacker injects instructions into content an agent reads, by indirect prompt injection or malicious tool triggering, so the agent pursues attacker goals while its legitimate task may still complete. Subverted agents can propagate payloads downstream. The defender audits, reprompts, resets, or isolates nodes on noisy signals; the attacker cannot observe resets and must probe to learn which nodes remain subverted. Valuations are independent per player, so the game is general-sum. ANSG keeps CyGym’s per-node state and PSRO machinery. Full details are in Appendix A.4. 5.2 Measurements Exploitability ε , Eq. (4), of the returned mixture in the true game; lower is better, 00 is exact, and scaling makes it a fraction of the payoff range: ε=max⁡maxi⁡(Dq)i−p⊤Dq,maxj⁡(Ap)j−q⊤Ap. = \ _i(Dq)_i-p Dq,\;\; _j(Ap)_j-q Ap \. (4) Bound tightness: realised ε against 2τ2τ, 2τsupp2 _supp, and the sharp form of Lemma 1, all computed from the method’s own output. Error decomposition and coverage studies are in Appendices A.10 and A.8. 5.3 Baselines and protocol Uniform sampling spends the same budget uniformly at random with a mean fill; full rebuild simulates everything, PSRO’s default and ours. We additionally compare against minimum-regret-first search and information-gain search [12] and the progressive-sampling family (Section 6.1). The latter is included to show that a uniform ε -approximation guarantee cannot be purchased at these budgets: its schedules require more samples per cell than the budget affords, so it returns the history-only estimate. The growing-pool comparison uses a 5%5\% per-build budget over twelve iterations with pools growing from three to fourteen per side, five seeds; the fixed-pool diagnostic builds of Section 6.4 sweep 5,10,20,40,70%\5,10,20,40,70\\% of the matrix over sixteen seeds, measuring ε against the full game by zero-lifting the restricted mixture, with best-response episodes counted separately. All runs are deterministic given recorded seeds; τ-statistics are maxima over 441441 cells and hence heavy-tailed, so we report medians with per-seed points shown. Seed counts are small and we present them as such. Code, data, and figures accompany the paper. 6 Results All aggregates are mean ± one standard deviation unless a caption states otherwise; per-seed values appear as faint points in the figures. The growing-pool comparison uses sixteen seeds and the coverage evaluation of Table 6 sixteen; the fixed-pool builds used as a diagnostic bed in Section 6.4 use four. Each caption states its own count. The implementation, the verification suite, and the raw per-seed CSVs are released with the paper, and every number below regenerates from run_all.py. 6.1 Growing-pool PSRO This is the setting the estimator is built for: pools grow, the cache persists, and every payoff entry costs a rollout. Table 1 reports twelve PSRO iterations at a 5%5\% per-build budget over sixteen seeds, with exploitability measured against the full 21×2121× 21 game by zero-lifting the restricted mixture. All budgeted methods consume an identical 256256 payoff episodes; the full rebuild is shown at its own 784784 as a reference rather than a competitor. Figure 1: Exploitability against the full game over twelve PSRO iterations at a 5%5\% per-build payoff budget. All methods draw the same initial pool and share a best-response oracle, but each responds to its own mixture, so the pools coincide at the first iteration and diverge thereafter. Means over sixteen seeds, interquartile bands. Table 1: Growing-pool PSRO, 5%5\% per-build budget, mean ± SD over sixteen seeds. ε0 _0 is the first iteration, where every method holds the same randomly drawn pool. Budget is cumulative payoff-rollout episodes over the run; every budgeted method is held to the same 256256. The full rebuild has no budget—it simulates every uncached cell, costing 784784 by iteration twelve—and is shown as a quality reference rather than a competitor. The three progressive-sampling members coincide because none prunes a single index at this budget. Game Payoff build ε0 _0 ε12 _12 budget Informative RWPS (ours) 0.2620.262 0.024±0.0170.024± 0.017 256256 MRFS 0.1800.180 0.091±0.0990.091 ±0.099 256256 IGS 0.1680.168 0.113±0.1110.113 ±0.111 256256 GS / PSP / PS-REG-M 0.2230.223 0.223±0.1740.223 ±0.174 256256 full rebuild 0.1110.111 0.036±0.0230.036 ±0.023 784784 Blotto RWPS (ours) 0.5250.525 0.082±0.0420.082± 0.042 256256 MRFS 0.5150.515 0.222±0.1140.222 ±0.114 256256 IGS 0.5540.554 0.276±0.1330.276 ±0.133 256256 GS / PSP / PS-REG-M 0.6270.627 0.627±0.1800.627 ±0.180 256256 full rebuild 0.3980.398 0.045±0.0150.045 ±0.015 784784 The separation accumulates rather than appearing at any single build. Figure 1 plots the same runs iteration by iteration. All methods begin together, separate over the first four iterations, and hold their ordering for the rest of the run. This is what reuse of the cache predicts. On Blotto the estimator tracks the full rebuild for several iterations before the budget binds, while uniform sampling and the progressive-sampling family flatten early and stay flat. By iteration twelve the estimator reaches 0.0240.024 against MRFS’s 0.0910.091 and uniform’s 0.1130.113, and on Blotto 0.0820.082 against 0.2220.222 and 0.2930.293. Both margins are significant under a paired test over the sixteen seeds: against MRFS, p=0.022p=0.022 on the latent games and p<0.001p<0.001 on Blotto; against uniform, p=0.003p=0.003 and p<0.001p<0.001. The estimator starts behind at iteration 00 (0.2620.262 against MRFS’s 0.1800.180), as expected with an empty cache and nothing to amortise; the gap then widens monotonically. Against the full rebuild the result divides by game. On the latent games the estimator reaches 0.0240.024 against the rebuild’s 0.0360.036 at a third of the episodes, winning 1313 of 1616 seeds, but the paired difference is not significant (p=0.057p=0.057). We claim only that 5%5\% of the cells cost no measurable quality, not that they buy more. On Blotto and on the arbitrary-embedding game the rebuild is ahead: 0.0450.045 against 0.0820.082 (p=0.004p=0.004), and 0.0360.036 against 0.0730.073 (p=0.036p=0.036). There the budget buys a real reduction in cost at a real cost in quality. The result is end-to-end: each method’s oracle responds to its own mixture, so pools diverge after iteration 00, and the number credits the estimator for the strategies it leads PSRO to find. IGS and the progressive-sampling family trail for a common reason: both need more samples per profile than the budget affords. At a 14×1414× 14 pool a 5%5\% budget is ten cell evaluations, against the 294294 samples per cell PSP’s schedule requires, so GS, PSP and PS-REG-M prune nothing and coincide exactly. Appendix A.3.4 gives the details, including IGS converging toward MRFS as its per-profile allowance grows. 6.2 Budget sweeps on CyGym and ANSG On both simulators RWPS reaches the lowest exploitability at the smallest budgets, and the other arms close the gap as the budget grows. On CyGym (Figure 2) both RWPS variants sit near the floor from budget 1, while uniform sampling and MRFS descend to it only around budget 8. IGS stays well above the floor across the sweep, and GS/PSP/PS-REG-M buys nothing at any budget shown. On ANSG (Figure 3) RWPS (adaptive) is lowest through budget 6; by budgets 11–13 the arms overlap within their bands. The two simulators separate the acquisition score from the fill differently. On CyGym the uniform-acquisition ablation tracks the adaptive rule closely, so the fill carries most of the margin. On ANSG the ablation is four to five times above the floor at budgets 1–3 and reaches it only at budget 4, so the score is what makes the first few purchases count. On all three simulators the ablation’s largest gap to the adaptive rule is at budget 1. Appendix A.5 reports the same sweep on Cyberwheel, where the pool is flat and every buying arm performs essentially the same. Figure 2: CyGym budget sweep. 6×66× 6 pool with a 5×55× 5 history pre-cached for every arm, leaving 1111 cells to buy; 1616 seeds. Exploitability is computed against a reference matrix estimated at 1616 rollouts per cell. Bands are ±1± 1 standard error. GS/PSP/PS-REG-M is constant: its sampling schedule requires more samples per cell than the budget affords, so it returns the history-only estimate. Figure 3: ANSG budget sweep. 7×77× 7 pool with a 6×66× 6 history pre-cached for every arm, leaving 1313 cells to buy; 1616 seeds; exploitability computed exactly against the ground-truth matrix, so no measurement is clamped. Bands are ±1± 1 standard error. Two arms are omitted for legibility. GS/PSP/PS-REG-M is constant at 1.97×1051.97× 10^5 payoff units: its sampling schedule requires far more samples per cell than the budget affords, so it buys nothing and returns the history-only estimate. RWPS (uniform), the ablation with the acquisition score removed, averages 4.28×1034.28× 10^3—it is 2.11×1042.11× 10^4, 1.88×1041.88× 10^4 and 1.57×1041.57× 10^4 at budgets 1–3, and reaches the floor only at budget 4, where RWPS (adaptive) is already at it from budget 1. 6.3 Acquisition Ablation Table 1 varies the payoff build as a whole, so its margin mixes two mechanisms: choosing which cells to simulate, and predicting the ones we skip. This section separates them. We fix the surrogate, the budget, the batch schedule, and the exploration rate, and vary only the acquisition score. Any difference between rows is therefore due to acquisition alone. All rules run on the same sixteen seeds, paired so that each begins from the same pool and the same oracle noise stream. Uniform here samples cells at random but keeps the surrogate fill; Table 1’s uniform also replaces the fill with a flat value, so comparing the two isolates the fill. The fill accounts for 62%62\% of the total margin and the acquisition score for 38%38\%. On the latent games the flat-fill baseline reaches 0.1130.113, the surrogate-fill baseline 0.0580.058, and the full method 0.0240.024. On Blotto the same three are 0.2930.293, 0.1620.162, and 0.0820.082. The split holds on both games to the nearest percentage point, although the two differ by a factor of three in difficulty and in whether the surrogate can fit the payoff surface at all. We did not tune for this and have no explanation for why it is so stable. Neither component is decorative. Table 2: Acquisition comparison. Identical surrogate, budget, batch schedule and forced-exploration rate; the rules differ only in the score used to rank uncached cells. Mean ± SD over sixteen paired seeds, ε12 _12. Uncertainty sampling scores by surrogate disagreement alone, the standard active-learning criterion [26, 29]. Uniform selection removes the score entirely while keeping the surrogate fill, so it is the control for the score rather than for the method. Appendix A.9.3 reports three further variants of our own rule. Acquisition score Informative Blotto ν-smoothed product (ours) 0.024±0.0170.024± 0.017 0.082±0.0420.082± 0.042 Sokota et al. [28] 0.032±0.0170.032 ±0.017 0.120±0.0450.120 ±0.045 uncertainty sampling (σ σ only) 0.040±0.0260.040 ±0.026 0.116±0.0500.116 ±0.050 uniform selection 0.058±0.0640.058 ±0.064 0.162±0.0770.162 ±0.077 The smoothed rule is first on both games. On Blotto it beats Sokota et al. [28] by 0.0380.038, under both a paired t-test (p=0.038p=0.038) and a signed-rank test (p=0.016p=0.016), winning 1313 of 1616 seeds. On the latent games it leads by 0.0070.007, which is not separable (p=0.224p=0.224). We report that as a tie. Uncertainty sampling separates the two ingredients of the score. Scoring by surrogate disagreement alone beats uniform selection on both games, so σ σ carries real information about where the fill is wrong, but it loses to the full rule (p=0.021p=0.021 on Blotto, p=0.062p=0.062 on the latent games). Disagreement is therefore informative and not sufficient: a cell can be maximally uncertain and irrelevant because no equilibrium strategy plays it, which is the argument of Section 3.2 measured rather than asserted. Appendix A.9.3 isolates the smoothing against the unsmoothed rule. Two cautions belong with this table. We chose ν=0.25ν=0.25 on these games, an advantage the ported baseline does not have. The Blotto margin is larger than the spread of the ν sweep in Appendix A.9, but the latent-game ordering is within it. Uniform selection also has by far the widest spread of any rule, 0.0640.064 against 0.0170.017 for the smoothed rule on the latent games, so paired t-tests against it are underpowered relative to signed-rank tests. We report both rather than the more favourable one. 6.4 Why the estimator can afford to be wrong Figure 4: Realised exploitability and its bounds on the estimator’s own output, over all 240240 fixed-pool budget-sweep runs on the three 21×2121× 21 games (the informative and arbitrary-embedding latent-quality games and Colonel Blotto; budgets 5,10,20,40,70%\5,10,20,40,70\\% of the matrix; 1616 seeds each), sorted by ε . Shaded regions are each bound’s margin over ε , faint at full resolution and solid under a 2121-run rolling mean; neither closes, and no bound is violated on any individual run. Error off the equilibrium support is invisible to regret, and this holds on the estimator’s own output. Over all 240240 budget-sweep runs every bound holds on every run (Figure 4). Our bound, the signed form (a) of Eq. (3) plus the measured solver term, averages 0.250.25 of the sup-norm bound, with a median overestimation factor of 2.32.3 against 11.411.4; forms (c) and (b) average 0.470.47 and 0.330.33, as the chain predicts. The estimator concentrates error on unplayed cells, the sup-norm is set by exactly those cells, and the support weighting removes them. The solver term is needed: without it the signed bound fails on three Blotto runs, each by less than that run’s solver regret (Appendix A.3.4). These are diagnostics, not certificates. Each form of Eq. (3) contains D^−D D-D, so all 240240 builds use a fixed-pool bed where the true matrix is available. Appendix A.10 gives per-game factors and the deployable certificate. 7 Conclusion Payoff estimation, not equilibrium solving, is what limits PSRO on cyber simulators, and this paper shows it no longer has to be paid in full. On a 5%5\% per-build simulation budget, RWPS reaches lower exploitability than every budgeted alternative we tested. It does so with a guarantee. Our bounds are four to six times tighter than the sup-norm bound they replace; once we simulate every strategy against the opponent’s equilibrium strategies, the surrogate’s guesses for the remaining cells cannot change how exploitable the equilibrium is; and the bound can be computed from the simulations we ran, without knowing the true payoff matrix. On CyGym and on our LLM-agent game ANSG, RWPS is the lowest-exploitability method at the smallest budgets. Budgeted, certified equilibrium computation is now practical for simulation-based security games. References [1] A. Andrew, S. Spillard, J. Collyer, and N. Dhir (2022) Developing optimal causal cyber-defence agents via cyber security simulation. arXiv preprint arXiv:2207.12355. Cited by: §1, §2. [2] E. Areyan Viqueira, C. Cousins, and A. Greenwald (2020) Improved algorithms for learning equilibria in simulation-based games. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), p. 79–87. Cited by: §2. [3] E. Areyan Viqueira, A. Greenwald, C. Cousins, and E. Upfal (2019) Learning simulation-based games from data. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), p. 1778–1780. Cited by: §2. [4] D. Balduzzi, M. Garnelo, Y. Bachrach, W. M. Czarnecki, J. Pérolat, M. Jaderberg, and T. Graepel (2019) Open-ended learning in symmetric zero-sum games. In International Conference on Machine Learning (ICML), Cited by: §2. [5] R. I. Brafman and M. Tennenholtz (2002) R-max: a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research 3, p. 213–231. Cited by: §4.3. [6] G. W. Brown (1951) Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation. Cited by: §1. [7] C. Cousins, B. Mishra, E. Areyan Viqueira, and A. Greenwald (2022) Computational and data requirements for learning generic properties of simulation-based games. arXiv preprint arXiv:2208.06400. Cited by: §2. [8] W. M. Czarnecki, G. Gidel, B. Tracey, K. Tuyls, S. Omidshafiei, D. Balduzzi, and M. Jaderberg (2020) Real world games look like spinning tops. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §2. [9] H. Emerson, L. Zhou, D. Bowman, et al. (2024) CybORG++: an enhanced gym for the development of autonomous cyber agents. arXiv preprint arXiv:2410.16324. Cited by: §1, §2. [10] P. Hennig and C. J. Schuler (2012) Entropy search for information-efficient global optimization. In Journal of Machine Learning Research, Vol. 13, p. 1809–1837. Cited by: §A.3.2. [11] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon (2021) Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics 49 (2), p. 1055–1080. Cited by: §4.2. [12] P. R. Jordan, Y. Vorobeychik, and M. P. Wellman (2008) Searching for approximate equilibria in empirical games. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 1063–1070. Cited by: §A.3.1, §A.3.3, §A.3.4, item 2, §2, §4.3, §5.3. [13] B. Lakshminarayanan, A. Pritzel, and C. Blundell (2017) Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §A.3.1, §2. [14] M. Lanctot, V. Zambaldi, A. Gruslys, A. Lazaridou, K. Tuyls, J. Pérolat, D. Silver, and T. Graepel (2017) A unified game-theoretic approach to multiagent reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §1, §2. [15] M. Lanier and Y. Vorobeychik (2026) A scalable approach to solving simulation-based network security games. In Proceedings of FLAIRS, Cited by: §1, §2. [16] M. Lanier and Y. Vorobeychik (2026) CyGym: a simulation-based game-theoretic analysis framework for cybersecurity. In Proceedings of GameSec, LNCS 16223. Cited by: §A.4, item 3, §1, §2, §5.1. [17] H. B. McMahan, G. J. Gordon, and A. Blum (2003) Planning in the presence of cost functions controlled by an adversary. In International Conference on Machine Learning (ICML), Cited by: §2. [18] Microsoft Defender Research Team (2021) CyberBattleSim. Note: https://github.com/microsoft/cyberbattlesim Cited by: §1, §2. [19] B. Mishra, C. Cousins, and A. Greenwald (2023) Regret pruning for learning equilibria in simulation-based games. In Proceedings of the AAAI Conference on Artificial Intelligence, Note: arXiv:2211.16670 Cited by: §2. [20] A. Molina-Markham, C. Miniter, B. Powell, and A. Ridley (2021) Network environment design for autonomous cyberdefense. arXiv preprint arXiv:2103.07583. Cited by: §1, §1, §2. [21] S. Oesch, A. Chaulagain, B. Weber, M. Dixson, A. Sadovnik, B. Roberson, C. Watson, and P. Austria (2024) Towards a high fidelity training environment for autonomous cyber defense agents. In Proceedings of the 17th Cyber Security Experimentation and Test Workshop, CSET ’24, p. 91–99. External Links: Document Cited by: §A.5. [22] S. Omidshafiei, C. Papadimitriou, G. Piliouras, K. Tuyls, M. Rowland, J. Lespiau, W. M. Czarnecki, M. Lanctot, J. Pérolat, and R. Munos (2019) α-Rank: multi-agent evaluation by evolution. Scientific Reports 9. Cited by: §2. [23] V. Picheny, M. Binois, and A. Habbal (2016) A Bayesian optimization approach to find Nash equilibria. arXiv preprint arXiv:1611.02440. Cited by: §A.3.1, §A.9.3, §2. [24] T. Rashid, C. Zhang, and K. Ciosek (2021) Estimating α-rank by maximizing information gain. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, p. 5673–5681. External Links: Document Cited by: §A.3.1, §2. [25] M. Rowland, S. Omidshafiei, K. Tuyls, J. Pérolat, M. Valko, G. Piliouras, and R. Munos (2019) Multiagent evaluation under incomplete information. In Advances in Neural Information Processing Systems (NeurIPS), Cited by: §A.3.1, §2, §2. [26] B. Settles (2009) Active learning literature survey. University of Wisconsin-Madison Department of Computer Sciences Technical Report 1648. Cited by: §A.3.1, §2, Table 2. [27] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. de Freitas (2016) Taking the human out of the loop: a review of bayesian optimization. Proceedings of the IEEE 104 (1), p. 148–175. Cited by: §A.3.1, §2. [28] S. Sokota, C. Ho, and B. Wiedenbeck (2019) Learning deviation payoffs in simulation-based games. In Proceedings of the AAAI Conference on Artificial Intelligence, Cited by: §A.3.1, §A.3.2, §A.3.4, item 2, §2, §2, §6.3, Table 2. [29] N. Srinivas, A. Krause, S. M. Kakade, and M. W. Seeger (2012) Information-theoretic regret bounds for Gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory 58 (5), p. 3250–3265. Cited by: §A.3.2, Table 2. [30] M. Standen, M. Lucas, D. Bowman, T. J. Richer, J. Kim, and D. Marriott (2021) CybORG: a gym for the development of autonomous cyber agents. In IJCAI-21 1st International Workshop on Adaptive Cyber Defense, Cited by: §1, §1, §2. [31] TTCP CAGE Working Group (2022) Cyber operations research gym. Note: https://github.com/cage-challenge/CybORG Cited by: §1, §2. [32] K. Tuyls, J. Pérolat, M. Lanctot, E. Hughes, R. Everett, J. Z. Leibo, C. Szepesvári, and T. Graepel (2020) Bounds and dynamics for empirical game theoretic analysis. Autonomous Agents and Multi-Agent Systems 34 (7). Cited by: item 1, §1, §2, §4.1, §4. [33] K. Tuyls, J. Pérolat, M. Lanctot, J. Z. Leibo, and T. Graepel (2018) A generalised method for empirical game theoretic analysis. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), Cited by: §2, §4.1, §4. [34] Y. Vorobeychik, M. P. Wellman, and S. Singh (2007) Learning payoff functions in infinite games. Machine Learning 67 (1–2), p. 145–168. Cited by: §2. [35] Y. Vorobeychik and M. P. Wellman (2008) Stochastic search methods for Nash equilibrium approximation in simulation-based games. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 1055–1062. Cited by: §2. [36] Y. Wang, Q. Ma, and M. P. Wellman (2023) Empirical game-theoretic analysis for mean field games. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 1025–1033. Cited by: §2. [37] Y. Wang and M. P. Wellman (2022) Evaluating strategy exploration in empirical game-theoretic analysis. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 1346–1354. Cited by: §2. [38] M. P. Wellman, K. Tuyls, and A. Greenwald (2025) Empirical game-theoretic analysis: a survey. Journal of Artificial Intelligence Research. Note: arXiv:2403.04018 Cited by: §A.3.3, §2, §4.3. [39] M. P. Wellman (2006) Methods for empirical game-theoretic analysis. Proceedings of the AAAI Conference on Artificial Intelligence. Cited by: §A.3.3, §A.8.2, §2, §4.3. [40] B. Wiedenbeck, B. Cassell, and M. P. Wellman (2014) Bootstrap statistics for empirical games. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 597–604. Cited by: §A.3.3. [41] B. Wiedenbeck and M. P. Wellman (2012) Scaling simulation-based game analysis through deviation-preserving reduction. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), p. 931–938. Cited by: §A.3.3, §A.8.2. Appendix A Appendix A.1 Proofs This appendix collects the proofs of the results in Section 4, in order of appearance. Statements are not repeated; each proof is headed by a reference to the result it establishes. Proof of Lemma 1. For any pure deviation i of the defender, ei⊤Dq^=ei⊤D^q^−ei⊤ΔDq^≤p^⊤D^q^+(|ΔD|q^)i=p^⊤Dq^+p^⊤ΔDq^+(|ΔD|q^)i,e_i D q=e_i D q-e_i _D q≤ p D q+ (| _D| q )_i= p D q+ p _D q+ (| _D| q )_i, using optimality of p p in the estimated game and the triangle inequality. Taking the maximum over i and bounding p^⊤ΔDq^≤p^⊤|ΔD|q^≤τD(q^) p _D q≤ p | _D| q≤ _D( q) gives the defender’s bound; the attacker’s is symmetric and no zero-sum structure is used. For the comparison, each row of |ΔD|q^| _D| q is a q q-weighted average of entries bounded by τ, so τD(q^)≤τ _D( q)≤τ; columns of zero mass contribute nothing. For (i), repeat the chain without the triangle inequality: ei⊤Dq^=ei⊤D^q^−ei⊤ΔDq^≤p^⊤D^q^−ei⊤ΔDq^=p^⊤Dq^+p^⊤ΔDq^−ei⊤ΔDq^e_i D q=e_i D q-e_i _D q≤ p D q-e_i _D q= p D q+ p _D q-e_i _D q; take the maximum over i. The comparison follows since dropping absolute values can only decrease each term. ∎ Proof of Theorem 1. Split (|ΔD|q^)i (| _D| q )_i over simulated and surrogate cells of row i. The simulated part is at most the concentration radius times ∑jq^j≤1 _j q_j≤ 1, by mean concentration of m-visit averages and a union bound over all 2nDnA2n_Dn_A cells; the surrogate part is at most β times the q q-mass row i places on surrogate cells. Take the maximum over rows, apply Lemma 1, and repeat for the attacker. ∎ Proof of Corollary 1. With probability 1−δ1-δ all simulated entries lie within ζm,δ _m,δ of truth, so D≤Dopt+ζm,δD≤ D^opt+ _m,δ entrywise: on simulated cells by concentration and on unsimulated cells because payoffs are bounded by the fill. Hence maxi⁡(Dq^)i≤maxi⁡(Doptq^)i+ζm,δ _i(D q)_i≤ _i(D^opt q)_i+ _m,δ, while p^⊤Dq^≥p^⊤D^q^−ζm,δ p D q≥ p D q- _m,δ whenever the support cells are simulated, the deficit otherwise being visible in the computable first term. The attacker is symmetric. ∎ Proof of Proposition 1. Coverage is monotone: a cell once simulated is never returned to the surrogate, so the set of cached cells is non-decreasing in t. Let ℛtR_t denote the set consisting of every row simulated in all nAn_A columns together with every column simulated in all nDn_D rows, after round t. Round t simulates 1:nD×supp⁡(q^t)\1:n_D\×supp( q_t), which completes every column of supp⁡(q^t)supp( q_t), and supp⁡(p^t)×1:nAsupp( p_t)×\1:n_A\, which completes every row of supp⁡(p^t)supp( p_t); hence supp⁡(p^t)∪supp⁡(q^t)⊆ℛtsupp( p_t) ( q_t) _t. Suppose the procedure does not halt after round t+1t+1, so wsur(q^t+1)>0w_sur( q_t+1)>0 or wsur(p^t+1)>0w_sur( p_t+1)>0. In the first case there are i and j with q^t+1,j>0 q_t+1,j>0 and (i,j)(i,j) unsimulated, so column j is incomplete and therefore j∉supp⁡(q^t)j ( q_t); round t+1t+1 simulates 1:nD×supp⁡(q^t+1)∋(⋅,j)\1:n_D\×supp( q_t+1) (·,j) and so adds j to ℛR. The second case is symmetric in rows. Every non-halting round therefore enlarges ℛR by at least one element, and |ℛ|≤nD+nA|R|≤ n_D+n_A, which gives (i). For (i), halting means wsur(p^)=wsur(q^)=0w_sur( p)=w_sur( q)=0 at the mixture returned by the final solve, which is exactly the hypothesis of Corollary 2 evaluated at that mixture; the conclusion of Theorem 1 then loses its β term. For (i), monotonicity bounds the total simulated set by the whole matrix. ∎ Proof of the per-iteration accounting above. Write p^,q p, q for the unchanged supports and dnew,anewd_new,a_new for the added strategies. The set 1:nD×supp⁡(q^)\1:n_D\×supp( q) acquires one new row, contributing the sAs_A cells (dnew,j)(d_new,j) for j∈supp⁡(q^)j ( q); the set supp⁡(p^)×1:nAsupp( p)×\1:n_A\ acquires one new column, contributing the sDs_D cells (i,anew)(i,a_new) for i∈supp⁡(p^)i ( p). The cell (dnew,anew)(d_new,a_new) lies in neither set, since by hypothesis neither new strategy is in a support. All other cells of the coverage set were simulated at the previous iteration and are cached. A cached full rebuild instead simulates every newly exposed cell, of which there are (k+1)2−k2=2k+1(k+1)^2-k^2=2k+1. ∎ Proof of Corollary 3. Under coverage wsur(p^)=wsur(q^)=0w_sur( p)=w_sur( q)=0, so the bound of Corollary 1 reduces to εsolve+2ζ(m,δ) _solve+2ζ(m,δ) and is at most εtgt _tgt exactly when 2ζ(m,δ)≤εtgt−εsolve2ζ(m,δ)≤ _tgt- _solve. Since ζ⁡(m,δ)ζ(m,δ) is strictly decreasing in m, the set of admissible m is an up-set and m∗m is its minimum. The cost follows because coverage simulates B∗B cells and each must carry m∗m visits. For the rate, drop the log⁡log2⁡(2m) _2(2m) term, which is o⁡(log⁡m)o( m): solving σ2log⁡(4nDnA/δ)/m=(εtgt−εsolve)/2σ 2 (4n_Dn_A/δ)/m=( _tgt- _solve)/2 gives m=8σ2log⁡(4nDnA/δ)/(εtgt−εsolve)2m=8σ^2 (4n_Dn_A/δ)/( _tgt- _solve)^2, and reinstating the log⁡log term inflates this by a factor 1+o⁡(1)1+o(1). ∎ Proof of Theorem 3. For (i), coverage is monotone: a simulated cell is never returned to the surrogate. Let ℛR be the set of rows simulated in every column together with the columns simulated in every row. By the argument of Proposition 1, whenever the iteration fails to halt it enlarges ℛR by at least one element. Since |ℛ|≤nD+nA|R|≤ n_D+n_A and ℛR never shrinks, at most nD+nAn_D+n_A such extensions can occur across the whole sequence, however many times the mixture changes; after the last, every subsequent solve halts immediately and wsur=0w_sur=0 holds permanently. For (i), on the stated event Theorem 1 gives ε≤εsolve+2maxπ[ζ⁡(m,δ)+βwsur(π)] ≤ _solve+2 _π[ζ(m,δ)+β w_sur(π)], and wsur=0w_sur=0 removes the second term. The radius ζ⁡(m,δ)=σ2(log⁡(4nDnA/δ)+log⁡log2⁡(2m))/mζ(m,δ)=σ 2( (4n_Dn_A/δ)+ _2(2m))/m is decreasing in m with ζ→0ζ→ 0: the numerator grows doubly logarithmically while the denominator grows linearly, so (log⁡(4nDnA/δ)+log⁡log2⁡(2m))/m→0( (4n_Dn_A/δ)+ _2(2m))/m→ 0 by L’Hôpital’s rule on the ∞/∞/∞ form. The log⁡log term therefore costs only a bounded factor at any practical m, and ζ retains the m−1/2m^-1/2 decay of a fixed-design radius; this is why the budget of Corollary 3 inherits the fixed-design rate up to that factor. Crucially the bound is time-uniform: it holds simultaneously for all m and all sample-dependent stopping rules on a single event of probability 1−δ1-δ, so the limit is taken on that event without a further union bound. For (i), εsolve _solve is the exploitability of (p^,q^)( p, q) in the estimated game and vanishes when the restricted game is solved exactly, giving ε→0 → 0. Since ε is exploitability in the true restricted game, the limit profile is an exact equilibrium of it. The cells outside the coverage set enter neither maxi⁡(Dq)i _i(Dq)_i nor maxj⁡(Ap)j _j(Ap)_j by Corollary 2, so their values are unconstrained. ∎ Proof of Lemma 2. By Eq. (2), φ⁡(π) (π) is a function of μπ(ξp)p≤P\ _π( _p)\_p≤ P alone, so any two policies agreeing on Ξ receive identical fingerprints whatever they do elsewhere. Payoffs, by contrast, depend on behaviour at all reachable states. Choosing π′π to agree with π on Ξ and to realise the desired behaviour off it, which the hypothesis permits, gives the claim. ∎ Proof of Theorem 2. Suppose for contradiction that some such A, at budget B, simulates a trap cell on every twin–trap instance. Consider the all-duplicate instance I0I_0, in which a designated attacker strategy a⋆a_ is a genuine copy of atwina_twin: same fingerprint, same payoffs, likewise weak. Run A on I0I_0 and let BS_B be the set of cells it simulates, so |B|≤B<nDnA|S_B|≤ B<n_Dn_A. Since BS_B omits at least one cell, and by enlarging the pool if necessary, choose an attacker column j⋆j_ that BS_B does not meet. By Lemma 2 there is a policy atrapa_trap with φ⁡(atrap)=φ⁡(atwin) (a_trap)= (a_twin) whose payoffs make it a dominant deviation. Let I1I_1 be the instance obtained from I0I_0 by installing atrapa_trap in column j⋆j_ , leaving everything else untouched. Then I1I_1 is a twin–trap instance, and I0I_0 and I1I_1 differ only in the payoffs of cells in column j⋆j_ . We claim A executes the same run on I0I_0 and I1I_1. Argue by induction on rounds. The fingerprints agree, since φ⁡(atrap)=φ⁡(atwin)=φ⁡(a⋆) (a_trap)= (a_twin)= (a_ ) and φ is a function of the actor alone, not of payoffs. Suppose the runs agree through round r, so the caches rC_r agree as multisets of simulated cells. The entries recorded there agree as values as well: every cell in r⊆BC_r _B lies outside column j⋆j_ , where I0I_0 and I1I_1 are identical by construction. Hence A receives identical inputs at round r+1r+1 and, being deterministic, selects identical cells. The induction closes. Therefore A simulates exactly BS_B on I1I_1, and BS_B does not meet column j⋆j_ , so A simulates no trap cell on I1I_1. But I1I_1 is a twin–trap instance, on which the hypothesis asserts that A does simulate a trap cell. This is the contradiction, and it establishes the first claim. For the exploitability claim, on I1I_1 the surrogate assigns column j⋆j_ its prediction for atwina_twin, since the two share a fingerprint and no label from j⋆j_ ever enters the cache. That prediction is uniformly weak, so the returned q q places no mass on the trap. In the true game atrapa_trap is a dominant deviation, so the attacker’s regret maxj⁡(Ap^)j−q^⊤Ap _j(A p)_j- q A p is at least η:⁣=(Ap^)j⋆−q^⊤Ap^η :=(A p)_j_ - q A p, the gap between the trap’s true payoff against p p and the value the estimated game reports. This is fixed by the instance and does not shrink with B. Uniform draws escape the argument because the construction needs a deterministic BS_B outside of which to place the trap. A rule visiting each unsimulated cell with probability bounded below admits no such placement, and reaches column j⋆j_ almost surely. ∎ A.2 Fingerprint collisions Lemma 2 (Fingerprint collisions exist). Fix a probe bank Ξ=ξ1,…,ξP =\ _1,…, _P\ and let Π be a policy class in which, for any π∈Ππ∈ and any prescribed behaviour off Ξ , some π′∈Ππ ∈ agrees with π on Ξ and realises that behaviour elsewhere. Then for every π∈Ππ∈ there is π′∈Ππ ∈ with φ⁡(π′)=φ⁡(π) (π )= (π) whose payoffs against a fixed opponent are arbitrary. The hypothesis on Π is mild. It asks only that agreement on P probe states does not determine behaviour everywhere, which fails only if Ξ happens to be a sufficient statistic for the policy class. For neural controllers on a state space larger than the probe bank, it holds. A.3 Extended discussion This appendix holds material condensed out of the main text. A.3.1 Related work We compare against three members and reach lower exploitability than all of them at a matched budget (Section 6.1). None prunes a single utility index at the budgets we study. PSP’s schedule begins at 294294 samples per cell against the ten cell evaluations a 5%5\% budget affords. A uniform PAC guarantee costs the sample complexity it requires, and in our regime it is not purchasable. Sokota et al. [28] deserve particular mention, since they pair a learned model with an acquisition rule defined at the level of the solution, as we do. They train a network mapping mixed profiles to deviation payoffs and refine it by sampling in the neighbourhood of each candidate equilibrium, which is the same instinct that motivates our bootstrap sensitivity. Three things separate the settings. Their model takes a mixture as input and returns deviation payoffs directly, so no payoff table is built, whereas we estimate individual cells over policy embeddings and hand the completed matrix to a solver. They exploit role symmetry to scale in the number of players, while our games are two-player and asymmetric with pools that grow by best response. And their refinement is validated empirically rather than through a bound, which is the gap Theorem 1 and Corollary 2 are meant to close: we ask not only where to sample but what the resulting estimate can be shown to be worth. Choosing which expensive evaluation to run is well trod [26, 27], and deep ensembles [13] supply our per-cell uncertainty. Picheny et al. [23] apply Bayesian optimisation to Nash equilibrium computation in black-box games, the closest precedent for treating the equilibrium rather than a payoff as the object of interest; they target continuous strategy spaces with a Gaussian-process surrogate and a fixed game, where we target a finite pool that grows across PSRO iterations and reuse every entry ever simulated as training data. The departure common to both from standard BO is the target functional: we care about the equilibrium of the whole matrix, not pointwise accuracy, so uncertainty is measured by re-solving bootstrap realisations of the game, which the cost asymmetry makes nearly free. Their two criteria are probability of equilibrium and stepwise uncertainty reduction. The first has a discrete analogue we report as a variant in Appendix A.9.3, scoring a cell by the bootstrap frequency with which it enters a support rather than by a Gaussian-process posterior. The second does not port: it targets the probability that a cell is the equilibrium, which is defined for the pure equilibria of their discretised space but not for the mixed equilibria at supports (2,2)(2,2) and (9,9)(9,9) that our games have. Generalising stepwise uncertainty reduction to mixed equilibria is open, and we do not attempt it here. A third line allocates payoff queries adaptively but targets α-rank rather than Nash: Rowland et al. [25] maintain confidence intervals over payoffs until the response graph is determined, and Rashid et al. [24] choose the next query by maximising information gain between an epistemic belief over α-ranks and the observed payoff. Exploitability against a Nash mixture is not what either optimises, so we do not run them as baselines; the information-gain criterion is in any case the one we do run, through Jordan et al. [12]. A.3.2 Method The fill affects how quickly the coverage rule halts, not the validity of what it returns. Corollary 2 removes the fill from the bound, so this is worth stating precisely. The solver reads the complete matrix, so the fill decides which strategies are played, and therefore which cells the coverage rule of Proposition 1 asks for. The construction is a response to the observation of Sokota et al. [28] that a learned payoff model should be accurate around a candidate equilibrium rather than at it. Their sampler perturbs the candidate and projects back onto the simplex, which moves mass toward the simplex edges and so concentrates it further; smoothing toward the uniform mixture moves in the opposite direction. Section 6.3 compares the two directly under an identical fill. When the surrogate’s uncertainty is calibrated, a rule of this form inherits the behaviour of uncertainty-driven acquisition in Bayesian optimization, where any rule monotone in posterior uncertainty is consistent [29, 10]: a cell whose resolution would move the true support has nonzero sensitivity, is eventually queried, and drops out of wsurw_sur (Theorem 1). The ν-floor strengthens this, since every cell in a played row or column keeps a score bounded below of the surrogate’s own uncertainty there. Each selection independently ignores the score with probability εx _x and draws uniformly instead, with revisits averaged into the cache. The per-draw form matters at small batch sizes. A per-batch quota must be an integer, so at c=1c=1 it can only be 00 or 11, which either forces every draw to be uniform or front-loads all exploration into the opening batches and leaves the tail greedy. Theorem 2 requires each unsimulated cell to retain a probability bounded below of being drawn at every step, which the Bernoulli form supplies for any c. RWPS interleaves surrogate fitting with simulation. Each of R rounds refits the ensemble on every cell ever simulated, then spends that round’s share of the budget on the cells its acquisition score ranks highest. The cache persists across PSRO iterations and does three things. A fit at iteration k trains on everything bought earlier, which is what the amortisation result of Section 6 turns on. Cached values always override surrogate predictions, so a cell simulated once is exact from then on. And when the budget is a coverage target rather than an exogenous constant, cached cells count toward it, so each iteration pays only for the part of the deviation-relevant set it does not already hold. The last of these makes the marginal cost constant in the pool size rather than growing with it. Until enough labels accumulate to fit the ensemble, predictions fall back to a rank-one row-and-column model, which is why the first acquisition round on a fresh pool is close to uninformed. A.3.3 Theory Using the same fill inside the solve, as R-max would, changes the object solved. Every unsimulated cell reads as maximal, so a best response points at it, it enters the support, is simulated, is revealed to be ordinary, and leaves – whereupon the next unsimulated cell is the maximal-looking one. Optimism inside the solve is a systematic pull toward whatever has not been paid for, with nDnAn_Dn_A cells to chase, and it certifies only after nearly the whole matrix has been bought (Appendix A.10). Optimism certifies a solution; it does not save simulation. The principle behind this corollary is standard, and we do not claim it. That verifying a profile’s regret requires only that profile and its unilateral deviations is long established in EGTA [39]. Wellman et al. [38] state it directly, together with the observation that the count stays modest for mixed profiles when supports are small, and the same idea underlies minimum-regret-first search [12] and deviation-preserving reduction [41]. What we add is the closed-form count for the bimatrix case and, more consequentially, the coupling to Theorem 1. That coupling is worth spelling out. In prior treatments the complement of the deviation set is unevaluated: it is pruned, deferred, or simply unknown, and the guarantee is stated over what has been sampled. In our setting it is instead filled, by a surrogate that the solver then reads, and the corollary establishes that the accuracy of that fill cannot reach either player’s regret. Note that wsurw_sur is zero whatever β happens to be. This is what makes interpolation admissible in place of pruning, and it is what turns the set into a budget for a budgeted estimator rather than a stopping criterion for a sampler. Read as a budget, the corollary converts equilibrium support size into a quantity we can screen before any rollout is spent. In particular, B∗B is linear in the pool sizes and in the supports, so support size rather than matrix size sets the price. Section 6 evaluates the screen. Corollary 3 (Budget for a target certificate). Fix δ and a target εtgt>εsolve _tgt> _solve. If the deviation-relevant set is covered, so that wsur=0w_sur=0, then the certificate of Corollary 1 is at most εtgt _tgt as soon as every simulated cell carries m≥m∗=min⁡m:2ζ(m,δ)≤εtgt−εsolve,m\;≥\;m \;=\; \\,m:2ζ(m,δ)≤ _tgt- _solve\,\, and the total rollout cost of achieving it is B∗⋅m∗B · m , with m∗=O⁡(σ2log⁡(nDnA/δ)(εtgt−εsolve)2)m \;=\;O\! ( σ^2 (n_Dn_A/δ)( _tgt- _solve)^2 ) up to the log⁡log factor carried by the time-uniform radius. We buy the two factors separately, and neither substitutes for the other. Here B∗B fixes which cells are simulated and removes β, while m∗m fixes how tight the bound is and shrinks ζ. Both are computable in advance, B∗B from bootstrap supports and m∗m by inverting ζ. A deployment can therefore price a guarantee before committing to it, instead of discovering after the fact what its budget bought. Section 6 reports that price. Because every quantity on the right of Corollary 1 is computable from simulation data, the pair also applies where the true equilibrium is not available, which is the setting a deployment faces: a budget can be quoted against a target exploitability rather than the other way round. Coverage is cheap and precision is not. At σ=0.1σ=0.1 on a 30×3030× 30 pool, 2ζ2ζ is roughly half the payoff range at m=4m=4 and reaching 0.050.05 needs m∗≈512m ≈ 512, while pool size enters only logarithmically. The relation to MRFS is exact rather than thematic, and we record it because it fixes the lineage. MRFS confirms a pure profile by evaluating its entire unilateral deviation set, which in a two-player n×n× n game is the row and the column through that cell, or 2n−12n-1 evaluations. Setting sD=sA=1s_D=s_A=1 in Corollary 2 gives n+n−1=2n−1n+n-1=2n-1. In other words, the deviation-relevant set is MRFS’s confirmation criterion carried from a pure profile to a mixed one, with sDs_D and sAs_A replacing the singleton supports. Theorem 1 carries two error sources, statistical and representational, and only the first is controllable by spending. The term β depends on whether fingerprints happen to be payoff-informative for the game at hand, it cannot be certified in advance, and by Theorem 2 it can be arbitrarily bad. Driving wsurw_sur to zero deletes that term outright and leaves a purely statistical certificate, which is the guarantee a full rebuild would give, obtained without a full rebuild and without any assumption about surrogate quality. The set that achieves this is exactly what Lemma 1 identifies as visible to regret. We need full columns on the opponent’s support, since those are the only columns that enter, and full rows on one’s own support, since deviations range over all rows. Nothing outside that set can affect either player’s regret, however wrong it is. Note that coverage does not simulate the matrix. The complementary nDnA−B∗n_Dn_A-B cells remain surrogate-filled and are read by the solver, and Corollary 2 establishes only that they carry zero weight in either player’s regret, not that they are absent. Estimating B∗B is cheap because it costs solves rather than rollouts. The support sizes it needs are not known before solving, but the bootstrap of Section 3.2 estimates them by re-solving many surrogate-filled realisations of the game. This consumes no simulation budget, since solving is negligible next to a rollout, and it follows the bootstrap-over-empirical-games methodology of Wiedenbeck et al. [40]. We can therefore use B∗B as a screen. Before committing any rollouts, a practitioner can read off whether coverage is a small fraction of the matrix, in which case the estimator is worth enabling, or close to all of it, in which case a rebuild is the better option. That is the decision the method actually faces. Read as a prediction the estimate can of course be wrong, and Section A.8.2 shows that it does not have to be read that way. Exploration is necessary The asymptotic guarantee rests on the forced-exploration draws alone. They visit every cell infinitely often almost surely, running means converge, and Lemma 1 with τsupp→0 _supp→ 0 closes the argument; the two-phase Borel–Cantelli proof is standard and we omit it. This cannot be obtained any other way. A fingerprint is a finite summary, so distinct policies can share one while differing arbitrarily in payoff (Appendix A.2), and any rule reading only fingerprints and labels is defeated by that fact. Theorem 2 (Necessity of exploration). Call an attacker strategy atwina_twin a twin if it is densely simulated and uniformly weak, and atrapa_trap a trap if φ⁡(atrap)=φ⁡(atwin) (a_trap)= (a_twin) while its true payoffs make it a dominant deviation. Let A be any deterministic acquisition rule whose selections are a function of the fingerprints φ⁡(s)s∈SD∪SA\ (s)\_s∈ S_D∪ S_A and the cache C alone. Then for every budget B<nDnAB<n_Dn_A there is a twin–trap instance on which A simulates no trap cell, and on which the returned mixture has exploitability at least η>0η>0 with η determined by the instance and independent of B. A.3.4 Results The result is end-to-end and does not isolate the matrix from the strategies. Pools are identical only at iteration 00. Each method’s best response is trained against its own mixture, so a better estimate steers the oracle to different strategies and the pools diverge. We measure exploitability against the full game by zero-lifting, which keeps pools of different composition comparable, but the number still credits the estimator for the strategies it leads PSRO to find. Appendix A.7 repeats the comparison with identical payoffs and uninformative fingerprints, which isolates what the embedding contributes. Information-gain search finishes at 0.0820.082 and 0.3430.343, behind both MRFS and the estimator. IGS is the comparator Jordan et al. [12] recommend for noisy payoffs, where MRFS is their revealed-payoff algorithm, and they report IGS outperforming the ECVI benchmark. We implement it from their Section 6.2. The profile maximising the Kullback–Leibler information gain aggregated over its deviation set is sampled next, with psp_s the probability that s has minimum regret under their point approximation, and an MRFS prefix supplies initial samples as in their IGS-MRFS-3. The budget, not the algorithm, is what puts IGS behind. IGS allocates samples across profiles it has already visited; the original experiments run it at roughly twenty-eight samples per profile on a thirty-five-profile game. A budget that cannot visit every profile once denies it the quantity it reasons about. This is visible on a fixed pool: at 21×2121× 21 IGS improves from 0.1770.177 to 0.0410.041 as the allowance grows from 0.20.2 to 1.01.0 evaluations per profile, converging toward MRFS. We make the same observation about PSP and its relatives below. The progressive-sampling family does not reach its own operating regime here. None of the three prunes a single utility index at a 5%5\% per-build budget—at a 14×1414× 14 pool that budget is ten cell evaluations, against the 294294 samples per cell PSP’s schedule requires before its bound certifies anything—so all three reduce to sampling a handful of profiles exhaustively and flat-filling the remainder, and coincide exactly. This is the regime argument of Section 6 reproduced in the deployment setting rather than a defect of those algorithms. Figure 5: NashConv over cumulative simulator calls (lower is better) in CyGym. At low and high budgets, uniform sampling suffices, but across all budget levels, meets of exceeds performance. The solver term earns its place. Without it the signed bound is violated on three runs, all on Blotto and all by less than the solver’s own regret on that run; fictitious play converges slowly on games with large supports, and raising its iteration count from 400400 to 20,00020,000 does not remove the residual (measured εsolve _solve averages 0.0080.008 on Blotto against 0.0020.002 on the informative game). Since εsolve _solve is computable from the estimated matrices alone, adding it costs nothing in applicability and restores validity on every run at a cost of 0.0060.006 in mean tightness. The table is needed because the rule of Sokota et al. [28] is a score over cells, not a payoff-build method, so it has no row in Table 1. Running it inside an otherwise identical build is the only fair comparison available to us. The estimator starts behind. At iteration 00 it is at 0.2620.262 against MRFS’s 0.1800.180 and uniform’s 0.2080.208. We expect this. The cache is empty at the first build, so there is nothing to amortise and the surrogate is a rank-one fit to almost no labels. What distinguishes the estimator is what it carries between builds, not what it does on one. The gap widens monotonically in the iteration index, which a per-build account does not predict. Error off the equilibrium support is invisible to regret, and Figure 4 (Appendix A.3.4) measures that on the estimator’s own output. It plots all 240240 budget-sweep runs sorted by realised exploitability, with the gap between ε and each bound shaded. No band closes, so every bound holds on every run. Our bound is the signed form (a) of Eq. (3) plus the measured solver term. It averages 0.250.25 of the sup-norm bound, with a median overestimation factor of 2.32.3 against 11.411.4, and the intermediate forms fall where the chain predicts: the support-weighted form (c) averages 0.470.47 and the two-term form (b) 0.330.33. The estimator concentrates error on unplayed cells, the sup-norm is set by exactly those cells, and the support weighting removes them. The asymmetry the design assumes is therefore real and not an artifact of a loose analysis. Latent-quality, arbitrary embedding. Identical payoffs, fingerprints drawn independently of q: identity without payoff information. This isolates whether the surrogate’s benefit is generalisation across embedding space or amortisation of row and column effects. It is an ablation of the fingerprint rather than a third domain, and is reported as such in Appendix A.7. Error decomposition: rebuild with one error source replaced by truth and re-solve, isolating statistical from representational contributions. Coverage corollary: simulate exactly the deviation-relevant set of Corollary 2, surrogate elsewhere, and compare ε to a full rebuild. The uniform row here is not the uniform row of Table 1. Here uniform samples cells at random but still fills the rest with the surrogate. In Table 1 it also replaces the surrogate with a flat value. Comparing the two isolates the fill. A.4 The Agentic Network Security Game This appendix gives the full specification of the ANSG introduced in Section 5. CyGym [16] models compromise as binary node access: the attacker exploits a node and thereby controls it. In a network of LLM agents the relevant failure is different. An agent processes workloads by invoking tools, and an adversary who plants instructions in content the agent reads can cause it to execute attacker-chosen goals in addition to the ones its principal asked for. The legitimate task still completes, so the subversion need not look like a failure at all. ANSG replaces access-compromise with this goal subversion model, keeping CyGym’s binary per-node state and its PSRO solution machinery while changing what compromise means and what each player can observe. ANSG is a two-player general-sum partially observable stochastic game =⟨,OD,OA,D,A,,UD,UA,γ⟩G= ,\,O^D,\,O^A,\,A^D,\,A^A,\,T,\,U^D,\,U^A,\,γ over a directed communication graph G=(,ℰ)G=(V,E) whose nodes host agents. Each node carries a behavioural mode bv∈,b_v∈\ benign, malicious\ and a context age hvh_v. Both players choose policies simultaneously without observing the other’s, so Nash equilibrium is the solution concept and PSRO the approximation method, as in CyGym. Attacker and defender valuations are independent rather than opposed: the attacker gains the value of the subverted goals it executes, while the defender loses the value of its workloads being corrupted, and these need not sum to a constant. Per-goal value factors differ by player. This is the property that makes ANSG a natural test for a budgeted estimator whose theory assumes nothing about zero-sum structure. The defender may audit a node, receiving a noisy signal whose detectability rises with the value of the subverted goal; reprompt it, a soft intervention with no CyGym analogue; reset it, which restores benign behaviour but erases context history at a cost; or isolate it, severing communication edges and halting propagation. The attacker may inject a payload into a workload, choosing a target, a goal rank, and a channel, or probe to estimate which previously compromised nodes remain malicious. Injection carries a channel choice χ. Indirect prompt injection appends an attacker goal alongside the legitimate workload, which therefore completes normally; the only signal is a rank-dependent trace. Malicious tool triggering instead redirects an existing call, denying the legitimate output for a more damaging hit at higher detection probability. The rank choice sets value against exposure, and the channel choice compounds it. Both players are partially informed, which is the substantive departure from CyGym. The defender sees only noisy audit signals. The attacker cannot observe resets, and because a reset benign node is behaviourally indistinguishable from one never compromised, must probe to estimate the current state. Compromise also propagates: a malicious agent can embed payloads in its outputs, infecting downstream agents along ℰE. ANSG is the harder of the two deployment games for a budgeted build, for reasons the theory anticipates. Payoffs require full rollouts of a partially observable game, so simulation dominates iteration cost and the premise of Section 6 holds strongly. Equilibrium supports are not known in advance, so B∗B must be estimated from bootstrap replicates rather than read off a solved game. And no ground-truth equilibrium is computable, so the certificate of Corollary 1 is the only available quality measure rather than a diagnostic checked against a known answer. A.5 Budget sweep on Cyberwheel When the pool is flat, every arm that buys cells returns essentially the same equilibrium, and budgeted acquisition has nothing to separate. Figure 6 repeats the budget sweep of Section 6.2 on Cyberwheel [21]. Uniform sampling, IGS, MRFS, and both RWPS variants all sit within about 0.0150.015 of zero exploitability at every budget, with overlapping bands from budget 2 onward. The one visible separation is at budget 1, where RWPS (uniform) is highest of the buying arms. GS/PSP/PS-REG-M is constant near 0.160.16 because, as on CyGym and ANSG, its sampling schedule cannot afford a single cell and it returns the history-only estimate. The pool is flat in a measurable sense: on this 6×66× 6 pool the payoff signal-to-noise ratio is below 11 for both roles, so no cell’s simulated value is distinguishable from rollout noise. This is the outcome Corollary 2 predicts for a matrix on which no cell is much more deviation-relevant than another: if the surrogate is already accurate everywhere, which cells are bought barely changes the equilibrium. We report it as the regime in which RWPS offers no advantage over simple baselines, and in which it also costs nothing. Figure 6: Cyberwheel budget sweep. 6×66× 6 pool with a 5×55× 5 history pre-cached for every arm, leaving 1111 cells to buy; 1616 seeds. Exploitability is computed against the stored payoff matrix of the pool. Bands are ±1± 1 standard error. All buying arms coincide within their bands; GS/PSP/PS-REG-M buys nothing and returns the history-only estimate. A.6 Implementation and computational procedure This appendix gives the full RWPS procedure as configured for the experiments of Section 5; Section 3.2 summarises it. Given a budget B over R rounds, each round performs four steps. 1. Fit. The ensemble of M networks is refit on the entire cache—every cell ever simulated, in this build and in all previous ones—each network on its own bootstrap resample of the labels. Inputs and targets are standardised per fit. 2. Predict. The fitted ensemble predicts the full grid, returning a mean u^ij u_ij and a disagreement σ^ij σ_ij on every unsimulated cell. 3. Bootstrap. BbootB_boot realisations of the game are drawn and re-solved by fictitious play to give W and ς . This step consumes no simulation budget; it costs only solves, which are cheap by the cost asymmetry the method exploits. 4. Simulate. The round’s share of the budget is spent: c cells, each drawn uniformly at random with probability εx _x and otherwise taken by descending acquisition score. New labels enter the cache and become training data for the next round’s fit. Real payoffs are therefore evaluated R times per build, in batches of roughly B/RB/R cells, and the surrogate is refit R+1R+1 times: once per round, plus a final fit before the matrices are committed. The cache lives on the simulator rather than on the builder, so it is persistent across PSRO iterations: a fit at iteration k trains on everything bought at iterations 1,…,k−11,…,k-1 as well. Cached values always override surrogate predictions, so a cell simulated once is exact from then on. Model state is also carried across builds: the ensemble is warm-started from the previous build() call rather than reinitialised, which leaves final exploitability unchanged (Welch p=0.81p=0.81 informative, p=0.62p=0.62 Blotto over eight seeds) and reduces payoff-build wall clock by 1717–20%20\%. The scope matters and is deliberately narrow: warm-starting the R internal rounds of a single build was measured to hurt, because the cache roughly doubles between rounds at a 40%40\% budget while a +1+1 pool growth enlarges it by only about a fifth, so a short warm schedule tracks the second and not the first. Rounds 2..R2..R and the final commit fit are therefore forced cold, and only a build’s opening fit continues from the previous build. Under a coverage budget the cache is also read for budget accounting: the target is B∗B evaluated at the current supports, and the amount actually spent is that target less the deviation-relevant cells already in C, so the per-iteration spend is the uncovered remainder rather than B∗B itself. Repeat visits arise only from the exploration draws, and only once every unsimulated cell has been visited; they are averaged into a running mean rather than overwriting, so a cell visited k times carries the mean of its k estimates and its effective NMCN_MC is k times the nominal value. Until the cache holds enough labels to fit the ensemble (eight, in our configuration), predictions fall back to a rank-one row-and-column model: row and column means of the observed entries, with the residual standard deviation serving as σ σ. The first acquisition round of the first build on a fresh pool is therefore close to uninformed, which at the smallest budgets is the dominant source of seed-to-seed variance. Unless stated otherwise we use M=3M=3 ensemble members, each a two-hidden-layer MLP of width 4848 trained for 6060 epochs with Adam at learning rate 5×10−35× 10^-3; Bboot=32B_boot=32 bootstrap replicates subsampling 80%80\% of each pool; R=3R=3 rounds; exploration probability εx=0.15 _x=0.15 applied as an independent Bernoulli per selection, batch size c=⌈B/3⌉c= B/3 unless stated (both ablated in Section A.9.2); and κ=0.25κ=0.25. Fictitious play runs 400400 iterations for the final solve and 200200 within the bootstrap. Each simulation call averages NMC=4N_MC=4 rollouts, and rollout noise is Gaussian with σ=0.10σ=0.10 on payoffs scaled to [0,1][0,1]. Games are 21×2121× 21, giving 441441 cells; all reported budgets are fractions of that. Probe banks hold P=32P=32 states per role. A.7 What the embedding contributes The latent-quality game admits a controlled ablation of the fingerprint. Holding the payoff matrices fixed and redrawing the fingerprints independently of latent quality yields a game identical in every respect except that the embedding carries no payoff information. Table 3 repeats the growing-pool comparison of Section 6.1 on both versions. Table 3: Growing-pool PSRO on games with identical payoffs and different fingerprints; final exploitability, mean over five seeds, all budgeted methods at a budget of 256256. Only the estimator reads fingerprints, so only its row moves. Payoff build informative uninformative Δ RWPS (ours) 0.0450.045 0.0600.060 +0.015+0.015 MRFS 0.0530.053 0.0530.053 00 IGS 0.0820.082 0.0820.082 00 GS / PSP / PS-REG-M 0.2690.269 0.2690.269 00 full, unbudgeted 0.0350.035 0.0350.035 00 Every method that does not consult the embedding is unchanged to the reported precision, which is a check on the construction as much as a result. The estimator is the only row that moves, so 0.0150.015 is a direct measurement of what payoff-informative fingerprints are worth in this game. The decomposition that follows is the substantive point, and it is not the one a reader would guess from the method description. The estimator’s advantage over uniform sampling splits into a part that survives an uninformative embedding, 0.092→0.0600.092→ 0.060, and a part attributable to generalisation across embedding space, 0.060→0.0450.060→ 0.045. The first is the larger. With fingerprints that are pure noise the surrogate still amortises row and column effects from cells already simulated—it continues to learn that a given strategy tends to score well or badly against the pool, which requires no embedding at all—and that alone recovers most of the gap. This tempers the natural reading of payoff regression over policy embeddings, and it is why the rank-one row-and-column fallback of Appendix A.6 is not merely a cold-start device: it is a substantial fraction of what the surrogate does throughout. It also explains where the estimator stops winning. On the uninformative game MRFS reaches 0.0530.053 against the estimator’s 0.0600.060, inside one standard deviation. MRFS obtains the same row-and-column structure directly, by expanding a profile into its unilateral deviations, and needs no embedding to do it. When the embedding contributes nothing there is nothing left for the estimator to win with, and the two methods are measuring the same thing by different means. We report this as the intended outcome of the ablation rather than as a defeat: the uninformative game exists to isolate the embedding term, and a near-tie with a model-free method is the correct result when that term is zero by construction. A.8 Coverage as a fixed point Corollary 2 identifies the deviation-relevant set B∗B and Corollary 3 prices a target certificate against it. This appendix turns the pair into an iteration and gives the asymptotic guarantee that follows. The finite-budget result the paper relies on is Theorem 1, which does not depend on anything here. A.8.1 The budget a target certificate requires Corollary 1 reports what a completed build certifies. Run backwards, it answers the question a practitioner actually asks, namely how much simulation buys a stated guarantee. The answer is available before any of that simulation is spent. A.8.2 Coverage as a fixed point We do not treat B∗B as a prediction that has to be got right. Instead we treat it as the first iterate of a procedure that comes with a free stopping test. The test is wsur=0w_sur=0, which holds exactly when the deviation-relevant set of the returned (p^,q^)( p, q) has been covered, and which is a cache-membership query costing no rollouts. This dissolves the apparent circularity in reading B∗B as an a-priori budget. The supports it needs are a property of the solve that it funds, but the procedure does not need them to be correct, only to be verified at the end. Proposition 1 (Coverage iteration). From any cache, iterate: solve (D^t,A^t)( D_t, A_t) for (p^t,q^t)( p_t, q_t); simulate every uncached cell of 1:nD×supp⁡(q^t)∪supp⁡(p^t)×1:nA\1:n_D\×supp( q_t) ( p_t)×\1:n_A\; refit and repeat, halting when wsur(p^t)=wsur(q^t)=0w_sur( p_t)=w_sur( q_t)=0. Then (i) the procedure halts after at most nD+nAn_D+n_A rounds; (i) at halting the hypothesis of Corollary 2 holds for the equilibrium actually returned, so ε≤εsolve+2ζ(m,δ) ≤ _solve+2ζ(m,δ) with no dependence on β; (i) total simulation never exceeds nDnAn_Dn_A cells, so the procedure is never more expensive than the full rebuild it replaces. Halting is by exhaustion of rows and columns, so the sequence of mixtures need not converge, and an oscillating equilibrium costs additional rounds and nothing else. The procedure is sound and terminating but not minimal, since an intermediate mixture can pull in rows for a support that later vacates. Note that the two error directions are not symmetric. Overshooting the support buys unnecessary cells while keeping the guarantee, whereas undershooting forfeits it, so we seed the first iterate with the union of the bootstrap supports rather than with a threshold on their average. Theorem 3 (Convergence under coverage). Consider a sequence of builds in which the iteration of Proposition 1 is run to halting whenever the returned mixture changes, and in which every cell of the coverage set continues to be sampled. Then, on the event of probability at least 1−δ1-δ on which Theorem 1 holds, (i) at most nD+nAn_D+n_A coverage extensions occur over the entire sequence, after which wsur(p^)=wsur(q^)=0w_sur( p)=w_sur( q)=0 holds permanently; (i) thereafter ε≤εsolve+2ζ(m,δ) ≤ _solve+2ζ(m,δ), and ε→εsolve → _solve as m→∞m→∞; (i) hence, with the restricted game solved exactly, the returned mixture converges to an exact equilibrium of that game, while the nDnA−B∗n_Dn_A-B surrogate-filled cells are never corrected and may remain arbitrarily wrong. A single confidence event supports every m here, which is what the time-uniform radius buys us: a fixed-design bound holds at one prescribed sample size, so letting m→∞m→∞ under it would require a union over sample sizes. Neither half of the result is an assumption. We reach coverage in finitely many rounds using a stopping test that is a cache query, and the vanishing of ζ follows from continued sampling of the cells that coverage identifies. Coverage decides which cells convergence is possible on and visits decide how fast, so spending alone does not substitute for coverage. The contrast with Section A.3 is one of cost: that argument needs forced exploration to visit every cell infinitely often, Θ⁡(nDnA) (n_Dn_A) cells, whereas this one needs only the Θ⁡(nDsA+nAsD) (n_Ds_A+n_As_D) cells of the coverage set. Coverage guarantees the bound, not the solve. Driving wsurw_sur to zero removes β from Theorem 1 by construction, so the bound holds whatever the surrogate predicts. The certificate no longer depends on surrogate quality. The surrogate has not ceased to matter. Which equilibrium the solver arrives at is still a function of the fill, because the solver reads the complete matrix and the unsimulated cells are exactly the cells that determined they were unplayed. The surrogate therefore controls rounds to termination rather than the validity of what the iteration returns. The β⋅wsurβ· w_sur term cannot express this role, since coverage sets it to zero. At B∗B coverage a surrogate fill and a flat fill carry the same guarantee, and Section 6 separates them empirically. Coverage separates the budget into two parts that are priced independently. Coverage decides which cells are bought and removes β⋅wsurβ· w_sur. Revisits decide how tight the bound is and shrink 2ζ(m,δ)2ζ(m,δ). Only the first is a question about the matrix, and it is the cheap one, costing sD+sAs_D+s_A cells per iteration under stable supports. The second is a visit count, and at small m it dominates, so a covered build certifies very little until m grows. A deployment can invert this: fix the exploitability bound required, take m to be the smallest visit count with 2ζ(m,δ)2ζ(m,δ) below it, and the rollout budget follows as the coverage set times m. Section 6 prices this. The iteration trades a spending cap for a guarantee. A budget fixed as a fraction of the matrix bounds what a build can cost. The iteration instead spends what the game demands, which is sD+sAs_D+s_A cells per iteration under stable supports and, in the worst case, the full matrix. Under a hard rollout ceiling it may be truncated before it halts. Nothing is lost when that happens. Stopping with wsur>0w_sur>0 returns us to Theorem 1 with the representational term retained at the measured wsurw_sur, which is the bound the estimator carries in any case. Halting is what removes β; truncation degrades to the general bound rather than forfeiting it. Fingerprint collisions do not defeat coverage. Theorem 2 constrains acquisition rules that read fingerprints, and its proof plants the trap in a column the rule never touches. Coverage admits no such column: wsur(p^)=0w_sur( p)=0 requires supp⁡(p^)×1:nAsupp( p)×\1:n_A\, so every attacker strategy is simulated against the defender’s support whatever its fingerprint reports, and the construction has nowhere to place the trap. If a trap’s true payoffs make it a profitable deviation against p p, covering reveals them, the re-solve moves mass onto it, wsurw_sur becomes positive, and the next round completes its column. If it is profitable only against strategies outside supp⁡(p^)supp( p), then it does not enter maxj⁡(Ap^)j _j(A p)_j and is not a deviation by which the returned mixture can be exploited. Forced exploration remains load-bearing for the acquisition rule of Section 3.2, whose score is a function of the embedding, but it is not needed for the coverage guarantee. Coverage costs sD+sAs_D+s_A cells per PSRO iteration whenever a new strategy pair leaves the supports unchanged. With a persistent cache the honest baseline is not a Θ⁡(nDnA) (n_Dn_A) rebuild. It is the 2k+12k+1 cells that a pool of size k per side newly exposes, an incremental-caching accounting standard in EGTA [39, 41]. The result is immediate: those are the only cells of the deviation-relevant set the cache does not already hold, which is to say the only cells at which wsur≠0w_sur≠ 0. The condition is support stability rather than support size, and it is the regime PSRO enters near termination. The saving accrues late in a run rather than eroding. Each result above attaches to a different part of the estimator, and none of them derives the acquisition rule. The surrogate fill steers which equilibrium is solved for. Coverage makes the bound on that equilibrium independent of the fill (Proposition 1). Corollary 1 certifies the result post hoc in settings where no ground truth exists, and Corollary 3 inverts that certificate into a budget. One caveat is worth stating. Our acquisition rule targets value sensitivity, through W on support×support, rather than the deviation-relevant set, so it under-covers relative to Corollary 2, with the exploration draws supplying the remainder. Closing that gap with a rule that targets deviation coverage directly is an immediate direction for future work. A.9 Ablations and bound diagnostics A.9.1 Error decomposition Counterfactual decomposition (Figure 7) replaces one error source at a time with ground truth and re-solves. Error is representational at low budget and statistical at high, with the crossover below 20%20\% on the informative game, between 20%20\% and 40%40\% on the arbitrary game, and near 40%40\% on Blotto. This yields a tuning rule: below the crossover spend on coverage, above it on revisits. The crossover need not be measured. Coverage and revisits buy different terms of Theorem 1 and are priced separately: coverage decides which cells and drives β⋅wsurβ· w_sur to zero, while revisits decide how tight and shrink 2ζ(m,δ)2ζ(m,δ). The rule in closed form is therefore to cover until wsur=0w_sur=0, which Proposition 1 bounds at nD+nAn_D+n_A rounds and costs sD+sAs_D+s_A cells per PSRO iteration under stable supports, and then to spend every remaining rollout revisiting covered cells until 2ζ(m,δ)2ζ(m,δ) meets the exploitability target. The two phases do not compete for the same cells: revisits fall only on cells coverage has already bought. Figure 7: Counterfactual decomposition of ε into statistical and representational parts (seed means; dotted line is the solver floor). A.9.2 Batch size and exploration probability The acquisition loop has two knobs. The batch size c is the number of cells bought between refits: c=Bc=B commits the whole budget on a single ranking, c=1c=1 re-ranks after every cell. The exploration probability εx _x is the chance that a given selection ignores the score. Table 4 sweeps both at a 20%20\% budget over four seeds. Table 4: Exploitability against batch size c and exploration probability εx _x, 20%20\% budget, mean over four seeds. Batch size is the operative knob; εx _x is close to flat. εx _x c 0.000.00 0.050.05 0.150.15 0.300.30 Latent, informative 11 0.0180.018 0.0290.029 0.0190.019 0.0280.028 44 0.0300.030 0.0540.054 0.0560.056 0.0270.027 1616 0.0140.014 0.0310.031 0.0370.037 0.0420.042 6464 0.0410.041 0.0280.028 0.0330.033 0.0740.074 Blotto 11 0.0730.073 0.0420.042 0.0780.078 0.0740.074 44 0.0860.086 0.0740.074 0.1070.107 0.1060.106 1616 0.1640.164 0.1640.164 0.1940.194 0.1600.160 6464 0.1630.163 0.1390.139 0.2140.214 0.1670.167 Batch size is the parameter that matters, and it matters where the theory says it should. On Blotto, c=1c=1 reaches 0.0730.073 against 0.1630.163 at c=64c=64, a factor of 2.22.2; on the informative game the effect is within seed noise. The asymmetry follows from what a batch commits to: every cell in a batch is chosen from one ranking, so a large c spends that share of the budget on the surrogate’s state at the start of the batch. On a game the surrogate fits well that state is already good and the loss is small; on a combinatorial surface it is not, and re-ranking after each cell recovers most of the gap. The exploration probability is close to flat, and εx=0 _x=0 is best or tied in several cells. This is the expected reading rather than a contradiction. Theorem 2 establishes that exploration is necessary, in the sense that no rule reading only fingerprints and the cache carries the asymptotic guarantee without it; it does not claim that exploration improves finite-budget exploitability on a benign instance. These three games are benign in exactly that sense—no fingerprint collision is constructed—so exploration buys the guarantee and not the number, and its cost is the small budget share it diverts. The instance where it earns its keep is the twin–trap construction, reported separately in Section 6. We therefore keep εx=0.15 _x=0.15 as the default: it is insurance whose premium is measured here and whose payout is measured there. A.9.3 Variants of the acquisition score Table 2 compares our rule against prior work and against no score at all. This subsection varies our own rule instead, under the same protocol: identical surrogate, budget, batch schedule and forced-exploration rate, sixteen paired seeds, ε12 _12. None of these is a baseline drawn from the literature; each removes or replaces one ingredient of the score in Algorithm 1. Table 5: Variants of our acquisition score. The first row repeats Table 2 for reference. Mean ± SD over sixteen paired seeds. Acquisition score Informative Blotto ν-smoothed product (ours) 0.024±0.0170.024± 0.017 0.082±0.0420.082± 0.042 bootstrap inclusion 0.035±0.0220.035 ±0.022 0.100±0.0690.100 ±0.069 training exposure 0.039±0.0190.039 ±0.019 0.105±0.0440.105 ±0.044 value-sensitivity (ν=0ν=0) 0.048±0.0380.048 ±0.038 0.096±0.0580.096 ±0.058 Value-sensitivity (ν=0ν=0) isolates the smoothing, and the ordering reverses across games. It is the rule used in earlier versions of this work: no smoothing, and the product returned inside the bootstrap average. Smoothing is worth 0.0240.024 on the latent games (p=0.007p=0.007, 12/1612/16 seeds) and 0.0140.014 on Blotto, where it is not significant (p=0.348p=0.348, 9/169/16). It therefore does its work where the support estimate is sharp and the unsmoothed score concentrates on a handful of cells, not where the support is already broad—on Blotto, at supports (12,12)(12,12), the unsmoothed score already spreads over most of the matrix and there is little left for ν to do. Bootstrap inclusion replaces equilibrium mass with inclusion frequency, the fraction of bootstrap replicates in which a strategy appears in the support at all, and sums the two roles rather than multiplying them. This is the discrete analogue of the probability-of-equilibrium criterion of Picheny et al. [23], with the bootstrap standing in for their Gaussian-process posterior. The sum is our departure from it: a product is supported only on supp⁡(p^)×supp⁡(q^)supp( p)×supp( q), whereas a sum scores every row against any plausible column, which is the shape of the deviation-relevant set of Corollary 2. It is the same neighbourhood idea as ν, learned from the bootstrap rather than imposed by a fixed constant, and it finishes second here—close enough that the choice between them is not settled by these games. Training exposure is the PSRO-specific rule. Every strategy in the pool arrived as a best response to a known opponent mixture, so the cells pairing it with the opponents it was optimised against are cells whose values that optimisation has already partly determined; the cells it was never trained against are both less predictable and, by Corollary 2, deviation-relevant as soon as that strategy enters a support. The rule down-weights a cell by the training exposure e⁡(i,j)e(i,j), the weight the mixture that produced aja_j placed on defender i, and symmetrically. It is the only rule considered anywhere in this paper that uses information no payoff-build baseline can see, since only the outer loop knows what each strategy was trained against, and it finishes fourth. We report it because the negative result is informative: a best response supplies one scalar constraint on a p p-weighted average of a column, not per-cell information, and weighting cells by it asks the constraint to carry more than it does. The constraint is better used inside the surrogate fit, which we have not attempted here. A.10 Bound and certificate diagnostics These three studies use fixed pools as a diagnostic bed rather than the growing-pool setting of Section 6. The first shows that the deviation-relevant set predicts cost before any budget is spent. The second breaks Figure 4 down by game. The third gives what the computable certificate costs in optimism. None is needed to read Table 1, Table 2, or Figure 4. A.10.1 Predicting difficulty before spending The results above are retrospective: they report what a budget bought. The practical question is the prospective one, whether a game’s cost can be known before committing to it. Corollary 2 answers it with B∗=nDsA+nAsD−sDsAB =n_Ds_A+n_As_D-s_Ds_A, computable from bootstrap support estimates alone, and Table 6 evaluates it directly: simulate exactly the deviation-relevant set, surrogate elsewhere. Two claims are tested. First, B∗B orders the games correctly. The two latent games have supports of size 22 on each side and cost 8080 cells, 18%18\% of the matrix; Blotto’s supports come out at (12,12)(12,12) under this solver, giving B∗=360B =360 cells, 82%82\%. That ordering is available before any budget is spent, and it matches the ordering the growing-pool results of Section 6.1 reveal. Equilibrium support size, not matrix size, is the operative quantity. Second, simulating exactly that set delivers full-rebuild quality: on the informative game coverage reaches 0.017±0.0030.017± 0.003 against 0.033±0.0140.033± 0.014 for a full rebuild, at 18%18\% of the simulation, and on the arbitrary game it is statistically indistinguishable (0.038±0.0200.038± 0.020). Coverage is therefore not merely equal to a full rebuild on the informative game, it is slightly ahead of it, and the reason is worth stating because it looks at first like an error. A full rebuild measures every one of the 441441 cells independently at NMC=4N_MC=4 and keeps the statistical error of all of them. Coverage measures 8080 cells and predicts the rest from a model fitted to everything observed so far. When that model class contains the truth, its predictions pool information across the matrix and carry lower variance than an individual four-rollout average, so replacing measurements by predictions can reduce error rather than add it. The latent games are the extreme case, since their payoff matrices are exactly rank one by construction (Section 5) and the surrogate’s row-and-column fallback is correctly specified for them. Applying a rank-one projection to a full rebuild’s own noisy measurements reproduces the effect on its own, halving realised exploitability, which confirms that the gain comes from denoising rather than from anything the acquisition rule does. The effect tracks how well the model class contains the truth, and it disappears when that fails. On the arbitrary game the payoffs are the same but the fingerprints carry no information, so only row and column effects can be pooled and coverage is indistinguishable from a rebuild. On Blotto it is worse. The payoff surface there has effective rank above four, the surrogate cannot fit it, and at 82%82\% coverage there is little left to save in any case. Table 6: Deviation-relevant coverage (Corollary 2), mean ± SD over sixteen seeds, on 21×2121× 21 games (441441 cells). Game supp. B∗B (%) ε Latent, informative (2,2)(2,2) 8080 (1818) 0.017±0.0030.017± 0.003 Latent, arbitrary (2,2)(2,2) 8080 (1818) 0.038±0.0200.038± 0.020 Blotto (12,12)(12,12) 360360 (8282) 0.062±0.0340.062± 0.034 full rebuild, latent 441441 (100100) 0.033±0.0140.033± 0.014 full rebuild, Blotto 441441 (100100) 0.043±0.0210.043± 0.021 A.10.2 Bound tightness by game Figure 8: Overestimation factor, bound over realised ε , per game (mean ± SD over the 240240 budget-sweep runs, log scale). Labels refer to the forms of Eq. (3); our bound is 44–6×6× tighter than the sup-norm bound. Figure 8 reports the same 240240 runs as per-game overestimation factors. The sup-norm bound (d) overestimates realised ε by mean factors of 22.722.7, 20.020.0, and 11.711.7 on the three games; the support-weighted form (c) reduces these to 11.111.1, 7.27.2, and 4.34.3; the signed form (a) with the measured solver term to 5.85.8, 3.43.4, and 2.02.0. Mean ratios carry heavy right tails, since a run with near-zero realised ε inflates the ratio however tight the bound is in absolute terms, so the seed spreads are large. The ordering (d) >> (c) >> (a) is uniform across games and budgets. A.10.3 The computable certificate, and the cost of optimism Corollary 1 is evaluated in both of the roles Section 4 distinguishes. Used post hoc at B∗B coverage, the computable certificate held on all 4848 runs, with values of 0.935±0.0590.935± 0.059 and 0.938±0.0750.938± 0.075 on the latent games and 0.516±0.0320.516± 0.032 on Blotto against realised ε of 0.0170.017–0.0620.062 (Table 6). At m=4m=4 visits its slack is dominated by the time-uniform concentration radius 2ζ4,0.05=0.4812 _4,0.05=0.481 and by mismatch between the estimated and true supports, and it contracts as 1/m1/ m with revisits. Proposition 1 removes the second of those two sources by construction: iterating coverage to wsur=0w_sur=0 leaves the statistical radius as the only slack. That remaining slack is the operative constraint, and it is a visit count rather than a coverage question. At m=4m=4 the bound a fully covered build can certify is εsolve+0.481 _solve+0.481, roughly half the payoff range, which is why the certificates above sit near 0.940.94 against realised ε of 0.0170.017–0.0620.062: the estimator was buying the right cells and not enough visits. Inverting 2ζ(m,δ)2ζ(m,δ) prices the alternative. A certificate of 0.250.25 needs m=16m=16 and, at the 8080 cells of B∗B coverage, 1,2801,280 rollouts—below the 1,7641,764 a full rebuild spends at m=4m=4. A certificate of 0.100.10 needs m=101m=101 and 8,0808,080 rollouts, and one of 0.050.05 needs m=408m=408 and 32,64032,640, some 18×18× a full rebuild. Coverage is cheap and the certificate is not; a deployment should choose the bound it needs and let the visit count follow, rather than choosing a cell budget and discovering what it certifies. Used inside the solve, R-max style, optimism certified only after simulating 9090–97%97\% of the matrix (395395–430430 of 441441 cells), because every unsimulated cell looks maximal and the support chases fresh cells. The division of labour is therefore a three-way one: the surrogate fill decides which equilibrium is solved for, coverage of the deviation-relevant set makes the bound on that equilibrium independent of the fill, and optimism only certifies it. The B∗B runs above isolate the middle role—every one of them carries the same β-free guarantee—while the exploitability they reach still separates surrogate fill from the flat fill of the uniform baseline, which is the first role.

Instant research discovery