Skip to main content

View as Markdown

Page content converted to Markdown. Use the original page link at the end to explore interactive graphics.

5. Temporal-Difference Methods

Temporal-difference (TD) methods combine ideas from Monte Carlo methods and dynamic programming. They update estimates at each step without waiting for an episode to finish.

For unfamiliar symbols, consult the terms and formulas quick reference. Expand the plain-language explanations beside this chapter's formulas without leaving the page.

Embodied AI perspective: TD learning is the core update mechanism behind many modern deep RL algorithms, including DQN's Q updates and DDPG/SAC's Critic updates. It lets a robot learn incrementally while interacting with its environment.

This chapter follows the MDP reward-index convention: executing produces and leads to ; an observed transition is . In numerical updates, takes its observed value . The code variables r and reward also denote the reward from this transition.

5.1 Temporal-difference estimation​

Recall the Monte Carlo update in :

The complete return starts at state and ends at the terminal state:

Monte Carlo estimation can update values incrementally across episodes, but it must first wait for an episode to finish to obtain its complete return. This can make learning slow for long episodes and unsuitable for tasks without a clear endpoint.

Temporal-difference (TD) estimation instead combines the immediate reward with the estimated value of the next state:

In plain language: what does one TD update calculate?

Suppose the old estimate is , the observed reward is , the next-state estimate is , the discount factor is , and the learning rate is :

  1. Calculate the target: , the immediate reward plus an estimate of the future.
  2. Calculate the error: . This target is above the old estimate.
  3. Move partway toward it: .

means to store the updated value, not that the old and new values are equal. If the next state is truly terminal, set its continuation value to ; the same other numbers give .

Quick reference: bootstrapping, TD error, and learning rate.

The quantity is the TD target, an estimate of the current return . Its difference from the current value estimate is the TD error:

Updating an estimate using another current estimate is called bootstrapping. TD combines Monte Carlo's ability to learn without transition probabilities with dynamic programming's use of existing value estimates. It can therefore update before a complete return is available.

If executing leads to a terminal , there is no continuation return, so set . The reward still updates the state from which the action was taken:

5.2 A numerical example​

Consider the grid world from the Monte Carlo chapter. The agent follows a random policy, starting at the upper-left corner and finishing at the lower-right corner. Actions and move right or down. The positions are states , with and terminal state .

The 3×3 grid used to compare Monte Carlo and TD estimation

A 3×3 grid world

Each step incurs reward . Entering the pit at adds ; entering the puddle at adds . With , estimate the state values .

The following Python example compares TD and Monte Carlo estimation:

Example 1: Comparing TD and Monte Carlo estimation
import random
from collections import defaultdict
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import time

# ---------- Parameters ----------
gamma = 0.9
alpha = 0.1 # Learning rate (try 0.05–0.2)
episodes = 100000
states = [f"s{i}" for i in range(1, 10)]
terminal = "s9"
start = "s1"

coords = {
"s1": (0,0), "s2": (0,1), "s3": (0,2),
"s4": (1,0), "s5": (1,1), "s6": (1,2),
"s7": (2,0), "s8": (2,1), "s9": (2,2)
}

# ---------- Environment ----------
def legal_actions(s):
r, c = coords[s]
acts = []
if c < 2: acts.append("right")
if r < 2: acts.append("down")
return acts

def step(s, a):
r, c = coords[s]
if a == "right": r2, c2 = r, c + 1
elif a == "down": r2, c2 = r + 1, c
s2 = [k for k, v in coords.items() if v == (r2, c2)][0]
reward = -1.0
if s2 == "s4": reward -= 3.0 # Pit
if s2 == "s5": reward -= 0.5 # Puddle
if s2 == "s9": reward += 1.0 # Goal +1 gives net reward 0
done = (s2 == terminal)
return s2, reward, done

def policy(s):
acts = legal_actions(s)
return random.choice(acts)

def generate_episode():
episode = []
s = start
while True:
if s == terminal:
episode.append((s, None, 0))
break
a = policy(s)
s2, r, done = step(s, a)
episode.append((s, a, r))
s = s2
return episode

# ---------- First-Visit Monte Carlo ----------
def first_visit_mc(num_episodes=episodes, gamma=0.9):
V = defaultdict(float)
N = defaultdict(int)
for _ in range(num_episodes):
episode = generate_episode()
G = 0
visited = set()
for s, a, r in reversed(episode):
G = gamma * G + r
if s not in visited:
visited.add(s)
N[s] += 1
V[s] += (G - V[s]) / N[s]
return V

