Search and Belief-Space Planning › Belief Trees and Information Gathering

We now know that the right information state for planning is the belief. A belief tree can be indexed by action-observation histories, with the posterior at each node stored explicitly or reconstructed from the root belief and model. POMCP uses the history-indexed form and represents those node beliefs with particles rather than dense vectors.

A history and root belief determine the corresponding posterior under a known model, so an algorithm need not store a dense belief vector at every node. POMCP goes further: it indexes nodes by histories and represents their beliefs through the latent-state particles delivered by simulations. The history alone is not a numerical belief; the root belief and the model, together with the filtering or particle procedure, supply the probabilities.

A belief tree alternates action edges and observation edges. A node is a history

$$h = (a_1, o_1, a_2, o_2, \ldots, a_t, o_t)$$

where $a_i$ is the action taken at step $i$, $o_i$ is the resulting observation, and $t$ is the history length in action-observation pairs. The belief at that node is $b(h) = P(\cdot \mid b_0, h)$, the posterior obtained by starting from root belief $b_0$ and applying the Bayes filter once per pair. From $h$, an action edge labeled $a$ leads to a chance node; from there, an observation edge labeled $o$ leads to the new history $h a o$.

The alternation of action edges and observation edges is the structural feature that separates a belief tree from a fully observed state tree. At a belief decision node there are up to $|A|$ action choices, and each action can lead to up to $|O|$ observation histories. Thus a complete action-observation layer can grow by at most $|A||O|$ before reachability and probability-zero branches are removed. A fully observed stochastic tree instead branches on successor states. Neither representation is uniformly smaller; the effective branching factor depends on the model and current support.

Two structural differences from the MDP tree change how the algorithm is implemented.

The first is that branching is on observations, not directly on latent next states. A fully observed state tree branches wherever the dynamics are stochastic. A belief tree branches when one action can produce different observations across states in the current belief. In our deterministic maze there are seven signatures globally. From the initial eight-cell signature-12 belief, left or right can produce three distinct next signatures, while up and down produce one. The corresponding fully observed transition from a known cell has one successor. Partial observability can therefore introduce observation branching even when physical dynamics and sensing are deterministic.

The second is that the same physical state can appear at many history nodes because the agent's information can differ. Before reachability pruning, a horizon of $t$ action-observation pairs permits at most $(|A||O|)^t$ histories. This is a worst-case count: zero-probability observations, merged beliefs, and sparse dynamics can reduce it sharply. Partial observability adds a curse of history to the continuous belief-state representation, which is why practical solvers sample, prune, merge, or restrict the histories they represent.

With the belief tree defined, information-gathering behavior becomes understandable. Consider a node $h$ and two actions $a_1$ and $a_2$ with identical expected immediate reward. The action values in the belief tree are

$$Q(h, a) = \rho(b(h), a) + \gamma \sum_{o \in O} P(o \mid b(h), a) \, V(h a o)$$

where:

• $\rho(b(h),a) = \sum_s b(h)(s)\,R(s,a)$: the expected immediate reward at belief $b(h)$
• $P(o \mid b(h),a)$: the probability of observing $o$ after taking $a$ from belief $b(h)$
• $V(h a o)$: the value of the successor history obtained by taking $a$ and observing $o$

An action that produces informative observations can create successor beliefs on which the agent chooses better continuation actions. Informativeness alone does not guarantee higher task value: the sensing cost, delay, state transition, and decision relevance of the observation all matter. When the expected improvement in later decisions exceeds those costs, the informative action wins without requiring a separate exploration bonus.

The continuation value $V(h a o)$ depends on the posterior used for later decisions. An observation is valuable when it separates hypotheses that call for different continuation actions. Posterior concentration by itself is not enough: learning a task-irrelevant detail can reduce entropy without changing the maximizing action or its value. In the exact belief-MDP backup, task-directed information value enters through observation-contingent continuation choices rather than through a separate generic information bonus. QMDP omits this mechanism because it assumes full observability after the current action.

For a fixed sensing action $a_{\mathrm{info}}$, the expected value of sample information compares choosing a continuation action after seeing its observation with committing to one continuation action beforehand:

$$\mathrm{EVSI}(a_{\mathrm{info}}) = \mathbb{E}_{o \sim P(\cdot \mid b(h),a_{\mathrm{info}})} \left[\max_{a'} Q_{\mathrm{cont}}(h a_{\mathrm{info}} o,a')\right] - \max_{a'} \mathbb{E}_{o \sim P(\cdot \mid b(h),a_{\mathrm{info}})} \left[Q_{\mathrm{cont}}(h a_{\mathrm{info}} o,a')\right]$$

