## 2 Measure and Use Differentiation in Multi-Armed Bandit
### Algorithms
#### 2.2.2 Mli  
MLI is an algorithm designed from scratch to fully exploit the new muMAB model. It is divided in two phases, identified as Phase 1 and Phase 2. Phase 1 is completely dedicated to collecting measurements, with the goal of building up a \"reliable enough\" estimate for each arm's reward mean value. Every arm \(k\) is measured \(d_{1}^{k}\) times according to a round robin scheduling. The duration of Phase 1 is, therefore, equal to:  
\[T_{PH1}=\sum_{k=1}^{K}d_{1}^{k}T_{M}, \tag{9}\]  
and the estimate of the reward for each arm is set to the average of the \(d_{1}^{k}T_{M}\) realizations of \(W_{k}\left(n\right)\) obtained for that arm. Since during  
support effective arm selection during Phase 2. If the first measurements show that arms reward mean values are significantly different among them, a low value for \(d_{1}\) could be selected in order to keep \(T_{PH1}\) as short as possible. As an alternative, each arm \(k\) can be measured a different number of times, e.g. spending more measuring actions on arms for which the variance of the measurements is higher, while interrupting sooner the measurements for arms showing a low variance in rewards. ```
Initialization:Measure each arm once and compute estimates \(\hat{\mu}_{k}\)
1 while\(n<n_{TH}\)do
2 for\(k=1,\cdots,K\)do
3 compute index \(l_{k}\) for each arm;
4 if\(k_{IND}==k_{EST}\)then
5\(\{use\}\);
6\(c_{n}\leftarrow(u,k_{IND})\);
7\(g\left(c_{n}\right)\leftarrow\sum_{i=i}^{n+n_{ID}}w_{k_{IND}}\left(i\right)\);
8\(f\left(c_{n}\right)\leftarrow\left(w_{k_{IND}}\left(n\right),g\left(c_{n} \right)\right)\);
9 update the estimate \(\hat{\mu}_{k_{IND}}\);
10\(n\gets n+n_{UI}\);
11
12 else
13\(\{measure\}\);
14\(c_{n}\leftarrow(m,k_{IND})\);
15\(g\left(c_{n}\right)\gets 0\);
16\(f\left(c_{n}\right)\leftarrow\left(w_{k_{IND}}\left(n\right),g\left(c_{n} \right)\right)\);
17 update the estimate \(\hat{\mu}_{k_{IND}}\);
18\(n\gets n+n_{M}\);
19
20 end if
21
22 end for
23
24 end for
```  
**Algorithm 1**muUCB1. Phase 2 of the MLI algorithm is mostly dedicated to \(use\) actions, with the exception of sporadic _measure_ actions, as explained in the following. Based on estimates built up during Phase 1, the algorithm starts exploiting the resource by using the arm with the highest estimated reward mean value, obtaining as feedback a gain and a reward realization, which is used to update the arm's reward estimate. Periodic _measure_ actions are, however, performed in order to update the estimates of the mean values of the rewards for the other arms. The first measure is performed after \(d_{2}\) use actions; the interval between two consecutive measures grows then logarithmically over time. In particular, arms are measured at time steps \(n_{i}\) such that  
\[n_{i}=\lceil n_{i-1}+\ln\left(n_{i-1}\right)\rceil, \tag{10}\]  
with:  
\[i\geq 1,\quad n_{0}=d_{2}n_{UI}>1. \tag{11}\]  
The arm chosen for being measured is the one whose reward estimate is based on the lowest number of values. This can later be changed, by choosing to measure the arm with the \"oldest\" updated estimate, the one with the second highest estimate (since it can be the most critical value) or a combination of these three solutions. In all the other time steps, the arm with the current highest reward estimate is always used. The pseudo code of the algorithm is reported in Algorithm 2, assuming for simplicity to adopt the approach \(d_{1}^{k}=d_{1}\,\forall k\).