# Probably Approximately Correct Nash Equilibrium Learning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2019.

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

- [Is Nash Equilibrium Approximator Learnable?](https://mlsanity.com/paper/2108.07472/) (2021)
- [Finite sample learning of moving targets](https://mlsanity.com/paper/2408.04406/) (2024)
- [Adversarially and Distributionally Robust Virtual Energy Storage Systems via the Scenario Approach](https://mlsanity.com/paper/2511.09427/) (2025)
- [Wasserstein Distributionally Robust Nash Equilibrium Seeking with Heterogeneous Data: A Lagrangian Approach](https://mlsanity.com/paper/2511.14048/) (2025)

## Abstract (arXiv)

We consider a multi-agent noncooperative game with agents' objective functions being affected by uncertainty. Following a data driven paradigm, we represent uncertainty by means of scenarios and seek a robust Nash equilibrium solution. We treat the Nash equilibrium computation problem within the realm of probably approximately correct (PAC) learning. Building upon recent developments in scenario-based optimization, we accompany the computed Nash equilibrium with a priori and a posteriori probabilistic robustness certificates, providing confidence that the computed equilibrium remains unaffected (in probabilistic terms) when a new uncertainty realization is encountered. For a wide class of games, we also show that the computation of the so called compression set - a key concept in scenario-based optimization - can be directly obtained as a byproduct of the proposed solution methodology. Finally, we illustrate how to overcome differentiability issues, arising due to the introduction of scenarios, and compute a Nash equilibrium solution in a decentralized manner. We demonstrate the efficacy of the proposed approach on an electric vehicle charging control problem.