1 Introduction↩︎

Optimizing sequential decision-making using only preference-based feedback has recently emerged as an important problem [1], [2]. In many applications, including large language model alignment [3], robotics, and recommendation systems, humans find it natural to compare options rather than assign calibrated numeric scores. Preference feedback is often more reliable than numeric ratings, even if less informative. Since human feedback is costly, it becomes essential to develop efficient methods that can learn near-optimal policies while minimizing the number of preference queries required. This motivates the study of reinforcement learning from preferential feedback, commonly referred to as reinforcement learning from human feedback (RLHF).

In the RLHF framework for episodic Markov Decision Processes (MDPs), at each episode, the learner deploys policies and receives preference feedback indicating which trajectory is preferred, rather than observing numeric rewards. This binary feedback is typically modeled as a Bernoulli random variable using the Bradley-Terry-Luce (BTL) model, in which the probability of a preference is determined by applying a link function to the difference in cumulative rewards. Performance is measured in terms of regret, defined as the cumulative loss compared to the optimal policy. The key challenge is learning from minimal one-bit feedback per episode, where the trajectory-level signal provides no direct information about per-step credit assignment.

Several works have studied preference-based RL in tabular MDPs, but these algorithms are computationally intractable even for small state spaces. [4] provide the first computationally efficient algorithm for preference-based RL in linear MDPs, achieving near-optimal regret via randomization to handle trajectory-level feedback. However, the linear MDP assumption is restrictive. For example, [5] showed that the required feature dimension can scale with the size of the state space. Kernel-based models offer a natural generalization that captures nonlinear structure while remaining amenable to theory, and connect to neural networks via the Neural Tangent Kernel [6]. Kernel RL under standard reward feedback has been studied extensively [7]–[10], and sublinear regret has only recently been achieved [10].

1.1 Main Results↩︎

In this work, we develop the first algorithm for preference-based RL in kernel MDPs that achieves provable sublinear regret for all kernels in the Matérn family. Our algorithm attains cumulative regret of order \(\widetilde{\mathcal{O}}\left(K^{1-0.5(\beta_p-1)^2/\beta_p(\beta_p+1)}\right)\), where \(\beta_p>1\) is the eigen-decay parameter defined in Assumption 1. In addition, the algorithm can be implemented in time polynomial in the number of episodes \(K\), thereby providing the first computationally efficient no-regret algorithm for preference-based feedback in kernel MDPs.

In the kernel RL literature [10]–[12], achieving sublinear regret in the number of episodes has been a central goal, as it implies convergence to the optimal policy as the number of episodes grows. For Matérn kernels, sublinear regret was only very recently established for MDPs with standard scalar-valued reward feedback in [10].¹ The authors develop a no-regret algorithm for scalar-feedback MDPs over a broad class of smooth environments, with kernel MDPs arising as a special case. However, the currently known implementations are not computationally efficient [9]; in particular, it remains unclear whether they can be implemented in time polynomial in the number of episodes. We discuss computational complexity in kernel MDPs further in Sec. 8.1.

Preference feedback is substantially more challenging than action-level scalar reward feedback. Unlike scalar feedback, which provides continuous signals containing both magnitude and distributional information, preference feedback compresses the information from an entire episode into a single binary comparison. As a result, both amplitude information (reward magnitude) and fine-grained temporal information (per-step reward assignment) are lost. Nevertheless, we show that near-optimal policies can be learned using only \(K\) bits of feedback, corresponding to one binary preference label per episode across \(K\) episodes.

Achieving sublinear regret under preference-based feedback requires overcoming three interrelated technical challenges: (i) controlling the log-covering number of the value function class, which depends on the RKHS norm of the estimators; (ii) designing exploration noise that induces sufficient trajectory-level exploration while remaining amenable to efficient covering arguments; and (iii) carefully tuning regularization and covering parameters to balance bias, variance, and statistical complexity simultaneously.

1.2 Technical Challenges and Contributions↩︎

We provide an overview of the three main technical challenges and corresponding contributions here, with full technical details deferred to Sec. 4.

1.2.0.1 (i) Controlling the log-covering number via estimator norm bound.

In kernel MDPs, confidence bounds depend on the log-covering number of the value-function class, which in turn scales with the RKHS norms of the estimators. This is a fundamental difference from linear MDPs, where the log-covering numbers are only logarithmic in the episode count [14]. Under trajectory-level preference feedback, localization arguments used in action-level kernel RL [9], [15], no longer apply, and naive estimators can exhibit rapidly growing RKHS norms, leading to overly conservative confidence sets. Our approach controls this complexity by learning the reward component from preferences using regularized kernel logistic regression, with the regularization explicitly tuned to keep the estimator norm (and thus the covering number of the induced function class) small.

1.2.0.2 (ii) Designing trajectory-level exploration with efficiently coverable sample paths.

Preference feedback requires exploration at the trajectory level, but deterministic bonuses cannot be applied because the realized trajectory is unknown at decision time. We therefore use randomized exploration through a Gaussian process perturbation that can be injected online. Since GP sample paths do not belong to the RKHS induced by their covariance kernel almost surely [16], we cannot cover the randomized estimator by placing it in a ball of the original RKHS. Instead, we use a high-probability Gaussian covering set: although a GP sample is not contained in any fixed finite-radius RKHS ball, it lies with high probability within\(\epsilon\), in \(\ell_\infty\), of a suitably enlarged RKHS ball [17]. This allows us to derive covering bounds for the posterior GP perturbation directly.

1.2.0.3 (iii) Tuning regularization and covering parameters to balance bias, variance, and complexity.

Regularization plays a dual role in our work: it controls statistical accuracy (bias and variance) and also complexity via covering numbers. Unlike linear value iteration [14], where log covering numbers are only polylogarithmic in the mesh \(\epsilon\), kernel MDPs yield polynomial log covering bounds (see 11 ). This makes tuning \(\epsilon\) non-trivial: too small inflates confidence widths, too large inflates misspecification error. We tune both the regularization and covering mesh \(\epsilon\) jointly to keep confidence bounds meaningful under preference feedback.

Together, these ingredients yield the first preference-based kernel MDP algorithm with provable sublinear regret.

1.3 Related Work↩︎

In recent years, preference-based reinforcement learning has gained significant attention in both bandit and MDP settings. In the bandit setting, that corresponds to a degenerate case with a single state, action-level preference (dueling bandits) has been extensively studied across various families of reward functions and preference assumptions [18]–[24]².
Preference-based MDPs have also received significant attention; however, theoretical guarantees in this setting often require optimization over a large policy space, making the approach computationally infeasible. [26] consider linear preference-based MDPs with trajectory-level preference and provide sub-linear regret guarantees. However, in a linear setting, the transition model is assumed to be known. Furthermore, the algorithm requires optimization across a large policy class, making it unclear how the approach could be implemented. [27] further generalizes [26], allowing the preference function to be an unknown element of a large function space; however, as in [26], it also requires optimization over the entire policy space. The works of [28], [29] suffer from similar scaling issues due to their policy-search approach. To the best of our knowledge, the first algorithm for preference-based feedback in linear MDPs that can be implemented efficiently is due to [4]. To bypass the total policy search, [4] incites trajectory-level exploration by injecting adequately sampled noise. The idea of randomized trajectory-level exploration has also appeared in works studying aggregate feedback [30]–[32]. Preference feedback is strictly harder than aggregate feedback: while aggregate feedback provides a continuous signal in \([0, H]\), preference feedback compresses this to a single bit, losing both the magnitude of reward differences and fine-grained distributional information
Also relevant to our work are papers on kernel MDPs with standard, immediate, state-action feedback. The setting in which the reward and transition operators are general members of an RKHS was first considered by [7]. In the paper, the authors provide regret guarantees for a wide class of kernels but do not ensure regret sublinearity kernel in the Matérn family. Under the kernel MDP assumption, the authors of [33] provide sublinear regret guarantees for the more challenging average-reward setting but with a constraining "optimistic closure" assumption on the value function which removes the need for value iteration. Several other works have considered kernel-based RL under additional structural assumptions [8], [34] but do not obtain sublinear regret for Matérn kernels of general smoothness.
Recently, the study of smooth state-action feedback MDPs has emerged [9], [10]. Instead of imposing smoothness assumptions directly on the MDPs reward function or transition operator, as in our work, smoothness is imposed on the Bellman operator. The Matérn kernel assumption implies the smoothness of the Bellman operator and is studied as a special case of a more general framework in [9], [10]. To the best of our knowledge, the algorithm in [10] is the only one that achieves sublinear regret for all Matérn kernels.

2 Problem Formulation↩︎

