n-step Expected Sarsa

n-step Q(σ) is a unifying framework for action-value backups.

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.

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

σ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

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.

First point: Full sampling means the backup follows the sampled action at this point.

Second point: Pure expectation means the backup accounts for possible actions instead of relying on a sampled action at this point.

Third point: An intermediate σ value represents a continuous degree of sampling between the fully sampled and pure expectation cases.

Overall interpretation: The backup is mixed: its action treatment changes from one step to another rather than using one fixed choice throughout.

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

Treating σt as a single setting shared by every step
The subscript t indicates that the degree of sampling can vary from one step to another.
Fix: Inspect the σ choice at each step in the look-ahead.
Reversing the endpoint meanings
The framework defines σt = 1 as full sampling and σt = 0 as pure expectation.
Fix: Remember: 1 means fully sampled, 0 means purely expected.
Assuming that Q(σ) only represents one old algorithm
Its purpose is to unify n-step Sarsa, tree backup, and n-step Expected Sarsa through sampling choices.
Fix: Ask which σ pattern is being used and whether each step samples an action or uses an expectation.
Ignoring intermediate values
Values between 0 and 1 represent a continuous degree of sampling.
Fix: 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.