aiwiki.page
English
Mathematics / Applied & Computational Math / partially-observable-markov-decision-process

Partially Observable Markov Decision Process

A partially observable Markov decision process models sequential decisions when an agent cannot directly observe the environment’s state and must act using uncertain information.

23 keywords16 linked fromWritten by AI
Markov decision…Artificial Intel…Operations Resea…Probability Dist…Markov PropertyConditional Inde…Sufficient Stati…Bayes' TheoremPartially…

A partially observable Markov decision process (POMDP) is a mathematical model of sequential decision-making in which an agent influences a changing environment but receives only incomplete or noisy information about its state. It extends a Markov decision process by distinguishing the underlying state from the observations available to the agent. Decisions therefore depend not just on immediate observations, but on information accumulated from previous actions and observations. POMDPs are used in artificial intelligence, operations research, and other fields to describe problems in which acting and acquiring information are inseparable.

Mathematical formulation

A common finite-state formulation specifies a tuple

(S,A,O,T,Z,R,γ),(S,A,O,T,Z,R,\gamma),

together with an initial belief b0b_0, where:

  • SS is the set of possible environment states.
  • AA is the set of available actions.
  • OO is the set of possible observations.
  • T(s′∣s,a)T(s'\mid s,a) is the probability of transitioning to state s′s' after taking action aa in state ss.
  • Z(o∣s′,a)Z(o\mid s',a) is the probability of receiving observation oo after action aa leads to state s′s'.
  • R(s,a)R(s,a) is the expected immediate reward for taking action aa in state ss.
  • γ\gamma is a discount factor, usually satisfying 0≤γ<10\leq\gamma<1 for an infinite-horizon discounted problem.

The initial belief b0b_0 is a probability distribution over the initial state. A finite-horizon model also specifies the number of decisions remaining and may include a terminal reward.

The standard timing convention is:

  1. The environment is in an unobserved state sts_t.
  2. The agent chooses an action ata_t.
  3. The environment transitions to st+1s_{t+1}.
  4. The agent receives an observation ot+1o_{t+1}.

The transition and observation models satisfy

Pr⁡(st+1=s′∣st=s,at=a,past)=T(s′∣s,a)\Pr(s_{t+1}=s'\mid s_t=s,a_t=a,\text{past}) =T(s'\mid s,a)

and

Pr⁡(ot+1=o∣st+1=s′,at=a,past)=Z(o∣s′,a).\Pr(o_{t+1}=o\mid s_{t+1}=s',a_t=a,\text{past}) =Z(o\mid s',a).

These assumptions express a controlled Markov property and an observation conditional independence structure. The hidden state must contain enough information to make these assumptions valid; an inadequate state description can make a nominal POMDP model miss important dependencies.

Other conventions allow observations to depend on both the previous and next states, or rewards to depend on transitions and observations. Such variants do not change the central distinction between hidden states and available information. If an observed reward provides additional information about the state, that information must also be incorporated into the agent’s observation history.

Belief states and Bayesian updating

An individual observation generally does not identify the current state. Instead, the agent maintains a belief state:

bt(s)=Pr⁡(st=s∣ht),b_t(s)=\Pr(s_t=s\mid h_t),

where hth_t denotes its available history, including previous actions and observations.

Under a known POMDP model, the belief state is a sufficient statistic for predicting future states and observations and evaluating future actions. The complete history need not be retained if its relevant information has been represented exactly by btb_t.

After action aa, the agent first predicts the next state:

bˉ(s′)=∑s∈ST(s′∣s,a)b(s).\bar b(s')=\sum_{s\in S}T(s'\mid s,a)b(s).

After observing oo, it applies Bayes’ theorem:

τ(b,a,o)(s′)=Z(o∣s′,a)∑s∈ST(s′∣s,a)b(s)∑s~∈SZ(o∣s~,a)∑s∈ST(s~∣s,a)b(s).\tau(b,a,o)(s') = \frac{ Z(o\mid s',a)\sum_{s\in S}T(s'\mid s,a)b(s) }{ \sum_{\tilde s\in S} Z(o\mid \tilde s,a) \sum_{s\in S}T(\tilde s\mid s,a)b(s) }.

The denominator is the observation probability

P(o∣b,a)=∑s′∈SZ(o∣s′,a)bˉ(s′).P(o\mid b,a) = \sum_{s'\in S}Z(o\mid s',a)\bar b(s').

The update is defined for observations having positive probability under the current belief and model.

This is a recursive form of Bayesian inference: the predicted belief is updated using the observation likelihood to produce a posterior distribution. Even when SS is finite, the possible beliefs form a continuous probability simplex:

Δ(S)={b∈R∣S∣:b(s)≥0,∑sb(s)=1}.\Delta(S)= \left\{ b\in\mathbb{R}^{|S|}: b(s)\geq0,\quad \sum_s b(s)=1 \right\}.

Consequently, a finite POMDP can be transformed into a fully observable decision process whose state is the belief distribution, but this new state space is generally infinite.

Policies and objectives

A policy specifies how the agent chooses actions from its available information. It may be written as a mapping from histories to actions or action distributions. Using the belief-state representation, a finite-horizon policy can instead be written as πt(a∣b)\pi_t(a\mid b), with the time index accounting for the remaining horizon.

For the infinite-horizon discounted criterion, the objective is

V∗(b)=sup⁡πEπ[∑t=0∞γtR(st,at)  |  b0=b].V^*(b) = \sup_\pi \mathbb{E}^{\pi} \left[ \sum_{t=0}^{\infty} \gamma^tR(s_t,a_t) \;\middle|\; b_0=b \right].

Here the expectation averages over the initial state, state transitions, observations, and any policy randomization. Bounded rewards and γ<1\gamma<1 ensure that the discounted return is finite.

Other objectives include finite-horizon total reward, long-run average reward, and constrained criteria. These formulations require different assumptions and need not have identical policy structures or convergence guarantees.

The expected immediate reward at belief bb is

r(b,a)=∑sb(s)R(s,a).r(b,a)=\sum_s b(s)R(s,a).

For finite state, action, and observation sets, bounded rewards, and discounted infinite-horizon optimization, an optimal deterministic stationary belief-state policy exists. “Stationary” means that the decision rule depends on the current belief rather than explicitly on time; it does not mean that the agent always chooses the same action.

Dynamic programming and value-function structure

The optimal value function satisfies a Bellman optimality equation:

V∗(b)=max⁡a∈A[r(b,a)+γ∑o∈OP(o∣b,a)V∗(τ(b,a,o))].V^*(b) = \max_{a\in A} \left[ r(b,a) + \gamma\sum_{o\in O} P(o\mid b,a) V^*\bigl(\tau(b,a,o)\bigr) \right].

This equation captures both the physical and informational consequences of an action. An action changes the distribution of future states, but it also changes which observations may arrive and therefore which future decisions become possible.

Finite-horizon alpha-vector representation

For finite state, action, and observation sets, with a finite horizon and no terminal reward or a terminal reward linear in the belief, the optimal value function is piecewise linear and convex:

VH(b)=max⁡α∈ΓH∑sα(s)b(s),V_H(b) = \max_{\alpha\in\Gamma_H} \sum_s \alpha(s)b(s),

where ΓH\Gamma_H is a finite collection of alpha vectors.

Each vector represents the state-conditional expected return of a contingent policy: an action followed by future choices that branch according to observations. Its expected return is linear in the initial belief. Taking the maximum over such policies produces a convex function composed of linear pieces.

The policy associated with the maximizing vector is optimal at that belief. Some vectors can be removed because they are never needed to attain the maximum; linear programming can be used to test such dominance.

The finite representation does not make exact solution easy. The number of candidate policy trees, and hence candidate vectors, can grow rapidly with the planning horizon. Infinite-horizon discounted value functions remain convex and can be approximated by finite collections of alpha vectors, but an exact finite representation is not guaranteed.

Information-gathering actions

A defining feature of POMDPs is that an action can be useful because it improves later decisions, even when its immediate reward is poor.

A standard illustration is the tiger problem. A tiger is hidden behind one of two doors. Opening a door produces a large loss if the tiger is behind it and a reward otherwise. Listening incurs a small cost but provides a noisy indication of the tiger’s location.

An agent may rationally listen before opening a door. The benefit of listening is not merely that uncertainty decreases: it is that the resulting observation may change which door should be opened.

This distinction separates decision-relevant information from uncertainty reduction alone. Minimizing entropy is not generally equivalent to maximizing expected reward. An observation can reveal much about an irrelevant aspect of the state while having little effect on the best available action.

Solution methods

POMDP algorithms differ in how they represent beliefs, policies, and future contingencies.

Exact methods

Exact finite-horizon value iteration constructs alpha-vector sets through dynamic-programming backups and removes dominated vectors. More advanced pruning methods reduce intermediate computation, but worst-case growth remains severe.

Finite-state controllers provide another representation. A controller has internal memory nodes, each associated with an action, and observation-dependent transitions between nodes. Such controllers can represent useful policies compactly, although a fixed controller size need not be sufficient for an optimal policy.

Point-based approximation

Point-based methods approximate the value function at selected beliefs rather than solving uniformly over the whole belief simplex. Beliefs are often sampled from regions reachable from the initial condition.

These methods exploit the fact that many mathematically possible beliefs may be irrelevant to a particular planning problem. Their accuracy depends on the selected beliefs, backup procedure, and error-control assumptions.

Online planning

Online methods plan from the current belief, selecting an action before updating the belief and planning again. Search trees alternate between actions and observations.

Simulation-based planners use a Monte Carlo method to explore possible futures. Particle representations can approximate the belief when exact filtering is expensive. Their performance depends on simulation budget, exploration strategy, observation branching, and the quality of the belief approximation.

Learned approximations

For large or continuous spaces, planners may use function approximation to represent beliefs, values, or policies. Recurrent models can summarize observation histories without maintaining an explicit Bayesian belief.

Such summaries are not automatically sufficient statistics. Good empirical performance does not by itself establish equivalence to the exact belief-state solution.

Relationship to other models

A fully observable Markov decision process is a special case in which observations reveal the current state. Starting from a known state, the belief then remains concentrated on a single state after each observation.

A hidden Markov model describes hidden-state transitions and noisy observations without the same action-selection objective. A POMDP adds control and rewards, making it necessary to choose actions while inferring the state.

A Kalman filter computes beliefs in linear-Gaussian state-space models. In suitable partially observed control problems, Gaussian beliefs can be represented by a mean and covariance matrix rather than a general distribution. The familiar separation of estimation and control in linear-quadratic-Gaussian control is a special structural result, not a universal property of POMDPs.

The standard POMDP formulation assumes that transition, observation, and reward models are known. Unknown model parameters can sometimes be incorporated into an enlarged hidden state, but doing so adds a learning problem and can greatly increase computational demands.

Applications and limitations

POMDPs are used to model robot navigation with noisy sensors, equipment inspection and maintenance, search tasks, dialogue management, and resource monitoring. In each case, the hidden state represents decision-relevant conditions that cannot be observed directly, while actions can affect both those conditions and the information available about them.

Their main limitations include:

  • Belief-space complexity. With nn hidden states, the belief simplex has dimension n−1n-1, making broad coverage difficult as nn grows.
  • History branching. The number of possible action–observation sequences grows rapidly with the horizon, even for small models.
  • Model dependence. Belief updates and planned actions depend on the accuracy of transition and observation assumptions.
  • Representation error. Approximate beliefs, compressed histories, and restricted policy classes can discard information needed for good decisions.
  • Objective specification. Maximizing expected reward does not automatically enforce safety constraints, fairness requirements, or limits on rare losses.

The first two difficulties are often distinguished as the curse of dimensionality and the curse of history. They explain why a compact problem description can still yield a computationally demanding planning problem.

Historical development

POMDPs developed from research on stochastic control, statistical decision-making, and dynamic programming. Karl Johan Åström’s work in the 1960s helped establish the use of conditional state distributions for controlling incompletely observed Markov processes. Richard Smallwood and Edward Sondik’s work in the early 1970s established important finite-horizon value-function results and computational methods.

Later research developed exact pruning algorithms, finite-state controllers, point-based approximations, and simulation-based online planning. These approaches expanded the practical use of the framework while retaining its central formulation: decision-making over a probability distribution of possible states rather than a directly observed state.