### H.1.1. PROOF OF LEMMA 54

Since $T$ is such that $h(T) > (K + \frac{1}{1-\xi_3})^2$, we have $h(T) \ge K^2$ and $\xi_3 < 1 - \frac{1}{\sqrt{h(T)-K}}$. In particular, for all $t \in \{h(T), \dots, T\}$ and all $s \in \{\sqrt{t}-K, \dots, t\}$, $\xi_3 + \frac{1}{s} < 1$. Then,

$$ \mathbb{P}(\mathcal{E}_T^c) \le \sum_{t=h(T)}^T \sum_{a=1}^K \left[ \mathbb{P}(|\mu_{t,a} - \mu_a| \ge \xi_1) + \mathbb{P}(\sigma_{a,t}^2 \ge \sigma_a^2 \xi_2) + \mathbb{P}\left(\sigma_{a,t}^2 \le \frac{\sigma_a^2}{\xi_2}\right) \right] $$

By forced exploration, for $t \ge h(T)$ one has $N_{t,a} \ge (\sqrt{t}-K/2)_+ - 1 \ge \sqrt{t}-K$ for every arm $a$. In the proof of Lemma 19 in Garivier and Kaufmann (2016) it was shown using a union bound over time and Lemma 29 that, for all $t \in [h(T), T]$,

$$ \mathbb{P}(|\mu_{t,a} - \mu_a| \ge \xi_1) \le \frac{2e^{-(\sqrt{t}-K)\frac{\xi_1^2}{2\sigma_a^2}}}{1 - e^{-\frac{\xi_1^2}{2\sigma_a^2}}}. $$

Since we use the same method to show our result on the variance, the proof for the mean is omitted.

Let $\hat{\sigma}_{a,s}^2$ be the empirical variance of the first $s$ reward from arm $a$ (such that $\hat{\sigma}_{a,N_{t,a}}^2 = \sigma_a^2$). We adopt their proof strategy to derive the equivalent upper bound on the concentration of the variance.

$$ \begin{aligned} \mathbb{P}(\sigma_{a,t}^2 \ge \sigma_a^2 \xi_2) &= \mathbb{P}(\sigma_{a,t}^2 \ge \sigma_a^2 \xi_2, N_{t,a} \ge \sqrt{t}-K) \\ &\le \sum_{s=\sqrt{t}-K-1}^{t-1} \mathbb{P}(\hat{\sigma}_{a,s+1}^2 \ge \sigma_a^2 \xi_2) \le \sum_{s=\sqrt{t}-K-1}^{t-1} \exp\left(-\frac{s}{2}\left(h\left(\xi_2 + \frac{1}{s}\right) - 1\right)\right) \end{aligned} $$

The first inequality is obtained by taking a union bound over the values of $N_{t,a} \in [\sqrt{t}-K, t]$. The second inequality is obtained by Corollary 27 with $x = \xi_2 + \frac{1}{s} > 1$. Using that $h(x) = x - \log(x)$ and $\log(1+x) \le x$, direct computations yield that

$$ \begin{aligned} & sh\left(\xi_2 + \frac{1}{s}\right) = s\xi_2 + 1 - s\log(\xi_2 + \frac{1}{s}) = sh(\xi_2) + 1 - s\log\left(1 + \frac{1}{s\xi_2}\right) \ge sh(\xi_2) + 1 - \frac{1}{\xi_2}, \\ & \sum_{s=\sqrt{t}-K-1}^{t-1} \left(e^{-\frac{1}{2}(h(\xi_2)-1)}\right)^s \le \frac{1}{1 - e^{-\frac{1}{2}(h(\xi_2)-1)}} e^{-\frac{(\sqrt{t}-K)-1}{2}(h(\xi_2)-1)}. \end{aligned} $$

Putting those together, we obtain, for all $t \in [h(T), T]$,

$$ \mathbb{P}(\sigma_{a,t}^2 \ge \sigma_a^2 \xi_2) \le \frac{e^{-\frac{1}{2}\left(1-\frac{1}{\xi_2}\right)}}{1 - e^{-\frac{1}{2}(h(\xi_2)-1)}} e^{-\frac{(\sqrt{t}-K)-1}{2}(h(\xi_2)-1)}. $$

The same manipulations using Corollary 27 with $x = \xi_3 + \frac{1}{s} \in (0, 1)$ for all $s \in [\sqrt{t}-K, t]$ and all $t \in [h(T), T]$ (see above by choice of $T$), yield that, for all $t \in [h(T), T]$,

$$ \mathbb{P}(\sigma_{a,t}^2 \le \sigma_a^2 \xi_3) \le \frac{e^{-\frac{1}{2}\left(1-\frac{1}{\xi_3}\right)}}{1 - e^{-\frac{1}{2}(h(\xi_3)-1)}} e^{-\frac{(\sqrt{t}-K)-1}{2}(h(\xi_3)-1)}. $$
Finally, letting

$$C = \frac{1}{2} \min \left\{ \frac{\xi_1^2}{\max_{a \in [K]} \sigma_a^2}, h(\xi_2) - 1, h(\xi_3) - 1 \right\} \quad \text{and}$$

$$B = \sum_{a=1}^{K} \left( \frac{2e^{\frac{K \xi_1^2}{2\sigma_a^2}}}{1 - e^{-\frac{\xi_1^2}{2\sigma_a^2}}} + \frac{e^{\frac{K-1}{2}(h(\xi_2) - 1) - \frac{1}{2}(1-\frac{1}{\xi_2})}}{1 - e^{-\frac{1}{2}(h(\xi_2) - 1)}} + \frac{e^{\frac{K-1}{2}(h(\xi_3) - 1) - \frac{1}{2}(1-\frac{1}{\xi_3})}}{1 - e^{-\frac{1}{2}(h(\xi_3) - 1)}} \right),$$

one obtains

$$\mathbb{P}(\mathcal{E}_T^c) \le \sum_{t=h(T)}^{T} B \exp(-\sqrt{t}C) \le BT \exp(-\sqrt{h(T)}C) = BT \exp(-CT^{1/8}).$$

## H.2. Wrapped β-EB-TCI

Showing an asymptotic upper bound on the expected sample complexity of β-EB-TCI and β-EB-EVTCI can be done with similar asymptotic arguments as when the variance is known (Shang et al., 2020). We will use the unified analysis of Top Two algorithms introduced in Jourdan et al. (2022), which highlights simple properties that the leader and the challenger should satisfy to obtain the desired upper bound. While they introduced it for single-parameter exponential families and bounded distributions, it also allows to cope for our two-parameters setting. The proof is composed of three steps: showing sufficient exploration of all arms, proving that the expectation of the convergence time towards the β-optimal allocation is finite and then concluding on the asymptotic upper bound.

To ensure sufficient exploration, we assume that $\min_{a \ne b} |\mu_a - \mu_b| > 0$, i.e. all the arms have distinct means. To our knowledge, this assumption is shared by all Top Two algorithms analysis.

### H.2.1. β-EB-TCI

Let $a^* = a^*(\mu)$. Since the proofs share the same structure as in Jourdan et al. (2022), we detail the one for β-EB-TCI and highlight the differences for β-EB-EVTCI. The β-optimal allocation for Gaussian with unknown variance is defined as

$$w_{\beta}^{*}(\mu, \sigma^2) = \arg \max_{w \in \Delta_K, w_{a^*} = \beta} \min_{a \neq a^*} \inf_{u \in \mathbb{R}} \sum_{b \in \{a^*, a\}} w_b \log \left( 1 + \frac{(\mu_b - u)^2}{\sigma_b^2} \right).$$

