No-regret learning and mixed Nash equilibria: They do not mix - Archive ouverte HAL Access content directly
Conference Papers Year :

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

(1) , (1) , (2) , (3, 4) , (5)
1
2
3
4
5

Abstract

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-today 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.
Fichier principal
Vignette du fichier
UnstableNash-NIPS.pdf (637.62 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03043763 , version 1 (07-12-2020)

Identifiers

  • HAL Id : hal-03043763 , version 1

Cite

Lampros Flokas, Emmanouil Vasileios Vlatakis-Gkaragkounis, Thanasis Lianeas, Panayotis Mertikopoulos, Georgios Piliouras. No-regret learning and mixed Nash equilibria: They do not mix. NeurIPS 2020 - 34th International Conference on Neural Information Processing Systems, Dec 2020, Vancouver, Canada. pp.1-24. ⟨hal-03043763⟩
89 View
162 Download

Share

Gmail Facebook Twitter LinkedIn More