Let $i \in [D]$ and consider $t \in [N_i, N_{i+1})$. For all $x$,

$$f_{N_i, \gamma}(x) \geq \sqrt{\frac{N_i}{t}} f_{t, \gamma}(x) \geq \frac{1}{\sqrt{1+\eta}} f_{t, \gamma}(x)$$

Direct computations shows that

$$\int f_{t,\gamma}(x) \exp \left( xS_t - \frac{1}{2}x^2t \right) dx = \frac{1}{\sqrt{1+\gamma^{-1}}} \exp \left( \frac{S_t^2}{2(1+\gamma)t} \right).$$

Minoring $\overline{M}(t)$ by one of the positive term of its sum, we obtain

$$\overline{M}(t) \geq \frac{1}{D} \frac{1}{\sqrt{(1+\gamma^{-1})(1+\eta)}} \exp \left( \frac{S_t^2}{2(1+\gamma)t} \right),$$

Using Ville's maximal inequality for non-negative supermartingale, we have that with probability greater than $1 - \delta$, $\log \overline{M}(t) \leq \log (1/\delta)$. Therefore, with probability greater than $1 - \delta$, for all $i \in [D]$ and $t \in [N_i, N_{i+1})$,

$$\frac{S_t^2}{t} \leq (1 + \gamma) (2 \log (1/\delta) + 2 \log D + \log(1 + \gamma^{-1}) + \log(1 + \eta)).$$

Since this upper bound is independent of $t$, we can optimize it and choose $\gamma$ as in Lemma 43.

**Lemma 43** (Lemma A.3 in [9]). For $a, b \geq 1$, the minimal value of $f(\eta) = (1+\eta)(a+\log(b+\frac{1}{\eta}))$ is attained at $\eta^*$ such that $f(\eta^*) \leq 1 - b + \overline{W}_{-1}(a+b)$. If $b=1$, then there is equality.

Therefore, with probability greater than $1 - \delta$, for all $i \in [D]$ and $t \in [N_i, N_{i+1})$,

$$\begin{aligned} \frac{S_t^2}{t} &\leq \overline{W}_{-1}(1 + 2 \log (1/\delta) + 2 \log D + \log(1 + \eta)) \\ &\leq \overline{W}_{-1}(1 + 2 \log (1/\delta) + 2 \log (\log(1 + \eta) + \log n) - 2 \log \log(1 + \eta) + \log(1 + \eta)) \\ &= \overline{W}_{-1}(2 \log (1/\delta) + 2 \log (2 + \log n) + 3 - 2 \log 2) \end{aligned}$$

The second inequality is obtained since $D \leq 1 + \frac{\log n}{\log(1+\eta)}$. The last equality is obtained for the choice $\eta^* = e^2 - 1$, which minimizes $\eta \mapsto \log(1+\eta) - 2\log(\log(1+\eta))$. Since $[n] \subseteq \cup_{i \in [D]} [N_i, N_{i+1})$ and $N_{t,k}(\mu_{t,k} - \mu_k) = \sum_{s \in [N_{t,k}]} X_{s,k}$ (unit-variance), this yields

$$\mathbb{P} \left( \exists m \le n, \left| \frac{1}{m} \sum_{s=1}^{m} X_s \right| \ge \sqrt{\frac{1}{m} \overline{W}_{-1} (2 \log(1/\delta) + 2 \log(2+\log(n)) + 3 - 2 \log 2)} \right) \le \delta.$$

Since $3 - 2 \log 2 \leq 2$ and $\overline{W}_{-1}$ is increasing, taking $\delta n^{-s}$ yields

$$\mathbb{P}_{\nu} \left( \exists t \le n, \sqrt{N_{t,k}} |\mu_{t,k} - \mu_k| \ge \sqrt{2 \tilde{f}_1(n, \delta)} \right) \le \delta n^{-s}.$$

Doing a union bound over arms yields the result. $\square$

Lemma 44 provides concentration results on the empirical gaps, which are tighter than the ones obtained in Lemma 41.

**Lemma 44.** Let $\delta \in (0, 1]$ and $s \geq 0$. Let $\overline{W}_{-1}$ defined in Lemma 49. For all $n > K$, let

$$\tilde{f}_2(n, \delta) = \overline{W}_{-1} \left( \log \left( \frac{1}{\delta} \right) + s \log n + 2 \log \left( 2 + \log n \right) + 2 \right), \quad (28)$$

and

$$\tilde{\mathcal{E}}_{n, \delta}^2 := \left\{ \forall (i, k) \in [K]^2 \text{ s.t. } i \neq k, \forall t \le n, \frac{|(\mu_{t,i} - \mu_{t,k}) - (\mu_i - \mu_k)|}{\sqrt{1/N_{t,i} + 1/N_{t,k}}} < \sqrt{2\tilde{f}_2(n, \delta)} \right\}. \quad (29)$$

Then, for all $n > K$, $\mathbb{P}_{\nu}((\tilde{\mathcal{E}}_{n,\delta}^2)^c) \le \frac{K(K-1)}{2} \frac{\delta}{n^s}$.
*Proof.* Without loss of generality, we show the result for arms $(i, k) = (1, 2)$. Let $(X_s)_{s \in [n]}$ and $(Y_s)_{s \in [n]}$ be i.i.d. observations from two sub-Gaussian distribution with mean 0 and variance proxy $\sigma^2 = 1$. Let $S_{t,k} = \sum_{s \in [t]} 1(I_s = k) X_s$ for all $k \in \{1, 2\}$. To derived concentration result, we use peeling as in Lemma 42.

Let $\eta > 0, \gamma > 0$ and $D = \lceil \frac{\log(n)}{\log(1+\eta)} \rceil$. For all $i \in [D]$, let $N_i = (1+\eta)^{i-1}$. For all $i \in [D]$, we define the family of priors $f_{N_i, \gamma}(x) = \sqrt{\frac{\gamma N_i}{2\pi}} \exp\left(-\frac{x^2\gamma N_i}{2}\right)$ with weights $w_i = \frac{1}{D}$ and process

$$ \forall k \in \{1, 2\}, \quad \bar{M}_k(t) = \sum_{i \in [D]} w_i \int f_{N_i, \gamma}(x) \exp \left( xS_{t,k} - \frac{1}{2}x^2 N_{t,k} \right) dx, $$

which satisfies $\bar{M}_k(0) = 1$ for all $k \in \{1, 2\}$. As in the proof of Lemma 42, we obtain that $\bar{M}_1(t)$ and $\bar{M}_2(t)$ are non-negative supermartingale such that

$$ \forall k \in \{1, 2\}, \quad \bar{M}_k(t) \ge \frac{1}{D} \frac{1}{\sqrt{(1+\gamma^{-1})(1+\eta)}} \exp \left( \frac{S_{t,k}^2}{2(1+\gamma)N_{t,k}} \right). $$

where we used $(i_1, i_2) \in [D]^2$ and consider $N_{t,k} \in [N_{i_k}, N_{i_{k+1}})$ for all $k \in \{1, 2\}$. Let us define $\bar{M}(t) = \bar{M}_1(t_1)\bar{M}_2(t_2)$. Then, we have that $\bar{M}(t)$ is a non-negative supermartingale such that

$$ \bar{M}(t) \ge \frac{1}{D^2 (1 + \gamma^{-1})(1 + \eta)} \exp \left( \frac{1}{2(1 + \gamma)} \sum_{k \in \{1, 2\}} \frac{S_{t,k}^2}{N_{t,k}} \right) $$

Using Ville's maximal inequality for non-negative supermartingale, we have that with probability greater than $1 - \delta$, $\log \bar{M}(t) \le \log (1/\delta)$. Therefore, with probability greater than $1 - \delta$, for all $(i_1, i_2) \in [D]^2$ and $N_{t,k} \in [N_{i_k}, N_{i_{k+1}})$ for all $k \in \{1, 2\}$,

$$ \sum_{k \in \{1, 2\}} \frac{S_{t,k}^2}{N_{t,k}} \le 2(1 + \gamma) \left( \log(1/\delta) + 2 \log D + \log(1 + \gamma^{-1}) + \log(1 + \eta) \right). $$

Since this upper bound is independent of $t$, we can optimize it and choose $\gamma$ as in Lemma 43.

Therefore, with probability greater than $1 - \delta$, for all $(i_1, i_2) \in [D]^2$ and $N_{t,k} \in [N_{i_k}, N_{i_{k+1}})$ for all $k \in \{1, 2\}$,

$$ \sum_{k \in \{1, 2\}} \frac{S_{t,k}^2}{N_{t,k}} \le 2\bar{W}_{-1} (\log (1/\delta) + 2 \log D + \log(1 + \eta) + 1) \\ \le 2\bar{W}_{-1} (\log (1/\delta) + 2 \log (2 + \log n) + 2) $$

The second inequality is obtained as in Lemma 42 by using that $D \le 1 + \frac{\log n}{\log(1+\eta)}$, $\bar{W}_{-1}$ increasing, taking $\eta^* = e^2 - 1$ and using $3 - 2 \log 2 \le 2$.

Since $[n] \subseteq \bigcup_{i \in [D]} [N_i, N_{i+1})$, $N_{t,k} \le n$ and $N_{t,k}(\mu_{t,k} - \mu_k) = S_{t,k}$ (unit-variance), this yields

$$ \mathbb{P} \left( \exists t \le n, \sum_{k \in \{1, 2\}} \frac{N_{t,k}}{2} (\mu_{t,k} - \mu_k)^2 \ge \bar{W}_{-1} (\log (1/\delta) + 2 \log (2 + \log n) + 2) \right) \le \delta. $$

Let $C(n, \delta) := \bar{W}_{-1} (\log (1/\delta) + 2 \log (2 + \log n) + 2)$. In the following, we consider that we are under the event,

$$ \mathcal{E}_{n, \delta}(1, 2) := \left\{ \forall t \le n, \sum_{k \in \{1, 2\}} \frac{N_{t,k}}{2} (\mu_{t,k} - \mu_k)^2 < C(n, \delta) \right\}, $$

which has probability at least $1 - \delta$. Since it satisfies the above constraint, the quantity $\mu_{t,1} - \mu_1 - (\mu_{t,2} - \mu_2)$ is upper bounded by

$$ \max_{x \in \mathbb{R}^2} \{\mu_{t,1} - \mu_{t,2} - x_1 + x_2\} \quad \text{subject to} \quad \sum_{k \in \{1, 2\}} \frac{N_{t,1}}{2} (\mu_{t,k} - x_k)^2 \le C(n, \delta). $$
Introducing a Lagrange multiplier $\alpha$, the above optimization problem is equivalent to

$$ \min_{\alpha \ge 0} \max_{x \in \mathbb{R}^2} \left\{ \mu_{t,1} - \mu_{t,2} - x_1 + x_2 + \alpha \left( C(n, \delta) - \sum_{k \in \{1,2\}} \frac{N_{t,k}}{2} (\mu_{t,k} - x_k)^2 \right) \right\}. $$

Solving for $x$ by cancelling the derivative yields that $x_1 = \mu_{t,1} - \frac{1}{\alpha N_{t,1}}$ and $x_2 = \mu_{t,2} + \frac{1}{\alpha N_{t,2}}$. Therefore, we obtain as solution

$$ \min_{\alpha \ge 0} \left\{ \alpha C(n, \delta) + \frac{1}{2\alpha} \sum_{k \in \{1,2\}} \frac{1}{N_{t,k}} \right\} = \sqrt{2C(n, \delta) \sum_{k \in \{1,2\}} \frac{1}{N_{t,k}}}, $$

where the last equality is obtained by solving the optimization since the derivative is null at $\alpha^* = \sqrt{\sum_{k \in \{1,2\}} \frac{1}{2C(n,\delta)N_{t,k}}}$. By symmetry, we obtain the same result to upper bound $\mu_{t,2} - \mu_2 - (\mu_{t,1} - \mu_1)$. Therefore, under $\mathcal{E}_{n,\delta}(1,2)$, we have shown that

$$ \frac{|\mu_{t,1} - \mu_1 - (\mu_{t,2} - \mu_2)|}{1/N_{t,1} + 1/N_{t,2}} \le \sqrt{2\bar{W}_{-1}(\log(1/\delta) + 2\log(2+\log n) + 2)} $$

The same argument as above can be applied for all $(i, k) \in [K]^2$ such that $i \neq k$. A direct union bound yields

$$ \mathbb{P}_{\nu}((\tilde{\mathcal{E}}_{n,\delta}^2)^{\mathcal{C}}) \le \sum_{(i,k) \in [K]^2, i \ne k} \mathbb{P}_{\nu}(\mathcal{E}_{n,\delta n^{-s}}(i,k)^{\mathcal{C}}) \le \frac{K(K-1)}{2} \frac{\delta}{n^s}, $$

where we used the inclusion proven above for $(n, \delta/n^s)$. This concludes the proof. $\square$

**Global events** Lemma 45 combines the above sequences of concentration events.

**Lemma 45.** Let $s > 1$. Let $(\mathcal{E}_{n,\delta}^1)_{n>K}$ and $(\mathcal{E}_{n,\delta}^2)_{n>K}$ as in (24) and (25). Let $(\tilde{\mathcal{E}}_{n,\delta}^1)_{n>K}$ and $(\tilde{\mathcal{E}}_{n,\delta}^2)_{n>K}$ as in (27) and (29). Let us define $\mathcal{E}_{n,\delta} := \mathcal{E}_{n,\delta}^1 \cap \mathcal{E}_{n,\delta}^2$ and $\tilde{\mathcal{E}}_{n,\delta} := \tilde{\mathcal{E}}_{n,\delta}^1 \cap \tilde{\mathcal{E}}_{n,\delta}^2$ for all $n>K$. Then,

