n-step action-value backups
n-step Q(σ) unifies Sarsa and tree backup by allowing sampling and expectation to be selected across backup steps.
One Backup, Two Choices
An n-step action-value backup can make a different kind of choice at each step. It may use the action that was actually selected, as in Sarsa, or it may use an expectation over possible actions, as in tree backup. n-step Q(σ) provides one framework for organizing these choices.
The central idea is step-by-step control of sampling: σt describes how much a particular step relies on sampling rather than expectation.
Reading σt at One Step
The symbol σt is the degree of sampling on step t. Its value lies between 0 and 1. At the endpoint σ = 1, the step uses full sampling: it uses the action that was actually selected. At the endpoint σ = 0, the step uses pure expectation with no sampling: it considers the expectation over actions. Values between 0 and 1 represent a continuous variation between these two endpoints.
Tracing a Backup Schedule
Classifying a three-step schedule
Suppose an n-step backup uses σ values of 1, 0, and 1 on three successive steps. What kind of information does each step use?
First step: σ = 1, so this step is fully sampled and uses the action that was actually selected.
Second step: σ = 0, so this step uses pure expectation over actions rather than a sampled action.
Third step: σ = 1, so this step returns to full sampling and uses the action that was actually selected.
Interpret the pattern: The backup does not need to use one kind of choice everywhere. It can alternate between sampling and expectation from one step to the next.
The schedule is a mixed n-step Q(σ) arrangement: sampled, expected, then sampled.
This example is about the pattern of choices, not about calculating a numerical update. To read a schedule, inspect each σ value separately and label that step as sampled, expected, or intermediate.
The Sarsa–Tree Backup Range
The two endpoint algorithms are obtained by using the same σ value at every step. If all steps use σ = 1, every step is fully sampled, and n-step Q(σ) produces Sarsa. If all steps use σ = 0, every step uses pure expectation, and n-step Q(σ) produces tree backup.
| Schedule | Meaning |
|---|---|
| σ = 1 on every step | Sarsa: full sampling throughout the backup |
| σ = 0 on every step | Tree backup: pure expectation throughout the backup |
| Different values on different steps | A mixed n-step Q(σ) arrangement |
The algorithm is identified by the sampling choices made across the backup steps.
Expected Sarsa Inside the Framework
Expected Sarsa is one of the special schedules inside n-step Q(σ). In the source's description, it samples on every step except the last. The last step uses expectation, so Expected Sarsa combines sampled choices with an expected final choice rather than using one mode uniformly across all steps.
Choosing a Sampling Schedule
When analyzing an n-step Q(σ) backup, do not assume that one rule controls every step. First list the σ value associated with each step. Then classify each value: 1 means full sampling, 0 means pure expectation, and an intermediate value means a position between those endpoints. This step-by-step reading prevents a mixed schedule from being mistaken for either Sarsa or tree backup.
The sampling degree also does not have to be selected by one fixed rule for every situation. The random variable σt may be set as a function of the state, the action, or the state-action pair at time t. Thus, the sampling degree can be associated with the situation encountered at that step.
Common Schedule Mistakes
Treating σ as one permanent choice for the entire backup
n-step Q(σ) allows the choice to vary from one backup step to another.
Fix:
Inspect σt separately at each step and record whether that step uses sampling or expectation.Reversing the endpoint meanings
The source defines σ = 1 as full sampling and σ = 0 as pure expectation with no sampling.
Fix:
Remember: 1 means the selected action is used; 0 means expectation over actions is used.Calling every mixed schedule Expected Sarsa
The source identifies Expected Sarsa specifically as sampling on every step except the last.
Fix:
Compare the complete schedule with the defining pattern before assigning the Expected Sarsa label.Assuming intermediate σ values are another endpoint algorithm
Intermediate values represent continuous variation between full sampling and pure expectation.
Fix:
Describe an intermediate value as lying between the two endpoint choices unless a specific schedule is given.
Check Your Interpretation
Classify each schedule as Sarsa, tree backup, Expected Sarsa, or another n-step Q(σ) arrangement: (1) σ = 1 on every step, (2) σ = 0 on every step, (3) sampling on every step except the last, and (4) sampling, expectation, sampling.
Hints
- Start by matching the two uniform endpoint schedules.
- For Expected Sarsa, look for sampling on every step except the last.
- A schedule that does not match one of those exact patterns is another possible n-step Q(σ) arrangement.
What do you think happens?
If σ changes from 1 to 0 at one backup step, what changes at that step?
Reveal answer
Answer: The step changes from using the selected action to using pure expectation over actions.
σ is defined separately for each step, so changing one step's value changes that step's sampling-versus-expectation choice. The other steps retain their own choices.
Key Takeaways
- σt is the degree of sampling on step t and lies between 0 and 1.
- σ = 1 means full sampling using the action that was actually selected; σ = 0 means pure expectation over actions.
- Setting σ = 1 on every step produces Sarsa, while setting σ = 0 on every step produces tree backup.
- n-step Q(σ) permits sampling and expectation to be mixed across backup steps.
- Expected Sarsa is the schedule that samples on every step except the last, where expectation is used.