Imperfect State Information and Partially Observed Markov Decision Processes

Intuition Beginner

The earlier decision-under-chance unit assumed you always know exactly which situation you are in before you choose. Often you do not. A doctor cannot see the disease, only the test results; a robot does not know its exact location, only what its noisy sensors report; a maintenance crew cannot open every machine, only watch a warning light that is sometimes wrong. You act on clues, not on certainty. This unit is about deciding well when the true situation is hidden and all you ever receive are imperfect readings of it.

The trick is to stop pretending you have one definite situation and instead carry a belief: a list of how likely each possible hidden situation is right now, given everything you have seen and done so far. The belief is a set of fractions that add to one, like "70 percent chance the machine is fine, 30 percent chance it is failing." Each time you act and then receive a new reading, you revise the belief with the everyday rule for updating chances in light of evidence: situations that fit the new reading get more weight, situations that do not fit get less.

The reason this matters is a small miracle of bookkeeping. You might think you must remember the entire history of readings and actions to choose well. You do not. The current belief alone holds everything from the past that could affect the future. So the belief is your new "situation," and the hidden-state problem turns into an ordinary known-situation problem, just with belief lists playing the role of states.

Once the problem is rephrased this way, the same value-and-policy machinery from the known-state case applies, only now the value is a function of a belief rather than of a plain state, and the best action depends on which belief you currently hold.

Visual Beginner

Picture a strip representing all possible beliefs about a machine that is either fine or failing. The far left of the strip means "certainly failing," the far right means "certainly fine," and the middle means "fifty-fifty." Your current belief is a single dot somewhere on the strip. Each action you take, followed by the reading you then get, slides the dot to a new spot: a reassuring reading pushes it right, an alarming reading pushes it left, and how far it slides depends on how trustworthy the reading is.

Above the strip, draw the value as a height over each belief. For these hidden-state problems that height is not a smooth bump but a creased shape made of straight pieces — the lowest of several straight lines, one line for each good plan you might commit to. The crease points are beliefs where the best plan switches. Scoring an action means averaging the value over the places your dot might slide to next.

ingredient	what it is	everyday picture
hidden state	the true situation you cannot see	is the machine actually failing
observation	the reading you do get	the warning light's color
belief	chances over hidden states	"70% fine, 30% failing"
belief update	revising chances after a reading	trusting an alarm a bit, not fully

Worked example Beginner

A machine is secretly good or bad. You cannot see which. Right now your belief is "good with chance $0.8$, bad with chance $0.2$." You take a reading. The reading is an honest-ish light: when the machine is good it flashes green with chance $0.9$ (and red with chance $0.1$); when the machine is bad it flashes green with chance $0.3$ (and red with chance $0.7$). Suppose the light flashes red. What should your updated belief be?

We update with the rule for revising chances after evidence. First, weight each hidden state by how it explains a red light. Good explains red with chance $0.1$, and good had belief $0.8$, so its weighted score is $0.8\times 0.1=0.08$. Bad explains red with chance $0.7$, and bad had belief $0.2$, so its weighted score is $0.2\times 0.7=0.14$.

These two scores, $0.08$ and $0.14$, are not yet a belief because they do not add to one; they add to $0.22$. Divide each by the total to rescale them so they sum to one. New chance of good: $0.08/0.22=0.36$. New chance of bad: $0.14/0.22=0.64$.

So a single red flash flipped you from "probably good" ($0.8$) to "probably bad" ($0.64$). What this tells us: the belief is the whole memory you need, and one reading can move it a lot when that reading is much more typical of one hidden state than the other. The number you divided by, $0.22$, is just the overall chance of seeing red in the first place, and it is exactly the scaling that keeps the revised chances adding to one.

Check your understanding Beginner

Formal definition Intermediate+

A partially observed Markov decision process (POMDP) is a tuple $(S,A,Z,P,O,g,\alpha )$: a hidden state space $S$, an action space $A$ (with admissible sets $A(s)$ suppressed when $A(s)=A$), an observation space $Z$, a transition kernel $P(s^{\prime }\mid s,a)$ — the controlled-Markov law of 37.05.01, indexed by the action — an observation kernel $O(z\mid s^{\prime },a)$ giving the law of the measurement received after landing in $s^{\prime }$ under action $a$, a bounded one-step cost $g(s,a)$ with $|g|\le M$, and (in the infinite-horizon case) a discount $\alpha \in [0,1)$. The controller never sees $s_t$; at stage $t$ its information vector is $I_t=(z_0,\dots ,z_t,u_0,\dots ,u_{t-1})$, the full record of observations and past actions. We take $S$ and $Z$ finite in the master-tier constructions; the abstract reduction holds for Polish $S$ with measurable kernels.

A policy maps each information vector to an admissible action, $u_t={\pi }_t(I_t)$, and the objective is the expected (discounted) cost as in the fully observed case 44.08.03, now with the expectation also over the unseen states and the observation noise. Writing the dynamic-programming recursion directly over $I_t$ is correct but the domain grows with $t$. The belief state (information state) is the conditional law of the hidden state given the record,

