Temporal-Difference Learning

If one idea had to be singled out as central and novel to reinforcement learning, it would be temporal-difference (TD) learning. It is a blend of the two families of solution methods we have already seen.¹ Like Monte Carlo methods, TD learns directly from raw experience with no model of the environment's dynamics — no need for the transition probabilities $p(s^{\prime },r\mid s,a)$. Like dynamic programming, TD updates its estimates in part from other learned estimates, without waiting for a final outcome. It bootstraps: it updates a guess from a later guess rather than from an actual return. The rest of this lesson works out the consequences of that one change.

As usual we begin with the prediction problem: estimating the value function $v_{\pi }$ for a fixed policy $\pi$. Control (finding a good policy) comes after, and follows the same generalized-policy-iteration pattern as everything else; the methods differ chiefly in how they solve prediction.

From Monte Carlo to TD

Both TD and Monte Carlo use experience to solve prediction. Following $\pi$, each generates a stream of states, actions, and rewards, and each updates its estimate $V$ of $v_{\pi }$ at the nonterminal states it meets. The difference is when, and toward what, they update.

A Monte Carlo method waits until the return following a visit is known, then uses that return as the target. A simple every-visit constant-$\alpha$ MC update is

where $G_t$ is the actual return following time $t$ and $\alpha$ is a constant step size. Call this method constant-$\alpha$ MC. Its target $G_t$ is not known until the episode terminates, so MC must wait for the end of the episode before it can change $V(S_t)$.

TD does not wait. At time $t+1$ it immediately forms a target from the one reward it just observed, $R_{t+1}$, and its existing estimate of the next state, $V(S_{t+1})$. The simplest TD method makes the update

on the transition to $S_{t+1}$ and receiving $R_{t+1}$. Where MC's target is the full return $G_t$, TD's target is $R_{t+1}+\gamma V(S_{t+1})$ — one real reward plus the discounted estimate of the rest. This method is called TD(0), or one-step TD, because it is the base case of the $n$-step and TD($\lambda$) methods that look further ahead.²

The whole method is one line inside two loops. No return has to be stored, no episode has to finish; the estimate at $S$ moves the instant the next state and reward arrive.

Why bootstrapping is legitimate

It is not obvious that updating a guess from another guess can converge to the true value function. The justification runs through the same recursive identity that produced the Bellman equation. Write the value three ways:

Each line is a target, and each method aims at a different one. Monte Carlo aims at the first line: because the expected return is unknown, it uses a sample return in its place. Dynamic programming aims at the third line: it can take the expectation exactly because it is handed a complete model, but it must substitute the current estimate $V(S_{t+1})$ for the true $v_{\pi }(S_{t+1})$, which is unknown. TD aims at that same third line and makes both substitutions at once — it samples the expectation (using the single observed $R_{t+1}$ and $S_{t+1}$ rather than averaging over all successors) and it bootstraps (using $V(S_{t+1})$ rather than $v_{\pi }(S_{t+1})$). Making both substitutions at once is what lets TD combine the sampling of Monte Carlo with the bootstrapping of DP.²

The backup diagrams show the contrast directly. We call TD and MC updates sample updates: they look ahead to a sample successor, use its value and the reward along the way to compute a backed-up value, and then adjust the value of the original state toward it. Sample updates differ from the expected updates of DP in resting on a single sample successor rather than the complete distribution of all possible successors. TD's diagram is the shortest of the three — a single link from a state to its one sampled successor — because TD backs up from the next state only.

The TD error

The bracketed quantity in the TD(0) update is a kind of error. It measures the difference between the estimated value of $S_t$ and the better estimate $R_{t+1}+\gamma V(S_{t+1})$. This is the TD error, and it recurs throughout reinforcement learning:

$V(S_t)$ is the prediction made at time $t$; $R_{t+1}+\gamma V(S_{t+1})$ is a corrected prediction after one observed step. Their difference ${\delta }_t$ is the one-step prediction error, and TD(0) moves $V(S_t)$ by $\alpha {\delta }_t$ to reduce it.