$$ \sum_{n>K} \mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^{\mathcal{C}}) \le \frac{K(K+1)}{2} \zeta(s)\delta \quad \text{and} \quad \sum_{n>K} \mathbb{P}_{\nu}(\tilde{\mathcal{E}}_{n,\delta}^{\mathcal{C}}) \le \frac{K(K+1)}{2} \zeta(s)\delta. $$

*Proof.* It is direct to see that

$$ \sum_{n>K} \mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^{\mathcal{C}}) \le \sum_{n>K} \frac{K\delta}{n^s} + \sum_{n>K} \frac{K(K-1)\delta}{2n^s} = \frac{K(K+1)}{2} \zeta(s)\delta. $$

The same proof can be applied to upper bound $\sum_{n>K} \mathbb{P}_{\nu}(\tilde{\mathcal{E}}_{n,\delta}^{\mathcal{C}})$. $\square$

## H Technicalities

Appendix H gathers existing and new technical results which are used for our proofs.

**Key technical result** Lemma 4 is the key technical ingredient on which our proofs rely on. It builds on a sequence of “bad” events such that, under each “bad” event, either the leader or the challenger was not often selected as leader or challenger, and shows that the number of times those “bad” events occur is small.

**Lemma (Lemma 4).** Let $\delta \in (0,1]$ and $n > K$. Let $(A_{t,\delta}(n, \delta))_{n \ge t > K}$ be a sequence of events and $(D_i(n, \delta))_{i \in [K]}$ be positive thresholds satisfying that, for all $t \in [n] \setminus [K]$, under the event $A_{t,\delta}(n, \delta)$,

$$ \exists i_t \in [K], \quad T_t(i_t) \le D_{i_t}(n, \delta) \quad \text{and} \quad T_{t+1}(i_t) = T_t(i_t) + 1. $$

Then, we have $\sum_{t=K+1}^n 1(A_{t,\delta}(n, \delta)) \le \sum_{i \in [K]} D_i(n, \delta)$.
**Proof.** Using the inclusion of events given by the assumption on $(A_{t,\delta}(n, \delta))_{n \ge t > K}$, we obtain

$$ \sum_{t=K+1}^{n} 1(A_{t,\delta}(n, \delta)) \le \sum_{t=K+1}^{n} 1(\exists k_t \in [K], T_t(k_t) \le D_{k_t}(n, \delta), T_{t+1}(k_t) = T_t(k_t) + 1) \\ \le \sum_{i \in [K]} \sum_{t=K+1}^{n} 1(T_t(i) \le D_i(n, \delta), T_{t+1}(i) = T_t(i) + 1) \le \sum_{i \in [K]} D_i(n, \delta). $$

The second inequality is obtained by union bound. The third inequality is direct since the number of times one can increase by one a quantity that is positive and bounded by $D_i(n, \delta)$ is at most $D_i(n, \delta)$. □

**Tracking** Lemma 46 provide general results for the $K(K-1)$ tracking procedures both for IDS and fixed proportions, which includes the ones of Lemma 2. The main theoretical argument behind those results is based on applying Theorem 6 in [12].

**Lemma 46.** For all $n > K$, $i \in [K]$, $j \ne i$, we have

$$ -1/2 \le N_{n,j}^i - (1 - \bar{\beta}_n(i,j))T_n(i,j) \le 1 \quad \text{i.e.} \quad -1 \le (T_n(i,j) - N_{n,j}^i) - \bar{\beta}_n(i,j)T_n(i,j) \le 1/2 \\ \text{and} $$

$$ \frac{N_{n,i}^i - (K - 1)/2}{\max_{j \ne i} \bar{\beta}_n(i,j)} \le \sum_{j \ne i} T_n(i,j) \le \frac{N_{n,i}^i + K - 1}{\min_{j \ne i} \bar{\beta}_n(i,j)}. $$

Let $\beta \in (0, 1)$. For fixed proportions $\beta$, we have

$$ N_{n,i} \ge \min\{\beta, 1 - \beta\} \left( T_n(i) - \frac{3(K-1)}{2} \right). $$

**Proof.** We have $K(K-1)$ independent two-arms C-Tracking between the challenger and the leader. Theorem 6 in [12] yields the result. The second inequality is a simple re-ordering.

To obtain the second part, direct manipulations yield that

$$ \sum_{j \ne i} T_n(i,j) \le \sum_{j \ne i} \frac{T_n(i,j) - N_{n,j}^i + 1}{\bar{\beta}_n(i,j)} \le \frac{\sum_{j \ne i} (T_n(i,j) - N_{n,j}^i) + K - 1}{\min_{j \ne i} \bar{\beta}_n(i,j)}, $$

which allows to conclude since $N_{n,i}^i = \sum_{j \ne i} (T_n(i,j) - N_{n,j}^i)$. The lower bound is obtained similarly.

The third is a direct consequence of the first part since

$$ N_{n,i} = \sum_{j \ne i} (T_n(i,j) - N_{n,j}^i) + \sum_{j \ne i} N_{n,i}^j \le \beta \sum_{j \ne i} T_n(i,j) + (1 - \beta) \sum_{j \ne i} T_n(j,i) + 3(K-1)/2 \\ \ge \beta \sum_{j \ne i} T_n(i,j) + (1 - \beta) \sum_{j \ne i} T_n(j,i) - 3(K-1)/2. $$

Having shown

$$ \max_{i \in [K]} \left| N_{n,i} - \left( \beta \sum_{j \ne i} T_n(i,j) + (1-\beta) \sum_{j \ne i} T_n(j,i) \right) \right| \le 3(K-1)/2, $$

it is direct to conclude. □

**Methodology** Lemma 47 is a standard result to upper bound the expected sample complexity of an algorithm, e.g. see Lemma 1 in [11]. This is a key method extensively used in the literature.

**Lemma 47.** Let $(\mathcal{E}_n)_{n>K}$ be a sequence of events and $T(\delta) > K$ be such that for $n \ge T(\delta)$, $\mathcal{E}_n \subseteq \{\tau_\delta \le n\}$. Then, $\mathbb{E}_\nu[\tau_\delta] \le T(\delta) + \sum_{n>K} \mathbb{P}_\nu(\mathcal{E}_n^c)$. □
**Proof.** Since the random variable $\tau_\delta$ is positive and $\{\tau_\delta > n\} \subseteq \mathcal{E}_n^c$ for all $n \ge T(\delta)$, we have

$$ \mathbb{E}_{\nu}[\tau_{\delta}] = \sum_{n \ge 0} \mathbb{P}_{\nu}(\tau_{\delta} > n) \le T(\delta) + \sum_{n \ge T(\delta)} \mathbb{P}_{\nu}(\mathcal{E}_n^c), $$

which concludes the proof by adding positive terms. □

Lemma 48 is a key method to upper bound the probability of error of an algorithm.

**Lemma 48.** Let $\varepsilon \ge 0$ and $(\mathcal{E}_{n,\delta})_{n>K,\delta \in (0,1)}$ be a sequence of events such that $\mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^c) \le C\delta$ with $C > 0$. Suppose that $T_{\varepsilon}(\delta) > K$ is such that for $n > T_{\varepsilon}(\delta)$, $\mathcal{E}_{n,\delta} \subseteq \{\hat{\eta}_n \in \mathcal{I}_{\varepsilon}(\mu)\}$. Then,

$$ \mathbb{P}_{\nu}(\hat{\eta}_n \notin \mathcal{I}_{\varepsilon}(\mu)) \le C \inf\{\delta \mid n > T_{\varepsilon}(\delta)\}. $$

**Proof.** Using the assumption, we have $\mathbb{P}_{\nu}(\hat{\eta}_n \notin \mathcal{I}_{\varepsilon}(\mu)) \le \mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^c) \le C\delta$ for all $n > T_{\varepsilon}(\delta)$. Taking the infimum yields the result. □

**Inversion results** Lemma 49 gathers properties on the function $\overline{W}_{-1}$, which is used in the literature to obtain concentration results.

**Lemma 49** ([22]). Let $\overline{W}_{-1}(x) = -W_{-1}(-e^{-x})$ for all $x \ge 1$, where $W_{-1}$ is the negative branch of the Lambert W function. The function $\overline{W}_{-1}$ is increasing on $(1, +\infty)$ and strictly concave on $(1, +\infty)$. In particular, $\overline{W}'_{-1}(x) = \left(1 - \frac{1}{\overline{W}_{-1}(x)}\right)^{-1}$ for all $x > 1$. Then, for all $y \ge 1$ and $x \ge 1$,

$$ \overline{W}_{-1}(y) \le x \iff y \le x - \log(x). $$

Moreover, for all $x > 1$,

$$ x + \log(x) \le \overline{W}_{-1}(x) \le x + \log(x) + \min\left\{\frac{1}{2}, \frac{1}{\sqrt{x}}\right\}. $$

Lemma 50 provides an ordering on the thresholds for tighter concentration results. It leverages properties of $\overline{W}_{-1}$.

**Lemma 50.** Let $s \ge 0$. Let $\overline{W}_{-1}$ defined in Lemma 49. For all $\delta \in (0, 1]$ and $n \ge 1$, let us denote by

$$ \tilde{f}_1(n, \delta) = \frac{1}{2} \overline{W}_{-1}(2 \log(1/\delta) + 2s \log n + 2 \log(2 + \log n) + 2), $$

$$ \tilde{f}_2(n, \delta) = \overline{W}_{-1} \left( \log \left( \frac{1}{\delta} \right) + s \log n + 2 \log \left( 2 + \log n \right) + 2 \right). $$

Then, we have $\tilde{f}_1(n, \delta) \le \tilde{f}_2(n, \delta)$.

**Proof.** Let $a > 0$ and $b \ge 1$. Let us define $f(x) = \frac{1}{x}\overline{W}_{-1}(ax + b)$. Using Lemma 49, we have

$$ f'(x) = -\frac{1}{x^2} \left( \overline{W}_{-1}(ax + b) - \frac{ax}{1 - \overline{W}_{-1}(ax + b)^{-1}} \right). $$

Therefore, we obtain $f'(x) \le 0$ if and only if $\overline{W}_{-1}(ax + b) \ge ax + 1$. Since $\overline{W}_{-1}(ax + b) \ge ax + b$ and $b \ge 1$, the function $f(x)$ is decreasing for all $x \ge 1$. Therefore, $\frac{1}{2}\overline{W}_{-1}(2x + b) \le \overline{W}_{-1}(a + b)$. Applying this result with $a = \log(1/\delta) + s \log n$ and $b = 2 \log(2 + \log n) + 2 \ge 1$ for all $n \ge 1$, we obtain $\tilde{f}_1(n, \delta) \le \tilde{f}_2(n, \delta)$. □

Lemma 51 is an inversion result to upper bound a time which is implicitly defined. It is a direct consequence of Lemma 49.

**Lemma 51.** Let $\overline{W}_{-1}$ defined in Lemma 49. Let $A > 0, B > 0$ such that $B/A + \log A > 1$ and

$$ C(A, B) = \sup \{x \mid x < A \log x + B\}, $$

$$ C(A, B, D) = \sup \{x \mid x < A \overline{W}_{-1} (2 \log (2 + \log x) + D) + B\}. $$

Then, $C(A, B) < h_1(A, B)$ with $h_1(z, y) = z\overline{W}_{-1}(y/z + \log z)$ and $C(A, B) < Ah_2(A, B, D) + B$ where

$$ h_2(x, y, z) = \inf \{u \mid u - \log u - 2 \log (2 + \log(xu + y)) \ge z\}. $$
**Proof.** Since $B/A + \log A > 1$, we have $C(A, B) \ge A$, hence

$$C(A, B) = \sup \{x \mid x < A \log(x) + B\} = \sup \{x \ge A \mid x < A \log(x) + B\}.$$

Using Lemma 49 yields that

$$x \ge A \log x + B \iff \frac{x}{A} - \log \left(\frac{x}{A}\right) \ge \frac{B}{A} + \log A \iff x \ge A \overline{W}_{-1} \left(\frac{B}{A} + \log A\right).$$

By changing the variable, we obtain

$$C(A, B, D) = B + A \sup \{y \mid y < \overline{W}_{-1} (2 \log (2 + \log(Ay + B)) + D)\}$$

Likewise, Lemma 49 yields that

$$y \ge \overline{W}_{-1} (2 \log (2 + \log(Ay + B)) + D) \iff y - \log y - 2 \log (2 + \log(Ay + B)) \ge D.$$

□

Lemma 52 is an inversion result to upper bound a probability which is implicitly defined based on times that are implicitly defined.

**Lemma 52.** Let $\overline{W}_{-1}$ defined in Lemma 49. Let $A > 0, B > 0, C > 0, E > 0, \alpha > 0, \beta > 0$ and

$$D_{A,B,C}(\delta) = \sup \{x \mid x \le A(\log(1/\delta) + C \log x) + B\},$$

$$D_{A,B,C,E,\alpha,\beta}(\delta) = \sup \left\{ x \mid x \le \frac{A}{\alpha} \overline{W}_{-1} \left( \alpha \left( \log(1/\delta) + C \log(\beta + \log x) + E \right) + B \right) \right\}.$$

Then,

$$\inf\{\delta \mid x > D_{A,B,C}(\delta)\} \le x^C \exp\left(-\frac{x-B}{A}\right),$$

$$\inf\{\delta \mid x > D_{A,B,C,E,\alpha,\beta}(\delta)\} \le e^E \left(\alpha \frac{x-B}{A}\right)^{1/\alpha} (\beta + \log x)^C \exp\left(-\frac{x-B}{A}\right).$$

