M12-T4 — POMDPs: Acting on a Belief

Learning objectives

After this lesson, you should be able to:

• Define a POMDP and explain why the belief is a sufficient statistic for the history.
• Write the Bayes update of the belief as the transition of a belief-space MDP and compute the expected reward in a belief.
• Run value iteration on a discretised belief space and read the optimal policy as regions of belief.
• Explain the value of information with the tiger problem, and compare thresholded and naive policies.

The intuition

Two doors; behind one is a tiger and behind the other a treasure, at random. Opening the right door wins 10, opening the tiger's loses 100. The robot may listen at a cost of 1: it hears the tiger on the correct side 85% of the time. After opening a door, a new problem starts. What should it do?

At the start the belief is ½ for each door. Opening a door at once is a coin flip with expected reward $\tfrac12(10)+\tfrac12(-100)=-45$: terrible. Listening costs 1 and changes the belief: one “tiger left” reading gives, by Bayes' rule, $0.85\cdot0.5/(0.85\cdot0.5+0.15\cdot0.5)=0.85$. Is that enough? Opening on 0.85 loses 100 with probability 0.15: $0.85(10)+0.15(-100)=-6.5$ on average, still bad. Two consistent readings give 0.970 (the loss probability is 0.03, $0.97(10)+0.03(-100)=6.7$), good enough. A second kind of good decision: if the two readings disagree, the belief returns to ½ and listening again is right.

Value iteration finds the optimal policy automatically. The value of a belief of ½ is 19.4 (in discounted reward, $\gamma=0.95$), and rises towards 28 as the belief approaches certainty: knowing is worth about 9 units. The optimal policy listens while the belief is between 0.037 and 0.963 and opens a door beyond that, which is exactly “listen until two net readings agree” (belief 0.970 after two, 0.85 after one).

The right panel measures the policies by simulation over 60 000 steps. Guessing: −45 per step. Listening once and trusting it (threshold 0.85): −3.8, because of 15% errors costing 100 each. Always listening: −1. Listening until the belief reaches 0.95, 0.97 or 0.99: about +1 per step, as good as the optimal policy (0.98): the thresholds from 0.95 to 0.99 are all nearly optimal, since 0.95 and 0.97 are reached by the same two readings and 0.99 by one more. The smart policy is not smarter than a good threshold here; the point is where the threshold sits.

A POMDP policy is a function from beliefs to actions. Sensing is an action with a cost; its value is the reduction in expected loss from deciding with a sharper belief.

Definitions

POMDP

States $s$, actions $a$, observations $o$, transition $p(s^\prime\mid s,a)$, observation model $p(o\mid s^\prime,a)$, reward $r(s,a)$, discount $\gamma$. The state is hidden.

Belief $b$

The distribution over states given the history: $b(s)=p(s_t=s\mid a_{0:t-1},o_{1:t})$. It is the output of the Bayes filter of Module 6.

Belief update $\tau(b,a,o)$

The Bayes filter step: predict with the action, correct with the observation.

Policy $\pi(b)$

A rule that maps a belief to an action.

Value function $V(b)$

The expected discounted reward of acting optimally from belief $b$.

Value of information

The gain in expected reward from sensing before acting: $\mathbb{E}_o[V^*(\tau(b,a,o))]-\max_a r(b,a)$ for a one-step view.

Derivation: the belief is a sufficient statistic; the tiger numbers

Why beliefs are enough

The value of acting from a history $h_t=(a_0,o_1,\dots,a_{t-1},o_t)$ could depend on every detail of it. It does not.

1. $$\text{future reward}=f\bigl(s_t,\ \text{future actions},\ \text{future noise}\bigr)$$

   By the Markov property of the hidden state, the future depends on the past only through the current state $s_t$.

2. $$\mathbb{E}\bigl[\text{future reward}\mid h_t\bigr]=\sum_sb_t(s)\,\mathbb{E}\bigl[\text{future reward}\mid s_t=s\bigr]$$

   Averaging over the hidden state with weights $b_t(s)=p(s_t=s\mid h_t)$. The history enters only through the belief.

3. $$b_{t+1}=\tau(b_t,a_t,o_{t+1})$$

   And the next belief is a function of the current belief, the action and the new observation (the Bayes filter): the belief evolves as a Markov process.

