Does it need behavior-policy probabilities?

The standard tree-backup return does not require them for importance ratios.

Does it eliminate random rewards?

No. Rewards and state transitions along the trajectory remain sampled.

What is its connection to Q(sigma)?

Setting sigma to zero at every step yields tree backup.

AI Glossary / Reinforcement learning and robotics / Advanced

N-step tree backup

Definition

N-step tree backup is a multi-step action-value learning method that combines an observed trajectory with expected values for actions not taken. At each intermediate state, it weights action branches by the target policy's probabilities. The sampled branch carries information from later experience, while the other branches use existing action-value estimates. The standard method can learn off-policy without importance-sampling ratios.

What it means

A trajectory reveals only the actions actually taken and the rewards that followed. Tree backup uses that experience without pretending that the same sequence represents every action the target policy might choose.

At each visited state, the target policy assigns probability to several possible actions. The observed action gets a deeper return; unobserved alternatives retain their current estimates. Combining these branches repeatedly produces the tree-shaped backup that gives the method its name.

It does not require physically trying every branch or having a transition model for unchosen actions. The unchosen branches contribute estimates, so their quality still matters.

How it works

Start at the end of the chosen backup horizon. At a genuine terminal transition, use its reward without a continuation value. At a nonterminal horizon, use the appropriate expected action-value bootstrap under the target policy.

Work backward along the sampled trajectory. At each earlier link, add the observed reward to gamma times a mixture: the target probability of the sampled next action times its deeper return, plus the target-weighted Q-values of the other next actions.

The same return can be expressed as a sum of Expected Sarsa TD errors. Later errors are multiplied by discount factors and by target probabilities of the intervening sampled actions. This attenuates the influence of a long sequence that the target policy would rarely follow.

For one step, the construction reduces to Expected Sarsa. For a greedy target policy, a sampled nongreedy action can stop later corrections from propagating through that branch because its target probability is zero. Avoid treating this as permission to ignore data coverage: useful learning still needs relevant state-action experience and appropriate representation and update conditions.

Three practical examples

1. A simulator evaluates a target policy using exploratory trajectories while avoiding products of potentially large importance-sampling ratios.

2. A tabular control experiment compares tree backup with n-step Sarsa to study reliance on alternative-action estimates.

3. A learning diagnostic traces how small target action probabilities reduce the contribution of rewards observed several steps later.

Think of it this way

Think of updating a route estimate using one completed journey. At each junction, retain forecasts for roads not traveled and replace the traveled road's forecast with more detailed downstream evidence. Weight all roads by how often the intended traveler would choose them. The result combines observed experience with forecasts rather than treating the one journey as the only possible future.

Worked example

Consider an original three-transition example with gamma equal to 0.5 and all Q estimates held fixed. The initial state-action value is 1. Its transition gives reward 2 and reaches S1.

At S1, the sampled action A has target probability 0.4 and Q-value 3. Alternative B has probability 0.6 and Q-value 5. Taking A gives reward 1 and reaches S2.

At S2, the sampled action C has target probability 0.25 and Q-value 4. Alternative D has probability 0.75 and Q-value 8. Taking C gives reward 6 and terminates.

Work backward. The deepest return is 6. At S1's sampled action, the deeper target is 1 plus 0.5 times [0.25 times 6 plus 0.75 times 8], giving 4.75. At the initial pair, the target becomes 2 plus 0.5 times [0.4 times 4.75 plus 0.6 times 5], giving 4.45.

A TD-error calculation checks the same result. Expected values at S1 and S2 are 4.2 and 7. The three Expected Sarsa errors are 3.1, 1.5 and 2. Their propagation coefficients are 1, 0.5 times 0.4, and 0.5 squared times 0.4 times 0.25. Thus the target is 1 plus 3.1 plus 0.2 times 1.5 plus 0.025 times 2, again 4.45.

With learning rate 0.2, the initial estimate becomes 1 plus 0.2 times (4.45 minus 1), or 1.69. A fully sampled three-step terminal return would instead be 2 plus 0.5 times 1 plus 0.25 times 6, or 4. The difference comes from tree backup's alternative-action estimates. Neither number is declared the unknown true action value.

Illustrative case study

In a fictional project, Birch Simulation evaluates a dispatch policy using deliberately exploratory behavior. The team chooses tree backup to study multi-step learning without large importance-ratio products.

Early results improve slowly because the target policy assigns very low probability to many exploratory action sequences. The team inspects the resulting propagation coefficients and compares shorter backups and better initial action estimates. It reports both learning accuracy and action coverage. Avoiding importance ratios solves one source of variability; it does not ensure that every collected trajectory contributes strongly to the target policy's estimates.

Common misconceptions and mistakes

Tree backup is not exhaustive tree search. Unchosen actions contribute Q estimates rather than simulated future trajectories.

It is not equivalent to taking an expectation only at the last step of an otherwise sampled return. The branch weighting happens throughout the backup.

No importance ratios does not mean no off-policy assumptions or guaranteed stability with arbitrary function approximation. Target probabilities, coverage and update rules remain important. Also, zero target probability for a sampled action can suppress later corrections without implying that the observed reward itself was erroneous.

Business use

The method is relevant when teams reuse exploratory experience to learn about another policy and want to compare alternatives to importance-weighted multi-step targets. Useful evaluation includes prediction quality, variability and how far delayed information actually propagates. Inspect whether the target policy's probabilities make long backups ineffective, and whether inaccurate estimates for unchosen actions dominate the resulting targets.

Check your understanding

Why is the last TD error weighted by only 0.025?

Answer: Two discounts and two target action probabilities multiply along its path.

Why is the target different from the sampled return of 4?

Answer: It also includes estimates for actions B and D.

Related terms

Expected SARSA
n-step return
Importance sampling
off-policy learning
Q(sigma)
target policy and action-value function

Learn next

Next, set the target probability of A to zero and inspect which later corrections disappear. Then compare tree backup with Retrace on the same trajectory.

Sources

Primary source: Kristopher De Asis and colleagues, Multi-Step Reinforcement Learning: A Unifying Algorithm, tree-backup section: https://arxiv.org/pdf/1703.01327

The three-transition calculation and fictional case are original teaching material. Values and target probabilities are held fixed throughout the worked backup.

Previous: n-step return Next: Naimi - Trehel algorithm