Tree-Backup Algorithm

Why Does This Exist?

Off-policy learning means collecting experience with one exploratory behavior policy $b$ while evaluating a different target policy $\pi$. Stretch that over multiple steps and two classic fixes both break.

The first fix multiplies importance sampling ratios down the trajectory, $\rho_{t:t+n-1} = \prod_k \pi(A_k \mid S_k) / b(A_k \mid S_k)$. When the policies differ, the product collapses toward zero (throwing the experience away) or explodes (injecting wild variance). The second fix, used by Watkins's $Q(\lambda)$, cuts the trace to zero at the first exploratory action, which in a curious agent means every trace dies after a step or two and the method degrades to slow single-step learning. Both failure modes are covered on their own pages: Watkins's Q lambda and n-step TD prediction.

Tree backup takes a third route: never correct the trajectory at all. At each visited state, score every untaken action by its exact expectation under the target policy, and let only the taken action continue down the sampled path. No ratios appear anywhere, so there is nothing to explode. The one-step version of this idea is Expected SARSA; tree backup is its multi-step extension.

Think of It Like This

How It Actually Works

The tree shape

The update targets one pair $(S_t, A_t)$. Picture the trajectory as a tree: each visited state fans out into all actions, but only the taken action grows deeper. Side branches end immediately in their current $Q$ estimates. The taken spine keeps sampling rewards and states until the horizon $n$ runs out, where the leaf closes with a full expectation over all actions.

The recursion

For horizon $n = 1$ the return is exactly Expected SARSA:

$G_{t:t+1} = R_{t+1} + \gamma \sum_a \pi(a \mid S_{t+1}) Q(S_{t+1}, a)$

where $R_{t+1}$ is the observed reward, $\gamma$ in $[0, 1]$ discounts the future, $\pi(a \mid S_{t+1})$ is the target policy's probability for action $a$, and $Q$ holds current estimates.

For $n \ge 2$, fold one level deeper. Split state $S_{t+1}$ into the untaken actions (closed with their expectations) and the taken action $A_{t+1}$ (continued recursively, scaled by its own target probability):

$G_{t:t+n} = R_{t+1} + \gamma \sum_{a \neq A_{t+1}} \pi(a \mid S_{t+1}) Q(S_{t+1}, a) + \gamma\, \pi(A_{t+1} \mid S_{t+1})\, G_{t+1:t+n}$

The leaf level uses the full expectation over all actions, and a terminal state contributes zero beyond its reward. Then update the root the usual TD way:

$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\, [G_{t:t+n} - Q(S_t, A_t)]$

with step size $\alpha$ in $(0, 1]$. No behavior probabilities appear anywhere: because every branch is weighted by $\pi$ and the weights over all actions sum to 1, the backup is exact for the target policy regardless of what $b$ did. When the target is greedy, an exploratory action simply gets weight $\pi = 0$ and the recursion ends there on its own, no special cutoff needed. Sampling the next action fully gives multi-step SARSA; taking expectations gives tree backup; the $Q(\sigma)$ blend interpolates between the two per step.

Worked example: a two-step backup by hand

Trajectory: $S_0$ with action $A_0$ pays $R_1 = 2.0$ into $S_1$; action $A_1 = a_0$ pays $R_2 = 4.0$ into leaf $S_2$. Discount $\gamma = 0.9$, step size $\alpha = 0.2$, starting estimate $Q(S_0, A_0) = 4.0000$.

At $S_1$ the target policy says $\pi(a_0 \mid S_1) = 0.60$, $\pi(a_1 \mid S_1) = 0.40$, with estimates $Q(S_1, a_0) = 5.0000$, $Q(S_1, a_1) = 3.0000$. At leaf $S_2$: $\pi(a_0) = 0.70$, $\pi(a_1) = 0.30$, values $8.0000$ and $6.0000$.

Step 1, leaf expectation at $S_2$: $0.70(8.0000) + 0.30(6.0000) = 5.6000 + 1.8000 = 7.4000$.

Step 2, one-step return from $(S_1, a_0)$: $G_{1:2} = 4.0000 + 0.9(7.4000) = 4.0000 + 6.6600 = 10.6600$.

Step 3, untaken branch at $S_1$ (action $a_1$ was not taken): $0.40 \times 3.0000 = 1.2000$. Taken spine weighted: $0.60 \times 10.6600 = 6.3960$. Combined: $1.2000 + 6.3960 = 7.5960$.

Step 4, full two-step return: $G_{0:2} = 2.0000 + 0.9(7.5960) = 2.0000 + 6.8364 = 8.8364$.

Step 5, update: $Q(S_0, A_0) \leftarrow 4.0000 + 0.2(8.8364 - 4.0000) = 4.0000 + 0.9673 = 4.9673$.

Every quantity stayed bounded, and no ratio was ever computed. The diagram above draws steps 3 and 4; the code below replays all five.

Code

The snippet folds the recursion backward from the leaf, then applies the update, printing the worked example's numbers.

1from typing import Dict, List, Tuple2
3
4def tree_backup_return(5    rewards: List[float],6    taken: List[str],7    states: List[str],8    policy: Dict[str, Dict[str, float]],9    q: Dict[Tuple[str, str], float],10    gamma: float,11) -> float:12    """n-step tree-backup return, folded backward from the leaf state."""13    actions = sorted(policy[states[-1]].keys())14    leaf = states[-1]15    current = rewards[-1] + gamma * sum(policy[leaf][a] * q[(leaf, a)] for a in actions)16    for k in range(len(rewards) - 2, -1, -1):17        s_next = states[k + 1]18        untaken = sum(19            policy[s_next][a] * q[(s_next, a)] for a in actions if a != taken[k + 1]20        )21        current = rewards[k] + gamma * (untaken + policy[s_next][taken[k + 1]] * current)22    return current23
24
25if __name__ == "__main__":26    rewards = [2.0, 4.0]27    taken = ["a0", "a0"]28    states = ["S0", "S1", "S2"]29    policy = {30        "S1": {"a0": 0.6, "a1": 0.4},31        "S2": {"a0": 0.7, "a1": 0.3},32    }33    q = {("S1", "a0"): 5.0, ("S1", "a1"): 3.0, ("S2", "a0"): 8.0, ("S2", "a1"): 6.0}34    g = tree_backup_return(rewards, taken, states, policy, q, 0.9)35    print(round(g, 4))  # -> 8.836436    print(round(4.0 + 0.2 * (g - 4.0), 4))  # -> 4.9673

Watch Out For

The Quick Version

• Tree backup does multi-step off-policy learning with zero importance sampling ratios, so nothing explodes when behavior and target policies differ.
• Untaken actions at each state contribute their exact target-policy expectation; only the taken action continues down the sampled spine, scaled by its own target probability.
• The one-step case is Expected SARSA, and the recursion closes leaves with a full expectation over all actions.
• On the worked trace (rewards 2.0 and 4.0, discount 0.9) the two-step return is 8.8364 and the root estimate moves from 4.0000 to 4.9673.
• Never add importance ratios to the recursion, and never hand-cut traces at exploratory actions: the target weights already handle both.

What to Read Next

• Watkins's Q(lambda) Algorithm
• n-Step TD Prediction in RL
• Expected SARSA