**Proof.** Direct manipulations yield that

$$x > D_{A,B,C}(\delta) \iff x > A(\log(1/\delta) + C \log x) + B \iff \delta < x^C \exp\left(-\frac{x-B}{A}\right).$$

Likewise, using Lemma 49, we obtain

$$\begin{align*}
x > D_{A,B,C,E,\alpha,\beta}(\delta) &\iff \alpha \frac{x-B}{A} > \overline{W}_{-1} \left( \alpha \left( \log(1/\delta) + C \log(\beta + \log x) + E \right) \right) \\
&\iff \frac{x-B}{A} - \frac{1}{\alpha} \log \left( \alpha \frac{x-B}{A} \right) > \log(1/\delta) + C \log(\beta + \log x) + E \\
&\iff \delta < e^E \left( \alpha \frac{x-B}{A} \right)^{1/\alpha} (\beta + \log x)^C \exp \left( -\frac{x-B}{A} \right).
\end{align*}$$

□

# I Multiplicative setting

Let $\nu \in D^K$ with mean parameters $\mu \in (\mathbb{R}_+^*)^K$. Compared to the additive setting, we only consider strictly positive mean parameters. In many applications, this assumption is natural. In other applications, there is a known lower bound on the value of the true mean parameters, hence we can simply translate the problem by adding this lower bound. We also note that the problem of identifying which arms are above the threshold 0 is the thresholding bandit problem, which has been extensively studied in the literature. Overall, while this assumption might seem restrictive, we think it is rather mild. Since the means are strictly positive, the multiplicative error $\varepsilon$ has also to be positive and strictly smaller than 1. Given a multiplicative error $\varepsilon \in [0, 1)$, the set of multiplicative $\varepsilon$-good arms are denoted by $\mathcal{I}_{\varepsilon}^{\text{mul}}(\mu) := \{i \in [K] \mid \Delta_i \le \mu_* \varepsilon\}$. We will refer to this problem as multiplicative $\varepsilon$-BAI.

First, we discuss the characteristic times involved in the fixed-confidence multiplicative $\varepsilon$-BAI (Appendix I.1). Second, for $\varepsilon_0 \in (0, 1)$, we present the $\text{EB-TC}_{\varepsilon_0}^m$ with IDS or fixed $\beta$ proportions (Appendix I.2). Finally, we prove that $\text{EB-TC}_{\varepsilon_0}^m$ is asymptotically (resp. $\beta$-)optimal when using IDS (resp. fixed $\beta$) when combined with the appropriate GLR stopping rule (Appendix I.3).
## I.1 Characteristic times

Let $\nu \in D^K$ with mean parameters $\mu \in (\mathbb{R}_+^*)^K$. We assume in the following that there exists a unique best arm, i.e. $i^*(\mu) = \{i^*\}$. Let $\varepsilon \in [0, 1)$. The $(\beta)$-characteristic times for the fixed confidence multiplicative $\varepsilon$-BAI setting with Gaussian bandits $\mathcal{N}(\mu, 1)$ are defined as $T_{\varepsilon}^{\text{mul}}(\mu) = \min_{i \in \mathcal{I}_{\varepsilon}^{\text{mul}}(\mu), \beta \in (0,1)} T_{\varepsilon, \beta}^{\text{mul}}(\mu, i)$ and $T_{\varepsilon, \beta}^{\text{mul}}(\mu) = \min_{i \in \mathcal{I}_{\varepsilon}^{\text{mul}}(\mu)} T_{\varepsilon, \beta}^{\text{mul}}(\mu, i)$ where

$$2T_{\varepsilon, \beta}^{\text{mul}}(\mu)^{-1}(\mu, i) = \max_{w \in \Delta_K, w_i = \beta} \min_{j \neq i} \frac{(\mu_i - (1 - \varepsilon)\mu_j)^2}{1/\beta + (1 - \varepsilon)^2/w_j}, \quad (30)$$

We denote by $w_{\varepsilon}^{\text{mul}}(\mu, i)$ and $w_{\varepsilon, \beta}^{\text{mul}}(\mu, i)$ their maximizer, which we refer to as the $(\beta)$-optimal allocation for multiplicative $\varepsilon$-BAI.

Even though the multiplicative $\varepsilon$-BAI is less studied, it is direct to see that it has similar properties as $T_0(\mu)$. Due to the factor $(1 - \varepsilon)^2$ in the denominator, it is not possible to simply use a reduction to a BAI problem as we did for the additive $\varepsilon$-BAI problem (see Lemma 9). Since the properties listed in Appendix C are obtained by studying the optimization problem defining $T_0(\mu)$, we will have the same properties for $T_{\varepsilon}^{\text{mul}}(\mu)$ by accounting for the extra multiplicative factor $(1 - \varepsilon)^2$. We list here the properties on which our proof relies:

* $T_{\varepsilon}^{\text{mul}}(\mu) = \min_{\beta \in (0,1)} T_{\varepsilon, \beta}^{\text{mul}}(\mu, i^*)$ and $T_{\varepsilon, \beta}^{\text{mul}}(\mu) = T_{\varepsilon, \beta}^{\text{mul}}(\mu, i^*)$, meaning the unique best arm corresponds to the arm which is the easiest to verify multiplicative $\varepsilon$-BAI.

* $w_{\varepsilon}^{\text{mul}}(\mu) = \{w_{\varepsilon}^{\text{mul}}\}$ and $w_{\varepsilon, \beta}^{\text{mul}}(\mu) = \{w_{\varepsilon, \beta}^{\text{mul}}\}$, meaning there is a unique $(\beta)$-optimal allocation which satisfies $\min_{i \in [K]} (w_{\varepsilon}^{\text{mul}})_i > 0$ and $\min_{i \in [K]} (w_{\varepsilon, \beta}^{\text{mul}})_i > 0$.

* There is equality at the equilibrium of the transportation costs, meaning for all $i \neq i^*$

$$\frac{(\mu_{i^*} - (1 - \varepsilon)\mu_i)^2}{(w_{\varepsilon}^{\text{mul}})_{i^*}^{-1} + (1 - \varepsilon)^2(w_{\varepsilon}^{\text{mul}})_i^{-1}} = 2T_{\varepsilon}^{\text{mul}}(\mu)^{-1} \quad \text{and} \quad \frac{(\mu_{i^*} - (1 - \varepsilon)\mu_i)^2}{\beta^{-1} + (1 - \varepsilon)^2(w_{\varepsilon, \beta}^{\text{mul}})_i^{-1}} = 2T_{\varepsilon, \beta}^{\text{mul}}(\mu)^{-1}, \quad (31)$$

and the multiplicative overall balance equation is satisfied

$$\sum_{i \neq i^*} \left( \frac{(w_{\varepsilon}^{\text{mul}})_i}{(w_{\varepsilon}^{\text{mul}})_{i^*}} \right)^2 = (1 - \varepsilon_0)^2. \quad (32)$$

For the sake of space, we omit the proofs and defer the reader to Appendix C for ideas on how to prove them.

## I.2 Anytime Top Two algorithm

Let $\varepsilon_0 \in (0, 1)$. The EB-TC$^{\text{m}}_{\varepsilon_0}$ algorithm, detailed in Figure 3, has the same structure as EB-TC$_{\varepsilon_0}$. There are two differences. First, the IDS proportions are $\beta_n(i, j) = N_{n,j}/((1 - \varepsilon_0)^2 N_{n,i} + N_{n,j})$ when considering multiplicative $\varepsilon$-BAI. Second, the challenger will be based on transportation costs for multiplicative $\varepsilon$-BAI, namely

$$C_n^{\text{TC}^{\text{m}}_{\varepsilon_0}} \in \arg \min_{i \neq B_n^{\text{EB}}} \frac{\mu_{n, B_n^{\text{EB}}} - (1 - \varepsilon_0)\mu_{n,i}}{\sqrt{1/N_{n, B_n^{\text{EB}}} + (1 - \varepsilon_0)^2/N_{n,i}}} . \quad (33)$$

**Stopping rule for fixed-confidence multiplicative $\varepsilon$-BAI** Similarly, the fixed-confidence setting requires a stopping rule, which will be different since we tackle multiplicative $\varepsilon$-BAI. Given an error/confidence pair $(\varepsilon, \delta) \in [0, 1) \times (0, 1)$, the GLR$^{\text{m}}_{\varepsilon}$ stopping rule [15] prescribes to stop at the time

$$\tau_{\varepsilon, \delta}^{\text{mul}} = \inf \left\{ n > K \mid \min_{i \neq i_n} \frac{\mu_{n, i_n} - (1 - \varepsilon)\mu_{n,i}}{\sqrt{1/N_{n, i_n} + (1 - \varepsilon)^2/N_{n,i}}} \ge \sqrt{2c(n - 1, \delta)} \right\}, \quad (34)$$

where $c: \mathbb{N} \times (0, 1) \to \mathbb{R}_+$ is a threshold function. Lemma 53 gives a threshold ensuring that the GLR$^{\text{m}}_{\varepsilon}$ stopping rule is $(\varepsilon, \delta)$-PAC for all $\varepsilon \in [0, 1)$ and $\delta \in (0, 1)$, independently of the sampling rule.
<caption>Figure 3: EB-TC<sup>m</sup><sub>ε<sub>0</sub></sub> algorithm with fixed or IDS proportions.</caption>

1. **Input:** slack ε₀ ∈ (0, 1), proportion β ∈ (0, 1) (only for fixed proportions).

2. Set $\hat{i}_n \in \arg\max_{i \in [K]} \mu_{n,i}$, $B_n^{\text{EB}} = \hat{i}_n$ and $C_n^{\text{TC}_{\varepsilon_0}^m} \in \arg\min_{i \neq B_n^{\text{EB}}}$ $\frac{\mu_{n,B_n^{\text{EB}}} - (1-\varepsilon_0)\mu_{n,i}}{\sqrt{1/N_{n,B_n^{\text{EB}}} + (1-\varepsilon_0)^2/N_{n,i}}}$.

3. Set [fixed] $\bar{\beta}_{n+1}(i, j) = \beta$ or [IDS] $\beta_n(i, j) = N_{n,j}/((1 - \varepsilon_0)^2 N_{n,i} + N_{n,j})$ and update $\bar{\beta}_{n+1}(i, j)$.

4. Set $I_n = C_n^{\text{TC}_{\varepsilon_0}^m}$ if $N_n^{\text{TC}_{\varepsilon_0}^m} \le (1 - \bar{\beta}_{n+1}(B_n^{\text{EB}}, C_n^{\text{TC}_{\varepsilon_0}^m}))T_{n+1}(B_n^{\text{EB}}, C_n^{\text{TC}_{\varepsilon_0}^m})$, otherwise set $I_n = B_n^{\text{EB}}$.

5. **Output:** next arm to sample $I_n$ and next recommendation $\hat{i}_n$.

**Lemma 53.** Let $\varepsilon \in [0, 1)$ and $\delta \in (0, 1)$. Given any sampling rule, using the threshold (4) with the stopping rule (34) with error/confidence pair $(\varepsilon, \delta)$ yields a $(\varepsilon, \delta)$-PAC algorithm for sub-Gaussian distributions.

*Proof.* The proof of Lemma 53 is actually almost identical to the one of Lemma 3. The only change is at the beginning of the proof. Since $\hat{i}_n = i^*(\mu_n)$, standard manipulations yield that for all $i \neq \hat{i}_n$

$$ \frac{(\mu_{n,\hat{i}_n} - (1-\varepsilon)\mu_{n,i})^2}{1/N_{n,\hat{i}_n} + (1-\varepsilon)^2/N_{n,i}} = \inf_{u \in \mathbb{R}} \left\{ \begin{aligned} & N_{n,\hat{i}_n}(\mu_{n,\hat{i}_n} - u)^2 + N_{n,i}(\mu_{n,i} - u/(1-\varepsilon))^2 \\ & \qquad - \inf_{y \ge x/(1-\varepsilon)} \left\{ N_{n,\hat{i}_n}(\mu_{n,\hat{i}_n} - x)^2 + N_{n,i}(\mu_{n,i} - y)^2 \right\} \end{aligned} \right\}. $$

Let $i^* = i^*(\mu)$. Using the stopping rule (34) and the above manipulations, we obtain

$$ \begin{aligned} & \mathbb{P}_{\nu} \left( \tau_{\varepsilon, \delta}^{\text{mul}} < +\infty, \hat{i}_{\tau_{\varepsilon, \delta}^{\text{mul}}} \notin \mathcal{I}_{\varepsilon}^{\text{mul}}(\mu) \right) \\ & \le \mathbb{P}_{\nu} \left( \exists n \in \mathbb{N}, \exists i \notin \mathcal{I}_{\varepsilon}^{\text{mul}}(\mu), i = i^*(\mu_n), \right. \\ & \qquad \left. \min_{k \neq i} \inf_{y \ge x/(1-\varepsilon)} \left( N_{n,\hat{i}_n}(\mu_{n,\hat{i}_n} - x)^2 + N_{n,i}(\mu_{n,i} - y)^2 \right) \ge 2c(n-1, \delta) \right) \\ & \le \mathbb{P}_{\nu} \left( \exists n \in \mathbb{N}, \exists i \notin \mathcal{I}_{\varepsilon}^{\text{mul}}(\mu), i = i^*(\mu_n), \right. \\ & \qquad \left. \frac{N_{n,i}}{2}(\mu_{n,i} - \mu_i)^2 + \frac{N_{n,i^*}}{2}(\mu_{n,i^*} - \mu_{i^*})^2 \ge c(n-1, \delta) \right) \\ & \le \sum_{i \notin \mathcal{I}_{\varepsilon}^{\text{mul}}(\mu)} \mathbb{P}_{\nu} \left( \exists n \in \mathbb{N}, \frac{N_{n,i}}{2}(\mu_{n,i} - \mu_i)^2 + \frac{N_{n,i^*}}{2}(\mu_{n,i^*} - \mu_{i^*})^2 \ge c(n-1, \delta) \right), \end{aligned} $$

