# An Algorithm for Making Regime-Changing Markov Decisions
## 3 Markov Decisions under Partial Observation
More precisely, we suppose that\(((s_{t},y_{t}))_{t=0}^{T}\) follows a Markov process whose transition operators are acting on functions \(v:S\times Y\to\mathbb{R}\) as  
\[(s,y)\mapsto\sum_{s^{\prime}\in S}\int_{Y}v(s^{\prime},y^{\prime})\Gamma_{s,s^{ \prime}}\mu_{s}(\mathrm{d}y^{\prime}). \tag{15}\]  
Here, \((\mu_{s})_{s\in S}\) stands for the family of distributions for the next-time observation of \(y_{t+1}\), conditioned on \(s_{t}=s\in S\). For each \(s\in S\), we assume that the distribution \(\mu_{s}\) is absolutely continuous with respect to a reference measure \(\mu\) on \(Y\) and introduce the densities  
\[v_{s}(y)=\frac{\mathrm{d}\mu_{s}}{\mathrm{d}\mu}(y)\text{ for }y\in Y\text{ and }s \in S.\]  
Since the state evolution \((s_{t})_{t=0}^{T}\) is not available, one must rely on the believe distribution \(\hat{s}_{t}\) of the state \(s_{t}\), conditioned on the observations \(y_{0},\ldots,y_{t}\). With this, the _hidden state estimates_\((\hat{s}_{t})_{t=0}^{T}\) yield a process that takes values in the set \(\widehat{S}\) of all probability measures on \(S\) which is identified with the convex hull of \(S\) due to (14). It turns out that although the observation process \((y_{t})_{t=0}^{T}\) is non-Markovian, it can be augmented by the believes process to obtain \((z_{t}=(\widehat{s}_{t},y_{t}))_{t=0}^{T}\) which follows a Markov process on the state space \(Z=\widehat{S}\times Y\). This process is driven by the transition kernels acting on functions \(v:\widehat{S}\times Y\to\mathbb{R}\) as  
\[\mathcal{K}_{t}v(\hat{s},y)=\int_{Y}vs.\bigg{(}\frac{\Gamma^{\top}\mathcal{V}( y^{\prime})\hat{s}}{\|\mathcal{V}(y^{\prime})\hat{s}\|},y^{\prime}\bigg{)}\| \mathcal{V}(y^{\prime})\hat{s}\|\mu(\mathrm{d}y^{\prime}),\quad(\hat{s},y)\in \widehat{S}\times Y, \tag{16}\]  
for all \(t=0,\ldots T-1\). In this formula, \(\mathcal{V}(y)\) stands for the diagonal matrix whose diagonal elements are given by \((v_{s}(y))_{s\in S}\), \(y\in Y\) whereas \(\|\cdot\|\) represents the usual \(l_{1}\) norm. Remark 2: _In the Formula (16) the quantity_  
\[\hat{s}(y^{\prime}):=\frac{\Gamma^{\top}\mathcal{V}(y^{\prime})\hat{s}}{\| \mathcal{V}(y^{\prime})\hat{s}\|} \tag{17}\]  
_represents the updated believe state under the assumption that prior to the observation \(y^{\prime}\in Y\), the believe state was \(\hat{s}\in\widehat{S}\). On this account, this vector must be an element of \(\widehat{S}\), which is seen as follows (the author would like to thank to anonymous referee for highlighting out this point): Having observed that all entries of \(\Gamma^{\top}\mathcal{V}(y^{\prime})\hat{s}\) and of \(\mathcal{V}(y^{\prime})\hat{s}\) are non-negative (ensured by multiplication of \(\hat{s}\) by matrices with non-negative entries), we have to verify that they sum up to one, thus (17) represents a probability distribution on \(S\). For this, we introduce a vector \(\overline{1}=(1,1,\ldots,1)\) of ones with our believe state dimension, in order to verify that the scalar product is_  
\[\overline{1}^{\top}\hat{s}(y^{\prime}) = \frac{\overline{1}^{\top}\Gamma^{\top}\mathcal{V}(y^{\prime})\hat {s}}{\|\mathcal{V}(y^{\prime})\hat{s}\|}=\frac{\overline{1}^{\top}\mathcal{V} (y^{\prime})\hat{s}}{\|\mathcal{V}(y^{\prime})\hat{s}\|}=1\]  
_in other words, all entries of \(\hat{s}(y)\) sum up to one. Here, we have used that \(\overline{1}^{\top}\Gamma^{\top}=\overline{1}\) since all rows of stochastic matrix \(\Gamma\) are probability vector whose \(l_{1}\) norm is representable by a scalar product with \(\overline{1}\)._  
The optimal control for such modulated MDP is formulated in terms of the transitions operators, rewards and scrap functions which we define now. With notations introduced above, consider a state space \(X=P\times Z\) with \(Z=\widehat{S}\times Y\).