Bootstrapping 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.
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?
- 1Collect experience
The method follows the sequence for several steps and records the rewards observed along the way.
- 2Reach the endpoint
At the endpoint, the method uses the estimated value there as the bootstrap component.
- 3Form the target
The target contains both the observed reward information and the later estimated value.
- 4Adjust 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 |
The methods differ by how far the target extends through the experience sequence.
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?
- 1Identify the step range
One step corresponds to the smallest listed special case, while infinity steps corresponds to the largest listed special case.
- 2Match 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.
Assume every method described with the word gradient computes the gradient of the full error.
The target's weight dependence is overlooked.
For semi-gradient TD, check whether the target depends on the weight vector. That dependence is ignored in the computed gradient.
The distinction between semi-gradient and true gradient methods is made explicit.
Common Classification Mistakes
Common mistake Treating every method with “gradient” in its name as a true gradient method.
What it looks likeCalling semi-gradient TD a true gradient method simply because it uses a gradient-style update.
Why it failsThe target uses a weight vector, but the target's dependence on that weight vector is ignored when the gradient is computed.
Do this insteadClassify semi-gradient TD as semi-gradient rather than true gradient.
Common mistake Forgetting that n determines the special case.
What it looks likeDescribing the one-step case and the infinity-step case as unrelated methods.
Why it failsBoth are identified as special cases of n-step semi-gradient TD.
Do this insteadRemember that semi-gradient TD(0) is the one-step case and gradient MC is the infinity-step case.
Common mistake Leaving out the fixed-policy condition when describing the natural setting for n-step semi-gradient TD.
What it looks likePresenting the method without identifying the on-policy fixed-policy setting.
Why it failsThe method is specifically suited to the on-policy case with a fixed policy.
Do this insteadState 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
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
- 1Variations of stochastic gradient descent are used to find a useful weight vector for function approximation.
- 2N-step semi-gradient TD is suited to the on-policy setting with a fixed policy.
- 3Semi-gradient TD(0) is the one-step special case of n-step semi-gradient TD.
- 4Gradient MC is the infinity-step special case.
- 5Semi-gradient TD is not a true gradient method because the target's dependence on the weight vector is ignored in the gradient.
At a glance
- 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.