Policy Iteration

Imagine planning a route when you know every road, travel time, and toll in advance. Policy iteration repeatedly asks two practical questions: “How good is my current plan?” and “Given that information, can I make the plan better?”

The two alternating steps
For a finite Markov decision process with known transition probabilities and rewards, policy iteration begins with any policy: a rule assigning an action to each state. It then alternates between:

Policy evaluation: calculate the value V^π(s), the expected discounted return from every state when following the current policy π. This means solving or repeatedly updating the Bellman expectation equation.
Policy improvement: at each state, compare the expected return of every available action, using those value estimates. Replace the policy’s action with the action having the highest expected return.

Why improvement is trustworthy
The improvement step is greedy, but it is not a blind guess: it accounts for immediate reward and for where each action is likely to lead. If a state’s current action gives a reward of 2 but moves the agent toward poor future states, another action with reward 1 can be preferred because its long-run return is higher. The policy improvement theorem guarantees that this replacement never makes the policy worse. In a finite problem, repeating evaluation and improvement reaches an optimal policy after a finite number of policy changes.

Role in reinforcement learning
Policy iteration is planning rather than trial-and-error learning: it requires the environment’s reward function and transition model. In a small Gridworld, it can compute the best route before an agent takes a real step. This makes it valuable as a clear baseline and as the foundation for generalized policy iteration, the idea behind many RL methods. Exact evaluation can be expensive, so practical variants stop evaluation early; value iteration effectively blends the two steps. When the model is unknown, methods such as DQN or PPO must estimate useful policies from collected experience instead, with no guarantee that their data covers every state.

Policy iteration is a dynamic-programming method for finding an optimal policy in a known Markov decision process. It alternates between policy evaluation, which computes the expected return of the current policy, and policy improvement, which replaces actions with greedy choices under those values. It matters because repeated evaluation and improvement converges to an optimal decision rule, providing a foundational model-based planning algorithm.

Imagine practising a route through a maze when you already have a map. First, you follow your current plan and ask, “How well does this route work?” Then you look at each junction and improve your choice wherever the map shows a better direction. You repeat: judge the plan, improve the plan, then judge it again.

Policy iteration is this idea applied to an AI making decisions. A policy simply means its plan for what to do in each situation. By repeatedly checking a plan’s likely results and replacing weaker choices with better ones, it steadily builds a stronger decision-making strategy—until no obvious improvement remains.