Value iteration
An agent that knows exactly how its world works can work out the best thing to do in every state before it moves: start with all values at zero and keep applying the Bellman equation until nothing changes.
Kind: deliberative agent (planning with a known model).
Week: 4 (slides 22 to 28).
Book: not in Wooldridge. Sutton and Barto 4.4, Russell and Norvig 17.2.1.
Techniques on this page: the sweep, value flowing back from the goal, extracting the policy, a gridworld backup by hand, what reshapes the policy.
The problem it solves
The Bellman optimality equation describes the best values, but it has a max in it, so you can’t just solve it like simultaneous equations.
Value iteration turns the equation into a repeated update. It needs the whole model, \(P\) and \(R\), which makes it planning: like STRIPS (week 2), but for a world with random outcomes and rewards, and producing an action for every state instead of a single plan.
Slide 28’s core point: acting well now depends on the value of states you may reach later.
Words you’ll hear
| Word or symbol | Plain meaning |
|---|---|
| sweep | one pass that updates every state’s value once |
| \(V_k\) | the values after \(k\) sweeps |
| Bellman backup | one application of the update to one state: pull value back from the next states |
| converged | another sweep changes nothing (or almost nothing) |
| policy extraction | reading off the best action in each state from the values |
| planning | using (estimated) future value to choose now |
Technique 1: the sweep
Problem it solves: computes \(V^*\) from the model.
- Start with \(V_0(s) = 0\) for every state (terminal states stay 0).
- For every non-terminal \(s\): \(V_{k+1}(s) = \max_a \sum_{s'} P(s' \mid s, a)[R(s, a, s') + \gamma V_k(s')]\), using the previous row on the right.
- Repeat until \(V_{k+1} = V_k\).
Worked example (slides 25 to 26). Corridor \(s_1 \leftrightarrow s_2 \to s_3\), certain moves, West from \(s_1\) stays, −0.1 per step, \(R(s_2, E, s_3) = 0.9\), \(\gamma = 0.9\).
| \(s_1\) | \(s_2\) | |
|---|---|---|
| \(V_0\) | 0 | 0 |
| \(V_1\) | −0.1 | 0.9 |
| \(V_2\) | 0.71 | 0.9 |
| \(V_3\) | 0.71 | 0.9 |
Sweep 2 at \(s_1\): East \(-0.1 + 0.9(0.9) = 0.71\); West \(-0.1 + 0.9(-0.1) = -0.19\); max 0.71. Sweep 3 changes nothing: converged.
Technique 2: value flows back from the goal
Problem it solves: explains why it takes several sweeps.
After sweep 1 only \(s_2\), next to the goal, has a good value. After sweep 2 the news has reached \(s_1\). Value moves back one step per sweep, so a start state \(n\) steps from the goal needs about \(n\) sweeps to feel it. This is the same “credit flowing backwards” that Q-learning does from experience.
Technique 3: extracting the policy
Problem it solves: turns values into actions.
\[\pi^*(s) = \arg\max_a \sum_{s'} P(s' \mid s, a)\,[R(s, a, s') + \gamma V^*(s')]\]
Worked example (slide 27). At convergence: \(Q^*(s_1, E) = 0.71\), \(Q^*(s_1, W) = -0.1 + 0.9(0.71) = 0.539\), \(Q^*(s_2, E) = 0.9\), \(Q^*(s_2, W) = 0.539\). So East in both states.
At \(s_1\) both actions cost −0.1 right now. Only the values of where they lead break the tie: that’s the whole point.
Technique 4: a gridworld backup by hand
Problem it solves: checks one arrow of slide 14’s policy.
Converged values for \(\gamma = 1\), living cost −0.04: \(V^*(s_{2,1}) = 0.695\), \(V^*(s_{3,2}) = 0.700\), \(V^*(s_{3,1}) = 0.651\), \(V^*(s_{4,1}) = 0.428\).
Worked example. At \(s_{3,1}\) (bottom row, below the cell next to the −1):
North: 0.8 to \(s_{3,2}\), 0.1 slip West to \(s_{2,1}\), 0.1 slip East to \(s_{4,1}\): \(0.8(0.660) + 0.1(0.655) + 0.1(0.388) = 0.632\).
West: 0.8 to \(s_{2,1}\), 0.1 slip North to \(s_{3,2}\), 0.1 slip South into the edge (stay): \(0.8(0.655) + 0.1(0.660) + 0.1(0.611) = 0.651\).
(Each bracket is \(-0.04 + V^*\) of the cell.) West wins, so the arrow points West, away from the goal. Small margin, so it flips easily.
Technique 5: what reshapes the policy
Problem it solves: shows that the reward and γ, not just the goal, decide behaviour.
Try it: living cost −0.01 makes the agent so careful it walks into walls rather than risk the −1; −0.4 takes the short risky route; −2 jumps straight into the −1 to stop paying; \(\gamma = 0.9\) flips the bottom row. A positive living reward means it never finishes: reward hacking in miniature.
Slide 7 vs slide 20. Slide 7 says \(\gamma \in [0, 1)\), but the gridworld policy on slide 14 is the one for \(\gamma = 1\). Fine: the gridworld is episodic. Also note rewards differ by problem: the gridworld’s +1 replaces the step cost; the corridor’s 0.9 is the step cost plus 1.
What to read
| Source | Read? | Why |
|---|---|---|
| Wooldridge | Not covered | value iteration isn’t in the book |
| Sutton and Barto 4.4 | Optional | value iteration, a page and a half |
| Russell and Norvig 17.1 to 17.2.1 | Optional | the gridworld and value iteration, with the living-cost experiment |
Practice prompt
I'm studying CS5940 Intelligent Agents, week 4 (MDPs and reinforcement learning). I want practice on VALUE ITERATION:
- running value iteration by hand on small deterministic corridors (sweeps from V0 = 0 using the previous row), until convergence
- how value propagates back one step per sweep
- extracting Q* and the optimal policy from the converged values
- one Bellman backup in the 4x3 gridworld with noisy moves (0.8 / 0.1 / 0.1) given the neighbouring values
- how gamma and the living cost change the optimal policy
- how value iteration compares with STRIPS planning, and why it needs P and R
Please:
1. Use plain, everyday language and explain any symbol in one short sentence.
2. Give me ONE question at a time, easy first, then harder, with friendly numbers.
3. Wait for my answer, then mark it and show the full working.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.