# A unified stochastic approximation framework for learning in games

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 73 references that are in the map.
- First posted on arXiv 8 Jun 2022.

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

- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile](https://mlsanity.com/paper/1807.02629/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020)
- [The limits of min-max optimization algorithms: convergence to spurious non-critical sets](https://mlsanity.com/paper/2006.09065/) (2020)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)
- [Bandit learning in concave N-person games](https://mlsanity.com/paper/1810.01925/) (2018)
- [On the Characterization of Local Nash Equilibria in Continuous Games](https://mlsanity.com/paper/1411.2168/) (2014)
- [Multi-agent online learning in time-varying games](https://mlsanity.com/paper/1809.03066/) (2018)
- [Learning Nash Equilibria in Monotone Games](https://mlsanity.com/paper/1904.01882/) (2019)
- [Learning with minimal information in continuous games](https://mlsanity.com/paper/1806.11506/) (2018)
- [Learning Generalized Nash Equilibria in a Class of Convex Games](https://mlsanity.com/paper/1703.04113/) (2017)

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

- [Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuning](https://mlsanity.com/paper/2511.22640/) (2025)
- [Provable Maximum Entropy Manifold Exploration via Diffusion Models](https://mlsanity.com/paper/2506.15385/) (2025)
- [Riemannian stochastic optimization methods avoid strict saddle points](https://mlsanity.com/paper/2311.02374/) (2023)
- [Verifier-Constrained Flow Expansion for Discovery Beyond the Data](https://mlsanity.com/paper/2602.15984/) (2026)
- [Multiplayer Federated Learning: Reaching Equilibrium with Less Communication](https://mlsanity.com/paper/2501.08263/) (2025)
- [No-regret learning in harmonic games: Extrapolation in the face of conflicting interests](https://mlsanity.com/paper/2412.20203/) (2024)
- [Exploiting hidden structures in non-convex games for convergence to Nash equilibrium](https://mlsanity.com/paper/2312.16609/) (2023)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [Payoff-based learning with matrix multiplicative weights in quantum games](https://mlsanity.com/paper/2311.02423/) (2023)
- [Accelerated regularized learning in finite N-person games](https://mlsanity.com/paper/2412.20365/) (2024)
- [The impact of uncertainty on regularized learning in games](https://mlsanity.com/paper/2506.13286/) (2025)
- [A Unified Density Operator View of Flow Control and Merging](https://mlsanity.com/paper/2602.08012/) (2026)
- [Sinkhorn Flow: A Continuous-Time Framework for Understanding and Generalizing the Sinkhorn Algorithm](https://mlsanity.com/paper/2311.16706/) (2023)
- [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026)
- [Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework](https://mlsanity.com/paper/2605.31309/) (2026)
- [A Payoff-Based Policy Gradient Method in Stochastic Games with Long-Run Average Payoffs](https://mlsanity.com/paper/2405.09811/) (2024)
- [Nested replicator dynamics, nested logit choice, and similarity-based learning](https://mlsanity.com/paper/2407.17815/) (2024)
- [Optimistic Online Learning in Symmetric Cone Games](https://mlsanity.com/paper/2504.03592/) (2025)
- [Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation](https://mlsanity.com/paper/2509.14032/) (2025)
- [Multi-agent learning under uncertainty: Recurrence vs. concentration](https://mlsanity.com/paper/2512.08132/) (2025)
- [Robust equilibria in continuous games: From strategic to dynamic robustness](https://mlsanity.com/paper/2512.08138/) (2025)
- [Computing Pure-Strategy Nash Equilibria in a Two-Party Policy Competition: Existence and Algorithmic Approaches](https://mlsanity.com/paper/2512.22552/) (2025)
- [Regret, equilibrium, and learning in games: A guided tour](https://mlsanity.com/paper/2608.09389/) (2026)

## Abstract (arXiv)

We develop a flexible stochastic approximation framework for analyzing the long-run behavior of learning in games (both continuous and finite). The proposed analysis template incorporates a wide array of popular learning algorithms, including gradient-based methods, the exponential/multiplicative weights algorithm for learning in finite games, optimistic and bandit variants of the above, etc. In addition to providing an integrated view of these algorithms, our framework further allows us to obtain several new convergence results, both asymptotic and in finite time, in both continuous and finite games. Specifically, we provide a range of criteria for identifying classes of Nash equilibria and sets of action profiles that are attracting with high probability, and we also introduce the notion of coherence, a game-theoretic property that includes strict and sharp equilibria, and which leads to convergence in finite time. Importantly, our analysis applies to both oracle-based and bandit, payoff-based methods - that is, when players only observe their realized payoffs.