Paper deep dive
Efficient Nash Equilibrium Computation for Cybersecurity Games
Michael Lanier, David Farmer, Yevgeniy Vorobeychik
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 9/23/2026, 3:42:29 AM
Summary
This paper introduces Regret-Weighted Payoff Sampling (RWPS), a method for efficiently computing Nash equilibria in simulation-based cybersecurity games. RWPS addresses the bottleneck of expensive payoff estimation by using a learned surrogate model to predict unsimulated payoffs and a scoring mechanism that prioritizes simulating payoffs most critical to the equilibrium. The authors prove tighter error bounds that weight payoff errors by the opponent's equilibrium strategy, showing that RWPS achieves lower exploitability with fewer simulator runs compared to existing methods like minimum-regret-first search and progressive sampling.
Entities (6)
Relation Signals (6)
RWPS → appliedto → CyGym
confidence 95% · On two cyber-defence simulators, CyGym... it gives the least exploitable equilibria at the smallest budgets.
RWPS → uses → Surrogate Model
confidence 95% · RWPS predicts the rest with a model trained on every payoff measured so far.
RWPS → appliedto → ANSG
confidence 92% · On CyGym and ANSG, RWPS reaches the lowest exploitability at the smallest budgets
ANSG → extends → CyGym
confidence 90% · ANSG extends CyGym [20] to networks of LLM agents that an attacker can subvert through indirect prompt injection
RWPS → improvesupon → Minimum-Regret-First Search
confidence 90% · RWPS finds less exploitable equilibria than minimum-regret-first search, information-gain search and progressive sampling at the same budget.
RWPS → extends → Tuyls et al. bound
confidence 85% · We sharpen the bound of Tuyls et al. [39] so that a player’s regret depends only on payoff errors weighted by the opponent’s equilibrium strategy
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Game-theoretic analyses of cyber defence often compute equilibria of games whose payoffs exist only as the output of a simulator. Iterative equilibrium-finding methods grow a set of attacker and defender policies and need the payoff of every attacker--defender pair, so they are bottlenecked by payoff estimation: each payoff costs many simulator runs. We introduce Regret-Weighted Payoff Sampling (RWPS), which spends a fixed simulation budget on the payoffs the equilibrium actually depends on and predicts the rest with a model trained on every payoff measured so far. Standard error bounds for estimated games are driven by the worst-estimated payoff, so they cannot credit an estimator that is inaccurate only where accuracy does not matter. We prove a bound that weights payoff errors by the opponent's equilibrium strategy, a certificate that can be computed from simulated payoffs alone, and a condition under which errors in the predicted payoffs cannot change either player's regret. On three synthetic general-sum games, one of them a Colonel Blotto game of military resource allocation, the new bounds are four to six times tighter than the standard one, and RWPS finds less exploitable equilibria than minimum-regret-first search, information-gain search and progressive sampling at the same budget. On two cyber-defence simulators, CyGym and a new game whose hosts are LLM agents exposed to prompt injection, it gives the least exploitable equilibria at the smallest budgets.
Tags
Links
- Source: https://arxiv.org/abs/2609.19399v2
- Canonical: https://arxiv.org/abs/2609.19399v2
Trouble viewing inline? Open PDF directly →
Full Text
143,168 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 Game-theoretic analyses of cyber defence often compute equilibria of games whose payoffs exist only as the output of a simulator. Iterative equilibrium-finding methods grow a set of attacker and defender policies and need the payoff of every attacker–defender pair, so they are bottlenecked by payoff estimation: each payoff costs many simulator runs. We introduce Regret-Weighted Payoff Sampling (RWPS), which spends a fixed simulation budget on the payoffs the equilibrium actually depends on and predicts the rest with a model trained on every payoff measured so far. Standard error bounds for estimated games are driven by the worst-estimated payoff, so they cannot credit an estimator that is inaccurate only where accuracy does not matter. We prove a bound that weights payoff errors by the opponent’s equilibrium strategy, a certificate that can be computed from simulated payoffs alone, and a condition under which errors in the predicted payoffs cannot change either player’s regret. On three synthetic general-sum games, one of them a Colonel Blotto game of military resource allocation, the new bounds are four to six times tighter than the standard one, and RWPS finds less exploitable equilibria than minimum-regret-first search, information-gain search and progressive sampling at the same budget. On two cyber-defence simulators, CyGym and a new game whose hosts are LLM agents exposed to prompt injection, it gives the least exploitable equilibria at the smallest budgets. 1 Introduction Defending a network is a contest between two adaptive parties. An attacker probes for weaknesses and changes tactics when blocked; a defender allocates limited monitoring and response effort without seeing everything the attacker does. Game theory gives a principled way to plan against such an opponent: model the interaction as a game, compute an equilibrium, and deploy the defender’s equilibrium strategy, which no attacker strategy can exploit by more than the equilibrium’s exploitability. For realistic networks the game cannot be written down in closed form. What a pair of strategies is worth to each side is known only by simulating the network under both of them, which makes these simulation-based security games. A family of simulators now supports this work. The Cyber Operations Research Gym [37, 38] underpins the CAGE challenges, Yawning Titan [2], CyberBattleSim [22] and FARLAND [24] offer alternatives at different levels of abstraction, and CyGym [20] models cyber defence directly as a two-player general-sum game. Games of this size are usually solved by growing each player’s strategy set gradually. Policy-space response oracles (PSRO) [18] start from a few attacker and defender policies and repeat three steps. They estimate the payoff of every attacker–defender pair in the current sets, which gives a small matrix game; they solve that matrix game for a mixed equilibrium; and they train one new policy per player as a best response to the opponent’s current mixture, add it to the sets, and start again. The loop stops when neither new policy improves on the mixture, and MetaDOAR [19] scales the best-response step to large networks. The three steps cost very different amounts. A best response is a bounded reinforcement learning run. Solving the matrix game takes milliseconds with fictitious play [7] or a standard solver [31]. Estimating one payoff, however, means running the full simulator many times under both policies, and the matrix has nDnAn_Dn_A entries for pools of nDn_D defender and nAn_A attacker policies, so the simulation bill grows quadratically over a run. Simulation throughput is already a known bottleneck: CybORG++ [10] was built largely for speed and reports up to a thousandfold faster parallel execution. Faster simulators usually give up fidelity by abstracting host, process and packet detail [37, 24], and that detail is often the realism the analysis needed. We take the other route and keep the simulator, but call it less often. RWPS spends a fixed simulation budget on the payoffs that can change the equilibrium and predicts the others with a learned model. The model is trained on every payoff measured earlier in the run, so a simulation paid for in one iteration keeps helping in later ones. A score chooses which payoffs to simulate, favouring those the equilibrium depends on and the model is least sure of. The obvious worry is what this costs in equilibrium quality. The standard analysis of estimated games [39] bounds the damage by twice the largest payoff error over all entries. That bound is uninformative here, because RWPS is deliberately inaccurate on entries it judges irrelevant, and those are exactly the entries that set the largest error. Judging the method requires a bound that separates errors the equilibrium can feel from errors it cannot. Our contributions are as follows. 1. Bounds for estimated games that ignore irrelevant errors. We sharpen the bound of Tuyls et al. [39] so that a player’s regret depends only on payoff errors weighted by the opponent’s equilibrium strategy, and give a signed version in which only two kinds of error can hurt (Lemma 1). Once every strategy has been simulated against the opponent’s equilibrium strategies, a set of B∗=nDsA+nAsD−sDsAB =n_Ds_A+n_As_D-s_Ds_A entries, errors in the predicted entries cannot affect regret at all (Corollary 2). We also give a certificate computable from simulated payoffs alone (Corollary 1). On the estimator’s own output the new bounds are four to six times tighter than the standard one. 2. Regret-Weighted Payoff Sampling. RWPS predicts unsimulated payoffs with a model trained on every payoff measured so far, chooses what to simulate with a score built from bootstrapped equilibrium strategies, and keeps a small amount of random exploration, which the appendix shows is necessary. Inside PSRO it reaches lower exploitability than minimum-regret-first search, information-gain search [15] and progressive sampling at the same budget. The prediction model accounts for 62%62\% of the gain over random sampling and the score for the other 38%38\%, and with the model held fixed the score beats the sampling rule of Sokota et al. [35] on Colonel Blotto. 3. The Agentic Network Security Game. ANSG extends CyGym [20] to networks of LLM agents that an attacker can subvert through indirect prompt injection, with general-sum payoffs and partial observability on both sides. On CyGym and ANSG, RWPS reaches the lowest exploitability at the smallest budgets; on ANSG, without its score it needs four simulated payoffs to reach the level it otherwise reaches with one. 2 Related Work Several simulators target cyber defence. CybORG [37, 38] drives the CAGE challenges. Yawning Titan [2], CyberBattleSim [22] and FARLAND [24] model networks at different levels of fidelity, and CyGym [20] adds the game-theoretic layer this paper builds on. In all of them, evaluating a strategy pair means running the simulator, and that cost is a recognised obstacle. CybORG++ [10] reports up to a thousandfold parallel speedup from a lightweight re-implementation, built because large-scale evaluation on the original was infeasible. Our work is complementary to simulator engineering. We reduce the number of simulator calls the equilibrium computation needs, and the two approaches can be combined. The double-oracle method [21] and PSRO [18] grow strategy pools by best response to the current meta-game equilibrium. Later work improves oracle quality and diversity [5], and studies of the structure of these pools [9] describe what equilibrium supports look like in practice, which matters here because support size sets the cost in Corollary 2. MetaDOAR [19] scales the best-response step to large cyber networks. Little of this work addresses the evaluation step, where most of the cost lies in simulation-based games. Our theory refines a known result. Tuyls et al. [40], Tuyls et al. [39] prove that a Nash equilibrium of an estimated meta-game is a 2τ2τ-approximate equilibrium of the true game, where τ is the largest payoff error. Lemma 1 replaces that largest error with one weighted by the opponent’s equilibrium strategy, so the bound stays informative for an estimator that leaves irrelevant cells inaccurate on purpose. Rowland et al. [30] allocate samples for evaluation under incomplete information, mainly for α-rank [27] response graphs, using bandit rules without a surrogate that generalises across cells. Query-efficient EGTA methods reduce the same cost by pruning profiles instead of predicting them. Progressive-sampling algorithms sample profiles in rounds and stop sampling a profile once its confidence interval shows it cannot affect the learning goal [4, 3, 8, 23]. Our method instead solves a matrix in which every cell is present, either simulated or predicted. The two guarantees promise different things. A uniform guarantee covers the whole estimated matrix, so any equilibrium computed from it is approximately correct, but it exists only after every surviving profile has been sampled to accuracy ε . Our certificate covers only the equilibrium actually returned and says nothing about cells we did not simulate, but it can be computed from whatever has been simulated so far. At the budgets we target, progressive sampling cannot prune a single profile and gives no guarantee (Section 6.1), while our certificate is available at every budget and tightens as more cells are simulated. Wellman et al. [45] still describe MRFS-style heuristic search as the practical option when exhaustive evaluation is infeasible, so we treat it as a live baseline. We compare against both algorithms of Jordan et al. [15] and reach lower exploitability than both in a growing pool (Section 6.1). Neither carries information between iterations beyond its cache, while our surrogate trains on every cell bought in every earlier iteration, so our advantage grows over a run. On a fixed pool, where there is no such history, MRFS is stronger at low budgets. On the model-learning side, Wang et al. [44] pair double oracle with a learned game model and regularisation for sample efficiency, although for mean-field games and without an explicit payoff matrix, and Wang et al. [43] study which strategies to add to a pool, a question separate from which profiles to evaluate. Earlier work learns payoff or deviation-payoff functions over strategy spaces [41, 35] within EGTA [46, 42]. Sokota et al. [35] pair a learned deviation-payoff model with sampling around candidate equilibria, which is the idea closest to ours, but they build no payoff table and give no bound. Picheny et al. [28] 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 [30, 29] target a different solution concept. Active learning [33, 34] and deep ensembles [17] provide our acquisition and uncertainty tools. The appendix compares each of these 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 have no analytical form. 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, because the two players value the same outcome differently. 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, a pair of 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)=maxmaxi(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. PSRO solves the full game by repeating three operations. It solves the current restricted game for (p,q)(p,q), trains a best response to each opponent mixture with a reinforcement-learning oracle and adds it to the pool, and then extends 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. This paper addresses 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, the goal is to 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 put in the others. PSRO / MetaDOAR iteration tφ(di)=[⋅] (d_i)=[\,·\,·\,·\,]φ(aj)=[⋅] (a_j)=[\,·\,·\,·\,]strategy embeddingsensemblesurrogateu^ij,σ^ij u_ij,\ σ_ij.62.62.31.31.45.45.18.18.52.52.37.37.29.29.44.44.21.21payoff matrix D Dbootstrapre-solvesp~,q~ p,\ qmarginals,ν-smoothedscores p~iq~jσ^ij p_i q_j σ_ijsimulatorfillresample and re-solvebuy, p=1−εxp=1- _xrandom, p=εxp= _xmeasuredvaluecache and surrogateto iteration t+1t+1 Figure 1: One acquisition round at PSRO / MetaDOAR iteration t. Embeddings feed an ensemble surrogate that fills every uncached entry of D D (italic) beside the measured ones (grey). Re-solving bootstrap realizations of the filled matrix gives equilibrium marginals, mixed toward uniform at rate ν; each uncached cell is scored by its marginal weight times the surrogate’s uncertainty, the top-scoring cell is simulated, and its value joins the cache carried into iteration t+1t+1. 3.2 The budgeted estimator Algorithm 1 gives the full procedure. It has four steps, explained below in order: embed each strategy, fit a surrogate, score cells by their influence on the equilibrium, and simulate the top-scoring cells with some forced exploration, which the appendix shows is necessary. We call this Regret-Weighted Payoff Sampling (RWPS), because the budget goes to cells in proportion to their estimated influence on equilibrium regret, measured through smoothed bootstrap marginals. The method has two separable parts, the history-trained fill and the acquisition score. Section 6.3 measures each. The fill accounts for most of the gain, 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)← embedding of every s∈SD∪SAs∈ S_D∪ S_A ⊳ no rollouts 3: B←B−|(i,j)∈|B← B-|\(i,j) \| if B is a coverage target ⊳ spend only on the uncovered remainder 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 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))← Nash solver on the realization 10: end for 11: p¯i←meanbpi(b) p_i _b\,p^(b)_i; q¯j←meanbqj(b) q_j _b\,q^(b)_j ⊳ product of marginals 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 ⊳ necessary; see appendix 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) First, each strategy receives an embedding φ(s)∈ℝd (s) ^d computed without simulation. RWPS requires only that φ distinguish the strategies in the pool. For policies with an actor μπ _π, a natural choice is a behavioural fingerprint over a fixed probe bank Ξ=ξ1,…,ξP =\ _1,…, _P\ of states, φ(π)=[meanpμπ(ξp)∥stdpμπ(ξp)], (π)= [mean_p _π( _p)\,\|\,std_p _π( _p) ], (2) at the cost of P forward passes. The simplest choice is an identity tag, a one-hot vector per strategy, which carries no behavioural information. Section 5 states the embedding used in each experiment. Second, an ensemble of M small networks is fit to map embedding pairs to payoff pairs, each on a bootstrap resample of every entry ever simulated, so a payoff bought at one PSRO iteration still trains the surrogate at the next. Queries return the mean u^ij u_ij and disagreement σ^ij σ_ij. Cached entries override surrogate values, and a rank-one row-and-column model stands in until enough labels exist. Third, each unsimulated cell is scored by how much the equilibrium uses it, times how uncertain the surrogate is about it. We weight by equilibrium use because only those cells can change the answer. By Lemma 1, a player’s regret depends on payoff errors only through the opponent’s equilibrium mixture, and with the support held fixed a change to cell (i,j)(i,j) moves the defender’s value p⊤Dqp Dq by piqjp_iq_j times that change. A cell that no equilibrium strategy uses cannot affect the solution however uncertain it is, so scoring by uncertainty alone wastes budget. The weights depend on the unknown equilibrium, but re-solving is nearly free, so we estimate it by re-solving BbootB_boot bootstrap realizations of the game, each with a resampled pool and a matrix realization drawn from the surrogate’s predictive distribution. Weighting by piqjp_iq_j from a single solve would score only cells whose strategies that solve already plays, so an error in the estimated support would never be corrected. We make two choices so that cells outside the estimated support can also be scored. First, we average each player’s mixture across the bootstrap replicates and then multiply, p¯iq¯j p_i q_j, instead of averaging the product within each replicate. If one replicate plays d1d_1 against a1a_1 and another plays d2d_2 against a2a_2, averaging the products scores only those two cells, while multiplying the averages also scores the cross pairs (d1,a2)(d_1,a_2) and (d2,a1)(d_2,a_1). Those are the cells that matter when the replicates disagree about the support. Second, each averaged mixture is blended with uniform, p~=(1−ν)p¯+ν/|SD| p=(1-ν) p+ν/|S_D|, with a hyperparameter ν, so every strategy keeps some weight even when all replicates agree and are wrong. Setting ν=0ν=0 and averaging the products instead recovers value-sensitivity weighting, reported as an ablation in the appendix. Finally, cells are simulated one selection at a time. With probability 1−εx1- _x the highest-scoring unsimulated cell is bought, and with probability εx _x a cell chosen uniformly at random is bought instead. The random purchases are needed because the surrogate cannot know where it is wrong on cells it has never simulated. Two strategies can share an embedding while differing arbitrarily in payoff, so any rule that consults only the embedding and the cache can miss the cell that matters, as the appendix proves. 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. The appendix gives further implementation details, such as when the surrogate is refit, and all 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. [40], Tuyls et al. [39]. 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. That bound is too loose for a budgeted estimator. Our estimator leaves irrelevant cells inaccurate on purpose, so τ is set by the cells that do not matter, and the bound is correspondingly weak (Section 6). In this section we let the equilibrium determine which errors count, strengthening the bound step by step from a two-sided worst case to a signed bound that can be computed from the data the estimator already holds. Proofs of the two results below are given here; the remaining proofs, and fuller versions of these, are in the appendix. 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). 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. Proof. 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^)ie_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^≤τD(q^) p _D q≤ _D( q) gives the defender’s bound; the attacker’s is symmetric, and no zero-sum structure is used. Each row of |ΔD|q^| _D| q is a q q-weighted average of entries bounded by τ, so τD(q^)≤τ _D( q)≤τ: columns outside supp(q^)supp( q) contribute nothing however large their error. The signed form follows by dropping absolute values and keeping only the two harmful directions. Appendix A.1 gives the step-by-step version. ∎ The chain contains four bounds.11 1 The bound constrains ΔD _D, not its origin, so it also covers irrational players and model misspecification. We do not consider either here. Throughout, ΔD _D is sampling and surrogate error. Form (d) is the sup-norm bound of Tuyls et al. [40], Tuyls et al. [39], 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 allows an optimistic fill. The solver term εsolve _solve is computable without ground truth, since it is 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 β (from regression error, an uninformative embedding, or both; we do not certify β in advance and instead measure it in Section 6). Which cells are simulated, and how often, is chosen by the acquisition rule from earlier samples, so the design is adaptive. A fixed-design union bound would be optimistic under adaptive selection. We therefore state the statistical term with a time-uniform concentration bound [14], valid simultaneously for all cells and all stopping times, at the cost of a loglog factor in the visit count. The guarantee below then holds however 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/δ)+loglog2(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). Proof. Split (|ΔD|q^)i(| _D| q)_i over the 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 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 that row i places on surrogate cells, which is wsur(q^)w_sur( q). Take the maximum over rows, apply Lemma 1, and repeat for the attacker; Appendix A.1 expands each step. ∎ The theorem tells acquisition what to aim for, which is to drive wsurw_sur to zero. Representational error enters in proportion to how much equilibrium mass touches surrogate cells, where the sup-norm bound charges it at full strength. A surrogate cell in a column the opponent never plays costs nothing, while one in a played column costs in proportion to that column’s weight. RWPS therefore scores cells by equilibrium sensitivity as well as uncertainty. The weight q~j q_j is zero on the columns that cannot make wsurw_sur positive, and largest on those that dominate it. Computing wsurw_sur needs only a cache query against the returned mixture, so we can check directly whether it has reached zero, and Appendix A.8 builds a terminating coverage iteration on it. Once it vanishes the bound keeps only its statistical term, which Appendix A.3.2 inverts into the budget a target exploitability requires. 4.3 An optimistic certificate Only two events produce regret. The estimate can understate a deviation row, or it can overstate the value of the support. Filling unsimulated cells of a player’s own matrix at the maximum payoff therefore understates no deviation, which makes the following bound computable without the true matrices. Its proof, like those of the other results in this section, is in Appendix A.1. Corollary 1 (Computable optimistic certificate). Let (p^,q^)( p, q) be an εsolve _solve-approximate equilibrium of estimated matrices (D^,A^)( D, A) whose support block supp(p^)×supp(q^)supp( p)×supp( q) is simulated, 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. Every quantity on the right is available at the end of a build. The deviation terms use (Dopt,Aopt)(D^opt,A^opt), the value terms use the estimated matrices (D^,A^)( D, A) the solver was given, and εsolve _solve is measured on those, so the true matrices never appear. The surrogate error β of Theorem 1 is the one quantity no data can bound, because it concerns cells never simulated. Covering the deviation-relevant set sets wsur=0w_sur=0 and removes it. 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 [46, 45] and underlies MRFS [15]. Setting sD=sA=1s_D=s_A=1 recovers its 2n−12n-1 confirmation set. We add the closed-form bimatrix count and the link to Theorem 1. In earlier methods the cells outside the deviation set are never evaluated. Here they are filled by a surrogate the solver reads, and the corollary shows that the fill cannot reach either player’s regret, which is why predicting unsimulated payoffs is safe where earlier work pruned them. Because the supports it needs are estimated by re-solving bootstrap samples of the game, without any rollouts, B∗B also works as a screen before any simulation. A small B∗B says the estimator is worth enabling, and a B∗B close to nDnAn_Dn_A says a full rebuild is the better option. The appendix prices a target certificate from B∗B and gives the extended discussion. Exploration is necessary for the asymptotic guarantee. An embedding is a finite summary, so two policies can share one while differing arbitrarily in payoff, and any deterministic acquisition rule that reads only embeddings and the cache can be led never to simulate the cell that matters, as the appendix proves. The uniform draws of Algorithm 1 are the only mechanism that does not consult the embedding. 5 Experimental Setup The experiments ask whether the estimator finds better equilibria than other budgeted payoff builds inside growing-pool PSRO (Section 6.1), whether that holds on cyber simulators (Section 6.2), and whether the bounds of Section 4 are tight enough to be worth computing (Section 6.4). On the latent-quality games and Blotto, exploitability is measured against the true, computable Nash equilibrium. On CyGym and ANSG no such equilibrium is available, which is why RWPS is needed there in the first place, so we measure exploitability against a full rebuild of a fixed pool instead. 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. 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. Equilibrium supports are (2,2)(2,2), so B∗=80B =80 cells, 18%18\%. Two embeddings share these payoffs: an informative one, [q,tanhq,q2,sinq][q, q,q^2, q], which makes payoff smooth in φ , and an arbitrary one drawn independently of q, which ablates the embedding (appendix). 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, or 82%82\%, and the theory predicts before any run that this game is expensive. CyGym and ANSG. CyGym [20] 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, and 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 the appendix. In the CyGym and ANSG budget sweeps every strategy is embedded by an identity tag. 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: ε=maxmaxi(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 the appendix. 5.3 Baselines and protocol Uniform sampling spends the same budget uniformly at random with a mean fill; full rebuild simulates every cell, as standard PSRO does. We additionally compare against minimum-regret-first search and information-gain search [15] and the progressive-sampling family (Section 6.1). The latter shows that a uniform ε -approximation guarantee cannot be bought at these budgets. Restricted games are solved by fictitious play on the synthetic games and on CyGym and ANSG by support enumeration with a Lemke–Howson fallback. The solver’s residual regret enters every bound as εsolve _solve. The growing-pool comparison uses a 5%5\% per-build budget over twelve iterations with pools growing from three to fourteen per side, sixteen 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. The τ-statistics are maxima over 441441 cells and therefore heavy-tailed, so we report medians. 6 Results All aggregates are mean ± one standard deviation over sixteen seeds unless a caption states otherwise. Every method in a comparison starts from the same pool. 6.1 Exploitability over PSRO Rounds for Synthetic Games 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. Figure 2: 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, and every budgeted method is held to the same 256256. The full rebuild has no budget. It simulates every uncached cell, costing 784784 episodes by iteration twelve, and is shown as a quality reference. 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 uniform (flat fill) 0.2080.208 0.113±0.0970.113 ±0.097 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 uniform (flat fill) 0.5930.593 0.293±0.1400.293 ±0.140 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 gap between methods builds up over the run. Figure 2 plots the same runs iteration by iteration. All methods begin together, separate over the first four iterations, and keep their ordering after that. 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 informative game and p<0.001p<0.001 on Blotto, and against uniform, p=0.003p=0.003 and p<0.001p<0.001. RWPS starts behind at iteration 00 (0.2620.262 against 0.1800.180 for MRFS), as expected with an empty cache, and its lead then widens every iteration, which is what reusing earlier simulations should produce. Against the full rebuild the result divides by game. On the informative game 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. On Blotto the rebuild is ahead, at 0.0450.045 against 0.0820.082 (p=0.004p=0.004). IGS and the progressive-sampling family trail because both need more samples per profile than the budget affords. A 5%5\% budget is ten cell evaluations at a 14×1414× 14 pool, against the 294294 per cell that PSP’s published schedule requires. The family matches RWPS only at about 100×100× the full matrix, where PS-REG-M first prunes (Table 2), a budget that defeats the purpose of estimating payoffs when every cell is a simulator rollout. Table 2: RWPS against the progressive-sampling family on fixed 21×2121× 21 pools, exploitability mean ± SD over four seeds at budgets that are multiples of the matrix. Bold marks each row’s best. The last column is the share of utility indices PS-REG-M prunes, and the appendix gives all five budgets. Game Budget RWPS GS PSP PS-REG-M pruned Inf. 1×1× .029±.023.029±.023 .162±.138.162 ±.138 .222±.081.222 ±.081 .214±.106.214 ±.106 00 20×20× .012±.006.012±.006 .413±.125.413 ±.125 .156±.298.156 ±.298 .029±.050.029 ±.050 00 100×100× .007±.003.007 ±.003 .025±.040.025 ±.040 .005±.003.005 ±.003 .003±.002.003±.002 0.5%0.5\% Blotto 1×1× .043±.011.043±.011 .475±.029.475 ±.029 .471±.026.471 ±.026 .617±.268.617 ±.268 00 20×20× .025±.004.025±.004 .561±.081.561 ±.081 .366±.081.366 ±.081 .404±.049.404 ±.049 00 100×100× .015±.003.015 ±.003 .440±.035.440 ±.035 .013±.001.013±.001 .017±.007.017 ±.007 6.1%6.1\% 6.2 Budget sweeps on Cybersecurity Games On both simulators RWPS reaches the lowest exploitability at the smallest budgets, and the other arms close the gap only as the budget grows (Figures 3 and 4). Uniform sampling and MRFS need most of the available cells to reach the same floor, which RWPS reaches with its first purchase. IGS stays above it throughout, and the progressive-sampling family buys nothing at any budget shown. RWPS leads from the first purchase because every arm starts from the same pre-cached history but only RWPS learns from it, predicting every unbought cell and buying where the equilibrium is sensitive and that prediction is least certain. 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 well above the floor at budgets 1–3 and reaches it only at budget 4, three purchases after RWPS (adaptive), so the score makes the first few purchases count. This is the cleanest test of the score in the paper, because ANSG keeps every RWPS arm on the rank-one fill and the two variants differ only in which cells they buy. The appendix reports the same sweep on Cyberwheel [26], where the pool is flat and every buying arm ties. Figure 3: 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 because its sampling schedule requires more samples per cell than the budget affords, so it returns the history-only estimate. Figure 4: ANSG budget sweep. 7×77× 7 pool with a 6×66× 6 history pre-cached for every arm, leaving 1313 cells to buy, over 1616 seeds. Exploitability is computed exactly against the fully simulated matrix of this pool, 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 because 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, 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. Here we fix the surrogate, budget, batch schedule and exploration rate and vary only the acquisition score, on the same sixteen paired seeds, so any difference between rows is due to acquisition alone. Uniform here keeps the surrogate fill, while Table 1’s replaces it 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 informative game 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. Table 3: Acquisition comparison. All rules share the surrogate, budget, batches and exploration rate and differ only in the score. Mean ± one standard error of ε12 _12 over sixteen paired seeds. Uncertainty sampling scores by surrogate disagreement alone [33, 36], and uniform selection keeps the fill but drops the score. The appendix reports three further variants. Acquisition score Informative Blotto ν-smoothed product (ours) 0.024±0.0040.024± 0.004 0.082±0.0110.082± 0.011 Sokota et al. [35] 0.032±0.0040.032 ±0.004 0.120±0.0110.120 ±0.011 uncertainty (σ σ only) 0.040±0.0070.040 ±0.007 0.116±0.0130.116 ±0.013 uniform selection 0.058±0.0160.058 ±0.016 0.162±0.0190.162 ±0.019 The smoothed rule is first on both games. On Blotto it beats Sokota et al. [35] by 0.0380.038 under 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 informative game its 0.0080.008 lead is not significant (p=0.224p=0.224), which we report as a tie. Uncertainty sampling beats uniform selection on both games but loses to the full rule (p=0.021p=0.021 on Blotto, p=0.062p=0.062 on the informative game). Disagreement shows where the fill is wrong, but a highly uncertain cell can still be irrelevant if no equilibrium strategy plays it. The appendix sweeps ν, εx _x and the bootstrap sizes. 6.4 Regret Bound Analysis Figure 5: 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 ε . Errors off the equilibrium support do not affect regret, and the estimator’s own output confirms it. Over all 240240 budget-sweep runs every bound holds on every run (Figure 5). 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 puts its error on cells no equilibrium strategy plays, those cells set the sup-norm bound, and the support weighting ignores them. The solver term is needed, since without it the signed bound fails on three Blotto runs, each by less than that run’s solver regret. These bounds are diagnostics and cannot be deployed as certificates. Each form of Eq. (3) contains D^−D D-D, so these builds use a fixed-pool bed where the true matrix is available. The appendix gives per-game factors and the deployable certificate. 7 Conclusion In simulation-based security games the expensive step is measuring payoffs, and most of those measurements can be avoided. On a 5%5\% per-build budget RWPS found less exploitable equilibria than every other budgeted method we tested, and did best at the smallest budgets on CyGym and ANSG. Our bounds are four to six times tighter than the standard one and need no access to the true payoffs, so an analyst can state how exploitable a computed defence is without ever simulating the full game. Together these make equilibrium analysis affordable at the simulator fidelity the analysis calls for, including on new threat models such as networks of LLM agents. References [1] A. Al-Dujaili, E. Hemberg, and U. O’Reilly (2018) Approximating Nash equilibria for black-box games: a Bayesian optimization approach. In Workshop on Optimization in Multiagent Systems (OptMAS), External Links: Link Cited by: §A.3.1. [2] 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: §A.3.6, §1, §2. [3] 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. [4] 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. [5] 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. [6] 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: §A.3.2. [7] G. W. Brown (1951) Iterative solution of games by fictitious play. Activity Analysis of Production and Allocation. Cited by: §1. [8] 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. [9] 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. [10] 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. [11] K. Hammar and R. Stadler (2020) Finding effective security strategies through reinforcement learning and self-play. In Proceedings of the 16th International Conference on Network and Service Management (CNSM), p. 1–9. Cited by: §A.3.6. [12] K. Hammar (2026) CSLE: a reinforcement learning platform for autonomous security management. In Proceedings of the Ninth Annual Conference on Machine Learning and Systems (MLSys), Cited by: §A.3.6. [13] M. Han, F. Zhang, and Y. Chen (2024) No-regret learning of Nash equilibrium for black-box games via Gaussian processes. In Proceedings of the 40th Conference on Uncertainty in Artificial Intelligence (UAI), External Links: Link Cited by: §A.3.1. [14] 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: §A.1, §4.2. [15] 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.2, §A.3.5, item 2, §2, §4.3, §5.3. [16] T. Kunz, C. Fisher, J. La Novara-Gsell, C. Nguyen, and L. Li (2022) A multiagent CyberBattleSim for RL cyber operation agents. In Proceedings of the International Conference on Computational Science and Computational Intelligence (CSCI), p. 897–903. Cited by: §A.3.6. [17] 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. [18] 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. [19] M. Lanier and Y. Vorobeychik (2026) A scalable approach to solving simulation-based network security games. In Proceedings of FLAIRS, Cited by: §1, §2. [20] 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.3.6, §A.4, item 3, §1, §2, §5.1. [21] 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. [22] Microsoft Defender Research Team (2021) CyberBattleSim. Note: https://github.com/microsoft/cyberbattlesim Cited by: §A.3.6, §1, §2. [23] B. Mishra, C. Cousins, and A. Greenwald (2022) Regret pruning for learning equilibria in simulation-based games. Note: arXiv preprint arXiv:2211.16670 Cited by: §2. [24] 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. [25] A. A. Nguyen and M. P. Wellman (2026) Conservative equilibrium discovery in offline game-theoretic multiagent reinforcement learning. In Proceedings of the 25th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), External Links: Link Cited by: §A.3.1. [26] 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.3.6, §A.5, §6.2. [27] 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. [28] V. Picheny, M. Binois, and A. Habbal (2019) A Bayesian optimization approach to find Nash equilibria. Journal of Global Optimization 73 (1), p. 171–192. External Links: Document Cited by: §A.3.1, §A.3.1, §A.9.3, §2. [29] 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. [30] 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. [31] R. Savani and T. L. Turocy (2025) Gambit: the package for computation in game theory, version 16.2.1. Note: https://w.gambit-project.org Cited by: §1. [32] J. Schwartz and H. Kurniawati (2019) Autonomous penetration testing using reinforcement learning. Note: arXiv:1905.05965 Cited by: §A.3.6. [33] 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 3. [34] 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. [35] 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, item 2, §2, §2, §6.3, Table 3. [36] 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: Table 3. [37] 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: §A.3.6, §1, §1, §2. [38] TTCP CAGE Working Group (2022) Cyber operations research gym. Note: https://github.com/cage-challenge/CybORG Cited by: §A.3.6, §1, §2. [39] 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. [40] 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. [41] 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. [42] 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. [43] Y. Wang, Q. Ma, 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. [44] 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. [45] 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.2, §2, §4.3. [46] M. P. Wellman (2006) Methods for empirical game-theoretic analysis. Proceedings of the AAAI Conference on Artificial Intelligence. Cited by: §A.3.2, §A.8, §2, §4.3. [47] 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.2. [48] 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.2, §A.8. Appendix A Appendix This appendix collects the proofs, the specification of the ANSG domain, implementation details and hyperparameters, and additional experiments. A.1 Proofs This appendix collects full proofs of the results in Section 4, in order of appearance. Throughout, rows index defender strategies d1,…,dnDd_1,…,d_n_D and columns attacker strategies a1,…,anAa_1,…,a_n_A; D,D^∈ℝnD×nAD, D ^n_D× n_A hold the defender’s true and estimated payoffs, and A,A^∈ℝnA×nDA, A ^n_A× n_D the attacker’s, indexed attacker-first. For a mixed profile (p,q)(p,q) the defender’s regret in a matrix M is regD(p,q,M)=maxiei⊤Mq−p⊤Mq,reg_D(p,q;M)\;=\; _i\,e_i Mq\;-\;p Mq, and symmetrically regA(p,q,N)=maxjej⊤Np−q⊤Npreg_A(p,q;N)= _je_j Np-q Np for the attacker. A profile is an ε -Nash equilibrium of (D,A)(D,A) when both regrets are at most ε , and its exploitability is ε=maxregD,regA = \reg_D,reg_A\. That (p^,q^)( p, q) is an εsolve _solve-approximate equilibrium of (D^,A^)( D, A) means maxiei⊤D^q^≤p^⊤D^q^+εsolve,maxjej⊤A^p^≤q^⊤A^p^+εsolve. _ie_i D q\;≤\; p D q+ _solve, _je_j A p\;≤\; q A p+ _solve. (5) Write ΔD=D^−D _D= D-D and ΔA=A^−A _A= A-A, and |⋅||·| for the entrywise absolute value. Proof of Lemma 1. We prove the four links of Eq. (3) for the defender in turn, then the attacker’s analogue and the consequence for ε . We begin with form (a). Fix a pure deviation i. Since D^=D+ΔD D=D+ _D, ei⊤Dq^=ei⊤D^q^−ei⊤ΔDq^.e_i D q\;=\;e_i D q-e_i _D q. By Eq. (5), ei⊤D^q^≤p^⊤D^q^+εsolvee_i D q≤ p D q+ _solve, and expanding D D once more, p^⊤D^q^=p^⊤Dq^+p^⊤ΔDq p D q= p D q+ p _D q. Combining, ei⊤Dq^−p^⊤Dq^≤εsolve+p^⊤ΔDq^+(−ΔDq^)i.e_i D q- p D q\;≤\; _solve+ p _D q+ (- _D q )_i. The right-hand side depends on i only through the last term, so taking the maximum over i on both sides gives regD−εsolve≤maxi(−ΔDq^)i+p^⊤ΔDq^reg_D- _solve≤ _i(- _D q)_i+ p _D q, which is (a). No property of the game other than bilinearity has been used; in particular the argument does not assume zero sum. To pass from (a) to (b), we bound the two terms separately. For every row i, (−ΔDq^)i=∑jq^j(−ΔD,ij)≤∑jq^j|ΔD,ij|=(|ΔD|q^)i(- _D q)_i= _j q_j(- _D,ij)≤ _j q_j| _D,ij|=(| _D| q)_i, because q^j≥0 q_j≥ 0 and −x≤|x|-x≤|x|; taking the maximum over i gives maxi(−ΔDq^)i≤τD(q^) _i(- _D q)_i≤ _D( q). Likewise p^⊤ΔDq^=∑i,jp^iq^jΔD,ij≤∑i,jp^iq^j|ΔD,ij|=p^⊤|ΔD|q p _D q= _i,j p_i q_j _D,ij≤ _i,j p_i q_j| _D,ij|= p | _D| q, since all weights are non-negative. To pass from (b) to (c), write p^⊤|ΔD|q^=∑ip^i(|ΔD|q^)i p | _D| q= _i p_i(| _D| q)_i. This is a convex combination of the numbers (|ΔD|q^)i(| _D| q)_i, since p p is a probability vector, and a convex combination never exceeds its largest element. Hence p^⊤|ΔD|q^≤maxi(|ΔD|q^)i=τD(q^) p | _D| q≤ _i(| _D| q)_i= _D( q), and (b) ≤2τD(q^)≤ 2 _D( q). Finally, for (c) to (d), note that for every row, (|ΔD|q^)i=∑jq^j|ΔD,ij|≤‖ΔD‖∞∑jq^j=‖ΔD‖∞≤τ(| _D| q)_i= _j q_j| _D,ij|≤\| _D\|_∞ _j q_j=\| _D\|_∞≤τ, so τD(q^)≤τ _D( q)≤τ. The sum ranges only over j∈supp(q^)j ( q): an entry in a column of zero mass contributes nothing, however large. For the equality condition, suppose τD(q^)=τ _D( q)=τ. Then some row i attains ∑jq^j|ΔD,ij|=τ _j q_j| _D,ij|=τ; since each term satisfies |ΔD,ij|≤τ| _D,ij|≤τ and the weights sum to one, this forces |ΔD,ij|=τ| _D,ij|=τ for every j with q^j>0 q_j>0. So a worst-error cell lies in a played column, which is the stated necessary condition. The same argument covers the attacker, whose payoff to pure strategy j against p p is ej⊤Ap^e_j A p; the four steps apply with the roles exchanged: replace (D,D^,p^,q^,i)(D, D, p, q,i) by (A,A^,q^,p^,j)(A, A, q, p,j) and use the second inequality of Eq. (5). This gives the attacker’s chain with τA(p^)=maxj(|ΔA|p^)j _A( p)= _j(| _A| p)_j in place of τD(q^) _D( q); played rows now play the role of played columns. Each form bounds its player’s regret minus εsolve _solve. The exploitability is the larger of the two regrets, so it is at most εsolve _solve plus the larger of the two players’ values of whichever form is used, which makes (p^,q^)( p, q) an ε -Nash equilibrium of (D,A)(D,A) for that ε . ∎ Proof of Theorem 1. The argument has three steps: a confidence event under which every simulated entry is accurate, a split of each row’s weighted error on that event, and an application of Lemma 1. We first build a confidence event under which every simulated entry is accurate. Fix one payoff entry, say DijD_ij, and let X¯n X_n be the average of its first n rollouts, each equal to DijD_ij plus independent σ-sub-Gaussian noise. A stitched time-uniform boundary of the kind developed by Howard et al. [14] gives, for any δ′∈(0,1)δ ∈(0,1), Pr[ [\, ∃n≥1: ∃\,n≥ 1: |X¯n−Dij|>σ2(log(2/δ′)+loglog2(2n))n]≤δ′, | X_n-D_ij |>σ 2( (2/δ )+ _2(2n))n\, ]\;≤\;δ , where the factor 22 inside the logarithm accounts for the two tails. The guarantee holds for all n simultaneously, and therefore also at any random visit count, including one chosen by an acquisition rule on the basis of earlier samples; this is what makes it valid under adaptive sampling, where a fixed-n bound would not be. There are nDnAn_Dn_A entries in D and nDnAn_Dn_A in A. Setting δ′=δ/(2nDnA)δ =δ/(2n_Dn_A) and taking a union bound, the event ℰ: : |D^ij−Dij|≤ζ(mij,δ) and |A^ji−Aji|≤ζ(mij,δ) | D_ij-D_ij |≤ζ(m_ij,δ)\ and \ | A_ji-A_ji |≤ζ(m_ij,δ) for every simulated cell (i,j) every simulated cell (i,j) holds with probability at least 1−δ1-δ, where mijm_ij is the cell’s visit count and log(2/δ′)=log(4nDnA/δ) (2/δ )= (4n_Dn_A/δ) as in ζ. Finally, ζ(⋅,δ)ζ(·,δ) is non-increasing in the visit count: the numerator grows only doubly logarithmically, while the denominator grows linearly. Since every simulated cell has mij≥m_ij≥ m, on ℰE every simulated entry has error at most ζ(m,δ)ζ(m,δ). Next we split each row’s weighted error on that event. Fix a row i, and let SiS_i and UiU_i be the columns whose cells in that row are simulated and surrogate-filled, respectively. On ℰE, (|ΔD|q^)i (| _D| q)_i =∑j∈Siq^j|ΔD,ij|+∑j∈Uiq^j|ΔD,ij| = _j∈ S_i q_j| _D,ij|+ _j∈ U_i q_j| _D,ij| ≤ζ(m,δ)∑j∈Siq^j+β∑j∈Uiq^j, ≤ζ(m,δ) _j∈ S_i q_j\;+\;β _j∈ U_i q_j, using Step 1 on the first sum and the assumption that surrogate entries have absolute error at most β on the second. The first sum of weights is at most one. The second is the q q-mass row i places on surrogate cells, which is at most its maximum over rows, wsur(q^)w_sur( q). Hence (|ΔD|q^)i≤ζ(m,δ)+βwsur(q^)(| _D| q)_i≤ζ(m,δ)+β\,w_sur( q) for every i, and taking the maximum, τD(q^)≤ζ(m,δ)+βwsur(q^) _D( q)≤ζ(m,δ)+β\,w_sur( q). The attacker’s version, τA(p^)≤ζ(m,δ)+βwsur(p^) _A( p)≤ζ(m,δ)+β\,w_sur( p), follows in the same way over the attacker’s rows. It remains to apply Lemma 1. Form (c) of Lemma 1 gives regD≤εsolve+2τD(q^)reg_D≤ _solve+2 _D( q) and regA≤εsolve+2τA(p^)reg_A≤ _solve+2 _A( p). Substituting Step 2 and taking the larger of the two regrets yields the stated bound on ε , on the event ℰE of probability at least 1−δ1-δ. Because ℰE was built to hold at every visit count, the bound holds for whatever cells and visit counts the acquisition rule chose. ∎ Proof of Corollary 1. Work on the event ℰE of the previous proof, which has probability at least 1−δ1-δ, and consider the defender; the attacker is symmetric. We first bound the best deviation from above, and claim that D≤Dopt+ζm,δD≤ D^opt+ _m,δ entrywise. On a simulated cell, DijoptD^opt_ij is the measured mean, which on ℰE is within ζm,δ _m,δ of DijD_ij. On an unsimulated cell, DijoptD^opt_ij is the maximum payoff, which bounds DijD_ij by definition. Since q^≥0 q≥ 0 and sums to one, it follows that for every i, ei⊤Dq^≤ei⊤Doptq^+ζm,δe_i D q≤ e_i D^opt q+ _m,δ, and so maxiei⊤Dq^≤maxi(Doptq^)i+ζm,δ _ie_i D q≤ _i(D^opt q)_i+ _m,δ. Next we bound the equilibrium value from below. The value term needs the matrix the solver was given to be accurate where the equilibrium plays, that is, on the support block supp(p^)×supp(q^)supp( p)×supp( q). When that block is simulated, every term of p^⊤D^q^=∑i,jp^iq^jD^ij p D q= _i,j p_i q_j D_ij with non-zero weight is a measured mean, so on ℰE, p^⊤Dq^≥p^⊤D^q^−ζm,δ p D q≥ p D q- _m,δ. Subtracting the second bound from the first, regD=maxiei⊤Dq^−p^⊤Dq^≤maxi(Doptq^)i−p^⊤D^q^+2ζm,δreg_D= _ie_i D q- p D q≤ _i(D^opt q)_i- p D q+2 _m,δ, which is at most the stated bound; the εsolve _solve term is slack and is kept only so that the certificate dominates Theorem 1 term by term. The same argument with AoptA^opt and the rows of supp(p^)supp( p) bounds regAreg_A, and the exploitability is the larger of the two. The condition on the support block cannot simply be dropped. If some support cell is surrogate-filled, the value term can overstate p^⊤Dq p D q by up to β times its weight, and that error is not visible in the data. Replacing D D in the value term by a pessimistic fill, measured values on simulated cells and the minimum payoff elsewhere, restores the bound without any condition, at the price of a looser value term. ∎ Proof of Corollary 2. We first show that both multipliers vanish. By definition, wsur(q^)=max∑jiq^j 1[(i,j) surrogate],w_sur( q)= _i _j q_j\,1[(i,j) surrogate], and only columns j∈supp(q^)j ( q) carry weight. The hypothesis says that every cell in those columns is simulated, in every row, so for each row the sum has no non-zero term and wsur(q^)=0w_sur( q)=0. The same argument over the rows of supp(p^)supp( p) gives wsur(p^)=0w_sur( p)=0. Substituting wsur=0w_sur=0 into Theorem 1 removes the term βwsurβ\,w_sur for both players, leaving ε≤εsolve+2ζ(m,δ) ≤ _solve+2ζ(m,δ). Since β appears only in the removed term, the bound holds whatever the surrogate’s error. It remains to count the cells. The set is the union of C=1:nD×supp(q^)C=\1:n_D\×supp( q), with nDsAn_Ds_A cells, and R=supp(p^)×1:nAR=supp( p)×\1:n_A\, with nAsDn_As_D cells. Their intersection is supp(p^)×supp(q^)supp( p)×supp( q), with sDsAs_Ds_A cells, so by inclusion and exclusion |C∪R|=nDsA+nAsD−sDsA=B∗|C∪ R|=n_Ds_A+n_As_D-s_Ds_A=B . ∎ 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 loglog2(2m) _2(2m) term, which is o(logm)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 loglog 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/δ)+loglog2(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 the ratio inside the root tends to 00 by L’Hôpital’s rule on the ∞/∞/∞ form. The loglog 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. We argue by induction over rounds. In the base case, before any cell is simulated, both runs hold the empty cache and the same fingerprints, since φ(atrap)=φ(atwin)=φ(a⋆) (a_trap)= (a_twin)= (a_ ) and φ is a function of the actor alone, not of payoffs; the two runs therefore agree at round 11. For the inductive hypothesis, 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 there, so the runs agree through round r+1r+1. By induction, A selects the same cells on I0I_0 and I1I_1 at every round. 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 gives the longer treatment of three topics the main text summarises: how RWPS relates to prior payoff-estimation and equilibrium-search methods, what the coverage result adds to known EGTA principles and how it prices a certificate, and further detail on the growing-pool PSRO comparison. Throughout, RWPS is the budgeted estimator of Algorithm 1: it simulates a subset of payoff cells, fills the rest with an ensemble surrogate over strategy embeddings, and chooses cells by a score built from bootstrap equilibrium marginals. The deviation-relevant set is the set of cells pairing every strategy of one player with each strategy in the support of the other player’s equilibrium mixture. A.3.1 Relation to prior payoff-estimation methods GS, PSP and PS-REG-M allocate samples so that a uniform ε -approximation guarantee holds over every cell, pruning profiles once their bounds separate. We run all three with the sampling schedules from their published works. At the budgets RWPS targets that guarantee cannot be bought: PSP’s published schedule begins at 294294 samples per cell, whereas a 5%5\% per-build budget on a 14×1414× 14 pool affords ten cell evaluations in total. None of the three methods therefore prunes a single profile, and all return the history-only estimate. This reflects the operating regime, not a flaw in those algorithms, which are designed for budgets that cover the matrix many times over. Sokota et al. [35] also pair a learned model with an acquisition rule defined at the level of the solution. They train a network mapping mixed profiles to deviation payoffs and refine it by sampling in the neighbourhood of each candidate equilibrium. Three differences separate their setting from ours. Their model takes a mixture as input and returns deviation payoffs directly, so no payoff table is built, whereas RWPS estimates individual cells over strategy embeddings and passes the completed matrix to a solver. They exploit role symmetry to scale in the number of players, while our games are two-player, asymmetric, and have pools that grow by best response. And their refinement is validated empirically, with no bound on the resulting equilibrium, which is what Theorem 1 and Corollary 2 supply. Because their rule is a score over cells rather than a full payoff-build method, the fair comparison runs it inside an otherwise identical build, which is how Table 3 reports it. Choosing which expensive evaluation to run is the subject of active learning and Bayesian optimisation [33, 34], and deep ensembles [17] supply the per-cell uncertainty RWPS uses. Picheny et al. [28] apply Bayesian optimisation to Nash equilibrium computation in black-box games, 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; RWPS targets a finite pool that grows across PSRO iterations and reuses every simulated entry as training data. Both depart from standard Bayesian optimisation in the target: accuracy of the equilibrium of the whole matrix, not pointwise accuracy. RWPS measures uncertainty about that equilibrium by re-solving bootstrap realisations of the game, which is nearly free because solving is cheap next to simulating. Of their two acquisition criteria, probability of equilibrium has a discrete analogue, reported as the bootstrap-inclusion variant in Appendix A.9.3: a cell is scored by how often it enters a bootstrap support instead of by a Gaussian-process posterior. Stepwise uncertainty reduction does not carry over. It targets the probability that a cell is the equilibrium, which is defined for the pure equilibria of a discretised space but not for the mixed equilibria, with supports (2,2)(2,2) and (12,12)(12,12), that our games have. Extending it to mixed equilibria is open. Two lines extend Picheny et al. [28]. Al-Dujaili et al. [1] search for pure equilibria of continuous black-box games by Gaussian-process regression on an approximate regret surface, with an ε -greedy trade-off between exploiting that surface and reducing uncertainty. Han et al. [13] give ARISE, which restricts acquisition to a region of interest around the current equilibrium estimate and proves no-regret guarantees for the resulting query sequence. Both minimise a global regret functional over a continuous strategy space and query strategy profiles directly. RWPS instead completes a finite payoff matrix whose rows and columns are policies produced by PSRO, reuses every cell across iterations, and certifies the equilibrium of the completed matrix; ARISE’s region-of-interest restriction plays a role similar to our equilibrium weighting, and its no-regret analysis is over queries rather than over the returned mixture. Nguyen and Wellman [25] also face payoffs that cannot be freely simulated, but from the opposite direction: their dataset is fixed, so they replace the simulator with an ensemble dynamics model and steer best responses away from profiles the data does not support. Our setting keeps the simulator and rations calls to it, so uncertainty drives which cells to pay for rather than a conservatism penalty on responses. The two are complementary: a budgeted estimator decides what to simulate next, and a conservative response objective decides what to trust when nothing more can be simulated. Rowland et al. [30] maintain confidence intervals over payoffs until the response graph is determined, and Rashid et al. [29] choose each query to maximise information gain about α-rank. Neither optimises exploitability against a Nash mixture, so neither is run as a baseline. Information-gain acquisition is represented among the baselines through the IGS method of Jordan et al. [15]. A.3.2 Coverage, budgets and certificates That verifying a profile’s regret requires only the profile and its unilateral deviations is long established in empirical game-theoretic analysis (EGTA) [46]. Wellman et al. [45] state it directly and note that the count stays modest for mixed profiles with small supports; the same idea underlies minimum-regret-first search (MRFS) [15] and deviation-preserving reduction [48]. We do not claim the principle. Corollary 2 adds two things: a closed-form count, B∗=nDsA+nAsD−sDsAB =n_Ds_A+n_As_D-s_Ds_A cells for a bimatrix game with pool sizes nD,nAn_D,n_A and support sizes sD,sAs_D,s_A, and a coupling to the error bound of Theorem 1. The coupling is the more consequential part. In prior treatments the cells outside the deviation set are unevaluated: pruned, deferred or unknown, with guarantees stated only over what was sampled. In RWPS they are filled by a surrogate the solver reads, and the corollary shows that however inaccurate that fill is, it cannot reach either player’s regret; the surrogate term wsurw_sur is zero regardless of the surrogate’s error β. This is what makes interpolation admissible in place of pruning, and what turns the deviation-relevant set into a budget for an estimator rather than a stopping rule for a sampler. The connection is exact. MRFS confirms a pure profile of a two-player n×n× n game by evaluating its entire unilateral deviation set, the row and column through that cell, which is 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. The deviation-relevant set is MRFS’s confirmation criterion extended from a pure profile to a mixed one. We need full columns on the opponent’s support, since only those columns enter a player’s expected payoff, and full rows on a player’s own support, since deviations range over all of that player’s strategies. Nothing outside this set affects either player’s regret. Coverage does not simulate the whole matrix: the remaining nDnA−B∗n_Dn_A-B cells stay surrogate-filled and are read by the solver, and the corollary shows only that they carry zero weight in regret. Theorem 1 bounds exploitability by a statistical term, from finite rollouts per simulated cell, and a representational term β, from surrogate error on unsimulated cells. Only the statistical term shrinks with spending. The representational term depends on whether fingerprints happen to predict payoffs in the game at hand, cannot be certified in advance, and by Theorem 2 can be arbitrarily large. Covering the deviation-relevant set removes it outright, leaving a purely statistical certificate: the guarantee a full rebuild would give, without a full rebuild and without any assumption about surrogate quality. B∗B is linear in pool and support sizes, so support size rather than matrix size sets the price of coverage. The support sizes are unknown before solving, but they can be estimated by re-solving many bootstrap realisations of the surrogate-filled game, following the bootstrap methodology of Wiedenbeck et al. [47]; this costs solves, not rollouts. Before committing any simulation, a practitioner can therefore read off whether coverage is a small fraction of the matrix, in which case budgeted estimation is worth enabling, or close to all of it, in which case a full rebuild is the better choice. Treated as a one-shot prediction the estimate can be wrong; Appendix A.8 shows how to iterate it to a fixed point instead. Coverage fixes which cells are simulated; the number of rollouts per cell fixes how tight the certificate of Corollary 1 is. 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∗=minm: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 loglog factor carried by the time-uniform radius. Here ζ(m,δ)ζ(m,δ) is the concentration radius for a cell mean from m rollouts, σ the payoff noise scale, and εsolve _solve the solver’s own regret. The two factors are bought separately and neither substitutes for the other: B∗B removes β, and m∗m shrinks ζ. Both are computable in advance, B∗B from bootstrap supports and m∗m by inverting ζ, and every quantity in the certificate is computable from simulation data. A deployment can therefore quote a budget against a target exploitability before spending it, including where the true equilibrium is unavailable. 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 unsigned forms of Eq. (3) charge errors in both directions, but the signed form (a) does not: only a deviation row whose value the estimate understates, or a support whose value it overstates, produces regret. This is what makes optimism admissible. Filling the unsimulated cells of a player’s own matrix at the maximum payoff, in the tradition of R-max [6], understates no deviation, so the deviation term reduces to statistical noise on simulated cells and only the support term remains; Corollary 1 uses exactly this fill, and only to evaluate the bound after the solve. Using the same fill inside the solve instead changes the object solved. Every unsimulated cell then looks maximal, so a best response points at it; it enters the support, is simulated, proves ordinary, and leaves, and the next unsimulated cell takes its place. With nDnAn_Dn_A cells to chase, this certifies only after nearly the whole matrix is bought (Appendix A.10). Optimism certifies a solution; it does not save simulation. A.3.3 Necessity of forced exploration The asymptotic guarantee of RWPS rests on its forced-exploration draws. They visit every cell infinitely often almost surely, so running means converge and Lemma 1 with τsupp→0 _supp→ 0 closes the argument; the two-phase Borel–Cantelli proof is standard. No acquisition rule that reads only fingerprints and cached payoffs can replace these draws. A fingerprint is a finite summary of a policy’s behaviour, so distinct policies can share one while differing arbitrarily in payoff (Appendix A.2), and such a rule cannot tell them apart. 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 Progressive sampling at budgets where it prunes The growing-pool comparison runs the progressive-sampling family below the budgets it was designed for. To show where it does become competitive, Table 2 in the main paper, and Table 4 in full, compare RWPS with GS, PSP and PS-REG-M on fixed 21×2121× 21 pools at budgets from 0.2×0.2× to 100×100× the 441441-cell matrix, with each family member implemented from its original specification. PS-REG-M, the member with mixed-equilibrium guarantees, prunes nothing below 100×100×; there it prunes 0.5%0.5\% of utility indices on the informative game and 6.1%6.1\% on Blotto. PSP prunes nothing at any budget tested, and the pure-equilibrium variant PS-REG+ starts earlier, pruning 0.7%0.7\% and 4.2%4.2\% at 20×20×. At 100×100× PSP and PS-REG-M reach exploitability comparable to RWPS: none of the four differences is significant (paired t-test, p≥0.15p≥ 0.15). Below that, GS and PSP coincide exactly at 0.2×0.2×, because neither can certify any cell and both fall back to a flat fill. Across all thirty pairwise comparisons RWPS is significantly better in twenty and never significantly worse (p<0.05p<0.05). The comparison is therefore one of operating regime: the family buys a uniform PAC guarantee and pays its sample complexity, which is affordable only at budgets many times the matrix. This sweep predates the final acquisition rule and uses four seeds, so we report it as a regime check rather than as a head-to-head result. Table 4: All five budgets of the progressive-sampling comparison (extends Table 2); exploitability mean ± SD over four seeds, bold marks each row’s best. Game Budget RWPS GS PSP PS-REG-M pruned Inf. 0.2×0.2× .051±.013.051±.013 .307±.112.307 ±.112 .307±.112.307 ±.112 .166±.136.166 ±.136 00 1×1× .029±.023.029±.023 .162±.138.162 ±.138 .222±.081.222 ±.081 .214±.106.214 ±.106 00 5×5× .037±.019.037±.019 .230±.091.230 ±.091 .354±.195.354 ±.195 .546±.331.546 ±.331 00 20×20× .012±.006.012±.006 .413±.125.413 ±.125 .156±.298.156 ±.298 .029±.050.029 ±.050 00 100×100× .007±.003.007 ±.003 .025±.040.025 ±.040 .005±.003.005 ±.003 .003±.002.003±.002 0.5%0.5\% Blotto 0.2×0.2× .135±.045.135±.045 .488±.024.488 ±.024 .488±.024.488 ±.024 .501±.041.501 ±.041 00 1×1× .043±.011.043±.011 .475±.029.475 ±.029 .471±.026.471 ±.026 .617±.268.617 ±.268 00 5×5× .032±.018.032±.018 .556±.093.556 ±.093 .419±.050.419 ±.050 .440±.080.440 ±.080 00 20×20× .025±.004.025±.004 .561±.081.561 ±.081 .366±.081.366 ±.081 .404±.049.404 ±.049 00 100×100× .015±.003.015 ±.003 .440±.035.440 ±.035 .013±.001.013±.001 .017±.007.017 ±.007 6.1%6.1\% A.3.5 Growing-pool PSRO: further detail In the growing-pool comparison of Table 1, every method starts from the same pool, but each method’s best-response oracle trains against that method’s own restricted equilibrium, so a better payoff estimate steers PSRO toward different strategies and the pools diverge after the first iteration. Exploitability is measured against the full game by zero-lifting each restricted mixture, which keeps pools of different composition comparable. The comparison is therefore end-to-end: it credits RWPS both for its payoff estimates and for the strategies those estimates lead PSRO to find. Appendix A.7 repeats it with identical payoffs and uninformative fingerprints to isolate what the fingerprint contributes. RWPS starts behind: at iteration 00 its exploitability is 0.2620.262, against 0.1800.180 for MRFS and 0.2080.208 for uniform sampling. This is expected. The cache is empty at the first build, so the surrogate is a rank-one fit to almost no labels and there is no history to reuse. The advantage of RWPS lies in what it carries between builds, and its lead widens monotonically with the iteration index. IGS finishes behind both MRFS and RWPS on both games (Table 1). Jordan et al. [15] recommend IGS for noisy payoffs, where MRFS is their method for exactly revealed payoffs, and report it outperforming the ECVI benchmark. We implement it from their Section 6.2: the next profile sampled is the one maximising Kullback–Leibler information gain aggregated over its deviation set, with the minimum-regret probability of each profile taken from their point approximation, and an MRFS prefix supplying initial samples as in their IGS-MRFS-3 variant. The budget, not the algorithm, is what puts IGS behind. IGS reallocates samples among profiles it has already visited; its original experiments run 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. On a fixed 21×2121× 21 pool, IGS improves from 0.1770.177 to 0.0410.041 as its allowance grows from 0.20.2 to 1.01.0 evaluations per profile, converging toward MRFS. Figure 6 reports an earlier CyGym comparison of RWPS and uniform sampling as a function of cumulative simulator calls. Figure 6: NashConv against cumulative simulator calls in CyGym (lower is better). At the lowest and highest budgets uniform sampling suffices; across all budget levels RWPS meets or exceeds it. The bound evaluated in Figure 5 includes the solver’s own regret εsolve _solve. Without that term the signed bound is violated on three runs, all on Blotto and each by less than that run’s solver regret. 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. Because εsolve _solve is computable from the estimated matrices alone, including it costs nothing in applicability and restores validity on every run, at a cost of 0.0060.006 in mean tightness. A.3.6 Cyber-defence simulators RWPS needs a simulator in which both an attacker and a defender are learning players, since PSRO grows a policy pool for each side and every payoff entry pairs one policy from each. We surveyed the environments in current use against that requirement; Table 5 summarises the result. CybORG [37], which underpins the CAGE challenges [38], and CyGym [20] both support learning agents on each side, and we use the latter directly. Cyberwheel [26] supports one learning red and one learning blue agent simultaneously and is the third simulator in our evaluation. gym-idsgame [11] models intrusion prevention as a Markov game between a learned attacker and a learned defender, and its accompanying study trains both by self-play against an opponent pool. It is the closest prior use of a policy pool in this domain, though it estimates no payoff matrix and so has no counterpart to our estimator. The multiagent extension of CyberBattleSim [16] adds a trainable defender and reports joint training of red and blue policies, which makes it a candidate once its code is publicly maintained. Several widely used environments do not meet the requirement. In YAWNING-TITAN [2] only the defender learns and the attacker is scripted and probabilistic, and in the standard CyberBattleSim [22] the defender is a predefined stochastic process. NASim [32] models a penetration-testing attacker with no active defender. CSLE [12] is a broad platform combining emulation and simulation across several security-management use cases rather than a single two-player environment; we have not identified a configuration of it that fits our setting. Table 5: Cyber-defence simulators by whether each side is a learning player. NASim has no defender at all. Simulator Learning red Learning blue Role here CyGym ✓ ✓ evaluated Cyberwheel ✓ ✓ evaluated CybORG / CAGE ✓ ✓ related gym-idsgame ✓ ✓ related Multiagent CyberBattleSim ✓ ✓ candidate YAWNING-TITAN ✗ ✓ excluded CyberBattleSim ✓ ✗ excluded NASim ✓ ✗ excluded CSLE platform deferred A.4 The Agentic Network Security Game This appendix gives the full specification of the ANSG introduced in Section 5. CyGym [20] 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 main 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 7 repeats the budget sweep of Section 6.2 on Cyberwheel [26]. 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 7: 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 A build with budget B runs R rounds. Each round refits the ensemble on the whole cache, predicts u^ij u_ij and σ^ij σ_ij on every unsimulated cell, re-solves BbootB_boot bootstrap realisations of the game to obtain the smoothed marginals, and then simulates about B/RB/R cells, each uniform with probability εx _x and otherwise the highest-scoring. The surrogate is therefore refit R+1R+1 times per build, once per round and once more before the matrices are committed. Only the simulation step consumes budget; the bootstrap costs solves alone. The cache persists across PSRO iterations, so a fit at iteration k trains on every cell bought earlier, and cached values always override the surrogate. Repeat visits, which arise only from exploration draws, are averaged into a running mean. The opening fit of each build warm-starts from the previous build’s weights, which leaves final exploitability unchanged (p=0.81p=0.81 informative, p=0.62p=0.62 Blotto, eight seeds) and cuts build time by 1717–20%20\%; the later rounds of a build are fit cold, because the cache roughly doubles between rounds and a short warm schedule does not track that. Until the cache holds eight labels, a rank-one row-and-column model stands in for the ensemble, so the first round on a fresh pool is close to uninformed. Each ensemble member is an MLP mapping the concatenated embeddings of a cell’s two strategies to both players’ payoffs. Member m trains on its own bootstrap resample of the cache (n cells drawn with replacement) with its own seed, which is the only source of disagreement between members; the loss is mean squared error on standardised targets, optimised full-batch with Adam for a fixed number of epochs, with no validation split or early stopping. This ensemble bootstrap measures uncertainty about individual payoffs. The separate acquisition bootstrap resamples 80%80\% of each pool’s strategies and re-solves the game, and so measures uncertainty about the equilibrium. On the synthetic games the restricted game is solved by fictitious play, whose residual regret is carried in every bound as εsolve _solve; the CyGym, ANSG and Cyberwheel sweeps use CyGym’s solver, support enumeration with a Lemke–Howson fallback. Those sweeps also embed strategies by identity tags, one-hot vectors per strategy, since building a behavioural probe bank for each simulator was out of scope; with tags the surrogate learns only row and column effects. On ANSG, 3636 cached cells were enough to trigger the MLP, which then filled the 1313 unseen cells worse than a flat mean, so that sweep keeps every RWPS arm on the rank-one model throughout. Table 6 lists the settings. Table 6: Default settings unless stated otherwise; epochs are cold / warm fits. Setting Value Ensemble M=3M=3 MLPs, 2×482× 48 hidden Training Adam, lr 5×10−35× 10^-3; 6060 / 1010 epochs Rounds and batch R=3R=3, c=⌈B/3⌉c= B/3 Bootstrap Bboot=32B_boot=32, 80%80\% of each pool Smoothing, exploration ν=0.25ν=0.25, εx=0.15 _x=0.15 Rank-one fallback below 88 cached labels Fictitious play 400400 final, 200200 in bootstrap Rollouts NMC=4N_MC=4, σ=0.10σ=0.10 Synthetic games 21×2121× 21, payoffs in [0,1][0,1] Probe bank P=32P=32 states per role A.7 Embedding Analysis 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 7 repeats the growing-pool comparison of Section 6.1 on both versions. Table 7: 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 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 learns row and column effects from cells already simulated: it learns 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 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 iteration and asymptotic guarantee 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. Corollary 1 reports what a completed build certifies; run backwards, it answers how much simulation buys a stated guarantee, before any of it is spent. 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.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 right 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 [46, 48]. 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 8) 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 8: 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 8 sweeps both at a 20%20\% budget over four seeds. Table 8: 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 3 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 9: Variants of our acquisition score, extending Table 3 with three further rules under the identical protocol; the first row repeats Table 3 for reference. Mean ± one standard error over sixteen paired seeds. Acquisition score Informative Blotto ν-smoothed product (ours) 0.024±0.0040.024± 0.004 0.082±0.0110.082± 0.011 bootstrap inclusion 0.035±0.0060.035 ±0.006 0.100±0.0170.100 ±0.017 training exposure 0.039±0.0050.039 ±0.005 0.105±0.0110.105 ±0.011 value-sensitivity (ν=0ν=0) 0.048±0.0100.048 ±0.010 0.096±0.0150.096 ±0.015 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. [28], 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 5 down by game. The third gives what the computable certificate costs in optimism. None is needed to read Table 1, Table 3, or Figure 5. 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 10 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 10: 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 9: 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 9 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 10). 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.