$$b_t(s)=\mathbb{P}(s_t=s\mid I_t),b_t\in \Delta (S)=\{b:S\to [0,1]|{\sum }_{s}b(s)=1\},$$

a point of the probability simplex $\Delta (S)$ recorded in _meta/NOTATION.md. A statistic $S_t(I_t)$ is sufficient for control if an optimal policy can be written as a function of $S_t$ alone; the belief is the canonical such statistic.

The belief evolves deterministically once the action and the next observation are realized, by the belief update (Bayes filter) $b_{t+1}=\tau (b_t,u_t,z_{t+1})$ with

$$\tau (b,a,z)(s^{\prime })=\frac{O(z\mid s^{\prime },a){\sum }_{s}P(s^{\prime }\mid s,a)b(s)}{\sigma (b,a,z)},\sigma (b,a,z)=\sum _{s^{\prime }}O(z\mid s^{\prime },a)\sum _{s}P(s^{\prime }\mid s,a)b(s),$$

where $\sigma (b,a,z)=\mathbb{P}(z_{t+1}=z\mid b,a)$ is the predictive probability of the observation and the normalizer of Bayes' rule. The numerator first predicts (${\sum }_{s}P(s^{\prime }\mid s,a)b(s)$, a time update) and then corrects by the observation likelihood $O(z\mid s^{\prime },a)$ (a measurement update). The belief MDP is the fully observed MDP on state space $\Delta (S)$ with action set $A$, transition law $b\mapsto \tau (b,a,z)$ occurring with probability $\sigma (b,a,z)$, and cost $\bar{g}(b,a)={\sum }_{s}b(s)g(s,a)$. The symbols $b$ (belief), $\Delta (S)$ (simplex), $\tau$ (belief update), $\sigma$ (observation normalizer), $O$ (observation kernel), and $I_t$ (information vector) are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

• "The hidden state is Markov given the observations, so I can run an ordinary MDP on it." The hidden state is not observed, so there is no state to run an MDP on. What is Markov — and observed, since the controller computes it — is the belief $b_t$: $b_{t+1}$ depends on $b_t$, $u_t$, $z_{t+1}$ only. The belief, not the hidden state, is the legitimate MDP state.

• "The belief update is stochastic, so the belief MDP has a random transition I cannot write down." The map $\tau (b,a,z)$ is a deterministic function of its arguments. The only randomness is which observation $z$ arrives, and that has the explicit law $\sigma (b,a,z)$. The belief MDP is an ordinary MDP whose transitions land on the finitely (in finite-$Z$ models) many beliefs $\{\tau (b,a,z){\}}_z$ with known probabilities.

• "A POMDP needs memory or randomized policies because the state is hidden." Memory is needed, but it is entirely captured by the belief; conditioned on $b_t$, no further history helps, and a deterministic belief-feedback policy is optimal. Randomization buys nothing for the unconstrained discounted criterion, exactly as in the fully observed case 44.08.03; it returns only for constrained POMDPs.

• "The value function over beliefs is some smooth surface on the simplex." For a finite-state finite-horizon POMDP it is piecewise linear and convex, the lower envelope (cost convention) of finitely many affine functions $b\mapsto ⟨b,\alpha ⟩$. The creases, not smoothness, are the generic feature; smoothness would be the exception.

Key theorem with proof Intermediate+

The signature result is the sufficient-statistic reduction: the belief is a sufficient statistic, and the POMDP collapses to a fully observed MDP on the belief simplex with a belief-state Bellman recursion. This is what makes the apparatus of 44.08.03 applicable to the hidden-state case; everything downstream (piecewise-linearity, $\alpha$-vectors, separation) is read off this reduction.

Theorem (sufficient-statistic reduction and the belief-state Bellman recursion). For a POMDP $(S,A,Z,P,O,g,\alpha )$ with $|g|\le M$, the belief $b_t=\mathbb{P}(s_t=\cdot \mid I_t)$ is a sufficient statistic for control: it evolves by the deterministic Bayes filter $b_{t+1}=\tau (b_t,u_t,z_{t+1})$ driven by the realized action and observation, and the optimal finite-horizon cost-to-go is a function $J_t$ of $b_t$ alone satisfying

$$J_t(b)=\underset{a\in A}{\min }\{\bar{g}(b,a)+\alpha \sum _{z\in Z}\sigma (b,a,z)J_{t+1}(\tau (b,a,z)\left)\right\},J_N(b)={\bar{g}}_N(b),$$

with $\bar{g}(b,a)={\sum }_{s}b(s)g(s,a)$. Consequently the POMDP is equivalent to the fully observed belief MDP on $\Delta (S)$, and in the infinite-horizon discounted case its optimality operator is a sup-norm $\alpha$-contraction on $B(\Delta (S))$ with unique fixed point $J^{\ast }$, exactly as in 44.08.03.

