Given reward and value sequences with shape [B, S], compute the Generalized Advantage
Estimate (GAE) for every batch element and timestep. GAE combines one-step temporal-difference
errors with a reverse discounted accumulation, creating a dependency that runs from the end of
each sequence toward the beginning.
The calculation has two stages. First, compute the one-step temporal-difference error at every position. The value after the final position is defined as zero:
\[ \widetilde{V}_{b,t+1} = \begin{cases} V_{b,t+1}, & t < S - 1 \\ 0, & t = S - 1 \end{cases} \qquad \delta_{b,t} = r_{b,t} + \gamma \widetilde{V}_{b,t+1} - V_{b,t} \]
Next, let c = gamma × lambda. The advantage at position t is the
current TD error plus the decayed advantage from the next position:
Therefore, implementations can compute all delta values in parallel, then perform a
reverse scan over the sequence using the recurrence above. For long sequences, the reverse scan
can be split into blocks: each block computes its local scan, then receives the decayed carry from
the block to its right.
For the example below, gamma = 0.9 and lambda = 0.5, so
c = 0.45:
solve(rewards, values, advantages, gamma, lam, B, S) with the signature unchangedadvantages tensorS; padding, per-token terminal flags, and masks are outside the scope of this challengeFor B = 1, S = 4, gamma = 0.9, and lambda = 0.5:
The final timestep uses next_value = 0, so its temporal-difference error is
4.0 - 2.0 = 2.0. Each earlier advantage includes the discounted contribution from later
timesteps.
B ≤ 256S ≤ 65,536rewards, values, and advantages have shape [B, S]gamma and lambda are in the range [0, 1]B = 64, S = 4,096High-Dimensional Continuous Control Using Generalized Advantage Estimation, Schulman et al. (2015)