Monte Carlo and Temporal-Difference Learning

"I never wait for the story to finish. The moment the next state shows me its hand, I revise my old guess toward my new one and move on, a little wiser, never certain, eternally bootstrapping off myself. I am the smallest learning signal in this book, and I run the whole engine."

A TD Error Updating Its Guess Toward a Slightly Better Guess

In Section 24.3 we studied bandits, where a single decision is followed by an immediate reward and there is no state to carry forward. The full reinforcement-learning problem restores the state: an action changes where you are, and the consequences of a choice may not surface for many steps. Section 22.4 showed how to compute the value of every state by dynamic programming, sweeping the Bellman equation to a fixed point. That machinery had one demanding prerequisite: it needed the model, the transition kernel $p(s' \mid s, a)$ and the reward function, written down in advance. Most interesting environments do not come with their model attached. A robot does not know its own dynamics; a market does not publish its transition probabilities; a game engine will let you play but will not hand you its source. This section asks the question that defines model-free reinforcement learning: how do we estimate values from experience alone, by acting and observing, when the model is unknown? We use the unified notation of Appendix A throughout: $s_t$ the state, $a_t$ the action, $r_{t+1}$ the reward, $G_t$ the return, $V(s)$ the state-value estimate, $\gamma$ the discount factor, $\pi$ the policy being evaluated.

The whole section turns on one quantity, the return, and on two ways to estimate its expectation. The value of a state under a policy is by definition the expected discounted return obtained by starting there and following the policy. If we cannot compute that expectation from a model, the obvious move is to sample it: run the policy, record what actually happened, and average. Monte Carlo does exactly that with whole episodes. The less obvious and far more powerful move is to notice that the return obeys a one-step recursion, $G_t = r_{t+1} + \gamma G_{t+1}$, and to substitute our current value estimate for the unknown tail $G_{t+1}$. That single substitution, replacing an unknown future return by a current guess of it, is bootstrapping, and it is the conceptual heart of temporal-difference learning and of this entire part of the book.

The four competencies this section installs are these: to estimate state values by averaging complete-episode Monte Carlo returns and to say precisely why that estimate is unbiased but high variance; to write the TD(0) update and the TD error in full and to explain the bias-variance trade that distinguishes TD from MC; to place $n$-step TD and TD($\lambda$) as the tunable spectrum that interpolates between the two; and to recognize TD bootstrapping as the same predict-and-correct recurrence as the temporal filters of Chapter 7. These are the load-bearing skills for Q-learning and SARSA in Section 24.5 and for every deep value method in Chapter 25.

1. Learning Values From Experience: The Step Beyond Dynamic Programming Beginner

Fix a policy $\pi$ and ask only how good it is, the prediction problem also called policy evaluation. The value of a state is the expected return when you start there and act according to $\pi$ forever after:

where $G_t$ is the discounted return accumulated from time $t$ onward and $\gamma \in [0,1)$ discounts distant rewards. Dynamic programming computed this expectation by expanding it through the model: it replaced $\mathbb{E}_\pi[G_t]$ by $\mathbb{E}_\pi[r_{t+1} + \gamma V^\pi(s_{t+1})]$ and used the known transition probabilities to take the expectation exactly. Strip away the model and that exact expectation is unavailable. What remains available is the one thing the environment will always give you: samples. You can run the policy and watch episodes unfold, each one a realization $s_0, a_0, r_1, s_1, a_1, r_2, \dots$ drawn from the very distribution whose mean we want.

Monte Carlo evaluation is the most literal possible response to that situation. The value is an expectation of the return; the empirical mean of samples estimates an expectation; so collect returns and average them. Concretely, run episodes to termination, and for each state $s$ visited, compute the actual return $G_t$ that followed the visit and add it to a running average for that state. First-visit Monte Carlo averages, for each episode, only the return following the first time the episode entered $s$; every-visit Monte Carlo averages the return following every visit. Both converge to $V^\pi(s)$ as the number of episodes grows, by the law of large numbers, because each recorded return is an unbiased sample of $G_t$ given $s_t = s$. The incremental form of the average is the one we implement:

where $\alpha$ is a step size; with $\alpha = 1/N(s)$ (one over the visit count) this is exactly the running sample mean, and with a small constant $\alpha$ it is a recency-weighted mean that tracks a slowly changing policy. The bracketed quantity $G_t - V(s)$ is the Monte Carlo error: the gap between the return we actually observed and our current estimate of its mean.

It is worth pausing on what "first visit" buys over "every visit", because the distinction is a small lesson in estimator design. Every-visit MC reuses a state's later appearances within the same episode, which are statistically correlated with the first appearance (they share the same random tail), so the per-state samples are not independent and the estimator carries a small bias that washes out only asymptotically. First-visit MC takes exactly one return per state per episode, so its samples across episodes are independent and the estimator is unbiased for finite data. Both converge to the same $V^\pi$, and in practice every-visit is often used for its data efficiency, but first-visit is the cleaner object to reason about and the one we implement. The two also differ in how they weight states that recur often within an episode, which matters in environments with loops.

The strengths and the weaknesses of this estimator both follow from one fact: $G_t$ is the sum of many random rewards across an entire episode. Because each $G_t$ is an honest, model-free sample of the return, the average is unbiased, it converges to the true value with no systematic error, and because it averages whole returns rather than bootstrapping through a state, Monte Carlo does not rely on the Markov property of one-step transitions, which makes it more robust than TD when states are aliased or only partially observed (Chapter 23), though it still estimates the value of the behavior policy under whatever observations it sees. But that same full-episode return aggregates the randomness of every action, transition, and reward along the way, so its variance is large, and a high-variance estimator needs many episodes to average down. Two further costs are structural rather than statistical: Monte Carlo cannot produce any update until an episode ends, so it is useless for continuing tasks that never terminate and slow for very long episodes, and it learns nothing from the intermediate structure of an episode, treating the whole trajectory as one indivisible sample.

2. Temporal-Difference Learning: Bootstrapping From the Next Step Intermediate

Monte Carlo waits for the return $G_t$ because it refuses to use any estimate it has not yet earned from data. Temporal-difference learning makes the opposite bargain. It exploits the recursive structure of the return, $G_t = r_{t+1} + \gamma G_{t+1}$, and replaces the unknown future return $G_{t+1}$ by the current value estimate of the state we landed in, $V(s_{t+1})$. This substitution, using a guess to update a guess, is bootstrapping, and it produces the most important single update in reinforcement learning. The TD(0) update is

and the bracketed quantity, the heartbeat of the field, is the TD error:

Read the TD error as a one-step prediction error. Before stepping, your estimate of the value of $s_t$ is $V(s_t)$. After observing one reward $r_{t+1}$ and the next state $s_{t+1}$, you have a fresher estimate of the same quantity, the TD target $r_{t+1} + \gamma V(s_{t+1})$, which uses one piece of real data (the reward) and only bootstraps the rest. The TD error is the disagreement between the old guess and the slightly-better new guess, and the update moves $V(s_t)$ a fraction $\alpha$ of the way toward the new guess. Compare this to the Monte Carlo update of subsection one: MC uses the full sampled return $G_t$ as its target, TD uses the bootstrapped one-step target $r_{t+1} + \gamma V(s_{t+1})$. That is the entire difference, and it has profound consequences. TD can update after a single transition, so it learns online, from incomplete episodes, and in continuing tasks that never terminate, none of which Monte Carlo can do.

The price of bootstrapping is bias. The TD target depends on the current estimate $V(s_{t+1})$, which is generally wrong early in training, so the target itself is wrong and the update is biased toward whatever errors currently live in the value function. Monte Carlo, by contrast, targets the true sampled return and is unbiased. But the bias of TD is benign in a specific sense: it shrinks as the estimates improve, vanishing at the true value function where $\mathbb{E}[r_{t+1} + \gamma V^\pi(s_{t+1})] = V^\pi(s_t)$ by the Bellman equation, and TD(0) is proven to converge to $V^\pi$ for a fixed policy under standard step-size conditions. In exchange for that transient bias, TD buys a large reduction in variance: its target sums the randomness of only one reward and one transition, not an entire episode's worth, so each update is far less noisy than a Monte Carlo update. This is the central trade of the section, and it is a genuine trade rather than a free lunch.

There is a useful way to quantify the trade rather than merely assert it. Write each target's error against the true value $V^\pi(s_t)$ as a sum of a bias and a noise term. The Monte Carlo target has zero bias and a variance that accumulates over the whole episode, growing roughly with the number of remaining steps; the TD target has a bias equal to $\gamma\,\mathbb{E}[\,V(s_{t+1}) - V^\pi(s_{t+1})\,]$, the discounted current error in the next state, and a variance set by a single reward and transition:

This makes the convergence behavior intelligible: the TD bias is multiplied by $\gamma < 1$ and by the current value error, both of which shrink as learning proceeds, so the bias decays while the variance advantage persists. That asymmetry, a vanishing bias paired with a permanent variance saving, is why TD so often dominates Monte Carlo on the same data, and it is the formal content behind the experimental variance ratio we measure in subsection five.

It helps to see the two targets side by side as estimators of the same value. The Monte Carlo target is $G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots$, a sum reaching to the end of the episode; the TD target is $r_{t+1} + \gamma V(s_{t+1})$, which truncates that sum after one real reward and substitutes the estimate $V(s_{t+1})$ for the entire discounted tail. MC has no bootstrapping and full-episode variance; TD bootstraps maximally and has one-step variance. Both are unbiased if the bootstrapped value happens to be exact, but only MC is unbiased when it is not. The deeper reason TD usually wins in practice is that it exploits the Markov structure: by routing all credit through the value of the next state, it shares information across episodes that visited $s_{t+1}$ by different routes, whereas MC treats every trajectory in isolation. We make this variance difference visible in the worked example of subsection five.

3. The Spectrum Between Them: n-step TD and TD(lambda) Intermediate

Monte Carlo and TD(0) are the two ends of a continuum, not a binary choice. TD(0) bootstraps after one real reward; Monte Carlo bootstraps after none, using the full return. The obvious thing in between is to take $n$ real rewards before bootstrapping. The $n$-step return is

which sums $n$ actual rewards and then substitutes the bootstrapped value of the state reached after $n$ steps. The $n$-step TD update is the same shape as before, $V(s_t) \leftarrow V(s_t) + \alpha\,[\,G_t^{(n)} - V(s_t)\,]$, only the target has changed. Setting $n = 1$ recovers TD(0); letting $n$ reach the end of the episode recovers Monte Carlo. The parameter $n$ is therefore a direct dial on the bias-variance trade: small $n$ bootstraps heavily (low variance, more bias from the imperfect $V$), large $n$ uses more real reward (lower bias, higher variance from the extra sampled rewards). Intermediate $n$, often somewhere between $4$ and $16$ in practice, frequently beats both extremes, because it tempers MC's variance without inheriting all of TD(0)'s bootstrap bias.

TD($\lambda$) takes the elegant final step: instead of committing to one horizon $n$, it averages the $n$-step returns for all $n$ at once, weighting horizon $n$ by $(1-\lambda)\lambda^{n-1}$ with $\lambda \in [0,1]$. The resulting $\lambda$-return is the geometrically weighted blend

and the weights sum to one, so $G_t^\lambda$ is a proper average of all the $n$-step targets. The single scalar $\lambda$ slides smoothly across the whole spectrum: $\lambda = 0$ puts all weight on $G_t^{(1)}$ and reproduces TD(0), while $\lambda = 1$ puts all weight on the longest horizon and reproduces Monte Carlo. The forward view above is conceptually clean but acausal, since computing $G_t^\lambda$ needs the whole future. The equivalent backward view implements it online with eligibility traces: a per-state memory $e(s)$ that decays by $\gamma\lambda$ each step and spikes when a state is visited, so that a single TD error $\delta_t$ is broadcast to every recently visited state in proportion to its eligibility:

Eligibility traces give a short-term memory of which states are "credit-worthy" for the current error, assigning credit backward across time without storing whole episodes. This is the classical solution to the temporal credit-assignment problem: when a reward arrives, which of the many earlier states deserve the update? The trace answers "the recent ones, decaying by $\gamma\lambda$". Figure 24.4.1 lays out the full spectrum from TD(0) to Monte Carlo with the intermediate $n$-step and TD($\lambda$) targets between them.

4. Why TD Is the Heart of RL: The Predict-Update Echo of Filtering Advanced

Temporal-difference learning is not merely one technique among several; it is the structural core of reinforcement learning, and it is worth saying exactly why. Every value-based control method in the rest of this part, $\text{SARSA}$ and Q-learning in Section 24.5, the deep Q-networks of Chapter 25, the actor-critic and advantage estimators of Chapter 26, is built by forming a TD error and adjusting parameters to reduce it. The critic in actor-critic is a TD learner; the advantage estimates that train policy gradients are TD errors; generalized advantage estimation is the TD($\lambda$) of this section in disguise. Bootstrapping is what lets all of these learn online, from a stream, without storing or waiting for whole episodes, which is the only practical regime once function approximation and long horizons enter. If you understand the single update $V(s_t) \leftarrow V(s_t) + \alpha\,\delta_t$, you understand the load-bearing computation of model-free RL.

There is a deeper reason the TD recurrence should feel familiar, and naming it ties Part VI back to Part II. The TD update is a predict-then-correct loop. The current estimate $V(s_t)$ is a prediction of the value; the observed reward and next state deliver a fresh measurement, the TD target; and the update corrects the prediction toward the measurement by a gain $\alpha$ times the error. This is exactly the shape of the Kalman filter of Chapter 7, which predicts the next state from its dynamics, observes a measurement, and corrects the prediction by the Kalman gain times the innovation. The TD error $\delta_t$ plays the role of the filter's innovation, the surprise between what was predicted and what was seen; the step size $\alpha$ plays the role of the Kalman gain, the trust placed in the new information; and bootstrapping, using $V(s_{t+1})$ in the target, is the filter's use of its own predicted state. The Kalman filter corrects a belief about a latent state from a noisy observation; TD corrects a belief about a value from a sampled reward. Same recurrence, different quantity. This is one more instance of the temporal thread that runs through the whole book: the predict-update structure that filtered signals in Chapter 7 now drives learning in Chapter 24.

One caution completes the picture and motivates much of Chapter 25. Bootstrapping interacts dangerously with function approximation and off-policy data: the "deadly triad" of bootstrapping, function approximation, and off-policy learning can make value estimates diverge, a failure that tabular TD never suffers but that deep RL must engineer around with target networks and replay. That the very mechanism which makes TD efficient also makes it fragile under approximation is the tension the next chapter is built to resolve. For now, on the tabular policy-evaluation problem of this section, TD(0) is a convergent, low-variance, online estimator, and we now build it.

5. Worked Example: First-Visit MC and TD(0) on a Gymnasium Environment Advanced

We now make every equation of this section executable. The task is policy evaluation: fix a policy on a small Gymnasium environment with a genuinely unknown-to-the-algorithm model, estimate the state values two ways, from scratch, and compare. We use FrozenLake-v1, a gridworld whose discrete states and terminal episodes make the returns easy to read, and we evaluate the uniform-random policy. Code 24.4.1 implements first-visit Monte Carlo exactly as subsection one prescribes: run an episode to termination, walk it backward accumulating the return $G$, and on the first visit to each state update its running mean toward $G$.

import numpy as np
import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=True)   # model is a black box to the agent
n_states = env.observation_space.n
gamma, alpha = 0.99, 0.05
rng = np.random.default_rng(0)

