Concepts / n-step Tree Backup

n-step Tree Backup

Expected action value is defined as a scalar random variable under the target policy.

  • Programming

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.

definesingredientingredientTarget policyaction probabilitiesExpected action valuescalar random variableTD errorseparate scalar randomvariablen-step returntree-backup target
How do the two scalar random variables become ingredients of the final n-step 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.

weightsweightsweightscontributescontributescontributesTarget policyprobabilitiesAction Aaction valueAction Baction valueOther actionsaction valuesExpected action valueone scalar quantity
How does the target policy assign probabilities to possible actions and combine their action values into one scalar random variable?

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.

First: Represent the target-policy expected action value as a scalar random variable.

Second: Represent the relevant TD error as a separate scalar random variable.

Third: Use both quantities in the definition of the n-step tree-backup return.

Check: 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.

usesusescontinuescontinuescontributescontributesCurrent returnat time tExpected action valuenext stepExpected action valuelater stepn-step returnconstructed targetTD errornext stepTD errorlater step
How do expected action values and TD errors combine across the next n steps to produce the final n-step tree-backup 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.

generatesprovides experiencedefinessuppliesBehavior policygenerates trajectoryTarget policysupplies expectationObserved trajectorystates and actionsExpected action valuetarget-policy quantityTree-backup returnno importance sampling
How can the behavior policy generate the trajectory while the target policy supplies expected action values without importance-sampling ratios?
Part of the processRole in n-step tree backup
Behavior policyGenerates the trajectory
Target policyDefines the expected action value
Importance samplingNot involved in the defining tree-backup algorithm
Tree-backup returnCombines the introduced quantities into the n-step target

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.

definesappliesOriginal treebackuptree-backup algorithmSemi-gradient treebackupsemi-gradient versionn-step returntree-backup constructionFixed target useparameterized action-valuefunction
What changes when the return is used as a fixed target for a parameterized action-value function, and what remains the same as in the original algorithm?
usesgivesn-step windowt + n < TTerminal boundaryt + n ≥ TG^(n)_tn-step representationG_tsame return representation
What happens when the n-step window reaches or passes terminal time T?

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.

organizesspecifiesn-step Q(σ)broader unifying roleSemi-gradient treebackupspecific versionSampling andexpectationalgorithmic mixtureTree-backup methodsemi-gradient application
Which part controls the broader mixture of sampling and expectation, and which part specifically identifies the semi-gradient tree-backup update?

Mistakes in the Construction

  • Treating the expected action value as the final n-step return.

    The expected action value is only the first scalar random variable introduced for the construction.

    Fix: Continue by introducing the separate TD-error quantity and then use both to define the n-step return.

  • Treating the TD error and expected action value as two names for one object.

    The source defines them as separate scalar random variables with different roles.

    Fix: Associate the expected action value with the target policy and the TD error with the temporal-difference part of the construction.

  • Assuming off-policy tree backup requires importance-sampling ratios.

    The defining tree-backup algorithm is distinguished by its lack of importance sampling.

    Fix: Keep the behavior policy's trajectory role separate from the target policy's expected action-value role.

  • Confusing the semi-gradient version with a completely different return.

    The semi-gradient algorithm is presented as a semi-gradient version of the original method.

    Fix: Treat the original tree-backup method as the underlying construction and the semi-gradient version as its semi-gradient application.

  • Ignoring the terminal boundary condition.

    The supplied boundary rule states that G^(n)_t = G_t whenever t + n ≥ T.

    Fix: Apply the stated boundary condition when the n-step window reaches or passes terminal time.

Check Your Understanding

MEDIUM

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.
EASY

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.
MEDIUM

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.

Related Topics