Optimal Estimation of the Best Mean in Multi-Armed Bandits

Thank you very much for your detailed and constructive comments. We respond to your questions one by one.

[Q1] bias

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

[Q2] computational cost

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

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

Regarding "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.

[Q3] BAI for best mean estimation

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

[Q4] non-convex optimization problem

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

[Q5] diverse experiments

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

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

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.

[Q1] lower bound

Thank 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$. While 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.

Now 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)$. As pointed out, $(U,L)$ satisfying $U-L>2\varepsilon$, (41) and (42) depends on $\delta$. Still, $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$. Since $\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$,

By using the finiteness of $\frac{\mathbb{E}[\tau]}{\log 1/\delta}$ again, there also exists $a>0$ independent of $\delta$ such that

which satisfies $(U_{\infty}+a)-(L_{\infty}-a)\ge 2\varepsilon +2a > 2\varepsilon$.

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

[Q2] regularization

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

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

[Q3] naive baseline

Thank you for the suggestion. We conducted the following ablation studies to assess the impact of using a naive baseline as described:

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

(B) We changed the stopping condition to a naive one: stop when $\max_i L_i \ge U - 2 \epsilon$.

Results:

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

(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:

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

[Q4] Theorem 2

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

[W1] P1

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

[W2] lower bound

See our response to [Q1]

[W3] Theorem 5

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

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.

[Q1] $r_i$

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

[Q2] role of $U$

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

[Q3] meaning of a sentence It 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.

[Q4] role of $S$ in the lower bound

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

[Q5] implementation challenges

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

Instead, 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.

[W1] presentation of the lower bound

Each constraint in P1 corresponds to ensuring that the interval $[U-2\epsilon, U]$ contains the true best mean. Specifically:

• (2) ensures that each $\mu_i$ is below $U$ (large $r_i$ is needed if the gap $U-\mu_i$ is small).
• (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.

Given these constraints, we need to choose $U$ to minimize the required number of samples, which is captured by the objective function.

[W2] presentation after P2

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

[W3] lower bound

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

[W4] confidence ellipsoid and Theorem 4

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

[W5] connection with practitioners

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

[W6] connection with the multiple-correct answer paper

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

[W7] lower bound is for Gaussian

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

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

[W8] knowledege on $S$

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

When $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.

[W9] technical advancements

Our main technical contributions lie in the sampling strategy and the stopping rule, both of which differ from prior approaches in meaningful ways.

Sampling Strategy: We 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.

Furthermore, 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.

Stopping Rule: We 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.

[W10] proof of Lemma 6

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

[W11] performance under many arms

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

[W12] Lai 1987

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

[W13] Russo and Pacchiano 2025

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

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.

[Q1] Notation

Thank you for pointing this out. We agree and will revise the notation to $\sum_{i\in[K]}$ for clarity and rigor.

[Q2] Non-convexity

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

In classical best arm identification, the lower bound (e.g., Proposition 16 in [02] and (1) in [20]) takes the form:

\max_{x \in \mathbb{R}, w \in \Sigma_K} x \mbox{ s.t. } x - \sum_{a \in [K]} w_a d(\mu_a, \lambda_a) \le 0, \forall \lambda \in \mathrm{Alt}(\mu),

I thank the authors for their answers. I do need further clarifications. Please find below my questions and comments.

Regarding non-convexity of the optimization problem leading to the lower bound. The classical idea is to actually partition the continuum set of alternative parameters into a finite set of subsets where indeed the most inner problem is convex, as for instance done in [20].

$

 \sup_{\omega \in \Sigma} \min_{\lambda \in \mathrm{Alt}(\mu)}\sum_{i=1}^K \omega_i \mathrm{kl}(\mu_i, \lambda_i) =  \sup_{\omega \in \Sigma} \min_{j \neq i_\star(\mu)}\inf_{\lambda: \lambda_j > \lambda_{i_\star(\mu)}}  \sum_{i=1}^K \omega_i \mathrm{kl}(\mu_i, \lambda_i)

$

You mention: "... This leads to challenges such as possible discontinuities in the optimal allocation and the lack of structure typically exploited in classical settings ... "

• Indeed, in general for structured problems, the optimal allocation is not necessarily unique as is the case of Linear bandits, but ideas like C-tracking can still work as observed in [W3]. Is the set of optimal allocations in your problem not unique? what properties does this set have?

• As for the continuity of the set of optimal allocation with respect to $\mu$, one typically uses the notion of hemi-continuity as done in [20]. Could you clarify what are the continuity properties of the set of optimal allocations?

[W3] Y. Jedra, A. Proutiere, Optimal best-arm identification in Linear Bandits, NeurIPS 2020.

Regarding the weakness concerning analysis and design. Track-and-stop as a design principle is well studied and established. In other words, I am wondering about what novelty you provide in terms of design principles. You said that your main technical novelty is in the upper bound analysis. It would be useful to clarify what are the key challenges that differentiate your track-and-stop algorithm either from a design perspective or from analysis perspective. I would appreciate if you could point me to specific part of your proofs that you think are novel.

Regarding the stopping rule. Note that confidence interval with $\log(\log(t))$ dependence yields much faster stopping in practice. If one assumes that the distribution is gaussian, why is it that your setting does not allow using such concentration bounds?

My concern about the stopping rule when I mentioned the work [W2] has to do with the novelty of your stopping rule. [W2] builds on using upper and lower confidence bounds. Your stopping rule seem to use a similar design mechanism. In best arm identification, and generally speaking in hypothesis testing one often relies on a generalized likelihood ratio test for tighter bounds. Can you elaborate on how your stopping rule is related to such tests?

Minor comments:

In Line 4.2.9, I believe it should be Proof of Theorem 2 in the title of the subsection.