# Multi-Level Elasticity for Wide-Area Data Streaming Systems: A Reinforcement Learning Approach
## 6 Infrastructure Control Policy
### Local Policy: Reinforcement Learning Scaling Policy  
Reinforcement learning approaches aim to learn the optimal strategy--in our scenario the RM scaling strategy--through experience and direct interaction with the system [14]. A RL task basically considers an _agent_ who aims to minimize a long-term _cost_. Considering a sequence of discrete time steps, which models the periodical activation of the local policy, at each step, the agent performs an _action_, looking at the current _state_ of its environment (i.e., the region). The chosen action causes the payment of an immediate cost, and the transition to a new state. Both the paid cost and the next state transition usually depend on external unknown factors as well, hence are stochastic. To minimize the expected long-term (discounted) cost, the agent keeps the estimates \(Q(s,a)\), which represent the expected long-run cost that follows the execution of action \(a\) in state \(s\). These estimates constitute the so-called Q-function, and are used by the RM to make decisions. By observing the actual incurred costs, the RM updates these estimates over time, and by so doing, also improves its policy. RL techniques are based on the assumption that the underlying system is stationary and satisfies the Markov property. Although these properties might not hold true in real systems, RL techniques have been often applied successfully in non-Markovian domains [14]. To cope with the (possible) lack of the stationary property, it is sufficient to use a constant (rather than decreasing) learning rate to let the learned policies adapt over time [14]. We define the state at the beginning of the \(i\)th time interval as the triple \(s_{i}=(k_{i},u_{i},f_{i})\), where \(k_{i}\) is the number of active computing nodes, \(u_{i}\) is the average resource utilization for the currently deployed application components, and \(f_{i}\in\{0,1\}\) signals whether an _idle_ node exists. In general, \(u_{i}\) is a vector containing the utilization of several resources (e.g., CPU, memory, and network bandwidth). For simplicity, in this work, we assume it to be a scalar value, representing the average CPU utilization for the running application replicas. Even though the average utilization is a real number taking values in \([0,1]\), for the sake of analysis, we discretize it by assuming that \(u_{i}\in\{0,\bar{u},\ldots,L_{u}\bar{u}\}\) where \(\bar{u}\) is a suitable quantum. We also assume that \(k_{i}\in\{0,\ldots,K_{max,r}\}\), where \(K_{max,r}\) depends on the total amount of resources available in region \(r\), and is statically configured. We will denote by \(\mathcal{S}\) the set of all the possible RM states. For each state \(s\in\mathcal{S}\), we have a set of scaling decisions represented by a set of actions \(\mathcal{A}(s)=\{+1,-1,0\}\), where \(a=+1\) denotes the decision of launching a new computing node, \(a=-1\) the decision of terminating one of the active nodes, and \(a=0\) is the _do nothing_ decision. Obviously, not all of the above-mentioned actions are available in those states with \(k=0\) or \(f=0\), where \(\mathcal{A}(s)=\{+1,0\}\) (there is no node that can be terminated), or with \(k=K_{max,r}\), where \(\mathcal{A}(s)=\{-1,0\}\) (we cannot add more computing nodes beyond the maximum available capacity). To each triple \((s,a,s^{\prime})\), we associate an immediate cost function \(c(s,a,s^{\prime})\), which captures the cost of carrying out action \(a\) when the system is in state \(s\) and transitions into \(s^{\prime}\). Since the ICS has a two-fold goal (i.e., satisfying the application resource demand and minimizing the resource usage), in our RL model, we consider two different costs:* \(c_{demand}\) captures a penalty paid whenever the RM cannot satisfy all the resource acquisition requests coming from the application during the next time interval. We simply consider this cost term as a constant penalty, which is paid whatever the number of the unsatisfied resource requests is (i.e., one or more).