Reward Learning as Doubly Nonparametric Bandits:  Optimal Design and Scaling Laws
Authors: Kush Bhatia
Wenshuo Guo
Jacob Steinhardt
Venue: ICLR 2022 Submitted (2022)
Keywords: reward learning
Gaussian process bandits
nonparametric learning
reproducing kernel Hilbert spaces

Abstract: Specifying reward functions for complex tasks like object manipulation or driving is challenging to do by hand. Reward learning seeks to address this by learning a reward model using human feedback on selected query policies. This shifts the burden of reward specification to the optimal design of the queries. We propose a theoretical framework for studying reward learning and the associated optimal experiment design  problem. Our framework models rewards and policies as nonparametric functions belonging to subsets of Reproducing Kernel Hilbert Spaces (RKHSs). The learner receives (noisy) oracle access to a true reward  and must output a policy  that performs well under the true reward.  For this setting, we first derive non-asymptotic excess risk bounds for a simple plug-in estimator based on ridge regression.  We then solve the query design problem by optimizing these risk bounds with respect to the choice of query set and obtain a finite sample statistical rate, which depends primarily on the eigenvalue spectrum of a certain linear operator on the RKHSs. Despite the generality of these results, our bounds are stronger than previous bounds developed for more specialized problems. We specifically show that the well-studied problem of Gaussian process (GP) bandit optimization is a special case of our framework, and that our bounds either improve or are competitive with known regret guarantees for the Mat\'ern kernel.

Under review as a conference paper at ICLR 2022
REWARD LEARNING AS DOUBLY NONPARAMETRIC BANDITS: OPTIMAL DESIGN AND SCALING LAWS
Anonymous authors Paper under double-bling review
ABSTRACT
Specifying reward functions for complex tasks like object manipulation or driving is challenging to do by hand. Reward learning seeks to address this by learning a reward model using human feedback on selected query policies. This shifts the burden of reward specification to the optimal design of the queries. We propose a theoretical framework for studying reward learning and the associated optimal experiment design problem. Our framework models rewards and policies non- parametric functions belonging to subsets of Reproducing Kernl Hilbert Spaces (RKHSs). The learner receives (noisy) oracle access to a true reward and must output a policy that performs well under the true reward. For this setting, we first derive non-asymptotic excess risk bounds for simple plug-in estimator based on ridge regression. We then solve the query design problem by optimizing these risk bounds with respect the choice of query set and obtain a finite sample statistical rate, which depends primarily on the eigenvalue spectrum of a certain linear oper- ator on the RKHSs. Despite the generality of these results, our bounds are stronger than previous bounds developed for more specialized problems. We specifically show that the well-studied problem Gaussian process (GP) bandit optimization is a special case of our framework, and that our bounds either improve are competitive with known regret guarantees for the Matérn kernel.
INTRODUCTION
Specifying the reward function accurately for a desired objective, or reward engineering, is challeng- ing to perform by hand, as the consequences of even small errors be drastic (Hadfiel-Mennell iet al. 2017). To address this, reward learning seeks to learn predictive model of the reward func- tion from data, which is obtained from carefully selected queries to human annotators. The learned reward model is then used as the optimization objective for policy learning. Reward learning has achieved significant empirical success in domains such as text summarization (Stiemnon al. 22200] Böhm et al. 2019), robot locomotion (Daniel et al., 2014), predicting driving styles (Kuderer et al., 2015), and Atari game playing (Christiano et al. 2017).
Despite their success, reward learning methods still lack theoretical grounding. Moreover, their behavior can be brittle even on simple tasks, due to the difficulty choosing appropriate queries and due to feedback loops from adaptive querying (Freire et al.) 2020). Indeed, an ablation study in inCChristiano et al. (2017) suggests that random queries can outperform or be competitive with adap- tive query procedures. To address these issues, provide theoretical framework for analyzing reward learning, framing it as a doubly nonparametric experimental design problem. This frame- work helps elucidate the role of query selection (Chaloner & Verdinelli 1995) and also enables to derive scaling laws-hon the sizes of the policy and reward models affect the query complexity-for reward learning (Kaplan et al. 2020).
Proposed framework. In our framework, suppose class C... Our goal is to find a policy म E C₁ that performs well according to an unknown true reward y* E C,, To do this, we query policies E C., observing noisy estimates of their true reward, and use this information to choose the eventual policy ft
given reward class C, and policy
To be compatible with modern nonparametric learning methods (i.e. neural nets), we view C, and C+ as subsets of Reproducing Kernel Hilbert Spaces (RKHS). The learner therefore optimizes a non- parametric reward function nonparametric space of policies, making the task "doubly" non-

---

