mlsanityData to 14 Oct 2026

The Power of Regularization in Solving Extensive-Form Games

arXiv 2206.09495 ↗First posted 19 Jun 2022cs.GT cs.LGcited by 21

Not on the map. Why?

Abstract (arXiv)

In this paper, we investigate the power of it regularization, a common technique in reinforcement learning and optimization, in solving extensive-form games (EFGs). We propose a series of new algorithms based on regularizing the payoff functions of the game, and establish a set of convergence results that strictly improve over the existing ones, with either weaker assumptions or stronger convergence guarantees. In particular, we first show that dilated optimistic mirror descent (DOMD), an efficient variant of OMD for solving EFGs, with adaptive regularization can achieve a fast tilde O(1/T) last-iterate convergence rate for the output of the algorithm in terms of duality gap and distance to the set of Nash equilibrium (NE) without uniqueness assumption of the NE. Second, we show that regularized counterfactual regret minimization (textttReg-CFR), with a variant of optimistic mirror descent algorithm as regret-minimizer, can achieve O(1/T1/4) best-iterate, and O(1/T3/4) average-iterate convergence rate for finding NE in EFGs. Finally, we show that textttReg-CFR can achieve asymptotic last-iterate convergence, and optimal O(1/T) average-iterate convergence rate, for finding the NE of perturbed EFGs, which is useful for finding approximate extensive-form perfect equilibria (EFPE). To the best of our knowledge, they constitute the first last-iterate convergence results for CFR-type algorithms, while matching the state-of-the-art average-iterate convergence rate in finding NE for non-perturbed EFGs. We also provide numerical results to corroborate the advantages of our algorithms.

Key facts. Cited by 21 papers in the map (data through 14 Oct 2026). Builds on 34 of its 70 references that are in the map. First posted on arXiv 19 Jun 2022.

Builds on

34 of 70 references.

References · 34

  1. 2019A Theory of Regularized Markov Decision Processescited by 286
  2. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  3. 2017Training GANs with Optimismcited by 217
  4. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  5. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  6. 2015Fast Convergence of Regularized Learning in Gamescited by 150
  7. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 143
  8. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 136
  9. 2017Cycles in adversarial regularized learningcited by 124
  10. 2018Deep Counterfactual Regret Minimizationcited by 103
  11. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 98
  12. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
22 more
  1. 2018Solving Imperfect-Information Games via Discounted Regret Minimizationcited by 68
  2. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 63
  3. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 61
  4. 2021Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibriumcited by 51
  5. 2020DREAM: Deep Regret minimization with Advantage baselines and Model-free learningcited by 36
  6. 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 31
  7. 2021Last-iterate Convergence in Extensive-Form Gamescited by 28
  8. 2019Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functionscited by 26
  9. 2018Online Convex Optimization for Sequential Decision Processes and Extensive-Form Gamescited by 21
  10. 2019Stable-Predictive Optimistic Counterfactual Regret Minimizationcited by 21
  11. 2020Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapescited by 21
  12. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  13. 2021Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationalitycited by 21
  14. 2019Single Deep Counterfactual Regret Minimizationcited by 20
  15. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 19
  16. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  17. 2020Joint Policy Search for Multi-agent Collaboration with Imperfect Informationcited by 13
  18. 2021Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibriacited by 13
  19. 2017Smoothing Method for Approximate Extensive-Form Perfect Equilibriumcited by 4
  20. 2020Finding the Near Optimal Policy via Adaptive Reduced Regularization in MDPscited by 4
  21. 2017Regret Minimization in Behaviorally-Constrained Zero-Sum Gamescited by 3
  22. 2016Extensive-Form Perfect Equilibrium Computation in Two-Player Gamescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 2; 2023: 4; 2024: 6; 2025: 7; 2026: 2.

21 papers.

Sort:

By area:

  1. 2025UFT: Unifying Supervised and Reinforcement Fine-Tuningcited by 59
  2. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 10
  3. 2024RL-CFR: Improving Action Abstraction for Imperfect Information Extensive-Form Games with Reinforcement Learningcited by 10
  4. 2022Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Gamescited by 9
  5. 2023Adaptively Perturbed Mirror Descent for Learning in Gamescited by 9
  6. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 8
  7. 2024A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergencecited by 5
  8. 2025RSPO: Regularized Self-Play Alignment of Large Language Modelscited by 5
  9. 2022Near-Optimal Phi-Regret Learning in Extensive-Form Gamescited by 3
  10. 2024LiteEFG: An Efficient Python Library for Solving Extensive-form Gamescited by 3
  11. 2025Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Gamescited by 3
  12. 2023Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Propertycited by 2
9 more
  1. 2024On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Gamescited by 2
  2. 2025NashPG: A Policy Gradient Method with Iteratively Refined Regularization for Finding Nash Equilibriacited by 2
  3. 2026Online Learning and Equilibrium Computation with Ranking Feedbackcited by 2
  4. 2024Configurable Mirror Descent: Towards a Unification of Decision Makingcited by 1
  5. 2024TrafficGamer: Reliable and Flexible Traffic Simulation for Safety-Critical Scenarios with Game-Theoretic Oraclescited by 1
  6. 2025Convergence and Connectivity: Dynamics of Multi-Agent Q-Learning in Random Networkscited by 1
  7. 2023Efficient Last-iterate Convergence Algorithms in Solving Gamescited by 0
  8. 2025Efficient Last-Iterate Convergence in Regret Minimization via Adaptive Reward Transformationcited by 0
  9. 2026GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learningcited by 0