Learning from experience: Monte Carlo and TD

At the end of Chapter 4 you could compute the best policy for any gridworld, as long as someone handed you the transition probabilities $P(s' \mid s, a)$ and the rewards $r(s, a)$. Almost nobody hands you those. A robot does not know the friction of the floor. A backgammon program does not have a formula for the chance of winning from a given board. A language model does not know in advance which answers a grader will like. What all of them can do is act, and watch what happens.

This chapter is about learning from that stream of experience alone. You will meet two ideas that run through the rest of the course. Monte Carlo learning waits until an episode ends and averages the returns it actually saw. Temporal-difference (TD) learning updates a guess from the next guess, one step later, without waiting. Then you will turn both into control algorithms: SARSA, Q-learning and Expected SARSA. You will also see why two of them, on the same cliff, learn to walk very different paths. In Chapter 1 you watched an agent learn a gridworld and were promised the algorithm later. This is where it comes from.

What you have when you don’t have a model

Recall the setup from Chapter 3. An agent in state $s_t$ takes action $a_t$, receives reward $r_t$, and lands in $s_{t+1}$. An episode is one run from a start state to a terminal state $s_T$:

The return from step $t$ is $G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \dots + \gamma^{T-t-1} r_{T-1}$, and the value of a state under policy $\pi$ is its expected return, $V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s]$.

Dynamic programming computed $V^\pi$ by sweeping over all states and taking exact expectations with $P$. Now we drop $P$ and $r$. A method that learns without them is called model-free. All it gets is sampled episodes. We split the job in two, exactly as in Chapter 4:

• Prediction (policy evaluation): given a fixed policy $\pi$, estimate $V^\pi$ from episodes generated by following $\pi$.
• Control: find a good policy, which means estimating values and improving the policy at the same time.

We start with prediction, on the smallest interesting example.

The running example: a random walk

Five states in a row, A to E, with an exit at each end:

Every episode starts in C. At each step a fair coin sends you one state left or right. Leaving E to the right ends the episode with reward $+1$. Leaving A to the left ends it with reward $0$. Every other step gives $0$. There are no decisions to make, so this is pure prediction: the “policy” is the coin. Take $\gamma = 1$, so the return of an episode is $1$ if it exits right and $0$ if it exits left. The value of a state is then the probability of exiting right from it.

This problem is small enough to solve exactly, which is why it is useful: you can check any learning method against the right answer. The Bellman expectation equation says $V(s) = \tfrac12 V(\text{left of } s) + \tfrac12 V(\text{right of } s)$, with boundary values $0$ beyond A and $1$ beyond E. A function whose value at every point is the average of its neighbours has zero second difference. It is the discrete Laplace equation, and its solution is a straight line between the boundary values:

Our learners will not know this. Each one starts from the guess $V = 0.5$ everywhere and learns from episodes.

Monte Carlo: average what actually happened

The definition $V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s]$ suggests the most direct method there is. Every time you visit $s$, write down the return that followed. Average those returns. By the law of large numbers the average converges to $V^\pi(s)$. Methods that estimate expectations by averaging samples are called Monte Carlo (MC) methods, after the casino. Physicists use them for integrals. Here the integral is over all possible futures.

Two small choices define the variants:

• First-visit vs. every-visit. If a state appears twice in an episode, first-visit MC uses only the return from its first visit. Every-visit MC uses the return from every visit. Both converge to $V^\pi$. First-visit gives independent samples, which makes the theory cleaner. Every-visit is simpler to code and is what most people write.
• Sample mean vs. constant step size. You can keep a running average, or you can use the incremental update from Chapter 2:

This is the pattern “estimate ← estimate + step size × (target − estimate)” again, with the return $G_t$ as the target. With $\alpha = 1/N(s)$ it computes the exact sample mean. With a constant $\alpha$ it weights recent returns more heavily, which helps when the policy (and therefore the true value) keeps changing, as it will during control. This version is called constant-α MC.

