Multi-Step Semi-Gradient Methods

The algorithm extends Expected Sarsa to an n-step form.

Programming

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.

How does a multi-step method organize information across several time indices before forming its target?

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.

Start at t: The target is attached to the current time t.

Inspect t + n: For the target convention, compare the later index t + n with the terminal time T.

Apply 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.

Where does importance sampling belong in the multi-step treatment?

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.

Case 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.

Case 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).

Compare 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.

What changes when the time indices reach or pass the terminal time T?

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

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.

How does n-step tree-backup differ from the semi-gradient method in its treatment of importance sampling?

Common Reasoning Errors

Treating n-Step Semi-Gradient Expected Sarsa as a new name for one-step Expected Sarsa.
The source describes it as a multi-step generalization, not as an interchangeable name.
Fix: State that Expected Sarsa is the starting algorithm and that the n-step method extends its structure over multiple steps.
Using t instead of t + n for the G_t^(n) endpoint check.
The convention for G_t^(n) depends on whether t + n is greater than or equal to T.
Fix: Use the separate condition t + n ≥ T and then use G_t for G_t^(n).
Using the G_t^(n) check to decide the convention for ρ_t^s.
The convention for ρ_t^s examines t itself.
Fix: Use 1 for ρ_t^s when t ≥ T.
Assuming every off-policy method in this topic uses importance sampling.
The source identifies n-step tree-backup as an off-policy method without importance sampling.
Fix: Distinguish the multi-step semi-gradient treatment from n-step tree-backup before describing sampling.

Check Your Understanding

MEDIUM

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.

Your attempt (not saved)

EASY

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.