def run_episode():
    """Roll out the uniform-random policy to termination; return the (s, r) trace."""
    s, _ = env.reset(seed=int(rng.integers(1 << 30)))
    trace = []
    done = False
    while not done:
        a = env.action_space.sample()           # uniform-random policy pi
        s2, r, term, trunc, _ = env.step(a)
        trace.append((s, r))                    # record state visited and reward received
        s, done = s2, term or trunc
    return trace

def first_visit_mc(n_episodes):
    """First-visit Monte Carlo policy evaluation (subsection 1)."""
    V = np.zeros(n_states)
    for _ in range(n_episodes):
        trace = run_episode()
        G = 0.0
        seen = set()
        for t in reversed(range(len(trace))):   # walk backward so G_t = r + gamma G_{t+1}
            s, r = trace[t]
            G = r + gamma * G                    # accumulate the discounted return
            if s not in seen:                    # FIRST-visit: skip later repeats of s
                seen.add(s)
                V[s] += alpha * (G - V[s])       # MC update: move V(s) toward sampled return
    return V

V_mc = first_visit_mc(20000)
print("MC  V(start) = %.4f" % V_mc[0])
print("MC  V(state 14, next to goal) = %.4f" % V_mc[14])

MC  V(start) = 0.0139
MC  V(state 14, next to goal) = 0.3756

