# Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Oct 2023.

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

- [Re-evaluating Open-ended Evaluation of Large Language Models](https://mlsanity.com/paper/2502.20170/) (2025)
- [No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes](https://mlsanity.com/paper/2405.08318/) (2024)
- [Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.16600/) (2024)
- [Batched Stochastic Bandit for Nondegenerate Functions](https://mlsanity.com/paper/2405.05733/) (2024)
- [A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games](https://mlsanity.com/paper/2503.18224/) (2025)
- [Nash Equilibria via Stochastic Eigendecomposition](https://mlsanity.com/paper/2411.02308/) (2024)
- [Bounded Rationality Equilibrium Learning in Mean Field Games](https://mlsanity.com/paper/2411.07099/) (2024)
- [Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities](https://mlsanity.com/paper/2601.23034/) (2026)
- [LLM Active Alignment: A Nash Equilibrium Perspective](https://mlsanity.com/paper/2602.06836/) (2026)

## Abstract (arXiv)

We propose the first loss function for approximate Nash equilibria of normal-form games that is amenable to unbiased Monte Carlo estimation. This construction allows us to deploy standard non-convex stochastic optimization techniques for approximating Nash equilibria, resulting in novel algorithms with provable guarantees. We complement our theoretical analysis with experiments demonstrating that stochastic gradient descent can outperform previous state-of-the-art approaches.