We consider an episodic Markov decision process \(\mathrm{MDP}(\mathcal{S},\mathcal{A},H,\{P_h\}_{h=1}^H,\{r_h\}_{h=1}^H)\) with measurable state space \(\mathcal{S}\), action set \(\mathcal{A}\) and horizon \(H\in\mathbb{N}\). For convenience of analysis, we assume that the state action product set is contained in a unit hypercube over \(\mathbb{R}^{d}\). At step \(h\in[H]\), taking action \(a_h\in\mathcal{A}\) at state \(x_h\in\mathcal{S}\) yields (deterministic) reward \(r_h(x_h,a_h)\in[0,1]\) and transitions to \(x_{h+1}\sim P_h(\cdot\mid x_h,a_h)\). A (deterministic) nonstationary policy is a mapping \(\pi:\mathcal{S}\times[H]\to\mathcal{A}\), with \(\pi_h(x)\in\mathcal{A}\) the action prescribed at step \(h\).
For any policy \(\pi\), we define the value and action-value functions \[\begin{align} &V_h^\pi(x)\;:=\;\mathbb{E}\!\left[\sum_{h'=h}^H r_{h'}(x_{h'},\pi_{h'}(x_{h'}))\;\bigg|\;x_h=x\right],\\ &Q_h^\pi(x,a)\;:=\;r_h(x,a)+\mathbb{E}\!\left[\sum_{h'=h+1}^H r_{h'}(x_{h'},\pi_{h'}(x_{h'}))\;\bigg|\;x_h=x,\,a_h=a\right], \end{align}\]

and \(V_h^\star(x):=\sup_\pi V_h^\pi(x)\). We adopt the notation \([P_h V](x,a):=\mathbb{E}_{x'\sim P_h(\cdot\mid x,a)}[V(x')]\) so that the Bellman equations read (\(V^{\pi}_{H+1}\equiv 0\)): \[\begin{align} \label{eq:bellman95eq} Q_h^\pi(x,a)=\big(r_h+P_h V_{h+1}^\pi\big)(x,a),\; V_h^\pi(x)=Q_h^\pi\!\big(x,\pi_h(x)\big) \end{align}\tag{1}\]

2.0.0.1 Reproducing Kernel Hilbert Spaces and Kernel ridge regression

We will assume that the state-action value function belongs to the reproducing kernel Hilbert space(RKHS) of a known kernel function \(k\). Let \(\mathcal{Z}=\mathcal{S}\times \mathcal{A}\) be the state-action product set. For a positive-definite function \(k: \mathcal{Z}\times \mathcal{Z}\rightarrow \mathbb{R}\) . let RKHS \(\mathcal{H}_k\) denote the Hilbert space of functions over \(\mathcal{Z}\) equipped with an inner product satisfying \((*)\forall z\in \mathcal{Z}, k(\cdot, z) \in \mathcal{H}_k\) and \((**) \forall z\in \mathcal{Z}, f \in \mathcal{H}_k, \langle f, k(\cdot, z)\rangle =f(z)\). This inner product induces the norm defined as \(\|f\|_{k}=\langle f, f\rangle_{\mathcal{H}_k}\). We introduce the shorthand notation for the feature function \(\phi(z)=k(z, \cdot)\), assume without loss of generality \(\|\phi(z)\|_{\mathcal{H}_k} \leq 1\), and that all features lie in the unit ball of \(\mathcal{H}_k\).
Hilbert space \(\mathcal{H}_k\) also admits an alternate characterization in terms of eigenvalues of the kernel function \(k\). Under mild conditions on \(k\), Mercer’s theorem provides a characterization of an orthonormal basis of \(\mathcal{H}_k\)

In particular \(\forall f \in \mathcal{H}_k\) and \(\{\zeta_j\}_{j\in \mathbb{N}}=\{\sqrt{\lambda_j}\psi_j\}_{j \in \mathbb{N}}\) form an orthonormal basis of the space \(\mathcal{H}_k\). Behavior of eigen-values of \(\{\lambda_j\}_{j\in \mathbb{N}}\) dictates the difficulty of many learning problems over \(\mathcal{H}_k\). In this work, we consider kernels from the Matérn kernel family. Next to the Squared-Exponential (SE) kernel³, it is one of the most widely used kernel families and is especially attractive for function modeling, as it is norm-equivalent to appropriate order Sobolev spaces [16]. Due to this norm equivalence, it is also studied in the wider context of smooth MDPs [9], [10].

Both the assumption on polynomial-eigen decay and \(\ell_{\infty}\) bound on \(\ell_2\)-eigen function are crucial in obtaining tractable regret bounds and are thus almost ubiquitously made across bandit and kernel RL literature [7], [12], [13], [36]–[38]. For Matern kernels both parameters \(\beta_p\) have closed form expressions in terms of the smoothness parameter \(\nu\), \(\beta_p=\frac{2\nu}{d}+1\).
We briefly introduce Gaussian Processes (GPs), which we use to design frequentist estimators of the value function. A GP on the state-action domain \(\mathcal{Z}\) is a zero-mean random process with covariance function \(k\), i.e.\(\mathbb{E}[f(z)]=0\) and \(\mathbb{E}[f(z)f(z')]=k(z,z')\). Given samples \(\mathbf{Y}_t\) of \(f\) at points \(\mathbf{Z}_t\), the posterior mean and variance are: \[\begin{align} \mu_{t}(z) & =\mathbf{k}_{\mathbf{Z}_t}(z)^{\top}\left(\tau \mathbf{I}_t+ \mathbf{K}_{\mathbf{Z}_t,\mathbf{Z}_t}\right)^{-1}\mathbf{Y}_t, \tag{2}\\ \sigma^2_t(z)& =k(z,z)-\mathbf{k}_{\mathbf{Z}_t}^{\top}(z)\left(\tau \mathbf{I}_t+\mathbf{K}_{\mathbf{Z}_t,\mathbf{Z}_t}\right)^{-1} \mathbf{k}_{\mathbf{Z}_t}(z), \tag{3} \end{align}\] where \(\mathbf{k}_{\mathbf{Z}_t}=[k(z,z_1),\dots, k(z,z_t)]\) and \(\mathbf{K}_{\mathbf{Z}_t,\mathbf{Z}_t}=\{k_{z_i,z_j}\}_{i,j=1}^{t}\). We model the \(Q\) function as a GP sample, updating the posterior as noisy samples arrive; the posterior mean serves as our estimator, and the posterior variance naturally drives exploration. We refer the reader to Sec. [sec:app_B] for further details.

2.0.0.2 Kernel MDP assumption [7], [13]:

We impose the following assumption on the parametric form of the reward function and the transition operator \(\forall z\in\mathcal{S}\times\mathcal{A},\;h\in[H]\): \[\begin{align} \label{eq:kernel-mdp} &r_h(z)=\langle \phi(z),\theta\rangle_{\mathcal{H}_k}\quad P_h(s'\mid z)=\big\langle \phi(z),\Psi_h(s')\big\rangle_{\mathcal{H}_k} \end{align}\tag{4}\] where \(\forall s'\in \mathcal{S}, \Psi_h(s'),\theta\in \mathcal{B}_k(1)\), introducing the short-hand notation for \(\mathcal{H}_k\)-ball, \(\mathcal{B}_k(r): =\{f\in \mathcal{H}_k| \|f\|_{k}\leq r\}\) . Note that we assume the reward function is homogeneous throughout the episode, while the transition operator may vary. We assume throughout that this representation defines a valid transition kernel: \(P_h(\cdot\mid z)\) is nonnegative and integrates to one for every \((z,h)\). Under the conditions in eq.(4 ) the state-action value function of an arbitrary policy \(\pi\) is provably an element of \(\mathcal{H}_k\), moreover \(Q^{\pi}_{h}\in \mathcal{B}_k(H)\) [38].

2.0.0.3 Interaction protocol with preference feedback.

