13  Temporal-Difference Learning

Core idea. Temporal-difference learning estimates value functions from experience by combining sampling with bootstrapping. Monte Carlo methods wait until the end of an episode and average complete returns. Dynamic programming uses a known model and backs up exact expectations. Temporal-difference methods use sampled transitions and replace the unknown future return by the current value estimate.

The basic TD(0) update is

\[ V(S_t) \leftarrow V(S_t)+\alpha \left[R_{t+1}+\gamma V(S_{t+1})-V(S_t)\right]. \]

The quantity

\[ \delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t) \]

is the temporal-difference error. It measures how surprising the one-step transition is relative to the current value function.

13.1 Learning goals

After reading this chapter, students should be able to:

1. explain the difference between Monte Carlo, dynamic programming, and temporal-difference learning;
2. define the TD target and TD error;
3. derive the TD(0) update from a one-step Bellman residual;
4. implement TD(0) for policy evaluation;
5. explain the bias-variance tradeoff between Monte Carlo and TD learning;
6. describe stochastic approximation conditions for TD convergence;
7. compare constant and decreasing learning-rate schedules;
8. understand the projected fixed-point interpretation of TD with tabular features;
9. derive \(n\)-step returns and TD(\(\lambda\)) returns;
10. use AI tools to check TD implementations without confusing sampled targets with exact Bellman expectations.

13.2 10.1 From complete returns to one-step bootstrapping

In Chapter 9, Monte Carlo prediction estimated

\[ V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s] \]

by averaging realized returns. For a visit to state \(s\), the Monte Carlo target is the complete return

\[ G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots. \]

This target is unbiased for \(V^\pi(S_t)\) under the sampling policy, but it may have high variance. It also requires waiting until the episode ends.

The Bellman equation suggests another target. For a fixed policy \(\pi\),

\[ V^\pi(s) = \mathbb E_\pi[R_{t+1}+\gamma V^\pi(S_{t+1})\mid S_t=s]. \]

If the unknown \(V^\pi\) were available on the right side, then one sampled transition would give the random target

\[ R_{t+1}+\gamma V^\pi(S_{t+1}). \]

TD learning replaces \(V^\pi\) by the current estimate \(V\). Thus the TD target is

\[ Y_t^{\mathrm{TD}}=R_{t+1}+\gamma V(S_{t+1}). \]

The update moves \(V(S_t)\) toward this target:

\[ V(S_t) \leftarrow V(S_t)+\alpha\left(Y_t^{\mathrm{TD}}-V(S_t)\right). \]

Equivalently,

\[ V(S_t) \leftarrow V(S_t)+\alpha\delta_t, \]

where

\[ \delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t). \]

TD learning is not simply Monte Carlo with a shorter episode. It estimates a Bellman fixed point by noisy one-step updates. The target depends on the current value function, so the target changes during learning.

13.2.1 Interactive: TD target and TD error

The TD error is the gap between the current estimate \(V(S_t)\) and the one-step bootstrapped target \(R_{t+1}+\gamma V(S_{t+1})\). The following Plotly figure shows how the target and update change as the discount factor and current estimates vary.

13.3 10.2 The prediction problem for a fixed policy

Let \(\pi\) be fixed. The environment and policy induce a Markov reward process with transition matrix

\[ P_\pi(s,s')=\sum_a \pi(a\mid s)P(s'\mid s,a) \]

and reward vector

\[ r_\pi(s)=\sum_a\pi(a\mid s)r(s,a). \]

The exact value function satisfies

\[ V^\pi=r_\pi+\gamma P_\pi V^\pi. \]

In vector form,

\[ (I-\gamma P_\pi)V^\pi=r_\pi. \]

TD learning assumes that \(P_\pi\) and \(r_\pi\) are not known, or that solving this system is not the desired computational strategy. Instead, we observe transitions

\[ S_t,R_{t+1},S_{t+1} \]

sampled under policy \(\pi\) and update only the value of the visited state.

For a tabular value function, write \(V_t(s)\) for the estimate after \(t\) updates. TD(0) is

\[ V_{t+1}(s)= \begin{cases} V_t(s)+\alpha_t\left[R_{t+1}+\gamma V_t(S_{t+1})-V_t(S_t)\right], & s=S_t,\\ V_t(s), & s\neq S_t. \end{cases} \]

The update is local in state space but global in meaning: changing \(V(S_t)\) changes future targets for predecessor states.

13.4 10.3 Expected TD update and the Bellman operator

To understand TD mathematically, condition on \(S_t=s\). Assume temporarily that the current value function \(V\) is fixed. Then

