Technical Summary: GAE Falls Short in Imperfect-Information Self-Play

Problem Statement

Competitive multi-agent reinforcement learning (MARL) in imperfect-information games requires agents to operate under partial observability against adversarial opponents, necessitating stochastic policies. While self-play reinforcement learning using Proximal Policy Optimization (PPO) has achieved empirical success, it faces a critical bottleneck in equilibrium learning: advantage-estimation variance.

Standard PPO implementations rely on Generalized Advantage Estimation (GAE) to aggregate multi-step temporal-difference (TD) residuals. In single-agent settings, GAE effectively balances bias and variance. However, in imperfect-information self-play, equilibrium policies are inherently stochastic. GAE inherits randomness from the sampling of future actions within its multi-step trace. Because equilibrium policies assign different values to different actions, the sampling of future actions introduces intrinsic noise. This variance is amplified in self-play scenarios and persists even when the state-value critic ($V$-critic) is exact. Consequently, standard GAE produces high-variance gradient estimates precisely in the regimes where stable learning is most critical, hindering the convergence to high-quality equilibria.

Methodology

Q-Boosting Estimator

To address the variance introduced by action sampling, the authors propose Q-boosting, a variance-reduced advantage estimator. The core innovation is replacing the sampled multi-step TD trace used in GAE with a multi-step Expected SARSA($\lambda$) trace computed from a centralized action-value critic ($Q$-critic).

• Mechanism: Instead of bootstrapping through sampled next actions (which introduces noise), Q-boosting computes policy expectations at each backup step. It averages out the noise from stochastic future actions by taking the expectation over the action distribution defined by the current policy.
• Formulation: Given a centralized $Q$-critic $Q_i(s, a)$ and a joint policy $\pi$, the state value is computed as $V^\pi_i(s) = \sum_a \pi(a|s) Q_i(s, a)$. The Q-boosting advantage estimate $\hat{A}^{boost}_{i,\tau}$ is defined as:
  $$\hat{A}^{boost}_{i,\tau} \triangleq Q_i(s_\tau, a_\tau) - V^\pi_i(s_\tau) + \sum_{\tau' \ge \tau} (\lambda\gamma)^{\tau'-\tau} \cdot \delta^+_{i,\tau'}$$
  where the Expected SARSA TD residual is $\delta^+_{i,\tau'} \triangleq r_{i}(s_{\tau'}, a_{\tau'}) + \gamma V^\pi_i(s_{\tau'+1}) - Q_i(s_{\tau'}, a_{\tau'})$.
• Theoretical Guarantee: The authors prove that for on-policy trajectories and $\lambda=1$, the Q-boosting estimator provides an unbiased estimate of the score-function policy-gradient term. Furthermore, if the $Q$-critic is sufficiently accurate, the mean-squared error of the Q-boosting estimator is strictly lower than that of GAE with an exact $V$-critic, provided that future actions exhibit non-zero variance in their action values.

Variance-Reduced Policy Optimization (VRPO)

The authors integrate Q-boosting into a PPO-style algorithm named Variance-Reduced Policy Optimization (VRPO).

• Architecture: VRPO follows the Centralized Training with Decentralized Execution (CTDE) paradigm. It utilizes decentralized actors for execution and a centralized $Q$-critic for training.
• Objective: The algorithm retains PPO's clipped surrogate objective and trust-region updates but modifies the advantage estimation and critic learning procedures.
• Training Procedure:
  1. Actor Update: Actors are updated using the Q-boosting advantage estimates. To maintain on-policy properties, the policy expectation terms in the advantage calculation are recomputed using current actor probabilities while keeping critic values fixed.
  2. Critic Update: The centralized $Q$-critics are trained by minimizing the squared regression loss against the Q-boosting target (a multi-step Expected SARSA trace).
  3. Regularization: An explicit KL-divergence penalty relative to a uniform distribution is added to the policy objective to promote exploration and encourage last-iterate convergence.
• Handling Large Action Spaces: For games with massive action sets (e.g., Dou Dizhu), the authors decompose complex decisions into multiple time steps. This reduces the number of available actions per step to a manageable size, allowing the enumeration required for the policy expectation in the $Q$-boosting trace.

Key Contributions

1. Identification of Variance Source: The paper identifies that the sampling of future actions in GAE introduces additional variance in stochastic self-play, which persists even with exact value functions.
2. Q-Boosting Estimator: The authors derive Q-boosting, a PPO-compatible estimator that applies an Expected SARSA($\lambda$) trace to a centralized $Q$-critic to average out future action-sampling noise.
3. VRPO Algorithm: The proposal of VRPO, a PPO-style algorithm that leverages Q-boosting to achieve improved stability and performance.
4. Empirical Validation: Demonstration that reducing advantage estimation variance yields substantial gains in equilibrium quality across games of varying scales.

Experimental Results

Mid-Sized Games (Exact Exploitability)

The authors benchmarked VRPO on mid-sized games where exact exploitability can be computed: Abrupt Phantom Tic-Tac-Toe (APTTT), Abrupt Dark Hex 3 (ADH3), and Liar's Dice with 2 Dice and 5 Faces (LiDi 2D5F).

• Performance: VRPO consistently achieved more than 15% lower exploitability compared to various PPO-based baselines (IPPO, MAPPO, MMD, PPG) under a shared training schedule.
• Ablation: Experiments confirmed that the performance gains are robust across different trace parameters ($\lambda$), regularization coefficients ($\alpha$), and PPO clipping coefficients ($\epsilon$).

Large-Scale Games

The authors evaluated VRPO in large-scale domains where exact exploitability is intractable.

• Dou Dizhu: VRPO was trained against the previous state-of-the-art agent, PerfectDou. Under a matched training budget ($\approx 2.65 \times 10^9$ timesteps), VRPO surpassed PerfectDou after only 40% of the training steps. In head-to-head evaluations over 100,000 deals, VRPO achieved positive gains against PerfectDou, DouZero, and itself (in role-swapped matchups), establishing a new state of the art.
• Heads-Up No-Limit Texas Hold'em (HUNL): VRPO was trained on HUNL with a 200 big-blind stack. Compared to IPPO and MAPPO, VRPO significantly reduced the standard deviation of the advantage estimates during training. Against the strong baseline Slumbot, the VRPO agent achieved an average gain of $33 \pm 19$ mBB/hand over 1,000,000 hands. Notably, this performance was achieved without online search, subgame solving, or blueprint-based raise sizing.

Significance and Scope

The paper claims that the primary contribution is the identification of advantage-estimation variance as a bottleneck in equilibrium self-play and the demonstration that Q-boosting effectively mitigates this issue. The results suggest that reducing variance in advantage estimation can yield substantial gains in the quality of learned equilibria.

The authors maintain a modest scope regarding their claims:

• The approach is validated for games with large discrete action sets (via decomposition) but does not address high-dimensional continuous action spaces.
• The empirical focus is on stochastic self-play with centralized critics; the authors do not claim broad improvements over GAE in standard single-agent RL benchmarks.
• The method relies on the ability to compute policy expectations over actions, which is feasible in the tested domains but may require specific architectural considerations for extremely large action spaces.

In conclusion, VRPO represents a significant step forward in applying policy gradient methods to imperfect-information games by addressing a specific, previously under-identified source of variance inherent in stochastic equilibrium learning.