Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms

We sincerely appreciate the reviewer's thorough and insightful review and apologize for any statements that may have caused confusion.

Tractability of the algorithm

First, we note that our method is tractable in terms of the number of oracle calls. We do not specify algorithms (optimization oracles) for the quadratic and fractional quadratic objectives.

Computation Oracles

Please refer to the response to Reviewer 4oes (we note that $q\_{n}$ is defined in Line 317 (right)).

Space complexity

In every iteration of Alg. 1, we approximate our sampling policy using Alg. 2. The choice of $n_t = t^u$ is motivated by the convergence rate of the Frank-Wolfe method (Lemma F.4). Under certain assumptions, the Frank-Wolfe method exhibits a faster convergence rate [Garber & Hazan, 2015], and the cardinality of the support of $\pi_t$ can be significantly reduced. However, this typically requires the set $\mathcal{V}(\mathcal{X})$ to be strongly convex, and we are unaware of any arm-sets that satisfy this assumption.

Instance-Dependent Optimality

We agree that our method is asymptotically optimal. However, as we discussed in the introduction, our analysis is instance-dependent unlike existing methods in the continuous arm setting (such as MVR). Theorem 6.2 assumes knowledge of the unknown characteristic time, however, as we remarked after Prop 6.2, we provided a convergence analysis in the case when $\lambda\_{V} = 0$ in Prop D.2.

Recommendation Rule

We agree that our main result, Thm. 6.2, relies on assumption (7) regarding the recommendation rule, and we provide sufficient conditions for (7) only for the greedy recommendation rule. To improve clarity, in the introduction of the revised version of this paper, we will discuss this.

PAC with respect to the unconditional probability

As clarified in the paper, we consider the $\epsilon$-BAI problem under the Bayesian reward model setting. Proving that the method is $(\epsilon, \delta)$-PAC with respect to the unconditional probability $P$ is not a primary focus of this study. We believe there are several ways to theoretically validate a pure exploration algorithm. For instance, under a Bayesian setting, Russo 2016 also provided a similar analysis (asymptotic bound of the posterior error probability) to this study, but it is considered to be an important literature in this field.

Moreover, the core ideas of PMCA can be applied to existing algorithms (such as LεBAI (Jourdan & Degenne, 2022)), since they do not clarify the optimization method regarding the sampling distribution, and it would be possible to prove the extended algorithm is PAC.

Stopping Rule

For any explicitly computable upper bound $u\_t$ of the conditional probability of misidentification and $\delta \in (0, 1)$, we refer to the stopping rule by the stopping time defined as the minimum $t$ satisfying $u\_{t} \le \delta$. Assuming $\mathcal{X} \subset [0, 1]^d$, we make the statement of Lemma D.1 more explicit. Using notation of 2 of Lemma D.1, by the tail probability of chi squared distribution, we can take $h\_{t} = t^{-(1 + c)}$ and $|\mathcal{X}\_{h}|$ is given as $(\sqrt{d}h^{-1})^d$. Then, $u\_t(\delta'\_t, h\_t, \mathcal{X}\_{h\_t})$ gives an explicit upper bound. As we discussed in Line 240, $\sup\_{\xi \in \mathcal{X}} P\_t(\cdots)$ can be solved using the fractional quadratic objective.

Lemma 4.1

Both sides of Lemma 4.1 are defined asymptotically, therefore they do not depend on $t$. In addition, unlike (Russo 2016), both sides depend on asymptotic behavior of general recommendation rule $\zeta\_t$ and (the mean of) general sampling rule $\pi\_{t}$ rather than the optimal one (our analysis can also be regarded as a generalization of Eq. (1) of Glynn & Juneja (2004)). In Eq. (15) in Appendix, we use the standard fact on the normal distribution that unconditionally holds for the signature of $\epsilon + \mu\_t(\zeta\_t) - \mu\_t(\xi\_t)$. Moreover, in the proof (around Line 715), we assume a sub-sequence of $(V(\overline{\pi}\_{t}))\_{t\ge 1}$ converges, and we do not assume $V(\overline{\pi}\_{t})$ converges in the statement of Lemma 4.1. We hope this resolves your concern and if you have further questions, we would be happy to answer them.

Experiments

We appreciate your suggestions. We refer to the response to Reviewer huXi for CPU time of each method. We have conducted an ablation study of the parameter $\lambda\_{V}$ for the second ($a, b=0.2, 0.6$) problem instance in Fig 2, where MVR is sub-optimal. The table shows the mean (standard deviation) of our evaluation metric. We found that while the original choice ($\lambda\_{V} = 0$) outperforms the baselines, the optimal choice of $\lambda\_{V}$ is around $1e^{-1}$.

References

• Garber & Hazan, Faster rates for the Frank-Wolfe method over strongly-convex sets, ICML 2015

We sincerely appreciate the reviewer's thorough and insightful review. We will revise our manuscript based on your suggestions.

Readability

We appreciate reviewer's suggestion. In a revision, we will improve the readability of the paper (e.g. by making detailed statements in Prop 6.5 concise and refer to the Appendix for a more precise statement).

Asymptotic optimality

Lemma 4.2 provides a non-asymptotic upper bound for the posterior probability of misidentification that asymptotically matches the actual conditional probability. However, a more refined analysis guaranteeing non-asymptotic optimality remains an important avenue for future research. We will discuss this limitation in the Conclusion section of the revised paper.

More discussion on the challenges of generalization from the finite-armed setting

While it would be difficult to prove that generalizing from the finite-armed setting is impossible for any existing algorithm, the non-smooth optimization objective over the space of probability measures is a fundamental problem that any asymptotically optimal algorithm must address. To the best of our knowledge, even in the finite-armed setting, the efficient solution of this problem has not been thoroughly discussed. We can also view our contribution as an efficient algorithm for the finite-armed setting, particularly when dealing with a large number of arms.

Computational Oracles

Quadratic Objective

For example if the arm set $\mathcal{X}$ is defined as an interval constraint $l \le q(x) \le u$ with a quadratic function $q$ (this includes the case of the unit sphere), the quadratic objective can be solved in polynomial time by the Lagrange relaxation (Park&Boyd, 2017). The relaxed problem is a semi-definite problem (convex problem). If we use an interior point method (barrier method), to obtain an $\epsilon'$-optimal solution, the outer loop needs $O(\log(1/\epsilon'))$ iterations and the convergence rate of the inner loop is linear convergence. Per iteration computational complexity is $O(d^4)$ with $O(d^2)$ space complexity (Boyd&Vandenberghe, 2004, Chapter 11.8.3).

