Belief states and the finite Bayes filter

For a finite POMDP with state set $S$, define its belief simplex by $\mathrm{\Delta }(S)=\{b:S\to [0,1]:{\sum }_{s\in S}b(s)=1\}$, with the Euclidean subspace topology and its Borel sigma-algebra. At time $t$, the observed-history random variable is $H_t=(A_0,O_1,\dots ,A_{t-1},O_t)$, and a realized history is $h_t=(a_0,o_1,\dots ,a_{t-1},o_t)$; at $t=0$ both histories are empty. A (possibly randomized) history policy assigns to each finite history $h_t$ a probability distribution ${\pi }_t(\cdot \mid h_t)$ on $A$; a deterministic choice is the point-mass case. Let ${\mathrm{Pr}}_{\pi }$ be the induced finite law: multiply the initial belief, these action probabilities, and the one-step factors $p(s^{\mathrm{\prime }},\rho \mid s,a)O(o\mid s^{\mathrm{\prime }})$, and sum out hidden states and unobserved rewards when taking marginals. Thus policy randomization depends only on the observed history and is conditionally independent of the hidden state given that history. The history $h_t$ is reachable when ${\mathrm{Pr}}_{\pi }(H_t=h_t)>0$. Its belief state is

$b_t(s)={\mathrm{Pr}}_{\pi }(S_t=s\mid H_t=h_t)=\frac{{\mathrm{Pr}}_{\pi }(S_t=s,H_t=h_t)}{{\mathrm{Pr}}_{\pi }(H_t=h_t)},$

where both probabilities are finite sums of products of the specified initial, action, transition, joint reward-transition, and observation probabilities, with unobserved rewards summed out. At $t=0$, the empty history has belief $b_0$.

For $b\in \mathrm{\Delta }(S)$ and $a\in A$, define the predicted state distribution ${\bar{b}}_{b,a}(s^{\mathrm{\prime }})={\sum }_{s\in S}T(s^{\mathrm{\prime }}\mid s,a)b(s)$ and, for $o\in \mathrm{\Omega }$, the observation probability

$q(o\mid b,a)={\sum }_{s^{\mathrm{\prime }}\in S}O(o\mid s^{\mathrm{\prime }}){\bar{b}}_{b,a}(s^{\mathrm{\prime }})\mathrm{.}$

When $q(o\mid b,a)>0$, the Bayes filter is the probability vector

$\tau (b,a,o)(s^{\mathrm{\prime }})=\frac{O(o\mid s^{\mathrm{\prime }}){\bar{b}}_{b,a}(s^{\mathrm{\prime }})}{q(o\mid b,a)}\mathrm{.}$

When $q(o\mid b,a)=0$, $\tau (b,a,o)$ is undefined; no quotient or filler value is assigned. For each $(b,a)$, the belief-state transition kernel on Borel sets $C\subseteq \mathrm{\Delta }(S)$ is

$K(C\mid b,a)={\sum }_{o\in \mathrm{\Omega }:q(o\mid b,a)>0}q(o\mid b,a)1_C(\tau (b,a,o)),$

and the expected one-step reward at belief $b$ under action $a$ is $\bar{r}(b,a)={\sum }_{s\in S}b(s)r(s,a)$, where $1_C$ denotes the indicator function of $C$.

The finite known transition and next-state observation laws used by the finite filter.

For a dominated observation kernel, Bayes' formula gives the conditional law at positive finite marginal density and specifies a filler on null fibres.

A probability kernel assigns a probability measure at every input and has measurable event sections.

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

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

Tedrake, MIT Underactuated Robotics course notes.

Poupart, University of Waterloo CS 886 Lecture 13.