Policy Iteration¶
Formal optimization method — instantiates Sequential Policy Optimization
Carries an explicit current policy and converges by alternating an exact evaluation of that policy with a greedy, state-by-state improvement over the available actions.
Policy Iteration solves a known model by working in policy space. Unlike its value-space twin, it always holds a named, explicit policy — a concrete state-to-action map — and converges by alternating two sharply different phases. First, policy evaluation: it computes the long-run value of this exact policy, either by solving the linear system that the fixed policy induces or by iterating value updates until they settle. Second, policy improvement: at every state it looks one step ahead over the action set and switches to whichever action now looks best given those freshly computed values. Evaluate, improve, evaluate, improve — until an improvement round changes nothing. Its defining property is that improvement is guaranteed monotone[n1] and the loop converges in a strikingly small number of policy changes, each of which is individually expensive because the full evaluation must be redone.
Example¶
A ride-share platform wants a smarter rule for where idle drivers should reposition. The city is carved into zones, and the state is (zone, time-of-day). The current policy is a plausible hand-written map: "idle in the financial district at 5pm → move toward the stadium." Policy Iteration starts from exactly this policy and evaluates it — computing, for every (zone, time), the expected long-run earnings a driver following this policy will accumulate, accounting for where each reposition tends to leave them next. This is not a guess about the next fare; it is the settled value of the whole standing rule.
Then it improves: in each state it asks, given those long-run values, is there a better reposition target than the one the policy currently names? In a handful of zones the answer is yes — sending drivers somewhere that positions them better for the following hour beats chasing the nearest current surge. Those states get their actions swapped, the policy is re-evaluated, and the cycle repeats. After perhaps four rounds the policy stops changing. What emerges is a repositioning rule that a myopic "go where the surge is highest right now" heuristic could never find, because it values future position, not just the next ride.
How it works¶
- Start from any policy — a hand-written rule or a random map.
- Evaluate it exactly. Compute the value of every state under the current fixed policy, by solving its induced system or iterating to a tolerance.
- Improve greedily. In each state, replace the action with the one that maximizes one-step-lookahead value using those evaluations.
- Repeat until an improvement pass leaves the policy unchanged; that policy is optimal.
The signature is the alternation over an explicit policy: a full, honest evaluation of the current rule sits between each improvement, and the whole loop typically finishes in very few outer rounds even when the state space is large.
Tuning parameters¶
- Evaluation exactness — solve the policy's value exactly, or only iterate a few sweeps toward it (modified policy iteration); approximate evaluation cuts per-round cost but can slow or destabilize convergence.
- Initial policy — a sensible warm start (an existing operating rule) reaches the optimum in fewer rounds than a random one.
- Improvement scope — improve all states each round, or asynchronously improve a subset; partial improvement saves work but changes the convergence pattern.
- Tie-breaking rule — how ties between equally-good actions are resolved, which affects reproducibility and can matter when many actions are near-equal.
When it helps, and when it misleads¶
Its strength is that it converges in remarkably few policy changes and produces an explicit, inspectable policy at every round — you can read the current rule, see what changed, and stop early with a usable map. It shines when you already have a decent operating policy and want to sharpen it, because the warm start does most of the work.
Its cost is the flip side: each evaluation phase is expensive, since valuing a fixed policy over the whole state space is real computation, and on very large spaces those rounds become unaffordable. It also needs a known, correct model. The classic misuse is under-solving the evaluation phase — stopping it too early so the improvement step chases evaluation noise rather than true value, which can stall the loop or oscillate. The guarding discipline is to evaluate to an adequate tolerance before improving and to watch policy stability across rounds rather than trusting a single pass.
How it implements the components¶
Policy Iteration is a policy-space solver — it evaluates and improves an explicit rule:
policy_evaluation_rule— its evaluation phase is this component: the exact long-run value of the current fixed policy, computed before any improvement.action_set— improvement is a greedy argmax over the actions available in each state; the action menu is what the improvement step searches.transition_model— both phases lean onP(next | state, action): evaluation propagates value through it, improvement looks one step ahead through it.
It does not converge by hammering a discounted value array with max-backups — the discounting_or_temporal_weight contraction and the value-space route that reads a policy off converged values are Dynamic Programming / Value Iteration's. Policy Iteration is separated from its near-twin by always carrying and exactly evaluating an explicit policy rather than iterating values.
Related¶
- Instantiates: Sequential Policy Optimization — the policy-space solver that evaluates and improves an explicit rule to optimality.
- Consumes: Markov Decision Process Model supplies the states, actions, transitions, and rewards its two phases operate on.
- Sibling mechanisms: Markov Decision Process Model · Dynamic Programming / Value Iteration · Simulation Rollout Evaluation · Reinforcement Learning Policy Learning · Threshold Policy Rule · Adaptive Policy Review Cycle · Off-Policy or Historical Replay Evaluation
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Policy Iteration operates as an analytical, modeling, inference, comparison, or optimization procedure that derives insight or a solution because it carries an explicit current policy and converges by alternating an exact evaluation of that policy with a greedy, state-by-state improvement over the available actions.
Independent corroboration: The frozen evidence defines Policy Iteration as 'Carries an explicit current policy and converges by alternating an exact evaluation of that policy with a greedy, state-by-state improvement over the available actions', so its operative form is Analysis, Modeling & Optimization.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Operations Research
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Multi-domain
Rationale: Policy iteration is a canonical dynamic-programming method for Markov decision processes in operations research.
Related originating lineages:
- Computer Science & Software Engineering — Computer science materially developed algorithmic implementations and reinforcement-learning variants.
- Mathematics — Mathematics supplies the fixed-point and contraction foundations for convergence.
Review resolution: Both blind reviewers agree that operations research is the primary origin. Reconciliation resolves alternate origin disagreement, domain reach disagreement. Formative alternate lineages are retained as computer_science, mathematics; later breadth of use is recorded separately as domain_reach=multi_domain, while origin_mode=cross_disciplinary_synthesis describes the relationship among origin lineages.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] The policy improvement theorem (Howard) guarantees that greedily updating a policy with respect to its own evaluated values yields a policy that is no worse in every state and strictly better in at least one — until no change is possible, at which point the policy is optimal. This monotonicity is why policy iteration finishes in so few outer rounds. ↩