POMDPs and belief-state planning

The final equality in [F1] says precisely that the set $\{t\in \mathbb{N}:t<n\}$ is $n$, so $I_n=n$.

By [F2], $n$ is finite and $\mathrm{\mid }n\mathrm{\mid }=n$. Substituting $I_n=n$ from step 1.1 gives that $I_n$ is finite and $\mathrm{\mid }{I}_n\mathrm{\mid }=n$.

For fixed $s,a$, the mass $J(s^{\mathrm{\prime }},\rho ,o\mid s,a)=p(s^{\mathrm{\prime }},\rho \mid s,a)O(o\mid s^{\mathrm{\prime }})$ is nonnegative. Summing first over observations gives ${\sum }_{s^{\mathrm{\prime }},\rho ,o}J={\sum }_{s^{\mathrm{\prime }},\rho }p(s^{\mathrm{\prime }},\rho \mid s,a){\sum }_{o}O(o\mid s^{\mathrm{\prime }})={\sum }_{s^{\mathrm{\prime }},\rho }p(s^{\mathrm{\prime }},\rho \mid s,a)=1$ by [F1]; all index sets are finite, so the reordering is justified by [F6] and [F7]. Thus the joint next-state/reward/observation mass is normalized.

The predicted coordinates ${\bar{b}}_{b,a}(s^{\mathrm{\prime }})$ are nonnegative, and ${\sum }_{s^{\mathrm{\prime }}}{\bar{b}}_{b,a}(s^{\mathrm{\prime }})={\sum }_{s}b(s){\sum }_{s^{\mathrm{\prime }}}T(s^{\mathrm{\prime }}\mid s,a)={\sum }_{s}b(s)=1$ by [F1], [F2], and finite double-sum interchange [F7]. Hence ${\bar{b}}_{b,a}$ is a probability distribution.

Every $q(o\mid b,a)$ is nonnegative, and ${\sum }_{o}q(o\mid b,a)={\sum }_{s^{\mathrm{\prime }}}{\bar{b}}_{b,a}(s^{\mathrm{\prime }}){\sum }_{o}O(o\mid s^{\mathrm{\prime }})={\sum }_{s^{\mathrm{\prime }}}{\bar{b}}_{b,a}(s^{\mathrm{\prime }})=1$ by [F1], step 1.2, and [F7]. Thus $q(\cdot \mid b,a)$ is a probability distribution, so each $q$ is finite and lies in $[0,1]$.

Fix $o$ with $q(o\mid b,a)>0$. Apply [F4] with prior $\pi ={\bar{b}}_{b,a}$ on the finite state set, observation kernel $Q(s^{\mathrm{\prime }},\cdot )=O(\cdot \mid s^{\mathrm{\prime }})$, counting measure on finite $\mathrm{\Omega }$, and density $\mathrm{\ell }(s^{\mathrm{\prime }},o)=O(o\mid s^{\mathrm{\prime }})$. The density is nonnegative and jointly measurable, and its marginal is exactly $q(o\mid b,a)$, which is finite and positive by step 2.1. The theorem's posterior is therefore $\tau (b,a,o)$, with coordinates summing to one. At $q=0$ the Bayes theorem supplies a filler for its everywhere kernel, but the partial update defined here remains undefined and $K$ omits that zero-mass observation.

For fixed $b,a$, the formula for $K$ is a finite nonnegative sum of point masses at the defined $\tau (b,a,o)$. For pairwise disjoint Borel sets $(C_n{)}_{n\ge 1}$, each point $\tau (b,a,o)$ lies in at most one $C_n$, so $1_{{\cup }_n{C}_n}(\tau )={\sum }_n{1}_{C_n}(\tau )$ with at most one nonzero term. Since there are finitely many observations, distributing the finite weighted sum over these finitely many nonzero terms gives $K({\cup }_n{C}_n)={\sum }_{n}K(C_n)$. Also $K(\mathrm{\Delta }(S))={\sum }_{o:q>0}q(o\mid b,a)=1$ by step 2.1. Thus $K(\cdot \mid b,a)$ is a probability measure.

