Understand the POMDP
Framework

Chapter 1: Observations & Belief

Since you can't see the state directly, what can you work with? Observations — noisy signals that give you partial information. Each observation shifts your belief, a probability distribution over all possible states.

In the tiger problem, you start with a 50/50 belief: the tiger is equally likely behind either door. After listening and hearing a growl from the left, your belief shifts — say 85% left, 15% right. Listen again and hear left? Now maybe 97% left. Your belief is your internal model of reality.

Chapter 2: The POMDP Tuple

A POMDP is formally defined by seven components. If you already know MDPs, you'll recognize most of them — the new ingredients are the observation set O and the observation model Z.

Chapter 3: Belief Update

After the agent takes action a and receives observation o, it must update its belief using Bayes' rule. The new belief b'(s') is proportional to the likelihood of the observation times the prior belief propagated through the transition model.

Here η is a normalizing constant that makes the probabilities sum to 1. In words: (1) propagate your old belief through the transition model, (2) weight by how likely the observation is in each state, (3) normalize.

The Full Update with Transitions

The tiger problem has trivial transitions (listening doesn't change the state), so let's see the full formula with a 5-state example. A robot is in one of 5 rooms. It takes action "move-right" and observes a sensor reading z:

5-state belief update
# Prior belief: mostly in room 2
b     = [0.05, 0.10, 0.60, 0.20, 0.05]

# Transition: "move right" shifts probability one room right
# T[s, move-right, s'] — each row sums to 1.0
# Mostly moves right (0.8) with some stay (0.15) and overshoot (0.05)

# Step 1: propagate belief through T
# b_predicted[s'] = sum_s T[s, a, s'] * b[s]
b_pred = [0.01, 0.05, 0.12, 0.56, 0.26]  # shifted right

# Step 2: weight by observation likelihood P(z | s')
# Sensor says "room 3 signature" with noise
Z_z   = [0.02, 0.05, 0.10, 0.75, 0.08]  # high for room 3

# Element-wise multiply
raw   = [0.0002, 0.0025, 0.012, 0.42, 0.0208]

# Step 3: normalize (sum = 0.4555)
b'    = [0.000, 0.005, 0.026, 0.922, 0.046]
# Belief collapsed: 92% confident we're in room 3

Walk-through
# Prior belief
b = [0.50, 0.50]           # [tiger-left, tiger-right]

# Observation likelihoods: P(hear-left | state)
Z = [0.85, 0.15]           # high if tiger IS left

# Step 1: multiply prior × likelihood (element-wise)
unnorm = [0.85 * 0.50, 0.15 * 0.50]  # = [0.425, 0.075]

# Step 2: normalize so it sums to 1.0
eta = 0.425 + 0.075       # = 0.500
b' = [0.425/0.5, 0.075/0.5]  # = [0.85, 0.15]

# One observation: 50/50 → 85/15. Hear left again?
# [0.85*0.85, 0.15*0.15] → normalize → [0.97, 0.03]

One observation shifted your belief from total uncertainty to strong suspicion. Two consistent observations push it to 97% — that's the decision threshold.

python
import numpy as np

def belief_update(b, a, o, T, Z):
    # Step 1: Predict — propagate belief through transition model
    # b_pred[s'] = sum_s T[s, a, s'] * b[s]
    b_pred = T[:, a, :].T @ b  # shape (|S|,)

    # Step 2: Update — weight by observation likelihood
    # unnormalized[s'] = Z[s', a, o] * b_pred[s']
    likelihood = Z[:, a, o]   # shape (|S|,)
    unnorm = likelihood * b_pred

    # Step 3: Normalize
    eta = unnorm.sum()
    if eta == 0:
        return np.ones_like(b) / len(b)  # degenerate case
    return unnorm / eta

Chapter 4: The Value of Information

Here's what makes POMDPs fascinating: sometimes the best action is to do nothing useful except gather information. In the tiger problem, opening a door immediately gives you a 50/50 chance of hitting the tiger. But listening (even at a small cost) lets you build confidence before committing.

This is the value of information: an information-gathering action has negative immediate reward (it costs you −1 to listen) but positive expected future reward because it lets you make a better decision later.

Chapter 5: Why POMDPs Are Hard

Solving an MDP means finding the best action for each state. Solving a POMDP means finding the best action for each belief — and the belief space is a continuous simplex. Even with just 2 states, the belief is a number between 0 and 1 (infinite possibilities). With n states, it's an (n−1)-dimensional continuous space.

This is the curse of dimensionality: the belief space grows exponentially with the number of states. Exact solutions are computationally intractable for all but the tiniest problems. POMDP solving is PSPACE-complete — among the hardest problems in computer science.

The formal complexity: finite-horizon POMDP solving is PSPACE-complete. That puts it among the hardest problems in computer science — harder than NP-complete problems (which MDPs fall into at worst). The root cause is the belief MDP reduction: you can convert any POMDP into an MDP over belief states, but that MDP has a continuous, (|S|−1)-dimensional state space even when the original POMDP has a finite number of states.

Chapter 6: Point-Based Solvers

Since we can't solve for every belief point, what if we just pick a handful of representative belief points and solve for those? This is the core idea behind point-based value iteration (PBVI) and its successors like SARSOP.

The value function of a POMDP is piecewise linear and convex (PWLC) over the belief simplex. This means it can be represented as the maximum of a set of hyperplanes (called alpha-vectors). Each alpha-vector corresponds to an action and defines the value for a region of belief space.

Practical Approximation Ladder

Since exact solving is intractable for real problems, practitioners use a hierarchy of approximations, trading optimality for tractability:

Chapter 7: SHOWCASE — The Tiger Problem

Put it all together. You are the POMDP agent. Behind one door is a tiger (−100), behind the other is gold (+10). Listening costs −1 but gives you an 85%-accurate hint. After opening a door, the tiger is re-placed randomly and you play again.

The optimal strategy: listen until your belief is confident enough (roughly 97%), then open the safe door. Can you beat random guessing?

Chapter 8: POMDPs in the Real World

POMDPs are far more than a toy problem with tigers. They provide the mathematical framework for any situation where an agent must act under partial observability.

What practitioners actually use

Nobody solves a 10,000-state POMDP exactly. In practice, the belief-MDP reduction is used as a conceptual framework, and the actual computation is heavily approximated. Here's the realistic stack for a modern robot:

Practical POMDP pipeline
# 1. Belief tracking: run a particle filter
#    (1000 weighted samples approximate the belief)
particles = [sample_state() for _ in range(1000)]

# 2. Action selection: online planning from current belief
#    POMCP: Monte Carlo tree search over belief trees
#    Plans ~1 second ahead, not the full infinite horizon
action = pomcp_search(particles, depth=10)

# 3. Execute action, get observation
obs = env.step(action)

# 4. Update particles with new observation
particles = particle_filter_update(particles, action, obs)
# Repeat forever