Policy Improvement Theorem

From Evaluation to Improvement

Policy improvement starts with an original policy and its value function, written as vπ. The value function provides the basis for comparing possible actions. The goal is to create a new policy that chooses the action that looks best according to that value function.

Building the Greedy Policy

To construct a greedy policy, examine each decision state separately. For that state, use the original policy's value function as the basis for a one-step comparison of the available actions. Select an action with the greatest resulting value. Repeating this choice at every state produces a new policy, called a greedy policy with respect to vπ.

The One-Step Lookahead

The comparison is described as a one-step lookahead because each candidate action is evaluated by looking at what happens immediately after taking it. The evaluation considers the current state, the candidate action, the immediate reward, and the value associated with the next state. These comparisons provide the action values used to decide which action is greedy.

The important point is that the original value function supplies the comparison basis. The greedy policy is not chosen by looking only at the action's immediate result; the one-step comparison also uses the value associated with what follows.

Choosing Among Action Values

Why Improvement Is Guaranteed

The policy improvement theorem connects the local greedy choice to a global guarantee about the new policy. When the new policy is constructed by choosing maximum-valued actions according to vπ, it meets the conditions of the theorem. The resulting policy is guaranteed to be as good as or better than the original policy.

Common Construction Mistakes

• Choosing an action without comparing it with the other available actions.

  Greedy construction requires selecting an action with the maximum value according to the comparison.

  Fix: Compare all available action values at the state before choosing.

• Treating the original policy and the greedy policy as the same policy.

  The original policy supplies vπ, while the new policy is constructed from maximum-valued actions according to that value function.

  Fix: Keep the original policy as the source of the value function and construct the greedy policy separately.

• Rejecting a greedy policy because it breaks a tie differently.

  Ties between maximum-valued actions may be broken arbitrarily.

  Fix: Accept any tied maximum-valued action as a valid greedy choice.

• Interpreting the theorem as requiring strict improvement.

  The guarantee is that the new policy is as good as or better than the original policy.

  Fix: Allow both equal performance and improved performance under the theorem's guarantee.

Practice Check

Key Takeaways

1. Policy improvement begins with an original policy and its value function vπ.
2. A greedy policy chooses maximum-valued actions according to one-step comparisons based on vπ.
3. The one-step lookahead considers the current state, candidate action, immediate reward, and next-state value.
4. Ties among maximum-valued actions may be broken arbitrarily.
5. The policy improvement theorem guarantees that the greedy policy is as good as or better than the original policy.