Eligibility Traces and TD(lambda)
An eligibility trace keeps a fading memory of which states were recently visited, so a single reward can update many past predictions at once instead of only the last one.
Prerequisites: Temporal Difference Learning
Plain temporal-difference learning only updates the value of the state you were just in. If a trading agent wanders through ten states before finally hitting a big reward, one-step TD blames only the last state and lets the reward trickle backward one update at a time over many episodes. Eligibility traces fix this by tagging every recently visited state as "eligible" for credit, with that tag decaying the further back in time the visit was.
An eligibility trace is a decaying memory of "how recently and how often was this state visited," and it lets one TD error update every recently visited state at once, weighted by how eligible each one still is.
Each state carries a trace value that jumps up when the state is visited and decays by a factor lambda (between 0 and 1) at every subsequent step. When a TD error arrives, every state updates its value in proportion to its current trace, not just the most recent one. Setting lambda = 0 recovers ordinary one-step TD; setting lambda = 1 behaves like a full Monte Carlo update that credits the entire episode.
Worked example. A trace starts at 1.0 the moment a state is visited and decays by lambda = 0.5 each subsequent step. Three steps later, without a revisit, its trace is 0.5^3 = 0.125. If a TD error of +0.4 arrives at that point, the state's value update is 0.4 x 0.125 = 0.05 — a small but nonzero nudge, versus zero under one-step TD.
TD(lambda) is a knob for the bias-variance trade-off between fast, low-variance one-step updates and slow, high-variance full-episode updates, and choosing lambda in between usually learns faster than either extreme alone.
Related concepts
Practice in interviews
Further reading
- Sutton & Barto, Reinforcement Learning: An Introduction (ch. 12)