In Russo (2016) and Jourdan et al. (2022), they show the β-optimal allocation was unique for any single-parameter exponential families and for bounded distributions. Since the proof only relies on strict convexity already shown in Appendix C.2, it is straightforward to see that $w_{\beta}^*(\mu, \sigma^2)$ is a singleton (Property 1 in Jourdan et al. (2022)), denoted by $\{w^{\beta}\}$, such that $\min_{a \in [K]} w_a^{\beta} > 0$.

Before delving into the specifics of the proof, Lemma 57 gathers concentration results on which the subsequent analysis heavily relies on.

**Lemma 57** There exists a sub-Gaussian random variable $W_{\mu}$ and a sub-exponential random variable $W_{\sigma}$, which are independent, such that almost surely for all $a \in [K]$ and all $t$ such that $N_{t,a} \ge 2$,

$$N_{t,a} | \mu_{t,a} - \mu_a | \le W_{\mu} \log(e + N_{t,a}) \quad \text{and} \quad \left| N_{t,a} \left( \frac{\sigma_{t,a}^2}{\sigma_a^2} - 1 \right) + 1 \right| \le W_{\sigma} \log(e + N_{t,a}).$$
There exists a random variable $W_0 = \max_{a \in [K]} W_a^{-1}$, independent of $W_\mu$, where $W_a/\sigma_a^2 \sim \chi^2(n_0 - 1)$ such that almost surely, for all $a \in [K]$ and all $t$ such that $N_{t,a} \ge n_0$, $N_{t,a}\sigma_{t,a}^2 \ge W_0^{-1}$. In particular, $W_0$ admits a finite mean for $n_0 \ge 4$ and a finite variance for $n_0 \ge 6$, and any random variable which is polynomial in both $W_\sigma$ and $W_\mu$ has a finite expectation.

**Proof** The existence of $W_\mu$ is given by Lemma 73 in Jourdan et al. (2022).

Using Lemma 25, we have for all $a \in [K]$ and $t$ such that $N_{t,a} \ge 2$, $N_{t,a} (\frac{\sigma_{t,a}^2}{\sigma_a^2} - 1) + 1 = S_{N_{t,a}-1,a}$, where $S_{n,a}$ is sub-exponential with $c = 2$ and $-S_{n,a}$ is sub-exponential with $c = -2$ and $S_{n-1,a} + n - 1 = \sum_{s \in [n-1]} Y_{s,a}^2$ is such that $Y_{s,a}$ are i.i.d. $\mathcal{N}(0, 1)$. Using Lemma 72 in Jourdan et al. (2022), $\sup_{N_{t,a} \ge 2} \frac{|S_{N_{t,a}-1,a}|}{\log(e+N_{t,a})}$ is also sub-exponential. By defining $W_\sigma$ as the maximum over the finitely many arms of the above quantity, we obtain that $W_\sigma$ is sub-exponential.

Since the increments $Y_{s,a}^2$ are positive, we have for all $a \in [K]$ and $t$ such that $N_{t,a} \ge n_0$

$$ \frac{\sigma_{t,a}^2}{\sigma_a^2} = \frac{S_{N_{t,a}-1,a} + N_{t,a} - 1}{N_{t,a}} = \frac{\sum_{s \in [N_{t,a}-1]} Y_{s,a}^2}{N_{t,a}} \ge \frac{Z_a}{N_{t,a}}, $$

where $Z_a = \sum_{s \in [n_0-1]} Y_{s,a}^2 \sim \chi^2(n_0 - 1)$. Taking $W_a = \sigma_a^2 Z_a$ and the maximum over $[K]$ yields the result. As maximum of finitely many inverse-chi-squared distributions, $W_0$ admits a finite mean for $n_0 \ge 4$ and a finite variance for $n_0 \ge 6$.

For the independence property between $W_\sigma$ and $W_\mu$ and between $W_0$ and $W_\mu$, this is a direct consequence of the fact that the empirical mean and empirical variance are independent. Therefore, any random variable which is polynomial in both $W_\sigma$ and $W_\mu$ has a finite expectation. ■

Using Lemma 57, it is direct to obtain that, for all $\varepsilon > 0$, there exists $N_\varepsilon$ with $\mathbb{E}_\nu[N_\varepsilon] < +\infty$ such that for all $a \in [K]$ and $t$ such that $N_{t,a} \ge N_\varepsilon$, $|\mu_{t,a} - \mu_a| \le \varepsilon$ and $|\frac{\sigma_{t,a}^2}{\sigma_a^2} - 1| \le \varepsilon$.

As in Qin et al. (2017); Shang et al. (2020); Jourdan et al. (2022), our goal is to upper bound the expectation of the convergence time. For $\varepsilon > 0$, the random variable $T_\beta^\varepsilon$ quantifies the number of samples required for the empirical allocations $\frac{N_t}{t}$ to be $\varepsilon$-close to $w^\beta$:

$$ T_{\beta}^{\varepsilon} \stackrel{\text{def}}{=} \inf \left\{ T \ge 1 \mid \forall t \ge T, \left\| \frac{N_t}{t} - w^\beta \right\|_{\infty} \le \varepsilon \right\}. \qquad (23) $$

Lemma 58 shows that a sufficient condition for asymptotic $\beta$-optimality is to show $\mathbb{E}_\nu[T_\beta^\varepsilon] < +\infty$ for all $\varepsilon$ small enough.

**Lemma 58** Let $(\delta, \beta) \in (0, 1)^2$. Assume that there exists $\varepsilon_1(\mu, \sigma^2) > 0$ such that for all $\varepsilon \in (0, \varepsilon_1(\mu, \sigma^2))$, $\mathbb{E}_\nu[T_\beta^\varepsilon] < +\infty$. Combining the GLR stopping rule (4) with an asymptotically tight family of threshold yields an algorithm such that, for all $(\mu, \sigma^2) \in \mathbb{R}^K \times (\mathbb{R}_+^*)^K$ with $|a^*(\mu)| = 1$,

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

**Proof** Let $\varepsilon_1 = \varepsilon_1(\mu, \sigma^2)$. Let $c_\beta = \frac{1}{2} \min_{a \in [K]} w_a^\beta > 0$ and $\Delta = \min_{a \ne a^*} |\mu_{a^*} - \mu_a| > 0$. Let $\zeta > 0$. By continuity of

$$ (\mu, \sigma^2, w) \mapsto \inf_{x \in \mathbb{R}} \sum_{c \in \{a, b\}} w_c \log \left( 1 + \frac{(\mu_c - x)^2}{\sigma_c^2} \right) \mathbf{1}\{\mu_a > \mu_b\} $$
on $\mathbb{R}^K \times (\mathbb{R}_+^*)^K \times \Delta_K$, there exists $\varepsilon_2 > 0$ such that

$$ 
\begin{aligned}
& \max_{a \in [K]} \left| \frac{N_{t,a}}{t} - w_a^\beta \right| \le \varepsilon_2 \quad , \quad \max_{a \in [K]} |\mu_{t,a} - \mu_a| \le \varepsilon_2 \quad \text{and} \quad \max_{a \in [K]} \left| \frac{\sigma_{t,a}^2}{\sigma_a^2} - 1 \right| \le \varepsilon_2 \\
\implies & \max_{a \in [K]} |\mu_{t,a} - \mu_a| \le \frac{\Delta}{4} \quad \text{and} \quad \frac{1}{t} \min_{a \ne a^*} C_t(a^*, a) \ge \frac{1-\zeta}{T_\beta^*(\mu, \sigma^2)}.
\end{aligned}
$$

Choosing such a $\varepsilon_2$, we take $\varepsilon \in (0, \min\{\varepsilon_1, \varepsilon_2, c_\beta\})$. By assumption, we have $\mathbb{E}_\nu[T_\beta^\varepsilon] < +\infty$, hence $\frac{N_{t,a}}{t} \ge w_a^\beta - \varepsilon \ge c_\beta$ for all $a \in [K]$.

