Temporal Difference Learning

TD learning combines the model-free nature of Monte Carlo with the bootstrapping of dynamic programming.

TD(0) update:

• $R_{t+1} + \gamma V(S_{t+1})$ = TD target (estimated return using current value estimate)
• $R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ = TD error $\delta_t$ (surprise: how much better/worse than expected)
• $\alpha$ = learning rate

Key insight: TD bootstraps — uses the current estimate $V(S_{t+1})$ instead of waiting for the full return. This introduces some bias but reduces variance compared to MC.

Advantages over MC:

• Can learn from incomplete episodes (online, step-by-step)
• Lower variance → faster convergence in practice
• Works in continuing (non-episodic) tasks

TD(λ): blends MC and TD(0) via eligibility traces. $\lambda = 0$ is pure TD; $\lambda = 1$ is MC. The trace decays by $\gamma\lambda$ each step, giving recent states more credit.

The TD error is everywhere in RL:

• Q-Learning and SARSA use TD updates for Q-values
• GAE uses discounted sums of TD errors
• Actor-Critic Methods use TD error as the critic's training signal

See also: Monte Carlo Methods in RL, Q-Learning, SARSA