---
title: Temporal-Difference Learning
module: Tabular Solution Methods
moduleNumber: 2
lessonNumber: 5
order: 205
summary: >
  Temporal-difference learning is the one idea most central to reinforcement
  learning: learn a value directly from experience, like Monte Carlo, but update
  each guess toward the next guess before the episode ends, like dynamic
  programming. We derive the TD(0) prediction rule and its reward-prediction
  error, contrast its one-step backup with MC and DP, work the driving-home and
  random-walk examples, and show the batch-updating optimality that makes TD
  approximate the certainty-equivalence estimate.
topics: [Tabular Methods]
sources:
  - book: Sutton & Barto
    ref: "Ch. 6 — Temporal-Difference Learning; §6.1 TD Prediction; §6.2 Advantages of TD Prediction Methods"
  - book: Sutton & Barto
    ref: "§6.3 Optimality of TD(0)"
---

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.[^sb-intro] Like
[Monte Carlo methods](/reinforcement-learning/tabular-methods/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',r \mid s,a)$. Like
[dynamic programming](/reinforcement-learning/tabular-methods/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](/reinforcement-learning/foundations/value-functions-and-optimality):
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

$$
V(S_t) \;\leftarrow\; V(S_t) + \alpha\big[\,G_t - V(S_t)\,\big],
$$

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

$$
V(S_t) \;\leftarrow\; V(S_t) + \alpha\big[\,R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\,\big]
$$

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.[^sb-td0]

$$
% caption: Constant-$\alpha$ MC waits for the whole episode, then corrects
% $V(S_t)$ toward the actual return $G_t$; TD(0) corrects after a single step,
% toward $R_{t+1} + \gamma V(S_{t+1})$ — one real reward plus the estimate of the
% rest. The target is the only thing that changes.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % shared trajectory of states
  \foreach \i/\x in {t/0, 1/1.9, 2/3.8, 3/5.7} {
    \node[st] (s\i) at (\x,0) {};
  }
  \node[st, fill=black!8] (sT) at (7.6,0) {};
  \node[anchor=north, font=\scriptsize] at (0,-0.45) {S(t)};
  \node[anchor=north, font=\scriptsize] at (1.9,-0.45) {S(t+1)};
  \node[anchor=north, font=\scriptsize] at (3.8,-0.45) {S(t+2)};
  \node[anchor=north, font=\scriptsize] at (5.7,-0.45) {...};
  \node[anchor=north, font=\scriptsize] at (7.6,-0.45) {terminal};
  \foreach \a/\b/\r in {st/s1/R(t+1), s1/s2/R(t+2), s2/s3/{}, s3/sT/{}} {
    \draw[->, black] (\a) -- (\b) node[midway, above, font=\scriptsize] {\r};
  }
  % TD(0) target: one step
  \draw[acc, thick, ->] (st) to[bend left=42] (s1);
  \node[acc, anchor=south, font=\scriptsize] at (0.95,0.95) {TD: back up 1 step};
  % MC target: whole episode
  \draw[red, thick, ->] (st) to[bend right=32] (sT);
  \node[red, anchor=north, font=\scriptsize] at (3.8,-1.55) {MC: back up whole return G(t)};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Tabular-TD}(0)$ — estimate $V \approx v_\pi$ for a given policy $\pi$