Let $N_\varepsilon$ as described above (obtained with Lemma 57). For all $t \ge c_\beta^{-1}N_\varepsilon$, we have $N_{t,a} \ge N_\varepsilon$ for all $a \in [K]$, hence $\max_{a \in [K]} |\mu_{t,a} - \mu_a| \le \varepsilon \le \varepsilon_2$ and $\max_{a \in [K]} \left| \frac{\sigma_{t,a}^2}{\sigma_a^2} - 1 \right| \le \varepsilon \le \varepsilon_2$. Therefore, we have $\hat{a}_t \in \arg \max_{a \in [K]} \mu_{t,a} = \arg \max_{a \in [K]} \mu_a = a^*$ as $\max_{a \in [K]} |\mu_{t,a} - \mu_a| \le \frac{\Delta}{4}$.

Let $\alpha \in [0, 1]$, $\delta_0 \in (0, 1]$, functions $f, \bar{T} : (0, 1] \to \mathbb{R}_+$ and $C$ as in the definition of an asymptotically tight family of thresholds. In the following, we consider $\delta \le \delta_0$. Let $\kappa > 0$. Let $T \ge \frac{1}{\kappa} \max\{T_\beta^\varepsilon, c_\beta^{-1}N_\varepsilon, \bar{T}(\delta)\}$. Using the definition of the GLR stopping rule (4) with a family of asymptotically tight threshold, we have

$$ 
\begin{aligned}
\min\{\tau_\delta, T\} &\le \kappa T + \sum_{t=\kappa T}^{T} \mathbf{1}\{\tau_\delta > t\} 
&\le \kappa T + \sum_{n=\kappa T}^{T} \mathbf{1}\{\exists a \ne a^*, C_t(a^*, a) \le c_{a^*,a}(N_t, \delta)\} \\
&\le \kappa T + \sum_{n=\kappa T}^{T} \mathbf{1}\{t \frac{1-\zeta}{T_\beta^*(\mu, \sigma^2)} \le f(\delta) + CT^\alpha\} \\
&\le \kappa T + \frac{T_\beta^*(\mu, \sigma^2)}{1-\zeta} (f(\delta) + CT^\alpha).
\end{aligned}
$$

Let $T_\zeta(\delta)$ as

$$ T_\zeta(\delta) \stackrel{\text{def}}{=} \inf \left\{ T \ge 1 \mid \frac{T_\beta^*(\mu, \sigma^2)}{(1-\zeta)(1-\kappa)} (f(\delta) + CT^\alpha) \le T \right\}. $$

