Bootstrapping and the Bias-Variance Tradeoff

In reinforcement learning, prediction means estimating the value function $v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$, the expected return from a state under policy $\pi$. Every prediction method must decide what target to regress $V(S_t)$ toward. Monte Carlo prediction uses the actual sampled return

as the target, where $T$ is the terminal time step. This target is a genuine sample of the true random variable whose expectation defines $v_\pi(s)$, so it is unbiased: $\mathbb{E}[G_t \mid S_t = s] = v_\pi(s)$ exactly.

Bootstrapping, by contrast, means constructing an update target that includes an existing estimate rather than waiting for the process to finish. The canonical example is TD(0), whose target is

called the TD target. Instead of summing rewards all the way to termination, TD(0) takes one real reward and then substitutes the current estimate $V(S_{t+1})$ for everything that would happen afterward. The word "bootstrap" captures this self-referential structure: the value function is used to update itself, one step removed. Dynamic programming methods (value iteration, policy evaluation) are the purest form of bootstrapping — they use only estimates, no sampled experience at all. MC is the opposite pole — it uses only sampled experience, no bootstrapping at all. TD(0) sits in between: one real transition, then bootstrap. This single design choice determines two statistical properties of the update:

• Bias: a systematic tendency for the expected update target to differ from the true value $v_\pi(s)$, arising because $V(S_{t+1})$ is itself imperfect during learning.
• Variance: the spread of the target around its own mean, arising from the randomness of the trajectory (stochastic policy, stochastic transitions, stochastic rewards) that the target depends on.

MC targets are unbiased but depend on an entire random trajectory — every reward and every action choice from $t$ to termination injects noise, so variance can be large, especially for long episodes. TD targets depend on only one random reward and one random next state, so their variance is small, but because $V(S_{t+1})$ is generally wrong during learning, the target is biased toward whatever error currently exists in $V$. This bias vanishes only in the limit as $V \to v_\pi$, which is why TD methods are still guaranteed to converge under standard stochastic approximation conditions — but at any finite point in training, the update target is not a sample of the true return.

Consider one-step TD prediction, TD(0), operating alongside Monte Carlo prediction for comparison. Both estimate $v_\pi$ from experience generated by following $\pi$.

Monte Carlo update (every-visit, incremental form): ``` Initialize V(s) arbitrarily for all s, V(terminal) = 0 Repeat for each episode: Generate an episode S_0, A_0, R_1, S_1, A_1, R_2, ..., S_{T-1}, A_{T-1}, R_T G <- 0 For t = T-1 down to 0: G <- R_{t+1} + gamma G # accumulate the actual return V(S_t) <- V(S_t) + alpha (G - V(S_t)) ```

TD(0) update: ``` Initialize V(s) arbitrarily for all s, V(terminal) = 0 Repeat for each episode: Initialize S Repeat for each step of episode, until S is terminal: A <- action given by pi for S Take action A, observe reward R and next state S' V(S) <- V(S) + alpha (R + gamma V(S') - V(S)) # bootstrap target S <- S' ``` The critical difference is visible line-by-line: MC must run the loop `for t = T-1 down to 0` after the episode ends, requiring a full trajectory in memory and forcing the agent to wait for termination. TD(0) updates `V(S)` immediately, using the just-observed reward `R` plus the current guess `V(S')`, and can therefore run in continuing (non-terminating) tasks and update online, one step at a time. A useful way to see the whole spectrum is the n-step return, which foreshadows n-Step Bootstrapping Methods:

• $n = 1$ recovers the TD(0) target.
• $n \to \infty$ (or $n = T - t$) recovers the Monte Carlo return, since the bootstrap term vanishes at a terminal state.

TD(λ), covered in TD(lambda) and Eligibility Traces, is a weighted average of all $G_t^{(n)}$ for $n = 1, 2, \ldots$, controlled by a single parameter $\lambda \in [0,1]$, giving a continuously tunable dial between the low-variance, high-bias end (TD(0), $\lambda = 0$) and the unbiased, high-variance end (MC, $\lambda = 1$).

