n-step Expected Sarsa

The central question is not whether the entire backup must be sampled or entirely expected. The central question is what choice to make at each step.

Programming

One Backup, Several Choices

An action-value backup improves an estimate of how valuable an action is. Earlier, three n-step choices were considered: n-step Sarsa, the tree-backup algorithm, and the n-step Expected Sarsa backup. They differ in how they handle the action choices encountered while looking ahead. n-step Q(σ) brings these choices into one framework: at every step, the backup can use the action that was sampled or an expectation over possible actions.

Key point

The central question is not whether the entire backup must be sampled or entirely expected. The central question is what choice to make at each step.

Following the Backup Step by Step

Imagine an n-step backup examining several successive decision points. At a decision point, it can commit to the action that was sampled, as Sarsa does, or account for all possible actions through an expectation, as tree backup does. In n-step Q(σ), this decision can be made separately at each step rather than being fixed for the whole backup.

How does the backup at each step choose between following the sampled next action and averaging over all possible actions?

The diagram shows the organizing decision at one step. The backup continues through its look-ahead after choosing either the sampled-action treatment or the expected-action treatment. Because the decision is available separately at each step, one backup can contain different choices at different points.

Reading σt as Sampling Degree

Definition

σt is the degree of sampling used at step t. σt = 1 represents full sampling, while σt = 0 represents pure expectation. Values between 0 and 1 represent a continuous degree of sampling.

What changes in the backup when σt moves from 0, fully expected, to 1, fully sampled, and what happens at intermediate values?

At σt = 1, the backup fully samples the action at step t. At σt = 0, it uses a pure expectation instead of relying on a sampled action. An intermediate value represents a continuous degree of sampling between those two endpoints. The subscript t matters: σt can differ from the sampling degree at another step.

A Look-Ahead Through n Steps

An n-step action-value backup looks across several successive decision points before improving the estimate of the starting action. At each point in that look-ahead, n-step Q(σ) applies the current sampling choice. The observed rewards and the action-value information encountered across the steps therefore contribute through a sequence of sampled or expected treatments.

How does information move from observed rewards and action values across n steps to form the updated estimate of the starting action value?

The pipeline is a structural view rather than a numerical calculation. The important mechanism is that the backup carries information across n steps, while the σ choice at each encountered decision point determines whether the action treatment is sampled or expected.

Three Methods in One Framework

Method	Sampling pattern	Action treatment
n-step Sarsa	Sampled-action pattern	Follows sampled actions
Tree backup	Expected-action pattern	Accounts for possible actions through expectation
n-step Expected Sarsa	Its corresponding expected-action backup pattern	Uses expected action values according to that backup

The three previously considered n-step action-value backups described through their sampling choices

The unifying claim is that these methods can be described with the same decision rule: choose how much each step relies on sampling. A pattern that uses full sampling corresponds to the Sarsa style. A pattern that uses pure expectation corresponds to the tree-backup style. The n-step Expected Sarsa backup is another particular pattern within the same framework. The source pack identifies these as particular σ choices, while the defining distinction remains whether each step follows a sampled action or uses expected action values.

Which pattern of σ values produces each of the three algorithms, and how do their resulting backups differ?

A Mixed Sampling Trace

Worked example

Following three decision points

Consider an n-step look-ahead with three encountered decision points. At the first point, the backup uses full sampling; at the second, it uses pure expectation; at the third, it uses an intermediate degree of sampling.

1
First point
Full sampling means the backup follows the sampled action at this point.
2
Second point
Pure expectation means the backup accounts for possible actions instead of relying on a sampled action at this point.
3
Third point
An intermediate σ value represents a continuous degree of sampling between the fully sampled and pure expectation cases.
4
Overall interpretation
The backup is mixed: its action treatment changes from one step to another rather than using one fixed choice throughout.

Result

n-step Q(σ) can represent a step-specific combination of sampled and expected action treatments.

This example illustrates the main advantage of the framework. The backup does not need to choose sampling or expectation once for the entire look-ahead. It can make the choice separately at each step, including intermediate degrees of sampling.

Mistakes About σ Choices

Common mistake
Treating σt as a single setting shared by every step
What it looks like
Assuming that one choice must control the entire n-step backup
Why it fails
The subscript t indicates that the degree of sampling can vary from one step to another.
Do this instead
Inspect the σ choice at each step in the look-ahead.
Common mistake
Reversing the endpoint meanings
What it looks like
Reading σt = 0 as full sampling and σt = 1 as pure expectation
Why it fails
The framework defines σt = 1 as full sampling and σt = 0 as pure expectation.
Do this instead
Remember: 1 means fully sampled, 0 means purely expected.
Common mistake
Assuming that Q(σ) only represents one old algorithm
What it looks like
Treating the framework as another name for only n-step Sarsa
Why it fails
Its purpose is to unify n-step Sarsa, tree backup, and n-step Expected Sarsa through sampling choices.
Do this instead
Ask which σ pattern is being used and whether each step samples an action or uses an expectation.
Common mistake
Ignoring intermediate values
What it looks like
Allowing only σt = 0 or σt = 1
Why it fails
Values between 0 and 1 represent a continuous degree of sampling.
Do this instead
Interpret an intermediate σt as a mixed degree between pure expectation and full sampling.

Practice the Unifying View

MEDIUM

Explain, in your own words, how n-step Q(σ) can describe both a sampled-action backup and an expected-action backup. Then explain what changes when σt varies across the steps of the same look-ahead.

Hints

Start with the meanings of σt = 1 and σt = 0.
Use the words sampled action and expectation over actions.
Explain why the subscript t allows different choices at different steps.

Your attempt (not saved)

EASY

Classify each description as closest to n-step Sarsa, tree backup, or a mixed n-step Q(σ) backup: a backup follows sampled actions throughout; a backup uses expectations throughout; a backup changes between sampling and expectation from one step to another.