Advantages of TD over MC and DP

Why Does This Exist?

In reinforcement learning, estimating how good a state is—its value $V(s)$—requires predicting cumulative future rewards. Before Temporal Difference (TD) learning emerged, practitioners relied on two classical frameworks, each suffering from a crippling limitation:

1. Dynamic Programming (DP) requires a complete model: DP methods like policy iteration and value iteration compute values by calculating expected future rewards. However, they require perfect mathematical specifications of transition probabilities $p(s' \mid s, a)$ and reward distributions. In complex domains such as robotic locomotion, autonomous navigation, or game playing, writing down these transition matrices is impossible. Furthermore, DP requires exhaustive sweeps over all states, making it intractable for large state spaces.
2. Monte Carlo (MC) requires complete episodes and suffers from high variance: MC methods eliminate the need for an environmental model by interacting with the world and sampling raw trajectories. But MC updates only after an episode terminates, because it computes the actual total return $G_t$. This means MC cannot learn on continuous, non-terminating tasks. Moreover, summing rewards over an entire rollout compounds the stochastic randomness of every subsequent transition and action, producing high-variance targets that require vast amounts of data to converge.

Temporal Difference learning resolves both bottlenecks simultaneously. Like Monte Carlo, TD is model-free, learning directly from sampled transitions without knowing transition probabilities. Like Dynamic Programming, TD bootstraps, updating value estimates based on other learned value estimates after a single transition. This synthesis gives TD the sample efficiency of online learning, the low variance of one-step updates, and the universal ability to learn from continuing tasks.

Think of It Like This

How It Actually Works

The Reinforcement Learning Trinity: DP, MC, and TD

The relationship between Dynamic Programming, Monte Carlo, and Temporal Difference learning is characterized by two orthogonal dimensions: sampling (whether the algorithm requires an environmental model or learns from experience) and bootstrapping (whether updates rely on successor value estimates or complete episode returns).

1                      BOOTSTRAPPING (Depth = 1)2                                ▲3                                │4               Dynamic          │          Temporal5             Programming        │       Difference [TD(0)]6               (DP)             │7                                │8   EXHAUSTIVE ◄─────────────────┼─────────────────► SAMPLING9   EXPECTATIONS                 │                   EXPERIENCE10   (Model-Based)                │                   (Model-Free)11                                │12                                │            Monte Carlo13                                │               (MC)14                                ▼15                       FULL ROLLOUT (Depth = ∞)

1. Dynamic Programming Backup (Model-Based, Bootstrapping)

Dynamic Programming performs full-width, shallow-depth backups using the Bellman expectation equation:

$V(s) \leftarrow \sum_{a \in \mathcal{A}} \pi(a \mid s) \sum_{s' \in \mathcal{S}} \sum_{r \in \mathcal{R}} p(s', r \mid s, a) \left[ r + \gamma V(s') \right]$

• Model dependency: Requires the transition probability function $p(s', r \mid s, a)$.
• Bootstrapping: Yes, uses current estimates $V(s')$.
• Sampling: No, computes expectations across all possible next states.
• Variance: Zero (deterministic calculation under a known model).

2. Monte Carlo Backup (Model-Free, No Bootstrapping)

Monte Carlo samples individual trajectories and updates values toward the full discounted empirical return $G_t$:

$V(S_t) \leftarrow V(S_t) + \alpha \left[ G_t - V(S_t) \right]$

where the return $G_t$ is defined across the entire remaining trajectory until terminal time step $T$:

$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots + \gamma^{T-t-1} R_T$

• Model dependency: None (model-free).
• Bootstrapping: No, relies exclusively on realized rewards.
• Sampling: Yes, follows sample paths through the environment.
• Variance: High, because stochastic state transitions and action choices compound multiplicatively along the path.
• Bias: Zero, because $\mathbb{E}[G_t \mid S_t = s] = v_\pi(s)$.

3. Temporal Difference TD(0) Backup (Model-Free, Bootstrapping)

TD(0) samples a single step $(S_t, A_t, R_{t+1}, S_{t+1})$ and bootstraps using the successor state estimate $V(S_{t+1})$:

$V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$

The quantity in brackets is the TD error, denoted $\delta_t$:

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

where the TD target is $R_{t+1} + \gamma V(S_{t+1})$.

• Model dependency: None (model-free).
• Bootstrapping: Yes, updates toward an estimate rather than the true return $G_t$.
• Sampling: Yes, updates along experienced state-action transitions.
• Variance: Low, because the target depends only on the single immediate reward $R_{t+1}$ and the smooth value $V(S_{t+1})$.
• Bias: Initial bias exists due to imperfect $V(S_{t+1})$ estimates, but bias vanishes asymptotically as values converge.

Feature Comparison Matrix

Worked numerical example

Consider a 3-state chain environment with states $S_0, S_1, S_2$ leading to a terminal state:

$S_0 \xrightarrow{R_1 = +2} S_1 \xrightarrow{R_2 = -1} S_2 \xrightarrow{R_3 = +8} \text{Terminal}$

Let the discount factor be $\gamma = 0.9$ and the learning rate be $\alpha = 0.2$. Suppose the current value estimates are:

$V(S_0) = 0.0, \quad V(S_1) = 5.0, \quad V(S_2) = 10.0, \quad V(\text{Terminal}) = 0.0$

Step 1: The 1-Step TD Update (Online at $t=1$)

After taking action $A_0$ in $S_0$, the agent receives immediate reward $R_1 = +2.0$ and transitions to $S_1$. The agent computes the TD target and TD error immediately:

$\text{TD Target} = R_1 + \gamma V(S_1) = 2.0 + (0.9 \times 5.0) = 2.0 + 4.5 = 6.5$

$\delta_0 = \text{TD Target} - V(S_0) = 6.5 - 0.0 = 6.5$

The value of $S_0$ updates right away:

$V(S_0) \leftarrow V(S_0) + \alpha \delta_0 = 0.0 + (0.2 \times 6.5) = 1.30$

Notice: State $S_0$ is updated at time step 1. The agent did not need to know what happens at $S_1$, $S_2$, or whether the episode ever finishes.

Step 2: The Monte Carlo Update (Delayed until $t=3$)

Under Monte Carlo, no update can occur until the agent traverses $S_1$ and $S_2$ and lands in the terminal state at $t=3$. Only then can it compute the full discounted return $G_0$:

$G_0 = R_1 + \gamma R_2 + \gamma^2 R_3 = 2.0 + 0.9 \times (-1.0) + (0.9)^2 \times 8.0$

$G_0 = 2.0 - 0.9 + (0.81 \times 8.0) = 1.1 + 6.48 = 7.58$

The MC update for $S_0$ occurs only at the end of the episode:

$V(S_0) \leftarrow V(S_0) + \alpha [G_0 - V(S_0)] = 0.0 + 0.2 \times (7.58 - 0.0) = 1.516$

Why This Difference Matters

1. Information propagation: TD began improving its estimate of $S_0$ at $t=1$. In long or continuous environments, TD propagates value information backward step by step during the rollout.
2. Variance isolation: If the final transition from $S_2$ had a noisy reward (e.g., $+20$ half the time and $-4$ half the time), every MC return $G_0$ would swing wildly. TD replaces the entire downstream tail with $V(S_1) = 5.0$, insulating the update of $S_0$ from the variance of subsequent transitions.

Code

The following script benchmarks TD(0) against First-Visit Monte Carlo on a 5-state Random Walk. It quantifies target variance and convergence speed:

1import math2import random3import statistics4from typing import Dict, List, Tuple5
6def compare_td_and_mc() -> None:7    # Set seed for exact numerical reproducibility8    random.seed(42)9
10    # 5-State Random Walk: states 1..5; terminals 0 (reward 0) and 6 (reward 1)11    # Analytical true values: V*(s) = s / 6.012    true_v: Dict[int, float] = {s: s / 6.0 for s in range(1, 6)}13
14    def generate_episode() -> List[Tuple[int, float, int]]:15        trajectory: List[Tuple[int, float, int]] = []16        state = 3  # Start in the center state17        while state not in (0, 6):18            action = -1 if random.random() < 0.5 else 119            next_state = state + action20            reward = 1.0 if next_state == 6 else 0.021            trajectory.append((state, reward, next_state))22            state = next_state23        return trajectory24
25    # Generate 150 shared episodes for identical empirical conditions26    episodes: List[List[Tuple[int, float, int]]] = [27        generate_episode() for _ in range(150)28    ]29
30    # 1. Target Variance Comparison at Center State (S3)31    # Compare empirical variance of MC return G vs TD target (R + gamma * V(s'))32    mc_returns_s3: List[float] = []33    td_targets_s3: List[float] = []34    baseline_v: Dict[int, float] = {s: s / 6.0 for s in range(7)}35
36    for ep in episodes:37        for i, (s, r, s_next) in enumerate(ep):38            if s == 3:39                # TD target uses single-step reward + successor estimate40                td_targets_s3.append(r + 1.0 * baseline_v[s_next])41                # MC return sums all future rewards along the trajectory42                return_g = sum(step[1] for step in ep[i:])43                mc_returns_s3.append(return_g)44                break45
46    var_mc = statistics.variance(mc_returns_s3)47    var_td = statistics.variance(td_targets_s3)48
49    # 2. Value Estimation Convergence (TD(0) vs First-Visit MC)50    v_mc: Dict[int, float] = {s: 0.5 for s in range(1, 6)}51    v_td: Dict[int, float] = {s: 0.5 for s in range(1, 6)}52    alpha = 0.0553
54    for ep in episodes:55        # First-Visit MC update (delayed until episode completion)56        visited_states = set()57        accumulated_g = 0.058        for s, r, _ in reversed(ep):59            accumulated_g += r60            if s not in visited_states:61                visited_states.add(s)62                v_mc[s] += alpha * (accumulated_g - v_mc[s])63
64        # TD(0) update (applied online after every single transition)65        for s, r, s_next in ep:66            next_val = 0.0 if s_next in (0, 6) else v_td[s_next]67            td_target = r + 1.0 * next_val68            v_td[s] += alpha * (td_target - v_td[s])69
70    rmse_mc = math.sqrt(sum((v_mc[s] - true_v[s]) ** 2 for s in range(1, 6)) / 5)71    rmse_td = math.sqrt(sum((v_td[s] - true_v[s]) ** 2 for s in range(1, 6)) / 5)72
73    print(f"MC Target Variance (S3): {var_mc:.4f}")74    print(f"TD Target Variance (S3): {var_td:.4f}")75    print(f"MC RMSE after 150 episodes: {rmse_mc:.4f}")76    print(f"TD RMSE after 150 episodes: {rmse_td:.4f}")77
78compare_td_and_mc()79
80# -> Expected output:81# -> MC Target Variance (S3): 0.250182# -> TD Target Variance (S3): 0.028083# -> MC RMSE after 150 episodes: 0.061184# -> TD RMSE after 150 episodes: 0.0464

Watch Out For

The Quick Version

• The Best of Both Worlds: Temporal Difference learning combines the model-free interaction of Monte Carlo with the one-step bootstrapping of Dynamic Programming.
• No Environmental Model Needed: Unlike Dynamic Programming, TD does not require explicit transition probability matrices $p(s' \mid s, a)$ or reward functions; it learns directly from experienced transitions.
• Online, Step-by-Step Updates: Unlike Monte Carlo, TD updates immediately after each transition, enabling efficient learning in real time and supporting non-terminating, continuous environments.
• Lower Target Variance: Bootstrapping on $V(S_{t+1})$ avoids accumulating the stochastic noise of entire future trajectories, allowing TD to converge with significantly fewer training samples than Monte Carlo.

What to Read Next

• Temporal Difference Learning
• Dynamic Programming in RL
• Monte Carlo Methods