input: policy $\pi$, step size $\alpha \in (0,1]$
$V(s) \gets$ arbitrary, with $V(\text{terminal}) = 0$, for all $s \in \mathcal{S}$
for each episode do
  initialize $S$
  repeat
    $A \gets$ action given by $\pi$ for $S$
    take action $A$, observe $R$, $S'$
    $V(S) \gets V(S) + \alpha[R + \gamma V(S') - V(S)]$
    $S \gets S'$
  until $S$ is terminal
```

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](/reinforcement-learning/foundations/value-functions-and-optimality).
Write the value three ways:

$$
\begin{aligned}
v_\pi(s)
&\doteq \mathbb{E}_\pi[\,G_t \mid S_t = s\,] \\
&= \mathbb{E}_\pi[\,R_{t+1} + \gamma G_{t+1} \mid S_t = s\,] \\
&= \mathbb{E}_\pi[\,R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s\,].
\end{aligned}
$$

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.[^sb-td0]

$$
% caption: Backup diagrams. DP (left) backs up from all successors using a model
% but bootstraps from estimates; MC (right) samples one full trajectory to the
% terminal state but does not bootstrap; TD(0) (center) does both — it samples a
% single successor and backs up from its estimate.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=5mm, inner sep=0pt},
  ac/.style={circle, draw, fill=black, minimum size=2.2mm, inner sep=0pt},
  lf/.style={circle, draw, fill=white, minimum size=4mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % ===== DP =====
  \begin{scope}
    \node[st, label={[text=acc]above:s}] (s) at (0,3) {};
    \node[ac] (a) at (0,2.1) {};
    \draw[acc, thick] (s) -- (a);
    \node[lf] (l1) at (-1,1.1) {};
    \node[lf] (l2) at (0,1.1) {};
    \node[lf] (l3) at (1,1.1) {};
    \draw[black] (a) -- (l1); \draw[black] (a) -- (l2); \draw[black] (a) -- (l3);
    \node[anchor=north, font=\footnotesize] at (0,0.65) {DP};
    \node[anchor=north, font=\scriptsize, text=black] at (0,0.2) {all successors};
  \end{scope}
  % ===== TD(0) =====
  \begin{scope}[xshift=4.6cm]
    \node[st, label={[text=acc]above:s}] (s) at (0,3) {};
    \node[ac] (a) at (0,2.1) {};
    \draw[acc, thick] (s) -- (a);
    \node[lf] (l) at (0,1.1) {};
    \draw[acc, thick] (a) -- (l);
    \node[anchor=north, font=\footnotesize] at (0,0.65) {TD(0)};
    \node[anchor=north, font=\scriptsize, text=black] at (0,0.2) {one successor};
  \end{scope}
  % ===== MC =====
  \begin{scope}[xshift=9.2cm]
    \node[st, label={[text=acc]above:s}] (s) at (0,3) {};
    \node[ac] (a1) at (0,2.35) {};
    \node[st] (m1) at (0,1.75) {};
    \node[ac] (a2) at (0,1.15) {};
    \node[st, fill=black!8] (term) at (0,0.55) {};
    \draw[acc, thick] (s) -- (a1); \draw[acc, thick] (a1) -- (m1);
    \draw[acc, thick] (m1) -- (a2); \draw[acc, thick] (a2) -- (term);
    \node[anchor=north, font=\footnotesize] at (0,0.15) {MC};
    \node[anchor=west, font=\scriptsize, text=black] at (0.35,1.45) {to terminal};
  \end{scope}
\end{tikzpicture}
$$

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:

$$
\delta_t \;\doteq\; R_{t+1} + \gamma V(S_{t+1}) - V(S_t).
$$

$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:

$$
G_t - V(S_t) \;=\; \sum_{k=t}^{T-1} \gamma^{k-t}\, \delta_k.
$$

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.[^sb-td0]

$$
% caption: The TD error $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ is the
% gap between the old estimate at $S_t$ and the one-step-corrected target; TD(0)
% moves $V(S_t)$ a fraction $\alpha$ of the way to close it.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % vertical value axis feel
  \draw[black, ->] (0,-0.3) -- (0,3.4) node[anchor=east, font=\scriptsize] {value};
  % old estimate level
  \draw[black, dashed] (0.2,0.9) -- (6.2,0.9);
  \node[anchor=west, font=\scriptsize] at (6.25,0.9) {old V(S(t))};
  \fill[acc] (1.2,0.9) circle (2.6pt);
  % target level
  \draw[black, dashed] (0.2,2.6) -- (6.2,2.6);
  \node[anchor=west, font=\scriptsize] at (6.25,2.6) {target = R + gamma times V(next)};
  \fill[red] (1.2,2.6) circle (2.6pt);
  % the delta gap
  \draw[red, thick, <->] (1.2,0.98) -- (1.2,2.52);
  \node[red, anchor=west, font=\footnotesize] at (1.35,1.75) {TD error};
  % the alpha step
  \draw[acc, very thick, ->] (3.6,0.9) -- (3.6,1.58);
  \node[acc, anchor=west, font=\scriptsize] at (3.75,1.25) {step alpha times error};
  \fill[acc] (3.6,1.58) circle (2.6pt);
  \node[anchor=north, font=\scriptsize] at (1.2,0.78) {before};
  \node[anchor=north, font=\scriptsize] at (3.6,0.78) {after};
\end{tikzpicture}
$$

## 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.[^sb-drive]

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.

$$
% caption: Driving home. Monte Carlo (left) waits for the actual 43-minute
% outcome and corrects every prediction toward it (red arrows all point to the
% final level); TD (right) corrects each prediction toward the very next
% prediction, as soon as it is made.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % ===== LEFT: MC =====
  \begin{scope}
    \draw[black, ->] (-0.2,0) -- (0,0) -- (0,3.4) node[anchor=east, font=\scriptsize] {pred. time};
    \draw[black, ->] (0,0) -- (5.2,0);
    % actual-outcome level
    \draw[black, dashed] (0,2.9) -- (5.0,2.9);
    \node[anchor=west, font=\scriptsize] at (0.15,3.15) {actual outcome};
    % predictions: 30 40 35 43 43 (scaled)
    \coordinate (p0) at (0.6,0.6);
    \coordinate (p1) at (1.6,2.0);
    \coordinate (p2) at (2.6,1.3);
    \coordinate (p3) at (3.6,2.9);
    \coordinate (p4) at (4.6,2.9);
    \draw[black, thick] (p0)--(p1)--(p2)--(p3)--(p4);
    \foreach \p in {(p0),(p1),(p2),(p3),(p4)} \fill[black] \p circle (2pt);
    % MC arrows all to actual level
    \draw[red, thick, ->] (0.6,0.7) -- (0.6,2.8);
    \draw[red, thick, ->] (1.6,2.1) -- (1.6,2.8);
    \draw[red, thick, ->] (2.6,1.4) -- (2.6,2.8);
    \node[anchor=north, font=\scriptsize] at (2.5,-0.15) {MC};
  \end{scope}
  % ===== RIGHT: TD =====
  \begin{scope}[xshift=6.6cm]
    \draw[black, ->] (-0.2,0) -- (0,0) -- (0,3.4) node[anchor=east, font=\scriptsize] {pred. time};
    \draw[black, ->] (0,0) -- (5.2,0);
    \draw[black, dashed] (0,2.9) -- (5.0,2.9);
    \node[anchor=west, font=\scriptsize] at (0.15,3.15) {actual outcome};
    \coordinate (q0) at (0.6,0.6);
    \coordinate (q1) at (1.6,2.0);
    \coordinate (q2) at (2.6,1.3);
    \coordinate (q3) at (3.6,2.9);
    \coordinate (q4) at (4.6,2.9);
    \draw[black, thick] (q0)--(q1)--(q2)--(q3)--(q4);
    \foreach \p in {(q0),(q1),(q2),(q3),(q4)} \fill[black] \p circle (2pt);
    % TD arrows: each toward the next prediction's level
    \draw[red, thick, ->] (0.6,0.7) -- (0.6,1.9);
    \draw[red, thick, ->] (1.6,1.9) -- (1.6,1.4);
    \draw[red, thick, ->] (2.6,1.4) -- (2.6,2.8);
    \node[anchor=north, font=\scriptsize] at (2.5,-0.15) {TD};
  \end{scope}
\end{tikzpicture}
$$

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.[^sb-adv]

## Advantages of TD prediction

TD methods bootstrap: they learn a guess from a guess. Three advantages
recommend them.[^sb-adv]

- **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.

$$
% caption: The random-walk Markov reward process. Episodes start in the center
% state C and step left or right with equal probability; termination on the far
% right pays reward 1, all other rewards are 0. The true value of each state is
% its probability of ending on the right — 1/6, 2/6, 3/6, 4/6, 5/6 for A..E.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=8mm, inner sep=0pt},
  tm/.style={draw, fill=black!8, minimum size=6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[tm] (TL) at (-1.6,0) {};
  \node[st] (A) at (0,0) {A};
  \node[st] (B) at (1.6,0) {B};
  \node[st, draw=acc, text=acc, thick] (C) at (3.2,0) {C};
  \node[st] (D) at (4.8,0) {D};
  \node[st] (E) at (6.4,0) {E};
  \node[tm] (TR) at (8.0,0) {};
  \foreach \a/\b in {A/TL, B/A, C/B, D/C, E/D} {
    \draw[<-, black] (\a) -- (\b) node[midway, above, font=\scriptsize] {0};
  }
  \foreach \a/\b/\r in {A/B/0, B/C/0, C/D/0, D/E/0} {
    \draw[->, black] (\a) -- (\b) node[midway, below, font=\scriptsize] {\r};
  }
  \draw[->, red, thick] (E) -- (TR) node[midway, above, font=\scriptsize, text=red] {1};
  \node[acc, anchor=north, font=\scriptsize] at (3.2,-0.7) {start};
\end{tikzpicture}
$$

Run TD(0) on this chain from an initial guess of $V(s) = 0.5$ everywhere and the
estimates march toward the true values $\tfrac16, \tfrac26, \tfrac36, \tfrac46,
\tfrac56$; 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$:

$$
\begin{aligned}
V(C) &\gets 0.5 + 0.1\,(1 - 0.5) = 0.55, \\
V(D) &\gets 0.5 + 0.1\,(1 - 0.5) = 0.55, \\
V(E) &\gets 0.5 + 0.1\,(1 - 0.5) = 0.55.
\end{aligned}
$$

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

$$
V(E) \gets 0.5 + 0.1\,(1 + 0 - 0.5) = 0.55.
$$

$$
% caption: One random-walk episode C-D-E-right-terminal, alpha = 0.1. Monte Carlo
% (top) moves all three visited states up by 0.05 toward the shared return G = 1.
% TD(0) (bottom) moves only V(E), because C and D see a zero reward and an
% unchanged next-state estimate, so their TD errors are zero on this episode.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % ---- MC row ----
  \node[anchor=east, font=\scriptsize] at (-0.3,2.3) {MC};
  \foreach \s/\x in {C/0.3, D/2.3, E/4.3} {
    \node[font=\scriptsize] at (\x,2.75) {\s};
    \node[red, font=\scriptsize] at (\x,2.3) {0.50};
    \draw[red, thick, ->] (\x+0.35,2.3) -- (\x+0.75,2.3);
    \node[red, font=\scriptsize] at (\x+1.1,2.3) {0.55};
  }
  \node[anchor=west, font=\scriptsize, text=black] at (5.7,2.3) {all visited states move (G=1)};
  % ---- TD row ----
  \node[anchor=east, font=\scriptsize] at (-0.3,0.7) {TD(0)};
  \foreach \s/\x in {C/0.3, D/2.3, E/4.3} {
    \node[font=\scriptsize] at (\x,1.15) {\s};
  }
  \node[font=\scriptsize] at (0.65,0.7) {0.50};
  \node[font=\scriptsize] at (2.65,0.7) {0.50};
  \node[acc, font=\scriptsize] at (4.3,0.7) {0.50};
  \draw[acc, thick, ->] (4.65,0.7) -- (5.05,0.7);
  \node[acc, font=\scriptsize] at (5.4,0.7) {0.55};
  \node[anchor=west, font=\scriptsize, text=black] at (5.9,0.7) {only V(E) moves};
\end{tikzpicture}
$$

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:

$$
\mathsf{A},0,\mathsf{B},0 \qquad \mathsf{B},1 \;(\times 6) \qquad \mathsf{B},0.
$$

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}) = \tfrac34$: 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.

$$
% caption: The two answers for $V(\mathsf{A})$. Batch Monte Carlo estimates 0 —
% the one observed return from A was 0, which minimizes error on the training set.
% Batch TD(0) estimates 3/4 by first building the maximum-likelihood Markov model
% (A always goes to B, and $V(\mathsf{B})=3/4$) — the certainty-equivalence answer.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=7mm, inner sep=0pt},
  tm/.style={draw, fill=black!8, minimum size=6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st] (A) at (0,0) {A};
  \node[st] (B) at (2.4,0) {B};
  \node[tm] (T1) at (5.0,0.9) {};
  \node[tm] (T2) at (5.0,-0.9) {};
  \draw[->, acc, thick] (A) -- (B) node[midway, above, font=\scriptsize] {r=0, 100 pct};
  \draw[->, black] (B) -- (T1);
  \draw[->, black] (B) -- (T2);
  \node[anchor=south, font=\scriptsize, text=black] at (3.9,0.7) {r=1, 75 pct};
  \node[anchor=north, font=\scriptsize, text=black] at (3.9,-0.7) {r=0, 25 pct};
  % answers
  \node[red, anchor=west, font=\footnotesize] at (0.0,-1.6) {MC: V(A) = 0};
  \node[acc, anchor=west, font=\footnotesize] at (2.9,-1.6) {TD: V(A) = 3/4};
\end{tikzpicture}
$$

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}) = \tfrac34$, 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
$\tfrac34$, so $\mathsf{A}$ must be worth $\tfrac34$ 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.

> **Definition (Certainty-equivalence estimate).** The value function computed
> as though the maximum-likelihood model of the Markov process were the true one.
> Batch TD(0) converges to this estimate; batch MC converges instead to the
> values that minimize mean-squared error on the observed returns.

This is why we expect $\tfrac34$ 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.[^sb-opt]

This continues in [TD Control: Sarsa, Q-learning, and Double Learning](/reinforcement-learning/tabular-methods/td-control-sarsa-and-q-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.

[^sb-intro]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), Ch. 6 — introduction: TD learning as the combination of Monte Carlo ideas (learn from raw experience, no model) and dynamic-programming ideas (bootstrap from an existing estimate without waiting for a final outcome).
[^sb-td0]: **Sutton & Barto**, §6.1 — TD Prediction: the constant-$\alpha$ MC update (6.1), the TD(0) update (6.2), the recursive identity (6.3)–(6.4) that TD samples and bootstraps at once, the tabular TD(0) box, the sample-versus-expected-update contrast, the TD error $\delta_t$ (6.5), and its decomposition of the Monte Carlo error (6.6).
[^sb-drive]: **Sutton & Barto**, §6.1, Example 6.1 (Driving Home) and Figure 6.1: the predicted-total-travel-time sequence with $\gamma = 1$, and the contrast between Monte Carlo corrections (toward the actual outcome) and TD corrections (toward the next prediction).
[^sb-adv]: **Sutton & Barto**, §6.2 — Advantages of TD Prediction Methods: no model required (unlike DP), online and incremental learning (unlike MC), convergence of TD(0) to $v_\pi$, and Example 6.2 (Random Walk) with Figure 6.2 showing TD beating constant-$\alpha$ MC.
[^sb-opt]: **Sutton & Barto**, §6.3 — Optimality of TD(0): batch updating, Example 6.4 (You are the Predictor), the certainty-equivalence estimate as the maximum-likelihood-model value function that batch TD(0) computes, and the memory/computation argument ($O(n)$ versus $O(n^2)$/$O(n^3)$).