From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization
arXiv:2002.08456
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).
arXiv comment43 pages
References in corpus (11)
- IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
- The Numerics of GANs
- Deep Reinforcement Learning from Self-Play in Imperfect-Information Games
- Fast Convergence of Regularized Learning in Games
- OpenSpiel: A Framework for Reinforcement Learning in Games
- A Theory of Regularized Markov Decision Processes
- Actor-Critic Policy Optimization in Partially Observable Multiagent Environments
- Value Function Approximation in Zero-Sum Markov Games
- GANGs: Generative Adversarial Network Games
- Negative Momentum for Improved Game Dynamics
- Modeling Friends and Foes
Cited by in corpus (9)
- Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning
- Learning to Play No-Press Diplomacy with Best Response Policy Iteration
- No-regret learning and mixed Nash equilibria: They do not mix
- Neural Replicator Dynamics
- DREAM: Deep Regret minimization with Advantage baselines and Model-free learning
- Learning in Matrix Games can be Arbitrarily Complex
- Search in Imperfect Information Games
- Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence
- Complex Momentum for Optimization in Games