We investigated the Sample Complexity of finding all the \(\varepsilon \) -good arms in a multi-armed bandit with Gaussian rewards. First we derived a lower bound involving a characteristic time that reflects the true hardness of the problem. Then based on a method to solve the optimization program that defines the characteristic time, we proposed a Track-and-Stop strategy whose sample complexity matches the lower bound for small values of the risk level. Finally, we showed through numerical simulations that our algorithm outperforms state-of-the-art methods for bandits with small to moderate number of arms.



Multiplicative Case
Most of the previous analysis of the additive case can be directly applied to the multiplicative case where the set of the best arms is defined as \(G_{\varepsilon }({\mu }) \triangleq \lbrace  a\in [K]:\mu _a \ge (1 - \varepsilon ) \max _{i} \mu _i \rbrace \) . The only missing pieces are the best response oracle and an upper bound on the Lipschitz constant for a mirror ascent algorithm. Solving these two problems gives us all the necessary tools to produce the multiplicative version of the algorithm presented in REF .
Best Response Oracle - Multiplicative Case
Similarly, as in the additive case, split the reasoning into two parts: making a good arm bad or making a bad arm good. This provides the following variation of Lemma 3
Lemma 7 
Define \(\lambda ^{k,\ell }_{\varepsilon }({\omega })\)  as in Definition REF  for
\(\overline{{\mu }}_{\varepsilon }^{k,\ell }({\omega })\triangleq \frac{(1-\varepsilon )^2\omega _k\mu _k + (1-\varepsilon )\omega _\ell \mu _\ell }{(1-\varepsilon )^2\omega _k + \omega _\ell }\) 
in the case of \(k\in G_{\varepsilon }({\mu })\)  and
\(\overline{{\mu }}_{\varepsilon }^{k,\ell }({\omega })\triangleq \frac{(1-\varepsilon )^2\omega _k\mu _k + \sum _{a=1}^\ell (1-\varepsilon )\omega _a\mu _a}{(1-\varepsilon )^2\omega _k + \sum _{a=1}^\ell \omega _a}\) 
in the case of \(k\in B_{\varepsilon }({\mu })\) . Then the best response \(\lambda ^*_{\varepsilon , {\mu }}({\omega })\)  to a given \({\omega }\)  is defined as:
\(\lambda ^*_{\varepsilon , {\mu }}({\omega })= \operatornamewithlimits{arg\,min}_{\lambda \in \Lambda _G\cup \Lambda _B} \sum _{a\in [K]}\omega _a\frac{(\mu _a - \lambda _a)^2}{2}.\) 
where
\(\Lambda _G = \lbrace \lambda ^{k,\ell }_{\varepsilon }({\omega }): k\in G_{\varepsilon }({\mu }), \ell \in G_{\varepsilon }({\mu })/\lbrace k\rbrace \rbrace \) 
and
\(\Lambda _B = \lbrace &\lambda ^{k,\ell }_{\varepsilon }({\omega }): k \in B_{\varepsilon }({\mu }) , \ell \in [|1,k-1|]\\ &\mathrm {s.t.}\ \mu _\ell \ge \overline{{\mu }}_{\varepsilon }^{k,\ell }({\omega })/(1-\varepsilon ) > \mu _{\ell +1}\rbrace .\) 

x
Case 1: Making one of the \(\varepsilon \) -optimal arms bad.
Selecting a good arm \(k\in G_{\varepsilon }({\mu })\)  and any other arm \(\ell \in G_{\varepsilon }({\mu })\)  we can set the expectation of arm \(k\)  to \(t\)  and the expectation of arm \(\ell \)  to \(t/(1-\varepsilon )\) . Using calculus, we can find the optimal value
\(t = \frac{(1-\varepsilon )^2\omega _k\mu _k + (1-\varepsilon )\omega _\ell \mu _\ell }{(1-\varepsilon )^2\omega _k + \omega _\ell }.\) 
Case 2: Making one of the sub-optimal arms good.
Selecting a bad arm \(k\in B_{\varepsilon }({\mu })\)  and the first \(\ell \)  arms we can set the expectation of arm \(k\)  to \(t\)  and the expectation of the first \(\ell \)  arms to \(t/(1-\varepsilon )\) . Note that \(\ell \)  is a unique integer such that \(\mu _\ell \ge t/(1-\varepsilon ) > \mu _{\ell +1}\)  thanks to the same argument as in the additive case. Using calculus, we can find the optimal value
\(t = \frac{(1-\varepsilon )^2\omega _k\mu _k + \sum _{a=1}^\ell (1-\varepsilon )\omega _a\mu _a}{(1-\varepsilon )^2\omega _k + \sum _{a=1}^\ell \omega _a}.\) 

