# An Algorithm for Making Regime-Changing Markov Decisions
## 3 Markov Decisions under Partial Observation  
In view of the general framework from Section 2, the classical Markov Decision Processes (MDPs) are obtained by specifying controlled Markovian evolution \((X_{t})_{t=0}^{T}\) in terms of assumptions on the state space and on the transition kernels. Here, the state space is given by a finite set \(P\) such that states are driven in terms of  
\[\text{stochastic matrices}\;(\alpha^{a}_{p,p^{\prime}})_{p,p^{\prime}\in P}, \quad a\in A. \tag{9}\]  
indexed by a finite number of actions \(a\in A\) with the interpretation that \(\alpha^{a}_{p,p^{\prime}}\in[0,1]\) stands for the transition probability from \(p\in P\) to \(p^{\prime}\in P\) if the action \(a\in A\) was taken. In this settings, the stochastic kernels \(\mathcal{K}^{a}_{t}\) are acting functions \(v:P\to\mathbb{R}\) by  
\[\mathcal{K}^{a}_{t}v(p)=\sum_{p^{\prime}\in P}\alpha^{a}_{p,p^{\prime}}v(p^{ \prime})\qquad p\in P,\;t=0,\ldots T-1. \tag{10}\]  
There is no specific assumption on scrap and reward functions, they are given by following mappings on the state space \(P\):  
\[p\to r_{T}(p),\quad(p,a)\mapsto r_{t}(p,a),\quad t=0,\ldots,T-1,\quad a\in A. \tag{11}\]  
In this work, we consider control problems where a finite number of Markov decision problems are involved, sharing the same state space: each is activated by a certain regime. For this reason, we introduce a selection of MDPs indexed by a finite set \(S\) of regimes. Here, we assume that stochastic matrices as in (9) and control costs as in (11) are now indexed by \(S\):  
\[ \begin{array}{c}(\alpha^{a}_{p,p^{\prime}}(s))_{p,p^{\prime}\in P},\quad p \to r_{T}(p)(s),\\ (p,a)\mapsto r_{t}(p,a)(s),\;\;t=0,\ldots,T-1,\end{array} \quad a\in A,\qquad s \in S. \tag{12}\]  
Let us now consider decision making under incomplete information. Given family of Markov decision problems as in (12), the controller deals with a dynamic mixture of these problems in the sense that each of these MDPs becomes valid under a certain regime which changes exogenously in an uncontrolled way and is not observed directly. More precisely, interpreting each probability distribution \(\hat{s}=(\hat{s}(s))_{s\in S}\) on \(S\) as controllers believe about the current regime, we introduce the following convex mixtures of the ingredients (12):  
\[ \begin{array}{c}\alpha^{a}_{p,p^{\prime}}(\hat{s})=(\sum_{s\in S}\hat{s}(s) \alpha^{a}_{p,p^{\prime}}(s))_{p,p^{\prime}\in P}\quad p\to\sum_{s\in S}\hat{ s}(s)r_{T}(p)(s),\\ (p,a)\mapsto\sum_{s\in S}\hat{s}(s)r_{t}(p,a)(s),\;\;t=0,\ldots,T-1,\end{array} \quad a\in A,\;\hat{s}\in\widehat{S}. \tag{13}\]  
where \(\widehat{S}\) stands for the simplex of all probability distributions on \(S\). That is, the transition kernels and the control costs are now modulated by an external variable \(\hat{s}\in\widehat{S}\) which represents the evolution of controller's believe about the current situation. To describe its dynamics, we suppose that the information is updated dynamically through the observation of another process \((y_{t})_{t=1}^{T}\) which follows the so-called _hidden Markov dynamics_. Let us introduce this concept before we finish the definition of our regime-changing Markov decision problem. Consider a time-homogeneous Markov chain \((s_{t})_{t=0}^{T}\) evolving on a  
\[ \begin{array}{c}\text{finite space $S$ which is identified with the set of orthonormal basis}\\ \text{vectors of a finite-dimensional Euclidean space.}\end{array}  \tag{14}\]  
Assume that this Markov chain is governed by the stochastic matrix \(\Gamma=(\Gamma_{s,s^{\prime}})_{s,s^{\prime}\in S}\). It is supposed that the evolution of \((s_{t})_{t=0}^{T}\) is unobservable, representing a _hidden regime_. The available information is realized by another stochastic process \((y_{t})_{t=0}^{T}\) taking values in a space \(Y\), such that at any time \(t\), the distribution of the next observation \(y_{t+1}\) depends on the past \(\{y_{0},\ldots,y_{t}\}\) through the recent state \(s_{t}\) only.