Markov Decision Processes · Machine Learning

01 · Motivation

Why does this matter?

Everything you have learned so far in this course — linear regression, classification, SVMs, kernel methods — assumed a fundamentally static world. You showed the model a fixed dataset and asked for a single prediction. There was no notion of time, no sense that the prediction you make today changes what data you see tomorrow.

But many of the most important problems are not static. What unites them is a common shape: an agent interacts with an environment over many time steps; each action changes the world; rewards may be delayed; and the goal is to maximise total reward over time, not to predict a single label.

A robot learning to walk

Every motor command changes the robot’s pose, which changes which next commands are even possible. A “wrong” step now means falling a second later. The cost is delayed, and there is no labelled dataset of “correct walking sequences.”

An investment portfolio

Today’s allocation determines tomorrow’s wealth, which determines what allocations are even feasible. A great trade today can lock you out of a better trade next week.

A chess game

A single brilliant move is worthless if the next twenty are bad. The “reward” — winning the game — arrives only at the end, dozens of decisions later.

why

Three reasons sequential problems are hard

1. Actions have long-term consequences. A move that looks good now may be catastrophic in ten steps. You cannot grade each action in isolation.

2. Reward is delayed. In chess the only reward arrives at checkmate. Which of the previous 60 moves caused the victory? This is the credit-assignment problem.

3. The agent’s behaviour shapes its data. Unlike supervised learning, the agent doesn’t see a fixed dataset — it generates its own data by interacting with the world. Aggressive exploration is risky; cautious behaviour might never discover the best strategy.

This chapter introduces the Markov Decision Process (MDP), the mathematical language that captures all three difficulties in a single, surprisingly clean framework. Once you can write a problem as an MDP, an entire toolbox of algorithms (Chapters 9 and 10) becomes available to solve it.

When is reinforcement learning useful?

Two situations make the RL viewpoint essential rather than optional:

The environment dynamics are unknown or hard to model. No one writes down the equations of motion for the stock market or the response of a real customer to an ad.
The model exists but is too complex to solve exactly. Chess has perfectly known rules, yet its game tree has more leaves than atoms in the observable universe. Approximate methods are the only way forward.

The MDP framework is the common ground for both. Whether you know the dynamics (Chapter 9, “dynamic programming”) or have to learn them from experience (Chapter 10, “reinforcement learning”), the language is the same.

How is this different from what you’ve learned before?

The boundaries against two closely related problems are sharp and exam-relevant.

Supervised learning

Fixed dataset $\{(x_i, y_i)\}$ . One prediction per example, graded immediately. No time, no sequence, no feedback loop. The learner cannot change which data it sees.

Multi-armed bandit

Repeated single-step decisions. Actions yield immediate stochastic reward, but actions do not change the state — every step starts fresh. Exploration matters; long-term consequences do not.

Markov decision process

Sequential, stateful, stochastic. Each action changes the world. Reward can be delayed across many steps. Bandits are the special case where $|\mathcal{S}| = 1$ .

One way to read the progression: supervised learning adds learning to a static problem; bandits add action selection under uncertainty; MDPs add temporal structure. Each step generalises the last. Everything here reduces correctly to bandit theory if you set $|\mathcal{S}| = 1$ , and to a degenerate problem if you also set $\gamma = 0$ .

02 · Intuition

The idea in plain language

The agent–environment loop

Picture two entities passing messages back and forth. The agent is the decision-maker (your robot, your trader, your chess engine). The environment is everything else (the physics, the market, the opponent). At every tick of the clock: the agent observes the state, chooses an action; the environment transitions to a new state and emits a reward; repeat.

That single picture is the whole framework. Everything in this chapter, in Chapter 9, and in Chapter 10 is just careful formalisation of this loop.

The Markov property: memoryless states

If the agent had to remember everything it has ever seen, the problem would explode in size with time. The Markov property is the simplifying assumption that rescues us.

key

The future is independent of the past, given the present

If the current state contains enough information to predict what comes next, then the past is irrelevant. The state is a sufficient statistic for the future. Once we know $s_t$ , we can throw away $s_{t-1}, s_{t-2}, \ldots$ and lose nothing.

This is a property of how you define the state, not of the world itself. A chessboard position is Markov (the future of the game depends only on the current arrangement of pieces). A poker game’s “what cards I’ve seen” is Markov only if you include the full memory of seen cards in the state.

tip

Rat example: how state design changes the problem

A rat in a maze keeps seeing a sequence of observations bell, light, lever, bell, lever, light, lever, light, food?

If state = last observation, the rat answers based on the most recent lever or light.
If state = counts of each observation, the rat aggregates frequency information.
If state = complete history, the rat captures order and timing but pays in complexity.

Different state definitions lead to different problems and different optimal behaviours. State design is part of modelling the problem.

Fully vs partially observable worlds

There are actually three different “states” floating around in any sequential problem, and it pays to keep them distinct:

