n-step Tree Backup
Keep three objects separate: the expected action value, the TD error, and the final n-step tree-backup return.
From Two Quantities to One Return
n-step tree backup is easiest to understand as a construction. It first introduces an expected action value under the target policy and a separate TD-error quantity. The n-step tree-backup return is then defined using both. This order matters: neither intermediate quantity is itself the final return.
Keep three objects separate: the expected action value, the TD error, and the final n-step tree-backup return.
Expected Action Value
The first quantity is an expected action value associated with the target policy. The formulation treats this quantity as a scalar random variable. Calling it scalar emphasizes that the policy-based action-value information is represented as one quantity that can be used compactly in later definitions. Calling it random reflects that it is introduced within the stochastic process of the algorithm rather than as a separate collection of action branches.
The target policy supplies probabilities for possible actions. Their action-value information is combined into the expected action value. The purpose is not to finish the return calculation at this point. It is to create a policy-based ingredient that the later n-step tree-backup definition can use.
TD Errors Along the Tree
The second quantity is a form of TD error, also introduced as a separate scalar random variable. Its role is different from the expected action value. The expected action value carries the target policy's action-value expectation; the TD error represents the temporal-difference part of the construction.
Tracing the construction
Suppose a tree-backup derivation is being organized over several steps. Identify what is defined first, what is defined second, and what is defined only afterward.
- 1First
Represent the target-policy expected action value as a scalar random variable.
- 2Second
Represent the relevant TD error as a separate scalar random variable.
- 3Third
Use both quantities in the definition of the n-step tree-backup return.
- 4Check
Do not rename either intermediate quantity as the return. The return is the later object constructed from them.
The construction has a strict conceptual order: expected action value, TD error, then n-step return.
Off-Policy Without Importance Sampling
The defining off-policy property of n-step tree backup is that it does not involve importance sampling. The behavior policy can generate the trajectory, while the target policy supplies the expected action-value quantity used in the tree-backup construction. The distinction between the policies is therefore handled through expectation in the backup rather than through importance-sampling ratios.
| Part of the process | Role in n-step tree backup |
|---|---|
| Behavior policy | Generates the trajectory |
| Target policy | Defines the expected action value |
| Importance sampling | Not involved in the defining tree-backup algorithm |
| Tree-backup return | Combines the introduced quantities into the n-step target |
The two policies have different roles, and the defining algorithm does not use importance sampling.
Semi-Gradient and Terminal Boundaries
The semi-gradient tree-backup algorithm is a semi-gradient version of the original n-step tree-backup method. The connection is direct: the original algorithm supplies the tree-backup construction, and the semi-gradient version applies semi-gradient methods to it. The return remains the tree-backup target; what changes is the learning setting in which that target is used.
Tree Backup and Q(σ)
n-step Q(σ) has a broader unifying role across action-value algorithms. Semi-gradient tree backup has a narrower role: it is the semi-gradient version of the original tree-backup algorithm. Therefore, do not treat the names as interchangeable. Q(σ) identifies a broader framework, while semi-gradient tree backup identifies a particular semi-gradient tree-backup method.
Mistakes in the Construction
Common mistake Treating the expected action value as the final n-step return.
What it looks likeThe target policy's expected action value is defined, and the derivation stops there.
Why it failsThe expected action value is only the first scalar random variable introduced for the construction.
Do this insteadContinue by introducing the separate TD-error quantity and then use both to define the n-step return.
Common mistake Treating the TD error and expected action value as two names for one object.
What it looks likeCalling the expected action value the TD error because both appear in the same derivation.
Why it failsThe source defines them as separate scalar random variables with different roles.
Do this insteadAssociate the expected action value with the target policy and the TD error with the temporal-difference part of the construction.
Common mistake Assuming off-policy tree backup requires importance-sampling ratios.
What it looks likeTrying to correct the behavior-policy trajectory with importance sampling before forming the tree-backup return.
Why it failsThe defining tree-backup algorithm is distinguished by its lack of importance sampling.
Do this insteadKeep the behavior policy's trajectory role separate from the target policy's expected action-value role.
Common mistake Confusing the semi-gradient version with a completely different return.
What it looks likeAssuming that introducing the semi-gradient version removes the original tree-backup construction.
Why it failsThe semi-gradient algorithm is presented as a semi-gradient version of the original method.
Do this insteadTreat the original tree-backup method as the underlying construction and the semi-gradient version as its semi-gradient application.
Common mistake Ignoring the terminal boundary condition.
What it looks likeContinuing to describe the n-step representation after t + n has reached or passed T.
Why it failsThe supplied boundary rule states that G^(n)_t = G_t whenever t + n ≥ T.
Do this insteadApply the stated boundary condition when the n-step window reaches or passes terminal time.
Check Your Understanding
Explain the construction in three sentences. Sentence one should identify the policy associated with the expected action value. Sentence two should identify the role of the separate TD-error random variable. Sentence three should explain why neither quantity alone is the final n-step return.
Hints
- Mention the target policy in the first sentence.
- Use the phrase separate scalar random variable for the TD error.
- End by describing the return as an object defined using both quantities.
A trajectory is generated by a behavior policy, but the backup uses expected action values under a target policy. What off-policy feature should you identify, and what method should you not add merely because the policies differ?
Hints
- Identify which policy generates the trajectory.
- Identify which policy supplies the expectation.
- Recall the defining absence in n-step tree backup.
Interpret the condition G^(n)_t = G_t when t + n ≥ T. Then state whether this condition describes the expected action value, the TD error, or the return representation.
Hints
- Focus on what happens when the n-step window reaches terminal time.
- The left side names an n-step return.
- The right side is the return representation used at the boundary.
Key Takeaways
- n-step tree backup introduces an expected action value as a scalar random variable under the target policy.
- A separate TD-error scalar random variable is introduced alongside it.
- The n-step tree-backup return is defined using both intermediate quantities; neither one is the return by itself.
- Tree backup is off-policy and is distinguished by its lack of importance sampling.
- The semi-gradient tree-backup algorithm is a semi-gradient version of the original method, while n-step Q(σ) has a broader unifying role.