Partially Observable MDPs (POMDPs)
Advanced material
This is a specialized, graduate-level extension of the core RL curriculum. It assumes you are comfortable with MDPs, the Bellman equation, and Bayesian updates. Read the Markov Decision Processes lesson first.
A standard MDP assumes the agent observes the true state at every step. In the real world this rarely holds — a robot's sensors are noisy, a poker player can't see opponents' cards, a medical agent sees symptoms but not the underlying disease. A Partially Observable MDP (POMDP) models this gap between what is true and what is observed.
The POMDP tuple
A POMDP extends the MDP tuple with two more elements:
- — the set of observations the agent can receive
- — the observation function: probability of seeing observation after taking action and landing in state
The crucial change: the agent never sees directly. It only sees observations , which are a noisy, possibly aliased function of the hidden state.
The belief state
Since the agent can't observe , it maintains a belief state — a probability distribution over all possible states:
The belief is a sufficient statistic of the entire history. After taking action and observing , the belief updates via Bayes' theorem (a forward filter, exactly like the HMM forward algorithm):
where is a normalizing constant ensuring .
The belief-MDP
Here is the key theoretical insight: a POMDP over states is equivalent to a fully observable MDP over belief states. The belief is Markovian — the next belief depends only on the current belief, action, and observation. So we can write a Bellman equation in belief space:
where is the expected reward under the belief.
The catch: the belief space is continuous (a simplex over states), so this MDP has an infinite state space. Exact solutions are intractable for all but tiny problems.
Why POMDPs are hard
- The belief simplex is continuous and high-dimensional.
- Exact value iteration over beliefs is PSPACE-hard.
- The optimal value function is piecewise-linear and convex (PWLC) in the belief — represented as the upper envelope of a set of hyperplanes called α-vectors. The number of α-vectors can grow exponentially with the planning horizon.
Exact solvers
Value iteration with α-vectors: The value function is represented as
Each α-vector corresponds to a conditional plan. Algorithms like Incremental Pruning and Witness maintain a minimal set of α-vectors, but the set still grows quickly.
Approximate solvers
In practice, POMDPs are solved approximately:
| Method | Idea |
|---|---|
| Point-Based Value Iteration (PBVI) | Track α-vectors only at a finite set of sampled belief points, not the whole simplex |
| SARSOP | PBVI variant that samples beliefs reachable from the initial belief under near-optimal policies |
| POMCP / DESPOT | Monte Carlo tree search in belief space using particle filters to represent beliefs |
| Deep RL (DRQN, recurrent policies) | Replace the explicit belief with an RNN hidden state that implicitly summarizes history |
Deep RL connection: recurrent policies
Modern deep RL handles partial observability without explicit belief tracking: feed the observation history into a recurrent network (LSTM/GRU). The hidden state learns to approximate a sufficient statistic of the history — effectively an implicit belief state. DRQN (Deep Recurrent Q-Network) is DQN with an LSTM layer, used when single frames don't reveal the full state (e.g., velocity in Atari from one frame).
When you need a POMDP
- Sensors are noisy or incomplete (robotics, autonomous driving)
- State aliasing: different true states produce identical observations
- Active information gathering matters (the optimal policy may take actions purely to reduce uncertainty, e.g., looking around before acting)
A defining feature of POMDP-optimal behavior: the agent will sometimes sacrifice immediate reward to gather information that improves future decisions — something a plain MDP policy never does.
Related concepts
- Markov Decision Processes: the fully-observable model POMDPs generalize
- Hidden Markov Models: the belief update is the same forward filter
- LSTM & GRU: recurrent policies (DRQN) that replace explicit belief tracking with a hidden state