# Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 47 references that are in the map.
- First posted on arXiv 12 Jan 2021.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos](https://mlsanity.com/paper/1703.01138/) (2017)
- [Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games](https://mlsanity.com/paper/1905.08396/) (2019)

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

- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [On the convergence of policy gradient methods to Nash equilibria in general stochastic games](https://mlsanity.com/paper/2210.08857/) (2022)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2208.09855/) (2022)
- [Adaptively Perturbed Mirror Descent for Learning in Games](https://mlsanity.com/paper/2305.16610/) (2023)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics](https://mlsanity.com/paper/2203.14129/) (2022)
- [The equivalence of dynamic and strategic stability under regularized learning in games](https://mlsanity.com/paper/2311.02407/) (2023)
- [Near-Optimal Phi-Regret Learning in Extensive-Form Games](https://mlsanity.com/paper/2208.09747/) (2022)
- [Exploiting Partial Common Information Microstructure for Multi-Modal Brain Tumor Segmentation](https://mlsanity.com/paper/2302.02521/) (2023)
- [No-Regret Learning in Games is Turing Complete](https://mlsanity.com/paper/2202.11871/) (2022)
- [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)
- [Second-Order Mirror Descent: Convergence in Games Beyond Averaging and Discounting](https://mlsanity.com/paper/2111.09982/) (2021)
- [Chaos persists in large-scale multi-agent learning despite adaptive learning rates](https://mlsanity.com/paper/2306.01032/) (2023)
- [Nested replicator dynamics, nested logit choice, and similarity-based learning](https://mlsanity.com/paper/2407.17815/) (2024)
- [Last-iterate Convergence for Symmetric, General-sum, 2 × 2 Games Under The Exponential Weights Dynamic](https://mlsanity.com/paper/2502.08063/) (2025)
- [Last-Iterate Convergence of No-Regret Learning for Equilibria in Bargaining Games](https://mlsanity.com/paper/2507.03150/) (2025)
- [Learnable Mixed Nash Equilibria are Collectively Rational](https://mlsanity.com/paper/2510.14907/) (2025)
- [Robust equilibria in continuous games: From strategic to dynamic robustness](https://mlsanity.com/paper/2512.08138/) (2025)
- [No Coin Left Behind: Maximizing Strategic Surplus Against No-Regret Dynamics](https://mlsanity.com/paper/2604.05129/) (2026)
- [Regret, equilibrium, and learning in games: A guided tour](https://mlsanity.com/paper/2608.09389/) (2026)

## Abstract (arXiv)

In this paper, we examine the Nash equilibrium convergence properties of no-regret learning in general N-player games. For concreteness, we focus on the archetypal follow the regularized leader (FTRL) family of algorithms, and we consider the full spectrum of uncertainty that the players may encounter - from noisy, oracle-based feedback, to bandit, payoff-based information. In this general context, we establish a comprehensive equivalence between the stability of a Nash equilibrium and its support: a Nash equilibrium is stable and attracting with arbitrarily high probability if and only if it is strict (i.e., each equilibrium strategy has a unique best response). This equivalence extends existing continuous-time versions of the folk theorem of evolutionary game theory to a bona fide algorithmic learning setting, and it provides a clear refinement criterion for the prediction of the day-to-day behavior of no-regret learning in games