Bootstrapping Methods
SGD variations are used to find a good weight vector for function approximation.
Why Approximate Value Functions
When a value function is represented by a parameterized approximation, learning means finding a useful weight vector. Variations of stochastic gradient descent are used for this search because updates can use sampled experience to adjust the weight vector toward better function-approximation predictions.
The central learning problem is not simply to calculate one value. It is to improve a weight vector so that the approximated value function becomes more useful.
Tracing an n-Step Target
N-step semi-gradient TD uses information from several steps of an experience sequence. The target combines rewards observed over those steps with a later value estimate at the endpoint. That later estimate is the bootstrap: the method uses an estimate to help construct the target rather than relying only on the complete outcome of the episode.
A Conceptual Three-Step Trace
Suppose an experience sequence provides three observed rewards before the target reaches an endpoint with an estimated value. What information contributes to the n-step target?
Collect experience: The method follows the sequence for several steps and records the rewards observed along the way.
Reach the endpoint: At the endpoint, the method uses the estimated value there as the bootstrap component.
Form the target: The target contains both the observed reward information and the later estimated value.
Adjust the weights: The resulting target is used in a semi-gradient TD update for the value-function approximation.
The defining idea is the combination of several observed rewards with a later value estimate.
Why the On-Policy Case Fits
N-step semi-gradient TD is suited to the on-policy setting with a fixed policy. In this setting, the experience sequence comes from the policy whose value function is being learned. The method can therefore use the rewards and later value estimates generated along that policy's experience to update the same policy's value-function weights.
On-policy means that the policy generating the experience and the policy whose value function is being learned are treated as the same policy in this setting.
The Two Special Cases
N-step semi-gradient TD forms a family of methods. Two familiar methods appear at its limits: semi-gradient TD(0) is the one-step special case, while gradient MC is the infinity-step special case. The difference is how much experience is used before the target is formed.
| Choice of n | Method identified in the family | Target construction idea |
|---|---|---|
| One step | Semi-gradient TD(0) | Use the one-step special case |
| Several steps | N-step semi-gradient TD | Combine several observed rewards with a later value estimate |
| Infinity steps | Gradient MC | Use the infinity-step special case |
Recognizing the Method from n
A learner is told that an update uses the one-step special case. Which member of the n-step family is being described? What if the update uses the infinity-step special case?
Identify the step range: One step corresponds to the smallest listed special case, while infinity steps corresponds to the largest listed special case.
Match the names: The one-step case is semi-gradient TD(0). The infinity-step case is gradient MC.
One step identifies semi-gradient TD(0); infinity steps identifies gradient MC.
Why Semi-Gradient Is Not Full Gradient
Semi-gradient TD methods use a weight vector in their update target, but the dependence of that target on the weight vector is ignored when the gradient is computed. Because the gradient does not include the target's dependence on the weights, the update is not a true gradient method. This is why these methods are called semi-gradient methods.
Common Classification Mistakes
Treating every method with “gradient” in its name as a true gradient method.
The target uses a weight vector, but the target's dependence on that weight vector is ignored when the gradient is computed.
Fix:
Classify semi-gradient TD as semi-gradient rather than true gradient.Forgetting that n determines the special case.
Both are identified as special cases of n-step semi-gradient TD.
Fix:
Remember that semi-gradient TD(0) is the one-step case and gradient MC is the infinity-step case.Leaving out the fixed-policy condition when describing the natural setting for n-step semi-gradient TD.
The method is specifically suited to the on-policy case with a fixed policy.
Fix:
State the learning setting before explaining why the method fits it.
Check Your Understanding
Explain in your own words why semi-gradient TD(0) and gradient MC can both be described as special cases of n-step semi-gradient TD. Then explain why the word “semi” remains necessary for semi-gradient TD methods.
Hints
- Start by comparing one step with infinity steps.
- Mention how much of the experience sequence contributes to the target.
- State what happens to the target's dependence on the weight vector during the gradient computation.
What do you think happens?
A method uses the one-step special case of the n-step family. Which method is it?
Reveal answer
Answer: Semi-gradient TD(0)
Semi-gradient TD(0) is identified as the one-step special case, while gradient MC is the infinity-step special case.
Key Takeaways
- Variations of stochastic gradient descent are used to find a useful weight vector for function approximation.
- N-step semi-gradient TD is suited to the on-policy setting with a fixed policy.
- Semi-gradient TD(0) is the one-step special case of n-step semi-gradient TD.
- Gradient MC is the infinity-step special case.
- Semi-gradient TD is not a true gradient method because the target's dependence on the weight vector is ignored in the gradient.
Key Takeaways
- Function approximation uses SGD variations to search for a useful weight vector.
- N-step semi-gradient TD combines several observed rewards with a later estimated value and fits the on-policy fixed-policy setting.
- Semi-gradient TD(0) and gradient MC are the one-step and infinity-step special cases.
- Semi-gradient TD methods are not true gradient methods because they ignore the target's dependence on the weight vector when computing the gradient.