mlsanityData to 7 Oct 2026

A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence

arXiv 2408.00751 ↗First posted 1 Aug 2024cs.GT cs.AI cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

Policy gradient methods have become a staple of any single-agent reinforcement learning toolbox, due to their combination of desirable properties: iterate convergence, efficient use of stochastic trajectory feedback, and theoretically-sound avoidance of importance sampling corrections. In multi-agent imperfect-information settings (extensive-form games), however, it is still unknown whether the same desiderata can be guaranteed while retaining theoretical guarantees. Instead, sound methods for extensive-form games rely on approximating counterfactual values (as opposed to Q values), which are incompatible with policy gradient methodologies. In this paper, we investigate whether policy gradient can be safely used in two-player zero-sum imperfect-information extensive-form games (EFGs). We establish positive results, showing for the first time that a policy gradient method leads to provable best-iterate convergence to a regularized Nash equilibrium in self-play.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 35 of its 51 references that are in the map. First posted on arXiv 1 Aug 2024.

Builds on

35 of 51 references.

References · 35

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  4. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  5. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 698
  6. 2021How to Train Your Robot with Deep Reinforcement Learning; Lessons We've Learnedcited by 201
  7. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  8. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  9. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 129
  10. 2018Deep Counterfactual Regret Minimizationcited by 102
  11. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  12. 2019Open-ended Learning in Symmetric Zero-sum Gamescited by 96
23 more
  1. 2018Solving Imperfect-Information Games via Discounted Regret Minimizationcited by 68
  2. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  3. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  4. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 59
  5. 2020Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descentcited by 56
  6. 2020DREAM: Deep Regret minimization with Advantage baselines and Model-free learningcited by 36
  7. 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 30
  8. 2021Last-iterate Convergence in Extensive-Form Gamescited by 27
  9. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  10. 2019Optimistic Regret Minimization for Extensive-Form Games via Dilated Distance-Generating Functionscited by 25
  11. 2018Variance Reduction in Monte Carlo Counterfactual Regret Minimization (VR-MCCFR) for Extensive Form Games using Baselinescited by 24
  12. 2022ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regretcited by 24
  13. 2019Stable-Predictive Optimistic Counterfactual Regret Minimizationcited by 21
  14. 2022The Power of Regularization in Solving Extensive-Form Gamescited by 21
  15. 2019Single Deep Counterfactual Regret Minimizationcited by 20
  16. 2022Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalitiescited by 18
  17. 2020Stochastic Regret Minimization in Extensive-Form Gamescited by 17
  18. 2020The Advantage Regret-Matching Actor-Criticcited by 17
  19. 2021Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Gamescited by 15
  20. 2021Model-Free Online Learning in Unknown Sequential Decision Making Problems and Gamescited by 12
  21. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  22. 2021Equivalence Analysis between Counterfactual Regret Minimization and Online Mirror Descentcited by 7
  23. 2023Local and adaptive mirror descents in extensive-form gamescited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 2.

5 papers.

  1. 2025UFT: Unifying Supervised and Reinforcement Fine-Tuningcited by 58
  2. 2024On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Gamescited by 2
  3. 2025Differentially Private Equilibrium Finding in Polymatrix Gamescited by 0
  4. 2026GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learningcited by 0
  5. 2026Self-Play Reinforcement Learning under Imperfect Information in Big 2cited by 0