Does improvement always change every action?

No. Some current actions may already maximize the relevant comparison.

Can tied actions be retained?

Yes. Consistent tie handling can avoid unnecessary changes.

Is policy improvement the same as policy iteration?

No. Policy iteration repeatedly alternates evaluation and improvement.

AI Glossary / Reinforcement learning and robotics / Intermediate

Policy improvement

Definition

Policy improvement is the process of changing a decision policy using information about the value of its actions. In the standard dynamic-programming setting, it constructs a policy that is greedy with respect to the current policy's exact value function. Under the relevant assumptions, the new policy performs at least as well as the old one, although a single improvement step need not produce an optimal policy.

What it means

Before changing behavior, an agent can ask what would happen if it took a different action now and then followed its existing policy afterward. That comparison uses more than the immediate reward: it includes the value of the state reached next.
If a new action has a better such continuation value, changing the decision can improve the policy. Repeating this reasoning across states turns value estimates into behavior changes. The conclusion depends on those values and the model assumptions.

How it works

Let Vπ(s) be the expected return from state s under the current policy π. For each candidate action a, calculate Qπ(s, a): its expected immediate reward plus the discounted value Vπ of the next state. This evaluates taking a once and then returning to π.
A greedy improved policy selects an action maximizing Qπ in each state. For a finite discounted MDP with exact values, the policy improvement theorem ensures that this policy's value is no lower than Vπ at any state. Strict improvement may occur in only some states, so the theorem should not be read as promising a strictly larger number everywhere.
The new policy is then a complete decision rule, not a temporary instruction to change only one action and immediately revert. Its actual value can differ from the one-step comparisons because it follows the new choices at later states as well.
With approximate values, incomplete action coverage, or an inaccurate model, the exact theorem does not automatically apply. Practical improvement procedures may use constraints, uncertainty estimates, or conservative steps. These additions must be assessed on their own terms rather than labeled guaranteed improvements merely because an estimated value increases.

Three practical examples

Inventory planning: change a replenishment decision after comparing immediate cost and expected future stock conditions under a current policy.
Simulated navigation: update route choices using values that include the consequences of later decisions.
Scheduling: replace a current job-selection rule with actions favored by an evaluated continuation model, then reassess the resulting policy.

Think of it this way

Think of revising a travel guide using an estimate of how good the rest of each route will be. A better first turn depends on what happens afterward. Once several later turns improve, an earlier turn that previously looked unattractive may become worthwhile too. That is why one round of revision may not be enough.

Worked example

Consider a fictional deterministic episodic problem with states A, B, and C and discount factor γ = 0.80. At A, Finish ends the episode with reward 2, while Advance gives reward 0 and moves to B. At B, Finish ends with reward 1, while Advance gives reward 0 and moves to C. At C, the only action ends the episode with reward 10. Terminal continuation value is zero.
The initial policy finishes at both A and B. Its exact values are Vπ(A) = 2, Vπ(B) = 1, and Vπ(C) = 10.
Perform one simultaneous greedy improvement using these old values. At A, Finish is worth 2 and Advance is worth 0 + 0.80 × 1 = 0.8, so the improved policy still chooses Finish. At B, Finish is worth 1 and Advance is worth 0 + 0.80 × 10 = 8, so it changes to Advance.
Now evaluate that new policy. Its values are 2 at A, 8 at B, and 10 at C. No state is worse, but A has not improved yet. A second improvement uses these updated values: Advance at A is now worth 0 + 0.80 × 8 = 6.4, so A changes as well.
The final route A to B to C yields rewards 0, 0, and 10, whose discounted return is 0 + 0.80 × 0 + 0.80² × 10 = 6.4. This exceeds the original value 2 at A.
The first improvement was valid even though it was not globally optimal. Using B's newly improved value during the first simultaneous comparison would describe a different update procedure from the one specified here.

Illustrative case study

Fictional case: BeechPlanning evaluates a small scheduling policy and changes several decisions based on their continuation values. Its team initially reports that every decision should now be strictly better. A review shows that some states retain the same action and value while other states improve.
The team corrects its claim, reevaluates the new policy, and performs another improvement step where appropriate. For a larger approximate model, it also tests whether predicted gains appear in separate simulations. This fictional case illustrates careful interpretation of improvement, not a measured result for a real scheduling system.

Common misconceptions and mistakes

Greedy with respect to a value function is not the same as greedy for immediate reward. One improvement step is not generally a complete optimization procedure. The one-step action values refer to continuation under the old policy, while the new policy's full value requires its own evaluation. An increase in estimated return is also not proof of an increase in true return when the estimates are inaccurate.

Business use

This concept supports transparent review of why an automated decision rule changes. Record the baseline policy, the values used for comparison, and the resulting new policy. Separate the predicted improvement from subsequent measured performance. In small exact models, the mathematical guarantee can be checked directly; in larger systems, estimation error and operational constraints become central to the assessment.

Check your understanding

Why does A stay unchanged after the first improvement?

Answer: The old value at B is only 1.

Which state improves immediately?

Answer: B, whose new value becomes 8.

Why does the second step change A?

Answer: Reevaluation reveals the better continuation now available from B.

Related terms

Policy evaluation
Policy iteration
Greedy policy
Bellman equation
Optimal policy
action-value function
generalized policy iteration
approximate dynamic programming

Learn next

Next, combine evaluation and improvement into a complete policy-iteration loop. Then investigate how small value-estimation errors can change action rankings when alternatives have similar returns.

Policy iteration

Sources

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, second edition, Sections 4.2–4.3: https://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf Prashanth L. A., Lectures on Reinforcement Learning Theory, Discounted Cost MDPs, policy iteration: https://cse.iitm.ac.in/~prashla/notes/rlbook/discounted-cost-mdps.html

Previous: Policy gradient theorem Next: Policy iteration