Environment state $s^e_t$ : whatever information the environment actually uses to compute the next transition and reward. Often hidden from the agent.
Agent state $s^a_t$ : whatever the agent maintains internally and uses to choose its next action — some function of the history.
Observation $o_t$ : what the agent receives each step. May be a partial, noisy view of $s^e_t$ .

The clean case — and the one this chapter studies — is when everything coincides: $o_t = s^a_t = s^e_t$ . The agent sees the full environment state directly. This is the fully observable setting, and it is exactly what an MDP models. When observations only give partial information, we have a Partially Observable MDP (POMDP), a much harder beast.

Three deceptively simple ingredients

States & Actions — what can happen?

A list of every situation the agent can be in ( $\mathcal{S}$ ) and every choice it can make ( $\mathcal{A}$ ). For chess: all positions, all legal moves.

Transitions — how does the world react?

A rule $\mathcal{P}(s' \mid s, a)$ : if I’m in state $s$ and take action $a$ , how likely am I to land in $s'$ ? Stochastic in general (slippery floors, opponent randomness).

Rewards — what do I want?

A scalar $r$ emitted each step — the agent’s only feedback signal. Positive = good, negative = bad. The agent’s purpose is to maximise the sum of these over time.

Plus one knob — the discount factor $\gamma$ — that controls how much the agent cares about the far future versus the near future. We’ll meet it formally in a moment.

The reward hypothesis (Sutton)

why

All goals can be expressed as the maximisation of a scalar reward

This is the working hypothesis of the entire field of reinforcement learning. It is probably not literally true — human goals seem more textured than a single number — but it is so powerful and so flexible that we adopt it as a starting point.

Key principle: the reward should specify what you want, not how to achieve it. If you reward “moving forward” instead of “winning the race”, the agent may discover that running in circles is technically optimal. A famous boat-racing agent learned to orbit a lagoon of respawning power-ups forever, scoring infinite reward while never finishing the race. The reward said “collect points”; the goal was “finish first”; the agent obeyed the reward.

03 · Formalism

Definitions and equations

The Markov property, precisely

A stochastic process $X_t$ is Markov when

\mathbb{P}\!\bigl(X_{t+1} = j \mid X_t = i, X_{t-1} = k_{t-1}, \ldots, X_0 = k_0\bigr) \;=\; \mathbb{P}\!\bigl(X_{t+1} = j \mid X_t = i\bigr).

Conditioning on the full history is the same as conditioning on just the current state. The state absorbs every relevant piece of the past.

why

Why this assumption is load-bearing

Without the Markov property, predicting the next step would require conditioning on the entire history $(s_0, a_0, s_1, a_1, \ldots, s_t)$ , which grows unboundedly with time. There would be no recursion to exploit, no fixed-point equation, no way to write “value of being here = reward + γ × value of next state” — because “next state” would depend on stuff that happened ten steps ago.

The Markov property is the assumption that buys us recursion. Every Bellman equation, every dynamic programming algorithm, every Q-learning update relies on it.

If we additionally assume stationarity (the transition probabilities don’t depend on $t$ ), we get a single transition matrix $P_{ij} = \mathbb{P}(X_1 = j \mid X_0 = i)$ that works for every step.

The MDP tuple

A discrete-time, finite Markov Decision Process is a tuple

\mathcal{M} \;=\; \langle\, \mathcal{S},\;\mathcal{A},\;\mathcal{P},\;\mathcal{R},\;\gamma,\;\mu_0 \,\rangle.

States $\mathcal{S}$: a finite set of states.
Actions $\mathcal{A}$: a finite set of actions (sometimes $\mathcal{A}(s)$ — the actions available depend on $s$ ).
Transitions $\mathcal{P}$: a transition kernel $\mathcal{P}(s' \mid s, a) = \mathbb{P}(s_{t+1}=s' \mid s_t = s, a_t = a)$ .
Reward $\mathcal{R}$: a reward function $\mathcal{R}(s, a) = \mathbb{E}[r_{t+1} \mid s_t = s, a_t = a]$ , the expected one-step reward.
Discount $\gamma$: a discount factor in $[0, 1]$ .
Initial law $\mu_0$: an initial-state distribution $\mu_0(s) = \mathbb{P}(s_0 = s)$ .

tip

Memorise this tuple

Every algorithm in Chapters 9 and 10 starts by writing “given an MDP $\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$ …” The first job in any RL question is to identify these five components in the problem at hand.

The return: how we score a trajectory

At each step the agent collects a reward $r_{t+1}$ . The total score we want to maximise over a trajectory is the return $v_t$ . Several flavours exist depending on the time horizon.

Finite horizon

$v_t = \sum_{k=0}^{T-t-1} r_{t+k+1}$ . Hard deadline at step $T$ . Used when the task has a natural ending (a chess game, one day of trading). Optimal policies may be non-stationary because “time left” matters.

Average reward

$\lim_{n\to\infty} \tfrac{1}{n}\sum_{i=1}^{n} r_i$ . Per-step reward in the long run. Useful for “ongoing” systems — queues, controllers, traffic — where there is no natural ending.

Discounted (most common)

$v_t = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}$ . Infinite horizon, but each reward shrinks by $\gamma$ per step. Mathematically clean, always finite for bounded rewards. The default in modern RL.

