Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

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

DerivationThe belief update
  1. bt+1(s′)=Z(o∣s′,a)∑sT(s′∣s,a) bt(s)Pr⁡(o∣bt,a)=:τ(bt,a,o)(s′)b_{t+1}(s')=\frac{Z(o\mid s',a)\sum_sT(s'\mid s,a)\,b_t(s)}{\Pr(o\mid b_t,a)}=:\tau(b_t,a,o)(s')

    Let bt(s)=Pr⁡(St=s∣ht,b0)b_t(s)=\Pr(S_t=s\mid h_t,b_0). After action aa and observation oo, Bayes' rule and the Markov structure of TT and ZZ give

  2. Pr⁡(o∣b,a)=∑s′Z(o∣s′,a)∑sT(s′∣s,a) b(s)\Pr(o\mid b,a)=\sum_{s'}Z(o\mid s',a)\sum_sT(s'\mid s,a)\,b(s)

    The normalizer is the predictive probability of the observation, which weights the branches of the future:

  3. E[∑k≥tγk−tR(Sk,Ak) ∣ ht, continuation rule]=f(bt, continuation rule)\E\Big[\sum_{k\ge t}\gamma^{k-t}R(S_k,A_k)\ \Big|\ h_t,\ \text{continuation rule}\Big]=f\big(b_t,\ \text{continuation rule}\big)

    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 hth_t only through btb_t; so does every expected future reward. The belief is a sufficient statistic for control (Åström, 1965).

Piecewise-linear convex value functions

DerivationProof by induction on the horizon
  1. Vt(b)=max⁡a[∑sb(s)R(s,a)+γ∑oPr⁡(o∣b,a) Vt−1(τ(b,a,o))]V_t(b)=\max_a\Big[\sum_sb(s)R(s,a)+\gamma\sum_o\Pr(o\mid b,a)\,V_{t-1}\big(\tau(b,a,o)\big)\Big]

    V0≡0V_0\equiv0 is the maximum over Γ0={0}\Gamma_0=\{\mathbf 0\}. Assume the claim for t−1t-1 and write the backup:

  2. Pr⁡(o∣b,a) Vt−1(τ(b,a,o))=max⁡α∈Γt−1∑sb(s)∑s′T(s′∣s,a) Z(o∣s′,a) α(s′)⏟ga,oα(s)\Pr(o\mid b,a)\,V_{t-1}\big(\tau(b,a,o)\big)=\max_{\alpha\in\Gamma_{t-1}}\sum_sb(s)\underbrace{\sum_{s'}T(s'\mid s,a)\,Z(o\mid s',a)\,\alpha(s')}_{g^{\alpha}_{a,o}(s)}

    The normalizer cancels. τ(b,a,o)\tau(b,a,o) is a linear function of bb divided by Pr⁡(o∣b,a)\Pr(o\mid b,a), so multiplying by Pr⁡(o∣b,a)\Pr(o\mid b,a) leaves a maximum of functions linear in bb:

  3. Γt=⋃a∈A{R(⋅,a)+γ∑o∈Oga,oαo : αo∈Γt−1 for each o}\Gamma_t=\bigcup_{a\in A}\Big\{R(\cdot,a)+\gamma\sum_{o\in O}g^{\alpha_o}_{a,o}\ :\ \alpha_o\in\Gamma_{t-1}\text{ for each }o\Big\}

    A sum over oo of maxima is the maximum over one choice αo∈Γt−1\alpha_o\in\Gamma_{t-1} per observation (a cross-sum), so the bracket is again a maximum of linear functions, and so is the outer maximum over actions:

  4. ∣Γt∣≤∣A∣ ∣Γt−1∣∣O∣,∣Γt∣≤∣A∣(∣O∣t−1)/(∣O∣−1)|\Gamma_t|\le|A|\,|\Gamma_{t-1}|^{|O|},\qquad|\Gamma_t|\le|A|^{(|O|^t-1)/(|O|-1)}

    Counting the choices gives the growth bound. Without pruning, ∣Γt∣|\Gamma_t| is doubly exponential in tt, matching the number of depth-tt policy trees:

Predict before you look

The tiger problem at horizon 1 (one action left). Over (tiger left, tiger right), the α\alpha-vectors are listen (−1,−1)(-1,-1), open-left (−100,10)(-100,10) and open-right (10,−100)(10,-100). Above what belief p=Pr⁡(tiger left)p=\Pr(\text{tiger left}) does opening the right door beat listening?

Show the answer

0.9

Opening the right door is worth 10p−100(1−p)=110p−10010p-100(1-p)=110p-100, which beats −1-1 when p>99/110=0.9p>99/110=0.9. So V1V_1 is the upper envelope of three lines, with kinks at p=0.1p=0.1 and p=0.9p=0.9. From 0.50.5, one growl from the left gives 0.850.85 (still listen) and two give 0.970.97 (open the right door). Longer horizons add facets, one for each conditional plan that is best somewhere.

Convexity has a decision-theoretic meaning. If b=λb1+(1−λ)b2b=\lambda b_1+(1-\lambda)b_2, then V(b)≤λV(b1)+(1−λ)V(b2)V(b)\le\lambda V(b_1)+(1-\lambda)V(b_2): 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

DerivationProof idea, in the spirit of their reduction
  1. Vt(b)=max⁡a[ρ(b,a)+γ∑oPr⁡(o∣b,a) Vt−1(τ(b,a,o))]evaluated recursivelyV_t(b)=\max_a\Big[\rho(b,a)+\gamma\sum_o\Pr(o\mid b,a)\,V_{t-1}\big(\tau(b,a,o)\big)\Big]\quad\text{evaluated recursively}

    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.

  2. S={1,…,m}×{satisfied, not yet}×{position in the variable order}S=\{1,\dots,m\}\times\{\text{satisfied},\ \text{not yet}\}\times\{\text{position in the variable order}\}

    PSPACE-hard, from quantified Boolean formulas ∃x1∀x2⋯φ\exists x_1\forall x_2\cdots\varphi with clauses C1,…,CmC_1,\dots,C_m. At the start, nature picks a clause jj uniformly at random and hides it from the agent.

  3. cost=1{Cj is unsatisfied by the final assignment}\text{cost}=\mathbf 1\{C_j\ \text{is unsatisfied by the final assignment}\}

    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.

  4. min⁡π Eπ[cost]=0  ⟺  ∃x1∀x2⋯φ is true\min_\pi\ \E^\pi[\text{cost}]=0\iff\exists x_1\forall x_2\cdots\varphi\ \text{is true}

    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 HH costs at most γHRmax⁡/(1−γ)\gamma^HR_{\max}/(1-\gamma), so ε\varepsilon-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).
