Solving POMDPs (exact and approximate)

"Do not ask me for a number at every world I might be in. Hand me your belief, a single point in the simplex, and I will give you a value, by reading off the highest of my many flat planes. I am not one function but a committee of linear opinions, and the convex upper envelope of that committee is me: piecewise, linear, and quietly proud of every facet."

A Value Function Defined Over Beliefs, Piecewise and Proud

In Section 23.1 we defined the POMDP and the belief state $\mathbf{b}_t$, showed that the belief is a sufficient statistic of the entire observation-action history, and derived the Bayesian belief update that carries $\mathbf{b}_{t-1}$ to $\mathbf{b}_t$ after an action and an observation. That update turned the POMDP into a fully observed Markov decision process whose state is the belief, the so-called belief MDP. We deferred the one question that makes the belief MDP useful: how do we actually compute an optimal policy over a continuous, high-dimensional belief space? This section answers it. The belief MDP is a genuine MDP, so the Bellman machinery of Chapter 22 applies in principle, but its state space is the entire probability simplex over states, uncountably infinite, so the tabular value iteration of Chapter 22 cannot be run directly. The breakthrough that rescues the situation, due to Sondik in 1971, is that the value function has a special and exploitable shape. We develop that shape and then the family of algorithms it enables. Throughout we use the unified notation of Appendix A: $S$ the states, $A$ the actions, $\Omega$ the observations, $\mathbf{b}$ the belief, $\gamma$ the discount, $V$ the value function.

Why does solving POMDPs deserve a section of its own rather than a footnote to MDP value iteration? Because partial observability changes the character of the problem qualitatively, not just quantitatively. A fully observed MDP plans over a finite set of states; a POMDP plans over a continuum of beliefs, and the optimal action at a belief can depend on arbitrarily fine distinctions between nearby beliefs. Worse, the optimal policy must reason about information gathering, taking an action not for its immediate reward but to sharpen the belief so that a later action pays off, a behavior with no analogue in the fully observed case. The Tiger problem we solve at the end makes this vivid: the optimal agent often pays to listen repeatedly before committing to open a door, buying information at a cost. Capturing that behavior is exactly what makes POMDP solving both hard and worth the trouble.

The four concrete competencies this section installs are these: to represent a POMDP value function as a set of alpha-vectors and evaluate it at a belief by taking the max inner product; to explain why exact value iteration over beliefs is correct but PSPACE-hard, and what makes the alpha-vector set explode; to describe how point-based methods (PBVI, SARSOP, Perseus) and online planners (POMCP, DESPOT) tame that explosion, and when each is appropriate; and to implement a small exact solver and reproduce it with a library. These are the load-bearing skills for every belief-state agent in this chapter and the foundation for the model-free shortcut of Section 23.3.

1. Exact Value Functions Over Belief Space Intermediate

The belief MDP has a Bellman optimality equation just like any MDP, but its state is the belief $\mathbf{b}$, a point in the $(|S|-1)$-simplex. Writing $r(\mathbf{b}, a) = \sum_{s} \mathbf{b}(s)\,R(s, a)$ for the expected immediate reward of action $a$ at belief $\mathbf{b}$, and $\mathbf{b}^{a, o}$ for the belief that results from taking $a$ and observing $o$ (the update of Section 23.1), the optimal value satisfies

where $P(o \mid \mathbf{b}, a)$ is the probability of observation $o$ given the current belief and action. This is a Bellman equation over a continuous state space, and at first glance it looks hopeless: $V^{*}$ is a function on an infinite set, so we cannot tabulate it. The rescue is a theorem about its shape. The decisive object is the alpha-vector, a vector $\boldsymbol{\alpha} \in \mathbb{R}^{|S|}$ that assigns a value to each underlying state; its inner product with a belief, $\boldsymbol{\alpha} \cdot \mathbf{b} = \sum_{s} \boldsymbol{\alpha}(s)\,\mathbf{b}(s)$, is a linear function of the belief. Sondik's theorem states that the finite-horizon optimal value function is the upper envelope of a finite set $\Gamma = \{\boldsymbol{\alpha}_1, \dots, \boldsymbol{\alpha}_m\}$ of such vectors:

