Concepts / Policy Iteration Algorithm and Example

Policy Iteration Algorithm and Example

The example begins with an equiprobable random policy.

  • Programming

From Assessment to Better Choices

Policy iteration is an iterative method for computing an optimal policy in a Markov Decision Process. Its central pattern is simple: begin with a policy, evaluate how well that policy performs, use the resulting value information to choose better actions, and repeat until the policy stops changing.

The two objects in this process have different jobs. The policy is the rule that chooses actions. The value function is the information produced by evaluation about the value of states under that policy. Evaluation does not itself become the new policy. Instead, the value function supplies the evidence used during improvement.

Initial policyπ(s)Policy evaluationupdate V(s)Policy improvementchoose greedy actionsPolicy stable?Stopoptimal policyassessvalue informationcompare policiesyesno
What happens next as the algorithm evaluates a policy, improves it, and decides whether to stop?

Tracing the First Evaluation

Worked example

Evaluating the Starting Policy

The example begins with an equiprobable random policy. Trace what policy iteration does before it can improve that policy.

  1. 1
    Start with π(s)

    The algorithm begins with a policy that distributes its choices equiprobably. At this point, the policy is the rule being assessed, not the result of the assessment.

  2. 2
    Initialize V(s)

    Policy iteration begins with arbitrary values V(s). These values will be updated while the current policy is evaluated.

  3. 3
    Update state values

    Iterative policy evaluation updates V(s) for the current policy. Each update is compared with the value saved before the update.

  4. 4
    Track ∆

    The algorithm tracks the largest update through ∆. This quantity is used to check whether the value estimates have converged sufficiently.

  5. 5
    Pass values to improvement

    After evaluation, the value function provides the information needed to form a greedy policy. The policy is now ready to be improved rather than selected randomly.

Result

Evaluation produces value information for the starting policy. It does not by itself make the stopping decision; policy improvement and the policy-stability check still have to occur.

Current V(s)saved valueValue updatenew V(s)∆largest updateConvergence checkNext evaluation sweepcomputemeasure changechecknot yetupdate again
How do repeated value updates change the estimated value of each state, and how does evaluation recognize convergence?

A useful implementation trace records five checkpoints: the value saved before an update, the newly computed value, the running maximum ∆, the old action, and the updated action. These checkpoints separate three possible sources of an unexpected result: an evaluation problem, an action-selection problem, or a termination-control problem.

Greedy Improvement

Definition

A policy is greedy with respect to a value function when it chooses the action with the highest expected return according to that value function. In policy iteration, improvement updates π(s) using an argmax over expected returns.

The word greedy describes how the next action is selected, not how the original policy was selected. The initial example uses an equiprobable random policy. The improved policy is different: it uses the current value function to select the highest-value action. Thus, evaluation supplies the values, while improvement turns those values into a new decision rule.

Original policyequiprobable choiceValue functionexpected returnsCandidate actionscompare valuesGreedy policyhighest-value actionevaluatescoreargmax
How does the current value function determine which action is greedy and replace the action chosen by the original policy?
Worked example

Turning Values into a Policy

The evaluated value function contains information about expected returns. What does policy improvement do with that information?

  1. 1
    Inspect the current values

    Use the value function produced by evaluating the current policy.

  2. 2
    Compare available actions

    Determine the expected return associated with the candidate actions using the current value information.

  3. 3
    Select the maximum

    Use an argmax to select the action with the highest expected return.

  4. 4
    Replace the policy choice

    Update π(s) so that the policy chooses the selected greedy action rather than retaining the original equiprobable choice.

Result

The improved policy is value-guided. It is not a random redraw of the starting policy.

Why Improvement Is Safe

The policy improvement theorem explains why replacing the original action choice with a greedy choice is safe. The theorem guarantees that the greedy policy is no worse than the policy whose value function was used to create it. The value function therefore acts as evidence for a policy change that cannot reduce performance according to the theorem.

Original policyvalue function sourceValue functionexpected returnsGreedy policyno worseevaluategreedy improvementat least as good
How does choosing an action that is greedy with respect to the value function ensure that the improved policy is at least as good as the original?

The One-Iteration Result

The example is deliberately useful because it does not show a long chain of increasingly refined policies. After the initial equiprobable random policy is evaluated, the greedy policy formed from its value function is already optimal. It reaches terminal states in the minimum number of steps.

Equiprobable policyinitial choice ruleEvaluated valuesevidence for improvementGreedy optimal policyminimum steps to terminalstatesevaluateimprove once
What changes from the initial equiprobable random policy to the improved policy, and why is no further improvement needed?

The key reasoning is not that policy iteration always finishes after one iteration. The source example finishes quickly because its first greedy improvement already identifies the optimal policy. Since that policy proceeds to terminal states in the minimum number of steps, another improvement cannot produce a better policy for this example.