Check your understanding

The belief MDP is "just an MDP", and solving MDPs is P-complete. Why doesn't that make finite-horizon POMDPs easy?

  1. The belief MDP has more actions than the POMDP
  2. Its states are beliefs, a continuum; even the beliefs reachable within horizon HH can number (∣A∣∣O∣)H(|A||O|)^H, exponential in the input
  3. The belief MDP is not Markov
  4. Each belief update takes exponential time
Show the answer

B. Its states are beliefs, a continuum; even the beliefs reachable within horizon HH can number (∣A∣∣O∣)H(|A||O|)^H, 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 b0b_0 only a small, often low-dimensional set of beliefs is reachable. Point-based value iteration (PBVI; Pineau, Gordon & Thrun, 2003) keeps a finite set BB of beliefs and computes, at each b∈Bb\in B, only the single α\alpha-vector that is best there. The cross-sum disappears: for each action and observation it picks the best continuation vector at bb, at a cost of O(∣A∣∣O∣∣Γ∣∣S∣2)\order{|A||O||\Gamma||S|^2} per point instead of ∣A∣∣Γ∣∣O∣|A||\Gamma|^{|O|} new vectors.

text
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 α · b

Every vector is the value of an actual conditional plan, so starting from a lower bound keeps every iterate a lower bound on V∗V^*. Expanding BB toward distant successors spreads the points over the reachable beliefs.

