No-regret learning and mixed Nash equilibria: They do not mix
arXiv:2010.09514
Abstract
Understanding the behavior of no-regret dynamics in general -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.
arXiv comment24 pages, 7 figures, 1 table
References in corpus (9)
- Online Learning with Predictable Sequences
- The emergence of rational behavior in the presence of stochastic perturbations
- Learning in Games: Robustness of Fast Convergence
- No-regret Dynamics and Fictitious Play
- Multiagent Evaluation under Incomplete Information
- From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization
- The limits of min-max optimization algorithms: convergence to spurious non-critical sets
- Chaos, Extremism and Optimism: Volume Analysis of Learning in Games
- Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games