Temporal-Difference Learning

Introduction and Context

Temporal-difference (TD) learning is a central family of reinforcement-learning methods for estimating values and improving policies from experience. It combines two ideas:

1. Sampling: learning from transitions actually observed by an agent.

2. Bootstrapping: updating an estimate toward a target that contains another learned estimate.

This combination distinguishes TD methods from both dynamic programming and Monte Carlo learning. Dynamic programming assumes that the environment model is known. Monte Carlo methods learn from complete returns and therefore wait until an episode ends. TD methods can learn after every transition, including in continuing tasks, without requiring a model or episode termination.

TD learning underlies widely used algorithms such as SARSA, Expected SARSA, Q-learning, eligibility-trace methods, and many modern actor–critic systems. It is important in robotics, recommendation, resource allocation, game playing, industrial control, and adaptive decision systems.

The chapter uses the standard Markov decision process (MDP) notation. At time t, the agent observes state S_t, selects action A_t, receives reward R_{t+1}, and enters state S_{t+1}. The discount factor is γ, where 0 ≤ γ < 1 for discounted continuing tasks. A policy π specifies action probabilities π(a|s). The value of a state under policy π is

V^π(s) = E_π[G_t | S_t = s],

where the return is

G_t = R_{t+1} + γR_{t+2} + γ²R_{t+3} + ⋯.

For action values,

Q^π(s,a) = E_π[G_t | S_t=s, A_t=a].

Terminal states are usually assigned value zero, so a target involving a terminal next state does not include a bootstrap term.

Learning Objectives

By the end of this chapter, students should be able to:

• explain prediction and control in TD learning;
• derive and apply the TD(0), SARSA, Expected SARSA, and Q-learning updates;
• distinguish on-policy and off-policy learning;
• compare bootstrapping, sampling, bias, variance, and convergence;
• calculate n-step returns and explain their relation to one-step and Monte Carlo methods;
• describe eligibility traces and TD(λ);
• select suitable TD methods for practical applications;
• identify limitations involving function approximation, exploration, safety, and distribution shift.

1. TD Prediction: Learning State Values

1.1 The one-step TD target

Suppose an agent follows policy π and observes one transition. The one-step TD target is

R_{t+1} + γV(S_{t+1}),

where V is the current estimate of V^π. The prediction error, or TD error, is

δ_t = R_{t+1} + γV(S_{t+1}) − V(S_t).

The tabular TD(0) update is

V(S_t) ← V(S_t) + αδ_t,

where α is the learning rate, normally 0 < α ≤ 1.

Equivalently,

V(S_t) ← V(S_t) + α[R_{t+1} + γV(S_{t+1}) − V(S_t)].

The update applies to the state visited at time t. For a terminal next state, the target is simply R_{t+1}; the term γV(S_{t+1}) is omitted or treated as zero.

The update is called bootstrapping because the target uses the current estimate V(S_{t+1}) rather than waiting for the complete return. It is a sampled update because only the transition actually experienced is used, rather than an expectation over every possible successor state and reward.

1.2 Relation to the Bellman equation

The Bellman expectation equation for a fixed policy is

V^π(s) = E_π[R_{t+1} + γV^π(S_{t+1}) | S_t=s].

TD(0) uses one sample of the random quantity inside this expectation. If the current estimate were exact on all relevant states, the expected TD error would be zero. Thus TD learning can be interpreted as stochastic approximation to the Bellman fixed point.

The Bellman optimality equation is

V(s) = max_a E[R_{t+1} + γV(S_{t+1}) | s,a],

and

Q(s,a) = E[R_{t+1} + γ max_{a'}Q(S_{t+1},a') | s,a].

These equations motivate TD control methods, but prediction and control should be distinguished. Prediction estimates the value of a specified policy. Control seeks to improve a policy while learning values.

1.3 Worked numerical example: TD(0)

Assume α = 0.2 and γ = 0.9. The agent transitions from state A to state B, receives reward 3, and currently estimates V(A)=5 and V(B)=7. Then

δ_t = 3 + 0.9(7) − 5 = 4.3.

