📐 Concept diagram

23-05 — Temporal Difference Learning

Phase: 23 — Reinforcement Learning Mathematics Subject: 23-05 Prerequisites: 23-04 — Monte Carlo Methods, 23-02 — Bellman Equations Next subject: 23-06 — Q-Learning

Learning Objectives

By the end of this subject, you will be able to:

1. Derive the TD(0) update rule from the Bellman equation and explain what "bootstrapping" means
2. Compare and contrast TD learning with Monte Carlo and Dynamic Programming
3. Define the TD error and explain its role as a learning signal
4. Implement SARSA for on-policy TD control and analyze its convergence properties
5. Understand the bias-variance trade-off between TD and MC methods

Core Content

The Central Idea of Temporal Difference Learning

Temporal Difference (TD) learning combines two ideas: 1. From Monte Carlo: Learn directly from experience without a model 2. From Dynamic Programming: Update estimates based on other learned estimates (bootstrapping)

The key insight: instead of waiting until the end of an episode to compute $G_t$ (like MC), TD updates after every step using the immediate reward plus the current estimate of the next state's value.

⚠️ CRITICAL: TD is arguably the most important idea in reinforcement learning. It enables online, incremental learning — the agent learns at every time step without waiting for episodes to complete.

TD(0) — The Simplest TD Algorithm

The TD(0) update for state-value estimation:

$$V(S_t) \leftarrow V(S_t) + \alpha \big[\underbrace{R_{t+1} + \gamma V(S_{t+1})}{\text{TD target}} - \underbrace{V(S_t)}{\text{current estimate}}\big]$$

• $R_{t+1} + \gamma V(S_{t+1})$ is the TD target — a one-step estimate of the return
• $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ is the TD error — the difference between the estimated return and the current estimate
• $\alpha \in (0, 1]$ is the learning rate (step-size parameter)

Derivation from the Bellman equation:

From 23-02: $V^\pi(s) = \mathbb{E}\pi[R{t+1} + \gamma V^\pi(S_{t+1}) \mid S_t = s]$

TD(0) uses a sample of this expectation as the target and moves the estimate toward it via stochastic approximation:

$$V(S_t) \leftarrow V(S_t) + \alpha[\text{sample} - V(S_t)]$$

where $\text{sample} = R_{t+1} + \gamma V(S_{t+1})$.

Comparison: TD vs. MC vs. DP

The bias-variance trade-off: MC has zero bias but high variance (complete returns compound many random events). TD has some bias (it bootstraps from imperfect estimates) but much lower variance. In practice, TD often converges faster than MC.

The TD Error as a Learning Signal

The TD error $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ has an important property — it can be related to the full return:

$$G_t - V(S_t) = \sum_{k=0}^{\infty} \gamma^k \delta_{t+k}$$

Proof:

$G_t - V(S_t) = (R_{t+1} + \gamma G_{t+1}) - V(S_t)$ $= R_{t+1} + \gamma V(S_{t+1}) - V(S_t) + \gamma(G_{t+1} - V(S_{t+1}))$ $= \delta_t + \gamma(G_{t+1} - V(S_{t+1}))$ $= \delta_t + \gamma \delta_{t+1} + \gamma^2(G_{t+2} - V(S_{t+2})) = \cdots = \sum_{k=0}^{\infty} \gamma^k \delta_{t+k}$

This shows that TD errors accumulate over time to form the full MC error. If $V = V^\pi$, the expected TD error is zero: $\mathbb{E}_\pi[\delta_t \mid S_t = s] = 0$.

TD(λ) — The Bridge Between TD and MC

The λ-return $G_t^\lambda$ is a weighted average of $n$-step returns, exponentially weighted by $\lambda \in [0,1]$:

$$G_t^\lambda = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n}$$

where $G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})$.

• $\lambda = 0$: $G_t^0 = G_{t:1} = R_{t+1} + \gamma V(S_{t+1})$ — TD(0)
• $\lambda = 1$: $G_t^1 = G_t$ — Monte Carlo (complete return)

TD(λ) smoothly interpolates between TD(0) and MC.

SARSA — On-Policy TD Control

SARSA (State-Action-Reward-State-Action) learns $Q(s,a)$ on-policy using TD:

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

The name comes from the transition quintuple: $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$.

Algorithm:

