M4-T5 — Monte Carlo and Temporal-Difference Learning

Learning objectives

After this lesson, you should be able to:

• Estimate a state value from sampled episodes with first-visit Monte Carlo, and write the TD(0) update with its TD error.
• Explain why the Monte Carlo target is unbiased but noisy and the TD target is biased but less noisy, and read the measured comparison on the ward.
• Describe n-step returns and TD(lambda) as the family between TD(0) and Monte Carlo.
• State the Robbins-Monro conditions on the step size carefully, and say what a constant step size does and does not guarantee.

The intuition

Suppose you want to know how long the walk from Ward 3 to the pharmacy takes. One honest way is to walk it many times and average the times: that is Monte Carlo. Each trip gives a whole, true outcome, but trips vary a lot (an open door, a queue at the lift), so you need many of them. The other way is to use what you already believe. You are standing at the lift and your belief says the rest of the trip from here takes 4 minutes. You have just walked 2 minutes from Ward 3 to the lift. Your new estimate for the whole trip is 2 + 4 = 6 minutes, and you nudge your old estimate for Ward 3 towards it. That is temporal-difference learning: you update a guess using another guess.

The second way learns after every step and does not need the trip to finish, so it works in tasks that never end. Its price is that the other guess may be wrong, and the error leaks into the new one: bias. The first way has no such leak, but each target contains every random event on the way to the goal: variance. The figure shows which part of an episode each target uses.

The mathematics

Goal

Estimate V^π(s), the expected discounted return from state s when following a fixed policy π (lesson M4-T3), using sampled episodes only. Let G_t = r_t+1 + gamma r_t+2 + ... be the return from time t (lesson M4-T2).

Monte Carlo (first visit)

1. Run an episode following π to its end, recording states and rewards.
2. Go backwards computing G_t = r_t+1 + gamma G_t+1.
3. For each state, take the G_t at its first visit in this episode and add it to that state’s list.
4. V(s) is the average of the list. Incrementally: N(s) ← N(s) + 1 and V(s) ← V(s) + (1 / N(s)) (G − V(s)).

The first-visit version averages one return per state per episode, and its estimate is an average of independent, unbiased samples of V^π(s). It needs episodes that end, and it can only update once the episode is over.

TD(0)

The bracketed term in the usual form, V(s) ← V(s) + α (r + γ V(s′) − V(s)), is delta. Its target r + γ V(s′) is a sampled version of the right-hand side of the Bellman expectation equation. The update is made after every step. As in lesson M4-T4, (1 − done) stops it from bootstrapping through a terminal state.

alpha

step size: how far the estimate moves towards the target.

delta

TD error: target minus current estimate. Zero on average when V is correct.

bootstrapping

using an estimate (V of the next state) to build the target for another estimate.

Bias and variance of the two targets

The bias of TD(0) shrinks as V improves, so TD(0) is consistent: with the right step sizes it still converges to V^π. For a fixed batch of experience the two methods also settle on different answers: according to Sutton and Barto (2018, section 6.3), repeated batch updating makes MC minimise the squared error on the training returns and TD(0) give the values of the maximum-likelihood model of the data.

n-step returns and TD(lambda)

Between the two lies the n-step return, which uses n real rewards and then bootstraps:

TD(lambda) averages all n-step returns with weights (1 − lambda) lambdaⁿ⁻¹, and gives the remaining weight to the full return when the episode ends. lambda = 0 is TD(0) and lambda = 1 is Monte Carlo. The practical form, the backward view, keeps an eligibility trace e(s) for each state and updates every state in proportion to it at every step:

Intermediate n or lambda often gives the best bias-variance balance in practice, which is why the knob exists. Sutton (1988) introduced TD(lambda) and analysed it; the exact equivalence of the forward and backward views holds for offline updating and only approximately for the online update used here.

Step size and convergence

Every update above is a stochastic-approximation step: V moves a fraction α towards a noisy target. The Robbins-Monro conditions on the step sizes used for one state are:

The first lets the estimate travel as far as it must, the second makes the noise average out. Careful statement for this lesson: for a finite MDP and a fixed policy, tabular TD(0) converges to V^π with probability one if every state is visited infinitely often and each state’s step sizes satisfy both conditions (this is the standard stochastic-approximation result, discussed in Sutton and Barto, 2018, chapter 6; the proofs are in the research literature and I do not reproduce them). Three cautions. (1) A constant alpha violates the second condition, so it does not converge with probability one: the estimate keeps fluctuating around V^π, with a spread that grows with alpha. Its advantage is that it keeps tracking when the world changes. (2) The conditions are asymptotic and say nothing about speed; 1 / n satisfies them yet can be very slow for TD, as the example shows. (3) They concern the tabular case; with function approximation they are not enough.