Upper bound on the Lipschitz constant
The final ingredient is a constant \(L\)  for a mirror ascent algorithm, characterized in the following lemma.
Lemma 8 The function \({\omega }\mapsto T_{\varepsilon }({\mu },{\omega })^{-1}\)  is \(L\) -Lipschitz with respect to \(\left\Vert \,\cdot \,\right\Vert _1\)  for any
\(L\ge \max _{a,b\in [K]}\frac{(\mu _a-\mu _b(1-\varepsilon ))^2}{2(1-\varepsilon )^2}\;.\) 

Lemma REF  shows that the expectation of the selected arm \(k\)  should be in equal to
\(t = \frac{(1-\varepsilon )^2\omega _k\mu _k + \sum (1-\varepsilon )\omega _a\mu _a}{(1-\varepsilon )^2\omega _k + \sum \omega _a}\) 
where the sum is taken either over a single arm \(\ell \)  or over the first \(\ell \)  arms. In both cases we can show
\((1-\varepsilon )\mu _\mathrm {min} \le \frac{(1-\varepsilon )^2\omega _k\mu _k + \sum (1-\varepsilon )\omega _a\mu _a}{(1-\varepsilon )^2\omega _k + \sum \omega _a}\) 
using \((1-\varepsilon ) < 1\) , \(\mu _\mathrm {min} \le \mu _a\)  for any \(a\in [K]\)  and
\(\frac{(1-\varepsilon )^2\omega _k\mu _k + \sum (1-\varepsilon )\omega _a\mu _a}{(1-\varepsilon )^2\omega _k + \sum \omega _a}\le \mu _\mathrm {max}\) 
using \((1-\varepsilon ) < 1\)  and \(\mu _\mathrm {max} \ge \mu _a\)  for any \(a\in [K]\) . Using this inequality we can show that \((\mu _a - \lambda _a)^2\)  can be upper-bounded by
\(\left(\frac{\mu _\mathrm {max}}{1-\varepsilon } - \mu _\mathrm {min}\right)^2\) 
for any best response \(\lambda \) . Applying this bound to the optimization problem concludes the proof of the lemma.

Proof of Proposition 1
Let \(\delta \in (0,1)\)  be a confidence parameter and \({\mu }\)  be a bandit problem. Considering a \(\delta \) -PAC strategy, we can apply transportation Lemma 1 of [1]} to obtain
\(\sum _{a\in [K]}\frac{(\mu _a-\lambda _a)^2}{2}\mathbb {E}[N_a] \ge \operatorname{kl}(\delta ,\,1-\delta )\) 
for \(N_a \triangleq N_a(\tau _\delta )\) . This holds for any alternative problem \(\lambda \in \operatorname{Alt}({\mu })\) . Therefore, we have
\(\operatorname{kl}(\delta ,\,1-\delta ) & \le \inf _{\lambda \in \operatorname{Alt}({\mu })} \sum _{a\in [K]}\mathbb {E}[\tau _\delta ]\frac{(\mu _a-\lambda _a)^2}{2}\frac{\mathbb {E}[N_a]}{\mathbb {E}[\tau _\delta ]} \\& \le \mathbb {E}[\tau _\delta ]\sup _{{\omega }\in \Delta _K}\inf _{\lambda \in \operatorname{Alt}({\mu })} \sum _{a\in [K]}\omega _a \frac{(\mu _a-\lambda _a)^2}{2}.\) 

