22 · Online Belief State Planning

Part IV — State Uncertainty

Executed in: Julia · Book: ADM Ch. 22 · Lecture: to be added

Big picture

Where this chapter fits

Chapter 21 computed approximate value functions over all beliefs before acting. That is wasteful: from any one belief, only a small set of beliefs is reachable in the next few steps. Online planning builds a search tree from the belief the agent is in right now, picks one action, acts, observes, updates its belief (the Chapter 19 filter), and plans again. These are the methods of Chapter 9, with one change: every action branches on the observation it could produce, not on the next state.

The question: from the current belief, how can we choose a good action with a bounded amount of computation, when we can’t solve the whole POMDP?

The short answer: search a few steps ahead, and let an offline value estimate take over at the leaves.

• Forward search expands every action and every observation to a fixed depth. It is exact up to its leaves, but its tree grows as \((|\mathcal{A}||\mathcal{O}|)^d\).
• Branch and bound skips actions whose upper bound can’t beat what has been found.
• Sampling (sparse sampling, Monte Carlo tree search, determinized trees) looks at a sample of observations instead of all of them.
• Gap heuristic search keeps upper and lower bounds and explores where they disagree most.

Figure 1: Map of this chapter. From the current belief, a search looks a few steps ahead, exhaustively or by sampling, with value estimates from Chapter 21 at the leaves. The agent takes the best first action, observes, updates its belief and plans again.

The key ideas at a glance

1. Plan from where you are. Online methods spend their computation on the beliefs reachable from the current one. Each decision costs more than looking up an offline policy, but nothing is spent on beliefs that will never occur. That makes them usable for problems too large to solve offline.

2. Forward search, with leaf values. Expand every action and every observation to depth \(d\). At the leaves, use an estimate \(U(b)\) from Chapter 21 (QMDP, the fast informed bound, a point-based lower bound) or from rollouts. The error at the root is at most \(\gamma^d\) times the leaf error, but the tree has \((|\mathcal{A}||\mathcal{O}|)^d\) leaves.

3. Branch and bound. With a lower bound at the leaves and an upper bound on each action’s value, skip any action whose upper bound can’t beat the best value found so far. The answer is unchanged. How much it saves depends entirely on how tight the bounds are.

4. Sampling instead of enumerating. Sparse sampling averages \(m\) sampled outcomes per action. Monte Carlo tree search runs simulations from states drawn from the belief and keeps statistics per history of actions and observations, so it never computes a belief below the root. Determinized sparse tree search fixes the randomness in advance, in \(m\) scenarios, so each action sequence yields at most \(m\) histories.

5. Search where the bounds disagree. Gap heuristic search keeps an upper and a lower bound at each belief it visits. It follows the action that looks best on the upper bound and the observation whose next belief has the widest gap, and tightens both bounds on the way back.

Vocabulary

Table 1: Terms used on this page.

Term	Plain meaning
Online planning	Choosing the next action by searching from the current belief, then replanning after each step
Leaf value \(U(b)\)	An estimate used where the search stops
Forward search	Exhaustive search over actions and observations to a fixed depth
Branch and bound	Forward search that skips actions whose upper bound is too low
Sparse sampling	Forward search that averages \(m\) sampled outcomes per action
History \(h\)	The actions taken and observations received since the current belief
Monte Carlo tree search (POMCP)	Simulation-based search with statistics per history
Determinized scenario	A pre-drawn sequence of random numbers that fixes what happens to one particle
Gap	Upper bound minus lower bound at a belief

After this chapter you can

• Run forward search from a belief, with leaf values from an offline method, and say how its error depends on the depth.
• Count the size of a search tree and choose between exhaustive, pruned and sampled search.
• Explain why sampled estimates of a maximum are biased upward.
• Run Monte Carlo tree search over histories, and choose its exploration constant for the scale of the rewards.
• Use upper and lower bounds to prune, and to decide where to search.

Intuition

TipAnalogy

A chess player doesn’t memorize the best move for every possible board; that’s offline planning. Before each move, they look a few moves ahead from this board, then trust their judgment (“this position looks good for me”) where they stop looking. That judgment is the leaf value. Stronger players either look deeper, prune lines that are clearly bad, or have better judgment. Under uncertainty there’s a twist: every move is followed not by a known reply but by something you observe, and you must plan for each thing you might see.

We use the two problems of Chapter 21: the crying baby, which has an exact solution to compare against, and the fork (problem gallery), where a hiker must pay to learn which trail leads home. On the fork, QMDP’s offline policy waits forever, and point-based value iteration earns about 27.

Look ahead a few steps

Forward search tries every action, then every observation that action could produce, then every action again, and so on to a depth \(d\). The crying baby has 3 actions and 2 observations, so a depth-3 search visits 259 beliefs; depth 5 visits 9331. With the fast informed bound at the leaves, the largest value error over the beliefs we checked fell from 0.65 at depth 0 to 0.19 at depth 3. See Equation 1.

Search can repair a bad leaf

On the fork, QMDP’s leaf values are wildly optimistic (190, when the truth is about 27), and a one-step lookahead on them waits forever. But a depth-2 search on the same leaves asks the passerby, and in closed loop it earned exactly what the offline point-based policy earned, run for run. With zero at the leaves, depth 3 is enough. The search sees that two answers in a row lead to near-certainty, which even QMDP rewards. See the worked example.

Prune with bounds

If the fast informed bound says an action is worth at most \(-20\), and another action has already been shown to be worth \(-19\), don’t search the first one. With a tight point-based lower bound at the leaves, branch and bound visited only 5% of forward search’s beliefs at depth 5, with the same answer. With a loose one, it pruned nothing. See Equation 3.

Sample instead of enumerate

Sampling a few outcomes per action makes the cost independent of the number of observations. The catch: the best of several noisy averages tends to be one that got lucky. For the crying baby at depth 3, sparse sampling with 1 sample per action overestimated the value by 9.0 on average; with 16, by 1.0. Monte Carlo tree search spends its simulations where they look promising, and at the fork it learned to ask (Figure 6). See Equation 4 and Equation 5.

Search where you’re unsure

Gap heuristic search keeps both bounds at every belief it visits, and follows the branch where they differ most. From the crying baby’s 50–50 belief, the gap was 17.1 after the first exploration and below 1 after 37. See Equation 7.

Formalism

Forward search

Search to depth \(d\) from belief \(b\) (ADM §22.2):

\[ Q_d(b, a) = R(b, a) + \gamma \sum_{o} P(o \mid b, a)\, U_{d-1}\big(\text{Update}(b, a, o)\big), \qquad U_d(b) = \max_a Q_d(b, a), \qquad U_0(b) = U(b) \tag{1}\]

