##  [Policy Iteration](/policy-iteration-0) 

 Definition

An algorithm for solving sequential decision problems (typically Markov decision processes) that alternates between evaluating the value of a current policy and improving the policy greedily with respect to that value until convergence to an optimal policy.

 

 

 

 

 

 





## Principle

Principle

Alternate exact or approximate policy evaluation and policy improvement: compute state-action or state values for the current policy, then update the policy to choose actions that maximize those values, repeating until no improvement occurs.

 

 

 

 

 





## Demonstration

Demonstration

In a finite-state Markov decision process, start with an arbitrary deterministic policy, compute the policy's value function by solving linear Bellman equations, then produce a new policy by choosing actions that maximize the one-step expected return; iterate these steps until the policy stabilizes.

 

 

 

 

## Misapplication

Misapplication

Using full policy iteration with exact evaluation on extremely large or continuous state spaces without approximation can be computationally infeasible and lead to excessive memory use or runtime; applying greedy improvement when evaluation is severely biased can cause oscillation.

 

 

 

 

 





## Consequence

Consequence

When applied correctly to finite MDPs or with stable approximations, policy iteration converges in a finite number of steps to an optimal policy and typically requires fewer iterations than naive value iteration.

 

 

 

 

## Reversal

Reversal

Reversing the concept yields value iteration: repeatedly apply Bellman optimality updates to value estimates without maintaining an explicit evaluated policy, deriving a policy only after values converge.

 

 

 

 

 





## Boundary

Boundary

Applies to sequential decision processes where policies and value functions are well-defined; excludes non-sequential optimization problems, games with adversarial agents unless reformulated, and settings without a Markovian structure or well-defined transition probabilities.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension exists between exact policy evaluation (which is stable but costly) and approximate or sample-based evaluation (which is scalable but can introduce bias and instability in the improvement step).

 

 

 

 

 





## Synthesis

Synthesis

Policy iteration is an alternating-evaluation scheme: evaluate a fixed decision rule, then improve the rule by greedy selection using the evaluated values; repeated alternation drives the system toward optimal sequential decisions under the assumed model.