# Last-iterate Convergence in Extensive-Form Games

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 54 references that are in the map.
- First posted on arXiv 27 Jun 2021.

## Builds on (most cited first, 19 of 19)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Deep Reinforcement Learning from Self-Play in Imperfect-Information Games](https://mlsanity.com/paper/1603.01121/) (2016)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/1811.00164/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent](https://mlsanity.com/paper/2007.14358/) (2020)
- [Solving Imperfect Information Games Using Decomposition](https://mlsanity.com/paper/1303.4441/) (2013)
- [Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functions](https://mlsanity.com/paper/1910.10906/) (2019)
- [Stable-Predictive Optimistic Counterfactual Regret Minimization](https://mlsanity.com/paper/1902.04982/) (2019)
- [Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes](https://mlsanity.com/paper/2002.06768/) (2020)
- [Revisiting CFR+ and Alternating Updates](https://mlsanity.com/paper/1810.11542/) (2018)
- [Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria](https://mlsanity.com/paper/2105.12954/) (2021)
- [Robust Stackelberg Equilibria in Extensive-Form Games and Extension to Limited Lookahead](https://mlsanity.com/paper/1711.08080/) (2017)
- [Smoothing Method for Approximate Extensive-Form Perfect Equilibrium](https://mlsanity.com/paper/1705.09326/) (2017)

## Built on by (most cited first, 28 of 28)

- [Near-Optimal Learning of Extensive-Form Games with Imperfect Information](https://mlsanity.com/paper/2202.01752/) (2022)
- [Improving LLM General Preference Alignment via Optimistic Online Mirror Descent](https://mlsanity.com/paper/2502.16852/) (2025)
- [The Power of Regularization in Solving Extensive-Form Games](https://mlsanity.com/paper/2206.09495/) (2022)
- [Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games](https://mlsanity.com/paper/2202.00237/) (2022)
- [Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback](https://mlsanity.com/paper/2112.02856/) (2021)
- [Policy Space Diversity for Non-Transitive Games](https://mlsanity.com/paper/2306.16884/) (2023)
- [Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms](https://mlsanity.com/paper/2406.10631/) (2024)
- [Adapting to game trees in zero-sum imperfect information games](https://mlsanity.com/paper/2212.12567/) (2022)
- [Mastering Strategy Card Game (Hearthstone) with Improved Techniques](https://mlsanity.com/paper/2303.05197/) (2023)
- [Can We Find Nash Equilibria at a Linear Rate in Markov Games?](https://mlsanity.com/paper/2303.03095/) (2023)
- [Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games](https://mlsanity.com/paper/2311.00676/) (2023)
- [Asynchronous Gradient Play in Zero-Sum Multi-agent Games](https://mlsanity.com/paper/2211.08980/) (2022)
- [A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence](https://mlsanity.com/paper/2408.00751/) (2024)
- [Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games](https://mlsanity.com/paper/2207.08426/) (2022)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [LiteEFG: An Efficient Python Library for Solving Extensive-form Games](https://mlsanity.com/paper/2407.20351/) (2024)
- [Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games](https://mlsanity.com/paper/2510.04407/) (2025)
- [Local and adaptive mirror descents in extensive-form games](https://mlsanity.com/paper/2309.00656/) (2023)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games](https://mlsanity.com/paper/2410.23398/) (2024)
- [Unified Policy Optimization for Continuous-action Reinforcement Learning in Non-stationary Tasks and Games](https://mlsanity.com/paper/2208.09452/) (2022)
- [Configurable Mirror Descent: Towards a Unification of Decision Making](https://mlsanity.com/paper/2405.11746/) (2024)
- [On the Power of Perturbation under Sampling in Solving Extensive-Form Games](https://mlsanity.com/paper/2501.16600/) (2025)
- [Efficient Last-iterate Convergence Algorithms in Solving Games](https://mlsanity.com/paper/2308.11256/) (2023)
- [Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformation](https://mlsanity.com/paper/2509.13653/) (2025)
- [Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback](https://mlsanity.com/paper/2512.24818/) (2025)
- [Last-Iterate Convergence of Optimistic Multiplicative Weight Update](https://mlsanity.com/paper/2606.11773/) (2026)
- [IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence](https://mlsanity.com/paper/2610.19016/) (2026)

## Abstract (arXiv)

Regret-based algorithms are highly efficient at finding approximate Nash equilibria in sequential games such as poker games. However, most regret-based algorithms, including counterfactual regret minimization (CFR) and its variants, rely on iterate averaging to achieve convergence. Inspired by recent advances on last-iterate convergence of optimistic algorithms in zero-sum normal-form games, we study this phenomenon in sequential games, and provide a comprehensive study of last-iterate convergence for zero-sum extensive-form games with perfect recall (EFGs), using various optimistic regret-minimization algorithms over treeplexes. This includes algorithms using the vanilla entropy or squared Euclidean norm regularizers, as well as their dilated versions which admit more efficient implementation. In contrast to CFR, we show that all of these algorithms enjoy last-iterate convergence, with some of them even converging exponentially fast. We also provide experiments to further support our theoretical results.