Does it require a perfect model?

No, learned models are common, but model errors affect planning quality.

Does it always find the optimal policy?

Not merely because priorities are used. Guarantees depend on the learning and planning assumptions, update coverage, and available computation.

Can a lower-valued state have higher priority?

Yes. Priority measures update importance, not the value itself.

AI Glossary / Graphs and symbolic AI / Advanced

Prioritized sweeping

Definition

Prioritized sweeping is a model-based reinforcement-learning and planning technique that concentrates value updates on states likely to be affected by important new information. It uses a priority queue and predecessor relationships to propagate changes backward through a transition model, directing limited computation toward consequential updates.

What it means

An agent may discover that a destination is more rewarding than previously estimated. That discovery should also change the estimated value of states leading toward it. Updating every known state equally can spend time on regions unaffected by the discovery.
Prioritized sweeping asks which earlier states most need reconsideration. A predecessor is a state from which an action can lead to the state whose value changed. The method gives those predecessors attention according to a chosen measure of likely impact. Priority refers to computational urgency, not necessarily the largest state value or the most attractive action.

How it works

The agent maintains a transition and reward model, value estimates, and information about predecessor states or state-action pairs. New experience can change the model or reveal a discrepancy between an existing estimate and a model-based backup target.
Candidates enter a priority queue. A planning step removes a high-priority candidate and updates its estimate. If this changes a state's value, the algorithm considers its predecessors and updates their priorities. Repeated planning steps carry important information backward along relevant paths.
Implementations differ. Priorities may reflect a Bellman residual, the size of a value change weighted by transition probability, or another approximation. They may queue states or state-action pairs and use thresholds to ignore tiny changes. Planning stops when its budget is exhausted or no sufficiently important candidate remains. These choices affect both computational cost and the accuracy achieved within a budget.

Three practical examples

A simulated warehouse robot discovers that a loading station now provides a higher task reward. Planning revisits routes that can reach that station, rather than spending equal effort on unrelated aisles.
A maintenance simulator revises the expected consequence of a machine failure. Predecessor operating conditions receive additional updates because their long-term costs may have changed.
A game agent learns that an action near a goal is unusually effective. Backward propagation helps improve estimates of earlier positions that can lead to that opportunity.

Think of it this way

Imagine a train connection changes. A timetable planner first checks journeys that depend on that connection, then journeys feeding those journeys. Rechecking an unrelated branch is less urgent. The analogy captures dependency-driven work, although reinforcement learning propagates numerical estimates rather than timetable notices.

Worked example

Consider a known episodic model with one available action per nonterminal state. Transitions are A to B, B to C, and C to terminal state T. State D leads to C with probability 0.2 and directly to T with probability 0.8. All rewards are zero except the newly learned reward of 10 on C to T.
Let the discount factor be 0.9, keep V(T)=0, and initially set all other values to zero. For this illustration, priority is the absolute difference between the current value and its expected one-step backup target.
C initially has priority 10. Updating it gives V(C)=10. B's target becomes 0+0.9×10=9, while D's becomes 0.2×0.9×10=1.8. Thus B receives attention before D.
After updating B to 9, A's target becomes 0.9×9=8.1. A now outranks D, so the update order is C, B, A, D. Final values are 10, 9, 8.1, and 1.8 respectively. Each discount corresponds to another transition before receiving the reward.
A budget of two backups completes only C and B; A and D still need updates. This is a residual-priority illustration, not an exact reproduction of every historical implementation. Its arithmetic demonstrates targeted propagation, not a measured runtime advantage.

Illustrative case study

A fictional equipment-rental team tests dispatch decisions in a simulator. It discovers that late returns at one depot create larger downstream costs than originally modeled. Uniform planning repeatedly updates many states whose transitions cannot reach that depot within the modeled episode.
The team adds predecessor tracking and prioritized backups. It records which estimates change, the number of backups, queue-management time, and resulting policy performance under the same planning budget. It also tests decreases in expected reward, since unfavorable discoveries must propagate too.
If predecessor maintenance costs more than the saved backups, the change may offer little practical benefit. The example illustrates an evaluation design; it does not report an observed improvement or assume that concentrated planning guarantees a better deployed policy.

Common misconceptions and mistakes

Prioritized sweeping is not the same as prioritized experience replay. Sweeping uses a model and predecessor dependencies to organize planning; replay prioritizes stored experience samples for learning updates.
It does not simply follow promising successors forward. Changes propagate toward predecessors whose estimates depend on those successors.
A small queue does not prove the real environment is well understood. An inaccurate model, missing predecessors, or an aggressive threshold can hide important errors. Large estimated impact is also not equivalent to high confidence in the underlying data.

Business use

Use the method when model-based planning is valuable but backup computation is constrained. Candidate settings include simulated operations, routing, and maintenance decisions with identifiable dependencies. Compare total computation and decision quality, including model upkeep and queue overhead. Rapidly changing or poorly observed environments require particular care because efficiently propagating an incorrect model still produces unreliable estimates.

Check your understanding

Why does B get updated before D in the example?

Answer: Its residual is 9, compared with D's 1.8.

Why does A subsequently move ahead of D?

Answer: Updating B creates an 8.1 residual at A.

What remains after two backups?

Answer: A and D still have outdated estimates.

Related terms

Learn next

Study Bellman backups and Dyna first. Then compare residual-based scheduling with uniform planning under equal total computation, checking both model accuracy and the cost of maintaining predecessor information.

Sources

Moore and Atkeson, Memory-Based Reinforcement Learning: Efficient Computation with Prioritized Sweeping, original research paper: https://proceedings.neurips.cc/paper/1992/file/55743cc0393b1cb4b8b37d09ae48d097-Paper.pdf AIMA glossary, prioritized sweeping terminology: https://github.com/aimacode/aima-glossary

Previous: Prioritized experience replay Next: Priority queue