where the second inequality is obtained with $(k, x, y) = (i^*, \mu_i, \mu_{i^*})$ since $i \notin \mathcal{I}_{\varepsilon}^{\text{mul}}(\mu)$, and the third by union bound. Then, we can conclude as in Appendix G.1 that

$$ \mathbb{P}_{\nu} \left( \tau_{\varepsilon, \delta}^{\text{mul}} < +\infty, \hat{i}_{\tau_{\varepsilon, \delta}^{\text{mul}}} \notin \mathcal{I}_{\varepsilon}^{\text{mul}}(\mu) \right) \le \delta. $$

□

**Asymptotic expected sample complexity** While Theorem 8 holds for all sub-Gaussian distributions, it is particularly interesting for Gaussian ones, in light of Lemma 1. It shows that, for multiplicative $\varepsilon$-BAI, EB-TC<sup>m</sup><sub>ε₀</sub> is asymptotically optimal for Gaussian bandits when using IDS proportions and asymptotically $\beta$-optimal when using fixed proportions $\beta$.

**Theorem 8.** Let $\varepsilon_0 \in (0, 1)$, $\beta \in (0, 1)$ and $\delta \in (0, 1)$. Using the threshold (4) in the stopping rule (34) with error/confidence $(\varepsilon_0, \delta)$, the EB-TC<sup>m</sup><sub>ε₀</sub> algorithm is $(\varepsilon_0, \delta)$-PAC and it satisfies that, for all $\nu \in \mathcal{D}^K$ such that $|i^*(\mu)| = 1$,

$$ \text{[IDS]} \quad \limsup_{\delta \to 0} \frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_0, \delta}]}{\log(1/\delta)} \le T_{\varepsilon_0}^{\text{mul}}(\mu) \quad \text{and} \quad \text{[fixed } \beta \text{]} \quad \limsup_{\delta \to 0} \frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_0, \delta}]}{\log(1/\delta)} \le T_{\varepsilon_0, \beta}^{\text{mul}}(\mu). $$
## I.3 Proof of Theorem 8

The proof is very similar to the one of Theorem 1, hence we will only highlight key differences. We defer the reader to Appendix D for a detailed discussion on the proof method and intuition on the different steps of the proof, see also [36, 21, 40].

In the following, we consider a slack $\epsilon_0$ for EB-TC$^{m}_{\epsilon_0}$ which matches the error $\epsilon$ considered by the GLR$^{m}_{\epsilon}$ stopping rule (34), i.e. $\epsilon_0 = \epsilon$. For conciseness, we denote $w^* = w^{\text{mul}}_{\epsilon}$ and $w^*_{\beta} = w^{\text{mul}}_{\epsilon, \beta}$.

Let $\gamma > 0$. Let us define the convergence times $T_{\epsilon_0, \gamma}$ and $T_{\epsilon_0, \beta, \gamma}$ as in (10) and (14), i.e.

$$T_{\epsilon_0, \gamma} := \inf \left\{ T \ge 1 \mid \forall n \ge T, \max_{i \ne i^*} \left| \frac{N_{n,i}}{N_{n,i^*}} - \frac{w_i^*}{w_{i^*}^*} \right| \le \gamma \right\},$$

$$T_{\epsilon_0, \beta, \gamma} := \inf \left\{ T \ge 1 \mid \forall n \ge T, \left\| \frac{N_n}{n-1} - w_{\beta}^* \right\|_{\infty} \le \gamma \right\}.$$

Lemma 54 gives a sufficient condition for asymptotic optimality and asymptotic $\beta$-optimality. The proof is the same as for Lemmas 13 and 25, hence we omit it.

**Lemma 54.** Let $\epsilon_0 \in (0, 1)$ and $\delta \in (0, 1)$. Assume that there exists $\gamma_1(\mu) > 0$ such that for all $\gamma \in (0, \gamma_1(\mu))$, $\mathbb{E}_{\nu}[T_{\epsilon_0, \gamma}] < +\infty$. Using the threshold (4) in the stopping rule (3) with error $\epsilon_0$ yields an algorithm such that, for all $\nu \in \mathcal{D}^K$ such that $|i^*(\mu)| = 1$,

$$\limsup_{\delta \to 0} \frac{\mathbb{E}_{\nu}[\tau_{\epsilon_0, \delta}]}{\log(1/\delta)} \le T_{\epsilon_0}^{\text{mul}}(\mu).$$

Assume that there exists $\gamma_1(\mu) > 0$ such that for all $\gamma \in (0, \gamma_1(\mu))$, $\mathbb{E}_{\nu}[T_{\epsilon_0, \beta, \gamma}] < +\infty$. Using the threshold (4) in the stopping rule (3) with error $\epsilon_0$ yields an algorithm such that, for all $\nu \in \mathcal{D}^K$ such that $|i^*(\mu)| = 1$,

$$\limsup_{\delta \to 0} \frac{\mathbb{E}_{\nu}[\tau_{\epsilon_0, \delta}]}{\log(1/\delta)} \le T_{\epsilon_0, \beta}^{\text{mul}}(\mu).$$

### I.3.1 Sufficient exploration

Lemma 55 shows that the transportation cost is strictly positive and increases linearly, it bares similarity with Lemma 14.

**Lemma 55.** Let $S_n^L$ and $\mathcal{I}_n^*$ as in (11). There exists $L_0$ with $\mathbb{E}_{\mu}[(L_0)^\alpha] < +\infty$ for all $\alpha > 0$ such that if $L \ge L_0$, for all $n$ such that $S_n^L \ne \emptyset$, for all $(i, j) \in \mathcal{I}_n^* \times S_n^L$ such that $i \ne j$, we have

$$\frac{\mu_{n,i} - (1 - \epsilon_0)\mu_{n,j}}{\sqrt{1/N_{n,i} + (1 - \epsilon_0)^2/N_{n,j}}} \ge \sqrt{LD_\mu},$$

where $D_\mu > 0$ is a problem dependent constant.

*Proof.* Using Lemma 12 and $\min\{N_{n,i}, N_{n,j}\} \ge L$, we obtain

$$\mu_{n,i} - (1 - \epsilon_0)\mu_{n,j} \ge \mu_i - (1 - \epsilon_0)\mu_j - W_\mu \left( \sqrt{\frac{\log(e + N_{n,i})}{N_{n,i}}} + (1 - \epsilon_0)\sqrt{\frac{\log(e + N_{n,j})}{N_{n,j}}} \right) \\ \ge \epsilon_0 \min_{i \in [K]} \mu_i - (2 - \epsilon_0)W_\mu \sqrt{\frac{\log(e + L)}{L}} \ge \epsilon_0 \min_{i \in [K]} \mu_i / 2,$$

where the last inequality is obtained for $L \ge L_0 = L_1 - e$ which is defined as

$$L_1 = \sup \left\{ x \mid x < \frac{4(2 - \epsilon_0)^2 W_{\mu}^2}{\epsilon_0^2 \min_{i \in [K]} \mu_i^2} \log(x) + e \right\} < h_1 \left( \frac{4(2 - \epsilon_0)^2 W_{\mu}^2}{\epsilon_0^2 \min_{i \in [K]} \mu_i^2}, e \right),$$

The last inequality is obtained by using Lemma 51, and we recall that $h_1$ is defined in Lemma 51. Since $h_1(x, e) \sim_{x \to +\infty} x \log x$, we have $\mathbb{E}_{\mu}[(L_0)^\alpha] < +\infty$ for all $\alpha > 0$ by using Lemma 12 (polynomial in $W_\mu$). Then, we have

$$\frac{\mu_{n,i} - (1 - \epsilon_0)\mu_{n,j}}{\sqrt{1/N_{n,i} + (1 - \epsilon_0)^2/N_{n,j}}} \ge \frac{\epsilon_0 \min_{i \in [K]} \mu_i / 2}{\sqrt{1/N_{n,i} + (1 - \epsilon_0)^2/N_{n,j}}} \ge \sqrt{L} \frac{\epsilon_0 \min_{i \in [K]} \mu_i}{2\sqrt{1 + (1 - \epsilon_0)^2}}.$$
Setting $D_\mu = \frac{\epsilon_0 \min_{i \in [K]} \mu_i}{2\sqrt{1+(1-\epsilon_0)^2}}$ yields the result. $\square$

Lemma 56 gives an upper bound on the transportation costs between a sampled enough arm and an under-sampled one it bares similarity with Lemma 15.

**Lemma 56.** Let $S_n^L$ as in (11). There exists $L_1$ with $\mathbb{E}_\mu[(L_1)^\alpha] < +\infty$ for all $\alpha > 0$ such that for all $L \ge L_1$ and all $n \in \mathbb{N}$,

$$ \forall (i, j) \in S_n^L \times \overline{S_n^L}, \quad \frac{\mu_{n,i} - (1 - \epsilon_0)\mu_{n,j}}{\sqrt{1/N_{n,i} + (1 - \epsilon_0)^2/N_{n,j}}} \le \frac{\sqrt{L}}{1 - \epsilon_0} (D_1 + 4W_\mu), $$

where $D_1 > 0$ is a problem dependent constant and $W_\mu$ is the random variables defined in Lemma 12.

*Proof.* Using Lemma 12 and $N_{n,i} \ge L \ge N_{n,j} \ge 1$, we obtain

$$ \begin{aligned} \frac{\mu_{n,i} - (1 - \epsilon_0)\mu_{n,j}}{\sqrt{1/N_{n,i} + (1 - \epsilon_0)^2/N_{n,j}}} &\le \frac{\sqrt{N_{n,j}}}{1 - \epsilon_0} |\mu_{n,i} - (1 - \epsilon_0)\mu_{n,j}| \\ &\le \frac{\sqrt{L}}{1 - \epsilon_0} \left( |\mu_i - (1 - \epsilon_0)\mu_j| + W_\mu \left( \sqrt{\frac{\log(e + N_{n,i})}{N_{n,i}}} + (1 - \epsilon_0)\sqrt{\frac{\log(e + N_{n,j})}{N_{n,j}}} \right) \right) \\ &\le \frac{\sqrt{L}}{1 - \epsilon_0} \left( |\mu_i - (1 - \epsilon_0)\mu_j| + (2 - \epsilon_0)W_\mu \sqrt{\log(e + 1)} \right) \le \frac{\sqrt{L}}{1 - \epsilon_0} (D_1 + 4W_\mu), \end{aligned} $$

for $D_1 = \max_{i \neq j} |\mu_i - (1 - \epsilon_0)\mu_j|$.

Lemma 57 show that the desired property for the TC challenger, we omit the proof since it is the same as for Lemma 17.

**Lemma 57.** There exists $L_1$ with $\mathbb{E}_\nu[L_3] < +\infty$ such that if $L \ge L_3$, for all $n$ (at most polynomial in $L$) such that $U_n^L \neq \emptyset$, $B_n^{EB} \notin V_n^L$ implies $C_n^{TC_{\epsilon_0}} \in V_n^L$.

Combining Lemma 16 and Lemma 57 yields Lemma 58. Importantly, Lemma 58 holds for the EB-TC$_{\epsilon_0}$ algorithm with fixed proportions $\beta \in (0, 1)$ and IDS proportions. Since the proof is the same as for Lemmas 18 and 26, we omit it.

**Lemma 58.** There exist $N_1$ with $\mathbb{E}_\nu[N_1] < +\infty$ such that for all $n \ge N_1$ and all $i \in [K]$, $N_{n,i} \ge \sqrt{n/K}$ and $B_n^{EB} = i^*.$

### I.3.2 Empirical overall balance

As in [40], the key to obtain asymptotic optimality is to show that the empirical proportion satisfy the empirical overall balance equation. Compared to them, the novelty of Lemma 59 is that we use IDS proportions with $K(K-1)$ tracking procedures to select between the leader and the challenger instead of sampling. The proof of Lemma 59 is highly similar to the one of Lemma 19.

**Lemma 59.** Let $\gamma > 0$. There exists $N_2$ with $\mathbb{E}_\nu[N_2] < +\infty$ such that for all $n \ge N_2$

$$ \left| \left( \frac{N_{n,i^*}}{n-1} \right)^2 - \sum_{i \neq i^*} \left( \frac{1}{1-\epsilon_0} \frac{N_{n,i}}{n-1} \right)^2 \right| \le \gamma. $$

*Proof.* Let $N_1$ as in Lemma 58. We proceed as in Lemma 19. Let us define

$$ G_n = \left( \sum_{t=N_1}^{n-1} \beta_t(i^*, C_t) \right)^2 - \sum_{j \neq i^*} \left( \frac{1}{1-\epsilon_0} \sum_{t=N_1}^{n-1} \mathbb{1}(C_t=j) (1-\beta_t(i^*, j)) \right)^2, $$

Direct manipulations yield that

