AI AI-03.05
Sequential decisions: MDPs (bridge to RL)
Markov decision processes, the Bellman equation and value iteration on a grid world, and how reinforcement learning solves MDPs without a model.
The big idea
The umbrella decision was a single choice. Most agents face a sequence of choices, where each action changes the situation for the next one and outcomes are uncertain: a robot that sometimes slips, a game where the opponent's reply is unknown, an inventory system that orders stock while demand fluctuates. A good action now is one that leads to situations where good actions are available later.
A Markov decision processA model of sequential decision making: states, actions, transition probabilities P(s' | s, a), rewards, and a discount factor. Solving it means finding a policy that maximizes expected total reward. (MDP) is the standard model for this. Instead of a plan, a fixed list of moves as in Classical planning , the answer is a policyA rule that says which action to take in every state. In an MDP, an optimal policy maximizes expected total (discounted) reward from every state.: a rule saying what to do in every state, so the agent knows how to act wherever its slips and surprises take it.
Think of a hiking map where every junction is labelled with how far it is to the hut, counting the risk of each trail. With those labels you never need to plan the whole route: at each junction, take the trail that leads to the best-labelled next junction. Value iteration is the procedure that writes those labels.
How it works
Step 1: The ingredients
An MDP has:
- States : where the agent can be. In a grid world, the cells.
- Actions : what it can try. Up, down, left, right.
- Transitions : where an action actually leads. A move succeeds 80 percent of the time and slips to either side 10 percent of the time each.
- Rewards : what each step earns. Exits pay +1 or -1, and every other step costs a little, such as -0.04.
- A discount between 0 and 1: how much a reward one step later is worth compared with one now.
"Markov" means the transition depends only on the current state and action, not on the history, the same assumption as in hidden Markov models ( Hidden Markov models ).
Step 2: Values and the Bellman equation
The valueThe expected total discounted reward an agent collects starting from a state and acting optimally afterwards. of a state, , is the expected total reward from that state onward when acting optimally. It satisfies the Bellman equationThe recursive equation linking a state's value to the values of the states its actions lead to: V(s) = max over actions of the expected reward plus discounted value of the next state.:
In words: a state is worth what its best action is expected to earn now, plus the discounted worth of wherever that action lands. It is expected utility ( Decision theory and utility ) applied recursively, one step at a time.
Step 3: Value iteration
The equation defines in terms of itself, so solve it by repetition. Value iteration starts with every value at 0 and applies the Bellman update to every state in a sweep, again and again. Values spread outward from the rewards like ripples, and they converge to the true values. The policy then falls out: in each state, take the action with the best expected value.
Try it
Try this:
- Press Sweep a few times. After the first sweep only the cells next to the exits know anything; each sweep carries information one cell further. Then Run to convergence: the start cell (bottom left) is worth 0.705, and the arrows lead around the top, away from the -1.
- Look at the bottom row. The three cells on the right all point left, the long way round the wall, although the route up the right-hand side is shorter. That route passes next to the -1 exit, where every move has a 10 percent chance of slipping sideways into it. With a small cost per step, the safe detour is worth more.
- Set the reward per step to -1 and run again. Life is now so costly that the cell below -1 jumps straight into it: a certain -1 beats a long, expensive walk. Set it to 0: the agent takes the long safe way round and even walks into walls on purpose rather than risk slipping into -1.
The same calculation, in code, for two step rewards:
# Value iteration on the 4 x 3 grid world. (x, y) with y = 0 at the top.
W, H, WALL = 4, 3, (1, 1)
EXITS = {(3, 0): 1.0, (3, 1): -1.0}
MOVES = {"^": (0, -1), ">": (1, 0), "v": (0, 1), "<": (-1, 0)}
SIDES = {"^": "<>", "v": "<>", "<": "^v", ">": "^v"} # slip directions
CELLS = [(x, y) for y in range(H) for x in range(W) if (x, y) != WALL]
def step(c, m):
x, y = c[0] + MOVES[m][0], c[1] + MOVES[m][1]
inside = 0 <= x < W and 0 <= y < H and (x, y) != WALL
return (x, y) if inside else c # bump into a wall: stay
def q(V, c, m, reward, gamma, slip=0.2):
"""Expected reward + discounted value of trying move m from c."""
outcomes = [(step(c, m), 1 - slip)] + \
[(step(c, s), slip / 2) for s in SIDES[m]]
return sum(p * (reward + gamma * V[n]) for n, p in outcomes)
def value_iteration(reward, gamma=1.0, eps=1e-6):
V = {c: EXITS.get(c, 0.0) for c in CELLS}
for sweep in range(1, 1000):
new = {c: EXITS[c] if c in EXITS else
max(q(V, c, m, reward, gamma) for m in MOVES)
for c in CELLS}
change = max(abs(new[c] - V[c]) for c in CELLS)
V = new
if change < eps:
return V, sweep
def show(V, reward):
for y in range(H):
row = []
for x in range(W):
c = (x, y)
if c == WALL:
row.append(" #### ")
elif c in EXITS:
row.append(f" {EXITS[c]:+.0f} ")
else:
m = max(MOVES, key=lambda m: q(V, c, m, reward, 1.0))
row.append(f"{m} {V[c]:+7.3f}")
print(" " + " | ".join(row))
for reward in (-0.04, -2.0):
V, sweeps = value_iteration(reward)
print(f"reward per step {reward}: converged after {sweeps} sweeps")
show(V, reward)Output
reward per step -0.04: converged after 28 sweeps
> +0.812 | > +0.868 | > +0.918 | +1
^ +0.762 | #### | ^ +0.660 | -1
^ +0.705 | < +0.655 | < +0.611 | < +0.388
reward per step -2.0: converged after 23 sweeps
> -7.043 | > -4.230 | > -1.730 | +1
^ -9.543 | #### | > -3.570 | -1
> -10.815 | > -8.474 | > -5.974 | ^ -3.775 Going deeper
Discounting
With a reward steps away is worth of a reward now: at , a reward 10 steps away counts for about 35 percent. Discounting expresses impatience or uncertainty about the future, and it guarantees that values stay finite even when the agent could go on forever, which is why value iteration converges for any . With it converges only when, as in this grid, the agent is guaranteed to reach an exit eventually under a good policy.
Policy iteration
Instead of refining values until they settle, policy iteration alternates two steps: evaluate the current policy exactly, then improve it by acting greedily on those values. It usually needs very few rounds, because the policy often stops changing long before the values have converged. Both methods need the full model, every , and sweep over every state, which limits them to problems with manageable state spaces.
From planning to learning
What if the agent does not know the transition probabilities or rewards? It must learn from experience: try actions, observe what happens, and update its estimates. That is reinforcement learningLearning to act by trial and error: an agent interacts with an environment, receives rewards, and improves its policy without being given the MDP's model.. Q-learning, for example, applies a sampled version of the Bellman update after every step it takes, and with enough exploration it converges to the same optimal policy value iteration would compute from the model. Deep reinforcement learning replaces the value table with a neural network so it can handle states such as screen images, and it is how systems learned to play video games from pixels and, combined with the tree search of Monte Carlo Tree Search and AlphaGo , to play Go. The ML track picks this up in RL fundamentals and MDPs .
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Value iteration | Known model, small or medium state spaces; simple to implement | Sweeps every state; needs the full transition model |
| Policy iteration | Known model, when the policy settles quickly | Each evaluation step is expensive on large problems |
| Reinforcement learning | Unknown or huge environments that can be simulated or experienced | Needs many interactions; exploration can be costly or unsafe |
| Classical planning (fixed plan) | Deterministic actions and known outcomes | Breaks when actions can fail or surprise |
Common mistakes
- Returning a plan where a policy is needed. With uncertain outcomes the agent must know what to do in states it did not expect to reach.
- Setting rewards that create unintended behaviour. A small positive reward for every step can make an agent avoid finishing at all; agents optimise exactly what they are paid for.
- Using in a problem where the agent can loop forever. Values can grow without bound.
- Confusing reward (what one step pays) with value (what a state is worth in the long run).
In the wild
Where you will see this: MDPs model inventory and supply-chain decisions, maintenance scheduling, robot navigation under uncertainty, dialogue managers that decide what to ask next, and the allocation of resources in data centres. Reinforcement learning built on the same equations trains game-playing agents, controls robots in simulation, and is one stage in fine-tuning language models from human feedback.
Check yourself
-
Why is the answer to an MDP a policy rather than a fixed plan?
Show answer
B. Outcomes are uncertain, so the agent needs an action for every state it might end up in When moves can slip, the agent may land anywhere; a policy covers every state.
-
What does the Bellman equation say?
Show answer
B. A state's value is the best action's expected immediate reward plus discounted value of the next state Value is defined recursively from the values of the states that actions lead to.
-
With a discount of 0.9, how much is a reward 2 steps away worth now?
Show answer
B. 0.81 Each step multiplies by 0.9: 0.9 x 0.9 = 0.81.
-
In the grid world, the reward per step goes from -0.04 to -1. Why does an agent next to the -1 exit now jump in?
Show answer
B. Walking is so costly that a certain -1 beats the expected cost of the long way round The policy optimises total reward: when every step costs 1, ending immediately at -1 is the best available option.
-
What does reinforcement learning add to value iteration?
Show answer
B. The ability to find good policies without knowing the transition model, by learning from experience RL estimates values or policies from interaction, sampling the Bellman update instead of computing it from a known model.
Recap
- An MDP has states, actions, uncertain transitions, rewards and a discount; its answer is a policy.
- The Bellman equation defines each state's value from the values of the states its best action leads to.
- Value iteration repeats Bellman updates until values converge; the greedy policy follows from them.
- Rewards and discounts shape behaviour, sometimes in surprising ways.
- Reinforcement learning solves MDPs from experience when the model is unknown.