n-Step TD Prediction Methods
An n-step return is not a completely different target from the full return. It is an approximation to the full return: the first n rewards are explicit, while the later terms are represented by a value estimate.
From Complete Return to Shorter Target
An episode can produce a sequence of rewards after a particular time step. The full return uses the complete discounted reward sequence from that time step through episode termination. An n-step return uses only the rewards observed during the next n steps and then estimates the remaining part. The central idea is to replace a long, completely observed target with a shorter target that combines observed rewards and a value estimate.
An n-step return is not a completely different target from the full return. It is an approximation to the full return: the first n rewards are explicit, while the later terms are represented by a value estimate.
Following the n-Step Window
Start at time t and look forward one step at a time. The n-step window includes the reward from the first step after t, the reward from the second step after t, and so on until n rewards have been observed. Those rewards form the explicit part of the n-step return. Rewards after that window are not individually included in the target. Instead, the value estimate for the state reached after n steps represents the missing later terms.
Selecting the Explicit Rewards
Suppose the next four rewards after time t are observed, but the method uses a 2-step return.
- 1Locate the starting time
Begin with the state at time t.
- 2Count two steps
The rewards from the first and second steps after t are included explicitly.
- 3Stop the explicit sequence
The third and fourth rewards are beyond the 2-step window, so they are not written as individually observed terms in the n-step target.
- 4Represent what remains
A value estimate at the state reached after the second step represents the missing later terms.
The 2-step return contains two explicit rewards followed by a discounted value estimate for the remaining part.
The Bootstrap Correction
Stopping after n rewards would leave out the rewards that occur later in the episode. The n-step method addresses this by looking at the state reached after n steps and using its value estimate as a stand-in for those missing later terms. Because this estimate begins n steps after the starting time, its contribution is discounted by γ^n. Thus, the n-step target has two parts: the explicitly observed discounted rewards and the discounted value estimate for the remaining sequence.
Separating Observed and Estimated Parts
Consider a 3-step return beginning at time t.
- 1Include three rewards
The rewards observed on steps one, two, and three after time t belong explicitly to the n-step return.
- 2Find the boundary state
After the third step, identify the state reached at the end of the 3-step window.
- 3Estimate the remainder
Use the value estimate of that boundary state to represent the later discounted rewards.
- 4Discount the estimate
The value estimate is multiplied by γ^3 because it stands three steps away from the starting time.
A 3-step return is the discounted contribution of the first three rewards plus γ^3 times the value estimate at the state reached after three steps.
Full Return and n-Step Approximation
The full return continues explicitly through episode termination, so it contains the entire discounted reward sequence from time t onward. The n-step return stops writing rewards after n steps. It then uses the value estimate at the reached state to approximate what the full return would have received later. The two targets therefore share the same beginning, but the n-step return replaces the later explicit sequence with an estimate.
| Feature | Full return | n-step return |
|---|---|---|
| Reward sequence | Uses the complete sequence through episode termination | Uses rewards observed during the next n steps |
| Later terms | Remain explicit in the return | Are represented by a value estimate |
| Role of γ^n | Not the defining correction described for a truncated window | Discounts the value estimate at the n-step boundary |
| Relationship | Complete target | Approximation to the full return |
The full return and n-step return differ mainly in how they handle rewards after the n-step boundary.
Termination and Exact Equality
The n-step return equals the ordinary full return when the n-step window reaches episode termination. In that case, there are no later rewards left to represent with a value estimate. The truncated sequence is not actually missing a later part, so the n-step target contains the same complete reward sequence as the full return.
An n-Step Window at the Episode End
Suppose an episode ends exactly after the nth step of the window.
- 1Observe the n rewards
The n-step method observes every reward from the starting time through the end of the window.
- 2Check for later terms
Because the episode terminates at that boundary, there are no later rewards beyond the observed sequence.
- 3Remove the missing-part correction
There is no remaining sequence for a value estimate to represent.
The n-step return is equal to the ordinary full return because the n-step window reaches episode termination.
Common Reasoning Errors
Common mistake Treating the n-step return as if it includes every reward through episode termination.
What it looks likeA learner counts rewards after the nth step as explicit terms in an n-step target.
Why it failsThe n-step return truncates the explicit reward sequence after n steps.
Do this insteadInclude only the next n observed rewards explicitly, then use the value estimate for the later terms.
Common mistake Using the value estimate to replace the first n rewards.
What it looks likeA learner begins with a value estimate at the n-step boundary and ignores the rewards observed before reaching that state.
Why it failsThe estimate represents the missing later part, not the already observed rewards.
Do this insteadKeep the first n discounted rewards and add the discounted value estimate for the remainder.
Common mistake Forgetting the γ^n discount on the value estimate.
What it looks likeA learner adds the boundary state's value estimate without accounting for the n steps between the starting state and that boundary.
Why it failsThe source definition states that the correction is discounted by γ^n.
Do this insteadDiscount the value estimate by γ^n before combining it with the explicit reward sequence.
Common mistake Assuming an n-step return is always different from the full return.
What it looks likeA learner continues to use a bootstrap estimate even when the episode terminates at the end of the n-step window.
Why it failsWhen the window reaches termination, no later terms are missing.
Do this insteadRecognize that the n-step and full returns are equal when the n-step window reaches episode termination.
When analyzing an n-step target, mark the boundary first. Count exactly n steps from time t, list the rewards up to that boundary, and then ask whether the episode has already terminated. If it has not, the value estimate at the reached state represents the later terms and must receive the γ^n discount.
Practice Check
A learner is forming a 4-step return from time t. The episode continues beyond the fourth step. Identify which rewards are included explicitly, what represents the later terms, and what discount is applied to that estimate. Then state whether this target is the full return or an approximation to it.
Hints
- Count four rewards beginning with the reward from the first step after time t.
- Locate the state reached after the fourth step.
- The missing later terms are represented by that state's value estimate.
- The correction is discounted by γ raised to the number of steps in the window.
What do you think happens?
If an episode terminates exactly at the end of a 4-step window, does the 4-step return still need a value estimate for later rewards?
Reveal answer
No, because there are no later terms after termination.
When the n-step window reaches episode termination, the observed sequence already extends through the end of the episode. Therefore, the n-step return equals the ordinary full return and has no missing later part to estimate.
Essential Distinctions
- 1The full return is the complete discounted reward sequence from time t through episode termination.
- 2The n-step return includes the rewards observed during the next n steps explicitly.
- 3The value estimate at the state reached after n steps represents the missing later terms.
- 4That estimate is discounted by γ^n because it begins n steps after the starting time.
- 5The n-step return equals the full return when its window reaches episode termination.
Key Takeaways
- The full return follows discounted rewards all the way to episode termination.
- An n-step return follows only the next n rewards explicitly.
- A value estimate at the state reached after n steps stands in for the later missing terms.
- The bootstrap correction is discounted by γ^n.
- If the n-step window reaches termination, the n-step return and full return are equal.