For every $T \ge \max\{T_\zeta(\delta), \frac{1}{\kappa} \max\{T_\beta^\varepsilon, c_\beta^{-1}N_\varepsilon, \bar{T}(\delta)\}$, we have $\tau_\delta \le T$, hence

$$ \mathbb{E}_\nu[\tau_\delta] \le \frac{1}{\kappa} \mathbb{E}_\nu[T_\beta^\varepsilon] + \frac{1}{\kappa c_\beta} \mathbb{E}_\nu[N_\varepsilon] + \frac{1}{\kappa} \bar{T}(\delta) + T_\zeta(\delta). $$

As $\mathbb{E}_\nu[T_\beta^\varepsilon] + c_\beta^{-1}\mathbb{E}_\nu[N_\varepsilon] < +\infty$ and $\lim_{\delta \to 0} \frac{\bar{T}(\delta)}{\log(1/\delta)} = 0$, we obtain for all $\zeta, \kappa > 0$

$$ \limsup_{\delta \to 0} \frac{\mathbb{E}_\nu[\tau_\delta]}{\log(1/\delta)} \le \limsup_{\delta \to 0} \frac{T_\zeta(\delta)}{\log(1/\delta)} \le \frac{T_\beta^*(\mu, \sigma^2)}{(1-\zeta)(1-\kappa)}, $$

where the last inequality uses an inversion result. Letting $\zeta$ and $\kappa$ go to zero yields the result. ■

To upper bound the expected convergence time, as prior work we first establish sufficient exploration. Given an arbitrary threshold $L \in \mathbb{R}_+^*$, we define the sampled enough set and its arms with highest mean (when not empty) as

$$ S_t^L \stackrel{\text{def}}{=} \{a \in [K] \mid N_{t,a} \ge L\} \quad \text{and} \quad \mathcal{I}_t^* \stackrel{\text{def}}{=} \arg \max_{a \in S_t^L} \mu_a. \qquad (24) $$
We define the highly and the mildly under-sampled sets

$$ U_t^L \stackrel{\text{def}}{=} \{a \in [K] \mid N_{t,a} < L^{1/6}\} \quad \text{and} \quad V_t^L \stackrel{\text{def}}{=} \{a \in [K] \mid N_{t,a} < L^{5/6}\}, \qquad (25) $$

where we used $L^{1/6}$ and $L^{5/6}$ instead of $\sqrt{L}$ and $L^{3/4}$ as done in Shang et al. (2020). However, Jourdan et al. (2022) noted the results would hold with $L^{\alpha_1}$ and $L^{\alpha_2}$ with $0 < \alpha_1 < \alpha_2 < 1$.

Lemma 59 shows that the transportation cost is strictly positive and increases linearly.

**Lemma 59** Let $\mu \in \mathbb{R}^K$ with $\mu_b < \mu_a$. There exists $L$ with $\mathbb{E}[|L|^\alpha] < +\infty$ for all $\alpha > 0$ and $D_\nu > 0$ such that for $N_{t,a} \ge L$ and $N_{t,b} \ge L$, $C_t(a, b) > LD_\nu$, where $D_\nu > 0$ is a problem dependent constant.

**Proof** Suppose that $N_{t,a} \ge L$ and $N_{t,b} \ge L$, for some $L$ to be determined. First we get

$$ C_t(a, b) \ge \frac{L}{2} \mathbf{1}\{\mu_{t,a} > \mu_{t,b}\} \inf_{x \in \mathbb{R}} \sum_{c \in \{a,b\}} \log \left( 1 + \frac{(\mu_{t,c} - x)^2}{\sigma_{t,c}^2} \right). $$

For any compact interval $\mathcal{I}_C \subseteq \mathbb{R}$, the function defined by

$$ (\mu, \sigma^2) \mapsto \mathbf{1}\{\mu_a > \mu_b\} \inf_{x \in \mathcal{I}_C} \sum_{c \in \{a,b\}} \log \left( 1 + \frac{(\mu_c - x)^2}{\sigma_c^2} \right) $$

is continuous on $\mathbb{R}^K \times (\mathbb{R}_+^*)^K$. For $L$ greater than some $L_1$ with finite moments, we have $\mu_{t,a} > \mu_{t,b}$, $[\mu_b - \varepsilon, \mu_a + \varepsilon] \subseteq \mathcal{I}_C$ and $(\mu_{t,a}, \sigma_{t,a}^2)$ is $\varepsilon$-close to $(\mu_a, \sigma_a^2)$ (and same thing for $(\mu_b, \sigma_b^2)$). The continuity then gives that there exists $L$ with finite moments such that

$$ \inf_{x \in \mathbb{R}} \sum_{c \in \{a,b\}} \log \left( 1 + \frac{(\mu_{t,c} - x)^2}{\sigma_{t,c}^2} \right) \ge \frac{1}{2} \inf_{x \in \mathcal{I}_C} \sum_{c \in \{a,b\}} \log \left( 1 + \frac{(\mu_c - x)^2}{\sigma_c^2} \right). $$

This is strictly positive since $\mu_b < \mu_a$ due to the continuity and strict convexity properties holding for Gaussian with unknown variance. ■

**Lemma 60** Let $D_\nu > 0$ as in Lemma 59. Let $S_t^L$ and $\mathcal{I}_t^*$ as in (24). There exists $L_4$ with $\mathbb{E}_\nu[(L_4)^\alpha] < +\infty$ for all $\alpha > 0$ such that if $L \ge L_4$, for all $t$ such that $S_t^L \ne \emptyset$, for all $(a, b) \in \mathcal{I}_t^* \times (S_t^L \setminus \mathcal{I}_t^*)$, we have $C_t(a, b) \ge LD_\nu$.

**Proof** Applying Lemma 59 yields the result directly. ■

Lemma 61 gives an upper bound on the transportation costs between a sampled enough arm and an under-sampled one.

**Lemma 61** Let $S_t^L$ as in (24). There exists $L_5$ with $\mathbb{E}_\nu[(L_5)^\alpha] < +\infty$ for all $\alpha > 0$ such that for all $L \ge L_5$ and all $t \in \mathbb{N}$,

$$ \forall (a, b) \in S_t^L \times \overline{S_t^L}, \quad C_t(a, b) \le \frac{L}{2} \log \left( 1 + LW_0 (D_1 + 4W_\mu)^2 \right), $$

where $D_1 > 0$ is a problem dependent constant and $W_0, W_\mu$ are the random variables defined in Lemma 57.
**Proof** Let $(a, b) \in S_t^L \times \overline{S_t^L}$ (a is sampled more than L times, b is not). Taking $x = \mu_{t,a}$ yields

$$C_t(a, b) \le \frac{1}{2} N_{t,b} \log \left( 1 + \frac{(\mu_{t,b} - \mu_{t,a})^2}{\sigma_{t,b}^2} \right) \le \frac{L}{2} \log \left( 1 + \frac{(\mu_{t,b} - \mu_{t,a})^2}{\sigma_{t,b}^2} \right),$$

where we used that $b \in \overline{S_t^L}$ and that $C_t(a, b) = 0$ when $\mu_{t,b} \ge \mu_{t,a}$.

By definition of $W_0$ and $W_\mu$, we have for all $k \in [K]$

$$\mu_{t,k} \le \mu_k + W_\mu \log(e + N_{t,k})/N_{t,k} \quad \text{and} \quad \sigma_{t,k}^2 \ge W_k/N_{t,k}.$$

Then, we obtain

$$\frac{(\mu_{t,b} - \mu_{t,a})^2}{\sigma_{t,b}^2} \le \frac{N_{t,b}}{W_b} \left( |\mu_a - \mu_b| + W_\mu \left( \frac{\log(e + N_{t,a})}{N_{t,a}} + \frac{\log(e + N_{t,b})}{N_{t,b}} \right) \right)^2.$$

Since $x \mapsto \frac{\log(e+x)}{x}$ is decreasing on $\mathbb{R}_+$, we have $\frac{\log(e+N_{t,k})}{N_{t,k}} \le 2$ for $N_{t,k} \ge 1$. Then, since $W_0 = \max_{a \in [K]} W_a^{-1}$, we have

$$\frac{(\mu_{t,b} - \mu_{t,a})^2}{\sigma_{t,b}^2} \le L W_0 (|\mu_a - \mu_b| + 4W_\mu)^2,$$

which yields the result by taking $D_1 = \max_{a \ne b} |\mu_a - \mu_b|$.

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

Lemma 62 shows that the EB leader satisfies the required condition on a leader to obtain sufficient exploration, i.e. Property 2 in Jourdan et al. (2022).

**Lemma 62 (Lemma 17 in Jourdan et al. (2022))** Let $S_t^L$ and $\mathcal{I}_t^*$ as in (24). Let $L_4$ in Lemma 60. Then, for all $L \ge L_4$, for all $n$ such that $S_t^L \ne \emptyset$, $B_{t+1}^{EB} \in S_t^L$ implies $B_{t+1}^{EB} \in \mathcal{I}_t^*$.

Lemma 63 shows that the TCI challenger satisfies the required condition on a challenger to obtain sufficient exploration, i.e. Property 3 in Jourdan et al. (2022). The proof of Lemma 63 resembles the proof of Lemma 21 in Jourdan et al. (2022). The sole technical difference lies in the necessities of having a finite mean for $W_0$, which explains why we consider $n_0 = 4$ for $\beta$-EB-TCI.

**Lemma 63** Let $U_t^L$ and $V_t^L$ as in (25) and $\mathcal{J}_t^* = \arg \max_{a \in \overline{V_t^L}} \mu_a$. There exists $L_6$ with $\mathbb{E}_\nu[L_6] < +\infty$ such that if $L \ge L_6$, for all $n$ such that $U_t^L \ne \emptyset$, $B_{t+1}^{EB} \notin V_t^L$ implies $A_{t+1}^{TCI} \in V_t^L \cup (\mathcal{J}_t^* \setminus \{B_{t+1}^{EB}\})$.

**Proof** Using Lemmas 60, 61 and 62, for all $L$ larger than a random variable $L_7$ with finite expectation, $B_{t+1}^{EB} \in \mathcal{J}_t^*$ and

$$\forall (a, b) \in \mathcal{J}_t^* \times (\overline{V_t^L} \setminus \mathcal{J}_t^*), \quad C_t(a, b) + \log N_{t,b} \ge L^{5/6} D_\nu + \frac{5}{6} \log L,$$

$$\forall (a, b) \in \overline{U_t^L} \times U_t^L, \quad C_t(a, b) + \log N_{t,b} \le \frac{L^{1/6}}{2} \log \left( 1 + L^{1/6} W_0 (D_1 + 4W_\mu)^2 \right) + \frac{1}{6} \log L.$$

Using that $\log(1+x) \le \sqrt{x}$, we obtain

$$\frac{L^{1/6}}{2} \log \left( 1 + L^{1/6} W_0 (D_1 + 4W_\mu)^2 \right) \le \frac{L^{1/4}}{2} \sqrt{W_0} (D_1 + 4W_\mu)$$
Therefore, for $L \ge L_8 := W_0^{6/7} \left( \frac{D_1+4W_\mu}{2D_\nu} \right)^{12/7} + 1$, we have that

$$L^{5/6} D_{\nu} + \frac{5}{6} \log L > \frac{L^{1/6}}{2} \log \left( 1 + L^{1/6} W_0 (D_1 + 4W_{\mu})^2 \right) + \frac{1}{6} \log L.$$

Let $L_6 = \max\{L_7, L_8\}$. Therefore, at least one under-sampled arm has transportation cost lower than all the ones that are much sampled. This implies that $A_{t+1}^{\text{TCI}} \in V_t^L \cup (J_t^* \setminus \{B_{t+1}^{\text{EB}}\})$. Then, we have

$$\mathbb{E}_{\nu}[L_6] \le \mathbb{E}_{\nu}[L_7] + 1 + \mathbb{E}_{\nu}[W_0^{6/7}] \mathbb{E}_{\nu}\left[\left(\frac{D_1 + 4W_{\mu}}{2D_{\nu}}\right)^{12/7}\right] < +\infty,$$

The first inequality and the last strict inequality are obtained by Lemma 57, thanks to the independence of $W_0$ and $W_\mu$, the fact that $W_0$ has finite mean since $n_0 \ge 4$ and that polynomial of $W_\mu$ have finite expectation. ■

Since Properties 2 and 3 of Jourdan et al. (2022) are satisfied (Lemmas 62 and 63), Lemma 64 holds for $\beta$-EB-TCI on instances such that $\min_{a \ne b} |\mu_a - \mu_b| > 0$.

**Lemma 64 (Lemma 7 in Jourdan et al. (2022))** There exist $N_0$ with $\mathbb{E}_{\nu}[N_0] < +\infty$ such that for all $t \ge N_0$ and all $a \in [K]$, $N_{t,a} \ge (t/K)^{1/6}$.

Now that we have proved sufficient exploration (Lemma 64), we will show convergence towards the $\beta$-optimal allocation. Lemma 65 shows that the EB leader satisfies the required condition on a leader to obtain convergence, i.e. Property 5 in Jourdan et al. (2022).

**Lemma 65 (Lemma 18 in Jourdan et al. (2022))** There exists $N_6$ with $\mathbb{E}_{\nu}[N_6] < +\infty$ such that for all $t \ge N_6$, $B_{t+1}^{\text{EB}} = a^*$.

For all $a \in [K]$ and all $t > t_0$, let $\psi_{t,a} \stackrel{\text{def}}{=} \mathbb{P}_{|(t-1)}[a_t = a]$ be the probability of sampling arm $a$ at time $t$ and $\Psi_{t,a} \stackrel{\text{def}}{=} \sum_{s \in [t]} \psi_{s,a}$ its cumulative sum.

Using the EB leader, Lemma 66 shows that the TCI challenger satisfies the required condition on a challenger to obtain convergence towards the $\beta$-optimal allocation, i.e. Property 6 in Jourdan et al. (2022). The proof of Lemma 66 is very similar to the proof of Lemma 22 in Jourdan et al. (2022), hence we omit certain details.

**Lemma 66** Let $\varepsilon > 0$. There exists $N_7$ with $\mathbb{E}_{\nu}[N_7] < +\infty$ such that for all $n \ge N_7$ and all $a \ne a^*(\mu)$, $\Psi_{t,a}/t \ge w_a^\beta + \varepsilon$ implies that $A_{t+1}^{\text{TCI}} \ne a$.

**Proof** Using Lemma 65, we know that $B_{t+1}^{\text{EB}} = a^*$ for all $t \ge N_6$. By definition of $A_{t+1}^{\text{TCI}}$ and algebraic manipulation, $A_{t+1}^{\text{TCI}} \ne a$ is implied by

$$\frac{1}{t} \left( C_t(a^*, a) - \min_{b \ne a^*} C_t(a^*, b) \right) > \frac{\log(tK)}{2t}.$$

In Appendix C.2, we obtain the desired regularity properties: joint continuity, strict convexity, equality at the equilibrium. Therefore, by using the same proof as the one of Lemma 20 in Jourdan et al. (2022), there exists $C_\nu > 0$ and $N_7$ with $\mathbb{E}_{\nu}[N_7] < +\infty$ such that for all $t \ge N_7$ and all $a \ne a^*$,

$$\frac{\Psi_{t,a}}{t} \ge w_a^\beta + \varepsilon \quad \Rightarrow \quad \frac{1}{t} \left( C_t(a^*, a) - \min_{b \ne a^*} C_t(a^*, b) \right) \ge C_\nu.$$
Since $\frac{\log(tK)}{2t} \to \infty$ 0, there exists a deterministic $N_8$ such that for all $n \ge N_8$, $\frac{\log(tK)}{2t} < C_\nu$. Therefore, for all $n \ge \tilde{N}_7$ $\stackrel{\text{def}}{=} \max\{N_8, N_7\}$ and all $a \ne a^*$, $\Psi_{t,a}/t \ge w_a^\beta + \epsilon$ implies that $A_{t+1}^{\text{TCI}} \ne a$. Since $\mathbb{E}_\nu[\tilde{N}_7] = N_8 + \mathbb{E}_\nu[N_7] < +\infty$, this concludes the proof. ■

Since there is sufficient exploration (Lemma 64) and Properties 5 and 6 of Jourdan et al. (2022) are satisfied (Lemmas 65 and 66), Lemma 67 holds for $\beta$-EB-TCI on instances such that $\min_{a \ne b} |\mu_a - \mu_b| > 0$.

**Lemma 67 (Lemma 10 in Jourdan et al. (2022))** Let $\epsilon > 0$ and $T_\beta^\epsilon$ as in (23). Then, $\beta$-EB-TCI satisfies $\mathbb{E}_\nu[T_\beta^\epsilon] < +\infty$.

Combining Lemmas 67 and 58 concludes the proof for $\beta$-EB-TCI.

### H.2.2. $\beta$-EB-EVTCI

Let $a^* = a^*(\mu)$. Similarly, the $\beta$-optimal allocation for Gaussian with known variance is defined as

$$w_{\sigma^2, \beta}^*(\mu) = \arg \max_{w \in \Delta_K, w_{a^*} = \beta} \min_{a \ne a^*} \inf_{u \in \mathbb{R}} \sum_{b \in \{a^*, a\}} w_b \frac{(\mu_b - u)^2}{\sigma_b^2},$$

is a singleton, denoted by $\{w^\beta\}$, such that $\min_{a \in [K]} w_a^\beta > 0$.

**Lemma 68** Using the EV-GLR stopping rule with an asymptotically tight family of thresholds, $\beta$-EB-EVTCI) satisfies that, for all $\nu$ with $\min_{a \ne b} |\mu_a - \mu_b| > 0$,

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

