# Learning Equilibria of Simulation-Based Games

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2019.

## Built on by (most cited first, 2 of 2)

- [Is Nash Equilibrium Approximator Learnable?](https://mlsanity.com/paper/2108.07472/) (2021)
- [Context-dependent agent evaluation with orthogonal equilibrium learning](https://mlsanity.com/paper/2609.31897/) (2026)

## Abstract (arXiv)

We tackle a fundamental problem in empirical game-theoretic analysis (EGTA), that of learning equilibria of simulation-based games. Such games cannot be described in analytical form; instead, a black-box simulator can be queried to obtain noisy samples of utilities. Our approach to EGTA is in the spirit of probably approximately correct learning. We design algorithms that learn so-called empirical games, which uniformly approximate the utilities of simulation-based games with finite-sample guarantees. These algorithms can be instantiated with various concentration inequalities. Building on earlier work, we first apply Hoeffding's bound, but as the size of the game grows, this bound eventually becomes statistically intractable; hence, we also use the Rademacher complexity. Our main results state: with high probability, all equilibria of the simulation-based game are approximate equilibria in the empirical game (perfect recall); and conversely, all approximate equilibria in the empirical game are approximate equilibria in the simulation-based game (approximately perfect precision). We evaluate our algorithms on several synthetic games, showing that they make frugal use of data, produce accurate estimates more often than the theory predicts, and are robust to different forms of noise.