Timezone: »

 
Poster
No-Regret Learning and Mixed Nash Equilibria: They Do Not Mix
Emmanouil-Vasileios Vlatakis-Gkaragkounis · Lampros Flokas · Thanasis Lianeas · Panayotis Mertikopoulos · Georgios Piliouras

Thu Dec 10 09:00 PM -- 11:00 PM (PST) @ Poster Session 6 #1866
in Poster Session 7 »

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.

Keywords: Computational Photography · Applications · Algorithms -> Semi-Supervised Learning; Applications · Computer Vision; Deep Learning

Author Information

Emmanouil-Vasileios Vlatakis-Gkaragkounis (Columbia University)
Lampros Flokas (Columbia University)
Thanasis Lianeas (National Technical University of Athens)
Panayotis Mertikopoulos (CNRS (French National Center for Scientific Research) and Criteo AI Lab)
Georgios Piliouras (Singapore University of Technology and Design)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors