Markov Decision Processes

Adversarial Search and Minimax planned against an opponent, but assumed the world itself was reliable: play a move and the board changes exactly as expected. Real environments are not so obliging. A robot commanded to move forward may drift; a recommendation may or may not be acted on. Actions have probability distributions over outcomes, not single outcomes.

A Markov decision process is the standard formalism for this situation, and it is the foundation the whole of reinforcement learning is built on.

A. The ingredients

An MDP is specified by four things:

• a set of states $s$;
• a set of actions $A(s)$ available in each state;
• a transition model $P(s' \mid s, a)$, the probability of landing in $s'$ when action $a$ is taken in $s$;
• a reward function $R(s)$.

The name comes from the Markov property: the probability of the next state depends only on the current state and action, not on the history of how the agent got there. That is what makes the problem tractable - the current state is a sufficient summary of the past.

A note on where the reward sits. Following Russell & Norvig, the reward $R(s)$ here is attached to the state the agent is in, and appears outside both the maximisation and the expectation. Much of the reinforcement-learning literature instead writes $R(s, a, s')$, a reward on the transition, which moves it inside the sum. The two formulations are equivalent for our purposes, but the equations look different, so it is worth knowing which convention you are reading.

A policy $\pi$ is a function recommending an action for every state - not a plan for one contingency, but a complete rule of behaviour. Solving an MDP means finding a good policy.

B. Why we discount

The utility of executing a policy $\pi$ from state $s$ is the expected sum of rewards along the way:

$$U^{\pi}(s) = E\left[\sum_{t=0}^{\infty} \gamma^{t} R(S_t)\right],$$

where $S_t$ is the state reached at time $t$ and $\gamma \in [0, 1]$ is the discount factor. Discounting is not a technicality bolted on for convenience. If the agent may never reach a terminal state, histories are infinitely long and undiscounted sums generally diverge - and comparing two policies that both score $+\infty$ is not a well-posed question.

With $\gamma < 1$ and rewards bounded by $R_{\max}$, the geometric series settles it:

$$U([s_0, s_1, s_2, \dots]) = \sum_{t=0}^{\infty} \gamma^{t} R(s_t) \;\le\; \sum_{t=0}^{\infty} \gamma^{t} R_{\max} = \frac{R_{\max}}{1 - \gamma}.$$

Every utility is finite, so every pair of policies is comparable. $\gamma$ near $0$ makes the agent myopic; $\gamma = 1$ recovers plain additive rewards, which is safe only when the agent is guaranteed to reach a terminal state - a policy with that guarantee is called proper.

An optimal policy is then $\pi^{*} = \arg\max_{\pi} U^{\pi}(s)$. A pleasant consequence of discounted infinite-horizon rewards is that $\pi^{*}$ does not depend on the starting state, so we can speak of the optimal policy and write $U(s)$ for the utility under it.

$U(s)$ and $R(s)$ are different quantities. $R(s)$ is the short-term reward for being in $s$; $U(s)$ is the long-term total from $s$ onward. Conflating them is the single most common source of confusion in this material.

C. The Bellman equation

Here is the central idea. The utility of a state is its immediate reward plus the discounted expected utility of wherever the best action takes you:

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

That is the Bellman equation, after Richard Bellman (1957). Read it slowly: the $\max$ chooses the best action, the $\sum$ averages over where that action might actually land you, and $\gamma$ discounts the future relative to the present.

If there are $n$ states there are $n$ such equations in $n$ unknowns. They are not linear, because $\max$ is not a linear operator - so we cannot simply invert a matrix and be done.

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.

D. Value iteration, worked to convergence

The fix is to iterate. Start with arbitrary utilities, evaluate the right-hand side, and use the result as the new left-hand side. Repeat.

Take a four-state world. Two non-terminal states, $s_1$ and $s_2$, each with $R(s) = -0.04$ - a small penalty per step, which encourages finishing. Two terminals: GOAL with utility $+1$ and PIT with $-1$. Set $\gamma = 0.9$.

Initialise $U(s_1) = U(s_2) = 0$.

Sweep 1. For $s_2$, Right gives $0.8(1) + 0.2(-1) = 0.6$, while Left gives $0.8(0) + 0.2(0) = 0$. So

$$U(s_2) = -0.04 + 0.9 \times 0.6 = -0.04 + 0.54 = 0.50 .$$

For $s_1$, both actions still see zeros, so $U(s_1) = -0.04 + 0.9 \times 0 = -0.04$.

Sweep 2. Now $s_1$ can see the value that has appeared in $s_2$. Right gives $0.8(0.50) + 0.2(-0.04) = 0.400 - 0.008 = 0.392$, beating Stay's $-0.04$:

$$U(s_1) = -0.04 + 0.9 \times 0.392 = -0.04 + 0.3528 = 0.3128 .$$

$U(s_2)$ does not move, because both its outcomes are terminal.

Continuing:

The values stop moving at $U(s_1) = 0.3902$, $U(s_2) = 0.5000$.

We can confirm that fixed point exactly rather than trusting the iteration. Once Right is known to be the better action at $s_1$, the Bellman equation there reads

$$U(s_1) = -0.04 + 0.9\big(0.8 \times 0.5 + 0.2\,U(s_1)\big) = 0.32 + 0.18\,U(s_1),$$

so $U(s_1) = 0.32 / 0.82 = 0.390243\ldots$, matching the table to four decimals.

Reading the policy off the converged utilities gives Right in both states, with expected successor utilities $\sum_{s'} P(s' \mid s, a)\,U(s')$ of $0.478$ versus $0.390$ at $s_1$, and $0.600$ versus $0.412$ at $s_2$. Adding $R(s)$ and discounting turns those into the action values $Q(s, a)$ of the next article: $0.3902$ versus $0.3112$ at $s_1$, and $0.5000$ versus $0.3310$ at $s_2$, the same ranking.

Running it reproduces the table above and prints Right for both states.

E. Policy iteration

Value iteration computes utilities to high precision and reads the policy off at the end. But the policy often stops changing long before the numbers settle - in our world, Right was optimal at $s_1$ from sweep 2, while the fourth decimal place kept moving for several sweeps more. Policy iteration exploits that by alternating:

1. Policy evaluation - given a fixed policy $\pi_i$, compute the utilities it produces.
2. Policy improvement - recompute the best action in each state using those utilities, giving $\pi_{i+1}$.

Repeat until the policy stops changing. The payoff is in step 1: with the action in each state fixed by the policy, there is no $\max$ left, and the Bellman equation becomes

$$U_i(s) = R(s) + \gamma \sum_{s'} P(s' \mid s, \pi_i(s))\, U_i(s') .$$

These are linear - $n$ equations, $n$ unknowns, solvable exactly by standard linear algebra in $O(n^3)$. For small state spaces exact policy evaluation is often the fastest approach; for large ones the cubic cost bites, and an approximate evaluation (a few sweeps rather than an exact solve) is used instead.

F. What this buys, and what it assumes

Both algorithms deliver an optimal policy for a known MDP. That assumption is the important one: value and policy iteration both require the transition model $P(s' \mid s, a)$ and reward function $R(s)$ up front. They are planning algorithms, not learning algorithms.

An agent dropped into an unknown environment has neither. It must act, observe what happens, and improve - which is the subject of Reinforcement Learning and Q-Learning.

Key takeaways

• An MDP is states, actions, a transition model, and rewards, with the Markov property making the current state a sufficient summary of the past.
• A policy specifies an action for every state; solving an MDP means finding an optimal one.
• Discounting keeps infinite-horizon utilities finite, bounded by $R_{\max}/(1-\gamma)$, so policies remain comparable.
• The Bellman equation $U(s) = R(s) + \gamma \max_a \sum_{s'} P(s' \mid s,a)U(s')$ is nonlinear because of the $\max$.
• Value iteration applies it as an update until the utilities converge; our world settled at $U(s_1) = 0.3902$, confirmed exactly as $0.32/0.82$.
• Policy iteration alternates evaluation and improvement; fixing the policy removes the $\max$ and leaves linear equations.
• Both require a known model - they plan, they do not learn.

What's next

Reinforcement Learning and Q-Learning drops the assumption that the model is known and learns good behaviour from experience alone.