Therefore,

V(A) ← 5 + 0.2(4.3) = 5.86.

The estimate increases because the sampled one-step target, 9.3, exceeds the old estimate of 5. The agent does not replace V(A) with 9.3; it moves part of the way toward that target.

2. Monte Carlo, Dynamic Programming, and TD Learning

The three approaches differ in the information used for an update.

Dynamic programming

Dynamic programming uses a known transition and reward model. For policy evaluation, it computes expected backups over all possible outcomes. It avoids sampling noise but may be computationally expensive and is unavailable when the model is unknown.

Monte Carlo learning

Monte Carlo prediction updates after a complete episode using the observed return G_t:

V(S_t) ← V(S_t) + α[G_t − V(S_t)].

The target is unbiased for the value under the behavior policy when the episode return is correctly sampled, but it can have high variance. It cannot naturally update from an unfinished episode.

TD learning

TD(0) updates after one transition using

R_{t+1} + γV(S_{t+1}).

It is usually lower variance and faster to propagate information than Monte Carlo learning, but its target is biased because it depends on an imperfect estimate. In tabular prediction with suitable conditions, TD methods converge to the correct value function.

A useful comparison is:

• Dynamic programming: model-based, expectation-based, bootstrapping.
• Monte Carlo: model-free, sampled complete returns, no bootstrapping.
• TD: model-free, sampled transitions, bootstrapping.

The terms bias and variance require care. A one-step TD target may be biased relative to the full return because it substitutes an estimate for future rewards. Its variance is often lower because it includes fewer random rewards. Monte Carlo returns are unbiased in the usual policy-evaluation setting but may fluctuate substantially. Multi-step methods provide a continuum between these extremes.

3. TD Control

3.1 SARSA

SARSA is an on-policy action-value method. Its name comes from the sequence used in an update:

S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}.

The update is

Q(S_t,A_t) ← Q(S_t,A_t) + αδ_t,

where

δ_t = R_{t+1} + γQ(S_{t+1},A_{t+1}) − Q(S_t,A_t).

The next action A_{t+1} is selected using the same behavior policy that is being evaluated, such as ε-greedy action selection. Consequently, SARSA learns the value of the behavior policy, including its exploratory actions. It is on-policy.

A typical ε-greedy policy selects a maximizing action with probability 1−ε and explores with probability ε, with the exploration probability distributed among actions. Ties should be handled consistently, often by random tie-breaking.

3.2 Expected SARSA

Expected SARSA replaces the sampled next action with an expectation under the policy:

Q(S_t,A_t) ← Q(S_t,A_t) + α[R_{t+1} + γΣ_{a}π(a|S_{t+1})Q(S_{t+1},a) − Q(S_t,A_t)].

This can reduce variance caused by sampling A_{t+1}. It remains on-policy when π is the policy whose expectation is used. Its computational cost is higher than SARSA when there are many actions because all or many next-action values must be evaluated.

For an ε-greedy policy, the expectation must account for both greedy and exploratory action probabilities. It is incorrect simply to use the maximum unless the policy is explicitly greedy.

3.3 Q-learning

Q-learning is an off-policy method. Its update is

Q(S_t,A_t) ← Q(S_t,A_t) + α[R_{t+1} + γ max_a Q(S_{t+1},a) − Q(S_t,A_t)].

The behavior policy may be exploratory, but the target represents a greedy target policy. Thus the algorithm learns toward the optimal action-value function while collecting data under a possibly different behavior policy.

The distinction is between:

• behavior policy: the policy used to select actions and generate data;
• target policy: the policy whose value is being estimated or improved.

SARSA uses the behavior policy in its target. Q-learning uses a greedy target in its bootstrap term.

3.4 Worked comparison

Suppose γ=0.9, α=0.5, current Q(S_t,A_t)=4, observed reward is 2, and the next-state action values are Q(S_{t+1},a_1)=6 and Q(S_{t+1},a_2)=10.

If SARSA selects a_1, its target is 2+0.9(6)=7.4, so the updated value is

4 + 0.5(7.4−4)=5.7.

