📘

TD Residuals for GAE

MediumReinforcement Learning 📚 RL 1: Foundations

Problem Statement

Generalized Advantage Estimation is built from one-step TD residuals. Given rewards R_1..R_T, value estimates values of length T+1 (values[T] is the bootstrap/terminal value), and discount gamma, compute the residual at each step:

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

Implement td_residuals(rewards, values, gamma) returning a list of length T.

Example:

Input:

td_residuals([1.0, 1.0], [0.0, 0.0, 0.0], 0.9)

Output:

[1.0, 1.0]

Reasoning:

Identify the parameters from the input: rewards are $[1.0, 1.0]$ , values are $[0.0, 0.0, 0.0]$ , and the discount factor is $\gamma = 0.9$ .
Compute the residual for the first step ( $t=0$ ) using the formula $\delta_0 = R_0 + \gamma V_1 - V_0$ : substitute the values to get $1.0 + 0.9(0.0) - 0.0 = 1.0$ .
Compute the residual for the second step ( $t=1$ ) using the formula $\delta_1 = R_1 + \gamma V_2 - V_1$ : substitute the values to get $1.0 + 0.9(0.0) - 0.0 = 1.0$ .
The final output is [1.0, 1.0]

Constraints:

len(values) == len(rewards) + 1.
Return a list of T floats.

More from RL 1: Foundations

GAE Over a Full TrajectoryHard PPO Clipped Objective (Single Sample)Medium Return Standardization BaselineMedium REINFORCE Loss TermMedium Entropy of a PolicyEasy

1. Background Knowledge

In policy gradient methods, the agent learns a policy $\pi_\theta$ by estimating how much better an action was compared to the baseline value function $V(s)$ . The raw return is a high-variance estimator, so we use advantage estimation to reduce variance while keeping bias low. Generalized Advantage Estimation (GAE) is the standard technique that blends multiple temporal-difference (TD) estimates to achieve a tunable bias-variance trade-off.

The building block of GAE is the one-step TD residual $\delta_t$ . It measures the one-step prediction error: how much the observed reward plus the discounted next-state value deviates from the current state's value. Formally,

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

where $R_{t+1}$ is the reward received after taking an action in state $s_t$ , $\gamma \in [0, 1]$ is the discount factor, and $V(s_t)$ is the value estimate for state $s_t$ . A positive $\delta_t$ means the outcome was better than expected; a negative $\delta_t$ means it was worse.

In a finite episode of length $T$ , the value array has length $T+1$ because the final entry $V(s_T)$ (or $V(s_{T+1})$ in some conventions) serves as the bootstrap value at the terminal step. If the episode ends, this bootstrap value is typically zero, but the problem statement allows it to be non-zero to handle truncated episodes.

2. Algorithm Approach

This is a straightforward element-wise computation over a sequence. For each timestep $t$ from $0$ to $T-1$ , you compute one residual using three quantities:

The reward at the next step: rewards[t] (which corresponds to $R_{t+1}$ in 1-indexed notation, or simply the reward associated with transition $t$ ).
The discounted next-state value: gamma * values[t + 1].
The current-state value: values[t].

The result is a list of $T$ residuals. No recursion, no loops beyond a single pass, and no state to carry over between steps. The pattern is: iterate, compute, append.

3. Step-by-Step Strategy

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.