Markov and Partially Observable Decision Processes

Imagine a small delivery robot navigating an office. It starts near the elevator, must pick up a package from a desk, and deliver it to a reception counter. The floor is slippery in places, the robot's wheel encoders are noisy, and a closed door sometimes hides the counter from view. Every few seconds the robot faces a choice: drive forward, turn, or pause and re-check its surroundings. Some choices lead smoothly to the goal. Others waste energy, or worse, send the robot tumbling down the stairwell at the end of the hall.

Notice how many distinct difficulties are packed into this humble scenario. Uncertainty enters through at least three separate doors: the slippery floor makes the consequences of actions unpredictable, the noisy encoders make the robot unsure where it is, and the closed door hides information about what exists beyond the robot's current line of sight. A useful formalism has to accommodate all three, and, as we will see, it handles them in different ways: stochastic transitions belong to the dynamics, while partial observability demands a deeper change to what "state" even means for the agent. Keeping these sources of uncertainty separate in your mind from the start will make the second half of this chapter much easier to absorb.

This chapter gives you the formal vocabulary for problems like this one. In Part I: The World-Model Idea, we built world models that predict what happens next. Prediction alone, however, does not tell the robot what to do. A perfect forecasting model can tell the robot where each candidate action leads, but it attaches no preference among those futures. To reason about action, we need three additional ingredients: a notion of choice (actions), a notion of desirability (rewards), and a way to score long-term consequences (returns and value functions). The Markov Decision Process, or MDP, packages these ingredients into a formalism that underlies nearly all modern work in sequential decision making. Its partially observable cousin, the POMDP, extends it to the realistic case where the agent never sees the true state of the world.

We will proceed in four steps. First, we define the MDP and examine the Markov assumption that makes it tractable. Second, we develop policies, returns, and value functions, culminating in the Bellman equations and value iteration. Third, we study how the Markov assumption fails and how POMDPs repair the damage with belief states. Finally, we implement both sides: a fully observed gridworld solved by value iteration, and a T-maze experiment showing quantitatively why memory turns a losing agent into a winning one. The material here is the foundation for everything in Part II: Inference, Decisions, and Control: the next chapter, Bayesian Filtering and Belief States, develops the estimation machinery this chapter motivates.

This section connects the dynamical systems view from Part I to the decision-making view we need now, and fixes the vocabulary we will use for the rest of the book.

Recall from Mathematical and Dynamical Foundations that a controlled dynamical system evolves according to a state transition rule such as $s_{t+1} = f(s_t, a_t, w_t)$, where $a_t$ is a control input and $w_t$ is noise. A world model, as we framed it in What Is a World Model?, is essentially a learned version of $f$: given the current situation and a candidate action, it predicts what happens next. Nothing in that formulation says whether the action is good, bad, or indifferent. The model is a neutral simulator, and if you hand an agent nothing but a simulator, the best it can do is enumerate futures, not rank them.

Decision making adds a scoring layer. We assume the environment emits a scalar reward after each transition, and the agent's goal is to collect as much cumulative reward as possible over time. This single assumption is remarkably productive: navigation, game playing, resource management, and motor control can all be cast as reward accumulation, and the rest of this chapter is about reasoning precisely with it. It is worth pausing on how strong a simplification this is. Every objective we might care about, whether it is "deliver the package," "minimize energy," or "keep the factory running," gets flattened onto a single number line. That flattening buys enormous mathematical power: comparing any two behavior patterns reduces to comparing two numbers. It also carries risk, since a poorly chosen reward measures something other than what we intended. We return to that danger in the Limitations section; for now, note that the entire machinery ahead takes the reward function as given and asks only how to maximize it.

Because the words state, observation, and action will carry heavy loads, let us fix their meanings now:

• State ($s$): the situation of the environment, including anything that influences its future. The agent may or may not have access to it.
• Observation ($o$): what the agent actually senses. Observations can be incomplete, noisy, or ambiguous about the state.
• Action ($a$): a decision the agent selects, which influences the transition of the state.
• Transition ($P$): the probabilistic rule by which states evolve under actions.
• Reward ($r$): a scalar signal emitted by the environment, treated as given rather than chosen by the agent.
• Policy ($\pi$): the agent's decision rule, mapping whatever it knows to an action.
• Environment: the process that consumes actions and produces next states, observations, and rewards.

Keeping these roles distinct matters more than it might seem. Much confusion in applied work comes from blurring state with observation, or from treating a learned latent representation as if it were the environment state. For example, when a neural network compresses camera frames into a latent vector, it is tempting to call that vector "the state." Whether it deserves the name depends entirely on whether it preserves everything relevant to the future, which is precisely the question the Markov property will let us pose precisely. We will return to that distinction repeatedly.

This section defines the MDP formally, states the Markov assumption, and explains discounting and horizons. Everything later in the book, from Kalman filters to large-scale world models, is best read as a variation on this template.

Each element answers a distinct question, and it helps to read the tuple that way. The state space $\mathcal{S}$ and initial distribution $\rho_0$ describe where the story can begin. The action set $\mathcal{A}$ describes what the agent can influence. The transition kernel $P$ describes how the world responds, capturing both physics and noise in a single conditional distribution. The reward function $R$ describes what matters, translating each transition into a score. Finally, the discount factor $\gamma$ describes how patient the agent is, a quantity whose full meaning emerges below. If you can locate all six pieces for a concrete problem, you have turned an informal description into a solvable decision problem.

The transition kernel is the world model in miniature: it answers the predictive question "if we do $a$ here, where do we end up?" The reward function answers the evaluative question "how much did that outcome help?" Notice the deliberate division of labor between the two: prediction is descriptive, evaluation is normative, and neither substitutes for the other. A fully specified MDP is therefore a complete decision problem, and much of this book is about learning or approximating its pieces from data. Later chapters differ mainly in which piece they learn and how they plan against the learned version, while the skeleton of the problem stays exactly as written above.

The adjective Markov refers to one assumption that does an enormous amount of work.

Why does this matter so much? Because it collapses an ever-growing history into a fixed-size summary. Without it, every quantity of interest would be indexed by a history $h_t$. At a fixed finite horizon, the history set is finite but grows exponentially whenever actions or observations branch. With an unbounded horizon, individual histories also grow without bound, so there is no fixed finite history table or fixed-size per-state recursion. Under the Markov property, by contrast, a policy only needs the current state, transition probabilities only need the current state and action, and the mathematics of planning becomes recursive rather than historical. Every efficient algorithm in this book, from value iteration to Kalman filtering to latent dynamics models, exploits some version of this compression.