$$ \frac{1}{2}(G_{n+1} - G_n) = \beta_n(i^*, C_n) \sum_{t=N_1}^{n-1} \beta_t(i^*, C_t) - \frac{1 - \beta_n(i^*, C_n)}{(1 - \epsilon_0)^2} \sum_{t=N_1}^{n-1} \mathbb{1}(C_t = C_n) (1 - \beta_t(i^*, C_n)) \\ + \beta_n(i^*, C_n)^2 - \frac{1}{(1 - \epsilon_0)^2} (1 - \beta_n(i^*, C_n))^2. $$
Using that $\beta_n(i^*, C_n)N_{n,i^*} = (1 - \beta_n(i^*, C_n))N_{n,C_n}/(1 - \varepsilon_0)^2$ since $\beta_n(i^*, C_n) = N_{n,C_n}/((1 - \varepsilon_0)^2N_{n,i^*} + N_{n,C_n})$ and the inequalities proven in Lemma 19, we can exhibit deterministic constants $A, B > 0$ (depending on $K$ and $\varepsilon_0$) such that

$$|G_{n+1} - G_n| \le AN_1 + B \quad \text{hence} \quad |G_n| \le (n-1-N_1)(AN_1 + B) + (1-\varepsilon_0)^2.$$

where the second inequality is obtained by telescopic sum (as in Lemma 19) and using that $G_{N_1+1} = \beta_{N_1}(i^*, C_{N_1})^2 - (1 - \beta_{N_1}(i^*, C_{N_1}))^2/(1 - \varepsilon_0)^2$.

As in Lemma 19, it is possible to exhibit deterministic constants $C, D > 0$ (depending on $K$ and $\varepsilon_0$) such that

$$\left| \left( \frac{N_{n,i^*}}{n-1} \right)^2 - \sum_{i \neq i^*} \left( \frac{1}{1-\varepsilon_0} \frac{N_{n,i}}{n-1} \right)^2 - \frac{G_n}{(n-1)^2} \right| \le \frac{CN_1 + D}{n-1}.$$

Combining both results, we can show

$$\left| \left( \frac{N_{n,i^*}}{n-1} \right)^2 - \sum_{i \neq i^*} \left( \frac{1}{1-\varepsilon_0} \frac{N_{n,i}}{n-1} \right)^2 \right| \le \frac{(A+C)N_1 + B + D}{n-1} + \frac{(1-\varepsilon_0)^2}{(n-1)^2}.$$

Therefore, we have shown the desired result for $n \ge N_2$ defined as

$$N_2 = \inf \left\{ n > 2 \mid \frac{(A+C)N_1 + B + D}{n-1} + \frac{(1-\varepsilon_0)^2}{(n-1)^2} \le \gamma \right\},$$

which satisfies $\mathbb{E}_\nu[N_2] < +\infty$ since it is a linear function of $N_1$. $\square$

<figure><img src="image_5.png" /></figure>

As in [40], using Lemma 59 allows to bound the empirical proportion allocated to the unique best arm $N_{n,i^*}/(n-1)$ away from 0 (Lemma 60).

**Lemma 60.** There exists $N_3$ with $\mathbb{E}_\nu[N_3] < +\infty$ such that for all $n \ge N_3$

$$c_L \le \frac{N_{n,i^*}}{n-1} \le c_U \quad \text{where} \quad c_U = \sqrt{\frac{(1-\varepsilon_0)^2/2 + 1}{(1-\varepsilon_0)^2 + 1}} \quad \text{and} \quad c_L = \frac{1-c_U}{(1-\varepsilon_0)\sqrt{2(K-1)}}.$$

*Proof.* Let $N_2$ as in Lemma 59 for $\frac{\gamma}{(1-\varepsilon_0)^4}$. Using Lemma 59, we obtain for all $n \ge N_2$

$$\begin{align*}
\gamma &\ge (1 - \varepsilon_0)^2 \left( \frac{N_{n,i^*}}{n-1} \right)^2 - \sum_{i \neq i^*} \left( \frac{N_{n,i}}{n-1} \right)^2 \ge (1 - \varepsilon_0)^2 \left( \frac{N_{n,i^*}}{n-1} \right)^2 - \left( 1 - \frac{N_{n,i^*}}{n-1} \right)^2 \\
&= ((1 - \varepsilon_0)^2 - 1) \left( \frac{N_{n,i^*}}{n-1} \right)^2 + 2 \frac{N_{n,i^*}}{n-1} - 1 \\
&\ge ((1 - \varepsilon_0)^2 + 1) \left( \frac{N_{n,i^*}}{n-1} \right)^2 - 1.
\end{align*}$$

where we used that $\frac{N_{n,i^*}}{n-1} \le 1$. Taking $\gamma = (1 - \varepsilon_0)^2/2$ yields the upper bound.

Let $\tilde{N}_2$ as in Lemma 59 for $\frac{\gamma}{(K-1)(1-\varepsilon_0)^2}$. Using Lemma 59, we obtain for all $n \ge \max\{N_2, \tilde{N}_2\}$

$$\begin{align*}
-\gamma &\le (K-1)(1-\varepsilon_0)^2 \left( \frac{N_{n,i^*}}{n-1} \right)^2 - (K-1) \sum_{i \neq i^*} \left( \frac{N_{n,i}}{n-1} \right)^2 \\
&\le (K-1)(1-\varepsilon_0)^2 \left( \frac{N_{n,i^*}}{n-1} \right)^2 - \left( 1 - \frac{N_{n,i^*}}{n-1} \right)^2 \\
&\le (K-1)(1-\varepsilon_0)^2 \left( \frac{N_{n,i^*}}{n-1} \right)^2 - (1-c_U)^2
\end{align*}$$

Taking $\gamma = (1 - c_U)^2/2$ yields the lower bound. Note that

$$c_L \le c_U \iff 1 \le \frac{(1 - \varepsilon_0)^2/2 + 1}{(1 - \varepsilon_0)^2 + 1} \left( 2(K - 1)(1 - \varepsilon_0)^2 + 2\sqrt{2(K - 1)(1 - \varepsilon_0)} + 1 \right),$$

where the last condition is trivially true. Taking $N_3 = \max\{N_2, \tilde{N}_2\}$ yields the result. $\square$

<figure><img src="image_6.png" /></figure>
Lemma 61 is a rescaled version of the empirical overall balance equation which is proven by simply combining Lemma 59 and Lemma 60.

**Lemma 61.** Let $\gamma > 0$. There exists $N_4$ with $\mathbb{E}_{\nu}[N_4] < +\infty$ such that for all $n \ge N_4$

$$ \left| (1 - \varepsilon_0)^2 - \sum_{i \neq i^*} \left( \frac{N_{n,i}}{N_{n,i^*}} \right)^2 \right| \leq \gamma. $$

*Proof.* Let $N_3$ and $c_L$ as in Lemma 60. Let $N_2$ as in Lemma 59 for $\gamma c_L^2/(1 - \varepsilon_0)^2$. Direct manipulation shows that, for all $n \ge N_4 = \max\{N_2, N_3\}$,

$$ \begin{aligned} \left| 1 - \sum_{i \neq i^*} \left( \frac{1}{1 - \varepsilon_0} \frac{N_{n,i}}{N_{n,i^*}} \right)^2 \right| &= \left( \frac{n-1}{N_{n,i^*}} \right)^2 \left| \left( \frac{N_{n,i^*}}{n-1} \right)^2 - \sum_{i \neq i^*} \left( \frac{1}{1 - \varepsilon_0} \frac{N_{n,i}}{n-1} \right)^2 \right| \\ &\le \frac{1}{c_L^2} \gamma c_L^2 = \frac{\gamma}{(1 - \varepsilon_0)^2}. \end{aligned} $$

This concludes the result.

<figure><img src="image_7.png" /></figure>

### I.3.3 Convergence towards optimal allocation

As in [40], we show that a challenger will not be sampled next when the ratio of its empirical proportion compared to the one of $i^*$ overshoots the ratio of the optimal allocations (Lemma 62).

**Lemma 62.** Let $\gamma > 0$. There exists $N_5$ with $\mathbb{E}_{\nu}[N_5] < +\infty$ such that for all $n \ge N_5$ and all $i \neq i^*$,

$$ \frac{N_{n,i}}{N_{n,i^*}} \ge \frac{w_i^*}{w_{i^*}^*} + \gamma \quad \Rightarrow \quad C_n^{\text{TC}_{\varepsilon_0}^m} \ne i. $$

*Proof.* Let $\gamma > 0$. Let $i \neq i^*$ such that

$$ \frac{N_{n,i}}{N_{n,i^*}} \ge \frac{w_i^*}{w_{i^*}^*} + \gamma. $$

Let $N_4$ as in Lemma 61. As in Lemma 22, we can show for all $n \ge N_4$

$$ \exists j \notin \{i^*, i\}, \quad \frac{N_{n,j}}{N_{n,i^*}} \le \frac{w_j^*}{w_{i^*}^*}. $$

Let $N_1$ as in Lemma 18. Using that $B_n^{\text{EB}} = i^*$ for all $n \ge N_1$ and the definition of $C_n^{\text{TC}_{\varepsilon_0}^m}$, we know that

$$ \frac{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,i}}{\sqrt{1/N_{n,i^*} + (1 - \varepsilon_0)^2/N_{n,i}}} > \frac{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,j}}{\sqrt{1/N_{n,i^*} + (1 - \varepsilon_0)^2/N_{n,j}}} \quad \Rightarrow \quad C_n^{\text{TC}_{\varepsilon_0}^m} \neq i. $$

To conclude the proof, it is sufficient to show that the ratio of the two quantities is strictly larger than one. For all $n \ge \max\{N_1, N_4\}$, we obtain

$$ \frac{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,i}}{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,j}} \sqrt{\frac{1 + (1 - \varepsilon_0)^2 N_{n,i^*} / N_{n,j}}{1 + (1 - \varepsilon_0)^2 N_{n,i^*} / N_{n,i}}} \\ \ge \frac{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,i}}{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,j}} \sqrt{\frac{1 + (1 - \varepsilon_0)^2 w_{i^*}^* / w_j^*}{1 + (1 - \varepsilon_0)^2 (w_i^* / w_{i^*}^* + \gamma)^{-1}}}. $$

Let $\tilde{\gamma} > 0$. Using Lemmas 12 and 18, we have, for all $n \ge N_1$ and all $k \neq i^*$,

$$ \left| \frac{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,k}}{\mu_{i^*} - (1 - \varepsilon_0)\mu_k} - 1 \right| \le \frac{W_\mu \left( \left(1 - \varepsilon_0\right) \sqrt{\frac{\log(e+N_{n,k})}{N_{n,k}}} + \sqrt{\frac{\log(e+N_{n,i^*})}{N_{n,i^*}}} \right)}{\mu_{i^*} - (1 - \varepsilon_0)\mu_k} \\ \le \frac{(2 - \varepsilon_0)W_\mu}{\min_{k \neq i^*} (\mu_{i^*} - (1 - \varepsilon_0)\mu_k)} \sqrt{\frac{\log(e + \sqrt{n/K})}{\sqrt{n/K}}} \le \tilde{\gamma} $$
for all $n \ge N_6 = K(X_0 - e)^2 + 1$ which is defined as

$$X_0 = \sup \left\{ x \ge 1 \mid \begin{aligned} & x < \frac{(2 - \varepsilon_0)^2 W_{\mu}^2}{\tilde{\gamma}^2 \min_{k \ne i^*} (\mu_{i^*} - (1 - \varepsilon_0)\mu_k)^2} \log x + e \\ & < h_1 \left( \frac{(2 - \varepsilon_0)^2 W_{\mu}^2}{\tilde{\gamma}^2 \min_{k \ne i^*} (\mu_{i^*} - (1 - \varepsilon_0)\mu_k)^2}, e \right) \end{aligned} \right\}$$

where the last inequality is obtained by using Lemma 51 with $h_1$ defined therein. Since $h_1(x, y) \sim x \to +\infty$ $x \log x$, we have $\mathbb{E}_{\nu}[N_6] < +\infty$ since it polynomial in $W_{\mu}$ (by using Lemma 12). Let $\kappa > 0$. We have shown that, for all $n \ge \max\{N_1, N_4, N_6\}$,

$$\begin{aligned} & \frac{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,i}}{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,j}} \sqrt{\frac{1 + (1 - \varepsilon_0)^2 N_{n,i^*}/N_{n,j}}{1 + (1 - \varepsilon_0)^2 N_{n,i^*}/N_{n,i}}} \\ & \ge \frac{\mu_{i^*} - (1 - \varepsilon_0)\mu_i}{\mu_{i^*} - (1 - \varepsilon_0)\mu_j} \sqrt{\frac{1 + (1 - \varepsilon_0)^2 w_{i^*}^*/w_j^*}{1 + (1 - \varepsilon_0)^2 (w_{i^*}^*/w_{i^*}^* + \gamma)^{-1}}} \frac{1 - \tilde{\gamma}}{1 + \tilde{\gamma}} \\ & = \sqrt{\frac{1 + (1 - \varepsilon_0)^2 w_{i^*}^*/w_i^*}{1 + (1 - \varepsilon_0)^2 (w_{i^*}^*/w_{i^*}^* + \gamma)^{-1}}} \frac{1 - \tilde{\gamma}}{1 + \tilde{\gamma}}. \end{aligned}$$

where the equality uses that the transportation costs are equal at the equilibrium, i.e. (31). Taking $\tilde{\gamma}$ small enough, we have that shown that, for all $n \ge \max\{N_1, N_4, N_6\}$,

$$\frac{N_{n,i}}{N_{n,i^*}} \ge \frac{w_i^*}{w_{i^*}^*} + \gamma \quad \implies \quad \frac{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,i}}{\mu_{n,i^*} - (1 - \varepsilon_0)\mu_{n,j}} \sqrt{\frac{1 + (1 - \varepsilon_0)^2 N_{n,i^*}/N_{n,j}}{1 + (1 - \varepsilon_0)^2 N_{n,i^*}/N_{n,i}}} > 1,$$