Bootstrapping and the deadly triad (a pointer)

In a table, bootstrapping is safe. Combine bootstrapping with function approximation and off-policy data and the updates can diverge; Sutton and Barto (2018, section 11.3) call the three together the deadly triad. We use a table here, so it does not bite yet; it is why deep reinforcement learning needs extra care in later modules.

A worked example

All numbers come from running code: a short script on RLCore.gridworld, RLCore.valueIteration, RLCore.evaluatePolicyDP and SLAMCore.rng.

1. One episode by hand. The chain from lesson M4-T4: states A, B, C and a terminal pharmacy; gamma 0.9; the rewards of the policy that always moves right are −1, −1 and +9 (the last includes the +10 for arriving). All values start at 0. True values are V(A, B, C) = (5.39, 7.1, 9).

• Monte Carlo. The returns are G_C = 9, G_B = −1 + 0.9 · 9 = 7.1 and G_A = −1 + 0.9 · 7.1 = 5.39. With a sample average, one episode (N = 1 for every state) already gives (5.39, 7.1, 9). The world is deterministic, so there is no variance to average away.
• TD(0) with alpha = 0.5, updating A, B, C in the order visited. A: target −1 + 0.9 · 0 = −1, so V(A) = −0.5. B: target −1, so V(B) = −0.5. C: target 9, so V(C) = 4.5. After episode 1 the values are (−0.5, −0.5, 4.5): only C is moving in the right direction by a real amount, the rest is waiting for information.
• Episode 2. A: target −1 + 0.9 · (−0.5) = −1.45, V(A) = −0.975. B: target −1 + 0.9 · 4.5 = 3.05, V(B) = 1.275. C: V(C) = 6.75. Information moves one state per episode; this is the bias of bootstrapping in action.
• n-step targets for A, using the values after episode 1: 1-step −1 + 0.9 · (−0.5) = −1.45; 2-step −1 − 0.9 + 0.81 · 4.5 = 1.745; 3-step (the full return) 5.39. The lambda = 0.5 return weights them 0.5, 0.25 and 0.25 and gives 1.05875. TD(0.5) in its backward view, from zero values after one episode, gives (0.18625, 1.525, 4.5): the trace lets A and B learn from the +9 straight away.

2. Targets on the ward. Take Scout’s ward (slip 0.2, gamma 0.95, step reward −0.1, goal +10, stairwell edge −10 and terminal) with the optimal policy fixed. The exact values come from evaluatePolicyDP; V(start) = 3.3137. From the start state the first move has three outcomes, with probability 0.8, 0.1 and 0.1, whose one-step targets with the true next value are 3.419, 2.736 and 3.048. They average 3.3137 (no bias when V is exact) with a standard deviation of 0.222. The Monte Carlo return from the same state, over 20,000 episodes, has mean 3.331 and a standard deviation of 3.596, sixteen times larger. Averaged over all 23 non-terminal states the standard deviation is 3.78 for the return and 0.675 for the TD target, a ratio of 5.6. (The TD number is for a perfect V; with a wrong V the target also carries bias.)

3. Learning curves. Procedure: episodes start in a non-terminal state chosen uniformly (so every state is visited; the mean episode length is 7.66 steps), follow the fixed optimal policy, and use uniform numbers from SLAMCore.rng(seed) for the transitions. All values start at 0. The score is the root-mean-square error against the exact V over the 23 states. Mean over 30 seeds (1 to 30), standard deviation over seeds in brackets:

What the numbers say, and what they do not:

• Variance and bias show up in different columns. The sample-average MC error is small at the start and falls like 1 / sqrt(N) (0.292 at 1,000, 0.128 at 5,000). Constant-alpha TD has a much smaller spread over seeds (standard deviation 0.099 against 0.616 at 50 episodes) but is far from the truth early on: its error at 50 episodes is 4.7 against MC’s 1.4. That gap is bias from starting at 0 and passing information one state per visit. At 200 episodes TD(0.1) has not yet moved V(start) from 0 (the average estimate is −0.18, true value 3.31); at 1,000 episodes it averages 3.32 with a standard deviation of 0.28 across seeds, while MC at 200 episodes averages 3.38 with a standard deviation of 0.84.
• On this task and with these settings MC with sample averaging is the most accurate for all budgets I tried, and TD(0) does not beat it. I did not reproduce the often-quoted advantage of TD over MC here. That advantage, found in the random-walk example of Sutton and Barto (2018), depends on the task and on tuning; in the ward the goal is far, the reward is sparse, and the first few hundred episodes are spent carrying information back. Do not take this table as a general ranking.
• The step size is a real trade. A constant alpha of 0.3 learns fastest but had stalled near an error of 1.0 by 1,000 episodes, as expected from a constant step; alpha 0.05 is slow but ends lower (0.39 at 5,000 episodes). Decaying schedules that satisfy the Robbins-Monro conditions do best at 5,000 episodes: n^−0.7 reaches 0.142, close to MC’s 0.128, while n^−0.51 (0.262) has not yet averaged the noise out.
• 1 / n satisfies both conditions and is the worst TD schedule here (2.349 after 5,000 episodes). With alpha = 1 / n the value is the plain average of all its past targets, including the early targets built on a wrong V(s′), so early errors are never forgotten fast enough. The conditions say TD(0) with 1 / n will converge eventually; they do not say when.
• The n-step and TD(lambda) rows use the same alpha 0.05 as the TD(0) and constant-alpha MC rows. At 1,000 episodes 4-step TD (0.536) and lambda 0.8 (0.504) are below both TD(0) (0.915) and constant-alpha MC (0.594), while 8-step TD (0.643) is not below MC. The gap between 0.504 and 0.594 is only about 2 standard errors of the difference over 30 seeds, so read it as "intermediate settings can be a little better than either end", not as a ranking.

