Policy Iteration Fundamentals

Why the Cycle Matters

Policy iteration searches for an optimal policy by repeating two jobs. First, it evaluates the current policy to obtain value information. Second, it uses that information to improve the policy. The output of evaluation guides improvement, and the improved policy becomes the input to the next evaluation.

Evaluation and Improvement

The evaluation stage computes the value function associated with the current policy. In other words, it supplies information about how the current policy performs. The improvement stage then uses that evaluation to change the policy. These stages have different responsibilities: evaluation changes the value information being calculated for a policy, while improvement changes the policy itself.

Following Three Policies

This example is intentionally abstract. The policy names do not describe particular actions or rewards. Their purpose is to make the sequence visible: π0 is evaluated, that information produces π1, π1 is evaluated, and that information can produce π2.

Why Improvement Stops

Policy improvement makes strict progress whenever the current policy is not optimal. Therefore, an improving iteration cannot continue forever while producing strictly better policies. When improvement no longer produces a strictly better policy, the current policy is optimal.

Finite Termination

In a finite Markov decision process, only finitely many policies are available. Each improvement step produces a strictly better policy unless the current policy is already optimal. Because an infinite sequence of strict progress cannot move through a finite set of possible policies, policy iteration must reach an optimal policy after finitely many iterations. At that point, it also reaches the optimal value function.

Reusing Value Information

Policy evaluation is itself an iterative computation. When a new policy is evaluated, a useful implementation choice is to begin with the value function from the previous policy instead of starting with an unrelated value function. The previous value function typically gives evaluation a better starting point because the value function changes little when one policy is replaced by the next. As a result, evaluation for the new policy can converge much faster.

Mistakes to Avoid

• Treating policy evaluation and policy improvement as the same operation.

  Evaluation supplies value information, while improvement uses that information to change the policy.

  Fix: Describe evaluation as computing the value function for the current policy, then describe improvement as producing a better policy from that evaluation.

• Assuming policy iteration can keep improving forever.

  There are finitely many possible policies, and every nonterminal improvement is strictly better.

  Fix: Connect strict improvement with the finite set of policies to explain finite termination.

• Stopping merely because one update was inconvenient.

  The convergence result identifies optimality when policy improvement no longer produces a strictly better policy.

  Fix: State that no strictly better policy is produced, so the current policy is optimal.

• Restarting every evaluation from an unrelated value function.

  The previous value function typically changes little from one policy to the next and can provide a better starting point.

  Fix: Reuse the previous value function when beginning evaluation of the new policy.

Check Your Understanding

Key Takeaways

1. Policy iteration alternates between evaluating the current policy and improving it.
2. Policy evaluation supplies the value information needed by policy improvement.
3. In a finite Markov decision process, every nonterminal improvement is strictly better, so the process reaches an optimal policy after finitely many iterations.
4. When no strictly better policy can be produced, the current policy is optimal.
5. Reusing the previous value function gives the next evaluation a better starting point and can make it converge much faster.