hence $C_n^{\text{TC}_{\varepsilon_0}^m} \ne i$. This concludes the proof. $\square$

<figure><img src="image_8.png" /></figure>

Lemma 63 is obtained with the same proof as Lemma 23.

**Lemma 63.** Let $\gamma > 0$. There exists $N_6$ with $\mathbb{E}_{\nu}[N_6] < +\infty$ such that for all $n \ge N_6$ and all $i \ne i^*$,

$$\frac{N_{n,i}}{N_{n,i^*}} \le \frac{w_i^*}{w_{i^*}^*} + \gamma.$$

Lemma 64 is obtained with the same proof as Lemma 24.

**Lemma 64.** Let $\varepsilon_0 \in (0, 1)$, $\gamma > 0$ and $T_{\varepsilon_0, \gamma}$ introduced before (adaptation of (10)). Under the EB-TC$_{\varepsilon_0}^m$ sampling rule with IDS proportions, we have $\mathbb{E}_{\nu}[T_{\varepsilon_0, \gamma}] < +\infty$.

Combining Lemmas 54 and 64 yields the first of Theorem 8.

### I.3.4 Convergence towards $\beta$-optimal allocation

Combining Lemmas 58 and 27 with the proof of Lemma F.9 in [20] yields Lemma 65.

**Lemma 65.** Let $\gamma > 0$. There exists $N_5$ with $\mathbb{E}_{\nu}[N_5] < +\infty$ such that for all $n \ge N_5$ and all $i \ne i^*$,

$$\frac{N_{n,i}}{n-1} \ge w_{\beta,i}^* + \gamma \quad \implies \quad C_n^{\text{TC}_{\varepsilon_0}^m} \ne i.$$

Lemma 66 is obtained with the same proof as Lemmas 29 and 30.

**Lemma 66.** Let $\varepsilon_0 \in (0, 1)$, $\beta \in (0, 1)$, $\gamma > 0$ and $T_{\varepsilon_0, \beta, \gamma}$ introduced before (adaptation of (14)). Under the EB-TC$_{\varepsilon_0}^m$ sampling rule with fixed proportions $\beta$, we have $\mathbb{E}_{\nu}[T_{\varepsilon_0, \beta, \gamma}] < +\infty$.

Combining Lemmas 54 and 66 yields the second part of Theorem 8.

## J Implementation details and additional experiments

After presenting the implementations details in Appendix J.1, we display supplementary experiments in Appendix J.2.
## J.1 Implementation details

**Top Two sampling rules** Given a fixed $\beta$, most Top Two algorithms use randomization to select $I_n \in \{B_n, C_n\}$, namely they sample $B_n$ with probability $\beta$, otherwise sample $C_n$. Instead of randomization, TTUCB [20] uses $K$ tracking procedures to select $I_n \in \{B_n, C_n\}$. Namely, they choose $I_n = B_n$ if $N_{n,B_n}^{B_n} \le \beta \sum_{i \ne B_n} T_{n+1}(B_n, i)$, and $I_n = C_n$ otherwise. In comparison, EB-TC$_{\epsilon_0}$ relies on $K(K-1)$ tracking procedures both for fixed proportion $\beta$ and IDS proportions [40]. In [40], they consider IDS proportions to define $\beta_n$ adaptively. For Gaussian with known homoscedastic variance, their update mechanism is

$$ \beta_n = \frac{N_{n,B_n} d_{\mathrm{KL}}(\mu_{n,B_n}, u_n(B_n, C_n))}{N_{n,B_n} d_{\mathrm{KL}}(\mu_{n,B_n}, u_n(B_n, C_n)) + N_{n,C_n} d_{\mathrm{KL}}(\mu_{n,C_n}, u_n(B_n, C_n))} = \frac{N_{n,C_n}}{N_{n,B_n} + N_{n,C_n}}, $$

where the second equality is obtained by direct computations which uses that

$$ u_n(i, j) = \inf_{x \in \mathbb{R}} [N_{n,i} d_{\mathrm{KL}}(\mu_{n,i}, x) + N_{n,j} d_{\mathrm{KL}}(\mu_{n,j}, x)] = \frac{N_{n,i} \mu_{n,i} + N_{n,j} \mu_{n,j}}{N_{n,i} + N_{n,j}}. $$

[8] proposed a new methodology called Balancing Optimal Large Deviations (BOLD) to select $I_n \in \{B_n, C_n\}$ adaptively. While their approach aims at minimizing the probability of incorrect selection (i.e. fixed-budget setting), it is possible to adapt their idea to minimize the expected sample complexity (i.e. fixed-confidence setting) by “swapping” the arguments of the KL divergence. Namely, the BOLD procedure can be rewritten in our setting as selecting $I_n = B_n$ if

$$ \sum_{i \neq B_n} \frac{d_{\mathrm{KL}}(\mu_{n,B_n}, u_n(B_n, i))}{d_{\mathrm{KL}}(\mu_{n,i}, u_n(B_n, i))} > 1, $$

and $I_n = C_n$ otherwise. For Gaussian with known homoscedastic variance, their approach recovers the heuristic “adaptive Welch divergence” algorithm of proposed in [37], i.e. $I_n = B_n$ if $N_{n,B_n}^2 < \sum_{i \neq B_n} N_{n,i}^2$, and $I_n = C_n$ otherwise. The analysis of [8] is focused on asymptotic guarantees in probability. It is an interesting direction for future research to show that the BOLD procedure also yields asymptotically optimal algorithms.

TTTS [34] uses a TS (Thompson Sampling) leader and a RS (Re-Sampling) challenger based on a sampler $\Pi_n$. For Gaussian bandits, the sampler $\Pi_n$ is the posterior distribution $\times_{i \in [K]} \mathcal{N}(\mu_{n,i}, 1/N_{n,i})$ given the improper prior $\Pi_1 = (\mathcal{N}(0, +\infty))^K$. The TS leader is $B_n^{\mathrm{TS}} \in \arg \max_{i \in [K]} \theta_i$ where $\theta \sim \Pi_n$. The RS challenger samples vector of realizations $\theta \in \Pi_n$ until $B_n \notin \arg \max_{i \in [K]} \theta_i$, then it is defined as $C_n^{\mathrm{RS}} \arg \max_{i \in [K]} \theta_i$ for this specific vector of realization. When the posterior $\Pi_n$ and the leader $B_n$ have almost converged towards the Dirac distribution on $\mu$ and the best arm $i^*(\mu)$ respectively, the event $B_n \notin \arg \max_{i \in [K]} \theta_i$ becomes very rare. The experiments in [21] reveals that computing the RS challenger can require more than millions of re-sampling steps. Therefore, the RS challenger can become computationally intractable even for Gaussian distribution where sampling from $\Pi_n$ can be done more efficiently.

T3C [36] combines the TS leader and the TC challenger. EB-TCI [21] combines the EB leader with the TCI challenger defined as

$$ C_n^{\mathrm{TCI}} = \arg \min_{i \neq B_n} \mathbb{1}(\mu_{n,B_n} > \mu_{n,i}) \frac{(\mu_{n,B_n} - \mu_{n,i})^2}{2(1/N_{n,B_n} + 1/N_{n,i})} + \log(N_{n,i}). $$

TTUCB [20] combined the TC challenger with a UCB leader which is defined as

$$ B_n^{\mathrm{UCB}} = \arg \max_{i \in [K]} \{\mu_{n,i} + \sqrt{g(n)/N_{n,i}}\}, $$

where $\sqrt{g(n)/N_{n,i}}$ is a bonus coping for uncertainty. TS-KKT [40] uses the TS leader and a challenger based on transportation costs with a different penalization than the one used in [21], namely

$$ C_n) \in \arg \min_{i \neq B_n} \left\{ \frac{(\mu_{n,B_n} - \mu_{n,i})^2}{2(1/N_{n,B_n} + 1/N_{n,i})} - \frac{\rho}{n} \log (1/N_{n,B_n} + 1/N_{n,i}) \right\}, $$

where $\rho$ is a parameter that needs to be selected beforehand. The authors highlight that the choice of $\rho$ has an important impact on the empirical performance.
While the above Top Two algorithms are BAI algorithms, we can adapt them straightforwardly to tackle the ε-BAI setting by (1) using the stopping rule as in (3) and (2) using transportation costs for ε-BAI, i.e. the ones in (2). The modification (1) is inspired by [19] and the modification (2) by [22]. As an example, the modified TCI challenger can be written as

$$C_n^{\text{TCI}} = \arg \min_{i \neq B_n} \mathbb{1}(\mu_{n, B_n} > \mu_{n, i}) \frac{(\mu_{n, B_n} - \mu_{n, i} + \varepsilon)^2}{2(1/N_{n, B_n} + 1/N_{n, i})} + \log(N_{n, i}).$$

**Fixed-confidence BAI algorithms** At each time n, Track-and-Stop (TaS) [15] computes the optimal allocation for the current empirical mean, $w_n = w^*(\mu_n)$. Given $w_n \in \Delta_K$, it uses a tracking procedure to obtain an arm $I_n$ to sample. On top of this tracking a forced exploration is used to enforce convergence towards the optimal allocation for the true unknown parameters. The optimization problem defining $w^*(\mu)$ can be rewritten as solving an equation $\psi_\mu(r) = 0$, where

$$\forall r \in (1/\min_{i \neq i^*}(\mu_{i^*} - \mu_i)^2, +\infty), \quad \psi_\mu(r) = \sum_{i \neq i^*} \frac{1}{(r(\mu_{i^*} - \mu_i)^2 - 1)^2} - 1$$

The function $\psi_\mu$ is decreasing, and satisfies $\lim_{r \to +\infty} \psi_\mu(r) = -1$ and $\lim_{y \to 1/\min_{i \neq i^*}(\mu_{i^*} - \mu_i)^2} F_\mu(y) = +\infty$. For the practical implementation of the optimal allocation, we use the approach of [15] and perform binary searches to compute the unique solution of $\psi_\mu(r) = 0$. A faster implementation based on Newton's iterates was proposed by [3] after proving that $\psi_\mu$ is convex. While this improvement holds only for Gaussian distributions, the binary searches can be used for more general distributions. Similarly, one can adapt TaS to tackle ε-BAI as done in [16], i.e. by tracking $w_n = w_\varepsilon(\mu_n)$. Using Lemma 9, it is direct to see that one can use the same implementation to compute it efficiently.

DKM [11] view $T^*(\mu)^{-1}$ as a min-max game between the learner and the nature, and design saddle-point algorithms to solve it sequentially. At each time n, a learner outputs an allocation $w_n$, which is used by the nature to compute the worst alternative mean parameter $\lambda_n$. Then, the learner is updated based on optimistic gains based on $\lambda_n$. Similarly, one can adapt DKM to tackle ε-BAI by using a modified alternative mean parameter. This coincides with the LεBAI algorithm [19] when used on unstructured multi-armed bandits.

FWS [39] alternates between forced exploration and Frank-Wolfe (FW) updates. Similarly, FWS can be adapted to tackle ε-BAI

LUCB [24] samples and stops based on upper/lower confidence indices for a bonus function g. For Gaussian distributions, it rewrites for all $i \in [K]$ as

$$U_{n,i} = \mu_{n,i} + \sqrt{\frac{2c(n-1, \delta)}{N_{n,i}}} \quad \text{and} \quad L_{n,i} = \mu_{n,i} - \sqrt{\frac{2c(n-1, \delta)}{N_{n,i}}}.$$

At each time n, it samples $\hat{\mu}_n$ and $\arg\max_{i \neq \hat{\mu}_n} U_{n,i}$. For ε-BAI, LUCB stops when $L_{n,\hat{\mu}_n} + \varepsilon \ge \max_{i \neq \hat{\mu}_n} U_{n,i}$.

**Fixed-budget BAI algorithms** We consider Successive Reject (SR) [1] and Sequential Halving (SH) [25]. SR eliminates one arm with the worst empirical mean at the end of each phase, and SH eliminated half of them but drops past observations between each phase. Within each phase, both algorithms use a round-robin uniform sampling rule on the remaining active arms. It is possible to convert the fixed-budget SH algorithm into an anytime algorithm by using the doubling trick. It considers a sequences of algorithms that are run with increasing budgets $(T_k)_{k \ge 1}$, with $T_{k+1} = 2T_k$ and $T_1 = 2K[\log_2 K]$, and recommend the answer outputted by the last instance that has finished to run. It is well known that the “cost” of doubling is to have a multiplicative factor 4 in front of the hardness constant. The first two-factor is due to the fact that we forget half the observations. The second two-factor is due to the fact that we use the recommendation from the last instance of SH that has finished. The doubling version of SR and SH are named Doubling SR (DSR) and Doubling SH (DSH).

**Reproducibility** Our code is implemented in Julia 1.9.0, and the plots are generated with the StatsPlots.jl package. Other dependencies are listed in the Readme.md. The Readme.md file also provides detailed julia instructions to reproduce our experiments, as well as a script.sh to run them all at once. The general structure of the code (and some functions) is taken from the
tidnabbil library. This library was created by [11], see https://bitbucket.org/wmkoolen/tidnabbil. No license were available on the repository, but we obtained the authorization from the authors. Our experiments are conducted on an institutional cluster with 4 Intel Xeon Gold 5218R CPU with 20 cores per CPU and an x86_64 architecture.

## J.2 Supplementary experiments

