Lune

ICLR2025Top-tier venue

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

Mingyang Liu, Gabriele Farina, Asuman E. Ozdaglar

Abstract

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 theoreticallysound avoidance of importance sampling corrections. In multi-agent imperfectinformation 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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization cites Linear Last-iterate Convergence in Constrained Saddle-point Optimization
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. UFT: Unifying Supervised and Reinforcement Fine-TuningMingyang Liu, Gabriele Farina, Asuman OzdaglarNeurIPS 2025 · 61 citations

Builds on19

  1. Training language models to follow instructions with human feedbackLong Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida et al.NeurIPS 2022 · 24,707 citations
  2. Linear Last-iterate Convergence in Constrained Saddle-point OptimizationChen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, Haipeng LuoICLR 2021 · 146 citations
  3. Fast Policy Extragradient Methods for Competitive Games with Entropy RegularizationShicong Cen, Yuting Wei, Yuejie ChiNeurIPS 2021 · 105 citations
  4. From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via RegularizationJulien Pérolat, Rémi Munos, Jean-Baptiste Lespiau, Shayegan Omidshafiei et al.ICML 2021 · 102 citations
  5. Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror DescentGabriele Farina, Christian Kroer, Tuomas SandholmAAAI 2021 · 91 citations

Related papers

  1. Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic ConvergenceDongsheng Ding, Chen-Yu Wei, Kaiqing Zhang, Mihailo R. JovanovicICML 2022 · 84 citations
  2. Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit FeedbackCanzhe Zhao, Yutian Cheng, Jing Dong, Baoxiang Wang et al.ICML 2025
  3. Policy Gradient Methods Converge Globally in Imperfect-Information Extensive-Form GamesFivos Kalogiannis, Gabriele FarinaNeurIPS 2025 · 2 citations
  4. A Natural Actor-Critic Framework for Zero-Sum Markov GamesAhmet Alacaoglu, Luca Viano, Niao He, Volkan CevherICML 2022 · 24 citations
  5. On the convergence of policy gradient methods to Nash equilibria in general stochastic gamesAngeliki Giannou, Kyriakos Lotidis, Panayotis Mertikopoulos, Emmanouil V. Vlatakis-GkaragkounisNeurIPS 2022 · 28 citations
Dusk over the sea between two cliffs drawn in fine vertical lines