Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 37 ยท Monte Carlo and Temporal Difference

Temporal-Difference Learning: TD(0) Prediction

Learn TD(0), the core idea of reinforcement learning: update value estimates after every step by bootstrapping, the TD error, and how TD compares with Monte Carlo on the random walk task in Python.

If you had to name one idea that defines reinforcement learning, it would be temporal-difference (TD) learning. It combines the best of the two methods you know. Like Monte Carlo, it learns directly from raw experience without a model. Like dynamic programming, it bootstraps: it updates an estimate partly from another estimate, so it does not have to wait until the end of an episode.

The intuition: driving home

You estimate that your drive home will take 30 minutes. After 5 minutes you hit unexpected traffic, and now you think the total will be 40. Do you wait until you arrive to correct your first guess? Monte Carlo does. TD does not: the moment you see the traffic, you already know your original estimate (30) was too low, because your new estimate (5 + 35 left) disagrees with it. You can learn immediately from the disagreement between two successive predictions, a temporal difference.

The TD(0) update

After taking a step from S_t, receiving R_{t+1} and arriving in S_{t+1}:

V(S_t) <- V(S_t) + alpha * [ R_{t+1} + gamma * V(S_{t+1}) - V(S_t) ]

The bracket is the TD error:

delta_t = R_{t+1} + gamma * V(S_{t+1}) - V(S_t)

R_{t+1} + gamma * V(S_{t+1}) is the TD target: a one-step-ahead estimate of the return. Monte Carlo uses the full return G_t as its target; TD(0) uses a sampled reward plus the current estimate of what follows. Compare the three update styles:

Method Target Uses a model? Waits for episode end?
DP sum p * (r + gamma * V(s')) (expected) yes no
Monte Carlo G_t (actual return) no yes
TD(0) R + gamma * V(S') (sampled + bootstrapped) no no
flowchart LR
    S["S_t"] -->|"R_{t+1}"| S2["S_{t+1}"]
    S2 -. "bootstrap: use V(S_{t+1})" .-> T["TD target = R + gamma*V(S')"]
    T -->|"delta = target - V(S_t)"| U["V(S_t) += alpha * delta"]

The random walk

A classic testbed: five states in a row, A B C D E, with terminal ends on both sides. The agent starts in C and moves left or right with equal probability. Reaching the right terminal gives reward +1; the left gives 0; all other rewards are 0, and gamma = 1. The true value of a state is the probability of finishing on the right: 1/6, 2/6, 3/6, 4/6, 5/6.

Python TD(0) learning the 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.

Initially all values are 0.5. After the first episode, only the states next to the terminal that was reached change, because the TD error r + V(s') - V(s) is nonzero only where the next value differs from the current one. Over time information leaks backward from the terminal, and after about 100 episodes the values are near the truth, with some noise since alpha is constant.

TD versus Monte Carlo

Which learns faster? On the random walk, TD usually wins. The program below runs both methods for 100 episodes, repeated over 100 independent runs, and reports the root-mean-squared error against the true values at several points. For Monte Carlo the target is the actual return (1 or 0 for the whole episode); for TD it is bootstrapped. We compare a few step sizes for each.

Python TD(0) versus constant-alpha Monte Carlo

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.

In typical runs the best TD settings reach a lower error than the best Monte Carlo settings for the same number of episodes. TD's lower variance beats its small start-up bias on this task. That pattern, TD usually faster than constant-alpha MC on stochastic tasks, is one of the main empirical facts of the field.

Why TD works

  • Online. It learns after every step, so it works in continuing tasks and can use partial episodes.
  • Low variance. The target depends on one random reward and one random next state instead of a whole random sequence.
  • Bias. The target uses the current estimate V(S'), which is wrong at first, so early updates are biased. The bias fades as estimates improve.
  • Convergence. For a fixed policy and a suitably decreasing step size, tabular TD(0) converges to v_pi.
  • Certainty equivalence. With a fixed batch of data, TD(0) converges to the value function of the maximum-likelihood Markov model of the data, whereas MC minimizes the mean-squared error on the training returns. TD therefore exploits the Markov structure.

Choosing the step size

A constant alpha (like 0.1) tracks changes but leaves some noise forever. Large values learn quickly and wobble; small values are precise but slow. Decaying alpha (for example 1 / n) converges exactly but adapts slowly. In practice you tune alpha on a small version of your problem.

From prediction to control

TD(0) predicts values for a fixed policy. To control, apply the same idea to action values: SARSA and Q-learning (chapter 5) are TD(0) applied to q. Before that, the next lesson fills the gap between one-step TD and Monte Carlo.

Common mistakes

  • Forgetting to treat terminal states as value 0 (the target at a terminal step is just the reward).
  • Using a step size that is too large and wondering why values never settle.
  • Initializing terminal values to nonzero numbers; this corrupts every nearby update.
  • Calling a method "TD" when the target is the full return (that is Monte Carlo).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the TD error in TD(0)?

    It is the difference between the one-step target and the current estimate.
  2. 2. What does bootstrapping mean?

    TD(0) builds its target from V(S'), an estimate, rather than waiting for the real return.
  3. 3. Which is a key advantage of TD over Monte Carlo?

    TD updates online with a lower-variance target, at the cost of some bias from bootstrapping.
  4. 4. In the random walk, why does only one value change after the first episode that ends on the right?

    With all values 0.5 and zero rewards, the TD error is nonzero only at the step that earns the reward or reaches a differing value.

Summary

  • TD(0) updates V(S_t) toward R_{t+1} + gamma * V(S_{t+1}) after every step; the gap is the TD error.
  • It bootstraps like DP and samples like Monte Carlo: model-free, online and low variance.
  • Bootstrapping adds bias that fades as estimates improve; on stochastic tasks TD is often faster than MC.
  • The same update applied to action values gives SARSA and Q-learning.

Next: n-step TD and Eligibility Traces