where $Q_{\mathrm{cont}}$ evaluates the downstream action $a'$ after the sensing transition. Both terms use the same observation distribution. The first permits $a'$ to depend on $o$; the second requires one $a'$ before $o$ is known. Their difference is non-negative because an observation-contingent decision rule includes every constant decision rule as a special case. It is zero when some fixed continuation action is optimal for all observations with positive probability (allowing ties). The net value of sensing must additionally subtract the sensing action's reward cost and account for its state transition. This subtraction is what makes information gathering a tradeoff rather than a free win: an informative action that costs too much reward or moves you into a bad region will lose to a less informative but cheaper alternative.

The tiger problem, presented as a benchmark by Kaelbling, Littman, and Cassandra (1998), gives a compact demonstration of information gathering. You face two doors. Behind one is a tiger; behind the other is a reward of $+10$. Opening the tiger door gives $-100$. You cannot tell the doors apart, but you can listen for a cost of $-1$; the growl indicates the tiger's side with probability $0.85$. The classic continuing formulation resets the hidden tiger after a door is opened. For a compact calculation, this chapter uses an episodic variant in which opening either door terminates the episode.

With two latent states and two observation symbols, the tiger belief space is one-dimensional, so the episodic value function can be plotted directly. The useful qualitative feature is a region of beliefs in which paying for another observation improves the later door choice. Larger POMDPs can contain analogous information-gathering regions, but their geometry and even their existence depend on the task.

Let $p$ denote the belief that the tiger is on the left, and let $1-p$ denote the belief that the tiger is on the right. The belief space is one-dimensional, so we can approximate the belief-MDP value on a dense grid and look at the whole curve at once. The interpolation and stopping tolerance make this a numerical solution rather than a symbolic exact one, but its symmetry and convergence can be checked directly.

The belief space is one-dimensional here, which lets us draw the whole episodic solution. In a larger problem, information-gathering actions can be optimal on more complicated belief regions. The middle band in this example has a precise interpretation: listening leaves the physical state unchanged but produces an observation that can change the later door choice. Repeated sensing or motion in another task should be called information gathering only after checking the same counterfactual, not merely because the behavior looks hesitant.

We now need an algorithm that can search a belief tree without enumerating it. POMCP, introduced by Silver and Veness (2010), adapts MCTS to partially observable domains using a generative model and sampled latent states. Its central idea is worth stating on its own.

Instead of representing the belief explicitly, sample a state from it.

That is the core idea. POMCP maintains a tree whose nodes are indexed by action-observation histories. At the root, each simulation begins by sampling a single state from the current belief. From there the simulation proceeds like MCTS: select an action by UCB, sample a successor state from the model, sample an observation, and descend to the child indexed by that observation rather than by the latent state. Because different simulations sample different states, they can reach the same history node through different latent trajectories, and the node's accumulated statistics integrate over those sampled possibilities.

For a fixed policy and finite-variance return, independent Monte Carlo standard error scales as $O(n^{-1/2})$. POMCP uses root-state and transition-observation samples to approximate belief-space action values, but its tree policy adapts across simulations, so this elementary rate is not a finite-budget error guarantee for the full algorithm. Histories index the tree, while the sampled latent states reaching a history form its particle approximation.

The reasons this works are worth making explicit:

• The root particles are a belief sample. Each root simulation draws $s \sim b_0$. For a fixed rollout policy and finite horizon, a sample return is an unbiased Monte Carlo estimate under the generative model. Adaptive tree selection changes which policies are sampled, so finite-budget POMCP value estimates need not themselves be unbiased.
• The tree's history structure handles the observation branching automatically. You never have to enumerate observations; you sample one per simulation and let the tree grow where the samples land.
• The transition model is used as a generative model, not as an explicit matrix. You only need to be able to sample $s' \sim T(\cdot \mid s, a)$ and $o \sim Z(\cdot \mid s', a)$. This makes POMCP applicable when a neural or other simulator can generate those samples even though its transition density is unavailable or inconvenient to evaluate.

The action-value update is a running mean of the returns observed when that action was taken from that node:

$$V(h a) \leftarrow V(h a) + \frac{G - V(h a)}{N(h a)}$$

where:

• $V(h a)$: the running mean return for taking action $a$ at history node $h$
• $G$: the discounted return obtained along the current simulated path
• $N(h a)$: the number of simulations in which action $a$ was taken at history $h$

This is the incremental sample-mean update used in POMCP. The exact belief-MDP backup sums observation branches with weights $P(o\mid b,a)$, whereas POMCP samples them from a generative model. Silver and Veness prove convergence in probability of their value estimate to an $epsilon$-optimal value under the finite-POMDP, bounded-reward, UCT-exploration, and correct-simulator conditions stated in the paper. At small budgets, rare observation branches can remain noisy or unvisited. Model correctness includes both transition and observation behavior; an observation-model error can distort the root belief update as well as simulated continuation values.

Let us implement it. Because our transitions are deterministic, sampling from $T$ is a lookup; but the code is written as if $T$ were a general distribution, which is how you would write it for a learned model.