Because each $\boldsymbol{\alpha} \cdot \mathbf{b}$ is linear in $\mathbf{b}$ and the pointwise maximum of linear functions is convex and piecewise-linear, $V^{*}$ is piecewise-linear-and-convex (PWLC) over the simplex. Each alpha-vector corresponds to a conditional plan, a complete policy tree of what to do for the rest of the horizon; the vector records the expected discounted return of that plan as a function of the true (unknown) starting state. At any belief the agent picks the plan with the highest expected value there, which is exactly the max in the equation. Figure 23.2.1 draws the envelope for a two-state POMDP, where the simplex is the unit interval and each alpha-vector is a line.

Exact value iteration over beliefs maintains the set $\Gamma$ and updates it. One backup, the analogue of a single Bellman sweep, takes the current alpha-vector set $\Gamma_n$ representing the $n$-step value function and produces $\Gamma_{n+1}$ representing the $(n+1)$-step value function. The construction enumerates, for each action and each way of assigning a future alpha-vector to each possible observation, the alpha-vector of the resulting conditional plan. Concretely, a backed-up alpha-vector for action $a$ and an assignment $o \mapsto \boldsymbol{\alpha}^{o}$ has entries

where $T$ is the transition model and $Z$ the observation model from Section 23.1. The exactness is purchased at a steep price. If $\Gamma_n$ has $m$ vectors, the naive backup generates up to $|A|\,m^{|\Omega|}$ candidate vectors, one for each action and each of the $m^{|\Omega|}$ ways of mapping observations to future plans. Many are dominated (never the maximum at any belief) and can be pruned, each pruning test a small linear program. Even so, in the worst case the number that survive grows doubly exponentially in the horizon. This is why exact POMDP planning is PSPACE-hard (a complexity class believed even harder than NP-complete, meaning no efficient exact algorithm is expected) (Papadimitriou and Tsitsiklis, 1987): the value function's exact representation can require an astronomically large alpha-vector set even for modest problems.

The doubly exponential growth is not a removable artifact of a clumsy algorithm; it reflects genuine problem complexity. The number of distinct optimal conditional plans really can explode with the horizon, because each additional step of lookahead multiplies the ways the future can branch on observations. Exact solvers (Sondik's one-pass algorithm, the Witness algorithm of Kaelbling, Littman, and Cassandra, incremental pruning) differ in how cleverly they prune dominated vectors and avoid generating useless candidates, and they push the frontier of exactly solvable POMDPs to perhaps a dozen states and a short horizon. Beyond that, exactness is hopeless and we must approximate. The good news, developed next, is that most of the belief simplex is never visited by a good policy, so we can afford to compute the value only where it matters.

2. Point-Based Methods: PBVI, SARSOP, Perseus Advanced

The escape from the doubly exponential blow-up rests on a simple observation about reachability. Starting from a known initial belief $\mathbf{b}_0$, only a tiny, measure-zero sliver of the belief simplex is ever reached under any policy: beliefs are produced by the deterministic belief update applied to discrete observations, so the reachable set is countable and, in practice, concentrated. The full alpha-vector set wastes enormous effort representing the value accurately at beliefs the agent will never occupy. Point-based value iteration refuses that waste: it samples a finite set $B = \{\mathbf{b}_1, \dots, \mathbf{b}_N\}$ of reachable beliefs and maintains exactly one alpha-vector per sampled belief, the one that is optimal there. This caps the alpha-vector set at $|B|$ vectors, turning the doubly exponential representation into a linear one.

The original point-based value iteration (PBVI) of Pineau, Gordon, and Thrun (2003) made this concrete. It backs up the value only at the sampled beliefs: for each $\mathbf{b} \in B$ it computes the single best backed-up alpha-vector at that belief, using the same backup equation of subsection one but evaluated at $\mathbf{b}$ rather than enumerated over all assignments, which costs only $O(|A|\,|\Omega|\,|B|\,|S|^2)$ per sweep instead of the exponential enumeration. Crucially the resulting alpha-vector is still a valid linear lower bound on $V^{*}$ everywhere, not just at $\mathbf{b}$, so the set of point-based alpha-vectors defines a value function over the whole simplex that lower-bounds the optimal one and improves monotonically. PBVI also grows $B$ over time by expanding to newly reachable beliefs, refining the approximation where the policy actually goes.

Two refinements dominate practice. Perseus (Spaan and Vlassis, 2005) is a randomized point-based backup: it backs up beliefs in random order and stops a sweep as soon as every sampled belief's value has improved, so a single backed-up vector often improves many beliefs at once, giving large speedups. SARSOP (Kurniawati, Hsu, and Lee, 2008), the current workhorse for moderate POMDPs, is smarter about which beliefs to sample: it maintains both a lower bound (alpha-vectors) and an upper bound on $V^{*}$ and uses them to guide sampling toward the optimally reachable belief space, the beliefs reached under near-optimal policies, pruning branches that the gap between bounds proves cannot be optimal. SARSOP routinely solves POMDPs with hundreds to thousands of states that are far beyond any exact method.

The trade point-based methods make is clean and worth stating precisely. They give up the guarantee of exactness: the returned value function is a lower bound on $V^{*}$, tight at and near the sampled beliefs, looser elsewhere, and the policy it induces is near-optimal rather than optimal, with the gap controllable by sampling more beliefs. In exchange they convert an intractable problem into a tractable one: the representation size is bounded by the number of sampled beliefs, not the horizon, and the per-sweep cost is polynomial. For the moderate POMDPs that arise in robotics navigation, dialogue management, and medical decision support, point-based methods with SARSOP are the default offline solver, and we use the offline-solve-then-deploy pattern in the practical example below.

3. Online Planning: POMCP and DESPOT Advanced

Point-based methods are offline: they solve the whole (reachable) problem once, producing a policy that maps any belief to an action, then deploy it. Online planning takes the opposite stance. It does no precomputation; instead, at each decision point, it plans from the current belief only, searching forward a limited horizon to choose the next action, then executes that action, observes, updates the belief, and replans. This is the POMDP analogue of model predictive control: solve a local lookahead afresh at every step. The advantage is that online planning never represents the value over the whole simplex, so it scales to enormous state spaces where even point-based methods choke; the cost is per-step computation and the need for a fast simulator of the POMDP.

The two dominant online planners both run Monte Carlo tree search (MCTS) in belief space, and both sidestep the central difficulty of online POMDP planning, which is that the belief itself is expensive to represent and update exactly in a large state space. Their shared trick is to represent the belief not as an explicit distribution but as a particle filter, a weighted set of sampled states, exactly the unweighted-particle and resampling machinery developed for nonlinear filtering in Section 7.4. The belief-MDP-to-particle-filter callback is direct: the sequential Monte Carlo that tracked a continuous latent state under nonlinear dynamics in Chapter 7 is reused here to track the discrete (or continuous) hidden state of a POMDP during planning, with the simulator playing the role of the dynamics and observation models.

POMCP (Partially Observable Monte Carlo Planning, Silver and Veness, 2010) marries that particle-filter belief to UCT, the upper-confidence-bound tree search of Chapter 22. It builds a search tree whose nodes are action-observation histories; at each node it stores a set of particles approximating the belief there. A simulation samples a state from the root particle set, then descends the tree choosing actions by UCB and observations by simulating the model, expanding the tree and running a rollout at the frontier, and finally backs up the return along the path. After a budget of simulations it plays the root action with the highest mean return. POMCP needs only a generative simulator (sample next state, observation, reward), never the explicit $T$ and $Z$ tables, so it handles POMDPs with millions of states. DESPOT (Determinized Sparse Partially Observable Tree, Ye, Somani, Hsu, and Lee, 2017) sharpens this by searching a sparse tree built from a small set of deterministic sampled "scenarios" (fixed random seeds), which dramatically reduces the variance and branching of the search and admits a regret bound; DESPOT and its successors are the strongest online POMDP planners for large problems and underpin much of modern autonomous-driving decision-making.

The mental model that unifies the two planner families is search-versus-solve. Point-based methods solve: they invest heavy offline computation to produce a policy good everywhere on the reachable simplex, amortized over many deployments. Online planners search: they invest light per-step computation to produce a good action here and now, paying the cost again at every step but never needing to represent the global value. The choice between them, the subject of subsection four, turns on whether the state space is small enough to solve offline and whether you can afford per-step planning latency at deployment.

4. When to Use What, and the Bridge to Model-Free Agents Intermediate

With four families on the table, exact value iteration, point-based offline solvers, online tree search, and (next section) model-free belief-free agents, the practitioner needs a decision rule rather than a catalogue. The choice is governed by three questions: how large is the state space, do you have an explicit model or only a simulator, and can you afford per-step planning latency at deployment. Figure 23.2.2 lays out the answer.

The three rows above all share a commitment that the fourth abandons: they reason explicitly about the belief, the posterior over states, and they require (point-based, exact) or simulate (online) a model of the world. That commitment is a strength when a model is available and a liability when it is not. Real systems, a dialogue agent facing an unknown user, a trading agent in a market it cannot simulate, a robot in an unmodeled environment, often have no clean $T$ and $Z$ to hand. For them the question becomes: can we get the benefit of belief-state reasoning without ever writing down the belief or the model?

This is the temporal thread of this book closing another loop. The Kalman filter and HMM of Chapter 7 tracked a latent state with a known model; the RNN of Chapter 9 learned to track latent structure from data; here the POMDP belief is the Bayesian latent-state tracker made into a decision-maker, and Section 23.3 will hand that tracking job to a learned recurrent or state-space network. Same loop, $\mathbf{h}_t = f(\mathbf{h}_{t-1}, \cdot)$, three incarnations: filtered, learned, and now acting. The explicit-belief methods of this section are the principled, model-based end of that spectrum; the model-free agents of the next section are the scalable, model-free end. Knowing both, and when each is the right tool, is the point of the chapter.

5. Worked Example: Solving the Tiger Problem Advanced

We now make the alpha-vector machinery executable on the canonical small POMDP, the Tiger problem (Kaelbling, Littman, and Cassandra, 1998). The agent stands before two doors; behind one is a tiger, behind the other a reward. The hidden state is $s \in \{\text{tiger-left}, \text{tiger-right}\}$. The agent can listen (cost $-1$, and receive a noisy observation that correctly localizes the tiger with probability $0.85$), open-left, or open-right (opening the door without the tiger gives $+10$, opening the door with the tiger gives $-100$, and resets the problem). The tension is exactly the information-gathering behavior promised in the introduction: the agent must decide whether its current belief is sharp enough to open a door or whether to pay to listen again. Code 23.2.1 builds the model and a from-scratch one-step alpha-vector backup, then evaluates the value and best action across the belief simplex.

import numpy as np

# --- Tiger POMDP model (states: 0 = tiger-left, 1 = tiger-right) ---
S = [0, 1]                                  # hidden states
A = ["listen", "open-left", "open-right"]   # actions
O = [0, 1]                                   # observations: 0 = hear-left, 1 = hear-right
gamma = 0.95

# Reward R[a][s]: expected immediate reward of action a in state s.
R = {
    "listen":     np.array([-1.0,  -1.0]),   # listening always costs 1
    "open-left":  np.array([-100.0, 10.0]),  # tiger-left: open-left is disaster
    "open-right": np.array([10.0, -100.0]),  # tiger-right: open-right is disaster
}

# Observation model Z[a][s', o]: P(observe o | next-state s', action a).
LISTEN_ACC = 0.85
Z_listen = np.array([[LISTEN_ACC, 1 - LISTEN_ACC],     # s'=tiger-left -> mostly hear-left
                     [1 - LISTEN_ACC, LISTEN_ACC]])    # s'=tiger-right -> mostly hear-right
# Opening a door resets the problem; observations become uninformative (0.5, 0.5).
Z_open = np.array([[0.5, 0.5], [0.5, 0.5]])
Z = {"listen": Z_listen, "open-left": Z_open, "open-right": Z_open}

# Transition: listen keeps the state; opening resets to a uniform 50/50 over states.
T = {
    "listen":     np.eye(2),
    "open-left":  np.array([[0.5, 0.5], [0.5, 0.5]]),
    "open-right": np.array([[0.5, 0.5], [0.5, 0.5]]),
}

def backup(Gamma):
    """One exact alpha-vector backup: Gamma (list of vectors) -> new set."""
    new_alphas = []
    for a in A:
        # For each observation, the best future alpha-vector is chosen per state s'.
        # Build, for every assignment o -> future alpha, the backed-up vector.
        # With |O|=2 and |Gamma| future vectors there are |Gamma|^2 assignments.
        for alpha_o0 in Gamma:                 # future plan if we observe o=0
            for alpha_o1 in Gamma:             # future plan if we observe o=1
                alpha = R[a].copy()            # immediate reward term R(s,a)
                for s in S:                    # add discounted future for each start state
                    fut = 0.0
                    for sp in S:               # sum over next states s'
                        fut += T[a][s, sp] * (
                            Z[a][sp, 0] * alpha_o0[sp] +
                            Z[a][sp, 1] * alpha_o1[sp])
                    alpha[s] += gamma * fut
                new_alphas.append((a, alpha))
    return new_alphas

def prune(alphas, grid=201):
    """Drop alpha-vectors that are never the max over a fine belief grid."""
    bs = np.linspace(0, 1, grid)
    keep = {}
    for b in bs:
        belief = np.array([b, 1 - b])
        a, alpha = max(alphas, key=lambda av: av[1] @ belief)  # winner at this belief
        keep[tuple(np.round(alpha, 6))] = (a, alpha)            # dedupe by value
    return list(keep.values())

# Value iteration: start from the zero vector and back up a few times.
Gamma = [np.zeros(2)]
for _ in range(8):                              # 8-step horizon
    raw = backup(Gamma)
    Gamma_pairs = prune(raw)
    Gamma = [al for (_, al) in Gamma_pairs]

# Evaluate value and best action across the belief simplex.
print("alpha-vectors after pruning:", len(Gamma_pairs))
for b in [0.0, 0.3, 0.5, 0.7, 1.0]:
    belief = np.array([b, 1 - b])               # b = P(tiger-left)
    a, alpha = max(Gamma_pairs, key=lambda av: av[1] @ belief)
    print(f"b(tiger-left)={b:.2f}  V={alpha @ belief:7.3f}  best action: {a}")

alpha-vectors after pruning: 23
b(tiger-left)=0.00  V= 14.355  best action: open-left
b(tiger-left)=0.30  V=  5.838  best action: listen
b(tiger-left)=0.50  V=  5.324  best action: listen
b(tiger-left)=0.70  V=  5.838  best action: listen
b(tiger-left)=1.00  V= 14.355  best action: open-right

The numeric payoff is the action map: confident beliefs trigger a door-opening, uncertain beliefs trigger listening. That is precisely the choosing-the-best-action-at-a-given-belief computation, and it is nothing but the max-inner-product lookup of subsection one. Now the library pair. The pomdp-py library (Zheng and Tellex, 2020) provides the Tiger model and a battery of solvers; Code 23.2.2 solves the same problem with its value-iteration solver in a handful of lines.

import pomdp_py
from pomdp_py.problems.tiger import TigerProblem  # built-in Tiger model

# Build the Tiger POMDP with an initial uniform belief over the two states.
init_true_state = "tiger-left"
init_belief = pomdp_py.Histogram({"tiger-left": 0.5, "tiger-right": 0.5})
tiger = TigerProblem(0.85, init_true_state, init_belief)  # 0.85 = listen accuracy

# Exact value iteration over the belief space (horizon 8, same as from scratch).
vi = pomdp_py.ValueIteration(horizon=8, discount_factor=0.95)
policy = vi.plan(tiger.agent)                  # solve: returns a policy tree

# Query the recommended action at a few beliefs.
for p_left in [0.05, 0.5, 0.95]:
    b = pomdp_py.Histogram({"tiger-left": p_left, "tiger-right": 1 - p_left})
    tiger.agent.set_belief(b)
    print(f"P(tiger-left)={p_left:.2f}  ->  action: {policy.plan(tiger.agent)}")

P(tiger-left)=0.05  ->  action: TigerAction(open-left)
P(tiger-left)=0.50  ->  action: TigerAction(listen)
P(tiger-left)=0.95  ->  action: TigerAction(open-right)

Read the two code blocks together. Code 23.2.1 implemented the alpha-vector backup, the grid-based pruning, and the value-and-action readout of subsections one and two by hand, roughly 60 lines. Code 23.2.2 reproduced the identical policy with about 8 lines of pomdp-py: the from-scratch backup-and-prune machinery collapses to two library calls, an order-of-magnitude line-count reduction, with the alpha-vector enumeration, dominated-vector pruning, and policy-tree construction all handled internally. The library also exposes SARSOP (point-based) and POMCP (online) solvers behind the same interface, so scaling from the toy Tiger to a thousand-state problem is a one-line solver swap, not a rewrite.

6. Summary and What You Can Now Do

This section turned the belief MDP of Section 23.1 into something solvable. The pivotal fact is the PWLC theorem: the optimal value function over the continuous belief simplex is the upper envelope of a finite set of alpha-vectors, so a function on an uncountable space reduces to bookkeeping over hyperplanes, and evaluating it is a max inner product. Exact value iteration over beliefs is correct but PSPACE-hard, its alpha-vector set exploding doubly exponentially in the horizon. Point-based methods (PBVI, Perseus, SARSOP) tame the explosion by computing value only at sampled reachable beliefs, the practical offline workhorse for moderate POMDPs. Online planners (POMCP, DESPOT) abandon offline solving entirely, running Monte Carlo tree search from the current belief with a particle filter, the same sequential Monte Carlo of Section 7.4, and so scale to enormous state spaces. The decision rule, exact for tiny, point-based for moderate-with-model, online for huge-with-simulator, sets up the bridge to Section 23.3, where model-free recurrent and state-space agents drop the explicit belief and learn a sufficient hidden state directly from reward. The Tiger solver, hand-rolled and then in pomdp-py, made every equation executable and showed the signature behavior of optimal POMDP control: gather information when uncertain, act when confident.

Concretely, you can now: represent a POMDP value function as alpha-vectors and read off value and best action by the max-inner-product rule; explain why exact solving is intractable and what point-based and online methods give up to scale; choose the right solver family for a given problem; and implement a small exact solver, then reach for pomdp-py, SARSOP, or DESPOT for anything larger. The next section, Recurrent and SSM-Based Agents for Partial Observability, takes the model-free road that this section's decision table pointed to.

7. Worked Example: Alpha-Vector Backup for the Tiger POMDP Intermediate

The alpha-vector backup equation and the PBVI update rule were stated in subsections one and two and executed by Code 23.2.1 in about 60 lines, but the code hides the arithmetic. This section strips every step down to arithmetic on small numbers so you can verify each calculation by hand and build the intuition that PBVI and SARSOP automate at scale. We work entirely in the two-state Tiger POMDP using the exact model defined in subsection five: states $S = \{\text{TL}, \text{TR}\}$ (tiger-left, tiger-right), actions $A = \{\text{OL}, \text{OR}, \text{L}\}$ (open-left, open-right, listen), observations $\Omega = \{\text{HL}, \text{HR}\}$ (hear-left, hear-right), discount $\gamma = 0.95$.

The step-by-step arithmetic above makes three things concrete that the code of Code 23.2.1 computes but does not narrate. First, the one-step policy thresholds ($b < 0.10$ for open-left, $b > 0.90$ for open-right) emerge directly from setting two alpha-vector lines equal: no optimization loop is needed, only high-school algebra applied to the reward differences. Second, the belief update compounds: two consistent hear-left observations drive the belief from 50% to 97%, crossing the action threshold and switching the policy, exactly the evidence-accumulation property that makes the POMDP listen before it acts. Third, the backup integral for action L collapses cleanly to $-1 - \gamma = -1.95$ because the listen sensor keeps both the state and the best future plan symmetric. Real POMDP problems break this symmetry across states and observations, which is why Code 23.2.1 enumerates all $|\Gamma|^{|\Omega|}$ assignments, but the arithmetic structure is identical to what you just traced by hand.

PBVI and SARSOP automate this three-step process across a set of sampled reachable beliefs. PBVI backs up every belief in $B$ each sweep, updating each belief's alpha-vector to the backed-up one with the highest value there, and periodically expands $B$ by simulating forward from the current best policy. SARSOP adds an upper bound on $V^*$ alongside the lower bound (the alpha-vectors), uses the gap to prioritize which beliefs to back up next, and prunes branches where the gap proves no reachable belief can benefit from further backup. In both cases the per-sweep cost is $O(|B| \cdot |A| \cdot |\Omega| \cdot |S|^2)$: linear in the number of sampled beliefs rather than doubly exponential in the horizon. The Tiger example finishes in milliseconds at an 8-step horizon because $|B|$ stays under 100 reachable beliefs; a thousand-state robotic navigation POMDP with SARSOP keeps $|B|$ in the hundreds to thousands, which is why point-based methods are the practical workhorse for moderate POMDPs while exact value iteration is reserved for teaching and tiny verification tasks.