Does policy iteration learn directly from raw observations?

Classical policy iteration uses a model; sampled or approximate variants add further machinery.

Can evaluation use repeated updates?

Yes, provided their accuracy suits the intended guarantee.

How does it differ from policy improvement?

Improvement is one step; iteration alternates that step with evaluation.

AI Glossary / Reinforcement learning and robotics / Advanced

Policy iteration

Definition

Policy iteration is a method for finding an improved decision policy by repeatedly alternating policy evaluation and policy improvement. Evaluation computes how well the current policy performs. Improvement uses those values to choose better actions. In a finite discounted Markov decision process with exact evaluation and suitable tie handling, this process reaches an optimal policy after finitely many policy changes.

What it means

The method separates two questions: what return does the current strategy produce, and which decisions should change in light of that return? After changing the strategy, its consequences must be evaluated again before the next comparison.
This alternation matters because an improvement in a later state can make an earlier action more attractive. A single comparison using an old strategy's values may miss that opportunity. Policy iteration repeatedly brings the behavior and its evaluation back into agreement until no improving action remains.

How it works

Begin with a policy that selects a permitted action in each state. For a discounted finite MDP, exact evaluation solves Vπ = rπ + γPπVπ, where rπ contains expected immediate rewards and Pπ describes state transitions under the fixed policy. Equivalently, solve the associated linear equations or iterate the policy's Bellman expectation updates to the required accuracy.
Next, for every state, compare actions using expected immediate reward plus discounted continuation value from Vπ. Choose a maximizing action to construct the improved policy. Then evaluate that new policy and repeat.
With exact values, policy improvement never reduces any state's value. If the policy is greedy with respect to its own exact value function, the Bellman optimality condition is satisfied. In a finite discounted problem, deterministic policies form a finite set, so strict improvements cannot continue indefinitely. Retaining an existing action when it is tied for best prevents needless switching among equivalent policies.
Practical implementations use numerical tolerances. An apparently unchanged policy based on inaccurate evaluation is not automatically an optimality certificate. Modified policy iteration deliberately uses partial evaluation, while value iteration repeatedly applies optimality updates directly; these are related but distinct procedures.

Three practical examples

Small resource models: solve a fully specified decision problem with manageable states and actions.
Teaching simulators: show how changes in downstream behavior propagate back to earlier choices.
Planning benchmarks: obtain an exact or high-accuracy reference policy against which approximate learning methods can be compared.

Think of it this way

Think of revising a bus timetable. First calculate the service quality produced by the current timetable. Then adjust departures using that assessment. Because those changes alter connections elsewhere, calculate the new service quality before making another round of changes. The repeated assessment is part of the method, not redundant paperwork.

Worked example

Consider a fictional deterministic continuing problem with states A and B and discount factor γ = 0.50. At A, Wait gives reward 1 and returns to A, while Switch gives reward −0.5 and moves to B. At B, Idle gives reward 2 and stays at B, while Boost gives reward 5 and also stays at B.
Start with policy π0 = {Wait at A, Idle at B}. Evaluation gives V0(A) = 1 + 0.50V0(A), hence 2, and V0(B) = 2 + 0.50V0(B), hence 4.
For the first improvement, Wait at A is worth 1 + 0.50 × 2 = 2, while Switch is worth −0.5 + 0.50 × 4 = 1.5. Keep Wait. At B, Idle is worth 4 and Boost is worth 5 + 0.50 × 4 = 7. Change B to Boost.
Evaluate π1 = {Wait, Boost}. Its values are V1(A) = 2 and V1(B) = 10. The next improvement now compares Wait = 2 with Switch = −0.5 + 0.50 × 10 = 4.5, so A changes to Switch. Boost remains preferred at B.
Evaluate π2 = {Switch, Boost}. Its values are V2(A) = 4.5 and V2(B) = 10. A final check gives Wait = 1 + 0.50 × 4.5 = 3.25, below Switch = 4.5. At B, Idle = 2 + 0.50 × 10 = 7 is below Boost = 10. The policy remains unchanged and satisfies the Bellman optimality comparisons.
There were two policy changes, each followed by reevaluation, and a final stability check. The temporary value 7 for Boost in the first comparison was a one-step deviation followed by the old policy, not Boost's eventual repeated-use value 10.

Illustrative case study

Fictional case: PinePlanning uses policy iteration on a compact model to establish a benchmark for a scheduling experiment. The first improvement changes decisions only in one part of the state space. After reevaluation, additional changes become worthwhile elsewhere.
The team saves each policy and its evaluation residual, allowing a reviewer to distinguish a genuine fixed point from termination caused by an overly loose numerical tolerance. This fictional case illustrates an auditable solving process. It does not claim that a compact model captures every operating condition or that exact optimization of that model guarantees real-world performance.

Common misconceptions and mistakes

Policy iteration is not repeated sampling of arbitrary new policies. Its improvement step is driven by evaluated continuation values. Exact policy evaluation is different from one value-update sweep. Policy stability based on approximate values requires attention to error, and arbitrary tie switching can obscure termination. The method also depends on a usable transition and reward model in its classical form.

Business use

Use policy iteration when an explicit model is available and the state-action space is small enough for reliable evaluation and improvement. Report the model, discounting, evaluation tolerance, and stopping criterion. For larger problems, compare computational cost with alternative solvers or approximate methods. A benchmark policy is only as relevant as the assumptions of the model used to calculate it.

Check your understanding

Why does A switch only in the second improvement?

Answer: The first evaluation still assigns B the lower value of the old Idle policy.

What is the final value at A?

Answer: 4.5.

Why is the final unchanged policy meaningful here?

Answer: Its exact values satisfy every stated optimality comparison.

Related terms

Learn next

Next, compare exact evaluation with a small fixed number of evaluation sweeps. Then study how value iteration and modified policy iteration balance computation per cycle against the number of cycles required.

Sources

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, second edition, Section 4.3: https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf Prashanth L. A., Lectures on Reinforcement Learning Theory, Discounted Cost MDPs: https://cse.iitm.ac.in/~prashla/notes/rlbook/discounted-cost-mdps.html

Previous: Policy improvement Next: Policy loss