Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 37 ยท Monte Carlo and Temporal Difference

n-step TD and Eligibility Traces (TD-lambda)

Bridge TD(0) and Monte Carlo with n-step returns and TD(lambda): the lambda-return, eligibility traces and the backward view, compared on a 19-state random walk with runnable Python.

One-step TD looks one step ahead and then trusts its own estimate. Monte Carlo looks all the way to the end of the episode and trusts nothing but real rewards. These are two ends of a spectrum, and the best choice is usually somewhere between them. This lesson builds that spectrum in two ways: n-step methods (look n steps ahead) and eligibility traces (a smooth, efficient way to mix all lookahead lengths at once).

n-step returns

Define the return that uses n real rewards and then bootstraps from the value estimate:

G_{t:t+n} = R_{t+1} + gamma * R_{t+2} + ... + gamma^(n-1) * R_{t+n} + gamma^n * V(S_{t+n})

With n = 1 this is the TD(0) target. With n as large as the remaining episode it is the Monte Carlo return. The n-step TD update is

V(S_t) <- V(S_t) + alpha * ( G_{t:t+n} - V(S_t) )

and is performed n steps late, when the needed rewards have arrived. Intermediate values of n often work best because they balance bias (small n, relies on estimates) against variance (large n, relies on long random sequences).

flowchart LR
    TD0["TD(0): n = 1"] --> N2["n = 2"] --> N4["n = 4"] --> N8["n = 8"] --> MC["Monte Carlo: n = episode length"]

A 19-state random walk

We reuse the random walk, now with 19 states in a row, terminals at both ends, and rewards of -1 for the left end and +1 for the right end. The agent starts in the middle. With gamma = 1 the true value of state s (numbered 1 to 19) is (s - 10) / 10, running from -0.9 to 0.9. The code implements n-step TD exactly as defined, keeping the trajectory so that updates can run n - 1 steps behind the action.

Python n-step TD on a 19-state random walk

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table by rows and columns. The best cell overall is a moderate lookahead (around n = 4 with alpha = 0.3), clearly better than the best one-step setting. Each n also has its own best step size: long returns are noisier, so they prefer a smaller alpha (n = 16 is best at alpha = 0.1, and gets much worse at 0.5), while short returns tolerate a larger one. This inverted-U pattern is the central message: intermediate lookahead is best, and the right n depends on the task, so it becomes a hyperparameter.

The lambda-return

Instead of picking one n, we can average all n-step returns with geometrically decaying weights. The lambda-return is

G^lambda_t = (1 - lambda) * sum over n >= 1 of lambda^(n-1) * G_{t:t+n}

(with the leftover weight going to the full Monte Carlo return at episode end). The parameter lambda in [0, 1] slides from TD(0) at lambda = 0 to Monte Carlo at lambda = 1. This is the forward view: to update V(S_t) you need future data, so it can be applied only after the episode.

Eligibility traces: the backward view

The backward view achieves (nearly) the same effect online, with constant work per step, by remembering which states were recently visited. Keep an eligibility trace E(s) per state. After every step:

  1. Compute the TD error delta = R + gamma * V(S') - V(S).
  2. Bump the trace of the current state: E(S) <- E(S) + 1 (accumulating trace).
  3. Update every state in proportion to its trace: V(s) <- V(s) + alpha * delta * E(s).
  4. Decay all traces: E(s) <- gamma * lambda * E(s).

Interpret the trace as credit assignment: a recently visited state is "eligible" to share in the blame or praise for the current TD error, and eligibility fades with time. This is TD(lambda). With lambda = 0 only the current state is updated, which is TD(0).

Python TD(lambda) with eligibility traces

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same pattern: an intermediate lambda (about 0.8 here) beats lambda = 0 at a well-chosen alpha, and large lambda wants a small alpha. (We leave out lambda = 1: with accumulating traces and a large step size it can diverge, because a state revisited many times builds a trace far above 1.) Traces also give a big practical advantage on tasks with delayed rewards, because one TD error at the end of a long chain immediately updates all the states that led up to it, instead of creeping backward one state per episode.

Trace variants

  • Accumulating traces add 1 on each visit (above). A state visited repeatedly can build a trace above 1.
  • Replacing traces set the trace to exactly 1 on a visit, which avoids over-crediting states in loops and often helps in practice.
  • True online TD(lambda) and Dutch traces make the backward view exactly equivalent to the forward view even with function approximation; they are the modern default in the linear case.

Traces also extend to control: SARSA(lambda) and Watkins's Q(lambda) are covered in the next chapter alongside SARSA.

Choosing between methods

Method Lookahead Bias Variance Updates
TD(0) 1 step highest lowest every step
n-step TD n steps medium medium delayed by n
TD(lambda) all steps, weighted tunable tunable every step
Monte Carlo whole episode none highest episode end

Common mistakes

  • Forgetting to reset traces at the start of every episode.
  • Updating terminal states or letting their traces grow; terminal values must stay 0.
  • Using the same step size for all n or lambda; longer returns usually need a smaller alpha.
  • Confusing lambda (trace decay) with gamma (discount). They multiply together in the decay but mean different things.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the n-step return?

    It uses n actual rewards and then bootstraps from V(S_{t+n}).
  2. 2. What does TD(lambda) with lambda = 1 correspond to (for episodic tasks)?

    With lambda = 1 the lambda-return is the full Monte Carlo return.
  3. 3. What is an eligibility trace?

    Traces decay by gamma * lambda and let one TD error update all recently visited states.
  4. 4. In the random walk experiments, which lookahead tended to work best?

    Intermediate values balance bias and variance, giving an inverted-U error curve.

Summary

  • n-step TD uses n real rewards before bootstrapping, interpolating between TD(0) and Monte Carlo.
  • The lambda-return averages all n-step returns; TD(lambda) implements it online with eligibility traces.
  • An intermediate n or lambda usually works best, and traces speed up learning with delayed rewards.
  • Traces must be reset each episode, and terminal values stay at 0.

Next: Q-learning: Off-policy TD Control