tip

Episodic vs continuing tasks

Episodic tasks have terminal/absorbing states (the Sleep state in our worked example, “checkmate” in chess). Once you enter one, the episode ends and rewards stop.
Continuing tasks never terminate (a thermostat, a power-grid controller). Discounting is essential here to keep returns finite.

A clever trick: a finite-horizon or episodic task can be reframed as a continuing one by adding a single absorbing “end” state with reward 0 and a self-loop. After that, the infinite-discounted-return machinery handles everything.

Why discount? The role of γ

The discount factor $\gamma \in [0, 1)$ might look like an arbitrary engineering parameter, but it serves several deep purposes at once:

Mathematical convergence. An infinite sum of rewards could diverge. With $\gamma < 1$ and bounded rewards, $v_t$ is always finite.
Modelling preference. “A euro today is worth more than a euro next year.” Humans, animals, and markets all discount the future.
Uncertainty about the future. $\gamma$ can be read as the probability the process continues each step; with probability $1-\gamma$ the episode ends.
Algorithmic stability. Discounting makes the Bellman operators contractions, which is what makes value iteration and policy iteration converge.

The choice of $\gamma$ controls the agent’s “horizon”: $\gamma \to 0$ is myopic (only the immediate next reward matters); $\gamma \to 1$ is far-sighted (distant rewards weigh almost as much as immediate ones).

Policies: the agent’s strategy

A policy is the agent’s rule for choosing actions. In full generality a policy can be any function of the history, but for MDPs we get a wonderful simplification: we only ever need stationary deterministic Markovian policies (we’ll see why shortly). Policies are classified along three independent axes.

Markovian vs history-dependent

Markovian: depends only on the current state $s_t$ . History-dependent: depends on the full trajectory $h_t$ . For a Markov environment, optimal Markovian policies always exist.

Deterministic vs stochastic

Deterministic: $a = \pi(s)$ , one action per state. Stochastic: $\pi(a \mid s)$ is a distribution. Stochastic policies matter for exploration and for non-MDP settings (games, POMDPs).

Stationary vs non-stationary

Stationary: the same rule at every step. Non-stationary: the rule depends on $t$ (relevant for finite-horizon problems where “how much time is left” matters).

Stationary stochastic Markovian policy

\pi(a \mid s) \;=\; \mathbb{P}(a_t = a \mid s_t = s).

A distribution over actions depending only on the current state, not on $t$ or history. A deterministic policy is the special case where one action gets probability 1; we write it $\pi : \mathcal{S} \to \mathcal{A}$ .

map

An MDP + policy collapse to a Markov chain

Once you fix a policy $\pi$ , there is no longer any choice to make — the agent’s actions are determined (in distribution) by the state. The combined system becomes a plain Markov reward process with

P^\pi(s' \mid s) = \sum_{a} \pi(a \mid s)\, \mathcal{P}(s' \mid s, a), \qquad R^\pi(s) = \sum_{a} \pi(a \mid s)\, \mathcal{R}(s, a).

This is why fixing a policy makes evaluation easy — once the action choice is decided, the rest is just a Markov chain we know how to analyse.

Value functions: how good is a state?

Given a policy $\pi$ , two natural questions about every state and every (state, action) pair:

State-value

V^\pi(s) \;=\; \mathbb{E}_\pi\!\bigl[\,v_t \,\big|\, s_t = s\,\bigr] \;=\; \mathbb{E}_\pi\!\!\left[\sum_{k=0}^{\infty}\gamma^k\, r_{t+k+1}\, \bigg|\, s_t = s\right].

“If I start in $s$ and follow $\pi$ forever, how much reward do I expect to collect?"

Action-value

Q^\pi(s, a) \;=\; \mathbb{E}_\pi\!\bigl[\,v_t \,\big|\, s_t = s, a_t = a\,\bigr].

"If I start in $s$ , take $a$ once, then follow $\pi$ forever.” Differs from $V^\pi$ only in the very first action.

The two are linked by a simple averaging:

V^\pi(s) \;=\; \sum_a \pi(a \mid s)\, Q^\pi(s, a).

The value of a state is the average of the action-values, weighted by how often the policy takes each action.

The Bellman expectation equations

Here is the key insight that unlocks all of dynamic programming. The value of a state can be written recursively: “immediate reward, plus the discounted value of where I land next.”

Bellman expectation for $V^\pi$

V^\pi(s) \;=\; \sum_{a} \pi(a \mid s)\!\left[\, \mathcal{R}(s, a) \;+\; \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\, V^\pi(s')\, \right].

Bellman expectation for $Q^\pi$

Q^\pi(s, a) \;=\; \mathcal{R}(s, a) \;+\; \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\, \sum_{a'} \pi(a' \mid s')\, Q^\pi(s', a').

key

Read it as: now + γ × later

Every Bellman equation, no matter how intimidating it looks, has the same shape: value of where I am = expected immediate reward + γ × expected value of where I go next. Keep that one phrase in mind and every formula in this and the next two chapters falls into place.

Matrix form: a linear system

For a fixed policy $\pi$ , the Bellman expectation equation is linear in $V^\pi$ . Stack the values into a vector $\mathbf{V}^\pi \in \mathbb{R}^{|\mathcal{S}|}$ , the rewards into $\mathbf{R}^\pi$ , and the transitions into a matrix $\mathbf{P}^\pi$ . Then

\mathbf{V}^\pi \;=\; \mathbf{R}^\pi \;+\; \gamma\, \mathbf{P}^\pi\, \mathbf{V}^\pi \quad \Longleftrightarrow \quad \mathbf{V}^\pi \;=\; (\mathbf{I} - \gamma\, \mathbf{P}^\pi)^{-1}\, \mathbf{R}^\pi.

Policy evaluation reduces to a linear solve. The matrix $\mathbf{I} - \gamma \mathbf{P}^\pi$ is always invertible for $\gamma < 1$ . Cost $O(|\mathcal{S}|^3)$ — fine for small problems, prohibitive when $|\mathcal{S}|$ is large.

Bellman operators

It helps to package the right-hand side of the Bellman equation as an operator that acts on value functions.

Bellman expectation operator

(T^\pi V)(s) \;=\; \sum_a \pi(a \mid s)\!\left[\,\mathcal{R}(s,a) + \gamma \sum_{s'}\mathcal{P}(s' \mid s, a)\, V(s')\right].

$T^\pi$ takes any value function and returns the next iterate. The Bellman expectation equation says $V^\pi$ is the unique fixed point: $T^\pi V^\pi = V^\pi$ .

The optimal value function and policy

Among all policies, the optimal ones achieve the highest expected return from every starting state:

Optimal value

V^*(s) \;=\; \max_\pi V^\pi(s), \qquad Q^*(s, a) \;=\; \max_\pi Q^\pi(s, a).

fact

For any finite MDP

There exists an optimal policy $\pi^*$ with $V^{\pi^*}(s) = V^*(s)$ and $Q^{\pi^*}(s, a) = Q^*(s, a)$ for every $s, a$ .
At least one optimal policy is deterministic — you never need randomisation to be optimal.
At least one optimal policy is stationary — you never need to change strategy over time.
At least one optimal policy is Markovian — you never need to remember the past beyond $s_t$ .

Given $Q^*$ , recovering an optimal policy is trivial:

\pi^*(s) \;=\; \arg\max_{a \in \mathcal{A}} Q^*(s, a).

“In each state, take the action with the highest optimal action-value.” This greedy rule is optimal because of the four facts above. Solving the MDP = finding $Q^*$ .

The Bellman optimality equations

$V^*$ and $Q^*$ satisfy a non-linear analogue of the expectation equations, with a $\max$ replacing the expectation over actions:

Bellman optimality for $V^*$

V^*(s) \;=\; \max_{a}\!\left[\, \mathcal{R}(s, a) \;+\; \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\, V^*(s') \,\right].

Bellman optimality for $Q^*$

Q^*(s, a) \;=\; \mathcal{R}(s, a) \;+\; \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\, \max_{a'} Q^*(s', a').

The expectation backup averages over actions; the optimality backup maximises. That single change is the whole difference between policy evaluation and optimisation.

The $\max$ makes the optimality system non-linear, so we can no longer solve it with one matrix inverse. The next chapter is dedicated to algorithms that handle the $\max$ iteratively.

Contraction: the algorithmic engine

The reason iterative algorithms work on MDPs is one beautiful property.

key

Bellman operators are γ-contractions in max-norm

For any two value functions $V_1, V_2$ and any policy $\pi$ :

\|\, T^\pi V_1 - T^\pi V_2 \,\|_\infty \;\le\; \gamma\, \|\, V_1 - V_2 \,\|_\infty, \qquad \|\, T^* V_1 - T^* V_2 \,\|_\infty \;\le\; \gamma\, \|\, V_1 - V_2 \,\|_\infty.

Each application of a Bellman operator shrinks the gap between any two value functions by at least a factor of $\gamma$ . By Banach’s fixed-point theorem, repeated application converges to a unique fixed point — $V^\pi$ for $T^\pi$ and $V^*$ for $T^*$ . This is the foundation of every algorithm in Chapter 9.

Deep dive

Monotonicity: if $V_1 \le V_2$ componentwise, then $T^\pi V_1 \le T^\pi V_2$ and $T^* V_1 \le T^* V_2$ .
Fixed-point uniqueness: $V^\pi$ is the only solution to $V = T^\pi V$ ; $V^*$ is the only solution to $V = T^* V$ .

Together with the contraction, these give existence, uniqueness, and convergence of the value-iteration sequence all at once.

A preview: solving the Bellman optimality equation

The Bellman optimality equation is non-linear — the $\max_a$ kills closed-form solutions. But the γ-contraction property opens three powerful routes, all developed in Chapter 9:

Value Iteration. Start with any $V$ , apply $T^*$ repeatedly. Convergence to $V^*$ guaranteed at rate $\gamma$ .
Policy Iteration. Alternate: evaluate the current policy (linear solve), then improve it by acting greedily. Often converges in surprisingly few iterations.
Linear Programming. Write the Bellman optimality inequalities as constraints and minimise $\sum_s V(s)$ . The LP optimum equals $V^*$ .

All three assume we know the MDP. When it is unknown — when the agent must learn from experience — we enter true reinforcement learning (Chapter 10): SARSA, Q-learning, and friends. But they are all, ultimately, sample-based approximations of the same Bellman operators we have just introduced.

04 · Worked example

A 3-state MDP, by hand

Three states, two actions, all numbers chosen so the arithmetic is painless. Discount $\gamma = 0.9$ .

Worked example Evaluating the Study / Procrastinate / Sleep MDP

1 · The MDP

Three states: Study (S), Procrastinate (P), Sleep (Z — terminal/absorbing). Two actions: work (W) and rest (R). The transitions and one-step rewards:

$s$	$a$	Next-state distribution	$\mathcal{R}(s,a)$
S	W	$0.8 \to$ S, $0.2 \to$ P	$+5$
S	R	$0.5 \to$ P, $0.5 \to$ Z	$+1$
P	W	$0.6 \to$ S, $0.4 \to$ P	$-1$
P	R	$1.0 \to$ Z	$+2$
Z	—	self-loop, 0 reward	$0$

We adopt the deterministic policy $\pi =$ “always work”, i.e. $\pi(\text{W} \mid \text{S}) = \pi(\text{W} \mid \text{P}) = 1$ .

2 · Evaluate the policy

Under $\pi =$ “always W”, the MDP collapses to a Markov reward process. Sleep is absorbing, so $V^\pi(\text{Z}) = 0$ , leaving two unknowns:

V^\pi(\text{S}) = 5 + 0.9\,\bigl[0.8\, V^\pi(\text{S}) + 0.2\, V^\pi(\text{P})\bigr],

V^\pi(\text{P}) = -1 + 0.9\,\bigl[0.6\, V^\pi(\text{S}) + 0.4\, V^\pi(\text{P})\bigr].

Move everything to the left and simplify:

0.28\, V^\pi(\text{S}) - 0.18\, V^\pi(\text{P}) = 5, \qquad -0.54\, V^\pi(\text{S}) + 0.64\, V^\pi(\text{P}) = -1.

3 · Solve the linear system

The determinant is $0.28 \cdot 0.64 - (-0.18)(-0.54) = 0.1792 - 0.0972 = 0.082$ , so by Cramer’s rule

V^\pi(\text{S}) = \frac{5 \cdot 0.64 - (-0.18)(-1)}{0.082} = \frac{3.2 - 0.18}{0.082} \approx 36.83,

V^\pi(\text{P}) = \frac{0.28 \cdot (-1) - (-0.54)\cdot 5}{0.082} = \frac{-0.28 + 2.70}{0.082} \approx 29.51.

Under “always work” the long-run value is roughly 37 from S and 30 from P. P is worth a lot — because from P we tend to bounce back to the high-reward state S.

4 · Compare to 'always rest'

From S, R sends us to P or Z with equal probability; from P, R sends us to Z. After one step we mostly hit Z and earn nothing more:

V^{\pi'}(\text{P}) = 2 + 0.9 \cdot 0 = 2, \qquad V^{\pi'}(\text{S}) = 1 + 0.9\,(0.5 \cdot 2 + 0.5 \cdot 0) = 1.9.

“Always rest” is dramatically worse: $1.9$ vs $\approx 37$ from S. A small immediate reward (the $+2$ from resting in P) can be misleading; the route to real value is to keep accessing S.

5 · Verify Bellman optimality at S

Is “always work” optimal? Check the max over actions of the optimality right-hand side, using the values above as $V^*$ :

$a = \text{W}$ : $\;5 + 0.9\,[0.8(36.83) + 0.2(29.51)] = 5 + 0.9 \cdot 35.37 = 36.83.$ ✓ matches.
$a = \text{R}$ : $\;1 + 0.9\,[0.5(29.51) + 0.5(0)] = 1 + 13.28 = 14.28.$ Smaller.

So W is the optimal action at S, and by the same check at P. “Always work” satisfies both Bellman equations — the expectation one (for $\pi$ ) and the optimality one (for the max). $\pi^* = \pi$ , deterministic, stationary, Markovian, exactly as promised.

05 · Visual explanation

Seeing the MDP machinery

The MDP as a graph

Every finite MDP is a labelled graph: states are circles, actions are smaller nodes attached to states, and transitions are arrows with probabilities and rewards. Here is our 3-state worked example.

Notice the two-layer structure: from each state the agent chooses one of several actions; from each (state, action) pair the world chooses (stochastically) a next state. Rewards live on the state-action layer.

Backup diagrams: the visual form of Bellman equations

The two Bellman expectation equations have a beautiful diagrammatic interpretation called a backup diagram. Time flows down; we “back up” estimates of future value into estimates of present value.

$V^\pi$ backup: a state averages over the actions $\pi$ might take, then over the next states the world might produce.
$Q^\pi$ backup: a (state, action) pair averages over the next states, then over the actions $\pi$ would pick there.

The Bellman optimality backup is identical except the average over actions ( $\sum_a \pi(a \mid s)\,\cdot$ ) is replaced by a maximum ( $\max_a \cdot$ ).

How γ shapes the agent’s horizon

The discount factor doesn’t change what the agent sees — it changes which future rewards it cares about. A reward arriving $k$ steps in the future is weighted by $\gamma^k$ . With $\gamma = 0.5$ , a reward 5 steps away is worth about 3% of an immediate one — the agent is essentially indifferent beyond a handful of steps. With $\gamma = 0.99$ , even rewards 100 steps away matter substantially. The choice of $\gamma$ is a choice of the agent’s “personality.” The first hands-on widget lets you feel this directly.

06 · Hands-on

Try it yourself

Three widgets, each isolating one idea from the chapter. Push the controls, watch the numbers, and read the takeaways — these are where the abstractions become intuitions. (The geometric convergence of the Bellman backup, hinted at in §3, gets its own interactive plot in the next chapter.)

First, policy evaluation on a 4×4 gridworld: solve $V^\pi = T^\pi V^\pi$ for a fixed policy and watch the goal’s value bleed backward through the grid as you change $\gamma$ and the slip probability.

Hands-on 2

Policy evaluation on a 4×4 gridworld

The goal (top-right) pays +1; the pit below it pays −1; every other step costs −0.04. The chosen direction succeeds with probability 1−slip and slips perpendicular with probability slip/2 each. We solve V^π = T^π V^π by repeatedly applying the Bellman expectation operator; cell shade and number are the converged V^π(s).

discount γ0.90

slip (1−p)0.20

avg V^π

-0.341

max V^π

0.792

min V^π

-0.793

iters to converge

128

Try thisStart at γ = 0.9, slip 0.2, policy right: values are highest near the goal and bleed leftward — the closer you are to +1, the more reward you expect. Switch to random and every value drops: aimless exploration wastes moves on the −0.04 step cost. Now push slip to 0.6 with right — cells near the pit lose almost all their value, because slipping into −1 becomes likely.

TakeawayV^π(s) is the expected discounted return under a fixed behaviour, the unique fixed point of T^π. Each sweep propagates the goal’s value one tile backward; the iteration count rises as γ→1, because information spreads less per step and the contraction is weaker.

Next, the discount factor as a weighting of a reward sequence: slide $\gamma$ and watch each future reward’s contribution $\gamma^k r_k$ collapse toward the present, and the total return shrink.

Hands-on 1

How γ weights a reward sequence

A fixed stream of rewards arrives over ten steps — a few small ones early, a big +10 at the end. The bars show the discounted contribution γᵏrₖ of each future reward to today’s return. Slide γ and watch the far future fade: a myopic agent (γ→0) sees almost only the next reward; a far-sighted one (γ→1) values the distant +10 almost in full.

discount γ0.90

balanced

discounted return v

8.46

undiscounted Σrₖ

16

half-life (steps)

6.6

bound rₘₐₓ/(1−γ)

100.0

Try thisSet γ = 0.5: the +10 at step 9 contributes only 0.020 — the agent is essentially blind to it, and the return is dominated by the early +2. Now slide to γ = 0.95: the distant reward suddenly matters, and the total return more than doubles. The reward stream never changed — only how much the agent cares about its future.

TakeawayThe discount factor is a preference dial, not a numerical nuisance. γᵏ decays geometrically, so the effective horizon is roughly 1/(1−γ) steps; and for bounded rewards the whole infinite sum stays finite, capped by rₘₐₓ/(1−γ).

Finally, policy vs return: pick a policy on the 3-state worked example, see its closed-form $V^\pi$ , then roll out episodes and watch the Monte-Carlo estimate $\hat V(S)$ creep toward the exact value — a preview of the sampling problem that defines Chapter 10.

Hands-on 3

Policy vs return — sample the Markov chain

The 3-state worked example: Study, Procrastinate, and the absorbing Sleep. Pick a policy — its closed-form V^π is solved exactly by the Bellman expectation equation. Then roll out episodes: each is one trajectory through the induced Markov chain, and the empirical V̂(S) (the average discounted return) creeps toward the exact value as samples accumulate.

Press “Roll 1” to begin…

rollouts

0

empirical V̂(S)

—

exact V^π(S)

36.829

|V̂ − V^π|

—

V^π(S)

36.83

V^π(P)

29.51

V^π(Z)

0.00

Try thisChoose always work and roll one episode — you’ll see a path like S ·W/+5→ S ·W/+5→ P …→ Z. Roll ×20 a few times: the running average climbs toward the closed-form V^π(S) ≈ 36.83. Now switch to always rest — episodes die almost immediately at Z, and the estimate barely scratches 2. Same MDP, different policy, vastly different value.

TakeawayA value function is an expected return — a property of the MDP and the policy. Solving the linear Bellman system gives it exactly; rolling out trajectories estimates it from samples, which is precisely what an RL agent must do when it does not know P and R in closed form.

07 · Exam intel

What the exam actually tests

MDP questions on this exam are the most predictable in the course. Six question shapes appear over and over.

Q1

Write down the MDP for the following scenario

A short prose description (a robot, a game, a market) and you must specify the tuple $\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$ . For full marks: be explicit about the state space (is the opponent’s hand part of it? the current bankroll?), enumerate actions, write $\mathcal{P}$ as a table or formula, give $\mathcal{R}$ with units, and justify the choice of $\gamma$ .

Q2

Compute V-pi for the following policy

Given a small MDP and a fixed policy, evaluate it. Two valid approaches:

Linear-system approach: write $\mathbf{V}^\pi = (\mathbf{I} - \gamma \mathbf{P}^\pi)^{-1} \mathbf{R}^\pi$ and solve. Cleaner for 2–3 states.
Iterative approach: apply $V \leftarrow T^\pi V$ a few times from $V^{(0)} = 0$ . Useful when the matrix is large or the question explicitly asks for “value-iteration steps.”

Show the matrix $\mathbf{P}^\pi$ explicitly — that’s where marks are lost.

Q3

Write the Bellman equations for this MDP

Two flavours. Expectation form (given $\pi$ ): $V^\pi(s) = \sum_a \pi(a \mid s)\bigl[\mathcal{R}(s,a) + \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\, V^\pi(s')\bigr]$ . Optimality form: $V^*(s) = \max_a \bigl[\mathcal{R}(s,a) + \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\, V^*(s')\bigr]$ . Common trap: writing $\sum_a$ when the policy is deterministic (a single term), or a single term when it is stochastic.

Q4

Prove the Bellman optimality operator is a γ-contraction

A short proof the exam loves. Skeleton:

Fix any state $s$ and two value functions $V_1, V_2$ . Use $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$ .
$\bigl|(T^* V_1)(s) - (T^* V_2)(s)\bigr| \le \max_a \bigl| \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\,[V_1(s') - V_2(s')] \bigr|.$
Pull $\gamma$ out and bound each difference by $\|V_1 - V_2\|_\infty$ ; since probabilities sum to 1, this is $\le \gamma\,\|V_1 - V_2\|_\infty$ .
Take $\sup_s$ on the left: $\|T^* V_1 - T^* V_2\|_\infty \le \gamma \|V_1 - V_2\|_\infty.$ ✓

The proof for $T^\pi$ is identical with $\max_a$ replaced by $\sum_a \pi(a \mid s)\cdot$ .

Q5

State and justify the existence of an optimal deterministic policy

Memorise the four-part statement: for any finite MDP there exists an optimal policy that is simultaneously (i) deterministic, (ii) stationary, (iii) Markovian, and (iv) achieves $V^*(s)$ and $Q^*(s,a)$ for all $s, a$ . The construction is $\pi^*(s) = \arg\max_a Q^*(s, a)$ .

Q6

What happens to the value function if γ changes?

A conceptual question. Two facts to deliver: the value function changes (higher $\gamma$ means farther rewards matter more, so values rise for positive-reward problems); and the optimal policy may change (different $\gamma$ can prefer different actions — the corridor / discount example is canonical).

tip

Memorise four formulas and you have the chapter

Bellman expectation for $V^\pi$ : $\;V^\pi(s) = \sum_a \pi(a \mid s)\bigl[\mathcal{R}(s,a) + \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\, V^\pi(s')\bigr].$
Closed-form evaluation: $\;\mathbf{V}^\pi = (\mathbf{I} - \gamma \mathbf{P}^\pi)^{-1} \mathbf{R}^\pi.$
Bellman optimality for $Q^*$ : $\;Q^*(s, a) = \mathcal{R}(s, a) + \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\, \max_{a'} Q^*(s', a').$
Greedy policy: $\;\pi^*(s) = \arg\max_a Q^*(s, a).$

08 · Common mistakes

Where students get this wrong

×

The Markov property is a property of the environment

It is a property of how you define the state. A partially-observed environment isn’t Markov in its observations; but with the right state (including memory or hidden variables) it can be Markov again. State design is a modelling choice. If your state seems insufficient, enlarge it.

×

Confusing V and Q

$V^\pi(s)$ assumes the policy is followed from the start. $Q^\pi(s, a)$ lets you take an arbitrary action $a$ once, then follow the policy. The relationship: $V^\pi(s) = \sum_a \pi(a \mid s)\, Q^\pi(s, a)$ . $Q$ is more useful for control because choosing actions directly requires comparing $Q$ values, not $V$ .

×

More reward = better — reward shaping gone wrong

Tempting to reward sub-goals (“moved one tile toward the goal: $+0.1$ ”) to “help” the agent. This often backfires: the agent racks up shaping rewards by oscillating, never reaching the actual goal. The reward must specify what you want, not how to get it. (Potential-based reward shaping preserves optimality, but it’s easy to misuse.)

×

Optimal policies must be stochastic

False for MDPs. For any finite MDP there is always a deterministic optimal policy. Stochastic policies become necessary only when the problem is no longer a true MDP — multi-agent games, partial observability, or constrained MDPs. In a vanilla MDP, randomisation buys you nothing.

×

Reward and return are the same thing

Crucial distinction. Reward $r_t$ is the one-step scalar emitted at time $t$ . Return $v_t$ is the (possibly discounted) sum of all future rewards from $t$ onward. Value functions are expected returns, not expected rewards. Mixing the two up is the single most common source of Bellman-equation sign errors.

×

γ = 1 is fine if there's a terminal state

It can be — but only if every trajectory ends in finite time with probability 1. If there’s any chance of an infinite loop, undiscounted returns can diverge and the value function is ill-defined. Discounting ( $\gamma < 1$ ) is the safe default that always gives finite values.

×

An MDP is just a bandit with more states

Half right and dangerously incomplete. A multi-armed bandit is an MDP with $|\mathcal{S}| = 1$ , but the behaviour is completely different. In a bandit, actions don’t change the world — every step is independent. In an MDP, an action’s value depends on which future states it makes accessible. The credit-assignment problem only exists in MDPs. Bandit algorithms (UCB, Thompson sampling) do not solve MDPs in general.

09 · Self-check

Can you answer these?

A robot's sensor reads the last 3 frames of camera data, and its action is move / turn / stop. Is this a Markov state?

You compute V-pi(s) = 12 and Q-pi(s, a₁) = 10, Q-pi(s, a₂) = 14. What is the most likely policy at s?

Why does the Bellman optimality equation have no closed-form matrix solution, while the expectation equation does?

With γ = 0.9, T* applied 50 times to V⁰. The gap ‖V⁵⁰ − V*‖∞ is at most:

In a continuing task with γ = 0.95 and rewards bounded by |r| ≤ 10, the maximum possible |vₜ| is:

10 · Recap

One-screen summary

Chapter 08 — load-bearing ideas

Sequential decision-making is structurally different from supervised learning: actions have long-term consequences, rewards are delayed, and the agent shapes its own data.
The Markov property — “future depends only on present, not past” — is what makes the problem tractable. State design ensures it.
An MDP is a tuple $\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$ . Every RL problem starts here.
The discount factor γ ensures finite returns, models preference for sooner rewards, and is the source of all algorithmic convergence guarantees.
A policy $\pi(a \mid s)$ collapses an MDP into a Markov chain. For any MDP there is always a stationary, deterministic, Markovian optimal policy.
Two value functions: $V^\pi(s)$ (start in $s$ , follow $\pi$ ) and $Q^\pi(s, a)$ (start in $s$ , take $a$ , then follow $\pi$ ). Linked by $V^\pi(s) = \sum_a \pi(a \mid s)\, Q^\pi(s, a)$ .
Bellman expectation: $V^\pi(s) = \sum_a \pi(a \mid s)[\mathcal{R}(s,a) + \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\, V^\pi(s')]$ . Linear in $V^\pi$ ; closed form via matrix inverse.
Bellman optimality: $V^*(s) = \max_a [\mathcal{R}(s,a) + \gamma \sum_{s'} \mathcal{P}(s' \mid s, a)\, V^*(s')]$ . Non-linear; requires iteration.
Bellman operators $T^\pi, T^*$ are γ-contractions in max-norm. Their fixed points are $V^\pi$ and $V^*$ . This is the foundation of every algorithm in Chapters 9 and 10.
Solving the MDP = finding $Q^*$ . The optimal policy is then $\pi^*(s) = \arg\max_a Q^*(s, a)$ .

→

What's next

You now have the language. Chapter 9 (Solving MDPs) shows how to actually solve them when you know $\mathcal{P}$ and $\mathcal{R}$ : policy iteration, value iteration, and linear programming all emerge directly from the contraction property you just met. Chapter 10 (Reinforcement Learning) drops the assumption that you know the dynamics, and shows how the same Bellman backups can be estimated from experience. Every algorithm from here on is a variation on “approximate the Bellman operator.”