Markov decision processes

You run a small workshop with one machine. Each morning it is new, worn, or broken. A tune-up costs money today. Skipping it earns you more today, but a worn machine is likely to break, and a major repair is expensive. Should you pay for the tune-up?

The bandit agents of Chapter 2 can’t even ask this question. In a bandit, pulling an arm gives you a reward and leaves the world unchanged, so the only thing an action affects is the reward it earns right now. In the workshop, today’s action changes tomorrow’s situation, and tomorrow’s situation decides which rewards are even possible. This chapter builds the standard language for such problems, the Markov decision process (MDP), and the central quantity of all of reinforcement learning: the value of a state, meaning how much reward you can expect from here on. By the end you will compute values exactly, by hand for the three-state machine and with one line of linear algebra for a gridworld. You will also see why the answer to the tune-up question depends on how patient you are.

From bandits to sequential decisions

Here is the workshop as a table. There are two actions: run the machine for a day, or repair it. Running a broken machine produces nothing, so “run” in the broken state really means “leave it broken”.

Today the machine is…	Action	Reward today	Tomorrow it is…
new	run	$+2$	new (prob. 0.6), worn (0.4)
worn	run	$0$	worn (0.5), broken (0.5)
broken	run	$0$	broken (1)
new or worn	repair	$-1$	new (1)
broken	repair	$-10$	new (1)

A worn machine earns nothing. Its output only covers the extra power and scrap. Now try to act greedily, the way a bandit agent would, by picking the action with the best immediate reward. When the machine is worn, run gives 0 and repair gives $-1$, so greedy runs it. Then half the time it breaks, and you face a $-10$ repair or a dead machine. The greedy choice looks wrong, but by how much? To answer that you have to add up rewards that arrive over many future days, and those depend on what you will do on those days too. Making this precise is the job of the rest of the chapter.

Three things are new compared with bandits:

1. There is a state $s_t$, the situation at time $t$ (here: new, worn or broken).
2. Your action $a_t$ affects not only the reward $r_t$ but also the next state $s_{t+1}$.
3. So you have to plan for delayed consequences: an action with a bad reward now can be the best one because of where it leads.

A bandit is the special case with a single state, where every action leads back to that same state.

States and the Markov property

What should count as “the state”? The answer that makes everything else work: the state must contain everything about the past that matters for the future.

The Markov property. A state signal is Markov if, once you know the current state and action, the rest of the history tells you nothing more about what happens next:

$$\Pr(s_{t+1}, r_t \mid s_t, a_t) \;=\; \Pr(s_{t+1}, r_t \mid s_0, a_0, r_0, \ldots, s_{t-1}, a_{t-1}, r_{t-1}, s_t, a_t).$$

The future is independent of the past given the present.

You have met this idea in mechanics. The position of a pendulum alone is not a state: two pendulums at the same angle can be swinging in opposite directions. The pair (angle, angular velocity) is a state, because Newton’s law is second order in the angle but first order in (angle, velocity). Phase space is exactly the choice of variables that makes dynamics depend only on the present. The Markov property is the probabilistic version of the same requirement.

Some examples:

• A chess position (plus whose turn it is, castling and en-passant rights) is Markov. How you got there doesn’t matter for what can happen next. (The threefold-repetition and fifty-move rules technically break this, because they depend on the past; programs add a repetition count and a move counter to the state.)
• A single frame of an Atari game is not Markov: you see where the ball is but not where it is going. DQN (Chapter 6) fixed this by stacking the last four frames into one state.
• The workshop: if a worn machine’s chance of breaking grows with how many days it has been worn, then “worn” alone is not Markov. “Worn for 3 days” is.

The general fix is always the same: put more history into the state. The full history $(s_0, a_0, r_0, \ldots, s_t)$ is Markov by construction, because nothing about the past is left out. So a Markov state always exists. The price is a bigger state space. In practice you look for a compact summary that keeps what matters, like velocity for the pendulum.

The MDP: five ingredients

A Markov decision process is a tuple $(\mathcal S, \mathcal A, P, r, \gamma)$:

• $\mathcal S$, the set of states. In this chapter it is finite: 3 states for the workshop, 11 cells for the gridworld below.
• $\mathcal A$, the set of actions. It may depend on the state; here it doesn’t.
• $P(s' \mid s, a)$, the transition probabilities: the chance of landing in $s'$ after taking $a$ in $s$. For each $(s, a)$ this is a probability distribution over $s'$.
• $r(s, a)$, the expected reward for taking $a$ in $s$.
• $\gamma \in [0, 1]$, the discount factor, which says how much less a reward is worth for each step it is delayed. More on it in the next section.

$P$ and $r$ together are called the model of the environment, or its dynamics. In this chapter and the next we assume we know them. From Chapter 5 on we won’t.

The agent and environment interact in a loop. In state $s_t$ the agent picks $a_t$; the environment returns a reward $r_t$ and a next state $s_{t+1} \sim P(\cdot \mid s_t, a_t)$; repeat. One run of this loop is a trajectory:

$$\tau = (s_0, a_0, r_0, s_1, a_1, r_1, s_2, \ldots).$$

The running example: a slippery gridworld

This is the gridworld of this chapter’s demo and lab. Its layout is the classic 4×3 world from Russell and Norvig’s AI textbook, so you may meet it elsewhere. It has 4 columns and 3 rows, and cells are named (row, column) with row 0 at the top. (Chapter 4 moves to a bigger grid.)

         col 0   col 1   col 2   col 3
row 0      .       .       .       G      G = goal: +1 for stepping into it, then the episode ends
row 1      .       #       .       P      P = pit:  −1 for stepping into it, then the episode ends
row 2      S       .       .       .      # = wall,  S = start

• Actions: up, right, down, left.
• Slip: with probability $1 - \text{slip}$ you move where you intended. With probability $\text{slip}/2$ each, you slip to one of the two perpendicular directions. Moving into the wall or off the edge leaves you where you were (a “bump”).
• Rewards: every step costs $0.04$ (reward $-0.04$), a small penalty for dawdling. Stepping into G adds $+1$ and stepping into P adds $-1$.

One transition, worked out. You are at (0, 2), just left of the goal, slip $= 0.2$, and you choose right:

• 0.8: you move right into the goal.
• 0.1: you slip up, bump the top edge, and stay at (0, 2).
• 0.1: you slip down to (1, 2).

So $P(\text{G} \mid (0,2), \text{right}) = 0.8$, $P((0,2) \mid (0,2), \text{right}) = 0.1$, $P((1,2) \mid (0,2), \text{right}) = 0.1$, and the expected reward is

$$r\big((0,2), \text{right}\big) = -0.04 + 0.8 \times (+1) = 0.76.$$

In code we store the whole model as two arrays: P[s, a, s2] with shape (12, 4, 12) and R[s, a] with shape (12, 4). State $s$ is cell number row * 4 + col. The lab keeps the wall cell as a dummy state that nothing ever enters, so the numbering stays that simple, which is why there are 12 states rather than 11. That’s 576 transition numbers, most of them zero. Building them is Task 1 of the lab.

Episodes, continuing tasks, and one trick to unify them

The gridworld is episodic: it has terminal states (G and P) where the interaction stops, and each run from start to terminal is an episode. Games, mazes and an LLM writing one response are episodic. The workshop is continuing: it never ends, like a thermostat or a recommender system.

A simple trick puts both in one framework. Make each terminal state absorbing: every action leads back to the same state with reward 0. An episode that “ends” is now a continuing trajectory that sits in the terminal state collecting zeros forever, which changes no sums. In the lab, $P[\text{G}, a, \text{G}] = 1$ and $R[\text{G}, a] = 0$ for every action. One consequence trips people up, so note it now: the value of a terminal state is 0. The $+1$ belongs to the step into the goal, so it is counted in $r(s, a)$ of the cell you came from.

Return and discounting

The agent’s goal is not the next reward but the sum of all the rewards to come. The return from time $t$ is

$$G_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k}.$$

For an episodic task the sum stops at the end of the episode, or, with the absorbing-state trick, just picks up zeros.

A worked return. With slip $= 0$, walk from the start along right, right, up, up, right. That takes 5 steps, and the last one enters the goal, so the rewards are $-0.04, -0.04, -0.04, -0.04, +0.96$. With $\gamma = 0.9$:

$$G_0 = -0.04\,(1 + 0.9 + 0.81 + 0.729) + 0.9^4 \times 0.96 = -0.1376 + 0.6299 = 0.4923.$$

Hold on to this number; you’ll see it again in the demo.

The single most useful fact about returns is that they are recursive:

$$G_t = r_t + \gamma\,\big(r_{t+1} + \gamma r_{t+2} + \cdots\big) = r_t + \gamma\, G_{t+1}.$$

The return from now is the reward now plus the discounted return from the next step. Everything in the rest of this chapter, and most of RL, grows out of this one line.

Why discount?

Four reasons, from most to least fundamental:

1. Finite sums. In a continuing task, an undiscounted sum of rewards can be infinite, and then “which policy is better” stops making sense. With $\gamma < 1$ and rewards bounded by $r_\text{max}$, $\lvert G_t \rvert \le r_\text{max}/(1-\gamma)$ by the geometric series.
2. Uncertainty about the future. Suppose that after every step, the world ends with probability $1-\gamma$: the machine is sold, the game is interrupted, the user closes the tab. Then the expected undiscounted total reward equals the expected discounted return. Discounting is survival probability.
3. Sooner is better. A reward now can be reinvested. With interest rate $i$, money one period later is worth $1/(1+i)$ today, a discount factor.
4. A practical knob. Smaller $\gamma$ means shorter-horizon problems, which are easier to learn and have lower variance. Chapter 8 uses this deliberately.

∂ Discounting as survival probability

Let the process continue after each step with probability $\gamma$, independently of everything else. Then the agent is still “alive” to collect $r_{t+k}$ with probability $\gamma^k$. Write $\mathbb 1_k$ for the indicator that it is alive at step $t+k$. The expected total undiscounted reward is

$$\mathbb E\Big[\sum_{k=0}^{\infty} \mathbb 1_k\, r_{t+k}\Big] = \sum_{k=0}^{\infty} \mathbb E[\mathbb 1_k]\,\mathbb E[r_{t+k}] = \sum_{k=0}^{\infty} \gamma^k\, \mathbb E[r_{t+k}],$$

using independence of $\mathbb 1_k$ and $r_{t+k}$. This is the expected discounted return. The expected lifetime is $\sum_k \gamma^k = 1/(1-\gamma)$ steps.

The effective horizon

How far ahead does a $\gamma$-discounted agent look? The weight on a reward $k$ steps away is $\gamma^k = e^{k \ln \gamma}$, and for $\gamma$ near 1, $\ln \gamma \approx -(1-\gamma)$. So

$$\gamma^k \approx e^{-k(1-\gamma)}:$$

exponential decay with a time constant of $1/(1-\gamma)$ steps. This is the effective horizon. It is also the total weight $\sum_k \gamma^k$, and the expected lifetime from the survival picture.

$\gamma$	0	0.5	0.9	0.99	0.999
horizon $1/(1-\gamma)$	1 step	2	10	100	1000

At $\gamma = 0$ the agent is myopic: $G_t = r_t$, and it maximizes immediate reward only, exactly like the greedy bandit agent that never repairs the machine. At $\gamma \to 1$ it is far-sighted.

Policies

A policy says what the agent does in each state. It can be:

• deterministic, a function $a = \pi(s)$. Example: the workshop policy run-to-failure = (new: run, worn: run, broken: repair), and maintain = (new: run, worn: repair, broken: repair).
• stochastic, a distribution $\pi(a \mid s)$. Example: the uniform random gridworld policy, $\pi(a \mid s) = 1/4$ for every action. A deterministic policy is the special case that puts probability 1 on one action.

Our policies look only at the current state, not at the time or the history. For an MDP that loses nothing: Chapter 4 shows there is always an optimal policy of this form. Stochastic policies matter for two reasons we’ll meet later. Exploration needs randomness (Chapter 5), and policy-gradient methods optimize smooth, stochastic policies (Chapter 7). A language model that samples its next token is a stochastic policy.

In code, a policy is an array pi[s, a] whose rows sum to 1.

Value functions: how good is a state?

The return $G_t$ is random: the policy may be random, and the environment certainly is. To compare states and policies we need its average. The state-value function of a policy $\pi$ is

$$V^\pi(s) = \mathbb E_\pi\big[\, G_t \mid s_t = s \,\big],$$

the expected return if you start in $s$ and follow $\pi$ from then on. "$\mathbb E_\pi$" averages over everything random: actions drawn from $\pi$, next states drawn from $P$.

Read it as “how good is it to be here, if I keep doing what I do?” A value always belongs to a policy. The same machine state is worth a lot to a careful owner and little to a careless one.

The action-value function asks a slightly different question:

$$Q^\pi(s, a) = \mathbb E_\pi\big[\, G_t \mid s_t = s,\ a_t = a \,\big],$$

the expected return if you take action $a$ in $s$ now, even if $\pi$ wouldn’t, and follow $\pi$ afterwards. Read it as “how good is it to do $a$ here, once, and then go back to my usual behavior?” That one-time deviation is exactly what you need for deciding whether to change your behavior, which is why $Q$ is the workhorse of Chapters 4 to 6.

The two relations between V and Q

The two functions are linked by two short equations, and between them they contain the whole chapter.

V from Q: average over what the policy does. In state $s$, the policy picks $a$ with probability $\pi(a \mid s)$, after which the expected return is $Q^\pi(s, a)$:

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

Q from V: one step of lookahead. Taking $a$ in $s$ earns $r(s, a)$ on average and lands you in $s'$ with probability $P(s' \mid s, a)$. From there, following $\pi$ is worth $V^\pi(s')$, discounted by one step:

$$Q^\pi(s, a) = r(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s').$$

A picture helps. Read it from the top down: from a state the policy branches over actions, and from each action the environment branches over next states.

                s                 V(s)    = Σ_a π(a|s) · Q(s,a)           ← policy's choice
            /   |   \
           a    a    a            Q(s,a)  = r(s,a) + γ Σ_s' P(s'|s,a) · V(s')   ← environment's choice
          /|\  /|\  /|\
         s' s' s' ...             V(s')   ... and so on, one level down

One more definition, because you will see it everywhere from Chapter 8 on. The advantage $A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s)$ is how much better action $a$ is than what the policy does on average in $s$. Positive advantage: do more of $a$. Most of the RL algorithms for LLMs in Part III are, at heart, ways to estimate it.

The Bellman expectation equation

Substitute the second relation into the first and you get an equation in $V^\pi$ alone:

$$V^\pi(s) = \sum_a \pi(a \mid s) \Big[\, r(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s') \,\Big].$$

This is the Bellman expectation equation. It is the expectation of the return recursion $G_t = r_t + \gamma G_{t+1}$.

What makes it powerful: $V^\pi(s)$ was defined as an average over infinitely long random futures. The Bellman equation replaces that with a local consistency condition between each state and its immediate neighbors. With $n$ states it is $n$ linear equations in $n$ unknowns. No sampling or infinite sums are needed: you solve them.

The derivation is short, but every step uses something specific, so here it is in full.

∂ Deriving the Bellman expectation equation from the return's recursion

Start from the definition and the recursion $G_t = r_t + \gamma G_{t+1}$:

$$V^\pi(s) = \mathbb E_\pi[G_t \mid s_t = s] = \mathbb E_\pi[r_t \mid s_t = s] + \gamma\, \mathbb E_\pi[G_{t+1} \mid s_t = s].$$

(Linearity of expectation. For $\gamma < 1$ and bounded rewards all the sums converge absolutely, so swapping sums and expectations is allowed.)

Condition on the action (law of total expectation, with $\Pr(a_t = a \mid s_t = s) = \pi(a \mid s)$):

$$V^\pi(s) = \sum_a \pi(a \mid s) \Big( \mathbb E[r_t \mid s_t = s, a_t = a] + \gamma\, \mathbb E_\pi[G_{t+1} \mid s_t = s, a_t = a] \Big).$$

The first term is $r(s, a)$ by definition.

Condition on the next state in the second term:

$$\mathbb E_\pi[G_{t+1} \mid s_t = s, a_t = a] = \sum_{s'} P(s' \mid s, a)\; \mathbb E_\pi[G_{t+1} \mid s_t = s, a_t = a, s_{t+1} = s'].$$

Use the Markov property. $G_{t+1}$ is built from $r_{t+1}, r_{t+2}, \ldots$, which depend on future actions (drawn from $\pi$ given the current state only) and future transitions (Markov). Given $s_{t+1} = s'$, neither depends on $s_t$ or $a_t$, so

$$\mathbb E_\pi[G_{t+1} \mid s_t = s, a_t = a, s_{t+1} = s'] = \mathbb E_\pi[G_{t+1} \mid s_{t+1} = s'].$$

Use stationarity. $P$, $r$ and $\pi$ don’t depend on time, so the expected return from $s'$ at time $t+1$ is the same function as at time $t$:

$$\mathbb E_\pi[G_{t+1} \mid s_{t+1} = s'] = V^\pi(s').$$

Put the pieces together:

$$V^\pi(s) = \sum_a \pi(a \mid s)\Big[r(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s')\Big]. \qquad \blacksquare$$

The same steps without the first averaging over $a$ give $Q^\pi(s,a) = r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^\pi(s')$, the “Q from V” relation. Exercise 3.3 asks you to write the equation in $Q$ alone.

A worked example: the workshop by hand

Let’s answer the opening question for the two workshop policies. To keep the arithmetic friendly, take $\gamma = 0.5$: an impatient owner with a horizon of about 2 days. (We redo it at $\gamma = 0.9$ in the next section.) Write $N, W, B$ for $V^\pi(\text{new}), V^\pi(\text{worn}), V^\pi(\text{broken})$.

Policy run-to-failure (run, run, repair). Each state has one action, so the sum over $a$ disappears and the Bellman equation for each state reads straight off the table:

$$\begin{aligned} N &= 2 + 0.5\,(0.6\,N + 0.4\,W) \\ W &= 0 + 0.5\,(0.5\,W + 0.5\,B) \\ B &= -10 + 0.5\,N \end{aligned}$$

Solve by substitution. The second equation gives $W = 0.25W + 0.25B$, so $0.75W = 0.25B$, so $W = B/3$. The third gives $B$ in terms of $N$. Substitute both into the first:

$$0.7\,N = 2 + 0.2\,W = 2 + \tfrac{0.2}{3}\,(-10 + 0.5N) = \tfrac{4}{3} + \tfrac{N}{30} \;\;\Rightarrow\;\; \tfrac{2}{3}N = \tfrac43 \;\;\Rightarrow\;\; N = 2.$$

Then $B = -10 + 1 = -9$ and $W = -3$. Always check by plugging back in: $W = 0.5\,(0.5 \cdot (-3) + 0.5 \cdot (-9)) = 0.5 \times (-6) = -3$. ✓

So under run-to-failure, $V = (2, -3, -9)$. A worn machine is worth $-3$: it is likely to break, and a broken one costs $-10$ to fix.

Policy maintain (run, repair, repair):

$$\begin{aligned} N &= 2 + 0.5\,(0.6\,N + 0.4\,W) \\ W &= -1 + 0.5\,N \\ B &= -10 + 0.5\,N \end{aligned}$$

Substitute $W$ into the first: $N = 2 + 0.3N + 0.2(-1 + 0.5N) = 1.8 + 0.4N$, so $0.6N = 1.8$ and $N = 3$. Then $W = 0.5$ and $B = -8.5$.

	new	worn	broken
$V$ run-to-failure	2	−3	−9
$V$ maintain	3	0.5	−8.5

Maintain is better in every state, even for this impatient owner.

Now the punchline: Q. Suppose you follow run-to-failure but, just once, repair a worn machine. Is that a good idea? That is exactly what $Q$ measures:

$$Q^{\text{rtf}}(\text{worn}, \text{repair}) = -1 + 0.5 \times V^{\text{rtf}}(\text{new}) = -1 + 0.5 \times 2 = 0,$$

while $Q^{\text{rtf}}(\text{worn}, \text{run}) = V^{\text{rtf}}(\text{worn}) = -3$. Deviating once is better by 3. The maintain policy is what you get by making that deviation permanent, and it improved every state. That’s no coincidence. It is the policy improvement theorem, which Chapter 4 proves and turns into an algorithm.

Finally, look at the myopic owner, $\gamma = 0$. Then $Q(\text{worn}, \text{run}) = 0 > Q(\text{worn}, \text{repair}) = -1$, so a $\gamma = 0$ agent never maintains. That is the greedy bandit agent from the start of the chapter, and its mistake is now a number.

The matrix form: all states at once

Solving by substitution gets tedious beyond three states. Linear algebra does it in one line.

Fix the policy and average out its action choice. That gives a Markov chain over states and a reward per state:

$$P_\pi(s' \mid s) = \sum_a \pi(a \mid s)\, P(s' \mid s, a), \qquad r_\pi(s) = \sum_a \pi(a \mid s)\, r(s, a).$$

$P_\pi$ is an $n \times n$ stochastic matrix: non-negative entries, every row summing to 1. $r_\pi$ is a vector of length $n$. Stack the values into a vector $V$ too, and the Bellman expectation equation for all states at once reads

$$V = r_\pi + \gamma P_\pi V \quad\Longleftrightarrow\quad (I - \gamma P_\pi)\, V = r_\pi \quad\Longleftrightarrow\quad V^\pi = (I - \gamma P_\pi)^{-1}\, r_\pi .$$

For run-to-failure on the workshop (states ordered new, worn, broken):

$$P_\pi = \begin{bmatrix} 0.6 & 0.4 & 0 \\ 0 & 0.5 & 0.5 \\ 1 & 0 & 0 \end{bmatrix}, \quad r_\pi = \begin{bmatrix} 2 \\ 0 \\ -10 \end{bmatrix}, \quad I - 0.5\,P_\pi = \begin{bmatrix} 0.7 & -0.2 & 0 \\ 0 & 0.75 & -0.25 \\ -0.5 & 0 & 1 \end{bmatrix},$$

and np.linalg.solve(I - 0.5 * P_pi, r_pi) returns $(2, -3, -9)$, the same as by hand. Now changing $\gamma$ costs nothing. At $\gamma = 0.9$, run-to-failure gives $V \approx (-4.85, -11.75, -14.37)$ and maintain gives $V \approx (12.06, 9.85, 0.85)$. The longer the horizon, the more maintenance pays.

What the inverse means

Is $(I - \gamma P_\pi)$ always invertible? For $\gamma < 1$, yes (Exercise 3.5 proves it). Expanding the inverse as a geometric (Neumann) series also tells you what it means:

$$V^\pi = (I - \gamma P_\pi)^{-1} r_\pi = \sum_{k=0}^{\infty} \gamma^k P_\pi^k\, r_\pi .$$

$(P_\pi^k)_{s s'}$ is the probability of being in $s'$ exactly $k$ steps after starting in $s$, so $(P_\pi^k r_\pi)(s)$ is the expected reward at step $k$. The value is the discounted sum of expected rewards over all future times. If you know Green’s functions, $(I - \gamma P_\pi)^{-1}$ is a resolvent: a sum over all paths of all lengths, each weighted by its probability and its discount.

Iterating instead of inverting

A linear solve costs $O(n^3)$. That’s nothing for 12 states, and hopeless for backgammon’s roughly $10^{20}$ states. There is a second way that uses only matrix–vector products: treat the Bellman equation as an update rule and iterate it,

$$V_{k+1} = r_\pi + \gamma P_\pi V_k, \qquad V_0 = 0.$$

Subtract the true $V^\pi = r_\pi + \gamma P_\pi V^\pi$ and you get $V_{k+1} - V^\pi = \gamma P_\pi (V_k - V^\pi)$. Since $P_\pi$ averages (rows sum to 1), the largest error shrinks by at least a factor $\gamma$ per sweep: $\max_s \lvert V_k(s) - V^\pi(s) \rvert \le \gamma^k \max_s \lvert V^\pi(s) \rvert$. This is iterative policy evaluation. Chapter 4 builds on it, and proves the convergence properly with the contraction mapping theorem. (Starting from $V_0 = 0$, after $k$ sweeps $V_k$ is the expected discounted reward of the first $k$ steps, the Neumann series cut off after $k$ terms.)

Policy evaluation, given the model P[s, a, s'], R[s, a], a policy pi[s, a], and gamma < 1

  1. P_pi[s, s'] = Σ_a pi[s, a] · P[s, a, s']        # Markov chain under pi
  2. r_pi[s]     = Σ_a pi[s, a] · R[s, a]            # expected reward per step
  3a. exact:     V = solve(I − gamma · P_pi, r_pi)
  3b. iterative: V = 0;  repeat  V ← r_pi + gamma · P_pi @ V  until max |change| < tol
  4. Q[s, a]     = R[s, a] + gamma · Σ_s' P[s, a, s'] · V[s']    # one-step lookahead

Both routes need the model, $P$ and $r$. In almost every interesting problem you don’t have it, and you learn from sampled experience instead. That is the subject of Chapter 5. And when there are too many states to list, you approximate $V$ with a function (Chapter 6).

Explore: values of a policy you design

Time to get a feel for all of this. The demo shows the gridworld. Each cell shows the policy’s arrow, its value $V^\pi(s)$, and a color: green for positive, red for negative. The values are computed exactly, by solving $(I - \gamma P_\pi) V = r_\pi$, every time you change anything. How to use it:

• Choose a policy with the preset buttons at the top. “Uniform random” draws all four faint arrows in each cell.
• Tap a cell to inspect it. The side panel shows the Bellman equation for that cell with the actual numbers plugged in (it always checks out), and the cell’s four $Q^\pi(s, a)$ values.
• Change the selected cell’s action by tapping it again (this cycles through ↑ → ↓ ←), with the arrow buttons in the panel, or with the arrow keys.
• Move the sliders to change γ, the slip probability and the reward per step.
• Sample an episode draws one random run from the selected cell and adds up its return. Average 1,000 episodes compares the average return with $V^\pi(s)$.

Policy:Shortest pathSafe detourUniform randomAlways →

negative zero positive

Tap any cell to inspect it. Tap the selected cell again, or use these buttons, to change its action.

↑→↓←random

Discount γ = Slip probability = Reward per step =

V^π(start) = Sample an episodeAverage 1,000 episodesReset

Episodes start from the selected cell. Each sample is one random run of the policy; V(s) is what their returns average to.

What to try: (1) Set slip to 0. 'Shortest path' and 'Safe detour' then give the same V(start) = 0.492, the return computed by hand above. Now raise slip: which wins, and which cell explains why? (2) Set γ to 0: every value collapses to the immediate reward. (3) In 'Shortest path', inspect the start cell: Q says ↑ beats →. Switch it and watch V(start) rise. (4) Pick 'Always →', set slip to 0, γ to 0.99 and the reward per step to +0.1. Which cells are suddenly worth the most, and why is that a warning about reward design?

A few things worth noticing as you play:

• Values are averages of returns. “Sample an episode” gives a different return every time. “Average 1,000 episodes” lands within a standard error or two of $V^\pi(s)$. The linear solve and the sampling compute the same expectation in two different ways. Chapter 5 is built on the sampling route.
• Change one arrow and many values move. A cell’s value depends on the cells it can reach, so editing one action changes the value of every state that can reach it.
• The value of an arrow depends on the slip. With slip 0, both preset paths take 5 steps. With slip 0.2, the shortest path passes (1, 2), right next to the pit, and every step up from there has a 10% chance of sliding in.

Optimal values and optimal policies

We can now evaluate any policy. The obvious next question: what is the best one?

Compare policies state by state. Say $\pi \ge \pi'$ if $V^\pi(s) \ge V^{\pi'}(s)$ in every state $s$. In the workshop, maintain $\ge$ run-to-failure. This is only a partial order: two policies can each be better in different states. The optimal value functions are the best achievable values:

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

For finite MDPs (with $\gamma < 1$), there is a remarkable fact: there is a single policy $\pi^*$ that achieves $V^*(s)$ in every state at the same time, and it can be taken deterministic. Chapter 4 proves this. Once you know $Q^*$, acting optimally is a lookup:

$$\pi^*(s) = \arg\max_a Q^*(s, a).$$

No lookahead and no model are needed. That is why Q-learning (Chapter 5) and DQN (Chapter 6) learn $Q^*$ directly. With only $V^*$, you’d need one step of lookahead through $P$ to find the best action.

$V^*$ satisfies its own Bellman equation, with the average over the policy replaced by a max:

$$V^*(s) = \max_a \Big[\, r(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^*(s') \,\Big].$$

This is the Bellman optimality equation. Because of the max it is no longer linear, so one call to solve won’t do. Solving it, by value iteration and policy iteration, is the whole of Chapter 4. For now, two facts you can check yourself. In the demo with the default settings, “Shortest path” with the start switched to ↑ happens to be optimal, with $V^*(\text{start}) \approx 0.351$. In the workshop, the optimal policy changes with $\gamma$: Exercise 3.6.

Summary

• An MDP $(\mathcal S, \mathcal A, P, r, \gamma)$ extends a bandit with states: actions earn rewards and move you to a new state, so good decisions must weigh delayed consequences.
• A state is Markov if it contains everything about the past that matters for the future. You can always make it so by adding history to the state (velocity for a pendulum, the whole prefix for an LLM).
• The return $G_t = \sum_k \gamma^k r_{t+k}$ satisfies $G_t = r_t + \gamma G_{t+1}$. The discount gives an effective horizon of $1/(1-\gamma)$ steps; $\gamma = 0$ is myopic.
• A policy $\pi(a \mid s)$ maps states to (distributions over) actions. $V^\pi(s)$ is the expected return from $s$, and $Q^\pi(s, a)$ is the expected return after doing $a$ once and then following $\pi$.
• $V^\pi(s) = \sum_a \pi(a \mid s) Q^\pi(s, a)$ and $Q^\pi(s, a) = r(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V^\pi(s')$. Combined, they give the Bellman expectation equation: value now = expected reward now + discounted expected value next.
• In matrix form, $V^\pi = (I - \gamma P_\pi)^{-1} r_\pi = \sum_k \gamma^k P_\pi^k r_\pi$: one linear solve, or iterate $V \leftarrow r_\pi + \gamma P_\pi V$, which converges geometrically for $\gamma < 1$.
• $Q^\pi$ tells you when a one-time deviation beats the policy. Making such deviations permanent improves the policy, a preview of Chapter 4.
• $V^*$, $Q^*$ and $\pi^*(s) = \arg\max_a Q^*(s, a)$ define optimality. Finding them needs the nonlinear Bellman optimality equation: Chapter 4.

Exercises

Exercise 3.1Markov or not?Concept●○○

For each candidate state, say whether it is Markov for the system described. If it isn’t, say what you would add to make it Markov.

1. The positions (only) of the planets in a Newtonian simulation, recorded once a day.
2. The positions and momenta of the planets in the same simulation.
3. The position of a pollen grain in water (Brownian motion), recorded once per second.
4. In poker: your own two cards plus the cards on the table.
5. A thermostat that sees only the current room temperature, where the heater takes ten minutes to warm up after switching on.
6. The text of a chat so far, for an LLM choosing its next token.

Solution

1. Not Markov. Same positions, different velocities, different futures. This is the pendulum example again.
2. Markov. Positions and momenta are the phase-space state; Hamilton’s equations are first order in them.
3. Markov to an excellent approximation. A pollen grain’s velocity decorrelates in well under a microsecond (it is overdamped), far shorter than the one-second sampling interval. So the velocity carries no usable memory between samples, and position alone predicts the future as well as the full history does. “Markov” can depend on the time scale you sample at.
4. Not Markov. The betting so far carries information about the opponents’ hidden cards: someone who raised hard probably has a strong hand. The full history of bets is better. This is a partially observable problem (a POMDP), and the principled Markov state is your belief over the hidden cards.
5. Not Markov. Two rooms at the same temperature behave differently if the heater was switched on a minute ago in one of them. Add the heater’s state and how long it has been on.
6. Markov. The state is the entire history of tokens, so nothing about the past is missing.

I've done this one

Exercise 3.2Discounted returns and the effective horizonPen & paper●○○

1. An episode has rewards $r_0, r_1, r_2, r_3 = 1, 0, 0, 5$ and then ends. With $\gamma = 0.9$, compute $G_0$ and $G_1$, and check that $G_0 = r_0 + \gamma G_1$.
2. A continuing task pays $+1$ every step forever. Compute $G_0$ for general $\gamma < 1$, then for $\gamma = 0.9$ and $\gamma = 0.99$.
3. What fraction of the total weight $\sum_{k \ge 0} \gamma^k$ falls on the first $H$ steps? Evaluate it for $H = 1/(1-\gamma)$ with $\gamma = 0.99$, and find its limit as $\gamma \to 1$.

Solution

1. $G_0 = 1 + 0.9 \cdot 0 + 0.81 \cdot 0 + 0.729 \cdot 5 = 1 + 3.645 = 4.645$. $G_1 = 0 + 0.9 \cdot 0 + 0.81 \cdot 5 = 4.05$. Check: $1 + 0.9 \times 4.05 = 1 + 3.645 = 4.645$. ✓
2. $G_0 = \sum_{k \ge 0} \gamma^k = \dfrac{1}{1-\gamma}$ (geometric series). $\gamma = 0.9$: 10. $\gamma = 0.99$: 100. This matches the effective-horizon reading: a reward of 1 per step over a horizon of $1/(1-\gamma)$ steps.
3. The first $H$ terms sum to $\dfrac{1 - \gamma^H}{1 - \gamma}$, so the fraction is $1 - \gamma^H$. For $\gamma = 0.99$, $H = 100$: $1 - 0.99^{100} = 1 - 0.366 = 0.634$. As $\gamma \to 1$ with $H = 1/(1-\gamma)$: $\gamma^H = \exp\!\big(\tfrac{\ln \gamma}{1-\gamma}\big) \to e^{-1}$ (since $\ln\gamma \approx -(1-\gamma)$), so the fraction tends to $1 - 1/e \approx 0.632$. About two-thirds of what the agent cares about lies within one horizon. That’s what “time constant” means for an exponential.

I've done this one

Exercise 3.3The Bellman equation for QPen & paper●●○

Derive the Bellman expectation equation written in $Q^\pi$ alone:

$$Q^\pi(s, a) = r(s, a) + \gamma \sum_{s'} P(s' \mid s, a) \sum_{a'} \pi(a' \mid s')\, Q^\pi(s', a').$$

Then say in one sentence how it differs from the $V$ version in where the policy’s choice appears.

Hint

Start from $Q^\pi(s,a) = \mathbb E_\pi[r_t + \gamma G_{t+1} \mid s_t = s, a_t = a]$. Condition on $s_{t+1}$ first, then on $a_{t+1}$, and use the Markov property as in the derivation of the $V$ equation.

Solution

Using $G_t = r_t + \gamma G_{t+1}$ and linearity,

$$Q^\pi(s, a) = \mathbb E[r_t \mid s_t = s, a_t = a] + \gamma\, \mathbb E_\pi[G_{t+1} \mid s_t = s, a_t = a] = r(s, a) + \gamma\, \mathbb E_\pi[G_{t+1} \mid s_t = s, a_t = a].$$

Condition on the next state $s_{t+1} = s'$, which has probability $P(s' \mid s, a)$:

$$\mathbb E_\pi[G_{t+1} \mid s_t = s, a_t = a] = \sum_{s'} P(s' \mid s, a)\, \mathbb E_\pi[G_{t+1} \mid s_t = s, a_t = a, s_{t+1} = s'].$$

By the Markov property and stationarity, the inner expectation equals $\mathbb E_\pi[G_{t+1} \mid s_{t+1} = s'] = V^\pi(s')$. Now condition on the next action $a_{t+1} = a'$, chosen with probability $\pi(a' \mid s')$:

$$V^\pi(s') = \sum_{a'} \pi(a' \mid s')\, \mathbb E_\pi[G_{t+1} \mid s_{t+1} = s', a_{t+1} = a'] = \sum_{a'} \pi(a' \mid s')\, Q^\pi(s', a').$$

Substituting gives the result. Equivalently: plug “V from Q” into “Q from V”.

The difference: in the $V$ equation the policy’s average over actions comes first (at $s$, before the environment’s average over $s'$). In the $Q$ equation the first action is fixed and the policy’s average comes after the transition, at $s'$. This is why $Q$ can evaluate actions the policy wouldn’t take, and why Q-learning and SARSA (Chapter 5) are built on it.

I've done this one

Exercise 3.4A two-state MDP by hand: the ice-cream standPen & paper●●○

An ice-cream stand has one policy (it always opens), so this is an MDP with one action per state. On a sunny day it earns 2, and tomorrow is sunny with probability 0.8. On a rainy day it earns 0, and tomorrow is sunny with probability 0.4. Let $\gamma = 0.9$.

1. Write the two Bellman equations and solve for $V(\text{sunny})$ and $V(\text{rainy})$.
2. Rainy days earn nothing, yet $V(\text{rainy})$ is not much smaller than $V(\text{sunny})$. Why? Find $V(\text{sunny}) - V(\text{rainy})$ with a one-line shortcut.
3. The weather chain has a stationary distribution $\mu$ with $\mu^\top P_\pi = \mu^\top$. Find it, and check that $\mu^\top V = \dfrac{\mu^\top r_\pi}{1-\gamma}$. Then prove this identity holds for any MDP and policy.

Hint

For part 2, subtract the two Bellman equations: you get one equation in the difference $D = V(\text{sunny}) - V(\text{rainy})$. For part 3, multiply $V = r_\pi + \gamma P_\pi V$ on the left by $\mu^\top$.

Solution

1. Write $S, R$ for the two values:

$$S = 2 + 0.9\,(0.8\,S + 0.2\,R), \qquad R = 0 + 0.9\,(0.4\,S + 0.6\,R).$$

The second gives $R\,(1 - 0.54) = 0.36\,S$, so $R = \tfrac{0.36}{0.46} S = \tfrac{18}{23} S$. The first gives $0.28\,S = 2 + 0.18\,R = 2 + 0.18 \cdot \tfrac{18}{23} S$. Multiply by 23: $6.44\,S = 46 + 3.24\,S$, so $3.2\,S = 46$ and

$$V(\text{sunny}) = 14.375, \qquad V(\text{rainy}) = \tfrac{18}{23} \times 14.375 = 11.25.$$

Check: $0.9\,(0.4 \times 14.375 + 0.6 \times 11.25) = 0.9 \times (5.75 + 6.75) = 11.25$. ✓

2. The value counts all future days, discounted. With an effective horizon of 10 days and weather that forgets itself within a few days, most of the value comes from the long-run mix of sunny and rainy days, which is nearly the same whichever day you start on. Subtract the equations:

$$D = 2 + 0.9\,\big(0.8S + 0.2R - 0.4S - 0.6R\big) = 2 + 0.9 \times 0.4\,D \;\Rightarrow\; 0.64\,D = 2 \;\Rightarrow\; D = 3.125.$$

✓ ($14.375 - 11.25 = 3.125$.) Notice the factor $0.4 = 0.8 - 0.4$: it measures how much today’s weather predicts tomorrow’s. If the weather had no memory it would be 0, and $D$ would be just today’s difference in reward, 2.

3. The stationary distribution solves $\mu_S = 0.8\mu_S + 0.4\mu_R$ with $\mu_S + \mu_R = 1$, so $0.2\mu_S = 0.4\mu_R$, giving $\mu = (2/3, 1/3)$. Then $\mu^\top V = \tfrac23 \times 14.375 + \tfrac13 \times 11.25 = 9.583 + 3.75 = 13.333$, and $\mu^\top r_\pi / (1-\gamma) = (\tfrac23 \times 2) / 0.1 = 13.333$. ✓

Proof: from $V = r_\pi + \gamma P_\pi V$, multiply on the left by $\mu^\top$ and use $\mu^\top P_\pi = \mu^\top$:

$$\mu^\top V = \mu^\top r_\pi + \gamma\, \mu^\top V \;\Rightarrow\; \mu^\top V = \frac{\mu^\top r_\pi}{1-\gamma}.$$

If you start from the stationary distribution, the expected value is the long-run average reward times the horizon.

I've done this one

Exercise 3.5Why I − γPπ is invertiblePen & paper●●○

Let $P_\pi$ be any $n \times n$ stochastic matrix (non-negative entries, rows summing to 1) and $0 \le \gamma < 1$.

1. Show that $I - \gamma P_\pi$ is invertible.
2. Show that $M = (I - \gamma P_\pi)^{-1}$ has non-negative entries and that every row of $M$ sums to $1/(1-\gamma)$. Conclude that $\lvert V^\pi(s) \rvert \le \max_{s'} \lvert r_\pi(s') \rvert / (1-\gamma)$.
3. Show that $I - P_\pi$ (the case $\gamma = 1$) is always singular. What does that mean for policy evaluation with $\gamma = 1$?

Hint

For part 1, suppose $(I - \gamma P_\pi) x = 0$ and look at the component of $x$ with the largest absolute value. For part 2, use the Neumann series $\sum_k (\gamma P_\pi)^k$ and the vector of all ones, $\mathbf 1$.

Solution

1. Suppose $(I - \gamma P_\pi)x = 0$, i.e. $x = \gamma P_\pi x$. Let $i$ be the index with the largest $\lvert x_i \rvert$. Because row $i$ of $P_\pi$ is a probability distribution,

$$\lvert x_i \rvert = \gamma\, \Big\lvert \sum_j (P_\pi)_{ij}\, x_j \Big\rvert \le \gamma \sum_j (P_\pi)_{ij}\, \lvert x_j \rvert \le \gamma\, \lvert x_i \rvert.$$

Since $\gamma < 1$, this forces $\lvert x_i \rvert = 0$, so $x = 0$. The null space is trivial, hence the matrix is invertible. (In words: averaging can’t make the biggest entry bigger, and the factor $\gamma$ then shrinks it.)

2. In the max-row-sum norm, $\lVert \gamma P_\pi \rVert_\infty = \gamma < 1$, so the Neumann series $\sum_{k \ge 0} (\gamma P_\pi)^k$ converges. Multiplying it by $(I - \gamma P_\pi)$ telescopes to $I$, so it equals $M$. Every term has non-negative entries, so $M$ does too. For the row sums, $P_\pi \mathbf 1 = \mathbf 1$ gives $(\gamma P_\pi)^k \mathbf 1 = \gamma^k \mathbf 1$, so

$$M \mathbf 1 = \sum_k \gamma^k\, \mathbf 1 = \frac{1}{1-\gamma}\, \mathbf 1.$$

Then $\lvert V^\pi(s) \rvert = \lvert \sum_{s'} M_{s s'} r_\pi(s') \rvert \le \max_{s'} \lvert r_\pi(s') \rvert \sum_{s'} M_{s s'} = \max_{s'} \lvert r_\pi(s') \rvert / (1-\gamma)$. Each row of $M$ is $1/(1-\gamma)$ times a probability distribution: the discounted occupancy of each state.

3. $(I - P_\pi)\mathbf 1 = \mathbf 1 - \mathbf 1 = 0$, so $\mathbf 1$ is in the null space. Then $V = r_\pi + P_\pi V$ has either no solution (when returns diverge, e.g. a policy that bumps into a wall forever, paying $-0.04$ per step) or infinitely many (add any constant to the values in an absorbing class whose rewards are 0). For episodic tasks you can still use $\gamma = 1$: fix $V = 0$ at the terminal states and solve only for the non-terminal ones. The reduced matrix is invertible as long as the policy reaches a terminal state with probability 1 from everywhere. This is how LLM training gets away with $\gamma = 1$.

I've done this one

Exercise 3.6Which workshop policy is best?Pen & paper●●●

The workshop has $2^3 = 8$ deterministic policies.

1. Using the maintain values at $\gamma = 0.5$, $V = (3, 0.5, -8.5)$, compute all six $Q^{\text{maint}}(s, a)$. In which state does a one-time deviation help?
2. Let abandon be the policy (run, repair, run): maintain, but leave a broken machine broken. Evaluate it by hand at $\gamma = 0.5$, and check that no single-state deviation from it helps.
3. At $\gamma = 0.9$, the matrix solve gives $V^{\text{maint}} \approx (12.06, 9.85, 0.85)$. Show that now repairing a broken machine is the better choice.
4. Find the exact discount factor $\gamma^\dagger$ at which repairing and abandoning a broken machine are equally good.

Hint

Use $Q(s, a) = r(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s')$. For part 2, note that from “new” the abandon policy never reaches “broken”. For part 4: under maintain/abandon, $V(\text{new})$ satisfies a linear equation in $V(\text{new})$ alone. Repairing pays iff $-10 + \gamma\, V(\text{new}) > 0$.

Solution

1. With $\gamma = 0.5$ and $V = (3, 0.5, -8.5)$:

• $Q(\text{new}, \text{run}) = 2 + 0.5(0.6 \cdot 3 + 0.4 \cdot 0.5) = 2 + 0.5 \cdot 2 = 3$
• $Q(\text{new}, \text{repair}) = -1 + 0.5 \cdot 3 = 0.5$
• $Q(\text{worn}, \text{run}) = 0 + 0.5(0.5 \cdot 0.5 + 0.5 \cdot (-8.5)) = 0.5 \cdot (-4) = -2$
• $Q(\text{worn}, \text{repair}) = -1 + 0.5 \cdot 3 = 0.5$
• $Q(\text{broken}, \text{run}) = 0 + 0.5 \cdot (-8.5) = -4.25$
• $Q(\text{broken}, \text{repair}) = -10 + 0.5 \cdot 3 = -8.5$

The policy’s own actions have $Q = V$, as they must. The only improvement is in broken: run (leave it) gives $-4.25 > -8.5$.

2. Abandon: $B = 0 + 0.5B$, so $B = 0$. From new you only ever visit new and worn, where abandon acts like maintain, so $N = 3$ and $W = 0.5$ as before. $V^{\text{abandon}} = (3, 0.5, 0)$, at least as good as maintain everywhere. The deviations:

• $Q(\text{new}, \text{repair}) = -1 + 1.5 = 0.5 < 3$
• $Q(\text{worn}, \text{run}) = 0.5\,(0.5 \cdot 0.5 + 0.5 \cdot 0) = 0.125 < 0.5$
• $Q(\text{broken}, \text{repair}) = -10 + 1.5 = -8.5 < 0$

None helps. Chapter 4 shows that “no one-step deviation helps” means the policy is optimal, so abandon is optimal at $\gamma = 0.5$. The impatient owner scraps a broken machine.

3. At $\gamma = 0.9$, with $V^{\text{maint}} \approx (12.06, 9.85, 0.85)$, the two actions in broken are worth

• $Q(\text{broken}, \text{repair}) = -10 + 0.9 \times 12.06 = 0.85$ (this is $V(\text{broken})$, the policy’s own action),
• $Q(\text{broken}, \text{run}) = 0 + 0.9 \times 0.85 = 0.77$.

So leaving it broken for a day, then repairing, is now worse than repairing at once, and repairing wins. You can see the same thing from abandon’s side: abandon has $V(\text{broken}) = 0$ and the same $V(\text{new}) \approx 12.06$ (it never visits broken from new), so $Q^{\text{abandon}}(\text{broken}, \text{repair}) = 0.85 > 0$. A patient owner fixes the machine because the many good days afterwards outweigh the $-10$.

Checking the other states as well, $Q(\text{new}, \text{repair}) = -1 + 0.9 \times 12.06 = 9.85 < 12.06$ and $Q(\text{worn}, \text{run}) = 0.9\,(0.5 \times 9.85 + 0.5 \times 0.85) = 4.82 < 9.85$. No one-step deviation from maintain helps anywhere, so maintain is optimal at $\gamma = 0.9$.

4. Under maintain (or abandon, identical away from broken), $W = -1 + \gamma N$ and $N = 2 + \gamma(0.6N + 0.4W) = 2 - 0.4\gamma + (0.6\gamma + 0.4\gamma^2)N$, so

$$N(\gamma) = \frac{2 - 0.4\gamma}{1 - 0.6\gamma - 0.4\gamma^2}.$$

Repair ties with abandon when $\gamma N(\gamma) = 10$:

$$\gamma(2 - 0.4\gamma) = 10\,(1 - 0.6\gamma - 0.4\gamma^2) \;\Rightarrow\; 3.6\gamma^2 + 8\gamma - 10 = 0 \;\Rightarrow\; \gamma^\dagger = \frac{-8 + \sqrt{64 + 144}}{7.2} \approx 0.892.$$

(At $\gamma^\dagger$, $V(\text{new}) = 10/\gamma^\dagger \approx 11.2$ and $V(\text{worn}) = 9$, so $Q(\text{worn}, \text{run}) = 0.892 \times 0.5 \times 9 \approx 4.0 < 9$: a worn machine is still repaired, so it was right to use the maintain/abandon values for $V(\text{new})$.)

Below $\gamma \approx 0.892$ (horizon under about 9 days), scrap it. Above, repair it. Same machine, same rewards: only patience changed, and with it the optimal policy.

I've done this one

Exercise 3.7Explore the demoExplore the demo●●○

Use the demo above.

1. Set slip to 0. Compare V(start) under “Shortest path” and “Safe detour”. Then set slip to 0.2 and compare again. Which cell explains the difference?
2. Choose “Uniform random” and move the slip slider. The values don’t change at all. Why not?
3. Choose “Shortest path” with the default settings. Inspect the start cell, note $Q(\text{start}, \uparrow)$, then switch the start to ↑. The new V(start) is slightly larger than the Q value you noted. Why?
4. Choose “Always →”, slip 0, γ = 0.99, step reward +0.1. Which cells are worth the most? Compute the value of (2, 0) by hand.

Hint

For part 3: Q(start, ↑) means “go up once, then follow the old policy”. What does the old policy do if a slip sends you back to the start? For part 4: where does “Always →” take you from the bottom row, and does that episode ever end?

Solution

1. With slip 0 both give $0.492$, the return we computed by hand. Both paths take 5 steps, and nothing is random. With slip 0.2: shortest path $\approx 0.239$, safe detour $\approx 0.346$. The shortest path goes up through (1, 2), next to the pit, where every attempt to go up has a 10% chance of slipping right into the $-1$. The detour reaches (1, 2) only if it slips down from (0, 2).
2. Slipping replaces the intended direction with a perpendicular one. If the intended direction is already uniformly random over the four directions, the actual direction is still uniformly random: $P_\pi$ is identical for every slip value, so the values are too.
3. Before switching, $Q^\pi(\text{start}, \uparrow) \approx 0.341$. After switching, $V(\text{start}) \approx 0.351$. Q assumed you go up once. If a slip leaves you at the start (slipping left bumps the edge), the old policy then goes right. The new policy goes up again, which is better again. One improvement step compounds through every revisit, so the new value is at least the Q value. This is the policy improvement theorem in miniature (Chapter 4). This policy is in fact optimal for these settings.
4. The bottom row and (1, 0) are worth about $+10$. From the bottom row ”→” leads to (2, 3) and then bumps the right edge forever, and (1, 0) bumps the wall forever. The episode never ends, so the agent collects $+0.1$ per step indefinitely: $V = 0.1/(1 - 0.99) = 10$. Meanwhile the top row, which walks into the goal, is worth only about $1.1$–$1.3$. With a positive per-step reward, the “best” behavior is to never finish the task. This is a tiny case of specification gaming: the reward said “stay alive”, not “reach the goal”. Chapters 1 and 19 have the real-world versions.

I've done this one

Exercise 3.8A chatbot as an MDPConcept●●○

A language model writes a response $y$ to a prompt $x$, one token at a time, with a vocabulary of 50,000 tokens and at most 100 response tokens. A reward model scores the finished response.

1. Write down $\mathcal S$, $\mathcal A$, $P$, $r$ and a sensible $\gamma$.
2. Is the state Markov? Is the transition stochastic?
3. In words, what is $V^\pi(s)$ for a half-written response $s$?
4. Roughly how many states are there? What does that imply for the methods of this chapter?
5. What changes if the conversation has several turns, with a human replying between the model’s turns?

Hint

Map each piece of the MDP tuple onto “write one more token”. The reward model only sees finished responses, so ask what the reward is for every token before the last one. For part 4, count the possible responses of exactly 100 tokens.

Solution

1. $\mathcal S$: all sequences (prompt, partial response) up to the length limit. $\mathcal A$: the 50,000 tokens. $P$: deterministic, $s' = s$ with the chosen token appended. Ending with the end-of-sequence token (or hitting 100 tokens) moves to a terminal state. $r$: 0 for every token except the final one, whose reward is the reward model’s score $r(x, y)$. $\gamma = 1$ is fine, because every episode ends within 100 steps.
2. Markov: yes, the state is the whole history. Transitions: deterministic. All the randomness is in the policy, the model’s sampling.
3. The expected final reward-model score if the model continues from this partial response, sampling as it normally does. A promising start has a high value; a response that has already said something wrong has a low one.
4. About $50{,}000^{100} = 10^{470}$ (times the number of prompts). You can’t list the states, store $P_\pi$, or solve $(I - P_\pi)V = r_\pi$. Everything must be done from sampled responses (Chapter 5) with function approximation: a neural network as the value function (Chapter 6, Chapter 12), or no value function at all (Chapter 15).
5. The human’s reply is the environment’s move: it is not chosen by the policy and it is random from the model’s point of view, so transitions become stochastic. The human’s tokens become part of the state but are not actions, so they shouldn’t be trained on. Rewards might come per turn or only at the end. This is the setting of Chapter 18.

I've done this one

Exercise 3.9Lab, part 1: the gridworld as arraysCode●●○

In the coding lab (below), open mdp.py and implement:

• Task 1 build_gridworld(slip, step_reward): fill in P[s, a, s2] and R[s, a].
• Task 2 policy_matrices(P, R, pi): return P_pi and r_pi.
• Task 3 evaluate_exact(P, R, pi, gamma): solve $(I - \gamma P_\pi) V = r_\pi$.

The tests check your arrays on hand-computable transitions (including the (0, 2)-going-right example from this chapter). They check your workshop values against $(2, -3, -9)$ and $(3, 0.5, -8.5)$. And they simulate 3,000 episodes to check that $V(\text{start})$ really is an average return.

Hint

In Task 1, move(s, a) and perpendicular(a) from envs.py do the geometry. Two outcomes can land in the same cell (two bumps), so use +=. Terminal states need P[s, a, s] = 1 and R[s, a] = 0. In Task 3 use np.linalg.solve, not np.linalg.inv.

Solution

The core of Task 1, for a non-terminal s:

side1, side2 = perpendicular(a)
P[s, a, move(s, a)]     += 1.0 - slip
P[s, a, move(s, side1)] += slip / 2
P[s, a, move(s, side2)] += slip / 2
bonus = sum(P[s, a, s2] * EXIT_REWARD.get(kind(s2), 0.0) for s2 in range(N_STATES))
R[s, a] = step_reward + bonus

The += matters: from the top-left corner going up, the intended move and the slip to the left both bump and stay put, so $P = 0.8 + 0.1 = 0.9$. A = would give 0.1 and rows that don’t sum to 1. $R$ is the expected reward, which is why the landing bonus is weighted by $P$.

Task 2 is two averages over the policy: P_pi = np.einsum("sa,sat->st", pi, P) and r_pi = (pi * R).sum(axis=1). Task 3 is np.linalg.solve(np.eye(n) - gamma * P_pi, r_pi). Solving is faster and more accurate than forming the inverse. The full reference is in solutions/mdp.py.

I've done this one

Exercise 3.10Lab, part 2: iterate, then look one step aheadCode●●○

• Task 4 evaluate_iterative(P, R, pi, gamma, tol): iterate $V \leftarrow r_\pi + \gamma P_\pi V$ from $V = 0$ until the largest change is below tol; return $V$ and the number of sweeps.
• Task 5 q_from_v(P, R, V, gamma): return $Q[s, a] = R[s, a] + \gamma \sum_{s'} P[s, a, s'] V[s']$.

Then answer: for the uniform random policy on the gridworld, how many sweeps does Task 4 need at $\gamma = 0.5, 0.9, 0.99$ with tol = 1e-10? Compare with the bound $\gamma^k \max_s \lvert V^\pi(s) \rvert$ from the chapter. Why is the real count smaller than the bound predicts?

Hint

P @ V with P of shape (S, A, S) and V of shape (S,) gives shape (S, A). For the last question: the bound assumes the error never leaves the system. What happens to an agent that reaches a terminal state?

Solution

Task 4 is a loop: V_new = r_pi + gamma * P_pi @ V; stop when np.max(np.abs(V_new - V)) < tol. Task 5 is one line, R + gamma * P @ V. The tests check (pi * Q).sum(axis=1) == V (the “V from Q” relation). They also check that switching the start to the action with the largest $Q$ improves $V$ everywhere, the same experiment as Exercise 3.7.3.

Sweep counts for the random policy (from the reference solution): about 29 at $\gamma = 0.5$, 142 at $\gamma = 0.9$, 419 at $\gamma = 0.99$. The bound $\gamma^k \max\lvert V \rvert \le 10^{-10}$ predicts about 32, 216 and 2,300 sweeps. Reality is faster because the error shrinks by more than $\gamma$ per sweep. Under the random policy the agent leaks into the absorbing terminal states, where the error is 0, so $\gamma P_\pi$ restricted to the non-terminal states has spectral radius below $\gamma$. The bound is tight only for a chain that never terminates. run.py plots the error against the bound on a log axis: both are straight lines (geometric convergence), with different slopes.

I've done this one

Further reading

• Sutton & Barto (2018), Reinforcement Learning: An Introduction, ch. 3. The canonical treatment of finite MDPs, returns, and value functions. Note their reward index is shifted by one relative to ours (see the notation page).
• David Silver, UCL Course on RL, Lecture 2: Markov Decision Processes. A clear 90-minute lecture with slides that build the same story: Markov chain, then Markov reward process, then MDP.
• OpenAI Spinning Up, Part 1: Key Concepts in RL. A compact summary in deep-RL notation, useful as a cheat sheet when you get to Parts II and III.
• Puterman (1994), Markov Decision Processes: Discrete Stochastic Dynamic Programming. The rigorous reference, if you want the measure-theoretic details and the full theory of optimality criteria.
• Kaelbling, Littman & Cassandra (1998), Planning and acting in partially observable stochastic domains. The standard introduction to POMDPs and belief states.

Next, Chapter 4 turns the Bellman equations into algorithms that find the optimal policy when you know the model: policy iteration, value iteration, and the contraction argument that makes them converge.