1. Initialize $Q(s,a)$ arbitrarily
2. For each episode:
3. Initialize $S$, choose $A$ from $S$ using policy derived from $Q$ (e.g., $\varepsilon$-greedy)
4. For each step:
   • Take action $A$, observe $R, S'$
   • Choose $A'$ from $S'$ using policy derived from $Q$ (e.g., $\varepsilon$-greedy)
   • $Q(S,A) \leftarrow Q(S,A) + \alpha[R + \gamma Q(S', A') - Q(S,A)]$
   • $S \leftarrow S'$, $A \leftarrow A'$
5. Until $S$ is terminal

SARSA is on-policy — the policy used to select $A'$ (in the update target) is the same policy used to generate behavior. This matters: if the behavior policy explores (e.g., $\varepsilon$-greedy), SARSA learns values for that exploratory policy, learning to account for the exploration penalty.

⚠️ CRITICAL — The Cliff Walking insight: In the classic cliff-walking problem, SARSA learns a safer path that stays away from the cliff edge because it accounts for the possibility of random exploratory moves sending the agent off the cliff. Q-learning (23-06), being off-policy, learns the optimal path right along the edge — but may actually fall off more during learning because it doesn't account for exploration noise.

Convergence of TD

For tabular TD(0) with a fixed policy $\pi$, TD converges to $V^\pi$ with probability 1 if: 1. The step sizes satisfy the Robbins-Monro conditions: $\sum_{t=1}^\infty \alpha_t = \infty$ and $\sum_{t=1}^\infty \alpha_t^2 < \infty$ 2. All states are visited infinitely often

Example valid step-size: $\alpha_t = 1/t$, or constant $\alpha$ with eventual averaging.

TD converges faster than MC in many practical settings because it exploits the Markov property to reduce variance, even though it introduces some bias.

Key Terms

• Bias
• Handles continuing tasks
• Requires model
• TD error
• TD target
• Update timing
• Uses bootstrapping
• Variance

Worked Examples

Example 1: TD(0) Update Step

$V = [0, 0, 0]$ for 3 states. Transition: $S_t = s_1, A_t, R_{t+1} = 5, S_{t+1} = s_2$. Current $V(s_1) = 10$, $V(s_2) = 3$. $\alpha = 0.1$, $\gamma = 0.9$. Compute the TD update.

Solution:

$\delta_t = 5 + 0.9(3) - 10 = 5 + 2.7 - 10 = -2.3$ $V(s_1) \leftarrow 10 + 0.1(-2.3) = 10 - 0.23 = 9.77$

The negative TD error indicates that $V(s_1)$ was too high — the observed reward (5) plus discounted next-state value (2.7) is less than the current estimate (10), so we reduce it.

Example 2: SARSA vs. the Cliff

Cliff walking grid: agent starts at bottom-left, goal is bottom-right. Cliff along the bottom row (except start and goal). Falling on cliff gives reward $-100$ and resets to start. Each step gives reward $-1$.

With $\varepsilon$-greedy ($\varepsilon = 0.1$): - The optimal path hugs the cliff edge — shortest path. - SARSA learns a path further from the cliff because the $\varepsilon$-greedy action selection means there's a 10% chance of a random move near the cliff, which would be catastrophic. - SARSA's Q-values account for the actual behavior policy's exploration, making it learn safer but longer paths.

Example 3: $n$-step Return Calculation

Trajectory: $R_1=1, R_2=2, R_3=3, R_4=4$, then terminal. $V = [0, 0, 0]$ for all states. $\gamma = 1$. Compute $G_{0:1}$, $G_{0:2}$, $G_{0:3}$, and the full return $G_0$.

Solution:

$G_{0:1} = R_1 + \gamma V(S_1) = 1 + 0 = 1$ $G_{0:2} = R_1 + \gamma R_2 + \gamma^2 V(S_2) = 1 + 2 + 0 = 3$ $G_{0:3} = R_1 + \gamma R_2 + \gamma^2 R_3 + \gamma^3 V(S_3) = 1 + 2 + 3 + 0 = 6$ $G_0 = R_1 + R_2 + R_3 + R_4 = 1 + 2 + 3 + 4 = 10$

Practice Problems

Problem 1: Derive the relationship $\sum_{k=0}^\infty \gamma^k \delta_{t+k} = G_t - V(S_t)$.

