Optimal Batched Best Arm Identification

Authors: tianyuan  jin
yu  yang
jing  tang
xiaokui  xiao
pan  xu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 18:23:08

Abstract: We study the batched best arm identification (BBAI) problem, where the learner's goal is to identify the best arm while switching the policy as less as possible. In particular, we aim to find the best arm with probability $1-\delta$ for some small constant $\delta>0$ while minimizing both the sample complexity (total number of arm pulls) and the batch complexity (total number of batches). We propose the three-batch best arm identification (Tri-BBAI) algorithm, which is the first batched algorithm that achieves the optimal sample complexity in the asymptotic setting (i.e., $\delta\rightarrow 0$) and runs in $3$ batches in expectation. Based on Tri-BBAI, we further propose the almost optimal batched best arm identification (Opt-BBAI) algorithm, which is the first algorithm that achieves the near-optimal sample and batch complexity in the non-asymptotic setting (i.e., $1/\delta$ is finite), while enjoying the same batch and sample complexity as Tri-BBAI when $\delta$ tends to zero. Moreover, in the non-asymptotic setting, the complexity of previous batch algorithms is usually conditioned on the event that the best arm is returned (with a probability of at least $1-\delta$), which is potentially unbounded in cases where a sub-optimal arm is returned. In contrast, the complexity of Opt-BBAI does not rely on such an event. This is achieved through a novel procedure that we design for checking whether the best arm is eliminated, which is of independent interest.

Main paper: 
 introduction: 
 Multi-armed bandit (MAB) is a fundamental model in various online decision-making problems, including medical trials [40] , online advertisement [5] , and crowdsourcing [43] . These problems typically involve a bandit with multiple arms, where each arm follows an unknown distribution with a mean value. At each time step, the learner selects an arm, and receives a reward sample drawn from the chosen arm's distribution. Best arm identification (BAI) aims to identify the arm with the highest mean reward, which can be approached with a fixed budget or a fixed confidence level [14, 4, 19] .In this paper, we assume that there is a unique best arm and study BAI with fixed confidence. Specifically, we consider a set [n] = {1, 2, . . . , n} of n arms, where each arm i is associated with a reward distribution having a mean value µ i . Without loss of generality, for a bandit instance denoted by µ = {µ 1 , µ 2 , . . . , µ n }, we assume that µ 1 > µ 2 ≥ • • • ≥ µ n . At each time step t, the learner selects an arm and observes a sample drawn independently from the chosen arm's distribution. In the fixed confidence setting, the learner aims to correctly identify the best arm (arm 1 in our context) with a probability of at least 1 -δ, where δ > 0 is a pre-specified confidence parameter. Meanwhile, the learner seeks to minimize the total number of arm pulls, also known as the sample complexity.Denote by a * (λ) = arg max i λ i the best arm for an arbitrary bandit instance λ. Let Alt(µ) = {λ : a * (λ) ̸ = 1} be a set of models that have a different best arm from the model µ, and P k = {w ∈ R n + : n i=1 w i = 1} be the probability simplex. Garivier and Kaufmann [17] showed that for bandits with reward distributions that are continuously parameterized by their means, the number N δ of pulls 38th Conference on Neural Information Processing Systems (NeurIPS 2024). by any algorithm that returns the best arm with a probability of at least 1 -δ is bounded byEQUATIONwhere T * (µ) is defined according to T * (µ) -1 := supEQUATIONand d(µ i , λ i ) is the Kullback-Leibler (KL) divergence of two arms' distributions with means µ i and λ i , respectively. We say that an algorithm achieves the asymptotically optimal sample complexity if it satisfieslim sup δ→0 E µ [N δ ] log(1/δ) ≤ T * (µ).(1.3)The well-known Track-and-Stop algorithm [17] solves the BAI problem with asymptotically optimal sample complexity. However, it is a fully sequential algorithm, which is hard to be implemented in parallel. The learner in such an algorithm receives immediate feedback for each arm pull, and adjusts the strategy for the next arm selection based on the previous observations. Unfortunately, this sequential approach may not be feasible in many real-world applications. For instance, in medical trials, there is typically a waiting time before the efficacy of drugs becomes observable, making it impossible to conduct all tests sequentially. Instead, the learner needs to group the drugs into batches and test them in parallel. Similarly, in crowdsourcing, the goal is to identify the most reliable worker for a specific task by testing candidates with a sequence of questions. Again, there is often a waiting time for workers to finish all the questions, necessitating the grouping of workers into batches and conducting parallel tests. In such scenarios, the results of pulling arms are only available at the end of each batch [22, 1, 39, 37, 15, 24, 25, 38] .Motivated by these applications, we study the problem of batched best arm identification (BBAI).In BBAI, we are allowed to pull multiple arms in a single batch, but the results of these pulls are revealed only after the completion of the batch. The objective is to output the best arm with a high probability of at least 1 -δ, while minimizing both the sample complexity (total number of pulls) and the batch complexity (total number of batches). This leads to the following natural question:Can we solve the BBAI problem with an asymptotically optimal sample complexity and only using a constant number of batches?Furthermore, the aforementioned results hold only in the limit as the confidence parameter δ approaches zero, which may provide limited practical guidance since we often specify a fixed confidence level parameter δ > 0. To address this, some algorithms [31, 21] have been proposed to solve the BAI problem with finite confidence. Specifically, for some universal constant C, these algorithms satisfy that with probability 1 -δ,E[N δ ] ≤ O i>1 1 ∆ 2 i log log ∆ -1 i (1.4)where ∆ i = µ 1 -µ i . In addition, Jamieson et al. [21] demonstrated that for two-armed bandits, the termlog log ∆ -1 2 ∆ 2 2is optimal as ∆ 2 → 0, where ∆ 2 is assumed to be the gap between the best arm and the second best arm. In the context of the batched setting, Jin et al. [22] proposed an algorithm that achieves the sample complexity in (1.4) within O(log * (n) • log(1/∆ 2 )) batches, where log * (n) is the iterated logarithm function 1 . Furthermore, Tao et al. [39] proved that for certain bandit instances, any algorithm that achieves the sample complexity bound shown in (1.4) requires at least Ω log ∆ -1 2 log log ∆ -1 2 batches. It should be noted that the batched lower bound proposed by Tao et al. [39] assumes δ as a constant, making it inapplicable in the asymptotic setting. Therefore, an additional question that arises is:Can we achieve the optimal sample complexity in (1.3) and (1.4) adaptively, taking into account the specified confidence level parameter δ, while minimizing the number of batches?Table 1 : Comparison of sample and batch complexity of different algorithms. In the asymptotic setting (i.e., δ → 0), the sample complexity of an algorithm is optimal if it satisfies the definition in (1.3) . The field marked with "-" indicates that the result is not provided. The sample complexity presented for [31, 22] is conditioned on the event that the algorithm returns the best arm, which can be unbounded when it returns a sub-optimal arm with certain (non-zero) probability (see Remark 4.4 for more details). In contrast, the sample complexity presented for [17, 26] and our algorithms is the total expected number of pulls that will be executed.Algorithm Asymptotic behavior (δ → 0) Finite-confidence behavior Sample complexity Batch complexity Sample complexity Batch complexity Karnin et al. [31] Not optimal O(log n• log n ∆2 ) O i>1 log(log ∆ -1 i ) ∆ 2 i O(log n • log n ∆2 ) Jin et al. [22] Not optimal O(log 1 ∆2 ) O i>1 log(log ∆ -1 i ) ∆ 2 i O(log * (n) • log 1 ∆2 ) Wang et al. [42] Optimal O( log(1/δ)) O(nH(µ) 4 /w 2 min ) - Agrawal et al. [2]OptimalT * (µ) log δ -1 m (m = o(log δ -1 )) - - Karpov et al. [32] - - O i>1 log(n log ∆ -1 i ) ∆ 2 i O(log 1 ∆2 ) Lower bound [39] - - O i>1 log(log ∆ -1 i ) ∆ 2 i Ω(log(1/∆ 2 )) Tri-BBAI (Our Algorithm 1) Optimal 3 - - Opt-BBAI (Our Algorithm 2) Optimal 3 O i>1 log(n log ∆ -1 i ) ∆ 2 i O(log 1 ∆2 )In this work, we provide positive answers to both of the aforementioned questions. Specifically, the main contributions of our paper can be summarized as follows:• We propose Tri-BBAI (Algorithm 1) that returns the best arm with a probability of at least 1 -δ by pulling all arms for a total number of at most T * (µ) log(1/δ) times when δ → 0. Tri-BBAI employs three batches in expectation when δ → 0. Therefore, Tri-BBAI achieves the optimal sample within constant batches. As a comparison, Track-and-Stop [17] also achieves the optimal sample complexity but requires solving the right-hand side of (1.2) after each arm pull, resulting in a batch complexity of the same order as the sample complexity, which is a significant computational overhead in practice. • Built upon Tri-BBAI, we further propose Opt-BBAI (Algorithm 2) that runs in O(log(1/∆ 2 ))expected batches and pulls at most O i>1 ∆ -2 i log(n log ∆ -1 i ) expected number of arms for finite confidence δ. It is also important to note that Opt-BBAI achieves the same sample and expected batch complexity as Tri-BBAI asymptotically when δ → 0. Moreover, for the finite confidence case, this sample complexity matches (1.4) within a log(•) factor and matches the optimal batched complexity within a log log(•) factor. To the best of our knowledge, Opt-BBAI is the first batched bandit algorithm that can achieve the optimal asymptotic sample complexity and the near-optimal non-asymptotic 2 sample complexity adaptively based on the assumption on δ.• Notably, in the non-asymptotic setting, the complexity of earlier batch algorithms [22, 32, 39, 24] typically depends on the event of returning the best arm, which occurs with a probability of at least 1 -δ. However, this complexity could potentially become unbounded if a sub-optimal arm is returned instead. Unlike these algorithms, the complexity of Opt-BBAI is not contingent on such an event. This is made by employing an innovative procedure to verify if the best arm is eliminated, a method that holds its independent interest. To the best of our knowledge, Opt-BBAI is the first algorithm that achieves the optimal asymptotic sample complexity while providing the optimal non-asymptotic sample complexity within logarithm factors. • We also conduct numerical experiments 3 to compare our proposed algorithms with the optimal sequential algorithm Track-and-Stop [17] , and the batched algorithm Top-k δ-Elimination [22] on various problem instances. The results indicate that our algorithm significantly outperforms the Track and Stop method in terms of batch complexity, while its sample complexity is not much worse than that of Track and Stop. Additionally, our algorithm demonstrates a notable improvement in sample complexity compared to [22] , while exhibiting similar batch complexity.For ease of reference, we compare our results with existing work on batched bandits in Table 1 . Karnin et al. [31] O(H(µ) log(1/δ)) O i>1 log(log ∆ -1 i ) ∆ 2 iGarivier and Kaufmann [17] T * (µ) log(1/δ)+o(1/δ) -Jamieson et al. [21] O(H(µ) log(1/δ)) O i>1 log(log ∆ -1 i ) ∆ 2 iJourdan and Degenne [26] T* β (µ) log(1/δ)+o(1/δ) O ((H(µ) log H(µ)) α ), α > 1 Degenne et al. [12] T * (µ) log(1/δ)+o(1/δ) Õ(nT * (µ) 2 ) Katz-Samuels et al. [33] O(T * (µ) log(1/δ)) O(H(µ) log(n/∆min)) Wang et al. [42] T * (µ) log(1/δ)+o(1/δ) O(nH(µ) 4 /w 2 min ) Opt-BBAI (Our Algorithm 2) T * (µ) log(1/δ)+o(1/δ) O i>1 log(n log ∆ -1 i ) ∆ 2 i 2 Related WorkThe BAI problem with fixed confidence is first studied for [0, 1] bounded rewards by Even-Dar et al. [14] . The sample complexity of their algorithm scales with the sum of the squared inverse gap, i.e., H(µ) = i>1 1/∆ 2 i . Garivier and Kaufmann [17] showed that H(µ) < T * (µ) ≤ 2H(µ) with T * (µ) defined in (1.2) and proposed the Track-and-Stop algorithm, which is the first one in the literature proved to be asymptotically optimal. Later, Degenne et al. [12] viewed T * (µ) as a min-max game and provided an efficient algorithm to solve it. Jourdan et al. [27] studied the asymptotically optimal sample complexity for any reward distributions with bounded support. Degenne et al. [13] studied pure exploration in linear bandits. Their proposed algorithm proved to be both asymptotically optimal and empirically efficient.There are also many studies [30, 10, 8, 21, 31] that focus on providing non-asymptotic optimal sample complexity. The best non-asymptotic sample complexity was achieved by Chen et al. [10] , which replaces the term log log ∆ -1 i in (1.4) with a much smaller term. Furthermore, when we allow a loss ϵ of the quality of the returned arm, the problem is known as (ϵ, δ)-PAC BAI, for which various algorithms [29, 14, 6, 9] are proposed, achieving the worst-case optimal sample complexity.There are a few attempts to achieve both the asymptotic and non-asymptotic optimal sample complexity. Degenne et al. [12] provided a non-asymptotic sample complexity Õ nT * (µ) 2 , which could be nT * (µ) larger than the optimal sample complexity. Recently, Jourdan and Degenne [26] managed to achieve a sample complexity that is β-asymptotically optimal (with w 1 fixed at 1/β in (1.2)), rendering it asymptotically optimal up to a factor of 1/β. Meanwhile, they also reached a non-asymptotic sample complexity of O (H(µ) • log H(µ)) α4 for some α > 1, where H(µ) = i>1 1/∆ 2 i . Wang et al. [42] explored both asymptotic and non-asymptotic sample complexities. Their algorithm achieves asymptotic optimality and shows a non-asymptotic sample complexity of O(nH(µ) 4 /w 2 min ). However, this non-asymptotic sample complexity is nH(µ) 3 /w 2 min away from being optimal. Jourdan et al. [28] studied (ϵ, δ)-PAC BAI, proposing an asymptotically optimal algorithm and providing non-asymptotic sample complexity. When ϵ = 0, it aligns with our setting, our non-asymptotic sample complexity is better scaled. Specifically, Jourdan et al. [28] offered a non-asymptotic sample complexity scale of n/∆ 2 2 log(1/∆ 2 ), whereas ours is more instance-sensitive, as our sample complexity is related to all gaps, not just ∆ 2 . Additionally, Jourdan et al. [28] considered a practical scenario where the algorithm can return a result at any time while still ensuring a good guarantee on the returned arm. For ease of reference, we summarize the sample complexity of different algorithms in Table 2 . As shown in Table 2 , our algorithm is the only one that achieves both the asymptotic optimality and non-asymptotic optimality within logarithm factors.Another line of research [31, 4, 7] investigated BAI with a fixed budget, where the objective is to determine the best arm with the highest probability within T pulls. Audibert et al. [4] and Karnin et al. [31] offered finite-time bounds for this problem, while Carpentier and Locatelli [7] presented a tight lower bound, demonstrating that such finite-time bounds [4, 31] are optimal for certain bandit instances. However, the asymptotic optimality for this problem remains unknown. Interested readers are referred to recent advancements [11, 35] in the asymptotic results of BAI with a fixed budget.In addition, some recent works [1, 22, 39, 32] also focused on batched BAI in non-asymptotic setting. Agarwal et al. [1] studied the batched BAI problem under the assumption that ∆ 2 is known. They proposed an algorithm that has the worst-case optimal sample complexity of O n∆ -2 2 and runs in log * (n) batches. Later, Jin et al. [22] provided the algorithms that achieves the sample complexity given in (1.4) within Õ(log(1/∆ 2 )) batches, where Õ hides the log log(•) factors. Tao et al. [39] studied the BAI problem in the general collaborative setting and showed that no algorithm can achieve (1.4) with o((log ∆ -12 )/ log log ∆ -1 2 ) batches. Karpov et al. [32] further proposed an algorithm which has the sample complexity i>1 log(n log ∆ -1 ) ∆ 2 i and the batch complexity O(log(1/∆ 2 )). We note that the lower bound of batch complexity given by Tao et al. [39] can only be applied to a constant δ. In other words, the lower bound of complexity for the asymptotic setting remains unknown. Agrawal et al. [2] studied the optimal batch size for keeping the asymptotic optimality. They showed an algorithm with batch size m = o(log(1/δ)) achieves the asymptotic optimality. The batch complexity of the algorithm is O(T * (µ) log(1/δ)/m). Wang et al. [42] provided an algorithm that uses O( log δ -1 ) batches and retains asymptotic optimality for linear bandits. However, for the asymptotic setting, such batch size is still too large as it grows to infinity as δ decreases to 0.3 Achieving Asymptotic Optimality with at Most Three Batches 
