## 2 Measure and Use Differentiation in Multi-Armed Bandit
### The muMAB Model
Gain \(g\left(c_{n}\right)\) is a function of both the selected action and \(W_{k}\left(n\right)\); it is always equal to zero when _measure_ action is selected, while it is the sum of the values of the realizations of \(W_{k}\left(n\right)\) from time steps \(n\) to \(n^{\prime}=n+n_{U}\) when arm \(k\) is used at time step \(n\): \[g\left(c_{n}\right)=\left\{ \begin{array}{ll}0,&\text{if }a_{n}=m,\\ \sum\limits_{i=n}^{n+n_{U}}w_{k}\left(i\right),&\text{if }a_{n}=u;\end{array} \right.\] (3)* the performance of an algorithm is measured by the _regret_ of not always using the arm with the highest reward mean value \(k^{*}\): \[k^{*}=\operatorname*{arg\,max}_{k\in\mathcal{K}}\mu_{k};\] (4) regret at time step \(n\) is defined as: \[R\left(n\right)=G_{MAX}\left(n\right)-E\left[G\left(n\right)\right],\] (5) where: \[G\left(n\right)=\sum_{i=1}^{n}g\left(c_{i}\right),\] (6) with \(i\) used as index of time steps where an action can be taken (i.e., excluding the time steps \"occupied\" by preceding decisions: _measure_ occupies the following \(n_{M}\) time steps while _use_ occupies the following \(n_{U}\) time steps), and \(G_{MAX}\left(n\right)\) is the maximum possible cumulative gain at time step \(n\), obtained by always using the arm \(k^{*}\) (and never measuring): \[G_{MAX}\left(n\right)=E\left[G\left(n\right)\right]:c_{i}=\left(u,k^{*}\right);\] (7)
* the goal is to find an algorithm that minimizes regret evolution in time. In the muMAB model, both actions provide, as part of their feedback, the value of the current reward on the arm measured or used, and allow thus the player to use this information in order to refine the estimation of the mean value of the reward of the selected arm. The key difference between the two actions is in the time span required to collect this information: since, in fact, usually \(T_{M}<T_{U}\) in real cases, when _use_ is selected, the player will have to wait a longer time span before deciding to switch to another arm based on the collected reward values. On the other hand, if the player selects the action _use_ on a given arm, the resource is effectively exploited and there is, therefore, an immediate gain. The choice of measuring an arm, instead, permits obtaining a more accurate estimate of the performance achievable with that arm (if it will be used in future steps) in a shorter time; this comes, however, at the price of a null gain for the entire measure period, i.e., for \(T_{M}\). The muMAB model differs thus from the classical MAB model under the following aspects:  
* it introduces two actions, _measure_ and _use_, in place of the _use_ action considered in the classical model;
* as a result of each action, it provides feedback composed of two parts: the values of the rewards on the selected arm, and a gain depending on the selected action;
* it introduces the concept of _locking_ the player on an arm after it is selected for measuring or using, with different locking periods depending on the selected action (_measure_ vs. _use_). These new features make the muMAB better suited to represent real world scenarios, in which a measuring phase precedes the decision on which resource to use. It is worth noting that different wireless networks might require different measurement and use periods, depending on the characteristics of the specific network. Nevertheless, any network selection algorithm will require the adoption for each of the two parameters of a common value to all networks, since a decision on which network to select will have to be guaranteed within a finite time. In the following, the determination of the values to be adopted for \(T_{M}\) and \(T_{U}\) will be assumed to be the result of a compromise between the optimal values that would be required for each of the candidate networks.