Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information

Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2147-2148, 2021.

Abstract

In this paper, we examine the Nash equilibrium convergence properties of no-regret learning in general N -player games. For concreteness, we focus on the archetypal “follow the regularized leader” (FTRL) family of algorithms, and we consider the full spectrum of uncertainty that the players may encounter – from noisy, oracle-based feedback, to bandit, payoff-based information. In this general context, we establish a comprehensive equivalence between the stability of a Nash equilibrium and its support: a Nash equilibrium is stable and attracting with arbitrarily high probability if and only if it is strict (i.e., each equilibrium strategy has a unique best response). This equivalence extends existing continuous-time versions of the “folk theorem” of evolutionary game theory to a bona fide algorithmic learning setting, and it provides a clear refinement criterion for the prediction of the day-to-day behavior of no-regret learning in games.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-giannou21a, title = {Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information}, author = {Giannou, Angeliki and Vlatakis-Gkaragkounis, Emmanouil Vasileios and Mertikopoulos, Panayotis}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {2147--2148}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/giannou21a/giannou21a.pdf}, url = {https://proceedings.mlr.press/v134/giannou21a.html}, abstract = {In this paper, we examine the Nash equilibrium convergence properties of no-regret learning in general N -player games. For concreteness, we focus on the archetypal “follow the regularized leader” (FTRL) family of algorithms, and we consider the full spectrum of uncertainty that the players may encounter – from noisy, oracle-based feedback, to bandit, payoff-based information. In this general context, we establish a comprehensive equivalence between the stability of a Nash equilibrium and its support: a Nash equilibrium is stable and attracting with arbitrarily high probability if and only if it is strict (i.e., each equilibrium strategy has a unique best response). This equivalence extends existing continuous-time versions of the “folk theorem” of evolutionary game theory to a bona fide algorithmic learning setting, and it provides a clear refinement criterion for the prediction of the day-to-day behavior of no-regret learning in games.} }
Endnote
%0 Conference Paper %T Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information %A Angeliki Giannou %A Emmanouil Vasileios Vlatakis-Gkaragkounis %A Panayotis Mertikopoulos %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-giannou21a %I PMLR %P 2147--2148 %U https://proceedings.mlr.press/v134/giannou21a.html %V 134 %X In this paper, we examine the Nash equilibrium convergence properties of no-regret learning in general N -player games. For concreteness, we focus on the archetypal “follow the regularized leader” (FTRL) family of algorithms, and we consider the full spectrum of uncertainty that the players may encounter – from noisy, oracle-based feedback, to bandit, payoff-based information. In this general context, we establish a comprehensive equivalence between the stability of a Nash equilibrium and its support: a Nash equilibrium is stable and attracting with arbitrarily high probability if and only if it is strict (i.e., each equilibrium strategy has a unique best response). This equivalence extends existing continuous-time versions of the “folk theorem” of evolutionary game theory to a bona fide algorithmic learning setting, and it provides a clear refinement criterion for the prediction of the day-to-day behavior of no-regret learning in games.
APA
Giannou, A., Vlatakis-Gkaragkounis, E.V. & Mertikopoulos, P.. (2021). Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:2147-2148 Available from https://proceedings.mlr.press/v134/giannou21a.html.

Related Material