Backward-view temporal-difference learning
The on-line λ-return algorithm motivates this topic because it combines strong performance with a complex forward-view presentation.
Why the Forward View Needs a Transformation
The on-line λ-return algorithm is important because it combines strong performance with a forward-view description. Its difficulty is that this forward-view form is complex. An algorithm can be valuable because of its performance, but it must also be practical to implement. Backward-view temporal-difference learning addresses this tension by transforming the same learning idea into an efficient, step-by-step implementation.
The forward-view and backward-view descriptions are not presented as unrelated algorithms. The backward view is an implementation transformation: eligibility traces provide a way to implement the on-line λ-return algorithm efficiently.
Reading the Two Views
The forward view organizes learning around returns that extend into the future. This makes the on-line λ-return algorithm conceptually powerful, but its presentation is complex because the update is described through future-return information. The backward view reorganizes the computation around the history that has already occurred. Eligibility traces record which recently visited states or features should receive credit when a new temporal-difference error arrives.
A new error arrives
Suppose a learner has recently encountered several states or features and then receives a new temporal-difference error.
Record recent experience: Eligibility traces retain information about which states or features were recently visited.
Receive the new error: The new temporal-difference error provides the immediate learning signal.
Assign credit through traces: The traces identify the earlier states or features that should share the effect of the new error.
Continue incrementally: The learner can proceed step by step rather than relying on a separate, complex forward-view presentation.
Eligibility traces connect a current temporal-difference error with relevant recent experience, producing the backward-view implementation idea.
True Online TD(λ)
True online TD(λ) is the backward-view implementation associated with the on-line λ-return algorithm. Its purpose is not to introduce an unrelated learning method, but to provide an exact and computationally efficient implementation of that algorithm when using linear function approximation. The scope matters: the source makes this exactness claim for linear function approximation, not for every possible form of function approximation.
Incremental Learning Without a Model
Temporal-difference learning is a class of methods for solving finite Markov decision problems without requiring a model. Requiring no model means that the method does not depend on being supplied with a complete and accurate description of the environment.
Fully incremental computation means that learning can make progress step by step. A temporal-difference method does not need to wait for a complete outcome before making progress, and it does not need to recompute earlier returns as a separate batch operation. Each newly observed transition can contribute to ongoing value-estimate updates through the temporal-difference learning process and its eligibility traces.
Three Ways to Solve the Problem
Dynamic programming, Monte Carlo methods, and temporal-difference learning can be compared using two questions: Does the method require a model of the environment? Can it compute incrementally, step by step? The comparison reveals why temporal-difference learning is useful without claiming that it is always the fastest or best method.
| Method class | Model requirement | Incremental computation | Main strength | Main weakness |
|---|---|---|---|---|
| Dynamic programming | Requires a complete and accurate model | Not identified in the source as the defining advantage | Mathematically well developed | Depends on a supplied model |
| Monte Carlo methods | Does not require a model | Not well suited to step-by-step incremental computation | Conceptually simple | Less suited to fully incremental computation |
| Temporal-difference learning | Does not require a model | Fully incremental | Combines no model requirement with step-by-step computation | More complex to analyze |
Temporal-difference learning's distinctive combination is model-free operation and fully incremental computation. Its trade-off is greater analytical complexity than the alternatives described here.
Common Misunderstandings
Treating the forward-view and backward-view algorithms as unrelated methods.
The backward-view approach is an implementation transformation intended to realize the on-line λ-return algorithm efficiently.
Fix:
Explain the forward view as the complex presentation and the backward view as the eligibility-trace-based implementation.Claiming that true online TD(λ) is exact for every kind of function approximation.
The stated exactness claim is specifically for linear function approximation.
Fix:
Always name linear function approximation when making the exactness claim.Confusing model-free learning with learning that uses no information about the environment.
No model means no supplied complete and accurate environment model is required; temporal-difference learning still proceeds from experience and observed transitions.
Fix:
Distinguish the absence of a model from the presence of ongoing learning information.Assuming that temporal-difference learning is always superior.
The source identifies useful flexibility and incremental computation, but also says that temporal-difference methods are more complex to analyze and does not give a universal speed or convergence ranking.
Fix:
Describe the trade-off rather than making an unconditional ranking.
Check Your Understanding
Explain, in your own words, why eligibility traces are useful when converting the on-line λ-return algorithm from a forward-view presentation into a backward-view implementation. Then state the precise setting in which true online TD(λ) implements the on-line λ-return algorithm exactly.
Hints
- Start by describing what makes the forward-view presentation difficult to implement.
- Connect eligibility traces to recently visited states or features and a new temporal-difference error.
- Include the words linear function approximation in the exactness statement.
What do you think happens?
A method requires no model and makes progress step by step as new transitions are observed. Which method class best matches this description?
Reveal answer
Answer: Temporal-difference learning
The source distinguishes temporal-difference learning by its combination of no model requirement and fully incremental computation.
Key Takeaways
- The on-line λ-return algorithm is significant because it combines strong performance with a complex forward-view presentation.
- Eligibility traces provide the mechanism for an efficient backward-view implementation based on recent experience and incoming temporal-difference errors.
- True online TD(λ) is an exact implementation of the on-line λ-return algorithm for linear function approximation.
- Temporal-difference learning solves finite Markov decision problems without requiring a complete and accurate model and supports fully incremental computation.
- Dynamic programming, Monte Carlo methods, and temporal-difference learning trade off model requirements, incremental computation, conceptual or analytical simplicity, and flexibility.
Key Takeaways
- Backward-view temporal-difference learning is an implementation transformation motivated by the strong but complex on-line λ-return algorithm.
- Eligibility traces connect each new temporal-difference error to relevant recently visited states or features.
- True online TD(λ) exactly implements the on-line λ-return algorithm in the setting of linear function approximation.
- Temporal-difference learning is model-free and fully incremental for finite Markov decision problems.
- Its main advantage is the combination of no model requirement and step-by-step computation, while its stated weakness is greater analytical complexity.