Value iteration: watch values propagate
In an MDP you're handed the rules — states, actions, transition probabilities T, rewards R — and value iteration solves them. Vk(s) is the best expected (discounted) reward you can collect starting from s within k steps. Start from V₀ ≡ 0 and sweep the Bellman update until nothing changes: value leaks outward from the reward squares one ring per sweep, damped by γ each ring. Two worlds below — the lecture's hand-checkable corridor, then a full stochastic gridworld — with the conventions the lecture left undeclared spelled out.
Vk+1(s) = maxa Σs′ T(s,a,s′) · [ R(s,a,s′) + γ·Vk(s′) ]Stage 1 — the lecture's 5-cell corridor
One action (→), deterministic moves, γ adjustable (lecture uses ½). The only reward is R(5) = 1, paid when leaving cell 5; it's collected once on a final self-loop step, then V(5) freezes. Every number here is hand-checkable.
| k | V(1) | V(2) | V(3) | V(4) | V(5) |
|---|
Trap №1 — when is a reward paid?
This corridor page is the one place the course declares its rule: “we get the reward when we are leaving from the current state.” That single sentence is the whole game — every reward rides inside the packet of the action that causes it, discounted at that action's time slot. The gridworld page one tab earlier never states its rule, and it cost real graded attempts. Before computing anything with γ < 1, find the page's billing sentence — and if it's missing, derive it from a worked iterate before trusting your hand computation.
Trap №2 — “step” means three things
In this unit “step” is used for an agent move, a time index, and an algorithm iteration. The k above counts iterations: full sweeps in which every cell is updated once from the previous row of the table. In this corridor the numbers coincide — the ripple travels one cell per sweep — which is exactly how a graded question got failed. The 10×10 below breaks the coincidence: it converges in ~47 sweeps at γ = 0.75, a number that has nothing to do with the length of any journey.
What to notice
Vk answers “best I can do in k steps.” With all rewards ≥ 0 the iterates only grow, approaching V* from below; each new sweep activates exactly one more cell, at γ times its neighbor's value. That's the propagation picture — and it's the entire algorithm.
Convergence — the contraction, visible
δk = maxs |Vk(s) − Vk−1(s)| per sweep, log scale. It hugs a straight line of slope γk (dashed) — the lecture's single-state contraction argument, εk = γkε₀, holding on the real world. This is also why the strict γ < 1 matters: at γ = 1 the slope is flat and the line never reaches the stopping threshold θ.
Controls
Click any cell to inspect its four Q-values. Changing γ restarts from V₀. Watch the arrows: the policy usually locks in long before the values stop moving.
Q inspector — how V and π come from Q
This world's rules — declared up front
World: Poole & Mackworth, Artificial Intelligence 2e, Example 12.30. Your action succeeds with p = 0.7; each of the other three directions happens with p = 0.1. Walking into a wall: you stay put and −1 is billed to that action. Acting while on a reward square pays R(s) — that's this world's billing rule, stated so you don't have to reverse-engineer it. Acting on +10 or +3 collects the prize and teleports you to a random corner (¼ each) — which is why those squares' values stay near their prize instead of compounding forever.