Dynamic Programming: Value and Policy Iteration

Dynamic programming (DP) sits at the planning end of the RL spectrum. You have full access to the MDP tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ and want to compute the optimal policy without interacting with the environment. Real problems rarely give you the true $P$ — but DP is the foundation everything else builds on, and modern model-based RL methods learn $\hat{P}$ and then plan inside it.

Two key objects: the optimal value function $V^\star(s) = \max_\pi V^\pi(s)$ and the optimal action-value function $Q^\star(s,a) = \max_\pi Q^\pi(s,a)$. Once you have either, extracting the optimal policy is trivial: $\pi^\star(s) = \arg\max_a Q^\star(s,a)$.

The optimal value functions satisfy a nonlinear recursion — the Bellman optimality equation:

$V^\star(s) = \max_a \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma V^\star(s')\right]$

$Q^\star(s,a) = \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma \max_{a'} Q^\star(s',a')\right]$

The $\max$ makes these nonlinear — unlike the expectation equation for a fixed $\pi$, you cannot solve this with direct matrix inversion. But the right-hand side is a contraction mapping, so repeated application converges. That convergence is the theoretical spine of both value iteration and policy iteration.

Define the Bellman optimality operator $\mathcal{T}$:

$(\mathcal{T} V)(s) = \max_a \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma V(s')\right].$

$\mathcal{T}$ is a $\gamma$-contraction in the $\ell_\infty$ norm:

$\|\mathcal{T} V - \mathcal{T} V'\|_\infty \le \gamma\, \|V - V'\|_\infty.$

By the Banach fixed-point theorem, $\mathcal{T}$ has a unique fixed point $V^\star$, and starting from any $V_0$ the iterates $V_{k+1} = \mathcal{T} V_k$ converge geometrically. The contraction factor $\gamma$ sets the rate: with $\gamma = 0.99$, you need $\approx 700$ sweeps to reduce the initial error by $10^6\times$.

The subroutine that computes $V^\pi$ for a given fixed $\pi$ is called iterative policy evaluation. It applies the Bellman expectation operator repeatedly:

$V_{k+1}(s) \leftarrow \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma V_k(s')\right].$

This is a contraction in $\ell_\infty$ with factor $\gamma$, so it converges to the true $V^\pi$. In practice you run it until $\|V_{k+1} - V_k\|_\infty < \epsilon$ for some small threshold. Policy evaluation is $O(|\mathcal{S}|^2 |\mathcal{A}|)$ per sweep — the costly step that policy iteration must repeat for each new policy.

Given $V^\pi$, can you build a strictly better policy? Yes — the policy improvement theorem guarantees it.

Define the greedy policy with respect to $V^\pi$:

$\pi'(s) = \arg\max_a \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma V^\pi(s')\right].$

Then $V^{\pi'}(s) \ge V^\pi(s)$ for all $s$. The proof is a one-step argument: taking the greedy action in $s$ and then following $\pi$ is at least as good as just following $\pi$, because the greedy action maximises the one-step look-ahead.

If $\pi' = \pi$ everywhere, improvement has stalled — and we've proved the policy is optimal.

Policy iteration alternates evaluation and improvement until convergence:

Policy iteration converges in a finite number of policy updates (the policy space is finite), typically far fewer than you'd expect. Empirically, 10-20 iterations often suffices even for large tabular MDPs. The bottleneck is the evaluation step, which itself requires many sweeps.

Value iteration skips full policy evaluation. It applies one sweep of the Bellman optimality operator per iteration:

$V_{k+1}(s) \leftarrow \max_a \sum_{s'} P(s' \mid s,a)\left[R(s,a,s') + \gamma V_k(s')\right].$

Convergence is guaranteed by the contraction argument. The extracted policy at any iteration $k$ is $\pi_k(s) = \arg\max_a(\cdot)$ — not necessarily optimal yet, but approaching it.

Practical trade-off:

• Policy iteration: fewer outer iterations, each expensive (full evaluation).
• Value iteration: more outer iterations, each cheap (one sweep).

For most problems, value iteration wins on wall-clock time because full policy evaluation is wasteful — the policy changes after just one improvement step anyway.

A compact NumPy implementation:

import numpy as np

def value_iteration(P, R, gamma, n_states, n_actions, tol=1e-8):
    """P[s, a, s'] = transition prob, R[s, a] = expected reward."""
    V = np.zeros(n_states)
    while True:
        Q = np.zeros((n_states, n_actions))
        for a in range(n_actions):
            # Q[s, a] = R[s, a] + gamma * sum_{s'} P[s,a,s'] * V[s']
            Q[:, a] = R[:, a] + gamma * (P[:, a, :] @ V)
        V_new = Q.max(axis=1)
        if np.max(np.abs(V_new - V)) < tol:
            break
        V = V_new
    policy = Q.argmax(axis=1)
    return V, policy

The inner loop vectorises over states; the @ is the transition-weighted sum. Stopping criterion: $\|V_{k+1}-V_k\|_\infty < \epsilon$ guarantees the extracted policy is within $\frac{2\gamma\epsilon}{1-\gamma}$ of optimal.

Three facts worth knowing precisely:

1. Value iteration converges to $V^\star$ in the limit; it never reaches it in finite steps (unless the MDP has a special structure). The bound $\|V_k - V^\star\|_\infty \le \gamma^k \|V_0 - V^\star\|_\infty$ gives the iteration count needed for any target accuracy.

2. Policy iteration reaches $V^\star$ exactly in finite steps (the policy space is finite). In practice it also terminates when $\|V^{\pi_{k+1}} - V^{\pi_k}\|_\infty < \epsilon$, accepting near-optimality.

3. Modified policy iteration interpolates: run $m$ evaluation sweeps instead of full convergence before improving. At $m=1$ it becomes value iteration; at $m=\infty$ it becomes policy iteration. Choosing $m \approx 10$–$30$ often dominates both extremes.

DP's fatal flaw is the curse of dimensionality. A robot with 10 joint angles discretised to 100 positions each has $10^{20}$ states — one sweep of value iteration is cosmically infeasible.

Three escape routes:

DP remains essential because:

• It defines the target every approximate method is chasing.
• Linear function approximation + DP gives approximate policy/value iteration with provable error bounds.
• Modern model-based RL (MuZero, Dreamer) learns $\hat{P}$ and then plans inside it, often with short-horizon DP rollouts.