Partially observable Markov decision process (POMDP)

Overview

An agent acts in a world whose state it cannot see. Its actions have uncertain effects and its observations are noisy. A POMDP describes this problem with states, actions, observations, a transition function, an observation function and a reward function 2107.07599 §2. The agent cannot plan over states, so it plans over beliefs: probability distributions over states that it updates with Bayes' rule after each action and observation 2107.07599 §2 2107.07599 eq. 2.

The core difficulty is that the optimal policy over beliefs is intractable in general (PSPACE-hard) 2107.07599 §3. Every variant below therefore trades optimality for a tractable approximation. The shared invariant is that the policy is a function of the belief, not of the last observation alone 2107.07599 §4.3. The sampling-based solvers do not guarantee an optimal policy 2107.07599 §1 2107.07599 §3.

The main source is a review of POMDP planning for robotics. It reports no experiments of its own; all numbers are quoted from cited work 2107.07599 §3.1 2107.07599 §4.3. Card: Partially Observable Markov Decision Processes (POMDPs) and Robotics. A second survey uses the same formalism to model what other agents know and intend; it is covered in its own section below 2601.02378 §2.1. A third source trains a learned policy under partial observation with no belief model; see the section on partial observation without a belief below 2409.03930 §3.2.

Variants

The review groups solver ideas by the five difficulties they address 2107.07599 §3. Each entry below names the difficulty it targets.

Offline point-based solvers (large state space)

These compute a policy before execution by backing up values at a sampled set of beliefs 2107.07599 §3.1. Card: Partially Observable Markov Decision Processes (POMDPs) and Robotics.

• PBVI: one alpha-vector per sampled belief, point-based backups only. The belief set grows by one-step simulation, keeping the successor farthest from the set under the L1 metric 2107.07599 §3.1.
• Perseus: separates belief sampling from backup and backs up only a subset of the sampled beliefs, which keeps fewer vectors 2107.07599 §3.1.
• HSVI2: keeps lower and upper bounds. The upper bound starts from the fully observable MDP and uses sawtooth interpolation; sampling walks down a belief tree 2107.07599 §3.1.
• SARSOP: samples beliefs close to those reachable under an optimal policy, predicts values of new beliefs from binned features, and prunes suboptimal branches 2107.07599 §3.1.
• PBPI: point-based backup applied to policy iteration, with the policy stored as a finite state controller 2107.07599 §3.1.

Continuous-state extensions

For continuous states the review lists a point representation with k-nearest-belief averaging under KL divergence, alpha-functions with Gaussian mixtures, policy graphs (MCVI) and guided cluster sampling (GCS) 2107.07599 §3.1.

Online tree search (large state space, real-time planning)

These plan only from the current belief at each step, interleaved with execution 2107.07599 §3 2107.07599 §3.1.

• POMCP: UCT-style Monte Carlo tree search over histories, with a generative model and particle beliefs 2107.07599 §3.1.
• ABT: backs up values along the tree and reuses earlier trees 2107.07599 §3.1.
• DESPOT: builds a sparse tree from a fixed number K of sampled scenarios 2107.07599 §3.1.
• RTDP-Bel: one-step lookahead with heuristics over a hash table of belief values 2107.07599 §3.1.

Long horizon: macro-actions (§3.2)

Temporally extended sub-policies that run until a termination condition. Hand-designed sub-goals are common; automatic constructions include milestone-based open-loop sequences, LQG-based macro-actions over a probabilistic roadmap for Gaussian beliefs, and value-of-information macro-actions with bounded regret 2107.07599 §3.2.

Large observation space (§3.3)

Offline: cluster observations by value-function features, or extend policy graphs with classification 2107.07599 §3.3. Online: progressive widening (POMCPOW), which adds observations incrementally and needs an explicit observation function, and lazy belief extraction (LABECOP) 2107.07599 §3.3.

Large action space (§3.4)

Most solvers enumerate actions and handle at most about 100 discrete actions 2107.07599 §3.4. Remedies are sampled maxima over random action subsets (Perseus, GCS), GPS-ABT, Bayesian optimisation with Gaussian processes (usually below 4 action dimensions), LQG for linear-Gaussian cases, and a two-stage quantile-based sampler for very large discrete action sets 2107.07599 §3.4.

Complex dynamics (§3.5)

Solvers assume that forward simulation is nearly free. When dynamics require solving differential equations, remedies are a hybrid switching model with an offline solver, linearised dynamics with LQR, and multilevel Monte Carlo, which uses the expensive model rarely and cheaper models otherwise 2107.07599 §3.5.

Use in world models and social reasoning

A survey of Theory of Mind for embodied agents writes its physical world model as a POMDP-style tuple whose state holds only physical attributes, with transitions that depend only on physical actions 2601.02378 §2.1 2601.02378 tab. 1. Its mental world model extends that state with the agent's memory and introspective observations, and memory is written from world states and actions by a memory function 2601.02378 §2.1. For several agents, the survey extends the model to a Dec-POMDP, in which each agent's policy depends on its own memory and observations. It describes Theory of Mind there as inferring other agents' states from their actions [arxiv:2601.02378 §2.1].