Notice a subtlety in the timing. The TD error at each step is the error in the estimate made at that time. Because ${\delta }_t$ depends on the next state $S_{t+1}$ and the next reward $R_{t+1}$, it is not available until one step later: ${\delta }_t$ is the error in $V(S_t)$ but can only be computed at time $t+1$. This one-step delay is unavoidable when learning without a model.

If $V$ does not change during an episode — as it does in Monte Carlo, but not quite in TD(0) — the Monte Carlo error decomposes exactly into a sum of TD errors:

The full-episode error is the discounted sum of the one-step errors. The identity is only approximate in TD(0) itself, since $V$ shifts as the episode runs, but it holds tightly for small $\alpha$ and underlies the eligibility traces introduced later.²

Driving home: TD versus MC intuition

For example: each day you drive home from work and try to predict how long it will take. Leaving the office on a Friday at 6:00 you estimate 30 minutes. Reaching the car at 6:05 it has begun to rain, so you revise the total to 40. Off the highway at 6:20 you cut the total to 35; then you get stuck behind a slow truck and revise up to 43; you turn onto your street at 6:40 and reach home at 6:43. The sequence of states carries a running predicted total travel time — 30, 40, 35, 43, 43 — and the reward on each leg is the elapsed time, with $\gamma =1$ so the return from any state is the actual remaining time to go.³

A Monte Carlo method plots those predictions and, at the end of the trip, when the true 43-minute total is finally known, corrects every earlier prediction toward it. When you left the highway you thought 15 minutes remained; it took 23; so MC pushes that prediction up — but only after you are already home. TD instead shifts each estimate toward the estimate that immediately follows it. The moment you revise from 35 to 43 behind the truck, TD updates the exiting-highway prediction toward 43, on the spot, without waiting to see the actual outcome. Each error is proportional to the change in prediction over time — the temporal difference in predictions — which is where the method gets its name.

The example also shows a practical advantage of TD. Suppose you move to a new office but still merge onto the same highway. After one bad day in traffic you already know your initial estimate was too low. Monte Carlo cannot raise it until you get home, because the true return is not yet known. TD shifts the estimate the moment the next, better-informed estimate arrives. Learning during the episode, not only at its end, is what makes TD suited to long episodes, to continuing tasks with no episodes at all, and to situations where waiting to the end is simply too slow.⁴

Advantages of TD prediction

TD methods bootstrap: they learn a guess from a guess. Three advantages recommend them.⁴

• No model. Unlike DP, TD needs no model of the environment: no reward distribution, no next-state probabilities. It learns straight from experience.
• Online and incremental. Unlike MC, TD updates after every step, needing no final return. Some episodes are very long, so waiting until the end makes all learning slow; some tasks are continuing and have no episode boundary; and some MC variants must discard episodes on which experimental actions are taken. TD is far less exposed to any of these, because it learns from each transition regardless of what follows.
• Sound. For any fixed policy $\pi$, TD(0) has been proved to converge to $v_{\pi }$: in the mean for a small enough constant step size, and with probability 1 if $\alpha$ decreases according to the usual stochastic- approximation conditions.

Which learns faster, TD or constant-$\alpha$ MC? No one has proved either uniformly faster, and it is not even settled what the right formal question is. In practice, though, TD methods have usually been found to converge faster than constant-$\alpha$ MC on stochastic tasks. Consider the random-walk example.

Run TD(0) on this chain from an initial guess of $V(s)=0.5$ everywhere and the estimates march toward the true values $\frac{1}{6},\frac{2}{6},\frac{3}{6},\frac{4}{6},\frac{5}{6}$; averaged over many runs, the root-mean-square error falls faster and settles lower than constant-$\alpha$ MC across a range of step sizes. Sampling and bootstrapping beats sampling alone here.

One episode, two update rules

Consider a single episode updating $V$ under each method, with real numbers. Take the random walk, $\alpha =0.1$, $\gamma =1$, and the standard start $V(s)=0.5$ for all five states $A,B,C,D,E$. Suppose the episode runs $C\to D\to E\to \text{(right terminal)}$, so it visits $C$, $D$, $E$ and terminates on the right with reward $1$; every earlier reward is $0$.

Constant-$\alpha$ MC waits for the return. The episode's return from every visited state is $G=1$ (undiscounted, the only reward was the terminal $1$). So each visited state moves toward $1$:

