Partial Observability: POMDPs and the Belief State

Every method so far has read the environment's state off the world for free. The Markov decision process handed the agent a state $s$ with the Markov property: the future depends on the past only through the present, so the current state is a sufficient statistic and a policy $π (a ∣ s)$ that looks only at $s$ loses nothing. That assumption does a lot of work, and the frontiers lesson already warned it is usually unrealistic. A camera sees one face of a room; a sonar returns a noisy range; a poker hand hides the opponent's cards. The agent does not receive the state. It receives an observation $o$ — a partial, possibly noisy function of a hidden state it never sees directly.

The moment the observation is not the state, the Markov property breaks at the level of what the agent can act on. Two different hidden states can produce the same observation, and they may require opposite actions. A single observation is no longer enough to decide well, and no policy of the form $π (a ∣ o)$ can recover the performance a state-based policy would get. The fix is to remember the past, because the current observation alone is not enough.

This lesson builds the theory: the POMDP tuple, the belief state that restores the Markov property, and the Bayes-filter update that maintains it. A companion lesson then shows why planning with beliefs is intractable and develops the practical deep-RL answer — recurrent policies that summarize history.

When one observation is not enough

For example, put an agent in a corridor of four cells. Cells $1$ and $3$ look identical from the agent's sensor — both return the observation blank hallway — but from cell $1$ the correct action is to go right and from cell $3$ it is to go left. A reactive policy $π (a ∣ o)$ sees the same $o$ in both and must commit to one action, so it is wrong in one of the two cells no matter what it chooses. This is perceptual aliasing: distinct states aliased onto one observation.

Perceptual aliasing. States

s_{1}

and

s_{3}

emit the same observation

o =

blank, so a policy that sees only

o

cannot tell them apart, yet the optimal action differs (right in

s_{1}

, left in

s_{3}

). One observation is not a Markov signal.

What the reactive policy is missing is how it got there. An agent that arrived at the blank cell by walking right from the entrance is in cell $1$ ; one that arrived by walking left is in cell $3$ . The disambiguating information is in the history of past observations and actions, not in the current observation. The rest of this lesson is about representing that history well enough to act on it.

The POMDP tuple

The formal object is a partially observable Markov decision process. It keeps the entire MDP — a hidden state that does evolve by the Markov property — and inserts an observation layer between that state and the agent.

An MDP is the special case $O = S$ with $Z (o ∣ s^{'}, a) = 1 [o = s^{'}]$ : the observation is the state. Everything hard about a POMDP comes from $Z$ being any less informative than that identity. The generative story is a loop: the hidden state transitions by $T$ , the environment emits an observation by $Z$ , the agent collects a reward $R$ , chooses an action, and the state transitions again — but the $s$ nodes are shaded, unseen.

The POMDP graphical model. The hidden states

s_{t}

(dashed, unobserved) evolve by the transition model

