From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization

Julien Perolat, Remi Munos, Jean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, Georgios Piliouras, Marc Lanctot, Karl Tuyls
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:8525-8535, 2021.

Abstract

In this paper we investigate the Follow the Regularized Leader dynamics in sequential imperfect information games (IIG). We generalize existing results of Poincar{é} recurrence from normal-form games to zero-sum two-player imperfect information games and other sequential game settings. We then investigate how adapting the reward (by adding a regularization term) of the game can give strong convergence guarantees in monotone games. We continue by showing how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium. Finally, we show how these insights can be directly used to build state-of-the-art model-free algorithms for zero-sum two-player Imperfect Information Games (IIG).

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-perolat21a, title = {From Poincar{é} Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization}, author = {Perolat, Julien and Munos, Remi and Lespiau, Jean-Baptiste and Omidshafiei, Shayegan and Rowland, Mark and Ortega, Pedro and Burch, Neil and Anthony, Thomas and Balduzzi, David and De Vylder, Bart and Piliouras, Georgios and Lanctot, Marc and Tuyls, Karl}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {8525--8535}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/perolat21a/perolat21a.pdf}, url = {https://proceedings.mlr.press/v139/perolat21a.html}, abstract = {In this paper we investigate the Follow the Regularized Leader dynamics in sequential imperfect information games (IIG). We generalize existing results of Poincar{é} recurrence from normal-form games to zero-sum two-player imperfect information games and other sequential game settings. We then investigate how adapting the reward (by adding a regularization term) of the game can give strong convergence guarantees in monotone games. We continue by showing how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium. Finally, we show how these insights can be directly used to build state-of-the-art model-free algorithms for zero-sum two-player Imperfect Information Games (IIG).} }
Endnote
%0 Conference Paper %T From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization %A Julien Perolat %A Remi Munos %A Jean-Baptiste Lespiau %A Shayegan Omidshafiei %A Mark Rowland %A Pedro Ortega %A Neil Burch %A Thomas Anthony %A David Balduzzi %A Bart De Vylder %A Georgios Piliouras %A Marc Lanctot %A Karl Tuyls %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-perolat21a %I PMLR %P 8525--8535 %U https://proceedings.mlr.press/v139/perolat21a.html %V 139 %X In this paper we investigate the Follow the Regularized Leader dynamics in sequential imperfect information games (IIG). We generalize existing results of Poincar{é} recurrence from normal-form games to zero-sum two-player imperfect information games and other sequential game settings. We then investigate how adapting the reward (by adding a regularization term) of the game can give strong convergence guarantees in monotone games. We continue by showing how this reward adaptation technique can be leveraged to build algorithms that converge exactly to the Nash equilibrium. Finally, we show how these insights can be directly used to build state-of-the-art model-free algorithms for zero-sum two-player Imperfect Information Games (IIG).
APA
Perolat, J., Munos, R., Lespiau, J., Omidshafiei, S., Rowland, M., Ortega, P., Burch, N., Anthony, T., Balduzzi, D., De Vylder, B., Piliouras, G., Lanctot, M. & Tuyls, K.. (2021). From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:8525-8535 Available from https://proceedings.mlr.press/v139/perolat21a.html.

Related Material