Policy Iteration Algorithm and Example
The example begins with an equiprobable random policy.
From Assessment to Better Choices
Policy iteration is an iterative method for computing an optimal policy in a Markov Decision Process. Its central pattern is simple: begin with a policy, evaluate how well that policy performs, use the resulting value information to choose better actions, and repeat until the policy stops changing.
The two objects in this process have different jobs. The policy is the rule that chooses actions. The value function is the information produced by evaluation about the value of states under that policy. Evaluation does not itself become the new policy. Instead, the value function supplies the evidence used during improvement.
Tracing the First Evaluation
Evaluating the Starting Policy
The example begins with an equiprobable random policy. Trace what policy iteration does before it can improve that policy.
Start with π(s): The algorithm begins with a policy that distributes its choices equiprobably. At this point, the policy is the rule being assessed, not the result of the assessment.
Initialize V(s): Policy iteration begins with arbitrary values V(s). These values will be updated while the current policy is evaluated.
Update state values: Iterative policy evaluation updates V(s) for the current policy. Each update is compared with the value saved before the update.
Track ∆: The algorithm tracks the largest update through ∆. This quantity is used to check whether the value estimates have converged sufficiently.
Pass values to improvement: After evaluation, the value function provides the information needed to form a greedy policy. The policy is now ready to be improved rather than selected randomly.
Evaluation produces value information for the starting policy. It does not by itself make the stopping decision; policy improvement and the policy-stability check still have to occur.
A useful implementation trace records five checkpoints: the value saved before an update, the newly computed value, the running maximum ∆, the old action, and the updated action. These checkpoints separate three possible sources of an unexpected result: an evaluation problem, an action-selection problem, or a termination-control problem.
Greedy Improvement
A policy is greedy with respect to a value function when it chooses the action with the highest expected return according to that value function. In policy iteration, improvement updates π(s) using an argmax over expected returns.
The word greedy describes how the next action is selected, not how the original policy was selected. The initial example uses an equiprobable random policy. The improved policy is different: it uses the current value function to select the highest-value action. Thus, evaluation supplies the values, while improvement turns those values into a new decision rule.
Turning Values into a Policy
The evaluated value function contains information about expected returns. What does policy improvement do with that information?
Inspect the current values: Use the value function produced by evaluating the current policy.
Compare available actions: Determine the expected return associated with the candidate actions using the current value information.
Select the maximum: Use an argmax to select the action with the highest expected return.
Replace the policy choice: Update π(s) so that the policy chooses the selected greedy action rather than retaining the original equiprobable choice.
The improved policy is value-guided. It is not a random redraw of the starting policy.
Why Improvement Is Safe
The policy improvement theorem explains why replacing the original action choice with a greedy choice is safe. The theorem guarantees that the greedy policy is no worse than the policy whose value function was used to create it. The value function therefore acts as evidence for a policy change that cannot reduce performance according to the theorem.
The One-Iteration Result
The example is deliberately useful because it does not show a long chain of increasingly refined policies. After the initial equiprobable random policy is evaluated, the greedy policy formed from its value function is already optimal. It reaches terminal states in the minimum number of steps.
The key reasoning is not that policy iteration always finishes after one iteration. The source example finishes quickly because its first greedy improvement already identifies the optimal policy. Since that policy proceeds to terminal states in the minimum number of steps, another improvement cannot produce a better policy for this example.
Explaining the Stopping Point
Why does the example stop after the first policy improvement?
Initial state: The policy begins as an equiprobable random policy.
Evaluation: The current policy is evaluated, producing value information and tracking the largest update through ∆.
Improvement: The value function is used to form a greedy policy by choosing the highest-value action.
Optimality of the result: In this example, the greedy policy already reaches terminal states in the minimum number of steps.
No further change: Because the first improved policy is already optimal, the policy is stable and the algorithm stops.
One policy-improvement step is enough in this example. This is a property of the example's result, not a claim that every policy-iteration problem requires only one iteration.
The Stability Decision
Policy evaluation convergence and policy stability are different checks. During evaluation, the algorithm updates V(s) and tracks ∆ to determine whether the value estimates have converged. The algorithm does not stop merely because that value-evaluation phase has converged. It must also complete policy improvement and compare the old action with the updated action.
When tracing policy iteration, record the old action before improvement and the updated action afterward. Then record the final policy-stable decision. This prevents a common debugging mistake: treating convergence of V(s) as if it were the same event as stability of π(s).
Treating the value function as the policy.
The policy is the action-selection rule. The value function supplies value information used to create a greedy policy.
Fix:
Say that evaluation produces V(s), and improvement uses V(s) to update π(s).Assuming the improved policy is still random.
The initial policy is equiprobable, but the improved policy selects the highest-value action using an argmax over expected returns.
Fix:
Distinguish the random starting policy from the value-guided greedy policy.Stopping when value evaluation converges.
The algorithm stops only after policy improvement and the policy-stability decision.
Fix:
Compare the old and updated actions before deciding whether to stop.Assuming every problem needs only one iteration.
This example finishes after one improvement because the greedy policy is already optimal.
Fix:
Treat the one-iteration result as a property of this example.
Trace It Yourself
Explain the complete stopping decision for the source example in your own words. Begin with the equiprobable random policy, identify what evaluation produces, describe how improvement selects the next action rule, and finish by explaining why the algorithm stops after one iteration.
Hints
- Keep the policy and value function as separate objects.
- Mention V(s) and the largest update ∆ during evaluation.
- Mention the argmax over expected returns during improvement.
- The final reason for stopping is policy stability after the greedy policy is found to be optimal.
What do you think happens?
After value evaluation has converged, has policy iteration necessarily finished?
Reveal answer
Answer: No, policy improvement and the policy-stability decision still have to occur.
Evaluation updates V(s) and tracks ∆, but the algorithm stops only after it improves the policy and determines whether the old and updated actions make the policy stable.
Key Takeaways
- Policy iteration alternates between evaluating the current policy and improving it.
- Evaluation updates V(s), tracks the largest update through ∆, and checks value convergence.
- Improvement uses the value function to select a greedy action through an argmax over expected returns.
- The policy improvement theorem guarantees that the greedy policy is no worse than the original policy.
- The example stops after one iteration because its first greedy policy is already optimal and reaches terminal states in the minimum number of steps.
- The final stopping decision depends on policy stability, not on value-evaluation convergence alone.
Key Takeaways
- Policy iteration uses evaluation as evidence for policy improvement.
- The value function and policy are distinct: V(s) supplies value information, while π(s) chooses actions.
- A greedy policy chooses the action with the highest expected return according to the current value function.
- The policy improvement theorem guarantees that the improved policy is at least as good as the original.
- The example converges after one iteration because the first greedy policy is already optimal, but the general algorithm stops only after the policy is stable.