Modern solvers refine the idea. HSVI (Smith & Simmons, 2004) keeps a lower bound of α\alpha-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 b(s)=Pr⁡(St=s∣ht)b(s)=\Pr(S_t=s\mid h_t), updated by Bayes' rule as τ(b,a,o)\tau(b,a,o), is a sufficient statistic; the POMDP is an MDP over the simplex Δ(S)\Delta(S).
  • Finite-horizon values are piecewise linear and convex, Vt(b)=max⁡α∈Γtα⋅bV_t(b)=\max_{\alpha\in\Gamma_t}\alpha\cdot b, because the observation normalizer cancels in the backup; without pruning, ∣Γt∣≤∣A∣∣Γt−1∣∣O∣|\Gamma_t|\le|A||\Gamma_{t-1}|^{|O|} 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 (Rmax⁡−Rmin⁡)δB/(1−γ)2(R_{\max}-R_{\min})\delta_B/(1-\gamma)^2; 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.

Question 1

Γt−1\Gamma_{t-1} 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 Γt\Gamma_t?

  1. 60
  2. 30
  3. 3×210=3,0723\times2^{10}=3{,}072
  4. 300
Show the answer

D. 300

For each action, choose one continuation vector per observation: 10210^2 combinations, times 3 actions, gives 300300. In general the bound is ∣A∣∣Γt−1∣∣O∣|A||\Gamma_{t-1}|^{|O|}, which iterates to a doubly exponential bound; LP pruning removes the vectors that are maximal nowhere.

Question 2

In the proof that VtV_t is piecewise linear and convex, which step makes each future term linear in bb?

  1. The belief update τ(b,a,o)\tau(b,a,o) is linear in bb
  2. Multiplying Vt−1(τ(b,a,o))V_{t-1}(\tau(b,a,o)) by Pr⁡(o∣b,a)\Pr(o\mid b,a) cancels the normalizer of τ\tau, leaving a maximum of functions linear in bb
  3. The future terms do not depend on bb
  4. Bayes' rule is applied only once
Show the answer

B. Multiplying Vt−1(τ(b,a,o))V_{t-1}(\tau(b,a,o)) by Pr⁡(o∣b,a)\Pr(o\mid b,a) cancels the normalizer of τ\tau, leaving a maximum of functions linear in bb

τ(b,a,o)\tau(b,a,o) is a linear function of bb divided by Pr⁡(o∣b,a)\Pr(o\mid b,a), which is itself linear in bb: a projective map, not a linear one. Multiplying back by Pr⁡(o∣b,a)\Pr(o\mid b,a) removes the division, so each weighted term Pr⁡(o∣b,a) α⋅τ(b,a,o)\Pr(o\mid b,a)\,\alpha\cdot\tau(b,a,o) becomes ga,oα⋅bg^\alpha_{a,o}\cdot b.

Question 3

Finite-horizon POMDP planning is PSPACE-complete, while MDP planning is P-complete. What is the essential source of the gap?

  1. Policies must condition on observation histories because the state is hidden, and the relevant histories or beliefs grow exponentially with the horizon
  2. POMDPs have larger state spaces
  3. POMDP rewards are random
  4. 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.

Question 4

PBVI starts from the lower bound Rmin⁡1−γ1\frac{R_{\min}}{1-\gamma}\mathbf 1. What can you say about the value function V(b)=max⁡α∈Γα⋅bV(b)=\max_{\alpha\in\Gamma}\alpha\cdot b it returns?

  1. It is an upper bound on V∗V^*
  2. It equals V∗V^* exactly at the points of BB
  3. It is a lower bound on V∗V^* everywhere, within (Rmax⁡−Rmin⁡)δB/(1−γ)2(R_{\max}-R_{\min})\delta_B/(1-\gamma)^2 on the reachable beliefs
  4. It comes with no guarantee
Show the answer

C. It is a lower bound on V∗V^* everywhere, within (Rmax⁡−Rmin⁡)δB/(1−γ)2(R_{\max}-R_{\min})\delta_B/(1-\gamma)^2 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 δB\delta_B 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).