Search and Belief-Space Planning

Imagine walking into a building you have never seen, with a hand-drawn floor plan someone gave you. The plan is roughly right. You have a model of the building (the floor plan), an observation (the weak flashlight), and an objective (the room). Your flashlight is weak, and the corridor ahead looks identical to the one behind you. You need to find a specific room, and you need to decide, right now, whether to walk forward, turn back, or stop and look around to figure out where you are.

That scenario contains the entire problem of this chapter. You have a model (the floor plan), an observation (the weak flashlight), and an objective (the room). Turning the model into an action requires something that neither the model nor the objective provides by itself. It requires a decision procedure for evaluating candidate actions or contingent policies and selecting what to do. In this chapter, that decision procedure is search.

Why does that procedure deserve an entire chapter of its own, when the previous chapters already gave us planners? Search allocates compute differently from the preceding planners, which can make it especially useful in some large, discrete, or partially observed problems. To see why, it helps to recall what the alternatives do with their compute.

Search-based planning sits alongside the two planning families you have already seen in this part. In Sampling-Based Planning and Model Predictive Control you saw planners that score sampled action sequences. In Differentiable Planning you saw planners that optimize one smooth action sequence by differentiating through latent state dynamics $z_{t+1}=f(z_t,a_t)$ and a cost over horizon $H$. Both can focus computation: adaptive shooting methods such as CEM refit their proposal distributions, and gradient methods follow local derivatives. Tree search focuses it differently. Each simulation updates branch statistics, and those statistics determine which branch receives the next simulation. This explicit, adaptive allocation is especially useful when the horizon is long, the choices are discrete, or the model is available only as a simulator. It does not imply that all search problems are nondifferentiable; it means tree search does not require derivatives from the simulator interface.

The simulator interface is worth stating precisely. Gradient planning needs derivatives through the model. Shooting methods and Monte Carlo tree search can instead use a generative model: given a state and action, sample a successor, reward, and, for a partially observed problem, an observation. Tree search is therefore a natural option when derivatives are unavailable and discrete branching matters, but its interface is not weaker than every shooting method's interface. Both families can work with forward samples; they differ in how they reuse those samples and allocate the next query.

The second half of the chapter addresses the harder half of the problem. The planner comparison immediately above assumed you know what state you are in. In the corridor, you do not. You know a distribution over states, which we have been calling a belief, and for which you built machinery back in Bayesian Filtering and Belief States. Planning with a belief as your starting point changes the problem in a way that is not merely quantitative. Actions that change what you can observe may become valuable even when they make little immediate physical progress. In this chapter you will see how to search over beliefs, how to recognize information-gathering behavior when it emerges, and how to make the search cheap enough to run inside a control loop.

That phrase "not merely quantitative" needs unpacking before we start. If uncertainty only made our estimates noisier, we could handle it with the same planning machinery and a little more caution. But uncertainty adds structure to the problem. It gives information a decision value that is absent when the relevant state is already known. An uncertain agent may have to trade task progress against observations that improve later choices, and a planner that cannot represent that tradeoff can miss good policies rather than merely attach noisier values to them. This is the sense in which the second half of the chapter differs from the first, even though the two share an algorithm.

The chapter proceeds as follows. We start with tree search and Monte Carlo Tree Search (MCTS), the workhorse algorithm that turns a simulator into a decision rule. We then confront partial observability and see why the MDP machinery breaks, which leads to the belief MDP and its difficult continuous state space. Next we build belief trees, the structures that let a planner reason about observations, and we work through the classic tiger problem to see information gathering emerge from expected value alone. We then put all of it together in a hidden-state maze where an agent has to infer its location while choosing movements. Finally, we replace hand-crafted heuristics with learned guidance and measure how a small neural network changes finite-budget MCTS in this maze. Throughout, we will keep model error, sampling error, and search confidence separate, because conflating them makes finite-budget results easy to overstate.

Before we can talk about searching over beliefs, we need the mechanics of searching over states. This section builds MCTS from the ground up: what problem it solves, why sampling is a reasonable answer, the four phases of the algorithm, the bandit theory underneath it, and the practical details that separate a working implementation from a minimal one. Even if you never implement MCTS yourself, the concepts here recur throughout the rest of the book: the difference between tree and default policies, the role of exploration bonuses, and the meaning of a backpropagated return. The belief-space algorithm later reuses MCTS selection, simulation, and backup, and adds history-indexed observation branching plus latent-state sampling from the current belief.