What the simulation simplifies. A table, a known and fixed policy, a start distribution that touches every state and a small state space. All settings were run once with no tuning beyond those shown, and the ranking can change with them. The tabular world is also exactly where the deadly triad cannot appear.

Engineering implications and limitations

Pick the target by the task

If episodes are short and the reward is noisy, Monte Carlo is simple and unbiased. If episodes are long or never end, or if you need to learn online while the robot moves, you need bootstrapping. A middle value of n or lambda is a sensible default in practice; check it on your own task as I did on the ward.

Treat alpha as a first-order setting

Report the step size and schedule with every result. A large constant alpha learns quickly and plateaus; a small one is slow; a decaying schedule can win but its decay rate matters (the example shows 0.142 against 0.262 at 5,000 episodes for exponents 0.7 and 0.51). Decay per state, using that state’s visit count, not a global clock, if some states are visited rarely.

Initialise with care

TD bootstraps from V, so the initial table is part of the bias. Starting at 0 is pessimistic when rewards are mostly positive and optimistic when most are negative; here it slowed TD down. Optimistic initial values are sometimes used on purpose to encourage exploration, which lesson M4-T7 returns to.

Handle episode ends exactly

Mark terminals and time-outs differently. At a goal or a crash the next value is 0; at a time limit the true value is not 0 and the target should still bootstrap. Mixing these up is a classic bug (lab M4-L4 debugs the terminal-state version of this bug).

Where this goes next

TD(0) learns the value of a fixed policy. Replacing V by an action value and the next state’s estimate by the best (or the chosen) next action gives Q-learning and SARSA in lesson M4-T6; the update you write in lab M4-L2 (implement Q-learning), q_update, is a TD(0) step on Q. With a function approximator instead of a table the same updates are used in deep reinforcement learning, with the deadly triad to watch for.

Common misconceptions

Engineering takeaways

1. First-visit Monte Carlo averages whole returns: unbiased but noisy, and it needs episodes to end. TD(0) updates every step with V(s) + alpha (r + gamma V(s′) − V(s)): lower variance, biased by its own estimate.
2. On the ward the TD target has about 5.6 times smaller spread than the return (0.675 against 3.78), but TD(0) still learned more slowly than sample-average MC because the bias takes many visits to wash out; do not generalise that in either direction.
3. n-step returns and TD(lambda) interpolate between TD(0) and Monte Carlo; at the same alpha, 4-step TD and lambda 0.8 beat both ends at 1,000 episodes on the ward, but by a small margin.
4. Robbins-Monro (the sum of alpha diverges, the sum of alpha squared converges) gives convergence only asymptotically and in the tabular case; constant alpha fluctuates around the answer.
5. Bootstrapping is safe in a table; with function approximation and off-policy data it is part of the deadly triad, which later modules return to.

References and further reading

The textbook treatment of Monte Carlo and TD prediction, the original TD paper, and the source of the step-size conditions.

• R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd edition, MIT Press, 2018 (chapters 5, 6, 7 and 12; section 11.3 for the deadly triad).
• R. S. Sutton, “Learning to predict by the methods of temporal differences”, Machine Learning 3(1), 9–44, 1988.
• H. Robbins and S. Monro, “A stochastic approximation method”, Annals of Mathematical Statistics 22(3), 400–407, 1951.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: turn the TD update into control. Q-learning and SARSA learn action values, and the choice of target decides whether the agent learns the safe route or the risky one.

Related content

Nothing below is required to finish this lesson.

• Before
  M4-T4: Dynamic Programming and Value Iteration

  Run value iteration on a small grid world, and explain why it converges.

• Lab
  M4-L2: Implement Q-Learning

  Scout does not know the map: learn a route from trial and error with a tabular Q-learning agent.