Optimal Estimation of the Best Mean in Multi-Armed Bandits
Authors: Takayuki Osogami
Junya Honda
Junpei Komiyama
Venue: NeurIPS 2025 poster ()
Keywords: confidence ellipsoid
sample complexity
pure exploration
probably approximately correct
non-convexity
Primary area: general_machine_learning
TL;DR: We propose an algorithm for estimating the best mean reward in a multi-armed bandit with asymptotically optimal, instance-adaptive sample complexity.

Abstract: We study the problem of estimating the mean reward of the best arm in a multi-armed bandit (MAB) setting. Specifically, given a target precision $\varepsilon$ and confidence level $1-\delta$, the goal is to return an $\varepsilon$-accurate estimate of the largest mean reward with probability at least $1-\delta$, while minimizing the number of samples. We first establish an instance-dependent lower bound on the sample complexity, which requires handling the infinitely many possible candidates of the estimated best mean. This lower bound is expressed in a non-convex optimization problem, which becomes the main difficulty of this problem, preventing the direct application of standard techniques such as Track-and-Stop to provably achieve optimality. To overcome this difficulty, we introduce several new algorithmic and analytical techniques and propose an algorithm that achieves the asymptotic lower bound with matching constants in the leading term. Our method combines a confidence ellipsoid-based stopping condition with a two-phase sampling strategy tailored to manage non-convexity proposed algorithm is simple, nearly free of hyperparameters, and achieves the instance-dependent, asymptotically optimal sample complexity.  Experimental results support our theoretical guarantees and demonstrate the practical effectiveness of our method.

