# No-regret learning and mixed Nash equilibria: They do not mix

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2020.

## Built on by (most cited first, 30 of 50)

- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Multi-agent Performative Prediction: From Global Stability and Optimality to Chaos](https://mlsanity.com/paper/2201.10483/) (2022)
- [Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Games](https://mlsanity.com/paper/2107.13090/) (2021)
- [Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information](https://mlsanity.com/paper/2101.04667/) (2021)
- [A unified stochastic approximation framework for learning in games](https://mlsanity.com/paper/2206.03922/) (2022)
- [Contracting with a Learning Agent](https://mlsanity.com/paper/2401.16198/) (2024)
- [On the convergence of policy gradient methods to Nash equilibria in general stochastic games](https://mlsanity.com/paper/2210.08857/) (2022)
- [Neural Network Weights Do Not Converge to Stationary Points: An Invariant Measure Perspective](https://mlsanity.com/paper/2110.06256/) (2021)
- [On the Convergence of No-Regret Learning Dynamics in Time-Varying Games](https://mlsanity.com/paper/2301.11241/) (2023)
- [Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms](https://mlsanity.com/paper/2406.10631/) (2024)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Follow-the-Regularized-Leader Routes to Chaos in Routing Games](https://mlsanity.com/paper/2102.07974/) (2021)
- [First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces](https://mlsanity.com/paper/2206.02041/) (2022)
- [Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions](https://mlsanity.com/paper/2110.03906/) (2021)
- [Asymptotic Convergence and Performance of Multi-Agent Q-Learning Dynamics](https://mlsanity.com/paper/2301.09619/) (2023)
- [Nash, Conley, and Computation: Impossibility and Incompleteness in Game Dynamics](https://mlsanity.com/paper/2203.14129/) (2022)
- [Learning in quantum games](https://mlsanity.com/paper/2302.02333/) (2023)
- [The equivalence of dynamic and strategic stability under regularized learning in games](https://mlsanity.com/paper/2311.02407/) (2023)
- [A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights](https://mlsanity.com/paper/2405.07224/) (2024)
- [No-regret learning in harmonic games: Extrapolation in the face of conflicting interests](https://mlsanity.com/paper/2412.20203/) (2024)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [The Replicator Dynamic, Chain Components and the Response Graph](https://mlsanity.com/paper/2209.15230/) (2022)
- [Evolutionary Dynamics and Phi-Regret Minimization in Games](https://mlsanity.com/paper/2106.14668/) (2021)
- [No-Regret Learning in Games is Turing Complete](https://mlsanity.com/paper/2202.11871/) (2022)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [Understanding Iterative Combinatorial Auction Designs via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2402.19420/) (2024)
- [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)

## Abstract (arXiv)

Understanding the behavior of no-regret dynamics in general N-player games is a fundamental question in online learning and game theory. A folk result in the field states that, in finite games, the empirical frequency of play under no-regret learning converges to the game's set of coarse correlated equilibria. By contrast, our understanding of how the day-to-day behavior of the dynamics correlates to the game's Nash equilibria is much more limited, and only partial results are known for certain classes of games (such as zero-sum or congestion games). In this paper, we study the dynamics of "follow-the-regularized-leader" (FTRL), arguably the most well-studied class of no-regret dynamics, and we establish a sweeping negative result showing that the notion of mixed Nash equilibrium is antithetical to no-regret learning. Specifically, we show that any Nash equilibrium which is not strict (in that every player has a unique best response) cannot be stable and attracting under the dynamics of FTRL. This result has significant implications for predicting the outcome of a learning process as it shows unequivocally that only strict (and hence, pure) Nash equilibria can emerge as stable limit points thereof.