T (s^{'} ∣ s, a)

; each emits an observation

o_{t}

by the observation model

Z (o ∣ s, a)

and a reward

r_{t}

R (s, a)

. The agent sees only the

o_{t}

and

r_{t}

(solid) and chooses actions

a_{t}

; it never sees the

s_{t}

row.

Because the $s_{t}$ row is invisible, the only Markov quantity the agent has direct access to is the whole history

h_{t} ≐ (a_{0}, o_{1}, a_{1}, o_{2}, \dots, a_{t - 1}, o_{t}),

the full record of actions taken and observations seen. The history is Markov — it contains everything the data can tell you — but it grows without bound and never repeats, so a policy or value function indexed by raw history is a table with a fresh row every step. That is useless for learning. We need a compact summary of $h_{t}$ that keeps everything relevant for the future and throws away the rest. The classical answer is the belief state.

The belief state as a sufficient statistic

Since the agent cannot know which hidden state it is in, the most it can hold is a probability distribution over hidden states, given everything it has seen. That distribution is the belief state.

A belief over $∣ S ∣ = n$ states is a point in the $(n - 1)$ -dimensional belief simplex $Δ (S)$ . The corners are the fully-known states (belief $1$ on one state, $0$ elsewhere); the interior points are genuine uncertainty. A three-state POMDP has a triangular simplex, and the agent's belief slides around inside it as evidence arrives.

The belief simplex for three hidden states. Each corner is certainty about one state; the interior is a mixed belief

b = (b (s_{1}), b (s_{2}), b (s_{3}))

summing to

1

. The centroid is maximal uncertainty (uniform belief); an observation moves the belief point toward the corner it favors.

The belief is a sufficient statistic in the precise sense the frontiers lesson defined: any two histories that produce the same belief yield the same distribution over every future observation, and so the same optimal behaviour. That single fact is the reason POMDPs are tractable to state, if not to solve. It lets us replace the ever-growing history with a fixed-length vector and — the key structural result — recast the whole problem as an ordinary MDP.

A POMDP is an MDP over belief states

Consider the process whose state is the belief $b_{t}$ . When the agent takes action $a$ and receives observation $o$ , the belief updates deterministically to a new belief $b^{'}$ (the update rule is next). So the belief follows Markov dynamics: $b_{t + 1}$ depends only on $b_{t}$ , $a_{t}$ , and $o_{t + 1}$ . Define a reward on beliefs by averaging the true reward under the belief, $ρ (b, a) = \sum_{s} b (s) R (s, a)$ , and a belief-transition model by summing over which observation arrives. The result is a genuine MDP.

The belief-MDP equivalence. The unobservable POMDP (top: hidden state

s

, partial observation

o

) is recast as a fully observed MDP (bottom) whose state is the belief

b

. The agent maintains

b

by a Bayes filter and acts by a policy

π (a ∣ b)

; the belief is the Markov state the POMDP lacked.

The equivalence cuts both ways. Solve the belief-MDP and you have solved the POMDP; but the belief-MDP has a continuous state space — the simplex — even when the POMDP had finitely many states, so the tabular machinery of the dynamic-programming chapter does not apply off the shelf. We first need the update that moves $b$ through that simplex.

The belief update: a Bayes filter

The belief update is Bayes' rule applied recursively. Given the current belief $b (s)$ , the action taken $a$ , and the new observation $o$ , the updated belief $b^{'} (s^{'})$ is the posterior over the next hidden state. Two steps: predict the next state by pushing the belief through the transition model, then correct by weighting each candidate next state by how well it explains the observation.

b^{'} (s^{'}) = \frac{Z ( o ∣ s ^{'} , a ) \sum _{s} T ( s ^{'} ∣ s , a ) b ( s )}{Pr ( o ∣ b , a )}, Pr (o ∣ b, a) = s^{'} \sum Z (o ∣ s^{'}, a) s \sum T (s^{'} ∣ s, a) b (s) .

The inner sum $\sum_{s} T (s^{'} ∣ s, a) b (s)$ is the prediction: the probability of landing in $s^{'}$ before seeing anything, obtained by propagating the old belief through the dynamics. Multiplying by $Z (o ∣ s^{'}, a)$ is the correction: reweight each predicted next state by the likelihood it would have produced the observation actually seen. The denominator $Pr (o ∣ b, a)$ is just the normalizer that makes $b^{'}$ sum to one; it also happens to be the probability of that observation, which is useful for scoring. This recursion is the Bayes filter (a.k.a. the forward algorithm for an HMM with actions).

Algorithm:

\textsc{Belief-Update}(b, a, o)

— one Bayes-filter step for a POMDP

1
$\bar b(s') \gets \sum_{s} T(s' \mid s, a)\, b(s)$ for each $s' \in \mathcal{S}$
predict: push belief through dynamics
2
$b'(s') \gets Z(o \mid s', a)\, \bar b(s')$ for each $s' \in \mathcal{S}$
correct: weight by observation likelihood
3
$\eta \gets \sum_{s'} b'(s')$
normalizer = Pr(o given b, a)
4
if $\eta = 0$ then
5
return error
observation impossible under this belief
6
$b'(s') \gets b'(s') / \eta$ for each $s' \in \mathcal{S}$
normalize to a distribution
7
return $b'$

Worked example: the two-state tiger-lite

Take the smallest interesting POMDP. Two hidden states, $s_{L}$ (a hazard behind the left door) and $s_{R}$ (behind the right). One listen action leaves the state unchanged, $T (s ∣ s, listen) = 1$ , but returns a noisy observation: with probability $0.85$ the sound comes from the side that actually holds the hazard, and with probability $0.15$ it is misleading. So $Z (hear-left ∣ s_{L}, listen) = 0.85$ and $Z (hear-left ∣ s_{R}, listen) = 0.15$ .

Start from total ignorance, $b = (0.5, 0.5)$ , and listen. Suppose we hear left. Prediction leaves the belief at $(0.5, 0.5)$ because listening does not move the state. Correction multiplies by the likelihoods:

b^{'} (s_{L}) \propto 0.85 \times 0.5 = 0.425, b^{'} (s_{R}) \propto 0.15 \times 0.5 = 0.075.

Normalizing by $η = 0.5$ gives $b^{'} = (0.85, 0.15)$ . One noisy left moved the belief from $50/50$ to $85%$ confident. Listen again and hear left a second time:

b^{''} (s_{L}) \propto 0.85 \times 0.85 = 0.7225, b^{''} (s_{R}) \propto 0.15 \times 0.15 = 0.0225,

normalizing to $b^{''} \approx (0.970, 0.030)$ . Evidence compounds: two consistent observations drive belief from $0.5$ to $0.97$ . This performs the disambiguation the reactive agent could not — the belief accumulates history into a single vector.

Now inject a conflict. From $b^{''} = (0.970, 0.030)$ , listen a third time and hear right — evidence against the current leaning. The likelihoods flip, $Z (hear-right ∣ s_{L}) = 0.15$ and $Z (hear-right ∣ s_{R}) = 0.85$ :

b^{'''} (s_{L}) \propto 0.15 \times 0.970 = 0.1455, b^{'''} (s_{R}) \propto 0.85 \times 0.030 = 0.0255,

normalizing to $b^{'''} \approx (0.851, 0.149)$ . One conflicting observation moved the belief from $0.97$ down to $0.85$ — it did not reset to $0.5$ , because two prior lefts still outweigh one right. A Bayes filter never discards history; it reweights it. The arithmetic is cleanest in log-odds: each hear-left adds $log (0.85/0.15) \approx 1.735$ to the log-odds of $s_{L}$ and each hear-right subtracts it, so the running log-odds is just (count of left minus count of right) times $1.735$ . After two lefts and one right the net count is $+ 1$ , giving log-odds $1.735$ , and $1/ (1 + e^{- 1.735}) \approx 0.850$ — matching the $b^{'''}$ above exactly. Independent evidence adds in log-odds, so the filter here reduces to a running sum.

Belief trajectory in the two-state tiger-lite. Starting from the uniform belief

b (s_{L}) = 0.5

, each noisy "hear-left" observation applies the Bayes-filter correction and pushes belief toward

s_{L}

: 0.50, then 0.85, then 0.97. A conflicting "hear-right" would pull it back. Belief accumulates evidence one observation at a time.

Where this leaves us

The theory of acting under partial observability is now in place, and it rests on one object. When the agent cannot see the state, the right thing to carry forward is not the last observation but the belief state — the full posterior over hidden states given everything seen so far. The belief is a sufficient statistic for the history: it turns the POMDP back into an ordinary MDP, the belief MDP, whose state is the belief and over which all the machinery of the earlier chapters applies in principle.

Maintaining the belief is mechanical: the Bayes filter updates it each step by predicting through the dynamics and correcting by the new observation's likelihood, as the worked example showed. So in principle partial observability is solved — reduce to the belief MDP and plan.

In practice two obstacles remain. Planning over the belief simplex is computationally expensive (the value function is piecewise-linear-and-convex, with a number of pieces that can explode), and computing the exact belief needs a known model the agent rarely has. Both, and the deep-RL answer that sidesteps them by making the policy a function of history through a recurrent network, continue in Partial Observability: Planning and Recurrent Policies.