Prioritized Sweeping

Spend planning backups where the Bellman error is largest, then chase the surprise backward through predecessors instead of sampling at random.

A plus 10 goal at S3 queues priority 10.0, then updates ripple to S2 at 9.0 and S1 at 8.1 in three focused backups

Why Does This Exist?

Model based planning should be cheaper than real experience, but uniform planning wastes the savings. Dyna samples stored state action pairs at random for its simulated backups. In a maze with hundreds of states, almost every sampled pair already agrees with its successor, so the Bellman error is zero and the backup changes nothing. Worse, when the agent first finds the goal, that news must travel backward one random hit at a time. Crossing $k$ steps by luck takes on the order of state space size to the $k$ draws.

Moore and Atkeson (Machine Learning, 1993), with Peng and Williams arriving independently, replaced luck with a queue. Priority is absolute Bellman error $P = \lvert R + \gamma \max_{a^{\prime}} Q(S^{\prime}, a^{\prime}) - Q(S, A) \rvert$ with discount $\gamma$ and current estimates $Q$ . Pop the largest $P$ , apply the backup, then look up every predecessor pair that leads into the changed state and queue those whose anticipated error clears a threshold $\theta$ . One surprise ripples home in a focused wave, and planning stops early when the queue empties. For the plan versus learn split behind this, read planning and learning.

Think of It Like This

Repair crews sent upstream from the burst main

A water main bursts downtown. Random patrols would keep checking quiet suburbs while pressure collapses block by block. Nobody runs a grid that way.

Dispatch queues jobs by urgency, fixes the burst first, then walks upstream: which feeder valves push water into the fixed block, and how far are their gauges off now. Those feeders jump the queue next, then their feeders after them. Quiet streets never get a truck. A threshold keeps tiny pressure wobbles off the board entirely so crews are not dispatched for noise.

Where it stops: water flows continuously while sweeping walks a discrete predecessor graph built from past transitions, and crews cannot set a full backup rate of $1.0$ the way a deterministic model backup can. The queue plus upstream chase carries over.

How It Actually Works

The agent keeps a forward model $Model(S, A) \to (R, S^{\prime})$ mapping each tried pair to its reward $R$ and next state $S^{\prime}$ , plus a predecessor registry $Pred(S)$ listing every pair known to land in $S$ . Both grow from real steps. Priority $P$ is the absolute one step error above. Pairs with $P > \theta$ enter a max heap; a pair already queued keeps the larger of old and new priority. Each planning iteration pops the max, applies $Q(S, A) \leftarrow Q(S, A) + \alpha [R + \gamma \max_{a^{\prime}} Q(S^{\prime}, a^{\prime}) - Q(S, A)]$ with step $\alpha$ , then scores every predecessor $(\bar{S}, \bar{A})$ in $Pred(S)$ as $\bar{P} = \lvert \bar{R} + \gamma \max_a Q(S, a) - Q(\bar{S}, \bar{A}) \rvert$ and queues those above $\theta$ .

Worked example

Chain $S_1 \to S_2 \to S_3 \to S_4$ goal, one action right, $\gamma = 0.9$ , $\alpha = 1.0$ , $\theta = 0.01$ . The model already knows $S_1 \to S_2$ and $S_2 \to S_3$ with reward $0$ , all $Q$ at $0$ .

Goal discovery: the agent takes $(S_3, right)$ , gets $R = 10.0$ , lands terminal. Error $P = \lvert 10.0 + 0.9 \times 0 - 0 \rvert = 10.0$ , so $(S_3, right)$ queues at $10.0$ .

Backup 1: pop $(S_3, right)$ , set $Q(S_3) = 0 + 1.0 \times 10.0 = 10.0$ . Predecessor $(S_2, right)$ scores $\lvert 0 + 0.9 \times 10.0 - 0 \rvert = 9.0$ and queues at $9.0$ .

Backup 2: pop $(S_2, right)$ , set $Q(S_2) = 9.0$ . Predecessor $(S_1, right)$ scores $\lvert 0 + 0.9 \times 9.0 - 0 \rvert = 8.1$ and queues at $8.1$ .

Backup 3: pop $(S_1, right)$ , set $Q(S_1) = 8.1$ . No predecessors remain, the queue empties, planning halts. Final values $[8.1, 9.0, 10.0]$ match the diagram. Uniform Dyna would need hundreds of random draws to land this exact backward order.

Code

The snippet replays the three priorities with the standard library only.

1gamma = 0.92
3q3 = 0.0 + (10.0 + gamma * 0.0 - 0.0)4print(round(q3, 4))  # -> 10.05
6q2 = 0.0 + (0.0 + gamma * 10.0 - 0.0)7print(round(q2, 4))  # -> 9.08
9q1 = 0.0 + (0.0 + gamma * 9.0 - 0.0)10print(round(q1, 4))  # -> 8.1

Each print matches the hand derived chain $10.0$ , $9.0$ , $8.1$ with decay factor $0.9$ per hop.

Watch Out For

Threshold set blind to reward scale

The symptom is either a heap that never drains or a wave that dies after one hop. Near zero $\theta$ admits numerical dust in stochastic graphs and heap costs dominate runtime; oversized $\theta$ kills the geometrically decaying wave ( $\gamma^k P$ ) before it reaches the start, so distant states never hear about the goal.

Scale $\theta$ to rewards, around $10^{-3}$ times the reward range, and cap planning steps per real step. In stochastic tasks keep expected transitions rather than overwriting with the last sample, or noise spikes keep requeueing phantom urgency.

The Quick Version

Priority is absolute Bellman error, and a max heap always serves the most wrong pair next.
A predecessor registry turns each backup into new queue entries one step upstream.
The plus 10 goal crosses three states in exactly three backups: $10.0$ , $9.0$ , $8.1$ .
Threshold $\theta$ prunes settled pairs so planning halts when there is nothing worth fixing.
Uniform Dyna needs hundreds of draws for the same cascade that sweeping aims directly.