Generalized Advantage Estimation (GAE)

The Bias-Variance Tradeoff

How do we estimate the advantage $\hat{A}_t$? There are many options:

Monte Carlo (high variance, no bias):

$$\hat{A}_t^{MC} = G_t - V(s_t) = \sum_{k=0}^{T-t} \gamma^k r_{t+k} - V(s_t)$$

TD(0) (low variance, high bias):

$$\hat{A}_t^{TD} = r_t + \gamma V(s_{t+1}) - V(s_t) = \delta_t$$

where $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$ is the TD residual.

Monte Carlo uses the actual return (accurate but noisy). TD uses the value estimate (smooth but biased by $V$ errors).

GAE: The Best of Both Worlds

Generalized Advantage Estimation (Schulman et al., 2016) interpolates between these extremes with a parameter $\lambda \in [0, 1]$:

$$\hat{A}_t^{GAE(\gamma, \lambda)} = \sum_{k=0}^{T-t} (\gamma \lambda)^k \delta_{t+k}$$

This can be written recursively:

$$\hat{A}_t^{GAE} = \delta_t + \gamma \lambda \hat{A}_{t+1}^{GAE}$$

The Role of $\lambda$

$\lambda$	Equivalent to	Bias	Variance
$\lambda = 0$	TD(0): $\hat{A}_t = \delta_t$	High	Low
$\lambda = 1$	Monte Carlo: $\hat{A}_t = G_t - V(s_t)$	None	High
$0 < \lambda < 1$	Weighted mix of n-step returns	Medium	Medium

Practical values

$\lambda = 0.95$ with $\gamma = 0.99$ is a common starting point. This gives a good balance — most of the low-variance benefit of bootstrapping with only a small amount of bias.

Worked Example: Computing GAE Across a 4-Step Episode

Concrete numbers. Rewards $r = [1, 0, 0, 2]$, value estimates $V = [0.8, 0.4, 0.5, 1.0, 0]$ (the last is $V(s_T) = 0$ for terminal), $\gamma = 0.9$.

TD residuals $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$:

$$\delta_0 = 1 + 0.9 \cdot 0.4 - 0.8 = 0.56 \qquad \delta_1 = 0 + 0.9 \cdot 0.5 - 0.4 = 0.05$$ $$\delta_2 = 0 + 0.9 \cdot 1.0 - 0.5 = 0.40 \qquad \delta_3 = 2 + 0.9 \cdot 0 - 1.0 = 1.00$$

GAE recursion $\hat{A}_t = \delta_t + \gamma \lambda \hat{A}_{t+1}$, with three different $\lambda$ values:

t	$\delta_t$	$\hat A_t$, λ=0 (TD(0))	$\hat A_t$, λ=0.5	$\hat A_t$, λ=1 (MC)
3	1.00	1.000	1.000	1.000
2	0.40	0.400	0.400 + 0.45·1.000 = 0.850	0.400 + 0.9·1.000 = 1.300
1	0.05	0.050	0.050 + 0.45·0.850 = 0.433	0.050 + 0.9·1.300 = 1.220
0	0.56	0.560	0.560 + 0.45·0.433 = 0.755	0.560 + 0.9·1.220 = 1.658

At $\lambda = 1$ the GAE value matches the Monte Carlo return-minus-baseline exactly (you can verify: $G_0 = 1 + 0.9 \cdot 0 + 0.81 \cdot 0 + 0.729 \cdot 2 = 2.458$, and $G_0 - V_0 = 2.458 - 0.8 = 1.658$ ✓). At $\lambda = 0$ each $\hat A_t$ depends only on the one-step bootstrap — if $V$ is mis-calibrated even a little, that bias appears everywhere. Intermediate $\lambda$ mixes them: a longer-horizon estimate where you still trust $V$ enough to short-circuit far-future noise.

GAE in the PPO Pipeline

The full PPO training loop:

1. Collect rollout data with current policy $\pi_{\theta_\text{old}}$
2. Compute TD residuals: $\delta_t = r_t + \gamma V_\phi(s_{t+1}) - V_\phi(s_t)$
3. Compute GAE advantages: $\hat{A}_t = \sum_k (\gamma\lambda)^k \delta_{t+k}$
4. Compute targets for the value function: $G_t = \hat{A}_t + V_\phi(s_t)$
5. Run multiple epochs of mini-batch updates on $L^{CLIP}$ and the value loss

Interactive: GAE-(γ,λ) Calculator

Edit the rewards or value estimates and slide $\lambda$ to watch $\hat A_t$ morph between pure TD(0) (red) and pure Monte Carlo (green). With a perfectly-calibrated $V$, all three curves coincide; introduce bias into $V$ and watch them diverge.

Common misconception: “Lower λ = lower variance, always.”

GAE’s variance comes from summing the per-step TD residuals: $\text{Var}(\hat A_t) \approx \sum_k (\gamma \lambda)^{2k} \text{Var}(\delta_{t+k})$. So yes, $\lambda < 1$ shrinks variance — but the bias term comes from how wrong $V$ is. If your critic is severely under-trained (early in PPO), even $\lambda = 0$ is terrible because every $\hat A_t$ inherits the entire $V$ error. Practitioners typically anneal $\lambda$ upward (or use a high λ like 0.95) only once $V$ has had time to converge.

Why Not Just Monte Carlo?

In LLM training (RLHF), episodes can be long (hundreds of tokens). Monte Carlo returns have very high variance because each token’s reward signal is buried under the noise of all future tokens.

GAE with $\lambda < 1$ exponentially downweights distant TD residuals, giving a much cleaner signal for credit assignment — which token actually contributed to the reward?

References

• Schulman, Moritz, Levine, Jordan, Abbeel. High-Dimensional Continuous Control Using Generalized Advantage Estimation. ICLR 2016. arXiv:1506.02438