TD(lambda) and Eligibility Traces

TD(lambda) blends one-step temporal-difference learning and Monte Carlo returns using eligibility traces to assign credit over multiple steps.

A spectrum of updates

One-step TD looks one transition ahead; Monte Carlo uses the entire return. TD(lambda) spans the range between them, mixing multi-step returns so the agent gets the fast online updates of TD with some of the low bias of longer lookaheads.

n-step returns

An n-step return uses the next n rewards plus the estimated value at step n: G_t^{(n)} = R_{t+1} + gamma R_{t+2} + ... + gamma^{n-1} R_{t+n} + gamma^n V(S_{t+n}). n = 1 is TD(0); n reaching the episode end is Monte Carlo. Intermediate n often works best.

The lambda-return

Rather than pick one n, TD(lambda) averages all n-step returns with geometrically decaying weights controlled by lambda in [0, 1]. lambda = 0 recovers one-step TD; lambda = 1 recovers Monte Carlo. Tuning lambda trades bias against variance smoothly.

Eligibility traces

Implementing the lambda-return exactly would require waiting for the future. Eligibility traces make it online: each state keeps a fading memory of how recently and often it was visited, and every TD error updates all recently visited states in proportion to their trace. This spreads credit backward efficiently, one step at a time.

Why it matters

Eligibility traces speed learning when rewards are delayed, because a reward can immediately update many of the states that led to it rather than propagating back one step per episode. The mechanism gives a principled, tunable way to handle the credit-assignment problem at the heart of reinforcement learning.