Temporal-Difference Learning Methods

Temporal-difference learning methods address a central problem in finite Markov decision problems: how can an agent improve its estimates while experience is being generated? The distinctive setting here is off-policy learning. One policy collects the experience, while another policy is the one being learned.

The policies need not be the same. The behavior policy determines what the agent actually experiences, while the target policy determines what the learner wants to evaluate or improve. The policy mismatch is therefore not an incidental detail: it is the defining feature that makes the learning off-policy.

An n-step method does not restrict its learning information to only the next step. The number n describes how far ahead the method looks before forming that information. As n grows, the method connects the current point with events farther along the trajectory or plan.

The n-step idea applies both to learning and to planning. In either use, the method adds a look-ahead of n steps instead of relying only on the immediate next step. In the off-policy setting, this longer look-ahead must be combined with a way to handle the difference between the behavior and target policies.

Once an n-step method uses experience from the behavior policy, it must address the fact that the target policy may be different. The source describes two approaches: importance sampling and tree backups.

Importance sampling handles the mismatch through experience reweighting. The influence of an observed experience is changed according to how likely that experience is under the target policy. Tree backups take a different route. They extend the idea of Q-learning to multiple steps when the target policy is stochastic, using the branching possibilities rather than relying on importance sampling.

Importance sampling can become high variance because it reweights experience to account for the target policy. Across an n-step look-ahead, the adjustment concerns several steps of experience. As more stepwise likelihood adjustments accumulate, the resulting influence can vary greatly from one trajectory to another.

The important practical lesson is not that importance sampling fails, but that its correction can be noisy. A long n-step sequence creates more opportunities for the reweighting to differ across experiences. That is why the source identifies high variance as a weakness of the approach.

Tree backups can use an n-step horizon while still having only a short effective bootstrap. The distinction is between the formal distance n and the part of the backup that contributes most strongly to the resulting estimate. A large n says that the method can look far ahead; it does not say that every step in that horizon has equal practical influence.

This is why n and effective bootstrap should not be treated as synonyms. The tree backup can represent a multi-step extension over a long horizon, yet the update's effective bootstrap may remain concentrated near the current point. The source presents this as an important limitation to recognize when interpreting what a large n accomplishes.

Temporal-difference learning is one of three broad method classes considered here for solving finite Markov decision problems. The most useful comparison asks what information a method requires and when it can make progress.

In this comparison, requiring no model means that the method does not depend on being supplied with a complete and accurate model of the environment. Fully incremental computation means that learning can make progress step by step rather than waiting for a complete outcome before progressing.