Skip to content
LearnMLByDoing
Free

7.1 MDPs, Bellman equations and value iteration

34 minProintermediateS&BHOMLCompendium

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 s\tok{state}{s} is the square you are on, the action a\tok{action}{a} is the direction you choose, and the reward r\tok{reward}{r} 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:

s0, a0, r1, s1, a1, r2, s2, …st+1∼P(⋅∣st,at)\tok{state}{s_0},\ \tok{action}{a_0},\ \tok{reward}{r_1},\ \tok{state}{s_1},\ \tok{action}{a_1},\ \tok{reward}{r_2},\ \tok{state}{s_2},\ \dots\qquad s_{t+1}\sim \tok{transition}{P}(\cdot\mid s_t,a_t)
The agent sees s_t, picks a_t; the environment answers with r_{t+1} and s_{t+1}.
P and R (the model)[,,]5,184 values

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 V(s)\tok{value}{V}(s) 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 10−610^{-6}. 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 0.94≈0.660.9^4 \approx 0.66 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 (S,A,P,R,γ)(\mathcal{S}, \mathcal{A}, \tok{transition}{P}, R, \tok{gamma}{\gamma}): a set of states (36 squares, 23 playable), a set of actions (N, E, S, W), the transition model P(s′∣s,a)P(s'\mid s,a), a reward function, and a discount factor γ\gamma between 0 and 1.

Pr⁡(st+1=s′∣st,at,st−1,at−1,…,s0)=P(s′∣st,at)\Pr\big(s_{t+1}=s'\mid s_t,a_t,s_{t-1},a_{t-1},\dots,s_0\big)=\tok{transition}{P}(s'\mid s_t,a_t)
The Markov property: the next state depends on the current state and action only, not on the history.

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 γ\gamma per step:

Gt=rt+1+γ rt+2+γ2 rt+3+⋯=∑k=0∞γk rt+k+1G_t=\tok{reward}{r_{t+1}}+\tok{gamma}{\gamma}\,\tok{reward}{r_{t+2}}+\tok{gamma}{\gamma}^2\,\tok{reward}{r_{t+3}}+\dots=\sum_{k=0}^{\infty}\tok{gamma}{\gamma}^{k}\,\tok{reward}{r_{t+k+1}}
The discounted return. γ = 0 cares only about the next reward; γ near 1 weighs the far future almost fully.
Geometric series and the effective horizon1/4
  1. 1
    Sn=∑k=0n−1γk,γSn=∑k=1nγk  ⇒  Sn−γSn=1−γnS_n=\sum_{k=0}^{n-1}\gamma^k,\qquad \gamma S_n=\sum_{k=1}^{n}\gamma^k\;\Rightarrow\;S_n-\gamma S_n=1-\gamma^{n}

    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: G=−0.04 (1+0.9+0.81+0.729)+0.94⋅1=−0.138+0.656=0.519G = -0.04\,(1 + 0.9 + 0.81 + 0.729) + 0.9^4 \cdot 1 = -0.138 + 0.656 = 0.519. The 13-move route over the top pays −0.04 (1−0.912)/(1−0.9)+0.912=−0.287+0.282=−0.005-0.04\,(1-0.9^{12})/(1-0.9) + 0.9^{12} = -0.287 + 0.282 = -0.005. Discounting and the living cost both favour the short route; the dice are what make the comparison interesting.

Loading figure
Bars are the weight γt\gamma^t a reward tt steps ahead receives; the cyan line is their running total, which levels off at 1/(1−γ)1/(1-\gamma). The bottom row recomputes the two routes above (no slips) for the current γ\gamma. The slider is the cockpit's discount, so the viewport follows.

Set the discount to γ=0.5\gamma = 0.5, an effective horizon of 2 moves.

Now set γ=0.99\gamma = 0.99, 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 π(a∣s)\tok{policy}{\pi}(a\mid s) gives the probability of each action on each square; a deterministic policy picks one, π(s)\pi(s). 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 ss and follow π\pi, and the action value fixes the first move:

Vπ(s)=Eπ[Gt∣st=s],Qπ(s,a)=Eπ[Gt∣st=s, at=a]\tok{value}{V}^{\tok{policy}{\pi}}(\tok{state}{s})=\mathbb{E}_{\pi}\big[G_t\mid s_t=s\big],\qquad \tok{qvalue}{Q}^{\tok{policy}{\pi}}(\tok{state}{s},\tok{action}{a})=\mathbb{E}_{\pi}\big[G_t\mid s_t=s,\ a_t=a\big]

The return splits into the first reward and the rest, Gt=rt+1+γ Gt+1G_t = r_{t+1} + \gamma\,G_{t+1}. Averaging both sides over what π\pi and the dice can do gives the Bellman expectation equation:

Vπ(s)=∑aπ(a∣s)∑s′P(s′∣s,a)[r(s,a,s′)+γ Vπ(s′)]\tok{value}{V}^{\pi}(s)=\sum_{a}\tok{policy}{\pi}(a\mid s)\sum_{s'}\tok{transition}{P}(s'\mid s,a)\big[\tok{reward}{r}(s,a,s')+\tok{gamma}{\gamma}\,\tok{value}{V}^{\pi}(s')\big]
A square's value is the average, over the policy's choice and the dice, of one reward plus the discounted value of where you land.

One backup by hand, at (4,4) beside the goal, starting from V=0V = 0 everywhere. East: 0.9⋅(+1)+0.05⋅(−1)+0.05⋅(−1)=0.8000.9\cdot(+1) + 0.05\cdot(-1) + 0.05\cdot(-1) = 0.800 (the goal, or a slip into a pit on either side). North: 0.9⋅(−1)+0.05⋅(+1)+0.05⋅(−0.04)=−0.8520.9\cdot(-1) + 0.05\cdot(+1) + 0.05\cdot(-0.04) = -0.852 (the pit, or a slip onto the goal or back onto the bridge). South is the mirror image, −0.852-0.852. West: 0.9⋅(−0.04)+0.05⋅(−1)+0.05⋅(−1)=−0.1360.9\cdot(-0.04) + 0.05\cdot(-1) + 0.05\cdot(-1) = -0.136. The random policy averages them: (0.800−0.852−0.852−0.136)/4=−0.260(0.800 - 0.852 - 0.852 - 0.136)/4 = -0.260, exactly what the viewport's first sweep gives there.

For a fixed policy the equation is linear in the 36 unknowns Vπ(s)V^\pi(s). Write Pπ(s′∣s)=∑aπ(a∣s)P(s′∣s,a)P_\pi(s'\mid s)=\sum_a\pi(a\mid s)P(s'\mid s,a) and rπ(s)r_\pi(s) for the expected one-step reward:

Vπ=rπ+γ PπVπ⟺(I−γPπ) Vπ=rπ\tok{value}{V}^{\pi}=r_{\pi}+\tok{gamma}{\gamma}\,\tok{transition}{P}_{\pi}\tok{value}{V}^{\pi}\quad\Longleftrightarrow\quad (I-\gamma P_{\pi})\,V^{\pi}=r_{\pi}
One linear solve gives V^π exactly. I − γP_π is invertible for γ < 1.
P_π (one policy's transition matrix)[,]1,296 values

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 Vπ(S)=−0.780V^\pi(S) = -0.780. 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 Q(s,a)Q(s,a).

Jump to the end of the evaluation (sweep 90) and hold it.

The two value functions are tied together: Vπ(s)=∑aπ(a∣s) Qπ(s,a)V^\pi(s) = \sum_a \pi(a\mid s)\,Q^\pi(s,a) and Qπ(s,a)=∑s′P(s′∣s,a) [r+γVπ(s′)]Q^\pi(s,a) = \sum_{s'} P(s'\mid s,a)\,[r + \gamma V^\pi(s')]. Hover QQ 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.

Compiling scene

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