Learning to predict by the methods of temporal differences

The problem the paper addressed

Supervised learning in its standard form learns from examples in which the correct answer is already available. Sutton's central argument in this paper is that most problems to which supervised learning is currently applied are really prediction problems of the sort to which temporal-difference methods can be applied to advantage ^[1]. In a prediction problem, the quantity of interest is not known at the moment the estimate has to be made; it becomes known only later, or arrives in a form that cannot be used directly as a training target.

How the methods work

Temporal-difference methods are incremental: they keep a running estimate and revise it after each new observation, rather than collecting a batch of data and fitting a model once. What distinguishes them is how they assign credit. Conventional methods treat the error as the difference between the prediction and the actual outcome. Temporal-difference methods instead use the difference between temporally successive predictions ^[1].

A small example makes the idea concrete. Suppose on Thursday you estimate the chance of rain on Saturday at 0.6. On Friday, with more information in hand, you estimate it again at 0.8. The Saturday outcome is still unknown, but the change between Thursday's and Friday's estimates already carries information: Friday's estimate was made with more knowledge and is therefore the better guess. A temporal-difference method moves Thursday's estimate toward Friday's before any outcome exists, and the size of that move is the correction signal. The final outcome, when it comes, is only one of many such signals along the way.

The paper presents these procedures as a class rather than a single algorithm, and relates the class formally to supervised-learning methods ^[1].

Results

The paper proves convergence and optimality of temporal-difference methods for special cases ^[1]. It also gives a comparison on practical grounds: for most real-world prediction problems, temporal-difference methods require less memory and less peak computation than conventional methods, and they produce more accurate predictions ^[1]. This economy follows from the incremental nature of the update — each observation can be used as it arrives, without holding a long record of observations until the outcome is known.

Why it mattered

Methods of this kind had appeared before, but in scattered and ad hoc forms: in Samuel's checker player, in Holland's bucket brigade, and in the author's own Adaptive Heuristic Critic. They had remained poorly understood ^[1]. Each was a working piece of engineering without a common account of what it was doing or why it should work. The paper supplied that account: a single description covering the earlier schemes, an analysis of when the approach converges, and a direct comparison with the supervised learning that most practitioners were then using.

The paper appeared as "Learning to predict by the methods of temporal differences" in Machine Learning, volume 3, pages 9–44, in August 1988, when Sutton was at GTE Laboratories ^[1].

Later influence

The family of methods introduced in the paper came to be known as the TD algorithms. Tesauro's 1992 paper refers to them as "Sutton's TD(lambda) algorithm" ^[2], a name that shows how the work had settled into the literature as a standard reference point: a named family of algorithms with a known analysis behind it, rather than a collection of separate tricks.