Course contentsShow
← Machine Learning and Deep Learning
Lesson 2169 of 3,53846. Reinforcement Learning: FundamentalsFree lesson

Prioritized Sweeping

Study how to focus computational effort on states whose values are likely to change most, improving convergence speed.

Prioritized Sweeping

What You'll Learn

You'll learn how to make dynamic programming more efficient by focusing updates on states that matter most, dramatically speeding up convergence.

The Core Idea

In standard dynamic programming methods like Value Iteration, we systematically update every state's value in each sweep through the state space. But here's the insight: not all states benefit equally from updates. Some states' values are already accurate, while others are badly out of date and desperately need attention.

Prioritized Sweeping tracks which states are likely to have the largest value changes and updates those first. It maintains a priority queue of states, ranked by how much their value might change. When you update one state and discover its value shifted significantly, you add its predecessors (states that lead to it) to the queue—because their values now depend on outdated information.

How It Works

Think of it like triaging patients in an emergency room. You don't treat people in the order they arrived; you help those in critical condition first. Similarly, Prioritized Sweeping doesn't waste time on states whose values are already stable—it rushes to fix the states where value estimates are most wrong.

The algorithm:

  1. Maintain a priority queue of states, ranked by potential value change magnitude
  2. Pop the highest-priority state and perform a Bellman backup
  3. If the update was significant, add that state's predecessors to the queue with updated priorities
  4. Repeat until the queue empties or values converge

This works especially well when rewards are sparse—value information propagates backward from goal states efficiently, rather than waiting for systematic sweeps to slowly diffuse it throughout the entire state space.

Key Takeaway: Prioritized Sweeping accelerates dynamic programming by intelligently focusing computational effort on states whose values are most likely to change, using a priority queue to guide the update order rather than blindly updating all states uniformly.