← All problems
#110 GAE Reverse Scan Medium

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.

Reverse GAE scan delta[t] advantage[t] delta[0] delta[1] delta[2] delta[3] A[0] A[1] A[2] A[3] carry carry carry A[S]=0 A[t] = delta[t] + (gamma × lambda) × A[t+1]

How GAE Is Computed

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:

\[ A_{b,S} = 0, \qquad A_{b,S-1} = \delta_{b,S-1}, \qquad A_{b,t} = \delta_{b,t} + c A_{b,t+1} \quad \text{for } t = S-2, S-3, \ldots, 0 \]

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:

\[ \delta = \begin{bmatrix} 1.4 & 2.35 & 3.3 & 2.0 \end{bmatrix} \] \[ A_3 = 2.0, \quad A_2 = 3.3 + 0.45(2.0) = 4.2, \quad A_1 = 2.35 + 0.45(4.2) = 4.24, \quad A_0 = 1.4 + 0.45(4.24) = 3.308 \]

Implementation Requirements

Examples

For B = 1, S = 4, gamma = 0.9, and lambda = 0.5:

\[ \text{rewards} = \begin{bmatrix} 1.0 & 2.0 & 3.0 & 4.0 \end{bmatrix}, \quad \text{values} = \begin{bmatrix} 0.5 & 1.0 & 1.5 & 2.0 \end{bmatrix} \] \[ \text{advantages} = \begin{bmatrix} 3.308 & 4.240 & 4.200 & 2.000 \end{bmatrix} \]

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.

Constraints

Reference

High-Dimensional Continuous Control Using Generalized Advantage Estimation, Schulman et al. (2015)

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.