TD(λ) and Eligibility Traces
What you'll learn: How eligibility traces extend temporal difference learning by distributing credit across multiple past states, and how TD(λ) unifies Monte Carlo and TD methods.
The Credit Assignment Problem
In reinforcement learning, when you receive a reward, which past states and actions deserve credit? One-step TD methods (like TD(0)) only update the immediately preceding state. Monte Carlo methods wait until the end and update all states in the trajectory. Eligibility traces offer a middle ground.
What Are Eligibility Traces?
Think of eligibility traces as a "memory fading" mechanism. When you visit a state, you mark it as "eligible" for updates. This eligibility decays over time according to two parameters:
- γ (gamma): the discount factor you already know
- λ (lambda): the trace decay rate (0 ≤ λ ≤ 1)
Each state maintains an eligibility score e(s) that increases when visited and gradually fades. When a TD error occurs, all states with non-zero eligibility get updated proportionally to their trace value.
The TD(λ) Algorithm
TD(λ) uses eligibility traces to blend n-step returns:
- λ = 0: Pure TD(0) — only one-step bootstrapping
- λ = 1: Equivalent to Monte Carlo — credit flows all the way back
- 0 < λ < 1: Balanced credit assignment
After each step, TD(λ) updates the eligibility traces for all states and applies the TD error scaled by each state's eligibility. This allows recent states to receive stronger updates while still crediting earlier states that contributed to the outcome.
Why This Matters
Eligibility traces solve the "delayed reward" problem more elegantly than waiting for episode termination (Monte Carlo) or only crediting one step back (TD(0)). They enable faster learning by propagating information backward through recent experience.
Key Takeaway: Eligibility traces track which states are "eligible" for credit assignment, and TD(λ) uses them to create a spectrum of algorithms between TD(0) and Monte Carlo, offering flexible and efficient credit distribution.