Temporal-Difference Learning

## What the update is trying to do We want `V(s)`, an estimate of the expected discounted return from state `s` under the current behaviour. We cannot see that expectation; we can only see experience. TD(0) takes the smallest possible slice of experience — one transition `s -> r, s'` — and uses it to improve the estimate. The reasoning is a consistency requirement. If our estimates were correct, then the value of `s` should equal the immediate reward plus the discounted value of wherever we land. So after observing one transition we can form the **TD target**: ``` target = r + gamma * V(s') ``` and compare it to what we currently believe: ``` delta = r + gamma * V(s') - V(s) # the TD error V(s) = V(s) + alpha * delta # the TD(0) update ``` `gamma` in `[0, 1]` discounts future reward; `alpha` in `(0, 1]` is the step size. If `delta` is positive, the step turned out better than predicted and `V(s)` rises; if negative, it falls; if zero, nothing moves — the estimate was already self-consistent with that transition. ## Reading the pieces **The TD error is a surprise signal.** It is not the prediction error against ground truth — ground truth is never observed — it is the error against a one-step-improved version of the agent's own prediction. Interpreted that way, learning is a long process of removing self-inconsistency from a table of estimates until nothing contradicts anything else. **The step size controls memory.** A constant `alpha` makes the estimate an exponentially weighted average of recent targets, which is what you want in a non-stationary environment. Averaging step sizes that shrink over time (satisfying the usual stochastic-approximation conditions — the sum of step sizes diverges while the sum of their squares converges) are what tabular TD(0) needs to converge to the true value function of the behaviour being followed. **Terminal states have value zero.** When `s'` ends the episode, the target collapses to `r`, which is what anchors the whole table: real reward enters at the terminal edge and propagates backwards through the bootstrapped targets. ## Bootstrapping and why it buys online learning The defining feature is that the target contains an estimate, `V(s')`, rather than only observed quantities. This is **bootstrapping** — building an estimate on top of other estimates. The alternative, Monte-Carlo, waits for the episode to finish and uses the realised return `G` as its target: `V(s) <- V(s) + alpha * [G - V(s)]`. That needs an episode to end, which rules out continuing tasks and delays every update until the end of a possibly very long trajectory. Bootstrapping removes that wait. Sutton's driving-home example is the clearest picture: you leave the office predicting a 30-minute drive, hit unexpected traffic at the first junction, and immediately revise the prediction upward — you do not withhold all learning until you park and know the true duration. Each landmark gives you a new estimate that improves the previous one. The practical consequences are: - **Online, incremental learning.** One transition, one update, constant memory. - **Works in continuing tasks.** No episode boundary required. - **Learns from incomplete sequences.** A truncated or abandoned trajectory still yields useful updates. - **Credit spreads gradually.** Reward information moves back one state per update through the chain of estimates, so with tabular TD(0) a distant reward takes several passes to reach early states. ## The obvious objection Updating an estimate toward a target that contains an estimate sounds circular. Why does it not simply reinforce whatever nonsense the table was initialised with? Because the target is not purely estimate. Each target contains a **real sampled reward**, and the terminal targets contain no bootstrap at all. Real information is injected at every step and, in tabular problems with a fixed policy and a suitable step-size schedule, TD(0) is guaranteed to converge to the true value function. Empirically the bootstrap is a strength rather than a tax: TD-Gammon learned a strong backgammon board evaluation almost entirely from self-play, with each position's value trained against the value of the position that followed it. ## What interviewers listen for Get the direction and the contents right. The target is `r + gamma * V(s')`, **not** `r + gamma * V(s)`, and the update moves `V(s)` a *fraction* `alpha` of the way toward it rather than replacing it. Saying "TD sets the value to the observed reward" or dropping the discount on the bootstrapped term are the two most common wrong answers, and both change what the algorithm converges to.