# An $\epsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond

Marc Jourdan, Rémy Degenne, Emilie Kaufmann

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

## To cite this version:

Marc Jourdan, Rémy Degenne, Emilie Kaufmann. An $\epsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond. Advances in Neural Information Processing Systems (NeurIPS), Dec 2023, New Orleans, United States. hal-04306214

HAL Id: hal-04306214

https://hal.science/hal-04306214v1

Submitted on 24 Nov 2023

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# An $\epsilon$-Best-Arm Identification Algorithm
for Fixed-Confidence and Beyond

Marc Jourdan

marc.jourdan@inria.fr

Rémy Degenne

remy.degenne@inria.fr

Emilie Kaufmann

emilie.kaufmann@univ-lille.fr

Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189-CRISTAL, F-59000 Lille, France

## Abstract

We propose EB-TC$_{\epsilon}$, a novel sampling rule for $\epsilon$-best arm identification in stochastic bandits. It is the first instance of Top Two algorithm analyzed for approximate best arm identification. EB-TC$_{\epsilon}$ is an *anytime* sampling rule that can therefore be employed without modification for fixed confidence or fixed budget identification (without prior knowledge of the budget). We provide three types of theoretical guarantees for EB-TC$_{\epsilon}$. First, we prove bounds on its expected sample complexity in the fixed confidence setting, notably showing its asymptotic optimality in combination with an adaptive tuning of its exploration parameter. We complement these findings with upper bounds on its probability of error at any time and for any error parameter, which further yield upper bounds on its simple regret at any time. Finally, we show through numerical simulations that EB-TC$_{\epsilon}$ performs favorably compared to existing algorithms, in different settings.

## 1 Introduction

In pure exploration problems, the goal is to answer a question about a set of unknown distributions (modelling for example the efficacy of a treatment) from which we can collect samples (measure its effect), and to provide guarantees on the candidate answer. Practitioners might have different pre-defined constraints, e.g. the maximal budget might be fixed in advance or the error made should be smaller than a fixed admissible error. However, in many cases, fixing such constraints in advance can be challenging since a “good” choice typically depends on unknown quantities. Moreover, while the budget is limited in clinical trials, it is often not fixed beforehand. The physicians can decide to stop earlier or might obtain additional fundings for their experiments. In light of those real-world constraints, regardless of its primal objective any strategy for choosing the next treatment should ideally come with guarantees on its current candidate answer that hold at any time.

We formalize our investigations in the well-studied stochastic bandit model [4, 29], in which a learner interacts sequentially with an environment composed of $K \in \mathbb{N}$ arms, which are unknown distributions $(\nu_i)_{i \in [K]}$ with finite means $(\mu_i)_{i \in [K]}$. At each stage $n \in \mathbb{N}$, the learner chooses an arm $I_n \in [K]$ based on the samples previously observed and receives a sample $X_{n,I_n}$, random variable with conditional distribution $\nu_{I_n}$ given $I_n$. It then proceeds to the next stage. An algorithm for the learner in this interaction is specified by a *sampling rule*, a procedure that determines $I_n$ based on previously observed samples. Formally, the sampling rule defines for all $n \in \mathbb{N}$ a function from $([K] \times \mathbb{R})^{n-1}$ to the probability distribution on $[K]$, which is measurable with respect to the $\sigma$-algebra $\mathcal{F}_n := \sigma(\{I_t, X_{t,I_t}\}_{t \in [n-1]})$. We call that $\sigma$-algebra *history* before $n$.

**Identification tasks** We focus on best arm identification (BAI). In that task, the goal of the algorithm is to find which of the arms has the largest mean, and to do so with a small probability of
error, as quickly as possible. If several arms have means very close to the maximum, finding the one with the highest mean might be difficult. However in practice we are often satisfied by any good enough arm, in the sense that its mean is greater than $\mu_\star - \epsilon$, where $\mu_\star = \max_{i \in [K]} \mu_i$. This is the $\epsilon$-BAI task. Our results can also be adapted to the multiplicative $\epsilon$-BAI task, in which all means are non-negative and we want to find an arm with mean $\mu_i \ge (1 - \epsilon)\mu_\star$ [19] (see Appendix I for details).

Now that we have a (for now informal) goal, we need to complement the sampling rule with a recommendation rule that specifies which arm is the candidate returned by the algorithm for the best arm. We follow [5] and define that rule for all stages: for all $n \in \mathbb{N}$, we denote by $\hat{\mu}_n$ this $\mathcal{F}_n$-measurable function from $([K] \times \mathbb{R})^{n-1}$ to $[K]$. We call algorithm the combination of a sampling and a recommendation rule.

**Performance criteria** There are several ways to evaluate the performance of an algorithm for $\epsilon$-BAI. Let $\mathcal{I}_\epsilon(\mu) = \{i \in [K] \mid \mu_i \ge \mu_\star - \epsilon\}$ be the set of $\epsilon$-good arms. The probability of $\epsilon$-error or the recommendation at $n$ is defined as $\mathbb{P}_\nu(\hat{\mu}_n \notin \mathcal{I}_\epsilon(\mu))$. Introduced in [1], the expected simple regret is defined as $\mathbb{E}_\nu[\mu_\star - \mu_{\hat{\mu}_n}]$, and is independent of any parameter $\epsilon$. Based on those notions, several setting are studied in the bandit identification literature.

* Fixed confidence: we augment the algorithm with a stopping rule, a stopping time $\tau_{\epsilon,\delta}$ with respect to the history of samples and we impose that the algorithm should be $(\epsilon, \delta)$-PAC. That is, its probability of $\epsilon$-error at $\tau_{\epsilon,\delta}$ must satisfy $\mathbb{P}_\nu(\tau_{\epsilon,\delta} < +\infty, \hat{\mu}_{\tau_{\epsilon,\delta}} \notin \mathcal{I}_\epsilon(\mu)) \le \delta$. The parameter $\delta$ is known to the algorithm. An algorithm is judged based on its expected sample complexity $\mathbb{E}[\tau_{\epsilon,\delta}]$, the expected number of samples it needs to collect before it can stop and return a good arm with the required confidence.

* Fixed budget: we run the algorithm until a predefined time $T$ and we evaluate it based on the probability of error at $T$. This setting has been mostly studied for $\epsilon = 0$ [1, 25], but [41] present the first bounds for $\epsilon > 0$ for an algorithm that is actually agnostic to this value.

* Simple regret minimization: we evaluate the expected simple regret at $T$ [5, 41].

Simple regret is typically studied in an anytime setting: [5] contains upper bounds on the simple regret at time $n$ for any $n \in \mathbb{N}^*$. Similarly, [23] propose the anytime exploration setting, in which they control the error probability $\mathbb{P}(\hat{\mu}_n \neq i_\star)$ for exact best arm identification. Interestingly, the authors build on an algorithm for the fixed-confidence setting, LUCB [24], whose sampling rule depends on the risk parameter $\delta$, which they replace by a sequence $\delta_n$. The algorithm that we study in this paper, motivated by the fixed-confidence $\epsilon$-BAI problem, will already be anytime, which means that it does not depend on a given final time $T$ or a confidence level $\delta$. We shall analyze its sample complexity in the fixed confidence setting but thanks to the anytime property we will also be able to prove guarantees on its probability of $\epsilon$-error for every $\epsilon \ge 0$ and its simple regret at any time.

**Additional notation and assumption** We denote by $\mathcal{D}$ a set to which the distributions of the arms are known to belong. We suppose that all distributions in $\mathcal{D}$ are 1-sub-Gaussian. A distribution $\nu_0$ is 1-sub-Gaussian if it satisfies $\mathbb{E}_{X \sim \nu_0}[e^{\lambda(X-\mathbb{E}_X \nu_0[X])}] \le e^{\lambda^2/2}$ for all $\lambda \in \mathbb{R}$. For example, all distributions bounded in $[-1, 1]$ are 1-sub-Gaussian. Let us denote by $i^*(\mu) := \arg\max_{i \in [K]} \mu_i$ the set of arms with largest mean (i.e. $i^*(\mu) = \mathcal{I}_0(\mu)$). Let $\Delta_i := \mu_\star - \mu_i$ denote the sub-optimality gap of arm $i$. We denote by $\Delta_K \subset \mathbb{R}^K$ the simplex of dimension $K-1$.

**Fixed-confidence $\epsilon$-best-arm identification** Let $\epsilon \ge 0$ and $\delta \in (0, 1)$ be fixed error and confidence parameters. In the fixed-confidence $\epsilon$-BAI setting [31, 13, 35, 16], the probability of error of an algorithm is required to be less than $\delta$ for all instances $\nu \in \mathcal{D}^K$. That requirement leads to an asymptotic lower bound on the expected sample complexity on any instance.

**Lemma 1 ([10]).** For all $(\epsilon, \delta)$-PAC algorithms and all instances $\nu_i = \mathcal{N}(\mu_i, 1)$ with $\mu \in \mathbb{R}^K$, $\liminf_{\delta \to 0} \frac{\mathbb{E}_\nu[\tau_{\epsilon,\delta}]}{\log(1/\delta)} \ge T_\epsilon(\mu)$ where $T_\epsilon(\mu) = \min_{i \in \mathcal{I}_\epsilon(\mu)} \min_{\beta \in (0,1)} T_{\epsilon,\beta}(\mu, i)$ with

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

We say that an algorithm is asymptotically (resp. $\beta$-)optimal if its sample complexity matches that lower bound, that is if $\limsup_{\delta \to 0} \frac{\mathbb{E}_\nu[\tau_{\epsilon,\delta}]}{\log(1/\delta)} \le T_\epsilon(\mu)$ (resp. $T_{\epsilon,\beta}(\mu) = \min_{i \in \mathcal{I}_\epsilon(\mu)} T_{\epsilon,\beta}(\mu, i)$). Note
that the expected sample complexity of an asymptotically 1/2-optimal algorithm is at worst twice higher than that of any asymptotically optimal algorithm since $T_{\epsilon, 1/2}(\mu) \le 2T_{\epsilon}(\mu)$ [34].