For $\epsilon > 0$, the random variable $\bar{T}_\beta^\epsilon$ quantifies the number of samples required for the empirical allocations $\frac{N_t}{t}$ to be $\epsilon$-close to $w^\beta$:

$$\bar{T}_\beta^\epsilon \stackrel{\text{def}}{=} \inf \left\{ T \ge 1 \mid \forall t \ge T, \left\| \frac{N_t}{t} - w^\beta \right\|_\infty \le \epsilon \right\}. \qquad (26)$$

Lemma 69 shows that a sufficient condition to obtain an upper bound on the asymptotic expected sample complexity is to show $\mathbb{E}_\nu[\bar{T}_\beta^\epsilon] < +\infty$ for $\epsilon$ small enough. The proof of Lemma 69 is omitted since it is almost identical to the one of Lemma 58.

**Lemma 69** Let $\delta, \beta \in (0, 1)$. Assume that there exists $\epsilon_1 > 0$ such that for all $\epsilon \in (0, \epsilon_1]$, $\mathbb{E}_\nu[\bar{T}_\beta^\epsilon] < +\infty$. Combining the EV-GLR stopping rule (5) with an asymptotically tight family of threshold yields an algorithm such that, for all $(\mu, \sigma^2) \in \mathbb{R}^K \times (\mathbb{R}_+^*)^K$ with $|a^*(\mu)| = 1$,

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

Lemma 70 is obtained similarly as Lemma 60, hence we omit the proof.
**Lemma 70** Let $S_t^L$ and $\mathcal{I}_t^*$ as in (24). There exists $L_4$ with $\mathbb{E}_\nu[(L_4)^\alpha] < +\infty$ for all $\alpha > 0$ such that if $L \ge L_4$, for all $t$ such that $S_t^L \ne \emptyset$, for all $(a, b) \in \mathcal{I}_t^* \times (S_t^L \setminus \mathcal{I}_t^*)$, we have $C_t^{EV}(a, b) \ge LD_\mu$, where $D_\nu > 0$ is a problem dependent constant.

Lemma 71 is obtained similarly as Lemma 61, hence we omit the proof.

**Lemma 71** Let $S_t^L$ as in (24). There exists $L_5$ with $\mathbb{E}_\nu[(L_5)^\alpha] < +\infty$ for all $\alpha > 0$ such that for all $L \ge L_5$ and all $t \in \mathbb{N}$,

$$ \forall (a, b) \in S_t^L \times \overline{S_t^L}, \quad C_t^{EV}(a, b) \le \frac{L^2}{2} W_0 (D_1 + 4W_\mu)^2, $$

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

Lemma 72 is obtained similarly as Lemma 63. The sole technical difference lies in the necessi- ties of having a finite variance for $W_0$, which explains why we consider $n_0 = 6$ for $\beta$-EB-EVTCI.

