Dynamic Programming: Policy Evaluation, Policy Iteration and Value Iteration

If we know an MDP's transition probabilities and rewards, we do not need to learn by trial and error — we can plan. Dynamic programming (DP) methods use the Bellman equations to compute value functions and optimal policies exactly. They require a perfect model and enumerate all states, so they rarely apply directly to large problems — but every RL algorithm can be understood as an approximation of DP.

Iterative policy evaluation#

To compute $V^\pi$ for a given policy, turn the Bellman expectation equation into an update and apply it repeatedly to all states:

Starting from any $V_0$, $V_k \to V^\pi$ as $k \to \infty$. In practice, stop when the largest change is below a small threshold $\theta$.

Policy improvement#

Given $V^\pi$, can we do better? Act greedily with respect to it:

The policy improvement theorem guarantees $V^{\pi'}(s) \ge V^\pi(s)$ for all states, with strict improvement somewhere unless $\pi$ is already optimal.

Policy iteration#

Alternate evaluation and improvement:

Because there are finitely many deterministic policies and each step improves, policy iteration converges to an optimal policy in a finite (often surprisingly small) number of iterations.

Value iteration#

Policy evaluation to full convergence is wasteful. Value iteration performs a single sweep that combines evaluation and improvement by applying the Bellman optimality update:

It converges to $V^*$ (contraction), after which we extract the greedy policy.

Implementation on the gridworld#

import numpy as np

N, gamma, slip = 4, 1.0, 0.2
S = [(r, c) for r in range(N) for c in range(N)]
terminal = {(0, 0), (N - 1, N - 1)}
A = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}

def move(s, a):
    r, c = s[0] + A[a][0], s[1] + A[a][1]
    return (r, c) if 0 <= r < N and 0 <= c < N else s

def outcomes(s, a):
    if s in terminal:
        return [(1.0, s, 0.0)]
    res = [(1 - slip, move(s, a), -1.0)]
    res += [(slip / 3, move(s, b), -1.0) for b in A if b != a]
    return res

def q_value(V, s, a):
    return sum(p * (r + gamma * V[s2]) for p, s2, r in outcomes(s, a))

def value_iteration(theta=1e-6):
    V = {s: 0.0 for s in S}
    while True:
        delta = 0.0
        for s in S:
            best = max(q_value(V, s, a) for a in A)
            delta, V[s] = max(delta, abs(best - V[s])), best
        if delta < theta:
            break
    policy = {s: max(A, key=lambda a: q_value(V, s, a)) for s in S if s not in terminal}
    return V, policy

def policy_iteration():
    policy = {s: "U" for s in S if s not in terminal}
    V = {s: 0.0 for s in S}
    while True:
        while True:                                            # policy evaluation
            delta = 0.0
            for s in policy:
                v = q_value(V, s, policy[s]); delta = max(delta, abs(v - V[s])); V[s] = v
            if delta < 1e-6:
                break
        stable = True                                          # policy improvement
        for s in policy:
            best = max(A, key=lambda a: q_value(V, s, a))
            if best != policy[s]:
                policy[s], stable = best, False
        if stable:
            return V, policy

V, pi = value_iteration()
for r in range(N):
    print(" ".join("  *  " if (r, c) in terminal else f"{V[(r, c)]:5.1f}" for c in range(N)),
          "  ", " ".join("*" if (r, c) in terminal else pi[(r, c)] for c in range(N)))
print("policy iteration agrees:", policy_iteration()[1] == pi)

The optimal policy points each cell towards the nearest terminal corner, and values reflect the expected number of steps (with slips).

Generalised policy iteration#

Almost every RL method follows the same pattern — Generalised Policy Iteration (GPI): a process that makes the value function consistent with the current policy (evaluation) interacting with a process that makes the policy greedy with respect to the value function (improvement). Monte Carlo control, SARSA, Q-learning and actor–critic methods are all forms of GPI with approximate, sample-based evaluation.

Limitations: the curse of dimensionality#

DP requires:

1. a complete, accurate model $p(s', r \mid s, a)$ — often unavailable;
2. sweeps over all states — impossible when states number in the billions (Go has more legal positions than atoms in the observable universe) or are continuous.

Remedies developed in later lectures: learn from samples instead of a model (Monte Carlo, TD), approximate value functions with neural networks, and focus computation on relevant states (asynchronous DP, real-time DP, tree search).