Dynamic Programming

"You handed me the transition table and the rewards and asked for the optimal policy. Fine. I will sweep every state, back up every value, and sweep again. And again. I will not stop sweeping until the largest change I see is smaller than your tolerance, and not one sweep before. I have a fixed point to reach and all the patience in the world."

A Bellman Backup That Will Not Stop Until Everything Converges

In Section 22.3 we met the Bellman equations: the consistency conditions that any value function must satisfy, and the optimality equations whose unique solution is the optimal value function $V^{\star}$. We proved those equations have a unique solution but stopped short of computing it. This section closes that gap. Given a fully specified MDP, the tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ of Section 22.3, we now turn the Bellman optimality equation from a condition into an algorithm, sweeping it across the state space until the values stop moving. We use the unified notation of Appendix A throughout: $\mathcal{S}$ the state set, $\mathcal{A}$ the action set, $\pi$ a policy, $V^{\pi}$ and $Q^{\pi}$ the state and action value functions, $\gamma \in [0, 1)$ the discount, and $V^{\star}, Q^{\star}, \pi^{\star}$ their optimal counterparts.

Why does an exact method deserve a full section when the rest of Part VI is about learning from experience? Because dynamic programming is the conceptual anchor for everything that follows. Every value-based reinforcement-learning algorithm, from the tabular temporal-difference methods of Chapter 24 to the deep $Q$-networks of Chapter 25, is best understood as an attempt to carry out a Bellman backup when you cannot afford the exact one: when the model $(P, R)$ is unknown, so you must replace the expectation over $s'$ with sampled transitions, or when the states are too numerous to enumerate, so you must replace the lookup table with a function approximator. Understand the exact backup first and the approximations read as principled compromises rather than disconnected tricks. Misunderstand it and the whole reinforcement-learning edifice looks like a bag of unrelated update rules.

The four competencies this section installs are these: to evaluate a fixed policy exactly and improve it greedily, and to see policy iteration as the alternation of the two; to run value iteration as the truncated combination of evaluation and improvement, and to write both updates with full notation; to prove convergence from the contraction property and quantify the geometric error decay; and to recognize where exact dynamic programming breaks (an unknown model, a state space too large to enumerate) and how reinforcement learning is built to step in there. These are load-bearing for every chapter of Part VI.

1. Solving a Known MDP Exactly: Policy Evaluation, Improvement, and Iteration Beginner

Begin with a fixed policy $\pi$ and ask the narrower question: what is it worth? The value function $V^{\pi}$ assigns to each state the expected discounted return obtained by following $\pi$ from that state. Because the MDP is Markov, $V^{\pi}$ satisfies the Bellman expectation equation, one linear equation per state, coupling each state's value to its successors':

This is the policy-evaluation equation. It is a system of $|\mathcal{S}|$ linear equations in the $|\mathcal{S}|$ unknowns $\{V^{\pi}(s)\}$, and in principle one can solve it directly by matrix inversion: writing $\mathbf{v}^{\pi}$ for the value vector, $\mathbf{r}^{\pi}$ for the expected one-step reward under $\pi$, and $\mathbf{P}^{\pi}$ for the policy-induced transition matrix, the equation is $\mathbf{v}^{\pi} = \mathbf{r}^{\pi} + \gamma \mathbf{P}^{\pi} \mathbf{v}^{\pi}$, whose closed-form solution is $\mathbf{v}^{\pi} = (\mathbf{I} - \gamma \mathbf{P}^{\pi})^{-1} \mathbf{r}^{\pi}$. The matrix $\mathbf{I} - \gamma \mathbf{P}^{\pi}$ is invertible for every $\gamma < 1$ because $\gamma \mathbf{P}^{\pi}$ has spectral radius at most $\gamma < 1$. The direct solve costs $O(|\mathcal{S}|^3)$; the cheaper alternative, used in practice and in the code below, is to treat the equation as a fixed-point iteration, $\mathbf{v} \leftarrow \mathbf{r}^{\pi} + \gamma \mathbf{P}^{\pi} \mathbf{v}$, sweeping until the values settle. That iterative sweep is iterative policy evaluation, and it converges for the same contraction reason we establish in subsection two.

