Tree backup
n-step Q(σ) unifies Sarsa and tree backup by allowing sampling and expectation to be selected across backup steps.
One Backup, Different Choices
An n-step action-value backup does not have to treat every step in the same way. At one step, it can follow the action that was actually selected. At another, it can combine the values associated with possible actions through expectation. n-step Q(σ) provides one framework for organizing these choices. Tree backup is the all-expectation endpoint of that framework.
Reading σt at One Step
σt is the degree of sampling on step t, and it lies between 0 and 1. σ = 1 means full sampling. σ = 0 means pure expectation with no sampling.
| Value of σt | Meaning | Backup choice |
|---|---|---|
| 1 | Full sampling | Use the action that was actually selected |
| 0 | Pure expectation | Use expectation over actions |
| Between 0 and 1 | Intermediate degree of sampling | A continuous variation between the two endpoints |
The degree of sampling describes the choice made at an individual backup step.
The value of σt does not have to be fixed by one rule for every situation. The source allows the random variable σt to 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.
Three Familiar Endpoints
The endpoint schedules make the unifying view easy to remember. If every step uses σ = 1, n-step Q(σ) becomes Sarsa. If every step uses σ = 0, it becomes the tree-backup algorithm. A schedule that samples on every step except the last gives Expected Sarsa.
Comparing four schedules
Identify the algorithmic pattern represented by each schedule of sampling degrees.
Schedule A: Every backup step has σ = 1. This is the Sarsa endpoint.
Schedule B: Every backup step has σ = 0. This is the tree-backup endpoint.
Schedule C: Every step is sampled except the last. This is the Expected Sarsa pattern.
Schedule D: The value of σ changes from step to step. This is another valid n-step Q(σ) arrangement, rather than one of the three named endpoint patterns.
n-step Q(σ) is broader than any one endpoint because it permits the sampling degree to vary across backup steps.
Following Another Policy
The n-step tree-backup algorithm is an off-policy algorithm. Its defining distinction in the supplied material is that it does not involve importance sampling.
Off-policy means that the policy generating the data and the policy associated with the update need not be the same. For tree backup, the important distinction is that this off-policy use does not require importance sampling. The behavior policy supplies the generated data, while the tree-backup backup uses expectation associated with the target policy.
Terminal Lookahead
The supplied boundary rule is G^(n)_t = G_t whenever t + n ≥ T. In words, once the n-step lookahead reaches or passes the terminal time, the n-step return is represented by the complete return G_t rather than by a shorter unfinished lookahead. The source also specifies γ = 1 in the continuing case.
The condition is about the boundary of the backup, not about choosing σ. Whether a step is sampled or expected is one issue; whether the lookahead has reached termination is another.
Exact and Semi-Gradient Forms
The semi-gradient tree-backup algorithm is a semi-gradient version of the original tree-backup method. Keep the two roles separate: tree backup identifies the off-policy backup based on expectation without importance sampling, while the semi-gradient version describes how that method is applied when semi-gradient methods are used.
Common Misreadings
Treating σ = 1 as tree backup because the value is larger.
σ = 1 means full sampling, and all steps set to σ = 1 produce Sarsa.
Fix:
Associate σ = 1 with sampling and σ = 0 with pure expectation. The all-zero schedule produces tree backup.Assuming n-step Q(σ) must use one fixed σ value at every step.
The framework specifically allows sampling and expectation to be selected across individual backup steps.
Fix:
Read σt locally: inspect the degree of sampling assigned to each step.Equating tree backup with any expected action-value backup.
The supplied definition distinguishes tree backup as an off-policy method that does not involve importance sampling.
Fix:
Mention both features when identifying tree backup: off-policy learning and no importance sampling.Treating n-step Q(σ) and semi-gradient tree backup as the same concept.
n-step Q(σ) has a broader unifying role, while semi-gradient tree backup is a semi-gradient version of the original tree-backup algorithm.
Fix:
Use n-step Q(σ) for step-by-step sampling choices and semi-gradient tree backup for the semi-gradient form of the tree-backup method.Ignoring the terminal boundary condition.
The supplied rule states that G^(n)_t = G_t whenever t + n ≥ T.
Fix:
Replace the n-step return with the complete return G_t at or beyond the terminal time.
Check Your Understanding
For each schedule, identify the corresponding interpretation: (1, 1, 1), (0, 0, 0), (1, 1, 0), and (1, 0, 1). Then state which schedule is the tree-backup endpoint and which schedule illustrates a mixed n-step Q(σ) arrangement.
Hints
- All ones means full sampling at every step.
- All zeros means pure expectation at every step.
- The source identifies sampling on every step except the last with Expected Sarsa.
- A schedule that changes from step to step is another possible n-step Q(σ) arrangement.
A learner says, “Tree backup is on-policy because it uses the observed trajectory.” Correct the statement using the two defining policy facts supplied for the algorithm.
Hints
- Separate the policy that generates data from the policy associated with the update.
- Include the fact about importance sampling.
Remember the Separation
- σt is the degree of sampling at step t, with values between 0 and 1.
- σ = 1 means full sampling; σ = 0 means pure expectation.
- All σ values equal to 1 produce Sarsa, all σ values equal to 0 produce tree backup, and sampling on every step except the last gives Expected Sarsa.
- Tree backup is off-policy and does not involve importance sampling.
- The semi-gradient tree-backup algorithm is a semi-gradient version of the original method.
- When t + n ≥ T, the supplied boundary rule is G^(n)_t = G_t.
Key Takeaways
- n-step Q(σ) unifies several action-value algorithms by allowing sampling or expectation to be chosen at each backup step.
- The endpoint σ schedules are Sarsa at σ = 1 everywhere and tree backup at σ = 0 everywhere.
- Expected Sarsa fits the framework through a schedule that samples on every step except the last.
- Tree backup is an off-policy method distinguished by its lack of importance sampling.
- The semi-gradient tree-backup algorithm is the semi-gradient version of the original tree-backup method, not a replacement name for the broader n-step Q(σ) framework.