Q-learning uses the maximum value, giving target 2+0.9(10)=11. The update is

4 + 0.5(11−4)=7.5.

If the next action selected by SARSA had been a_2, SARSA would also use target 11. The difference is therefore not the current action or reward; it is the treatment of the next action in the target.

4. n-Step Returns

One-step TD uses only one observed reward before bootstrapping. Monte Carlo uses all rewards until termination. An n-step return combines these approaches:

G_{t:t+n} = R_{t+1} + γR_{t+2} + ⋯ + γ^{n−1}R_{t+n} + γ^nV(S_{t+n}),

provided the episode has not terminated before time t+n. If termination occurs earlier, the remaining bootstrap term is omitted.

The n-step prediction update is

V(S_t) ← V(S_t) + α[G_{t:t+n} − V(S_t)].

For action values, replace V with Q and use the relevant action at the bootstrap state. In an on-policy control method, the n-step SARSA target uses the subsequent actions generated by the behavior policy. An n-step Q-learning target may bootstrap using a greedy action value.

Example of a three-step return

Let γ=0.9, and suppose the observed rewards are R_{t+1}=2, R_{t+2}=−1, R_{t+3}=4. If V(S_{t+3})=5, then

G_{t:t+3} = 2 + 0.9(−1) + 0.9²(4) + 0.9³(5)

= 2 − 0.9 + 3.24 + 3.645

= 7.985.

If V(S_t)=6 and α=0.1, the update is

V(S_t) ← 6 + 0.1(7.985−6) = 6.1985.

As n increases, the method relies more on observed rewards and less on bootstrapping. Larger n can reduce bootstrap bias but increase return variance and delay updates. The Monte Carlo method is the limiting case when n extends to the end of the episode.

5. Eligibility Traces and TD(λ)

One-step TD updates only the most recently visited state. However, a reward may provide useful information about several preceding states. Eligibility traces provide a decaying memory of recently visited states.

For accumulating traces, a simple tabular update is

E_t(s) = γλE_{t−1}(s) + 1{S_t=s},

where E_t(s) is the eligibility trace, λ satisfies 0≤λ≤1, and 1{·} is an indicator function. The corresponding TD(λ) update is

V(s) ← V(s) + αδ_tE_t(s)

for each state s, with

δ_t = R_{t+1} + γV(S_{t+1}) − V(S_t).

Some implementations use replacing traces, in which the trace for the current state is set to 1 rather than increased by 1. These variants behave differently when states are revisited and should not be mixed without understanding the convention.

The parameter λ controls the trace horizon:

• λ=0 gives one-step TD(0);
• λ near 1 allows credit to spread farther into the past;
• in episodic prediction, λ=1 is closely related to Monte Carlo learning, subject to implementation and step-size details.

There are two complementary views of TD(λ). The forward view defines a λ-return as a geometrically weighted mixture of n-step returns:

G_t^λ = (1−λ)Σ_{n=1}^∞ λ^{n−1}G_{t:t+n},

with suitable treatment of the terminal tail in episodic tasks. The backward view computes the same general learning idea online using eligibility traces. The forward view is conceptually clear but appears to require future information; the backward view is practical for real-time learning.

Eligibility traces are especially useful when rewards are delayed. They assign larger credit to recently visited states and progressively less credit to earlier states, allowing information to propagate more rapidly than one-step TD.

For action values, traces are maintained for state–action pairs. Algorithms include SARSA(λ), Q(λ), and true-online TD(λ). Off-policy traces require additional care because naive combinations of bootstrapping, traces, and changing policies can become unstable.

6. Convergence, Bias, Variance, and Stability

6.1 Tabular convergence

Under standard conditions, tabular TD prediction converges with probability one when the Markov process is suitably well behaved, every relevant state is visited sufficiently often, rewards are bounded, and learning rates satisfy stochastic-approximation conditions such as

Σ_t α_t = ∞ and Σ_t α_t² < ∞.

A common example is α_t decreasing over visits. Constant step sizes are often used in practical nonstationary problems, but they generally produce continuing fluctuations around the target rather than exact convergence.

