# Variables Reduction in Sequential Resource Allocation Problems
## 2 Dynamic Principle for Optimal Switching and Reduction of Decision Variables  
In applications, sequential decision-making is usually addressed under the framework of discrete-time _Stochastic Control_. The theory of _Markov Decision Processes/Dynamic Programming_ provides a variety of methods to deal with such questions. In generic situations, approaching analytical solutions for even some simplest decision processes may be a cumbersome process ([10; 14; 16]) Furthermore, since closed-form solutions to practically important control problems are usually unavailable, numerical approximations became popular among practitioners to obtain approximately optimal control policies. Although a huge variety of computational methods have been developed therefore, typical real-world problems are usually too complex for the existing solution techniques, in particular if the state dimension of the underlying controlled evolution is high. Let us review the finite-horizon [PERSON] decision theory following [17]. **Controlled Markov processes:** Consider a random dynamics on a finite time horizon \(0,\ldots,T\) whose state \(x\) evolves in \(E\) and is controlled by actions \(a\) from an action set \(A\). For each \(a\in A\), we assume that \(K_{t}^{a}(x,dx^{\prime})\) is a stochastic transition kernel on \(E\). A mapping \(\pi_{t}:E\mapsto A\) which describes the action that the controller takes at time \(t\) is called a _decision rule_. A sequence of decision rules \(\pi=(\pi_{t})_{t=0}^{T-1}\) is called a _policy_. For each initial point \(x_{0}\in E\) and each policy \(\pi=(\pi_{t})_{t=0}^{T-1}\), there exists a probability measure \(\mathbb{P}^{x_{0},\pi}\) and a stochastic process \((X_{t})_{t=0}^{T}\) satisfying the initial condition \(\mathbb{P}^{x_{0},\pi}(X_{0}=x_{0})=1\) such that  
\[\mathbb{P}^{x_{0},\pi}(X_{t+1}\in B\mid X_{0},\ldots,X_{t})=K_{t}^{\pi_{t}(X_{ t})}(X_{t},B) \tag{1}\]  
holds for each \(B\subset E\) at all times \(t=0,\ldots,T-1\), i.e., given that system is in state \(X_{t}\) at time \(t\), the action \(a=\pi_{t}(X_{t})\) is used to pick the transition probability \(K_{t}^{a=\pi_{t}(X_{t})}(X_{t}\cdot)\) which randomly drives the system from \(X_{t}\) to \(X_{t+1}\) with the distribution \(K_{t}^{\pi_{t}(X_{t})}(X_{t}\cdot)\). Let us use \(\mathcal{K}_{t}^{a}\) to denote the one-step transition operator associated with the transition kernel \(K_{t}^{a}\) when the action \(a\in A\) is chosen. In other words, for each action \(a\in A\) the operator \(\mathcal{K}_{t}^{a}\) acts on functions \(v\) by  
\[(\mathcal{K}_{t}^{a}v)(x)=\int_{E}v(x^{\prime})K_{t}^{a}(x,dx^{\prime})\qquad x \in E, \tag{2}\]  
whenever the above integrals are well-defined. **Costs of control:** For each time \(t\), we are given the \(t\)-_step reward function_\(r_{t}:E\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 E\) at time \(t\). Atthe 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)\), which is described by a pre-specified _scrap function_\(r_{T}:E\to\mathbb{R}\), is collected. Given an initial point \(x_{0}\), the goal is to maximize the expected finite-horizon total reward, in other words to find the argument \(\pi^{*}=(\pi_{t}^{*})_{t=0}^{T-1}\) such that  
\[\pi^{*}=\operatorname{argmax}_{\pi}\mathbb{E}^{x_{0},\pi}\left(\sum_{t=0}^{T-1 }r_{t}(X_{t},\pi_{t}(X_{t}))+r_{T}(X_{T})\right), \tag{3}\]  
where \(A\) is the set of all policies, and \(\mathbb{E}^{x_{0},\pi}\) denotes the expectation over the controlled Markov chain defined by (1). **Decision optimization:** The maximization (3) is well-defined under diverse additional assumptions (see [14], p. 199). The calculation of the optimal policy is addressed in the following setting.