\[ \mathbb E_\pi[\delta_t\mid S_t=s] = \mathbb E_\pi[R_{t+1}+\gamma V(S_{t+1})-V(s)\mid S_t=s]. \]

Therefore

\[ \mathbb E_\pi[\delta_t\mid S_t=s] = (T^\pi V)(s)-V(s), \]

where

\[ (T^\pi V)(s)=r_\pi(s)+\gamma\sum_{s'}P_\pi(s,s')V(s') \]

is the Bellman expectation operator. Thus TD(0) is a stochastic approximation to the fixed-point equation

\[ T^\pi V=V. \]

This explains why TD is closely related to iterative policy evaluation. The deterministic full-sweep update is

\[ V_{k+1}=T^\pi V_k. \]

TD replaces the exact expectation in \(T^\pi V_k\) by a single sampled transition and updates only the visited state.

TD(0) can be interpreted as a noisy asynchronous fixed-point iteration for the Bellman expectation equation.

13.5 10.4 A small tabular example

Consider a three-state Markov reward process with transition matrix

\[ P= \begin{pmatrix} 0.1 & 0.8 & 0.1\\ 0.2 & 0.2 & 0.6\\ 0.0 & 0.4 & 0.6 \end{pmatrix} \]

and reward vector

\[ r=(0,1,2)^T. \]

The exact value is

\[ V=(I-\gamma P)^{-1}r. \]

The following Python code computes the exact solution and then estimates it using TD(0) from a single long trajectory.

import numpy as np

rng = np.random.default_rng(7339)

P = np.array([
    [0.1, 0.8, 0.1],
    [0.2, 0.2, 0.6],
    [0.0, 0.4, 0.6]
])
r = np.array([0.0, 1.0, 2.0])
gamma = 0.9

V_exact = np.linalg.solve(np.eye(3) - gamma * P, r)
print("Exact value:", np.round(V_exact, 4))

V = np.zeros(3)
s = 0
alpha0 = 0.4
visits = np.zeros(3, dtype=int)

for t in range(20_000):
    s_next = rng.choice(3, p=P[s])
    reward = r[s]
    visits[s] += 1
    alpha = alpha0 / np.sqrt(visits[s])
    td_error = reward + gamma * V[s_next] - V[s]
    V[s] += alpha * td_error
    s = s_next

print("TD estimate:", np.round(V, 4))
print("Absolute error:", np.round(np.abs(V - V_exact), 4))

Exact value: [12.773  14.2101 15.4688]
TD estimate: [12.8564 14.3565 15.518 ]
Absolute error: [0.0833 0.1464 0.0492]

The estimate is not obtained by solving a linear system. It is learned from sampled transitions.

13.6 10.5 Monte Carlo versus TD

Monte Carlo and TD methods estimate the same value function, but their targets differ.

For Monte Carlo prediction, the target is

\[ Y_t^{\mathrm{MC}}=G_t. \]

For TD(0), the target is

\[ Y_t^{\mathrm{TD}}=R_{t+1}+\gamma V(S_{t+1}). \]

The Monte Carlo target is an unbiased sample of the return, conditional on \(S_t\), but can have large variance. The TD target usually has lower variance because it uses only one random reward and one random next state. However, it is biased during learning because \(V(S_{t+1})\) is only an estimate.

This creates a central tradeoff:

Method	Target	Bias during learning	Variance	Needs episode end?
Monte Carlo	\(G_t\)	low for value target	high	yes
TD(0)	\(R_{t+1}+\gamma V(S_{t+1})\)	yes	lower	no
Dynamic programming	\(r+\gamma PV\)	none if model exact	none	no

13.6.1 Interactive: Monte Carlo and TD learning curves

The following demonstration compares the typical behavior of Monte Carlo and TD estimates on a small prediction problem. Monte Carlo uses complete returns; TD uses bootstrapped one-step targets.

13.7 10.6 Learning rates and stochastic approximation

TD learning is a stochastic approximation algorithm. A generic stochastic approximation update has the form

\[ \theta_{t+1}=\theta_t+\alpha_t\left[h(\theta_t)+M_{t+1}\right], \]

where \(h\) is a deterministic drift and \(M_{t+1}\) is noise with mean zero conditional on the past.

For tabular TD, the drift is related to the Bellman residual

\[ T^\pi V - V. \]

The standard decreasing step-size conditions are

\[ \sum_{t=0}^{\infty}\alpha_t=\infty, \qquad \sum_{t=0}^{\infty}\alpha_t^2<\infty. \]

The first condition says that learning must not stop too early. The second condition says that the accumulated noise must be controlled.

Examples include

\[ \alpha_t=\frac{1}{t+1} \]

and more generally

\[ \alpha_t=\frac{c}{(t+1)^p}, \qquad \frac{1}{2}<p\leq 1. \]

In practice, constant learning rates are also common. A constant \(\alpha\) may not converge exactly, but it can track nonstationary environments and is often useful in continuing learning.

13.7.1 Interactive: learning-rate schedules

The next figure compares decreasing and constant learning rates. Decreasing schedules stabilize asymptotically; constant schedules keep adapting but fluctuate near the solution.

13.8 10.7 TD convergence in the tabular case

A full proof of TD convergence requires stochastic approximation theory, but the main ideas are accessible.

Assume:

1. the state space is finite;
2. the policy \(\pi\) is fixed;
3. the Markov chain induced by \(\pi\) visits each relevant state infinitely often;
4. rewards have bounded second moments;
5. step sizes satisfy the stochastic approximation conditions.

Then tabular TD(0) converges to \(V^\pi\) under standard ergodicity assumptions.

The fixed point is unique because \(T^\pi\) is a contraction in the sup norm:

\[ \|T^\pi V-T^\pi W\|_\infty \leq \gamma\|V-W\|_\infty. \]

The TD update is noisy, but its conditional expectation points toward this fixed point:

\[ \mathbb E[\delta_t\mid S_t=s,V_t] = (T^\pi V_t)(s)-V_t(s). \]

This is why TD can learn without knowing \(P_\pi\).

13.9 10.8 TD prediction on the random walk example

A classical example uses a one-dimensional random walk with two terminal states. The nonterminal states are \(1,2,3,4,5\). From each nonterminal state, the process moves left or right with equal probability. The left terminal gives reward \(0\); the right terminal gives reward \(1\).

For \(\gamma=1\), the exact values are

\[ V^*(i)=\frac{i}{6}, \qquad i=1,2,3,4,5. \]

Here the star denotes the true prediction target for the fixed random policy, not an optimal control value.

import numpy as np

rng = np.random.default_rng(5110)

n_states = 5
true_values = np.arange(1, n_states + 1) / (n_states + 1)

V = np.full(n_states + 2, 0.5)
V[0] = 0.0
V[-1] = 0.0
alpha = 0.1
gamma = 1.0

def run_episode_td(V, alpha):
    s = 3
    while s not in [0, n_states + 1]:
        s_next = s + rng.choice([-1, 1])
        reward = 1.0 if s_next == n_states + 1 else 0.0
        V[s] += alpha * (reward + gamma * V[s_next] - V[s])
        s = s_next

snapshots = {}
for episode in range(1, 101):
    run_episode_td(V, alpha)
    if episode in [1, 10, 50, 100]:
        snapshots[episode] = V[1:-1].copy()

print("True values:", np.round(true_values, 3))
for episode, values in snapshots.items():
    print(f"After {episode:3d} episodes:", np.round(values, 3))

True values: [0.167 0.333 0.5   0.667 0.833]
After   1 episodes: [0.45 0.5  0.5  0.5  0.5 ]
After  10 episodes: [0.389 0.472 0.52  0.57  0.747]
After  50 episodes: [0.167 0.366 0.501 0.755 0.895]
After 100 episodes: [0.178 0.452 0.6   0.743 0.889]

13.9.1 Interactive: TD learning on a random walk

The figure below shows how TD estimates on the random-walk problem move toward the exact linear value function.

13.10 10.9 The TD error as a diagnostic

The TD error

\[ \delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t) \]

is not merely an update signal. It is also a diagnostic.

If \(V=V^\pi\), then

\[ \mathbb E[\delta_t\mid S_t=s]=0 \]

for each state \(s\). Individual TD errors need not be zero because transitions and rewards are random. However, persistent positive or negative average TD error in a state indicates that the value estimate is systematically too low or too high relative to its Bellman target.

This diagnostic is important in deep RL. Neural value functions are often trained by minimizing squared TD error. Large TD-error outliers may indicate rare transitions, reward scaling problems, poor exploration, or function-approximation instability.

13.11 10.10 Batch TD and the empirical Bellman equation

Suppose we collect a dataset of transitions

\[ \mathcal D=\{(s_i,r_i,s_i')\}_{i=1}^n. \]

A simple batch TD objective is the empirical squared TD error

\[ L(V)=\frac{1}{n}\sum_{i=1}^n \left(r_i+\gamma V(s_i')-V(s_i)\right)^2. \]

In the tabular case, minimizing this objective is not exactly the same as solving the empirical Bellman equation, because the target also depends on \(V\). This distinction becomes more important with function approximation.

For now, the key point is that TD methods transform sequential prediction into learning from one-step transitions. This is the bridge to later algorithms such as SARSA, Q-learning, actor-critic methods, and deep Q-networks.

13.12 10.11 \(n\)-step returns

TD(0) uses a one-step target. Monte Carlo uses the full return. Between them are \(n\)-step returns:

\[ G_t^{(n)} = R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{n-1}R_{t+n} + \gamma^n V(S_{t+n}). \]

When \(n=1\),

\[ G_t^{(1)}=R_{t+1}+\gamma V(S_{t+1}), \]

which is the TD(0) target. When \(n\) extends to the end of the episode, the target becomes Monte Carlo.

The \(n\)-step update is

\[ V(S_t)\leftarrow V(S_t)+\alpha\left(G_t^{(n)}-V(S_t)\right). \]

Increasing \(n\) usually reduces bootstrapping bias but increases variance and delays updates.

13.13 10.12 TD(\(\lambda\)) and eligibility traces

TD(\(\lambda\)) combines many \(n\)-step returns. The forward-view \(\lambda\)-return is

\[ G_t^\lambda = (1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_t^{(n)}, \qquad 0\leq \lambda <1. \]

In episodic problems, the final Monte Carlo return receives the remaining weight. The parameter \(\lambda\) controls the interpolation:

• \(\lambda=0\) gives TD(0);
• \(\lambda\) close to \(1\) behaves more like Monte Carlo;
• intermediate \(\lambda\) blends short and long backups.

The backward-view implementation uses eligibility traces. In the tabular case, the trace vector \(e_t\) is updated by

\[ e_t(s)=\gamma\lambda e_{t-1}(s)+\mathbf 1\{S_t=s\}. \]

Then all states are updated according to

\[ V(s)\leftarrow V(s)+\alpha\delta_t e_t(s). \]

Eligibility traces give credit not only to the current state but also to recently visited states.

13.13.1 Interactive: TD(\(\lambda\)) weighting of backups

The parameter \(\lambda\) controls how much weight is placed on longer returns. The following figure shows the geometric weights on \(n\)-step returns for different values of \(\lambda\).

13.14 10.13 Python implementation of TD(\(\lambda\))

The following code implements a simple tabular TD(\(\lambda\)) update for the random-walk example.

import numpy as np

rng = np.random.default_rng(6241)

n_states = 5
terminal_left = 0
terminal_right = n_states + 1
gamma = 1.0
alpha = 0.05
lam = 0.8

V = np.full(n_states + 2, 0.5)
V[terminal_left] = 0.0
V[terminal_right] = 0.0

def td_lambda_episode(V, alpha, lam):
    e = np.zeros_like(V)
    s = 3
    while s not in [terminal_left, terminal_right]:
        s_next = s + rng.choice([-1, 1])
        reward = 1.0 if s_next == terminal_right else 0.0
        delta = reward + gamma * V[s_next] - V[s]
        e *= gamma * lam
        e[s] += 1.0
        V += alpha * delta * e
        V[terminal_left] = 0.0
        V[terminal_right] = 0.0
        s = s_next

for _ in range(200):
    td_lambda_episode(V, alpha, lam)

print("TD(lambda) values:", np.round(V[1:-1], 3))
print("True values:      ", np.round(np.arange(1, n_states + 1) / 6, 3))

TD(lambda) values: [0.117 0.421 0.66  0.847 0.948]
True values:       [0.167 0.333 0.5   0.667 0.833]

13.15 10.14 What changes with function approximation?

For a tabular value function, each state has its own parameter. With function approximation, we use a parameter vector \(\theta\) and a value function

\[ V_\theta(s)\approx V^\pi(s). \]

For linear approximation,

\[ V_\theta(s)=\phi(s)^T\theta. \]

The TD error becomes

\[ \delta_t=R_{t+1}+\gamma\phi(S_{t+1})^T\theta_t-\phi(S_t)^T\theta_t. \]

The semi-gradient TD update is

\[ \theta_{t+1}=\theta_t+\alpha_t\delta_t\phi(S_t). \]

The word semi-gradient is important. The TD target depends on \(\theta_t\), but the update treats the target as fixed when differentiating with respect to \(V_\theta(S_t)\). This idea becomes central in Chapter 13.

13.16 10.15 AI component: using an AI assistant to audit TD code

TD algorithms are short, but they are easy to implement incorrectly. A useful AI workflow is to ask an assistant to check the following issues:

1. Is the TD target computed before or after updating \(V(S_t)\)?
2. Are terminal values handled correctly?
3. Is the reward associated with the transition \(S_t\to S_{t+1}\)?
4. Is the learning rate constant, state-dependent, or time-dependent?
5. Is the experiment episodic or continuing?
6. Is the code accidentally using the exact model when it claims to be model-free?
7. Are random seeds and evaluation metrics reported clearly?

A good prompt is:

I am implementing tabular TD(0) for a fixed-policy Markov reward process. Please check whether my TD target, terminal-state handling, learning-rate schedule, and evaluation metric are mathematically consistent. Do not rewrite the whole code. First list possible conceptual errors.

Warning

AI tools often describe TD as minimizing a supervised regression loss. That explanation is incomplete. TD targets depend on the current value estimate, so TD is better understood first as stochastic approximation to a Bellman fixed point.

13.17 10.16 Summary

Temporal-difference learning is one of the central ideas of reinforcement learning. It combines the sampling viewpoint of Monte Carlo methods with the Bellman fixed-point viewpoint of dynamic programming.

The essential update is

\[ V(S_t) \leftarrow V(S_t)+\alpha \left[R_{t+1}+\gamma V(S_{t+1})-V(S_t)\right]. \]

The TD error

\[ \delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t) \]

is a sampled Bellman residual. In expectation, it points toward the Bellman fixed point. This idea will be reused immediately in SARSA and Q-learning, and later in actor-critic and deep reinforcement learning.

13.18 Conceptual exercises

1. Explain why TD(0) can update before an episode terminates, while ordinary Monte Carlo prediction cannot.
2. Describe the bias-variance tradeoff between Monte Carlo and TD learning.
3. In what sense is TD a model-free method? In what sense does it still rely on the Markov property?
4. Why is the TD target not a fixed label in the same way as a supervised-learning target?
5. Explain how the TD error can be used as a diagnostic for value-function quality.

13.19 Mathematical exercises

1. Let \(T^\pi\) be the Bellman expectation operator. Prove that \(T^\pi\) is a contraction in \(\|\cdot\|_\infty\) when \(0\leq\gamma<1\).
2. Show that if \(V=V^\pi\), then \(\mathbb E[\delta_t\mid S_t=s]=0\) for every state \(s\).
3. For a two-state Markov reward process, write the TD(0) expected update explicitly and identify its fixed point.
4. Derive the \(n\)-step return formula recursively.
5. Show that the weights \((1-\lambda)\lambda^{n-1}\) sum to \(1\) for \(0\leq\lambda<1\).
6. Derive the semi-gradient TD update for \(V_\theta(s)=\phi(s)^T\theta\).

13.20 Computational exercises

1. Implement TD(0) on the random-walk problem and compare several learning rates.
2. Compare Monte Carlo prediction and TD(0) using root mean squared error against the exact value function.
3. Modify the random-walk example so the right terminal reward is \(2\) instead of \(1\). Predict and verify the new exact value function.
4. Implement \(n\)-step TD for \(n=1,2,4,8\) and compare learning curves.
5. Implement TD(\(\lambda\)) for \(\lambda=0,0.4,0.8,1.0\) and compare empirical performance.
6. Record TD errors during training and plot their moving average by state.

13.21 AI-assisted exercises

1. Ask an AI assistant to explain TD(0), then identify whether the explanation correctly distinguishes the TD target from the Monte Carlo return.
2. Give an AI assistant a TD implementation with one intentional bug in terminal-state handling. Ask it to find the bug and explain the mathematical consequence.
3. Ask an AI assistant to design a Monte Carlo versus TD experiment. Critique whether the proposed comparison uses fair learning rates and evaluation metrics.
4. Use an AI assistant to generate a small MRP. Then compute the exact value function yourself and verify whether the proposed TD code converges to it.
5. Ask for an explanation of TD(\(\lambda\)) in both forward-view and backward-view language. Check whether the weights and eligibility trace equations are consistent.

13.22 Instructor notes

This chapter should be taught as the transition from averaging complete returns to learning Bellman fixed points from sampled transitions. Students with statistics backgrounds often understand the sample-average view quickly, but TD requires a new idea: the target is itself changing because it uses the current estimate. Emphasize the conditional expectation of the TD error and the relationship between TD and stochastic approximation.

A good classroom sequence is:

1. compare MC and TD targets on one trajectory;
2. derive the expected TD update;
3. run the random-walk example;
4. discuss learning rates;
5. introduce \(n\)-step returns and TD(\(\lambda\)) as the bridge between MC and TD.