# Efficient Nash Equilibrium Computation for Cybersecurity Games

arXiv: https://arxiv.org/abs/2609.19399 · HTML: https://mlsanity.com/paper/2609.19399/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 54 references that are in the map.
- First posted on arXiv 16 Sep 2026.

## Builds on (most cited first, 28 of 28)

- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Open-ended Learning in Symmetric Zero-sum Games](https://mlsanity.com/paper/1901.08106/) (2019)
- [Real World Games Look Like Spinning Tops](https://mlsanity.com/paper/2004.09468/) (2020)
- [CybORG: A Gym for the Development of Autonomous Cyber Agents](https://mlsanity.com/paper/2108.09118/) (2021)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [Developing Optimal Causal Cyber-Defence Agents via Cyber Security Simulation](https://mlsanity.com/paper/2207.12355/) (2022)
- [Autonomous Penetration Testing using Reinforcement Learning](https://mlsanity.com/paper/1905.05965/) (2019)
- [Finding Effective Security Strategies through Reinforcement Learning and Self-Play](https://mlsanity.com/paper/2009.08120/) (2020)
- [Network Environment Design for Autonomous Cyberdefense](https://mlsanity.com/paper/2103.07583/) (2021)
- [A Generalised Method for Empirical Game Theoretic Analysis](https://mlsanity.com/paper/1803.06376/) (2018)
- [Multiagent Evaluation under Incomplete Information](https://mlsanity.com/paper/1909.09849/) (2019)
- [Empirical Game-Theoretic Analysis: A Survey](https://mlsanity.com/paper/2403.04018/) (2024)
- [CybORG++: An Enhanced Gym for the Development of Autonomous Cyber Agents](https://mlsanity.com/paper/2410.16324/) (2024)
- [A Bayesian optimization approach to find Nash equilibria](https://mlsanity.com/paper/1611.02440/) (2016)
- [A Multiagent CyberBattleSim for RL Cyber Operation Agents](https://mlsanity.com/paper/2304.11052/) (2023)
- [Evaluating Strategy Exploration in Empirical Game-Theoretic Analysis](https://mlsanity.com/paper/2105.10423/) (2021)
- [CSLE: A Reinforcement Learning Platform for Autonomous Security Management](https://mlsanity.com/paper/2604.15590/) (2026)
- [Estimating α-Rank by Maximizing Information Gain](https://mlsanity.com/paper/2101.09178/) (2021)
- [Approximating Nash Equilibria for Black-Box Games: A Bayesian Optimization Approach](https://mlsanity.com/paper/1804.10586/) (2018)
- [Empirical Game-Theoretic Analysis for Mean Field Games](https://mlsanity.com/paper/2112.00900/) (2021)
- [No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes](https://mlsanity.com/paper/2405.08318/) (2024)
- [CyGym: A Simulation-Based Game-Theoretic Analysis Framework for Cybersecurity](https://mlsanity.com/paper/2506.21688/) (2025)
- [Computational and Data Requirements for Learning Generic Properties of Simulation-Based Games](https://mlsanity.com/paper/2208.06400/) (2022)
- [Regret Pruning for Learning Equilibria in Simulation-Based Games](https://mlsanity.com/paper/2211.16670/) (2022)
- [A Scalable Approach to Solving Simulation-Based Network Security Games](https://mlsanity.com/paper/2602.16564/) (2026)
- [Conservative Equilibrium Discovery in Offline Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2603.00374/) (2026)

## Abstract (arXiv)

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.