n-Step Tree-Backup Algorithm
Episode-end handling requires two independent index checks.
Why the Episode Boundary Matters
The difficult part of n-step tree-backup is not limited to what happens during an episode. You must also decide how to interpret the notation when a time index reaches or passes the terminal time T. The source defines two separate episode-end conventions: one for the importance-sampling-related quantity ρ_t^s and another for the multi-step target G(n)_t.
Never use one episode-end test for both quantities. Check t against T for ρ_t^s, and check t + n against T for G(n)_t.
This distinction is especially important because the n-step tree-backup algorithm belongs to off-policy learning but does not involve importance sampling. At the same time, the algorithm has a semi-gradient version. Therefore, the terms off-policy, importance sampling, and semi-gradient must not be treated as interchangeable labels.
The Two Boundary Checks
The first check asks whether t has reached or passed T. If t is greater than or equal to T, ρ_t^s is defined as 1. Otherwise, ρ_t^s uses its ordinary definition. The second check asks whether t + n has reached or passed T. If t + n is greater than or equal to T, G(n)_t is treated as G_t. Otherwise, G(n)_t uses its ordinary multi-step definition.
Tracing the Return Window
Consider a generated case with terminal time T equal to 5. Start at t equal to 4 and use n equal to 1. The first test examines t itself: 4 is less than 5, so the episode-end convention for ρ_t^s does not apply. The second test examines t + n: 4 + 1 equals 5, so the episode-end convention for G(n)_t does apply. The target is therefore read as G_t.
Applying Both Tests to One Case
Let T = 5, t = 4, and n = 1. Determine the episode-end treatment for ρ_t^s and G(n)_t.
Check ρ_t^s: Compare t with T. Since 4 is less than 5, t has not reached the episode end, so the special value 1 is not selected for ρ_t^s.
Check G(n)_t: Compute t + n. Since 4 + 1 equals 5, the return window reaches T, so G(n)_t is treated as G_t.
Keep the results independent: The first quantity is handled using the test on t, while the second is handled using the test on t + n.
For this case, ρ_t^s uses its ordinary treatment, while G(n)_t is read as G_t.
If t + n passes T rather than merely reaching it, the same return convention applies. For example, with T equal to 5, t equal to 4, and n equal to 2, t + n equals 6, which is greater than T. The condition t + n greater than or equal to T is still satisfied, so G(n)_t is treated as G_t. The source pack does not expand G_t into a reward-by-reward expression, so the safe conclusion is the convention itself: use G_t at this boundary.
Tracing the Ratio Boundary
The episode-end rule for ρ_t^s is controlled only by t. Whenever t is greater than or equal to T, ρ_t^s is taken to be 1. This remains true regardless of the value of n, because n is not part of this particular boundary test.
Checking t Without Looking at n
Let T = 5 and t = 5. Compare the episode-end treatment of ρ_t^s for n = 1 and n = 3.
Compare t with T: The value of t is 5 and T is 5, so t has reached T.
Apply the ratio convention: Because t is greater than or equal to T, ρ_t^s is taken to be 1.
Ignore n for this check: Changing n from 1 to 3 does not change the result for ρ_t^s, because its episode-end test examines t rather than t + n.
For both n = 1 and n = 3, the episode-end value of ρ_t^s is 1.
Off-Policy and Semi-Gradient Status
The n-step tree-backup algorithm is an off-policy method without importance sampling. This is the key distinction from the semi-gradient methods described in the source passage, where importance sampling is involved. The absence of importance sampling does not prevent the algorithm from having a semi-gradient version.
| Method or description | Policy setting stated in the source | Importance sampling | Semi-gradient version |
|---|---|---|---|
| n-step tree-backup algorithm | Off-policy | Does not involve importance sampling | Yes |
| Semi-gradient methods described in the source passage | Not specified in the supplied material | Importance sampling is involved | They are described as semi-gradient methods |
The practical lesson is to identify the algorithm before describing its sampling behavior. First ask whether the discussion is about n-step tree-backup. If it is, the source characterizes it as off-policy and without importance sampling. Then separately note whether the version under discussion is its semi-gradient version.
Common Boundary Mistakes
Using t + n to decide the episode-end value of ρ_t^s.
The convention for ρ_t^s examines t itself. Here t is less than T.
Fix:
Check t ≥ T for ρ_t^s. In this case, the special value 1 is not selected by the episode-end rule.Using t alone to decide whether G(n)_t becomes G_t.
The convention for G(n)_t examines t + n, which is 6 and therefore reaches or passes T.
Fix:
Check t + n ≥ T for G(n)_t. In this case, use G_t.Assuming every off-policy method uses importance sampling.
The source explicitly describes n-step tree-backup as off-policy without importance sampling.
Fix:
State the method's sampling treatment directly: n-step tree-backup does not involve importance sampling.Treating semi-gradient and importance sampling as mutually exclusive.
The source states that n-step tree-backup has a semi-gradient version.
Fix:
Keep the labels separate. The algorithm can be discussed as off-policy, without importance sampling, and in a semi-gradient version.
Independent Check Practice
For each case, determine whether the episode-end convention applies to ρ_t^s, to G(n)_t, to both, or to neither. Case A: T = 8, t = 6, n = 2. Case B: T = 8, t = 8, n = 1. Case C: T = 8, t = 7, n = 3.
Hints
- For ρ_t^s, compare t with T.
- For G(n)_t, compute t + n and compare it with T.
- Do not let the result of one check determine the other.
What do you think happens?
In Case A, with T = 8, t = 6, and n = 2, which episode-end convention applies?
Reveal answer
Answer: Only the convention for G(n)_t
Here t is 6, which is less than T, so the episode-end convention for ρ_t^s does not apply. But t + n is 8, so G(n)_t is treated as G_t.
Write two separate lines when solving a boundary case: first, “Is t at least T?” and second, “Is t + n at least T?” Assign the treatment of ρ_t^s only from the first answer and the treatment of G(n)_t only from the second.
Key Takeaways
- The episode-end rules for ρ_t^s and G(n)_t require independent index checks.
- Use 1 for ρ_t^s when t is greater than or equal to T.
- Use G_t for G(n)_t when t + n is greater than or equal to T.
- n-step tree-backup is an off-policy method that does not involve importance sampling.
- n-step tree-backup also has a semi-gradient version, so semi-gradient status and importance-sampling treatment must be described separately.
Key Takeaways
- Check t against T for ρ_t^s and use 1 when t reaches or passes T.
- Check t + n against T for G(n)_t and use G_t when the return window reaches or passes T.
- The two episode-end checks can produce different outcomes in the same case.
- n-step tree-backup is off-policy without importance sampling, yet it has a semi-gradient version.
- Always identify the algorithm and perform both boundary checks before assigning the notation.