The asymptotic characteristic time $T_{\epsilon}(\mu)$ is of order $\sum_{i=1}^{K} \min\{\epsilon^{-2}, \Delta_{i}^{-2}\}$. It is computed as a minimum over all $\epsilon$-good arms $i \in \mathcal{I}_{\epsilon}(\mu)$ of an arm-specific characteristic time, which can be interpreted as the time required to verify that $i$ is $\epsilon$-good. Each of the times $\min_{\beta \in (0,1)} T_{\epsilon, \beta}(\mu, i)$ correspond to the complexity of a BAI instance (i.e. $\epsilon$-BAI with $\epsilon = 0$) in which the mean of arm $i$ is increased by $\epsilon$ (Lemma 9). Let $w_{\epsilon, \beta}(\mu, i)$ be the maximizer of (1). In [16], they show that $T_{\epsilon}(\mu) = T_{\epsilon, \beta*(i^*)(\mu, i^*)$ and $T_{\epsilon, \beta}(\mu) = T_{\epsilon, \beta}(\mu, i^*)$, where $i^* \in i^*(\mu)$ and $\beta^*(i^*) = \arg \min_{\beta \in (0,1)} T_{\epsilon, \beta}(\mu, i^*)$. For $\epsilon = 0$, a similar lower bound to Lemma 1 holds for all $\delta$ [15]. Lower bounds of order $\sum_{i=1}^{K} \Delta_{i}^{-2} \log \log \Delta_{i}^{-2}$ (independent of $\delta$, but with a stronger dependence in the gaps) were also shown [17, 6, 38, 7]. Note that the characteristic time for $\sigma$-sub-Gaussian distributions (which does not have a form as “explicit” as (1)) is always smaller than the ones for Gaussian having the same means and variance $\sigma^2$.

A good algorithm should have an expected sample complexity as close as possible to these lower bounds. Several algorithms for $(\epsilon)$-BAI are based on modifications of the UCB algorithm [24, 17, 14]. Others compute approximate solutions to the lower bound maximization problem and sample arms in order to approach the solution [15, 11, 39]. Our method belongs to the family of Top Two algorithms [34, 36, 21], which select at each time two arms called leader and challenger, and sample among them. It is the first Top Two algorithm for the $\epsilon$-BAI problem (for $\epsilon > 0$).

**Any time and uniform $\epsilon$-error bound** In addition to the fixed-confidence guarantees, we will prove a bound on the probability of error for any time $n$ and any error $\epsilon$, similarly to the results of [41]. That is, we bound $\mathbb{P}_{\nu}(\hat{\eta}_n \notin \mathcal{I}_{\epsilon}(\mu))$ for all $n$ and all $\epsilon$. This gives a bound on the probability of error in $\epsilon$-BAI, and a bound on the simple regret of the sampling rule by integrating: $\mathbb{E}_{\nu}[\mu_* - \mu_{\hat{\eta}_n}] = \int \mathbb{P}_{\nu}(\hat{\eta}_n \notin \mathcal{I}_{\epsilon}(\mu))d\epsilon$.

The literature mostly focuses on the fixed budget setting, where the time $T$ at which we evaluate the error probability is known and can be used as a parameter of the algorithm. Notable algorithms are successive rejects (SR, [1]) and sequential halving (SH, [25]). These algorithms can be extended to not depend on $T$ by using a doubling trick [23, 41]. That trick considers a sequence of algorithms that are run with budgets $(T_k)_k$, with $T_{k+1} = 2T_k$ and $T_1 = 2K[\log_2 K]$. Past observations are dropped when reaching $T_k$, and the obtained recommendation is used until the budget $T_{k+1}$ is reached.

## 1.1 Contributions

We propose the EB-TC$_{\epsilon_0}$ algorithm for identification in bandits, with a slack parameter $\epsilon_0 > 0$, originally motivated by $\epsilon_0$-BAI. We study its combination with a stopping rule for fixed confidence $\epsilon$-BAI (possibly with $\epsilon_0 \ne \epsilon$) and also its probability of error and simple regret at any time.

* EB-TC$_{\epsilon_0}$ performs well empirically compared to existing methods, both for the expected sample complexity criterion in fixed confidence $\epsilon$-BAI and for the anytime simple regret criterion. It is in addition easy to implement and computationally inexpensive in our regime.

* We prove upper bounds on the sample complexity of EB-TC$_{\epsilon_0}$ in fixed confidence $\epsilon$-BAI with sub-Gaussian distributions, both asymptotically (Theorem 1) as $\delta \to 0$ and for any $\delta$ (Theorem 2). In particular, EB-TC$_{\epsilon}$ with $\epsilon > 0$ is asymptotically optimal for $\epsilon$-BAI with Gaussian distributions.

* We prove a uniform $\epsilon$-error bound valid for any time for EB-TC$_{\epsilon_0}$. This gives in particular a fixed budget error bound and a control of the expected simple regret of the algorithm (Theorem 3 and Corollary 1).

# 2 Anytime Top Two sampling rule

We propose an anytime Top Two algorithm, named EB-TC$_{\epsilon_0}$ and summarized in Figure 1.

**Recommendation rule** Let $N_{n,i} := \sum_{t \in [n-1]} 1$ ($I_t = i$) be the number of pulls of arm $i$ before time $n$, and $\mu_{n,i} := \frac{1}{N_{n,i}} \sum_{t \in [n-1]} X_{t,I_t} 1$ ($I_t = i$) be its empirical mean. At time $n > K$, we recommend the Empirical Best (EB) arm $\hat{\eta}_n \in \arg \max_{i \in [K]} \mu_{n,i}$ (where ties are broken arbitrarily).
1. **Input:** slack $\varepsilon_0 > 0$, proportion $\beta \in (0, 1)$ (only for fixed proportions).

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

3. Set $\bar{\beta}_{n+1}(B_n, C_n) = (T_n(B_n, C_n)\bar{\beta}_n(B_n, C_n) + \beta_n(B_n, C_n))/T_{n+1}(B_n, C_n)$ with [fixed] $\beta_n(i, j) = \beta$ or [IDS] $\beta_n(i, j) = N_{n,j}/(N_{n,i} + N_{n,j})$ and $T_{n+1}(B_n, C_n) = T_n(B_n, C_n) + 1$.

4. Set $I_n = C_n$ if $N_{n,C_n}^{B_n} \le (1 - \bar{\beta}_{n+1}(B_n, C_n))T_{n+1}(B_n, C_n)$, otherwise set $I_n = B_n$.

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

<caption>Figure 1: EB-TC$_{\varepsilon_0}$ algorithm with fixed or IDS proportions.</caption>

## 2.1 Anytime Top Two sampling rule

We start by sampling each arm once. At time $n > K$, a Top Two sampling rule defines a leader $B_n \in [K]$ and a challenger $C_n \neq B_n$. It then chooses the arm to pull among them. For the leader/challenger pair, we consider the Empirical Best (EB) leader $B_n^{EB} = \hat{i}_n$ and, given a slack $\varepsilon_0 > 0$, the Transportation Cost (TC$_{\varepsilon_0}$) challenger

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

The algorithm then needs to choose between $B_n$ and $C_n$. In order to do so, we use a so-called tracking procedure [15]. We define one tracking procedure per pair of leader/challenger $(i, j) \in [K]^2$ such that $i \neq j$, hence we have $K(K-1)$ independent tracking procedures. For each pair $(i, j)$ of leader and challenger, the associated tracking procedure will ensure that the proportion of times the algorithm pulled the leader $i$ remains close to a target average proportion $\bar{\beta}_n(i, j) \in (0, 1)$. At each round $n$, only one tracking rule is considered, i.e. the one of the pair $(i, j) = (B_n, C_n)$.

We define two variants of the algorithm that differ in the way they set the proportions $\bar{\beta}_n(i, j)$. Fixed proportions set $\bar{\beta}_n(i, j) = \beta$ for all $(n, i, j) \in \mathbb{N} \times [K]^2$, where $\beta \in (0, 1)$ is fixed beforehand. Information-Directed Selection (IDS) [40] defines $\beta_n(i, j) = N_{n,j}/(N_{n,i} + N_{n,j})$ and sets $\bar{\beta}_n(i, j) := T_n(i, j)^{-1} \sum_{t \in [n-1]} 1((B_t, C_t) = (i, j)) \beta_t(i, j)$ where $T_n(i, j) := \sum_{t \in [n-1]} 1((B_t, C_t) = (i, j))$ is the selection count of arms $(i, j)$ as leader/challenger.

Let $N_{n,j}^i := \sum_{t \in [n-1]} 1((B_t, C_t) = (i, j), I_t = j)$ be the number of pulls of arm $j$ at rounds in which $i$ was the leader. We set $I_n = C_n$ if $N_{n,C_n}^{B_n} \le (1 - \bar{\beta}_{n+1}(B_n, C_n))T_{n+1}(B_n, C_n)$ and $I_n = B_n$ otherwise. Using Theorem 6 in [12] for each tracking procedure (i.e. each pair $(i, j)$) yields Lemma 2 (proved in Appendix H).

**Lemma 2.** For all $n > K$, $i \in [K]$, $j \neq i$, we have $-1/2 \le N_{n,j}^i - (1 - \bar{\beta}_n(i, j))T_n(i, j) \le 1$.

The TC$_{\varepsilon_0}$ challenger seeks to minimize an empirical version of a quantity that appears in the lower bound for $\varepsilon_0$-BAI (Lemma 1). As such, it is a natural extension of the TC challenger used in the T3C algorithm [36] for $\varepsilon_0 = 0$. In earlier works on Top Two methods [34, 32, 36], the choice between leader and challenger is randomized: given a fixed proportion $\beta \in (0, 1)$, set $I_n = B_n$ with probability $\beta$, otherwise $I_n = C_n$. [20] replaced randomization by tracking, and [40] proposed IDS to define adaptive proportions $\beta_n(B_n, C_n) \in (0, 1)$. In this work we study both fixed proportions with $\beta = 1/2$ and adaptive proportions with IDS. Empirically, we observe slightly better performances when using IDS (e.g. Figure 7 in Appendix J.2.1). While [20] tracked the leader with $K$ procedures, we consider $K(K-1)$ independent tracking procedures depending on the current leader/challenger pair.

**Choosing $\varepsilon_0$** [21] shows that EB-TC (i.e. EB-TC$_{\varepsilon_0}$ with slack $\varepsilon_0 = 0$) suffers from poor empirical performance for moderate $\delta$ in BAI (see Appendix D.3 in [21] for a detailed discussion). Therefore, the choice of the slack $\varepsilon_0 > 0$ is critical since it acts as a regularizer which naturally induces sufficient exploration. By setting $\varepsilon_0$ too small, the EB-TC$_{\varepsilon_0}$ algorithm will become as greedy as EB-TC and perform poorly. Having $\varepsilon_0$ too large will flatten differences between sub-optimal arms, hence it will behave more uniformly. We observe from the theoretical guarantees and from our experiments that it is best to take $\varepsilon_0 = \varepsilon$ for $\varepsilon$-BAI, but the empirical performance is only degrading slowly for $\varepsilon_0 > \varepsilon$. Taking $\varepsilon_0 < \varepsilon$ leads to very poor performance. We discuss this trade-off in more details in our experiments (e.g. Figures 5, 6 and 7 in Appendix J.2.1). When tackling BAI, the limitation of EB-TC can be solved by adding an implicit exploration mechanism in the choice of the leader/challenger
pair. For the choice of leader, we can use randomization (TS leader [34, 32, 36]) or optimism (UCB leader [20]). For the choice of the challenger, we can use randomization (RS challenger [34]) or penalization (TCI challenger [21], KKT challenger [40] or EI challenger [32]).

**Anytime sampling rule** EB-TC$_{ε_0}$ is independent of a budget of samples T or a confidence parameter $\delta$. This anytime sampling rule can be regarded as a stream of empirical means counts $(\mu_n, N_n)_{n>K}$ (which could trigger stopping) and a stream of recommendations $\hat{\mu}_n = i^*(\mu_n)$. These streams can be used by agents with different kinds of objectives. The fixed-confidence setting couples it with a stopping rule to be $(\varepsilon, \delta)$-PAC. It can also be used to get an $\varepsilon$-good recommendation with large probability at any given time $n$.

## 2.2 Stopping rule for fixed-confidence $\varepsilon$-best-arm identification

In addition to the sampling and recommendation rules, the fixed-confidence setting requires a stopping rule. Given an error/confidence pair, the GLR$_\varepsilon$ stopping rule [15] prescribes to stop at the time

$$ \tau_{\varepsilon, \delta} = \inf \left\{ n > K \mid \min_{i \neq \hat{\mu}_n} \frac{\mu_{n, \hat{\mu}_n} - \mu_{n, i} + \varepsilon}{\sqrt{1/N_{n, \hat{\mu}_n} + 1/N_{n, i}}} \ge \sqrt{2c(n-1, \delta)} \right\} \quad \text{with} \quad \hat{\mu}_n = i^*(\mu_n), \quad (3) $$

where $c: \mathbb{N} \times (0, 1) \to \mathbb{R}_+$ is a threshold function. Lemma 3 gives a threshold ensuring that the GLR$_\varepsilon$ stopping rule is $(\varepsilon, \delta)$-PAC for all $\varepsilon \ge 0$ and $\delta \in (0, 1)$, independently of the sampling rule.

**Lemma 3 ([27]).** Let $\varepsilon \ge 0$ and $\delta \in (0, 1)$. Given any sampling rule, using the threshold

$$ c(n, \delta) = 2C_G(\log((K-1)/\delta)/2) + 4 \log(4 + \log(n/2)) \quad (4) $$

with the stopping rule (3) with error/confidence pair $(\varepsilon, \delta)$ yields a $(\varepsilon, \delta)$-PAC algorithm for sub-Gaussian distributions. The function $C_G$ is defined in (23). It satisfies $C_G(x) \approx x + \log(x)$.

## 3 Fixed-confidence theoretical guarantees

To study $\varepsilon$-BAI in the fixed-confidence setting, we couple EB-TC$_{ε_0}$ with the GLR$_\varepsilon$ stopping rule (3) using error $\varepsilon \ge 0$, confidence $\delta \in (0, 1)$ and threshold (4). The resulting algorithm is $(\varepsilon, \delta)$-PAC by Lemma 3. We derive upper bounds on the expected sample complexity $E_\nu[\tau_{\varepsilon, \delta}]$ both in the asymptotic regime of $\delta \to 0$ (Theorem 1) and for finite confidence when $\varepsilon = \varepsilon_0$ (Theorem 2).

**Theorem 1.** Let $\varepsilon \ge 0$, $\varepsilon_0 > 0$ and $(\beta, \delta) \in (0, 1)^2$. Combined with GLR$_\varepsilon$ stopping (3), the EB-TC$_{ε_0}$ algorithm is $(\varepsilon, \delta)$-PAC and it satisfies that, for all $\nu \in D^K$ with mean $\mu$ such that $|i^*(\mu)| = 1$,

$$ [\text{IDS}] \limsup_{\delta \to 0} \frac{E_\nu[\tau_{\varepsilon, \delta}]}{\log(1/\delta)} \le T_{\varepsilon_0}(\mu) D_{\varepsilon, \varepsilon_0}(\mu) \quad \text{and} \quad [\text{fixed } \beta] \limsup_{\delta \to 0} \frac{E_\nu[\tau_{\varepsilon, \delta}]}{\log(1/\delta)} \le T_{\varepsilon_0, \beta}(\mu) D_{\varepsilon, \varepsilon_0}(\mu), $$

$$ \text{where } D_{\varepsilon, \varepsilon_0}(\mu) = (1 + \max_{i \neq i^*} (\varepsilon_0 - \varepsilon) / (\mu_* - \mu_i + \varepsilon))^2. $$

While Theorem 1 holds for all sub-Gaussian distributions, it is particularly interesting for Gaussian ones, in light of Lemma 1. When choosing $\varepsilon = \varepsilon_0$ (i.e. $D_{\varepsilon_0, \varepsilon_0}(\mu) = 1$), Theorem 1 shows that EB-TC$_{ε_0}$ is asymptotically optimal for Gaussian bandits when using IDS proportions and asymptotically $\beta$-optimal when using fixed proportions $\beta$. We also note that Theorem 1 is not conflicting with the lower bound of Lemma 1, as shown in Lemma 11 in Appendix C. Empirically we observe that the empirical stopping time can be drastically worse when taking $\varepsilon_0 < \varepsilon$, and close to the optimal one when $\varepsilon_0 > \varepsilon$ (Figures 5, 6 and 7 in Appendix J.2.1).

Until recently [40], proving asymptotic optimality of Top Two algorithms with adaptive choice $\beta$ was an open problem in BAI. In this work, we prove that their choice of IDS proportions also yield asymptotically optimal algorithms for $\varepsilon$-BAI. While the proof of Theorem 1 assumes the existence of a unique best arm, it holds for instances having sub-optimal arms with the same mean. This is an improvement compared to existing asymptotic guarantees on Top Two algorithms which rely on the assumption that the means of all arms are different [32, 36, 21]. The improvement is possible thanks to the regularization induced by the slack $\varepsilon_0 > 0$.

While asymptotic optimality in the $\varepsilon$-BAI setting was already achieved for various algorithms (e.g. $\varepsilon$-Track-and-Stop (TaS) [16], Sticky TaS [10] or $L\varepsilon$BAI [19]), none of them obtained non-asymptotic guarantees. Despite their theoretical interest, asymptotic results provide no guarantee on the performance for moderate $\delta$. Furthermore, asymptotic results on Top Two algorithms require a
unique best arm regardless of the considered error $\epsilon$: reaching asymptotic (β-)optimality implicitly means that the algorithm eventually allocates samples in an optimal way that depends on the identity of the unique best arm, and that requires the unique best arm to be identified. As our focus is $\epsilon$-BAI, our guarantees should only require that one of the $\epsilon$-good arms is identified and should hold for instances having multiple best arms. The upper bound should scale with $\epsilon_0^{-2}$ instead of $\Delta_{\min}^{-2}$ when $\Delta_{\min}$ is small. Theorem 2 satisfies these requirements.

**Theorem 2.** Let $\delta \in (0, 1)$ and $\epsilon_0 > 0$. Combined with GLR$_{\epsilon_0}$ stopping (3), the EB-TC$_{\epsilon_0}$ algorithm with fixed $\beta = 1/2$ is $(\epsilon_0, \delta)$-PAC and satisfies that, for all $\nu \in \mathcal{D}^K$ with mean $\mu$,

$$ \mathbb{E}_{\nu}[\tau_{\epsilon_0, \delta}] \leq \inf_{\tilde{\epsilon} \in [0, \epsilon_0]} \max\{T_{\mu, \epsilon_0}(\delta, \tilde{\epsilon}) + 1, S_{\mu, \epsilon_0}(\tilde{\epsilon})\} + 2K^2, $$

where $T_{\mu, \epsilon_0}(\delta, \tilde{\epsilon})$ and $S_{\mu, \epsilon_0}(\tilde{\epsilon})$ are defined by

$$ T_{\mu, \epsilon_0}(\delta, \tilde{\epsilon}) = \sup\{n \mid n-1 \leq 2(1+\gamma)^2 \sum_{i \in \mathcal{I}_{\tilde{\epsilon}}(\mu)} T_{\epsilon_0, 1/2}(\mu, i)(\sqrt{c(n-1, \delta)} + \sqrt{4 \log n})^2\}, $$

$$ S_{\mu, \epsilon_0}(\tilde{\epsilon}) = h_1 \left( \frac{16(1 + \gamma^{-1})}{a_{\mu, \epsilon_0}(\tilde{\epsilon})} H_{\mu, \epsilon_0}(\tilde{\epsilon}), \frac{(1 + \gamma^{-1})K^2}{a_{\mu, \epsilon_0}(\tilde{\epsilon})} + 1 \right), $$

$$ a_{\mu, \epsilon_0}(\tilde{\epsilon}) = \frac{\min_{i \in \mathcal{I}_{\tilde{\epsilon}}(\mu)} T_{\epsilon_0, 1/2}(\mu, i)}{\sum_{i \in \mathcal{I}_{\tilde{\epsilon}}(\mu)} T_{\epsilon_0, 1/2}(\mu, i)} \min_{i \in \mathcal{I}_{\tilde{\epsilon}}(\mu), j \neq i} w_{\epsilon_0, 1/2}(\mu, i)_j, $$

where $\gamma \in (0, 1/2]$ is an analysis parameter and $h_1(y, z) \approx z + y \log(z + y \log(y))$ as in Lemma 51. $T_{\epsilon_0, 1/2}(\mu, i)$ and $w_{\epsilon_0, 1/2}(\mu, i)$ are defined in (1) and

$$ H_{\mu, \epsilon_0}(\tilde{\epsilon}) := \frac{2|i^*(\mu)|}{\Delta_{\mu}(\tilde{\epsilon})^2} + (|\mathcal{I}_{\tilde{\epsilon}}(\mu) \setminus i^*(\mu)|)C_{\mu, \epsilon_0}(\tilde{\epsilon})^2 + \sum_{i \notin \mathcal{I}_{\tilde{\epsilon}}(\mu)} \max\{C_{\mu, \epsilon_0}(\tilde{\epsilon}), \sqrt{2}\Delta_i^{-1}\}^2, \quad (5) $$

$$ \text{with } \Delta_{\mu}(\tilde{\epsilon}) = \min_{k \notin \mathcal{I}_{\tilde{\epsilon}}(\mu)} \Delta_k \text{ and } C_{\mu, \epsilon_0}(\tilde{\epsilon}) = \max\{2\Delta_{\mu}(\tilde{\epsilon})^{-1} - \epsilon_0^{-1}, \epsilon_0^{-1}\}. $$

The upper bound on $\mathbb{E}_{\nu}[\tau_{\epsilon_0, \delta}]$ involves a $\delta$-dependent term $T_{\mu, \epsilon_0}(\delta, \tilde{\epsilon})$ and a $\delta$-independent term $S_{\mu, \epsilon_0}(\tilde{\epsilon})$. The choice of $\tilde{\epsilon}$ influences the compromise between those, and the infimum over $\tilde{\epsilon}$ means that our algorithm benefits from the best possible trade-off. In the asymptotic regime, we take $\tilde{\epsilon} = 0$ and $\gamma \to 0$ and we obtain $\lim_{\delta \to 0} \mathbb{E}_{\nu}[\tau_{\epsilon_0, \delta}]/\log(1/\delta) \leq 2|i^*(\mu)|T_{\epsilon_0, 1/2}(\mu)$. When $|i^*(\mu)| = 1$, we recover the asymptotic result of Theorem 1 up to a multiplicative factor 2. For multiple best arms, the asymptotic sample complexity is at most a factor $2|i^*(\mu)|$ from the $\beta$-optimal one.

Given a finite confidence, the dominant term will be $S_{\mu, \epsilon_0}(\tilde{\epsilon})$. For $\tilde{\epsilon} = 0$, we show that $H_{\mu, \epsilon_0}(0) = O(K \min\{\Delta_{\min}, \epsilon_0\}^{-2})$, hence we should consider $\tilde{\epsilon} > 0$ to avoid the dependency in $\Delta_{\min}$. For $\tilde{\epsilon} = \epsilon_0$, there exists instances such that $\max_{i \in \mathcal{I}_{\tilde{\epsilon}}(\mu)} T_{\epsilon_0, 1/2}(\mu, i)$ is arbitrarily large, hence $S_{\mu, \epsilon_0}(\epsilon_0)$ will be very large as well. The best trade-off is attained in the interior of the interval $(0, \epsilon_0)$. For $\tilde{\epsilon} = \epsilon_0/2$, Lemma 10 shows that $T_{\epsilon_0, 1/2}(\mu, i) = O(K/\epsilon_0^2)$ for all $i \in \mathcal{I}_{\epsilon_0/2}(\mu)$ and $H_{\mu, \epsilon_0}(\epsilon_0/2) = O(K/\epsilon_0^2)$. Therefore, we obtain an upper bound $O(|\mathcal{I}_{\epsilon_0/2}(\mu)|K\epsilon_0^{-2} \log \epsilon_0^{-1})$.

Likewise, Lemma 10 shows that $\min_{j \neq i} w_{\epsilon_0, 1/2}(\mu, i)_j \geq (16(K-2)+2)^{-1}$ for all $i \in \mathcal{I}_{\epsilon_0/2}(\mu)$. While the dependency in $a_{\mu, \epsilon_0}(\epsilon_0/2)$ is milder in $\epsilon$-BAI than in BAI (as it is bounded away from 0), we can improve it by using a refined analysis (see Appendix E). Introduced in [20], this method allows to clip $\min_{j \neq i} w_{\epsilon_0, 1/2}(\mu, i)_j$ by a fixed value $x \in [0, (K-1)^{-1}]$ for all $i \in \mathcal{I}_{\tilde{\epsilon}}(\mu)$.

**Comparison with existing upper bounds** The LUCB algorithm [24] has a structure similar to a Top Two algorithm, with the differences that LUCB samples both the leader and the challenger and that it stops when the gap between the UCB and LCB indices is smaller than $\epsilon_0$. As LUCB satisfies $\mathbb{E}_{\mu}[\tau_{\epsilon_0, \delta}] \leq 292H_{\epsilon_0}(\mu) \log(H_{\epsilon_0}(\mu)/\delta) + 16$ where $H_{\epsilon_0}(\mu) = \sum_i(\max\{\Delta_i, \epsilon_0/2\})^{-2}$, it enjoys better scaling than EB-TC$_{\epsilon_0}$ for finite confidence. However, since the empirical allocation of LUCB is not converging towards $w_{\epsilon_0, 1/2}(\mu)$, it is not asymptotically 1/2-optimal. While LUCB has better moderate confidence guarantees, there is no hope to prove anytime performance bounds since LUCB indices depends on $\delta$. In contrast, EB-TC$_{\epsilon_0}$ enjoys such guarantees (see Section 4).

**Key technical tool for the non-asymptotic analysis** We want to ensure that EB-TC$_{\epsilon_0}$ eventually selects only $\epsilon$-good arms as leader, for any error $\epsilon \geq 0$. Our proof strategy is to show that if the leader is not an $\epsilon$-good arm and empirical means do not deviate too much from the true means, then either the current leader or the current challenger was selected as leader or challenger less than a given quantity. We obtain a bound on the total number of times that can happen.
**Lemma 4.** Let $\delta \in (0, 1]$ and $n > K$. Let $T_n(i) := \sum_{j \neq i} (T_n(i, j) + T_n(j, i))$ be the number of times arm $i$ was selected in the leader/challenger pair. Assume there exists a sequence of events $(A_t(n, \delta))_{n \ge t > K}$ and positive reals $(D_i(n, \delta))_{i \in [K]}$ such that, for all $t \in \{K+1, \dots, n\}$, under the event $A_t(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. \qquad (6) $$

Then, we have $\sum_{t=K+1}^{n} 1(A_t(n, \delta)) \le \sum_{i \in [K]} D_i(n, \delta)$.

To control the deviation of the empirical means and empirical gaps to their true value, we use a sequence of concentration events $(\mathcal{E}_{n,\delta})_{n>T}$ defined in Lemma 45 (Appendix G.2) such that $\mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^c) \le K^2 \delta n^{-s}$ where $s \ge 0$ and $\delta \in (0, 1]$. For the EB-TC$_{\varepsilon_0}$ algorithm with fixed $\beta = 1/2$, we prove that, under $\mathcal{E}_{n,\delta}$, $\{B_t^{EB} \notin \mathcal{I}_{\varepsilon}(\mu)\}$ is a “bad” event satisfying the assumption of Lemma 4. This yields Lemma 5, which essentially says that the leader is an $\varepsilon$-good arm except for a logarithmic number of rounds.

**Lemma 5.** Let $\delta \in (0, 1]$, $n > K$ and $\varepsilon \ge 0$. Under the event $\mathcal{E}_{n,\delta}$, we have

$$ \sum_{i \in \mathcal{I}_{\varepsilon}(\mu)} \sum_{j} T_n(i, j) \ge n - 1 - 8H_{\mu, \varepsilon_0}(\varepsilon)f_2(n, \delta) - 3K^2, $$

where $f_2(n, \delta) = \log(1/\delta) + (2+s) \log n$ and $H_{\mu, \varepsilon_0}(\varepsilon)$ is defined in (5).

Noticeably, Lemma 5 holds for any $\varepsilon \ge 0$ even when there are multiple best arms. As expected the number of times the leader is not among the $\varepsilon_0$-good arms depends on $H_{\mu, \varepsilon_0}(\varepsilon_0) = O(K/\varepsilon_0^2)$. The number of times the leader is not among the best arms depends on $H_{\mu, \varepsilon_0}(0) = O(K(\min\{\Delta_{\min}, \varepsilon_0\})^{-2})$.

**Time-varying slack** Theorem 1 shows the asymptotic optimality of the EB-TC$_{\varepsilon_0}$ algorithm with IDS for $\varepsilon_0$-BAI (where $\varepsilon_0 > 0$). To obtain optimality for BAI, we consider time-varying slacks $(\varepsilon_n)_n$, where $(\varepsilon_n)_n$ is decreasing, $\varepsilon_n > 0$ and $\varepsilon_n \to_{+\infty} 0$. A direct adaptation of our asymptotic analysis on $\mathbb{E}_{\nu}[\tau_{0,\delta}]$ (see Appendix D), regardless of the choice of $(\varepsilon_n)_n$, one can show that using GLR$_0$ stopping, the EB-TC$_{(\varepsilon_n)_n}$ algorithm with IDS is $(0, \delta)$-PAC and is asymptotically optimal in BAI. Its empirical performance is however very sensitive to the choice of $(\varepsilon_n)_n$ (Appendix J.2.3).

# 4 Beyond fixed-confidence guarantees

Could an algorithm analyzed in the fixed-confidence setting be used for the fixed-budget or even anytime setting? This question is especially natural for EB-TC$_{\varepsilon_0}$, which does not depend on the confidence parameter $\delta$. Yet its answer is not obvious, as it is known that algorithms that have optimal asymptotic guarantees in the fixed-confidence setting can be sub-optimal in terms of error probability. Indeed [28] prove in their Appendix C that for any asymptotically optimal (exact) BAI algorithm, there exists instances in which the error probability cannot decay exponentially with the horizon, which makes them worse than the (minimax optimal) uniform sampling strategy [5].

Their argument also applies to $\beta$-optimal algorithms, hence to EB-TC$_0$ with $\beta = 1/2$. However, whenever $\varepsilon_0$ is positive, Theorem 3 reveals that the error probability of EB-TC$_{\varepsilon_0}$ always decays exponentially, which redeems the use of optimal fixed-confidence algorithms for a relaxed BAI problem in the anytime setting. Going further, this result provides an anytime bound on the probability to recommend an arm that is not $\varepsilon$-optimal, for any error $\varepsilon \ge 0$. This bound involves instance-dependent complexities depending solely on the gaps in $\mu$. To state it, we define $C_{\mu} := |\{\mu_i | i \in [K]\}|$ as the number of distinct arm means in $\mu$ and let $C_{\mu}(i) := \{k \in [K] | \mu_* - \mu_k = \Delta_i\}$ be the set of arms having mean gap $\Delta_i$ where the gaps are sorted by increasing order $0 = \Delta_1 < \Delta_2 < \dots < \Delta_{C_{\mu}}$. For all $\varepsilon \ge 0$, let $i_{\mu}(\varepsilon) = i$ if $\varepsilon \in [\Delta_i, \Delta_{i+1})$ (with the convention $\Delta_{C_{\mu}+1} = +\infty$). Theorem 3 shows that the exponential decrease of $\mathbb{P}_{\nu}(\hat{i}_n \notin \mathcal{I}_{\varepsilon}(\mu))$ is linear.

**Theorem 3.** (see Theorem 6 in Appendix F) Let $\varepsilon_0 > 0$. The EB-TC$_{\varepsilon_0}$ algorithm with fixed proportions $\beta = 1/2$ satisfies that, for all $\nu \in \mathcal{D}^K$ with mean $\mu$, for all $\varepsilon \ge 0$, for all $n > 5K^2/2$,

$$ \mathbb{P}_{\nu}(\hat{i}_n \notin \mathcal{I}_{\varepsilon}(\mu)) \le K^2 e^2 (2 + \log n)^2 \exp \left( -p \left( \frac{n - 5K^2/2}{8H_{i_{\mu}(\varepsilon)}(\mu, \varepsilon_0)} \right) \right). $$

where $p(x) = x - \log x$ and $(H_i(\mu, \varepsilon_0))_{i \in [C_{\mu}-1]}$ are such that $H_1(\mu, \varepsilon_0) = K(2\Delta_{\min}^{-1} + 3\varepsilon_0^{-1})^2$ and $K/\Delta_{i+1}^{-2} \le H_i(\mu, \varepsilon_0) \le K \min_{j \in [i]} \max\{2\Delta_{j+1}^{-1}, 2\frac{\Delta_{i+1}/\varepsilon_0+1}{\Delta_{i+1}-\Delta_j} + 3\varepsilon_0^{-1}\}^2$ for all $i > 1$.
This bound can be compared with the following uniform $\epsilon$-error bound of the strategy using uniform sampling and recommending the empirical best arm:

$$ \mathbb{P}(\hat{i}_n^U \notin \mathcal{I}_\epsilon(\mu)) \leq \sum_{i \notin \mathcal{I}_\epsilon(\mu)} \exp\left(-\frac{\Delta_i^2 |n/K|}{4}\right) \leq K \exp\left(-\frac{n-K}{4K \Delta_{i\mu}(\epsilon)+1}\right) $$

Recalling that the quantity $H_i(\mu, \epsilon_0)$ in Theorem 3 is always bounded from below by $2K\Delta_{i+1}^{-1}$, we get that our upper bound is larger than the probability of error of the uniform strategy, but the two should be quite close. For example for $\epsilon = 0$, we have

$$ \mathbb{P}_{\nu}(\hat{i}_n \notin i^*(\mu)) \leq \exp\left(-\Theta\left(\frac{n}{K(\Delta_{\min}^{-1} + \epsilon_0^{-1})^2}\right)\right), \quad \mathbb{P}_{\nu}(\hat{i}_n^U \notin i^*(\mu)) \leq \exp\left(-\Theta\left(\frac{n}{K\Delta_{\min}^{-2}}\right)\right). $$

Even if they provide a nice sanity-check for the use of a sampling rule with optimal fixed-confidence guarantees for $\epsilon_0$-BAI in the anytime regime, we acknowledge that these guarantees are far from optimal. Indeed, the work of [41] provides tighter anytime uniform $\epsilon$-error probability bounds for two algorithms: an anytime version of Sequential Halving [25] using a doubling trick (called DSH), and an algorithm called Bracketting Sequential Halving, that is designed to tackle a very large number of arms. Their upper bounds are of the form $\mathbb{P}_{\nu}(\hat{i}_n \notin \mathcal{I}_\epsilon(\mu)) \leq \exp(-\Theta(n/H(\epsilon)))$ with $H(\epsilon) = \frac{1}{g(\epsilon/2)} \max_{i \geq g(\epsilon)+1} \frac{i}{\Delta_i^2}$ where $g(\epsilon) = |\{i \in [K] | \mu_i \geq \mu^* - \epsilon\}|$. Therefore, they can be much smaller than $K\Delta_{i\mu}(\epsilon)+1$.

The BUCB algorithm of [26] is also analyzed for any level of error $\epsilon$, but in a different fashion. The authors provide bounds on its $(\epsilon, \delta)$-unverifiable sample complexity, defined as the expectation of the smallest stopping time $\tilde{\tau}$ satisfying $\mathbb{P}(\forall t \geq \tilde{\tau}, \hat{i}_n \in \mathcal{I}_\epsilon(\mu)) \geq 1 - \delta$. This notion is different from the sample complexity we use in this paper, which is sometimes called verifiable since it is the time at which the algorithm can guarantee that its error probability is less than $\delta$. Interestingly, to prove Theorem 3 we first prove a bound on the unverifiable sample complexity of EB-TC$_{\epsilon_0}$ which is valid for all $(\epsilon, \delta)$, neither of which are parameters of the algorithm. More precisely, we prove that $\mathbb{P}_{\nu}(\forall n > U_{i\mu}(\epsilon), \delta(\mu, \epsilon_0), \hat{i}_n \in \mathcal{I}_\epsilon(\mu)) \geq 1 - \delta$ for $U_{i\mu}(\epsilon), \delta(\mu, \epsilon_0) = \delta \to 0$ $8H_i(\mu, \epsilon_0) \log(1/\delta) + O(\log \log(1/\delta))$. As this statement is valid for all $\delta \in (0, 1)$, applying it for each $n$ to $\delta_n$ such that $U_{i\mu}(\epsilon), \delta_n(\mu, \epsilon_0) = n$, we obtain Theorem 3. We remark that such a trick cannot be applied to BUCB to get uniform $\epsilon$-error bounds for any time, as the algorithm does depend on $\delta$.

**Simple regret** As already noted by [41], uniform $\epsilon$-error bounds easily yield simple regret bounds. We state in Corollary 1 the one obtained for EB-TC$_{\epsilon_0}$. As a motivation to derive simple regret bounds, we observe that they readily translate to bounds on the cumulative regret for an agent observing the stream of recommendations $(\hat{i}_n)$ and playing arm $\hat{i}_n$. An exponentially decaying simple regret leads to a constant cumulative regret in this decoupled exploration/exploitation setting [2, 33].

**Corollary 1.** Let $\epsilon_0 > 0$. Let $p(x)$ and $(H_i(\mu, \epsilon_0))_{i \in [C_\mu - 1]}$ be defined as in Theorem 3. The EB-TC$_{\epsilon_0}$ algorithm with fixed $\beta = 1/2$ satisfies that, for all $\nu \in \mathcal{D}^K$ with mean $\mu$, for all $n > 5K^2/2$,

$$ \mathbb{E}_{\nu}[\mu_{*} - \mu_{\hat{i}_n}] \leq K^2 e^2 (2 + \log n)^2 \sum_{i \in [C_{\mu}-1]} (\Delta_{i+1} - \Delta_i) \exp\left(-p\left(\frac{n - 5K^2/2}{8H_i(\mu, \epsilon_0)}\right)\right). $$

Following the discussion above, this bound is not expected to be state-of-the-art, it rather justifies that EB-TC$_{\epsilon_0}$ with $\epsilon_0 > 0$ is not too much worse than the uniform sampling strategy. Yet, as we shall see in our experiments, the practical story is different. In Section 5, we compare the simple regret of EB-TC$_{\epsilon_0}$ to that of DSH in synthetic experiments with a moderate number of arms, revealing the superior performance of EB-TC$_{\epsilon_0}$.

# 5 Experiments

We assess the performance of the EB-TC$_{\epsilon_0}$ algorithm on Gaussian instances both in terms of its empirical stopping time and its empirical simple regret, and we show that it perform favorably compared to existing algorithms in both settings. For the sake of space, we only show the results for large sets of arms and for a specific instance with $|i^*(\mu)| = 2$.
<figure><img src="image_3.png" /><figcaption>Figure 2: (a) Empirical stopping time on “$\alpha = 0.3$” instances for varying $K$ and stopping rule (3) using $(\varepsilon, \delta) = (0.1, 0.01)$. The BAI algorithms T3C, EB-TCI and TTUCB are modified to be $\varepsilon$-BAI ones. (b) Empirical simple regret on instance $\mu = (0.6, 0.6, 0.55, 0.45, 0.3, 0.2)$, in which $\text{EB-TC}_{\varepsilon_0}$ with slack $\varepsilon_0 = 0.1$ and fixed $\beta = 1/2$ is used.</figcaption></figure>

**Empirical stopping time** We study the impact of large sets of arms (up to $K = 1000$) in $\varepsilon$-BAI for $(\varepsilon, \delta) = (0.1, 0.01)$ on the “$\alpha = 0.3$” scenario of [18] which sets $\mu_i = 1 - ((i-1)/(K-1))^{\alpha}$ for all $i \in [K]$. $\text{EB-TC}_{\varepsilon_0}$ with IDS and slack $\varepsilon_0 = \varepsilon$ is compared to existing $\varepsilon$-BAI algorithms having low computational cost. This precludes algorithms such as $\varepsilon$-Track-and-Stop (TaS) [16], Sticky TaS [10] or $\varepsilon$-BAI adaptation of FWS [39] and DKM [11]. In Appendix J.2.2, we compare $\text{EB-TC}_{\varepsilon}$ to those algorithms on benchmarks with smaller number of arms. We show that $\text{EB-TC}_{\varepsilon}$ performs on par with $\varepsilon$-TaS and $\varepsilon$-FWS, but outperforms $\varepsilon$-DKM. As Top Two benchmarks with fixed $\beta = 1/2$, we consider T3C [36], EB-TCI [21] and TTUCB [20]. To provide a fair comparison, we adapt them to tackle $\varepsilon$-BAI by using the stopping rule (3) and by adapting their sampling rule to use the $\text{TC}\varepsilon$ challenger from (2) (with a penalization $\log N_{n,i}$ for EB-TCI). We use the heuristic threshold $c(n, \delta) = \log((1 + \log n)/\delta)$. While it is too small to ensure the $(\varepsilon, \delta)$-PAC property, it still yields an empirical error which is several orders of magnitude lower than $\delta$. Finally, we compare with LUCB [24] and uniform sampling. For a fair comparison, LUCB uses $\sqrt{2c(n-1, \delta)/N_{n,i}}$ as bonus, which is also too small to yield valid confidence intervals. Our results are averaged over 100 runs, and the standard deviations are displayed. In Figure 2(a), we see that $\text{EB-TC}_{\varepsilon}$ performs on par with the $\varepsilon$-T3C heuristic, and significantly outperforms the other algorithms. While the scaling in $K$ of $\varepsilon$-EB-TCI and LUCB appears to be close to the one of $\text{EB-TC}_{\varepsilon}$, $\varepsilon$-TTUCB and uniform sampling obtain a worse one. Figure 2(a) also reveals that the regularization ensured by the $\text{TC}\varepsilon$ challenger is sufficient to ensure enough exploration, hence other exploration mechanisms are superfluous (TS/UCB leader or TCI challenger).

**Anytime empirical simple regret** The $\text{EB-TC}_{\varepsilon_0}$ algorithm with fixed $\beta = 1/2$ and $\varepsilon_0 = 0.1$ is compared to existing algorithms on the instance $\mu = (0.6, 0.6, 0.55, 0.45, 0.3, 0.2)$ from [16], which has two best arms. As benchmark, we consider Doubling Successive Reject (DSR) and Doubling Sequential Halving (DSH), which are adaptations of the elimination based algorithms SR [1] and 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. These doubling-based algorithms have empirical error decreasing by steps: they change their recommendation only before they restart. In Figure 2(b), we plot the average of the simple regret over 10000 runs and the standard deviation of that average (which is too small to see clearly). We observe that $\text{EB-TC}_{\varepsilon_0}$ outperforms uniform sampling, as well as DSR and DSH, which both perform worse due to the dropped observations. The favorable performance of $\text{EB-TC}_{\varepsilon_0}$ is confirmed on other instances from [16], and for “two-groups” instances with varying $|i^*(\mu)|$ (see Figures 10 and 12).

**Supplementary experiments** Extensive experiments and implementation details are available in Appendix J. In Appendix J.2.1, we compare the performance of $\text{EB-TC}_{\varepsilon_0}$ with different slacks $\varepsilon_0$ for IDS and fixed $\beta = 1/2$. In Appendix J.2.2, we demonstrate the good empirical performance of $\text{EB-TC}_{\varepsilon_0}$ compared to state-of-the-art methods in the fixed-confidence $\varepsilon$-BAI setting, compared to DSR and DSH for the empirical simple regret, and compared to SR and SH for the probability of 0-error in the fixed-budget setting (Figure 13). We consider a wide range of instances: random ones, benchmarks from the literature [18, 16] and “two-groups” instances with varying $|i^*(\mu)|$.
# 6 Perspectives

We have proposed the EB-TC<sub>ε₀</sub> algorithm, which is easy to understand and implement. EB-TC<sub>ε₀</sub> is the first algorithm to be simultaneously asymptotically optimal in the fixed-confidence ε₀-BAI setting (Theorem 1), have finite-confidence guarantees (Theorem 2), and have also anytime guarantees on the probability of error at any level ε (Theorem 3), hence on the simple regret (Corollary 1). Furthermore, we have demonstrated that the EB-TC<sub>ε₀</sub> algorithm achieves superior performance compared to other algorithms, in benchmarks where the number of arms is moderate to large. In future work, we will investigate its possible adaptation to the data-poor regime of [41] in which the number of arms is so large that any algorithm sampling each arm once is doomed to failure.

While our results hold for general sub-Gaussian distributions, the EB-TC<sub>ε₀</sub> algorithm with IDS and slack ε₀ > 0 only achieves asymptotic optimality for ε₀-BAI with Gaussian bandits. Even though IDS has been introduced by [40] for general single-parameter exponential families, it is still an open problem to show asymptotic optimality for distributions other than Gaussians. While our non-asymptotic guarantees on $E_ν[τ_{ε₀,δ}]$ and $E_ν[μ* - μ̂_n]$ were obtained for the EB-TC<sub>ε₀</sub> algorithm with fixed β = 1/2, we observed empirically better performance when using IDS. Deriving similar (or better) non-asymptotic guarantees for IDS is an interesting avenue for future work.

Finally, the EB-TC<sub>ε₀</sub> algorithm is a promising method to tackle structured bandits. Despite the existence of heuristics for settings such as Top-k identification [40], it is still an open problem to efficiently adapt Top Two approaches to cope for other structures such as ε-BAI in linear bandits.

# Acknowledgments and Disclosure of Funding

Experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr). This work has been partially supported by the THIA ANR program "AI_PhD@Lille". The authors acknowledge the funding of the French National Research Agency under the project BOLD (ANR-19-CE23-0026-04) and the project FATE (ANR22-CE23-0016-01).

# References

[1] J.-Y. Audibert, S. Bubeck, and R. Munos. Best Arm Identification in Multi-armed Bandits. In *Conference on Learning Theory*, 2010.

[2] O. Avner, S. Mannor, and O. Shamir. Decoupling exploration and exploitation in multi-armed bandits. In *Proceedings of the 29th International Conference on International Conference on Machine Learning*, pages 1107–1114, 2012.

[3] A. Barrier, A. Garivier, and T. Kocák. A non-asymptotic approach to best-arm identification for gaussian bandits. In *Proceedings of The 25th International Conference on Artificial Intelligence and Statistics*, 2022.

[4] S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. *Fondations and Trends in Machine Learning*, 5(1):1–122, 2012.

[5] S. Bubeck, R. Munos, and G. Stoltz. Pure Exploration in Finitely Armed and Continuous Armed Bandits. *Theoretical Computer Science* 412, 1832-1852, 412:1832–1852, 2011.

[6] L. Chen, J. Li, and M. Qiao. Towards instance optimal bounds for best arm identification. *Conference on Learning Theory*, 2017.

[7] L. Chen, J. Li, and M. Qiao. Nearly instance optimal sample complexity bounds for top-k arm selection. In *Artificial Intelligence and Statistics*, 2017.

[8] Y. Chen and I. O. Ryzhov. Balancing optimal large deviations in sequential selection. *Management Science*, 69(6):3457–3473, 2023.

[9] R. Degenne. *Impact of structure on the design and analysis of bandit algorithms*. PhD thesis, Université de Paris, 2019.
[10] R. Degenne and W. M. Koolen. Pure exploration with multiple correct answers. In *Advances in Neural Information Processing Systems (NeurIPS)*, 2019.

[11] R. Degenne, W. M. Koolen, and P. Ménard. Non-asymptotic pure exploration by solving games. In *Advances in Neural Information Processing Systems (NeurIPS)*, 2019.

[12] R. Degenne, H. Shao, and W. M. Koolen. Structure adaptive algorithms for stochastic bandits. In *International Conference on Machine Learning (ICML)*, 2020.

[13] E. Even-Dar, S. Mannor, and Y. Mansour. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems. *Journal of Machine Learning Research*, 7:1079–1105, 2006.

[14] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence. In *Advances in Neural Information Processing Systems*, 2012.

[15] A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In *Proceedings of the 29th Conference On Learning Theory*, 2016.

[16] A. Garivier and E. Kaufmann. Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models. *Sequential Analysis*, 40(1): 61–96, 2021.

[17] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck. lil'UCB: an Optimal Exploration Algorithm for Multi-Armed Bandits. In *Proceedings of the 27th Conference on Learning Theory*, 2014.

[18] K. G. Jamieson and R. D. Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In *Conference on Information Sciences and Systems (CISS)*, 2014.

[19] M. Jourdan and R. Degenne. Choosing answers in $\varepsilon$-best-answer identification for linear bandits. In *International Conference on Machine Learning (ICML)*, 2022.

[20] M. Jourdan and R. Degenne. Non-asymptotic analysis of a ucb-based top two algorithm. *arXiv preprint arXiv:2210.05431*, 2022.

[21] M. Jourdan, R. Degenne, D. Baudry, R. De Heide, and E. Kaufmann. Top two algorithms revisited. *Advances in Neural Information Processing Systems*, 2022.

[22] M. Jourdan, R. Degenne, and E. Kaufmann. Dealing with unknown variances in best-arm identification. *International Conference on Algorithmic Learning Theory*, 2023.

[23] K.-W. Jun and R. Nowak. Anytime exploration for multi-armed bandits using confidence information. In *International Conference on Machine Learning (ICML)*, 2016.

[24] S. Kalyanakrishnan, A. Tewari, P. Auer, and P. Stone. PAC subset selection in stochastic multi-armed bandits. In *International Conference on Machine Learning (ICML)*, 2012.

[25] Z. Karnin, T. Koren, and O. Somekh. Almost optimal Exploration in multi-armed bandits. In *International Conference on Machine Learning (ICML)*, 2013.

[26] J. Katz-Samuels and K. Jamieson. The true sample complexity of identifying good arms. In *International Conference on Artificial Intelligence and Statistics*, 2020.

[27] E. Kaufmann and W. M. Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. *Journal of Machine Learning Research*, 22(246):1–44, 2021.

[28] J. Komiyama, T. Tsuchiya, and J. Honda. Minimax optimal algorithms for fixed-budget best arm identification. In *Advances in Neural Information Processing Systems*, 2022.

[29] T. Lattimore and C. Szepesvari. *Bandit Algorithms*. Cambridge University Press, 2019.

[30] A. Locatelli, M. Gutzeit, and A. Carpentier. An optimal algorithm for the thresholding bandit problem. In *International Conference on Machine Learning (ICML)*, 2016.
[31] S. Mannor and J. Tsitsiklis. The Sample Complexity of Exploration in the Multi-Armed Bandit Problem. *Journal of Machine Learning Research*, pages 623–648, 2004.

[32] C. Qin, D. Klabjan, and D. Russo. Improving the expected improvement algorithm. In *Advances in Neural Information Processing Systems 30 (NIPS)*, 2017.

[33] C. Rouyer and Y. Seldin. Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits. In *Conference on Learning Theory*, pages 3227–3249. PMLR, 2020.

[34] D. Russo. Simple Bayesian algorithms for best arm identification. In *Proceedings of the 29th Conference on Learning Theory (COLT)*, 2016.

[35] S. Sabato. Epsilon-best-arm identification in pay-per-reward multi-armed bandits. *Advances in Neural Information Processing Systems*, 32, 2019.

[36] X. Shang, R. de Heide, E. Kaufmann, P. Ménard, and M. Valko. Fixed-confidence guarantees for bayesian best-arm identification. In *International Conference on Artificial Intelligence and Statistics (AISTATS)*, 2020.

[37] D. Shin, M. Broadie, and A. Zeevi. Tractable sampling strategies for ordinal optimization. *Operations Research*, 66(6):1693–1712, 2018.

[38] M. Simchowitz, K. Jamieson, and B. Recht. The simulator: Understanding adaptive sampling in the moderate-confidence regime. In *Conference on Learning Theory*, 2017.

[39] P.-A. Wang, R.-C. Tzeng, and A. Proutiere. Fast pure exploration via frank-wolfe. *Advances in Neural Information Processing Systems*, 2021.

[40] W. You, C. Qin, Z. Wang, and S. Yang. Information-directed selection for top-two algorithms. In *The Thirty Sixth Annual Conference on Learning Theory*, pages 2850–2851. PMLR, 2023.

[41] Y. Zhao, C. J. Stephens, C. Szepesvári, and K.-S. Jun. Revisiting simple regret: Fast rates for returning a good arm. In *40th International Conference on Machine Learning (ICML)*, 2023.
## A Outline

The appendices are organized as follows:

* Notation are summarized in Appendix B.

* In Appendix C, we show how the characteristic times and optimal allocations for $\varepsilon$-BAI can be reduced to the ones of a BAI problem with modified instances (Lemma 9).

* The asymptotic upper bound on the expected sample complexity of the EB-TC$_{\varepsilon_0}$ algorithm when combined with the stopping rule (4) is proven in Appendix D (Theorem 1).

* The non-asymptotic upper bound on the expected sample complexity of the EB-TC$_{\varepsilon_0}$ algorithm when combined with the stopping rule (4) is proven in Appendix E (Theorem 5).

* The upper bound on the probability of error and on the simple regret of the EB-TC$_{\varepsilon_0}$ algorithm is proven in Appendix F (Theorem 6), as well as the upper bound on its unverifiable expected sample complexity (Theorem 7).

* Appendix G gathers concentration results used for the calibration of the stopping rule (Lemma 3) and to control the empirical means and gaps.

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