Hence the POMDP is an MDP on the belief space, which is continuous (a simplex of dimension $|S|-1$). For the tiger problem it is the interval $[0,1]$ of $b=P(\text{tiger left})$, and the Bellman equation can be solved on a grid, as here.

The tiger numbers

1. $$b^\prime=\frac{0.85\,b}{0.85\,b+0.15\,(1-b)}\ \ (\text{heard left}),\qquad b^\prime=\frac{0.15\,b}{0.15\,b+0.85\,(1-b)}\ \ (\text{heard right})$$

   The belief update for the listening action, from Bayes’ rule (Module 3).

2. $$\text{odds}^\prime=\text{odds}\times\frac{0.85}{0.15}=\text{odds}\times5.67$$

   In odds form each reading multiplies the odds by 5.67 (log odds add 1.73): the log-odds filter of Module 3 again. Two agreeing readings give odds 32.1, belief 0.970; three give 182, belief 0.995.

3. $$r(b,\text{open left})=b(-100)+(1-b)(10),\quad r(b,\text{open right})=(1-b)(-100)+b(10)$$

   Expected immediate reward of opening a door in belief $b$. Opening beats listening (reward −1, plus the value of a better belief) when the chance of the tiger being behind the chosen door is small enough.

4. $$b^*:\ r(b^*,\text{open})+\gamma V(\tfrac12)=-1+\gamma\bigl[p_1V(b_1)+p_2V(b_2)\bigr]$$

   The threshold is where the value of opening equals the value of listening once more. The value iteration places it at $b^*=0.963$, between the belief after one reading (0.85, listen) and after two (0.970, open).

A belief of 0.85 is not enough to act when a mistake costs ten times what a success earns. The decision threshold depends on the payoffs, not on a fixed confidence level.

A worked example

The tiger problem with accuracy 0.85, reward +10 for the safe door, −100 for the tiger, −1 for listening, discount 0.95, beliefs on a grid of 401 points with linear interpolation.

1. Value iteration. It converges in 272 sweeps. The value of the initial belief (0.5) is 19.37; at 0.7 it is 20.03, at 0.9 22.57, at 0.97 25.10 and at 0.999 28.29. The best action is to listen for beliefs up to 0.95 (and symmetrically from 0.05), and to open the door away from the likely tiger from 0.97. The optimal policy listens while the belief is between 0.037 and 0.963.
2. Policies by simulation (60 000 steps each). Guess a door at once: −45.06 per step. Always listen: −1.00. Listen once and trust it (threshold 0.85): −3.80. Listen until the belief reaches 0.95: 0.98; 0.97: 0.97; 0.99: 0.97. The optimal policy: 0.98. The optimum is about 1 per step of reward, from a problem in which a blind guess costs 45.
3. The value of information. The value function at the uniform belief (19.37) against the value at certainty (about 28.3) says that knowing the tiger's side is worth about 9 units in discounted reward, which two readings (cost 2) obtain with 97% confidence: the information is worth far more than it costs. If a wrong door cost little, the same readings would be worth less and the optimal policy would act sooner.

import math
from robotprob import Rng, mean

# the tiger problem: a tiger is behind the left or the right door (state). The robot can listen (cost 1, and the noise is heard correctly
# with probability 0.85) or open a door (+10 if it is the safe one, -100 if it is the tiger's). Opening a door starts a new problem at random.
ACC, R_LISTEN, R_WIN, R_LOSE, GAMMA = 0.85, -1.0, 10.0, -100.0, 0.95
# the belief b = P(tiger on the left) is all the robot needs to remember
def update(b, heard_left):
    pl = ACC if heard_left else 1 - ACC                      # P(hear this | tiger left)
    pr = 1 - ACC if heard_left else ACC                      # P(hear this | tiger right)
    z = pl * b + pr * (1 - b)
    return pl * b / z, z                                     # Bayes' rule: the new belief and the probability of this observation

def reward(b, a):                                            # the expected immediate reward in belief b
    if a == 'listen': return R_LISTEN
    p_tiger_here = b if a == 'open_left' else 1 - b
    return p_tiger_here * R_LOSE + (1 - p_tiger_here) * R_WIN

