Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Authors: Sho Takemori
Yuhei Umeda
Aditya Gopalan
Venue: ICML 2025 poster (2025)
Keywords: pure exploration
linear bandits
continous arm set
Primary area: theory->online_learning_and_bandits
TL;DR: We propose a novel algorithm for a pure exploration problem with linear bandit feedback on a continuous arm set with an instance-dependent optimality.

Abstract: This paper studies a pure exploration problem with linear bandit feedback on continuous arm sets, aiming to identify an $\epsilon$-optimal arm with high probability. Previous approaches for continuous arm sets have employed instance-independent methods due to technical challenges such as the infinite dimensionality of the space of probability measures and the non-smoothness of the objective function. This paper proposes a novel, tractable algorithm that addresses these challenges by leveraging a reparametrization of the sampling distribution and projected subgradient descent. However, this approach introduces new challenges related to the projection and reconstruction of the distribution from the reparametrization. We address these by focusing on the connection to the approximate Carath\'eodory  problem. Compared to the original optimization problem on the infinite-dimensional space, our method is tractable, requiring only the solution of quadratic and fractional quadratic problems on the arm set. We establish an instance-dependent optimality for our method, and empirical results on synthetic data demonstrate its superiority over existing instance-independent baselines.

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Sho Takemori'
Yuhei Umeda'
Aditya Gopalan
Abstract
an e-optimal arm (ef. (Bubeck al., 2011, Theorem 1), Lemma 4.1, (Banerjee al., 2023, Theorem 2.2)). where <> O is given error tolerance. Furthermore, this paper considers a continuous arm set X' C R (a compact subset of IR:)) and aims to optimize sampling distributions to mini- mize the posterior probability of misidentification under a Bayesian reward model. Despite extensive existing research on BAI problems, as we detail below, the e-BAI problem on continuous arm sets is open problem.
This paper studies pure exploration problem with linear bandit feedback on continuous arm sets, aiming to identify an e-optimal arm with high probability. Previous approaches for continu- ous arm sets have employed eendeeeeenn methods due to technical challenges such as the infinite dimensionality of the space of probability measures and the non smoothness of the objective function. This paper proposes a novel, tractable algorithm that addresses these challenges by lever- aging a reparametrization of the sampling distribu- tion and projected subgradient descent. However, this approach introduces new challenges related to the projection and reconstruction of the distri- bution from the reparametrization. We address these by focusing the connection to the ap- proximate Carathéodory problem. Compared to the original optimization problem on the infinite- dimensional space, our method is tractable, requir- ing only the solution of quadratic and fractional quadratic problems on the arm set. We establish instance-dee -eeredeed optimality for our method, and empirical results on synthetic environments demonstrate its superiority over existing instance- independent baselines.
The pure exploration problem with linear bandit feedback in the finite-armed setting has been extensively studied, with instance-optimal algorithms proposed for the (c. PAC learning setting (Jourdan & Degenne, 2022), aiming to identify an e-optimal arm with probability least 1 8. These algorithms typically solve an optimization problem over the probability simplex AK-1 RK where K is the number of arms; for example, Lazy Track-and-Stop (Je- dra & Proutiere, 2020) employs the Frank-Wolfe algorithm. Naively applying these finite-armed algorithms to the con- tinuous arm setting via discretization of the arm set X is computationally intractable, as the number of discretization points K can grow exponentially with the dimension d.
Although most existing works for pure exploration problems focused on the finite-armed setting, there are few notable exceptions. Jedra & Proutiere (2020) studied a linear pure exploration problem with the fixed confidence setting and proposed an (order-wise) optimal algorithm when the arm set X' is the unit sphere (along with the case of the finite- armed setting). However, their analysis shows that a uni- form exploration is (order-wise) optimal sampling rule and such an exploration would not be optimal for general continuous arm sets. Bhat & Amballa (2022) also studied the (c, 8)-PAC learning problem with the linear bandit set- ting for general continuous arm sets. However, their method is also a uniform exploration and theoretical result (Bhat & Amballa, 2022, Theorem 4.4, Eq. (10)) shows an upper bound of the sample complexity involves the dimension d and rather than problem instance, i.e., their analysis is instance inneeeeeendeedd Therefore, even in the case of linear bandits, to the best of our knowledge, is an open problem to develop trackable algorithm for a pure exploration prob- lem with linear bandit feedback with an instance-dependent optimality.
1. Introduction
The stochastic linear bandit problem (Dani et al., 2008; Jedra & Proutiere, 2020) is a well-studied online decision- making problem that has been widely applied to real-world problems (Lattimore & Szepesvári, 2020). While most re- search focuses on minimizing cumulative regret, this paper considers a pure exploration problem, specifically the e-BAI (best arm identification) problem. Unlike regret-minimizing algorithms, optimal pure exploration algorithms achieve an exponentially decaying probability of misidentifying
'Fujitsu Limited, Kawasaki, Japan IIndia Institute of Sci- ence, Bengaluru 560012, India. Correspondence to: Sho Takemori <takemori.shoo fujitsu.com>.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
As we detail in Section 4, developing a tractable e-BAI algorithm is challenging because finding an optimal sam- pling strategy requires optimization over the space P(x) of probability measures on X'. This optimization problem (defined as Eq. (4)) is highly non-trivial to solve due to (i) the onfiniteddimensionaliiyy of P(Y) when the arm set X continuous, and (ii) the non-smoothness of the objective function (4) due to the inner supremum. Furthermore, ban- dit feedback obscures the true objective function. This paper addresses these challenges by reparameterizing + ((T) for E (( where (==) = E [xx""] E IRddd is the covariance matrix, and adapting a projected subgradient descent (PSGD) method (cf. (Bubeck, 2015, Chapter 3.1)). This approach updates symmetric matrix V2 E RRdxd such that V = (TT),, where ne is an arm's 's sampling distribution at round f. However, introduces new challenges: (iii) projecting onto the space V(z) := (V(T) x E P(X)), and (iv) reconstructing a distribution ne from a given ma- trix V/2 We address these by leveraging connection to the approximate Carathéodory problem (Combettes & Pokutta, 2023), which seeks a convex combination approximating a given point in a convex set. Analogously to the approximate Carathéodory problem, we resolve (iii) and (iv) using an adapted Frank-War Wolfe method (Algorithm 2).
algorithm termed PMCA in Section 5.1; a method for Posterior error Minimization for a general Continuous Arm set based on the PSGD (projected subgradient descent method) that has an interesting connection to the Approximate Carathéodory problem. More pre- cisely, our algorithm assumes computation oracles for quadratic and fractional quadratic objectives on the arm set N. which can be implemented by standard optimization library unlike the original optimization problem P(X).
3.
An instance-dependent (or asymptotic) optimality of the sampling strategy. We show that our pro- posed method is asymptotically optimal (Theorem 6.2), i.e., for any given recommendation rule (4))21, the sampling rule (Tz) of PMCA minimizes the pos- terior probability asymptotically, i.e., it minimizes lim; / log (C & X (e)).
4. Experiments. To demonstrate the effectiveness of our method, in simple, synthetic environments, we empirically compare our method with baselines (in- cluding MVR ( (Vakili et al., 2021), which is instance- independent optimal) and the empirical results demon- strate its superiority over existing instance- indeeeeddnne baselines (Section 7).
To summarize our contributions, we briefly describe the problem setting (a more formal description is given in Sec- tion 3). We assume a Bayesian linear reward model, i.c., ., for a selected arm Ie E X. learner
As we shall clarify in Section 6, we provide main the- oretical result (Theorem 6.2) for a given recommendation rule (G))22 satisfying Eq. (7). Our analysis implies that a pair ((TT)) (G))21) is (asymptotically) mustance-optima if the recommendation rule (4))221 is asymptotically opti- mal (we refer to Section 4.3 for more details for choices of a recommendation rule). In this work, assuming a recommen- dation rule (5))221 is given, we focus on the optimization of sampling rule (TT))21 which we believe is the most chal- lenging aspect in the continuous arm setting. Nevertheless, we emphasize that our analysis is instance-dependen unlike existing pure exploration methods for the continuous arm setting (such as MVR Vakili et al. (2021)).
for each = ........ observes a noisy reward y/ = f(x) + we, where W/ is a zero- mean noise, f(x) is an unknown random function given as f(x)= = 05 xz and of is an unknown random vector sampled from prior distribution .' (O,,, Σa) with 0g E Rd Eo E dddd when the round starts. The learner samples an arm using a distribution n. E P(x)), where T. is a distribution computed using observations up to round t - 1, and we call (TT)221 sampling rule. For each round 2 1. after observ- ing Mr. learner recommends an arm G. E X' that estimates an c-optimal arm. The objective of the learner to minimize the posterior probability Pi & X" (c)) of misidentifica- tion, where X² (e) is the set of e-optimal arms given as {x E X f(x)= > suPEEx fzx - ) and P, denotes the posterior probability given observations up to round t. For conciseness, we provide informal theoretical statements of our thcoretical results and refer Lemma 1 and Theo- rem 6.2 for more formal statements (All the omitted proofs can be found in Appendix F).
2. Related Work
This paper studies the c-BAl problem with linear bandit feed- back on a continuous arm set X' C Ed and our objective is to minimize the posterior probability Pt E X" (c)) of misidentification under a Bayesian linear reward model. As we mentioned in the introduction, Bhat & Amballa (2022) studied a (e, 6)- learning problem with linear bandit feedback continuous arm set, where the objective is to minimize the stopping time of an algorithm that returns an e-optimal arm with confidence 1 - 5. The (c, 8) learning problem with linear bandit feedback has been well- studied especially for the finite-armed setting (Jourdan & Degenne, 2022; Jedra & Proutiere, 2020; Soare et al., 2014;
1. Formalization of the objective. To formalize our op- timization objective regarding sampling rules, we show that lim,- log Pe. & X (c)) can be written function of ग.C lim 3. and &oo = lim Go. where T. : E nT (Lemma 4.1).
2. A trackable algorithm. We propose a novel, tractable
2

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Xu et al., 2018; Fiez al., 2019; Degenne al., 2019; Mo- hammadi Zaki & Gopalan, 2022). Specifically, Jourdan & Degenne (2022) studied the transductive linear bandits (a more general setting than linear bandits), proposed an 0)- PAC learning algorithm, and discussed asymptotic optimal- ity as 8 + 0 (i.e., a limit to the case of 100% confidence). Although our objective is to minimize Pr & X (e)), our theoretical analysis parallel to that of the (e, learn- ing setting, i.e., we discuss asymptotic optimality of our algorithm as + oc (Lemma 4.1, Theorem 6.2) and dis- cuss stopping rule that ensures the posterior probability of misidentification is less than ò (Section 3, Lemma 4.2). We also note that an asymptotic analysis of the posterior prob- ability of misidentification standard in the finite-armed setting (Li et al., 2024; Russo, 2016).
positive constant À O, {wi) is an i.i.d sequence of noise random variable with wi NN( A), which is inde- pendent of f. We denote by F, the o-algebra generated by 21, V1. Vi.............................. E.., ./t The posterior reward function fo condi- tioned on F, is given as ft(xx) = 0f Iz where 0g follows normal distribution 0f ~ (Nu,, E,)),,)) ), and E, and Me are given as E; = Plk + Σe=1 IzJ, M4 := E,' Σx=1 Vo (this is a special case of (Kanagawa et al., 2018, Theorem 3.1)). We denote by Pa the posterior probability measure conditioned on Ft.
Recommendation Rule and Objective of the Learner. In each round t, after observing yt. the learner recommends an arm G. E X'' that estimates Çe an e-optimal arm at time step t. More formally, Çe is a Fe-measurable ran- dom variable. Here, the set of c-optimal arms X (c) is defined as {x E X [(x) > supsex (E) - -e. For example, the greedy recommendation rule is defined by G argmax He (x)), where fe is the posterior mean of f. This recommendation rule is used for an existing method for simple regret minimization (Vakili et al., 2021).
Despite extensive existing research for pure exploration problems with linear bandit feedback, most papers focus on the case of finite-armed settings due to the difficulties men- tioned in the introduction. To the best of our knowledge, it is an open problem to develop a trackable algorithm for a pure exploration problem on a general continuous arm set with an instance-dependent optimality. Other than linear bandit literature, Vakili et al. (2021) proposed an optimal algorithm pure exploration (simple regret minimization) called MVR (maximum variance reduction) for Gaussian process bandits (or Bayesian optimization). However, their analysis is also an instance- inneeeeeendee analysis, and MVR is non-adaptive and selects an arm that minimizes the posterior variance ore Shekhar& & Javidi (2022) provided instance- dependent analysis of kernelized bandits, however, they focused cumulative regret minimization. We discuss more related works in Appendix C.
The objective of the learner is to minimize the posterior probability of misidentification Po(Se & X (e)), which de- pends on the sampling rule (x1)221 and recommendation rule (St)121. In this paper, for any given recommenda- tion rule (G))211 we aim to seek an optimal sampling rule (Te 211) As we discuss in Section 4, the optimality involves an optimization problem on the space of probability mea- sures P(X), which is a highly non-trivial problem due to the infinite dimensionality of P(2)) and non-smoothness of the objective (4). Moreover, we discuss choices of recom- mendation rule (51)22 in Section 4.3.
Stopping Rule. In the (c,5)-PAC learning problem, an algorithm stops if it ensures the error probability is less than a given threshold 8. In our problem setting (i.e., the e- e-BAl problem under a Bayesian reward model), assum- ing observations up to round t, the posterior probability (G & X (e)) of misidentification is known to the learner, i.c., more formally it is a F.-meauurable random variable. Therefore, instead of conducting the GLLR (generalized likeliield ratio) test (Jedra & Proutiere, 2020), it is sufficient to compute PG & X (4)). However, an ac- tual computation of Pt(Ge & X (e)) is non-trivial due to the continuous arm set setting. Hence, we provide a com- putable upper bound of Pe(Se & X (e)) that asymptotically matches PC & X (c) (Lemma 4.2). More precisely, for any explicitly computable upper bound u, of the con- ditional probability of misidentification and 8 E (0. 1), we refer to the stopping rule by the stopping time defined as the minimum t satisfying 4 < 8. In the experiment sec- tion (Section 7), we compare algorithms in terms of this computable upper bound.
3. Problem Formulation
Bayesian Linear Reward Model. We assume that X' is a compact subset of dRd and consider Bayesian linear re- ward function f X - R. We suppose T > O satisfies supzex ||=||² < k. More formally, the random linear func- tion f is defined as fx) = 05 vr, where a- b is the standard Euclidean inner product, and of is a random vector that fol- lows a prior distribution 0f ~ . (i0, Eo), where Gu E Idd and Eo E Raxd is a positive definite symmetric matrix. By applying an affine transformation of X, without loss of generality, we may assume 0n 022 and Eg = La. where 0, and La are the zero vector and identity matrix of size d, respectively. In the rest of the paper, we assume that the prior distribution of 0f is given to be (O,,,, la).
Sampling Rule. For each time step f = 1.2..... learner selects an arm x, E X, where 24 is sampled from a probabil- ity distribution म. = (= 1/, 22, 1/2 1/2..... 1t 91-1) E P P(2). Then, after committing an action v, the learner ob- serves random reward y;- = f(x)) + wi and where for
Assumptions and Notations. For a symmetric matrix V
3

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Rdxd, denote V 0 if V is positive definite. For symmetric matrix V, denote by Amin (V) the minimum eigenvalue of V, and define | as v Va for I I if V For matrix V. | denotes the Frobenius norm. We denote by ((x)) the space of Borel probability measures on X, which is a general class of probability measures. For E (())), we define (z² = Be> [xr The space ((X') is defined as (V(T): i E P- For a E X, 8(a) is the Dirac delta distribution putting all mass on {a}. We refer to Appendix for notation table.
10a
decay rate r(r(())
10
Ours
MVR
10-2
3
parameter 0 of arm
Figure I. A numerical example of (T(V(T). for X c I2 and f(x) n² with fixed reward vector μe" IR... An am in N' is parametrized by z(0) = (cos(0), sin(()) with 0 S 0 S æ. The z-axis represents the parameter 0 and the y- axis represents r(z(0)) = (T(V(T),x(0)) (0););;<< Soc, " where "² is a fixed reward vector in RR, Soe argmax,ex x / 2. = 10-2, We compare r(x(0)) with sampling rule obtained by our algorithm and that of MVR (Vakili al., 2021).
4. Posterior Probability of Misidentification
4.1. Asymptotic Bounds of the Posterior Probability
For a fixed recommendation rule (G))211 this section in- troduces results on (asymptotic) lower and upper bounds of the posterior probability of misidentification in terms of the sampling rule (TT))21 in Lemma 4.1. To do so, we introduce following notations. Here, for positive-definite matrix V E _axd S. E X. and function μ X I,, we define
its decay rate is given as lim (T (V(r)) Coo, f)) assuming the limit exists. We note that similar results are well-known in the finite-armed setting (Li et al., 2024, The- orem 2.1), (Russo, 2016, Theorem 1). Lemma 4.1 general- izes these results to general continuous arm sets and general recommendation rules (Gt)21. In the proof, since we can- not compute Pi(ce & X (c)) directly, we rewrite using supeex Pc(S(G) S (() -),, and we further rewrite to value of the function I"
E11 T(V.& = (E+ u(S) n(E))2²
Then, for a probability distribution क E P(X), < X, p. :
R. we define
('(((T): = sup (Vp) EEX
(1)
Optimization Objective. Lemma 4.1 indicates that if (#z) is asymptotically optimal sampling rule and m. converges Too E P(X), then To should be solution of the following optimization problem:
The following lemma provides a lower bound of the poste- rior probability of misidentification in terms of the sampling rule (Te)<2 (and recommendation rule 11)
Lemma 4.1 (Asymptotic posterior probability of misidenti- fication). Let (Tz) be a sampling rule and (G))21 be recommendation rule with lime- St Soo E X (c), a.s., that is, Soo is the a.s. limit of the random variables (St) Suppose limy-+oc [e(x)) = fx) for any I E X a.s. and inf,21 Amin (V (v(z)) )) > O, where ne =
(fo == inf (V =EP(X)
(4)
1K EllV
inf sup TEP(X) (c+ f(Sx)) f(())²
Te. Then,
The optimization problem (4) is challenging to solve since the space P(X') is infinite dimensional and [* I'V('""V (V(T): Soo f) is non-smooth due to the supremum for & E X. In Figure 1, we show numerical examples of (T(V(T), Coe f)) for two sampling rules (ours and MVR). Using the notation in the figure caption, see that with our sampling rule, the value of infçex r()) = (supeex ((V(T), ( is smaller than that of MVR.
we have the asymptotic bound:
lim inf log P. (G X (c)) t0
1
2 2 1000
lim (V 1
(2)
Moreover, we have:
limsup - log Pt (G. $ X' (E))
4.2. Non-Asymptotic Bound and Stopping Rule
As we discussed in Section 3, Pr(ge & X (c)) is mathemati- cally computable using observations up to round é, however, an actual computation is non-trivial especially when the arm set is continuous. The following lemma provides a computable upper bound. For conciseness, we provide a
lim inf (V -)) to000
(3)
Intuitively, this lemma implies that the posterior probability Pe (Ce & x (4)) exponentially decays as t increases, and

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
brief statement here, and detailed statement in Appendix (Lemma D.1).
that with an optimal recommendation rule (G)) Soe should minimize (Go under the constraint (oo E X (c). We call such recommendation rule asymptotically opti- mal. If an estimation of lim I (V.TT G, ff (and that of the constraint Ç E (c)) is available for any Ç. one can implement such a recommendation rule by applying any black-box optimization algorithm (such as Bayesian optimization algorithms (Frazier, 2018)). In practice, we can use I (V(((T)): (,44) an estimation of I (Vaz: and {< E X ((((() 2 supzEx (x(x)) e) as an estima- tion of the constraint {C : S. X (t)). We shall discuss algorithms for computing (V:(; (.)) in Section 5.2. For a positive-definite matrix V E Rdxd and a function μ X - IR, we note that argminçex (V; is equiv- alent to the furthest answer introduced in the finite-armed setting (Jourdan & Degenne, 2022) and they assume a com- putation oracle for the furthest answer. similarly, this paper assumes recommendation rule is given in our theoretical analysis provided in Section 6.
Lemma 4.2 (A computable upper bound of the posterior probability). Suppose that the assumptions in Lemma 4.1 hold. For any c. > O and for each L. 2 1, there exist by 2 0 with by O(poly(t)) and Et 2 with 1om = e such that
PalCe & X (t)) S az + be sup PG( S (() - et),
SEX
where = -epp(-t+o)) Moreover, we have
1
lim sup- log u S 255222200 1-300 t-000
lim inf (T (V f)) '))",
where == + by supeex P.(((G) S f(E) -e).
We note that inequalities (2), (3) and Lemma 4.2 imply that 7 log ue asymptotically matches & log P: (Se & X (e)) if V (Ft) converges, which is the case for our method proposed in Section 5.1. In Lemma D.1, the term by given as (an upper bound) the cardinality of a discretization of X, which can be easily computed since X' c Id is compact. Moreover, (the proof of) Lemma D.I implies that
5. A Tractable Algorithm for Minimizing the Error Probability
5.1. Proposed Method
( log (logt) t )
log u 50
+ sup +sup <ext
log Pc(f(C)) & f(5) c),
In Section 3, we formalized the optimization objective Eq. (4) for an optimal sampling rule. In this section, we pro- vide a novel tractable algorithm termed PMCA based on the projected subgradient descent method and discuss its connection to the approximate Carathéodory problem (Com- bettes & Pokutta, 2023).
t
and the latter term is dominant. By definition and noting the monotonicity of the cumulative distribution function of the standard normal distribution, we can rewrite the above term as follows:
Projected Subgradient Based Method. The optimization objective (4) is a minimization problem over the space P(X) of probability measures. One can hope to solve such an op- timization problem by Wasserstein gradient flow (Salim et al., 2020). However, an actual implementation of such algorithms is highly non-trivial. More specifically, in the framework of (Salim et al., 2020), an explicit calculation of the proximity operator is unclear for our setting. In this paper, focusing on the simple fact that our objective (4) is a function of a matrix V(T),, we optimize Eq. (4) over V(X) by the reparametrization π + V(T)., where V(X) = {V(x) : x E P(X)). Moreover, to stabilize the optimization process, for any xv 2 O. for Ç E X, con- sider the regularized objective infrep(x) I' (V(()))) where
sup Pi(f(s)) Ex) SEX
(- inf EEX
c + mo(Ge) - me(()
+
I1Ce - -Ils,,-
where & is the cumulative distribution function of the stan- dard normal distribution. Therefore, we see that we can compute this term by optimizing a fractional quadratic ob- jective on X, which we detail in Section 5.2.
4.3. Choices of Recommendation Rules
A simple example of a recommendation rule is given as the maximizer of the posterior mean, i.e., &e = argmax,ex (1) We call this recommendation rule the greedy recommendation rule. Existing pure exploration methods adopt this recommendation rule (e.g., MVR (Vakili et al., 2021)), and we use it in our experimental benchmarks (Section 7)-
+vIIVE
(5)
We prove that the function (=: is a convex function on ((X) (Lemma F.2). Consequently, we design our algo- rithm based on the PSGD (projected subgradient descent method) (cf. (Bubeck, 2015)). For conciseness, we first provide a slightly informal procedure of our method and a difficulty in applying the PSGD. Since the true objective
Next, we assume that (oo) as t + do (as we discuss in Section 6, our sampling rule satisfies this property). Lemma 4.1 implies
converges to
5

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
function is unknown, for each round I, we compute sub- gradient It of estimation of I" (::C. f) and compute approximate projection II of W++1 Vi- Ttc to the space V( where V E (2)) is parameter to be updated by the PSGD based method, G > 0 is a normalizing factor of the subgradient 9t. and 77 is step size.
Algorithm 1 PMCA: a tractable algorithm for error proba- bility minimization
I: Input: recommendation rule (5i)e21. base exploration distribution Texp E P(2), step sizes for the PSGD (ne)21, normalizing factors (ct)c21, decay rate for the mixture coefficient
0, step sizes for projection
(nt),. regularizer Xv 2 0,
The re- parametrization and PSGD address challenges of the origi- nal optimization objective (4), i.e., the infinite dimension- ality of (()) and the non-smoothness of the objective.
Projection and Distributtion-Recosstuucch
Initialize: को Texp: Vi V(
3: for t 1.2...... do
4: Play 2, n7 and observe a noisy reward ye:
5: // Reparametrization x; + Vi.
However, this approaches introduces new challenges re- lated to the projection onto ((X) and reconstruction of
6:
V. = (1 -1- -- +///+1=90 (TTxp))
7: Computation of subgradient gt-
the sampling distribution from the reparametrization. Not- } is dense
&, = argmax r(V,, C: Si Mt).
ing that the convex closure of {ax=
Vt == (Vi) (4: Ec).
in (xx),, if W E V(2), then the problem of finding
10:
Define ge by Eq. (6).
E P(2)) such that V(T) is close to W is equivalent
11:
I/ Update in the matrix space.
to the approximate Carathéodory problem (Combettes & Pokutta, 2023), i.e., a problem to seek a convex combina-
12:
We+1 = V 7c
13:
// Computation of an approx. projection and
tion close to a given point in a convex set. Therefore, simi- lar to the approximate Carathéodory problem, we compute an approximate projection by the Frank-Wolft algorithm detailed in Algorithm 2. For each iteration and matrix W' E TR Rddxd Algorithm 2 solves linear optimization prob- lem aryma Tr W'X X on ((Y). which is equivalent the quadratic optimization objective argmaxzex* x: W'x on X. This algorithm solves the aforementioned two chal- si-
distribution-reconsttucciii
14: # f- Algorithm with W = Wi41, = ne, [0] mo
15: M++1 = ( 1 Texps V411
V ((T+11).
16: end for
lenges (i.e., projection and multancously, i.c., it returns distribution ((*) such that V(T(")) is an approximate projection of an input W onto (() (Lemma F.4).
Algorithm 2 Approximate Projection by the Wolle
Algorithm
Input: W E Bdxd n 2 1, = 7,(0) E P(()),
for 1, 2, ...., 12 do
f 1) = ((7(1-1))
PMCA. We display pseudo code in Algorithm 1 of our proposed method termed PMCA (a method for posterior error Probability Minimization for Continuous Arm sets). Each round f, we compute a subgradient 9i of the function V + I ((1 ((-- -av + + (Texp()T)pi)))))) Sr, Rt), where a > 0 is a parameter of the algorithm and we consider a base exploration distribution Texp E P(2)) with V V(Texx)) > to bound the subgradient. With notations defined in the pseudo-code, a subgradient Sr
0: argmax x (W -
( (1 76 7) (1-1) 1 770(a))
end for Output (n)
objectives on X.
can be computed as follows:
Quadratic Objective. For any symmetric matrix V Raxd (which is not necessarily definite), we assume that an argmax oracle (x) for the quadratic ob- jective I + x VV, i.e., (V; returns a point in argmax zEx x. Vx. Such a computation oracle is assumed in existing work. For instance, Vakili et al. (2021) assumes an argmax oracle for the objective x - x" x ax, which is not concave. If X' is defined as linear and quadratic con- straints, such an optimization problem is called non-convex quadratic programming. Some problems are known to be solvable in polynomial time, while others are NP-hard (Park & Boyd, 2017).
9: : = (1 - (1-1 - + p(())) - (((()) -2 1.
+ 21v (I
(6)
We denote by V. E ((²' the parameter updated by PMCA. As we explained above, we compute an approximate projec- tion (( ) of W++1= := V.-- CeC. to (xX) by applying Algorithm 2. Then, we define a sampling rule by the mixture distribution _z-1 == (1 (t + 1) - + (t+ 1) Texp-
5.2. Computation Oracles
For later analysis of the proposed method, we introduce computational oracles for quadratic and quadratic fractional
For example if the arm set X is defined as an interval con- straint 1 S ((x) S u with a quadratic function g (this
6

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
includes the case of the unit sphere), the quadratic objec- tive can be solved in polynomial time by the Lagrange relaxation (Park& & Boyd, 2017). The relaxed problem is semi-de semi-definite problem (convex problem). If we use an inte- rior point method (barrier method), to obtain an e'-optimal solution, the outer loop needs (log((//e)) iterations and the convergence rate of the inner loop is linear convergence. Per iteration computational complexity is (ad*) with (dP) space complexity (Boyd & Vandenberghe, 2004, Chapter 11.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 (PosteriorStandrddDiiii ation) in the BoTorch library (Balandat et al., 2020), we use a non-linear solver (such as L--FGG-B) with a randomly selected initial point in our experiment.
6. Instance-Dependent (or Asymptotie) Optimality of the Proposed Method
This section provides theoretical analysis of the proposed method (Algorithm 1). In Section 6.1, we introduce our main theorem (Theorem 6.2) that assures the asymptotic optimality of the proposed method. We derive the main theorem by Lemma 4.1 and convergence analysis of the algorithm, which we introduce in Section 6.2. Moreover, we provide sufficient conditions for satisfying non-trivial assumption considered in the main results in Section 6.3.
6.1. Main Result
We make the following assumptions of the algorithm.
Assumption 6.1. We assume that we have access to compu- tational oracles Oo OOF for quadratic and quadratic frac- tional objectives on X' discussed in Section 5.2. Moreover, we assume that the following convergence rate of the recom- mendation rule Soo lim, Çt, a.s.: for any 5 E (0, 1), there exists (x) > 0 and constant >> 0, such that the following inequality holds for any t 2 1 with probability at least - 5:
Quadratic Fractional Objective. Next, for V1, V22 E Rd with 1/2 > 0, we introduce computation ora- cle Oqr (V1, 22) for quadratic fractional objectives. We assume that OOF (V1, 2); returns a point in argmax, (I [[z)/(zz V22)). This is known as frac- tional programming, and it is well-studied (Dinkelbach, 1967; Shen & Yu, 2018; Schaible, 1976). For in- stance, Dinkelbach's algorithm iteratively solves xx(*) argmax,5xx A(x) B(),, where A(x) x Víx and B(x)= = x V22 are the numerator and denomina- tor of the fractional objective, respectively and go+1 = B(z=")) It is proved that In converges to an optimal value q² and the convergence rate is superlinear (the error goes to zero faster than any geometric sequence) (Schaible, 1976). Then, one obtain a solution of the original problem by argmax A(z) q- B(z). Due to the superlinear convergence rate, we use limited number of iterations in our experiments.
1150 - Sell S cx. (x)
We also assume (TTex)) > 0 and the objective Eq. (5) is minimized at V E V((2) with V > 0. For inputs of Algorithm 1, we assume that 0 < a < v, take ne so that - (m; + -2)-1 < 1 (e.g., n4 2 ts with 8 > 1). We take an input of Algorithm 2 as 74- 2/ + 1).
Here, the most non-trivial assumption is that for the con- vergence rate of the recommendation rule Eq. (7). We note that because G. depends on the observation history (I1,81),.., (z ye). v can depend on other parameters of the algorithm. In Section 6.3, we provide examples sat- isfying the assumption Eq. (7) in the case when & argmax pr. Under these assumptions, the main result of this paper is given as follows.
5.3. Tractability of the Proposed Method
We discuss the tractability of PMCA (or computational complexity in terms of the number of oracle calls). In each round 1, PMCA solves the quadratic fractional ob- jective & = argmaxçexx I'(V,, Çt, (4e) at line 1. This line calls OQF once, where OOF the computation oracle for quadratic fractional objectives discussed in Section 5.2. At line 1, PMCA computes an approximate projection by call- ing Algorithm 2 and it calls the computation oracle Oq for quadratic objectives for n4 times. In the theoretical analysis in Section 6, we assume that Eee n, converges. For instance, any u. > 1, 74 = t" satisfies this condition. Thus, with this choice of nt, for each round I, the computation oracle Oq is called for O(t") times. For each round 2 1, store the support of the discrete probability measure 7, computed by Algorithm 2. Therefore, the space complexity up to round t is given as Old² + - n.).
Theorem 6.2 (Instance- Dependent Optimality). Suppose
Assumption 6.1 hold, and let (Te)22 be the sampling rule of Algorithm 1, and (Gi):2 be recommendation rule with Soo lim Se a.s. Furthermore, we assume that 0 < a < min(v. 5)) and take Ny = t 2n 1/2 C = 1, = 0. Then, the following holds:
lim 1-20
7
log Pr(ce $ X" (4))
(T:
(8)
This theorem implies that the decay rate of the error prob- ability of our sampling rule is given as (2 (fxc))) and Lemma 4.1 1 and (4) imply that it is equal to the optimal rate.
7

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
6.2. Convergence Analysis
p E Rd with || + O. If for any xo E X there ex- ists neighborhood Mz C TRd of zo and an analytic function Onn Uma + R such that X n Uzo is given as {ir E Uzo (2)(z) (z) 0}. V (z)ll is bounded on Uzy and the minimal eigenvalue of the Hessian of Ozo at xo is larger than a positive constant c. >> 0 independent of zo. then X satisfies the condition (9) with xx- = 2.
Theorem 6.2 can be proved by Lemma 4.1 and the results on the convergence analysis introduced below. Since we con- sider Gaussian posterior distributions, Lemma 4.1 requires two conditions, i.e., lim;-so (z) f(x) and v*++) con- verges to an optimal matrix of our objective (4). The former condition regarding H4 is a weak requirement and satisfied by any sampling policy with lim inf Amio (V (TTe) > O. The latter condition is more subtle and to satisfy the condi- tion, we need to solve the optimization problem (5). There- fore, we can deduce Theorem 6.2 by the following proposi- tion:
We note that an existing work also assumed arm sets with positive curvature (Banerjee et al., 2023, Definition 2.1).
7. Experiments
Proposition 6.3. Suppose the same assumptions as in The- orem 6.2 hold. For the sampling rule (Tz)(21 of PMCA, we have the following:
We coduct experiments in simple synthetic environments for the case X' C R², and empirically demonstrate that our proposed method outperforms existing pure exploration algorithms for continuous arm sets.
lim 5500
f)
Motivation. Jedra & Proutiere (2020) proposed a pure exploration algorithm in the case when the arm set X' is the unit sphere, and they showed that an optimal sampling policy is the round-robin manner using the orthonormal basis. Due to the symmetry of the arm set (unit sphere), this uniform exploration distribution is in fact optimal; however, if the arm set is a more general set, then this distribution may not be optimal. Therefore, we compare our algorithm with existing methods in several (synthetic) problem instances with X c R
In Proposition 6.3, we assume the step sizes 'e is given as t- 122-11/2 We shall show that a converge result can be proved with more general (standard) choices of step sizes in Proposition D.3.
6.3. Sufficient Condition for the Assumption Eq. (7)
In subsection, we provide examples of X' satisfying the as- sumption Eq. (7) in the case of the greedy recommendation rule G = argmax jt-- First, we introduce the following sufficient condition for Eq. (7).
Setup of the experiments. In this simple setting, X' is defined as a subset {(cos(O), sin())) : 0 E [0,, 01]} of the unit circle in R?, and f(x) = (cos(O)), sinn())) x, A = 10- c = 10-2 Here, for simplicity, we consider a deterministic function f and we understand that f is sam- pled before the round starts. Specifically, in this section, we consider the case when 0, = am, 0o 0, 01 bu. We have conducted experiments for = 0.0, 0.2, .......................... and b = 0.0, 0.2. 1.8 with a < b. In this section, we only show the case when a = 0.2, b = 0.4, 0.6, 0.8, 1.0. We refer to Appendix G for further experimental results.
Proposition 6.4 (Sufficient Condition for Eq. (7)). We as- sume that any vector μ E IRd with μ + O argmax fe- is singleton (an optimal arm is unique) and denote S argmax ft xx. We further assume that for any with μ + O there exist constants 6x K.X > 0 such that the following inequality holds:
||00 - -|-1" S cx Iu S7 - -/
(9)
Let Se = argmax Me the greedy recommendation rule and (#z)121 be a sampling rule with Amiin (V:) 2 t Then, the inequality (7) holds with v= 2xx
Evaluation metric. For all Sampling rules, we use the same recommendation rule defined as G argmax (x)). For sampling rule (mz)z21, we let Pt == supeex P((f(()) S f(E) - e) and use pt as an eval- uation metric (the lower is the better). By Lemma 4.2, as- suming 4 R3 c, this corresponds to the computational upper bound of Pt(Ge & X (e)) since a and by are independent of sampling rules.
Since the condition Aminn()) t- holds for the sampling rule of Algorithm 1, if the inequality (9) is satisfied, then the assumption (7) satisfied. We also note that the condition a < min(1 (1/3, v/) satisfied if a < min 1/(2xx +1) in the setting of Proposition 6.4.
It is easy to see that the unit sphere X' = for E Rdd ||]|| = }} satisfies the condition (9), More generally, we can show that if X' is a hypersurface with a "positive curvature", then X satisfies the condition.
Baselines. We compare method PMCA to the uniform random policy and MVR (Vakili et al., 2021), where the uniform random policy is a strong baseline in a pure explo- ration problem (as we discussed above, Jedra & Proutiere (2020) proved a uniform exploration is optimal in the case of the unit sphere). MVR is an optimal method for any arm
Proposition 6.5 (Examples of X' satisfying Eq. (7)). We assume that Çj == argmax xex (1 x. is unique for any
8

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
a, b 0.2, 0.4
a. = 0.2, 0.6
b 0.2, 0.8
a. b = 0.2, 1.0
method
lopfiN)
Ours
-25
-00
Uniform
50-
-100
-50
MVR
100
round
round
round
round
Figure 2. Comparison of our method to existing pure exploration methods in several problem instances.
sets for pure exploration problem (simple regret minimiza- tion), however, as we discussed in the introduction, their method is instance-independent.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning, especially for the area of the online optimization with bandit feedback. There many potential societal consequences of our work, none which feel must be specifically highlighted here.
Results. Figure 2 shows the experimental results for several problem instances, where the error bands represent 95% %- confidence interval over 10 repetition. MVR outperforms Uniform, but, is sub-optimal for some problem instances.
We provide more details of the experiments, experimental results, and CPU time for each method in Appendix G.
References
Abbasi- Yadkoi, Y., Pál, D., and Szepesvári, C. On- line least squares estimation with self-normalized pro- cesses: An application to bandit problems. arXiv preprint arXiv:1102.2670 2011.
8. Concluding Remarks
8.1. Conclusion
Balandat, M., Karrer, B., Jiang, D., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E. BoTorch: A frame- work for efficient Monte-Carlo Bayesian optimization. Advances in neural information processing systems, 33: 21524-21538, 2020.
We proposed a pure exploration algorithm for general con- tinuous arm sets that tractable and achieves an instance- dependent optimality. Moreover, empirically show that method outperforms baselines in terms of the computa- tional upper bound of the non-asymptotic error probability.
Banerjee, D., Ghosh, A., Chowdhury, S. R., and Gopalan, A. Exploration in linear bandits with rich action sets and its implications for inference. In International Conference on Artificial Intelligence and Statistics, pp. 8233-8262. PMLR, 2023.
8.2. Limitations and Future Work
A limitation of this study is the asymptotic nature of the optimality result. Developing finite-time analysis for practical algorithm would be an important direction for fu- ture research. In addition, we focus on the optimization of sampling rule and assume a recommendation rule is given. As discussed in Section 4.3, an (asymptotically) optimal method requires both optimal sampling and an optimal rec- ommendation rule and only discuss optimal sampling rule in this study. Moreover, some of our theoretical results (those provided in Section 6.3) and experimental results focus only on the greedy recommendation rule.
Bhat, S. P. and Amballa, C. Identifying near-optimal deci- bandit models with continu-
sions in ous decision sets. In Uncertainty in Artificial Intelligence, pp. 181-190. PMLR, 2022.
Boyd, S. P. and Vandenberghe, L. Convex optimization. Cambridge university press, 2004.
Bubeck, Convex optimization: Algorithms and complex- ity. Foundations and Trends@ in Machine Learning, 8 (3-4):231-357, 2015.
generalization to the Gaussian process reward model would be an important future work since it would enable the development of practical Bayesian optimization algorithm with instance-dependent optimality. However, existing anal- ysis (Vakili et al., 2021) indicates that exponential decay of the error probability may not be guaranteed depending on kernel smoothness, necessitating new theoretical analysis. Therefore, we leave as future work.
Bubeck, S., Munos, R., and Stoltz, G. Pure exploration in finitely-armed and continuous-armed bandits. Theoretical Computer Science, 4 412(199:1832-1152 2011.
Combettes, C. W. and Pokutta, S. Revisiting the approx- imate Carathéodory problem via the Frank-Wolfe algo- rithm. Mathematical Programming, 197(1)1191-214, 2023.
9

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic Linear Optimization under Bandit Feedback. In COLT, volume 2, pp. 3, 2008.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Laurent, B. and Massart, P. Adaptive estimation of quadratic functional by model selection. Annals of statis- rics, pp. 1302-1338, 2000.
Degenne, R., Koolen, W. M., and Ménard, P. Non- asymptotic pure exploration by solving games. Advances in Neural Information Processing Systems, 32, 2019.
Li, Z.,, Jamieson, K., and Jain, L.. Optimal Exploration is no harder than Thompson Sampling. In International Conference on Artificial Intelligence and Statistics, pp. 1684-1692. PMLR, 2024.
Dinkelbach, W. On nonlinear fractional programming. Man- agement science, (3(7):492-498, 1967.
Fiez, T., Jain, L., Jamieson, K. G., and Ratliff, L. Sequen- tial experimental design for transductive linear bandits. Advances in neural information processing systems, 32, 2019.
Mohammadi Zaki, M. and Gopalan, Improved pure exploration in linear bandits with no-regret learning. In Proceedings of the Thirty-Firss International Joint Confer- ence on Artificial Intelligence, IJCAI-22, pp. 3709-3715, 2022.
Frazier, P. I. A tutorial on Bayesian optimization. arXiv 2018.
preprint
Park, J. and Boyd, General heuristics for nonconvex quadratically constrained quadratic programming. arXiv preprint arXiv: 1 1703.0787, 2017.
Garivier, A. and Kaufmann, Optimal best arm identifi- cation with fixed confidence. In Conference on Learning Theory, pp. 998-1027. PMLR, 2016.
Qin, C., Klabjan, D., and Russo, D. Improving the expected improvement algorithm. Advances in Neural Information Processing Systems, 30, 2017.
Glynn, P. and Juneja, S. A large deviations perspective on ordinal optimization. In Proceedings of the 2004 Winter Simulation Conference, 2004., volume 1. IEEE, 2004.
Hiriart-Urruty, J.-B. and Lemaréchal, C. Fundamentals of convex analysis. Springer Science & Business Media, 2004.
Russo, D. Simple bayesian algorithms for best arm identi- fication. In Conference on Learning Theory, pp. 1417- 1418. PMLR, 2016.
Hoffman, J. and Wielandt, H. W. The variation of the spectrum of normal matrix. In Selected Papers Of Alan J Hoffman: With Commentary, pp. 118-120. World Scientific, 2003.
Ruszezyáski, A. P. Nonlinear optimization, volume 13. Princcton university press, 2006.
Salim, A., Korba, A., and Luise, G. The wasserstein proxi- mal gradient algorithm. Advances Neural Information Processing Systems, 33: 18:16-1233666 2020.
Jaggi, M. Revisiting Wolff: Projection-Fis free sparse convex optimization. In International conference on ma- chine learning, pp. 427-435. PMLR, 2013.
Schaible, S. Fractional programming. II, Dinkelbach's algorithm. Management science, 22(8))868-877 1976.
Jedra, Y. and Proutiere, A. Optimal best-arm identifica- tion in linear bandits. Advances in Neural Information Processing Systems, 33: 13:10007710017, 2020.
Shang. X., Heide, R., Menard, P., Kaufmann, E., and Valko,
M. Fixed confidenc guarantees for bayesian best-arm identification. In International Conference on Artificial Intelligence and Statistics, pp. 1823-1832. PMLR, 2020.
Jourdan, M. and Degenne, Choosing Answers in Epsilon- Best-Answer Identification for Linear Bandits. In Inter- national Conference on Machine Learning, pp. 10384- 10430. PMLR, 2022.
Shekhar, S. and Javidi, T. Instance dependent regret analysis of kernelized bandits. In International Conference on Machine Learning, pp. 19747-19772. PMLR, 2022.
Jourdan, M., Degenne, R., Baudry, D., de Heide, R., and Kaufmann, E. Top two algorithms revisited. Advances in Neural Information Processing Systems, 35:26791- 26803, 2022.
Shen, K. and Yu, W. Fractional programming for communi- cation systems-Pare Part I: Power control and beamforming. IEEE Transactions on Signal Processing, 66(10):2616- 2630, 2018
Kanagawa, M., Hennig, P., Sejdinovic, D., and Sriperum- budur, B. K. Gaussian processes and kernel methods: A review on connections and equivalences. arXiv preprint arXiv: 1007 02582, 2018.
Soare, M., Lazaric, A., and Munos, R. Best-arm identifica- tion in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
10

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Srinivas, N., Krause, A., Kakade, S., and Seeger, M. W. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. In International Con- ference on Machine Learning, 2010.
Vakili, S., Bouziani, N., Jalali, S., Bernacchia, A., and Shiu, D.-s. Optimal order simple regret for Gaussian process bandits. Advances in Neural Information Processing Systems, 34:21202-2113 2021.
Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., der Walt, S. J., Brett, M., Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., Carey, C. J., Polat, I. Feng. Y. Moore, E. W., VanderPlas, J.. Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E. A., Harris, C. R., Archibald, A. M., Ribeiro, A. H., Pedregosa, F., van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-274 2020. doi: 10.1038/441592-019900
Wang, P.-A., Tzeng, R.-C., and Proutiere, A. Fast pure exploration via fralk-wolfe. Advances in Neural Infor- mation Processing Systems, 34:5810 10-2811, 2021.
Xu, I.., Honda, J., and Sugiyama, M. fully adaptive algo- rithm for pure exploration in linear bandits. Interna- tional Conference Artificial Intelligence and Statistics, pp. 843 851. PMLR, 2018.
You, W., Qin, C., Wang, Z., and Yang, S. Information- directed selection for top-two algorithms. In The Thirty Sixth Annual Conference on Learning Theory, pp. 2850- 2851. PMLR, 2023.

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Table List of Notations
Symbol
Description the arm set the reward function I conditioned on Fr
X
St
P(X)
the space of probability measures on X' recommendation rule
(G))21
See
lim;-+co Çe (a.s. convergence)
(m1)e21
sampling rule
(w1)221
the noise stochastic process
V(A)
(V(m) : ग E P(X)}
Pe: M,
the posterior
and covariance matrix
(V(()));
the objective function for an optimal allocation ı (Eq. (1))
F (V
the regularized objective with regularizer xv (Eqq. (5))
|| |15-
(e+v(()-m())
Pt
a posterior probability distributions of random rewards ft
E
|
Frobenius norm VVV of a matrix V the space of symmetric matrices in ddd Dirac delta supported on singleton {a}, where E X the cumulative distribution function of the standard normal distribution
Sa
8(a)
+
((T)
E E 0.
A. Notation Table
provide the list of notations in Table 1.
B. Another Interpretation of the Objective
To provide another interpretation of (f:(C) we introduce known results on characteristic time (Jourdan & Degenne, 2022) for the BAI problem in the case of the finite-armed setting. In this subsection, we consider non-random linear reward function f + R and a finite discretization & of X. For simplicity, we assume argmax, = f()) is unique. Let .A be (c,6) 6)C strategy consisting of sampling rule for selecting arms Iı E X for each round t, and recommendation rule E X, and stopping time тa such that P(T8 < co, & & (e)) < An (e, 8P- strategy is called asymptotically greedy lim P(T < 00, 2 + argmax, =E f())) =
Proposition B.1 (Jourdan & Degenne, 2022), Theorem 2.1, Lemma 2.2, Lemma C.I). (i) For any asymptotically greedy (e, -PCC strategy with stopping time Ty, we have
E [r8]
I1 - Ell REP(E) (e+ f((*) f(E))²
lim inf 6-+0
2 inf sup 2
(10)
log 1/8
Here, 5" = argmax & f(z) and (T) denotes the Penore-eerrose pseudo inverse of (T). (ii) For any (e, P)AC strategy with stopping time Ta, we have
E [T8)
2 inf inf sup -
lim inf 6-0
(11)
log 1/5 (EP(() (c f(() f(())²
The LHS of Eq. (11) (resp. Eq. (10)) is called characteristic time (resp. greedy characteristic time) and any optimal strategy should minimize characteristic time. For instance, Lazy Track-and-Stop (Jedra & Prouticre, 2020) minimizes characteristic time over the probability distribution on a finite arm sets for fxx = (x), where H4, is an estimation the reward function. L=BAI (Jourdan & Degenne, 2022) requires a computation oracle for the optimization problem (11) that returns an optimal Ç and for f(x = (x)..
12

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
We note that one can take any fine discretization X of X' in Proposition B.I. However, taking fine discretization could hurt the performance of algorithm. If L is sufficiently fine discretization of X so that can identify & with the continuous arm set X' and if V (**)) is positive definite for any optimal allocation x², then we can apply our algorithm to the characteristic time minimization in the problem setting in Proposition B.
Intuitively, an asymptotically greedy strategy corresponds to a recommendation rule (G))21 satisfying limp-+o Se argmax=exx f (x) in our setting. In this case, our objective (f:() corresponds to the minimization of greedy characteristic time (10). Next, we assume that recommendation rule (51)221 satisfies lim So E argminçex* Tx((f(). One could construct such a recommendation rule if we have an estimation of T (f: for Ç E X in each time step t, and apply any black-box optimization methods (such as Bayesian optimization) to the estimated objective for Ç. Then, the objective (/x () corresponds to the minimization of characteristic time (11).
C. Related Work (Extended)
This paper studies a pure exploration problem with linear bandit feedback on a continuous arm set X' C TRd and our objective to minimize the posterior probability Pe(e: & X (e)) of misidentification under a Bayesian linear reward model. As we mentioned in the introduction, Bhat & Amballa (2022) studied a (e, 6)-PAC learning problem with linear bandit feedback on continuous arm set, where the objective is to minimize the stopping time of an algorithm that returns e-optimal arm with confidence 1 - 5. The (c, 8)-CC learning problem with linear bandit feedback has been well- especially for the finite-armed setting (Jourdan & Degenne, 2022; Jedra & Proutiere, 2020; Soare et al., 2014; Xu et al., 2018; Fiez et al., 2019; Degenne et al., 2019; Jedra & Proutiere, 2020; Mohammadi Zaki & Gopalan, 2022). Specifically. Jourdan & Degenne (2022) studied the transductive linear bandits (a more general setting than linear bandits), proposed an (c. PPC learning algorithm, and discussed asymptotic optimality as 8 + (i.e., a limit to the case of 100% confidence). Although our objective is to minimize the posterior probability PC & X (e)), our theoretical analysis is parallel to that of the (e, (PPC learning setting, i.e., we discuss asymptotic optimality of our algorithm as f - oo (Lemma 4.1, Theorem 6.2) and discuss stopping rule that ensures the posterior probability of misidentification is less than 5, where 5 E (0, 1) is given. We also note that an asymptotic analysis of the posterior probability of misidentification is standard in the finite-armed setting (I.i et al., 2024; Russo, 2016).
Despite extensive existing research for pure exploration problems with linear bandit feedback, most papers focus on the case of finite-armer armed settings due to the difficulties mentioned in the introduction. To the best of our knowledge, is an open problem to develop a trackable algorithm for pure exploration problem instance-depender optimality. Other than linear bandit literature, in general (not necessarily linear) Gaussian process bandits, (Vakili et al., 2021) proposed an optimal algorithm pure exploration (simple regret minimization). However, their analysis is also instance-indes indeeedennd
general continuous arm set with an
In the finite and discrete armed setting (i.e., there is no structural reward model), the BAI problem has been extensively studied. Since the objective introduced in Section is closely related to the characteristic time the fixed confidence setting (Jourdan & Degenne, 2022; Jedra & Proutiere, 2020), we mainly restrict our attention to the setting. In the finite and discrete armed setting, Glynn& & Juneja (2004) derived a condition for asymptotically optimal allocation. More recent papers provided more fine-grained analysis and optimal algorithms; Track-and-Stop (Garivier & Kaufmann, 2016), Foank-Wolfe based method (Wang et al., 2021), Top-Two algorithms (Russo, 2016 6; Qin et al., 2017: Shang et al., 2020; Jourdan et al., 2022: You et al., 2023). Track-and-Stop and the Trank-Wolf-basee method iteratively optimize a sampling distribution. However, unlike their setting, our probability space P(X)) is infinite- dimitt-dimensional,, so it is highly non-trivial to generalize these existing results. Moreover, due to the correlation between arms, it not trivial to generalize some existing algorithms such as top-two algorithms. The BAI problem has been extended to the linear bandit setting. However, most existing works focus on the finite armed setting (Soare et al., 2014; Xu et al., 2018: Fiez et al., 2019; Degenne et al., 2019; Jedra& & Proutiere, 2020; Mohammadi Zaki & Gopalan, 2022: Li et al., 2024). Therefore, similarly to the discrete finite case, it is non-trivial to generalize these existing algorithms to the case of continuous arm sets.
D. Additional or Detailed Theoretical Results
Lemma D.1 (A computable upper bound of the posterior probability). For any h > 0, let &n C be a finite subset satisfying the following condition: for ani X, there exists x' X₁, such that ||a- x' S h. For any 8' E (0, 1), we take B'z >0 0 so that P(d/2, 2, BB /2) 2 1 - 5', where P is the regularized gamma function (i.e., x r> P(d/2, x. /2) is the
13

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
cumalative distribution function of the chi squared distribution x.).
1. Then, for each O, we let
11; - 8' + 1
sup Pt(S(G)) S (() - s
SEX
where BL.s' is given as B == || + | 1/- 1/ BBg Then, we have the following non-asymptotic upper bound: Polce & x (c)) S ve h; X.).
2. Moreover, let c > be any positive number. For each t 2 if we take take 8; = exp( exp(-ttto), then there exists a sequence finte sets (Khe)221 with [x = O(poly(t)) and (ha)e2) such that
lim sup log un (8 Mni)
t-000
1
lim inf (oo))
(12)
Remark D.2. Assuming X' C [0, 1Js, make the statement of the lemma more explicit. Using notation of 2 of D.I, by the tail probability of chi squared distribution, we can take h4 = (-++) and [ is given as (Vdh (yd Then, uz(8%, f he, X,.)) gives an explicit upper bound.
Proposition D.3. Suppose Assumption 6.1 hold. Furthermore, let xy O, assume that 0 < min(v, () C 0 is given c. max(c.) gellF] with constant e 0, (fx)221 satisfies lim 1/: 0, and E th xc. Let (Tt) be the sampling rule defined by Algorithm 1. Then, we have the following a.s., lim inf (V(T)): (f:
E. Some Measure Theoretic Details
We provide some measure theoretical details omitted in Section 3. We assume that f. (we) and randomness of the algorithm are defined on a probability space (9,F, P) and the probability space is the product of two probability spaces (Rgp:Fuge P&p) and (Ωu, Fn, Pn), where the Gaussian process I (resp. the i.i.d noise process (wi); and randomness the algorithm) is defined on (Ogps FRD: PRD) (resp. (Sn, Fn, Pn)).
F. Proofs
F11 Overview of the Proofs
In Appendix F22, we provide proof of Lemmas 4.1 and D.I. In Appendix F.3, shall see that functions L'(:E:i; f) and (ff) is convex on ((X). In Appendix F.4, we introduce some lemmas required for the proofs of Proposition D.3 and Theorem 6.2. More specifically, we introduce results for subgradients, an approximate projection, an error analysis of an estimated objective function of (f Using these lemmas, we prove Proposition D.3 Appendix F.5, and prove Theorem 6.2 (and Proposition 6.3) in Appendix F.6. Finally, we prove Proposition 6.5 in Appendix F.7.
F.2 Proofs of Lemmas 4.1 and D.1
In this section, first, we proof the inequality (2), and Lemma D.I. then we prove the inequality (3). For the proof, we introduce the following lemma:
Lemma F.1. Let (Si)221 be a recommendation rule. Then, the following holds for any t 2 1:
(S()) sup ((E) -6)
.)
sup P. (f(G.) (()) - 5 P,
EEX
EEX
Proof. For any &, see that the event f(G) S f(()
implies f(()) < supeex f(E) c. Therefore,
supsex Pt (f()) S f(E) - c) < Pt (f(G)) S supeex f(E) ().
14

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Proof of (2). Let (Ze be any convergence subsequence of (me) and put V -lim;-so V(Te). Then, the assumption of the lemma, we have Amin (V) > 0. To show (2), it is enough prove
lim 2000
log P.Cca $ (e)) 2 - (oe:((
In the rest of the proof, by abuse of notation, we assume ( converges, lim V (TTe) = V, and prove the following:
1
lim 10
log Pi(ce $ x (c)) 2 - (T (V: (V: f)) f))-
(13)
Let & is Fm-meauuralle random variable. Fort 1, we let X, et fi(St) - fr(E). Then conditioned on Fr, X, follows the normal distribution:
X, ~ N (e()) - (G) - 5) Tx, '(e - -))).
(14)
Thus, we have
P.(f(C)) S f(E) c)) < 0) ②b (-11/2 + pe(Ge) po(E)
(15)
11sr El((2,/0)>
where & is the cumulative distribution function of the standard normal distribution. Using the asymptotic formula of the complementary error function for sufficiently large x >> 0,
erfc(z) exp(-x²) IVT
(1+
we have the following for sufficiently large x > 0,
log (-=x) log erfo(r/ (0/V/////22)) 22) - log
x²
logævo22 2n + log (1 (1 01+ 9)
We let T2 = ct((E Tsr-Ellos,//)-11 Then, by assumptions, have lim 815-61y-1
(+1(()- f(E)
0. Therefore, by Eq. (15), for
sufficiently large t, we have the following:
Jt. 1 log P.([(G) < f(9) -c) -()= - t
logre V 20/1/2 + 1 log (1 + (1+0(1)),2))
(16)
Thus, it follows that
lim log P.(S(G)) S ((S) <) (E- - f(() - f(E))² t-00
(17)
2 115 E
The above argument holds for any even the event & = ( = C. then lim I't and the both sides of Eq. (16)
tend to oo and we understand both sides of the equation above represent - -o)). Since lime ((+)()))(E)) xc, for 115-E11--1 Thus, by (17), we have
any small open neighborhood U of C, we have infgex (c+)(()-/(E)= infçexru (c-11C)- (()) 115-511-11
1I--
1 - (V:(Vi
sup lim log (((((G) & f(E) -c) c) <E txxt t
(18)
Since Ge + Soo, for sufficiently large f, convergence of in LHS of (18) is uniform w.r.t & E X' U. Therefore, we can exchange som and supeexyu and it follows that
lim 1 sup log P.(f(G)) S -) - -)) - (VVV:..)))
(19)
100 1
gex'u
(p) and lime Ti = -+/(6=)-((E) By (16) with r, = [[ El0
[[ Ellv-1 we can take a neighborhood 14 of Soo and a sufficiently
large lo 2 1 such that supeexyz log (G( S f(E) - <) = supeex log Pr(S(G)) S f(E) - e) for any 1 2 lo. i.e., the
supremum is not attained for & E U. Thus, we see that the following holds:
lim sup log P.(f(() < f()) - -)= (V: - to00
(20)
gEX
The inequality (13) follows from (20) and Lemma F.1. This completes the proof.
15

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Next, we provide proofs of Lemma D.I and the inequality (3).
Proof of Lemma D.1 and (3). Let & X' be any finite subset and define
(c; x x: f(x) > sup f(E)
We define (e(e; F) by
pclc;))= Ps Pp &
Then, by union bound, have
U ( -e)
lo log Pt
AEE
log
Σ (
LEE
$ log
X
+ sup log Pe (f(G) S f()) -).
(21)
EEX
Next, consider the second assertion. By definition of By and 0 ~ NN(H,, Dr have
P([l1Oul S Bi, 51-8
Thus, we have
Pi(S & X" (c) < 8' + P.(s. & x" (6),11011 S B,,,)) 8 + P.(s. & x' + ;
Here, the second inequality follows from the Lipchitz condition of the (posterior) reward function x 0, and the definition of Xt. Noting that by Eq. (21), have Pe (c(;; < supeex P. (f(G)) f(E) c'), we have Pt X (c)) I (6', h; Xn) (i.e., the first assertion of Lemma D.1).
Next, prove the second assertion of Lemma D.I and inequality (3). For each 1, we let he > 0 and Xn, X be finite set with L (t)oy((t) (we choose h; and Xh, later in the proof). For simplicity, we denote Xr, by Xr. We also let 0; E (0, 1) so that & s supeex Pt (f(G) < f(E) -) holds for sufficiently large and log(8)) O(poly(()) Since by Eq. (20) and assumption of the covariance matrices, have
sup log P, (f(G.) < f(() - -)) O(t)
<Ex
for example 8 exp(-t?) satisfies these condition. By the tail probability of the chi square distribution (c.f., (Laurent Massart, 2000, Lemma 1)) and the definition of B, we have B (t))y(()). Therefore, if take sufficiently large m 1, have
lim h Br.5, = O, 1000
16

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
with h4 = By the first assertion of Lemma D.I, have the following:
1 [ log P.(Ge $ X" (e))
lim limsup sup 10000
1 log (ui h4; ),,))
1 <limsup 1-000
t
+ log
1
< sup 1+x
[ sup P. (f(G)) S ((5) -6) -))+ + + EEX
7
1 < lumsup log Kel + lim (-000
1
log Pt (f(G) & f(E) -
{
EEX
1
sup sup log Pa (f(C.) S f()) e). (-000
7
gEx
Here, the first and second inequalities follow from the first assertion of Lemma D.I, the third inequality follows by the condition of & (i.c., 8 & supgex Pt (f({.) < f(E) - e)). the last equality follows from log |/& = (pooly(log t)). Our assertion (3) follows from this inequality and Eq. (20). We also have the second assertion Lemma D.1. This completes the proof.
F33 Convexity of the Objective Function
The convexity of the function ((::E:C, follows from the lemma below. Since the function (f defined as the supremum of functions (T(::;;;ff)) we see that ("; is also convex.
Lemma F.2. For any a Fd, the function V + TT V defined on 8 is convex.
Proof. We note that the following holds.
sup a 2
AERd
As function of V, the LHS is supremum of affine functions. Therefore, it is convex function with respect to V.
F44. Some Lemmas for the Convergence Analysis
F.4.1. SUBGRADIENT
Since the function (VVV; S. (1) is the (pointwise) supremum of collection of differentiable functions, we can compute its subgradient as follows (ef. (Hiriart-Uruup & Lemaréchal, 2004, Chapter D, Section 4.4)).
Lemma F.3. Let S E X, μ argmaxgex I(V,Ç, Then, the following is subgradient of I (V: (,; at V: sv ==-(e+ -((E))((()))))))))))))) -V () - 5) V-1 that is, I (U: () 2 I (V: + (U V), VU E S
+ R, E 5 be a symmetric positive semi-definite mutrix, and & =
Proof. Let g argmaxçex I'VV 44). Then, by (Hiriart-Urruty & Lemaréchal, 2004, Chapter D, Section 4.4), the gradient of the differentiable function C. p)) at V a subgradient of (V: ()). Then, the assertion of the lemma follows from the matrix calculus.
F.4.2. APPROXIMATE PROJECTION
As we stated in Section 5.1, Algorithm takes an input V E gdddd and returns distribution गे on X' so that V( is an approximate projection of V to ((Y) with respect the Frobenius norm. More formally, have the following lemma and can prove by the analysis of the Frank- Wolfe algorithm (Jaggi, 2013) applied to the function V(X) X + ||X | VI Lemma F.4. Let W E Rddxd be symmetric matrix. For 2 2, we denote by HI (W) by V( where ((n) is an output of Algorithum 2 with input W. Then, there exists universal constant e > O such that the following statement holds. For any X E V(X), we have
(W) - X1I + (W) - W < X
3
11 +
17

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Or equivalenty,
ck
(X - [[](W)) (II((W W) 2 2(n + 2)
Proof. We define function on ((X) by g(X) ||- VIl on v(X) for V(2). given (Vg(X), 2 V)x'. Since V(X) the convex closure of {ax
Then, the gradient of g
XJ, note that
x (V)(X), X²) is equivalent to
argmin Tr(X- V)ax" argmin 1x=1xx
Therefore, Algorithm 2 is the Frank- Wolfe applied for minimizing the function g over X. We also note that the curvature constant Cy (ef. (Jaggi, 2013)) is given as
C/= =2 XXX'V(X))
sup
|X X < 2(2
Therefore, by (Jaggi, 2013, Theorem 2), there exists a universal constant c > 0 such that the following incquality holds:
ck
2 (VV
v)
V E V(X).
n +
The assertion of the lemma follows from this inequality.
F.4.3. ESTIMATION ERROR
In Algorithm compute estimations of the values of f and Therefore, introduce concentration inequality for (r).. Since f is a linear function on X' with probability 1, the following proposition follows from the standard result (Abbasi- Yadkori et al., 2011). However, due to the non-standard setting (i.e., is random function), we apply the standard (Abbaii-Yadkori standard concentration inequality on the probability space (a. Pa) for each Wgp E Sep where notation defined in Appendix E). We also remark that a similar concentration inequality proved the Gaussian process setting (Srinivas al., 2010).
concentration inequality (Abbasi- Yadkori et al., 2011) after sampling a random function f (more formally, we apply the
Lemma F5. For any > 0, the following inequality holds with probability at least - 8: If(x) - me(x)) S
(())),(()), E 1, where 0r(x)= = V TV, VV,Vaa and Be( = vA (Vdlog
[ ( 8
+ |10'11
The following lemma states that V(T.)) can approximated by the empirical covariance matrix and can proved by the standard concentration inequality (Abbasi- Yadkori al., 2011).
Lemma F.6. Assume x, E X is sampled from a probability kernel n.. Then, for any E (0, 1), the following inequality holds with probability at least 1 for any t 2 1, i E.
x, V( F S ([(8)/ Vt, where म, 1 E Re and
(((5)= = ++- (1 20g (1 101/281)))))
Proof. For each x E X and i < d. the (i.j) entry of xx is bounded as
(xx)) Dsg Tr e xx e, Tr xx e,,, z ||r lIrlee IF S K.
Thus, for each (i.j), (0.05) (TTT) by is conditionally 2T-subgaussian. By (Abbasi- Yadkori et al., 2011, (11)) and taking x [d]. we have
a union bound for (i. E (d]
J Σ (TTa)oo S (1+ (1+ (1+ (1)(
18

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
We deduce the following lemma by Lemma F.5.
Lemma F.7. Let ( be a sequence of actions selected by Algorithm I and Co. Pt be in Algorithm 1. Then, there exists
(o) to; d, a, Texp) such that, with probability at least - 8. we have
[f(z) (x)x S (8)
(22)
ift 2 to, where (6) Bc(6/2) 2(1 a)d (V(Txx)))
Proof.
By Lemma F.6 and the Hoffman-Wiclandi theorem (Hoffman & Wielandt, 2003), with probability at least 1 8, we
have
{ Tatt
1
Amin
7
Amin (V(T+)) S 1((5
We put ar : Ex_1 8 " Since V(T,) - as V (TTop)), we have
1 (
(
at (Amin(V (VTTex))) -
1--12) s Amin
xz
t
We take to tolō; d, a, Texp) so that (((0/2)a; 1--122 Amia (VanaVVVTTT (Texp))/22i3 2 to Then, if 2 to. we have
1
1 Σ
2 Amin (TTxx)))) Amin
7
Thus, for any x E X, ift 2 to, the following incquality holds with probability at least 6/2:
(x())= S 22x-1/2 min (V(Tex))) ,/2,, < v2v1 - 12v1-ax-11"
Then, the assertion of the lemma follows from Lemma F.5.
Finally, by above results (Lemmas F.5 F.7), we can upper bound the estimation error of the objective function follows. Lemma E8. Lei (xe)z, be sequence of actions selected by Algorithm I and Ct. pe be in Algorithm 1. Assume V = t V (Tex)). Then, there exists t, (6) ti (6; d, Texp) 2 (o) such that with probability least 1 - 8, we have
(V: - -
S (V (TTEx)))( V Tellss - Small + 2e" "-3 X (V(Te)) (BIlG: Sxol (0))
Here, == f(Coo) supeex (xx + 6 > and the notation S hides universal constants.
Proof.
Let &g be an event on which the inequality (22) holds if 2 (o))). We assume that &s hold. Then, for E X, we
have
|l|: - Ellv- - 11500 - -1lv-11 S 115+ --oll-
< 10/2 >0/2>> (V Sxoll
-1/2
(23)
For E, V, we define function :: R2 + R as
(11600 Ellv-1 + p)
<(p.0) (E+ f((5o) f(E) + q)²
Letting p. I1s+ Ellv- - 11550 Ellv-1, 9: (e((e) -((50) - -M(l) + f({) and the Taylor theorem, have
T(V, = (pe.9)) qc)
0Φ
αΦ (pe, कo )a:.
= =I(V Eoci: +
(P., d) +
Op
0g
19

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
where (pr, (+) (Ipr lq)) with 0 < <ISL 1. We take (1(6) (1(6e"", 3e (8)66000111 1)/2
, M, B,d,ar a, Texp) lo(0) that lgel S Blls: Soo
<" /2 if 2 (6), where e' is defined as
Then, if t 2 (6). we have lq.1 - /2, and
d6
2 2 xmin 1/2 (V (Texp)) (V + lIse (xoll) S 2xmin (
(Pr, %b)
0p
06
Se" XV (v lIse llse - Scoll) 3e" (V (V (TTexp)))t
(Pt. 9:)
0q
Here, notation S hides universal constants. Thus, we have
(V: (V: 0)
S - 2x 1112 (V (Texp)) / V klpp.l + c" (V (V (f
S "² 2x Att (VTTex)) ) a v /Tllss Soell
+ 2c 3 (V (Texp))Ktt (Blls - -r(
F.5. Proof of Proposition D.3
Proof of Proposition D.3. We follow the standard proof of the (projected) subgradient method (Ruszczyúski,, 2006, Chapter 7). However, in our setting, we only have an estimation of the objective function, and we can compute the projection only approximately. Thus, we provide proof for completeness. In the proof, we define
(=) = r- - TVV + t t (F(ex))): (e, =- (VV::.=
for any V VXY). Then, by definition, we have (V,) (V:). For symmetric matrices A, B E Rdxd we denote Tr AB by A B. We assume the event &o on which Lemma F.8 holds. Let V E argminvep(x) (V: We let
d. = S: (V- /
U V + dege/199/11
1| 1- 11, (W++1) VO1
ck 2
< |Wi+1 V²1
2(ni +
ck
1 m/ag: V*
2(n; +2)
ck
11, v' 2cm.g (V-V + 11911
(24)
2(n, + 2)
ck²
< 1 v 2c.nellallldd m//22) 2(n, + 2)
(25)
Here, the first inequality follows from Lemma F.4 and the second inequality follows from ey e1l1 S 1. Since gi is subgradient of T at V. by Lemma F.3, and by definition of de, Ur, we have
(U.) > (V.) + g: (U, - V.) - I, = (V)).
(26)
20

---

Pr T Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
If lim in d2 then there exists subsequence T (nn)221 such that 1im in oo and n Un V have for i T.
= (M()) + (M()))-F((()))
((())) +
((U)))
2 2((((V) (((())) +17(K)
= -("(())-) - ( (()(
+ (V (F(())) (V)))) + (V)).
(27)
By a < max(1/3,0) v). Lemma F.8, and the definition of T the second and third terms in (27) converge to zero since Lemma F.8 holds uniformly for V E V(X). For t E T, the first term converges zero. Thus, by inequality (27), we have (V***) 2 lim in I (V.). Thus, we have our assertion if lim d, 0. Next, we assume lim inf de > 0. that there exists 0 and t 2 such that de 12222 for any 2 t1. By summing both sides of (25) for 1 S < where s is any integer with 2 t1, we see that
Since lim 7ht 0,
0 < V V 1 < 1V - V'
2a Σ
CelleelTTe
+
2(m + 2)
t=
t=t1
lim infz- ce cell9:11r 0, then can derive contradiction by the above inequality by taking since E 7/ xo and Ee= (ne + 2) < oc. Thus, we assume that lim inf cel19:11e = O. Since gi is a subgradient of F2 at V,, we have
I7 = - (V").
ge (v. V*) 2 (V))
Since V - || is bounded, we have 2 lim inf o0 (v:) Since Lemma E88 holds uniformly for E V(X). we see that lim inf,- n (V)) = lim inf, (V,) & (v*) = [V*)).
(V
Therefore, we have proved that for any E (0, 1) there exists an event &, with P(Es) s 1-8 such that on &g, we have inm (V)) (V*).
We take sequence (6n) with 8n E (0, and lim, on and let &n Es.. We define event & as lim sup &n On Uk2n Es. Then, by Fatou's lemma, we have P(E)= > limssp,, P(E,) Z lim lim (1 6,) = 1. Since for any w E E, there exists 2 1 such that w E En, and, we see that lim infe I" (V(TT)): = T" (f:() holds on E,, holds on the event E. This completes the proof.
F6. Proof of Theorem 6.2
For the proof of the theorem, we introduce the following results (Proposition F.9, Lemma F.10). We note that Proposition 6.3 follows from Proposition F.9.
Proposition F.9. Suppose assumptions in Assumption 6. hold. We
(V: f) [
+ \
and Vi,- E argmaxyev(x) (oo f). Then, for any 8 E (0, 1), we have the following for any T with probability at least 1 - 8:
Ist (V I#t
Here, using notation of Lemma F8,, pr is given as
(4e -2 -1 (TT o AyR +
41+1 ( +2+ b 222
TV f) - G. + Σ -TX
and c' - d' Texps Xv)= = (4x (V (TTxp))) -2 )2
Moreover, we have the following a.s.:
lim 1 (V(((Te): = 10000
21

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Proof. Basically, follow the standard proof of the projected subgradient descent method (Bubeck, 2015). We let T Goo f) Soo, + Av [V]l and (v: f) - (11--19) + +t= Soo: f), Viv
vev22 (o: f).
We put 9: = - - t ()(( + me(e)) - Ho(E))) 2000 + 2Av Vr E Rddd Since 9:. is a subgradient of [2 Se. Me) at Vi,
we have
(. TT S Tr - -V)
1 Tr(V, -W+1) -VAr)
(IV:
-W+1 11: + I| - Vxy 11: -IVV - -W1+1l1?)
21P
11l |1
ll
1
(I Vx |ا -I - Wet+lll)
(28)
2n
By Lemma F.4, we have
11V Vet1 11 - 115 We+1 11 ck
(29)
14 + 2
Since V/ 2 (TTex)) we see that
Bonal |F = EG) (VV) (V/))=(GG 2GG Er) s 4x (V(Tee))
Thus, have
1100 < pa d.
where d c(e,, Texps Av) (4) A (T(oxp))) )2v By this inequality and (28), (29), have
(e.ViiG. - [T((V2;
T
An n. + +2- 2/-11/111 Vgr + "T ck
Y1g
+
2
t=1
T
2- 22k
1d + (2 + c)k 'T 2
Here, we take so that Eee 1/(n: + 2) < 1 and take = t- 1-20-117 1/2 Then, we have
T
d' d
4a+1 +2+c 2ddut112
(30)
22

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Noting that (V: f) & 4e 4e "> (F a + Ayk for V E S for t S f1, we have
T
- (vor: f))
(Vi f) - (oc.
< 11 (4c X (Texp)) " + \v +
Σ
< 11 (4e 2 > (Tex)) +xb + 1a
d
+2 + 0)
//uua11/2
T
T
(T:V:: 12 (V::
Σ
-
Here, the third inequality follows from (30). Since F'x (5 Soo: J) is convex function, we have
I ((1 - ar) V or (Texp): foor f) I't i S PT T
V and oT = Ei= to Thus, we have the first assertion. Letting Av = O, by Lemma F.8 and the assumptions, with probability at least 1 o, we have lim (v) f) = (fo By the same argument as in the proof of Proposition D.3, we see that lim (V f) (f: (oo). holds a.s. Thus, we have the second assertion. This completes the proof.
where ,
Lemma F.10. Let {)) be a sequence by running Algorithmm 1. Then, for any x E X, we have lim Me(x) - f(x) almost surely.
Proof. This follows from Lemma F.7 and the same argument in the proof of Proposition D.3.
Proof of Theorem 6.2. The statement of Theorem 6.2 follows from Lemma 4.1, Lemma F.10, and Proposition F.9.
F.7. Proof of Propositions 6.4 and 6.5
Proof of Proposition 6.5. Suppose X is a unit sphere and let f(x) - x. Then Ç2 p// ||1
and by
[(C)) - [(x) |121|| (1 (1-1Al x
He
|0 2
2
||]|
||ا2 - =el2
Telli
=
x
2
the assumption (9) is satisfied with xx 2.
More generally, let us suppose that for any zo E X' there exists a neighborhood Uz C 12 of zo and an analytic function Φro Uzx + R such that X' nue,, is given as fi E Uz, oz (x) = 0} and the minimal eigenvalue of the Hessian of Φz. at Jo larger than a positive constant >> independent of ag. We define a (possibly infinite) constant 7(1) by
|| 1/
T(H)
sup xEx(((;)) 1 Ç/- - 1 27
Ia 1--C1 [-- By assumptions there exists an open
If (p)) < 30 for μ + 0, then we have the condition (9). We let ((,,x) neighborhood 2/ <7 and an analytic function á : 24 + R such that locally X is given as Φ(x)) 0. Since Çi is an optimal arm, there exists Lagrange multiplier do e R such that μ dn Vo(G)) By ||ll| * 0 and |Vo(2t)) is bounded, we that Au 2 1. Thus, it follows that
110 . 5% 1t. = (((() (x - - Z VV() (x - -,,,,
23

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
for any E X nu. By the power series expansion of &b around çū. for each X Xnu, we have
x()) = vo(())) (x (p) + - ()) ( -2 Ra(x Sii S7))
Here, H(+)) is the Hessian of Φ at çp and Ra(: (t) is the residual of degree greater than or equal to three of the power series expansion. Thus, for any x E X nu, we have
x), = Ax -x--sill
| - Cill
(31)
I 94 J (0 -0--;) T (2= - (7) + 2R Sp: (p)
By the assumption the Hessian, we that sup ((,,)) co. If X' \ U, then by the uniqueness of Ço we have inf (1- (Si - z) > 0. Therefore, supeexiu (1, x) < co. Thus, we have (1)) < co.
Proof of Proposition 6.4. By the assumption Amin (V)) 2 t t9, we see that by the same proof, statements of Lemmas F.6 and F.7 hold for the sampling rule (24)221. Let (6) and (6) be constants defined in these lemmas. By (22) and the definition of Gr, we have
S(C) S p4(() + (1) (m(G) (8)
Similarly, we have
pelG) S (10) f()) /2))
Thus, we have If(() - (i(s)) I (8)) From the assumption (9), 1|5 - Gell s
Here,
3 (8) = (cx,)) (8) Thus, the assumption (7) holds with v = (1 - (2x
G. Appendix to Experiments
G.1. More Details of the Experiments
We provide more details of the experimental results in Section 7. The experiment has been conducted using AMD) EPYC
7352 CPU with 64GB RAM. In the experiments, we use the following parameters of the algorithm: a = 1, 1/2 =c/V
n = 1/t², Ay = 0. where C, is defined so that Tr 1991 = 1. We take Texp as the uniform distribution on X. For, step sizes (7t); for Algorithm 2, we did a line-search to minimize the objective 7 + [I(1 - 7) (+;-)) + +7 a. - WI We take a larger a in Assumption 6.1 since we consider a mixture distribution with Texp to ensure V(Tx) is positive definite. If this condition is satisfied during the optimization, it is not necessary to consider a mixture distribution and taking a smaller a makes the convergence slower. Thus, we set a a larger value in this experiment. In Algorithm 2, we break the for loop if ())))) V(* is less than a threshold, and we take the threshold as 10-3 To optimize the fractional objective, we used the Dinkelbach's 'ss algorithm (Dinkelbach, 1967). In the implementation, we stop the iteration loop if Ian -- < 10-5 or n. > 30, where gn is given in Section 5.3. We empirically solved the linear and quadratic objective on X by using the optimization library provided by the SciPy (Virtanen et al., 2020).
G.2. Additional Experimental Results
As we detailed in Section 7, we have conducted experiments in the following setting; X' is defined as a subset {(cos(0), sin( 0 E 10,, 01]} of the unit circle in IR2 and f(x) = (ins())),sin(()))) x. À = 10-2,e where 0, = am, fg = 0, 01 = br, and a = 0.0, 0.2, 1.8, = 0.0, 0.2. 1.8 with a < b. Due to the page limit, we only show a subset of the experimental results. In this section, we introduce additional experimental results. In. We show experimental results with (a. b) (0.0, 1.8), (0.2, 0.4), (0.2, 0.6), (0.2, (0.2, (0.2 1.2,, 1.4), (0.2, 1.6), (0.2, (0.4, 0.6) in Figure 3, that (0.6.0.)) (0.6, 1.0). (0.6, (0.6, 1.4), (0.4,0.8), 1.04, (0.4)),)) (0.,,,,))) (0.4, (0.4, (04, (0.6, 1.6), (0.6, 1.8). (0.8, 1.0), 1.28, (0,8, 1.6), (1.0,,))) in Figure 4, that with (a, 1.4), (1.0, 1.6). (1.0, (12, (L) (1.,, (1.4, (1.4, (1.6, in Figure 5. These figures indicate that our proposed method overall outperforms the baselines. Although these figures shows our method overall outperforms the baselines, we see that in some problem instances (such as (a.b) b) = (0.0, 1.6)), MVR outperforms our method and we suspect that in some problem instances, MVR happens to be nearly optimal. Improving an empirical
10-2.
(0.0, (0.0, 00.0, 00.0, (0.0, 1.0), (0.0, 1.2), (0.0, 1.4), (0.0, 1.6),
with (a,
24

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Table 2. CPU time of each method (including time for evaluation)
method time (sec)
Uniform
MVR
Ours
1.2e+00 (1.9e-02) 1.3e+00 (2.0e-02) 2.6e+00 (4.3e-02)
Table 3. CPU time of each method (excluding time for evaluation)
method
Uniform
MVR
Ours
time (sec)
8.6e-03 (6.7e-05) 1.9c-01 (6.4e-04) 1.5c+00 (2.3e-02)
performance of our proposed method (for example, by selecting an appropriate step size m)) is also future work this study.
In Tables 2, 3, show cpu time for each algorithm for the left most instance in Figure 2. In these tables, the number represents time in seconds for rumning experiment and shows the mean (std) over 10 repetitions. Table 2 shows the numbers including cpu time for computing Pt (the evaluation metric) and Table 3 shows the number excluding epu time for computing These results show 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 reasonable time.
25

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
0.0,
0.0.0,
a, b 0.0, 0.6
-25
-10
-25
log(p))
log(p.)
logipH
-50
-7.5
method
Ours
methad
Ours
-75
method
Ours
-10.0
Uniform
-40
Uniform
-100
Uniform
MVR
-12.5
50
125
0
20
40
60
100
60
80
100
20
40
60
80
100
round
0.0,
0.8
round
b 0.0,
1.0
round
a. b
0.0, 1.2
0
O. M
-50
-50
log(e)
log(Po)
log(p)
100
-100
method
-100
method
150
method
Ours
Ours
Ours
Unifarm
-150
Unifarm
200
Unifarm
-200
MVR
MVR
250
MVR
100
round
a. b = 0.0, 1.4
round
a, b = 0.0, 1.6
round
a, b 0.0, 1.8
Www. WWW
-100
-000
-100
logipd
-200
method
lagipd
400
method
109)PH)
200
methad
Ours
600
Ours
Ours
-300
Uniform
Uniform
-300
Uniform
400
MVR
8000
MVR
400
MVR
0
20
40
60
80
100
0
20
40
60
80
100
20
40
60
80
100
round
a,
0.2,
round
0.2,
round
a, b
0.2,
0.8
10
-2
-20
log(o))
logle))
-40
method
method
method
Ours
Ours
-60
Ours
-30
Uniform
Uniform
Uniform
-80
MVR
60
MVR
MVR
20
100
60
80
100
round d
0.2, 1.0
round
b 0.2, 1.2
round
b 0.2
1.4
-2
-20
-50
loglpd
log(p))
-40
log(p))
-40
method
method
method
100
Ours
-60
Ours
-60
Ours
Uniform
Uniform
Uniform
150
MVR
-80
MVR
80
MVR
20
40
60
100
80
100
40
60
80
100
round
a, b = 0.2, 1.6
round
a, b = 0.2, 1.8
round
a, b
0.4, 0.6
-20
-200
log(o,)
(x))
-100
log(o:)
method
method
-40
method
-400
-150
Uniform
Uniform
Uniform
-60
MVR
MVR
MVR
-600
0
20
40 60
80
100
0
20
40
60
80
100
20
40
60
80
100
round
round
round
Figure 3. Experimental Results for (a, b) (0.0,0.2), (0.0, 0.4) 0.6), (0.0. (0.0, 1.2),
(0.0. 1.4), (0.0, 10.0,
(0.0, 1.8), (0.2, 0.4), (0.2, 0.6), (0.2, 0.8), (0.2, 1.0), (0.2, (0.2, 1.4), (0.2, 1.6), (0.2, 1.8), (0.4, 0.6).
26

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
a, b 0.4, 0.8
a. b 0.4, 1.0
a, b 0.4, 1.2
20-
-20
-20
log(oz)
-40
log(p.)
40
log(o,))
-40
method
method
method
-60-
Ours
-60
Ours
-60
Ours
Uniform
Uniform
Uniform
-80
MVR
-80
MVR
MVR
20
100
20
100
20
80
100
rnund
8. b = 0.4, 1.4
round
a. b = 0.4, 1.6
round
a. b
0.4, 1.8
-20
-50-
-50
loglo,)
loglo.)
log(pa)
-40
method
-100
method
methad
-100
-60
Ours
Ours
Ours
Uniform
-150
Uniform
80
Uniform
-150
MVR
200
MVR
100
MVR
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
round
a, b
0.6,
0.8
round
a, b =
0.6,
1.0
round
a, b = 0.6,
1.2
-20-
20
20
(og(
40
(og
-40
log(
-40
method
method
method
-60
Ours
-60
Ours
-60
Ours
Uniform
Uniform
Uniform
80
-80
MVR
MVR
MVR
1000
100
0
20
40
60
80
100
0
20
40
60
80
100
20
40
60
80
100
round
a, b=
0.6,
1.4
round
a, b=
0.6,
1.6
round
a, b
0.6,
1.8
-20
-20
-20
log[pd)
-40-
log(p,)
-40
log(p.)
-40
method
method
methad
-60-
Ours
Ours
-60
Ours
Uniform
Uniform
Uniform
-80
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
round
a. b
0.8,
1.0
round
a. b
0.8,
1.2
round
b a.
0.8, 1.4
20
20
-20
(og)
(o.)
(og(o.)
-40
method
method
method
-60
Ours
-60
Ours
-60
Ours
Uniform
Uniform
Uniform
80
MVR
MVR
MVR
1000
100
20
40
80
100
20
40
80
100
20
40
60
80
100
round
a, b = 0.8,
1.6
round
a, b
0.8, 1.8
round
a, b =
1.0, 1.2
-20-
-20
loglp:)
-40-
log(p,)
50
loglp.)
-40
method
method
methad
-60-
Ours
-100
Ours
-60
Ours
Uniform
Uniform
Uniform
MVR
MVR
-80
MVR
20
60
80
100
20
40
60
80
100
60
80
100
round
round
round
1,0,,,..0,00.,1111..... 1.2), (0.4, (0.4,1.6) (.84, (0.6, 0.8), 10.6,1.0), (0.6, 1.2), (0.6, 1.4). (0.6, 1.6), (0.6, 188), (0.8, L.), 10.8, 1.4). (0.8, 1.6), (0.8, L.8), (1.0, 1.2).
Figure 4. Experimental Results for (a, b) = (0.4,0.8), (..4,
1.0), (0.4,
27

---

Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
a, b 0.4, 0.8
a. b 0.4, 1.0
a, b 0.4, 1.2
-20
-20
-20
loglpa)
440
log(p.)
440
loglp.)
-40
60
method
-60
method
method
-80
Uniform
Uniform
Uniform
MVR
MVR
MVR
20
40
60
80
100
0
20
40
60
80
100
20
40
60
80
100
round
round
round
b 0.4, 1.4
b 0.4, 1.6
b 0.4, 1.8
-25
500
-50
-40-
log(p)
-75
log(p))
log(p)
-100
-100
-60
method
method
method
Ours
-150
Ours
80
Ours
-150
Uniform
Uniform
Uniform
MVR
MVR
100
MVR
-175
20
40
60
80
100
20
40
60
80
100
20
40
60
80
100
round
round
round
a, b 0.6, 0.8
a, b 0.6, 1.0
a,
0.6, 1.2
20
-20
log(p))
log(p))
-0
log(p>)
-40
-60
method
method
method
Ours
Ours
Ours
-80
Uniform
Uniform
Uniform
MVR
MVR
MVR
20
60
100
-100
20
60
80
100
100
60
80
100
round
round
round
Figure 5. Experimental Results for (a,b) = (1.0, 1.4), (L.0, (.),,
(1.0, (1.0, (1.2, 1.4,, (1.2 1.6), (1.2, 1.6), 1..),
(1.6, 1.8).
28


Reviews:
[{"review_id": "H0BVHroreN", "reviewer": "Reviewer_huXi", "summary": "This work studies the problem of pure exploration for linear bandits particularly with continuous arms. The paper begins by establishing a lower bound on the asymptotic posterior probability of misidentification, and then proposes a tractable algorithm, called PMCA, for minimizing the error probability. The authors provide theoretical analysis showing that the suggested algorithm finds the optimal sampling rule that achieves the asymptotic optimality for any given recommendation rule. The numerical experiments show that the algorithm outperforms MVR and the uniform sampling strategy, confirming the theoretical finding.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's thorough and insightful review. We will revise our manuscript based your on suggestions.\n\n\n## Instance-dependent optimality and recommendation rule\nWe 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.\n\n## Assumption 6.1 and the assumption for Proposition 6.4 \nOur 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.\n\n\n## Experiments \nWe 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. \n\nIn 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$.\n\nThe 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.\n\n\n| Uniform (w/ eval_time) | MVR (w/ eval_time) | Ours (w/ eval_time) | Uniform (w/o eval_time) | MVR (w/o eval_time) | Ours (w/o eval_time) |\n| -- | -- | -- | -- | -- | -- |\n|1.2e+00 (1.9e-02) | 1.3e+00 (2.0e-02) | 2.6e+00 (4.3e-02) | 8.6e-03 (6.7e-05) | 1.9e-01 (6.4e-04) | 1.5e+00 (2.3e-02)|\n\n\n## Practical applications\nAs 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.\n\nMore 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).\n\n**References**\n- Jinnai, Y., & Ariu, K. (2024). Hyperparameter-Free Approach for Faster Minimum Bayes Risk Decoding. In ACL (Findings).\n- Li, Y. (2025). LLM Bandit: Cost-Efficient LLM Generation via Preference-Conditioned Dynamic Routing. arXiv preprint arXiv:2502.02743.\n- 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.\n- Nguyen, Quang H., et al. (2024). \"MetaLLM: A High-performant and Cost-efficient Dynamic Framework for Wrapping LLMs.\" arXiv preprint arXiv:2407.10834 (2024).\n\n\n## Response to other comments\n> In Proposition 6.3, the term $\\zeta^{\\ast}$ was used without any definition.\n\nWe 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.", "claims_and_evidence": "I agree that the suggested algorithm PMCA significantly reduces the computational burden required to optimize the sampling distribution.\n\nHowever, the term “instance-dependent optimality” sounds considerably misleading. Algorithm 1 and Theorem 6.2 treat the recommendation rule $(\\zeta_t)_t$ as something given exogenously. Theorem 6.2 states that the sampling rule of PMCA achieves the asymptotic optimality for any given recommendation rule satisfying some regularity condition, without arguing the optimality of the recommendation rule.\n\nI believe that, conventionally, a pure exploration algorithm corresponds to a combination of sampling rule $\\pi$ and recommendation rule $\\xi$. It does not make sense to me that an algorithm can be said to be instance-optimal without having the recommendation rule specified.\n\nI guess that the authors are aware of that it is technically challenging to guarantee that both of sampling rule and recommendation rule safely converge to their optimal combination, say $(\\pi^*, \\zeta^*)$. In this work, some assumptions are being made for one component in order to guarantee convergence of the other component (e.g., Assumption 6.1 for Theorem 6.2 vs. $\\lambda_{min}(V_t) \\geq t^{-\\alpha}$ for Proposition 6.4). It was not discussed whether the assumptions can be satisfied simultaneously. Jedra & Proutiere (2020) had introduced the notion of forced exploration in order to break this mutual dependence. I believe the authors should explicitly discuss this gap.", "methods_and_evaluation_criteria": "The proposed algorithm PMCA looks completely sensible.", "theoretical_claims": "I carefully read the statements provided in the main body, but not the proofs in the appendix. I gently believe that the proofs are rigorous.", "experimental_designs_or_analyses": "- I believe the authors should report the computational time of the algorithms, because it is one of the main contributions of this paper.\n- I hope to see performance/speed of the algorithm with discretization.\n- In order to highlight the practical importance of PMCA, I would like to recommend the authors to find/test an application with many and densely distributed arms. Possibly, LLMs can help in direction (e.g., an arm corresponds a text's embedding).", "relation_to_broader_scientific_literature": "I am not sure how the key contributions can extend beyond the linear bandit literature.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Although I am skeptical about the claim “near optimal”, I do appreciate the ideas behind PMCA -- the use of PSGD method and the reparameterization trick. As suggested in Experimental Designs or Analyses, I believe that this algorithm has a great potential for the situations with many many arms.", "other_comments_or_suggestions": "- In Proposition 6.3, the term $\\zeta^*$ was used without any definition.\n- Please see Experimental Designs or Analyses for my suggestions on experiments.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hv9S2sB0Z5", "reviewer": "Reviewer_bZeb", "summary": "This paper investigates the problem of best arm identification (BAI) for Bayesian linear bandits, where the action set is assumed to be continuous. While existing investigations, e.g., [Jedra et. al.] establish optimal algorithms when the set of arms is finite, BAI for linear bandits under infinite actions is hitherto unexplored. This paper takes a step towards solving this problem, specifically, making the following key contributions:\n\n- It introduces an instance-dependent measure (which I will call problem complexity in the rest of the review), a counterpart of its finite-armed setting, and shows that the asymptotic posterior probability of error for any algorithm decays exponentially at a rate proportional to the problem complexity, and no larger (converse result).\n- It devises an algorithm which achieves this asymptotic error rate\n\nThere are some novel observations, which I would also like to highlight.\n\n- The paper introduces a reparameterization to solve the infinite-dimensional problem (in the probability space) to an equivalent problem in the matrix space, (and hence finite dimensional)\n- It introduces a projected gradient descent-based algorithm for BAI (which has been used in prior works), and the projection step is tackled using a novel connection with the approximate Caratheodary theorem.\n\nOverall, the paper takes a step towards solving BAI in the linear bandit setting with continuous arm sets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's thorough and insightful review. We will revise our manuscript based on your suggestions.\n\n## Posterior probability of misidentification\nAs 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.\n\n## Computational Complexity\nSince 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.\n\n## Subgradient\n$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.", "claims_and_evidence": "Yes, I think that the claims and evidences are coherent and sufficient.", "methods_and_evaluation_criteria": "Yes, the experiment settings make sense.", "theoretical_claims": "I did not have time to check the correctness of the proofs. I would be happy to take a look at any specific part, if any issue is raised.", "experimental_designs_or_analyses": "This is a theoretical paper; having said that, the experimental settings suffice to bolster theoretical claims.", "relation_to_broader_scientific_literature": "- BAI is an important problem in the bandit literature, with various practical applications including A/B testing, clinical trials, recommender systems, etc. Investigating the continuous-armed setting enhances our theoretical understanding of BAI. \n- Prior works establish optimal (fixed-confidence and fixed-budget) algorithms for linear bandits. Examples include [Jedra et. al.], [Vakili et. al.]. Most of these investigations consider a finite set of arms.\n- This paper positions itself as the one which extends BAI to continuous arm sets, which has not been sufficiently investigated.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I have already listed the strengths of this paper. A weakness of the paper is that the writing can be improved. Here are instances of typographical / grammatical inconsistencies:\n\n- **Line 95:** It should be $f(\\zeta)$\n- **Lines 161-162:** that estimates $\\zeta_t$ an $\\epsilon$-optimal arm ...\n-  **Lines 220-222:** the term $b_t$ is given as (an upper bound) the ...\n- **Lines 272-274:** similarly should be Similarly", "other_comments_or_suggestions": "Answered above.", "questions_for_authors": "I have the following questions for the authors:\n\n- the authors mention that \"..the posterior probability $P_t(\\zeta_t\\in\\mathcal{X}^*(\\epsilon))$ of misidentification is known to the learner...\". How does the learner know $\\mathcal{X}^*(\\epsilon)$? \n- What is the computational complexity of the reparameterization $\\pi_t \\mapsto \\mathbf{V}_t$, since it involves an expectation operator?\n- It seems that the expression of the sub-gradient in (6) is its gradient. How do the authors deal with the non-differentiability at points due to the inner supremum, say, in (4)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XdaJF3eLSj", "reviewer": "Reviewer_4oes", "summary": "This paper investigates a pure exploration problem with linear bandit feedback on continuous arm sets, aiming to identify an $\\varepsilon$-optimal arm with high probability. Previous approaches for continuous arm sets have employed instance-independent methods, due to technical challenges such as the infinite dimensionality of the space of probability measures, and the non-smoothness of the objective function. This paper designs a novel and tractable algorithm that addresses these challenges by using a reparametrization of the sampling distribution and projected subgradient descent. However, this approach introduces new challenges related to the projection and reconstruction of the distribution from the reparametrization. This paper addresses these by focusing on the connection to the approximate Caratheodory problem. Compared to the original optimization problem on the infinite-dimensional space, the proposed method is tractable, requiring only the solution of quadratic and fractional quadratic problems on the arm set. This paper also provides empirical results.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's thorough and insightful review. We will revise our manuscript based on your suggestions.\n## Readability\nWe 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).\n\n## Asymptotic optimality\nLemma 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.\n\n## More discussion on the challenges of generalization from the finite-armed setting\nWhile 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.\n\n\n## Computational Oracles\n### Quadratic Objective\nFor 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).\n\nIn 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.\n\n\n### Quadratic Fractional Objective\nLet $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.\n\n\n\n**References**\n\n- Boyd & Vandenberghe, Convex Optimization, Cambridge University Press, 2004", "claims_and_evidence": "The claims made in this paper are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense.", "theoretical_claims": "The theoretical results look reasonable, but I didn’t go through every proof.", "experimental_designs_or_analyses": "The experiments look reasonable.", "relation_to_broader_scientific_literature": "This paper is relevant to the literature.", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths:\n\n1. This paper proposes a tractable algorithm PMCA for Posterior error Minimization for a general Continuous Arm set based on the PSGD (projected subgradient descent method).\n2. This paper provides upper and lower bounds to show that the proposed algorithm is asymptotically optimal.\n3. The theoretical contribution of this paper is solid and interesting to the linear bandit community.\n4. Empirical results are provided to demonstrate the effectiveness of the proposed algorithm.\n\nWeaknesses:\n\n1. The readability of this paper should be improved. This paper is dense and hard to follow.\n2. This paper provides asymptotically optimal results. It seems that the practical significance of asymptotically optimal optimality is not strong, because the number of times we sample an option is finite and we care more about the optimality of the final output option in real-world applications. Can the asymptotic results in this paper provide any insight for the finite-time results/optimality?\n3. More discussion on the challenges of generalization from the finite-arm set to the continuous arm set is needed.\n4. Can you give more concrete examples for the computational oracles used in the proposed algorithm? For example, in what subproblems such computational oracles exist, and what are the corresponding concrete computational oracles (algorithms)?", "other_comments_or_suggestions": "Please see the weaknesses above.", "questions_for_authors": "Please see the weaknesses above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JmSFfW4lFT", "reviewer": "Reviewer_oQBX", "summary": "This paper studies $\\epsilon$-BAI for Bayesian linear bandits with Gaussian noise and Gaussian prior on compact and continuous arm sets. The metric of performance that is being minimized is the posterior probability of identifying an $\\epsilon$-optimal arm conditioned on the history of the observations. In particular, they consider instance-dependent asymptotic rate of convergence of this conditional posterior probability. This setting is challenging due to the infinite dimensionality of the space of policy (i.e., continuous distribution on the set of arms) and the non-smoothness of the objective. To alleviate these challenges, the authors re-parametrize the optimization problem with respect to the design matrix being induced by the sampling policy. As a consequence, they need to extract a policy from the optimized design matrix, which is done with projection and reconstruction following along the lines of the approximate Caratheodory problem. This requires solving quadratic and fractional quadratic optimization problem on the arm set. The authors provide an upper and lower bound on the conditional posterior probability of error. Moreover, they numerically compare their algorithm with other benchmarks on synthetic instances.\n\n**## update after rebuttal**\nIncluding the discussions will improve the paper in its revised version, hence I raised my score towards weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's thorough and insightful review and apologize for any statements that may have caused confusion.\n\n## Tractability of the algorithm\nFirst, 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.\n\n### Computation Oracles \nPlease refer to the response to Reviewer 4oes (we note that $q\\_{n}$ is defined in Line 317 (right)).  \n\n### Space complexity\nIn 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.\n\n## Instance-Dependent Optimality \nWe 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).\nTheorem 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.\n\n## Recommendation Rule\nWe 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.\n\n## PAC with respect to the unconditional probability\nAs 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. \n\nMoreover, 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.\n\n## Stopping Rule \nFor 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.\n\n\n## Lemma 4.1\nBoth 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.\n\n\n## Experiments\nWe 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}$. \n\n| $\\lambda\\_{V}$ | 0.0 | 1e-2 | 1e-1|\n| -- | -- | -- | -- |\n| $log (p\\_t)$ | -63.6 (1.4)|-64.1 (3.7)|-69.4 (2.3) |\n\n**References**\n- Garber & Hazan, Faster rates for the Frank-Wolfe method over strongly-convex sets, ICML 2015", "claims_and_evidence": "I. Tractable algorithm. \n\nWhile PCMA aims at solving more tractable optimization problems, the discussion on the tractability of PCMA is not fully convincing based on Sections 5.2 and 5.3. To the best of my understanding, PCMA has both a large computational and space cost. In particular, it would be valuable to have a more detailed discussion on the\n\nQuadratic Objective. What is the per-call computational and space cost of the quadratic objective used in Algorithm 2 ?  More importantly, the authors mention that “some problems can be solved in a polynomial time, and some problems are NP-hard”. Is the quadratic objective solvable in polynomial time for the problems considered in this paper, or is it NP-hard ? Even if the computational cost is polynomial, this oracle is being called a superlinear number of times at each iteration, i.e., $O(t^{u})$ with $u> 1$. Therefore, it seems to be a major computational bottleneck.\n\nQuadratic Fractional Objective. What is the per-iteration computational and space cost of the quadratic fractional objective (being called at each time step) ? What is the convergence rate, and how does it impact the choice of the “break” condition for this optimization procedure ? In particular, Appendix G.1 seems to suggest that at most 30 iterations are used, and refer to a quantity $q_n$ not defined in Section 5.3. \nAlgorithm 2. The memory requirement seems also to be superlinear with time. Is it possible to maintain a sparser approximation or the policy ?\nIf the discussion is not possible for general set of arms, then it would be enlightening to illustrate the discussion in some special cases such as (1) the unit sphere or (2) a spherical cap as considered in Section 7. \n\nBased on the small scale of the experiments and the lack of numerical computational costs, I am wondering whether PCMA can be truly considered as a tractable and practical algorithm.\n\nII. Instance-Dependent Optimality. \n\nWhile the authors claim instance-dependent optimality, their actual statement doesn’t reflect what is commonly referred to as “Instance-Dependent Optimality”. Therefore, it would be better to be more precise and discuss the difference with what is usually referred to as asymptotic optimality.\n\nTheorem 6.2 is a statement on the conditional posterior probability of misidentification, hence it doesn’t account for the randomness of the observations themselves.\n\nTheorem 6.2 assumes knowledge of the unknown characteristic time $\\tau^\\star$ in order to match the optimal rate. This is not a practical assumption, hence the theorem doesn’t hold for practical implementation\n\nIII. Recommendation Rule. \n\nThe authors state their result for a given stream of recommendation rule. However, to the best of my understanding, they have only theoretical guarantees (Section 6.3) and experiments (Section 7) for the greedy recommendation rule. The paper would gain in clarity by being specialized for the greedy recommendation rule. The greedy recommendation rule is by far the least computational expensive method, even though it is not asymptotically optimal on all instances.\n\nSection 4.3 glimpses at a more sophisticated notion of recommendation rule, i.e., the (instantaneous) furthest answer in Jourdan & Degenne (2022). However, this choice is far from being tractable. Even with the approximated algorithms from PCMA, it would require an additional outer optimization loop for a non-convex optimization problem. On top of the intractability of this procedure, it will probably be challenging to show that Equation (7) holds for this choice. \n\nIV. Stopping Rule.\n\nTo the best of my understanding, based on paragraph “Stopping Rule” in Section 3 and Section 4.2, the authors do not provide a clear and convincing discussion as regards the stopping rule. In particular, the authors should explicitly define what is the stopping rule that they are referring to, compare it to the literature on stopping rule, and explain whether this stopping rule has some theoretical guarantees.\n\nIn particular, while the authors only control the posterior probability conditioned on $\\mathcal F_t$, proving $(\\epsilon,\\delta)$-PAC also require controlling the randomness of the observations themselves, i.e., without the conditioning on $\\mathcal F_t$. Therefore, comparing their upper bound to $\\delta$ will not be enough to obtain an $(\\epsilon,\\delta)$-PAC stopping rule, both theoretically and empirically.\n\nThe upper bound proposed in Lemma 4.2 does not seem to be truly non-asymptotic. It is based on a discretization of the space (Lemma D.1) and the different terms do not seem to be explicit.", "methods_and_evaluation_criteria": "See “Experimental Designs Or Analyses” section for details on the empirical evaluation.", "theoretical_claims": "Lemma 4.1 seems unusual for the literature due to its dependency in $t$ on both sides of the equations. In particular, while both the sampling and the recommendation rules are not explicitly given and satisfy some general conditions, the upper and lower bounds are matching. This seems too good to be true. Could the authors provided more discussion ?\n\nLower bound from (2). While it could be independent of the sampling policy as in Theorem 2.1 in Li et al (2024) and Theorem 1 in Russo (2016), the analysis should most likely require more assumptions as regards the recommendation rule at each time. For example, a minimum requirement should be that the recommendation is $\\epsilon$-optimal for $\\mu_t$, which is satisfied by the greedy recommendation rule. It seems like this property is used in the equation 15 in Appendix F.2. Some statements should also be detailed more in the proof as they don’t seem to be trivial: (Line 756-757) “convergence of t in LHS of (18) is uniform [...] we can exchange lim and sup”.\n\nUpper bound from (3). This seems to be very surprising that it holds for general  sampling policy without assumptions on its asymptotic behavior. Intuitively, one should at least require convergence of the sampling policy. While this assumption is not made explicit in Lemma 4.1, it seems used in Appendix F.2: (Line 715) “we assume $(\\pi_t)$ converges,”.", "experimental_designs_or_analyses": "The empirical metric of performance used in the experiments appears to be unusual, and lack details on its practical implementation. Instead of considering the empirical proportion of error as a function of time, the authors consider the conditional posterior probability of misidentification. Since it is hard to compute, they consider as proxy the upper bound from Lemma 4.2, yet dropping the terms $a_t$ and $b_t$. Due to the optimization over the continuous set of arms, it is not clear how $p_t$ is actually computed numerically. Are the authors using a discretization of the space, e.g., the one from Lemma D.1 ? Even for a discrete set, it is not clear how each term is numerically computed. Is it based on the Gaussian cumulative distribution discussed at the end of Section 4.2.\n\n\nWhile promising, the experimental results provided in Section 7 and Appendix G seem to be preliminary. A more extensive empirical evaluation would be appreciated. In particular, the empirical claims would be strengthened by having:\n- More than one hundred rounds for each run, and more than ten runs for each instance.\n- Plots of the empirical proportion of error as a function of time.\n- Plots of the actual computational cost (in terms of CPU time) for the proposed algorithms to highlight that it is tractable.\n- Bayesian experiments in order to actually match the Bayesian setting considered in this paper.\n- Number of samples needed for the approximated upper bound (from Lemma 4.2) on the conditional posterior probability of error to be lower than $\\delta$.\n- Ablation studies to better understand the impact of the hyper-parameter of the algorithm. In particular, the experiments use $\\lambda_{V} = 0$, yet the theory require $\\lambda_{V}$ to depend on the unknown characteristic time (Theorem 6.2 and Propostion 6.3).", "relation_to_broader_scientific_literature": "The authors wrote a wrong statement on the literature: \n“Jedra & Proutiere (2020) [...] showed that an optimal sampling policy is the round-robin manner using the orthonormal basis.”\nJedra & Proutiere (2020) show that round-robin sampling yields an algorithm whose sample complexity is order-wise optimal. Order-wise means that it has the same scaling as the optimal characteristic time, however the lower and upper bound are not matching asymptotically. Therefore, round-robin is not an optimal sampling policy, only one that is “not too bad”.", "essential_references_not_discussed": "To the best of my knowledge, most relevant literature is discussed. Nevertheless, more details could be added in order to compare the obtained results for continuous set of arms with the ones known for discrete set of arms.", "other_strengths_and_weaknesses": "I. Lack of clarity. \n\nIn general, the paper would gain in clarity by considering a specific recommendation rule instead of studying a general formula under some assumptions. This obfuscates the discussion on the main challenges of the continuous set of arms. It would be valuable to clearly state what are the theoretical challenges in proving Theorem 6.2. Is a direct extension of the analysis for discrete sets ?  Moreover, the paper would benefit from more examples to illustrate the bounds and the algorithms, e.g. special case of the unit sphere. Currently, it is difficult to parse everything in all its generality.\n\nII. Confusing notation for the conditional posterior probability of misidentification. \n\nTo the best of my understanding, the only randomness in the conditional posterior probability of misidentification is with respect to $f_t \\sim P_t$ since $\\zeta_t$ is given. The dependency in $f_t$ is not made explicit and seems hidden in the notation $\\mathcal X^*(\\epsilon)$ which should depend on $f_t$ and not on $f$ fixed at initialization.", "other_comments_or_suggestions": "Equation (16) in Appendix F.2 lacks a square on $r_t$ in the first term of the right hand side.", "questions_for_authors": "Several questions have been asked in the previous sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper investigates the problem of identifying an $\epsilon$-optimal arm in linear bandits with a continuous action space. The analysis is conducted within a Bayesian framework, assuming a Gaussian prior over the unknown parameter. The objective is to minimize the posterior probability of error.

Due to the continuous nature of the action space, instance-specific analysis poses significant challenges. To address this, the authors employ a reparametrization of the sampling distribution combined with projected subgradient descent. They introduce PMCA, an algorithm that, for a given recommendation rule, provably achieves asymptotic optimality.

The contributions are substantial, as acknowledged by all reviewers. However, there are several areas for improvement, as outlined in the reviews and the authors’ rebuttal. In particular:

1. The authors should provide a more detailed discussion of the computational and memory complexities of PMCA, and report these metrics in the numerical experiments.

2. The use of the term instance-optimality may be misleading, as pointed out by Reviewers oQBX and huXi. This notion should be clarified.

3. The presentation could benefit from simplification and improved clarity. Reviewers have suggested, for instance, focusing on the greedy recommendation rule to enhance readability.

4. The computational oracles used by the algorithm should be exemplified and discussed in greater detail.

5. A clear and convincing discussion of the stopping rule is needed to complete the methodological picture.
Decision: Accept (poster)