Partial observability breaks the ordinary Markov property at the observation level. The correct state for planning is the belief distribution over hidden states.
POMDP model
The agent sees observations generated from a latent Markov state.
Definition. A partially observable Markov decision process has latent states \(S_t\), actions \(A_t\), transitions \(P(S_{t+1}\mid S_t,A_t)\), observations \(O_t\) generated from an observation kernel, and rewards depending on latent states and actions. The history \(H_t=(O_0,A_0,\ldots,O_t)\) is observed; \(S_t\) is not.
Remark. A policy based only on the current observation is generally not Markov-optimal, because the observation may not contain all information about the latent state.
Belief states
The posterior distribution of the latent state is a sufficient statistic for control.
Definition. The belief state is \[ b_t(B)=P(S_t\in B\mid H_t). \] Bayes filtering updates \(b_t\) using the action, transition kernel, and new observation likelihood.
Theorem. The belief process is fully observed and Markov controlled: \(b_{t+1}\) depends on the past only through \((b_t,A_t,O_{t+1})\).
Proof. Given \(b_t\) and \(A_t\), the predictive law of \(S_{t+1}\) is obtained by integrating the transition kernel against \(b_t\). Observing \(O_{t+1}\) applies Bayes' rule to this predictive law. The earlier history enters only through \(b_t\), so the belief update is Markov.
Belief MDP
Planning in a POMDP can be reformulated as planning in a continuous-state MDP over beliefs.
Proposition. The expected reward under belief \(b\) and action \(a\) is \[ \bar r(b,a)=\int r(s,a)b(\mathrm{d}s), \] and the belief transition kernel is induced by prediction and Bayes update. Thus the POMDP becomes a fully observed belief MDP.
Proof. Conditional on the history, the latent state distribution is \(b\). Taking conditional expectation of reward gives \(\bar r\). The next belief is a measurable function of the current belief, action, and random observation, which defines the belief transition kernel.
Memory and recurrent policies
Approximate solutions often replace exact beliefs by learned memory states.
Remark. Recurrent networks, filters, and predictive-state representations can be viewed as approximations to belief-state inference. Their statistical difficulty is that representation learning and control are coupled.
Hidden-state control
A POMDP augments an MDP with observations: \[ S_{t+1}\sim P(\cdot\mid S_t,A_t),\qquad O_{t+1}\sim G(\cdot\mid S_{t+1},A_t). \] The controller sees \(H_t=(O_0,A_0,\ldots,A_{t-1},O_t)\), not \(S_t\). A policy is a kernel from observable histories to actions.
Bayesian filtering and the belief MDP
Theorem (belief-state reduction). Let \[ b_t(B)=\mathbb P(S_t\in B\mid H_t) \] be the filtering distribution. Under known kernels, \(b_{t+1}\) is a deterministic measurable function \(\tau(b_t,A_t,O_{t+1})\). The process \(b_t\) is a fully observed controlled Markov process, and no history-dependent policy can outperform a policy that depends only on \(b_t\).
Proof. Prediction and Bayes update give \[ \bar b_{t+1}(\mathrm{d}s') =\int P(\mathrm{d}s'\mid s,A_t)b_t(\mathrm{d}s), \] \[ b_{t+1}(\mathrm{d}s') =\frac{G(\mathrm{d}O_{t+1}\mid s',A_t)\bar b_{t+1}(\mathrm{d}s')} {\int G(\mathrm{d}O_{t+1}\mid x,A_t)\bar b_{t+1}(\mathrm{d}x)}. \] Conditional on \(b_t,A_t\), the next observation and belief law do not depend on earlier history. Expected immediate reward is \(\bar r(b,a)=\int r(s,a)b(\mathrm{d}s)\). Markovization on the belief space therefore preserves every additive return.
Piecewise-linear convex finite-horizon values
Theorem. In a finite POMDP with finite horizon and reward maximization, the optimal value is piecewise linear and convex in the belief: \[ V_h^*(b)=\max_{\alpha\in\Gamma_h}\alpha^\top b \] for a finite set of alpha-vectors \(\Gamma_h\).
Proof. At the terminal stage the value is the maximum over action-reward vectors, hence has the form. Assume the next stage has alpha-vectors. For each current action and each mapping from possible observations to next-stage alpha-vectors, expand expected reward plus next value before normalizing the Bayes update. The resulting expression is linear in the current belief. Maximizing over finitely many action/continuation plans produces a finite maximum of linear functions.
Dimensional and statistical difficulty
The belief simplex is continuous even when hidden state and observation spaces are finite, and the number of alpha-vectors can grow exponentially with horizon. Point-based value iteration retains vectors useful on sampled beliefs; particle filters approximate beliefs in large models. Errors now arise from filtering, value approximation, and planning, and they interact.
Memory, predictive states, and identifiability
A recurrent policy compresses history into a learned state, but without guarantees that this state is sufficient. Predictive-state representations use conditional distributions of future observations as state coordinates and can avoid latent-state nonidentifiability. Off-policy learning is particularly delicate: two latent models may induce the same behavior-policy observation law but different target-policy values. Sequential overlap plus observability or identification assumptions are therefore necessary, not merely more data.