# Multi-Level Elasticity for Wide-Area Data Streaming Systems: A Reinforcement Learning Approach
## 6 Infrastructure Control Policy
### Local Policy: Reinforcement Learning Scaling Policy
#### 6.2.2 Model-Based Reinforcement Learning  
Model-based RL relies on a possibly approximated system model to directly compute the Q-functions. Instead of learning the value of state and actions through experience, in this scenario, the agent uses its experience to improve the system model approximation. In particular, we consider the _full backup model-based_ RL approach (see [14]), which backups the value of each state-action pair at every time step. To update the Q-function for all \(s\in\mathcal{S}\) and for all \(a\in\mathcal{A}(s)\), we directly use the Bellman equation [14; 51]  
\[Q(s,a)=\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)\left[c(s,a,s^{\prime}) +\gamma\min_{a^{\prime}\in\mathcal{A}}Q(s^{\prime},a^{\prime})\right].\]  
We replace the unknown state transition probabilities \(p(s^{\prime}|s,a)=P[s_{i+1}=s^{\prime}|s_{i}=s,a_{i}=a]\), and the unknown cost function \(c(s,a,s^{\prime})\), \(\forall s,s^{\prime}\in\mathcal{S}\) and \(a\in\mathcal{A}(s)\) by their empirical estimates, \(\hat{p}(s^{\prime}|s,a)\) and \(\hat{c}(s,a,s^{\prime})\). To estimate the transition probabilities \(p(s^{\prime}|s,a)\), we first observe that  
\[p(s^{\prime}|s,a) = P[s_{i+1}=(k^{\prime},u^{\prime},f^{\prime})|s_{i}=(k,u,f),a_{i} =a]=\] \[= \left\{ \begin{array}{ll}P[u_{i+1}=u^{\prime},f_{i+1}=f^{\prime} |k_{i}=k,u_{i}=u,f_{i}=f,a_{i}=a]&k^{\prime}=k+a\\ 0&\text{otherwise.}\end{array} \right. \tag{2}\]  
Unfortunately, the dynamics of the resource utilization and the presence of idle nodes are not fully captured by our model, as they also depend on the application workload and the adaptation actions carried on by the ACS. Therefore, a naive approach would consist in estimating the transition probabilities on-line by observing the state transition frequencies. However, since these probabilities depend on several state-action variables, the agent would need to learn a large number of parameters, possibly requiring a long transitory phase. Aiming at balancing the model accuracy and the learning velocity, we adopt an approximate probability model that relies on the following assumptions: (i) the resource utilization variations do not depend on the ICS decisions, but they depend only on the application workload changes; and (ii) the presence of an idle computing node in \(i+1\) only depends on its presence in \(i\) and the latest action \(a_{i}\). Formally, we have  
\[p(s^{\prime}|s,a)\approx\mathds{1}_{\{k^{\prime}=k+a\}}P[u_{i+1}=u^{\prime}|u_ {i}=u]P[f_{i+1}=f^{\prime}|f_{i}=f,a_{i}=a]. \tag{3}\]  
Hereafter, since \(u\) takes value in a discrete set, we will write \(P^{u}_{i,f^{\prime}}=P[u_{i+1}=f^{\prime}u|u_{i}=j\bar{u}]\), \(j,f^{\prime}\in\{0,\ldots,L_{u}\}\) for short. Let \(u^{u}_{i,j\bar{\prime}}\) be the number of times the average resource utilization changes from state \(j\bar{u}\) to \(f^{\prime}\bar{u}\), in the interval \(\{1,\ldots,i\},j,f^{\prime}\in\{1,\ldots,L_{u}\}\). At time \(i\), the transition probabilities estimates are then  
\[\widehat{P^{u_{i,j^{\prime}}}_{i,f^{\prime}}}=\frac{n^{u}_{i,j\bar{\prime}}}{ \sum_{l=0}^{L_{u}}n^{u}_{i,j\bar{l}}}.\]  
Analogously, we define the estimated transition probabilities for the variable \(f\), that is \(\widehat{P^{f}_{x,y}},x,y\in\{0,1\}\). Replacing these probabilities, we derive the estimates \(\hat{p}(s^{\prime}|s,a)\) via (3). Besides the state transition probabilities, to compute the Q-function using the Bellman equation, we need an (approximate) formulation of the cost function. To estimate the immediate cost \(c(s,a,s^{\prime})\), we first split it into two terms, that we indicate as the _known_ and the _unknown_ costs:  
\[c(s,a,s^{\prime})=c_{k}(s,a)+c_{u}(s^{\prime}). \tag{4}\]  
Comparing the expression above with Equation (1), we observe that the known cost \(c_{k}(s,a)\) accounts for the resources costs, thus it only depends on the current state and action.