Proof. First, the belief recursion. By definition $b_{t+1}(s^{\prime })=\mathbb{P}(s_{t+1}=s^{\prime }\mid I_t,u_t,z_{t+1})$. Bayes' rule conditions the joint law of $(s_{t+1},z_{t+1})$ given $(I_t,u_t)$ on the realized $z_{t+1}$:

$$b_{t+1}(s^{\prime })=\frac{\mathbb{P}(z_{t+1}\mid s_{t+1}=s^{\prime },u_t)\mathbb{P}(s_{t+1}=s^{\prime }\mid I_t,u_t)}{\mathbb{P}(z_{t+1}\mid I_t,u_t)}.$$

The observation depends on the new state and action only, so the first factor is $O(z_{t+1}\mid s^{\prime },u_t)$. The one-step-ahead predictive uses the Markov transition and the definition of $b_t$: $\mathbb{P}(s_{t+1}=s^{\prime }\mid I_t,u_t)={\sum }_{s}P(s^{\prime }\mid s,u_t)b_t(s)$. The denominator is the sum of the numerator over $s^{\prime }$, which is $\sigma (b_t,u_t,z_{t+1})$. This is the stated $\tau$, a deterministic function of $(b_t,u_t,z_{t+1})$; $b_{t+1}$ depends on the past only through $b_t$, so $(b_t)$ is a controlled Markov process — the belief is Markov even though the hidden state is unobserved.

Second, sufficiency and the recursion. Write the exact DP over the information vector: ${\tilde{J}}_t(I_t)={\min }_a\{\mathbb{E}[g(s_t,a)\mid I_t]+\alpha \mathbb{E}[{\tilde{J}}_{t+1}(I_{t+1})\mid I_t,a]\}$, the standard backward recursion of 44.08.01 applied to the information-state system. Each ingredient depends on $I_t$ only through $b_t$: the running cost is $\mathbb{E}[g(s_t,a)\mid I_t]={\sum }_s{b}_t(s)g(s,a)=\bar{g}(b_t,a)$, and the continuation expectation factors through the observation law as $\mathbb{E}[{\tilde{J}}_{t+1}(I_{t+1})\mid I_t,a]={\sum }_z\sigma (b_t,a,z){\tilde{J}}_{t+1}(I_t,a,z)$, where the next information vector is $(I_t,a,z)$ whose belief is $\tau (b_t,a,z)$. By downward induction from the terminal stage, where ${\tilde{J}}_N(I_N)=\mathbb{E}[g_N(s_N)\mid I_N]={\bar{g}}_N(b_N)$ depends on $I_N$ only through $b_N$: if ${\tilde{J}}_{t+1}(I_{t+1})=J_{t+1}(b_{t+1})$ for a function $J_{t+1}$ on $\Delta (S)$, then ${\tilde{J}}_t(I_t)$ equals the displayed $J_t(b_t)$, again a function of $b_t$ alone. The induction establishes both that $J_t$ exists and that it satisfies the belief-state recursion; the optimal action at $I_t$ is the minimizer, a function of $b_t$, so $b_t$ is sufficient for control.

Third, the contraction. The belief recursion exhibits $(\Delta (S),A,\{\tau (\cdot ,a,z)\},\sigma ,\bar{g},\alpha )$ as a bona fide MDP: a state space $\Delta (S)$, an action set $A$, transitions to $\tau (b,a,z)$ with probabilities $\sigma (b,a,z)$ that sum to one over $z$ (since $\sigma (b,a,\cdot )$ is the law of $z_{t+1}$), and a bounded cost $|\bar{g}(b,a)|\le M$. The optimality operator $(\mathcal{T}J)(b)={\min }_a\{\bar{g}(b,a)+\alpha {\sum }_z\sigma (b,a,z)J(\tau (b,a,z))\}$ on $B(\Delta (S))$ is therefore a sup-norm $\alpha$-contraction by the MDP contraction theorem of 44.08.03 applied verbatim to this belief MDP, with unique fixed point $J^{\ast }=\mathcal{T}{J}^{\ast }$ the optimal discounted cost. $\square$

Bridge. This theorem is the foundational reason a hidden-state problem is no harder, structurally, than a known-state one: the conditional distribution $b_t$ absorbs the entire information vector, and once it does, the belief-state Bellman recursion is exactly the MDP optimality equation of 44.08.03 with the simplex $\Delta (S)$ as state space and the deterministic Bayes filter $\tau$ as the transition map. This is exactly the sufficient-statistic principle: the belief is what one must carry, and nothing more. The reduction generalises the fully observed MDP — recovered when $O(z\mid s^{\prime },a)$ reveals $s^{\prime }$, so $b_t$ is a vertex of the simplex and the belief MDP restricts to $S$ — and it builds toward the Smallwood–Sondik representation, where the belief-MDP value function inherits piecewise-linear convexity from the affine running cost and the bilinear belief update. The central insight is that promoting the unobserved state to a computed probability vector converts imperfect information into perfect information over a richer state. Putting these together, the same contraction that solved the MDP solves the POMDP, and the bridge is that the only genuinely new object is the filter $\tau$; this appears again in the linear-quadratic-Gaussian problem, where $\tau$ is the Kalman filter and the belief mean is all that the optimal controller needs.

