Xuedong Shang

Rianne De Heide

Emilie Kaufmann

Pierre Ménard

Michal Valko

Fixed-confidence guarantees for Bayesian best-arm identification

come

Introduction

In multi-armed bandits, a learner repeatedly chooses an arm to play, and receives a reward from the associated unknown probability distribution. When the task is best-arm identification (BAI), the learner is not only asked to sample an arm at each stage, but is also asked to output a recommendation (i.e., a guess for the arm with the largest mean reward) after a certain period. Unlike in another well-studied bandit setting, the learner is not interested in maximizing the sum of rewards gathered during the exploration (or minimizing regret), but only cares about the quality of her recommendation. As such, BAI is a particular pure exploration setting (Bubeck et al., 2009).

Formally, we consider a finite-arm bandit model, which is a collection of K probability distributions, called arms A {1, . . . , K}, parametrized by their means µ 1 , . . . , µ K . We assume the (unknown) best arm is unique and we denote it by I arg max i µ i . A bestarm identification strategy (I n , J n , τ ) consists of three components. The first is a sampling rule, which selects an arm I n at round n. At each round n, a vector of re-

wards Y n = (Y n,1 , • • • , Y n,K
) is generated for all arms independently from past observations, but only Y n,In is revealed to the learner. Let F n be the σ-algebra generated by (U 1 , I 1 , Y 1,I1 , • • • , U n , I n , Y n,In ), then I n is F n-1 -measurable, i.e., it can only depend on the past n -1 observations, and some exogeneous randomness, materialized into U n-1 ∼ U([0, 1]). The second component is a F n -measurable recommendation rule J n , which returns a guess for the best arm, and thirdly, the stopping rule τ , a stopping time with respect to (F n ) n∈N , decides when the exploration is over. BAI has already been studied within several theoretical frameworks. In this paper we consider the fixed-confidence setting, introduced by Even-dar et al. (2003), in which given a risk parameter δ, the goal is to ensure that probability to stop and recommend a wrong arm, P [J τ = I ], is smaller than δ, while minimizing the expected total number of samples to make this accurate recommendation, E [τ ]. The most studied alternative is the fixed-budget setting for which the stopping rule τ is fixed to some (known) maximal budget n, and the goal is to minimize the error probability P [J n = I ] (Audibert and Bubeck, 2010). Note that these two frameworks are very different in general and do not share transferable regret bounds (see Carpentier and Locatelli 2016 for an additional discussion).

Most of the existing sampling rules for the fixedconfidence setting depend on the risk parameter δ. Some of them rely on confidence intervals such as LUCB (Kalyanakrishnan et al., 2012), UGapE (Gabillon et al., 2012), or lil'UCB (Jamieson et al., 2014); others are based on eliminations such as SuccessiveElimination (Even-dar et al., 2003) and ExponentialGapElimination (Karnin et al., 2013). The first known sampling rule for BAI that does not depend on δ is the tracking rule proposed by Garivier and Kaufmann (2016), which is proved to achieve the minimal sample complexity when combined with the Chernoff stopping rule when δ goes to zero. Such an anytime sampling rule (neither depending on a risk δ or a budget n) is very appealing for applications, as advocated by Jun and Nowak (2016), who introduce the anytime best-arm identification framework. In this prove that optimal posterior convergence rates can be obtained for those two as well.

Outline In Section 2, we give a reminder of TTTS and introduce T3C along with our proposed recommendation and stopping rules. Then, in Section 3, we describe in detail two important notions of optimality that are invoked in this paper. The main fixedconfidence analysis follows in Section 4, and further Bayesian optimality results are given in Section 5. Numerical illustrations are given in Section 6.

Bayesian BAI Strategies

In this section, we give an overview of the sampling rule TTTS and introduce T3C. We provide details for Bayesian updating for Gaussian and Bernoulli models respectively, and introduce associated Bayesian stopping and recommendation rules.

Sampling rules

Both TTTS and T3C employ a Bayesian machinery and make use of a prior distribution Π 1 over a set of parameters Θ, that contains the unknown true parameter vector µ. Upon acquiring observations (Y 1,I1 , • • • , Y n-1,In-1 ), we update our beliefs according to Bayes' rule and obtain a posterior distribution Π n which we assume to have density π n w.r.t. the Lebesgue measure. Russo's analysis is restricted to strong regularity properties on the models and priors that exclude two important useful cases we consider in this paper: (1) the observations of each arm i follow a Gaussian distribution N (µ i , σ2 ) with common known variance σ 2 , with imposed Gaussian prior N (µ 1,i , σ 2 1,i ), (2) all arms receive Bernoulli rewards with unknown means, with a uniform prior on each arm.

Gaussian model For Gaussian bandits with a N (0, κ 2 ) prior on each mean, the posterior distribution of µ i at round n is Gaussian with mean and variance that are respectively given by n-1

=1 1{I = i}Y ,I T n,i + σ 2 /κ 2 and σ 2 T n,i + σ 2 /κ 2 ,
where T n,i n-1 =1 1{I = i} is the number of selections of arm i before round n. For the sake of simplicity, we consider improper Gaussian priors with µ 1,i = 0 and σ 1,i = +∞ for all i ∈ A, for which

µ n,i = 1 T n,i n-1 =1 1{I = i}Y ,I and σ 2 n,i = σ 2 T n,i .
Observe that in that case the posterior mean µ n,i coincides with the empirical mean.

Beta-Bernoulli model For Bernoulli bandits with a uniform (Beta(1, 1)) prior on each mean, the posterior distribution of µ i at round n is a Beta distribution with shape parameters α n,i = n-1 =1 1{I = i}Y ,I + 1 and β n,i = T n,i -n-1 =1 1{I = i}Y ,I + 1. Now we briefly recall TTTS and introduce T3C. Description of TTTS At each time step n, TTTS has two potential actions: (1) with probability β, a parameter vector θ is sampled from Π n , and TTTS chooses to play I

(1) n arg max i∈A θ i , (2) and with probability 1 -β, the algorithm continues sampling new θ until we obtain a challenger I

(2) n arg max i∈A θ i that is different from I

(1) n , and TTTS then selects the challenger.

Description of T3C One drawback of TTTS is that, in practice, when the posteriors become concentrated, it takes many Thompson samples before the challenger I

(2) n is obtained. We thus propose a variant of TTTS, called T3C, which alleviates this computational burden. Instead of re-sampling from the posterior until a different candidate appears, we define the challenger as the arm that has the lowest transportation cost W n (I (1) n , i) with respect to the first candidate (with ties broken uniformly at random).

Let µ n,i be the empirical mean of arm i and µ n,i,j (T n,i µ n,i + T n,j µ n,j )/(T n,i + T n,j ), then we define W n (i, j) 0 if µ n,j ≥ µ n,i , W n,i,j + W n,j,i otherwise,

(1)

where W n,i,j T n,i d (µ n,i , µ n,i,j ) for any i, j and d(µ; µ ) denotes the Kullback-Leibler between the distribution with mean µ and that of mean µ . In the Gaussian case, d(µ

; µ ) = (µ -µ ) 2 /(2σ 2 ) while in the Bernoulli case d(µ; µ ) = µ ln(µ/µ ) + (1 -µ) ln(1 - µ)/(1 -µ ).
In particular, for Gaussian bandits

W n (i, j) = (µ n,i -µ n,j ) 2 2σ 2 (1/T n,i + 1/T n,j ) 1{µ n,j < µ n,i }.
The pseudo-code of TTTS and T3C are shown in Algorithm 1. Note that under the Gaussian model with improper priors, one should pull each arm once at the beginning for the sake of obtaining proper posteriors.

W n in Line 12 of Algorithm 1 is the transportation cost defined in (1).

Rationale for T3C

In order to explain how T3C can be seen as an approximation of the re-sampling performed by TTTS, we first need to define the optimal action probabilities.

Algorithm 1 Sampling rule (TTTS/T3C)

1: Input: β 2: for n ← 1, 2, • • • do 3: sample θ ∼ Πn 4: I (1) ← arg max i∈A θi 5: sample b ∼ Bern(β) 6: if b = 1 then 7:
evaluate arm I (1) 8: else 9:

repeat sample θ ∼ Πn 10:

I (2) ← arg max i∈A θ i TTTS 11: until I (2) = I (1) 12: I (2) ← arg min i =I (1) Wn(I (1) , i), cf. (1) T3C 13:
evaluate arm I (2) 14:

end if 15:

update mean and variance 16:

t = t + 1 17: end for
Optimal action probability The optimal action probability a n,i is defined as the posterior probability that arm i is optimal. Formally, letting Θ i be the subset of Θ such that arm i is the optimal arm,

Θ i θ ∈ Θ θ i > max j =i θ j ,
then we define

a n,i Π n (Θ i ) = Θi π n (θ)dθ.
With this notation, one can show that under TTTS,

Π n I (2) n = j|I (1) n = i = a n,j k =i a n,k . (2)
Furthermore, when i coincides with the empirical best mean (and this will often be the case for I

(1) n when n is large due to posterior convergence) one can write

a n,j Π n (θ j ≥ θ i ) exp (-W n (i, j)) ,
where the last step is justified in Lemma 2 in the Gaussian case (and Lemma 26 in Appendix H.3 in the Bernoulli case). Hence, T3C replaces sampling from the distribution (2) by an approximation of its mode which is easy to compute. Note that directly computing the mode would require to compute a n,j , which is much more costly than the computation of W n (i, j)3 .

Stopping and recommendation rules

In order to use TTTS or T3C as sampling rule for fixedconfidence BAI, we need to additionally define stopping and recommendation rules. While Qin et al. (2017) suggest to couple TTEI with the "frequentist" Chernoff stopping rule (Garivier and Kaufmann, 2016), we propose in this section natural Bayesian stopping and recommendation rule. They both rely on the optimal action probabilities defined above.

Bayesian recommendation rule At time step n, a natural candidate for the best arm is the arm with largest optimal action probability, hence we define

J n arg max i∈A a n,i .
Bayesian stopping rule In view of the recommendation rule, it is natural to stop when the posterior probability that the recommended action is optimal is large, and exceeds some threshold c n,δ which gets close to 1. Hence our Bayesian stopping rule is

τ δ inf n ∈ N : max i∈A a n,i ≥ c n,δ . (3)
Links with frequentist counterparts Using the transportation cost W n (i, j) defined in (1), the Chernoff stopping rule of Garivier and Kaufmann (2016) can actually be rewritten as

τ Ch. δ inf n ∈ N : max i∈A min j∈A\{i} W n (i, j) > d n,δ . (4)
This stopping rule coupled with the recommendation rule J n = arg max i µ n,i .

As explained in that paper, W n (i, j) can be interpreted as a (log) Generalized Likelihood Ratio statistic for rejecting the hypothesis H 0 : (µ i < µ j ). Through our Bayesian lens, we rather have in mind the approximation Π n (θ j > θ i ) exp {-W n (i, j)}, valid when µ n,i > µ n,j , which permits to analyze the two stopping rules using similar tools, as will be seen in the proof of Theorem 2.

As shown later in Section 4, τ δ and τ Ch. δ prove to be fairly similar for some corresponding choices of the thresholds c n,δ and d n,δ . This endorses the use of the Chernoff stopping rule in practice, which does not require the (heavy) computation of optimal action probabilities. Still, our sample complexity analysis applies to the two stopping rules, and we believe that a frequentist sample complexity analysis of a fully Bayesian BAI strategy is a nice theoretical contribution.

Useful notation

We follow the notation of Russo (2016) and define the following measures of effort allocated to arm i up to time n,

ψ n,i P [I n = i|F n-1 ] and Ψ n,i n l=1 ψ l,i .
In particular, for TTTS we have

ψ n,i = βa n,i + (1 -β)a n,i j =i a n,j 1 -a n,j , while for T3C ψn,i = βan,i+(1-β) j =i
an,j 1{Wn(j, i) = min k =j Wn(j, k)} # arg min k =j Wn(j, k) .

Two Related Optimality Notions

In the fixed-confidence setting, we aim for building δcorrect strategies, i.e. strategies that identify the best arm with high confidence on any problem instance.

Definition 1. A strategy (I n , J n , τ ) is δ-correct if for all bandit models µ with a unique optimal arm, it holds that P µ [J τ = I ] ≤ δ.

Among δ-correct strategies, seek the one with the smallest sample complexity E [τ δ ]. So far, TTTS has not been analyzed in terms of sample complexity; Russo (2016) focusses on posterior consistency and optimal convergence rates. Interestingly, both the smallest possible sample complexity and the fastest rate of posterior convergence can be expressed in terms of the following quantities.

Definition 2. Let Σ K = {ω :

K k=1 ω k = 1} and define for all i = I C i (ω, ω ) min x∈I ωd(µ I ; x) + ω d(µ i ; x),
where d(µ, µ ) is the KL-divergence defined above and I = R in the Gaussian case and I = [0, 1] in the Bernoulli case. We define

Γ max ω∈Σ K min i =I C i (ω I , ω i ), Γ β max ω∈Σ K ω I =β min i =I C i (ω I , ω i ). (5)
The quantity C i (ω I , ω i ) can be interpreted as a "transportation cost"4 from the original bandit instance µ to an alternative instance in which the mean of arm i is larger than that of I , when the proportion of samples allocated to each arm is given by the vector ω ∈ Σ K . As shown by Russo (2016), the ω that maximizes (5) is unique, which allows us to define the β-optimal allocation ω β in the following proposition.

