Bellman backup

A backup recomputes the state-value of a state from the value estimate of its successor states, via a one step lookahead through a model:

$$V(s)\leftarrow \underset{a}{\max }[\hat{r}(s,a)+\gamma \sum _{s^{\prime }}\hat{p}(s^{\prime }\mid s,a)V(s^{\prime })]$$

$\hat{r}(s,a)$ … expected immediate reward
$\hat{p}(s^{\prime }\mid s,a)$ … transition probabilities
$\hat{r},\hat{p}$ … the model: the agent’s estimate of the environment’s true reward and dynamics (a world model)
$\gamma$ … discount
We set the value to the maximum reward, for each action available in $s$, along the way plus discounted value of where you’d land;
This applies the Bellman optimality operator at a single state.

The name comes from the backup diagram: $s$ at the root, actions below it, possible next states below those. Values flow from the leaves backwards up the tree, against the direction of time, into the root.

One backup improves one state’s estimate by one step of lookahead, and propagates information one step further back: once $s$ is backed up, backing up $s$‘s predecessors passes the improvement along. Planning is just many backups: value iteration backs up states again and again until no backup changes anything anymore; the values are then consistent with the model.

When and where to back up is open (backups are asynchronous background compute: planning runs in parallel with acting, on spare cycles, and converges regardless of order as long as all relevant states keep getting selected). Choosing the states, called search control, is what makes planning feasible in a big world.

With function approximation there is no table entry to overwrite: $V$ becomes $\hat{v}(s,\mathbf{w})$, values are computed from shared weights $\mathbf{w}$, and changing $\mathbf{w}$ moves many states’ values at once. The backup target is computed as before, now called the backed-up value of $(s,a)$:

$$b(s,a,\mathbf{w})=\hat{r}(s,a)+\gamma \sum _{s^{\prime }}\hat{p}(s^{\prime }\mid s,a)\hat{v}(s^{\prime },\mathbf{w})$$

and the update is a gradient step of $\mathbf{w}$ that moves $\hat{v}(s,\mathbf{w})$ toward that target:

$$\mathbf{w}\leftarrow \mathbf{w}+\alpha [\underset{a}{\max }b(s,a,\mathbf{w})-\hat{v}(s,\mathbf{w})]{\nabla }_{\mathbf{w}}\hat{v}(s,\mathbf{w})$$

$\alpha$ … step size
${\max }_{a}b(s,a,\mathbf{w})-\hat{v}(s,\mathbf{w})$ … the error: what the value should be after one step of lookahead, minus what it currently is.
Note that this value is not bounded, and prone to explode, see deadly triad.
The tabular backup is the special case where the step fully overwrites one entry, and it doesn’t run into the problem above, because true values are bounded (geometric series: at most max-reward divided by one minus gamma). And the backup operator is a contraction: applying it shrinks the distance to the true values by a factor of gamma each time.

A TD update is the model-free version, a sample backup: instead of averaging over all successors with the model, use the one successor that actually happened.
With option models a backup keeps the same form but jumps a whole behavior instead of one timestep.