Planning Under Uncertainty

A four-part series (plus epilogue) on planning when the agent can't see the full state — POMDPs, belief tracking, online tree search, and the two strategies (abstraction and learning) that make large partially-observable problems tractable.

Why this series exists

Classical planning assumes you know everything. The sibling series, Learning for Planning, lived inside that assumption: same warehouse with a robot and packages, but the robot saw it all. That series spent four posts on the scaling problem alone.

Real agents almost never see everything. A robot tidying a house can't see through walls. A warehouse robot picking the next aisle can't see what's in the rest of the building. The state of the world is what it is — but the agent only ever has a probability distribution over it. That distribution is the agent's belief, and planning against a belief is much harder than planning against a state.

This series covers the formalism (POMDPs), the algorithmic toolkit the community converged on (POMCP, DESPOT, online tree search with particle filters), and the two parallel research paths that make large POMDPs solvable: abstraction (HOO-POMDP) and learning (GammaZero, the partially-observable cousin of GABAR from the LFP series).

Same warehouse, with fog. All four posts use the same warehouse from the LFP series — a robot delivering packages between zones A, B, C, D — with one change: the robot can only see its current zone. Post 1's animated counter shows what that change costs: the belief space, even before approximation, hits 10¹⁵+ effective configurations.

The roadmap

Four parts + an epilogue, two paper anchors, one foggy warehouse

Planning When You Can't See the Whole World the setup

Belief states, Bayesian updates, and why partial observability is computationally brutal. Side-by-side animation: the same 16-zone warehouse, with and without fog. Counter climbs from 1K to 10¹⁵+ belief states. PSPACE-completeness, but visceral.

MCTS for POMDPs survey

The non-learning baselines GammaZero competes against: POMCP, DESPOT, POMCPOW, AdaOPS. Particle beliefs, the 4-phase MCTS loop, and the rollout-evaluation bottleneck that every one of them inherits. This is where the "we need learning" argument originates.

Teaching Robots to Tidy Up (HOO-POMDP) paper deep-dive

Paper deep-dive. Hierarchical Object-Oriented POMDP for multi-object rearrangement scales to 20 objects via principled object-oriented belief factorization. But each decision still runs POMCP with random rollouts — nearly half an hour per task at 20 objects. This is the ceiling principled abstraction can reach with classical search inside, and the motivation for GammaZero.

GammaZero — Your Belief About the World Is a Graph paper deep-dive

Series finale and main paper deep-dive. Replaces POMCP's random rollouts with a learned value+policy network (the AlphaZero recipe for POMDPs). Crucially, the network is a GNN over a belief graph, so the same trained network handles POMDPs of any size — fixing BetaZero's fixed-dimensional bottleneck. Full lineage covered: AlphaZero, MuZero, BetaZero, ConstrainedZero, LeTS-Drive, GABAR.

Epilogue — Open Questions looking forward

What HOO-POMDP and GammaZero don't yet do, where the next decade of partially-observable planning is heading, and how this all eventually connects to LLM agents, foundation models, and large-scale robotics deployments.

The two paper anchors and how they relate

This series has two papers, not one. They're not competitors — they take opposite tacks on the same wall.

HOO-POMDP (Post 3) — shrink the problem. Use principled hierarchical abstraction to reduce the effective state space until a classical solver can handle it. Object-oriented belief factorization is the key trick. Works without learning.
GammaZero (Post 4) — keep the problem large; learn to navigate it. Train a GNN on solved small POMDPs; deploy on larger ones. Inherits the GABAR recipe from the sibling series and extends it to belief space.

Both posts are also readable standalone as paper deep-dives (under the "My Research" tag), without requiring Posts 1-2. Posts 1-2 are there to anchor the broader context.

Who this is for

The LFP series reader

You read Learning for Planning. This series is the natural next chapter — same warehouse, same scaling story, now with partial observability. Skim Post 1, dive into Posts 3 and 4.

The POMDP-curious reader

You know POMDPs exist but not the modern algorithmic landscape. Read all four posts. Post 1 gives the formalism; Post 2 is the toolkit; Posts 3 and 4 are two ways to attack the heuristic gap that Post 2 reveals.

The robotics reader

You operate robots in environments where state is uncertain — manipulation under occlusion, household tasks, exploration. This series is most directly about your problem. HOO-POMDP (Post 3) is especially relevant for object-rearrangement tasks.

Reading paths

Linear (recommended for first read): 01 → 02 → 03 → 04 → Epilogue. About 2 hours including time spent on visualizations and side notes.
Papers only: Skip to Post 3 (HOO-POMDP) or Post 4 (GammaZero). Each works standalone with a small "Series context" sidebar to orient you.
Bridge from LFP: If you came from LFP's epilogue, start at Post 1 here — it intentionally references the warehouse you've been reading about. Then jump to Post 4 (GammaZero) for the direct GABAR cousin.

What you won't find here

No exhaustive POMDP textbook. Kaelbling, Littman, Cassandra (1998) is the classical reference; Kochenderfer's POMDPs book (2022) is the modern one. This series covers the parts those texts treat as "implementation details."
No deep-RL for POMDPs. R2D2, IMPALA, and recurrent policy gradients are real but live in a different ecosystem (offline RL, model-free) than the model-based MCTS framing this series uses.
No simulator tutorial. The visualizations are conceptual; the actual experiments in HOO-POMDP and GammaZero use POMDP simulators we won't be teaching from scratch.