Introduction
Search assumed every action has a known result. Real actions often do not: a robot's wheel slips, a delivery is late, a patient responds to treatment only sometimes. An agent then cannot commit to a fixed sequence of actions. It needs a policy: an action for every state it might end up in. Markov decision processes (MDPs) are the standard model for this, and they are also the foundation of reinforcement learning, the subject of the next lesson.
How it works
An MDP has:
- states, such as the cells of a grid;
- actions, such as up, right, down and left;
- a transition model P(s′ | s, a): in the example, a move goes the intended way with probability 0.8 and slips to each side with probability 0.1; hitting a wall means staying put;
- rewards: a small living reward (here −0.04) for each step, and terminal states worth +1 (G) or −1 (P);
- a discount factor γ, so that a reward k steps away counts γᵏ as much.
The value of a state is the expected total discounted reward an optimal agent collects from there. It satisfies the Bellman equation:
V(s) = R(s) + γ · maxₐ Σₛ′ P(s′ | s, a) V(s′)
The sum is the expected value of the next state if the agent takes action a; the max picks the best action.
Value iteration solves it: start with V = 0 for every non-terminal state, then replace every value by the right-hand side, using the old values, and repeat. Each pass is one more step of look-ahead. With γ < 1 the values converge; stop when the largest change is tiny.
The optimal policy then chooses, in every state, the action that achieves the max. The living reward changes it: a large negative living reward makes the agent rush, even past danger; a small one lets it take the long, safe way round.
Syntax
def q_value(V, s, a):
return R + GAMMA * sum(p * V[s2] for p, s2 in outcomes(s, a))
while True:
new = {s: max(q_value(V, s, a) for a in actions) for s in non_terminal}
if max(abs(new[s] - V[s]) for s in new) < 1e-6: break
V.update(new)
policy = {s: max(actions, key=lambda a: q_value(V, s, a)) for s in non_terminal}
Example
GRID = ["....G", ".##.P", "....."]
LIVING, GAMMA = -0.04, 0.95
ROWS, COLS = len(GRID), len(GRID[0])
MOVES = {"^": (-1, 0), ">": (0, 1), "v": (1, 0), "<": (0, -1)}
SIDES = {"^": "><", "v": "><", ">": "^v", "<": "^v"}
TERMINAL = {"G": 1.0, "P": -1.0}
def step(cell, d):
r, c = cell[0] + MOVES[d][0], cell[1] + MOVES[d][1]
if 0 <= r < ROWS and 0 <= c < COLS and GRID[r][c] != "#":
return (r, c)
return cell
def q_value(V, cell, d):
a, b = SIDES[d]
return LIVING + GAMMA * (0.8 * V[step(cell, d)] + 0.1 * V[step(cell, a)] + 0.1 * V[step(cell, b)])
V = {}
for r in range(ROWS):
for c in range(COLS):
if GRID[r][c] != "#":
V[(r, c)] = TERMINAL.get(GRID[r][c], 0.0)
iterations = 0
while True:
iterations += 1
new = dict(V)
for cell in V:
if GRID[cell[0]][cell[1]] == ".":
new[cell] = max(q_value(V, cell, d) for d in MOVES)
change = max(abs(new[cell] - V[cell]) for cell in V)
V = new
if change < 1e-6:
break
print("converged after", iterations, "iterations")
for r in range(ROWS):
print(" ".join(f"{V[(r, c)]:5.2f}" if GRID[r][c] == "." else f"{GRID[r][c]:>5}" for c in range(COLS)))
for r in range(ROWS):
row = []
for c in range(COLS):
if GRID[r][c] == ".":
row.append(max(MOVES, key=lambda d: q_value(V, (r, c), d)))
else:
row.append(GRID[r][c])
print(" ".join(row))Line by line
- The grid has a goal G (+1), a pit P (−1) and two walls. Each step costs 0.04 and future rewards are discounted by 0.95.
stepfinds where a move ends, staying put at walls and edges;q_valueweighs the intended move and the two slips.- Value iteration repeats the Bellman update until no value changes by more than one millionth.
- Values are highest next to the goal and fall off with distance; the cells near the pit are lower.
- The arrows lead to the goal. Beside the pit, the best move still accepts a 10% chance of slipping in: the safe alternative, bumping into the wall, wastes too many steps.
Expected result
converged after 26 iterations
0.56 0.66 0.75 0.86 G
0.47 # # 0.57 P
0.39 0.31 0.37 0.45 0.23
> > > > G
^ # # ^ P
^ < > ^ <
In the real world
MDPs plan inventory restocking, decide when to replace machines, route data packets, schedule elevators and manage power in phones. Robots plan in MDPs whose states describe position and speed. Medical treatment policies, such as when to change a drug dose, are studied as MDPs over patient states.
Common mistakes
- Treating the most likely outcome as certain and planning a fixed path.
- Updating values in place during a pass while describing it as synchronous value iteration; both converge, but the numbers per iteration differ.
- Setting γ = 1 with no terminal states, so values never settle.
- Forgetting that walls make the agent stay, which is also an outcome with probability.
Best practices
- Check that the outcome probabilities of every action add up to 1.
- Stop iterating on a small largest change, and print the number of iterations.
- Try several living rewards to see how the policy changes; it is a good test of the model.
Summary
An MDP models decisions with uncertain outcomes through states, actions, transition probabilities, rewards and a discount. The Bellman equation links each state's value to the best expected value of its successors. Value iteration applies it repeatedly until the values converge, and the optimal policy takes the action that achieves the max in each state.
Quick check
Key takeaways
- With uncertain outcomes, a plan is a policy, not a fixed sequence of actions.
- Value iteration converges to the optimal values; the best action in each state is the one that achieves the max.
- The living reward and the discount shape the policy: cautious or bold, quick or careful.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.