Model-based inference in that survey rests on the assumption that behaviour is optimal planning towards a goal. Intentions are then inferred by working backwards from observed behaviour 2601.02378 §4.2. The survey gives no algorithm and no experiments for these models, so the belief-update and solver sections above do not transfer to them without the original papers 2601.02378 §4.2. Card: Modeling the Mental World for Embodied AI: A Comprehensive Review.

Partial observation without a belief

Some learned controllers act under partial observation but never maintain a belief. The drone paper trains its policy with PPO and an asymmetric actor-critic: the critic gets privileged state during training, and the actor gets only observations at deployment 2409.03930 §3.2. The policy maps observation histories to action distributions, and the card records no belief or belief update 2409.03930 §3.2. The belief-update and solver sections above therefore do not apply to it. Its reported gains are over Q-learning, DQN and Sarsa in simulation, not over POMDP solvers 2409.03930 tab. 1. Card: DRAL.

When to use which

The review gives no decision rule. The rows below follow from its stated trade-offs and are not benchmark rankings. Each row cites the statement it rests on.

The review reports that state, action and observation spaces are usually easy to define, while transition, observation and reward functions are harder 2107.07599 §4.3. Budget modelling effort accordingly.

Implementation sketch

Belief update, following the review's description of Bayes' rule 2107.07599 §2 2107.07599 eq. 2:

# Bayes belief update after action a and observation o  [§2] [eq. 2]
# Input: belief b over states, action a, observation o
# Output: new belief b'

def update_belief(b, a, o, T, Z):
    # Predict: push the belief through the transition model  [§2]
    predicted = {s2: sum(T(s, a, s2) * b[s] for s in states) for s2 in states}
    # Correct: weight by the observation likelihood  [§2] [eq. 2]
    weighted = {s2: Z(s2, a, o) * predicted[s2] for s2 in states}
    # Normalise by the probability of the observation  [§2] [eq. 2]
    norm = sum(weighted.values())
    return {s2: w / norm for s2, w in weighted.items()}

Sampling-based solver loop, the common skeleton of the point-based and tree-search methods 2107.07599 §3 2107.07599 alg. 1:

# Sampling-based approximate POMDP solver  [alg. 1] [§3]
# Input: POMDP model, initial belief, planning budget
# Output: policy over the sampled beliefs

def sampling_pomdp_solver(model, initial_belief, budget):
    # Start with the initial belief in the sampled set  [alg. 1]
    policy = initial_policy()
    sampled_beliefs = [initial_belief]
    # Repeat until the stopping criterion holds  [alg. 1] [§3]
    while not stopping_criterion(budget):
        # Sample a belief; some methods sample histories instead  [alg. 1]
        new_belief = sample_belief(sampled_beliefs, model)
        sampled_beliefs.append(new_belief)
        # Estimate values with heuristics and backups  [alg. 1] [§3]
        values = estimate_values(sampled_beliefs, model)
        # The policy update is usually a by-product of the backup  [alg. 1]
        policy = update_policy(policy, values)
    return policy

Where variants differ: the belief sampler (reachable under an optimal policy for SARSOP, a one-step successor for PBVI, a simulated tree path for HSVI2 and the online methods), the backup (alpha-vector for point-based, tree values for online), and the stopping rule (a time budget, or a bound gap at the initial belief, which the review says solvers often reach earlier than the threshold) 2107.07599 §3.1 2107.07599 §3.

Contradictions

None known between the two sources, which use the formalism for different purposes and report no competing numbers. The main review's Tag timings (PBVI about 50 hours, HSVI2 at 2 hours, SARSOP in 6 seconds) are quoted from cited works and marked author-reported. The review does not say whether those setups match, so check the originals before comparing them 2107.07599 §3.1.

Pitfalls

• No hyperparameter values are stated for any solver: the HSVI2 gap threshold, POMCP exploration constant, DESPOT scenario count K, SARSOP dominance and bin settings, and particle counts are all "not stated" in the source 2107.07599 §3.1 2107.07599 §4.2. Take them from the original solver papers.
• Some printed formulas in the review need checking against the originals before implementation: the HSVI2 observation-selection score, the POMCP action rule, and the finite-horizon base case 2107.07599 §3.1 2107.07599 eq. 3.
• The review assumes first-order Markov transition and observation functions 2107.07599 §4.3.
• Earth mover's distance is suggested for robotics belief comparison, but the review gives no parameters for it 2107.07599 §4.2.
• The mental-world survey's tuples are described as POMDP-style, and its transition notation switches between A^phy and A_t 2601.02378 §2.1. Read its definitions against the original POMDP formulation before copying them.

Papers

• Partially Observable Markov Decision Processes (POMDPs) and Robotics: review of sampling-based POMDP solvers for robotics, grouped by five difficulties (state, horizon, observation, action space, dynamics), with software and practical notes.
• DRAL: PPO with an asymmetric actor-critic for three cable-carrying drones that search for and carry an unknown payload indoors; simulation results only.
• Modeling the Mental World for Embodied AI: A Comprehensive Review: survey of Theory of Mind for embodied agents that frames physical and mental world models as POMDP-style and Dec-POMDP models; no experiments.