---
kind: concept
slug: partially-observable-markov-decision-process
title: Partially observable Markov decision process (POMDP)
summary: >-
  Sequential decision making when the state is hidden and actions and observations are noisy. The agent plans over beliefs, probability distributions over states. Exact solutions are intractable, so practical solvers plan over a sampled set of beliefs (offline point-based methods such as SARSOP, or online tree search such as POMCP and DESPOT).
tags: [planning, uncertainty, robotics, reinforcement-learning]
papers: ["2107.07599", "2409.03930", "2601.02378"]
related: [value-iteration, monte-carlo-tree-search, model-based-reinforcement-learning, hierarchical-reinforcement-learning, sim-to-real-transfer, robot-simulation, bayesian-optimization, world-model, proximal-policy-optimization, multi-robot-navigation]
status: draft
updated_at: 2026-10-25
---

## 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 [arxiv: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 [arxiv:2107.07599 §2]
[arxiv:2107.07599 eq. 2].

The core difficulty is that the optimal policy over beliefs is intractable in
general (PSPACE-hard) [arxiv: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
[arxiv:2107.07599 §4.3]. The sampling-based solvers do not guarantee an
optimal policy [arxiv:2107.07599 §1] [arxiv: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
[arxiv:2107.07599 §3.1] [arxiv:2107.07599 §4.3]. Card: [Partially Observable Markov Decision Processes (POMDPs) and Robotics](/papers/2107.07599).
A second survey uses the same formalism to model what other agents know and
intend; it is covered in its own section below
[arxiv: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 [arxiv:2409.03930 §3.2].

## Variants

The review groups solver ideas by the five difficulties they address
[arxiv: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 [arxiv:2107.07599 §3.1]. Card: [Partially Observable Markov Decision Processes (POMDPs) and Robotics](/papers/2107.07599).

- **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 [arxiv:2107.07599 §3.1].
- **Perseus**: separates belief sampling from backup and backs up only a
  subset of the sampled beliefs, which keeps fewer vectors [arxiv: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 [arxiv: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 [arxiv:2107.07599 §3.1].
- **PBPI**: point-based backup applied to policy iteration, with the policy
  stored as a finite state controller [arxiv: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)
[arxiv: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 [arxiv:2107.07599 §3] [arxiv:2107.07599 §3.1].

- **POMCP**: UCT-style Monte Carlo tree search over histories, with a
  generative model and particle beliefs [arxiv:2107.07599 §3.1].
- **ABT**: backs up values along the tree and reuses earlier trees
  [arxiv:2107.07599 §3.1].
- **DESPOT**: builds a sparse tree from a fixed number K of sampled scenarios
  [arxiv:2107.07599 §3.1].
- **RTDP-Bel**: one-step lookahead with heuristics over a hash table of belief
  values [arxiv: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 [arxiv:2107.07599 §3.2].

### Large observation space (§3.3)

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

### Large action space (§3.4)

Most solvers enumerate actions and handle at most about 100 discrete actions
[arxiv: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
[arxiv: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
[arxiv: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 [arxiv:2601.02378 §2.1]
[arxiv: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 [arxiv: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 [arxiv: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
[arxiv:2601.02378 §4.2]. Card: [Modeling the Mental World for Embodied AI: A Comprehensive Review](/papers/2601.02378).

## 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 [arxiv:2409.03930 §3.2]. The policy maps
observation histories to action distributions, and the card records no belief
or belief update [arxiv: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 [arxiv:2409.03930 tab. 1].
Card: [DRAL](/papers/2409.03930).

## 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.

| Situation | Use | Why |
|---|---|---|
| Planning time can be spent before deployment and the state space is moderate | Offline point-based (SARSOP, HSVI2, Perseus) | Offline solvers can need tens of hours, but the policy is then ready at run time [arxiv:2107.07599 §3.1] |
| Hard real-time limits, or a very large state space | Online tree search (POMCP, DESPOT, ABT) | Online solvers cannot be precomputed and must meet real-time limits [arxiv:2107.07599 §3] [arxiv:2107.07599 §3.1] |
| Long plans with clear sub-goals | Macro-actions with hand-designed sub-goals | Look-ahead grows exponentially with depth; macro-actions shorten it [arxiv:2107.07599 §3.2] |
| Many discrete actions (up to about 100) | Enumerate actions | Most solvers enumerate actions [arxiv:2107.07599 §3.4] |
| Many discrete actions (hundreds or more) | Sampled maxima or the quantile sampler | Enumeration does not scale [arxiv:2107.07599 §3.4] |
| Expensive simulator or differential-equation dynamics | Multilevel Monte Carlo or linearised LQR | Forward simulation is no longer nearly free [arxiv:2107.07599 §3.5] |
| Model is rough, data-fitted | Plan anyway and check robustness on hardware | A rough model still gave good policies in one reported demonstration [arxiv:2107.07599 §4.3] |
| Partial observations at run time, a simulator with full state for training, and no belief model wanted | Asymmetric actor-critic with PPO | The critic sees privileged state only during training, so no belief is tracked [arxiv:2409.03930 §3.2]. Reward and observation definitions are not stated in the card, so the policy cannot be rebuilt from it alone [arxiv:2409.03930 §3.2] |

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

## Implementation sketch

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

```pseudocode
# 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 [arxiv:2107.07599 §3] [arxiv:2107.07599 alg. 1]:

```pseudocode
# 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) [arxiv:2107.07599 §3.1] [arxiv: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 [arxiv: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
  [arxiv:2107.07599 §3.1] [arxiv: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 [arxiv:2107.07599 §3.1] [arxiv:2107.07599 eq. 3].
- The review assumes first-order Markov transition and observation functions
  [arxiv:2107.07599 §4.3].
- Earth mover's distance is suggested for robotics belief comparison, but the
  review gives no parameters for it [arxiv: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 [arxiv:2601.02378 §2.1].
  Read its definitions against the original POMDP formulation before copying them.

## Papers

- [Partially Observable Markov Decision Processes (POMDPs) and Robotics](/papers/2107.07599): review of sampling-based POMDP solvers for robotics, grouped by five difficulties (state, horizon, observation, action space, dynamics), with software and practical notes.
- [DRAL](/papers/2409.03930): 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](/papers/2601.02378): survey of Theory of Mind for embodied agents that frames physical and mental world models as POMDP-style and Dec-POMDP models; no experiments.