# ---------- TD(0) prediction ----------
def td0_value_prediction(episodes=episodes, alpha=alpha, gamma=gamma, start="s1"):
V = defaultdict(float) # Initialize all values to 0
for _ in range(episodes):
s = start
while s != terminal:
a = policy(s)
s2, r, done = step(s, a)
# TD(0) update
V[s] += alpha * (r + gamma * V[s2] - V[s])
s = s2
return V

s_t = time.time()
V_mc = first_visit_mc()
t_cost_mc = time.time() - s_t
print(f"First-Visit MC time: {t_cost_mc:.2f} seconds")

# ---------- Print results ----------
grid_mc = np.array([[V_mc[f"s{r*3+c+1}"] for c in range(3)] for r in range(3)])
df_mc = pd.DataFrame(grid_mc.round(3),
columns=["col1","col2","col3"],
index=["row1","row2","row3"])
print(df_mc)

s_t = time.time()
V_td0 = td0_value_prediction()
t_cost_td0 = time.time() - s_t

print(f"TD(0) time: {t_cost_td0:.2f} seconds")

grid_td0 = np.array([[V_td0[f"s{r*3+c+1}"] for c in range(3)] for r in range(3)])
df_td0 = pd.DataFrame(grid_td0.round(3),
columns=["col1","col2","col3"],
index=["row1","row2","row3"])
print(df_td0)

An example output is:

First-Visit MC time: 0.57 seconds
col1 col2 col3
row1 -4.43 -2.149 -1.0
row2 -2.15 -1.000 0.0
row3 -1.00 0.000 0.0
TD(0) time: 0.47 seconds
col1 col2 col3
row1 -4.110 -2.216 -1.0
row2 -2.182 -1.000 0.0
row3 -1.000 0.000 0.0

Both methods produce similar values in this example, with TD taking slightly less time. TD updates during an episode, which can improve learning efficiency when complete episodes are expensive to collect. Values and runtimes vary between runs.

5.3 Deriving the TD target​

Where does come from? Recall the Bellman equation:

Under the expectation for a given policy, the complete return can be replaced by an immediate reward plus the discounted next-state value. This motivates the sampled approximation:

Step by step: why is this an approximation, not an equality?

The recursion holds along a single trajectory. Instead of waiting for that trajectory to finish, TD replaces its unavailable with the current estimate . That enables earlier updates but introduces estimation error.

Even the true value is an average return. Suppose the next state's subsequent return is either or with equal probability: its true value is , but a particular trajectory still returns or . The Bellman equation relates the corresponding conditional expectations; it does not make every trajectory's numbers identical.

Quick reference: Bellman equation and expectation.

Substituting this target into the Monte Carlo update gives the TD update. The relation is about expectations, not equality between an individual sampled target and a complete return. A stable policy, sufficient exploration, and repeated updates are important for value estimation. As approaches , the target's conditional expectation approaches .

Insufficient coverage or too few updates can leave estimates unstable. Converging value estimates is also different from finding an optimal policy: prediction evaluates a given policy; control additionally improves it. Before values have converged, the bootstrap term is itself approximate. Learning rates, exploration settings, alternative TD targets, and function approximators all affect practical training behavior.

5.4 n-step temporal difference​

The target bootstraps after one step: TD(0). We can instead collect rewards before bootstrapping:

The first term is the discounted sum of rewards sampled after step . The second uses the estimated value at . Increasing uses more observed rewards and discounts the bootstrap term more strongly; decreasing relies more on the current value estimate and permits earlier updates.

The limiting cases connect TD and Monte Carlo:

For an episodic task, collecting rewards through termination gives the complete Monte Carlo return. Smaller typically means more bootstrap bias and less variance; larger typically reduces that bias while increasing variance and the delay before updating. Thus controls a tradeoff among computation, accuracy, bias, and variance.

5.5 Comparing dynamic programming, Monte Carlo, and TD​

MethodEnvironment modelUpdate timingEstimationMain tradeoffs
Dynamic programmingRequiredDuring value-update sweepsBootstrappingCan converge quickly, but requires a complete environment model
Monte CarloNot requiredAfter an episodeSamplingUnbiased complete-return samples for a fixed policy; requires full episodes and often has high variance
Temporal differenceNot requiredEach interaction stepSampling and bootstrappingTimely, efficient updates with lower variance; bootstrap bias and sensitivity to exploration and learning settings

5.6 Sarsa​

Sarsa is an on-policy TD control algorithm for estimating . Its name refers to the five elements in an update: state , action , reward , next state , and next action .