For the sake of space, we only presented a small subset of our experiments in Section 5, hence we provide additional empirical evidence below. In Appendix J.2.1, we assess the impact of the choice of the slack $\epsilon_0$ on the empirical performance of EB-TC$_{\epsilon_0}$ with IDS or with fixed proportion $\beta = 1/2$. Appendix J.2.2 complements Section 5 by providing more comparison between EB-TC$_{\epsilon_0}$ and existing algorithms. In Appendix J.2.3, we study the BAI problem and show the empirical performance of the EB-TC($\epsilon_n$)$_{n>K}$ with fixed proportion $\beta = 1/2$ and using varying slack parameters ($\epsilon_n$)$_{n>K}$ (as described in Sections 3 and 4). As in Section 5, we consider $\delta = 0.01$ and use the heuristic threshold $c(n, \delta) = \log((1 + \log n)/\delta)$, which yields an empirical error which is several orders of magnitude lower than $\delta$.

### J.2.1 Numerical simulations on EB-TC$_{ε_0}$

Appendix J.2.1 is meant to be a sensitivity analysis of the EB-TC$_{ε_0}$ algorithm. It will allow us to numerically substantiate our recommendation to the practitioner on how to set the slack $\epsilon_0$, and why using IDS yields better empirical performance. For slacks $\epsilon_0 \in \{0.15, 0.1, 0.05\}$, we will consider the EB-TC$_{ε_0}$ algorithms with IDS proportions and fixed proportions $\beta = 1/2$.

<figure><img src="image_9.png" /><figcaption>Figure 4: Empirical stopping time with stopping rule (3) using $(\epsilon, \delta) = (0.1, 0.01)$ on (a)“sparse” instances“, (b) $\alpha = 0.3$” instances and (c) “$\alpha = 0.6$” instances. “c-” denotes fixed $\beta = 1/2$, without refers to IDS.</figcaption></figure>

**Large sets of arms** First, we evaluate the impact of larger number of arms (up to $K = 1000$). The “$\alpha = 0.6$” scenario of [18] sets $\mu_i = 1 - ((i-1)/(K-1))^{\alpha}$ for all $i \in [K]$. The “sparse” scenario of [18] sets $\mu_1 = 1/4$ and $\mu_i = 0$ otherwise. We average on 100 runs, and the standard deviations are displayed.

In Figure 4, we see that all instances of EB-TC$_{ε_0}$ with IDs or fixed $\beta = 1/2$ have the same scaling with the dimension $K$. Figure 4 also reveals that using IDS instead of fixed $\beta = 1/2$ consistently yields smaller empirical stopping time. Therefore, IDS should be preferred to choosing fixed $\beta = 1/2$. Finally, Figure 4 shows that better empirical performance are obtained when using a slack $\epsilon_0$ which matches the error $\epsilon$, i.e. choosing $\epsilon_0 = \epsilon$ to tackle $\epsilon$-BAI. While choosing $\epsilon_0 > \epsilon$ only slightly damage the empirical performance, taking $\epsilon_0 < \epsilon$ is clearly detrimental to the empirical performance.
<figure><img src="image_10.png" /><figcaption>Figure 5: Empirical stopping time on random instances with stopping rule (3) using (left) $(\varepsilon, \delta) = (0.05, 0.01)$ and (right) $(\varepsilon, \delta) = (0.1, 0.01)$ with (top) $K = 5$, (middle) $K = 10$ and (bottom) $K = 20$. “c-” denotes fixed $\beta = 1/2$, without refers to IDS.</figcaption></figure>

**Random instances** We further investigate the phenomenon described above on random instances. For $\varepsilon \in \{0.05, 0.1\}$, we assess the performance on 1000 random Gaussian instances with $K = 5$ (resp. $K = 10$ and $K = 10$) such that $\mu_1 = 1$, $\mu_i \sim \mathcal{U}([1 - \varepsilon, 1])$ for $i \in \{2\}$ (resp. $i \in \{2, 3\}$ and $i \in \{2, 3, 4\}$) and $\mu_i \sim \mathcal{U}([0, 1 - \varepsilon])$ for $i \ge 3$ (resp. $i \ge 4$ and $i \ge 6$), hence $\mathcal{I}_{\varepsilon}(\mu) = [2]$ (resp. $\mathcal{I}_{\varepsilon}(\mu) = [3]$ and $\mathcal{I}_{\varepsilon}(\mu) = [5]$). We display the boxplots of the empirical stopping time on 1000 runs.

In Figure 5, the tendencies glimpsed by inspecting Figure 4 are more apparent. Figure 5 shows that better empirical performance are obtained when using a slack $\varepsilon_0$ which matches the error $\varepsilon$, i.e. choosing $\varepsilon_0 = \varepsilon$ to tackle $\varepsilon$-BAI. We also see that the empirical gain of taking $\varepsilon_0 = \varepsilon$ is increasing with the dimension $K$. Figure 5 shows that $\varepsilon_0 > \varepsilon$ slightly damage the empirical performance: the larger the missmatch $\varepsilon_0 - \varepsilon$ is, the worse the performances are. Moreover, Figure 5 highlights how choosing $\varepsilon_0 < \varepsilon$ is highly detrimental to the empirical performance. Finally, we see that there is a mild advantage in using IDS over fixed $\beta = 1/2$. Note that the mild empirical gain of adaptive proportions is a known phenomenon which was studied empirically in [20], and larger gains can be observed for “two-groups” instances. Intuitively, the characteristic times $T_{\varepsilon}(\mu)$ and $T_{\varepsilon, 1/2}(\mu)$ are very close to each other on average and the difference is the largest when all the sub-optimal arms have the same mean. Therefore, on average, using IDS has mild gain compared to using fixed $\beta = 1/2$. This worst-case scenario of the “two-groups” instances is studied in Figure 7.
<table><caption>Table 3: Specific instances from [16] with corresponding $\epsilon$.</caption><thead><tr><th rowspan="2">ε</th><th rowspan="2">Instance</th><th rowspan="2">|I<sub>ε</sub>(μ)|</th><th colspan="6">Arms</th></tr><tr><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>0.1</td><td>μ<sub>1</sub></td><td>1</td><td>0.7</td><td>0.55</td><td>0.5</td><td>0.4</td><td>0.2</td><td>-</td></tr><tr><td>0.15</td><td>μ<sub>2</sub></td><td>3</td><td>0.8</td><td>0.75</td><td>0.7</td><td>0.6</td><td>0.5</td><td>0.4</td></tr><tr><td>0.1</td><td>μ<sub>3</sub></td><td>3</td><td>0.6</td><td>0.6</td><td>0.55</td><td>0.45</td><td>0.3</td><td>0.2</td></tr></tbody></table>

**Specific instances** We continue the experimental validation of our the phenomenon described above by considering the three specific instances from the experimental section of [16] which are described in Table 3. Instance $\mu_3$ corresponds to the specific instances studied in Section 5. It is particularly interesting since it has two best arms, a third $\epsilon$-good arm which is equally distant from $\epsilon$ than the bad arm with largest mean, and has two additional bad arms. Instance $\mu_2$ has also three $\epsilon$-good arms, which are equally spaced, and three bad arms. Instance $\mu_1$ has only one $\epsilon$-good arm, and four bad arms. We display the boxplots of the empirical stopping time on 1000 runs, and the empirical simple regret on 10000 runs (with associated standard deviation).

<figure><img src="image_11.png" /><figcaption>Figure 6: (Left) Empirical stopping time for the stopping rule (3) using $\delta = 0.01$ and (right) empirical simple regret on instances (top) $\mu_1$ with $\epsilon = 0.1$, (middle) $\mu_2$ with $\epsilon = 0.15$ and (bottom) $\mu_3$ with $\epsilon = 0.1$. “c-” denotes fixed $\beta = 1/2$, without refers to IDS.</figcaption></figure>

The left column of Figure 6 confirms our previous observations: taking $\epsilon = \epsilon_0$ yields the best performance, taking $\epsilon_0 > \epsilon$ slightly damage performance and taking $\epsilon_0 < \epsilon$ highly damage performance.
Figure 6 (middle left) shows that the larger the mismatch $\varepsilon - \varepsilon_0$ is, the worse the performances are.

The right column of Figure 6 reveals that the choice of $\varepsilon_0$ has few impact on the empirical simple regret, at least for reasonably chosen $\varepsilon_0$. Likewise, there is few differences between IDS proportions and fixed $\beta = 1/2$. The good empirical performance of IDS proportions as regards the simple regret hints that EB-TC$_{\varepsilon_0}$ with IDS has (most likely) similar theoretical guarantees as the ones obtained in Section 4 for EB-TC$_{\varepsilon_0}$ with fixed $\beta = 1/2$ (Theorem 3 and Corollary 1). This is an interesting open problem that we leave for future work.

**Two-groups instances** We conclude our sensitivity analysis on EB-TC$_{\varepsilon_0}$ by considering the “two-groups” instances $\mu \in \{0.6, 0.4\}^{10}$ for varying number of best arms, i.e. $|i^*(\mu)| \in [8]$. Our aim is to assess the impact of having multiple best arms on the empirical stopping time. We average on 1000 runs, and the standard deviations are displayed.

<figure><img src="image_12.png" /><figcaption>Figure 7: Empirical stopping time with stopping rule (3) using $(\varepsilon, \delta) = (0.1, 0.01)$ on instances $\mu \in \{0.6, 0.4\}^{10}$ for varying $|i^*(\mu)|$. “c-” denotes fixed $\beta = 1/2$, without refers to IDS.</figcaption></figure>

On this specific instances where the number of arms is fixed, it would be intuitive to think that the problem is easier when there are more best arms. However, this is actually the opposite since there less bad arms (which were easy to detect) and more good arms which need to be estimated well enough. While Figure 7 shows how poor the performances are when taking $\varepsilon_0 < \varepsilon$, it also shows that the impact of having multiple best arms is rather mild for slacks $\varepsilon_0 \ge \varepsilon$. We will see in Figure 12 that EB-TC$_{\varepsilon_0}$ is the most resilient algorithm with respect to multiple arms, meaning that its slope is the smallest.

“Two-groups” instances are interesting since they are the instances for which the ratio $T_{\varepsilon,1/2}(\mu)/T_{\varepsilon}(\mu)$ is the largest. Using Lemma 9 and the theoretical results of [20] (see their Lemma C.6), we conjecture that $T_{\varepsilon,1/2}(\mu) \le r_K T_{\varepsilon}(\mu)$ with $r_K = 2K/(1 + \sqrt{K-1})^2$ and that the equality occurs for “two-groups” instances. Since $r_{10} = 5/4$, using fixed $\beta = 1/2$ should be roughly 25% slower than using IDS. While Figure 7 confirms that using IDS yields better empirical performance than using fixed $\beta = 1/2$, the empirical ratio between their performance is lower than the one suggested by the theory.

<table><caption>Table 4: Comparison between the original sampling rule and the modified sampling rule for BAI algorithms when combined with the GLR$_{\varepsilon}$ stopping rule (3) using $(\varepsilon, \delta) = (0.1, 0.01)$. We display the empirical stopping time (and standard deviation) on random instances with $K \in \{5, 10, 20\}$.</caption><thead><tr><th>K</th><th>T3C</th><th>ε-T3C</th><th>EB-TCI</th><th>ε-EB-TCI</th></tr></thead><tbody><tr><td>5</td><td>9138 (±7988)</td><td>2259 (±1243)</td><td>22505 (±66624)</td><td>2290 (±1202)</td></tr><tr><td>10</td><td>17418 (±9726)</td><td>3793 (±1524)</td><td>58086 (±135655)</td><td>3975 (±1509)</td></tr><tr><td>20</td><td>30771 (±13038)</td><td>6631 (±1992)</td><td>115861 (±195797)</td><td>6905 (±1879)</td></tr></tbody></table>
## J.2.2 Comparison with modified BAI algorithms

Appendix J.2.2 is meant to provide further empirical evidence that EB-TC<sub>ε₀</sub> outperforms its competitors on different tasks and for different types of instances. Overall, we will use the same instances as used in Appendix J.2.1 since they provide a wide range of interesting problems. Throughout this section, we will be using EB-TC<sub>ε₀</sub> with slack ε₀ = 0.1. While IDS proportions are used for the experiments on the empirical stopping time, we use fixed β = 1/2 for the empirical simple regret.

<figure><img src="image_13.png" /><figcaption>Figure 8: Empirical stopping time on (a) “α = 0.6” instances and (b) “sparse” instances for varying K and stopping rule (3) using (ε, δ) = (0.1, 0.01). The BAI algorithms T3C, EB-TCI and TTUCB are modified to be ε-BAI ones.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 9: Empirical stopping time on random instances with stopping rule (3) using (left) (ε, δ) = (0.05, 0.01) and (right) (ε, δ) = (0.1, 0.01) with (top) K = 5, (middle) K = 10 and (bottom) K = 20. The BAI algorithms T3C, EB-TCI, TTUCB, TaS, FWS, DKM are modified for ε-BAI.</figcaption></figure>
As benchmarks we consider modified BAI which are tailored to tackle $\varepsilon$-BAI, and we combine them with the GLR$_\varepsilon$ stopping rule. One can still wonder whether the unmodified sampling rule would perform well for $\varepsilon$-BAI when combined with the GLR$_\varepsilon$ stopping rule. While we could hope that modifying the stopping rule is enough, our experiments reveal that it is not the case. If we don't adapt the sampling rule as well, Table 4 shows that the empirical stopping time can be more than ten times larger than their modified version.

**Large sets of arms** To complement Figure 2(a), we consider the “$\alpha = 0.6$” instances and “sparse” instances for varying $K$. We average on 100 runs, and the standard deviations are displayed.

