GAE Advantages with Episode Boundaries

MediumML Coding

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 not
  • gamma: the discount factor
  • lam: 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:

  1. advantages: the GAE advantages for each timestep, rounded to 4 decimal places
  2. returns: 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