* In Appendix I, we discuss the multiplicative notion of $\varepsilon$-goodness, propose the EB-TC$^{m}$, and show asymptotic guarantees on the expected sample complexity when combined with the appropriate GLR stopping rule (Theorem 8).

* Implementation details and additional experiments are presented in Appendix J.

<table><caption>Table 1: Notation for the setting.</caption><thead><tr><th>Notation</th><th>Type</th><th>Description</th></tr></thead><tbody><tr><td>K</td><td>N</td><td>Number of arms</td></tr><tr><td>ν<sub>i</sub></td><td>D</td><td>Sub-Gaussian distribution of arm i ∈ [K]</td></tr><tr><td>ν</td><td>D<sup>K</sup></td><td>Vector of sub-Gaussian distributions, ν := (ν<sub>i</sub>)<sub>i∈[K]</sub></td></tr><tr><td>μ<sub>i</sub></td><td>R</td><td>Mean of arm i ∈ [K]</td></tr><tr><td>μ</td><td>R<sup>K</sup></td><td>Vector of means, μ := (μ<sub>i</sub>)<sub>i∈[K]</sub></td></tr><tr><td>μ<sub>*</sub></td><td>R</td><td>Largest mean, μ<sub>*</sub> := max<sub>i∈[K]</sub> μ<sub>i</sub></td></tr><tr><td>Δ<sub>i</sub></td><td>R<sub>+</sub></td><td>Gap of arm i, Δ<sub>i</sub> := μ<sub>*</sub> - μ<sub>i</sub></td></tr><tr><td>i<sup>*</sup>(μ)</td><td>[K]</td><td>Best arms, i<sup>*</sup>(μ) := arg max<sub>i∈[K]</sub> μ<sub>i</sub></td></tr><tr><td>ε</td><td>R<sub>+</sub></td><td>Additive error of ε-good arms</td></tr><tr><td>I<sub>ε</sub>(μ)</td><td>[K]</td><td>ε-Good arms, I<sub>ε</sub>(μ) := {i ∈ [K] | Δ<sub>i</sub> ≤ ε}</td></tr><tr><td>T<sub>ε</sub>(μ), T<sub>ε,β</sub>(μ), T<sub>ε,β</sub>(μ, i)</td><td>R<sub>+</sub><sup>*</sup></td><td>Asymptotic (β-)characteristic time for ε-BAI</td></tr><tr><td>w<sub>ε</sub>(μ), w<sub>ε,β</sub>(μ), w<sub>ε,β</sub>(μ, i)</td><td>Δ<sub>K</sub></td><td>Asymptotic (β-)optimal allocation for ε-BAI</td></tr><tr><td>C<sub>μ</sub></td><td>[K]</td><td>Number of equivalence classes, C<sub>μ</sub> := {μ<sub>i</sub> | i ∈ [K]}</td></tr><tr><td>C<sub>μ</sub>(i)</td><td>[K]</td><td>Equivalence class, C<sub>μ</sub>(i) := {k ∈ [K] | μ<sub>*</sub> - μ<sub>k</sub> = Δ<sub>i</sub>}</td></tr></tbody></table>

## B Notation

We recall some commonly used notation: the set of integers $[n] := \{1, \dots, n\}$, the complement $X^c$ and interior $\tilde{X}$ of a set $X$, the indicator function $1(X)$ of an event, the probability $P_ν$ and the expectation $E_ν$ under distribution $ν$, Landau's notation $o$, $O$, $\Omega$ and $\Theta$, the $(K-1)$-dimensional probability simplex $\Delta_K := \{w \in R_K^+ | w \ge 0, \sum_{i \in [K]} w_i = 1\}$. The functions $C_G$ and $g_G$ are defined in (23), $\overline{W}_{-1}$ in Lemma 49, $h_1$ in Lemma 51, $\zeta$ is the Riemann $\zeta$ function. While Table 1 gathers problem-specific notation, Table 2 groups notation for the algorithms.
<table><caption>Table 2: Notation for algorithms.</caption><thead><tr><th>Notation</th><th>Type</th><th>Description</th></tr></thead><tbody><tr><td>B<sub>n</sub>, B<sup>EB</sup><sub>n</sub></td><td>[K]</td><td>(EB) Leader at time n</td></tr><tr><td>C<sub>n</sub>, C<sup>TCε<sub>0</sub></sup><sub>n</sub></td><td>[K]</td><td>(TC<sub>ε<sub>0</sub></sub>) Challenger at time n</td></tr><tr><td>I<sub>n</sub></td><td>[K]</td><td>Arm sampled at time n</td></tr><tr><td>X<sub>n,I<sub>n</sub></sub></td><td>R</td><td>Sample observed at the end of time n, i.e. X<sub>n,I<sub>n</sub></sub> ~ ν<sub>I<sub>n</sub></sub></td></tr><tr><td>F<sub>n</sub></td><td></td><td>History before time n, i.e. F<sub>n</sub> := σ(I<sub>1</sub>, X<sub>1,I<sub>1</sub></sub>, ..., I<sub>n</sub>, X<sub>n,I<sub>n</sub></sub>)</td></tr><tr><td>ŷ<sub>n</sub></td><td>[K]</td><td>Arm recommended before time n</td></tr><tr><td>τ<sub>ε,δ</sub></td><td>N</td><td>Sample complexity (stopping time)</td></tr><tr><td>c(n, δ)</td><td>N × (0, 1) → R<sup>*</sup><sub>+</sub></td><td>Stopping threshold function</td></tr><tr><td>N<sub>n,i</sub></td><td>N</td><td>Number of pulls of arm i before time n</td></tr><tr><td>μ<sub>n,i</sub></td><td>I</td><td>Empirical mean of arm i before time n</td></tr><tr><td>T<sub>n</sub>(i, j)</td><td>N</td><td>Counts of (B<sub>t</sub>, C<sub>t</sub>) = (i, j) before time n</td></tr><tr><td>T<sub>n</sub>(i)</td><td>N</td><td>Counts of i ∈ {B<sub>t</sub>, C<sub>t</sub>} before time n</td></tr><tr><td>N<sup>i</sup><sub>n,j</sub></td><td>N</td><td>Counts of (B<sub>t</sub>, C<sub>t</sub>, I<sub>t</sub>) = (i, j, j) before time n</td></tr><tr><td>β</td><td>(0, 1)</td><td>Fixed proportion</td></tr><tr><td>β<sub>n</sub>(i, j)</td><td>(0, 1)</td><td>IDS proportions</td></tr><tr><td>β<sub>n</sub>(i, j)</td><td>(0, 1)</td><td>Averaged IDS proportions</td></tr></tbody></table>

## C Characteristic Times

In Appendix C, we first recall properties satisfied by the (β-)characteristic times and (β-)optimal allocation for the BAI setting with Gaussian bandits. Then, we show how a ε-BAI problem can be reduced to a BAI one on a modified (and easier) instance.

**BAI setting** Let $\nu \in D^K$ with mean $\mu \in R^K$. The (β-)characteristic times for the fixed-confidence BAI setting with Gaussian bandits $N(\mu, 1)$ are defined as

$$T^*(\mu) = \min_{\beta \in (0,1)} T_{\beta}^*(\mu) \quad \text{with} \quad 2T_{\beta}^*(\mu)^{-1} = \max_{w \in \Delta_K, w_i^* = \beta} \min_{i^* \neq i} \frac{(\mu_{i^*} - \mu_i)^2}{1/\beta + 1/w_i}, \quad (7)$$

see [15, 34] for example. Let us denote by $w_{\beta}^*(\mu)$ and $w^*(\mu)$ their maximizer, which we will refer to as (β-)optimal allocations. Note that $(T^*(\mu), T_{\beta}^*(\mu)) = (T_0(\mu), T_{0,\beta}(\mu))$ and $(w^*(\mu), w_{\beta}^*(\mu)) = (w_0(\mu), w_{0,\beta}(\mu))$.

We recall in the following some fundamental results on those quantities (β-)characteristic times and (β-)optimal allocations. Lemma 6 proves that the (β-)optimal allocations are unique, have strictly positive elements, and shows a worst-case inequality $T_{1/2}^*(\mu) \le 2T^*(\mu)$. Lemma 6 also holds for any single-parameter exponential family of distributions and for the non-parametric family of bounded distributions [21].

**Lemma 6** ([15, 34, 21]). If $i^*(\mu)$ is a singleton and $\beta \in (0, 1)$, then $w^*(\mu)$ and $w_{\beta}^*(\mu)$ are singletons, i.e. the optimal allocations are unique, and $w^*(\mu)_i > 0$ and $w_{\beta}^*(\mu)_i > 0$ for all $i \in [K]$. Moreover, we have $T_{1/2}^*(\mu) \le 2T^*(\mu)$ and with $\beta^* = w_{i^*}^*(\mu)$. Additionally, we have $H(\mu) \le T^*(\mu) \le 2H(\mu)$ where $H(\mu) = 2 \sum_{i \in [K]} \Delta_i^{-2}$ where $\Delta_i^* = \Delta_{\min}$.

For Gaussian bandits, Lemma 7 shows that the (β-)characteristic times and (β-)optimal allocations can be obtained by solving a simpler optimization problem, which is amenable to faster implementation (e.g. Newton's iterates). It also provides upper and lower bound on the optimal allocation of the best arm, and gives hints that a tighter worst-case inequality $T_{1/2}^*(\mu) \le r_K T^*(\mu)$ might hold.

**Lemma 7** ([3, 20]). Assume that $i^*(\mu) = \{i^*\}$. Let $r(\mu)$ and $r_{\beta}(\mu)$ be the solution of $\psi_{\mu}(r) = 0$ and $\varphi_{\mu,\beta}(r) = 0$ with, for all $r \in (1/\min_{i \neq i^*}(\mu_{i^*} - \mu_i)^2, +\infty)$,

$$\psi_{\mu}(r) = \sum_{i \neq i^*} \frac{1}{(r(\mu_{i^*} - \mu_i)^2 - 1)^2} - 1 \quad \text{and} \quad \varphi_{\mu,\beta}(r) = \sum_{i \neq i^*} \frac{1}{r(\mu_{i^*} - \mu_i)^2 - 1} - \frac{1 - \beta}{\beta},$$
Then, $\psi_{\mu}$ and $\varphi_{\mu,\beta}$ are convex and decreasing. Moreover,

$$T^*(\mu) = \frac{2r(\mu)}{1 + \sum_{i \neq i^*} \frac{1}{r(\mu)(\mu_{i^*} - \mu_i)^2 - 1}} \quad \text{and} \quad T_{\beta}^*(\mu) = \frac{2r_{\beta}(\mu)}{\beta}.$$

Additionally, for all $i \neq i^*$, we have $\beta w_{\beta}^*(\mu)^{-1} = \beta T_{\beta}^*(\mu)(\mu_{i^*} - \mu_i)^2/2 - 1$. For $K = 2$, $w^*(\mu) = (0.5, 0.5)$ and $T^*(\mu) = T_{1/2}^*(\mu) = 8(\mu_1 - \mu_2)^2$. For $K \ge 3$, we have

$$1/(\sqrt{K-1}+1) \le w^*(\mu)_{i^*} \le 1/2.$$

Let $r_K = 2K/(1 + \sqrt{K-1})^2$, $j^* \in \arg \min_{j \neq i^*} \mu_{i^*} - \mu_j$ and $x \in \mathbb{R}^{K-2}$ such that $x_j = \frac{\mu_{i^*} - \mu_j}{\mu_{i^*} - \mu_{j^*}}$. Then, we have $T_{1/2}^*(\mu)/T^*(\mu) = \Omega(x)$ (i.e. independent of $\mu_{i^*}$ and $\mu_{i^*} - \mu_{j^*}$) and

$$\Omega(1_{K-2}) = r_K \quad \text{and} \quad \nabla_x \Omega(1_{K-2}) = 0_{K-2}.$$

**Lemma 8** gathers necessary conditions on the $(\beta)$-optimal allocations at the equilibrium such as equality of the transportation costs, and a link between the squared allocation which was refered to as overall balance in [40].

**Lemma 8** ([3, 40]). Assume that $i^*(\mu) = \{i^*\}$ and $\beta \in (0, 1)$. Then, for all $i \neq i^*$,

$$2T^*(\mu)^{-1} = \frac{(\mu_{i^*} - \mu_i)^2}{1/w^*(\mu)_{i^*} + 1/w^*(\mu)_i} \quad \text{and} \quad 2T_{\beta}^*(\mu)^{-1} = \frac{(\mu_{i^*} - \mu_i)^2}{1/\beta + 1/w_{\beta}^*(\mu)_i}.$$

Moreover, we have

$$w^*(\mu)_{i^*}^2 = \sum_{i \neq i^*} w^*(\mu)_i^2.$$

**Reduction of an $\varepsilon$-BAI problem to a BAI problem** Lemma 9 gives a reduction of a $\varepsilon$-BAI problem to a BAI one on a modified instance, which is easier. Thanks to Lemma 9, it is possible to leverage existing results on $T^*(\mu)$, $T_{\beta}^*(\mu)$, $w^*(\mu)$, $w_{\beta}^*(\mu)$ (such as Lemmas 6, 7 and 8) in order to study $T_{\varepsilon}(\mu)$, $T_{\varepsilon,\beta}(\mu)$, $T_{\varepsilon,\beta}(\mu, i)$, $w_{\varepsilon}(\mu)$, $w_{\varepsilon,\beta}(\mu)$ and $w_{\varepsilon,\beta}(\mu, i)$.

**Lemma 9.** Let $\mu \in \mathbb{R}^K$, $\varepsilon \ge 0$ and $\tilde{\varepsilon} \in [0, \varepsilon]$ and $\beta \in (0, 1)$. For all $i \in \mathcal{I}_{\tilde{\varepsilon}}(\mu)$, we define $\mu_{\tilde{\varepsilon}}(i)$ as $\mu_{\tilde{\varepsilon}}(i)_j = \mu_j - \varepsilon$ for all $j \neq i$ and $\mu_{\tilde{\varepsilon}}(i)_i = \mu_i$. Then, for all $i \in \mathcal{I}_{\tilde{\varepsilon}}(\mu)$, $T_{\varepsilon,\beta}(\mu, i) = T_{\beta}^*(\mu_{\tilde{\varepsilon}}(i))$ and $w_{\varepsilon,\beta}(\mu, i) = w_{\beta}^*(\mu_{\tilde{\varepsilon}}(i))$. Moreover, for all $i^* \in i^*(\mu)$,

$$T_{\varepsilon}(\mu) = T^*(\mu_{\tilde{\varepsilon}}(i^*)) \quad \text{and} \quad T_{\varepsilon,\beta}(\mu) = T_{\beta}^*(\mu_{\tilde{\varepsilon}}(i^*)) .$$

$$\text{Moreover, we have } w_{\varepsilon}(\mu) = \bigcup_{i^* \in i^*(\mu)} w^*(\mu_{\tilde{\varepsilon}}(i^*)) \text{ and } w_{\varepsilon,\beta}(\mu) = \bigcup_{i^* \in i^*(\mu)} w_{\beta}^*(\mu_{\tilde{\varepsilon}}(i^*)).$$

**Proof.** For $\varepsilon = 0$, the result is direct by definition. Let $\varepsilon > 0$ and $\tilde{\varepsilon} \in [0, \varepsilon]$. The first part is obtained by definition of $T_{\varepsilon,\beta}^*(\mu, i)$, $w_{\varepsilon,\beta}^*(\mu, i)$. Let $i^* \in i^*(\mu)$ and $\mu_{\tilde{\varepsilon}}(i^*)$ defined as above, hence $i^*(\mu_{\tilde{\varepsilon}}(i^*)) = \{i^*\}$. For all $i \in \mathcal{I}_{\tilde{\varepsilon}}(\mu) \setminus i^*(\mu)$, let us denote by $\lambda_{\tilde{\varepsilon}}^{(i^*,i)}$ the instance such that $\lambda_{\tilde{\varepsilon},i}^{(i^*,i)} = \mu_i$ and $\lambda_{\tilde{\varepsilon},j}^{(i^*,i)} = \mu_j - \varepsilon$ for all $j \neq i$. If $\mu_{i^*} - \mu_i = \varepsilon$ then $i^*(\lambda_{\tilde{\varepsilon}}^{(i^*,i)}) = \{i\} \cup i^*(\mu) \setminus \{i^*\}$, otherwise $i^*(\lambda_{\tilde{\varepsilon}}^{(i^*,i)}) = \{i\}$. We consider the permutation $\sigma$ that swaps arm $i$ with arm $i^*$. By symmetry, we have $T^*(\lambda_{\tilde{\varepsilon}}^{(i^*,i)}) = T^*(\sigma(\lambda_{\tilde{\varepsilon}}^{(i^*,i)}))$. Moreover, we have that the gaps of $\sigma(\lambda_{\tilde{\varepsilon}}^{(i^*,i)})$ are all strictly smaller than the gaps of $\mu_{\tilde{\varepsilon}}$ since $\varepsilon \ge \Delta_i > 0$. Therefore, Lemma 11 of Barrier et al (2022) yields that $T^*(\sigma(\lambda_{\tilde{\varepsilon}}^{(i^*,i)})) > T^*(\mu_{\tilde{\varepsilon}})$. We have proved that

$$\forall i^* \in i^*(\mu), \quad T^*(\mu_{\tilde{\varepsilon}}(i^*)) < \min_{i \in \mathcal{I}_{\tilde{\varepsilon}}(\mu) \setminus i^*(\mu)} T^*(\lambda_{\tilde{\varepsilon}}^{(i^*,i)}).$$

By symmetry $T^*(\mu_{\tilde{\varepsilon}}(i^*))$ is constant for all $i^* \in i^*(\mu)$, hence we have shown that

$$\forall i^* \in i^*(\mu), \quad T_{\varepsilon}(\mu) = T^*(\mu_{\tilde{\varepsilon}}(i^*)) .$$

It also shows that $w_{\varepsilon}(\mu) = \bigcup_{i^* \in i^*(\mu)} w^*(\mu_{\tilde{\varepsilon}}(i^*))$. The same reasoning yields the result for $T_{\varepsilon,\beta}(\mu)$ and $w_{\varepsilon,\beta}(\mu)$. $\square$
**ε-BAI problems cannot be arbitrarily difficult** Lemma 10 shows that, for all $i \in \mathcal{I}_{\varepsilon/2}(\mu)$, $T_{\varepsilon,1/2}(\mu, i)$ cannot be arbitrarily large and $\min_{j \neq i} w_{\varepsilon,0,1/2}(\mu, i)_j$ cannot be arbitrarily small. The proof relies on Lemma 9 and existing results for BAI.

**Lemma 10.** Let $\varepsilon > 0$ and $\mu \in \mathbb{R}^K$. Then, for all $i \in \mathcal{I}_{\varepsilon/2}(\mu)$, we have $T_{\varepsilon,1/2}(\mu, i) \le 32K/\varepsilon^2$ and $\min_{j \neq i} w_{\varepsilon,1/2}(\mu, i)_j \ge (16(K-2)+2)^{-1}$.

*Proof.* Let $i \in \mathcal{I}_{\varepsilon/2}(\mu)$, hence $\mu_i \ge \mu_* - \varepsilon/2$. Let $\mu_\varepsilon(i)$ as in Lemma 9 which satisfies that $i^*(\mu_\varepsilon(i)) = \{i\}$. Let $\Delta_{i,j} = \mu_i - \mu_j$ and $\Delta_{i,i} = \mu_i - \max_{j \neq i} \mu_j$. Then, we have

$$T_{\varepsilon,1/2}(\mu, i) = T_{1/2}^*(\mu_\varepsilon(i)) \le 2T^*(\mu_\varepsilon(i)) \le 8 \sum_{j \in [K]} (\Delta_{i,j} + \varepsilon)^{-2} \le 8 \sum_{j \in [K]} (\Delta_j + \varepsilon/2)^{-2},$$

where we used Lemma 6 for the two first inequality and $i \in \mathcal{I}_{\varepsilon/2}(\mu)$ for the last one. Since $\Delta_j \ge 0$, we conclude that $T_{\varepsilon,\beta}(\mu, i) \le 32K/\varepsilon^2$. Moreover, using Lemma 6, we have

$$T_{\varepsilon,1/2}(\mu, i) = T_{1/2}^*(\mu_\varepsilon(i)) \ge T^*(\mu_\varepsilon(i)) \ge 2 \sum_{j \in [K]} (\Delta_{i,j} + \varepsilon)^{-2}.$$

Likewise, using Lemma 9 and Lemma 7, we obtain that, for all $j \neq i$,

$$w_{\varepsilon,1/2}(\mu)_j^{-1/2} = w_{1/2}^*(\mu_\varepsilon(i))_j^{-1/2} = T_{1/2}^*(\mu_\varepsilon(i))(\mu_i - \mu_j + \varepsilon)^2/4 - 1 \\ \le 2 \sum_{k \notin \{i,j\}} \left( \frac{\mu_i - \mu_j + \varepsilon}{\mu_i - \mu_k + \varepsilon} \right)^2 + 1$$

where the last inequality uses what we proved above. When $\mu_k \le \mu_j$, the ratio is smaller than one. When $\mu_k > \mu_j$, we have $\mu_* \ge \mu_k > \mu_j \ge \mu_* - \varepsilon/2$, hence $\mu_k - \mu_j \le \varepsilon/2$ and

$$\frac{\mu_i - \mu_j + \varepsilon}{\mu_i - \mu_k + \varepsilon} \le 1 + \frac{\varepsilon/2}{\mu_* - \mu_k + \varepsilon/2} \le 2.$$

Therefore, we obtain $w_{\varepsilon,1/2}(\mu)_j^{-1/2} \le 8(K-2)+1$, which concludes the result. $\square$

Lemma 11 links the characteristic times for ε-BAI where $\varepsilon \in \{\varepsilon_0, \varepsilon_1\}$.

**Lemma 11.** Let $\mu \in \mathbb{R}^K$ such that $|i^*(\mu)| = 1$. Let $\varepsilon_0 > \varepsilon_1$. Then, for all $\beta \in (0,1)$, we have $T_{\varepsilon_0}(\mu)(\Delta_{\min}+\varepsilon_0)^2 \ge T_{\varepsilon_1}(\mu)(\Delta_{\min}+\varepsilon_1)^2$ and $T_{\varepsilon_0,\beta}(\mu)(\Delta_{\min}+\varepsilon_0)^2 \ge T_{\varepsilon_1,\beta}(\mu)(\Delta_{\min}+\varepsilon_1)^2$. Let $\varepsilon_0 < \varepsilon_1$. Then, $T_{\varepsilon_0}(\mu)(\Delta_{\max}+\varepsilon_0)^2 \ge T_{\varepsilon_1}(\mu)(\Delta_{\max}+\varepsilon_1)^2$ and $T_{\varepsilon_0,\beta}(\mu)(\Delta_{\max}+\varepsilon_0)^2 \ge T_{\varepsilon_1,\beta}(\mu)(\Delta_{\max}+\varepsilon_1)^2$.

*Proof.* Let $i^*(\mu) = \{i^*\}$. Let $\varepsilon_0 > \varepsilon_1$. Using Lemma 9, we have

$$2T_{\varepsilon}(\mu)^{-1}(\Delta_{\min} + \varepsilon)^{-2} = \max_{w \in \Delta_K} \min_{j \neq i^*} \frac{\tilde{\Delta}_j(\varepsilon)^2}{1/w_{i^*} + 1/w_j} \quad \text{with} \quad \tilde{\Delta}_j(\varepsilon) = \frac{\mu_* - \mu_j + \varepsilon}{\Delta_{\min} + \varepsilon}.$$

To conclude the first part of the first result, a sufficient condition is to show that $\tilde{\Delta}_j(\varepsilon_1) \ge \tilde{\Delta}_j(\varepsilon_0)$ for all $j \neq i^*$. Direct manipulations show that, for all $j \neq i^*$,

$$\tilde{\Delta}_j(\varepsilon_1) \ge \tilde{\Delta}_j(\varepsilon_0) \iff 1 - \frac{\varepsilon_0 - \varepsilon_1}{\mu_* - \mu_j + \varepsilon_0} \ge 1 - \frac{\varepsilon_0 - \varepsilon_1}{\Delta_{\min} + \varepsilon_0} \iff \mu_* - \mu_j \ge \Delta_{\min},$$

hence the result holds. The same proof can be used to obtain the second part of the first result.

Let $\varepsilon_0 < \varepsilon_1$. Using Lemma 9, we have

$$2T_{\varepsilon}(\mu)^{-1}(\Delta_{\max} + \varepsilon)^{-2} = \max_{w \in \Delta_K} \min_{j \neq i^*} \frac{\tilde{\Delta}_j(\varepsilon)^2}{1/w_{i^*} + 1/w_j} \quad \text{with} \quad \tilde{\Delta}_j(\varepsilon) = \frac{\mu_* - \mu_j + \varepsilon}{\Delta_{\max} + \varepsilon}.$$

To conclude the first part of the second result, a sufficient condition is to show that $\tilde{\Delta}_j(\varepsilon_1) \ge \tilde{\Delta}_j(\varepsilon_0)$ for all $j \neq i^*$. Direct manipulations show that, for all $j \neq i^*$,

$$\tilde{\Delta}_j(\varepsilon_1) \ge \tilde{\Delta}_j(\varepsilon_0) \iff 1 + \frac{\varepsilon_1 - \varepsilon_0}{\mu_* - \mu_j + \varepsilon_0} \ge 1 + \frac{\varepsilon_1 - \varepsilon_0}{\Delta_{\max} + \varepsilon_0} \iff \mu_* - \mu_j \le \Delta_{\max},$$

hence the result holds. The same proof can be used to obtain the second part of the second result. $\square$
## D Asymptotic analysis

Let $\varepsilon_0 > 0$, $\beta \in (0, 1)$ and $\delta \in (0, 1)$. In this section, we provide an asymptotic analysis of EB-TC$_{\varepsilon_0}$ slack $\varepsilon_0 > 0$ combined with the stopping rule (3) with parameters $(\varepsilon_0, \delta)$. First, we detail IDS proportions in Appendix D.1. Then, we sketch the proof for fixed proportions $\beta$ in Appendix D.2.

In the following, we consider a sub-Gaussian bandit with distribution $\nu \in D^K$ having mean parameter $\mu \in \mathbb{R}^K$ with a unique best arm, i.e. $i^*(\mu) = \{i^*\}$. We restate Theorem 1 below.

**Theorem 4 (Theorem 1).** Let $\varepsilon_0 > 0$, $\varepsilon_1 \ge 0$ and $\delta \in (0, 1)$. Using the threshold (4) in the stopping rule (3) with slack $\varepsilon_1$, the EB-TC$_{\varepsilon_0}$ algorithm is $(\varepsilon_1, \delta)$-PAC. For IDS proportions, it satisfies that, for all $\nu \in D^K$ such that $|i^*(\mu)| = 1$,

$$ \limsup_{\delta \to 0} \frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_1, \delta}]}{\log(1/\delta)} \le T_{\varepsilon_0}(\mu) \left( 1 + \max_{i \ne i^*} \frac{\varepsilon_0 - \varepsilon_1}{\mu_{i^*} - \mu_i + \varepsilon_1} \right)^2 . $$

Let $\beta \in (0, 1)$. For fixed proportions $\beta$, it satisfies that, for all $\nu \in D^K$ such that $|i^*(\mu)| = 1$,

$$ \limsup_{\delta \to 0} \frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_1, \delta}]}{\log(1/\delta)} \le T_{\varepsilon_0, \beta}(\mu) \left( 1 + \max_{i \ne i^*} \frac{\varepsilon_0 - \varepsilon_1}{\mu_{i^*} - \mu_i + \varepsilon_1} \right)^2 . $$

Theorem 1 provides asymptotic upper bound on the expected sample complexity of the EB-TC$_{\varepsilon_0}$ algorithm when combined with the stopping rule (3). When $\varepsilon_1 = \varepsilon_0$ and for Gaussian distributions, combining Lemma 1 and Theorem 1 shows that the EB-TC$_{\varepsilon_0}$ algorithm is asymptotically optimal for $\varepsilon_0$-BAI when using IDS proportions and asymptotically $\beta$-optimal for $\varepsilon_0$-BAI when using fixed proportions $\beta$. Until recently [40], proving asymptotic optimality of Top Two algorithms with adaptive choice $\beta$ was an open problem in the BAI literature. Our work extends their analysis to tackle the $\varepsilon$-BAI setting. Compared to previous work, we removed the assumption that sub-optimal arms should have distinct means.

Considering $\varepsilon_1 \ne \varepsilon_0$ can be interesting when the practitioner decides to tackle $\varepsilon$-BAI with an error $\varepsilon$ which is different from the slack $\varepsilon_0$ used by the EB-TC$_{\varepsilon_0}$ algorithm. Those situations occur when the practitioner is observing the data collected by the EB-TC$_{\varepsilon_0}$ algorithm without having control over it. Theorem 1 shows that the resulting sequential hypothesis testing has still asymptotic guarantees on the expected sample complexity. Quite naturally, those guarantees are not asymptotically optimal even for Gaussian distributions. The sub-optimality multiplicative gap of IDS proportions (that is, the ratio of the upper bound in Theorem 1 and the characteristic time for $\varepsilon_1$-BAI, $T_{\varepsilon_1}(\mu)$) is

$$ \frac{T_{\varepsilon_0}(\mu) (\Delta_{\min} + \varepsilon_0)^2}{T_{\varepsilon_1}(\mu) (\Delta_{\min} + \varepsilon_1)^2} \ge 1 \quad \text{when } \varepsilon_0 > \varepsilon_1, \text{ otherwise} \quad \frac{T_{\varepsilon_0}(\mu) (\Delta_{\max} + \varepsilon_0)^2}{T_{\varepsilon_1}(\mu) (\Delta_{\max} + \varepsilon_1)^2} \ge 1, $$

where the inequalities come from Lemma 11 and justify that there is no contradiction with the asymptotic lower bound on the expected sample complexity (Lemma 1). The same reasoning applies to fixed proportions $\beta$ by replacing $T_\varepsilon(\mu)$ by $T_{\varepsilon, \beta}(\mu)$.

**Concentration result** For both proofs, we use the following concentration result of the empirical mean for sub-Gaussian observations (Lemma 12). This is a standard tool for the asymptotic analysis of Top Two algorithms (e.g. Lemma 3 in [32], Lemma 5 in [36] or Lemma 14 in [21]), hence we omit the proof.

**Lemma 12.** There exists a sub-Gaussian random variable $W_\mu$ such that almost surely, for all $i \in [K]$ and all $n$ such that $N_{n,i} \ge 1$,

$$ |\mu_{n,i} - \mu_i| \le W_\mu \sqrt{\frac{\log(e + N_{n,i})}{N_{n,i}}}. $$

In particular, any random variable which is polynomial in $W_\mu$ has a finite expectation.

### D.1 IDS proportions

Using Lemma 9, the optimal allocation for $\varepsilon_0$-BAI are defined as

$$ w_{\varepsilon_0}(\mu) := \arg\max_{w \in \Delta_K} \min_{i \ne i^*} \frac{(\mu_{i^*} - \mu_i + \varepsilon_0)^2}{1/w_{i^*} + 1/w_i}. $$
Since $|i^*(\mu)| = 1$, let $\mu_{\varepsilon_0} = \mu_{\varepsilon_0}(i^*)$ where $\mu_\varepsilon(i^*)$ as in Lemma 9. Since we have $T_{\varepsilon_0}(\mu) = T^*(\mu_{\varepsilon_0})$ and $w_{\varepsilon_0}(\mu) = w^*(\mu_{\varepsilon_0})$, Lemma 6 and 8 yield that $w_{\varepsilon_0}(\mu) = \{w^*\}$ is a singleton with unique element denotes by $w^*$ which satisfies that $\min_{i \in [K]} w_i^* > 0$,