**Lemma 72** Let $U_t^L$ and $V_t^L$ as in (25) and $\mathcal{J}_t^* = \arg \max_{a \in \overline{V_t^L}} \mu_a$. There exists $L_6$ with $\mathbb{E}_\nu[L_6] < +\infty$ such that if $L \ge L_6$, for all $n$ such that $U_t^L \ne \emptyset$, $B_{t+1}^{EB} \notin V_t^L$ implies $A_{t+1}^{EVTCI} \in V_t^L \cup (\mathcal{J}_t^* \setminus \{B_{t+1}^{EB}\})$.

**Proof** Using Lemmas 70, 71 and 62, for all $L$ larger than a random variable $L_7$ with finite expec- tation, $B_{t+1}^{EB} \in \mathcal{J}_t^*$ and

$$ \begin{aligned} \forall (a, b) \in \mathcal{J}_t^* \times (\overline{V_t^L} \setminus \mathcal{J}_t^*), \quad & C_t(a, b) + \log N_{t,b} \ge L^{5/6} D_\mu + \frac{5}{6} \log L, \\ \forall (a, b) \in \overline{U_t^L} \times U_t^L, \quad & C_t(a, b) + \log N_{t,b} \le \frac{L^{1/3}}{2} W_0 (D_1 + 4W_\mu)^2 + \frac{1}{6} \log L. \end{aligned} $$

Therefore, for $L \ge L_8 := W_0^2 \left( \frac{D_1+4W_\mu}{2D_\nu} \right)^4 + 1$, we have that

$$ L^{5/6} D_{\mu} + \frac{5}{6} \log L > \frac{L^{1/3}}{2} W_0 (D_1 + 4W_{\mu})^2 + \frac{1}{6} \log L. $$

Let $L_6 = \max\{L_7, L_8\}$. Therefore, at least one under-sampled arm has transportation cost lower than all the ones that are much sampled. This implies that $A_{t+1}^{EVTCI} \in V_t^L \cup (\mathcal{J}_t^* \setminus \{B_{t+1}^{EB}\})$. Then, we have

$$ \mathbb{E}_{\nu}[L_6] \le \mathbb{E}_{\nu}[L_7] + 1 + \mathbb{E}_{\nu}[W_0^2] \mathbb{E}_{\nu} \left[ \left( \frac{D_1 + 4W_{\mu}}{2D_{\nu}} \right)^4 \right] < +\infty. $$

The first inequality and the last strict inequality are obtained by Lemma 57, thanks to the indepen- dence of $W_0$ and $W_\mu$, the fact that $W_0$ has finite variance since $n_0 \ge 6$ and that polynomial of $W_\mu$ have finite expectation. ■

Since Properties 2 and 3 of Jourdan et al. (2022) are satisfied (Lemmas 62 and 72), Lemma 64 holds for $\beta$-EB-EVTCI on instances such that $\min_{a \ne b} |\mu_a - \mu_b| > 0$.

Lemma 73 is obtained similarly as Lemma 66, hence we omit the proof.
**Lemma 73** Let $\varepsilon > 0$. There exists $N_7$ with $\mathbb{E}_{\nu}[N_7] < +\infty$ such that for all $n \ge N_7$ and all $a \ne a^*(\mu)$, $\Psi_{t,a}/t \ge w_a^\beta + \varepsilon$ implies that $A_{t+1}^{\text{EVTCl}} \ne a$.

Since there is sufficient exploration (Lemma 64) and Properties 5 and 6 of Jourdan et al. (2022) are satisfied (Lemmas 65 and 73), Lemma 74 holds for $\beta$-EB-EVTCI on instances such that $\min_{a \ne b} |\mu_a - \mu_b| > 0$.

**Lemma 74 (Lemma 10 in Jourdan et al. (2022))** Let $\varepsilon > 0$ and $\bar{T}_{\beta}^{\varepsilon}$ as in (26). Then, $\beta$-EB-EVTCI satisfies $\mathbb{E}_{\nu}[\bar{T}_{\beta}^{\varepsilon}] < +\infty$.

Combining Lemmas 74 and 69 concludes the proof of the asymptotic upper bound on the expected sample complexity of $\beta$-EB-EVTCI, i.e. Lemma 68.

In Appendix C.1, we explained that $T_{\sigma^2, \beta}^*(\mu)$ and $T_{\beta}^*(\mu, \sigma^2)$ satisfied inequalities like the ones between $T_{\sigma^2}^*(\mu)$ and $T^*(\mu, \sigma^2)$ in (2). Similar to Lemma 12, we can show that there exists a sequence of instances $(\nu_n)_{n \in \mathbb{N}}$ with $\min_{b \ne a} |\mu_{n,a} - \mu_{n,b}| > 0$ such that $\lim_{n \to +\infty} T_{\beta}^*(\mu_n, \sigma_n^2)/T_{\sigma_n^2, \beta}^*(\mu_n) = +\infty$. Therefore, we can conclude the impossibility result for $\beta$-EB-EVTCI (Theorem 10) with the same arguments as for EV-TaS in Appendix H.1.

## Appendix I. The Lambert W Function

The Lambert W function is implicitly defined by the equation $W(x)e^{W(x)} = x$. It defines two main branches $W_{-1}$ (negative) and $W_0$ (positive).

* $W_{-1}$, defined on $[-e^{-1}, 0)$, is decreasing and $W_{-1}(-e^{-1}) = -1$.

* $W_0$, defined on $[-e^{-1}, +\infty)$, is increasing and $W_0(-e^{-1}) = -1$.

The function $W_0$ satisfies for all $x \ge e$, $W_0(e^x) \le x$ and

$$ \frac{\log \log(x)}{2 \log(x)} \le W_0(x) - (\log(x) - \log \log(x)) \le \frac{e}{e-1} \frac{\log \log(x)}{\log(x)}. $$

Lambert's branches are involved in the inversion of $h(x) = x - \log(x)$. When $x \ge 1$, it involves the negative branch. When $x \le 1$, it involves the negative part of the positive branch. To make the notations clearer, we define for all $x \ge 1$

$$ \bar{W}_{-1}(x) = -W_{-1}(-e^{-x}) \quad \text{and} \quad \bar{W}_{0}(x) = -W_{0}(-e^{-x}). \qquad (27) $$

Lemma 75 gather useful properties on $\bar{W}_{-1}$ and $\bar{W}_{0}$ that we will use.
**Lemma 75 (1)** For $x \ge 1$, let $h(x) = x - \log(x)$. Then,

$$
\begin{align*}
\forall y \ge 1, \quad y \le h(x) &\iff \begin{cases} \overline{W}_{-1}(y) \le x & \text{if } x \ge 1 \\ \overline{W}_0(y) \ge x & \text{if } x \in (0, 1] \end{cases}, \\
\forall \delta > 0, \forall c > 0, \quad e^{-c(h(x)-1)} \le \delta &\iff \begin{cases} \overline{W}_{-1}\left(1+\frac{1}{c}\log\frac{1}{\delta}\right) \le x & \text{if } x > 1 \\ \overline{W}_0\left(1+\frac{1}{c}\log\frac{1}{\delta}\right) \ge x & \text{if } x \in (0, 1] \end{cases}, \\
\forall x > 1, \quad \exp(-x+e^{-x}) \le \overline{W}_0(x) \le \exp(-x+e^{1-x}), & \\
\forall x > 1, \quad x+\log(x) \le \overline{W}_{-1}(x) \le x+\log(x)+\min\left\{\frac{1}{2}, \frac{1}{\sqrt{x}}\right\}, & \\
\forall u > 1, \forall t > 1, \quad \overline{W}_0\left(1+\frac{u}{t}\right) \ge \frac{1}{t} &\iff t \ge \exp\left(1+W_0\left(\frac{u-1}{e}\right)\right).
\end{align*}
$$

