Value Iteration

Watch state values and the optimal policy emerge in a grid world with the Bellman equation

Intermediate

Grid world

Tap a cell to see its Bellman backup. Switch to "Tap to edit" to change the map.

Controls

Algorithm

Discount γ0.90Step cost0.04Slip probability0.20

Sweeps per second

Sweeps

Status

Ready

Last max |ΔV|

–

Stop when max |ΔV| <

1e-4

Bellman backup for cell (2, 2)

Each action's expected value, Σ p × (r + γ × V(s')), using the current V. Step reward r = −0.040 (plus ±1 on entering a goal or pit), γ = 0.90.

↑ UpQ = −0.040
0.80 × (−0.040 + 0.90 × 0.000) + 0.10 × (−0.040 + 0.90 × 0.000) + 0.10 × (−0.040 + 0.90 × 0.000)
→ RightQ = −0.040
0.80 × (−0.040 + 0.90 × 0.000) + 0.10 × (−0.040 + 0.90 × 0.000) + 0.10 × (−0.040 + 0.90 × 0.000)
↓ DownQ = −0.040
0.80 × (−0.040 + 0.90 × 0.000) + 0.10 × (−0.040 + 0.90 × 0.000) + 0.10 × (−0.040 + 0.90 × 0.000)
← LeftQ = −0.040
0.80 × (−0.040 + 0.90 × 0.000) + 0.10 × (−0.040 + 0.90 × 0.000) + 0.10 × (−0.040 + 0.90 × 0.000)

V(s) ← max_a Q(s, a) = −0.040 (now 0.000)

Convergence

How to use this visualizer

1
Press Run to sweep through every state repeatedly, or One sweep to go a step at a time. Cell colour and number show V(s); the arrow is the greedy action.
2
Tap a cell (in "Tap to inspect" mode) to see its Bellman backup: the expected value of each of the four actions, and which one wins.
3
Switch to "Tap to edit" and tap cells to cycle empty, wall, goal and pit. The algorithm restarts from V = 0 on every change.
4
Raise the slip probability and watch the policy steer away from cells next to a pit. Raise the step cost and it prefers the shortest route, even past danger.
5
Switch to policy iteration: it evaluates the current policy fully, then improves it. It needs far fewer iterations, but each one does more work.

What value iteration does

A Markov decision process (MDP) describes a world where the next state depends only on the current state and the action. The value V(s) of a state is the total discounted reward an agent can expect from there if it acts optimally. Value iteration finds V by repeatedly applying the Bellman optimality equation to every state.

Start with V = 0 everywhere. After one sweep, only cells next to the goal or a pit know about it. After two sweeps, cells two moves away do, and so on: information spreads outwards from the rewards one step per sweep. Because each sweep shrinks the error by at least a factor γ, the values converge, and acting greedily with respect to the converged values is an optimal policy.

States and actions

Each open cell is a state. In every state the agent can try to move up, right, down or left.

Transition model

With slip probability p the move goes sideways instead (p/2 each way). Bumping into a wall or the edge leaves the agent in place.

Rewards

Every move costs the step cost. Entering the goal adds +1, entering a pit adds −1, and both end the episode.

Discount γ

A reward k steps away is worth γᵏ of a reward now. Smaller γ makes the agent short-sighted.

Key formulas

Bellman optimality equation

V(s) = max_a Σ_s' P(s' | s, a) [ R(s, a, s') + γ V(s') ]

P(s' | s, a): probability of landing in s' after trying action a in s
R(s, a, s'): reward for that transition (step cost, plus ±1 for a goal or pit)
γ: discount factor, 0 ≤ γ < 1

Greedy policy from values

π(s) = argmax_a Σ_s' P(s' | s, a) [ R(s, a, s') + γ V(s') ]

Stopping rule

stop when max_s |V_k+1(s) − V_k(s)| < θ

The convergence chart plots this quantity on a log scale. It falls roughly like γᵏ, a straight line.

Value iteration vs policy iteration

Value iteration does one cheap max-backup per state per sweep. Policy iteration alternates a full policy evaluation (solve V for a fixed policy) with a greedy improvement step, and usually stops after a handful of iterations because there are only finitely many policies.

Code

Python

def value_iteration(states, actions, P, R, gamma=0.9, theta=1e-4):
    """P[s][a] -> list of (prob, next_state); R(s_next) -> reward."""
    V = {s: 0.0 for s in states}
    while True:
        delta, new_V = 0.0, {}
        for s in states:
            if is_terminal(s):
                new_V[s] = 0.0
                continue
            new_V[s] = max(
                sum(p * (R(s2) + gamma * V[s2]) for p, s2 in P[s][a])
                for a in actions
            )
            delta = max(delta, abs(new_V[s] - V[s]))
        V = new_V
        if delta < theta:
            break
    policy = {
        s: max(actions, key=lambda a: sum(p * (R(s2) + gamma * V[s2]) for p, s2 in P[s][a]))
        for s in states if not is_terminal(s)
    }
    return V, policy

Practice problems

Problem 1: A three-cell corridor

A corridor has cells A, B and then a goal G (+1, terminal). Moves are deterministic, every move costs 0.04, γ = 0.9 and walls block the ends. Starting from V = 0, what are V(A) and V(B) after each sweep of value iteration?

Show solution

Sweep 1: V(B) = −0.04 + 1 + 0.9 × 0 = 0.96 (move right into G).

V(A): every action gives −0.04 + 0.9 × 0 = −0.04, so V(A) = −0.04.

Sweep 2: V(A) = −0.04 + 0.9 × V(B) = −0.04 + 0.864 = 0.824. V(B) stays 0.96.

Sweep 3: nothing changes, so max |ΔV| = 0 and the algorithm stops.

V(B) = 0.96 and V(A) = 0.824, reached after two sweeps

Problem 2: One backup with slipping

Slip probability is 0.2, γ = 0.9 and the step reward is −0.04. From state s, moving Right lands in a cell with V = 0.8. The two sideways outcomes are Up (a wall, so the agent stays in s, where V(s) = 0.5) and Down (a cell with V = 0.3). What is Q(s, Right)?

Show solution

Right succeeds with p = 0.8; each sideways slip has p = 0.1.

0.8 × (−0.04 + 0.9 × 0.8) = 0.8 × 0.68 = 0.544

0.1 × (−0.04 + 0.9 × 0.5) = 0.1 × 0.41 = 0.041

0.1 × (−0.04 + 0.9 × 0.3) = 0.1 × 0.23 = 0.023

Q(s, Right) = 0.544 + 0.041 + 0.023 = 0.608

Discussion

Questions, ideas or a different approach? Join the conversation.