Temporal-Difference Learning
Reinforcement learning uses approximation because its problem framing cannot guarantee optimal behavior throughout the entire state set.
Useful Imperfection
Imagine an agent facing an enormous collection of possible states. An ideal policy would choose the best action in every one of them. Reinforcement learning cannot generally maintain that level of perfection across the entire state set, so it uses approximation. The important question becomes whether the approximation produces strong behavior in the states where the agent actually spends its experience.
Experience Concentrates Effort
The on-line nature of reinforcement learning creates a particular allocation of learning effort. As the agent encounters states, it can devote more effort to states that appear frequently and less effort to states that appear infrequently. This does not promise equally accurate decisions everywhere. Instead, it makes the approximation useful where the agent's experience is concentrated.
Source material uses TD-Gammon to illustrate this trade-off: a system may make bad decisions for a large fraction of a game's state set and still not be treated as useless. The relevant question is where those states occur and how much their decisions matter to experienced reward.
The Frequency of Errors
A poor decision in a rarely encountered state may have little effect on total reward because the agent seldom reaches that state. By contrast, an error in a frequently encountered state can matter more because it is connected to more of the agent's experienced behavior. This is not a promise that every rare-state error is harmless. State frequency and the state's effect on reward both matter.
One-Step Progress
Temporal-difference learning is a class of methods for solving finite Markov decision problems without requiring a model. Its defining computational feature is fully incremental, step-by-step progress. A method with no model requirement does not depend on being given a complete and accurate model of the environment.
A Single Experienced Step
An agent encounters a state, takes an action, receives a reward, and reaches another state. How does temporal-difference learning treat this experience?
Observe: The agent encounters the current state as part of ongoing experience.
Act and receive an outcome: The experience includes an action, a reward, and a next state.
Make progress: The method can use this step to update its value estimate rather than waiting for a complete outcome.
Continue: Because computation is fully incremental, learning can continue with the next experienced step.
Temporal-difference learning makes progress during the ongoing sequence of experience and does not require a complete, accurate model of the environment.
Three Method Classes
Dynamic programming, Monte Carlo methods, and temporal-difference learning all address finite Markov decision problems, but they make different trade-offs. The most useful comparison asks two questions: Does the method require a model of the environment? Can it compute incrementally, step by step?
| Method | Model requirement | Incremental computation | Stated strength or weakness |
|---|---|---|---|
| Dynamic programming | Requires a complete and accurate model | Not identified here as the defining property | Mathematically well developed |
| Monte Carlo | Does not require a model | Not well suited to step-by-step incremental computation | Conceptually simple |
| Temporal-difference learning | Does not require a model | Fully incremental | Useful flexibility, but more complex to analyze |
The central comparison is based on model requirements and when a method can make progress.
Common Misreadings
Assuming a useful reinforcement-learning system must make the best decision in every possible state.
Reinforcement learning uses approximation because it cannot generally maintain perfect behavior throughout the entire state set.
Fix:
Also consider which states are encountered frequently and how their decisions affect experienced reward.Treating weak performance in a rarely encountered state as automatically disastrous.
State frequency and effect on reward both matter; a rarely encountered state may have little effect on experienced behavior.
Fix:
Evaluate errors in relation to visitation frequency and consequences.Interpreting no model as no learning.
No model means the method does not require a complete and accurate model; it can learn from ongoing experience.
Fix:
Separate the source of information, experience, from the requirement for a supplied model.Treating Monte Carlo and temporal-difference learning as identical because neither requires a model.
Monte Carlo methods are not well suited to step-by-step incremental computation, whereas temporal-difference learning is fully incremental.
Fix:
Compare both model requirements and update timing.
Check Your Understanding
A learning agent visits State A many times and State B only rarely. Its decisions in State A improve, while its decisions in State B remain weak. Explain why this pattern can still be consistent with useful reinforcement learning. Then compare temporal-difference learning with dynamic programming and Monte Carlo methods using the two questions: Does it require a complete and accurate model? Can it make progress incrementally?
Hints
- Begin with the relationship between on-line experience and allocation of learning effort.
- Explain why the frequency and reward consequences of a state matter.
- For the method comparison, identify the model requirement and incremental-computation property of each method.
Key Takeaways
- Reinforcement learning uses approximation because perfect decisions across the entire state set generally cannot be maintained.
- On-line learning directs more effort toward states encountered frequently and less effort toward rarely encountered states.
- An error in a rare state may have little effect on experienced reward, although frequency and consequences must both be considered.
- Temporal-difference learning solves finite Markov decision problems without requiring a complete and accurate model and makes progress fully incrementally.
- Dynamic programming requires a complete and accurate model, Monte Carlo methods are not well suited to step-by-step incremental computation, and temporal-difference methods combine no model requirement with incremental computation but are more complex to analyze.
Key Takeaways
- Approximation is central to reinforcement learning because optimal behavior across every possible state cannot generally be guaranteed.
- On-line experience concentrates learning effort where states occur frequently, so practical strength does not require equal accuracy everywhere.
- Temporal-difference learning is model-free and fully incremental: it can make progress from ongoing experience without waiting for a complete outcome.
- Dynamic programming, Monte Carlo, and temporal-difference methods differ in model requirements, incremental computation, and analytical complexity.