Problem 2: Show that under the true value function $V^\pi$, the expected TD error is zero: $\mathbb{E}_\pi[\delta_t \mid S_t = s] = 0$.

Problem 3: Explain why TD learns faster than MC in a random walk problem. (Hint: consider how many random transitions affect each update.)

Problem 4: In SARSA, if the policy is pure greedy (no exploration), what happens to learning? Why does $\varepsilon$-greedy fix this?

Problem 5: Compute the λ-return $G_0^\lambda$ for $\lambda = 0.5$ using the returns from Example 3, with $V = [0, 0, 0]$ for all states. Compare to $G_{0:1}$, $G_{0:2}$, and full $G_0$.

Summary

Key takeaways:

• TD learning bootstraps — it updates estimates using other estimates ($R_{t+1} + \gamma V(S_{t+1})$), enabling online step-by-step learning
• The TD error $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ is the fundamental learning signal; expected to be zero at the true value function
• TD occupies the middle ground: lower variance than MC (single-step randomness) but some bias from bootstrapping
• SARSA is on-policy TD control — learns Q-values for the actual behavior policy, naturally accounting for exploration risk
• TD(λ) interpolates between TD(0) (λ=0) and MC (λ=1) via exponentially weighted n-step returns
• TD converges under Robbins-Monro step-size conditions with sufficient exploration

Quiz

Question 1: The TD(0) update uses which of the following as the target?

A. The complete return $G_t$ B. $R_{t+1} + \gamma V(S_{t+1})$ C. $\max_a Q(S_{t+1}, a)$ D. $R_{t+1}$ only

Correct Answer: B

Question 2: What is the primary advantage of TD over MC?

A. TD is unbiased B. TD can learn online without waiting for episode completion C. TD requires a model of the environment D. TD always converges faster mathematically

Correct Answer: B

Question 3: In SARSA, what does the second 'A' in the name stand for?

A. The action taken at the current state B. The action that will be taken at the next state, according to the current policy C. The optimal action at the next state D. An arbitrary action

Correct Answer: B

Question 4: What does $\lambda = 0$ in TD(λ) correspond to?

A. Monte Carlo (complete returns) B. TD(0) — one-step bootstrapping C. Dynamic programming D. SARSA

Correct Answer: B

Question 5: Why might SARSA learn a different policy than Q-learning in the same environment?

A. SARSA uses a different discount factor B. SARSA is on-policy — it learns values for the behavior policy including exploration C. SARSA doesn't use value functions D. SARSA requires a model

Correct Answer: B

Next Steps

Next up: 23-06 — Q-Learning — where you'll learn the off-policy TD control algorithm that directly approximates $$Q^*$$ and forms the basis for deep reinforcement learning.

Pitfalls

1. Thinking TD is the same as MC because both are model-free. TD uses bootstrapping (updates from $$R_{t+1} + \gamma V(S_{t+1})$$), while MC uses complete returns. This seemingly small difference has major consequences: TD exploits the Markov property for lower variance but introduces bias; MC is unbiased but has high variance. The choice depends on your problem's structure.

2. Misunderstanding the SARSA vs. Q-learning distinction. SARSA uses $$Q(S_{t+1}, A_{t+1})$$ where $$A_{t+1}$$ is the action actually taken by the behavior policy. Q-learning uses $$\max_{a'} Q(S_{t+1}, a')$$. This single difference makes SARSA on-policy (learns values for the exploratory policy) and Q-learning off-policy (learns optimal values regardless of exploration).

3. Setting constant α and expecting exact convergence. The Robbins-Monro conditions ($$\sum \alpha_t = \infty$$, $$\sum \alpha_t^2 < \infty$$) require decaying learning rates. Constant α causes persistent oscillations around the true value. In non-stationary environments constant α is acceptable (it tracks changes), but for stationary problems, decay α or average final estimates.

4. Using λ = 1 in TD(λ) on continuing tasks. λ = 1 gives the full Monte Carlo return $$G_t$$, which requires episode termination. On continuing tasks, this is undefined. Use λ < 1 for continuing environments or truncate with an artificial horizon.

Q8: The expected TD error $$\mathbb{E}_\pi[\delta_t \mid S_t = s]$$ equals zero when:

A) The learning rate is zero B) $$V = V^\pi$$ (the true value function) C) All rewards are positive D) The policy is deterministic