One-step Temporal-Difference Learning

The Endpoint Question

The most useful way to understand one-step temporal-difference learning is to start with the two endpoint settings of the λ-return. The value of λ determines which return results when the λ-return is simplified. At λ = 1, the result is the conventional return, which leads to the Monte Carlo algorithm. At λ = 0, the result is the one-step return, written as G (1) t, which leads to the one-step temporal-difference method.

Reading λ at the Endpoints

λ is a parameter of the λ-return. Its role becomes clearest at the endpoints. When λ = 1, the λ-return simplifies to the conventional return. Backing up according to that return is identified as the Monte Carlo algorithm. When λ = 0, the λ-return simplifies to the one-step return G (1) t. Backing up according to that return is identified as the one-step TD method.

Classifying a Simplified Return

Incremental Updates in TD Learning

Temporal-difference learning is a class of methods for solving finite Markov decision problems. Its defining computational feature is fully incremental, step-by-step progress. In this context, fully incremental means that learning can proceed as experience unfolds rather than being designed around waiting for a complete outcome before making progress.

For one-step temporal-difference learning, the important mental model is a repeated transition through experience: an observed state, a reward, and a next state provide information for progress, and the value estimate can change step by step. The defining point is not a particular speed or a universal superiority over other methods. The defining point is that computation is incremental rather than dependent on completing an entire episode before progress can occur.

Learning Without a Model

The no-model property and the incremental property are separate ideas that work together. No model describes what the method needs from the environment. Fully incremental describes when the method can make progress. Temporal-difference learning is distinguished by having both properties: it requires no model and can proceed step by step.

Three Method Classes

Dynamic programming, Monte Carlo methods, and temporal-difference learning all address finite Markov decision problems, but they make different trade-offs. Dynamic programming requires a complete and accurate model. Monte Carlo methods do not require a model and are conceptually simple, but they are not well suited to step-by-step incremental computation. Temporal-difference methods require no model and are fully incremental, although they are more complex to analyze.

Mistakes to Avoid

• Assigning Monte Carlo to λ = 0

  At λ = 0, the λ-return becomes the one-step return G (1) t.

  Fix: Associate λ = 0 with the one-step TD method. Associate Monte Carlo with λ = 1.

• Treating λ = 1 as merely similar to Monte Carlo

  The stated property is stronger: after simplification, the λ-return is the conventional return, and backing up according to it is identified as a Monte Carlo algorithm.

  Fix: State the full chain: λ = 1, conventional return, Monte Carlo algorithm.

• Confusing no model with no information

  The no-model property means that a complete and accurate model is not required; it does not mean that learning uses no observations.

  Fix: Keep the two ideas separate: temporal-difference learning uses experience and does not require a supplied model.

• Equating incremental computation with guaranteed superiority

  The source identifies temporal-difference learning's flexibility and incremental computation, but also states that it is more complex to analyze and does not give a universal ranking of efficiency or convergence speed.

  Fix: Describe incremental computation as a defining property and advantage, not as proof of universal superiority.

Check Your Classification

Key Takeaways

1. The λ-return is best understood through its endpoint settings. λ = 1 produces the conventional return and therefore the Monte Carlo algorithm. λ = 0 produces the one-step return G (1) t and therefore the one-step TD method. Temporal-difference learning solves finite Markov decision problems without requiring a model and is fully incremental, meaning that it can make progress step by step. Dynamic programming requires a complete and accurate model, Monte Carlo methods are model-free but not well suited to incremental computation, and temporal-difference methods combine model-free learning with incremental computation while being more complex to analyze.