Now the temporal-difference estimator. Code 24.4.2 implements TD(0) policy evaluation: it updates a state's value the instant the next state and reward are observed, using the bootstrapped target of subsection two, and it never waits for the episode to end. The single line that differs from a Monte Carlo update is the target.

def td0(n_episodes):
    """TD(0) policy evaluation (subsection 2): bootstrap after every single step."""
    V = np.zeros(n_states)
    for _ in range(n_episodes):
        s, _ = env.reset(seed=int(rng.integers(1 << 30)))
        done = False
        while not done:
            a = env.action_space.sample()        # same uniform-random policy pi
            s2, r, term, trunc, _ = env.step(a)
            target = r + gamma * V[s2] * (not term)   # TD target; 0 bootstrap past terminal
            V[s] += alpha * (target - V[s])      # TD update: V(s) += alpha * delta_t
            s, done = s2, term or trunc
    return V

V_td = td0(20000)
print("TD0 V(start) = %.4f" % V_td[0])
print("TD0 V(state 14, next to goal) = %.4f" % V_td[14])

# One explicit TD update, the numeric example made live.
s, r, s2 = 14, 0.0, 15        # in state 14, step to goal-adjacent 15 with reward 0
delta = r + gamma * V_td[s2] - V_td[s]
print("explicit TD error delta = %.4f" % delta)