Proposition 1. There is a unique solution ω β to the optimization problem (5) satisfying ω β I = β, and for all i, j = I , C i (β,

ω β i ) = C j (β, ω β j ).
For models with more than two arms, there is no closed form expression for Γ β or Γ , even for Gaussian bandits with variance σ 2 for which we have

Γ β = max ω:ω I =β min i =I (µ I -µ i ) 2 2σ 2 (1/ω i + 1/β) .
Bayesian β-optimality Russo (2016) proves that any sampling rule allocating a fraction β to the optimal arm (Ψ n,I /n → β) satisfies 1 -a n,I ≥ e -n(Γ β +o( 1)) (a.s.) for large values of n. We define a Bayesian β-optimal sampling rule as a sampling rule matching this lower bound, i.e. satisfying Ψ n,I /n → β and 1 -a n,I ≤ e -n(Γ β +o(1)) .

Russo ( 2016) proves that TTTS with parameter β is Bayesian β-optimal. However, the result is valid only under strong regularity assumptions, excluding the two practically important cases of Gaussian and Bernoulli bandits. A fundamental ingredient of these proofs is to establish the convergence of the allocation of measurement effort to the β-optimal allocation: Ψ n,i /n → ω β i for all i, which is equivalent to T n,i /n → ω β i (cf. Lemma 4).

β-optimality in the fixed-confidence setting In the fixed confidence setting, the performance of an algorithm is evaluated in terms of sample complexity. A lower bound given by Garivier and Kaufmann (2016) states that any δ-correct strategy satisfies

E [τ δ ] ≥ (Γ ) -1 ln (1/(3δ)).
Observe that Γ = max β∈[0,1] Γ β . Using the same lower bound techniques, one can also prove that under any δ-correct strategy satisfying T n,I /n → β,

lim inf δ→0 E [τ δ ] ln(1/δ) ≥ 1 Γ β .
This motivates the relaxed optimality notion that we introduce in this paper: A BAI strategy is called asymptotically β-optimal if it satisfies

T n,I n → β and lim sup δ→0 E [τ δ ] ln(1/δ) ≤ 1 Γ β .
In the paper, we provide the first sample complexity analysis of a BAI algorithm based on TTTS (with the stopping and recommendation rules described in Section 2), establishing its asymptotic β-optimality.

As already observed by Qin et al. (2017), any sampling rule converging to the β-optimal allocation (i.e. satisfying T n,i /n → w β i for all i) can be shown to satisfy lim sup δ→0 τ δ / ln(1/δ) ≤ (Γ β ) -1 almost surely, when coupled with the Chernoff stopping rule. The fixed confidence optimality that we define above is stronger as it provides guarantees on E [τ δ ].

Fixed-Confidence Analysis

In this section, we consider Gaussian bandits and the Bayesian rules using an improper prior on the means. We state our main result below, showing that TTTS and T3C are asymptotically β-optimal in the fixed confidence setting, when coupled with appropriate stopping and recommendation rules.

Theorem 1. With C g G the function defined by Kaufmann and Koolen (2018), which satisfies C g G (x)

x + ln(x), we introduce the threshold

d n,δ = 4 ln(4 + ln(n)) + 2C g G ln((K -1)/δ) 2 . ( 6
)
The TTTS and T3C sampling rules coupled with either

• the Bayesian stopping rule (3) with threshold

c n,δ = 1 - 1 √ 2π e - √ d n,δ + 1 √ 2 2
and the recommendation rule J t = arg max i a n,i • or the Chernoff stopping rule (4) with threshold d n,δ and recommendation rule J t = arg max i µ n,i , form a δ-correct BAI strategy. Moreover, if all the arms means are distinct, it satisfies

lim sup δ→0 E [τ δ ] log(1/δ) ≤ 1 Γ β .
We now give the proof of Theorem 1, which is divided into three parts. The first step of the analysis is to prove the δ-correctness of the studied BAI strategies.

Theorem 2. Regardless of the sampling rule, the stopping rule (3) with the threshold c n,δ and the Chernoff stopping rule with threshold d n,δ defined in Theorem 1 satisfy

P [τ δ < ∞ ∧ J τ δ = I ] ≤ δ.
To prove that TTTS and T3C allow to reach a β-optimal sample complexity, one needs to quantify how fast the measurement effort for each arm is concentrating to its corresponding optimal weight. For this purpose, we introduce the random variable

T ε β inf N ∈ N : max i∈A |T n,i /n -ω β i | ≤ ε, ∀n ≥ N .
The second step of our analysis is a sufficient condition for β-optimality, stated in Lemma 1. Its proof is given in Appendix E. The same result was proven for the Chernoff stopping rule by Qin et al. ( 2017).

Lemma 1. Let δ, β ∈ (0, 1). For any sampling rule which satisfies E T ε β < ∞ for all ε > 0, we have

lim sup δ→0 E [τ δ ] log(1/δ) ≤ 1 Γ β ,
if the sampling rule is coupled with stopping rule (3),

Finally, it remains to show that TTTS and T3C meet the sufficient condition, and therefore the last step, which is the core component and the most technical part our analysis, consists of showing the following.

Theorem 3. Under TTTS or T3C, E T ε β < +∞.

In the rest of this section, we prove Theorem 2 and sketch the proof of Theorem 3. But we first highlight some important ingredients for these proofs.

Core ingredients

Our analysis hinges on properties of the Gaussian posteriors, in particular on the following tails bounds, which follow from Lemma 1 of Qin et al. (2017).

Lemma 2. For any i, j ∈ A, if µ n,i ≤ µ n,j Πn [θi ≥ θj] ≤ 1 2 exp - (µn,j -µn,i) 2 2σ 2 n,i,j , (7)
Πn [θi ≥ θj] ≥ 1 √ 2π exp - (µn,j -µn,i + σn,i,j) 2 2σ 2 n,i,j , (8)
where σ 2 n,i,j

σ 2 /T n,i + σ 2 /T n,j .
This lemma is crucial to control a n,i and ψ n,i , the optimal action and selection probabilities.

Proof of Theorem 2

We upper bound the desired probability as follows

P [τ δ < ∞ ∧ Jτ δ = I ] ≤ i =I P [∃n ∈ N : αi,n > c n,δ ] ≤ i =I P [∃n ∈ N : Πn(θi ≥ θI ) > c n,δ , µn,I ≤ µn,i] ≤ i =I P [∃n ∈ N : 1 -c n,δ > Πn(θI > θi), µn,I ≤ µn,i] .
The second step uses the fact that as c n,δ ≥ 1/2, a necessary condition for

Π n (θ i ≥ θ I ) ≥ c n,δ is that µ n,i ≥ µ n,I . Now using the lower bound (8), if µ n,I ≤ µ n,i , the inequality 1 -c n,δ > Π n (θ I > θ i ) implies (µ n,i -µ n,I ) 2 2σ 2 n,i,I ≥ ln 1 √ 2π(1 -c n,δ ) - 1 √ 2 2 = d n,δ ,
where the equality follows from the expression of c n,δ as function of d n,δ . Hence to conclude the proof it remains to check that

P ∃n ∈ N : µn,i ≥ µ n,I , (µn,i -µ n,I ) 2 2σ 2 n,i,I ≥ d n,δ ≤ δ K -1 . ( 9
)
To prove this, we observe that for µ n,i ≥ µ by δ/(K -1) for the choice of threshold given in (6), which completes the proof that the stopping rule ( 3) is δ-correct. The fact that the Chernoff stopping rule with the above threshold d n,δ given above is δ-correct straightforwardly follows from (9).

Sketch of the proof of Theorem 3

We present a unified proof sketch of Theorem 3 for TTTS and T3C. While the two analyses follow the same steps, some of the lemmas given below have different proofs for TTTS and T3C, which can be found in Appendix C and Appendix D respectively.

We first state two important concentration results, that hold under any sampling rule.

i ∈ A, ∀n ∈ N, |T n,i -Ψ n,i | ≤ W 2 (n + 1) log(e 2 + n) a.s.,
and E e λW2 < ∞ for any λ > 0.

Lemma 3 controls the concentration of the posterior means towards the true means and Lemma 4 establishes that T n,i and Ψ n,i are close. Both results rely on uniform deviation inequalities for martingales.

Our analysis uses the same principle as that of TTEI:

We establish that T ε β is upper bounded by some random variable N which is a polynomial of the random variables W 1 and W 2 introduced in the above lemmas, denoted by Poly

