N-Step Returns and Eligibility Traces
What you'll learn: How to extend actor-critic methods beyond single-step updates to better balance bias and variance using n-step returns and eligibility traces.
The Core Problem
In one-step actor-critic (lesson 2281), the critic updates based on immediate rewards plus the next state's value estimate. This is fast but high-bias—it relies heavily on potentially inaccurate value estimates. REINFORCE uses full episode returns (low bias, high variance). Can we find a middle ground?
N-Step Returns: Looking Further Ahead
Instead of updating with just one reward, n-step returns accumulate n rewards before bootstrapping from a value estimate:
- 1-step return: r₁ + γV(s₂)
- 2-step return: r₁ + γr₂ + γ²V(s₃)
- n-step return: r₁ + γr₂ + ... + γⁿ⁻¹rₙ + γⁿV(sₙ₊₁)
As n increases, you use more real rewards (less bias) but wait longer and accumulate more variance from stochastic actions. The sweet spot is often n=3 to n=5.
Eligibility Traces: The Best of All Worlds
Eligibility traces blend all n-step returns using exponential decay parameter λ (lambda). Instead of choosing one n, you average them:
TD(λ) return = (1-λ) × [1-step + λ×2-step + λ²×3-step + ...]
When λ=0, you get pure 1-step (high bias). When λ=1, you get Monte Carlo (full episode). Values between 0.9-0.95 often work best, creating a smooth credit assignment that propagates rewards backward through time efficiently.
The "trace" tracks which states deserve credit for future rewards, decaying as you move backward in time.
Key Takeaway: N-step returns and eligibility traces let actor-critic methods balance bias-variance by looking multiple steps ahead or blending different horizons, improving both sample efficiency and convergence stability.