Figure 8 confirms the observations made in Figure 2(a). We see that $\text{EB-TC}_\varepsilon$ performs on par with the $\varepsilon$-T3C, and outperforms the other algorithms. It also highlights that the regularization ensured by the $\text{TC}\varepsilon$ challenger is sufficient to ensure enough exploration. As a consequence, other exploration mechanism are superfluous when using Top Two algorithms for $\varepsilon$-BAI (e.g. using TS/UCB leader or TCI challenger).

**Random instances** For $\varepsilon \in \{0.05, 0.1\}$, we assess the performance on 1000 random Gaussian instances with $K \in \{5, 10, 20\}$ as described above. We display the boxplots of the empirical stopping time on 1000 runs.

Figure 9 confirms that $\text{EB-TC}_{\varepsilon_0}$ performs on par with the state-of-the-art $\varepsilon$-BAI algorithms and greatly outperform $\varepsilon$-DKM, LUCB and uniform sampling. Interestingly, for larger sets of arms ($K = 20$), $\text{EB-TC}_{\varepsilon_0}$ appears to be more robust than its competitors, closely followed by $\varepsilon$-T3C and $\varepsilon$-EB-TCI. The performance $\varepsilon$-TTUCB, $\varepsilon$-TaS and $\varepsilon$-FWS is slightly worse, while the one of $\varepsilon$-DKM is greatly impacted. LUCB seems relatively robust to larger sets of arms, but it is still significantly worse than $\text{EB-TC}_{\varepsilon_0}$. It is even the best when considering slack $\varepsilon_0 = \varepsilon$ in the bottom row of Figure 9. The slightly worse (but still competitive) empirical performance of $\text{EB-TC}_{\varepsilon_0}$ in the top row of Figure 9 is explained by the slack $\varepsilon_0 = 0.1$ which differs from the error $\varepsilon = 0.05$ considered in the GLR$_\varepsilon$ stopping rule.

**Specific instances** To complement Figure 2(b), we consider the two other instances from Table 3. We display the boxplots of the empirical stopping time on 1000 runs, and the empirical simple regret on 10000 runs (with associated standard deviation).

The left column of Figure 10 validates the previous conclusions as regards the good empirical performance of $\text{EB-TC}_{\varepsilon_0}$ compare to existing $\varepsilon$-BAI algorithms. We also see that it seems to perform even better when there are multiple $\varepsilon$-good arms and multiple best arms, i.e. $|i^*(\mu)| > 1$. The right column of Figure 10 corroborates the observations made in Figure 2(b): $\text{EB-TC}_{\varepsilon_0}$ outperforms uniform sampling, as well as DSR and DSH.

**Two groups** We consider the “two-groups” instances $\mu \in \{0.6, 0.4\}^{10}$ for varying number of best arms, i.e. $|i^*(\mu)| \in [8]$. We average on 1000 runs, and the standard deviations are displayed.

Figure 11 reveals that $\text{EB-TC}_{\varepsilon_0}$ is the most robust to increased number of best arms, i.e. its slope is the smallest. The good performance of $\text{EB-TC}_{\varepsilon_0}$ is closely followed by other Top Two algorithms. This confirms that additional regularization mechanisms (e.g. TS/UCB leader or TCI challenger) are superfluous since the $\text{TC}\varepsilon$ challenger is enough to ensure sufficient exploration. $\varepsilon$-TaS and $\varepsilon$-FWS have slightly worse slope, and the one of $\varepsilon$-DKM seems to become less steep after a large initial increase. The highest slope is achieved by LUCB. Quite surprisingly, uniform sampling seems to reach a plateau after which it is scaling better than $\text{EB-TC}_{\varepsilon_0}$ (in terms of slope), while still having worse empirical performance. It would be interesting to quantify theoretically the good scaling of $\text{EB-TC}_{\varepsilon_0}$ with respect to increased number of best arms.
<figure><img src="image_15.png" /><figcaption>Figure 10: (Left) Empirical stopping time for the stopping rule (3) using $\delta = 0.01$ and (right) empirical simple regret on instances (top) $\mu_1$ with $\varepsilon = 0.1$, (middle) $\mu_2$ with $\varepsilon = 0.15$ and (bottom) $\mu_3$ with $\varepsilon = 0.1$. The BAI algorithms T3C, EB-TCI, TTUCB, TaS, FWS, DKM are modified to be $\varepsilon$-BAI ones.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Figure 11: Empirical stopping time with stopping rule (3) using $(\varepsilon, \delta) = (0.1, 0.01)$ on instances $\mu \in \{0.6, 0.4\}^{10}$ for varying $|i^*(\mu)|$. The BAI algorithms T3C, EB-TCI, TTUCB, TaS, FWS, DKM are modified to be $\varepsilon$-BAI ones.</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>Figure 12: Empirical simple regret on instances $\mu \in \{0.6, 0.4\}^{10}$ for $|i^*(\mu)| \in [6]$, i.e. (top left) $|i^*(\mu)| = 1$ and (bottom right) $|i^*(\mu)| = 6$.</figcaption></figure>

Figure 12 provides additional empirical validation that EB-TC$_{ε_0}$ outperforms uniform sampling as well as DSR and DSH in terms of empirical simple regret. While the empirical stopping time increased with the number of best arms, Figure 12 confirms the intuition that the problem gets easier with respect to the simple regret. First, the range of empirical simple regret becomes smaller with increased number of best arms. This was expected as we have more chances to recommend one of the best arms at early stage even though this recommendation is close to random. Second, we observe a steeper decrease of the empirical simple regret with increased number of best arms. Likewise, this is a natural phenomenon since the collected data will reveal that there multiple good options very fast.

Quite surprisingly, EB-TC$_{ε_0}$ is still better than DSH when the number of best arms increases. To understand why it is surprising, we recall that the exponential decrease of DSH's probability of error is linear with a rate proportional to a hardness constant $H_{\text{DSH}}(\mu)$. By definition, $H_{\text{DSH}}(\mu)$ gets small when there are multiple best arms, hence we would expect to observe lower empirical simple regret (i.e. a “speed-up”). In contrast, our hardness constant $H_1(\mu, \epsilon_0) = K(2\Delta_{\min}^{-1} + 3\epsilon_0^{-1})^2$ does not enjoy such property. Therefore, we would expect that DSH will outperform EB-TC$_{ε_0}$ when the number of best arms increases. Theoretically proving that EB-TC$_{ε_0}$ has a better scaling than the one given in Theorem 3 is still an open problem. Solving it would allow to better understand its good empirical performance on this task.

**Fixed-budget performance** In addition, we compare the performance of EB-TC$_{ε_0}$ with $ε_0$ and $\beta = 1/2$ to the one of SR and SH. Since SR and SH are fixed-budget algorithms, we ran a different instance for each budget $T$. Therefore, this comparison gives an unfair advantage to the fixed-budget
algorithms which fully leverage the knowledge of $T$ but have no theoretical guarantees at time $n \neq T$ (even at time $T \pm 1$). As a result, the empirical performances of SR and SH are better than the ones of DSR and DSH. We consider the instances from Table 3, as well as “two-groups” instances.

<figure><img src="image_18.png" /><figcaption>Figure 13: (Left) Empirical simple regret and (right) empirical error on instances (top to bottom) $\mu_3 = (0.6, 0.6, 0.55, 0.45, 0.3, 0.2)$, $\mu_2 = (0.8, 0.75, 0.7, 0.6, 0.5, 0.4)$, $\mu_1 = (0.7, 0.55, 0.5, 0.4, 0.2)$ and $\mu \in \{0.6, 0.4\}^{10}$ with $|i^*(\mu)| \in \{1, 3\}$. Average over 200 runs. We ran a different instance of SR and SH for each budget $T$.</figcaption></figure>
Overall, according to Figure 13, EB-TC<sub>ε₀</sub> seems to perform on par with SR and SH in all instances considered, and to outperform SH for some instances. In our experiments, we consider SH in which the samples are dropped between each phase, as analyzed theoretically in [1]. This loss of information explains why SR has better empirical performance than SH. To the best of our knowledge, there is no theoretical analysis for the heuristic SH where all the samples are preserved, even though it has better empirical performance.

### J.2.3 Varying slack parameter

In Appendix J.2.3, we study the BAI problem. Those experiments have two goals: (1) sensitivity analysis of EB-TC<sub>(ε<sub>n</sub>)<sub>n</sub></sub> described in Section 3 and (2) performance assessment of EB-TC<sub>ε₀</sub> on BAI problems. We consider fixed proportions β = 1/2, and use ε₀ = 0.1 for EB-TC<sub>ε₀</sub>. For the rate of decrease of (ε<sub>n</sub>)<sub>n</sub>, we will be considering two archetypal choices: (a) polynomial by taking ε<sub>n</sub> = n<sup>-α/2</sup> and (b) polylogarithmic by taking ε<sub>n</sub> = log(n)<sup>-α/2</sup>. We compare empirically those two rates of decrease for different choices of α, namely α ∈ {0.05, 0.1, 0.5}. To tackle BAI, we consider the GLR<sub>0</sub> stopping rule (3) with (ε, δ) = (0, 0.01) and the heuristic threshold c(n, δ) = log((1 + log n)/δ). Even though this choice is not sufficient to prove (0, δ)-PAC, it yields an empirical error which is several orders of magnitude lower than δ. As benchmark, we use the unmodified BAI algorithms.

**Random instances** We assess the performance on 1000 random Gaussian instances with K ∈ {5, 10, 20} such that μ₁ = 1 and μᵢ ~ U([0.5, 0.8]) for i ≠ 1. We display the boxplots of the empirical stopping time on 1000 runs.

<figure><img src="image_19.png" /><figcaption>Figure 14: Empirical stopping time for the stopping rule (3) using (ε, δ) = (0, 0.01) on random instances with (a) K = 5, (b) K = 10 and (c) K = 20. “|” denotes εn = log(n)<sup>-α/2</sup>, “p” denotes εn = n<sup>-α/2</sup>. “a..” refers to α ∈ {0.5, 0.1, 0.05}.</figcaption></figure>

The most striking feature of Figure 14 is that it reveals how poor the performance of EB-TC<sub>(ε<sub>n</sub>)<sub>n</sub></sub> can be for many choices of (ε<sub>n</sub>)<sub>n</sub>. For the considered α, we observe that polynomial decrease is always bad since it yields roughly the same empirical performance as uniform sampling. This can be explained by the fact that this decrease is too fast, hence EB-TC<sub>(ε<sub>n</sub>)<sub>n</sub></sub>, will ressemble EB-TC<sub>0</sub> which is known to have poor empirical performance [21]. For the considered α, we see that polylogarithmic decrease is often bad, except for α = 0.5. In that case, it performs on par with TaS, slightly worse than standard Top Two algorithms for BAI and better than LUCB and uniform sampling. This can be explained by the fact that EB-TC<sub>(ε<sub>n</sub>)<sub>n</sub></sub> is similar to uniform sampling when the decrease is too slow. The above sensitivity analysis truly shows how difficult it is to choose (ε<sub>n</sub>)<sub>n</sub> beforehand. The
best “trade-off” between a slow decrease (yet not too slow) highly depends on the complexity of the unknown instance. While EB-TC<sub>(ε<sub>n</sub>)</sub>, reaches asymptotic optimality for BAI, we recommend the practitioner to use other Top Two algorithms which enjoy the same theoretical guarantees and better empirical performance. When one needs to have a deterministic algorithms, EB-TCI seems to be the best. Without the deterministic constraint, T3C has great performance.

In Figure 14, we also see that, when combined with the GLR₀ stopping rule, EB-TC<sub>ε₀</sub> has good empirical performance for BAI. It outperforms EB-TC<sub>(ε<sub>n</sub>)</sub>, performs on par with TaS and is only slightly worse than standard Top Two algorithms for BAI. Experiments conducted in Appendix J.2.1 already provide experimentally confirmation that EB-TC<sub>ε₀</sub> has still good empirical performance on ε-BAI problems when ε₀ ≥ ε. Theoretically, Theorem 1 provide some intuition on why this is true. It shows that the gap between the asymptotic lower bound T₀(μ) and the asymptotic upper bound of EB-TC<sub>ε₀</sub> is bounded by

$$ \frac{T_{\epsilon_0, 1/2}(\mu)}{T_0(\mu)} \left(1 + \frac{\epsilon_0}{\Delta_{\min}}\right)^2 \le 4 \frac{\sum_{i \ne i^*} (\Delta_i + \epsilon_0)^{-2}}{\sum_{i \ne i^*} \Delta_i^{-2}} \left(1 + \frac{\epsilon_0}{\Delta_{\min}}\right)^2 \approx \begin{cases} 4 & \text{if } \epsilon_0 \gg \Delta_{\min}, \\ 4 & \text{if } \epsilon_0 \ll \Delta_{\min}, \end{cases} $$

where we used Lemmas 6, 9 and 7.

**Specific instances** We consider the two instances μ₁ and μ₂ from Table 3 with ε = 0. Since most theoretical guarantees on BAI algorithms assume that there is a unique best arm, we don't study μ₃. We display the boxplots of the empirical stopping time on 1000 runs.

<figure><img src="image_20.png" /><figcaption>Figure 15: Empirical stopping time for the stopping rule (3) using (ε, δ) = (0, 0.01) on instances (a) μ₁ and (b) μ₂. “l” denotes εₙ = log(n)⁻¹/², “p” denotes εₙ = n⁻¹/².</figcaption></figure>

Figure 15 confirms the empirical observations from Figure 14. Overall, EB-TC<sub>(ε<sub>n</sub>)</sub> performs poorly and EB-TC<sub>ε₀</sub> has good empirical performance for BAI.