Pure Exploration in Kernel and Neural Bandits
Authors: Yinglun Zhu
Dongruo Zhou
Ruoxi Jiang
Quanquan Gu
Rebecca Willett
Robert D Nowak
Venue: NeurIPS 2021 Poster (2021)
Keywords: bandits
pure exploration
reproducible kernel Hilbert space
neural network

Abstract: We study pure exploration in bandits, where the dimension of the feature representation can be much larger than the number of arms. To overcome the curse of dimensionality, we propose to adaptively embed the feature representation of each arm into a lower-dimensional space and carefully deal with the induced model misspecifications. Our approach is conceptually very different from existing works that can either only handle low-dimensional linear bandits or passively deal with model misspecifications. We showcase the application of our approach to two pure exploration settings that were previously under-studied: (1) the reward function belongs to a possibly infinite-dimensional Reproducing Kernel Hilbert Space, and (2) the reward function is nonlinear and can be approximated by neural networks. Our main results provide sample complexity guarantees that only depend on the effective dimension of the feature spaces in the kernel or neural representations. Extensive experiments conducted on both synthetic and real-world datasets demonstrate the efficacy of our methods.

Pure Exploration in Kernel and Neural Bandits
Yinglun Zhu"
Dongruo Zhou"
Department of Computer Sciences University of Wisconsin-Madison
Department of Computer Science University of California, Los Angeles
Madison, WT 53706
Los Angeles, CA 90095 drzhou@cs. wwwa.clla...ooooo... edu
yinglunêcs, .duu
Ruoxi Jiang'
Quanquan Gu Department Computer Science University of California, Los Angeles
Department of Computer Science
University of Chicago Chicago, IL 60637
Los Angeles, CA 90095 qguêcs.ucla www.u.llllee..
roxie62@uchicago.. edu
Rebecca Willett
Department of Statistics and Computer Science
University of Chicago Chicago, IL 60637
wi willett@uchicago. edu
Robert Nowak
Department of Electrical and Computer Engincering University of Dusconsin-Madison
Madison, WI 53706 rdnowak@wisc.cm edu
Abstract
We study pure exploration in bandits, where the dimension of the feature repre- sentation can be much larger than the number arms. To overcome the curse of dimensionality, each arm into lower-dimensional space and carefully deal with the induced model misspecifications. Our approach is conceptually very different from existing works that can either only handle low-dimensional linear bandits or passively deal with model misspecifications. We showcase the application of our approach two pure exploration settings that were previously under-studied: (1) the reward function belongs possibly infiiteediimensiona. Reproducing Kernel Hilbert Space, and (2) the reward function is nonlinear and can be approximated by neu- networks. Our main results provide sample complexity guarantees that only depend on the effective dimension of the feature spaces in the kernel or neural representations. Extensive experiments conducted both synthetic and real-world datasets demonstrate the efficacy of our methods.
propose to adaptively embed the feature representation of
Introduction
Pure exploration in bandits [11, 12, 6] has been extensively studied in machine learning. Consider a set of arms, where each arm is associated with an unknown reward distribution. The goal is to
EEqul contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

approximately identify the optimal arm using as few samples as possible. Applications of bandit pure exploration range from medical domains [3] online content recommendation [40].
Despite the popularity of bandit pure exploration, it was previously mainly studied in two relatively restrictive setrings: (1) the standard multi-armed bandit setting [22, 19, 9, 18], where the expected rewards among arms are completely unrelated to each other, and (2) the (generalized) linear bandit setting [38, 13, 10, 26]. where the expected rewards are assumed be linearly parameterized by some unknown weight vector. The standard multi-armed bandit setting fails to deal with large arm sets, and the linear bandit setting suffers from both model misspecifications (due to its simplified linear form) and the curse of dimensionality in the high-dimension setting. Pure exploration is also studied in continuous spaces. However, guarantees therein scale exponentially with dimension [31, 4].
In this paper, we generalize bandit pure exploration to the nonlinear and high-ddmensiioal settings. More specifically, we study the following two settings: (1) the rewards of arms are parameterized by function belonging
Reproducing Kernel Hilbert Space (RKHS), and (2) the rewards of arms nonlinear functions that can be approximated by an overparameterized neural network. Problems in these two settings are often high-dimensional in nature. To overcome the curse of dimensionality, we propose to adaptively embed each arm's 's feature representation in a lower-dimensional space and carefully deal with the induced misspecifications. Note that our approach is conceptually very different from all existing work dealing with model misspecifications: they assume the existence of misspecifications and address in the original space (thus dealing with model misspecifications in a passive way) [28, 7]. On the other hand, we deliberately induce (acceptable) misspecifications to embed arms into lower-dimensional spaces and thus overcome the curse of dimensionality.
1.1 Contribution and Outline
We make the following main contributions:
In Section 3, we introduce the idea of adaptive embedding to avoid the curse of dimensionality. The induced model misspecifications are carefully handled, which is novel in the bandit pure exploration setting. The sample complexity is theoretically analyzed and relate the instance- dependent sample complexity to the complexity of a closely-related linear bandit problem without model misspecification. As by-product, our algorithm can also be applied to constrained high- dimensional linear bandit pure exploration to reduce sample complexity.
In Scction 4, we specialize the adaptive embedding scheme to pure exploration in an RKHS. We construct feature mappings from eigenfunctions and eigenvalues of the associated kernel. The effective dimension of the kernel is analyzed, and we provide sample complexity guarantees in terms of the eigenvalue decay of the associated kernel. We rely a known kernel in this setting.
In Section 5, we further extend our adaptive embedding scheme to pure exploration with general nonlinear reward function and model the reward function with an over-paramen preammaraeteri neural network. Sample complexity guarantees are provided with respect to the eigenvalue decay of the associated Neural Tangent Kernel. To the best of our knowledge, this provides the first theoretically founded pure exploration algorithm with a neural network approximation.
In Section 6, we conduct extensive experiments on both synthetic and real-world datesets to confirm the efficacy of our proposed algorithms. We conclude our paper in Section with open problems.
1.2 Related Work
The bandit pure exploration problem has a long history, dating back to the seminal work by Bechhofer [5], Paulson et al. [32]. One classical objective of pure exploration is Best Arm Identification (BAI), where the goal is to identify the best arm using as few samples as possible [22, 19, 9, 15]. To make it applicable to large action space, the BAI problem is also extensively studied the good arm identification problem, where the goal is to identify an c-optimal arm [11, 12, 20, 21, 34, 23, 30].
The pure exploration problem in linear bandits is initially analyzed in Soare et al. [38], where optimal experimental design [27] is applied to guide the allocation of samples. Other approaches dealing with linear bandits, with various sample complexity guarantees, include adaptive sampling [45] and an approach called track-and-stop [10]. Constrained linear bandit pure exploration is also commonly studied with additional assumptions on the reward parameters [41, 10]. We note that the