Knowing what a policy is worth, we ask whether we can do better. The policy improvement step looks at $V^{\pi}$ and, in each state, switches to whichever action looks best when followed thereafter by $\pi$. Define the action value of the current policy,

and form the greedy policy $\pi'(s) = \arg\max_{a} Q^{\pi}(s, a)$. The policy improvement theorem, proven in Section 22.3, guarantees that $\pi'$ is at least as good as $\pi$ in every state, $V^{\pi'}(s) \ge V^{\pi}(s)$, and strictly better in at least one state unless $\pi$ is already optimal. Alternate the two steps, evaluate then improve, and you have policy iteration: starting from any policy $\pi_0$, repeatedly compute $V^{\pi_k}$ exactly and set $\pi_{k+1}$ greedy with respect to it. Because there are only finitely many deterministic policies and each iteration strictly improves until convergence, policy iteration reaches the exact optimum $\pi^{\star}$ in a finite number of iterations, typically a handful even for large state spaces.

Policy iteration spends real effort on each evaluation: solving (or iterating to convergence) the full linear system before taking a single improvement step. Value iteration is the impatient cousin that refuses to wait. Instead of evaluating the current policy to convergence, it performs exactly one backup of the value function and then immediately acts greedily, fusing evaluation and improvement into a single update. Concretely, value iteration sweeps the Bellman optimality backup,

over every state at every iteration, starting from an arbitrary $V_0$. The $\max$ over actions is exactly an improvement step folded into the backup, and the single application of the operator is a truncated evaluation: one sweep rather than a full solve. When the values stop changing, $V_k \to V^{\star}$, and the greedy policy read off the converged values is $\pi^{\star}$. Value iteration is policy iteration with the evaluation truncated to one backup, which is why it needs more sweeps than policy iteration needs improvement steps but pays far less per sweep.

2. Why They Converge: The Bellman Operator Is a Contraction Intermediate

Both algorithms converge for one reason, and it is worth stating precisely because it also delivers the rate. Define the Bellman optimality operator $\mathcal{T}$, which maps a value function to a new one by applying the optimality backup at every state:

Value iteration is nothing but the repeated application $V_{k+1} = \mathcal{T} V_k$, and $V^{\star}$ is by definition the fixed point $\mathcal{T} V^{\star} = V^{\star}$ (the Bellman optimality equation of Section 22.3). The decisive property is that $\mathcal{T}$ is a $\gamma$-contraction in the supremum norm: for any two value functions $V$ and $W$,

where $\lVert V \rVert_{\infty} = \max_{s} |V(s)|$. The proof is short and instructive. Fix a state $s$ and let $a^{\star}$ be the maximizing action for $\mathcal{T} V$ at $s$. Then

using that the rewards cancel, the probabilities sum to one, and the same argument with $V$ and $W$ swapped bounds the other sign, so the absolute difference is at most $\gamma \lVert V - W \rVert_{\infty}$ at every $s$, hence in the max. The key step is that the $\max_a$ is a non-expansion: $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$, so taking the best action cannot amplify a difference. Discounting by $\gamma$ then shrinks it.

The Banach fixed-point theorem now does the rest. A contraction on a complete metric space (the space of bounded value functions under the supremum norm is one) has a unique fixed point, and iterating the map from any starting point converges to it. So $V^{\star}$ is unique, and value iteration converges to it from any $V_0$. More: the contraction gives the rate directly. Applying the contraction $k$ times to the gap between $V_k$ and the fixed point,

The error decays geometrically with ratio $\gamma$ per sweep. The number of sweeps to reach a target accuracy $\varepsilon$ is therefore $O\!\big(\tfrac{1}{1 - \gamma} \log \tfrac{1}{\varepsilon}\big)$: logarithmic in the accuracy, but the factor $1/(1 - \gamma)$ means a discount near one (a far-sighted agent) converges slowly, because each sweep removes only a $\gamma$ fraction of the remaining error. The same contraction argument, applied to the policy-specific operator $\mathcal{T}^{\pi}$ (the optimality $\max$ replaced by the expectation under $\pi$), proves iterative policy evaluation converges geometrically too.

3. Complexity, the Curse of Dimensionality, and Generalized Policy Iteration Intermediate

Exact dynamic programming is powerful but it asks for a great deal, and naming what it asks for is what motivates everything after it. Each value-iteration sweep visits every state, and for each state it maximizes over every action a sum over every possible successor, so one sweep costs $O(|\mathcal{S}|^2 |\mathcal{A}|)$ when transitions are dense (and $O(|\mathcal{S}| |\mathcal{A}| \cdot \bar{b})$ with average branching factor $\bar{b}$ when sparse). Policy iteration pays $O(|\mathcal{S}|^3)$ per exact evaluation solve plus the improvement scan, over a handful of outer iterations. Either way the cost is polynomial in the size of the state space, which sounds benign until you notice how state spaces are built.

The trouble is the curse of dimensionality: in most real problems the state is a vector of features, and the number of states grows exponentially in the number of features. A robot with ten joints each discretized to a hundred positions has $100^{10} = 10^{20}$ states; a board game has astronomically many configurations; a portfolio over fifty assets is a continuum. Dynamic programming needs to enumerate and store a value for every one of these, and that is impossible past a few well-behaved dimensions. The polynomial-in-$|\mathcal{S}|$ cost is fatal precisely because $|\mathcal{S}|$ itself is exponential in the natural problem description. This single obstacle is the reason the rest of Part VI exists: we cannot enumerate the states, so we must generalize across them with function approximation, and we usually cannot write down $P$ and $R$ either, so we must learn from experience.

Before leaving exact methods, it helps to see policy iteration and value iteration as instances of one broader pattern, because that pattern survives the move to approximation. Generalized policy iteration (GPI) is the name for any scheme that interleaves two processes: a policy-evaluation process that drives the value estimate toward the true value of the current policy, and a policy-improvement process that drives the policy toward greedy with respect to the current value estimate. The two pull on each other, evaluation makes the value consistent with the policy, improvement makes the policy greedy for the value, and they reach a joint fixed point exactly when the policy is greedy for its own value, which is the optimality condition. Policy iteration runs each process to completion before switching; value iteration interleaves them at the finest grain (one backup each); modified policy iteration sits between. Crucially, almost every reinforcement-learning algorithm in the chapters ahead is also a GPI scheme, with the evaluation done from samples and the value stored in a network, which is why GPI, not any single algorithm, is the unifying picture to carry forward.

4. The Bridge to Reinforcement Learning: When the Model Is Unknown or Too Large Advanced

Dynamic programming assumed two luxuries: a known model $(P, R)$ and an enumerable, storable state space. Reinforcement learning is what you do when one or both are taken away, and the cleanest way to see the connection is to write the exact Bellman backup and then cross out the parts you can no longer compute, replacing each with something you can.

The first luxury removed is the known model. The optimality backup contains an expectation over successors, $\sum_{s'} P(s' \mid s, a)\, V(s')$, which needs the full transition kernel. When $P$ is unknown you cannot form that sum, but you can sample from it: take action $a$ in state $s$, observe the actual reward $r$ and next state $s'$ the environment returns, and use that single transition as an unbiased one-sample estimate of the expectation. Replacing the exact backup with a sampled one is exactly the move from dynamic programming to Monte Carlo and temporal-difference learning, the subject of Chapter 24. Temporal-difference learning in particular is the sampled, incremental cousin of the Bellman backup: where value iteration sets $V(s) \leftarrow \max_a [R(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s')]$ exactly, the temporal-difference update nudges $V(s)$ toward the bootstrapped sample target $r + \gamma V(s')$, an idea that traces straight back to the contraction backup we just analyzed.

The second luxury removed is the small, enumerable state space. When states are too many to store one value each (the curse of dimensionality of subsection three), the table $V(s)$ is replaced by a parametric function $V_{\theta}(s)$, a linear model or, in the modern setting, a neural network, that generalizes a value to states it has never visited by sharing parameters across similar states. The Bellman backup becomes a regression target: fit $V_{\theta}(s)$ toward $r + \gamma \max_{a} V_{\theta}(s')$ by gradient descent. This is approximate dynamic programming, and with a deep network as the approximator it is deep reinforcement learning, the subject of Chapter 25. The deep $Q$-network is precisely a value-iteration backup with the table swapped for a convolutional or recurrent network and the exact expectation swapped for sampled transitions, the two substitutions composed.

5. Worked Example: Value Iteration and Policy Iteration on a Gridworld Advanced

We now make every equation of this section executable on a small but genuine MDP: a four-by-four gridworld. The agent starts anywhere, moves up, down, left, or right, pays a small step cost of $-0.04$ per move, and seeks a terminal goal cell worth $+1$ while avoiding a terminal trap worth $-1$. The model is fully known, so dynamic programming applies exactly. The plan is the cleanest demonstration of the section's claims: implement value iteration from scratch (subsection one's optimality backup swept to convergence), implement policy iteration from scratch (evaluation plus greedy improvement), confirm the two reach the same optimal policy, then collapse the whole computation into a library MDP solver. Code 22.4.1 sets up the gridworld model.

import numpy as np

# 4x4 gridworld. State = cell index 0..15 (row-major). Goal=15 (+1), trap=11 (-1),
# both terminal. Every non-terminal move costs -0.04. Discount gamma = 0.95.
N, GAMMA, STEP = 4, 0.95, -0.04
GOAL, TRAP = 15, 11
ACTIONS = {0: (-1, 0), 1: (1, 0), 2: (0, -1), 3: (0, 1)}   # up, down, left, right
n_states, n_actions = N * N, len(ACTIONS)

def step(s, a):
    """Deterministic transition: return (next_state, reward, done)."""
    if s in (GOAL, TRAP):
        return s, 0.0, True                 # terminals absorb, no further reward
    r, c = divmod(s, N)
    dr, dc = ACTIONS[a]
    nr, nc = r + dr, c + dc
    if not (0 <= nr < N and 0 <= nc < N):
        nr, nc = r, c                       # bumping a wall: stay in place
    ns = nr * N + nc
    reward = {GOAL: 1.0, TRAP: -1.0}.get(ns, STEP)
    return ns, reward, ns in (GOAL, TRAP)

# Precompute the model tables P (next state) and R (reward) for every (s, a).
P = np.zeros((n_states, n_actions), dtype=int)
R = np.zeros((n_states, n_actions))
for s in range(n_states):
    for a in range(n_actions):
        ns, rew, _ = step(s, a)
        P[s, a], R[s, a] = ns, rew

print("model built: %d states, %d actions" % (n_states, n_actions))
print("reward for moving into goal:", R[14, 3])   # cell 14, move right -> goal

model built: 16 states, 4 actions
reward for moving into goal: 1.0

Code 22.4.2 implements value iteration: the optimality backup of subsection one swept across all states until the largest value change falls below a tolerance, then the greedy policy read off the converged values. The per-sweep error contracts by $\gamma$, exactly as subsection two proved.

def value_iteration(P, R, gamma=GAMMA, tol=1e-8):
    """Sweep the Bellman optimality backup V <- max_a [R + gamma V(s')] to convergence."""
    V = np.zeros(n_states)
    sweeps = 0
    while True:
        Q = R + gamma * V[P]                  # Q[s,a] = R[s,a] + gamma * V[next state]
        Q[GOAL, :] = Q[TRAP, :] = 0.0         # terminals have zero value
        V_new = Q.max(axis=1)                 # the max over actions IS the improvement
        sweeps += 1
        if np.max(np.abs(V_new - V)) < tol:   # stop when the largest change is tiny
            V = V_new
            break
        V = V_new
    pi = Q.argmax(axis=1)                     # greedy policy from the converged values
    return V, pi, sweeps

V_vi, pi_vi, sweeps = value_iteration(P, R)
print("value iteration converged in %d sweeps" % sweeps)
print("V(start cell 0) = %.4f" % V_vi[0])
print("greedy policy:", pi_vi.reshape(N, N))

value iteration converged in 7 sweeps
V(start cell 0) = 0.5928
greedy policy:
[[1 1 1 1]
 [1 1 1 2]
 [1 1 1 0]
 [3 3 3 0]]

Code 22.4.3 implements policy iteration: iterative policy evaluation (subsection one's expectation equation swept to convergence) alternating with greedy improvement, until the policy stops changing. We then assert it finds the same optimal policy as value iteration, the central claim that the two algorithms are two settings of one dial.

def policy_evaluation(pi, P, R, gamma=GAMMA, tol=1e-8):
    """Iterate V <- R[s, pi(s)] + gamma V(s') to the value of the fixed policy pi."""
    V = np.zeros(n_states)
    while True:
        idx = np.arange(n_states)
        V_new = R[idx, pi] + gamma * V[P[idx, pi]]    # Bellman EXPECTATION backup under pi
        V_new[GOAL] = V_new[TRAP] = 0.0
        if np.max(np.abs(V_new - V)) < tol:
            return V_new
        V = V_new

def policy_iteration(P, R, gamma=GAMMA):
    """Alternate exact evaluation and greedy improvement until the policy is stable."""
    pi = np.zeros(n_states, dtype=int)        # start from 'always go up'
    iters = 0
    while True:
        V = policy_evaluation(pi, P, R, gamma)        # evaluate current policy
        Q = R + gamma * V[P]                          # action values from that V
        pi_new = Q.argmax(axis=1)                     # greedy improvement
        iters += 1
        if np.array_equal(pi_new, pi):                # no action changed: optimal
            return V, pi_new, iters
        pi = pi_new

V_pi, pi_pi, iters = policy_iteration(P, R)
print("policy iteration converged in %d improvement steps" % iters)

# The central check: both exact methods reach the SAME optimal policy.
movable = [s for s in range(n_states) if s not in (GOAL, TRAP)]
print("same policy as value iteration:", np.array_equal(pi_pi[movable], pi_vi[movable]))
print("values agree:", np.allclose(V_pi, V_vi, atol=1e-4))

policy iteration converged in 5 improvement steps
same policy as value iteration: True
values agree: True

Step back and read what the three code blocks establish together. Code 22.4.2 swept the optimality backup of subsection one to convergence and read off a policy; Code 22.4.3 alternated exact evaluation and greedy improvement and reached the identical policy in a fraction of the outer iterations; the equality check certified that policy iteration and value iteration are the same dial at two settings, exactly as subsection one claimed. The from-scratch pair is about forty lines of careful backup bookkeeping. A dedicated MDP library collapses all of it.

import mdptoolbox
import numpy as np

# mdptoolbox wants P of shape (A, S, S) and R of shape (S, A). Build the
# sparse-but-dense transition tensor from our deterministic gridworld model.
T = np.zeros((n_actions, n_states, n_states))
for s in range(n_states):
    for a in range(n_actions):
        T[a, s, P[s, a]] = 1.0                # deterministic: all mass on one successor

vi = mdptoolbox.mdp.ValueIteration(T, R, GAMMA)   # construct the solver
vi.run()                                          # runs Bellman backups to convergence
print("library optimal policy:", np.array(vi.policy).reshape(N, N))
print("library value(start)  : %.4f" % vi.V[0])

import torch
import torch.nn as nn
import torch.optim as optim
import numpy as np

# A minimal Lagrangian safe RL loop.
# Policy: linear mapping from state to action logits (for discrete action spaces).
# Constraint threshold d: max allowed expected cumulative cost per episode.

class LinearPolicy(nn.Module):
    def __init__(self, obs_dim, act_dim):
        super().__init__()
        self.fc = nn.Linear(obs_dim, act_dim)

    def forward(self, obs):
        return torch.softmax(self.fc(obs), dim=-1)

def collect_rollout(env, policy, max_steps=200):
    """Run one episode; return rewards, costs, log-probs."""
    obs, _ = env.reset()
    rewards, costs, log_probs = [], [], []
    for _ in range(max_steps):
        obs_t = torch.tensor(obs, dtype=torch.float32)
        probs = policy(obs_t)
        dist = torch.distributions.Categorical(probs)
        action = dist.sample()
        log_probs.append(dist.log_prob(action))
        obs, reward, terminated, truncated, info = env.step(action.item())
        rewards.append(reward)
        costs.append(info.get("cost", 0.0))   # Safety Gym stores cost in info
        if terminated or truncated:
            break
    return rewards, costs, log_probs

def lagrangian_update(policy, optimizer, lam, lam_lr, rewards, costs, log_probs,
                      gamma=0.99, d=25.0):
    """One primal-dual update step.
    d: constraint threshold (cumulative cost per episode; Safety Gym default ~25).
    """
    # Discounted returns for reward and cost.
    G_r, G_c = [], []
    g_r = g_c = 0.0
    for r, c in zip(reversed(rewards), reversed(costs)):
        g_r = r + gamma * g_r
        g_c = c + gamma * g_c
        G_r.insert(0, g_r)
        G_c.insert(0, g_c)
    G_r = torch.tensor(G_r, dtype=torch.float32)
    G_c = torch.tensor(G_c, dtype=torch.float32)
    log_probs = torch.stack(log_probs)

    # Lagrangian objective: maximize J_r - lambda * (J_c - d).
    J_c_ep = G_c[0].item()          # episode cumulative cost (rough scalar)
    lagrangian_loss = -(G_r * log_probs).mean() + lam * (G_c * log_probs).mean()
    optimizer.zero_grad()
    lagrangian_loss.backward()
    optimizer.step()

    # Dual update: increase lambda if constraint violated, decrease if satisfied.
    lam = max(0.0, lam + lam_lr * (J_c_ep - d))
    return lam, J_c_ep

# --- Training loop (replace DummyEnv with a safety-gymnasium environment) ---
# import safety_gymnasium
# env = safety_gymnasium.make("SafetyPointGoal1-v0")
# obs_dim = env.observation_space.shape[0]
# act_dim = env.action_space.n

obs_dim, act_dim = 8, 4            # placeholder dimensions
policy = LinearPolicy(obs_dim, act_dim)
optimizer = optim.Adam(policy.parameters(), lr=1e-3)
lam = 0.0                          # dual variable, starts at zero
lam_lr = 0.01
d = 25.0                           # cost threshold

# Uncomment to train:
# for episode in range(500):
#     rewards, costs, log_probs = collect_rollout(env, policy)
#     lam, ep_cost = lagrangian_update(
#         policy, optimizer, lam, lam_lr, rewards, costs, log_probs, d=d)
#     if episode % 50 == 0:
#         print(f"ep {episode}: return={sum(rewards):.1f} cost={ep_cost:.1f} lam={lam:.3f}")
print("Lagrangian loop defined. Swap DummyEnv for safety_gymnasium.make(...) to run.")