$$ \sum_{i \neq i^*} \left( \frac{w_i^*}{w_{i^*}^*} \right)^2 = 1, \qquad (8) $$

and

$$ \forall i \in [K] \setminus \{i^*\}, \quad \frac{(\mu_{i^*} - \mu_i + \varepsilon_0)^2}{1/w_{i^*}^* + 1/w_i^*} = 2T_{\varepsilon_0}(\mu)^{-1}. \qquad (9) $$

[40] refers to (8) as the overall balance equation. The key novelty of their analysis is to show that asymptotically the empirical proportions satisfy the same equation, referred to as the empirical overall balance, when using IDS proportions with sampling to choose among the leader and the challenger. The key novelty in our work lies in proving that the empirical overall balance equation is also satisfied when using IDS proportions with $K(K-1)$ tracking procedures to select between the leader and the challenger (see Appendix D.1.2).

**Convergence time** We follow an asymptotic analysis similar to the ones used in [32, 36, 21] with the improvement from [40]. Let $\gamma > 0$. Let us define the convergence time $T_{\varepsilon_0,\gamma}$, which is a random variable quantifies the number of samples required for the empirical allocations $(N_{n,i}/N_{n,i^*})_{i \neq i^*}$ to be $\gamma$-close to $(w_i^*/w_{i^*}^*)_{i \neq i^*}$:

$$ T_{\varepsilon_0,\gamma} := \inf \left\{ T \ge 1 \mid \forall n \ge T, \max_{i \neq i^*} \left| \frac{N_{n,i}}{N_{n,i^*}} - \frac{w_i^*}{w_{i^*}^*} \right| \le \gamma \right\}. \qquad (10) $$

Lemma 13 gives a sufficient condition to prove Theorem 1 for IDS proportions. The case $\varepsilon_0 = \varepsilon_1$ is a direct consequence of combining Theorem 13 and Proposition 14 in [40]. The proof is inspired by existing methods, e.g. Theorem 2 in [21] or Theorem 3 in [32].

**Lemma 13.** Let $\varepsilon_0 > 0$, $\varepsilon_1 \ge 0$ 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_{\varepsilon_0,\gamma}] < +\infty$. Using the threshold (4) in the stopping rule (3) with slack $\varepsilon_1$ 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_{\varepsilon_1, \delta}]}{\log(1/\delta)} \le T_{\varepsilon_0}(\mu) \left( 1 + \max_{i \neq i^*} \frac{\varepsilon_0 - \varepsilon_1}{\mu_{i^*} - \mu_i + \varepsilon_1} \right)^2 . $$

*Proof.* Let $\gamma > 0$. Let us define by

$$ \tilde{T}_{\gamma, \varepsilon_0} := \inf \left\{ T \ge 1 \mid \forall n \ge T, \left\| \frac{N_n}{n-1} - w^* \right\|_{\infty} \le \gamma \right\}. $$

Using that

$$ \sum_{i \neq i^*} \frac{w_i^*}{w_{i^*}^*} = \frac{1}{w_{i^*}^*} - 1 \quad \text{and} \quad \sum_{i \neq i^*} \frac{N_{n,i}}{N_{n,i^*}} = \frac{n-1}{N_{n,i^*}} - 1, $$

it is direct to see that for all $n \ge T_\gamma$

$$ \begin{aligned} \left| \frac{N_{n,i^*}}{n-1} - w_{i^*}^* \right| &= \left| \frac{n-1}{N_{n,i^*}} - \frac{1}{w_{i^*}^*} \right| \left| \frac{N_{n,i^*}}{n-1} w_{i^*}^* \right| \le \left| \frac{n-1}{N_{n,i^*}} - \frac{1}{w_{i^*}^*} \right| \le \gamma(K-1), \\ \left| \frac{N_{n,i}}{n-1} - w_{i}^* \right| &= w_{i^*}^* \left| \frac{N_{n,i}}{n-1} \left( \frac{1}{w_{i^*}^*} - \frac{n-1}{N_{n,i^*}} \right) + \frac{N_{n,i}}{N_{n,i^*}} - \frac{w_{i}^*}{w_{i^*}^*} \right| \\ &\le \left| \frac{1}{w_{i^*}^*} - \frac{n-1}{N_{n,i^*}} \right| + \left| \frac{N_{n,i}}{N_{n,i^*}} - \frac{w_{i}^*}{w_{i^*}^*} \right| \le \gamma K. \end{aligned} $$

Therefore, for all $\gamma \in (0, \gamma_1(\mu)/K]$, $\mathbb{E}_\nu[\tilde{T}_{\gamma, \varepsilon_0}] < +\infty$.

Let $\mu_{\varepsilon_0}$ as in Lemma 9. Since we have $T_{\varepsilon_0}(\mu) = T^*(\mu_{\varepsilon_0})$ and $w_{\varepsilon_0}(\mu) = w^*(\mu_{\varepsilon_0})$, we can leverage existing results from the BAI literature, e.g. Theorem 2 in [21] or Theorem 3 in [32]. The sole criterion on the stopping threshold is to be asymptotically tight (Definition 1).
**Definition 1.** A threshold $c: \mathbb{N} \times (0, 1] \to \mathbb{R}_+$ is said to be asymptotically tight if there exists $\alpha \in [0, 1)$, $\delta_0 \in (0, 1]$, functions $f, \bar{T}: (0, 1] \to \mathbb{R}_+$ and $C$ independent of $\delta$ satisfying: (1) for all $\delta \in (0, \delta_0]$ and $n \ge \bar{T}(\delta)$, then $c(n, \delta) \le f(\delta) + Cn^\alpha$, (2) $\limsup_{\delta \to 0} f(\delta)/\log(1/\delta) \le 1$ and (3) $\limsup_{\delta \to 0} \bar{T}(\delta)/\log(1/\delta) = 0$.

Since $C_G$ defined in (23) satisfies $C_G \approx x + \log(x)$, it is direct to see that

$$c(n, \delta) = 2C_G \left( \frac{1}{2} \log \left( \frac{K-1}{\delta} \right) \right) + 4 \log \left( 4 + \log \frac{n}{2} \right)$$

is asymptotically tight, e.g. by taking $(\alpha, \delta_0, C) = (1/2, 1, 4)$, $f(\delta) = 2C_G(\frac{1}{2} \log(\frac{K-1}{\delta}))$ and $\bar{T}(\delta) = 1$.

Based on continuity arguments and using that $\mathbb{E}_\nu[T_{\varepsilon_0, \gamma}] < +\infty$, the proof of Theorem 2 in [21] yields that

$$\limsup_{\delta \to 0} \frac{\mathbb{E}_\nu[\tau_\delta]}{\log(1/\delta)} \le \left( \min_{i \ne i^*} \frac{(\mu_{i^*} - \mu_i + \varepsilon_1)^2}{2(1/w_{i^*}^* + 1/w_i^*)} \right)^{-1} = T_{\varepsilon_0}(\mu) \max_{i \ne i^*} \left( \frac{\mu_{i^*} - \mu_i + \varepsilon_0}{\mu_{i^*} - \mu_i + \varepsilon_1} \right)^2,$$

where the equality uses the condition at the equilibrium (9). This concludes the proof. $\square$

Using Lemma 13, the proof of Theorem 1 for IDS proportions boils down to showing that $\mathbb{E}_\nu[T_{\varepsilon_0, \gamma}] < +\infty$. As in [32, 36, 21, 40], the proof is divided in several steps. First, we show that all the arms are sufficient explored for $n$ large enough (Appendix D.1.1). Second, we prove that the empirical overall balance equation approximately holds for $n$ large enough (Appendix D.1.2). Finally, we show convergence of the empirical ratio of proportions towards the ratio of optimal allocation, i.e. $\mathbb{E}_\nu[T_{\varepsilon_0, \gamma}] < +\infty$ (Appendix D.1.3).

### D.1.1 Sufficient exploration

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_n^L := \{i \in [K] \mid N_{n,i} \ge L\} \quad \text{and} \quad \mathcal{I}_n^* := \arg \max_{i \in S_n^L} \mu_i. \qquad (11)$$

In all generality $\mathcal{I}_n^*$ is a set, yet we obtain $\mathcal{I}_n^* = \{i^*\}$ as soon as $i^* \in S_n^L$. We define the highly and the mildly under-sampled sets

$$U_n^L := \{i \in [K] \mid N_{n,i} < \sqrt{L}\} \quad \text{and} \quad V_n^L := \{i \in [K] \mid N_{n,i} < L^{3/4}\}. \qquad (12)$$

[21] identifies the properties that the leader and the challenger should satisfy to ensure sufficient exploration. We improve on their analysis by removing the need for the distinct means assumption, and supporting IDS instead of a fixed allocation $\beta$.

Lemma 14 shows that the transportation cost is strictly positive and increases linearly. Compared to previous results, the key improvement lies in the fact that the lower bound holds for $(i, j) \in \mathcal{I}_n^* \times S_n^L$ instead of $(i, j) \in \mathcal{I}_n^* \times (S_n^L \setminus \mathcal{I}_n^*)$. This is due to the $\varepsilon_0$ regularization, which removes the need to assume that the means are distinct.

**Lemma 14.** 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} - \mu_{n,j} + \varepsilon_0}{\sqrt{1/N_{n,i} + 1/N_{n,j}}} \ge \sqrt{L} \frac{\varepsilon_0}{2\sqrt{2}}.$$

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

$$\mu_{n,i} - \mu_{n,j} \ge \mu_i - \mu_j - W_\mu \left( \sqrt{\frac{\log(e + N_{n,i})}{N_{n,i}}} + \sqrt{\frac{\log(e + N_{n,j})}{N_{n,j}}} \right) \\ \ge -2W_\mu \sqrt{\frac{\log(e + L)}{L}} \ge -\frac{\varepsilon_0}{2},$$
where the last inequality is obtained for $L \ge L_0 = L_1 - e$ which is defined as

$$L_1 = \sup \{x \mid x < 16W_{\mu}^2 \log(x)/\varepsilon_0^2 + e\} \le h_1 (16W_{\mu}/\varepsilon_0^2, e).$$

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} - \mu_{n,j} + \varepsilon_0}{\sqrt{1/N_{n,i} + 1/N_{n,j}}} \ge \frac{\varepsilon_0/2}{\sqrt{1/N_{n,i} + 1/N_{n,j}}} \ge \sqrt{L} \frac{\varepsilon_0}{2\sqrt{2}}.$$

□

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

**Lemma 15.** 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} - \mu_{n,j} + \varepsilon_0}{\sqrt{1/N_{n,i} + 1/N_{n,j}}} \le \sqrt{L}(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} - \mu_{n,j} + \varepsilon_0}{\sqrt{1/N_{n,i} + 1/N_{n,j}}} &\le \sqrt{N_{n,j}} |\mu_{n,i} - \mu_{n,j} + \varepsilon_0| \\
&\le \sqrt{L} \left( |\mu_i - \mu_j + \varepsilon_0| + W_{\mu} \left( \sqrt{\frac{\log(e + N_{n,i})}{N_{n,i}}} + \sqrt{\frac{\log(e + N_{n,j})}{N_{n,j}}} \right) \right) \\
&\le \sqrt{L} \left( |\mu_i - \mu_j + \varepsilon_0| + 2W_{\mu} \sqrt{\log(e + 1)} \right) \\
&\le \sqrt{L}(D_1 + 4W_{\mu}),
\end{aligned}$$

for $D_1 = \max_{i \ne j} |\mu_i - \mu_j + \varepsilon_0|$.

□

Lemma 16 shows the desired property for the EB leader. Since it corresponds to Lemma 17 in [21], we omit the proof.

**Lemma 16 (Lemma 17 in [21]).** There exists $L_2$ with $\mathbb{E}_{\nu}[(L_2)^{\alpha}] < +\infty$ for all $\alpha > 0$ such that if $L \ge L_2$, for all $n$ (at most polynomial in $L$) such that $S_n^L \ne \emptyset$, $B_n^{EB} \in S_n^L$ implies $B_n^{EB} \in \mathcal{I}_n^*$.

Lemma 17 shows that the desired property for the TC challenger. Compared to existing result, we improve by remove the assumption that all arms have distinct means thanks to the regularization $\varepsilon_0 > 0$.

**Lemma 17.** There exists $L_3$ 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 \ne \emptyset$, $B_n^{EB} \notin V_n^L$ implies $C_n^{TC\varepsilon_0} \in V_n^L$.

*Proof.* In the following, we consider $U_n^L \ne \emptyset$ (hence $V_n^L \ne \emptyset$) and $B_n^{EB} \notin V_n^L$. Let $\mathcal{J}_n^* = \arg \max_{i \in \overline{V_n^L}} \mu_i$ and $L_2$ as in Lemma 16. Then, for $L \ge L_2^{4/3}$, we have $B_n^{EB} \in \mathcal{J}_n^*$.

Let $L_0$ and $(L_1, D_1)$ as in Lemmas 14 and 15. Then, for all $L \ge \max\{L_0^{4/3}, L_2^{4/3}, L_1^2\}$,

$$\begin{aligned}
& B_n^{EB} \in \mathcal{J}_n^*, \\
\forall (i, j) \in \mathcal{J}_n^* \times \overline{V_n^L}, \text{ s.t. } i \ne j, & \frac{\mu_{n,i} - \mu_{n,j} + \varepsilon_0}{\sqrt{1/N_{n,i} + 1/N_{n,j}}} \ge L^{3/8} \frac{\varepsilon_0}{2\sqrt{2}}, \\
\forall (i, j) \in \overline{U_n^L} \times U_n^L, & \frac{\mu_{n,i} - \mu_{n,j} + \varepsilon_0}{\sqrt{1/N_{n,i} + 1/N_{n,j}}} \le L^{1/4} (D_1 + 4W_{\mu}).
\end{aligned}$$
Since $\mathcal{J}_n^* \subseteq \overline{V}_n^L \subseteq \overline{U}_n^L$, for all $L \ge L_3 := \max\{L_0^{4/3}, L_2^{4/3}, L_1^2, \left(\frac{2\sqrt{2}}{\epsilon_0}(D_1 + 4W_\mu)\right)^8 + 1\}$ we have
$$ \forall (i, k, j) \in \mathcal{J}_n^* \times U_n^L \times \overline{V}_n^L, \text{ s.t. } i \neq j, \quad \frac{\mu_{n,i} - \mu_{n,j} + \epsilon_0}{\sqrt{1/N_{n,i} + 1/N_{n,j}}} > \frac{\mu_{n,i} - \mu_{n,k} + \epsilon_0}{\sqrt{1/N_{n,i} + 1/N_{n,k}}}. $$

As $B_n^{EB} \in \mathcal{J}_n^*$, the definition $C_n^{TC\epsilon_0}$ yields that $C_n^{TC\epsilon_0} \in V_n^L$. Otherwise the above strict inequality would yield a contradiction. Using Lemma 12, we show

$$ \mathbb{E}_{\mathbf{F}}[L_3] \le \mathbb{E}_{\mathbf{F}} \left[ \left( \frac{2\sqrt{2}}{\epsilon_0} (D_1 + 4W_\mu) \right)^8 + 1 \right] + \mathbb{E}_{\mathbf{F}}[(L_0)^{4/3}] + \mathbb{E}_{\mathbf{F}}[(L_2)^{4/3}] + \mathbb{E}_{\mathbf{F}}[(L_1)^2] < +\infty, $$
hence this concludes the proof. $\square$

Lemma 18 shows that all arms are sufficiently explored and that the leader is the unique best arm for $n$ large enough.

**Lemma 18.** 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^*.$

*Proof.* Let $L_2$ and $L_3$ as in Lemmas 16 and 17. Therefore, for $L \ge L_4 := \max\{L_3, L_2^{4/3}\}$, for all $n$ such that $U_n^L \ne \emptyset$, $B_n^{EB} \in V_n^L$ or $C_n^{TC\epsilon_0} \in V_n^L$. We have $\mathbb{E}_\nu[L_4] < +\infty$. There exists a deterministic $L_5$ such that for all $L \ge L_5$, $\lfloor L \rfloor \ge KL^{3/4}$. Let $L \ge \max\{L_5, L_4\}$.

Suppose towards contradiction that $U_{\lfloor KL \rfloor}^L$ is not empty. Then, for any $1 \le t \le \lfloor KL \rfloor$, $U_t^L$ and $V_t^L$ are non empty as well. Using the pigeonhole principle, there exists some $i \in [K]$ such that $N_{\lfloor L \rfloor, i} \ge L^{3/4}$. Thus, we have $\lfloor V_{\lfloor L \rfloor}^L \rfloor \le K - 1$. Our goal is to show that $\lfloor V_{\lfloor 2L \rfloor}^L \rfloor \le K - 2$. A sufficient condition is that one arm in $V_{\lfloor L \rfloor}^L$ is pulled at least $L^{3/4}$ times between $\lfloor L \rfloor$ and $\lfloor 2L \rfloor - 1$.

If we have

$$ \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} 1 (\{B_t^{EB}, C_t^{TC\epsilon_0}\} \subseteq V_t^L) \ge KL^{3/4}, $$

then, using that $V_t^L \subseteq V_{\lfloor L \rfloor}^L$, we obtain

$$ \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} 1 (I_t \in V_{\lfloor L \rfloor}^L) \ge \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} 1 (I_t \in V_t^L) \ge \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} 1 (\{B_t^{EB}, C_t^{TC\epsilon_0}\} \subseteq V_t^L) \ge KL^{3/4}, $$

Therefore, there exists $i \in V_{\lfloor L \rfloor}^L$ which is sampled $L^{3/4}$ times between $\lfloor L \rfloor$ and $\lfloor 2L \rfloor - 1$.

In the following, we assume that

$$ \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} 1 (\{B_t^{EB}, C_t^{TC\epsilon_0}\} \subseteq V_t^L) < KL^{3/4}, $$

Since $B_t^{EB} \in V_t^L$ or $C_t^{TC\epsilon_0} \in V_t^L$, we have

$$ \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} \left( 1 (B_t^{EB} \in V_t^L, C_t^{TC\epsilon_0} \notin V_t^L) + 1 (B_t^{EB} \notin V_t^L, C_t^{TC\epsilon_0} \in V_t^L) \right) > \lfloor 2L \rfloor - \lfloor L \rfloor - KL^{3/4}. $$

Therefore, we have

Case 1: $\sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} 1 (B_t^{EB} \in V_t^L, C_t^{TC\epsilon_0} \notin V_t^L) > (\lfloor 2L \rfloor - \lfloor L \rfloor - KL^{3/4})/2,$

or Case 2: $\sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} 1 (B_t^{EB} \notin V_t^L, C_t^{TC\epsilon_0} \in V_t^L) > (\lfloor 2L \rfloor - \lfloor L \rfloor - KL^{3/4})/2.$
Since $\beta_t(i, j) = N_{t,j}/(N_{t,j} + N_{t,i})$, we obtain

$$1/2 \le \begin{cases} \beta_t(B_t^{\text{EB}}, C_t^{\text{TC}\epsilon_0}) & \text{if } B_t^{\text{EB}} \in V_t^L, C_t^{\text{TC}\epsilon_0} \notin V_t^L \\ 1 - \beta_t(B_t^{\text{EB}}, C_t^{\text{TC}\epsilon_0}) & \text{if } B_t^{\text{EB}} \notin V_t^L, C_t^{\text{TC}\epsilon_0} \in V_t^L \end{cases}.$$

This lower bound will be crucial to argue that the challenger is sampled enough in case 2 and the leader is sampled enough in case 1.

**Case 1.** Using Lemma 46 and the above, we obtain

$$\begin{aligned} \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} \mathbb{1}(I_t \in V_{\lfloor L \rfloor}^L) &\ge \sum_{i \in V_{\lfloor L \rfloor}^L} \sum_{j \ne i} \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} \mathbb{1}(I_t = i, (B_t^{\text{EB}}, C_t^{\text{TC}\epsilon_0}) = (i, j)) \\ &\ge \sum_{i \in V_{\lfloor L \rfloor}^L} \sum_{j \ne i} \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} \beta_t(i, j) \mathbb{1}((B_t^{\text{EB}}, C_t^{\text{TC}\epsilon_0}) = (i, j)) - K^2 \\ &\ge \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} \beta_t(B_t^{\text{EB}}, C_t^{\text{TC}\epsilon_0}) \mathbb{1}(B_t^{\text{EB}} \in V_t^L, C_t^{\text{TC}\epsilon_0} \notin V_t^L) - K^2 \\ &\ge (\lfloor 2L \rfloor - \lfloor L \rfloor - KL^{3/4})/4 - K^2 \ge KL^{3/4}, \end{aligned}$$

where the last inequality is obtained for $L \ge L_6 + 1$ with

$$L_6 = \sup \left\{ L \in \mathbb{N} \mid \left( \lfloor 2L \rfloor - \lfloor L \rfloor - KL^{3/4} \right) / 4 - K^2 < KL^{3/4} \right\}.$$

Therefore, there exists $i \in V_{\lfloor L \rfloor}^L$ which is sampled $L^{3/4}$ times between $\lfloor L \rfloor$ and $\lfloor 2L \rfloor - 1$.

**Case 2.** Using Lemma 46 and the above, we obtain

$$\begin{aligned} \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} \mathbb{1}(I_t \in V_{\lfloor L \rfloor}^L) &\ge \sum_{j \in V_{\lfloor L \rfloor}^L} \sum_{i \ne j} \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} \mathbb{1}(I_t = j, (B_t^{\text{EB}}, C_t^{\text{TC}\epsilon_0}) = (i, j)) \\ &\ge \sum_{j \in V_{\lfloor L \rfloor}^L} \sum_{i \ne j} \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} (1 - \beta_t(i, j)) \mathbb{1}((B_t^{\text{EB}}, C_t^{\text{TC}\epsilon_0}) = (i, j)) - K^2 \\ &\ge \sum_{t=\lfloor L \rfloor}^{\lfloor 2L \rfloor-1} (1 - \beta_t(B_t^{\text{EB}}, C_t^{\text{TC}\epsilon_0})) \mathbb{1}(B_t^{\text{EB}} \notin V_t^L, C_t^{\text{TC}\epsilon_0} \in V_t^L) - K^2 \\ &\ge (\lfloor 2L \rfloor - \lfloor L \rfloor - KL^{3/4})/4 - K^2 \ge KL^{3/4}, \end{aligned}$$

where the last inequality is obtained for $L \ge L_6 + 1$. Therefore, there exists $i \in V_{\lfloor L \rfloor}^L$ which is sampled $L^{3/4}$ times between $\lfloor L \rfloor$ and $\lfloor 2L \rfloor - 1$.

**Summary.** We have shown $|V_{\lfloor 2L \rfloor}^L| \le K - 2$. By induction, for any $1 \le k \le K$, we have $|V_{\lfloor kL \rfloor}^L| \le K - k$, and finally $U_{\lfloor KL \rfloor}^L = \emptyset$ for all $L \ge L_7 := \max\{L_5, L_4, L_6 + 1\}$. Defining $N_0 = KL_7$, we have $\mathbb{E}_{\nu}[N_0] < +\infty$. For all $n \ge N_0$, we let $L = n/K$, hence we have $U_n^{n/K} = U_{\lfloor KL \rfloor}^L = \emptyset$. This concludes the proof of sufficient exploration.

**Leader is best arm.** Using Lemma 12, we obtain that for all $n \ge N_0$,

$$\begin{aligned} \forall i \ne i^*, \quad \mu_{n,i} &\le \mu_i + W_\mu \sqrt{\frac{\log(e + N_{n,i})}{N_{n,i}}} \le \mu_i + W_\mu \sqrt{\frac{\log(e + \sqrt{n/K})}{\sqrt{n/K}}}, \\ \mu_{n,i^*} &\le \mu_{i^*} - W_\mu \sqrt{\frac{\log(e + N_{n,i^*})}{N_{n,i^*}}} \le \mu_{i^*} - W_\mu \sqrt{\frac{\log(e + \sqrt{n/K})}{\sqrt{n/K}}}. \end{aligned}$$
Therefore, we have $B_n^{\text{EB}} = i^*$ for all $n \ge N_1 := \max\{N_0, K(X_0 - e)^2 + 1\}$ where

$$X_0 = \sup \left\{ x > 1 \mid x < \frac{16W_{\mu}^2}{\min_{i \neq i^*} (\mu_{i^*} - \mu_i)^2} \log(x) + e \right\} \le h_1 \left( \frac{16W_{\mu}^2}{\min_{i \neq i^*} (\mu_{i^*} - \mu_i)^2}, e \right),$$

where the last inequality is obtained by using Lemma 51 with $h_1$ defined therein. Since $h_1(x, e) \sim_{x \to +\infty} x \log x$, we have

$$\mathbb{E}_{\nu}[N_1] < \mathbb{E}_{\nu}[N_0] + \mathbb{E}_{\nu}[K(X_0 - e)^2 + 1] < +\infty.$$

This concludes the proof. □

### D.1.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 19 is that we use IDS proportions with $K(K-1)$ tracking procedures to select between the leader and the challenger instead of sampling.

**Lemma 19.** 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{N_{n,i}}{n-1} \right)^2 \right| \le \gamma.$$

*Proof.* Let $N_1$ as in Lemma 18. Then, we have for all $n > N_1$

$$\frac{N_{n,i^*}}{n-1} = \frac{N_{n,i^*}}{n-1} + \frac{\sum_{i \neq i^*} N_{N_1,i^*}}{n-1}, \quad \frac{N_{n,i}}{n-1} = \frac{N_{n,i^*}}{n-1} + \frac{\sum_{j \neq i^*} N_{N_1,i^*}}{n-1}, \\ (1 - \bar{\beta}_n(i^*, j)) \frac{T_n(i^*, j)}{n-1} = \frac{1}{n-1} \sum_{t=N_1}^{n-1} 1(C_t = j) (1 - \beta_t(i^*, j)) + (1 - \bar{\beta}_{N_1}(i^*, j)) \frac{T_{N_1}(i^*, j)}{n-1}, \\ \sum_{j \neq i^*} \bar{\beta}_n(i^*, j) \frac{T_n(i^*, j)}{n-1} = \frac{1}{n-1} \sum_{t=N_1}^{n-1} \beta_t(i^*, C_t) + \sum_{j \neq i^*} \bar{\beta}_{N_1}(i^*, j) \frac{T_{N_1}(i^*, j)}{n-1}$$

Chaining the inequalities with Lemma 46, we obtain that

$$-\frac{K}{n-1} \le \frac{N_{n,i^*}}{n-1} - \frac{1}{n-1} \sum_{t=N_1}^{n-1} \beta_t(i^*, C_t) \le \frac{2N_1 + K}{n-1}, \\ -\frac{1}{n-1} \le \frac{N_{n,i}}{n-1} - \frac{1}{n-1} \sum_{t=N_1}^{n-1} 1(C_t = j) (1 - \beta_t(i^*, j)) \le \frac{2N_1 + 1}{n-1}.$$

Using that $a^2 - b^2 = (a-b)(a+b) \le 2(a-b)$ for $(a,b) \in (0,1)^2$, we obtain

$$-2 \frac{K}{n-1} \le \left( \frac{N_{n,i^*}}{n-1} \right)^2 - \left( \frac{1}{n-1} \sum_{t=N_1}^{n-1} \beta_t(i^*, C_t) \right)^2 \le 2 \frac{2N_1 + K}{n-1}, \\ -2 \frac{1}{n-1} \le \left( \frac{N_{n,i}}{n-1} \right)^2 - \left( \frac{1}{n-1} \sum_{t=N_1}^{n-1} 1(C_t = j) (1 - \beta_t(i^*, j)) \right)^2 \le 2 \frac{2N_1 + 1}{n-1}.$$

For all $n > N_1$, let us denote by

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

Therefore, we have

$$-4K \frac{N_1 + 1}{n - 1} \le \left( \frac{N_{n,i^*}}{n-1} \right)^2 - \sum_{i \neq i^*} \left( \frac{N_{n,i}}{n-1} \right)^2 - \frac{G_n}{(n-1)^2} \le 4 \frac{N_1 + K}{n-1}.$$
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) - (1 - \beta_n(i^*, C_n)) \sum_{t=N_1}^{n-1} 1(C_t = C_n)(1 - \beta_t(i^*, C_n)) \\ + \beta_n(i^*, C_n) - 1/2. $$

Therefore, we obtain by using the above inequalities that

$$ \frac{1}{2}(G_{n+1} - G_n) \le \beta_n(i^*, C_n)N_{n,i^*} - (1 - \beta_n(i^*, C_n))N_{n,C_n} + 2N_1 + K + 3/2 \\ = 2N_1 + K + 3/2, $$

$$ \frac{1}{2}(G_{n+1} - G_n) \ge \beta_n(i^*, C_n)N_{n,i^*} - (1 - \beta_n(i^*, C_n))N_{n,C_n} - 2N_1 - K - 3/2 \\ = -2N_1 - K - 3/2, $$

where we used that $\beta_n(i^*, C_n)N_{n,i^*} = (1 - \beta_n(i^*, C_n))N_{n,C_n}$ since $\beta_n(i^*, C_n) = \frac{N_{n,C_n}}{N_{n,i^*}+N_{n,C_n}}$.

Summing those inequalities, we obtain

$$ G_n = \sum_{t=N_1+1}^{n-1} (G_{t+1} - G_t) + G_{N_1+1} \le (4N_1 + 2K + 3)(n-1-N_1) + 1 \\ \ge -(4N_1 + 2K + 3)(n-1-N_1) - 1, $$

where we used that $G_{N_1+1} = 2\beta_{N_1}(i^*, C_{N_1}) - 1 \in [-1, 1]$. Combining everything together, we have shown that

$$ \left(\frac{N_{n,i^*}}{n-1}\right)^2 - \sum_{i \neq i^*} \left(\frac{N_{n,i}}{n-1}\right)^2 \le 4 \frac{N_1 + K}{n-1} + \frac{(4N_1 + 2K + 3)(n-1-N_1) + 1}{(n-1)^2} \\ \ge -4K \frac{N_1 + 1}{n-1} - \frac{(4N_1 + 2K + 3)(n-1-N_1) + 1}{(n-1)^2}. $$

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

$$ N_2 = \inf \left\{ n > 2 \mid 4K \frac{N_1 + 1}{n-1} + \frac{(4N_1 + 2K + 3)(n-1-N_1) + 1}{(n-1)^2} \le \gamma \right\}, $$

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

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

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

$$ \frac{1}{4\sqrt{2(K-1)}} \le \frac{N_{n,i^*}}{n-1} \le \frac{3}{4}. $$

*Proof.* Let $N_2$ as in Lemma 19 for $\gamma = 1/2$. Using Lemma 19, we obtain $\frac{N_{n,i^*}}{n-1} \le \frac{3}{4}$ since

$$ 1/2 \ge \left(\frac{N_{n,i^*}}{n-1}\right)^2 - \sum_{i \neq i^*} \left(\frac{N_{n,i}}{n-1}\right)^2 \ge \left(\frac{N_{n,i^*}}{n-1}\right)^2 - \left(1 - \frac{N_{n,i^*}}{n-1}\right)^2 = 2\frac{N_{n,i^*}}{n-1} - 1. $$

Let $\tilde{N}_2$ as in Lemma 19 for $\gamma = \frac{1}{32(K-1)}$. Similarly by using Lemma 19, we obtain $\frac{N_{n,i^*}}{n-1} \ge \frac{1}{4\sqrt{2(K-1)}}$ since

$$ \left(\frac{N_{n,i^*}}{n-1}\right)^2 \ge -\frac{1}{32(K-1)} + \sum_{i \neq i^*} \left(\frac{N_{n,i}}{n-1}\right)^2 \ge -\frac{1}{32(K-1)} + \frac{1}{K-1}\left(1 - \frac{N_{n,i^*}}{n-1}\right)^2 \\ \ge \frac{1}{32(K-1)}. $$

