Advantages of TD over MC and DP

Why Does This Exist?

Estimating a state's value means predicting the rewards still to come. The two classical answers each demand something you often lack.

Dynamic programming computes values from a perfect model: transition probabilities and reward tables for every outcome. Hand it the model and it sweeps the state space with zero sampling noise. Refuse it the model, which is the normal case in robotics and games, and it cannot start. Big spaces make the sweeps costly too.

Monte Carlo methods drop the model and learn from real episodes. Honest prices. You must finish the episode before any update, so continuing tasks that never terminate get nothing. Worse, the target sums noise from every future step, so variance balloons and data demands explode.

Temporal-difference learning takes the workable half of each. Like Monte Carlo it learns model-free from sampled transitions. Like dynamic programming it bootstraps from successor estimates after a single step. You get online updates, continuing-task support, and low-variance targets, paying with bias that fades as the table improves.

Think of It Like This

How It Actually Works

Symbols for this page: $V(s)$ is the estimated value of state $s$, $R_{t+1}$ the next reward, $\gamma$ the discount, $\alpha$ the step size, $G_t$ the full Monte Carlo return, and $\delta_t$ the TD error. Two ideas split the three methods: sampling (model or experience) and bootstrapping (estimates or full returns).

Dynamic programming backs up a full expectation one step deep. It needs the model $p(s', r \mid s, a)$ and the current successor values, computes with zero variance, and sweeps offline. Monte Carlo backs up one sampled episode at full depth. It needs no model, uses only realized rewards, carries zero bias since the expected return equals the true value, and pays with high variance plus end-of-episode timing. TD with one-step depth backs up one sampled transition:

The bracket is the TD error $\delta_t$, and $R_{t+1} + \gamma V(S_{t+1})$ is the TD target. Model-free like Monte Carlo, bootstrapping like dynamic programming, constant work per step, usable mid-episode and in continuing tasks.

Three properties side by side

Model needed: dynamic programming wants the full transition model, while Monte Carlo and TD learn from experience alone. Bootstrapping: dynamic programming and TD bootstrap at depth 1, Monte Carlo never bootstraps. Update timing: dynamic programming sweeps offline in batches, Monte Carlo waits for termination, TD updates after every transition. Variance runs from zero to high to low across the three. Bias runs from zero with a true model, to none for Monte Carlo, to early bias for TD that vanishes as values converge.

Worked example with target 6.50 against return 7.58

A three-state chain pays $+2$, then $-1$, then $+8$ before terminating. Discount $\gamma = 0.9$, step size $\alpha = 0.2$, values $V(S_0) = 0.0$, $V(S_1) = 5.0$, $V(S_2) = 10.0$, terminal $0.0$.

TD acts after the first transition $(S_0 \to S_1, R_1 = 2.0)$:

State $S_0$ improves at step one. Nothing downstream needed.

Monte Carlo must walk the whole chain first, then discounts all three rewards:

Same start, two lessons. TD learns sooner and insulates $S_0$ from late-trajectory noise by substituting the smooth $V(S_1)$ for the whole tail. Monte Carlo sees the true $+8$ but imports every wobble along the way. If that last reward flipped between $+20$ and $-4$ across episodes, the TD update would barely move while the Monte Carlo target swung wildly.

Code

A short check of the two updates above, with type hints throughout:

1from typing import List2
3
4def td_update(v0: float, reward: float, v_next: float, gamma: float, alpha: float) -> float:5    target = reward + gamma * v_next6    return v0 + alpha * (target - v0), target7
8
9def mc_return(rewards: List[float], gamma: float) -> float:10    total = 0.011    for k, r in enumerate(rewards):12        total += (gamma ** k) * r13    return total14
15
16gamma = 0.917alpha = 0.218
19v_td, td_target = td_update(0.0, 2.0, 5.0, gamma, alpha)20print([round(td_target, 2), round(v_td, 2)])21# -> [6.5, 1.3]22
23g0 = mc_return([2.0, -1.0, 8.0], gamma)24print([round(g0, 2), round(alpha * g0, 2)])25# -> [7.58, 1.52]

1# -> expected output:2[6.5, 1.3]3[7.58, 1.52]

Watch Out For

The Quick Version

• Dynamic programming needs a model and sweeps offline, Monte Carlo needs finished episodes and pays high variance, TD needs neither.
• The TD update $V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$ learns after every transition, including in continuing tasks.
• Bootstrapping cuts variance by replacing the noisy tail with a smooth estimate, at the price of early bias that fades with convergence.
• On rewards $[2.0, -1.0, 8.0]$ with $\gamma = 0.9$, the TD target is $6.50$ giving $1.30$, while the Monte Carlo return is $7.58$ giving $1.52$.
• With function approximation plus off-policy data, bootstrapping can diverge, so use target networks and modest step sizes.

What to Read Next

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