7.1 MDPs, Bellman equations and value iteration
A Markov decision process turns a sequential decision into a board game with dice, and value iteration solves it by repeating one equation until every square knows how good it is.
01A board game with dice: agents, states, actions, rewards
Picture a board game. Your token starts on the square marked S, at the left end of row 4 of a 6 × 6 board, and the goal sits at the right end of the same row, worth +1. The four squares between them are a bridge with a row of pits above and a row below; falling into a pit ends the game at −1. A wall blocks row 1 except at its two ends, so the safe way round goes up the left edge, along the top and down the right edge: 13 moves instead of 5. Every move costs 0.04 points.
Then the dice. Each turn you choose a direction. With probability 0.9 you move that way; with probability 0.05 each you slip to one of the two sideways directions. Bumping into a wall or the edge leaves you where you are. So every step along the bridge carries a 10% chance of falling in, half to each side.
That is a complete reinforcement-learning problem. The agent is the player, the environment is the board plus the dice, the state is the square you are on, the action is the direction you choose, and the reward arrives with the square you land on: +1 for the goal, −1 for a pit, and the living reward of −0.04 for any other square. The game is an episode that ends at the goal or in a pit. Play produces a stream:
Stored densely over all 36 squares: 23 are playable, while the 4 walls, 8 pits and the goal have empty rows (nothing happens after the game ends). Each playable row has at most 3 non-zero entries, and R[s, a, s′] is the reward for landing on s′. The Python challenge uses exactly these arrays.
The viewport is solving this game. Each column's height and colour is the value of standing on that square, how many points you can expect from there if you play well (step 3 defines it exactly), and each amber arrow is the best move found so far. The algorithm, value iteration, works in sweeps: each sweep updates every square once from its neighbours' previous values. Value appears beside the goal first and spreads backwards while arrows appear and flip; after 23 sweeps nothing changes by more than . The emerald line is the route the arrows describe from S: straight across the bridge. Then the token plays a few episodes with real dice; about two games in three reach the goal, because of tokens survive the four bridge squares.
Restart value iteration and hold it after the first sweep.
Reinforcement Learning: An Introduction, Sutton & Barto, Ch. 3.1, The agent–environment interface
Hands-On Machine Learning, Aurélien Géron, Ch. 18, Reinforcement Learning
02MDPs, the Markov property and discounted returns
Formally the game is a Markov decision process (MDP), a tuple : a set of states (36 squares, 23 playable), a set of actions (N, E, S, W), the transition model , a reward function, and a discount factor between 0 and 1.
On the board, how you reached a square does not change where the dice can send you next, so the square alone is a complete state. When history does matter (a key picked up earlier, the last few frames of a video game), the fix is to put it into the state: square plus has-key doubles the number of states, and stacking recent frames turns a moving ball into a state with a velocity.
The agent wants a large return, the total reward from now on, with rewards further in the future discounted by per step:
- 1
Multiply by γ and subtract: every term cancels except the first and the last.
A worked example with no slips. The bridge route pays −0.04 on four moves and +1 on the fifth: . The 13-move route over the top pays . Discounting and the living cost both favour the short route; the dice are what make the comparison interesting.
Set the discount to , an effective horizon of 2 moves.
Now set , a horizon of 100 moves.
Reinforcement Learning: An Introduction, Sutton & Barto, Ch. 3.2 to 3.4, Goals, returns and episodes
Maths, CS & AI Compendium, Henry Ndubuaku, Reinforcement learning: Markov decision processes
03Policies, value functions and the Bellman expectation equation
A policy gives the probability of each action on each square; a deterministic policy picks one, . The viewport is now evaluating the uniform random policy, which picks each of the four moves with probability 1/4. Its state value is the expected return when you start on and follow , and the action value fixes the first move:
The return splits into the first reward and the rest, . Averaging both sides over what and the dice can do gives the Bellman expectation equation:
One backup by hand, at (4,4) beside the goal, starting from everywhere. East: (the goal, or a slip into a pit on either side). North: (the pit, or a slip onto the goal or back onto the bridge). South is the mirror image, . West: . The random policy averages them: , exactly what the viewport's first sweep gives there.
For a fixed policy the equation is linear in the 36 unknowns . Write and for the expected one-step reward:
Each playable row sums to 1, and terminal rows are zero. The viewport does not solve the system: it repeats the backup on every square (iterative policy evaluation), which reaches the same V^π and needs 90 sweeps to change by less than 10⁻⁶.
Random wandering is a bad policy here: from S it reaches the goal only about 0.7% of the time and ends in a pit otherwise, so the columns sink below the board and . The amber arrows are not the random policy, which has no single arrow per square. They are the greedy policy with respect to the current values: on each square, the move with the best one-step look-ahead .
Jump to the end of the evaluation (sweep 90) and hold it.
The two value functions are tied together: and . Hover to see the four action values on the selected square.
Reinforcement Learning: An Introduction, Sutton & Barto, Ch. 3.5 and 4.1, Value functions and policy evaluation
The rest of this lesson is in Pro
- 04The Bellman optimality equation and value iteration
- 05Policy iteration, convergence and the greedy policy
- 06Where this sits: model-based, model-free and RL in practice
- Python challenge: Bellman backups, value iteration and exact policy evaluation
- Knowledge check, 4 questions
Pro opens all 45 lessons, every graded Python challenge and the full 3D labs.
The Python challenge and knowledge check for this lesson are part of Pro.
Questions learners ask
- What is the Bellman equation in simple terms?
- It says that the value of a situation equals the reward you get on the next step plus the discounted value of where you end up, averaged over what can happen. For a fixed policy this gives a linear system you can solve directly. For the best possible behaviour you take the best action instead of averaging over the policy, which gives the Bellman optimality equation that value iteration solves.
- What is the difference between value iteration and policy iteration?
- Value iteration repeats one cheap update, the best one-step look-ahead on every state, until the values stop changing, and reads the policy off at the end. Policy iteration alternates an exact evaluation of the current policy, a linear solve, with a greedy improvement, and stops when the policy no longer changes. Policy iteration needs far fewer iterations but each one is more expensive. On this lesson's board value iteration takes 23 sweeps and policy iteration 9 improvements from an all-North start.
- What does the discount factor gamma do in reinforcement learning?
- Gamma between 0 and 1 multiplies a reward by gamma to the power t when it arrives t steps in the future. It keeps returns finite and sets an effective horizon of about 1 over 1 minus gamma steps: 10 steps at 0.9, 100 at 0.99. A low gamma makes the agent short-sighted and a high gamma lets it accept long detours for safer or larger rewards. It is part of the problem definition, so changing it can change the optimal policy.
Next in Reinforcement Learning
7.2Q-learning, SARSA and explorationLearn action values from experience alone, balance exploration against exploitation, and see why off-policy learning walks the cliff edge.Sources
- Reinforcement Learning: An Introduction, Sutton & Barto
- Hands-On Machine Learning, Aurélien Géron
- Maths, CS & AI Compendium, Henry Ndubuaku