Learning to Predict Independent of Span

By Hado van Hasselt, Richard S. Sutton. 2015

20 citations recorded by the source corpus.

We consider how to learn multi-step predictions efficiently. Conventional algorithms wait until observing actual outcomes before performing the computations to update their predictions. If predictions are made at a high rate or span over a large amount of time, substantial computation can be required to store all relevant observations and to update all predictions when the outcome is finally observed. We show that the exact same predictions can be learned in a much more computationally congenial way, with uniform per-step computation that does not depend on the span of the predictions. We apply this idea to various settings of increasing generality, repeatedly adding desired properties and each time deriving an equivalent span-independent algorithm for the conventional algorithm that satisfies these desiderata. Interestingly, along the way several known algorithmic constructs emerge spontaneously from our derivations, including dutch eligibility traces, temporal difference errors, and averaging. This allows us to link these constructs one-to-one to the corresponding desiderata, unambiguously connecting the `how' to the `why'. Each step, we make sure that the derived algorithm subsumes the previous algorithms, thereby retaining their properties. Ultimately we arrive at a single general temporal-difference algorithm that is applicable to the full setting of reinforcement learning.

Subfields: Artificial Intelligence, Management Science and Operations Research, Natural Language Processing, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Hado van Hasselt
2. A. Mahmood
3. Matteo Hessel
4. John Aslanides
5. Sergey Levine
6. Richard S. Sutton
7. Pieter Abbeel
8. David Silver

In Management Science and Operations Research

1. Hado van Hasselt
2. A. Mahmood
3. Matteo Hessel
4. John Aslanides
5. Patrick M. Pilarski
6. Richard S. Sutton
7. Harm van Seijen
8. Marlos C. Machado

In Natural Language Processing

1. Matteo Hessel
2. John Aslanides
3. Hado van Hasselt
4. Richard S. Sutton
5. Harm van Seijen
6. A. Mahmood

In Statistical Learning Theory

1. A. Mahmood
2. Richard S. Sutton
3. Matteo Hessel
4. John Aslanides
5. Hado van Hasselt
6. Harm van Seijen
7. Marlos C. Machado
8. Huizhen Yu

Citations in the corpus

• When to use parametric models in reinforcement learning? (2019, methodology): “Second, we could rely less on bootstrapping by using multi-step returns [Sutton, 1988, van Hasselt and Sutton, 2015, Sutton and Barto, 2018].”
• True Online Temporal-Difference Learning (2015, background): “Recently, Mahmood & Sutton (2015) extended this theorem further by proving equivalence between an even more general forward view and backward view.”