Multi-Step Semi-Gradient Methods
Keep the algorithm identity clear: Expected Sarsa is the starting one-step algorithm named by the source, while n-Step Semi-Gradient Expected Sarsa is its multi-step counterpart.
From One Step to Several
n-Step Semi-Gradient Expected Sarsa extends Expected Sarsa from a one-step procedure to a multi-step method. The important point is that this is not merely a different label for the same algorithm. The n-step method is a generalization that expresses the learning target over multiple steps. In this multi-step setting, importance sampling is part of the algorithm.
Keep the algorithm identity clear: Expected Sarsa is the starting one-step algorithm named by the source, while n-Step Semi-Gradient Expected Sarsa is its multi-step counterpart.
Reading the Multi-Step Target
The notation G_t^(n) identifies the target used at time t when the method is expressed over n steps. Conceptually, the target is associated with a span that begins at t and reaches toward t + n. The estimate at the later point is relevant when the backup has not already reached the end of the episode. This is the structural difference from a one-step method: the multi-step version is organized around a larger time span rather than only the immediately following step.
Checking the Backup Horizon
Consider a target written as G_t^(n), with a current time t and a later index t + n. Decide which index determines whether the multi-step target reaches the episode end.
- 1Start at t
The target is attached to the current time t.
- 2Inspect t + n
For the target convention, compare the later index t + n with the terminal time T.
- 3Apply the boundary rule
If t + n is greater than or equal to T, use G_t in place of G_t^(n).
The target-end check is based on t + n, not on t alone.
The Two Episode-End Checks
The episode boundary is the most delicate part of the notation. It requires two independent checks, because ρ_t^s and G_t^(n) use different indices. First ask whether t has reached or passed T. Then separately ask whether t + n has reached or passed T. The two conditions must not be merged into one test.
| Quantity | Boundary check | Episode-end convention |
|---|---|---|
| ρ_t^s | t is greater than or equal to T | Use 1 |
| G_t^(n) | t + n is greater than or equal to T | Use G_t |
The two endpoint rules use different index checks.
Applying the Rules Separately
Suppose the terminal time is T = 5. Examine two cases: t = 4 with n = 2, and t = 5 with n = 2.
- 1Case one: t = 4
Because t is less than T, the endpoint convention for ρ_t^s is not triggered by t. However, t + n equals 6, which is greater than T, so the convention for G_t^(n) is triggered.
- 2Case two: t = 5
Because t is equal to T, use 1 for ρ_t^s. Also, t + n is greater than T, so use G_t for G_t^(n).
- 3Compare the checks
The first case shows that the target can reach the endpoint even when t itself has not reached it. The second case shows that both endpoint conventions can apply at once.
Check t for ρ_t^s and check t + n for G_t^(n); never substitute one test for the other.
Write the boundary checks as two separate questions: Is t at least T? Is t + n at least T? Assign the convention only after answering the relevant question.
Expected Sarsa and Tree-Backup
| Method | Structural description | Importance sampling |
|---|---|---|
| Expected Sarsa | One-step algorithm named as the starting point | The source distinguishes it from the multi-step treatment |
| n-Step Semi-Gradient Expected Sarsa | Multi-step generalization of Expected Sarsa | Part of the multi-step treatment |
| n-step tree-backup | Off-policy alternative | Does not involve importance sampling |
The methods are distinguished by both backup structure and sampling treatment.
n-Step Tree-Backup should not be confused with n-Step Semi-Gradient Expected Sarsa. The source identifies n-step tree-backup as an off-policy method that does not involve importance sampling. It also states that n-step tree-backup has a semi-gradient version. Therefore, semi-gradient and importance sampling are not opposites: the algorithm must be identified first, and then its sampling treatment must be described correctly.
Common Reasoning Errors
Common mistake Treating n-Step Semi-Gradient Expected Sarsa as a new name for one-step Expected Sarsa.
What it looks likeDescribing the n-step method as if it used exactly the same one-step structure.
Why it failsThe source describes it as a multi-step generalization, not as an interchangeable name.
Do this insteadState that Expected Sarsa is the starting algorithm and that the n-step method extends its structure over multiple steps.
Common mistake Using t instead of t + n for the G_t^(n) endpoint check.
What it looks likeChecking only whether the current time has reached T.
Why it failsThe convention for G_t^(n) depends on whether t + n is greater than or equal to T.
Do this insteadUse the separate condition t + n ≥ T and then use G_t for G_t^(n).
Common mistake Using the G_t^(n) check to decide the convention for ρ_t^s.
What it looks likeReplacing ρ_t^s because t + n reaches the terminal time, even though t is still less than T.
Why it failsThe convention for ρ_t^s examines t itself.
Do this insteadUse 1 for ρ_t^s when t ≥ T.
Common mistake Assuming every off-policy method in this topic uses importance sampling.
What it looks likeAdding importance sampling to n-step tree-backup simply because it is off-policy.
Why it failsThe source identifies n-step tree-backup as an off-policy method without importance sampling.
Do this insteadDistinguish the multi-step semi-gradient treatment from n-step tree-backup before describing sampling.
Check Your Understanding
For each case, identify which endpoint checks are triggered. Use T = 8. Case A: t = 6 and n = 2. Case B: t = 7 and n = 2. Case C: t = 8 and n = 1. State the convention for ρ_t^s and for G_t^(n) in each case.
Hints
- Check t against T for ρ_t^s.
- Check t + n against T for G_t^(n).
- The two checks are independent.
Explain in two or three sentences why n-Step Semi-Gradient Expected Sarsa and n-step tree-backup should not be described as having the same importance-sampling behavior.
Hints
- One method is the multi-step generalization of Expected Sarsa.
- The source places importance sampling in that multi-step semi-gradient treatment.
- The source describes n-step tree-backup as an off-policy method without importance sampling.
Essential Takeaways
- 1n-Step Semi-Gradient Expected Sarsa is a multi-step generalization of Expected Sarsa.
- 2Importance sampling is part of the multi-step semi-gradient treatment described by the source.
- 3Use 1 for ρ_t^s when t is greater than or equal to T.
- 4Use G_t for G_t^(n) when t + n is greater than or equal to T.
- 5n-step tree-backup is an off-policy method without importance sampling, and it also has a semi-gradient version.
At a glance
- The n-step method extends Expected Sarsa across multiple steps rather than merely renaming the one-step method.
- Importance sampling belongs to the multi-step semi-gradient treatment.
- Episode-end handling requires two independent tests: t ≥ T for ρ_t^s and t + n ≥ T for G_t^(n).
- When the target reaches the episode end, use G_t for G_t^(n). When the time index reaches or passes the endpoint, use 1 for ρ_t^s.
- n-step tree-backup is an off-policy alternative without importance sampling and has its own semi-gradient version.