---

track-and-stop approach only achieves optimal pustance-dependee sample complexity in the regime where the confidence parameter approaches 0, but fails do so in the moderate confidence regime. Fiez et al. [13] propose an climination-barn algorithm (with optimal design) that achieves (nearly) instance-dependen sample complexity. such algorithm further generalized to the combinatorial bandit setting [24].
Learning with model misspecifications was recently introduced in bandit learning, with the primary emphasis placed on the regret minimization problem [16. 28, 14]. A very recent independent work studies pure exploration in kernel bandits with misspecifications [7]: both their and our algorithms follow the framework of RAGE [13] and draw inspiration from [28]. Camilleri et al. [7] propose a robust estimator that works in nigh-dimensional spaces and also explore the project-then-rotee through regularized least squares. Our algorithms adaptively embed actions into lower dimensional spaces according to some error tolerances (different embeddings from round to round); our rounding and elimination steps are thus computed only with respect to lower-dimensionss embeddings. We additionally study the pure exploration problem with an overparameterized neural network. As mentioned before, our approach is also conceptually different from existing ones: rather than passively dealing with model misspecifications in its original representation, we deliberately and adaptively embed arms into a lower-dimensional space to avoid the curse of dimensionality; the induced model misspecification are also carefully dealt with in our algorithms.
idea
2 Problem setting
We introduce the general setting and notations for pure exploration in bandits. Consider a set of arms X C RDD where the number of arms | K is possibly very large. We use an unknown function h: X' + [-1, 1] to represent the true reward of each arm. A noisy feedback h(x) + & is observed after each sample arm æ, where the noise & is assumed be l-sub-Gaussian. The learner allowed to allocate her samples based on previously collected information, and the goal is to approximately identify an approximately optimal arm using as few samples as possible. Let I. = arg max xxx h(x)) denote the optimal arm among X We aim at developing (c, 6)-PAC guarantees: for any 5 E (0. 1), with probability least 1 1-& the algorithm outputs an e-optimal arm such that h(t) 2 h(x.) using finite number of samples. The performance of the algorithm is measured by its sample complexity, i.e., the number of samples pulled before it stops and recommends a candidate arm.
Notations. We define A. = -((x.) )- Mxx) as the sub-optimality gap of arm æ. We use the notations Se == {or E X A. < 2-2 (with S = X). We consider feature mappings of the form (b(+)) : X + Rd, and define (x)(x) = [wa(x) x E X). We use Ax = {A E R|*) Evex Au =
1, Am 2 0} to denote the (|A*) di-dimension probability simplex over arms in X: and set
T.2 We use ||>||| = Væ Aæ to represent the Mahalanobis norm. We also detine (VV)- {u - v' v. v' E V} for any set V. For matrix H E IR [X X1, we use (x, d') to denote the entry of H which locates at row æ and column x'.
(A) = Emex ta )
3 Bandit pure exploration with adaptive embedding
We introduce the idea of bandit pure exploration with adaptive embedding, which can be viewed as an approach that actively trades off sample complexity with accuracy guarantees: we adaptively embed the feature representation into conduct pure exploration with misspecified linear bandits. The embedding dimensions are carefully selected so that we can identify an e-optimal arm.
spaces to avoid the curse of dimensionality. and
We formalize the idea as follows. For any d E N, we assume the existence of feature mapping ahs X + d and a unknown reward vector 0g E IRd such that, for any æ E X,
h(x:) = (4ba (x), 0z) + (ar),
where nz( represents the induced approximation error on arm x with respect to the low-dimensional embedding (ba(-). Without loss of generality, we assume that the action set X' is rich enough so that (2) spans IRd for d considered in this paper. Otherwise, one can always project feature
A generalized inversion is used for singular matrices. We refer to Appendix A.I for detailed discussion.
3

---

representations (2)) into an even lower-dimension space without losing information in the linear component.
We use 7 - I to represent the misspecification level: an upper bound of the induced approximation error across all arms, i.e., maxgex|\a(a))
(dd). We define g () = (1+ () infXeAx (upye)( I (A) which represents the optimal value of a transductive
design among embeddings in Rdd We define rdd) = (16 + g(d F(d), which quantifies the sub-optimality gap of the identified arm in the worst case. One can easily show y(d) S ((((d) through Kiefer- Wolfowitz theorem [27].
Remark 1. We believe such optimality guarantees are un-improvable in general. In fact, a hard in- stance is constructed in [28] showing that, even with deterministic feedback, identifying a (d) optimal arm requires sample complexity exponential on d. On the other side, identifying a ( optimal only requires sample complexity polynomially in d. Such sharp trade-off' between optimality and sample complexity motivates our definition of (dd) (and our sample complexities are polynomially in d).
We assume the knowledge of both the feature mapping 4ba(-) and the error function 7--). This assumption is mild since one can explicitly construct/analyze (ba(-) and 7-) in many cases (as discussed in Section 3.2, Section 4 and Section 5). We further assume that 7(d) can be made arbitrarily small for large enough d. Such assumption trivially holds if the rewards are perfectly explained for d large enough, i.e., 7(d) = O. We now define the effective dimension with respect to (d) (induced from feature mapping (a(-)) as follows.
Definition 1. For any c > O, we define the effective dimension as dcr(c) == minfd 2 1: yd)) S c).
In general, the effective dimension dett (c) captures the smallest dimension one needs to explore in order to identify e-optimal arm. Similar notions have been previously used in regret minimization settings [42, 43]. One can easily see that deft (Ga) S ((2) as long as 6 2 C2.
3.1 Algorithm and analysis
Algorithm I follows the framework of RAGE [13] to eliminate arms with sub-optimality gap 2 O(2-*) the k-th iteration. It runs for n = ((log(1/e) ()))) iterations and identifies an e-optimal arm. We use optimal experimental design to select arms for faster climination. For any fixed design À E Ax, with N ra(() samples and an approximation factor Ç (with default value Ç E [1/10, 1/4), the rounding procedure in Rd i.e., ROUND(A, N, d, {), outputs discrete allocation { 22, 2.,) satisfying N,d,
max
| | (EL, (mm S (1 + ()
max (E)(())))))
|1 (1yll 1A.
(1)
(()()
Efficient rounding procedures exist with ra(5) = + [33] or ra(() = 180d [1. 13). We refer reads to [13, 33, I] for detailed rounding algorithms and the associated computational complexities.
C²
Unlike RAGE that directly works in the original high-dimensional space, Algorithm I adaptively embeds arms into lower-dimensional spaces and carefully deals with the induced misspecifications. More specifically, the embedding dimension de is selected as the smallest dimension such that the induced error term é is well controlled, i.c., c I 0(2-*), *) The embedding is more aggressive at initial iterations due to larger error tolerance; The embedding dimension selected at the last iteration is (roughly) dent (c) to identify an e-optimal arm. The number of samples required for each iteration N with respect an experimental design in the -iver-dimeniional space after embedding. The ROUND procedure also becomes more efficient due to the embedding. Before stating our main theorem, we introduce the following complexity measure [38, 13, 10], which quantifies the hardness of the pure exploration problem (with respect to mapping vba(-)).
[1.ba(xr.) (b)( Au, (2)-
pā(e)=
inf sup =
XEAx
max(h(x..) - h)x),c}²
Theorem 1. With probability of at least - 6, Algorithm 1 correctly oulputs an e-optimal arm with sample complexity upper bounded by
(2/e))
640
Σ
((KP2 (2--) log(k)) + (ra + +1)) s Ö(dea(e) maxxAAmin+ of 2),
K=

---

Algorithm Arm Elimination with Adaptive Embedding and Induced Misspecification
Input: Action set X, confidence parameter ó, accuracy parameter and rounding approximation factor Ç.
Set
(2/e)] and S X.
2: for k = 1....... do
3: Set dg 8/k², d2 = deft 1..... 2 2-*)
4: Select feature representation ddd, (-), and calculate the induced misspecification level 7(dx).
Set rd, (() ( ) as the number of samples needed for ROUND in R
5: Set d and тy be the design and the value of the following optimization problem
inf sup MEM( (Sx)
I1yll (A)-1-
xEAx
6: Set c (7(()) +
Tke and N₂ = max ( 112 c2) 22 + () log( log([Se|2 (5(2 rdx (S)).
7:
Get {ar1, 222 ..... 21 NNN, ROUND Au. Nu, Ne, d), ().
8:
Pull arms { 22..., ,N,, and receive rewards (yi,.... ,NN. J.
9: Set 02 Ax bR. where As = Σn aa (a,)) (z:) and by Em shds (x:))
10:
Eliminate arms with respect to criteria
Sx+1 S5 { E Sz Eoo such that (wa. (xx) whe (2:) 2 wN wh(Waa (x0') - -bo (x))),
3z
where W/ (x(y) (y) = eu + lllll,, 222 2 (o2x)
11: end for Output: Output any arm in S,+1-
where de dott k-k) S dett(e) since 4 4 2 e when k < [log2(2/e)].
The rounding term ra(ς) commonly appears in the sample complexity of linear bandits [13, 24]; and our rounding term with respect to the lover-dimensional space after embedding. which only scales with de rather than the ambient dimension. To further interpret the complexity, we define another complexity measure closely related linear bandit problem in the low-dimensional space and without model misspecifications.
[[/,(x.)) - 2 (2)
(a(e)= = inf
sup
ΛEΛx (=.) (bbu(.)) - v/)(2)),,.)))))));,))))))))))) 02),
where ( (x)), 0z) on the denominator represents the sub-optimality gap characterized by the linear component rather than the true sub-optimality gap h(x, h((:). The relation between p² (c) and p" (c) discussed as follows.
Proposition 1. Suppose max (h(x) (bba(x), 0a)l S 7d)). For any 2 7(d), we have Pā(c) (c)(c). When ((d) Amin/2 (o( represents the sample complexity of a closely-related linear bandit problem without model misspecifications, i.e., h(x) (ıba(x), 0a).
When ((d) < Amin/2. our sample complexity upper bound is relevant to the sample complexity of closely-related linear bandit problems without model misspecifications in lower- dimensional spaces. In fact, (0) log(1/2.48) ) is the lower bound of the corresponding linear bandit problem in Rd [38. 13, 10].
Remark 2.
Remark Although the misspecification levels are generally known for situations considered in this paper, we also provide an algorithm that deals with unknown misspecification levels in Appendix D. Similar sample complexity guarantees are provided, but only in an unverifiably way (due to unknown misspecification levels): the algorithm starts output e-good arms after N samples, yet it doesn't 'ttstt know when to stop. We refer readers to [23] details on the unverifiable sample complexity.
3.2 Application to high-dimensional linear bandits
We apply the idea adaptive embedding to high-dimensional linear bandits. We consider lincar bandit problem of the form h X0, where X E I8 KDD and the i-th row of X represents the
5

---

feature vector of arm 2;. We assume that 110.122 S C, which is commonly studied as the constrained linear bandit problem [41, 10].
Let X = UEVT be the singular value decomposition (SVD) of X, with singular values σ1 2 02 2 o, 0 for some r S minn(K K D). Let uis denote the (i,j)-th entry of matrix U and u. denote the i-th column of U (similar notations for V). We have
h x0. = -UV 0
Σ J. v.
Σ (=d+1
Σ o. v + 17,
where |111100 S Ci o.
Ur. As a result, for any d S T, we can construct the feature map- ping (),( = (olui,1...,,auuu
E Rd such that h(x;)) = (sba(z,), 0.) + n7x,), where O, [VT0] [1:d]] E Rd is the associated reward parameter." The upper bound of the induced misspecification can be expressed as idd) CE Ts. which allows us to calculate yd). We can then apply Algorithm to identify an e-optimal arm. A high- high-dimensional linear bandit instance is provided in Appendix B.3 showing that: Algorithm I takes ( samples to identify an e-optimal arm, while the sample complexity upper bound of RAGE scales as Ō(D/e).
4 Pure exploration in RKHS
We consider kernel function K. 2 x 2 + R over a compact set Z; we assume the kernel function satisfies condition stated in the Mercer's Theorem (see Appendix E.I) and has eigenvalues decay fast enough (see Assumption 1). Let H be the Reproducing Kernel Hilbert Space (RKHS) induced from K.. We assume X C Z and the true reward of any arm æ X' is given by an unknown function h E H. such that |[bliæ < 1.
Let {0)),21 and (1z}5=1 be sequences of eigenfunctions and non-negative eigenvalues associated with kernel K. A corollary of Mercer's 's theorem shows that any h E H. can be written in the form of h(-) = و (-) for some [0 l ((N) such that Σド= 03/1z < oc. We also have || = ンラ= 02/11; prj Although functions in RKHS are non-linear in nature, we now can represent them in terms of an infinitedimmensional linear function. We construct feature mappings for the embedding next.
For any X, we have h(x) Σj= (x6 = Σラ vis (1))(())))) Let C2 sup 52 121 (z)) Since Σド= 09/1g = |11 S is bounded, for any E N, we define feature mapping (b((x)= = (z), [Padu Rd such that
h(x) = (0a. (z))))) + na(x),
where 0₂ =
0,/ /Pa] E p. and (na())) (z) s 7(d)= = Coy C En>etii. We remark here that the constant C. is calculable and usually mild, e.g., Co for (y(x) sin((2j - 1)xx/2).
We can then construct (d) and (c) as in Section and specialize Algorithm 1 to the kernel setting. Both (d) and deft (+) depend on eigenvalues of the associated kernel. Fortunately, fast eigenvalue decay are satisfied by most kernel functions, e.g., Gaussian kernel. We quantify such properties through the following assumption.
Assumption We consider kernels with the following eigenvalue decay with some absolute constants C₁ and B.
Kernel KC is said to have (Ck, B) -polynoola eigenvalue decay (with 3 > 3/2) if 14j S C.. for all j 2
'We note that the embeddings and associated quantities also be constructed the fly with respect to the set of uneliminated arms.
"With a known kernel, the sequence of eigenfunctions and eigenvalues can be analytically calculated or numeriaclly approximated [36, 35J. We assume the knowledge of eigenfunctions and eigenvalues in this paper.

---

2. Kernel K. is said to have (Ck: expponenni eigenvalue decay (with 3 > 0) is S Cae Ai for all j 2
Theorem 2. Suppose Assumption holds. For any e >> 0, the following statements hold when we specialize Algorithm the kernel setting.
1. Suppose K. has (Ck: 3)-polynooial eigenvalue decay. We have den(e) O(e-2 -2(22--3)) and the sample complexity of identifying an e-optimal arm is upper bounded by Ö(E ((-211B)))) max e) 2)
2. Suppose K. has (Ck, -e=eoonnxptalliial eigenvalue decay. We have den (c) S Ollo((//e); and the sample complexity of identifying c-optimal arm is upper bounded by O (max(Amins< c} -2
Remark 4. Our sample complexity guarantees directly related the eigenvalue decay of the underlying kernel function, rather than the empirical kernel matrix as studied in previous works 17, 42]. Although one can also provide an instance dependent bound in Theorem I, the worst-case sample complexity bound in Theorem 2 provides insightful characterizations of the sample complexity in terms of eigenvalue decay. One should notice that with exponential eigenvalue decay, the sample complexity ((c-3) essentially matches, up to logarithmic factors, the complexity of distinguishing two-armed bandit up to accuracy e [25].
5 Pure exploration with neural networks
In this section present neural network-based pure exploration algorithm in Algorithm 2. Our algorithm is inspired by the recently proposed neural bandits algorithms for regret minimization [47, 46]. At the core of our algorithm to use neural network fa: 0) learn the unknown reward function h. Specifically, following [8, 47], we consider a fully connected neural network f(x; 0)
with depth L 2 2
f(x; Vm (WL-0(..... (W--Oo (Wix)))
where (x) := max(x, 0) is the ReLU activation function, W1 E R W. E Rixm and for
2 < i < L - 1, W; E mm Moreover, we denote 0 = where p = + md + (L is the number of all the network parameters. We use g( 0) Val( 0) to denote the gradient of the neural network output with respect to the weights.
,..., vec WT, (e)) E RP,
In detail, at k-th iteration, Algorithm 2 firstly applies its current gradient mapping gæ;; 0 over the whole action set X' and obtains the collection of gradients G' E g|X|Xp, Then Algorithm 2 does SVD over G and constructs dy dimensional feature mapping 2hd., which can be regarded as the projection of the gradient feature mapping g2: x to the most informative dy -d-imennsionll eigenspace. Here we choose dę such that the summation of the eigenvalues of the remaining eigenspace be upper bounded by some error Algorithm 2 then computes the optimal design A over ( and pulls arms [.t,,..,, N, based on both the design A and the total number of allocations Ng- Finally, Algorithm 2 trains new neural network (ar; Qx)) using gradient descent starting from the initial parameter Op (details are deferred to Appendix F), then eliminates the arms æ in the current arm set S. which are sub-optimal with respect to the neural network function value f f(x; 0k)
The main difference between Algorithm 2 and its RKHS counterpart is follows. Unlike Algorithm I which works on known feature mappings tha (derived from a known kernel IC), Algorithm 2 does not have information about the feature mapping, and thus it constructs the feature mapping from the raw high-dimensional up-to-date gradient mapping g 1) The feature mapping is constructed with respect to a trained neural work, which leverages the great representation power of neural networks. This makes Algorithm 2 a more general and flexible algorithm than Algorithm 1.
Now we present the main theorem of Algorithm 2. Let H be the Neural Tangent Kernel [17 gram matrix over all arms X' (the detailed definition of H is deferred to Appendix F). We define the effective dimension for the neural version as below. The definition is similar to Definition I.
7

---

Algorithm 2 Neural Arm Elimination
Input: Action set X. initial parameter 9,, neural network f(;; 0), gradient mapping ( 0), width of the matrix m. parameter of the number of allocations A, approximation parameter ç. regularization parameter error parameter é, e, confidence level 65 6/(8k2)
1: Set S = X.
2: for k= 1,,,, 1,....... do
3: Construct the truncated feature representation (2' based on gradient mapping g 0x-1).
In detail, let G' R be the collection of gradients such that
= (x( 0x 0x-1) :....: x 0k-1) 11/mm E X
(3)
Let V be the SVD of G. where U
(uaz) E - Σ
(diag(ei...., exx)), Ri xp, V E RRXx, Get du = min{d E [|ll]] E 6
S E).
and set tha (z:) (e1 ed, Ui,d2) R
4: Set d and The be the experimental design and the value of the following optimization problem
inf sup I1all (2)-1-
ΛEλx yE) (Sa)
5:
Set N₂ = max {22* A(1 + () log (1x1/6k)) ra, (C)}.
6: Get f 22, NN. ROUND dl. N₁, C).
7:
,,N,.....,N..... Using Js step 7i Step size gradient descent to optimize the following loss function to obtain Oz.
Pull arms (æ), 22,..... N2 } and receive rewards (. UN,, ).
8:
N2
02 arg min L(0)
(2,0))-))²+ -)
ma 10 0.122-
(5)
2
1=1
9:
Set A al + Ei=1 uh (2 (x)) and eliminate arms with respect to criteria
SK41 Sz fnr E Sx 7x such that (xx;02)) f(x; 0x) 2 2 2 /8 3e 38/8).
10: end for Output: Output any arm in S,+11
Definition 2 (Neural version). For any e we define the effective dimension as dett min(d E [| Ei (H) S e}. where (HH
) is the i-th eigenvalue of H.
Next, we make standard assumptions for the initialization of neural networks and the arms E X. Assumption 2 ([47)). There exists Xo such that H > An For any x E X, the arm satisfies ||æ||| 1 and that its j-th coordinate is identical to its + d/2-th coordinate. Meanwhile, the initial parameter Oo [vec( W1) "T.T".... ...., vec (ec TT is initialized as follows: for 1 S S L- Wi is set to
W where each entry of W is generated independently from (0, 4/m); WL is set
to (w)
w ), where each entry of w generated independently from N N 2/m).
We now present our main theorem for pure exploration with neural network approximation. The formal version of our theorem is deferred to Appendix F.
Theorem (Informal). Under Assumption 2, with proper selection of parameters at, E, A, mb. Jr. then when m = poly([XX) L, >n log([X)/6,)) (6x)), Ng, a1E-)), with probability at least only includes satisfying å I c, and the total sample complexity of Algorithm 2 is bounded by
Sk+1
N O=Ō (1+()d((//111)) ((an((/111)(()) =0(ds((/1x1)) 2).
Remark 5. For the case where the effective dimension can be well bounded, e.g., dea (2/ ((1)) 0log((x1/22),, Theorem 7 suggests that Algorithm 2 is able to identify an c-optimal arm within Ó(c-2) samples. That suggests that our neurul network- based algorithm is efficient without con- structing a low-dimensional linear approximation of h in prior, like the previous linear or RKHS approaches.
8

---

Experiments
We conduct four experiments on synthetic and real-world datasets. We specialize our embedding idea to the neural, kernel, and linear regimes, and denote the algorithms as NeuralEmbedding (Algorithm 2), KernelEmbedding (Algorithm with Gaussian kernel), and LinearEmbedding (Algorithm 1 with linear representation). respectively. We compare our algorithms with two baselines: RAGE and ActionElim. RAGE [13] conducts pure exploration in linear bandits and ActionElim [18, 11] ignores all feature representations. The (empirical) sample complexity of each algorithm calculated as the number of samples needed so that the uneliminated set contains only e-optimal arms. Unsuccessful runs, i.e., those terminate with non-e-optimal arms, are reported as failures. In our experiments, we set 0.1 and 0.05. All results are averaged over 50 runs.'
10
Sample Complexity
10¹
sample complexity
10
20
10²
10a
10a
Embedding (Ours)
10a
Neural Embedding (Ours)
Kernel Embedding
Action Elim
Kernel Embedding (Ours)
Action Eilm
10a
Linear Embedding (Ours)
Linear Embedding (Ours)
10
250
500
750
1000
10
15
20
25
30
Numbers
Dimension
(a)
(b)
Figure 1: Experiments on synthetic datasets. (a) linear reward function with D 20; (b) nonlinear reward function with K = 200.
Synthetic datasets. We first generate the feature matrix X X EEE R where X is constructed as a rank-2 matrix and perturbation matrix with tiny spectral norm (See Appendix G for details). Each row of X represents the feature representation of an arm, and those features can be grouped into two clusters with equal size. the case with linear rewards, we let O, equal to the first row of X. For nonlinear rewards, the reward of each arm is set as the 2-norm of its feature representation. We vary the number of arms K and the ambient dimension D in our experiments.
Fig. shows experimental results on synthetic datasets. All algorithms successfully identify e- optimal arms with zero empirical failure probability (due to the simplicity of the datasets). In terms of sample complexity, geuralEmbddding outperforms all other algorithms in most cases, and KernelEmbedding and LinearEmbedding significantly outperform RAGE and Action Elim. The sample complexities of NeuralEmbeddingg KernelEmbedding affected when increasing number of arms dimensions since they first identify the important subspace and then conduct elimination. On the other side, the sample complexity of ActionElim gets larger with increasing number of arms and the sample complexity of RAGE gets larger with increasing dimensions.
and LinearEmbedding are not
MNIST dataset. The MNIST dataset [29] contains waidt-ritten digits from 0 to 9. We view each digit as an arm, and set their rewards according to the confusion matrix of a trained classifier. Digit 7 chosen the optimal arm with reward 1; the reward of digits 1, 2 and 9 are set to be 0.8, and all other digits have reward 0.5. each experiment, we randomly draw 200 samples (20 samples each digit) from the dataset. We project the raw feature matrix X E 2000x 784 into nower-dimensiooal space X 200xx00 so that it becomes full rank (but without losing any information) and feasible for RAGE. Our goal is to correctly identify digit 7.
Yahoo dataset. The Yahoo! User Click Log Dataset R6A contains users' click-through records. Each record consists of 36-dimensional feature representation (obtained from an outer product), and binary outcome stating whether or a user clicked on the article. We view each record as
$ algorithms are dimination-styles for fair comparison. Other implementation details are deferred to Appendix G. "httpss:/wwbbsea sandbox, wawdbox.aaho.cccomm com

---

10
Sample Complexity
Sample Complexity
10a
Naural
Kamel Embedding (ours)
Linear Embedding (ours)
RAGE
Action Elim
Neural Embeddiing (Burs)
Karnel
Lineor Embedding (ours)
RAGE
Action Elim
Embedcing (ours)
Embedding (ours)
(a) MNIST
Yahoo
Figure 2: Experiments on real-world datasets. The mean sample complexity is represented by black star. The mean sample complexities of LinearEmbedding and RAGE are heavily affected by outliers in the Yahoo dataset.
an arm, and set the reward as 0.8 (if clicked) or 0.3 (if not clicked) to makes the problem harder. In each experiment, we randomly draw 200 arms from the dataset, where of them having rewards 0.8 (proportional to true click-through ratio), Our goal to identify an arm with rewards 0.8, Our experimental setup is similar to the one used in Fiez et al. [13]. However, their true rewards obtained from a least square regression. We do not enforce linearity rewards in our experiment.
Box plots in Fig. 2 show the sample complexity of each algorithm on real-world datasets. NeuralEmbedding significantly outperforms all other algorithms thanks to (1) the representation power of neural networks and (2) efficient exploration in low-dimensional spaces. KernelEmbeddi and LineerEmbeddie success rate of each algorithm. Linear methods such as RAGE and LinearEmbedding have rela- tively low success rates on the Yahoo dataset (with nonlinear rewards). Our Neur MeuralEmbeddia and KernelEmbedding methods have high success rates since they are designed for nonlinear setting.
have competitive performance on the MNIST dataset. Table shows the
Table 1: Success rates on real-world datasets
KernelEmbeddinng NeurallEmeedding
LinearEmbedding
RAGE
ActionElin
MNIST
98%
100%
100%
100%
100%
Yahoo
100%
98%
88%
90%
100%
Conclusion
We introduce the idea of adaptive embedding in bandit pure exploration. Unlike existing works that passively deal with model misspecifications, we adaptively embed high-dimensional feature spaces avoid the curse of dimensionality. The induced
representations into misspecifications are carefully dealt with. We further apply our approach to two under-studied settings with the nonlinearity: (1) pure exploration in RKHS and (2) pure exploration with neural networks. Our sample complexity guarantees depend on the effective dimension of the feature spaces in the kernel neural representations. We conduct extensive experiments both synthetic and real-world datasets, and our algorithms greatly outperform existing ones.
Our current analysis with neural representations is in the NTK regime, which can only describe part the representation of the neural networks. We leave extending our algorithm to more general settings (beyond the NTK regime) future direction.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers and area chair for their helpful comments. YZ and RN are partially supported by AFOSR grant FA9550-18 1-111 66. DZ and QG are partially supported by the National Science Foundation CAREER Award 1906169, ISS-1904183 and AWS Machine Learning Research Award. RJ and RW are partially supported by AFOSR FA9550- 8-1-0166, NSF OAC-1934633 NSF DMS-2023109 and NSF DGE-2022023. The views and conclusions contained in this paper are those of the authors and should not be interpreted representing any funding agencies.
10

---

References
[1] Zeyuan Allen-Zhu, Yuanzhi Li, Aarti Singh, and Yining Wang. Near-optimal discrete optimiza- tion for experimental design: A regret minimization approach. Mathematical Programming. pages 1-40, 2020.
[2] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, 2019.
[3] Maryam Aziz, Emilie Kaufmann, and Marie-Karelle Riviere. On multi-armed bandit designs for phase clinical trials. arXiv preprint arXiv:1903.07085 2019.
[4] Peter L Bartlett, Victor Gabillon, and Michal Valko. A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption. In Algorithmic Learning Theory, pages 184-206 PMLR. 2019.
[5] Robert Bechhofer. A sequential multiple-decisee procedure for selecting the best one of several normal populations with common unknown variance, and its with various experimental designs. Biometrics, 14(3):408-429 1958.
[6] Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. Pure exploration in multi- bandits problems. In International conference on Algorithmic learning theory, pages 23-37. Springer, 2009.
[7] Romain Camilleri, Julian Katz-Samuels, and Kevin Jamieson. High-dimensional experimental design and kernel bandits. arXiv preprint arXiv:2105.05806, 2021.
[8] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems, 2019.
[9] Lijie Chen and Jian Li. On the optimal sample complexity for best arm identification. arXiv preprint arXiv: /5/ 1.03774, 2015.
[10] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432- 2442. PMLR, 2020.
[11] Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Pac bounds for multi-armed bandit and markov decision processes. International Conference on Computational Learning Theory, pages 255-270. Springer, 2002.
[12] Eyal Even-Dar, Shie Mannor, Yishay Mansour, and Sridhar Mahadevan. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of machine learning research, 7(6), 2006.
[13] Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. In Advances in Neural Information Processing Systems, pages 10667-10677, 2019.
[14] Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecifica- tion in contextual bandits. Advances in Neural Information Processing Systems, 33, 2020.
[15] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
[16] Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Misspecified linear bandits, In Proceedings of the AAAI Conference on Artificial Intelligence, 2017.
[17] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018
11

---

[18] Kevin Jamieson and Robert Nowak. Best-an arm identification algorithms for multi-armes bandits the fixed confidence setting. 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6. IEEE, 2014.
[19] Kevin Jamieson, Matthew Malloy, Robert Nowak, and Sébastien Bubeck. lil'ucb: An optimal exploration algorithm for multi-armed bandits. In Conference on Learning Theory, pages 423-439 PMLR, 2014.
[20] Shivaram Kalyanakrishnan, Ambuj Tewari, Peter Auer, and Peter Stone. Pac subset selection in stochastic multi-armed bandits. In ICML., volume 12, pages 655-662, 2012.
[21] Hideaki Kano, Junya Honda, Kentaro Sakamaki, Kentaro Matsuura, Atsuyoshi Nakamura, and Masashi Sugiyama. Good arm identification via bandit feedback. Machine Learning, 108(5): 721-745, 2019.
[22] Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-1246. PMLR, 2013.
[23] Julian Saiz-Saauels and Kevin Jamieson. The true sample complexity of identifying good arms. In International Conference on Artificial Intelligence and Statistics, pages 1781-1791. PMLR, 2020.
[24] Julian Katz-Samuels, Lalit Jain, Zohar Karnin, and Kevin Jamieson. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. arXiv preprint arXiv:2006. 11855, 2020.
[25] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):
1 1-42, 2016.
[26] Abbas Kazerouni and Lawrence M Wein. Best arm identification in generalized linear bandits. Operations Research Letters, 49(3):365-377 2021.
[27] Jack Kiefer and Jacob Wolfowitz. The equivalence of two extremum problems. Canadian Journal of Mathematics, 12:363-366, 1960.
[28] Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with a generative model. In International Conference on Machine Learning. pages 5662-5670. PMLR, 2020.
[29] Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. comfexdb/mnist// 1998.
[30] Blake Mason, Lalit Jain, Ardhendu Tripathy, and Robert Nowak. Finding all c-good arms in stochastic bandits. Advances in Neural Information Processing Systems, 33, 2020.
[31] Rémi Munos. From bandits to monte-carlo tree search: The optimistic principle applied to fr/hal- -0075555-00777755
optimization and planning, 2014. archiv/
document.
[32] Edward Paulson et al. A sequential procedure for selecting the population with the largest mean from k normal populations. Annals of Mathematical Statistics, 35(1): 1964.
[33] Friedrich Pukelsheim. Optimal design of experiments. SIAM, 2006.
[34] Sivan Sabato. Epsilon-best-arm identification in pay-per-reward multi-armed bandits, 2019. https://openrevieww net/forumm XkvNrLLS.
[35] Gabriele Santin and Robert Schaback. Approximation of eigenfunctions in kernel-based spaces. Advances in Computational Mathematics, 42(4):973-99) 2016.
[36] Stewart Schlesinger. Approximating cigenvalues and eigenfunctions of symmetric kernels. Journal of the Society for Industrial and Applied Mathematics, 5(1):1-14, 1957.
12

---

[37] Shai Shalev-Shware and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[38] Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification linear bandits. arXiv preprini 1409.66 10, 2014.
[39] Gilbert W Stewart. Perturbation theory for the singular value decomposition. Technical report, University of Maryland, 1998. https:/ /ttr//rummmmmm 1ib. umd. edu/handle/19933
[40] Ervin Tanczos, Robert Nowak, and Bob Mankoff. A ki-lucb bandit algorithm for large-scale crowdsourcing. In Proceedings of the s1 International Conference Neural Information Processing Systems, pages 5896-5905, 2017.
[41] Chao Tao, Saúl Blanco, and Yuan Zhou. Best arm identification in linear bandits with linear dimension dependency. In International Conference on Machine Learning, pages 4877-4886. PMLR, 2018.
[42] Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv:1309.6869 2013.
[43] Michal Valko, Rémi Munos, Branislav Kveton, and Tomáš Kocák. Spectral bandits for smooth graph functions. In International Conference Machine Learning, pages 46-54 PMLR, 2014.
[44] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
[45] Liyuan Xu, Junya Honda, and Masashi Sugiyama. A fully adaptive algorithm for pure explo- ration in linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 843 851. PMLR, 2018.
[46] Weitong ZHANG. Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference on Learning Representations, 2020.
[47] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492-11502. PMLR, 2020.
13


Reviews:
[{"review_id": "ZjxA6Pgj-6c", "reviewer": "Reviewer_Mvyo", "summary": "This paper introduces a new approach to tackle bandit pure exploration in high dimensional setting. Recall that the literature generally deals with a finite number of arms, or scale exponentially with the dimension of the feature space. The idea, developed in Algorithm 1, is as follows. At each iteration of a RAGE-like algorithm, the arms are embedded into a lower dimensional space. The dimension is chosen as the smallest integer such that the induced error does not harm the subsequent computations and guarantees. Guarantees for Algorithm 1 are derived in Theorem 1, and expressed in terms of the effective dimension. An example of sequence of feature maps is given for linear bandits, based on the SVD decomposition of the design matrix. Under boundedness of parameter $\\theta_\\star$, it is possible to control the induced error by the successive approximations. When the reward function is assumed to be in a RKHS, using the eigendecomposition of the associated integral operator allows to design similarly a series of feature maps with controllable error. The effective dimension can be bounded in terms of the eigendecay of the kernel. The reward function can also be approximated using a neural network. The algorithm (Algorithm 2) then also needs to learn the weights of the network jointly. Guarantees for Algorithm 2 are stated in Theorem 3. Finally, Section 6 presents some experiments on synthetic and real world datasets showing that the proposed Algorithms exhibit smaller sample complexities than Action Elim.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "I found the paper globally clear and well written. The motivations are clear, and the idea of using as few dimensions as possible (as long as the error is controllable) is indeed sound. I found the instantiation to linear bandits (Section 3.2) very enlightening. Then, the extension to a kernelized version (Section 4) also appears to be natural, but it is well presented and treated. The instantiation to neural networks is slightly more involved, but of high interest in practice. Overall, I think the authors did a great writing job (right technical level, natural progression, useful remarks) so that the story presented is consistent and sounds very natural.\n\nCould it be possible to extend the proposed approach to other problems than pure exploration? To the contextual case? What would be the difficulties? \n\nI thought it could be interesting to plot the evolution of $d_k$ with respect to $k$.\n\nSome other minor comments:\n- l. 37: address it *in* the\n- display eq. 109-110: is it necessary to \"assume\" here? the equation seems always verified, for any $\\psi_d$, as long as we define $\\eta_d(x) = h(x) - <\\psi_d(x), \\theta_d>$\n- l. 115: I assume that $||\\cdot||_A$ refers to the Mahalanobis norm (w.r.t. matrix $A$) but this should be specified in the notation\n- l. 132: one need*s*\n- l. 136: citing the RAGE paper here too would be better\n- l. 139: $r_d(\\zeta)$ is not defined\n- Alg. 1/2: putting algorithms at the top of pages help the reading\n- display eq. 150-151: an intuition comment on the complexity measure could help\n- l. 189: *which* is square..\n- l. 230: is *the* use\n- l. 240: *to let* --> such that\n- alg. 2: line 8 is not very clear\n\n**Post-rebuttal edit**\n\nI thank the authors for their response. I am in favor of acceptance and keep my 7 score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "RfHnBTf9Bm1", "reviewer": "Reviewer_Fv1X", "summary": "This paper considers the best arm identification problem for kernel and neural bandits, where the reward function belongs to an RKHS and is approximated by a neural network, respectively. The main contribution is that the authors propose to consider a variant of the Randomized Adaptive Gap Elimination (RAGE) algorithm with adaptive embedding (so that the problem can be viewed as misspecified linear bandits) and then address the corresponding misspecification issue. The sample complexity results are established under known feature mappings and misspecification errors and then adapted to the cases of RKHS and neural bandits. Experimental results on both synthetic datasets and real datasets are provided to validate the proposed algorithms.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "The main idea of this paper is to adaptively choose the embedding and do pure exploration with the corresponding misspecified linear bandits. I like the idea of adaptively selecting the embedding in RAGE as it appears to be a quite generic approach for pure exploration (as long as the feature mapping can be constructed). Based on this design (cf. Alg. 1), the main challenge lies in determining the number of samples ($N_k$ in Line 6 of Alg. 1), which requires careful and non-trivial control of the misspecification error term ($\\epsilon_k$). \nAs the main theoretical result of this paper, Theorem 1 shows that under known feature embeddings and the proposed careful control, the sample complexity is proportional to $d_{eff}(\\epsilon)$, which captures the minimum required dimensionality of the embedding. The proof of Theorem 1 looks sound. Based on Theorem 1, one can accordingly obtain the sample complexity of pure exploration in RKHS and neural bandits (with the corresponding NTK), as described by Theorems 2 and 3. Overall this is a solid theoretical contribution to the best arm identification problem.\n\nI have some questions about the main results:\n- How tight are the sample complexity results provided in Theorems 2-3? \n\n- Regarding Theorem 3 for neural bandits, the hidden layer size $m$ is a function of the number of samples $N_k$, which is at least on the order of $2^{2k}$ and shall be quite large. In practice, how to choose a proper $m$ such that the misspecification error is well controlled? \n\nOn the other hand, I would also suggest the authors to further improve the presentation. Currently, the presentation is quite dense, and several terms, definitions, and designs are introduced without much explanation. This makes some parts of the paper quite difficult to parse. Just to name a few:\n- Lines 114-115: The definitions of $g(d,\\zeta)$ and $\\gamma(d)$ would require more explanation. On the high level, $g(d,\\zeta)$ seems related to the transductive linear bandits (e.g., [Fiez et al., 2019]). On the other hand, it is not immediately clear why $\\gamma(d)$ captures the suboptimality gap.\n\n- Line 6 in Algorithm 1: While I can understand the intuition behind the choice of $\\epsilon_k$, it is not immediately clear to me why $\\epsilon_k$ shall take the current form.\n\n- There are several complexity measures that look similar and related. For example, what is the connection between $g(d,\\zeta)$ and $\\rho^*_d(\\epsilon)$?\n\n- By the equation in Line 109, it appears that $\\eta_d(x)$ also depends on the choice of $\\psi_d(\\cdot)$, and hence $\\tilde{\\gamma}(d)$ shall not only depend on $d$ but also $\\psi_d(\\cdot)$?\n\n- Line 116: The intuition behind the suboptimality gap $\\gamma(d)$ is not clearly explained.\n\n- Is the arm set $\\mathcal{X}$ finite?\n\n- Line 551: There might be some typos in these inequalities. What are $x$ and $x’$ here?\n\n- Line 554: Similarly, what is $x’$ in (12)?\n\nOther minor comments:\n- Line 550: $\\psi(x)\\in \\hat{S}_k$ -> $x\\in \\hat{S}_k$\n\n----- Post-rebuttal update -----\n\nThank the authors for the response. The rebuttal has clearly addressed my questions, and overall this paper is a solid contribution to the pure exploration problems. As a result, I have raised my score accordingly.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In the checklist, the paper mentions that it has described the limitations in Section 7, but I did not see this mentioned in any section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "C3d3pN75QuU", "reviewer": "Reviewer_7Wf3", "summary": "\nThis paper studies best arm identification in kernel bandits. This paper provides an algoritihm to solve it, and extends it to neural bandit setting.\n", "questions": "", "limitations": "", "rating": 2, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "\nThe paper looks incremental, in that it seems to be a combination of recent progress in pure exploration for linear bandits (cf. [13, arXiv:2006.11685]) and the kernel / neural bandit [46]. Since kernel case is usually similar to the linear case, and neural bandit is just kernel bandit with NTK, I do not see much novelty in this paper.\n\n--- \n\nI find academic integrity concerns in this paper. I would argue for strong rejection.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nPlease refer to Ethical Concerns.\n\n---\n\nAt Line 136, RAGE is never introduced before, and one cannot know what RAGE means until Line 282.", "review_text": "", "extra_scores": {"needs_ethics_review": "Yes", "ethics_review_area": ["Research Integrity Issues (e.g., plagiarism)"], "time_spent_reviewing": "4"}, "extra_text": {"ethical_concerns": "\nI am raising academic integrity concerns on this submission. Algorithm 5 in Appendix F.1 is almost the same as Algorithm 2 in [46]. The algorithms has 6 lines. Lines 2-6 are the same as in [46], and Line 1 only changes the symbols. The submission seems not to point this out.  Furthermore, some citations seem improper. For example, the submission cites [17] for Definition 3, but Definition 4.1 in [46] looks more similar to Definition 3 in the submission. Also, the complexity measure in the submission (the equation under Line 150) looks from Eq. (1) in [13], but this also seems not pointed out."}}, {"review_id": "-k4tY9MKZLw", "reviewer": "Reviewer_QyNd", "summary": "Summary: This paper studies \\delta-PAC \\epsilon-best arm identification when a kernel or neural representation is used to embed the arms. The paper targets regimes where the number of arms K is really large and the similarity between arms can be exploited to reduce the sample complexity of the tests needed to find the best arm.\n\nGeneral remark: The paper is well written and addresses a hard problem. The algorithms are smart and the empirical results are impressive. Despite a few minor remarks listed below, I recommend accepting this paper.\n\nDisclaimer: Unfortunately, my level of expertise does not allow me to verify Appendix F.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Positive points:\nI think the main contribution of the paper is that Alg2 improves sample complexity of BAI by *orders of magnitude*, while also satisfying high-probability bounds based on the NTK of the network. \nThe appendix is remarkably clear and (nearly) flawless, which also translates into verifiable correctness.\nThe code is provided and just skimming through some of the files, it does look like a high quality implementation. I did not deeply verify it though.\n\nImprovement points: \n1/ The paper is more or less based on Rage from Fiez et al. [13] but that’s not clearly stated. In the Related Work section, the sentence on line 72 that presents this paper is strange: “hat do you mean by “the instance-dependent sample complexity is achieved” ? Here you should already mention RAGE. But more importantly on page 3, line 136, you say “Algo 1 follows the framework of RAGE” but you forgot to cite [13] here such that someone who does not know the reference [13] already, does not follow your point (that was my case). \n\n2/ *Computational complexity*: I am surprised the computational complexity is not more discussed because the quantities involved in your algorithms do not seem straightforward to compute. First, the feature representation step at the beginning of both algorithms seem like they must be pre-learnt ? So you’d have to store these models. Then the efficient dimension, the \\lambda_k, the \\tau_k are solutions of minmax problems and do not seem immediate to obtain. For the ROUND function, you mention that “computationally efficient” algorithms exist but I am still curious how that scales with K and d (and N).\n\n3/ Maybe there are smart ways to compute these quantities and it’d be worth discussing this. I actually don’t really doubt there is a way because you have pretty large scale experiments so I believe you found a way around but I think it would be reassuring to see this discussion. I am personally quite worried about having to implement this method myself and not knowing what would cost what, what are the bottlenecks, it does not seem like a simple algorithm. \n\n4/ You mention the “rounding term” r_d(\\xi) at line 139 and 141 but is it defined ? I mean else than in Algo 1 where it is only defined up to a constant.\n\n5/ In Remark 3, you talk about known versus unknown misspecification “levels”, is that \\eta_d, or perhaps \\gamma_d ? On line 110, you call \\eta_d the “induced error with low-dimensional approximation”, but it’s actually the “misspecification level”. \nAlso, related wording issue, you say on line 116 that \\gamma(d) quantifies the sub-optimality of the identified arm, but \\gamma_d is just the max of the \\eta_d(x) so it’s more like a misspecification error rather than a gap. I really don’t understand why you mention the gap there. \n\n6/ The “rounding” procedure is strangely named. Somehow I’d call it the “scheduling” or something of the like.\n“Complexity measure” \\rho_d is a bit hard to understand intuitively, at least for the non-expert, which makes the RHS of Theorem 1 a bit difficult to sanity-check.\n7/ Appendix B.3 : I don’t understand line 603 (page 19) how you define x_1=-1/\\sqrt{D}, I guess you are missing the rest of the definition such that x_1 satisfies the definition constraints listed in the paragraph.\n\n8/ Appendix D: “We then define \\bar γ(d) as a measure the quantity the optimality of the identified arm” (l 642) is hard to parse. Also, the statement of Theorem 5 is unclear: what is this display line? I guess you are missing “N\\leq …”. I am still a bit confused about this section because I don't really understand what you *can* compute and that replaces the lack of knowledge of \\tilde \\gamma(d) in the algorithm. But I might have missed it.\n\n\n\nMinor remarks: \nLine 137 : “itertion”\nLine 158, use a “:” for the definition\nLine 173 : “details of”->”on”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is good paper that should be accepted to the conference. Reviewer 7Wf3 raised a concern about plagiarism and gave a very low score of 2 because of the plagiarism claim. However, the other three reviewers and I agree that there is no plagiarism in this paper; unfortunately the reviewer did not interact with us and did not update his score. Aside form the plagiarism claim there are plenty of comments from the reviewers that the authors should use to improve their paper further. 
Decision: Accept (Poster)