(2) The function $\overline{W}_{-1}$ is increasing and strictly concave on $(1, +\infty)$. The function $\overline{W}_0$ is decreasing and strictly convex on $(1, +\infty)$. In particular,

$$
\forall x > 1, \quad (\overline{W}_0)'(x) = \left(1 - \frac{1}{\overline{W}_0(x)}\right)^{-1} \quad \text{and} \quad (\overline{W}_{-1})'(x) = \left(1 - \frac{1}{\overline{W}_{-1}(x)}\right)^{-1}.
$$

**Proof (1)** Let $y \ge 1$ and $x \in (0, 1]$. We obtain

$$
\overline{W}_0(y) \ge x \iff W_0(-e^{-y}) \le -x \iff -e^{-y} \le -xe^{-x} \iff y \le x - \log(x)
$$

where the second equivalence uses that $-e^{-y} = W_0(-e^{-y})e^{W_0(-e^{-y})}$, $y \mapsto ye^y$ is increasing on $[-1, +\infty)$ and $W_0(x)$ has values on $[-1, 0)$ for $x \in [-e^{-1}, 0)$. Let $x \in (0, 1)$, $\delta, c > 0$. Then,

$$
\overline{W}_0 \left( 1 + \frac{1}{c} \log \frac{1}{\delta} \right) \ge x \iff 1 + \frac{1}{c} \log \frac{1}{\delta} \le h(x) \iff \exp(-c(h(x) - 1)) \le \delta
$$

Let $x > 1$ and $f(x) \in (0, 1)$. Then, we obtain

$$
\overline{W}_0(x) \ge f(x) \iff x \le f(x) - \log(f(x))
$$

For $f(x) = e^{-x+e^{-x}}$, we have $x \le f(x) - \log(f(x)) \iff e^{-x} \ge 0$, hence this condition holds and $\overline{W}_0(x) \ge f(x)$. For $f(x) = e^{-x+e^{1-x}}$, we have $x \le f(x) - \log(f(x)) \iff x \le 1$, hence this condition doesn't hold for $x > 1$, hence $\overline{W}_0(x) \le f(x)$.

For $\overline{W}_{-1}(y)$, the same arguments yield the three results, which were first proven in Lemma A.1 and A.2 of Degenne (2019)).

We denote $v = \frac{u-1}{t} > 0$. Since $t > 1$, direct manipulations show that

$$
\begin{align*}
\overline{W}_0 \left(1 + \frac{u}{t}\right) \ge \frac{1}{t} &\iff 1 + \frac{u}{t} \le \frac{1}{t} - \log \left(\frac{1}{t}\right) \iff v + \log(v) \le \log \left(\frac{u-1}{e}\right) \\
&\iff ve^v \le \frac{u-1}{e} \iff v \le W_0 \left(\frac{u-1}{e}\right) \iff t \ge \frac{u-1}{W_0 \left(\frac{u-1}{e}\right)} = e^{1+W_0 \left(\frac{u-1}{e}\right)}
\end{align*}
$$

The equivalence introducing $W_0$ uses that for $\alpha = \frac{u-1}{e} > 0$, $W_0(\alpha)e^{W_0(\alpha)} = \alpha$, $y \mapsto ye^y$ is increasing on $[-1, +\infty)$ and $v > 0$. The last equality uses that $e^{W_0(x)} = \frac{x}{W_0(x)}$.
(2) Let $W$ denote $W_0$ or $W_{-1}$ and $\overline{W}(x) = -W(-e^{-x})$. It is known (by implicit derivation) that $W'(z) = \frac{1}{z+e^{W(z)}}$ for $z \neq -e^{-1}$. Using that $e^{W(z)} = \frac{z}{\overline{W}(z)}$, this yields that $zW'(z) = (1 + \frac{e^{W(z)}}{z})^{-1} = (1 + \frac{1}{\overline{W}(z)})^{-1}$. For $x \neq 1$, using the above with $z = -e^{-x}$, we obtain

$$ \overline{W}'(x) = -\frac{d}{dx}(W(-e^{-x})) = -e^{-x}W'(-e^{-x}) = \left(1 + \frac{1}{\overline{W}(-e^{-x})}\right)^{-1} = \left(1 - \frac{1}{\overline{W}(x)}\right)^{-1} $$

Since $W_0(-e^{-x}) \in (-1, 0)$ for all $x > 1$ (positive branch on $(-e^{-1}, 0)$), we have $\overline{W}_0(x) \in (0, 1)$, hence $\overline{W}'_0(x) < 0$ for $x > 1$. Therefore, $\overline{W}_0$ is decreasing on $(1, +\infty]$. Using that $\overline{W}'(x) = (1 - \frac{1}{\overline{W}(x)})^{-1}$ for $x \neq 1$, we obtain that $\overline{W}'_0$ is increasing on $(1, +\infty]$, hence strictly convex. The same arguments yield that $\overline{W}_{-1}$ is increasing and strictly concave on $(1, +\infty]$. ■

Lemma 76 was proven in Degenne (2019). It is needed when using the peeling method.

**Lemma 76 (Lemma A.3 in Degenne (2019))** For $a, b \ge 1$, the minimal value of $f(\eta) = (1 + \eta)(a + \log(b + \frac{1}{\eta}))$ is attained at $\eta^*$ such that $f(\eta^*) \le 1 - b + \overline{W}_{-1}(a + b)$. If $b = 1$, then there is equality.

# Appendix J. Implementation Details and Additional Experiments

Implementations details are given in Appendix J.1. Supplementary experiments are provided in Appendix J.2.

## J.1. Implementation Details

We detail below the most relevant implementation details, both regarding the sampling rules and the considered family of thresholds.

**Stopping thresholds** The implementation of the different families of thresholds require to specify the hyper-parameters $(s, \eta_0, \eta_1, \gamma)$. Based on the obtained formulas, we see that there is a trade-off in their choice. Smaller values of $(\eta_0, \eta_1)$ yield close to ideal dependency in $\delta$, at the cost of increasing the dependency in $t$. Smaller values of $s$ yield close to ideal dependency in $t$, at the cost of increasing the constant term. Smaller values of $\gamma$ yield more frequent update of the approximation term error (i.e. the ratio of eigenvalues), at the cost of increasing the dependency in $t$. Those updates are responsible for stair-step shaped curves of the KL and (EV-)BoB thresholds. For reasonable choices of the parameters, the relative performance of the thresholds are not changed. We conduct our experiments with $s = 2, \gamma = 1.2, \eta_0 = \eta_1 = \log(1/\delta)^{-1}$ (as $\delta < 1$).

**Optimal allocation oracles** To compute the optimal allocation in TaS, we perform nested binary searches to solve the optimization problem described in Theorem 13. The outer binary search is done on $y \in [0, \min_{a \neq a^*} d_{a^*}(\mu_a))$. The inner binary searches are done to compute $x_a(y)$ for all $a \in [K]$. To obtain $\lambda(x)$, we compute the (at most three) real solutions of the third order polynomial equation, and then return the one minimizing the function of interest. For EV-TaS, the procedure is similar as the one implemented in Garivier and Kaufmann (2016), and it is significantly faster as $\lambda(x)$ has a closed-form solution.
**Sampling rules** As recommended in Jourdan et al. (2022), we implemented the β-EB-TCI algorithm with β = 0.5. This is a deterministic instance of Top Two algorithm with an efficient implementation since it can re-use computations done in the stopping and recommendation rules.

