Dynamic Programming for RL: Policy Iteration and Value Iteration

TL;DR

Every technique in the companion Q-learning and actor-critic articles is solving an approximation of a problem that has an exact solution when the environment’s transition and reward functions are fully known: a Markov Decision Process. Policy Iteration alternates between evaluating a fixed policy exactly and improving it greedily, provably converging to the optimal policy in a finite number of steps; Value Iteration merges those two phases into a single, simpler update. Neither one touches a neural network or samples an environment — they’re the “if you had a perfect model, here’s the exact answer” baseline that everything else in reinforcement learning is an approximation of. Used less for large-scale production ML and more for small, fully-known planning problems, as the theoretical backbone behind model-based RL, and in classical control and operations research.

The Policy Iteration Loop

graph LR
    A[Arbitrary Initial Policy] --> B[Policy Evaluation: compute exact V]
    B --> C[Policy Improvement: act greedily on V]
    C -->|policy changed| B
    C -->|policy stable| D[Optimal Policy]

    style D fill:#6366f1,color:#fff

Problem Statement

Every algorithm elsewhere on this site — Q-learning, actor-critic, model-based RL — exists because the environment’s dynamics p(s'|s,a) and reward function r(s,a) are usually unknown, forcing the agent to learn from sampled experience. But if you do know the full MDP — a small gridworld, an inventory management problem, a known-physics control task — the optimal policy can be computed exactly, with guaranteed convergence, using classical dynamic programming. This isn’t a historical footnote: it’s the ground truth that every sample-based method is trying to approximate without needing the model.

The Bellman Equations

Both algorithms below are direct applications of the Bellman optimality equation, which states that the value of a state under the optimal policy equals the immediate reward plus the discounted value of the best next state:

V*(s) = max_a [ r(s,a) + γ Σ_s' p(s'|s,a) V*(s') ]

Because the full transition model p(s'|s,a) is known, this sum can be computed exactly for every state — no sampling, no bootstrapping from noisy estimates, no function approximation error.

Policy Iteration: Evaluate, Then Improve, Repeat

Policy Iteration alternates two phases until they stop changing anything: policy evaluation (compute the exact value function for the current policy) and policy improvement (make the policy greedy with respect to that value function).

def policy_evaluation(policy, P, R, gamma=0.99, theta=1e-6):
    V = np.zeros(n_states)
    while True:
        delta = 0
        for s in range(n_states):
            v = V[s]
            a = policy[s]
            V[s] = R[s, a] + gamma * sum(P[s, a, s_next] * V[s_next] for s_next in range(n_states))
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break
    return V

def policy_improvement(V, P, R, gamma=0.99):
    new_policy = np.zeros(n_states, dtype=int)
    for s in range(n_states):
        action_values = [R[s, a] + gamma * sum(P[s, a, s_next] * V[s_next] for s_next in range(n_states))
                          for a in range(n_actions)]
        new_policy[s] = np.argmax(action_values)
    return new_policy

def policy_iteration(P, R, gamma=0.99):
    policy = np.zeros(n_states, dtype=int)   # arbitrary initial policy
    while True:
        V = policy_evaluation(policy, P, R, gamma)
        new_policy = policy_improvement(V, P, R, gamma)
        if np.array_equal(new_policy, policy):
            break   # policy stopped changing: it's optimal
        policy = new_policy
    return policy, V

Each full evaluation phase requires iterating to convergence before a single improvement step happens — expensive per iteration, but the number of outer iterations needed is typically very small, since the policy has nowhere left to improve once it stabilizes.

Value Iteration: Merge Evaluation and Improvement

Value Iteration notices that you don’t need to fully evaluate a policy before improving it — you can take the max over actions at every single sweep instead of waiting for evaluation to converge first, collapsing the two-phase loop into one:

def value_iteration(P, R, gamma=0.99, theta=1e-6):
    V = np.zeros(n_states)
    while True:
        delta = 0
        for s in range(n_states):
            v = V[s]
            V[s] = max(
                R[s, a] + gamma * sum(P[s, a, s_next] * V[s_next] for s_next in range(n_states))
                for a in range(n_actions)
            )
            delta = max(delta, abs(v - V[s]))
        if delta < theta:
            break

    policy = np.array([
        np.argmax([R[s, a] + gamma * sum(P[s, a, s_next] * V[s_next] for s_next in range(n_states))
                    for a in range(n_actions)])
        for s in range(n_states)
    ])
    return policy, V

Value Iteration’s individual sweeps are cheaper than Policy Iteration’s full evaluation phase, but it typically needs more sweeps overall to converge — the classic time-per-iteration versus number-of-iterations trade-off, and in practice both usually converge fast enough on small MDPs that the choice rarely matters much.

Comparison Table

Method	Phases per Iteration	Convergence	Best When
Policy Iteration	Full evaluation, then improvement	Fewer outer iterations, more work each	Action space is small; evaluation is cheap relative to number of iterations needed
Value Iteration	Combined single Bellman backup	More iterations, less work each	Simpler to implement; no separate evaluation loop to manage

Applications

Small, fully-known planning problems — inventory management, scheduling, and classical control problems where the transition model is a known, explicit function.
Theoretical backbone of model-based RL — the model-based RL article on this site covers algorithms (Dyna-Q, PETS, MuZero) that are essentially trying to approximate exactly this kind of planning when the model has to be learned rather than given.
Validating and debugging RL implementations — running exact DP on a small version of a problem gives ground-truth optimal values to check a sampled, function-approximated method against.
Operations research — many classical OR problems (routing, resource allocation) are formalized as MDPs and solved with these exact methods when state spaces stay tractable.

Key Learnings

These are the exact solutions every other RL method on this site is approximating. Q-learning is essentially value iteration with samples standing in for the unknown transition model; understanding DP first makes clear exactly what error every learned method is willing to trade away for scalability.
The model requirement is the whole limitation. These algorithms are provably optimal and provably convergent — the entire rest of the field of RL exists because knowing p(s'|s,a) exactly is the exception, not the rule, in real-world problems.
State-space size, not algorithmic subtlety, is what breaks these methods in practice. Both algorithms sweep over every state on every iteration, which is exactly why deep RL replaces the explicit table with a function approximator the moment the state space becomes large or continuous.

References

Bellman, R. (1957). Dynamic Programming. Princeton University Press.
Howard, R. (1960). Dynamic Programming and Markov Processes. MIT Press.
Sutton, R., Barto, A. (2018). Reinforcement Learning: An Introduction, 2nd Edition. MIT Press.