Markov and Partially Observable Decision Processes › Partially Observable Decision Processes

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.