mlsanityData to 13 Oct 2026

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

arXiv 2101.04667 ↗First posted 12 Jan 2021cs.GT cs.LG cs.MAcited by 22

Not on the map. Why?

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

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

Builds on

7 of 47 references.

References · 7

  1. 2019Introduction to Multi-Armed Banditscited by 479
  2. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  3. 2017Cycles in adversarial regularized learningcited by 122
  4. 2016Learning in games with continuous action sets and unknown payoff functionscited by 79
  5. 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 49
  6. 2017Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaoscited by 29
  7. 2019Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Gamescited by 24

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 1; 2022: 7; 2023: 6; 2024: 2; 2025: 5; 2026: 1.

22 papers.

Sort:

  1. 2022Multi-agent Performative Prediction: From Global Stability and Optimality to Chaoscited by 33
  2. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  3. 2022On the convergence of policy gradient methods to Nash equilibria in general stochastic gamescited by 13
  4. 2022First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spacescited by 10
  5. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  6. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  7. 2023Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinementscited by 6
  8. 2022Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamicscited by 4
  9. 2023The equivalence of dynamic and strategic stability under regularized learning in gamescited by 4
  10. 2022Near-Optimal Phi-Regret Learning in Extensive-Form Gamescited by 3
  11. 2023Exploiting Partial Common Information Microstructure for Multi-Modal Brain Tumor Segmentationcited by 3
  12. 2022No-Regret Learning in Games is Turing Completecited by 2
10 more
  1. 2024Accelerated regularized learning in finite N-person gamescited by 2
  2. 2025The impact of uncertainty on regularized learning in gamescited by 2
  3. 2021Second-Order Mirror Descent: Convergence in Games Beyond Averaging and Discountingcited by 1
  4. 2023Chaos persists in large-scale multi-agent learning despite adaptive learning ratescited by 0
  5. 2024Nested replicator dynamics, nested logit choice, and similarity-based learningcited by 0
  6. 2025Last-iterate Convergence for Symmetric, General-sum, 2 × 2 Games Under The Exponential Weights Dynamiccited by 0
  7. 2025Last-Iterate Convergence of No-Regret Learning for Equilibria in Bargaining Gamescited by 0
  8. 2025Learnable Mixed Nash Equilibria are Collectively Rationalcited by 0
  9. 2025Robust equilibria in continuous games: From strategic to dynamic robustnesscited by 0
  10. 2026Regret, equilibrium, and learning in games: A guided tourcited by 0