Exercises Intermediate+

Advanced results Master

The belief-MDP reduction supports four developments: the Smallwood–Sondik piecewise-linear-convex (PWLC) representation of the finite-horizon value function with exact value iteration over $\alpha$-vectors, the computational hardness of exact POMDP solution, point-based approximate value iteration, and the linear-quadratic-Gaussian special case where the filter is Kalman and certainty equivalence holds.

Theorem 1 (Smallwood–Sondik: PWLC value function and the $\alpha$-vector backup). For a finite-state, finite-observation POMDP, each finite-horizon optimal cost-to-go $J_t:\Delta (S)\to \mathbb{R}$ is piecewise linear and convex: there is a finite set ${\Gamma }_t\subset {\mathbb{R}}^{|S|}$ with $J_t(b)={\min }_{\alpha \in {\Gamma }_t}⟨b,\alpha ⟩$. The terminal ${\Gamma }_N=\{(g_N(s){)}_s\}$ is a single vector. Given ${\Gamma }_{t+1}$, the exact backup constructs ${\Gamma }_t$ by combining, for each action $a$ and observation $z$, the backprojected vectors

$${\alpha }_{\beta }^{a,z}(s)=\sum _{s^{\prime }}P(s^{\prime }\mid s,a)O(z\mid s^{\prime },a)\beta (s^{\prime }),\beta \in {\Gamma }_{t+1},$$

forming, for each action $a$ and each choice of one vector per observation, the cross-sum ${\alpha }^a=\frac{1}{|Z|}g(\cdot ,a)+\alpha {\sum }_z{\alpha }_{{\beta }_z}^{a,z}$, and taking ${\Gamma }_t={\bigcup }_a\{{\alpha }^a\}$ with dominated vectors pruned. The unnormalized $⟨b,{\alpha }_{\beta }^{a,z}⟩$ already folds the observation normalizer $\sigma$ into the inner product, so no division by $\sigma$ appears in the backup; pruning a vector $\alpha$ that satisfies $⟨b,\alpha ⟩>{\min }_{{\alpha }^{\prime }\ne \alpha }⟨b,{\alpha }^{\prime }⟩$ for all $b\in \Delta (S)$ is a linear-programming feasibility test ^{[Smallwood Sondik 1973]}.

Theorem 2 (computational hardness of exact POMDP planning). The cardinality $|{\Gamma }_t|$ produced by the unpruned backup is $|A||{\Gamma }_{t+1}{|}^{|Z|}$, doubly exponential in the horizon before pruning; even after optimal pruning the minimal $|{\Gamma }_t|$ can grow exponentially. Exact finite-horizon POMDP value iteration is PSPACE-hard, and the infinite-horizon discounted problem — deciding whether a policy of value within $\epsilon$ of optimal exists — is undecidable in general for unbounded representations. The intractability is intrinsic to the belief space, a continuum simplex of dimension $|S|-1$ over which an exponentially detailed PWLC function must be maintained, not an artifact of any one algorithm ^{[Kaelbling Littman Cassandra 1998]}.

Theorem 3 (point-based value iteration as an $\alpha$-vector lower bound). Point-based methods control the explosion by backing up $\alpha$-vectors only at a finite set $B=\{b_1,\dots ,b_m\}\subset \Delta (S)$ of sampled beliefs: for each $b_i$ one computes a single optimal backed-up vector ${\alpha }_i$ and sets $\hat{\Gamma }=\{{\alpha }_1,\dots ,{\alpha }_m\}$, so $|\hat{\Gamma }|\le m$ stays bounded across iterations. Because every ${\alpha }_i$ is a genuine backprojection of vectors in the previous set, $\hat{J}(b)={\min }_{\alpha \in \hat{\Gamma }}⟨b,\alpha ⟩$ is an upper bound on the optimal cost everywhere (lower bound for rewards), exact at the sampled beliefs and accurate where the reachable belief set clusters; PBVI, Perseus, HSVI, and SARSOP differ in how they grow and prune $B$ and whether they also maintain a complementary bound. The approximation error is controlled by the belief-space sample density and the contraction modulus $\alpha$ ^{[Kaelbling Littman Cassandra 1998]}.

