MCTS for POMDPs

Exact POMDPs are intractable. Online tree search makes them solvable in practice. The price: every modern POMDP solver depends on heuristics — and that's exactly where learning fits in.

Part 1 left us with a problem: belief space is infinite-dimensional, exact dynamic programming over it is hopeless, and even ε-approximate solutions are intractable for most non-trivial POMDPs. This post covers the workaround the field converged on, the algorithmic vocabulary the remaining two posts in this series depend on, and the gap that learning is meant to fill.

Stop solving the whole problem

The shift is from offline to online planning. Don't try to compute a global policy over all of belief space — you can't. Instead, at every step, build a small search tree from the current belief, pick the action that looks best in that tree, execute it, observe what happens, and repeat. The tree is small and disposable; the next step you build a fresh one from the new belief.

The tree's root is the agent's current belief. Each branch represents an action followed by some observation the world might produce. The whole tree is therefore an action-observation chain — a history.

Particle beliefs

Before we get to the algorithm, one representational trick. We never represent beliefs as explicit distributions over states — that would be intractable for any non-toy state space. Instead we keep a particle filter: a collection of sampled states drawn from the current belief. Updating the belief after an observation becomes weighting and resampling particles. This makes everything tractable in practice, because the bottleneck shifts from "represent the belief" to "sample enough particles."

You'll see this assumption baked into every solver below. The same warehouse Part 1 used: the agent doesn't know where the three packages are, but it has a few hundred candidate world configurations — particles — consistent with what it has observed so far.

POMCP — the canonical online POMDP solver

Partially Observable Monte Carlo Planning (Silver and Veness, 2010) is the workhorse. It adapts UCT — the same algorithm behind early AlphaGo — to belief space. The four phases of MCTS, slightly retargeted, look like this:

DESPOT — the "determinized" alternative

Determinized Sparse Partially Observable Tree (Ye, Somani, Hsu, and Lee, 2017) takes a different tack. Instead of sampling histories on the fly during search, DESPOT samples a small set of scenarios — entire deterministic worlds drawn from the initial belief — up front. The search tree is then built over those scenarios, with explicit regularization to avoid overfitting to the particular sample. The regularization coefficient trades tree size against estimated value, and theoretical analysis shows the resulting plan is near-optimal with high probability when the scenario sample is sufficient.

POMCP samples observations on the fly; DESPOT commits to a sample up front and searches more efficiently within it. Both have become standard baselines.

POMCPOW — continuous observations via progressive widening

POMCPOW (Sunberg and Kochenderfer, 2018) addresses one of POMCP's worst pathologies: continuous observation spaces. Vanilla POMCP creates a separate tree branch for every distinct observation encountered during simulation, so when observations are drawn from a continuous space — sensor readings, real-valued positions — every sample produces a new branch and the tree never gets to revisit anything. Progressive widening caps the number of observation branches at each node as a function of the visit count, adding new branches only when the existing ones have been explored enough. The tree stays compact without throwing away the statistical benefit of continuous sampling.

POMCPOW is the right choice when observations are high-dimensional or continuous — which is much of robotics, where a camera frame is the observation.

AdaOPS — adaptive bounds

AdaOPS (Wu et al., 2021) combines particle filtering with the adaptive branching strategy of heuristic search planners. At each tree node it maintains upper and lower bounds on the value function and refines those bounds through selective expansion. The bounds let AdaOPS prune clearly suboptimal actions early, focusing simulation effort on actions whose bounds still overlap. It is the bound-driven cousin of DESPOT and tends to be the strongest non-learning baseline on benchmark POMDP domains.

POMCP, POMCPOW, DESPOT, AdaOPS — together these define the current ceiling of non-learning online POMDP planning. They differ in sampling strategy and pruning mechanism but agree on the basic loop: build a tree from the current belief, decide via UCB-like statistics, execute the top action, re-plan from the new belief. They all share the same dependency on rollouts to evaluate leaf nodes.

The dependency that learning can replace

All four methods above need a way to assign a value to a leaf node. None of them computes that value exactly — the whole point of online planning is to avoid the exponential cost of exact computation. So they substitute. Random rollouts simulate forward from the leaf with a default policy until reaching a terminal or a horizon, and use the discounted return as the value estimate. Or they use hand-crafted bounds (AdaOPS) or hand-crafted heuristics (everything else when random rollouts aren't enough).

This is the crucial bottleneck. Random rollouts are unbiased but extremely high-variance — a single sample of the future barely tells you anything about a hard problem, so the planner needs many simulations per decision before the estimates stabilize. The HOO-POMDP experiments (Part 3) make this concrete: at 20 objects, the planner spends nearly half an hour per task, and most of that cost is rollout variance. The state abstraction in HOO-POMDP reduces the effective state space but does not remove the rollout dependency. POMCP still runs at every decision, still needs many particles, still rolls out from leaves.

The alternative is to learn what the rollouts are trying to estimate. Train a value network that predicts the leaf value directly from the belief, in a single forward pass. Train an action prior that biases the search toward promising actions. Both replace the noisy, expensive rollout estimate with a deterministic, cheap network call. This is exactly the AlphaZero recipe for board games — and exactly what GammaZero (Part 4) ports to POMDPs.

From "two strategies" to "abstraction reaches its limit, learning takes over"

Earlier framings of this series suggested two parallel research strategies for scaling POMDPs: abstraction and learning. With the heuristic-gap story above, the framing tightens.

• Abstraction (HOO-POMDP, Part 3) reduces the effective state space the planner has to reason over. It scales the problem to tractable sizes by collapsing irrelevant detail. But once the abstraction is in place, the inner loop is still POMCP — with random rollouts. Abstraction alone hits a wall: the rollouts become the dominant cost.
• Learning (GammaZero, Part 4) attacks the bottleneck directly. The rollouts are replaced by a learned value network; the search is biased by a learned policy. Crucially, the network is graph-based, so it generalizes across instance sizes — the same network can guide search on a small warehouse and on instances several times larger without retraining.

HOO-POMDP (Part 3) shows how far principled abstraction gets us. It scales to 20 objects, solves complex multi-room rearrangement under partial observability — but slowly. GammaZero (Part 4) takes the next step: same kind of problem, but with the rollout bottleneck removed, scaling improves significantly and per-decision cost drops by orders of magnitude. The story is sequential, not parallel.

With this post's MCTS skeleton in hand, the rest of the series follows the arc. Part 3 (HOO-POMDP) shows how far principled abstraction gets us — impressive, but bottlenecked by rollouts. Part 4 (GammaZero) removes the bottleneck via learning. Same warehouse with fog throughout.