---
title: "Partial Observability: POMDPs and the Belief State"
module: Modern Deep Reinforcement Learning
moduleNumber: 5
lessonNumber: 18
order: 518
summary: >
  Drop the assumption that the agent sees the state. It sees an observation, a
  partial and noisy function of a hidden state, and one observation is no longer a
  Markov signal. This lesson builds the POMDP tuple, shows that the belief state —
  the posterior over hidden states — is a sufficient statistic that turns a POMDP
  back into an MDP over beliefs, and works the Bayes-filter belief update step by
  step. A companion lesson explains why exact planning is intractable and develops
  the deep-RL answer of recurrent, history-based policies.
topics: [Deep RL]
sources:
  - book: Sutton & Barto
    ref: "Ch. 17 — Frontiers; §17.3 Observations and State (history, Markov state, belief state)"
  - book: Grokking Deep RL
    ref: "Ch. 12 — partial observability and recurrent agents"
---

Every method so far has read the environment's **state** off the world for free. The
[Markov decision process](/reinforcement-learning/foundations/markov-decision-processes)
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
$\pi(a \mid s)$ that looks only at $s$ loses nothing. That assumption does a lot of
work, and the [frontiers lesson](/reinforcement-learning/deep-rl/frontiers) 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 $\pi(a \mid 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](/reinforcement-learning/modern-deep-rl/partial-observability-pomdps-part-2)
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 $\pi(a \mid 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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\small,
  cell/.style={draw, minimum width=13mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[cell] (c1) at (0,0)   {s1};
  \node[cell] (c2) at (1.6,0) {s2};
  \node[cell] (c3) at (3.2,0) {s3};
  \node[cell, draw=acc, text=acc] (c4) at (4.8,0) {goal};
  % observations below
  \node[anchor=north, font=\scriptsize, text=black] at (0,-0.75)   {o = blank};
  \node[anchor=north, font=\scriptsize, text=black] at (1.6,-0.75) {o = wall};
  \node[anchor=north, font=\scriptsize, text=black] at (3.2,-0.75) {o = blank};
  \node[anchor=north, font=\scriptsize, text=acc]   at (4.8,-0.75) {o = goal};
  % aliasing bracket
  \draw[red, thick] (0,0.85) -- (0,1.05) -- (3.2,1.05) -- (3.2,0.85);
  \node[red, anchor=south, font=\scriptsize] at (1.6,1.05) {same observation, opposite best action};
  % desired actions
  \node[acc, anchor=north, font=\scriptsize] at (0,-1.35)   {act: right};
  \node[acc, anchor=north, font=\scriptsize] at (3.2,-1.35) {act: left};
\end{tikzpicture}
$$

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.

> **Definition (POMDP).** A partially observable Markov decision process is a tuple
> $(\mathcal{S}, \mathcal{A}, \mathcal{O}, T, Z, R, \gamma)$: a set of hidden states
> $\mathcal{S}$, actions $\mathcal{A}$, observations $\mathcal{O}$; a transition model
> $T(s' \mid s, a) = \Pr\{s_{t+1} = s' \mid s_t = s, a_t = a\}$; an **observation model**
> $Z(o \mid s', a) = \Pr\{o_{t+1} = o \mid s_{t+1} = s', a_t = a\}$; a reward
> $R(s, a)$; and a discount $\gamma \in [0, 1)$. The agent chooses actions but observes
> only $o$, never $s$.

An MDP is the special case $\mathcal{O} = \mathcal{S}$ with $Z(o \mid s', a) =
\mathbf{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.

$$
% caption: The POMDP graphical model. The hidden states $s_t$ (dashed, unobserved)
% evolve by the transition model $T(s' \mid s, a)$; each emits an observation $o_t$
% by the observation model $Z(o \mid s, a)$ and a reward $r_t$ by $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.
\begin{tikzpicture}[>=stealth, font=\small,
  hid/.style={circle, draw, dashed, minimum size=9mm, inner sep=0pt, font=\footnotesize},
  obs/.style={circle, draw, minimum size=9mm, inner sep=0pt, font=\footnotesize},
  act/.style={rectangle, draw, minimum size=7mm, inner sep=1pt, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % hidden state row
  \node[hid] (s0) at (0,2.0)   {s(t)};
  \node[hid] (s1) at (3.4,2.0) {s+1};
  \node[hid] (s2) at (6.8,2.0) {s+2};
  \draw[->, black, thick] (s0) -- (s1) node[midway, above, font=\scriptsize, text=black] {T};
  \draw[->, black, thick] (s1) -- (s2) node[midway, above, font=\scriptsize, text=black] {T};
  % observation row
  \node[obs, draw=acc, text=acc] (o0) at (0,0)   {o(t)};
  \node[obs, draw=acc, text=acc] (o1) at (3.4,0) {o+1};
  \node[obs, draw=acc, text=acc] (o2) at (6.8,0) {o+2};
  \draw[->, acc, thick] (s0) -- (o0) node[midway, right, font=\scriptsize, text=black] {Z};
  \draw[->, acc, thick] (s1) -- (o1) node[midway, right, font=\scriptsize, text=black] {Z};
  \draw[->, acc, thick] (s2) -- (o2) node[midway, right, font=\scriptsize, text=black] {Z};
  % action nodes feeding transitions
  \node[act] (a0) at (1.7,3.3) {a(t)};
  \node[act] (a1) at (5.1,3.3) {a+1};
  \draw[->, black] (a0) -- (s1);
  \draw[->, black] (a1) -- (s2);
  % reward markers
  \node[red, anchor=west, font=\scriptsize] at (0.55,1.0) {r = R(s,a)};
  \node[anchor=north, font=\scriptsize, text=black] at (3.4,-0.7) {agent sees only this row};
  \node[anchor=east, font=\scriptsize, text=black, align=right] at (-0.65,2.4) {hidden state\\(unobserved)};
\end{tikzpicture}
$$

Because the $s_t$ row is invisible, the only Markov quantity the agent has direct
access to is the whole **history**

$$
h_t \;\doteq\; (a_0, o_1, a_1, o_2, \ldots, 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**.

> **Definition (Belief state).** The belief $b_t(s) = \Pr\{s_t = s \mid h_t\}$ is the
> posterior probability that the hidden state is $s$, given the history $h_t$. It is a
> vector on the probability simplex over $\mathcal{S}$: $b_t(s) \ge 0$ and
> $\sum_s b_t(s) = 1$. The belief is a **sufficient statistic** for the history — it
> carries everything in $h_t$ that is relevant to predicting the future and choosing
> actions.

A belief over $|\mathcal{S}| = n$ states is a point in the $(n-1)$-dimensional
**belief simplex** $\Delta(\mathcal{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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % triangle corners
  \coordinate (A) at (0,0);
  \coordinate (B) at (5.0,0);
  \coordinate (C) at (2.5,4.0);
  \draw[black, thick] (A) -- (B) -- (C) -- cycle;
  \node[anchor=north east, font=\footnotesize] at (A) {b(s1) = 1};
  \node[anchor=north west, font=\footnotesize] at (B) {b(s2) = 1};
  \node[anchor=south, font=\footnotesize] at (C) {b(s3) = 1};
  % centroid (uniform)
  \coordinate (M) at (2.5,1.33);
  \fill[black] (M) circle (2pt);
  \node[anchor=north, font=\scriptsize, text=black] at (2.5,1.2) {uniform};
  % a belief point
  \coordinate (P) at (1.7,1.9);
  \fill[acc] (P) circle (2.4pt);
  \node[acc, anchor=west, font=\scriptsize] at (1.85,1.75) {belief b};
  % observation moves it
  \coordinate (Q) at (1.05,2.7);
  \draw[->, red, thick] (P) -- (Q);
  \node[red, anchor=west, font=\scriptsize] at (0.6,3.05) {after observation o};
\end{tikzpicture}
$$

The belief is a sufficient statistic in the precise sense the
[frontiers lesson](/reinforcement-learning/deep-rl/frontiers) 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, $\rho(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.

> **Theorem (Belief-MDP equivalence).** A POMDP $(\mathcal{S}, \mathcal{A}, \mathcal{O},
> T, Z, R, \gamma)$ is equivalent to a fully observable MDP whose state space is the
> belief simplex $\Delta(\mathcal{S})$, with reward $\rho(b, a) = \sum_s b(s) R(s, a)$
> and Markov belief-transition dynamics driven by $(a, o)$. An optimal policy for the
> belief-MDP, $\pi^\ast(a \mid b)$, is optimal for the POMDP.

$$
% caption: 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
% $\pi(a \mid b)$; the belief is the Markov state the POMDP lacked.
\begin{tikzpicture}[>=stealth, font=\small,
  box/.style={draw, minimum width=22mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % POMDP row
  \node[box, dashed] (hs) at (0,1.4) {hidden state s\\(unobserved)};
  \node[box] (ob) at (4.4,1.4) {observation o};
  \node[box] (ag) at (8.8,1.4) {agent};
  \draw[->, black, thick] (hs) -- (ob) node[midway, above, font=\scriptsize, text=black] {Z};
  \draw[->, black, thick] (ob) -- (ag);
  \node[anchor=west, font=\scriptsize, text=black] at (-2.6,1.4) {POMDP:};
  % belief row
  \node[box, draw=acc, text=acc, thick] (bf) at (2.2,-1.2) {Bayes f\/ilter\\update b};
  \node[box, draw=acc, text=acc, thick] (be) at (6.6,-1.2) {policy\\pi(a given b)};
  \draw[->, acc, thick] (bf) -- (be) node[midway, above, font=\scriptsize, text=black] {belief b};
  \node[anchor=west, font=\scriptsize, text=black] at (-2.6,-1.2) {belief-MDP:};
  % observation feeds the filter
  \draw[->, red, thick] (ob.south) .. controls (4.4,-0.2) and (2.2,-0.1) .. (bf.north)
    node[midway, right, font=\scriptsize, text=red] {o, a in};
\end{tikzpicture}
$$

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](/reinforcement-learning/tabular-methods/dynamic-programming)
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 \mid s', a)\;\sum_{s} T(s' \mid s, a)\, b(s)}{\Pr(o \mid b, a)},
\qquad
\Pr(o \mid b, a) \;=\; \sum_{s'} Z(o \mid s', a) \sum_{s} T(s' \mid s, a)\, b(s).
$$

The inner sum $\sum_s T(s' \mid 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 \mid 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 \mid 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
caption: $\textsc{Belief-Update}(b, a, o)$ — one Bayes-filter step for a POMDP
$\bar b(s') \gets \sum_{s} T(s' \mid s, a)\, b(s)$ for each $s' \in \mathcal{S}$ // predict: push belief through dynamics
$b'(s') \gets Z(o \mid s', a)\, \bar b(s')$ for each $s' \in \mathcal{S}$ // correct: weight by observation likelihood
$\eta \gets \sum_{s'} b'(s')$ // normalizer = Pr(o given b, a)
if $\eta = 0$ then
  return error // observation impossible under this belief
$b'(s') \gets b'(s') / \eta$ for each $s' \in \mathcal{S}$ // normalize to a distribution
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 \mid s, \text{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(\text{hear-left} \mid s_L, \text{listen}) =
0.85$ and $Z(\text{hear-left} \mid s_R, \text{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, \qquad
b'(s_R) \propto 0.15 \times 0.5 = 0.075.
$$

Normalizing by $\eta = 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, \qquad
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(\text{hear-right}
\mid s_L) = 0.15$ and $Z(\text{hear-right} \mid s_R) = 0.85$:

$$
b'''(s_L) \propto 0.15 \times 0.970 = 0.1455, \qquad
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
"left"s 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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (7.4,0) node[anchor=north, font=\footnotesize, text=black] {listen steps};
  \draw[->, black] (0,0) -- (0,4.0) node[anchor=south, font=\footnotesize, text=black, rotate=90, xshift=-16mm, yshift=8mm] {belief b(sL)};
  % gridline at 0.5 and 1.0
  \draw[black, dashed] (0,1.75) -- (7.2,1.75);
  \node[anchor=east, font=\scriptsize, text=black] at (-0.15,1.75) {0.5};
  \draw[black, dashed] (0,3.5) -- (7.2,3.5);
  \node[anchor=east, font=\scriptsize, text=black] at (-0.15,3.5) {1.0};
  \node[anchor=east, font=\scriptsize, text=black] at (-0.15,0) {0};
  % points: (0,0.50) (1,0.85) (2,0.97)
  \coordinate (p0) at (0.6,1.75);
  \coordinate (p1) at (3.4,2.975);
  \coordinate (p2) at (6.2,3.395);
  \draw[acc, very thick] (p0) -- (p1) -- (p2);
  \fill[acc] (p0) circle (2.4pt);
  \fill[acc] (p1) circle (2.4pt);
  \fill[acc] (p2) circle (2.4pt);
  \node[acc, anchor=north west, font=\scriptsize] at (0.6,1.7) {0.50};
  \node[acc, anchor=north west, font=\scriptsize] at (3.4,2.95) {0.85};
  \node[acc, anchor=south, font=\scriptsize] at (6.2,3.5) {0.97};
\end{tikzpicture}
$$

## 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](/reinforcement-learning/modern-deep-rl/partial-observability-pomdps-part-2).