Finite-horizon POMDP values are piecewise-linear and convex

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.