Efficient Nash Equilibrium Computation for Cybersecurity Games
cs.GT, cs.AI
Submitted: 2026-09-16
Updated: 2026-09-22
License: http://creativecommons.org/licenses/by/4.0/
The gist: Computing Nash equilibria of simulation-based cybersecurity games with policy-space response oracles (PSRO) is bottlenecked by payoff estimation: every payoff-matrix entry costs Monte-Carlo rollouts
Terminology
Abstract
Computing Nash equilibria of simulation-based cybersecurity games with policy-space response oracles (PSRO) is bottlenecked by payoff estimation: every payoff-matrix entry costs Monte-Carlo rollouts of a slow simulator, while policies and restricted-game solves are cheap. We introduce Regret-Weighted Payoff Sampling (RWPS), a budgeted estimator that simulates only the cells an equilibrium is sensitive to and fills the rest with a surrogate trained on every entry simulated earlier in the run. The sup-norm error bound cannot evaluate such an estimator, because it is set by the cells left deliberately inaccurate. We prove an instance-dependent bound that weights error by the opponent's equilibrium mixture, a certificate computable from simulation data alone, and a coverage result showing that once the deviation-relevant set is simulated, surrogate error cannot affect either player's regret. On three 21x21 general-sum games, two synthetic and an asymmetric Colonel Blotto, the refined bounds are four to six times tighter on the estimator's own output, and the coverage result predicts in advance which games are cheap: 18% of the matrix for small-support games against 82% for Blotto. In growing-pool PSRO, RWPS reaches lower exploitability than minimum-regret-first search, information-gain search, and progressive sampling at a matched budget, and on the CyGym and ANSG cyber simulators it is lowest at the smallest budgets.
Sources
- Developing Optimal Causal Cyber-Defence Agents via Cyber Security Simulation
- Computational and Data Requirements for Learning Generic Properties of Simulation-Based Games
- CybORG++: An Enhanced Gym for the Development of Autonomous Cyber Agents
- Regret Pruning for Learning Equilibria in Simulation-Based Games
- Network Environment Design for Autonomous Cyberdefense
- A Bayesian optimization approach to find Nash equilibria
- Empirical Game-Theoretic Analysis: A Survey
Related papers
- Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
- In-Context Credit Assignment via the Core
- Breaking 1/epsilon Barrier in Quantum Zero-Sum Games: Generalizing Metric Subregularity for Spectraplexes
- Enhancing Affine Maximizer Auctions with Correlation-Aware Payment
- LLM Bidders Preserve the Mechanism-Level Orderings of Human Bidders
- Towards Performatively Stable Equilibria in Decision-Dependent Games for Arbitrary Data Distribution Maps