Fraction \(\mathbb {E}[N_a] / \mathbb {E}[\tau _\delta ]\)  represents empirical proportion of arm draws which enables us to upper-bound it by a supremum over all possible arm allocations.

Proof of Theorem 2
We start with a few technical lemmas. The first two are adapted from [2]}:
Lemma 9 (Lemma 7, [2]})
For all \(t\ge 1\) , the C-Tracking with weights \((\widetilde{{\omega }}(\widehat{{\mu }}_s))_{s\in \mathbb {N}^*}\)  ensures that \(N_a(t) \ge \sqrt{t+K^2} - 2K\)  and that
\(\max \limits _{1\le 1\le K} \bigg |N_a(t) - \sum \limits _{s=1}^t \widetilde{{\omega }}_a(\widehat{{\mu }}_s) \bigg | \le K(1+\sqrt{t})\) 

Lemma 10 (Lemma 19, [2]})
For \(\xi > 0\) , define \(I_{\xi } \triangleq [\mu _1-\xi , \mu _1+\xi ]\times \ldots [\mu _K-\xi , \mu _K+\xi ]\) . And for \(T\ge 1\) , consider the event: \(\mathcal {E}_T = \bigcap \limits _{t = {T^{1/4}}}^T \big (\widehat{{\mu }}_t \in I_{\xi } \big )\) . Then there exists two constants \(B, C\)  that only depend on \({\mu }\)  and \(\xi \)  such that
\(\mathbb {P}\big (\mathcal {E}_T^c\big ) \le B T \exp (-C T^{1/8})\) 

where \(\mathcal {E}_T^c\)  is the complementary event of \(\mathcal {E}_T\) .

The last lemma states that \({\mu }\mapsto T_{\varepsilon }({\mu }, {\omega })^{-1}\)  is Lipschitz. Its proof is deferred to the end.
Lemma 11 For all vectors \({\omega }\)  in the simplex, for all instances \({\mu }\) , \({\mu }^{\prime }\)  in \([\mu _{min}, \mu _{max}]^K\)  we have:
\(|T_{\varepsilon }({\mu }^{\prime }, {\omega })^{-1} - T_{\varepsilon }({\mu }, {\omega })^{-1} |\le 4(\mu _{max} - \mu _{min}+\varepsilon ) \left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }.\) 

Now we are ready to prove the Theorem. We denote by \(L_1([\mu _{min}, \mu _{max}]^K) \triangleq 4(\mu _{max} - \mu _{min}+\varepsilon )\)  the Lipschitz constant of the mapping \({\mu }\mapsto T_{\varepsilon }({\mu }, {\omega })^{-1}\)  in the domain \([\mu _{min}, \mu _{max}]^K\)  and by \(L_2({\mu }) \triangleq \max _{a,b\in [K]}\frac{(\mu _a-\mu _b + \varepsilon )^2}{2}\)  the Lipschitz constant of the mapping \({\omega }\mapsto T_{\varepsilon }({\mu }, {\omega })^{-1}\) .
We will prove a lower bound on \(T_\varepsilon \bigg (\widehat{{\mu }}_t, \frac{N(t)}{t}\bigg )^{-1}\)  under \(\mathcal {E}_T\)  which will result into an upper bound on the stopping time \(\tau _\delta = \inf \big \lbrace  t \in \mathbb {N}\ :\ t T_\varepsilon \big (\widehat{{\mu }}_t, \frac{N(t)}{t} \big )^{-1} \ge \beta (\delta ,t) \big \rbrace \) .
First observe that under \(\mathcal {E}_T\) , the \(L_1\)  constant is upper bounded: \(L_1(I_{\xi }) \le L_{1,max} \triangleq 4(\max _a \mu _a - \min _b \mu _b + \varepsilon + 2\xi )\) . Similarly, we have for all \({T^{1/4}} \le t \le T,\ L_2(\widehat{{\mu }}_t) \le L_{2, max} \triangleq \frac{(\max _a \mu _a - \min _b \mu _b + 2\xi + \varepsilon )^2}{2}\) .
Now applying Lemma 7 and the Lipschitz property w.r.t the weights, we have for all \({T^{1/4}} \le t \le T\) :
\(T_\varepsilon \bigg (\widehat{{\mu }}_t, \frac{N(t)}{t}\bigg )^{-1} &\ge T_\varepsilon \bigg (\widehat{{\mu }}_t, \frac{\sum \limits _{s=1}^t \widetilde{{\omega }}(\widehat{{\mu }}_s)}{t}\bigg )^{-1} - L_{2,max}\frac{K(1+\sqrt{t})}{t}\\&\ge \frac{\sum \limits _{s=1}^t T_\varepsilon \big (\widehat{{\mu }}_t, \widetilde{{\omega }}(\widehat{{\mu }}_s)\big )^{-1}}{t} - L_{2,max}\frac{K(1+\sqrt{t})}{t}\\&\ge \frac{\sum \limits _{s={T^{1/4}}}^t T_\varepsilon \big (\widehat{{\mu }}_t, \widetilde{{\omega }}(\widehat{{\mu }}_s)\big )^{-1}}{t} - L_{2,max}\frac{K(1+\sqrt{t})}{t}\\\) 

