Temporal-difference learning

Temporal-difference (TD) learning is a family of methods that learn value estimates from incomplete episodes by updating each estimate toward the observed reward plus the current estimate of the next state's value. It combines the sampling of Monte Carlo methods with the bootstrapping of dynamic programming.

The TD(0) update

After observing a transition $(S_t,R_{t+1},S_{t+1})$, TD(0) moves the value estimate a step of size $\alpha$ toward a one-step target:

The bracketed term is the TD error. The target $R_{t+1}+\gamma V(S_{t+1})$ uses the agent's own estimate of the future, which is what "bootstrapping" means. Learning can happen after every step, in continuing tasks with no episodes at all.

TD vs Monte Carlo

A Monte Carlo target is the full sampled return: unbiased, but noisy because it sums many random rewards. A TD target depends on one random reward and one estimate, so it has much lower variance but is biased while the estimate is wrong. In a seeded simulation of the classic five-state random walk (200 runs, 100 episodes each, values initialised to 0.5), TD(0) with $\alpha =0.05$ reached a root-mean-square value error of 0.034, while the best constant-step Monte Carlo setting we tried ($\alpha =0.02$) reached 0.082. That pattern, TD learning faster on Markov problems, is typical, though not guaranteed.

The TD family

• n-step TD uses $n$ real rewards before bootstrapping, trading bias for variance.
• TD($\lambda$) averages all n-step targets with weights $(1-\lambda ){\lambda }^{n-1}$; $\lambda =0$ is TD(0) and $\lambda =1$ recovers Monte Carlo. Eligibility traces implement it online.
• Control methods: SARSA (on-policy) and Q-learning (off-policy) apply the same idea to action values.

Why it matters

TD learning is the engine inside most practical RL: critics in actor-critic methods, deep Q-networks and value heads in language-model RL are all trained on TD-style targets. Its weakness is the flip side of its strength. Bootstrapping propagates errors, and TD with function approximation and off-policy data can diverge, which is why target networks, replay ratios and careful step sizes matter in deep RL.

Related terms

• TD error
• Monte Carlo methods (RL)
• Value function
• Q-learning
• Bellman equation
• Generalized advantage estimation (GAE)

Sources

1. Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction (2nd edition), 2018. incompleteideas.net
2. Richard S. Sutton. Learning to predict by the methods of temporal differences, 1988. doi.org