Efficiently computing game strategies for cybersecurity simulations
Efficient Nash Equilibrium Computation for Cybersecurity Games
Computer Science and Game TheoryArtificial Intelligence
Summary
Finding the best strategies for computer security games can be very slow because it requires many simulations. The authors developed a new approach that focuses only on the important parts of the game to save time. Their method uses a smart estimator that guesses missing information based on earlier simulations to speed up calculations. Tests on multiple games and cybersecurity simulators showed it finds better strategies with fewer simulations than previous methods.
What this means in practice
- •For cybersecurity teams: Speed up finding reliable defense strategies in cybersecurity simulations by focusing computations only on critical scenarios.
- •For game developers: Improve AI opponents in strategy games by efficiently estimating optimal mixed strategies with fewer simulations.
Authors
Michael Lanier, David Farmer, Yevgeniy Vorobeychik
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.