Theorem 4 (linear-quadratic-Gaussian separation and certainty equivalence). For the linear-Gaussian system $x_{t+1}=A{x}_t+B{u}_t+w_t$, $z_t=C{x}_t+v_t$ with independent Gaussian noises and quadratic cost, the belief is exactly Gaussian and its sufficient statistic is the pair (mean ${\hat{x}}_t$, covariance ${\Sigma }_t$); the mean evolves by the Kalman filter — the linear-Gaussian instance of the Bayes filter $\tau$ — and ${\Sigma }_t$ evolves by a deterministic Riccati recursion independent of the data. The optimal control is $u_t=-K_t{\hat{x}}_t$, the very LQR gain of the fully observed problem 44.07.02 applied to the state estimate: estimation and control separate, and the controller is certainty-equivalent, acting on ${\hat{x}}_t$ as if it were the true state. This is the one classical POMDP family with a closed-form solution; the cost decomposes into the deterministic-LQR cost plus an estimation-error penalty driven by ${\Sigma }_t$ ^{[Bertsekas Vol. 1 Ch. 5]}.

Synthesis. The foundational reason a partially observed problem is solvable at all is the sufficient-statistic reduction: the belief $b_t=\mathbb{P}(s_t\mid I_t)$ is the smallest summary of the entire information vector that suffices for optimal control, and once the unobserved state is promoted to this computed probability vector, imperfect information becomes perfect information over the richer state space $\Delta (S)$. This is exactly the MDP optimality equation of 44.08.03 transplanted to the simplex, with the deterministic Bayes filter $\tau$ as the transition map and the predictive law $\sigma$ as the transition probability; the $\alpha$-contraction, value iteration, and greedy-policy machinery are inherited rather than reproven, and the only genuinely new object is the filter. The central insight is that the structure of the running data — an affine running cost $\bar{g}(b,a)$ composed with a bilinear belief update — forces the value function to be piecewise linear and convex, so the abstract belief-MDP recursion becomes the concrete Smallwood–Sondik $\alpha$-vector backup, which generalises the finite vector of MDP values to a finite set of vectors indexed by the optimal continuation plan.

The reduction is dual to the estimation problem it contains: the Kalman filter is the belief update for the linear-Gaussian instance, and certainty equivalence is the statement that estimation and control separate there, the belief collapsing to its mean. Putting these together, the hardness theorems show the price of generality — the PWLC representation is doubly exponential and exact infinite-horizon solution is undecidable — so the same $\alpha$-vector object that solves small POMDPs exactly is, in point-based value iteration, sampled at finitely many beliefs to trade exactness for tractability while preserving a valid bound on the optimal value.

Full proof set Master

Proposition 1 (the Bayes filter is the belief recursion). The conditional law $b_{t+1}(s^{\prime })=\mathbb{P}(s_{t+1}=s^{\prime }\mid I_t,u_t,z_{t+1})$ equals $\tau (b_t,u_t,z_{t+1})(s^{\prime })$, a deterministic function of $(b_t,u_t,z_{t+1})$.

Proof. Condition on $(I_t,u_t)$ throughout. The joint law of $(s_{t+1},z_{t+1})$ given $(I_t,u_t)$ factors as $\mathbb{P}(s_{t+1}=s^{\prime }\mid I_t,u_t)\mathbb{P}(z_{t+1}\mid s_{t+1}=s^{\prime },u_t)$, because the observation depends only on the new state and the action. The first factor is the one-step predictive ${\sum }_{s}P(s^{\prime }\mid s,u_t)b_t(s)$, using the controlled-Markov transition and the definition of $b_t$ as the conditional law of $s_t$ given $I_t$ (here $z_{t+1}$ has not yet been used). The second factor is $O(z_{t+1}\mid s^{\prime },u_t)$. Bayes' rule for $s_{t+1}$ given the additional datum $z_{t+1}$ divides this product by its sum over $s^{\prime }$:

$$b_{t+1}(s^{\prime })=\frac{O(z_{t+1}\mid s^{\prime },u_t){\sum }_{s}P(s^{\prime }\mid s,u_t)b_t(s)}{{\sum }_{s^{\prime \prime }}O(z_{t+1}\mid s^{\prime \prime },u_t){\sum }_{s}P(s^{\prime \prime }\mid s,u_t)b_t(s)},$$

which is $\tau (b_t,u_t,z_{t+1})(s^{\prime })$ with denominator $\sigma (b_t,u_t,z_{t+1})$. The right side depends on the history only through $b_t$, so $(b_t)$ is a controlled Markov process. $\square$

Proposition 2 (sufficiency: the information-vector DP factors through the belief). Let ${\tilde{J}}_t(I_t)$ be the optimal cost-to-go of the information-state DP. Then ${\tilde{J}}_t(I_t)=J_t(b_t)$ for a function $J_t$ on $\Delta (S)$ satisfying the belief-state Bellman recursion, and an optimal policy is a function of $b_t$.