On $\mathrm{\Delta }(S)\times A$, the predicted law $\bar{K}(\{s^{\mathrm{\prime }}\}\mid b,a)={\bar{b}}_{b,a}(s^{\mathrm{\prime }})$ is a probability kernel: step 1.2 gives probability sections, and each evaluation is a finite linear function of $b$ on each discrete action. The function $((b,a),s^{\mathrm{\prime }})\mapsto O(o\mid s^{\mathrm{\prime }})$ is product-measurable, so [F5] makes $q(o\mid b,a)=\int O(o\mid s^{\mathrm{\prime }})\bar{K}(d{s}^{\mathrm{\prime }}\mid b,a)$ measurable; its displayed finite formula also shows it is continuous in $b$. On the Borel set where $q(o\mid b,a)>0$, every coordinate of $\tau$ is a quotient of continuous functions with positive denominator and is Borel. For Borel $C$, the function equal to $q(o\mid b,a)1_C(\tau (b,a,o))$ there and zero where $q=0$ is Borel; summing these functions over the finite set $\mathrm{\Omega }$ proves that $K(C\mid b,a)$ is Borel measurable. By [F3], $K$ is a probability kernel.

The only conditional law used in step 3.1 is the explicit dominated-kernel formula at a positive finite marginal. The finite history beliefs are ratios on positive-probability atoms, and all other constructions use specified finite sums and kernels; no version selection or arbitrary-family choice is used.

Fix $h_t$ and $a$ as in the statement. By [F2], $b_t(s)=\mathrm{Pr}(S_t=s\mid h_t)$. Conditioning first on $S_t$ and using the POMDP's specified one-step law [F1] gives $\mathrm{Pr}(S_{t+1}=s^{\mathrm{\prime }},O_{t+1}=o\mid h_t,A_t=a)={\sum }_{s\in S}{b}_t(s)T(s^{\mathrm{\prime }}\mid s,a)O(o\mid s^{\mathrm{\prime }})$. The action selection does not alter $b_t$ after conditioning on $h_t$, because its randomization depends only on that history and is conditionally independent of the hidden state.

Summing the joint probability in step 1.1 over $s^{\mathrm{\prime }}$ yields $q(o\mid b_t,a)$ by [F2]. If this is positive, dividing the joint mass by it gives $\mathrm{Pr}(S_{t+1}=s^{\mathrm{\prime }}\mid h_t,A_t=a,O_{t+1}=o)=\tau (b_t,a,o)(s^{\mathrm{\prime }})$; if it is zero, the observation event has probability zero and no conditional quotient is used. By [F3], these positive branches form the probability kernel $K$.

Conditioning the immediate reward on the current hidden state and chosen action gives $\mathbb{E}[R_t\mid h_t,A_t=a]={\sum }_{s\in S}{b}_t(s)r(s,a)=\bar{r}(b_t,a)$ by [F1] and [F2]. Thus the conditional immediate reward and next-belief law depend on the history only through $b_t$ and $a$, which proves the stated controlled belief-state transition and reward description.

We prove the finite-horizon recursion by induction on $n$. With no decisions remaining, the reward sum is empty, so $V_0(b)=0$. Suppose the optimal $n$-step continuation value is the function $V_n$ of the current belief. If action $a$ is taken at belief $b$, its immediate expected reward is $\bar{r}(b,a)$ by step 2.2, and for each positive-probability observation $o$ the remaining belief is $\tau (b,a,o)$ by step 2.1. Conditional expectation over the finite observation set therefore gives the $n+1$ step action value $Q_{n+1}(b,a):=\bar{r}(b,a)+\gamma {\sum }_{o:q>0}q(o\mid b,a)V_n(\tau (b,a,o))$. The set $\{Q_{n+1}(b,a):a\in A\}$ is a nonempty finite image of $A$ in $\mathbb{R}$, so [F4] gives an attained maximum. Taking that maximum gives the displayed $V_{n+1}(b)$. The expression depends only on $b$, completing the induction and proving history sufficiency for every finite horizon.

If the action at a history is randomized with probabilities ${\lambda }_a$, its expected action value is ${\sum }_{a\in A}{\lambda }_a{Q}_{n+1}(b,a)$, where $Q_{n+1}$ is the finite action value from step 3.1, ${\lambda }_a\ge 0$, and ${\sum }_a{\lambda }_a=1$. Since each $Q_{n+1}(b,a)\le {\max }_{c\in A}{Q}_{n+1}(b,c)$, [F5] gives ${\sum }_a{\lambda }_a{Q}_{n+1}(b,a)\le {\max }_{c\in A}{Q}_{n+1}(b,c)$. Randomization cannot improve the finite-horizon value.

