Scaling DP: Asynchronous Updates and the Curse of Dimensionality

The cost of a full sweep

Classic DP sweeps every state on every iteration. That is wasteful: most states barely change in any given sweep, and some far-flung corner of the state space might be holding up convergence while you keep re-backing-up states that are already correct. If the state set is large, even one sweep can be unaffordable.

V(s) \leftarrow \max_a \sum_{s'} p(s' \mid s,a)\,\bigl[\,r(s,a,s') + \gamma\,V(s')\,\bigr]

Each full backup sums over every successor state s', and a sweep applies it to all states — which is exactly what gets expensive.

Asynchronous DP

Asynchronous dynamic programming drops the requirement that a sweep touch every state in lockstep. You back up states one at a time, in any order you like, reusing whatever values are current — this is in-place updating taken to its logical end. Convergence still holds, as long as every state continues to be selected for backup eventually (no state is starved forever).

The payoff: you can spend computation where it matters. Focus backups along the trajectories the agent actually visits, or near states whose values are still wildly wrong, and ignore the rest until later. This is the same generalized policy iteration spirit — progress comes from any mix of partial backups, not from rigid full passes.

Prioritized sweeping

If you can update in any order, the obvious next question is: which state should you update next? Prioritized sweeping answers it. Keep a priority queue of states ranked by how much their value is likely to change — measured by the size of the most recent bootstrapped update (the Bellman error). Always back up the highest-priority state, then bump the priority of its predecessors, since a big change here means their values are now stale.

p(s) = \Bigl|\, \max_a \sum_{s'} p(s' \mid s,a)\bigl[\,r + \gamma\,V(s')\,\bigr] - V(s) \,\Bigr|

Prioritized sweeping ranks each state by its Bellman error — how much a backup would change its value — and updates the largest first.

Pop the state with the largest pending Bellman error from the queue.
Back it up; its value jumps toward consistency.
For each predecessor, compute how much that change would shift it; insert it with that priority.
Repeat — work flows backward from where change originates.

The curse of dimensionality

Cleverer scheduling buys you a lot, but it cannot escape the deeper wall. The curse of dimensionality is that the number of states grows exponentially with the number of state variables. A problem with thirty binary features already has more states than there are atoms in your laptop's memory — you cannot store the value table, let alone sweep it. Tabular DP simply does not scale to high-dimensional or continuous problems.

|\mathcal{S}| = k^{d}

The curse of dimensionality: discretize d variables into k levels each and the number of states blows up as k to the d.

This is the wall that defines the rest of reinforcement learning. Two doors lead out. One is sample backups — give up sweeping every successor and follow sampled transitions instead (Monte Carlo and TD methods). The other is function approximation — give up the table and learn a compact parametric value function. Almost every modern method walks through one or both of those doors.

A different door entirely: linear programming

It is worth knowing that iteration is not the only way to solve a finite MDP exactly. Linear programming for MDPs casts the Bellman optimality conditions as constraints of a linear program: minimise the sum of state values subject to the value of each state being at least as large as every one-step lookahead. The solution is the optimal value function. LP solvers give worst-case polynomial-time guarantees and underpin some theory of approximate DP, though for large problems value and policy iteration are usually faster in practice.