Search and Belief-Space Planning › Summary

Search-based planning turns a world model into decisions by exploring selected action consequences rather than enumerating every future. Its result is only as reliable as the model, search coverage, and finite-budget statistics. A deployed controller therefore needs an explicit response to search timeout or invalid assumptions.

UCT-style MCTS replaces uniform expansion with a simulation budget allocated by a bandit rule. The four phases — selection, expansion, simulation, and backpropagation — implement that allocation. UCB-style scores balance sampled value against exploration, while PUCT adds a policy prior. Finite-budget search values and visit counts are different decision statistics, and implementations choose a final-action rule to match their training or control design. Progressive widening extends the scheme to large or continuous action spaces.

Planning under partial observability retains the latent physical state but replaces the planner's known-state input with a belief. Under the assumed model, the belief and any required finite-horizon time index are sufficient for control. When state, action, observation, and horizon are all finite, the optimal reward-maximizing belief value is piecewise linear and convex, with worst-case growth in its alpha-vector representation. QMDP and most-likely-state planning discard future uncertainty; point-based methods back up selected beliefs; online sampling methods plan locally from the current belief under a compute budget.

Belief trees and information gathering make the belief-space structure concrete. A belief tree branches on observations and can index its nodes by action-observation histories; the belief at a node is obtained by filtering along the path from the root. An informative action has task value when its observation changes later decisions enough to repay its sensing and transition costs; entropy reduction alone does not establish that value. The tiger problem isolates this effect through a listening region in which new information changes which door can be opened safely. POMCP samples latent states and observations from a generative model while indexing its tree by observable history.

Learned search guidance addresses finite-budget allocation. Priors enter PUCT selection, value estimates can replace default rollouts at leaves, and search visit distributions can supervise an amortized policy. In this seeded toy experiment, both the BFS rollout heuristic and the oracle-trained action prior reduce value error relative to uniform rollouts over the tested budgets; only the learned prior approaches the fully observed reference value. Because the network sees one-hot encodings of every state and exact tabular labels, the result demonstrates search guidance but not generalization.

Two threads carry forward. Policies Learned in Imagination and the Dreamer family amortize decisions learned through model interaction rather than running this tree search at every action. Active Perception, Dual Control, and Exploration develops the information-action tradeoff beyond the value-of-information framing used here. These methods share the objective-design lessons from Chapters 37 and 38 while representing alternatives and uncertainty differently.