Dynamic Programming Methods
Dynamic Programming methods use successor-state estimates when updating state-value estimates.
Why Successor Estimates Matter
Dynamic Programming methods revise a state-value estimate by using estimates associated with successor states. This means that value information can move from a later state toward the state currently being reconsidered. The central idea behind this process is bootstrapping: revising one estimate on the basis of another estimate.
Dynamic Programming methods use successor-state estimates when updating state-value estimates.
Bootstrapping a State Estimate
Bootstrapping is the practice of revising an estimate on the basis of another estimate.
Suppose State A is the state whose value estimate is being reconsidered. Instead of revising A directly from a final answer, the method looks at an estimate belonging to a later state, such as successor State B. Information from B becomes part of the basis for revising A. Because one estimate helps revise another estimate, the update bootstraps.
State A and Its Successor
Explain why revising State A using an estimate for successor State B is bootstrapping.
- 1Identify the current state
State A is the state whose value estimate is being reconsidered.
- 2Identify the successor
State B is a later state and its value estimate supplies information for the update.
- 3Apply the update
The estimate for A is revised using the estimate for B rather than being revised directly from a final answer.
- 4Classify the update
Because one estimate is used to revise another estimate, the update is a bootstrapping update.
The update bootstraps the estimate for State A from the estimate for successor State B.
Information Moving Backward
Dynamic Programming applies bootstrapping systematically. Its state-value updates are based on estimates of successor states, so the estimate for one state is connected to estimates farther along the state sequence. During an update, information from successor states moves toward the state currently being reconsidered. This makes the updates internally connected: an estimate for one state can provide the basis for changing an estimate for another state.
The Environment Model
Dynamic Programming requires a complete and accurate model of the environment. That model is used to consider possible successor states while state-value estimates are updated. The model requirement describes what information the method needs about the environment; it is a separate question from whether the method bootstraps.
Two Independent Questions
When classifying a reinforcement learning method, ask two separate questions. First, does it require a complete and accurate model of the environment? Second, does it bootstrap by updating one estimate from another estimate? Dynamic Programming answers yes to both questions, but these properties do not always appear together in other methods.
| Method category | Requires a complete and accurate model | Bootstraps |
|---|---|---|
| Dynamic Programming | Yes | Yes |
| Another reinforcement learning method | No | No |
| Another reinforcement learning method | No | Yes |
The source distinguishes model dependence from bootstrapping. The categories are illustrative properties, not names of additional algorithms.
Estimate or Observed Outcome
The defining distinction is what supplies the basis for an update. In bootstrapping, an estimate for another state supplies that basis. This differs from revising an estimate directly from a final answer or completed outcome. Dynamic Programming uses the first pattern: successor-state estimates support the update of the current state estimate.
Check Your Classification
A method revises the value estimate for State A using an estimate for successor State B. The method also has a complete and accurate model of the environment. Which two properties does this description identify?
Hints
- Look separately at the source of the update and the information the method requires.
- Using one estimate to revise another is the definition of bootstrapping.
What do you think happens?
Does the method bootstrap, require a complete and accurate model, or both?
Reveal answer
It does both.
The update uses a successor-state estimate, so it bootstraps. The description also explicitly gives the method a complete and accurate environment model.
Key Takeaways
- 1Bootstrapping means revising an estimate using another estimate.
- 2Dynamic Programming updates a state-value estimate using estimates of successor states.
- 3The update moves value information from successor states toward the state being reconsidered.
- 4Dynamic Programming requires a complete and accurate environment model and also bootstraps.
- 5Model dependence and bootstrapping are separate properties, so reinforcement learning methods can combine them in different ways.
At a glance
- Bootstrapping revises one estimate on the basis of another estimate.
- Dynamic Programming uses successor-state estimates to update current state-value estimates.
- Dynamic Programming requires a complete and accurate environment model.
- Requiring a model and bootstrapping are independent classification questions.
- A method may differ from Dynamic Programming by changing either property or both.