# Is Nash Equilibrium Approximator Learnable?

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 69 references that are in the map.
- First posted on arXiv 17 Aug 2021.

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

- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [Game-Theoretic Multiagent Reinforcement Learning](https://mlsanity.com/paper/2011.00583/) (2020)
- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [Data-Driven Estimation in Equilibrium Using Inverse Optimization](https://mlsanity.com/paper/1308.3397/) (2013)
- [Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent](https://mlsanity.com/paper/1903.05614/) (2019)
- [What game are we playing? End-to-end learning in normal and extensive form games](https://mlsanity.com/paper/1805.02777/) (2018)
- [End-to-End Learning and Intervention in Games](https://mlsanity.com/paper/2010.13834/) (2020)
- [Online Double Oracle](https://mlsanity.com/paper/2103.07780/) (2021)
- [Contextual Games: Multi-Agent Learning with Side Information](https://mlsanity.com/paper/2107.06327/) (2021)
- [Learning Equilibria of Games via Payoff Queries](https://mlsanity.com/paper/1302.3116/) (2013)
- [Learning Probably Approximately Correct Maximin Strategies in Simulation-Based Games with Infinite Strategy Spaces](https://mlsanity.com/paper/1911.07755/) (2019)
- [Large Scale Learning of Agent Rationality in Two-Player Zero-Sum Games](https://mlsanity.com/paper/1903.04101/) (2019)
- [Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries](https://mlsanity.com/paper/1310.7419/) (2013)
- [Data-Driven Estimation of Travel Latency Cost Functions via Inverse Optimization in Multi-Class Transportation Networks](https://mlsanity.com/paper/1703.04010/) (2017)
- [Probably Approximately Correct Nash Equilibrium Learning](https://mlsanity.com/paper/1903.10387/) (2019)
- [Distributed Methods for Computing Approximate Equilibria](https://mlsanity.com/paper/1512.03315/) (2015)
- [Using Inverse Optimization to Learn Cost Functions in Generalized Nash Games](https://mlsanity.com/paper/2102.12415/) (2021)
- [Learning Equilibria of Simulation-Based Games](https://mlsanity.com/paper/1905.13379/) (2019)
- [An Empirical Study of Finding Approximate Equilibria in Bimatrix Games](https://mlsanity.com/paper/1502.04980/) (2015)

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

- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [Are Equivariant Equilibrium Approximators Beneficial?](https://mlsanity.com/paper/2301.11481/) (2023)
- [Large-Scale Contextual Market Equilibrium Computation through Deep Learning](https://mlsanity.com/paper/2406.15459/) (2024)
- [Learning to Coordinate Bidders in Non-Truthful Auctions](https://mlsanity.com/paper/2507.02801/) (2025)

## Abstract (arXiv)

In this paper, we investigate the learnability of the function approximator that approximates Nash equilibrium (NE) for games generated from a distribution. First, we offer a generalization bound using the Probably Approximately Correct (PAC) learning model. The bound describes the gap between the expected loss and empirical loss of the NE approximator. Afterward, we prove the agnostic PAC learnability of the Nash approximator. In addition to theoretical analysis, we demonstrate an application of NE approximator in experiments. The trained NE approximator can be used to warm-start and accelerate classical NE solvers. Together, our results show the practicability of approximating NE through function approximation.