Learning proceeds over \(K\) comparison rounds. At round \(k\in[K]\), an initial state \(x_1^k\in\mathcal{S}\) is chosen (possibly adversarially) and the learner selects a policy pair \((\pi,\pi')\), executing each from \(x_1^k\) to generate trajectories \[\begin{align} &\tau_k=(x_1^{k},a_1^{k},\ldots,x_{H+1}^{k}),\quad a_h^{k}=\pi(x^{k}_h);\\ &\tau'_k=({x'}_1^{k},{a'}_1^{k},\ldots,{x'}_{H+1}^{k}),\quad {a'}_h^{k}=\pi'(x'^{k}_h). \end{align}\] No per-step rewards are observed; instead, the learner receives a single binary label \[\begin{align} \label{eq:pref-model} y_k\sim\mathrm{Ber}\!\left(\sigma\!\left(\sum_{h=1}^H r_h(z^{k}_h) -\sum_{h=1}^H r_h(z'^{k}_h)\right)\right), \qquad \sigma(z):=\frac{1}{1+e^{-z}}, \end{align}\tag{5}\] modeled via a Bradley–Terry–Luce logistic link on the difference of cumulative (unobserved) rewards. As in logistic bandits [39], [40], performance depends on the maximum inverse link gradient \(\kappa_{\mathcal{Z}}=\max_{x\in[-H,H]}(\sigma'(x))^{-1}\), which measures how identifiable the reward is from preference feedback: large \(\kappa_{\mathcal{Z}}\) corresponds to a flat link function and poor learnability.

2.0.0.4 Objective and regret.

The goal is to learn an optimal policy \(\pi^\star\) (maximizing \(V_1^\pi\)) using only preference feedback 5 . Since each round requires two length-\(H\) rollouts, the total number of environment steps after \(K\) rounds is \(T=2KH\). We measure performance by the pairwise (weak) regret \[\begin{align} \label{eq:regret} \mathfrak{R}(K):= \sum_{k=1}^{K}\left[V_1^\star(x_1^k)-\frac{\big(V_1^{\pi}(x_1^k)+\,V_1^{\pi'}(x_1^k)\big)}{2}\right] \end{align}\tag{6}\] which credits the learner with the average of the two policies it deploys in each comparison round. We aim to design an algorithm whose regret grows sublinearly in \(K\) under the kernel MDP structure 4 .

3 Algorithm Description↩︎

In this section, we introduce our algorithm (Preference based Regularized Optimization via Sampled Trajectory induced Optimism ) PROSTO. At the start of the \(k^{\text{th}}\) episode, we estimate the state-action value function \({\widehat Q}^{k}_{h}\) based on the trajectory-level feedback from the previous \(k-1\) episodes and the state transition samples. Due to the inherent difficulty of trajectory-level feedback, we employ separate approaches to estimate the reward and the next-state expected value function. At time \(h\), we obtain the final estimate by adding the individual estimates, \(\widehat\theta_k+ \widehat\Psi_{h}\widehat V^{k}_{h+1}\).
By using the MDP parametrization in eq.(4 ), we can rewrite the difference of reward sums obtained by playing \(\pi,\pi'\) in \(k^{\text{th}}\) episode as \(\sum_{h=1}^{H}\theta^{\top}\left(\phi\left(z^{k}_h\right)-\phi\left(z'^{k}_h\right)\right)\), where \(z^{k}_h\) is a short-hand for for the state-action pair \((x^{k}_h,a^{k}_h)\). Along with eq.(5 ), this parametrization motivates the application of the maximum likelihood estimator (MLE) for the reward vector \(\theta\), utilizing the preference feedback \(\{y_j\}_{j=1}^{k-1}\) as the outcome variable and the trajectory differences \(\sum_{h=1}^{H} \phi(z^{j}_h) - \phi(z'^{j}_h),j\leq k-1\) as the set of covariates. Specifically, an MLE incorporating a norm-weighted penalty is employed. \[\begin{align} \label{eq:reward95theta95calc} \widehat\theta_{k}=\mathrm{argmin}_{\theta} &-\left(\sum_{i=1}^{k-1} y_i\log\sigma\left(\theta^{\top}\overline{\phi}_i\right)+(1-y_i)\log\left(1-\sigma\left(\theta^{\top}\overline{\phi}_i\right)\right)\right)+\tau\|\theta\|^2_{\mathcal{H}_k} \end{align}\tag{7}\] where \(\overline{\phi}_i= \sum_{h=1}^{H} \phi\left(z^{i}_h\right)-\phi\left(z'^{i}_h\right)\label{eq:trajectory95lvl95feature}\) is the trajectory difference feature and \(\sigma(\cdot)\) is the sigmoid function.

3.0.0.1 Exploration noise \(\varepsilon_k\) and the reward estimator \(\widehat\theta_{k}\).

To design the estimator \(\widehat \theta_{k}\) for the state-action value function, we will use the kernel logistic ridge regressor (see eq.(7 ))(KLRR). However, as is common in RL applications, we need to ensure that the set of trajectories used to compute KLRR is sufficiently informative (i.e. exploratory). To incentivize trajectory-level exploration, we need to design an exploration bonus to be added to \(\widehat\theta_{k}\). A difficulty in promoting exploration with trajectory-level feedback is that a commonly used elliptic (deterministic) bonus requires complete knowledge of the trajectory up front, at the beginning of each episode. This is clearly impossible without fully knowing the transition dynamics, and to overcome this issue, we use a randomized (linear) exploration bonus [30], [31]. In kernel-based RL, exploration noise is drawn from a Gaussian Process (GP). We draw \(\varepsilon_k\) from a GP to promote exploration along the directions of those eigenfunctions of the empirical covariance operator \(\mathbf{W}_k=\sum_{i=1}^{k-1}\overline{\phi}_i\otimes\overline{\phi}_i+\tau\mathbf{Id}\) that have small eigenvalues: \[\begin{align} \label{eq:noise95definition} \varepsilon_k\sim \mathbf{GP}(0,\mathrm{Cov}(z_1,z_2)), \quad \mathrm{Cov}(z_1,z_2)=\beta^2_{\text{reward}}(\delta)\langle\phi(z_1),\phi(z_2)\rangle_{\boldsymbol{W}^{-1}_k} \end{align}\tag{8}\] where \(\beta_{\text{reward}}(\delta)\) is the confidence width defined in Lemma (4). Intuitively, we identify underexplored directions and encourage play through these directions. Reward estimate with exploration (confidence) bonus is now simply calculated as \(\widehat\theta_{k}+\varepsilon_k\).

3.0.0.2 Calculating the Value functions \(\widehat{V}^{k}_h,\widehat{V}'^{k}_h\).

As is usually the case in MDP’s [14] we calculate the state-action and value functions recursively via value iteration. The difference in our setting is that the reward vector and the expected next-state value are estimated separately. As in eq.(7 ), the reward estimate \(\widehat{\theta}_k\) is calculated via kernel logistic regression, while the next state expected value function is calculated via the usual kernel ridge regression. In particular, for \(\pi\)(and entirely analogous for \(\pi'\)): \(\widehat{Q}^k_{H+1}=0\), \[\begin{align} \label{eq:Q95estimate} \widehat{Q}^{k}_h= \left[\widehat{\theta}_k+\varepsilon_{k}+\left(\sum_{i=1}^{k-1} \phi(z^i_h)\otimes\phi(z^i_h)+\lambda \boldsymbol{Id}\right)^{-1}\Phi^{h}_{k-1}[\widehat{V}^{i}_{h+1}(x^{i}_{h+1})]_{i\leq k-1}+b^{k}_{h}\right]_{\pm\beta_{\text{clip}}(H-h+1)}\nonumber \end{align}\tag{9}\] where \(b^{k}_h(z)=\beta_{\text{trans}}(\delta, \varepsilon)\sqrt{\phi^{\top}(z)\left(\sum_{i=1}^{k-1} \phi(z^i_h)\otimes\phi(z^i_h)+\lambda \boldsymbol{Id}\right)^{-1}\phi(z)}\) is the deterministic elliptic potential used to incite optimism in estimating the expected next state value function and \(\Phi^{h}_{k-1}=[\phi(z^{i}_h)]_{i\leq k-1}\) is the feature matrix. Here \(\beta_{\text{trans}}(\delta, \epsilon)\) is the confidence width of the kernel ridge regression, which, unlike the bandit case, also depends on the covering mesh of the value function cover. Due to value iteration, confidence bounds need to hold over the entire value function class, thus the confidence width scales logarithmically with the size of the \(\ell_{\infty}\) cover. Lastly, \([x]_{\pm C}\) is the clipping operator that projects \(x\) into the interval \((-C, C)\). For an exact expression on \(\beta_{\text{clip}}\)⁴, please see the lemma(5).

Both policies are designed greedily with respect to the state-action function, that is, the action is chosen so that the empirical state-action function is maximized \(\widehat{V}^{k}_{h}(x)=\max_{a\in \mathcal{A}}\widehat{Q}_h^{k}(x, a)\).

3.0.0.3 Tuning regularizers \(\tau, \lambda\) and the covering mesh \(\epsilon\).

Tunning the norm penalty weights for both \(\widehat\Psi^{k}_h\widehat V^{k}_{h+1},\widehat\theta_k\) transition and reward estimates is crucial to achieving sub-linear regret in our algorithm. In addition to allowing for more granular bias-variance trade-off [12], adjusting \(\lambda,\tau\) in our work enables a sharp bound on the log-covering number. Reward-regularizer \(\tau\) directly influences the RKHS norm of \(\|\widehat\theta_k\|_{\mathcal{H}_k}\) and the covering numbers of the sample paths \(\varepsilon_k\)(see Lemma.(2)), which in part determine how complex a function class we need to cover to achieve uniform bounds over all value functions. Transition-regularizer \(\lambda\) further ensures that the covering number of the elliptic bonus \(b^{k}_h(\cdot)\) is not too large. Additionally, unlike the bandit setting, our setting requires tuning the covering accuracy \(\epsilon\). If \(\epsilon\) is too small, the covering number(see eq.(11 )) is large and hence the confidence width \(\beta_{\text{trans }}(\delta, \epsilon)\) is too wide thus making the estimator \(\widehat Q^k_{h}\) inaccurate. On the other hand, if \(\epsilon\) is too big, the value function cover is too coarse, leading again to an inaccurate estimator and vacuous regret bounds. We tune the regret with respect to these three parameters essentially requiring a solution to a piece-wise linear 3-dimensional optimization problem(see. eq(33 )): \[\begin{align} \tau= H^2\log(K)^{\beta_p}K^{\frac{2}{\beta_p+1}}\quad \lambda= \log(K)^{\beta_p}K^{\frac{2}{\beta_p+1}}\quad \epsilon=H^{2}\kappa_{\mathcal{Z}}K^{-\frac{\beta_p-1}{2(\beta_p+1)}} \end{align}\]

Finally, we design policies \(\pi, \pi'\) as greedy policies with respect to the estimated state-action value function. In particular, at the start of \(k^{\text{th}}\) episode, each policy draws an independent exploration noise vector \(\varepsilon_k\)(from the distribution described in eq.(8 )) and calculates its own \(Q\)-estimate as in eq.(9 ).

4 Performance Guarantees and Technical Challenges↩︎

In this section, we state the cumulative regret upper bound of our algorithm \(\mathrm{\small PROSTO}\) and further expand on the challenges unique to learning with preference feedback in the kernel setting.

A detailed proof of Theorem.(2) can be found in Sec.(6) in the Appendix.
For the remainder of this section, we highlight the technical difficulties unique to kernel MDPs and explain how our contributions address these challenges; see Sec. 7 for additional discussion.

4.0.0.1 Covering bounds for estimators in kernel based MDPs.

Extending preference-based RL to kernel MDPs introduces technical obstacles absent in both linear preference-based RL and kernel RL with action-level rewards. The central challenge is controlling the log-covering number of the value-function class, which directly determines the widths of confidence intervals and is essential for optimism-based analyses [14].

In linear MDPs, the log-covering number is bounded polynomially in the ambient dimension, does not grow with the number of episodes, and only exhibits logarithmic growth with respect to the covering parameter \(\epsilon\) [14]. Consequently, the covering mesh \(\epsilon\) can be set to \(1/\text{poly}(K)\) while the log-covering number remains \(\widetilde{\mathcal{O}}(1)\), leaving the regret order unchanged. In kernel settings, the situation is fundamentally different. Recall that the parameter \(\beta_p = 2\nu/d + 1\) captures the smoothness of the kernel relative to the input dimension; the log-covering number of the value function class \(\mathcal{V}\) satisfies: [7], [13]: \[\begin{align} \label{eq:main95text95cover} &\mathcal{V}=\left\{\mathrm{\small clip}\left(\max_{a\in \mathcal{A}}\phi^{\top}(z)\theta+\beta\sqrt{\phi^{\top}(z)\mathbf{B}\phi(z)}, C_{\text{clip}}\right), \|\theta\|_{\mathcal{H}_k}\leq R_{\text{norm}}, \|\mathbf{B}\|_2\leq \lambda^{-1}, \beta\leq B_{\text{optim}}\right\}\nonumber\\ &\log \mathcal{N}_{\infty}(\mathcal{V}, \epsilon)= \mathcal{O}\left(\left(\frac{R^{2}_{\text{norm}}}{\epsilon^2}\right)^{\frac{1}{\beta_p-1}}+\left(\frac{B_{\text{optim}}^2}{\lambda\epsilon^2}\right)^{\frac{2}{\beta_p-1}}\right) \end{align}\tag{11}\] The critical difficulty is that the exponent \(1/(\beta_p - 1)\) diverges as \(\beta_p \to 1\) (i.e., when \(d \gg 2\nu\)). Since the estimator norm \(R_{\text{norm}}\), the confidence width \(B_{\text{optim}}\), and the covering mesh \(\epsilon\) are all polynomial in \(K\), this means the log-covering number itself can grow as an arbitrary-degree polynomial in \(K\), rendering standard regret analyses vacuous. As emphasized in [10], it is exactly the settings where \(\beta_p\sim 1\) that make it difficult to achieve no-regret bounds, even for action-level feedback.
Kernel preference feedback adds an additional layer of difficulty to bounding the log covering numbers; exploration necessitates the addition of a linear exploration bonus in the form of a GP(see eq.(8 )). This exploration noise is not sufficiently smooth and lies outside of the \(\nu\)-Matérn RKHS w.p. 1 [16], making the bounds in eq.(11 ) inapplicable. While sampling-based exploration in RL is certainly not new [41], value iteration poses new challenges for Thompson sampling. While GP-TS [8] can simply disregard the complexity of the estimated/sampled posterior and only concentrate on the \(\ell_{\infty}\) error bound, value iteration requires regularity of the estimators, implicitly through the covering bounds.

4.0.0.2 Related approaches.

The current state of the art for action-level kernel MDPs [10] considers space partitioning in which the Bellman operator admits a low-error, locally linear approximation and avoids value iteration over a nonparametric functional family altogether. While [10] achieves an impressive no-regret performance for a wide family of smooth MDPs, domain partitioning is fundamentally unapplicable in trajectory-level feedback. The stochasticity of transitions prevents advance determination of which trajectory (and thus which part of the space) will be realized, precluding localized Bellman operator estimation. In addition, standard elliptic exploration bonuses cannot be computed causally; they require knowing the whole trajectory before the episode begins. An additional research direction relevant to preference learning with kernels is trajectory-level feedback learning in linear MDPs. Causality of the exploration bonus in linear MDP’s is adressed by sampling Gaussian noise from the trajectory covariance [30], [31]. Exploration in linear MDPs requires exploration only along \(d\) directions, hence the addition of the exploratory noise does not alter the order of the log covering bounds in [14].

4.0.0.3 Our technical contributions.

The key to obtaining tight confidence bounds and meaningful regret guarantees is to simultaneously control the RKHS norm of the deterministic component of the \(Q\)-function estimator and the functional complexity of the sampled paths of the GP perturbation \(\varepsilon_k\). Our contribution addresses this through two approaches: (i) for KLRR and KRR estimators, this is done through RKHS and operator norm bounds; (ii) for GP perturbation, which does not have a finite norm in the \(\nu\)-Matérn RKHS, we instead use a high-probability Gaussian covering argument. Tuning the reward regularizer \(\tau\). The central idea for controlling the KLRR estimator’s RKHS norm is careful tuning of the regularizer \(\tau\). Increasing \(\tau\) places more weight on the norm penalty, yielding smaller-norm estimators, but creates a bias-variance trade-off. Critically, \(\tau\) also controls the covering bounds of the exploration process; Intuitively, as shown in [12], tuning \(\tau\) enables tighter bounds on the confidence width \(\beta_{\text{reward}}(\delta)\), making the estimator more confident and thus allowing us to reduce exploration variance. However, the relationship between \(\beta_{\text{reward}}(\delta)\) and \(\tau\) is nonlinear; increasing \(\tau\) excessively can worsen the confidence width of the KLRR estimator.

Covering bounds for the posterior GP \(\varepsilon_k\). As shown in [16], \(\varepsilon_k\) does not possess sufficient smoothness to be in \(\nu\)-Matérn RKHS and instead is a member of a more coarse RKHS, \(\nu'<\nu-d/2\) Matérn reproducing Hilbert space. As a result, the usual covering bounds in [7] are inapplicable, and moreover, for \(\beta_p<2\), the sampled GP does not belong to any Matérn RKHS, thus necessitating an entirely different approach. To this end, we use the result of [17] linking the log-covering bounds of the GP(with covariance \(k(\cdot, \cdot)\)) sample paths and the probability that the GP stays within a(\(\ell_\infty\)) ball(small ball probability). Intuitively, while the GP sample paths lie outside of any \(\nu\)-Matérn RKHS ball, with high probability they have a neighbor inside of a (reasonably sized) RKHS ball that is only \(\epsilon\), away in \(\ell_{\infty}\). Hence \(\ell_{\infty}\), \(\epsilon\)-thickened RKHS ball contains almost all GP sample paths and has small metric entropy. With machinery from [17], we modify their result for the posterior GP \(\varepsilon_k\). The posterior GP \(\varepsilon_k\) is less random than its prior \(\mathbf{GP}(0, k)\) and thus we expect that the small ball probability for \(\varepsilon_k\) is at least that of \(\mathbf{GP}(0,k)\). This proves to be the case, and in a satisfying way, large \(\tau\) necessitates less exploration noise while large \(\beta_{\text{reward}}\) increases the noise. Indeed the log-covering bounds for the sample paths of \(\varepsilon_k\) can be bounded (with high probability) as \[\begin{align} &\varepsilon_k\in G_{k, \epsilon,\delta} \quad \text{w.p.}\quad 1-\delta\\ &\log \mathcal{N}_\infty(\mathcal{G}_{k, \epsilon,\delta},\epsilon) \le\widetilde{\mathcal{O}}\left(\left(\frac{\beta_r}{\sqrt{\tau}\epsilon} \right)^{\frac{2}{(\beta_p-1)}}+\log(1/\delta)\right). \end{align}\]

For more precise treatment of the covering bounds, please see Sec.(6.1).

Tuning the transition regularizer \(\lambda\) and the covering parameter \(\epsilon\). The transition regularizer \(\lambda\) governs a bias-variance tradeoff analogous to \(\tau\). The elliptic exploration bonus is defined through a norm induced by a \(\lambda \mathbf{Id}\)-shifted covariance operator, hence altering \(\lambda\) directly alters the local behavior of the elliptic bonus and hence the covering bounds. A small \(\lambda\) can provide highly confident(transition) estimator but inflates the covering number of the bonus; a large \(\lambda\) reduces the covering number at the cost of overly pessimistic confidence intervals. The covering mesh \(\epsilon\) introduces a tradeoff that is unique to the kernel regime. In linear MDPs, the log covering number depends only polylogarithmically on \(1/\epsilon\), so \(\epsilon\) can be tuned freely without polynomial cost. In kernel MDPs, however, eq. 11 shows that this dependence is polynomial in \(1/\epsilon\), and can be of arbitrarily high degree in hard kernel instances (\(\beta_p\to 1\)). The two sides of the \(\epsilon\) tradeoff are as follows. We run kernel regression on the nearest neighbor of \(\widehat{V}^{k}_{h+1}\) in the \(\ell_\infty\) cover rather than on \(\widehat{V}^{k}_{h+1}\) itself, which introduces a misspecification error in learning the next-state value function \(\Psi_h\widehat{V}^{k}_{h+1}\). This causes \(\beta_{\text{trans}}\) to scale as \(\widetilde{\mathcal{O}}(\epsilon\sqrt{K})\),⁵ so a large \(\epsilon\) leads to trivially wide confidence intervals. Conversely, a small \(\epsilon\) controls misspecification but implies large bounds on the covering number. We tune \(\epsilon\) to balance these two effects.

5 Conclusion↩︎

We study preference feedback in the kernel MDP setting and design a sublinear regret policy. The main novelty of our approach is the derivation of the new GP-specific covering bounds and the tuning of the norm regularizer and the covering mesh to control the covering number of the value function class and, hence, the confidence width of the \(Q\)-function estimator.
Whether the regret bound of \(\mathrm{\small PROSTO}\) can be made order-optimal remains an open question. Domain partitioning approaches [15], [42], which currently provide the only known path to order-optimal regret in kernel MDPs and contextual bandits, are incompatible with trajectory-level feedback, so a fundamentally different technique would be required.

6 Appendix A.↩︎

The proof is conceptually split into three parts: GP prerequisite lemmas, estimation and optimism. For the GP part, we bound the covering bounds of the GP perturbation noise \(\varepsilon_k\) (Lemma.(1)) and also provide uniform bounds on the value of the GP function at feature functions (Lemma.(3)). These are later utilized in deriving Lemmas.(7, 9)

For the estimation part, Lemma.(4) provides the confidence bounds for the reward function estimate \(\widehat\theta_r\) and Lemmas.(5) and (6) are crucial in providing a bound on the log-covering number of the state value function, and subsequently proving the confidence bounds of the transition operator in Lemma.(7). Finally, in Lemma.(9) we bound the effect of the GP exploration noise \(\varepsilon_k\)(see eq.(8 )) on the estimation of the \(Q\) -function.
On the optimism side, we show constant probability(\(\approx \Phi(-1)\)) "approximate optimism" in Lemma.(8) and then extend this to \(\approx 1-o(1)\) probability optimism in Lemma.(10). Finally, in the Theorem.(2), we present the final regret upper bound.

6.1 Axillary lemmas on the posterior GP↩︎

We first derive log covering bound for the exploratory GP process sampled in eq.(8 ), and initially we concetrate on the derivation for the "vanila" Matérn GP, \(w\). The idea is that while the sampled GP, \(w \sim \mathbf{GP}(0, k(\cdot, \cdot))\) is not in RKHS of \(\nu\)-Mat́ern kernel, it can be shown that with high probability that \(\varepsilon_k\) is within an \(\epsilon\) (in the \(\ell_{\infty}\) sense) of a reasonably small ball in RKHS of \(\nu\)-Matérn kernel. In other words , with high probability we will show that: \[w \in M\cdot\{f\in \mathcal{H}_k| \|f\|_{\mathcal{H}_k}\leq 1\}+ \epsilon\cdot \{f\in \ell_\infty |\|f\|_{\infty}<1\}\]

Hence, even though \(\epsilon_k \in M\cdot\{f\in \mathcal{H}_k| \|f\|_{\mathcal{H}_k}\leq 1\}\) w.p. 0, the log covering number of the GP sample paths is, up to a constant the same as that of \(B_{\mathcal{H}_k}(1)\). Exactly this is shown in [17]. Combining the said result with the small ball probability bounds in [43] (Lemma 3) we have the following result:

We next generalize Lemma.(1) to the posterior GP \(\varepsilon_k\sim \mathbf{GP}(0, \mathrm{Cov}_{k}(\cdot, \cdot))\). The idea is that as we sample new trajectory pairs, the uncertainty in the point estimate provably drops and thus \(k_{\text{posterior}}\preceq k\) in the positive-definite sense. This essentially implies that \(\varepsilon_k\) is "less random" than \(w\). The subtlety here is that \(\varepsilon_k\) is inflated by \(\beta_{\text{reward}}\) and compressed by the regularizer \(\tau\). We thus expect the covering bound to be trade-off between these two quantities.

Next, we derive general uniform bounds on the feature-GP functional \(\langle \varepsilon_k, \phi(z)\rangle \forall \mathcal{Z}\). The idea is to use the Hölder continuity \((\alpha=\nu)\) of the Matérn feature function along with [45] integral to bound the supremum of the GP in terms of the log-covering number.

6.2 Main Proof↩︎

Define the set of value functions in episode \(k\) as : \[\begin{align} \label{eq:val95set} \mathcal{V}_k=&\left\{\mathrm{\small clip}\left(\max_{a\in \mathcal{A}}\phi^{\top}(s,a)(\theta+\epsilon)+\beta\sqrt{\phi^{\top}(s,a)\mathbf{B}\phi(s,a)}, \pm(H-h+1)\beta_{\mathrm{\small clip}}\right)\right\},\\ &\text{ where, }\|\theta\|_{\mathcal{H}_k}\leq C_{\mathcal{H}}, \|\mathbf{B}\|_2\leq \lambda^{-0.5}, \beta\leq C_{\beta}\sqrt{\lambda}, \varepsilon \in \mathcal{G}_{k ,\epsilon, \delta} \nonumber \end{align}\tag{14}\]

Where \(\mathcal{G}_{k,\epsilon, \delta}\) is the high-probability set defined in Lemma.(2). Of central importance in deriving the confidence bounds for the estimator \(\widehat\Psi^{k}_{h}V, V \in \mathcal{V}_k\) is the \(\epsilon\)-covering number \(\mathcal{N}_{\infty}(\mathcal{V}_k, \epsilon)\). In the next lemma, we derive exact dependence on the confidence width of the KRR estimator \(\widehat{\Psi}^{k}_hV\) as a function of regularizers \(\lambda, \tau\) and the covering mesh \(\epsilon\). This will be crucial later on, when we tune the regret with respect to \(\lambda, \tau, \epsilon\).

In other words, in addition to widening the confidence width by \(\epsilon\sqrt{K}\) we also pay a \(2\epsilon\) additive approximation error for using the \(\mathcal{V}_{\infty}(\epsilon)\) covering. Next, we show that an "approximate optimism" holds for the approximate value function of the policy \(\pi\), \(\widehat V^{\pi'}\), with constant probability for a fixed episode up to a factor of \(\epsilon\).

After obtaining approximate optimism, we turn to bounding the estimation error \(\widehat V_1^{\pi}-V_1^{\pi}\). In particular, in the \(i^{\text{th}}\) episode we need to bound the product \(\overline{\phi}^{\top}_i\varepsilon_i\), where \(\overline{\phi}_i\) is the trajectory difference defined in eq.(7 ). Usual sub-Gaussian concentration bounds are inapplicable here as \(\overline{\phi}_i, \varepsilon_i\) are not independent, given that policy \(\pi\) samples all actions during the \(i^{\text{th}}\) episode \(\{a^{i}_h\}_{h=1}^{H}\) based on the exploration noise \(\varepsilon_i\).
To resolve this issue, we use uniform bounds that hold across the entire trajectory-difference space.

We now extend the optimism Lemma (8) over all episodes by following the derivation analogous to [4], [49]. The idea is that the algorithm is optimistic every \(\approx\frac{1}{\Phi(-1)}\) episodes, and that, for the remaining time, we can bound the optimism error by conditioning on the high-probability bound in Lemma. (9).
First define the "worst case" random process \(\varepsilon^{\dagger}_i\) as : \[\begin{align} \label{eq:worst95case95noise95app} \varepsilon^{\dagger}_i=\mathrm{argmin}_{\varepsilon \in \mathcal{T}}\widehat V^{\pi}(x^i_1,\varepsilon)-\widetilde{V}^{\pi'}_{1}(x^{i}_1,\varepsilon) \end{align}\tag{20}\] where \(\mathcal{T}\) is the set of all functions over \(\mathcal{Z}\) satisfying noise-estimation bound eq.(19 ). Also, define the "worst-case" value functions as : \[\begin{align} \label{eq:worst95case95val95app} \widehat V^{\dagger,\pi}(x^{i}_1)= \widehat V^{\pi}\left(x^i_1,\varepsilon^{\dagger}_i\right) \qquad \widetilde{V}^{\dagger,\pi'}(x^{i}_1)= \widetilde{V}^{\pi'}\left(x^i_1,\varepsilon^{\dagger}_i\right) \end{align}\tag{21}\] Note that the value functions \(\widehat V^{\dagger,\pi}(x^{i}_1),\widetilde{V}^{\dagger,\pi'}(x^{i}_1)\) are no longer random functions with respect to the random process \(\varepsilon_i\) as they are now parametrized by the(deterministic) "worst-case" process \(\varepsilon^{\dagger}_i\).

We are now ready to state and prove the regret bound of Algorithm(1)

7 Appendix C↩︎

In this section, we add a more technical discussion around the difficulty of adapting the ideas from the works that consider linear trajectory-feedback setting and action-level feedback in kernel MDPs.

7.0.0.1 Difficulty of extending current approaches to kernel RL preference feedback.

Extending preference-based RL to kernel MDPs introduces technical obstacles absent in both linear preference-based RL and kernel RL with action-level rewards. The central challenge is controlling the log-covering number of the value-function class, which directly determines the widths of confidence intervals and is essential for optimism-based analyses [14].

In linear MDPs, the log-covering number is bounded polynomially in the ambient dimension, does not grow with the number of episodes, and only exhibits logarithmic growth with respect to the covering parameter \(\epsilon\) [14]. Consequently, the covering mesh \(\epsilon\) can be set to \(1/\text{poly}(K)\) while the log-covering number remains \(\widetilde{\mathcal{O}}(1)\), leaving the regret order unchanged. In kernel settings, the situation is fundamentally different. Recall that the parameter \(\beta_p = 2\nu/d + 1\) captures the smoothness of the kernel relative to the input dimension; the log-covering number of the value function class \(\mathcal{V}\) satisfies: [7], [13]: \[\begin{align} \label{eq:appendix95cover} &\mathcal{V}=\left\{\mathrm{\small clip}\left(\max_{a\in \mathcal{A}}\phi^{\top}(z)\theta+\beta\sqrt{\phi^{\top}(z)\mathbf{B}\phi(z)}, C_{\text{clip}}\right), \|\theta\|_{\mathcal{H}_k}\leq R_{\text{norm}}, \|\mathbf{B}\|_2\leq \lambda^{-1}, \beta\leq B_{\text{optim}}\right\}\nonumber\\ &\log \mathcal{N}_{\infty}(\mathcal{V}, \epsilon)= \mathcal{O}\left(\left(\frac{R^{2}_{\text{norm}}}{\epsilon^2}\right)^{\frac{1}{\beta_p-1}}+\left(\frac{B_{\text{optim}}^2}{\lambda\epsilon^2}\right)^{\frac{2}{\beta_p-1}}\right) \end{align}\tag{34}\] The critical difficulty is that the exponent \(1/(\beta_p - 1)\) diverges as \(\beta_p \to 1\) (i.e., when \(d \gg 2\nu\)). Since the estimator norm \(R_{\text{norm}}\), the confidence width \(B_{\text{optim}}\), and the covering mesh \(\epsilon\) are all polynomial in \(K\), this means the log-covering number itself can grow as an arbitrary-degree polynomial in \(K\), rendering standard regret analyses vacuous. It is almost universally the case that the hardest modes of operation for kernel algorithms(both bandit and MDPs) are exactly when \(\beta_p\sim 1\). Frequently, algorithms fail to achieve sub-linearity in the "left tail" of the smoothness parameter \(\beta_p\) [7]–[9], [50]
Kernel preference feedback adds an additional layer of difficulty to bounding the log covering numbers; exploration necessitates the addition of a linear exploration bonus in the form of a GP(see eq.(8 )). This exploration noise is not sufficiently smooth and lies outside of the \(\nu\)-Matérn RKHS w.p. 1 [16], making the bounds in eq.(11 ) inapplicable. While sampling-based exploration in RL is certainly not new [41], value iteration poses new challenges for Thompson sampling. While GP-TS [8] can simply disregard the complexity of the estimated/sampled posterior and only concentrate on the \(\ell_{\infty}\) bound, value iteration requires regularity of the estimators, implicitly through the covering bounds.

7.0.0.2 Comparison to the work of [13]

The current state of the art for action-level kernel MDPs [10] considers space partitioning in which the Bellman operator admits a low-error, locally linear approximation and avoids value iteration over a nonparametric functional family altogether. While [10] achieves an impressive no-regret performance for a wide family of smooth MDPs, domain partitioning is fundamentally unapplicable in trajectory-level feedback. The stochasticity of transitions prevents advance determination of which trajectory (and thus which part of the space) will be realized, precluding localized Bellman operator estimation. In addition, standard elliptic exploration bonuses cannot be computed causally; they require knowing the whole trajectory before the episode begins. The work of [13] recently claimed a very impressive order-optimal regret under action-level feedback; however, [10] pointed out a subtle flaw in the use of domain partitioning in conjunction with value iteration. Namely, space localization methods aim to obtain tighter confidence bounds by constructing estimators that use only samples from a small subset of the domain. The issue with this method in value iteration is that while we can control the state-action pair \((x^{h}_i, a^h_i)\), there is no way to localize the next transition state \(x^{h+1}_i\). This is crucial in value-iteration, as \(V(x^{h+1}_i)\) is used as an estimate for \(\Psi_{h}V(x^{h}_i, a^h_i)\). Our work avoids this issue by using uniform covering bounds; that is, we do not localize the value function to any part of the domain. As a result, our covering bounds are much less optimistic than those in [13] and require careful tuning of the cover parameter \(\epsilon\) to obtain a no-regret performance
An additional research direction relevant to preference learning with kernels is trajectory-level feedback learning in linear MDPs. Causality of the exploration bonus in linear MDP’s is adressed by sampling Gaussian noise from the trajectory covariance [30], [31]. Exploration in linear MDPs requires exploration only along \(d\) directions, hence the addition of the exploratory noise does not alter the order of the log covering bounds in [14].

7.0.0.3 Our technical contributions.

The key to obtaining tight confidence bounds and meaningful regret guarantees is controlling the RKHS norm of the \(Q\)-function estimator. Our contribution addresses this through two main techniques applied to (i) the kernel logistic ridge regression (KLRR) reward estimator (eq. 7 ) and (ii) the exploration noise (eq. 8 ).

Tuning the reward regularizer \(\tau\). The central idea for controlling the KLRR estimator’s RKHS norm is careful tuning of the regularizer \(\tau\). Increasing \(\tau\) places more weight on the norm penalty, yielding smaller-norm estimators, but creates a bias-variance trade-off. Critically, \(\tau\) also controls the RKHS norm of the exploration process: as shown in [12], tuning \(\tau\) enables tighter bounds on the confidence width \(\beta_{\text{reward}}(\delta)\), allowing us to reduce exploration variance (and thus RKHS norm) when the estimator is more certain. However, the relationship between \(\beta_{\text{reward}}(\delta)\) and \(\tau\) is nonlinear; increasing \(\tau\) excessively can worsen the confidence width of the KLRR estimator.

Covering bounds for the posterior GP \(\varepsilon_k\). As shown in [16], \(\varepsilon_k\) does not possess sufficient smoothness to be in \(\nu\)-Matérn RKHS and instead is a member of a more coarse RKHS, \(\nu'=\nu-d/2\) Matérn reproducing Hilbert space. As a result, the usual covering bounds in [7] are inapplicable, and moreover, for \(\beta_p<2\), the sampled GP does not belong to any Matérn RKHS, thus necessitating an entirely different approach. To this end, we use the result of [17] linking the log-covering bounds of the GP(with covariance \(k(\cdot, \cdot)\)) sample paths and the probability that the GP stays within a(\(\ell_\infty\)) ball(small ball probability). Intuitively, while the GP sample paths lie outside of any \(\nu\)-Matérn RKHS ball, with high probability they have a neighbor inside of a (reasonably sized) RKHS ball that is only \(\epsilon\), away in \(\ell_{\infty}\). Hence \(\ell_{\infty}\), \(\epsilon\)-thickened RKHS ball contains almost all GP sample paths and has small metric entropy. With machinery from [17], we modify their result for the posterior GP \(\varepsilon_k\). The posterior GP \(\varepsilon_k\) is less random than its prior \(\mathbf{GP}(0, k)\) and thus we expect that the small ball probability for \(\varepsilon_k\) is at least that of \(\mathbf{GP}(0,k)\). This proves to be the case, and in a satisfying way, large \(\tau\) necessitates less exploration noise while large \(\beta_{\text{reward}}\) increases the noise. Indeed the log-covering bounds for the sample paths of \(\varepsilon_k\) can be bounded (with high probability) as \[\begin{align} &\varepsilon_k\in G_{k, \epsilon,\delta} \quad \text{w.p.}\quad 1-\delta\\ &\log \mathcal{N}_\infty(\mathcal{G}_{k, \epsilon,\delta},\epsilon) \le\widetilde{\mathcal{O}}\left(\left(\frac{\beta_r}{\sqrt{\tau}\epsilon} \right)^{\frac{2}{(\beta_p-1)}}+\log(1/\delta)\right). \end{align}\]

Tuning the transition regularizer \(\lambda\) and the covering parameter \(\epsilon\). The transition regularizer \(\lambda\) governs a bias-variance tradeoff analogous to \(\tau\). The elliptic exploration bonus is defined through a norm induced by a \(\lambda \mathbf{Id}\)-shifted covariance operator, hence altering \(\lambda\) directly alters the local behavior of the elliptic bonus and hence the covering bounds. A small \(\lambda\) can provide highly confident(transition) estimator but inflates the covering number of the bonus; a large \(\lambda\) reduces the covering number at the cost of overly pessimistic confidence intervals. The covering mesh \(\epsilon\) introduces a tradeoff that is unique to the kernel regime. In linear MDPs, the log covering number depends only polylogarithmically on \(1/\epsilon\), so \(\epsilon\) can be tuned freely without polynomial cost. In kernel MDPs, however, eq. 11 shows that this dependence is polynomial in \(1/\epsilon\), and can be of arbitrarily high degree in hard kernel instances (\(\beta_p\to 1\)). The two sides of the \(\epsilon\) tradeoff are as follows. We run kernel regression on the nearest neighbor of \(\widehat{V}^{k}_{h+1}\) in the \(\ell_\infty\) cover rather than on \(\widehat{V}^{k}_{h+1}\) itself, which introduces a misspecification error in learning the next-state value function \(\Psi_h\widehat{V}^{k}_{h+1}\). This causes \(\beta_{\text{trans}}\) to scale as \(\widetilde{\mathcal{O}}(\epsilon\sqrt{K})\),¹⁰ so a large \(\epsilon\) leads to trivially wide confidence intervals. Conversely, a small \(\epsilon\) controls misspecification but implies large bounds on the covering number. We tune \(\epsilon\) to balance these two effects.

8 Appendix D↩︎

In this section, we run a simple simulation emprirically confirming the theoretically proven upper bounds in Theorem 2
We run PROSTO on the synthetic MDP with \(\mathcal{S}=[0,1]^2,\mathcal{A}=[0,1]\). The transition function is parametrized as a spherical Gaussian function: \[\begin{align} P_h(x'|x,a)\sim\exp\left(-\frac{\|x'-[x\; a]^{\top}\mathbf{A}\|^2_2}{2}\right)\quad \mathbf{A}=\begin{bmatrix} 0.5& 0 & 0.5\\ 0& 0.5 & 0.5\\ \end{bmatrix}^{\top}\label{eq:MDP952} \end{align}\tag{35}\] We plot the cumulative and average regret of PROSTO for frequently used functions in Bayesian optimization: Hartman [51] and Ackley [52]. We parametrize both as a function state-action \(\mathbf{z}=(s,a)\) variable below: \[\begin{align} &r_{\text{hartman}}(\mathbf{z}) = -\sum_{i=1}^{4} \alpha_i \exp\!\left(-\sum_{j=1}^{3} A_{ij}(z_j - P_{ij})^2\right), \qquad \mathbf{z}\in[0,1]^3\tag{36}\\ &\boldsymbol{\alpha} = (1,\;1.2,\;3,\;3.2)^\top\quad A = \begin{pmatrix} 3 & 10 & 30 \\ 0.1 & 10 & 35 \\ 3 & 10 & 30 \\ 0.1 & 10 & 35 \end{pmatrix}, \qquad P = 10^{-4}\begin{pmatrix} 3689 & 1170 & 2673 \\ 4699 & 4387 & 7470 \\ 1091 & 8732 & 5547 \\ 381 & 5743 & 8828 \end{pmatrix}\nonumber\\ & r_{\text{ackley}}(\mathbf{z}) = -20\exp\!\left(-0.2\sqrt{\frac{1}{3}\sum_{i=1}^{3}z_i^2}\right) - \exp\!\left(\frac{1}{3}\sum_{i=1}^{3}\cos(2\pi z_i)\right) + 20 + \exp(1) \tag{37} \end{align}\]

Both functions are scaled and translated so that their image is \([0,1]\). Note that both functions are non-convex and admit several local minima over the optimization domain.

We plot the cumulative and average regret of \(\mathrm{\small PROSTO}\), where the average regret is defined as \(\mathfrak{R}_{\text{avg}}(k)=\frac{\mathfrak{R}(k)}{k}\). From the above picture, we can see \(\mathfrak{R}_{\text{avg}}(k)\) decays to zero as the episode count \(k\) increases, thus demonstrating a sub-linear regret guarantee.
We also plot the log dependency \(\log{\mathfrak{R}}(\log k)\) of the cumulative regret as a function of log episode count. This graph offers an interesting comparison between the empirical log regret and the (now linear) upper bound. We plot the log dependency for Hartman and Branin [51] reward function

The log upper bound is calculated as: \[\begin{align} \text{upper}(\log k)=\left(1-\frac{(\beta_p-1)^2}{2\beta_p(\beta_p+1)}\right)\log{k} \end{align}\] where the kernel smoothness parameter can be calculated as described in the Sec.(2). As seen in the figure, the predicted upper bound lies above the empirical log regret.

8.1 Discussion on computational complexity of PROSTO↩︎

8.1.0.1 Computational efficiency.

We now discuss the computational cost of PROSTO. The two computationally intesive operations in our algorithm are: (i) Sample the posterior GP noise eq.(8 ) and (ii) greedily optimizing the surrogate \(Q\) function \(\widehat{Q}^{k}_{h}\) over the entire action set. The remaining operations are logistic regression and \(\ell_2\)-norm kernel ridge regression, both of which are the result of a convex optimization objective and can thus be efficiently computed over the number of episodes \(K\). While various speedups, such as RLS [53], infrequent Gramian calculation, momentum gradient methods etc., are possible for both, here we focus on (i), (ii).

8.1.0.2 Calculating (i).

While \(\varepsilon_k\) is not necessarily a member of a \(\nu\)-Matérn RKHS by a similar argument to that in Lemma.(3) applied do a slightly differently constructed feature \(\phi(z,z')=\phi(z)-\phi(z')\) we have: \[\begin{align} \forall z, z'\in \mathcal{Z}\langle \phi(z)-\phi(z'), \varepsilon_k\rangle \leq \widetilde{\mathcal{O}}\left( C \sqrt{ \frac{2d}{\alpha} \log\!\left( C L_\phi \sqrt{\frac{k+\lambda}{\lambda}}\right)}\|\phi(z)-\phi(z')\|_{\mathbf{W}^{-1}_k} \right) \end{align}\] Note that LHS contain an \(\log(1/\|z-z'\|_2)\) factor which is collapsed into \(\widetilde{\mathcal{O}}(\cdot)\). By additionally using smoothness of the covariance induced norm \(\|\cdot\|_{\mathbf{W}^{-1}_k}\) essentially gives us \(\alpha=\min(\nu, 1)\) modulus of continuity for the posterior GP \(\varepsilon_k\). Equivalently, we only need to calculate \(\varepsilon_k\) in \(\mathcal{O}(K^{2d/\alpha})\)(say equally spaced into a grid \(\mathcal{G}\)) points from the domain \(\mathcal{Z}\) at the price of \(\widetilde{\mathcal{O}}(H)\) additive regret error terms.
After this point, this is a tractable, but computationally intensive task. Essentially we need to generate \(\mathbb{R}^{\mathcal{O}(K^{2d/\alpha})}\) dimensional , unbiased Gaussian from a covariance \[\mathrm{Cov}(z_1,z_2)=\beta^2_{\text{reward}}(\delta)\langle\phi(z_1),\phi(z_2)\rangle_{\boldsymbol{W}^{-1}_k}, (z_1, z_2)\in \mathcal{G}\times \mathcal{G}\] , which can be done by simply diagonalizing \(\{\mathrm{Cov}(z_1,z_2)\}_{(z_1,z_2)\in \mathcal{G}\times \mathcal{G}}\). Hence the complexity of \(\mathcal{O}(K^{6d/\alpha})\). We note that other sampling-based methods in GP bandits almost ubiquitously assume a finite discretization of the domain [8], [37].

8.1.0.3 Calculating (ii)

For continuous action spaces, the greedy step can either be implemented using a discretization of the state-action space \(\mathcal{Z}\) or it can be abstracted via an optimization oracle for \(\arg\max_{a\in\mathcal{A}} \widehat Q_h^k(x,a)\) and ommited from overall complexity considerations as is standard in kernel bandit and kernel RL analyses [7], [37], [42], [54] . Here we develop the former argument in more detail, in fact we show that for Mateŕn kernels the greedy optimization step can always be found in \(\mathcal{O}(K^{2d/\alpha})\) run time while paying for additional additive \(\widetilde{\mathcal{O}}(H)\) regret. The argument here is similar to "discrete to continous" confidence bounds guarantees seen often in kernel bandits [11], [54].
In case of PROSTO the surrogate state-action function can be written as: \[\begin{align} \widehat{Q}^{h}_{k}(z)= \langle \phi(z), \widehat{r}\rangle_{\mathcal{H}_k}+ \beta \|\phi(z)\|_{\mathbf{B}^{-1}} \end{align}\] where specifically in Alg.(1), \(\widehat{r}\) is the sum of KLRR and the exploratory GP bonus, and \(\mathbf{B}\) is the covariance operator where \(\|\mathbf{B}\|_2\leq \lambda^{-1}\). While \(\widehat{r}\) is \(\alpha\) Hölder continuous by the same argument as in (i). To settle the approximation of the elliptic exploration bonus, we simply use the continuity of the operator \(\mathbf{B}\) induced norm: \[\begin{align} &\left|\|\phi(z_1)\|_{\mathbf{B}^{-1}}- \|\phi(z_2)\|_{\mathbf{B}^{-1}}\right|\leq\\ &\leq \|\phi(z_1)- \phi(z_2)\|_{\mathbf{B}^{-1}}\leq\lambda^{-1/2}\|(\phi(z_1)-\phi(z_2)\|_{\mathcal{H}_k}\leq \mathcal{O}\left(\lambda^{-1/2}\|z_1-z_2\|^{\alpha}_2\right) \end{align}\]

Not let \(\mathcal{G}\) be a mesh grid, with mesh size \(K^{-2/\alpha}\) and let \([z]= \mathrm{argmin}_{g \in \mathcal{G}}\|z-g\|_2\). By previous argument we have: \[\begin{align} \left|\widehat{Q}^{h}_{k}(z)-\widehat{Q}^{h}_{k}([z])\right|\leq \mathcal{O}\left(\max(\beta\lambda^{-1/2}, \|\widehat{r}\|_{\mathcal{H}_k})\|z_1-z_2\|^{\min(\nu, 1)}\right) \end{align}\] while we have developed stronger bounds for \(\beta,\|\widehat{r}\|_{\mathcal{H}_k}\) here a trivial upper bound or \(K\) suffices. Finally we have \[\begin{align} \left|\widehat{Q}^{h}_{k}(z)-\widehat{Q}^{h}_{k}([z])\right|\leq \mathcal{O}\left(\frac{1}{K}\right) \end{align}\]

hence using discrete version of \(\widehat{Q}\) incurs at most \(\widetilde{\mathcal{O}}(H)\) additive cost while requiring only polynomial run-time as claimed.

8.1.0.4 Comparison with computational aspects of prior kernel RL algorithms.

This computational guarantee should be contrasted with existing no-regret algorithms for kernel and smooth MDPs. Algorithms such as KOVI[7] are computationally efficient in the usual kernel-LSVI sense, but their regret guarantees are not sublinear for the hard low-smoothness Matérn regimes considered here. On the other hand, the recent smooth-MDP algorithms that obtain no-regret guarantees at this level of generality rely on optimization oracles for which a polynomial implementation is unclear. In particular, [10] explicitly notes that the corresponding constrained continuous optimization problems are computationally intractable for Smooth Kernel MDP’s and that a naive discretization leads to a complexity exponential \(K\). In particular, for the worst-case complexity in [10] for the chosen covering parameter is \(\widetilde{O}\left(\exp\left(K^{\frac{d}{(\beta_p+1)}}\right)\right)\).¹¹

It is unclear if the approach could possibly be implemented efficiently for less general kernel MDPs.
A domain-partitioning approach in KRVI [13] has been claimed to achieve both order-optimal regret and polynomial runtime under state-action feedback. However, as explained in this work and [10], there is an issue with the covering argument for the surrogate value function, and it is unclear how it can be patched. Consequently, to the best of our knowledge, PROSTO is the first algorithm under the preference kernel MDP model that simultaneously achieves sublinear regret for all kernels in the Matérn family and admits an implementation whose dependence on the number of episodes \(K\) is polynomial.

NeurIPS Paper Checklist↩︎

1. Claims

2. Question: Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?

3. Answer:

4. Justification: All the claims stated in the abstract and introduction are further developed in the main text and proven in the Appendix.

5. Guidelines:

   • The answer means that the abstract and introduction do not include the claims made in the paper.

   • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A or answer to this question will not be perceived well by the reviewers.

   • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.

   • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.

6. Limitations

7. Question: Does the paper discuss the limitations of the work performed by the authors?

8. Answer:

9. Justification: The limitations of our work are mentioned in the conclusion section and through out the main result and related works section.

10. Guidelines:

    • The answer means that the paper has no limitation while the answer means that the paper has limitations, but those are not discussed in the paper.

    • The authors are encouraged to create a separate “Limitations” section in their paper.

    • The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.

    • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.

    • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.

    • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.

    • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.

    • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren’t acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.

11. Theory assumptions and proofs

12. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?

13. Answer:

14. Justification: All theoretical statements are proven in the appendix.

15. Guidelines:

    • The answer means that the paper does not include theoretical results.

    • All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.

    • All assumptions should be clearly stated or referenced in the statement of any theorems.

    • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.

    • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.

    • Theorems and Lemmas that the proof relies upon should be properly referenced.

16. Experimental result reproducibility

17. Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?

18. Answer:

19. Justification: The experiments are described in detail in Sec.8.

20. Guidelines:

    • The answer means that the paper does not include experiments.

    • If the paper includes experiments, a answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.

    • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.

    • Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.

    • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example

      1. If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.

      2. If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.

      3. If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).

      4. We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.

21. Open access to data and code

22. Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?

23. Answer:

24. Justification: We run synthetic experiments with detailed descriptions of the MDP environment sufficient in its own.

25. Guidelines:

    • The answer means that paper does not include experiments requiring code.

    • Please see the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.

    • While we encourage the release of code and data, we understand that this might not be possible, so is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).

    • The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https://neurips.cc/public/guides/CodeSubmissionPolicy) for more details.

    • The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.

    • The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.

    • At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).

    • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.

26. Experimental setting/details

27. Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer) necessary to understand the results?

28. Answer:

29. Justification: All details of the experiment are stated in Sec.(8).

30. Guidelines:

    • The answer means that the paper does not include experiments.

    • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.

    • The full details can be provided either with the code, in appendix, or as supplemental material.

31. Experiment statistical significance

32. Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?

33. Answer:

34. Justification: All experiments are run 5 times and the one std deviations are shown on the graphs.

35. Guidelines:

    • The answer means that the paper does not include experiments.

    • The authors should answer if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.

    • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).

    • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

    • The assumptions made should be given (e.g., Normally distributed errors).

    • It should be clear whether the error bar is the standard deviation or the standard error of the mean.

    • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.

    • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g., negative error rates).

    • If error bars are reported in tables or plots, the authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.

36. Experiments compute resources

37. Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?

38. Answer:

39. Justification: Our experiments are synthetic simulations and could be run on just CPU over the course of few hours.

40. Guidelines:

    • The answer means that the paper does not include experiments.

    • The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.

    • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.

    • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn’t make it into the paper).

41. Code of ethics

42. Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?

43. Answer:

44. Justification: We conform to ethics guidelines.

45. Guidelines:

    • The answer means that the authors have not reviewed the NeurIPS Code of Ethics.

    • If the authors answer , they should explain the special circumstances that require a deviation from the Code of Ethics.

    • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).

46. Broader impacts

47. Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?

48. Answer:

49. Justification: It is a theoretical paper.

50. Guidelines:

    • The answer means that there is no societal impact of the work performed.

    • If the authors answer or , they should explain why their work has no societal impact or why the paper does not address societal impact.

    • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.

    • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate Deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.

    • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.

    • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).

51. Safeguards

52. Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pre-trained language models, image generators, or scraped datasets)?

53. Answer:

54. Justification:

55. Guidelines:

    • The answer means that the paper poses no such risks.

    • Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.

    • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.

    • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.

56. Licenses for existing assets

57. Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?

58. Answer:

59. Justification:

60. Guidelines:

    • The answer means that the paper does not use existing assets.

    • The authors should cite the original paper that produced the code package or dataset.

    • The authors should state which version of the asset is used and, if possible, include a URL.

    • The name of the license (e.g., CC-BY 4.0) should be included for each asset.

    • For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.

    • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.

    • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.

    • If this information is not available online, the authors are encouraged to reach out to the asset’s creators.

61. New assets

62. Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?

63. Answer:

64. Justification:

65. Guidelines:

    • The answer means that the paper does not release new assets.

    • Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.

    • The paper should discuss whether and how consent was obtained from people whose asset is used.

    • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.

66. Crowdsourcing and research with human subjects

67. Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?

68. Answer:

69. Justification:

70. Guidelines:

    • The answer means that the paper does not involve crowdsourcing nor research with human subjects.

    • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.

    • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.

71. Institutional review board (IRB) approvals or equivalent for research with human subjects

72. Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?

73. Answer:

74. Justification:

75. Guidelines:

    • The answer means that the paper does not involve crowdsourcing nor research with human subjects.

    • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.

    • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.

    • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.

76. Declaration of LLM usage

77. Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigor, or originality of the research, declaration is not required.

78. Answer:

79. Justification:

80. Guidelines:

    • The answer means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.

    • Please refer to our LLM policy in the NeurIPS handbook for what should or should not be described.

References↩︎