Research map / Multi-agent systems and games / Games and equilibria
A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes QFR, a policy-gradient method for two-player zero-sum extensive-form games that uses sampled trajectory Q-values and a bidilated regularizer to achieve best-iterate convergence to a regularized Nash equilibrium without importance sampling.
Problem
Whether policy gradient methods, which use rollout-based value estimates and iterate convergence, can be made theoretically sound for two-player zero-sum imperfect-information extensive-form games, where existing sound methods rely on counterfactual values and average strategies.
Approach
Uses trajectory Q-values (estimated by rollouts without importance sampling) together with a bidilated regularizer that weights each infoset's regularizer by the reach probabilities of all players, plus a depth-increasing learning rate schedule, in a regularized optimistic mirror descent update that yields best-iterate convergence.
Key results
- QFR outperforms outcome-sampling CFR/CFR+, MMD, and BalancedOMD in all four tested games in exploitability over 100 seeds.
- QFR outperforms BalancedFTRL in all games except Liar's Dice (QFR 0.174 vs BFTRL 0.167 exploitability on Liar's Dice).
- Theory gives sum of Bregman divergences to the regularized NE bounded by O(max eta T) + O(1/min eta), so with eta = Theta(1/sqrt T) an iterate with Bregman divergence O(1/sqrt T) exists.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use QFR instead of outcome-sampling CFR | tabular two-player zero-sum extensive-form games · 4-Sided Liar's Dice, Leduc Poker, Kuhn Poker, and 2×2 Abrupt Dark Hex | exploitability | Helped |
| use QFR instead of CFR+ | tabular two-player zero-sum extensive-form games · 4-Sided Liar's Dice, Leduc Poker, Kuhn Poker, and 2×2 Abrupt Dark Hex | exploitability | Helped |
| use QFR instead of MMD | tabular two-player zero-sum extensive-form games · 4-Sided Liar's Dice, Leduc Poker, Kuhn Poker, and 2×2 Abrupt Dark Hex | exploitability | Helped |
| use QFR instead of BOMD | tabular two-player zero-sum extensive-form games · 4-Sided Liar's Dice, Leduc Poker, Kuhn Poker, and 2×2 Abrupt Dark Hex | exploitability | Helped |
| use QFR instead of BFTRL | tabular two-player zero-sum extensive-form games · 4-Sided Liar's Dice | exploitability: QFR 0.174 v.s. BFTRL 0.167 | Hurt |
| use QFR instead of BFTRL | tabular two-player zero-sum extensive-form games · Leduc Poker, Kuhn Poker, and 2×2 Abrupt Dark Hex | exploitability | Helped |
Limitations
- Experiments are limited to small tabular games (Kuhn, Leduc, Liar's Dice, Dark Hex)
- Theory relies on regularized NE and needs annealing of tau to recover unregularized NE; the best-iterate guarantee needs learning-rate conditions with game-dependent constants
- Theorem requires learning rates to decrease with depth and a exploration constant gamma; the experiments use the same learning rate in all infosets, which the theory does not cover
Experimental setup
Benchmarks: 4-Sided Liar's Dice Leduc Poker Kuhn Poker 2x2 Abrupt Dark Hex
Metrics: exploitability
Baselines: Outcome-sampling CFR CFR+ MMD BalancedOMD BalancedFTRL
Builds on: Counterfactual Regret Minimization Regularized Optimistic Mirror Descent dilated regularizer MMD Outcome-Sampling MCCFR
Closest papers by meaning
- Policy Gradient Methods Converge Globally in Imperfect-Information Extensive-Form Games (NeurIPS 2025 · similarity 0.94)
- Learning Imperfect Information Extensive-form Games with Last-iterate Convergence under Bandit Feedback (ICML 2025 · similarity 0.93)
- Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.91)
- Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games (ICLR 2022 · similarity 0.91)
- On the convergence of policy gradient methods to Nash equilibria in general stochastic games (NeurIPS 2022 · similarity 0.91)
- Local and Adaptive Mirror Descents in Extensive-Form Games (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.