Optimal Estimation of the Best Mean in Multi-Armed Bandits
Takayuki Osogami IBM Research Tokyo osogami ibm. com
Junya Honda Kyoto University, RIKEN AIP honda@i ky ac. jp
Junpei Komiyama
New York University, RIKEN AIP Sanpei@komyyam inno info
Abstract
We study the problem of estimating the mean reward of the best arm in multi- armed bandit (MAB) setting. Specifically, given a target precision e and confidence level 1 - 5, the goal is to return e-accurate estimate of the largest mean ward with probability at least 1 - 6, while minimizing the number of samples. We first establish an instance deeteneedde lower bound the sample complexity, which requires handling the infinitely many possible candidates of the estimated best mean. This lower bound is expressed in non-convex optimization prob- lem, which becomes the main difficulty of this problem, preventing the direct application of standard techniques such as Track-and-Stop to provably achieve optimality. To overcome this difficulty, we introduce several new algorithmic and analytical techniques and propose an algorithm that achieves the asymptotic lower bound with matching constants in the leading term. Our method combines a confidence ellipsoid-basee stopping condition with a two-phase sampling strategy tailored to manage non-convexity proposed algorithm is simple, nearly free of hyperparameters, and achieves the instance- dependent asymptotically optimal sample complexity. Experimental results support our theoretical guarantees and demonstrate the practical effectiveness of our method.
Introduction
Al agents and foundation models are developed be adapted for, applied to, wide range of tasks, users, and deployment contexts. Given this diversity of applications, it is essential to ensure that these systems perform reliably even under challenging foundation model should provide a minimal level of utility across various downstream tasks, and an AI agent should consistently satisfy all required safety criteria [14.. In other words, before deployment, we must ensure that the expected performance is acceptable even in worst-case scenarios.
unfavorable conditions. For example,
This problem of evaluating expected performance in the worst-case scenario can be naturally formu- lated within the multi-armed bandit (MAB) framework as the task of estimating the mean of the best arm (i.e., best-mean estimation). This paper adopts the standard MAB convention in which rewards are to be maximized and focuses on designing an algorithm that accurately estimates the best mean.
Our primary focus in algorithm design is minimizing sample complexity, motivated by the substantial cost of evaluating Al agents and foundation models, This concern particularly relevant given the growing trend toward inference-time time reasoning [16] 7 [23] which often demands substantial test- test-time computation. An AI agent may rely on Best-of-N sampling with millions or billions of candidates or Monte Carlo tree search to select its next action [24] making each evaluation costly.
16 7
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

More specifically, we develop a probably approximately correct (PAC) algorithm for best-mean estimation, achieving asymptotically optimal sample complexity. The algorithm guarantees an estimation error of at most with probability at least - 6, and the expected number of samples it uses matches the theoretical lower bound that we establish in this paper. This ensures that, as - 0. the sample complexity achieved by our algorithm is asymptotically optimal.
Our lower bound proof leverages the approach of [2). which addresses the problem of selecting an arm when multiple (a finite number of) correct arms may exist. However, our setting differs in a crucial way: we must select a real-valued estimate of the best mean from infinitely many possibilities. This fundamental distinction requires modifications to the technique in (2]. We show that, for Gaussian rewards, any algorithm must use at least 2R ((4 (1g
(log(1/6)) samples in expectation. where f(p) is the optimal value of an optimization problem that characterizes the optimal allocation of samples among arms. While [(z) = (e(²) in the worst case, it instance-dependent and can be significantly smaller. The key challenge, therefore, is to design an algorithm that adapts to the structure of each instance and achieves the corresponding sample complexity.
Our algorithm builds on the martingale-bate based anytime confidence bound introduced by M. a tech- nique that has been widely adopted in the linear bandit literature. We adapt this technique in a novel way to the MAB setting, using it to jointly estimate the expected rewards of arms as a confidence ellipsoid. A key insight is that this ellipsoidal representation enables efficient testing of global hypotheses- -scch as whether at least one arm has an expected reward above a given threshold u' w'-which would be difficult to verify using conventional, per-arm confidence intervals. Moreover, to achieve asymptotically optimal sample complexity, we conduct a detailed analysis showing that the original (K + 1) d-dmmensional non-convex characterizing optimization problem can be reduced to a -ineennniio non-convex optimization over a narrow interval. This enables efficient grid search within the narrow interval to optimize the allocation of samples used by our algorithm.
The primary contribution of this paper is a novel PAC algorithm for best-mean estimation, with sample complexity that is asymptotically optimal. A key challenge in our analysis lies in handling the non-convexity of the characterizing optimization problem, which makes it difficult to ensure that the sample allocation closely upproximates the optimal one. To validate our theoretical analysis and highlight the practical relevance of our approach, we also present numerical experiments. These results illustrate not only the empirical advantages of the algorithm but also certain limitations that are not captured by the asymptotic theory.
Related work
Our problem can viewed as an instance of pure exploration problems, which requires identifying quantity that depends on unknown parameters. The most relevant literature in this context is fixed-confidence e-best arm identification K 10
X where the goal is to identify one of the e-best arms with confidence 1 8. However, our problem and e-best arm identification Identifying an g-best arm does not guarantee that the best mean is estimated within E error, since all estimated means can have greater than errors. Conversely, our problem of fixed-confidence e-best-mean estimation does not guarantee that an e-best arm is identified. However, our algorithm can be used for 2;- arm identification, since it finds U such that all means are below U as well as an arm with mean at least U - 2s. We empirically compare our algorithm with a representative e-best arm identification algorithm, UGapEc 44 adapted for best-mean estimation in Section 7
different.
The utility of the Track-and-Story algorithm 5 for pure exploration problems is shown in 2 While the idea of Track-and-Sto could potentially be applied to best-mean estimation, the non-convexity of the characterizing optimization problem prohibits us from establishing the continuity of its optimal solution with respect to the true means, which is utilized by Track-and-Stop. On the other hand, our two-phase algorithm leverages the continuity of the optimal value to guarantee its asymptotic optimality. Deriving the optimal sample complexity of gradient-based methods, such as the one in 21. is challenging due to the non-convex nature of the underlying optimization problem, which can result in convergence to suboptimal solutions.
Although non-convexity also appears in the characterizing optimization problems of classical best arm identification, those optimization problems typically allow convex reformulation (e.g.. [2] 21) Also, Russo and Pacchiano deal with the non-convexity by convex relaxation, which is shown to lose optimality at most by factor of 4 [15). On the other hand, we solve our nonconvex optimization

---

problem by decomposing it into convex subproblems and reducing it to a one-dimensional optimiza- tion problem within narrow interval specified later, which we can solve via grid search with an arbitrary accuracy.
Best-mean estimation has been studied by 13 where it arises as subproblem in mechanism
design-specifically, in ensuring that desired properties hold across all agent types. [3] proposes
simple two-step approach: first identifying an (2/3)e-best arm with confidence level 8/2. 2. then
collecting enough additional samples from it to meet the required guarantee. This method achieves a sample complexity of (((K/=") ( and a matching lower bound of (2((K is established. In contrast, our results provide sharp, instance-dependee upper and lower bounds, with matching constants in the leading term, establishing that, for each instance, our algorithm has asymptotically optimal sample complexity.
/E") log( (1/))
The problem of best-mean estimation also arises frequently in both machine learning and reinforce- ment learning. In machine learning. it corresponds to estimating the expected performance of the optimal predictor (9] while in reinforcement learning, it corresponds tht] is, the maximum expected return from a state, achieved by selecting the optimal action at each state. While prior work in these areas focuses on how to best estimate the best mean given fixed set of samples [20), our work addresses a complementary question: how to efficiently sample to estimate the best mean with high confidence.
estimating the value function
3 Settings
We consider a multi-armed bandit (MAB) setting with K arms, where each arm E [K] = , K} is associated with reward distribution having mean 14. We assume that the reward distributions are R-sub-Gaussian (i.e., the reward X; from each arm i satisfies Pr([X.] 2 x) S 2 exxp(-2²/R3 for known constant R), and that the means constant 5 (i.e., maX;e[K] |14 I S). Let μ == max,g[K [K] H4 denote the mean of the best arm (best mean) and i" argmax; b4 be the index of best arm. In the case of multiple optimal arms, we break ties arbitrarily and fix one such arm as i*, We denote the full mean vector by == (μi, (2,., ,K) and define the suboptimality gap for arm as A. 1r p4;
bounded in magnitude by known
Our objective is to design an algorithm that adaptively samples from the K distributions and stops after random number of samples, denoted by Upon termination, the algorithm outputs estimate f* of the best mean such that 11 - f= I E holds with probability at least 1 - 8, for given parameters (c, In Section 7.3 discuss equivalent formulation of returning interval of length 2e that contains je with probability at least
5. The sample complexity of the algorithm is defined as E[r], where the expectation is taken with respect the underlying reward distributions. Throughout, we use the following notations: (x)+ = max(O, x). x V y = max x. y and x A y = min(2; x. y-
4 Sample Complexity Lower Bound
We start by deriving the following lower bound on the sample complexity R[7] of our best-mean estimation (BME) problem:
Theorem Consider any algorithm that returns an e-accurate estimate of the best mean with probability at least 1 - 5. Then, when rewards follow Gaussian distribution with variance R2, the sample complexity is lower bounded as follows:
Epp [T]
lim inf 810
2R s(p),
log(1/0)
where (11) is the optimal objective value of the following optimization problem:
(P1)
min "UE(p" . +26)
Σ
(2)
KE[K]
s.1.
ri (U -m:) 2 Vi E [K]
(3)
Σ
rs (14 - U + 28)2 21.
(4)
KE(K]
3

---

14400
NU;N)
14300
min RU:p)
(US
14200
14100
14000
13900
1.15
1.16
1.17
1.18
0
Figure 1: Non-uniqueness of the optimal solution for (PI).
Here, we outline the full proof of the theorem provided in Appendix A.I
In the proof, we introduce multiple correct answer problem (MCP) that can be reduced to BME in the sense that an algorithm for BME can also solve this MCB. We then obtain a lower bound for BME from a lower bound for MCP, which is established primarily consider a lower bound for Gaussian rewards, similar to [8) but an analogous, albeit less explicit, lower bound may be obtained for more general distributions from that of the M-bin MCP.
(see Lemma 7 in Appendix [A.]]. We
Specifically, consider the following M-bin MCP problem with parameter M E N, which defines e' =/M.. The problem asks return a bin from finite set, B {(-00,
[)" E, E+ - E + e', _t E + 2='). ..... [1* + E, μ E+E [u + EE, oo)), where the answer considered correct if it is in 6* (p) = {6 B bn [p E. p² + * 0). Notice that any 6-correct algorithm for BME can be converted into a ò-correct algorithm for the M-bin MCP by simply mapping the output of the BME algorithm the bin that contains the output.
In Lemma@[Appenditn II. we show that, for any > O, there exists a large M such that the sample complexity of the M-bin MCP bounded from below by 2(1 - 11) I2' Rt² I (1x log(1/0) ((log(1/)) where ((()) is the optimal objective value of (PI). Letting r] - O, we establish that any 6-correct algorithm for BME-one that returns e-accurate estimate of μ with probability at least 8 for any mum incur sample complexity of at least 2 [(u) log(1/5) - o(log(1 (1))).
The optimization problem (PI) plays central role in our analysis: besides it provides a lower bound on sample complexity, it characterizes the minimal number of samples required from each arm i [K] to estimate the best mean to match this bound asymptotically. Specifically, 2R²r; log(1/5) represents the number of samples that should be taken from arm E [K].
Note that Eq. 2 is non-convex optimization over (r, U). An important observation is that, when we fix the value U E (μ²,, n=* 2s). the corresponding subproblem, given by
(P2) min Σ KE]K]
s.t. the same constraints as (PI) for a given U
(5)
a convex optimization over r. We denote the optimal solution and value of (P2) by (U: ( and fU p), respectively. Although fU: μ1) depends on E, we regard E as a fixed constant and often omit its dependence throughout the paper for brevity. The optimal solution (P1) is then given by U(+)= = argming E(u" _ +2s) SUU (4) and re( = (U (U)); and we define the corresponding optimal value as f(u) = min .a" +2c) f(U;
Figure I illustrates numerical example highlighting the nonconvex nature of the optimization problem (P1). Specifically. it shows the objective value (U; μ1) of (P2) as a function of U, revealing the existence of multiple disconnected local minima, which leads to discontinuities in the optimal allocation and complicates the analysis compared to settings where convex reformulations are possible. See Appendix [.8 for further details.
Since (P1) is nonconvex optimization, giving upper and lower bounds of the optimal solution U(p) is beneficial for implementation and analysis. To this end, we now introduce additional notations. Let

---

(p) and (p) be the solutions to g(U: pi) = 0 and g(U = 0, respectively, where we define
g4U: 1- (#s U 2
(U - 144
iE|K]
D(U: = (n* U + 26)3
Σ 171
(6)
m,)3
for any E (n*,, 14* + 2e). As we will show below, (1)) and (()) can be used to define a narrow interval in which (p4) is contained. Here, & and 9 monotonically increasing in U, and their roots can be efficiently computed using standard methods such as bisection over the interval [f* μ + 2s].
For convenience, we extend their domains by setting
g(U: g(U 14) -00
for U P for U P² + 22.
g(U: (4) g(U:
The solution the optimization problem (P2) can then characterized as follows:
Lemma 2. The optimal solution and objective value of (P2) satisfy the following properties:
() U(p) E [a- 8,,
4n + +e) and (1)) < 4t + 28.
(ii When U 2 (p)), there is an optimal solution
i i 1t
(m-
(n:-U+2E) (U (ύ-Ee}² i= i" which satisfies ri (1: 2 w- addition, the optimal value satisfies
r(U: p1)
(a- U0te3 (I-Eizi
(8)
m) Σ (U p;)² (1² U + 22)2 ifi
1
1 Σ
(mi U
(9)
(U -U-
(iii) The minimizer of f(U: pi) satisfies U(H) E [U(H), v (()).
(iv) To (U(H): < (KK-1)/++1)²
42a
(v) (U)))
1
-2
The proof of the lemma is postponed to Appendix A.2 Although the function ( is generally non- convex, we can still confine its minimizer U()) = argming f(U; μ1) within a reasonably narrow interval using the bounds, (1)) and (p) V (p). This allows for efficient approximation of the minimizer via grid search over the interval [m()), [()) v U[4)] C [μ* + e, e, + 2s). When (()) 2 U(4), the minimizer (H)), and there is no need for solving the non-convex optimization.
5 Ellipsoid-based Estimation Algorithm
Motivated by the structure of the characterizing optimization, we propose the Ellipsoid- based Es- timation algorithm (EllipsoidEst) shown in Algorithm [ In addition the problem parameters (K, R, R, 8) introduced in Section 3 EllipsoidEst uses regularization parameter X.
EllipsoidEst is characterized by its novel stopping condition based on tight confidence ellipsoid formed by regularized estimators. It also employs two-phase sampling strategy to minimize the need for solving non-convex optimization problems. These components optimal and computationally efficient algorithm for a probably approximately correct (PAC) estimate of the best mean. In what follows, we describe each of these components in detail.
critical to derive an
EllipsoidEst computes upper confidence bounds (UCBs; (t(() + BBt, ())N,(t) in Step 9 where ((t, 8) is defined as
1 + Σ B(, 2R log
x N+(()
NO(1)
Rd log
(10)
5 KE[K]
No(1) +
5

---

Algorithm EllipsoidEst
Require: R. e, problem dependent parameters; A: regularization parameter
1: (2(0) - 0, vi E [
2: [s(t)= < 0, [K]
3: Phase f-1
> There are two phases.
4: for -1, 1,2, do
Phase 2 and N₁. (t 1) rg. 1, 1,6),
5: i(t)
/(t-1.5) argmax; [bi(t - N](-1)
otherwise.
6: Update (t) (t
7:
Pull arm i(t) and obtain reward ((c)))
(1)
8:
Update (t(e)(t) & (e(r)()+XX mml Zi(t).m
U(t) + max, (ai(t) + V N.(()
((C,6)
9:
10:
if LIEK (x(t)((:(t) (() + 2c) 2 8(t, then
11:
Output fi" t U(t) and terminate.
if Phase = and (1)( g(U((t)
then
13:
Phase + 2
Determine the target confidence interval.
14:
it t argmax, (t((t)
15:
Ū U U(((t)
Minimize over U [((A()))T((()))))(((()
r/. t rg. (ū:
and
N.(()
(.(1) = NOO
Σ Timm
(11)
m=1
denotes a regularized estimate of the mean reward based the (t) samples { ........... (i,N,(1) collected up to round
A natural, yet naive, stopping condition would be to terminate when U(t) L,(t) S 2s holds for some arm where (t) is the highest UCB and (t) (tx()) /3(t,))/N, is the lower confidence bound (LCB) for in round t. This condition guarantees that (tt) E E [M* - E, H* +
when the true means simultancously contained in the respective confidence bounds.
When multiple arms have estimated means (t) close to the highest UCB Utt), we can improve upon the naive stopping rule. Namely, EllipsoidEst employs more refined stopping condition, as specified in Step [0] Figure providee an intuitive illustration of this condition the case of two arms. It can be shown that, with probability at least 1 6. the true mean vector lies within the confidence ellipsoid defined by the individual upper and lower confidence bounds. Therefore, U(t) 2s} } lies outside this ellipsoid, we can conclude that the true best-mean must lie within the interval (t) - 2e, (t)], even the confidence interval for each individual arm is not contained in (t) 2z, (t)).
region {(41, (22 #4 V n2
Formally, the stopping condition of EllipsoidEst is supported by the following lemma, which we prove in Appendix A.3 using the martingale-basse based anytime confidence bound from D:
Lemma 3. Let S be such that |pa| < S, Vi E [K]. Then, with probability at least 8, the regularized estimator (īa(t)) satisfies for all t that
Σ N.(t) (p.(t) - 24) < ((t #E|K]
(12)
Moreover, when 2 2 and X 2 2/K, the following simpler bound holds:
B(t, < 2R² log(1/6) + KR² log t KXS2
(13)

---

H2
Confidence interval fos
Confidence ellipsoid
N.C))
Confidence interval for
j(())
8tt.8) My(3)
Region where μı va & (1))
U(t) 2
U())
Figure 2: Confidence ellipsoid for two arms: f is in the ellipsoid with probability at least 1 - d.
Remark 1. Instead, one may construct a confidence bound based on deviation inequality for exponential families explored ([2]. Since such a bound can be constructed with 3(t, 8) Ollog log( Nt())) instead of ((t, = (Iogg(N,(t))) large N1(()'s. s.. This deviation inequality has an additional udvantage that it does not require the knowledge of the constant S (such that max4e[K] |ns] S S). However, we confirm in Appendix B.9 that the bound based on this deviation inequality can have improvement only for quite large (t.
as in (10), it can lead to tighter bound for
The leading term 2R ()) in Eq. (E) is asymptotically optimal as it matches the lower bound in Theorem [] The following theorem then follows from Lemma 3
Theorem 4 (Correctness). The output j of EllipsoidEst satisfies 1i 1= S E with probability at least 1 8.
Proof. For the stopping time let K. {i E [K] (.T) - Then we have
Σ NN((T) (U(T) - 2=))² = Σ (((T) - -2=))²
iEK
(E|K]
z B(T, 0)
(by the stopping condition of Algorithm T Σ (.(1)((((T) - 14)² (by Lemma 3
(E]K]
Σ N((1)((((T) - - REK
(14)
This means that (U(r) 2e) outside the confidence ellipsoid for the arms in K., which
implies that 1r E (T( 2c, Urr) with probability at least 1 - 6, which in turn implies that fi* U(T) - E jat - =, + E] with probability at least 8.
While the stopping condition guarantees that the output fi* = Ur) - is PAC estimator of the carefully designed to
true regardesss of how the samples are Collected-FlliissiiidP collect samples in a way that achieves asymptotically optimal sample complexity. Our lower bound analysis reveals that all non-best arms should be sampled so that they maintain the same UCB, while the (presumed) best arm sometimes needs to be sampled more frequently to tighten its LCB and accurately estimate the best mean.
Specifically, EllipsoidEst operates in two phases. In Phase 1, it repeatedly selects the arm with the highest UCB, aiming to obtain rough estimates of the arm means without oversampling any arm. Phase 2 is designed to match the lower bound when the estimated means are close to the true values, while still ensuring termination within reasonable number of rounds even if the estimates at the time of the phase shift are inaccurate. Specifically, the algorithm transitions to Phase 2 when the condition in Step 12 is satisfied. At this point, it tentatively identifies the best arm i' and estimates its optimal sample allocation rj.. More precisely, it determines that arm i should be sampled at least r;. (t, 8) times. In Phase 2, the algorithm continues to pull the arm with the highest UCB, except when i* has not yet received its allocated number of samples (i.e., N₁. (t) S r ((1, 5) holds); in that case, it is pulled instead.
7

---

Note that EllipsoidEst returns the midpoint f = (T) -E, but what it actually finds is the interval - (T)) that contains μ with high probability. We will discuss this in detail in Section 7.3
Sample complexity analysis
Here, we establish the sample complexity of EllipsoidEstt that matches the lower bound, and thus proves its asymptotic optimality. We first show that the stopping time of EllipsoidEst is almost surely bounded by a certain quantity T max defined as follows (see Lemma 11 in Appendix (..4):
maax = R log(1/6) + OKKRE log((/6))
(15)
where
4(K - 1) ((K- +1) =O(KE=
=
(16)
4=2
R2 (0)()
7 == K R5 log
+ X 2X55 +2) = Olog log(1 (1/6)).
(17)
AK
This is then used to establish the following sample complexity of EllipsoidEst:
Lemma 5 (Sample complexity). Consider any sufficiently small > O such that log(1/6) 2 K.
Then the stopping time of EllipsoidEst satisfies T < Taxx almost surely for the Taax defined in [5 Furthermore, for any e S 8/2, /,, the sample complexity satisfies
E [r]
S 2R f() 1og(118) Ec (3((Tmaxe 8) + K + Tmax min 1, 1 T// exp
KAS
2R²
(18)
where
B(T 8) < 2R² loo(loo)]))) + a(Tmax)
Tmax
a a(Tmax)
KR² log
1 AK
+ O (1g(8)))
Ec
c:
A Amax +
3 alTmax)
R2 log(1/8)
2+c
28(1 + c)²K O(K/5)).
Ç 3
f(w) +
(19)
By setting E. =(log(1/))) all but the first term in the right-hand side of (18) are olog (1/8)) and we obtain the following theorem (see Appendix (A.4):
Theorem 6. FllipsoidfEst is asymptotically optimal, that is,
E[r]
lim log((10) f(H).
(20)
Lemma and Theorem 6 are proved Appendix A.4 In the proof, we consider the event
A(c) = (a(t)(Pa(t) - -4)² e Vt V (
Tiaax
(21)
KE]K]
whose probability approaches 1 as 8 - 0 (see Lemma 14
Under A(c), the estimation error in (t:(t)
after the phase shift (i.e., for 2 TI, where Ti denotes the first time the condition in [tep met) can be made arbitrarily small by setting sufficiently small (see Lemma 12). This concentration result allows us to bound the stopping time under A(c) by a quantity whose leading term 2R² ((1) log(1/5) by leveraging the structure of the characterizing optimization (see Lemma 13

---

0.1
UGapÉc
10
SE
EllipsnidEst
0.05
10
UGapEc
SE EllipsoldEst
-0.05
32
2
4
8
16
64 128 256
(0/6))1)))
(a) K = 16
(b) 6 0.01
(c) 6 = 0.01 (bias)
Figure 3: (a)(bb Sample complexity т of EllipsoidEst and baselines (SE and U'GaEEe.. (c) Bias in the output (midpoint) and the maximum empirical mean. The results are based on 30 random seeds.
7 Experiments and discussion
7.1 Experimental settings and implementation
We choose to set the regularization parameter as À (R/S)². As we discuss in Appendix B.1 this choice minimizes the size of the confidence ellipsoid in the limit of large sample size and is also empirically shown to approximately minimize the sample complexity a wide range of settings. Owing this nearly optimal choice, EllipsoidEst is essentially free of hyperparameters.
design our experiments to evaluate the empirical properties EllipsiidEst, focusing on three aspects. First, evaluate how the performance of EllipsoidEst depends the confidence parameter and the number of arms K. comparing it against baselines. Second, we evaluate the EllipsoidEst's 's sensitivity the misspecification of the parameters R and S, which reflect assumptions about the reward distributions. Finally, we evaluate the bias in the midpoint of the interval returned by EllipsoidEst and discuss its implications. Due to space constraints, present full results and details in Appendix B and summarize the main findings in this section.
As baselines, we consider Successive Elimination (SE) 66 and UGapEc [4], both originally designed for best-arm identification and adapted here best-mean estimation following the approach in [13 They thus satisfy the same PAC guarantee: the best mean is estimated within error with probability at least 6. Figure in Appendix [ confirms that these baselines and EllipsoidEst indeed estimate best means with the required accuracy. While SE has suboptimal asymptotic sample complexity, known to perform well for moderate values of 5, especially when the number of arms is large. UGapEc achieves asymptotically optimal order of sample complexity for best-arm identification and also demonstrates strong empirical performance at practical confidence levels.
We assume that each arm's reward follows Bernoulli distribution and that the means
equally
spaced within [0, 1] (specifically, μ = i/(K + 1), Vi E [K]). We fix & 0.1 and study the impact of varying (the confidence level) and K (the number of arms). In Appendix B we explore other settings experiments. See Appendix B.7 for details the computational environment.
7.2 Results
Figure 3a- 3b compares the sample complexity of EllipsoidEst against SE and UGapEc. The results show that EllipsoidEst consistently outperforms the baselines for small and moderate K. Moreover, EllipsoidEstt exhibits the slowest growth in sample complexity as 5 -> O, which is consistent with the asymptotic optimality
EllipsoidEst. However, the sample complexity of EllipsoidEst increases more rapidly than the baselines as K grows. This motivates further research on best-mean estimation algorithms that scale more gracefully with K.
The experiments with other settings in Appendix B, B.4 that UGapEc performs poorly when K small when the true means tightly clustered. SE shows faster increase in sample complexity (as 8 + 0) across settings. Overall, although each method has its own strengths and limitations, EllipsoidEst demonstrates robust and competitive performance in configurations of practical interest.
In Appendix B.3 we examine the sensitivity the sample complexity of EllipsoidEst the values of R and S. As consistent with asymptotic analysis (i.c., [[[] ~ 2R3 f(x) log(1/ (1(1)))), the sample

---

complexity exhibits approximately quadratic growth with respect to R. While the influence of S is relatively weak, the sample complexity tends increase with S, which motivates the sample-shifting technique that we discuss in Appendix B.1
Figure 3c evaluates the output já returned by EllipsoidEst (red solid curve) and the maximum of the empirical means (i.e., max, (T)),, based on the samples collected by EllipsoidEst (blue dashed line), relative the true best-mean ju" The oulput ji* tends overestimate the best mean, with the bias being particularly pronounced when K is large, while the maximum empirical mean max; (T) notably less biased. In the following, we will discuss this bias in detail.
7.3 Bias in the midpoint of the interval
In Section we defined best-mean estimation as the problem of returning point estimate ji" that lies within e of the true best-mean μe with probability least the potential bias of fa". However, the problem can be equivalently framed as returning an interval of length (at most) 2: that contains fJ with probability at least 6. Under this equivalent formulation, the point estimate in the original definition is merely the midpoint of such an interval of length 2s.
This may raise questions about
The original formulation might be simpler and more familiar within the PAC learning framework, which is why we chose to adopt it initially. However, it has the drawback of placing unnecessary emphasis on the output fi*, requiring it lie the center of an interval solely due to how the problem is framed. It should be understood that the essential output of EllipsoidEst is the interval (U] 2s, (T)]. which contains μ² with probability at least 8. The output pt* (T) should be viewed as merely the midpoint of this interval, returned to satisfy the requirements of the original problem formulation.
The output is typically higher than the maximum empirical mean (i.e., ft" 2 max; (T((T)), as is also demonstrated in Figure 3c] Notice that the maximum empirical mean is typically biased upward due to the "winner's s curse" [8]. i.e., E mmmax; (T( > max; Jr. although this phenomenon is not visible in Figure 3c due the large sample size. In practice, the maximum empirical mean could be provided as supplementary information alongside the primary output- the confidence interval itself. Additional bias correction techniques such as [17 22 could also be applied to reduce the bias in such supplementary information.
8 Conclusion
We have considered the problem of estimating the mean of the best arm, which can be viewed as a pure exploration problem with an infinite number of answers. Although the characterizing optimization is non-convex, it can be decomposed into convex subproblem if we fix one parameter. By using this structure, we propose EllipsoidEst that only calculates a non-convex optimization at most once during the runtime. The sample complexity of our algorithm is asymptotically optimal, and its practical performance is verified through numerical experiments. In particular, our algorithm has outperformed the baselines for the number of arms K up around 16. Improving the sample complexity for large K is interesting future work.
A limitation of EllipsoidEst is that it relies a known upper bound S the magnitude of the truc means, although this assumption is standard in the linear bandit literature with sub-Gaussian noise since [T] In some settings (e.g., Bernoulli rewards) S is trivially known, but this is not always the case. When S is unknown, the confidence bound from Theorem 2 in I (which we use) becomes inapplicable. However, Theorem 1 in [ still provides valid anytime confidence bound that does not require knowledge of S, although the resulting confidence region becomes more complicated.
Acknowledgements
We thank the reviewer who pointed out error in the original proof of Theorem 1 It has since been corrected using an approach that simpler than the one proposed during the discussion. JH was supported by JSPS KAKENHI Grant Number JP25K02232.
10

---

References
[1] Y. Abbasii- D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[2] R. Degenne and W. M. Koolen. Pure exploration with multiple correct answers. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[3] E. Even-Dar, S. Mannor, and Y. Mansour. Action climination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 1379:1079-1100 2006.
[4] V. Gabillon, M. Ghavamzadeh, and A. Lazaric. Best arm identification: A unified approach fixed budget and fixed confidence. In F. Pereira, C. Burges, Bottou, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25, Curran Associates, Inc., 2012.
[5] A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In V. Feldman, A. Rakhlin, and O. Shamir, editors, 29th Annual Conference Learning The- ory, volume 49 of Proceedings of Machine Learning Research, pages 998-1027, Columbia University, New York, New York, USA, 23 26 Jun 2016. PMLR.
[6] A. Hassidim, R. Kupfer, and Y. Singer. An optimal elimination algorithm for learning a best arm. In Advances in Neural Information Processing Systems, volume 33, pages 10788-10798. Curran Associates, Inc., 2020.
[7] A. Huang, A. Block, Q Liu, N. Jiang, A. Krishnamurthy, and D. J. Foster. Is best-of-n the best of them? coverage, scaling, and optimality in inference-time time alignment, 2025.
[8] M. Jourdan, R. Degenne, and E. Kaufmann, An E-best-arm identification algorithm for fixed- confidence and beyond. In Thirty-sevnnth Conference Neural Information Processing Systems, 2023.
[9] H. Kajino, K. Miyaguchi, and T. Osogami. Biases in evaluation of molecular optimization methods and bias reduction strategies. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 15567-15585, 23-29 Jul 2023.
[10] Kalyanakrishnan, Tewari, Auer, and Stone. PAC subset selection in stochastic multi- armed bandits. In International Conference on Machine Learning, ICML' 12, page 227-234. Omnipress, 2012.
[11] Z. Karnin, T. Koren, and O. Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, Proceedings of Machine Learning Research, pages 1238-1246. PMLR, 17-19 Jun 2013.
[12] E. Kaufmann and W. M. Koolen. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22(246):1444 2021.
[13] T. Osogami, H. Kinoshita, and S. Wasserkrug. Mechanism design with multi-armed bandit, 2024. btttp:://axxiv.rrg/bbb... 00345v1
[14] M. Rauh, N. Marchal, A. Manzini, L. A. Hendricks, R. Comanescu, C. Akbulut, T. Stepleton, J. Aarccos-Garcia, Bergman. J. Kay, C. Griffin, B. Bariach, I. Gabriel, V. Rieser, W. Isaac, and L. Weidinger. Gaps in the safety evaluation of generative AI. Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, 1(1):1200-1117 Oct. 2024.
[15] A. Russo and A. Pacchiano. Adaptive exploration for multi-reward multi-policy evaluation. In Forty-second International Conference Machine Learning, 2025.
[16] C. Snell, Lee, K. Xu, and A. Kumar. Scaling LLM test-time compute optimally can more effective than scaling model parameters, 2024. https: / arxiv. wwaxxiv.rr///e/ org/abs: hegg/abs/4408 03314

---

[17] L. Sun, A. Dimitromanolakis, L. L. Faye, A. D. Paterson, D. Waggott, T. D. R. Group, and S. B. Bull. Bq-squeeed: A practical solution the winner's curse genome-wide scans, Human Genetics, 129, 2011.
[18] R. Thaler. Anomalies: The winner's curse. Journal of Economic Perspectives, 2(1):191-222 1988.
[19] H. van Hasselt. Double Q-learning. In J. Lafferty, C. Williims, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
[20] H. van Hasselt. Estimating the maximum expected value: An analysis of (nested) cross validation and the maximum sample average, 2013. https://arxiv: wttp://r/aa....////11//
[21] P.-. Wang, R.-C. Tzeng, and Proutiere. Fast pure exploration via Frank- -olfe. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 5810-5821. Curran Associates, Inc., 2021.
[22] R. Xiao and M. Bochnke. Quantifying and correcting for the winner's curse in genetic associa- tion studies. Genetic Epidemiology, 33(5):453-44) 462,, 2009.
[23] F. Xu, Q. Hao, Z. Zong, J. Wang, Y. Zhang, J. Wang, X. Lan, J. Gong, T. Ouyang, F. Meng, C. Shao, Y. Yan, Q Yang, Y. Song, S. Ren, X. Hu, Y. Li, Feng, C. Gao, and Y. Li. Towards large reasoning models: survey on scaling LLM reasoning capabilities, 2025.
https
//arxiv. org/ abs/ 2501 09686
[24] X. Yu, Peng. V. Vajipey, Cheng, M. Galley, Gao, and Yu. ExACT: Teaching Al agents to explore with reflectiveMMCTS and exploratory learning. In The Thirleenth International Conference on Learning Representations, 2025.
12

---

A Proofs and technical lemmas
A.1 Analysis of the lower bound
Consider the following multiple correct answer problem (MCP) 22]. means μa, this problem involves finite answer set B. There is answer function b' R.K - 2 that determines the set of correct answers for a given model μ.. Consider an adaptive algorithm that samples rewards from K arms and stops. Let be the stopping time. When this algorithm stops, it outputs b* E B. An algorithm is 5-correct if b* b* (1) with probability at least 1 ō under any model μ..
In addition to K arms with
Lemma 7. (Lower bound in the multiple correct answer problem, Theorem in 2 Any d-correct
MCP algorithm satisfies
E log(1/5)
1
lim inf 610
(22)
max max inf BED (JC) WEAK (A)
wed(us, A:)
KE[K]
where dips, 2x) denotes the KL divergence from the distribution with mean Ht to that with mean X;; hence, d(js, X²) = [m (144->a)//00 /2R))(( for Gaussian distributions. Here, A denotes the (K 1)- dimensional simplex.
We then introduce an M-bin MCP problem with parameter M E N. Let =/M. This problem
involves bins B {(-00 00. 1²" -E), [M* - E, E + E'), 1nr -E E', E', - E + 2E')........ Ju* e, e. +
+ e²), [nr + E + 6', oo)]. The number of bins is finite (2M + 2). We define the answer function as b" (14) = (b E B: :::b ju* - + E] + 0).
The output A of the original BME problem can be put into one of the bins. We can see that, if we convert d-correct BME algorithm into the M-bin MCP problem by assigning the estimated best mean into a bin including it, the resulting algorithm is a d-correct M-bin MCP algorithm. By this fact, Lemma 7 applies as a lower bound of the original BME algorithm. In the following, we lower-bound the performance of the M-bin MCP algorithm.
Lemma 8. (Lower bound optimization for M-bin MCP algorithm) Let n > be arbitrary. Then there exists M E N such that the RHS of Eq. (22) for M-bin MCP is larger than 2(1 - n)) (()) for Gaussian rewards with variance R²
Proof of Lemma 8
The denominator of RHS of Eq. 22 is
max Max inf BE (J)) WEAR Xiogb" (A)
wid(ui Az).
(23)
(E(K)
We upper-bound Eq. 23) as follows. Take any bin b E b" b²())) {1p² -e, pe-- -=+e), 11t 1e, 1t
8 e+5')} T.(b) the lefimost point in b. Then, T.(b) E [u" -e, 1--"-e,, 1¹ +s}. Let ba = (- [(bb) - E-
by
= [.(b) + co). Then
b b (A) = (X* +E+E'S S L(b)) (L(b) + e' xx- = X* UB.
(24)
where we denote X max do Hence, we have
max inf WEAM Xibeb* (A) KE(R]
Σ
wid(ui; As)
max inf wEAK ddbbbba
Σ SE(R]
wid(ai do))
(25)
inf WEAM A:A Ebaubs
max
welm - A1)²
(26)
2R
KE(K)
for Gaussian rewards. Here,
inf ADA {E|K]
Σ wi - x,,²= = Σ
wilm: - ( A(b,)))
(27)
K
since L(b)= < n² + and hence L(b) 8 - el < 1²* (the minimizer is A; = L(b) - E s5 if
H4 2 L(b) - - el and X = p4 otherwise). Also,
inf Σ wi(m 2,)² min wi (L(b) + - -m)2 = B(b, w)
(28)
Aby (E(k)
13

---

since L(b) 2 jr* - and hence L(b) + + E' > μ= (the minimizer is X L(b) + + e' for the
minimizer of wi(m (L(b) E1)) and A, = μu; for other t). By using these, we obtain
inf AAA"bbaUbi
Σ {E[K]
wi(m: X.)² min(A(b, w). B(b, w)) C(b, w)
and therefore
2R C+
(29)
max (1)) wa inf (A) Eielk wyd(ps, Ax)
for C* = m&Xbeb (n) ыax C(b, w). We write (b", w²*) to denote its maximizer, which always exists because this a maximization of a continuous function C(b, w) over a compact set. Here note that
B(b',w") 2 C(p , +6),,1/K
min
Σ
(E (i)) min(A, + + +
K
sE|K]
(E + E²)2
8²
(30)
K K
where 1 is the all-one vector, and A; == n¹ - it for [K]. Let = (1 Rv
1,
U' = L(bb) + E - E', and rf == aw /C for i E [K]. Then we have
Σ EE[R]
Mlw - U' U'+ +2)) aA(b", w w²//C²" //0" 2 a a>>,
r'(10' - -m)² (L(b) + + -
(L(b - -
C*
(L(b((('') +E+ 11))+
B(b* w*)
2e' Vu,
2
2
C*
aa
1
(wf(L(b*) (L(b*)
+ pi)+
26'
2.a 1
21, vi E [K].
/ /B(b w.))
where the last line follows from (30), w < 1, and the definition of a. From this result we see that
U' and r' = (r'.....ry, ...,.))) are a feasible solution of the minimization problem in (PI), and therefore the optimal value f(4) of (P1) satisfies
f(n) S
Σ iE[K]
C
C+
[
2v
Combining this fact with
29 we obtain
(1 1- 2VKK (1_2/K
maX (n) ma inf inf (A) EiE(K) w,d(pr,)) 2 2R f(v)
the RHS of which approaches 2n f(u) as 4
Proof of Theorem 7 Theorem is an immediate consequence of Lemma 7 Lemma 8 and the fact
that any 5-correct BME algorithm can be converted into an M-bin MCP, as well as the choice of
77 0.
14

---

A.2 Analysis of the characterizing optimization
Proof of Lemma
The statement can be easily obtained from
s(U:N4) E (1- Km' (u U 26)
(10 - U + 22)3
-U-
(U - 11*
g(U:H) 2 (10 U + 22)3
1
Σ
1
(31)
(U - w²)s
ipi-
for U (1²", n² + 22).
(ii) By the Lagrange multiplier method, we immediately obtain
i i*
P0- (a- U42667
p4)
11-ipi
Un-((+20)1 V (W-1eyz
i7
(32)
(0- (m-+))²
where recall that we set one optimal arm as i", and therefore the case = i* happens only for one i [K] even if there multiple optimal arms.
Here, ra- (U; 14) (U w-Erez holds when
1- Σ
(m: + 22)
1 UU - )²)
(33)
(n U + 28)2
(U - 14)
it
or equivalently
(μ4 - + 22)
11
S 0,
(34)
(U- 11:}
vE(K)
that is, U < (()). In this case.
f(U:P)= Σ SE[K] (U (4)
(35)
which is decreasing in U. Therefore, U < ((H) cannot be the optimal solution U(4) minimizing [(U; ud), and we obtain (1)) 2 (H),, where
i i i
(U 3
(1- Eigir
(M- 20)2
1 == 1
(36)
[nr- U42eF
(U-p=;²
and
f(U:A)= Σ 1
1
1 1- 1-
Σ
(4--U
- + 25)
(U - mr)² - 22)2
(U- 14)2
ifi
igfii
Σ 1 (1-
(m4 U + 22)
1
+
(37)
U 1r)2
(n* - U + 25)2
(1r* U + +
which is not necessarily convex in U.
15

---

(iii) (p)) 2 (p)) is already proved above. By letting f(U:
Uf 80 we obtain for
2 (p) that
((UU:))
11- (14 U + 22)
Σ SE|K]
2
(U v:)s
(1r - U + 28)²
1
(4--U 2 + 2E)
(1i + +2))
Σ
+
(U - 21
(11 U + 25)3
(er U + 25)
KE(K]
2
Σ
1
(1 (1- (1- (er - U + 28)2
(1u U + 22)2
)
+ (nr - U 26)3
(U 14))
SEIK]
(1 (1- (A: - U + 2z)
E
+ (p* U + +2)3
(U ks)3
(μ² U + 22)²
+
UU p1)3
(n* U 25)3
g(U:UH) pt)
(38)
Therefore, when 7(U; (1) > 0, that is, when > U(H), we see that f(U: p1) is increasing. Therefore,
> ((1) satisfying U 2 [i()) cannot minimize f(U: p)) Therefore we obtain (()) - ((p) V
Uw)).
, (iv) Recall that (1+) is the solution to g(U; pt), and gUU p1) is increasing with U in (n", p= + 22).
Now, observe that
M( (n1* - U + 28)3
Σ
(U
11)
(
(1* - U + 22)3
IU - 43)3
i
K-1
(39)
(10 U + 22)3
(U 11t
which attains 0 at
2
U n² +
4² + 25.
(40)
1 (K-
Hence,
2
U(H) S n1¹ + 1+
< 4¹ + 2
(41)
(K-1)173
and we get
r((())):)) 5
(prr U. (14) + 22)²
((K - 1)2/3 + +1² 2
(42)
4Ea
(v) By 32 we have
1
rh (U(M):)) 2 (U(11) }2
(43)
Then the statement is immediate from (1+) (H) < 4r¹ + 2E shown in (i) and (ii).
16

---

A.3 Analysis of the confidence ellipsoid
Proof of Lemma
Let define
det(V)
biss .)
M1 V det(V + V/)
exp
(44)
where
St Σ n
Σ (Y X, x)
(45)
for observation Y, yx=x; X,T0 + ?) with R-sub-Gaussian 7)--
Then by Theorem 1 of [1. with probability at least - ô it holds for all & that
| S 2R log det(V + V,)
(46)
de))
Here, let us consider our setting with V = AZ and regularized esttmarr ja:(1) N.O+X Emer Yim.. where Yim is the m-th observation from arm i. Then
N:(l)
SSel
Σ KE(K)
N.(t) + A ((N((t) + A)ā,(t) N((t)A))2
(N.(0) A)A.(1) 20(00N(())) + Ni(1) NO(1) +
Σ
(E(K]
(((0))01)2 20000(( + Ni(t)
Σ
N((1)
KE(K]
Σ
(4O0 (A.(1) -m)² NOO
N.(1) +X N((O))
(E[K]
AN.(O)
Σ
(NO0) (Da(1) - -14)
Ni(t) +X
(E[K]
AN.(1)S²
Σ
(N((t) (A.(t) - -4)²
N.(t) +
TE(K]
N₂(1)
Σ ((((()))) 14) XS Σ
(47)
Ni(t) +^
KE[K]
RE|K]
where 2 max; |pr|. From these results, with probability at least - 8 it holds for all t that
Σ xE[K]
N.(t) (t,(t) 24)² < 2R log det(V - 1/2
+ AS
Σ
N₂(1)
de)t(V)
+1
SE[K]
I
K
VA+ N:(1)
A Σ NG(1)
=2R2 log
8/K/2
Ni(t) +
KE|K]
N
N(())
2R² log
+
R log
XS2
NO(1) + +x)
(48)
In settings, the norm is more natural than the Le norm in O1.
17

---

While the hight-hand side of this expression is computable and sufficient for implementation, for the theoretical analysis it becomes convenient bound the reminder term by
X+ (ttt)
N.(t)
Σ
R log
+ AS2
N((1)+
[E[K]
A 1/K
1/K
)
S K
R 12
+ AS²
t/K+ +
x/t+1/k + XS2
S K
R loggt t + R² R2 log
X
< K (R² logt t- + AS
(49)
when f 2 2 and 2 2/K.
m
A.4
Analysis of the sample complexity of Algorithm D
A.4.1 Preliminary
Lemma 9, For any t 2 0 and 6 > 0, we have
B(1, v 21² log(1/6) a(t);
(50)
where
a(t) = KR log
1+ *+>k) +ASS
(51)
Moreover, at t = maax we have
R
log (1/() K 7+ AK
a(Tmax) < K KR2 log
AS K.
(52)
AK
2 (1g(1
When â is sufficiently small and satisfies log(1/8) 2 K, we have
22 1og(1/8) + 7 XK
mmmaa & KR log
+ *SSK..
(53)
AK
25
Proof. Since log(1 + x/A) and x/ (x + A) are concave in x for A > 0, B(t, 6) defined in maximized when (t) t/ vi E [K]. Hence,
(10 is
t. XK
+ 1/K
ott, < 2 log (1 KR² log
+
t/K +
1 t XK
2R log (1/6)
log KR log
(54)
By the definition of Tmax in (15),
we have
Tiax
a (oTmaat max)
KRR log
1
AK
KR log
RER
log(1/6)
?
+1) + 1
AK
AK
KR² log
R2
log(116)) (e((1/)
+ KR log
1
AR
+
+
AK
25 XK
log(1
S KRR log
12ER²
log(1/6)
+ KRR
x
+1
+
AS2K
(by log (1 x) S x)
AK
2CR
log(1/8)
AK
(55)
which gives
52
When log 2 K holds, the second term in the previous expression is bounded
as follows:
XX +1
+ AK
K KR
(56)
25R
log(1/8)
2
XK
which gives
53
18

---

In the following, we derive a couple of lemmas on the properties of f(U; pt) and {ra(U;p)) that are needed for the sample complexity analysis. Define
[u(rU
Σ
rv
(57)
UU 14)2 if
(U - mx)
An intuition that fr,r, U; (s) corresponds the sample complexity rate ensure that the best mean is at most U given that arm & is pulled at least r times.
Lemma 10. Let E1 E (0,e/2), E2 E (0,z) and take i arbitrar.. Let μt be such that 1u4 Mei S Ei for all i. For k* argmax, bbg define r Tk- (f'). Then,
fr,,""U((z)) E2: x²) S f(u) + 4K
2K
+
(58)
E(E 22,)² E(E 166-5p E2)
In this lemma, pe' intuitively corresponds to the estimator of μe when the proportion of the optimal arm is determined. We can use this lemma to show that the sample complexity is close to the optimal one, (44,, far as the estimator fı' is not far from μ.
The technical difficulty this lemma comes from the non- non-convexity of the characterizing optimization
(PI). While we can easily show [x-(r", U; (i f(u) if* ri- (p)) and U = U₁- (r; (t). cannot guarantee that the optimal allocation rx- (fx') for p' becomes close to the optimal allocation T (μ)
for μ due to the non-convexity. This lemma can be used to guarantee that if r and U' are determined based on an estimator close to fu then the sample complexity becomes close to the optimal one despite the non-convexity of (P1).
Proof of Lemma 10 First we have
Before evaluating fi- (r=, E2j (z)) we prepare several elementary rela-
tions.
(U(H') 14 - E2)
(U(m') -1,)3
(U(n') - -2) (U(w') - m1,2
(2(2(U()))) - 11) 62)
(U(w') -113
(U(p') 14: 02) (1))(((())))) 11)
(2(2(U()') - -22)
$ (U(w') -4422
(by U(p') 2 max; p4 + from Lemma (ii))
(U(w')) - 14/ RE2
(2(28 - 82)
(by U(4)) 2 max; 14 + from Lemma 2 (i)ii)
(U(x')) -4)²
(e (6-8))e2 Po2
282
(59)
(w'w') - 12)²
(s - (6-82)26
and similarly,
1
1
451
<
(60)
(U()) p4 221)²
(U(#) n:)²
(e (e-2s))
19

---

For any & E [K], we also have
(4) (U(H)- 11/- -E1)²
U(H) + 2E + E
(M(-U()) + 28 + +1)
+ 1[ + +i (1/. - -U(H) + 28 + 81)
(U(H) 14, =11)
(U(H) 11/- =1
(mi (m--U(e U()) + 22)2
[ + im] (ci. U (1L) + +22)
(U(H) 14)2
(U(H) 14-) )²
ipkii
(wi (()) 26)2
11 + [+] (max: p4; - U (1) + 22) (U(H) mmax 14)
Σ itkii
(U(M)) 14)2
(mi- 1i-uU U()) + 2
(μx: - Up) + +2 (U(H) -2a)
1l + 10
(U(M)= - 14)2
ip
(4- U()) + 2z)²
(61)
(U(++) m1)2
We also obtain the following from 1A4 - Hil S E1:
Σ
(UL)) 14 E1) I
1
(62)
(U(p) 14: 221)²"
i71
Since r* = (pe)) for k argmax; 14/;
1
1 E (nh -U((')+ + +2)²
r¹ (klg (H²) 25)2
(63)
(U(p') 11,)2
(U(#²)) 122-12
by Lemma 2 (ii).
Now we evaluate fi- (r*,U U(1') - -22: p2) as follows.
far (r", U(') Ezi p2)
Σ
(U(m') - =2)2 + (1* (U(H²)) - 11/.- =22
1
1
$ Σ
(U((')) - =11)2 + (1*V (U(H²)) - -1/.-)
1
+ EE(E E2)2
2K
(by (59)
isk
Σ
1
1
1-E EgE
(4 -U('')) + 26)
2K
+ e(e - 62
(U(11') - -112 (1/. U(11) + 28)2
(U(Kz')11))
FAK
(by 633
2K
)(U())):)))) + E(E E2)
2K
= =inf ((U:N'))) E((E E2)²
= inf f(U; +e11)+ + 2K
(64)
5(8-82)
- E2)²
2K
< {(U(()) +s,1+ + ele - -2
= Σ
1
1- (4-UU() + 2s +
2K
(U(H) - 14-- - 52
(p/. - U(H)+ + 2s + 1
(U((H) 11: 51
s(s 22)
k
20

---

1
1
(1+ (4-UU (U-UU() + 25)
2K
1
(U(M))
p4 201)²
(142 U(1) 2e + t1)²
-1))
e(e 62)
ippi"
20 by o(U(1))22
(by 61 and 62
1
1
1 E-Σ
(wi (u-U(()) U(()) + +20)3
2K
+ (ut U1H) + 22)2
+ E(E -22)²
(U(H) pi 201)²
(U( -Na)2
8711"
1
1- Σ
(m4 - U(p) + +2)22
4K
2K
(U(H)) :H)2 + (e0 U(}) + 2E)²
+
(U(H) p1)²
E(E 251)2
E(E -2))
(by (60))
f(() + 4Ks
2K
(by the definition of f(u)).
E(E 2²
E(E =2)²
Here, in (64 1 is the all-one vector and the equality comes from the shift-invariance in μ of the original problem 33)
A.4.2 Analysis of Tiaa
Lemma 11. When K s log(1/8) holds, the algorithm stops by Tiax almost surely.
Proof. We begin by bounding the number of times each arm is pulled before the algorithm terminates. Recall that at Step the algorithm selects an arm, and that the tentative best arm i*, identified at Step 14 is treated differently from the others. Therefore, we analyze two separate cases depending on whether arm k is equal to i* or not.
Case 1: k * f For the arm k * i* to be pulled in round t, it must be the maximizer k* at Step in round - 1. Since the algorithm has stopped in round 1, we must have
- 1,0) > Σ
Na(t - () 1) - Utt - 1) + 2c)
=K|K]
2 (t 1)((u((t - 1) - Ut 166-1] 1) + 2z)
2
3(1 - 1, 8)
= Na((t - 1) ppa(t - 1) - mult - 1) - V
Nu(t + 2s
(-v/((-1,0) 2 Nu(1 - 1) 1
(65)
implying that
N&(1 1) < 3(1 1,8)
3 3(Tmaxx 8)
(66)
2²
E²
Since this relation holds whenever arm k is pulled in round l S T, we must have
3 maxx
8) + 1.
Nx(())
(67)
g2
Case 2: k= --_ For the arm 7t to be pulled in round I, it must be the maximizer A at Step 9 in round
t- 1 or it satisfies N₁. (t 1) < rq. 3(t 1, at Step 5 in round t. However, by the same argument as above, the first situation implies
(TTmax;0) 8)
No. (t - <
(68)
2²
The second situation can happen only when
( +
N₂. (t- - 1)<<
3 Tmax- 8),
(69)
4=a
21

---

by Lemma v).
From the ahove argument cases, obtain
((Tmux:8)
+1
1: x
(111
ct
(70)
B(T 8) + h ==
which means
Σ (T(T) kE[K]
K K-1 (K- 1)1/3 + +1)²)
( (mmaxx 8) K
22
4s²
=E max: 8) + K,
(71)
where & as defined in (T6).
By Lemma 9 we have under (1/0) 2 K that
1
R2 AK
1
AK +
([T 6) $ 2R log
+ KR
log
log
+ AS*K
8
2
Tmax
K
(72)
5
where the equality follows from the definition of y in 17 This together with 71 implies
S { max: 8) + K
< T
Tmax-
(73)
Hence, the algorithm must stop within Tmax rounds almost surely when log(1/6) 2 K holds.
A.4.3 Stopping time under A(c)
We will first show, in Lemma 12 that the estimation error in (t.(t) after the phase shift (i.e., for t 2 Tι) can be made arbitrarily small under the event A(c) with a sufficiently small c. This will then be used in Lemma 13 to bound the stopping time 7 under A(c).
Lemma 12. Let Amax max: (s) and e" 2a
a(Tmax)) 212 log for the defined in Lemma
Then, under A(c) with c E [0, +em for any Ee > 0, we have
(i:(t) mil S Eo, Vt V [K].
(74)
Proof. Let be the time of the phase shift, that is,
Ti min(t: (t) ((t)) v ((U(();A()) s 03.
(75)
Observe that ((U(() v (TU < 0 is equivalent to U(t) s ((A(t)) V U(a(t)) and that U(t(t)) v ((((t) < (t) + 2: by Lemma 2 i). These imply that
T = min(t ((U(t)) (t)) A(( s 0}
2 min
{t: U(t) < (t) + 2z}
b: Ne- > 8)t,8)
min
(76)
(2s)2
where R*(t)= argmax, (t)...
Consider the event
3(t,5)
B U(1) S +2(1 +2(1+ +c)e
Vi E (T,,I + 1,..,, Tmax
(77)
A(T))
22

---

Then B always holds under A(e) because
8(1,6)
U())
max kE[K]
(+=(t) +
(a(t)
B((,5)
=g. +
(t)
8(t,
5 +1+ 1
(under A(c))
(t)
8(t,
Spt + +1++0V
Nx-(1) (t)
B(t,8)
Sp¹ + (1+
(by t m
Nu, (T1)
B(t,
S 4² + 2(1 + V
(by 776
(78)
A(Ti)
Hence, under B 2 A(c), we have
((t, N.(t)
5(t,5)
#4 (1 /
S (.(t)) + | N,)
(under A(c))
Ut))
3(t,
$ n³ + 2(1 + c)
(by 78
(79)
A(Ti)
for any & 2 TI E [K]. Therefore, under A(c), we have
8)t,5)
(t) S c/
(t(t)
(n* -1i)+ + 2c(1 cc)
B(t,
1-c
VV
A(π)
(by (79)
2c(1 cc)
B 8)
A max
(by the definition of Amaxi A is increasing)
1-c
A(0)
2c(1 cc)
(Tmax) ( max
< max
1
(by 10
with t 0 and Lemma 9
1-c
2R log
Ammax + (1 + c)=").
(80)
To prove 77)), suffices to show that
g(c) = cA max + c(1 + ccE" - -(1- c)εc 0
(81)
for any e, > 0 and E 0,, Amaxte
Since g(c) is quadratic function with g(0) < 0, it is
straightforward to verify that g(c) S for
D
45"
-1)- :1]
0,
(1+
(82)
2="1
D
where
D = Amax + 5" + teo
(83)
23

---

Since v 11+1++ 1+
2(1+z/4) for x > O, the upper bound on can be simplified to
D
(11
E
-1
-
2
D
4e Es
D
2z"
D
20
(1 +
D
E
+
g"Ea'
D
Ec
(since D > E"),
(84)
+ Ec
which completes the proof of the lemma.
Lemma 13. Under A(c) with e. in the range specified in Lemma
12
for sufficiently small E such satisfies
that & e/2 and 20e Be < E, the stopping time T of Algorithm
r (1 + c)2 (f(W) +
4K +
2K (2cE + Ec)
[ max: 8) K.
(85)
E(E C(E-Ec) E(E 20E - Ec)
Proof. We prove the lemma by showing that sufficiently large (.(t)'s make the stopping condition in Step T of of the algorithm satisfied. To derive a lower bound on a term involved in the stopping condition, consider
(x
U U 22)+
minimize:
subject
x + cy 2 μb
x + S U,
y> 0,
(86)
where e (0,1).
This optimization problem is feasible only when U 2 1a, and this case, we can see that the optimal value is
2(1 - c)E U 4 -1)
- - (
(U + 205) 2c
(87)
-
Indeed, when U μ + 2(1 c)E, the objective value can achieve with U 2s and y 22. Consider the case where U < + 2(1 - c)E. Observe that the minimum is achieved with cy for any With this we must have y S UーE
T-c Hence,
U + 25 1 cy U + 2
U + 25
y/
2( - C)E
2
1,
(88)
U
which is nonnegative under < p + 2(1 c).. This lower bound achieved with y x cy.
U-
and
I-c
Therefore, under A(c), have
1
[ (U(t) + 2CE) + 25
U(t))
(89)
B(t,
U(t) - 1Ak
Similarly, if we additionally have (²) 2 r;,3(1,0), then we can show
1
5)t,5) (,.(1) - U() + +2e)3
r3. pi: ((()) + c
2
Hig (U(t) 2cE) +
+ 22
V
(90)
U(t)
P..
24

---

To see this, consider the optimization problem with the additional constraint of
S
(91)
Similar to the previous argument, the minimum is achieved with æ ey for any y. With this x, we must have S T-e
U-E A V Hence,
I x- U 25
U
+ 25
y
y
2(1 - c)E -1
Vr |
U +
c vrr
+
28
(92)
U μ
which is achieved with CーE A / and x = 11. cy. I-c
From these results, under A(c), if N₁. (1) 2 r;- 35, 8) holds, then
E (a(1)(((()) - (t) +2
B(1,5)
RE(K]
Me (U + 2cs) 2
U(t) Pk
kEi
+
rj.
Pij.
U(t) +
C
2
V
14 (U(I) + 2ce) + 28
(93)
Vi-
U(1) Pç-
+
Therefore, if (T)) pxl S e, additionally holds, then
Σ (a(t)(a((t) U(t) +2)) RE(K)
8(t,o)
(in(T)) - (U(t) + 20E + EE) + +((t)+EEe) (m)(T))
Σ
k
(T)) (U(t) +
[ (a(m)-(U() + 208 + Ec) + 2
2
+ +ri.
+ to
+
Vi..
(U(t) + A3 (T)
(94)
From this discussion with the definition of r, if
U(t) < U(}(T)) max 2cE, Ti.
C
Ec
(95)
holds, then we can show that
1
Σ (a(1)(aa(() U(I) +20) 2 11 KE[K]
(96)
B(t, 8)
25

---

that is, the algorithm terminates. To show this, let Ü = (T)(TT)). Then, since 994 with U (t), we have under (95) that
is decreasing
E (a(t)(pa(t)) U(t) + 2c) RE[K]
8(t,
(a((T) - (U(1)) 20E + EC) +
+r;. (Ds((m) -(U())((
2
[(tt+ +
+ tee
+ +
(U(t) Ec)) - -Ax(TT1)
VTa
(m)(T) ) - Ú + 28
+ri. (it+(1)) - +26) )
- ( - 2CE
+
2
(L(TT) - - + 25
(a(T))) - 25
2 1+
Σ
Σ
(by the definition of rj.
Ü --i((TT) 20s
Ú - -xxTx(T))
k
21.
(97)
Therefore, remains evaluate the number of samples until (t)) decreases the point where satisfied.
95
If arm i + it is pulled in round t, we must have
B(L - 1,5) Ni 1)
iu(1 1x)
= -U( (1(t-1) 1) > U(A(TT)) - max { C
2ce,
Ec V33
(since not terminated in round / - 1).
(98)
Hence, we must have
B(t 1,5)
1)
(U(((T))) - ii,(t 1) max (205, v.çe
ED
8(t 1,6)
(by Lemma 2()
(U(((T))) - Pu:l1 1) 208 =e)²
B(t 1,8)
(under A(c)).
(99)
(U(A(T))) - M4i /v 1,5) - 200 EC)
(1(1-1)
By solving the previous inequality for N2(t - 1), we obtain
(1 + c)2
N. 1) < (U((((Ti)) - 145 - 22E Ec)
3(t 3(t-1,0)
(1+c)²
3[Tmmax: 8).
(100)
(U(((T))) 14 2cc EC)
Likewise, if arm 3* is pulled in round t, we must have
(1+c) c)2
No. 1) (U((((T))) M3. 2cs E0)
1,8) (.6) (((--1,)) Btt 1,5)
(1+c)²
Vra B [(Tmaxx 8).
(101)
(U((((T)) - Hi. 2ca - Ec)
Hence, for any $ T, we have
(1+c)
(T max: 8) +1
(1+
265 (1+e)²
N.(1) <
(102)
V (r;
3(Tmax, 8) +1 (i=i²) it)
(U(D(T))) - 205 205-8,)
26

---

Hence, for Eo <E/2 and 2CE t < we can use Lemma 10 to establish
== Σ Ni(T)
KE[K]
4Kec
2K (2ce + 60) ) B (( 8) + K.
$ (1 + c)² [(H+) +
+ E(E 2c0 - Ex)
(103)
E(E =E))
A.4.4 Probability of A(c)
Lemma 14. For any e (0, 1), we have
Pr(-A(c)) min {
KXS2
1, 118--TK1
max exp
(104)
2R
Proof. Lemma implies
Pr
s Σ N(()((((()) S ((,, (2,3, T Tmaxx) 2
(105)
iE[K]
Hence, A(c) holds with probability at least 8' satisfies
(), 2 2N log 8
+ a(), 1I E 32, "mamk
(106)
By solving this for 8', we obtain
1 - c²
exp
alt)
vt E {2, 3.. T.,,a }
(107)
2
which is satisfied by choosing
c1
8' = 80² exp
a: <((maxx)
(108)
2R
We thus obtain
Pr(-A(c))
58'
8e exp
-
c²
(K RR2 log Tmax KXS2)
21
80 exp
(K R2 log Tmax + KAS2)
2R2
8 K22 exp
(109)
max
2R
A.4.5 Proof of the upper bound theorem
Proof of L Note that the upper bound Tmax is from Lemma the upper bound on
((Tmaxx 8) is from Lemma 9 (TTmax) is given the proof Lemma 9 and is in the range
specified in Lemma 12 and satisfies the condition, 2ce + E. < e, in Lemma B3
EC
A Max + +
Eo
A max + 8d + Ec
A Amax+
+
+
af axTmaxe
R² log(1/5)
205 + E
A Amax=
+
od a(Tmax) log( 18))
5
Ec
(110)
<
(111)
27

---

since Ec I E. Notice also that (10)) gives < 38
11 shows that I max almost surely under log(1/6) 2 K, and Lemma 13 shows that, under A with the given conditions on c. and cc. we almost surely have
Lemma
4Kec (2cs + EC)
7 (1+ [(()) + E(E E(E 2cE - Ex)
3(T 5) K
tKec
+ 2K(2cE + EO)
(1 (22 + +c) max: 8) (1+c))
((Tmaxx: 6) K
E(EE - Ec)
E(E 205 - Ee)
< < 8) + Ec (2+c
f(H) + 4(1 + c)2K
2(1 + (2CE + EE) ) ((Tmuxx 8) + K
3
- Ec
Ec(E - 2cE Ec)
(byc< +
Ec (2+c {(1) + 4(1 + c)2K
(1 + c)2
((1)))(Tmas)
B(Tmuxe () 8) K
E Ec
E,(5 [60)
(by m )
$ f(()) maxx 8) + Ec (2+
20(1 + c)2K f(W) + 8(1 + c)2K
3(Tmax: 8) + K
3
(by E S 2
= = (mxx 8) + Ec
- C3((maxx 8) + K.
(112)
Hence, we have
E [r] PI(A(C)BBT + P((A)D(EA AAcc]
S [T A(c)
max
< (11) 5) + Ec _ 8) + K + min g max exp
KAS
Tiax (113)
2R
which implies (18) by the bound on Pr(-A(c)) from Lemma 14
Since the sample complexity has a lower bound of 2 (1x) (og(1/))- + ollog(1/6) by Theorem
and upper bound of Tmax O(K R2 log(1/5)/e²) by Lemma 11 have ((4) O(K/e*
Hence, we must have = OKK/s))
Proof of Theorem
Since Amax and a (TTmax)
Ollo log(1/8)), we have
& = (1lgg11/6))-11)
(114)
+ (maa)) R 1og[1/0]
E
Now, notice that
log 80 = 2² log
(log(1/8))
(115)
Hence, we have
8c T1+K/2 - (log(1/8)))1 (log(1/8))++k))
= o())
(116)
These together with Lemma iimply
20
B Details of experiments
B.1 Implementation
In this section, we discuss two implementation choices that can enhance the efficiency of EllipsoidEsst. These techniques are broadly applicable and are recommended when appropriate.
28

---

0.001
0.001
0.001
6 10
0.01
0.01
2 10
0.01
4 10
x0
10
10
1/16
1/4
16
1/16
1/4
16
1/16
1/4
A/OR/S)
A/ORSY?
A/OR/S/
(a) Uniform μ
(b) Clustered μ
(c) Gaussian f
Figure Sample complexity against the regularization parameter X, where K 10, 0.1; 5 is as shown in the legend. The results are over 10 random seeds.
First, while there may be room for further refinement, we recommend setting À (R/S)2. With this setting, EllipsoidEst becomes effectively free of tunable hyperparameters. This choice can be supported both theoretically and empirically.
Theoretically, note that our confidence ellipsoid (specifically, (tt, in (T)) involves terms of the form
w(x) R² log(1 + n/x) + x2
(117)
n + x
The derivative of w(x) is
Ow(x)
nR²
n² (n+ + x)2
w(x)
(118)
dr
x.2 + nx
= which tends to (R/S)2 - So, for large n, (R/S)² tends minimize wxx), meaning that the size of the confidence ellipsoid tends be minimized with A = (R/S)² as more samples are collected from the arms.
and equals zero at x
n.tt"
The choice of À (R/S)² is also supported empirically, as shown in Figure The sample complexity 7 is minimized around À = 2 across a wide range of settings. In the figure, la is configured in three different settings: Uniform, Clustered, and Gaussian. These configurations will
be explained in detail in Appendix B.2
The second implementation choice concerns the selection of S. Recall that S must be chosen such that |us] S S, Vi E [K] in order to guarantee the PAC property. we know that μi; E [e, u]. Vi for can set S = |e] v uu]. As demonstrated in Appendix B.3 the sample complexity of EllipsoidEst tends to increase with (even with the choice of X = ()) This motivates us to shift the sample by -(e + u)/ /2, which makes the true means lie within [(e 22/ (u f)/2l.
constants f and
Consequently, we can set S = (u f) /2, which is guarantced be no greater than [e] V Ju].
B.2 Experimental settings and baselines
We design our experiments to evaluate the empirical properties of EllipsoidEst and compare its performance against baseline methods, focusing on three aspects. First, EllipsoidEst requires parameters R and S, which depend on assumptions about the reward distributions. In practice, these values may be misspecified, so is important to assess the algorithm's 's sensitivity to such inaccuracies. Second, the midpoint of the interval returned by EllipsoidEst tends overestimate the best mean (i.e.. E[i²]] > μ²)). It is useful and interesting to quantify the extent of this bias. Third, although EllipsoidEst achieves asymptotically optimal sample complexity - 0, this does not guarantec strong performance for moderate values of 8. We therefore empirically evaluate its performance under practical confidence levels and compare it standard baselines.
As baselines, we consider Successive Elimination (SE) 6. and UGapEe 4 both originally designed for best-arm identification and adapted here for best-mean estimation following the approach in [3]. While SE has suboptimal asymptotic sample complexity, is known perform well for moderate values of ó, especially when the number of arms is large. UGapEc achieves
29

---

0.001
0.001
0.001
0.01
107
0.01
10
101
10a
10
1/16
1/4
1/2
1
1/16
1/8
1/4
1/2
2
1/16
1/8
1/4
1/2
2
10
0.001
0.001
0.001
0.1
0.1
0.1
10a
10
10a
(a) Uniform P
(b) Clustered
(c) Gaussian J
Figure 5: Sensitivity of the sample complexity T to the values of R (top row) and S (bottom row), where set K 10, 0.1; ō is as shown in the legend. The results over 10 random seeds.
asymptotically optimal order of sample complexity for best-arm identification and also demonstrates strong empirical performance at practical confidence levels. Specifically, we use the SE variant proposed in [13], which is inspired by the original SE but tailored for best-mean estimation. For UGapEe, we adopt the two-step procedure from 13: first, identify the best arm using UGapEc, and then sample that arm to estimate its mean with the desired confidence leve
typically assume that each arm's reward follows Bernoulli distribution. This choice aligns with the baselines (SE and UGapEc), which are originally designed for bounded reward distributions. To assess the robustness of our findings, also examine settings with Gaussian reward distributions in Appendix [.6] We consider three configurations for the mean vector fa: Uniform. Clustered, and Gaussian. In the Uniform configuration, the means are evenly spaced in [0, 1], with = i/(K + 1i. E [K]. In the Clustered configuration, all arms share the same mean: 14 1/2, vi E [K]. In the Gaussian configuration, the means follow a Gaussian-shaped distribution centered at 0.5. Specifically, we compute the percent point function (inverse CDF) of standard normal distribution at the 100(i 0.5) percentile, then linearly scale the values so that μl and μ 0.9.
In experiments,
We assume that the of EllipsoidEst knows that the rewards follow Bernoulli distribution. This allows the user to set / S 1/2, while shifting the sample by -0.5 as we have discussed in Appendix B.J In all experiments, fix e 0.1 and vary 6 and K to evaluate the performance of EllipsoidEst under different confidence and problem-size settings.
B.3 Sensitivity to At and S
Figure S examines the sensitivity of the sample complexity 7 of EllipsoidEst to the values of R and S. In the top row, we fix S = 1/2 and vary Rt while in the bottom row, we fix R 1/2 and vary S.
The sensitivity of sample complexity to is consistent with our asymptotic analysis, which shows that E[r] scales 2R² f(4) log(1/8). implying approximately quadratic growth with respect R. In contrast, the influence of is less direct but still significant, as it affects the size of the confidence ellipsoid through the term B(t, 8) in (IO). As shown in the figure, sample complexity increases with larger values of S, which supports the sample-shiftnng technique described in Appendix B.I] Overall, while the impact of S is weaker than that of R, it still nogligglig,,,,, underscoring the importance of setting both parameters carefully.
"The proof of Lemma 4 in 13 does not hold for the case when the samples from best-arm identification is reused for best-mean estimation: hence, set M, 0 in Algorithm 2 in (13).
30

---

0.001
0.001
0.1
0.1
0.001
0.1
00.1
0..
-0.1
1/4
1/2
1/16
1/8
R
0.1
0.1
0.11
0.001
0.01
0.01
0-
0.001
0.01
-0.1
-0.1
1/32
178
1/2
2
1/32
1/8
1/2
8
1/32
1788
1/2
(a) Uniform μ
(b) Clustered μ
(c) Gaussian 1
Figure 6: Sensitivity of the estimated best-mean ji* to the values of R (top row) and S (bottom row), where we set = 10, 0.1; 5 is as shown in the legend. The results are over 10 random seeds.
When R and S are set too high, the sample complexity increases unnecessarily; when set too low, they lead to significant emrors in the estimated best-mean fi* This trade-off is illustrated in Figure particularly in the Uniform and Gaussian configure configurations, where ji* exhibits significant deviation from the true best-mean μz when or S is consistently overestimated, which we discuss in detail in Section 7.3
low. For the Clustered configuration, the best mean is
B.4 Comparison against baselines
Figure compares the sample complexity of EllipsoidEst against two baseline methods Successivee Elimination (SE) and UGapEc-bodd bottc adapted for best-mean estimation. All three methods satisfy the same PAC guarantee: the best mean is estimated within e error with probability least 8. The results show that EllipsoidEst consistently outperforms the baselines when the number of arms is small moderate (up to around K 16). Moreover, as predicted by theory, EllipsoidEst exhibits the slowest growth in sample complexity as log(1/5) (i.e., as -> 0). UGapEc performs poorly when K is small or when the true means are tightly clustered, while SE shows faster increase in sample complexity (as d + 0) across settings. Overall, although each method has its own strengths and limitations, EllipsoidEst demonstrates robust and competitive performance configurations of practical interest.
Figure highlights limitation EllipsoidEst by showing how its sample complexity scales with the number of arms K. As the figure illustrates, the sample complexity of EllipsoidEst increases more rapidly than that of the baseline methods as K grows. This observation motivates further research on best-mean estimation algorithms that scale more gracefully with the number of arms.
estimate that is within of the true best-mean with probability at least 1 - ó. Here, we set ε = 0.1 and 5 = 0.01 in the settings of Figure The sox-and-whisker plots indicate that, in every case, the returned estimates lie within 8 0.1 of the true best-mean across all 30 random seeds. In Appendix B.5 we discuss the bias in the estimated best-means.
Figure confirms the correctness of the algorithms in returning
B.5 Bias in the midpoint of the interval
As discussed in Section 7.3 EllipsoidEss returns the output fi* that typically exceeds the maximum of the empirical means, max, Ais (T), which itself tends to overestimate the true best-mean μ²' due to the winner's curse. Figure 10 explores this bias in the output-the the midpoint of the interval that contains the true best-mean with high probability- returned by EllipsoidESs, using the same settings Figure 8 The red curve shows the bias in the midpoint (i.c., ft μ²' As expected, the midpoint
31

---

K =
10
10a
UGapEc
SE
EllipsoidEst
10*
UGapEc
UGapÉc
SE
SE EllipsoidEst
10a
10a
10a
3
4
1
2
2
3
(1/6)
(1/6)
logzo (1/6)
K
16
10
10a
UGapEc
SE
UGapEc
EllipsoidEEt
++- UGapEc SE
SE EllipsoidEst
EllipsoidEst
10a
4
2
2
3
loguo (1/6)
logao (1/5)
logzo
K
32
100
10*
10*
UGapEc
UGapEc
SE EllipsoidEst
EllipsoiEEst
UGapEc
EllipsoidEst
10a
10a
logio (116)
logao (1/6)
logio
(a) Uniform /
(b) Clustered
(c) Gaussian ja
Figure 7: Sample complexity t of EllipsoidEst compared against baselines, Successive Elimination (SE) and UGapEc, where vary 6, setting 0.1 and K as indicated in above the panels. The results are based on 30 random seeds.
UGapEc SE
UGapÉc
SE
EllipsoidEst
10
UGapEc
SE
10a
EllipsoidEst
10a
(a) Uniform P
(b) Clustered
(c) Gaussian
Figure 8: Sample complexity r of EllipsoidEst compared against baselines, Successive Elimination (SE) and UGapEc, where vary K, while setting 8 = 0.01, 0.1. The results are based on 30 random seeds.
returned by EllipsoidEst consistently overestimates the best mean, with the bias being particularly pronounced when the number of arms K is large when the true means tightly clustered- scenarios where many arms are close to optimal. Note that despite the bias, the midpoint (output) f** still satisfies the PAC guarantee with 0.1 in this experiment: the bias remains below e, in line with the theoretical guarantee.
The blue curve in Figure 10 illustrates the bias in the maximum of the empirical means (i.e., max; (7((7) ,²"), based on the samples collected by EllipsoidEst. expected, this value allue-already stored in the memory of EllipsoidEst-ins notably less biased than the output ft".
32

---

K = 8
0.60
1.00
1.00
0.55
0.95
0.95
0.90
0.45
0.85
0.85
0.40
0.80
UGapEc
Ellissidesst
UGapEc
SE
EllipsoidEst
UGepEc
SE
EllipsoidEst
K 16
1.05
0.35
0.95
1.00
0.50
0.90
0.95
0.90
0.40
UGapEc
EllipsoidEst
UGapEc
SE
EllipsoidEst
UGapEc
SE
EllipsoidEst
K 32
0.60
1.00
1.05
0.55
0.50
0.95
0.45
0.85
0.90
0.40
0.80
UGapFc
EllipsoidEst
UGapEc
EllipsoidEst
UGapEc
FilipsoldEst
(a) Uniform μ
(b) Clustered
(c) Gaussian
Figure 9: The best means estimated by UGapEC, SE, and EllipsoidEst in the settings of Figure with 0.1 and 5 = 0.01.
0.1
0.1
0.1
+ A
0.05
+ maxıi
max
+
A
+
maxii
32 K
128 256
256
(a) Uniform μ
(b) Clustered
(c) Gaussian
Figure 10: Bias in the midpoint of the confidence interval returned by EllipsoidEst, where we vary K, while setting 8 = 0.01, 0.1. The results are based 30 random seeds.
Also, recall from Section I that, although we have framed the problem as best-mean estimation follow- ing the multi-armed bandit literature, our original motivation was to estimate the mean performance in worst scenarios. In such settings, the overestimation can be viewed as form of conservatism, which is typically more appropriate than optimistic estimates in safety-critical applications. In fact, an unbiased estimate may unintentionally underestimate risks and lead to overly optimistic conclusions from the perspective of confidence guarantees, which can be undesirable from the standpoint of safety assurance.
33

---

K =
10a
UGapEc
SE
EllipsoidEst
104
UGapEc
UGapÉc
SE
SE EllipsoidEst
10a
10"
10a
3
4
1
2
2
3
6
(1/6)
logao (1/6)
logzo (1/6)
K
16
10
10
10a
UGapEc
SE
UGapEc
EllipsoidEst
UGapEc
SE EllipsoidEst
-- SE
EllipsoidEst
10a
4
2
5
2
3
loguo (1/6)
logao (1/5)
logzo
K
32
100
10*
10*
UGapEc
UGapEc
SE EllipsoidEst
Elli
UGapEc
EllipsoidEst
10a
10a
2
logio (1/6)
logao (1/6)
logio
(a) Uniform /
(b) Clustered
(c) Gaussian ja
Figure 11: [Gaussian reward distributions] Sample complexity of EllipsoidEst compared against baselines, Successive Elimination (SE) and UGapEe, where vary 8, setting 0.1 and K as indicated in above the panels. The results are based on 30 random seeds.
B.6 Gaussian reward distributions
In this section, we assume that each arm's 's reward follows a Gaussian distribution. The standard deviation of the Gaussian distribution is fixed R = 1/2. Similar the previous experiments, consider three configurations for the mean vector μc: Uniform, Clustered, and Gaussian. Hence, the means are in [0, 1], which we assume be known and set S 1/2 (while shifting the sample by -0.5).
While EllipsoidEst is guaranteed estimate the best mean within error with probability least 1 1 this setting, the PAC guarantees of the baselines -SE and UGapEc-do not formally extend here, they
originally designed for bounded reward distributions. Nevertheless, apply them as if each arm's 's reward follows a Bernoulli distribution, in order to assess the robustness of our findings about EllipsoidEst across different reward models.
Figures present results analogous to those Figures 7 but for the case of Gaussian reward distributions. The similarity between the two sets of results suggests that our findings based on Bernoulli rewards are robust to changes the underlying distribution.
B.7 Computational requirements
Although running time is not the primary concern in best-mean estimation, it is still important that algorithms do not require excessive computation. Here, we compare the running time of EllipsoidEst to that of the baselines. All experiments in Appendix conducted on single CPU core with 4 GB of memory and no GPU acceleration, in a cloud environment.
B including those reported previously, were
34

---

+- UGapEc
+- UGapEc
EllipsaidEst
10*
EllipsoldEst
UGapEc
SE
10a
FilipsoidEst
10a
16
32
64
32
64
2
4
16
32
64
(a) Uniform μ
(b) Clustered
(c) Gaussian
Figure 12: [Gaussian reward distributions] Sample complexity of EllipsoidEst compared against baselines, Successive Elimination (SE) and UGapEc, where we vary K, while setting = 0.01, 0.1. The results are based on 30 random seeds.
K 8
10
10
10
time (secones)
time (secones)
time (seconds)
10-1
UGapEc
10
UGapEc
10
UGapEc SE
EllipsoidEst
EllipsoidEst
EllipsoidEst
Ing (1/8)
(1/8)
logu (1/8)
16
10
10-4
time (seconds)
time (secords)
(seconds)
10-5
UGaaEC
UGapEc EllipsoidEst
10-5
UGapEc
EllipsoldEst
20.3
EllipsoidEst
10"*
logio (1/51
logio (1/61
logio (1/5)
32
10-4
time (secones)
time oseconds)
time (seconds)
10-3
o.. UGapEc
UGapEc
SE EllipsoidEst
10-5
UGapEc
EllipsoidEst
10
EllipsoidEst
Iagio (1/5)
loguo (3/51
logu (3/8)
(a) Uniform μ
(b) Clustered μ
(c) Gaussian 1
Figure 13: Running time of EllipsoidEst compared against baselines in the settings of Figure
Figures 13 14
report the running times of EllipsoidEst and the baselines the same settings as Figures 788 The reported time measured until each algorithm returns output, and it includes the time to generate samples. As a result, the number of samples an algorithm requires is the primary factor affecting its running time.
While the running time of each algorithm can vary significantly with implementation-ann our implementations are not fully optimized-, we can already conclude from these results that all algorithms are sufficiently efficient from computational perspectives. particular, each algorithm requires well under millisecond per sample.
35

---

+-
USopEc
+
UGopÉc
time (seconds)
10P
time (seconds)
101
time (seconds)
10a
SE
EllipsoldEst
EllipsoidEst
UGapEc
10a
SE
10-1
10"1
EllipsoddEst
10"3
10
2
16
32
64
16
32
64
4
8
16
64
(a) Uniform μ
(b) Clustered
(c) Gaussian
Figure 14: Running time of EllipsoidEst compared against baselines the settings Figure
B.8 Properties of the optimal solution of (P1)
Recall that the difficulty of best mean estimation stems from the non-convexity of the optimization problem (P1). While the prior work on best arm identification has addressed such non-convexity with convex reformulation [12 211, (P1) does not admit such convex reformulation, and the lower bound remains inherently nonconvex. This leads to challenges such as possible discontinuities in the optimal allocation and the lack of structure typically exploited in classical settings. In this section, we provide a numerical example where the solution of (P1) has multiple disconnected local minima.
Specifically, Figure I shows the optimal value fU, (1) of (P2) as function of U for the setting where = = 0.1, K = 512, μl = 1, and μ4 = 0.971525 for + 1. In this case, the objective fUU μ)) has two local minima U As 1.1633 and As 1.1745. For μ4 around the above values, the optimal solution discontinuously changes between these U's
This phenomenon simply arises from the fact that the feasible region is nonconvex. The Hes- sian of the left-hand side (LHS) of has eigenvalues Ti + 1 + 4(U p² 2 with respect (ra, U). This means that the LHS of semidefinite and thus the feasible region is nonconvex.
Vr² + 4(U m,)²² I 0 and
negative-
Although nonconvex optimization also appears in the lower-bound analysis of classical best arm identification, an important distinction lies in the availability of a convex reformulation.
In classical best arm identification, the lower bound (e.g., Proposition 16 in 12 and (1) in 21 takes form:
max inf WEE XEAI(()) aE[K]
Σ
wallpay Aa);
(119)
which is nonconvex problem if first solve the inner minimization. However, this be equivalently rewritten as linear program with infinitely many constraints:
max I S.t. WER
Σ [E[K]
wod Aa) 3,00 E Ali(p),
(120)
where the objective and constraints are linear (and hence convex) (r, w). While the constraint set indexed by X E All(1)) is nonconvex, the resulting optimization problem enjoys desirable properties such as convexity (and often uniqueness) the optimal solution set, and continuity the optimal allocation with respect to μ. These properties crucial for algorithms like Track-and-Ster which rely on the property that the allocation gradually converges to the optimal one.
In contrast, our problem does not admit such a convex reformulation, and the lower bound remains inherently nonconvex, leading to the discontinuity in the optimal allocation as shown with Figure [
B.9 Comparison a deviation inequality for exponential families
Here, we consider stopping rule based on deviation inequality for exponential families proposed in [12 for the case of Gaussian distributions. Specifically, Theorem 9 in [12 suggests the stopping
36

---

rule where the B(t, 5) in Step 10 of Algorithm
is replaced with the (t, 6) defined as follows:
log(110)
(6/
(e = KCc
4R²
log (4 + log(N,(t))),
(121)
K
KE|K]
where
g(L) + a
Co(+) = min
(122)
8E(1/2,1)
g(5) = 25 2 log(4E) + log <(2E) - log( - E),
(123)
2
where is the zeta function. The stopping rule based on Bet guarantees the correctness of the algorithm for Gaussian arms.
Since (tt, 8) = (log N:(t)) and (tr 6) = Olog log (t)). the algorithm terminates earlier with the stopping rule based on Ber than with the one based on [t,, 8) the limit of N2 - co. However, here we show B(t, 5) < (tr 5) for moderate values of (t) in typical cases of practical interest.
We first derive a lower bound of (e) Observe that
g(5)
Ca(x) 2 min
+
min (E(1/2,1)
(124)
{E(1/2.1)
&
2 11
(125)
where 7j 1.4169 can be verified numerically (see Figure 15a
Hence, we have
Bet(t, 5) B. (t, Rn + 2R log(1/6) 4R²
log(4 log(NN
(126)
iE[R]
We also derive upper bound of ();
No(1)
8(t,8) & B(t, 6) = 2R log(1/0) AS* R²
log
(127)
A
kE[K]
Now, consider the case where R = S = and n = N₂((), Vi E [K]. We also (optimally) set (R/S)² in Btt, 5). Then have
Bit, 6) = 2R (og(1/0)) + Rº K (log(n 1) + 1)
(128)
(t, (t, 6) = 2 log(1 (1/5) ))) + R² K log(4 + log(n)) + 2n).
(129)
can be verified numerically (see Figure 15b) that
log(n + 1) + < log(4 + log(n)) ) + 2n, Vn < 549906
(130)
In Figure 15c we compare the values of (t,,, 8) and (t, Although Ser 8) = Olog log N:(())
get smaller than ((t, = Ollog Nt) for large Ni(t), observe ((t, < (t,5) for moderate values (t( (specifically, N&(t) S 5 x 109) that are of practical interest.
B.10 Ablation
In this section, we conduct the following ablation studies to assess the effectiveness of our stopping rule and sampling strategy against relatively naive choices: (i) We change the stopping condition such that the algorithm terminates when
L; 2 U 2
(131)
holds. (ii) We fix the sampling strategy UCB (i.c., the algorithm never enters Phase 2).
Figure 16 shows the sample complexity т of EllipsoidEst with our proposed stopping rule with the confidence ellipsoid (EllipsoidEst) and the one with the naive stopping rule with (I3I) (Naive). Observe that the choice of stopping condition can significantly affect performance, especially when is clustered.
On the other hand, while two-phase sampling strategy is crucial for our theoretical guarantees, we find that its empirical impact is limited in the settings considered in our experiments. Specifically, in the settings of Figure T6 the differences in the stopping times are at most few percent between the two sampling strategies.
37

---

suh-Gauasler
14
exp famiy
275
SEEV
14009
230
150
225
100
4lbg(4 1 logint) +.
150
1
50-
125
10
10'
10
10
10"
10
1.00
0.5
0.6
0.7
0.8
0.9
1.0
10'
10'
10'
10
10
10*
Ald) vie.
(b) 3(t, 8)
(1,
(())// 2
1.4169
549906
(c) ((t,
(c) The value of (tt, 5) in our stopping rule Gaus-aan))i and Ber 5) for the bound based on the deviation inequality in [2 (exp-family), where K 16 and 0.001.
Figure 15: (a)-(b) Numerical verifications of 125) and (130)
10
10*
EllipsoidEst
EllipsoidEst
Ellipsoidest
Naive
Naive
Naive
4
2
(1/6)
(1/8)
logoo
(a) Uniform μe; K = 16
(b) Clustered pa; K 16
(c) Gaussian K 16
10
EllipsoidEst
EllipsoidEst
Naive
Naive
+ Nalve
10
10a
10a
10
10a
10a
(d) Uniform 8 0.01
(e) Clustered p 0.01
(1) Gaussian μa; 0.01
Figure 16: Ablation study comparing the sample complexity r of EllipsoidEst with the proposed stopping rule (EllipsoidEst) and the naive stopping rule (Naive), where we vary K and indicated, while setting
0.1. The results are based on 30 random seeds.
C Societal impacts
This work is expected to have both positive and potentially negative societal impacts. On the positive side, our method improves the data efficiency estimating the mean performance the best or worst case, which is particularly valuable in domains where data collection is costly time-consuming, While originally motivated by the need to provide safety guaranties for AI agents, the proposed approach may have broader societal applications in areas such as healthcare, finance, and scientific research- ffelds where rigorous safety and performance assurances are essential. On the negative side, method could be misused if the PAC guaranty is misunderstood. In particular, the midpoint of the interval returned by our method should not be applied as a point estimate in use cases that require unbiased estimates.
38

---

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:
The contributions and claims are accurately summarized the end Section
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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 other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The proposed algorithm has relatively poor performance for large number of arms, and this is shown and discussed with Figure 3b in Section and with Figure X in Appendix [B.4
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 sell-speciiiitiinn 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?
39

---

Answer: [Yes]
Justification: All the theoretical statements are stated with full set of assumptions, and complete proofs presented in Section S and Appendix
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 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 encouraged 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 or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
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 or not)?
Question:
Answer: [Yes]
Justification: All the details of experimental settings are explained in Section 7 or Ap- pendix B and source code is submitted as the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to 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.
If 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 novel architecture, describing the architecture fully might suffice, or if the contribution a 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 to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either 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 reprodueibility may be tricky in some cases, in which authors are welcome to 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 be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
40

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We submit the source code as supplementary material together with README.nd, which includes the instructions on how to set up the environment and how to reproduce all of the experimental results reported in the paper. This paper does not use any datasets.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might 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 NeurlPS code and data submission guidelines (https
ptaips.cc/publicgu.ddeees
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. only subset of experiments are reproducible, they 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 much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The proposed algorithm has a single hyperparameter X, and we set its value as X (R/S)² based on analysis. Our experimental settings do not involve train-test split.
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, 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 all figures of experimental results, we plot standard deviations as error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
41

---

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).
The method for calculating the error bars should be explained (closed form formula, call to 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.
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 not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars 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.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The computer resources detailed in Appendix B.7 Also, while the running
time of an algorithm is not our primary concern, we report the running time in Appendix B.7 B.7
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums 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 itdn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: We have carefully read the NeurIPS Code of Ethics and ensured that this paper follows the code.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss both potential positive societal impacts and negative socictal impacts in Appendix
Guidelines:
42

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt 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 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 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 intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release 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 ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release data or models.
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 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
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: [Yes]
Justification: We use numpy, scipy, matplotibb, jupyterlab, which explicitly mentioned in pyproject.toml files. These libraries have BSD-style or MIT licenses.
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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
43

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thood cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
If this information is not available online, the authors 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: [Yes]
Justification: README. provides all of the necessary information to run the source code for reproducing the experimental results.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of 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 is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in 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 in the main paper.
According to the NeurlPS 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
44

---

Depending on 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: We have used LLMs for writing and editing and for implementing standard methods such bisection.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurl)) hatt:e///eerrrppccc///ooffrrrrrr /tt///////oeeeeeee////////../. for what should or should not be described.
45


Reviews:
[{"review_id": "dYL4vId5eT", "reviewer": "Reviewer_Cj7t", "summary": "The authors consider the task of best-mean estimation in a pure exploration multi-armed bandit setting. Specifically, their objective is to identify an estimate of the mean corresponding to the best arm within a threshold $\\epsilon$  using as few samples as possible. First they provide an instance-specific lower bound that is asymptotic. Then, they propose an algorithm who sample complexity matches that of the lower bound asymptotically. The authors further complement their results with a numerical experiments.", "questions": "-  The notation $\\sum_{i}$ is not rigorous. What are the limits in the sum? I think you want to say $\\sum_{i \\in [K]}$. \n-  The authors say that their lower bound instance dependent constants involves a non-convex optimization problem which does not arise in classical bandits setting. This is a bit confusing to me because in the classical best arm identification setting the optimization problem involved in the lower bound is also nonconvex (e.g. see [20]). Can the authors clarify this point? \n- The authors claim that the change-of-measure argument requires substantial changes because with they deal with many answers. I think this is over-claiming the difficulty of the problem. Can the author be more precise why this is a challenging step in their analysis? \n-  The authors rely on the concentration of Lemma 3 to derive their stopping rule which relies on the self-normalized martingale bound given in [1]. Why not use the bound given in [02] which offers a tighter dependence on $\\log\\log(t)$ rather than $\\log(t)$? this can yield faster stopping. \n\n\n\n[02]  E. Kaufmann and W. M. Koolen, Mixture Martingales Revisited\nwith Applications to Sequential Tests and Confidence Intervals,  JMLR 2021.", "limitations": "See weaknesses and questions", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strength.**\n-  The authors study a new problem in bandits corresponding to identifying an epsilon close estimate of the best mean which is an interesting questions. \n-  The authors provide instance dependent lower bounds which requires adapting the classical change-of-measure argument from the setting of best-arm identification to their new setting. \n- The authors also provide an algorithm whose sample complexity matches the lower bound asymptotically, i.e.  $\\delta \\to 0$. \n-  Even though the paper is of theoretical nature, the authors provide experimental results to complement their theoretical findings.\n\n**Weaknesses.**\n- The analysis and design of track-and-stop for this new problem \n- I think some relevant papers are missing in the literature review. The authors did not compare with the paper of Garivier and Kaufman (see [00]) which I believe already treated this work. \n- The authors only provide an asymptotic lower bound, i.e. $\\delta \\to 0$. \n- The proposed algorithm combines previously known ideas, notably similar stopping rules were considered for instance in [01].   \n- The optimality of the proposed algorithm is only asymptotic. What about the non-asymptotic regime? \n    \n\n[00] A. Garivier, and E. Kaufamm. Non-Asymptotic Sequential Tests for Overlapping Hypotheses\nApplied to Near Optimal Arm Identification in Bandit Models, Sequential Analysis\n\n[01] P. Menard, et al. Fast active learning for pure exploration\nin reinforcement learning, ICML 2021", "was_revised": true, "final_justification": "Overall, I find this work on the borderline. I Would like to maintain my score. The rebuttal did clarify few things, but I would encourage the reviewers to make rigorous some of their claims: \n\n1. Regarding the structure of the set of optimal allocation, the authors argue that this is a challenging part of their algorithm design.  In the rebuttal, they gave a numerical example as to why this the case, which to be honest would be better visualised by plot, but I believe a proof would also be much better.  The manuscript doesn't really talk about this part which I find a bit strange if it is such a challenge. This point was raised because I was trying to understand the significance and novelty of their algorithm design.\n\n2. Although minor, the authors should also make sure they use stopping rules with improved threshold. For specific distributions, like Gaussians, this is possible. The authors argued that their focus is sub-gaussian distributions. I find this argument really weak especially since their lower bounds are only for gaussians.  \n\n3. The authors should also clarify that their lower bounds are for the gaussian case, which they did not highlight in the manuscript.  \n\n4. The authors should also tone down their claims about the lower bound in view of the discussion during the rebuttal. I find the result to rely heavily on existing ideas around the change-of-measure for deriving lower bounds not that this diminishes their contributions. For example, non-convexity of the optimisation problem is standard in bandit settings.", "rebuttal": "Thank you very much for your detailed and constructive comments. In the following, we respond to your questions and weaknesses, addressing them in this revised order.\n\n**[Q1] Notation**\n\nThank you for pointing this out. We agree and will revise the notation to $\\sum_{i\\in[K]}$ for clarity and rigor.\n\n**[Q2] Non-convexity**\n\nWe agree that, in classical best arm identification, the lower bound can also be formulated as a nonconvex optimization. However, an important distinction lies in the availability of a convex reformulation.\n\nIn classical best arm identification, the lower bound (e.g., Proposition 16 in [02] and (1) in [20]) takes the form:\n$$\n\\max_{w \\in \\Sigma} \\inf_{\\lambda \\in \\mathrm{Alt}(\\mu)} \\sum_{a \\in [K]} w_a d(\\mu_a, \\lambda_a) $$\nwhich is indeed a nonconvex problem if we first solve the inner minimization. However, this can be equivalently rewritten as a linear program with infinitely many constraints:\n$$\n\\max_{x \\in \\mathbb{R}, w \\in \\Sigma_K} x\n\\mbox{ s.t. } x - \\sum_{a \\in [K]} w_a d(\\mu_a, \\lambda_a) \\le 0,\n\\forall \\lambda \\in \\mathrm{Alt}(\\mu),\n$$\nwhere the objective and the constraints are linear (and hence convex) in $(x,w)$.  While the constraint set indexed by $\\lambda\\in\\mathrm{Alt}(\\mu)$ is nonconvex, the resulting optimization problem enjoys desirable properties such as convexity (and often uniqueness) of the optimal solution set, and continuity of the optimal allocation with respect to $\\mu$. These properties are crucial for algorithms like Track-and-Stop, which rely on the property that the allocation gradually converges to the optimal one.\n\nIn contrast, our problem does not admit such a convex reformulation, and the lower bound remains inherently nonconvex. This leads to challenges such as possible discontinuities in the optimal allocation and the lack of structure typically exploited in classical settings. This is the key distinction we intended to highlight.\n\n**[Q3] change-of-measure argument**\n\nIn standard change-of-measure arguments, one typically relates the probabilities of events such as $\\Pr[(\\mbox{best arm is $i$})]$ or $\\Pr[(\\mbox{best arm is in some set})]$, which are straightforward to define when the set of correct answers is finite. In contrast, in our setting, the number of possible answers (i.e., the estimated best mean) is uncountably infinite, making it nontrivial to define the event whose probability should be bounded.\n\nTo address this, we construct appropriate events (see around the bottom of p.15) using structural properties of the underlying optimization problem, as developed in Lemma 7 and the first part of the proof of Theorem 2. For example, unlike [2] (Degenne and Koolen, 2019), where the finiteness of the answer set allows the summation $\\sum_{i \\in i^*(\\mu)}$ (Appendix B.5), we instead introduce the events $\\mathcal{E}^+$ and $\\mathcal{E}^-$ to decompose the continuum of possible answers into a finite number of sets.\n\nThat said, our main technical contributions lie in the upper bound analysis, and we will tone down the emphasis on this point in the revision if it still looks over-claiming.\n\n**[Q4] self-normalizing martingale bound**\n\nThank you for the insightful suggestion. While our current analysis relies on the concentration inequality from [1], alternative techniques, such as the one in the paper you suggested, can indeed yield similar guarantees without regularization.\n\nThat said, the referenced result does not seem to be directly applicable to general sub-Gaussian distributions. Nonetheless, adopting such techniques for specific exponential families is a promising direction, and we will incorporate this discussion in the revised version.\n\n**[W0] analysis and design**\n\nWe believe this point is intended as a strength of the paper, rather than a weakness.\n\n**[W1] Garivier and Kaufman**\n\nThe referenced paper [00] addresses the $\\varepsilon$-best arm identification problem, similar to works such as [3, 4, 8, 10, 11] that we discuss in the paper. In contrast, our work focuses on estimating the best mean with a PAC guarantee, rather than identifying an $\\varepsilon$-best arm.\n\nIn particular, [00] computes the empirical mean of an $\\varepsilon$-best arm, but this empirical mean is not guaranteed to satisfy the PAC criterion. Our setting and guarantees are therefore fundamentally different from those in [00].\n\n**[W2] asymptotic lower bound**\n\nWe agree that our lower bound is established in the asymptotic regime as $\\delta\\to 0$.  Deriving tighter or non-asymptotic lower bounds is an interesting direction for future work. That said, we note that even in the \"finite answer\" setting, the lower bound in [2] (Degenne and Koolen, 2019) is also formulated for the asymptotic regime, highlighting the inherent difficulty of obtaining sharp finite-$\\delta$ lower bounds in these problems. In particular, for the problems with multiple correct answers, we cannot directly use the high-level form [00] due to unavailability on an event that holds with probability $>1-\\delta$ in one model and with probability $<\\delta$ in alternative models.\n\n**[W3] similar stopping rules**\n\nThe construction of our confidence region is fundamentally different from that in [01]. Our key contribution regarding the stopping rule is the use of a confidence ellipsoid framework, which has been previously employed in linear bandits but not in the setting considered by [01].\n\nIn contrast, [01] uses independent confidence intervals, which is a natural and standard approach when rewards from different arms are independent, especially in the context of best arm identification.\n\nIf there are specific aspects of similarity you are concerned about, we would appreciate further clarification to ensure we address any overlooked connections.\n\n**[W4] non-asymptotic optimality**\n\nWe acknowledge that the optimality of the proposed algorithm is currently established only in the asymptotic regime as $\\delta\\to 0$. Extending these results to non-asymptotic regimes is an important and challenging direction for future work, as also noted in our response to [W2]."}, {"review_id": "8i7HzV0C8n", "reviewer": "Reviewer_nDLd", "summary": "In this paper the authors study the problem of estimating the mean value of the best arm in an unstructured multi-armed bandit problem. They assume the rewards are $R$-subgaussian, and provide a lower bound for $(\\epsilon,\\delta)$-PAC estimation that any $(\\epsilon,\\delta)$-PAC algorithm must satisfy. Then provide an algorithm that is based on a UCB principle, and conclude with experiments comparing the performance of their technique to Successive elimination and UGapEc .", "questions": "- line 118: $r_i$ is the sampling rate or number of samples?\n- line 121: unclear to  reader the role of U and why it should make P1 non-convex, and also why fixing the value makes it convex.\n- line 162: what does it mean \" It also employs a two-phase sampling strategy to minimize the need for solving non-convex optimization problems\"?\n- Knowing an upper bound $\\max_i |\\mu_i|< S$, should this quantity appear in the lower bound since we have additional information/structure about the problem? If not, why it should not appear? \n- What are the key challenges in implementing this algorithm?", "limitations": "Authors only discuss limitations in the checklist, saying that the algorithm does not perform well with a large number of arms.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strenghts**\n- The authors provide ample numerical evidence, also in the appendix, comparing Bernoulli and Gaussian rewards. Probably it could benefit to also compare to a very simple exploration technique (just uniform?)\n- Apart from some questions below, the main results for the algorithm seem sound, and the UCB approach is rather interesting.\n- Pure exploration for estimation problems in bandit/MDPs is relatively new, and there are only a few works studying this problem.\n\n**Weaknessess**\n- Overall there are some presentation issues. \n  - The presentation of the lower bound is overall a bit unclear (derivation, presentation). To a general reader, it may not seem clear why P1 should be true and why we should obtain this type of optimization problem. \n  - Also the presentation after (P2) is unclear: what is the strategy and end goal? why care about this specific case of $U$? This becomes even more confusing when $f(U;\\mu),U(\\mu),\\bar U, \\bar g$, etc get introduced.\n  - In Theorem 2 an asymptotic lower bound is presented. However, it is unclear what the two alternative models are, and what \"substantial modifications\" are required to deal with \"infinitely many possible answers\", as the authors write in line 154-155. In the appendix no guide is provided to the proof strategy.\n  - The confidence ellipsoid argument line 177-182 is unclear why it should hold, and why we need it. Similarly, the proof of thm. 4 is not well explained.\n  - Missing connections with practitioners: It is my belief that a practitioners will hardly use this method to evaluate the performance of a real system that maybe has safety constraints. However, the goal of this type of theoretical work should be to provide insights on what are the key ideas that potentially could be used in a more practical setting.\n\n\n- Technical: \n  - It is not immediately clear what is the connection with the multiple-correct answer paper (Degenne and Koolen 2019). The correct answers there are a property of the model $\\mu$. For example, their paper  is important in applications where we are interested in estimating something like $g(\\mu)$, where $g$ maps the model to some output that is not necessarily a singleton (e.g.,  the set of optimal arms). However, in this case we are interested only in estimating a single scalar value.\n  - the model assumes sub-gaussian distributions, however the lower bound seems to be written for gaussian distributions (see also the log-likelihood ratio in lemma 6). However, there may be sub-gaussian reward distributions that are easier to learn than gaussian. As of now, the lower bound seems more to be an upper bound.\n  - the algorithm seem to rely on a known upper bound $S$ on $\\max_i |\\mu_i|$, and it is not clear what happens if we do not know this constant.\n  - Not clear what are the main technical advancements. The algorithm uses an UCB based approach which seems novel, but apart from that it is not clear what are the main technical advancements compared to prior work.\n  - Proof of lemma 6: why the relative log-likelihood ratio can be factorized in this way as if the rewards are Gaussianly distributed? Don't you just assume that the rewards are sub-gaussian?\n  - Not clear why the method does not seem to perform well with $K>10$ (see fig 7)\n- Missing relevant prior work: while the authors discuss some related work, there is ample literature on the pure exploration problem. For example, lemma 6 resembles classical changes of measure originally employed by Lai, e.g., in Adaptive treatment allocation and the multi-armed bandit problem, 1987. More importantly, there is  also some prior work on policy evaluation in RL that uses BAI techniques (Russo and Pacchiano, \"Adaptive Exploration for Multi-Reward Multi-Policy Evaluation\", 2025). This paper is also related to the first comment above. How does your technique compare and what are the differences?", "was_revised": true, "final_justification": "The rebuttal directly addressed core technical ambiguities, however, there are a number of ambiguities that need to be addressed:\n\n- The lower bound is proved for Gaussians while the algorithm assumes sub-Gaussian rewards. This needs to be addressed by either assuming only Gaussian rewards or extending the lower bound discussion.\n- stopping doesn’t use  tight bounds as noted by reviewer Cj7t\n-  scalability for large number of arms $K$ is limited.\n\nWe also discussed with the authors a connection to the “multiple correct answers” paper (Degenne and Koolen, 2019). They argue that Degenne and Koolen’s analysis cannot be extended because it assumes a finite set of correct answers, whereas here the set is infinite. Does the infinitude arise because any value in an ϵϵ-ball is acceptable? Are all points in this ball equivalent in terms of information? These questions seem unanswered in the paper. My intuition is that any point in the ball is probably equivalent, and thus, even though the set is infinite, it can be viewed as a single point from a topological perspective; therefore it may not the same as the multiple-correct-answers setting. Furthermore, this issue does not seem to appear in the policy-evaluation paper by Russo and Pacchiano (2025), which treats MDPs and targets single/multi-policy evaluation for a finite/convex set of rewards. This requires further investigation..", "rebuttal": "Thank you very much for your detailed and constructive comments. In the following, we respond to your questions and weaknesses, addressing them in this revised order.\n\n**[Q1] $r_i$**\n\n$r_i$ is a sampling rate, although the sum over $r_i$ is not necessarily 1. $2R^2 r_i \\log 1/\\delta$ corresponds to the number of samples.\n\n**[Q2] role of $U$**\n\nAs discussed around Section 2, $U$ is an upper bound of the best mean. P2 is a standard linear program and thus convex. In contrast, P1 includes higher-order terms such as $r_i U^2$ and $r_i \\mu_i U$, which introduce nonconvexity in the joint variables $(r,U)$. Once $U$ is fixed, these terms become linear in $r$. For additional discussion on the nonconvexity of P1, see our response to [Q2] of Reviewer Cj7t.\n\n**[Q3] meaning of a sentence**\nIt means that we use the two-phase strategy that computes the nonconvex optimization only once at the time of the phase shift instead of computing it at every round like standard Track-and-Stop algorithms. This significantly reduces the computational burden associated with nonconvex optimization.  For further details on the two-stage strategy, see our response to [Q2] from Reviewer SxLQ.\n \n**[Q4] role of $S$ in the lower bound**\n\nIt is true that the lower bound should change if we know $S$, though it is standard in the literature after [1] not to consider this gap. Please also see our response to [W8] on the confidence region.\n\n**[Q5] implementation challenges**\n\nThere are no major difficulties in the actual implementation of the algorithm besides it relies on knowledge of instance-dependent constants ($R$ and $S$), which may not always be readily available in practice.\n\nInstead, the main challenges lie in its design, which enables computing the optimal allocation only once. This requires carefully determining the timing of the phase shift so that the estimates are sufficiently accurate, while avoiding over-exploration of any arm. A further challenge is that the estimates at the time of the phase shift might be inaccurate with a small but nonzero probability. To ensure a bound on the expected number of samples (rather than a high-probability bound), the algorithm is designed so that it still terminates within a reasonable number of rounds even when the computed allocation is suboptimal.\n\n**[W1] presentation of the lower bound**\n\nEach constraint in P1 corresponds to ensuring that the interval $[U-2\\epsilon, U]$ contains the true best mean. Specifically:\n- (2) ensures that each $\\mu_i$ is below $U$ (large $r_i$ is needed if the gap $U-\\mu_i$ is small). \n- (3) ensures that at least one $\\mu_i$ is above $U-2\\epsilon$, confirming that the interval contains a valid candidate for the best mean.\n\nGiven these constraints, we need to choose $U$ to minimize the required number of samples, which  is captured by the objective function.\n\n**[W2] presentation after P2**\n\nThe difficulty in our problem lies in the fact that optimizing the total number of samples involves solving a nonconvex optimization problem over $U$. In contrast, once $U$ is fixed, the remaining optimization is explicitly solved. Given this situation, to extract the nonconvex and difficult feature, we introduced $f(U;\\mu)$ as the optimal value given $U$ (which is nonconvex in $U$) and $U(\\mu)$ as its minimizer, respectively. Since this is a nonconvex optimization, specifying upper and lower bounds of the optimal solution is beneficial for implementation and analysis, for which quantities like $\\overline{U}$ and $\\overline{g}$ are introduced. We will clarify these points in the revision.\n\n**[W3] lower bound**\n\nThe alternative models are specified in (43) and (45) in the proof of Theorem 2. Constructing these alternatives requires carefully choosing values of $U$ and $L<U-2\\epsilon$, depending on the algorithm that violates the lower bound by using the discussion in Lemma 7. Such constructions are more straightforward for finitely many possible answers. For the difficulties associated with infinitely many possible answers, see our response to [Q3] from Reviewer Cj7t.\n\n**[W4] confidence ellipsoid and Theorem 4**\n\nThe argument using the confidence ellipsoid is intended to justify that, if there exists a subset of arms whose confidence region (whether rectangular or elliptical) is contained in the square defined with the interval $[U-2\\epsilon,U]$, the true best mean is guaranteed to lie within this interval. Theorem 4 formalizes this argument in a higher-dimensional setting by showing that the confidence ellipsoid allows us to conclude that the true mean lies within the desired interval.\n\n**[W5] connection with practitioners**\n\nWhile our work is primarily theoretical, it does offer a practical insight: to reliably estimate the best mean, one should construct a confidence ellipsoid around the empirical means. This approach is intuitively appealing, and we provide rigorous justification for its use.\n\n**[W6] connection with the multiple-correct answer paper**\n\nWhile the multiple-correct answer paper allows non-scalar output $g(\\mu)$, it requires that $g(\\mu)$ must be from a finite set. This finiteness is a key component in their analysis, for instance, in the lower bound derivation, where they bound the probability that the algorithm outputs a particular answer $g$ within a given number of rounds. In contrast, our setting focuses on estimating a single scalar quantity (best mean) but from an uncountable set. Due to this difference, the method and the results for multiple-correct answers cannot be directly applied in our settings.\n\n**[W7] lower bound is for Gaussian**\n\nThank you for pointing this out. Our lower bound is indeed derived under the Gaussian assumption, primarily for clarity and tractability. The lower bound can be generalized to broader sub-Gaussian models by replacing the L2 distance (which arises from the Gaussian KL divergence) with the corresponding KL divergence for the given distribution class. We will clarify this point in the revised version.\n\nWe also agree that in some cases, sub-Gaussian distributions may lead to easier learning problems than the Gaussian case, depending on the available structure or additional information.\n\n**[W8] knowledege on $S$**\n\nWe acknowledge that relying on a known upper bound $S$ is a limitation of our algorithm. However, this assumption is standard in the linear bandit literature with sub-Gaussian noise after the seminal paper by Abbasi-Yadkori et al. [1]. In some settings (e.g., Bernoulli rewards) $S$ is trivially known, but this is not always the case.\n\nWhen $S$ is unknown, the specific form of the confidence bound from Theorem 2 in [1] (which we use) becomes inapplicable. However, Theorem 1 in [1] still provides a valid anytime confidence bound that does not require knowledge of $S$, although the resulting confidence region becomes a bit complicated. We will add this clarification in the revision.\n\n**[W9] technical advancements**\n\nOur main technical contributions lie in the sampling strategy and the stopping rule, both of which differ from prior approaches in meaningful ways.\n\n**Sampling Strategy:**\nWe extend the UCB approach using a two-phase strategy, where the optimal allocation (which is nonconvex) is computed only once, at the phase transition. This avoids solving a non-convex problem at every round, which is required in traditional Track-and-Stop. The technical challenge here is to guarantee that the estimates are sufficiently accurate at the time of the phase shift, while the phase shift must occur early enough to avoid over-exploring suboptimal arms.\n\nFurthermore, unlike the sticky Track-and-Stop algorithm in the multiple-correct answer paper, our setting requires reasoning over infinitely many candidate answers. This introduces additional difficulty, as the set of relevant alternatives (i.e., those that could invalidate the current answer) dynamically changes with the estimates, which further complicates the analysis.\n\n**Stopping Rule:**\nWe introduce the use of a confidence ellipsoid for best mean estimation in an unstructured bandit setting. While such ellipsoids have been used in linear bandits, their application to identifying the best mean among independent arms is novel.\n\n**[W10] proof of Lemma 6**\n\nThank you very much for pointing this out. In Section 4, we derive the lower bound under the Gaussian assumption, which should have been stated more clearly.  For general sub-Gaussian rewards, the L2 distance should be replaced with the corresponding KL divergence.\n\n**[W11] performance under many arms**\n\nWe agree that the performance degradation with larger numbers of arms is worth further investigation. However, this phenomenon is not unique to our setting and has also been widely observed in the literature on best arm identification [6]. Algorithms that achieve asymptotically optimal sample complexity often underperform in practice when there are many arms. For instance, Approximate Best Arm in [6] is asymptotically optimal but resorts to Naive Elimination, an algorithm with suboptimal asymptotic complexity, when the number of arms is small or after enough suboptimal arms have been eliminated.\n\n**[W12] Lai 1987**\n\nThe change-of-measure technique used in Lemma 6 indeed follows the classical approach developed by Lai (1987), and we will make this connection explicit with proper citation. The key difference lies in how the technique is applied: in our work, it is adapted to handle the setting with infinitely many correct answers, which introduces new technical challenges, particularly in the proof of Theorem 2.\n\n**[W13] Russo and Pacchiano 2025**\n\nThe paper by Russo and Pacchiano (2025) focuses on evaluating the value of all policies, rather than estimating the value of the best policy. In the context of multi-armed bandits (i.e., reinforcement learning without states), their objective corresponds to estimating the means of all arms, while our work focuses on estimating the best mean with high confidence."}, {"review_id": "g77qalokTz", "reviewer": "Reviewer_Q5FJ", "summary": "The paper proposes an algorithm that returns an $\\epsilon$-accurate estimate of the largest mean (by returning an interval smaller than $\\varepsilon$ that contains $\\mu_\\star$) in a bandit model with probability $1-\\delta$. It also gives an asymptotic lower bound on the sample complexity of any such $(\\varepsilon,\\delta)$-PAC algorithm, which is matched by their algorithm. The lower bound can be written as a solution to a non-convex optimization problem, and a (somewhat) efficient computation of the resulting optimal allocation is proposed. Interestingly the proposed algorithms calls this \"optimal solver\" only once and therefore remains efficient.", "questions": "1. Can you fix the lower bound? \n\n2. I wonder whether the proposed regularization is actually essential. Your correctness analysis hinges on the concentration inequality of [1] which indeed requires regularization to concentrate all arms simultaneously. But you could use other results that do not require regularization, and would yields a $\\log\\log(n)$ instead of $\\log(n)$, see, e.g., https://jmlr.org/papers/volume22/18-798/18-798.pdf\n\n3. Did you experiment with the naive baseline described in l.171-174? E.g. use LUCB as a sampling rule (which doesn't depend on $\\epsilon$) and stop whenever the confidence interval of the empirical best arm is of size at most $2\\varepsilon$. I suspect this would be already better compared to the naive two stage baseline used in the experiments (and perhaps we can get a simple sample complexity bound and compare it to the optimal one, at least numerically).\n\nMinor: \n* the statement of Theorem 2 is weird. Why are you keeping the parameter $\\eta > 0$ and not letting it go to zero which removes it?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\nLower-bound inspired algorithms are ubiquitous in the growing literature on pure exploration in bandits. This paper makes however an important step forward by tackling a problem in which the set of correct answers (all possible estimators within epsilon) is infinite. The new lower bound is definitely non trivial, as well as the analysis of the proposed algorithm. I also appreciated the experimental section. \n\n## Weaknesses\n\nThe lower bound is cool, but  I would have presented it differently and (2) more importantly there is currently a mistake in its proof \n\n(1) Section 4 starts with an optimization problem (P1) and discussion about it without connecting it directly to the lower bound. I would start with Theorem 2 and define f(\\mu) therein as a minimum over r and U in $(\\mu^\\star,\\mu^\\star + \\varepsilon)$ satisfying the constraints (2) and (3). Then after that you can discuss its computation. It is not clear to me whether we even need (P1) with a fully unconstrained $\\mu$ actually. \n\n(2) In the proof of the lower bound, some alternative models $\\lambda_i^+$ and $\\lambda_i^-$ are chosen. However, these models depend on $\\delta$. Lemma 6 on the other hand is an asymptotic result that is only valid for fixed instances $\\mu$ and $\\lambda$, so you cannot apply it to get Equation (50). Lemma 6 is based on asymptotic arguments (the law of large numbers), maybe you could use instead some non asymptotic result relating the probability of an event under two different models, such as the change of distribution Lemma used in [5]. In any case, I think a precise proof sketch of the lower bound is needed in the main text. Also the lower bound should hold only for Gaussian distributions (even if algorithms work for sub-Gaussian ones), in the proof of Lemma 6 when you use the change of distribution, $L_t$ really need to be your (Gaussian) likelihood. \n\nOn the upper bound side, I found it a bit hard to get Corollary 1 from Theorem 5. The finite time upper bound in Theorem 5 seem to feature other terms that depend on $\\log(1/\\delta)$, in particular the last one with $T_{\\max}$. Where does the parameter $c$ comes from in $\\delta^{c^2}$? Even if it is nice to have some an explicit upper bound instead of only an asymptotic result, I am not sure Theorem 5 is very insightful for the reader.", "was_revised": true, "final_justification": "I raised my score in light of the correction in the lower bound.", "rebuttal": "Thank you very much for your detailed and constructive comments. In the following, we respond to your questions and weaknesses, addressing them in this revised order.\n\n**[Q1] lower bound**\n\nThank you for your careful reading. Indeed, there is an issue in the current proof of Theorem 2 (Appendix A.2.2) due to the dependence on $\\delta$.\nWhile it would be possible to correct the proof by deriving a non-asymptotic version of Lemma 6 as suggested, it can also be easily fixed by the following simple modification.\n\nNow we consider a sequence $\\delta_1,\\delta_2,\\dots\\to 0$ satisfying $\\frac{\\mathbb{E}[\\tau_n]}{\\log 1/\\delta_n}\\le 2(1-\\eta)R^2 f(\\mu)$.\nAs pointed out, $(U,L)$ satisfying $U-L>2\\varepsilon$, (41) and (42) depends on $\\delta$.\nStill, $U'=U'(\\delta):=\\min ( U(\\delta), \\mu^\\star+2\\varepsilon ) \\in [\\mu^\\star, \\mu^\\star+2\\varepsilon]$ and $L'=L'(\\delta):=\\max(L(\\delta), \\mu^{\\star}-2\\varepsilon)\\in [\\mu^\\star-2\\varepsilon, \\mu^\\star]$ become bounded sequences and therefore there exists a subsequence $\\delta_{n_1},\\delta_{n_2},\\dots$ such that $U'(\\delta_{n_m})\\to U_{\\infty}$ and $L'(\\delta_{n_m})\\to L_{\\infty}$ for some $U_{\\infty},L_{\\infty}$ such that $U_{\\infty}-L_{\\infty}\\ge 2\\varepsilon$.\nSince $\\frac{\\mathbb{E}[\\tau_{n}]}{\\log 1/\\delta_n}\\le 2(1-\\eta)R^2 f(\\mu)$ is finitely bounded independently of $\\delta$, we can immediately see from (41) and (42) that there exists $m_0>0$ such that, for all $m\\ge m_0$,\n$$\n\\text{(i'):  } \\exists i\\in[K],\\ \\frac{\\mathbb{E}\\left[N_i(\\tau_{n_m})\\right]}{\\log 1/\\delta_{n_m}}\n (U_{\\infty} - \\mu_i)^2 \\le  2 (1-\\eta/2) R^2\n$$\n$$\n\\text{(ii'): } \\sum_{i \\in [K]} \\frac{\\mathbb{E}\\left[N_i(\\tau_{n_m})\\right]}{\\log 1/\\delta_{n_m}}\n (\\mu_i - L_{\\infty})_+^2 \\le 2 (1-\\eta/2) R^2.\n$$\n\nBy using the finiteness of $\\frac{\\mathbb{E}[\\tau]}{\\log 1/\\delta}$ again,\nthere also exists $a>0$ independent of $\\delta$ such that\n$$\n\\text{(i''):  } \\exists i\\in[K],\\ \\frac{\\mathbb{E}\\left[N_i(\\tau_{n_m})\\right]}{\\log 1/\\delta_{n_m}}\n ((U_{\\infty} + a) - \\mu_i)^2 \\le  2 (1-\\eta/4) R^2\n$$\n$$\n\\text{(ii''): } \\sum_{i \\in [K]} \\frac{\\mathbb{E}\\left[N_i(\\tau_{n_m})\\right]}{\\log 1/\\delta_{n_m}}\n (\\mu_i - (L_{\\infty}-a))_+^2 \\le 2 (1-\\eta/4) R^2,\n$$\n\nwhich satisfies $(U_{\\infty}+a)-(L_{\\infty}-a)\\ge 2\\varepsilon +2a > 2\\varepsilon$.\n\nFrom this result, the discussion after (42) becomes valid by replacing $(U(\\delta),L(\\delta))$ with fixed parameters $(U_{\\infty}+a, L_{\\infty}-a)$ and considering the subsequence $(\\delta_{n_1}, \\delta_{n_2},\\dots)$, which derives the contradiction as in the original argument.\n\n**[Q2] regularization**\n\nThank you for the insightful suggestion. We agree that the regularization is not essential for the correctness analysis. While our current analysis relies on the concentration inequality from [1], alternative techniques, such as the one in the paper you suggested, can indeed yield similar guarantees without regularization.\n\nThat said, the referenced result does not seem to be directly applicable to general sub-Gaussian distributions. Nonetheless, adopting such techniques for specific exponential families is a promising direction, and we will incorporate this discussion in the revised version.\n \n**[Q3] naive baseline**\n\nThank you for the suggestion. We conducted the following ablation studies to assess the impact of using a naive baseline as described:\n\n(A) We fixed the sampling strategy to UCB (i.e., the algorithm never enters Phase 2).  We use UCB instead of LUCB, since best arm identification is not our goal.\n\n(B) We changed the stopping condition to a naive one: stop when $\\max_i L_i \\ge U - 2 \\epsilon$.\n\nResults:\n\n(A) While the two-phase sampling strategy is crucial for our theoretical guarantees, its empirical impact is limited in the settings considered in our experiments. We observed some cases where the two-phase and one-phase strategies behave differently, but in the scenarios we tested, both strategies yielded very similar stopping times ($\\tau$).\n\n(B) In contrast, the choice of stopping condition significantly affects performance, especially when arm means are clustered. The table below compares the stopping times ($\\tau$) under EllipsoidEst (with our proposed stopping rule with the confidence ellipsoid) versus the naive stopping condition, using the same setup as in Fig. 6(b) (Clustered) with K=16:\n\n| $\\log_{10} (1/\\delta)$       | EllipsoidEst | Naive Stopping |\n|---------|--------------|----------------|\n| 1       | 21200        | 61024          |\n| 2       | 22016        | 63073          |\n| 3       | 22816        | 65120          |\n| 4       | 23632        | 67153          |\n| 5       | 24432        | 69185          |\n| 6       | 25232        | 71217          |\n\nThese results show that the naive stopping rule can result in significantly larger sample complexity in practice. We will include this comparison in the revised version.\n\n**[Q4] Theorem 2**\n\nThank you very much for pointing this out. Since $\\eta$ can be made arbitrarily small, we can indeed remove it. We will revise the paper accordingly.\n\n**[W1] P1**\n\nThank you for the suggestion. We will revise the paper based on your suggestions.  In particular, it is not essential to define the optimization including $U$ outside $[\\mu^\\star, \\mu^\\star+\\epsilon]$ and we will clarify the equivalence in an early place.\n\n**[W2] lower bound**\n\nSee our response to [Q1]\n\n**[W3] Theorem 5**\n\n$c$ is in the third line of (19), which has the same order as $\\epsilon_c=O((\\log 1/\\delta)^{-1/3})$. It may be true that the non-asymptotic bound is not so informative in our case, and we will state current Corollary 1 as the main theorem and move the current Theorem 5 to the appendix."}, {"review_id": "GyUEdfJrjU", "reviewer": "Reviewer_SxLQ", "summary": "This paper studies how to estimate the expected ε-accurate reward of the best arm in a multi-armed bandit problem with probability at least 1 − δ. The authors propose a new algorithm, EllipsoidEst, which employs a two-phase sampling strategy and adaptively solves a non-convex optimization problem to determine optimal sampling proportions. They prove that the algorithm is asymptotically optimal and show that it outperforms previous methods in experiments.", "questions": "1. The output by the algorithm may exhibit upward bias due to the stopping rule. Is there a practical correction method or debiasing step that could be incorporated?\n2. In large-scale settings (e.g., hundreds of arms), how would the computational cost of solving the non-convex optimization scale? Are there practical heuristics or approximations that could make it scalable?\n3. In the fixed-confidence BAI setting, many algorithms stop when the best arm is identified with high probability. One can then use the empirical mean of the selected arm as an estimate of the best mean. Since the arm is correct with probability at least $1-\\delta$ and $\\delta$ is typically small, this estimate is already likely to be accurate, except in rare cases where the instance is easy and the algorithm stops early without enough samples. Therefore, the motivation for studying best-mean estimation as a separate problem is not entirely clear to me.\n4. The proposed algorithm relies on solving a non-convex optimization problem to compute the sampling ratios r, but no closed-form solution is provided. It is unclear how the optimization is solved in practice, and whether this step introduces significant computational overhead—especially when the number of arms K is large. Although the algorithm may reduce sample complexity, it could become difficult to apply in practice due to the runtime cost of solving this optimization at every round. In addition, since different solvers may yield slightly different results, it is unclear how sensitive the algorithm's performance is to the accuracy or stability of the optimization step.\n5. The experiments are limited to Bernoulli bandits and relatively small-scale settings. It would be helpful to include results on other reward distributions (e.g., Gaussian or sub-Gaussian) and larger numbers of arms to better demonstrate the algorithm's generality and scalability. Additionally, the algorithm involves several parameters,  but the paper does not include any sensitivity analysis to show how performance varies with these choices.", "limitations": "1. The non-convex optimization involved in computing sampling ratios, while tractable in small cases, may present challenges in large-scale problems with many arms.\n2. The returned estimator may have an upward bias due to the nature of the stopping criterion, which could affect applications requiring unbiased estimates.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper studies a novel bandit problem—estimating the best mean instead of identifying the best arm—under a fixed-confidence setting.\n2. The proposed algorithm, EllipsoidEst, is simple and asymptotically optimal.\n3. The paper is generally well-written and the theoretical analysis is rigorous and complete.\n\nWeaknesses:\n1. The experimental evaluation is limited: it focuses on simple Bernoulli settings with relatively small numbers of arms, and lacks comparisons on more diverse reward distributions or larger-scale settings.\n2. The estimator output by the algorithm may have a bias.\n3. The non-convex optimization is handled in the algorithm, but it may become harder to scale to larger or more complex problem settings.", "was_revised": true, "final_justification": "Thank you for your response. I have no further questions. I have raised my score.", "rebuttal": "Thank you very much for your detailed and constructive comments. We respond to your questions one by one.\n\n**[Q1] bias**\n\nOur goal is not to produce an unbiased point estimate, but rather to construct an interval that contains the true best mean with high probability. As discussed in Section 7.3, the midpoint of the returned interval is biased and should not be interpreted as a point estimate with minimal bias. We do not view this as a weakness, but rather as a fundamental property of any PAC estimate of the best mean.\n\n**[Q2] computational cost**\n\nWe have reduced the non-convex optimization problem to more tractable subproblems. Specifically, it involves (i) performing bisection to find the root of two monotonic one-dimensional functions (see Lines 129–131), and (ii) solving a one-dimensional non-convex optimization via grid search over a narrow interval $[\\underline{U}(\\mu),\\underline{U}(\\mu)\\lor\\overline{U}(\\mu)]\\subseteq[\\mu^\\star+\\epsilon,\\mu^\\star+2\\epsilon]$ (see L143-145). Both one-dimensional functions can be evaluated in time linear in $K$, the number of arms. Furthermore, the bisection is required only during Phase 1 (at each round), while the grid search is performed just once at the start of Phase 2. This structure makes the optimization computationally scalable even in large-scale settings.\n\nIn Appendix B.7, we also empirically study the computational cost of our algorithm. Figures 12–13 show that the running time of our algorithm is negligible and comparable to that of the baselines.\n\nRegarding \"more complex problem settings\" that you raised in Weakness 3, it is true that this kind of reduction to simple problem might be applicable for more complex problems. However, we believe that the current problem of best mean estimation itself has its importance as discussed in the introduction.\n\n**[Q3] BAI for best mean estimation**\n\nIn our experiments, we evaluate a representative BAI algorithm, UGapEC, with a natural modification to handle the \"rare cases\", specifically by collecting additional samples after stopping in order to ensure a PAC guarantee on the estimated best mean. However, as our results demonstrate, this approach of combining BAI with post hoc sampling is typically suboptimal compared to a method that is designed explicitly for best-mean estimation. This gap highlights the value of studying best-mean estimation as a distinct problem, rather than treating it as a simple extension of BAI.\n\n\n**[Q4] non-convex optimization problem**\n\nAs explained in our response to [Q2], we reduce the non-convex optimization to tractable subproblems: (i) bisection for solving one-dimensional monotonic equations, and (ii) grid search over a narrow one-dimensional interval. While we acknowledge that runtime may vary depending on implementation details, both bisection and grid search are simple and robust methods. Even with a straightforward implementation, the computational overhead is negligible in practice, as demonstrated in our empirical analysis in Appendix B.7. These results suggest that the optimization step does not hinder the algorithm’s practical applicability, even with a large number of arms.\n\n\n**[Q5] diverse experiments**\n\nWe agree that broader evaluations are important. In Appendix B, we provide results on more diverse settings, including Gaussian reward distributions (see Appendix B.6). Note that we experiment with up to $K=256$ arms in some settings. That said, our experiments indicate that the proposed algorithm outperforms baselines for $K\\le 16$. Since performance tends to degrade for larger $K$, we believe that extending experiments to much larger $K$ would offer limited additional practical insight.  \n\nRegarding hyperparameters, our algorithm requires one tunable parameter, $\\lambda$, and two instance-dependent parameters, $R$ and $S$. In Appendix B.1, we show that $\\lambda=(R/S)^2$ is the optimal choice in practice. We further study the sensitivity to $R$ and $S$ in Appendix B.2, demonstrating that the algorithm is reasonably robust to their misspecification."}]

Author rebuttal:

Meta-review: The paper addresses the problem of estimating the mean reward of the best arm in a multi-armed bandit (MAB) setting, distinct from simply identifying the best arm.  The authors establish an instance-dependent lower bound on the sample complexity for this problem. The author argues that straightforward application of standard MAB algorithms like Track-and-Stop cannot achieve sample optimality. They introduce a new algorithm that combines a confidence ellipsoid-based stopping condition with a two-phase sampling strategy. This design is specifically tailored to manage the challenges of the non-convexity. The proposed algorithm is simple, nearly free of hyperparameters, and achieves the instance-dependent, asymptotically optimal sample complexity. 

All reviewers acknowledged that studying the estimation of the best mean (as opposed to its identification) is interesting problem in the pure exploration bandits literature. The paper's main strength is its rigorous theoretical contribution, including the derivation of a non-trivial lower bound and an algorithm proven to match it asymptotically. The handling of a problem with an infinite set of possible correct answers (any value within $\epsilon$ of the true best mean) was seen as significant.

The authors provided thorough and convincing rebuttals, addressing the technical concerns (like the proof error), clarifying ambiguities, and defending their contributions.
Decision: Accept (poster)