(W 1 , W 2 ) O(W c1 1 W c2 2 )
, where c 1 and c 2 are two constants (that may depend on arms' means and the constant hidden in the O). As all exponential moments of W 1 and W 2 are finite, N has a finite expectation as well, which concludes the proof.

The first step to exhibit such an upper bound N is to establish that every arm is pulled sufficiently often. Lemma 5. Under TTTS or T3C, there exists

N 1 = Poly(W 1 , W 2 ) s.t. ∀n ≥ N 1 , for all i, T n,i ≥ n/K, almost surely.
Due to the randomized nature of TTTS and T3C, the proof of Lemma 5 is significantly more involved than for a deterministic rule like TTEI. Intuitively, the posterior of each arm would be well concentrated once the arm is sufficiently pulled. If the optimal arm is undersampled, then it would be chosen as the first candidate with large probability. If a sub-optimal arm is undersampled, then its posterior distribution would possess a relatively wide tail that overlaps with or cover the somehow narrow tails of other overly-sampled arms. The probability of that sub-optimal arm being chosen as the challenger would be large enough then.

Combining Lemma 5 with Lemma 3 straightforwardly leads to the following result. Lemma 6. Under TTTS or T3C, fix a constant ε > 0, there exists

N 2 = Poly(1/ε, W 1 , W 2 ) s.t. ∀n ≥ N 2 , ∀i ∈ A, |µ n,i -µ i | ≤ ε.
We can then deduce a very nice property about the optimal action probability for sub-optimal arms from the previous two lemmas. Indeed, we can show that

∀i = I , a n,i ≤ exp - ∆ 2 min 16σ 2 n K
for n larger than some Poly(W 1 , W 2 ). In the previous inequality, ∆ min is the smallest mean difference among all the arms.

Plugging this in the expression of ψ n,i , one can easily quantify how fast ψ n,I converges to β, which eventually yields the following result. Lemma 7. Under TTTS or T3C, fix ε > 0, then there exists

N 3 = Poly(1/ε, W 1 , W 2 ) s.t. ∀n ≥ N 3 , T n,I n -β ≤ ε.
The last, more involved, step is to establish that the fraction of measurement allocation to every suboptimal arm i is indeed similarly close to its optimal proportion ω β i . Lemma 8. Under TTTS or T3C, fix a constant ε > 0, there exists

N 4 = Poly(1/ε, W 1 , W 2 ) s.t. ∀n ≥ N 4 , ∀i = I , T n,i n -ω β i ≤ ε.
The major step in the proof of Lemma 8 for each sampling rule, is to establish that if some arm is oversampled, then its probability to be selected is exponentially small. Formally, we show that for n larger than some Poly

(1/ε, W 1 , W 2 ), Ψ n,i n ≥ ω β i + ξ ⇒ ψ n,i ≤ exp {-f (n, ξ)} ,
for some function f (n, ξ) to be specified for each sampling rule, satisfying

f (n) ≥ C ξ √ n (a.s.
). This result leads to the concentration of Ψ n,i /n, thus can be easily converted to the concentration of T n,i /n by Lemma 4. Finally, Lemma 7 and Lemma 8 show that

T ε β is upper bounded by N max(N 3 , N 4 ), which yields E[T ε β ] ≤ max(E [N 3 ] , E [N 4 ]) < ∞.

Optimal Posterior Convergence

Recall that a n,I denotes the posterior mass assigned to the event that action I (i.e. the true optimal arm) is optimal at time n. As the number of observations tends to infinity, we desire that the posterior distribution converges to the truth. In this section we show equivalently that the posterior mass on the complementory event, 1 -a n,I , the event that arm I is not optimal, converges to zero at an exponential rate, and that it does so at optimal rate Γ β . Russo (2016) proves a similar theorem under three confining boundedness assumptions (cf. Russo 2016, Asssumption 1) on the parameter space, the prior density and the (first derivative of the) log-normalizer of the exponential family. Hence, the theorems in Russo (2016) do not apply to the two bandit models most used in practise, which we consider in this paper: the Gaussian and Bernoulli model.

In the first case, the parameter space is unbounded, in the latter model, the derivative of the log-normalizer (which is e η /(1 + e η )) is unbounded. Here we provide two theorems, proving that under TTTS, the optimal, exponential posterior convergence rates are obtained for the Gaussian model with uninformative (improper) Gaussian priors (proof given in Appendix G), and the Bernoulli model with Beta(1, 1) priors (proof given in Appendix H).

Theorem 4. Under TTTS, for Gaussian bandits with improper Gaussian priors, it holds almost surely that

lim n→∞ - 1 n log(1 -a n,I ) = Γ β .
Theorem 5. Under TTTS, for Bernoulli bandits and uniform priors, it holds almost surely that

lim n→∞ - 1 n log(1 -a n,I ) = Γ β .

Sampling rule

T3C TTTS TTEI BC D-Tracking Uniform UGapE Execution time (s) 1.6 × 10 -5 2.3 × 10 -4 1 × 10 -5 1.4 × 10 -5 1.3 × 10 -3 6 × 10 -6 5 × 10 -6
Table 1: average execution time in seconds for different sampling rules.

Numerical Illustrations

This section is aimed at illustrating our theoretical results and supporting the practical use of Bayesian sampling rules for fixed-confidence BAI.

We experiment with three different Bayesian sampling rules: T3C, TTTS and TTEI, and we also include the Direct Tracking (D-Tracking) rule of Garivier and Kaufmann (2016) (which is adaptive to β), the UGapE (Gabillon et al., 2012) algorithm, and a uniform baseline. In order to make a fair comparison, we use the Chernoff stopping rule (4) and associated recommendation rule for all of the sampling rules, including the uniform one, except for UGapE which has its own stopping rule. Furthermore, we include a toptwo variant of the Best Challenger (BC) heuristic (see, e.g., Ménard, 2019).

BC selects the empirical best arm I n with probability β and the maximizer of W n ( I n , j) with probability 1β, but also performs forced exploration (selecting any arm sampled less than √ n times at round n). T3C can thus be viewed as a variant of BC in which no forced exploration is needed to converge to ω β , due to the noise added by replacing I n with I

(1) n . We consider two simple instances with arms means given by µ 1 = [0.5 0.9 0.4 0.45 0.44999], and µ 2 = [1 0.8 0.75 0.7] respectively. We run simulations for both Gaussian (with σ = 1) and Bernoulli bandits with a risk parameter δ = 0.01. Figure 1 reports the empirical distribution of τ δ under the different sampling rules, estimated over 1000 independent runs. These figures provide several insights: (1) T3C is competitive with, and sometimes slightly better than TTTS and TTEI in terms of sample complexity. (2) The UGapE algorithm has a larger sample complexity than the uniform sampling rule, which highlights the importance of the stopping rule in the fixed-confidence setting. [START_REF]I /n → β[END_REF] The fact that D-Tracking performs best is not surprising, since it converges to ω β and achieves minimal sample complexity. However, in terms of computation time, D-Tracking is much worse than other sampling rules, as can be seen in Table 1, which reports the average execution time of one step of each sampling rule for µ 1 in the Gaussian case. ( 4) TTTS also suffers from computational costs, whose origins are explained in Section 2, unlike T3C and TTEI. Although TTEI is already computationally more attractive than TTTS, its practical benefits are limited to the Gaussian case, since the Expected Improvement (EI) does not have a closed form beyond this case and its approximation would be costly. In contrast, T3C can be applied for other distributions.

Conclusion

We have advocated the use of a Bayesian sampling rule for BAI. In particular, we proved that TTTS and a computationally advantageous approach T3C, are both β-optimal in the fixed-confidence setting, for Gaussian bandits. We further extended the Bayesian optimality properties established by Russo ( 2016) to more practical choices of models and prior distributions.

In order to be optimal, the sampling rules studied in this paper would need to use the oracle tuning β = arg max β∈[0,1] Γ β , which is not feasible. In future work, we will investigate an efficient online tuning of β to circumvent this issue. We also plan to investigate the extension of T3C to more general pure exploration problems, as an alternative to approaches recently proposed by Ménard ( 2019 Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285.

• Recall that d(µ 1 ; µ 2 ) denotes the KL-divergence between two distributions parametrized by their means µ 1 and µ 2 . For Gaussian distributions, we know that

d(µ 1 ; µ 2 ) = (µ 1 -µ 2 ) 2 2σ 2 .
When it comes to Bernoulli distributions, we denote this with kl, i.e.

kl(µ 1 ; µ 2 ) = µ 1 ln µ 1 µ 2 + (1 -µ 1 ) ln 1 -µ 1 1 -µ 2 . • Beta(•, •) denotes a Beta distribution. • Bern(•) denotes a Bernoulli distribution. • B(•) denotes a Binomial distribution. • N (•, •) denotes a normal distribution. • Y n,i is the reward of arm i at time n. • Y n,
In is the observation of the sampling rule at time n.

• F n σ(I 1 , Y 1,I1 , I 2 , Y 2,I2 , • • • , I n , Y n,In
) is the filtration generated by the first n observations.

• ψ n,i P [I n = i|F n-1 ]. • Ψ n,i n l=1 ψ l,i .
• For the sake of simplicity, we further define ψ n,i Ψn,i n .

• T n,i is the number of pulls of arm i before round n.

• T n denotes the vector of the number of arm selections.

• I n arg max i∈A µ n,i denotes the empirical best arm at time n.

• For any a, b > 0, define a function C a,b s.t. ∀y, C a,b (y) (a + b -1)kl( a -1 a + b -1 ; y).
• We define the minimum and the maximum means gap as

∆ min min i =j |µ i -µ j |; ∆ max max i =j |µ i -µ j |.
• We introduce two indices

J (1) n arg max j a n,j , J (2)
n arg max j =J

(1) n a n,j .

Note that J

(1)

n coincides with the Bayesian recommendation index J n . • Two real-valued sequences (a n ) and (b n ) are are said to be logarithmically equivalent if

lim n→∞ 1 n log a n b n = 0,
and we denote this by a n . = b n .

Preprint

C Fixed-Confidence Analysis for TTTS

This section is entirely dedicated to TTTS.

C.1 Sufficient exploration of all arms, proof of Lemma 5 under TTTS

To prove this lemma, we introduce the two following sets of indices for a given L > 0: ∀n ∈ N we define

U L n {i : T n,i < √ L}, V L n {i : T n,i < L 3/4 }.
It is seemingly non trivial to manipulate directly TTTS's candidate arms, we thus start by connecting TTTS with TTPS (top two probability sampling). TTPS is another sampling rule presented by Russo (2016) for which the two candidate samples are defined as in Appendix B, we recall them in the following.

J (1) n arg max j a n,j , J (2) n arg max j =J (1) n a n,j .
Lemma 5 is proved via the following sequence of lemmas.

Lemma 9. There exists

L 1 = Poly(W 1 ) s.t. if L > L 1 , for all n, U L n = ∅ implies J (1) n ∈ V L n or J (2) n ∈ V L n .
Proof. If J

(1)

n ∈ V L n , then the proof is finished. Now we assume that J

(1)

n ∈ V L n , and we prove that J

(2)

n ∈ V L n .
Step 1 According to Lemma 3, there exists

L 2 = Poly(W 1 ) s.t. ∀L > L 2 , ∀i ∈ U L n , |µ n,i -µ i | ≤ σW 1 log(e + T n,i ) 1 + T n,i ≤ σW 1 log(e + √ L) 1 + √ L ≤ σW 1 ∆ min 4σW 1 = ∆ min 4 .
The second inequality holds since x → log(e+x) 1+x is a decreasing function. The third inequality holds for a large L > L 2 with L 2 = . . ..

Step 2 We now assume that L > L 2 , and we define

J n arg max j∈U L n µ n,j = arg max j∈U L n µ j .
The last equality holds since ∀j ∈ U L n , |µ n,i -µ i | ≤ ∆ min /4. We show that there exists

L 3 = Poly(W 1 ) s.t. ∀L > L 3 , J n = J (1) n .
We proceed by contradiction, and suppose that J n = J

(1)

n , then µ n,J (1) n < µ n,J n , since J (1) n ∈ V L n ⊂ U L n .
However, we have

a n,J (1) n = Π n θ J (1) n > max j =J (1) n θ j ≤ Π n θ J (1) n > θ J n ≤ 1 2 exp - (µ n,J (1) n -µ n,J n ) 2 2σ 2 (1/T n,J (1) n + 1/T n,J n ) .
The last inequality uses the Gaussian tail inequality (7) of Lemma 2. On the other hand,

|µ n,J (1) n -µ n,J n | = |µ n,J (1) n -µ J (1) n + µ J (1) n -µ J n + µ J n -µ n,J n | ≥ |µ J (1) n -µ J n | -|µ n,J (1) n -µ J (1) n + µ J n -µ n,J n | ≥ ∆ min -( ∆ min 4 + ∆ min 4 ) = ∆ min 2 , and 1 T n,J (1) n + 1 T n,J n ≤ 2 √ L .
Thus, if we take

L 3 s.t. exp - √ L 3 ∆ 2 min 16σ 2 ≤ 1 2K ,
then for any L > L 3 , we have

a n,J (1) n ≤ 1 2K < 1 K ,
which contradicts the definition of J

(1)

n . We now assume that L > L 3 , thus J

(1)

n = J n .
Step 3 We finally show that for L large enough, J

n ∈ V L n . First note that ∀j ∈ V L n , we have a n,j ≤ Π n θ j ≥ θ J n ≤ exp - L 3/4 ∆ 2 min 16σ 2 . ( (2)
) 10
This last inequality can be proved using the same argument as Step 2. Now we define another index J n arg max j∈U L n µ n,j and the quantity c n max(µ n,J n , µ n,J n ). We can lower bound a n,J n as follows:

a n,J n ≥ Π n θ J n ≥ c n j =J n Π n [θ j ≤ c n ] = Π n θ J n ≥ c n j =J n ;j∈U L n Π n [θ j ≤ c n ] j∈U L n Π n [θ j ≤ c n ] ≥ Π n θ J n ≥ c n 1 2 K-1 .
Now there are two cases:

• If µ n,J n > µ n,J n
, then we have

Π n θ J n ≥ c n = Π n θ J n ≥ µ n,J n ≥ 1 2 . • If µ n,J n < µ n,J n
, then we can apply the Gaussian tail bound (8) of Lemma 2, and we obtain

Π n θ J n ≥ c n = Π n θ J n ≥ µ n,J n = Π n θ J n ≥ µ n,J n + (µ n,J n -µ n,J n ) ≥ 1 √ 2π exp    - 1 2 1 - T n,J n σ (µ n,J n -µ n,J n ) 2    = 1 √ 2π exp    - 1 2 1 + T n,J n σ (µ n,J n -µ n,J n ) 2    .
On the other hand, by Lemma 3, we know that

|µ n,J n -µ n,J n | = |µ n,J n -µ J n + µ J n -µ J n + µ J n -µ n,J n | ≤ |µ J n -µ J n | + σW 1 log(e + T n,J n ) 1 + T n,J n + σW 1 log(e + T n,J n ) 1 + T n,J n ≤ |µ J n -µ J n | + 2σW 1 log(e + T n,J n ) 1 + T n,J n ≤ ∆ max + 2σW 1 log(e + T n,J n ) 1 + T n,J n .
Therefore,

Π n θ J n ≥ c n ≥ 1 √ 2π exp    - 1 2 1 + T n,J n σ ∆ max + 2σW 1 log(e + T n,J n ) 1 + T n,J n 2    ≥ 1 √ 2π exp      - 1 2   1 + √ L σ   ∆ max + 2σW 1 log(e + √ L) 1 + √ L     2      ≥ 1 √ 2π exp - 1 2 1 + L 1/4 ∆ max σ + 2W 1 log(e + √ L) 2 .
Now we have

a n,J n ≥ max 1 2 K , 1 2 K-1 1 √ 2π exp - 1 2 1 + L 1/4 ∆ max σ + 2W 1 log(e + √ L) 2 ,
and we have ∀j ∈ V L n , a n,j ≤ exp -L 3/4 ∆ 2 min /(16σ 2 ) , thus there exists

L 4 = Poly(W 1 ) s.t. ∀L > L 4 , ∀j ∈ V L n , a n,j ≤ a n,J n 2 ,
and by consequence, J

(2)

n ∈ V L n .
Finally, taking L 1 = max(L 2 , L 3 , L 4 ), we have ∀L > L 1 , either J

(1)

n ∈ V L n or J (2) n ∈ V L n .
Next we show that there exists at least one arm in V L n for whom the probability of being pulled is large enough. More precisely, we prove the following lemma.

Lemma 10. There exists L 1 = Poly(W 1 ) s.t. for L > L 1 and for all n s.t. U L n = ∅, then there exists

J n ∈ V L n s.t. ψ n,Jn ≥ min(β, 1 -β) K 2 ψ min .
Proof. Using Lemma 9, we know that J

(1)

n or J (2) n ∈ V L n .
On the other hand, we know that

∀i ∈ A, ψ n,i = a n,i   β + (1 -β) j =i a n,j 1 -a n,j   .
Therefore we have

ψ n,J (1) n ≥ βa n,J (1) n ≥ β K ,
since i∈A a n,i = 1, and

ψ n,J (2) n ≥ (1 -β)a n,J (2) n a n,J (1) n 1 -a n,J (1) n = (1 -β)a n,J (1) n a n,J (2) n 1 -a n,J (1) n ≥ 1 -β K 2 , since a n,J (1) n ≥ 1/K and i =J (1) n a n,i /(1 -a n,J (1) n ) = 1, thus a n,J (2) n /(1 -a n,J (1) n ) ≥ 1/K.
The rest of this subsection is quite similar to that of Qin et al. (2017). Indeed, with the above lemma, we can show that the set of poorly explored arms U L n is empty when n is large enough. Lemma 11. Under TTTS, there exists

L 0 = Poly(W 1 , W 2 ) s.t. ∀L > L 0 , U L KL = ∅.
Proof. We proceed by contradiction, and we assume that U L KL is not empty. Then for any 1 ≤ ≤ KL , U L and V L are non empty as well.

There exists a deterministic L 5 s.t. ∀L > L 5 ,

L ≥ KL 3/4 .
Using the pigeonhole principle, there exists some i ∈ A s.t. T L ,i ≥ L 3/4 . Thus, we have

|V L L | ≤ K -1. Next, we prove |V L 2L | ≤ K -2. Otherwise, since U L is non-empty for any L + 1 ≤ ≤ 2L , thus by Lemma 10, there exists J ∈ V L s.t. ψ ,J ≥ ψ min . Therefore, i∈V L ψ ,i ≥ ψ min , and i∈V L L ψ ,i ≥ ψ min since V L ⊂ V L L . Hence, we have i∈V L L (Ψ 2L ,i -Ψ L ,i ) = 2L = L +1 i∈V L L ψ ,i ≥ ψ min L .
Then, using Lemma 4, there exists L 6 = Poly(W 2 ) s.t. ∀L > L 6 , we have

i∈V L L (T 2L ,i -T L ,i ) ≥ i∈V L L (Ψ 2L ,i -Ψ L ,i -2W 2 2L log(e 2 + 2L )) ≥ i∈V L L (Ψ 2L ,i -Ψ L ,i ) -2KW 2 2L log(e 2 + 2L ) ≥ ψ min L -2KW 2 C 2 L 3/4 ≥ KL 3/4 ,
where C 2 is some absolute constant. Thus, we have one arm in V L L that is pulled at least L 3/4 times between L + 1 and 2L , thus

|V L 2L | ≤ K -2.
By induction, for any 1 ≤ k ≤ K, we have |V L kL | ≤ K -k, and finally if we take

L 0 = max(L 1 , L 5 , L 6 ), then ∀L > L 0 , U L KL = ∅.
We can finally conclude the proof of Lemma 5 for TTTS.

Preprint

Proof of Lemma 5 Let N 1 = KL 0 where L 0 = Poly(W 1 , W 2 ) is chosen according to Lemma 11. For all n > N 1 , we let L = n/K, then by Lemma 11, we have

U L KL = U n/K n
is empty, which concludes the proof.

C.2 Concentration of the empirical means, proof of Lemma 6 under TTTS As a corollary of the previous section, we can show the concentration of µ n,i to µ i for TTTS5 .

By Lemma 3, we know that ∀i ∈ A and n ∈ N,

|µ n,i -µ i | ≤ σW 1 log(e + T n,i ) T n,i + 1 .
According to the previous section, there exists

N 1 = Poly(W 1 , W 2 ) s.t. ∀n ≥ N 1 and ∀i ∈ A, T n,i ≥ n/K. Therefore, |µ n,i -µ i | ≤ log(e + n/K) n/K + 1 , since x → log(e + x)/(x + 1) is a decreasing function. There exists N 2 = Poly(ε, W 1 ) s.t. ∀n ≥ N 2 , log(e + n/K) n/K + 1 ≤ 2(n/K) 1/4 n/K + 1 ≤ ε σW 1 . Therefore, ∀n ≥ N 2 max{N 1 , N 2 }, we have |µ n,i -µ i | ≤ σW 1 ε σW 1 .
C.3 Measurement effort concentration of the optimal arm, proof of Lemma 7 under TTTS

In this section we show that the empirical arm draws proportion of the true best arm for TTTS concentrates to β when the total number of arm draws is sufficiently large.

The proof is established upon the following lemmas. First, we prove that the empirical best arm coincides with the true best arm when the total number of arm draws goes sufficiently large.

Lemma 12. Under TTTS, there exists M 1 = Poly(W 1 , W 2 ) s.t. ∀n > M 1 , we have

I n = I = J (1)
n and ∀i = I ,

a n,i ≤ exp - ∆ 2 min 16σ 2 n K .
Proof. Using Lemma 6 with ε = ∆ min /4, there exists

N 1 = Poly(4/∆ min , W 1 , W 2 ) s.t. ∀n > N 1 , ∀i ∈ A, |µ n,i -µ i | ≤ ∆ min 4 ,
which implies that starting from a known moment, µ n,I > µ n,i for all i = I , hence I n = I . Thus, ∀i = I ,

a n,i = Π n θ i > max j =i θ j ≤ Π n [θ i > θ I ] ≤ 1 2 exp - (µ n,i -µ n,I ) 2 2σ 2 (1/T n,i + 1/T n,I )
.

Preprint

The last inequality uses the Gaussian tail inequality of (7) Lemma 2. Furthermore,

(µ n,i -µ n,I ) 2 = (|µ n,i -µ n,I |) 2 = (|µ n,i -µ i + µ i -µ I + µ I -µ n,I |) 2 ≥ (|µ i -µ I | -|µ n,i -µ i + µ I -µ n,I |) 2 ≥ ∆ min - ∆ min 4 + ∆ min 4 2 = ∆ 2 min 4 ,
and according to Lemma 5, we know that there exists

M 2 = Poly(W 1 , W 2 ) s.t. ∀n > M 2 , 1 T n,i + 1 T n,I ≤ 2 n/K . Thus, ∀n > max{N 1 , M 2 }, we have ∀i = I , a n,i ≤ exp - ∆ 2 min 16σ 2 n K .
Then, we have

a n,I = 1 - i =I a n,i ≥ 1 -(K -1) exp - ∆ 2 min 16σ 2 n K .
There exists M 2 s.t. ∀n > M 2 , a n,I > 1/2, and by consequence I = J

(1)

n . Finally taking M 1 max{N 1 , M 2 , M 2 } concludes the proof.

Before we prove Lemma 7, we first show that Ψ n,I /n concentrates to β.

Lemma 13. Under TTTS, fix a constant ε > 0, there exists M 3 = Poly(ε, W 1 , W 2 ) s.t. ∀n > M 3 , we have

Ψ n,I n -β ≤ ε.
Proof. By Lemma 12, we know that there exists

M 1 = Poly(W 1 , W 2 ) s.t. ∀n > M 1 , we have I n = I = J (1)
n and ∀i = I ,

a n,i ≤ exp - ∆ 2 min 16σ 2 n K .
Note also that ∀n ∈ N, we have

ψ n,I = a n,I   β + (1 -β) j =I a n,j 1 -a n,j   .
We proceed the proof with the following two steps.

Preprint

Step 1 We first lower bound Ψ n,I for a given ε. Take M 4 > M 1 that we decide later, we have ∀n > M 4 ,

Ψ n,I n = 1 n n l=1 ψ l,I = 1 n M4 l=I ψ l,I + 1 n n l=M4+1 ψ l,I ≥ 1 n n l=M4+1 ψ l,I ≥ 1 n n l=M4+1 a l,I β = β n n l=M4+1   1 - j =I a l,j   ≥ β n n l=M4+1 1 -(K -1) exp - ∆ 2 min 16σ 2 l K = β - M 4 n β - β n n l=M4+1 (K -1) exp - ∆ 2 min 16σ 2 l K ≥ β - M 4 n β - (n -M 4 ) n β(K -1) exp - ∆ 2 min 16σ 2 M 4 K ≥ β - M 4 n β -β(K -1) exp - ∆ 2 min 16σ 2 M 4 K .
For a given constant ε > 0, there exists M 5 s.t. ∀n > M 5 ,

β(K -1) exp - ∆ 2 min 16σ 2 n K < ε 2 .
Furthermore, there exists M 6 = Poly(ε/2, M 5 ) s.t. ∀n > M 6 ,

M 5 n β < ε 2 .
Therefore, if we take M 4 max{M 1 , M 5 , M 6 }, we have ∀n > M 4 ,

Ψ n,I n ≥ β -ε.
Step 2 On the other hand, we can also upper bound Ψ n,I . We have ∀n > M 3 ,

Ψ n,I n = 1 n n l=1 ψ l,I = 1 n n l=1 a l,I   β + (1 -β) j =I a l,j 1 -a l,j   ≤ 1 n n l=1 a l,I β + 1 n n l=1 a l,I (1 -β) j =I a l,j 1 -a l,j ≤ β + 1 n n l=1 (1 -β) j =I a l,j 1 -a l,j ≤ β + 1 n n l=1 (1 -β) j =I exp - ∆ 2 min 16σ 2 l K 1 -exp - ∆ 2 min 16σ 2 l K
.

Since, for a given ε > 0, there exists

M 8 s.t. ∀n > M 8 , exp - ∆ 2 min 16σ 2 n K < 1 2 ,
and there exists M 9 s.t. ∀n > M 9 ,

(1 -β)(K -1) exp - ∆ 2 min 16σ 2 n K < ε 4 .
Thus, ∀n > M 10 max{M 8 , M 9 },

Ψ n,I n ≤ β + 1 -β n     M10 l=1 j =I exp - ∆ 2 min 16σ 2 l K 1 -exp - ∆ 2 min 16σ 2 l K + n l=M10+1 j =I exp - ∆ 2 min 16σ 2 l K 1 -exp - ∆ 2 min 16σ 2 l K     ≤ β + 1 -β n M10 l=1 j =I exp - ∆ 2 min 16σ 2 l K 1 -exp - ∆ 2 min 16σ 2 l K + 2(1 -β)(K -1) exp - ∆ 2 min 16σ 2 M 10 K ≤ β + 1 -β n M10 l=1 j =I exp - ∆ 2 min 16σ 2 l K 1 -exp - ∆ 2 min 16σ 2 l K + ε 2 .
There exists

M 11 = Poly(ε/2, M 10 ) s.t. ∀n > M 11 , 1 -β n M10 l=1 j =I exp - ∆ 2 min 16σ 2 l K 1 -exp - ∆ 2 min 16σ 2 l K < ε 2 .
Therefore, ∀n > M 7 max{M 3 , M 11 }, we have

Ψ n,I n ≤ β + ε.
Conclusion Finally, combining the two steps and define M 3 max{M 4 , M 7 }, we have ∀n > M 3 ,

Ψ n,I n -β ≤ ε.
With the help of the previous lemma and Lemma 4, we can finally prove Lemma 7.

Proof of Lemma 7 Fix an ε > 0. Using Lemma 4, we have ∀n ∈ N,

T n,I n - Ψ n,I n ≤ W 2 (n + 1) log(e 2 + n) n .
Thus there exists

M 12 s.t. ∀n > M 12 , T n,I n - Ψ n,I n ≤ ε 2 .
And using Lemma 13, there exists

M 3 = Poly(ε/2, W 1 , W 2 ) s.t. ∀n > M 3 , Ψ n,I n -β ≤ ε 2 .
Again, according to Lemma 10, there exists M 3 s.t. ∀n > M 3 ,

Ψ n,I n ≤ β + ε 2 .
Thus, if we take N 3 max{M 3 , M 12 }, then ∀n > N 3 , we have

T n,I n -β ≤ ε.

C.4 Measurement effort concentration of other arms, proof of Lemma 8 under TTTS

In this section, we show that, for TTTS, the empirical measurement effort concentration also holds for other arms than the true best arm. We first show that if some arm is overly sampled at time n, then its probability of being picked is reduced exponentially.

Lemma 14. Under TTTS, for every ξ ∈ (0, 1), there exists S 1 = Poly(1/ξ, W 1 , W 2 ) such that for all n > S 1 , for all i = I ,

Ψ n,i n ≥ ω β i + ξ ⇒ ψ n,i ≤ exp {-ε 0 (ξ)n} ,
where ε 0 is defined in (11) below.

Proof. First, by Lemma 12, there exists M 1 = Poly(W 1 , W 2 ) s.t. ∀n > M 1 ,

I = I n = J (1) n .
Then, following the similar argument as in Lemma 25, one can show that for all i = I and for all n > M 1 ,

ψ n,i = a n,i   β + (1 -β) j =i a n,j 1 -a n,j   ≤ a n,i β + a n,i (1 -β) j =i a n,j 1 -a n,J (1) n = a n,i β + a n,i (1 -β) j =i a n,j 1 -a n,I ≤ a n,i β + a n,i (1 -β) 1 1 -a n,I ≤ a n,i 1 -a n,I ≤ Π n [θ i ≥ θ I ] Π n [∪ j =I θ j ≥ θ I ] ≤ Π n [θ i ≥ θ I ] max j =I Π n [θ j ≥ θ I ]
.

Using the upper and lower Gaussian tail bounds from Lemma 2, we have

ψ n,i ≤ exp - (µ n,I -µ n,i ) 2 2σ 2 (1/T n,I + 1/T n,i ) exp    -min j =I 1 2 (µ n,I -µ n,j ) σ (1/T n,I + 1/T n,j ) -1 2    = exp -n (µ n,I -µ n,i ) 2 2σ 2 (n/T n,I + n/T n,i ) exp    -n min j =I (µ n,I -µ n,j ) 2σ 2 (n/T n,I + n/T n,j ) - 1 √ 2n 2    ,
where we assume that n > S 2 = Poly(W 1 , W 2 ) for which

(µ n,I -µ n,i ) 2 σ 2 (1/T n,I + 1/T n,i ) ≥ 1
according to Lemma 5. From there we take a supremum over the possible allocations to lower bound the denominator and write

ψ n,i ≤ exp -n (µ n,I -µ n,i ) 2 2σ 2 (n/T n,I + n/T n,i ) exp    -n sup ω:ω I =T n,I /n min j =I (µ n,I -µ n,i ) 2σ 2 (1/ω I + 1/ω j ) - 1 √ 2n 2    = exp -n (µ n,I -µ n,i ) 2 2σ 2 (n/T n,I + n/T n,i ) exp -n Γ T n,I /n (µ n ) - 1 √ 2n 2 ,
where µ n (µ n,1 , • • • , µ n,K ), and (β, µ) → Γ β (µ) represents a function that maps β and µ to the parameterized optimal error decay that any allocation rule can reach given parameter β and a set of arms with means µ. Note that this function is continuous with respect to β and µ respectively. Now, assuming Ψ n,i /n ≥ ω β i +ξ yields that there exists S 2 Poly(2/ξ, W 2 ) s.t. for all n > S 2 , T n,i /n ≥ ω β i +ξ/2, and by consequence,

ψ n,i ≤ exp              -n   (µ n,I -µ n,i ) 2 2σ 2 n/T n,I + 1/(ω β i + ξ/2) -Γ T n,I /n (µ n ) - 1 2n + 2Γ T n,I /n (µ n ) n   εn(ξ)             
.

Using Lemma 7, we know that for any ε, there exists

S 3 = Poly(1/ε, W 1 , W 2 ) s.t. ∀n > S 3 , |T n,I /n -β| ≤ ε, and ∀j ∈ A, |µ n,j -µ j | ≤ ε. Furthermore, (β, µ) → Γ β (µ)
is continuous with respect to β and µ, thus for a given ε 0 , there exists S 3 = Poly(1/ε 0 , W 1 , W 2 ) s.t. ∀n > S 3 , we have

ε n (ξ) -   (µ I -µ i ) 2 2σ 2 1/β + 1/(ω β i + ξ/2) -Γ β   ≤ ε 0 .
Finally, define S 1 max{S 2 , S 2 , S 3 }, we have ∀n > S 1 ,

ψ n,i ≤ exp {-ε 0 (ξ)n} ,
where

ε 0 (ξ) = (µ I -µ i ) 2 2σ 2 1/β + 1/(ω β i + ξ/2) -Γ β + ε 0 . (11)
Next, starting from some known moment, no arm is overly allocated. More precisely, we show the following lemma.

Lemma 15. Under TTTS, for every ξ, there exists

S 4 = Poly(1/ξ, W 1 , W 2 ) s.t. ∀n > S 4 , ∀i ∈ A, Ψ n,i n ≤ ω β i + ξ.
Proof. From Lemma 14, there exists S 1 = Poly(2/ξ, W 1 , W 2 ) such that for all n > S 1 and for all i = I ,

Ψ n,i n ≥ ω β i + ξ 2 ⇒ ψ n,i ≤ exp {-ε 0 (ξ/2)n} .
Thus, for all i = I ,

Ψ n,i n ≤ S 1 n + n =S 1 +1 ψ ,i 1 Ψ ,i n ≥ ω β i + ξ 2 n + n =S 1 +1 ψ ,i 1 Ψ ,i n ≤ ω β i + ξ 2 n ≤ S 1 n + n =1 exp {-ε 0 (ξ/2)n} n + n (ξ) =S 1 +1 ψ ,i 1 Ψ ,i n ≤ ω β i + ξ 2 n ,
where we let n (ξ) = max

≤ n : Ψ ,i /n ≤ ω β i + ξ/2 . Then Ψ n,i n ≤ S 1 n + n =1 exp {-ε 0 (ξ/2)n} n + Ψ n(ξ),i ≤ S 1 + (1 -exp(-ε 0 (ξ/2)) -1 n + ω β i + ξ 2
Then, there exists S 5 such that for all n ≥ S 5 ,

S 1 + (1 -exp(-ε 0 (ξ/2)) -1 n ≤ ξ 2 .
Therefore, for any n > S 4 max{S 1 , S 5 }, Ψ n,i ≤ ω β i + ξ holds for all i = I . For i = I , it is already proved for the optimal arm. We now prove Lemma 8 under TTTS.

Proof of Lemma 8 From Lemma 15, there exists

S 4 = Poly((K -1)/ξ, W 1 , W 2 ) such that for all n > S 4 , ∀i ∈ A, Ψ n,i n ≤ ω β i + ξ K -1 .
Using the fact that Ψ n,i /n and ω β i all sum to 1, we have ∀i ∈ A,

Ψ n,i n = 1 - j =i Ψ n,j n ≥ 1 - j =i ω β j + ξ K -1 = ω β i -ξ.

Preprint

Thus, for all n > S 4 , we have

∀i ∈ A, Ψ n,i n -ω β i ≤ ξ.
And finally we use the same reasoning as the proof of Lemma 7 to link T n,i and Ψ n,i . Fix an ε > 0. Using Lemma 4, we have ∀n ∈ N,

∀i ∈ A, T n,i n - Ψ n,i n ≤ W 2 (n + 1) log(e 2 + n) n .
Thus there exists S 5 s.t. ∀n > S 5 ,

T n,I n - Ψ n,I n ≤ ε 2 .
And using the above result, there exists

S 4 = Poly(2/ε, W 1 , W 2 ) s.t. ∀n > S 4 , Ψ n,i n -ω β i ≤ ε 2 .
Thus, if we take N 4 max{S 4 , S 5 }, then ∀n > N 4 , we have

∀i ∈ A, T n,i n -ω β i ≤ ε.

D Fixed-Confidence Analysis for T3C

This section is entirely dedicated to T3C. Note that the analysis to follow share the same proof line with that of TTTS, and some parts even completely coincide with those of TTTS. For the sake of simplicity and clearness, we shall only focus on the parts that differ and skip some redundant proofs.

D.1 Sufficient exploration of all arms, proof of Lemma 5 under T3C

To prove this lemma, we still need the two sets of indices for under-sampled arms like in Appendix C.1. We recall that for a given L > 0: ∀n ∈ N we define

U L n {i : T n,i < √ L}, V L n {i : T n,i < L 3/4 }.
For T3C however, we investigate the following two indices,

J (1) n arg max j a n,j , J (2) n arg min j =J (1) n W n (J (1) n , j).
Lemma 5 is proved via the following sequence of lemmas.

Lemma 16. There exists

L 1 = Poly(W 1 ) s.t. if L > L 1 , for all n, U L n = ∅ implies J (1) n ∈ V L n or J (2) n ∈ V L n .
Proof. If J

(1) n ∈ V L n , then the proof is finished. Now we assume that J

(1) n ∈ V L n ⊂ U L n , and we prove that J

(2)

n ∈ V L n .
Step 1 Following the same reasoning as Step 1 and Step 2 of the proof of Lemma 9, we know that there exists

L 2 = Poly(W 1 ) s.t. if L > L 2 , then J n arg max j∈U L n µ n,j = arg max j∈U L n µ j = J (1)
n .

Preprint

Step 2 Now assuming that L > L 2 , and we show that for L large enough, J

(2)

n ∈ V L n .
In the same way that we proved (10) one can show that for all ∀j ∈ V L n ,

W n (J (1) n , j) = (µ n,I -µ n,j ) 2 2σ 2 1 T n,I + 1 T n,j ≥ L 3/4 ∆ 2 min 16σ 2 .
Again, denote J n arg max j∈U L n µ n,j , we obtain

W n (J (1) n , J n ) =            0 if µ n,J n ≥ µ n,J (1) n , (µ n,J (1) n -µ n,J n ) 2 2σ 2 1 T n,J (1) n + 1 T n,J n else.
In the second case, as already shown in Step 3 of Lemma 9 we have that

|µ n,J n -µ n,J n | ≤ ∆ max + 2σW 1 log(e + T n,J n ) 1 + T n,J n ≤ ∆ max + 2σW 1 log(e + √ L) 1 + √ L , since J n ∈ U L n .
We also know that

2σ 2 1 T n,J (1) n + 1 T n,J n ≥ 2σ 2 T n,J n ≥ 2σ 2 √ L .
Therefore, we get

W n (J (1) n , J n ) ≤ √ L 2σ 2   ∆ max + 2σW 1 log(e + √ L) 1 + √ L   2 .
On the other hand, we know that for all j ∈ V L n ,

W n (J (1) n , j) ≥ L 3/4 ∆ 2 min 16σ 2 .
Thus, there exists

L 3 s.t. if L > L 3 , then ∀j ∈ V L n , W n (J (1) n , j) ≥ 2W n (J (1) n , J n ).

That means J

(2) n / ∈ V L n and by consequence, J

n ∈ V L n . (2)
Finally, taking

L 1 = max(L 2 , L 3 ), we have ∀L > L 1 , either J (1) n ∈ V L n or J (2) n ∈ V L n .
Next we show that there exists at least one arm in V L n for whom the probability of being pulled is large enough. More precisely, we prove the following lemma.

Lemma 17. There exists L 1 = Poly(W 1 ) s.t. for L > L 1 and for all n s.t. U L n = ∅, then there exists

J n ∈ V L n s.t. ψ n,Jn ≥ min(β, 1 -β) K 2 ψ min .
Proof. Using Lemma 16, we know that J

(1)

n or J (2) n ∈ V L n .
We also know that under T3C, for any arm i, ψ n,i can be written as

ψ n,i = βa n,i + (1 -β) j =i a n,j 1{W n (j, i) = min k =j W n (j, k)} arg min k =j W n (j, k) .
Then,

ψ n,i ≤ βa n,i + (1 -β) j =i a n,j 1{W n (j, i) = min k =j W n (j, k)} ≤ βa n,i + (1 -β)   j =i,I a n,j + a n,I 1{W n (I , i) = min k =I W n (I , k)}   ≤ j =I a n,j + 1{W n (I , i) = min k =I W n (I , k)}.
Next we show that the indicator function term in the previous inequality equals to 0.

Using Lemma 3 and Lemma 7 for T3C, there exists S 3 = Poly(1/ξ, W 1 , W 2 ) such that for any n > S 3 ,

T n,I n -β ≤ ξ 2 and ∀j ∈ A, |µ n,j -µ j | ≤ ξ 2 . Now if ∀j = I , i, we have T n,j /n > ω β j , then n -1 n = j∈A T n,j n = T n,I n + T n,i n + j =I ,i T n,j n > β -ε 2 + ω β i + ε + j =I ,i ω β j ≥ 1, is a contradiction.
Thus there exists at least one j 0 = I , i, such that T n,j0 /n ≤ ω β j . Assuming n > max(S 2 , S 3 ), we have

W n (I , i) -W n (I , j 0 ) = (µ n,I -µ n,i ) 2 2σ 2 1 T n,I + 1 T n,i - (µ n,I -µ n,j0 ) 2 2σ 2 1 T n,I + 1 T n,j0 ≥ (µ I -µ i -2ξ 2 ) 2 2σ 2 1 β -ξ 2 + 1 ω β i + ξ - (µ I -µ j0 + 2ξ 2 ) 2 2σ 2 1 β + ξ 2 + 1 ω β j0 W ξ i,j 0 .
According to Proposition 1, W ξ i,j0 converges to 0 when ξ goes to 0, more precisely we have

W ξ i,j0 = (µ I -µ i ) 2 2σ 2 β β + ω β i 2 ξ + O(ξ 2 ) ,
thus there exists a ε 0 such that for all ξ < ε 0 it holds for all i, j 0 = I , W ξ i,j0 > 0. It follows then

W n (I , i) -min k =I W n (I , k) ≥ W n (I , i) -W n (I , j 0 ) > 0,
and

1{W n (I , i) = min k =I W n (I , k)} = 0.
Knowing that Lemma 12 is also valid for T3C, thus there exists

M 1 = Poly(4/∆ min , W 1 , W 2 ) such that for all n > M 1 , ∀j = I , a n,j ≤ exp - ∆ 2 min 16σ 2 n K ,
which then concludes the proof by taking S 1 max(M 1 , S 2 , S 3 ).

The rest of this subsection almost coincides with that of TTTS. We first show that, starting from some known moment, no arm is overly allocated. More precisely, we show the following lemma. Lemma 20. Under T3C, for every ξ, there exists

S 4 = Poly(1/ξ, W 1 , W 2 ) s.t. ∀n > S 4 , ∀i ∈ A, Ψ n,i n ≤ ω β i + 2ξ.
Proof. See proof of Lemma 15 in Appendix C.4. Note that the previous step does not match exactly that of TTTS, so the proof would be slightly different. However, the difference is only a matter of constant, we thus still choose to skip this proof.

It remains to prove Lemma 8 for T3C, which stays the same as that of TTTS.

Proof of Lemma 8 for T3C See proof of Lemma 8 for TTTS in Appendix C.4.

E Proof of Lemma 1

Finally, it remains to prove Lemma 1 under the Gaussian case before we can conclude for Theorem 1 for TTTS or T3C. Lemma 1. Let δ, β ∈ (0, 1). For any sampling rule which satisfies E T ε β < ∞ for all ε > 0, we have

lim sup δ→0 E [τ δ ] log(1/δ) ≤ 1 Γ β ,
if the sampling rule is coupled with stopping rule (3),

For the clarity, we recall the definition of generalized likelihood ratio. For any pair of arms i, j, We first define a weighted average of their empirical means,

µ n,i,j T n,i T n,i + T n,j µ n,i + T n,j T n,i + T n,j µ n,j .
And if µ n,i ≥ µ n,j , then the generalized likelihood ratio Z n,i,j for Gaussian noise distributions has the following analytic expression, Z n,i,j T n,i d( µ n,i ; µ n,i,j ) + T n,j d( µ n,j ; µ n,i,j ).

We further define a statistic Z n as

Z n max i∈A min j∈A\{i} Z n,i,j .
The following lemma stated by Qin et al. ( 2017) is needed in our proof. Lemma 21. For any ζ > 0, there exists ε s.

t. ∀n ≥ T ε β , Z n ≥ (Γ β -ζ)n.
To prove Lemma 1, we need the Gaussian tail inequality (7) of Lemma 2.

Proof. We know that

1 -a n,I = i =I a n,i ≤ i =I Π n [θ i > θ I ] = i =I Π n [θ i -θ I > 0] ≤ (K -1) max i =I Π n [θ i -θ I > 0] . Preprint We can further rewrite Π n [θ i -θ I > 0] as Π n [θ i -θ I > µ n,i -µ n,I + µ n,I -µ n,i ] .
We choose ε sufficiently small such that the empirical best arm I n = I . Then, for all n ≥ T n β and for any i = I , µ n,I ≥ µ n,i . Thus, fix any ζ ∈ (0, Γ β /2) and apply inequality (7) of Lemma 2 with µ n,I and µ n,i , we have for any n ≥ T ε β ,

1 -a n,I ≤ (K -1) max i =I 1 2 exp - (µ n,I -µ n,i ) 2 2σ 2 n,i,I = (K -1) exp {-Z n } 2 ≤ (K -1) exp -(Γ β -ζ)n 2 .
The last inequality is deduced from Lemma 21. By consequence,

∀n ≥ T ε β , ln (1 -a n,I ) ≤ ln K -1 2 -(Γ β -ζ)n.
On the other hand, we have for any n,

1 -c n,δ = δ 2n(K -1) √ 2πe exp 2 ln 2n(K -1) δ .
Thus, there exists a deterministic time N s.t. ∀n ≥ N ,

ln (1 -c n,δ ) = ln δ (K -1) √ 8πe -ln n -2 ln 2n(K -1) δ ≥ ln δ 2(K -1) √ 2πe -ζn. Let C 3 (K -1) 2 √ 2πe, we have for any n ≥ N 0 T ε β + N , ln (1 -a n,I ) -ln (1 -c n,δ ) ≤ ln C 3 δ -(Γ β -2ζ)n, (12)
and it is clear that

E [N 0 ] < ∞.

Let us consider the following two cases:

Case 1 There exists n ∈ [1, N 0 ] s.t. a n,I ≥ c n,δ , then by definition,

τ δ ≤ n ≤ N 1 .
Case 2 For any n ∈ [1, N 0 ], we have a n,I < c n,δ , then τ δ ≥ N 0 + 1, thus by Equation 12,

0 ≤ ln (1 -a τ δ -1,I ) -ln (1 -c τ δ -1,δ ) ≤ ln C 3 δ -(Γ β -2ζ)(τ δ -1),
and we obtain

τ δ ≤ ln(C 3 /δ) Γ β -2ζ + 1.
Combining the two cases, and we have for any ζ ∈ (0, Γ β /2),

τ δ ≤ max N 0 , ln(C 3 /δ) Γ β -2ζ + 1 ≤ N 0 + 1 + ln(C 3 ) Γ β -2ζ + ln(1/δ) Γ β -2ζ . Since E [N 1 ] < ∞, therefore lim sup δ E [τ δ ] log(1/δ) ≤ 1 Γ β -2ζ , ∀ζ ∈ (0, Γ β /2),
which concludes the proof.

F Technical Lemmas

The whole fixed-confidence analysis for the two sampling rules are both substantially based on two lemmas: Lemma 5 of Qin et al. ( 2017) and Lemma 4. We prove Lemma 4 in this section.

Lemma 4. There exists a random variable W 2 , such that for all i ∈ A,

∀n ∈ N, |T n,i -Ψ n,i | ≤ W 2 (n + 1) log(e 2 + n) a.s.,
and E e λW2 < ∞ for any λ > 0.

Proof. The proof shares some similarities with that of Lemma 6 of Qin et al. (2017). For any arm i ∈ A, define ∀n ∈ N,

D n T n,i -Ψ n,i , d n 1{I n = i} -ψ n,i .
It is clear that

D n = n-1 l=1 d l and E [d n |F n-1 ] = 0. Indeed, E [d n |F n-1 ] = E [1{I n = i} -ψ n,i |F n-1 ] = P [I n = i|F n-1 ] -E [P [I n = i|F n-1 ] |F n-1 ] = P [I n = i|F n-1 ] -P [I n = i|F n-1 ] = 0.
The second last equality holds since

P [I n = i|F n-1 ] is F n-1 -measurable. Thus D n is a martingale, whose increment are 1 sub-Gaussian as d n ∈ [-1, 1] for all n.
Applying Corollary 8 of Abbasi-Yadkori et al. ( 2012) 6 , it holds that, with probability larger than 1 -δ, for all n,

|D n | ≤ 2 (1 + n) ln √ 1 + n δ
which yields the first statement of Lemma 4.

We now introduce the random variable

W 2 max n∈N max i∈A |T n,i -Ψ n,i | (n + 1) ln(e 2 + n) .
Applying the previous inequality with δ = e -x 2 /2 yields

P ∃n ∈ N : |D n | > (1 + n) (ln (1 + n) + x 2 ) ≤ e -x 2 /2 , P ∃n ∈ N : |D n | > (1 + n) ln (e 2 + n) x 2 ≤ e -x 2 /2 ,
6 but we could actually use several deviation inequalities that hold uniformly over time for martingales with sub-Gaussian increments where the last inequality uses that for all a, b ≥ 2, we have ab ≥ a + b.

Consequently ∀x ≥ 2, for all i ∈ A P max n∈N |T n,i -Ψ n,i | (n + 1) log (e 2 + n) ≥ x ≤ e -x 2 /2 .
Now taking a union bound over i ∈ A, we have ∀x ≥ 2,

P [W 2 ≥ x] ≤ P max i∈A max n∈N |T n,i -Ψ n,i | (n + 1) log √ e 2 + n ≥ x ≤ P i∈A max n∈N |T n,i -Ψ n,i | (n + 1) log √ e 2 + n ≥ x ≤ i∈A P max n∈N |T n,i -Ψ n,i | (n + 1) log √ e 2 + n ≥ x ≤ Ke -x 2 /2 .
The previous inequalities imply that ∀i ∈ A and ∀n ∈ N, we have |T

Due to the concentration result in Lemma 4 that we restate below (and proved in Appendix C), which will be useful at several places in the proof, observe that

lim n→∞ T n,i n a.s = ω β i ⇔ lim n→∞ Ψ n,i n a.s = ω β i ,
therefore it suffices to establish the convergence of ψ n,i = Ψ n,i /n to ω β i , which we do next. For that purpose, we need again the following maximality inequality lemma.

First we show that n∈N T n,j = ∞ for each arm j. Suppose otherwise. Let I again be the set of arms to which only finite measurement effort is allocated. Under TTTS, we have

ψ n,i = a n,i   β + (1 -β) j =i a n,j 1 -a n,j   ,
so ψ n,i ≥ βa n,i . Therefore, by Lemma 23, if i ∈ I, then lim inf a n,i > 0 implies that n ψ n,i = ∞. By Lemma 4, we then must have that lim n→∞ T n,i = ∞ as well: contradiction. Thus, lim n→∞ T n,i = ∞ for all i, and we conclude that a n,I → 1, by Lemma 23.

For TTTS with parameter β this implies that ψ n,I → β, and since we have a bound on |T n,i /n-ψ n,i | in Lemma 4, we have T n,I /n → β as well.

Step 2: Controlling the over-allocation of sub-optimal arms. The convergence of T n,I /n to β leads to following interesting consequence, expressed in Lemma 24: if an arm is sampled more often than its optimal proportion, the posterior probability of this arm to be optimal is reduced compared to that of other sub-optimal arms.

Lemma 24 (Over-allocation implies negligible probability).7 Fix any ξ > 0 and j = I . With probability 1, under any allocation rule, if T n,I /n → β, there exist ξ > 0 and a sequence ε n with ε n → 0 such that for any n ∈ N, n(ξ +εn) .

T n,j n ≥ ω β j + ξ ⇒ a n,j max i =I a n,i ≤ e -
Proof. We have

Π n (Θ ∪i =I ) = i =I a n,i = 1 -a n,I , therefore max i =I a n,i ≤ 1 -a

Preprint

We also have the following from the standard Gaussian tail inequality, for n ≥ τ after which µ n,I ≥ µ n,i , using that θ i -θ I ∼ N (µ n,i -µ n,I , σ 2 n,i + σ 2 n,I ) and σ 2 n,i + σ 2 n,I = σ 2 (1/T n,i + 1/T n,I ),

a n,i ≤ Π n (θ i ≥ θ I ) ≤ exp -(µ n,i -µ n,I ) 2 2σ 2 (1/T n,I + 1/T n,i ) = exp -n (µ n,i -µ n,1 ) 2 2σ 2 (n/T n,I + n/T n,i )
.

Thus, there exists a sequence ε n → 0, for which

a n,j max i =I a n,i ≤ exp -n (µ n,j -µ n,I ) 2 2σ 2 (n/T n,I + n/T n,j ) -ε n /2 exp -n Γ β + ε n /2 ) = exp -n (µ n,j -µ n,I ) 2 2σ 2 (n/T n,I + n/T n,j ) -Γ β -ε n .
Now we take a look at the two terms in the middle:

(µ n,j -µ n,I ) 2 2σ 2 (n/T n,I + n/T n,j ) -Γ β .
Note that the first term is increasing in T n,j /n. We have the definition from Qin et al. ( 2017), for any j = I ,

Γ β = (µ j -µ I ) 2 2σ 2 1/ω β I + 1/ω β j ,
and we have the premise

T n,j n ≥ ω β j + ξ.
Combining these with the convergence of the empirical means to the true means (consistency, see Lemma 23), we can conclude that for all ε > 0, there exists a time n 0 such that for all later times n ≥ n 0 , we have

(µ n,j -µ n,I ) 2 2σ 2 (n/T n,I + n/T n,j ) ≥ (µ j -µ I ) 2 2σ 2 (1/β + n/T n,j ) -ε ≥ (µ j -µ I ) 2 2σ 2 1/β + 1/(ω β j + ξ) -ε > Γ β ,
where the first inequality follows from consistency, the second from monotonicity in T n,j /n. That means that there exist a ξ > 0 such that

(µ n,j -µ n,I ) 2 2σ 2 (n/T n,I + n/T n,j ) -Γ β > ξ ,
and thus the claim follows that when Tn,j n ≥ ω β j + ξ, we have n(ξ +εn) .

a n,j max i =I a n,i ≤ exp -n (µ n,j -µ n,I ) 2 2σ 2 (n/T n,I + n/T n,j ) -Γ β -ε n ≤ e -
Step 3: ψ n,i converges to ω β i for all arms. To establish the convergence of the allocation effort of all arms, we rely on the same sufficient condition used in the analysis of Russo ( 2016), that we recall below. First, note that from Lemma 22 we know that T n,I /n → β, an by Lemma 4 this implies ψ n,I → β, hence we can use Lemma 25 to prove convergence to the optimal proportions. Thus, we now show that ( 14) holds under TTTS. Recall that J

(1) n = arg max j a n,j and J

(2) n = arg max j =J (1) n a n,j . Since a n,I → 1 by Lemma 22, there is some finite time τ after which for all n > τ , J

(1) n = I . Under TTTS,

ψ n,i = a n,i   β + (1 -β) j =i a n,j 1 -a n,j   ≤ a n,i β + a n,i (1 -β) j =i a n,j 1 -a n,J (1) n ≤ a n,i β + a n,i (1 -β) j =i a n,j a n,J (2) n ≤ a n,i β + a n,i (1 -β) 1 a n,J (2) n ≤ a n,i a n,J (2) n ,
where we use the fact that for j = J . For n ≥ τ this means that ψ n,i ≤ a n,i / max j =I a n,i for any i = I . By Lemma 24, there is a constant ξ > 0 such and a sequence ε n → 0 such that n(ξ -εn) .

T n,i /n ≥ w β i + ξ ⇒ a n,i max j =I a n,j ≤ e -
Now take a time τ large enough, such that for n ≥ τ we have |T n,j /n -ψ n,j | ≤ ξ (which can be found by Lemma 4). Then we have

1 ψ n,j ≥ ψ β j + ξ ≤ 1 T n,j n ≥ ω β j + 2ξ
Therefore, for all i = I , we have

n≥τ ψ n,i 1 ψ n,j ≥ ψ β j + ξ ≤ n≥τ ψ n,i 1 T n,j n ≥ ω β j + 2ξ ≤ n≥τ e -n(ξ -εn) < ∞.
Thus ( 14) holds and the convergence to the optimal proportions follows by Lemma 25. and recall that for i ∈ A for which T n,i = 0, we have µ ni = µ 1,i = 0 and σ 2 n,i = σ 2 1,i = ∞, and if T n,i > 0, we have

µ n,i = 1 T n,i n-1 =1 1{I = i}Y ,I , and σ 2 n,i = σ 2 T n,i .
For all arms that are sampled infinitely often, we therefore have µ ∞,i = µ i and σ 2 ∞,i = 0. For all arms that are sampled only a finite number of times, i.e. i ∈ I, we have σ 2 ∞,i > 0, and there exists a time n 0 after which for all n ≥ n 0 and i ∈ I, we have

T n,i = T n0,i . Define Π ∞ N (µ ∞,1 , σ 2 ∞,1 ) ⊗ N (µ ∞,2 , σ 2 ∞,2 ) ⊗ . . . ⊗ N (µ ∞,k , σ 2 ∞,k ) = i ∈I δ µi ⊗ i∈I Π n0 .
Then for each i ∈ A we define

a ∞,i Π ∞ θ i > max j =i θ j .
Then we have for all i ∈ I, a ∞,i ∈ (0, 1), since σ 2 ∞,i > 0, and thus a ∞,I < 1.

When I is empty, we have a n,I = Π n (θ I > max i =I θ i ), but since Π ∞ = i∈A δ µi , we have a ∞,I = 1 and a ∞,i = 0 for all i = I . so that we have

H Proof of Posterior Convergence for the Bernoulli Bandit

P [X ≥ x] = P [B a+b-1,x ≤ a -1] = P [B a+b-1,1-x ≥ b] .
We can bound Binomial tails with Sanov's inequality:

e -nd(k/n,x) n + 1 ≤ P [B n,x ≥ k] ≤ e -nd(k/n,x) ,
where the last inequalities hold when k ≥ nx.

Lemma 26. Let X ∼ Beta(a, b) and Y ∼ Beta(c, d) with 0 < a-1 a+b-1 < c-1 c+d-1 . Then we have P [X > Y ] ≤ De -C where C = inf a-1 a+b-1 ≤y≤ c-1 c+d-1 C a,b (y) + C c,d (y),
and

D = 3 + min C a,b c -1 c + d -1 , C c,d a -1 a + b -1 .
Note that this lemma is the Bernoulli version of Lemma 2.

Theorem 6. Consider the Beta-Bernoulli setting. For β ∈ (0, 1), under any allocation rule satisfying T n,I /n → ω

β I , lim n→∞ - 1 n log(1 -a n,I ) ≤ Γ β ,
and under any allocation rule satisfying T n,i /n → ω β i for each i ∈ A,

lim n→∞ - 1 n log(1 -a n,I ) = Γ β .
Proof. Denote again with I again the set of arms sampled only finitely many times. For I empty, we thus have µ ∞,i lim n→∞ µ n,i = µ i . The posterior variance is

σ 2 n,i = α n,i β n,i (α n,i + β n,i ) 2 (α n,i + β n,i + 1) = (1 + n-1 =1 1{I = i}Y ,I )(1 + T n,i - n-1 =1 1{I = i}Y ,I ) (2 + T n,i ) 2 (2 + T n,i + 1)
.

We see that when I is empty, we have σ 2 ∞,i lim n→∞ σ 2 n,i = 0, i.e., the posterior is concentrated.

Step 1: A lower bound when some arms are sampled only finitely often. First, note that when T n,i = 0 for some i ∈ A, the empirical mean for that arm equals the prior mean µ n,i = α 0,i /(α 0,i + β 0,i ), and the variance is strictly positive: σ 2 n,i = (α 0,i β 0,i )/ (α 0,i + β 0,i ) 2 (α 0,i + β 0,i + 1) > 0. When I is not empty, then for every i ∈ I we have σ 2 ∞,i > 0, and a ∞,i ∈ (0, 1), implying a ∞,I < 1, and thus

lim n→∞ - 1 n log (1 -a n,I ) = - 1 n log (1 -a ∞,I ) = 0.

Preprint

Step 2: A lower bound when every arm is sampled infinitely often. Suppose now that I is empty, then we have

max i =I Π n (θ i ≥ θ I ) ≤ 1 -a n,I ≤ i =I Π n (θ i ≥ θ I ) ≤ (k -1) max i =I Π n (θ i ≥ θ I ).
Thus, we have 1 -a n,I ≤ (k -1) max i =I Π n (θ i ≥ θ I ) and also 1 -a n,I . = max i =I Π n (θ i ≥ θ I ). We have

Γ = max w∈W min i =I C i (ω I , ω i ), Γ β = max w∈W ;ω I =β min i =I C i (β, ω i ), with C i (ω I , ω i ) = min x∈R ω I d(θ I ; x) + ω i d(θ i ; x) = ω I d(θ I ; θ) + ω i d(θ i ; θ), where θ ∈ [θ i , θ I ] is the solution to A (θ) = ω I A (θ I ) + ω i A (θ i ) ω I + ω i .
Since every arm is sampled infinitely often, when n is large, we have µ n,I > µ n,i . Define S n,i n-1 =1 1{I = i}Y ,I . Recall that the posterior is a Beta distribution with parameters a n,i = S n,i + 1 and β n,i = T n,i -S n,i + 1. Let τ ∈ N be such that for every n ≥ τ , we have S n,i /(T n,i + 1) < S n,I /(T n,I + 1). For the sake of simplicity, we define for any i ∈ A the interval

I i,I S n,i T n,i + 1 , S n,I T n,I + 1 . Then using Lemma 26 with a = S n,i + 1, b = T n,i -S n,i + 1, c = S n,I + 1, d = T n,I -S n,I + 1, we have Π n (θ i -θ I ≥ 0) ≤ D exp -inf y∈I i,I
C Sn,i+1,Tn,i-Sn,i+1 (y) + C S n,I +1,T n,I -S n,I +1 (y) .

This implies

1 n log Π n (θ i ≥ θ I ) exp -inf y∈I i,I C Sn,i+1,Tn,i-Sn,i+1 (y) + C S n,I +1,T n,I -S n,I +1 (y) ≤ 1 n log(D),
which goes to zero as n goes to infinity. Indeed replacing a, b, c, d by their values in the definition of D we get

D ≤ 3 + (T n,i -1)kl S n,i T n,i + 1 ; S n,I T n,I + 1 ≤ 3 + (n + 1)kl 0; n n + 1 = (n + 1) log(n + 1) .
Hence,

Π n (θ i ≥ θ I ) . = exp -inf y∈I i,I
C Sn,i+1,Tn,i-Sn,i+1 (y) + C S n,I +1,T n,I -S n,I +1 (y) .

We thus have for any i,

1 -a n,i . = max j =I Π n [θ j ≥ θ I ] . = max j =I exp -inf y∈I j,I
C Sn,j +1,Tn,j -Sn,j +1 (y) + C S n,I +1,T Fix some ε > 0, then there exists some n 0 (ε) such that for all n ≥ n 0 (ε), we have for any j,

I j,I = S n,j T n,j + 1 , S n,I T n,I + 1 , ⊂ [µ j + ε, µ I -ε] I j,ε ,
and because KL-divergence is uniformly continuous on the compact interval I j,ε , there exists an n 1 such that for every n ≥ n 1 we have kl S n,j T n,j + 1 ; y ≥ (1 -ε)kl (µ j ; y) , for any y and for all j ∈ A. Therefore, we have

1 -a n,i . = exp -n max ω min j =I inf y∈I j,I ω j kl S n,j T n,j + 1 ; y + ω I kl S n,I T n,I + 1 ; y ≥ exp -n max ω min i =I inf y∈I j,ε ω i kl(µ j ; y) + ω I kl(µ I ; y) .
Therefore, we have

lim sup n→∞ - 1 n log(1 -a n,i ) ≤ Γ . If T n,i /n → ω i for each i ∈ A, we have lim n→∞ inf y∈I i,I T n,i + 1 n kl S n,i T n,i + 1 ; y + T n,I + 1 n kl S n,I T n,i + 1 ; y = inf y∈[µi, µ I ] ω i kl(µ i ; y) + ω I kl(µ I ; y) = Γ ,
and thus

1 -a n,i . = exp -n max ω min j =I inf y∈I ε ω i kl(µ j ; y) + ω I kl(µ I ; y) . = exp {-nΓ } , implying lim n→∞ - 1 n log (1 -a n,i ) = Γ .
Everything goes similarly when ω I = β ∈ (0, 1), so under any sampling rule satisfying T n,I /n → β we have

lim sup n→∞ - 1 n log(1 -a n,i ) ≤ Γ β
and under any sampling rule satisfying T n,i /n → ω β i for each i ∈ A, we have

lim n→∞ - 1 n log(1 -a n,i ) = Γ β .
H.2 Proof of Theorem 5

Theorem 5. Under TTTS, for Bernoulli bandits and uniform priors, it holds almost surely that

lim n→∞ - 1 n log(1 -a n,I ) = Γ β .
From Theorem 6 we know that under any allocation rule satisfying T n,i /n → ω β i for every i ∈ A, we have

lim n→∞ - 1 n log (1 -a n,I ) = Γ β .
Thus, we only need to prove that under TTTS, for all i ∈ A, we have

lim n→∞ T n,i n a.s = ω β i .
Just as for the proof of the Gaussian case, we can use Lemma 4 (proof = ω β i .

Therefore, it suffices to show convergence for ψ n,i = Ψ n,i /n to ω β i , which we will do next, following the same steps as in the proof for the Gaussian case.

Step 1: TTTS draws all arms infinitely often and satisfies T n,I /n → β. We prove the following lemma.

Lemma 27. Under TTTS, it holds almost surely that 1. for all i ∈ A, lim n→∞ T n,i = ∞.

2. a n,I → 1.

3.

T n,I n → β.

Proof. First, we give a lemma showing the implications of finite measurement, and consistency when all arms are sampled infinitely often, which provides a proof for 2. The proof of this lemma follows from the proof of Theorem 6, and is given in Appendix H.3.

Lemma 28 (Consistency and implications of finite measurement).

Denote with I the arms that are sampled only a finite amount of times: I = {i ∈ {1, . . . , k} : ∀n, T n,i < ∞}.

If I is empty, a n,i converges almost surely to 1 when i = I and to 0 when i = I . If I is non-empty, then for every i ∈ I, we have lim inf n→∞ a n,i > 0 a.s.

Now we can show 1. of Lemma 27: we show that under TTTS, for each j ∈ A, we have n∈N T n,j = ∞. The proof is exactly equal to the proof for Gaussian arms.

Under TTTS, we have

ψ n,i = a n,i   β + (1 -β) j =i
a n,j 1 -a n,j   , so ψ n,i ≥ βa n,i , therefore, by Lemma 23, if i ∈ I, then lim inf a n,i > 0 implies that n ψ n,i = ∞. By Lemma 4, we then must have that lim n→∞ T n,i = ∞ as well: contradiction. Thus, lim n→∞ T n,i = ∞ for all i, and we conclude that a n,I → 1, by Lemma 23.

Lastly we prove point 3. of Lemma 27. For TTTS with parameter β, the above implies that ψ n,I → β, and since we have a bound on |T n,i /n -ψ n,i | in Lemma 4, we have T n,I /n → β as well.

Preprint

Step 2: Controlling the over-allocation of sub-optimal arms. Following the proof for the Gaussian case again, we can establish a consequence of the convergence of T n,I /n to β : if an arm is sampled more often than its optimal proportion, the posterior probability of this arm to be optimal is reduced compared to that of other sub-optimal arms. We can prove this by using ingredients from the proof of the lower bound in Theorem 6.

Lemma 29 (Over-allocation implies negligible probability).9 Fix any ξ > 0 and j = I . With probability 1, under any allocation rule, if T n,I /n → β, there exist ξ > 0 and a sequence ε n with ε n → 0 such that for any n ∈ N, T n,j n ≥ ω β j + ξ =⇒ a n,j max i =I a n,i ≤ e -n(ξ +εn) .

Proof. By Theorem 6, we have, as T n,I /n → β,

lim sup n→∞ - 1 n log max i =I a n,i ≤ Γ β ,
since max i =I a n,i ≤ 1 -a n,I . We also have from Lemma 26 a deviation inequality, so that we can establish the following logarithmic equivalence:

a n,j ≤ Π n (θ j ≥ θ I ) . = exp {-nC j (w n,I , ω n,j )} . = exp {-nC j (β, ω n,j )} ,

where we denote ω n,j Tn,j n . We can combine these results, which implies that there exists a non-negative sequence ε n → 0 such that

a n,j max i =I a n,i ≤ exp {-nC j (β, ω n,j ) -ε n /2} exp -n(Γ β + ε/2) = exp -n C j (β, ω n,j ) -Γ β -ε n .
We know that C j β, ω β j is strictly increasing in ω β j , and C j β, ω β j = Γ β , thus, there exists some ξ > 0 such that ω n,j ≥ ω β j + ξ =⇒ C j (β, ω n,j ) -Γ β > ξ .

Step 3: ψ n,i converges to ω β i for all arms. To establish the convergence of the allocation effort of all arms, we rely on the same sufficient condition used in the analysis of Russo (2016), restated above in Lemma 25, and we will restate it here again for convenience. First, note that from Lemma 27 we know that T n,I n → β, and by Lemma 4 this implies ψ n,I → β, hence we can use the lemma above to prove convergence to the optimal proportions. This proof is already given in Step 3 of the proof for the Gaussian case, and since it does not depend on the specifics of the Gaussian case, except for invoking Lemma 23 (consistency), which for the Bernoulli case we replace by Lemma 28, it gives a proof for the Bernoulli case as well. We conclude that (14) holds, and the convergence to the optimal proportions follows by Lemma 25.

P [X > Y ] = E [P [X > Y |Y ]] ≤ E 1{Y < a -1 a + b -1 } + 1{Y ≥ a -1 a + b -1 }P [X > Y |Y ] ≤ exp -(c + d -1)kl c -1 c + d -1 ; a -1 a + b -1 + E exp -(a + b -1)kl a -1 a + b -1 ; Y 1{Y ≥ a -1 a + b -1 } ,
Using the Beta-Binomial trick in the second inequality. Then we have (call the second half A) Proof of Lemma 28 Let I be empty, then we have µ ∞,i lim n→∞ µ n,i = µ i . The posterior variance is

A ≤ E 1{ a -1 a + b -1 ≤ Y ≤ c -1 c + d -1 } exp -(
σ 2 n,i = α n,i β n,i (α n,i + β n,i ) 2 (α n,i + β n,i + 1) = (1 + n-1 =1 1{I = i}Y ,I )(1 + T n,i - n-1 =1 1{I = i}Y ,I ) (2 + T n,i ) 2 (2 + T n,i + 1) ,
We see that when I is empty, we have σ 2 ∞,i lim n→∞ σ 2 n,i = 0, i.e., the posterior is concentrated.

When T n,i = 0 for some i ∈ A, the empirical mean for that arm equals to the prior mean µ n,i = α 1,i /(α 1,i + β 1,i ), and the variance is strictly positive: σ 2 n,i = (α n,i β n,i )/ (α 1,i + β 1,i ) 2 (α 1,i + β 1,i + 1) > 0. When I is not empty, then for every i ∈ I we have σ 2 ∞,i > 0, and α ∞,i ∈ (0, 1), implying α ∞,I < 1, hence the posterior is not concentrated.

Figure 1 :

 1 Figure 1: black dots represent means and oranges lines represent medians.

Lemma 25 (

 25 Sufficient condition for optimality). 8 Consider any adaptive allocation rule. If we have ψ n,I → β, and n∈Nψ n,j 1 ψ n,j ≥ ω β j + ξ < ∞, ∀j = I , ξ > 0,(14)then ψ n → ψ β .

  have a n,J (1) n ≥ a n,j and a n,J (2) n ≤ 1 -a n,J (1)n

G. 2

 2 Proof of auxiliary lemmas Proof of Lemma 23 Let I be nonempty. Define µ

H. 1

 1 PreliminariesWe first introduce a crucial Beta tail bound inequality. Let F Beta a,b denote the cdf of a Beta distribution with parameters a and b, and F B c,d the cdf of a Binomial distribution with parameters c and d, then we have the following relationship, often called the 'Beta-Binomial trick', F Beta a,b (y) = 1 -F B a+b-1,y (a -1),

Lemma 30 (

 30 Sufficient condition for optimality).Consider any adaptive allocation rule. Ifψ n,I → β, and n∈N ψ n,j 1 ψ n,j ≥ ω β j + ξ < ∞, ∀j = I , ξ > 0,(15)then ψ n → ψ β .

  a + b -1)kl a -1 a + b -1 ; Y + exp -(a + b -1)kl a -1 a + b -1 ; c -1 c + d -1 (call the first half B). Denote with f the density of Y , then exp -(a + b -1)kl a -1 a + b -1 ; y f (y) dy.Via integration by parts we obtainB = exp -(a + ba + b -1 ; y exp {-C a,b (y)} P (Y ≤ y) dy ≤ a + b -1 ; y exp {-(C a,b (y) + C c,d (y))} dy + exp -(a + b -1)kl a -1 a + b -1 ; c -1 c + d -1 ,where the first inequality uses the Binomial trick again. Let b (y) + C c,d (y), then note that in particular we haveC ≤ min (a + ba + b -1 ; y) dy + e -C = (a + b -1)kl a -1 a + b -1 ; c -1 c + d -1 + 1 e -C .Thus we haveP [X > Y ] ≤ 3 + (a + b -1)kl a -1 a + b -1 ; c -1 c + d -1 e -C .PreprintBy symmetry, we haveP [X > Y ] ≤ 3 + min C a,b

  n,I ,

	(µn,i -µn,I ) 2 2σ 2 n,i,I	= inf θ i <θ I	Tn,id(µn,i; θi) + Tn,I d(µn,I ; θI )
		≤ Tn,id(µn,i; µi) + Tn,I d(µn,I ; µI ).
	Corollary 10 of Kaufmann and Koolen (2018) then al-
	lows us to upper bound the probability
	P [∃n ∈ N : Tn,id(µn,i; µi) + Tn,I d(µn,I , µI ) ≥ d n,δ ]

  );Degenne et al. (2019).Finally, it is also important to study Bayesian sampling rules in the fixed-budget setting which is more plausible in many application scenarios such as applying BAI for automated machine learning(Hoffman et al., 2014; Li et al., 2017; Shang et al., 2019).

			Garivier, A. and Kaufmann, E. (2016). Optimal best
			arm identification with fixed confidence. In Pro-
			ceedings of the 29th Conference on Learning Theory
			(CoLT).
			Hoffman, M. W., Shahriari, B., and de Freitas, N.
			(2014). On correlation and budget constraints in
			model-based bandit optimization with application
			to automatic machine learning. In Proceedings of
			the 17th International Conference on Artificial In-
			telligence and Statistics (AIStats).
			Jamieson, K., Malloy, M., Nowak, R., and Bubeck, S.
			(2014). lil'UCB: An optimal exploration algorithm
			for multi-armed bandits. In Proceedings of the 27th
			Conference on Learning Theory (CoLT).
	Audibert, J.-Y. and Bubeck, S. (2010). Best arm iden-tification in multi-armed bandits. In Proceedings of the 23rd Conference on Learning Theory (CoLT).	Jun, K.-S. and Nowak, R. (2016). Anytime exploration for multi-armed bandits using confidence informa-tion. In Proceedings of the 33rd International Con-
			ference on Machine Learning (ICML).
	Pure exploration in finitely-armed and continuous-
	armed bandits.	Theoretical Computer Science,	Kaufmann, E. and Garivier, A. (2017). Learning the
	412(19):1832-1852.		distribution with largest mean: two bandit frame-
	Burnetas, A. N. and Katehakis, M. N. (1996). Optimal adaptive policies for sequential allocation problems.	works. ESAIM: Proceedings and Surveys, 60:114-131.
	Advances in Applied Mathematics, 17(2):122-142.	Kaufmann, E. and Koolen, W. (2018). Mixture
			martingales revisited with applications to sequen-
			tial tests and confidence intervals. arXiv preprint
			arXiv:1811.11419.
			Li, L., Jamieson, K., DeSalvo, G., Talwalkar, A.,
			and Rostamizadeh, A. (2017). Hyperband: Bandit-
	Carpentier, A. and Locatelli, A. (2016). Tight (lower)	based configuration evaluation for hyperparameter
	bounds for the fixed budget best arm identification	optimization. In Proceedings of the 5th International
	bandit problem. In Proceedings of the 29th Confer-	Conference on Learning Representations (ICLR).
	ence on Learning Theory (CoLT).	Ménard, P. (2019). Gradient ascent for active ex-
	Degenne, R., Koolen, W., and Ménard, P. (2019). Non-	ploration in bandit problems.	arXiv preprint
	asymptotic pure exploration by solving games. In	arXiv:1905.08165.
	Advances in Neural Information Processing Systems 33 (NeurIPS).	Qin, C., Klabjan, D., and Russo, D. (2017). Improv-ing the expected improvement algorithm. In Ad-
	Even-dar, E., Mannor, S., and Mansour, Y. (2003).	vances in Neural Information Processing Systems 30
	Action elimination and stopping conditions for rein-	(NIPS).

Auer, P.,

Cesa-Bianchi, N., and Fischer, P. (2002)

.

Finite-time analysis of the multi-armed bandit problem. Machine Learning Journal, 47(2-3):235-256. Bubeck, S., Munos, R., and Stoltz, G. (2009). Pure exploration in multi-armed bandits problems. In Proceedings of the 20th International Conference on Algorithmic Learning Theory (ALT). Bubeck, S., Munos, R., and Stoltz, G. (2011). Cappé, O., Garivier, A., Maillard, O. A., Munos, R., and Stoltz, G. (2013). Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 41(3):1516-1541. forcement learning. In Proceedings of the 20th International Conference on Machine Learning (ICML). Gabillon, V., Ghavamzadeh, M., and Lazaric, A. (2012). Best arm identification: A unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems 25 (NIPS). Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. (2012). PAC subset selection in stochastic multiarmed bandits. In Proceedings of the 29th International Conference on Machine Learning (ICML). Karnin, Z., Koren, T., and Somekh, O. (2013). Almost optimal exploration in multi-armed bandits. In Proceedings of the 30th International Conference on Machine Learning (ICML). Russo, D. (2016). Simple Bayesian algorithms for best arm identification. In Proceedings of the 29th Conference on Learning Theory (CoLT). Shang, X., Kaufmann, E., and Valko, M. (2019). A simple dynamic bandit algorithm for hyperparameter tuning. In 6th Workshop on Automated Machine Learning at International Conference on Machine Learning (ICML-AutoML).

  n,i -Ψ n,i | ≤ W 2 (n + 1) log(e 2 + n) almostsurely. Now it remains to show that ∀λ > 0, E e λW2 < ∞. Fix some λ > 0.

	∞						∞
	E e λW =	P e λW ≥ x dx =		P e λW ≥ e 2λy 2λe 2λy dy
	x=1						y=0
		2						∞
	= 2λ		P [W ≥ 2y] e 2λy dy + 2λ	P [W ≥ 2y] e 2λy dy
	y=0						y=2
	≤ 2λ	2	P [W ≥ 2y] e 2λy dy	+ 2λC 1	∞	e -y 2 /2 e 2λy dy	< ∞,
	y=0						y=2
			=e 4λ-1				<∞
	where C 1 is some constant.
	G Proof of Posterior Convergence for the Gaussian Bandit
	G.1 Proof of Theorem 4
	Theorem 4. Under TTTS, for Gaussian bandits with improper Gaussian priors, it holds almost surely that
			lim n→∞	-	1 n	log(1 -a n,I ) = Γ β .
	From Theorem 2 in Qin et al. (2017), any allocation rule satisfying T n,i /n → ω β i for each i ∈ A, satisfies
			lim n→∞	-	1 n	log(1 -a n,I ) = Γ β .
	Therefore, to prove Theorem 4, it is sufficient to prove that under TTTS,
		∀i ∈ {1, . . . , K},	lim n→∞	T n,i n	a.s = ω β i .

  n,I . By Theorem 2 of Qin et al. (2017) we have, as T n,I /n → β,

	lim sup n→∞	-	1 n	log max i =I

a n,i ≤ Γ β .

  in Appendix G.2), which implies

	lim n→∞	T n,i n	a.s = ω β i	⇔	n→∞ lim	n Ψ n,i	a.s

hereafter 'Gaussian bandits' or 'Gaussian model'

hereafter 'Bernoulli bandits'

the TTPS sampling rule (Russo, 2016) also requires the computation of an,i, thus we do not report simulations for this Bayesian sampling rule in Section 6

for which Wn(I , i) is an empirical counterpart

this proof is the same asProposition 3 of Qin et al. (2017)

analogue ofLemma 13 of Russo (2016)

analogue ofLemma 13 of Russo (2016)

Acknowledgement The research presented was supported by European CHIST-ERA project DELTA, French National Research Agency projects BADASS (ANR-16-CE40-0002) and BOLD (ANR-19-CE23-0026-04), the Inria-CWI associate team 6PAC and LUF travel grant number W19204-1-35.

A Outline

The appendix of this paper is organized as follows:

Appendix C provides the complete fixed-confidence analysis of TTTS (Gaussian case). Appendix D provides the complete fixed-confidence analysis of T3C (Gaussian case). Appendix E is dedicated to Lemma 1. Appendix F is dedicated to crucial technical lemmas. Appendix G is the proof to the posterior convergence Theorem 4 (Gaussian case). Appendix H is the proof to the posterior convergence Theorem 5 (Beta-Bernoulli case).

B Useful Notation for the Appendices

In this section, we provide a list of useful notation that is applied in appendices (including reminders of previous notation in the main text and some new ones).

Note that (ψ n,i ) i sums to 1,

Therefore, we have

on one hand, since i∈A a n,i = 1. On the other hand, we have

which concludes the proof.

The rest of this subsection is exactly the same to that of TTTS. Indeed, with the above lemma, we can show that the set of poorly explored arms U L n is empty when n is large enough. Lemma 18. Under T3C, there exists

Proof. See proof of Lemma 11 in Appendix C.1.

We can finally conclude the proof of Lemma 5 for T3C in the same way as for TTTS in Appendix C.1.

D.2 Concentration of the empirical means, proof of Lemma 6 under T3C

As a corollary of the previous section, we can show the concentration of µ n,i to µ i , and the proof remains the same as that of TTTS in Appendix C.2.

D.3 Measurement effort concentration of the optimal arm, proof of Lemma 7 under T3C

Next, we show that the empirical arm draws proportion of the true best arm for T3C concentrates to β when the total number of arm draws is sufficiently large. This proof also remains the same as that of TTTS in Appendix C.3.

D.4 Measurement effort concentration of other arms, proof of Lemma 8 under T3C

In this section, we show that, for T3C, the empirical measurement effort concentration also holds for other arms than the true best arm. Note that this part differs from that of TTTS.

We again establish first an over-allocation implies negligible probability result as follow.

Lemma 19. Under T3C, for every ξ ≤ ε 0 with ε 0 problem dependent, there exists S 1 = Poly(1/ξ, W 1 , W 2 ) such that for all n > S 1 , for all i = I ,

Proof. Fix i = I s.t. Ψ n,i /n ≥ ω β i + 2ξ, then using Lemma 4, there exists S 2 = Poly(1/ξ, W 2 ) such that for any n > S 2 , we have T n,i n ≥ ω β i + ξ.