Monte Carlo and TD Learning

Dynamic Programming needed a fully known model of the environment — real problems rarely offer one. This page introduces the two foundational ways to learn value functions purely from experience: waiting to see how things actually turned out, or updating immediately using your own current guess.

Key idea

Monte Carlo waits for the true return; temporal difference learning bootstraps from its own current estimate and updates immediately.

The model-free setting

Neither method here requires knowing $P$ or $R$ — both learn $V^\pi$ (or $Q^\pi$) purely from sampled trajectories generated by actually running the policy in the environment. This is the defining shift from Dynamic Programming: experience replaces a known model entirely.

Monte Carlo prediction: average the observed returns

The simplest possible idea: run full episodes under policy $\pi$, and for each visited state, average the actual observed return $G_t$ that followed. By the law of large numbers, this average converges to $V^\pi(s) = \mathbb{E}_\pi[G_t \mid s_t = s]$ as more episodes accumulate — no model needed at all, just direct empirical averaging.

First-visit vs. every-visit

First-visit MC: only include the return following the first occurrence of a state within an episode. Every-visit MC: include the return following every occurrence. Both converge to the same $V^\pi$ in the limit; first-visit has cleaner theoretical properties (each episode contributes independent samples per state), every-visit uses the available data more fully.

MC needs complete episodes, which rules out continuing tasks

Because Monte Carlo waits for the actual return $G_t$, it can only update once an episode has fully terminated — the return isn't known until then. This makes MC entirely unusable for continuing tasks with no natural termination, and even for long episodic tasks it means no learning happens until the episode ends, however long that takes.

Temporal difference learning: the TD(0) update

$$V(s_t) \leftarrow V(s_t) + \alpha \left[ r_{t+1} + \gamma V(s_{t+1}) - V(s_t) \right]$$

Instead of waiting for the true return, TD(0) updates immediately after a single step, using the current estimate $V(s_{t+1})$ as a stand-in for everything that would follow — replacing "wait and see" with "estimate now, using what you currently believe about the future."

The TD error as the learning signal

$$\delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t)$$

The TD error $\delta_t$ measures the gap between the current estimate $V(s_t)$ and a one-step-improved estimate — every TD-based algorithm in this section, all the way through Actor-Critic Methods, is built around some variant of this exact quantity.

Bootstrapping defined, and why it is the central idea

Bootstrapping means updating an estimate using other estimates, rather than only actual observed outcomes — TD(0) bootstraps by using $V(s_{t+1})$ (itself just an estimate, possibly wrong) as part of its own update target. Monte Carlo does not bootstrap at all — it only ever uses genuinely observed returns. This single distinction is the axis every method in this section can be placed along, and every algorithm page states it explicitly.

The bias/variance trade between MC and TD, made concrete

Monte Carlo: unbiased (the true return is, by definition, an unbiased sample of $V^\pi$), but high variance — a full episode's return depends on every random action and transition along the way. TD(0): lower variance (only one step's randomness enters each update), but biased while $V$ is still inaccurate, since it bootstraps from a potentially-wrong estimate. Neither dominates the other unconditionally — the right choice depends on episode length, environment stochasticity, and how much data is available.

n-step returns as the interpolation

$$G_t^{(n)} = r_{t+1} + \gamma r_{t+2} + \dots + \gamma^{n-1} r_{t+n} + \gamma^n V(s_{t+n})$$

An n-step return uses $n$ real observed rewards before bootstrapping from the estimate — $n=1$ recovers plain TD(0); $n \to \infty$ recovers Monte Carlo. Choosing $n$ directly dials the bias/variance trade-off between the two extremes.

Eligibility traces and TD(λ), conceptually

Rather than picking one fixed $n$, TD(λ) maintains an eligibility trace — a decaying memory of recently-visited states — and updates all recently-visited states proportionally to how recently they were visited, each time a TD error occurs. This effectively averages over all n-step returns simultaneously, weighted by $\lambda$, giving a smooth, tunable dial between TD(0) ($\lambda = 0$) and Monte Carlo ($\lambda = 1$) without needing to commit to a single $n$ in advance.

Comparison table

	Monte Carlo	TD(0)
Bias	unbiased	biased (while learning)
Variance	high	low
Needs complete episodes	yes	no
Update timing	end of episode	every step
Bootstraps	no	yes

Why TD dominates in practice

TD methods' ability to update online, every step, without waiting for episode completion — combined with typically lower variance — makes them the practical foundation for essentially every algorithm from Q-Learning and SARSA onward, including every deep RL method in this section. Pure Monte Carlo methods remain useful primarily as a conceptual baseline and in settings with short, cheap-to-complete episodes.

Symbol	Meaning
$G_t$	the actual observed return from time $t$
$\delta_t$	the TD error
$\alpha$	the learning-rate (step-size) parameter

Code: MC and TD(0) prediction compared against the DP ground truth

mc_td_demo.py

import numpy as np
import matplotlib.pyplot as plt
from grid_world_env import GridWorld
from dynamic_programming_demo import policy_evaluation
from mdp_demo import policy as fixed_policy, n_states

env = GridWorld()
gamma = 0.95
V_true = policy_evaluation(fixed_policy)  # DP ground truth to measure error against
rng = np.random.default_rng(0)

def state_to_index(pos):
    return pos[0] * env.size + pos[1]

def run_episode():
    trajectory = []
    state = env.reset()
    for _ in range(50):
        s_idx = state_to_index(state)
        action = rng.choice(4, p=fixed_policy[s_idx])
        next_state, reward, done = env.step(action)
        trajectory.append((s_idx, reward))
        state = next_state
        if done:
            break
    return trajectory

def monte_carlo_prediction(n_episodes):
    V = np.zeros(n_states)
    counts = np.zeros(n_states)
    errors = []
    for ep in range(n_episodes):
        trajectory = run_episode()
        G, visited_returns = 0.0, {}
        for s_idx, reward in reversed(trajectory):
            G = reward + gamma * G
            visited_returns[s_idx] = G  # first-visit: later assignment (earlier in reverse) wins
        for s_idx, G in visited_returns.items():
            counts[s_idx] += 1
            V[s_idx] += (G - V[s_idx]) / counts[s_idx]  # running average
        errors.append(np.abs(V - V_true).mean())
    return errors

def td_prediction(n_episodes, alpha=0.1):
    V = np.zeros(n_states)
    errors = []
    for ep in range(n_episodes):
        state = env.reset()
        for _ in range(50):
            s_idx = state_to_index(state)
            action = rng.choice(4, p=fixed_policy[s_idx])
            next_state, reward, done = env.step(action)
            s_next_idx = state_to_index(next_state)
            td_target = reward + gamma * V[s_next_idx] * (not done)
            V[s_idx] += alpha * (td_target - V[s_idx])  # TD(0) update
            state = next_state
            if done:
                break
        errors.append(np.abs(V - V_true).mean())
    return errors

mc_errors = monte_carlo_prediction(500)
td_errors = td_prediction(500)

plt.plot(mc_errors, label="Monte Carlo (high variance)")
plt.plot(td_errors, label="TD(0) (lower variance)")
plt.xlabel("episode"); plt.ylabel("mean |V - V_true|")
plt.legend(); plt.title("estimate error against DP ground truth")
plt.savefig("mc_vs_td_convergence.png")

See also

• Q-Learning and SARSA — turning TD prediction into a control algorithm that learns to act.
• Dynamic Programming — the known-model exact case these methods approximate from experience.