At horizon $h=0$, there is one empty-continuation policy tree and the backup returns ${\mathrm{\Gamma }}_0=\{0\}$. Its conditional value is zero at every state, and the optimal zero-step value is $V_0(b)=0={\sum }_{s}b(s)0$ for each belief. Thus $P(0)$ holds.

Fix $h\in \mathbb{N}$ and assume $P(h)$.

A depth-$(h+1)$ policy tree is a root action $a$ and a depth-$h$ continuation tree ${\pi }_o$ for each $o\in \mathrm{\Omega }$. From initial hidden state $s$, its expected immediate reward plus discounted continuation value is ${\sum }_{s^{\mathrm{\prime }}\in S}{\sum }_{\rho \in \mathcal{R}}{\sum }_{o\in \mathrm{\Omega }}p(s^{\mathrm{\prime }},\rho \mid s,a)O(o\mid s^{\mathrm{\prime }})(\rho +\gamma {\alpha }_h^{{\pi }_o}(s^{\mathrm{\prime }}))$. By the induction hypothesis [L1], each continuation vector ${\alpha }_h^{{\pi }_o}$ is represented in ${\mathrm{\Gamma }}_h$. Since the continuation is selected from $o$ alone, not from the unobserved reward $\rho$, finite-sum linearity and reindexing [F5], together with ${\sum }_{o}O(o\mid s^{\mathrm{\prime }})=1$ from [F1], rewrite this expectation as ${\sum }_{s^{\mathrm{\prime }},\rho }\rho p(s^{\mathrm{\prime }},\rho \mid s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}}({\sum }_{\rho }p(s^{\mathrm{\prime }},\rho \mid s,a)){\sum }_{o}O(o\mid s^{\mathrm{\prime }}){\alpha }_h^{{\pi }_o}(s^{\mathrm{\prime }})$. The first term is $r(s,a)$ and the inner next-state marginal is $T(s^{\mathrm{\prime }}\mid s,a)$ by [F1], so this is exactly the vector formed by [F3]. Conversely, each tuple generated by [F3] has a depth-$h$ tree for each continuation vector by [L1]; since $\mathrm{\Omega }$ is finite, choose these finitely many trees successively and adjoin the root action to obtain a depth-$(h+1)$ tree. Therefore ${\mathrm{\Gamma }}_{h+1}$ is exactly the set of distinct conditional-value vectors of those trees. The candidate set $A\times {\mathrm{\Gamma }}_h^{\mathrm{\Omega }}$ is finite by [F8]–[F9], so its image ${\mathrm{\Gamma }}_{h+1}$ under the vector formula is finite; it is nonempty by the nonempty action set and a constant continuation tuple.

For each depth-$(h+1)$ tree $\pi$, conditioning on the initial hidden state gives value ${\sum }_{s}b(s){\alpha }_{h+1}^{\pi }(s)$ from belief $b$. Every deterministic history policy is such a tree: its first action is the root and its restriction after each observation is the corresponding subtree; conversely every tree prescribes such a policy. Since ${\mathrm{\Gamma }}_{h+1}$ is finite and nonempty by step 2.1, its value set $\{{\sum }_{s}b(s)\alpha (s):\alpha \in {\mathrm{\Gamma }}_{h+1}\}$ is a nonempty finite image in $\mathbb{R}$, so [F6] gives an attained maximum. By [F4], randomized policies cannot improve it. Hence $V_{h+1}(b)={\max }_{\alpha \in {\mathrm{\Gamma }}_{h+1}}{\sum }_{s}b(s)\alpha (s)$. This completes $P(h+1)$.

The base step 1.1 and successor steps 2.1–3.1 prove $P(h)$ for every natural $h$ by induction. The recursion in [F3] depends only on the preceding stage, so a call with horizon at least $h$ has the same ${\mathrm{\Gamma }}_h$ as a call with horizon exactly $h$. In particular, the displayed alpha-vector representation holds for every $0\le h\le H$.

For each $\alpha \in {\mathrm{\Gamma }}_h$, its maximizing region $R_{\alpha }$ is the simplex intersected with the finitely many half-spaces ${\sum }_{s}b(s)(\alpha (s)-\beta (s))\ge 0$, one for each $\beta \in {\mathrm{\Gamma }}_h$. These regions cover $\mathrm{\Delta }(S)$ because the maximum in step 4.1 is attained, and on $R_{\alpha }$ the value equals the linear function $b\mapsto {\sum }_{s}b(s)\alpha (s)$. This proves piecewise linearity.

For arbitrary $b,c\in \mathrm{\Delta }(S)$ and $\lambda \in [0,1]$, the vector $\lambda b+(1-\lambda )c$ is again in $\mathrm{\Delta }(S)$ by [F2]: its coordinates are nonnegative and sum to $\lambda +(1-\lambda )=1$. Finite-sum linearity [F5] gives ${\sum }_s(\lambda b(s)+(1-\lambda )c(s))\alpha (s)=\lambda {\sum }_{s}b(s)\alpha (s)+(1-\lambda ){\sum }_{s}c(s)\alpha (s)$ for each $\alpha$. Taking the maximum over ${\mathrm{\Gamma }}_h$ and bounding each summand by the corresponding maxima gives $V_h(\lambda b+(1-\lambda )c)\le \lambda V_h(b)+(1-\lambda )V_h(c)$. Thus $V_h$ is convex.

Define ${\mathrm{\Gamma }}_h^{\mathrm{w}\mathrm{i}\mathrm{t}}=\{\alpha \in {\mathrm{\Gamma }}_h:\mathrm{\exists }b\in \mathrm{\Delta }(S),{\sum }_{s}b(s)\alpha (s)=V_h(b)\}$. For arbitrary $b$, [F6] gives a maximizing ${\alpha }_b\in {\mathrm{\Gamma }}_h$; that same $b$ witnesses ${\alpha }_b$, so ${\alpha }_b\in {\mathrm{\Gamma }}_h^{\mathrm{w}\mathrm{i}\mathrm{t}}$. Therefore ${\max }_{\alpha \in {\mathrm{\Gamma }}_h^{\mathrm{w}\mathrm{i}\mathrm{t}}}{\sum }_{s}b(s)\alpha (s)=V_h(b)$; deleting all vectors with no witness preserves the value at every belief.

Let ${\mathcal{P}}_0$ contain only the empty continuation and ${\mathcal{P}}_{h+1}=A\times {\mathcal{P}}_h^{\mathrm{\Omega }}$. A depth-$(h+1)$ tree is uniquely its root action and a function from observations to depth-$h$ trees. By [F8]–[F9], these sets are finite and their cardinalities satisfy $N_0=1$ and $N_{h+1}=\mathrm{\mid }A\mathrm{\mid }{N}_h^{\mathrm{\mid }\mathrm{\Omega }\mathrm{\mid }}$; [F10] fixes the natural-power convention. The map from trees to conditional-value vectors has image ${\mathrm{\Gamma }}_h$, the set of distinct exhaustive candidates by step 2.1. Enumerating the $N_h$ trees shows that this image has at most $N_h$ vectors, and the witness vectors form a subset, so their count is no larger.

In the case $\mathrm{\mid }A\mathrm{\mid }=2$, $\mathrm{\mid }\mathrm{\Omega }\mathrm{\mid }=1$, let $Q(h)$ be the claim $N_h=2^h$. The base case is $N_0=1=2^0$.

Fix $h$ and assume $Q(h)$. Step 5.4 gives $N_{h+1}=2N_h=2\cdot 2^h=2^{h+1}$ by the natural-power recursion [F10], so $Q(h+1)$ holds.

The base and successor steps prove $N_h=2^h$ for every $h$ by [F11]. Thus exhaustive tree candidates can grow exponentially, although duplicate vectors or pruning may reduce the stored set.

The induction conclusions in steps 4.1 and 7.1, together with the envelope and convexity arguments in steps 5.1 and 5.2, witness pruning in step 5.3, and the general tree count in step 5.4, establish all claims. No Axiom of Choice is used: branches are selected only over the finite observation set, maxima are attained in finite sets, and the cited sufficiency, finite-sum, finite-function-set, product, and induction arguments make no arbitrary-family choice.