Probabilistic forward projections

The probabilistic forward projection can be considered as a Markov process because the ``decision'' part is removed once the actions are given. Suppose that $x_k$ is given and $u_k$ is applied. What is the probability distribution over $x_{k+1}$? This was already specified in (10.6) and is the one-stage forward projection. Now consider the two-stage probabilistic forward projection, $P(x_{k+2}\vert x_k,u_k,u_{k+1})$. This can be computed by marginalization as

$$P(x_{k+2}\vert x_k,u_k,u_{k+1}) = \sum_{x_{k+1} \in X} P(x_{k+2}\vert x_{k+1},u_{k+1}) P(x_{k+1}\vert x_k,u_k) .$$ (10.13)

Computing further forward projections requires nested summations, which marginalize all of the intermediate states. For example, the three-stage forward projection is

$$\begin{split}P(x_{k+3}\vert x_k,u_k,& u_{k+1},u_{k+2}) = &... ...+2}\vert x_{k+1},u_{k+1}) P(x_{k+1}\vert x_k,u_k) . \end{split}$$ (10.14)

A convenient expression of the probabilistic forward projections can be obtained by borrowing nice algebraic properties from linear algebra. For each action $u \in U$, let its state transition matrix $M_u$ be an $n \times n$ matrix, for $n = \vert X\vert$, of probabilities. The matrix is defined as

$$M_u = \begin{pmatrix}m_{1,1} & m_{1,2} & \cdots & m_{1,n} m_{2... ...s & \vdots & & \vdots m_{n,1} & m_{n,2} & \cdots & m_{n,n} \end{pmatrix},$$ (10.15)

in which

$$m_{i,j} = P(x_{k+1} = i \; \vert \; x_k = j, \;u) .$$ (10.16)

For each $j$, the $j$th column of $M_u$ must sum to one and can be interpreted as the probability distribution over $X$ that is obtained if $u_k$ is applied from state $x_k = j$.

Let $v$ denote an $n$-dimensional column vector that represents any probability distribution over $X$. The product $M_u v$ yields a column vector that represents the probability distribution over $X$ that is obtained after starting with $v$ and applying $u$. The matrix multiplication performs $n$ inner products, each of which is a marginalization as shown in (10.13). The forward projection at any stage, $k$, can now be expressed using a product of $k-1$ state transition matrices. Suppose that ${\tilde{u}}_{k-1}$ is fixed. Let $v = [0 \; 0 \; \cdots 0 \; 1 \; 0 \; \cdots \; 0]$, which indicates that $x_1$ is known (with probability one). The forward projection can be computed as

$$v^\prime = M_{u_{k-1}} M_{u_{k-2}} \cdots M_{u_2} M_{u_1} v .$$ (10.17)

The $i$th element of $v^\prime$ is $P(x_k = i \;\vert\; x_1, {\tilde{u}}_{k-1})$.

Example 10..4 (Probabilistic Forward Projections)   Once again, use the first model from Example 10.1; however, now assign probability $1/3$ to each nature action. Assume that, initially, $x_1 = 0$, and $u=2$ is applied in every stage. The one-stage forward projection yields probabilities

$$[1/3 \;\; 1/3 \;\; 1/3]$$ (10.18)

over the sequence of states $(1,2,3)$. The two-stage forward projection yields

$$[1/9 \;\; 2/9 \;\; 3/9 \;\; 2/9 \;\; 1/9]$$ (10.19)

over $(2,3,4,5,6)$. $\blacksquare$