Worked example

Explaining the Stopping Point

Why does the example stop after the first policy improvement?

  1. 1
    Initial state

    The policy begins as an equiprobable random policy.

  2. 2
    Evaluation

    The current policy is evaluated, producing value information and tracking the largest update through ∆.

  3. 3
    Improvement

    The value function is used to form a greedy policy by choosing the highest-value action.

  4. 4
    Optimality of the result

    In this example, the greedy policy already reaches terminal states in the minimum number of steps.

  5. 5
    No further change

    Because the first improved policy is already optimal, the policy is stable and the algorithm stops.

Result

One policy-improvement step is enough in this example. This is a property of the example's result, not a claim that every policy-iteration problem requires only one iteration.

The Stability Decision

Policy evaluation convergence and policy stability are different checks. During evaluation, the algorithm updates V(s) and tracks ∆ to determine whether the value estimates have converged. The algorithm does not stop merely because that value-evaluation phase has converged. It must also complete policy improvement and compare the old action with the updated action.

Old actionπ(s)Updated actiongreedy choiceCompare actionsstable?Evaluate againpolicy changedStoppolicy stablebefore improvementafter improvementsamedifferent
How does the algorithm compare the old and improved actions to determine whether the policy is stable and should stop?
Best practice

When tracing policy iteration, record the old action before improvement and the updated action afterward. Then record the final policy-stable decision. This prevents a common debugging mistake: treating convergence of V(s) as if it were the same event as stability of π(s).

  • Common mistake

    Treating the value function as the policy.

    What it looks like
    Describing V(s) as if it directly chooses actions.
    Why it fails

    The policy is the action-selection rule. The value function supplies value information used to create a greedy policy.

    Do this instead

    Say that evaluation produces V(s), and improvement uses V(s) to update π(s).

  • Common mistake

    Assuming the improved policy is still random.

    What it looks like

    Describing the improved policy as another equiprobable choice.

    Why it fails

    The initial policy is equiprobable, but the improved policy selects the highest-value action using an argmax over expected returns.

    Do this instead

    Distinguish the random starting policy from the value-guided greedy policy.

  • Common mistake

    Stopping when value evaluation converges.

    What it looks like

    Ending the algorithm immediately after ∆ indicates convergence.

    Why it fails

    The algorithm stops only after policy improvement and the policy-stability decision.

    Do this instead

    Compare the old and updated actions before deciding whether to stop.

  • Common mistake

    Assuming every problem needs only one iteration.

    What it looks like

    Generalizing the result of this example to all policy-iteration problems.

    Why it fails

    This example finishes after one improvement because the greedy policy is already optimal.

    Do this instead

    Treat the one-iteration result as a property of this example.

Trace It Yourself

MEDIUM

Explain the complete stopping decision for the source example in your own words. Begin with the equiprobable random policy, identify what evaluation produces, describe how improvement selects the next action rule, and finish by explaining why the algorithm stops after one iteration.

Hints
  • Keep the policy and value function as separate objects.
  • Mention V(s) and the largest update ∆ during evaluation.
  • Mention the argmax over expected returns during improvement.
  • The final reason for stopping is policy stability after the greedy policy is found to be optimal.

What do you think happens?

After value evaluation has converged, has policy iteration necessarily finished?

  • Yes, because value convergence is the only stopping condition.

  • No, policy improvement and the policy-stability decision still have to occur.

Reveal answer
Answer:

No, policy improvement and the policy-stability decision still have to occur.

Evaluation updates V(s) and tracks ∆, but the algorithm stops only after it improves the policy and determines whether the old and updated actions make the policy stable.

Key Takeaways

  1. 1
    Policy iteration alternates between evaluating the current policy and improving it.
  2. 2
    Evaluation updates V(s), tracks the largest update through ∆, and checks value convergence.
  3. 3
    Improvement uses the value function to select a greedy action through an argmax over expected returns.
  4. 4
    The policy improvement theorem guarantees that the greedy policy is no worse than the original policy.
  5. 5
    The example stops after one iteration because its first greedy policy is already optimal and reaches terminal states in the minimum number of steps.
  6. 6
    The final stopping decision depends on policy stability, not on value-evaluation convergence alone.

At a glance

  • Policy iteration uses evaluation as evidence for policy improvement.
  • The value function and policy are distinct: V(s) supplies value information, while π(s) chooses actions.
  • A greedy policy chooses the action with the highest expected return according to the current value function.
  • The policy improvement theorem guarantees that the improved policy is at least as good as the original.
  • The example converges after one iteration because the first greedy policy is already optimal, but the general algorithm stops only after the policy is stable.

Related Topics

Related concepts

More concepts starting with P