Continuous Function

Reinforcement Learning

Dynamic Programming and Value Iteration

Value iteration turns the Bellman optimality backup into a known-model planning algorithm: sweep old values through every state until a greedy policy stabilizes.

status: reviewimportance: criticaldifficulty 4/5math: graduateread: 24mlive demo
Back to Reinforcement LearningNext: Policy Iteration (review)

Concept Structure

Dynamic Programming and Value 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
2related links

Learner Contract

What this page should let you do.

You are here becauseValue iteration turns the Bellman optimality backup into a known-model planning algorithm: sweep old values through every state until a greedy policy stabilizes.

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

Before thisBellman Equations (review)

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

Bellman Equations (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 nextPolicy Iteration (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 Policy Iteration (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
Sources4 cited
Codeattached
Demolive
Reviewed2026-07-03
Updatedpage 2026-07-03

Learning item flow

4/4 sections readyAsk about thisResearch room
ConceptDynamic Programming and Value IterationReinforcement LearningEquationDynamic Programming and Value Iteration equation 1Exact equationCodeDynamic Programming and Value Iteration runnable code 1Exact runnable codeDemoDynamic Programming and Value Iteration interactive demoInteractive demoClaimIn a finite discounted MDP with known transition and reward model, va...Exact claim checkSourceReinforcement Learning: An Introduction, Second EditionExact source
ConceptDynamic Programming and Value IterationReinforcement Learning
4 sources attachedLocal snapshot ready
concept:reinforcement-learning/dynamic-programming-value-iteration
CodenearbyPredictbefore revealRoomitem 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.
01

01

Intuition

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

Section prompt

Bellman optimality told us what a perfect value function must satisfy. Value iteration asks a more procedural question:

If the model is known, can we start with rough values and repeatedly improve every state?

Yes. One sweep applies the Bellman optimality backup to each state using the old value table. Then the new table replaces the old table. Another sweep repeats the same local computation with better future estimates.

That is dynamic programming: solve bigger planning subproblems by reusing smaller value estimates. Reward does not need to be physically adjacent to the starting state. If a state can reach reward in one step, its value rises first. States that can reach that state rise on later sweeps. Value information propagates backward through the transition graph.

The known-model assumption is the hinge. Value iteration is not learning from sampled experience. It assumes you can enumerate transition probabilities and rewards, then plan by applying the model.

Policy evaluation and value iteration look similar because both are Bellman updates. The difference is the operator. Policy evaluation averages action rows under a fixed policy. Value iteration improves toward control by taking the best action row at each state on every sweep.

02

02

Math

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

Section prompt
Equation 1(T⋆Vk)(s)=max⁡a∈A(s)∑s′∈SP(s′∣s,a)[R(s,a,s′)+γVk(s′)].(\mathcal{T}^{\star}V_k)(s) = \max_{a\in\mathcal{A}(s)} \sum_{s'\in\mathcal{S}} P(s'\mid s,a) \left[ R(s,a,s')+\gamma V_k(s') \right].Equation 2Vk+1(s)=(T⋆Vk)(s)for every s∈S.V_{k+1}(s) = (\mathcal{T}^{\star}V_k)(s) \quad \text{for every } s\in\mathcal{S}.

Let M=(S,A,P,R,γ)\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma) be a finite discounted MDP, where 0≤γ<10\leq \gamma < 1. The transition model is known: for each state ss and action aa, we can enumerate P(s′∣s,a)P(s'\mid s,a) and reward R(s,a,s′)R(s,a,s').

For any current value estimate Vk:S→RV_k:\mathcal{S}\to\mathbb{R}, define the Bellman optimality operator

(T⋆Vk)(s)=max⁡a∈A(s)∑s′∈SP(s′∣s,a)[R(s,a,s′)+γVk(s′)].(\mathcal{T}^{\star}V_k)(s) = \max_{a\in\mathcal{A}(s)} \sum_{s'\in\mathcal{S}} P(s'\mid s,a) \left[ R(s,a,s')+\gamma V_k(s') \right].

Value iteration applies this operator repeatedly:

Vk+1(s)=(T⋆Vk)(s)for every s∈S.V_{k+1}(s) = (\mathcal{T}^{\star}V_k)(s) \quad \text{for every } s\in\mathcal{S}.

The phrase "for every state" matters. In the standard synchronous version, the whole right-hand side uses the old table VkV_k. Only after all states have been updated do we replace it with Vk+1V_{k+1}.

The largest value change in one sweep is the residual

Δk=∥Vk+1−Vk∥∞=max⁡s∈S∣Vk+1(s)−Vk(s)∣.\Delta_k = \lVert V_{k+1}-V_k\rVert_\infty = \max_{s\in\mathcal{S}} |V_{k+1}(s)-V_k(s)|.

For a finite discounted MDP, T⋆\mathcal{T}^{\star} is a contraction in the max norm, so repeated sweeps converge to the unique optimal fixed point V⋆V^\star:

V⋆=T⋆V⋆.V^\star = \mathcal{T}^{\star}V^\star.

Once the value estimate is good enough, extract a greedy policy:

πgreedy(s)∈arg⁡max⁡a∈A(s)∑s′P(s′∣s,a)[R(s,a,s′)+γV(s′)].\pi_{\text{greedy}}(s) \in \arg\max_{a\in\mathcal{A}(s)} \sum_{s'}P(s'\mid s,a) \left[ R(s,a,s')+\gamma V(s') \right].

That last equation is why value iteration is a planning algorithm. It first computes good state values, then turns those values into action choices.

03

03

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 sweep(V):
    new, greedy = {}, {}
    for s in states:
        qs = {}
        for a, transitions in P[s].items():
            qs[a] = sum(p * (r + gamma * V[sp]) for sp, p, r in transitions)
        greedy[s] = max(qs, key=qs.get)
        new[s] = qs[greedy[s]]
    return new, greedy

V = dict.fromkeys(states, 0.0)
for k in range(4):
    V_next, pi = sweep(V)
    residual = max(abs(V_next[s] - V[s]) for s in states)
    print(k, {s: round(V_next[s], 3) for s in states}, pi, round(residual, 3))
    V = V_next

The code mirrors the math: every Qk(s,a)Q_k(s,a) row is computed from the old table VkV_k, and each new state value is the largest action row.

04

04

Interactive Demo

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

Section prompt

Use the Value Iteration Sweep Lab to predict how a whole value table changes.

Choose a sweep, then predict which state will change most when the old table is used to compute the next table. After reveal, inspect the residual, the greedy action chosen at each state, and the action rows behind the largest change.

Before reveal, the next values and residual stay locked. That matters because value iteration is not a notation exercise; the learning move is to anticipate how value information propagates through the model.

Live Concept Demo

Explore Dynamic Programming and Value 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 Dynamic Programming and Value 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

Value iteration turns the Bellman optimality backup into a known-model planning algorithm: sweep old values through every state until a greedy policy stabilizes.

Prediction open01 / Intuition
Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change Dynamic Programming and Value Iteration should make visible.

Visual Inquiry

Make the image answer a mathematical question

Value iteration turns the Bellman optimality backup into a known-model planning algorithm: sweep old values through every state until a greedy policy stabilizes.

4/4 stages readyLive demo connected
Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make Dynamic Programming and Value 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 dynamic programming, value iteration, Bellman optimality backups, and finite discounted MDP assumptions.

Open source
course-notes · 2026Stanford CS234: MDPs, Bellman Equations, and PlanningStanford CS234

Graduate RL source for planning with known dynamics, Bellman equations, dynamic programming, and value-iteration context.

Open source
course-notes · 2026UC Berkeley CS188: Value IterationUC Berkeley CS188

Course-note source for the synchronous value-iteration update, Bellman operator distinction, contraction framing, and policy extraction.

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

Open textbook source for turning the dynamic-programming principle into the value-iteration update in tabular reinforcement learning.

Open source

Claim Review

Value iteration turns the Bellman optimality backup into a known-model planning algorithm: sweep old values through every state until a greedy policy stabilizes.

Status1 substantive review recorded

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

Sources4 references

sutton-barto-2018-rl, stanford-cs234-value-iteration, berkeley-cs188-value-iteration, d2l-value-iteration

Local checks4 local checks

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

Substantively reviewedIn a finite discounted MDP with known transition and reward model, value iteration repeatedly applies the Bellman optimality operator to every state, using old values on the right-hand side, until the values approach the optimal fixed point; a greedy policy is then extracted from one-step action values.Claim metadata: source checked

The sources support finite discounted tabular value iteration as a dynamic-programming planning algorithm that repeatedly applies Bellman optimality backups under a known model, uses the previous sweep's values on the update's right-hand side, converges to the optimal value function under the discounted finite setting, and supports greedy policy extraction from the converged value estimate.

Sources: Reinforcement Learning: An Introduction, Second Edition, Stanford CS234: MDPs, Bellman Equations, and Planning, UC Berkeley CS188: Value Iteration, Dive into Deep Learning: Value IterationFinite tabular teaching MDP only; excludes asynchronous value iteration, function approximation, sampled TD/Q-learning, exploration, and full contraction proof details.A bounded review summary is present; still check caveats and exact reference scope.

Checked Berkeley CS188 and D2L for the synchronous update rule V_{k+1}(s)=max_a sum_{s'} P(s'|s,a)[R+gamma V_k(s')], convergence/fixed-point framing, and greedy policy extraction; checked the existing Sutton/Barto and Stanford CS234 RL spine for dynamic-programming and known-model planning context. 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-rlsource-span-stanford-cs234-value-iterationsource-span-berkeley-cs188-value-iterationsource-span-d2l-value-iterationEquation 1Equation 2Runnable code 1Interactive demo

Source support candidates

book 2018Reinforcement Learning: An Introduction, Second Edition

Canonical source for dynamic programming, value iteration, Bellman optimality backups, and finite discounted MDP assumptions.

course-notes 2026Stanford CS234: MDPs, Bellman Equations, and Planning

Graduate RL source for planning with known dynamics, Bellman equations, dynamic programming, and value-iteration context.

course-notes 2026UC Berkeley CS188: Value Iteration

Course-note source for the synchronous value-iteration update, Bellman operator distinction, contraction framing, and policy extraction.

book 2026Dive into Deep Learning: Value Iteration

Open textbook source for turning the dynamic-programming principle into the value-iteration update in tabular reinforcement learning.

Mechanism checks

Equation 1
(T⋆Vk)(s)=max⁡a∈A(s)∑s′∈SP(s′∣s,a)[R(s,a,s′)+γVk(s′)].(\mathcal{T}^{\star}V_k)(s) = \max_{a\in\mathcal{A}(s)} \sum_{s'\in\mathcal{S}} P(s'\mid s,a) \left[ R(s,a,s')+\gamma V_k(s') \right].
Equation 2
Vk+1(s)=(T⋆Vk)(s)for every s∈S.V_{k+1}(s) = (\mathcal{T}^{\star}V_k)(s) \quad \text{for every } s\in\mathcal{S}.
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

Value iteration turns the Bellman optimality backup into a known-model planning algorithm: sweep old values through every state until a greedy policy stabilizes.

Readiness0/3 checks ready
Predict

Before touching the demo, predict one visible change that should happen in Dynamic Programming and Value 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.

Grounded research drawerClose
ConceptDynamic Programming and Value IterationReinforcement Learning
Runnable code comparisonDynamic Programming and Value Iteration runnable code 1states = ["Start", "Practice", "Confused", "Mastered"] gamma = 0.90 P = { "Start": {"drill":...Prediction before revealDynamic Programming and Value Iteration interactive demoManipulate one control and predict the visible change.
Grounded room questionWhat is the smallest example that makes Dynamic Programming and Value 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

Dynamic Programming and Value Iteration

Attached question

What is the smallest example that makes Dynamic Programming and Value 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.

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 - Dynamic Programming and Value Iteration Selected item key: recorded for copy. Context: Reinforcement Learning Page anchor: recorded for copy. Open question: What is the smallest example that makes Dynamic Programming and Value 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/dynamic-programming-value-iteration concept:reinforcement-learning/dynamic-programming-value-iteration