25 Partially Observable MDPs

Core idea. In a fully observed MDP, the state \(S_t\) is available to the decision maker. In a partially observable Markov decision process, the state is hidden and the agent observes only a noisy signal \(O_t\). The central mathematical idea is that the posterior distribution

\[ b_t(s)=P(S_t=s \mid H_t) \]

is a sufficient statistic for optimal decision making. This posterior is called the belief state. A POMDP becomes a fully observed MDP on the belief simplex, but the new state space is continuous even when the original hidden state space is finite.

25.1 Learning goals

After reading this chapter, students should be able to:

define a finite partially observable Markov decision process precisely;
distinguish hidden states, observations, histories, beliefs, and policies;
derive the belief update from Bayes’ rule;
explain why the belief state is a sufficient statistic for control;
convert a finite POMDP into a fully observed belief-state MDP;
write the Bellman expectation and Bellman optimality equations on the belief space;
explain why finite-horizon POMDP value functions are piecewise-linear and convex;
implement exact belief filtering in a finite example;
implement approximate planning on a discretized belief grid;
explain the role of particle filters in large POMDPs;
identify statistical issues in estimating transition and observation models;
use AI tools to audit belief updates, indexing conventions, and modeling assumptions.

25.2 22.1 Why partial observability?

The MDP assumption says that the agent observes a state variable \(S_t\) that is rich enough to make the future conditionally independent of the past:

\[ P(S_{t+1}=s' \mid S_0,A_0,\ldots,S_t,A_t) = P(S_{t+1}=s' \mid S_t,A_t). \]

This is powerful, but often unrealistic. In many sequential decision problems, the true state is latent:

Application	Hidden state	Observation
Medical treatment	disease stage	tests, symptoms, imaging
Robot navigation	physical location	camera, lidar, sonar
Education technology	student mastery	quiz responses
Finance	market regime	prices, volumes, news
Recommendation systems	user intent	clicks, dwell time, ratings
Maintenance	machine health	sensor readings

Partial observability is not just a nuisance. It changes the mathematical structure of the problem. The agent cannot choose actions as a function of \(S_t\) because \(S_t\) is not observed. It must choose actions using the information history available to it.

A typical history is

\[ H_t=(O_0,A_0,R_1,O_1,A_1,R_2,\ldots,A_{t-1},R_t,O_t). \]

A general policy may depend on this entire history:

\[ \pi_t(a \mid H_t)=P(A_t=a \mid H_t). \]

The key question is whether the full history can be compressed into a smaller object. For finite POMDPs with known models, the answer is yes: the correct compression is the posterior belief distribution over hidden states.

The belief state is the replacement for the observed state. It is not an estimate such as a single most likely state. It is the full conditional distribution of the hidden state given the information available to the agent.

The interactive figure illustrates how repeated noisy observations move the posterior belief. When observations are informative, the belief becomes concentrated. When observations are weak, the belief moves slowly.

25.3 22.2 Definition of a finite POMDP

A finite discounted POMDP is specified by

\[ (S,A,O,P,Z,r,\gamma,b_0). \]

Here:

\(S=\{1,\ldots,n\}\) is a finite hidden state space;
\(A\) is a finite action space;
\(O=\{1,\ldots,m\}\) is a finite observation space;
\(P(s' \mid s,a)\) is the controlled transition probability;
\(Z(o \mid s',a)\) is the observation probability after action \(a\) and transition to \(s'\);
\(r(s,a)\) is the expected one-step reward;
\(0<\gamma<1\) is the discount factor;
\(b_0\) is the initial distribution over hidden states.

The process evolves as follows. At time \(t\), the hidden state is \(S_t=s\). The agent chooses action \(A_t=a\). The environment samples the next hidden state from

\[ S_{t+1}\sim P(\cdot \mid s,a), \]

then samples an observation from

\[ O_{t+1}\sim Z(\cdot \mid S_{t+1},a), \]

and produces reward with conditional expectation

\[ E[R_{t+1} \mid S_t=s,A_t=a]=r(s,a). \]

Some books use the convention \(Z(o \mid s,a)\), where the observation depends on the current state before the transition. Others use \(Z(o \mid s',a)\), where the observation depends on the next state after the transition. This chapter uses the second convention because it aligns naturally with filtering after the transition.

A POMDP is an MDP whose state is hidden. The hidden process is Markov, but the observed process usually is not Markov. The agent must maintain a posterior distribution over hidden states.

25.4 22.3 Belief states

The belief state at time \(t\) is the probability vector

\[ b_t(s)=P(S_t=s \mid H_t), \qquad s\in S. \]

Thus \(b_t\) lies in the probability simplex

\[ \Delta(S)=\left\{b\in R^n: b(s)\ge 0,\ \sum_{s\in S}b(s)=1\right\}. \]

For two hidden states, the belief simplex is the interval \([0,1]\). For three hidden states, it is a triangle. For \(n\) hidden states, it is an \((n-1)\)-dimensional simplex.

The belief is not merely a statistic for state estimation; it is the state variable for planning. A belief policy has the form

\[ \pi(a \mid b)=P(A_t=a \mid b_t=b). \]

The main theorem of POMDP theory says that, under standard finite-model assumptions, there exists an optimal policy that depends on the history only through the current belief.

Belief-state sufficiency. For a finite discounted POMDP with known transition and observation models, the belief state \(b_t=P(S_t\in\cdot \mid H_t)\) is a sufficient statistic for optimal control. That is, the optimal expected future return conditioned on the full history \(H_t\) is a function of \(b_t\) alone.

Reason. Given \(b_t\) and action \(a\), the conditional distribution of the next hidden state, next observation, reward expectation, and next belief is completely determined. Therefore the future decision problem depends on the history only through \(b_t\).

25.5 22.4 Bayesian filtering in a POMDP

Suppose the current belief is \(b\), the agent chooses action \(a\), and the next observation is \(o\). The belief update has two stages.

First, predict the next hidden-state distribution:

\[ \bar b(s')= \sum_{s\in S}P(s' \mid s,a)b(s). \]

Second, condition on the observed signal:

\[ b^+(s')= P(S_{t+1}=s' \mid H_t,A_t=a,O_{t+1}=o). \]

By Bayes’ rule,

\[ b^+(s') = \frac{Z(o \mid s',a)\bar b(s')} {\sum_{x\in S}Z(o \mid x,a)\bar b(x)}. \]

Substituting the prediction step gives the standard belief update

\[ \tau(b,a,o)(s') = \frac{ Z(o \mid s',a) \sum_{s\in S}P(s' \mid s,a)b(s) }{ \sum_{x\in S} Z(o \mid x,a) \sum_{s\in S}P(x \mid s,a)b(s) }. \]

The denominator is the probability of observing \(o\) given belief \(b\) and action \(a\):

\[ p(o \mid b,a) = \sum_{x\in S} Z(o \mid x,a) \sum_{s\in S}P(x \mid s,a)b(s). \]

This denominator is also the normalizing constant that makes the posterior probabilities sum to one.

Belief filtering algorithm

Input: belief \(b\), action \(a\), observation \(o\).

Prediction: \[ \bar b(s')=\sum_s P(s' \mid s,a)b(s). \]
Observation likelihood: \[ \ell(s')=Z(o \mid s',a). \]
Correction: \[ \tilde b(s')=\ell(s')\bar b(s'). \]
Normalization: \[ b^+(s')=\frac{\tilde b(s')}{\sum_x \tilde b(x)}. \]

25.5.1 Python example: exact belief update

import numpy as np

# Hidden states: 0 = healthy, 1 = failed
# Observations: 0 = quiet, 1 = alarm
# Actions: 0 = wait, 1 = inspect

P = np.zeros((2, 2, 2))
# P[a, s, s']
P[0] = np.array([
    [0.92, 0.08],
    [0.15, 0.85]
])
P[1] = np.array([
    [0.98, 0.02],
    [0.75, 0.25]
])

Z = np.zeros((2, 2, 2))
# Z[a, s', o]
Z[0] = np.array([
    [0.85, 0.15],
    [0.25, 0.75]
])
Z[1] = np.array([
    [0.95, 0.05],
    [0.05, 0.95]
])

def belief_update(b, action, observation):
    predicted = b @ P[action]
    likelihood = Z[action, :, observation]
    unnormalized = likelihood * predicted
    normalizer = unnormalized.sum()
    return unnormalized / normalizer, predicted, normalizer

b = np.array([0.80, 0.20])
for obs in [1, 1, 0, 1]:
    b, predicted, prob_obs = belief_update(b, action=0, observation=obs)
    print("observation", obs, "predicted", np.round(predicted, 3),
          "posterior", np.round(b, 3), "p(obs)", round(prob_obs, 3))

observation 1 predicted [0.766 0.234] posterior [0.396 0.604] p(obs) 0.29
observation 1 predicted [0.455 0.545] posterior [0.143 0.857] p(obs) 0.477
observation 0 predicted [0.26 0.74] posterior [0.544 0.456] p(obs) 0.406
observation 1 predicted [0.569 0.431] posterior [0.209 0.791] p(obs) 0.408

The posterior changes for two reasons: the hidden state evolves, and the observation provides information about the new hidden state. A common error is to condition on the observation before applying the transition. Under the convention used here, the transition prediction comes first.

25.6 22.5 Observation quality and posterior uncertainty

Observation probabilities determine how quickly beliefs become concentrated. For a two-state model, suppose observation \(o=1\) is more likely under state \(1\) than under state \(0\):

\[ Z(1 \mid 1,a)>Z(1 \mid 0,a). \]

Then observing \(o=1\) increases the posterior probability of state \(1\), but the size of the increase depends on the likelihood ratio

\[ \frac{Z(1 \mid 1,a)}{Z(1 \mid 0,a)}. \]

The posterior odds form is especially clean. For two hidden states,

\[ \frac{b^+(1)}{b^+(0)} = \frac{Z(o \mid 1,a)}{Z(o \mid 0,a)} \frac{\bar b(1)}{\bar b(0)}. \]

Thus each observation multiplies the prior odds by a likelihood ratio. This is the same statistical mechanism underlying Bayesian classification and hidden Markov model filtering.

25.7 22.6 The belief MDP

The belief-state reduction converts a POMDP into a fully observed MDP whose state space is the simplex \(\Delta(S)\). The belief-MDP ingredients are:

state: \(b\in\Delta(S)\);
action: \(a\in A\);
immediate reward: \[ r(b,a)=\sum_{s\in S}b(s)r(s,a); \]
next belief: \(b^+=\tau(b,a,o)\) after observing \(o\);
observation probability: \[ p(o \mid b,a)=\sum_{s'}Z(o \mid s',a)\sum_sP(s' \mid s,a)b(s). \]

The transition in the belief MDP is not indexed directly by next hidden state. It is indexed by possible observations. After action \(a\), the next belief is random because the next observation is random.

For a fixed belief policy \(\pi(a \mid b)\), the Bellman expectation equation is

\[ V^{\pi}(b) = \sum_a\pi(a \mid b) \left[ r(b,a) + \gamma \sum_o p(o \mid b,a)V^{\pi}(\tau(b,a,o)) \right]. \]

The Bellman optimality equation is

\[ V^*(b) = \max_a \left[ r(b,a) + \gamma \sum_o p(o \mid b,a)V^*(\tau(b,a,o)) \right]. \]

This equation looks like the ordinary MDP Bellman equation, but it is defined on a continuous state space. Even a two-hidden-state POMDP has a continuum of possible beliefs.

The price of turning a POMDP into a fully observed MDP is dimensionality. If the hidden state space has \(n\) states, then the belief state has \(n-1\) degrees of freedom. Exact planning is often expensive because value functions live on a continuous simplex.

25.8 22.7 A small two-state maintenance POMDP

Consider a machine that is either healthy or failed. The state is not directly observed. At each time step, the agent chooses either to wait or inspect. Waiting is cheap but risky; inspection is costly but tends to repair or reveal the problem.

Let the hidden states be

\[ S=\{H,F\}, \]

where \(H\) means healthy and \(F\) means failed. The belief is determined by one number

\[ p=P(S_t=F \mid H_t). \]

A reasonable reward model is

\[ r(H,\text{wait})=1, \qquad r(F,\text{wait})=-4, \]

and

\[ r(H,\text{inspect})=-1, \qquad r(F,\text{inspect})=-1. \]

The expected reward for waiting is

\[ r(p,\text{wait})=(1-p)(1)+p(-4)=1-5p, \]

whereas the expected reward for inspecting is \(-1\). The immediate-reward comparison alone favors waiting when

\[ 1-5p>-1, \]

or \(p<0.4\). However, optimal POMDP planning is not based only on immediate reward. Actions also affect the future belief. Inspection may be valuable because it changes the transition probabilities and yields more informative observations.

25.8.1 Python example: grid-based value iteration on beliefs

The following code discretizes the belief interval \([0,1]\) and performs approximate value iteration. This is not the most efficient POMDP algorithm, but it is mathematically transparent for students.

import numpy as np

# States: 0 = healthy, 1 = failed. Belief p = P(failed).
# Actions: 0 = wait, 1 = inspect.
P = np.zeros((2, 2, 2))
P[0] = np.array([[0.92, 0.08], [0.10, 0.90]])
P[1] = np.array([[0.98, 0.02], [0.80, 0.20]])

Z = np.zeros((2, 2, 2))
Z[0] = np.array([[0.80, 0.20], [0.30, 0.70]])
Z[1] = np.array([[0.95, 0.05], [0.05, 0.95]])

R = np.array([
    [1.0, -1.0],   # rewards in healthy state
    [-4.0, -1.0]   # rewards in failed state
])

gamma = 0.95
grid = np.linspace(0.0, 1.0, 201)

def interp_value(V, p):
    return np.interp(p, grid, V)

def update_p(p_failed, action, obs):
    b = np.array([1.0 - p_failed, p_failed])
    pred = b @ P[action]
    un = Z[action, :, obs] * pred
    post = un / un.sum()
    return post[1], un.sum()

def immediate_reward(p_failed, action):
    b = np.array([1.0 - p_failed, p_failed])
    return b @ R[:, action]

V = np.zeros_like(grid)
policy = np.zeros_like(grid, dtype=int)

for it in range(300):
    V_new = np.zeros_like(V)
    new_policy = np.zeros_like(policy)
    for i, p in enumerate(grid):
        q_values = []
        for a in [0, 1]:
            future = 0.0
            for o in [0, 1]:
                p_next, prob_o = update_p(p, a, o)
                future += prob_o * interp_value(V, p_next)
            q_values.append(immediate_reward(p, a) + gamma * future)
        V_new[i] = max(q_values)
        new_policy[i] = int(np.argmax(q_values))
    if np.max(np.abs(V_new - V)) < 1e-8:
        break
    V = V_new
    policy = new_policy

print("iterations:", it + 1)
print("inspect region approximately starts near p =", grid[np.argmax(policy == 1)])
print("value at p=0.1:", round(interp_value(V, 0.1), 3))
print("value at p=0.8:", round(interp_value(V, 0.8), 3))

iterations: 300
inspect region approximately starts near p = 0.22
value at p=0.1: 8.257
value at p=0.8: 7.158

The output shows a threshold-like structure: when the posterior probability of failure is small, the agent tends to wait; when the posterior probability is large, the agent tends to inspect. This kind of threshold behavior is common in partially observed maintenance and medical screening models.

25.9 22.8 Finite-horizon value functions and alpha-vectors

Finite-horizon POMDPs have an elegant geometric structure. Suppose there are \(T\) steps remaining. The value function is a function of the belief \(b\):

\[ V_T(b)=\max_{\pi}E_{\pi}\left[\sum_{t=0}^{T-1}\gamma^t R_{t+1}\mid b_0=b\right]. \]

For a fixed conditional plan, the expected return is linear in \(b\) because the only uncertainty about the initial hidden state is averaged under \(b\). Therefore a finite collection of conditional plans gives a maximum of linear functions:

\[ V_T(b)=\max_{\alpha\in\Gamma_T} b^T\alpha. \]

Here each vector \(\alpha\in R^{|S|}\) is called an alpha-vector. It represents the value of a particular conditional plan as a function of the initial hidden-state distribution.

Piecewise-linear convex finite-horizon value function. For a finite-horizon discounted POMDP with finite states, actions, and observations, the optimal value function on the belief simplex is piecewise-linear and convex:

\[ V_T(b)=\max_{\alpha\in\Gamma_T} b^T\alpha. \]

The set \(\Gamma_T\) is finite for each finite horizon \(T\), though it can grow very quickly with \(T\).

For horizon \(1\),

\[ V_1(b)=\max_a\sum_s b(s)r(s,a), \]

so the alpha-vectors are simply

\[ \alpha_a(s)=r(s,a). \]

For longer horizons, each alpha-vector encodes an action now and a continuation plan for each possible observation. This is why the number of possible vectors grows rapidly.

25.10 22.9 Conditional plans and alpha-vector backup

Let \(\Gamma_t\) be a set of alpha-vectors for \(t\) remaining steps. To construct candidates for \(t+1\) remaining steps, choose:

a current action \(a\);
for each possible observation \(o\), a continuation vector \(\alpha_o\in\Gamma_t\).

The resulting vector has components

\[ \alpha(s) = r(s,a) + \gamma \sum_{s'}P(s' \mid s,a) \sum_o Z(o \mid s',a)\alpha_o(s'). \]

This backup is the POMDP analogue of Bellman backup. The difference is that the continuation plan can depend on the future observation.

The candidate set can be large. If there are \(|A|\) actions, \(|O|\) observations, and \(N_t\) alpha-vectors at horizon \(t\), a naive backup can generate

\[ |A|N_t^{|O|} \]

candidate vectors. Many are dominated and can be pruned.

Finite-horizon alpha-vector value iteration

Initialize \(\Gamma_0=\{0\}\).
For each horizon \(t=0,1,\ldots,T-1\):
- for each action \(a\);
- for each assignment of one old alpha-vector to each observation;
- construct a new alpha-vector using the backup equation;
- remove dominated alpha-vectors.
Evaluate by \(V_T(b)=\max_{\alpha\in\Gamma_T}b^T\alpha\).

25.10.1 Python example: one-step alpha-vector construction

import itertools
import numpy as np

S = 2
A = 2
O = 2
gamma = 0.9

P = np.zeros((A, S, S))
P[0] = np.array([[0.90, 0.10], [0.20, 0.80]])
P[1] = np.array([[0.95, 0.05], [0.70, 0.30]])

Z = np.zeros((A, S, O))
Z[0] = np.array([[0.80, 0.20], [0.30, 0.70]])
Z[1] = np.array([[0.95, 0.05], [0.05, 0.95]])

R = np.array([[1.0, -1.0], [-3.0, -1.0]])

Gamma = [np.zeros(S)]
for horizon in range(1, 4):
    new_Gamma = []
    for a in range(A):
        for choices in itertools.product(range(len(Gamma)), repeat=O):
            alpha = R[:, a].copy()
            for s in range(S):
                continuation = 0.0
                for sp in range(S):
                    obs_sum = 0.0
                    for o in range(O):
                        obs_sum += Z[a, sp, o] * Gamma[choices[o]][sp]
                    continuation += P[a, s, sp] * obs_sum
                alpha[s] += gamma * continuation
            new_Gamma.append(alpha)
    # Simple duplicate removal only. Full dominance pruning is more involved.
    unique = []
    for alpha in new_Gamma:
        if not any(np.allclose(alpha, beta) for beta in unique):
            unique.append(alpha)
    Gamma = unique
    print("horizon", horizon, "number of candidate vectors", len(Gamma))
    for alpha in Gamma[:5]:
        print("  ", np.round(alpha, 3))
    if len(Gamma) > 5:
        print("  ...")

horizon 1 number of candidate vectors 2
   [ 1. -3.]
   [-1. -1.]
horizon 2 number of candidate vectors 8
   [ 1.54 -4.98]
   [ 1.342 -4.044]
   [ 0.298 -4.836]
   [ 0.1 -3.9]
   [-0.28 -1.18]
  ...
horizon 3 number of candidate vectors 128
   [ 1.799 -6.308]
   [ 1.826 -5.844]
   [ 1.607 -6.281]
   [ 1.634 -5.816]
   [ 1.744 -4.459]
  ...

This example intentionally uses only duplicate removal, not full dominance pruning. In practical exact POMDP solvers, pruning dominated alpha-vectors is essential.

25.11 22.10 Relation to hidden Markov models

A hidden Markov model is a POMDP without actions and rewards. In an HMM, one performs inference about a latent Markov chain using observations. In a POMDP, one performs both inference and control. The agent’s actions influence future hidden states and future observations.

Model	Hidden state?	Actions?	Rewards?	Main task
Markov chain	no	no	no	transition modeling
HMM	yes	no	no	filtering and smoothing
MDP	no	yes	yes	control with observed state
POMDP	yes	yes	yes	control under uncertainty

This connection is useful for MS Statistics students because the belief update is exactly a Bayesian filtering recursion. The main new ingredient in POMDPs is that the action affects both the latent dynamics and the future information structure.

25.12 22.11 Approximate methods

Exact POMDP planning is computationally difficult. Approximate methods are therefore central.

25.12.1 Belief-grid approximation

The simplest approximation is to choose a finite grid of beliefs and solve an approximate MDP on that grid. This is easy to teach but scales poorly with the dimension of the belief simplex.

25.12.2 Point-based value iteration

Point-based methods focus computation on a set of reachable beliefs rather than the entire simplex. The idea is that, from a given initial belief and reasonable policies, only a subset of beliefs is likely to occur.

25.12.3 Recurrent policies

Deep RL often avoids explicit Bayesian filtering by training a recurrent neural network policy:

\[ h_t=f_\theta(h_{t-1},O_t,A_{t-1},R_t), \qquad A_t\sim \pi_\theta(\cdot \mid h_t). \]

The hidden vector \(h_t\) is a learned memory state. It may approximate a belief state, but it is not generally an exact posterior distribution.

25.12.4 Particle filtering

When the hidden state space is large or continuous, the belief distribution may be approximated by particles:

\[ b_t \approx \sum_{i=1}^N w_t^{(i)}\delta_{s_t^{(i)}}. \]

Particles are propagated through the transition model, weighted by the observation likelihood, and resampled to avoid degeneracy.

25.13 22.12 Statistical issues

POMDPs combine reinforcement learning with statistical inference. Several issues are especially important.

25.13.1 Model estimation

If transitions and observations are unknown, the agent must estimate both

\[ P(s' \mid s,a) \]

and

\[ Z(o \mid s',a). \]

But states are hidden, so this is not ordinary supervised estimation. The likelihood contains latent variables, and estimation resembles hidden Markov model learning or expectation-maximization.

25.13.2 Identifiability

Different latent-state models can produce the same distribution over observation histories. Therefore the hidden state representation may not be identifiable without additional assumptions. For control, perfect identification of latent states is not always necessary; what matters is whether the learned representation is sufficient for good decisions.

25.13.3 Exploration and information gathering

In fully observed MDPs, exploration means trying actions to learn rewards and transitions. In POMDPs, actions can also be chosen to reveal information. Such actions may have low immediate reward but high value because they reduce posterior uncertainty.

25.13.4 Model misspecification

A common modeling mistake is to choose a state variable that is too small. If the belief update is based on an incorrect latent-state model, the resulting belief may not be sufficient. This produces biased planning and misleading uncertainty estimates.

AI-assisted modeling prompt. Give an AI tool a proposed POMDP model for a medical screening, machine-maintenance, or student-learning problem. Ask it to identify: hidden states, observations, actions, rewards, transition assumptions, observation assumptions, and possible identifiability problems. Then check whether the proposed belief update uses the correct conditioning order.

25.14 22.13 Implementation checklist

When implementing a finite POMDP, check the following points carefully.

Every row of each transition matrix must sum to one: \[ \sum_{s'}P(s' \mid s,a)=1. \]
Every row of each observation matrix must sum to one: \[ \sum_o Z(o \mid s',a)=1. \]
Beliefs must be nonnegative and normalized: \[ \sum_s b(s)=1. \]
The prediction step must match the chosen observation convention.
The observation probability \(p(o \mid b,a)\) must be computed before normalizing the posterior.
Interpolation on a belief grid can introduce approximation error.
For continuous or large hidden spaces, particle degeneracy must be monitored.

25.14.1 Python example: automated consistency checks

import numpy as np

def check_pomdp(P, Z, b, tol=1e-10):
    errors = []
    if np.any(P < -tol):
        errors.append("transition probabilities contain negative entries")
    if np.any(Z < -tol):
        errors.append("observation probabilities contain negative entries")
    if not np.allclose(P.sum(axis=2), 1.0, atol=tol):
        errors.append("some transition rows do not sum to one")
    if not np.allclose(Z.sum(axis=2), 1.0, atol=tol):
        errors.append("some observation rows do not sum to one")
    if np.any(b < -tol) or not np.isclose(b.sum(), 1.0, atol=tol):
        errors.append("belief is not a probability vector")
    return errors

P_test = np.array([
    [[0.9, 0.1], [0.2, 0.8]],
    [[0.7, 0.3], [0.6, 0.4]]
])
Z_test = np.array([
    [[0.8, 0.2], [0.3, 0.7]],
    [[0.9, 0.1], [0.1, 0.9]]
])
b_test = np.array([0.4, 0.6])

print(check_pomdp(P_test, Z_test, b_test))

[]

25.15 22.14 AI components for this chapter

AI derivation audit. Ask an AI tool to derive the belief update formula. Then verify whether it explicitly distinguishes the prediction step \(\bar b\) from the correction step \(b^+\). Many incorrect derivations skip the transition step or normalize the wrong quantity.

AI code review. Provide your belief-update function to an AI tool and ask it to check array shapes. Require it to specify whether your convention is \(Z(o\mid s,a)\) or \(Z(o\mid s',a)\). Do not accept an answer that does not state the convention.

AI modeling critique. For an applied example, ask an AI tool: “Which variables should be hidden states, which should be observations, and which should be actions?” Then ask it to give two alternative latent-state models and explain how they might produce different policies.

25.16 22.15 Summary

A POMDP is a sequential decision model in which the true state is hidden and the agent receives noisy observations. The full observable history can be compressed into the posterior belief distribution

\[ b_t(s)=P(S_t=s \mid H_t). \]

The belief is updated by Bayesian filtering: transition prediction followed by observation correction. This converts the POMDP into a fully observed MDP on the belief simplex, with Bellman optimality equation

\[ V^*(b) = \max_a \left[ r(b,a) + \gamma \sum_o p(o \mid b,a)V^*(\tau(b,a,o)) \right]. \]

The mathematical advantage of this transformation is conceptual clarity: the POMDP is an MDP in belief space. The computational disadvantage is that the belief space is continuous and high-dimensional. Finite-horizon value functions are piecewise-linear and convex, but exact alpha-vector methods can grow rapidly. Practical methods often rely on belief grids, point-based methods, recurrent policies, or particle filters.

25.17 Exercises

25.17.1 Conceptual exercises

Explain why the observed process \(O_t\) is usually not Markov, even when the hidden state \(S_t\) is Markov.
Give an example in which the most likely hidden state is not enough information for optimal decision making.
Explain the difference between a belief state and a recurrent neural network hidden state.
In a maintenance problem, why might an inspection action be valuable even if it has negative immediate reward?
Explain why partial observability creates an information-gathering aspect of control.

25.17.2 Mathematical exercises

Derive the belief update formula using Bayes’ rule under the convention \(Z(o\mid s',a)\).
Prove that \(p(o\mid b,a)\) is the normalizing constant in the belief update.
Show that \(r(b,a)=\sum_sb(s)r(s,a)\) is linear in \(b\).
Derive the Bellman optimality equation for the belief MDP.
Prove that \(V_1(b)=\max_a b^Tr_a\) is piecewise-linear and convex.
Prove by induction that the finite-horizon POMDP value function is piecewise-linear and convex.
For a two-state POMDP, express the belief update as a scalar map on \(p=P(S_t=1\mid H_t)\).
Show how the posterior odds update by multiplication with the likelihood ratio.

25.17.3 Computational exercises

Implement the belief update for a three-state POMDP with two observations.
Simulate a hidden Markov chain and compare the true hidden states with the posterior beliefs.
Implement grid-based value iteration for a two-state POMDP and plot the resulting policy threshold.
Change the observation accuracy in the maintenance example and study how the inspection threshold changes.
Implement finite-horizon alpha-vector backups for horizon \(T=3\) and remove dominated vectors by checking a dense belief grid.
Implement a simple particle filter for a continuous hidden state and compare it with exact filtering in a discretized model.
Compare a belief-state policy with a policy based only on the latest observation.

25.17.4 AI-assisted exercises

Ask an AI tool to propose a POMDP model for one application. Then identify at least three assumptions that would need empirical justification.
Ask an AI tool to derive the belief update. Mark each line as prediction, likelihood evaluation, correction, or normalization.
Ask an AI tool to review your POMDP code for row-stochasticity and normalization errors.
Ask an AI tool to explain why finite-horizon POMDP value functions are piecewise-linear and convex. Then write your own proof using induction.
Ask an AI tool to compare POMDPs with HMMs and MDPs. Correct any statement that confuses hidden states with observations.

25.18 Notes for instructors

For MA Applied Math students, emphasize the belief-state reduction, Bellman equations on continuous state spaces, and the geometry of piecewise-linear convex value functions. For MS Statistics students, emphasize Bayesian filtering, likelihood ratios, posterior distributions, identifiability, and model misspecification. A good lecture sequence is:

hidden state and noisy observation motivation;
derivation of the belief update;
belief-state MDP and Bellman equation;
two-state maintenance example;
finite-horizon alpha-vector geometry;
statistical and computational limitations.