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.
- Initialization: choose any deterministic policy, for example a random action in every state.
- Policy evaluation: solve the Bellman expectation equation to obtain the state value of the current policy.
- Policy improvement: in every state, select the action with the highest expected return given those values.
- 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.
| Phase | Input | Output | Typical cost |
|---|---|---|---|
| Policy evaluation | Current policy and model | State value function | Linear system or many sweeps |
| Policy improvement | Value function and model | Greedy updated policy | One sweep over states and actions |
| Convergence check | Old and new policy | Stop or continue | Negligible |
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 method | Accuracy | Cost per iteration | Best suited for |
|---|---|---|---|
| Direct linear solve | Exact | About cubic in state count | Small state spaces |
| Iterative sweeps to tolerance | Near exact | Many sweeps | Medium state spaces |
| Truncated sweeps | Approximate | Few sweeps | Modified policy iteration |
| Sample-based estimation | Noisy | Depends on samples | Unknown or huge models |
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.
| Method | Needs a model | Iterations to converge | Main idea |
|---|---|---|---|
| Policy iteration | Yes | Few, often under 20 | Full evaluation then greedy update |
| Value iteration | Yes | Many | Repeated Bellman optimality backups |
| Modified policy iteration | Yes | Moderate | Partial evaluation between updates |
| Q-learning | No | Many episodes | Learns action values from samples |
| Actor-critic | No | Many episodes | Critic evaluates, actor improves |
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.
| Problem | Cause | Remedy |
|---|---|---|
| Endless oscillation | Inconsistent tie-breaking | Keep the current action on ties |
| Very slow evaluation | Discount factor near 1 | Use a direct solve or truncated sweeps |
| Memory exhaustion | State space too large | Use function approximation |
| Poor real-world results | Inaccurate transition model | Validate the model or use robust planning |
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.