Research map / Multi-agent systems and games / Games and equilibria

GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learning

NeurIPS 2026 · Multi-agent systems and games › Games and equilibria · approach: Learning in Markov games · 0 citations (OpenAlex)

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 Q-boosting, a variance-reduced advantage estimator using an Expected SARSA(λ) trace on a centralized Q-critic, and VRPO, a PPO-style self-play algorithm that outperforms baselines on exploitability benchmarks, Dou Dizhu, and HUNL.

Problem

Self-play policy-gradient RL in imperfect-information games suffers high advantage-estimation variance because GAE samples future stochastic actions, and this is amplified when equilibrium policies are stochastic, even with an exact critic.

Approach

Replace GAE's sampled multi-step TD trace with a multi-step Expected SARSA(λ) trace computed from a centralized Q-critic, averaging over the policy at each backup step so future action-sampling noise is removed; plug this into PPO's clipped objective (VRPO).

Key results

• On mid-sized games with exact exploitability, VRPO achieves more than 15% lower exploitability than all policy-gradient baselines (IPPO, MAPPO, MMD, PPG).
• In Dou Dizhu, VRPO surpasses PerfectDou after about 40% of its training timesteps; head-to-head gain of 0.152 ± 0.004 over PerfectDou and 0.286 ± 0.004 over DouZero.
• Against the 2022 Slumbot in HUNL200, VRPO achieves 33 ± 19 mBB/hand over 1,000,000 hands without search or subgame solving.

Surprising findings

• Recomputing the policy-expectation terms with current actor probabilities during actor updates adds negligible overhead.
• Removing the extra replay buffer for critic regression gives comparable exploitability, suggesting gains do not depend on off-policy critic replay.

Limitations

• Scope limited to discrete action sets; continuous high-dimensional action spaces are out of scope.
• Q-boosting trades action-sampling variance for critic approximation error; the variance guarantee needs a sufficiently accurate Q-critic.
• Against Slumbot the result (33 mBB/hand) is not a decisive win.

Experimental setup

Datasets: APTTT ADH3 LiDi 2D5F Dou Dizhu HUNL200

Benchmarks: APTTT ADH3 LiDi 2D5F Dou Dizhu HUNL200 vs Slumbot

Metrics: exact exploitability role-averaged gain (mBB or points) advantage standard deviation mBB/hand

Baselines: IPPO MAPPO MMD PPG PerfectDou DouZero Slumbot

Builds on: PPO generalized advantage estimation Expected SARSA MAPPO PerfectDou

Closest papers by meaning

• Provable Self-Play Algorithms for Competitive Reinforcement Learning (ICML 2020 · similarity 0.90)
• A Policy-Gradient Approach to Solving Imperfect-Information Games with Best-Iterate Convergence (ICLR 2025 · similarity 0.89)
• Learning Diverse Risk Preferences in Population-Based Self-Play (AAAI 2024 · similarity 0.88)
• Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.87)
• A2PO: Towards Effective Offline Reinforcement Learning from an Advantage-aware Perspective (NeurIPS 2024 · similarity 0.86)
• Self-Play $Q$-Learners Can Provably Collude in the Iterated Prisoner's Dilemma (ICML 2025 · similarity 0.86)