mlsanityData to 14 Oct 2026

Last-iterate Convergence in Extensive-Form Games

arXiv 2106.14326 ↗First posted 27 Jun 2021cs.LGcited by 28

Not on the map. Why?

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.

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

19 of 54 references.

References · 19

  1. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 233
  2. 2017Training GANs with Optimismcited by 217
  3. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  4. 2016Deep Reinforcement Learning from Self-Play in Imperfect-Information Gamescited by 158
  5. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  6. 2017Cycles in adversarial regularized learningcited by 124
  7. 2018Deep Counterfactual Regret Minimizationcited by 103
  8. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  9. 2014Solving Large Imperfect Information Games Using CFR+cited by 78
  10. 2018Solving Imperfect-Information Games via Discounted Regret Minimizationcited by 68
  11. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 57
  12. 2013Solving Imperfect Information Games Using Decompositioncited by 29
7 more
  1. 2019Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functionscited by 26
  2. 2019Stable-Predictive Optimistic Counterfactual Regret Minimizationcited by 21
  3. 2020Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapescited by 21
  4. 2018Revisiting CFR+ and Alternating Updatescited by 19
  5. 2021Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibriacited by 13
  6. 2017Robust Stackelberg Equilibria in Extensive-Form Games and Extension to Limited Lookaheadcited by 5
  7. 2017Smoothing Method for Approximate Extensive-Form Perfect Equilibriumcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 8; 2023: 7; 2024: 5; 2025: 5; 2026: 2.

28 papers.

Sort:

By area:

  1. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  2. 2025Improving LLM General Preference Alignment via Optimistic Online Mirror Descentcited by 24
  3. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  4. 2022Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Gamescited by 19
  5. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 15
  6. 2023Policy Space Diversity for Non-Transitive Gamescited by 15
  7. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  8. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  9. 2023Mastering Strategy Card Game (Hearthstone) with Improved Techniquescited by 10
  10. 2023Can We Find Nash Equilibria at a Linear Rate in Markov Games?cited by 9
  11. 2023Last-Iterate Convergence Properties of Regret-Matching Algorithms in Gamescited by 6
  12. 2022Asynchronous Gradient Play in Zero-Sum Multi-agent Gamescited by 5
16 more
  1. 2024A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergencecited by 5
  2. 2022Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Gamescited by 4
  3. 2022A Survey of Decision Making in Adversarial Gamescited by 3
  4. 2024LiteEFG: An Efficient Python Library for Solving Extensive-form Gamescited by 3
  5. 2025Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Gamescited by 3
  6. 2023Local and adaptive mirror descents in extensive-form gamescited by 2
  7. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
  8. 2024On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Gamescited by 2
  9. 2022Unified Policy Optimization for Continuous-action Reinforcement Learning in Non-stationary Tasks and Gamescited by 1
  10. 2024Configurable Mirror Descent: Towards a Unification of Decision Makingcited by 1
  11. 2025On the Power of Perturbation under Sampling in Solving Extensive-Form Gamescited by 1
  12. 2023Efficient Last-iterate Convergence Algorithms in Solving Gamescited by 0
  13. 2025Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformationcited by 0
  14. 2025Unregularized Linear Convergence in Zero-Sum Game from Preference Feedbackcited by 0
  15. 2026Last-Iterate Convergence of Optimistic Multiplicative Weight Updatecited by 0
  16. 2026IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergencecited by 0