Taking $N_3 = \max\{N_2, \tilde{N}_2\}$ yields the result. $\square$
Lemma 21 is a rescaled version of the empirical overall balance equation which is proven by simply combining Lemma 19 and Lemma 20.

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

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

*Proof.* Let $N_2$ as in Lemma 19 for $\frac{\gamma}{32(K-1)}$. Let $N_3$ as in Lemma 20. Direct manipulation shows that, for all $n \ge N_4 = \max\{N_2, N_3\}$,

$$ \left| 1 - \sum_{i \neq i^*} \left( \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{N_{n,i}}{n-1} \right)^2 \right| \le 32(K-1) \frac{\gamma}{32(K-1)} = \gamma. $$

This concludes the result.

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

### D.1.3 Convergence towards optimal ratio of 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 22).

**Lemma 22.** 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^{TC\epsilon_0} \neq 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. $$

Suppose towards contradiction that

$$ \forall j \neq i^*, \quad \frac{N_{n,j}}{N_{n,i^*}} > \frac{w_j^*}{w_{i^*}^*}. $$

Let $\tilde{\gamma} > 0$. Let $N_4$ as in Lemma 21 for $\tilde{\gamma}$. then using Lemma 21 and 8 yields that, for all $n \ge N_4$,

$$ \tilde{\gamma} \ge \sum_{j \neq i^*} \left( \frac{N_{n,j}}{N_{n,i^*}} \right)^2 - 1 \ge \left( \frac{w_i^*}{w_{i^*}^*} + \gamma \right)^2 - \left( \frac{w_i^*}{w_{i^*}^*} \right)^2 = \gamma \left( \gamma + 2 \frac{w_i^*}{w_{i^*}^*} \right). $$

Therefore, we have a contradiction if we take $\tilde{\gamma}$ small enough (e.g. $\tilde{\gamma} < \gamma^2$), hence we have shown that, for all $n \ge N_4$,

$$ \frac{N_{n,i}}{N_{n,i^*}} \ge \frac{w_i^*}{w_{i^*}^*} + \gamma \quad \Rightarrow \quad \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^{EB} = i^*$ for all $n \ge N_1$ and the definition of $C_n^{TC\epsilon_0}$, we know that

$$ \frac{\mu_{n,i^*} - \mu_{n,i} + \epsilon_0}{\sqrt{1/N_{n,i^*} + 1/N_{n,i}}} > \frac{\mu_{n,i^*} - \mu_{n,j} + \epsilon_0}{\sqrt{1/N_{n,i^*} + 1/N_{n,j}}} \quad \Rightarrow \quad C_n^{TC\epsilon_0} \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^*} - \mu_{n,i} + \epsilon_0}{\mu_{n,i^*} - \mu_{n,j} + \epsilon_0} \sqrt{\frac{1 + N_{n,i^*}/N_{n,j}}{1 + N_{n,i^*}/N_{n,i}}} \ge \frac{\mu_{n,i^*} - \mu_{n,i} + \epsilon_0}{\mu_{n,i^*} - \mu_{n,j} + \epsilon_0} \sqrt{\frac{1 + w_{i^*}^*/w_j^*}{1 + (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 \ne i^*$,

$$ \left| \frac{\mu_{n,i^*} - \mu_{n,k} + \epsilon_0}{\mu_{i^*} - \mu_k + \epsilon_0} - 1 \right| \le \frac{W_\mu}{\mu_{i^*} - \mu_k + \epsilon_0} \left( \sqrt{\frac{\log(e + N_{n,k})}{N_{n,k}}} + \sqrt{\frac{\log(e + N_{n,i^*})}{N_{n,i^*}}} \right) \\ \le \frac{2W_\mu}{\min_{k \ne i^*} (\mu_{i^*} - \mu_k + \epsilon_0)} \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 x < \frac{4W_{\mu}^2}{\tilde{\gamma}^2 \min_{k \ne i^*} (\mu_{i^*} - \mu_k + \epsilon_0)^2} \log x + e \right\} \\ \le h_1 \left( \frac{4W_{\mu}^2}{\tilde{\gamma}^2 \min_{k \ne i^*} (\mu_{i^*} - \mu_k + \epsilon_0)^2}, e \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\}$,

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

where the equality uses that the transportation costs are equal at the equilibrium, i.e. (9). 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^*} - \mu_{n,i} + \epsilon_0}{\mu_{n,i^*} - \mu_{n,j} + \epsilon_0} \sqrt{\frac{1 + N_{n,i^*}/N_{n,j}}{1 + N_{n,i^*}/N_{n,i}}} > 1 \quad \implies \quad C_n^{\text{TC}\epsilon_0} \ne i. $$

This concludes the proof. $\square$

Lemma 23 shows no sub-optimal arm is overshooting the ratio of its optimal allocation for $n$ large enough.

**Lemma 23.** 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. $$

*Proof.* Let $\gamma > 0$. Let $N_1$ as in Lemma 18. Let $N_3$ and $N_5$ as in Lemmas 20 and 22. Let $M \ge \max\{N_3, N_5, N_1\}$ and $n > M$. Let $t_{n,i}(\gamma) = \max\{M, \max\{t \in \{M, \dots, n-1\} \mid \frac{N_{t,i}}{N_{t,i^*}} < \frac{w_i^*}{w_{i^*}^*} + \gamma/2\}\}$ for all $i \ne i^*$. In particular, using Lemma 22, for all $n > M$

$$ \forall t > t_{n,i}(\gamma), \quad \frac{N_{t,i}}{N_{t,i^*}} \ge \frac{w_i^*}{w_{i^*}^*} + \gamma/2 \quad \text{hence} \quad i \ne C_t^{\text{TC}\epsilon_0}, $$

and

$$ N_{t_{n,i}(\gamma),i} \le \max \left\{ M, \left( \frac{w_i^*}{w_{i^*}^*} + \gamma/2 \right) N_{t_{n,i}(\gamma),i^*} \right\} $$

Then, we have for all $n \ge M$,

$$ N_{n,i} = N_{t_{n,i}(\gamma),i} + 1 \left( i = I_{t_{n,i}(\gamma)} \right) + \sum_{t=t_{n,i}(\gamma)+1}^{n-1} 1 \left( i = I_t = C_t^{\text{TC}\epsilon_0} \right) \\ \le \max \left\{ M, \left( \frac{w_i^*}{w_{i^*}^*} + \gamma/2 \right) N_{t_{n,i}(\gamma),i^*} \right\} + 1. $$
Using that $N_{t_{n,i}(\gamma),i^*} \le N_{n,i^*}$, $N_{n,i^*} \ge \frac{n-1}{4\sqrt{2(K-1)}}$ (Lemma 20) and $\max\{a,b\} \le a+b$, we obtain that

$$ \frac{N_{n,i}}{N_{n,i^*}} \le \frac{4(M+1)\sqrt{2(K-1)}}{n-1} + \frac{w_i^*}{w_{i^*}^*} + \gamma/2 \le \frac{w_i^*}{w_{i^*}^*} + \gamma, $$

where the last inequality holds for $n \ge N_7 = 8(M+1)\sqrt{2(K-1)}/\gamma + 1$. Taking $N_6 = \max\{N_3, N_5, N_1, N_7\}$ yields the result since $\mathbb{E}_{\nu}[N_6] < +\infty$. $\square$

Finally, Lemma 24 shows that the sufficient condition (see Lemma 13) to obtain the asymptotic upper bound on the expected sample complexity is satisfied.

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

*Proof.* Let $\gamma > 0$ and $\tilde{\gamma}$. Let $N_4$ and $N_6$ as in Lemmas 21 and 23 for $\tilde{\gamma}$. Then, using Lemmas 21 and 23, we have for all $n \ge \max\{N_4, N_6\}$,

$$ \left(\frac{N_{n,i}}{N_{n,i^*}}\right)^2 \ge 1 - \sum_{j \notin \{i,i^*\}} \left(\frac{N_{n,j}}{N_{n,i^*}}\right)^2 - \tilde{\gamma} \\ \ge 1 - \sum_{j \notin \{i,i^*\}} \left(\frac{w_j^*}{w_{i^*}^*} + \tilde{\gamma}\right)^2 - \tilde{\gamma} \\ = \left(\frac{w_i^*}{w_{i^*}^*}\right)^2 - \left((K-2)\tilde{\gamma} + 2 \sum_{j \notin \{i,i^*\}} \frac{w_j^*}{w_{i^*}^*} + 1\right) \tilde{\gamma} $$

where the equality uses (9). Therefore, we have shown that for all $n \ge \max\{N_4, N_6\}$,

$$ \frac{N_{n,i}}{N_{n,i^*}} \ge \frac{w_i^*}{w_{i^*}^*} \sqrt{1 - \left(\frac{w_{i^*}^*}{w_i^*}\right)^2 \left( (K-2)\tilde{\gamma} + 2 \sum_{j \notin \{i,i^*\}} \frac{w_j^*}{w_{i^*}^*} + 1 \right) } \ge \frac{w_i^*}{w_{i^*}^*} - \gamma, $$

where the last inequality holds for $\tilde{\gamma}$ small enough as a function of $\gamma$ and $w^*$. Therefore, we obtained

$$ \max_{i \neq i^*} \left| \frac{N_{n,i}}{N_{n,i^*}} - \frac{w_i^*}{w_{i^*}^*} \right| \le \gamma, $$

which concludes the proof, i.e. $\mathbb{E}_{\nu}[T_{\gamma}] < +\infty$. $\square$

Combining Lemmas 13 and 24 concludes the first part of Theorem 1, i.e.

$$ \limsup_{\delta \to 0} \frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_1, \delta}]}{\log(1/\delta)} \le T_{\varepsilon_0}(\mu) \left( 1 + \max_{i \neq i^*} \frac{\varepsilon_0 - \varepsilon_1}{\mu_{i^*} - \mu_i + \varepsilon_1} \right)^2. $$

## D.2 Fixed proportions

Using Lemma 9, the $\beta$-optimal allocation for $\varepsilon_0$-BAI are defined as

$$ w_{\varepsilon_0,\beta}(\mu) := \arg\max_{w \in \Delta_K, w_{i^*} = \beta} \min_{i \neq i^*} \frac{(\mu_{i^*} - \mu_i + \varepsilon_0)^2}{1/\beta + 1/w_i}. $$

Since $|i^*(\mu)| = 1$, let $\mu_{\varepsilon_0} = \mu_{\varepsilon_0}(i^*)$ where $\mu_{\varepsilon}(i^*)$ as in Lemma 9. Since we have $T_{\varepsilon_0,\beta}(\mu) = T_{\beta}^*(\mu_{\varepsilon_0})$ and $w_{\varepsilon_0,\beta}(\mu) = w_{\beta}^*(\mu_{\varepsilon_0})$, Lemma 6 and 8 yield that $w_{\varepsilon_0,\beta}(\mu) = \{w_{\beta}^*\}$ is a singleton with unique element denotes by $w_{\beta}^*$ which satisfies that $\min_{i \in [K]} w_{\beta,i}^* > 0$ and

$$ \forall i \in [K] \setminus \{i^*\}, \quad \frac{(\mu_{i^*} - \mu_i + \varepsilon_0)^2}{1/\beta + 1/w_{\beta,i}^*} = 2T_{\varepsilon_0,\beta}(\mu)^{-1}. \qquad (13) $$

When considering fixed proportions $\beta$, the proof strategy is the same as in Appendix D.1. The sole difference lies in the fact that the empirical allocation of the unique best arm is converging towards a fixed $\beta$.
**Convergence time** Let $\gamma > 0$. Let us define the convergence time $T_{\varepsilon_0, \beta, \gamma}$, which is a random variable quantifies the number of samples required for the empirical allocations $N_n$ to be $\gamma$-close to $w_{\beta}^*$:

$$ T_{\varepsilon_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\}. \quad (14) $$

Lemma 25 gives a sufficient condition for asymptotic $\beta$-optimality. The case $\varepsilon_0 = \varepsilon_1$ is a direct consequence of existing methods, e.g. Theorem 2 in [21] or Theorem 3 in [32].

**Lemma 25.** Let $\varepsilon_0 > 0$, $\varepsilon_1 \ge 0$ 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_{\varepsilon_0, \beta, \gamma}] < +\infty$. Using the threshold (4) in the stopping rule (3) with slack $\varepsilon_1$ 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_{\varepsilon_1, \delta}]}{\log(1/\delta)} \le T_{\varepsilon_0, \beta}(\mu) \left( 1 + \max_{i \ne i^*} \frac{\varepsilon_0 - \varepsilon_1}{\mu_{i^*} - \mu_i + \varepsilon_1} \right)^2 . $$

*Proof.* The proof is the same of the ones of Lemma 13. The sole difference is that we have $w_{\beta, i^*}^* = \beta$ by definition. $\square$

**Sufficient exploration** Lemma 26 shows that all arms are sufficiently explored and that the leader is the unique best arm for $n$ large enough.

**Lemma 26.** 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^*$.

*Proof.* Since Lemmas 16 and 17 holds, we can use the intermediate results of Lemma 18. It is direct to see that the proof can be conducted similarly by noting that, for all $i \ne j$,

$$ \min\{\beta_t(i, j), 1 - \beta_t(i, j)\} = \min\{\beta, 1 - \beta\} > 0. \quad \square $$

**Convergence towards optimal allocation** Combining Lemma 26 with the proof of Lemma F.8 in [20] yields Lemma 27.

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

$$ \left| \frac{N_{n,i^*}}{n-1} - \beta \right| \le \gamma. $$

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

**Lemma 28.** 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^{TC\varepsilon_0} \ne i. $$

Combining Lemmas 27 and 28 with the proof of Lemma F.10 in [20] yields Lemma 29.

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

$$ \left\| \frac{N_n}{n-1} - w_{\beta}^* \right\|_{\infty} \le \gamma. $$

Lemma 30 is a direct corollary of Lemma 29.

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

Combining Lemmas 25 and 30 concludes the second part of Theorem 1, i.e.

$$ \limsup_{\delta \to 0} \frac{\mathbb{E}_{\nu}[\tau_{\varepsilon_1, \delta}]}{\log(1/\delta)} \le T_{\varepsilon_0, \beta}(\mu) \left( 1 + \max_{i \ne i^*} \frac{\varepsilon_0 - \varepsilon_1}{\mu_{i^*} - \mu_i + \varepsilon_1} \right)^2 . $$
## E Non-asymptotic analysis

Let $\varepsilon_0 > 0$, $\beta \in (0, 1)$ and $\delta \in (0, 1)$. In this section, we provide a non-asymptotic analysis of EB-TC$_{\varepsilon_0}$ with fixed proportions $\beta$ and slack $\varepsilon_0 > 0$ when combined with the stopping rule (3) with parameters $(\varepsilon_0, \delta)$. In practice, we will mostly be interested in the case $\beta = 1/2$. First, we prove Lemma 5 in Appendix E.1. Then, we detail the proof of Theorem 2 in Appendix E.2.

In the following, we consider a sub-Gaussian bandit with distribution $\nu \in D^K$ having mean parameter $\mu \in \mathbb{R}^K$. In particular, our analysis holds when several arms have the largest mean $\mu_*$.

### E.1 Proof of Lemma 5

Let $s \ge 0$. For all $n > K$ and $\delta \in (0, 1]$, let $\mathcal{E}_{n,\delta} = \mathcal{E}_{n,\delta}^1 \cap \mathcal{E}_{n,\delta}^2$ with $(\mathcal{E}_{n,\delta}^1)_{n>K}$ and $(\mathcal{E}_{n,\delta}^2)_{n>K}$ as in (24) and (25), i.e.

$$ 
\begin{aligned}
\mathcal{E}_{n,\delta}^1 &= \left\{ \forall k \in [K], \forall t \le n, |\mu_{t,k} - \mu_k| < \sqrt{\frac{2f_1(n, \delta)}{N_{t,k}}} \right\}, \\
\mathcal{E}_{n,\delta}^2 &= \left\{ \forall (i, k) \in [K]^2 \text{ s.t. } i \ne 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{2f_2(n, \delta)} \right\},
\end{aligned}
$$

where $f_2(x, \delta) = \log(1/\delta) + (1+s)\log(x)$ and $f_2(x, \delta) = \log(1/\delta) + (2+s)\log(x)$.

Lemma 31 shows that when there are arms with strictly higher true mean than the one of the leader, then at least one of those arms is undersampled.

**Lemma 31.** Under $\mathcal{E}_{n,\delta}^1$, for all $t \in [n] \setminus [K]$ let $B_t^{EB} = k$. Then,

$$ \forall i \neq k, \quad 1(\mu_i > \mu_k) \min\{N_{t,k}, N_{t,i}\} \leq \frac{8f_1(n, \delta)}{(\mu_i - \mu_k)^2}. $$

*Proof.* Under $\mathcal{E}_{n,\delta}^1$, for all $t \in [n] \setminus [K]$, let $B_t^{EB} = k$. Then, for all $i \neq k$, we have

$$ 
\begin{aligned}
\mu_i - \sqrt{\frac{2f_1(n, \delta)}{\min\{N_{t,k}, N_{t,i}\}}} &\le \mu_i - \sqrt{\frac{2f_1(n, \delta)}{N_{t,i}}} \le \mu_{t,i} \le \mu_{t,k} \le \mu_k + \sqrt{\frac{2f_1(n, \delta)}{N_{t,k}}} \\
&\le \mu_k + \sqrt{\frac{2f_1(n, \delta)}{\min\{N_{t,k}, N_{t,i}\}}}
\end{aligned}
$$

Re-ordering the above equations for $i$ such that $\mu_i > \mu_k$ yields the result. $\square$

**Lemma 32.** Let $\varepsilon \ge 0$, $\Delta_\mu(\varepsilon) = \min_{k \notin \mathcal{I}_\varepsilon(\mu)} \Delta_k$ and $C_{\mu,\varepsilon_0}(\varepsilon) = \max\{2\Delta_\mu(\varepsilon)^{-1} - \varepsilon_0^{-1}, \varepsilon_0^{-1}\}^2$. Let $A_{\varepsilon_0,\varepsilon,i} = 2/\Delta_\mu(\varepsilon)^2$ for all $i \in i^*(\mu)$, $A_{\varepsilon_0,\varepsilon,i} = C_{\mu,\varepsilon_0}(\varepsilon)$ for all $i \in \mathcal{I}_\varepsilon(\mu) \setminus i^*(\mu)$, otherwise $A_{\varepsilon_0,\varepsilon,i} = \max\{C_{\mu,\varepsilon_0}(\varepsilon), 2/\Delta_\mu^2\}$. For all $n > K$, under event $\mathcal{E}_{n,\delta}$, for all $t \in [n] \setminus [K]$ such that $B_t^{EB} \notin \mathcal{I}_\varepsilon(\mu)$, there exists $i_t \in [K]$ such that

$$ T_t(i_t) \le \frac{4f_2(n, \delta)}{\min\{\beta, 1-\beta\}} A_{\varepsilon_0, \varepsilon, i_t} + 3(K-1)/2 \quad \text{and} \quad T_{t+1}(i_t) = T_t(i_t) + 1. $$

*Proof.* Let $\Delta_i = \mu_* - \mu_i$ and $\Delta_{\max} = \max_{i \in [K]} \Delta_i$. When $\varepsilon \ge \Delta_{\max}$, we have $\mathcal{I}_\varepsilon(\mu)^c = \emptyset$, hence the above result holds trivially since the event $B_t^{EB} \notin \mathcal{I}_\varepsilon(\mu)$ cannot happen. Let $\varepsilon \in [0, \Delta_{\max})$, i.e. $\mathcal{I}_\varepsilon(\mu)^c \neq \emptyset$. We will consider in two distinct cases since

$$ \{B_t \notin \mathcal{I}_\varepsilon(\mu)\} = \{B_t \notin \mathcal{I}_\varepsilon(\mu), C_t \in i^*(\mu)\} \cup \{B_t \notin \mathcal{I}_\varepsilon(\mu), C_t \notin i^*(\mu)\}. $$

**Case 1.** Let $t \in [n] \setminus [K]$ such that $(B_t^{EB}, C_t^{TC\varepsilon_0}) = (i, j)$ with $i \notin \mathcal{I}_\varepsilon(\mu)$ and $j \in i^*(\mu)$. Using Lemmas 46 and 31, we obtain

$$ \min\{\beta, 1-\beta\} (\min\{T_t(i), T_t(j)\} - 3(K-1)/2) \le \min\{N_{t,i}, N_{t,j}\} \le \frac{8f_1(n, \delta)}{\Delta_i^2} \le \frac{8f_2(n, \delta)}{\Delta_i^2}, $$
which can be rewritten as

$$ \min\{T_t(i), T_t(j)\} \le \frac{8f_2(n, \delta)}{\min\{\beta, 1-\beta\}\Delta_i^2} + 3(K-1)/2. $$

Let us define $\Delta_{\mu}(\varepsilon) = \min_{k \notin \mathcal{I}_{\varepsilon}(\mu)} \Delta_k$, and

$$ \forall i \notin \mathcal{I}_{\varepsilon}(\mu), \quad D_{\varepsilon,i} = 2/\Delta_i^2 \quad \text{and} \quad \forall i \in i^{*}(\mu), \quad D_{\varepsilon,i} = 2/\Delta_{\mu}(\varepsilon)^2. $$

The above shows that there exists $k_t \in \mathcal{I}_{\varepsilon}(\mu)^{\mathcal{C}} \cup i^{*}(\mu)$ such that

$$ T_t(k_t) \le \frac{4f_2(n, \delta)}{\min\{\beta, 1-\beta\}} D_{\varepsilon, k_t} + 3(K-1)/2 \quad \text{and} \quad T_{t+1}(k_t) = T_t(k_t) + 1. $$

**Case 2.** Let $t \in [n] \setminus [K]$ such that $(B_t^{\text{EB}}, C_t^{\text{TC}\varepsilon_0}) = (i, j)$ with $i \notin \mathcal{I}_{\varepsilon}(\mu)$ and $j \notin i^{*}(\mu)$. Let $i_0 \in i^{*}(\mu)$. Using the TC challenger, we obtain

$$ \frac{\varepsilon_0 - \Delta_i}{\sqrt{1/N_{t,i} + 1/N_{t,i_0}}} + \sqrt{2f_2(n, \delta)} \ge \frac{\mu_{t,i} - \mu_{t,i_0} + \varepsilon_0}{\sqrt{1/N_{t,i} + 1/N_{t,i_0}}} \ge \frac{\mu_{t,i} - \mu_{t,j} + \varepsilon_0}{\sqrt{1/N_{t,i} + 1/N_{t,j}}} \\ \ge \varepsilon_0 \sqrt{\min\{N_{t,i}, N_{t,j}\}/2}. $$

Using Lemma 31, we obtain

$$ \frac{1}{1/N_{t,i} + 1/N_{t,i_0}} \le \min\{N_{t,i}, N_{t,i_0}\} \le \frac{8f_1(n, \delta)}{\Delta_i^2} \le \frac{8f_2(n, \delta)}{\Delta_i^2}. $$

By distinguishing between $\varepsilon_0 > \Delta_i$ and $\varepsilon_0 \le \Delta_i$ and using that $\Delta_i > 0$, we have

$$ \frac{\varepsilon_0 - \Delta_i}{\sqrt{1/N_{t,i} + 1/N_{t,i_0}}} + \sqrt{2f_2(n, \delta)} \le \max\{2\varepsilon_0/\Delta_i - 1, 1\} \sqrt{2f_2(n, \delta)}. $$

Using Lemma 46 to lower bound $\min\{N_{t,i}, N_{t,j}\}$ and reordering, we have shown that

$$ \min\{T_t(i), T_t(j)\} \le \max\left\{\left(\frac{2}{\Delta_i} - \frac{1}{\varepsilon_0}\right)^2, \frac{1}{\varepsilon_0^2}\right\} \frac{4f_2(n, \delta)}{\min\{\beta, 1-\beta\}} + 3(K-1)/2. $$

Let us define $C_{\mu,\varepsilon_0}(\varepsilon) = \max\{2\Delta_{\mu}(\varepsilon)^{-1} - \varepsilon_0^{-1}, \varepsilon_0^{-1}\}^2$. The above shows that, there exists $k_t \notin i^{*}(\mu)$ such that

$$ T_t(k_t) \le \frac{4f_2(n, \delta)}{\min\{\beta, 1-\beta\}} C_{\mu,\varepsilon_0}(\varepsilon) + 3(K-1)/2 \quad \text{and} \quad T_{t+1}(k_t) = T_t(k_t) + 1. $$

**Summary.** Let us define $(A_{\varepsilon_0,\varepsilon,i})_{i \in [K]}$ as in the statement of Lemma 32. Under $\mathcal{E}_{n,\delta}$, we have shown that, when $B_t \notin \mathcal{I}_{\varepsilon}(\mu)$, there exists $i_t \in [K]$ such that

$$ T_t(k_t) \le \frac{4f_2(n, \delta)}{\min\{\beta, 1-\beta\}} A_{\varepsilon, \varepsilon_0, i_t} + 3(K-1)/2 \quad \text{and} \quad T_{t+1}(k_t) = T_t(k_t) + 1. $$

□

For all $n > K$, under event $\mathcal{E}_{n,\delta}$, combining Lemma 4 and 32 for $A_t(n, \delta) = \{B_t^{\text{EB}} \notin \mathcal{I}_{\varepsilon}(\mu)\}$ and $D_i(n, \delta) = \frac{4f_2(n, \delta)}{\min\{\beta, 1-\beta\}} A_{\varepsilon_0, \varepsilon, i} + 3(K-1)/2$ yields that

$$ \sum_{t=K+1}^{n} 1 (B_t^{\text{EB}} \notin \mathcal{I}_{\varepsilon}(\mu)) \le \frac{4f_2(n, \delta)}{\min\{\beta, 1-\beta\}} H_{\mu, \varepsilon_0}(\varepsilon) + 3K(K-1)/2. $$

where we used that $\sum_{i \in [K]} A_{\varepsilon_0, \varepsilon, i} = H_{\mu, \varepsilon_0}(\varepsilon)$ where $H_{\mu, \varepsilon_0}(\varepsilon)$ is defined in (5). To conclude the proof of Lemma 5, we use that

$$ \sum_{t=K+1}^{n} 1 (B_t^{\text{EB}} \notin \mathcal{I}_{\varepsilon}(\mu)) = n-1 - \sum_{i \in \mathcal{I}_{\varepsilon}(\mu)} \sum_{j} T_n(i, j). $$

Let $\tilde{f}_1(n, \delta)$ and $\tilde{f}_2(n, \delta)$ defined as in (26) and (28). Using Lemma 50, we have $\tilde{f}_1(n, \delta) \le \tilde{f}_2(n, \delta)$. Therefore, it is direct to see that Lemma 33 can be proven with the same proof as for Lemma 5 based on the concentration event $\tilde{\mathcal{E}}_{n,\delta} = \tilde{\mathcal{E}}_{n,\delta}^1 \cap \tilde{\mathcal{E}}_{n,\delta}^2$ with $(\tilde{\mathcal{E}}_{n,\delta}^1)_{n>K}$ and $(\tilde{\mathcal{E}}_{n,\delta}^2)_{n>K}$ as in (27) and (29).
**Lemma 33.** Let $\delta \in (0, 1]$, $\varepsilon \ge 0$ and $H_{\mu, \varepsilon_0}(\varepsilon)$ as in (5). For all $n > K$, under the event $\tilde{\mathcal{E}}_{n, \delta}$,

$$ \sum_{i \in \mathcal{I}_{\varepsilon}(\mu)} \sum_{j} T_n(i, j) \ge n - 1 - \left( \frac{4H_{\mu, \varepsilon_0}(\varepsilon)}{\min\{\beta, 1-\beta\}} \tilde{f}_2(n, \delta) + 3K(K-1)/2 \right). $$

## E.2 Proof of Theorem 2

Let $s > 1$. For all $n > K$, let $\mathcal{E}_n = \mathcal{E}_{n,1}^1 \cap \mathcal{E}_{n,1}^2$ with $(\mathcal{E}_{n,1}^1)_{n>K}$ and $(\mathcal{E}_{n,1}^2)_{n>K}$ as in (24) and (25). Using Lemma 45, we know that $\sum_{n>K} \mathbb{P}_{\nu}(\mathcal{E}_n^c) \le \frac{K(K+1)}{2} \zeta(s)$.

Let $\varepsilon_0 > 0$, $\varepsilon_1 \ge \varepsilon_0$ and $\delta \in (0, 1)$. Since $\varepsilon_1 \ge \varepsilon_0$, and using the definition of the stopping rule (3), it is direct to see that $\mathbb{E}_{\nu}[\tau_{\varepsilon_1, \delta}] \le \mathbb{E}_{\nu}[\tau_{\varepsilon_0, \delta}]$.

Suppose that we have constructed a time $T(\delta) > K$ be such that for $n \ge T(\delta)$, $\mathcal{E}_n \subset \{\tau_{\varepsilon_0, \delta} \le n\}$ Then, Lemma 47 yields

$$ \mathbb{E}_{\nu}[\tau_{\varepsilon_0, \delta}] \le T(\delta) + \frac{K(K+1)}{2} \zeta(s). $$

We will construct an infinite number of times $\{T(\delta, u)\}_{u \in \mathcal{U}}$ such that the above property holds, hence taking the infimum yields

$$ \mathbb{E}_{\nu}[\tau_{\varepsilon_0, \delta}] \le \inf_{u \in \mathcal{U}} T(\delta, u) + \frac{K(K+1)}{2} \zeta(s). $$

This proof strategy is the one used to prove Theorem 5. Theorem 2 is a corollary of Theorem 5. Note that the notation of both theorems differ slightly since we provide a shorter statement in the main content. The key difference lies in the refined analysis used to clip $\min_{j \ne i} w_{\varepsilon_0, 1/2}(\mu, i)_j$ by a fixed value $x \in [0, (K-1)^{-1}]$ for all $i \in \mathcal{I}_{\varepsilon}(\mu)$.

**Theorem 5.** Let $\varepsilon_0 > 0$, $\varepsilon_1 \ge \varepsilon_0$ and $\delta \in (0, 1)$. Using the threshold (4) in the stopping rule (3) with error $\varepsilon_1$, the EB-TC$_{\varepsilon_0}$ algorithm with fixed proportions $\beta = 1/2$ is $(\varepsilon_1, \delta)$-PAC and satisfies that, for all $\nu \in \mathcal{D}^K$, $\mathbb{E}_{\nu}[\tau_{\varepsilon_1, \delta}] \le \mathbb{E}_{\nu}[\tau_{\varepsilon_0, \delta}]$ and

$$ \mathbb{E}_{\nu}[\tau_{\varepsilon_0, \delta}] \le \inf_{(\varepsilon, x) \in [0, \varepsilon_0] \times [0, (K-1)^{-1}]} \max\{T_{\mu, \varepsilon_0}(\delta, \varepsilon, x) + 1, S_{\mu, \varepsilon_0}(\varepsilon, x)\} + \zeta(s) \frac{K(K+1)}{2}, $$

where

