From Poincar\'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization

Autor:	Perolat, Julien, Munos, Remi, Lespiau, Jean-Baptiste, Omidshafiei, Shayegan, Rowland, Mark, Ortega, Pedro, Burch, Neil, Anthony, Thomas, Balduzzi, David, De Vylder, Bart, Piliouras, Georgios, Lanctot, Marc, Tuyls, Karl
Rok vydání:	2020
Předmět:	Computer Science - Computer Science and Game Theory Computer Science - Machine Learning Statistics - Machine Learning
Druh dokumentu:	Working Paper
Popis:	In this paper we investigate the Follow the Regularized Leader dynamics in sequential imperfect information games (IIG). We generalize existing results of Poincar\'e 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). Comment: 43 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2002.08456 Zobrazit plný text záznamu View this record from Arxiv