# An Algorithm for Making Regime-Changing Markov Decisions
## 4 Approximate Algorithmic Solutions  
Although there are a number theoretical and computational methods to solve stochastic control problems, many industrial applications exhibit complexity and size driving numerical techniques to their computational limits. For an overview on this topic we referrer the reader to [7]. One of the major difficulties originates from high-dimensionality. Here, approximate methods have been proposed based on state and action space discretization or approximations of functions on this space. Among _function approximation_ methods, the _least-squares Monte Carlo approach_ represents a traditional way to approximate the value function s in [8; 9; 10; 11; 12; 13]. However, function approximation methods have also been used to capture local behavior of value functions and advanced regression methods such as kernel methods [14; 15], local polynomial regression [16], and neural networks [17], have been suggested. Considering partial observability, several specific approaches are studied in [18], with bound estimation presented in [19]. The work [20] provides an overview of modern algorithms in this field with the main focus on the so-called point-based solvers. The main aspect of any point-based POMDP algorithm (see [21]) is a dynamical adaptation of the state-discretized grid. In this work, we treat our regime switching Markov decision problem in terms of efficient numerical schemes, which deliver an approximate solution along with its diagnostics. The following section presents this methodology and elaborates on specific assumptions, required in this setting. The numerical solution method is based on function approximations which require convexity and linear state dynamics. For technical details, we refer the interested reader to [22]. Furthermore, there are applications to pricing financial options [23], natural resource extraction [3], battery management [24] and optimal asset allocation under hidden state dynamics [25], many applications are illustrated using R in [26]. Suppose that the state space \(\mathcal{X}=P\times\mathbb{R}^{d}\) is a Cartesian product of a finite set \(P\) and the Euclidean space \(\mathbb{R}^{d}\). Consider a controlled Markovian process \((X_{t})_{t=0}^{T}:=(P_{t},Z_{t})_{t=0}^{T}\) that consists of two parts. The discrete-space component \((P_{t})_{t=0}^{T}\) describes the evolution of a finite-state controlled Markov chain, taking values in a finite set \(P\), while the continuous-space component \((Z_{t})_{t=0}^{T}\) follows uncontrolled evolution with values in \(\mathbb{R}^{d}\). More specifically, we assume that at any time \(t=0,\ldots,T-1\) in an arbitrary state \((p,z)\in\mathcal{X}\) the controller chooses an action \(a\) from \(A\) in order to trigger the one-step transition from the mode \(p\in P\) to the mode \(p^{\prime}\in P\) with probability \(\alpha_{p,p^{\prime}}^{a}(z)\), given in terms of pre-specified transition probability matrices \((\alpha_{p,p^{\prime}}^{a}(z))_{p,p^{\prime}\in P}\) indexed by actions \(a\in A\). Notethat these transition probabilities can depend on continuous state component \(z\in\mathbb{R}^{d}\). For the continuous-state process \((Z_{t})_{t=0}^{T}\), we assume an uncontrolled evolution which is governed by linear state dynamics  
\[Z_{t+1}=W_{t+1}Z_{t},\qquad t=0,\ldots,T-1, \tag{21}\]  
with independent _disturbance matrices_\((W_{t})_{t=1}^{T}\), thus the transition operators \(\mathcal{K}_{t}^{a}\) are  
\[\mathcal{K}_{t}^{a}v(p,z)=\sum_{p^{\prime}\in P}\alpha_{p,p^{\prime}}^{a}(z) \mathbb{E}(v(p^{\prime},W_{t+1}z)),\quad p\in P,z\in\mathbb{R}^{d},t=0,\ldots,T-1, \tag{22}\]  
acting on all function \(v:P\times\mathbb{R}^{d}\to\mathbb{R}\) where the required expectations exist.