GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learning
Zhiyuan Fan, Gabriele Farina · 2026
Read GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learning by Zhiyuan Fan, Gabriele Farina (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19235.txt.
Introduction
Zhiyuan Fan and Gabriele Farina diagnose a flaw in advantage estimation for self-play learning in games with hidden information. Random future actions inflate variance in the usual estimator, and the noise survives even with a perfect critic. Their VRPO method replaces sampled backups with a variance-reduced estimator built on a central action-value critic. Tests on mid-size and large games, including Dou Dizhu and no-limit Texas Hold'em, show consistently strong play.
Catalog record
| CREATOR | Zhiyuan Fan, Gabriele Farina |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89514 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.19235
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
GAE Falls Short in Imperfect-Information Self-Play Reinforcement Learning Zhiyuan Fan, Gabriele Farina Abstract Competitive multi-agent reinforcement learning in imperfect-information games requires agents to act under partial observability and against adversarial opponents, necessitating stochastic policies. While self-play reinforcement learning with Proximal Policy Optimization (PPO) has achieved strong empirical success, its standard advantage estimator, generalized advantage estimation, suffers from additional variance due to the sampling of stochastic future actions. This variance is amplified in equilibrium self-play because of the stochastic nature of the equilibrium policy and persists even when the critic is exact. We address this bottleneck by introducing 𝑸 \bm{Q} -boosting , a variance-reduced advantage estimator based on a centralized action-value critic, and propose Variance-Reduced Policy Optimization (VRPO) , incorporating this new estimator. The algorithm replaces sampled multi-step backups with a multi-step Expected SARSA ( λ ) (\lambda) trace, computing policy expectations at each step to average out action-sampling noise, while retaining PPO’s clipped objective and on-policy actor updates. Empirically, VRPO consistently achieves strong performance from mid-sized to large-scale games including Dou Dizhu and Heads-Up No-Limit Texas Hold’em. 1 Introduction Multi-agent reinforcement learning (MARL) is a central challenge in reinforcement learning, where multiple agents interact competitively under imperfect information. During gameplay, players must take actions based only on the private information they observe. The outcome of the game is determined by both the hidden states and the actions of the opponents. Learning policies with equilibrium-like robustness is a common goal in such games. This can be formulated as learning a policy that maximizes reward against the most adversarial opponent. However, such equilibrium concepts are generally intractable, and the best response is difficult to evaluate in large-scale games. Therefore, performance is often evaluated using heads-up play against a fixed opponent that is not encountered during training. This problem is challenging for two main reasons. First, the agent needs to act under partial observability, which requires implicit reasoning about the hidden states of the opponents. Second, we want a policy that is robust to adaptive opponents, meaning that the training process needs to account for adversarial gameplay, even when such strategies may be far from the final policy. These challenges have motivated two broad paradigms: regret minimization and self-play RL. The first line of work is based on Counterfactual Regret Minimization (CFR) [ 39 ] . The algorithm provably converges to Nash equilibria in two-player zero-sum games. This approach is considered a leading method for solving extensive-form games such as No-Limit Texas Hold’em [ 5 ] . Follow-up methods such as Deep CFR [ 4 ] and ReBeL [ 3 ] build on neural networks to approximate regrets and values, enabling the algorithms to scale to larger game trees and achieve strong performance in poker. However, CFR-style methods can still struggle to scale in games such as Stratego or Dou Dizhu due to their large private-information spaces, long gameplay trajectories, and large action sets. These features make it difficult to expand the extensive-form game tree from any position, and thus regret minimization is considered both computationally and statistically inefficient in such settings. The other, complementary line of work is based on Self-Play Reinforcement Learning (Self-play RL) , where policies are directly optimized using policy gradient methods. These algorithms have shown effectiveness in environments with vast private information, including Stratego [ 19 , 28 ] and Dou Dizhu [ 37 , 34 ] . A recent line of work suggests that self-play can approximate equilibria in small games where the exact equilibrium can be directly evaluated, both theoretically [ 16 , 15 ] and empirically [ 22 ] . Among policy gradient methods, Proximal Policy Optimization (PPO) [ 24 ] , deployed under the centralized training with decentralized execution (CTDE) paradigm is a widely used and competitive pipeline, where decentralized actors are trained using centralized critics [ 35 ] . However, even with its success, self-play RL still cannot achieve fully end-to-end training in games with a large dynamic range of payoffs, such as No-Limit Texas Hold’em. Existing work [ 38 ] has achieved strong results in HUNL, but still relies on restricted betting-action representations to handle the large dynamic range of rewards. In this paper, we identify a new bottleneck of self-play RL in imperfect-information games: advantage-estimation variance . PPO-style algorithms use Generalized Advantage Estimation (GAE) [ 23 ] to aggregate multi-step temporal-difference residuals along sampled trajectories, thereby estimating the advantage with a variance–bias trade-off. GAE inherits randomness from future actions sampled in the multi-step trace. While this may not be a problem in single-agent settings, this noise is amplified in self-play RL, where equilibrium policies are generally stochastic and assign different values to different actions. Consequently, standard GAE can produce high-variance gradient estimates precisely in the regimes where stable learning is most critical. We propose the \bm{Q} -boosting estimator to address this problem. This estimator reduces the variance of advantage estimation by removing intrinsic action-sampling noise, replacing GAE’s sampled multi-step backup with a multi-step Expected SARSA (\lambda) trace computed from a centralized Q -critic. Instead of bootstrapping through sampled next actions, Q -boosting takes policy expectations at each backup step, averaging out noise from stochastic future actions. We introduce Variance-Reduced Policy Optimization (VRPO) based on this new estimator. VRPO is a PPO-style algorithm with improved stability that achieves strong empirical performance: it consistently achieves lower exploitability than other PPO-based baselines on mid-sized benchmarks where exploitability is computable, and appears to achieve strong heads-up performance in larger real-world games such as Dou Dizhu and No-Limit Texas Hold’em. The results suggest that reducing variance in advantage estimation can yield substantial gains in equilibrium-quality self-play. To summarize, our main contributions are: • We identify an additional source of variance in GAE arising from sampled future actions in stochastic self-play. We show that this variance persists even with an exact state-value critic, and derive Q -boosting: a PPO-compatible advantage estimator that applies an Expected SARSA( \lambda ) trace to a centralized Q -critic to average out future action-sampling noise. • We propose Variance-Reduced Policy Optimization (VRPO) , a PPO-style algorithm that surpasses various baselines in self-play RL. In Dou Dizhu, VRPO outperforms the previous state-of-the-art agent, PerfectDou [ 34 ] , under a matched training budget. In heads-up no-limit Texas Hold’em, VRPO achieves positive performance against Slumbot, a strong poker baseline, without online search, subgame solving, or blueprint-based raise sizing. 2 Preliminary 2.1 Multiplayer Imperfect Information Game We consider zero-sum multiplayer games with imperfect information, discrete time, and discrete action sets. Unlike cooperative MARL, we focus on competitive zero-sum settings, where the sum of players’ returns is zero and equilibrium quality is measured by unilateral deviation gains. This setting captures a broad class of competitive decision-making problems, including many classical board games. Let n denote the number of players, and let \mathcal{S} be the set of all distinct states. We model simultaneous steps, when present, as sequences of imperfect-information states while preserving the original information structure; players do not observe actions or hidden variables that would be unavailable in the original game. We also explicitly resolve all environmental randomness and model stochastic transitions (e.g., card draws) by introducing a special player, Nature , who follows a fixed policy. This modeling still allows for a random starting