## 2 Measure and Use Differentiation in Multi-Armed Bandit  
### The muMAB Model  
The classical MAB model foresees different arms, each of them characterised by a reward, modeled by a random variable with a fixed (unknown) mean value. At every step, an arm is selected and its current reward value is obtained as feedback. Many algorithms, also called strategies or policies, were proposed in literature in order to identify and choose as soon as possible the arm with the highest mean reward without any a priori knowledge, except for the number of arms [16; 17]. Their performance is usually expressed in terms of regret, which is the difference between the cumulative reward obtained by always choosing the arm with the highest mean and the cumulative reward actually obtained with the chosen arms. Regret was first proposed as evaluation parameter for algorithms performance in [20]; it was later shown that, in terms of regret, the best performance an algorithm can achieve is a regret that grows logarithmically over time [16]. In the classical MAB model, there is only one possible action: to select an arm and collect the corresponding reward. In real world scenarios, however, such as the best wireless network selection considered in this work, the selection phase is preceded by a measurement phase, in order to support an informed decision. Furthermore, the selection is usually kept unchanged for a significant time, typically much longer than the time dedicated to measuring the performance of the candidate networks. This is due to the overhead introduced by a network switching procedure, as well as to the discomfort caused to the user due to service interruption during network switch; indeed, a significant effort was devoted to designing algorithms that prevent frequent network switching procedures [21]. The muMAB model is designed so to grasp the cycle between measuring and using, and thus model real scenarios with higher accuracy than the classical MAB model. The muMAB model can be described as follows:  
* time is divided into steps with a duration of \(T\), and the time horizon is defined as \(T_{TH}=n_{TH}T\);
* there are 1 player and \(\mathcal{K}\) arms;
* a reward is associated with the generic \(k\)-th arm, \(k=\left\{1,\cdots,\mathcal{K}\right\}\); \(\forall k\in\mathcal{K}\), the reward \(\left\{W_{k}(n):n\in N\right\}\) is a stationary ergodic random process associated with arm \(k\), with statistics not known a priori; given a time step \(n\), \(W_{k}(n)\) is thus a random variable taking values in the real non-negative numbers set \(\Re^{+}\), with unknown Probability Density Function (PDF); the mean value of \(W_{k}(n)\) is defined as \(\mu_{k}=E\left[W_{k}(n)\right]\);
* there are two distinct actions: to _measure_ (\"\(m\)\") and to _use_ (\"\(u\)\"). At the beginning of time step \(n\), the player can choose to apply action \(a\) to arm \(k\); the choice \(c_{n}\) is represented by a pair: \[c_{n}=\left(a_{n},k_{n}\right),a_{n}\in\left\{m,u\right\},k_{n}\in\mathcal{K},\] (1) which means that, at time step \(n\), the arm \(k_{n}\) has been chosen with an action \(a_{n}\); every choice \(c_{n}\) obtains feedback \(f\left(c_{n}\right)\);
* feedback \(f\left(c_{n}\right)\) is a pair, composed by: 1. a realization of \(W_{k}\left(n\right)\) at time step \(n\), \(w_{k}\left(n\right)\), that is the current reward value associated with arm \(k\);
2. a gain \(g\left(c_{n}\right)\); therefore: \[f\left(c_{n}\right)=\left(w_{k}\left(n\right),g\left(c_{n}\right)\right);\] (2)
* _measure_ and _use_ actions have duration \(T_{M}\) and \(T_{U}\), respectively, defined as \(T_{M}=n_{M}T\), \(T_{U}=n_{U}T\), where \(n_{M}\), \(n_{U}\in N\). As a result, if at time step \(n\) the player chooses action _measure_ (_use_, respectively), i.e., \(a_{n}=m\left(a_{n}=u\right)\), the next \(n_{M}\left(n_{U}\right)\) steps are \"occupied\" and the next choice can be taken at time step \(n^{\prime}=n+n_{M}\left(n^{\prime}=n+n_{U}\right)\).