Where we used the fact that the mapping \({\omega }\mapsto T_{\varepsilon }({\mu }, {\omega })^{-1}\)  is concave (resp. non-negative) in the second (resp. last) inequality. Now observe that for all \(s,t \ge {T^{1/4}},\ \left\Vert \widehat{{\mu }}_t - \widehat{{\mu }}_s\right\Vert _{\infty } \le 2\xi \) . Therefore the Lipschitz property w.r.t \({\mu }\)  implies that:
\(T_\varepsilon \bigg (\widehat{{\mu }}_t, \frac{N(t)}{t}\bigg )^{-1} &\ge \frac{\sum \limits _{s={T^{1/4}}}^t T_\varepsilon \big (\widehat{{\mu }}_s, \widetilde{{\omega }}(\widehat{{\mu }}_s)\big )^{-1}}{t} - \frac{2\xi L_{1,max}(t-{T^{1/4}})}{t}- L_{2,max}\frac{K(1+\sqrt{t})}{t} \nonumber \\&\ge \frac{\sum \limits _{s={T^{1/4}}}^t T_\varepsilon ^*\big (\widehat{{\mu }}_s\big )^{-1}}{t} - \frac{\sum \limits _{s={T^{1/4}}}^t \frac{1}{\sqrt{s}}}{t} -2\xi L_{1,max}- L_{2,max}\frac{K(1+\sqrt{t})}{t}\) 

where in the second inequality we used the fact that by definition \(\widetilde{{\omega }}(\widehat{{\mu }}_s)\)  is at most \(\frac{1}{\sqrt{s}}\)  sub-optimal. Now observe that:
\(& T_\varepsilon ^*\big (\widehat{{\mu }}_s\big )^{-1} \underset{s\rightarrow \infty }{\longrightarrow } T_\varepsilon ^*\big ({\mu }\big )^{-1}\quad \textrm {almost surely (since N_a(t) \ge \sqrt{t+K^2} - 2K)}.\\& \frac{\sum \limits _{s={T^{1/4}}}^t \frac{1}{\sqrt{s}}}{t} \underset{t\rightarrow \infty }{\sim } \frac{\int _{1}^{t} \frac{dx}{\sqrt{x}}}{t} \longrightarrow 0.\\& \frac{K(1+\sqrt{t})}{t} \longrightarrow 0.\) 

Therefore for \(\eta > 0\) , there exists \(t_\eta \)  such that for all \(t\ge t_\eta \) :
\(\frac{\sum \limits _{s={T^{1/4}}}^t T_\varepsilon ^*\big (\widehat{{\mu }}_s\big )^{-1}}{t} - \frac{\sum \limits _{s={T^{1/4}}}^t \frac{1}{\sqrt{s}}}{t} -L_{2,max}\frac{K(1+\sqrt{t})}{t} \ge T_\varepsilon ^*\big ({\mu }\big )^{-1} - \eta .\) 

Summing up (REF ) and (REF ), we get for all \(t\ge t_\eta \) :
\(T_\varepsilon \bigg (\widehat{{\mu }}_t, \frac{N(t)}{t}\bigg )^{-1} \ge T_\varepsilon ^*\big ({\mu }\big )^{-1} -2\xi L_{1,max} - \eta .\) 

