Fixed Confidence Best Arm Identification in the Bayesian Setting
Authors: Kyoungseok Jang
Junpei Komiyama
Kazutoshi Yamazaki
Venue: NeurIPS 2024 poster (2024)
Keywords: Multi-armed bandit
Best arm identification
Primary area: bandits
TL;DR: Fixed-confidence best arm identification in the Bayesian setting, where the mean vector is drawn from a known prior.

Abstract: We consider the fixed-confidence best arm identification (FC-BAI) problem in the Bayesian setting. This problem aims to find the arm of the largest mean with a fixed confidence level when the bandit model has been sampled from the known prior. 
Most studies on the FC-BAI problem have been conducted in the frequentist setting, where the bandit model is predetermined before the game starts. 
We show that the traditional FC-BAI algorithms studied in the frequentist setting, such as track-and-stop and top-two algorithms, result in arbitrarily suboptimal performances in the Bayesian setting. 
We also obtain a lower bound of the expected number of samples in the Bayesian setting and introduce a variant of successive elimination that has a matching performance with the lower bound up to a logarithmic factor. Simulations verify the theoretical results.

Fixed Confidence Best Arm Identification in the Bayesian Setting
Kyoungseok Jang Universitá degli Studi di Milano ksajks@mmiil. com
Junpei Komiyama New York University RIKEN AIP Sunpei@komyymaa info
Kazutoshi Yamazaki The University of Queensland k. yamazaki @uq. edu, au
Abstract
We consider the fixed-confidence best arm identification (FC-BAI) problem in the Bayesian setting. This problem aims to find the arm of the largest mean with a fixed confidence level when the bandit model has been sampled from the known prior. Most studies on the FC-BAI problem have been conducted in the frequentist setting, where the bandit model is predetermined before the game starts. We show that the traditional FC-BAI algorithms studied in the frequentist setting, such as track- and-stop and top-two algorithms, result in arbitrarily suboptimal performances in the Bayesian setting. We also obtain lower bound of the expected number samples in the Bayesian setting and introduce variant of successive elimination that has matching performance with the lower bound up to a logarithmic factor. Simulations verify the theoretical results.
Introduction
In many sequential decision-makinn problems, the learner repeatedly chooses arm (option) to play with and observes a reward drawn from the unknown distribution the corresponding arm. One of the most widcly-studies instances of such problems is the multi-armed bandit problem [Thompson]
1933 Robbins 1952 Lai 1987). where the goal is to maximize the sum of rewards during the rounds. Since the learner does not know the distribution of rewards, they need to explore the different arms, and yet, exploit the arms of the most rewarding arms so far. Different from the classical bandit formulation, there situations where one is more interested in collecting information rather than maximizing intermediate rewards. The best arm identification (BAI) is a sequential decision makinng problem in which the learner only interested in identifying the arm with the highest mean reward. While the origin of this problem dates back to at least the 1950s [Bechhofer] 1954] Paulson 1964 Gupta 1977). recent work in the field of machine learning reformulated the problem Audibert et al. 2010 In the BAI, the learner needs to pull arms efficiently for better identification. To achieve efficiency and accuracy, the learner should determine which arm choose based the history, when to stop the sampling, and which arm to recommend as the learner's final decision.
There two types of BAI problems depending the optimization objective. In the (FB) setting [Audibert et al.] 2010), the learner attempts to minimize the probability of error (misiden- tification of the best arm) given limited number of arm pulls T. In the fixed confidence (FC) setting Jamieson and Nowak 2014). the learner attempts to minimize the number of arm pulls, subject to a predefined probability of error 8 (0, 1). In this paper, shall focus the FC setting, which is useful when we desire a rigorous statistical guarantee.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Most of the previous BAI studies focus on the frequentist setting, where the bandit model is chosen adversarially from some hypothesis class beforehand. In this setting, several algorithms, such as Track and Stop Kaufmann et al. 201 6a) and Top-two algorithms [Russo] 2016 Qin et al. 201 7b Jourdan jet al. 2202], , are widely known. These algorithms have an optimal sample complexity, meaning that they are one of the most sample-efficient algorithms among the class of é-correct algorithms.
The sample complexity of these algorithms is problem-dependent. To see this, consider the following example.
Example 1. (A/B/C testing) Consider A/B/C testing of web designs. We have three arms (web designs) from which we would like to find the largest retention rate via allocating users to web designs = 1, 2,3. If we attempt find the best arm with confidence 6, we may need large number of samples (users) when the suboptimality gap (the gap between the retention rate of the best arm and the second best arm) is small because in such case the identification of the best arm is difficult the minimum number of samples required is inversely proportional to the square of the suboptimality gap(Kaufmaan al., 2014]. For example, when comparing the testing of retention rates of (0.9, 0.5, 0.1) with (0.9, 0.89, 0.1), the second case requires around compared to the first case.
0.9-0.5
1600 times more samples
0.9-0.89
In practice, the retention rate of 0.89 in the second case may be acceptably good compared to the optimal retention rate of 0.9, and we may stop exploration at the moment the learner identifies reasonably good arm, which is the first or the second arm in this example. This idea is formalized in several ways. The literature of Ranking and Selection (R&S) usually considers the indifference-zone formulation [Hong et al., 2021). In the context of best arm identification, a similar notion of c-best
answer identification has also been considered [Maron and Moore, 1993 Even-Dar et al.) 2006
Gabillon et al. 2012 Kaufmann and Kalyanakrishnan 2013 Jourdan et al. 2023 In these settings,
the leamner accepts sub-optimal arm whose means are most e worse than the mean of the optimal
arm. Other related settings include the good arm identification problem (Kano et al. 2019 Tabata cet al.. 2020 Zhao al. 2023). J. where the goal is identify an arm that exceeds the predefined threshold, and the thresholding bandit problem (Locatelli et al. [016]] Xu et al.] [019]] where the
goal is to identify whether the mean of each arm above or below the threshold. All these problem
settings require an extra parameter, like c or an acceptance threshold, that directly determines the acceptance level. Even though the algorithm's performance depends on this parameter, it is often challenging to determine a reasonable value for it in advance.
In this paper, we study an alternative approach based on the Bayesian setting. In particular, we consider the prior distribution on the model parameters. We relax the requirement on the correctness of the best arm identification by using the prior belief. Rather than requiring the frequentist ö- correctness for any model, we require the learner to have marginalized correctness over the prior distribution, which we call Bayesian Ó-correctness.
We study the fixed confidence BAI (FC-BAI) problem in the Bayesian setting. Our contributions are as follows.
First, find that in the Bayesian setting, the performance of the traditional frequentist setting-based algorithms, such as Track and Stop and Top-two algorithms, can be arbitrarily worse (Section 3). This is because frequentist approaches spend too many resources when the suboptimality gap is narrow.
Second, we prove that the lower bound of the number of expected samples should attain at least the order of Ω ((HH)" as 5 + 0 (Section 4). Here L(H) is our novel quantity that represents the sample complexity with respect to the prior distribution H. This order is different from the existing lower bound in the frequentist setting implying that the Bayesian setting is essentially different from the frequentist setting.
Third, we design
algorithm whose expected sample size is upper-bounded by
5 log L(H)) (Section 5) Our algorithm is based on the elimination algorithm [Maron and Moore 1993] Even-Dar et al.] [0066] Frazierr 2014], but we add an early stop- ping criterion to prevent wermcoommtment of the algorithm for bandit model with a narrow suboptimality gap. Our algorithm has a matching upper bound up the logarithmic factor.
O(H(H))
In fact, marginalizing the frequentist sample complexity over the prior distribution leads to an unbounded value.

---