A worked example. Suppose the first episode is C → D → E → exit right. With $\gamma = 1$, every step’s return is the final reward: $G = 1$ from C, from D and from E. With $\alpha = 0.1$, each visited state moves a tenth of the way from $0.5$ toward $1$:

A and B were not visited, so they stay at $0.5$. One episode has taught all three visited states something.

Every-visit constant-α Monte Carlo prediction
  input: policy π, step size α
  initialise V(s) arbitrarily (e.g. 0.5), V(terminal) = 0
  repeat for each episode:
      generate s0, a0, r0, ..., s_{T-1}, a_{T-1}, r_{T-1}, s_T by following π
      G = 0
      for t = T-1 down to 0:              # backward pass computes all returns
          G = r_t + γ G
          store G_t = G
      for t = 0 to T-1:
          V(s_t) += α (G_t − V(s_t))

Monte Carlo has three properties worth stating plainly. Its target $G_t$ is an honest sample of the thing we want, so it is unbiased. It must wait until the episode ends before it can update anything, so it does not work for tasks that never end. And its target can be very noisy, because $G_t$ adds up the randomness of every future step. The next method trades the first property for relief on the other two.

TD(0): learn a guess from a guess

Start with something you already do. You leave the lab at 18:00 and estimate you will be home in 30 minutes. Here is how your predictions evolve on the way:

How should you correct the 18:00 guess of 30 minutes? The Monte Carlo answer: wait until you get home, see that the trip took 43, and push the 18:00 guess toward 43. The temporal-difference answer: you already learned something at the car. Five minutes in, your newer, better-informed prediction said 40 in total, so your 18:00 guess was about 10 minutes optimistic. Push it toward 40 now. Then push the “at the car” guess toward the “off the highway” guess, and so on. Each prediction learns from the next prediction.

The TD corrections are $+10, -5, +5, +3$. They add up to $+13$, which is exactly the Monte Carlo correction $43 - 30$. That is no accident (see the derivation below). TD spreads the same total correction over the steps where the information actually arrived.

The update

Now write this down for values. The Bellman expectation equation from Chapter 3 says the value of a state is the expected immediate reward plus the discounted value of where you land:

Dynamic programming computed that expectation exactly with $P$. TD makes two substitutions. It replaces the expectation with the single transition you just experienced, and it replaces the unknown $V^\pi(s_{t+1})$ with your current estimate $V(s_{t+1})$. The result is the TD target $r_t + \gamma V(s_{t+1})$, and the update moves $V(s_t)$ toward it:

The quantity in brackets has a name you will see in every remaining chapter, the TD error:

It measures surprise: how much better or worse the step turned out than your estimate of $s_t$ predicted. If $s_{t+1}$ is terminal, $V(s_{t+1}) = 0$ by definition. This method is called TD(0), or one-step TD, because the target looks one step ahead.

Updating an estimate using another estimate is called bootstrapping, after pulling yourself up by your own bootstraps. Dynamic programming bootstraps too (value iteration’s targets use $V_k$). Monte Carlo does not: its target $G_t$ contains only real rewards. TD is the method that both bootstraps (like DP) and learns from samples (like MC).