reward distribution: 
 We assume the reward distributions belong to a known one-parameter exponential family that is commonly considered in the literature [17, 16, 36] . In particular, the measure ν θ of such probability distributions with respect the model parameter θ satisfies dν θ dρ (x) = exp(xθ -b(θ)), for some measure ρ and b(θ) = log( e xθ dρ(x)). For one-parameter exponential distributions, it is known that b ′ (θ) = E[ν θ ] and the mapping b ′ (θ) → θ is one-to-one. Moreover, given any two mean values µ and µ ′ , we define d(µ, µ ′ ) to be the Kullback-Leibler divergence between two distributions with mean values µ and µ ′ .Algorithm 1 shows the pseudo-code of our proposed Tri-BBAI algorithm. In particular, Tri-BBAI has four stages. In what follows, we elaborate on the details of each stage.Stage I: Initial exploration. In this stage, we pull each arm for L 1 times. Denote by i * (t) the arm with the largest empirical mean at time t (i.e., after we pull all arms for a total number of t times), i.e., i* (t) = max i∈[n] μi (t). Let τ 0 = nL 1 . Fix t = τ q-1 ≥ τ 0 , we let b q i = μi (t) + ϵ for i ̸ = i * (t) and b q i = μi (t) -ϵ for i = i * (t). Let w * (µ) = arg max w∈P k inf λ∈Alt(µ) ( n i=1 w i • d(µ i , λ i )).Then, for the aforementioned b q = {b q 1 , b q 2 , . . . , b q n }, we calculate w * (b q ) according to Lemma A.1 and T * (b q ) according to Lemma A.2. We note that arm 1 is assumed to be the arm with the highest mean in these two lemmas. However, in the context of b q , the index of i * (t) might be different. To align with the standard practice, we can rearrange the indices of the arms in b q so that i * (t) corresponds to index 1.Purpose. To achieve the asymptotic optimality, we attempt to pull each arm i for around w * i (µ)T * (µ) times. We can show that with a high probability, w * i (b q )T * (b q ) is close to w * i (µ)T * (µ), which implies that pulling arm i for a number of times proportional to w * i (b q )T * (b q ) is likely to ensure the asymptotic optimal sample complexity.Stage II: Exploration using w * (b q ) and T * (b q ). Stage II operates in batches with the maximum number of batches determined by log(1/δ). At batch q, each arm i is pulled max p:p∈N,p∈[1,q] T q i times in total. HereEQUATIONwhere the definition of w * i (b q ) and T * (b q ) could be found in Stage I. We then evaluate the stage switching condition, |w * i (b q ) -w * i (b q-1 )| ≤ 1/ √ n for all i ∈ [n]. If(b 0 ) = (1/n, 1/n, • • • , 1/n) and T 0 i = L 1 for all i ∈ [n]; for q = 1, 2 • • • , log(1/δ) do i * (t) ← max i∈[n] μi (t); for each i ∈ [n] \ {i * (t)} do b q i ← μi (t) + ϵ; b q i * (t) ← μi * (t) (t) -ϵ; for i ← 1 to n doPull arm i for {0, T q i -max p:p∈N,p∈[0,q) T p i } times; /**/ Note that T q i = min αw * i (b q )T * (b q ) log δ -1 , L 2 by (3.1) t ← t + {0, T q i -max p:p∈N,p∈[0,q) T p i }; if |w * i (b q ) -w * i (b q-1 )| ≤ 1/ √ n for all i ∈ [n] then Break; τ q ← t; τ ← t) ; if min j∈[n]\{i * (τ )} Z j (τ ) ≥ β(τ, δ/2) then return i * (τ );Stage IV: Round 3 exploration for i ← 1 to n do Pull arm i for total max{0, L 3 -L 1 -T i } times;t ← nL 3 , and i * (t) ← max i∈[n] μi (t); return i * (t) ;Purpose. Pulling arm i proportional to w * i (b q )T * (b q ) provides statistical evidence for the reward distributions without sacrificing sample complexity compared to the optimality per our above discussion. Meanwhile, we also set a threshold L 2 to avoid over-exploration due to sampling errors from Stage I.The rationale for running Stage II in multiple batches is based on empirical considerations. In experiments, δ is always finite. Consequently, the error of arm i, |μ i (t) -µ i |, remains constant since the number of pulls of arms is limited. Given that the stopping rule in Stage III is highly dependent on the error of arm i and the number of pulls T i := max p:p∈N,p≥1 T p i , there is a constant probability that the stopping rule may not be met, leading to significant sample costs in Stage IV. Adding the condition in Line 15 ensures that w * (b q ) converges and that the sample size T q i , as defined by w * (b q ) and T * (b q ), closely approximates αw * (µ)T * (µ) log δ -1 . This alignment significantly increases the probability that the stopping rule will be satisfied in experiments.Moreover, such modification doesn't hurt any theoretical results. To explain, in our analysis for Tri-BBAI, we demonstrate that as δ approaches 0, w * (b q ) will be very close to w * (µ) and the probability that Line 15 is not satisfied could be bounded by 1/ log 2 δ -1 , which means with high probability Stage II costs 2 batches. Besides, q ≤ log(1/δ), which implies that even if Line 15 is not satisfied, the number of batches required for Stage II is at most log(1/δ). Therefore, the expected number of batches required for Stage II is 2 as δ approaches 0.Stage III: Statistical test with Chernoff's stopping rule. Denote by N i (t) the number of pulls of arm i at time t. For each pair of arms i and j, define their weighted empirical mean asEQUATIONwhere μi (t) and μj (t) are the empirical means of arms i and j at time t. For μi (t) ≥ μj (t), defineEQUATIONWe test whether Chernoff's stopping condition is met (Line 21). If so, we return the arm with the largest empirical mean, i.e., i * (τ ), where τ is the total number of pulls examined after Stage II.Purpose. The intuition of using Chernoff's stopping rule for the statistical test is two-fold. Firstly, if Chernoff's stopping condition is met, with a probability of at least 1 -δ/2, the returned arm i * (τ ) in Line 22 is the optimal arm (see Lemma B.1). Secondly, when δ is sufficiently small, with high probability, Chernoff's stopping condition holds (see Lemma B.4). As a consequence, our algorithm identifies the best arm successfully with a high probability of meeting the requirement.Stage IV: Re-exploration. If the previous Chernoff's stopping condition is not met, we pull each arm until the total number of pulls of each arm eqauls L 3 taking into account the pulls in the previous stages (Line 24). Finally, the arm with the largest empirical mean is returned (Line 26).Purpose. If Chernoff's stopping condition is not met, i * (τ ) might not be the optimal arm. In addition, when each arm is pulled for L 3 times, we are sufficiently confident that i * (t) is the best arm. Since the probability of Stage IV happening is very small, its impact on the sample complexity is negligible.In the following, we present the theoretical results for Algorithm 1.Theorem 3.1 (Asymptotic Sample Complexity). Given any δ > 0, let ϵ = 1 log log(δ -1 ) , L 1 = log δ -1 , L 2 = log δ -1 log log δ -1 n, and L 3 = (log δ -1 ) 2 . Meanwhile, for any given α ∈ (1, e/2], define function β(t, δ) as β(t, δ) = log(log(1/δ)t α /δ). 5 Then, for any bandit instance µ, Algorithm 1 satisfieslim sup δ→0 E µ [N δ ] log(1/δ) ≤ αT * (µ).By letting α in Theorem 3.1 approach 1 (e.g., α = 1 + 1/ log δ -1 ), we obtain the asymptotic optimal sample complexity. Theorem 3.2 (Correctness). Let ϵ, L 1 , L 2 , L 3 , α, and β(t, δ) be the same as in Theorem 3.1. Then, for sufficiently small δ > 0, Algorithm 1 satisfiesP µ (i * (N δ ) ̸ = 1) ≤ δ. Theorem 3.3 (Asumptotic Batch Complexity). Let ϵ, L 1 , L 2 , L 3, α, and β(t, δ) be the same as in Theorem 3.1. For sufficiently small δ > 0, Algorithm 1 runs within 3 + o(1) batches in expectation. Besides, Algorithm 1 runs within 3 batches with probability 1 -1/ log(1/δ 2 ).To the best of our knowledge, all previous works in the BAI literature [18, 12, 2, 42] that achieve the asymptotic optimal sample complexity require unbounded batches as δ → 0. In contrast, Tri-BBAI achieves the asymptotic optimal sample complexity and runs within 3 batches in expectation, which is a significant improvement in the batched bandit setting where switching to new policies is expensive. Remark 3.4. Apart from best arm identification, regret minimization is another popular task in bandits, where the aim is to maximize the total reward in T rounds. Jin et al. [25] proposed an algorithm that achieves a constant batch complexity for regret minimization and showed that their algorithm is optimal when T goes to infinity. In regret minimization, the cost of pulling the optimal arm is 0, indicating that the allocation w i (i.e., the proportion of pulling the optimal arm) is close to 1.In the BAI problem, the main hardness is to find the allocation w i for each arm since even pulling arm 1 will increase the sample complexity of the algorithm. Therefore, the strategy proposed by Jin et al. [25] cannot be applied to the BAI problem. Let pj i be the empirical mean of arm i in S j ;S r ← [n], B 0 ← 0, r ← 1; while |S r | > 1 do Let ϵ r ← 2 -r /4, δ r ← δ/(40π 2 n • r 2 ), ℓ r ← 0,ℓ j ← ℓ j + 1; if ∃i ∈ S j , pj i > pr * -ϵ j /2 then 22return Randomly return an arm in S r ;r ← r + 1;return The arm in S r ;4 Best of Both Worlds: Achieving Asymptotic and Non-asymptotic OptimalitiesThe Tri-BBAI algorithm is shown to enjoy the optimal sample complexity with only three batches in the asymptotic setting. However, in practice, we are limited to a finite number of samples and thus δ cannot go to zero, which is a critical concern in real-world applications. Consequently, obtaining the optimal sample and batch complexity in a non-asymptotic setting becomes the ultimate objective of a practical bandit strategy in BBAI. In this section, we introduce Opt-BBAI, which can attain the optimal sample and batch complexity in asymptotic settings and near-optimal sample and batch complexity in non-asymptotic settings.We assume a bounded reward distribution within [0, 1], which aligns with the same setting in the literature [31, 21] . Again, we consider that the reward distribution belongs to a one-parameter exponential family. By refining Stage IV of Algorithm 1, we can achieve asymptotic optimality and near non-asymptotic optimality adaptively based on the assumption on δ in various settings.The pseudo-code for the algorithm is provided in Algorithm 2. The main modification from Algorithm 1 occurs in Stage IV. Intuitively, if the algorithm cannot return at Stage III, then the value of log δ -1 may be comparable to other problem parameters, such as 1/∆ 2 . Therefore, we aim to achieve the best possible sample and batch complexity for the non-asymptotic scenario. Stage IV operates in rounds, progressively eliminating sub-optimal arms until a result is obtained. Each round consists of two components: Successive Elimination and Checking for Best Arm Elimination.Successive Elimination. In the r-th round, we maintain a set S r , a potential set for the best arm. Each arm in S r is then pulled d r = 32/ϵ 2 r log(2/δ r ) times. At Line 11, all possible sub-optimal arms are eliminated. This first component of Stage IV borrows its idea from successive elimination [14] .Purpose. After d r number of pulls, arms are likely to be concentrated on their true means within a distance of ϵ r /4 with a high probability. Hence, with high probability, the best arm is never eliminated at every round of Line 11, and the final remaining arm is the best arm.Issue of Best Arm Elimination. Due to successive elimination, there is a small probability (≤ δ r ) that the best arm will be eliminated. The following example illustrates that, conditioning on this small-probability event, the sample and batch complexity of the algorithm could become infinite. > µ 2 = µ 3 > µ 4 ≥ • • • ≥ µ n .If the best arm is eliminated at a certain round and never pulled again, the algorithm tasked with distinguishing between the 2nd and 3rd best arms will likely never terminate due to their equal means, leading to unbounded sample and batch complexity.To address this issue, we introduce a Check for Best Arm Elimination component into Stage IV.Checking for Best Arm Elimination. In the r-th round, we represent the total sample complexity used up to the r-th round as B r . We employ γ j as an upper bound for the probability that the best arm is eliminated in S j . If Line 16 is true (B r γ j • 2 ℓj > B j ), we adjust γ j to γ 2 j and pull each arm in S j for 32/ϵ 2 j log(2/γ j ) times (Line 18), subsequently updating their empirical mean (Line 19). Finally, we return a random arm in S r if the condition at Line 21 holds.Purpose. If Line 16 is satisfied, it indicates that the sample costs, based on the event of the best arm being eliminated in the r-th round, exceed B j /2 ℓj . In this case, we increase the number of samples for arms in S j and re-evaluate if their empirical mean is lower than that of the current best arm * . This ensures that the expected total sample costs, assuming the best arm is eliminated at S j , are bounded by ∞ ℓj =1 B j /2 ℓj ≤ B j . If Line 21 holds, we randomly return an arm from S r . Since this only happens with a small probability, we still guarantee that Algorithm 2 will return the best arm with a probability of at least 1 -δ.In what follows, we provide the theoretical results for Algorithm 2. Theorem 4.2. Let ϵ, L 1 , L 2 , L 3 , α, and β(t, δ) be the same as in Theorem 3.1. For finite δ ∈ (0, 1), Algorithm 2 identifies the optimal arm with probability at least 1 -δ and there exists someuniversal constant C such that E[N δ ] ≤ C i>1 ∆ -2 i log n • log ∆ -1 i, and the algorithm runs in C log(1/∆ 2 ) expected batches.When δ is allowed to go to zero, we also have the following result. Theorem 4.3. Let ϵ, L 1 , L 2 , L 3 , α, and β(t, δ) be the same as in Theorem 3.1. Algorithm 2 identifies the optimal with probability at least 1 -δ and its sample complexity satisfies lim sup δ→0 E µ [N δ ]/log(1/δ) ≤ αT * (µ), and the expected batch complexity of Algorithm 2 converges to 3 when δ approaches 0.The results in Theorems 4.2 and 4.3 state that Algorithm 2 achieves both the asymptotic optimal sample complexity and a constant batch complexity. Moreover, it also demonstrates near-optimal performance in both non-asymptotic sample complexity and batch complexity. Notably, this is the first algorithm that successfully attains the optimal or near-optimal sample and batch complexity, adaptively, in asymptotic and non-asymptotic settings.Remark 4.4. Jin et al. [22] achieved near-optimal sample and batch complexity in a non-asymptotic setting. However, their results are contingent on the event that the algorithm can find the best arm (with probability 1 -δ). Consequently, with a probability of δ there is no guarantee for its batch and sample complexity to be bounded. As demonstrated in Example 4.1, the batch and sample complexity in [22] could even be infinite.In contrast, the batch and sample complexity introduced in Theorem 4.2 is near-optimal and does not rely on any specific event due to the procedure "checking for best arm elimination" we proposed. Our technique could be of independent interest and could be further applied to existing eliminationbased BAI algorithms [14, 21, 22, 31] to ensure that the sample and batch complexity is independent of the low-probability event that the best arm is eliminated. 
