Contributions
- Introduced the Temporal Difference (TD) learning family of algorithms: learning predictions by bootstrapping from later predictions rather than waiting for final outcomes
- Proved that TD methods converge for linear function approximators under certain conditions
- Unified prior work (Samuel’s checkers, Widrow-Hoff rule, Rescorla-Wagner animal learning model) as special cases of TD(λ)
- Proposed the eligibility trace mechanism (λ parameter) bridging one-step TD(0) and Monte Carlo methods
Methodology
TD(λ) updates predictions online after each observation:
V(s_t) ← V(s_t) + α[r_{t+1} + γV(s_{t+1}) − V(s_t)] · e_t
where e_t is the eligibility trace decaying by λ at each step. The key insight: the prediction error — the difference between successive estimates — is a training signal without waiting for the episode to end. At λ=1, TD(λ) is equivalent to Monte Carlo (using actual returns); at λ=0, it is pure one-step bootstrapping.
The paper applies TD(λ) to a multi-step prediction task (a random walk) and demonstrates superior sample efficiency over supervised methods.
Results
- TD(0) and TD(0.3) outperform the Widrow-Hoff supervised method in mean squared error on the random walk benchmark across a range of learning rates
- Showed that online incremental updates are more efficient than batch updates for sequential prediction
- Demonstrated that temporal difference errors — not final outcomes — are sufficient to drive learning
Limitations
- Theoretical analysis confined to linear function approximators and finite Markov chains; convergence not guaranteed with nonlinear approximators (neural networks)
- Paper addresses prediction only, not control (choosing actions) — the control extension came with Q-learning (Watkins 1992)
- Practical convergence can be slow with large λ and high-variance environments