MDPs and the Bellman Equation

Search assumed your actions do what you intend. Drop that assumption - let an action succeed most of the time and slip occasionally - and a fixed sequence of moves stops being a useful answer. What you need instead is a rule that tells you what to do from wherever you actually end up.

The five parts

A Markov decision process is a sequential decision problem with a fully observable, stochastic environment. It is specified by:

Two of these carry more weight than they first appear to.

The transition model is where uncertainty lives. $P(s' \mid s, a)$ is a distribution, not an outcome. Attempting to move right might take you right with probability $0.8$ and leave you where you are with probability $0.2$. The agent does not choose $s'$; it chooses only $a$.

The Markov property is the assumption that makes this tractable. The next state depends on the current state and action alone - not on how you arrived. That is a real restriction, and it is what lets you attach one number to each state instead of to each possible history.

Reward on the state. This course follows Russell & Norvig, where the reward attaches to the state you are in, written $R(s)$. Much of the literature attaches it to the transition instead, $R(s,a,s')$. The theory is the same either way, but the equations look different, so expect the discrepancy when comparing sources.

Why the answer is a policy

Because outcomes are stochastic, a plan like "right, right, up" is worthless: the first slip puts you somewhere the rest of the sequence no longer addresses.

The answer is a policy $\pi(s)$ - an action recommended for every state. It never runs out of applicability, because whatever happens, you are in some state and the policy has an answer for it. An optimal policy $\pi^*$ is one that maximises expected utility.

What the best policy depends on. The figure below is Russell & Norvig's 4x3 world: four squares by three with one blocked by a wall, and two exits worth $+1$ and $-1$. Its transition model is a little richer than the one above: each move goes as intended with probability $0.8$ and to either side with $0.1$, and there is no discounting. The one thing you move is the living reward R, the $R(s)$ every non-terminal square pays, and the optimal policy is a step function of it: at eight thresholds, one square's arrow turns over. The button the textbook -0.04 brings it back to the value Russell & Norvig use.

The Bellman equation

Suppose you already knew $U(s)$, the utility of every state. Then the value of being in $s$ decomposes into what you collect now and what you can expect afterwards:

$$U(s) = R(s) + \gamma \max_{a \in A(s)} \sum_{s'} P(s' \mid s,a)\, U(s')$$

Read it slowly, because every piece is doing work:

• $R(s)$ - collected for being in $s$, regardless of what you do next.
• $\max_a$ - you choose the action, so you take the best one available.
• $\sum_{s'} P(s' \mid s,a) U(s')$ - you do not choose the outcome, so the future is an average weighted by the transition model.
• $\gamma$ - discounts that future relative to the present.

The order matters: maximise over what you control, average over what you do not.

This is a condition, not a recipe. It says nothing about how to find $U$; it says only that the true $U$ must satisfy it at every state simultaneously. With $n$ states you get $n$ equations in $n$ unknowns - but they are nonlinear, because $\max$ is not a linear operator, so you cannot simply solve them with linear algebra. Getting from this condition to actual numbers is the next lesson.

The order of operations is the part a formula cannot show, so the figure below takes it apart. Each action gets its own line with its own average over the outcomes it does not control, and the maximum is taken visibly between the lines rather than inside a symbol. Drag the discount to watch the future term grow from nothing: at zero the agent sees only the living cost, and near one it is dominated by a reward several steps away.

Why discounting

With $\gamma < 1$, a reward $k$ steps away is worth $\gamma^k$ times its face value. Two reasons this matters:

1. It bounds the total. An infinite run of bounded rewards would otherwise sum to infinity, and infinities cannot be compared.
2. It expresses genuine preference. Sooner is usually better.

At $\gamma = 0$ the agent is myopic, caring only about $R(s)$. As $\gamma \to 1$ it becomes far-sighted, willing to accept a long unrewarding stretch for a large payoff at the end.

Try it live. Watch occupancy probabilities evolve from the transition rates alone, with no policy involved yet. This one is a continuous-time chain with an absorbing failure state, so it never settles: over the printed horizon the mass drains steadily into failed.

Before the quiz

Be able to list the five parts, state what the Markov property forbids, explain why a policy beats a plan under uncertainty, and point at which term in the Bellman equation is a maximisation and which is an expectation - and why they are not interchangeable. The companion article Markov Decision Processes derives the same material at more length.