Policy iteration

On this page 7

Policy iteration is a dynamic programming algorithm that finds an optimal policy for a known Markov decision process by alternating two steps: policy evaluation, which computes the value of the current policy, and policy improvement, which makes the policy greedy with respect to those values. In reinforcement learning, it is one of the foundational planning methods and the template behind many modern algorithms.

Because it requires a complete model of transitions and rewards, policy iteration is a planning method rather than a learning-from-experience method. Its importance comes from a guarantee: in a finite Markov decision process, it converges to the optimal policy in a finite number of iterations, often surprisingly few.

How policy iteration alternates evaluation and improvement

Policy iteration starts from an arbitrary policy and repeats a two-phase cycle until the policy stops changing. Each cycle produces a policy that is at least as good as the previous one in every state, a property known as monotonic improvement.

  1. Initialization: choose any deterministic policy, for example a random action in every state.
  2. Policy evaluation: solve the Bellman expectation equation to obtain the state value of the current policy.
  3. Policy improvement: in every state, select the action with the highest expected return given those values.
  4. Termination check: if no state changes its action, the policy is optimal and the loop stops.

The algorithm terminates because a finite Markov decision process has only a finite number of deterministic policies, and the improvement step never revisits a worse one. The final policy satisfies the Bellman optimality equation, which is the formal definition of optimality.

The table below summarizes what each phase takes as input and what it produces.

PhaseInputOutputTypical cost
Policy evaluationCurrent policy and modelState value functionLinear system or many sweeps
Policy improvementValue function and modelGreedy updated policyOne sweep over states and actions
Convergence checkOld and new policyStop or continueNegligible
The two phases of policy iteration

Policy evaluation methods and their cost

Policy evaluation is the expensive part of policy iteration, and it can be done in two ways. The exact approach solves a system of linear equations with one equation per state, which costs roughly the cube of the number of states. The iterative approach repeatedly applies the Bellman expectation backup until values change by less than a small tolerance.

In practice, iterative evaluation does not need full convergence. Stopping after a fixed number of sweeps gives modified policy iteration, which sits between classic policy iteration and value iteration and is often the fastest variant in practice.

Evaluation methodAccuracyCost per iterationBest suited for
Direct linear solveExactAbout cubic in state countSmall state spaces
Iterative sweeps to toleranceNear exactMany sweepsMedium state spaces
Truncated sweepsApproximateFew sweepsModified policy iteration
Sample-based estimationNoisyDepends on samplesUnknown or huge models
Ways to perform policy evaluation

Policy iteration compared with value iteration and learning methods

Policy iteration and value iteration solve the same problem but distribute the work differently. Policy iteration performs few but expensive iterations, each with a full evaluation, while value iteration performs many cheap iterations that combine a single backup with an implicit improvement.

MethodNeeds a modelIterations to convergeMain idea
Policy iterationYesFew, often under 20Full evaluation then greedy update
Value iterationYesManyRepeated Bellman optimality backups
Modified policy iterationYesModeratePartial evaluation between updates
Q-learningNoMany episodesLearns action values from samples
Actor-criticNoMany episodesCritic evaluates, actor improves
Policy iteration and related reinforcement learning methods

The comparison with model-free methods reveals why policy iteration matters beyond small problems. The evaluate-then-improve pattern, often called generalized policy iteration, underlies SARSA, actor-critic methods and proximal policy optimization. In those algorithms, a critic estimates values from sampled experience and the actor improves the policy, mirroring the two phases with approximation and noise.

Practical use and configuration

Policy iteration is the method of choice when the model is known exactly and the state space is small enough to enumerate, typically up to hundreds of thousands of states. Typical applications include inventory control, queue management, maintenance scheduling and small robot navigation grids.

Several configuration choices decide how well it performs. The discount factor controls convergence speed: values close to 1 make evaluation slower because future rewards carry more weight. The evaluation tolerance trades accuracy for time, and tie-breaking rules in the improvement step must be consistent, otherwise the algorithm can cycle between equally good actions and never report convergence.

  • Warm start: begin from a sensible heuristic policy to cut the number of iterations.
  • Reuse values: initialize each evaluation with the previous value function rather than zeros.
  • Stable ties: keep the current action when it is among the best, which guarantees clean termination.

Limitations and common pitfalls

The central limitation is the curse of dimensionality: the number of states grows exponentially with the number of state variables, so exact sweeps quickly become infeasible. Policy iteration also assumes the model is correct, and a policy that is optimal for a wrong model can perform poorly in reality.

ProblemCauseRemedy
Endless oscillationInconsistent tie-breakingKeep the current action on ties
Very slow evaluationDiscount factor near 1Use a direct solve or truncated sweeps
Memory exhaustionState space too largeUse function approximation
Poor real-world resultsInaccurate transition modelValidate the model or use robust planning
Common problems with policy iteration

A common misconception is that policy iteration is always slower than value iteration because each step is heavier. In many problems the opposite holds: far fewer iterations more than offset the cost of evaluation, especially when a direct linear solver is efficient.

A non-technical view

Think of planning the best routine for a delivery driver. First, write down a plan and work out how well it really performs. Then look at each stop and ask whether a different choice would do better. If so, change the plan at that stop.

Repeat these two steps again and again. Each round makes the plan a little better or leaves it the same. When no change helps anymore, the plan is the best possible one. Policy iteration is simply this careful check-and-improve loop done by a computer.

A concrete example

An operations analyst at a regional warehouse models daily stock decisions for one product as a Markov decision process. The state is the number of units on the shelf, from 0 to 200, the actions are order quantities, and rewards combine sales revenue, holding costs and penalties for stockouts. Demand probabilities come from two years of sales records.

Starting from the current rule of thumb, which orders 50 units whenever stock falls below 40, the analyst runs policy iteration with a discount factor of 0.95. Each evaluation solves a linear system of 201 equations in well under a second, and the policy stops changing after seven iterations.

The resulting order-up-to policy reduces expected stockouts while lowering holding costs by roughly 12 percent in simulation. Because the policy is a simple table of order quantities per stock level, store managers can review and adopt it without any special software.