No-Regret Learning and Mixed Nash Equilibria: They Do Not Mix
Authors: Emmanouil-Vasileios Vlatakis-Gkaragkounis, Lampros Flokas, Thanasis Lianeas, Panayotis Mertikopoulos, Georgios Piliouras
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Collaboration | Lampros Flokas Department of Computer Science Columbia University New York, NY 10025 lamflokas@cs.columbia.edu Emmanouil V. Vlatakis-Gkaragkounis Department of Computer Science Columbia University New York, NY 10025 emvlatakis@cs.columbia.edu Thanasis Lianeas School of Electrical and Computer Engineering National Technical University of Athens Athens,Greece lianeas@corelab.ntua.gr Panayotis Mertikopoulos Univ. Grenoble Alpes, CNRS, Inria, LIG & Criteo AI Lab panayotis.mertikopoulos@imag.fr Georgios Piliouras Engineering Systems and Design Singapore University of Technology and Design Singapore georgios@sutd.edu.sg |
| Pseudocode | No | The paper is theoretical and does not contain any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is a theoretical work focusing on mathematical analysis and proofs, not empirical evaluation with datasets. Therefore, it does not provide information about public datasets used for training. |
| Dataset Splits | No | The paper is a theoretical work and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or mention hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup or list software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup, hyperparameters, or training configurations. |