Dynamic Programming: Asynchronous DP and Generalized Policy Iteration

This builds on Dynamic Programming, which developed policy evaluation, policy improvement, and the two classic algorithms that alternate them — policy iteration and value iteration. Both of those sweep the entire state set on every pass. Here we loosen that schedule, name the general pattern behind almost every RL method, and place DP among its competitors.

Asynchronous dynamic programming

Synchronous DP sweeps the entire state set on every pass. When $|\mathcal{S}|$ is large this is prohibitive: backgammon has over $10^{20}$ states, and at $10^6$ updates per second a single sweep would take on the order of a thousand years.

Asynchronous DP algorithms drop the systematic sweep. They are in-place iterative methods that back up states in any order, using whatever values are currently available; some states may be updated many times before others are touched once. Convergence requires only that every state be updated infinitely often — no state may be ignored past some point — but within that constraint the order is free.

In-place asynchronous value iteration. On step $k$ back up a single state $s_k$ by the value-iteration rule,

reading the latest $V$ for successors. For $0\le \gamma <1$ this converges to $v_{\ast }$ provided every state appears in $\{s_k\}$ infinitely often. Avoiding sweeps does not by itself buy less computation, but it buys flexibility: order updates to propagate value efficiently, skip states irrelevant to optimal behavior, and interleave DP with real-time interaction. Running updates on the states an agent actually visits focuses computation where it matters, a recurring theme in reinforcement learning.

Generalized policy iteration

Every algorithm in this lesson and the last is the same two operations — evaluation and improvement — run at different granularities. That abstraction has a name.

Evaluation drives the value function toward consistency with the current policy, $V\to v_{\pi }$; improvement drives the policy toward greediness with respect to the current value function, $\pi \to \mathrm{greedy}(V)$. The three algorithms differ only in how finely the two are interleaved:

As long as both processes keep updating all states, the outcome is identical: convergence to $v_{\ast }$ and an optimal policy.

Generalized policy iteration (GPI) names this idea in the abstract: let evaluation and improvement interact at whatever granularity. Almost every reinforcement-learning method is a form of GPI — each carries an identifiable policy and value function, with the policy driven toward greediness and the value function driven toward the policy's true values.¹

The two processes both compete and cooperate. They compete because they pull in opposite directions: greedifying $\pi$ for $V$ generally makes $V$ wrong for the new policy, and correcting $V$ for $\pi$ generally makes $\pi$ no longer greedy. Yet they cooperate, because both stabilize only at one joint solution: $V$ stops moving only when $V=v_{\pi }$, and $\pi$ stops moving only when $\pi =\mathrm{greedy}(V)$. When neither moves, $\pi$ is greedy for its own value function, and that joint fixed point restates the Bellman optimality equation $V={\max }_a{\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma V(s^{\prime })]$ — so $\pi ={\pi }_{\ast }$ and $V=v_{\ast }$. Geometrically, two non-orthogonal lines in value space (one for consistency, one for greediness); each process projects the joint state onto its own line, so progress toward one goal costs a little of the other, yet the alternation still converges to their intersection, the optimum.

Bootstrapping, efficiency, and the curse of dimensionality

Two DP traits reappear in every later method: where its update draws its target, and how it scales.

The first is bootstrapping: every DP update computes a state's value from estimates of its successors' values, not from returns played out to termination. The evaluation update

leans on the current $V(s^{\prime })$, itself only an estimate. Two features are entangled here — a model and bootstrapping — and the next two chapters separate them:

The two features are separable and can be mixed.

The second is efficiency. DP finds an optimal policy in time polynomial in the number of states $n$ and actions $k$, even though the number of deterministic policies is $k^n$. DP is therefore exponentially faster than direct search over policy space, which must examine each of those $k^n$ policies. Linear programming also solves MDPs with sometimes-better worst-case guarantees, but becomes impractical at a state count roughly $100\times$ smaller. For the largest problems, only DP methods are feasible.

DP is often said to suffer the curse of dimensionality: the state count grows exponentially in the number of state variables. This is real but is a property of the problem, not of DP as a solution method — DP handles large state spaces comparatively better than direct search or linear programming. In practice DP solves MDPs with millions of states, and both policy iteration and value iteration converge far faster than their worst-case bounds, especially from a good initial value function or policy. On the largest problems, asynchronous methods are preferred, since even one synchronous sweep can be too expensive.

Beyond exact sweeps: approximate and neural dynamic programming

Classical DP assumes two luxuries: an affordable full sweep, and one stored value per state in a table. The half-century of work since Bellman has kept the equation-becomes-assignment core while dropping each cost that makes exact DP impractical: the full sweep and the tabular value function.² Three threads are worth tracing past Sutton and Barto.

Ordering the updates. Asynchronous DP frees the update order, and the natural question is which order propagates value fastest. Moore and Atkeson's prioritized sweeping answers it: keep a priority queue of states whose Bellman error is large, and always update the most-urgent state next, propagating changes backward from where value just moved.³ On problems where the interesting dynamics touch a small part of a large state space, prioritized sweeping reaches optimality with an order of magnitude fewer updates than uniform sweeps — the same backward-focusing idea reappears in the planning lesson as a way to focus simulated experience. Barto, Bradtke, and Singh's real-time DP pushes the idea further: run asynchronous value-iteration updates only on the states an agent actually visits along trajectories, and for stochastic shortest-path problems it converges to a policy optimal on the relevant states without ever sweeping the irrelevant ones.⁴

Approximating the value function. The tabular assumption fails the moment the state space is continuous or astronomically large. Bertsekas and Tsitsiklis's neuro-dynamic programming recasts DP with the value function replaced by a parametric approximator $\hat{v}(\cdot ,\mathbf{w})$ — the bridge from exact DP to the function-approximation methods of the rest of the course, and the theoretical home of approximate value iteration.⁵ Writing $T$ for the Bellman optimality operator and $\Pi$ for projection onto the representable functions, the update becomes the projected backup $\hat{v}\leftarrow \Pi T\hat{v}$, whose fixed point is the best representable approximation to $v_{\ast }$ rather than $v_{\ast }$ itself.

DP as a differentiable layer. A more recent turn treats the value-iteration recurrence itself as a computation to learn through. Tamar and colleagues' Value Iteration Networks embed a fixed number of value-iteration sweeps as a differentiable module inside a neural network, so a policy network can learn to plan on a learned, approximate model by backpropagating through the sweeps.⁶ And the model-based deep-RL system MuZero learns a latent dynamics model and runs a DP-flavored lookahead (Monte Carlo tree search over the learned model) entirely in a learned representation, with no access to the true rules of the game.⁷ Each of these keeps the DP skeleton — a Bellman backup iterated toward a fixed point — and swaps the exact tabular pieces for learned, approximate ones.

DP needs the model, and that is why it serves more as theory than as practical algorithm. But it defines the goal precisely: an optimal value function that satisfies the Bellman optimality equation, reached by letting evaluation and improvement interact. Everything in the tabular methods that follow is a way to run that same GPI loop when the model is missing and the sweeps must be replaced by sampled experience.