n-step state-value algorithms
Keep that statement separate from the terminal-time boundary rule: the equality G^(n)_t = G_t is supplied for the case t + n ≥ T.
Why Tree Backup Matters
The n-step tree-backup algorithm belongs to the off-policy material in Chapter 7. Its defining distinction is that it is off-policy without using importance sampling. That single property makes it important to separate tree backup from methods whose off-policy correction depends on importance-sampling ratios.
The Off-Policy Distinction
An off-policy method separates the policy generating experience from the policy being learned about. For n-step tree backup, the source makes a specific claim about this separation: the algorithm is off-policy and does not involve importance sampling. Therefore, the defining point is not merely that tree backup uses multiple steps. The defining point is the way it supports off-policy learning without importance-sampling ratios.
Tracing the Return Boundary
The supplied boundary rule is G^(n)_t = G_t whenever t + n ≥ T. Here, T is the terminal time named by the condition. The practical interpretation is direct: once the n-step index reaches or passes the terminal time, the n-step return is represented by G_t rather than by a separate unfinished n-step expression.
Applying the terminal-time condition
Suppose the condition t + n ≥ T is true for a particular time t. Which return represents the n-step return?
- 1Check the boundary
Evaluate whether t + n reaches or passes T.
- 2Apply the supplied rule
Because t + n ≥ T, use the equality G^(n)_t = G_t.
- 3Interpret the result
The n-step return is represented by G_t at this boundary.
When t + n ≥ T, the n-step return is G_t.
Original and Semi-Gradient Forms
The semi-gradient tree-backup algorithm is a semi-gradient version of the original tree-backup method. These are connected algorithms, but they should not be treated as unrelated names. The original method is the base tree-backup algorithm; the semi-gradient version applies semi-gradient methods to that original method.
| Algorithm | Relationship | What to identify |
|---|---|---|
| Original n-step tree backup | Base method | An off-policy algorithm without importance sampling |
| Semi-gradient tree backup | Semi-gradient version of the original | The same tree-backup idea presented through semi-gradient methods |
The source distinguishes the original tree-backup algorithm from its semi-gradient version.
Tree Backup and Q Sigma
n-step Q(σ) and semi-gradient tree backup play different roles. The source describes n-step Q(σ) as having a broader unifying role across action-value algorithms. By contrast, semi-gradient tree backup is specifically a semi-gradient version of the original tree-backup algorithm. Q(σ) is therefore the broader unifying idea in this comparison, while semi-gradient tree backup names a particular version of tree backup.
| Concept | Role described by the source | Scope |
|---|---|---|
| n-step Q(σ) | Broader unifying role | Across action-value algorithms |
| Semi-gradient tree backup | Semi-gradient version of tree backup | The tree-backup method |
Do not use the two names as though they identify the same kind of idea.
Common Misreadings
Common mistake Calling tree backup on-policy because it does not use importance sampling.
What it looks likeTree backup is off-policy, but it has no importance-sampling ratios.
Why it failsThe source explicitly identifies n-step tree backup as off-policy and separately emphasizes its lack of importance sampling.
Do this insteadRemember both properties together: tree backup is off-policy and does not involve importance sampling.
Common mistake Treating the semi-gradient tree-backup algorithm as a completely different algorithm.
What it looks likeThe original method and the semi-gradient version are unrelated.
Why it failsThe semi-gradient algorithm is described as a semi-gradient version of the original method.
Do this insteadView the semi-gradient form as a version of the original tree-backup method.
Common mistake Reading t + n ≥ T as though the n-step return remains an unspecified expression.
What it looks likeWhen t + n reaches T, continue without applying a boundary rule.
Why it failsThe supplied condition explicitly gives G^(n)_t = G_t in that case.
Do this insteadReplace the n-step return representation with G_t whenever t + n ≥ T.
Common mistake Using n-step Q(σ) and semi-gradient tree backup as interchangeable labels.
What it looks likeBoth names refer to the same narrowly scoped tree-backup version.
Why it failsThe source gives Q(σ) a broader unifying role across action-value algorithms, while semi-gradient tree backup is a version of tree backup.
Do this insteadMatch each term to its scope before explaining it.
Check Your Understanding
Explain in two or three sentences why n-step tree backup is classified as off-policy even though it does not use importance sampling. Then explain what the condition t + n ≥ T tells you about G^(n)_t.
Hints
- Use the source's distinction between off-policy learning and importance sampling.
- State the boundary equality explicitly.
A learner says, “n-step Q(σ) is simply the semi-gradient form of tree backup.” Correct the statement by identifying the role and scope of each concept.
Hints
- One concept has a broader unifying role across action-value algorithms.
- The other is explicitly described as a version of the original tree-backup algorithm.
Key Takeaways
- 1N-step tree backup is an off-policy method distinguished by its lack of importance sampling.
- 2The semi-gradient tree-backup algorithm is a semi-gradient version of the original tree-backup method.
- 3When t + n ≥ T, the supplied boundary rule is G^(n)_t = G_t.
- 4N-step Q(σ) has a broader unifying role across action-value algorithms, so it should not be treated as a synonym for semi-gradient tree backup.
- 5The target-policy and behavior-policy distinction must be kept separate from the question of whether importance sampling is used.
At a glance
- Tree backup is off-policy without importance sampling.
- The semi-gradient tree-backup algorithm is a semi-gradient version of the original method.
- The boundary condition G^(n)_t = G_t applies whenever t + n ≥ T.
- N-step Q(σ) is broader in scope than semi-gradient tree backup because it has a unifying role across action-value algorithms.