Tabular Q-learning has convergence guarantees under conditions including sufficient exploration of state–action pairs, bounded rewards, appropriate diminishing step sizes, and a finite MDP. In practice, these assumptions may fail.

6.2 Bias–variance trade-off

One-step methods have short targets and usually lower variance, but they can propagate reward information slowly and inherit bias from inaccurate bootstrap estimates. Monte Carlo methods avoid bootstrap bias in policy evaluation but can have high variance. n-step and λ-return methods interpolate between these properties.

Q-learning introduces another source of bias: the maximum over noisy estimates tends to be optimistically biased. If several action estimates contain random errors, selecting the largest estimate tends to select a positive error. Double Q-learning addresses this issue by separating action selection from action evaluation, for example by using one estimate to choose the action and another to evaluate it.

6.3 Function approximation

In large or continuous state spaces, a table is impractical. A parameterized approximation V(s,w) or Q(s,a,w) is used. A semi-gradient TD update for state values is

w ← w + αδ_t∇_w V(S_t,w).

This treats the bootstrap target as fixed while differentiating the current estimate. With linear function approximation and suitable conditions, some TD methods have strong theoretical properties. With nonlinear approximation, especially neural networks, instability can arise from the interaction of:

• bootstrapping;
• off-policy data;
• function approximation.

This combination is often called the “deadly triad.” Experience replay, target networks, carefully controlled exploration, gradient clipping, normalization, and algorithm-specific corrections can improve practical stability, but they do not eliminate all risks.

7. An Illustrative Applied Case: Safe Warehouse Routing

Background

Consider an illustrative autonomous warehouse robot that moves through a grid to deliver parts. Each state includes the robot’s location, battery level, and whether a delivery is pending. Actions are movement commands. A successful delivery gives a positive reward, time and energy consumption produce small negative rewards, and entering a restricted area incurs a large penalty.

Problem

A Monte Carlo method would need to wait until delivery or episode termination before assigning credit to early movement decisions. This is inefficient when routes are long. A TD method can update after every movement.

Analysis

SARSA is attractive when the robot’s actual exploratory behavior must be reflected in the learned values. Suppose the robot follows an ε-greedy policy. A route that passes close to a restricted area may have a high value under a purely greedy policy but a lower value when exploration can cause accidental entry. SARSA’s target includes the value of the next action selected by the exploratory policy, so it can learn a more conservative route.

Q-learning instead uses the maximum next-state action value. It may learn an optimal greedy route more rapidly in a stationary, well-explored simulation, but the learned value may not fully reflect the consequences of exploration during deployment.

Approach

A practical design could use:

1. state and action constraints that prohibit physically impossible moves;

2. a shaped reward for energy and delay, audited to ensure it does not encourage unsafe shortcuts;

3. SARSA or Expected SARSA during safety-sensitive exploration;

4. eligibility traces when delivery rewards are delayed;

5. a separate safety supervisor that can override an RL action;

6. evaluation under multiple random seeds and demand patterns;

7. conservative deployment, beginning in simulation and controlled pilots.

If the action set is small, Expected SARSA can reduce variance by averaging over the ε-greedy next-action distribution. If the route contains long delayed consequences, SARSA(λ) can transmit delivery information to earlier decisions more quickly.

Outcome

The expected outcome is not merely a higher average reward. Evaluation should include delivery success rate, energy use, restricted-area violations, worst-case delay, and performance under demand changes. A policy that maximizes mean reward while occasionally causing hazardous behavior is unacceptable for a warehouse safety system.

Learning points

This case illustrates that algorithm choice depends on the relationship between learning and deployment. On-policy methods can represent exploratory risk more directly; off-policy methods can learn a greedy target from exploratory data; traces can address delayed rewards; and governance requires constraints and monitoring beyond the learning algorithm itself.

8. Implementation Best Practices

A reliable TD implementation should:

