Temporal-Difference Learning

Dynamic Programming needed \(P\) and a full sweep of \(S\). Real agents have neither. Temporal-difference learning is the practical middle path: interact, observe \((s,a,r,s')\), and apply a sample Bellman backup.

Almost every value-based deep RL method — DQN, Rainbow, the critic in SAC — is a neural approximation of ideas in this chapter. Actor–critic methods reuse the same \(\delta_t\) as an advantage signal. If DP was “Bellman with a model,” TD is “Bellman with a trajectory.”

All three methods target the same fixed point \(V^{\pi}\) (or \(Q^{\pi}\)/\(Q^*\)). They differ in how they form the target in the incremental update

DP

Target \(=\mathbb{E}_\pi[r+\gamma V(s')]\). Full backup, needs \(P\). No sampling.

MC

Target \(=G_t\). Unbiased sample of return. Wait until episode ends. High variance.

TD

Target \(=r_{t+1}+\gamma V(s_{t+1})\). One real step + bootstrap. Online, low variance, biased until \(V\) is correct.

Monte Carlo is deferred to a short companion note in your roadmap; here we need only enough MC to place TD on the bias–variance dial.

Prediction means: evaluate a fixed policy \(\pi\) — learn \(V^{\pi}\), not yet control. After taking \(a_t\sim\pi(\cdot\mid s_t)\) and observing \(r_{t+1},s_{t+1}\),

Compare to the DP evaluation backup (Chapter 03): DP replaces \(r_{t+1}+\gamma V(s_{t+1})\) by its expectation under \(P\) and \(\pi\). TD(0) uses a single sample of that expectation. Under standard step-size conditions (Robbins–Monro: \(\sum\alpha_t=\infty\), \(\sum\alpha_t^2<\infty\)) and a tabular representation with adequate exploration of states under \(\pi\), \(V\to V^{\pi}\) with probability 1.

\(\delta_t\) is a one-step prediction error:

• \(\delta_t > 0\): the transition was better than \(V(s_t)\) predicted — raise \(V(s_t)\).
• \(\delta_t < 0\): worse than predicted — lower \(V(s_t)\).
• \(\delta_t = 0\): local consistency with the current table on this sample.

The same scalar reappears as the one-step advantage estimate in actor–critic (\(\hat A_t \approx \delta_t\)) and as the building block of GAE. Treat \(\delta_t\) as a first-class object, not a notational convenience.

Monte Carlo’s target \(G_t\) is unbiased for \(V^{\pi}(s_t)\) but depends on the entire future — high variance. TD’s target is biased whenever \(V\neq V^{\pi}\), yet only one step of environment noise enters — low variance. As \(V\) converges, TD’s bias vanishes. In finite-data regimes, variance usually hurts more, which is why TD often learns faster than MC in practice.

n-step TD and TD(\(\lambda\)) (Section 9) interpolate: longer backups reduce bias toward MC and increase variance.

Control means learning a good policy, typically via \(Q(s,a)\). SARSA updates using the action that was actually taken next:

The name is the tuple \((s_t,a_t,r_{t+1},s_{t+1},a_{t+1})\). Because the target uses \(a_{t+1}\sim\pi(\cdot\mid s_{t+1})\) from the same behavior policy that collected the data, SARSA is on-policy: it learns \(Q^{\pi}\) for the exploring policy you are following (e.g. \(\varepsilon\)-greedy), not for the pure greedy policy.

One word changes everything: \(Q(s_{t+1},a_{t+1})\) becomes \(\max_{a'}Q(s_{t+1},a')\). The target is a sample of the Bellman optimality backup \(\mathcal{T}^*\) (Chapter 02–03), not of \(\mathcal{T}^{\pi}\). You may behave with an exploratory policy while learning about the greedy/optimal policy — that is off-policy learning.

Off-policy control is what later enables experience replay: store transitions and reuse them even after the behavior policy has changed. DQN is Q-learning with a neural \(Q_\theta\), a replay buffer, and a lagged target network.

DP never explores — it backs up every \((s,a)\) from the model. TD only sees what it tries. If the behavior policy is purely greedy from a bad initialization, it may never discover better actions.

Cruder than necessary, but the right conceptual placeholder. Softmax / Boltzmann exploration, UCB-style bonuses, parameter noise, and SAC’s entropy term are later refinements of the same tension: exploit what \(Q\) knows vs visit what it does not.

The n-step target bootstraps after \(n\) real rewards:

\(n=1\) recovers TD(0); \(n\to\infty\) recovers Monte Carlo (episodic). TD(\(\lambda\)) averages all \(n\) with weights proportional to \(\lambda^{n-1}\), implemented efficiently with eligibility traces rather than storing every n-step return. Remember the dial exists; PPO-era methods use a related tool (GAE) on advantages instead of values.

Tabular TD is safe. Trouble starts when you combine:

1. Function approximation (neural nets — not an independent entry per state),
2. Bootstrapping (TD targets),
3. Off-policy sampling (replay / behavior ≠ target).

Together these are the deadly triad: convergence guarantees disappear; training can diverge. That is why DQN needed target networks and replay design care, and part of why trust-region / clipped policy gradients (TRPO/PPO) were developed as stabler alternatives to naive deep bootstrapped updates. Flag now; it will click when we reach deep RL.

Suppose \(Q(s,a)=2.0\), \(\alpha=0.5\), \(\gamma=0.9\), reward \(r=−1\), and next estimates \(Q(s',a_{\mathrm{taken}})=3.0\), \(\max_{a'}Q(s',a')=4.0\).

Same transition, different targets — SARSA pulls toward the action you took; Q-learning pulls toward the best action in the table. That is the entire on-/off-policy distinction in one numerical example.

Next: a dedicated deep dive into Q-learning and Deep Q-Networks — convergence, maximisation bias, experience replay, target networks, Double DQN, and Rainbow. Policy gradients follow after that.