Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 37 ยท Dynamic Programming

Asynchronous DP, Generalized Policy Iteration and Limits of DP

Learn asynchronous dynamic programming, prioritized sweeping and generalized policy iteration, compare update orders in Python and see why DP struggles with the curse of dimensionality.

The DP algorithms so far sweep through every state each time. That is synchronous-style DP, and it has two weaknesses: sweeps are expensive when there are many states, and most states may not need updating most of the time. This lesson relaxes the rules (asynchronous DP), steps back to a picture that explains almost every RL algorithm (generalized policy iteration), and ends with an honest look at where DP stops working.

Asynchronous dynamic programming

Asynchronous DP updates states in any order, any number of times, using whatever values are currently stored. There is no notion of a full sweep. The only requirement for convergence is that every state keeps being updated in the long run. This freedom helps in several ways:

  • Ordering. Update states near the goal first, so useful information travels forward immediately instead of crawling one step per sweep.
  • Focus. Update states the agent actually visits. Irrelevant states cost nothing. This idea, real-time DP, runs a DP update on the state the agent is in while it behaves in the real environment.
  • Interleaving. Mix DP updates with acting and learning, so computation and experience happen together.

Prioritized sweeping

Which state deserves the next update? The one whose value is most wrong. Prioritized sweeping keeps a queue ordered by Bellman error |max over a of lookahead(s) - v(s)|. It repeatedly takes the state with the largest error, updates it, then re-evaluates the error of its predecessors (states that can lead to it), which are the only ones whose targets just changed.

Comparing update orders

The experiment below uses a 12x12 grid with the goal in the bottom-right corner, deterministic moves and a reward of -1 per step. All variants compute the same v* (minus the Manhattan distance to the goal). Every value starts at -1000 (pessimistic), so correct values must flow outward from the goal. What differs is how many single-state backups they need.

Python Sweeps in different orders, and prioritized sweeping

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The numbers differ a lot. A synchronous sweep moves information only one step per pass, so it needs about as many sweeps as the grid is wide. An in-place sweep in the wrong direction behaves similarly, but sweeping backward from the goal lets one pass propagate the answer across the whole grid (a second pass just confirms nothing changed). Prioritized sweeping reaches the same exact answer with a single backup per state, because it only ever updates states that are known to be wrong.

Generalized policy iteration

Look again at policy iteration and value iteration. Both keep two things: a policy and a value function. Evaluation pushes the values toward the policy's true values. Improvement pushes the policy toward being greedy with respect to the values. They pull in opposing directions: when the policy changes, old values are wrong; when values change, the old policy is no longer greedy. Yet together they settle at the single point where both are consistent: an optimal policy and its value function.

Generalized policy iteration (GPI) is the name for any scheme where evaluation and improvement interact like this, regardless of granularity (full sweeps, one sweep, single states, or sampled episodes).

flowchart LR
    V["value function v"] -->|"greedy w.r.t. v (improvement)"| PI["policy pi"]
    PI -->|"evaluate pi (prediction)"| V
    PI -.-> OPT["fixed point: pi* and v*"]
    V -.-> OPT

Almost every method in this course is GPI in disguise. Monte Carlo control, SARSA, Q-learning, actor-critic: all keep a value estimate and a policy, and alternate noisily between them. Seeing that structure lets you tell algorithms apart by how they evaluate and how they improve.

The limits of DP

DP is exact, polynomial and guaranteed to converge. Why is it not enough?

  1. It needs the model. p(s', r | s, a) is rarely known.
  2. The curse of dimensionality. The number of states grows exponentially with the number of state variables. The next TryIt makes this concrete.
  3. Bootstrapping noise in function approximation. With approximators instead of tables, DP-style backups can diverge (chapter 6).
Python How fast does the state space grow?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two or four variables are trivial; twelve ten-valued variables already need terabytes and hours per sweep. Real tasks (images, robot joint angles, game boards) have far more. The way out is sampling (do not visit every state) and approximation (do not store every state's value), which is what the rest of the course develops, starting with Monte Carlo prediction.

Common mistakes

  • Treating asynchronous DP as unordered and forgetting the requirement that every state still be updated eventually.
  • Believing prioritized sweeping is always faster; the queue has overhead and pays off mostly when information is sparse.
  • Believing GPI means exact evaluation. The point is that partial, interleaved evaluation and improvement still converge.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the key idea of asynchronous DP?

    There are no full sweeps; flexibility in ordering lets computation focus where it helps.
  2. 2. How does prioritized sweeping choose the next state?

    It keeps a queue by Bellman error and re-queues the predecessors of updated states.
  3. 3. What does generalized policy iteration describe?

    GPI is the common structure of DP, Monte Carlo, TD and actor-critic methods.
  4. 4. Why does DP not scale to problems like Go or robot control?

    Exponential state spaces and unknown models call for sampling and function approximation.

Summary

  • Asynchronous DP updates states in any order, focusing computation where values are most wrong.
  • Update order matters: sweeping from the goal backward or prioritized sweeping needs far fewer backups.
  • GPI: evaluation and improvement alternate and compete until policy and values agree; nearly every RL algorithm is an instance.
  • DP is exact but needs a model and suffers from the curse of dimensionality, so we move on to learning from sampled experience.

Next: Monte Carlo Prediction