$$ \begin{aligned} T_{\mu, \varepsilon_0}(\delta, \varepsilon, x) &= \sup \left\{ n \mid n-1 \le \frac{2(1+\gamma)^2 \sum_{i \in \mathcal{I}_{\varepsilon}(\mu)} T_{\varepsilon_0, 1/2}(\mu, i)}{(1-x)^{d_{\mu, \varepsilon_0}(\varepsilon, x)}} \right. \\ & \qquad \left. \left( \sqrt{c(n-1, \delta)} + \sqrt{(2+s) \log n} \right)^2 \right\}, \\ S_{\mu, \varepsilon_0}(\varepsilon, x) &= h_1 \left( \frac{4(2+s)(1+\gamma^{-1})}{a_{\mu, \varepsilon_0}(\varepsilon, x) v_{\mu, \varepsilon_0}(\varepsilon)} H_{\mu, \varepsilon_0}(\varepsilon), \frac{(1+\gamma^{-1})(3K^2/4+1)}{a_{\mu, \varepsilon_0}(\varepsilon, x) v_{\mu, \varepsilon_0}(\varepsilon)} + 1 \right), \\ v_{\mu, \varepsilon_0}(\varepsilon) &= \frac{\min_{i \in \mathcal{I}_{\varepsilon}(\mu)} T_{\varepsilon_0, 1/2}(\mu, i)}{\sum_{i \in \mathcal{I}_{\varepsilon}(\mu)} T_{\varepsilon_0, 1/2}(\mu, i)}, \\ a_{\mu, \varepsilon_0}(\varepsilon, x) &= \min_{i \in \mathcal{I}_{\varepsilon}(\mu)} (1-x)^{d_{\mu, \varepsilon_0}(x, i)} \max\{\min_{j \ne i} w_{\varepsilon_0, 1/2}(\mu, i)_j, x/2\}, \\ d_{\mu, \varepsilon_0}(\varepsilon, x) &= \max_{i \in \mathcal{I}_{\varepsilon}(\mu)} d_{\mu, \varepsilon_0}(x, i) \quad \text{with} \quad d_{\mu, \varepsilon_0}(x, i) = |\{j \ne i \mid w_{\varepsilon_0, 1/2}(\mu, i)_j < x/2\}|, \end{aligned} $$

where $\gamma \in (0, 1/2]$ and $s > 1$ are analysis parameters. $T_{\varepsilon_0, 1/2}(\mu, i)$ and $w_{\varepsilon_0, 1/2}(\mu, i)$ are defined in (1), $H_{\mu, \varepsilon_0}(\varepsilon)$ in (5), $\zeta$ is the Riemann $\zeta$ function and $h_1(z, y) = z\bar{W}_{-1}(\log(z) + y/z)$ is defined in Lemma 51 and satisfies that $h_1(z, y) \approx x \log(z) + y + \log(\log(z) + y/z)$.

**Proof.** Let $\varepsilon \in [0, \varepsilon_0]$ be an analysis parameter, and $I_{\varepsilon} = |\mathcal{I}_{\varepsilon}(\mu)|$. Let $v \in \mathring{\Delta}_{I_{\varepsilon}}$ defined as

$$ \forall i \in \mathcal{I}_{\varepsilon}(\mu), \quad v_i = \frac{T_{\varepsilon_0, 1/2}(\mu, i)}{\sum_{j \in \mathcal{I}_{\varepsilon}(\mu)} T_{\varepsilon_0, 1/2}(\mu, j)}, \quad \text{hence} \quad \min_{i \in \mathcal{I}_{\varepsilon}(\mu)} v_i = v_{\mu, \varepsilon_0}(\varepsilon). $$

The main technical result on which our proof relies on is Lemma 34, which we will prove afterwards.
**Lemma 34.** There exist $D_0 > 0$ and $T_\mu > 0$ such that for all $n \ge T_\mu$ such that $\mathcal{E}_n \cap \{n < \tau_{\varepsilon_1, \delta}\}$ holds true, there exists $i_0 \in \mathcal{I}_\varepsilon(\mu)$ and $t \le n$ with $B_t^{EB} = i_0$, which satisfies

$$1/N_{t,i_0}^{i_0} + 1/N_{t,C_t^{\tau_{\varepsilon_0}}}^{i_0} \le \frac{D_0}{v_{i_0}(n-1)} \left(1/\beta + 1/w_{\beta}^*(i_0) C_t^{\tau_{\varepsilon_0}}\right). \quad (15)$$

Before proving Lemma 34, we show how it can be used to conclude. Based on Lemma 34, let $D_0 > 0$, $T_\mu > 0$, $n > T_\mu$ such that $\mathcal{E}_n \cap \{n < \tau_{\varepsilon_1, \delta}\}$ holds true, $i_0$ and $t \le n$ such that as $B_t^{EB} = i_0$ and

$$1/N_{t,i_0}^{i_0} + 1/N_{t,C_t^{\tau_{\varepsilon_0}}}^{i_0} \le \frac{D_0}{v_{i_0}(n-1)} \left(1/\beta + 1/w_{\beta}^*(i_0) C_t^{\tau_{\varepsilon_0}}\right).$$

Using the stopping rule (3) with error $\varepsilon_0$, $t \le n < \tau_{\varepsilon_1, \delta}$, $B_t^{EB} = \hat{i}_t = i_0$ and the definition of the TC$_{\varepsilon_0}$challenger in (2) with slack $\varepsilon_0$, we obtain

$$\begin{aligned} \sqrt{2c(n-1, \delta)} &\ge \min_{i \ne i_0} \frac{\mu_{t,i_0} - \mu_{t,i} + \varepsilon_0}{\sqrt{1/N_{t,i_0} + 1/N_{t,i}}} \\ &\ge \frac{\mu_{i_0} - \mu_{C_t^{\tau_{\varepsilon_0}}} + \varepsilon_0}{\sqrt{1/N_{t,i_0} + 1/N_{t,C_t^{\tau_{\varepsilon_0}}}}} - \sqrt{2(2+s) \log n} \\ &\ge \sqrt{\frac{1/\beta + w_{\beta}^*(i_0)^{-1}}{1/N_{t,i_0}^{i_0} + 1/N_{t,C_t^{\tau_{\varepsilon_0}}}^{i_0}}} \sqrt{2T_{\varepsilon_0,\beta}(\mu, i_0)^{-1}} - \sqrt{2(2+s) \log n} \\ &\ge \sqrt{\frac{2(n-1)}{D_0 \sum_{i \in \mathcal{I}_\varepsilon(\mu)} T_{\varepsilon_0,\beta}(\mu, i)}} - \sqrt{2(2+s) \log n}. \end{aligned}$$

The third inequality is obtained since $\mathcal{E}_n$ holds. The fourth inequality is obtained since $N_{t,i}^{i_0} \ge N_{t,i}^{i_0}$ for all $i \in [K]$ and by using Lemmas 8 and 9. The last inequality is obtained by Lemma 34 and using the definition of $v_{i_0}$.

Let's define $T(\delta, D_0) := \sup\{n > K \mid n-1 < D_0 \sum_{i \in \mathcal{I}_\varepsilon(\mu)} T_{\varepsilon_0,\beta}(\mu, i)(\sqrt{c(n-1, \delta)} + \sqrt{(2+s) \log n})^2\}$. Therefore, we have $\mathcal{E}_n \cap \{n < \tau_{\varepsilon_0, \delta}\} = \emptyset$ (i.e. $\mathcal{E}_n \subset \{\tau_{\varepsilon_0, \delta} \le n\}$) for all $n \ge \max\{T(\delta, D_0), T_\mu + 1\}$. This concludes the construction.

To conclude the proof, we will show that Lemma 34 for many choices of $D_0$ and $T_\mu$.

**Vanilla Proof of Lemma 34.** Let $g_\varepsilon(n) = \frac{4H_{\mu,\varepsilon_0}(\varepsilon)}{\min\{\beta, 1-\beta\}}(2+s) \log n + 3K(K-1)/2$. Using Lemma 5, under the event $\mathcal{E}_n$,

$$\sum_{i \in \mathcal{I}_\varepsilon(\mu)} \sum_j T_n(i, j) \ge n - 1 - g_\varepsilon(n).$$

Therefore, the pigeonhole principle yields that there exists $i_0 \in \mathcal{I}_\varepsilon(\mu)$ such that

$$\sum_j T_n(i_0, j) \ge v_{i_0}(n-1 - g_\varepsilon(n)).$$

The crux of the problem is to relate $N_{t,C_t}^{i_0}/(n-1)$ and $w_{\beta}^*(i_0) C_t^{\tau_{\varepsilon_0}}$. To do so, we use the approach of [20] that builds on the idea behind the proof for APT from [30]: consider an arm being over-sampled and study the last time this arm was pulled.

By the pigeonhole principle, at time $n$, there is an index $k_1 \ne i_0$ such that

$$N_{n,k_1}^{i_0} \ge \frac{w_{\beta}^*(i_0)k_1}{1-\beta} \sum_{j \ne i_0} N_{n,j}^{i_0}, \quad (16)$$

and we take such $k_1$. Let $t_1 := \sup\{t < n \mid (B_t, C_t) = (i_0, k_1)\}$ be the last time at which $i_0$ was the leader and $k_1$ was the challenger. If $I_{t_1} = B_{t_1}$ then $N_{t_1,k_1}^{i_0} = N_{n,k_1}^{i_0}$, otherwise $N_{t_1,k_1}^{i_0} = N_{n,k_1}^{i_0} - 1$.
In both cases, we have $N_{t_1,k_1}^{i_0} \ge N_{n,k_1}^{i_0} - 1$. Combined with the above and using that $w_{\beta}^{*}(i_0)_{k_1} \le 1 - \beta$ and $v_{i_0} \le 1$, we obtain

$$
\begin{align*}
N_{t_1,k_1}^{i_0} \ge N_{n,k_1}^{i_0} - 1 &\ge \frac{w_{\beta}^{*}(i_0)_{k_1}}{1-\beta} \sum_{j \ne i_0} N_{n,j}^{i_0} - 1 \\
&\ge w_{\beta}^{*}(i_0)_{k_1} \left( \sum_{j \ne i_0} T_n(i_0, j) - \frac{K-1}{2(1-\beta)} \right) - 1 \\
&\ge w_{\beta}^{*}(i_0)_{k_1} v_{i_0}(n-1) - (1-\beta)v_{i_0}g_{\varepsilon}(n) - \frac{K+1}{2} \\
&\ge w_{\beta}^{*}(i_0)_{k_1} v_{i_0}(n-1) - h_{\varepsilon}(n), \\
\text{with } h_{\varepsilon}(n) &= \frac{4(1-\beta)H_{\mu,\varepsilon_0}(\varepsilon)}{\min\{\beta, 1-\beta\}} f_2(n) + \frac{(1-\beta)3K(K-1)}{2} + \frac{K+1}{2}.
\end{align*}
$$

Let $w_{i_0,-} > 0$ be a lower bound on $w_{\beta}^{*}(i_0)_{k_1}$, e.g. $w_{i_0,-} = \min_{i \ne i_0} w_{\beta}^{*}(i_0)_{i}$. For instances $\mu$ such that $w_{\beta}^{*}(i_0)_{k_1}$ is small, the equation (16) can be satisfied at the very beginning, hence $t_1$ might be sublinear in $n$. Due to the missing link between $t_1$ and $n$, we use the following inequality

$$1/N_{t_1,i_0}^{i_0} + 1/N_{t_1,k_1}^{i_0} \le \frac{1}{v_{i_0}(n-1)} \left( \frac{1}{\beta} + \frac{v_{i_0}(n-1)}{N_{t_1,k_1}^{i_0}} \right) \left( \frac{N_{t_1,k_1}^{i_0}}{N_{t_1,i_0}^{i_0}} + 1 \right),$$

which is a suboptimal step which artificially introduces $1/\beta$.

Let $\gamma \in (0, 1/2]$. It remains to control both terms. First, we obtain

$$1/\beta + \frac{v_{i_0}(n-1)}{N_{t_1,k_1}^{i_0}} \le 1/\beta + \frac{1}{w_{\beta}^{*}(i_0)_{k_1} - \frac{h_{\varepsilon}(n)}{v_{i_0}(n-1)}} \le (1+\gamma)(1/\beta + 1/w_{\beta}^{*}(i_0)_{k_1}),$$

for all $n > C_1(w_{i_0,-}, v_{\mu,\varepsilon_0}(\varepsilon))$. The last inequality is obtained by definition of

$$C_1(w, v) := \sup \left\{ n \ge 1 \mid n-1 < \frac{h_{\varepsilon}(n)}{wv} (1+\gamma^{-1}) \right\}, \quad (17)$$

which ensures that, for all $n > C_1(w_{i_0,-}, v_{\mu,\varepsilon_0}(\varepsilon))$, the last condition of the equivalence

$$w_{\beta}^{*}(i_0)_{k_1} - \frac{h_{\varepsilon}(n)}{v_{i_0}(n-1)} \ge (1+\gamma)^{-1} w_{\beta}^{*}(i_0)_{k_1} \iff n-1 \ge \frac{h_{\varepsilon}(n)}{v_{i_0} w_{\beta}^{*}(i_0)_{k_1}} (1+\gamma^{-1})$$

is satisfied since $w_{\beta}^{*}(i_0)_{k_1} \ge w_{i_0,-}, v_{i_0} \ge v_{\mu,\varepsilon_0}(\varepsilon)$ and $n > C_1(w_{i_0,-}, v_{\mu,\varepsilon_0}(\varepsilon))$.

Second, using Lemma 46, we can show that

$$N_{t_1,i_0}^{i_0} \ge T_{t_1}(i_0, k_1) - N_{t_1,k_1}^{i_0} \ge \beta T_{t_1}(i_0, k_1) - 1 \ge \frac{\beta}{1-\beta} N_{t_1,k_1}^{i_0} - \frac{1}{1-\beta}.$$

Then, re-ordering the above and using that $N_{t_1,k_1}^{i_0} \ge w_{\beta}^{*}(i_0)_{k_1} v_{i_0}(n-1) - h_{\varepsilon}(n)$, we obtain

$$\frac{N_{t_1,k_1}^{i_0}}{N_{t_1,i_0}^{i_0}} + 1 \le \left( \frac{\beta}{1-\beta} - \frac{1}{(1-\beta) \left( w_{\beta}^{*}(i_0)_{k_1} v_{i_0}(n-1) - h_{\varepsilon}(n) \right)} \right)^{-1} + 1 \le (1+\gamma)/\beta,$$

for all $n > C_2(w_{i_0,-}, v_{\mu,\varepsilon_0}(\varepsilon))$. The last inequality is obtained by definition of

$$C_2(w, v) := \sup \left\{ n \in \mathbb{N}^{*} \mid n-1 < \frac{1}{wv} \left( h_{\varepsilon}(n) + \frac{\gamma+1-\beta}{\beta\gamma} \right) \right\}, \quad (18)$$

which ensures that, for all $n > C_2(w_{i_0,-}, v_{\mu,\varepsilon_0}(\varepsilon))$, the last condition of the equivalence

$$\left( \frac{\beta}{1-\beta} - \frac{1}{(1-\beta) \left( w_{\beta}^{*}(i_0)_{k_1} v_{i_0}(n-1) - h_{\varepsilon}(n) \right)} \right)^{-1} + 1 \le (1+\gamma)/\beta \\
\iff \frac{1}{w_{\beta}^{*}(i_0)_{k_1} v_{i_0}(n-1) - h_{\varepsilon}(n)} \le \frac{\beta\gamma}{\gamma+1-\beta} \\
\iff n-1 \ge \frac{1}{w_{\beta}^{*}(i_0)_{k_1} v_{i_0}} \left( h_{\varepsilon}(n) + \frac{\gamma+1-\beta}{\beta\gamma} \right)$$
is satisfied since $w_{\beta}^{*}(i_0)_{k_1} \ge w_{i_0, -}^{*}, v_{i_0} \ge v_{\mu, \varepsilon_0}(\varepsilon)$ and $n > C_2(w_{i_0, -}, v_{\mu, \varepsilon_0}(\varepsilon))$.

Let $T_{\mu} \ge \max_{k \in [2]} C_k(\min_{i \in \mathcal{I}_{\varepsilon}(\mu)} w_{i, -}, v_{\mu, \varepsilon_0}(\varepsilon))$ and $D_0 = (1 + \gamma)^2/\beta$. In summary, we have shown that for all $n > T_{\mu}$, there exists $i_0 \in \mathcal{I}_{\varepsilon}(\mu)$ and $t_1 \le n$ with $B_{t_1} = i_0$ and such that (15) holds.

For $\beta = 1/2$, using that $K \ge 2, 1 < 1 + \gamma^{-1}$ and $5/2 + \gamma^{-1} \le 3(1 + \gamma^{-1})/2$ (since $\gamma \in (0, 1/2]$), we obtain that

$$ \max_{i \in [2]} C_i(w, v) \le \sup \left\{ n \ge 1 \mid n - 1 < \frac{1 + \gamma^{-1}}{wv} \left( 4(2 + s)H_{\mu, \varepsilon_0}(\varepsilon) \log n + 3K^2/4 + 1 \right) \right\} \\ < h_1 \left( \frac{4(2 + s)(1 + \gamma^{-1})}{wv} H_{\mu, \varepsilon_0}(\varepsilon), \frac{(1 + \gamma^{-1})(3K^2/4 + 1)}{wv} + 1 \right), $$

where the last inequality uses Lemma 51 and $h_1(x, y)$ defined therein.

Using $w_{i_0, -} = \min_{i \ne i_0} w_{\beta}^{*}(i_0)_i$ and $\beta = 1/2$, the first part of Theorem 5 (i.e. $x = 0$) is obtained by taking the infimum over $(\varepsilon, x) \in [0, \varepsilon_0] \times \{0\}$.

**Refined Proof of Lemma 34.** When considering large $K$ or instances with unbalanced $\beta$-optimal allocation, $\min_{i_0 \in \mathcal{I}_{\varepsilon}(\mu)} \min_{i \ne i_0} w_{\beta}^{*}(i_0)_i$ can become arbitrarily small, hence a dependence in its inverse is undesired. Thanks to the refined analysis from [20], we can clip it with a value of our choosing which is away from zero.

Let $x \in (0, 1/(K-1)]$ be an allocation threshold and $d_{\mu}(x, i) := |\{j \in [K] \setminus \{i\} | w_{\beta}^{*}(i)_j < (1-\beta)x\}|$ for all $i \in \mathcal{I}_{\varepsilon}(\mu)$. The equation (16) is only informative when $(1) w_{\beta}^{*}(i_0)_{k_1} \ge (1-\beta)x$ or $(2) w_{\beta}^{*}(i_0)_{k_1} < (1-\beta)x$ and $N_{n,k_1}^{i_0} \ge x \sum_{j \ne i_0} N_{n,j}^{i_0}$. The problematic case occurs when $(3) w_{\beta}^{*}(i_0)_{k_1} < (1-\beta)x$ and $N_{n,k_1}^{i_0} < x \sum_{j \ne i_0} N_{n,j}^{i_0}$.

When $w_{\beta}^{*}(i_0)_{k_1} \ge (1-\beta)x$, we can use the above computations by considering $w_{i_0, -} = \max\{(1-\beta)x, \min_{i \ne i_0} w_{\beta}^{*}(i_0)_i\}$.

When $w_{\beta}^{*}(i_0)_{k_1} < (1-\beta)x$ and $N_{n,k_1}^{i_0} \ge x \sum_{j \ne i_0} N_{n,j}^{i_0}$, the above proof can be conducted by using $(1-\beta)x$ instead of $w_{\beta}^{*}(i_0)_{k_1}$ since we will obtain that

$$ N_{t_1, k_1}^{i_0} \ge (1 - \beta)xv_{i_0}(n - 1) - h_{\varepsilon}(n) \quad \text{and} \quad 1/\beta + \frac{1}{(1 - \beta)x} \le 1/\beta + 1/w_{\beta}^{*}(i_0)_{k_1}. $$

Then, we can likewise consider $w_{i_0, -} = \max\{(1-\beta)x, \min_{i \ne i_0} w_{\beta}^{*}(i_0)_i\}$ to conclude.

When $w_{\beta}^{*}(i_0)_{k_1} < (1-\beta)x$ and $N_{n,k_1}^{i_0} < x \sum_{j \ne i_0} N_{n,j}^{i_0}$, as in (16), the pigeonhole principle yields that there exists $k_2 \in [K] \setminus \{i_0, k_1\}$ such that

$$ N_{n,k_2}^{i_0} \ge \frac{w_{\beta}^{*}(i_0)_{k_2}}{1 - \beta - w_{\beta}^{*}(i_0)_{k_1}} \sum_{j \notin \{i_0, k_1\}} N_{n,j}^{i_0} \ge \frac{(1 - x)w_{\beta}^{*}(i_0)_{k_2}}{1 - \beta} \sum_{j \ne i_0} N_{n,j}^{i_0}. $$

Based on $k_2$ the same dichotomy as for $k_1$ happens: either we can conclude the proof when we are in case 1 or 2 or we cannot since we are in case 3. If case 3 occurs also for $k_2$, i.e. $w_{\beta}^{*}(i_0)_{k_2} < (1-\beta)x$ and $N_{n,k_2}^{i_0} < x \sum_{j \notin \{i_0, k_1\}} N_{n,j}^{i_0}$, we should also ignore it since it is non informative and construct a third arm $k_3$.

The main idea is then to peel off arms that are not informative, till we find an informative one. By induction, we construct a sequence $(k_a)_{a \in [d]}$ of such arms, where $k_d$ is the first arm for which either $(1) w_{\beta}^{*}(i_0)_{k_d} \ge (1-\beta)x$ or $(2) w_{\beta}^{*}(i_0)_{k_d} < (1-\beta)x$ and $N_{n,k_d}^{i_0} \ge x \sum_{j \notin \{i_0\} \cup \{k_a\}_{a \in [d-1]}} N_{n,j}^{i_0}$ holds. This means that for all $a \in [d-1]$, we have $w_{\beta}^{*}(i_0)_{k_a} < (1-\beta)x$ and

$$ N_{n,k_a}^{i_0} < x \sum_{j \notin \{i_0\} \cup \{k_b\}_{b \in [a-1]}} N_{n,j}^{i_0}. $$

Using the pigeonhole principle for $i \in [K] \setminus \{(i_0) \cup \{k_a\}_{a \in [d-1]}\}$ yields that $k_d$ satisfies

$$ N_{n,k_d}^{i_0} \ge \frac{w_{\beta}^{*}(i_0)_{k_d}}{1 - \beta - \sum_{a \in [d-1]} w_{\beta}^{*}(i_0)_{k_a}} \sum_{j \notin \{i_0\} \cup \{k_b\}_{b \in [a-1]}} N_{n,j}^{i_0}, $$
Using a simple recurrence on the arms {$k_a$}$_{a\in[d-1]}$, we obtain that

$$
\sum_{j \notin \{i_0\} \cup \{k_b\}_{b \in [a-1]}} N_{n,j}^{i_0} \ge (1-x)^{d-1} \sum_{j \ne i_0} N_{n,j}^{i_0}.
$$

Let $t_d := \sup \{t < n \mid (B_t, C_t) = (i_0, k_d)\}$. Since the arm $k_d$ satisfies case 1 or case 2, we can conclude similarly as above with an extra multiplicative factor $(1-x)^{d-1}$.

To remove the dependency in the random variable $d$, we consider the worst case scenario where $\{k_a\}_{a\in[d-1]} = \{i \in [K] \setminus \{i_0\} | w_{\beta}^*(i_0)_i < (1-\beta)x\}$, i.e. $d-1 \le d_{\mu}(x, i_0)$. In words, it means that we had to enumerate over all arms with small allocation, such that case 2 didn't hold, before finding an arm with large allocation, i.e. satisfying case 1. Let $d_{\mu,\varepsilon}(x) = \max_{i \in \mathcal{I}_{\varepsilon}(\mu)} d_{\mu}(x, i)$. Using that

$$
\begin{gather*}
(1-x)^{d-1} \ge (1-x)^{d_{\mu}(x,i_0)} \ge (1-x)^{d_{\mu,\varepsilon}(x)}, \\
w_{i_0,-} = (1-x)^{d_{\mu}(x,i_0)} \max\{(1-\beta)x, \min_{i \ne i_0} w_{\beta}^*(i_0)_i\},
\end{gather*}
$$

we can conclude the proof by taking $T_{\mu} \ge \max_{k \in [2]} C_k(\min_{i \in \mathcal{I}_{\varepsilon}(\mu)} w_{i,-}, v_{\mu, \varepsilon_0}(\varepsilon))$ and $D_0 = \frac{(1+\gamma)^2}{\beta(1-x)^{d_{\mu, \varepsilon}(x)}}$. In other words, we have shown that $n > T_{\mu}$, there exists $i_0 \in \mathcal{I}_{\varepsilon}(\mu)$ and $t_d \le n$ with $B_{t_d} = i_0$ and such that (15) holds. Using $\beta = 1/2$, the second part of Theorem 5 is obtained by taking the infimum over $(\varepsilon, x) \in [0, \varepsilon_0] \times (0, 1/(K-1))$. $\square$

E.2.1 Consequence of tighter concentration

