Skip to Main content Skip to Navigation
Conference papers

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

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03043763
Contributor : Panayotis Mertikopoulos Connect in order to contact the contributor
Submitted on : Monday, December 7, 2020 - 2:16:58 PM
Last modification on : Wednesday, November 3, 2021 - 9:49:23 AM
Long-term archiving on: : Monday, March 8, 2021 - 7:09:54 PM

File

UnstableNash-NIPS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03043763, version 1

Citation

Lampros Flokas, Emmanouil 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⟩

Share

Metrics

Les métriques sont temporairement indisponibles