Generalized Advantage Estimation
Generalized Advantage Estimation
Generalized Advantage Estimation (GAE) provides a family of advantage estimators that trade off bias and variance using a parameter lambda. When lambda = 0 it reduces to the one-step TD error (low variance, high bias). When lambda = 1 it becomes equivalent to the full Monte Carlo advantage (high variance, low bias). In practice, lambda around 0.95 works well.
Given rewards, value estimates (including V(s_T) = 0 for the terminal state), gamma, and lambda, compute the GAE advantages for each timestep.
Algorithm
- Compute the TD error (delta) at each timestep:
- Compute advantages backward using the recursive formula:
Examples
Input: rewards = [1, 1, 1], values = [0, 0, 0, 0], gamma = 1.0, lam = 1.0
Output: [3.0, 2.0, 1.0]
With gamma=1, lam=1 (no discounting, full trace): advantages accumulate all future TD errors. Equivalent to Monte Carlo returns minus values.
Input: rewards = [1, 0, 5], values = [1, 2, 3, 0], gamma = 0.9, lam = 0.95
Output: [3.86055, 2.41, 2.0]
With gamma=0.9, lam=0.95: TD errors are δ₂=5+0.9×0−3=2, δ₁=0+0.9×3−2=0.7, δ₀=1+0.9×2−1=1.8. Advantages blend these with exponential decay.
Hint 1
Create an advantages list of length T. Start from t = T-1 going backward to 0. At each step compute delta = rewards[t] + gamma * values[t+1] - values[t], then A[t] = delta + gamma * lam * last_adv, where last_adv tracks the advantage from the next timestep.
Hint 2
Initialize last_adv = 0. After computing A[t], set last_adv = A[t] before moving to the previous timestep.
Requirements
- Compute TD errors: delta_t = rewards[t] + gamma * values[t+1] - values[t]
- Compute advantages backward: A[t] = delta_t + gamma * lambda * A[t+1]
- The values list has length T+1 (includes the terminal value)
- Return a list of floats with length T (same as rewards)
Constraints
- rewards has at least one element
- values has len(rewards) + 1 elements
- 0 <= gamma <= 1, 0 <= lam <= 1
- Return a list of floats with the same length as rewards
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: number
Accepts: number
Generalized Advantage Estimation
Generalized Advantage Estimation
Generalized Advantage Estimation (GAE) provides a family of advantage estimators that trade off bias and variance using a parameter lambda. When lambda = 0 it reduces to the one-step TD error (low variance, high bias). When lambda = 1 it becomes equivalent to the full Monte Carlo advantage (high variance, low bias). In practice, lambda around 0.95 works well.
Given rewards, value estimates (including V(s_T) = 0 for the terminal state), gamma, and lambda, compute the GAE advantages for each timestep.
Algorithm
- Compute the TD error (delta) at each timestep:
- Compute advantages backward using the recursive formula:
Examples
Input: rewards = [1, 1, 1], values = [0, 0, 0, 0], gamma = 1.0, lam = 1.0
Output: [3.0, 2.0, 1.0]
With gamma=1, lam=1 (no discounting, full trace): advantages accumulate all future TD errors. Equivalent to Monte Carlo returns minus values.
Input: rewards = [1, 0, 5], values = [1, 2, 3, 0], gamma = 0.9, lam = 0.95
Output: [3.86055, 2.41, 2.0]
With gamma=0.9, lam=0.95: TD errors are δ₂=5+0.9×0−3=2, δ₁=0+0.9×3−2=0.7, δ₀=1+0.9×2−1=1.8. Advantages blend these with exponential decay.
Hint 1
Create an advantages list of length T. Start from t = T-1 going backward to 0. At each step compute delta = rewards[t] + gamma * values[t+1] - values[t], then A[t] = delta + gamma * lam * last_adv, where last_adv tracks the advantage from the next timestep.
Hint 2
Initialize last_adv = 0. After computing A[t], set last_adv = A[t] before moving to the previous timestep.
Requirements
- Compute TD errors: delta_t = rewards[t] + gamma * values[t+1] - values[t]
- Compute advantages backward: A[t] = delta_t + gamma * lambda * A[t+1]
- The values list has length T+1 (includes the terminal value)
- Return a list of floats with length T (same as rewards)
Constraints
- rewards has at least one element
- values has len(rewards) + 1 elements
- 0 <= gamma <= 1, 0 <= lam <= 1
- Return a list of floats with the same length as rewards
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: number
Accepts: number