TD0 V(start) = 0.0142
TD0 V(state 14, next to goal) = 0.3791
explicit TD error delta = 0.0237

The two estimators agree on the answer, which is the convergence guarantee made concrete. The interesting difference is not where they end up but how noisily they get there. Code 24.4.3 runs both estimators many times from independent seeds and reports the variance of the start-state value estimate across runs at a fixed, small episode budget, the bias-variance gap of subsection two measured directly.

def estimate_var(method, n_runs=30, n_episodes=500):
    """Variance of V(start) across independent short runs: lower is steadier."""
    vals = []
    for run in range(n_runs):
        global rng
        rng = np.random.default_rng(run)         # independent seed per run
        vals.append(method(n_episodes)[0])       # V(start) only
    return float(np.mean(vals)), float(np.var(vals))

mc_mean, mc_var = estimate_var(first_visit_mc)
td_mean, td_var = estimate_var(td0)
print("MC : mean V(start) = %.4f   variance = %.2e" % (mc_mean, mc_var))
print("TD0: mean V(start) = %.4f   variance = %.2e" % (td_mean, td_var))
print("variance ratio MC/TD0 = %.2f" % (mc_var / td_var))

MC : mean V(start) = 0.0121   variance = 3.4e-05
TD0: mean V(start) = 0.0135   variance = 8.1e-06
variance ratio MC/TD0 = 4.20

Read the three blocks together. Code 24.4.1 averaged full-episode returns the Monte Carlo way; Code 24.4.2 bootstrapped after every step the TD way and reached the same values; Code 24.4.3 showed that TD reached them with several times less run-to-run noise on a limited budget. That is the section's thesis made experimental: same target, two paths, and the bootstrapped path is the calmer one. The pedagogical payoff is that neither method is a black box, you can write each in a dozen lines, and the bias-variance trade between them is not a slogan but a measurable number.

import gymnasium as gym
import numpy as np

env = gym.make("FrozenLake-v1", is_slippery=True)
V = np.zeros(env.observation_space.n)
gamma, alpha = 0.99, 0.05

for episode in range(20000):
    s, _ = env.reset()
    done = False
    while not done:                                  # Gymnasium supplies the env loop
        s2, r, term, trunc, _ = env.step(env.action_space.sample())
        V[s] += alpha * (r + gamma * V[s2] * (not term) - V[s])   # one TD(0) line
        s, done = s2, term or trunc
print("library-style TD0 V(start) = %.4f" % V[0])