Chapter 4: Monte Carlo & Temporal-Difference Learning

Convergence proofs need every state-action pair to be visited infinitely often. Exploring starts guarantee this by beginning episodes from a random state-action pair, but that is impossible in most real environments where you cannot place the agent arbitrarily. The practical alternative is an $\varepsilon$-greedy policy, which takes the greedy action with probability $1-\varepsilon$ and a uniformly random one otherwise, so every action retains positive probability forever. The weakness is that exploratory moves are uniform: a clearly terrible action is sampled exactly as often as a promising untried one.

Classic policy iteration evaluates each policy to convergence before improving, which here would require infinitely many episodes per improvement. Monte Carlo control instead improves the policy after every episode, using whatever estimates are available. This is generalized policy iteration with a tiny evaluation budget, the same truncation idea that produced value iteration in Chapter 3. One caution: for the exploring-starts version, convergence to the optimum is still only partly proved. Sutton posed it as an open problem, and Tsitsiklis settled it only for the case where every state-action pair starts episodes equally often; arbitrary start choices can break it. It works reliably in practice nonetheless.

The quantity $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ is the TD error: the difference between the estimate before and after seeing one more step of reality. It is the single most important scalar in reinforcement learning, and it reappears in three distinct roles across the remaining chapters. It drives the update in TD(0), it serves as the advantage estimate in the actor-critic methods of Chapter 8, and its magnitude is the sampling priority in prioritized experience replay. Recognizing it in each disguise makes those later algorithms considerably less mysterious.

TD updates after every step, so it learns from incomplete episodes and works in continuing tasks that never terminate. Its targets have far lower variance than full returns because they depend on one random reward and transition rather than hundreds. Empirically it converges faster than Monte Carlo on most Markov problems, and it exploits structure Monte Carlo ignores by reusing value estimates across states — information learned about one state immediately improves the targets for all of its predecessors, which is a form of generalization that Monte Carlo simply does not have access to.

Dynamic programming takes a full expectation over every next state, which requires a model, and bootstraps after a single step, so its backups are wide but shallow. Monte Carlo samples one trajectory and does not bootstrap, so its backups are narrow but run to the end of the episode. TD samples and bootstraps, narrow and shallow, which is why it needs neither a model nor complete episodes. The remaining corner, full expectation without bootstrapping, is exhaustive search over whole trajectories, wide and deep, and generally intractable. Laid out this way, the methods are not competing philosophies but corners of one design space.

The Monte Carlo target is unbiased with variance proportional to episode length. The TD target is biased by the current value error but has variance from only one transition. Early in training the bias dominates because the estimates are poor; later it vanishes as values become accurate, while Monte Carlo's variance never shrinks at all. That asymmetry is the practical argument for bootstrapping: its cost is temporary and self-correcting, whereas the variance cost of full returns is permanent and set by the problem rather than by the state of learning.

The n-step return accumulates $n$ discounted rewards and then adds the discounted value estimate of the state reached. Intermediate values of $n$ typically outperform both extremes, with the best setting depending on how sparse the rewards are and how accurate the value function currently is. The costs are real but modest: updates must be delayed by $n$ steps, since the return is not complete until then, and $n$ becomes another hyperparameter to tune. In practice the method is fairly forgiving, with performance varying smoothly rather than sharply across nearby values.

Rather than committing to one $n$, the lambda return averages all n-step returns with weights $(1-\lambda)\lambda^{n-1}$, which sum to one. Computing it directly means waiting for the episode to end. The backward view with eligibility traces approximates it online: each state keeps a trace that jumps when the state is visited and decays by $\gamma\lambda$ every step, and every TD error updates all states in proportion to their traces. The two views match exactly when updates are applied offline at the end of the episode; true online TD($\lambda$) makes them match online too. In practice $\lambda$, like $n$, still needs tuning.