Partial Observability and Belief States

"Nobody ever shows me the world. They slide me a smudged photograph under the door, ask me what to do, and slam it before I can squint. So I keep a private little ledger of how things probably are, update it with every smudge, and act on the most likely story. I have never once seen the truth, and I have stopped expecting to."

An Agent Acting on a Hunch Because It Cannot See the True State

In Chapter 23's opening we promised to relax the strongest assumption of Chapter 22: that the agent observes the Markov state directly. That assumption made the optimal policy a function of the current state alone, and it is what let dynamic programming and Q-learning operate on a finite, fully visible state space. It is also almost never true. A clinician does not observe a patient's true physiological state, only blood tests and vital signs sampled from it. A maintenance system does not observe a machine's true internal wear, only vibration and temperature readings. A trading system does not observe the market's true regime, only prices that are consistent with several regimes at once. In every case the true state is Markov and hidden, the observation is a noisy partial shadow of it, and the agent must act anyway. This section formalizes that situation and gives the agent the one object it needs to cope: a belief over where it probably is.

The thread back to Part II is not a loose analogy; it is an exact equality, and stating it precisely is the spine of this section. In Chapter 7 we studied recursive state estimation: a hidden state evolves by a transition model, emits an observation by an emission model, and a filter maintains a posterior over the hidden state by alternating a predict step (push the posterior through the transition) and an update step (reweight by the new observation via Bayes' rule). The hidden Markov model's forward pass did this for discrete states (Section 7.5); the Kalman filter did it for linear-Gaussian states. A POMDP agent maintains exactly such a posterior, now called a belief, with exactly the same predict-update recursion. The only addition is the action: the agent's chosen $a_t$ enters the transition model, so the agent partly controls the very process it is filtering. The temporal thread of this book reaches one of its sharpest junctions here: the HMM filter of Chapter 7 IS the belief update of the Chapter 23 agent. The estimator became a decision maker.

The four competencies this section installs are these: to recognize when a problem is partially observable and write down its POMDP tuple including the observation model; to define the belief state as a posterior over hidden states and derive its update as a Bayes filter; to state and use the theorem that a POMDP is an MDP over beliefs, and to name why that does not trivially solve the problem; and to implement a discrete belief update from scratch, act greedily on it, then reproduce it with a library updater. These are the foundation for the solution methods of Section 23.2 and every belief-based agent in the rest of Part VI.

1. When the Markov State Is Hidden Beginner

A Markov decision process assumes the agent reads the state $s_t$ off the environment at every step, the way a chess engine reads the board. Partial observability breaks that assumption in the most common way the physical world breaks it: the state is still there, still Markov, still evolving by clean transition rules, but the agent's sensors return only a noisy, lossy function of it. The agent is told a number; the state is a different, hidden thing that the number is merely evidence about. The agent that pretends its observation is the state will, sooner or later, act confidently on a misreading.

It helps to separate two distinct ways an observation can fail to be the state, because a POMDP folds both into one framework. The first is noise: the observation is the state corrupted by a random error, like a thermometer that reads the true temperature plus a small Gaussian jitter. The second is partiality (aliasing): the observation collapses several distinct states into one reading, so the same observation is consistent with more than one underlying state, like a robot in a corridor whose camera sees an identical stretch of wall at three different locations. Noise blurs the state; partiality hides which of several states you are in. Real sensors do both at once, and the belief state is the object that copes with both, because a probability distribution can be spread out by noise and multi-modal under aliasing.

Three running examples, drawn from the book's domains, anchor the abstraction. Consider Figure 23.1.1's depiction of the gap between truth and evidence.

The clinical case: a patient's true state (say, deteriorating, stable, or recovering) is hidden; the observations are blood pressure, heart rate, and lab values, each a noisy and partial readout. The maintenance case: a machine's true wear level is hidden; the observations are a vibration spectrum and a temperature, which a healthy and a mildly worn machine can both produce. The market case: the regime (bull, bear, or choppy) is hidden; the observation is a price move that any regime could have generated on a given day. In all three the right object is not a guessed state but a distribution over states, and the next subsection gives the tuple that defines the problem formally.

There is a subtlety worth flagging before the formalism, because it explains why partial observability is harder than it first looks rather than merely noisier. Under full observability the optimal policy is reactive: a lookup table from the current state to the best action, with no need to remember anything, because the current state already summarizes all of the past that matters (the Markov property of Chapter 22). Partial observability destroys that convenience. The current observation is not Markov: knowing $o_t$ alone does not screen off the past, because earlier observations carry information about the hidden state that $o_t$ does not. A policy that looks only at $o_t$ is therefore provably suboptimal in general, and the optimal policy must, in some form, remember. The belief state is precisely the smallest thing it can remember that restores the Markov property, which is why the rest of the section is organized around constructing it.

One more distinction prevents a common confusion. Partial observability is not the same as a stochastic transition. An MDP can be wildly stochastic and still fully observed: you see exactly which state the dice landed on, you just could not predict it. A POMDP can have perfectly deterministic transitions and still be partially observed: the state evolves with no randomness at all, but you cannot see which deterministic state you are in. The two axes are independent, and a POMDP is the one where uncertainty lives in your knowledge of the present, not only in your prediction of the future. That is exactly the uncertainty a posterior, the belief, is built to represent.

2. The POMDP Tuple Beginner

A POMDP extends the MDP tuple of Chapter 22 with two new components that describe what the agent can perceive. Where an MDP is $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$, a POMDP is the seven-tuple

read as follows. $\mathcal{S}$ is the set of hidden states and $\mathcal{A}$ the set of actions, both as in the MDP. $P(s' \mid s, a)$ is the transition model, the probability the hidden state moves to $s'$ when action $a$ is taken in state $s$, identical to the MDP transition (the world still evolves by a Markov rule). $R(s, a)$ is the reward, a function of the hidden state and action. $\gamma \in [0,1)$ is the discount. The two genuinely new objects are $\mathcal{O}$, the set of possible observations, and $Z$, the observation model

the probability of receiving observation $o$ given that the environment has landed in hidden state $s'$ after action $a$. This $Z$ is precisely the emission model of Chapter 7's HMM, written with an action argument because in a POMDP the sensor's behavior may depend on what the agent just did. The notation $s, a, o, P, Z$ follows the unified symbol table in Appendix A; an MDP is recovered as the special case where $\mathcal{O} = \mathcal{S}$ and $Z(o \mid s', a) = \mathbb{1}[o = s']$, the observation equals the state, full observability restored.

The dynamics unfold in a fixed order each step, and the order matters for the belief update of the next subsection. From hidden state $s_t$ the agent picks $a_t$; the environment transitions to $s_{t+1} \sim P(\cdot \mid s_t, a_t)$ and emits a reward; the agent then receives $o_{t+1} \sim Z(\cdot \mid s_{t+1}, a_t)$; and the cycle repeats. The agent's entire experience is the history $h_t = (a_0, o_1, a_1, o_2, \dots, a_{t-1}, o_t)$, a growing string of its own actions and the observations they elicited. A policy in a POMDP must therefore be a function of this history, not of a state it cannot see, and the central problem of the chapter is that the history grows without bound. The belief state, defined next, is the bounded summary that replaces it.

3. The Belief State and the Bayes-Filter Update Intermediate

The belief state is the agent's probability distribution over the hidden states given everything it has seen. Formally, for a discrete state space, the belief at time $t$ is the vector

a posterior over $\mathcal{S}$ conditioned on the full action-observation history $h_t$. Because the belief is a probability vector summing to one, it lives on the probability simplex over $\mathcal{S}$: for $|\mathcal{S}| = n$ states it is a point in an $(n-1)$-dimensional continuous set. The belief is a sufficient statistic for the history, meaning $b_t$ contains everything in $h_t$ that is relevant to predicting the future and choosing actions; the unbounded history collapses into a fixed-size vector. That is the property that rescues the agent from remembering an ever-growing string.

The belief is maintained recursively, and the recursion is the predict-update cycle of Chapter 7's filtering, now with an action in the predict step. Given the previous belief $b_{t-1}$, the action $a_{t-1}$ just taken, and the new observation $o_t$ just received, the new belief is

Read the formula as two steps stacked. The inner sum $\bar{b}_t(s') = \sum_s P(s' \mid s, a_{t-1})\, b_{t-1}(s)$ is the predict step: push the old belief through the action-conditioned transition to get the prior over the next state before seeing the observation. Multiplying by $Z(o_t \mid s', a_{t-1})$ is the update step: reweight that prior by how likely each candidate state was to have produced the actual observation $o_t$, which is Bayes' rule with the observation likelihood. The denominator is just the normalizer $\Pr(o_t \mid b_{t-1}, a_{t-1})$ that makes the result sum to one. Predict then update, transition then likelihood: this is the HMM forward recursion of Section 7.5 verbatim, with $a_{t-1}$ threaded into $P$ and $Z$. We write $b_t = \tau(b_{t-1}, a_{t-1}, o_t)$ for this deterministic belief-update operator $\tau$, which the next theorem treats as the transition function of a new process.

It is worth pausing on a point that surprises newcomers: the belief update is deterministic even though the world is stochastic. Given a fixed previous belief, a fixed action, and a fixed observation, the formula above returns one specific next belief, with no randomness in it. The randomness has not vanished; it has moved. What is stochastic is which observation $o_t$ arrives, drawn from the belief-predicted distribution $\Pr(o_t \mid b_{t-1}, a_{t-1})$ in the denominator. So the belief evolves deterministically as a function of a random observation, exactly as a Kalman filter's mean and covariance update deterministically given a random measurement. This is the precise sense in which the agent's state of knowledge is a well-defined object even though its state of the world is not: the agent always knows its own belief exactly, it just does not know which state that belief is about.

4. The Belief-MDP Theorem Advanced

The belief update buys a structural result of the first importance. Although the original POMDP is not an MDP (its true state is hidden, so no MDP policy on states is available to the agent), the process the agent actually experiences, the evolution of its belief, IS a Markov decision process. This is the belief-MDP theorem, and it is the reason the entire dynamic-programming and reinforcement-learning machinery of Part VI can be brought to bear on partial observability at all.

Spelled out, the belief MDP has continuous state space $\mathcal{B}$, the probability simplex over $\mathcal{S}$ (each "state" is a belief vector $b$); the same action set $\mathcal{A}$; a transition rule given by the belief update, where taking action $a$ in belief $b$ and receiving observation $o$ moves the agent deterministically to $b' = \tau(b, a, o)$, with the observation drawn according to its belief-predicted probability $\Pr(o \mid b, a) = \sum_{s'} Z(o \mid s', a) \sum_s P(s' \mid s, a)\, b(s)$; and a reward that is the belief-averaged true reward,

the expected reward under the agent's current uncertainty. Because the belief is a sufficient statistic for the history, this belief process is Markov: the next belief depends only on the current belief, the action, and the observation, not on the older history. Therefore an optimal POMDP policy is a function of the belief alone, $\pi^\star: \mathcal{B} \to \mathcal{A}$, and it satisfies the Bellman optimality equation over beliefs,

This is exactly the MDP Bellman equation of Chapter 22 with the belief playing the role of the state. So in principle every method of Part VI, value iteration, policy iteration, Q-learning, policy gradients, transfers directly: just run them on the belief MDP.

The reduction also clarifies a phenomenon that has no analogue in the fully observed world: information-gathering actions. In an MDP every action is taken for its reward and its effect on the next state. In the belief MDP an action additionally changes the agent's uncertainty, because different actions elicit different observations and so sharpen or blur the belief differently. The Bellman equation above accounts for this automatically: the term $\sum_o \Pr(o \mid b, a)\, V^\star(\tau(b, a, o))$ rewards an action partly for the beliefs its observations will produce, so an optimal POMDP agent will sometimes take a low-immediate-reward action purely to see a more informative observation, the formal basis of "look before you leap". A medical agent ordering a diagnostic test, a robot turning to face a landmark, a trading system probing with a small order: all are information-gathering actions, and they fall out of the belief-MDP Bellman equation without any special machinery, because reducing uncertainty raises future value. This is the single most important behavior partial observability adds, and it is invisible to any policy that acts on the raw observation.

The phrase "in principle" carries all the weight, and naming the obstruction precisely is what motivates Section 23.2. The belief MDP's state space is continuous and high dimensional: for $n$ hidden states the belief is a point in an $(n-1)$-dimensional simplex, an uncountable set, so the tabular value iteration of Chapter 22, which enumerates states, cannot be run directly. Worse, the number of distinct beliefs reachable in $t$ steps grows exponentially in $t$ (one per possible observation history), so even tracking the reachable beliefs is expensive. The redeeming structure, exploited heavily in Section 23.2, is that the optimal value function $V^\star(b)$ over the belief simplex is piecewise linear and convex in $b$ for a finite-horizon POMDP, which lets exact solvers represent it with a finite set of hyperplanes (alpha-vectors) and approximate solvers sample a manageable subset of beliefs (point-based methods). The takeaway for this section is the clean conceptual reduction: partial observability is not a different kind of problem, it is an MDP whose state is a belief, and the practical work of the chapter is making that infinite-state MDP tractable.

5. Worked Example: A Belief Update From Scratch, Then a Library Updater Advanced

We now make the belief update executable. The plan mirrors the rest of the book: implement the discrete Bayes-filter belief update by hand in numpy, run it on the tiger-style two-state POMDP, act greedily on the belief, and confirm it reproduces the numeric example exactly; then replace the hand-rolled filter with a library belief updater (the pomdp-py toolkit) and count the lines saved. Code 23.1.1 is the from-scratch version.

import numpy as np

# A two-state machine-health POMDP: states {healthy=0, worn=1}.
states = ["healthy", "worn"]
# Transition under action "operate": rows = from-state, cols = to-state.
P = np.array([[0.9, 0.1],     # healthy -> stays 0.9, wears 0.1
              [0.0, 1.0]])    # worn    -> stays worn
# Observation model Z(o | s'): vibration reads {"low", "high"}.
#   row = hidden state s', col = observation.  high is evidence of wear.
Z = np.array([[0.8, 0.2],     # healthy -> low 0.8, high 0.2
              [0.2, 0.8]])    # worn    -> low 0.2, high 0.8
obs_index = {"low": 0, "high": 1}

def belief_update(b, a_trans, Z, obs):
    """One discrete Bayes-filter belief update: predict through P, reweight by Z(o|.)."""
    b_pred = a_trans.T @ b                    # PREDICT: push belief through transition
    likelihood = Z[:, obs_index[obs]]         # UPDATE: P(o | each next state s')
    b_unnorm = likelihood * b_pred            # Bayes numerator, elementwise
    return b_unnorm / b_unnorm.sum()          # normalize to a valid belief

b = np.array([0.7, 0.3])                       # prior belief
b = belief_update(b, P, Z, "high")            # observe a "high" vibration reading
print("belief after 'high':", np.round(b, 3))

# Act greedily on the belief: a tiny reward model and one-step expected reward.
#   R[s, a] for actions {0: keep running, 1: send to maintenance}.
R = np.array([[ 2.0, -1.0],    # healthy: running pays 2, maintenance wastes 1
              [-5.0,  1.0]])    # worn:    running risks -5, maintenance pays 1
q = b @ R                                       # rho(b,a) = sum_s b(s) R(s,a)
action = ["keep running", "send to maintenance"][int(np.argmax(q))]
print("expected reward per action:", np.round(q, 3), "-> choose:", action)

belief after 'high': [0.299 0.701]
expected reward per action: [-1.005  0.401] -> choose: send to maintenance

Now the library equivalent. The pomdp-py toolkit (Zheng and Tellex, 2020) models the states, the transition and observation distributions, and the belief as first-class objects, and its update_histogram_belief performs the same discrete Bayes filter internally. Code 23.1.2 expresses the identical update through the library and confirms it matches.

import pomdp_py
from pomdp_py.representations.distribution import Histogram

# States, transition, and observation models as pomdp_py objects.
S = [pomdp_py.State(s) for s in ("healthy", "worn")]
class TransitionModel(pomdp_py.TransitionModel):
    def probability(self, sp, s, a):  return float(P[S.index(s), S.index(sp)])
class ObservationModel(pomdp_py.ObservationModel):
    def probability(self, o, sp, a):  return float(Z[S.index(sp), obs_index[o.name]])

prior = Histogram({S[0]: 0.7, S[1]: 0.3})      # same prior belief (0.7, 0.3)
obs = pomdp_py.Observation("high")             # same "high" observation

new_belief = pomdp_py.update_histogram_belief(  # one call: the whole Bayes filter
    prior, action=pomdp_py.Action("operate"), observation=obs,
    observation_model=ObservationModel(), transition_model=TransitionModel())

print("library belief:", {s.name: round(new_belief[s], 3) for s in S})

library belief: {'healthy': 0.299, 'worn': 0.701}

The from-scratch belief filter of Code 23.1.1 was about ten lines of explicit predict, reweight, and normalize; the library version replaces that core with a single update_histogram_belief call, roughly a tenfold reduction in the belief-update code, and what pomdp-py handles internally is exactly the predict-through-transition, reweight-by-observation, renormalize cycle, plus the bookkeeping to scale it to histograms and particle beliefs over large state spaces and to plug straight into the POMDP planners of Section 23.2. Code 23.1.1 teaches you what the filter is; Code 23.1.2 is what you would ship.

To see the belief behave as a memory rather than a single reflex, Code 23.1.3 runs the from-scratch filter over a short stream of observations and prints the belief trajectory. Watch the posterior on "worn" climb monotonically as evidence accumulates, then notice that a single contrary "low" reading dents it only a little: the belief is hard to move once history has piled up behind it, the exact opposite of a memoryless observation-to-label rule.

# Run the belief filter over a stream and watch the posterior evolve.
b = np.array([0.7, 0.3])                        # start: 70% healthy
stream = ["high", "high", "low", "high"]        # four readings over time
print("step  obs   P(healthy)  P(worn)")
for t, o in enumerate(stream, start=1):
    b = belief_update(b, P, Z, o)               # one Bayes-filter step per reading
    print(f"  {t}   {o:4s}    {b[0]:.3f}      {b[1]:.3f}")

step  obs   P(healthy)  P(worn)
  1   high     0.299      0.701
  2   high     0.096      0.904
  3   low      0.275      0.725
  4   high     0.087      0.913