21 · Offline Belief State Planning

Part IV — State Uncertainty

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

Big picture

Where this chapter fits

Chapter 20 solved POMDPs exactly by value iteration over conditional plans. That works for toy problems only. Exact solution of a finite-horizon POMDP is PSPACE-complete in the worst case, and the sets of alpha vectors can grow without bound. This chapter keeps Chapter 20’s representation, a value function over beliefs, but computes it approximately and offline, before the agent acts. Many methods here produce bounds: an upper bound that the true value never exceeds, or a lower bound it never falls below. Bounds let us say how good an approximation is, and they guide the search for better ones. Chapter 22 plans online instead, from the current belief only.

The question: how can we get a good value function over beliefs, with a guarantee on its quality, without solving the POMDP exactly?

The short answer: bound it from both sides, and refine where it matters.

• Cheap upper bounds pretend the agent will soon know more than it will: QMDP assumes the state becomes known after one step; the fast informed bound also uses the observations.
• Cheap lower bounds assume it can’t adapt at all.
• Point-based value iteration computes alpha vectors only at a chosen set of beliefs, giving a lower bound. Sawtooth and triangulated value functions interpolate between beliefs, giving an upper bound.
• Heuristic search tightens both bounds along the beliefs reachable from the start, until they meet.

Figure 1: Map of this chapter. Offline methods bound the optimal value over beliefs from above and below; point-based methods and interpolation refine the bounds at chosen beliefs.

The key ideas at a glance

1. Bounds make approximations checkable. If \(U_{\text{lo}}(b) \le U^*(b) \le U_{\text{hi}}(b)\), then either bound’s policy is within the gap \(U_{\text{hi}}(b) - U_{\text{lo}}(b)\) of optimal, in the sense of the value it guarantees. A gap near zero certifies near-optimality.

2. Upper bounds assume too much information. QMDP solves the fully observed MDP and averages its action values over the belief, as if the state would be revealed after one step. The fast informed bound lets the next action depend on the observation, which is tighter. Both give one alpha vector per action.

3. Lower bounds assume too little flexibility. The best-action worst-state bound takes the best action’s worst reward forever. The blind bound commits to a single action forever, ignoring observations.

4. Point-based value iteration. Instead of all beliefs, back up alpha vectors only at a finite set of beliefs \(B\), one per belief. Starting from a lower bound, it stays a lower bound and is exact at the chosen beliefs when they are well placed. Perseus backs up random beliefs until all have improved, often with fewer vectors.

5. Interpolating upper bounds. The sawtooth bound stores values at a few beliefs and interpolates with teeth that dip to each stored value. Triangulation interpolates over a regular grid of beliefs. Both remain upper bounds because the true value is convex.

6. Search where it matters. Sawtooth heuristic search starts from the initial belief, follows the upper bound’s actions and the observations with the largest gap, and tightens both bounds on the way back, until the gap at the start closes.

Vocabulary

Table 1: Terms used on this page.

Term	Plain meaning
Offline planning	Computing a policy for all beliefs before acting
Upper / lower bound	A value that the optimal value never exceeds / never falls below
QMDP	Upper bound: the fully observed MDP’s action values averaged over the belief
Fast informed bound (FIB)	Upper bound that also accounts for the observations, one step ahead
Best-action worst-state (BAWS)	Lower bound: the best action’s worst reward, forever
Blind lower bound	Lower bound: one fixed action forever
Point-based value iteration (PBVI)	Alpha-vector backups only at a chosen set of beliefs
Perseus	Randomized point-based value iteration
Sawtooth bound	Upper bound interpolating stored belief values with “teeth”
Triangulated value function	Upper bound interpolating over a regular grid of beliefs
Gap	Upper bound minus lower bound at a belief

After this chapter you can

• Compute QMDP and fast informed upper bounds, and blind and best-action worst-state lower bounds.
• Explain why QMDP undervalues information-gathering actions, and recognize problems where that matters.
• Run point-based value iteration and Perseus on a set of beliefs, and choose those beliefs.
• Evaluate sawtooth and triangulated upper bounds at any belief.
• Use heuristic search to close the gap between the bounds from a starting belief.

Intuition

TipAnalogy

You’re estimating how long a trip across an unfamiliar city will take.

• An optimistic estimate: “if I knew exactly where every traffic jam was, it would take 30 minutes”. That’s QMDP: pretend you’ll know everything. It can’t be beaten, so it’s an upper bound on how well you’ll do.
• A pessimistic estimate: “if I just drive my usual route and ignore the radio, it takes 55 minutes”. That’s the blind bound: a plan you can certainly carry out.
• Refining both: check the estimates at a few key intersections and interpolate. The truth lies between the bounds, and when they meet, you know it.

We use two problems. The crying baby of Chapter 20 has an exact solution to compare against. The fork is a small problem built for this chapter, in the problem gallery. A hiker at a fork doesn’t know which trail leads home. Choosing right earns 10, choosing wrong costs 50, and then a new hike starts. The hiker can ask a passerby for 1, and the answer is right 85% of the time; or wait, which costs nothing and teaches nothing.

Pretend you’ll know: QMDP

QMDP assumes the state will be revealed after one step. For the crying baby that’s a mild fiction, and its bound is at most 4.14 above the true value. At the fork, it’s a disaster. If you’ll know the right trail for free next step anyway, why pay to ask? QMDP waits, the belief never changes, and it waits forever: a return of 0, where the best policy earns about 27. See Equation 1.

Use what you’ll observe: the fast informed bound

The fast informed bound lets the next action depend on the observation, which tightens the crying baby’s bound to within 0.65. At the fork it still fails: after waiting, the state is unchanged and certain in its per-state calculation, so waiting still looks like it reveals the trail. Its value at the fork’s start is 97.4, compared with QMDP’s 190.0 and the true 27.11. See Equation 2.

