Greedy Policy
The key pattern is evaluate, improve, and then evaluate the updated policy again when further improvement may be possible.
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.
The key pattern is evaluate, improve, and then evaluate the updated policy again when further improvement may be possible.
Value Information and Greedy Choice
A greedy policy is a policy constructed from the value function of an original policy. At each decision, it selects an action that has the maximum value according to that original policy's value function.
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
Selecting an Action from Lookahead Values
At one decision, three actions have lookahead values of 4, 7, and 5 according to the original policy's value function. Which action does the greedy policy select?
- 1Compare
Compare the values associated with all available actions: 4, 7, and 5.
- 2Find the maximum
The largest value is 7.
- 3Choose greedily
The greedy policy selects the action whose lookahead value is 7.
The action with value 7 becomes the greedy choice at this decision.
| Action values | Greedy choice |
|---|---|
| 4, 7, 5 | The action valued at 7 |
| 6, 6, 3 | Either action valued at 6 |
A greedy policy selects a maximum-valued action. If multiple actions share the maximum value, the tie may be broken arbitrarily.
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 theorem is a general guarantee. It does not merely describe a lucky result in one example: policy improvement produces a policy that is no worse than the original policy.
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.
Initial policy: equiprobable random policy Evaluation: obtain its value function
The policy has been evaluated but has not yet been improved.
Improved policy: greedy policy Result: reaches terminal states in the minimum number of steps
The greedy policy is already optimal for this particular problem.
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
Common mistake Treating a greedy policy as an arbitrary new policy
What it looks likeChoosing an action without comparing its value with the other available actions.
Why it failsA greedy policy is specifically constructed by selecting maximum-valued actions according to the original policy's value function.
Do this insteadUse the original policy's value function as the basis for a one-step comparison.
Common mistake Assuming the theorem guarantees immediate optimality in every problem
What it looks likeConcluding that every greedy policy must be optimal after one improvement.
Why it failsThe 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.
Do this insteadSeparate the general theorem guarantee from the stronger outcome of a specific example.
Common mistake Rejecting a greedy choice when values are tied
What it looks likeSeeing two actions with the same maximum value and concluding that no greedy policy can be formed.
Why it failsTies between maximum-valued actions may be broken arbitrarily.
Do this insteadSelect any one of the actions tied for the maximum value.
Common mistake Confusing evaluation with improvement
What it looks likeCalling the value function itself the improved policy.
Why it failsEvaluation provides value information; improvement uses that information to construct a new policy.
Do this insteadKeep the sequence clear: evaluate the current policy, then form a greedy policy from its value function.
Practice: Choose Greedily
A decision has four available actions with values 2, 9, 9, and 6 according to the original policy's value function. Which action or actions can the greedy policy choose, and why?
Hints
- Find the maximum value.
- Check whether more than one action has that value.
- Use the rule for breaking ties.
What do you think happens?
The action values are 2, 9, 9, and 6. Which action or actions can the greedy policy choose?
Reveal answer
Either action valued at 9
The greedy policy selects a maximum-valued action. The maximum value is 9, and ties between maximum-valued actions may be broken arbitrarily.
Key Takeaways
- 1Policy iteration alternates between evaluating a policy and improving it.
- 2The value function of the original policy supplies the information for a one-step action comparison.
- 3A greedy policy selects an action with the maximum value at each decision.
- 4The policy improvement theorem guarantees that the greedy policy is as good as or better than the original policy.
- 5In 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.
At a glance
- Policy iteration repeatedly evaluates the current policy and improves it.
- A greedy policy is formed by choosing maximum-valued actions according to the original policy's value function.
- One-step lookahead compares the available actions using that value information.
- The policy improvement theorem guarantees a result that is as good as or better than the original policy.
- Ties among maximum-valued actions may be broken arbitrarily.