Derive the Bellman Control Equation Over POMDP Beliefs

You write down the MDP Bellman equation, swap $s$ for $b$, and the result looks plausible. It also predicts nothing you can act on. The symbol changed; the object it refers to did not. Fix that, and the recursion falls out almost mechanically.

Why the MDP Recursion Stops Working

Assume the standard toolkit: return, discounting, $V$ and $Q$, and the one-step decomposition $V(s) = \mathbb{E}[R_{t+1} + \gamma V(S_{t+1}) \mid S_t = s]$. That equation is correct because $s$ is the quantity the agent is in. At decision time, the agent knows $s$, so it can evaluate $V(s)$ and select an action.

In a POMDP, the agent does not know $s$. It cannot evaluate $V(s)$ for the true state, and it cannot act on a value it cannot compute. The obvious repair — condition on the full history $h_t = (a_0, o_1, a_1, o_2, \dots)$ — is valid in principle. A history is a sufficient decision variable. It is also unusable: it grows without bound, and two different histories can be decision-equivalent, meaning they imply the same distribution over hidden states and therefore the same optimal action.

The target of this article is a recursion whose argument is something the agent actually possesses at time $t$.

The Belief as a Decision State

Define the belief $b$ as a probability distribution over the state set $S$:

$b(s) \ge 0, \qquad \sum_{s \in S} b(s) = 1.$

For $|S|$ states, beliefs live on the $(|S|-1)$-dimensional simplex. With two states, that is a line segment; with three, a triangle.

The claim that makes the derivation work is sufficiency: given $b_t$, the future is conditionally independent of how $b_t$ was reached. Two histories that produce the same belief produce the same distribution over future states, observations, and rewards. The belief is a sufficient statistic for the history.