Therefore for every \( T \ge \max \bigg (t_\eta , \frac{\beta (\delta ,t)}{T_\varepsilon ^*\big ({\mu }\big )^{-1} -2\xi L_{1,max} - \eta }\bigg )\) , we have \(\mathcal {E}_T \subset (\tau _\delta \le T)\)  thus \(\mathbb {P}(\tau _\delta > T) \le \mathbb {P}\big (\mathcal {E}_T^c\big ) \le B T \exp (-C T^{1/8})\) . Hence:
\(\mathbb {E}[\tau _\delta ] &= \sum \limits _{T=1}^{\infty } \mathbb {P}(\tau _\delta > T)\\&\le \max \bigg (t_\eta , \frac{\beta (\delta ,t)}{T_\varepsilon ^*\big ({\mu }\big )^{-1} -2\xi L_{1,max} - \eta }\bigg ) + \sum \limits _{T=1}^{\infty } B T \exp (-C T^{1/8})\) 

Since \(\lim \limits _{\delta \rightarrow 0} \frac{\beta (\delta ,t)}{\log (1/\delta )} = 1\)  the last inequality implies that \(\limsup \limits _{\delta \rightarrow 0} \frac{\mathbb {E}[\tau _\delta ]}{\log (1/\delta )} \le \frac{1}{T_\varepsilon ^*\big ({\mu }\big )^{-1} -2\xi L_{1,max} - \eta }\) . We conclude by letting \(\eta \)  and \(\xi \)  go to zero.
Proof of Lemma  REF
First case: arms in \({\mu }\)  and \({\mu }^{\prime }\)  have the same order
Without loss of generality, suppose that \(\mu _1 \ge \mu _2 \ge \ldots \ge \mu _K\)  and \(\mu ^{\prime }_1 \ge \mu ^{\prime }_2 \ge \ldots \ge \mu ^{\prime }_K\) .
Then we see that for all \(k \ne l \in [K], \overline{{\mu }}_{\varepsilon }^{k,\ell }({\omega })\)  and \(\overline{{\mu }^{\prime }}_{\varepsilon }^{k,\ell }({\omega })\)  have the same formula and : \(|\overline{{\mu }^{\prime }}_{\varepsilon }^{k,\ell }({\omega })- \overline{{\mu }}_{\varepsilon }^{k,\ell }({\omega })| \le \left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }\) , which implies that \(|\lambda ^{\prime k,\ell }_{\varepsilon }({\omega })- \lambda ^{k,\ell }_{\varepsilon }({\omega })| \le \left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }\) . Therefore, letting \(f\)  denote the function \(f({\mu },\lambda ) \triangleq \sum _{a\in [K]}\omega _a \frac{(\mu _a - \lambda _a)^2}{2}\) , we have:
\(|f({\mu }^{\prime },\lambda ^{\prime k,\ell }_{\varepsilon }({\omega })) - f({\mu },\lambda ^{k,\ell }_{\varepsilon }({\omega }))| &\le \sum _{a\in [K]}\frac{\omega _a(\mu ^{\prime }_a - \mu _a + \lambda ^{k,\ell }_{\varepsilon }({\omega })_a - \lambda ^{\prime k,\ell }_{\varepsilon }({\omega })_a)(\mu ^{\prime }_a + \mu _a - \lambda ^{k,\ell }_{\varepsilon }({\omega })_a - \lambda ^{\prime k,\ell }_{\varepsilon }({\omega })_a)}{2}\\&\le \frac{\omega _a \times 2\left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty } \times 2(\mu _{max} - \mu _{min}+\varepsilon )}{2}\\& = 2(\mu _{max} - \mu _{min}+\varepsilon )\left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }.\) 

