mlsanityData to 7 Oct 2026

Is Nash Equilibrium Approximator Learnable?

arXiv 2108.07472 ↗First posted 17 Aug 2021cs.GT cs.LG cs.MAcited by 4

Not on the map. Why?

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.

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

Builds on

23 of 69 references.

References · 23

  1. 2013Intriguing properties of neural networkscited by 5,114
  2. 2018Lipschitz regularity of deep neural networks: analysis and efficient estimationcited by 413
  3. 2017A Unified Game-Theoretic Approach to Multiagent Reinforcement Learningcited by 265
  4. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  5. 2020Near-Optimal Reinforcement Learning with Self-Playcited by 108
  6. 2020Game-Theoretic Multiagent Reinforcement Learningcited by 92
  7. 2021Modelling Behavioural Diversity for Learning in Open-Ended Gamescited by 39
  8. 2013Data-Driven Estimation in Equilibrium Using Inverse Optimizationcited by 32
  9. 2019Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descentcited by 31
  10. 2018What game are we playing? End-to-end learning in normal and extensive form gamescited by 22
  11. 2020End-to-End Learning and Intervention in Gamescited by 19
  12. 2021Online Double Oraclecited by 18
11 more
  1. 2021Contextual Games: Multi-Agent Learning with Side Informationcited by 11
  2. 2013Learning Equilibria of Games via Payoff Queriescited by 8
  3. 2019Learning Probably Approximately Correct Maximin Strategies in Simulation-Based Games with Infinite Strategy Spacescited by 8
  4. 2019Large Scale Learning of Agent Rationality in Two-Player Zero-Sum Gamescited by 6
  5. 2013Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queriescited by 4
  6. 2017Data-Driven Estimation of Travel Latency Cost Functions via Inverse Optimization in Multi-Class Transportation Networkscited by 4
  7. 2019Probably Approximately Correct Nash Equilibrium Learningcited by 4
  8. 2015Distributed Methods for Computing Approximate Equilibriacited by 3
  9. 2021Using Inverse Optimization to Learn Cost Functions in Generalized Nash Gamescited by 3
  10. 2015An Empirical Study of Finding Approximate Equilibria in Bimatrix Gamescited by 1
  11. 2019Learning Equilibria of Simulation-Based Gamescited by 1

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 1; 2025: 1.

4 papers.

  1. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  2. 2023Are Equivariant Equilibrium Approximators Beneficial?cited by 2
  3. 2024Large-Scale Contextual Market Equilibrium Computation through Deep Learningcited by 0
  4. 2025Learning to Coordinate Bidders in Non-Truthful Auctionscited by 0