5.6.1 TD estimation of action values​

The action-value update is analogous to the state-value update:

5.6.2 Sarsa procedure​

Combining the control loop with TD action-value estimation gives the following procedure. See the practice material for complete implementations.

  1. Initialize . Reset the environment to for each episode and select using an -greedy policy.
  2. Starting at , execute and observe and .
  3. If is terminal, update toward and end the episode.
  4. Otherwise, select in using the same policy. Update toward .
  5. Set and repeat steps 2–4, executing the action already selected.

Sarsa updates without waiting for episode completion, using and the next action selected by the same policy. No next action is selected after reaching a terminal state.

5.6.3 Exploration policy​

Sufficient exploration is important for learning values. Sarsa commonly uses an -greedy policy to balance exploration and exploitation: select a currently best action with probability , or a uniformly random action with probability .

The exploration rate is often reduced during training: explore broadly at first, then increasingly exploit what has been learned.

5.7 Q-learning​

Q-learning is an off-policy TD control algorithm. Instead of evaluating the action actually selected at the next state, it uses the highest estimated next-state action value. This lets it learn a greedy target policy while collecting experience with a different behavior policy:

In plain language: how does Q-learning's max differ from Sarsa?

Suppose the next state has two actions with estimates and , and exploration actually selects the action worth . With immediate reward and :

  • Sarsa uses the selected action, giving target .
  • Q-learning uses the highest estimated value, giving target .

Here returns the score ; returns the action that achieves that score. Q-learning's target does not require executing that highest-scoring action next.

Quick reference: on-policy and off-policy, max and argmax.

The procedure is as follows. See the practice material for complete implementations.

  1. Initialize and reset the environment to for each episode.
  2. Starting at , choose and execute using a behavior policy such as -greedy. Observe and .
  3. If is terminal, update toward and end the episode. Otherwise, update toward .
  4. Set and repeat steps 2–3. The maximum in the update target does not depend on the action actually selected next.

Q-learning uses , while Sarsa evaluates the next action sampled by its policy. Q-learning focuses on the greedy policy and can learn aggressively; Sarsa accounts for the exploratory actions it actually takes. Their relative speed and stability depend on the environment and learning settings.

Q-learningSarsa
Policy typeOff-policyOn-policy
Update targetBest estimated next actionNext action actually selected
Learning behaviorOften more aggressiveAccounts for behavior-policy exploration
Typical considerationLearning a greedy policy while exploringEvaluating the consequences of the policy actually executed

5.8 On-policy and off-policy learning​

The distinction concerns the behavior policy, which collects experience, and the target policy, which is evaluated or improved. If they are the same, learning is on-policy; if they differ, learning is off-policy.

For a driving analogy, an on-policy learner evaluates and improves the driving behavior it currently follows. An off-policy learner may evaluate an idealized driving policy while collecting experience under different behavior dictated by traffic or road conditions.

A driving analogy comparing learning from the current policy with learning a different target policy

On-policy and off-policy learning (labels in Chinese)

On-policy methods learn directly from their current behavior. Off-policy methods offer more flexibility to reuse data from other behavior policies, but can face additional stability and convergence challenges.

5.9 Questions​

Are Monte Carlo and TD methods both model-free?

Yes. They learn values or policies from interaction without requiring an explicit model of the environment's dynamics.

What are their respective strengths and weaknesses?

Monte Carlo methods learn directly from complete returns. For a fixed policy, those returns provide unbiased samples, but updates must wait for full episodes and can have high variance. Long or nonterminating episodes are problematic. TD methods learn during interaction, work with both episodic and continuing tasks, and can use function approximation in large state spaces. Bootstrapping introduces bias, and learning rate and exploration settings affect stability. Choose according to the task and the available experience.

What is Q-value overestimation, and how can it be reduced?

Overestimation occurs when learned state or action values exceed their true values because of sampling noise or properties of the learning algorithm. Double Q-learning separates action selection from evaluation to reduce this effect. Prioritized replay, target networks, and exploration strategies also affect data coverage and training stability, although they serve different roles from the direct overestimation correction in Double Q-learning.

How do on-policy and off-policy methods differ?

On-policy methods collect samples with the policy they are learning about. Off-policy methods can collect data with a different behavior policy and use it to improve their target policy.

Why is exploration necessary?

The optimal policy is initially unknown. Following only currently preferred actions can leave useful states and actions unexplored and miss better strategies. Common exploration mechanisms include -greedy policies, softmax sampling, and Gaussian action noise.