In words. The value of an action is its expected reward now, plus the discounted value of each belief it could lead to, weighted by how likely each observation is. The recursion stops at depth 0, where a leaf estimate \(U\) takes over.

Term by term.

• \(R(b, a) = \sum_s b(s) R(s, a)\) is the expected immediate reward.
• \(P(o \mid b, a) = \sum_{s'} O(o \mid a, s') \sum_s T(s' \mid s, a) b(s)\) is the chance of seeing \(o\); observations with probability 0 are skipped.
• \(\text{Update}(b, a, o)\) is the Chapter 19 belief update.
• \(U\) is any estimate of the optimal value: an offline bound, a rollout, or zero.
• The tree has at most \(\sum_{k=0}^{d}(|\mathcal{A}||\mathcal{O}|)^k\) belief nodes (fewer if some observations are impossible): 259 for the crying baby at depth 3.

Why it holds. This is the one-step lookahead of Chapter 20 (eq. 20.13), applied recursively: \(d\) steps of the Bellman backup on the belief MDP, starting from \(U\).

How much does depth help? If the leaf values are off by at most \(\varepsilon\), then

\[ \big|U_d(b) - U^*(b)\big| \le \gamma^d\,\varepsilon, \qquad \varepsilon = \max_{b'} \big|U(b') - U^*(b')\big| \tag{2}\]

In words. Each level of search multiplies the leaf’s error by at most \(\gamma\).

Term by term.

• \(U^*\) is the optimal value; \(\varepsilon\) is the leaf’s worst error over the beliefs the tree can reach.
• \(\gamma^d\): for the crying baby (\(\gamma = 0.9\)), 5 levels cut the bound to \(0.9^5 \approx 0.59\) of the leaf error.

Why it holds. By induction on \(d\). Both \(U_d\) and \(U^*\) satisfy the backup in Equation 1, so \(|Q_d(b, a) - Q^*(b, a)| \le \gamma \sum_o P(o \mid b, a)\,|U_{d-1} - U^*| \le \gamma \cdot \gamma^{d-1}\varepsilon\), and the max over actions doesn’t increase a uniform error. The bound is often loose: with zero at the leaves, the crying baby’s error was 11.2 at depth 5, against a bound of 17.5.

Branch and bound

Given a lower bound \(U_{\text{lo}}\) for the leaves and an upper bound \(Q_{\text{hi}}(b, a)\) on each action’s value (ADM §22.3):

\[ \text{skip action } a \text{ at } b \quad\text{if}\quad Q_{\text{hi}}(b, a) \le \max_{a' \text{ searched}} Q_d(b, a') \tag{3}\]

In words. If an action’s best case is no better than an action already evaluated, it can’t be the answer.

Term by term.

• \(Q_d(b, a')\) is Equation 1 with \(U_{\text{lo}}\) at the leaves.
• \(Q_{\text{hi}}(b, a)\) must be at least \(Q_d(b, a)\); here it is a one-step lookahead on the fast informed bound, which is an upper bound on the optimal value, and so on \(Q_d\) with a lower-bound leaf.
• Searching actions in decreasing order of \(Q_{\text{hi}}\) finds good actions early, so more are pruned.

Why it holds. A skipped action’s value is at most \(Q_{\text{hi}}(b, a)\), which is at most the value already found. So the maximum, and the chosen action, are the same as forward search with \(U_{\text{lo}}\) at the leaves (up to ties).

Sparse sampling

Replace the sum over observations by \(m\) samples per action (ADM §22.4; M. Kearns, Y. Mansour and A. Y. Ng, Machine Learning, 2002):

\[ Q_d(b, a) \approx \frac{1}{m}\sum_{i=1}^{m} \Big( r_a^{(i)} + \gamma\, U_{d-1}\big(\text{Update}(b, a, o_a^{(i)})\big) \Big) \tag{4}\]

In words. Try each action \(m\) times in simulation, and average what happened.

Term by term.

• \((r_a^{(i)}, o_a^{(i)})\): draw a state \(s\) from \(b\), then \(s'\) from \(T\) and \(o\) from \(O\); the reward is \(R(s, a)\).
• The tree has \((|\mathcal{A}|\,m)^d\) leaves, whatever the number of observations.
• \(U_{d-1}\) is itself computed by sparse sampling, down to the leaf estimate.

Why it holds. Each term is an unbiased sample of the summand in Equation 1. But the maximum over actions of noisy averages is biased upward: \(\mathbb{E}[\max_a \hat{Q}(a)] \ge \max_a \mathbb{E}[\hat{Q}(a)]\). With 1 sample per action at depth 3, the bias for the crying baby was 9.0.

Monte Carlo tree search over histories

Monte Carlo tree search (ADM §22.5; D. Silver and J. Veness, NeurIPS, 2010, who call it POMCP) keeps a count \(N(h, a)\) and an average return \(Q(h, a)\) for each history \(h\) of actions and observations. Each simulation draws a state from the current belief and walks down the tree, choosing

\[ a = \arg\max_{a}\; Q(h, a) + c\sqrt{\frac{\log N(h)}{N(h, a)}}, \qquad N(h) = \sum_a N(h, a) \tag{5}\]

In words. Prefer actions that have done well, plus a bonus for actions that have been tried rarely.

Term by term.

• \(Q(h, a)\) is the average discounted return of simulations that took \(a\) after \(h\).
• The bonus grows slowly with the total visits \(N(h)\) and shrinks as \(a\) is tried; untried actions get an infinite bonus.
• \(c\) sets the balance, and must match the scale of the returns: a bonus of 10 is large when returns differ by 1, and small when they differ by 60.
• A new history is added with zero counts and valued by the leaf estimate; its state, not its belief, is passed to that estimate.

Why it holds. The states that reach a history \(h\) are distributed according to the belief after \(h\), because each was sampled from the root belief and then moved and observed by the model. So averages at \(h\) estimate values under that belief, without ever computing it. The UCB1 rule (P. Auer, N. Cesa-Bianchi and P. Fischer, Machine Learning, 2002) makes sure every action keeps being tried, so the estimates at the root converge as simulations grow.

Determinized sparse tree search

Fix the randomness in advance (ADM §22.6; N. Ye, A. Somani, D. Hsu and W. S. Lee, JAIR, 2017, who call their method DESPOT). Draw an \(m \times d\) matrix \(\Phi\) of uniform numbers. A particle \(\phi = (s, i, j)\) is a state on scenario \(i\) at depth \(j\), and taking action \(a\) moves it to

\[ (s', o) = \text{the first pair, in a fixed order, at which } \sum P(s', o \mid s, a) \ge \Phi_{ij}, \qquad P(s', o \mid s, a) = T(s' \mid s, a)\, O(o \mid a, s') \tag{6}\]

In words. Each particle carries its own pre-drawn random numbers, so the same particle and action always lead to the same next state and observation.

Term by term.

• The running sum is the cumulative distribution over \((s', o)\) pairs; stopping where it first reaches \(\Phi_{ij}\) is inverse-CDF sampling with a stored number.
• The new particle is \((s', i, j + 1)\): same scenario, one step deeper.
• An action splits the particles by the observation each produces. A child’s weight is its share of the particles.

Why it holds. Each \(\Phi_{ij}\) is uniform, so each particle’s successor has the right distribution. Because every action sequence sends the \(m\) particles down at most \(m\) paths, the tree has at most \(m\) nodes per action sequence: \(O(|\mathcal{A}|^d m)\) in all. And because all actions are scored on the same scenarios, their comparison is less noisy than with independent samples (the common random numbers of Chapter 14).

Gap heuristic search

Keep bounds \(U_{\text{lo}}(b) \le U^*(b) \le U_{\text{hi}}(b)\) at every belief visited, initialized from bound functions (ADM §22.7). From belief \(b\), explore

\[ a = \arg\max_a Q_{\text{hi}}(b, a), \qquad o = \arg\max_{o} \Big( U_{\text{hi}}(b'_o) - U_{\text{lo}}(b'_o) \Big) \tag{7}\]

where \(b'_o = \text{Update}(b, a, o)\); move to \(b'_o\) and repeat. After returning, replace both bounds at \(b\) by their one-step lookahead backups (keeping the tighter value). Stop when the gap at \(b\) is below \(\delta\) or the depth limit is reached.

In words. Go where the optimistic bound says to go, toward the outcome you’re least sure about.

Term by term.

• \(Q_{\text{hi}}(b, a)\) is the one-step lookahead on the stored upper bounds.
• The gap \(U_{\text{hi}} - U_{\text{lo}}\) at the next belief says how much there is to learn there.
• The backups use Equation 1 with depth 1, on the stored bounds.

Why it holds. A backup of an upper bound is an upper bound, and likewise for lower bounds, so the stored values stay valid bounds at every step. The search is guaranteed only if the initial bounds are true bounds. A single rollout is not a lower bound: it is one noisy sample.

Worked example

Two steps of search fix QMDP at the fork

QMDP’s value at the fork is flat at 190 in the middle: it’s the value of waiting, \(0.95 \times 200\), where 200 is the value of a hike that always goes home. Going right beats waiting only when \(P(\text{home right}) \ge 0.83\), so QMDP rises to 200 only near the ends.

• Depth 1. Waiting scores \(0 + 0.95 \times 190 = 180.5\). Asking scores \(-1 + 0.95 \times 191 = 180.45\), because either answer moves the belief to 0.15 or 0.85, where QMDP is just 191. Waiting wins by 0.05, and waits forever.
• Depth 2, after a “right” answer (belief 0.85). Now one more step is searched. Asking again reaches 0.97 if the answers agree (probability 0.745), where QMDP is 198.2, or falls back to 0.5 (190). So asking again scores 185.29, more than going right (181.5) or waiting (181.45). \(U_1(0.85) =\) 185.29.
• Depth 2, at the start. Asking scores \(-1 + 0.95 \times\) 185.29 \(=\) 175.03 (both answers are symmetric). Waiting scores \(0.95 \times U_1(0.5) = 0.95 \times 180.5 =\) 171.47. Asking wins.

The leaf values are still wrong by more than 150. But the search compares the actions by what they lead to, and two answers in a row reach the region where even QMDP’s optimism rewards certainty.

The code’s depth-2 values at the start: wait 171.47, ask 175.03, go left 151.47, go right 151.47.

A determinized successor by hand

A sated baby is ignored. The four outcomes \((s', o)\), in the fixed order (sated, crying), (sated, quiet), (hungry, crying), (hungry, quiet), have probabilities \(0.9 \times 0.1 = 0.09\), \(0.9 \times 0.9 = 0.81\), \(0.1 \times 0.8 = 0.08\) and \(0.1 \times 0.2 = 0.02\), so the running sums are 0.09, 0.90, 0.98 and 1.

• With \(\Phi_{ij} = 0.62\), the first running sum at or above 0.62 is 0.90: the particle stays sated and the baby is quiet.
• With \(\Phi_{ij} = 0.95\), it is 0.98: the baby turns hungry and cries.

Whichever action sequence the search tries, this particle, at this depth, always uses the same number.

The code’s successors: Φ = 0.62 → (sated, quiet); Φ = 0.95 → (hungry, crying).

Interactive

How deep must you look?

Choose a problem, a leaf estimate and a search depth. The top chart shows forward search’s value over beliefs (blue) against a reference (black): the exact value for the crying baby, and the point-based value of Chapter 21 for the fork (within \(10^{-5}\) of optimal at 50–50). The strips below show the action forward search chooses, and the reference policy’s action.

depthData = FileAttachment("data/ch22-depth.json").json()
viewof depthProblem = Inputs.radio(["crying baby", "fork"], {label: "Problem", value: "fork"})
viewof depthLeaf = Inputs.select(["zero", "blind (lower)", "QMDP (upper)", "fast informed (upper)"]
  .filter(k => k in depthData[depthProblem].leaves), {label: "Leaf estimate", value: "QMDP (upper)"})
viewof depthD = Inputs.range([0, 5], {step: 1, value: 1, label: "Depth d"})

depthNow = {
  const P = depthData[depthProblem], run = P.leaves[depthLeaf][String(depthD)];
  const pts = P.x.map((x, i) => ({x, u: run.u[i], ref: P.ref.u[i],
                                  a: run.a[i] ? P.actions[run.a[i] - 1] : "(none)", r: P.actions[P.ref.a[i] - 1]}));
  const mid = pts[Math.round((pts.length - 1) / 2)];
  const differ = depthD === 0 ? null : pts.filter(p => p.a !== p.r).length;
  return {P, pts, mid, differ, err: d3.max(pts, p => Math.abs(p.u - p.ref))};
}
md`At 50–50: forward search **${depthD === 0 ? "has no action at depth 0 (the leaf value alone)" : depthNow.mid.a}**, the reference **${depthNow.mid.r}**. Largest value gap from the reference: **${depthNow.err.toFixed(2)}**. ${depthNow.differ === null ? "" : `Beliefs where the action differs from the reference: **${depthNow.differ}** of ${depthNow.pts.length}.`} Beliefs visited per decision: **${(Math.pow(depthNow.P.actions.length * 2, depthD + 1) - 1) / (depthNow.P.actions.length * 2 - 1)}**.`

{
  const colors = {wait: "#9c9b95", ask: "#eb6834", "go left": "#2a78d6", "go right": "#4a3aa7",
                  feed: "#2a78d6", sing: "#1baf7a", ignore: "#eda100", "(none)": "#f0efec"};
  const acts = [...depthNow.P.actions, "(none)"];
  const top = Plot.plot({width: 640, height: 260, style: {background: "#fcfcfb"},
    x: {domain: [0, 1], label: depthNow.P.xlabel}, y: {label: "value", grid: true},
    marks: [Plot.line(depthNow.pts, {x: "x", y: "ref", stroke: "#0b0b0b", strokeWidth: 2.5}),
            Plot.line(depthNow.pts, {x: "x", y: "u", stroke: "#2a78d6", strokeWidth: 2})]});
  const rows = depthNow.pts.flatMap(p => [{x: p.x, row: "forward search", act: p.a}, {x: p.x, row: "reference", act: p.r}]);
  const strip = Plot.plot({width: 640, height: 130, style: {background: "#fcfcfb"}, marginLeft: 110,
    x: {domain: [-0.01, 1.01], label: depthNow.P.xlabel}, y: {label: null, domain: ["forward search", "reference"]},
    color: {domain: acts, range: acts.map(a => colors[a]), legend: true},
    marks: [Plot.barX(rows, {x1: d => d.x - 0.01, x2: d => d.x + 0.01, y: "row", fill: "act"})]});
  return html`<div>${top}${strip}</div>`;
}

Figure 2: Forward search on the chosen problem: value over beliefs (blue) against the reference (black), and the actions chosen by forward search and by the reference policy.

Monte Carlo tree search at the fork’s start

Step through the simulations of one Monte Carlo tree search from the fork’s 50–50 belief (depth 20, zero leaf values). Bars show how often each action was tried at the root; dots show its average return so far.

mctsData = FileAttachment("data/ch22-mcts.json").json()
viewof mctsC = Inputs.radio(["10", "50"], {label: "Exploration constant c", value: "50"})
viewof mctsK = Inputs.range([1, 3000], {step: 1, value: 60, label: "Simulations"})

mctsNow = {
  const run = mctsData.runs[mctsC], i = d3.bisectRight(run.k, mctsK) - 1;   // last snapshot at or before mctsK
  const rows = mctsData.actions.map((a, j) => ({action: a, N: run.N[i][j], Q: run.N[i][j] > 0 ? run.Q[i][j] : null}));
  const tried = rows.filter(r => r.N > 0);
  const best = tried.length ? tried.reduce((x, y) => (y.Q > x.Q ? y : x)).action : "(none yet)";
  const allQ = run.Q.flatMap((q, t) => q.filter((v, j) => run.N[t][j] > 0));
  return {k: run.k[i], rows, best, qDomain: [Math.min(-5, d3.min(allQ)) - 2, Math.max(5, d3.max(allQ)) + 2]};
}
md`After **${mctsNow.k}** simulations, the root's best action by average return is **${mctsNow.best}**.`

{
  const left = Plot.plot({width: 320, height: 200, marginLeft: 70, style: {background: "#fcfcfb"},
    x: {label: "visits N(h, a)", grid: true}, y: {label: null, domain: mctsData.actions},
    marks: [Plot.barX(mctsNow.rows, {x: "N", y: "action", fill: "#2a78d6"}), Plot.ruleX([0])]});
  const right = Plot.plot({width: 320, height: 200, marginLeft: 70, style: {background: "#fcfcfb"},
    x: {label: "average return Q(h, a)", grid: true, domain: mctsNow.qDomain}, y: {label: null, domain: mctsData.actions},
    marks: [Plot.dot(mctsNow.rows.filter(r => r.Q !== null), {x: "Q", y: "action", fill: "#eb6834", r: 6}), Plot.ruleX([0])]});
  return html`<div style="display:flex;flex-wrap:wrap;gap:12px">${left}${right}</div>`;
}

Figure 3: Root statistics of one Monte Carlo tree search at the fork’s start: visits per action (bars, left) and average return (dots, right).

These are the averages of the returns the search got while exploring. They are well below the true values (about 29 for asking), because the simulations include exploratory mistakes and stop after 20 steps. What matters for the decision is their order.

Algorithms & code

Forward search, branch and bound, sampling, Monte Carlo tree search, determinized search, gap search

Julia

# Online belief state planning (ADM Ch. 22): plan from the current belief only.
# A POMDP p has p.T[s, a, s′], p.R[s, a], p.O[a, s′, o] and p.γ (as in Ch. 20-21).
# Beliefs are probability vectors over states, updated with update_discrete.

# One step of the generative model from a known state: move, observe, reward.
function pomdp_step(p, s, a, rng)
    s′ = rand(rng, Categorical(p.T[s, a, :]))
    o = rand(rng, Categorical(p.O[a, s′, :]))
    return s′, p.R[s, a], o
end

# Rollout from belief b (§22.1): follow `policy` (a function of the belief) for d
# steps. randstep (Ch. 21) draws a state from the current belief at every step;
# that gives the same distribution of rewards and observations as tracking one
# hidden state, because the belief is exactly the posterior over that state.
function belief_rollout(p, b, policy, d, rng)
    ret = 0.0
    for t in 0:d-1
        b, r = randstep(p, b, policy(b), rng)
        ret += p.γ^t * r
    end
    return ret
end

# Forward search (eq. 22.1): expand every action and every possible observation
# to depth d, and value the leaves with U. `count` tallies belief nodes visited.
function forward_search_belief(p, b, d, U; count = Ref(0))
    count[] += 1
    d == 0 && return (a = 0, u = U(b))
    Ud(b′) = forward_search_belief(p, b′, d - 1, U; count).u   # value with d - 1 left
    q = [lookahead_belief(p, Ud, b, a) for a in 1:nactions(p)]
    return (a = argmax(q), u = maximum(q))
end

# Branch and bound (§22.3): forward search with Ulo at the leaves, but skip an
# action when its upper bound Qhi(b, a) can't beat the best value found so far.
# With true bounds, the answer is the same as forward_search_belief(p, b, d, Ulo).
function branch_and_bound_belief(p, b, d, Ulo, Qhi; count = Ref(0))
    count[] += 1
    d == 0 && return (a = 0, u = Ulo(b))
    Ud(b′) = branch_and_bound_belief(p, b′, d - 1, Ulo, Qhi; count).u
    best = (a = 0, u = -Inf)
    hi = [Qhi(b, a) for a in 1:nactions(p)]
    for a in sortperm(hi, rev = true)          # most promising action first
        hi[a] <= best.u && break               # this one and all after it: pruned
        u = lookahead_belief(p, Ud, b, a)
        u > best.u && (best = (a = a, u = u))
    end
    return best
end

# Sparse sampling (eq. 22.2): instead of summing over observations, average m
# sampled (reward, next belief) pairs per action. Cost O((|A| m)^d), whatever |O|.
function sparse_sampling_belief(p, b, d, m, U, rng)
    d == 0 && return (a = 0, u = U(b))
    best = (a = 0, u = -Inf)
    for a in 1:nactions(p)
        u = 0.0
        for _ in 1:m
            b′, r = randstep(p, b, a, rng)
            u += (r + p.γ * sparse_sampling_belief(p, b′, d - 1, m, U, rng).u) / m
        end
        u > best.u && (best = (a = a, u = u))
    end
    return best
end

# Monte Carlo tree search over histories (§22.5; POMCP, Silver and Veness, 2010).
# A history h is a tuple of (action, observation) pairs since the root. N and Q
# are keyed by (h, a). Each simulation draws a state from the root belief and
# follows it down the tree, so no belief is ever computed below the root.
struct HistoryMCTS
    p                        # the POMDP
    N::Dict{Any,Int}         # visit counts N(h, a)
    Q::Dict{Any,Float64}     # value estimates Q(h, a)
    d::Int                   # depth
    c::Float64               # exploration constant
    U                        # leaf value estimate: a function of the state
end
HistoryMCTS(p; d = 10, c = 1.0, U = s -> 0.0) =
    HistoryMCTS(p, Dict{Any,Int}(), Dict{Any,Float64}(), d, c, U)

# UCB1 (eq. 22.3). Untried actions get an infinite bonus, so each is tried
# once first; ties go to the lowest action index.
function mcts_explore(π::HistoryMCTS, h)
    A = 1:nactions(π.p)
    Nh = sum(π.N[(h, a)] for a in A)
    score(a) = π.N[(h, a)] == 0 ? Inf : π.Q[(h, a)] + π.c * sqrt(log(Nh) / π.N[(h, a)])
    return argmax(score, A)
end

function mcts_simulate!(π::HistoryMCTS, s, h, d, rng)
    d <= 0 && return π.U(s)
    if !haskey(π.N, (h, 1))                    # a new history: add it, value its leaf
        for a in 1:nactions(π.p)
            π.N[(h, a)], π.Q[(h, a)] = 0, 0.0
        end
        return π.U(s)
    end
    a = mcts_explore(π, h)
    s′, r, o = pomdp_step(π.p, s, a, rng)
    q = r + π.p.γ * mcts_simulate!(π, s′, (h..., (a, o)), d - 1, rng)   # h extended by (a, o)
    π.N[(h, a)] += 1
    π.Q[(h, a)] += (q - π.Q[(h, a)]) / π.N[(h, a)]    # running mean of the returns
    return q
end

# Run m simulations from belief b (at history h) and return the best root action.
function (π::HistoryMCTS)(b, m, rng; h = ())
    for _ in 1:m
        mcts_simulate!(π, rand(rng, Categorical(b)), h, π.d, rng)
    end
    return argmax(a -> π.Q[(h, a)], 1:nactions(π.p))
end

# Determinized sparse tree search (§22.6; DESPOT, Ye et al., 2017). Φ is an
# m × d matrix of uniform random numbers. A particle is a state on scenario i at
# depth j; Φ[i, j] fixes what happens to it next, for every action.
struct DeterminizedParticle
    s::Int                   # state
    i::Int                   # scenario: row of Φ
    j::Int                   # depth: column of Φ
end

# Inverse-CDF sampling with the stored number Φ[i, j]: walk the joint
# distribution P(s′, o | s, a) = T(s′ | s, a) O(o | a, s′) in a fixed order and
# stop where the running total first reaches Φ[i, j].
function successor(p, Φ, ϕ, a)
    u, total, last_pair = Φ[ϕ.i, ϕ.j], 0.0, (0, 0)
    for s′ in 1:nstates(p), o in 1:nobs(p)             # o varies fastest
        q = p.T[ϕ.s, a, s′] * p.O[a, s′, o]
        q > 0 || continue                              # impossible pairs never chosen
        total += q
        last_pair = (s′, o)
        total >= u && return last_pair
    end
    return last_pair          # rounding left the total a hair below u
end

# m particles, one per scenario, with states drawn from b.
determinized_belief(b, m, rng) = [DeterminizedParticle(rand(rng, Categorical(b)), i, 1) for i in 1:m]

# The belief a particle set stands for: the fraction of particles in each state.
particle_belief(p, particles) = [count(ϕ -> ϕ.s == s, particles) for s in 1:nstates(p)] ./ length(particles)

# Forward search on the determinized tree. Each particle's future is fixed, so an
# action splits the particles by the observation they produce; each group is
# weighted by its share of the particles. At most m histories survive per action
# sequence, so the tree has O(|A|^d m) nodes. U values a leaf's particle set.
function determinized_search(p, Φ, particles, d, U; count = Ref(0))
    count[] += 1
    d == 0 && return (a = 0, u = U(particles))
    best = (a = 0, u = -Inf)
    for a in 1:nactions(p)
        u = sum(p.R[ϕ.s, a] for ϕ in particles) / length(particles)
        groups = Dict{Int,Vector{DeterminizedParticle}}()      # observation => particles
        for ϕ in particles
            s′, o = successor(p, Φ, ϕ, a)
            push!(get!(groups, o, DeterminizedParticle[]), DeterminizedParticle(s′, ϕ.i, ϕ.j + 1))
        end
        for kids in values(groups)
            share = length(kids) / length(particles)
            u += p.γ * share * determinized_search(p, Φ, kids, d - 1, U; count).u
        end
        u > best.u && (best = (a = a, u = u))
    end
    return best
end

# Gap heuristic search (§22.7): keep lower and upper bounds at the beliefs seen,
# starting from the functions Ulo and Uhi. Each exploration follows the action
# that is best on the upper bound and the observation whose next belief has the
# widest gap, then backs both bounds up on the way back. Returns the action best
# on the lower bound, the bounds at b after each exploration, and both tables.
function gap_heuristic_search(p, b, Ulo, Uhi; δ = 0.01, k_max = 100, d_max = 10)
    lo, hi = Dict{Vector{Float64},Float64}(), Dict{Vector{Float64},Float64}()
    visit!(x) = haskey(hi, x) || (lo[x] = Ulo(x); hi[x] = Uhi(x))
    function explore(b, d)
        visit!(b)
        (d == 0 || hi[b] - lo[b] <= δ) && return
        # Bounds for every next belief, since the lookaheads below read them.
        nexts = Dict((a, o) => update_discrete(b, p.T, p.O, a, o)
                     for a in 1:nactions(p), o in 1:nobs(p) if observation_probability(p, b, a, o) > 0)
        foreach(visit!, values(nexts))
        a = argmax(a -> lookahead_belief(p, x -> hi[x], b, a), 1:nactions(p))
        # Candidates sorted, so ties go to the lowest observation index.
        _, o = argmax(ao -> hi[nexts[ao]] - lo[nexts[ao]], sort([k for k in keys(nexts) if k[1] == a]))
        explore(nexts[(a, o)], d - 1)
        # A backup of a lower (upper) bound is still one; keep the tighter value.
        lo[b] = max(lo[b], maximum(lookahead_belief(p, x -> lo[x], b, a) for a in 1:nactions(p)))
        hi[b] = min(hi[b], maximum(lookahead_belief(p, x -> hi[x], b, a) for a in 1:nactions(p)))
        return
    end
    history = Tuple{Float64,Float64}[]
    for _ in 1:k_max
        explore(b, d_max)
        push!(history, (lo[b], hi[b]))
        hi[b] - lo[b] < δ && break
    end
    a = argmax(a -> lookahead_belief(p, x -> haskey(lo, x) ? lo[x] : Ulo(x), b, a), 1:nactions(p))
    return (a = a, history = history, lo = lo, hi = hi)
end

# Run a belief-based policy on the true POMDP for `steps` steps from state s and
# belief b; returns the discounted return and the actions taken.
function run_pomdp(p, policy, b, s, steps, rng)
    ret, acts = 0.0, Int[]
    for t in 0:steps-1
        a = policy(b)
        push!(acts, a)
        s′, r, o = pomdp_step(p, s, a, rng)
        ret += p.γ^t * r
        b, s = update_discrete(b, p.T, p.O, a, o), s′
    end
    return ret, acts
end

Python

import numpy as np

from adm.problems.crying_baby import belief_update
from adm.problems.fork import fork

p = fork()                       # actions: wait, ask, go left, go right
nA, nO = p.T.shape[1], p.O.shape[2]


def obs_prob(p, b, a, o):
    """P(o | b, a): move with T, then observe with O."""
    return (b @ p.T[:, a, :]) @ p.O[a, :, o]


def forward_search(p, b, d, U, count):
    """eq. 22.1: (best action, value) to depth d; count[0] tallies beliefs."""
    count[0] += 1
    if d == 0:
        return None, U(b)
    q = []
    for a in range(nA):
        v = p.R[:, a] @ b                              # expected reward now
        for o in range(nO):
            po = obs_prob(p, b, a, o)
            if po > 0:                                 # skip impossible observations
                b2 = belief_update(p, b, a, o)
                v += p.gamma * po * forward_search(p, b2, d - 1, U, count)[1]
        q.append(v)
    return int(np.argmax(q)), max(q)


def qmdp(p, k_max=300):
    """eq. 21.1: one alpha vector per action (rows)."""
    G = np.zeros((nA, 2))
    for _ in range(k_max):
        G = p.R.T + p.gamma * np.einsum("sat,t->as", p.T, G.max(axis=0))
    return G


G = qmdp(p)
b0 = np.array([0.5, 0.5])
results = {}
for d in (1, 2, 3):
    count = [0]
    a, u = forward_search(p, b0, d, lambda b: (G @ b).max(), count)
    results[d] = (a, u, count[0])
    print(f"depth {d}: {p.actions[a]:>4}  value {u:7.2f}  beliefs {count[0]}")
assert [results[d][0] for d in (1, 2, 3)] == [0, 1, 1]      # wait, then ask
assert [results[d][2] for d in (1, 2, 3)] == [9, 73, 585]

NoteReading the Julia code (for Python programmers)

• count = Ref(0) is a mutable box holding one integer, like a one-element list; count[] += 1 changes the value inside. It lets recursive calls share a tally.
• (h..., (a, o)) builds a new tuple: all the elements of h, then the pair (a, o). Tuples are immutable and hashable, so histories can be dictionary keys.
• argmax(score, A) returns the element of A with the largest score, like max(A, key=score) in Python.
• get!(groups, o, DeterminizedParticle[]) returns groups[o], first inserting an empty vector if the key is missing: groups.setdefault(o, []).
• for s′ in 1:n, o in 1:m is a nested loop with o innermost. (In a comprehension, [f(x, y) for x in A, y in B] makes a matrix instead.)
• (π::HistoryMCTS)(b, m, rng) makes the struct callable, like defining __call__.

Run them

p = crying_baby()
upper = fast_informed_bound(p; k_max = 300)
lower = pbvi(p, [[1 - x, x] for x in 0:0.25:1]; k_max = 100)
b = [0.5, 0.5]
Qhi(b, a) = lookahead_belief(p, x -> utility(upper, x), b, a)
fs_count, bb_count = Ref(0), Ref(0)
fs = forward_search_belief(p, b, 4, x -> utility(lower, x); count = fs_count)
bb = branch_and_bound_belief(p, b, 4, x -> utility(lower, x), Qhi; count = bb_count)

(a = 1, u = -24.676346805617435)

forward search: feed, value -24.676, 1555 beliefs
branch and bound: feed, value -24.676, 115 beliefs

Results

Depth, leaves and pruning on the crying baby

Figure 4: Forward search on the crying baby, over 51 beliefs. Left: the largest value error for each leaf estimate, by depth (solid), and the bound γ^d times the leaf’s error (dashed). Right: beliefs visited per decision by forward search and by branch and bound with a tight and a loose point-based lower bound (log scale).

• Depth helps, geometrically at best. Every leaf’s error stayed under its \(\gamma^d\) bound. The fast informed bound starts close (error 0.65) and ends at 0.15 after 5 levels. Zero leaves end at 11.2: depth alone doesn’t make up for poor leaves.
• Actions settle before values. With zero leaves, forward search chose the optimal action at 15 of 51 beliefs at depth 1, 40 at depth 2 and 51 from depth 3, though its values were still off by more than 10.
• Pruning needs a tight lower bound. Point-based value iteration after 100 iterations is within 0.002 of the exact value; after 10 it is up to 28.2 below. With the tight one, branch and bound visited 458 beliefs per decision at depth 5 instead of 9331. With the loose one, it visited all of them: no action’s upper bound was ever below the values found.

Sampling: sparse sampling and determinized scenarios

Figure 5: Sampled search at the crying baby’s 50–50 belief, fast informed bound at the leaves. Left: sparse sampling’s value estimate (mean ± one standard deviation over 200 seeds) by samples per action, at depths 1 and 3, against forward search’s exact value at the same depth (dashed). Right: determinized search at depth 4 (100 seeds), by number of scenarios, against forward search at depth 4 (dashed).

• The maximum of noisy averages is biased upward. At depth 3, sparse sampling overestimated forward search’s value by 9.0 with 1 sample per action, 3.4 with 4 and 1.0 with 16. The bias grows with depth, since every level takes a maximum. The spread (one standard deviation) fell from 4.5 to 1.2.
• Choosing the action is hard when actions are close. At 50–50, feeding is optimal, but only by 2.5 over the next best action. Sparse sampling at depth 3 chose it in 68% of runs with 16 samples per action.
• Determinized scenarios cost less and vary less. With 64 scenarios, determinized search at depth 4 visited 1010 beliefs on average (forward search: 1555), had a spread of 0.96, and chose to feed in 100% of runs. With 16 scenarios, 93%.

Monte Carlo tree search: the exploration constant matters

Figure 6: Monte Carlo tree search at the fork’s start (depth 20, zero leaf values): the share of 100 runs whose root action is to ask, by number of simulations, for two exploration constants.

With \(c = 50\), the root chose to ask in 99% of runs after 1000 simulations. With \(c = 10\), only 80% after 3000: the rewards span 60, so a bonus of 10 is too small to make the search revisit an action that got unlucky early. Deeper in the hike the decisions are harder. At \(P(\text{home right}) = 0.85\), asking again is best, but with 500 simulations and \(c = 50\) the search asked in only 53% of runs; with 2000 simulations, 79% (\(c = 50\)) and 92% (\(c = 20\)). Its average returns there (for example -6.6 for asking) are far below the true values, since they average over the search’s own exploration.

Gap heuristic search

Figure 7: Gap heuristic search from the crying baby’s 50–50 belief, with the blind lower bound and the fast informed upper bound as initial bounds: the stored lower and upper bounds at that belief after each exploration, with depth limits 10 and 20. The exact value is black.

• With true bounds, the gap closes. With a depth limit of 20, the gap at 50–50 fell below 1 after 37 explorations and below 0.1 after 84, ending at 0.067 after 300. Every stored bound, at all 612 beliefs visited, stayed on the right side of the exact value.
• The depth limit sets a floor. With a limit of 10, the gap stalled at 1.3: the leaves at depth 10 keep their initial bounds, and their gap, discounted by \(0.9^{10}\), still reaches the root.
• A rollout is not a lower bound. Replacing the blind lower bound by one 10-step random rollout per belief, the “gap” at 50–50 was already below \(\delta = 0.01\) (or negative) after a single exploration in 93 of 100 runs, so the search stopped there. The stored lower value at 50–50 ended above the exact value in 100 runs, and the recommended action wasn’t to feed in 22. The cause is noise, not bias: over 100,000 rollouts the average was -30.0, below the exact -24.67, but a single rollout exceeded the exact value 41% of the time.

Closed loop: plan, act, observe, repeat

Each planner below chooses one action, the true POMDP responds, the belief is updated, and the planner runs again. Returns are discounted sums over 120 steps (fork) or 80 steps (crying baby), from the 50–50 belief with the true state drawn from it. Every planner faces the same random outcomes in run \(i\) (common random numbers).

Table 2: The fork.

Planner	Runs	Return (± s.e.)	Difference from first row, paired (± s.e.)	Asks per hike
point-based lookahead (offline, Ch 21)	2000	27.87 ± 0.36	—	2.72
forward search, depth 1, QMDP leaves	2000	0.0 ± 0.0	-27.87 ± 0.36	never goes
forward search, depth 2, QMDP leaves	2000	27.87 ± 0.36	0.0 ± 0.0	2.72
forward search, depth 3, zero leaves	2000	27.87 ± 0.36	0.0 ± 0.0	2.72
MCTS, 1000 simulations, c = 20	100	23.35 ± 1.61	-4.24 ± 1.77	2.69

Table 3: The crying baby.

Planner	Runs	Return (± s.e.)	Difference from first row, paired (± s.e.)
exact lookahead (Ch 20)	500	-24.28 ± 0.45	—
forward search, depth 1, fast informed leaves	500	-24.28 ± 0.45	0.0 ± 0.0
forward search, depth 2, zero leaves	500	-26.81 ± 0.66	-2.54 ± 0.36
sparse sampling, m = 4, depth 2	500	-27.2 ± 0.58	-2.92 ± 0.31
determinized search, 16 scenarios, depth 4	500	-25.21 ± 0.46	-0.93 ± 0.16
MCTS, 300 simulations, c = 10	200	-25.01 ± 0.74	-0.59 ± 0.18

• The reference is noisy too. The point-based policy’s proven value at the start is 27.11; its 27.87 here is 2.1 standard errors above that, by chance (Chapter 21’s 10,000 runs gave 27.28 ± 0.17). Differences between planners on the same runs, in the paired column, are much more precise than either mean.
• On the fork, search repairs QMDP. One step of lookahead on QMDP never leaves the fork (return 0). Two steps, or three steps on zero leaves, earned exactly the offline point-based return in every run (checked): they chose the same actions. Monte Carlo tree search with 1000 simulations per step earned 23.3 ± 1.6 over its 100 runs; on the same runs, the point-based policy earned 4.2 ± 1.8 more. Its noisy choices deeper in each hike (above) cost it.
• On the crying baby, a good leaf needs little search. One step on the fast informed bound matched the exact policy in every run (checked). Every other planner earned less, by several standard errors of the paired difference: determinized search 0.93 and Monte Carlo tree search 0.59 less, zero leaves at depth 2 2.54 and sparse sampling 2.92 less. Zero leaves at depth 2 chose the optimal action at only 40 of 51 beliefs (above), and sparse sampling’s choices are noisy.

Solved problems

Problem 1: tree sizes. A POMDP has 4 actions and 3 observations. How many beliefs does forward search visit at depth 3? Sparse sampling with \(m = 2\)? Determinized search with 10 scenarios (at most)?

TipSolution

• Forward search: \(1 + 12 + 12^2 + 12^3 = 1885\), since each level multiplies by \(|\mathcal{A}||\mathcal{O}| = 12\).
• Sparse sampling: \(1 + 8 + 8^2 + 8^3 = 585\), since each level multiplies by \(|\mathcal{A}|\,m = 8\), whatever \(|\mathcal{O}|\) is.
• Determinized search: at depth \(k\), each of the \(4^k\) action sequences has at most \(\min(3^k, 10)\) histories: \(4 \times 3 = 12\), \(16 \times 9 = 144\), \(64 \times 10 = 640\). Total at most \(1 + 12 + 144 + 640 = 797\). The saving grows with depth: at depth 6 the bound is about 55,000 beliefs, against about 3.3 million for forward search.

Problem 2: how deep is deep enough? Your leaf estimate is off by at most 5, and \(\gamma = 0.9\). What depth guarantees a value error of at most 1? What would that cost with 4 actions and 3 observations?

TipSolution

By Equation 2, we need \(0.9^d \times 5 \le 1\), so \(d \ge \log(0.2)/\log(0.9) = 15.3\): depth 16 (\(0.9^{16} \times 5 = 0.93\)). The tree would have about \(12^{16} \approx 1.8 \times 10^{17}\) leaves, far beyond reach. That’s why online search relies on good leaf values, sampling or pruning, rather than depth alone. And the bound is a worst case: on this page, actions were often right long before values were.

Problem 3: what gets pruned? At a belief, the upper bounds are \(Q_{\text{hi}} = (12, 9, 7.5)\) for actions \(a_1, a_2, a_3\). Branch and bound searches \(a_1\) first and finds \(Q_d = 8\). What happens next? And what if \(a_1\) had come back at 5?

TipSolution

Next is \(a_2\) (upper bound 9 > 8), so it must be searched. Suppose it returns 8.6: the best is now 8.6, and \(a_3\) is skipped, since \(7.5 \le 8.6\). Even if \(a_2\) returned less than 8, \(a_3\) would be skipped because \(7.5 \le 8\). If \(a_1\) had returned 5, both \(a_2\) and \(a_3\) would have to be searched unless \(a_2\) came back above 7.5. A loose lower bound at the leaves makes searched values small, and then nothing is pruned, as we saw for the crying baby.

Problem 4: UCB by hand. At a history \(h\) of the fork’s search, \(N(h, \cdot) = (6, 12, 1, 1)\) and \(Q(h, \cdot) = (2, 4, -30, -45)\) for (wait, ask, go left, go right). Which action does Equation 5 pick with \(c = 10\)? With \(c = 50\)?

TipSolution

\(N(h) = 20\) and \(\log 20 = 3.00\).

• \(c = 10\): wait \(2 + 10\sqrt{3.00/6} = 9.07\); ask \(4 + 10\sqrt{3.00/12} = 9.00\); go left \(-30 + 17.3 = -12.7\); go right \(-45 + 17.3 = -27.7\). Wait, narrowly.
• \(c = 50\): wait \(37.3\); ask \(29.0\); go left \(-30 + 86.5 = 56.5\); go right \(41.5\). Go left: after one bad result, a large \(c\) tries it again.

With \(c = 10\), an action that once returned \(-30\) may never be retried. With \(c = 50\), the search keeps checking. On the fork, where returns range over about 60, that’s what made the difference in Figure 6.

Problem 5: a lower bound that isn’t. Gap heuristic search initializes the lower bound at a new belief with one random rollout. At a belief whose true value is \(-20\) and whose upper bound is \(-19.8\), the rollout returns \(-12\). What does the search conclude, and how would you fix it?

TipSolution

The “gap” is \(-19.8 - (-12) = -7.8\), below any threshold \(\delta\), so the search treats the belief as solved and never explores it. Worse, when this value is backed up to its parent, the parent’s lower bound can rise above its true value too, and that can change which action is chosen. Fixes: use a true lower bound (the blind bound, or a point-based one from Chapter 21); or estimate a fixed policy’s value by averaging many long rollouts. Such an average estimates a value that can’t exceed the optimum, but it is still only an estimate. On this page, one rollout exceeded the true value 41% of the time.

Recap

1. Online planning searches from the current belief (Equation 1). Why it matters: only beliefs reachable in a few steps are considered, which is what makes large POMDPs tractable; the offline methods of Chapter 21 become the leaf values.
2. Depth shrinks leaf errors by \(\gamma^d\), at a cost of \((|\mathcal{A}||\mathcal{O}|)^d\) (Equation 2). Why it matters: search can correct a leaf’s bad decisions quickly (two steps fixed QMDP at the fork), but not its values; good leaves and cheap search go together.
3. Bounds let search prune, but only if they are tight (Equation 3). Why it matters: with a tight lower bound, branch and bound did 5% of the work at depth 5; with a loose one, 100%. Offline effort buys online speed.
4. Sampling trades exhaustiveness for noise and bias (Equation 4, Equation 5, Equation 6). Why it matters: sampled maxima are optimistic; Monte Carlo tree search needs an exploration constant on the scale of the rewards; fixing the randomness in scenarios reduces both the tree and the noise. These are the ideas behind practical solvers such as POMCP and DESPOT.
5. Gap-guided search needs true bounds (Equation 7). Why it matters: with true bounds, it certifies its answer as the gap closes; with a noisy stand-in, it can stop at once with a wrong answer.

Cheat sheet & connections

Table 4: Key equations from this page (★ = well-known by name).

Name	Formula	Ref	Cost per decision
Forward search	\(Q_d(b, a) = R(b, a) + \gamma\sum_o P(o \mid b, a)\,U_{d-1}(b'_o)\)	Equation 1	\(O((|\mathcal{A}||\mathcal{O}|)^d)\)
Depth error	\(|U_d - U^*| \le \gamma^d \varepsilon\)	Equation 2
Branch and bound	skip \(a\) if \(Q_{\text{hi}}(b, a) \le\) best found	Equation 3	at most forward search
Sparse sampling	average of \(m\) samples of \(r + \gamma U_{d-1}(b')\)	Equation 4	\(O((|\mathcal{A}|\,m)^d)\)
★ UCB1 over histories	\(Q(h, a) + c\sqrt{\log N(h)/N(h, a)}\)	Equation 5	\(O(m\,d)\) for \(m\) simulations
Determinized successor	first \((s', o)\) with cumulative \(P \ge \Phi_{ij}\)	Equation 6	\(O(|\mathcal{A}|^d m)\)
Gap-guided search	\(\arg\max_a Q_{\text{hi}}\), then the widest-gap observation	Equation 7	per exploration \(O(d\,|\mathcal{A}||\mathcal{O}|)\)

Common pitfalls

• Judging a search by its values. A shallow search can pick the right action while its value is far off, and a noisy one can have unbiased-looking values and still pick badly. Evaluate the policy in closed loop.
• An exploration constant on the wrong scale. UCB’s bonus is added to returns; set \(c\) relative to how much returns differ.
• Treating a rollout as a bound. It’s one sample. Use true bounds where a method’s correctness depends on them.
• Forgetting impossible observations. Updating a belief on an observation with probability 0 divides by zero; skip it.
• Reusing randomness across decisions by accident. Determinized search should draw a fresh \(\Phi\) for each decision, or it will make the same mistakes at every step.

Connections

• Ch 9 · Online Planning: the same methods for fully observed problems, branching on next states.
• Ch 21 · Offline Belief State Planning: the bounds used here as leaf values and for pruning.
• Ch 19 · Beliefs: the belief update applied after every real step.
• Ch 14 · Policy Validation: common random numbers, the idea behind determinized scenarios.
• Ch 23 · Controller Abstractions: policies represented as finite controllers instead of searched online.
• Appendix E · Search Algorithms: the deterministic versions of forward search, branch and bound and heuristic search.