Year: 2021

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érn kernel.

heading: 1 INTRODUCTION
text: Specifying the reward function accurately for a desired objective, or reward engineering, is challenging to perform by hand, as the consequences of even small errors can be drastic (Hadfield-Menell et al., 2017). To address this, reward learning seeks to learn a predictive model of the reward function 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 (Stiennon et al., 2020; Bö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 of choosing appropriate queries and due to feedback loops from adaptive querying (Freire et al., 2020). Indeed, an ablation study in Christiano et al. (2017) suggests that random queries can outperform or be competitive with adaptive query procedures. To address these issues, we provide a theoretical framework for analyzing reward learning, framing it as a doubly nonparametric experimental design problem. This framework helps elucidate the role of query selection (Chaloner & Verdinelli, 1995) and also enables us to derive scaling laws—how the sizes of the policy and reward models affect the query complexity—for reward learning (Kaplan et al., 2020). Proposed framework. In our framework, we suppose we are given a reward class Cr and policy class Cπ . Our goal is to find a policy π̂ ∈ Cπ that performs well according to an unknown true reward r∗ ∈ Cr. To do this, we query policies π ∈ Cπ , observing noisy estimates of their true reward, and use this information to choose the eventual policy π̂.
To be compatible with modern nonparametric learning methods (i.e. neural nets), we view Cr and Cπ as subsets of Reproducing Kernel Hilbert Spaces (RKHS). The learner therefore optimizes a nonparametric reward function over a nonparametric space of policies, making the task “doubly” non-
parametric. 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 a nonparametric function on a finite-dimensional input space. Conversely, nonparametric supervised learning (Wahba, 1990; Hofmann et al., 2008) minimizes a known loss function over a nonparametric input space.
The doubly nonparametric nature of our task poses new challenges. The (possibly) infinitedimensional RKHS requires the learner to select which subspace to explore given a finite number of queries. Furthermore, the unknown reward function makes it challenging for the learner to reason 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 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 eigenspectrum. 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 as the policy class grows at a slower rate relative to the reward class.
Sharpness of analysis. Our risk bounds apply to reward and policy classes of arbitrary or even infinite 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 Cπ is a compact subspace and thus has finite rank. For these instances, we show that our learning algorithm obtains a better excess risk O(n− β β+2 ) versus a rate of O(n− β−1 2(β+1) ) obtained by the adaptive GP-UCB algorithm (Srinivas et al., 2010), where β > 0 is a power law decay rate.
In Section 5, 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 Matérn kernels with parameter ν in d dimensions, we show that our algorithm achieves a regret bound of Õ(T 4ν+d(4d+6) 6ν+d(4d+7) ) which is strictly better than those achieved by the GP-UCB and GP-Thompson Sampling (GP-TS) (Chowdhury & Gopalan, 2017) algorithms and comparable with π-GP UCB (Janz et al., 2020) and supKernelUCB (Valko et al., 2013; Vakili et al., 2021); see Table 1 for details. GP-UCB and GP-TS are only yield sub-linear regret bounds when the smoothness of the kernel ν > d2—thus in high dimensions, these bounds essentially become vacuous. The π-GP UCB algorithm was designed specifically to overcome this issue. Our proposed algorithm achieves sublinear regret for all ν > 3/2.
Our Contributions. We propose doubly-nonparametric 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 existing algorithms, showing that the doubly-nonparametric lens of reward learning is fruitful even for “singly-nonparametric” tasks. To obtain these bounds, our reduction carefully constructs two different RKHSs to embed the input space and reward function into a policy and reward class.

heading: 2 FRAMEWORK: DOUBLY NONPARAMETRIC BANDITS
text: Our framework considers non-parametric policy learning with non-parametric reward models. We let π ∈ Hπ denote an arbitrary policy and r ∈ Hr denote an arbitrary reward function, where Hπ and Hr are Reproducing Kernel Hilbert Spaces. For technical reasons, we assume the corresponding kernel functionsKπ andKr both satisfy the Hilbert-Schmidt condition (see Appendix A for details). We let F (π, r) ∈ R denote the reward obtained by selecting policy π under reward function r and consider the case where the evaluation functional F is linear in both π and r. In other words, F (π, r) = 〈r,Mπ〉Hr where M : Hπ 7→ Hr is a known linear mapping from the policy space to the
reward space. Since Hπ and Hr may be infinite-dimensional, linearity is only a weak restriction– e.g. the map f 7→ 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∗ ∈ Cr for some known set Cr ⊆ Hr such that ‖r∗‖Hr = 1. We further assume that policies π are restricted to lie in some Cπ 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 π∗ ∈ argmaxπ∈Cπ F (π, r
∗). This proposed framework, which allows for infinite-dimensional 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∗ is unknown to the learner but is accessible via queries to an oracle (e.g. a human expert), which provide noisy zeroth-order (or bandit) evaluations of the reward r∗. When queried with a policy π ∈ Cπ , the oracle provides a response Oracle Or∗ : π 7→ F (π, r∗) + where ∼ N (0, τ2) , (1) with τ2 denoting the variance of the response. There are two possible query models: passive queries (Atkinson, 1996; Sebastiani & Wynn, 2000), where the learner selects all queries at the same time, and active queries (Bubeck et al., 2011; Lattimore & Szepesvári, 2020), where the learner is allowed to select queries sequentially. Our focus in this work will be on the passive query model, but in many cases we will outperform existing active query algorithms.
Problem statement. Given passive access to the oracleOr∗ , the objective of the learner is to output a policy π̂ ∈ Cπ that has small excess risk ∆, defined as ∆(π̂; r∗) : = F (π∗, r∗)− F (π̂, r∗) . (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 & Szepesvári, 2020).
Representations in `2(N). By Mercer’s theorem, we can represent any RKHS as a subset of `2(N). Formally, the policy and the reward spaces are isomorphic to the ellipsoids
Hπ : = { ∞∑ j=1 κπ,jφπ,j ∣∣∣ (κπ,j)∞j=1 ∈ `2(N) with ∞∑ j=1 κ2π,j µ2π,j <∞ } and
Hr : = { ∞∑ j=1 κr,jφr,j ∣∣∣ (κr,j)∞j=1 ∈ `2(N) with ∞∑ j=1 κ2r,j µ2r,j <∞ } ,
for appropriately chosen eigenfunctions φπ,j and φr,j , and corresponding eigenvalues µπ,j and µr,j (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 of notation, going forward, we will use π and r to denote the corresponding coefficients (κπ,j) and (κr,j) in the expansion above. 1 With this, the
1While the eigenfunctions φπ and φr can be different, this representation can still be used by modifying the map M appropriately. This is detailed in Appendix A.
Algorithm 1: Policy Learning via Reward Learning Input: Number of queries n, policy set Cπ , oracle Or∗ Select n policies Q = {π1, . . . , πn} and receive noisy reward evaluations yi = Or∗(πi). Estimate r̂ using observed responses {(π1, y1), . . . , (πn, yn)} using ridge regression (4). Obtain plug-in policy π̂plug ∈ argmaxπ∈Cπ F (π, r̂). Output: Policy π̂plug
inner products associated with Hπ and Hr simplify 〈π1, π2〉Hπ : = ∞∑ j=1 π1,jπ2,j µπ,j and 〈r1, r2〉Hr : = ∞∑ j=1 r1,jr2,j µr,j . (3)
Also let Sr : = diag(µ−1r,j ) and Sπ : = diag(µ −1 π,j) be diagonal matrices comprising the inverse of the eigenvalues of Hr and Hπ . With this notation, if we view the map M as a (infinite-dimensional) matrix, its Hermitian adjoint2 is equal to M∗ = S−1π M >Sr.
In order for the evaluation functional F (π, r∗) to be finite for all π ∈ Hπ , the operator norm ‖S 1 2 r MS − 12 π ‖op must be bounded (see Appendix A). We will see later that the decay of this operator’s singular values is closely related to the difficulty of learning in our setting.

heading: 3 ALGORITHM: POLICY LEARNING VIA REWARD LEARNING
text: Given the setup above, we now describe a meta-algorithm, policy learning via reward learning (Algorithm 1), for the non-parametric policy learning problem. The algorithm is a three-stage procedure: it (i) selects a subset of policies Q to query for reward feedback, (ii) uses the responses to learn a reward estimate r̂, and (iii) optimizes this learnt estimate to output the policy π̂plug, that is, π̂plug ∈ argminπ∈Cπ 〈r̂,Mπ〉Hr . Such general plug-in procedure have been studied in the statistics (Van der Vaart, 2000) and the machine learning (Devroye et al., 2013) literature. We analyze the excess risk of this estimator for our doubly-nonparametric 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 as well as the choice of query set Q.
Reward learning via ridge regression. We estimate the reward r̂ via ridge regression in the RKHS Hr (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 {(πi, yi)}ni=1 represent the query-response pairs. For a regularization parameter λreg > 0, the ridge regression estimate of the reward function is
r̂ ∈ argmin r∈Hr
1
n n∑ i=1 (yi − 〈r,Mπi〉Hr )2 + λreg‖r‖2Hr . (4)
The parameter λreg, which is usually set as a function of n, controls the bias-variance trade-off in estimating r∗—smaller values of λreg reduce bias while larger values help reduce variance.
Excess risk bound for fixed query set. Observe that the plug-in estimator π̂plug(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
Q = argmin S:|S|≤n E[∆(π̂plug(S); r∗)] . (5)
However, solving the above precisely requires knowledge about the underlying reward function r∗, and the combinatorial nature of the optimization problem makes it hard to find an exact solution. To address this, we first upper bound the excess risk of the plug-in policy π̂plug in terms of the query set Q = {π1, . . . , πn}. The following theorem3 bounds the excess risk in terms of the spectrum of the spaces Hr and Hπ , as well as the covariance matrix of the queried policies ΣQ : = 1n ∑ π∈Q ππ >.
2Recall the Hermitian adjoint of M satisfies 〈r,Mπ〉Hr = 〈M∗r, π〉Hπ 3Throughout the paper, for clarity purposes, we denote by c a universal constant whose value changes across
lines. All our proofs in the appendices explicitly track this constant.
Theorem 1 (Excess risk of plug-in). For any query setQ consisting of n policies and regularization parameter λreg > 0, the excess risk of the plug-in estimator π̂plug is upper bounded as
E[∆(π̂plug; r∗)] ≤ 2E[‖M∗(r∗ − r̂)‖Hπ ] . (6)

heading: In addition, letting A = MΣQM>Sr + λregI , the expected squared distance is equal to
text: E[‖M∗(r∗ − r̂)‖2Hπ ] = λ 2 reg · ‖M∗A−1r∗‖2Hπ +
τ2 n · tr [ Sπ(M ∗A−1M)ΣQ(M ∗A−1M)> ] . (7)
The proof follows a standard analysis of ridge regression and is deferred to Appendix B. Observe that in the above theorem, the query set π ∈ Q participates in the excess risk only via the covariance ΣQ. 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, ΣQ 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 a constant excess risk, since for those directions the matrix A ≈ λregI . As shown later in the appendix, in the special case when the policy set consists of the entire unit ball Cπ = {π ∈ Hπ | ‖π‖Hπ ≤ 1}, the excess risk bound can be improved by a quadratic factor: E[∆(π̂plug; r∗)] ≤ O ( ‖M∗(r∗ − r̂)‖2Hπ ) . Such a phenomenon was first observed in the finitedimensional setup by Rusmevichientong & Tsitsiklis (2010).

heading: 4 QUERY SELECTION AND STATISTICAL GUARANTEES
text: We now show how to select the query setQ effectively and study the excess risk of the corresponding plug-in estimator π̂plug. We will start with the special case where the policy set Cπ is the unit ball in Hπ and the mapM 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 Hπ space. For the special case when the map M is diagonal, this is reduces to querying the top eigenvectors of Hπ .
The excess risk will ultimately depend on the the eigenspectrum of the operator S− 1 2 π M>SrMS − 12 π , which is similar to the operator M∗M . Additionally, to interpret our results, we instantiate them for a power law spectrum with exponent β > 0, that is, σj(S − 12 π M>SrMS − 12 π ) j−β . where σj corresponds to the jth singular value of the corresponding operator. Such power law spectra have been observed in a variety of practical settings, for instance, in the Hessian of trained deep neural networks (Ghorbani et al., 2019).
4.1 WARM-UP: Cπ = UNIT BALL, M = DIAGONAL
In order to get some intuition, we study the special case where the policy setCπ consists of the entire unit ball in the space Hπ and the map M is diagonal with M = diag(νj). Further, let us denote the operator M̃ = S 1/2 r MS −1/2 π .
For this special case, our sampling algorithm (Algorithm 2) simply selects the top J eigenvectors of the space Hπ to query, for some value J which depends on the decay exponent β. 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 πj in our algorithm is simply the scaled eigenfunction √µπ,j · φπ,j . Having selected these J queries, the algorithm queries each one of the nJ 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 knowledge of r∗, any policy π ∈ Cπ can be an optimal policy. By querying the top J ones out of these, 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 n available. Since the oracle responses are noisy, to reduce variance in the responses along those directions, our algorithm performs multiple queries along the same direction.
If we further consider the special case when the policies and rewards correspond to the unit balls in the finite dimensional spaces Rdπ and Rdr respectively, our choice of query set queries the directions
{ei}dπi=1, each for J = ndπ 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 1 (Risk bound for Cπ = unit ball.). For any J ≤ n and regularization parameter λreg > 0, consider the plug-in estimator obtained via the passive sampling algorithm which explores the first J eigenfunctions of Hπ . The excess risk satisfies
E[∆(π̂plug; r∗)] ≤ c · ( 1 + τ2
nλ2reg
) ·max { sup j≤J λ2regJ 2ζj ζ2j + λ 2 regJ2 , sup j>J ζj } , (8)
where the quantity ζj = ν2jµπ,j µr,j and c > 0 is some universal constant.
We defer the proof of the above proposition to Appendix B. The choice of the exploration parameter J allows us to trade-off between the two terms inside the maximum. Typically, the second term will be maximized at j = J + 1. For the first term, the supremum depends on the choice of λreg — for small values of λreg, the sup is achieved at j = 1 while for larger values, it is achieved at j = J . In order to gain more intuition about this bound, we instantiate this for the power law decay. Corollary 1 (Risk bound for power-law decay). Suppose that eigenvalues of the police space Hπ decay as j−βπ , reward space Hr as j−βr and the singular values of map M as j−βM . This satisfies the power law assumption with exponent β = βπ+βM−βr. The plug-in estimator with exploration parameter J = n 1 β+2 and regularization λreg = n− β+1 β+2 satisfies E[∆(π̂plug; r∗)] ≤ cn− β β+2 .
The above bound shows that our algorithm can learn in the framework as long as β > 0 or equivalently βπ + βM > βr, with better rates for larger values of β. Thus, for a fixed size of reward class βr, the learning rate improves as the policy class grows smaller (βπ increases) – this is intuitive since we are required to search over a smaller policy space. On the other hand, for a fixed policy class βπ , our excess risk rate gets better as the reward class grows in size (βr increases) – this is because a larger set of reward functions have similar optimal policies and hence learning gets easier.

heading: 4.2 GENERAL POLICY SETS
text: We now describe our choice of query sets Q for general policy sets Cπ . Our strategy, described in Algorithm 2, differs from the above special case in that we need to take into account the interaction of the policy space Hπ with the map M . Specifically, we show in Appendix B that the upper bound in Theorem 1 can be diagonalized for this general case via a transformation.
Let us denote the operator M̃ = S 1/2 r MS −1/2 π . Our transformation reveals that the relevant directions to query for this general case corresponds to the columns of ΦπS −1/2 π Φ>π VM where , then VM are the eigenvectors of the self-adjoint operator M̃>M̃ – and it is precisely a subset of these directions that our algorithm queries.
In order to be able to 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 1 (Regularity assumption on Cπ). For any eigenfunction φM̃,j of the operator M̃ >M̃ , consider the policy πj = ΦπS −1/2 π Φ>π φM̃,j . There exists a policy π̃j in policy set Cπ such that for some constant cπ > 0, we have π̃j π̃>j cππjπ>j .
The above assumption requires that for every choice of the policy πj in Algorithm 2, the set Cπ has the another policy π̃j 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, a generalization of Proposition 1, provides a bound on the excess risk for the plug-in estimate for general policy sets Cπ . Theorem 2 (Risk bound for general policy sets Cπ .). For any J ≤ n, regularization parameter λreg > 0 and set Cπ satisfying Assumption 1, let π̂plug be the estimator output by Algorithm 1. The squared excess risk satisfies
(E[∆(π̂plug; r∗)])2 ≤ c · ( 1 + τ2
nλ2reg
) ·max { sup j≤J λ2regJ 2ζj ζ2j + λ 2 regJ2 , sup j>J ζj } ,
Algorithm 2: Passive querying strategy Input: Number of queries n, map M , policy set Cπ , exploration parameter J Construct linear map M̃ = S 1 2 r MS − 12 π and compute eigenvectors {φM̃,j}j of operator M̃>M̃ Set policy πj = ΦπS − 12 π Φ>π φM̃,j for all j ≤ J Obtain policy π̃j ∈ Cπ such that π̃j π̃>j cππjπ>j Form query set Q = {π̃(n/J)1 , . . . , π̃ (n/J) nα } where a(b) = {a, . . . , a}} repeated b times Output: Query set Q
where the values ζj correspond to the jth eigen values of the operator M̃∗M̃ with M̃ = S 1 2 r MS 1 2 π .
We defer the proof of this theorem to Appendix B. The proof of this theorem goes via a transformation which diagonalizes the excess risk bound and reduces the problem to a similar setup as that of Proposition 1. Additionally, Assumption 1 allows us to generalize the results to arbitrary policy sets Cπ . Note that the above upper bounds the square of the excess risk. As discussed in Section 3, 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 2 (Risk bound for power-law decay). Suppose that eigenspectrum of the operator S− 1 2 π M>SrMS − 12 π satisfy the power law assumption with exponent β > 0, that is, σj(S − 12 π M>SrMS − 12 π ) j−β . The plug-in estimator π̂plug with parameter J = n 1 β+2 and regularization λreg = n− β+1 β+2 satisfies E[∆(π̂plug; r∗)] ≤ cn− β 2(β+2) .
The above bound indicates that for the general case, learning is possible if the spectrum decay has parameter β > 0. 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 Hπ towards the smaller eigenvectors of Hr, that is, the map M preserves the ordering of the eigenvectors of Hπ when transformed to the space Hr. Such a misaligned scenario would require learning a very accurate representation of the reward to learn a good policy and will make learning harder.

heading: 4.3 COMPARISON WITH UCB-STYLE ADAPTIVE ALGORITHMS
text: 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 singly-nonparametrics algorithm by taking a finitedimensional 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 GPUCB algorithm (Srinivas et al., 2010) provides a rate of O(n− β−1 2(β+1) ), which is strictly worse than the O(n− β β+1 ) obtained by our analysis in Corollary 1. We refer the reader to Proposition 2 in Appendix D for an 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 are comparing upper bounds for the two algorithms, we believe that our 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, 2021), 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 et al., 2021) are known to yield suboptimal regret rates and it is an open question as to whether these can be improved.

heading: 5 NEW BOUNDS FOR KERNEL MULTI-ARMED BANDITS
text: In the previous subsection, we saw that our passive sampling algorithm actually outperforms existing adaptive sampling algorithms for the reward learning task we care about. Here we take this a step
further—we specialize our algorithm to the case of kernel MABs, and show that it outperforms standard algorithms for that setting and is competitive with a specialized algorithm for Matérn kernels.
We consider the task of maximizing an unknown function f∗ : X 7→ 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 kernel4 K, such that ‖f∗‖H = 1. Let us further restrict our attention to the space of input pointsX = {x ∈ Rd | ‖x‖2 ≤ 1}. The learner is allowed to access this function via a noisy zeroth-order oracle Of∗ : x 7→ f∗(x) + ηwhere η ∼ N (0, τ2). Going forward we will assume that τ = 1. The above oracle is similar to the reward oracleOr∗ , except that the query points x belong to a 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∈X f∗(x)− T∑ t=1 f∗(xt) , (9)
where xt is the datapoint queried in the tth 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 specialpurpose 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 3, are better than several general purpose algorithms (GP-UCB, IGP-UCB, GP-TS) and comparable to those specialized for the Matérn kernel (π-GP-UCB).
In order to reduce kernel MAB to our framework, we need to introduce three elements – the policy space Hπ , the reward space Hr and the map M . We would like spaces Hr and Hπ such that (1) the resulting objective F (r, π) 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 -net of the input space X under the `2 norm and denote its size by Ncov( ). We define the kernel matrix K ∈ RNcov×Ncov on points selected in the cover as K(i, j) = K(xi, xj) for all (xi, xj) ∈ C × C . Reward space Hr. Given the RKHS H 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 RNcov( ). More precisely, letting f̃ = [f(x1), . . . , f(xNcov)] denote the vector of evaluations of a function f , we define
Hr : = span{f̃ | f ∈ H} with 〈f̃1, f̃2〉Hr : = f̃>1 K−1f̃2, . (10)
With this notation, we define the true reward r∗ : = f̃∗ = [f∗(x1), . . . , f∗(xNcov)].
Policy Space Hπ . Similarly to rewards, we will embed policies in RNcov . For any point x ∈ C , let kx = [K(x, x1), . . . ,K(x, xNcov)] denote the corresponding vector in RNcov obtained by evaluating the kernel K over the cover. Then, the space
Hπ : = span{kx | x ∈ C } with 〈k1, k2〉Hπ : = 〈k1,K−2k2〉 . (11)
The choice of the above norm ensures that 〈ki, kj〉Hπ = 〈K−1ki,K−1kj〉 = δi,j for all (xi, xj) ∈ C × C . Thus in particular, Hπ contains an orthonormal embedding of the set of vectors {kx}x∈C . Map M . Both the reward space Hr and policy space Hπ can be associated with RNcov . Under this transformation, the evaluation f∗(x) for any x ∈ C corresponds to the standard inner product with F (r∗, πx) = f
∗(x) = (f̃∗)>K−1kx = 〈r∗, kx〉Hr . This indicates that we should take the map M to be the identity. Furthermore, as a simple application of Mercer’s theorem it follows that this map M is a bounded linear operator.
We make an 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 Matérn kernel when ν > 3/2. Assumption 2 (Lipschitz Kernel K). The Kernel K associated with the Hilbert space H is LKLipschitz with respect to the `2-norm for some LK > 0: |K(x, y) − K(x, x)| ≤ LK‖x − y‖2 for all x ∈ X , y ∈ X . Furthermore, the kernel satisfies K(x, x) = 1 for all points x ∈ X .
4We require that the kernel K be a Mercer’s kernel satisfying K(x, x) = c for all x ∈ X .
Applying Theorem 2 under the above assumption, we obtain the following excess risk bound for the plug-in estimator evaluated on the unknown function f∗. Theorem 3 (Excess risk for Kernel MAB). Suppose that the eigenvalues of a LK-Lipschitz kernel K satisfy the power-law decay µj j−β . Let x̂plug be the output of Algorithm 1 using n queries to the oracle Of∗ . Then, for any value of β > 1 + 2d + log( 1 δ ) and ∈ (0, 1), the excess risk satisfies
max x:‖x‖2≤1
f∗(x)− f∗(x̂plug) . N 1 β+2 cov ( ) · n −β 2(β+2) +N 1−β 2 cov ( ) + √ LK ,
with probability at least 1− δ.
For Matérn kernels, it is known that the eigenvalues decay with parameter β = 1 + 2νd (Janz et al., 2020). Using this, we can obtain the following corollary. Corollary 3 (Regret bound for Matérn Kernel). Consider the family of Matérn kernels with parameter ν > 32 defined with the Euclidean norm over R d. The T -step regret of our algorithm is
Rmat,T = Õ ( T 4ν+d(6+4d) 6ν+d(7+4d) ) .
The above bound is for regret, which is an online notion, while our previous results are offline notions. We get from one to the other using a standard batch-to-online conversion bound based on an explore-then-commit strategy. Table 1 compares the above bound to the existing bounds in the literature. While the bounds for GP-UCB and GP-TS become vacuous for ν . d2, our bound from Corollary 3 is always sublinear in T .

heading: 6 EXPERIMENTAL EVALUATION
text: We experimentally evaluate our algorithm via a simulation study. We use these experiments to establish the dimension free nature of our results as well as to conjecture optimality of our bounds.
Setup. In the simulation study, we work with d dimensional RKHSs Hr and Hπ . In order to simulate the nonparmeteric regime, we typically use value of n which are less or at most a constant times the dimension d. We set the matrices Sπ = diag(j−1.75), Sr = diag(j−1) and the map M = I . With this, the effective decay parameter β = βπ − βr = 0.75. We further sampled the oracle noise ∼ N (0, 0.01). All plots were averaged over 10 runs. Observations. Figure 1(a) shows the variation of excess risk as the number of queries n are varied from 256 to 4096 on a log-log plot. Our bounds in Corollary 1 for this setup predict that the excess risk should decay at a rateO(n−0.27). By fitting a linear line through the plot, we found that observed risk to vary as O(n−0.28). This plot is suggestive of the fact that our theoretical upper bounds might be tight in a minimax way over choices of decay parameter β. In Figure 1(b), we plot the excess risk as we vary the dimension d from 32 to 8192 for four different choices of sample size, again, on a 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-vacuous bounds for the doubly-nonparametric setup in the regime d→∞.

heading: ETHICS STATEMENT
text: Our main contribution is a theoretical framework to study reward learning and the associated optimal design problem. Since our contributions are mostly theoretical in nature, we do not anticipate any ethical issues arising in the near future.

heading: REPRODUCIBILITY STATEMENT
text: On the theoretical side, we provide detailed proofs for all our results in the appendix and appropriately 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 to reproduce the experiments.

heading: A TECHNICAL DETAILS FOR PROPOSED FRAMEWORK

heading: A.1 RKHS ASSUMPTION
text: The Hilbert spaces Hπ and Hr are Reproducing Kernel Hilbert Spaces defined by kernel functions Kπ,Kr : X ×X 7→ [0, 1] respectively defined over a compact instance space X . Further, the kernels Kπ and Kr satisfy the Hilbert-Schmidt condition∫
X×X Ki(x, z)2dP(x)dP(z) ≤ ∞ for i = {π, r} , (12)
for some distribution P over space X . Mercer’s theorem (Mercer, 1909) implies that such kernel functions have an associated set of eigenfunctions (with corresponding eigenvalues) that form an orthonormal basis for L2(X ,P). We restate a version of this theorem below (Wainwright, 2019). Theorem 4 (Mercer’s theorem). Suppose that the space X is compact and the positive semi-definite kernelK satisfies the Hilbert-Schmidt condition (12). Then there exists a sequence of eigenfunctions (φj) ∞ j=1 that form an orthonormal basis of L
2(X ,P) and non-negative eigenvalues (µj)∞j=1 such that ∫
X K(x, z)φj(z)dP(z) = µjφj(x) for all j = 1, 2, . . . . (13)
Furthermore, the kernel function has the expansion
K(x, z) = ∞∑ j=1 µjφj(x)φj(z) , (14)
where the convergence of the sequence holds absolutely and uniformly.

heading: A.2 CONDITIONS FOR REWARD BOUNDEDNESS
text: For learning to be feasible in the proposed framework, we would require that the evaluation functional F (π, r∗) is bounded for any policy π ∈ Hπ . Using the fact that ‖r∗‖Hr ≤ 1 and ‖π‖Hπ ≤ 1, we have
F (π, r∗) = 〈r∗,Mπ〉Hr = (r∗)>SrMπ ≤ ‖S 1 2 r MS − 12 π ‖op . (15)
Thus one sufficient condition for the reward functional to be bounded is to ensure that the operator norm ‖S 1 2 r MS − 12 π ‖op is finite. In the special case when the map is diagonal with M = diag(νj), the above condition simplifies to
F (π, r∗) ≤ sup j≥1 νjµ 12π,j µ
1 2 r,j  . (16)

heading: A.3 REGULARITY ASSUMPTIONS ON MAP M
text: We assume that the map M is a compact bounded operator from the policy space Hπ to the reward space Hr. By Schauder’s theorem, the adjoint M∗ is also a compact operator. Thus, the map M∗M : Hπ → Hπ is a compact self-adjoint operator. This allows us to use the spectral theorem for compact self-adjoint operators which guarantees the existence of eignevalues and eignefunctions for the operator M∗M and a corresponding singular value decomposition for the map M (Kreyszig, 1978).

heading: A.4 NON-ALIGNED RKHSS
text: As mentioned in the Section 2, if the eigenvectors of the spaces Hr and Hπ are not aligned, one can consider the following simple transformation which resolves this. Let Φπ and Φr represent the eigenvectors.
r̃ = Φrr, π̃ = Φ > π π, and M̃ = Φ > r MΦπ . (17)
The above transformation implies that ‖r̃‖Hr ≤ 1 and ‖π̃‖Hπ ≤ 1.

heading: B PROOF OF MAIN RESULTS
text: In this section we provide the proofs for the main results of this work. Appendix D to follow contains the proofs for the other results.

heading: B.1 PROOF OF THEOREM 1
text: We begin by proving the result for the special case when the policy set Cπ consists of the entire unit ball and then generalize the analysis to arbitrary policy sets.
Case 1: Cπ is unit ball in Hπ . For this special case, observe that the the optimal policy π∗ and the plug-in policy π̂plug for any reward estimate r̂ can be written as
π∗ = M∗r∗
‖M∗r∗‖Hπ and π̂plug =
M∗r̂
‖M∗r̂‖Hπ , (18)
where the operator M∗ is the adjoint of of the map M . To prove a bound on the excess risk using the plug-in estimate, we use the following lemma which bounds this error in terms a deviation of the estimated and true rewards.
Lemma 1. Consider any vectors x and y with finite non-zero norm under some inner product 〈·, ·〉. Then, we have
〈x, x ‖x‖ − y ‖y‖ 〉 ≤ ‖x− y‖ 2 2‖y‖ . (19)
The proof of the above lemma is presented in Section B.1.1. Taking the above as given, we can upper bound the excess risk
∆(π̂; r∗) = 〈M∗r∗, M ∗r∗
‖M∗r∗‖Hπ − M
∗r̂
‖M∗r̂‖Hπ 〉Hπ
≤ ‖M∗(r∗ − r̂)‖2Hπ
2‖M∗r̂‖Hπ . (20)
Case 2: Arbitrary set Cπ . For this case, consider the excess risk of plug-in estimator π̂plug obtained by maximizing reward estimate r̂
∆(π̂; r∗) = 〈M∗r∗, π∗ − π̂plug〉Hπ = 〈M∗(r∗ − r̂), π∗〉Hπ + 〈M∗r̂, π∗ − π̂plug〉Hπ + 〈M∗(r̂ − r∗), π̂plug〉Hπ (i)
≤ 2‖M∗(r∗ − r̂)‖Hπ , (21)
where the final inequality follows from the fact that π̂plug maximizes F (π; r̂) over the set Cπ .
Thus, we see that for both the cases above, we can upper bound the excess risk of the plug-in estimator in terms of the norm ‖M∗(r∗ − r̂)‖Hπ . Next, we evaluate this for the ridge regression based reward estimator for any set of n queries Q = {π1, . . . , πn} with covariance matrix Σ = 1 n ∑ i πiπ > i . For any regularization parameter λreg > 0, we have,
r̂ = arg min r∈Hr
1
n n∑ i=1 (yi − 〈r,Mπi〉Hr )2 + λreg‖r‖2Hr
(i) = (MΣM>Sr + λregI) −1 · 1 n n∑ i=1 yiMπi
= r∗ − λreg(MΣM>Sr + λregI)−1r∗ + (MΣM>Sr + λregI)−1 ( M
n n∑ i=1 iπi
) , (22)
where and equality (i) follows by substituting the value of yi = F (πi, r∗) + i. Let us denote by matrix A = MΣM>Sr + λregI . Therefore, the error in reward estimation
r̂ − r∗ = λregA−1r∗ +A−1 ( M
n n∑ i=1 iπi
)
∼ N ( λregA −1r∗, τ2
n A−1MΣM>A−>
) , (23)
where the final distribution follows from our assumption on the noise variables i ∼ N (0, τ2). Using this above distributional form, we have
E[‖M∗(r∗ − r̂)‖2Hπ ] = λ 2 reg · 〈M∗A−1r∗,M∗A−1r∗〉Hπ +
τ2 n · tr [ SπM ∗A−1MΣnM >A−>(M∗)> ] = λ2reg · tr [ (r∗)>A−>(M∗)>SπM ∗A−1r∗ ] + τ2 n · tr [ SπM ∗A−1MΣM>A−>(M∗)> ] .
(24)
The final bound for the general policy set Cπ follows from using the above bound with a an application of Jensen’s inequality. In order to convert the above bound to a high probability bound, we require an infinite dimensional analog of the Hanson-Wright concentration inequality. Using Theorem 2.6 from Chen & Yang (2021) along with equation (23), we obtain
Pr(∆(π̂; r∗) ≥ E[∆(π̂; r∗)] + t) ≤ 2 exp ( −C min ( t2
‖Γ‖2HS ,
t
Γ‖op )) where the covariance matrix Γ = S 1 2 πM∗A−1MΣM>A−>(M∗)>S 1 2 π .

heading: B.1.1 PROOF OF LEMMA 1
text: Let the vector y = x+ δx for some difference vector δx. Using this, we have
〈x, x ‖x‖ − y ‖y‖ 〉 = 〈x, x ‖x‖ − x+ δx ‖x+ δx‖ 〉
= ‖x‖
‖x+ δx‖
( ‖x+ δx‖ − ‖x‖ −
〈x, δx〉 ‖x‖ ) (i)
≤ ‖x‖ ‖x+ δx‖
( ‖x‖+ 〈x, δx〉
‖x‖ + ‖δ2x‖ 2‖x‖ − ‖x‖ − 〈x, δx〉 ‖x‖ ) =
δ2x 2‖x+ δx‖ , (25)
where (i) follows from using the inequality √ a2 + z ≤ a+ z2a . This establishes the result.

heading: B.2 PROOF OF PROPOSITION 1
text: Let us denote the the map M = diag(νj) and the covariance matrix Σ = diag(σj). From the upper bound obtained in Theorem 1, we have,
E[‖M∗(r∗ − r̂)‖2Hπ ] = λ 2 reg · ‖M∗A−1r∗‖2Hπ +
τ2 n2 · n∑ i=1 ‖M∗A−1Mπi‖2Hπ
(i) ≤ λ2reg · ‖S 1 2 πM ∗A−1S − 12 r ‖2op + τ2 n · tr [ SπM ∗A−1MΣM>A−>(M∗)> ]
(ii) ≤ λ2reg · sup j≥1
[ ν2j µr,jµπ,j
ν4j σ 2 j + λ 2 regµ 2 r,j
] + τ2
n · sup j≥1
[ ν4j µ 2 π,j
ν4j σ 2 j + λ 2 regµ 2 r,j
] , (26)
where inequality (i) follows from using the fact that ‖r∗‖Hr ≤ 1 and inequality (ii) uses the diagonal structure of the map M as well as the fact that each policy πi ∈ Q has unit Hπ-norm.
Recall that the choice of querying strategy queries each scaled eigenfunction√µπ,jφπ,j of the policy space n1−α times. Therefore the jth entry of the covariance matrix Σ is given by
σj =
{µπ,j nα for j ≤ n α
0 otherwise . (27)
Plugging the above value of σj into equation (26), we obtain
E[‖M∗(r∗ − r̂)‖2Hπ ] ≤ max { sup j≤nα λ2regn 2αζj ζ2j + λ 2 regn 2α , sup j>nα ζj }
+ τ2
n ·max { sup j≤nα n2αζ2j ζ2j + λ 2 regn 2α , sup j>nα ζ2j λ2reg } (28)
This concludes the proof of the proposition.

heading: B.3 PROOF OF COROLLARY 1
text: We now derive explicit finial sample rates for the case when the spectrum of the map M>SrMS−1π satisfies a power law decay for some parameter β > 0. In the notation used in Proposition 1, we have the quantity ζj j−β . (29) Our proof strategy will be to instantiate the bias and variance terms for this setting of ζj and finally select a setting for the exploration parameter α and regularization parameter λreg.
Bounding Bias. The bias term in the proposition is a max over two terms
Bias2 = max { sup j≤nα λ2regn 2αζj ζ2j + λ 2 regn 2α , sup j>nα ζj } . (30)
We consider the two terms in the analysis here separately. For the first term,
sup j≤nα
λ2regn 2αζj
ζ2j + λ 2 regn
2α = λ2reg sup
j≤nα
[ 1
j−β n2α + λ 2 regj β
] ≤ λregnα , (31)
where the final inequality follows from using a2 + b2 ≥ 2ab. For the second term, we have sup j≥nα ζj = sup j≥nα j−β = n−αβ . (32)
Bounding Variance. Recall that the variance term (assuming τ = 1) is given by
Variance = 1
n ·max { sup j≤nα n2αζ2j ζ2j + λ 2 regn 2α , sup j>nα ζ2j λ2reg } . (33)
We again consider both terms of the maximum separately. For the first term,
1 n · sup j≤nα n2αζ2j ζ2j + λ 2 regn 2α ≤ n2α−1 , (34)
where the inequality follows from ignoring the term λ2regn 2α in the denominator. For the second variance term,
sup j>nα ζ2j nλ2reg = n−2αβ λ2regn . (35)
Setting regularization parameter. By setting λreg > n−αβ−α, we can have that the bias term is dominated by λregnα. Similarly, the above setting also implies that the variance term is dominated by n2α−1. Combing these observations, we have that the expected error is upper bounded by
∆(π̂plug; r ∗) ≤ λregnα + n2α−1 where λreg > n−αβ−α. (36)
Setting λreg = n−α(β+1) and then α = 1β+2 , we get that
∆(π̂plug; r ∗) ≤ n− β β+2 . (37)
This completes the proof of the corollary.

heading: B.4 PROOF OF THEOREM 2
text: In order to prove the general theorem, we exhibit a transformation which allows us to reduce the problem to that with the diagonal structure described in Proposition 1.
We will consider orthogonally diagonalizable matrices Sr and Sπ which represent the eigenvectors and eigenvalues of the Hilbert spaces Hr and Hπ . Consider the following set of transformations for any reward r ∈ Cr and policy π ∈ Cπ .
r̃ = S 1 2 r r, π̃ = S 1 2 π π, M̃ = S 1 2 r MS − 12 π . (38)
With this transformation, we can rewrite the objective function above
max π̃ 〈r̃, M̃ π̃〉 s.t. 〈π̃, π̃〉 = 1 and 〈r̃, r̃〉 = 1 ,
where the inner product 〈·, ·〉 denotes the standard `2 inner product. Observe that we have overloaded notation to denote by r̃∗ = r̃. Further, using these above transformations, we can rewrite the adjoint operator
M∗ = S−1π M >Sr = S − 12 π (S 1 2 r MS − 12 π ) >S 1 2 r = S − 12 π M̃ >S 1 2 r . (39)
Recall from Theorem 1, the matrix
A = MΣM>Sr + λregI = S − 12 r [ M̃ Σ̃M̃> + λregI ] S 1 2 r , (40)
where the covariance matrix Σ̃ = 1n ∑ i π̃π̃
>. We have used the fact here that the matrices Sπ and Sr 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̃ = UM̃ΛM̃V > M̃ .
The existence of 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∗ − r̂‖2Hπ ] from Theorem 1.
Bound on bias. The squared bias term is given by
λ−2reg · Bias2 = r>A−>(M∗)>SπM∗A−1r
= r>S 1 2 r S − 12 r · S 1 2 r (M̃ Σ̃M̃ > + λregI) −1S − 12 r · S 1 2 r M̃S − 12 π · Sπ ·M∗A−1r
= r̃>(M̃ Σ̃M̃> + λregI) −1M̃ · S 1 2 π S − 12 π M̃ >S 1 2 r · S − 12 r (M̃ Σ̃M̃ > + λregI) −1S 1 2 r r
= r̃>(M̃ Σ̃M̃> + λregI) −1M̃ · M̃>(M̃ Σ̃M̃> + λregI)−1r̃
= r̃>UM̃ (ΛM̃V > M̃ Σ̃VM̃ΛM̃ + λregI) −1Λ2 M̃ (ΛM̃V > M̃ Σ̃VM̃ΛM̃ + λregI) −1U> M̃ r̃ , (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 = τ2 n · tr [ SπM ∗A−1MΣnM >A−>(M∗)> ] = τ2 n · tr [ M̃>(M̃ Σ̃M̃> + λregI) −1M̃ Σ̃M̃>(M̃ Σ̃M̃> + λregI) −1M̃
] = τ2 n · tr [ ΛM̃ (ΛM̃V > M̃ Σ̃VM̃ΛM̃ + λregI) −1ΛM̃V > M̃ Σ̃VM̃ΛM̃ (ΛM̃V > M̃ Σ̃VM̃ΛM̃ + λregI) −1ΛM̃ ] .
(42)
Finally, by making a substitution for reward r̃ = U> M̃ r̃ and policy π̃ = V > M̃ π̃ in equations (41) and (42), we recover back the bias variance expressions used in the analysis for Proposition 1. What
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
πj = ∞∑ i=1 √ µπ,i · 〈φM̃,j , φπ,i〉φπ,i for j ≤ n α ,
is such that the transformed policies
π̃j = V > M̃ S 1 2 π πj = V > M̃ S 1 2 π · S − 12 π VM̃ej = ej , (43)
indeed correspond to the basis vector. This finishes the proof of the desired claim.

heading: B.5 PROOF OF COROLLARY 2
text: The proof of this corollary follows similar to that of Corollary 1 in terms of bounding the bias and the variance. The final rate follows by an application of Jensen’s inequality to conclude
E[‖M∗(r∗ − r̂)‖Hπ ] ≤ (E[‖M∗(r∗ − r̂)‖2Hπ ]) 1 2 . (44)
The final rate that we get in this case is thus upper bounded by the square root of the rate observed in Corollary 1. This concludes the proof.

heading: C GAUSSIAN PROCESS BANDIT OPTIMIZATION
text: In this section, we discuss in detail the application of our framework to the problem of frequentist Gaussian process bandit optimization, also known as Kernelized multi-armed bandits (MAB) problem. Recall the reduction of the Kernel MAB problem to our setup required us to define three elements.
Reward space Hr. Given the RKHS H 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 RNcov( ). More precisely, letting f̃ = [f(x1), . . . , f(xNcov)] denote the vector of evaluations of a function f , we define
Hr : = span{f̃ | f ∈ H} with 〈f̃1, f̃2〉Hr : = f̃>1 K−1f̃2 , (45)
where 〈·, ·〉 represents the standard `2 inner product. With this notation, let us define the true reward r∗ : = f̃∗ = [f∗(x1), . . . , f ∗(xNcov)].
Policy Space Hπ . For the policy space Hπ in our setup, we let
Hπ : = span{kx = [K(x, x1), . . . ,K(x, xNcov)] ∈ RNcov | x ∈ C } with 〈k1, k2〉Hπ : = 〈k1,K−2k2〉 .
(46)
The choice of the above norm ensures that
〈ki, kj〉Hπ = 〈K−1ki,K−1kj〉 = 〈ei, ej〉 = δi,j for all (xi, xj) ∈ C × C .
For the policy space Hπ , we have created an orthonormal embedding of the set of vectors {kx}x∈C . Observe that this policy set that we construct satisfies the regularity Assumption 1 because each vector k is an eigenvector of the space Hπ .
Map M . By our assumption that the kernel K is a Mercer’s kernel, we have that Hπ ⊆ Hr, that is, for all x ∈ C, the vector kx ∈ Hr. Furthermore, both Hr and Hπ are sub-spaces of RNcov and we can take the map M = INcov .
With these definitions, we now explicitly establish a correspondence between our doubly nonparameteric bandit problem and the Kernel MAB problem.

heading: C.1 CONNECTING THE PROBLEMS
text: Given an RKHS H with an associated Mercer’s kernel K, the objective of the zeroth-order bandit optimization problem is
max x∈X
f∗(x) such that ‖f∗‖H ≤ 1 , (P1)
with access to oracle Of∗ : x 7→ f∗(x) + η where η ∼ N (0, τ2) .
Equivalently, the objective in our reward learning framework is
max π∈Hπ
〈r∗, π〉Hr such that ‖r∗‖Hr ≤ 1 and ‖π‖Hπ ≤ 1 , (P2)
with the corresponding spaces and inner products are defined in the previous section. The oracle required in our setup responds with
Or∗ : π 7→ 〈r∗, π〉Hr + η where η ∼ N (0, τ2) ,
for any policy π ∈ Hπ such that ‖π‖Hπ ≤ 1. Our first lemma below states that obtaining such a n oracle is indeed feasible if we are able to restrict our queries π to include only points kx for which the vector kx ∈ C . Lemma 2. Given access to oracle Of∗ for a function f∗, the corresponding oracle Or∗ can be implemented when the query set consists of {kx}x∈C .
Proof. For any query point k, the oracle Or∗ needs to compute the value 〈r∗, k〉Hr = f∗(x). Thus, these two oracles on the provided query set are exactly identical.
Lemma 3. For any f∗ ∈ H satisfying ‖f∗‖H ≤ 1, we have that ‖r∗‖Hr ≤ 1.
Proof. Observe that an alternate way to define the RKHS norm is given by
‖f‖H : = sup S⊆X ;|S|≤∞ f |SK−1S f |S .
The fact that ‖r∗‖Hr is computed on C ⊂ X establishes the desired claim.
Finally, we turn to establishing a relation between the solutions obtained from solving the relaxed problem (P2) as compared to solving the original problem (P1). We denote the corresponding maximizers for both problems
x∗ ∈ arg max x∈X f∗(x) and x∗π ∈ arg max x∈C 〈r∗, kx〉Hr , (47)
The following lemma now relates both these maximizers together.
Lemma 4. For an RKHS H with kernel K satisfying Assumption 2 with constant LK > 0 and any function f∗ ∈ H, let x∗ ∈ X and x∗π ∈ C be the maximizers as defined in equation (47), we have
f∗(x∗π) ≥ f∗(x∗)− √ 2cLK . (48)
Proof. Denote by ΠC (x ∗) : = arg minx∈C ‖x∗ − x‖2 the projection of the point x∗ onto the set C . Then, we have
f∗(x∗)− f∗(x∗π) = f∗(x∗)− f∗(ΠC (x∗)) + f∗(ΠC (x∗))− f∗(x∗π) ≤ √
2cLK .
This completes the proof of the lemma.
The above lemma shows that solving Problem P2 is equivalent to solving Problem P1 up to an additive factor of √ 2cLK when we are working with an -cover over the domain space.

heading: C.2 ANALYSIS FOR BANDIT OPTIMIZATION
text: Recall from the previous section that the quantity which determines the rate of decay is the ratio of eigenvalues
ζj = µ̂π,j µ̂r,j = µ̂2r,j µ̂r,j = µ̂r,j ,
where µ̂r,j is the jth eigenvalue of the kernel matrix K. Let us denote by P denote the uniform distribution over the input space X and let us suppose that the cover Ncov is formed using random samples from this distribution. Let us denote by {µj} the eigenvalues and by φj the corresponding eigen vectors of the Mercer kernel K. For every point x ∈ X , let us denote by
Φ(x) : = (√ µjφj(x) )∞ j=1 ,
the corresponding featurization of the point x. Then, for S : = Ex∼P[Φ(x)Φ(x)>], we have
[S]j,k = [Ex∼P[Φ(x)Φ(x)>]]j,k = Ex∼P[ √ µj √ µkφj(x)φk(x)] = µjδj,k . (49)
Observe that the kernel matrix K and the (scaled) sample covariance matrix Ncov · Ŝ =∑ x∈C Φ(x)Φ(x)
> 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 covariance matrix Ŝ to those of the underlying kernel K.
Lemma 5. For any λS > 0 and size of the cover satisfyingNcov( ) > c· tr(S(S+λSI) −1)
2S + 1 2S log ( 1 δ ) ,
we have,
µ̂j ≤ (1 + S)µj + λS S for all j , (50)
with probability at least 1− δ.
The following corollary of Lemma 5 provides us with a way to control the deviation of the eigenvalues µ̂j from the corresponding µj in a multiplicative manner. Corollary 4. For any value of decay parameter β > 1 and γ < β, we have, for all j, the eigenvalues
µ̂j ≤ 3
2 µj + N−γcov 2 , (51)
with high probability.
Proof. Let us understand the condition Ncov( ) tr(S(S+λSI) −1)
2S and see what restrictions it puts
on the value of the covering number. Lets suppose that the true eigen values µj j−β and we set the value of λS N−γcov . Therefore, the sum∑
j
j−β
j−β + λS . N
γ β cov + 1
N−γcov ∑ j>N γ β cov j−β
. N γ β cov +
N γ β cov
β − 1 .
Thus, if we set S = 12 , then for any β > 1 and γ < β, 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 a good understanding of the decay of the eigenvalues of the kernelK associated with the RKHS and this allows us to relate the set of empirical eigenvalues to these.
We now present a proof of Theorem 3, 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 Matérn kernel later.
Theorem 5 (Restated Theorem 3). Suppose that the eigenvalues of a LK-Lipschitz kernel K with respect to a distribution P over X satisfy the power-law decay µj j−β . Let x̂plug be the output of Algorithm 1 using n queries to the oracleOf∗ . Then, for any value of γ ∈ (1 + 1d log(1/ ) log(LK/ 2)
, β) and ∈ (0, 1), the excess risk
max x
f∗(x)− f∗(x̂plug) . N 1 β+2 cov ( ) · n −β 2(β+2) +N 1−γ 2 cov ( ) + √ LK ,
with high probability.
Proof. Our strategy, as before, will be to explore nα directions and assume τ2 = 1. Recall, that for symmetric matrices, Theorem 2, the excess error of the plug-in estimator can be upper bounded as
E[∆(π̂plug; r∗)]2 ≤ λ2reg sup j≥1  1 ν2j σ 2 j
µπ,jµr,j +
λ2regµr,j µπ,jν2j
+ 1 n sup j≥1 [ ν4j µ 2 π,j ν4j σ 2 j + λ 2 regµ 2 r,j ] .
Bounding Bias. We will split the analysis into two cases.
Case 1: j > nα. For this case, we have that σj = 0 and therefore
λ2reg sup j>nα µ̂π,j λ2regµ̂r,j = sup j>nα Ncovµ̂j . sup j>nα Ncov(µj +N −γ cov ) ≤ Ncovn−αβ +N1−γcov , (52)
with the above holding with high probability from an application of Corollary 4 for any 1 < γ < β.
Case 2: j ≤ nα. For this case, we have σj = µπ,jnα . The bias can then be upper bounded as
λ2reg sup j≤nα  1 ν2jµπ,j
n2αµr,j +
λ2regµr,j µπ,jν2j  ≤ λregnα , (53) where the final inequality follows from using a2 + b2 ≥ 2ab.
Bounding variance. As we did in the section above, let us split the analysis into two cases.
Case 1: j > nα. For this case, the variance term simplifies to
1 n sup j>nα
[ µ2π,j
λ2regµ 2 r,j
] = 1
λ2regn sup j>nα
[ N2covµ̂ 2 j ] ≤ N 2 cov
λ2regn sup j>nα
[ µ̂2j ] . N2covn −2αβ +N 2(1−γ) cov
λ2regn .
(54)
Case 2: j ≤ nα. For the second case, we can upper bound the variance term
1 n sup j≤nα  ν4j µ2π,j ν4jµ 2 π,j
n2α + λ 2 regµ 2 r,j
 ≤ n2α n , (55)
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
Bias2 ≤ max{Ncovn−αβ +N1−γcov , λregnα} ≤ max{Ncovn−αβ , λregnα}+N1−γcov , (56)
Variance ≤ max{N 2 covn
−2αβ +N 2(1−γ) cov
λ2regn , n2α n } ≤ max{N 2 covn
−2αβ
λ2regn , n2α n }+ N
2(1−γ) cov λ2regn . (57)
For regularization parameter λreg > Ncovn−αβ−α and γ > αβlognNcov , we have
Bias2 ≤ λregnα +N1−γcov ,
Variance ≤ n 2α
n .
Excess risk bound. To obtain the final excess risk bound, we set α = 1+lognNcovβ+2
E[∆(π̂plug; r∗)]2 ≤ λregnα + n2α
n +N1−γcov
≤ Ncovn−αβ + n2α−1 +N1−γcov (i) . N 2 β+2 cov n −β β+2 +N1−γcov , (58)
where inequality (i) follows from our particular choice of α. Combining the above bound with Lemma 4 completes the proof.
The following corollary instantiates the above theorem for the case when the input space is the unit ball, that is, X = Bd(1). Corollary 5. Let the input space X = Bd(1) and the kernel K satisfy Assumption 2. Then, for any β > 1 + 2d , we have
max x
f∗(x)− Ex∼π̂plugf∗(x) . L d β+2+2d K n −β 2(β+2+2d) . (59)
Proof. From the bound in Theorem 3, we have,
max x
f∗(x)− Ex∼π̂plugf∗(x) . N 1 β+2 cov ( ) · n −β 2(β+2) +N 1−γ 2 cov ( ) + √ LK
(i) ≤ N 1 β+2 cov (
2
LK ) · n
−β 2(β+2) +N 1−γ 2 cov ( 2
LK ) +
(ii) ≤ L d β+2 K · ( 1 ) 2d β+2 · n −β 2(β+2) + ( LK 2 ) d(1−γ) 2 +
(iii) ≤ L d β+2 K · ( 1 ) 2d β+2 · n −β 2(β+2) + 2 , (60)
where inequality (i) follows from substituting → 2/LK, (ii) follows from the fact that Ncov( )
( 1 )d , and (iii) follows from using the assumption that β > γ > 1 + 2d log(1/ ) log(LK/ 2) .
Finally, setting L d β+2+2d K n −β 2(β+2+2d) , we get
max x
f∗(x)− Ex∼π̂plugf∗(x) . L d β+2+2d K n −β 2(β+2+2d) .
This establishes the desired claim.

heading: C.3 REGRET BOUND FOR MATÉRN KERNEL
text: In this section, we specialize the bound from Theorem 3 for the special class of Matérn kernels. Recall that the Matern kernel is a distanced based kernel with K(x, y) = f(‖x − y‖). Denote by r = ‖x− y‖, the exact form for the kernel is given by
KMatern,ν(r) = 21−ν
Γ(ν)
(√ 2νr
l
)ν Kν (√ 2νr
l
) , (61)
with parameters ν and l and where Kν is the modified Bessel function of the second kind. Going forward, lets fix the scale parameter l = 1 without loss of generality.
The following lemma then bounds the Lipschitz constant for this class of kernels when the distance function is the `2 norm. Lemma 6 (Lipschitz Matérn Kernel). Consider the Matérn kernel with parameter ν > 32 . The Lipschitz constant of this kernel is bounded by
LK ≤ sup r∈(0,1)
[ e22−ννKν−1(1)
Γ(ν) · re−
√ 2νr]. (62)
Proof. The approach will be to show that the kernel function KMatern,ν is a Lipschitz function of the distance r and then cover the `2 ball in the d dimensional space appropriately. We now look at the derivative of the function KMatern,ν(r) with respect to r.
∂KMatern,ν(r) = 21−ν(
√ 2ν)ν
Γ(v)
( νrν−1Kν( √ 2νr∂r + rν∂Kν( √ 2νr )
(i) =
21−ν( √ 2ν)ν
Γ(v)
( νrν−1Kν( √ 2νr)− rν ( √ 2νKν−1( √ 2νr) + ν √
2ν√ 2νr
Kν( √ 2νr) )) ∂r
= −2 1−ν( √ 2ν)ν
Γ(v)
( rν √ 2νKν−1( √ 2νr) ) ∂r , (63)
where (i) follows from the identity ∂Kν(z) = (−Kν−1(z)− νzKν(z))∂z.
For any ν > 12 , we have the inequality
Kν(x) Kν(y) < expy−x (y x )ν for 0 < x < y. (64)
Instantiating the above with y = 1 and ν > 32 , we have
|∂KMatern,ν(r)| ≤ 21−ν(
√ 2ν)ν
Γ(v)
( rν √ 2ν · e − √ 2νr
( √ 2νr)ν−1 · eKν−1(1)
)
≤ e2 2−ννKν−1(1)
Γ(ν) · re−
√ 2νr . (65)
The Lipschitz constant for this case can now be obtained by taking a sup over r ∈ (0, 1).
While our upper bound was in terms of sample complexity, in order to compete with the cumulative regret formulation, we adapt an explore-then-commit strategy. The following lemma relates the sample complexity bound to a cumulative regret bound.
Lemma 7 (Batch to online conversion). Suppose an algorithm has sample complexity O(n−α)) in the passive learning setup, the explore then commit strategy based on this learning algorithm would have regret O(T 1 1+α ).
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 − T γ time steps. The cumulative regret for such an algorithm is
RT = T γ + T−αγ(T − T γ) ≤ T γ + T 1−αγ . (66)
Setting γ = 11+α finishes the proof.
We now proceed to prove Corollary 3 which instantiates the bound in Theorem 3 for the class of Matérn kernels. Corollary 6 (Restated Corollary 3). Consider the family of Matérn kernels with parameter ν > 32 defined with the euclidean norm over Rd. The T -step regret of the explore-then-commit algorithm is
RMat,T . O
( L
d2
2ν+d(3+2d) K · T 4ν+d(6+4d) 6ν+d(7+4d)
) .
with high probability.
Proof. First, observe that excess risk bound in Corollary 5 can be converted to a corresponding T -step regret bound by an application of Lemma 7 such that
RT . O
( L d β+2+2d
K · T 2β+4+4d 3β+4+4d
) . (67)
For the class of Matérn kernels, the decay parameter β = 1 + 2νd (Janz et al., 2020, Theorem 9). Using this wit the above regret bound, we get,
RMat,T . O
( L
d2
2ν+d(3+2d) K · T 4ν+d(6+4d) 6ν+d(7+4d)
) .
This completes the proof.

heading: D ADAPTIVE SAMPLING VIA GP-UCB
text: In this section, we prove an upper bound on the expected risk of the Gaussian process upper confidence bound algorithm (GP-UCB) algorithm of Srinivas et al. (2010). In order to adapt their algorithm for our setup, consider the function
fr(x) : = 〈r,Mx〉Hr such that D = {x | ‖x‖Hπ ≤ 1}. (68) We have used x 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 – a necessary condition for the algorithm to work. One work around this is to truncate the unit ball after a 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 Õ(γT √ T ) where γT is the information gain with
γT : = max x1,...,xT∈D
1 2 log det(I + [K(xi, xj)]Ti,j=1) , (69)
where we have assumed without loss of generality that the noise variance τ = 1. For our setup, the kernel function K(xi, xj) = 〈Mxi,Mxj〉Hr . We additionally require that the reward function r belongs to the RKHS spanned by the set {Mx | x ∈ D}. Denote by S = S 1 2 πM>S−1r S 1 2 π and suppose that its eigenvalues satisfy a power law decay with σj(S) = ζj = j−β . The following lemma upper bounds the information gain for this setup in terms of the power law parameter β > 0. Lemma 8 (Information Gain.). The information gain γT for the above setup is bounded as
γT = O(log(T ) · T 1 β+1 ) . (70)
Proof. The quantity of interest here is the information gain
γT : = max x1,...,xT
1 2 log det(I +XSX>) such that ∀j ‖xj‖2 ≤ 1 , (71)
where the matrix X = [x>1 ; . . . ;x > T ] and we have assumed that the noise variance is 1. From the setup described above, we have that the eigen values of S decay as λj j−β . It is easy to see that
Fig({xt}) : = 1
2 log det(I +XSX>) (72)
is a monotonic sub-modular function. Thus, the value of γT can be upper bounded by (1− 1/e)−1 times the value of the greedy maximization algorithm. The greedy maximization algorithm is equivalent to picking
xt = arg max x
Fig(Xt−1 ∪ {x}) .
It is easy to see that at each time t, the unit vector xt will be an eigen vector of the matrix S. Given this observation, we can finally upper bound the value of the info gain
γT ≤ c · max m1,...,mT T∑ j=1 log(1 +mjλj) such that mj ≥ 0 and ∑ j mj = T.
Solving the above optimization problem, the optimal choice of the variables
mj = max
{ 1
λ − 1 λj , 0
} and ∑ j mj = T . (73)
Setting λ = T− β β+1 ensures that there are T 1 β+1 active directions. Substituting the above values of mj in the expression for γT , we get
γT ≤ c · ∞∑ j=1 log(1 + max( λj λ − 1, 0))
≤ c · log ( λ1 λ ) · ∞∑ j=1 I[λj > λ]
(i) = O(log(T ) · T 1 β+1 ) ,
where (i) follows from setting λ = T− β β+1 . This establishes the required claim.
We are now ready to state this our sample complexity bound for GP-UCB for this subclass of problems. Proposition 2 (Sample complexity for GP-UCB). Suppose that the police space Hπ , reward space Hr and the map M satisfy the power law decay assumption with exponent β > 0. The estimator π̂ucb output by the GP-UCB algorithm satisfies
E[∆(π̂ucb; r∗)] ≤ Õ(n− β−1 2(β+1) ) . (74)
The proof of the sample complexity bound in Proposition 2 now follows the regret bound of Õ(γT √ T ) along with using the upper bound on the information gain from Lemma 8.
E[∆(π̂plug; r∗)] = Õ(n 1 β+1− 1 2 ) = Õ(n− β−1 2(β+1) ) . (75)
More recently, Cai & Scarlett (2021) extended the analysis of Valko et al. (2013) to show that the SupKernelUCB algorithm achieves a regret bound Õ( √ γTT ). Using this modified bound, one can improve the above analysis to obtain excess risk
E[∆(π̂plug; r∗)] = Õ(n 1 2(β+1) − 12 ) = Õ(n− β 2(β+1) ) , (76)
which is still worse than those obtained by the bounds by our proposed ridge regression estimator.

heading: E FURTHER DETAILS ON EXPERIMENTAL EVALUATION
text: In the simulation study, we work with d dimensional RKHSs Hr and Hπ . In order to simulate the nonparmeteric regime, we typically use value of n which are less or at most a constant times the dimension d. We set the matrices Sπ = diag(j−1.75), Sr = 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 β = βπ − βr = 0.75. We sampled the true reward r∗ uniformly at random from the unit ball in Hr. We further sampled the oracle noise ∼ N (0, 0.01). All plots were averaged over 10 runs.

Review summaries:
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. 

The paper studies a pure exploration bandit problem in a setting where the reward and policies are assumed to  be in RKHS spaces. The main result is a passive strategy based on experimental design and bounds on the simple regret. The results are extended to the cumulative regret setting via a standard explore-then-commit argument. In the latter setting the results are (depending on the kernel) about competitive with the state-of-the-art (more on this later).

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. 

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.