TD(0) prediction
  input: policy π, step size α
  initialise V(s) arbitrarily, V(terminal) = 0
  repeat for each episode:
      s = start state
      repeat until s is terminal:
          a = action from π(·|s)
          take a, observe r, s'
          V(s) += α (r + γ V(s') − V(s))       # update NOW, not at the end
          s = s'

The worked example, TD version

Same first episode, C → D → E → exit right, same $\alpha = 0.1$, all values $0.5$:

• C → D, reward 0: $\delta = 0 + 0.5 - 0.5 = 0$. No change.
• D → E, reward 0: $\delta = 0 + 0.5 - 0.5 = 0$. No change.
• E → exit, reward 1: $\delta = 1 + 0 - 0.5 = 0.5$, so $V(E) = 0.5 + 0.1 \times 0.5 = 0.55$.

Only E moved. C and D had nothing to learn from their successors, because their successors’ estimates had not changed yet. Now suppose the second episode takes the same path:

• C → D: $\delta = 0 + 0.5 - 0.5 = 0$. No change.
• D → E: $\delta = 0 + 0.55 - 0.5 = 0.05$, so $V(D) = 0.505$.
• E → exit: $\delta = 1 - 0.55 = 0.45$, so $V(E) = 0.595$.

The news of the reward crawls backward one state per episode. On this example, that looks like a weakness compared with Monte Carlo, which moved all three states at once. The payoff comes when you look at noise rather than at a single lucky episode. That is the next section.

Monte Carlo vs. TD: bias and variance

Both methods have the form “move $V(s_t)$ toward a target”. They differ only in the target, so compare the targets as estimators of the thing we want, $V^\pi(s_t)$.

Bias. The MC target $G_t$ has expectation exactly $V^\pi(s_t)$. That is the definition of $V^\pi$. It is unbiased, whatever your current estimates are. The TD target has expectation

The first term is $V^\pi(s)$ by the Bellman equation. The second term is the error of your current estimates one step ahead. So the TD target is biased whenever $V$ is wrong, which early in learning is always. The bias shrinks as $V$ improves, and vanishes at $V = V^\pi$.

Variance. $G_t$ depends on every random action, transition and reward from $t$ to the end of the episode. The TD target depends on just one of each. On the random walk, look at state C with the true values in hand. The MC target from C is $0$ or $1$ with probability $\tfrac12$ each, so its variance is $\tfrac14$. The TD target from C is $V(B) = \tfrac13$ or $V(D) = \tfrac23$, so its variance is $(\tfrac16)^2 = \tfrac1{36}$. That is nine times smaller. On long episodes the gap is far larger, because the MC target accumulates noise from every step.

Which matters more? On most problems, variance does. A biased but steady target lets you take bigger steps. And TD’s bias corrects itself. Average a TD update over the random next step, and apply it to every state at once: you get $V \leftarrow V + \alpha(\mathcal{T}^\pi V - V)$, where $\mathcal{T}^\pi$ is the Bellman operator from Chapter 4. That is a damped version of the iteration you proved converges there, because $\mathcal{T}^\pi$ is a γ-contraction. So the bias shrinks geometrically as the estimates converge (Exercise 5.2 does the proof). The demo lets you see the result.

Three things are worth noticing in the demo.

1. TD learns faster on average. With $\alpha = 0.1$ for both methods, TD’s averaged error after 100 episodes is around $0.055$. MC’s is around $0.14$, more than twice as large. Even at its best step size (around $\alpha = 0.02$), MC ends near $0.08$, while TD at $\alpha = 0.05$ gets below $0.04$.
2. Large step sizes level off at a higher error. A constant step size never fully averages away the noise in the targets: the estimate keeps jumping toward the most recent sample. The floor is roughly proportional to $\alpha$ times the target’s variance, which is why MC’s floor is higher.
3. A single run is noisy. The thin lines wander. When you compare algorithms, average over many runs and seeds (the lab does this too).

Tabular TD(0) is guaranteed to converge to $V^\pi$ for a fixed policy if every state keeps being visited and the step sizes shrink in the usual way ($\sum_k \alpha_k = \infty$ and $\sum_k \alpha_k^2 < \infty$, the Robbins–Monro conditions). With a small constant $\alpha$ it converges in the mean and then hovers near $V^\pi$, as in the demo.

Same data, different answers

There is a second, subtler difference. Suppose you stop collecting episodes and instead replay a fixed batch of data again and again until each method settles. Sutton & Barto’s Example 6.4 makes the point with eight episodes:

• A → B (reward 0) → exit (reward 0), once.
• B → exit (reward 1), six times.
• B → exit (reward 0), once.

Both methods agree that $V(B) = \tfrac68 = 0.75$. For A they disagree. Batch Monte Carlo averages the returns that followed A. There is only one, and it was $0$, so $V(A) = 0$. Batch TD notices that A always led to B with reward $0$, so $V(A) = 0 + V(B) = 0.75$.

TD’s answer is the value you would compute if you first fitted the most likely Markov model to the data (A goes to B with probability 1; B pays 1 with probability $\tfrac68$) and then solved that model exactly. This is called the certainty-equivalence estimate. MC’s answer is the one that best fits the returns already observed. If the process really is Markov, TD’s answer generalizes better: it uses all six B-episodes to learn about A. That is a large part of why TD tends to win on Markov problems. Exercise 5.4 asks you to work out a case of your own.

n-step returns: the dial between them

MC and TD(0) are the two ends of a dial. TD(0) uses one real reward and then bootstraps. MC uses all the real rewards and never bootstraps. In between, the n-step return uses $n$ real rewards and then bootstraps from the estimate $n$ steps ahead:

If the episode ends before $t + n$, the bootstrap term is dropped and $G_{t:t+n}$ is just $G_t$. For $n = 1$ this is the TD(0) target. For $n$ at least as long as the episode it is the MC target. The n-step update moves $V(s_t)$ toward $G_{t:t+n}$, and it must wait $n$ steps before making it.

Each extra real reward reduces bias (less weight on the estimate) and adds variance (more randomness in the target). In practice an intermediate $n$ is often best. Rather than pick one $n$, you can average all of them with geometrically decaying weights. That gives the λ-return, and its practical form, GAE, is the heart of Chapter 8. We leave it there.

From prediction to control

Now let the agent choose its actions. The plan is the one from Chapter 4, generalized policy iteration (GPI): keep an estimate of the current policy’s values, keep making the policy greedy with respect to it, and let the two chase each other. Two adjustments are needed for the model-free setting.

Learn Q, not V. To act greedily with respect to $V$ you have to look one step ahead:

That needs $P$ and $r$, which we no longer have. Acting greedily with respect to $Q$ needs neither: $\pi(s) = \arg\max_a Q(s, a)$. The action values already contain the one-step lookahead. So every control method in this chapter learns a table $Q(s, a)$.

Keep exploring. If you always take the action that currently looks best, you never find out whether the others are better. This is the bandit problem of Chapter 2 again, now in every state. The standard fix is the ε-greedy policy: with probability $\epsilon$ take a uniformly random action, otherwise take $\arg\max_a Q(s, a)$ (breaking ties at random). Every action keeps a probability of at least $\epsilon / \lvert \mathcal{A} \rvert$.

All three algorithms below share the same loop and the same form of update:

They differ only in the target. That one line decides which policy the table ends up describing.

SARSA: on-policy TD control

The most direct move is to apply TD(0) to action values. Take the Bellman equation for $Q^\pi$,

and replace the expectation with one sample, exactly as before:

The update uses the five quantities $(s_t, a_t, r_t, s_{t+1}, a_{t+1})$, which is where the name SARSA comes from. The important detail is $a_{t+1}$: it is the action the agent will actually take next, chosen by its ε-greedy policy. So the agent must pick its next action before it can update.

SARSA
  initialise Q(s, a) = 0 for all s, a
  repeat for each episode:
      s = start state
      a = ε-greedy action from Q(s, ·)
      repeat until s is terminal:
          take a, observe r, s'
          a' = ε-greedy action from Q(s', ·)      # choose the next action first
          target = r            if s' is terminal
                   r + γ Q(s', a')   otherwise
          Q(s, a) += α (target − Q(s, a))
          s, a = s', a'

Since $a_{t+1}$ comes from the ε-greedy policy, the target is a sample of the Bellman equation for the ε-greedy policy. SARSA therefore learns $Q$ for the policy it is actually following, exploration included. Meanwhile that policy keeps getting greedier with respect to the improving $Q$. That is GPI with one sample per evaluation step. If you also let $\epsilon$ decay to zero slowly enough that every pair is still tried infinitely often (a schedule called GLIE, “greedy in the limit with infinite exploration”), SARSA converges to an optimal policy.

Q-learning: off-policy TD control

Q-learning makes one change to the target. Instead of the value of the next action you will take, it uses the value of the best next action:

This is a sampled version of the Bellman optimality equation for $Q^*$ from Chapter 4. You can read Q-learning as value iteration on $Q$, with one sampled transition in place of the exact sum over $s'$. Its fixed point is $Q^*$, however the agent is actually behaving.

Q-learning
  initialise Q(s, a) = 0 for all s, a
  repeat for each episode:
      s = start state
      repeat until s is terminal:
          a = ε-greedy action from Q(s, ·)          # behavior: explore
          take a, observe r, s'
          target = r                     if s' is terminal
                   r + γ max_a' Q(s', a')  otherwise    # target: greedy
          Q(s, a) += α (target − Q(s, a))
          s = s'

On-policy and off-policy, carefully

Q-learning acts with one policy and learns about another. To talk about this precisely we need two names:

• The behavior policy $b$ is the one that chooses the actions that generate the data. Here it is ε-greedy.
• The target policy $\pi$ is the one whose values you are learning. For Q-learning it is the greedy policy, the one that would take $\arg\max_a Q(s, a)$ everywhere.

A method is on-policy if the two are the same: it learns about the policy that generates its data. SARSA is on-policy. A method is off-policy if they can differ. Q-learning is off-policy: its target policy is greedy, while its behavior can be ε-greedy, purely random, or a human driving the robot, as long as every state–action pair keeps being tried.

Why doesn’t Q-learning need to correct for the mismatch? Look at what each part of an update depends on. $Q(s, a)$ is defined given that action $a$ was taken in $s$, so how $a$ was chosen does not matter. The next state $s'$ and reward $r$ come from the environment, not from any policy. The only place a policy enters is the choice of the next action, and there Q-learning plugs in the target policy’s choice (the max) instead of the action the behavior will actually take. So the behavior policy affects only which pairs get updated and how often, never what they are updated toward. Watkins and Dayan (1992) proved that tabular Q-learning converges to $Q^*$ under exactly those conditions: every pair visited infinitely often, and Robbins–Monro step sizes.

Off-policy learning is not always this cheap. If you wanted to evaluate a policy $\pi$ from whole Monte Carlo returns generated by a different policy $b$, you would have to reweight each return by the product of ratios $\pi(a_k \mid s_k) / b(a_k \mid s_k)$ along the episode. That product is an importance-sampling correction, and over long episodes its variance can explode. Importance ratios come back as $\rho_t(\theta)$ in Chapter 9, where they let PPO reuse slightly stale data.

Expected SARSA: average instead of sample

SARSA’s target uses one sampled next action $a_{t+1}$. That sample adds noise. If you know the policy’s probabilities (you do: you chose ε-greedy), you can average over the next action instead of sampling it:

This is Expected SARSA. In expectation it makes the same update as SARSA, but without the randomness of $a_{t+1}$, so it tolerates larger step sizes. For an ε-greedy $\pi$ over $\lvert\mathcal{A}\rvert$ actions, the sum is $\epsilon \cdot \text{mean}_{a'} Q(s', a') + (1 - \epsilon) \max_{a'} Q(s', a')$. It also unifies the family. If $\pi$ is the ε-greedy behavior policy, Expected SARSA is on-policy, like SARSA. If $\pi$ is greedy, the sum collapses to $\max_{a'} Q(s', a')$ and Expected SARSA is Q-learning.

Cliff walking: safe or optimal?

Here is the classic problem that shows the difference in a single picture (Sutton & Barto, Example 6.6). A 4 × 12 grid. You start at the bottom-left corner S and must reach the bottom-right corner G. The cells between them along the bottom row are a cliff. Every step costs $-1$. Stepping into the cliff costs $-100$ and sends you back to S. The episode ends at G, and $\gamma = 1$.

The optimal path walks along the edge of the cliff: up one, right eleven, down one, 13 steps, return $-13$. Both agents below explore with the same ε-greedy policy, use the same α, and see their episodes in lockstep. The only difference between them is the one line that computes the target.

With the default settings ($\epsilon = 0.1$, $\alpha = 0.5$) you should see what Sutton & Barto report:

• Q-learning’s greedy path hugs the cliff edge (13 steps). Its values are those of the greedy policy, and the greedy policy never steps off the edge.
• SARSA’s greedy path takes a detour, usually along the top row (17 steps). Its values are those of the ε-greedy policy. From a cell next to the cliff, that policy has a $\epsilon/4 = 2.5\%$ chance per step of picking “down”, which costs 100. SARSA’s table has priced that in, so the cells next to the cliff look expensive and the greedy path avoids them.
• While learning, SARSA earns more per episode: around $-25$, against around $-50$ for Q-learning. Q-learning’s agent walks the edge it believes is optimal, but it still explores, and an exploring agent on the edge falls off. Roughly once every three episodes, by the “falls per episode” row.

So which agent is right? Both, about different questions. Q-learning answers “what is the best thing to do, assuming I will act greedily from now on?”. SARSA answers “what is the best thing to do, given how I will actually behave, exploration and all?”. If your robot will keep making random moves (exploration, sensor noise, a slippery floor you didn’t model), SARSA’s caution is worth having. If you will switch exploration off before deployment, Q-learning’s path is the one you want. With $\epsilon$ decaying toward zero, the two answers converge, because the policies they evaluate converge.

Maximization bias and Double Q-learning

Q-learning’s max hides a trap. Suppose that in some state all ten actions have true value $0$, but your estimates are noisy: each $Q(s, a)$ equals the truth plus independent noise with standard deviation 1. The true value of the best action is $0$. The expected value of your estimated max is not. The maximum of ten independent standard normal samples has expectation about $1.54$. Taking the max of noisy estimates selects the ones whose noise happens to be positive. In general,

since the max is a convex function (this is Jensen’s inequality). Q-learning bootstraps from this max at every step, so the upward bias propagates backward through the table. This is called maximization bias. It is mild on deterministic problems like the cliff, where the targets are not noisy. It can be serious when rewards or transitions are random. Exercise 5.9 computes the bias exactly for two actions.

The fix is to stop using the same noisy numbers both to choose the best action and to evaluate it. Double Q-learning (van Hasselt, 2010) keeps two independent tables, $Q_A$ and $Q_B$. On each step, flip a coin. On heads, update $Q_A$, letting $Q_A$ pick the action and $Q_B$ say what it is worth:

On tails, swap the roles of A and B. Act ε-greedily with respect to $Q_A + Q_B$. Because $Q_B$‘s noise is independent of the choice $Q_A$ made, the evaluation is no longer biased upward (it can be slightly biased downward instead). The same idea, with the target network playing the role of $Q_B$, becomes Double DQN in Chapter 6.

Summary

• Model-free methods learn values from sampled experience, with no access to $P$ or $r$.
• Monte Carlo moves $V(s_t)$ toward the observed return $G_t$. The target is unbiased but high-variance, and it is only available when the episode ends.
• TD(0) moves $V(s_t)$ toward $r_t + \gamma V(s_{t+1})$, using the TD error $\delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$. It bootstraps: the target is biased by the current estimates but has low variance, and it updates after every step. The MC error is the discounted sum of TD errors.
• n-step returns interpolate between the two; their λ-weighted average becomes GAE in Chapter 8.
• For control, learn Q (so acting greedily needs no model) and explore with ε-greedy.
• SARSA (target uses the next action you will take) is on-policy: it learns the values of its own exploring policy. Q-learning (target uses the max) is off-policy: it learns $Q^*$ whatever the behavior policy, as long as everything keeps being tried. Expected SARSA averages over the next action and contains both.
• On the cliff, SARSA learns the safe detour and earns more while exploring. Q-learning learns the optimal edge path and falls off more while exploring.
• The max in Q-learning is biased upward under noise. Double Q-learning decouples choosing an action from evaluating it.

Exercises