Proof. Downward induction on $t$. At the terminal stage ${\tilde{J}}_N(I_N)=\mathbb{E}[g_N(s_N)\mid I_N]={\sum }_s{b}_N(s)g_N(s)={\bar{g}}_N(b_N)$, a function of $b_N$; set $J_N={\bar{g}}_N$. Suppose ${\tilde{J}}_{t+1}(I_{t+1})=J_{t+1}(b_{t+1})$. The DP step is ${\tilde{J}}_t(I_t)={\min }_a\{\mathbb{E}[g(s_t,a)\mid I_t]+\alpha \mathbb{E}[{\tilde{J}}_{t+1}(I_{t+1})\mid I_t,a]\}$. The first term is ${\sum }_s{b}_t(s)g(s,a)=\bar{g}(b_t,a)$. For the second, condition on the next observation: $I_{t+1}=(I_t,a,z)$ occurs with probability $\mathbb{P}(z_{t+1}=z\mid I_t,a)=\sigma (b_t,a,z)$, and on that event $b_{t+1}=\tau (b_t,a,z)$ by Proposition 1, so $\mathbb{E}[{\tilde{J}}_{t+1}\mid I_t,a]={\sum }_z\sigma (b_t,a,z)J_{t+1}(\tau (b_t,a,z))$. Substituting, ${\tilde{J}}_t(I_t)={\min }_a\{\bar{g}(b_t,a)+\alpha {\sum }_z\sigma (b_t,a,z)J_{t+1}(\tau (b_t,a,z))\}=:J_t(b_t)$, a function of $b_t$. The minimizing $a$ depends on $I_t$ only through $b_t$, so a belief-feedback policy is optimal, establishing sufficiency. $\square$

Proposition 3 (the belief MDP and contraction of $\mathcal{T}$). The tuple $(\Delta (S),A,\{\tau (\cdot ,a,z){\}}_z,\sigma ,\bar{g},\alpha )$ is an MDP, and its optimality operator $\mathcal{T}$ is a sup-norm $\alpha$-contraction on $B(\Delta (S))$ with unique fixed point the optimal discounted cost.

Proof. Transitions from $b$ under $a$ land on the points $\{\tau (b,a,z):z\in Z\}$ with probabilities $\sigma (b,a,z)\ge 0$ summing to $1$ (Exercise 5 / the normalizer is a law over $Z$), and the cost $\bar{g}(b,a)={\sum }_{s}b(s)g(s,a)$ is bounded by $M$. This is precisely the data of a (discounted) MDP with state space $\Delta (S)$. The contraction estimate is the MDP estimate of 44.08.03: for $J,J^{\prime }\in B(\Delta (S))$ and fixed $b,a$, the action scores differ by $\alpha {\sum }_z\sigma (b,a,z)(J(\tau )-J^{\prime }(\tau ))$ in absolute value at most $\alpha \Vert J-J^{\prime }{\Vert }_{\infty }$ since ${\sum }_z\sigma =1$; the minimum over the finite action set is $1$-Lipschitz, so $\Vert \mathcal{T}J-\mathcal{T}{J}^{\prime }{\Vert }_{\infty }\le \alpha \Vert J-J^{\prime }{\Vert }_{\infty }$. Completeness of $(B(\Delta (S)),\Vert \cdot {\Vert }_{\infty })$ and $\alpha <1$ give, by the Banach fixed-point theorem 02.01.05, a unique fixed point $J^{\ast }=\mathcal{T}{J}^{\ast }$, identified with the optimal cost by the MDP optimality theorem of 44.08.03 applied to this belief MDP. $\square$

Proposition 4 (preservation of PWLC under the exact backup). If $J_{t+1}(b)={\min }_{\beta \in {\Gamma }_{t+1}}⟨b,\beta ⟩$ for a finite ${\Gamma }_{t+1}$, then $J_t=\mathcal{T}{J}_{t+1}$ is again of the form ${\min }_{\alpha \in {\Gamma }_t}⟨b,\alpha ⟩$ for a finite ${\Gamma }_t$, hence piecewise linear and convex.

Proof. Expand one backup. For fixed $a$,

$$\bar{g}(b,a)+\alpha \sum _z\sigma (b,a,z)J_{t+1}(\tau (b,a,z)).$$

