Greedy Policy

From Evaluation to Improvement

A policy tells an agent how to act. Policy iteration asks whether the current policy can be improved by using information about the value of states or state-action pairs. It repeats two activities: evaluate the current policy, then improve it by choosing actions that look better according to the value information.

Value Information and Greedy Choice

The value function supplies an estimate of expected return or utility for states or state-action pairs. Policy improvement uses this information for a one-step lookahead: from the current decision, compare the available actions using the original policy's value information, then choose an action with the highest value.

The word greedy describes the decision rule, not a claim that the original policy was poor. The new policy simply uses the available value information to select the best-looking action at each decision. Its comparison is based on the value function of the original policy.

Constructing the Improved Policy

Why Improvement Is Guaranteed

The policy improvement theorem provides the central guarantee: a greedy policy constructed from the original policy's value function is as good as or better than the original policy. The theorem applies because the new policy chooses actions according to the maximum available value information in the one-step comparison.

The One-Iteration Outcome

In the Figure 4.1 trace, policy iteration begins with an equiprobable random policy. That policy is evaluated, and its value function is then used to form a greedy policy. In this particular problem, the resulting greedy policy is already optimal because it proceeds to terminal states in the minimum number of steps.

This example reaches its final policy after one improvement iteration because no better policy is needed after the greedy choice is formed. That stronger conclusion belongs to the particular example. The general policy improvement theorem guarantees that the greedy policy is as good as or better than the original; it does not by itself say that every greedy policy is immediately optimal.

Common Reasoning Errors

• Treating a greedy policy as an arbitrary new policy

  A greedy policy is specifically constructed by selecting maximum-valued actions according to the original policy's value function.

  Fix: Use the original policy's value function as the basis for a one-step comparison.

• Assuming the theorem guarantees immediate optimality in every problem

  The theorem guarantees that the new policy is as good as or better than the original. Immediate optimality is a stronger result shown by the particular Figure 4.1 example.

  Fix: Separate the general theorem guarantee from the stronger outcome of a specific example.

• Rejecting a greedy choice when values are tied

  Ties between maximum-valued actions may be broken arbitrarily.

  Fix: Select any one of the actions tied for the maximum value.

• Confusing evaluation with improvement

  Evaluation provides value information; improvement uses that information to construct a new policy.

  Fix: Keep the sequence clear: evaluate the current policy, then form a greedy policy from its value function.

Practice: Choose Greedily

Key Takeaways

1. Policy iteration alternates between evaluating a policy and improving it.
2. The value function of the original policy supplies the information for a one-step action comparison.
3. A greedy policy selects an action with the maximum value at each decision.
4. The policy improvement theorem guarantees that the greedy policy is as good as or better than the original policy.
5. In the Figure 4.1 example, the greedy policy is already optimal after one iteration because it reaches terminal states in the minimum number of steps.