RobotGuide
Foundations/Model-Free: The Bias-Variance Ledger of MC vs TD

Foundations 04 / 11 · Value functions

Model-Free: The Bias-Variance Ledger of MC vs TD

Real return as the target or a bootstrap as the target - this one choice decides the shape of every algorithm that follows. Includes a reproducible measured comparison

60 minFoundational6 derivation steps4 self-test questions

One-line conclusion

MC uses the real return as its target: unbiased, but variance grows linearly with the episode length. TD uses 'one step of reward plus its own estimate' as the target: biased, but with far smaller variance. Under the same sample budget, TD's error can be one third of MC's.

This is the quantitative answer to 'why TD is the default'. It is also the prerequisite for understanding GAE - GAE is exactly a tunable interpolation between these two extremes.

Symbol table

SymbolMeaning
αLearning rate. In tabular methods it directly decides 'how much weight the new sample gets'
δ_tTD error = r + γV(s') - V(s); every algorithm that follows revolves around it
G_t^{(n)}The n-step return: n steps of real reward plus the estimate at step n
λThe decay coefficient of the eligibility trace, controlling 'how far you trust the bootstrap'

Derivation

  1. The MC update: treat the real return as the supervision signal
  2. The TD update: use one estimate to correct another estimate
  3. n-step: connecting the two extremes with a line
  4. Measured: how much better TD is on the same budget
  5. The convergence conditions, and why nobody uses them in practice
  6. Why this difference becomes 'do you need a target network' in deep RL

1. The MC update: treat the real return as the supervision signal

Finish an episode, compute the actual discounted return of every step, then move the value toward it. Formally it is just 'supervised learning', with G_t as the label.

V(S_t) ← V(S_t) + α[ G_t - V(S_t) ]

Why this holdsUnbiased: G_t is genuinely sampled from the environment, and its expectation is V^π(S_t). But high variance: if rewards are independent with variance σ², the variance of a T-step return is about σ²(1-γ^{2T})/(1-γ²), growing with episode length. On a 100-step trajectory, the noise in G_0 can exceed the signal by an order of magnitude.

2. The TD update: use one estimate to correct another estimate

Do not wait for the episode to end; update every step. The target is 'this step's reward plus the current estimate of the next state'. This is called bootstrapping.

V(S_t) ← V(S_t) + α[ rt+1 + γV(St+1) - V(S_t) ]

Why this holdsThe bracket is the TD error δ_t. The target contains V(S_{t+1}), which is an estimate, so the target is 'biased'. But distinguish two kinds of bias: (1) bias during training because V is still inaccurate; (2) at the converged limit, E[δ_t]=0 and the bias vanishes. Many people merge these two into one sentence 'TD is biased' and then tune in the wrong direction.

3. n-step: connecting the two extremes with a line

Take n steps of real reward, then attach the estimate at step n. n=1 is TD, n=∞ is MC. n is 'how long you trust real rewards'.

G_t(n) = rt+1 + γrt+2 + … + γn-1rt+n + γ^n V(St+n)

Why this holdsTD(λ) goes further and averages all n-step returns with geometric weights (1-λ)λ^{n-1}. λ=0 degenerates to TD(0); λ=1 degenerates to MC. This 'λ interpolation' idea reappears verbatim in policy gradient under the name GAE.

4. Measured: how much better TD is on the same budget

The 5-state random walk (the classic test bed), γ=1, each episode starts in the middle and moves randomly; reaching the right end pays 1, the left end pays 0. 1000 episodes, averaged over 30 seeds.

with α=0.005: TD RMSE 0.014, MC RMSE 0.044

Why this holdsTD's error is about one third of MC's. The reason is not that 'TD is smarter' but sample efficiency: on a 9-step trajectory TD updates 9 times while MC updates once (and only after the episode ends). Push α higher and MC's variance eats the gains fast: at α=0.15 MC's RMSE rises to 0.21 while TD only reaches 0.071.

5. The convergence conditions, and why nobody uses them in practice

Tabular convergence requires the learning rate to satisfy two conditions: the sum diverges (guaranteeing you can get arbitrarily far) and the sum of squares converges (guaranteeing it eventually settles down).

∑_t α_t = ∞ and ∑_t α_t² < ∞ (e.g. α_t = 1/t)

Why this holdsIn practice people use constant α or slow decay. With constant α, TD converges to 'the solution of the most recent data' rather than the global solution - an advantage in nonstationary environments (it can track change), at the price of jittering forever late in training. When the loss curve tail jitters, first check whether this is just normal constant-α behavior before swapping algorithms.

6. Why this difference becomes 'do you need a target network' in deep RL

The TD target contains the very parameters you are updating. In tabular methods this is fine (each update touches one cell), but with function approximation one update changes the estimates at every state simultaneously, and the target moves with them - the 'moving target'.

tabular: updating V(s) affects only s; function approximation: updating w affects every v̂(s;w)

Why this holdsTarget networks, soft updates, and delayed updates all exist to pin this moving target down temporarily. Expanded in article 5 on function approximation.

Work it by hand

A 4-step trajectory: s0 →(r=0)→ s1 →(r=0)→ s2 →(r=1)→ terminal. Set all V initial values to 0.5, α=0.5, γ=1. Apply one pass of MC and one pass of TD(0), and write down the updated V.

  1. MC: G_2 = 1, G_1 = 0+1×1 = 1, G_0 = 1; all three states move halfway toward 1: V = 0.75 (s0, s1, s2 all identical)
  2. TD from the back forward: V(s2) ← 0.5 + 0.5×(1 + 0 - 0.5) = 0.75
  3. V(s1) ← 0.5 + 0.5×(0 + 0.75 - 0.5) = 0.625
  4. V(s0) ← 0.5 + 0.5×(0 + 0.625 - 0.5) = 0.5625
Answer

MC gives [0.75, 0.75, 0.75]; TD gives [0.5625, 0.625, 0.75]. TD's answer 'looks more conservative', but its gradient structure is right: states nearer the terminal have higher values, farther ones lower. MC pours in the information beyond three steps all at once with equal weight, which is noisier in the short run - this is what bias and variance look like on a single trajectory.

Run it

40 lines, reproducing the table above. Change α and the episode count yourself and watch how sensitive MC is to α - more convincing than any verbal explanation.

python · numpy only
import numpy as np
G = 1.0
def run(alpha, episodes, mode, seed):
    r = np.random.default_rng(seed)
    V = np.full(7, 0.5); V[0] = 0.0; V[6] = 0.0   # terminal at both ends, both values 0
    for _ in range(episodes):
        s, traj = 3, []
        while True:
            s2 = s + (1 if r.random() < 0.5 else -1)
            rw = 1.0 if s2 == 6 else 0.0
            traj.append((s, rw, s2)); s = s2
            if s in (0, 6): break
        if mode == 'mc':
            gt = 0.0
            for (st, rt, sn) in reversed(traj):
                gt = rt + G * gt
                V[st] += alpha * (gt - V[st])
        else:
            for (st, rt, sn) in traj:
                V[st] += alpha * (rt + G * V[sn] - V[st])
    return V
truth = np.arange(7) / 6.0
for mode in ['mc', 'td']:
    e = [np.sqrt(((run(0.005, 1000, mode, s)[1:6] - truth[1:6])**2).mean()) for s in range(30)]
    print(mode, 'RMSE = %.3f' % np.mean(e))

You pass when you see this

td RMSE ≈ 0.014, mc RMSE ≈ 0.044. If your mc does better instead, check the terminal state value: the V of the right-end terminal state must be 0 (the reward is given on the step entering it); writing 1 inflates the TD target by 1 and everything is wrong.

Self-test · 4 questions

Answer first, then expand. Each question traces back to a specific derivation section.

01To what extent does TD's 'bias' vanish, and to what extent does it not?

Bias caused by an inaccurate V vanishes at convergence (E[δ]=0). But the bias intrinsic to 'using an estimate as the target' does not vanish - it shows up at the fixed point: you are solving the Bellman equation, whose solution is exactly V^π, so the limit is accurate. The bias that truly never vanishes comes from function approximation (article 5).

02On a 200-step episode with γ=0.99, what magnitude is MC's return variance roughly?

About 1/(1-γ²) ≈ 50 times the single-step reward variance (if rewards are roughly independent). So on long episodes MC is basically unusable; you must use TD or n-step.

03Why does practice almost never use 1/t learning rate decay?

Because environments are usually nonstationary (the policy changes, the data distribution changes); 1/t drives the learning rate to zero too early and nothing can be tracked. Constant α plus a target network is the more common combination.

04How large should n be in the n-step return?

Commonly 3~5 (PPO by default cuts 1-step TD inside its n=2048-step rollout; DQN uses 1). Large n → closer to MC, unbiased but high variance; small n → faster but more bias. Increase it for sparse-reward tasks.

Keep reading

Previous: the Bellman equationNext: function approximation and the deadly triadRun experiments in the browser
PreviousThe Bellman Equation: Why V Is a Fixed Point and Why Iteration Must Converge NextFunction approximation: the three ingredients that take you from 'guaranteed convergence' to 'blowing up'

The whole series · 11 articles

01The Only Four Math Tools You Need40 min02MDP and Return: Writing 'What To Do' as Something Computable45 min03The Bellman Equation: Why V Is a Fixed Point and Why Iteration Must Converge60 min04Model-Free: The Bias-Variance Ledger of MC vs TD60 min05Function approximation: the three ingredients that take you from 'guaranteed convergence' to 'blowing up'55 min06Policy gradient: deriving REINFORCE line by line70 min07Actor–critic and GAE: turning the variance knob to λ60 min08PPO: what does clip actually clip70 min09SAC: entropy, reparameterization, double Q - three parts, each solving one problem75 min10HER: why goal relabeling is mathematically legitimate50 min11How to debug non-convergence: map symptoms back to formulas45 min