4.Markov Decision Processes: The Formalism

4.1 The finite MDP

A finite Markov decision process is a tuple $(\mathcal{S}, \mathcal{A}, p, \gamma)$ where $\mathcal{S}$ and $\mathcal{A}$ are finite sets of states and actions, $\gamma \in [0,1)$ is a discount factor, and the dynamics are captured by a single function

$p(s', r \mid s, a) \doteq \mathbb{P}\big(S_{t+1} = s',\, R_{t+1} = r \mid S_t = s,\, A_t = a\big),$

satisfying $\sum_{s'}\sum_r p(s',r \mid s,a) = 1$ for every $(s,a)$. Everything else is derived from it. Marginalizing the reward gives the state-transition probabilities,

$p(s' \mid s, a) = \sum_r p(s', r \mid s, a),$

and weighting by reward gives the expected immediate reward,

$r(s,a) = \mathbb{E}[R_{t+1} \mid S_t = s, A_t = a] = \sum_r r \sum_{s'} p(s', r \mid s, a).$

Note the indexing convention, inherited from Chapter 1: the reward $R_{t+1}$ arrives after action $A_t$. It is a consequence, not a property of the state you were in.

Rusty's warehouse, fixed once for the rest of Part I. A $12 \times 9$ grid with shelf blocks removed, leaving about 80 traversable cells. Four actions $\{N, E, S, W\}$. Slip probability $p_{\text{slip}} = 0.2$, split evenly between the two lateral directions. Rewards: $+25$ for reaching the dock, $-1$ per step, $-10$ for bumping a shelf. Discount $\gamma = 0.95$. Chapters 5, 6 and 7 use these exact numbers, so results are comparable across algorithms.

4.2 Returns, and why we discount

The agent's goal is not to maximize immediate reward but the return — the accumulated reward from time $t$ onward:

$G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}.$

For a continuing task this is an infinite sum, and we need it to be finite. If rewards are bounded by $R_{\max}$, the geometric series gives

$|G_t| \le \sum_{k=0}^{\infty} \gamma^k R_{\max} = \frac{R_{\max}}{1 - \gamma},$

which is finite exactly because $\gamma < 1$. Discounting is not a modelling nicety; without it the objective may not be defined.

The single most useful property of the return is its recursion, obtained by factoring $\gamma$ out of everything after the first term:

Everything that follows in this book is, in some sense, this one line taken seriously.

4.3 Value functions and the Bellman expectation equations

A policy $\pi(a \mid s)$ is a distribution over actions in each state. The state-value function is the expected return from following it:

$v_\pi(s) \doteq \mathbb{E}_\pi\left[G_t \mid S_t = s\right],$

and the action-value function fixes the first action before following $\pi$ thereafter:

$q_\pi(s,a) \doteq \mathbb{E}_\pi\left[G_t \mid S_t = s, A_t = a\right].$

Now the derivation. Every step is either the return recursion, the tower property from Chapter 2, or the definition of expectation.

The same argument applied to $q_\pi$ yields its twin:

