POMDPs & Belief States
Planning when you cannot see the state.
A robot that cannot see where it is must plan over what it believes. Treating beliefs as states turns a POMDP back into an MDP, but one over a continuous simplex, where value functions are maxima of linear functions, exact planning is PSPACE-complete, and practical solvers back up only the beliefs that matter.
What you’ll learn
- Define a POMDP, derive the belief update, and explain why the belief is a sufficient statistic that turns the problem into a belief MDP.
- Prove that finite-horizon value functions are piecewise linear and convex (Smallwood & Sondik, 1973), and bound the growth of their α-vector sets.
- Sketch why finite-horizon POMDP planning is PSPACE-complete, and contrast it with MDPs and with infinite-horizon and multi-agent variants.
- Explain point-based value iteration and its error bound, and place HSVI, SARSOP, POMCP and DESPOT among modern solvers.
From histories to beliefs
Let . After action and observation , Bayes' rule and the Markov structure of and give
The normalizer is the predictive probability of the observation, which weights the branches of the future:
By induction, the distribution of all future observations and states, given the history and any rule for choosing future actions from future observations, depends on only through ; so does every expected future reward. The belief is a sufficient statistic for control (Åström, 1965).
Piecewise-linear convex value functions
is the maximum over . Assume the claim for and write the backup:
The normalizer cancels. is a linear function of divided by , so multiplying by leaves a maximum of functions linear in :
A sum over of maxima is the maximum over one choice per observation (a cross-sum), so the bracket is again a maximum of linear functions, and so is the outer maximum over actions:
Counting the choices gives the growth bound. Without pruning, is doubly exponential in , matching the number of depth- policy trees:
The tiger problem at horizon 1 (one action left). Over (tiger left, tiger right), the -vectors are listen , open-left and open-right . Above what belief does opening the right door beat listening?
Show the answer
0.9
Opening the right door is worth , which beats when . So is the upper envelope of three lines, with kinks at and . From , one growl from the left gives (still listen) and two give (open the right door). Longer horizons add facets, one for each conditional plan that is best somewhere.
Convexity has a decision-theoretic meaning. If , then : learning which of the two beliefs you are in can only help. It is the same convexity of the maximum that makes the value of information non-negative in Rationality & Expected Utility. Exact solvers prune vectors that are maximal nowhere by solving small linear programs, as in the Witness algorithm (Kaelbling, Littman & Cassandra, 1998) and incremental pruning (Cassandra, Littman & Zhang, 1997). Pruning helps enormously on small problems, but it cannot beat the worst case.
How hard is it? PSPACE and beyond
In PSPACE. Evaluate the tree of action–observation histories depth-first. Its depth is the horizon, polynomial in the input, and each level stores only a belief and partial sums, so polynomial space suffices although the tree is exponentially large.
PSPACE-hard, from quantified Boolean formulas with clauses . At the start, nature picks a clause uniformly at random and hides it from the agent.
Then the variables are set in order: the agent chooses the existential ones, and nature flips a fair coin for each universal one, which the agent observes. The state records whether the hidden clause has been satisfied, and at the end a cost of 1 is paid if it has not.
A policy sees only the assignments so far, so it is exactly a strategy for the existential player. Every clause and every universal branch have positive probability, so expected cost 0 means the strategy satisfies every clause on every branch, which is the truth of the formula. The construction is polynomial.
Partial observability is what defeats the MDP algorithms: policies must condition on observation histories, and here the hidden clause is never revealed. The landscape beyond this result:
- Infinite horizons. Without discounting, even deciding whether some policy reaches a goal with probability above a threshold is undecidable (Madani, Hanks & Condon, 2003), a descendant of undecidability results for probabilistic automata. With discounting, truncating at horizon costs at most , so -optimal values are computable, though not efficiently in general.
- Approximation. Approximating optimal values within useful factors is itself intractable for broad classes of POMDPs (Lusena, Goldsmith & Mundhenk, 2001).
- Many agents. Decentralized POMDPs, in which several agents act on their own observations, are NEXP-complete even for two agents and a finite horizon (Bernstein, Givan, Immerman & Zilberstein, 2002).
The belief MDP is "just an MDP", and solving MDPs is P-complete. Why doesn't that make finite-horizon POMDPs easy?
- The belief MDP has more actions than the POMDP
- Its states are beliefs, a continuum; even the beliefs reachable within horizon can number , exponential in the input
- The belief MDP is not Markov
- Each belief update takes exponential time
Show the answer
B. Its states are beliefs, a continuum; even the beliefs reachable within horizon can number , exponential in the input
P-completeness is about MDPs given explicitly, with a table of states. The belief MDP is given implicitly: its reachable states multiply with the horizon, and its full state space is the continuous simplex, so explicit-state algorithms do not apply. The piecewise-linear convex structure is what makes exact computation possible at all.
Point-based and online solvers
Exact backups over the whole simplex are wasteful: from a given only a small, often low-dimensional set of beliefs is reachable. Point-based value iteration (PBVI; Pineau, Gordon & Thrun, 2003) keeps a finite set of beliefs and computes, at each , only the single -vector that is best there. The cross-sum disappears: for each action and observation it picks the best continuation vector at , at a cost of per point instead of new vectors.
function POINT-BASED-BACKUP(b, Γ): # Γ: current set of α-vectors
for each action a:
for each observation o:
α_o ← argmax over α in Γ of Σ_s b(s) · g_{a,o}^α(s) # g as in the PWLC proof
α_a ← R(·, a) + γ · Σ_o g_{a,o}^{α_o}
return argmax over a of Σ_s b(s) · α_a(s)
function PBVI(b0):
B ← {b0}; Γ ← { R_min / (1 − γ) · 1 } # a lower bound on V*
repeat until out of time:
repeat a few times: Γ ← { POINT-BASED-BACKUP(b, Γ) : b in B }
for each b in B: add the successor τ(b, a, o) farthest (in L1) from B
return Γ # V(b) = max over α in Γ of α · bEvery vector is the value of an actual conditional plan, so starting from a lower bound keeps every iterate a lower bound on . Expanding toward distant successors spreads the points over the reachable beliefs.
Modern solvers refine the idea. HSVI (Smith & Simmons, 2004) keeps a lower bound of -vectors and an upper bound by sawtooth interpolation, and explores the beliefs where the gap matters most. SARSOP (Kurniawati, Hsu & Lee, 2008) samples only beliefs reachable under near-optimal policies and solves problems with thousands of states offline. Online planners search from the current belief at every step: POMCP (Silver & Veness, 2010) runs UCT-style Monte Carlo tree search over histories with a particle belief and needs only a simulator, and DESPOT (Somani, Ye, Hsu & Lee, 2013) searches a sparse tree of sampled scenarios with regularization. Why do they work? The difficulty of approximate planning is governed by the covering number of the reachable belief space rather than by its dimension (Hsu, Lee & Rong, 2007).
Key takeaways
- A POMDP's belief , updated by Bayes' rule as , is a sufficient statistic; the POMDP is an MDP over the simplex .
- Finite-horizon values are piecewise linear and convex, , because the observation normalizer cancels in the backup; without pruning, grows doubly exponentially.
- Finite-horizon POMDP planning is PSPACE-complete (MDPs are P-complete), some infinite-horizon undiscounted questions are undecidable, and decentralized POMDPs are NEXP-complete.
- Point-based methods back up only sampled reachable beliefs and keep lower bounds with error at most ; HSVI, SARSOP, POMCP and DESPOT scale the idea to large problems.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
holds 10 vectors, and the POMDP has 3 actions and 2 observations. Before pruning, at most how many vectors can the exact backup produce for ?
- 60
- 30
- 300
Show the answer
D. 300
For each action, choose one continuation vector per observation: combinations, times 3 actions, gives . In general the bound is , which iterates to a doubly exponential bound; LP pruning removes the vectors that are maximal nowhere.
In the proof that is piecewise linear and convex, which step makes each future term linear in ?
- The belief update is linear in
- Multiplying by cancels the normalizer of , leaving a maximum of functions linear in
- The future terms do not depend on
- Bayes' rule is applied only once
Show the answer
B. Multiplying by cancels the normalizer of , leaving a maximum of functions linear in
is a linear function of divided by , which is itself linear in : a projective map, not a linear one. Multiplying back by removes the division, so each weighted term becomes .
Finite-horizon POMDP planning is PSPACE-complete, while MDP planning is P-complete. What is the essential source of the gap?
- Policies must condition on observation histories because the state is hidden, and the relevant histories or beliefs grow exponentially with the horizon
- POMDPs have larger state spaces
- POMDP rewards are random
- POMDPs are discounted
Show the answer
A. Policies must condition on observation histories because the state is hidden, and the relevant histories or beliefs grow exponentially with the horizon
In the reduction, the hidden clause forces the agent to plan for all clauses at once with a policy that sees only the observed assignments, like an existential player who never learns which clause will be checked. In a fully observable MDP the state itself is a sufficient statistic, so dynamic programming over the given states suffices.
PBVI starts from the lower bound . What can you say about the value function it returns?
- It is an upper bound on
- It equals exactly at the points of
- It is a lower bound on everywhere, within on the reachable beliefs
- It comes with no guarantee
Show the answer
C. It is a lower bound on everywhere, within on the reachable beliefs
Every vector is the value of an actual conditional plan, so the maximum can only underestimate the optimum, at every belief. The density of the belief set controls how much is lost, and HSVI adds an upper bound to certify the gap.
Further reading
- R. D. Smallwood & E. J. Sondik, "The optimal control of partially observable Markov processes over a finite horizon," Operations Research 21(5), 1071–1088 (1973).
- L. P. Kaelbling, M. L. Littman & A. R. Cassandra, "Planning and acting in partially observable stochastic domains," Artificial Intelligence 101, 99–134 (1998).
- C. H. Papadimitriou & J. N. Tsitsiklis, "The complexity of Markov decision processes," Mathematics of Operations Research 12(3), 441–450 (1987).
- J. Pineau, G. Gordon & S. Thrun, "Point-based value iteration: an anytime algorithm for POMDPs," Proceedings of IJCAI (2003).
- D. Silver & J. Veness, "Monte-Carlo planning in large POMDPs," Advances in Neural Information Processing Systems 23 (2010).