• define terminal-state handling explicitly;
• verify whether the algorithm is on-policy or off-policy;
• use the correct behavior-policy probabilities for Expected SARSA;
• distinguish reward timing from state transitions;
• test a small tabular environment before using function approximation;
• log TD errors, returns, visit counts, and policy changes;
• use separate training and evaluation policies;
• test sensitivity to α, γ, ε, and λ;
• average results over multiple random seeds;
• monitor rare but serious failures, not only mean reward;
• use reproducible environment and random-number settings.

Reward design deserves special attention. Reward shaping can accelerate learning, but poorly designed rewards may produce reward hacking: the agent discovers an unintended way to obtain numerical reward while violating the actual objective. In consequential applications, hard constraints, human oversight, audit logs, and rollback procedures should accompany TD learning.

9. Contemporary Developments

Modern deep reinforcement-learning systems frequently use TD targets. Deep Q-networks employ replayed transitions and a delayed target network to reduce harmful feedback between changing predictions and bootstrap targets. Double estimators reduce maximization bias, while dueling architectures separate state-value and action-advantage representations. Distributional methods estimate a distribution of returns rather than only their mean. Retrace-style and other corrected multi-step methods seek to obtain the benefits of multi-step learning while controlling off-policy errors.

These developments do not make foundational TD concepts obsolete. They make the underlying assumptions more important. Replay changes the data distribution, target networks create delayed targets, and neural approximation introduces generalization and stability concerns. A practitioner must therefore understand the one-step TD error, policy relationship, target construction, and convergence limitations before selecting an advanced method.

Chapter Summary

Temporal-difference learning estimates values from sampled transitions and bootstraps from current estimates. TD(0) updates a state value toward a one-step reward-plus-discounted-value target. SARSA is an on-policy control method because its target uses the next action actually selected by the behavior policy. Expected SARSA replaces that sampled action with a policy-weighted expectation. Q-learning is off-policy because it uses a greedy maximum in its target even when behavior is exploratory.

n-step returns combine observed rewards with later bootstrapping and create a continuum between one-step TD and Monte Carlo learning. Eligibility traces and TD(λ) distribute TD errors over recently visited states, improving learning when rewards are delayed. The choice of method involves trade-offs among computational cost, bias, variance, information delay, and policy dependence. Tabular methods have strong convergence results under suitable assumptions, whereas function approximation—particularly the combination of bootstrapping, off-policy data, and nonlinear approximation—can be unstable. Practical systems require careful terminal handling, hyperparameter testing, safety constraints, monitoring, and evaluation beyond average reward.

Key Terms

TD learning: Model-free learning that updates estimates using sampled transitions and bootstrap targets.

Bootstrapping: Updating an estimate toward a target that contains another current estimate.

TD error: The difference between a one-step bootstrap target and the current value estimate.

TD(0): The one-step temporal-difference prediction algorithm.

Policy evaluation: Estimating the value of a specified policy.

TD control: Using temporal-difference estimates to improve a policy.

SARSA: On-policy action-value learning using the sequence state, action, reward, next state, next action.

Expected SARSA: An action-value method whose target averages next-action values under a policy.

Q-learning: Off-policy action-value learning using the maximum next-action estimate.

Behavior policy: The policy used to generate experience.

Target policy: The policy whose value is represented by the learning target.

n-step return: A return using n observed rewards followed by a bootstrap estimate.

Eligibility trace: A decaying memory assigning credit to recently visited states or state–action pairs.

TD(λ): A family of methods combining multi-step returns through the parameter λ.

On-policy learning: Learning about the same policy used to generate behavior.

Off-policy learning: Learning about a target policy using data generated by another policy.

Bootstrapping bias: Error introduced when an imperfect estimate is used in a target.

Deadly triad: The potentially unstable combination of function approximation, bootstrapping, and off-policy learning.

Maximization bias: Optimistic bias caused by selecting the maximum among noisy value estimates.

Reward shaping: Modifying rewards to guide learning while attempting to preserve the intended objective.

Review Questions

Short Answer Questions

1. What is bootstrapping in temporal-difference learning?

2. Why is SARSA classified as an on-policy method?

3. State the one-step TD(0) update for a state-value estimate.

