Reinforcement Learning

Policy Iteration

Policy iteration alternates fixed-policy value evaluation with greedy policy improvement until the policy stops changing.

status: reviewimportance: criticaldifficulty 4/5math: graduateread: 18mlive demo

Back to Reinforcement Learning Next: Monte Carlo Reinforcement Learning (review)

Concept Structure

Policy Iteration

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

1prerequisites

3next concepts

3related links

Learner Contract

What this page should let you do.

You are here becausePolicy iteration alternates fixed-policy value evaluation with greedy policy improvement until the policy stops changing.

This Reinforcement Learning concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

Before thisDynamic Programming and Value Iteration (review)

1 prerequisite listed; refresh them before leaning on the math or code.

Dynamic Programming and Value Iteration (review)

By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Then go nextMonte Carlo Reinforcement Learning (review)

Follow this edge after making one prediction here; the next page should reuse the result, not restart the route.

Test the linkManipulate one control and predict the visible change.Then continue to Monte Carlo Reinforcement Learning (review)

Claim/source review status

Substantive review recorded

1/1 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.

Claims1/1 reviewed

Sources3 cited

Codeattached

Demolive

Reviewed2026-07-03

Updatedpage 2026-07-03

Learning item flow

4/4 sections readyAsk about this Research room

ConceptPolicy IterationReinforcement Learning EquationPolicy Iteration equation 1Exact equation CodePolicy Iteration runnable code 1Exact runnable code DemoPolicy Iteration interactive demoInteractive demo ClaimPolicy iteration for a finite discounted tabular MDP alternates polic...Exact claim check SourceReinforcement Learning: An Introduction, Second EditionExact source

ConceptPolicy IterationReinforcement Learning

3 sources attachedLocal snapshot ready

concept:reinforcement-learning/policy-iteration

Codenearby Predictbefore reveal Roomitem handoff

01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

Value iteration asks, "What if every state greedily improves its value estimate on every sweep?"

Policy iteration slows that down on purpose. It asks:

If we commit to this policy, what is it actually worth?
After seeing those values, which actions would a one-step lookahead choose instead?

That separation is the whole idea. During policy evaluation, the policy is frozen. We do not ask whether another action is better yet. We only compute the value function $V^\pi$ for the policy $\pi$ we already have.

During policy improvement, the values are frozen. We compare all available action rows using $V^\pi$ as the future-value table, then replace the policy by a greedy one.

This is why policy iteration is such a clean control algorithm. It turns control into a loop of prediction and improvement:

\pi_0 \xrightarrow{\text{evaluate}} V^{\pi_0} \xrightarrow{\text{improve}} \pi_1 \xrightarrow{\text{evaluate}} V^{\pi_1} \xrightarrow{\text{improve}} \cdots

In a finite discounted tabular MDP, this loop cannot keep producing strictly new deterministic policies forever. When the greedy improvement step leaves the policy unchanged, the Bellman optimality condition has been reached.

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt

Equation 1 $V^\pi(s) = \sum_{a\in\mathcal{A}(s)} \pi(a\mid s) \sum_{s'\in\mathcal{S}} P(s'\mid s,a) \left[ R(s,a,s')+\gamma V^\pi(s') \right].$ Equation 2 $V^\pi(s) = \sum_{s'} P(s'\mid s,\pi(s)) \left[ R(s,\pi(s),s')+\gamma V^\pi(s') \right].$

Let $\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma)$ be a finite discounted MDP with known transition model $P(s'\mid s,a)$ , reward $R(s,a,s')$ , and $0\leq\gamma<1$ .

For a fixed policy $\pi(a\mid s)$ , policy evaluation computes the state-value function

V^\pi(s) = \sum_{a\in\mathcal{A}(s)} \pi(a\mid s) \sum_{s'\in\mathcal{S}} P(s'\mid s,a) \left[ R(s,a,s')+\gamma V^\pi(s') \right].

For a deterministic policy, this reduces to the action chosen by the policy:

V^\pi(s) = \sum_{s'} P(s'\mid s,\pi(s)) \left[ R(s,\pi(s),s')+\gamma V^\pi(s') \right].

Once $V^\pi$ has been evaluated, define the one-step lookahead action value

Q^\pi(s,a) = \sum_{s'} P(s'\mid s,a) \left[ R(s,a,s')+\gamma V^\pi(s') \right].

Policy improvement chooses a greedy action with respect to that evaluated value function:

\pi_{\text{new}}(s) \in \arg\max_{a\in\mathcal{A}(s)} Q^\pi(s,a).

The policy improvement theorem says that the greedy policy is at least as good as the policy it was built from. If the greedy policy equals the old policy in every state, then the policy already satisfies the Bellman optimality equation:

V^\pi(s) = \max_a Q^\pi(s,a).

So policy iteration is not "value iteration with a different name." Value iteration repeatedly applies the Bellman optimality backup to values. Policy iteration alternates an evaluation problem for a fixed policy with a greedy improvement problem for the policy.

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt

Runnable code 1states = ["Start", "Practice", "Confused", "Mastered"] gamma = 0.90 P = { "Start": {"drill":...python

states = ["Start", "Practice", "Confused", "Mastered"]
gamma = 0.90
P = {
    "Start": {"drill": [("Practice", .62, 1.0), ("Confused", .23, -.5), ("Mastered", .15, 3.0)],
              "skim": [("Start", .30, .1), ("Practice", .45, .5), ("Confused", .25, -.2)]},
    "Practice": {"repeat": [("Mastered", .55, 2.0), ("Practice", .30, .4), ("Confused", .15, -.6)],
                 "reflect": [("Mastered", .35, 1.2), ("Practice", .55, .5), ("Start", .10, 0.0)]},
    "Confused": {"ask": [("Practice", .65, .7), ("Confused", .25, -.4), ("Start", .10, 0.0)],
                 "guess": [("Mastered", .20, 1.6), ("Confused", .50, -.8), ("Start", .30, -.1)]},
    "Mastered": {"done": [("Mastered", 1.0, 0.0)]},
}

def q_value(V, s, a):
    return sum(p * (r + gamma * V[sp]) for sp, p, r in P[s][a])

def evaluate(pi, theta=1e-10):
    V = dict.fromkeys(states, 0.0)
    while True:
        old = V.copy()
        for s in states:
            V[s] = q_value(old, s, pi[s])
        if max(abs(V[s] - old[s]) for s in states) < theta:
            return V

pi = {"Start": "drill", "Practice": "reflect", "Confused": "guess", "Mastered": "done"}
for i in range(3):
    V = evaluate(pi)
    improved = {s: max(P[s], key=lambda a: q_value(V, s, a)) for s in states}
    print(i, {s: round(V[s], 3) for s in states}, "changes", [s for s in states if pi[s] != improved[s]])
    if improved == pi:
        break
    pi = improved

The policy is fixed inside evaluate. Only after evaluation do we compute the greedy action rows and decide whether the policy changes.

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

Use the Policy Iteration Improvement Lab to predict a greedy improvement step.

Choose an iteration, inspect the current fixed policy, then predict what changes after evaluating that policy and improving greedily with respect to $V^\pi$ . After reveal, compare the evaluated values, the old action row, the best action row, and the policy-stability verdict.

Before reveal, the evaluated values and greedy actions stay locked. That is the learning move: keep evaluation and improvement mentally separate before the table gives away the answer.

Live Concept Demo

Explore Policy Iteration

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 4/5graduatecode-aligned

Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what Policy Iteration should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

Policy iteration alternates fixed-policy value evaluation with greedy policy improvement until the policy stops changing.

Prediction open01 / Intuition

Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change Policy Iteration should make visible.

Visual Inquiry

Make the image answer a mathematical question

Policy iteration alternates fixed-policy value evaluation with greedy policy improvement until the policy stops changing.

4/4 stages readyLive demo connected

Visual cueWhich visible object should carry the first intuition?

Inspection depth2/4

Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make Policy Iteration easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

book · 2018Reinforcement Learning: An Introduction, Second EditionRichard S. Sutton and Andrew G. Barto

Canonical source for policy evaluation, policy improvement, the policy improvement theorem, and finite-MDP policy iteration.

Open source

course-notes · 2026Stanford CS234: Lecture 2, Making Sequences of Good Decisions Given a Model of the WorldStanford CS234

Graduate RL source for iterative policy evaluation, policy improvement from Q^pi, and the policy-iteration loop.

Open source

book · 2026Dive into Deep Learning: Value IterationDive into Deep Learning

Open textbook source for policy-evaluation updates in tabular reinforcement learning.

Open source

Claim Review

Policy iteration alternates fixed-policy value evaluation with greedy policy improvement until the policy stops changing.

Status1 substantive review recorded

Claims without a substantive review badge still need exact source-support review.

Sources3 references

sutton-barto-2018-rl, stanford-cs234-policy-iteration, d2l-policy-evaluation

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewedPolicy iteration for a finite discounted tabular MDP alternates policy evaluation of a fixed policy with greedy policy improvement using Q^pi(s,a); if the greedy policy no longer changes, the policy is optimal for that MDP.Claim metadata: source checked

The sources support the evaluate-then-improve decomposition: compute V^pi for the current fixed policy, compute Q^pi(s,a) by one-step lookahead through the known model, set the next policy greedily with respect to those Q values, and stop when the policy is unchanged.

Sources: Reinforcement Learning: An Introduction, Second Edition, Stanford CS234: Lecture 2, Making Sequences of Good Decisions Given a Model of the World, Dive into Deep Learning: Value IterationFinite discounted tabular teaching MDP only; excludes modified policy iteration, approximate evaluation, generalized policy iteration under function approximation, continuous state/action spaces, exploration, and sample-based learning.A bounded review summary is present; still check caveats and exact reference scope.

Checked Sutton/Barto Chapter 4 for policy evaluation, the policy improvement theorem, policy iteration, and finite-MDP convergence; checked Stanford CS234 Lecture 2 for iterative policy evaluation, the policy-iteration loop, and greedy improvement from Q^pi; checked D2L for the fixed-policy evaluation update. GPT Pro publication critique remains pending because 127.0.0.1:51672 is unavailable.

Reviewer: codex-local-source-review; reviewed 2026-07-03

source-span-sutton-barto-2018-rl source-span-stanford-cs234-policy-iteration source-span-d2l-policy-evaluation Equation 1 Equation 2 Runnable code 1 Interactive demo

Source support candidates

book 2018Reinforcement Learning: An Introduction, Second Edition

Canonical source for policy evaluation, policy improvement, the policy improvement theorem, and finite-MDP policy iteration.

course-notes 2026Stanford CS234: Lecture 2, Making Sequences of Good Decisions Given a Model of the World

Graduate RL source for iterative policy evaluation, policy improvement from Q^pi, and the policy-iteration loop.

book 2026Dive into Deep Learning: Value Iteration

Open textbook source for policy-evaluation updates in tabular reinforcement learning.

Mechanism checks

Equation 1

V^\pi(s) = \sum_{a\in\mathcal{A}(s)} \pi(a\mid s) \sum_{s'\in\mathcal{S}} P(s'\mid s,a) \left[ R(s,a,s')+\gamma V^\pi(s') \right].

Equation 2

V^\pi(s) = \sum_{s'} P(s'\mid s,\pi(s)) \left[ R(s,\pi(s),s')+\gamma V^\pi(s') \right].

Runnable code 1states = ["Start", "Practice", "Confused", "Mastered"] gamma = 0.90 P = { "Start": {"drill":...Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

Policy iteration alternates fixed-policy value evaluation with greedy policy improvement until the policy stops changing.

Readiness0/3 checks ready

Predict

Before touching the demo, predict one visible change that should happen in Policy Iteration.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Your answer canvas

Local checks

Claim

A concrete answer is on the canvas.

Mechanism

The answer names why the claim should hold.

Bridge

It touches the page context or a neighboring idea.

Misconception check

Grounded research drawerClose

ConceptPolicy IterationReinforcement Learning

Runnable code comparisonPolicy Iteration runnable code 1states = ["Start", "Practice", "Confused", "Mastered"] gamma = 0.90 P = { "Start": {"drill":...Prediction before revealPolicy Iteration interactive demoManipulate one control and predict the visible change.

Grounded room questionWhat is the smallest example that makes Policy Iteration click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.

Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptReinforcement Learning

Policy Iteration

Attached question

What is the smallest example that makes Policy Iteration click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action

Local action draft

This draft stays in this browser, attached to the selected learning item.

Draft noteNext action

No local draft saved.

Evidence to inspect

References to inspect: attached references on this page.
Definition, prerequisite, and contrast concept links
The equation or runnable code that makes the concept operational
One demo state that shows the invariant instead of a slogan

What would resolve this

The learner can state the mechanism in their own words
The learner can name the prerequisite that would repair confusion
The learner can predict how the mechanism changes under one perturbation

Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - Policy Iteration Selected item key: recorded for copy. Context: Reinforcement Learning Page anchor: recorded for copy. Open question: What is the smallest example that makes Policy Iteration click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context

concept/concept-notebook/reinforcement-learning/policy-iteration
concept:reinforcement-learning/policy-iteration

Learning Map

Before / Now / Try / Next

BeforeDynamic Programming and Value Iteration (review)

NowIntuition -> Math -> Code -> Demo

TryManipulate one control and predict the visible change.

NextMonte Carlo Reinforcement Learning (review)

Intuitionready
Mathready
Codeready
Interactive Demoready

AI Companion

Ask beside the selected object

Policy iteration alternates fixed-policy value evaluation with greedy policy improvement until the policy stops changing.

Your question

GoalComfortStyleStuck on

Context prompt

You are my AI learning companion for Continuous Function. Current context: Reinforcement Learning concept. Learning surface: Policy Iteration. What this page says: Policy iteration alternates fixed-policy value evaluation with greedy policy improvement until the policy stops changing. Current section: Intuition, math, code, and interactive demo. Suggested next step: Manipulate one control and predict the visible change.. Learner goal: Understand the idea. Learner comfort level: New to this. Preferred explanation style: Visual first. Task: Explain the central idea in plain language, then restate it with the exact math objects from the page. Answer in a way that helps me learn: ask one clarifying question only if needed, use intuition before notation, and end with one thing I should try on the page.

Domain

Reinforcement Learning

reinforcement-learningdynamic-programmingpolicy-iterationpolicy-evaluationpolicy-improvement

Prerequisites

Dynamic Programming and Value Iteration (review)

Leads To

Monte Carlo Reinforcement Learning (review)Temporal-Difference Learning (review)Q-Learning and SARSA (review)

Markov Decision Process Formalism (review)Bellman Equations (review)Dynamic Programming and Value Iteration (review)

Within this domain