Time and space, per update. TD(0) performs $O(1)$ work per environment step: one lookup of $V(S')$, one arithmetic update. Its memory footprint is $O(1)$ beyond the value table itself, since it needs no trajectory history — the update at time $t$ only needs $S_t, R_{t+1}, S_{t+1}$. This is what makes TD(0) usable in continuing tasks with no terminal state at all. Monte Carlo requires $O(T)$ space to store (or replay) the full episode before any update can be made, where $T$ is the episode length, and $O(T)$ total time per episode to compute all returns via the backward accumulation `G <- R + gammaG`. Per-state-visit this is still $O(1)$ amortized work, but the latency* before the first update is $O(T)$ — MC cannot update online mid-episode, and cannot be used at all if $T = \infty$.

Bias — why TD(0) is biased and MC is not. Fix a state $s$ visited at time $t$. The MC target is $G_t$, a random variable whose expectation, by definition of $v_\pi$, satisfies

So $\mathbb{E}[G_t - v_\pi(s)] = 0$: no bias, regardless of the current value table (MC targets don't even reference the value table). The TD target is $R_{t+1} + \gamma V(S_{t+1})$. Taking expectation over the one-step transition,

If $V \equiv v_\pi$ exactly, the right-hand side equals $\mathbb{E}_\pi[R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t=s] = v_\pi(s)$ by the Bellman equation — so the TD target is unbiased only at the fixed point. During learning, $V \ne v_\pi$, so

which is exactly the (discounted, expected) error currently present in the successor state's estimate. This is why bootstrapped bias is often called "cascading" — early errors in $V$ propagate into targets for other states, and only shrink as $V$ improves.

Variance — why TD(0) has less. Write the MC return as a sum of $T - t$ (possibly random-length) reward terms:

If the per-step reward noise terms have roughly comparable variance $\sigma^2$ and are not perfectly negatively correlated, the variance of a sum of $T - t$ such terms scales roughly linearly in the number of terms (exactly so if independent):

which grows with episode length (bounded by $\sigma^2/(1-\gamma^2)$ as $T\to\infty$ but still large for long or highly stochastic episodes, and additionally inflated by variance in the policy's action choices along the way). The TD target's variance,

depends on only one reward and one next-state draw — it does not compound over a trajectory. This is the structural reason bootstrapped targets have dramatically lower variance: they truncate the random sum after one term and replace the remainder with a (fixed, non-random-given-$S_{t+1}$) point estimate.

Convergence. Both tabular MC and tabular TD(0), with step sizes satisfying the Robbins–Monro conditions $\sum_t \alpha_t = \infty, \sum_t \alpha_t^2 < \infty$, converge to $v_\pi$ with probability 1, under standard assumptions (finite MDP, all states visited infinitely often). TD(0)'s convergence proof relies on the Bellman operator $T^\pi$ being a $\gamma$-contraction in the max norm, so successive bootstrapped applications shrink error geometrically in expectation, even though any single update is biased. MC's convergence is the standard law-of-large-numbers argument for sample averages of i.i.d.-ish returns per state. Empirically, and provably in tabular linear settings (the classic "A–B example" in Sutton & Barto), TD methods often converge faster in terms of data efficiency, because bootstrapping lets information propagate through the whole Markov chain's structure rather than requiring long trajectories to be resampled repeatedly — this is TD's implicit exploitation of the Markov property, something MC targets ignore entirely.

Honest tradeoff summary.

Consider a tiny 4-state chain: $A \to B \to C \to \text{Terminal}$, undiscounted ($\gamma = 1$), with deterministic transitions but a stochastic reward at the $B\to C$ step: reward is $+2$ with probability 0.5 and $0$ with probability 0.5. All other rewards are $0$. Suppose $v_\pi(C) = 0$ is already known exactly (it's one step from termination with reward 0), and the true value $v_\pi(B) = 1$ (expectation of the stochastic reward), $v_\pi(A) = 1$. Suppose the current estimates, before any update this episode, are miscalibrated:

One episode is sampled: $A \to B$ (reward 0), $B \to C$ (reward $2$, the high-reward outcome), $C \to \text{Terminal}$ (reward 0).

Monte Carlo, using every-visit returns computed backward ($\gamma=1$):

Note the return $G_0 = 2$ used to update $A$ is a real sample of the true trajectory-sum — unbiased, but it's a "lucky" high-reward sample (the other possible outcome, reward 0, would have given $G_0=0$, a big swing). This is the variance in action: the MC target for $A$ can be $0$ or $2$ depending on a coin flip three steps away, even though $v_\pi(A)=1$ exactly in between.

TD(0), updating online as the episode unfolds ($\alpha = 0.1$):

The update to $V(A)$ used target $0.4$, which is biased — it doesn't reflect the reward that will actually arrive at $B\to C$, only $B$'s current (also wrong) estimate. But notice the update to $A$ moved only from $0.2 \to 0.22$: a small, low-variance nudge, because it depended only on $V(B)$ at the time, not on the downstream coin flip. Over many episodes, as $V(B)$ itself gets corrected toward $1$ by the second row's updates, $V(A)$'s bootstrapped targets automatically improve too — this is the "propagation" that makes TD data-efficient, while MC would keep swinging $V(A)$ between roughly $0$ and $2$ every episode until enough samples average out.

Bootstrapping is not a niche academic distinction — it governs the design of nearly every scalable RL system. Temporal-difference methods underlie Q-learning and SARSA, the workhorses of tabular control, and their function-approximation descendants such as Deep Q-Networks (DQN), which bootstrap Q-value targets using a separately maintained target network specifically to tame the bias-variance and stability tradeoffs discussed here. Actor-critic methods (A3C, PPO, SAC) use a bootstrapped critic to estimate value and reduce the variance of policy-gradient updates — the critic is, in essence, an industrial application of the TD idea to make policy learning tractable at scale. AlphaGo and AlphaZero blend Monte Carlo tree search rollouts (variance-heavy but unbiased local estimates) with a learned bootstrapped value network (low-variance but approximate), a direct architectural embodiment of the MC/TD tradeoff. In robotics and continuous-control research, n-step returns and TD(λ)-style eligibility traces are routinely tuned as a hyperparameter precisely because the "right" amount of bootstrapping depends on reward sparsity, episode length, and how trustworthy the current value estimates are — the exact tradeoff this article formalizes, and the exact motivation for n-Step Bootstrapping Methods and TD(lambda) and Eligibility Traces.

Ask the tutor: How does the eligibility-trace mechanism in TD(λ) let you compute a weighted blend of all n-step returns without storing every one of them explicitly?