Recall from Markov and Partially Observable Decision Processes that a Markov decision process is a tuple $(S, A, P, R, \gamma)$, where $S$ is the state space, $A$ the action space, $P(s' \mid s, a)$ the transition kernel, $R(s, a)$ the reward, and $\gamma \in [0, 1)$ the discount factor. For the finite discrete case used below, the optimal value function satisfies the Bellman optimality equation:

$$V^*(s) = \max_{a \in A} \left[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V^*(s') \right]$$

where:

• $V^*(s)$: the maximum expected discounted return obtainable from state $s$
• $R(s,a)$: the expected immediate reward for taking action $a$ in state $s$
• $P(s' \mid s,a)$: the probability of successor state $s'$ under the transition model
• $\gamma \in [0,1)$: the discount factor

If you can evaluate the right-hand side exactly, you can solve for $V^*$ by dynamic programming, as we did for the grid world in Classical Planning and Optimal Control. An exact tabular solution requires enumerating $S$ and iterating until convergence, and both scale badly. For factored state variables, the number of joint assignments grows exponentially; a few dozen binary features already yield billions of states, while a continuous space cannot be tabulated at all. But there is a second way to use the Bellman equation: not to solve for the whole function $V^*$, but to answer a single question about a single state. Given a state $s$, which action $a$ maximizes the right-hand side?

That reframing is the key move. You do not need to know $V^*$ everywhere. You need to know it at the states that arise from your current situation, and ideally only at those. Everything MCTS does follows from taking that observation seriously. The value function is a book with pages for every state in the world, most of which you will never read; MCTS is a procedure for reading only the pages you need. It is guided by the assumption that you do not need many of them.

The naive way to exploit it is a depth-limited expectimax tree. From the root state $s_0$, expand every action, then every successor with nonzero probability, then every action from there, and so on to depth $d$. If each state has $b_A$ available actions and each state-action pair has at most $b_S$ possible successors, the tree can have $(b_A b_S)^d$ leaves. In a deterministic 6-by-6 grid, $b_S=1$ and four actions already produce $4^{20} \approx 1.1 \times 10^{12}$ length-20 action sequences before transpositions or pruning. Even this tiny domain therefore yields roughly a trillion candidates, each of which requires model transitions and value bookkeeping rather than a single machine instruction. The point is not merely that we need a faster computer; uniform enumeration spends its effort in the wrong shape for this problem.

MCTS addresses this by refusing to build the tree uniformly. Instead of expanding every branch to depth $d$, it runs a fixed number of simulations, each of which walks from the root down to a leaf along a policy that balances exploitation of branches with strong sampled returns against exploration of under-sampled ones, evaluates the leaf cheaply, and then updates statistics along the visited path. The represented tree is therefore usually asymmetric. Its exact shape reflects the selection rule, the rollout or leaf evaluator, the model, and the finite budget; an initially misleading estimate can direct substantial work toward a poor branch before later evidence corrects it.

Each MCTS simulation executes four phases in sequence.

1. Selection. Starting at the root, repeatedly choose the child that maximizes the tree policy. The tree policy is what makes MCTS work, and we will spend most of this section on it. Selection stops when you reach a node that has not been fully expanded, or a terminal node. Because each step of selection moves one level down the tree, a single simulation visits $O(\text{depth})$ nodes, and the tree policy is consulted at each one.

2. Expansion. If the selected node is not terminal and has unexpanded actions, add one or more children. A common choice is to add all $|A|$ children at once and mark the node fully expanded. You can also add children lazily, one per visit; this matters when $|A|$ is large, and we will return to it. When child creation evaluates the model, eager expansion can require up to $|A|$ model queries, many for children that may never be revisited. Laziness delays that work until a child is needed.

3. Simulation (rollout). From the newly created node, simulate a trajectory using some default policy, such as uniform random actions or a cheap heuristic, until you hit a terminal state or a depth limit. Sum the discounted rewards to get a return estimate $G$. In rollout-based MCTS, this phase evaluates what lies beyond the explicit tree; other variants use a learned or heuristic leaf evaluator instead. A random default policy often produces noisy leaf values, while an accurate goal-directed heuristic can reduce that variance.

4. Backpropagation. Walk back up the path you came down, incrementing visit counts $N$ and updating the running mean return $Q$ at each visited node or edge. Every visited ancestor receives an update on that simulation; the update does not guarantee that its finite-sample estimate becomes more accurate.

The distinction between the tree policy (used during selection, inside the tree) and the default policy (used during simulation, outside the tree) is central. The tree policy can afford more computation per decision because it is applied only along the explicit-tree prefix and its job is to allocate future simulations well. The default policy is applied throughout the remaining rollout for every simulation, so its cost is multiplied across many simulated steps. The useful balance depends on depth, branching, simulator cost, and how much a better tree or default policy changes return variance and action ranking.

The tree policy treats action selection at each node like a multi-armed bandit problem. Each selected edge produces a sampled downstream return, and the selection rule balances exploiting actions with high observed returns against exploring actions with little evidence. A canonical rule is UCB1 (Auer, Cesa-Bianchi, and Fischer, 2002):

$$a^* = \arg\max_{a} \left[ \bar{Q}(s, a) + c \sqrt{\frac{\ln N(s)}{N(s, a)}} \right]$$

where:

• $\bar{Q}(s,a)$: the running mean return observed when action $a$ was tried from $s$
• $N(s)$: the number of times node $s$ has been visited
• $N(s,a)$: the number of times action $a$ has been tried from $s$
• $c$: the exploration constant controlling the size of the uncertainty bonus

The expression is evaluated only after every available action has been visited at least once; implementations usually force unvisited actions to be selected before applying it. Read the score as a conversation between two terms. The first term, $\bar{Q}(s,a)$, is exploitation: it prefers actions that have paid off so far. The second term is exploration: it grows when $N(s,a)$ is small relative to $N(s)$, so an action that has rarely been tried gets a large bonus. The logarithm in the numerator means the bonus grows slowly. Kocsis and Szepesvári (2006) applied upper-confidence selection recursively in a search tree and called the result UCT. They proved consistency for the finite-horizon and discounted MDP settings analyzed in their paper; the result depends on bounded rewards, a correct generative model, and sufficient exploration.

The bonus has the shape of a concentration bound. In the stationary bandit setting used to derive UCB1, uncertainty shrinks roughly as $1/\sqrt{N(s,a)}$, while the $\ln N(s)$ term makes an under-sampled action eligible again as the parent is revisited. The coefficient $c$ absorbs the reward range and the desired confidence level. Recursive tree search is more delicate than an independent stationary bandit at every node because the return distribution changes as policies deeper in the tree change. UCT's consistency analysis handles that coupling under its stated assumptions; the single-node UCB1 regret guarantee should not be copied to every node without those conditions.

UCT has one important weakness for our purposes. The exploration bonus has no place to insert side information about which actions are likely to be good. If a learned policy assigns most of its probability to one action, plain UCT does not use that ranking: it normally gives every legal action an initial visit and then allocates later visits from sampled returns and counts alone. With hundreds of legal moves, those mandatory first visits can consume much of a small simulation budget even when a useful prior is available.

PUCT fixes this by multiplying the exploration term by a prior $P(s,a)$:

$$a^* = \arg\max_{a} \left[ \bar{Q}(s,a) + c \, P(s,a) \frac{\sqrt{N(s)}}{1 + N(s,a)} \right]$$

where:

• $P(s,a) \in [0,1]$: the action prior, normally produced by a policy network, indicating how promising action $a$ looks before any search statistics are collected
• $c > 0$: PUCT's exploration coefficient, playing the same qualitative role as the UCB coefficient (though the two formulas have different scales, so their numerical values are not interchangeable)

The denominator $1 + N(s,a)$ makes the prior-weighted bonus decay relative to repeated visits to the same action. AlphaGo and AlphaZero use closely related prior-guided tree policies, with implementation-specific coefficients and root exploration. We will return to that design in the final section and in MuZero and Value-Equivalent Models.

The PUCT score combines three signals. The prior $P(s,a)$ says how promising the action looks before search at this node. The running mean $\bar{Q}(s,a)$ summarizes sampled returns, and $N(s,a)$ records how often the edge has been visited. High-prior actions receive a larger early exploration bonus; repeated visits reduce that bonus relative to alternatives. A positive prior and continued exploration can let later return evidence override an imperfect ranking. A zero prior is different: in the displayed formula it gives no exploration bonus, so implementations commonly add root noise, probability floors, or forced initial visits. PUCT is a knowledge-guided selection rule, not a general guarantee of using fewer simulations than UCT.

When a simulation returns a discounted return $G_{\text{rollout}}$ from the leaf, that value is the return from the leaf. But the node statistics you need to update are indexed by the path from the root. If the path is $n_0 \to n_1 \to \cdots \to n_k$ and $r_i$ is the reward received when entering node $n_i$, then the return from node $n_i$ is defined recursively:

$$\begin{aligned} G_k &= G_{\text{rollout}} \\ G_{k-1} &= r_k + \gamma G_k \\ G_{k-2} &= r_{k-1} + \gamma G_{k-1} \\ &\;\;\vdots \\ G_i &= r_{i+1} + \gamma G_{i+1} && \text{(general recursive step)} \end{aligned}$$

where:

• $G_i$: the return backed up to node $n_i$, obtained by working backward from the leaf
• $r_{i+1}$: the reward on the transition from $n_i$ to $n_{i+1}$
• $\gamma$: the discount factor
• $G_{\text{rollout}}$: the leaf evaluation or remaining rollout return at node $n_k$

Working backward along the path and adding each corresponding $G_i$ to node $n_i$ gives the correctly indexed discounted sample return. Backing up the root return unchanged to every node instead shifts the reward timing and biases deeper-node estimates. This matters because selection compares deeper-node values against each other, and a systematic shift in those values biases the search. A buggy implementation can still populate a tree and sometimes reach the goal, so the defect may surface as inefficient allocation or different action choices rather than a crash.

Once you have them, the node statistics are simple running averages:

$$\bar{Q}(n, a) = \frac{1}{N(n,a)} \sum_{i\,:\, (n,a) \in \text{path}_i} G^{(i)}_{n}$$

where:

• $N(n,a)$: the number of simulations in which action $a$ was taken from node $n$
• $G^{(i)}_{n}$: the discounted return from node $n$ recorded on simulation $i$
• the sum runs over simulations $i$ whose selected path passed through the edge $(n,a)$

This estimator is a sample mean of returns generated by the search procedure; it is not automatically an unbiased estimate of $Q^*(s,a)$. The tree policy and leaf evaluation change as the tree grows, so the samples are neither identically distributed nor drawn from the final policy. Uneven action sampling alone does not bias the conditional mean for an edge, but adaptive downstream policies, finite horizons, and approximate leaf values can. Treat a finite-budget MCTS $Q$ as a search statistic tied to a particular algorithm and budget, not as a calibrated critic unless calibration is checked separately.

When the budget runs out, you need to pick an action. Two options:

• Most-visited child. Return $\arg\max_a N(s, a)$. This convention reports which action received the largest allocation under the configured tree policy and budget.
• Highest-value child. Return $\arg\max_a \bar{Q}(s,a)$. This convention reports the largest sampled mean and can be sensitive to actions supported by very few visits.

Many implementations choose the root action by visit count while using value estimates inside the tree. Both statistics reflect returns propagated through a subtree, but they answer different questions. $\bar{Q}(s,a)$ is the observed mean for one edge; $N(s,a)$ records how often the selection rule returned to that edge after comparing it with alternatives. A high value supported by two visits is fragile, while a large visit count can still be wrong when the prior, exploration rule, or model is biased. Visit count is an allocation statistic, not a calibrated confidence probability.

The visit distribution at the root can itself serve as a policy or a policy-training target. AlphaZero uses $\pi(a) \propto N(s_0,a)^{1/\tau}$ as a search-policy target, where $\tau$ is a temperature. If a search allocates 80% of its simulations to one action, that is a strong preference under that search configuration and budget. We will exploit this in the Policies Learned in Imagination chapter. The temperature $\tau$ controls how sharp the distribution is: at $\tau = 1$ you take the raw visit proportions, at $\tau \to 0$ you get a one-hot distribution when the most-visited action is unique (ties require an explicit rule), and larger $\tau$ flattens the distribution. A training scheme may use a higher temperature while collecting exploratory data than at deployment, but the schedule is a design choice rather than a property of MCTS itself.

The scheme above assumes that expanding a node means adding all $|A|$ children. That can be manageable when $|A|$ is four and each child is cheap to instantiate. It is impossible to enumerate when $A$ is a continuous set, such as a bounded subset of $\mathbb{R}^7$, and costly when the discrete action set contains hundreds of moves. Progressive widening (Coulom, 2007; later refined by Auger, Couëtoux, and Teytaud, 2013) limits the number of instantiated children after $N$ visits to

$$k(N) = \lceil c_w N^{\alpha} \rceil$$

where:

• $k(N)$: the number of children the node is allowed to have at visit count $N$
• $c_w > 0$: the widening constant that sets the overall rate of growth
• $\alpha \in (0,1)$: the widening exponent controlling how quickly the child budget broadens

The constants are problem-dependent; $\alpha=0.5$ is a common starting point, not a universal default. Early visits instantiate few children and go deep; later visits broaden as the budget grows. POMCPOW (Sunberg and Kochenderfer, 2018) applies progressive widening to sampled actions and observations so a finite search tree can be used in continuous spaces. Widening does not by itself ensure that an optimal continuous action is ever sampled. That conclusion additionally requires an action proposal with suitable support and regularity assumptions. The practical tradeoff is depth against coverage: a slow schedule gives each instantiated child more visits, while a fast schedule covers more candidates with fewer samples per child.

Let us now build the MCTS algorithm. The first cell binds shared plot-style helpers alongside computation imports. Figure construction remains in the later visualization cells, while arrays and statistics are prepared beforehand.

The left panel shows that repeated closed-loop search reaches the goal in this seeded run: the guided rollout follows the ten-step route, while the uniform rollout takes thirteen steps. The right panel explains why this one trajectory should not be mistaken for a well-resolved root estimate. The 400-simulation search spreads visits nearly evenly, including across the two wall-bumping actions. Closed-loop replanning recovers a useful action sequence here even though each individual uniform-rollout search remains uncertain. Read visits and values together: the visit count records the selection rule's allocation, while the value is the sampled mean return on an edge. Neither is a calibrated confidence measure.

We can compare finite-budget root estimates under uniform and guided rollouts. The experiment below measures absolute error relative to $V^*(\text{START})$ over eight seeds. It tests these two implementations on this maze; it does not establish a general sample-complexity result.

The experiment demonstrates a narrower practical point: guidance can materially change finite-budget search. A better rollout policy, leaf evaluator, or action prior can reduce the simulations needed for a chosen decision-quality target, but only when its extra evaluation cost and errors are included. Unguided search remains useful in some domains; guidance changes its sample efficiency rather than defining whether search has value.

One caveat before we move on. Both curves in the first panel are relative to $V^*$, the value of the fully observed MDP. That is the right benchmark here, but it stops being the right benchmark the moment we take away the agent's knowledge of its own state, which is exactly what we do next. Under partial observability, "estimated minus optimal" would compare a belief-conditioned value estimate with a fully observed state value, so the comparison would no longer mean the same thing. Keep this in mind as you read the next section; the numbers are still informative, but they measure a different quantity.

The key MCTS parameters in this section are:

• n_sims: Number of simulations per planning call. Controls online cost and often improves decision quality, but finite-budget estimates need not improve monotonically.
• c: Exploration coefficient in the tree policy (UCB1 and PUCT). Larger values encourage exploring under-visited branches.
• max_depth: Maximum simulated horizon. Bounds the cost of each simulation and prevents infinite loops.
• prior: PUCT action prior. Concentrates search when informative, but can suppress exploration if overly confident.
• rollout policy: Default policy used inside simulations. A cheap, accurate heuristic can reduce the simulation budget for a chosen quality target, while a biased heuristic can steer estimates in the wrong direction.

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.

Starting from true cell $(0,1)$, each right action produces the displayed signature and prunes the posterior support from eight cells to five, then two, then one. This is filtering under a fixed, physically consistent action-observation sequence. It shows how motion can disambiguate aliased positions; deciding whether that information is worth the motion is the planner's separate job.

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.