This is the lesson where RL stops needing a model of the world. Monte Carlo learns by watching whole episodes. TD learning learns one step at a time by bootstrapping off its own predictions — a trick so powerful that Sutton's 1988 TD paper is one of the most-cited in all of AI. Every Q-learning, DQN, PPO, and AlphaGo target you'll ever see is some version of r + γV(s'). That formula starts here.
Learning Objectives
After this lesson, you will be able to:
Estimate value functions from episodes you have actually experienced — Monte Carlo's wait-till-the-end approach — and know when full-episode returns make sense
Bootstrap your value estimates with TD learning — update mid-episode using your own predictions of the future, the trick that makes online RL practical
Pick between MC, TD(0), n-step TD, and TD(λ) based on episode length, variance tolerance, and how soon you need to act on what you learned
Tell on-policy from off-policy methods, and use importance sampling to learn about one policy while following another
Build this --> Code Monte Carlo and TD(0) value estimation from scratch on a 5x5 GridWorld; plot how MC's variance is huge but unbiased while TD(0)'s bias decays smoothly; see why TD wins for online learning
Don't worry if "bootstrapping with your own estimate" sounds circular — once you see TD converge faster than MC on real episodes, the bias-variance trade clicks fast.
MC estimates V(s) by averaging the actual returns observed from s to the end of the episode. The return G_t is the discounted sum of rewards from time t until termination.
First-visit MC updates V(s) only the first time s appears in an episode. Every-visit MC updates every time. Both converge; first-visit is the standard.
MC's catch: it requires terminating episodes. You cannot apply pure MC to a continuing task (driving forever, perpetual trading). And the variance is high — a single lucky/unlucky tail of rewards swings the estimate.
Why TD won: it learns online. You don't wait for the episode to end. You can apply it to non-terminating tasks. The variance is much lower than MC because you only depend on one transition's noise. The bias starts large (V is wrong at initialization) but vanishes as V converges to V*.
So far TD(0) updates exactly one state per step — the state we just left — and MC updates the entire trajectory at episode end. There's a vast middle ground between these two extremes, and it's where most production RL actually lives. Eligibility traces are the mechanism that exposes the full spectrum as a single tunable knob.
The credit assignment problem. Suppose an agent visits states s_1 → s_2 → s_3 → s_4 → s_5 and receives a reward of +10 at s_5. TD(0) only updates V(s_4) based on this reward — V(s_3), V(s_2), and V(s_1) wait until later episodes for the reward signal to propagate one Bellman backup at a time. In a 100-state chain, that's roughly 100 episodes for the reward to reach the start. MC, in contrast, updates every state in the trajectory immediately: all five states get credit for the +10 proportional to discounting. The cost is MC's variance and its requirement that the episode terminate. n-step TD bridges the two: bootstrap after n steps instead of 1, propagating reward n states backward per update.
Gt(n)=Rt+1+γRt+2+⋯+γn−1Rt+n+γnV(st+n)
The λ-return (forward view). Picking a single n is unsatisfying — different transitions deserve different look-aheads. The λ-return is the exponentially weighted average of every n-step return, with weight λ^(n-1) for the n-step return:
Gtλ=(1−λ)n=1∑T−t−1λn−1Gt(n)+λT−t−1Gt(λ∈[0,1])
The forward view is conceptually clean but computationally awkward: you'd have to wait for the episode to end before computing G_t^λ for any state, because each G_t^{(n)} needs n more rewards. The backward view fixes this by maintaining a running memory.
The backward view: eligibility traces. Maintain a scalar e_t(s) for every state — the eligibility trace — that decays by γλ each step and accumulates a +1 whenever the state is visited. After each step, broadcast the TD error to every state, scaled by its current trace:
Forward-view = backward-view (in expectation). Sutton & Barto (Reinforcement Learning: An Introduction, Theorem 12.4) prove that the offline λ-return updates (forward view) and the online eligibility-trace updates (backward view) produce the same total update to V over an episode, in expectation, when the step size α is small enough to ignore second-order effects. The equivalence isn't superficial — it's a deep identity between two different ways of writing the same algorithm. Modern implementations use the backward view because it's online; the forward view is mostly a pedagogical tool to understand what TD(λ) is computing.
Three trace update rules. The variant above uses accumulating traces: e_t(s) = γλ · e_{t-1}(s) + 1 when s_t = s. There are two alternatives in common use:
Replacing traces: when s_t = s, replace the trace with 1 instead of adding. e_t(s) = 1 if s_t = s, else γλ · e_{t-1}(s). This caps the trace at 1 and prevents revisits from compounding — useful when states are visited many times in an episode.
True online TD(λ) (van Seijen et al., 2014): a corrected backward-view update that exactly matches the offline forward-view λ-return on every step, not just at episode end and not just in expectation. The math is messier — there's an extra "dutch trace" correction term — but the resulting algorithm has the best convergence guarantees of any TD(λ) variant under linear function approximation, and is recommended for any application that mixes TD(λ) with neural networks where bias matters.
Why TD(λ) often wins. In practice TD(λ) with λ ≈ 0.9 to 0.95 consistently outperforms both TD(0) and MC on tabular and function-approximation problems alike. Three reasons stack:
Smoother credit assignment. Distant states get a graded share of credit instead of all-or-nothing.
Bias-variance sweet spot. TD(0) is too biased early; MC is too noisy. λ ≈ 0.9 finds the middle.
Works under function approximation. Standard TD(0) with neural networks (deadly triad) can diverge; TD(λ) acts as implicit regularization on the bootstrap, and true online TD(λ) provably converges under linear FA — one of the only TD-style algorithms with that guarantee.
This is why GAE (Generalized Advantage Estimation), used in PPO and every modern actor-critic, is mathematically just TD(λ) applied to the advantage instead of the value. λ_GAE = 0.95 is the canonical default and traces directly back to Sutton's TD(λ) — Schulman et al. (2016) explicitly call it "λ-return for advantages."
On-policy methods learn the value of the policy you are currently following. Examples: MC, TD(0), SARSA. If you switch policies, your value estimates become wrong.
Off-policy methods learn about a target policy π while following a different behavior policy b. Q-learning is the classic example — it learns the optimal Q*, regardless of how the agent actually explored. The math: use importance sampling to correct for the policy mismatch.
You're training an RL agent in a game with episodes lasting on average 200 steps. You have stochastic rewards along the way. Which method gives lower-variance value estimates?
The answer is TD(0). MC's variance grows with episode length because every step's reward noise enters the return. TD(0) only depends on one transition's noise plus the variance in your own V estimate, which shrinks as V converges.
MC waits till episode end and averages actual returns. Unbiased, high variance, requires episodic tasks; great when episodes are short and reward noise is small
TD bootstraps off its own value estimate after one step. Biased early, low variance, works for both episodic and continuing tasks; the foundation of every modern deep RL algorithm
n-step TD and TD(λ) interpolate between MC and TD. Bias-variance dial, usually λ ≈ 0.9–0.95 in practice; eligibility traces let you compute this online efficiently
On-policy methods (MC, SARSA) learn V/Q for the policy you're following. Off-policy methods (Q-learning) learn V/Q* for a different target policy via importance sampling or one-step bootstrapping
TD targets are the ancestor of every modern deep RL algorithm. DQN, PPO (via GAE), IMPALA (via V-trace), MuZero — all variations on Sutton's 1988 update with neural function approximation and stability tricks layered on top
Interactive Lab
Run MC and TD(0) side by side on the same gridworld and watch MC's variance spike on unlucky episodes while TD's biased-but-stable estimate slides toward the true value — the visual that makes the bias-variance trade-off click instantly.
Why is TD(0) lower variance than Monte Carlo for value estimation?
You now have the engine that powers every modern deep-RL algorithm. Next: SARSA and Q-Learning — the leap from "estimate values of a fixed policy" to "find the optimal policy by acting".