It is direct to see that the proof of Theorem 5 will also work when using the concentration event
$\tilde{\mathcal{E}}_n = \tilde{\mathcal{E}}_{n,1}^1 \cap \tilde{\mathcal{E}}_{n,1}^2$ with $(\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

$$
\begin{align*}
\tilde{f}_1(n) &= \frac{1}{2} \bar{W}_{-1}(2s \log n + 2 \log(2 + \log n) + 2), \\
\tilde{f}_2(n) &= \bar{W}_{-1}(s \log n + 2 \log(2 + \log n) + 2).
\end{align*}
$$

Using Lemma 50, we know that $\tilde{f}_1(n) \le \tilde{f}_2(n)$. Then, we will be able to show

$$
\mathbb{E}_{\nu}[\tau_{\delta}] \le \inf_{(\varepsilon, x) \in [0, \varepsilon_0] \times [0, 1/(K-1)]} \max \left\{ \tilde{T}_{\mu, \varepsilon_0}(\delta, \varepsilon, x) + 1, \tilde{S}_{\mu, \varepsilon_0}(\varepsilon, x) \right\} + \zeta(s)K(K+1)/2,
$$

where

$$
\begin{align*}
\tilde{T}_{\mu, \varepsilon_0}(\delta, \varepsilon, x) &= \sup \left\{ n \mid n-1 \le \frac{2(1+\gamma)^2 \sum_{i \in \mathcal{I}_{\varepsilon}(\mu)} T_{\varepsilon_0, 1/2}(\mu, i)}{(1-x)^{d_{\mu, \varepsilon_0}(\varepsilon, x)}} \right. \\
&\qquad \left. \left( \sqrt{c(n-1, \delta)} + \sqrt{\tilde{f}_2(n)} \right)^2 \right\}, \\
\tilde{S}_{\mu, \varepsilon_0}(\varepsilon, x) &= \tilde{h}_1 \left( \frac{4(1+\gamma^{-1})}{a_{\mu, \varepsilon_0}(\varepsilon, x) v_{\mu, \varepsilon_0}(\varepsilon)} H_{\mu, \varepsilon_0}(\varepsilon), \frac{(1+\gamma^{-1})(3K^2/4+1)}{a_{\mu, \varepsilon_0}(\varepsilon, x) v_{\mu, \varepsilon_0}(\varepsilon)} + 1 \right),
\end{align*}
$$

with $\tilde{h}_1(z, y) > \sup \{n \ge 1 \mid n < z \tilde{f}_2(n) + y\}$. Using Lemma 49, we obtain that

$$
\begin{align*}
n \ge z \tilde{f}_2(n) + y &\iff \frac{n-y}{z} - \log(n-y) \ge s \log n + 2 \log(2+\log n) + 2 - \log z \\
&\iff \frac{n}{z(1+s)} - \log \frac{n}{z(1+s)} \ge \log(1+s) + \frac{s}{s+1} \log z + \frac{1}{1+s} \left(2 \log(2+\log n) + 2 + \frac{y}{z}\right).
\end{align*}
$$

Therefore, we can consider $\tilde{h}_1(z, y) \ge z(1 + s)h_2(z, y)$ with

$$
h_2(z, y) = \sup \left\{ x \mid x - \log x - \frac{2}{1+s} \log(\log x + 2 + \log(z(1+s))) < C(z, y) \right\}
$$

where $C(z, y) = \frac{y}{(1+s)z} + \frac{s}{s+1} \log z + \log(1+s) + \frac{2}{1+s}$. Therefore, we will obtain a multiplicative factor $(1+s)$ instead of $(2+s)$ in front of $H_{\mu, \varepsilon_0}(\varepsilon)$. This improvement is rather mild, hence we don't elaborate on it further.
F Probability of error and simple regret

Let $\varepsilon_0 > 0$ and $\beta \in (0, 1)$. In Appendix F, we provide an analysis on the probability of error and the simple regret of EB-TC$_{\varepsilon_0}$ with fixed proportions $\beta$ and slack $\varepsilon_0 > 0$ (Theorem 6 proved in Appendix F.1). In Appendix F.2, we provide an upper bound on the unverifiable expected sample complexity of EB-TC$_{\varepsilon_0}$ (Theorem 7). Then, by using Theorem 6, we prove that the policy pulling arm $\hat{i}_n$ at time $n$ has a constant induced regret (Corollary 2 proved in Appendix F.3). In practice, we will mostly be interested in the case $\beta = 1/2$.

Theorem 3 and Corollary 1 is a corollary of Theorem 6 up to some additional computations on the complexities $(H_i(\mu, \varepsilon_0))_{i \in [C_\mu - 1]}$, which we will detail below. Theorem 6 provides upper bound on $\mathbb{P}_\nu(\hat{i}_n \notin \mathcal{I}_\varepsilon(\mu))$ holding for any time $n$ and any error $\varepsilon \ge 0$, and upper bound on $\mathbb{E}_\nu[\mu_* - \mu_{\hat{i}_n}]$ holding for any time $n$.

**Theorem 6.** Let $\varepsilon_0 > 0$. For all $\varepsilon \ge 0$, let $i_\mu(\varepsilon) = i$ if $\varepsilon \in [\Delta_i, \Delta_{i+1})$ and $i \in [C_\mu - 1]$, otherwise $i_\mu(\varepsilon) = C_\mu$. For all $i \in [C_\mu - 1]$, let $C_i(\varepsilon_0) = 2\Delta_i^{-1} - \varepsilon_0^{-1}$ and $C_{i,j}(\varepsilon_0) = 2\frac{\Delta_j/\varepsilon_0+1}{\Delta_i-\Delta_j} + 3\varepsilon_0^{-1}$. For all $i \in [C_\mu - 1]$, let $H_i(\mu, \varepsilon_0) := \min_{j \in [i]} \max\{\tilde{H}_{i,j}(\mu, \varepsilon_0), \tilde{H}_{i,j}(\mu, \varepsilon_0)\}$ where

$$ \begin{aligned} \bar{H}_{i,j}(\mu, \varepsilon_0) &:= |i^*(\mu)| \max \left\{ \sqrt{2\Delta_{j+1}^{-1}}, C_{i+1,j}(\varepsilon_0) \right\}^2 \\ &\quad + \max \left\{ C_{j+1}(\varepsilon_0), C_{i+1,j}(\varepsilon_0) \right\}^2 \left( \sum_{k=2}^{j} |C_\mu(k)| + \sum_{k=i+1}^{C_\mu} |C_\mu(k)| \right) \\ &\quad + \sum_{k=j+1}^{i} |C_\mu(k)| \max \left\{ C_{j+1}(\varepsilon_0), C_{i+1,j}(\varepsilon_0), \sqrt{2\Delta_k^{-1}} \right\}^2, \end{aligned} $$

$$ \begin{aligned} \tilde{H}_{i,j}(\mu, \varepsilon_0) &:= \frac{2|i^*(\mu)|}{\Delta_{j+1}^2} + \max \{C_{j+1}(\varepsilon_0), \varepsilon_0^{-1}\}^2 \sum_{k=2}^{j} |C_\mu(k)| + \frac{2\sum_{k=1}^{j} |C_\mu(k)|}{(\Delta_{i+1} - \Delta_j)^2} \\ &\quad + \sum_{k=j+1}^{C_\mu} |C_\mu(k)| \max \{C_{j+1}(\varepsilon_0), \varepsilon_0^{-1}, \sqrt{2\Delta_k^{-1}}\}^2. \end{aligned} $$

The EB-TC$_{\varepsilon_0}$ algorithm with fixed proportions $\beta = 1/2$ satisfies that, for all $\nu \in \mathcal{D}^K$ and all $n \ge D_\mu$, if the algorithm has not stopped yet, then

$$ \begin{aligned} \forall \varepsilon \ge 0, \quad \mathbb{P}_\nu(\hat{i}_n \notin \mathcal{I}_\varepsilon(\mu)) &\le 1 (\varepsilon < \Delta_{\max}) \frac{K(K+1)}{2} e^2 (2 + \log n)^2 p\left(\frac{n - 5K^2/2}{8H_{i_\mu}(\mu, \varepsilon_0)}\right), \\ \mathbb{E}_\nu[\mu_* - \mu_{\hat{i}_n}] &\le \frac{K(K+1)}{2} e^2 (2 + \log n)^2 \sum_{i \in [C_\mu - 1]} (\Delta_{i+1} - \Delta_i) p\left(\frac{n - 5K^2/2}{8H_i(\mu, \varepsilon_0)}\right). \end{aligned} $$

where $p(x) = x \exp(-x)$ and $D_\mu = 8H_1(\mu, \varepsilon_0)h_2(8H_1(\mu, \varepsilon_0), 5K^2/2, 2 + \log(K(K+1)/2)) + 5K^2/2$ with $h_2$ defined in Lemma 51.

**Hardness of BAI** We have $C_2(\varepsilon_0) = 2\Delta_{\min}^{-1} - \varepsilon_0^{-1}$ and $C_{2,1}(\varepsilon_0) = 2\Delta_{\min}^{-1} + 3\varepsilon_0^{-1}$. Then, we obtain $H_1(\mu, \varepsilon_0) = \tilde{H}_{1,1}(\mu, \varepsilon_0) = K(2\Delta_{\min}^{-1} + 3\varepsilon_0^{-1})^2$ since

$$ \tilde{H}_{1,1}(\mu, \varepsilon_0) = 4|i^*(\mu)|\Delta_{\min}^{-2} + \sum_{k=2}^{C_\mu} |C_\mu(k)| \max \{C_2(\varepsilon_0), \varepsilon_0^{-1}, \sqrt{2}\Delta_k^{-1}\}^2. $$

This corresponds to the complexity of the two-groups instances which are defined as $\mathcal{D}_\Delta := \{\nu \in \mathcal{D}^K | C_\mu = 2, \Delta_2 = \Delta\}$ where $\Delta > 0$. More importantly, it corresponds to the complexity of identifying one of the best arms, i.e. taking $\varepsilon = 0$ yields

$$ \mathbb{P}_\nu(\hat{i}_n \notin i^*(\mu)) \le \frac{K(K+1)}{2} e^2 (2 + \log n)^2 p\left(\frac{n - 5K^2/2}{8K(2\Delta_{\min}^{-1} + 3\varepsilon_0^{-1})^2}\right). $$
**Hardness of ε-BAI** Let $i > 1$ and $j \in [i]$. We have $C_{i+1,j}(\epsilon_0) = 2\frac{\Delta_j/\epsilon_0+1}{\Delta_{i+1}-\Delta_j} + 3\epsilon_0^{-1}$, $C_{j+1}(\epsilon_0) = 2\Delta_{j+1}^{-1} - \epsilon_0^{-1} \le 2\Delta_{j+1}^{-1}$ and $\sqrt{2}\Delta_k^{-1} \le 2\Delta_{j+1}^{-1}$ for all $k \ge j + 1$. Direct manipulations show that, for all $i > 1$ and all $j \in [i]$, we have

$$ \max\{\bar{H}_{i,j}(\mu, \epsilon_0), \tilde{H}_{i,j}(\mu, \epsilon_0)\} \le K \max\left\{2\Delta_{j+1}^{-1}, 2\frac{\Delta_j/\epsilon_0 + 1}{\Delta_{i+1} - \Delta_j} + 3\epsilon_0^{-1}\right\}^2. $$

Therefore, we have

$$ H_i(\mu, \epsilon_0) \le K \min_{j \in [i]} \max \left\{ 2\Delta_{j+1}^{-1}, 2\frac{\Delta_j/\epsilon_0 + 1}{\Delta_{i+1} - \Delta_j} + 3\epsilon_0^{-1} \right\}^2. $$

Taking $j = 1$ and then $j = 2$, we see that, for all $i > 1$,

$$ H_i(\mu, \epsilon_0) \le K \max \left\{ 2\Delta_{\min}^{-1}, 3\epsilon_0^{-1} + 2\Delta_{i+1}^{-1} \right\}^2 < H_1(\mu, \epsilon_0), $$

$$ H_i(\mu, \epsilon_0) \le K \max \left\{ 2\Delta_3^{-1}, 2\frac{\Delta_{\min}/\epsilon_0 + 1}{\Delta_{i+1} - \Delta_{\min}} + 3\epsilon_0^{-1} \right\}^2 \le K \max \left\{ 2\frac{\Delta_{\min}/\epsilon_0 + 1}{\Delta_3 - \Delta_{\min}} + 3\epsilon_0^{-1} \right\}^2, $$

where the last inequality uses that $\Delta_3 \le \Delta_{i+1}$ for all $i > 1$.

Similarly, we can derive a lower bound on $H_i(\mu, \epsilon_0)$ by noting that $H_i(\mu, \epsilon_0) \ge \min_{j \in [i]} \bar{H}_{i,j}(\mu, \epsilon_0)$. For all $j \in [i]$, we have that $\sqrt{2}\Delta_{j+1}^{-1} \ge \sqrt{2}\Delta_{i+1}^{-1}$, $C_{j+1}(\epsilon_0) \ge 2\Delta_{i+1}^{-1} - \epsilon_0^{-1}$ and $C_{i+1,j}(\epsilon_0) \ge 2\Delta_{i+1}^{-1} + 3\epsilon_0^{-1}$, hence we obtain

$$ H_i(\mu, \epsilon_0) \ge \min_{j \in [i]} \bar{H}_{i,j}(\mu, \epsilon_0) \ge 2K \Delta_{i+1}^{-2}. $$

**Three-groups instances** The three-groups instances are defined as $\mathcal{D}_{\Delta, \Lambda} := \{\nu \in \mathcal{D}^K \mid C_\mu = 3, \Delta_2 = \Delta, \Delta_3 = \Lambda\}$ where $\Delta > 0$ and $\Lambda > \Delta$. Above results yield

$$ H_2(\mu, \epsilon_0) \le K \left( 2 \frac{\Delta/\epsilon_0 + 1}{\Lambda - \Delta} + 3\epsilon_0^{-1} \right)^2 = \mathcal{O} \left( \frac{K}{\min\{\Lambda - \Delta, \epsilon_0\}^2} \right). $$

## F.1 Proof of Theorem 6

In the following, we consider a sub-Gaussian bandit with distribution $\nu \in \mathbb{R}^K$ having mean parameter $\mu \in \mathbb{R}^K$. In particular, our analysis holds when several arms have the largest mean $\mu_*$.

Let $\Delta_{\max} = \max_{i \in [K]} \mu_* - \mu_i$. Let $\epsilon_1$ be an analysis parameter (i.e. not the error parameter from the stopping rule (3)). When $\epsilon_1 \ge \Delta_{\max}$, we have $\mathcal{I}_{\epsilon_1}(\mu)^c = \emptyset$, hence $\mathbb{P}_{\nu}(\hat{\mu}_n \notin \mathcal{I}_{\epsilon_1}(\mu)) = 0$. In the following, we consider $\epsilon_1 \in [0, \Delta_{\max})$.

For all $n > K$ and $\delta \in (0, 1)$, let $\tilde{\mathcal{E}}_{n,\delta} = \tilde{\mathcal{E}}_{n,\delta}^1 \cap \tilde{\mathcal{E}}_{n,\delta}^2$ with $(\tilde{\mathcal{E}}_{n,\delta}^1)_{n>K}$ and $(\tilde{\mathcal{E}}_{n,\delta}^2)_{n>K}$ as in (27) and (29) for $s = 0$, i.e.

$$ \tilde{\mathcal{E}}_{n,\delta}^1 = \left\{ \forall k \in [K], \forall t \le n, |\mu_{t,k} - \mu_k| < \sqrt{\frac{2\tilde{f}_1(n, \delta)}{N_{t,k}}} \right\}, $$

$$ \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\}, $$

where

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

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

Using Lemma 50, we know that $\tilde{f}_1(n, \delta) \le \tilde{f}_2(n, \delta)$. Using Lemmas 42 and 44, we obtain that $\mathbb{P}_{\nu}(\tilde{\mathcal{E}}_{n,\delta}^c) \le \frac{K(K+1)}{2}\delta$.
Suppose that we have constructed a time $T_{\varepsilon_1}(\delta) > K$ such that $\tilde{\mathcal{E}}_{n,\delta} \subseteq \{\hat{n}_n \in \mathcal{I}_{\varepsilon_1}(\mu)\}$ for $n > T_{\varepsilon_1}(\delta)$. Then, using Lemma 48, we obtain

$$ \mathbb{P}_{\nu}(\hat{n}_n \notin \mathcal{I}_{\varepsilon_1}(\mu)) \leq \frac{K(K+1)}{2} \inf\{\delta \mid n > T_{\varepsilon_1}(\delta)\}. $$

We will construct an infinite number of times $\{T_{\varepsilon_1}(\delta, \varepsilon)\}_{\varepsilon \in [0, \varepsilon_1]}$ such that the above property holds, hence taking the infimum yields

$$ \mathbb{P}_{\nu}(\hat{n}_n \notin \mathcal{I}_{\varepsilon_1}(\mu)) \leq \frac{K(K+1)}{2} \inf\{\delta \mid n > \inf_{\varepsilon \in [0, \varepsilon_1]} T_{\varepsilon_1}(\delta, \varepsilon)\}. $$

This proof strategy is the one used to prove Theorem 6.

Let $\varepsilon \in [0, \varepsilon_1]$. Since $\hat{n}_n = B_n^{\text{EB}}$, our goal is to construct a time $T_{\varepsilon_1}(\delta, \varepsilon)$ such that

$$ \forall n > T_{\varepsilon_1}(\delta, \varepsilon), \quad \tilde{\mathcal{E}}_{n,\delta} \cap \{B_n^{\text{EB}} \notin \mathcal{I}_{\varepsilon_1}(\mu)\} = \emptyset. $$

**Error due to undersampled arms** Let us denote by $U_{\varepsilon, \varepsilon_1, t}(n, \delta)$ the set of undersampled arms which are not $\varepsilon_1$-good, i.e.

$$ U_{\varepsilon, \varepsilon_1, t}(n, \delta) := \mathcal{I}_{\varepsilon_1}(\mu)^{\mathcal{G}} \cap \{i \mid N_{t,i} \leq 4C_{\varepsilon,i} \tilde{f}_2(n, \delta)\} \quad \text{with} \quad C_{\varepsilon,i} := \frac{2}{\min_{k \in \mathcal{I}_{\varepsilon}(\mu)} (\Delta_i - \Delta_k)^2}. $$

Lemma 35 shows that, for $n$ large enough, a necessary condition for an error to occur is to have an undersampled leader.

**Lemma 35.** Let $\varepsilon_1 > 0$ and $\varepsilon \in [0, \varepsilon_1]$. Let $H_{\mu, \varepsilon_0}(\varepsilon)$ as in Lemma 5 and define

$$ \tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0) := H_{\mu, \varepsilon_0}(\varepsilon) + \frac{2|\mathcal{I}_{\varepsilon}(\mu)|}{\min_{(i,j) \in \mathcal{I}_{\varepsilon}(\mu) \times \mathcal{I}_{\varepsilon_1}(\mu)^{\mathcal{G}}} (\Delta_j - \Delta_i)^2}. \quad (19) $$

Let us define

$$ S_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta) = \sup \left\{ n \mid n \leq \frac{4\tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)}{\min\{\beta, 1-\beta\}} \tilde{f}_2(n, \delta) + (3/2 + 1/\beta)K^2 \right\}. $$

For all $n > S_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$, under the event $\tilde{\mathcal{E}}_{n,\delta}$, we have $B_n^{\text{EB}} \notin \mathcal{I}_{\varepsilon_1}(\mu)$ implies that $B_n^{\text{EB}} \in U_{\varepsilon, \varepsilon_1, n}(n, \delta)$.

**Proof.** Let $|\mathcal{I}_{\varepsilon}(\mu)| = I_{\varepsilon}$ and $g_{\varepsilon, \varepsilon_0}(n, \delta) = \frac{4H_{\mu, \varepsilon_0}(\varepsilon)}{\min\{\beta, 1-\beta\}} \tilde{f}_2(n, \delta) + 3K(K-1)/2$. Using Lemma 5 and the pigeonhole principle, there exists $i_0 \in \mathcal{I}_{\varepsilon}(\mu)$ such that

$$ \sum_j T_n(i_0, j) \geq (n - 1 - g_{\varepsilon, \varepsilon_0}(n, \delta)) / I_{\varepsilon}. $$

Therefore, we have

$$ N_{n, i_0} \geq \beta \sum_j T_n(i_0, j) - (K-1) \geq \beta (n-1 - g_{\varepsilon, \varepsilon_0}(n, \delta)) / I_{\varepsilon} - (K-1). $$

Let $S_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$ defined as in the statement of Lemma 35. Direct manipulations shows that

$$ S_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta) \geq \sup \left\{ n \mid n-1 \leq g_{\varepsilon, \varepsilon_0}(n, \delta) + \frac{I_{\varepsilon}}{\beta} \left( 4\tilde{f}_2(n, \delta) \max_{i \notin \mathcal{I}_{\varepsilon_1}(\mu)} C_{\varepsilon, i} + K-1 \right) \right\}. $$

Therefore, we have $N_{n, i_0} > 4\tilde{f}_2(n, \delta) \max_{i \notin \mathcal{I}_{\varepsilon_1}(\mu)} C_{\varepsilon, i}$ for all $n > S_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$.

Let $n > S_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$. Suppose that $B_n^{\text{EB}} = i \notin \mathcal{I}_{\varepsilon_1}(\mu)$. Using Lemma 31, under the event $\tilde{\mathcal{E}}_{n,\delta}$, we obtain that

$$ \min\{N_{n,i}, N_{n,i_0}\} \leq \frac{8\tilde{f}_1(n, \delta)}{(\mu_{i_0} - \mu_i)^2} \leq 4C_{\varepsilon,i} \tilde{f}_2(n, \delta). $$

Suppose towards contradiction that $\min\{N_{n,i}, N_{n,i_0}\} = N_{n,i_0}$, then we have $N_{n,i_0} \leq 4C_{\varepsilon,i} \tilde{f}_2(n, \delta)$. This is a direct contradiction with $N_{n,i_0} > 4\tilde{f}_2(n, \delta) \max_{i \notin \mathcal{I}_{\varepsilon_1}(\mu)} C_{\varepsilon,i}$ since $n > S_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$. Therefore, we have shown that $\min\{N_{n,i}, N_{n,i_0}\} = N_{n,i}$, hence $i \in U_{\varepsilon, \varepsilon_1, n}(n, \delta)$. This concludes the proof. $\square$
**No remaining undersampled arms** Lemma 36 shows that, if there are still undersampled arms which are not $\varepsilon_1$-good, then either the leader or the challenger was not often selected as leader or challenger.

**Lemma 36.** Let $\varepsilon_1 \ge 0$ and $\varepsilon \in [0, \varepsilon_1]$. Let $\Delta_\mu(\varepsilon) = \min_{k \notin \mathcal{I}_\varepsilon(\mu)} \Delta_k$, $C_{\mu, \varepsilon_0}(\varepsilon, \varepsilon_1) = 2 \max_{j \notin \mathcal{I}_{\varepsilon_1}(\mu)} \frac{\Delta_j/\varepsilon_0 + 1}{\min_{k \in \mathcal{I}_\varepsilon(\mu)} (\Delta_j - \Delta_k)} + \varepsilon_0^{-1}$ and $C_{\mu, \varepsilon_0}(\varepsilon) = 2/\Delta_\mu(\varepsilon) - \varepsilon_0^{-1}$. Let $A_{\varepsilon, \varepsilon_1, \varepsilon_0, i} = \max\{2/\Delta_\mu(\varepsilon)^2, C_{\mu, \varepsilon_0}(\varepsilon, \varepsilon_1)^2\}$ for all $i \in i^*(\mu)$, $A_{\varepsilon, \varepsilon_1, \varepsilon_0, i} = \max\{C_{\mu, \varepsilon_0}(\varepsilon)^2, C_{\mu, \varepsilon_0}(\varepsilon, \varepsilon_1)^2\}$ for all $i \in (\mathcal{I}_\varepsilon(\mu) \setminus i^*(\mu)) \cup ([K] \setminus \mathcal{I}_{\varepsilon_1}(\mu))$, and otherwise $A_{\varepsilon, \varepsilon_1, \varepsilon_0, i} = \max\{C_{\mu, \varepsilon_0}(\varepsilon)^2, C_{\mu, \varepsilon_0}(\varepsilon, \varepsilon_1)^2, 2/\Delta_i^2\}$ for all $i \in \mathcal{I}_{\varepsilon_1}(\mu) \setminus \mathcal{I}_\varepsilon(\mu)$. For all $n > K$, under event $\tilde{\mathcal{E}}_{n, \delta}$, for all $t \in [n] \setminus [K]$ such that $U_{\varepsilon, \varepsilon_1, t}(n, \delta) \neq \emptyset$, there exists $i_t \in [K]$ such that

$$T_t(i_t) \le \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} A_{\varepsilon, \varepsilon_1, \varepsilon_0, i_t} + 3(K-1)/2 \quad \text{and} \quad T_{t+1}(i_t) = T_t(i_t) + 1.$$

*Proof.* We will be interested in three distinct cases since

$$\{U_{\varepsilon, \varepsilon_1, t}(n, \delta) \neq \emptyset\} = \{U_{\varepsilon, \varepsilon_1, t}(n, \delta) \cap \{B_t^{\mathrm{EB}}, C_t^{\mathrm{TC}}\} \neq \emptyset\} \\ \cup \{U_{\varepsilon, \varepsilon_1, t}(n, \delta) \neq \emptyset, U_{\varepsilon, \varepsilon_1, t}(n, \delta) \cap \{B_t^{\mathrm{EB}}, C_t^{\mathrm{TC}}\} = \emptyset, B_t^{\mathrm{EB}} \notin \mathcal{I}_{\varepsilon}(\mu)\} \\ \cup \{U_{\varepsilon, \varepsilon_1, t}(n, \delta) \neq \emptyset, U_{\varepsilon, \varepsilon_1, t}(n, \delta) \cap \{B_t^{\mathrm{EB}}, C_t^{\mathrm{TC}}\} = \emptyset, B_t^{\mathrm{EB}} \in \mathcal{I}_{\varepsilon}(\mu)\},$$

**Case 1.** Let $t \in [n] \setminus [K]$ such that $\{B_t^{\mathrm{EB}}, C_t^{\mathrm{TC}}\} \cap U_{\varepsilon, \varepsilon_1, t}(n, \delta) \neq \emptyset$. Let $k_t \in \{B_t^{\mathrm{EB}}, C_t^{\mathrm{TC}}\} \cap U_{\varepsilon, \varepsilon_1, t}(n, \delta)$. For this $k_t \notin \mathcal{I}_{\varepsilon_1}(\mu)$, we have $T_{t+1}(k_t) = T_t(k_t) + 1$ and, by combining Lemma 31 and $N_{t, k_t} \le 4C_{\varepsilon, k_t} \tilde{f}_2(n, \delta)$, we obtain that

$$T_t(k_t) \le \frac{N_{t,k_t}}{\min\{\beta, 1-\beta\}} + \frac{3(K-1)}{2} \le \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} C_{\varepsilon, k_t} + 3(K-1)/2.$$

**Case 2.** Let $t \in [n] \setminus [K]$ such that $U_{\varepsilon, \varepsilon_1, t}(n, \delta) \neq \emptyset$, $U_{\varepsilon, \varepsilon_1, t}(n, \delta) \cap \{B_t^{\mathrm{EB}}, C_t^{\mathrm{TC}}\} = \emptyset$ and $B_t^{\mathrm{EB}} \notin \mathcal{I}_{\varepsilon}(\mu)$. Let $\Delta_\mu(\varepsilon)$ and $C_{\mu, \varepsilon_0}(\varepsilon)$ defined as in the statement of Lemma 36. Let $D_{\varepsilon_0, \varepsilon, i} = 2/\Delta_\mu(\varepsilon)^2$ for all $i \in i^*(\mu)$, $D_{\varepsilon_0, \varepsilon, i} = C_{\mu, \varepsilon_0}(\varepsilon)$ for all $i \in \mathcal{I}_\varepsilon(\mu) \setminus i^*(\mu)$, otherwise $D_{\varepsilon_0, \varepsilon, i} = \max\{C_{\mu, \varepsilon_0}(\varepsilon), 2/\Delta_i^2\}$. Using Lemma 32, there exists $k_t \in [K]$ such that

$$T_t(k_t) \le \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} D_{\varepsilon, \varepsilon_0, k_t} + 3(K-1)/2 \quad \text{and} \quad T_{t+1}(k_t) = T_t(k_t) + 1.$$

**Case 3.** Let $t \in [n] \setminus [K]$ such that $U_{\varepsilon, \varepsilon_1, t}(n, \delta) \neq \emptyset$, $U_{\varepsilon, \varepsilon_1, t}(n, \delta) \cap \{B_t^{\mathrm{EB}}, C_t^{\mathrm{TC}}\} = \emptyset$ and $B_t^{\mathrm{EB}} \in \mathcal{I}_\varepsilon(\mu)$. Let $j_0 \in U_{\varepsilon, \varepsilon_1, t}(n, \delta) \setminus \{B_t^{\mathrm{EB}}, C_t^{\mathrm{TC}}\}$, which is possible since $U_{\varepsilon, \varepsilon_1, t}(n, \delta) \cap \{B_t^{\mathrm{EB}}, C_t^{\mathrm{TC}}\} = \emptyset$ and $U_{\varepsilon, \varepsilon_1, t}(n, \delta) \neq \emptyset$. Let us denote by $(B_t^{\mathrm{EB}}, C_t^{\mathrm{TC}}) = (i, j)$ with $i \in \mathcal{I}_\varepsilon(\mu)$ and $j \neq j_0$. Using the TC challenger, under the event $\mathcal{E}_{n, \delta}$, we obtain

$$\frac{\mu_i - \mu_{j_0} + \varepsilon_0}{\sqrt{1/N_{t,i} + 1/N_{t,j_0}}} + \sqrt{2\tilde{f}_2(n, \delta)} \ge \frac{\mu_{t,i} - \mu_{j_0} + \varepsilon_0}{\sqrt{1/N_{t,i} + 1/N_{t,j_0}}} \ge \frac{\mu_{t,i} - \mu_{j,j} + \varepsilon_0}{\sqrt{1/N_{t,i} + 1/N_{t,j}}} \\ \ge \varepsilon_0 \sqrt{\min\{N_{t,i}, N_{t,j}\}/2}.$$

Since $\mu_i - \mu_{j_0} + \varepsilon_0 \ge \varepsilon_0 > 0$, we have

$$\frac{\mu_i - \mu_{j_0} + \varepsilon_0}{\sqrt{1/N_{t,i} + 1/N_{t,j_0}}} \le \sqrt{N_{t,j_0}}(\mu_i - \mu_{j_0} + \varepsilon_0) + \sqrt{2\tilde{f}_2(n, \delta)} \\ \le \left(2 \frac{\mu_i - \mu_{j_0} + \varepsilon_0}{\min_{k \in \mathcal{I}_\varepsilon(\mu)} (\mu_k - \mu_{j_0})} + 1\right) \sqrt{2\tilde{f}_2(n, \delta)}.$$

Using Lemma 31 to lower bound $\min\{N_{t,i}, N_{t,j}\}$ and $\mu_i - \mu_{j_0} \le \Delta_{j_0}$ for all $i \in \mathcal{I}_\varepsilon(\mu)$, direct manipulation yields that

$$\min\{T_t(i), T_t(j)\} \le \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} C_{\mu, \varepsilon_0}(\varepsilon, \varepsilon_1)^2 + 3(K-1)/2.$$
where $C_{\mu,\varepsilon_0}(\varepsilon, \varepsilon_1)$ is defined as in the statement of Lemma 36. It is direct to see that $C_{\mu,\varepsilon_0}(\varepsilon, \varepsilon_1)^2 \ge \max\{1/\varepsilon_0^2, \max_{i \notin \mathcal{I}_{\varepsilon_1}(\mu)} C_{\varepsilon,i}\}$ and $C_{\varepsilon,i} \ge 2/\Delta_i^2$ for all $i \notin \mathcal{I}_{\varepsilon_1}(\mu)$. The above shows that there exists $k_t \in [K]$ such that

$$T_t(k_t) \le \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} C_{\mu,\varepsilon_0}(\varepsilon, \varepsilon_1)^2 + 3(K-1)/2 \quad \text{and} \quad T_{t+1}(k_t) = T_t(k_t) + 1.$$

**Summary.** Let us define $(A_{\varepsilon,\varepsilon_1,\varepsilon_0,i})_{i \in [K]}$ as in the statement of Lemma 36. Under $\tilde{\mathcal{E}}_{n,\delta}$, we have show that, when $U_{\varepsilon,\varepsilon_1,t}(n, \delta) \ne \emptyset$, there exists $i_t \in [K]$ such that

$$T_t(i_t) \le \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} A_{\varepsilon,\varepsilon_1,\varepsilon_0,i_t} + 3(K-1)/2 \quad \text{and} \quad T_{t+1}(i_t) = T_t(i_t) + 1.$$

□

Lemma 37 shows that, for $n$ large enough, there is no undersampled arms which are not $\varepsilon_1$-good.

**Lemma 37.** Let $\varepsilon_1 \ge 0$ and $\varepsilon \in [0, \varepsilon_1]$. Let $\Delta_\mu(\varepsilon)$, $C_{\mu,\varepsilon_0}(\varepsilon, \varepsilon_1)$ and $C_{\mu,\varepsilon_0}(\varepsilon)$ as in Lemma 36 and

$$\begin{aligned} \bar{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0) := & |i^*(\mu)| \max\{\sqrt{2}\Delta_\mu(\varepsilon)^{-1}, C_{\mu, \varepsilon_0}(\varepsilon, \varepsilon_1)\}^2 \\ & + |(\mathcal{I}_\varepsilon(\mu) \setminus i^*(\mu)) \cup ([K] \setminus \mathcal{I}_{\varepsilon_1}(\mu))| \max\{C_{\mu, \varepsilon_0}(\varepsilon), C_{\mu, \varepsilon_0}(\varepsilon, \varepsilon_1)\}^2 \\ & + \sum_{i \in \mathcal{I}_{\varepsilon_1}(\mu) \setminus \mathcal{I}_\varepsilon(\mu)} \max\{C_{\mu, \varepsilon_0}(\varepsilon), C_{\mu, \varepsilon_0}(\varepsilon, \varepsilon_1), \sqrt{2}\Delta_i^{-1}\}^2. \end{aligned} \quad (20)$$

Let us define

$$T_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta) = \sup \left\{ n \mid n \le \frac{4\bar{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)}{\min\{\beta, 1-\beta\}} \tilde{f}_2(n, \delta) + 3K^2/2 \right\}.$$

For all $n > T_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$, under the event $\tilde{\mathcal{E}}_{n,\delta}$, we have $U_{\varepsilon, \varepsilon_1, n}(n, \delta) = \emptyset$.

*Proof.* For all $n > K$, under event $\tilde{\mathcal{E}}_{n,\delta}$, combining Lemma 4 and 36 for $A_t(n, \delta) = \{U_{\varepsilon, \varepsilon_1, t}(n, \delta) \ne \emptyset\}$ and $D_i(n, \delta) = \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} A_{\varepsilon, \varepsilon_1, \varepsilon_0, i} + 3(K-1)/2$ yields that

$$\sum_{t=K+1}^{n} 1(U_{\varepsilon, \varepsilon_1, t}(n, \delta) \neq \emptyset) \leq \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} \bar{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0) + 3K(K-1)/2.$$

where we used that $\sum_{i \in [K]} A_{\varepsilon, \varepsilon_1, \varepsilon_0, i} = \bar{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)$ where $\bar{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)$ is defined in (20).

For all $i \notin \mathcal{I}_{\varepsilon_1}(\mu)$, let us define

$$t_i(n, \delta) = \max \{t \in [n] \setminus [K] \mid i \in U_{\varepsilon, \varepsilon_1, t}(n, \delta)\}.$$

By definition, for all $i \notin \mathcal{I}_{\varepsilon_1}(\mu)$, we have $i \in U_{\varepsilon, \varepsilon_1, t}(n, \delta)$ for all $t \in (K, t_i(n, \delta)]$ and $i \notin U_{\varepsilon, \varepsilon_1, t}(n, \delta)$ for all $t \in (t_i(n, \delta), n]$. Therefore, for all $t \in (K, \max_{i \notin \mathcal{I}_{\varepsilon_1}(\mu)} t_i(n, \delta)]$, we have $U_{\varepsilon, \varepsilon_1, t}(n, \delta) \ne \emptyset$ and $U_{\varepsilon, \varepsilon_1, t}(n, \delta) = \emptyset$ for all $t > \max_{i \notin \mathcal{I}_{\varepsilon_1}(\mu)} t_i(n, \delta)$, hence

$$\begin{aligned} \max_{i \notin \mathcal{I}_{\varepsilon_1}(\mu)} (t_i(n, \delta) - K) &= \sum_{t=K+1}^{n} 1(U_{\varepsilon, \varepsilon_1, t}(n, \delta) \neq \emptyset) \\ &\le \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} \bar{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0) + 3K(K-1)/2. \end{aligned}$$

Let $T_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$ defined as in the statement of Lemma 37. Direct manipulations show that

$$T_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta) \ge \sup \left\{ n \mid n - K \le \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} \bar{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0) + 3K(K-1)/2 \right\}.$$

Let $n > T_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$. Then, we have

$$n - K > \frac{4\tilde{f}_2(n, \delta)}{\min\{\beta, 1-\beta\}} \bar{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0) + 3K(K-1)/2 \ge \max_{i \notin \mathcal{I}_{\varepsilon_1}(\mu)} (t_i(n, \delta) - K),$$

hence $n > \max_{i \notin \mathcal{I}_{\varepsilon_1}(\mu)} t_i(n, \delta)$. This conclude the proof that $U_{\varepsilon, \varepsilon_1, n}(n, \delta) = \emptyset$.

□
**Upper bound probability of error** Let $S_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$ and $T_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$ as in Lemmas 35 and 37. For $\beta = 1/2$, direct manipulations show that $\max\{S_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta), T_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)\} \le E_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$ with

$$E_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta) := \sup \left\{ n \mid n \le 8 \max\{\tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0), \tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)\} \tilde{f}_2(n, \delta) + 5K^2/2 \right\}$$

Combining Lemmas 35 and 37, for all $n > E_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta)$, we proved that

$$\tilde{\mathcal{E}}_{n, \delta} \cap \{\hat{n} \notin \mathcal{I}_{\varepsilon_1}(\mu)\} = \tilde{\mathcal{E}}_{n, \delta} \cap \{B_n^{\text{EB}} \notin \mathcal{I}_{\varepsilon_1}(\mu)\} \subseteq \tilde{\mathcal{E}}_{n, \delta} \cap \{U_{\varepsilon, \varepsilon_1, n}(n, \delta) \neq \emptyset\} = \emptyset,$$

$$\text{hence } \{\hat{n} \notin \mathcal{I}_{\varepsilon_1}(\mu)\} \subseteq \tilde{\mathcal{E}}_{n, \delta}.$$

