Partially observable Markov decision process

Also known as: POMDP

On this page 7

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.

ComponentMeaningTypical form
State space SAll hidden configurations of the environmentFinite set or continuous vector space
Action space AChoices available to the agentDiscrete set or continuous controls
Transition model TProbability of the next state given state and actionT(s’ | s, a)
Reward function RImmediate payoff for an action in a stateR(s, a)
Observation space ΩSignals the agent actually receivesSensor readings, text, images
Observation model OProbability of an observation given the new stateO(o | s’, a)
Discount factor γWeight of future rewardsUsually 0.9 to 0.99
Components of a POMDP

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.

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.

ModelState observableAgent chooses actionsTypical use
Markov decision processYes, fullyYesGames with full information, simulated control
Hidden Markov modelNoNoSpeech recognition, sequence labeling
POMDPNo, through observationsYesRobotics, dialogue, medical decision support
Contextual banditContext only, no state dynamicsYes, one stepRecommendations, ad selection
Decentralized POMDPNo, each agent sees its own viewYes, several agentsMulti-agent coordination
POMDP compared with related sequential models

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.

ApproachCore ideaStrengthLimitation
Exact value iterationEnumerate all alpha vectors over the belief simplexProvably optimalFeasible only for a few states
Point-based value iterationBack up values at sampled belief pointsScales to thousands of statesQuality depends on sampled beliefs
Online tree searchPlan from the current belief with Monte Carlo tree searchHandles large or continuous spacesNeeds a fast simulator at decision time
Recurrent deep RLLearn a policy over histories with recurrent networksWorks without a known modelData-hungry and hard to verify
QMDP heuristicAssume full observability after one stepVery cheap to computeNever takes information-gathering actions
Main families of POMDP solution methods

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.