Search and Belief-Space Planning › Planning Under Partial Observability

Everything in the previous section assumed the planner knows the state $s$. In a maze rendered as a grid of characters, that assumption is invisible because it is satisfied by construction. Many real systems violate it: a robot may have a drifting odometer, a dialogue agent may not know what the user knows, and a recommender may not know what the user has already seen. This section explains why that violation is not a technicality and what replaces the MDP.

The physical state $s_t$ does not become a distribution; it remains the latent state of the environment. What changes is the planner's information state. The planner replaces direct access to $s_t$ with a belief $b_t$ over possible states, evaluates a belief value $V^*(b_t)$, and combines prediction with Bayesian conditioning. Under the assumed POMDP model, the belief is a controlled Markov information state, so Bellman reasoning can be applied in belief space.

Recall from Markov and Partially Observable Decision Processes that a partially observable MDP adds an observation space $O$ and an observation model $Z(o \mid s', a)$ to the MDP tuple: $(S, A, O, T, Z, R, \gamma)$. After taking action $a$ in state $s$, the environment moves to $s' \sim T(\cdot \mid s, a)$ and emits $o \sim Z(\cdot \mid s', a)$. Critically, the agent sees $o$ but not $s'$.

The immediate consequence is that the planner cannot index its decision by one known physical state. Suppose the agent assigns probability to both $(0,2)$ and $(2,2)$, two cells with the same local wall signature. Moving right is on the goal route from $(0,2)$ but moves toward the dead-end branch from $(2,2)$. Planning from an arbitrarily chosen candidate discards both the belief weights and the way future observations can separate the candidates. Its error rate is not generically one half; it depends on the belief, on the rewards, and on the candidate-state action values.

A second consequence is subtler and, for planning purposes, more important. Once actions can change what you know, an action may be valuable partly because of its observations. Turning around in a corridor may earn no immediate reward, and may even cost time, but it may tell you which way is north. A fully observed MDP planner has no information term with which to value that effect; it would choose the same physical motion only for its transition and reward consequences. In a POMDP, later decisions can make information valuable. This is the structural shift we flagged in the introduction: uncertainty can make policies that pay to observe outperform policies that only chase immediate task progress.

The standard resolution is to change what the planner treats as a state. Instead of planning over $S$, plan over the space of probability distributions over $S$. This space is called the belief space and is denoted $\Delta(S)$; an element $b \in \Delta(S)$ assigns a probability $b(s)$ to each state. You built the machinery for computing $b$ from observation histories in Bayesian Filtering and Belief States. Here we use it as the substrate for planning.

The mathematical shape of $\Delta(S)$ contrasts sharply with $S$. When $S$ is finite with $|S| = n$, $S$ is a set of $n$ discrete points, but $\Delta(S)$ is the $(n-1)$-dimensional simplex, a continuous space whose dimension is one less than the number of states. The three-state case gives a triangle; the four-state case gives a tetrahedron; the twenty-two-state case, which is our maze, is a twenty-one-dimensional polytope that we can only visualize through projections. Even a small discrete state space therefore induces a continuous belief space, one major source of POMDP planning complexity alongside action-observation branching and horizon.

The key fact is that a correctly updated belief is sufficient for predicting future rewards and observations under future actions. The belief need not preserve the literal history; it preserves the history's decision-relevant probabilistic information under the assumed model. This means the POMDP induces an MDP over $\Delta(S)$, with:

• Belief states: $b \in \Delta(S)$.
• Actions: the same $A$.
• Belief reward: $\rho(b, a) = \sum_{s} b(s) \, R(s, a)$, the expected immediate reward.
• Belief transition: $\tau(b' \mid b, a)$, defined below.

The belief transition is the composition of a prediction step and a Bayesian correction. The prediction step propagates belief through the dynamics:

$$\hat{b}(s') = \sum_{s} T(s' \mid s, a) \, b(s)$$

Here $b(s)$ is the current probability of state $s$, $T(s'\mid s,a)$ is the transition probability after action $a$, and $\hat b(s')$ is the predicted probability of successor $s'$ before seeing the next observation.

The probability of observing $o$ under this predicted belief is

$$P(o \mid b, a) = \sum_{s'} Z(o \mid s', a) \, \hat{b}(s')$$

Here $Z(o\mid s',a)$ is the likelihood of observation $o$ after arriving in $s'$, and the sum marginalizes the unobserved successor state.

The corrected belief is then Bayes' rule applied cellwise:

$$b'(s') = \frac{Z(o \mid s', a) \, \hat{b}(s')}{P(o \mid b, a)}$$

The denominator must be positive; a zero-probability observation is outside the conditioning event. The result $b'(s')$ is the posterior probability of successor state $s'$. Before the observation is seen, the next belief is a random variable because different possible observations induce different posteriors. This remains true in our maze even though both the physical dynamics and sensor are deterministic: uncertainty about the current latent cell induces uncertainty about which deterministic successor and signature will occur. Once the action and observation are fixed, the Bayes update itself is deterministic.

Three properties of the belief MDP are worth keeping in mind.

First, an optimal policy can be expressed as a function of the current belief under the standard POMDP assumptions. For a finite horizon it may also depend on the remaining time; for an infinite-horizon discounted problem, a stationary belief policy can be optimal under the usual conditions. The belief is therefore a sufficient information state for control. We discussed sufficient state in Sufficient State and State Abstraction. A controller need not retain the full history when it can update the exact belief and any required time index.

Second, for a finite-state, finite-action, finite-observation POMDP with a finite horizon and expected-reward maximization, the optimal belief value function is piecewise linear and convex in $b$. This means $V^*(b) = \max_k (\alpha_k \cdot b)$ for a finite set of alpha vectors $\alpha_k \in \mathbb{R}^{|S|}$, where $\alpha_k \cdot b = \sum_{s} \alpha_k(s)\, b(s)$ is the inner product of the $k$-th vector with the belief. Each alpha vector represents a conditional plan, and the maximizing vector defines a region of belief space. This structural result (Sondik, 1971; Smallwood and Sondik, 1973) underlies exact finite-horizon POMDP methods. The convexity is what makes the structure exploitable: the value function is the upper envelope of a family of linear functions, and the choices of optimal action correspond to the faces of that envelope. A piecewise-linear convex value function is a much more constrained object than a general one, and in principle it can be computed exactly.

Third, the exact representation grows quickly in the worst case. Before pruning, the standard finite-horizon backup can generate a number of candidate alpha vectors that is doubly exponential in horizon when there is more than one observation; the number that survives pruning is problem-dependent. The belief space is also a simplex of dimension $|S|-1$ rather than a finite collection of states. Pruning helps, but exact methods become impractical as the state, action, observation, or horizon sizes increase. The two-state tiger problem is useful because its belief space is one-dimensional and can be visualized. State count alone does not determine the number of surviving alpha vectors; the structure of transitions, observations, rewards, and horizon also matters.

Large POMDPs usually require approximations, while exact belief-space methods remain useful for small finite problems. It helps to organize approximations by what they discard and to ask which discarded structure is least costly for the problem at hand.

Throw away uncertainty. The crudest family. QMDP computes the MDP Q-function and then evaluates actions by their expectation under the belief:

$$Q_{\mathrm{QMDP}}(b, a) = \sum_s b(s) \, Q^*(s, a)$$

Here $Q^*(s,a)$ is the optimal fully observed MDP action value and $b(s)$ weights each possible state. This is fast but structurally incapable of valuing future information, because it assumes that uncertainty disappears after the current action. For reward maximization, granting the controller that extra future information makes the QMDP value an optimistic upper bound on the corresponding POMDP value, not a lower bound. The resulting policy can favor actions that work only under the assumed future certainty. The observation model does not appear in the QMDP expression, so an otherwise reward-neutral sensing action receives no credit for improving later decisions. QMDP could still select an action called peek for its modeled reward or state transition, but not for the observation it supplies.

A close cousin is most-likely-state planning: take $\hat{s} = \arg\max_s b(s)$ and plan as if $\hat{s}$ were known. It is cheap and reuses an MDP planner, but it discards probability mass on every other state and cannot value observations. It can be adequate when the belief is tightly concentrated and nearby states have similar action values. A multimodal belief is a warning sign rather than a proof of failure: the approximation fails when plausible modes favor materially different actions.

Throw away most beliefs. Point-based methods apply backups at a finite set of representative beliefs rather than across the full simplex. PBVI (Pineau, Gordon, and Thrun, 2003) uses explorative stochastic trajectories to select belief points. SARSOP (Kurniawati, Hsu, and Lee, 2008) focuses sampling on an approximation to the beliefs reachable under optimal policies, not specifically on the boundary of the reachable set. HSVI (Smith and Simmons, 2004) maintains upper and lower bounds and directs trials using those bounds. These methods can produce alpha-vector policy representations. Their tractability depends on more than the raw dimension: reachable-set geometry, sparsity, action and observation counts, and the required error tolerance also matter. A finite sample of reachable beliefs can greatly reduce work, but it can miss decision-relevant regions and therefore does not preserve the instance's optimum automatically.

Throw away the global offline policy. Online methods plan from the current belief with a fixed compute budget, execute one action, and plan again. They may still use a fixed finite search depth or discounted infinite-horizon objective. If the planner only needs the next action, it can concentrate on beliefs reachable from the current one. The belief tree still branches over observations, so sampling and, in continuous spaces, observation progressive widening are used to keep the represented tree finite. POMCP is one online sampling approach.

Let us build the POMDP version of the maze. We keep the deterministic dynamics and replace the position sensor with a local wall signature: the agent perceives a four-bit pattern saying which of its four neighbors are blocked. Many cells share a signature, so the sensor is ambiguous rather than noisy. Ambiguous sensors are useful here because they separate two kinds of partial observability that learners often conflate: noise (the same state produces different observations on different visits) and aliasing (different states produce the same observation). Our maze has only aliasing, and every observation is produced deterministically by its state.