In general, the problem can be NP-hard. We note that MVR (Vakili et al., 2021) has the same problem and similar to the MVR implementation (PosteriorStandardDeviation) in the BoTorch library, we use a non-linear solver (such as L-BFGS-B) with a randomly selected initial point in our experiment.

Quadratic Fractional Objective

Let $A(x)/B(x)$ be the objective we want to maximize over $x \in \mathcal{X}$. As we briefly discussed in Sec. 5.2, if we use the Dinkelbach's algorithm, we call the quadratic objective oracle once in each iteration of the Dinkelbach's algorithm. More precisely, if we define $q^{(n + 1)} = A(x^{(n)})/B(x^{(n)})$ and $x^{(n)} = argmax\_{x} A(x) - q\_{n}B(x)$, then $q\_{n}$ converges to the optimal value $q\_{\ast}$ and its convergence rate is superlinear (the error goes to zero faster than any geometric sequence) (Schaible, 1976). Then one can obtain a solution of the original problem by $argmax\_{x} A(x) - q^{\ast}B(x)$. Due to the superlinear convergence rate, we use a limited number of iterations (i.e., 30) in our experiments.

References

• Boyd & Vandenberghe, Convex Optimization, Cambridge University Press, 2004

We sincerely appreciate the reviewer's thorough and insightful review. We will revise our manuscript based on your suggestions.

Posterior probability of misidentification

As we briefly discussed in Line 133 (right), the posterior probability $P\_t(\zeta\_t \not \in \mathcal{X}^{\ast}(\epsilon))$ is known to the learner, i.e., it is a $\mathcal{F}\_{t}$-measurable variable because it is defined using the conditional probability $P\_t$. More concretely, we can rewrite $P\_t(\zeta\_t \not \in \mathcal{X}^{\ast}(\epsilon)) = P\_t(\zeta\_t \le \sup_{x}f(x) - \epsilon)$. We note that conditioned on $\mathcal{F}\_t$, the reward function $f$ is identified with $f\_{t}$. In addition, the distribution of $f\_{t}$ is known due to the Bayesian setting and we provide it explicitly in Line 152 (left). Therefore, we can essentially compute the posterior probability of misidentification. We hope this resolves your concern. We will clarify the statements in Line 133 in the revision of this paper.

Computational Complexity

Since in each round, we add $n\_{t}$ points to the support of the sampling distribution, the computational complexity of the reparametrization is given as $O(d^2 n_t)$, which is polynomial in $t$. We appreciate your suggestion and will add the discussion on this in Section 5.3.

