Marc Jourdan
email: marc.jourdan@inria.fr

Rémy Degenne
email: remy.degenne@inria.fr

Emilie Kaufmann
email: emilie.kaufmann@univ-lille.fr

An ε-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond

We propose EB-TC ε , a novel sampling rule for ε-best arm identification in stochastic bandits. It is the first instance of Top Two algorithm analyzed for approximate best arm identification. EB-TC ε 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 ε . 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 ε performs favorably compared to existing algorithms, in different settings.

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 [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF][START_REF] Lattimore | Bandit Algorithms[END_REF], in which a learner interacts sequentially with an environment composed of K ∈ N arms, which are unknown distributions (ν i ) i∈ [K] with finite means (µ i ) i∈ [K] . At each stage n ∈ N, the learner chooses an arm I n ∈ [K] based on the samples previously observed and receives a sample X n,In , random variable with conditional distribution ν In 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 ∈ N a function from ([K] × R) n-1 to the probability distribution on [K], which is measurable with respect to the σ-algebra F n := σ({I t , X t,It } t∈ [n-1] ). We call that σ-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 µ -ε, where µ = max i∈[K] µ i . This is the ε-BAI task. Our results can also be adapted to the multiplicative ε-BAI task, in which all means are non-negative and we want to find an arm with mean µ i ≥ (1 -ε)µ [START_REF] Jourdan | Choosing answers in ε-best-answer identification for linear bandits[END_REF] (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 [START_REF] Bubeck | Pure Exploration in Finitely Armed and Continuous Armed Bandits[END_REF] and define that rule for all stages: for all n ∈ N, we denote by în this F n -measurable function from ([K] × 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 ε-BAI. Let I ε (µ) = {i ∈ [K] | µ i ≥ µ -ε} be the set of ε-good arms. The probability of ε-error or the recommendation at n is defined as P ν (î n / ∈ I ε (µ)). Introduced in [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF], the expected simple regret is defined as E ν [µ -µ în ], and is independent of any parameter ε. 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 τ ε,δ with respect to the history of samples and we impose that the algorithm should be (ε, δ)-PAC.

That is, its probability of ε-error at τ ε,δ must satisfy P ν (τ ε,δ < +∞, îτ ε,δ / ∈ I ε (µ)) ≤ δ. The parameter δ is known to the algorithm. An algorithm is judged based on its expected sample complexity E[τ ε,δ ], 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 ε = 0 [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF][START_REF] Karnin | Almost optimal Exploration in multi-armed bandits[END_REF], but [START_REF] Zhao | Revisiting simple regret: Fast rates for returning a good arm[END_REF] present the first bounds for ε > 0 for an algorithm that is actually agnostic to this value.

• Simple regret minimization: we evaluate the expected simple regret at T [START_REF] Bubeck | Pure Exploration in Finitely Armed and Continuous Armed Bandits[END_REF][START_REF] Zhao | Revisiting simple regret: Fast rates for returning a good arm[END_REF].

Simple regret is typically studied in an anytime setting: [START_REF] Bubeck | Pure Exploration in Finitely Armed and Continuous Armed Bandits[END_REF] contains upper bounds on the simple regret at time n for any n ∈ N * . Similarly, [START_REF] Jun | Anytime exploration for multi-armed bandits using confidence information[END_REF] propose the anytime exploration setting, in which they control the error probability P (î n = i ) for exact best arm identification. Interestingly, the authors build on an algorithm for the fixed-confidence setting, LUCB [START_REF] Kalyanakrishnan | PAC subset selection in stochastic multi-armed bandits[END_REF], whose sampling rule depends on the risk parameter δ, which they replace by a sequence δ n . The algorithm that we study in this paper, motivated by the fixed-confidence ε-BAI problem, will already be anytime, which means that it does not depend on a given final time T or a confidence level δ. 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 ε-error for every ε ≥ 0 and its simple regret at any time.

Additional notation and assumption

We denote by D a set to which the distributions of the arms are known to belong. We suppose that all distributions in D are 1-sub-Gaussian. A distribution ν 0 is 1-sub-Gaussian if it satisfies E X∼ν0 [e λ(X-E X∼ν 0 [X]) ] ≤ e λ 2 /2 for all λ ∈ R. For example, all distributions bounded in [-1, 1] are 1-sub-Gaussian. Let us denote by i (µ) := arg max i∈[K] µ i the set of arms with largest mean (i.e. i (µ) = I 0 (µ)). Let ∆ i := µ -µ i denote the sub-optimality gap of arm i. We denote by K ⊂ R K the simplex of dimension K -1.

Fixed-confidence ε-best-arm identification Let ε ≥ 0 and δ ∈ (0, 1) be fixed error and confidence parameters. In the fixed-confidence ε-BAI setting [START_REF] Mannor | The Sample Complexity of Exploration in the Multi-Armed Bandit Problem[END_REF][START_REF] Even-Dar | Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems[END_REF][START_REF] Sabato | Epsilon-best-arm identification in pay-per-reward multi-armed bandits[END_REF][START_REF] Garivier | Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models[END_REF], the probability of error of an algorithm is required to be less than δ for all instances ν ∈ D K . That requirement leads to an asymptotic lower bound on the expected sample complexity on any instance.

Lemma 1 ( [START_REF] Degenne | Pure exploration with multiple correct answers[END_REF]). For all (ε, δ)-PAC algorithms and all instances ν i = N (µ i , 1) with µ ∈ R K , lim inf δ→0

Eν [τ ε,δ ] log(1/δ) ≥ T ε (µ) where T ε (µ) = min i∈Iε(µ) min β∈(0,1) T ε,β (µ, i) with

T ε,β (µ, i) -1 = max w∈ K ,wi=β min j =i 1 2
(µ i -µ j + ε) 2 1/β + 1/w j .

We say that an algorithm is asymptotically (resp. β-)optimal if its sample complexity matches that lower bound, that is if lim sup δ→0

Eν [τ ε,δ ] log(1/δ) ≤ T ε (µ) (resp. T ε,β (µ) = min i∈Iε(µ) T ε,β (µ, 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 ε,1/2 (µ) ≤ 2T ε (µ) [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF].

The asymptotic characteristic time T ε (µ) is of order

K i=1 min{ε -2 , ∆ -2 i }.
It is computed as a minimum over all ε-good arms i ∈ I ε (µ) of an arm-specific characteristic time, which can be interpreted as the time required to verify that i is ε-good. Each of the times min β∈(0,1) T ε,β (µ, i) correspond to the complexity of a BAI instance (i.e. ε-BAI with ε = 0) in which the mean of arm i is increased by ε (Lemma 9). Let w ε,β (µ, i) be the maximizer of [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF]. In [START_REF] Garivier | Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models[END_REF], they show that T ε (µ) = T ε,β (i ) (µ, i ) and T ε,β (µ) = T ε,β (µ, i ), where i ∈ i (µ) and β (i ) = arg min β∈(0,1) T ε,β (µ, i ). For ε = 0, a similar lower bound to Lemma 1 holds for all δ [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]. Lower bounds of order K i=1 ∆ -2 i log log ∆ -2 i (independent of δ, but with a stronger dependence in the gaps) were also shown [START_REF] Jamieson | lil'UCB: an Optimal Exploration Algorithm for Multi-Armed Bandits[END_REF][START_REF] Chen | Towards instance optimal bounds for best arm identification[END_REF][START_REF] Simchowitz | The simulator: Understanding adaptive sampling in the moderate-confidence regime[END_REF][START_REF] Chen | Nearly instance optimal sample complexity bounds for top-k arm selection[END_REF]. Note that the characteristic time for σ-sub-Gaussian distributions (which does not have a form as "explicit" as [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF]) is always smaller than the ones for Gaussian having the same means and variance σ 2 .

A good algorithm should have an expected sample complexity as close as possible to these lower bounds. Several algorithms for (ε-)BAI are based on modifications of the UCB algorithm [START_REF] Kalyanakrishnan | PAC subset selection in stochastic multi-armed bandits[END_REF][START_REF] Jamieson | lil'UCB: an Optimal Exploration Algorithm for Multi-Armed Bandits[END_REF][START_REF] Gabillon | Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence[END_REF].

Others compute approximate solutions to the lower bound maximization problem and sample arms in order to approach the solution [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF][START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF][START_REF] Wang | Fast pure exploration via frank-wolfe[END_REF]. Our method belongs to the family of Top Two algorithms [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF][START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF][START_REF] Jourdan | Top two algorithms revisited[END_REF], which select at each time two arms called leader and challenger, and sample among them. It is the first Top Two algorithm for the ε-BAI problem (for ε > 0).

Any time and uniform ε-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 ε, similarly to the results of [START_REF] Zhao | Revisiting simple regret: Fast rates for returning a good arm[END_REF]. That is, we bound P ν (î n / ∈ I ε (µ)) for all n and all ε. This gives a bound on the probability of error in ε-BAI, and a bound on the simple regret of the sampling rule by integrating:

E ν [µ -µ în ] = P ν (î n / ∈ I ε (µ))d ε.
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, [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF]) and sequential halving (SH, [START_REF] Karnin | Almost optimal Exploration in multi-armed bandits[END_REF]). These algorithms can be extended to not depend on T by using a doubling trick [START_REF] Jun | Anytime exploration for multi-armed bandits using confidence information[END_REF][START_REF] Zhao | Revisiting simple regret: Fast rates for returning a good arm[END_REF]. 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.

Contributions

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

• EB-TC ε0 performs well empirically compared to existing methods, both for the expected sample complexity criterion in fixed confidence ε-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 ε0 in fixed confidence ε-BAI with sub-Gaussian distributions, both asymptotically (Theorem 1) as δ → 0 and for any δ (Theorem 2). In particular, EB-TC ε with ε > 0 is asymptotically optimal for ε-BAI with Gaussian distributions.

• We prove a uniform ε-error bound valid for any time for EB-TC ε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).

Anytime Top Two sampling rule

We propose an anytime Top Two algorithm, named EB-TC ε0 and summarized in Figure 1.

Recommendation rule Let N n,i := t∈[n-1] 1 (I t = i) be the number of pulls of arm i before time n, and µ n,i := 1

Nn,i t∈[n-1] X t,It 1 (I t = i) be its empirical mean. At time n > K, we recommend the Empirical Best (EB) arm în ∈ arg max i∈[K] µ n,i (where ties are broken arbitrarily).

1: Input: slack ε 0 > 0, proportion β ∈ (0, 1) (only for fixed proportions). 2: Set în ∈ arg max i∈[K] µ n,i , B n = în and C n ∈ arg min i =Bn µ n,Bn -µn,i+ε0 √ 1/N n,Bn +1/Nn,i .

3: Set βn+1 (B n , C n ) = (T n (B n , C n ) βn (B n , C n ) + β n (B n , C n ))/T n+1 (B n , C n ) with [fixed]
β n (i, j) = β or [IDS] β 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 Bn n,Cn ≤ (1 -βn+1 (B n , C n ))T n+1 (B n , C n ),

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 ∈ [K] and a challenger C n = B n . It then chooses the arm to pull among them. For the leader/challenger pair, we consider the Empirical Best (EB) leader B EB n = în and, given a slack ε 0 > 0, the Transportation Cost (TC ε0 ) challenger

C TCε0 n ∈ arg min i =B EB n µ n,B EB n -µ n,i + ε 0 1/N n,B EB n + 1/N n,i . (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 [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF]. We define one tracking procedure per pair of leader/challenger (i, j) ∈ [K] 2 such that i = 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 βn (i, j) ∈ (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 βn (i, j). Fixed proportions set βn (i, j) = β for all (n, i, j) ∈ N × [K] 2 , where β ∈ (0, 1) is fixed beforehand. Information-Directed Selection (IDS) [START_REF] You | Information-directed selection for top-two algorithms[END_REF] defines β n (i, j) = N n,j /(N n,i + N n,j ) and sets βn (i, j) := T n (i, j) -1 t∈[n-1] 1 ((B t , C t ) = (i, j)) β t (i, j) where T n (i, j) := t∈[n-1] 1 ((B t , C t ) = (i, j)) is the selection count of arms (i, j) as leader/challenger. Let N i n,j := t∈[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 Bn n,Cn ≤ (1 -βn+1 (B n , C n ))T n+1 (B n , C n ) and I n = B n otherwise. Using Theorem 6 in [START_REF] Degenne | Structure adaptive algorithms for stochastic bandits[END_REF] for each tracking procedure (i.e. each pair (i, j)) yields Lemma 2 (proved in Appendix H).

Lemma 2. For all n > K, i ∈ [K], j = i, we have -1/2 ≤ N i n,j -(1 -βn (i, j))T n (i, j) ≤ 1. The TC ε0 challenger seeks to minimize an empirical version of a quantity that appears in the lower bound for ε 0 -BAI (Lemma 1). As such, it is a natural extension of the TC challenger used in the T3C algorithm [START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF] for ε 0 = 0. In earlier works on Top Two methods [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF][START_REF] Qin | Improving the expected improvement algorithm[END_REF][START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF], the choice between leader and challenger is randomized: given a fixed proportion β ∈ (0, 1), set I n = B n with probability β, otherwise I n = C n . [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF] replaced randomization by tracking, and [START_REF] You | Information-directed selection for top-two algorithms[END_REF] proposed IDS to define adaptive proportions β n (B n , C n ) ∈ (0, 1). In this work we study both fixed proportions with β = 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 [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF] tracked the leader with K procedures, we consider K(K -1) independent tracking procedures depending on the current leader/challenger pair.

Choosing ε 0 [START_REF] Jourdan | Top two algorithms revisited[END_REF] shows that EB-TC (i.e. EB-TC ε0 with slack ε 0 = 0) suffers from poor empirical performance for moderate δ in BAI (see Appendix D.3 in [START_REF] Jourdan | Top two algorithms revisited[END_REF] for a detailed discussion). Therefore, the choice of the slack ε 0 > 0 is critical since it acts as a regularizer which naturally induces sufficient exploration. By setting ε 0 too small, the EB-TC ε0 algorithm will become as greedy as EB-TC and perform poorly. Having ε 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 ε 0 = ε for ε-BAI, but the empirical performance is only degrading slowly for ε 0 > ε. Taking ε 0 < ε leads to very poor performance. We discuss this trade-off in more details in our experiments (e.g. Figures 5,[START_REF] Chen | Towards instance optimal bounds for best arm identification[END_REF] 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 [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF][START_REF] Qin | Improving the expected improvement algorithm[END_REF][START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF]) or optimism (UCB leader [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF]). For the choice of the challenger, we can use randomization (RS challenger [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF]) or penalization (TCI challenger [START_REF] Jourdan | Top two algorithms revisited[END_REF], KKT challenger [START_REF] You | Information-directed selection for top-two algorithms[END_REF] or EI challenger [START_REF] Qin | Improving the expected improvement algorithm[END_REF]).

Anytime sampling rule EB-TC ε0 is independent of a budget of samples T or a confidence parameter δ. This anytime sampling rule can be regarded as a stream of empirical means/counts (µ n , N n ) n>K (which could trigger stopping) and a stream of recommendations în = i (µ 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 (ε, δ)-PAC. It can also be used to get an ε-good recommendation with large probability at any given time n.

Stopping rule for fixed-confidence ε-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 ε stopping rule [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] prescribes to stop at the time

τ ε,δ = inf n > K | min i =în µ n,în -µ n,i + ε 1/N n,în + 1/N n,i ≥ 2c(n -1, δ) with în = i (µ n ) , (3)
where c : N×(0, 1) → R + is a threshold function. Lemma 3 gives a threshold ensuring that the GLR ε stopping rule is (ε, δ)-PAC for all ε ≥ 0 and δ ∈ (0, 1), independently of the sampling rule.

Lemma 3 ([27]

). Let ε ≥ 0 and δ ∈ (0, 1). Given any sampling rule, using the threshold

c(n, δ) = 2C G (log((K -1)/δ)/2) + 4 log(4 + log(n/2)) (4)
with the stopping rule (3) with error/confidence pair (ε, δ) yields a (ε, δ)-PAC algorithm for sub-Gaussian distributions. The function C G is defined in [START_REF] Jun | Anytime exploration for multi-armed bandits using confidence information[END_REF].

It satisfies C G (x) ≈ x + log(x).

Fixed-confidence theoretical guarantees

To study ε-BAI in the fixed-confidence setting, we couple EB-TC ε0 with the GLR ε stopping rule (3) using error ε ≥ 0, confidence δ ∈ (0, 1) and threshold [START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF]. The resulting algorithm is (ε, δ)-PAC by Lemma 3. We derive upper bounds on the expected sample complexity E ν [τ ε,δ ] both in the asymptotic regime of δ → 0 (Theorem 1) and for finite confidence when ε = ε 0 (Theorem 2).

Theorem 1. Let ε ≥ 0, ε 0 > 0 and (β, δ) ∈ (0, 1) 2 . Combined with GLR ε stopping (3), the EB-TC ε0 algorithm is (ε, δ)-PAC and it satisfies that, for all ν ∈ D K with mean µ such that |i (µ)| = 1,

[IDS] lim sup δ→0 E ν [τ ε,δ ] log(1/δ) ≤ T ε0 (µ)D ε,ε0 (µ) and [fixed β] lim sup δ→0 E ν [τ ε,δ ] log(1/δ) ≤ T ε0,β (µ)D ε,ε0 (µ), where D ε,ε0 (µ) = (1 + max i =i (ε 0 -ε)/(µ -µ i + ε)) 2 .
While Theorem 1 holds for all sub-Gaussian distributions, it is particularly interesting for Gaussian ones, in light of Lemma 1. When choosing ε = ε 0 (i.e. D ε0,ε0 (µ) = 1), Theorem 1 shows that EB-TC ε0 is asymptotically optimal for Gaussian bandits when using IDS proportions and asymptotically β-optimal when using fixed proportions β. 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 ε 0 < ε, and close to the optimal one when ε 0 > ε (Figures 5, 6 and 7 in Appendix J.2.1).

Until recently [START_REF] You | Information-directed selection for top-two algorithms[END_REF], proving asymptotic optimality of Top Two algorithms with adaptive choice β was an open problem in BAI. In this work, we prove that their choice of IDS proportions also yield asymptotically optimal algorithms for ε-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 [START_REF] Qin | Improving the expected improvement algorithm[END_REF][START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF][START_REF] Jourdan | Top two algorithms revisited[END_REF]. The improvement is possible thanks to the regularization induced by the slack ε 0 > 0.

While asymptotic optimality in the ε-BAI setting was already achieved for various algorithms (e.g. ε-Track-and-Stop (TaS) [START_REF] Garivier | Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models[END_REF], Sticky TaS [START_REF] Degenne | Pure exploration with multiple correct answers[END_REF] or LεBAI [START_REF] Jourdan | Choosing answers in ε-best-answer identification for linear bandits[END_REF]), none of them obtained nonasymptotic guarantees. Despite their theoretical interest, asymptotic results provide no guarantee on the performance for moderate δ. Furthermore, asymptotic results on Top Two algorithms require a unique best arm regardless of the considered error ε: 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 ε-BAI, our guarantees should only require that one of the ε-good arms is identified and should hold for instances having multiple best arms. The upper bound should scale with ε -2 0 instead of ∆ -2 min when ∆ min is small. Theorem 2 satisfies these requirements.

Theorem 2. Let δ ∈ (0, 1) and ε 0 > 0. Combined with GLR ε0 stopping (3), the EB-TC ε0 algorithm with fixed β = 1/2 is (ε 0 , δ)-PAC and satisfies that, for all ν ∈ D K with mean µ,

E ν [τ ε0,δ ] ≤ inf ε∈[0,ε0] max {T µ,ε0 (δ, ε) + 1, S µ,ε0 (ε)} + 2K 2 ,
where T µ,ε0 (δ, ε) and S µ,ε0 (ε) are defined by

T µ,ε0 (δ, ε) = sup{n | n -1 ≤ 2(1 + γ) 2 i∈Iε(µ) T ε0,1/2 (µ, i)( c(n -1, δ) + 4 log n) 2 } , S µ,ε0 (ε) = h 1 16(1 + γ -1 ) a µ,ε0 (ε) H µ,ε0 (ε), (1 + γ -1 )K 2 a µ,ε0 (ε) + 1 , a µ,ε0 (ε) = min i∈Iε(µ) T ε0,1/2 (µ, i) i∈Iε(µ) T ε0,1/2 (µ, i) min i∈Iε(µ),j =i w ε0,1/2 (µ, i) j ,
where γ ∈ (0, 1/2] is an analysis parameter and h 1 (y, z) ≈ z + y log(z + y log(y)) as in Lemma 51. T ε0,1/2 (µ, i) and w ε0,1/2 (µ, i) are defined in (1) and

H µ,ε0 (ε) := 2|i (µ)| ∆ µ (ε) 2 + (|I ε(µ) \ i (µ)|)C µ,ε0 (ε) 2 + i / ∈Iε(µ) max{C µ,ε0 (ε), √ 2∆ -1 i } 2 , ( 5
)
with ∆ µ (ε) = min k / ∈Iε(µ) ∆ k and C µ,ε0 (ε) = max{2∆ µ (ε) -1 -ε -1 0 , ε -1 0 }. The upper bound on E ν [τ ε0,δ ] involves a δ-dependent term T µ,ε0 (δ, ε
) and a δ-independent term S µ,ε0 (ε). The choice of ε influences the compromise between those, and the infimum over ε means that our algorithm benefits from the best possible trade-off. In the asymptotic regime, we take ε = 0 and γ → 0 and we obtain lim δ→0 E ν [τ ε0,δ ]/ log(1/δ) ≤ 2|i (µ)|T ε0,1/2 (µ). When |i (µ)| = 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 (µ)| from the β-optimal one. Given a finite confidence, the dominant term will be S µ,ε0 (ε). For ε = 0, we show that H µ,ε0 (0) = O(K min{∆ min , ε 0 } -2 ), hence we should consider ε > 0 to avoid the dependency in ∆ min . For ε = ε 0 , there exists instances such that max i∈Iε 0 (µ) T ε0,1/2 (µ, i) is arbitrarily large, hence S µ,ε0 (ε 0 ) will be very large as well. The best trade-off is attained in the interior of the interval (0, ε 0 ). For ε = ε 0 /2, Lemma 10 shows that T ε0,1/2 (µ, i) = O(K/ε 2 0 ) for all i ∈ I ε0/2 (µ) and H µ,ε0 (ε 0 /2) = O(K/ε 2 0 ). Therefore, we obtain an upper bound O(|I ε0/2 (µ)|Kε -2 0 log ε -1 0 ). Likewise, Lemma 10 shows that min j =i w ε0,1/2 (µ, i) j ≥ (16(K -2) + 2) -1 for all i ∈ I ε0/2 (µ). While the dependency in a µ,ε0 (ε 0 /2) is milder in ε-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 [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF], this method allows to clip min j =i w ε0,1/2 (µ, i) j by a fixed value x ∈ [0, (K -1) -1 ] for all i ∈ I ε(µ).

Comparison with existing upper bounds The LUCB algorithm [START_REF] Kalyanakrishnan | PAC subset selection in stochastic multi-armed bandits[END_REF] 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 ε 0 . As LUCB satisfies E µ [τ ε0,δ ] ≤ 292H ε0 (µ) log(H ε0 (µ)/δ) + 16 where H ε0 (µ) = i (max{∆ i , ε 0 /2}) -2 , it enjoys better scaling than EB-TC ε0 for finite confidence. However, since the empirical allocation of LUCB is not converging towards w ε0,1/2 (µ), 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 δ. In contrast, EB-TC ε0 enjoys such guarantees (see Section 4).

Key technical tool for the non-asymptotic analysis

We want to ensure that EB-TC ε0 eventually selects only ε-good arms as leader, for any error ε ≥ 0. Our proof strategy is to show that if the leader is not an ε-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 δ ∈ (0, 1] and n > K. Let T n (i) := j =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, δ)) n≥t>K and positive reals (D i (n, δ)) i∈[K] such that, for all t ∈ {K + 1, . . . , n}, under the event A t (n, δ),

∃i t ∈ [K], T t (i t ) ≤ D it (n, δ) and T t+1 (i t ) = T t (i t ) + 1 . (6) Then, we have n t=K+1 1 (A t (n, δ)) ≤ i∈[K] D i (n, δ).
To control the deviation of the empirical means and empirical gaps to their true value, we use a sequence of concentration events (E n,δ ) n>T defined in Lemma 45 (Appendix G.2) such that P ν (E n,δ ) ≤ K 2 δn -s where s ≥ 0 and δ ∈ (0, 1]. For the EB-TC ε0 algorithm with fixed β = 1/2, we prove that, under E n,δ , {B EB t / ∈ I ε (µ)} is a "bad" event satisfying the assumption of Lemma 4. This yields Lemma 5, which essentially says that the leader is an ε-good arm except for a logarithmic number of rounds.

Lemma 5. Let δ ∈ (0, 1], n > K and ε ≥ 0. Under the event E n,δ , we have

i∈Iε(µ) j T n (i, j) ≥ n -1 -8H µ,ε0 (ε)f 2 (n, δ) -3K 2 , where f 2 (n, δ) = log(1/δ) + (2 + s) log n and H µ,ε0 (ε) is defined in (5).
Noticeably, Lemma 5 holds for any ε ≥ 0 even when there are multiple best arms. As expected the number of times the leader is not among the ε 0 -good arms depends on H µ,ε0 (ε 0 ) = O(K/ε 2 0 ). The number of times the leader is not among the best arms depends on H µ,ε0 (0

) = O(K(min{∆ min , ε 0 }) -2 ).
Time-varying slack Theorem 1 shows the asymptotic optimality of the EB-TC ε0 algorithm with IDS for ε 0 -BAI (where ε 0 > 0). To obtain optimality for BAI, we consider time-varying slacks (ε n ) n , where (ε n ) n is decreasing, ε n > 0 and ε n → +∞ 0. A direct adaptation of our asymptotic analysis on E ν [τ 0,δ ] (see Appendix D), regardless of the choice of (ε n ) n , one can show that using GLR 0 stopping, the EB-TC (εn)n algorithm with IDS is (0, δ)-PAC and is asymptotically optimal in BAI. Its empirical performance is however very sensitive to the choice of (ε n ) n (Appendix J.2.3).

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 ε0 , which does not depend on the confidence parameter δ. 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 [START_REF] Komiyama | Minimax optimal algorithms for fixed-budget best arm identification[END_REF] 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 [START_REF] Bubeck | Pure Exploration in Finitely Armed and Continuous Armed Bandits[END_REF].

Their argument also applies to β-optimal algorithms, hence to EB-TC 0 with β = 1/2. However, whenever ε 0 is positive, Theorem 3 reveals that the error probability of EB-TCε 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 ε-optimal, for any error ε ≥ 0. This bound involves instancedependent complexities depending solely on the gaps in µ. To state it, we define

C µ := |{µ i | i ∈ [K]}| as the number of distinct arm means in µ and let C µ (i) := {k ∈ [K] | µ -µ k = ∆ i }
be the set of arms having mean gap ∆ i where the gaps are sorted by increasing order 0

= ∆ 1 < ∆ 2 < • • • < ∆ Cµ . For all ε ≥ 0, let i µ (ε) = i if ε ∈ [∆ i , ∆ i+1 ) (with the convention ∆ Cµ+1 = +∞).
Theorem 3 shows that the exponential decrease of P ν (î n / ∈ I ε (µ)) is linear.

Theorem 3. (see Theorem 6 in Appendix F) Let ε 0 > 0. The EB-TC ε0 algorithm with fixed proportions β = 1/2 satisfies that, for all ν ∈ D K with mean µ, for all ε ≥ 0, for all n > 5K 2 /2,

P ν (î n / ∈ I ε (µ)) ≤ K 2 e 2 (2 + log n) 2 exp -p n -5K 2 /2 8H iµ(ε) (µ, ε 0 ) . where p(x) = x -log x and (H i (µ, ε 0 )) i∈[Cµ-1] are such that H 1 (µ, ε 0 ) = K(2∆ -1 min + 3ε -1 0 ) 2 and K/∆ -2 i+1 ≤ H i (µ, ε 0 ) ≤ K min j∈[i] max{2∆ -1 j+1 , 2 ∆j /ε0+1 ∆i+1-∆j + 3ε -1 0 } 2 for all i > 1.
This bound can be compared with the following uniform ε-error bound of the strategy using uniform sampling and recommending the empirical best arm:

P îU n / ∈ I ε (µ) ≤ i / ∈Iε(µ) exp - ∆ 2 i n/K 4 ≤ K exp - n -K 4K∆ -2 iµ(ε)+1
Recalling that the quantity H i (µ, ε 0 ) in Theorem 3 is always bounded from below by 2K∆ -1 i+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 ε = 0, we have

P ν (î n / ∈ i (µ)) ≤ exp -Θ n K(∆ -1 min + ε -1 0 ) 2 , P ν îU n / ∈ i (µ) ≤ exp -Θ n K∆ -2 min .
Even if they provide a nice sanity-check for the use of a sampling rule with optimal fixed-confidence guarantees for ε 0 -BAI in the anytime regime, we acknowledge that these guarantees are far from optimal. Indeed, the work of [START_REF] Zhao | Revisiting simple regret: Fast rates for returning a good arm[END_REF] provides tighter anytime uniform ε-error probability bounds for two algorithms: an anytime version of Sequential Halving [START_REF] Karnin | Almost optimal Exploration in multi-armed bandits[END_REF] 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

P ν (î n / ∈ I ε (µ)) ≤ exp (-Θ (n/H(ε))) with H(ε) = 1 g(ε/2) max i≥g(ε)+1 i ∆ 2 i where g(ε) = |{i ∈ [K] | µ i ≥ µ -ε}|.
Therefore, they can be much smaller than K∆ -2 iµ(ε)+1 . The BUCB algorithm of [START_REF] Katz-Samuels | The true sample complexity of identifying good arms[END_REF] is also analyzed for any level of error ε, but in a different fashion. The authors provide bounds on its (ε, δ)-unverifiable sample complexity, defined as the expectation of the smallest stopping time τ satisfying P(∀t ≥ τ , în ∈ I ε (µ)) ≥ 1 -δ. 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 δ. Interestingly, to prove Theorem 3 we first prove a bound on the unverifiable sample complexity of EB-TC ε0 which is valid for all (ε, δ), neither of which are parameters of the algorithm. More precisely, we prove that P ν ∀n > U iµ(ε),δ (µ, ε 0 ), în ∈ I ε (µ) ≥ 1 -δ for U i,δ (µ, ε 0 ) = δ→0 8H i (µ, ε 0 ) log(1/δ) + O(log log(1/δ)). As this statement is valid for all δ ∈ (0, 1), applying it for each n to δ n such that U iµ(ε),δn (µ, ε 0 ) = n, we obtain Theorem 3. We remark that such a trick cannot be applied to BUCB to get uniform ε-error bounds for any time, as the algorithm does depend on δ.

Simple regret As already noted by [START_REF] Zhao | Revisiting simple regret: Fast rates for returning a good arm[END_REF], uniform ε-error bounds easily yield simple regret bounds. We state in Corollary 1 the one obtained for EB-TC ε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 (î n ) and playing arm în . An exponentially decaying simple regret leads to a constant cumulative regret in this decoupled exploration/exploitation setting [START_REF] Avner | Decoupling exploration and exploitation in multi-armed bandits[END_REF][START_REF] Rouyer | Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits[END_REF].

Corollary 1. Let ε 0 > 0. Let p(x) and (H i (µ, ε 0 )) i∈[Cµ-1] be defined as in Theorem 3. The EB-TC ε0 algorithm with fixed β = 1/2 satisfies that, for all ν ∈ D K with mean µ, for all n > 5K 2 /2,

E ν [µ -µ în ] ≤ K 2 e 2 (2 + log n) 2 i∈[Cµ-1] (∆ i+1 -∆ i ) exp -p n -5K 2 /2 8H i (µ, ε 0 ) .
Following the discussion above, this bound is not expected to be state-of-the-art, it rather justifies that EB-TC ε0 with ε 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 ε0 to that of DSH in synthetic experiments with a moderate number of arms, revealing the superior performance of EB-TC ε0 .

Experiments

We assess the performance of the EB-TC ε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 (µ)| = 2. Empirical stopping time We study the impact of large sets of arms (up to K = 1000) in ε-BAI for (ε, δ) = (0.1, 0.01) on the "α = 0.3" scenario of [START_REF] Jamieson | Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting[END_REF] which sets

µ i = 1 -((i -1)/(K -1)) α for all i ∈ [K]
. EB-TC ε0 with IDS and slack ε 0 = ε is compared to existing ε-BAI algorithms having low computational cost. This precludes algorithms such as ε-Track-and-Stop (TaS) [START_REF] Garivier | Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models[END_REF],

Sticky TaS [START_REF] Degenne | Pure exploration with multiple correct answers[END_REF] or ε-BAI adaptation of FWS [START_REF] Wang | Fast pure exploration via frank-wolfe[END_REF] and DKM [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF]. In Appendix J.2.2, we compare EB-TC ε to those algorithms on benchmarks with smaller number of arms. We show that EB-TC ε performs on par with ε-TaS and ε-FWS, but outperforms ε-DKM. As Top Two benchmarks with fixed β = 1/2, we consider T3C [START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF], EB-TCI [START_REF] Jourdan | Top two algorithms revisited[END_REF] and TTUCB [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF]. To provide a fair comparison, we adapt them to tackle ε-BAI by using the stopping rule (3) and by adapting their sampling rule to use the TCε challenger from (2) (with a penalization log N n,i for EB-TCI). We use the heuristic threshold c(n, δ) = log((1 + log n)/δ). While it is too small to ensure the (ε, δ)-PAC property, it still yields an empirical error which is several orders of magnitude lower than δ. Finally, we compare with LUCB [START_REF] Kalyanakrishnan | PAC subset selection in stochastic multi-armed bandits[END_REF] and uniform sampling. For a fair comparison, LUCB uses 2c(n -1, δ)/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 EB-TC ε performs on par with the ε-T3C heuristic, and significantly outperforms the other algorithms. While the scaling in K of ε-EB-TCI and LUCB appears to be close to the one of EB-TC ε , ε-TTUCB and uniform sampling obtain a worse one. Figure 2(a) also reveals that the regularization ensured by the TCε challenger is sufficient to ensure enough exploration, hence other exploration mechanisms are superfluous (TS/UCB leader or TCI challenger).

Anytime empirical simple regret The EB-TC ε0 algorithm with fixed β = 1/2 and ε 0 = 0.1 is compared to existing algorithms on the instance µ = (0.6, 0.6, 0.55, 0.45, 0.3, 0.2) from [START_REF] Garivier | Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models[END_REF], 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 [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF] and SH [START_REF] Karnin | Almost optimal Exploration in multi-armed bandits[END_REF]. 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 EB-TC ε0 outperforms uniform sampling, as well as DSR and DSH, which both perform worse due to the dropped observations. The favorable performance of EB-TC ε0 is confirmed on other instances from [START_REF] Garivier | Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models[END_REF], and for "two-groups" instances with varying |i (µ)| (see Figures 10 and12).

Supplementary experiments

Extensive experiments and implementation details are available in Appendix J. In Appendix J.2.1, we compare the performance of EB-TC ε0 with different slacks ε 0 for IDS and fixed β = 1/2. In Appendix J.2.2, we demonstrate the good empirical performance of EB-TC ε0 compared to state-of-the art methods in the fixed-confidence ε-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 [START_REF] Jamieson | Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting[END_REF][START_REF] Garivier | Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models[END_REF] and "two-groups" instances with varying |i (µ)|.

Perspectives

We have proposed the EB-TC ε0 algorithm, which is easy to understand and implement. EB-TC ε0 is the first algorithm to be simultaneously asymptotically optimal in the fixed-confidence ε 0 -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 ε0 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 [START_REF] Zhao | Revisiting simple regret: Fast rates for returning a good arm[END_REF] 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 ε0 algorithm with IDS and slack ε 0 > 0 only achieves asymptotic optimality for ε 0 -BAI with Gaussian bandits. Even though IDS has been introduced by [START_REF] You | Information-directed selection for top-two algorithms[END_REF] 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 ν [τ ε0,δ ] and E ν [µ -µ în ] were obtained for the EB-TC ε0 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 ε0 algorithm is a promising method to tackle structured bandits. Despite the existence of heuristics for settings such as Top-k identification [START_REF] You | Information-directed selection for top-two algorithms[END_REF], it is still an open problem to efficiently adapt Top Two approaches to cope for other structures such as ε-BAI in linear bandits.

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 ε-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 ε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 ε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 ε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 ε-goodness, propose the EB-TC m ε0 algorithm 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 1: Notation for the setting.

Notation

Type Description

K N Number of arms ν i D Sub-Gaussian distribution of arm i ∈ [K] ν D K Vector of sub-Gaussian distributions, ν := (ν i ) i∈[K] µ i R Mean of arm i ∈ [K] µ R K Vector of means, µ := (µ i ) i∈[K] µ R Largest mean, µ := max i∈[K] µ i ∆ i R + Gap of arm i, ∆ i := µ -µ i i (µ) [K] Best arms, i (µ) := arg max i∈[K] µ i ε R + Additive error of ε-good arms I ε (µ) [K] ε-Good arms, I ε (µ) := {i ∈ [K] | ∆ i ≤ ε} T ε (µ), T ε,β (µ), T ε,β (µ, i) R + Asymptotic (β-)characteristic time for ε-BAI w ε (µ), w ε,β (µ), w ε,β (µ, i) K Asymptotic (β-)optimal allocation for ε-BAI C µ [K] Number of equivalence classes, C µ := |{µ i | i ∈ [K]}| C µ (i) [K] Equivalence class, C µ (i) := {k ∈ [K] | µ -µ k = ∆ i }

B Notation

We recall some commonly used notation: the set of integers [n] := {1, • • • , n}, the complement X and interior 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, Ω and Θ, the (K -1)-dimensional

probability simplex K := w ∈ R K + | w ≥ 0, i∈[K] w i = 1 .
The functions C G and g G are defined in [START_REF] Jun | Anytime exploration for multi-armed bandits using confidence information[END_REF]

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 ν ∈ D K with mean µ ∈ R K . The (β-)characteristic times for the fixed-confidence BAI setting with Gaussian bandits N (µ, 1) are defined as

T (µ) = min β∈(0,1) T β (µ) with 2T β (µ) -1 = max w∈ K ,w i =β min i =i (µ i -µ i ) 2 1/β + 1/w i , (7)
see [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF][START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF] for example. Let us denote by w β (µ) and w (µ) their maximizer, which we will refer to as (β-)optimal allocations. Note that (T (µ), T β (µ)) = (T 0 (µ), T 0,β (µ)) and (w (µ), w β (µ)) = (w 0 (µ), w 0,β (µ)).

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 (µ) ≤ 2T (µ). Lemma 6 also holds for any single-parameter exponential family of distributions and for the non-parametric family of bounded distributions [START_REF] Jourdan | Top two algorithms revisited[END_REF].

Lemma 6 ([15, 34, 21]). If i (µ) is a singleton and β ∈ (0, 1), then w (µ) and w β (µ) are singletons, i.e. the optimal allocations are unique, and w (µ) i > 0 and w β (µ) i > 0 for all i ∈ [K]. Moreover, we have T 1/2 (µ) ≤ 2T (µ) and with β = w i (µ). Additionally, we have

H(µ) ≤ T (µ) ≤ 2H(µ)
where

H(µ) = 2 i∈[K] ∆ -2 i where ∆ i = ∆ 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 (µ) ≤ r K T (µ) might hold.

Lemma 7 ( [START_REF] Barrier | A non-asymptotic approach to best-arm identification for gaussian bandits[END_REF][START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF]). Assume that i (µ) = {i }. Let r(µ) and r β (µ) be the solution of ψ µ (r) = 0 and ϕ µ,β (r) = 0 with, for all r ∈ (1/ min i =i (µ i -µ i ) 2 , +∞),

ψ µ (r) = i =i 1 (r(µ i -µ i ) 2 -1) 2 -1 and ϕ µ,β (r) = i =i 1 r(µ i -µ i ) 2 -1 - 1 -β β ,
Then, ψ µ and ϕ µ,β are convex and decreasing. Moreover,

T (µ) = 2r(µ) 1 + i =i 1 r(µ)(µ i -µi) 2 -1 and T β (µ) = 2r β (µ) β .
Additionally, for all i = i , we have βw

β (µ) -1 i = βT β (µ)(µ i -µ i ) 2 /2 -1. For K = 2, w (µ) = (0.5, 0.5) and T (µ) = T 1/2 (µ) = 8(µ 1 -µ 2 ) 2 . For K ≥ 3, we have 1/( √ K -1 + 1) ≤ w (µ) i ≤ 1/2 . Let r K = 2K/(1 + √ K -1) 2 , j ∈ arg min j =i µ i -µ j and x ∈ R K-2 such that x j = µ i -µj µ i -µ j .
Then, we have T 1/2 (µ)/T (µ) = Ω(x) (i.e. independent of µ i and µ i -µ j ) and

Ω(1 K-2 ) = r K and ∇ x Ω(1 K-2 ) = 0 K-2 .
Lemma 8 gathers necessary conditions on the (β-)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 [START_REF] You | Information-directed selection for top-two algorithms[END_REF]. Lemma 8 ([3,[START_REF] You | Information-directed selection for top-two algorithms[END_REF]). Assume that i (µ) = {i } and β ∈ (0, 1). Then, for all i = i ,

2T (µ) -1 = (µ i -µ i ) 2 1/w (µ) i + 1/w (µ) i and 2T β (µ) -1 = (µ i -µ i ) 2 1/β + 1/w β (µ) i .
Moreover, we have

w (µ) 2 i = i =i w (µ) 2 i .
Reduction of an ε-BAI problem to a BAI problem Lemma 9 gives a reduction of a ε-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 (µ), T β (µ), w (µ), w β (µ) (such as Lemmas 6, 7 and 8) in order to study T ε (µ), T ε,β (µ), T ε,β (µ, i), w ε (µ), w ε,β (µ) and w ε,β (µ, i).

Lemma 9. Let µ ∈ R K , ε ≥ 0 and ε ∈ [0, ε] and β ∈ (0, 1). For all i ∈ I ε(µ), we define µ ε (i) as µ ε (i) j = µ j -ε for all j = i and µ ε (i

) i = µ i . Then, for all i ∈ I ε(µ), T ε,β (µ, i) = T β (µ ε (i)) and w ε,β (µ, i) = w β (µ ε (i)). Moreover, for all i ∈ i (µ), T ε (µ) = T (µ ε (i )) and T ε,β (µ) = T β (µ ε (i )) . Moreover, we have w ε (µ) = i ∈i (µ) w (µ ε (i )) and w ε,β (µ) = i ∈i (µ) w β (µ ε (i )). Proof. For ε = 0, the result is direct by definition. Let ε > 0 and ε ∈ [0, ε]. The first part is obtained by definition of T ε,β (µ, i), w ε,β (µ, i). Let i ∈ i (µ) and µ ε (i ) defined as above, hence i (µ ε (i )) = {i }. For all i ∈ I ε (µ) \ i (µ), let us denote by λ (i ,i) ε the instance such that λ (i ,i) ε,i = µ i and λ (i ,i) ε,j = µ j -ε for all j = i. If µ i -µ i = ε then i (λ (i ,i) ε ) = {i} ∪ i (µ) \ {i }, otherwise i (λ (i ,i) ε ) = {i}.
We consider the permutation σ that swaps arm i with arm i . By symmetry, we have T (λ

(i ,i) ε ) = T (σ(λ (i ,i) ε
)). Moreover, we have that the gaps of σ(λ

(i ,i) ε
) are all strictly smaller than the gaps of µ ε since ε ≥ ∆ i > 0. Therefore, Lemma 11 of Barrier et al (2022) yields that T (σ(λ

(i ,i) ε )) > T (µ ε ). We have proved that ∀i ∈ i (µ), T (µ ε (i )) < min i∈Iε(µ)\i (µ) T (λ (i ,i) ε )
.

By symmetry T (µ ε (i )) is constant for all i ∈ i (µ), hence we have shown that

∀i ∈ i (µ), T ε (µ) = T (µ ε (i )) .
It also shows that w ε (µ) = i ∈i (µ) w (µ ε (i )). The same reasoning yields the result for T ε,β (µ) and w ε,β (µ).

ε-BAI problems cannot be arbitrarily difficult Lemma 10 shows that, for all i ∈ I ε/2 (µ), T ε,1/2 (µ, i) cannot be arbitrarily large and min j =i w ε0,1/2 (µ, i) j cannot be arbitrarily small. The proof relies on Lemma 9 and existing results for BAI.

Lemma 10. Let ε > 0 and µ ∈ R K . Then, for all i ∈ I ε/2 (µ), we have T ε,1/2 (µ, i) ≤ 32K/ε 2 and min j =i w ε,1/2 (µ, i) j ≥ (16(K -2) + 2) -1 . Proof. Let i ∈ I ε/2 (µ), hence µ i ≥ µ -ε/2. Let µ ε (i) as in Lemma 9 which satisfies that i (µ ε (i)) = {i}. Let ∆ i,j = µ i -µ j and ∆ i,i = µ i -max j =i µ j . Then, we have T ε,1/2 (µ, i) = T 1/2 (µ ε (i)) ≤ 2T (µ ε (i)) ≤ 8 j∈[K] (∆ i,j + ε) -2 ≤ 8 j∈[K] (∆ j + ε/2) -2 ,
where we used Lemma 6 for the two first inequality and i ∈ I ε/2 (µ) for the last one. Since ∆ j ≥ 0, we conclude that T ε,β (µ, i) ≤ 32K/ε 2 . Moreover, using Lemma 6, we have

T ε,1/2 (µ, i) = T 1/2 (µ ε (i)) ≥ T (µ ε (i)) ≥ 2 j∈[K] (∆ i,j + ε) -2 .
Likewise, using Lemma 9 and Lemma 7, we obtain that, for all j = i,

w ε,1/2 (µ) -1 j /2 = w 1/2 (µ ε (i)) -1 j /2 = T 1/2 (µ ε (i))(µ i -µ j + ε) 2 /4 -1 ≤ 2 k / ∈{i,j} µ i -µ j + ε µ i -µ k + ε 2 + 1
where the last inequality uses what we proved above. When µ k ≤ µ j , the ratio is smaller than one.

When

µ k > µ j , we have µ ≥ µ k > µ j ≥ µ -ε/2, hence µ k -µ j ≤ ε/2 and µ i -µ j + ε µ i -µ k + ε ≤ 1 + ε/2 µ -µ k + ε/2 ≤ 2 .
Therefore, we obtain w ε,1/2 (µ) -1 j /2 ≤ 8(K -2) + 1, which concludes the result.

Lemma 11 links the characteristic times for ε-BAI where ε ∈ {ε 0 , ε 1 }.

Lemma 11. Let µ ∈ R K such that |i (µ)| = 1. Let ε 0 > ε 1 .
Then, for all β ∈ (0, 1), we have

T ε0 (µ)(∆ min +ε 0 ) 2 ≥ T ε1 (µ)(∆ min +ε 1 ) 2 and T ε0,β (µ)(∆ min +ε 0 ) 2 ≥ T ε1,β (µ)(∆ min +ε 1 ) 2 . Let ε 0 < ε 1 . Then, T ε0 (µ)(∆ max +ε 0 ) 2 ≥ T ε1 (µ)(∆ max +ε 1 ) 2 and T ε0,β (µ)(∆ max +ε 0 ) 2 ≥ T ε1,β (µ)(∆ max +ε 1 ) 2 . Proof. Let i (µ) = {i }. Let ε 0 > ε 1 . Using Lemma 9, we have 2T ε (µ) -1 (∆ min + ε) -2 = max w∈ K min j =i ∆j (ε) 2 1/w i + 1/w j with ∆j (ε) = µ -µ j + ε ∆ min + ε .
To conclude the first part of the first result, a sufficient condition is to show that ∆j (ε 1 ) ≥ ∆j (ε 0 ) for all j = i . Direct manipulations show that, for all j = i ,

∆j (ε 1 ) ≥ ∆j (ε 0 ) ⇐⇒ 1 - ε 0 -ε 1 µ -µ j + ε 0 ≥ 1 - ε 0 -ε 1 ∆ min + ε 0 ⇐⇒ µ -µ j ≥ ∆ min ,
hence the result holds. The same proof can be used to obtain the second part of the first result.

Let ε 0 < ε 1 . Using Lemma 9, we have

2T ε (µ) -1 (∆ max + ε) -2 = max w∈ K min j =i ∆j (ε) 2 1/w i + 1/w j with ∆j (ε) = µ -µ j + ε ∆ max + ε .
To conclude the first part of the second result, a sufficient condition is to show that ∆j (ε 1 ) ≥ ∆j (ε 0 ) for all j = i . Direct manipulations show that, for all j = i ,

∆j (ε 1 ) ≥ ∆j (ε 0 ) ⇐⇒ 1 + ε 1 -ε 0 µ -µ j + ε 0 ≥ 1 + ε 1 -ε 0 ∆ max + ε 0 ⇐⇒ µ -µ j ≤ ∆ max ,
hence the result holds. The same proof can be used to obtain the second part of the second result.

D Asymptotic analysis

Let ε 0 > 0, β ∈ (0, 1) and δ ∈ (0, 1). In this section, we provide an asymptotic analysis of EB-TC ε0 slack ε 0 > 0 combined with the stopping rule (3) with parameters (ε 0 , δ). First, we detail IDS proportions in Appendix D.1. Then, we sketch the proof for fixed proportions β in Appendix D.2.

In the following, we consider a sub-Gaussian bandit with distribution ν ∈ D K having mean parameter µ ∈ R K with a unique best arm, i.e. i (µ) = {i }. We restate Theorem 1 below.

Theorem 4 (Theorem 1). Let ε 0 > 0, ε 1 ≥ 0 and δ ∈ (0, 1). Using the threshold (4) in the stopping rule (3) with slack ε 1 , the EB-TC ε0 algorithm is (ε 1 , δ)-PAC. For IDS proportions, it satisfies that, for all ν

∈ D K such that |i (µ)| = 1, lim sup δ→0 E ν [τ ε1,δ ] log(1/δ) ≤ T ε0 (µ) 1 + max i =i ε 0 -ε 1 µ i -µ i + ε 1 2 . Let β ∈ (0, 1). For fixed proportions β, it satisfies that, for all ν ∈ D K such that |i (µ)| = 1, lim sup δ→0 E ν [τ ε1,δ ] log(1/δ) ≤ T ε0,β (µ) 1 + max i =i ε 0 -ε 1 µ i -µ i + ε 1 2 .
Theorem 1 provides asymptotic upper bound on the expected sample complexity of the EB-TC ε0 algorithm when combined with the stopping rule (3). When ε 1 = ε 0 and for Gaussian distributions, combining Lemma 1 and Theorem 1 shows that the EB-TC ε0 algorithm is asymptotically optimal for ε 0 -BAI when using IDS proportions and asymptotically β-optimal for ε 0 -BAI when using fixed proportions β. Until recently [START_REF] You | Information-directed selection for top-two algorithms[END_REF], proving asymptotic optimality of Top Two algorithms with adaptive choice β was an open problem in the BAI literature. Our work extends their analysis to tackle the ε-BAI setting. Compared to previous work, we removed the assumption that sub-optimal arms should have distinct means.

Considering ε 1 = ε 0 can be interesting when the practitioner decides to tackle ε-BAI with an error ε which is different from the slack ε 0 used by the EB-TC ε0 algorithm. Those situations occur when the practitioner is observing the data collected by the EB-TC ε0 algorithm without having control over it. Theorem 1 show 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 ε 1 -BAI, T ε1 (µ)) is

T ε0 (µ) T ε1 (µ) (∆ min + ε 0 ) 2 (∆ min + ε 1 ) 2 ≥ 1 when ε 0 > ε 1 , otherwise T ε0 (µ) T ε1 (µ) (∆ max + ε 0 ) 2 (∆ max + ε 1 ) 2 ≥ 1 ,
where the inequalities comes 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 β by replacing T ε (µ) by T ε,β (µ).

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 [START_REF] Qin | Improving the expected improvement algorithm[END_REF], Lemma 5 in [START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF] or Lemma 14 in [START_REF] Jourdan | Top two algorithms revisited[END_REF]), hence we omit the proof. Lemma 12. There exists a sub-Gaussian random variable W µ such that almost surely, for all i ∈ [K] and all n such that N n,i ≥ 1,

|µ n,i -µ i | ≤ W µ log(e + N n,i ) N n,i .
In particular, any random variable which is polynomial in W µ has a finite expectation.

D.1 IDS proportions

Using Lemma 9, the optimal allocation for ε 0 -BAI are defined as

w ε0 (µ) := arg max w∈ K min i =i (µ i -µ i + ε 0 ) 2 1/w i + 1/w i . Since |i (µ)| = 1, let µ ε0 = µ ε0 (i )
where µ ε (i ) as in Lemma 9. Since we have T ε0 (µ) = T (µ ε0 ) and w ε0 (µ) = w (µ ε0 ), Lemma 6 and 8 yield that w ε0 (µ) = {w } is a singleton with unique element denotes by w which satisfies that min i∈

[K] w i > 0, i =i w i w i 2 = 1 , (8)
and

∀i ∈ [K] \ {i }, (µ i -µ i + ε 0 ) 2 1/w i + 1/w i = 2T ε0 (µ) -1 . (9)
[40] refers to [START_REF] Chen | Balancing optimal large deviations in sequential selection[END_REF] 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 [START_REF] Qin | Improving the expected improvement algorithm[END_REF][START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF][START_REF] Jourdan | Top two algorithms revisited[END_REF] with the improvement from [START_REF] You | Information-directed selection for top-two algorithms[END_REF]. Let γ > 0. Let us define the convergence time T ε0,γ , which is a random variable quantifies the number of samples required for the empirical allocations

(N n,i /N n,i ) i =i to be γ-close to (w i /w i ) i =i : T ε0,γ := inf T ≥ 1 | ∀n ≥ T, max i =i N n,i N n,i - w i w i ≤ γ . ( 10
)
Lemma 13 gives a sufficient condition to prove Theorem 1 for IDS proportions. The case ε 0 = ε 1 is a direct consequence of combining Theorem 13 and Proposition 14 in [START_REF] You | Information-directed selection for top-two algorithms[END_REF]. The proof is inspired by existing methods, e.g. Theorem 2 in [START_REF] Jourdan | Top two algorithms revisited[END_REF] or Theorem 3 in [START_REF] Qin | Improving the expected improvement algorithm[END_REF].

Lemma 13. Let ε 0 > 0, ε 1 ≥ 0 and δ ∈ (0, 1). Assume that there exists γ 1 (µ) > 0 such that for all γ ∈ (0, γ 1 (µ)], E ν [T ε0,γ ] < +∞. Using the threshold (4) in the stopping rule (3) with slack ε 1 yields an algorithm such that, for all ν

∈ D K such that |i (µ)| = 1, lim sup δ→0 E ν [τ ε1,δ ] log (1/δ) ≤ T ε0 (µ) 1 + max i =i ε 0 -ε 1 µ i -µ i + ε 1 2 . Proof. Let γ > 0. Let us define by Tγ,ε0 := inf T ≥ 1 | ∀n ≥ T, N n n -1 -w ∞ ≤ γ . Using that i =i w i w i = 1 w i -1 and i =i N n,i N n,i = n -1 N n,i -1 , it is direct to see that for all n ≥ T γ N n,i n -1 -w i = n -1 N n,i - 1 w i N n,i n -1 w i ≤ n -1 N n,i - 1 w i ≤ γ(K -1) , N n,i n -1 -w i = w i N n,i n -1 1 w i - n -1 N n,i + N n,i N n,i - w i w i ≤ 1 w i - n -1 N n,i + N n,i N n,i - w i w i ≤ γK .
Therefore, for all γ ∈ (0,

γ 1 (µ)/K], E ν [ Tγ,ε0 ] < +∞.
Let µ ε0 as in Lemma 9. Since we have T ε0 (µ) = T (µ ε0 ) and w ε0 (µ) = w (µ ε0 ), we can leverage existing results from the BAI literature, e.g. Theorem 2 in [START_REF] Jourdan | Top two algorithms revisited[END_REF] or Theorem 3 in [START_REF] Qin | Improving the expected improvement algorithm[END_REF]. The sole criterion on the stopping threshold is to be asymptotically tight (Definition 1).

Definition 1. A threshold c : N × (0, 1] → R + is said to be asymptotically tight if there exists α ∈ [0, 1), δ 0 ∈ (0, 1], functions f, T : (0, 1] → R + and C independent of δ satisfying: (1) for all δ ∈ (0, δ 0 ] and n ≥ T (δ), then c(n, δ)

≤ f (δ) + Cn α , (2) lim sup δ→0 f (δ)/ log(1/δ) ≤ 1 and (3) lim sup δ→0 T (δ)/ log(1/δ) = 0. Since C G defined in (23) satisfies C G ≈ x + log(x), it is direct to see that c(n, δ) = 2C G 1 2 log K -1 δ + 4 log 4 + log n 2
is asymptotically tight, e.g. by taking (α,

δ 0 , C) = (1/2, 1, 4), f (δ) = 2C G 1 2 log K-1 δ and T (δ) = 1.
Based on continuity arguments and using that E ν [T ε0,γ ] < +∞, the proof of Theorem 2 in [START_REF] Jourdan | Top two algorithms revisited[END_REF] yields that

lim sup δ→0 E ν [τ δ ] log (1/δ) ≤ min i =i (µ i -µ i + ε 1 ) 2 2 (1/w i + 1/w i ) -1 = T ε0 (µ) max i =i µ i -µ i + ε 0 µ i -µ i + ε 1 2 ,
where the equality uses the condition at the equilibrium ( 9). This concludes the proof.

Using Lemma 13, the proof of Theorem 1 for IDS proportions boils down to showing that E ν [T ε0,γ ] < +∞. As in [START_REF] Qin | Improving the expected improvement algorithm[END_REF][START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF][START_REF] Jourdan | Top two algorithms revisited[END_REF][START_REF] You | Information-directed selection for top-two algorithms[END_REF], 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.

E ν [T ε0,γ ] < +∞ (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 ∈ R * + , we define the sampled enough set and its arms with highest mean (when not empty) as

S L n := {i ∈ [K] | N n,i ≥ L} and I n := arg max i∈S L n µ i . (11)
In all generality I n is a set, yet we obtain I n = {i } as soon as i ∈ S L n . We define the highly and the mildly under-sampled sets

U L n := {i ∈ [K] | N n,i < √ L} and V L n := {i ∈ [K] | N n,i < L 3/4 } . (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 β.

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)

∈ I n × S L n instead of (i, j) ∈ I n × S L n \ I n .
This is due to the ε 0 regularization, which removes the need to assume that the means are distinct. Lemma 14. Let S L n and I n as in [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF]. There exists

L 0 with E µ [(L 0 ) α ] < +∞ for all α > 0 such that if L ≥ L 0 , for all n such that S L n = ∅, for all (i, j) ∈ I n × S L n such that i = j, we have µ n,i -µ n,j + ε 0 1/N n,i + 1/N n,j ≥ √ L ε 0 2 √ 2 .
Proof. Using Lemma 12 and min{N n,i , N n,j } ≥ L, we obtain

µ n,i -µ n,j ≥ µ i -µ j -W µ log(e + N n,i ) N n,i + log(e + N n,j ) N n,j ≥ -2W µ log(e + L) L ≥ - ε 0 2 ,
where the last inequality is obtained for L ≥ L 0 = L 1 -e which is defined as

L 1 = sup x | x < 16W 2 µ log(x)/ε 2 0 + e ≤ h 1 16W µ /ε 2 0 , 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) ∼ x→+∞ x log x, we have E µ [(L 0 ) α ] < +∞ for all α > 0 by using Lemma 12 (polynomial in W µ ). Then, we have

µ n,i -µ n,j + ε 0 1/N n,i + 1/N n,j ≥ ε 0 /2 1/N n,i + 1/N n,j ≥ √ L ε 0 2 √ 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 L n as in [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF]. There exists L 1 with E µ [(L 1 ) α ] < +∞ for all α > 0 such that for all L ≥ L 1 and all n ∈ N,

∀(i, j) ∈ S L n × S L n , µ n,i -µ n,j + ε 0 1/N n,i + 1/N n,j ≤ √ L(D 1 + 4W µ ) ,
where D 1 > 0 is a problem dependent constant and W µ is the random variables defined in Lemma 12.

Proof. Using Lemma 12 and N n,i ≥ L ≥ N n,j ≥ 1, we obtain

µ n,i -µ n,j + ε 0 1/N n,i + 1/N n,j ≤ N n,j |µ n,i -µ n,j + ε 0 | ≤ √ L |µ i -µ j + ε 0 | + W µ log(e + N n,i ) N n,i + log(e + N n,j ) N n,j ≤ √ L |µ i -µ j + ε 0 | + 2W µ log(e + 1) ≤ √ L(D 1 + 4W µ ) , for D 1 = max i =j |µ i -µ j + ε 0 |.
Lemma 16 shows the desired property for the EB leader. Since it corresponds to Lemma 17 in [START_REF] Jourdan | Top two algorithms revisited[END_REF], we omit the proof.

Lemma 16 (Lemma 17 in [START_REF] Jourdan | Top two algorithms revisited[END_REF]). There exists

L 2 with E ν [(L 2 ) α ] < +∞ for all α > 0 such that if L ≥ L 2 , for all n (at most polynomial in L) such that S L n = ∅, B EB n ∈ S L n implies B EB n ∈ I n .
Lemma 17 show 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 ε 0 > 0.

Lemma 17. There exists

L 3 with E ν [L 3 ] < +∞ such that if L ≥ L 3 , for all n (at most polynomial in L) such that U L n = ∅, B EB n / ∈ V L n implies C TCε0 n ∈ V L n .
Proof. In the following, we consider

U L n = ∅ (hence V L n = ∅) and B EB n / ∈ V L n . Let J n = arg max i∈V L n µ i and L 2 as in Lemma 16. Then, for L ≥ L 4/3 2 , we have B EB n ∈ J n .
Let L 0 and (L 1 , D 1 ) as in Lemmas 14 and 15. Then, for all L ≥ max{L

4/3 0 , L 4/3 2 , L 2 1 }, B EB n ∈ J n , ∀(i, j) ∈ J n × V L n , s.t. i = j, µ n,i -µ n,j + ε 0 1/N n,i + 1/N n,j ≥ L 3/8 ε 0 2 √ 2 , ∀(i, j) ∈ U L n × U L n , µ n,i -µ n,j + ε 0 1/N n,i + 1/N n,j ≤ L 1/4 (D 1 + 4W µ ) . Since J n ⊆ V L n ⊆ U L n , for all L ≥ L 3 := max{L 4/3 0 , L 4/3 2 , L 2 1 , 2 √ 2 ε0 (D 1 + 4W µ ) 8 + 1} we have ∀(i, k, j) ∈ J n × U L n × V L n , s.t. i = j, µ n,i -µ n,j + ε 0 1/N n,i + 1/N n,j > µ n,i -µ n,k + ε 0 1/N n,i + 1/N n,k . As B EB n ∈ J n , the definition C TCε0 n yields that C TCε0 n ∈ V L n .
Otherwise the above strict inequality would wield a contradiction. Using Lemma 12, we show

E F [L 3 ] ≤ E F   2 √ 2 ε 0 (D 1 + 4W µ ) 8 + 1   + E F [(L 0 ) 4/3 ] + E F [(L 2 ) 4/3 ] + E F [(L 1 ) 2 ] < +∞ ,
hence this concludes the proof.

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 E ν [N 1 ] < +∞ such that for all n ≥ N 1 and all i ∈ [K], N n,i ≥ n/K and B EB n = i .
Proof. Let L 2 and L 3 as in Lemmas 16 and 17. Therefore, for L ≥ L 4 := max{L 3 , L

4/3 2 }, for all n such that U L n = ∅, B EB n ∈ V L n or C TCε0 n ∈ V L n . We have E ν [L 4 ] < +∞.
There exists a deterministic L 5 such that for all L ≥ L 5 , L ≥ KL 3/4 . Let L ≥ max{L 5 , L 4 }.

Suppose towards contradiction that U L

KL is not empty. Then, for any 1 ≤ t ≤ KL , U L t and V L t are non empty as well. Using the pigeonhole principle, there exists some

i ∈ [K] such that N L ,i ≥ L 3/4 . Thus, we have V L L ≤ K -1. Our goal is to show that V L 2L ≤ K -2. A sufficient condition is that one arm in V L L is pulled at least L 3/4 times between L and 2L -1. If we have 2L -1 t= L 1 {B EB t , C TCε0 t } ⊆ V L t ≥ KL 3/4 , then, using that V L t ⊆ V L L , we obtain 2L -1 t= L 1 I t ∈ V L L ≥ 2L -1 t= L 1 I t ∈ V L t ≥ 2L -1 t= L 1 {B EB t , C TCε0 t } ⊆ V L t ≥ KL 3/4 ,
Therefore, there exists i ∈ V L L which is sampled L 3/4 times between L and 2L -1. In the following, we assume that

2L -1 t= L 1 {B EB t , C TCε0 t } ⊆ V L t < KL 3/4 , Since B EB t ∈ V L t or C TCε0 t ∈ V L t , we have 2L -1 t= L 1 B EB t ∈ V L t , C TCε0 t / ∈ V L t + 1 B EB t / ∈ V L t , C TCε0 t ∈ V L t > 2L -L -KL 3/4 .

Therefore, we have

Case 1:

2L -1 t= L 1 B EB t ∈ V L t , C TCε0 t / ∈ V L t > 2L -L -KL 3/4 /2 ,
or Case 2:

2L -1 t= L 1 B EB t / ∈ V L t , C TCε0 t ∈ V L t > 2L -L -KL 3/4 /2 .
Since β t (i, j) = N t,j /(N t,j + N t,i ), we obtain

1/2 ≤ β t (B EB t , C TCε0 t ) if B EB t ∈ V L t , C TCε0 t / ∈ V L t 1 -β t (B EB t , C TCε0 t ) if B EB t / ∈ V L t , C TCε0 t ∈ V L t .
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

2L -1 t= L 1 I t ∈ V L L ≥ i∈V L L j =i 2L -1 t= L 1 I t = i, (B EB t , C TCε0 t ) = (i, j) ≥ i∈V L L j =i 2L -1 t= L β t (i, j)1 (B EB t , C TCε0 t ) = (i, j) -K 2 ≥ 2L -1 t= L β t (B EB t , C TCε0 t )1 B EB t ∈ V L t , C TCε0 t / ∈ V L t -K 2 ≥ 2L -L -KL 3/4 /4 -K 2 ≥ KL 3/4 ,
where the last inequality is obtained for L ≥ L 6 + 1 with

L 6 = sup L ∈ N | 2L -L -KL 3/4 /4 -K 2 < KL 3/4 .
Therefore, there exists i ∈ V L L which is sampled L 3/4 times between L and 2L -1. Case 2. Using Lemma 46 and the above, we obtain

2L -1 t= L 1 I t ∈ V L L ≥ j∈V L L i =j 2L -1 t= L 1 I t = j, (B EB t , C TCε0 t ) = (i, j) ≥ j∈V L L i =j 2L -1 t= L (1 -β t (i, j))1 (B EB t , C TCε0 t ) = (i, j) -K 2 ≥ 2L -1 t= L (1 -β t (B EB t , C TCε0 t ))1 B EB t / ∈ V L t , C TCε0 t ∈ V L t -K 2 ≥ 2L -L -KL 3/4 /4 -K 2 ≥ KL 3/4 ,
where the last inequality is obtained for L ≥ L 6 + 1. Therefore, there exists i ∈ V L L which is sampled L 3/4 times between L and 2L -1.

Summary. We have shown V L 2L ≤ K -2. By induction, for any 1 ≤ k ≤ K, we have V L kL ≤ K -k, and finally U L KL = ∅ for all L ≥ L 7 := max{L 5 , L 4 , L 6 + 1}. Defining N 0 = KL 7 , we have E ν [N 0 ] < +∞. For all n ≥ N 0 , we let L = n/K, hence we have U n/K n = U L KL = ∅.
This concludes the proof of sufficient exploration.

Leader is best arm. Using Lemma 12, we obtain that for all n ≥ N 0 ,

∀i = i , µ n,i ≤ µ i + W µ log(e + N n,i ) N n,i ≤ µ i + W µ log(e + n/K) n/K , µ n,i ≤ µ i -W µ log(e + N n,i ) N n,i ≤ µ i -W µ log(e + n/K) n/K .
Therefore, we have B EB n = i for all n ≥ N 1 := max{N 0 , K(X 0 -e) 2 + 1} where

X 0 = sup x > 1 | x < 16W 2 µ min i =i (µ i -µ i ) 2 log(x) + e ≤ h 1 16W 2 µ min i =i (µ i -µ i ) 2 , e ,
where the last inequality is obtained by using Lemma 51 with h 1 defined therein. Since h 1 (x, e) ∼ x→+∞ x log x, we have

E ν [N 1 ] < E ν [N 0 ] + E ν [K(X 0 -e) 2 + 1] < +∞ .
This concludes the proof.

D.1.2 Empirical overall balance

As in [START_REF] You | Information-directed selection for top-two algorithms[END_REF], 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 γ > 0. There exists N 2 with E ν [N 2 ] < +∞ such that for all n ≥ N 2 N n,i n -1 2 - i =i N n,i n -1 2 ≤ γ .
Proof. Let N 1 as in Lemma 18. Then, we have for all n > N 1

N n,i n -1 = N i n,i n -1 + i =i N i N1,i n -1 , N n,i n -1 = N i n,i n -1 + j =i N j N1,i n -1 , (1 -βn (i , j)) T n (i , j) n -1 = 1 n -1 n-1 t=N1 1 (C t = j) (1 -β t (i , j)) + (1 -βN1 (i , j)) T N1 (i , j) n -1 , j =i βn (i , j) T n (i , j) n -1 = 1 n -1 n-1 t=N1 β t (i , C t ) + j =i βN1 (i , j) T N1 (i , j) n -1
Chaining the inequalities with Lemma 46, we obtain that

- K n -1 ≤ N n,i n -1 - 1 n -1 n-1 t=N1 β t (i , C t ) ≤ 2N 1 + K n -1 , - 1 n -1 ≤ N n,i n -1 - 1 n -1 n-1 t=N1 1 (C t = j) (1 -β t (i , j)) ≤ 2N 1 + 1 n -1 . Using that a 2 -b 2 = (a -b)(a + b) ≤ 2(a -b) for (a, b) ∈ (0, 1) 2 , we obtain -2 K n -1 ≤ N n,i n -1 2 - 1 n -1 n-1 t=N1 β t (i , C t ) 2 ≤ 2 2N 1 + K n -1 , -2 1 n -1 ≤ N n,i n -1 2 - 1 n -1 n-1 t=N1 1 (C t = j) (1 -β t (i , j)) 2 ≤ 2 2N 1 + 1 n -1 .
For all n > N 1 , let us denote by

G n = n-1 t=N1 β t (i , C t ) 2 - j =i n-1 t=N1 1 (C t = j) (1 -β t (i , j)) 2 .
Therefore, we have

-4K N 1 + 1 n -1 ≤ N n,i n -1 2 - i =i N n,i n -1 2 - G n (n -1) 2 ≤ 4 N 1 + K n -1 .
Direct manipulations yield that

1 2 (G n+1 -G n ) = β n (i , C n ) n-1 t=N1 β t (i , C t ) -(1 -β n (i , C n )) n-1 t=N1 1 (C t = C n ) (1 -β t (i , C n )) + β n (i , C n ) -1/2 .
Therefore, we obtain by using the above inequalities that

1 2 (G n+1 -G n ) ≤ β n (i , C n )N n,i -(1 -β n (i , C n ))N n,Cn + 2N 1 + K + 3/2 = 2N 1 + K + 3/2 , 1 2 (G n+1 -G n ) ≥ β n (i , C n )N n,i -(1 -β n (i , C n ))N n,Cn -2N 1 -K -3/2 = -2N 1 -K -3/2 ,
where we used that

β n (i , C n )N n,i = (1 -β n (i , C n ))N n,Cn since β n (i , C n ) = N n,Cn
N n,i +N n,Cn . Summing those inequalities, we obtain

G n = n-1 t=N1+1 (G t+1 -G t ) + G N1+1 ≤ (4N 1 + 2K + 3)(n -1 -N 1 ) + 1 ≥ -(4N 1 + 2K + 3)(n -1 -N 1 ) -1 ,
where we used that

G N1+1 = 2β N1 (i , C N1 ) -1 ∈ [-1, 1].
Combining everything together, we have shown that

N n,i n -1 2 - i =i N n,i n -1 2 ≤ 4 N 1 + K n -1 + (4N 1 + 2K + 3)(n -1 -N 1 ) + 1 (n -1) 2 ≥ -4K N 1 + 1 n -1 - (4N 1 + 2K + 3)(n -1 -N 1 ) + 1 (n -1) 2 .
Therefore, we have shown the desired results for n ≥ N 2 defined as

N 2 = inf n > 2 | 4K N 1 + 1 n -1 + (4N 1 + 2K + 3)(n -1 -N 1 ) + 1 (n -1) 2 ≤ γ , which satisfies E ν [N 2 ] < +∞ since it is a linear function of N 1 .
As in [START_REF] You | Information-directed selection for top-two algorithms[END_REF], 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 E ν [N 3 ] < +∞ such that for all n ≥ N 3 1 4 2(K -1) ≤ N n,i n -1 ≤ 3 4 .
Proof. Let N 2 as in Lemma 19 for γ = 1/2. Using Lemma 19, we obtain

N n,i n-1 ≤ 3 4 since 1/2 ≥ N n,i n -1 2 - i =i N n,i n -1 2 ≥ N n,i n -1 2 -1 - N n,i n -1 2 = 2 N n,i n -1 -1 .
Let Ñ2 as in Lemma 19 for γ = 1 32(K-1) . Similarly by using Lemma 19, we obtain

N n,i n-1 ≥ 1 4 √ 2(K-1) since N n,i n -1 2 ≥ - 1 32(K -1) + i =i N n,i n -1 2 ≥ - 1 32(K -1) + 1 K -1 1 - N n,i n -1 2 ≥ 1 32(K -1)
.

Taking N 3 = max{N 2 , Ñ2 } yields the result.

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 γ > 0. There exists

N 4 with E ν [N 4 ] < +∞ such that for all n ≥ N 4 1 - i =i N n,i N n,i 2 ≤ γ .
Proof. Let N 2 as in Lemma 19 for γ 32(K-1) . Let N 3 as in Lemma 20. Direct manipulation shows that, for all n ≥ N 4 = max{N 2 , N 3 },

1 - i =i N n,i N n,i 2 = n -1 N n,i 2 N n,i n -1 2 - i =i N n,i n -1 2 ≤ 32(K -1) γ 32(K -1) = γ .
This concludes the result.

D.1.3 Convergence towards optimal ratio of allocation

As in [START_REF] You | Information-directed selection for top-two algorithms[END_REF], 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 γ > 0. There exists N 5 with E ν [N 5 ] < +∞ such that for all n ≥ N 5 and all i = i ,

N n,i N n,i ≥ w i w i + γ =⇒ C TCε0 n = i . Proof. Let γ > 0. Let i = i such that N n,i N n,i ≥ w i w i + γ .
Suppose towards contradiction that

∀j = i , N n,j N n,i > w j w i .
Let γ > 0. Let N 4 as in Lemma 21 for γ. then using Lemma 21 and 8 yields that, for all n ≥ N 4 ,

γ ≥ j =i N n,j N n,i 2 -1 ≥ w i w i + γ 2 - w i w i 2 = γ γ + 2 w i w i .
Therefore, we have a contradiction if we take γ small enough (e.g. γ < γ 2 ), hence we have shown that, for all n ≥ N 4 ,

N n,i N n,i ≥ w i w i + γ =⇒ ∃j / ∈ {i , i}, N n,j N n,i ≤ w j w i .
Let N 1 as in Lemma 18. Using that B EB n = i for all n ≥ N 1 and the definition of

C TCε0 n , we known that µ n,i -µ n,i + ε 0 1/N n,i + 1/N n,i > µ n,i -µ n,j + ε 0 1/N n,i + 1/N n,j =⇒ C TCε0 n = 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 ≥ max{N 1 , N 4 }, we obtain

µ n,i -µ n,i + ε 0 µ n,i -µ n,j + ε 0 1 + N n,i /N n,j 1 + N n,i /N n,i ≥ µ n,i -µ n,i + ε 0 µ n,i -µ n,j + ε 0 1 + w i /w j 1 + (w i /w i + γ) -1 .
Let γ > 0. Using Lemmas 12 and 18, we have, for all n ≥ N 1 and all k = i ,

µ n,i -µ n,k + ε 0 µ i -µ k + ε 0 -1 ≤ W µ µ i -µ k + ε 0 log(e + N n,k ) N n,k + log(e + N n,i ) N n,i ≤ 2W µ min k =i (µ i -µ k + ε 0 ) log(e + n/K) n/K ≤ γ
for all n ≥ N 6 = K(X 0 -e) 2 + 1 which is defined as

X 0 = sup x ≥ 1 | x < 4W 2 µ γ2 min k =i (µ i -µ k + ε 0 ) 2 log x + e ≤ h 1 4W 2 µ γ2 min k =i (µ i -µ k + ε 0 ) 2 , e .
where the last inequality is obtained by using Lemma 51 with h 1 defined therein. Since

h 1 (x, y) ∼ x→+∞ x log x, we have E ν [N 6
] < +∞ since it polynomial in W µ (by using Lemma 12). Let κ > 0. We have shown that, for all n ≥ max{N 1 , N 4 , N 6 },

µ n,i -µ n,i + ε 0 µ n,i -µ n,j + ε 0 1 + N n,i /N n,j 1 + N n,i /N n,i ≥ µ i -µ i + ε 0 µ i -µ j + ε 0 1 + w i /w j 1 + (w i /w i + γ) -1 1 - γ 1 + γ = 1 + w i /w i 1 + (w i /w i + γ) -1 1 - γ 1 + γ .
where the equality uses that the transportation costs are equal at the equilibrium, i.e. [START_REF] Degenne | Impact of structure on the design and analysis of bandit algorithms[END_REF]. Taking γ small enough, we have that shown that, for all n ≥ max{N 1 , N 4 , N 6 },

N n,i N n,i ≥ w i w i + γ =⇒ µ n,i -µ n,i + ε 0 µ n,i -µ n,j + ε 0 1 + N n,i /N n,j 1 + N n,i /N n,i > 1 =⇒ C TCε0 n = i .
This concludes the proof.

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

Lemma 23. Let γ > 0. There exists N 6 with E ν [N 6 ] < +∞ such that for all n ≥ N 6 and all i = i ,

N n,i N n,i ≤ w i w i + γ .
Proof. Let γ > 0.

Let N 1 as in Lemma 18.

Let N 3 and N 5 as in Lemmas 20 and 22.

Let

M ≥ max{N 3 , N 5 , N 1 } and n > M . Let t n,i (γ) = max M, max t ∈ {M, • • • , n -1} | Nt,i N t,i < w i w i + γ/2
for all i = i . In particular, using Lemma 22, for all n > M

∀t > t n,i (γ), N t,i N t,i ≥ w i w i + γ/2 hence i = C TCε0 t , and
N tn,i(γ),i ≤ max M, w i w i + γ/2 N tn,i(γ),i
Then, we have for all n ≥ M ,

N n,i = N tn,i(γ),i + 1 i = I tn,i(γ) + n-1 t=tn,i(γ)+1 1 i = I t = C TCε0 t ≤ max M, w i w i + γ/2 N tn,i(γ),i + 1 . Using that N tn,i(γ),i ≤ N n,i , N n,i ≥ n-1 4 √ 2(K-1)
(Lemma 20) and max{a, b} ≤ a + b, we obtain that

N n,i N n,i ≤ 4(M + 1) 2(K -1) n -1 + w i w i + γ/2 ≤ w i w i + γ ,
where the last inequality holds for n ≥ N 7 = 8(M + 1) 2(K -1)/γ + 1.

Taking N 6 = max{N 3 , N 5 , N 1 , N 7 } yields the result since E ν [N 6 ] < +∞.
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 ε 0 > 0, γ > 0 and T ε0,γ as in [START_REF] Degenne | Pure exploration with multiple correct answers[END_REF]. Under the EB-TC ε0 sampling rule with IDS proportions, we have E ν [T ε0,γ ] < +∞.

Proof. Let γ > 0 and γ. Let N 4 and N 6 as in Lemmas 21 and 23 for γ. Then, using Lemmas 21 and 23, we have for all n ≥ max{N 4 , N 6 },

N n,i N n,i 2 ≥ 1 - j / ∈{i,i } N n,j N n,i 2 - γ ≥ 1 - j / ∈{i,i } w j w i + γ 2 - γ = w i w i 2 -   (K -2)γ + 2 j / ∈{i,i } w j w i + 1   γ
where the equality uses [START_REF] Degenne | Impact of structure on the design and analysis of bandit algorithms[END_REF]. Therefore, we have shown that for all n ≥ max{N 4 , N 6 },

N n,i N n,i ≥ w i w i 1 - w i w i 2   (K -2)γ + 2 j / ∈{i,i } w j w i + 1   γ ≥ w i w i -γ ,
where the last inequality holds for γ small enough as a function of γ and w . Therefore, we obtained

max i =i N n,i N n,i - w i w i ≤ γ , which concludes the proof, i.e. E ν [T γ ] < +∞.
Combining Lemmas 13 and 24 concludes the first part of Theorem 1, i.e.

lim sup δ→0 E ν [τ ε1,δ ] log(1/δ) ≤ T ε0 (µ) 1 + max i =i ε 0 -ε 1 µ i -µ i + ε 1 2 .

D.2 Fixed proportions

Using Lemma 9, the β-optimal allocation for ε 0 -BAI are defined as

w ε0,β (µ) := arg max w∈ K ,w i =β min i =i (µ i -µ i + ε 0 ) 2 1/β + 1/w i .
Since |i (µ)| = 1, let µ ε0 = µ ε0 (i ) where µ ε (i ) as in Lemma 9. Since we have T ε0,β (µ) = T β (µ ε0 ) and w ε0,β (µ) = w β (µ ε0 ), Lemma 6 and 8 yield that w ε0,β (µ) = {w β } is a singleton with unique element denotes by w β which satisfies that min i∈[K] w β,i > 0 and

∀i ∈ [K] \ {i }, (µ i -µ i + ε 0 ) 2 1/β + 1/w β,i = 2T ε0,β (µ) -1 . (13)
When considering fixed proportions β, 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 β.

Convergence time Let γ > 0. Let us define the convergence time T ε0,β,γ , which is a random variable quantifies the number of samples required for the empirical allocations N n to be γ-close to w β :

T ε0,β,γ := inf T ≥ 1 | ∀n ≥ T, N n n -1 -w β ∞ ≤ γ . (14)
Lemma 25 gives a sufficient condition for asymptotic β-optimality. The case ε 0 = ε 1 is a direct consequence of existing methods, e.g. Theorem 2 in [START_REF] Jourdan | Top two algorithms revisited[END_REF] or Theorem 3 in [START_REF] Qin | Improving the expected improvement algorithm[END_REF].

Lemma 25. Let ε 0 > 0, ε 1 ≥ 0 and δ ∈ (0, 1). Assume that there exists γ 1 (µ) > 0 such that for all γ ∈ (0, γ 1 (µ)], E ν [T ε0,β,γ ] < +∞. Using the threshold (4) in the stopping rule (3) with slack ε 1 yields an algorithm such that, for all ν ∈ D K such that |i (µ

)| = 1, lim sup δ→0 E ν [τ ε1,δ ] log (1/δ) ≤ T ε0,β (µ) 1 + max i =i ε 0 -ε 1 µ i -µ i + ε 1 2 .
Proof. The proof is the same of the ones of Lemma 13. The sole difference is that we have w β,i = β by definition.

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 E ν [N 1 ] < +∞ such that for all n ≥ N 1 and all i ∈ [K], N n,i ≥ n/K and B EB n = 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 = j,

min{β t (i, j), 1 -β t (i, j)} = min{β, 1 -β} > 0 .
Convergence towards optimal allocation Combining Lemma 26 with the proof of Lemma F.8 in [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF] yields Lemma 27.

Lemma 27. Let γ > 0. There exists

N 2 with E µ [N 2 ] < +∞ such that for all n ≥ N 2 , N n,i n -1 -β ≤ γ .
Combining Lemmas 26 and 27 with the proof of Lemma F.9 in [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF] yields Lemma 28.

Lemma 28. Let γ > 0. There exists N 5 with E ν [N 5 ] < +∞ such that for all n ≥ N 5 and all i = i ,

N n,i n -1 ≥ w β,i + γ =⇒ C TCε0 n = i .
Combining Lemmas 27 and 28 with the proof of Lemma F.10 in [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF] yields Lemma 29.

Lemma 29. Let γ > 0. There exists

N 6 with E ν [N 6 ] < +∞ such that for all n ≥ N 6 , N n n -1 -w β ∞ ≤ γ .
Lemma 30 is a direct corollary of Lemma 29.

Lemma 30. Let ε 0 > 0, β ∈ (0, 1), γ > 0 and T ε0,β,γ as in [START_REF] Gabillon | Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence[END_REF]. Under the EB-TC ε0 sampling rule with fixed proportions β, we have E ν [T ε0,β,γ ] < +∞.

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

lim sup δ→0 E ν [τ ε1,δ ] log(1/δ) ≤ T ε0,β (µ) 1 + max i =i ε 0 -ε 1 µ i -µ i + ε 1 2 .

E Non-asymptotic analysis

Let ε 0 > 0, β ∈ (0, 1) and δ ∈ (0, 1). In this section, we provide a non-asymptotic analysis of EB-TC ε0 with fixed proportions β and slack ε 0 > 0 when combined with the stopping rule (3) with parameters (ε 0 , δ). In practice, we will mostly be interested in the case β = 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 ν ∈ D K having mean parameter µ ∈ R K . In particular, our analysis holds when several arms have the largest mean µ .

E.1 Proof of Lemma 5

Let s ≥ 0. For all n > K and δ ∈ (0, 1], let E n,δ = E 1 n,δ ∩ E 2 n,δ with (E 1 n,δ ) n>K and (E 2 n,δ ) n>K as in ( 24) and ( 25), i.e.

E 1 n,δ = ∀k ∈ [K], ∀t ≤ n, |µ t,k -µ k | < 2f 1 (n, δ) N t,k , E 2 n,δ = ∀(i, k) ∈ [K] 2 s.t. i = k, ∀t ≤ n, |(µ t,i -µ t,k ) -(µ i -µ k )| 1/N t,i + 1/N t,k < 2f 2 (n, δ) ,
where

f 2 (x, δ) = log(1/δ) + (1 + s) log(x) and f 2 (x, δ) = log(1/δ) + (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 E 1 n,δ , for all t ∈ [n] \ [K] let B EB t = k. Then, ∀i = k, 1 (µ i > µ k ) min{N t,k , N t,i } ≤ 8f 1 (n, δ) (µ i -µ k ) 2 . Proof. Under E 1 n,δ , for all t ∈ [n] \ [K], let B EB t = k.
Then, for all i = k, we have

µ i - 2f 1 (n, δ) min{N t,k , N t,i } ≤ µ i - 2f 1 (n, δ) N t,i ≤ µ t,i ≤ µ t,k ≤ µ k + 2f 1 (n, δ) N t,k ≤ µ k + 2f 1 (n, δ) min{N t,k , N t,i } .
Re-ordering the above equations for i such that µ i > µ k yields the result.

Lemma 32. Let ε ≥ 0, ∆ µ (ε) = min k / ∈Iε(µ) ∆ k and C µ,ε0 (ε) = max{2∆ µ (ε) -1 -ε -1 0 , ε -1 0 } 2 . Let A ε0,ε,i = 2/∆ µ (ε) 2 for all i ∈ i (µ), A ε0,ε,i = C µ,ε0 (ε) for all i ∈ I ε (µ) \ i (µ), otherwise A ε0,ε,i = max{C µ,ε0 (ε), 2/∆ 2 i }. For all n > K, under event E n,δ , for all t ∈ [n] \ [K] such that B EB t / ∈ I ε (µ), there exists i t ∈ [K] such that T t (i t ) ≤ 4f 2 (n, δ) min{β, 1 -β} A ε0,ε,it + 3(K -1)/2 and T t+1 (i t ) = T t (i t ) + 1 . Proof. Let ∆ i = µ -µ i and ∆ max = max i∈[K] ∆ i . When ε ≥ ∆ max , we have I ε (µ) = ∅, hence
the above result holds trivially since the event B EB t / ∈ I ε (µ) cannot happen. Let ε ∈ [0, ∆ max ), i.e. I ε (µ) = ∅. We will consider in two distinct cases since

{B t / ∈ I ε (µ)} = {B t / ∈ I ε (µ), C t ∈ i (µ)} ∪ {B t / ∈ I ε (µ), C t / ∈ i (µ)} . Case 1. Let t ∈ [n] \ [K] such that (B EB t , C TCε0
t ) = (i, j) with i / ∈ I ε (µ) and j ∈ i (µ). Using Lemmas 46 and 31, we obtain

min{β, 1 -β} (min{T t (i), T t (j)} -3(K -1)/2) ≤ min{N t,i , N t,j } ≤ 8f 1 (n, δ) ∆ 2 i ≤ 8f 2 (n, δ) ∆ 2 i ,
which can be rewritten as

min{T t (i), T t (j)} ≤ 8f 2 (n, δ) min{β, 1 -β}∆ 2 i + 3(K -1)/2 . Let us define ∆ µ (ε) = min k / ∈Iε(µ) ∆ k , and ∀i / ∈ I ε (µ), D ε,i = 2/∆ 2 i and ∀i ∈ i (µ), D ε,i = 2/∆ µ (ε) 2 .
The above shows that there exists

k t ∈ I ε (µ) ∪ i (µ) such that T t (k t ) ≤ 4f 2 (n, δ) min{β, 1 -β} D ε,kt + 3(K -1)/2 and T t+1 (k t ) = T t (k t ) + 1 . Case 2. Let t ∈ [n] \ [K] such that (B EB t , C TCε0 t ) = (i, j) with i / ∈ I ε (µ) and j / ∈ i (µ). Let i 0 ∈ i (µ). Using the TC challenger, we obtain ε 0 -∆ i 1/N t,i + 1/N t,i0 + 2f 2 (n, δ) ≥ µ t,i -µ t,i0 + ε 0 1/N t,i + 1/N t,i0 ≥ µ t,i -µ t,j + ε 0 1/N t,i + 1/N t,j ≥ ε 0 min{N t,i , N t,j }/2 .
Using Lemma 31, we obtain

1 1/N t,i + 1/N t,i0 ≤ min{N t,i , N t,i0 } ≤ 8f 1 (n, δ) ∆ 2 i ≤ 8f 2 (n, δ) ∆ 2 i .
By distinguishing between ε 0 > ∆ i and ε 0 ≤ ∆ i and using that ∆ i > 0, we have

ε 0 -∆ i 1/N t,i + 1/N t,i0 + 2f 2 (n, δ) ≤ max{2ε 0 /∆ i -1, 1} 2f 2 (n, δ) .
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)} ≤ max 2 ∆ i - 1 ε 0 2 , 1 ε 2 0 4f 2 (n, δ) min{β, 1 -β} + 3(K -1)/2 . Let us define C µ,ε0 (ε) = max{2∆ µ (ε) -1 -ε -1 0 , ε -1 0 } 2 .
The above shows that, there exists k t / ∈ i (µ) such that

T t (k t ) ≤ 4f 2 (n, δ) min{β, 1 -β} C µ,ε0 (ε) + 3(K -1)/2 and T t+1 (k t ) = T t (k t ) + 1 .
Summary. Let us define (A ε0,ε,i ) i∈[K] as in the statement of Lemma 32. Under E n,δ , we have show that, when B t / ∈ I ε (µ), there exists i t ∈ [K] such that

T t (k t ) ≤ 4f 2 (n, δ) min{β, 1 -β} A ε,ε0,it + 3(K -1)/2 and T t+1 (k t ) = T t (k t ) + 1} .
For all n > K, under event E n,δ , combining Lemma 4 and 32 for

A t (n, δ) = {B EB t / ∈ I ε (µ)} and D i (n, δ) = 4f2(n,δ) min{β,1-β} A ε0,ε,i + 3(K -1)/2 yields that n t=K+1 1 B EB t / ∈ I ε (µ) ≤ 4f 2 (n, δ) min{β, 1 -β} H µ,ε0 (ε) + 3K(K -1)/2 .
where we used that i∈[K] A ε0,ε,i = H µ,ε0 (ε) where H µ,ε0 (ε) is defined in [START_REF] Bubeck | Pure Exploration in Finitely Armed and Continuous Armed Bandits[END_REF]. To conclude the proof of Lemma 5, we use that

n t=K+1 1 B EB t / ∈ I ε (µ) = n -1 - i∈Iε(µ) j
T n (i, j) .

Let f1 (n, δ) and f2 (n, δ) defined as in ( 26) and [START_REF] Komiyama | Minimax optimal algorithms for fixed-budget best arm identification[END_REF]. Using Lemma 50, we have f1 (n, δ) ≤ f2 (n, δ). 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 Ẽn,δ = Ẽ1 n,δ ∩ Ẽ2 n,δ with ( Ẽ1 n,δ ) n>K and ( Ẽ2 n,δ ) n>K as in ( 27) and [START_REF] Lattimore | Bandit Algorithms[END_REF].

Lemma 33. Let δ ∈ (0, 1], ε ≥ 0 and H µ,ε0 (ε) as in [START_REF] Bubeck | Pure Exploration in Finitely Armed and Continuous Armed Bandits[END_REF]. For all n > K, under the event Ẽn,δ ,

i∈Iε(µ) j T n (i, j) ≥ n -1 - 4H µ,ε0 (ε) min{β, 1 -β} f2 (n, δ) + 3K(K -1)/2 . E.2 Proof of Theorem 2 Let s > 1. For all n > K, let E n = E 1 n,1 ∩ E 2 n,1
with (E 1 n,δ ) n>K and (E 2 n,δ ) n>K as in ( 24) and ( 25). Using Lemma 45, we know that n>K P

ν (E n ) ≤ K(K+1) 2 ζ(s).
Let ε 0 > 0, ε 1 ≥ ε 0 and δ ∈ (0, 1). Since ε 1 ≥ ε 0 , and using the definition of the stopping rule (3), it is direct to see that

E ν [τ ε1,δ ] ≤ E ν [τ ε0,δ ].
Suppose that we have constructed a time T (δ) > K be such that for n ≥ T (δ), E n ⊂ {τ ε0,δ ≤ n} Then, Lemma 47 yields

E ν [τ ε0,δ ] ≤ T (δ) + K(K + 1) 2 ζ(s) .
We will construct an infinite number of times {T (δ, u)} u∈U such that the above property holds, hence taking the infimum yields

E ν [τ ε0,δ ] ≤ inf u∈U T (δ, u) + K(K + 1) 2 ζ(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 =i w ε0,1/2 (µ, i) j by a fixed value x ∈ [0, (K -1) -1 ] for all i ∈ I ε (µ).

Theorem 5. Let ε 0 > 0, ε 1 ≥ ε 0 and δ ∈ (0, 1). Using the threshold (4) in the stopping rule (3) with error ε 1 , the EB-TC ε0 algorithm with fixed proportions β = 1/2 is (ε 1 , δ)-PAC and satisfies that, for all

ν ∈ D K , E ν [τ ε1,δ ] ≤ E ν [τ ε0,δ ] and E ν [τ ε0,δ ] ≤ inf (ε,x)∈[0,ε0]×[0,(K-1) -1 ] max {T µ,ε0 (δ, ε, x) + 1, S µ,ε0 (ε, x)} + ζ(s) K(K + 1) 2 ,
where

T µ,ε0 (δ, ε, x) = sup n | n -1 ≤ 2(1 + γ) 2 i∈Iε(µ) T ε0,1/2 (µ, i) (1 -x) dµ,ε 0 (ε,x) c(n -1, δ) + (2 + s) log n 2 , S µ,ε0 (ε, x) = h 1 4(2 + s)(1 + γ -1 ) a µ,ε0 (ε, x)v µ,ε0 (ε) H µ,ε0 (ε), (1 + γ -1 )(3K 2 /4 + 1) a µ,ε0 (ε, x)v µ,ε0 (ε) + 1 , v µ,ε0 (ε) = min i∈Iε(µ) T ε0,1/2 (µ, i) i∈Iε(µ) T ε0,1/2 (µ, i) a µ,ε0 (ε, x) = min i∈Iε(µ) (1 -x) dµ,ε 0 (x,i) max{min j =i w ε0,1/2 (µ, i) j , x/2} , d µ,ε0 (ε, x) = max i∈Iε(µ) d µ,ε0 (x, i) with d µ,ε0 (x, i) = |{j = i | w ε0,1/2 (µ, i) j < x/2}| ,
where γ ∈ (0, 1/2] and s > 1 are analysis parameters. T ε0,1/2 (µ, i) and w ε0,1/2 (µ, i) are defined in (1), H µ,ε0 (ε) in (5), ζ is the Riemann ζ function and h 1 (z, y) = zW -1 (log(z) + y/z) is defined in Lemma 51 and satisfies that h 1 (z, y) ≈ x log(z) + y + log(log(z) + y/z).

Proof. Let ε ∈ [0, ε 0 ] be an analysis parameter, and

I ε = |I ε (µ)|. Let v ∈ ˚ Iε defined as ∀i ∈ I ε (µ), v i = T ε0,1/2 (µ, i) j∈Iε(µ) T ε0,1/2 (µ, j)
, hence min i∈Iε(µ)

v i = v µ,ε0 (ε)
.

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 µ > 0 such that for all n ≥ T µ such that E n ∩ {n < τ ε1,δ } holds true, there exists i 0 ∈ I ε (µ) and t ≤ n with B EB t = i 0 , which satisfies

1/N i0 t,i0 + 1/N i0 t,C TCε 0 t ≤ D 0 v i0 (n -1) 1/β + 1/w β (i 0 ) C TCε 0 t . (15)
Before proving Lemma 34, we show how it can be used to conclude. Based on Lemma 34, let D 0 > 0, T µ > 0, n > T µ such that E n ∩ {n < τ ε1,δ } holds true, i 0 and t ≤ n such that as B EB t = i 0 and

1/N i0 t,i0 + 1/N i0 t,C TCε 0 t ≤ D 0 v i0 (n -1) 1/β + 1/w β (i 0 ) C TCε 0 t .
Using the stopping rule (3) with error ε 0 , t ≤ n < τ ε1,δ , B EB t = ît = i 0 and the definition of the TC ε0 challenger in (2) with slack ε 0 , we obtain

2c(n -1, δ) ≥ min i =i0 µ t,i0 -µ t,i + ε 0 1/N t,i0 + 1/N t,i ≥ µ i0 -µ C TCε 0 t + ε 0 1/N t,i0 + 1/N t,C TCε 0 t -2(2 + s) log n ≥ 1/β + w β (i 0 ) -1 C TCε 0 t 1/N i0 t,i0 + 1/N i0 t,C TCε 0 t 2T ε0,β (µ, i 0 ) -1 -2(2 + s) log n ≥ 2(n -1) D 0 i∈Iε(µ) T ε0,β (µ, i) -2(2 + s) log n .
The third inequality is obtained since E n holds. The fourth inequality is obtained since

N i0 t,i ≥ N i0 t,i
for all i ∈ [K] and by using Lemmas 8 and 9. The last inequality is obtained by Lemma 34 and using the definition of v i0 .

Let's define T (δ, D 0 ) :

= sup{n > K | n -1 < D 0 i∈Iε(µ) T ε0,β (µ, i)( c(n -1, δ) + (2 + s) log n) 2 }
. Therefore, we have E n ∩ {n < τ ε0,δ } = ∅ (i.e. E n ⊂ {τ ε0,δ ≤ n}) for all n ≥ max{T (δ, D 0 ), T µ + 1}. This concludes the construction.

To conclude the proof, we will show that Lemma 34 for many choices of D 0 and T µ .

Vanilla Proof of Lemma 34. Let g ε (n) = 4Hµ,ε 0 (ε) min{β,1-β} (2 + s) log n + 3K(K -1)/2. Using Lemma 5, under the event E n , i∈Iε(µ) j T n (i, j) ≥ n -1 -g ε (n) .
Therefore, the pigeonhole principle yields that there exists

i 0 ∈ I ε (µ) such that j T n (i 0 , j) ≥ v i0 (n -1 -g ε (n)) .
The crux of the problem is to relate N i0 t,Ct /(t -1) and w β (i 0 ) C TCε 0 t . To do so, we use the approach of [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF] that builds on the idea behind the proof for APT from [START_REF] Locatelli | An optimal algorithm for the thresholding bandit problem[END_REF]: 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 = i 0 such that

N i0 n,k1 ≥ w β (i 0 ) k1 1 -β j =i0 N i0 n,j , (16)
and we take such k 1 . Let t 1 := sup {t < n | (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 t1 = B t1 then N i0 t1,k1 = N i0 n,k1 , otherwise N i0 t1,k1 = N i0 n,k1 -1.
In both cases, we have N i0 t1,k1 ≥ N i0 n,k1 -1. Combined with the above and using that w β (i 0 ) k1 ≤ 1-β and v i0 ≤ 1, we obtain

N i0 t1,k1 ≥ N i0 n,k1 -1 ≥ w β (i 0 ) k1 1 -β j =i0 N i0 n,j -1 ≥ w β (i 0 ) k1   j =i0 T n (i 0 , j) - K -1 2(1 -β)   -1 ≥ w β (i 0 ) k1 v i0 (n -1) -(1 -β)v i0 g ε (n) - K + 1 2 ≥ w β (i 0 ) k1 v i0 (n -1) -h ε (n) , with h ε (n) = 4(1 -β)H µ,ε0 (ε) min{β, 1 -β} f 2 (n) + (1 -β)3K(K -1)/2 + K + 1 2 .
Let w i0,-> 0 be a lower bound on w β (i 0 ) k1 , e.g. w i0,-= min i =i0 w β (i 0 ) i . For instances µ such that w β (i 0 ) k1 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 i0 t1,i0 + 1/N i0 t1,k1 ≤ 1 v i0 (n -1) 1/β + v i0 (n -1) N i0 t1,k1 N i0 t1,k1 N i0 t1,i0 + 1 ,
which is a suboptimal step which artificially introduces 1/β.

Let γ ∈ (0, 1/2]. It remains to control both terms. First, we obtain

1/β + v i0 (n -1) N i0 t1,k1 ≤ 1/β + 1 w β (i 0 ) k1 -hε(n) vi 0 (n-1) ≤ (1 + γ) 1/β + 1/w β (i 0 ) k1 , for all n > C 1 (w i0,-, v µ,ε0 (ε)
). The last inequality is obtained by definition of

C 1 (w, v) := sup n ≥ 1 | n -1 < h ε (n) wv 1 + γ -1 , (17)
which ensures that, for all n > C 1 (w i0,-, v µ,ε0 (ε)), the last condition of the equivalence

w β (i 0 ) k1 - h ε (n) v i0 (n -1) ≥ (1 + γ) -1 w β (i 0 ) k1 ⇐⇒ n -1 ≥ h ε (n) v i0 w β (i 0 ) k1 1 + γ -1
is satisfied since w β (i 0 ) k1 ≥ w i0,-, v i0 ≥ v µ,ε0 (ε) and n > C 1 (w i0,-, v µ,ε0 (ε)).

Second, using Lemma 46, we can show that

N i0 t1,i0 ≥ T t1 (i 0 , k 1 ) -N i0 t1,k1 ≥ βT t1 (i 0 , k 1 ) -1 ≥ β 1 -β N i0 t1,k1 - 1 1 -β .
Then, re-ordering the above and using that N i0 t1,k1 ≥ w β (i 0 ) k1 v i0 (n -1) -h ε (n), we obtain

N i0 t1,k1 N i0 t1,i0 + 1 ≤   β 1 -β - 1 (1 -β) w β (i 0 ) k1 v i0 (n -1) -h ε (n)   -1 + 1 ≤ (1 + γ)/β , for all n > C 2 (w i0,-, v µ,ε0 (ε)).
The last inequality is obtained by definition of

C 2 (w, v) := sup n ∈ N | n -1 < 1 wv h ε (n) + γ + 1 -β βγ , (18)
which ensures that, for all n > C 2 (w i0,-, v µ,ε0 (ε)), the last condition of the equivalence

  β 1 -β - 1 (1 -β) w β (i 0 ) k1 v i0 (n -1) -h ε (n)   -1 + 1 ≤ (1 + γ)/β ⇐⇒ 1 w β (i 0 ) k1 v i0 (n -1) -h ε (n) ≤ βγ γ + 1 -β ⇐⇒ n -1 ≥ 1 w β (i 0 ) k1 v i0 h ε (n) + γ + 1 -β βγ is satisfied since w β (i 0 ) k1 ≥ w i0,-, v i0 ≥ v µ,ε0 (ε) and n > C 2 (w i0,-, v µ,ε0 (ε)).
Let T µ ≥ max k∈ [START_REF] Avner | Decoupling exploration and exploitation in multi-armed bandits[END_REF] C k (min i∈Iε(µ) w i,-, v µ,ε0 (ε)) and D 0 = (1 + γ) 2 /β. In summary, we have shown that for all n > T µ , there exists i 0 ∈ I ε (µ) and t 1 ≤ n with B t1 = i 0 and such that (15) holds.

For β = 1/2, using that K ≥ 2, 1 < 1 + γ -1 and 5/2 + γ -1 ≤ 3(1 + γ -1 )/2 (since γ ∈ (0, 1/2]), we obtain that

max i∈[2] C i (w, v) ≤ sup n ≥ 1 | n -1 < 1 + γ -1 wv 4(2 + s)H µ,ε0 (ε) log n + 3K 2 /4 + 1 < h 1 4(2 + s)(1 + γ -1 ) wv H µ,ε0 (ε), (1 + γ -1 )(3K 2 /4 + 1) wv + 1 ,
where the last inequality uses Lemma 51 and h 1 (x, y) defined therein.

Using w i0,-= min i =i0 w β (i 0 ) i and β = 1/2, the first part of Theorem 5 (i.e. x = 0) is obtained by taking the infimum over

(ε, x) ∈ [0, ε 0 ] × {0}.
Refined Proof of Lemma 34. When considering large K or instances with unbalanced β-optimal allocation, min i0∈Iε(µ) min i =i0 w β (i 0 ) i can become arbitrarily small, hence a dependence in its inverse is undesired. Thanks to the refined analysis from [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF], we can clip it with a value of our choosing which is away from zero.

Let x ∈ (0, 1/(K -1)] be an allocation threshold and

d µ (x, i) := |{j ∈ [K] \ {i} | w β (i) j < (1 -β)x}| for all i ∈ I ε (µ).
The equation ( 16) is only informative when (1)

w β (i 0 ) k1 ≥ (1 -β)x or (2) w β (i 0 ) k1 < (1 -β)x and N i0 n,k1 ≥ x j =i0 N i0 n,j . The problematic case occurs when (3) w β (i 0 ) k1 < (1 -β)x and N i0 n,k1 < x j =i0 N i0 n,j . When w β (i 0 ) k1 ≥ (1 -β)x, we can use the above computations by considering w i0,-= max{(1 - β)x, min i =i0 w β (i 0 ) i }.
When w β (i 0 ) k1 < (1 -β)x and N i0 n,k1 ≥ x j =i0 N i0 n,j , the above proof can be conducted by using (1 -β)x instead of w β (i 0 ) k1 since we will obtain that

N i0 t1,k1 ≥ (1 -β)xv i0 (n -1) -h ε (n) and 1/β + 1 (1 -β)x ≤ 1/β + 1/w β (i 0 ) k1 .
Then, we can likewise consider w i0,-= max{(1 -β)x, min i =i0 w β (i 0 ) i } to conclude.

When w β (i 0 ) k1 < (1 -β)x and N i0 n,k1 < x j =i0 N i0 n,j , as in ( 16), the pigeonhole principle yields that there exists k

2 ∈ [K] \ {i 0 , k 1 } such that N i0 n,k2 ≥ w β (i 0 ) k2 1 -β -w β (i 0 ) k1 j / ∈{i0,k1} N i0 n,j ≥ (1 -x)w β (i 0 ) k2 1 -β j =i0 N i0 n,j .
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 β (i 0 ) k2 < (1 -β)x and N i0 n,k2 < x j / ∈{i0,k1} N i0 n,j , 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∈[d] of such arms, where k d is the first arm for which either [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF]

w β (i 0 ) k d ≥ (1 -β)x or (2) w β (i 0 ) k d < (1 -β)x and N i0 n,k d ≥ x j / ∈{i0}∪{ka} a∈[d-1] N i0 n,j
holds. This means that for all a ∈ [d -1], we have w β (i 0 ) ka < (1 -β)x and

N i0 n,ka < x j / ∈{i0}∪{k b } b∈[a-1]
N i0 n,j .

Using the pigeonhole principle for

i ∈ [K] \ {i 0 } ∪ {k a } a∈[d-1] yields that k d satisfies N i0 n,k d ≥ w β (i 0 ) k d 1 -β -a∈[d-1] w β (i 0 ) ka j / ∈{i0}∪{k b } b∈[a-1] N i0 n,j ,
Using a simple recurrence on the arms {k a } a∈[d-1] , we obtain that

j / ∈{i0}∪{k b } b∈[a-1] N i0 n,j ≥ (1 -x) d-1 j =i0 N i0 n,j . Let t d := sup {t < n | (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∈[d-1] = {i ∈ [K] \ {i 0 } | w β (i 0 ) i < (1 -β)x}, i.e. d -1 ≤ d µ (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 µ,ε (x) = max i∈Iε(µ) d µ (x, i). Using that

(1 -x) d-1 ≥ (1 -x) dµ(x,i0) ≥ (1 -x) dµ,ε(x) , w i0,-= (1 -x) dµ(x,i0) max{(1 -β)x, min i =i0 w β (i 0 ) i } ,
we can conclude the proof by taking

T µ ≥ max k∈[2] C k (min i∈Iε(µ) w i,-, v µ,ε0 (ε)) and D 0 = (1+γ) 2 β(1-x) dµ,ε(x) .
In other words, we have shown that n > T µ , there exists i 0 ∈ I ε (µ) and t d ≤ n with B t d = i 0 and such that (15) holds. Using β = 1/2, the second part of Theorem 5 is obtained by taking the infimum over (ε, x) ∈ [0, ε 0 ] × (0, 1/(K -1)].

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 Ẽn = Ẽ1 n,1 ∩ Ẽ2 n,1 with ( Ẽ1 n,δ ) n>K and ( Ẽ2 n,δ ) n>K as in ( 27) and ( 29). Let us define

f1 (n) = 1 2 W -1 (2s log n + 2 log(2 + log n) + 2) , f2 (n) = W -1 (s log n + 2 log (2 + log n) + 2) .
Using Lemma 50, we know that f1 (n) ≤ f2 (n). Then, we will be able to show

E ν [τ δ ] ≤ inf (ε,x)∈[0,ε0]×[0,1/(K-1)] max Tµ,ε0 (δ, ε, x) + 1, Sµ,ε0 (ε, x) + ζ(s)K(K + 1)/2 ,
where

Tµ,ε0 (δ, ε, x) = sup n | n -1 ≤ 2(1 + γ) 2 i∈Iε(µ) T ε0,1/2 (µ, i) (1 -x) dµ,ε 0 (ε,x) c(n -1, δ) + f2 (n) 2 , Sµ,ε0 (ε, x) = h1 4(1 + γ -1 ) a µ,ε0 (ε, x)v µ,ε0 (ε) H µ,ε0 (ε), (1 + γ -1 )(3K 2 /4 + 1) a µ,ε0 (ε, x)v µ,ε0 (ε) + 1 , with h1 (z, y) > sup n ≥ 1 | n < z f2 (n) + y . Using Lemma 49, we obtain that n ≥ z f2 (n) + y ⇐⇒ n -y z -log(n -y) ≥ s log n + 2 log (2 + log n) + 2 -log z ⇐= n z(1 + s) -log n z(1 + s) ≥ log(1 + s) + s s + 1 log z + 1 1 + s (2 log (2 + log n) + 2 + y z ) .
Therefore, we can consider h1 (z, y) ≥ z(1 + s)h 2 (z, y) with

h 2 (z, y) = sup x | x -log x - 2 1 + s log(log x + 2 + log(z(1 + s))) < C(z, y)
where C(z, y) = y (1+s)z + s s+1 log z + log(1 + s) + 2 1+s . Therefore, we will obtain a mulitplicative factor (1 + s) instead of (2 + s) in front of H µ,ε0 (ε). This improvement is rather mild, hence we don't elaborate on it further.

F Probability of error and simple regret

Let ε 0 > 0 and β ∈ (0, 1). In Appendix F, we provide an analysis on the probability of error and the simple regret of EB-TC ε0 with fixed proportions β and slack ε 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 ε0 (Theorem 7). Then, by using Theorem 6, we prove that the policy pulling arm î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 β = 1/2. Theorem 3 and Corollary 1 is a corollary of Theorem 6 up to some additional computations on the complexities (H i (µ, ε 0 )) i∈[Cµ-1] , which we will detail below. Theorem 6 provides upper bound on P ν (î n / ∈ I ε (µ)) holding for any time n and any error ε ≥ 0, and upper bound on E ν [µ -µ în ] holding for any time n.

Theorem 6. Let ε 0 > 0. For all ε ≥ 0, let i µ (ε) = i if ε ∈ [∆ i , ∆ i+1 ) and i ∈ [C µ -1], otherwise i µ (ε) = C µ . For all i ∈ [C µ -1], let C i (ε 0 ) = 2∆ -1 i -ε -1 0 and C i,j (ε 0 ) = 2 ∆j /ε0+1 ∆i-∆j + 3ε -1 0 . For all i ∈ [C µ -1], let H i (µ, ε 0 ) := min j∈[i] max{ Hi,j (µ, ε 0 ), Hi,j (µ, ε 0 )} where Hi,j (µ, ε 0 ) := |i (µ)| max √ 2∆ -1 j+1 , C i+1,j (ε 0 ) 2 + max {C j+1 (ε 0 ), C i+1,j (ε 0 )} 2   j k=2 |C µ (k)| + Cµ k=i+1 |C µ (k)|   + i k=j+1 |C µ (k)| max C j+1 (ε 0 ), C i+1,j (ε 0 ), √ 2∆ -1 k 2 , Hi,j (µ, ε 0 ) := 2|i (µ)| ∆ 2 j+1 + max C j+1 (ε 0 ), ε -1 0 2 j k=2 |C µ (k)| + 2 j k=1 |C µ (k)| (∆ i+1 -∆ j ) 2 + Cµ k=j+1 |C µ (k)| max C j+1 (ε 0 ), ε -1 0 , √ 2∆ -1 k 2 .
The EB-TC ε0 algorithm with fixed proportions β = 1/2 satisfies that, for all ν ∈ D K and all n ≥ D µ , if the algorithm has not stopped yet, then

∀ε ≥ 0, P ν (î n / ∈ I ε (µ)) ≤ 1 (ε < ∆ max ) K(K + 1) 2 e 2 (2 + log n) 2 p n -5K 2 /2 8H iµ(ε) (µ, ε 0 ) , E ν [µ -µ în ] ≤ K(K + 1) 2 e 2 (2 + log n) 2 i∈[Cµ-1] (∆ i+1 -∆ i )p n -5K 2 /2 8H i (µ, ε 0 ) .
where p(x) = x exp(-x) and

D µ = 8H 1 (µ, ε 0 )h 2 8H 1 (µ, ε 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 (ε 0 ) = 2∆ -1 min -ε -1 0 and C 2,1 (ε 0 ) = 2∆ -1 min + 3ε -1 0 . Then, we obtain H 1 (µ, ε 0 ) = H1,1 (µ, ε 0 ) = K(2∆ -1 min + 3ε -1 0 ) 2 since H1,1 (µ, ε 0 ) = 4|i (µ)|∆ -2 min + Cµ k=2 |C µ (k)| max C 2 (ε 0 ), ε -1 0 , √ 2∆ -1 k 2 .
This corresponds to the complexity of the two-groups instances which are defined as

D ∆ := ν ∈ D K | C µ = 2, ∆ 2 = ∆ where ∆ > 0.
More importantly, it corresponds to the complexity of identifying one of the best arms, i.e. taking ε = 0 yields

P ν (î n / ∈ i (µ)) ≤ K(K + 1) 2 e 2 (2 + log n) 2 p n -5K 2 /2 8K(2∆ -1 min + 3ε -1 0 ) 2 .

Hardness of ε-BAI

Let i > 1 and j ∈ [i]. We have C i+1,j (ε 0 ) = 2 ∆j /ε0+1 ∆i+1-∆j + 3ε -1 0 , C j+1 (ε 0 ) = 2∆ -1 j+1 -ε -1 0 ≤ 2∆ -1 j+1 and √ 2∆ -1 k ≤ 2∆ -1
j+1 for all k ≥ j + 1. Direct manipulations show that, for all i > 1 and all j ∈ [i], we have max{ Hi,j (µ, ε 0 ), Hi,j (µ, ε 0

)} ≤ K max 2∆ -1 j+1 , 2 ∆ j /ε 0 + 1 ∆ i+1 -∆ j + 3ε -1 0 2
. Therefore, we have

H i (µ, ε 0 ) ≤ K min j∈[i] max 2∆ -1 j+1 , 2 ∆ j /ε 0 + 1 ∆ i+1 -∆ j + 3ε -1 0 2 .
Taking j = 1 and then j = 2, we see that, for all i > 1,

H i (µ, ε 0 ) ≤ K max 2∆ -1 min , 3ε -1 0 + 2∆ -1 i+1 2 < H 1 (µ, ε 0 ) , H i (µ, ε 0 ) ≤ K max 2∆ -1 3 , 2 ∆ min /ε 0 + 1 ∆ i+1 -∆ min + 3ε -1 0 2 ≤ K max 2 ∆ min /ε 0 + 1 ∆ 3 -∆ min + 3ε -1 0 2 ,
where the last inequality uses that ∆ 3 ≤ ∆ i+1 for all i > 1.

Similarly, we can derive a lower bound on H i (µ, ε 0 ) by noting that

H i (µ, ε 0 ) ≥ min j∈[i] Hi,j (µ, ε 0 ). For all j ∈ [i], we have that √ 2∆ -1 j+1 ≥ √ 2∆ -1 i+1 , C j+1 (ε 0 ) ≥ 2∆ -1 i+1 -ε -1 0 and C i+1,j (ε 0 ) ≥ 2∆ -1 i+1 + 3ε -1 0 , hence we obtain H i (µ, ε 0 ) ≥ min j∈[i] Hi,j (µ, ε 0 ) ≥ 2K∆ -2 i+1 .
Three-groups instances The three-groups instances are defined as

D ∆,Λ := ν ∈ D K | C µ = 3, ∆ 2 = ∆, ∆ 3 = Λ where ∆ > 0 and Λ > ∆. Above results yield H 2 (µ, ε 0 ) ≤ K 2 ∆/ε 0 + 1 Λ -∆ + 3ε -1 0 2 = O K min{Λ -∆, ε 0 } 2 .

F.1 Proof of Theorem 6

In the following, we consider a sub-Gaussian bandit with distribution ν ∈ R K having mean parameter µ ∈ R K . In particular, our analysis holds when several arms have the largest mean µ .

Let ∆ max = max i∈[K] µ -µ i . Let ε 1 be an analysis parameter (i.e. not the error parameter from the stopping rule (3)). When ε 1 ≥ ∆ max , we have I ε1 (µ) = ∅, hence P ν (î n / ∈ I ε1 (µ)) = 0. In the following, we consider ε 1 ∈ [0, ∆ max ).

For all n > K and δ ∈ (0, 1), let Ẽn,δ = Ẽ1 n,δ ∩ Ẽ2 n,δ with ( Ẽ1 n,δ ) n>K and ( Ẽ2 n,δ ) n>K as in ( 27) and ( 29) for s = 0, i.e.

Ẽ1 n,δ =    ∀k ∈ [K], ∀t ≤ n, |µ t,k -µ k | < 2 f1 (n, δ) N t,k    , Ẽ2 n,δ = ∀(i, k) ∈ [K] 2 s.t. i = k, ∀t ≤ n, |(µ t,i -µ t,k ) -(µ i -µ k )| 1/N t,i + 1/N t,k < 2 f2 (n, δ) ,
where

f1 (n, δ) = 1 2 W -1 (2 log(1/δ) + 2 log(2 + log n) + 2) , f2 (n, δ) = W -1 (log (1/δ) + 2 log (2 + log n) + 2) .
Using Lemma 50, we know that f1 (n, δ) ≤ f2 (n, δ). Using Lemmas 42 and 44, we obtain that

P ν ( Ẽ n,δ ) ≤ K(K+1)
Suppose that we have constructed a time T ε1 (δ) > K such that Ẽn,δ ⊆ {î n ∈ I ε1 (µ)} for n > T ε1 (δ).

Then, using Lemma 48, we obtain

P ν (î n / ∈ I ε1 (µ)) ≤ K(K + 1) 2 inf{δ | n > T ε1 (δ)} .
We will construct an infinite number of times {T ε1 (δ, ε)} ε∈[0,ε1] such that the above property holds, hence taking the infimum yields

P ν (î n / ∈ I ε1 (µ)) ≤ K(K + 1) 2 inf{δ | n > inf ε∈[0,ε1] T ε1 (δ, ε)} .
This proof strategy is the one used to prove Theorem 6.

Let ε ∈ [0, ε 1 ]. Since în = B EB n , our goal is to construct a time T ε1 (δ, ε) such that ∀n > T ε1 (δ, ε), Ẽn,δ ∩ {B EB n / ∈ I ε1 (µ)} = ∅ .
Error due to undersampled arms Let us denote by U ε,ε1,t (n, δ) the set of undersampled arms which are not ε 1 -good, i.e.

U ε,ε1,t (n, δ) := I ε1 (µ) ∩ i | N t,i ≤ 4C ε,i f2 (n, δ) with C ε,i := 2 min k∈Iε(µ) (∆ i -∆ 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 ε 1 > 0 and ε ∈ [0, ε 1 ]. Let H µ,ε0 (ε) as in Lemma 5 and define Hε,ε1 (µ, ε 0 ) := H µ,ε0 (ε) + 2|I ε (µ)| min (i,j)∈Iε(µ)×Iε 1 (µ) (∆ j -∆ i ) 2 . ( 19
)
Let us define

S ε,ε1,ε0,µ (δ) = sup n | n ≤ 4 Hε,ε1 (µ, ε 0 ) min{β, 1 -β} f2 (n, δ) + (3/2 + 1/β)K 2 .
For all n > S ε,ε1,ε0,µ (δ), under the event Ẽn,δ , we have

B EB n / ∈ I ε1 (µ) implies that B EB n ∈ U ε,ε1,n (n, δ). Proof. Let |I ε (µ)| = I ε and g ε,ε0 (n, δ) = 4Hµ,ε 0 (ε)
min{β,1-β} f2 (n, δ) + 3K(K -1)/2. Using Lemma 5 and the pigeonhole principle, there exists i 0 ∈ I ε (µ) such that j T n (i 0 , j) ≥ (n -1 -g ε,ε0 (n, δ)) /I ε .

Therefore, we have

N n,i0 ≥ β j T n (i 0 , j) -(K -1) ≥ β (n -1 -g ε,ε0 (n, δ)) /I ε -(K -1) .
Let S ε,ε1,ε0,µ (δ) defined as in the statement of Lemma 35. Direct manipulations shows that

S ε,ε1,ε0,µ (δ) ≥ sup n | n -1 ≤ g ε,ε0 (n, δ) + I ε β 4 f2 (n, δ) max i / ∈Iε 1 (µ) C ε,i + K -1 .
Therefore, we have N n,i0 > 4 f2 (n, δ) max i / ∈Iε 1 (µ) C ε,i for all n > S ε,ε1,ε0,µ (δ).

Let n > S ε,ε1,ε0,µ (δ). Suppose that B EB n = i / ∈ I ε1 (µ). Using Lemma 31, under the event Ẽn,δ , we obtain that

min{N n,i , N n,i0 } ≤ 8 f1 (n, δ) (µ i0 -µ i ) 2 ≤ 4C ε,i f2 (n, δ) .
Suppose towards contradiction that min{N n,i , N n,i0 } = N n,i0 , then we have N n,i0 ≤ 4C ε,i f2 (n, δ). This is a direct contradiction with N n,i0 > 4 f2 (n, δ) max i / ∈Iε 1 (µ) C ε,i since n > S ε,ε1,ε0,µ (δ). Therefore, we have shown that min{N n,i , N n,i0 } = N n,i , hence i ∈ U ε,ε1,n (n, δ). This concludes the proof.

No remaining undersampled arms Lemma 36 shows that, if there are still undersampled arms which are not ε 1 -good, then either the leader or the challenger was not often selected as leader or challenger.

Lemma 36. Let ε 1 ≥ 0 and ε ∈ [0, ε 1 ]. Let ∆ µ (ε) = min k / ∈Iε(µ) ∆ k , C µ,ε0 (ε, ε 1 ) = 2 max j / ∈Iε 1 (µ) ∆j /ε0+1 min k∈Iε(µ) (∆j -∆ k ) + ε -1 0 and C µ,ε0 (ε) = 2/∆ µ (ε) - ε -1 0 . Let A ε,ε1,ε0,i = max{2/∆ µ (ε) 2 , C µ,ε0 (ε, ε 1 ) 2 } for all i ∈ i (µ), A ε,ε1,ε0,i = max{C µ,ε0 (ε) 2 , C µ,ε0 (ε, ε 1 ) 2 } for all i ∈ (I ε (µ) \ i (µ)) ∪ ([K] \ I ε1 (µ)), and otherwise A ε,ε1,ε0,i = max{C µ,ε0 (ε) 2 , C µ,ε0 (ε, ε 1 ) 2 , 2/∆ 2 i } for all i ∈ I ε1 (µ) \ I ε (µ). For all n > K, under event Ẽn,δ , for all t ∈ [n] \ [K] such that U ε,ε1,t (n, δ) = ∅, there exists i t ∈ [K] such that T t (i t ) ≤ 4 f2 (n, δ) min{β, 1 -β} A ε,ε1,ε0,it + 3(K -1)/2 and T t+1 (i t ) = T t (i t ) + 1 .
Proof. We will be interested in three distinct cases since

{U ε,ε1,t (n, δ) = ∅} = U ε,ε1,t (n, δ) ∩ {B EB t , C TC t } = ∅ ∪ U ε,ε1,t (n, δ) = ∅, U ε,ε1,t (n, δ) ∩ {B EB t , C TC t } = ∅, B EB t / ∈ I ε (µ) ∪ U ε,ε1,t (n, δ) = ∅, U ε,ε1,t (n, δ) ∩ {B EB t , C TC t } = ∅, B EB t ∈ I ε (µ) , Case 1. Let t ∈ [n] \ [K] such that {B EB t , C TC t } ∩ U ε,ε1,t (n, δ) = ∅. Let k t ∈ {B EB t , C TC t } ∩ U ε,ε1,t (n, δ). For this k t / ∈ I ε1 (µ), we have T t+1 (k t ) = T t (k t ) + 1
and, by combining Lemma 31 and N t,kt ≤ 4C ε,kt f2 (n, δ), we obtain that

T t (k t ) ≤ N t,kt min{β, 1 -β} + 3(K -1) 2 ≤ 4 f2 (n, δ) min{β, 1 -β} C ε,kt + 3(K -1)/2 . Case 2. Let t ∈ [n] \ [K] such that U ε,ε1,t (n, δ) = ∅, U ε,ε1,t (n, δ) ∩ {B EB t , C TC t } = ∅ and B EB t / ∈ I ε (µ). Let ∆ µ (ε) and C µ,ε0 (ε) defined as in the statement of Lemma 36. Let D ε0,ε,i = 2/∆ µ (ε) 2 for all i ∈ i (µ), D ε0,ε,i = C µ,ε0 (ε) for all i ∈ I ε (µ) \ i (µ), otherwise D ε0,ε,i = max{C µ,ε0 (ε), 2/∆ 2 i }. Using Lemma 32, there exists k t ∈ [K] such that T t (k t ) ≤ 4 f2 (n, δ) min{β, 1 -β} D ε,ε0,kt + 3(K -1)/2 and T t+1 (k t ) = T t (k t ) + 1 . Case 3. Let t ∈ [n] \ [K] such that U ε,ε1,t (n, δ) = ∅, U ε,ε1,t (n, δ) ∩ {B EB t , C TC t } = ∅ and B EB t ∈ I ε (µ). Let j 0 ∈ U ε,ε1,t (n, δ) \ {B EB t , C TC t }, which is possible since U ε,ε1,t (n, δ) ∩ {B EB t , C TC t } = ∅ and U ε,ε1,t (n, δ) = ∅.
Let us denote by (B EB t , C TC t ) = (i, j) with i ∈ I ε (µ) and j = j 0 . Using the TC challenger, under the event E n,δ , we obtain

µ i -µ j0 + ε 0 1/N t,i + 1/N t,j0 + 2 f2 (n, δ) ≥ µ t,i -µ t,j0 + ε 0 1/N t,i + 1/N t,j0 ≥ µ t,i -µ t,j + ε 0 1/N t,i + 1/N t,j ≥ ε 0 min{N t,i , N t,j }/2 . Since µ i -µ j0 + ε 0 ≥ ε 0 > 0, we have µ i -µ j0 + ε 0 1/N t,i + 1/N t,j0 ≤ N t,j0 (µ i -µ j0 + ε 0 ) + 2 f2 (n, δ) ≤ 2 µ i -µ j0 + ε 0 min k∈Iε(µ) (µ k -µ j0 ) + 1 2 f2 (n, δ) .
Using Lemma 31 to lower bound min{N t,i , N t,j } and µ i -µ j0 ≤ ∆ j0 for all i ∈ I ε (µ), direct manipulation yields that

min{T t (i), T t (j)} ≤ 4 f2 (n, δ) min{β, 1 -β} C µ,ε0 (ε, ε 1 ) 2 + 3(K -1)/2 .
where C µ,ε0 (ε, ε 1 ) is defined as in the statement of Lemma 36. It is direct to see that C µ,ε0 (ε, ε 1 ) 2 ≥ max{1/ε 2 0 , max i / ∈Iε 1 (µ) C ε,i } and C ε,i ≥ 2/∆ 2 i for all i / ∈ I ε1 (µ). The above shows that there exists k

t ∈ [K] such that T t (k t ) ≤ 4 f2 (n, δ) min{β, 1 -β} C µ,ε0 (ε, ε 1 ) 2 + 3(K -1)/2 and T t+1 (k t ) = T t (k t ) + 1 .
Summary. Let us define (A ε,ε1,ε0,i ) i∈[K] as in the statement of Lemma 36. Under Ẽn,δ , we have show that, when U ε,ε1,t (n, δ) = ∅, there exists i t ∈ [K] such that

T t (i t ) ≤ 4 f2 (n, δ) min{β, 1 -β} A ε,ε1,ε0,it + 3(K -1)/2 and 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 ε 1good.

Lemma 37. Let ε 1 ≥ 0 and ε ∈ [0, ε 1 ]. Let ∆ µ (ε), C µ,ε0 (ε, ε 1 ) and C µ,ε0 (
) := |i (µ)| max{ √ 2∆ µ (ε) -1 , C µ,ε0 (ε, ε 1 )} 2 + |(I ε (µ) \ i (µ)) ∪ ([K] \ I ε1 (µ))| max{C µ,ε0 (ε), C µ,ε0 (ε, ε 1 )} 2 + i∈Iε 1 (µ)\Iε(µ) max{C µ,ε0 (ε), C µ,ε0 (ε, ε 1 ), √ 2∆ -1 i } 2 . ( 20
)
Let us define

T ε,ε1,ε0,µ (δ) = sup n | n ≤ 4 Hε,ε1 (µ, ε 0 ) min{β, 1 -β} f2 (n, δ) + 3K 2 /2 .
For all n > T ε,ε1,ε0,µ (δ), under the event Ẽn,δ , we have U ε,ε1,n (n, δ) = ∅.

Proof. For all n > K, under event Ẽn,δ , combining Lemma 4 and 36 for A t (n, δ) = {U ε,ε1,t (n, δ) = ∅} and D i (n, δ) = 4 f2(n,δ) min{β,1-β} A ε,ε1,ε0,i + 3(K -1)/2 yields that

n t=K+1 1 (U ε,ε1,t (n, δ) = ∅) ≤ 4 f2 (n, δ) min{β, 1 -β} Hε,ε1 (µ, ε 0 ) + 3K(K -1)/2 .
where we used that i∈[K] A ε,ε1,ε0,i = Hε,ε1 (µ, ε 0 ) where Hε,ε1 (µ, ε 0 ) is defined in [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF].

For all i / ∈ I ε1 (µ), let us define

t i (n, δ) = max {t ∈ [n] \ [K] | i ∈ U ε,ε1,t (n, δ)} .

By definition, for all i /

∈ I ε1 (µ), we have i ∈ U ε,ε1,t (n, δ) for all t ∈ (K, t i (n, δ)] and i / ∈ U ε,ε1,t (n, δ) for all t ∈ (t i (n, δ), n]. Therefore, for all t ∈ (K, max i / ∈Iε 1 (µ) t i (n, δ)], we have

U ε,ε1,t (n, δ) = ∅ and U ε,ε1,t (n, δ) = ∅ for all t > max i / ∈Iε 1 (µ) t i (n, δ), hence max i / ∈Iε 1 (µ) (t i (n, δ) -K) = n t=K+1 1 (U ε,ε1,t (n, δ) = ∅) ≤ 4 f2 (n, δ) min{β, 1 -β} Hε,ε1 (µ, ε 0 ) + 3K(K -1)/2 .
Let T ε,ε1,ε0,µ (δ) defined as in the statement of Lemma 37. Direct manipulations show that

T ε,ε1,ε0,µ (δ) ≥ sup n | n -K ≤ 4 f2 (n, δ) min{β, 1 -β} Hε,ε1 (µ, ε 0 ) + 3K(K -1)/2 .
Let n > T ε,ε1,ε0,µ (δ). Then, we have

n -K > 4 f2 (n, δ) min{β, 1 -β} Hε,ε1 (µ, ε 0 ) + 3K(K -1)/2 ≥ max i / ∈Iε 1 (µ) (t i (n, δ) -K) ,
hence n > max i / ∈Iε 1 (µ) t i (n, δ). This conclude the proof that U ε,ε1,n (n, δ) = ∅.

Upper bound probability of error Let S ε,ε1,ε0,µ (δ) and T ε,ε1,ε0,µ (δ) as in Lemmas 35 and 37.

For β = 1/2, direct manipulations show that max{S ε,ε1,ε0,µ (δ), T ε,ε1,ε0,µ (δ)} ≤ E ε,ε1,ε0,µ (δ) with

E ε,ε1,ε0,µ (δ) := sup n | n ≤ 8 max{ Hε,ε1 (µ, ε 0 ), Hε,ε1 (µ, ε 0 )} f2 (n, δ) + 5K 2 /2
Combining Lemmas 35 and 37, for all n > E ε,ε1,ε0,µ (δ), we proved that

Ẽn,δ ∩ {î n / ∈ I ε1 (µ)} = Ẽn,δ ∩ {B EB n / ∈ I ε1 (µ)} ⊆ Ẽn,δ ∩ {U ε,ε1,n (n, δ) = ∅} = ∅ , hence {î n / ∈ I ε1 (µ)} ⊆ Ẽ n,δ .
Using Lemma 48, P ν ( Ẽ n,δ ) ≤ K(K + 1)δ/2 and taking the infimum over ε ∈ [0, ε 1 ], yields

P ν (î n / ∈ I ε1 (µ)) ≤ K(K + 1) 2 inf{δ | n > E ε1,ε0,µ (δ)} .
where we used Lemma 52 and inf ε∈[0,ε1] E ε,ε1,ε0,µ (δ) = E ε1,ε0,µ (δ) with

E ε1,ε0,µ (δ) := sup n | n ≤ 8 inf ε∈[0,ε1] max{ Hε,ε1 (µ, ε 0 ), Hε,ε1 (µ, ε 0 )} f2 (n, δ) + 5K 2 /2 .
Using Lemma 52, we obtain that

P ν (î n / ∈ I ε1 (µ)) ≤ 1 ε 1 < ∆ Cµ K(K + 1) 2 e 2 (2 + log n) 2 p n -5K 2 /2 8 inf ε∈[0,ε1] max{ Hε,ε1 (µ, ε 0 ), Hε,ε1 (µ, ε 0 )} ,
where p(x) = x exp(-x).

More explicit complexity In order to obtain a more interpretable result, we notice that the dependence in (ε, ε 1 ) of Hε,ε1 (µ, ε 0 ) and Hε,ε1 (µ, ε 0 ) is only with respect to its position in the ordered means. In the following, we will replace the dependency in (ε, ε 1 ) by a dependency in such indices.

Let µ ∈ R K . Let us denote by

C µ := |{µ i | i ∈ [K]}| the number of different arm means in µ. For all i ∈ [C µ ],
we denote the set of arms having mean gap

∆ i by C µ (i) := {k ∈ [K] | µ -µ k = ∆ i }
where the gaps are sorted by increasing order

0 = ∆ 1 < ∆ 2 < • • • < ∆ Cµ .
In particular, we have C µ (1) = i (µ) and ∆ Cµ = ∆ max . Let us denote by

∀ε > 0, i µ (ε) := i if ε ∈ [∆ i , ∆ i+1 ) with i ∈ [1, C µ -1] C µ if ε ≥ ∆ Cµ . ( 21
) It is direct to see that i µ (ε) = max{i ∈ [C µ ], C µ (i) ⊂ I ε (µ)} for all ε > 0. For all i ∈ [C µ -1], let us define H i (µ, ε 0 ) = min j∈[i]
max{ Hi,j (µ, ε 0 ), Hi,j (µ, ε 0 )} with Hi,j (µ, ε 0 ) and Hi,j (µ, ε 0 ) as in Theorem 6. Let ε 1 ≥ 0 and ε ∈ [0, ε 1 ]. Then, we have by direct manipulations that

inf ε∈[0,ε1]
max{ Hε,ε1 (µ, ε 0 ), Hε,ε1 (µ, ε 0 )} = H iµ(ε1) (µ, ε 0 ) , since Hε,ε1 (µ, ε 0 ) = Hiµ(ε1),iµ(ε) (µ, ε 0 ) and Hε,ε1 (µ, ε 0 ) = Hiµ(ε1),iµ(ε) (µ, ε 0 ). This concludes the first part of Theorem 6, i.e.

P ν (î n / ∈ I ε1 (µ)) ≤ 1 (ε 1 < ∆ max ) K(K + 1) 2 e 2 (2 + log n) 2 p n -5K 2 /2 8H iµ(ε1) (µ, ε 0 )
.

Simple regret Since µ -µ în is a positive random variable, we obtain that

E ν [µ -µ în ] = +∞ ε1=0 P ν (µ -µ în > ε 1 )d ε 1 = +∞ ε1=0 P ν (î n / ∈ I ε1 (µ))d ε 1 .
As a function of ε, our upper bound on P ν (î n / ∈ I ε1 (µ)) is piecewise constant on [∆ i , ∆ i+1 ) for all i ∈ [C µ -1] and has null value for ε 1 ≥ ∆ max . Our upper is informative, i.e. smaller than 1, for all n ≥ D µ where

D µ = 8H 1 (µ, ε 0 )h 2 8H 1 (µ, ε 0 ), 5K 2 /2, 2 + log (K(K + 1)/2) + 5K 2 /2 > sup x | x < 8H 1 (µ, ε 0 )W -1 (2 log (2 + log x) + 2 + log (K(K + 1)/2)) + 5K 2 /2 ,
where the inequality is obtained by using Lemma 51, and h 2 is defined therein. Therefore, we obtain that, for all n ≥ D µ ,

E ν [µ -µ în ] ≤ K(K + 1) 2 e 2 (2 + log n) 2 i∈[Cµ-1] (∆ i+1 -∆ i )p n -5K 2 /2 8H i (µ, ε 0 ) ,
which concludes the second part of Theorem 6.

F.2 Unverifiable sample complexity

The (ε, δ)-unverifiable sample complexity is defined as the expectation of the smallest stopping time τ satisfying P(∀t ≥ τ , în ∈ I ε (µ)) ≥ 1 -δ. Theorem 7 gives an upper bound on the unverifiable expected sample complexity of the EB-TC ε0 algorithm with fixed proportions β = 1/2.

Theorem 7. Let ε 0 > 0 and δ ∈ (0, 1). The EB-TC ε0 algorithm with fixed proportions β = 1/2 satisfies that, for all ν ∈ D K with mean µ, for all ε ≥ 0,

P ν ∀n > U iµ(ε),δ (µ, ε 0 ), în ∈ I ε (µ) ≥ 1 -δ .
The times U iµ(ε),δ (µ, ε 0 ) are the (ε, δ)-unverifiable sample complexity of EB-TC ε0 defined as

∀i ∈ [C µ -1], U i,δ (µ, ε 0 ) = h 2 log(1/δ), 8H i (µ, ε 0 ), 8H i (µ, ε 0 ) log (K(K + 1)/2) + 5K 2 /2 , ( 22
) with (H i (µ, ε 0 )) i∈[Cµ-1] defined in Theorem 6.
The function

h 2 (log(1/δ), A, B) = 2AW -1 ( 1 2 log(1/δ) + B 2A + log(2A)) satisfies that h 2 (log(1/δ), A, B) = δ→0 A log(1/δ) + O(log log(1/δ)).
Proof. In Appendix F.1, we consider the concentration event Ẽn,δ that involved tighter concentration results with thresholds f1 (n, δ) and f2 (n, δ). Let n > K and δ ∈ (0, 1). It is direct to see that the same argument holds for the concentration events E n,δ = E 1 n,δ ∩ E 2 n,δ with (E 1 n,δ ) n>K and (E 2 n,δ ) n>K as in ( 24) and ( 25) for s = 0, i.e.

E 1 n,δ = ∀k ∈ [K], ∀t ≤ n, |µ t,k -µ k | < 2f 1 (n, δ) N t,k , E 2 n,δ = ∀(i, k) ∈ [K] 2 s.t. i = k, ∀t ≤ n, |(µ t,i -µ t,k ) -(µ i -µ k )| 1/N t,i + 1/N t,k < 2f 2 (n, δ) ,
where f 1 (n, δ) = log(1/δ) + log n + log (K(K + 1)/2) and f 2 (n, δ) = log(1/δ) + 2 log n + log (K(K + 1)/2), which satisfy f 1 (n, δ) ≤ f 2 (n, δ). Using Lemmas 40 and 41, we obtain that

P ν (E n,δ ) ≤ δ.
In the following, we use the notation on the gaps introduced in Appendix F.1, the complexities

(H i (µ, ε 0 )) i∈[Cµ-1]
defined in Theorem 6 and the function i µ (ε) defined in [START_REF] Jourdan | Top two algorithms revisited[END_REF]. To prove Theorem 6, we obtain as an intermediary step that: for all n > E ε1,ε0,µ (δ), {î n / ∈ I ε1 (µ)} ⊆ E n,δ , where

E ε1,ε0,µ (δ) := sup n | n ≤ 8 inf ε∈[0,ε1] max{ Hε,ε1 (µ, ε 0 ), Hε,ε1 (µ, ε 0 )}f 2 (n, δ) + 5K 2 /2 = sup n | n ≤ 8H iµ(ε1) f 2 (n, δ) + 5K 2 /2 ,
where the equality holds by using the rewriting of the complexities done in the end of Appendix F.1.

Let A = 8H iµ(ε1) and B = 8H iµ(ε1) log (K(K + 1)/2) + 5K 2 /2. Using a proof similar to Lemma 51, applying Lemma 49 yields that

n > E ε1,ε0,µ (δ) ⇐⇒ n > 2A log n + A log(1/δ) + B ⇐⇒ n 2A -log n 2A > 1 2 log(1/δ) + B 2A + log(2A) ⇐⇒ n > 2AW -1 1 2 log(1/δ) + B 2A + log(2A) , Let us define h 2 (log(1/δ), A, B) = 2AW -1 1 2 log(1/δ) + B 2A + log(2A) and, for all i ∈ [C µ -1], we define U i,δ (µ, ε 0 ) = h 2 log(1/δ), 8H i (µ, ε 0 ), 8H i (µ, ε 0 ) log (K(K + 1)/2) + 5K 2 /2
. Therefore, we have shown that, for all ε 1 ≥ 0,

{∃n > U iµ(ε1),δ (µ, ε 0 ), în / ∈ I ε1 (µ)} ⊆ E n,δ
Using that P ν (E n,δ ) ≤ δ, we can conclude that, for all ε 1 ≥ 0,

P ν ∀n > U iµ(ε1),δ (µ, ε 0 ), în ∈ I ε1 (µ) ≥ 1 -δ .

F.3 Cumulative regret of induced policy

Given a stream of recommendations (î n ) n>K , an external agent aiming at minimizing its cumulative regret can simply pull the arm î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 ε 0 > 0. Let (î n ) n>K be the recommendations of the EB-TC ε0 algorithm with fixed proportions β = 1/2. An agent pulling în at time n has constant induced regret, i.e.

∀ν ∈ D K , ∀T > K, T n=K+1 E ν [µ -µ în ] = O K 3 ∆ max min{∆ min , ε 0 } 2 log K min{∆ min , ε 0 } 2 2 . Proof. Using that H 1 (µ, ε 0 ) = max i∈[Cµ-1] H i (µ, ε 0 ), a direct upper bound based on Corollary 1 yields that, for all n ≥ D µ , E ν [µ -µ în ] ≤ K(K + 1) 2 e 2 (2 + log n) 2 ∆ max n -5K 2 /2 8H 1 (µ, ε 0 ) exp - n -5K 2 /2 8H 1 (µ, ε 0 ) . Let c > 0. Let f (c, x) = (c + log(x)) 2 x exp(-x) for all x ≥ 1. Let A > 0, B > 0. By integration, for all C ≥ A + B, we obtain T n=C f (c, (n -B)/A) ≤ A +∞ 1 f (c, x)d x = A c 2 + 2cC 1 + C 2 .
where

C α = +∞ 1 log(x) α exp(-x)d x < +∞ for all α ≥ 0. For n ≥ 5K 2 , we have n ≤ 2(n - 5K 2 /2). Recall that D µ = 8H 1 (µ, ε 0 )h 2 8H 1 (µ, ε 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 µ , we have trivially that E ν [µ -µ în ] ≤ ∆ max . Therefore, we obtain T n=K+1 E ν [µ -µ în ] ≤ (5K 2 /2 + D µ )∆ max + K(K + 1) 2 e 2 ∆ max T n=5K 2 +8H1(µ,ε0) f 2 + log (16H 1 (µ, ε 0 )) , n -5K 2 /2 8H 1 (µ, ε 0 ) ≤ (5K 2 /2 + D µ )∆ max + K(K + 1) 2 e 2 ∆ max 8H 1 (µ, ε 0 ) (2 + log (16H 1 (µ, ε 0 ))) 2 + 2C 1 (2 + log (16H 1 (µ, ε 0 ))) + C 2 .
Studying the function h 2 (x, y, z), it is direct to see that h 2 (x, y, z) = x→+∞ o(log(x) α ) for all α > 0, hence ∆ max D µ is dominated by the other term. Therefore, by studying the dominating term when min{∆ min , ε 0 } → 0, our upper bound scales as

O K 2 ∆ max H 1 (µ, ε 0 )(log H 1 (µ, ε 0 )) 2 = O K 3 ∆ max min{∆ min , ε 0 } 2 log K min{∆ min , ε 0 } 2 2 ,
where we used that

H 1 (µ, ε 0 ) = K(2∆ -1 min + 3ε -1 0 ) 2 = O K min{∆min,ε0} 2 .
The idea of decoupling exploration and exploitation when minimizing the regret in the multi-armed bandits literature was introduced by [START_REF] Avner | Decoupling exploration and exploitation in multi-armed bandits[END_REF]. 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 [START_REF] Rouyer | Tsallis-inf for decoupled exploration and exploitation in multi-armed bandits[END_REF] achieves a constant regret O(K/∆ min ). Therefore, in this setting, our constant regret in Corollary 2 does have the best achievable scaling in K and ∆ min .

Beyond synchronized policy When the external agent plays în at time n, it is said to be synchronized with the recommendation rule. In all generality, one could pull arm îL(n) at time n, where L : N → 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 L can be rapidly increasing, e.g. 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 L can be piecewise constant with small steps, e.g. L(n) = n/B + K. The communication between the agent and the recommendation rule can happen infrequently (e.g. paying to access the recommendation) hence L can be piecewise constant with large steps, e.g.

L(n) = ( n/B ) α + K where α > 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 (ε 1 , δ)-PAC is done by leveraging concentration results. In particular, we build upon Theorem 9 of [START_REF] Kaufmann | Mixture martingales revisited with applications to sequential tests and confidence intervals[END_REF] 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 σ 2 = 1 (as the authors mentioned).

Lemma 38 (Theorem 9 of [START_REF] Kaufmann | Mixture martingales revisited with applications to sequential tests and confidence intervals[END_REF]). Consider a sub-Gaussian bandit ν with means µ ∈ R K . Let S ⊆ [K] and x > 0.

P ν ∃n ∈ N, k∈S N n,k 2 (µ n,k -µ k ) 2 > k∈S 2 log (4 + log (N n,k )) + |S|C G x |S| ≤ e -x
where C G is defined in [START_REF] Kaufmann | Mixture martingales revisited with applications to sequential tests and confidence intervals[END_REF] by

C G (x) = min λ∈]1/2,1] g G (λ)+x λ and g G (λ) = 2λ -2λ log(4λ) + log ζ(2λ) - 1 2 log(1 -λ) , ( 23
)
where ζ is the Riemann ζ function and C G (x) ≈ x + log(x).

Since în = i (µ n ), standard manipulations yield that for all i = în

(µ n,în -µ n,i + ε 1 ) 2 1/N n,în + 1/N n,i = inf u∈R N n,în (µ n,în -u) 2 + N n,i (µ n,i -u -ε 1 ) 2 = inf y≥x+ε1 N n,în (µ n,în -x) 2 + N n,i (µ n,i -y) 2 .
Let i = i (µ). Using the stopping rule (3) and the above manipulations, we obtain

P ν τ ε1,δ < +∞, îτ ε 1 ,δ / ∈ I ε1 (µ) ≤ P ν (∃n ∈ N, ∃i / ∈ I ε1 (µ), i = i (µ n ), min k =i inf y≥x+ε1 N n,în (µ n,în -x) 2 + N n,i (µ n,i -y) 2 ≥ 2c(n -1, δ) ≤ P ν (∃n ∈ N, ∃i / ∈ I ε1 (µ), i = i (µ n ), N n,i 2 (µ n,i -µ i ) 2 + N n,i 2 (µ n,i -µ i ) 2 ≥ c(n -1, δ) ≤ i / ∈Iε 1 (µ) P ν ∃n ∈ N, N n,i 2 (µ n,i -µ i ) 2 + N n,i 2 (µ n,i -µ i ) 2 ≥ c(n -1, δ) ,
where the second inequality is obtained with (k, x, y) = (i , µ i , µ i ) since i / ∈ I ε1 (µ), and the third by union bound. By concavity of x → log(4 + log(x)) and

N n,i + N n,i ≤ k∈[K] N n,k = n -1, we obtain ∀i / ∈ I ε1 (µ), log(4 + log N n,i ) + log(4 + log N n,i ) ≤ 2 log(4 + log((n -1)/2))
Combining the above with Lemma 38 for all i / ∈ I ε1 (µ) and using that |I ε1 (µ)| ≤ K -1, we obtain

P ν (τ δ < +∞, îτ δ / ∈ I ε1 (µ)) ≤ i / ∈Iε 1 (µ) δ K -1 ≤ δ .

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 σ 2 . Then, for all δ ∈ (0, 1],

P X |X| ≥ σ 2 log(1/δ) ≤ δ .
Lemma 40 gives a sequence of concentration events under which the empirical means are close to their true values.

Lemma 40. Let δ ∈ (0, 1] and s ≥ 0. For all n > K, let f 1 (x, δ) = log(1/δ) + (1 + s) log x and

E 1 n,δ := ∀k ∈ [K], ∀t ≤ n, |µ t,k -µ k | < 2f 1 (n, δ) N t,k . (24)
Then, for all n > K, P ν ((E 1 n,δ ) ) ≤ Kδ n s .

Proof. Let (X s ) s∈[n] be i.i.d. observations from one sub-Gaussian distribution with mean 0 and variance proxy σ 2 = 1. Then, 1 m m i=1 X i is sub-Gaussian with mean 0 and variance proxy σ 2 = 1/m. By union bound over [K] and over m ∈ [n], we obtain

P ν ∃k ∈ [K], ∃t ≤ n, |µ t,k -µ k | ≥ 2f 1 (n, δ) N t,k ≤ k∈[K] m∈[n] P   1 m s∈[m] X s ≥ 2f 1 (n, δ) m   ≤ δ k∈[K] m∈[n] n -(1+s) = Kδn -s ,
where we used that µ t,k -

µ k = 1 N t,k t s=1 1 (I s = k) X s,k
and concentration results for sub-Gaussian observations (Lemma 39). Lemma 41 gives a sequence of concentration events under which the empirical gaps are close to their true values. Lemma 41. Let δ ∈ (0, 1] and s ≥ 0. For all n > K, let f 2 (x, δ) = log(1/δ) + (2 + s) log(x) and

E 2 n,δ := ∀(i, k) ∈ [K] 2 s.t. i = k, ∀t ≤ n, |(µ t,i -µ t,k ) -(µ i -µ k )| 1/N t,i + 1/N t,k < 2f 2 (n, δ) . (25)
Then, for all n > K,

P ν ((E 2 n,δ ) ) ≤ K(K-1)δ 2n s . Proof. Let (X s ) s∈[n] and (Y s ) s∈[n]
be two streams of i.i.d. observations from two sub-Gaussian distributions with mean 0 and variance proxy σ 2 = 1. Then,

1 m1 m1 i=1 X i -1 m2 m2
i=1 Y i is sub-Gaussian with mean 0 and variance proxy σ 2 = 1 m1 + 1 m2 . By union bound , we obtain

P ν ∃(i, k) ∈ [K] 2 s.t. i = k, ∃t ≤ (µ t,i -µ t,k ) -(µ i -µ k ) 1/N t,i + 1/N t,k ≤ 2f 2 (n, δ) ≤ (i,k)∈[K] 2 ,i =k (m1,m2)∈[n] 2 P 1 m 1 m1 i=1 X i - 1 m 2 m2 i=1 Y i ≤ -2f 2 (n, δ) (1/m 1 + 1/m 2 ) ≤ δ (i,k)∈[K] 2 ,i =k (m1,m2)∈[n] 2 n -(2+s) = K(K -1) 2 δn -s ,
where we used that

(µ t,i -µ i ) -(µ t,k -µ k ) = 1 N t,i t s=1 1 (I s = i ) X s,i - 1 N t,k t s=1 1 (I s = k) X s,k
and concentration results for sub-Gaussian observations (Lemma 39).

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

Lemma 42. Let δ ∈ (0, 1] and s ≥ 0. Let W -1 defined in Lemma 49. For all n > K, let

f1 (n, δ) = 1 2 W -1 (2 log(1/δ) + 2s log n + 2 log(2 + log n) + 2) , (26)
and

Ẽ1 n,δ =    ∀k ∈ [K], ∀t ≤ n, |µ t,k -µ k | < 2 f1 (n, δ) N t,k    . (27)
Then, for all n > K, P ν (( Ẽ1 n,δ ) ) ≤ Kδ n s .

Proof. Let (X s ) s∈[n] be i.i.d. observations from one sub-Gaussian distribution with mean 0 and variance proxy σ 2 = 1. Let S t = s∈[t] X s . To derived concentration result, we use peeling.

Let η > 0, γ > 0 and

D = log(n) log(1+η) . For all i ∈ [D], let N i = (1 + η) i-1 . For all i ∈ [D], we define the family of priors f Ni,γ (x) = γNi 2π exp -x 2 γNi
2 with weights w i = 1 D and process

M (t) = i∈[D] w i f Ni,γ (x) exp xS t - 1 2 x 2 t dx , which satisfies M (0) = 1. It is direct to see that M (t) = exp xS t -1 2
x 2 t is a non-negative supermartingale since sub-Gaussian distributions with mean 0 and variance proxy

σ 2 = 1 satisfy ∀λ ∈ R, E X [exp(sX)] ≤ exp(λ 2 /2) .
By Tonelli's theorem, then M (t) is also a non-negative supermartingale of unit initial value.

Let i ∈ [D] and consider t ∈ [N i , N i+1 ). For all x, f Ni,γ (x) ≥ N i t f t,γ (x) ≥ 1 √ 1 + η f t,γ (x)
Direct computations shows that

f t,γ (x) exp xS t - 1 2 x 2 t dx = 1 1 + γ -1 exp S 2 t 2(1 + γ)t .
Minoring M (t) by one of the positive term of its sum, we obtain

M (t) ≥ 1 D 1 (1 + γ -1 )(1 + η) exp S 2 t 2(1 + γ)t ,
Using Ville's maximal inequality for non-negative supermartingale, we have that with probability greater than 1 -δ, log M (t) ≤ log (1/δ). Therefore, with probability greater than 1 -δ, for all i ∈ [D] and t ∈ [N i , N i+1 ),

S 2 t t ≤ (1 + γ) 2 log (1/δ) + 2 log D + log(1 + γ -1 ) + log(1 + η) .
Since this upper bound is independent of t, we can optimize it and choose γ as in Lemma 43.

Lemma 43

(Lemma A.3 in [9]). For a, b ≥ 1, the minimal value of f (η) = (1 + η)(a + log(b + 1 η )) is attained at η such that f (η ) ≤ 1 -b + W -1 (a + b). If b = 1, then there is equality. Therefore, with probability greater than 1 -δ, for all i ∈ [D] and t ∈ [N i , N i+1 ), S 2 t t ≤ W -1 (1 + 2 log (1/δ) + 2 log D + log(1 + η)) ≤ W -1 (1 + 2 log (1/δ) + 2 log (log(1 + η) + log n) -2 log log(1 + η) + log(1 + η)) = W -1 (2 log (1/δ) + 2 log (2 + log n) + 3 -2 log 2)
The second inequality is obtained since D ≤ 1 + log n log(1+η) . The last equality is obtained for the choice η = e 2 -1, which minimizes η → log(1 + η) -2 log(log

(1 + η)). Since [n] ⊆ i∈[D] [N i , N i+1 ) and N t,k (µ t,k -µ k ) = s∈[N t,k ] X s,k (unit-variance), this yields P ∃m ≤ n, 1 m m s=1 X s ≥ 1 m W -1 (2 log(1/δ) + 2 log(2 + log(n)) + 3 -2 log 2) ≤ δ .
Since 3 -2 log 2 ≤ 2 and W -1 is increasing, taking δn -s yields

P ν ∃t ≤ n, N t,k |µ t,k -µ k | ≥ 2 f1 (n, δ) ≤ δn -s .
Doing a union bound over arms yields the result.

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

Lemma 44. Let δ ∈ (0, 1] and s ≥ 0. Let W -1 defined in Lemma 49. For all n > K, let

f2 (n, δ) = W -1 (log (1/δ) + s log n + 2 log (2 + log n) + 2) , (28)
and

Ẽ2 n,δ := ∀(i, k) ∈ [K] 2 s.t. i = k, ∀t ≤ n, |(µ t,i -µ t,k ) -(µ i -µ k )| 1/N t,i + 1/N t,k < 2 f2 (n, δ) . (29)
Then, for all n > K,

P ν (( Ẽ2 n,δ ) ) ≤ K(K-1) 2 δ n s .
Proof. Without loss of generality, we show the result for arms (i, k) = (1, 2). Let (X s ) s∈[n] and (Y s ) s∈[n] be i.i.d. observations from two sub-Gaussian distribution with mean 0 and variance proxy

σ 2 = 1. Let S t,k = s∈[t] 1 (I s = k) X s for all k ∈ {1, 2}.
To derived concentration result, we use peeling as in Lemma 42.

Let η > 0, γ > 0 and D = log(n) log(1+η) . For all i ∈ [D], let N i = (1 + η) i-1 . For all i ∈ [D], we define the family of priors f Ni,γ (x) = γNi 2π exp -x 2 γNi 2 with weights w i = 1 D and process

∀k ∈ {1, 2}, M k (t) = i∈[D] w i f Ni,γ (x) exp xS t,k - 1 2 x 2 N t,k dx , which satisfies M k (0) = 1 for all k ∈ {1, 2}.
As in the proof of Lemma 42, we obtain that M 1 (t) and M 2 (t) are non-negative supermartingale such that

∀k ∈ {1, 2}, M k (t) ≥ 1 D 1 (1 + γ -1 )(1 + η) exp S 2 t,k 2(1 + γ)N t,k .
where we used (i

1 , i 2 ) ∈ [D] 2 and consider N t,k ∈ [N i k , N i k +1 ) for all k ∈ {1, 2}. Let us define M (t) = M 1 (t 1 )M 2 (t 2 )
. Then, we have that M (t) is a non-negative supermartingale such that

M (t) ≥ 1 D 2 1 (1 + γ -1 )(1 + η) exp   1 2(1 + γ) k∈{1,2} S 2 t,k N t,k  
Using Ville's maximal inequality for non-negative supermartingale, we have that with probability greater than 1 -δ, log M (t) ≤ log (1/δ). Therefore, with probability greater than 1 -δ, for all

(i 1 , i 2 ) ∈ [D] 2 and N t,k ∈ [N i k , N i k +1 ) for all k ∈ {1, 2}, k∈{1,2} S 2 t,k N t,k ≤ 2(1 + γ) log (1/δ) + 2 log D + log(1 + γ -1 ) + log(1 + η) .
Since this upper bound is independent of t, we can optimize it and choose γ as in Lemma 43.

Therefore, with probability greater than 1 -δ, for all

(i 1 , i 2 ) ∈ [D] 2 and N t,k ∈ [N i k , N i k +1 ) for all k ∈ {1, 2}, k∈{1,2} S 2 t,k N t,k ≤ 2W -1 (log (1/δ) + 2 log D + log(1 + η) + 1) ≤ 2W -1 (log (1/δ) + 2 log (2 + log n) + 2)
The second inequality is obtained as in Lemma 42 by using that D ≤ 1 + log n log(1+η) , W -1 increasing, taking η = e 2 -1 and using 3 -2 log 2 ≤ 2.

Since [n] ⊆ i∈[D] [N i , N i+1 ), N t,k ≤ n and N t,k (µ t,k -µ k ) = S t,k (unit-variance), this yields P   ∃t ≤ n, k∈{1,2} N t,k 2 (µ t,k -µ k ) 2 ≥ W -1 (log (1/δ) + 2 log (2 + log n) + 2)   ≤ δ .
Let C(n, δ) := W -1 (log (1/δ) + 2 log (2 + log n) + 2). In the following, we consider that we are under the event,

E n,δ (1, 2) :=    ∀t ≤ n, k∈{1,2} N t,k 2 (µ t,k -µ k ) 2 < C(n, δ)    ,
which has probability at least 1 -δ. Since it satisfies the above constraint, the quantity µ t,1 -µ 1 -

(µ t,2 -µ 2 ) is upper bounded by max x∈R 2 {µ t,1 -µ t,2 -x 1 + x 2 } subject to k∈{1,2} N t,1 2 (µ t,k -x k ) 2 ≤ C(n, δ) .
Introducing a Lagrange multiplier α, the above optimization problem is equivalent to

min α≥0 max x∈R 2    µ t,1 -µ t,2 -x 1 + x 2 + α   C(n, δ) - k∈{1,2} N t,k 2 (µ t,k -x k ) 2      .
Solving for x by cancelling the derivative yields that x 1 = µ t,1 -1 αNt,1 and x 2 = µ t,2 + 1 αNt,2 . Therefore, we obtain as solution

min α≥0    αC(n, δ) + 1 2α k∈{1,2} 1 N t,k    = 2C(n, δ) k∈{1,2} 1 N t,k ,
where the last equality is obtained by solving the optimization since the derivative is null at α = k∈{1,2} 1 2C(n,δ)N t,k . By symmetry, we obtain the same result to upper bound µ t,2 -µ 2 -(µ t,1µ 1 ). Therefore, under E n,δ (1, 2), we have shown that

|µ t,1 -µ 1 -(µ t,2 -µ 2 )| 1/N t,1 + 1/N t,2 ≤ 2W -1 (log (1/δ) + 2 log (2 + log n) + 2) .
The same argument as above can be applied for all (i, k) ∈ [K] 2 such that i = k. A direct union bound yields

P ν (( Ẽ2 n,δ ) ) ≤ (i,k)∈[K] 2 ,i =k P ν E n,δn -s (i, k) ≤ K(K -1) 2 δ n s ,
where we used the inclusion proven above for (n, δ/n s ). This concludes the proof.

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

Lemma 45. Let s > 1. Let (E

P ν (E n,δ ) ≤ n>K Kδ n s + n>K K(K -1)δ 2n s = K(K + 1) 2 ζ(s)δ .
The same proof can be applied to upper bound n>K P ν ( Ẽ n,δ ).

Proof. Using the inclusion of events given by the assumption on (A t,δ (n, δ)) n≥t>K , we obtain

n t=K+1 1 (A t,δ (n, δ)) ≤ n t=K+1 1 (∃k t ∈ [K], T t (k t ) ≤ D kt (n, δ), T t+1 (k t ) = T t (k t ) + 1) ≤ i∈[K] n t=K+1 1 (T t (i) ≤ D i (n, δ), T t+1 (i) = T t (i) + 1) ≤ i∈[K] D i (n, δ) .
The second inequality is obtained by union bound. The third inequality is direct since the number of times one can increase by one a quantity that is positive and bounded by D i (n, δ) is at most D i (n, δ).

Tracking Lemma 46 provide general results for the K(K -1) tracking procedures both for IDS and fixed proportions, which includes the ones of Lemma 2. The main theoretical argument behind those results is based on applying Theorem 6 in [START_REF] Degenne | Structure adaptive algorithms for stochastic bandits[END_REF].

Lemma 46. For all n > K, i ∈ [K], j = i, we have

-1/2 ≤ N i n,j -(1-βn (i, j))T n (i, j) ≤ 1 i.e. -1 ≤ (T n (i, j)-N i n,j )-βn (i, j)T n (i, j) ≤ 1/2 and N i n,i -(K -1)/2 max j =i βn (i, j) ≤ j =i T n (i, j) ≤ N i n,i + K -1 min j =i βn (i, j) .
Let β ∈ (0, 1). For fixed proportions β, we have

N n,i ≥ min{β, 1 -β} T n (i) - 3(K -1) 2 .
Proof. We have K(K -1) independent two-arms C-Tracking between the challenger and the leader. Theorem 6 in [START_REF] Degenne | Structure adaptive algorithms for stochastic bandits[END_REF] yields the result. The second inequality is a simple re-ordering.

To obtain the second part, direct manipulations yield that

j =i T n (i, j) ≤ j =i
T n (i, j) -N i n,j + 1 βn (i, j) ≤ j =i (T n (i, j) -N i n,j ) + K -1 min j =i βn (i, j) , which allows to conclude since N i n,i = j =i (T n (i, j) -N i n,j ). The lower bound is obtained similarly.

The third is a direct consequence of the first part since

N n,i = j =i (T n (i, j) -N i n,j ) + j =i N j n,i ≤ β j =i T n (i, j) + (1 -β) j =i T n (j, i) + 3(K -1)/2 ≥ β j =i T n (i, j) + (1 -β) j =i T n (j, i) -3(K -1)/2 .
Having shown

max i∈[K] N n,i -   β j =i T n (i, j) + (1 -β) j =i T n (j, i)   ≤ 3(K -1)/2 , it is direct to conclude.
Methodology Lemma 47 is a standard result to upper bound the expected sample complexity of an algorithm, e.g. see Lemma 1 in [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF]. This is a key method extensively used in the literature.

Lemma 47. Let (E n ) n>K be a sequence of events and T (δ) > K be such that for n ≥ T (δ), Lemma 52 is an inversion result to upper bound a probability which is implicitly defined based on times that are implicitly defined.

E n ⊆ {τ δ ≤ n}. Then, E ν [τ δ ] ≤ T (δ) + n>K P ν (E n ). Proof. Since B/A + log A > 1, we have C(A, B) ≥ A, hence C(A, B) = sup {x | x < A log(x) + B} = sup {x ≥ A | x < A log(x) + B} . Using Lemma 49 yields that x ≥ A log x + B ⇐⇒ x A -log x A ≥ B A + log A ⇐⇒ x ≥ AW -1 B A + log A .
Lemma 52. Let W -1 defined in Lemma 49. Let A > 0, B > 0, C > 0, E > 0, α > 0, β > 0 and

D A,B,C (δ) = sup {x | x ≤ A(log(1/δ) + C log x) + B} , D A,B,C,E,α,β (δ) = sup x | x ≤ A α W -1 (α (log(1/δ) + C log(β + log x) + E)) + B .
Then,

inf{δ | x > D A,B,C (δ)} ≤ x C exp - x -B A , inf{δ | x > D A,B,C,E,α,β (δ)} ≤ e E α x -B A 1/α (β + log x) C exp - x -B A .
Proof. Direct manipulations yield that

x > D A,B,C (δ) ⇐⇒ x > A(log(1/δ) + C log x) + B ⇐⇒ δ < x C exp - x -B A .
Likewise, using Lemma 49, we obtain

x > D A,B,C,E,α,β (δ) ⇐⇒ α x -B A > W -1 (α (log(1/δ) + C log(β + log x) + E)) ⇐⇒ x -B A - 1 α log α x -B A > log(1/δ) + C log(β + log x) + E ⇐⇒ δ < e E α x -B A 1/α (β + log x) C exp - x -B A .

I Multiplicative setting

Let ν ∈ D K with mean parameters µ ∈ (R + ) K . Compared to the additive setting, we only consider strictly positive mean parameters. In many applications, this assumption is natural. In other applications, there is a known lower bound on the value of the true mean parameters, hence we can simply translate the problem by adding this lower bound. We also note that the problem of identifying which arms are above the threshold 0 is the thresholding bandit problem, which has been extensively studied in the literature. Overall, while this assumption might seem restrictive, we think it is rather mild. Since the means are strictly positive, the multiplicative error ε has also to be positive and strictly smaller than 1. Given a multiplicative error ε ∈ [0, 1), the set of multiplicative ε-good arms are denoted by

I mul ε (µ) := {i ∈ [K] | ∆ i ≤ µ ε}.
We will refer to this problem as multiplicative ε-BAI.

First, we discuss the characteristic times involved in the fixed-confidence multiplicative ε-BAI (Appendix I.1). Second, for ε 0 ∈ (0, 1), we present the EB-TC m ε0 with IDS or fixed β proportions (Appendix I.2). Finally, we prove that EB-TC m ε0 is asymptotically (resp. β-)optimal when using IDS (resp. fixed β) when combined with the appropriate GLR stopping rule (Appendix I.3).

I.1 Characteristic times

Let ν ∈ D K with mean parameters µ ∈ (R + ) K . We assume in the following that there exists a unique best arm, i.e. i (µ) = {i }. Let ε ∈ [0, 1). The (β-)characteristic times for the fixed confidence multiplicative ε-BAI setting with Gaussian bandits N (µ, 1) are defined as T mul ε (µ) = min i∈I mul ε (µ),β∈(0,1) T mul ε,β (µ, i) and T mul ε,β (µ) = min i∈I mul ε (µ) T mul ε,β (µ, i) where

2T mul ε,β (µ) -1 (µ, i) = max w∈ K ,wi=β min j =i (µ i -(1 -ε)µ j ) 2 1/β + (1 -ε) 2 /w j , (30)
We denote by w mul ε (µ, i) and w mul ε,β (µ, i) their maximizer, which we refer to as the (β-)optimal allocation for multiplicative ε-BAI.

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

• T mul ε (µ) = min β∈(0,1) T mul ε,β (µ, i ) and T mul ε,β (µ) = T mul ε,β (µ, i ), meaning the unique best arm corresponds to the arm which is the easiest to verify multiplicative ε-BAI.

• w mul ε (µ) = {w mul ε } and w mul ε,β (µ) = {w mul ε,β }, meaning there is a unique (β-)optimal allocation which satisfies min i∈[K] (w mul ε ) i > 0 and min i∈[K] (w mul ε,β ) i > 0. • There is equality at the equilibrium of the transportation costs, meaning for all i = i

(µ i -(1 -ε)µ i ) 2 (w mul ε ) -1 i + (1 -ε) 2 (w mul ε ) -1 i = 2T mul ε (µ) -1 and (µ i -(1 -ε)µ i ) 2 β -1 + (1 -ε) 2 (w mul ε,β ) -1 i = 2T mul ε,β (µ) -1 , (31)
and the multiplicative overall balance equation is satisfied

i =i (w mul ε ) i (w mul ε ) i 2 = (1 -ε 0 ) 2 . ( 32
)
For the sake of space, we omit the proofs and defer the reader to Appendix C for ideas on how to prove them.

I.2 Anytime Top Two algorithm

Let ε 0 ∈ (0, 1). The EB-TC m ε0 algorithm, detailed in Figure 3, has the same structure as EB-TC ε0 . There are two differences. First, the IDS proportions are β n (i, j) = N n,j /((1 -ε 0 ) 2 N n,i + N n,j ) when considering multiplicative ε-BAI. Second, the challenger will be based on transportation costs for multiplicative ε-BAI, namely

C TC m ε 0 n ∈ arg min i =B EB n µ n,B EB n -(1 -ε 0 )µ n,i 1/N n,B EB n + (1 -ε 0 ) 2 /N n,i . ( 33
)
Stopping rule for fixed-confidence multiplicative ε-BAI Similarly, the fixed-confidence setting requires a stopping rule, which will be different since we tackle multiplicative ε-BAI. Given an error/confidence pair (ε, δ) ∈ [0, 1) × (0, 1), the GLR m ε stopping rule [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] prescribes to stop at the time

τ mul ε,δ = inf n > K | min i =în µ n,în -(1 -ε)µ n,i 1/N n,în + (1 -ε) 2 /N n,i ≥ 2c(n -1, δ) , (34)
where c : N × (0, 1) → R + is a threshold function. Lemma 53 gives a threshold ensuring that the GLR m ε stopping rule is (ε, δ)-PAC for all ε ∈ [0, 1) and δ ∈ (0, 1), independently of the sampling rule. Lemma 53. Let ε ∈ [0, 1) and δ ∈ (0, 1). Given any sampling rule, using the threshold (4) with the stopping rule [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF] with error/confidence pair (ε, δ) yields a (ε, δ)-PAC algorithm for sub-Gaussian distributions.

Proof. The proof of Lemma 53 is actually almost identical to the one of Lemma 3. The only change is at the beginning of the proof. Since în = i (µ n ), standard manipulations yield that for all i = în

(µ n,în -(1 -ε)µ n,i ) 2 1/N n,în + (1 -ε) 2 /N n,i = inf u∈R N n,în (µ n,în -u) 2 + N n,i (µ n,i -u/(1 -ε)) 2 = inf y≥x/(1-ε) N n,în (µ n,în -x) 2 + N n,i (µ n,i -y) 2 .
Let i = i (µ). Using the stopping rule [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF] and the above manipulations, we obtain

P ν τ mul ε,δ < +∞, îτ mul ε,δ / ∈ I mul ε (µ) ≤ P ν ∃n ∈ N, ∃i / ∈ I mul ε (µ), i = i (µ n ), min k =i inf y≥x/(1-ε)
N n,în (µ n,în -x) 2 + N n,i (µ n,i -y) 2 ≥ 2c(n -1, δ)

≤ P ν ∃n ∈ N, ∃i / ∈ I mul ε (µ), i = i (µ n ), N n,i 2 (µ n,i -µ i ) 2 + N n,i 2 (µ n,i -µ i ) 2 ≥ c(n -1, δ) ≤ i / ∈I mul ε (µ) P ν ∃n ∈ N, N n,i 2 (µ n,i -µ i ) 2 + N n,i 2 (µ n,i -µ i ) 2 ≥ c(n -1, δ) ,
where the second inequality is obtained with (k, x, y) = (i , µ i , µ i ) since i / ∈ I mul ε (µ), and the third by union bound. Then, we can conclude as in Appendix G.1 that

P ν τ mul ε,δ < +∞, îτ mul ε,δ / ∈ I mul ε (µ) ≤ δ .
Asymptotic expected sample complexity While Theorem 8 holds for all sub-Gaussian distributions, it is particularly interesting for Gaussian ones, in light of Lemma 1. It shows that, for multiplicative ε-BAI, EB-TC m ε0 is asymptotically optimal for Gaussian bandits when using IDS proportions and asymptotically β-optimal when using fixed proportions β. Theorem 8. Let ε 0 ∈ (0, 1), β ∈ (0, 1) and δ ∈ (0, 1). Using the threshold (4) in the stopping rule [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF] with error/confidence (ε 0 , δ), the EB-TC m ε0 algorithm is (ε 0 , δ)-PAC and it satisfies that, for all ν ∈ D K such that |i (µ)| = 1,

[IDS] lim sup δ→0 E ν [τ ε0,δ ] log(1/δ) ≤ T mul ε0 (µ) and [fixed β] lim sup δ→0 E ν [τ ε0,δ ] log(1/δ) ≤ T mul ε0,β (µ)
.

I.3 Proof of Theorem 8

The proof is very similar to the one of Theorem 1, hence we will only highlight key differences. We defer the reader to Appendix D for a detailed discussion on the proof method and intuition on the different steps of the proof, see also [START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF][START_REF] Jourdan | Top two algorithms revisited[END_REF][START_REF] You | Information-directed selection for top-two algorithms[END_REF].

In the following, we consider a slack ε 0 for EB-TC m ε0 which matches the error ε considered by the GLR m ε stopping rule [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF], i.e. ε 0 = ε. For conciseness, we denote w = w mul ε and w β = w mul ε,β . Let γ > 0. Let us define the convergence times T ε0,γ and T ε0,β,γ as in ( 10) and ( 14), i.e.

T ε0,γ := inf T ≥ 1 | ∀n ≥ T, max i =i N n,i N n,i - w i w i ≤ γ , T ε0,β,γ := inf T ≥ 1 | ∀n ≥ T, N n n -1 -w β ∞ ≤ γ .
Lemma 54 gives a sufficient condition for asymptotic optimality and asymptotic β-optimality. The proof is the same as for Lemmas 13 and 25, hence we omit it.

Lemma 54. Let ε 0 ∈ (0, 1) and δ ∈ (0, 1). Assume that there exists γ 1 (µ) > 0 such that for all γ ∈ (0, γ 1 (µ)], E ν [T ε0,γ ] < +∞. Using the threshold (4) in the stopping rule (3) with error ε 0 yields an algorithm such that, for all ν

∈ D K such that |i (µ)| = 1, lim sup δ→0 E ν [τ ε0,δ ] log (1/δ) ≤ T mul ε0 (µ) .
Assume that there exists γ 1 (µ) > 0 such that for all γ ∈ (0, γ 1 (µ)], E ν [T ε0,β,γ ] < +∞. Using the threshold (4) in the stopping rule (3) with error ε 0 yields an algorithm such that, for all ν

∈ D K such that |i (µ)| = 1, lim sup δ→0 E ν [τ ε0,δ ] log (1/δ) ≤ T mul ε0,β (µ)
.

I.3.1 Sufficient exploration

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

Lemma 55. Let S L n and I n as in [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF]. There exists L 0 with E µ [(L 0 ) α ] < +∞ for all α > 0 such that if L ≥ L 0 , for all n such that S L n = ∅, for all (i, j) ∈ I n × S L n such that i = j, we have

µ n,i -(1 -ε 0 )µ n,j 1/N n,i + (1 -ε 0 ) 2 /N n,j ≥ √ LD µ ,
where D µ > 0 is a problem dependent constant.

Proof. Using Lemma 12 and min{N n,i , N n,j } ≥ L, we obtain

µ n,i -(1 -ε 0 )µ n,j ≥ µ i -(1 -ε 0 )µ j -W µ log(e + N n,i ) N n,i + (1 -ε 0 ) log(e + N n,j ) N n,j ≥ ε 0 min i∈[K] µ i -(2 -ε 0 )W µ log(e + L) L ≥ ε 0 min i∈[K] µ i /2 ,
where the last inequality is obtained for L ≥ L 0 = L 1 -e which is defined as

L 1 = sup x | x < 4(2 -ε 0 ) 2 W 2 µ ε 2 0 min i∈[K] µ 2 i log(x) + e < h 1 4(2 -ε 0 ) 2 W 2 µ ε 2 0 min i∈[K] µ 2 i , 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) ∼ x→+∞ x log x, we have E µ [(L 0 ) α ] < +∞ for all α > 0 by using Lemma 12 (polynomial in W µ ). Then, we have

µ n,i -(1 -ε 0 )µ n,j 1/N n,i + (1 -ε 0 ) 2 /N n,j ≥ ε 0 min i∈[K] µ i /2 1/N n,i + (1 -ε 0 ) 2 /N n,j ≥ √ L ε 0 min i∈[K] µ i 2 1 + (1 -ε 0 ) 2 . Using that β n (i , C n )N n,i = (1 -β n (i , C n ))N n,Cn /(1 -ε 0 ) 2 since β n (i , C n ) = N n,Cn /((1 - ε 0 ) 2 N n,i + N n,Cn
) and the inequalities proven in Lemma 19, we can exhibit deterministic constants A, B > 0 (depending on K and ε

0 ) such that |G n+1 -G n | ≤ AN 1 + B hence |G n | ≤ (n -1 -N 1 )(AN 1 + B) + (1 -ε 0 ) 2 .
where the second inequality is obtained by telescopic sum (as in Lemma 19) and using that G

N1+1 = β N1 (i , C N1 ) 2 -(1 -β N1 (i , C N1 )) 2 /(1 -ε 0 ) 2 .
As in Lemma 19, it is possible to exhibit deterministic constants C, D > 0 (depending on K and ε 0 ) such that

N n,i n -1 2 - i =i 1 1 -ε 0 N n,i n -1 2 - G n (n -1) 2 ≤ CN 1 + D n -1 .
Combining both results, we can show

N n,i n -1 2 - i =i 1 1 -ε 0 N n,i n -1 2 ≤ (A + C)N 1 + B + D n -1 + (1 -ε 0 ) 2 (n -1) 2 .
Therefore, we have shown the desired result for n ≥ N 2 defined as

N 2 = inf n > 2 | (A + C)N 1 + B + D n -1 + (1 -ε 0 ) 2 (n -1) 2 ≤ γ , which satisfies E ν 2 ] < +∞ since it is a linear function of N 1 .
As in [START_REF] You | Information-directed selection for top-two algorithms[END_REF], using Lemma 59 allows to bound the empirical proportion allocated to the unique best arm N n,i /(n -1) away from 0 (Lemma 60).

Lemma 60. There exists

N 3 with E ν [N 3 ] < +∞ such that for all n ≥ N 3 c L ≤ N n,i n -1 ≤ c U where c U = (1 -ε 0 ) 2 /2 + 1 (1 -ε 0 ) 2 + 1 and c L = 1 -c U (1 -ε 0 ) 2(K -1) .
Proof. Let N 2 as in Lemma 59 for

γ ≥ (1 -ε 0 ) 2 N n,i n -1 2 - i =i N n,i n -1 2 ≥ (1 -ε 0 ) 2 N n,i n -1 2 -1 - N n,i n -1 2 = (1 -ε 0 ) 2 -1 N n,i n -1 2 + 2 N n,i n -1 -1 ≥ (1 -ε 0 ) 2 + 1 N n,i n -1 2 -1 .
where we used that

N n,i n-1 ≤ 1. Taking γ = (1 -ε 0 ) 2 /2 yields the upper bound. Let Ñ2 as in Lemma 59 for γ (K-1)(1-ε0) 2 . Using Lemma 59, we obtain for all n ≥ max{N 2 , Ñ2 } -γ ≤ (K -1)(1 -ε 0 ) 2 N n,i n -1 2 -(K -1) i =i N n,i n -1 2 ≤ (K -1)(1 -ε 0 ) 2 N n,i n -1 2 -1 - N n,i n -1 2 ≤ (K -1)(1 -ε 0 ) 2 N n,i n -1 2 -(1 -c U ) 2 Taking γ = (1 -c U ) 2 /2 yields the lower bound. Note that c L ≤ c U ⇐⇒ 1 ≤ (1 -ε 0 ) 2 /2 + 1 (1 -ε 0 ) 2 + 1 2(K -1)(1 -ε 0 ) 2 + 2 2(K -1)(1 -ε 0 ) + 1 ,
where the last condition is trivially true. Taking N 3 = max{N 2 , Ñ2 } yields the result. combining Lemma 59 and Lemma 60.

Lemma 61. Let γ > 0. There exists

N 4 with E ν [N 4 ] < +∞ such that for all n ≥ N 4 (1 -ε 0 ) 2 - i =i N n,i N n,i 2 ≤ γ .
Proof. Let N 3 and c L as in Lemma 60. Let N 2 as in Lemma 59 for γc 2 L /(1 -ε 0 ) 2 . Direct manipulation shows that, for all n ≥ N 4 = max{N 2 , N 3 },

1 - i =i 1 1 -ε 0 N n,i N n,i 2 = n -1 N n,i 2 N n,i n -1 2 - i =i 1 1 -ε 0 N n,i n -1 2 ≤ 1 c 2 L γc 2 L = γ (1 -ε 0 ) 2 .
This concludes the result.

I.3.3 Convergence towards optimal allocation

As in [START_REF] You | Information-directed selection for top-two algorithms[END_REF], we show that a challenger will not be sampled next when the ratio of its empirical proportion compared to the one of i overshoots the ratio of the optimal allocations (Lemma 62).

Lemma 62. Let γ > 0. There exists N 5 with E ν [N 5 ] < +∞ such that for all n ≥ N 5 and all i = i ,

N n,i N n,i ≥ w i w i + γ =⇒ C TC m ε 0 n = i . Proof. Let γ > 0. Let i = i such that N n,i N n,i ≥ w i w i + γ .
Let N 4 as in Lemma 61. As in Lemma 22, we can show for all n ≥ N 4 ∃j / ∈ {i , i}, N n,j N n,i ≤ w j w i .

Let N 1 as in Lemma 18. Using that B EB n = i for all n ≥ N 1 and the definition of

C TC m ε 0 n , we known that µ n,i -(1 -ε 0 )µ n,i 1/N n,i + (1 -ε 0 ) 2 /N n,i > µ n,i -(1 -ε 0 )µ n,j 1/N n,i + (1 -ε 0 ) 2 /N n,j =⇒ C TC m ε 0 n = 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 ≥ max{N 1 , N 4 }, we obtain

µ n,i -(1 -ε 0 )µ n,i µ n,i -(1 -ε 0 )µ n,j 1 + (1 -ε 0 ) 2 N n,i /N n,j 1 + (1 -ε 0 ) 2 N n,i /N n,i ≥ µ n,i -(1 -ε 0 )µ n,i µ n,i -(1 -ε 0 )µ n,j 1 + (1 -ε 0 ) 2 w i /w j 1 + (1 -ε 0 ) 2 (w i /w i + γ) -1 .
Let γ > 0. Using Lemmas 12 and 18, we have, for all n ≥ N 1 and all k = i , In comparison, EB-TC ε0 relies on K(K -1) tracking procedures both for fixed proportion β and IDS proportions [START_REF] You | Information-directed selection for top-two algorithms[END_REF]. In [START_REF] You | Information-directed selection for top-two algorithms[END_REF], they consider IDS proportions to define β n adaptively. For Gaussian with known homoscedastic variance, their update mechanism is

µ n,i -(1 -ε 0 )µ n,k µ i -(1 -ε 0 )µ k -1 ≤ W µ (1 -ε 0 ) log(e+N n,k ) N n,k + log(e+N n,i ) N n,i µ i -(1 -ε 0 )µ k ≤ (2 -ε 0 )W µ min k =i (µ i -(1 -ε 0 )µ k ) log(e + n/K) n/K ≤ γ J.
β n = N n,Bn d KL (µ n,Bn , u n (B n , C n )) N n,Bn d KL (µ n,Bn , u n (B n , C n )) + N n,Cn d KL (µ n,Cn , u n (B n , C n )) = N n,Cn N n,Bn + N n,Cn ,
where the second equality is obtained by direct computations which uses that

u n (i, j) = inf x∈R [N n,i d KL (µ n,i , x) + n,j d KL (µ n,j , x)] = N n,i µ n,i + N n,j µ n,j N n,i + N n,j .
[8] proposed a new methodology called Balancing Optimal Large Deviations (BOLD) to select I n ∈ {B n , C n } adaptively. While their approach aims at minimizing the probability of incorrect selection (i.e. fixed-budget setting), it is possible to adapt their idea to minimize the expected sample complexity (i.e. fixed-confidence setting) by "swapping" the arguments of the KL divergence.

Namely, the BOLD procedure can be rewritten in our setting as selecting

I n = B n if i =Bn d KL (µ n,Bn , u n (B n , i)) d KL (µ n,i , u n (B n , i)) > 1 ,
and I n = C n otherwise. For Gaussian with known homoscedastic variance, their approach recovers the heuristic "adaptive Welch divergence" algorithm of proposed in [START_REF] Shin | Tractable sampling strategies for ordinal optimization[END_REF], i.e.

I n = B n if N 2 n,Bn < i =Bn N 2
n,i , and I n = C n otherwise. The analysis of [START_REF] Chen | Balancing optimal large deviations in sequential selection[END_REF] is focused on asymptotic guarantees in probability. It is an interesting direction for future research to show that the BOLD procedure also yields asymptotically optimal algorithms. TTTS [START_REF] Russo | Simple Bayesian algorithms for best arm identification[END_REF] uses a TS (Thompson Sampling) leader and a RS (Re-Sampling) challenger based on a sampler Π n . For Gaussian bandits, the sampler Π n is the posterior distribution × i∈[K] N (µ n,i , 1/N n,i )

given the improper prior Π 1 = (N (0, +∞)) K . The TS leader is B TS n ∈ arg max i∈[K] θ i where θ ∼ Π n . The RS challenger samples vector of realizations θ ∈ Π n until B n / ∈ arg max i∈[K] θ i , then it is defined as C RS n arg max i∈[K] θ i for this specific vector of realization. When the posterior Π n and the leader B n have almost converged towards the Dirac distribution on µ and the best arm i (µ) respectively, the event B n / ∈ arg max i∈[K] θ i becomes very rare. The experiments in [START_REF] Jourdan | Top two algorithms revisited[END_REF] reveals that computing the RS challenger can require more than millions of re-sampling steps. Therefore, the RS challenger can become computationally intractable even for Gaussian distribution where sampling from Π n can be done more efficiently. T3C [START_REF] Shang | Fixed-confidence guarantees for bayesian best-arm identification[END_REF] combines the TS leader and the TC challenger. EB-TCI [START_REF] Jourdan | Top two algorithms revisited[END_REF] combines the EB leader with the TCI challenger defined as

C TCI n = arg min i =Bn 1 (µ n,Bn > µ n,i ) (µ n,Bn -µ n,i ) 2 2(1/N n,Bn + 1/N n,i ) + log(N n,i ) .
TTUCB [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF] combined the TC challenger with a UCB leader which is defined as

B UCB n = arg max i∈[K] {µ n,i + g(n)/N n,i } ,
where g(n)/N n,i is a bonus coping for uncertainty. TS-KKT [START_REF] You | Information-directed selection for top-two algorithms[END_REF] uses the TS leader and a challenger based on transportation costs with a different penalization than the one used in [START_REF] Jourdan | Top two algorithms revisited[END_REF], namely

C n ) ∈ arg min i =Bn (µ n,Bn -µ n,i ) 2 2(1/N n,Bn + 1/N n,i ) - ρ n log (1/N n,Bn + 1/N n,i ) ,
where ρ is a parameter that needs to be selected beforehand. The authors highlight that the choice of ρ has an important impact on the empirical performance.

While the above Top Two algorithms are BAI algorithms, we can adapt them straightforwardly to tackle the ε-BAI setting by (1) using the stopping rule as in ( 3) and (2) using transportation costs for ε-BAI, i.e. the ones in (2). The modification (1) is inspired by [START_REF] Jourdan | Choosing answers in ε-best-answer identification for linear bandits[END_REF] and the modification (2) by [START_REF] Jourdan | Dealing with unknown variances in best-arm identification[END_REF].

As an example, the modified TCI challenger can be written as

C TCI n = arg min i =Bn 1 (µ n,Bn > µ n,i ) (µ n,Bn -µ n,i + ε) 2 2(1/N n,Bn + 1/N n,i ) + log(N n,i ) .
Fixed-confidence BAI algorithms At each time n, Track-and-Stop (TaS) [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] computes the optimal allocation for the current empirical mean, w n = w (µ n ). Given w n ∈ K , it uses a tracking procedure to obtain an arm I n to sample. On top of this tracking a forced exploration is used to enforce convergence towards the optimal allocation for the true unknown parameters. The optimization problem defining w (µ) can be rewritten as solving an equation ψ µ (r) = 0, where

∀r ∈ (1/ min i =i (µ i -µ i ) 2 , +∞), ψ µ (r) = i =i 1 (r(µ i -µ i ) 2 -1) 2 -1
The function ψ µ is decreasing, and satisfies lim r→+∞ ψ µ (r) = -1 and lim y→1/ min i =i (µ i -µi) 2 F µ (y) = +∞. For the practical implementation of the optimal allocation, we use the approach of [START_REF] Garivier | Optimal best arm identification with fixed confidence[END_REF] and perform binary searches to compute the unique solution of ψ µ (r) = 0. A faster implementation based on Newton's iterates was proposed by [START_REF] Barrier | A non-asymptotic approach to best-arm identification for gaussian bandits[END_REF] after proving that ψ µ is convex. While this improvement holds only for Gaussian distributions, the binary searches can be used for more general distributions. Similarly, one can adapt TaS to tackle ε-BAI as done in [START_REF] Garivier | Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models[END_REF], i.e. by tracking w n = w ε (µ n ). Using Lemma 9, it is direct to see that one can use the same implementation to compute it efficiently. DKM [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF] view T (µ) -1 as a min-max game between the learner and the nature, and design saddlepoint algorithms to solve it sequentially. At each time n, a learner outputs an allocation w n , which is used by the nature to compute the worst alternative mean parameter λ n . Then, the learner is updated based on optimistic gains based on λ n . Similarly, one can adapt DKM to tackle ε-BAI by using a modified alternative mean parameter. This coincides with the LεBAI algorithm [START_REF] Jourdan | Choosing answers in ε-best-answer identification for linear bandits[END_REF] when used on unstructured multi-armed bandits.

FWS [START_REF] Wang | Fast pure exploration via frank-wolfe[END_REF] alternates between forced exploration and Frank-Wolfe (FW) updates. Similarly, FWS can be adapted to tackle ε-BAI LUCB [START_REF] Kalyanakrishnan | PAC subset selection in stochastic multi-armed bandits[END_REF] samples and stops based on upper/lower confidence indices for a bonus function g. For Gaussian distributions, it rewrites for all i ∈ [K] as

U n,i = µ n,i + 2c(n -1, δ) N n,i and L n,i = µ n,i - 2c(n -1, δ) N n,i .
At each time n, it samples în and arg max i =în U n,i . For ε-BAI, LUCB stops when L n,în + ε ≥ max i =în U n,i .

Fixed-budget BAI algorithms We consider Successive Reject (SR) [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF] and Sequential Halving (SH) [START_REF] Karnin | Almost optimal Exploration in multi-armed bandits[END_REF]. SR eliminates one arm with the worst empirical mean at the end of each phase, and SH eliminated half of them but drops past observations between each phase. Within each phase, both algorithms use a round-robin uniform sampling rule on the remaining active arms. It is possible to convert the fixed-budget SH algorithm into an anytime algorithm by using the doubling trick. It considers a sequences of algorithms that are run with increasing budgets (T k ) k≥1 , with T k+1 = 2T k and T 1 = 2K log 2 K , and recommend the answer outputted by the last instance that has finished to run. It is well know that the "cost" of doubling is to have a multiplicative factor 4 in front of the hardness constant. The first two-factor is due to the fact that we forget half the observations. The second two-factor is due to the fact that we use the recommendation from the last instance of SH that has finished. The doubling version of SR and SH are named Doubling SR (DSR) and Doubling SH (DSH).

Reproducibility Our code is implemented in Julia 1.9.0, and the plots are generated with the StatsPlots.jl package. Other dependencies are listed in the Readme.md. The Readme.md file also provides detailed julia instructions to reproduce our experiments, as well as a script.sh to run them all at once. The general structure of the code (and some functions) is taken from the

Random instances

We further investigate the phenomenon described above on random instances. For ε ∈ {0.05, 0.1}, we assess the performance on 1000 random Gaussian instances with K = 5 (resp. K = 10 and K = 10) such that µ 1 = 1, µ i ∼ U([1 -ε, 1]) for i ∈ {2} (resp. i ∈ {2, 3} and i ∈ {2, 3, 4}) and µ i ∼ U([0, 1 -ε)) for i ≥ 3 (resp. i ≥ 4 and i ≥ 6), hence I ε (µ) = [START_REF] Avner | Decoupling exploration and exploitation in multi-armed bandits[END_REF] (resp. I ε (µ) = [START_REF] Barrier | A non-asymptotic approach to best-arm identification for gaussian bandits[END_REF] and I ε (µ) = [START_REF] Bubeck | Pure Exploration in Finitely Armed and Continuous Armed Bandits[END_REF]). We display the boxplots of the empirical stopping time on 1000 runs.

In Figure 5, the tendencies glimpsed by inspecting Figure 4 are more apparent. Figure 5 shows that better empirical performance are obtained when using a slack ε 0 which matches the error ε, i.e. choosing ε 0 = ε to tackle ε-BAI. We also see that the empirical gain of taking ε 0 = ε is increasing with the dimension K. Figure 5 shows that ε 0 > ε slightly damage the empirical performance: the larger the missmatch ε 0 -ε is, the worse the performances are. Moreover, Figure 5 highlights how choosing ε 0 < ε is highly detrimental to the empirical performance. Finally, we see that there is a mild advantage in using IDS over fixed β = 1/2. Note that the mild empirical gain of adaptive proportions is a known phenomenon which was studied empirically in [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF], and larger gains can be observed for "two-groups" instances. Intuitively, the characteristic times T ε (µ) and T ε,1/2 (µ) are very close to each other on average, and the difference is the largest when all the sub-optimal arms have the same mean. Therefore, on average, using IDS has mild gain compared to using fixed β = 1/2. This worst-case scenario of the "two-groups" instances is studied in Figure 7.

Specific instances

We continue the experimental validation of our the phenomenon described above by considering the three specific instances from the experimental section of [START_REF] Garivier | Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models[END_REF] which are described in Table 3. Instance µ 3 corresponds to the specific instances studied in Section 5. It is particularly interesting since it has two best arms, a third ε-good arm which is equally distant from ε than the bad arm with largest mean, and has two additional bad arms. Instance µ 2 has also three ε-good arms, which are equally spaced, and three bad arms. Instance µ 1 has only one ε-good arm, and four bad arms. We display the boxplots of the empirical stopping time on 1000 runs, and the empirical simple regret on 10000 runs (with associated standard deviation). The left column of Figure 6 confirms our previous observations: taking ε = ε 0 yields the best performance, taking ε 0 > ε slightly damage performance and taking ε 0 < ε highly damage performance.

As benchmarks we consider modified BAI which are tailored to tackle ε-BAI, and we combine them with the GLR ε stopping rule. One can still wonder whether the unmodified sampling rule would perform well for ε-BAI when combined with the GLR ε stopping rule. While we could hope that modifying the stopping rule is enough, our experiments reveal that it is not the case. If we don't adapt the sampling rule as well, Table 4 shows that the empirical stopping time can be more than ten times larger than their modified version.

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

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

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

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

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

The left column of Figure 10 validates the previous conclusions as regards the good empirical performance of EB-TC ε0 compare to existing ε-BAI algorithms. We also see that it seems to perform even better when there are multiple ε-good arms and multiple best arms, i.e. Two groups We consider the "two-groups" instances µ ∈ {0.6, 0.4} 10 for varying number of best arms, i.e. |i (µ)| ∈ [START_REF] Chen | Balancing optimal large deviations in sequential selection[END_REF]. We average on 1000 runs, and the standard deviations are displayed.

Figure 11 reveals that EB-TC ε0 is the most robust to increased number of best arms, i.e. its slope is the smallest. The good performance of EB-TC ε0 is closely followed by other Top Two algorithms. This confirms that additional regularization mechanisms (e.g. TS/UCB leader or TCI challenger) are superfluous since the TCε challenger is enough to ensure sufficient exploration. ε-TaS and ε-FWS have slightly worse slope, and the one of ε-DKM seems to become less steep after a large initial increase. The highest slope is achieved by LUCB. Quite surprisingly, uniform sampling seems to reach a plateau after which it is scaling better than EB-TC ε0 (in terms of slope), while still having worse empirical performance. It would be interesting to quantify theoretically the good scaling of EB-TC ε0 with respect to increased number of best arms. Figure 12 provides additional empirical validation that EB-TC ε0 outperforms uniform sampling as well as DSR and DSH in terms of empirical simple regret. While the empirical stopping time increased with the number of best arms, Figure 12 confirms the intuition that the problem gets easier with respect to the simple regret. First, the range of empirical simple regret becomes smaller with increased number of best arms. This was expected as we have more chances to recommend one of the best arms at early stage even though this recommendation is close to random. Second, we observe a steeper decrease of the empirical simple regret with increased number of best arms. Likewise, this is a natural phenomenon since the collected data will reveal that there multiple good options very fast.

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

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

Figure 13: (Left) Empirical simple regret and (right) empirical error on instances (top to bottom) µ 3 = (0.6, 0.6, 0.55, 0.45, 0.3, 0.2), µ 2 = (0.8, 0.75, 0.7, 0.6, 0.5, 0.4), µ 1 = (0.7, 0.55, 0.5, 0.4, 0.2) and µ ∈ {0.6, 0.4} 10 with |i (µ)| ∈ {1, 3}. Average over 200 runs. We ran a different instance of SR and SH for each budget T .

Overall, according to Figure 13, EB-TC ε0 seems to perform on par with SR and SH in all instances considered, and to outperform SH for some instances. In our experiments, we consider SH in which the samples are dropped between each phase, as analyzed theoretically in [START_REF] Audibert | Best Arm Identification in Multi-armed Bandits[END_REF]. This loss of information explains why SR has better empirical performance than SH. To the best of our knowledge, there is no theoretical analysis for the heuristic SH where all the samples are preserved, even though it has better empirical performance.

J.2.3 Varying slack parameter

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

Random instances

We assess the performance on 1000 random Gaussian instances with K ∈ {5, 10, 20} such that µ 1 = 1 and µ i ∼ U([0.5, 08]) for i = 1. We display the boxplots of the empirical stopping time on 1000 runs. The most stricking feature of Figure 14 is that it reveals how poor the performance of EB-TC (εn)n can be for many choices of (ε n ) n . For the considered α, we observe that polynomial decrease is always bad since it yields roughly the same empirical performance as uniform sampling. This can be explained by the fact that this decrease is too fast, hence EB-TC (εn)n will ressemble EB-TC 0 which is know to have poor empirical performance [START_REF] Jourdan | Top two algorithms revisited[END_REF]. For the considered α, we see that polylogarithmic decrease is often bad, except for α = 0.5. In that case, it performs on par with TaS, slightly worse than standard Top Two algorithms for BAI and better than LUCB and uniform sampling. This can be explained by the fact that EB-TC (εn)n is similar to uniform sampling when the decrease is too slow. The above sensitivity analysis truly shows how difficult it is to choose (ε n ) n beforehand. The best "trade-off" between a slow decrease (yet not too slow) highly depends on the complexity of the unknown instance. While EB-TC (εn)n reaches asymptotic optimality for BAI, we recommend the practitioner to use other Top Two algorithms which enjoy the same theoretical guarantees and better empirical performance. When one needs to have a deterministic algorithms, EB-TCI seems to be the best. Without the deterministic constraint, T3C has great performance.

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

T ε0,1/2 (µ) T 0 (µ) 1 + ε 0 ∆ min 2 ≤ 4 i =i (∆ i + ε 0 ) -2 i =i ∆ -2 i 1 + ε 0 ∆ min 2 ≈ 4 if ε 0 ∆ min 4 if ε 0 ∆ min ,
where we used Lemmas 6, 9 and 7.

Specific instances

We consider the two instances µ 1 and µ 2 from Table 3 with ε = 0. Since most theoretical guarantees on BAI algorithms assume that there is a unique best arm, we don't study µ 3 . We display the boxplots of the empirical stopping time on 1000 runs. Figure 15 confirms the empirical observations from Figure 14. Overall, EB-TC (εn)n performs poorly and EB-TC ε0 has good empirical for BAI.

  otherwise set I n = B n . 5: Output: next arm to sample I n and next recommendation în .

Figure 1 :

 1 Figure 1: EB-TC ε0 algorithm with fixed or IDS proportions.

Figure 2 :

 2 Figure 2: (a) Empirical stopping time on "α = 0.3" instances for varying K and stopping rule (3) using (ε, δ) = (0.1, 0.01). The BAI algorithms T3C, EB-TCI and TTUCB are modified to be ε-BAI ones. (b) Empirical simple regret on instance µ = (0.6, 0.6, 0.55, 0.45, 0.3, 0.2), in which EB-TC ε0 with slack ε 0 = 0.1 and fixed β = 1/2 is used.

  By changing the variable, we obtain C(A, B, D) = B + A sup y | y < W -1 (2 log (2 + log(Ay + B)) + D) Likewise, Lemma 49 yields that y ≥ W -1 (2 log (2 + log(Ay + B)) + D) ⇐⇒ y -log y -2 log (2 + log(Ay + B)) ≥ D .

Figure 3 : 2 :. 3 :

 323 Figure 3: EB-TC m ε0 algorithm with fixed or IDS proportions. 1: Input: slack ε 0 ∈ (0, 1), proportion β ∈ (0, 1) (only for fixed proportions). 2: Set în ∈ arg max i∈[K] µ n,i , B EB n = în and C TC m ε 0 n

5 :

 5 Output: next arm to sample I n and next recommendation în .

Figure 5 :

 5 Figure 5: Empirical stopping time on random instances with stopping rule (3) using (left) (ε, δ) = (0.05, 0.01) and (right) (ε, δ) = (0.1, 0.01) with (top) K = 5, (middle) K = 10 and (bottom) K = 20. "c-" denotes fixed β = 1/2, without refers to IDS.

Figure 6 :

 6 Figure 6: (Left) Empirical stopping time for the stopping rule (3) using δ = 0.01 and (right) empirical simple regret on instances (top) µ 1 with ε = 0.1, (middle) µ 2 with ε = 0.15 and (bottom) µ 3 with ε = 0.1. "c-" denotes fixed β = 1/2, without refers to IDS.

  |i (µ)| > 1. The right column of Figure 10 corroborates the observations made in Figure 2(b): EB-TC ε0 outperforms uniform sampling, as well as DSR and DSH.

Figure 10 :

 10 Figure 10: (Left) Empirical stopping time for the stopping rule (3) using δ = 0.01 and (right) empirical simple regret on instances (top) µ 1 with ε = 0.1, (middle) µ 2 with ε = 0.15 and (bottom) µ 3 with ε = 0.1. The BAI algorithms T3C, EB-TCI, TTUCB, TaS, FWS, DKM are modified to be ε-BAI ones.

Figure 11 :

 11 Figure 11: Empirical stopping time with stopping rule (3) using (ε, δ) = (0.1, 0.01) on instances µ ∈ {0.6, 0.4} 10 for varying |i (µ)|. The BAI algorithms T3C, EB-TCI, TTUCB, TaS, FWS, DKM are modified to be ε-BAI ones.

Figure 12 :

 12 Figure 12: Empirical simple regret on instances µ ∈ {0.6, 0.4} 10 for |i (µ)| ∈ [6], i.e. (top left) |i (µ)| = 1 and (bottom right) |i (µ)| = 6.

Figure 14 :

 14 Figure 14: Empirical stopping time for the stopping rule (3) using (ε, δ) = (0, 0.01) on random instances with (a) K = 5, (b) K = 10 and (c) K = 20. "l" denotes ε n = log(n) -α/2 , "p" denotes ε n = n -α/2 . "a••" refers to α ∈ {0.5, 0.1, 0.05}.

Figure 15 :

 15 Figure 15: Empirical stopping time for the stopping rule (3) using (ε, δ) = (0, 0.01) on instances (a) µ 1 and (b) µ 2 . "l" denotes ε n = log(n) -α/2 , "p" denotes ε n = n -α/2 .

  , W -1 in Lemma 49, h 1 in Lemma 51, ζ is the Riemann ζ function. While Table 1 gathers problem-specific notation, Table 2 groups notation for the algorithms.

Table 2 :

 2 Notation for algorithms.

	Notation	Type	Description
	B n , B EB n C n , C TCε0 n	[K] [K]	(EB) Leader at time n (TC ε0 ) Challenger at time n
	I n	[K]	Arm sampled at time n
	X n,In	R	Sample observed at the end of time n, i.e. X n,In ∼ ν In
	F n		History before time n, i.e. F n := σ(I 1 , X 1,I1 , • • • , I n , X n,In )
	în	[K]	Arm recommended before time n
	τ ε,δ	N	Sample complexity (stopping time)
	c(n, δ)	N × (0, 1) → R + Stopping threshold function
	N n,i	N	Number of pulls of arm i before time n
	µ n,i	I	Empirical mean of arm i before time n
	T n (i, j)	N	Counts of (B t , C t ) = (i, j) before time n
	T n (i)	N	Counts of i ∈ {B t , C t } before time n
	N i n,j	N	Counts of (B t , C t , I t ) = (i, j, j) before time n
	β	(0, 1)	Fixed proportion
	β n (i, j) βn (i, j)	(0, 1) (0, 1)	IDS proportions Averaged IDS proportions

  ε) as in Lemma 36 and Hε,ε1 (µ, ε 0

  1 Implementation details Top Two sampling rules Given a fixed β, most Top Two algorithms use randomization to select I n ∈ {B n , C n }, namely they sample B n with probability β, otherwise sample C n . Instead of randomization, TTUCB [20] uses K tracking procedures to select I n ∈ {B n , C n }. Namely, they choose I n = B n if N Bn n,Bn ≤ β i =Bn T n+1 (B n , i), and I n = C n otherwise.

Table 3 :

 3 Specific instances from[START_REF] Garivier | Non-asymptotic sequential tests for overlapping hypotheses and application to near optimal arm identification in bandit models[END_REF] with corresponding ε.

	ε	Instance |I ε (µ)|			Arms
				1	2	3	4	5	6
	0.1	µ 1	1	0.7 0.55	0.5	0.4 0.2	-
	0.15	µ 2	3	0.8 0.75	0.7	0.6 0.5 0.4
	0.1	µ 3	3	0.6	0.6	0.55 0.45 0.3 0.2

δ.

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).

H Technicalities

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

Key technical result Lemma 4 is the key technical ingredient on which our proofs rely on. It builds on a sequence of "bad" events such that, under each "bad" event, either the leader or the challenger was not often selected as leader or challenger, and shows that the number of times those "bad" events occur is small. Lemma (Lemma 4). Let δ ∈ (0, 1] and n > K. Let (A t,δ (n, δ)) n≥t>K be a sequence of events and (D i (n, δ)) i∈[K] be positive thresholds satisfying that, for all t ∈ [n] \ [K], under the event A t,δ (n, δ), ∃i t ∈ [K], T t (i t ) ≤ D it (n, δ) and T t+1 (i t ) = T t (i t ) + 1 . Proof. Since the random variable τ δ is positive and {τ δ > n} ⊆ E n for all n ≥ T (δ), we have

Then, we have

which concludes the proof by adding positive terms.

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

Lemma 48. Let ε ≥ 0 and (E n,δ ) n>K,δ∈(0,1) be a sequence of events such that P ν (E n,δ ) ≤ Cδ with C > 0. Suppose that T ε (δ) > K is such that for n > T ε (δ), E n,δ ⊆ {î n ∈ I ε (µ)}. Then,

Proof. Using the assumption, we have

Taking the infimum yields the result.

Inversion results

Lemma 49 gathers properties on the function W -1 , which is used in the literature to obtain concentration results.

Lemma 49 ( [START_REF] Jourdan | Dealing with unknown variances in best-arm identification[END_REF]). Let W -1 (x) = -W -1 (-e -x ) for all x ≥ 1, where W -1 is the negative branch of the Lambert W function. The function W -1 is increasing on (1, +∞) and strictly concave on

for all x > 1. Then, for all y ≥ 1 and x ≥ 1,

Moreover, for all x > 1,

Lemma 50 provides an ordering on the thresholds for tighter concentration results. It leverages properties of W -1 .

Lemma 50. Let s ≥ 0. Let W -1 defined in Lemma 49. For all δ ∈ (0, 1] and n ≥ 1, let us denote by

Then, we have f1 (n, δ) ≤ f2 (n, δ).

Proof. Let a > 0 and b ≥ 1. Let us define f (x) = 1 x W -1 (ax + b). Using Lemma 49, we have

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

Lemma 51. Let W -1 defined in Lemma 49. Let A > 0, B > 0 such that B/A + log A > 1 and

Then, C(A, B) < h 1 (A, B) with h 1 (z, y) = zW -1 (y/z + log z) and C(A, B) < Ah 2 (A, B, D) + B where

1+(1-ε0) 2 yields the result.

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

Lemma 56. Let S L n as in [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF]. There exists L 1 with E µ [(L 1 ) α ] < +∞ for all α > 0 such that for all L ≥ L 1 and all n ∈ N,

where D 1 > 0 is a problem dependent constant and W µ is the random variables defined in Lemma 12.

Proof. Using Lemma 12 and N n,i ≥ L ≥ N n,j ≥ 1, we obtain

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

Lemma 57. There exists

Combining Lemma 16 and Lemma 57 yields Lemma 58. Importantly, Lemma 58 holds for the EB-TC ε0 algorithm with fixed proportions β ∈ (0, 1) and IDS proportions. Since the proof is the same as for Lemmas 18 and 26, we omit it.

Lemma 58. There exist

Empirical overall balance

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

Proof. Let N 1 as in Lemma 58. We proceed as in Lemma 19. Let us define

for all n ≥ N 6 = K(X 0 -e) 2 + 1 which is defined as

where the last inequality is obtained by using Lemma 51 with h 1 defined therein. Since h 1 (x, y) ∼ x→+∞ x log x, we have E ν [N 6 ] < +∞ since it polynomial in W µ (by using Lemma 12). Let κ > 0. We have shown that, for all n ≥ max{N 1 , N 4 , N 6 },

where the equality uses that the transportation costs are equal at the equilibrium, i.e. [START_REF] Mannor | The Sample Complexity of Exploration in the Multi-Armed Bandit Problem[END_REF]. Taking γ small enough, we have that shown that, for all n ≥ max{N 1 , N 4 , N 6 },

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

Lemma 63. Let γ > 0. There exists N 6 with E ν [N 6 ] < +∞ such that for all n ≥ N 6 and all i = i ,

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

Lemma 64. Let ε 0 ∈ (0, 1), γ > 0 and T ε0,γ introduced before (adaptation of (10)). Under the EB-TC m ε0 sampling rule with IDS proportions, we have E ν [T ε0,γ ] < +∞. Combining Lemmas 54 and 64 yields the first of Theorem 8.

I.3.4 Convergence towards β-optimal allocation

Combining Lemmas 58 and 27 with the proof of Lemma F.9 in [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF] yields Lemma 65.

Lemma 65. Let γ > 0. There exists N 5 with E ν [N 5 ] < +∞ such that for all n ≥ N 5 and all i = i ,

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

Lemma 66. Let ε 0 ∈ (0, 1), β ∈ (0, 1), γ > 0 and T ε0,β,γ introduced before (adaptation of (14)).

Under the EB-TC m ε0 sampling rule with fixed proportions β, we have E ν [T ε0,β,γ ] < +∞. Combining Lemmas 54 and 66 yields the second part of Theorem 8.

J Implementation details and additional experiments

After presenting the implementations details in Appendix J.1, we display supplementary experiments in Appendix J.2. tidnabbil library. This library was created by [START_REF] Degenne | Non-asymptotic pure exploration by solving games[END_REF], see https://bitbucket.org/wmkoolen/ tidnabbil. No license were available on the repository, but we obtained the authorization from the authors. Our experiments are conducted on an institutional cluster with 4 Intel Xeon Gold 5218R CPU with 20 cores per CPU and an x86_64 architecture.

J.2 Supplementary experiments

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

J.2.1 Numerical simulations on EB-TC ε0

Appendix J.2.1 is meant to be a sensitivity analysis of the EB-TC ε0 algorithm. It will allow us to numerically substantiate our recommendation to the practitioner on how to set the slack ε 0 , and why using IDS yields better empirical performance. For slacks ε 0 ∈ {0.15, 0.1, 0.05}, we will consider the EB-TC ε0 algorithms with IDS proportions and fixed proportions β = 1/2. Large sets of arms First, we evaluate the impact of larger number of arms (up to K = 1000). The "α = 0.6" scenario of [START_REF] Jamieson | Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting[END_REF] sets

The "sparse" scenario of [START_REF] Jamieson | Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting[END_REF] sets µ 1 = 1/4 and µ i = 0 otherwise. We average on 100 runs, and the standard deviations are displayed.

In Figure 4, we see that all instances of EB-TC ε0 with IDs or fixed β = 1/2 have the same scaling with the dimension K. Figure 4 also reveals that using IDS instead of fixed β = 1/2 consistently yields smaller empirical stopping time. Therefore, IDS should be preferred to choosing fixed β = 1/2. Finally, Figure 4 shows that better empirical performance are obtained when using a slack ε 0 which matches the error ε, i.e. choosing ε 0 = ε to tackle ε-BAI. While choosing ε 0 > ε only slightly damage the empirical performance, taking ε 0 < ε is clearly detrimental to the empirical performance.

Figure 6(middle left) shows that the the larger the missmatch ε -ε 0 is, the worse the performances are.

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

Two-groups instances

We conclude our sensitivity analysis on EB-TC ε0 by considering the "twogroups" instances µ ∈ {0.6, 0.4} 10 for varying number of best arms, i.e. |i (µ)| ∈ [START_REF] Chen | Balancing optimal large deviations in sequential selection[END_REF]. Our aim is to assess the impact of having multiple best arms on the empirical stopping time. We average on 1000 runs, and the standard deviations are displayed. On this specific instances where the number of arms is fixed, it would be intuitive to think that the problem is easier when there are more best arms. However, this is actually the opposite since there less bad arms (which were easy to detect) and more good arms which need to be estimated well enough. While Figure 7 shows how poor the performances are when taking ε 0 < ε, it also shows that the impact of having multiple best arms is rather mild for slacks ε 0 ≥ ε. We will see in Figure 12 that EB-TC ε0 is the most resilient algorithm with respect to multiple arms, meaning that its slope is the smallest. "Two-groups" instances are interesting since they are the instances for which the ratio T ε,1/2 (µ)/T ε (µ) is the largest. Using Lemma 9 and the theoretical results of [START_REF] Jourdan | Non-asymptotic analysis of a ucb-based top two algorithm[END_REF] (see their Lemma C.6), we conjecture that T 2 and that the equality occurs for "twogroups" instances. Since r 10 = 5/4, using fixed β = 1/2 should be roughly 25% slower than using IDS. While Figure 7 confirms that using IDS yields better empirical performance than using fixed β = 1/2, the empirical ratio between their performance is lower than the one suggested by the theory.

Table 4: Comparison between the original sampling rule and the modified sampling rule for BAI algorithms when combined with the GLR ε stopping rule (3) using (ε, δ) = (0.1, 0.01). We display the empirical stopping time (and standard deviation) on random instances with K ∈ {5, 10, 20}. J.2.2 Comparison with modified BAI algorithms Appendix J.2.2 is meant to provide further empirical evidence that EB-TC ε0 outperforms its competitors on different tasks and for different types of instances. Overall, we will use the same instances as used in Appendix J.2.1 since they provide a wide range of interesting problems. Throughout this section, we will be using EB-TC ε0 with slack ε 0 = 0.1. While IDS proportions are used for the experiments on the empirical stopping time, we use fixed β = 1/2 for the empirical simple regret.