aiqbench analysis
This research introduces Regret-Weighted Payoff Sampling (RWPS), a novel estimator that accelerates Nash equilibrium computation in simulation-based cybersecurity games by selectively simulating only payoff cells critical to the equilibrium. By leveraging surrogate models for non-sensitive entries and proving instance-dependent error bounds, RWPS achieves lower exploitability than existing sampling strategies while significantly reducing computational budgets on complex cyber simulators. The work advances the efficiency of policy-space response oracles (PSRO), a core algorithmic framework for training robust AI agents in adversarial environments.
Efficient Nash Equilibrium Computation for Cybersecurity Games
arXiv:2609.19399v1 Announce Type: cross 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.
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.
Computer Science and Game Theory (cs.GT); Artificial Intelligence (cs.AI)
arXiv:2609.19399 [cs.GT]
(or arXiv:2609.19399v1 [cs.GT] for this version)
https://doi.org/10.48550/arXiv.2609.19399 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 309 words
Related coverage
Normal-Form Correlation in Markov Games
arXiv · Oct 5, 2026
Phi-Actor-Critic: Steering General-Sum Games to Pareto-Efficient Correlated Equilibria
arXiv · Jun 12, 2026
DiffNash: Finding Nash Equilibrium in High-Dimensional Continuous Action Spaces with Diffusion Policies
arXiv · Oct 15, 2026
Aerial GRIPPER: A Gradient-based Real-time Inverse-game Predictor and Planner
arXiv · Sep 29, 2026