Under review as a conference paper at ICLR 2022
parametrie. In contrast, previous work considers a nonparametric function class or reward class, but typically not both. For instance, nonparametric zeroth order or bandit optimization (Srinivas et al. 2010 Mockus 2012 Wang et al., 2018) considers nonparametric function a finite-dimentt dimensad input space. Conversely, nonparametric supervised learning (Wahba 1990. Hofmann et al., 2008
minimizes known loss function over nonparametrie input space.
The doubly nonparametric nature of our task poses new challenges. The (possibly) infinite- dimensional RKHS requires the learner to select which subspace explore given a finite number of queries. Furthermore, the unknown reward function makes it challenging for the learner to rea- son about the information gained from the selected query policies. We address these challenges by deriving a risk upper bound for a family of plug-in in estimators based on ridge regression, and then optimizing this bound to solve the optimal design task.
In addition to the optimal design problem, our framework allows us to study scaling laws with respect to the reward (or policy) class by varying the rate of decay of their corresponding eigen- spectrum. This decay rate determines the effective dimensionality of a RKHS (Zhang) 2002), and provides a natural proxy for varying the the size of the reward or policy class. Qualitatively, our main results show that the excess risk asymptotically vanishes as long the policy class grows at slower rate relative to the reward class.
Sharpness of analysis. Our risk bounds apply to reward and policy classes of arbitrary even infi- nite dimensionality. Despite this generality, we show they provide stronger guarantees than previous known bounds for the specialized settings of compact policy sets and kernel multi-armed bandits.
In Section 4.3 we look at a special case of our problem when the policy set CG is a compact subspace and thus has finite rank. For these instances, show that our learning algorithm obtains
a better excess risk On T42 versus a rate of O(n s(*+1) obtained by the adaptive GP-UCB algorithm (Srinivas et al., 2010), where 3 > 0 a power law decay rate.
In Section we specialize our general results to the well-studied problem of Gaussian process bandit optimization (Williams & Rasmussen 2006). also known as kernel multi-armed bandit (MAB). Specifically, for the class of Matérn kernels with parameter v in d dimensions, we show that our 414444446)
algorithm achieves regret bound of Ö(T (d444(247)
which is strictly better than those achieved by
the GP-UCB and Ti-TThopsoon Sampling (GP-TS) (Chowdhury & Gopalan| 2017) algorithms and comparable with T-GP UCB (Janz et al. (020) and supKernelUCB (Valko et al. 2013 Vakili et al.) 2021]: see Table [ for details. GP-UCB and GP-TS are only yield sub-linear regret bounds when the smoothness of the kernel >>>>> dhut in high dimensions, these bounds essentially become vacuous. The G-G UCB algorithm was designed specifically to overcome this issue. Our proposed algorithm achieves sublinear regret for all / > 3/2.
Our Contributions. We propose wuubly-nonparamettin bandits as a framework for theoretically studying the reward learning problem. Within this framework, we obtain finite sample risk bounds for a ridge regression based plug-in estimator and derive scaling laws for reward learning. From a technical standpoint, we study the optimal design problem for our estimator to select informative query points by showing that the excess risk depends only on the spectral properties of a certain operator of the two RKHSs and the empirical covariance matrix. As a corollary of our risk bounds, we provide sharper regret bounds for a class of kernel MAB problems compared to several exist- ing algorithms, showing that the muubly-nonaarametri lens of reward learning fruitful even for "singly- nopparatnprrrmerrcccc tasks. To obtain these bounds, our reduction carefully constructs two differ- ent RKHSS to embed the input space and reward function into a policy and reward class.
2 FRAMEWORK: DOUBLY NONPARAMETRIC BANDITS
Our framework considers non-parametric policy learning with non-parametric reward models. We let π E H, denote an arbitrary policy and r E HH,, denote an arbitrary reward function, where H, and IH, are Reproducing Kernel Hilbert Spaces. For technical reasons, assume the corresponding kernel functions K2 and C,, both satisfy the Hilbert- Scheeitt condition (see Appendix A details).
We let F(TTr)) E IR denote the reward obtained by selecting policy π under reward function and consider the case where the evaluation functional is linear in both π and r. In other words, F(T,r) (r, MT) where M: H + H,, is known linear mapping from the policy space the
2

---

Under review as a conference paper at ICLR 2022
Algorithm
Regret Ry
Non-vacuous regime
GP-UCB Srinivas et al.
2010)
O 4v4d(2842)
2r4di38+3)
1> +
GP-TS
Chowdhury & Gopalan
2017
Ö (r
1> Ldd
2
Our work
Ö(T (v4d(1847)
x-GP-UCB (Janz et al. 2020)
1/ > 1
SupKemelUCB Vakili al. 2021)
Ó Ruren
Table 1. Our algorithm specializes the case of kernel multi-armed bandits and yields strong bounds (see eq. (9) for precise definition of regret). For a d-dimensional Matérn kernel with smoothness v, we outperform both GP-UCB and GP-TS unless 2 d². The only works to achieve better bounds for small are T-GP UCB, which was designed specifically for the Matérn kernel and a very recent analysis of the SupKemelUCC which achieves near minimax rates.
reward space. Since H, and H., may be infinite-dimensional linearity is only a weak restriction- e.g. the map f + (x) is linear in f for any RKHS.
To incorporate problem structure, we let r" denote the true reward function and assume that r' E C, for some known set C. S HI, such that ||r* 1. We further assume that policies π are restricted to lie in some Cz which is a subset of the unit ball in H. (for instance, C₂ might incorporate physical constraints on implementable policies). Thus, given the true reward r", the optimal policy (for a compact C₂)) is x² E argmax, F"), This proposed framework, which allows for infiite-dimmnsiioal policy as well as reward classes, allows us to study how both the policy and reward space affect the difficulty of learning.
Query access to reward r", The true reward function r* unknown to the learner but is acces- sible via queries to an oracle (e.g. human expert), which provide noisy zeroth-order (or bandit) evaluations of the reward r*. When queried with a policy π E C., the oracle provides response
Oracle O,, : + F(T,r")
+ +E
where e~ (0,
with 72 denoting the variance of the response. There are two possible query models: passive queries (Atkinson] Sebastiani & Wynn 2000), where the learner selects all queries at the same time, and active queries (Bubeck et al., [011 I Lattimore Szepesvári] 2020), where the learner is allowed to select queries sequentially. Our focus in this work will be on the passive query model, but many cases we will outperform existing active query algorithms.
Problem statement. Given passive access to the oracle O,-, the objective of the learner is to output a policy म CT that has small excess risk A, defined as
A r") F(mt", ,r") F(+rr").
(2)
We think of queries to the oracle as expensive, and are interested in achieving low excess risk with as few queries as possible. This notion of excess risk is also studied by the term simple regret in pure exploration bandit problems (Lattimore & Szepesvári, 2020).
Representations in (N). By Mercer's theorem, we can represent any RKHS as subset of (N). Formally, the policy and the reward spaces are isomorphic to the ellipsoids
Hy
Na, oo
(1)) with (
< 00
and
22
H,
Kr. Ors (Kra) E (N) with
0c
for appropriately chosen eigenfunctions Φr.j and Ør.j and corresponding eigenvalues (T. and Mri (Wainwright) 2019). These are defined with respect to a base measure P over the input domain; see Appendix A for details. With a slight abuse notation, going forward, we will use π and r to denote the corresponding coefficients (Kr..) and (kr.) in the expansion above. With this, the
While the eigenfunctions &- and Φr can he different, this representation can still be used by modifying the map M appropriately. This is detailed Appendix A
3

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Policy Learning via Reward Learning
Number of queries n, policy set C.. oracle O,- Select n. policies Q ( ..... Tn) and receive noisy reward evaluations yi (0.((m)) Estimate using observed responses
Input:
(Tn:Yn), using ridge regression Obtain plug-in in policy Aplug E argmax F)
Output: Policy Aplug
inner products associated with HH, and H,, simplify
00
TIJTZJ and (r1,72),,
2.
12),H
Pnj
Pr.j
j=1
Also let S, =- ) and S. = d be diagonal matrices comprising the inverse of the cigenvalues of H,, and H. With this notation, if we view the map M as (infnite-dimensionaa) matrix, its Hermitian adjoin is equal to MM* 8- "M SS.
In order for the evaluation functional F(), to be finite for all т E Hr, the operator norm ||S M ST Plop must be bounded (see Appendix A). We will see later that the decay of this op- erator's singular values is closely related to the difficulty of learning in our setting.
3 ALGORITHM: POLICY LEARNING VIA REWARD LEARNING
Given the setup above, we now describe a meta-algorithm, policy learning via reward learning (Al- gorithm T. for the non-parametrie policy learning problem. The algorithm three-stage proce- dure: it (1) selects a subset of policies Q to query for reward feedback, (ii) uses the responses to learn reward estimate f, and (iii) optimizes this learnt estimate output the policy Aplug. that is, Tplug E argmint (f, . xt) M.... Such general plug-in procedure have been studied in the statis- ties (Van der Vaart 2000) and the machine learning (Devroye et al., (003)) literature. We analyze the excess risk of this estimator for our doubly nonparaetnia setup and use this risk bound to select our query set Q. We now discuss the two key design choices in our algorithm: the choice of the reward estimation procedure well the choice of query set Q.
Reward learning via ridge regression. We estimate the reward f via ridge regression in the RKHS H., (Friedman et al. 2001 Shawe- Taylor et al.) 2004). Suppose that in the first step of the algorithm, we have already queried the oracle on n policies and let {(T,, 3) represent the query-response pairs. For regularization parameter Areg > O, the ridge regression estimate of the reward function is
n
A E argmin Σ (yt ( (r, MT) Aregll
(4)
rEE, 71
The parameter Aveg. which is usually set function of n, controls the bias-variance trade-off in estimating r" smaller values of Aveg reduce bias while larger values help reduce variance.
Excess risk bound for fixed query set. Observe that the plug-in estimator A'lug (Q) is implicitly a function of the query set Q. Ideally, we want to choose the set Q which minimizes the expected risk of the plugin estimator. This requires us to solve the optimization problem
@ argmin E ( (S):r
(5)
S:|S|Sn
However, solving the above precisely requires knowledge about the underlying reward function r", and the combinatorial nature of the optimization problem makes hard to find an exact solution. To address this, we first upper bound the excess risk of the plug-in in policy pllu in terms of the query set
Q = [TI,... Tn) The following theorem bounds the excess risk in terms of the spectrum of the spaces H,, and HH, as well as the covariance matrix of the queried policies Do E मम.
RRcall Hermitian adjoint M satisfies (r. MT)H, = (M"r,
TThroughout the paper, for clarity purposes, we denote by universal constant whose value changes across lines. All our proofs in the appendices explicitly track this constant.
4

---

Under review as a conference paper at ICLR 2022
Theorem 1 (Excess risk of plug-in). For any query set Q consisting of n policies and regularization parameter Aveg > O, the excess risk of the plug-in in estimator Tplug is upper bounded as
(#pugg r"]] & 2|[[ (r (flm))
(6)
In addition, letting M T S, + >regt, the expected squared distance is equal to
B1JM (r- -) Xies IIM AMAAT r
(7)
72
The proof follows a standard analysis of ridge regression and is deferred to Appendix B Observe that in the above theorem, the query set E Q participates in the excess risk only via the covariance Eg. The risk bound is the sum of two term: the first corresponding to the bias and the second corresponding to the variance. In both these terms, Σg appears as part of A-1_thus query sets Q which induce a larger correlation with the map M will generally have lower excess risk. Choices of queries which are orthogonal to the right singular vectors of M will have constant excess risk, since for those directions the matrix A R Areg
As shown later in the appendix, in the special ball C. = { E H || |n, Σ 1]. the excess risk bound can be improved by a quadratic factor:
when the policy set consists of the entire unit
E[A plug: r"] I O (r" ). Such a phenomenon was first observed in the finite- dimensional setup by Rusmevichientong & Tsitsiklis 2010).
4 QUERY SELECTION AND STATISTICAL GUARANTEES
We now show how to select the query set Q effectively and study the excess risk of the corresponding plug-in estimator pluug We will start with the special case where the policy set C is the unit ball in H and the map M is diagonal, and then generalize to arbitrary policy sets. In both cases, low excess risk can be achieved by repeatedly querying (approximations of) the projections of top eigenvectors of M M onto the Hg, space. For the special case when the map M is diagonal, this is reduces to querying the top eigenvectors of HHl.
The excess risk will ultimately depend on the the eigenspectrum of the operator S 2 MM S.M which is similar to the operator M M. Additionally, to interpret our results, we instantiate them for a power law spectrum with exponent /3 > O, that is, (S M S,MS x j-8 where oj corresponds to the jth singular value of the corresponding operator. Such power law spectra have been observed in variety of practical settings, for instance, in the Hessian of trained deep neural networks (Ghorbani et al. 2019).
4.1 WARM-UP: CN = UNIT BALL, M = DIAGONAL
In order get some intuition, we study the special case where the policy set C, consists of the entire unit ball in the space H, and the map M is diagonal with M = diag(v;). Further, let us denote the operator M S MS,
For this special case, our sampling algorithm (Algorithm 2 simply selects the top J eigenvectors of the space H query, for some value J which depends on the decay exponent 3. To see why, observe that for a diagonal map M, the right singular vectors of the operator M are the same as the eigenvectors of the policy space H,, Therefore, the choice of policy Ty in our algorithm is simply the scaled eigenfunction /Mr.jj &z.j. Having selected these J queries, the algorithm queries each one of the y times and uses this as query set Q.
The intuition for this choice of query set Q is that since we are in the passive setup with no knowl- edge of r", any policy we can obtain a good enough approximation to the performance of any policy in the unit ball. The particular choice of the parameter J depends on the number of queries available. Since the acle responses are noisy, to reduce variance in the responses along those directions, our algorithm performs multiple queries along the same direction.
Cn can be optimal policy. By querying the top J ones out of these,
we further consider the special case when the policies and rewards correspond to the unit balls in the finite dimensional spaces de and Rdd respectively, our choice of query set queries the directions
5

---

Under review as a conference paper at ICLR 2022
fei each for J = 2 number of times. Intuitively, this strategy works well because without any prior over the unknown reward function, the optimal strategy in the passive setup is to explore all directions equally and this is precisely our set of chosen queries. This simple query strategy enjoys the following excess risk bound.
Proposition (Risk bound for C2 = unit ball.). For any J and regularization parameter
Areg > O, consider the plug-in in estimator obtained via the passive sampling algorithm which explores the first J eigenfunctions of Hlg. The excess risk satisfies
(ipiui 5')s (1+
Neg J
TeXing
max
sup Lisu
Cj + Xing 3od
(8)
Sune and e O is some universal constant. Hng
where the quantity C
We defer the proof of the above proposition to Appendix B The choice of the exploration parameter allows us to trade-off between the two terms inside the maximum. Typically, the second term will be maximized at J + 1. For the first term, the supremum depends the choice of Areg for small values of Aveg. the sup is achieved at j = while for larger values, it is achieved at = J. In order gain more intuition about this bound, we instantiate this for the power law decay.
Corollary (Risk bound for power-law decay). Suppose that eigenvalues of the police space H decay as j j-D=, reward space H,, j- and the singular values of map M as j- This satisfies the power law assumption with exponent 3 = BBx + 3M Br. The plug-in estimator with exploration parameter n 8-2 and regularization Xreg = n2 942 satisfies [[A(Aplug;: r]]] $ cn #42.
The above bound shows that our algorithm can learn in the framework as long as B >> 0 or equiva- lently 3- + BB > 3r. with better rates for larger values of 3. Thus, for fixed size of reward class 3r. the learning rate improves as the policy class grows smaller (3, increases) - this is intuitive since are required
search over smaller policy space. On the other hand, for fixed policy class 9 our excess risk rate gets better as the reward class grows in size (8, increases) this is because a larger set of reward functions have similar optimal policies and hence learning gets easier.
4.2 GENERAL POLICY SETS
We now describe our choice of query sets Q for general policy sets Cr. Our strategy, described in Algorithm 2 differs from the above special case that we need to take into account the interaction of the policy space HI, with the map M. Specifically, we show in Appendix B that the upper bound in Theorem can be diagonalized for this general case via a transformation.
Let us denote the operator M = S/ M 1/2 Our transformation reveals that the relevant directions query for this general case corresponds to the columns of Sx VM where then VM the eigenvectors of the self-adjoint operator M M and is precisely subset of these directions that our algorithm queries.
In order to be able query these policies, we require the set C to contain some policies which align well with them. We formally state this regularity assumption below.
Assumption (Regularity assumption on Cz). For any eigenfunction & of the operator M T M, consider the policy n. = S ST/S 1/4 2 There exists policy řt in policy set C' such that for some constant ex > O, we have न. Z C.
The above assumption requires that for every choice of the policy тÿ in Algorithm 2 the set C has the another policy म which is collinear with it. This assumption can be relaxed in various ways (for instance via convexification) but we omit this as it is not needed for our results. Given this assumption, the following theorem, generalization of Proposition D provides bound on the excess risk for the plug-in estimate for general policy sets Cx.
Theorem 2 (Risk bound for general policy sets Cz.). For any J < n, regularization parameter let ftplug be the estimator output by Algorithm 7 The
Xreg 0 and set Cr satisfying Assumption /
squared excess risk satisfies
X2
(Fpphip i 112 sc. (1+
niZis
max sup List C3 + NPag
sup 43
52
6

---

Under review as a conference paper at ICLR 2022
Algorithm 2: Passive querying strategy
Input: Number of queries n, map M. policy set Cn, exploration parameter J Construct linear map M = S M and compute eigenvectors { of operator M M
Set policy Tj = =x x j for all j J Obtain policy #j E C such that म5 T Form query set Q [ (n/J)
where a!h) = fa..... ......,,a])))). a}} repeated b times ..... "p0
Output: Query set Q
where the values Çj correspond to the juh eigen values of the operator M M with M = S MSt
We defer the proof of this theorem to Appendix B The proof of this theorem goes via a transfor- mation which diagonalizes the excess risk bound and reduces the problem a similar setup as that of Proposition]] I Additionally, Assumption I allows us to generalize the results to arbitrary policy sets CT. Note that the above upper bounds the square of the excess risk. As discussed in Section one can obtain a quadratic improvement in this rate if the set C' is the entire unit ball in H,, We specialize the above bound for the power law decay assumption in the following corollary.
Corollary (Risk bound for power-law decay). Suppose that eigenspectrum of the opera- for ST .M S,MS. satisfy the power law assumption with exponent 3 0, that is, (S M S,MS. x j. The plug-in estimator Tplug with parameter J = na+2 and reg- ularization Xreg n #4Z satisfies [[[[(iplug; r"]] S en 2(5+2))
d+1
The above bound indicates that for the general case, learning is possible if the spectrum decay has parameter 3 > To get such a spectrum decay with the operator defined in the above corollary, one sufficient condition is that the map M does not flip the larger eigenvectors of IH,, towards the smaller eigenvectors of Hy, that is, the map preserves the ordering of the eigenvectors of HI, when transformed to the space Hi, Such misaligned scenario would require learning a very accurate representation the reward to learn a good policy and will make learning harder.
4.3 COMPARISON WITH UCB-STYLE ADAPTIVE ALGORITTM
We next turn to evaluating the sharpness of Theorem 2 Existing frameworks for studying "singly"- nonparametric setups require the input domain to be compact. In our doubly-nonparametric setup, the input space is the policy set C₂ which is often non-compact (i.e. the unit ball is not compact in infinite dimensions). We address this for nonpaaeoopa algorithm by taking a finite- dimensional approximation.
Even though our proposed method is passive, it achieves better rates than well-known adaptive sampling algorithms. Specifically, in the power law setting of Section 4.1 the analysis of GP-
8-1 UCB algorithm (rinivas et al. 2010) provides a rate of O(n 1) which is strictly worse than
the O(n œीr) obtained by our analysis in Corollary [] We refer the reader to Proposition 2 in Appendix D for exact statement. The proof adapts the analysis from Srinivas et al. (2010), which hinges on a quantity called the information gain, which we bound for our setup. While we comparing upper bounds for the two algorithms, we believe that improved bound is due to a better algorithm and not an analysis gap. While we expect adaptive algorithms to perform better than passive ones in general (Lattimore & Hao 202T). UCB style algorithms require the construction of confidence intervals around input points, which crucially dictate the regret bounds of such algorithms. In the frequentist setup, the best known such bounds (Vakili al., (221)) are known to yield suboptimal regret rates and it is an open question as to whether these can be improved.
NEW BOUNDS FOR KERNEL MULTI-ARMED BANDITS
In the previous subsection, we saw that our passive sampling algorithm actually outperforms exist- ing adaptive sampling algorithms for the reward learning task we care about. Here take this step
7

---

Under review as a conference paper at ICLR 2022
further- we specialize our algorithm to the case of kernel MABs, and show that it outperforms stan- dard algorithms for that setting and is competitive with a specialized algorithm for Matérn kernels.
We consider the task of maximizing an unknown function f X'' + R over its domain X' Rd In the kernel multi-armed bandit (MAB) setup, this unknown function f belongs to an RKHS H. equipped with a positive-definite kerne [C, such that || 1. Let us further restrict our attention to the space of input points X' = {2 R |||||| 1}. The learner is allowed to access this function via a noisy zeroth-order oracle O-- : + fx(x) + 17 where 17 ~ (0, r²). Going forward we will assume that т = 1. The above oracle is similar to the reward oracle O,-- . except that the query points belong to finite dimensional space and f is a non-linear function of the query point x. The goal
in MAB is to minimize the T step regret
RT max (x) Σ (xe)
where 24 is the datapoint queried in the thh round. There have been several algorithms proposed to solve this problem including general purpose UCB algorithms (Srinivas et al. 2010 Chowdhury & Gopalan| 2017). Thompson sampling approaches (Chowdhury & Gopalan 2017). and special- purpose algorithms for specific kernels (Janz et al., 2020).
We next show that kernel MAB can be cast as a special case of our non-parametric policy learning framework. The resulting regret bounds, derived from an application of Theorem B] are better than several general purpose algorithms (GP-UCB, IGP-UCB, GP-TS) and comparable to those special- ized for the Matérn kernel GP-UBB)
In order to reduce kernel MAB to our framework, we need to introduce three elements - the policy space H.,, the reward space H,, and the map M. We would like spaces H, and HH such that (1) the resulting objective F(r, T) is linear in this space, (2) the resulting rewards and policies have unit norm in their respective space, and (3) we have a good understanding of the eigenvalues of the resulting operator. This last point ensures that we can employ our upper bounds from Section 4
Before we define these, we let C. denote an e-net of the input space X under the lg norm and denote its size by (E). We define the kernel matrix K E R NoooxNN on points selected in the cover as K (ii,j) = K(T,,, 23) for all (I2, E C, x C..
Reward space IH,,, Given the RKHS HI as well as the elements of the cover C., we view the reward function as a map from C. to R, or equivalently as a vector in R RMr(()) More precisely, letting f= [f(1))).....) f( N... denote the vector of evaluations of a function f. we define
H, Š I E IH with (f,, = Ι K-
(10)
With this notation, we define the true reward r" : (f)). ((NN.))).
Policy Space IH,, Similarly to rewards, we will embed policies in No For any point C,, let k2 [K(z, _ K(2,, 2 New)] )l denote the corresponding vector in R Now obtained by evaluating the kernel K. over the cover. Then, the space
H span (k. x E C.) with (ki, k2) = (K,, K 2k2)
(11)
The choice of the above norm ensures that (k;, ky)n, = (K- kk; K ky) = ōg,5 for all (z,, rz) e C. x C. Thus in particular, HH,, contains an orthonormal embedding of the set of vectors (kz J
Map M. Both the reward space H, and policy space H2 can be associated with R Now, Under this transformation, the evaluation f (xx) for any C. corresponds to the standard inner product with F(r", -=)== (z) = ( k = (r", ,,z),.. This indicates that we should take the map M to be the identity. Furthermore, as simple application of Mercer's 's theorem it follows that this map M is a bounded linear operator.
We make additional assumption on the kernel function K,, requiring it to be Lipschitz in its input arguments. This assumption is often satisfied, in particular for the Matérn kernel when v > 3/2.
Assumption 2 (Lipschitz Kernel K)). The Kernel KC associated with the Hilbert space HH is Lx-- Lipschitz with respect to the ty-norm for some Lx > 0: [[(x, v) K(x,x)) Σ Lx||æ all2 for all x E X,y y E X. Furthermore, the kernel satisfies K(x, lforr all points x E X.
"We require that the kernel K. be Mercer's kemel satisfying K((x, = c for all x X.
8

---

22 (Janz al. Under review as a conference paper at ICLR 2022
5000, /
0.75
0.05
Observed risk
0.045
Linear 0.20
Excess risk
0.04
Prodicted
Excess risk
0.035
0.03
1084
2046
4056
0.025
8192
2
10
Number queries
Dimension
(a)
(b)
Figure (a) Corroborating upper bound from Corollary [ Our theoretical bounds predict rate of n 0.27 and the experiment shows an almost matching rate of 20.22 (b) As the dimension d is increased, the excess risk curves asymptote at different levels for different This shows that our algorithu achieves non-vacuous error for the doubly nonparametric set the regime d' -
Applying Theorem 2 under the above assumption, we obtain the following excess risk bound for the plug-in in estimator evaluated on the unknown function f*
Theorem (Excess risk for Kernel MAB). Suppose that the eigenvalues of a LipLschchitz kernel K. satisfy the power-law decay μj x j 3- Let Eplug be the output of Algorithm I Jusing queries to the oracle Oy.. Then, for any value of B 1 + loo(?)) and E (0, 1), the excess risk satisfies
1 max (x) - ("((up) S Ncow (c) F + Neoù (e) v Txce.
=1
with probability at least 1 5.
For Matérn kernels, it is known that the eigenvalues decay with parameter 2020). Using this, we can obtain the following corollary.
Corollary 3 (Regret bound for Matérn Kernel). Consider the family of Matérn kernels with pa- rameter >
defined with the Euclidean norm over Rdd. The T T-step regret of our algorithm is dv d(6++44)
Rmatt Ō Bo
The above bound is for regret, which is an online notion, while our previous results are offline notions. We get from to the other using standard batch-to-online conversion bound based on an explore-then-come tthen-commit strategy. Table I compares the above bound to the existing bounds in the literature. While the bounds for GP-UCB and GP-TS become vacuous for S d, our bound from Corollary 3 is always sublinear T.
6 EXPERIMENTAL EVALUATION
We experimentally evaluate our algorithm via a simulation study. We use these experiments to establish the dimension free nature of results well as conjecture optimality of bounds.
Setup. In the simulation study, we work with dimensional RKHSs Hi, and H. In order to simulate the nonparmeteric regime, we typically use value of which are less at most constant times the dimension d. We set the matrices S, = diag(} 1175), -1.75) S, diag(j-1) and the map M = L. With this, the effective decay parameter = B B, 0.75. We further sampled the oracle noise e < (O0, 0.01). All plots were averaged over 10 runs.
Observations. Figure a shows the variation of excess risk as the number of queries n are varied from 256 to 4096 on log-log plot. Our bounds in Corollary [ this setup predict that the excess risk should decay a rate (n -0.27). By fitting linear line through the plot, we found that observed risk to vary as (n This plot is suggestive of the fact that our theoretical upper bounds might be tight a minimax way over choices of decay parameter B. In Figure [b), we plot the excess risk we vary the dimension d from 32 to 8192 for four different choices of sample size, again, on log-log scale. Increasing the number of queries decreases the excess risk for all dimensions consistently. The risk curves tend to asymptote at different error levels for different values of n. This corroborates our theoretical findings that our proposed algorithm provides non- von-vacuous bounds for the doubly-nonparammtric setup in the regime d - co.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Our main contribution a theoretical framework to study reward learning and the associated optimal design problem. Since our contributions are mostly theoretical in nature, do anticipate any ethical issues arising in the near future.
REPRODUCIBILITY STATEMENT
On the theoretical side, we provide detailed proofs for all our results in the appendix and appro- priately reference the intermediate results we might have used in the proofs. For the experimental aspect, we have attached our matlab code as a supplementary file and have provided all necessary hyper parameters details required reproduce the experiments.
10

---

Under review as a conference paper at ICLR 2022
REFERENCES
Anthony C Atkinson. The usefulness of optimum experimental designs. Journal of the Royal Statistical Society: Series (Methodological), 58, 1996.
Florian Böhm, Yang Gao, Christian M Meyer, Ori Shapira, Ido Dagan, and Iryna Gurevych. Bet- ter rewards yield better summaries: Learning to summarise without references. arXiv preprint arXiv: 19tp:0199001110 24, 2019.
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. Journal of Machine Learning Research, 12(5), 2011.
Xu Cai and Jonathan Scarlett. On lower bounds for standard and robust gaussian process bandit optimization. In International Conference on Machine Learning. PMLR, 2021.
Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: A review. Statistical Science, pp. 273-304, 1995.
Xiaohui Chen and Yun Yang. Hanghn-wright inequality in hilbert spaces with application to k- means clustering for non-euclidean data. Bernoulli, 27(1):586-614 2021.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, 2017.
Paul Christiano, Jan Leike, Tom B Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. arXiv preprint 1rXiv:1706.03741, 2017.
Christian Daniel, Malte Viering, Jan Metz, Oliver Kroemer, and Jan Peters. Active reward learning. In Robotics: Science and systems, volume 98, 2014.
Luc Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, vol- ume 31. Springer Science & Business Media, 2013.
Pedro Freire, Adam Gleave, Sam Toyer, and Stuart Russell. In Proceedings of the Workshop on Deep Reinforcement Learning al NeurlPS, 2020.
Jerome Friedman, Trevor Hastie, Robert Tibshirani, al. The elements of statistical learning, volume 1. Springer series in statistics New York, 2001.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density. In International Conference on Machine Learning, pp. 2232- 2241. PMLR, 2019.
Dylan Hadfield-Menell, Smitha Milli, Pieter Abbeel, Stuart Russell, and Anca Dragan. Inverse reward design. arXiv preprint arXiv:/71 2017.
Thomas Hofmann, Bernhard Schölkopf, and Alexander Smola. Kernel methods in machine learn- ing. The annals of statistics, 36(3):1171-1220, 2008.
David Janz, David Burt, and Javier González. Bandit optimisation of functions in the matérn kernel rkhs. International Conference on Artificial Intelligence and Statistics, 2020.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08366 2020.
Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sam- ple covariance operators. Bernoulli, 23, 2017.
Erwin Kreyszig. Introductory functional analysis with applications, volume 1. wiley New York, 1978.
Markus Kuderer, Shilpa Gulati, and Wolfram Burgard. Learning driving styles for autonomous hicles from demonstration. In 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 2641-2646 IEEF, 2015.
11

---

Under review as a conference paper at ICLR 2022
Tor Lattimore and Botao Hao. Bandit phase retrieval. arXiv preprint arXiv:2106.01660 2021.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Mereer. Functions of positive and negative type. and their connection with the theory integral equations. Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, 209, 1909.
Jonas Mockus. Bayesian approach to global optimization: theory and applications, volume 37.
Springer Science & Business Media, 2012.
Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of
Operations Research, 35, 2010.
Paola Sebastiani and Henry P Wynn. Maximum entropy sampling and optimal bayesian experi- mental design. Journal of the Royal Statistical Society: Series (Statistical Methodology), 62, 2000.
John Shawe-Taylor, Nello Cristianini, et al. Kernel methods for pattern analysis. Cambridge uni- versity press, 2004.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias W Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning, 2010.
Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. Learning to summarize from human feedhack. arXiv preprint arXiv:2009.01325, 2020.
Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pp. 82-90. PMLR, 2021.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint orXiv:1309.6866 2013.
Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
Grace Wahba. Spline models for observational data. SIAM, 1990.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Yining Wang, Simon Du, Sivaraman Balakrishnan, and Aarti Singh. Stochastic zeroth-order opti- mization in high dimensions. In International Conference on Artificial Intelligence and Statisties, pp. 1356-1365. PMLR, 2018.
Christopher K Williams and Carl Edward Rasmussen. Gaussian processes for machine learning. volume 2. MIT press Cambridge, MA, 2006.
Tong Zhang. Effective dimension and generalization of kernel learning. In NIPs, volume 4, pp- 454 461. Citeseer, 2002.
12

---

Under review as a conference paper at ICLR 2022
A TECHNICAL DETAILS FOR PROPOSED FRAMEWORK
A.1 RKHS ASSUMPTION
The Hilbert spaces H and H, are Reproducing Kernel Hilbert Spaces defined by kernel functions Ka Kr A' x X' + [0, 1] respectively defined over a compact instance space A. Further, the kernels Ky and K2 satisfy the Hilbert-Schmine condition
JENX Ki(æ, dP))())))(()))) S oc for i {T,
(12)
for some distribution P over space X. Mercer's theorem (Mercer 1909) implics that such kernel functions have an associated set of eigenfunctions (with corresponding cigenvalues) that form an orthonormal basis for (X,, IP). We restate a version of this theorem below (Wainwright 2019).
Theorem 4 (Mercer's theorem). Suppose that the space X compact and the positive semi-definite kernel K. satisfies the Hilbert-Schmidl condition [12. Then there exists a sequence of eigenfunctions
{=)) that form an orthonormal basis of L X PP) and non-negative eigenvalues (1z)}=1 such that
J K(z, (x) for all j 1,2,...
(13)
Furthermore, the kernel function has the expansion
K(a,, z) = Engo,
(14)
where the convergence of the sequence holds absolutely and uniformly.
A.2 CONDITIONS FOR REWARD BOUNDEDNESS
For learning be feasible in the proposed framework, we would require that the evaluation func- tional F(T,, r") is bounded for any policy E [Hl.. Using the fact that ||r"||,, & 1 and ||>||, < 1, we have
F(T,r") = (r",, (r*) < S llop
(15)
Thus one sufficient condition for the reward functional to be bounded is to ensure that the operator norm ||5 M !lop is finite. In the special case when the map is diagonal with M = diag(v)), the above condition simplifies
Vi
F(T,T") & sup j21
(16)
M
A.3 REGULARITY ASSUMPTIONS ON MAP M
We assume that the map M is compact bounded operator from the policy space HH to the reward space H,. By Schauder's theorem, the adjoint M is also a compact operator. Thus, the map M M HL, + Hy compact self-adjoint operator. This allows for compact self-adjoint operators which guarantees the existence of eignevalues and cignefunctions for the operator M M and corresponding singular value decomposition for the map M (Kreyszig 1978).
use the spectral theorem
A.4 NON-ALIGNED RKHSS
As mentioned in the Section 2 if the eigenvectors of the spaces H, and H, are not aligned, one can consider the following simple transformation which resolves this. Let & and o, represent the eigenvectors.
F L
# == n, and M T.7 M
(17)
The above transformation implies that ||+||,, and || ||,, 1.
13

---

Under review as a conference paper at ICLR 2022
B PROOF OF MAIN RESULTS
In this section provide the proofs for the main results of this work. OopendixDioo follow contains the proofs for the other results.
B. PROOF OF THEOREM
We begin by proving the result for the special case when the policy set C, consists the entire unit ball and then generalize the analysis to arbitrary policy sets.
Case C is unit ball in H For this special case, observe that the the optimal policy x* and the plug-in policy &plug for any reward estimate i can be written as
M
M
π
and Tplug
(18)
M
M f
where the operator M* is the adjoint of of the map M. To prove. bound on the excess risk using plug-in estimate, we use the following lemma which bounds this error terms a deviation the estimated and true rewards.
Lemma 1. Consider any vectors x and y with finile non-zero norm under some inner product (:))) Then, we have
1/c y/1²
(19)
x
2 ylll
The proof of the above lemma is presented in Section B.I.I upper bound the excess risk
Taking the above as given, we can
Mr A(t;r")= (M*r"
M ||
)n,
|| r 1|a ||
f)
(20)
2||M*
Case 2: Arbitrary set Cr. For this case, consider the excess risk of plug-in estimator Aplug ob- lained by maximizing reward estimate ñ
A(ā;r*) (M" n²" &ppug) H. (M" -"), + (M*f - + (M r"), )
2r f)]
(21)
where the final incquality follows from the fact that ulug maximizes F(R;;) over the set C₁,.
Thus, we see that for both the cases above, estimator in terms the norm J.M*((" - ll.. Next, we evaluate this for ridge regression based reward estimator for any set of queries Q (TI...., with covariance matrix Σ Ee प.;. For any regularization parameter Areg > O, we have,
upper bound the excess risk of the plug-in
arg min rEa. YI
wE (r, MT.)u.)) Aregl1r12..
(MEM S, \reg!)
Mm
i=1
M Σ
=r-- (MEM S, 1)=g!)-14" (MEM 8, + >reg!)
E
(22)
14