It is worth being precise about what the Markov property does not claim. It does not claim the world is deterministic, nor that it is noiseless, nor even that the state is small. Stochasticity survives fully intact inside $P(s' \mid s, a)$; the property constrains what the probabilities condition on, not how random they are. Nor does it claim the agent's chosen representation is automatically adequate. It claims only that the chosen state representation is predictively sufficient: no information relevant to the future is missing from it. Whether a given representation satisfies this is an empirical property of the environment paired with the representation, and Section "When the Markov Assumption Fails" examines what happens when it does not hold.

There is also a constructive reading worth internalizing: the Markov property is something you can often engineer. If position alone fails to predict next position, include velocity; if velocity fails, include acceleration; if battery charge matters, measure it. Each enrichment costs dimensionality, so practical modeling is a negotiation between sufficiency and tractability. That negotiation recurs throughout this book wherever learned latent representations stand in for engineered features.

The agent does not care about individual rewards so much as about their accumulated total. The quantity of interest is the return $G_t$, the total discounted reward from time $t$ onward:

For episodic tasks that terminate, such as our delivery robot finishing its route, the sum simply stops at the terminal time step. For continuing tasks that never end, the discount factor $\gamma$ serves two purposes at once, and understanding both prevents a lot of confusion.

First, $\gamma$ is an economic preference for earlier reward. With $\gamma = 0.9$, a reward arriving ten steps from now counts about $0.9^{10} \approx 0.35$ as much as the same reward today. This mirrors interest rates and time preferences in economics, and in many applications it encodes the fact that sooner is better: energy spent today cannot be reclaimed by reward promised tomorrow. Second, and more technically, $\gamma$ guarantees that the infinite sum stays finite and that the optimization problem is well posed. As long as rewards are bounded and $\gamma < 1$, the return is bounded by $r_{\max}/(1-\gamma)$. Without this guarantee, summing rewards forever could diverge, and two infinite quantities could not be compared; with it, every policy receives a finite score and there is always a well-defined best one to seek.

The quantity $1/(1-\gamma)$ is called the effective horizon: it measures how many future steps materially influence decisions. With $\gamma = 0.9$ the effective horizon is 10 steps; with $\gamma = 0.99$ it is 100. Choosing $\gamma$ is therefore not a numerical detail but a modeling statement about how far ahead the agent should reason. Set it too low and a greedy agent will happily sprint toward a pit because tomorrow's catastrophe is discounted away; set it too high and planning becomes computationally expensive and statistically fragile, since values then depend on chains of many uncertain predictions. We will see in the value iteration experiments that $\gamma$ bounds the worst-case contraction rate of Bellman backups, while the transition structure can make actual convergence substantially faster. It therefore sits at the junction of modeling intent and algorithmic cost.

The abstract discussion of discounting becomes much clearer when drawn. The next figure shows how much a unit of reward is worth as a function of how far in the future it arrives, for several values of $\gamma$.

Each curve is a straight line on the logarithmic axis because $\gamma^k$ decays geometrically, and its slope is set entirely by $\gamma$. The labeled effective horizons make the modeling statement explicit: moving from $\gamma = 0.9$ to $\gamma = 0.99$ stretches the decision-relevant future from ten steps to one hundred.

Two variations round out the picture. In finite-horizon problems, the agent optimizes reward over exactly $H$ remaining steps; the optimal policy then generally depends on the countdown, so it is nonstationary even in a stationary environment. Intuitively, with ten steps left it pays to take a shortcut you would refuse with three steps left, because there will be time to recover from it. In the average-reward formulation, the agent maximizes reward per step in the long run, which suits some scheduling and queueing problems where no natural notion of "early versus late" exists. Discounted infinite-horizon formulations dominate practice because their theory is especially clean, and we use one for the tabular MDP and value-iteration treatment below. The later T-maze is instead a finite, undiscounted episode.

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.

Before writing any code, let us solve a complete MDP analytically. The problem is small enough to do with algebra, which makes the Bellman machinery concrete.

A machine is either working (W) or broken (B). When working, you may operate it, earning reward 4 per step, but each step it breaks with probability 0.1. Alternatively you may service it, earning nothing but keeping it working. When broken, you may repair it at a cost of 2, returning it to working state in one step, or wait and earn nothing while it stays broken. The discount factor is $\gamma = 0.9$.

First, guess the structure of the optimal policy: operate when working, repair when broken. We will verify the guess afterward. This guess-and-verify pattern is a standard analytical technique: in small problems you can hypothesize the shape of the solution, solve the resulting linear system, and then check that no alternative action contradicts the hypothesis. Under this policy, the Bellman expectation equations read:

Substituting the second equation into the first:

Solving, $v(\mathrm{W}) = 3.82 / 0.109 \approx 35.05$, and then $v(\mathrm{B}) \approx 0.9 \times 35.05 - 2 \approx 29.54$.

Now verify the guess by checking that neither alternative action beats the assumed one. Servicing instead of operating when working yields $0 + 0.9 \times 35.05 \approx 31.55$, which is less than 35.05. Waiting instead of repairing when broken yields $0.9 \times 29.54 \approx 26.59$, less than 29.54. Both alternatives lose, so the guessed policy is indeed optimal, and the values are correct.

The guess-and-verify calculation has already certified that operating in W and repairing in B are the winning actions. We can therefore iterate the fixed-policy Bellman backup for those two actions from zero; it reaches the same values that the full max-based optimality operator $\mathcal{T}$ would compute.

The iterates settle onto the exact fixed point computed by substitution, while the displayed hand values are rounded to $35.05$ and $29.54$. With the stopping rule used here, the remaining numerical fixed-point error is on the order of $10^{-9}$; the larger dotted offset against the two-decimal hand value is therefore rounding, not failed convergence. The error falls along the $\gamma^k$ reference slope.

Three observations are worth drawing out. First, the value of a working machine, about 35, vastly exceeds any single-step reward, because it prices in the entire expected future stream. Value is a stock of future income, not a flow, and the discount factor determines the exchange rate between them. Second, the value gap is exact: $v(W)-v(B)=2+0.1v(W)=600/109\approx5.5046$. The immediate repair cost contributes 2, while the remaining term prices the repair transition against the working state's discounted future. Third, the same numbers would fall out of value iteration automatically: the algebra we did by hand is what the fixed-point iteration computes numerically. Starting from zeros, applying $\mathcal{T}$ repeatedly converges to these same two numbers without ever forming a linear system explicitly. When a problem is too large to solve as a linear system, iterative methods take its place.

This section examines how real environments violate the assumptions we just made, why those violations are dangerous, and what conceptual repairs exist. The T-maze experiment later in the chapter measures one such failure precisely.

The Markov property is a statement about a representation, not about the world. The physical world is arguably Markovian at the level of microscopic physics, but the representations available to an agent almost never are. Cameras see surfaces, not velocities; software agents inherit databases, not causal mechanisms. Between the full physical state and whatever the agent records lies an abstraction, and abstractions lose information. The common representation-induced failures fall into a handful of recurring patterns:

• Sensor aliasing: two distinct situations produce identical observations. Our delivery robot at either end of a symmetric corridor sees the same walls. Anything built only from momentary sensations is blind to the difference, however consequential it may be.
• Latent physical quantities: variables that matter but are not directly sensed, such as the charge left in a battery, the contents of a closed drawer, or whether a door is locked. These variables influence outcomes while hiding from measurement.
• Observation delays: the reading available at time $t$ describes an earlier state, so the current observation alone omits the intervening evolution. Timestamping and stacking delayed observations can restore sufficiency when the delay is known.
• Exogenous processes: parts of the environment the agent does not model, such as other people moving through the office, inject state changes the agent's $s_t$ cannot explain. To the agent these events look like irreducible noise, though from a richer viewpoint they are perfectly predictable.
• Deliberate abstraction: compressed or learned state representations merge situations for the sake of tractability, silently destroying distinctions that matter for control. Dimensionality reduction is safe only when the discarded directions carry no decision-relevant information, which is rarely verifiable for free.

The consequence of these representation failures is the same: the agent's apparent state becomes an unreliable basis for prediction and control. Predictions conditioned on $s_t$ are systematically biased, because the omitted history carried real information. Note the word systematically: these errors do not average out like sampling noise, because they repeat in exactly the same direction whenever the same hidden context recurs. Worse for decision making, the optimal action can depend on the missing information. In an aliased corridor whose two ends hide a goal and a hazard, no fixed reaction to the current observation can be safe; the right move depends on which end you are actually at, and only your history distinguishes the two.

Two principal formal repairs restore a Markov state, and mature systems often combine them. The first is to enrich the state: engineer or learn features that restore sufficiency, which is the business of Sufficient State and State Abstraction in Part III. The second is to infer the missing information from history: maintain an explicit probability distribution over what the true state might be, and treat that distribution as the effective state. Enrichment pushes the ambiguity backward into sensing; inference pulls it forward into estimation. History-dependent recurrent policies and robust policies can sometimes act effectively without an explicit calibrated belief, but they do not by themselves prove that the chosen state is Markov. The second formal repair is the subject of the next section and, in full generality, of the next chapter on Bayesian filtering.

A separate assumption can fail even when the representation is sufficient: nonstationarity. As tires wear or other agents adapt, yesterday's transition kernel no longer applies. Adding time, wear state, or regime variables can convert predictable drift into a larger stationary model; changes that cannot be represented this way call for online or adaptive identification rather than belief filtering over a fixed hidden state.

This section formalizes decision making under incomplete observation. The central result is elegant: if the agent summarizes its history into a belief distribution over states, it recovers an MDP, albeit one with a continuous and high-dimensional state space.

Two structural notes help in reading the definition. First, the emission model conditions on the action $a$ as well as the new state $s'$, which captures the fact that sensors are often directional or action-dependent: looking left reveals the left corridor regardless of where the wall actually is. Second, the underlying MDP mechanics are still present and still Markov; partial observability changes what the agent knows, not how the environment evolves. The distinction between epistemic limitation and physical randomness, blurred in everyday speech, is drawn sharply here: slips live in $P$, ignorance lives in $O$.

The POMDP is the honest formalism for embodied agents. Cameras do not report object velocities, tactile sensors do not report friction coefficients, and a single image does not reveal what is behind the sofa. Any world model deployed on real sensor data is implicitly a POMDP model, whether or not its builders use the term.

With full observability, the optimal policy was a function of the current state. With partial observability, the optimal policy is a function of the entire history, because different histories consistent with the same latest observation can warrant different actions. Two agents standing in front of the same door should turn the handle only if their arrival routes imply the room behind it is unlocked; the latest observation alone cannot say. Histories grow without bound, so we need a compressed summary that preserves everything decision-relevant.

The right summary is the belief state: the posterior distribution over the true state given the history,

After taking action $a_t$ and receiving observation $o_{t+1}$, Bayes rule updates the belief:

where $\eta$ normalizes the distribution. Read the update as a dialogue between prediction and correction: the inner sum predicts where the state might have moved under the action, smearing each unit of belief across successors according to the transition kernel, and the emission factor corrects that prediction in light of what was actually observed, amplifying candidates consistent with the sensor reading and suppressing those inconsistent with it.

A tiny numeric example makes the predictor-corrector dialogue visible. Suppose the robot can be in three corridor cells, L, C, or R, and hears a beep that only the right-hand cell emits reliably.

Prediction alone moves mass symmetrically inward, taking the uniform prior to approximately $(0.27, 0.47, 0.27)$ over L, C, and R. The beep then suppresses L and shifts the posterior to approximately $(0.04, 0.27, 0.69)$. Cell R becomes the most likely location, but substantial uncertainty remains on C. One step of the filter has turned an uninformative prior into a useful, calibrated localization by multiplying predictive plausibility against sensor likelihood and renormalizing.

Beliefs that were sharp before an action may widen afterward, reflecting new uncertainty introduced by the transition, then sharpen again when the observation arrives. This is exactly the predictor-corrector structure of the Kalman filter and its nonlinear cousins, which the next chapter develops in depth; the formula above is the discrete-state special case of that whole family.

Here is the result that makes POMDPs tractable to reason about. Treat the belief $b_t$ itself as a state. The belief evolves stochastically (through the observations it receives), it is Markov (because it is a deterministic function of the previous belief, action, and fresh observation noise), and it carries a well-defined expected reward:

The intuition for the Markov claim is subtle but crucial. The old state $s_t$ was Markov for the environment, but the agent's observation stream is not Markov in $o_t$: knowing only the latest pixel, you cannot know where you are. Under the POMDP transition and observation model defined above, the true posterior belief condenses all evidential content of the history. Since $b_{t+1}$ is computed from $(b_t, a_t, o_{t+1})$ alone, conditioning on the pair (belief, action) leaves nothing predictive in earlier beliefs, which restores the property that made planning recursive in the first place. This theorem concerns the true posterior under the true model. If an agent updates a surrogate belief with misspecified transition or observation probabilities, that internal state need not retain all predictive information in the history.

The POMDP is therefore equivalent to an MDP over the space of beliefs. Early incomplete-information control work includes Åström's 1965 formulation, while Smallwood and Sondik's 1973 finite-horizon analysis developed belief-space dynamic programming and its piecewise-linear convex value structure. All the machinery of the first half of this chapter applies, with one sobering caveat: the belief space is a continuum of probability distributions, with dimension equal to the number of states minus one. Exact value iteration over beliefs is practical only for tiny problems, and finding optimal POMDP policies is computationally intractable in the worst case. Practical systems use approximations such as point-based value iteration, particle filters, or, increasingly, learned latent representations that play the role of beliefs implicitly. Those approximations occupy several later chapters.

One further wrinkle distinguishes belief-space planning from ordinary MDP planning: because collecting information changes the belief, acting can serve two purposes at once. An action might gather reward or gather evidence, and sometimes the best evidence-gathering move earns nothing immediately. This state-information tension vanishes in a fully observed problem with known dynamics, where no action teaches the agent anything new about the current state or model. Fully observed problems with unknown dynamics can still require exploration to learn the model.

We now make the first half of the chapter executable. Our running example is a $5\times5$ office gridworld: the delivery robot starts at the bottom-left corner, a charging goal sits at the top-right, and an open stairwell (a pit) sits at the center. Each move succeeds with probability 0.8 and slips to a perpendicular direction with probability 0.1 each, simulating the slippery floor. Reaching the goal earns 20, falling into the pit costs 20, and every other step costs 1, encouraging short routes.

First, the imports and the environment model. We represent the transition kernel and reward function as dense arrays, indexed as T[action, state, next_state].

Two distinct lobes appear instead of a symmetric spread around the mean: a tall lobe of successful deliveries whose returns spread across the planned value, with unobstructed routes landing above it and early slip-induced detours landing below, and a thin but costly lobe of pit outcomes far below zero. All 4,000 seeded rollouts reached one of the two terminals within the 100-step cap; the code asserts that no timeout was silently discarded. The empirical mean differs slightly from the planned value because of finite-sample noise. The value-iteration approximation contributes at most about $10^{-11}$ here, negligible beside the Monte Carlo standard error. Within the two-lobe empirical decomposition, increasing the pre-change pit probability from $p$ to $2p$ while holding the conditional return distributions fixed would shift the population mean by $p$ times the gap between their conditional means. That is why the tail should be inspected separately from the average.

The key parameters for the gridworld planning experiment are:

• gamma: Discount factor, set to 0.9. It controls how far ahead the agent plans and sets the geometric contraction rate of value iteration.
• slip: Slip probability, set to 0.1 per perpendicular direction. Together with the 0.8 success probability it models the slippery floor.
• Reward schedule: Entering the goal earns 20, entering the pit costs 20, and every other step costs 1, encouraging short, safe routes.
• Tolerance: Sweeping stops when the maximum per-sweep value change falls below 1e-12, placing the returned values within roughly 1e-11 of the exact fixed point and making them effectively exact for this example.

We now measure what partial observability costs and what belief tracking buys. The testbed is the classic T-maze, stripped to its essentials. This example uses the undiscounted sum over its finite two-action episode, equivalently $\gamma=1$ for that bounded horizon.

At the start of each episode, the agent stands at the base of a T-shaped maze and glimpses a noisy cue telling it which arm holds the reward: the cue is correct with probability 0.9. The agent then advances to the junction. Crucially, at the junction the observation carries no information about the cue; the glimpse is gone. Entering the correct arm pays 4, entering the wrong arm pays -4, and every action costs 0.1. The latent variable "which arm is good" is drawn fresh each episode, so nothing can be memorized across episodes; the only path to above-chance performance runs through within-episode memory.

This tiny world isolates the phenomenon from the previous section: the optimal action at the junction depends on information that exists only in the agent's history. Let us code four agents that differ in how much episode information they can use: one reads the latent state directly, one remembers the cue as a belief, and two choose without retaining the cue.

The pattern in the bars tells the whole story of this chapter in one glance. The oracle bar is the ceiling imposed by the environment's latent variable. The memory bar nearly touches it, and the residual gap is $3.8-3.0=0.8$ reward units: exactly the cost of the cue being wrong on 10% of episodes, since each wrong arm changes the outcome by $3.8-(-4.2)=8.0$. This is a perceptual limitation rather than a cognitive one. No amount of additional reasoning can extract information the sensor never delivered; this decomposition of performance loss into perceptual versus cognitive components is worth carrying into every applied project. The reactive and random bars sit below zero: an agent that cannot retain information is not merely suboptimal, it is actively losing, because half of its committed guesses walk into the punished arm. Suboptimality sounds benign; negative expected return does not, and the difference between the two words is the difference between a minor engineering flaw and a system you should switch off.

The error bars describe dispersion across episodes, not uncertainty in the plotted means. The oracle follows the same successful path every time, so its standard-deviation bar has zero width. The memory agent's return varies only with whether the cue is correct. The reactive agent always commits to the right arm, so its return varies with which arm the environment rewarded. For the random agent, a separate random-number stream makes its arm choice statistically independent of that rewarded-arm draw; the return still depends on both variables because it is determined by whether they match. Their intervals overlap, but that overlap should not be read as evidence that the policies have equal expected performance.

It is worth pausing on what the memory agent's belief is for. In this maze the belief never changes after the cue, because no later observation or action reveals anything about the latent variable; the Bayes update fires exactly once per episode and thereafter just holds steady. Real environments are kinder: actions usually generate informative observations, so beliefs evolve continuously as the agent explores. Tracking a belief over both position and latent variables, using the full predictor-corrector update, is precisely the business of the next chapter, Bayesian Filtering and Belief States. The T-maze is the degenerate but clarifying case where the filter reduces to remembering one number.

The key parameters for the T-maze experiment are:

• CUE_ACCURACY: Probability, set to 0.9, that the starting cue identifies the rewarded arm correctly.
• STEP_COST: Cost per action, set to 0.1, incurred both at the junction advance and upon entering an arm.
• ARM_REWARD: Reward magnitude, set to 4.0, paid for entering the correct arm and penalized for entering the wrong arm.
• seed: Random generator seed 7 controls environment sampling; seed 8 controls the random agent's independent action stream. Both keep the experiment reproducible without repeating the same first draw in every episode.
• n_episodes: Number of evaluation episodes, set to 4000, which tightens the empirical estimates against the analytical predictions.

The MDP and POMDP formalisms give control, operations research, and reinforcement learning a shared vocabulary for dynamics, observations, objectives, and decisions. When we speak of a world model as something an agent plans against, the mathematical content of that sentence is an approximation of $P$, $R$, and, under partial observability, $O$, evaluated through the value-function lens this chapter built. Learned latent-state systems preserve the same division of labor when an encoder supplies an internal state, a transition model predicts how it evolves, and a policy or planner chooses actions against those predictions.

The limitations are equally structural, and it is better to meet them now than to discover them mid-project. First, the curse of dimensionality is not an implementation detail but a property of the representation. A belief over $|\mathcal{S}|$ enumerated states lies on a simplex of dimension $|\mathcal{S}|-1$; if the underlying state combines $m$ variables with $d$ possibilities each, then $|\mathcal{S}|=d^m$ and the belief representation grows exponentially in $m$. This arithmetic alone explains why exact tabular methods quickly become impractical and why later chapters rely on sampled trajectories, learned value functions, point-based belief planning, or amortized policies. Second, the framework takes the reward function as given, yet specifying rewards that capture what we actually want is notoriously difficult, and optimizing a misspecified reward faithfully can be worse than useless. This is the scalar-reward flattening danger promised in the opening: a single number can collapse incompatible goals, hide distributional consequences, and reward proxies that cease to track the intended outcome. An agent that maximizes the letter of a flawed specification does so relentlessly; the scalar objective treated here as an axiom is also a major source of silent failure. The safety questions of Part XII begin right here, at the moment we declare a scalar sufficient. Third, the assumptions are fragile in practice. Stationarity fails as mechanisms wear and other agents adapt, while the Markov property fails whenever the chosen representation loses information. These are distinct failure modes, though predictable drift can sometimes be absorbed into an enlarged state. As the T-maze showed, representation loss can flip a profitable agent into a losing one. The engineering responses (enriching the state, inferring beliefs, learning representations that preserve decision-relevant information, and adapting the dynamics model under drift) are not optional refinements. They are where most of the real difficulty lives.

A final limitation deserves emphasis because it recurs throughout the book: everything in this chapter evaluates a policy against a model of the environment, and the model can be wrong. Value iteration on an inaccurate $P$ produces confidently wrong values, and an agent that plans against its own model can exploit model errors in ways that look brilliant in simulation and fail in reality. Notice the asymmetry between the two kinds of error: errors in $P$ distort predictions broadly, but errors concentrated along the trajectory the plan happens to prefer are the dangerous ones, because the optimizer actively seeks out whichever futures the model rates most favorably, accurate or not. This gap between model-space optimality and environment-space performance, sometimes called model exploitation, is a first-class concern we will carry into model-based reinforcement learning and the reliability chapters. The Monte Carlo validation loop from the gridworld experiment, comparing planned values against realized returns, is the humble prototype of the safeguards those chapters develop.

This chapter built the formal backbone for everything that follows:

• An MDP $(\mathcal{S}, \mathcal{A}, P, R, \gamma, \rho_0)$ couples a world model (the transition kernel) with an objective (the reward function) and a time preference (the discount factor).
• The Markov property licenses compressing entire histories into the current state. It is a property of a representation, not of the world, and it can fail through sensor aliasing, omitted latent variables, observation delays, exogenous processes, or lossy abstraction. Nonstationarity is a separate dynamics assumption: under drift, the same represented state and action need not retain the same transition law over time.
• Returns accumulate discounted reward; the effective horizon $1/(1-\gamma)$ expresses how far ahead the agent reasons.
• Value functions convert long-horizon expectations into per-state scores. The Bellman equations make them recursive, and the Bellman operator's $\gamma$-contraction guarantees that value iteration converges to the unique optimal value function, from which a greedy policy is recovered.
• POMDPs model partial observability with an emission model. The optimal policy depends on history, but the belief state, the posterior over true states given history, restores the Markov property at the cost of a continuous, high-dimensional state space.
• The T-maze experiment quantified the stakes: maintaining a belief recovered most of an oracle's performance, while reactive policies lost reward on average. Memory is not a convenience; under partial observability it is the difference between profit and loss.

You now have the decision-theoretic skeleton on which every later chapter hangs. You can define a decision problem precisely, evaluate any policy against it recursively, plan optimally when the model is known and the state visible, and state exactly which assumptions collapse when observation becomes incomplete. The immediate next step is the one this chapter motivated but deferred: how to compute and maintain beliefs efficiently, with the Kalman filter as the canonical case. That is the subject of the next chapter, Bayesian Filtering and Belief States.

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about Markov and partially observable decision processes.