Subgradient

$g\_t$ defined in Eq. (6) is a subgradient of the function defined in Eq. (4). We used a known fact that if the function $F$ is defined as the supremum of convex functions $(F\_{i})\_{i \in I}$, then a subgradient of $F$ is given as a gradient of $F\_{i^{\ast}}$, where $i^\ast$ attains the supremum (Hiriart-Urruty & Lemarechal 2004, Chapter D, Lemma 4.4.1). We appreciate the reviewer's suggestion and will briefly explain this in the main paper.

We sincerely appreciate the reviewer's thorough and insightful review. We will revise our manuscript based your on suggestions.

Instance-dependent optimality and recommendation rule

We agree that while an asymptotically optimal algorithm needs both optimal sampling and recommendation rules, we mainly focus on the optimization problem regarding the sampling rules, which we believe is the most challenging aspect in the continuous arm setting. More precisely, our main result, Theorem 6.2, relies on assumption (7) on the recommendation rule, and we show the greedy recommendation rule satisfies (7) under some assumptions. To improve clarity, in the introduction (or conclusion section) of the revised version of this paper, we will explicitly explain this more in detail.

Assumption 6.1 and the assumption for Proposition 6.4

Our method satisfies the condition on $\lambda_{min}(V_t)$ for Proposition 6.4 because we consider a mixture distribution of $(1-t^{-\alpha})\tilde{\pi}\_{t} + t^{-\alpha}\pi\_{exp}$ at Line 15 in Algorithm 1. Thus, we can focus on Assumption 6.1 and we believe that we already discussed the validity of the assumption in Sections 6.1 and 6.3. We will clarify this in the revision and appreciate the reviewer's suggestion.

Experiments

We sincerely appreciate reviewer's suggestion on the experiments. In the following table, we show cpu time for each algorithm for the left most instance in Figure 2. Regarding a method that discretizes the arm set, the efficiency of such a method can be arbitrary worse due to the discretization, however, we need different problem instances (higher dimensional problem instances) to demonstrate the inefficiency.

In the following table, the number represents time in seconds for running one experiment and shows the mean (std) over 10 repetitions. (w/ eval_time) represents the number includes cpu time for computing $p_t$ (the evaluation metric) and (w/o eval_time) represents the number excluding cpu time for $p_t$.

The table shows our method took about 1.5 seconds while MVR took 0.2 seconds. This is natural since the instance-independent baselines (Uniform and MVR) do not solve the optimization objective over the space of probability measures. The experimental results show our method runs in a reasonable time.

Practical applications

As you mentioned, recent papers consider an application of bandits to LLMs [Li, Y., 2025, Nguyen, Quang H., et al., 2024, Jinnai & Ariu, 2024]. For instance, Jinnai & Ariu applied the Correlated Sequential-Halving to the text generation tasks (such as machine translation, text summarization, and image captioning tasks), where the objective is to find a text sequence with the best utility efficiently. By regarding an embedded sequence as an arm, we can formulate it as a BAI problem with a linear reward model. Since the set of possible sequences is exponentially large, our algorithm has potential application to this problem.

More generally, we can extend any linear bandit algorithm to Bayesian optimization algorithms by random Fourier features (or quadrature Fourier features) [Mutný, M., & Krause, A. 2019]. The continuous arm setting naturally arises in the Bayesian optimization setting and has numerous applications including material design and hyper-parameter optimization. As we discussed in the conclusion section, it is an important future study of this paper to directly extend our result to the Bayesian optimization setting (without such a reduction).

References

• Jinnai, Y., & Ariu, K. (2024). Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decoding. In ACL (Findings).
• Li, Y. (2025). LLM Bandit: Cost-Efficient LLM Generation via Preference-Conditioned Dynamic Routing. arXiv preprint arXiv:2502.02743.
• Mutný, M., & Krause, A. (2019). Efficient high dimensional bayesian optimization with additivity and quadrature fourier features. Advances in Neural Information Processing Systems 31, 9005-9016.
• Nguyen, Quang H., et al. (2024). "MetaLLM: A High-performant and Cost-efficient Dynamic Framework for Wrapping LLMs." arXiv preprint arXiv:2407.10834 (2024).

Response to other comments

In Proposition 6.3, the term $\zeta^{\ast}$ was used without any definition.

We thank the reviewer for pointing out this. In Proposition 6.3, $\zeta^{\ast}$ is a typo and should be $\zeta_{\infty}$. We will correct this in the revision.