---

Under review as a conference paper at ICLR 2022
where and equality (i) follows by substituting the value of y/ FT,,, r")r"" + c.. Let us denote by matrix A MEM Sp + IregI Therefore, the error in reward estimation
M
8 Aveg 7
A
+ 1-1
N (Wrre
72 A
MEMMEMAAT A-T)
(23)
where the final distribution follows from our assumption the noise variables NN +2). Using this above distributional form, we have
(rllM"(r - I1l,a] = Xeeg (M-A r" M AAAA"") + T A AAMMM--M,MM.. A (MM) AAMMAAATA
= > (rr) A--))AATMM'"" S, S A tr, MMM' A (M*)T]
(24)
The final bound for the general policy set Cx follows from using the above bound with ap-
plication of Jensen's inequality. order to convert the above bound to a high probability bound, we require an infinite dimensional analog of the Warignn-riight concentration inequality. Using
Theorem 2.6 from Chen Yang (202T) along with equation (23) we obtain
t2
Pr(A(R; r") 2 E A: }] + t) - exxp (-C min
|
Tlloo
HS
where the covariance matrix I S AM'A-MEMM A A S
B.1.1 PROOF OF LEMMA
Let the vector y x + 8z for some difference vector 8. Using this, we have
(x. ||=||| |M = (zc,
x
x
x + &x
||0|||
| + 6zel'
|
(a, 85)
|| + 8wll - ||11-1
22 + 8z
|
||a:||
|| + (x, oz)
||
(xr, 5z)
+
||=|||
||x + 8ell
||||||
2||==|
||~|||
62
(25)
2| 6
where (i) follows from using the inequality Va² + 2 +
2.
This establishes the result.
2a
B.2 PROOF OF PROPOSITION D
Let us denote the the map M (1z)( and the covariance matrix Σ diag(o,). From the upper bound obtained in Theorem I we have,
T2
E[[| (r"
||M A 1 f) X
M - M
n²
Xpeg
||$ M A - $12
+
tr
S M
'MEM" A
T]
n
(
?2
V V2 + reg
reg
sup f21
1203 + X2 u
+
sup j21
(26)
where inequality (i) follows from using the fact that ||, < and inequality (ii) uses the diagonal structure of the map M as well the fact that each policy E Q has unit norm.
15

---

Under review as a conference paper at ICLR 2022
Recall that the choice of querying strategy queries each scaled eigenfunction Ox of the policy space n²-a times. Therefore the jth entry of the covariance matrix 2 is given by
for j S n
76
(27)
otherwise
Plugging the above value of oy into equation 26
obtain
2 reg
Cj
B||l A) & max
sup S
sup
reg
jun
n 2
G
max
sup JSn
(28)
Aeg
22
Aegg
This concludes the proof of the proposition.
B.3 PROOF OF COROLLARY 1
We now derive explicit finial sample rates for the case when the spectrum of the map M S,MST
satisfies power law decay for some parameter > O. In the notation used in Proposition I have the quantity
(29)
Our proof strategy will be to instantiate the bias and variance terms for this setting of Cy and finally select setting for the exploration parameter and regularization parameter Areg.
Bounding Bias.
The bias term in the proposition is a max over two terms
X 2 Sj
Bias
sup jzna
sup Sj
(30)
C} + rog
20
j>n'
We consider the two terms in the analysis here separately. For the first term,
\ nan Cj + Xeg
1
sup jSn
Aeg sup SSn
A
(31)
Veng 1
n2a
where the final inequality follows from using a² b2 > 2ab. For the second term, we have
sup Gj= sup j j_ aB
(32)
12n"
j2n
Bounding Variance. Recall that the variance term (assuming 1) is given by
n
S
Variance n
max sup jSn
2a sup Jona X
(33)
{j Teg
We again consider both terms of the maximum separately. For the first term,
2220²
sup j5n
X2 n2a Agg
S 2a-1
(34)
where the inequality follows from ignoring the term variance term,
X2 Xaag
2a in the denominator, For the second
2 n 22g
sup j>no n2
(35)
Xogg
Setting regularization parameter. By setting Areg > - we can have that the bias term is dominated by >re Similarly, the above setting also implies that the variance term is dominated by 22a-1, Combing these observations, we have that the expected error upper bounded by
A(#plugir") r") S AregT +2
where Areg -ag-a
(36)
Setting Areg o(8-1) and then a 8+2 we get that
A (ftplog r²) S n 342
(37)
This completes the proof of the corollary.
n
16

---

Under review as a conference paper at ICLR 2022
B.4 PROOF OF THEOREM! 2
In order to prove the general theorem, we exhibit a transformation which allows us to reduce the problem that with the diagonal structure described Proposition I
We will consider orthogonally diagonalizable matrices S, and SN which represent the eigenvectors and eigenvalues of the Hilbert spaces H,, and HHl. Consider the following of transformations for any reward r E C,- and policy E C..
Săr, #= =
(38)
With this transformation, rewrite the objective function above
max M))
s.t. (m, = and (f, =1
where the inner product ( denotes the standard lg inner product. Observe that we have overloaded notation to denote by f f. Further, using these above transformations, we can rewrite the adjoint operator
M = S-= (s
NT s#
(39)
Recall from Theorem
1 the matrix
= MEM S, + Arg ST MEM + \reg! 8
(40)
where the covariance matrix E - TT We have used the fact here that the matrices S, and S, are orthogonally diagonalizable and hence symmetric. Finally, we will denote the singular value decomposition of the compact map M in the matrix form as
M = U
The existence such a decomposition is guaranteed by the regularity assumptions we consider on the map M in Appendix A We will now analyze the bias and the variance terms from the upper bound on [E[] M (r* fll from Theorem
Bound on bias.
The squared bias term given by
Bias²
= r A T( ( S.M-
reg
-r S (MSSTT
> 1) S MS b. MM
=FT(M + >res!)) 1)-M St ST MT S - (MEMT \reg!) -F
=MEMM + \rog!) 1 - (MEM + \)
V Xreg!) 1) A (A EV AM A UTT (41)
where we have used the SVD decomposition for the matrix M in the last step.
Bound on variance.
The variance term is given by
Var 22
tr S A ME, A A
71
7
tr M T ATME A () -MEM TMMEMM (MEMT + Areg!)
71
7² ir (A VTV + \reg!) A V TVV Sz Air + \rag!) -Axi) -
(42)
Finally, by making substitution for reward F F and policy म VT= in equations (41)
M
and 42 recover back the bias variance expressions used in the analysis for Proposition| 1 What
17

---

Under review as a conference paper at ICLR 2022
remains to be shown is that our particular choice of query policies correspond to basis vectors in this transformed space. For this, observe that the sampling policies
Ty
Mrr ( Dx for S n2
is such that the transformed policies
M Si My =V V ST V =jj
(43)
indeed correspond to the basis vector. This finishes the proof of the desired claim.
B.5 PROOF OF COROLLARY 2
The proof of this corollary follows similar that of Corollary | in terms of bounding the bias and the variance. The final rate follows by application of Jensen inequality to conclude
M|I (r" f),) s (E[I) - )
(44)
The final rate that we get in this case is thus upper bounded by the square root of the rate observed in Corollary [
This concludes the proof.
C GAUSSIAN PROCESS BANDIT OPTIMIZATION
In this section, discuss in detail the application of our framework the problem of frequen- tist Gaussian process bandit optimization, also known as Kernelized multi-armed bandits (MAB) problem. Recall the reduction of the Kernel MAB problem our setup required to define three elements.
Reward space H,, Given the RKHS IH as well as the elements of the cover C., we view the reward function as a map from C. to R, or equivalently as vector R Nawce) More precisely, letting f f= f(ee. denote the vector of evaluations of function define f(NN.))
H. { f H}
(45)
with f2mm = fT K K-
where (:--) represents the standard lo inner product. With this notation, let us define the true reward r" := f If" (x
f ff= N..)..
Policy Space Hr, For the policy space HI, in our setup, we let
H span = [K(x,,)) K .... E R. xx E with (k1, k2) : = (k:,, -K-2kk) k2)
(46)
The choice of the above norm ensures that
(ks, k.) = (K k; K ky) = (e,, eg) 81,5 for all (2,,2;) E C. x C.
For the policy space Hig, we have created an orthonormal embedding of the set of vectors hacc Observe that this policy set that we construct satisfies the regularity Assumption [ because each vector & is eigenvector of the space H.,
Map M. By our assumption that the kernel K. is Mercer's kernel, have that H, H,, that is, for all x E C, the vector kg E Hp.. Furthermore, both HI, and HI, are sub-spaces of New and we can take the map M I
With these definitions, we now explicitly establish a correspondence between our doubly nonparam- eteric bandit problem and the Kernel MAB problem.
18

---

Under review as a conference paper at ICLR 2022
C.I CONNECTING THE PROBLEMS
Given an RKHS H with an associated Mercer's kernel K. the objective of the zeroth-order bandit optimization problem is
max f" (x) such that |l 1 1, ZE
(PI)
with access to oracle
O 12 (*)
where ~N(,
Equivalently, the objective in our reward learning framework is
(rx T)H.. such that ||r||,, and || S 1,
(P2)
with the corresponding spaces and inner products are defined in the previous section. The oracle required in setup responds with
O : (r", T)H, where r NO,,
for any policy Hy, such that || 1. Our first lemma below states that obtaining such a oracle is indeed feasible if we are able to restrict our queries to include only points hi for which the vector k C..
Lemma 2. Given access to oracle Or- for a function f*, the corresponding oracle O can be implemented when the query set consists of (EC)
Proof. For any query point the oracle O,, needs to compute the value (r", (,",)),," (x).. Thus, these two oracles on the provided query set are exactly identical.
Lemma 3. For any f E H. satisfying fI ı| S 1, we have that || S
Proof. Observe that an alternate way to define the RKHS norm is given by
|| =
sup Scx
J'sK'sJ ʃls
The fact that [|t, is computed on C. C X' establishes the desired claim.
Finally, we turn to establishing relation between the solutions obtained from solving the relaxed problem (P2) compared to solving the original problem (II). We denote the corresponding max- imizers for both problems
x² E arg max (x) and x E arg max(r" kz) ZEX
(47)
zeC.
The following lemma relates both these maximizers together.
Lemma 4. For an RKHS HI with kernel K. satisfying Assumption with constant Lg 0 and any function 8 E H. let x² E X and xi E C. be the maximizers as defined in equation we have
V2CLKE.
(48)
Proof. Denote by 1lc, (x*) arg minzec, || æl12 the projection of the point x onto the set C. Then, we have
(xxx) - f* (x²z = (x)) (IIc, - (x
S 2eltxce
This completes the proof of the lemma.
The above lemma shows that solving Problem P2 is equivalent to solving Problem PT up to an additive factor of /2el.ge when we working with an e-cover the domain space.
19

---

Under review as a conference paper at ICLR 2022
C.2 ANALYSIS FOR BANDIT OPTIMIZATION
Recall from the previous section that the quantity which determines the rate of decay is the ratio of eigenvalues
Pr. Pr.j
C G=
pr..j
Prs
where Prg is the 5th eigenvalue of the kernel matrix K. Let us denote by IP denote the uniform distribution over the input space X' and let us suppose that the cover Neov formed using random samples from this distribution. Let us denote by {1z} the eigenvalues and by Φ the corresponding eigen vectors of the Mercer kernel IC. For every point x E X. let us denote by
(xx) = (x)))
the corresponding featurization of the point æ. Then, for S = E (x))(()) JI we have (x)] 15
[5 (())))l((())))))))))) II,, Ee VEw.ellVyyvve Myy /
(49)
Observe that the kernel matrix K and the (scaled) sample covariance matrix Neov = Exec (xx) ( are similar matrices and thus have the same eigenvalues. The following lemma, adapted from Koltchinskii & Lounici (2017 Theorem 9) relates the eigenvalues of the sample co- variance matrix S to those of the underlying kernel K.
Lemma 5. For any Xs >> and size of the cover satisfying Neo (E) > (e(S(5+)a1) log (1).
we have,
B s (1+ + Ages for all
(50)
with probability at least 1
The following corollary of Lemma 5 provides us with a way to control the deviation of the eigen- values jú from the corresponding μj multiplicative manner.
Corollary 4. For any value of decay parameter 3 >> 1 and < 3, we for all j, the eigenvalues
3
No1
AJ S 2
"j 2
(51)
with high probubility.
Proof. Let us understand the condition (cov(E) 1r(S(S+As\) and see what restrictions it puts o
on the value of the covering number. Lets suppose that the true eigen values Mj X jー and we set the value of Äs x New.. Therefore, the sum
j-B
Σ Lj
S Neov
Σ jーf
New
N>N
3 +
Ncov
S Neo
8 8-1
Thus, if we set es = 1. then for any 8 > 1 and < B, the above condition on the covering number will be satisfied and we get desired bound on the deviation of the empirical eigenvalues from population eigenvalues.
The above corollary is essential to our argument because often times we have good understanding of the decay of the eigenvalues of the kernel K. associated with the RKHS and this allows us to relate the set of empirical eigenvalues to these.
We now present proof of Theorem restated below, which upper bounds the excess risk for this setup. We will then use a batch to online conversion bound to convert this to a regret bound and specialize to the Matérn kernel later.
20

---

Under review as a conference paper at ICLR 2022
Theorem 5 (Restated Theorem Suppose that the eigenvalues of Lip-iishhitz kernel K. with respect to distribution P over satisfy the power-law decay μJ x j Let øplug be the output of Algorithm using queries the oracle Or.. Then, for any value of r (1+ log(1/e) e E (0, 1), the excess risk
(3) and
Ing(Txx/c2)
max (x)) ((ppu))) S
Noov 242 (c) 2:
Neov (e) + LIKE
with high probability.
Proof. Our strategy, as before, will be to explore n² directions and assume r² = 1. Recall, that for symmetric matrices, Theorem the excess error of the plug-in estimator can be upper bounded
E ( r
) Xzeg sup f21
v Pr.
sup n2 f21
1203
Bounding Bias. We will split the analysis into two cases.
Case 1: j na. For this case, we have that oj and therefore
Pej sup
2 sup jun Neghrr.
Neouly sup New + Neoi) S Neoun -f0 + Now>
(52)
j>n
jkn
with the above holding with high probability from an application of Corollary 4 for any Case 2: n²_ For this case, have a, Hry The bias then be upper bounded as
< < 3.
Teg sup j'nn
S
Areggt
(53)
ue n unis
Nightna p
where the final inequality follows from using a² + 2 2ab.
Bounding variance. As did the section above, let us split the analysis into cases.
Case 1: j > n For this case, the variance term simplifies to
1 sup n j>m"
1 sup n2
N2 cov X n
N2 n 2a, +
N2
2-1111))
N22 1
sup j>n
[
2 u
PPgg
juna
X n2
(54)
Case 2: j S n²" For the second case, we can upper bound the variance term
p X2
n
20
sup jSno
(55)
Negg
where the last inequality follows from ignoring the second term in the denominator.
Setting regularization parameter. From the analysis in the above paragraphs, we have
2 < imax(Noovl) a03 + N! >rregn < max max(Ncow
-08 >regg
+
Nd->
(56)
N2 N n 2008 + 22
2a
N2 con -2a
20
22(117)
Variance & max
max
(57)
X2gg n
X2 A2Eg n
n
Xa.g
For regularization parameter Xreg
Neout aB and
aB
we have
log, Now
Bias I >reg
+ NNl-x.
20 <
Variance
21

---

Under review as a conference paper at ICLR 2022
Excess risk bound.
To obtain the final excess risk bound, we 1+log, New B+2
AregTt " + n2a
El (Aplui
n + No
co -a + n 22-1 + Now
gं Nev n n+ + Noov",
(58)
where inequality (i) follows from our particular choice of a. Combining the above bound with Lemma completes the proof.
The following corollary instantiates the above theorem for the case when the input space is the unit ball, that is, = (a()).
Corollary 5. Let the input space X [Ba(1) and the kernel K. satisfy Assumption 2 Then, for any
B B> 2. we have
max (x)
(x) - E (x) S LK 242222 223322222)
(59)
Proof. From the bound in Theorem
we have,
max (2) - Bow (z) Neov (e) n 2542) + Neo (e) + Lice
2²
2
n 2(+22
Neov
+
LK
Lx
d(1-1
i
P12
Lx
2
K
71
+ E
+ 2E
(60)
where inequality (i) follows from substituting e +
2/ (ii) follows from the fact that
(eo (t) and (iii) follows from using the assumption that B > <>>>>> 1+ 2 log(1/c) logtLx/e=]
Finally, setting LE 13 we get
max / (x:) E, Ex ("
LK
242+22 n
This establishes the desired claim.
C.3 REGRET BOUND FOR MATÉRN KERNEL
In this section, we specialize the bound from Theorem for the special class Matérn kernels. Recall that the Matern kernel is distanced based kernel with K(x, v) f(] wll). Denote by r == | y/|, the exact form for the kernel is given by
21-v T(v)
/2VT
/2ur
KMatern, (r)
K,
(61)
with parameters v and / and where K, is the modified Bessel function of the second kind. Going forward, lets fix the scale parameter | without loss of generality.
The following lemma then bounds the Lipschitz constant for this class of kernels when the distance function is the E, norm.
Lemma 6 (Lipschitz Matérn Kernel), Consider the Matérn kernel with parameter v > Lipschitz constant of this kernel is bounded by
2. The
2-2 22"KvK,-i vKy-1(1) V20r
Lx < sup
(62)
I(v)
rE(0.1)
22

---

Under review as a conference paper at ICLR 2022
Proof. The approach will be to show that the kernel function Materm, is Lipschitz function of the distance and then cover the lz ball in the dimensional space appropriately. We now look at the derivative of the function M (r) with respect to
MoMatern, (r) 21-u(v22 2V22()
pr (pr" (v(V (Vo2vrr +r" a"k
l(v)
2 - (V20)" 22''
(ol--KK(V2ii) - (V20Kn-1(V2r)) (
DV22
) dr
Ky Kx (v2v))
I'(e)
/2vr
2 (V22("
(P'V2KK- Ör
(63)
I(t)
where (i) follows from the identity (z, = 1-Ku-1(2) (z)(2))
For any v > we have the inequality
(x)x)
exp"-= y
for 0 <
(64)
Ky)
Instantiating the above with y = 1 and
have
[0KMatem.. (r)) 22-M(V2v)
4" vVv2v. e V2vr V2vr
(V2ur)u-1 eKv- (1)))
((v)
22 vKK-1(1
Tre Veor
(65)
T(v)
The Lipschitz constant for this case can now be obtained by taking sup over (0,
While upper bound in terms of sample complexity, in order compete with the cumulative regret formulation, we adapt an explore-then-commit strategy. The following lemma relates the sample complexity bound to cumulative regret bound.
Lemma (Batch to online conversion). Suppose an algorithm has sample complexity O(n-a)) in the passive learning setup, the explore then commit strategy based on this learning algorithm would have regret ((T [+x
Proof. For some parameter >> 0, let the explore then commit algorithm explore for T steps and the commit to the strategy obtained post this exploration for the remaining T time steps. The cumulative regret for such an algorithm is
Ry = T +
(T
T & T +11-y
(66)
Setting
1_ finishes the proof.
I4a
We now proceed to prove Corollary which instantiates the bound in Theorem 3 for the class of Matérn kernels.
Corollary (Restated Corollary 3) Consider the family of Matérn kernels with parameter defined with the euclidean norm over Rdd. The T T-step regret of the explore-then-coee algorithm
RM 5
L
with high probability.
Proof. First, observe that excess risk bound in Corollary 5 can be converted to a corresponding T-step regret bound by application of Lemma such that
2844-4d
Ry S 0
[
33444-44
(67)
23

---

Under review as a conference paper at ICLR 2022
For the class of Matérn kernels, the decay parameter 3 = + Using this wit the above regret bound, we get,
2v d'
(Janz et al. 2020 Theorem 9).
Mat. 20
2u4d(3+22)
4u4-016--dd) (
This completes the proof.
D ADAPTIVE SAMPLING VIA GP-UCB
In this section, we prove an upper bound on the expected risk of the Gaussian process upper con- fidence bound algorithm (GP-UCB) algorithm of (Srinivas et al. (2010). In order adapt their algorithm for our setup, consider the function
(x) (r, Ma)E, such that D fa |al|e, 1).
(68)
We have used r to denote policies in this setup to be consistent with the notation in Srinivas et al. (2010). Observe that the domain defined above is not compact necessary condition for the algo- rithm to work. One work around this is to truncate the unit ball after finite number of dimensions and bound this truncation error. The excess risk incurred by this truncation can be made arbitrary small. Going forward, we ignore this truncation. The regret for the UCB algorithm is shown to be upper bounded by ((TTVT) where "T is the information gain with
1 log det(I + xx)xx,,)))
TT Fr. 2
(69)
where we have assumed without loss of generality that the noise variance 1. For our setup, the kernel function K(I;, x,) = (Mx; Mæz)H, We additionally require that the reward function
r belongs to the RKHS spanned by the set {Mx / x E D}. Denote by S = S M 52 and suppose that its eigenvalues satisfy power law decay with (S( = S = jー The following lemma upper bounds the information gain for this setup in terms of the power law parameter B > 0.
Lemma (Information Gain.). The information gain "r for the above setup is bounded as
O(log(T) .Te41).
(70)
Proof. The quantity of interest here the information gain
Tr == max log det(T + XSXT) such that Vj | S 11,
(71)
#I Er. 2
where the matrix X [ :..:; setup described above, have that the eigen values of S decay as X j-. It easy that
; T1] and we have assumed that the noise variance is 1. From the
Fig (1x))) = log det(1 + XSXT)
(72)
a monotonic sub-modular function. Thus, the value of fr can be upper bounded by (1- 1/e) times the value of the greedy maximization algorithm. The greedy maximization algorithm is equiv- alent to picking
It arg max Fig (X,-1 U {z))
It is easy to see that at each time t, the unit vector will be an eigen vector of the matrix S. Given this observation, we can finally upper bound the value of the info gain
Σ log(1 myAs) such that my 2 0 and Σ mm,=1 T.
TT
Solving the above optimization problem, the optimal choice of the variables
m, = max
Ag 0 and Σ m, = T
(73)
24

---

Under review as a conference paper at ICLR 2022
Setting 7- गीं ensures that there are TDiT active directions. Substituting the above values of my in the expression for yr, we get
A
TT S c.
log(1 + max
1,0))
==1
A1
S e. log
T
Ollog( (T) .TFT),
where (i) follows from setting À = T #FT This establishes the required claim.
We are now ready to state this our sample complexity bound for GP-UCB for this subclass of prob- lems.
Proposition 2 (Sample complexity for GP-UCB). Suppose that the police space IH reward space H., and the map M satisfy the power law decay assumption with exponent B > 0. The estimator Ruc output by the GP-UCB algorithm satisfies
8-1 E (Tucii r"]] S Ö(n T6+
(74)
The proof of the sample complexity bound in Proposition now follows the regret bound of Ó(rrVT) along with using the upper bound the information gain from Lemma
E A r²]] Ö 1) Ö(
P-1 2(
(75)
More recently, Cai & Scarlett (2021) extended the analysis of Valko et al. 2013 to show that the SupKemelUCCB algorithm achieves regret bound TT Using this modified bound, one can improve the above analysis obtain excess risk
r r*]] (Apug:
Ö(n スलका B) Ö(n 2(641]
(76)
which is still worse than those obtained by the bounds by our proposed ridge regression estimator.
E FURTHER DETAILS ON EXPERIMENTAL EVALUATION
In the simulation study, work with d dimensional RKHSs H, and H,, In order simulate the nonparmeteric regime, we typically use value of n which are less or at most a constant times the dimension d. We the matrices S,- diag(j-1.75), S, diag(j-1) and the map M I. This is allowed since the policy space is smaller than the reward space. With this, the effective decay parameter ( 3 8, 0.75. We sampled the true reward y* uniformly at random from the unit ball in H.. We further sampled the oracle noise ~ (0,, 0.01). All plots were averaged over 10 runs.
25


Reviews:
[{"review_id": "qgQsrsNHtUr", "reviewer": "Reviewer_qTko", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Overall I feel this is an interesting work and well-written. Section 4 has its value. I have some specific comments below.\n\n1. I feel the setting is very close to the study of simple regret in the pure exploration problem in the bandit community. (2) is essentially the simple regret? I feel it's a bit weird to call (1) an oracle. It's just bandit feedback? Maybe the authors are from other communities but I hope you could relate or comment with bandits language in Section 2. Pure exploration with a simple regret guarantee is a well-studied area where you could refer Bandit Algorithm book. \n\n2. Some important references on GP-bandits are missing. The minimax optimal regret for the Matern kernel of GP-bandits has been solved recently. The rate is T^{(\\nu+d)/(2\\nu+d)}. The upper bound appears in \"On Information Gain and Regret Bounds in Gaussian Process Bandits, AISTATS 2021\" and the lower bound appears in \"On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization, ICML 2021\". The regret bound in this paper is clearly sub-optimal when reducing to GP-bandits. Please correct me if I am wrong. If this is correct, I think it is very important to discuss how the current result can go beyond the GP-bandits setting and how important the nonparametric policy is. And how the current regret bound explains the hardness of more general policy class. \n\n3. I feel it should be cautious to argue passive learning is better than adaptive learning in terms of simple regret. The bound you compare with is not sharp. Actually, in a recent work (Bandit Phase Retrieval, https://arxiv.org/abs/2106.01660), the authors have shown that adaptive learning is strictly better than passive learning (the rate is sharp there). Their model is a strictly sub-class of your model I think. \n\n4. In Section 5, do you require the space of input points to be the full unit ball? Because when you convert your algorithm into an online regret minimization algorithm, the explore-then-commit should not be a good one unless your action set has some good curvature to use, like the full unit ball. \n\n5. How it relates to optimal design? Indeed, in the main section, the word \"optimal design\" does not even appear. If it appears in the title, I feel you should explain what do you mean by optimal design explicitly. ", "summary_of_the_paper": "This paper essentially studies pure exploration in nonparametric bandits setting and provides a simple regret guarantee. The authors generalized the setting to nonparametric policy class. Some new ideas based on minimizing a risk upper bound are proposed. ", "summary_of_the_review": "This paper presents some interesting ideas and generalizes the setting to nonparametric policy class. I hope the authors could clarify their contribution w.r.t the SOTA rate. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "oaoENkmXY_A", "reviewer": "Reviewer_k2hj", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The proposed techniques are shown to yield non-asymptotic excess risk bounds for a simple plug-in estimator based on ridge regression. The general results can be applied to the specific settings of GP-Bandits and are shown to yield competitive regret guarantees for the Matern kernel.\n\nThe paper is readably well written and the proofs are sound which is however mostly borrowed from the existing analysis of GP-Bandits (e.g. Srinivas, 2010). \n\nOne concern with the problem formulation (doubly-nonparametric bandits) is it seems to be closely tied to the framework of GP-Bandits which is well studied in the literature, it is unclear the scopes and motivations of the proposed frameworks beyond that are already covered by GP-Bandits. Can you point out a real-world problem that can not be resolved under the GP-Bandits framework but with a doubly non-parametric bandits framework? Due to the same reason, the proposed ridge regression-based algorithms are also lifted from standard methods used in GP bandits as well as the analysis techniques. So it is hard to appreciate the specific novelties of this paper, or the unique contribution that is missing the earlier works. This does not reflect from the contribution section of the paper as well.\n\nAny comments on the computational complexity of the proposed algorithm given any arbitrary non-parametric reward and policy class?\nFinally, the experimental evaluation section of the paper is extremely weak, there have been no comparisons made with state-of-the-art methods, even the algorithms of Kernelized-MAB as listed in Table 1 which is surprising.\n\nThe paper has some minor typos, e.g. “doubly-nonparameteric” in Pg 2, please proofread the draft thoroughly. A separate problem formulation and technical contributions section would also be helpful for the readers. \n", "summary_of_the_paper": "The paper addresses the problem of reward learning by learning a reward model from human feedback using the optimal design of the queries. Authors address this by essentially framing the problem in the flavor of GP-Bandits that models rewards and policies as non-parametric functions belonging to subsets of Reproducing Kernel Hilbert Spaces (RKHSs) where the learner receives (noisy) oracle access to a true reward and is expected to output a near-optimal (reward maximizing) policy. More precisely they analyze the framework of doubly-nonparametric bandits for theoretically studying the reward learning problem.\n", "summary_of_the_review": "The theoretical findings of the paper are sound but it is hard to appreciate the novelties of this work over the existing techniques and analysis of GP-Bandits. I will be happy to increase the score if authors can precisely point the new challenges overcome by this work and what the one novel idea unique to this work.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "ih2RjBvbIa6", "reviewer": "Reviewer_oTMH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This is a solid contribution in an impressively general setting, which I believe be interesting to many working in this area and inspire future work. The challenge is well motivated in the introductory sections and the theoretical results show the proposed approach has strong performance. I have not been able to fully check all of the mathematical work in the appendices, but what I have inspected seems to be accurate and non-trivial. While I am assigning a positive score, I think the exposition around the improvement over UCB-style algorithms could be improved. \n\nPresently, there is a comment saying that you believe the improvement in terms of the theory is due to the proposed approach being a better approach rather than some gap in the theory. This doesn’t feel as strong as it could be – could you supplement this with some more details as to what features make the difference? It is, as you identify, quite a surprising result that popular adaptive algorithms are theoretically outperformed by passive approaches. Could some of the elements of this passive approach be employed to produce a yet stronger adaptive approach in future work do you think?\n\nMinor Comments\n•\tTypo near the bottom of page 2: “GP-UCB and GP-TS are only yield sub-linear”\n•\tTypo in second para of Section 3: “Such general plug-in procedure have”\n", "summary_of_the_paper": "This paper is motivated by learning optimal actions in tasks where both the reward function, and policy (actions) are nonparametric. Previous literature has typically only considered one of these two components as being nonparametric. The main focus is on reliably identifying a policy with low instantaneous regret/risk via as few queries as possible, where all queries are specified in advance (i.e. the passive query setting). The proposed approach selects query locations based on an eigenvalue decomposition of the policy space, sampling repeatedly along a set of top eigenvectors to ensure reliable estimation of the reward via a plug-in ridge-regression-based regression. This estimated reward function is then minimised over the policy class to return a suggested policy/action. The accompanying theory shows the decay of the risk of this suggested action, and shows that in the setting of the Gaussian Process bandit, this can enjoy a better rate than existing adaptive approaches such as GP-UCB. ", "summary_of_the_review": "I am positive about this submission, I think it is interesting, innovative and potentially very impactful. The results are impressive, though I think there is an opportunity to give a bit more insight as to the conceptual reasons for the more surprising aspects of the results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "dmR9cabK3K", "reviewer": "Reviewer_kffS", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Technical correctness:\n\nI did not check the proofs in detail. As far as I see the results are consistent with the literature and I do not have any particular concerns.\n\nClarity:\n\nThe writing is technically reasonable (see the minors for some exceptions). The paper does not help the reader very much developing intuitions. You could write, for example, what the algorithm is doing in the finite-dimensional linear setting. At the same time, I would encourage the authors to spell out where is the novelty in their analysis. What technical barrier has been overcome? What parts of the proof would be most interesting and most useful in future analysis?\n\nNovelty:\n\nI am not a super expert on kernel methods for bandits. I am a little surprised that the basic results are new. I suppose experimental design is already a little bit niche. Anyway, someone more expert than me should probably comment on the novelty.\n\nOther comments:\n\n(1)\n\nIt is interesting that an improvement in the rate of the cumulative regret is possible relative to UCB. The author could explain a little more why this is possible. My own guess is that the non-sequential way the data is collected leads to an improved dependence on the effective dimension, which in the kernel setting is coupled to the horizon. This effect appears in the finite-dimensional setting where the phased algorithms achieve a bound of sqrt(d T log(k)) with k the number of actions and d the dimension. UCB one obtains only d sqrt(n).\n\nNote that explore-then-commit in this setting yields a suboptimal T^{2/3} rate, but the dimension dependence is improved by using the non sequential estimators.\n\nAn obvious question this raises is whether or not a phased elimination algorithm using your risk bounds can improve even further. The algorithm I am proposing would operate in phases m=1,2,... with the number of interactions in phase m being 2^m. Within each phase the algorithm would use the same procedure as your simple regret algorithm to collect data and then eliminate policies based on confidence intervals.\n\nDoes this idea lead to an even better rate? If not, can you explain why? Note you will need high probability confidence intervals for this. But I guess you are (could) derive them already for your analysis.\n\nNote that some previous work also handles the contextual bandit version of this problem, which is not possible using explore-then-commit.\n\n(2)\n\nAnother obvious question is whether or not you can get high probability bounds in Theorem 1. I guess the answer is yes. \n\n(3)\n\nThere is a related literature on best arm identification in linear bandits. Here the algorithms are generally adaptive and the\nbounds depend on the relationship between the policies (actions). For example, [1] below, but there are many more recent papers (see citations to this paper). While these works often study finite (dimensional and action) settings, they do have a problem-dependent nature. It would be interesting to investigate this possibility here.\n\n[1] Soare et al. Best-Arm Identification in Linear Bandits (2014).\n\n(4)\n\nMy last comment is on Assumption 1. How benign is this? And how necessary is it? In the finite-policy linear setting the assumption in general simply does not hold. What is interesting there is that by solving the log-det problem you can nevertheless find a design that yields the same minimax rate independent of the geometry of the policy set. Surely we should wonder if the same is true here. My intuition says yes, since by introducing the effective dimension everything becomes finite. In summary: can we obtain the same results without this assumption by first introducing the effective dimension and then solving a standard D-optimal design problem? If not, why not? If so, why not do it?\n\n\n\n\n\nMinors:\n\n* P2. The regret has not been defined in Table 1.\n\n* P3. \"pi^* \\in argmax ...\" but why should this exist? Some compactness assumption?\n\n* P3. The coefficients mu_pi and mu_r were not explained\\introduced.\n\n* P4. \"policy Learning via reward learning\" -> \"policy learning via reward learning\"?\n\n* P4. There is a missing expectation in the RHS of (7).\n\n* P5. I am not sure if the singular values sigma_j are defined (or I missed where)\n\n* P5. It was not clear to me whether or not the assumption in (9) will be used for the remainder.\n\n* P5. J is introduced abruptly and before it has really been defined.\n\n* P6. \"where the quantity zeta_j = ... for some universal constant c > 0\" -> \"where the quantity zeta_j = ... and c > 0 is a universal constant.\"\n\n* P6. On what does c_pi depend? I think it is a universal constant but the order of quantifiers in the assumption is a bit confusing.\n\n* P6. \"for instance via convexification\" -> can you explain this more?\n\n* P7. \"does not flip the larger eignevectors of ...\" more explanation would be helpful here as well.\n\n* P8. \"we let N_cov(eps) denote an eps-net of\". I guess really N_cov(eps) is the size of an epsilon net. The net itself seems to be C defined in the next sentence? Or this terminology is unfamiliar to me.\n\n* What you call policies are perhaps more commonly called actions.\n\n* What lower bounds do we have in these settings?\n\n* The observation that rates improve when the policy set is the unit ball was observed (in the finite-dimensional setting) by Rustemevichientong et al. Linearly Parameterized Bandits (2010).\n", "summary_of_the_paper": "The paper studies a pure exploration bandit problem in a setting where the reward and policies are assumed to \nbe in RKHS spaces. The main result is a passive strategy based on experimental design and bounds on\nthe simple regret. The results are extended to the cumulative regret setting via a standard explore-then-commit argument.\nIn the latter setting the results are (depending on the kernel) about competitive with the state-of-the-art (more on this later).", "summary_of_the_review": "The paper executes about the first thing you would try. This can be a strength and a weakness. I wish the authors provided more insight in their writing. Not only explaining what holds, but also why and putting in the context of existing work. The paper could be made stronger by investigating any or all of the directions suggested in (1)-(4) above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the reviewers found several interesting points about the paper, they raised several issues, which prevents me from recommending acceptance of the paper. In particular, the paper is not positioned properly in the literature, hence the novelty and the contributions are not properly clarified. The approach of the paper is reasonably simple (which would be a good thing by itself), but there seem to be natural avenues along which more complete results could be obtained, as mentioned in the reviews. Finally, the experiments should be improved (e.g., comparing with other algorithms from the literature). In summary, this is a promising work, but it requires some improvements before it can be published.
Decision: Reject