# value iteration on a grid of beliefs
GRID = [i / 400 for i in range(401)]
def interp(V, b):
    x = b * 400; i = min(399, int(x)); f = x - i
    return V[i] * (1 - f) + V[i + 1] * f
V = [0.0] * 401
for sweep in range(300):
    newV = []
    for b in GRID:
        best = -1e18
        for a in ('open_left', 'open_right', 'listen'):
            if a == 'listen':
                q = R_LISTEN
                for heard_left in (True, False):
                    nb, z = update(b, heard_left)
                    q += GAMMA * z * interp(V, nb)
            else:
                q = reward(b, a) + GAMMA * interp(V, 0.5)                          # a new problem starts: the belief is 0.5 again
            best = max(best, q)
        newV.append(best)
    if max(abs(a - b) for a, b in zip(V, newV)) < 1e-6: V = newV; break
    V = newV
def best_action(b):
    qs = {}
    for a in ('open_left', 'open_right', 'listen'):
        if a == 'listen':
            qs[a] = R_LISTEN + GAMMA * sum(z * interp(V, nb) for nb, z in (update(b, True), update(b, False)))
        else:
            qs[a] = reward(b, a) + GAMMA * interp(V, 0.5)
    return max(qs, key=qs.get), qs
print('value iteration finished after', sweep + 1, 'sweeps; the value of the starting belief 0.5 is', round(interp(V, 0.5), 2))
print('belief P(tiger left)   best action     value of the belief')
for b in (0.5, 0.7, 0.85, 0.9, 0.95, 0.97, 0.98, 0.99, 0.999):
    a, qs = best_action(b)
    print(str(b).rjust(12), a.rjust(16), str(round(interp(V, b), 2)).rjust(14))
th = next(b for b in GRID if b > 0.5 and best_action(b)[0] == 'open_right')
print('the optimal policy listens while the belief is between', round(1 - th, 3), 'and', round(th, 3), 'and opens a door beyond that')

# simulate policies on the continuing problem: reward per step
def simulate(policy, steps=60000, seed=2):
    rng = Rng(seed)
    tiger_left = rng.random() < 0.5
    b, total = 0.5, 0.0
    for _ in range(steps):
        a = policy(b, rng)
        if a == 'listen':
            total += R_LISTEN
            heard_left = (rng.random() < ACC) == tiger_left
            b, _z = update(b, heard_left)
        else:
            opened_left = a == 'open_left'
            total += R_LOSE if opened_left == tiger_left else R_WIN
            tiger_left = rng.random() < 0.5; b = 0.5
    return total / steps
def threshold_policy(th):
    return lambda b, rng: 'open_right' if b >= th else ('open_left' if b <= 1 - th else 'listen')
policies = {'always listen': lambda b, rng: 'listen',
            'guess a door at once (belief 0.5)': lambda b, rng: 'open_left' if rng.random() < 0.5 else 'open_right',
            'listen once, then trust it': None,
            'listen until the belief is 0.95': threshold_policy(0.95),
            'listen until the belief is 0.97': threshold_policy(0.97),
            'listen until the belief is 0.99': threshold_policy(0.99),
            'optimal (value iteration)': lambda b, rng: best_action(b)[0]}
# the policy that listens once and acts on the single reading is a threshold policy with threshold 0.85
policies['listen once, then trust it'] = threshold_policy(0.85)
print('policy                                  average reward per step')
for name, pol in policies.items():
    print(name.ljust(40), str(round(simulate(pol), 2)).rjust(8))

value iteration finished after 272 sweeps; the value of the starting belief 0.5 is 19.37
belief P(tiger left)   best action     value of the belief
         0.5           listen          19.37
         0.7           listen          20.03
        0.85           listen          21.44
         0.9           listen          22.57
        0.95           listen          23.79
        0.97       open_right           25.1
        0.98       open_right           26.2
        0.99       open_right           27.3
       0.999       open_right          28.29
the optimal policy listens while the belief is between 0.037 and 0.963 and opens a door beyond that
policy                                  average reward per step
always listen                                -1.0
guess a door at once (belief 0.5)          -45.06
listen once, then trust it                   -3.8
listen until the belief is 0.95              0.98
listen until the belief is 0.97              0.97
listen until the belief is 0.99              0.97
optimal (value iteration)                    0.98

In robotics

Where beliefs drive decisions in robotics