All three visited states rise by the same $0.05$, because MC hands each the same target $G=1$ regardless of position in the episode.

TD(0) updates on each transition, using the next state's current estimate as the target. Process the transitions in order. On $C\to D$ the reward is $0$ and $V(D)=0.5$, so the target is $0+0.5=0.5$, equal to $V(C)$; the TD error is zero and $V(C)$ does not move. Same for $D\to E$: target $0+V(E)=0.5$, no change to $V(D)$. Only the last transition carries information: $E\to$ terminal pays reward $1$, and the terminal value is $0$, so the target is $1+0=1$ and

After one episode MC has raised all three visited estimates; TD has raised only $V(E)$. TD credits a state only when the step out of it was informative, and it propagates that credit backward on later episodes: once $V(E)$ is above $0.5$, a future visit to $D$ that steps to $E$ will find a target above $0.5$ and raise $V(D)$ in turn. TD diffuses value backward one link per episode; MC injects the outcome everywhere at once but with the full variance of a single sampled return.

Optimality of TD(0): batch updating

TD's advantage is clearest when data is scarce. Suppose only a finite batch of experience is available — say ten episodes. A natural tactic is to present the batch repeatedly until the estimate converges: compute the increments (6.1) or (6.2) for every step at every visited state, but change $V$ only once, by the sum of all the increments, then reprocess the whole batch, and repeat. This is batch updating, because updates are made only after processing each complete batch of training data.

Under batch updating, TD(0) converges deterministically to a single answer, independent of the step size $\alpha$ as long as $\alpha$ is small. Constant- $\alpha$ MC also converges deterministically under the same conditions, but to a different answer — and comparing the two answers is what reveals the difference between the methods.

Consider a tiny example. You observe eight episodes of an unknown Markov reward process:

The first episode went from $\mathsf{A}$ to $\mathsf{B}$ with reward $0$, then terminated from $\mathsf{B}$ with reward $0$; six other episodes went directly from $\mathsf{B}$ and terminated with reward $1$; one terminated from $\mathsf{B}$ with reward $0$. Clearly $V(\mathsf{B})=\frac{3}{4}$: six of eight visits to $\mathsf{B}$ ended in $1$. But what is $V(\mathsf{A})$? There are two defensible answers, one per method: MC uses only the one return observed from $\mathsf{A}$, while TD infers that $\mathsf{A}$ always leads to $\mathsf{B}$, so $\mathsf{A}$ should inherit $\mathsf{B}$'s value.

Batch Monte Carlo gives $V(\mathsf{A})=0$: $\mathsf{A}$ was visited once, and the return that followed was $0$. This answer gives zero squared error on the training set — it is optimal in that limited sense. Batch TD(0) gives $V(\mathsf{A})=\frac{3}{4}$, by a different route. It first builds the maximum-likelihood model of the Markov process: the estimated transition probability from $i$ to $j$ is the fraction of observed transitions from $i$ that went to $j$, and each reward is the average observed on that transition. Here $\mathsf{A}$ went to $\mathsf{B}$ every time, and $\mathsf{B}$ is worth $\frac{3}{4}$, so $\mathsf{A}$ must be worth $\frac{3}{4}$ too. The value function that would be exactly correct if this model were the true model is the certainty-equivalence estimate — it acts as if the estimated process were certainly correct.

This is why we expect $\frac{3}{4}$ to predict future data better even though $0$ fits the past data perfectly. If the process is Markov, the certainty-equivalence estimate captures its structure, and structure generalizes. It also explains why TD tends to converge faster: nonbatch TD(0) does not reach the certainty-equivalence estimate, but it moves roughly toward it, whereas MC moves toward the minimum-training-error solution. TD approximates the certainty-equivalence answer with memory only $O(n)$ in the number of states, where forming the model outright would take $O(n^2)$ memory and $O(n^3)$ computation — so on large problems TD may be the only feasible way to approach it.⁵

This continues in TD Control: Sarsa, Q-learning, and Double Learning, which turns TD prediction into control — Sarsa on-policy, Q-learning off-policy, Expected Sarsa spanning the two — and fixes the maximization bias with Double Q-learning.