Note: Sufficiency is a property of the model, not of the agent's approximation. It holds when the transition model $T(s' \mid s, a)$ and observation model $O(o \mid s', a)$ are known, stationary, and used correctly in the belief update. If the model is wrong or drifting, the resulting distribution is still a valid probability vector — but it is no longer a sufficient statistic, and the recursion silently optimizes the wrong problem.

That distinction matters more than it looks. A belief computed with a broken model is a distribution that lies. It will produce confident, wrong decisions, and no amount of planning will detect the error from inside the recursion.

From POMDP to Belief MDP

Once the belief is sufficient, the POMDP reduces to a fully observed MDP whose states are beliefs. The tuple is $(B, A, \tau, r, \gamma)$:

• $B$ is the belief space — continuous, even when $S$ is finite.
• $A$ is the same finite action set.
• $\tau(b, a, b')$ is the belief transition kernel.
• $r(b, a)$ is the expected immediate reward.
• $\gamma$ is the same discount factor.

The reward is a direct expectation under current uncertainty:

$r(b, a) = \sum_{s \in S} b(s) \, R(s, a).$

The transition kernel takes more work. Given belief $b$ and action $a$, the predicted distribution over next states is $\sum_s b(s) T(s' \mid s, a)$. After observing $o$, Bayes' rule corrects it:

$b'(s') = \frac{O(o \mid s', a) \sum_s T(s' \mid s, a) b(s)}{\Pr(o \mid b, a)},$

where $\Pr(o \mid b, a) = \sum_{s'} O(o \mid s', a) \sum_s T(s' \mid s, a) b(s)$ normalizes the result. Marginalizing over observations gives the kernel:

$\tau(b, a, b') = \sum_{o \in O} \Pr(b' \mid b, a, o) \Pr(o \mid b, a).$

The structural point: the next belief is stochastic because the observation is stochastic. Even with deterministic underlying dynamics, the agent's information state jumps unpredictably. That is what makes the belief MDP a genuine MDP rather than a relabeled POMDP.

The cost is immediate. A finite POMDP becomes a continuous-state MDP. Exact solutions require piecewise-linear structure or a finite reachable belief set; otherwise the recursion is approximated.

Deriving the Belief-State Value Recursion

Start from the definition. For a policy $\pi$ mapping beliefs to actions:

$V_\pi(b) = \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t R_t \;\middle|\; b_0 = b \right].$

Write the first reward term explicitly and apply the one-step decomposition:

$V_\pi(b) = \mathbb{E}_\pi \left[ R_0 + \gamma \sum_{t=1}^{\infty} \gamma^{t-1} R_t \;\middle|\; b_0 = b \right].$

The first term is the expected immediate reward under the policy's action distribution. The second is the discounted continuation, which depends on the successor belief. Pushing the expectation through the belief transition:

$V_\pi(b) = \sum_{a \in A} \pi(a \mid b) \left[ r(b, a) + \gamma \sum_{b' \in B} \tau(b, a, b') \, V_\pi(b') \right].$

This is the POMDP belief state Bellman equation for a fixed policy. Every symbol is something the agent can compute: $r(b,a)$ from the reward table and current belief, $\tau$ from the transition and observation models, and $V_\pi(b')$ from the value function being defined.

For control, replace the policy average with a maximum:

$V^*(b) = \max_{a \in A} \left[ r(b, a) + \gamma \sum_{b' \in B} \tau(b, a, b') \, V^*(b') \right].$

This is a fixed-point equation. The operator on the right is a contraction in the sup norm when $\gamma < 1$, so the optimal value function is its unique fixed point.

Warning: The assumptions are load-bearing. Finite $S$, $A$, and $O$; known models; infinite horizon with $\gamma < 1$ or an absorbing terminal condition. Drop any of these and the fixed-point argument needs repair.

Worked Example: A Two-State POMDP

Two hidden states $s_0, s_1$. Two actions $a_0, a_1$. Two observations $o_0, o_1$. Transition and observation tables:

Rewards: $R(s_0, a_0) = 1$, $R(s_1, a_0) = -1$, $R(s_0, a_1) = 0$, $R(s_1, a_1) = 0$. Take $\gamma = 0.9$ and belief $b = (0.7, 0.3)$.

Immediate expected reward. For $a_0$: $0.7(1) + 0.3(-1) = 0.4$. For $a_1$: $0$.

Successor beliefs for $a_0$. Predicted next-state distribution: $s_0$ gets $0.7(0.9) + 0.3(0.2) = 0.69$, $s_1$ gets $0.31$. Observation probabilities: $\Pr(o_0 \mid b, a_0) = 0.69(0.8) + 0.31(0.3) = 0.645$; $\Pr(o_1 \mid b, a_0) = 0.69(0.2) + 0.31(0.7) = 0.355$. Corrected beliefs: after $o_0$, $b' = (0.552/0.645, 0.093/0.645) \approx (0.856, 0.144)$; after $o_1$, $b' = (0.138/0.355, 0.217/0.355) \approx (0.389, 0.611)$.

Successor beliefs for $a_1$. The transition sends both hidden states to the same distribution $(0.5, 0.5)$, and the observation is uninformative, so both observations leave the belief at $(0.5, 0.5)$.

One-step lookahead. Suppose a crude $V(b') \approx 0$ for all $b'$. Then $Q(b, a_0) \approx 0.4$ and $Q(b, a_1) \approx 0$. The max selects $a_0$.

Now suppose $V(b') = 1$ for $b'$ with $b'(s_0) > 0.5$ and $V(b') = -1$ otherwise. Then $Q(b, a_0) \approx 0.4 + 0.9[0.645(1) + 0.355(-1)] \approx 0.4 + 0.9(0.29) \approx 0.661$. And $Q(b, a_1) \approx 0 + 0.9(-1) = -0.9$. The max stays with $a_0$ — the action whose noisy observations produce a successor belief that lands on the favorable side of the value function.

Contrast case. The most likely state under $b = (0.7, 0.3)$ is $s_0$. A greedy most-likely-state policy would pick $\arg\max_a R(s_0, a) = a_0$. Here the belief-optimal action agrees, but for a different reason: $a_0$ is chosen because its observation distribution shifts the successor belief toward $s_0$, not because $s_0$ is the mode. Change the continuation value and the two policies can diverge.

Belief Update Is Not Belief Control

The update is inference. It answers what do I now believe? It consumes a prior belief, an action, and an observation. It produces a posterior belief. It optimizes nothing.

Control is optimization. It answers what should I do given what I believe? It consumes a value function, a horizon, and a discount. It produces an action.

The coupling that makes this subtle: the value of an action depends on the information the resulting observation will provide. A belief-state policy can deliberately choose actions that are informative rather than immediately rewarding. That behavior is invisible to an agent that only implements the update.

Common mistake: An agent that tracks beliefs perfectly and still acts myopically. The update was implemented; the recursion never was. The symptom is a policy that reacts to the current belief but never invests in reducing uncertainty.

When This Recursion Is the Right Tool

Use it when the model is known or learnable, the state space is small, and the decision genuinely depends on uncertainty rather than on a point estimate. The recursion is the right answer when the value of information is part of the value of an action.

Do not use it when a point estimate of the state is adequate, when the belief space is too large to represent, or when model error dominates the planning gain. A continuous belief space with a poorly estimated transition kernel will produce a confident policy for the wrong problem.

The cost is structural. Exact value iteration over beliefs requires piecewise-linear value functions or a finite reachable belief set. Otherwise the recursion is approximated by sampling, discretization, or function approximation. The approximation is where most practical POMDP work lives.

Warning: Planning on a belief that is not sufficient — a truncated history summary, a learned recurrent state that has not been validated as a statistic — produces confident, wrong decisions. The recursion does not know the difference.

Where to Go Next

The recursion is not the MDP equation with a renamed variable. It is the MDP equation applied to a different process — one whose states happen to be probability distributions. The belief is not a summary of the state; it is the state of that process.

Hand-compute the one-step lookahead for a second belief, say $b = (0.4, 0.6)$, under the same tables. Check whether the argmax action changes. If it does, you have seen the belief doing real work as a decision state.

The durable rule: if you can write the belief transition kernel $\tau$ and the belief reward $r$, you can write the recursion. If you cannot, you are doing inference, not control.