Temporal-Difference (TD) Learning

You are learning the value of states — the "signpost prices" from the Bellman topic — by actually living through episodes. There are two obvious strategies, and each has a fatal annoyance.

Strategy A: Monte-Carlo (MC). Play the whole episode, see the actual total return, then correct every state along the way toward that truth.

• Honest: it uses real rewards, no guesswork. Unbiased.
• Annoying: you must wait until the end. A trading bot cannot learn anything until the account closes. A robot cannot update mid-task. And the full return stacks dozens of random dice rolls on top of each other, so it is a noisy (high-variance) teacher.

Strategy B: Dynamic Programming (DP). Never wait: correct a state using the Bellman backup r + γV(s') — the price of the next state, bootstrapped from what you already believe.

• Fast and smooth: one step, low variance.
• Fatal annoyance: it requires the model P(s'|s,a) — the world's dice, written down. You usually do not have it. And it leans on your own possibly-wrong estimates.

Temporal-Difference learning is the answer: bootstrap, but from one step of real experience.

TD learning updates predictions toward other predictions refined by one step of reality. After transitioning s → s' and observing reward r, compute the TD error:

δ = r + γV(s') − V(s)

Three pieces, read in English:

• V(s) — the prediction you made: "reward-to-come from here is about this much."
• r — what the world actually just paid you.
• γV(s') — your already-learned estimate of everything beyond this step.

So r + γV(s') is the revised prediction: keep the one slice of truth you just got, and bootstrap the rest from the next state's guess. TD nudges V(s) toward that target:

V(s) ← V(s) + αδ = V(s) + α[r + γV(s') − V(s)]

• α (alpha) is the learning rate — how far you move toward the target on each sighting. Same small-step idea as any gradient descent you have seen.

One line of technical dignity: this update is literally gradient descent on half the squared Bellman error from a single sample — TD is the online solver of the Bellman equation. Each transition is one noisy gradient step toward making neighboring signposts agree.

Carry this one analogy (it is Sutton and Barto's own classic): you deliver office drinks and bet on which room the boss will drink in.

• Monte-Carlo you: watch the whole journey — lobby, kitchen, conference room, finally the boss settles in office 314. Only then do you correct all your earlier predictions, using the true final room.
• DP you: sit with a printed map of habits (P) and update predictions by pure reasoning about the corridors. No walking required, but you need the map, and the map may be wrong.
• TD you: at each junction, make your next-room prediction; when you actually arrive at the next room, use that one step of reality to fix the prediction you made one room back.

code
Copy
        lobby ──► kitchen ──► hallway ──► 314
   guess₁   r?     guess₂      guess₃      truth

   TD fix after one step:  adjust guess₁ toward (what happened + guess₂)

The punchline: TD learns a little at every doorway, the way humans do — the flinch when a step surprises you is a TD error. The correction propagates backward through the whole hallway over many deliveries, even though you only ever compared neighbors.

A corridor of states 0 → 1 → 2 → 3 (goal). A fixed policy walks right. The only reward, +1.0, is paid on the step from 2 into 3. Take γ = 0.95, α = 0.1, and all values start at 0. Watch the price signal crawl backward like ripples:

• First pass, at state 2: δ = 1.0 + 0.95×V(3) − V(2) = 1.0 + 0 − 0 = 1.0, and V(2) ← 0 + 0.1×1.0 = 0.1.
• State 1 on that same pass saw V(2)=0, so it got nothing yet. But on the next episode, at state 1: δ = 0 + 0.95×0.1 − 0 ≈ 0.095, so V(1) finally rises.
• Then state 0 notices state 1, and so on.

After 2000 episodes the code settles near the true discounted values: V ≈ {0: 0.903, 1: 0.95, 2: 1.0, 3: 0}. Check the math: the reward 1.0 two steps away is worth 0.95 × 0.95 ≈ 0.9025 from state 0 — TD rediscovered the discount, one doorway at a time, with no model and no waiting.

import random
gamma, alpha = 0.95, 0.1
V = {0:0.0, 1:0.0, 2:0.0, 3:0.0}          # V[3]=0 is the terminal goal reward base

for episode in range(2000):
    s = 0
    while s != 3:
        a = 1                                # always move right (fixed policy)
        r = 1.0 if s == 2 else 0.0           # reward only on the step into goal
        s2 = s + a
        delta = r + gamma * V[s2] - V[s]     # TD error
        V[s] += alpha * delta                # TD(0) update
        s = s2
print({k: round(v,3) for k,v in V.items()})

TD is a prediction engine, but you can point it at action-values to get control (a policy). The general one-step TD update for Q is:

Q(s,a) ← Q(s,a) + α[r + γ Q(s',a') − Q(s,a)]

Now the only question that matters: what is a'? This single decision defines the algorithm:

• SARSA (on-policy TD control): a' is the action the current policy will actually take next (e.g., ε-greedy — possibly a silly exploratory one). Target = r + γQ(s', a_next). Conservative and safe: it prices the road as you actually walk it.
• Q-learning (off-policy TD control): a' = argmax_{a'} Q(s',a'), ignoring what you will really do. Target = r + γ max_{a'} Q(s',a'). Full treatment in topic 201.

And a nice memory aid: the name SARSA literally lists the tuple driving the update — (S, A, R, S', A'): current state, action taken, reward seen, next state, next action actually chosen.

One-step TD is biased (it trusts a possibly-wrong V(s')) but low-variance; Monte-Carlo is unbiased but high-variance. TD(λ) interpolates between them using eligibility traces e_t — a fading memory of which states you recently visited:

e_t = γλ e_{t−1} + 1{S_t = s}, V(s) += αδ_t e_t

When a TD error δ fires now, every recently-visited square shares the blame — in proportion to its trace (how recently, how often). Credit assignment becomes a decaying spotlight instead of a single doorway.

• λ = 0: only the state you are in has a trace — pure one-step TD(0).
• λ = 1: traces never decay within the episode — equivalent to Monte-Carlo.
• 0 < λ < 1: an n-step blend that often learns dramatically faster than either extreme.

The finite-horizon compromise TD(λ) approximates is the n-step return:

G_t^(n) = R_{t+1} + γR_{t+2} + … + γ^(n−1) R_{t+n} + γⁿ V(S_{t+n})

— n steps of real rewards, then bootstrap. That object is the direct ancestor of GAE (Generalized Advantage Estimation) used by PPO: same dial, now controlling how far advantage credit reaches back.

TD is the reason RL works without a model and without waiting.

• A stock-trading TD agent updates the value of a position today from the next tick — it never waits for the account to close.
• AlphaGo's value network was trained with TD-style self-play backups: every board position nudged toward r + γV(next position) across millions of games, so positional judgment improved each move, not just at checkmate.
• SARSA, Q-learning, DQN, TD3, and the critics inside A2C/PPO are all, at their core, iterating a sampled Bellman/TD update — the same signpost-consistency step wearing different hats.

One more unifying thought: TD error δ is the Bellman error sampled once (topic 199). When your brain, or a critic network, fires "that was better/worse than expected" — that surprise signal is a TD error. Sutton introduced TD learning partly as a model of exactly this kind of reward-prediction learning.