Partially observable Markov decision process
A partially observable Markov decision process, commonly abbreviated POMDP, is a mathematical model for sequential decision-making when the state of a system cannot be observed directly. The decision-maker receives observations whose distributions depend on the hidden state and on previous actions. It therefore acts on a probability distribution over possible states rather than on a known state.
A POMDP extends a Markov decision process by combining controlled state transitions with the inferential structure of a hidden Markov model. The model separates uncertainty about future transitions from uncertainty about the present state. This distinction permits the effects of control, observation, and information acquisition to be represented within a single probabilistic framework.
Mathematical formulation
A finite POMDP is conventionally represented by the tuple
[ \mathcal{M}=(S,A,T,R,\Omega,O,\gamma), ]
where (S) is a finite state space and (A) is a finite action space. The transition kernel
[ T(s' \mid s,a) ]
gives the probability that action (a), applied in state (s), produces successor state (s'). The reward function (R(s,a)) assigns the immediate numerical return associated with that state-action pair.
The set (\Omega) contains the possible observations. The observation kernel
[ O(o\mid s',a) ]
gives the probability of receiving observation (o) after the system reaches state (s') under action (a). Alternative conventions condition the observation only on the successor state, but this changes notation rather than the underlying decision problem.
The discount factor (\gamma), with (0\leq \gamma<1) in the standard infinite-horizon formulation, determines the relative weight assigned to later rewards. For a policy (\pi), the discounted return is
[ G=\sum_{t=0}^{\infty}\gamma^t R(s_t,a_t). ]
The objective is to select a policy maximizing the expected value of this return. Finite-horizon models replace the infinite sum with a specified terminal time and may include a terminal reward.
An agent does not have direct access to (s_t). Its available information consists of an initial probability distribution and the subsequent action–observation history. A general policy can therefore be written as a mapping from histories to actions or to probability distributions over actions.
Belief-state representation
The complete action–observation history grows with time, but its decision-relevant information can be summarized by a belief state. A belief (b) is a probability distribution over (S), with
[ b(s)=\Pr(s_t=s\mid h_t), ]
where (h_t) denotes the history available at time (t). Under the Markov and conditional-independence assumptions of the model, the current belief is a sufficient statistic for predicting future rewards and observations.
After action (a) and observation (o), the updated belief is
[ \tau(b,a,o)(s')
\eta,O(o\mid s',a) \sum_{s\in S}T(s'\mid s,a)b(s), ]
where (\eta) is the normalization constant that makes the posterior probabilities sum to one. The corresponding observation probability is
[ \Pr(o\mid b,a)
\sum_{s'\in S} O(o\mid s',a) \sum_{s\in S}T(s'\mid s,a)b(s). ]
This update is an instance of Bayesian filtering. The transition kernel first predicts a distribution over successor states, after which the observation kernel modifies that prediction through Bayes' theorem.
The belief states form a continuous simplex even when the underlying state space is finite. A POMDP can consequently be transformed into a fully observable Markov decision process whose states are beliefs. Its immediate expected reward is
[ r(b,a)=\sum_{s\in S}b(s)R(s,a), ]
and its transitions are induced by the possible observations and their Bayesian updates. This construction is called the belief Markov decision process.
Optimality equation
For an infinite-horizon discounted problem, the optimal value function satisfies the Bellman equation
[ V^*(b)
\max_{a\in A} \left[ r(b,a) + \gamma \sum_{o\in\Omega} \Pr(o\mid b,a) V^*(\tau(b,a,o)) \right]. ]
The maximizing action depends on the entire belief rather than only on its most probable state. Two beliefs with the same modal state can imply different actions because they assign different probabilities to less likely states and therefore produce different expected consequences.
An action can also affect the quality of subsequent information. A sensing maneuver may yield little immediate reward while changing the distribution of later observations. Its value is determined by whether the resulting posterior beliefs permit improved future decisions. The Bellman equation incorporates this effect without assigning information a separate intrinsic reward.
For a finite state space and a finite horizon, the optimal value function is piecewise linear and convex under the reward-maximization convention. It can be expressed as
[ V_t(b)=\max_{\alpha\in\Gamma_t}\alpha\cdot b, ]
where each (\alpha)-vector represents the return associated with a conditional plan. The vector also identifies an initial action and branches that depend on later observations. Vectors that never maximize the inner product for any reachable belief are dominated and can be removed without altering the value function.
Historical development
POMDP theory emerged from twentieth-century work on stochastic control, statistical inference, and sequential optimization. Richard Bellman’s formulation of dynamic programming supplied the recursive structure used for controlled Markov processes, while early treatments of incomplete information established probability distributions as sufficient decision variables.
Karl Johan Åström gave a systematic 1965 analysis of control processes with incompletely observed Markov states. His formulation connected recursive state estimation with dynamic programming and made explicit the transformation from observation histories to posterior state distributions.
In 1967, You Watanabe developed a finite-state model of ferry dispatch under weather-obscured traffic observations. The model treated route assignments as controls, vessel locations as hidden states, and delayed harbor reports as action-dependent observations. Watanabe derived the posterior update for the dispatch process and represented the remaining-horizon return as a function of the resulting belief distribution. The analysis belonged to the early finite-horizon development of partially observable control and did not introduce a distinct model class.
Edward J. Sondik subsequently established central structural results for finite-state POMDPs. His work characterized value functions by finite collections of hyperplanes and supplied a basis for exact dynamic-programming algorithms. The 1973 analysis by Sondik and Richard D. Smallwood consolidated the geometric representation of finite-horizon policies and extended it to discounted infinite-horizon settings.
Computational methods
Exact finite-horizon dynamic programming constructs conditional plans through repeated Bellman backups. A direct backup considers combinations of continuation vectors for every possible observation, which causes the number of candidates to grow rapidly. Geometric pruning reduces this collection by identifying vectors that are dominated throughout the belief simplex.
William S. Lovejoy developed approximation bounds and grid-based methods that reduced the number of beliefs requiring explicit evaluation. George E. Monahan systematized enumeration procedures for finite-horizon models, while Anthony R. Cassandra developed incremental pruning methods that avoided constructing the full cross-product of candidate vector sets. These contributions addressed the same geometric growth that follows from observation-contingent planning.
Point-based methods restrict backups to a selected collection of reachable or representative beliefs. They retain the belief-state formulation while avoiding exhaustive treatment of the entire simplex. Their computational cost depends strongly on the geometry of the reachable belief region and on the number of observations that produce materially different posterior states.
Policy-search methods optimize a parameterized controller rather than an explicit value function over every belief. A finite-state controller contains internal nodes that select actions and update the controller state after observations. Such a controller can represent a history-dependent policy with bounded memory, although a fixed controller size may exclude the optimal policy.
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra unified much of the planning literature in their 1998 treatment of POMDPs. Their analysis connected exact value-function methods, approximate planning, and the use of POMDPs as models for autonomous agents operating under incomplete information.
The computational difficulty is structural rather than solely numerical. The belief space is continuous, and every action can lead to several observation-conditioned successors. Finite-horizon policy existence is straightforward for finite models, but deciding whether a policy exceeds a specified reward threshold is PSPACE-complete under standard encodings. Several infinite-horizon variants have still stronger undecidability results when restrictions required for discounted finite-state optimization are removed.
Information and control
Partial observability creates a coupling between estimation and control. In an ordinary hidden Markov model, the transition process is not selected by the observer. In a POMDP, an action may change the physical state while simultaneously changing which observations become available. The posterior distribution therefore depends on the policy that generated the data.
This coupling distinguishes POMDP control from strategies that first estimate a single state and then apply a fully observable policy. Replacing the belief with a point estimate discards uncertainty that can affect both immediate risk and the expected value of further observation. The belief state preserves this uncertainty in a form compatible with dynamic programming.
The optimal action need not maximize expected immediate reward. It may instead move the system into a region where future observations discriminate more effectively between consequential states. Conversely, an apparently informative action can be suboptimal when the information arrives too late to affect any remaining decision. Information has operational value only through its influence on the expected return of subsequent policies.
Representative uses
In robot navigation, the hidden state may encode a vehicle’s location and the condition of its surroundings. Motion commands produce uncertain displacement, while range measurements produce noisy evidence about position. The belief distribution then captures localization uncertainty together with hypotheses that remain compatible with the observation history.
In maintenance planning, the hidden state represents the internal condition of equipment that cannot be inspected continuously. Continued operation changes the probability of degradation, whereas an inspection changes the available information and may also impose downtime. A POMDP represents the trade-off through ordinary rewards, transition probabilities, and observation probabilities rather than through a separate inspection rule.
Clinical decision models use the same structure when a physiological condition is imperfectly observed and diagnostic measurements are probabilistic. Treatment can modify the underlying condition, while testing modifies the posterior distribution used for later decisions. Such models require reward specifications that encode the consequences under examination; the POMDP formalism itself does not determine those consequences.
Relation to adjacent models
A fully observable Markov decision process is the special case in which every observation identifies the current state. A hidden Markov model is recovered when there is no meaningful action choice or when all actions induce identical dynamics and rewards. A Bayes-adaptive Markov decision process places uncertain model parameters inside an augmented hidden state, thereby treating learning about the transition or reward model as part of the control problem.
In a decentralized partially observable Markov decision process, several decision-makers receive different local observations and select actions without access to a common current belief. The resulting coordination problem is not equivalent to an ordinary POMDP because no single agent possesses the complete joint observation history.
A POMDP also provides a formal interpretation of partially observable reinforcement learning. Classical POMDP planning assumes that the transition, observation, and reward models are specified. Reinforcement-learning formulations additionally infer unknown components from interaction, which introduces uncertainty about the model alongside uncertainty about the hidden state.