Based on Degenne et al. (2019), we consider DKM with one learner on $\Delta_K$ instead of K learners. For unknown variances, the wrapped DKM algorithm is obtained by considering adapted transportation costs (and the corresponding alternatives). To cope for an additional uncertainty due to the unknown variance, the bonus $\frac{\log(t)}{N_{t,a}}$ is multiplied by $1 + 2^{-\frac{\log(t)}{N_{t,a}}}$. This heuristic is legitimated by our box concentration. The implementation of EV-DKM is direct by plugging in the empirical variance. Based on Wang et al. (2021), the wrapped algorithms FWS and EV-FWS are obtained similarly.

FHN2 refers to the procedure 2 in Fan et al. (2016), whose pseudo-code (see Algorithm 1) was given in Hong et al. (2021). FHN2 is an elimination strategy which repeatedly samples all arms until only one arm is left. For all $a \in [K]$, let $\bar{X}_{n,a} = \frac{1}{n} \sum_{t \in [n]} X_{t,a}$ where $(X_{t,a})_{t \in [n]}$ are i.i.d. observations from $\nu_{\mu_a, \sigma_a^2}$. Its elimination mechanism compares the pairwise statistics $t_{b,a}(n)(\bar{X}_{n,b} - \bar{X}_{n,a})$ to an elimination threshold $g_{b,a}(t_{b,a}(n), \delta)$, where the effective time $t_{b,a}(n) = n/S_{b,a}(n)$ is defined with the empirical variances of pairwise comparison between arms b and a

$$S_{b,a}(n) = \frac{1}{n-1} \sum_{t \in [n]} (X_{t,b} - X_{t,a} - \bar{X}_{n,b} + \bar{X}_{n,a})^2 .$$

The calibration of the elimination threshold, which is done by simulations arguments and continuous-time approximations, yields

$$g_{b,a}(x, \delta) = \sqrt{(x+1)\left(2\log\left(\frac{K-1}{2\delta}\right) + \log(x+1)\right)}.$$

The choice of the initial time $n_0$ impacts the empirical performance of the algorithm, yet few practical guidelines were given. In our experiments we took $n_0 = \max\{2, 10 \log(1/\delta)\}$.

**Algorithm 1: FHN2**

Let $I = [K]$ and $n = n_0$ (user-specified)

Sample $n_0$ observations from each arm

while $|I| > 1$ do

Compute $S_{b,a}(n)$ and set $t_{b,a}(n) = n/S_{b,a}(n)$ for all $b \neq a$

Update active arms, $I \leftarrow I \setminus \{b \mid \forall a \neq b, t_{b,a}(n)(\bar{X}_{n,b} - \bar{X}_{n,a}) < -g_{b,a}(t_{b,a}(n), \delta)\}$

Pull each arm once, and set $n \leftarrow n + 1$

end

Return the unique arm in $I$

In Fan et al. (2016), they also propose the procedure 1, which we refer to as FHN1. The main difference is that FHN1 uses the empirical variances obtained after initialization, meaning it uses $t_{b,a}(n) = n/S_{b,a}(n_0)$ instead of $t_{b,a}(n) = n/S_{b,a}(n)$. While one can argue that this wastes precious information, FHN1 enjoys better theoretical guaranty. The impact of then choice of $n_0$ is more important for FHN1 since $S_{b,a}(n_0)$ is used for elimination.

**Reproducibility** Our code is implemented in Julia 1.7.2, and the plots are generated with the StatsPlots.jl package. Optimizations are performed based on the JuMP.jl optimization
package. In particular, we use the Ipopt non-linear solver (Wächter and Biegler, 2006), available in Ipopt.jl, and the LambertW.jl package to compute the Lambert W function. 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.<fnref n="2" />

## J.2. Supplementary Experiments

In Appendix J.2.1, we perform simulations on the characteristic times $T^*(\mu, \sigma^2)$ and $T_{\sigma^2}^*(\mu)$. In Appendix J.2.2, we compare family of stopping thresholds for the EV-GLR stopping rule.

### J.2.1. CHARACTERISTIC TIMES

We perform numerical simulations to compare $T^*(\mu, \sigma^2)$ and $T_{\sigma^2}^*(\mu)$. Based on the inequalities (2), we will compare $\frac{T^*(\mu, \sigma^2)}{T_{\sigma^2}^*(\mu)}$ and its upper bound $\frac{d(\mu, \sigma^2)}{\log(1+d(\mu, \sigma^2))}$ on $\frac{T^*(\mu, \sigma^2)}{T_{\sigma^2}^*(\mu)}$, where $d(\mu, \sigma^2) = \max_{a \neq a^*(\mu)} \frac{(\mu_{a^*(\mu)} - \mu_a)^2}{\min\{\sigma_a^2, \sigma_{a^*(\mu)}^2\}}$. Taking $K = 2$, we consider the canonical instance $\mu = (0, -\Delta)$ and $\sigma^2 = (1, r)$, hence $d(\mu, \sigma^2) = \frac{\Delta^2}{\min\{1, r\}}$, and instantiate it by default with $\Delta = 0.2$ and $r = 0.5$. We perform 10000 simulations for varying $\Delta$ and $r$.

<figure><img src="image_23.png" /><figcaption>Figure 3: Evolution of $\frac{T^*(\mu, \sigma^2)}{T_{\sigma^2}^*(\mu)}$ as a function of (a) $\Delta$ for $r = 0.5$ and (b) $r$ for $\Delta = 0.2$.</figcaption></figure>

Figure 3 empirically confirms that $\frac{d(\mu, \sigma^2)}{\log(1+d(\mu, \sigma^2))}$ is an upper bound on $\frac{T^*(\mu, \sigma^2)}{T_{\sigma^2}^*(\mu)}$, which is always above 1. It shows that $\frac{T^*(\mu, \sigma^2)}{T_{\sigma^2}^*(\mu)}$ is close to one as long as the gap is not too large. Moreover, the upper bound $\frac{d(\mu, \sigma^2)}{\log(1+d(\mu, \sigma^2))}$ has the same behavior, except when the variance of the optimal arm is significantly larger than the one of the sub-optimal arm. In this particular regime, our upper bound appears to be loose.

<footnote n="2">2. This library was created by Degenne et al. (2019), see https://bitbucket.org/wmkoolen/tidnabbil. No license were available on the repository, but we obtained the authorization from the authors.</footnote>
### J.2.2. THRESHOLDS

Using the same experimental setup as in Section 3.3, we perform numerical simulations to compare the family of thresholds derived for the EV-GLR stopping rule: EV-Student (Lemma 50), EV-Box (Lemma 51) and EV-BoB (Corollary 52).

<figure><img src="image_24.png" /><figcaption>Figure 4: Threshold for (5) as a function of (a) $\log(1/\delta)$ for $t = 5000$ and (b) $t$ for $\delta = 0.01$.</figcaption></figure>

Figure 4 is the equivalent of Figure 1 and similar messages can be extracted from it. However, for the EV-GLR stopping rule, the $\delta$-correct family of thresholds can be asymptotically tight, otherwise Theorem 9 would contradict the asymptotic lower bound. The Student threshold in (21) has poor performance in $t$. While the box threshold in (22) yields better performance in $t$, it comes at a worse dependency in $\log(1/\delta)$ (higher slope). The BoB threshold in Corollary 52 has the good performance in $t$ of the box threshold and the same dependency in $\log(1/\delta)$ as the Student threshold.

<figure><img src="image_25.png" /><figcaption>Figure 5: Thresholds as a function of (a) $\log(1/\delta)$ for $t = 5000$ and (b) $t$ for $\delta = 0.01$.</figcaption></figure>

Figure 5 groups Figures 1 and 4 together. By comparing the thresholds obtained by using the same method, all the thresholds for the EV-GLR stopping rule are above the ones obtained for the GLR stopping rule. Given the ordering of the statistic (Lemma 16), this was expected.