Inside, $\sigma (b,a,z)J_{t+1}(\tau (b,a,z))=\sigma \cdot {\min }_{\beta }⟨\tau ,\beta ⟩={\min }_{\beta }⟨\sigma \tau ,\beta ⟩={\min }_{\beta }⟨u^{a,z}(b),\beta ⟩$, where $u^{a,z}(b)(s^{\prime })=O(z\mid s^{\prime },a){\sum }_{s}P(s^{\prime }\mid s,a)b(s)$ is the unnormalized posterior (linear in $b$), using $\sigma \tau =u^{a,z}$. By linearity of the inner product in $b$, $⟨u^{a,z}(b),\beta ⟩=⟨b,{\alpha }_{\beta }^{a,z}⟩$ with ${\alpha }_{\beta }^{a,z}(s)={\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)O(z\mid s^{\prime },a)\beta (s^{\prime })$. Thus $\sigma J_{t+1}(\tau )={\min }_{\beta }⟨b,{\alpha }_{\beta }^{a,z}⟩$. The minimum-of-affine is taken inside the sum over $z$; since the choice of $\beta$ may differ per observation, ${\sum }_z{\min }_{\beta }⟨b,{\alpha }_{\beta }^{a,z}⟩={\min }_{({\beta }_z{)}_z}{\sum }_z⟨b,{\alpha }_{{\beta }_z}^{a,z}⟩$, a minimum over the finite set of observation-indexed selections $({\beta }_z)\in {\Gamma }_{t+1}^{|Z|}$. Adding the affine $\bar{g}(\cdot ,a)$ and the factor $\alpha$, the per-action value is ${\min }_{({\beta }_z)}⟨b,g(\cdot ,a)+\alpha {\sum }_z{\alpha }_{{\beta }_z}^{a,z}⟩$, a minimum of finitely many affine functions. Finally $J_t={\min }_a(\cdot )$ is a minimum over $a$ of such minima, hence $J_t(b)={\min }_{\alpha \in {\Gamma }_t}⟨b,\alpha ⟩$ with ${\Gamma }_t=\{g(\cdot ,a)+\alpha {\sum }_z{\alpha }_{{\beta }_z}^{a,z}:a\in A,({\beta }_z)\in {\Gamma }_{t+1}^{|Z|}\}$, a finite set; the pointwise minimum of affine functions is concave's mirror — it is convex since each piece is affine and the lower envelope of affine functions is convex. $\square$

Proposition 5 (unpruned $\alpha$-vector count). The construction of Proposition 4 yields $|{\Gamma }_t|\le |A||{\Gamma }_{t+1}{|}^{|Z|}$, and starting from $|{\Gamma }_N|=1$ gives a bound doubly exponential in the horizon before pruning.

Proof. For each action $a$ there are $|{\Gamma }_{t+1}{|}^{|Z|}$ observation-indexed selections $({\beta }_z)$, each producing one vector $g(\cdot ,a)+\alpha {\sum }_z{\alpha }_{{\beta }_z}^{a,z}$; ranging over $a\in A$ gives at most $|A||{\Gamma }_{t+1}{|}^{|Z|}$ vectors. With $|{\Gamma }_N|=1$, one step gives $|{\Gamma }_{N-1}|\le |A|$, then $|{\Gamma }_{N-2}|\le |A||A{|}^{|Z|}=|A{|}^{1+|Z|}$, and in general the exponent compounds multiplicatively by $|Z|$ each stage, so $|{\Gamma }_{N-k}|\le |A{|}^{(|Z{|}^k-1)/(|Z|-1)}$ for $|Z|\ge 2$, doubly exponential in $k$. Pruning removes vectors that are nowhere the minimum — testable by the linear program ${\min }_b\{⟨b,{\alpha }^{\prime }⟩-⟨b,\alpha ⟩\}$ over the simplex for each candidate dominator — but the minimal set can still grow exponentially. $\square$

Proposition 6 (perfect observation recovers the MDP). If $Z=S$ and $O(z\mid s^{\prime },a)=1[z=s^{\prime }]$, then every reachable belief is a vertex $e_{s^{\prime }}$ of $\Delta (S)$, the belief update reduces to the state transition, and the belief-state recursion is the MDP optimality equation of 44.08.03 on $S$.

Proof. With $O(z\mid s^{\prime },a)=1[z=s^{\prime }]$, $\sigma (b,a,z)={\sum }_{s^{\prime }}1[z=s^{\prime }]{\sum }_{s}P(s^{\prime }\mid s,a)b(s)={\sum }_{s}P(z\mid s,a)b(s)$, and $\tau (b,a,z)(s^{\prime })=1[s^{\prime }=z]{\sum }_{s}P(s^{\prime }\mid s,a)b(s)/\sigma =1[s^{\prime }=z]=e_z(s^{\prime })$, a vertex. Starting from a vertex $b=e_s$, $\sigma (e_s,a,z)=P(z\mid s,a)$ and the next belief is $e_z$; by induction all reachable beliefs are vertices $e_s$, identified with states. On vertices $\bar{g}(e_s,a)=g(s,a)$ and the recursion becomes $J_t(e_s)={\min }_a\{g(s,a)+\alpha {\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)J_{t+1}(e_{s^{\prime }})\}$, the MDP Bellman recursion of 44.08.03 with $J_t(e_s)$ read as the state value $V_t(s)$. $\square$

Connections Master

• The Markov decision process 44.08.03 is the structure this unit reduces to: the sufficient-statistic theorem reexpresses the POMDP as a fully observed MDP on the belief simplex $\Delta (S)$, so the MDP optimality operator, its sup-norm $\alpha$-contraction, value iteration, and greedy-policy criterion are inherited verbatim, the belief $b$ playing the role of the state and the deterministic Bayes filter $\tau$ the role of the transition map. The genuinely new content is the filter and the resulting piecewise-linear-convex value function; the fully observed MDP is the special case (Proposition 6) where the observation kernel reveals the state and beliefs collapse to simplex vertices.