We also conduct simulation to demonstrate that the sample complexity of frequentist algorithms does indeed diverge in a bandit model with small suboptimality gap, even in very simple cases (Section 60..
1.1 Related work
To our knowledge, BAI problems studied for the Bayesian setting have been limited to the fixed budget setting [Komiyama et al. 2023 Atsidakou et al. 2023]. Komiyama et al. (2023] showed that, in the fixed-budget setting, a simple non-Bayesian algorithm has an optimal simple regret up to a constant factor, implying that the advantage the learner could get from the prior is small when the
budget is large. This is very different from our fixed-confidence setting, where utilizing the prior distribution is necessary.
Several FC-BAI algorithms used Bayesian ideas on the structure of the algorithm, although most of those studies used frequentist settings for measuring the guarantee. The "Top-Two" type of algorithms are the leading representatives in this direction. The first instance of top-two algorithms, which is called Top-Two Thompson sampling (TTTS), is introduced in the context of Bayesian best arm identification. TTTS requires a prior distribution, and Russo [2066] showed that the sample complexity of posterior convergence of TTTS which is the same as the sample complexity of the frequentist fxxed-coffidecc best arm identification. Subsequent research analyzed the performance of TTTS from the frequentists' viewpoint (Shang et al. 2020]. Later on, the idea of top-two sampling is then extended into many other algorithms, such as Top-Two Transportation Cost [Shang et al. 2020]. Top-Two Expected Improvement (TTEL, Qin et al. 2017b), Top-Two Upper Confidence bound (TTOCB, Jourdan and Degenne 2022a). Even though some of the top two algorithms adapt a prior, they implicitly solve the optimization that is justified in view of frequentist.
Jourdan
Another line of Bayesian sequential decision-making is Bayesian optimization (Srinivas et al. 2010 Mockus, 2012 Shahriari et al.) 2016 Jamieson and Talwalkar 2016 Frazier, 2018), where the goal is to find the best arm in Bayesian setting. Note that Bayesian optimization tends to deal with structured identification, especially for Gaussian processes, and most of the algorithms for Bayesian optimization do not have specific stopping criteria.
2 Problem setup
We study the fixed confidence best arm identification problem (FC-BAI) in a Bayesian setting. In this setup, we have i arms in the set [k] := {1,2... .... k} with unknown distribution P = (PI, Ps) which is drawn from a known prior distribution time 0, namely H (H,,... Hg). The unknown bandit model P: is one-parameter distribution, and P is specified by μ == (MI,... ms). To simplify the problem, we will focus on the Gaussian case, where each P; is a Gaussian distribution with known variance of. Each mean of P., denoted μ4, is drawn from a known prior Gaussian distribution Hi, which can be written as ((m,,53)
At every time step t 1,2, the forecaster chooses an arm A, E [k] and observes a reward Xe. which is drawn independently from PA.- Since we focus on the Gaussian case, X, N A,) conditionally given A, and μ.A.- After each sampling, the forecaster must decide whether to continue the sampling process or stop sampling and make recommendation
[R:].
Let F, = (Ai, X1, A2, X2, ... Ar,, Xx) be the a-field generated by observations up to time L. The algorithm of the forecaster = ((At)e: T; J) is defined by the following triplet [Kaufmann et al. 2016a]:
A sampling rule (A,).. which determines the arm to draw at round t based on the previous history (each A, must be F. measurable).
A stopping rule т, which means when to stop the sampling (i.c., stopping time with respect F,).
A decision rule J. which determines the arm the forecaster recommends based on his sampling history (i.c., J is F, m
In FC-BAI, the forecaster aims to recommend arm J that correctly identifies (one of) the best arm(s)
i" (p)) arg max [s] #4 with probability at least 1 8. Since the case of multiple best arms is of
3

---

measure zero under H, we can focus on such that i (f²) is unique. For the FC-BAI problem in the Bayesian setting, we use the expected probability of misidentification:
(T H) = : Ep-H (
(1)
where My := {f is the correct bandit model). Now we formally define the algorithm of interest as follows:
Definition 1. (Bayesian 5-correctness) For a prior distribution H, an algorithm л = ((At), T,
is said to be Bayesian (H, 8) correett if it satisfies (TE H) I 8. Let ( H) be the set of Bayesian (H, co-rrett algorithms for the prior distribution H.
The objective of the FC-BAI problem in the Bayesian setting is to find an algorithm ा ((A)), E (6, H) that minimizes Hx-
Terminology Define N:(1) Σ 1[A, i] the number of times arm i is pulled before timestep L. Let hg be the probability density function of H3. Since we consider Gaussian prior, hx(p))= = (1/v2x),,) (1pp(-44-m,))) /2())))(2))))))))))))))))))))( Let j j"= R + [k] be the best and the second best
arm under the input such that for each E (XER* : + xyVi + j}. 8 (n)) = arg max []] (4
and j (14) = arg (/(( 14:
Let (al(a =
[a=b)² : represent the KI--divergence between two Gaussian distributions with 20
equal variances (the variance of the i-th arm of) but different means, denoted as a and b. Similarly, d(a, b) == log(a/b) + (1 a) log((1 - a)/(1 b)) is the KL divergence between two Bernoulli distributions with means a and Throughout this paper, E and Py denote the expectation and probability when the bandit model fixed as E RR, i.e., Ey = E[-[Huu and Pp = P-(1Ht). We will abuse the notation PoE so that for À E R PoE(T; A) means
PoF((T; A) = ( + ( Naturally, PTE(T; H) = Ep-H PoE((: [T)
Lastly, we introduce the constant L H)) that characterizes the sample complexity in the Bayesian setting.
Definition 2. For each i,j E [kt). define (i)(H) and L(H) as follows:
L(H): = Σ Lif(H) where (i) [ (x(x)))(a)
II
(z) dr.
(JE())
(+M()))
This constant has the following interesting property which we call a volume lemma: Lemma (Volume Lemma, informal). For A E (0, 1), let
1 PP Pa~H pirt)) (4)(()) S S
A L(H). In particular, for A L(H, A)
Then, lim L(H, A) 2L)())
L(H)
L(H,A)
The volume lemma states that the volume of prior where the suboptimality gap is smaller than A is proportional L(H)A A when A is small. We will in Section 3 that such small-gap cases, which require a large amount of exploration to identify the best arm, dominate the Bayesian expectation of the stopping time. Therefore, L (H) defines the Bayesian sample complexity. The formal version of this lemma, which involves some regularity conditions, is shown in Appendix B
Remark Here, we elaborate on how the Bayesian sample complexity defined. As will be shown in Section 3 for an algorithm to have finite expected stopping time, it must determine whether the current instance is difficult or not. particular, if an algorithm tries to identify even the top-O(5) "hardest instances ? in the prior, the algorithm cannot achieve the finite expected stopping time. By
Here the hardness is based on the size of the suboptimality gap. When the suboptimality gap of an instance small, it is harder instance for the BAI algorithm to identify the best arm, mentioned in Example 1.

---

Lemma 1 the suboptimality gap of the top-O(6) hardest instance is given by L(H) = 8. and the corresponding (frequentist) sample complexity is proportional to A - (L(H)/6)² [Kaufmann et al. 2014). Such instances constitute an (6)) fraction of the prior, and thus the Bayesian sample complexity is:
(I(H))2 8²
x x6)=0 =0 ( (L(H))) ((((())))
3 Limitation of traditional frequentist approaches in the Bayesian setting
Existing BAI studies mainly focused on the Frequentist d-correct algorithms which are defined as follows:
Definition 3 (Frequentist 5-correctness). An algorithm = ((Ar), T, J) is said to be frequentist 5-correct if, for any bandit instance μa E R* such that i" (()) is unique, it satisfies PoE(T; (4) S 8. Let A (6) be the set of all frequentist---correet algorithms.
For the frequentist d-correct algorithms, Garivier and Kaufmann 2016 proved a lower bound for the expected stopping time as follows: for all bandit instance μe R and for all ((Ac), E (
B [r] log(6 ( + oolog((-1))
where 7" (f4) is a sample complexity function dependent on the bandit instance μ Moreover, many of the known frequentist d-correct algorithms achieve asymptotic optimality [Garivier and Kaufmanni 2016 Russo 2016 Tabata et al. 2023] Qin al. 2017a meaning that they are orderwisely tight up to the lower bound on Eq. (2) as ò O. However, little is known, or at least discussed, about their performance in the Bayesian setting.
One can check that frequentist 8-correct algorithm also Bayesian 8-correct as well (A4 C (8, H) for all H). Naturally, our interest whether or not the most efficient classes of fre- quentist d-correct algorithms, such as Tracking algorithms and Top-two algorithms, are efficient in Bayesian settings. Somewhat surprisingly, the following theorem states that any 8-correct algorithm is suboptimal in Bayesian settings.
Theorem 2. For all 8 > 0, H and ((Ar), E (O), En~H [T] to0.
Proof of Theorem P found in Appendix C illustrate proof, we will use a two-armed Gaussian instance as an example.
3.1 Special case two armed Gaussian case
Here we present one intuitive corollary of the lower bound theorem [Kaufmann al. 2016a Garivier and Kaufmann] 2016 Kaufmann et al. 2016b) that uses a standard information thhoorttic technique.
Corollary 3 (Kaufmann et al. 2014). Let 6 E (0, 1). For any frequentist 8-correct algorithm
((AI),T)) and for any fixed mean vector fa (11 (2) IR? E, [T] 2
(n -12) Z
d(6.1-6)
log T
((1-W2)
In the frequentist setting, Corollary implies the lower bound of [x,[T]] 2(log(5 (5-1)/ -22)²).
which is 2(log(6-1)) when view parameters (μr, M2) constants. However, in the Bayesian setting, the algorithm is given the prior distribution H on μ4, and thus the stopping time is marginalized
over H. In particular, limiting our interest to the case of A11 pul < A for small enough A > 0, can obtain the following lower bound:
TF Ey (7) 2 Eu H
1 [1/4 - M2l S A]]
(Since 7 is positive r.v.)
> E P H
[[(T(4] 1| μ2l < A]]
(Law of total expectation)
log 8-1
E
1| H2l A]
(Corollary
(11 222
log 8
log 0 L(H)
P [| μ2l < A
(Lemmal
2
2
2
For details about 1 (M)) reader may refer Garivier and Kaufmann 2016
5

---

(L((L)))) log 8-
((H))
This inequality implies that if we naively use known frequentist d-correct algorithm in the Bayesian setting, the expected stopping time will diverge because we can choose an arbitrarily small A. The case of a small gap is difficult to identify, and the expected stopping time can be very large for such a case if aim to identify the best arm for any model.
4 Lower bound
This section will elaborate on the lower bound the stopping time the Bayesian setting. Theorem below states that any Bayesian (H, correct algorithm requires the expected stopping time of at
least S2( L(H)
Theorem 4. Define miin = min of and Ny = L(H))oo ln Let < 8 (H) be sufficiently 16e
small Then, for any BAI algorithms = ((A,), T, JJ), if Bn- S Nv, then PoE(T: H) 2 8.
In this main body, we will use the two-armed Gaussian bandit model with homogeneous variance condition (i.e. 01 = σ2 = σ) for easier demonstration of the proof sketch. Theorem 4 which is more general in the sense that it can deal with k > 2 arms with heterogeneous variances, proven in Appendix D
Sketch of the proof, for h: = 2: It suffices to show that the following is an empty set:
(6, H. Nv) ( (6 H) En-HH [7] Nv..
Assume that ( H, Ny) * and choose an arbitrary π E (6, H. Ny). We start from the following transportation lemma:
Lemma 5 (Kaufmann al. [2016a] Lemma 1). Let E (0, 1). For any algorithm ((A)), T, J), any measuraabe event E, any bandit models μ, {x,,) R² x y) such that i (' & (A),
Ep Σ (L, d(PP(E).PA(E))
Note that the above Lemma holds for any algorithm, and thus works for any stopping time r. Now define v(u) swapped version of μ4 R2, which means (v(μ)); μ2, ((4) = μ4, and let
{J * (. the event that the recommendation of the algorithm is wrong. Substituting À with v(() from the above equation of Lemma leads
(un - 222) - 20
E
2 d(PoE(T; p1) PoE(T;U)) 2 log 2.4(PoE(T; μ4) + PoE(T:
(3)
Note that the first inequality comes from the fact that E, the failure event of the bandit model μt, is exactly success event of =(4x) in this two-armed case, and the last inequality is from modified lemma (Lemmall from Eq. (3) of Kaufmann et al. [2016a]. One can rewrite the above inequality as
PoE(T; ; p) + PoÉ(T; v)
(Mi 122) :1
cxp
E,,
4)
2.4
20
We can rewrite the conditions of (6, H, Nv) as
PoE(T: H)
PoE(T; μ) dH (p) < and
E, En HH S Ny. (Opt0)
MER2
UERE
Using Eq.
4 and with some symmetry tricks, we get Vo PoE(T; H) where
(M) - 22)² Embr (H()) < 5 and / pE
Vn =
exp
E EnldHH()) S Nv.
MER2 2.4
20
(Opt1)
In particular, 8z (H) f defined in Appendix

---

Algorithm Successive Elimination with Early-Stopping
Input: Confidence level ó, prior H
Ag := 2L(H)
Initialize the candidate of best arms A(1) [K].
t ==
while True do
Draw each arm in A(t) once. t < + |A((t)|- for i A(t) do
Compute UCB(1, 6) and ICB( () from 5
if (UUBB(E S max, LCB(j,t) then A(t) < A(t) {2).
end if end for if [A(() = then
Return arm in A(t). end if Compute Á = max UCB(i, max LCB(i, t).
(EA(())
(EA(()
if Å Amafo(t (t) Return arm J, uniformly sampled from A(t).
Ag then
end if end while
Note that on the above two inequalities, only Ey,[T] is the value that depends on the algorithm и. Now our main idea is that we can relax these two inequalities to the following optimization problem by substituting 1 [r] to arbitrary û: R22 > [0, oo) as follows:
/
(ni (1I- (22) n((pe)
(H( s.t. J. (H) S Nv
V
inf (0,00) MER2
exp
202
(Opt2)
and < 2.4% < 2.45. Let W == {u IR? |/1 U2l < A
86 }. From the discussions in L(HR)
Section 3.1 might notice that N' is an important region for bounding H(T). We relax the above (pt2) to the following version, which focuses more on NV
/ exp (-(mn- (-"mn-ma) 12)² m((1)) (H( s.t. JeEX a(p)dH(p) S Nv.
V"
inf n: + (0,00) PEN
20
(0pt3)
One can prove V S V < 2.45. Now, if we notice that function x + exp (- ( x) is convex function, we can use Jensen's inequality to verify that the optimal solution for (Opt3) when E E [x]] 1v. and when we use Ny in Theorem 4 one can get:
2
Nv
V'
exp
20²
B
dH(u)
(by optimality of
Ny E [w
PEN
2 Ny (AL(H
A Nv (2L(H)) (
) AL(H) (both by Lemma
cxp
dH(H) 2 exp
JEN
2.46,
(by definition of Ny and A)
which is contradiction. This means no algorithm satisfies OOpt and the proof is completed.
5 Main algorithm
This section introduces our main algorithm (Algorithm T In short, our algorithm is modification of the climination algorithm with the incorporation of the indifference zone technique. Define
7

---

Ao (L(H) which satisfies the following condition, thanks to Lemma
8
P (pr) (3r(()) S Ao) - 2"
In each iteration of the while loop of Algorithm [ the learner selects and observes each arm in the active set. After drawing each once, the algorithm calculates the confidence bounds for each arm in the active set using the formula as follows: let Conf(i, t) and (t(t) be the confidence width and the empirical mean of arm at time as
log (eg((((M))) (((((((())))))) (N))))))))
(i
?
(a(()) = Σ
X, [ ii.
(2())
Then the upper and lower confidence bounds of arm at timestep denoted UCB and LCB respectively, can be defined in the following manner:
tC = (t( + Conf(i, t),
LCB(i,t) (t( Conf(i, t).
(5)
This confidence bounds ensure that, with high probability, for all t E [T] and i [K]. #4 (UCB(i, f), LCB(i, t)) (See Lemma 15 in Appendix for details). After calculating UCB and LCB, the algorithm eliminates arms with UCB smaller than the largest LCB and maintains only arms that could be optimal in the active set A. Up to this point, follows the traditional elimination approach.
The main difference in our algorithm lies in the stopping criterion. At the end of each iteration, the algorithm checks the stopping criterion. Unlike typical climination algorithms that continue until only one arm remains, we have introduced an additional indifference condition. This condition arises when the suboptimalitt gap is so small that identifying them would require an excessive number of samples. In such cases, our algorithm stops additional attempts to identify differences between arms in the active set and randomly recommends one from the active set instead.
Remark 2. In the context of PAC-(e, 8) identification, Evr et al. (006) Remark 9] introduced a similar approach. The largest difference that they use the parameter as parameter that defines the indifference-zone level, whereas our parameter An is spontaneously derived from the prior H and the confidence level å without specifying the indifference- zone.. zone.
Theorem 6 describes the theoretical guarantee of the Algorithm
Theorem For 8 (H) min
Eee (min Exbry (H)
F(
Algorithm
which
consists of ((At), J) has the expected stopping time upper bound follows:
L(H)²
log [(HH) + O(log
Eu~H[T] S C¹ 2 max
(6)
where == 320 +1) is a universal constant and Omax max Øt. Here, O(log is function of ó and H that is proportional to log 8-1 when view prior parameters H as constants. Plus, the strategy defined by Algorithm is in (8,
See Appendix for the formal proof of Theorem Remark 3. When we compare the lower bound (Theorem 4 with the upper bound of Algorithm (Theorem 6). we can see the algorithm is near-optimal. If we view Fmax/ 0min as a constant, the bounds tight up a log L(H) factor.
Remark 4. The condition 5 4L(H) min ((H)/ jij è. jin (E (H))) is only for cleaner illustration of the regret bound in Theorem 6 moderately large constant, can be found in Appendix E.I
The non-asymptotic result, when 6 is
Proof sketch of Theorem We summarize the general strategy for the proof as follows. By the law of total expectation, Ep~H[T] [7] En~ En[r]] Therefore, we first derive a frequentist upper
bound of Ey, [7). and then marginalize it obtain the expected Bayesian stopping time. First, with the confidence bound defined as Eq. 5 we have the following guarantee that the true means for all arms are in the confidence bound interval with high probability.

---

Lemma 7. For any fixed {v E R :u & u, for all i.j E [k],, let x()) = {Vi E [k] and t N, M. E (LCB(i,t), UCB(i, t))}. Then, Pu Pn (x(()) 2 -8.
Now we can rewrite E H--H [r] as follows:
Ex~H [r] =B [u[T]]
(Law of Total Expectation)
= BBEHH H EE [ [ [[((x)] + EA-H [xx
BuCH En [[ EE [[NTI[[
(7)
Let A, = A.()) == (maxse Ms) 4n and Ro(A) Rd [Coo
For the first term, under X()), we can bound NT(T) by Ro(max Ao. A:)) (Lemma 17 Appendix D and integrate it over
log A
the prior distribution to obtain the leading factor. For the second term, thanks to the indifference
stopping condition (Å (t) I Ao). one prove that T is always smaller than R(Ao) (Lemma 14 in Appendix which leads to non-leading term.
To check that the expected probability of error is below 8, we have an additional lemma:
Lemma 8 (Probability of dropping i" (11)). For any μo, under Hao (11) C N. (i)()) E A(t))
This lemma means under the event (u), the best arm is never dropped. We can also prove that under the event (1)). if (,( ) > Ao. the sub-optimal arm will eventually be dropped before the algorithm terminates (Lemma 14 in Appendix [E). These two facts mean there are only two cases in which the prediction of Algorithm could be wrong.
Under X(x),, both facts cannot guarantee the correct identification. From Lemma (p( < 82 for all μ., and thus IP, (P-HH (x)) S 6
When (p( < Ag. From Lemma and the definition of Ao. the probability of drawing such μ from the prior is at most 6/2.
Therefore, by union bound, Algorithm Taas the expected probability of misidentification guarantee smaller than 82 + 6/2 < 6.
Simulation
We conduct experiments to demonstrate that the expected stopping times of frequentist 8-correct algorithms diverge in a Bayesian setting and that the climination process in Algorithm i necessary for more efficient sampling. In Tables [ and [ each column 'Avg'. 'Max', and 'Error' represents the average stopping time, maximum stopping time, and the ratio of the misidentification, respectively More details of these experiments are in Appendix F
Frequentist algorithms diverge in Bayesian Setting We evaluate the empirical performance of our Elimination algorithm (Algorithm I by comparing it with other frequentist algorithms such as Top-two Thommsoo Sampling (TTTS) [Russo] 2016] and Top-two UCB (TTUCB) [Jorrdan and Degenne 20226).
We design an experiment setup that has k = 2 arms with standard Gaussian prior distribution. which means m; & for all i E [k]. We set 8 0.1 and ran N 1000 Bayesian FC-BAI simulations to estimate the expected stopping time and success rate.
In Table I can that the two top-two algorithms exhibit very large maximum stopping time. This supports our theoretical result in Section that the expected stopping time of Frequentist correct algorithms will diverge in the Bayesian setting. We did not check the track and stop algorithm (Garivier and Kaufmann 2016) because it needs to solve an optimization for each round, but the fact that the expected stopping time of the track and stop is at least half of the TTTS and TTUCB for a small 5 implies that the performance of track and stop is similar to that of top-two algorithms. Algorithm shows significantly smaller average stopping time well an average computation time than that of these algorithms.
We include the computation time in the Appendix E3

---

Table 1:
Comparison of two top-two algo-
Table 2: Comparison of Algorithm and the no-elimination version of
rithms and Algorithm !
AVG
MAX
ERROR
AvG
MAX
ERROR
ALG.
1.06 x 10"
2.35 x 10
1.5%
TTTS
1.56 x 10"
1.09 x 10
0.5%
ALG.
2.69 10
1.66
10"
0.6%
TTUCB
1.95 x 10
1.13 x 10
0%
NOELIM
1.29 x 10
8.25 x 102
0%
Effect of the elimination process We implemented the modification of Algorithm (denoted as Nožlim) that never eliminates an arm from A(t) ( In this setup, we have k = 10 arms with standard Gaussian prior distribution, which means m, = 0, 1 for all i [k]. We set 8 0.01 and ran N 1000 Bayesian FC-BAI simulations.
As one check from Table 2 elimination of arms helps the efficient use of samples and reduces stopping time and computation time.
7 Discussion and future works
We have considered the Gaussian Bayesian best arm identification with fixed confidence. We show that the traditional Frequentist FC-BAI algorithms do not stop in finite time expectation, which implies the suboptimality of such algorithms the Bayesian FC-BAI problem. We have established a lower bound of the Bayesian expected stopping time, which is of order 2 <(H)²) Moreover, we have introduced the elimination and early stopping algorithm, which achieves a matching stopping time up to a polylogarithmic factor of L(H) and 6. We conduct simulations to support our results.
In the future, we will attempt to tighten the logarithmic and
max; dgg
gap between the lower
min,
and upper bound, extend the indifference zone strategy for other traditional BAI algorithms in the Bayesian setting, extend our analysis from Gaussian bandit instances to general exponential families, and design robust algorithm against misspecified priors.
Acknowledgements
K. Jang acknowledge the financial support from the MUR PRIN grant 2022EKNE5K (Learning in Markets and Society), the FAIR (Future Artificial Intelligence Research) project, funded by the NextGenerationEU program within the PNRR-PE-AI scheme, and the the EU Horizon CL4-2022- HUMAN-02 research and innovation action under grant agreement 101 120237, project ELIAS (European Lighthouse of AI for Sustainability).
J. Komiyama supported by NYU Stern School of Business Research Scholars Fund no. 10-83004 BF478.
K. Yamazaki was supported by JSPS KAKENHI grant no. JP20K03758, JP24K06844 and JP24H00328 and the start-up grant by the School of Mathematics and Physics of the University of Queensland.
References
Alexia Atsidakou, Sumeet Katariya, Sujay Sanghavi, and Branislav Kveton. Bayesian fixed- budd-budeet best-arm identification, 2023.
Jean- Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi- armed bandits. In Conference on Learning Theory, pages 41-53, 2010. URL http://
Robert Bechhofer. A single-sample multiple decision procedure for ranking means of normal populations with known variances. The Annals of Mathematical Statistics, pages 16-39, 1954.
SSee Appendix F2 for the pseudocode.
10

---

Eyal Even-Dat Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armes bandit and reinforcement learning problems. Journal of machine learning research, 7:1079-1100 -105, 2006.
Peter I. Frazier. A fully sequential elimination procedure for indifference-zonn ranking and selection with tight bounds on probability of correct selection. Operations Research, 62(4):926 942, 2014. doi: 10. 10.1287/opre. 2014, 1282.
Peter I. Frazier. A tutorial on bayesian optimization. CoRR, abs/1807.028)) 2018.
URL http:
7/ /aaxiivorrg/ abs 1807.888111
Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In Peter L. Bartlett, Fernando C. N. Pereira, Christopher J. C. Burges, Léon Bottou, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pages 3221 3229,,222922222 2012. URL htt.sttps::// wttp././Rtttssss//ooooeeeeeooee /ptrtpeed/pprocediingaa htwpoeeeeednnnnnneurrii. neurips.ce wwwpccpppppppaeeccccccccceee /20p2/ 2012/hash/ 3b0226990adddd600000044444444999 -bb.aeapp99---btbaatt.......
Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
Shanti S. Gupta. Selection and ranking procedures: brief introduction. Communications in Statistics Theory and Methods, 6(11):993-101,, 1977. doi: 10110800061192778855554 URL
https: :thpps:/doos htt:///o..orrg//// 00001000000031009778887774888
L Jeff Hong, Weiwei Fan, and Jun Luo. Review ranking and selection: new perspective. Frontiers of Engineering Management, 8(3):311-34,, 2021.
Kevin G. Jamieson and Robert D. Nowak. Best-arm identification algorithms for multi-armed bandits the fixed confidence setting. 48th Anmual Conference on Information Sciences and Systems, CISS 2014, Princeton, NJ, USA, March 19-21, 2014, pages 1-6. IEEE, 2014. doi: 19///09//SSSSS 2014. 61144.68449666
10.1109/CISS. 201..6...11...1..14 4096. URL
Kevin G. Jamieson and Ameet Talwalkar. Non-stochastic best arm identification and hyperparameter optimization. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th Interna- tional Conference on Artificial Intelligence and Statistics, AISTATS 2016, Cadiz, Spain, May 9-11, 2016, volume 51 of JMLR Workshop and Conference Proceedings, pages 240-248. JMLR.org. 2016. URL
Mare Jourdan and Rémy Degenne. Non-asymptoticc analysis of ucb-based top two algorithm. CoRR. abs/2210.05431, 2022a. doi: 445550//RRXIV.220005553 URL /RL.:ttpp:///0..org//.. 10.48550/
ar arXiv.2210.0545 054431
Marc Jourdan and Rémy Degenne. Non-asymptotic analysis of ucb-based top two algorithm. arXiv preprint arXiv:2210.05431, 2022b.
Marc Jourdan, Rémy Degenne, Dorian Baudry, Rianne de Heide, and Emilie Kaufmann. Top two algorithms revisited. Advances in Neural Information Processing Systems, 35:26791-26803, 2022.
Marc Jourdan, Rémy Degenne, and Emilie Kaufmann. An varepsilon-best-amm identification algorithm for fixed-confidence and beyond. arXiv preprint arXiv:2305. 1604, 2023.
Hideaki Kano, Junya Honda, Kentaro Sakamaki, Kentaro Matsuura, Atsuyoshi Nakamura, and Masashi Sugiyama. Good arm identification via bandit feedback. Mach. Learn., 108(5):721-755. 2019. doi: 10.
URL ntttp:://di..rgg /ttp///.....r.....00/////0990000
05784-4
Emilie Kaufmann and Shivaram Kalyanakrishnan. Information complexity in bandit subset se- lection. In Shai Shalev-Shwartz and Ingo Steinwart, editors, COLT 2013 The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, volume 30 of JMLR Workshop and Conference Proceedings, pages 228-251. JMLR org, 2013. URL. http://proceedings.... mlr pww.trppeeeeeeeeee wwt.///afaann...ncccmmoo

---

Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of a/b testing, In Conference on Learning Theory, pages 461-481. PMLR, 2014.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armes bandit models. Journal of Machine Learning Research, 17(1):1-44 -22,, 2016a.
Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification in multi-armeed bandit models, 2016b.
Junpei Komiyama, Kaito Ariu, Masahiro Kato, and Chao Qin. Rate-optimal bayesian simple regret in best arm identification. Mathematiccs of Operations Research, Ahead of Print, 2023. doi: 10. 20.1128/mor..0222.0
www.11287mmorr00000 2022..001
Tze Leung Lai. Adaptive treatment allocation and the multi-armed bandit problem. The Annals of Statistics, (53)):1911 1114, 1987. doi: 10.1214/aos/ 176350495. URL
Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier, An optimal algorithm for the thresh- olding bandit problem. In Maria-Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 1690-1698 JMLR.org, 2016. URL
mlr pttppp///////aaaaalll......
Oded Maron and Andrew W. Moore. Hoeffding races: Accelerating model selection search for classification and function approximation. In Jack D. Cowan, Gerald Tesauro,
and Joshua Alspector, editors, Advances in Neural Information Processing Systems 6, [7th NIPS Conference. Denver, Colorado. USA. 1993], pages 59-66. Morgan Kauf- mann, 1993. model- mocel-sellectoo---errrc--------o www.ooor-rassssisaaaaaaaa -tt.:aaff....ttoooaaaaaammtt..on htt.:/acw......ooooooooooooooooa
httppppppp..appapcco////a/aaaaaa and
J. Mockus. Bayesian Approach Global Optimization: Theory and Applications. Mathematics
and its Applications. Springer Netherlands, 2012. ISBN 9789400909090. URL https://
Edward Paulson. A sequential procedure for selecting the population with the largest mean from k normal populations. The Anmals of Mathematical Statistics, 35(1):174 - 180, 1964. doi:
URL htttggss//dbi..org//00//////oo// 117777033/1777773
Chao Qin, Diego Klabjan, and Daniel Russo. Improving the expected improvement algorithm. In
Advances in Neural Information Processing Systems, volume 30, pages 5381-5391, 2017a
Chao Qin, Diego Klabjan, and Daniel Russo. Improving the expected improvement algorithm. Advances in Neural Information Processing Systems, 30, 2017b.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527 - 535, 1952.
Daniel Russo. Simple bayesian algorithms for best arm identification. In 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1417-1418. PMLR, 23-26 Jun 2016.
Bobak Shahriari. Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas. Taking the human out of the loop: A review of bayesian optimization. Proc. IEEE, 104(1):148-173 2016. doi: 10. 10.1 2494218.. URL /ttptps://aoi.org//.o.o wtt.://////.....////./..... 201. 2.944218
Xuedong Shang. Rianne Heide, Pierre Menard, Emilie Kaufmann, and Michal Valko. Fixed- confidence guarantees for bayesian best-arm identification. In International Conference on Artificial Intelligence and Statistics, pages 1823-1833 PMLR, 2020.
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Gaussian process optimization the bandit setting: No regret and experimental design. Johannes Fürnkranz and Thorsten Joachims, editors, Proceedings of the 27th International Conference Machine Learning (0), June 21-24, 2010, Haifa, Israel, pages 1015-1022, Omnipress, 2010. URI.
12

---

Koji Tabata, Atsuyoshi Nakamura, Junya Honda, and Tamiki Komatsuzaki. A bad arm existence checking problem: How utilize asymmetric problem structure? Mach. Learn, 109(2):327- 372, 2020. doi: 10. 00077/110944-011-0555544-4 URL http:///ob...rg111110////0000000 05854-7
Koji Tabata, Junpei Komiyama, Atsuyoshi Nakamura, and Tamiki Komatsuzaki. Posterior tracking algorithm for classification bandits. In Francisco J. R. Ruiz, Jennifer G. Dy, and Jan- Lan-Willem van de Meent, editors, International Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos. Valencia, Spain, volume 206 of Proceedings of Machine Learning Research, pages 10994-11022 PMLR, 2023. URL httttt::///occeeeiiinnnn .ll 22ees/// tabata23a.html
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-299) 1933.
Yichong Xu, Xi Chen, Aarti Singh, and Artur Dubrawski. Thresholding bandit problem with both duels and pulls. CoRR, abs/1910.06366 2019. URL http:://axxiiv..rrpp abs/19100.62330
Yao Zhao, Connor Stephens, Csaba Szepesvári, and Kwang-Sung Jun. Revisiting simple re- gret: Fast rates for returning a good arm. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Confer- Machine Learning. ICML 2023, 23-29 July 2023. Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 42110-42158, PMLR, 2023. URL www.diinnnn............. https://proocedngssmmt mlr pttpppoeeeeddna....eeee/////000 zhao23g.html
13

---

A Notation table
Table 3: Major notation
symbol
definition
k
number of the arms confidence level
5
means (= (2,, (a),..,,..,))..
H
prior distribution of μ
Hi
prior distribution of μ4 prior density of μ4;
hy
ma,
and standard deviation of h2
N:(1)
Σ [[A.
L(H)
See Definition 2
(())
best and second best
p(p)
alternative model where the top-two means of μ are swapped KI. divergence between two distributions
KL((;))
d(p,4)
KL divergence between two Bernoulli distributions with parameters p and number of draws on arm before time step 320 e| of
N.(1)
( + B
Bo
O
(n RK : (m)
Oij
(n RK :
i (z)
pa (Mai))
the vector projection which omits i-th coordinate ji,j-th, respectively)
Hyp (H.s)
the distribution which omits i-th coordinate (i,j-th, respectively)
Table 4: Notations for the lower bound proof, Section D
symbol
definition
R
Á
32e*
L(H)
v(u)
alternative model where the top-two means are swapped
(,(
E
(T))
W
If maxte[k] &
(H)
32 ma /./
2
(W is the Lambert W function.)
Otherwise
DH(H)
minifj
m.
1
1
-2
20
203
(H)
L(H)
min
Do(H), (H), minse[k]
L H(H)
3264
Im
I(k-1) E.eM
B Proof of Lemma 1
We will use the following formal version of the volume lemma for the proof. The first result used for the upper bound, and the second result used for the lower bound.
Lemma (Volume Lemma, formal). Let Og {u R* 1 (M) i, (14) =]]
1. For any A E (0. 1), define
/
Lig (H, :=
1llp 2 (M)
e.
14

---

Table Notations for the upper bound proof, Section
symbol
definition
(o
confidence bound (Section
UCB(i, (i, t), tC)(i,t)
upper and lower confidence bounds (Section max4E((1) UCB(i, 4( LCB((t,)
Å Amaee (t)
Ao
4L(H)
Athr
min log
AVR 1
DET B
Ro(A)
B log Jogmin(A, Aear)
Aun))
To
(Ao)
(1(
(w) Ms
NiE(H) ( (LCB(i, s wi))n (onnnn 2 mit] (Eq. (4
((u)
Event
Then,
La (H) 1 A, Lag H)) + _A] 5,
(8)
L(H) L(H, A) < HH)
In particular, when ExEN
2. (Volume lemma for the lower bound) For small enough positive real number A
min
1maxic(s) m²? Do(HH) let
1 /
HH, A) A Jeus
1|[m Mol A]i[[ma
dH(
Then,
2 A
A
by H A)
Lig(H (
Lig H +
(9)
E,
In particular, when A
min
Do(H):
L(H
L'H
max
m3
11-11 (e((4)
t
(
Proof. First, let us prove the upper bound of Eq.
18, i.e. (H (H))H) + E.4 A.
Recall for i,j E [k), Oij tu : (n) -i,j" (n) = j}. We have
| 1 Ilm usl dH) =
~c
pay - ha(m) duc II Azi
My
hu (mx) duphi (ليياي(ييي) dps
A
max USYSA
ho(ps + +v)
II (w(ux) danhg (11)) dup keght.
-00
hw(w)) + -1/2
(t hu(ux) duch; (Ky) dبب
<
&i
k
(by the Lipschitz property of the Gaussian density, 1/2 / is the steepest slope of N (m, {?
Ee 1/2 1/2
S A
h((H)) II Keft."
hu (ux) duch, (Hy) duy +
E3
"ee Appendix for the definition of Do
15

---

Therefore, verified the upper bound side of Eq. (8)
For the lower bound, by following the same steps, one can prove Se., [1 M4ll S A dH( 2
(Tay(H) 5. A)
For the proof of Eq. (..b by Chernoff's method can bound the tail probability as follows:
(H) < / [Ime
1
Uss mil
m,l dH(w) 2exp
When my
then we can change the above incquality as:
2VA
1
1
|4
dH
1
1
(H(
1
[4s
mil
dH(H) < <eexp
2VA A
Therefore,
1
1| Ayl= s A]1[|//]: |ay1 -
dH(H) 2
1 1|m4 Mul I AldH(H)
VA
1
|
mil
dH(H)
1
|g 1--my m2l
dH(p)
AVA
Jes
2VA
1
1
2 (H)
A)D - 2 2exp
2 exp
&
8AE
2 A)A
2 (LH(H)
(by A < D)(H))
for A min minie(M) im? (H(H)
C Proof of Theorem 2
For A let (A( (1 R* (1) =1,44 -P)(())) S S... From Lemma have
P Pu~H 1" (w) i, (m) s |]
Σ
PunH ('()) (ij))=ijj(( (x) j. p s A
Σ Lig HH)
jzi
Now, for each IR., let v: I8 + R* be function such that for E [k],
(K)
when s = (1)
v(H)s = (1)
when = (4)
14x
Otherwise.
For any μ E IR*, let let = (J ir (1)) and v v(1). By Lemma in Kaufmann et 2016a for any frequentist 8-correct algorithm = ((Ar),, J), we have
Σ E,N.N,())KLLL (AA.::ALLLCCLDD222PPPPPEEEPPAAA) P # E SE[A]
(10)
For the left side, from the construction of P,
16

---

(m), (4)
(La(le))es)
20
Otherwise.
Since E (0) and from the definition of E()) and (L(E)))) S 6 and (P(((()) 21-6.
Overall, can rewrite Eq. TTP to the following simpler form:
Eu(Ne (Mi (m) (1)(1))) + (x) (1i (10) - (11) 2 d(0,1-1 -8 20
20 20
2d(0,1 1 - -8) [in o² (14:014) ())(1)))
Since 7 = - (T) we can lower bound the expected stopping time when is given as follows:
2d(6, 5) min o3 (Hir (1))
Eulr] 2 (N)N (T)6
(11)
Now, when we compute marginal [m(T] [T] over μa, we have
Eu~H(T [5]
E Eu~H H
Eu[T]]
(Law of total expectation)
2 E H
E [e)())
2d(8, 1 - 8) min of 10((A)
E F
(Eq.
(14-(()) - (1))
12((8, 1 5) ii of 10((1)
2 Em~H
A
CEjni (H) d(o, - 8) min o²
(Engi LH)(H)) d(o, 1 6) min o
2
A
Now since A is arbitrary small positive number, conclude that Ex~ [7] diverges.
D Proof of Theorem
In this subsection, we will prove the following theorem:
Theorem 10 (Restatement of Theorem Let 8 > 0 be sufficiently small such that 8 < (H). For any best arm identification algorithm, if
Σ ne(m)) (E(A)
dH(u)) & Nv,
then
P # Ez (1)) (H 2 8.
Jgt
Proof.
By Lemmal 1 in Kaufmann et al.
2016a]. for any stopping time we have
Σ
(T[[N( 2 P(P)) μ PER* R
(12)
KE
To modify the RHS of Eq.
12
will use the following lemma:
17

---

Lemma 11. For any p.9'. (0, 1) such that q' S 9, we have
In 4(p+
S d(p, - g¹).
By using Lemmal and the fact that (E(H)) 1- PulJ # (*())] by definition, we can transform into
Σ E.(N)))KLL((alll)) In ( + KE
VpeR
(13)
Note that (E(()( is exactly the enror probability, and we are interested in the marginal error probability Ex-H (E)). Let (m)) (N)( and Å is arbitrary small enough positive variable which we will define later on Eq. (19). Then, by rearrangement, we can induce the following inequalities
f PulJ # (H) (H)
ΣΣ
PAlJ # (H)
KE[A] jæi Be
PulJ #Q)H(M) ΣΣ/ JE(M] (Øj Oy
/
Pu(m)(] + slha(1y))s(s))
II (us) efii
dje
2
Jas
iE(M) jæi
(Symmetry of the Lebesgue measure)
= 2
ΣΣ
Puly # ()((()))))()) + Pu # ()
II ho((e) att.j
du
iE(M) jæi Gis
PulJ # (x)) + PP
# (r(()) min (h, (1s (g
Σ
due
K i 0.j
2
(AC BD 2 Amin(C, D) B min((, (A B) min for A, A,B,C,D>
exp (nn 13) ny (L) (4) min (1, (e(
ΣΣ
h h=(H))y((ug) du
8
h,
KE(M jii 0.
(Eq. 13
exp (nn:(H)KL (4s. nn (L) (pg.
2 le Σ
1elll S
dH (p)..
KE[A] j7i O.
/
A
(Lemmal
12
For the last inequality, we used the following lemma. The proof for this lemma is found in Subsection D.1.2
Lemma 12 (Ratio Lemma). For all a, b IR which satisfy la bl s (H and |a), |b| v (H)
for some fixed (H
(a) (, 2 -4 for i,j E [k:]
In short, we have
Pull # 1" (H)] (H)
exp exp (Mnn((()KTT mz) -
2 e
|uol A
aH(
(E(A) Jæl O.
8
(14)
DD, = min
m.
-2
20 7
26
18

---

and the following statement is stronger statement than Theorem 10
If (( (H( S Nv, then (RHS of Eq. (14) 2 6.
RHS of Eq. (14) is represented terms of n == (m1, .. nx IR - [0, oo) (the expected number
of arm pulls) and does hold for any algorithm given n. To prove the above statement, since 'set of all expected number of arm pulls' is a subset of (n R - [0, oo) }. it suffices to show that the optimal value V of the following objective
Vmin
inf (0,00(0.00)+
V(n)
(15)
/
Σ mo((e) 8=1
(H(H)) S NY
s.t.
R²
exp (xp( m2)
KL)
where V(ñ): :-)==
Judl. s
dH(
8
greater than
Let G,₁ = (u E O1g lus - -usl A, lusl S Vá
Mll
Then, it holds that Vmin > Vinin
Vá
where
Viuin =
inf
(i(
(16)
RiRk (0,nc))
s.t. ΣΣ
Σ mo(H))
dH(w)) S Nv
kE(M] 1z1 B.
(xp(-fx(4)KLL M2) -
where Vi(nt) = e
(H()).
8
(E[K]
To see this, suppose á is an optimal solution to 15 Then, by the constraint of optimization
problem (15 Jgx Exejs (n((t)) (H) S Ny and since is a collection positive functions,
Enjeph Jesuue (Ix=, n((()) (H( < Nv. which means â satisfies the constraint of (16).
By the minimality, Vmnin < (ñ),, and since exp is a positive function, we have (ń) & V(ñ) Vmmin
Moreover, Viuin 2 V/min holds for
Vimin
inf
(17)
R:R -0,
S.t. ΣΣ Σ (H(
dH(p) s Ny
1E(A] 1 S.y
(-(ū((10)+ + +ū,(1))
32 dH (1))
exp
where V2(nn ==
8
by using the fact that KLa(14, 14))
< 2 2min (
A2
20
19

---

Claim 1. We abuse our notation slightly so that (()) 5 (H) for any Lebesgue measurable E, and let é U2, Gig (note that all O. are mutually disjoint except for the measure zero sets). Then, the following opt is an optimal solutions (17)
ng (1) = Nv a (Ujze u (Urss
(H)
Proof. Choose an arbitrary ñ R + [0, oo) which satisfies the constraint of optimization problem (7). Let (HL)= == Ex((N) (s()).. Now, since the function p x + 8R exp(-x say that 2 2min(0;))e(e) is
Á2
convex and decreasing function, by Jensen's 's inequality
Ve(n) ΣΣ
p (f + =n((w)) (H(
kE(M] jti
Σ H(Ob)p
H(Ois) Ja,, (Me(m) + +nz(t)) (H)
kE J#
(Jensen's inequality for each integral on θ.y)
= -H(O) ΣΣ H(),))
(E|M) iti H H(Or)) / (Ns(()) mn(()) (H
(Oij))
2 H(())
(m.(m) + +n)(m) (H
H(²) H(Ois) J0g
(E(A] i&ز
(Jensen's inequality)
> H(Ō):
ΣΣ
Σ n dH(u)
KEiA iti H(O) J. (E]k
(ñ4 + no S >>.
EeE(h]
and is a decreasing function.) ns
Nv H())
2 H(())
(Constraint of
Since ñ is chosen arbitrarily, we can say Vinin 2 -H())
Ny H(@)
One can check the above n opt
Ny satisfies the constraint in the optimization problem (17 and also satisfies Va(n H())p(
H(
Therefore, nt is optimal solution of optimization problem [1
Using Lemma we can get
H(Ō) =
1les
Psl <
[]1[ lngl < (H) ( (H,
(18)
*f Og
Now applying Claim T and Eq.
18 on Optimization
17
implies the following result:
mimin
(Claim
Ny
A minn
exp
2L A) A) minn
1[[m pyl []]([m (ugl S JA (14)
8
Jeg
(Eq. (18)
Nv
exp
2 mmin(o?) L'
x I! Á)Â
(Eq. (88
8
If V < 6 is true, then 1/2 < 6, which implies
20

---

Ny A 2 min L/ (H,A))
exp
min o. NE L' L A)
L'(H,
X (H, A) +
+ Nv 2
In
Se
88
To make this lower bound greater than 0, In ('H 85*6
1. From Lemma we know that for small
enough 1 ()) (HL(H), Setting
32c
Â =
(19)
L(H)
we have
L
Nv 2 min(o,))
In2
(20)
16e4
which is the inequality we desired.
L
D.1 Proof of Lemmas
D.1.1 Proof of lemma
Proof. It is equivalent to prove p + q 1 {exp(-d(p, d))) 1-)11)))) for any p, q, (0, such that
of S q. First, if 2 1/4 2 1/4 4 it trivially holds, and thus we assume < 1/4 and 1/4. We have
d(p. 1 o dpp 1) 9)
(p. 9 S }
$ d(p + q; 1 - (p + 4))
(p+ g < !
log 2.4(p + q)
(Eq.(3) of Kaufmann al. [20
and transforming this yields
(d(p.1-9')
p+q² 2.4
This completes the proof.
D.1.2 Proof of the Lemma 12
Proof. We have
(b(a)
(a mm
(b mm,)2
(b 16-10 mm;m)
(a (a-ma) m2)
exp ha(b)hz(a)
20
20
20²
203
(a (a + b 2m;)
(b - a) + b b- -2mm)
exp
20
20
exp
2(a b)
m7
0
m2
2
(a b)(a + b)
20
1
+
20
2 exp
22
M
m
1(a
b)(a + b)
a?
20
20
2 exp
-28
m;
m-
2
+ R, (H, 20
1
o
20
Define R'H mingy Ry (H, 8) which satisfies the condition of the Ratio lemma. For 8 such that
< Di = min
m;
m,
1
2
0
20 3
20
L(H) Ä < min DH(H), minje(k] am? uck EiE()) +
Check Section G for the condition.
21

---

we have ( Se e
E Proof of Theorem 6
For notational convenience, define (,( := (r)()) - μe for [Re, A()) : min A,
(u) Let A(l) be the subset of arms that have not been eliminated at time
Since 8 < Eic 4
(H)) Do
5
1(H) and we have
AL(H)
Exe())
I
PAnH(AO 2 A(H))
Σ)
1l - Hyl & Aol (H
inf
=I(H, Ao) S 2T(HH) Ao
(Lemma
6
$ 2
(21)
Next, consider the upper bound estimator such that (tale(t) A holds with high probability. Namely,
UCB(i, LCB(i, = (t) + Conf(i, t),
Conf(i, = 20 log(6( (()((())) )m²))
26
N.(t)
Å safe (t) = max UCB(i, - max (j.(j.t).
From the definition above, we can calculate how many arm pulls the learner needs to narrow down the confidence width.
Lemma 13. Define B = 320max;E[N] of and Auh min (log AVT BB. Let Ro(A)
B Jog minl A Amtr) Then, for any A E (0, oo) and for timestep & which satisfies N.(t) Z (A(A). min(A, A..))
Conl(i, A/4.
Proof of Lemma 13 nience. Then,
Only for this part of the proof, let A' == min(A (A, Athr) for notational conve-
(og(6(N.())//(())))))))
Conf(i, t) =
20? Ni(t)
(og( (2)((()))))))))) (A)² /(( TT²)
207
(assumption on /)
Ra(A)
log(6(B log(A' (111
))7))
A /208 20?
A
2T
B log A A/11)
log(6( (6( B )2/((((()
21 m))
$
207
A7s
(log 1-1 < <A-11
Blog( (~1))
6 Glog(4 A- ) + 2 log B log 12k 87
20
Blog( (-11)
2
A' 20
+
+
(Definition of Aphr, Auhr 2 A')
B B B
A
200?
< A A.
22

---

From this lemma, one could induce the following corollary which states that Algorithm 5 always terminates before certain timestep:
Corollary 14. Let (and ?) be the stopping time (and the last iteration of the while loop in Algorithm [] respectively) where Algorithm [ meets the stopping condition. Then, y is always bounded by (D)) and T is uniformly bounded by To = k Ro (Do)
Proof of Corollary 14 Let us assume that T > To + 1. Then, by Lemma 13 each e
Ar satisfies Conf To) I 4o/4. Let juc arg A())EA(() LCB(i, t). From definition,
arg max))(()) UCB(i, t) and glob(t)
A safe (Tb)
Aaao((T)
iEA(Te) max UCB(i, To) max LCB(i, To)
(ELA(T))
UCB(i" (ith (Tb), To) LCB( (To), To)
2Conf(i (To), To) + 2Conf( jeb (Tb), Tb) + LCB( (Tb) To) - UCB( (To). To)
S An + LCB( (To), ( To) UCB() To)
Ao
(Since both arms survived from the elimination phase)
which implies saae < Do. contradicting To since the algorithm should be terminated by Line 18 at timestep To. Therefore, 7 S To-
Lemma 14 implles Algorithm aaways stops before To samples. Morever, the following lemma states that with high probability, true mean fu is between UCB and LCB for all time steps.
Lemma 15. (Uniform confidence bound) The following holds for all i [A:]:
82
P p
(LCB(i,))
& m1 2
(22)
2k'
21 82
TP,
n (iu S UCB(i,
(23)
2k
Proof of Lemma 75 The following derives the upper bound part, Eq. derived by following the same steps.
23
The lower bound is
Since each arm is independent of each other, Eq. 23 boils down to prove
8²
{ps UCB(i,t(())))
2 1
2k
where (.(s) minft E N:
=0. For each event {u: < (C)):( since each arm pull is independent of each other, by Hoeffding's 's inequality we have
Nt)t) 2 $) and (s(s) of (t N,(t) 2 s) =
SE2
pa) -e < exp
20
for any 0. If we set = (s)), transform the above inequality to
82 6
(UCB(((, (s)) S m4) <
2ks
n
By the union bound,
P
(u < UCB(i.t((s))
>
P [1: UCB(i,((s))
23

---

82
6
21
2ks
n
==1
82
6
82
2
2ks
77²
2k
and the proof completed.
Let us define good event based on Lemma 15as as
(n (LCB(())) s m²)
>a(nnnn (UCB(1, 2 mi) ]
x(1)=
n VE[A]
(24)
We now prove that, under Hy and under this good event X' (14)
The best arm i" (1)) is always the active arm A(t) for all (Lemma 16).
Each count of the suboptimal arm pull, NT(T)), is bounded by roughly O log A. A7
(Lemma
17..
Lemma 16. Let
X'(x) = n (i())) E A(t))
Then, under Hy, X()) C (1a) and therefore
PA (1)() S
Proof of Lemma 16 Suppose that event X(1) oceurs under Hy, Then for all E [K] and for all t, i4 Conf(i,t) S μr and i. + Conf(i, t) μ4: Now, for any + i",
LCB(i, UCB(I" t) fs Conf(i, t) - (fu- + Conf((",,)) μ4 + Conf(i, Conf(i,t) (pr- Conf(i", ,t) + Conf(i", t))
(Event X' occurs)
#4 μ3 <0 0
which means when event X occurs, the optimal arm will never be dropped, and thus X C X' By Lemma [5]
(x)( 2 (x(()) 2 82.
Lemma 17. For any i + i", under Hp we have
(No(To) (m Ao)) X(H))
(25)
and therefore, EN((N(() < Ro (max A,, Ao)).
Proof of Lemma 17 Only for this part of the proof, let T; := Ry (max((A, Ao)) for brevity.
When A < Ae. max( A,, Ao) = -A. which, combined with Corollary
14 implies that
(N,(T)) 2 7.} always holds.
For the case of A; > Ap, suppose that the learner under the events X(4) and {i E A(T:)). Note that
Conf(a, Ti) < Ai
Va E A(T:).
4
Then,
max LCB, (T,) - UCB,(T) 2 (CBB-(T) UCB((T) eEA((T)
24

---

Rs Conf (Ti) - (f: + Conf,
Ht 2Conf, (T;) (ys 2Conf,
(A' occurs)
A; = 0.
Therefore, when X' occurs, μ4 should be eliminated after timestep T, so N.(To) s T.
Lemmas 16 and 17 guarantee the Bayesian d-correctness of our Algorithm |
Theorem 18. (ó-correctness) The Bayesian PoE of Algorithm T is at most 8, i.e.,
[
PoE(u) (H s
(26)
Proof of Theorem
18
Throughout the proof, we use the following results.
The probability that (4)(()) - (w) S Ap is at most by Eq. 21
The event X' fails to hold with probability at most d² by Lemma 15
When (4*(w) (g*(2) An and event X' occurs, by Lemmas 16 and 17 all suboptimal
arms will be eliminated before T and only the optimal arm will remain in the set. This means E()) C (()) (p)())) (w) Ao).
Therefore.
PoF(m; ; H) = E
P (1) H4)) E [[I(E())))HHL)
< E
B|I(fHir(m) (b)(()) S A +
< H
[(tHir()) (b)(()) S A - -
1 + 82 <
Finally, Lemma 19 shows the upper bound of the expected stopping time of our algorithm.
Lemma 19. We have E[7] < Bo L
log L(H) + O(log 5
Proof. We have
k BE N. (To)l
B Σ E[N.
E (TT)
Σ E IN
[. + TTo-6
(Corollary 14 and Lemma [5]
and since Ag < Aghy by assumption,
log A 82
To 52 - Ro 80 $ kB
(27)
A
Therefore, remains to compute the scale of the first term, Σ (N
25

---

The following evaluates E3 (To for each i. For notational convenience, let Ts(p))
Ey Ro(max (As, Ao)) 1 X (1))] Then,
E [E,, s [[T)(
(Lemmal 17
(m 9:]]
Σ ==1 HEB;
Te(H)dH(u)
(28)
(Recall that O; = {u R& Juee, Ta(p) (H). By assumption, Do Athr-
max In the following, we calculate each
For this part, we define a new notation that for each vector v E IR and i.j E [k], Vi (and wiy)) is the projection of e to R+-1 (R*-2 respectively) by omitting i-th coordinate ji,j-th coordinate, respectively), thg = (V1, 12, .. W--1, "1 ,y.) Similarly, for a k-dimensional distribution H
R- coordinates
and i.j E [k]. H (and H. High) is the distribution which omits i-th jith, respectively) coordinate.
Case 1: s + In this case, by Lemma 17
To(H) (H)) = =f Ta(M)(1(u4 - Ma 2 Dol + 1lm us < Dol) dH(
WEB;
NEE,
pli
(o( (Hs) dHt dus du
JHER M(LrE(-OoM1))
+
(1i dH dH dus du
JUEB Ma Aetrr ((s.E(-
+
To Tz dH due du
J4ERR Mo=p: Do Mas.el-oom
log A -1
B
thr
Urr
An
log(14 (4))
+
me(ui)h dH vse ducs das (1i )1,)2
JEER
Dehr Em..Ee--oo.pp
14
1
log A7
+
B
holmy)h dH Vins duc dp
A
EEER 1o Do M(,.E(-
(Lemmal 17
Do
log(14 (M0))
B
h(lmg)hoHm)
II Ha(p)) du du
(1i - -11a)²
14 16, 11, Achr
+ B log
log A thr
((i = =i Mo S Do) + B.
A2
<B log A /
ho(Hs) | p4i-
J (M4 Mea)² ho(Ha)
II Hel()) due du
H.ER
(A)
26

---

+ log A
log A Ahr
P(i P(i(()) = i, 1,14 - M4s S Ao)
+ +B
thr
(Pu)
We first deal with the term (A). The following splits (A) into the sum of two integrals (A1) and (A2):
J
Pi-Ao
(4) = hi(m))
II kETRMMA.s
(Hr M₂) he no((ss djes dus
MLER
p-==00
2020 1-1
mi p 120
h((ms)
II Hu(m))
(0=m--(4114) (Mi us) (o(( dut dui
MERR
1=1
(41)
+ f (x(ss)
Me
22/00 140
II Halms)
(14 - o=,) les (1s) dns.
HIER
AEIG)MEL,s)
#-=-00
(42)
For (A1), have
2/20
/ h((u)
p - -oo
(A1) S
Σ
II (m((s)
h (1s) dus dup
MLER
1-1
(M) [1A0. (1+ 1)
PAJ
2020
2P(i (p) =i,4- 14:44 -4 S Ao)
(Lemma 20
PA
00
2Pr.
P
1=1
2
P...
(29)
3A3
Now for (A2), we evaluate the inner integral of (A2):
1
2/20
1Ao
(14, m,)²
[Inner
A2)
(44 11)2 exp
V2TO,
20
-00
1
(Us m2
2/20 1A0
exp
V
(1:-
20
-00
2/00
10
Ms m
exp
(1ls
m2)²
dps
2
03 v6s
20
-00
(partial integration)
1
1
2/20
14 m3
-1) exp
(1+ mma²²
djts
V2TOO,
2/An
1o
v
2
#4 1ts
20
(1u > (aa)
27

---

1
20
Ao
μ1s mg
( ma)²
exp
due
V2TO,
A40
2
A
20
2v
2vAu
1
14
m
+
max
0
VTTO,
A
Ao
2/50
2/200
By integrating above over variable we have
(A2) < / he(me)
II
Halme)
1
max
1
14 mg
du
V2TO,
1
0
Do
AE(MI
2v300
2v
< 1 hz(me)
+ max
14
my
dps
(F&(+) 1)
V2TOo
Ao
0
A
2/230
2v200
1
1
[/e hns(us) max [uc mss 0] duc
V2TT,
1o
031
Ao
2/Ar
2v
1
1
[/e h:(p:)lu malday
V V2TO,
1
A
03
Ao
2/Do
2/2n
1
1
[/ [ni(p)) - mi) + Imm msl) dus
V
2TTO,
Ao
03
Do
2/A0
2/An
1
1
ØiV2 VT
(mm4
ms
V
/2TT
A
0
A
2/Au
2VA.
(Mean of Half normal distribution is 2.v2
+
1
m+
2:v2 2 m2l +
See H
0
(30)
Do
VTTo,
03
A
2//3o
(Hr(H
Therefore, by Eq.
and Eq. (30)
1 T2
(A) (A1) + (A2)
P.. + +0A 13)
A
3
and therefore
I weB:
T.()ddH(
B log A7
Pi
+1
+ 0(45111)
(31)
A
3
Case 2: = In this case, let
J yEe, To(H) dH (m) = _/ TH(H)dH(H)
i4s mEO.;
Σ
max (Ti(H)) igs
itts uee.; (N, increases only when [A 1, so there should be a competitor)
Σ
max iss
(a(A)( Ao)] (H
(Lemmal 17
HEO,,
Ro(A)(H), Ao) dH(
j mEB,,
28

---

and by the same calculation as Case 1, we obtain
J,CO,, [o(A,, Ao) du _ and therefore
B Blog
A 1
Psj
T²
+
1
+
+0(4
A
3
J JEEe To()ddH dH dH (n) <
B log A -1
π
P.j 0
(32)
A
x² + +1]
For notational convenience, By B
From Eq.
28 Eq.
31
Eq.
(32)
we get
3
(Zo)] EULH [ulN(((6)1 BU (1,
(33)
4 Σ
$
Te(R)) (H( + EE [TT
(Eq. (28
1m1 MEO,
(e(H) /
T. EnLH (BNNN(/)NNNNN
uEB.
igf HEO,
Bo log A -1 A6
Σ
Pis Σ Paj
+ +0457 + B Bg((N((T)
f
(Eq.
and 32
Bo log A 1
((i &, ns I Ao) PPi 8, 1b (1) S
Ao)
A8
10A 1/2
RUTH B. [[N(
(34)
Now, the total stopping time is bounded as follows:
(To)
Bo log A, 1
Σ (((i(()) # 8, (,1 14.
Ao)
Σ P(i (1t) 8, 8,1s (13-(1)) S Ao)
A
Peum
Psum2
+ +(A5)12) E[
(Eq.
64
The final task we have left is bounding (Psum1) and (Psum2). Let us define k² (/4) the third best arm μ. For (Psuml),
(Psuml)
P(i (m) + (.)()( Mo S Au)
P(j (n) (, - us < Ao) + P(i + 8, s, Mo S Ao)
< {((p)) - ())(m)) & Ao) + Σ P(ur(u) - (k-(m) S Ao)
(When j" (11) # 8, (2) 2
29

---

8
+ k. P() Mp)(()) S Au)
(Definition of An)
2
8
2 + 0(4g).
(Lemma 21
For (Psum2),
(Psum2)
((( = 8, (H-((a) S Ao) s=1
= P((r p))(1)) S S
6
= =P(A()) & Ao) S 2
(Definition of An)
and finally we can conclude
Bp log A
B|r] v
8 004, + [[[1[
(Eq. (Psuml) and (Psum2))
A
Bo log
A7
KB A 82
8 + 0(4
1/3)+
(Eq 27
A
A
By log
A
8 044 1/2)
(35)
A
and the proof completed.
E.1 Bound that holds for any 5
In this case, need to change the definition of Do
o) & 2
Ao == min max A (0. ((H
minn(:L.;)) (H))²
(36)
itj
Assume that Ao Ashr. Then, all the proof flows of Section E after Eq. and we obtain the following upper bound:
follows accordingly,
Bo log Au
2 2i4g S,y
KB log A
log A.t +22 Bo log A-1 thr Ahr
B[r] <
8 +
8² Bo
+
Σ ifj
Qisk
Aoo
A
From (Psuml)
(37)
where Siy and Qifk defined in Eq. 330 and Lemma 21 respectively.
Eq. (37 also holds the case of Ao Z thr In this case, from the definition of Ro, we have
(p)) = En Ro(max Ao) 1[2] E2 [Ro(Aen ]1[]]] & Ro )P = Ro(DeNr).
which implies
[ < k. Ra(Ashr) ) To 52
k. Ro ((hr)) -(1 (1+ 82)
(To A Ro(Ao) Ro
Bo log A Ahr.
(1+
2
thr
Bo log thr
2k
Eq. 37
2
In summary, obtain Eq.
37
30

---

E.2 Proof of Lemmas
E.2.1 Proof Lemma 20
Lemma 20. For S + S va and for (G.4,,HH) we have
(() i, p4 - ns [S6, (S 1)8] 21 (1) ii 1:-- us S 8).
Proof. We have
1 e.
76.(541)
1 1| psl E [S6, (5 + 1)8J (H
JB.. M4 ha(m) dus (H(
1/2
$ je he(H))) + &, (S (H,,)))))
(by Lipschitz property of Gaussian, e /2 is the steepest slope of N ((,; (
1/2
= 5(
h((m)d (H(
+
(S + 1)8)
&
(H(HH)
S (H) + - + 1)006.
6
When 8' 11< 1 and v8 < Lis (H) we have V8
/ 1 11m4 Myl (S6, (S + (H)))H(())) s (H)6
as intended.
E.2.2 Proof of Lemma 21
We will show that the probability that three or more arms are 8-close O(82). Namely: Lemma 21. We have (())(()) (k)(w) Ao) (
Proof. For any # $ [k),, we have
f [1m - --ylllls - pal S dH)
= =S p1488
prito
hy (4y (e duu dp, dH (1(()))))
Mige MS=MI 1
Mige M1 - - m
puit8
puito
hns(mt+ + --120) ) (malme) + e -128"
dua duj dH (wirk)
E
Ex
(Lipschitz property of Gaussian)
< (26)² (ns()))a(m))) + 0(8)] dH (M)))))
=:QuA(H))
Experimental details
The code used in the experiments for this paper can found at the following link: https:// /// cattuu.comjajjjjaae Baaiii/annnnaBBBBBaaaaeea
31

---

F.1 Stopping condition
TTTS We use our theoretical results stated in Section 5 for our stopping criterion. For TTTS, we Chernoff's stopping rule, as Garivier and Kaufmann 2016 Jourdan et al. 2022] did. Here is the description of how it works: for each arm i, E [ki].
let
(t (t(() NO(1) + N2(1)
N2 (.(t) + N:(1) + N₂(1) Pt()).
and define
Z,(() = N.(() (L) +2(( (Ls(
Now the stopping time is defined as:
TTTTS == inf E N max min (a) 2 ((1,))
ae(k] (e]]
for some threshold function (tt, 5), which is defined by the following proposition of Garivier and Kaufmann [2166]:
Theorem 22 (Garivier and Kaufmann 2016 Proposition 12). Let μu an exponential family bandit
model. Let 5 (0, 1) and a > 1. There exists constant C' = C(a, k) such that whatever the sampling strategy, using Chernoff's stopping rule with the threshold
Ct
8(t,6) = log 8
ensures that for all μr, (T 00, (0. 6.
In this theorem, we give an advantage the stopping time of TTTS by setting 1,C 1. Theoretically, C(a, k) 1 and C + oo as a + 1+, but we set the threshold smaller than the theoretical guarantce that TTTS stops earlier.
TTUCB We followed the stopping rule of the original paper Jourdan and Degenne 2022b Let 2A-2A +og(4))++og ((2A) 0.5 log( 1)))+ where is Riemann ( function, and
Ca(x)= == min
1 c(n, 6) 2011, log
k 41o((4 + log ")
Let i, == arg max (t,))), the empirical best arm at step t. The TTUCB algorithm stops when
min ic(1) P.(()) 1o (0) + N.O
2 Ve(t,8).
When the algorithm stops sampling, the TTUCB algorithm recommends the empirical best arm as its final suggestion.
Since the computation of Ca(x) involves optimization, it is computationally heavy when the number of samples is excessively large (as our Table 1). Instead, approximated Ca(x) Re + log as mentioned in Jourdan and Degenne 2022bb.
F.2
NoElim algorithm
The NoElim algorithm shown in Algorithm 2
F.3
Tables including computation time
For all tables in this section, Comp represents the average computation time (second).
32

---

Algorithm 2 No Elimination (NoElim) Algorithm
Input: Confidence level ó, prior H
Ag := 2L(H)
Initialize the candidate of best arms A(1) [k]
t ==
while True do
Draw each arm in [k] once.
[Main Difference with Algorithm
1+t+ AA(t) for i A(t) do
safe (t).
Calculate UCB(i, t) and LCB(i, t) from (5)
if UCCBii, S max, tC then
A(t) < A(t) fd).
end if
end for
if [A(t)] = then
Return arm J in A(t). end if
Calculate safe empirical gap
if s Ao then
Return arm which is uniformly sampled from A(t).
end if
end while
Table 6: Extended version of Table | with computation time.
AvG
MAX
ERROR
CоMP.
ALG.
1.06 x 10
2.35 x 10
1.5%
TTTS
1.56 x 10
1.09 x 10
0.5%
27.6
TTUCB
1.95 x 10
1.13 x 10
0%
5.07
Table 7: Extended version of Table 2 with computation time.
AvG
MAX
ErROR
CоMP.
ALG.
2.69 x 10
1.66 x 10
0.6%
1.59
NoELIM
1.29 x 108
8.25 10?
0%
5.5
F.4
Additional experiment results
Multiple arms, different prior mean/variance
In Section 6 we only used k = 2 arms for the simulation of Table I We made brief comparison between A Algorithm| [ and TTUCE in l: = 10 arm environment with a prior distribution where prior means and variances all different.
Number of arms = 10
Prior means: we sample 10 random numbers from (00, 1) before the experiment starts, and
set them as prior means, Here is the list of prior means: [-0.053 0.528 -0.332 -0.368 -0.273 0.909 0.418 11.17 0.873 -0.405)
Prior variance: we sample 10 random numbers from Unif (0.5, 1.5)) before the experiment starts, and set them as prior means. Here is the list of prior std: [0.604 1.477 1.163 0.988 0.560 0.513 0.997 1.332 0.828 0.833]
Instance variance: we sample 10 random numbers from Unif( 1.5)) before the exper- iment starts, and set them prior means. Here is the list of instance std: [1.498, 1.262, 1.485, 0.963, 1.375, 0.969, 1.357, 1.238, 1.088, 0.699]
Number of experiments: 500
33

---

We stop additional sampling of TTUCB when its number of samples is over 10t because of the time constraint. This means we gave some "advantage" on TTUCB about expected stopping time (since it makes TTUCB stop earlier than it should.)
Result Our algorithm had the average stopping time 1.1 105, while TTUCB had the average stopping time of 7.1 10", again proving the superiority of Algorithm over TTUCB in Bayesian settings.
Table 8: Multiple arms.
AVG
MAX
ERROR
CоMP.
ALG. TTUCE
1.1 10
2.58 x 10
1.5%
1.52
7.1 10
10 (CAPPED)
0.1%
6.22
F55
Miscellaneous
Computation of Ao
From Definition
2
Liy(H) { (x()))(())
II
H,(x)
In Scipy package, there are functions for computing the cumulative function of Gaussian H2 (scipy.norm.co cdf) and h; (scipy.norm.pdf) Scipy package also supports the numerical integration (scipy.integrate.quu quad) which we use numerically compute Lij in our experiments.
Codes The codes are in the following GitHub repository: http:://github.com/jj8...
FC_ BAI Bayes
Hardware We used Python 3.7 as our programming language and Macbook Pro M2 16 inch as our hardware.
G
Scale restriction on ó for each theorem
The second result the Lemma 9 is used for the lower bound. For this result to hold, we need the following two conditions for Di:
Proof Lemma
second result: For the proof of Eq. we used |m,] S
2VA
Proof Lemma second result:
For the proof of Eq. we used
1 2
2 exp
+ 2 exp
To satisfy this condition, A Do ()) where
SAE?
W
32 max 872 If maxxe[]] &
62
Do(H)
2TL
Otherwise
Here W the Lambert W function with the principal branch.
For the lower bound proof, consider sufficiently small d subject to the following constraints
32c4 8:
L(H))
Two conditions above for Lemma 9
For the Lemma 12 Â Di ( min
m
-2
20
20
To make L'(H, ÁJ E (L)
Á
L(H)
4 EiEM
E-r
34

---

In summary, Theorem holds for any
L(H) 32e
L(H)
8 8 ==
min Do Di
min iE(k] 4m
4(k
1) 1)EGE(K SE|K &
For the upper bound proof (Theorem 6). we consider 8 such that Do AL(H) conditions:
satisfies the following
A
Eiem k-1 make L(H, Ao) Ao (H) by the first result of Lemma &
L(H)
Ag S (Lojs) for the proof and usage of Lemma 20 and
Ao < Athr.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We accurately present the paper's contributions and scope in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We present our limitations and possible future works in discussion and future works.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-speciiiiatinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
36

---

Answer: [Yes]
Justification: We provide the full set of assumptions and problem settings in Section and Appendix G Additionally, we include all the proofs in the Appendix. Throughout multiple revisions, we have ensured the correctness of our proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results, All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We provide all the experimental details in Section 6 and Appendix Addi- tionally, we provide our code facilitate the reproduction of our results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
37

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
We provide open access to the data and code with sufficient instructions.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niis.co/
public/guides
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips.cc wwwpccccppcccccccc.cc.c.ccc..ccl poublic/guidese guwdes/ Suse//ooeeuuiiic..c ss wwwssssssssooooo inolciyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We specify all the experimental details in Section and Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In Section we provide average stopping time, maximum stopping time, and the ratio of misidentification report our result statistically.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
38

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the full information on the computer resource Appendix F In addition, we provide the full table in Appendix F to present time of execution.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httttp/://eerrrip.ccc//p/////eie
Answer: [Yes]
Justification: This research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
39

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This work poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
40

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
41


Reviews:
[{"review_id": "fnzKnNY4cS", "reviewer": "Reviewer_jd9J", "summary": "The paper studies the problem of FC-BAI; the goal is to find the arm with largest mean with a given probability of correctness. It analyzes FC-BAI for a Gaussian bandit model where the arms reward mean is sampled from a known prior and the reward variances are known. It proves other (frequentist) FC-BAI algorithms could fail at this setting. Then it proves a lower bound for the sample complexity of this problem. Finally, an elimination algorithm is introduced which is near-optimal. The main difference of this algorithm with previous algorithms is in its less conservative stopping criteria, where it stops if the remaining arms have small enough optimality gap.", "questions": "1. In Thm 4, the constants in the lower bound seem very small ($\\frac{1}{16 e^4} \\approx \\frac{1}{2^8}$), so it could entail a trivial lower bound in most cases, specially since it is the lower bound to the sample complexity (natural number). What is the actual value of this lower bound in some of your example simulations?", "limitations": "Yes.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "*Soundness*: the paper clearly defines the problem, introduces a lower bound for the problem, theoretically proves the sub-optimality of previous algorithms, and conducts simulation studies along with ablation experiment.\n\n*Presentation*: The paper provides all the proof sketches and pseudo-codes required for reproducibility of the results. It efficiently uses its notation and avoids overloading symbols.", "weaknesses": "*Contribution*: The paper considers a small subset of bandit models, Gaussian reward with know prior and variance. This limits applicability of the algorithm and theoretical results. As also mentioned in the discussion section, it would be great if they could generalize the algorithm to deal with misspecified or under-specified prior (see [1]), or unknown variance.\n\n\n[1] Azizi, J., Kveton, B., Ghavamzadeh, M. and Katariya, S. 2023. Meta-Learning for Simple Regret Minimization. Proceedings of the AAAI Conference on Artificial Intelligence. 37, 6 (Jun. 2023), 6709-6717. DOI:https://doi.org/10.1609/aaai.v37i6.25823.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are truly grateful for the encouraging evaluation and valuable comments. The following is the response to the question you raised.\n\n>In Thm 4, the constants in the lower bound seem very small ($\\frac{1}{16e^4}\\approx 2^{-8}$), so it could entail a trivial lower bound in most cases, especially since it is the lower bound to the sample complexity (natural number). What is the actual value of this lower bound in some of your example simulations?\n\nWe agree that our lower bound tends to be much smaller than actual values. For example, when $\\delta=0.01$, for the instance in our Example 1 ($\\mu=(1,0.9,0.1)$), the sample complexity lower bound is 0.0468, smaller than 1. However, the main objective of our lower bound is to check the order of the sample complexity. Through this analysis, we found out that L(H) is a crucial variable in designing the algorithm, and we were able to propose our Algorithm 1 which is optimal up to a logarithmic factor.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tJpqBYm7Go", "reviewer": "Reviewer_EP71", "summary": "In this paper, the focus is on the fixed-confidence best-arm identification problem within a Bayesian setting. The objective is to determine the arm with the largest mean with a certain confidence, given a known prior distribution. Existing work in FC-BAI is mostly in the frequentist setting. This paper shows that the popular algorithms used in the frequentist setting are not optimal in this setting. Additionally, a lower bound for this setting is derived, using a sampling complexity constant and the confidence level. Lastly, a successive elimination method that matches the order of the derived lower bound along with experiments comparing the performance of popular frequentist algorithms and this algorithm are presented.", "questions": "- 267-268: In Remark 3, can the authors explain if in the general case the result matches with the lower bound?\n- 309-313: The authors state that the expected stopping time of the track-and-stop method is at least half of the TTS and TTUCB methods, which according to Table 1, is on average at least 300. This number is less than that for Algorithm 1, so can the authors explain why they didn’t compare?", "limitations": "The research was done only for the Gaussian distribution.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The authors show that popular frequentist algorithms are suboptimal in the Bayesian setting.\n\n- The paper presents a novel algorithm, which is significant because, according to related work, it is uncommon to have a stopping time in Bayesian optimization.\n\n- In the successive elimination method, the indifference zone is not a parameter.\n\n- The derived lower bound is novel.", "weaknesses": "1. 47: Example 1 lacks proof or reference for the number of samples.\n\n2. The authors do not discuss how they derived the constant L(H) and its significance. Since this constant represents sampling complexity and is not a traditional term, it is harder to compare the complexity to existing work.\n\n3. 171: In Chapter 3, the authors claim there is a known lower bound for the expected stopping time without providing any reference.\n\n4. 196: The derivation of the inequalities in Section 3.1 is not clear.\n\n5. 242-243: In Chapter 5, there is no explanation for why this particular confidence width was considered.\n\n6. In Chapter 6, there is no discussion on why Algorithm 1 shows higher error percentages than the other two algorithms.\n\n7. 313: there are two dots instead of one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading of the paper and the insightful comments. We will revise the typos and references in our final version. In the following, we address the main questions raised.\n\n> W2) The authors do not discuss how they derived the constant L(H) and its significance. Since this constant represents sampling complexity and is not a traditional term, it is harder to compare the complexity to existing work.\n\nFrom Section 3, we find that measuring the probability when $\\mu$ achieves a small suboptimality gap is crucial. The constant $L(H)$ represents the ratio between the gap $\\Delta$ and the probability that $\\mu$ achieves a suboptimality gap smaller than $\\Delta$, as outlined in Lemma 1. We will include a discussion on this in our final version.\n\n> Q1) 267-268: In Remark 3, can the authors explain if in the general case, the result matches with the lower bound?\n\nOur lower bound holds only when $\\delta$ is sufficiently small, whereas the result in Remark 3 (upper bound) is the case of moderately large $\\delta$, so we cannot say the result matches with the lower bound. \n\n> Q2) 309-313: The authors state that the expected stopping time of the track-and-stop method is at least half of the TTTS and TTUCB methods, which according to Table 1, is on average at least 300. This number is less than that for Algorithm 1, so can the authors explain why they didn’t compare?\n\nTo avoid possible confusion, allow us to clarify our experiment result again. In Table 1 of the paper we submitted, our algorithm has a stopping time of $10^4$, TTUCB has a stopping time of $1.5\\times 10^5$, and TTTS has an even higher stopping time. Even if the stopping time of Track-and-Stop is half that of TTUCB, it would be $7.6\\times 10^4$, which is still over 7 times larger than our algorithm.\n\n> W4) 196: The derivation of the inequalities in Section 3.1 is not clear.\n\nWe will add more explanation on Section 3.1 in our final version. Corollary 3 implies that for any fixed mean vector $\\mu \\in \\mathbb{R}^2$, the stopping time is lower bounded by $\\log (1/\\delta)/(\\mu_1 -\\mu_2)^2$. For the following sequence of equations (equation in line 196~197),\n\n$\\mathbb{E}\\_{\\mu \\sim H} [\\tau] \\geq \\mathbb{E}\\_{\\mu \\sim H} [\\tau \\cdot  \\mathbb{1}[|\\mu_1 -\\mu_2| \\leq \\epsilon]]\n    \\geq \\frac{\\log \\delta^{-1}}{\\epsilon^2} \\mathbb{P}\\_{\\mu \\sim H} [|\\mu_1- \\mu_2| \\leq \\epsilon] = \\Omega(\\frac{\\log \\delta^{-1}}{\\epsilon})$\n\n1) The first inequality holds since $\\tau$ is a positive random variable.\n2) The second inequality holds by the following  \n  - law of total expectation $\\mathbb{E}\\_{\\mu \\sim H} [\\tau \\cdot  \\mathbb{1}[|\\mu_1 -\\mu_2| \\leq \\epsilon]] = \\mathbb{E}\\_{\\mu \\sim H} [\\mathbb{E}[\\tau |\\mu] \\cdot  \\mathbb{1}[|\\mu_1 -\\mu_2| \\leq \\epsilon]]$\n  - and Corollary 3 $\\mathbb{E}\\_{\\mu \\sim H} [\\mathbb{E}[\\tau|\\mu] \\cdot  \\mathbb{1}[|\\mu_1 -\\mu_2| \\leq \\epsilon]] \\geq \\mathbb{E}\\_{\\mu \\sim H} [\\frac{\\log \\delta^{-1}}{(\\mu_1 - \\mu_2)^2} \\cdot  \\mathbb{1}[|\\mu_1 -\\mu_2| \\leq \\epsilon]]\\geq \\frac{\\log \\delta^{-1}}{\\epsilon^2} \\mathbb{P}\\_{\\mu \\sim H} [|\\mu_1- \\mu_2| \\leq \\epsilon]$\n3) Finally, by Lemma 1, we can replace $\\mathbb{P}(\\cdots)$ as $L(H)\\cdot \\epsilon$ which leads the RHS.\n\n> W5) 242-243: In Chapter 5, there is no explanation for why this particular confidence width was considered.\t\n\nThe bound is for assuring $LCB(i,t) \\leq \\mu_i \\leq UCB(i,t)$ for all $t\\in \\mathbb{N}$ and $i\\in[k]$ with high probability. For more details, please check Lemma 15 (Appendix E). In our final version, we will add more explanation about the proof in Section 5. \n\n> W6) In Chapter 6, there is no discussion on why Algorithm 1 shows higher error percentages than the other two algorithms.\t\n\nWhen our algorithm finds the suboptimality gap is too narrow, instead of trying to identify the best arm, our algorithm stops sampling to avoid excessive sample complexity. On the other hand, the other two algorithms always keep sampling until they identify the best arm. This difference causes the error rate difference. However, as we have mentioned in Section 3, the algorithm should set an indifference condition in the Bayesian setting or the algorithm will attain an excessive scale of sample complexity, even diverging to infinity in expectation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eIr8eimTAS", "reviewer": "Reviewer_bY8m", "summary": "This paper considers a best arm identification problem in Bayesian multi-armed bandit setting. The arms' distributions are generated according to the unknown prior, and the probability of error is averaged over this prior distribution. The paper makes two key contributions: first, a lower bound characterizing the fundamental hardness of BAI in the Bayesian setting (where the L(H) parameter is identified as playing a key role), and second, and achievability part that proposes a successive elimination-based algorithm (with early stopping in case the arm instance has very close best arms). The algorithm achieves within a logarithmic factor of the lower bound.", "questions": "The definition of $\\mathcal H_\\mu$ at the beginning of page 4 may not be precise...is it an event or a $\\sigma$-algebra? In the former case, with continuous Gaussian priors, it is not clear if the event has non-zero probability, which makes all the conditional probabilities technically dubious. Please clarify.", "limitations": "Limitations are acknowledged in the conclusions reasonably.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper brings out an interesting twist on BAI, where the Bayesian setting is statistically easier on \"an average\" compared to the frequentist setting. The paper explains the intuition clearly throughout, and is executed competently.", "weaknesses": "There is no glaring weakness. It appears to be obvious in hindsight that \"very close\" instances do not occur with substantial probability, when we have a Gaussian prior, making the hard frequentist instances statistically irrelevant in the Bayesian setting. This makes the BAI problem easier in terms of the expected stopping time. If the prior model creates close instances with non-vanishing probability, I suppose we'd be back to the frequentist performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful reading of the paper and the insightful comments. In the following, we address the question raised.\n\n> The definition of ${\\mathcal{H}}_{\\mu}$ at the beginning of page 4 may not be precise...is it an event or a $\\sigma$-algebra? In the former case, with continuous Gaussian priors, it is not clear if the event has a non-zero probability, which makes all the conditional probabilities technically dubious. Please clarify.\n\nWe are using the law of total expectation $\\mathbb{E} [X] =  \\mathbb{E} [\\mathbb{E} [X|\\sigma(Y)]] = \\mathbb{E} [g(Y)]$ where $\\sigma(Y)$ is the sigma algebra generated by random variable $Y$ and $g(y) = \\mathbb{E} [X|Y=y]$. This argument holds even when {Y=y} has zero probability. See for example\n\n1. Example 4.1.6 in 'Durrett, Rick. Probability: theory and examples. Vol. 49. Cambridge University Press, 2019'\n2. Example 4 in https://www.stat.cmu.edu/~arinaldo/Teaching/36752/S18/Notes/lec_notes_6.pdf\n3. https://math.stackexchange.com/questions/1332879/conditional-probability-combining-discrete-and-continous-random-variables\n\n In particular, in our case $Y$ is $\\mu$ and we are computing $\\mathbb{E}\\_{\\mu_0 \\sim \\mathcal{H}} [\\mathbb{P}(J\\neq i^*(\\mu)|\\mu=\\mu_0)]$. In this sense, $\\mathcal{H}_{\\mu_0} = \\{\\mu = \\mu_0\\}$ is an event. In the Bayesian setting, $\\mu$ is a random variable, and we wanted to express the probability of error (PoE) as the form of the law of the total expectation, to emphasize that our probability of error is the marginalized form of the PoE. We used the notation $\\mathcal{H}\\_{\\mu}$ to simplify notation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Iy9U0V5n6B", "reviewer": "Reviewer_4HmL", "summary": "This paper considers the best arm identification (BAI) problem in the fixed confidence setting and in the Bayesian setting, where the mean rewards of each arm is drawn from a known prior distribution. The authors formulate the problem and discuss the related literature. The authors provide the lower bound of the expected sample complexity of finding the optimal arm, which is proportional $L(\\mathbb{H})/\\delta$ where $L(\\mathbb{H})$ is defined by the authors to characterize the sample complexity. Then the authors show the current optimal algorithms in the frequentist setting: the top two and tack-and-stop algorithms are suboptimal in the Bayesian setting. The authors then propose a new algorithm based on the successive elimination algorithm in the frequentist setting, showing that this algorithm reaches the optimal sample complexity up to a logarithmic factor. The authors provide the upper bound of the algorithm on the expected sample complexity. Finally the authors run two simulations to show that the top-two algorithm is indeed suboptimal comparing with Algorithm 1, and also show the superior performance of algorithm1 compared to the no-elimination version of it.", "questions": "1. Is it possible to use tighter confidence intervals to get a better upper bound?\n2. Is it trivial or direct to consider similar algorithms when the distribution of the arms is more general, like subgaussian, or non-parametric?\n3. Is it possible to modify top-two or tack-and-stop to make it better in the Bayesian setting?\n4. Just out of curiosity, is it possible to modify LUCB or lil-UCB to this setting so that it achieves similar performance when the authors modify the successive elimination algorithm? Since the former two algorithms have better sample complexity in the frequentist setting.\n5. Can the upper bound be modified to a high probability bound instead of an expectation bound on the sample complexity? Would it be challenging or trivial?", "limitations": "See weaknesses and questions.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The problem is clearly defined and the paper is nicely presented.\n2. It is nice to show that the optimal algorithms (top-two and tack-and-stop) are suboptimal in the Bayesian setting\n3. The authors illustrate the theorems and proofs using a simpler 2-arm version which can be better understood.", "weaknesses": "1. The assumption of the arms may be stringent, i.e. all arms are from the Gaussian distribution. The current literature considers many more general distributions, such as sub-gaussian, exponential family, or even non-parametric cases.\n2. The confidence interval is not optimized to the tightest confidence interval which is suggested in the lil-UCB paper from Jamieson: \"lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits\"\n3. The lower bound proof (and possibly the upper bound proof) uses standard techniques from the literature. Perhaps the authors could point out the difficulty or challenge in the proofs.\n4. The upper bound is not optimal compared to the lower bound, with an extra logarithmic factor. Is it possible to reduce this gap using tighter confidence bound or do some modification to the algorithm, such as modification of top-two or tack-and-stop instead of modify the SE algorithm (which is not optimal in the frequentist setting)\n5. The simulations are limited to just two sets of experiments. The baselines or compared algorithms are just 2/1 in the respective setting. And it might be better to include different $\\delta$ values since the authors consider the fixed confidence setting and change priors as well.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable review and comments. The following are the responses to the questions you raised.\n\n> Q1) better upper bound using lil-UCB\n\nWe assume your question refers to the improvement of the confidence bound from $\\sqrt{\\log(N_i(t)/\\delta)/N_i(t)}$ to $\\sqrt{\\log(\\log(N_i(t))/\\delta)/N_i(t)}$. It is challenging to verify all parts of the proof during this short rebuttal period, but we conjecture this can improve the dependency on $\\log(L(H))$ but would not change the dependency with respect to $\\log(1/\\delta)$. Since this is the first paper on the fixed-confidence Bayesian best arm identification, we consider the current analysis to have enough novelty. \n\n> Q2) extending the distribution of the arms is more general, like subgaussian, or non-parametric?\n\nMany results in our paper, such as Lemma 1 (Volume lemma), Lemmas 11, 13~17, and Theorem 18 hold also in non-Gaussian settings. However, several results such as Lemmas 12 and 17 are tailored for the Gaussian setting and we cannot extend those results easily to other environments. Therefore, our lower and upper bound results need some additional work to extend to other settings. As we mentioned in Section 7, extending the current results to more diverse environments is one of the interesting future research topics. \n\n> Q3, Q4) modify other algorithms, such as top-two, track-and-stop, LUCB or lil-UCB to make it better in the Bayesian setting \n\nAs we have mentioned in our future work section (Section 7), it is another interesting research topic. We chose the Elimination algorithm since it is easier to manage the number of suboptimal arm pulls. Elimination also attains an orderwise optimal ratio in a frequentist setting, so we believe that using TT, T&S, LUCB or lil-UCB won't make an orderwise improvement, especially with respect to $\\delta$. \n\n> Q5) a high probability bound instead of an expectation bound on the sample complexity?\n\nIn the Bayesian setting in general, there is no natural idea of a high-probability bound, since the bandit instance $\\mu$ is also another random variable. For example, in many FC-BAI studies in a frequentist setting, they propose the high-probability bounds of the stopping time as the form of **'$\\tau \\leq f(\\mu)$ with probability $1-\\delta$'**. It is reasonable in a frequentist setting since $\\mu$ is a fixed instance in their setting. However, in our case, $\\mu$ is also a random variable, so it means now the bold inequality compares two random variables. We thought that whether such results could be accepted as high-probability bounds might be controversial depending on the reader. Therefore, we presented expectation bounds.\n\nIn the case of the high-probability bound when the bandit instance $\\mu$ is fixed, it is relatively trivial. Our Lemma 17 can be seen as the high probability bound for each arm when $\\mu$ is given, and from this result we computed the overall expectation, which was computationally challenging (about 5 pages of integral computations).\n\n> W3) The lower bound proof (and possibly the upper bound proof) uses standard techniques from the literature. \n\nOur lower bound proof is novel and we suggest the first framework to prove Bayesian FC-BAI lower bound. Our proof structure is significantly different from the standard technique in the Frequentist FC-BAI lower bound, such as Kaufmann et al., (2016). \n\nThe main differences come from the different definitions of the error probability (PoE) between the frequentist setting and the Bayesian setting. As mentioned in Lines 178-179, Bayesian $\\delta$-correctness is more lenient than the frequentist $\\delta$-correctness. This means we need to consider more diverse algorithms for the lower bound since the lower bound is for all possible $\\delta$-correct algorithms. We want to mention three challenges in our proof. \n\n- First, in our case, we suggest a novel interpretation of PoE to an optimization problem (Opt0 -> Opt1, given the upper bound of the stopping time, how small the error probability can be?) \n\n- Second, we propose a relaxation (Opt1 -> Opt2), which changes the optimization parameter from algorithms to the positive real functions $\\tilde{n}: \\mathbb{R}^2 \\to [0,\\infty)$.\n\n- Lastly, we found out that the main problem happens in the 'instances with small suboptimality gaps' and made a novel modification (Opt2 -> Opt3), and use Jensen's inequality in a creative way (Claim 1 in Appendix D) to achieve a computable optimal answer. \n\nThere are also other minor novel techniques, such as extension of the [Lemma 1, Kaufmann et al., 2016] (Lemma 11 in our paper) which helped us to transform the little-kl divergence to easier notation. \n\n\n\n> W5) The simulations are limited to just two sets of experiments. The baselines or compared algorithms are just 2/1 in the respective setting. And it might be better to include different values since the authors consider the fixed confidence setting and change priors as well.\n\nWe made a brief comparison between Algorithm 1 and TTUCB in $K=10$ arm environment with different prior means, prior variances and instance variances. (because of the time constraint, it was not easy to finish TTTS at the same time.) Details of experiments are in the next comment. \n\nAfter 500 simulations, the expected stopping time of our algorithm was $1.1\\times 10^5$, while TTUCB attains $7.1\\times 10^5$. Even after giving an advantage to TTUCB, our algorithm shows a much smaller sample complexity than TTUCB. \n\nTo avoid possible confusion, allow us to clarify our experiment result again. In Table 1, the compared algorithms have 10 times larger expected stopping time than ours, and about 500 times larger maximum stopping time.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers a Bayesian formulation of the classic fixed confidence best-arm identification problem. In particular, they consider the special case of known independent Gaussian priors for each arm, and Gaussian rewards with known variance. Given the overlapping support of the priors, there is a non-zero chance of an arbitrarily small minimum gap which blows up the sample complexity of naively applied delta-PAC algorithms for the frequentist setting. The main contributions are a novel lower bound for this setting and an algorithm that matches it up to log factors.

The goals of the paper are clear and they are well-executed. Perhaps the biggest weakness of this paper is the assumption that the prior distributions are Gaussian. As the critical identified quantity in the sample complexity denoted as L(H) is derived directly from this assumption, it is unlikely to be meaningful in the general prior case. Indeed, if the prior is a uniformly random permutation of a fixed set of separated means, L(H) has no impact on the sample complexity of this problem (see Chen, Li, Qiao 2016 and Simchowitz and Jamieson 2016). As some reviewers suggested, the authors would improve the paper by adding a longer discussion motivating L(H) and under what prior conditions it is a relevant quantity.
Decision: Accept (poster)