4. What role does λ play in TD(λ)?

5. Why can Monte Carlo returns have higher variance than one-step TD targets?

Long Answer Questions

1. Compare dynamic programming, Monte Carlo learning, and TD learning in terms of model requirements, sampling, bootstrapping, and update timing.

2. Explain the differences among SARSA, Expected SARSA, and Q-learning, including their targets and policy relationships.

3. Derive and interpret an n-step return, and explain how changing n affects bias, variance, and learning speed.

4. Explain eligibility traces using both the forward-view and backward-view interpretations of TD(λ).

5. Discuss why function approximation can make TD control unstable and explain the deadly triad.

Analytical / Application Questions

1. An agent has γ=0.8, α=0.25, Q(S,A)=6, receives reward 3, and observes next-state values 5 and 9. Calculate the Q-learning update and, separately, the SARSA update if the selected next action has value 5.

2. Design an RL method for a safety-critical navigation task. Justify your choices of on-policy or off-policy learning, λ, exploration strategy, constraints, and evaluation metrics.

3. A learning system performs well in training but fails when the environment changes. Analyze at least three possible causes involving policy distribution, bootstrapping, function approximation, or reward design, and propose diagnostic tests.

Multiple Choice Questions with Answers

Question 1

Which feature most directly distinguishes one-step TD learning from Monte Carlo prediction?

A. TD learning requires a complete episode before updating.

B. TD learning bootstraps from an estimate of the next state’s value.

C. TD learning requires a known transition model.

D. TD learning cannot be used in continuing tasks.

Correct Answer: B. TD learning bootstraps from an estimate of the next state’s value.

Question 2

If R_{t+1}=3, γ=0.9, V(S_{t+1})=7, and V(S_t)=5, what is the TD error?

A. 2.0

B. 3.7

C. 4.3

D. 9.3

Correct Answer: C. 4.3

Question 3

Which algorithm uses the action actually selected at the next state in its standard one-step target?

A. SARSA

B. Q-learning

C. Dynamic programming

D. Greedy Monte Carlo control

Correct Answer: A. SARSA

Question 4

What makes Q-learning off-policy?

A. It never uses sampled rewards.

B. It evaluates the behavior policy exactly.

C. It uses a greedy target even when behavior is exploratory.

D. It requires a model of the environment.

Correct Answer: C. It uses a greedy target even when behavior is exploratory.

Question 5

Expected SARSA differs from SARSA because Expected SARSA:

A. does not use rewards

B. averages next-action values under a policy

C. always uses a Monte Carlo return

D. cannot perform control

Correct Answer: B. averages next-action values under a policy

Question 6

Given γ=0.9, rewards 2, −1, and 4, and V(S_{t+3})=5, what is the three-step return?

A. 6.340

B. 7.985

C. 8.900

D. 10.645

Correct Answer: B. 7.985

Question 7

What does λ=0 produce in the standard TD(λ) family?

A. One-step TD(0)

B. Pure dynamic programming

C. An undiscounted Monte Carlo method

D. A method with no bootstrap term

Correct Answer: A. One-step TD(0)

Question 8

Which condition is generally associated with tabular stochastic-approximation convergence?

A. Every state is visited at most once.

B. The learning rate is always exactly one.

C. Relevant state–action pairs receive sufficient exploration.

D. The discount factor must equal zero.

Correct Answer: C. Relevant state–action pairs receive sufficient exploration.

Question 9

Which combination is known as the deadly triad?

A. Sampling, rewards, and discounting

B. Function approximation, bootstrapping, and off-policy learning

C. Planning, exploration, and exploitation

D. Eligibility traces, Monte Carlo, and dynamic programming

Correct Answer: B. Function approximation, bootstrapping, and off-policy learning

Question 10

Why can Q-learning’s maximum operator introduce optimistic bias with noisy estimates?

A. The maximum tends to select positive estimation errors.

B. The maximum always selects the smallest reward.

C. The maximum removes all sampling variation.

D. The maximum prevents exploration entirely.

Correct Answer: A. The maximum tends to select positive estimation errors.