PPO Algorithm › Generalized Advantage Estimation

PPO typically uses Generalized Advantage Estimation (GAE) to compute advantages with a controllable bias-variance tradeoff. The advantage function measures how much better an action is than average. True advantages depend on full trajectory information unavailable during learning, so we must estimate them from observed rewards. Different estimation approaches trade off bias against variance in different ways, and this tradeoff has a major impact on the stability and efficiency of training.

Think of advantage estimation as a forecasting problem. The one-step estimator is like a weather forecast that only looks at today's conditions: it is highly confident (low variance) but might be systematically wrong if today's conditions are atypical (high bias). The Monte Carlo estimator is like collecting many days of weather data before making a prediction: it captures complex patterns (low bias) but requires lots of data and is noisy (high variance). GAE is like a weighted ensemble of forecasts at different time horizons, combining the precision of short-term estimates with the accuracy of long-term ones.

A one-step estimate uses only the immediate reward and next state value. This provides low variance, since it depends on fewer random variables, but high bias, since it relies heavily on the accuracy of the value function. A Monte Carlo estimate uses all future rewards until episode end. This provides low bias, since it uses actual observed returns, but high variance, since it incorporates the randomness of many future actions and transitions. The quality of one-step estimates depends entirely on how good the value function is. If the value function is poor, one-step TD errors will be systematically wrong, and the policy will learn from corrupted signals.

GAE solves this estimation problem by taking an exponentially weighted average of temporal difference errors at different time horizons. The parameter $\lambda$ controls how quickly the weights decay as we look further into the future. This approach combines the benefits of using both short-term (low variance but high bias) and long-term (high variance but low bias) estimates. By tuning $\lambda$, we can find the sweet spot for our particular problem.

GAE is defined as:

$$\hat{A}_t^{\text{GAE}(\gamma, \lambda)} = \sum_{l=0}^{\infty} (\gamma \lambda)^l \delta_{t+l}$$

Each component of this formula contributes to the bias-variance tradeoff:

• $\hat{A}_t^{\text{GAE}(\gamma, \lambda)}$: the GAE advantage estimate at timestep $t$
• $\sum_{l=0}^{\infty}$: sum over all future timesteps from the current timestep forward (in practice, truncated at episode end)
• $l$: the lookahead index, showing how many steps into the future we're considering
• $\gamma$: the discount factor, typically 0.99, which determines how much we value future rewards
• $\lambda$: the GAE parameter, typically 0.95, which controls the bias-variance tradeoff
• $(\gamma \lambda)^l$: the exponentially decaying weight for the $l$-step temporal difference error
• $\delta_{t+l}$: the temporal difference (TD) error at timestep $t+l$
• $t$: the current timestep

The temporal difference error, which is the building block for GAE, measures the discrepancy between what we expected and what we observed. It is defined as:

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

Understanding each term clarifies why TD errors are useful for advantage estimation:

• $\delta_t$: the temporal difference error at timestep $t$, measuring the difference between the observed reward plus next state value versus the current state value
• $r_t$: the immediate reward received at timestep $t$
• $\gamma$: the discount factor
• $V(s_t)$: the value function estimate for state $s_t$ (the predicted cumulative future reward)
• $V(s_{t+1})$: the value function estimate for the next state
• $\gamma V(s_{t+1})$: the discounted value of the next state
• $s_t$: the state at timestep $t$
• $s_{t+1}$: the next state at timestep $t+1$

The TD error intuition is clear: if our value function were perfect, the expected TD error would be zero. The value of the current state should equal the immediate reward plus the discounted value of the next state. A positive TD error indicates we received more reward than expected, suggesting the action was good. A negative TD error indicates we received less than expected. By accumulating these errors over multiple timesteps with exponentially decaying weights, GAE builds a richer signal that accounts for delayed consequences while limiting how much noise accumulates.

The tradeoff controlled by $\lambda$ determines how we combine information across time horizons:

• $\lambda = 0$ uses only one-step TD error (low variance, high bias)
• $\lambda = 1$ uses full Monte Carlo returns (high variance, low bias)

In practice, $\lambda = 0.95$ provides a good balance for most problems, weighting nearby TD errors heavily while still incorporating longer-term information with diminishing weight. For language models, this setting helps because the value function approximation is imperfect given the enormous state space, and GAE mitigates the impact of value function errors on advantage quality.

The recursive formulation for efficient computation eliminates the need to store and sum all future TD errors explicitly:

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

Each component of this recursive formula has a clear interpretation:

• $\hat{A}_t$: the advantage estimate at timestep $t$, computed recursively
• $\delta_t$: the temporal difference error at timestep $t$, equal to $r_t + \gamma V(s_{t+1}) - V(s_t)$
• $\gamma$: discount factor
• $\lambda$: GAE parameter
• $\hat{A}_{t+1}$: the advantage estimate for the next timestep, computed first in backward iteration
• $t$: the current timestep

The boundary condition is $\hat{A}_T = 0$ at the terminal timestep, since there are no future advantages after the episode ends. This recursive formulation is computationally efficient because we can compute all advantages in a single backward pass through the trajectory, starting from the end and working toward the beginning. Each computation reuses the result from the next timestep, avoiding redundant calculations. The algorithm is simple: iterate backwards, accumulating a running GAE value with decay, and store the result at each timestep.