Using Lemma 48, $\mathbb{P}_{\nu}(\tilde{\mathcal{E}}_{n, \delta}^{\mathcal{C}}) \le K(K+1)\delta/2$ and taking the infimum over $\varepsilon \in [0, \varepsilon_1]$, yields

$$\mathbb{P}_{\nu}(\hat{n} \notin \mathcal{I}_{\varepsilon_1}(\mu)) \le \frac{K(K+1)}{2} \inf\{\delta \mid n > E_{\varepsilon_1, \varepsilon_0, \mu}(\delta)\}.$$

where we used Lemma 52 and $\inf_{\varepsilon \in [0, \varepsilon_1]} E_{\varepsilon, \varepsilon_1, \varepsilon_0, \mu}(\delta) = E_{\varepsilon_1, \varepsilon_0, \mu}(\delta)$ with

$$E_{\varepsilon_1, \varepsilon_0, \mu}(\delta) := \sup \left\{ n \mid n \le 8 \inf_{\varepsilon \in [0, \varepsilon_1]} \max\{\tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0), \tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)\} \tilde{f}_2(n, \delta) + 5K^2/2 \right\}.$$

Using Lemma 52, we obtain that

$$\mathbb{P}_{\nu}(\hat{n} \notin \mathcal{I}_{\varepsilon_1}(\mu)) \le 1 (\varepsilon_1 < \Delta_{C_{\mu}}) \frac{K(K+1)}{2} e^2 (2 + \log n)^2 \\ p\left(\frac{n - 5K^2/2}{8 \inf_{\varepsilon \in [0, \varepsilon_1]} \max\{\tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0), \tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)\}}\right),$$

where $p(x) = x \exp(-x)$.

**More explicit complexity** In order to obtain a more interpretable result, we notice that the dependence in $(\varepsilon, \varepsilon_1)$ of $\tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)$ and $\tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)$ is only with respect to its position in the ordered means. In the following, we will replace the dependency in $(\varepsilon, \varepsilon_1)$ by a dependency in such indices.

Let $\mu \in \mathbb{R}^K$. Let us denote by $C_\mu := |\{\mu_i \mid i \in [K]\}|$ the number of different arm means in $\mu$. For all $i \in [C_\mu]$, we denote the set of arms having mean gap $\Delta_i$ by $C_\mu(i) := \{k \in [K] \mid \mu_k - \mu_k = \Delta_i\}$ where the gaps are sorted by increasing order

$$0 = \Delta_1 < \Delta_2 < \dots < \Delta_{C_\mu}.$$

In particular, we have $C_\mu(1) = i^*(\mu)$ and $\Delta_{C_\mu} = \Delta_{\max}$. Let us denote by

$$\forall \varepsilon > 0, \quad i_{\mu}(\varepsilon) := \begin{cases} i & \text{if } \varepsilon \in [\Delta_i, \Delta_{i+1}) \text{ with } i \in [1, C_{\mu} - 1] \\ C_{\mu} & \text{if } \varepsilon \ge \Delta_{C_{\mu}} \end{cases}. \qquad (21)$$

It is direct to see that $i_\mu(\varepsilon) = \max\{i \in [C_\mu], C_\mu(i) \subset \mathcal{I}_\varepsilon(\mu)\}$ for all $\varepsilon > 0$. For all $i \in [C_\mu - 1]$, let us define $H_i(\mu, \varepsilon_0) = \min_{j \in [i]} \max\{\tilde{H}_{i,j}(\mu, \varepsilon_0), \tilde{H}_{i,j}(\mu, \varepsilon_0)\}$ with $\tilde{H}_{i,j}(\mu, \varepsilon_0)$ and $\tilde{H}_{i,j}(\mu, \varepsilon_0)$ as in Theorem 6. Let $\varepsilon_1 \ge 0$ and $\varepsilon \in [0, \varepsilon_1]$. Then, we have by direct manipulations that

$$\inf_{\varepsilon \in [0, \varepsilon_1]} \max\{\tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0), \tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)\} = H_{i_\mu(\varepsilon_1)}(\mu, \varepsilon_0),$$

since $\tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0) = \tilde{H}_{i_\mu(\varepsilon_1), i_\mu(\varepsilon)}(\mu, \varepsilon_0)$ and $\tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0) = \tilde{H}_{i_\mu(\varepsilon_1), i_\mu(\varepsilon)}(\mu, \varepsilon_0)$. This concludes the first part of Theorem 6, i.e.

$$\mathbb{P}_{\nu}(\hat{n} \notin \mathcal{I}_{\varepsilon_1}(\mu)) \le 1 (\varepsilon_1 < \Delta_{\max}) \frac{K(K+1)}{2} e^2 (2 + \log n)^2 p\left(\frac{n - 5K^2/2}{8H_{i_\mu(\varepsilon_1)}(\mu, \varepsilon_0)}\right).$$
**Simple regret** Since $\mu_{\star} - \mu_{\hat{i}_n}$ is a positive random variable, we obtain that

$$ \mathbb{E}_{\nu}[\mu_{\star} - \mu_{\hat{i}_n}] = \int_{\varepsilon_1=0}^{+\infty} \mathbb{P}_{\nu}(\mu_{\star} - \mu_{\hat{i}_n} > \varepsilon_1) \mathrm{d} \varepsilon_1 = \int_{\varepsilon_1=0}^{+\infty} \mathbb{P}_{\nu}(\hat{i}_n \notin \mathcal{I}_{\varepsilon_1}(\mu)) \mathrm{d} \varepsilon_1 . $$

As a function of $\varepsilon$, our upper bound on $\mathbb{P}_{\nu}(\hat{i}_n \notin \mathcal{I}_{\varepsilon_1}(\mu))$ is piecewise constant on $[\Delta_i, \Delta_{i+1})$ for all $i \in [C_{\mu} - 1]$ and has null value for $\varepsilon_1 \ge \Delta_{\max}$. Our upper is informative, i.e. smaller than 1, for all $n \ge D_{\mu}$ where

$$ D_{\mu} = 8H_{1}(\mu, \varepsilon_{0})h_{2}\left(8H_{1}(\mu, \varepsilon_{0}), 5K^{2}/2, 2 + \log\left(K(K + 1)/2\right) + 5K^{2}/2\right) \\ > \sup\left\{x \mid x < 8H_{1}(\mu, \varepsilon_{0})\overline{W}_{-1}\left(2\log\left(2 + \log x\right) + 2 + \log\left(K(K + 1)/2\right) + 5K^{2}/2\right)\right\}, $$

where the inequality is obtained by using Lemma 51, and $h_2$ is defined therein. Therefore, we obtain that, for all $n \ge D_{\mu}$,

$$ \mathbb{E}_{\nu}[\mu_{\star} - \mu_{\hat{i}_n}] \le \frac{K(K+1)}{2} e^2 (2 + \log n)^2 \sum_{i \in [C_{\mu}-1]} (\Delta_{i+1} - \Delta_i) p \left( \frac{n - 5K^2/2}{8H_i(\mu, \varepsilon_0)} \right), $$

which concludes the second part of Theorem 6.

## F.2 Unverifiable sample complexity

The $(\varepsilon, \delta)$-unverifiable sample complexity is defined as the expectation of the smallest stopping time $\tilde{\tau}$ satisfying $\mathbb{P}(\forall t \ge \tilde{\tau}, \hat{i}_n \in \mathcal{I}_{\varepsilon}(\mu)) \ge 1 - \delta$. Theorem 7 gives an upper bound on the unverifiable expected sample complexity of the EB-TC$_{\varepsilon_0}$ algorithm with fixed proportions $\beta = 1/2$.

**Theorem 7.** Let $\varepsilon_0 > 0$ and $\delta \in (0, 1)$. The EB-TC$_{\varepsilon_0}$ algorithm with fixed proportions $\beta = 1/2$ satisfies that, for all $\nu \in \mathcal{D}^K$ with mean $\mu$, for all $\varepsilon \ge 0$,

$$ \mathbb{P}_{\nu}(\forall n > U_{i_{\mu}(\varepsilon),\delta}(\mu, \varepsilon_0), \hat{i}_n \in \mathcal{I}_{\varepsilon}(\mu)) \ge 1 - \delta. $$

The times $U_{i_{\mu}(\varepsilon),\delta}(\mu, \varepsilon_0)$ are the $(\varepsilon, \delta)$-unverifiable sample complexity of EB-TC$_{\varepsilon_0}$ defined as

$$ \forall i \in [C_{\mu}-1], \quad U_{i,\delta}(\mu, \varepsilon_0) = h_2(\log(1/\delta), 8H_i(\mu, \varepsilon_0), 8H_i(\mu, \varepsilon_0) \log(K(K+1)/2) + 5K^2/2), \quad (22) $$

with $(H_i(\mu, \varepsilon_0))_{i \in [C_{\mu}-1]}$ defined in Theorem 6. The function $h_2(\log(1/\delta), A, B) = 2AW_{-1}(\frac{1}{2}\log(1/\delta) + \frac{B}{2A} + \log(2A))$ satisfies that $h_2(\log(1/\delta), A, B) =_{\delta \to 0} A \log(1/\delta) + O(\log \log(1/\delta))$.

**Proof.** In Appendix F.1, we consider the concentration event $\tilde{\mathcal{E}}_{n,\delta}$ that involved tighter concentration results with thresholds $\tilde{f}_1(n, \delta)$ and $\tilde{f}_2(n, \delta)$. Let $n > K$ and $\delta \in (0, 1)$. It is direct to see that the same argument holds for the concentration events $\mathcal{E}_{n,\delta} = \mathcal{E}_{n,\delta}^1 \cap \mathcal{E}_{n,\delta}^2$ with $(\mathcal{E}_{n,\delta}^1)_{n>K}$ and $(\mathcal{E}_{n,\delta}^2)_{n>K}$ as in (24) and (25) for $s = 0$, i.e.

$$ \mathcal{E}_{n,\delta}^1 = \left\{ \forall k \in [K], \forall t \le n, |\mu_{t,k} - \mu_k| < \sqrt{\frac{2f_1(n, \delta)}{N_{t,k}}} \right\}, $$

$$ \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{2f_2(n, \delta)} \right\}, $$

where $f_1(n, \delta) = \log(1/\delta) + \log n + \log(K(K+1)/2)$ and $f_2(n, \delta) = \log(1/\delta) + 2\log n + \log(K(K+1)/2)$, which satisfy $f_1(n, \delta) \le f_2(n, \delta)$. Using Lemmas 40 and 41, we obtain that $\mathbb{P}_{\nu}(\mathcal{E}_{n,\delta}^{\mathcal{C}}) \le \delta$.

In the following, we use the notation on the gaps introduced in Appendix F.1, the complexities $(H_i(\mu, \varepsilon_0))_{i \in [C_{\mu}-1]}$ defined in Theorem 6 and the function $i_{\mu}(\varepsilon)$ defined in (21). To prove Theorem 6, we obtain as an intermediary step that: for all $n > E_{\varepsilon_1, \varepsilon_0, \mu}(\delta)$, $\{\hat{i}_n \notin \mathcal{I}_{\varepsilon_1}(\mu)\} \subseteq \mathcal{E}_{n,\delta}^{\mathcal{C}}$, where

$$ \begin{aligned} E_{\varepsilon_1, \varepsilon_0, \mu}(\delta) &:= \sup \left\{ n \mid n \le 8 \inf_{\varepsilon \in [0, \varepsilon_1]} \max\{\tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0), \tilde{H}_{\varepsilon, \varepsilon_1}(\mu, \varepsilon_0)\} f_2(n, \delta) + 5K^2/2 \right\} \\ &= \sup \left\{ n \mid n \le 8H_{i_{\mu}(\varepsilon_1)} f_2(n, \delta) + 5K^2/2 \right\}, \end{aligned} $$
where the equality holds by using the rewriting of the complexities done in the end of Appendix F.1.

Let $A = 8H_{i_\mu(\varepsilon_1)}$ and $B = 8H_{i_\mu(\varepsilon_1)} \log(K(K+1)/2) + 5K^2/2$. Using a proof similar to Lemma 51, applying Lemma 49 yields that

$$ 
\begin{align*}
n > E_{\varepsilon_1, \varepsilon_0, \mu}(\delta) &\iff n > 2A \log n + A \log(1/\delta) + B \\
&\iff \frac{n}{2A} - \log\left(\frac{n}{2A}\right) > \frac{1}{2} \log(1/\delta) + \frac{B}{2A} + \log(2A) \\
&\iff n > 2A \overline{W}_{-1} \left( \frac{1}{2} \log(1/\delta) + \frac{B}{2A} + \log(2A) \right),
\end{align*}
$$

Let us define $h_2(\log(1/\delta), A, B) = 2A\overline{W}_{-1}(\frac{1}{2}\log(1/\delta) + \frac{B}{2A} + \log(2A))$ and, for all $i \in [C_\mu - 1]$, we define

$$ U_{i,\delta}(\mu, \varepsilon_0) = h_2(\log(1/\delta), 8H_i(\mu, \varepsilon_0), 8H_i(\mu, \varepsilon_0) \log(K(K+1)/2) + 5K^2/2). $$

Therefore, we have shown that, for all $\varepsilon_1 \ge 0$,

$$ \{\exists n > U_{i_\mu(\varepsilon_1),\delta}(\mu, \varepsilon_0), \hat{i}_n \notin \mathcal{I}_{\varepsilon_1}(\mu)\} \subseteq \mathcal{E}_{n,\delta}^{\mathcal{C}} $$

Using that $\mathbb{P}_\nu(\mathcal{E}_{n,\delta}^{\mathcal{C}}) \le \delta$, we can conclude that, for all $\varepsilon_1 \ge 0$,

$$ \mathbb{P}_\nu(\forall n > U_{i_\mu(\varepsilon_1),\delta}(\mu, \varepsilon_0), \hat{i}_n \in \mathcal{I}_{\varepsilon_1}(\mu)) \ge 1 - \delta. $$

□

### F.3 Cumulative regret of induced policy

Given a stream of recommendations $(\hat{i}_n)_{n>K}$, an external agent aiming at minimizing its cumulative regret can simply pull the arm $\hat{i}_n$ at time $n$. Since the EB-TCa algorithm has anytime guarantees on the simple regret of this recommendation, the regret of the induced policy is constant (Corollary 2).

**Corollary 2.** Let $\varepsilon_0 > 0$. Let $(\hat{i}_n)_{n>K}$ be the recommendations of the EB-TC$_{\varepsilon_0}$ algorithm with fixed proportions $\beta = 1/2$. An agent pulling $\hat{i}_n$ at time $n$ has constant induced regret, i.e.

$$ \forall \nu \in \mathcal{D}^K, \forall T > K, \quad \sum_{n=K+1}^{T} \mathbb{E}_{\nu}[\mu_{\star} - \mu_{\hat{i}_n}] = \mathcal{O} \left( \frac{K^3 \Delta_{\max}}{\min\{\Delta_{\min}, \varepsilon_0\}^2} \left( \log \frac{K}{\min\{\Delta_{\min}, \varepsilon_0\}^2} \right)^2 \right). $$

*Proof.* Using that $H_1(\mu, \varepsilon_0) = \max_{i \in [C_\mu - 1]} H_i(\mu, \varepsilon_0)$, a direct upper bound based on Corollary 1 yields that, for all $n \ge D_\mu$,

$$ \mathbb{E}_{\nu}[\mu_{\star} - \mu_{\hat{i}_n}] \le \frac{K(K+1)}{2} e^2 (2 + \log n)^2 \Delta_{\max} \frac{n - 5K^2/2}{8H_1(\mu, \varepsilon_0)} \exp \left( - \frac{n - 5K^2/2}{8H_1(\mu, \varepsilon_0)} \right). $$

Let $c > 0$. Let $f(c, x) = (c + \log(x))^2 x \exp(-x)$ for all $x \ge 1$. Let $A > 0, B > 0$. By integration, for all $C \ge A + B$, we obtain

$$ \sum_{n=C}^{T} f(c, (n-B)/A) \le A \int_{1}^{+\infty} f(c, x) dx = A(c^2 + 2cC_1 + C_2). $$

where $C_\alpha = \int_1^{+\infty} \log(x)^\alpha \exp(-x) dx < +\infty$ for all $\alpha \ge 0$. For $n \ge 5K^2$, we have $n \le 2(n - 5K^2/2)$. Recall that $D_\mu = 8H_1(\mu, \varepsilon_0)h_2(8H_1(\mu, \varepsilon_0), 5K^2/2, 2 + \log(K(K+1)/2)) + 5K^2/2$ with $h_2$ defined in Lemma 51. For all $n < 5K^2/2 + D_\mu$, we have trivially that $\mathbb{E}_{\nu}[\mu_{\star} - \mu_{\hat{i}_n}] \le \Delta_{\max}$. Therefore, we obtain

$$ 
\begin{align*}
\sum_{n=K+1}^{T} \mathbb{E}_{\nu}[\mu_{\star} - \mu_{\hat{i}_n}] &\le (5K^2/2 + D_{\mu})\Delta_{\max} + \frac{K(K+1)}{2}e^2\Delta_{\max} \\
&\quad + \sum_{n=5K^2+8H_1(\mu, \varepsilon_0)}^{T} f\left(2 + \log(16H_1(\mu, \varepsilon_0)), \frac{n-5K^2/2}{8H_1(\mu, \varepsilon_0)}\right) \\
&\le (5K^2/2 + D_{\mu})\Delta_{\max} + \frac{K(K+1)}{2}e^2\Delta_{\max} \\
&\quad + 8H_1(\mu, \varepsilon_0)\left((2 + \log(16H_1(\mu, \varepsilon_0)))^2 + 2C_1(2 + \log(16H_1(\mu, \varepsilon_0))) + C_2\right).
\end{align*}
$$
Studying the function $h_2(x, y, z)$, it is direct to see that $h_2(x, y, z) =_{x \to +\infty} o(\log(x)^\alpha)$ for all $\alpha > 0$, hence $\Delta_{\max} D_\mu$ is dominated by the other term. Therefore, by studying the dominating term when $\min\{\Delta_{\min}, \varepsilon_0\} \to 0$, our upper bound scales as

$$ \mathcal{O} (K^2 \Delta_{\max} H_1(\mu, \varepsilon_0) (\log H_1(\mu, \varepsilon_0))^2) = \mathcal{O} \left( \frac{K^3 \Delta_{\max}}{\min\{\Delta_{\min}, \varepsilon_0\}^2} \left( \log \frac{K}{\min\{\Delta_{\min}, \varepsilon_0\}^2} \right)^2 \right), $$

where we used that $H_1(\mu, \varepsilon_0) = K(2\Delta_{\min}^{-1} + 3\varepsilon_0^{-1})^2 = \mathcal{O} \left( \frac{K}{\min\{\Delta_{\min}, \varepsilon_0\}^2} \right)$. $\square$

The idea of decoupling exploration and exploitation when minimizing the regret in the multi-armed bandits literature was introduced by [2]. At each round, the agent is allowed to choose one arm to explore and one arm to exploit at every round. While the agent suffers the loss from the exploited arm, it observes the one of the explored arm without cost. In the stochastic regime for instances having a unique best arm, the Decoupled-Tsallis-INF algorithm [33] achieves a constant regret $\mathcal{O}(K/\Delta_{\min})$. Therefore, in this setting, our constant regret in Corollary 2 does have the best achievable scaling in $K$ and $\Delta_{\min}$.

**Beyond synchronized policy** When the external agent plays $\hat{\imath}_n$ at time $n$, it is said to be synchronized with the recommendation rule. In all generality, one could pull arm $\hat{\imath}_{\mathcal{L}(n)}$ at time $n$, where $\mathcal{L}: \mathbb{N} \to \mathbb{N}$ is a non-decreasing function, and obtain similar guarantees as Corollary 2. The agent can be slower than the recommendation rule (e.g. offline hyper-parameter optimization) hence $\mathcal{L}$ can be rapidly increasing, e.g. $\mathcal{L}(n) = Bn + K$ where $B > 1$. The recommendation rule can be slower than the agent (e.g. pulling the same arm multiple times) hence $\mathcal{L}$ can be piecewise constant with small steps, e.g. $\mathcal{L}(n) = \lceil n/B \rceil + K$. The communication between the agent and the recommendation rule can happen infrequently (e.g. paying to access the recommendation) hence $\mathcal{L}$ can be piecewise constant with large steps, e.g. $\mathcal{L}(n) = (\lceil n/B \rceil)^\alpha + K$ where $\alpha > 1$.

# G Concentration results

The proof of Lemma 3 is given in Appendix G.1. Appendix G.2 gathers concentration results to control the empirical means and gaps.

## G.1 Proof of Lemma 3

Proving that a GLR stopping rule ensures the algorithm to be $(\varepsilon_1, \delta)$-PAC is done by leveraging concentration results. In particular, we build upon Theorem 9 of [27] which is restated below. While Theorem 9 was only stated for Gaussian distributions, it is direct to notice that the result also holds for sub-Gaussian distributions with variance proxy $\sigma^2 = 1$ (as the authors mentioned).

**Lemma 38 (Theorem 9 of [27]).** Consider a sub-Gaussian bandit $\nu$ with means $\mu \in \mathbb{R}^K$. Let $S \subseteq [K]$ and $x > 0$.

$$ \mathbb{P}_{\nu} \left[ \exists n \in \mathbb{N}, \sum_{k \in S} \frac{N_{n,k}}{2} (\mu_{n,k} - \mu_k)^2 > \sum_{k \in S} 2 \log (4 + \log (N_{n,k})) + |S| \mathcal{C}_G \left( \frac{x}{|S|} \right) \right] \le e^{-x} $$

where $\mathcal{C}_G$ is defined in [27] by $\mathcal{C}_G(x) = \min_{\lambda \in [1/2, 1]} \frac{g_G(\lambda) + x}{\lambda}$ and

$$ g_G(\lambda) = 2\lambda - 2\lambda \log(4\lambda) + \log \zeta(2\lambda) - \frac{1}{2} \log(1 - \lambda), \quad (23) $$

where $\zeta$ is the Riemann $\zeta$ function and $\mathcal{C}_G(x) \approx x + \log(x)$.

Since $\hat{\imath}_n = i^*(\mu_n)$, standard manipulations yield that for all $i \ne \hat{\imath}_n$

$$ \frac{(\mu_{n,\hat{\imath}_n} - \mu_{n,i} + \varepsilon_1)^2}{1/N_{n,\hat{\imath}_n} + 1/N_{n,i}} = \inf_{u \in \mathbb{R}} \left( N_{n,\hat{\imath}_n} (\mu_{n,\hat{\imath}_n} - u)^2 + N_{n,i} (\mu_{n,i} - u - \varepsilon_1)^2 \right) \\ = \inf_{y \ge x + \varepsilon_1} \left( N_{n,\hat{\imath}_n} (\mu_{n,\hat{\imath}_n} - x)^2 + N_{n,i} (\mu_{n,i} - y)^2 \right). $$
Let $i^* = i^*(\mu)$. Using the stopping rule (3) and the above manipulations, we obtain

$$
\begin{align*}
& \mathbb{P}_{\nu} (\tau_{\varepsilon_1, \delta} < +\infty, \hat{i}_{\tau_{\varepsilon_1, \delta}} \notin \mathcal{I}_{\varepsilon_1}(\mu)) \\
& \le \mathbb{P}_{\nu} (\exists n \in \mathbb{N}, \exists i \notin \mathcal{I}_{\varepsilon_1}(\mu), i = i^*(\mu_n), \\
& \qquad \min_{k \ne i} \inf_{y \ge x + \varepsilon_1} (N_{n, \hat{i}_n}(\mu_{n, \hat{i}_n} - x)^2 + N_{n, i}(\mu_{n, i} - y)^2) \ge 2c(n-1, \delta)) \\
& \le \mathbb{P}_{\nu} (\exists n \in \mathbb{N}, \exists i \notin \mathcal{I}_{\varepsilon_1}(\mu), i = i^*(\mu_n), \\
& \qquad \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)) \\
& \le \sum_{i \notin \mathcal{I}_{\varepsilon_1}(\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{align*}
$$

where the second inequality is obtained with $(k, x, y) = (i^*, \mu_i, \mu_{i^*})$ since $i \notin \mathcal{I}_{\varepsilon_1}(\mu)$, and the third
by union bound. By concavity of $x \mapsto \log(4 + \log(x))$ and $N_{n,i^*} + N_{n,i} \le \sum_{k \in [K]} N_{n,k} = n-1$,
we obtain

$$
\forall i \notin \mathcal{I}_{\varepsilon_1}(\mu), \quad \log(4 + \log N_{n,i^*}) + \log(4 + \log N_{n,i}) \le 2 \log(4 + \log((n-1)/2))
$$

Combining the above with Lemma 38 for all $i \notin \mathcal{I}_{\varepsilon_1}(\mu)$ and using that $|\mathcal{I}_{\varepsilon_1}(\mu)| \le K - 1$, we obtain

$$
\mathbb{P}_{\nu} (\tau_{\delta} < +\infty, \hat{i}_{\tau_{\delta}} \notin \mathcal{I}_{\varepsilon_1}(\mu)) \leq \sum_{i \notin \mathcal{I}_{\varepsilon_1}(\mu)} \frac{\delta}{K-1} \leq \delta.
$$

**G.2 Sequence of concentration events**

Lemma 39 is a standard concentration result for sub-Gaussian distribution, hence we omit the proof.

**Lemma 39.** Let $X$ be an observation from a sub-Gaussian distribution with mean 0 and variance proxy $\sigma^2$. Then, for all $\delta \in (0, 1]$,

$$
\mathbb{P}_X \left( |X| \ge \sigma \sqrt{2 \log(1/\delta)} \right) \le \delta .
$$

Lemma 40 gives a sequence of concentration events under which the empirical means are close to their true values.

**Lemma 40.** Let $\delta \in (0, 1]$ and $s \ge 0$. For all $n > K$, let $f_1(x, \delta) = \log(1/\delta) + (1+s) \log x$ and

$$
\mathcal{E}_{n, \delta}^{1} := \left\{ \forall k \in [K], \forall t \le n, |\mu_{t,k} - \mu_k| < \sqrt{\frac{2f_1(n, \delta)}{N_{t,k}}} \right\}. \quad (24)
$$

$$
\text{Then, for all } n > K, \mathbb{P}_{\nu}((\mathcal{E}_{n,\delta}^1)^c) \le \frac{K\delta}{n^s}.
$$

Proof. Let $(X_s)_{s \in [n]}$ be i.i.d. observations from one sub-Gaussian distribution with mean 0 and variance proxy $\sigma^2 = 1$. Then, $\frac{1}{m} \sum_{i=1}^m X_i$ is sub-Gaussian with mean 0 and variance proxy $\sigma^2 = 1/m$. By union bound over $[K]$ and over $m \in [n]$, we obtain

$$
\begin{align*}
& \mathbb{P}_{\nu} \left( \exists k \in [K], \exists t \le n, |\mu_{t,k} - \mu_k| \ge \sqrt{\frac{2f_1(n, \delta)}{N_{t,k}}} \right) \\
\le & \sum_{k \in [K]} \sum_{m \in [n]} \mathbb{P} \left( \left| \frac{1}{m} \sum_{s \in [m]} X_s \right| \ge \sqrt{\frac{2f_1(n, \delta)}{m}} \right) \\
\le & \delta \sum_{k \in [K]} \sum_{m \in [n]} n^{-(1+s)} = K \delta n^{-s},
\end{align*}
$$

where we used that $\mu_{t,k} - \mu_k = \frac{1}{N_{t,k}} \sum_{s=1}^t \mathbb{1}(I_s = k) X_{s,k}$ and concentration results for sub-Gaussian observations (Lemma 39). $\square$
Lemma 41 gives a sequence of concentration events under which the empirical gaps are close to their true values.

**Lemma 41.** Let $\delta \in (0, 1]$ and $s \ge 0$. For all $n > K$, let $f_2(x, \delta) = \log(1/\delta) + (2+s) \log(x)$ and

$$ \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{2f_2(n, \delta)} \right\}. \quad (25) $$

Then, for all $n > K$, $\mathbb{P}_\nu((\mathcal{E}_{n,\delta}^2)^\mathcal{C}) \le \frac{K(K-1)\delta}{2n^s}$.

*Proof.* Let $(X_s)_{s \in [n]}$ and $(Y_s)_{s \in [n]}$ be two streams of i.i.d. observations from two sub-Gaussian distributions with mean 0 and variance proxy $\sigma^2 = 1$. Then, $\frac{1}{m_1} \sum_{i=1}^{m_1} X_i - \frac{1}{m_2} \sum_{i=1}^{m_2} Y_i$ is sub-Gaussian with mean 0 and variance proxy $\sigma^2 = \frac{1}{m_1} + \frac{1}{m_2}$. By union bound, we obtain

$$ \begin{aligned} & \mathbb{P}_\nu \left( \exists (i, k) \in [K]^2 \text{ s.t. } i \neq k, \exists t \le n, \left| \frac{(\mu_{t,i} - \mu_{t,k}) - (\mu_i - \mu_k)}{\sqrt{1/N_{t,i} + 1/N_{t,k}}} \right| \le \sqrt{2f_2(n, \delta)} \right) \\ & \le \sum_{(i,k) \in [K]^2, i \neq k} \sum_{(m_1, m_2) \in [n]^2} \mathbb{P} \left( \left| \frac{1}{m_1} \sum_{i=1}^{m_1} X_i - \frac{1}{m_2} \sum_{i=1}^{m_2} Y_i \right| \le \sqrt{2f_2(n, \delta) (1/m_1 + 1/m_2)} \right) \\ & \le \delta \sum_{(i,k) \in [K]^2, i \neq k} \sum_{(m_1, m_2) \in [n]^2} n^{-(2+s)} = \frac{K(K-1)}{2} \delta n^{-s}, \end{aligned} $$

where we used that $(\mu_{t,i^*} - \mu_{i^*}) - (\mu_{t,k} - \mu_k) = \frac{1}{N_{t,i^*}} \sum_{s=1}^t 1(I_s = i^*) X_{s,i^*} - \frac{1}{N_{t,k}} \sum_{s=1}^t 1(I_s = k) X_{s,k}$ and concentration results for sub-Gaussian observations (Lemma 39). $\square$

**Tighter concentration** Lemma 42 provides concentration results on the empirical means, which are tighter than the one obtained in Lemma 40.

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

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

and

$$ \tilde{\mathcal{E}}_{n, \delta}^1 = \left\{ \forall k \in [K], \forall t \le n, |\mu_{t,k} - \mu_k| < \sqrt{\frac{2\tilde{f}_1(n, \delta)}{N_{t,k}}} \right\}. \quad (27) $$

Then, for all $n > K$, $\mathbb{P}_\nu((\tilde{\mathcal{E}}_{n,\delta}^1)^\mathcal{C}) \le \frac{K\delta}{n^s}$.

*Proof.* Let $(X_s)_{s \in [n]}$ be i.i.d. observations from one sub-Gaussian distribution with mean 0 and variance proxy $\sigma^2 = 1$. Let $S_t = \sum_{s \in [t]} X_s$. To derived concentration result, we use peeling.

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

$$ \overline{M}(t) = \sum_{i \in [D]} w_i \int f_{N_i, \gamma}(x) \exp \left( xS_t - \frac{1}{2}x^2t \right) dx, $$

which satisfies $\overline{M}(0) = 1$. It is direct to see that $M(t) = \exp(xS_t - \frac{1}{2}x^2t)$ is a non-negative supermartingale since sub-Gaussian distributions with mean 0 and variance proxy $\sigma^2 = 1$ satisfy

$$ \forall \lambda \in \mathbb{R}, \quad \mathbb{E}_X[\exp(sX)] \le \exp(\lambda^2/2). $$

By Tonelli's theorem, then $\overline{M}(t)$ is also a non-negative supermartingale of unit initial value.