GAE Advantages with Episode Boundaries
Problem statement
Implement a function that computes Generalized Advantage Estimation (GAE) advantages and the corresponding returns for a trajectory, properly handling episode boundaries.
Your function takes:
rewards: a list of rewards $[r_0, r_1, \ldots, r_{T-1}]$ of length $T$values: a list of estimated state values $[V(s_0), V(s_1), \ldots, V(s_T)]$ of length $T+1$ (the last value is the bootstrap value for the state after the final action)dones: a list of done flags $[d_0, d_1, \ldots, d_{T-1}]$ of length $T$, where 1 means the episode terminated after step $t$ and 0 means it did notgamma: the discount factorlam: the GAE $\lambda$ parameter that controls the bias-variance tradeoff
When an episode terminates ($d_t = 1$), the bootstrapped next-state value is treated as zero, and the advantage accumulation must not propagate across the episode boundary.
Return a tuple of two lists:
advantages: the GAE advantages for each timestep, rounded to 4 decimal placesreturns: the target returns, computed as advantages plus the corresponding state values $V(s_t)$, rounded to 4 decimal places
Example
Input:
rewards = [2.0, -1.0, 3.0]
values = [1.0, 2.0, 0.5, 1.0]
dones = [0, 1, 0]
gamma = 0.9, lam = 0.8
Output:
([0.64, -3.0, 3.4], [1.64, -1.0, 3.9])
Reasoning: Backwards from $t = 2$: $\delta_2 = 3 + 0.9 \cdot 1.0 - 0.5 = 3.4$ and $\hat{A}_2 = 3.4$. At $t = 1$ the episode ended, so $\delta_1 = -1 - 2 = -3$ and nothing from $t = 2$ flows in: $\hat{A}_1 = -3$. At $t = 0$: $\delta_0 = 2 + 0.9 \cdot 2 - 1 = 2.8$ and $\hat{A}_0 = 2.8 + 0.72 \cdot (-3) = 0.64$. Returns add $V(s_t)$: $[1.64, -1.0, 3.9]$.
Show hint
Which one-step quantity, built from a reward and two value estimates, does GAE average over future steps?
Relevant roles: Research Scientist, LLM Engineer, ML Engineer and Applied Scientist.
Related free problems
- GRPO Objective FunctionMedium
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium