Finite Markov Decision Processes
The formal problem the rest of the book solves. MDPs add the associative aspect (different actions in different situations) and delayed consequences: actions influence the next state and, through it, future rewards.
- Write the four-argument dynamics $p(s',r\mid s,a)$ and derive $p(s'\mid s,a)$, $r(s,a)$, $r(s,a,s')$ from it.
- State the Markov property and where the agent–environment boundary goes.
- Compute returns by hand (work backwards with $G_t = R_{t+1}+\gamma G_{t+1}$).
- Define $v_\pi, q_\pi, v_*, q_*$; write all four Bellman equations and their backup diagrams; convert between $v$ and $q$.
- Why a greedy policy w.r.t. $v_*$ (or $q_*$) is optimal, and why $q_*$ needs no model.
- Effect of the discount rate γ and of adding a constant to rewards (continuing vs episodic).
3.1 The agent–environment interface
Note the indexing: $R_{t+1}$ (not $R_t$) is the reward due to $A_t$ — it emphasises that $R_{t+1}$ and $S_{t+1}$ are jointly determined.
In a finite MDP, $\mathcal S,\mathcal A,\mathcal R$ are finite. The dynamics are completely described by:
Everything else follows from $p$:
The probability of each possible $S_t, R_t$ depends only on the immediately preceding state and action $S_{t-1},A_{t-1}$, not on earlier history. This is a restriction on the state, not the decision process: the state must include all information about the past interaction that makes a difference for the future.
Where is the agent–environment boundary?
- Anything that cannot be changed arbitrarily by the agent is part of the environment. A robot's motors, linkages and sensors — and an animal's muscles and skeleton — belong to the environment.
- Rewards are computed "inside" the body but are considered external to the agent: they define the task, so the agent must not be able to change them.
- The boundary is the limit of the agent's absolute control, not of its knowledge (you may know exactly how a Rubik's cube works and still find it hard).
- It can be placed differently for different purposes (hierarchies of agents).
The whole framework reduces goal-directed learning to three signals: actions (the choices), states (the basis for choices), rewards (the goal). Time steps need not be fixed real-time intervals; states and actions can be low-level (voltages, sensor readings) or high-level and even mental. Rewards are always single numbers; states and actions are often structured vectors (bioreactor, pick-and-place robot).
Example 3.3 — the recycling robot
States $\{\text{high},\text{low}\}$ (battery). $\mathcal A(\text{high})=\{\text{search},\text{wait}\}$, $\mathcal A(\text{low})=\{\text{search},\text{wait},\text{recharge}\}$. Searching from high stays high w.p. $\alpha$; from low stays low w.p. $\beta$, else the battery dies, the robot is rescued (reward $-3$) and returned to high. $r_\text{search}>r_\text{wait}$.
| $s$ | $a$ | $s'$ | $p(s'\mid s,a)$ | $r(s,a,s')$ |
|---|---|---|---|---|
| high | search | high | $\alpha$ | $r_\text{search}$ |
| high | search | low | $1-\alpha$ | $r_\text{search}$ |
| low | search | high | $1-\beta$ | $-3$ |
| low | search | low | $\beta$ | $r_\text{search}$ |
| high | wait | high | 1 | $r_\text{wait}$ |
| low | wait | low | 1 | $r_\text{wait}$ |
| low | recharge | high | 1 | 0 |
Zero-probability rows (high-wait-low, low-wait-high, low-recharge-low) are omitted. In a transition graph, state nodes are large open circles, action nodes are small solid circles, and arrows out of an action node carry $p(s'\mid s,a)$ and $r(s,a,s')$ and sum to 1. Exercise 3.4 (the $p(s',r\mid s,a)$ table) has exactly these rows, with $r$ as its own column, since each $(s,a,s')$ here has a single reward.
3.2 Goals and rewards
"That all of what we mean by goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of a received scalar signal (called reward)."
- Walking robot: reward ∝ forward motion. Maze: $-1$ per step until escape (encourages speed). Can collector: +1 per can. Chess: +1 win, −1 loss, 0 otherwise.
- The reward tells the agent what you want achieved, not how. Don't reward sub-goals (e.g. capturing pieces in chess) — the agent may achieve them at the expense of the real goal. Prior knowledge belongs in the initial policy or value function.
3.3 Returns and episodes
Episodic tasks break into episodes (plays of a game, trips through a maze), each ending in a terminal state followed by a reset; $T$ is a random variable. $\mathcal S$ = non-terminal states, $\mathcal S^+$ = all states incl. terminal. Continuing tasks go on without limit ($T=\infty$) — the sum (3.7) could be infinite, so we discount:
- A reward $k$ steps in the future is worth $\gamma^{k}$ times an immediate one ($\gamma^{k-1}$ if counted from the next reward). It sets the present value of future rewards.
- $\gamma=0$: myopic — maximise only $R_{t+1}$. Fine only if actions don't influence future rewards; in general, greedily grabbing immediate reward reduces later reward.
- $\gamma\to1$: far-sighted — future rewards count more strongly.
- $\gamma<1$ keeps the infinite sum finite for bounded rewards. Rough "effective horizon": $1/(1-\gamma)$ steps (γ = 0.9 → ~10 steps, γ = 0.99 → ~100).
- Changing γ can change which policy is optimal (Exercise 3.22 below).
Example 3.4 — pole balancing, two formulations
| Formulation | Reward | Return |
|---|---|---|
| Episodic, undiscounted | +1 every step without failure | Number of steps until failure (∞ if balanced forever) |
| Continuing, discounted | −1 on failure, 0 otherwise | $-\gamma^{K-1}$ for the next failure $K$ steps away (plus later failures) |
Either way the return is maximised by balancing as long as possible.
Defaults are Exercise 3.8 (γ = 0.5, T = 5).
3.4 Unified notation for episodic and continuing tasks
Treat episode termination as entering a special absorbing state that transitions only to itself with reward 0. Then the episodic return equals the infinite sum, with or without discounting:
3.5 Policies and value functions
A policy $\pi(a\mid s)$ is a mapping from states to probabilities of selecting each action. RL methods specify how the policy changes with experience.
The value of a terminal state is always 0. Values can be estimated by averaging returns observed after each state (Monte Carlo, Ch 5) or, for many states, by a parameterised function (Part II).
Conversions between v and q (Exercises 3.12, 3.13, 3.18, 3.19)
The Bellman equation for $v_\pi$
Derivation: $v_\pi(s)=\E_\pi[G_t\mid S_t=s]=\E_\pi[R_{t+1}+\gamma G_{t+1}\mid S_t=s]$, then expand the expectation over $a$ (by π), $s',r$ (by $p$). Read it as: value of a state = expected immediate reward + discounted expected value of the next state, averaged over all possibilities weighted by $\pi(a\mid s)p(s',r\mid s,a)$. $v_\pi$ is the unique solution of this system of $|\mathcal S|$ linear equations.
Example 3.5 — gridworld
5×5 grid, actions N/S/E/W move deterministically; moving off-grid leaves you in place with reward −1; other moves give 0, except: from A every action gives +10 and teleports to A′; from B every action gives +5 and teleports to B′. With the equiprobable random policy and γ = 0.9:
- Negative values near the lower edge — high chance of hitting the wall.
- $v_\pi(A) < 10$: from A′ the agent is likely to hit the edge. $v_\pi(B) > 5$: B′ has positive value (can stumble onto A or B).
Centre value 0.7, neighbours 2.3, 0.4, −0.4, 0.7, all rewards 0, each action prob. ¼: $\;0.9\times\tfrac14(2.3+0.4-0.4+0.7)=0.9\times0.75=0.675\approx0.7$ ✓.
Adding a constant to all rewards (Exercises 3.15, 3.16)
Continuing: every state's value shifts by the same $v_c=c/(1-\gamma)$, so relative values and the optimal policy are unchanged — only the intervals between rewards matter. Episodic: the shift is $c\sum_{k=0}^{T-t-1}\gamma^k$, which depends on how long the episode lasts, so it can change the task. Example: maze with −1 per step; add $c=+2$ → +1 per step, and the agent now prefers never escaping.
Example 3.6 — golf
Reward −1 per stroke until the ball is in the hole; value = −(strokes to go). $v_\text{putt}$: −1 on the green, contours −2, −3, … outward; sand traps $-\infty$ with the putter; 6 strokes from the tee by putting only.
3.6 Optimal policies and optimal value functions
Policies are partially ordered: $\pi\ge\pi'$ iff $v_\pi(s)\ge v_{\pi'}(s)$ for all $s$. There is always at least one policy better than or equal to all others — an optimal policy $\pi_*$ (possibly several, all sharing the same value functions).
The Bellman optimality equation: the value of a state under an optimal policy equals the expected return for the best action from that state — no reference to any specific policy.
- For finite MDPs, (3.19) has a unique solution — a system of $n$ nonlinear (because of max) equations in $n$ unknowns.
- From $v_*$: any policy greedy w.r.t. $v_*$ (one-step lookahead using $p$) is optimal — because $v_*$ already accounts for all future consequences, short-term greedy = long-term optimal.
- From $q_*$: just pick $\argmax_a q_*(s,a)$ — no one-step search and no knowledge of the dynamics needed. $q_*$ "caches the results of all one-step-ahead searches" at the cost of representing a function of state–action pairs.
| Goal | Formula | Needs model? |
|---|---|---|
| $v_*$ from $q_*$ (Ex 3.25) | $v_*(s)=\max_a q_*(s,a)$ | No |
| $q_*$ from $v_*$ (Ex 3.26) | $q_*(s,a)=\sum_{s',r}p(s',r\mid s,a)[r+\gamma v_*(s')]$ | Yes |
| $\pi_*$ from $q_*$ (Ex 3.27) | $\pi_*(s)=\argmax_a q_*(s,a)$ | No |
| $\pi_*$ from $v_*$ (Ex 3.28) | $\pi_*(s)=\argmax_a\sum_{s',r}p(s',r\mid s,a)[r+\gamma v_*(s')]$ | Yes |
Exercise 3.29 — Bellman equations with $p(s'\mid s,a)$ and $r(s,a)$
Example 3.8 — solving the gridworld
$v_*(A)=24.4$. From A the optimal policy collects +10, jumps to A′, and walks 4 steps back up to A: a 5-step cycle.
Example 3.9 — recycling robot Bellman optimality equations
It amounts to exhaustive search and relies on three assumptions rarely true together: (1) dynamics accurately known; (2) enough computation; (3) Markov states. Backgammon satisfies 1 and 3 but has ~1020 states, so 2 fails. Heuristic search, DP and RL methods can all be viewed as approximately solving it — RL uses experienced transitions in place of expected ones.
3.7 Optimality and approximation
- Optimal policies can be computed only at extreme cost; the constraints are computation per time step and memory.
- Tabular case: one table entry per state (or state–action pair). Otherwise, parameterised function approximation is needed (Ch 9).
- RL's online nature lets it put more effort into frequently encountered states at the expense of rare ones (TD-Gammon may play badly in positions experts never reach) — a key property distinguishing RL from other approximate MDP solvers.
Chapter summary
| Concept | Summary |
|---|---|
| Agent / environment | Everything inside the agent is known and controllable; the environment is incompletely controllable and may or may not be known. |
| Finite MDP | Finite $\mathcal S,\mathcal A,\mathcal R$ with dynamics $p(s',r\mid s,a)$. |
| Return | Undiscounted for episodic tasks; discounted for continuing tasks; unified by an absorbing terminal state. |
| Value functions | $v_\pi,q_\pi$: expected return under π. $v_*,q_*$: the largest achievable — unique; optimal policies may be many. |
| Bellman equations | Consistency conditions; linear for $v_\pi$, nonlinear (max) for $v_*$. |
| Complete vs incomplete knowledge | Complete = the agent has the full model $p$ (DP, Ch 4). Incomplete = it doesn't (MC, TD, Ch 5–7). |
Self-test
Ex 3.5 — Modify (3.3) for episodic tasks.
$\sum_{s'\in\mathcal S^+}\sum_{r\in\mathcal R}p(s',r\mid s,a)=1$ for all $s\in\mathcal S$, $a\in\mathcal A(s)$ — the next state can be the terminal state, so sum over $\mathcal S^+$.
Ex 3.6 — Pole-balancing treated as episodic with discounting, reward −1 on failure, 0 otherwise. What is the return? How does it differ from the continuing formulation?
$G_t=-\gamma^{K-1}$ where $K$ is the number of steps until failure (the episode ends there). In the continuing version, $G_t=-\sum_i\gamma^{K_i-1}$ over all future failures — later failures also count.
Ex 3.7 — Maze robot: +1 for escaping, 0 otherwise, undiscounted episodic. It shows no improvement. Why?
Every policy that eventually escapes gets return 1, so there's no incentive to escape quickly (and with random exploration it nearly always escapes eventually). You haven't communicated "fast". Use −1 per step or discount (γ < 1).
Ex 3.8 — γ = 0.5, R = 1, 2, 6, 3, 2, T = 5. Compute G₀…G₅.
Backwards: $G_5=0$; $G_4=2$; $G_3=3+0.5\cdot2=4$; $G_2=6+0.5\cdot4=8$; $G_1=2+0.5\cdot8=6$; $G_0=1+0.5\cdot6=\mathbf 4$.
Ex 3.9 — γ = 0.9, R₁ = 2 then an infinite sequence of 7s. G₁ and G₀?
$G_1 = 7/(1-0.9)=70$; $G_0=2+0.9\cdot70=65$.
Ex 3.10 — Prove $\sum_{k=0}^\infty\gamma^k=1/(1-\gamma)$.
Let $S=\sum_{k\ge0}\gamma^k$ (converges for $|\gamma|<1$). Then $S=1+\gamma S$, so $S(1-\gamma)=1$.
Ex 3.11 — Expected next reward under a stochastic policy, in terms of π and p.
$\E[R_{t+1}\mid S_t=s]=\sum_a\pi(a\mid s)\sum_{s',r}r\,p(s',r\mid s,a)$.
Ex 3.22 — Top state: left gives +1 then 0 (and returns); right gives 0 then +2. Which policy is optimal for γ = 0, 0.9, 0.5?
$v_\text{left}=1+\gamma^2+\gamma^4+\dots=1/(1-\gamma^2)$; $v_\text{right}=2\gamma/(1-\gamma^2)$. Left is better iff $1>2\gamma$. γ = 0: left (1 vs 0). γ = 0.9: right (9.47 vs 5.26). γ = 0.5: both equal (1.33).
Why can the optimal action be chosen from $q_*$ without a model, but not from $v_*$?
$q_*(s,a)$ already includes the expected next reward and next-state value. From $v_*$ you must do a one-step lookahead $\sum_{s',r}p(s',r\mid s,a)[r+\gamma v_*(s')]$, which needs $p$.
Is the optimal value function unique? Is the optimal policy unique?
$v_*$ and $q_*$ are unique for a given MDP; there can be multiple optimal policies (any policy giving non-zero probability only to maximising actions — e.g. ties in the gridworld).
Ex 3.2 — Is the MDP framework adequate for all goal-directed learning? An exception?
Not always usefully: tasks where the state is not observable (non-Markov, partial observability), multiple goals that can't be reduced to a single scalar, or when the reward itself can be altered by the agent. Very long horizons or continuous time also strain it.
Ex 3.3 — Driving: where should the agent–environment line go?
It's a modelling choice determined by what you can control arbitrarily and what decision problem you want to learn. Too far in (muscle twitches) makes learning the high-level task very hard; too far out (tyre torques) assumes control you don't directly have. A sensible choice is where actions are reliably executable and meaningful for the goal (e.g. accelerator/brake/steering, or route choices for a navigation agent).
Chapter quiz — check your understanding
Scored quiz: pick an answer (or type a number) to get instant feedback and an explanation. Questions marked Exam-style give you values to interpret (sweeps, logs, returns, learning curves), the way exam problems do. Your best score is saved in this browser and shown on the home page. "Shuffle & restart" re-orders the questions.