• The finite-horizon dynamic programming and principle of optimality of 44.08.01 supply the backward recursion that, run on the information-state system, becomes the belief-state Bellman recursion once sufficiency is established; the terminal condition and the stage-by-stage minimization are the finite-horizon machinery transplanted to $\Delta (S)$. The Smallwood–Sondik $\alpha$-vector backup is precisely this recursion made computational for finite-state finite-observation models, each stage's value carried as a finite set of vectors rather than a table.

• The Markov chain and transition-matrix theory of 37.05.01 furnishes both the latent dynamics and the filter: the predict step of the Bayes update is the chain's one-step push-forward $\hat{b}=P_a^{\top }b$, and the correct step reweights by the observation likelihood. Fixing a belief-feedback policy turns the belief process into a Markov chain on $\Delta (S)$, so the recurrence and mixing of the underlying chain govern which beliefs are reachable and thus where point-based methods must sample.

• The linear-quadratic regulator and Hamilton–Jacobi–Bellman theory of 44.07.02 is the analytic special case: for the linear-Gaussian-quadratic problem the belief is Gaussian, the Bayes filter $\tau$ specializes to the Kalman filter, and the separation/certainty-equivalence theorem says the optimal controller is the deterministic LQR feedback applied to the filtered estimate. The POMDP value decomposes into the LQR value plus an estimation-error term, exhibiting estimation and control as separable subproblems whose only coupling is through the dimension of the belief.

Historical & philosophical context Master

The partially observed control problem was formulated within Richard Bellman's dynamic-programming program and the contemporaneous theory of statistical decision and filtering. Karl Åström's 1965 paper on the optimal control of Markov processes with incomplete state information ^{[Astrom 1965]} gave the belief (conditional distribution) as the sufficient statistic and the reduction to a fully observed problem over the space of distributions. The decisive structural result for finite models is due to Edward Sondik and Richard Smallwood: their 1973 Operations Research paper ^{[Smallwood Sondik 1973]} proved that the finite-horizon value function is piecewise linear and convex and gave the first exact value-iteration algorithm over the associated vectors, with Sondik's 1978 work extending the analysis toward the discounted infinite-horizon case.

The reduction's analytic ancestor is the linear-Gaussian filtering and control theory: Rudolf Kálmán's 1960 filter ^{[Kalman 1960]} is the belief update for the Gaussian instance, and the separation of estimation from control — that the optimal linear-quadratic-Gaussian controller applies the deterministic regulator gain to the Kalman estimate — was established for that family by Wonham and others in the 1960s. The modern algorithmic and complexity-theoretic treatment, including the witness and incremental-pruning algorithms, the PSPACE-hardness of finite-horizon planning, and the undecidability of the unbounded infinite-horizon problem, was consolidated in the artificial-intelligence literature by Kaelbling, Littman, and Cassandra ^{[Kaelbling Littman Cassandra 1998]}, whose framing motivated the point-based approximate methods that made moderate-sized POMDPs practical. The comprehensive control-theoretic reference is Bertsekas's treatment of imperfect state information ^{[Bertsekas Vol. 1 Ch. 5]}.

Bibliography Master

@article{smallwoodsondik1973,
  author  = {Smallwood, Richard D. and Sondik, Edward J.},
  title   = {The Optimal Control of Partially Observable Markov Processes over a Finite Horizon},
  journal = {Operations Research},
  volume  = {21},
  number  = {5},
  year    = {1973},
  pages   = {1071--1088}
}

@article{kaelbling1998pomdp,
  author  = {Kaelbling, Leslie Pack and Littman, Michael L. and Cassandra, Anthony R.},
  title   = {Planning and Acting in Partially Observable Stochastic Domains},
  journal = {Artificial Intelligence},
  volume  = {101},
  number  = {1--2},
  year    = {1998},
  pages   = {99--134}
}

@article{astrom1965pomdp,
  author  = {{\AA}str{\"o}m, Karl Johan},
  title   = {Optimal Control of Markov Processes with Incomplete State Information},
  journal = {Journal of Mathematical Analysis and Applications},
  volume  = {10},
  number  = {1},
  year    = {1965},
  pages   = {174--205}
}

@article{kalman1960filter,
  author  = {Kalman, Rudolf E.},
  title   = {A New Approach to Linear Filtering and Prediction Problems},
  journal = {Journal of Basic Engineering},
  volume  = {82},
  number  = {1},
  year    = {1960},
  pages   = {35--45}
}

@book{bertsekas2017dpvol1,
  author    = {Bertsekas, Dimitri P.},
  title     = {Dynamic Programming and Optimal Control, Volume 1},
  edition   = {4},
  publisher = {Athena Scientific},
  year      = {2017}
}

@book{krishnamurthy2016pomdp,
  author    = {Krishnamurthy, Vikram},
  title     = {Partially Observed Markov Decision Processes: From Filtering to Controlled Sensing},
  publisher = {Cambridge University Press},
  year      = {2016}
}