Online Belief State Planning

Chapter 1: Lookahead with Rollouts

Before building full search trees, consider the simplest possible online method: lookahead with rollouts. For each candidate action a, run m simulations forward. In each simulation: sample a state s ~ b, take action a, sample a transition and observation, then follow a rollout policy π_R for H steps. Average the returns:

Pick the action with the highest estimated Q-value. The rollout policy π_R can be anything: random actions, a simple heuristic, or the QMDP policy from offline precomputation. The rollout doesn't need to be optimal — it just needs to estimate the value better than zero.

Chapter 2: Forward Search

Rollouts estimate Q(b,a) with simulation noise. Forward search computes it exactly (within a tree), by summing over all observations at each step. The recursion:

This is exact: no sampling noise. The leaf value U_approx comes from offline precomputation. Better leaf estimates allow shallower search: with PBVI leaves, depth 2 can be nearly as good as random-rollout depth 10.

Chapter 3: Branch and Bound

Forward search builds the full tree and wastes time on obviously bad actions. Branch and bound uses precomputed upper and lower bounds to prune branches that cannot possibly beat the current best solution.

The algorithm maintains two quantities at each node:

• Upper bound Q̅(b, a): the best this action branch could possibly achieve. Comes from FIB or the sawtooth bound.
• Lower bound U̲(b): the value we've already guaranteed is achievable. Comes from PBVI or the blind policy.

Pruning rule: if Q̅(b, a) < U̲(b), skip action a entirely. It cannot beat what we already have. This is valid because:

Chapter 4: Sparse Sampling

Forward search sums over every observation. For |O| = 100 and depth 5, that's 100⁵ = 10 billion observation branches. Sparse sampling replaces the exact sum with a stochastic approximation: draw m observation samples instead of enumerating all of them.

where o_a⁽ⁱ⁾ ~ P(o|b,a) are sampled observations. The branching factor drops from |O| to m. Crucially, m doesn't depend on |O| at all. Whether |O| = 10 or |O| = 10 million, the same m gives the same approximation quality (up to statistical noise).

The tradeoff: sparse sampling introduces variance. The estimate of Q(b,a) has variance O(1/m) at each node. But the variance can be controlled by choosing m, whereas the explosion from |O| cannot. For many practical problems, m=10 to m=30 gives excellent results.

Chapter 5: POMCP — Monte Carlo Tree Search for POMDPs

Sparse sampling builds a tree of fixed depth and uniform breadth. Partially Observable Monte Carlo Planning (POMCP) adapts MCTS to POMDPs, spending more computation on promising branches and less on hopeless ones.

The core adaptation: MCTS normally indexes nodes by states. Since the agent doesn't know the state, POMCP indexes by action-observation histories h = (a₁, o₁, ..., a_t, o_t). Each history node stores Q(h, a) estimates and visit counts N(h, a). The UCB action selection:

where N(h) = ∑_a N(h, a) is total visits at history h. The c parameter balances exploration and exploitation.

The particle filter innovation: instead of representing beliefs explicitly, POMCP maintains a particle set at each history node — the collection of states that have been visited at that node across simulations. This implicitly approximates the belief without ever computing it.

julia (POMCP core)
function pomcp_simulate(pomdp, s, h, depth, tree, c)
    if depth == 0; return rollout(pomdp, s, 10); end

    if !haskey(tree, h)
        # New history node: initialize Q-values
        tree[h] = Dict(a => (Q=0.0, N=0) for a in actions(pomdp))
        return rollout(pomdp, s, depth)
    end

    # UCB action selection
    N_h = sum(n.N for n in values(tree[h]))
    a = argmax(a -> tree[h][a].Q + c*sqrt(log(N_h+1)/(tree[h][a].N+1)), actions(pomdp))

    # Sample transition
    sp, o, r = gen(pomdp, s, a)
    h_new = (h..., a, o)  # extend history

    # Add particle to new history node
    push!(get!(Set, particles, h_new), sp)

    G = r + discount(pomdp) * pomcp_simulate(pomdp, sp, h_new, depth-1, tree, c)

    # Backup
    tree[h][a] = (Q = tree[h][a].Q + (G - tree[h][a].Q)/(tree[h][a].N+1),
                  N = tree[h][a].N + 1)
    return G
end

function pomcp_action(pomdp, belief, n_sims)
    tree = Dict(); particles = Dict()
    for _ in 1:n_sims
        s = rand(belief)
        pomcp_simulate(pomdp, s, (), 5, tree, 1.0)
    end
    return argmax(a -> tree[()][a].N, actions(pomdp))
end

Chapter 6: DESPOT

POMCP draws fresh random observations at each simulation. Determinized Sparse Tree Search (DESPOT) takes a different approach: pre-generate K fixed random scenarios before search begins. A scenario φ = (φ₁, φ₂, ...) is a sequence of random numbers that deterministically specifies the environment's behavior (transitions and observations) at each depth.

Given action sequence a₁, ..., a_d and scenario φ, the entire trajectory is determined. This means actions a and a' can be compared under exactly the same random events. This is analogous to common random numbers in simulation: variance reduction by correlating random draws across alternatives.

The tree structure: DESPOT doesn't branch on observations. Instead, each scenario follows a unique path through the tree determined by its sequence of random numbers. The tree has at most K leaves at any depth, and total size O(|A|^dK) — independent of |O|.

julia (DESPOT core)
struct Scenario
    s0::Int          # initial state sampled from belief
    rands::Vector{Float64}  # random numbers for each depth level
end

function despot_value(pomdp, b, depth, scenarios, bounds)
    if depth == 0
        return mean(bounds.lower(pomdp, s) for (s,_) in scenarios)
    end
    best_val = -Inf
    for a in actions(pomdp)
        # All K scenarios face the same action a
        # Group by which observation they produce
        obs_groups = Dict{Int, Vector}()
        total_r = 0.0
        for (s, rand_seq) in scenarios
            sp, o, r = gen_deterministic(pomdp, s, a, rand_seq[depth])
            total_r += r
            push!(get!(obs_groups, o, []), (sp, rand_seq))
        end
        future = sum(for (o, group) in obs_groups
            length(group)/length(scenarios) *
            despot_value(pomdp, nothing, depth-1, group, bounds))
        val = total_r/length(scenarios) + discount(pomdp) * future
        if val > best_val; best_val = val; end
    end
    return best_val
end

Chapter 7: SHOWCASE — MCTS Search Tree Live

Watch POMCP build its search tree in real time on the Crying Baby POMDP. Each simulation starts at the root belief, navigates down using UCB, and backs up the return. The tree grows asymmetrically: promising branches get more visits. Run enough simulations and the most visited action at the root is reliably the best.

Chapter 8: Gap Heuristic Search

Branch and bound prunes action branches using upper/lower bounds. The gap heuristic applies a similar idea to observation branches: instead of exploring all (or m random) observations at each node, selectively expand only the most informative ones.

The gap at a belief b is the difference between upper and lower bounds: gap(b) = U̅(b) − U̲(b). The gap heuristic expands the observation branch that maximizes the probability-weighted gap:

This targets observations that are both likely to occur and have high uncertainty in their value. If an observation is very likely but already well-understood (small gap), it's not worth expanding. If it's very uncertain but very unlikely, it's also not worth expanding. The product captures the joint importance.

Chapter 9: Summary & Connections

Online POMDP planning covers a rich set of methods, each making different tradeoffs. The core tension is between: complete enumeration (forward search) and smart sampling/pruning (everything else). Here's the complete landscape: