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

arXiv: https://arxiv.org/abs/2002.08456 · HTML: https://mlsanity.com/paper/2002.08456/

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2020.

## Built on by (most cited first, 30 of 61)

- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Games](https://mlsanity.com/paper/2206.05825/) (2022)
- [Scalable Deep Reinforcement Learning Algorithms for Mean Field Games](https://mlsanity.com/paper/2203.11973/) (2022)
- [Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization](https://mlsanity.com/paper/2103.04564/) (2021)
- [Adversarial Policies Beat Superhuman Go AIs](https://mlsanity.com/paper/2211.00241/) (2022)
- [Policy Mirror Ascent for Efficient and Independent Learning in Mean Field Games](https://mlsanity.com/paper/2212.14449/) (2022)
- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [Student of Games: A unified learning algorithm for both perfect and imperfect information games](https://mlsanity.com/paper/2112.03178/) (2021)
- [Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality](https://mlsanity.com/paper/2106.12928/) (2021)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPs](https://mlsanity.com/paper/2302.01275/) (2023)
- [Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignment](https://mlsanity.com/paper/2410.16714/) (2024)
- [Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2102.08903/) (2021)
- [Reevaluating Policy Gradient Methods for Imperfect-Information Games](https://mlsanity.com/paper/2502.08938/) (2025)
- [Complex Momentum for Optimization in Games](https://mlsanity.com/paper/2102.08431/) (2021)
- [Learning in Matrix Games can be Arbitrarily Complex](https://mlsanity.com/paper/2103.03405/) (2021)
- [Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2207.06541/) (2022)
- [Online Learning in Periodic Zero-Sum Games](https://mlsanity.com/paper/2111.03377/) (2021)
- [RL-CFR: Improving Action Abstraction for Imperfect Information Extensive-Form Games with Reinforcement Learning](https://mlsanity.com/paper/2403.04344/) (2024)
- [Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions](https://mlsanity.com/paper/2207.12463/) (2022)
- [Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2208.09855/) (2022)
- [Adaptively Perturbed Mirror Descent for Learning in Games](https://mlsanity.com/paper/2305.16610/) (2023)
- [Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent](https://mlsanity.com/paper/2101.05248/) (2021)
- [Search in Imperfect Information Games](https://mlsanity.com/paper/2111.05884/) (2021)
- [Mutation-Driven Follow the Regularized Leader for Last-Iterate Convergence in Zero-Sum Games](https://mlsanity.com/paper/2206.09254/) (2022)
- [COMAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences](https://mlsanity.com/paper/2410.23223/) (2024)
- [Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RL](https://mlsanity.com/paper/2305.17342/) (2023)
- [Minimizing Weighted Counterfactual Regret with Optimistic Online Mirror Descent](https://mlsanity.com/paper/2404.13891/) (2024)
- [Abstracting Imperfect Information Away from Two-Player Zero-Sum Games](https://mlsanity.com/paper/2301.09159/) (2023)

## Abstract (arXiv)

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).