where in the second inequality we used the fact that \(\lambda ^{k,\ell }_{\varepsilon }({\omega })\)  (resp. \(\lambda ^{\prime k,\ell }_{\varepsilon }({\omega })\) ) is a weighted average of some arm in \({\mu }\) (resp. \({\mu }^{\prime }\) ) with one or more arms of \({\mu }\) (resp. \({\mu }^{\prime }\) ) decreased by \(\varepsilon \)  and therefore lies in \([\mu _{min}-\varepsilon , \mu _{max}]^K\) . Let \((k_0, l_0)\)  be such that \(\lambda ^*_{\varepsilon , {\mu }}({\omega })= \lambda ^{k_0,l_0}_{\varepsilon }({\omega })\)  then:
\(T_{\varepsilon }({\mu }^{\prime }, {\omega })^{-1} - T_{\varepsilon }({\mu }, {\omega })^{-1} &= T_{\varepsilon }({\mu }^{\prime }, {\omega })^{-1} - f\big (\omega , \lambda ^{k_0, l_0}_{\varepsilon }({\omega })\big ) \\&\le f\big (\omega ,\lambda ^{\prime k_0, l_0}_{\varepsilon }({\omega })\big ) - f\big (\omega , \lambda ^{k_0, l_0}_{\varepsilon }({\omega })\big ) \\&\le 2(\mu _{max} - \mu _{min}+\varepsilon )\left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }.\) 

By symmetry we get for all instances \({\mu }\)  and \({\mu }^{\prime }\)  with the same arm ordering:
\(|T_{\varepsilon }({\mu }^{\prime }, {\omega })^{-1} - T_{\varepsilon }({\mu }, {\omega })^{-1}| \le 2(\mu _{max} - \mu _{min}+\varepsilon )\left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }.\) 

Second case: arms in \({\mu }\)  and \({\mu }^{\prime }\)  have a different order
Then for \(n\)  large enough we can find a sequence \((\mu ^i)_{0\le i \le 2^n}\)  of instances in the segment \([{\mu }, {\mu }^{\prime }]\)  such that \(\mu ^0 = {\mu }\) , \(\mu ^{2^n} = {\mu }^{\prime }\)  and:
\(\forall i \in [|0, 2^n-1|],\ \mu ^i \textrm { and } \mu ^{i+1} \textrm { have the same arm ordering and } \left\Vert \mu ^{i+1} - \mu ^{i}\right\Vert _{\infty } \le \frac{\left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }}{2^{n-1}}.\) 
We can construct such a sequence in the following way: Split \([\mu _{min}, \mu _{max}]^K\)  into \(K!\)  regions such that any two instances in the same region share the same arm ordering. The boundaries between these regions correspond to instances where two or more arms are equal. Starting from \(\mu ^0 \triangleq {\mu }\) , span the segment \([{\mu }, {\mu }^{\prime }]\)  and define \(\mu ^{i+1}\)  to be the first instance where: either the \(L^\infty \)  distance from \(\mu ^i\)  is equal to \(\frac{\left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }}{2^{n-1}}\) , or we cross a boundary between two regions. Since there can be at most \(K! - 1\)  changes in the arm ordering, for \(n\)  large enough such sequence always exists. Now we have:
\(|T_{\varepsilon }({\mu }^{\prime }, {\omega })^{-1} - T_{\varepsilon }({\mu }, {\omega })^{-1}| &\le \sum \limits _{i=0}^{2^n - 1} |T_{\varepsilon }({\omega }, {\mu }^{i+1})^{-1} - T_{\varepsilon }({\omega }, {\mu }^i)^{-1}| \\&\le \sum \limits _{i=0}^{2^n - 1} 2(\mu _{max} - \mu _{min}+\varepsilon ) \frac{\left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }}{2^{n-1}}\\&\le 4(\mu _{max} - \mu _{min}+\varepsilon )\left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }.\) 

where in the second inequality we use the first case and the fact that \(\mu ^i\)  and \(\mu ^{i+1}\)  have the same arm ordering. As a summary, we always have:
\(|T_{\varepsilon }({\mu }^{\prime }, {\omega })^{-1} - T_{\varepsilon }({\mu }, {\omega })^{-1} |\le 4(\mu _{max} - \mu _{min}+\varepsilon ) \left\Vert {\mu }^{\prime } - {\mu }\right\Vert _{\infty }.\) 