conclusion, limitations, and future work: 
 In this paper, we studied the BAI problem in the batched bandit setting. We proposed a novel algorithm, Tri-BBAI, which only needs 3 batches in expectation to find the best arm with probability 1 -δ and achieves the asymptotic optimal sample complexity. We further proposed Opt-BBAI and theoretically showed that Opt-BBAI has a near-optimal non-asymptotic sample and batch complexity while still maintaining the asymptotic optimality as Tri-BBAI does.In our experiments, although Tri-BBAI utilizes a limited number of batches, its sample complexity does not match that of Garivier and Kaufmann [17] . Designing a batched algorithm with sample complexity comparable to Garivier and Kaufmann [17] , while maintaining a constant number of batches, presents an intriguing challenge.As for future work, an interesting direction is to investigate whether our "checking for best arm elimination" could be beneficial to other elimination-based algorithms. Additionally, some research [3, 23] implied a strong correlation between batch complexity in batched bandit, and the memory complexity and pass complexity in streaming bandit. Thus, it could be valuable to assess if our techniques could enhance the results in the field of streaming bandit. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We state all information on the computer resources in Appendix E.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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal 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 or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness 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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 as 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 or 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe 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)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] .Justification: The paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a 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 of use in the 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 a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: i the empirical mean of arm i after its s-th pull and by μi (t) the empirical mean of arm i at time t (i.e., after a total number of t pulls are examined for all arms). We use ∆ i = µ 1 -µ i for the gap between the optimal arm and the i-th arm. Throughout the paper, we use the following asymptotic notation. Specifically we use f (δ) ≲ g(δ) to denote that there exists some δ 0 , such that for any δ < δ 0 , f (δ) ≤ g(δ). Similarly, we use f (δ) ≳ g(δ) to denote that there exists some δ 0 , such that for any δ < δ 0 , f (δ) ≥ g(δ).A Computing w * (µ) and T * (µ)In this section, we introduce two useful lemmas that help us to calculate w * (b) and T * (b) in Algorithm 1 and Algorithm 2, which are also used in [17] . For ease of presentation, we first define some useful notations. For every c ∈ [0, 1], we defineI c (µ, µ ′ ) := cd(µ, cµ + (1 -c)µ ′ ) + (1 -c)d(µ ′ , cµ + (1 -c)µ ′ ).For any arm i ∈ [n] \ {1}, we define g i (x) := (1 + x)I 1 1+x (µ 1 , µ i ). Lemma A.w i d(µ i , λ i ) = min i̸ =1 (w 1 + w i )I w 1 w 1 +w i (µ 1 , µ i ).Besides,EQUATIONandw * (µ) = arg max w∈Pn min i̸ =1 (w 1 + w i )I w 1 w 1 +w i (µ 1 , µ i ). (A.2)Lemma A.2 (Garivier and Kaufmann 17, Theorem 5). For i ∈ [n], letw * i (µ) = x i (y * ) i∈[n] x i (y * ), where y * is the unique solution of the equation F µ (y) = 1, and where F µ : y → n i=2 d µ 1 , µ1+xi(y)µi 1+xi(y) d µ i , µ1+xi(y)µi 1+xi(y) . in a continuous, increasing function on [0, d(µ 1 , µ 2 )) such that F µ (y) → ∞ when y → d(µ 1 , µ 2 ).β(t, δ/2) = log 2 log(2/δ)t α δ , ensures that P µ (i * (N δ ) ̸ = 1) ≤ δ/2.Recall μs i is the empirical mean of arm i after its s-th pull. LetE 1 = {∀s ≥ L 3 and i ∈ [n] : μs i ∈ [µ i -ϵ, µ i + ϵ]}.The following lemma shows that P(E c 1 ) ≤ δ/2, where E c denotes the complement event of E. Lemma B.2. For sufficiently small δ > 06 , we haveP(E c 1 ) ≤ δ/2.If Proof of Theorem 3.1. Recall in Algorithm 1, b q 1 = μi * (t) (t) -ϵ and b q i = μi (t) + ϵ for all i ∈ [n] \ {i * (t)}, where t = τ q . Let E 0 be the intersection of the following four events:E 1 0 = ∩ q≥1 {b q 1 ∈ [µ 1 -3ϵ/2, µ 1 -ϵ/2]}, (B.1a) E 2 0 = ∩ q≥1 {for all i ∈ [n] \ {1}, b q i ∈ [µ i + ϵ/2, µ i + 3ϵ/2]}, (B.1b) E 3 0 = ∩ q≥0 {μ 1 (τ q ) ≥ µ 1 -ϵ/2}, (B.1c) E 4 0 = ∩ q≥0 {for all i ∈ [n] \ {1}, μi (τ q ) ≤ µ i + ϵ/2}. (B.1d)Here (B.1a) and (B.1b) ensure that the estimation of w * (b q ) and T * (b q ) is close to w * (µ) and T * (µ), and (B.1c) and (B.1d) ensure that arm 1 has the largest average reward at time τ q . Lemma B.3. For sufficiently small δ > 0, we have 4 . If E 0 holds, then for sufficiently small δ > 0, we haveP((E c 0 ) ≤ 1 (log δ -1 ) 2 . Lemma B.1. T i = αw * i (µ)T * (µ) log(1/δ) + o(log(1/δ)); 2. |w * i (b 2 ) -w * i (b 1 )| ≤ 1/ √ n for all i ∈ [n]; 3. min j / ∈[n]\{i * (τ )} Z j (τ ) ≥ β(τ, δ/2).From Lemma B.4, if δ is sufficiently small and E 0 holds, then Algorithm 1 will return at Line 22.Besides, we note that the total number of pulls of any arm is no more than L 3 = (log(δ -1 )) 2 times.Therefore,E[N δ ] ≤ nL 1 + 1{E 0 } • (αT * (µ) log δ -1 + o(n log(1/δ))) + 1{E c 0 } • (L 2 + nL 3 ) ≤ 1{E 0 } • αT * (µ) log δ -1 + o(n log(1/δ)) + 1{E c 0 }nL 3 ≲ 1{E 0 } • αT * (µ) log δ -1 + n ≤ αT * (µ) log δ -1 + n. (B.2)We further havelim δ→0 E[N δ ] log δ -1 ≤ αT * (µ). This completes the proof.Proof of Theorem 3.3. Stage I costs one batch. For the Stage II, note thatP(E c 0 ) ≤ 1 log(δ -1 ) 2 and if E 0 occurs, then |w * i (b 2 ) -w * i (b 1 )| ≤ 1/√ n for all i ∈ [n] (from the second statement of Lemma B.4), which means Stage II costs 2 batches. Moreover, from Lemma B.4, if δ is sufficiently small and E 0 holds, then Algorithm 1 will return at Line 22. Otherwise, the algorithm goes to Stage IV and costs one batch. Therefore, for sufficiently small δ, the expected number of batches≤ 1 + P(E c 0 ) • log(1/δ) + 2 + P(E c 0 ) = 3 + o(1). Finally, if E 0 is true, the algorithm costs 3 batches. Therefore, with probability 1 -1/ log(1/δ 2 ), Algorithm 1 costs 3 batches.The proof of Lemma B.3 requires the following useful inequalities.Let N and M be two positive integers, let γ > 0, and μn be the empirical mean of n random variables i.i.d. according to the arm's distribution with mean µ. Then, for x ≤ µ,P(∃N ≤ n ≤ M, μn ≤ x) ≤ e -N (x-µ) 2 /(2V0) , (B.3)and for every x ≥ µ,P(∃N ≤ n ≤ M, μn ≥ x) ≤ e -N (x-µ) 2 /(2V1) , (B.4)where V 0 is the maximum variance of arm's distribution with mean µ ∈ [x, µ] and V 1 is the maximum variance of arm's distribution with mean µ ∈ [µ, x].Note that Lemma B.5 is an improved version of Lemma 4 of [36] , where we use a much smaller variance upper bound to tighten the inequalities for the case x ≤ µ and the case x ≥ µ respectively. From Lemma B.5, we have that for s ≥ L 1 ,P(∃s ≥ L 1 : μs 1 / ∈ [µ 1 -ϵ/2, µ 1 + ϵ/2]) ≤ P(∃s ≥ L 1 : μs 1 ≥ µ 1 + ϵ/2) + P(∃s ≥ L 1 : μs 1 ≤ µ 1 -ϵ/2) ≤ 2e -L1(ϵ/2) 2 /(2V ) ≲ 1 n(log δ -1 ) 2 , (B.6)where the second inequality is from Lemma B.5, and the last inequality is due to that for sufficiently small δ > 0, L 1 = log δ -1 ≥ 8V /ϵ 2 log(n(log δ -1 ) 2 ). Similarly, for i ∈ [n] \ {1},P(∃s ≥ L 1 : μs i / ∈ [µ i -ϵ/2, µ i + ϵ/2]) ≲ 1 n(log δ -1 ) 2 .(B.7)Define events:A 1 = {∀s ≥ L 1 : μs 1 ∈ [µ 1 -ϵ/2, µ 1 + ϵ/2]} and A 2 = {for all i ∈ [n] \ {1}, ∀s ≥ L 1 : μs i ∈ [µ i -ϵ/2, µ i + ϵ/2]}.Assume that both events A 1 and A 2 hold. Then, we haveμL1 1 ≥ µ 1 -ϵ/2 ≥ µ i + ϵ/2 + ∆ i -ϵ ≥ μL1 i ,where in the last inequality we assumed ϵ ≤ min i̸ =1 ∆ i . This further implies i * (τ q ) = 1 for any q ≥ 0 and thus b q-1 1 = μ1 (τ q ) -ϵ. Therefore, we have for any q ≥ 11. b q 1 = μ1 (τ q-1 ) -ϵ ∈ [µ 1 -3ϵ/2, µ 1 -ϵ/2]; 2. ∀i ∈ [n] \ {1}, b q i = μi (τ q-1 ) + ϵ ∈ [µ i -ϵ/2, µ 1 + ϵ/2]; 3. μ1 (τ q-1 ) ≥ µ 1 -ϵ/2; 4. and ∀i ∈ [n] \ {1}, μi (τ q-1 ) ≤ µ i + ϵ/2,which means E 0 defined in (B.1) occurs. Therefore, we haveP(E 0 ) ≥ P(A 1 ∩ A 2 ) = P {∀s ≥ L 1 : μs 1 ∈ [µ 1 -ϵ/2, µ 1 + ϵ/2]} i:i∈[n]\{1} {∀s ≥ L 1 : μs i ∈ [µ i -ϵ/2, µ i + ϵ/2]} = P {∃s ≥ L 1 : μs 1 / ∈ [µ 1 -ϵ/2, µ 1 + ϵ/2]} c i:i∈[n]\{1} {∃s ≥ L 1 : μs i / ∈ [µ i -ϵ/2, µ i + ϵ/2]} c ≥ 1 -P ∃s ≥ L 1 : μs 1 / ∈ µ 1 - ϵ 2 , µ 1 + ϵ 2 - i:i∈[n]\{1} P ∃s ≥ L 1 : μs i / ∈ µ i - ϵ 2 , µ i + ϵ 2 ≥ 1 -(log δ -1 ) -2 ,where the last inequality is due to (B.6) and (B.7).Proof of Lemma B. 4 .Assume E 0 is true. Recall that ∆ 2 = min i∈[n]\{1} µ 1 -µ i . For sufficiently small δ > 0 such that ϵ < ∆ 2 /8, we have b q 1 ∈ [µ 1 -∆ 2 /4, µ 1 ] and b q i ∈ [µ i , µ i + ∆ 2 /4]. Let L(b) = {λ ∈ S : λ 1 ∈ [µ 1 -∆ 2 /4, µ 1 ] and for any i ∈ [n] \ {1}, λ i ∈ [µ i , µ i + ∆ 2 /4]}. Therefore αw * i (b q )T * (b q ) ≤ max b ′ ∈L(b) αw * i (b ′ )T * (b ′ ) < ∞. Since max b ′ ∈L(b) αw * i (b ′ )T * (b ′ ) < ∞ is independent of δ , we have αw * i (b q )T * (b q ) ≤ max b ′ ∈L(b) αw * i (b ′ )T * (b ′ ) ≲ log log δ -1 /n = L 2 ,which implies T q i = min{αw * i (b q )T * (b q ) log δ -1 , L 2 } = αw * i (b q )T * (b q ) log δ -1 . Besides, as w * (b q ) and T * (b q ) are continuous on b q , we have that as b q → µ, w * (b q ) → w * (µ) and T * (b q ) → T * (µ). Note that |b q i -µ i | ≤ 2ϵ and ϵ approaches 0 as δ approaches 0. Recall τ is the stopping time of Stage II and T i is the number of pulls of arm i at time τ . Therefore, for sufficiently small δ, T i := max p:p∈N,p≥1T p i = αw * i (µ)T * (µ) log δ -1 + o(log(1/δ)).Moreover, for sufficient smaller δ and ∀i ∈[n], |w * i (b q ) -w * i (µ)| = o(1) and thus |w * i (b 1 ) -w * i (b 2 )| < 1/ √ n,which means the condition in Line 15 is satisfied and the Algorithm goes to Stage III.Assume τ = τ q ′ . We haveZ 1i (τ ) = N 1 (τ ) • d(μ 1 (τ ), μ1i (τ )) + N i (τ ) • d(μ i (τ ), μ1i (τ )) = N 1 (τ q ′ ) • d(μ 1 (τ ), μ1i (τ )) + N i (τ q ′ ) • d(μ i (τ ), μ1i (τ )) ≥ α log δ -1 • w * 1 (b q ′ )d(μ 1 (τ ), μ1i (τ )) T * (b q ′ ) -1 + w * i (b q ′ )d(μ 1 (τ ), μ1i (τ )) T * (b q ′ ) -1 , (B.8)where the last inequality is due toT i ≥ T q ′ i = αw * i (b q ′ )T * (b q ′ ) log(1/δ).In what follows, we will showw * 1 (b q ′ ) • d(μ 1 (τ ), μ1i (τ )) T * (b q ′ ) -1 + w * i (b q ′ ) • d(μ i (τ ), μ1i (τ )) T * (b q ′ ) -1 ≥ 1.The following minimization problem is a convex optimization problemmin λ1w:λ1w≤λiw w * 1 (b q ′ ) • d(μ 1 (τ ), λ 1w ) + w * i (b q ′ ) • d(μ i (τ ), λ iw ),which is solved when we have λ 1w = λ iw = μ1i (τ ). The proof of this lemma is based on the assumption that E 0 occurs. Note that E 0 occurs, then b q′ 1 = μ1 (τ q ′ -1 ) -ϵ ≤ µ 1 -ϵ/2 ≤ μ1 (τ ) and b q ′ i = μ1 (τ q ′ -1 ) + ϵ > μi (τ ) for all i ∈ [n] \ {1}. Therefore, μ1 (τ ) ≥ b q ′ 1 ≳ b q ′ i ≥ μi (τ ). Let λ w * (b q ′ ) (b q ′ 1 , b q ′ i ) = w * 1 (b q ′ ) w * 1 (b q ′ ) + w * i (b q ′ ) • b q 1 + w * i (b q ′ ) w * 1 (b q ′ ) + w * i (b q ′ ) • b q i . Then, λ w * (b) (b q ′ 1 , b q ′ i ) is the solution to minimizing w * 1 (b q ′ ) • d(b q ′ 1 , x) + w * i (b q ′ ) • d(b q ′ i , x) for x ∈ (b q ′ i , b q ′ 1 ). Case 1: if μ1i (τ ) ∈ (b q ′ 1 , μ1 (τ )), then w * 1 (b q ′ ) • d(μ 1 (τ ), μ1i (τ )) + w * i (b q ′ ) • d(μ i (τ ), μ1i (τ )) ≥ w * 1 (b q ′ ) • d(μ 1 (τ ), μ1 (τ )) + w * i (b q ′ ) • d(μ i (τ ), b q ′ 1 ) ≥ w * 1 (b q ′ ) • d(b q ′ 1 , b q ′ 1 ) + w * i (b q ′ ) • d(b q ′ i , b q ′ 1 ) ≥ w * 1 (b q ′ ) • d(b q ′ 1 , λ w * (b q ′ ) (b q ′ 1 , b q ′ i )) + w * i (b q ′ ) • d(b q ′ i , λ w * (b q ′ ) (b q ′ 1 , b q ′ i )), (B.9)where the first and second inequalities are due to (B.5) and the last inequality is due to the fact thatw * 1 (b q ′ ) • d(b q ′ 1 , x) + w * i (b q ′ ) • d(b q ′ i , x) achieves it minimum at x = λ w * (b q ′ ) (b q ′ 1 , b q ′ i ). Case 2: if μ1i (τ ) ∈ (b q ′ i , b q ′ 1 ), we have w * 1 (b q ′ ) • d(μ 1 (τ ), μ1i (τ )) + w * i (b q ′ ) • d(μ i (τ ), μ1i (τ )) ≥ w * 1 (b q ′ ) • d(b q ′ 1 , μ1i (τ )) + w * i (b q ′ ) • d(b q ′ i , μ1i (τ )) ≥ w * 1 (b q ′ ) • d(b q ′ 1 , λ w * (b q ′ ) (b q ′ 1 , b q ′ i )) + w * i (b q ′ ) • d(b q ′ i , λ w * (b q ′ ) (b q ′ 1 , b q ′ i )), (B.10)where the first inequality is due to (B.5) and the last inequality is due to the fact that for x ∈ (bq ′ i , b q ′ 1 ), w * 1 (b q ′ ) • d(b q ′ 1 , x) + w * i (b q ′ ) • d(b q ′ i , x) achieves its minimum at x = λ w * (b q ′ ) (b 1 . . . . . . q ′ , b q ′ i ).Case 3: if μ1i (τ ) ∈ (μ i (τ ), b q ′ i ), similar to (B.9) and (B.10), we havew * 1 (b q ′ ) • d(μ 1 (τ ), μ1i (τ )) + w * i (b q ′ ) • d(μ i (τ ), μ1i (τ )) ≥ w * 1 (b q ′ ) • d(b q ′ 1 , λ w * (b q ′ ) (b q ′ 1 , b q ′ i )) + w * i (b q ′ ) • d(b q ′ i , λ w * (b q ′ ) (b q ′ 1 , b q ′ i )). (B.11)Combine all three cases, we obtainw * 1 (b q ′ ) • d(μ 1 (τ ), μ1i (τ )) + w * i (b q ′ ) • d(μ i (τ ), μ1i (τ )) ≥ w * 1 (b q ′ ) • d(b 1 , λ w * (b q ′ ) (b q ′ 1 , b q ′ i )) + w * i (b q ′ ) • d(b q ′ i , λ w * (b q ′ ) (b q ′ 1 , b q ′ i )). (B.12) Note that μ1i (τ ) = λ w * (b q ′ ) (μ 1 (τ ), μi (τ )), we have w * 1 (b q ′ ) • d(μ 1 (τ ), μ1i (τ )) T * (b q ′ ) -1 + w * i (b q ′ ) • d(μ 1 (τ ), μ1i (τ )) T * (b q ′ ) -1 ≥ w * 1 (b q ′ ) • d(b q ′ 1 , λ w * (b q ′ ) (b q ′ 1 , b q ′ i )) T * (b q ′ ) -1 + w * i (b q ′ ) • d(b q ′ i , λ w * (b q ′ ) (b q ′ 1 , b q ′ i )) T * (b q ′ ) -1 = 1, (B.13)where the first inequality is due to (B.12) and the last inequality is due to (A.1). Note that conditioned on event E 0 , for sufficiently small δ > 0, we have 1 = i * (τ ). Therefore, for any i ∈ [n] \ {1},Z i (τ ) = Z 1i (τ ) = α log δ -1 • w * 1 (b q ′ ) • d(μ 1 (τ ), μ1i (τ )) T * (b q ′ ) -1 + w * i (b q ′ ) • d(μ 1 (τ ), μ1i (τ )) T * (b q ′ ) -1 ≥ α log δ -1 ,where the first equality is from (3.3), the second equality is from (B.8), and the last inequality is from (B.13). Finally, for α ≥ 1 + 6 log log δ -1 / log δ -1 , we obtainZ i (τ ) ≥ log (log δ -1 ) 6 δ ≳ log 2(log(2/δ))) • (nL 2 + nL 1 ) α δ = β(τ, δ/2),which completes the proof.Proof of Lemma B.5. Recall that the result of Lemma 4 of Ménard and Garivier [36] is: for μn ≤ µ,P(∃N ≤ n ≤ M, d(μ n , µ) ≥ γ) ≤ e -N γ . (B.14)By Lemma 1 of Harremoës [20] , we haved(x, µ) = µ x y -x V (y) dy ≤ (x -µ) 2 2V 0 , (B.15)where V (y) is the variance of the distribution with mean y. As a simple consequence of (B.15) and (B.14), we haveP(∃N ≤ n ≤ M, μn ≤ x) ≤ e -N (x-µ) 2 /(2V0) . (B.16)For the case when μn ≥ µ, we can directly follow the idea of Lemma 4 of Ménard and Garivier [36] .For the case μn ≥ µ, we aim to showP(∃N ≤ n ≤ M, d(μ n , µ) ≥ γ) ≤ e -N γ . (B.17)We let M (λ) be the log-moment generating function of ν θ . Recall that dν θ dρ (x) = exp(xθ -b(θ)). We use the following properties of one exponential family.1. M (λ) = b(θ + λ) -b(θ); 2. KL(ν θ1 , ν θ ) = b(θ) -b(θ 1 ) + b ′ (θ 1 )(θ -θ 1 ); 3. E[ν θ ] = b ′ (θ). Let E[ν θ ] = µ. Let λ = θ 1 -θ, z = b ′ (θ 1 ) > µ, and γ = d(z, µ), we have γ = d(z, µ) = KL(ν θ1 , ν θ ) = λz -M (λ). Since d(z, µ) is monotone increasing for z > µ, we obtain λ > 0. If event {∃N ≤ n ≤ M, d(μ n , µ) ≥ γ} and μn ≥ µ, one have μn ≥ µ, λμ n -M (λ) ≥ λz -M (λ) = γ, λnμ n -nM (λ) ≥ N γ.By Doob's maximal inequality for the exponential martingale exp(λnμ n -nM (λ)),P(∃N ≤ n ≤ M, d(μ n , µ) ≥ γ) ≤ P(∃N ≤ n ≤ M, λnμ n -nM (λ) ≥ N γ) ≤ e -N γ . (B.18)Combining above inequality and (B.15), we obtain for μn ≥ µP(∃N ≤ n ≤ M, d(μ n , µ) ≥ γ) ≤ e -N (x-µ) 2 /(2V1) . (B.19)This completes the proof.In this proof, we define "one round" as a single iteration of the While Loop of Algorithm 2.Proof of Theorem 4.2. Proof of Correctness. We first show that the best arm is not eliminated by Line 11 for any round r. For any l, let E l be defined as follows.E l = {1 ∈ S r , ∀r ≤ l}. (C.1) Lemma C.1. Line 11 of Algorithm 2 satisfies r≥1 P pr 1 ≥ pr * - ϵ r 4 E r ≥ 1 - δ 8 .To streamline our presentation, we define ℓ js = s, γ js = (δ j ) 2 s , and pjs i as the sth updates of parameters ℓ j , γ j , and pj i , respectively, within the second For Loop. For any fixed j, we define U j (s) to be the following set of rounds, where ℓ j remains to be the same value s: U j (s) := {r = 1, 2, . . . : ℓ j = s at round r of Algorithm 2}.(C.2)Then the condition of Line 21 could be represented as ∃i ∈ S j and r ∈ U j (s), pjs i ≥ pr * -ϵ j 2 .The following lemma shows that with high probability, Algorithm 2 will not return at Line 22.Lemma C.2. Line 21 of Algorithm 2 satisfiesP j≥1 s>1 r∈Uj (s) max i∈Sj pjs i < pr * - ϵ j 2 ≥ 1 - 3δ 16 .Note that Algorithm 2 will return arm 1 at Line 24 if 1: Arm 1 is always maintained in S r , and 2: Algorithm 2 never return at Line 22.According to Lemma C.1, there is a probability of at least 1 -δ/8 that Arm 1 will never be eliminated at Line 11. Given that Arm 1 is never eliminated at Line 11, Lemma C.2 suggests that there is a probability of at least 1 -3δ/16 that we will never loop back at Line 22. Hence, with a probability of 1 -δ/2, Stage IV will identify the optimal arm. By incorporating the results of Lemma B.1, we find that with a probability exceeding 1 -δ/2 -δ/2, which is greater than 1 -δ, Algorithm 2 will return the optimal arm. Proof of Sample Complexity. Let N ′ be the sample complexity of Stage IV. Let E = ∩ r>1 E r . The following lemma shows the sample complexity conditioned on event E. Lemma C.3. The expected sample complexity N ′ conditioned on event E has the orderE[N ′ | E] = O i>1 log n/δ log(∆ -1 i ) ∆ 2 i .Now, we consider the expected sample complexity if the best arm is eliminated at some round r. We prove the following lemma. Lemma C.4. The sum of expected sample complexity N ′ at each loop has the orderr≥1 E[N ′ 1{E r , (E r+1 ) c }] = O i>1 log n/δ log(∆ -1 i ) ∆ 2 i .The number of pulls of all arms in the first three stages is no more than max{n log δ -1 , L 2 }. By combining the above results, Lemma C.3 and Lemma C.4 together, we can obtain the following total sample complexityE[N δ ] = O (log δ -1 ) • log log δ -1 + i>1 log nδ -1 log ∆ -1 i ∆ 2 i .Since in the non-asymptotic setting, δ is finite. ThenE[N δ ] = O i>1 log n log ∆ -1 i ∆ 2 i .Proof of Batch Complexity. Just as we discussed in the proof of sample complexity, we first demonstrate the batch complexity conditioned on the event of E.Lemma C.5. Conditional on event E, Algorithm 2 conducts O(log(1/∆ -12 )) batches in expectation.Let B ′ be the number of batches we used in Stage IV. We consider the expected batch complexity if the best arm is eliminated at some round r. We prove the following lemma.Lemma C.6. The sum of expected batch complexity B ′ at each loop has the orderr≥1 E[B ′ 1{E r , (E r+1 ) c }] = O(log(1/∆ -1 2 )).By combining Lemma C.5, Lemma C.6, the fact that the first three stages use O(log(1/δ)) batches, and δ is a constant in non-asymptotic setting, the batch complexity of Algorithm 2 is O(log(1/∆ -1 2 )).Proof of Theorem 4.3. Let E 0 be the event defined in (B.1) in the proof of Theorem 3.1. From Lemma B.4, if δ is sufficiently small and E 0 holds, then Algorithm 2 will return at Stage III. Note that the expected number of pulls in Stage IV is ≲ (log δ -1 ) 2 . Hence, the expected number of pulls of all arms is no more than 2(log δ -1 ) 2 times. Therefore, for any ϵ ′ > 0E[N δ ] ≲ αT * (b) log δ -1 + o(log(1/δ)) + 1{E c 0 }2n(log δ -1 ) 2 ≲ αT * (µ) log δ -1 + 2n. (C.3) Therefore, lim δ→0 E µ [N δ ] log δ -1 ≤ αT * (µ), Moreover, there exists some universal constant C, such that the expected number of batches used in Stage IV is ≲ C log(1/∆ 2 ) • 1{E c 0 } ≲ o(1), where the last inequality is due to Lemma B.3. Form Theorem 3.3, the batch complexity of the first three Stage is 3 + o(1). Therefore, the total expected batch complexity is 3 + o(1).The proof of the supporting lemmas requires the following concentration inequalities. Lemma D.1. [41, Theorem 2.2.6] Let X 1 , . . . , X k ∈ [0, 1] be independent bounded random variables with mean µ. Then for any ϵ > 0P(μ ≥ µ + ϵ) ≤ exp - kϵ 2 2and (D.1)P(μ ≤ µ -ϵ) ≤ exp - kϵ 2 2 , (D.2) where μ = 1/k k t=1 X t . D.1 Proof of Lemma C.1From Lemma D.1,P |p r i -µ i | ≥ ϵ r 8 ≤ 2 exp - 2d r ϵ 2 r 64 = δ r .Applying union bound, we haveP r≥1 i∈[n] |p r i -µ i | ≥ ϵ r 8 ≤ r>1 i∈[n] δ r ≤ r>1 δ 40π 2 • r 2 ≤ δ 8 . (D.3)The aforementioned inequality suggests that, with a probability of at least 1 -δ/8, the condition |p r i -µ i | ≤ ϵr 8 holds true for any i ∈ [n] and r ≥ 1. Then, for any r > 1,pr 1 ≥ µ 1 - ϵ r 8 ≥ µ * - ϵ r 8 ≥ pr * - ϵ r 4 .Therefore,r≥1 P pr 1 ≥ pr * - ϵ r 4 E r ≥ 1 - δ 8 . D.2 Proof of Lemma C.2From Lemma D.1,P |p js i -µ i | ≥ ϵ j 8 ≤ γ js = (δ j ) 2 s .Applying union bound, we haveP j≥1 s>1 i∈Sj |p js i -µ i | ≥ ϵ j 8 ≤ j≥1 s>1 i∈Sj (δ j ) 2 s ≤ j≥1 s>1 δ 40π 2 • j 2 2 s ≤ s>1 δ 8 2 s ≤ δ 16 . (D.4)Besides, from (D.3), we obtainP r≥1 i∈[n] |p r i -µ i | ≤ ϵ r 8 ≥ 1 - δ 8 . (D.5)Define eventsE 3 = ∩ r≥1 ∩ i∈[n] {|p r i -µ i | ≤ ϵ r /8}, and E 4 = ∩ j≥1 ∩ s>1 ∩ i∈Sj {|p js i -µ i | < ϵ j /8}. If E 3 and E 4 truly hold, we have that (1): for any j and arm i ∈ S j ,µ i ≤ pj i + ϵ j 8 ≤ pj * - 7ϵ j 8 ≤ µ * - 3ϵ j 4 ≤ µ 1 - 3ϵ j 4 ,where the second inequality is due to Line 11 of Algorithm 2; (2): for any fixed j, s, and any r ∈ U j (s), where U j (s) is defined in (C.2) and represents the set of all rounds in which parameter ℓ j is updated for exactly s times,pjs i < µ i + ϵ j 8 ≤ µ 1 - 5ϵ j 8 ≤ pr 1 - ϵ j 2 ≤ pr * - ϵ j 2 .Therefore, if E 3 and E 4 truly hold, the event pjs i < pr * -ϵj 2 consistently holds for all j, s, i ∈ S j , and r ∈ U j (s). It's noteworthy that, according to (D.4), P E 4 ≥ 1 -δ/16, and from (D.5), P(E 3 ) ≥ 1 -δ/8. Therefore,EQUATIONWe first focus on bounding the number of pulls of arm i within the first For Loop. Definer(i) = min r : ϵ r < ∆ i 2 .From Lemma D.1 and the union bound, for r ≥ r(i),P |p r i -µ i | ≥ ϵ r(i) 8 ∪ |p r 1 -µ 1 | ≥ ϵ r(i) 8 ≤ 4 exp - 2d r ϵ 2 r(i) 64 ≤ 4(δ r ) r-r(i) ≤ 10 r(i)-r . (D.6) Let E r i be the event |p r i -µ i | ≤ ϵ r(i) /8 and |p r 1 -µ 1 | ≤ ϵ r(i) /8 truly hold at r-th round. Conditioned on E r i and E,pr i ≤ µ i + ϵ r 8 ≤ µ 1 -∆ i + ϵ r 8 ≤ µ 1 - 3ϵ r 2 ≤ pr 1 -ϵ r ≤ pr * -ϵ r ,which mean arm i will be eliminated. Therefore, the total sample cost of arm i in the first For Loop of Algorithm 2 isr≤ri 32 ϵ 2 r log(2/δ r ) + r>r(i) 10 r-r(i)-1 32 ϵ 2 r log(2/δ r ) =O log(1/δ r(i) ) ϵ 2 r(i) =O log n/δ log(∆ -1 i ) ∆ 2 i .Consequently, if we define H to be the total sample complexity in the first For Loop of Algorithm 2. Then we haveE[H] = O i>1 log n/δ log(∆ -1 i ) ∆ 2 i .Now, we bound the sample complexity within the second For Loop. We let L j be the total number of pulls of arms in S j \ S j+1 within the second For Loop. We letn j = min s ∈ {0, 1, 2, • • • } : B j (δ j ) 2 s • 2 s ≥ H .As per Line 16, n j represents the total count of arm re-pulls in the set S j \ S j+1 . Consequently, we can establish the following bound for L j .L j ≤ (B j -B j-1 ) nj s=0 2 s ≤ B j -B j-1 + δ j H.where the first inequality is because γ j(s+1) = γ 2 js and we pull the arms in S j /S j+1 for totali∈Sj \Sj+1 32 ϵ 2 j log 2 γ js ≤ i∈Sj \Sj+1 32 • 2 s ϵ 2 j log 2 δ j = (B j -B j-1 ) • 2 stimes at Line 18 and the last inequality is because for n j > 1,δ j H ≥ δ j B j (δ j ) 2 n j -1 • 2 nj -1 ≥ B j 2 nj +1 ,where the first inequality is due to the definition of n j . Therefore,j≥1 L j ≤ j>1 B j + H j>1 δ j ≤ 2H.Now, we conclude that conditioned on event E, the total expected sample complexity isO i>1 log n/δ log(∆ -1 i ) ∆ 2 i . D.4 Proof of Lemma C.4 From Lemma D.1, P |p r i -µ i | ≥ ϵ r 2 ≤ 2 exp - 2d r ϵ 2 r 4 ≤ (δ r ) 4 .Applying union bound, we haveP i∈Sr |p r i -µ i | ≥ ϵ r 2 ≤ i∈Sr (δ r ) 4 ≤ (δ r ) 3 . (D.7)The aforementioned inequality suggests that, with a probability of at least 1 -(δ r ) 3 , the condition |p r i -µ i | ≤ ϵ r /4 consistently holds true for any i ∈ S r . Then,pr 1 ≥ µ 1 - ϵ r 2 ≥ µ * - ϵ r 2 ≥ pr * -ϵ r .Therefore,P(E r , (E r+1 ) c ) ≤ (δ r ) 3 . (D.8)For any fixed j, recall the definition of U j (s) in (C.2). Assume E r , (E r+1 ) c truly hold and denote U r (s) = {r 1 s , r 2 s , • • • , r s ′ s } as the rounds where ℓ r = s. We note that at r l s -th round, each arm within the first For Loop of Algorithm 2 is pulled at least32 • 4 s+l ϵ 2 r log 2 δ rtimes. Besides, each arm within the second For Loop is pulled at least32 • 2 s ϵ 2 r log 2 δ rtimes. Then, similar to (D.7), for r l s -th round, we haveP ∪ i∈S r l s |p r l s i -µ i | ≥ ϵ r 4 ≤ 2 i∈S r l s exp -2ϵ 2 r 16 • 32 • 4 s+l ϵ 2 r log 2 δ r ≤ i∈S r l s (δ 4 r ) 4 s+l .Then, we apply a union bound over all rounds in U r (s), we obtainP ∪ l∈[s ′ ] ∪ i∈S r l s |p r l s i -µ i | ≥ ϵ 4 ≤ (δ 3 r ) 2 s /2.Moreover, if E r , (E r+1 ) c happens, the best arm is eliminated at r-th round. Then for any rounds in U r (s), we have pulled arm 1 for at least32 • 2 s ϵ 2 r log 2 δ rtimes in the second For Loop. Recall that pjs i is the sth updates of parameter pj i within the second For Loop. From Lemma D.1, we have thatP prs 1 ≤ µ 1 - ϵ r 4 ≤ exp - 2ϵ 2 r 16 • 32 • 2 s ϵ 2 r log 2 δ r ≤ (δ 3 r ) 2 s /2.Therefore, if E r , (E r+1 ) c happens, with probabilityEQUATIONprs 1 > µ 1 - ϵ 4 ,and thus for all l ∈ [s ′ ]prs 1 ≥ µ 1 - ϵ 4 ≥ pr l s * - ϵ 2 ,which means Algorithm 2 returns at Line 22. Before we continue, we will first show that the number of pulls in the second For Loop is lower than the first For Loop. Assume the algorithm stops at r ′ -th round. Let s ′ j = max{s : B r ′ γ js • 2 s > B j }. The number of pulls for S j \ S j+1 at second For Loop is at mosts ′ j s=1 (B j -B j-1 ) • 2 s ≤ s ′ j s=1 B j 2 s ≤ B j • 2 s ′ j +1 = 2 2s ′ j +1 γ js ′ j B j 2 s ′ j γ js ′ j ≤ B r ′ 2 2s ′ j +1 (δ j ) 2 s ′ j ≤ B r ′ δ j .Therefore, the total number of pulls within the second For Loop is at mostj≥1 s ′ j s=1 (B j -B j-1 ) • 2 s ≤ B r ′ j>1 δ j ≤ B r ′ ,which means the number of for the second For Loop is lower than the first For Loop. Finally, we obtainE[N ′ 1{E r , (E r+1 ) c }] ≤ E O s=1 ((δ r ) 3 ) 2 s-1 • B r (δ r ) 2 s 2 s = E[O(δ r B r )] = O i>1 δ r log n/δ log(∆ -1 i ) ∆ 2 i .In the first inequality, we used the fact that if the algorithm stops in some rounds in U r (s), the total number of pulls of all arms is at most B r /(γ js • 2 s ) + B r /(γ js • 2 s ), whcih comes from the first and second For Loop respectively. Moreover, the factor ((δ r ) 3 ) 2 s-1 is because from (D.9), if E r , (E r+1 ) c holds, then Algorithm 2 returns in some rounds in U r (s) (at Line 22) with probability at least 1 -((δ r ) 3 ) 2 s-1. The last equality is because from Lemma C.3, if E r , (E r+1 ) c holds, thenE[B r ] ≤ O i>1 log n/δ log(∆ -1 i ) ∆ 2 i . Finally, r≥1 E[N ′ 1{E r , (E r+1 ) c }] = O i>1 log n/δ log(∆ -1 i ) ∆ 2 i . D.5 Proof of Lemma C.5We note that each round within the While Loop costs one batch. Letr(2) = min r : ϵ r < ∆ 2 2 .Let E r be the eventi>1 |p r i -µ i | ≤ ϵ r(2) 8 |p r 1 -µ 1 | ≤ ϵ r(2) 8 .Conditioned on E r and E,pr i ≤ µ i + ϵ r(2) 8 ≤ µ 1 -∆ i - ϵ r(2) 8 ≤ pr 1 -ϵ r(2) ≤ pr * -ϵ r(2) ,which means all sub-optimal arms have been eliminated and the algorithm returns. From Lemma D.1 and the union bound, for r ≥ r(2),P((E r ) c ) ≤ 4n exp - 2d r ϵ 2 r(i)≤ 4n(δ r ) r-r(i) ≤ 10 r(i)-r . (D.10) Therefore, the total batch cost isr 2 + r≥r2 1 10 r-r2 = O(r 2 ) = O log 1 ∆ 2 .This completes the proof.The proof of this lemma is similar to that of Lemma C.4. we have the following results. 1: From (D.8), we haveP(E r , (E r+1 ) c ) ≤ (δ r ) 3 .2: From (D.9), we have if E r and (E r+1 ) c truly hold, then with fixed ℓ s , Algorithm 2 returns at Line 22 with probability1 -(δ 3 r ) 2 s-1 . (D.11)We first compute the size of U r (s). From Algorithm 2, we know that the arm kept in the set S r will be pulled 4 times larger compared to (r -1)-th round. Besides, we update ℓ r to s + 1, if the number of pulls exceeds B r /((δ r ) 2 s • 2 s ) (Line 16 of Algorithm 2). It is easy to see after log 4 n rounds, the number of pulls of any arm exceeds B r and then after ln 1 (δr) 2 s •2 s rounds, the number of pulls of single arm exceeds B r /((δ r ) 2 s • 2 s ). Therefore, the size of U r (s) is at most ln 1 (δr) 2 s •2 s + ln n. We let U be the total number of rounds used. Then, we obtainE[U • 1{E r , (E r+1 ) c }] ≤ r • P(E r , (E r+1 ) c ) + E O s=1 ((δ r ) 3 ) 2 s-1 • ln n + ln 1 (δ r ) 2 s • 2 s ≤ rP(E r , (E r+1 ) c ) + δ r .We have shown in Lemma C.5, r>1 rP(E r , (E r+1 ) c ) = O(log(1/∆ 2 )). Therefore, the total number of rounds is∞ r≥1 E[U • 1{E r , (E r+1 ) c }] = O(log(1/∆ 2 )),which completes the proof.In this section, we compare our algorithms Tri-BBAI and Opt-BBAI with Track-and-Stop [17] , Top-k δ-Elimination [22] , ID-BAI [23] and CollabTopM [32] under bandit instances with Bernoulli rewards. All the experiments are repeated in 1000 trials. We perform all computations in Python on R9 5900HX for all our experiments. The implementation of this work can be found at https://github.com/panxulab/Optimal-Batched-Best-Arm-Identification Data generation. For all experiments in this section, we set the number of arms n = 10, where each arm has Bernoulli reward distribution with mean µ i for i ∈ [10] . More specifically, the mean rewards are generated by the following two cases. • It should be clear whether the error bar is the standard deviation or 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 a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Justification: The research conducted in the paper conforms, in every respect, to the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Specifically, log * (n) denotes the number of times the function log(•) needs to be applied to n until the result is less than 1.Non-asymptotic here refers to finite confidence. In this paper, we use names non-asymptotic and finite confidence interchangeably.Due to the space limit, we put the experimental results in Appendix E.To derive the near-optimal non-asymptotic sample complexity, α should be 1. However, As explained in their original paper, the algorithm will be sub-optimal if we set α close to 1.Recent work by Kaufmann and Koolen[34] offers improved deviation inequalities allowing for a smaller selection of β(t, δ) without sacrificing the asymptotic optimality. However, it remains uncertain whether this refined parameter choice is applicable to our batched bandit problem. For ease of presentation, we use the parameter choice of β in Garivier and Kaufmann[17].If event E occur for a sufficiently small δ > 0, it signifies that there exists a δ0 ∈ (0, 1) such that for all δ ≤ δ0, event E consistently holds.From Theorem 3.1, we can select α to be any constant within the range (1, e/2). To optimize the convergence rate of E[N δ ]/(log(1/δ)T * (µ)), we set α slightly above 1, specifically we choose α = 1.001. 


Decision: This paper discusses the best arm identification in the bandit problem under the batched setting. Two algorithms are proposed for this problem. The first one achieves the asymptotic optimality with respect to the error probability within almost three batches, and the second algorithm achieves the optimality in both the error probability and other parameters with the number of batches depending on the gap parameter. Results of experiments are given in the appendix to verify the performance of the algorithms.

The main strength of the paper is that the proposed algorithms achieve good sample complexities with a theoretically and empirically very small number of batches in various settings. On the other hand, there are several concerns on the writing/structure of the paper and comparison with other algorithms. The authors gave a plan of the revision to address these concerns and some additional results of the experiments are shown in the rebuttal. I judged that they are reasonable and I determined to recommend acceptance, but I expect that the authors very carefully revise the paper so that it falls within a minor revision while addressing all the above concerns.

Another criticism on the paper is that the asymptotics in $\delta$ is not very important. Though I partly agree that very small $\delta$ is practically not realistic, I think it is still significant that the optimality in $\delta$ is achievable jointly with the optimality in other parameters unless the criticism is accompanied with some support on the triviality of this combination. Still, I expect that the authors explain the significance on this point more clearly in the final version.

Following is my own comment to the paper:
- On Algorithm 1: in Line 15, $t$ and $\tau_q$ are opposite? I also got a similar concern on the unused notation as YCPj like $\tau_q$, and I hope that the authors very carefully check them.
- My concern is that, not only the sample complexity is 2-3 times worse than the Track-and-Stop algorithm even for $\delta=10^{-10}$, its slope with respect to $\log 1/\delta$ also seems 4-5 times worse even though $\alpha=1.001$ (very close to 1) is used in the experiments. This seems to mean that the asymptotic behavior in e.g. Theorem 3.1 does not appear even in this extremely small $\delta$. I think there should be some discussion on this point in relation with the concern by Uhz8. Related to this, why is $\alpha=1.001$ used in the experiments rather than $\alpha=1+1/\log \delta^{-1}$ suggested below Theorem 3.1? I don't see the necessity of the use of $\alpha$ very close to 1 if the asymptotic behavior cannot be observed.

Reviews: review: paper_summary: paper_summary: The paper presents two novel algorithms for the batched best arm identification (BBAI) problem. The first is the Tri-BBAI algorithm, which employs three batches with the expectation of achieving the asymptotic optimal sample complexity. Based on Tri-BBAI, the authors conceived the Opt-BBAI algorithm, which achieves the near-optimal sample and batch complexity when δ is finite and it does not tend to 0. Opt-BBAI enjoys the same sample and batch complexity of Tri-BBAI for the asymptotic setting
strength_weakness: strength_weakness: - The paper dedicates a significant portion to the introduction and related works, only beginning to describe methodologies and algorithms on page 5. I suggest reducing the introductory section to allow more space for discussing comparisons with existing algorithms (Table 2) and for elaborating on the experimental results.
- The paragraph on the notation is partially useful, since it presents some notations that are never utilized in the main paper, but only in the appendix and may be employed to describe other unclear symbols.
- I found some statements a bit misleading. For example, at line 251 the period ”In this section, we introduce Opt-BBAI, which can attain the optimal sample and batch complexity in both asymptotic and non-asymptotic settings adaptively [...]” is in contrast with lines 255-256 where, always regarding Opt-BBAI, is correctly said that ”we can achieve asymptotic optimality and near non-asymptotic optimality adaptively[...].
- The claim at line 714 ”the sample complexity of Tri-BBAI and Opt-BBAI [...] is at most 2.6 times greater than Track and Stop when δ is very small” is not true, since in the second experiment for δ = 1 × 10−10 the ratio is evidently larger.
questions: questions: - Reward distributions are assumed to belong to a single one-parameter exponential family, a common choice in literature. Are there any limitations in choosing different reward distributions that could affect the effectiveness of the presented approach?
- I have some doubts about the necessity of presenting both Tri-BBAI and Opt-BBAI in the paper. If Opt-BBAI achieves the same performances of Tri-BBAI in the asymptotic settings, why is it necessary to describe Tri-BBAI as well, considering that Opt-BBAI also addresses non-asymptotic settings? Could you explain and give some intuition about the need to
present Tri-BBAI?
- The choice of exactly three batches in the Tri-BBAI algorithm is not entirely clear. Additionally, I would like to ask the authors to provide some intuition regarding the optimal batch complexity of 2 for both Tri-BBAI and Opt-BBAI (shown in Table 1) compared to the structure of Tri-BBAI algorithm which employs at most 3 batches. What is the intuition behind these results? Why was a 2-batch algorithm not considered from the beginning?
- Experiments have been carried on crafted environments. Since authors argued about the benefits that their work would bring in real-world settings, I would expect to find an experiment on a such real-world scenario.
limitations: limitations: N/A
paper_summary: paper_summary: This paper considers the problem of BAI in the fixed confidence setting, in the context of finding the best arm in as few batches as possible. That is, instead of observing the reward of each arm pulled in turn, the learner makes multiple pulls in a single batch and only observes all rewards after the completion of said batch. The first result of the paper is to show that it is possible to achieve asymptotically optimal sample complexity, with only a constant number of batches. Specifically the authors propose the Tri-BBAI algorithm, which is shown to have asymptotically optimal sample complexity, PAC guarantees and requiring at most 3 batches in expectation, Theorems 3.1, 3.2, 3.3 respectively.

The authors then describe a second algorithm Opt-BBAI which has near optimal finite confidence guarantees as well as being asymptotically optimal.
strength_weakness: strength_weakness: When considering finite confidence guarantees the authors could also compare with the recent work "An ε-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond", Jourdan, Degenne, Kaufmann.
questions: questions: Do the authors have an idea as to why the Tri-BBAI has poor experimental performace against Track and Stop?
limitations: limitations: No concern.
paper_summary: paper_summary: The paper "Optimal Batched Best Arm Identification" introduces Tri-BBAI and Opt-BBAI algorithms to identify the best arm in multi-armed bandit settings. Tri-BBAI achieves optimal sample complexity with only three batches on average as the confidence parameter $\delta$ approaches zero. Opt-BBAI extends Tri-BBAI for finite-confidence settings, providing near-optimal sample and batch complexities for finite $\delta$.
strength_weakness: strength_weakness: First, I don't think the regime when $\delta$ approaches $0$ is interesting. In a typical scenario, we want to set the confidence relatively small, and it doesn't make a lot of sense to consider the algorithm's performance on extremely small values.

The paper doesn't fairly compare previous results. It mentions the work "Collaborative top distribution identifications with limited interaction," and work "Optimal streaming algorithms for multi-armed bandits", but it doesn't include it in the table, which can lead to the impression that Opt-BBAI is the first algorithm to achieve $O(\log \frac{1}{\Delta_{2}})$ batch complexity. However, many algorithms have already achieved similar results. Moreover, these algorithms are not included in experiments. Significant work should be done to implement a fair comparison and properly acknowledge other works.
questions: questions: N/A
limitations: limitations: N/A
paper_summary: paper_summary: This paper studies the Batched Best Arm Identification (BBAI) problem in multi-armed bandits. The goal is to design an efficient algorithm that correctly finds the arm with the highest mean with probability $\ge 1 - \delta$, while minimizing: (1) the sample complexity, defined as the total number of arm pulls; (2) the "batch complexity", defined as the number of rounds in which the algorithm requests arm pulls. (Formally, the algorithm specifies the number of times it pulls each arm in the $r$-th round after observing all the outcomes in the previous $r-1$ rounds.)

The main results of this work are:
- An algorithm (termed Tri-BBAI) that achieves an asymptotically (i.e., as $\delta \to 0^{+}$) optimal sample complexity in three batches in expectation.
- Another algorithm (termed Opt-BBAI) that achieves: (1) near-optimal sample and batch complexities in the non-asymptotic setting; (2) the same guarantees as Tri-BBAI in the asymptotic setting.
strength_weakness: strength_weakness: I think a major weakness of the work is that its main result is fairly intuitive, and arguably, its proof does not give new insights to the design of pure exploration algorithms. Here is why: For simplicity, suppose that we only have two arms with means $1/2+\epsilon$ and $1/2-\epsilon$, and the parameter $\epsilon > 0$ is *unknown*.

In this case, the "natural" algorithm is to make geometrically decreasing guesses on $\epsilon$: $\epsilon_1, \epsilon_2, \ldots$, where each $\epsilon_k = 2^{-k}$. At guess $\epsilon_k$, we would pull each arm $(1/\epsilon_k)^2$ times to get an $O(\epsilon_k)$-approximation of the means. If the means are clearly separated, we get the answer; otherwise, we continue with smaller guesses. Clearly, this approach requires many rounds ($\Omega(\log(1/\epsilon))$ rounds) of adaptivity.

On this instance, very roughly speaking, the authors' approach is to start with the guess, say, $\epsilon_k = 1/\log^{1/3}(1/\delta)$. For each fixed $\epsilon$, when $\delta$ is small enough, the guess would be smaller than the actual $\epsilon$, and the algorithm wins the game in $O(1)$ rounds. Also, this first round only takes $(1/\epsilon_k)^2 = \log^{2/3}(1/\delta) \ll \log(1/\delta)$ samples, so this will not affect the asymptotic behavior as $\delta \to 0^{+}$.

In general, the Tri-BBAI algorithm uses a round-robin strategy as an inefficient exploration round. The length of this round is chosen as a function of $\delta$, so that the asymptotic behavior is not affected. Therefore, for each fixed instance, there exists some $\delta_0 > 0$ such that whenever $\delta < \delta_0$, this inefficient exploration succeeds with a good probability, and may guide the algorithm to sample in an asymptotically optimal way in the rest. As a result, this asymptotic optimality might only hold for extremely small values of $\delta$: From Line 492, the analysis needs $1/\log\log(1/\delta) = \epsilon \le \Delta_2$ to go through; in other words, $1/\delta$ needs to be **doubly exponential** in $1/\Delta_2$.

Admittedly, this weakness was addressed by the other algorithm Opt-BBAI, which achieves a sample complexity bound for finite $\delta$ as well. However, it should be noted that the complexity contains a $\sum_{i=2}^{n}(1/\Delta_i)^2\log n$ term, which could be higher than the optimal sample complexity by a $\log n$ factor. In contrast, the state-of-the-art bounds for (non-batched) BAI (e.g., [Karnin-Koren-Somekh, ICML'13][Jamieson-Malloy-Nowak-Bubeck, COLT'14][Chen-Li, arXiv'15][Chen-Li-Qiao, COLT'17]) are tight up to a doubly-logarithmic factor.

Despite the weakness mentioned above, I think this submission presents some solid work and a nice observation (Lines 72-73), namely, the need for many rounds of adaptivity only arises when $\delta$ is small (or moderate), and goes away when we focus on the asymptotic regime. Therefore, I lean towards accepting the paper.
questions: questions: I don't have specific questions for the authors.
limitations: limitations: Limitations have been adequately addressed.

Comments: comment: Thank you for your reply. We would like to summarize our responses to your review as follows:

1. You raised concerns that the asymptotic setting (as $\delta$ approaches 0) is not interesting.
2. You noted the omission of two related works (‘Collaborative Top Distribution Identification with Limited Interaction’ and ‘Optimal Streaming Algorithms for Multi-Armed Bandits’) from our comparison table.

In our previous response, we addressed these points, which we believe are relatively minor and do not detract from the overall significance of our technical contributions. Specifically:

* We demonstrated that the asymptotic setting is not only widely studied in the literature but also holds practical significance (see A1 for more details).
* We emphasized our substantial contributions to the non-asymptotic setting (finite $\delta$), as discussed in both our paper and the previous response.
* We clarified that 'Optimal Streaming Algorithms for Multi-Armed Bandits' is not designed for  the batched bandit setting, and that we have already cited the main results of 'Collaborative Top Distribution Identification with Limited Interaction' in Lines 151 and 152 of our paper.
* We committed to add more discussions on these papers and add related results in our comparison table and we have conducted additional experiments in the rebuttal which will be included in the revised manuscript.

We hope this summary clarifies our position and the steps we have taken to address your concerns.

Best regards,

Authors
Thank you for your feedback; I will keep my score as it is.
Thank you for your response, I will maintain my score.
Thanks for the answers to my concerns. They are satisfactory.
Dear Reviewer 3W3Z,

We would like to know whether our responses have addressed your concerns. If there are any additional questions or areas that require clarification, please do not hesitate to let us know.

Thank you.
Dear Reviewer YCPj,

We would like to know whether our responses have addressed your concerns. If there are any additional questions or areas that require clarification, please do not hesitate to let us know.

Thank you.
Dear Reviewer vkzZ,

Thanks again for reviewing our paper. As the end of the discussion period approaches, we would like to know whether our responses have addressed your concerns. If there are any additional questions or areas that require clarification, please do not hesitate to let us know. We highly value your perspective and, if you find our responses satisfactory, would be grateful if you would consider raising your score for our paper.

Thank you.