--- title: "Dynamic Programming: Asynchronous DP and Generalized Policy Iteration" module: Tabular Solution Methods moduleNumber: 2 lessonNumber: 2 order: 202 summary: > Policy and value iteration both sweep the entire state set on every pass, which is impossible once the state space is huge. This lesson loosens the schedule: asynchronous DP updates states in any order, generalized policy iteration names the alternation of evaluation and improvement that underlies nearly every RL method, and a look at efficiency and the curse of dimensionality places DP among the alternatives. We close past Sutton & Barto with prioritized sweeping, neuro-dynamic programming, value-iteration networks, and MuZero. topics: [Tabular Methods] sources: - book: Sutton & Barto ref: "§4.5 Asynchronous Dynamic Programming; §4.6 Generalized Policy Iteration; §4.7 Efficiency of Dynamic Programming; §4.8 Summary" --- This builds on [Dynamic Programming](/reinforcement-learning/tabular-methods/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. $$ % caption: A synchronous DP sweep (top) updates every state in a fixed pass before % repeating; asynchronous DP (bottom) updates states in any order, some far more % often than others, using out-of-date values from neighbors — yet still converges % if every state keeps getting updated. \begin{tikzpicture}[>=stealth, font=\footnotesize, cell/.style={draw, minimum size=6mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % synchronous row \node[anchor=east, font=\scriptsize] at (-0.25,0) {synchronous}; \foreach \i in {0,...,7} \node[cell] at (\i*0.72,0) {}; \draw[->, acc, thick] (-0.1,-0.55) -- (5.14,-0.55) node[midway, below, font=\scriptsize] {one full sweep, left to right}; % asynchronous row \node[anchor=east, font=\scriptsize] at (-0.25,-1.7) {asynchronous}; \foreach \i in {0,...,7} \node[cell] at (\i*0.72,-1.7) {}; % highlight a few updated-often cells \foreach \i in {2,5,3} \node[cell, draw=acc, thick, fill=acc!12] at (\i*0.72,-1.7) {}; \node[anchor=north west, align=left, font=\scriptsize] at (-0.1,-2.25) {any order; some cells revisited before others are touched}; \end{tikzpicture} $$ **In-place asynchronous value iteration.** On step $k$ back up a single state $s_k$ by the value-iteration rule, $$ V(s_k) \gets \max_a \sum_{s',r} p(s',r \mid s_k, a)\big[\,r + \gamma V(s')\,\big], $$ 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 \greedy(V)$. The three algorithms differ only in how finely the two are interleaved: | Method | Evaluation granularity | Improvement granularity | | --- | --- | --- | | Policy iteration | full evaluation to $v_\pi$ | one full greedification | | Value iteration | one sweep | one greedification per sweep | | Asynchronous DP | per state | per state | 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.[^sb-gpi] $$ % caption: Generalized policy iteration: evaluation drives $V$ toward $v_\pi$ while % improvement drives $\pi$ toward greedy(V). The two processes fight — each undoes % a little of the other's work — but converge together at the single joint fixed % point where $\pi$ is greedy for $V$ and $V$ is correct for $\pi$: the optimum. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % two labelled nodes \node[font=\normalsize] (pi) at (-2.4,0) {pi}; \node[font=\normalsize] (V) at (2.4,0) {V}; % top arc: evaluation (pi -> V) \draw[->, acc, thick] (pi) to[bend left=42] node[midway, above, font=\scriptsize] {evaluation: V toward v-pi} (V); % bottom arc: improvement (V -> pi) \draw[->, red, thick] (V) to[bend left=42] node[midway, below, font=\scriptsize] {improvement: pi toward greedy(V)} (pi); % joint solution below \node[anchor=north, font=\scriptsize, align=center] at (0,-1.9) {stabilizes only at pi-star, v-star\\(greedy and consistent at once)}; \end{tikzpicture} $$ 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 = \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',r} p(s',r\mid s,a)[r+\gamma V(s')]$ — so $\pi = \pi_*$ and $V = v_*$. 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 $$ V(s) \gets \sum_a \pi(a \mid s)\sum_{s',r} p(s',r \mid s,a)\big[\,r + \gamma V(s')\,\big] $$ leans on the current $V(s')$, itself only an estimate. Two features are entangled here — a model and bootstrapping — and the next two chapters separate them: | Method | Model | Bootstraps | | --- | --- | --- | | Dynamic programming | required | yes | | [Monte Carlo](/reinforcement-learning/tabular-methods/monte-carlo-methods) | not needed | no | | [Temporal difference](/reinforcement-learning/tabular-methods/temporal-difference-learning) | not needed | yes | The two features are separable and can be mixed. > **Definition (Bootstrapping).** Updating an estimate on the basis of other > estimates, rather than on complete, unbiased returns. DP bootstraps fully: each > value is backed up from successors' current values. 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. > **Definition (Curse of dimensionality).** The exponential growth of the state > count as the number of state variables increases. It bounds any exact method, DP > included, but is a property of the problem's dimensionality rather than a special > weakness of DP. ## 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.[^bellman] 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.[^moore] 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](/reinforcement-learning/tabular-methods/planning-and-learning) 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.[^rtdp] **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](/reinforcement-learning/approximation/on-policy-prediction) of the rest of the course, and the theoretical home of approximate value iteration.[^ndp] Writing $T$ for the Bellman optimality operator and $\Pi$ for projection onto the representable functions, the update becomes the projected backup $\hat v \gets \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.[^vin] 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.[^muzero] 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. $$ % caption: The lineage from exact DP. Exact tabular DP relaxes along two axes: the % update order (asynchronous DP, prioritized sweeping, real-time DP focus effort on % high-error or visited states) and the value representation (neuro-dynamic % programming, value-iteration networks, MuZero replace the table with a learned % approximator). Every descendant keeps the Bellman-backup fixed point. \begin{tikzpicture}[>=stealth, font=\footnotesize, box/.style={draw, minimum width=30mm, minimum height=9mm, align=center, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} \node[box, draw=acc, text=acc, thick] (exact) at (0,0) {exact tabular DP\\(sweep + table)}; % axis 1: ordering \node[box] (async) at (5.4,1.6) {asynchronous /\\prioritized / RTDP}; \node[anchor=south, font=\scriptsize, text=black] at (2.7,1.9) {relax the update order}; \draw[->, thick] (exact) -- (async); % axis 2: representation \node[box, draw=red, text=red] (approx) at (5.4,-1.6) {neuro-DP / VIN /\\MuZero}; \node[anchor=north, font=\scriptsize, text=black] at (2.7,-1.9) {relax the table}; \draw[->, red, thick] (exact) -- (approx); \end{tikzpicture} $$ 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](/reinforcement-learning/tabular-methods/monte-carlo-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. [^sb-gpi]: **Sutton & Barto**, §4.5 — Asynchronous Dynamic Programming (sweepless in-place updates, convergence if every state is updated infinitely often); §4.6 — Generalized Policy Iteration (the two interacting evaluation/improvement processes and their joint fixed point); §4.7 — Efficiency of Dynamic Programming (polynomial-time guarantee versus $k^n$ policies, the curse of dimensionality); §4.8 — bootstrapping. [^bellman]: **Bellman, R.** (1957), _Dynamic Programming_, Princeton University Press — the origin of dynamic programming and the term "curse of dimensionality"; and **Bertsekas, D. P.** (2012), _Dynamic Programming and Optimal Control_ (4th ed.), Athena Scientific — the standard modern reference for exact and approximate DP. [^moore]: **Moore, A. W., & Atkeson, C. G.** (1993), "Prioritized Sweeping: Reinforcement Learning with Less Data and Less Time," _Machine Learning_ 13(1):103–130 — prioritizing Bellman-error-large states in a queue and propagating changes backward, reaching optimality with far fewer updates than uniform sweeps. [^rtdp]: **Barto, A. G., Bradtke, S. J., & Singh, S. P.** (1995), "Learning to Act Using Real-Time Dynamic Programming," _Artificial Intelligence_ 72(1–2):81–138 — RTDP as asynchronous value iteration over states visited along trajectories, with convergence on the relevant states of stochastic shortest-path problems. [^ndp]: **Bertsekas, D. P., & Tsitsiklis, J. N.** (1996), _Neuro-Dynamic Programming_, Athena Scientific — DP with the value function replaced by a parametric approximator, and the projected-Bellman-update view of approximate value iteration. [^vin]: **Tamar, A., Wu, Y., Thomas, G., Levine, S., & Abbeel, P.** (2016), "Value Iteration Networks," _NeurIPS_ — embedding a fixed number of value-iteration sweeps as a differentiable planning module inside a policy network. [^muzero]: **Schrittwieser, J., et al.** (2020), "Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model," _Nature_ 588:604–609 (MuZero) — learning a latent dynamics model and running Monte Carlo tree search over it, with no access to the environment's true rules.