$q_\pi(s,a) = \sum_{s',r} p(s',r \mid s,a)\left[r + \gamma \sum_{a'} \pi(a' \mid s')\, q_\pi(s', a')\right].$

This is a linear system. With $|\mathcal{S}|$ unknowns and $|\mathcal{S}|$ equations, we can write it in matrix form as $v_\pi = r_\pi + \gamma P_\pi v_\pi$ and solve directly:

$v_\pi = (I - \gamma P_\pi)^{-1} r_\pi,$

with the inverse guaranteed to exist by the Neumann-series argument from §2.6. For Rusty's 80-state warehouse this is a trivial linear solve. For a robot with a continuous state space it is hopeless, which is what drives Part II.

4.4 Optimality, and the moment linearity dies

Define a partial order on policies: $\pi \ge \pi'$ if $v_\pi(s) \ge v_{\pi'}(s)$ for all states. There always exists an optimal policy $\pi_*$ that is at least as good as every other, and all optimal policies share the same value functions:

$v_*(s) = \max_\pi v_\pi(s), \qquad q_*(s,a) = \max_\pi q_\pi(s,a).$

The optimal value function satisfies a self-consistency condition of its own — but now with a maximum where the policy average used to be.

The argument is that $v_*(s)$ must equal the value of the best action available at $s$, evaluated under optimal behaviour thereafter. If some action had a higher one-step-lookahead value, the policy that took it and then behaved optimally would beat $\pi_*$ — contradiction.

Two consequences follow immediately, and they are the reason this equation is worth its fame.

Greedy is optimal. Any policy that acts greedily with respect to $v_*$ is optimal. A one-step lookahead using $v_*$ already accounts for all future consequences, because that is what $v_*$ encodes. With $q_*$ it is even easier — no lookahead at all, just $\pi_*(s) = \arg\max_a q_*(s,a)$. This is why so much of RL is the pursuit of $q_*$: get it, and the policy is free.

A deterministic optimal policy always exists for a finite MDP: pick any argmax at each state.

4.5 The contraction, at last

Chapter 2 built the fixed-point machinery. Here is what it was for.

Define the Bellman optimality operator $T_*$ on value functions by

$(T_* v)(s) \doteq \max_a \sum_{s',r} p(s',r \mid s,a)\left[r + \gamma\, v(s')\right],$

and the policy-evaluation operator $T_\pi$ analogously with $\sum_a \pi(a\mid s)$ in place of the max. The Bellman equations say precisely that $v_*$ and $v_\pi$ are the fixed points of these operators.

Now cash Chapter 2's theorem. The space of bounded value functions with the sup norm is complete, so Banach applies and delivers, at no additional cost:

1. $v_*$ exists and is the unique fixed point of $T_*$;
2. iterating $v_{k+1} = T_* v_k$ converges to it from any starting point — including the all-zeros initialization every implementation uses;
3. convergence is geometric at rate $\gamma$, with a computable error bound that tells you when to stop.

That last item is not decoration: it is the stopping rule for value iteration, and Chapter 5's dashboard displays it live.

4.6 The confession: robots never see the state

Everything above assumes the agent observes $S_t$. Rusty does not. He has wheel encoders that drift, a lidar that returns noisy ranges, and no oracle telling him which cell he occupies.

The honest formalism is a partially observable MDP — an MDP plus an observation space $\Omega$ and an observation model $O(o \mid s', a)$. The agent sees $o_t$, never $s_t$.

The standard repair is to maintain a belief $b_t(s) = \mathbb{P}(S_t = s \mid o_{1:t}, a_{1:t-1})$, a distribution over states. It updates by Bayes' rule: after taking $a$ and observing $o$,

$b'(s') = \frac{O(o \mid s', a) \sum_s p(s' \mid s, a)\, b(s)}{\sum_{s''} O(o \mid s'', a) \sum_s p(s'' \mid s, a)\, b(s)},$

where the numerator predicts forward and reweights by the observation likelihood, and the denominator normalizes.

The remarkable fact is that the belief is Markov even though the observation is not: $b_{t+1}$ depends only on $b_t$, $a_t$ and $o_{t+1}$. So a POMDP is an MDP over beliefs — all the theory above still applies. The catch is that the belief space is continuous even when $\mathcal{S}$ is finite, and solving POMDPs exactly is PSPACE-hard.

4.7 The same robot, different MDPs

One more idea before the code, because it reframes everything: the MDP is a modelling choice, not a property of the robot.

Tang and colleagues organize this along three axes. The action-space level may be low (joint torques), mid (task-space velocity commands), or high (temporally extended subroutines). The observation space may be a low-dimensional estimated state vector or raw high-dimensional sensing. The reward may be sparse or dense.

Each combination is a different MDP for the same physical task. Rusty at grid level — this chapter — has 80 states and four actions. Rusty at velocity level has a continuous state and continuous actions. Rusty at torque level, Chapter 13's territory, adds motor dynamics.

/// A set an observation or action can be drawn from.
pub trait Space {
    type Item;
    fn contains(&self, x: &Self::Item) -> bool;
    fn sample<R: rand::Rng>(&self, rng: &mut R) -> Self::Item;
}
 
pub struct Transition<S> {
    pub next_state: S,
    pub reward: f64,
    pub done: bool,
}
 
/// The black-box view: you may sample the dynamics, never inspect them.
/// This is all a real robot ever offers.
pub trait Env {
    type State: Clone;
    type Action: Copy;
 
    fn reset<R: rand::Rng>(&mut self, rng: &mut R) -> Self::State;
    fn step<R: rand::Rng>(
        &mut self,
        state: &Self::State,
        action: Self::Action,
        rng: &mut R,
    ) -> Transition<Self::State>;
    fn gamma(&self) -> f64;
}
 
/// The white-box view: the full distribution p(s′, r | s, a) is available.
/// Simulators can offer this; reality cannot.
pub trait Mdp: Env {
    fn states(&self) -> &[Self::State];
    fn actions(&self, state: &Self::State) -> &[Self::Action];
 
    /// Every (next_state, reward, probability) triple, summing to 1.
    fn transitions(
        &self,
        state: &Self::State,
        action: Self::Action,
    ) -> Vec<(Self::State, f64, f64)>;
}

4.8 Chapter bridge

The formalism is complete. An MDP is four objects; the return has a recursion; value functions satisfy Bellman equations; those equations are fixed-point conditions for operators that contract at rate $\gamma$; and Banach hands us existence, uniqueness, and a convergent algorithm with a stopping rule.

We also admitted that the state is not observable, that solving the honest version is intractable, and that the MDP itself is something an engineer chooses rather than discovers.

Chapter 5 takes the algorithm Banach promised and makes it real. With $p$ and $r$ known, we can compute $v_*$ by iteration and watch value ripple outward from Rusty's dock — and we will find that evaluation and improvement, alternated, form a pattern so general that every remaining algorithm in this book is a variation on it.

References