Plan at a few beliefs: point-based value iteration

Back up alpha vectors only at a handful of beliefs. For the crying baby, 5 beliefs spaced 0.25 apart give a lower bound within 0.002 of the true value everywhere. At the fork, 21 beliefs give a policy that asks until fairly sure (below \(P(\text{home right}) =\) 0.08 go left, above 0.92 go right). It earns 27.28 ± 0.17 in simulation, asking 2.7 times per hike. See Equation 4.

Interpolate from above: sawtooth and triangulation

Store upper-bound values at a few beliefs and interpolate. Because the true value is convex, straight-line interpolation between true values stays above it. Six beliefs and three sawtooth iterations bring the crying baby’s upper bound to within 1.1. A triangulation with 11 grid beliefs gets within 0.17. See Equation 5 and Equation 7.

Close the gap where you’ll go

Starting from a sated baby, sawtooth heuristic search follows the most uncertain branch, tightening both bounds. The gap at the start fell from 83.9 to 0.009 in 24 explorations (Figure 6). See Equation 6.

Formalism

QMDP

Compute one alpha vector per action by value iteration on the fully observed MDP (ADM §21.1; M. L. Littman, A. R. Cassandra and L. P. Kaelbling, ICML, 1995):

\[ \alpha_a^{(k+1)}(s) = R(s, a) + \gamma \sum_{s'} T(s' \mid s, a) \max_{a'} \alpha_{a'}^{(k)}(s'), \qquad U_{\text{QMDP}}(b) = \max_a \alpha_a^\top b \tag{1}\]

In words. Solve the problem as if the state were visible, then average each action’s value over the belief.

Term by term.

• At convergence, \(\alpha_a(s) = Q^*_{\text{MDP}}(s, a)\), the fully observed action value.
• The \(\max_{a'}\) inside the sum picks the best next action for each next state, as if the next state were known.
• Each iteration costs \(O(|\mathcal{A}|^2|\mathcal{S}|^2)\).
• For any problem, \(U_{\text{QMDP}}(b) \ge U^*(b)\) (when run to convergence or started from an upper bound).

Why it holds. An agent that will be told the state after one step can do everything the real agent can, and more. So its value is an upper bound. The flip side: QMDP treats information as free, so it never pays for it. Actions whose only purpose is to learn look no better than doing nothing.

Fast informed bound

Let the next alpha vector depend on the observation (ADM §21.2; M. Hauskrecht, JAIR, 2000):

\[ \alpha_a^{(k+1)}(s) = R(s, a) + \gamma \sum_o \max_{a'} \sum_{s'} O(o \mid a, s')\, T(s' \mid s, a)\, \alpha_{a'}^{(k)}(s') \tag{2}\]

In words. After acting from \(s\), the agent sees an observation and may choose its next alpha vector accordingly, but still knows where it started.

Term by term.

• The max over \(a'\) now sits outside the sum over \(s'\) but inside the sum over \(o\). The choice may depend on the observation, not on the unobserved next state.
• It is never looser than QMDP, and it costs \(O(|\mathcal{A}|^2|\mathcal{S}|^2|\mathcal{O}|)\) per iteration.
• It still knows the current state \(s\) exactly. When an action doesn’t change the state, as waiting at the fork doesn’t, that knowledge carries over, and the bound again treats the state as known.

Why it holds. Knowing the current state, and choosing the next plan after seeing the observation, is more information than the real agent has. So the value is still an upper bound, but it credits the information carried by observations rather than assuming the next state is revealed.

Fast lower bounds

The best-action worst-state bound and the blind bound (ADM §21.3):

\[ r_{\text{baws}} = \frac{1}{1 - \gamma}\max_a \min_s R(s, a), \qquad \alpha_a^{(k+1)}(s) = R(s, a) + \gamma \sum_{s'} T(s' \mid s, a)\, \alpha_a^{(k)}(s') \tag{3}\]

In words. The first is the reward of the best action in its worst state, received forever. The second is the value of repeating one action forever, whatever is observed.

Term by term.

• The BAWS bound is one flat alpha vector: very loose, but safe.
• The blind iteration has no max over next actions: each vector follows a single action. It is started from the BAWS bound.

Why it holds. Both describe policies the agent could actually follow (always do \(a\)). An achievable policy’s value can’t exceed the optimum, so both are lower bounds.

Point-based value iteration

Keep a set of beliefs \(B\) and one alpha vector per belief. The backup at a belief \(b\) (ADM §21.4; J. Pineau, G. Gordon and S. Thrun, IJCAI, 2003):

\[ \alpha_{a,o} = \arg\max_{\alpha \in \Gamma} \alpha^\top \text{Update}(b, a, o), \qquad \alpha_a(s) = R(s, a) + \gamma \sum_{s', o} O(o \mid a, s')\, T(s' \mid s, a)\, \alpha_{a,o}(s'), \qquad \alpha = \arg\max_{\alpha_a} \alpha_a^\top b \tag{4}\]

In words. For each action, find the best existing plan to follow after each possible observation. Combine them into a new plan, as in Chapter 20, and keep the action whose plan is best at \(b\).

Term by term.

• \(\alpha_{a,o}\) is chosen at the belief that would actually follow, \(\text{Update}(b, a, o)\), not over all beliefs. That’s what makes it cheap.
• The combination is Chapter 20’s backup (eq. 20.17) with the chosen subplans.
• Each backup costs \(O(|\mathcal{A}||\mathcal{O}||\Gamma||\mathcal{S}|^2)\), and there are \(|B|\) of them per iteration: polynomial, not exponential.

Why it holds. Each new vector is the value of a real conditional plan: act, then follow an existing plan chosen by the observation. If every vector in \(\Gamma\) is the value of a real plan (a lower bound), so is the new one. At the beliefs in \(B\), it is exactly the Bellman backup restricted to those plans, so values rise toward the optimum there.

Perseus (M. T. J. Spaan and N. Vlassis, JAIR, 2005; ADM §21.5) backs up beliefs chosen at random and skips any belief whose value an earlier backup in the same round already improved. It often needs far fewer backups and vectors.

Sawtooth upper bound

Store belief-utility pairs \(V\), including every corner belief \(e_i\) (the states themselves). Each non-corner pair \((b', u')\) defines a tooth (ADM §21.6):

\[ U^{(b', u')}(b) = u_E^\top b + \rho(b, b')\big(u' - u_E^\top b'\big), \qquad \rho(b, b') = \min_{i:\, b'_i > 0} \frac{b_i}{b'_i}, \qquad U^V(b) = \min_{(b', u') \in V} U^{(b', u')}(b) \tag{5}\]

In words. Start from the plane through the corners’ values. Near each stored belief, the bound dips down to the stored value, like a tooth, and the overall bound is the lowest of the teeth.

Term by term.

• \(u_E\) is the vector of corner values.
• \(\rho(b, b')\) is the largest multiple of \(b'\) that fits inside \(b\): 1 at \(b = b'\), and 0 at the corners that \(b'\) doesn’t use.
• With two states, each tooth is two line segments from the corners down to \((b', u')\).
• The result is piecewise linear but not convex.

Why it holds. Write \(b = \rho b' + (1 - \rho)c\), where \(c\) is some other belief. The true value is convex, so \(U^*(b) \le \rho U^*(b') + (1 - \rho)U^*(c)\). Bounding \(U^*(b')\) by \(u'\) and \(U^*(c)\) by the corners’ plane gives exactly the tooth.

Sawtooth iteration replaces each stored value by its one-step lookahead (Chapter 20, eq. 20.13) on the current bound. Since the lookahead of an upper bound is again an upper bound, it stays one.

Heuristic search on the gap

From the initial belief, repeatedly explore (ADM §21.8; T. Smith and R. Simmons, UAI, 2004):

\[ a = \pi_{\text{hi}}(b), \qquad o = \arg\max_o \Big[U_{\text{hi}}\big(\text{Update}(b, a, o)\big) - U_{\text{lo}}\big(\text{Update}(b, a, o)\big)\Big], \qquad \text{stop when } U_{\text{hi}}(b) - U_{\text{lo}}(b) \le \delta/\gamma^d \tag{6}\]

In words. Follow the optimistic policy’s action, and go wherever the bounds disagree most. On the way back, back up both bounds at every belief visited.

Term by term.

• \(U_{\text{hi}}\) is a sawtooth bound, started from the fast informed bound; \(U_{\text{lo}}\) is a set of alpha vectors, started from the BAWS bound.
• At depth \(d\), a gap of \(\delta/\gamma^d\) contributes at most \(\delta\) to the gap at the start, so exploration stops there.
• The algorithm stops when the gap at the start belief is below \(\delta\).

Why it holds. The gap at a belief after a backup is at most \(\gamma\) times the average gap at its successors. Tightening the successors with the largest gaps shrinks the start’s gap fastest. Following the upper bound’s action is optimism under uncertainty (Chapter 15): either that action really is good, or exploring it lowers its upper bound.

Triangulated value functions

Place beliefs on a regular grid of granularity \(m\) over the simplex, the Freudenthal triangulation (ADM §21.9; W. S. Lovejoy, Operations Research, 1991), and interpolate within the small simplex that contains \(b\):

\[ U(b) = \sum_{i=1}^{n} \lambda_i\, U\big(b^{(i)}\big), \qquad \sum_i \lambda_i = 1,\quad \sum_i \lambda_i b^{(i)} = b,\quad \lambda_i \ge 0 \tag{7}\]

In words. A belief’s value is a weighted average of the values at the nearby grid beliefs that surround it.

Term by term.

• The grid has \(\binom{m + n - 1}{n - 1}\) beliefs: for two states, \(m + 1\) evenly spaced beliefs.
• The \(b^{(i)}\) are the corners of the grid simplex containing \(b\), and the \(\lambda_i\) its barycentric weights. The code finds them in \(O(n \log n)\) by sorting the fractional parts of cumulative coordinates.
• Value iteration updates the grid values by one-step lookahead on the interpolated function.

Why it holds. Linear interpolation of a convex function between points on the function lies on or above it. Value iteration on the interpolated function therefore converges to an upper bound (Lovejoy’s lemma 4).

Worked example

QMDP’s first step for the crying baby

Start from zero vectors. After one iteration, \(\alpha_a = R(\cdot, a)\): feed \((-5, -15)\), sing \((-0.5, -10.5)\), ignore \((0, -10)\) over (sated, hungry). After two, with \(\max_{a'}\alpha_{a'}(\text{sated}) = 0\) (ignore) and \(\max_{a'}\alpha_{a'}(\text{hungry}) = -10\) (ignore):

• feed, from hungry: \(-15 + 0.9 \times 0 = -15\), since feeding always sates;
• ignore, from sated: \(0 + 0.9\,(0.9 \times 0 + 0.1 \times -10) = -0.9\);
• ignore, from hungry: \(-10 + 0.9 \times -10 = -19\).

The code’s two-step QMDP vectors: feed (-5.0, -15.0); sing (-1.4, -19.5); ignore (-0.9, -19.0).

A tooth by hand

Suppose the corners have upper-bound values \(u_E = (-2, -20)\) for (sated, hungry), and one stored belief \(b' = (0.6, 0.4)\) has upper-bound value \(-10\). Evaluate the bound at \(b = (0.8, 0.2)\):

• The corners’ plane: \(u_E^\top b = 0.8(-2) + 0.2(-20) = -5.6\) at \(b\), and \(u_E^\top b' = -9.2\) at \(b'\). The stored value, \(-10\), is 0.8 below the plane there.
• The ratio: \(\rho = \min(0.8/0.6,\ 0.2/0.4) = 0.5\): half of \(b'\) fits inside \(b\).
• The tooth: the plane plus half the dip, \(-5.6 + 0.5\,(-10 - (-9.2)) = -6.0\).
• The bound: the smaller of the plane and the tooth, \(-6.0\).

A stored value above the plane (say \(-8\)) would make a tooth above the plane, and the bound would stay at the plane. Only stored values below the corners’ plane tighten the bound.

The code gives -6.0 with the stored −10, and -5.6 with −8.

Why QMDP waits at the fork

With the trail known, the hiker would always go home: \(+10\) per hike, worth \(10/(1 - 0.95) = 200\). QMDP’s value of waiting in either state is \(0 + 0.95 \times 200 = 190\), since it pretends it will then know the trail. Asking is worth \(-1 + 0.95 \times 200 = 189\), less than waiting. Going left at \(P(\text{home right}) = 0.5\) is worth \(0.5\,(10 + 190) + 0.5\,(-50 + 190) = 170\). So QMDP waits, the belief stays at 0.5, and it waits again, forever.

The policies on this page act by one-step lookahead on QMDP’s value, which takes one real step first. Waiting then scores \(0 + 0.95 \times 190 = 180.5\). Asking scores \(-1 + 0.95 \times 190 = 180.45\), because either answer (0.15 or 0.85) lands where QMDP’s value is still flat at 190. The ranking is the same:

QMDP’s one-step lookahead values at the start: wait 180.5, ask 180.4, go left 160.5, go right 160.5.

Interactive

Bounds explorer

Choose a method and the number of iterations. The crying baby’s exact value is black; upper bounds should stay above it, lower bounds below.

boundsData = FileAttachment("data/ch21-bounds.json").json()
viewof boundMethod = Inputs.select(Object.keys(boundsData.series).sort(), {label: "Method", value: "QMDP (upper)"})
viewof boundIter = Inputs.select(Object.keys(boundsData.series[boundMethod]).map(Number).sort((a, b) => a - b),
                                 {label: "Iterations (or m)"})

boundNow = {
  const y = boundsData.series[boundMethod][String(boundIter)];
  const diff = y.map((v, i) => v - boundsData.exact[i]);
  return {pts: boundsData.x.map((x, i) => ({x, bound: y[i], exact: boundsData.exact[i]})),
          worst: d3.max(diff.map(Math.abs)), above: d3.min(diff) >= -1e-6, below: d3.max(diff) <= 1e-6};
}
md`Largest distance from the exact value: **${boundNow.worst.toFixed(3)}**. ${boundNow.above ? "The curve is on or above the exact value everywhere." : boundNow.below ? "The curve is on or below the exact value everywhere." : "The curve crosses the exact value (not yet a bound of either kind)."}`

Plot.plot({
  width: 600, height: 330, style: {background: "#fcfcfb"},
  x: {domain: [0, 1], label: "P(hungry)"}, y: {label: "value", grid: true},
  marks: [
    Plot.line(boundNow.pts, {x: "x", y: "exact", stroke: "#0b0b0b", strokeWidth: 2.5}),
    Plot.line(boundNow.pts, {x: "x", y: "bound", stroke: "#2a78d6", strokeWidth: 2})
  ]
})

Figure 2: The chosen bound (blue) and the exact value (black) for the crying baby, over P(hungry).

Algorithms & code

Bounds, point-based methods, interpolation and search

Julia

# Offline belief state planning (ADM Ch. 21): bounds and approximate value functions.
# A POMDP p has p.T[s, a, s′], p.R[s, a], p.O[a, s′, o] and p.γ; alpha vectors
# are plain vectors over states, and U(b) = max α ⋅ b over a set Γ (utility).

nstates(p) = size(p.T, 1)
nactions(p) = size(p.T, 2)
nobs(p) = size(p.O, 3)

# QMDP (eq. 21.1): one alpha vector per action, by value iteration on the fully
# observed MDP. It assumes the state will be known after one step: an upper bound.
function qmdp(p; k_max = 100)
    Γ = [zeros(nstates(p)) for _ in 1:nactions(p)]
    for _ in 1:k_max
        U = [maximum(α[s′] for α in Γ) for s′ in 1:nstates(p)]  # best action per state
        Γ = [[p.R[s, a] + p.γ * (p.T[s, a, :] ⋅ U) for s in 1:nstates(p)]
             for a in 1:nactions(p)]
    end
    return Γ
end

# Fast informed bound (eq. 21.4): like QMDP, but the next alpha vector may be
# chosen per observation, so information that arrives is partly credited.
function fast_informed_bound(p; k_max = 100)
    Γ = [zeros(nstates(p)) for _ in 1:nactions(p)]
    for _ in 1:k_max
        Γ = [[p.R[s, a] + p.γ * sum(maximum(
                  sum(p.O[a, s′, o] * p.T[s, a, s′] * α[s′] for s′ in 1:nstates(p))
                  for α in Γ) for o in 1:nobs(p))
              for s in 1:nstates(p)] for a in 1:nactions(p)]
    end
    return Γ
end

# Best-action worst-state lower bound (eq. 21.5): the best action's worst
# reward, received forever.
baws_lowerbound(p) = fill(maximum(minimum(p.R[:, a]) for a in 1:nactions(p)) /
                          (1 - p.γ), nstates(p))

# Blind lower bound (eq. 21.6): commit to one action forever, ignoring
# observations; one alpha vector per action, iterated from the BAWS bound.
function blind_lowerbound(p; k_max = 100)
    Γ = [baws_lowerbound(p) for _ in 1:nactions(p)]
    for _ in 1:k_max
        Γ = [[p.R[s, a] + p.γ * (p.T[s, a, :] ⋅ Γ[a]) for s in 1:nstates(p)]
             for a in 1:nactions(p)]
    end
    return Γ
end

# Point-based backup at belief b (eqs. 21.8-21.10): for each action, pick the
# best alpha vector at each updated belief, combine them (as in eq. 20.17),
# and keep the action whose new vector is best at b.
function belief_backup(p, Γ, b)
    best, best_val = Float64[], -Inf
    for a in 1:nactions(p)
        αo = map(1:nobs(p)) do o
            po = observation_probability(p, b, a, o)
            # An impossible observation's subplan never matters; any vector works.
            po > 0 || return Γ[1]
            b′ = update_discrete(b, p.T, p.O, a, o)
            Γ[argmax([α ⋅ b′ for α in Γ])]
        end
        α = combine_alpha(p, a, αo)
        if α ⋅ b > best_val
            best, best_val = α, α ⋅ b
        end
    end
    return best
end

# Point-based value iteration (algorithm 21.7): one backup per belief in B.
function pbvi(p, B; k_max = 50, Γ = [baws_lowerbound(p)])
    for _ in 1:k_max
        Γ = [belief_backup(p, Γ, b) for b in B]
    end
    return Γ
end

# Randomized point-based value iteration (Perseus, algorithm 21.8): back up
# random beliefs until every belief in B has improved (or kept its value).
function perseus(p, B, rng; k_max = 50, Γ = [baws_lowerbound(p)])
    for _ in 1:k_max
        Γ′, todo = Vector{Float64}[], collect(B)
        while !isempty(todo)
            b = rand(rng, todo)
            α_old = Γ[argmax([α ⋅ b for α in Γ])]
            α_new = belief_backup(p, Γ, b)
            push!(Γ′, α_new ⋅ b ≥ α_old ⋅ b ? α_new : α_old)
            # Keep only beliefs whose value Γ′ has not yet matched.
            filter!(b -> utility(Γ′, b) < utility(Γ, b), todo)
        end
        Γ = Γ′
    end
    return Γ
end

# Sawtooth upper bound (eqs. 21.14-21.16). V maps beliefs to upper-bound
# utilities and must contain every corner belief e_i. Each non-corner pair
# (b′, u′) is a "tooth": the corners' plane, dipping down to u′ at b′.
function sawtooth(V, b)
    haskey(V, b) && return V[b]
    n = length(b)
    corners = [[i == j ? 1.0 : 0.0 for j in 1:n] for i in 1:n]
    uE = [V[e] for e in corners]
    best = uE ⋅ b                          # the corners' plane alone
    for (b′, u′) in V
        b′ in corners && continue
        # ρ: how much of b′ fits inside b (the minimum ratio, eq. 21.14).
        ρ = minimum(b[i] / b′[i] for i in 1:n if b′[i] > 0)
        best = min(best, uE ⋅ b + ρ * (u′ - uE ⋅ b′))
    end
    return best
end

# Sawtooth iteration (algorithm 21.10): replace each non-corner value in B by
# its one-step lookahead on the current sawtooth bound.
function sawtooth_iteration(p, V, B; k_max = 10)
    corners = [[i == j ? 1.0 : 0.0 for j in 1:nstates(p)] for i in 1:nstates(p)]
    for _ in 1:k_max
        U = b -> sawtooth(V, b)
        V = Dict(b => (b in corners ? V[b] : greedy_belief(p, U, b).u) for b in B)
    end
    return V
end

# One random step in belief space (algorithm 21.11): sample a state from b,
# move and observe with the model, and update the belief.
function randstep(p, b, a, rng)
    s = rand(rng, Categorical(b))                    # Distributions.Categorical
    s′ = rand(rng, Categorical(p.T[s, a, :]))
    o = rand(rng, Categorical(p.O[a, s′, :]))
    return update_discrete(b, p.T, p.O, a, o), p.R[s, a]
end

# Exploratory belief expansion (algorithm 21.13): from each belief, try every
# action once and keep the new belief farthest (in L1) from the set so far.
function exploratory_belief_expansion(p, B, rng)
    B′ = copy(B)
    for b in B
        cands = [randstep(p, b, a, rng)[1] for a in 1:nactions(p)]
        dist(c) = minimum(sum(abs.(c .- x)) for x in B′)
        c = cands[argmax(dist.(cands))]
        dist(c) > 0 && push!(B′, c)
    end
    return B′
end

# Sawtooth heuristic search (algorithm 21.14): from b0, repeatedly follow the
# upper bound's greedy action and the observation with the largest gap,
# then tighten both bounds on the way back. Returns (V, Γ, gaps at b0).
function sawtooth_heuristic_search(p, b0; depth = 10, k_max = 30, δ = 0.01)
    fib = fast_informed_bound(p)
    corners = [[i == j ? 1.0 : 0.0 for j in 1:nstates(p)] for i in 1:nstates(p)]
    V = Dict(e => utility(fib, e) for e in corners)          # upper bound
    Γ = [baws_lowerbound(p)]                                   # lower bound
    gap(b) = sawtooth(V, b) - utility(Γ, b)
    function explore(b, d)
        (d >= depth || gap(b) <= δ / p.γ^d) && return
        a = greedy_belief(p, b -> sawtooth(V, b), b).a
        # The observation leading to the belief with the widest gap.
        obs = [o for o in 1:nobs(p) if observation_probability(p, b, a, o) > 0]
        next = [update_discrete(b, p.T, p.O, a, o) for o in obs]
        b′ = next[argmax(gap.(next))]
        explore(b′, d + 1)
        b′ in corners || (V[b′] = greedy_belief(p, b -> sawtooth(V, b), b′).u)
        push!(Γ, belief_backup(p, Γ, b′))
        return
    end
    gaps = [gap(b0)]
    for _ in 1:k_max
        explore(b0, 0)
        V[b0] = min(sawtooth(V, b0), greedy_belief(p, b -> sawtooth(V, b), b0).u)
        push!(Γ, belief_backup(p, Γ, b0))
        push!(gaps, gap(b0))
        gaps[end] < δ && break
    end
    return V, Γ, gaps
end

# Freudenthal interpolation (Lovejoy, 1991) on the belief simplex with
# granularity m. Returns the vertices (beliefs whose entries are multiples of
# 1/m) of the sub-simplex containing b, and weights λ with Σλ = 1, Σλ v = b.
function freudenthal(b, m)
    n = length(b)
    # Cumulative coordinates: x_i = m (b_i + ... + b_n). x_1 = m exactly; set it
    # directly, since a sum a hair below 1 would floor to m - 1.
    x = [i == 1 ? float(m) : m * sum(b[i:n]) for i in 1:n]
    base = floor.(x)
    d = x .- base                                      # fractional parts
    # Visit coordinates by decreasing fraction; coordinate 1 (fraction 0) last.
    order = sortperm(1:n, by = i -> (i == 1, -d[i]))
    to_belief(v) = [(v[i] - (i < n ? v[i+1] : 0.0)) / m for i in 1:n]
    # Vertices: the base, then the base stepped up along order[1], order[2], ...
    verts, v = [to_belief(base)], copy(base)
    for k in 1:n-1
        v[order[k]] += 1
        push!(verts, to_belief(v))
    end
    # Weights: 1 - d_(1), then successive differences of the sorted fractions.
    λ = [1 - d[order[1]]; [d[order[k]] - d[order[k+1]] for k in 1:n-1]]
    return verts, λ
end

# Triangulated value iteration (algorithm 21.16): values at the grid beliefs,
# interpolated elsewhere; each sweep replaces them by one-step lookahead.
# Starting from 0 gives an upper bound when rewards are never positive.
function triangulated_iteration(p, m; k_max = 50)
    n = nstates(p)
    key(b) = round.(b; digits = 10)                    # grid beliefs as keys
    grid = [key(collect(c) ./ m)
            for c in Iterators.product(fill(0:m, n)...) if sum(c) == m]
    V = Dict(b => 0.0 for b in grid)
    function U(b)
        verts, λ = freudenthal(b, m)
        # Skip zero weights: on a tie their vertex may lie off the grid.
        return sum(l * V[key(v)] for (v, l) in zip(verts, λ) if l > 1e-12)
    end
    for _ in 1:k_max
        V = Dict(b => greedy_belief(p, U, b).u for b in grid)   # U sees the old V
    end
    return V, U
end

Python

import numpy as np

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

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


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


def backup(p, G, b):
    """eq. 21.8-21.10: the best new alpha vector at belief b from the vectors G."""
    best = None
    for a in range(nA):
        alpha = p.R[:, a].copy()
        for o in range(nO):
            po = (b @ p.T[:, a, :]) @ p.O[a, :, o]
            sub = G[np.argmax(G @ belief_update(p, b, a, o))] if po > 0 else G[0]
            alpha += p.gamma * p.T[:, a, :] @ (p.O[a, :, o] * sub)
        if best is None or alpha @ b > best @ b:
            best = alpha
    return best


def lookahead_action(p, G, b):
    """eq. 20.13 with U(b) = max over G of alpha . b."""
    q = []
    for a in range(nA):
        v = p.R[:, a] @ b
        for o in range(nO):
            po = (b @ p.T[:, a, :]) @ p.O[a, :, o]
            if po > 0:
                v += p.gamma * po * (G @ belief_update(p, b, a, o)).max()
        q.append(v)
    return int(np.argmax(q))


B = [np.array([1 - x, x]) for x in np.linspace(0, 1, 21)]
G = np.full((1, nS), p.R.min(axis=0).max() / (1 - p.gamma))    # best-action worst-state bound
for _ in range(300):
    G = np.array([backup(p, G, b) for b in B])

b0 = np.array([0.5, 0.5])
print("QMDP at the start:", p.actions[lookahead_action(p, qmdp(p), b0)],
      "| point-based:", p.actions[lookahead_action(p, G, b0)], f"(value {(G @ b0).max():.3f})")
assert lookahead_action(p, qmdp(p), b0) == 0 and lookahead_action(p, G, b0) == 1
assert abs((G @ b0).max() - 27.1149) < 1e-3

NoteReading the Julia code (for Python programmers)

• map(1:nobs(p)) do o ... end applies the block to each observation, like a list comprehension with a multi-line body; return inside the block returns from the block only.
• filter!(b -> ..., todo) removes, in place, every belief for which the condition fails.
• Dict(e => utility(fib, e) for e in corners) builds a dictionary from pairs, like a dict comprehension.
• function explore(b, d) ... end inside another function is a closure that sees and changes V and Γ, like a nested def using nonlocal.
• sortperm(1:n, by = i -> (i == 1, -d[i])) sorts indices by a tuple key: false sorts before true, so index 1 goes last, and ties within each group are ordered by decreasing d.
• Iterators.product(fill(0:m, n)...) is itertools.product(range(m + 1), repeat=n).

Run them

p = crying_baby()
upper = fast_informed_bound(p; k_max = 300)
beliefs = [[1 - x, x] for x in 0:0.25:1]
lower = pbvi(p, beliefs; k_max = 100)
gap(b) = utility(upper, b) - utility(lower, b)

gap (generic function with 1 method)

gap between the fast informed bound and point-based VI: 0.0: 0.236, 0.25: 0.611, 0.5: 0.213, 0.75: 0.213, 1.0: 0.213

Results

Upper and lower bounds for the crying baby

Figure 3: Fast bounds for the crying baby. Left: QMDP (dashed) and the fast informed bound (solid) after 1, 2, 3 and 300 iterations, above the exact value (black). Right: the best-action worst-state and blind lower bounds, far below it.

At convergence, QMDP overestimates by up to 4.14 and the fast informed bound by up to 0.65. The blind bound, one action forever, falls up to 32.9 below. Always feeding and always ignoring are both far from adaptive care.

Point-based value iteration and Perseus

Figure 4: Lower bounds from point-based value iteration (left) and Perseus (right) on five beliefs (P(hungry) = 0, 0.25, 0.5, 0.75, 1; ticks), after 0, 5, 10, 20 and 40 iterations, rising toward the exact value (black).

After 40 iterations, point-based value iteration is within 1.197 of the exact value everywhere, using 2 distinct alpha vectors. Perseus is within 1.918 with 2. Five well-spread beliefs suffice here because the exact value has only 2 pieces (Chapter 20).

Sawtooth and triangulated upper bounds

Figure 5: Interpolating upper bounds for the crying baby. Left: the sawtooth bound on six beliefs (ticks) after 1, 2, 3 and 20 iterations, started from the fast informed bound’s corner values. Right: triangulated value iteration with grids of 3, 6 and 11 beliefs. The exact value is black.

The sawtooth bound is within 1.07 after 20 iterations; its remaining error sits between the stored beliefs, where the teeth interpolate. The triangulated bound with 3, 6 and 11 grid beliefs exceeds the exact value by at most 2.45, 0.56 and 0.17.

Closing the gap from a starting belief

Figure 6: Sawtooth heuristic search from a sated baby: the gap between the upper (sawtooth) and lower (alpha vector) bounds at the start belief, after each exploration (log scale).

The search only visits beliefs reachable from a sated baby, under the upper bound’s policy. It closes the gap there without making either bound tight elsewhere.

The fork: when information has to be paid for

Figure 7: The fork. Left: value over P(home right) according to QMDP and the fast informed bound (upper bounds), point-based value iteration on 21 beliefs (lower bound) and triangulated value iteration (upper bound); the last two nearly coincide. Right: each method’s one-step lookahead action at every belief.

• QMDP waits in a band around 50–50, from \(P(\text{home right}) =\) 0.47 to 0.53, and asks outside it. Its value is flat at 190.0 across the middle and rises only near the ends. So asking looks worthwhile only if a likely answer would land near an end. Starting from 50–50, the hiker waits, the belief never moves, and the return is exactly 0.
• The fast informed bound waits over a wider band, from 0.27 to 0.73, with a value near 97.0 there. It too never leaves the fork from 50–50. Both values assume the trail will somehow become known.
• The point-based policy asks until \(P(\text{home right})\) is below 0.08 or above 0.92, then goes. In simulation it asked 2.7 times per hike, chose wrong 3.0% of the time, and earned 27.28 ± 0.17.
• The bounds pinch. Point-based value iteration (a lower bound) and triangulation (an upper bound) agree at the start to within 5.9e-6. So the optimal value is 27.115, and the point-based policy is essentially optimal.
• Exact value iteration struggles here. Chapter 20’s method still keeps 23 alpha vectors after 10 steps, and has to build 2116 candidate plans to get there, a number that grows with the square of the kept set. Its 10-step value at the start is only 9.73, far from the infinite-horizon 27.11: many hikes lie beyond 10 steps.

Solved problems

Problem 1: a QMDP value. A two-state POMDP has fully observed action values \(Q(s_1, a_1) = 10\), \(Q(s_1, a_2) = 4\), \(Q(s_2, a_1) = 0\), \(Q(s_2, a_2) = 6\). What does QMDP choose at \(b = (0.4, 0.6)\), and what value does it claim?

TipSolution

\(\alpha_{a_1} = (10, 0)\) and \(\alpha_{a_2} = (4, 6)\). At \(b\): \(a_1 \to 4\) and \(a_2 \to 1.6 + 3.6 = 5.2\). QMDP chooses \(a_2\) and claims 5.2. That’s an upper bound on the true value: a real agent at \(b\) can’t do better than one who will learn the state immediately.

Problem 2: why the fast informed bound is tighter. In Equation 2 the max over \(a'\) sits inside the sum over \(o\); in QMDP it sits inside the sum over \(s'\). Explain why moving the max outward can only lower the bound.

TipSolution

QMDP computes \(\sum_{s'} T(s')\max_{a'}\alpha_{a'}(s')\), choosing the best vector separately for every next state. That is the same as \(\sum_o \sum_{s'} O(o \mid s')T(s')\max_{a'}\alpha_{a'}(s')\), since the observation probabilities sum to 1. The fast informed bound instead computes \(\sum_o \max_{a'}\sum_{s'} O\,T\,\alpha_{a'}(s')\), one vector per observation. For every \(o\), a maximum of a sum is at most the sum of maxima, so the fast informed value is at most QMDP’s. It knows less at choice time: the observation, not the next state.

Problem 3: a point-based backup’s guarantee. Your alpha vectors are all lower bounds. After a point-based backup at belief \(b\), why is the new vector also a lower bound everywhere, not just at \(b\)?

TipSolution

The new vector is the exact value of a concrete conditional plan: take action \(a\), then after each observation \(o\) follow the plan behind \(\alpha_{a,o}\). That plan’s value at any belief is at most the optimal value there. Its value is at least what the new vector says, because each \(\alpha_{a,o}\) is itself a lower bound on its plan. Choosing the subplans using \(b\) only affects how good the plan is, not whether its vector is achievable.

Problem 4: triangulation weights. With two states and granularity \(m = 4\), which grid beliefs surround \(b = (0.3, 0.7)\), with what weights, and what is the interpolated value if the grid values are \(U(0.25, 0.75) = -20\) and \(U(0.5, 0.5) = -16\)?

TipSolution

The grid beliefs are \((1, 0), (0.75, 0.25), (0.5, 0.5), (0.25, 0.75), (0, 1)\). \(b\) lies between \((0.25, 0.75)\) and \((0.5, 0.5)\): \(0.3 = 0.8 \times 0.25 + 0.2 \times 0.5\), so the weights are 0.8 and 0.2. \(U(b) \approx 0.8(-20) + 0.2(-16) = -19.2\). If the grid values are upper bounds and the true value is convex, this interpolation is also an upper bound.

Problem 5: design a problem that breaks QMDP. The fork breaks QMDP because a free action teaches nothing. Would QMDP still wait if waiting cost 2 per step? What does that suggest?

TipSolution

QMDP would value waiting at \(-2 + 0.95 \times 200 = 188\) and asking at \(189\), so it would ask. Then it would ask again and again: at any belief short of certainty, QMDP compares asking (189) with going under uncertainty, and only goes when it’s nearly sure. It would behave reasonably, by accident: its preference would be right only because asking happens to be cheaper than waiting. QMDP’s rankings of information-gathering actions are driven by their costs, never by their information. Any problem where the informative action is not the cheapest safe action will fool it.

Recap

1. Offline approximations come with bounds; the gap measures their quality (Equation 6). Why it matters: for the fork, the lower and upper bounds pinched to within a thousandth at the start, certifying the point-based policy as essentially optimal without solving exactly.
2. QMDP and the fast informed bound are cheap upper bounds that overvalue information (Equation 1, Equation 2). Why it matters: they are often good enough, within 0.65 for the crying baby. But in problems like the fork, where information must be bought, both wait forever from an even start. Online methods (Chapter 22) often use them as optimistic heuristics instead.
3. Point-based value iteration gives lower bounds at polynomial cost (Equation 4). Why it matters: backing up only at chosen beliefs sidesteps Chapter 20’s explosion of alpha vectors; this is the idea behind modern solvers such as SARSOP.
4. Convexity turns interpolation into upper bounds (Equation 5, Equation 7). Why it matters: sawtooth and triangulated values bound from above, giving the other side of the gap.
5. Heuristic search focuses on beliefs that matter from the start (Equation 6). Why it matters: reachable beliefs are usually a tiny part of the belief space, and closing the gap only there is what makes large POMDPs solvable offline.

Cheat sheet & connections

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

Name	Formula	Ref
★ QMDP	\(\alpha_a(s) = R(s, a) + \gamma\sum_{s'}T(s' \mid s, a)\max_{a'}\alpha_{a'}(s')\)	Equation 1
Fast informed bound	\(\alpha_a(s) = R + \gamma\sum_o\max_{a'}\sum_{s'}O\,T\,\alpha_{a'}(s')\)	Equation 2
BAWS and blind bounds	\(\max_a\min_s R(s, a)/(1 - \gamma)\); \(\alpha_a = R + \gamma T\alpha_a\)	Equation 3
★ Point-based backup	best \(\alpha_{a,o}\) at \(\text{Update}(b, a, o)\), combined, best at \(b\)	Equation 4
Sawtooth	\(\min_{(b', u')}\, u_E^\top b + \rho(b, b')(u' - u_E^\top b')\)	Equation 5
Gap-driven search	follow \(\pi_{\text{hi}}\), the widest-gap observation; stop at \(\delta/\gamma^d\)	Equation 6
Triangulation	\(U(b) = \sum_i\lambda_i U(b^{(i)})\) over the enclosing grid simplex	Equation 7

Common pitfalls

• Using QMDP where information costs something. It will never pay for information, and may do nothing at all.
• Stopping QMDP early. Before convergence, it’s an upper bound only if started from one (for example, the best-action best-state value).
• Belief points that miss the reachable beliefs. Point-based bounds are only tight near the chosen beliefs; choose them by simulating from the start belief.
• Comparing against a finite-horizon “exact” value. A 60-step solution is not the infinite-horizon value; with rewards of −10 per step it can be off by tenths.
• Reading a lower bound as the value of its policy. A lower bound is guaranteed, but the policy acting greedily on it may do better; simulate to find out.

Connections

• Ch 20 · Exact Belief State Planning: alpha vectors, the backup, and one-step lookahead used throughout this page.
• Ch 8 · Approximate Value Functions: interpolation over grids and simplexes, here over beliefs.
• Ch 9 · Online Planning: heuristic search with bounds in fully observed problems.
• Ch 15 · Exploration and Exploitation: the value of information, which QMDP ignores.
• Ch 22 · Online Belief State Planning: planning from the current belief, using these bounds as heuristics.
• Appendix C · Computational Complexity: why general infinite-horizon POMDPs can’t be solved exactly, which is why this chapter computes bounds.