11.3.3 The Probabilistic Case: POMDPs

Example 11.14 generalizes nicely to the case of $n$ states. In operations research and artificial intelligence literature, these are generally referred to as partially observable Markov decision processes or POMDPs (pronounced ``pom dee peez''). For the case of three states, the probabilistic I-space, ${\cal I}_{prob}$, is a $2$-simplex embedded in ${\mathbb{R}}^3$. In general, if $\vert X\vert = n$, then ${\cal I}_{prob}$ is an $(n-1)$-simplex embedded in ${\mathbb{R}}^n$. The coordinates of a point are expressed as $(p_0,p_1,\ldots,p_{n-1}) \in {\mathbb{R}}^n$. By the axioms of probability, $p_0 + \cdots + p_{n-1} = 1$, which implies that ${\cal I}_{prob}$ is an $(n-1)$-dimensional subspace of ${\mathbb{R}}^n$. The vertices of the simplex correspond to the $n$ cases in which the state is known; hence, their coordinates are $(0,0,\ldots,0,1)$, $(0,0,\ldots,0,1,0)$, $\ldots$, $(1,0,\ldots,0)$. For convenience, the simplex can be projected into ${\mathbb{R}}^{n-1}$ by specifying a point in ${\mathbb{R}}^{n-1}$ for which $p_1 + \cdots + p_{n-2} \leq 1$ and then choosing the final coordinate as $p_{n-1} = 1 - p_1 + \cdots + p_{n-2}$. Section 12.1.3 presents algorithms for planning for POMDPs.