Dynamic Programming for MDPs

A Markov Decision Process is defined by states $\mathcal{S}$, actions $\mathcal{A}$, a transition model $p(s' \mid s, a)$, a reward function, and a discount factor $\gamma$. The Bellman equations express the value of a state as a recursive sum over immediate reward plus the discounted value of the next state. For a fixed policy $\pi$, the Bellman expectation equation is

For the optimal value function, the Bellman optimality equation replaces the average over actions with a maximum:

These are systems of $|\mathcal{S}|$ equations in $|\mathcal{S}|$ unknowns. In principle one could solve them directly with linear algebra (for $v_\pi$, which is linear in $v_\pi$), but this requires inverting an $|\mathcal{S}| \times |\mathcal{S}|$ matrix, which costs $O(|\mathcal{S}|^3)$ and becomes impractical as state spaces grow. Dynamic programming instead treats each Bellman equation as an assignment operator: replace the "$=$" with "$\leftarrow$" and apply it repeatedly to every state, using the current estimates of the values on the right-hand side. This is bootstrapping: a value estimate $V(s)$ is updated using other value estimates $V(s')$ that are themselves still being refined, rather than using final, ground-truth outcomes. It is what distinguishes DP (and later, TD learning) from Monte Carlo methods, which wait for actual returns to unfold before updating anything. The second defining feature is the full backup. Because the model $p(s', r \mid s, a)$ is completely known, each update can average over every possible next state and reward exactly, weighted by their true probabilities — no sampling, no estimation error from a finite number of trials. This is why DP methods, when they converge, converge to the exact value function, not an approximation contaminated by sampling noise. The cost of this exactness is that every single successor state must be enumerated and its probability known, which is precisely the requirement of having a complete model.

The mechanism is a repeated sweep: for each state, the algorithm consults the model, computes the Bellman backup, and updates the state's value. Two flavors of sweep matter for laying groundwork here.

Full policy evaluation sweep. Given a fixed policy $\pi$, apply the Bellman expectation equation as an update rule to every state, repeatedly, until values stop changing appreciably. Each state's new value is a weighted average over the actions the policy would take, and within that, an average over the model's transition probabilities.

Full optimality sweep. Instead of averaging over actions according to a policy, take the maximum over actions at each state. This directly targets $v_*$, without ever holding a fixed policy in hand — this is the operation underlying value iteration. Two implementation choices recur in every DP algorithm:

• Two-array vs. in-place updates. A synchronous sweep computes all new values from a frozen copy of the old array, then swaps. An in-place (asynchronous within a sweep) sweep overwrites values immediately, letting later states in the sweep see fresher information. In-place updates often converge faster in practice and still provably converge, though the convergence argument is slightly more delicate.
• Stopping criterion. Sweeps continue until the maximum change in any state's value, $\Delta = \max_s |V_{\text{new}}(s) - V_{\text{old}}(s)|$, drops below a small threshold $\theta$.

Below is the generic template that both iterative policy evaluation and value iteration specialize. ``` function DP-SWEEP(states S, model P, R, gamma, V, mode):

# mode = "evaluate" (needs policy pi) or "optimize" delta = 0 for each state s in S: v_old = V[s] if mode == "evaluate": total = 0 for each action a with pi(a|s) > 0: q = 0 for each (s_next, r, prob) in P(s, a): q += prob (r + gamma V[s_next]) total += pi(a|s) q V[s] = total else if mode == "optimize": best_q = -infinity for each action a in A(s): q = 0 for each (s_next, r, prob) in P(s, a): q += prob (r + gamma * V[s_next]) best_q = max(best_q, q) V[s] = best_q delta = max(delta, abs(v_old - V[s])) return delta

function DP-SOLVE(states S, model P, R, gamma, theta, mode, pi=None): V = array of zeros, size |S| repeat: delta = DP-SWEEP(S, P, R, gamma, V, mode) until delta < theta return V ``` Every terminal (absorbing) state is defined to have value 0 and is either excluded from the sweep or handled with a trivial self-loop of value 0, which prevents the recursion from being ill-defined. This is the algorithm's essential base case: without a properly anchored terminal value, the recursive backups have nothing fixed to converge toward. The overall shape that DP work builds toward is: 1. Iterative policy evaluation — repeatedly runs the `"evaluate"` sweep for a fixed $\pi$ until $V \approx v_\pi$. 2. Policy iteration — alternates full evaluation with a policy improvement step (greedify the policy with respect to the current $V$), provably converging to $\pi_*$. 3. Value iteration — runs the `"optimize"` sweep directly, folding evaluation and improvement into a single update, converging to $v_*$.

Time complexity per sweep. For each of the $|\mathcal{S}|$ states, the update considers up to $|\mathcal{A}|$ actions, and for each action sums over up to $|\mathcal{S}|$ possible successor states (the transition model can, in the worst case, connect any state to any other). This gives

per full sweep. In practice, transition models are usually sparse — each $(s,a)$ pair has only $k \ll |\mathcal{S}|$ possible successors — reducing the cost to $O(|\mathcal{S}| |\mathcal{A}| k)$. The number of sweeps needed for convergence to a fixed tolerance is not bounded by a fixed constant in general, but is controlled by the contraction rate $\gamma$, discussed below; for value iteration, an $\varepsilon$-accurate value function is reached in $O\!\left(\frac{\log(1/\varepsilon)}{1-\gamma}\right)$ sweeps in the worst case, giving a total cost polynomial in $|\mathcal{S}|$, $|\mathcal{A}|$, and $\frac{1}{1-\gamma}$.

Space complexity. DP needs to store one value per state, $O(|\mathcal{S}|)$, plus (for policy-based variants) one action per state, $O(|\mathcal{S}|)$ — dominated by the model itself, which if stored explicitly is $O(|\mathcal{S}|^2 |\mathcal{A}|)$ in the dense case.

Correctness: why bootstrapped full backups converge. Define the Bellman optimality operator $T$ acting on any value function $V: \mathcal{S} \to \mathbb{R}$ by

The DP optimality sweep is exactly the iteration $V_{k+1} = T V_k$. The correctness argument rests on two facts. Fact 1 — $T$ is a contraction in the max-norm. For any two value functions $U, V$,

This follows because the max over actions and the weighted sum over successor states are both non-expansive operations (a max of differences is bounded by the max absolute difference, and a convex combination is bounded by the largest term), and each term differs only through the $\gamma V(s')$ component, contributing exactly one factor of $\gamma$. Fact 2 — $v_*$ is the unique fixed point of $T$. This is precisely the statement of the Bellman optimality equation: $v_* = T v_*$, and by the Banach fixed-point theorem, since $T$ is a $\gamma$-contraction on a complete metric space ($\mathbb{R}^{|\mathcal{S}|}$ with the max-norm) and $\gamma < 1$, $T$ has exactly one fixed point, and iterating $T$ from any starting point converges to it:

This is why bootstrapping is safe here: even though $V_k$ is not correct, applying $T$ repeatedly provably shrinks the error geometrically, regardless of the (finite) starting guess. The same contraction argument applies to the Bellman expectation operator $T_\pi$ for a fixed policy, giving convergence of iterative policy evaluation to $v_\pi$.

Tradeoffs. DP is exact and convergence is mathematically guaranteed, but it requires: 1. A complete, correct model $p(s', r \mid s, a)$ — unavailable in most real applications. 2. Enumerating every state — infeasible when $|\mathcal{S}|$ is astronomically large or continuous (the curse of dimensionality). 3. A full sweep over all states even if most of them are irrelevant to the optimal policy from a given start state — motivating asynchronous and prioritized variants, and eventually sample-based methods that only visit states the agent actually encounters.

Consider a tiny 1-D "corridor" MDP with states $\{1, 2, 3\}$ plus an absorbing goal $G$ (value fixed at 0) reachable from state 3. The agent can move `Right` (deterministic) or `Stay` (deterministic), reward $-1$ per step until reaching $G$, discount $\gamma = 1$ for finite-horizon simplicity within this trace (we use $\gamma = 0.9$ to keep the contraction visibly at work). Fixed policy $\pi$: always choose `Right`. Transition model: from state $s < 3$, `Right` leads deterministically to $s+1$; from state 3, `Right` leads to $G$ (value 0, absorbing). We run iterative policy evaluation (the `"evaluate"` sweep with a deterministic policy, so the average over actions collapses to the single chosen action):

(Sweep 3 uses the previous sweep's values for state 2 and 3 under synchronous updates; by sweep 4 the values stop changing — the sweep has converged.) Notice this matches the closed-form geometric series exactly: $v_\pi(1) = -1 - 0.9 - 0.81 = -2.71$, $v_\pi(2) = -1 - 0.9 = -1.9$, $v_\pi(3) = -1$, confirming the DP sweep reached the true $v_\pi$ under this policy, not merely something close to it. Now switch the sweep to `"optimize"` mode, introducing a second action `Stay` (self-loop, reward $-1$, clearly suboptimal here since it never reaches the goal). At each state the max over $\{$`Right`, `Stay`$\}$ will always select `Right`, since `Stay` produces an infinite loop of $-1$ rewards discounted forever, i.e. value $-1/(1-0.9) = -10$, far worse than any finite path to the goal. This is a direct illustration of the maximization step in the Bellman optimality backup pruning away a clearly bad action — the same mechanism value iteration will use, sweep after sweep, to discover $v_*$ and, from it, $\pi_*$.

Exact DP for MDPs underlies planning modules in robotics and operations research whenever a reliable simulator or transition model exists — inventory management, elevator scheduling, and network routing problems have all been solved historically with policy iteration or value iteration on hand-built models. In modern deep RL, DP is less often run to convergence on the full state space (too large), but its update rule is the direct ancestor of the Temporal-Difference Learning update used in Q-learning, SARSA, and actor-critic methods, all of which replace the exact expectation over successor states with a sampled successor, trading exactness for scalability. Model-based reinforcement learning systems, including those that learn a model and then plan with it (e.g., Dyna-style architectures, MuZero-style planning with a learned model), essentially run truncated or approximate DP sweeps inside a larger learning loop. Understanding DP correctly is therefore a prerequisite for understanding almost every value-based deep RL algorithm as an approximation of a known-convergent ideal.

Ask the tutor: How does the choice between synchronous and in-place sweeps affect the number of iterations needed for value iteration to converge in practice?