# An Algorithm for Making Regime-Changing Markov Decisions
## 2 Discrete-Time Stochastic Control  
First, let us review a finite-horizon control theory. Consider a random dynamics within a time horizon \(\{0,1,\ldots,T\}\subset\mathbb{N}\) whose state \(x\) evolves in a state space \(\mathcal{X}\) (subset of a Euclidean space) and is controlled by actions \(a\) from a finite action set \(A\). The mapping \(\pi_{t}:\mathcal{X}\mapsto A\), describing the action \(\pi_{t}(x)\) that the controller takes at time \(t=0,\ldots T\) in the situation \(x\in\mathcal{X}\) is referred to as _decision rule_. A sequence of decision rules \(\pi=(\pi_{t})_{t=0}^{T-1}\) is called a _policy_. Given a family of  
\[\text{stochastic kernels}\ K_{t}^{a}(x,dx^{\prime}),\quad t=0,\ldots,T-1\ \ a\in A\ \text{on}\ \mathcal{X},\]  
there exists an appropriately constructed probability space which supports a stochastic process \((X_{t})_{t=0}^{T}\) such that for each initial point \(x_{0}\in\mathcal{X}\) and each policy \(\pi=(\pi_{t})_{t=0}^{T-1}\) there exists a measure \(\mathbb{P}^{x_{0},\pi}\) and such that  
\[\mathbb{P}^{x_{0},\pi}(X_{0}=x_{0})=1,\quad\mathbb{P}^{x_{0},\pi}(X_{t+1}\in B \mid X_{0},\ldots,X_{t})=\mathcal{K}_{t}^{\pi_{t}(X_{t})}(X_{t},B) \tag{1}\]  
holds for \(t=0,\ldots,T-1\) for each measurable \(B\subset\mathcal{X}\). Such a system is called _controlled Markovian evolution_. The interpretation is that if at time \(t\) the process state is \(X_{t}\) and the action \(\pi_{t}(X_{t})\) is applied, then the distribution \(K_{t}^{\pi_{t}(X_{t})}(X_{t},\cdot)\) randomly changes the state from \(X_{t}\) to \(X_{t+1}\). Stochastic kernels are equivalently described in terms of transition operators. The transition operator, associated with the stochastic kernel \(K_{t}^{a}\) will be denoted by the same letter, but it acts on functions \(v:\mathcal{X}\to\mathbb{R}\) by  
\[(\mathcal{K}_{t}^{a}vs.)(x)=\int_{\mathcal{X}}v(x^{\prime})\mathcal{K}_{t}^{a }(x,dx^{\prime})\qquad x\in\mathcal{X},\,t=0,\ldots,T-1 \tag{2}\] \begin{table}
\begin{tabular}{l c c c c} \hline \hline stochastic kernel & \(\mathcal{K}_{t}^{a}\) & vector with unit entries & \(\bar{\Upsilon}\) & volume & cubic meter \\ controlled probability & \(\mathbb{P}^{x,\pi}\) & \(l^{1}\)-norm & \(\|\cdot\|\) & area & hectare \\ controlled expectation & \(\mathbb{E}^{x,\pi}\) & maximum & \(\bigvee\) & currency & USD \\ Bellman operator & \(\mathcal{T}_{t}\) & binding by row & \(\sqcup\) & costs & USD per hectare \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations and measurement units. whenever the above integrals are well-defined. Having introduced such controlled Markovian dynamics, let us turn to control costs now. Suppose that for each time \(t=0,\ldots,T-1\), we are given the \(t\)_-step reward function_\(r_{t}:\mathcal{X}\times A\mapsto\mathbb{R}\) where \(r_{t}(x,a)\) represents the reward for applying an action \(a\in A\) when the state of the system is \(x\in\mathcal{X}\) at time \(t\). At the end of the time horizon, at time \(T\), it is assumed that no action can be taken. Here, if the system is in a state \(x\), a _scrap value_\(r_{T}(x)\), described by a pre-specified _scrap function_\(r_{T}:\mathcal{X}\to\mathbb{R}\) is collected. The expectation of the cumulative reward from following a policy \(\pi\) is referred to as _policy value_:  
\[v_{0}^{\pi}(x)=\mathbb{E}^{x,\pi}\left(\sum_{t=0}^{T-1}r_{t}(X_{t},\pi_{t}(X_{ t}))+r_{T}(X_{T})\right),\quad x\in\mathcal{X},\]  
where \(\mathbb{E}^{x,\pi}\) denotes the expectation over the controlled Markov chain whose distribution is defined by (1). For \(t=0,\ldots,T-1\), introduce the backward induction operator  
\[\mathcal{T}_{t}^{a}v(x)=r_{t}(x,a)+\mathcal{K}_{t}^{a}v(x),\quad x\in \mathcal{X},\quad a\in A \tag{3}\]  
which acts on each measurable function \(v:\mathcal{X}\to\mathbb{R}\) where \(\mathcal{K}_{t}^{a}v\) is well-defined.