A partially observable Markov decision process (POMDP) is a mathematical framework for sequential decision making in which an agent cannot observe the true state of its environment directly and must act on noisy or incomplete observations. In reinforcement learning, it generalizes the Markov decision process by adding an observation model, so the agent reasons about a probability distribution over states rather than a single known state.
Most real problems are partially observable: a robot sees only part of a room, a dialogue system cannot read user intent, and a trading agent never sees the full market. The POMDP formalism makes this uncertainty explicit and shows that optimal behavior often includes actions taken purely to gather information.
How a POMDP is defined
A POMDP is usually written as the tuple (S, A, T, R, Ω, O, γ). The first four elements and the discount factor are inherited from an ordinary Markov decision process; the two additions describe what the agent can perceive and how perceptions relate to hidden states.
| Component | Meaning | Typical form |
|---|---|---|
| State space S | All hidden configurations of the environment | Finite set or continuous vector space |
| Action space A | Choices available to the agent | Discrete set or continuous controls |
| Transition model T | Probability of the next state given state and action | T(s’ | s, a) |
| Reward function R | Immediate payoff for an action in a state | R(s, a) |
| Observation space Ω | Signals the agent actually receives | Sensor readings, text, images |
| Observation model O | Probability of an observation given the new state | O(o | s’, a) |
| Discount factor γ | Weight of future rewards | Usually 0.9 to 0.99 |
The Markov property still holds for the hidden state, but not for the observations. A single observation rarely identifies the state, so a policy that maps only the current observation to an action is generally suboptimal. The agent needs a summary of its entire history of actions and observations.
Belief states and belief updating
The standard sufficient summary of history is the belief state, a probability distribution b(s) over all hidden states. After taking action a and receiving observation o, the agent updates its belief with Bayes’ rule: the new probability of each state is proportional to O(o | s’, a) multiplied by the sum over s of T(s’ | s, a) b(s).
This update converts any POMDP into a belief MDP, a fully observable Markov decision process whose states are beliefs. The belief MDP has a continuous state space even when the original problem has only a handful of states, which is the root of the computational difficulty.
For linear Gaussian systems, the belief update is exactly the Kalman filter. For nonlinear or multimodal problems, practitioners use particle filters that approximate the belief with weighted samples. In deep reinforcement learning, a recurrent neural network or transformer often replaces explicit belief tracking with a learned memory of past inputs.
How a POMDP differs from related models
The POMDP is the most general model in a family that differs by what the agent can see and whether it can act. The following table places it among its closest neighbors.
| Model | State observable | Agent chooses actions | Typical use |
|---|---|---|---|
| Markov decision process | Yes, fully | Yes | Games with full information, simulated control |
| Hidden Markov model | No | No | Speech recognition, sequence labeling |
| POMDP | No, through observations | Yes | Robotics, dialogue, medical decision support |
| Contextual bandit | Context only, no state dynamics | Yes, one step | Recommendations, ad selection |
| Decentralized POMDP | No, each agent sees its own view | Yes, several agents | Multi-agent coordination |
A useful way to remember the relationship: a POMDP is a hidden Markov model with actions and rewards, or equivalently an MDP with a noisy sensor placed between the world and the agent.
Solution methods and their trade-offs
Solving a POMDP exactly is computationally intractable for all but tiny problems: finite-horizon planning is PSPACE-complete, and the infinite-horizon problem is undecidable in general. Practical work therefore relies on approximate planners or on learning methods that sidestep explicit beliefs.
A key theoretical result is that the optimal value function over beliefs is piecewise linear and convex for finite horizons. Point-based solvers exploit this by maintaining a set of alpha vectors, each representing the value of a conditional plan, and updating them only at sampled belief points.
| Approach | Core idea | Strength | Limitation |
|---|---|---|---|
| Exact value iteration | Enumerate all alpha vectors over the belief simplex | Provably optimal | Feasible only for a few states |
| Point-based value iteration | Back up values at sampled belief points | Scales to thousands of states | Quality depends on sampled beliefs |
| Online tree search | Plan from the current belief with Monte Carlo tree search | Handles large or continuous spaces | Needs a fast simulator at decision time |
| Recurrent deep RL | Learn a policy over histories with recurrent networks | Works without a known model | Data-hungry and hard to verify |
| QMDP heuristic | Assume full observability after one step | Very cheap to compute | Never takes information-gathering actions |
The QMDP shortcut illustrates the essence of partial observability: by assuming that uncertainty vanishes after the next step, it undervalues information. Genuine POMDP solvers will deliberately choose a sensing action, such as moving a camera or asking a clarifying question, when reducing uncertainty raises expected return.
Practical modeling pitfalls
Most failures in applied POMDP work come from modeling choices rather than solver bugs. The observation model is often guessed rather than measured, and an overconfident sensor model causes the belief to collapse onto a wrong state that later evidence cannot correct.
- Treating observations as states turns a POMDP into a misspecified MDP and produces brittle policies.
- Too large a state space makes belief tracking and planning infeasible; abstraction or factored representations help.
- Frame stacking in deep RL gives only a short fixed memory and fails when relevant information is many steps old.
- Ignoring the cost of information leads to agents that either never explore or sense excessively.
- Particle depletion in particle filters can make the belief lose the true state; resampling and injection of random particles mitigate it.
The short version
A partially observable Markov decision process describes a decision maker who cannot see everything that matters. Instead of knowing the exact situation, it keeps a running best guess with probabilities and updates that guess each time new clues arrive.
Picture walking through a dark house with a flashlight. You do not know exactly where you are, but each glimpse of a door or a staircase makes some rooms more likely. Sometimes the smartest move is not to walk toward the exit but to shine the light around first, because knowing more leads to better choices later.
Where it makes a difference
A warehouse robot must pick a specific item from a shelf where boxes partly hide one another. Its depth camera returns noisy readings, and the item may be in any of four positions. Engineers model the task as a POMDP with hidden item location, actions that include grasping and repositioning the camera, and an observation model estimated from about 2,000 recorded test scans.
An online planner based on Monte Carlo tree search runs from the current belief, which a particle filter maintains with 500 particles. When the belief is split between two positions, the planner chooses to move the camera to a second viewpoint before grasping, because a failed grasp costs several seconds and may knock over neighboring boxes.
Compared with an earlier controller that grasped the most likely position immediately, the POMDP-based robot takes slightly longer per attempt but reduces failed grasps substantially, which raises overall throughput across a full shift.