Concepts / Policy Iteration Fundamentals

Policy Iteration Fundamentals

Keep the direction of information clear: policy evaluation supplies value information, and policy improvement uses that information to change the policy.

  • Programming

Why the Cycle Matters

Policy iteration searches for an optimal policy by repeating two jobs. First, it evaluates the current policy to obtain value information. Second, it uses that information to improve the policy. The output of evaluation guides improvement, and the improved policy becomes the input to the next evaluation.

Current policyπPolicy evaluationvalue informationValue functionVπPolicy improvementbetter policyUpdated policyπ′evaluatesuppliesguidesproducesnext input
What happens to the policy and its value function during each alternating stage?

Evaluation and Improvement

The evaluation stage computes the value function associated with the current policy. In other words, it supplies information about how the current policy performs. The improvement stage then uses that evaluation to change the policy. These stages have different responsibilities: evaluation changes the value information being calculated for a policy, while improvement changes the policy itself.

StatesPolicy πselected actionsAction choicesalternativesValue functionestimated returnsUpdated policyπ′maps tois evaluated intoinforms comparison ofcan produce
How are a policy, its value function, and action choices connected within one iteration?
Key point

Keep the direction of information clear: policy evaluation supplies value information, and policy improvement uses that information to change the policy.

Following Three Policies

Worked example

A generated policy sequence

Trace the control process through three successive policies named π0, π1, and π2.

  1. 1
    Start with π0

    Begin with the initial policy π0. The labels identify successive policies; they do not specify particular actions or rewards.

  2. 2
    Evaluate π0

    Policy evaluation computes the value function associated with π0.

  3. 3
    Improve π0

    Policy improvement uses the value information from π0 to produce π1.

  4. 4
    Evaluate π1

    If π1 is not yet optimal, evaluate π1 to compute its associated value function.

  5. 5
    Improve again

    Use the evaluation of π1 to produce π2. The same evaluation-improvement pattern continues until improvement no longer creates a strictly better policy.

Result

The process alternates between evaluating the current policy and improving it. It stops when the current policy is already optimal, so no strictly better policy is produced.

This example is intentionally abstract. The policy names do not describe particular actions or rewards. Their purpose is to make the sequence visible: π0 is evaluated, that information produces π1, π1 is evaluated, and that information can produce π2.

Why Improvement Stops

Policy improvement makes strict progress whenever the current policy is not optimal. Therefore, an improving iteration cannot continue forever while producing strictly better policies. When improvement no longer produces a strictly better policy, the current policy is optimal.

Current policyπAlternative actionscompare using valuesImproved policystrictly betterOptimal policyno improvementevaluate choicesan improvement existsno improvement exists
How does comparing alternative actions change the policy, and what does it mean when no action can improve it?

Finite Termination

In a finite Markov decision process, only finitely many policies are available. Each improvement step produces a strictly better policy unless the current policy is already optimal. Because an infinite sequence of strict progress cannot move through a finite set of possible policies, policy iteration must reach an optimal policy after finitely many iterations. At that point, it also reaches the optimal value function.

π0initial policyπ1strictly betterπ2strictly betterOptimal policyfinite stopping pointimprovementimprovementimprovement or recognition
How does each improving iteration move through finitely many possible policies until the process stops?
Key point

Finiteness does not merely make the process easier to describe. It provides the reason an indefinitely long sequence of strict improvements is impossible.

Reusing Value Information

Policy evaluation is itself an iterative computation. When a new policy is evaluated, a useful implementation choice is to begin with the value function from the previous policy instead of starting with an unrelated value function. The previous value function typically gives evaluation a better starting point because the value function changes little when one policy is replaced by the next. As a result, evaluation for the new policy can converge much faster.

Previous policyπNew policyπ′Previous valuefunctionstarting estimateNew evaluationfaster convergencewas evaluated intoreused to startis evaluated
How does the value function from the previous policy provide a better starting point for evaluating the new policy?

Mistakes to Avoid

  • Common mistake

    Treating policy evaluation and policy improvement as the same operation.

    What it looks like

    Saying that evaluation directly changes the policy.

    Why it fails

    Evaluation supplies value information, while improvement uses that information to change the policy.

    Do this instead

    Describe evaluation as computing the value function for the current policy, then describe improvement as producing a better policy from that evaluation.

  • Common mistake

    Assuming policy iteration can keep improving forever.

    What it looks like

    Ignoring the fact that the process runs in a finite Markov decision process.

    Why it fails

    There are finitely many possible policies, and every nonterminal improvement is strictly better.

    Do this instead

    Connect strict improvement with the finite set of policies to explain finite termination.

  • Common mistake

    Stopping merely because one update was inconvenient.

    What it looks like

    Calling a policy optimal without relating the stopping condition to improvement.

    Why it fails

    The convergence result identifies optimality when policy improvement no longer produces a strictly better policy.

    Do this instead

    State that no strictly better policy is produced, so the current policy is optimal.

  • Common mistake

    Restarting every evaluation from an unrelated value function.

    What it looks like

    Discarding the value function computed for the previous policy.

    Why it fails

    The previous value function typically changes little from one policy to the next and can provide a better starting point.

    Do this instead

    Reuse the previous value function when beginning evaluation of the new policy.

Check Your Understanding

MEDIUM

A finite Markov decision process starts with policy π0. Evaluation computes its value function, and improvement produces π1. Explain what must happen next if π1 is not optimal, and explain why the overall process cannot continue making strict improvements forever.

Hints
  • Name the two stages that repeat.
  • Use the fact that improvement is strict unless the current policy is optimal.
  • Connect the finite number of possible policies to termination.

What do you think happens?

When evaluating a new policy, which starting point is typically more useful: an unrelated value function or the value function from the previous policy?

  • An unrelated value function

  • The value function from the previous policy

Reveal answer
Answer:

The value function from the previous policy

The source explains that the value function typically changes little when one policy is replaced by the next, so reusing the previous value function can make the new evaluation converge much faster.

Key Takeaways

  1. 1
    Policy iteration alternates between evaluating the current policy and improving it.
  2. 2
    Policy evaluation supplies the value information needed by policy improvement.
  3. 3
    In a finite Markov decision process, every nonterminal improvement is strictly better, so the process reaches an optimal policy after finitely many iterations.
  4. 4
    When no strictly better policy can be produced, the current policy is optimal.
  5. 5
    Reusing the previous value function gives the next evaluation a better starting point and can make it converge much faster.

At a glance

  • Policy iteration repeatedly performs policy evaluation followed by policy improvement.
  • Evaluation computes value information for the current policy; improvement uses that information to produce a better policy.
  • Strict improvement and a finite set of possible policies guarantee finite termination at an optimal policy and its optimal value function.
  • Reusing the previous value function can speed up evaluation of the next policy because successive value functions typically change little.

Related Topics

Related concepts

More concepts starting with P