Markov and Partially Observable Decision Processes › Policies and Value Functions

This section defines what an agent's decision rule looks like, how to score it, and how the famous Bellman equations turn long-horizon scoring into a one-step recursion.

A policy $\pi$ is the agent's decision rule. Formally, $\pi(a \mid s)$ is the probability of choosing action $a$ in state $s$. Deterministic policies are the special case where one action gets probability one. A remarkable fact simplifies everything that follows: for a discounted MDP, if an optimal policy exists, a stationary deterministic optimal policy exists. You never need to remember the past or randomize to act optimally in a fully observed, discounted MDP. Partial observability changes the state on which that result operates: memory becomes necessary when the latest observation underdetermines the latent state, so history must be compressed into a belief. Once the belief is treated as the state, an unconstrained expected-return optimum can again be chosen deterministically. Randomization can still be useful for a deliberately restricted reactive controller, or under fairness, risk, or exploration constraints: when one observation aliases two latent states needing opposite actions, mixing can spread state-conditional regret instead of always sacrificing the same case, though it does not beat the best deterministic action for ordinary expected return at a fixed belief. The T-maze experiment will make the memory distinction measurable.

Given a policy, we can ask how good it is to be in a particular state, assuming the agent follows $\pi$ forever after. This is the state-value function:

Similarly, the action-value function scores taking a specific action first and following $\pi$ afterward:

The difference $q^\pi(s,a) - v^\pi(s)$ is the advantage of action $a$ over the policy's own average behavior in $s$, a quantity that becomes central when we reach policy improvement and actor-critic methods much later in the book. Positive advantage means the action beats the policy's habit in that state and the policy should lean toward it; negative advantage means the action drags the expected return down.

Notice what these definitions accomplish: they convert a long-run, stochastic question ("what will your total reward be?") into a function of the current situation. That is exactly the compression the Markov property licensed. All of the uncertainty about future slips, future rewards, and future choices collapses into a single expected number attached to each state. A value function is, in effect, a decision-oriented projection of the world model: it folds the transition kernel, the reward function, and the policy into a single number per state. Two environments with wildly different physics can share identical value functions over some region, and conversely tiny changes in $P$ can move values dramatically. Values summarize consequences, not mechanisms.

The magic of the Markov property is that expectations over infinite futures satisfy one-step recursions. Conditioning on the first transition and applying the law of total expectation gives the Bellman expectation equation for a fixed policy:

Read it from the inside out: take action $a$, land somewhere with probability $P(s' \mid s, a)$, collect the immediate reward $R(s,a,s')$, and then be worth $v^\pi(s')$ in the new state, discounted once. The discount appears once per step, matching the definition of the return, and the outer average over actions weights the policy's own choice habits. The same structure holds for action values:

These are linear systems in the unknown values, which means a fixed policy can be evaluated exactly by solving linear equations in small problems, or by iterative averaging in large ones. The recursivity itself deserves emphasis: an expectation involving infinitely many future decisions has been reduced to an equation involving only immediate quantities plus values one step ahead. Every family of algorithms you will meet, dynamic programming, temporal-difference learning, and the Bellman-consistency losses used to train modern world-model agents, is a strategy for solving equations of this shape.

For decision making we want the best achievable value, not the value of a given policy. The Bellman optimality equation replaces the policy average with a maximum:

That one-symbol change, average to maximum, transforms evaluation into optimization: instead of asking what a fixed habit achieves, the equation asks what the best single choice at each state achieves, assuming the same standard applies everywhere downstream. Collect the right-hand side into an operator $\mathcal{T}$ acting on any value function $v$:

The key property of $\mathcal{T}$ is that it is a contraction in the maximum norm. For any two value functions $v$ and $w$:

The proof is two lines and worth internalizing. The maximum operation is Lipschitz, meaning $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$. Applying that inside each state, the only difference between the two backups is the term $\gamma v(s')$ versus $\gamma w(s')$, which differs by at most $\gamma \|v - w\|_\infty$ at every successor. Because $\gamma < 1$, the operator squeezes any two value functions together by a factor of $\gamma$ per application.

Contractions have unique fixed points, and repeated application reaches the fixed point geometrically fast. This gives us value iteration, the workhorse algorithm of small-scale planning:

1. Initialize $v_0$ arbitrarily, for example to zeros.
2. Sweep over all states, setting $v_{k+1}(s) = (\mathcal{T}v_k)(s)$.
3. Stop when $\|v_{k+1} - v_k\|_\infty$ falls below a tolerance; the result approximates $v^*$.
4. Recover the greedy policy $\pi(s) = \arg\max_a \sum_{s'} P(s' \mid s, a)[R + \gamma v^*(s')]$.

Each sweep propagates value information one step backward through the transition graph, so the number of sweeps needed depends on both the effective horizon and the structure of the transition graph. Early sweeps carry almost no information; values then ripple outward from rewarded regions until distant states have absorbed news of the goal. We will watch this happen numerically in the gridworld experiment, where the successive-change curve can be checked against the geometric envelope supplied by contraction theory.

It is worth unpacking that last warning with a concrete image. Suppose a learned model forecasts positions perfectly except within a centimeter of the stairwell. Average prediction error might look impressively small, yet an agent that plans through that blind spot will confidently select trajectories ending in the stairwell. The failures are rare, but they sit exactly where decisions carry their largest stakes. Good model quality, measured globally, is therefore neither necessary nor sufficient for good control quality, measured locally; keeping the two assessments apart is one of the recurring disciplines of this book.