• Active localisation and exploration: choose where to move to reduce the pose uncertainty (turn to see a distinctive landmark), or which frontier of the map to visit.
• Manipulation under uncertainty: push, touch, or look to reduce the uncertainty about an object's pose before grasping, as in “tactile localisation”.
• Navigation in a changing world: plan with a belief about where people are, or where a door is open.
• Human–robot interaction: a belief about the human's goal, with questions as actions.

Why exact POMDPs are hard, and what is done

The belief space has dimension $|S|-1$, so the grid approach of this lesson is exponential in the number of states. Practical methods:

• Point-based value iteration (PBVI, SARSOP, HSVI): back up the value only at a sample of reachable beliefs, and represent it by a set of alpha-vectors (the exact value is piecewise linear and convex).
• Online search (POMCP, DESPOT): from the current belief, simulate with particles a tree of actions and observations, with a particle filter as the belief.
• QMDP and heuristics: solve the fully observed MDP and act on the belief-weighted action values. It assumes the state will be known after the next step, so it undervalues actions whose only purpose is to gather information; it is a reasonable heuristic where sensing is incidental and a poor one where it is the point.
• Belief-space planning: plan in the space of Gaussian beliefs (mean and covariance) with the filter's covariance update as the dynamics, as in belief-space iLQG.

The thread of the course

Every ingredient has appeared in the course: the belief is the Bayes filter (Modules 6–9), represented by a Gaussian, a grid or particles; its update uses the sensor models of Module 5; the value of information is an expected posterior quantity from Modules 3–4; and the cost of a wrong decision brings in the decision-theoretic side of probability. A robot that plans with its belief, not with its best guess, is doing probabilistic robotics in the full sense.

Common misconceptions

Key takeaways

1. A POMDP has a hidden state, observations and rewards; the belief (the output of the Bayes filter) is a sufficient statistic for the history.
2. It becomes an MDP on belief space: the transition is the belief update, the reward is the expected reward, and the Bellman equation is V(b) = max_a [r(b,a) + γ Σ_o p(o|b,a) V(τ(b,a,o))].
3. In the tiger problem, the optimal policy is a threshold: listen while the belief is within 0.037 and 0.963, open the safe-looking door beyond. Two agreeing readings (belief 0.970) cross it, one (0.85) does not.
4. Guessing earned −45 per step, trusting one reading −3.8, optimal +0.98; knowing the state is worth about 9 units of discounted value over not knowing it.
5. Exact solutions are exponential in the number of states; point-based, online (particle) and belief-space methods make larger problems tractable. Acting on the most likely state fails exactly when information gathering matters.

References and further reading

Each source is marked free or paid. Free to read does not mean free to reuse: the course resources page lists every source with its licence.

• L. P. Kaelbling, M. L. Littman and A. R. Cassandra, “Planning and acting in partially observable stochastic domains”, Artificial Intelligence 101 (1–2), 1998, the source of the tiger problem. Paid or institutional access; the authors’ copies were not checked here.
• S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, MIT Press, 2005, chapter 15 (partially observable Markov decision processes). Paid book.
• M. J. Kochenderfer, T. A. Wheeler and K. H. Wray, Algorithms for Decision Making, MIT Press, 2022 , the chapters on POMDPs (belief updates, exact and offline solutions, online planning). Free PDF for personal use on the book’s site; the licence terms were not checked here.
• J. Pineau, G. Gordon and S. Thrun, “Point-based value iteration: an anytime algorithm for POMDPs”, IJCAI 2003. Paid or institutional access; free copies exist but were not checked here.

Knowledge check

Three questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

This is the last lesson. The ten labs of the course let you write these algorithms yourself, in Python in the browser, from noisy motion and Bayes filters to Kalman filters, particle filters, occupancy grids and pose graphs.

Related content

Nothing below is required to finish this lesson.

• Before
  M12-T3: Smoothing: Using Future Measurements

  Distinguish filtering from smoothing, run the Rauch-Tung-Striebel backward pass, and relate fixed-lag smoothing to factor graphs.

Other courses on this site treat neighbouring topics from their own angle:

• UAV M3-T6: Error-State Kalman Filter
• UAV M6-T5: PX4 state estimation and EKF2
• Physical AI: Belief under uncertainty