Search and Belief-Space Planning › Limitations and Impact

Search-based planning gives a world model another useful interface: the planner can query a generative simulator without differentiating through it or enumerating its full state space. That makes tree search a natural option for discrete or hybrid choices and for partially observed problems represented by a sampling model. UCT connects bandit selection to Monte Carlo planning; AlphaGo and AlphaZero add learned priors and values. POMCP starts simulations from states sampled from the root belief and indexes its tree by action-observation histories. POMCPOW combines progressive widening with observation-likelihood-weighted particle filtering to address continuous action and observation spaces. These methods still require a usable simulator, a bounded search representation, and adequate coverage of high-value or safety-critical branches.

The limitations below are organized by mechanism, not by a claimed universal frequency ranking; their importance depends on the application.

Search can amplify model error. This is a central caveat for model-based search. MCTS preferentially explores the parts of the model where predicted value is highest. If model error makes a region look unusually good, search can find that region and allocate many simulations to it. This is the same failure mode we discussed under model exploitation in Model-Based Reinforcement Learning, and it interacts badly with partial observability because the belief update also depends on the model. A biased observation model can produce a biased belief and plan, with later observations feeding the same loop. Ensembles for uncertainty quantification (as in PETS, which we cover in PILCO, PETS, Ensembles, and MBPO) and pessimism under uncertainty can mitigate this problem but do not eliminate it. Optimistic model errors are especially damaging because the search procedure favors high predicted values.

The belief tree adds an observation-branching stage after each action. A complete action-observation layer has at most $|A||O|$ branches, but only positive-probability observations count at a particular belief. In our initial eight-cell belief, left and right each have three possible next signatures, while up and down each have one, for eight reachable action-observation pairs in total rather than $4\times8=32$. A continuous observation space has uncountably many possible values, while any sampled tree remains finite. Progressive widening and discretization, along with particle clustering, control representation size but can merge or miss decision-relevant observations.

Exact finite-horizon belief-MDP value iteration faces a doubly exponential pre-pruning candidate recurrence in the worst case, over a continuous belief simplex; the number of undominated vectors that remains is instance-dependent. Exact algorithms remain practical for some small structured problems; PBVI and SARSOP, along with online sampling, trade global exactness for selected beliefs or histories. If decision-relevant regions are not represented, the resulting policy can be poor there, so coverage and bound diagnostics should be evaluated explicitly.

Monte Carlo estimates can have high variance at small budgets, especially when return outcomes differ sharply across latent states and observation branches. In a controller, unstable action rankings can cause action switching, although the physical effect is application-dependent. More simulations, variance-reduced rollouts, learned leaf values, and deliberate tie-breaking or action-smoothing policies can help. Choosing by visit count reports the tree policy's allocation rather than the largest sampled mean; which final-action rule behaves better is problem- and budget-dependent.

Computational cost is a hard constraint in real control loops. A 50 Hz controller has 20 milliseconds per control interval. Our POMCP example uses 300 simulations per step with a cheap tabular generative model; replacing it with a neural simulator changes the cost according to batching, hardware, model size, and tree depth. Amortized policies and learned values shift some work from online search into training, but total online and offline cost is not fixed by a universal law. It must be measured for the chosen system and quality target.

Search trades online computation for action selection that is adapted to the current state or belief, provided the simulator is trustworthy on the branches being compared. An amortized policy may be preferable when latency is tight; online search may be valuable when the current belief changes the decision sharply. Safety-critical systems also need a defined failure response when search times out or its assumptions are violated. Whether that response is a fallback policy, safe stop, or supervisory controller is application-specific.