# 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
On the other hand, the unknown cost \(c_{u}(s^{\prime})\) accounts for the unsatisfied resource demand penalty, which depends on the resource utilization and the application behavior in the next time interval (i.e., it depends on the next state \(s^{\prime}\)). Since we cannot easily formulate these dynamics, we replace \(c_{u}(s^{\prime})\) with its on-line estimate \(\hat{c}_{u}(s^{\prime})\). To this end, the agent observes the incurred cost \(c_{i}\) at the end of each time interval \(i\) and determines the \"unknown\" cost paid in the \(i\)th time slot, \(c_{u,i}\), as  
\[c_{u,i}=c_{i}-c_{k}(s,a)\]  
by simply applying Equation (4). Then, the unknown cost estimate is updated using a simple exponential weighted average:  
\[\hat{c}_{u}(s^{\prime})\leftarrow(1-\alpha)\hat{c}_{u}(s^{\prime})+\alpha c_{ u,i}. \tag{5}\]  
We must note that the cost estimation rule above does not exploit all the a priori knowledge about the system. Indeed, we can heuristically assume that the expected cost due to unsatisfied resource requests is not lower when the amount of nodes is reduced and/or the utilization increases, and it is not higher with more nodes and/or a lower utilization. Therefore, after applying Equation (5) for \(s=(k,\lambda)\), we always enforce the following constraints adjusting the estimates for states \(s^{\prime}=(k^{\prime},\lambda^{\prime})\):  
\[\hat{c}_{u,i}(s) \leq\hat{c}_{u,i}(s^{\prime}) \forall k\geq k^{\prime},u\leq u^{\prime}\] \[\hat{c}_{u,i}(s) \geq\hat{c}_{u,i}(s^{\prime}) \forall k\leq k^{\prime},u\geq u^{\prime}.\]  
The resulting Q-function update step (Line 5 of Algorithm 1) is summarized in Algorithm 2. Given the current estimates \(Q(s,a)\), at any step, the RM chooses the greedy action, that is, the action with the minimum long term estimated cost, \(\arg\min_{a\in A(s_{i})}Q(s_{i},a)\). It is worth noting that, differently from the model-free RL algorithms, with this approach we do not need a mechanism for forcing action space exploration, which is a common issue in RL solutions [14]. ```
1:Update estimates \(\widehat{P_{j,j^{\prime}}^{n_{i}}}\), \(\widehat{P_{x,y}^{f}}\) and \(\hat{c}_{u,i}(s_{i})\)
2:for all\(s\in\mathcal{S}\)do
3:for all\(a\in\mathcal{A}(s)\)do
4:\(Q(s,a)\leftarrow\sum_{s^{\prime}\in\mathcal{S}}\hat{p}(s^{\prime}|s,a)\left[ \hat{c}(s,a,s^{\prime})+\gamma\min_{a^{\prime}\in\mathcal{A}}Q(s^{\prime},a^{ \prime})\right]\)
5:endfor
6:endfor
```  
**Algorithm 2** Full backup model-based learning update. Each learning update step requires iterating over all the states, all the actions, and all the next states. Therefore, the computational complexity is \(O(|\mathcal{S}|^{2}|\mathcal{A}|)\). Given the limited amount of available actions (two or three) and the fact that many transition probabilities are equal to 0 (see Equation (2)), the complexity reduces to \(O(K_{max,r}\lceil\frac{1}{\theta}\rceil^{2})\), that is, it scales linearly with the number of resources in the region. Storing the Q function in memory requires \(O(K_{max,r}\lceil\frac{1}{\theta}\rceil)\), corresponding to \(O(|\mathcal{S}||\mathcal{A}|)\) space.