Exhaustive finite-horizon POMDP alpha-vector backup

Input a finite POMDP, a horizon $H\in \mathbb{N}$, and its discount $\gamma \in [0,1]$. A depth-zero policy tree is the empty continuation and has the zero vector ${\alpha }_0:S\to \mathbb{R}$. Recursively, a depth-$(h+1)$ policy tree consists of a root action $a\in A$ and one depth-$h$ continuation tree for each observation $o\in \mathrm{\Omega }$. If the continuation vectors are $({\alpha }_o{)}_{o\in \mathrm{\Omega }}$, assign the tree the vector

${\alpha }_{a,({\alpha }_o)}(s)=r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}\in S}T(s^{\mathrm{\prime }}\mid s,a){\sum }_{o\in \mathrm{\Omega }}O(o\mid s^{\mathrm{\prime }}){\alpha }_o(s^{\mathrm{\prime }})(s\in S)\mathrm{.}$

Set ${\mathrm{\Gamma }}_0=\{{\alpha }_0\}$. For each $h=0,\dots ,H-1$, form ${\mathrm{\Gamma }}_{h+1}$ from every action $a\in A$ and every tuple $({\alpha }_o{)}_{o\in \mathrm{\Omega }}\in {\mathrm{\Gamma }}_h^{\mathrm{\Omega }}$ using the displayed formula, treating ${\mathrm{\Gamma }}_{h+1}$ as a set so equal vectors are stored once. Return $({\mathrm{\Gamma }}_0,\dots ,{\mathrm{\Gamma }}_H)$. This procedure exhaustively enumerates finite policy-tree vectors; it does not perform linear-program witness pruning and makes no bit-complexity or polynomial-time claim.

A finite known model supplies the state, action, observation, transition, reward, and observation laws.

Finite sums are defined independently of an enumeration of their finite index set.

Kaelbling, Littman, and Cassandra, Brown Technical Report CS-96-08.

Poupart, University of Waterloo CS 886 Lecture 13.

The diagram shows a depth-two policy tree: the root chooses $a_0$; after the observation $x$ the continuation chooses $a_x$, and after $y$ it chooses $a_y$. The outgoing edges represent observations, not hidden states or rewards. Every observation has a branch, including an observation that has probability zero at a particular belief. The algebraic definition above, rather than the diagram, determines the procedure and its outputs.

diagram failed to render:
\begin{tikzpicture}[level distance=1.25cm,sibling distance=3.0cm]
  \node[draw,rounded corners] {$a_0$}
    child { node[draw,rounded corners] {$a_x$} edge from parent node[left] {$x$} }
    child { node[draw,rounded corners] {$a_y$} edge from parent node[right] {$y$} };
\end{tikzpicture}