Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds
Authors: Aya Kayal
Sattar Vakili
Laura Toni
Da-shan Shiu
Alberto Bernacchia
Venue: ICML 2025 poster (2025)
Keywords: Bayesian optimization
human
preferential
preference-based feedback
kernel methods
regret bounds
dueling bandit
RLHF
Primary area: theory->online_learning_and_bandits
TL;DR: We propose an algorithm for the problem of Bayesian optimization from preference-based (human) feedback and prove improved and tight regret bounds and sample complexities.

Abstract: Bayesian optimization (BO) with preference-based feedback has recently garnered significant attention due to its emerging applications. We refer to this problem as Bayesian Optimization from Human Feedback (BOHF), which differs from conventional BO by learning the best actions from a reduced feedback model, where only the preference between two actions is revealed to the learner at each time step. The objective is to identify the best action using a limited number of preference queries, typically obtained through costly human feedback. Existing work, which adopts the Bradley-Terry-Luce (BTL) feedback model, provides regret bounds for the performance of several algorithms. In this work, within the same framework we develop tighter performance guarantees. Specifically, we derive regret bounds of $\tilde{\mathcal{O}}(\sqrt{\Gamma(T)T})$, where $\Gamma(T)$ represents the maximum information gain—a kernel-specific complexity term—and $T$ is the number of queries. Our results significantly improve upon existing bounds. Notably, for common kernels, we show that the order-optimal sample complexities of conventional BO—achieved with richer feedback models—are recovered. In other words, the same number of preferential samples as scalar-valued samples is sufficient to find a nearly optimal solution.

Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds
Aya Kayal' Sattar Vakili Laura Toni
Da-shan Shiu 2
Alberto Bernacchia"
2
Abstract
et al., 2024), which aims efficiently identify the best prompt for black-box Large Language Models (LLMs), thereby significantly enhancing their performance (Chen et al., 2024; Lin et al., 2024; 2023). Obtaining a numeric score to evaluate each prompt's performance is often un- realistic, but human users are generally much more reli- able at providing preference feedback between pairs of prompts (Lin et al., 2024). Since human feedback is costly, it becomes essential to develop efficient methods that se- quentially select favorable pairs of actions while minimizing the number of feedback instances required.
Bayesian optimization (BO) with preference- based feedback has recently garnered significant attention due to its emerging applications. We refer to this problem as Bayesian Optimization from Human Feedback (BOHF), which differs from conventional BO by learning the best actions from reduced feedback model, where only the preference between two actions is revealed to the learner at each time step. The objective is to iden- tify the best action using a limited number of pref- erence queries, typically obtained through costly human feedback. Existing work, which adopts the
The theoretical framework for learning from preference- based feedback (see, e.g., Pásztor et al., 2024; Xu et al., 2024) can be modeled as Bayesian Optimization from Hu- man Feedback (BOHF). Similarly to conventional BO (Fra- zier, 2018; Shahriari et al., 2015; Srinivas et al., 2010), the learner leverages previously collected samples through kernel-based regression to learn an unknown Black-box func- tion. However, unlike conventional BO methods that rely on direct evaluations of the target function, this approach collects pairwise comparisons instead of direct evaluation feedback, adding further complexities to the problem.
(BTL) feedback model, provides regret bounds for the performance of several algorithms. In this work, within the same framework we develop tighter performance guar- antees. Specifically, we derive regret bounds of Ö(TT(T))), where I'(T) represents the maxi- mum information gain-a kernel-specific com- plexity term-an and T is the number of queries. Our results significantly improve upon existing bounds. Notably, for common kernels, we show that the order-optimal sample complexities of conventional BO-achieved with richer feedback models-as are recovered. In other words, the same number of preferential samples as scalar-valus samples is sufficient find a nearly optimal solu- tion.
In the BOHF framework, at each time step t 1,2, T
the learner selects a pair of actions (xx, and receives binary feedback E {0, 1} representing the preference between the two actions. This binary feedback is mod- cled as a Bernoulli random variable, where the parameter is determined by applying a link function (here, sigmoid) to the difference in the unobserved utilities corresponding to each action, quantifying the preference between them. Performance is measured in terms of regret, defined as the cumulative loss in the selected pairs of actions compared to the optimal action (details are provided in Section 2). Kernel-based models employed within the BOHF frame- work allow for powerful and versatile modeling of prefer- ences among actions, leveraging structures, and handling continuous domains or very large action spaces.
1. Introduction
Optimizing black-box function using only preference- based feedback between pairs of candidate solutions has recently emerged as interesting problem. This approach finds application, for instance, in prompt optimization (Lin
Aya Kayal's work was part of her research place- ment at MediaTek Research. University College Lon- don, UK *MediaTek Research. Correspondence to: Aya Kayal <aya.ayall22 @uk>.ac.uk>, Sattar Vakili <sat- tar vakilf@mkrreearcchccom
Existing work establishes δ (T(T)R²VT) for the BOHF problem (Pásztor et al., 2024), where we use the O and the Ô notations to hide constants and logarithmic terms respectively, for simplicity of presentation. In this expression, is the maximum of the derivative the inverse link function (see
regret bound of
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Bayesian Optimization from Human Feedback
Equation (2)) and T(T) is the maximum information gain, kernel-specific and algoritin-independent complexity term (see Equation (13)).
based confidence intervals, contributing to improvements in both (T) and K.
We present experimental results on the performance of MR- LPF on synthetic functions that closely align with the ana- lytical assumptions, as well as on a dataset of Yelp reviews, demonstrating the utility of the proposed algorithm in real- world applications (Section 5).
It is insightful to compare the existing BOHF regret bound with the order-optimal regret bounds of Ô ( (V((T)T) in conventional BO. In comparison, an additional x² factor arises due to the feedback model. While this constant is independent of T, it can be very large. There is also an extra (T) factor, which introduces potential challenges. To better understand this, let us take a closer look at (TT). For smooth kernels with exponentially decaying eigenval- ues, such as the Squared Exponential (SE) kernel, I(T) is polylogarithmic in T. However, for more general ker- nels of both practical and theoretical interest, such as the Matérn family (Borovitskiy et al., 2020) and Neural Tangent (NT) kemels (Arora et al., 2019), T(T) grows polynomially with T, possibly faster than vT, making the regret bounds vacuous (linear in T).
1.1. Related Work
Two works closely related to ours are Pásztor et al. (2024) and Xu et al. (2024), which consider the exact same BOHF framework. The work by Pásztor et al. (2024) proposed the MaxMinI.CB algorithm, which takes game-theoretic approach to selecting the pair of actions (Ta, at each time step t. Specifically, 2₁ and 2 are selected according to a game, with the objective function defined as a lower confidence bound (LCB) on the probability of favoring d over at. Hence, the name: 2y is chosen to Maximize and xy to Minimize the LCB (see, Pásztor al., 2024, Algorithm 1). Their regret bound scales as Ô (T(T)=²vTT) which may be vacuous for some commonly used kernels and scales with x², which can be a large constant.
Our contribution is that we establish regret bounds of Ô (VT(T)T) for the BOHF problem (Theorem 4.1), achieving a v T(T) improvement and eliminating the depen- dency on K, resolving both issues and matching the regret bounds of conventional BO. From our regret bounds, we derive the sample complexities the number of preference query samples required identify near-optimal actions. Our sample complexities match the lower bounds obtained in Scarlett et al. (2017) for conventional BO, which benefits from richer feedback model with different noise distri- bution. We will provide a technical discussion on this in Section 4.
Another closely related work is Xu et al. (2024), which develops Principled Optimistic Preferential Bayesian Opti- mization (POP-BO), an algorithm based on the optimism principle. Specifically, at each time step f, x/ is set to 2t-1- one of the actions from the previous time step, and x, is set to the maximizer of an upper confidence bound on the pref- erence between the two actions (see, Xu et al., 2024, Algo- rithm 1). They establish a regret bound of Ô ((TTT))))/)) which is larger than the one in Pásztor al. (2024) by factor of (T/I(T)) and similarly may be vacuous for many cases of interest.' Their definition of regret is based directly on the utility function and slightly differs from ours. However, it remains equivalent to our regret definition up to a constant factor, as discussed in Pásztor et al. (2024).
In summary, we establish the intriguing result that the number of preferential feedback samples required to iden- tifyy near-optimal actions is of the same order the num- ber of scalar-valued feedback samples. This is in sharp contrast and significant improvement over the existing work (Pásztor et al., 2024; Xu et al., 2024).
To obtain the improved regret bounds, we propose an algo- rithm referred to as Muuti-Round Learning from Preference- based Feedback (MR-L.FF). The proposed algorithm pro- ceeds in rounds. In each round, pairs of actions are sequen- tially selected based on the highest uncertainty in their pref- erence. This method effectively reduces uncertainties about the preferences between actions by the end of each round. The uncertainties are represented by kernel-based standard deviations. At the end of each round, the kernel- con- fidence intervals are used to eliminate actions unlikely to be the best. Our multi-round structure is inspired by the BPE algorithm of Li & Scarlett (2022), though the details and analysis differ significantly due to the preference-based feedback model. Details are provided in Section 3. We show that this structure allows for a more efficient use of kernel-
Table I.
Comparison of regret bounds in BOHF.
(Pásztor al., 2024)
(Xu ct al., 2024)
This work (Vi(T)T)
Ô (T(TTAVV
(((T))))344
Some other preferential BO methods mainly propose heuris- ties without formal theoretical guarantees on regret or con- vergence proofs (González al., 2017; Mikkola et al., 2020; Takeno et al., 2023).
'u al. (2024) does not explicitly report the scaling of the regret bound with k.
2

---

Bayesian Optimization from Human Feedback
1.1.1. CONVENTIONAL BO
1.1.3. REINFORCEMENT LEARNING FROM HUMAN
FREDBACK (RLHF)
Classical BO algorithms include strategies based on the upper confidence bound (UCB), Thompson sampling (TS) (Thompson, 1933), expected improvement (EI) (Jones et al., 1998), and probability of improvement (PI) (Brochu et al., 2010). A line of research has established regret bounds for BO algorithms, including the ((I(T) bounds for GP-UCB (Srinivas et al., 2010) and GP-TS (Chowd- hury& & Gopalan, 2017). Several works have achieved tighter (T)T(T)T bounds, including Sup variations of UCB (Valko et al., 2013), the domain-shrinking algorithm GP-ThreDS (Salgia et al., 2021), and Batch Pure Explo- ration (BPE) (Li & Scarlett, 2022). The latter also features a multi-round structure and has inspired our MR-LPF algo- rithm. However, there are differences in the inference pro- cedure and analysis, due to the use of a reduced preference- based feedback model, which introduces additional com- plexities in both algorithm design and theoretical analysis.
Another related line of work is RLHF (Griffith et al., 2013; Novoseller et al., 2020; Xu et al., 2020b; Wu & Sun, 2024; Saha et al., 2023; Chen et al., 2022), which has gained popularity due to its success in fine-tuning LLMs (Ouyang et al., 2022). In this context, preference- breeerence-based feedback is provided for Markov decision process trajectories or policies rather than pairs of actions. However, these results are primarily limited to tabular (finite state-action) linear settings and are not directly related to our kernel-based setting.
2. Preliminaries and Problem Formulation
In this section, we provide details of the BOHF framework. We also outline the methods used to predict preference func- tions and estimate uncertainty, which form the foundation of our algorithm's 's design and analysis.
1.1.2. DUELING BANDITS
2.1. BOHF Framework
The BOHF framework can be viewed as an extension of bandits with feferrence-bssed feedback, also known as duel- ing bandits (Yue & Joachims, 2009; Yue et al., 2012), where the goal is to identify the best action from a set of actions using only pairwise comparisons. For comprehensive sur- vey dueling bandits, see Bengs et al. (2021). Dueling bandit problems focus on multi-armed settings and learning the pairwise preference matrix by applying noisy sorting or tournament algorithms (Ailon et al., 2014; Zoghi et al., 2014; Falahatgar et al., 2017; Zoghi et al., 2015). These approaches are typically limited scenarios where the num- ber of arms small, and their regret can become unbounded as the number of arms approaches infinity. The simplest structured variation is the linear contextual dueling ban- dit, studied in Dudík et al. (2015): Saha & Krishnamurthy (2022); Das et al. (2024); Li et al. (2024); Bengs et al. (2022), which allows for a large number of actions but under the limiting assumption of linear structure. Several works have extended the dueling bandit problem to kernel-based set- tings, which differ from our BOHF framework. For instance, Xu et al. (2020a); Mehta et al. (2023a;b) consider the Borda score, representing the probability that a selected action is preferred over a uniformly sampled action from the domain. They make strong assumptions about the Borda function, which effectively reduces the problem to conventional BO. In contrast, our analytical requirements are significantly dif- ferent from these approaches. A recent extension (Verma et al., 2025) considers neural dueling bandits with a wide neural network for preference prediction. Their approach differs in both modeling and action selection, with regret bounds depending on the model's effective dimension and the curvature parameter K.
At each step t 1,2,...,, ,T, the agent selects pair of actions Iy and x/i, from the set X. which can either be a continuous space or (possibly very large) discrete set. We consider the following feedback model: Let ye E {0, 1} be a binary random variable indicating the preference between dy and xy, defined as y: = 1 (2x, > 21). The notation oy. > x/ denotes that action 2, preferred over action at and 1 is the indicator function. Specifically, following the existing work, for each pair (z,z²) E X x X, the random variable y = 11 {x: > 2'} is modelled as Bernoulli random vari- able satisfying P(y = 1|x,, x²) = l (f(z)) - fxx'). Here, # : R + 10. 1] is a known monotonically increasing link function satisfying p(0) = that is assumed to be the sig- moid function pd-) = (1+e unknown latent utility function that quantifies the value of each action. This preference feedback model is referred to as the Bradeley-Terry-Luue (BTL) model (Bradley & Terry, 1952) and is widely utilized in bandit and RL problems with preference feedback (Pásztor et al., 2024; Xu et al., 2024; Zhan et al., 2024; Wu & Sun, 2024).
and f X' - IR is an
We note that when f(x) > f(x'), we have P(r > x²) Ply 1 ==xr,a = ((x))
1. and vice versa. We also emphasize that this feedback model is weaker than the standard BO where the per-step utility signal (the quan- titative value of ʃ) is revealed, typically as a scalar value.
The goal is to sequentially select favorable action pairs over horizon of T steps, and converge to the globally preferred action xx, defined as x= arg max fxx) A common objective adopted in the literature is to design algorithm with sublinear cumulative regret over the horizon T, defined as the sum of the average sub- sub-optimality gap between the
3

---

Bayesian Optimization from Human Feedback
selected pair and the globally optimal action:
of Hy. respectively. The reproducing property implies that for all Ha. and x X, (f. (),,))),, = f(x). Mercer theorem implies, under certain mild conditions, k can be represented using an infinite dimensional feature map:
T P(a* > Iz)) + P(a* > x1)-1 -1
R(T)
(1)
2
It can be shown that the value of regret above is equiv- alent to variation of regret defined on the utility func- tion: Et= (f(x*) (f(z)) + f(x1))
((x,
Im (z)))(()'),
(3)
/2) u2)-used in Xu et al. (2024)-10) up to constants that depend on the link func- tion (Saha, 2021).
where Y'm > O, and Vmmimm E HR form an orthonor- mal basis of Hk- In particular, any f E Hy can be represented using this basis and weights Wm E R as Wm Pm where Ilf >m== w A formal statement and the details are provided in Appendix A. We refer to Tm and (m as (Mercer) eigenvalues and eigen- features of k; respectively.
The notion of regret accounts for the entire sequence of Alternatively,
f -m==
query points throughout steps f ..., T. one may be interested solely in the final performance. In this case, the algorithm outputs êe at the end of T samples, and the performance is measured in terms of PPx"" > -T)== 3- We refer to the number of samples T required to ensure F(x* > kr) - 2/2 S e, for some 0 < c << 1/2, as the sample complexity and also remark on the sample complexity of different algorithms.
Let us use the notation 2 = (æ, x') and h(=) - f(x-)(x²) for (x,x') E X X. As shown in Pásztor et al. (2024), we can define dueling kernel
k< 22) = ((11, + k(2), - 2²)) x2()) (4)
An important quantity that appears in the analysis is
where, we have: [l = || (Pásztor et al., 2024, Proposition 4).
sup 2 is (()x)=((x))))
Below is a formal statement of our assumptions on f.
where ji denotes the derivative of the link function j and k captures its curvature. The dependence on i has been exten- sively studied in linear logistic bandits, with recent works successfully removing the regret dependency on x (Faury al., 2020). To emphasize the significance of this quantity, consider the case where f is bounded within the interval 5]. In this scenario, K. can become extremely large (> 22028). When the algorithm selects an action pair x') that are nearly equally favorable. f(x f(x') will be close to 0, in which case the inverse derivative of the sigmoid function is almost a constant However, when one action is clearly preferred over the other, (f - fx=') becomes large, making the inverse derivative of the sigmoid function very large. Therefore, crucial aspect of algorithm design is to remove the dependency on x defined in (2) by ensuring that the algorithm gradually queries only closely preferred actions.
Assumption 2.1. We assume that the utility function is in the RKHS of a known kemel & satisfying Ilf S B for some constant B > O. Without loss of generality, we assume that the kernel function is normalized k(...) S 1 everywhere in the domain.
2.3. Preference Function Prediction and Uncertainty Estimation
The preference-based feedback model in BOHF is weaker than the standard BO, where quantitative observations of utility are available at each step. Before discussing the case with preference feedback, we briefly review kernel ridge regression in the standard BO setting.
Hypothetically, assume a dataset ((); of observa- tions of f is available, where o, = f(x) Ei, with obser- vation noise E,. Kernel ridge regression would provide powerful predictor and uncertainty estimate of S, as follows:
2.2. Preliminaries and Assumptions
Similar to Pásztor et al. (2024); Xu et al. (2024), we assume that the utility function f belongs to a known Reproduc- ing Kernel Hilbert Space (RKHS). This is a very general assumption, considering that the RKHS of common ker- nels can approximate almost all continuous functions on the compact subsets of Rd (Srinivas et al., 2010) Consider a positive definite kernel k X x X + R. Let H4 be the RKHS induced by k where H4 contains a family of functions defined on X. Let (r-) : H4 x H2 + R and ||. ll Hi -> R. denote the inner product and the norm
f((x) = k, (x) + A (x(x)) = k(I,,) kT (z)((,) +
(5)
where kx(x) = [k(x, x. 1)) represents the pairwise kernel
values between the prediction point x and the observation points, K; = [k( .x, = is the kernel (or covariance) matrix,
0 is a free parameter, and o, [o.]==] is
the vector of observation values. The prediction function fo here is the solution to the following regularized least squares
4

---

Bayesian Optimization from Human Feedback
error optimization (see, e.g., Schölkopf et al., 2001):
Similar to (5), we have an uncertainty estimation for each
2 2 X x X' as follows
ft = arg min
Σ (g(2)) - o,) + 11all ==1
(6)
of(2) = k(2, - k. (=) + AxT) (k+))))(z),,
(10)
gEMe
where À is the same parameter as in (5). Confidence inter- vals of the form [f(z) - (z)] S (( (z), where (()) is a confidence interval width multiplier for a 1 - 8 confidence level, have been shown in several works
where the notation K, [k ((are, srf); (13, +4 1 sents the (dueling) kernel matrix on the space of pair obser- vations X' XX. Note the subtle difference in the definition of of above for the preference- based feedback case compared to the conventional kernel-based regression case, where the free parameter is multiplied by K, reflecting the effect of the sigmoid nonlinearity on the quality of prediction.
repre-
Yadkoi, 2013; Chowdhury & Gopalan, 2017: Vakili et al., 202 la; Whitehouse et al., 2024) under various assumptions, and serve key building blocks in the analysis and algorithm design of standard BO.
Centered around the prediction (.))(()) and incorporating the uncertainty estimate from kernel ridge regression, as defined in Equation (10), we can construct 1 5 confidence intervals of the form:
In the absence of straightforward observations o, and with preference- based feedback, a closed-form prediction no longer available. Intuitively, this case resembles classífication-liee problem with binary outputs, where can employ logistic negative log-likelihood loss. Specifically, for history of preference feedback Hi, (21, z y2),..., (Iz, z/., ye) in the BOHF framework, we define the following loss:
lu(he(z)) - (00n~((h()))) (e(8)o
for a pair of interest = = x'). In Theorem 4.7, we prove novel confidence interval of this form applicable to the analysis of our algorithm.
H,) = Σ ys log ((((z;;,)))
3. Algorithm Description
In this section, we present the Multi-Round Learning from Preference- prefeeence-based Feedback (MR-LPF) algorithm, inspired by Li & Scarlett (2022), designed to achieve low regret within the BOHF framework described in Section 2.1.
(1 - y:) log(1 ((h(z;, + 2 2 II
A prediction hy of the preference function h (difference in the utilities) can be obtained as:
The algorithm partitions the time horizon T into rounds, indexed by = 1.2..... R. During each round r, to- tal of N, samples are collected, ensuring that the cumu- lative number of samples across all rounds equals T, i.e., E N, = T. We define t, = Σj= N, as the time step at the end of round r. The size of each round is de- termined as follows: N₁ = [VT]. N, = I/N,,17 7 for
hy = arg min HE
which represents the minimizer of the regularized negative -og-liielhood loss.
To solve this minimization problem, we apply the Represen- ter Theorem, similar to Pásztor et al. (2024), which provides a parametric representation of hy:
<<> < R. and NR min TT (n-1).
We introduce the notations ((.r) (z, x²) and h(n.r) (z, x') to represent the kernel- based uncertainty estimate and pre- diction, respectively, from the first n samples in round r according to Section 2.3.
he(-) Σ 0,k (c, (z),
(8)
in terms of 0: = 02.,00..... T.]T R With a slight abuse of notation, replacing h with 0 in Le. the regularized negative log-likelihood loss can then be rewritten in terms of the parameter vector 0 as follows:
LPF maintains set M, of actions in each round that are likely to be the most preferable. Initially, Mj is set to A' and is updated at the end of each round while satisfying a nested structure, M, C M, as subsequently described.
(0, =
Us log une (k((z))))))
Within each round r, the n-th sample is chosen as the pair of actions within M, that maximizes uncertainty:
i=1
(1 - y:) log(1 - u (e x1)) + 1101
(I(n.))) arg max a.
(11)
(9)
The preference feedback for this pair V(n.r) 1 (I((ar)) y a(mm)) } is then revealed to the algorithm. The tuple (I K(ma)) M(n.)) is added to the observations specific
where (x) = [lk (æ,, +1l is the kernel values be- tween the pair and observation pairs.
5

---

Bayesian Optimization from Human Feedback
to round r: Hn,r 1.r U (nrr) Mmry M(n.r) )}, which is initialized an empty set at the beginning of the round: Ho.- = 0.
Algorithm 1 MR-LPF
Require: Vr, P(r); time horizon T
M1 <- X, 1
At the end of round r, we compute the prediction function huN...r) based on observations N.,, following the method of minimizing the regularized negative log-likelihood loss described in Section 2.3. Subsequently, we update M, according to the following rule:
for = 1. ... R do
Initialize Hl.. - 0
for n = -1.2.... N, do
Select the pair of actions (din.r)) ().))) that maxi- mizes the variance, with ties broken arbitrarily:
(I(n.))) ((.))) arg max,, (n- (3), + + if ft 2 T then Terminate
Mr+1 = f M,IV'' E M,
(L)(),,)(1xx'))) + (N, 2 0.5). (12)
end Observe ((n.r) = (m > {nm) H...- = Hn-1, r U ( (T ot (nr)) M(rr)))
The round specifie parameters B(r) are designed in way that the left hand side of the inequality is an upper confi- dence bound on the probability of favoring I over x' (the values are given in Theorem 4.1). The rationale here is that when an upper confidence bound on the probability of preferring x to any a' is greater than 0.5, x is plausible to be the most preferred action. Therefore, we keep it in the update of M,+11 All other actions are removed as they are unlikely to be the most preferred. More precisely, as we will show in the analysis, with high probability, the removed actions are not the most preferred, while the most preferred actions remain within the sets M, and are not removed. A pseudocode is provided in Algorithm
end for
Update h(N...) based on observations in Hy...
Update the set of maximizers Mr+1 1 by removing ac- tions unlikely to be optimal:
Mr+1 for E M,IVe'' E EM, : (u(h(N,,) + (1, (N.)) end for
2 0.5)
where, B is the upper bound on the RKHS norm of J given in Assumption 2.1, L maXe, ((h(x, x')), Ki = defined in Equation (2), Vr > 1, = 6, X is the regu- larization parameter of the dernel-based regression. Then, for some constant To > independent Tf (specified in Appendix B), and for all T 2 To. with probability at least 1-6 5:
When the confidence intervals shrink sufficiently fast rate, only near-optimal actions remain in M, the rounds progress. This is a key aspect of our algorithm's design, which eliminates the dependency of regret scaling on k by ensuring that the algorithm gradually queries only closely preferred actions. Recall the discussion following Equa- tion (2). In the next section, we provide an analysis of the performance guarantees of the algorithm.
R(T) S (C) (8) ( ((aN)(T) (TI/2=1)
where R < Mogg logo (T)] + is the maximum number of rounds and C = 2 log(1 log(1+4(62)-1) is a constant.
4. Analysis of MR-LPF
2
In this section, we present our main results on the perfor- mance of MR-LPF (Algorithm 1). The performance is given terms of the maximum information gain defined as
Remark 4.2. The value of (T( is kernel-specific and This term is a common complexity measure that appears in the analysis of both BO and BOHF in the existing literature (e.g., see Srinivas et al., 2010; Pásztor et al., 2024; Xu et al., 2024). Bounds on (T) have been established for various kernels. In particular, for linear kernels, (T) log()). For kernels with exponen- tially decaying Mercer eigenvalues, such as the Squared Exponential (SE) kernel, (T) = O(poly log(T)). For kernels with polynomially decaying eigenvalues, (T') grows polynomially (though sublinearly) with T. For exam- ple, in the case of the Matérn family of kernels, (T) (TT ), where d is the input dimension and v > 0.5 is the smoothness parameter (see, e.g., Vakili et al., 2021b). In Proposition 4 of Pásztor et al. (2024), it is shown that the eigenvalues of the dueling kernel Ik are exactly twice those of the original kernel (see their Appendix C. Since the
[T)
(21 J.... (x) log det (1 (1+ (13)
max
where Kr is the kernel matrix of T observations.
Theorem 4.1 (Regret bound for MR-LPF). Consider the BOHF framework described in Section 2.1 and the MR-LPF algorithm presented in Algorithm 1. For 5 1). in MR-LPF, let
Rr
2 5
(6) - L B +
log(
(14)
Unlike in Section 1, where À was omitted from the expression of T, we include it here for clarity.
6

---

Bayesian Optimization from Human Feedback
maximum information gain (T) scales with the decay rate of the kernel eigenvalues (Vakili et al., 2021b), both kernels exhibit the same scaling of the information gain with T.
These bounds apply to scalar-valued feedback, which is richer than the binary preference feedback used in BOHF,
For technical details, consider a standard BO setting with scalar observations = f(x;) + EG. where are i..d. zero-mean noise terms (following the notation in Sec- tion 2.3). Suppose that at each step t, instead of observing o2 = f(x)) + E, and df f(x() + Ez. we receive binary preference feedback y, 1 > o.}. Under the BTL model, this corresponds to the case where the noise differ- ence - follows a logistic distribution, which can arise if the individual noise terms E, are Gumbel-distriuuted Thus, the lower bound on sample complexity in the BOHF setting should be at least half of that of conventional BO under Gumbel noise for achieving at most e loss in the value of the target function.
Remark 4.3. By substituting the value of ((R) the ex- pression of the regret bound can be simplified
R(T) = (VIATTTTOss (2]] )
(15)
as T becomes large. This represents a sublinear regret growth rate for broad class of commonly used kernels where Ix (T) grows sublinearly with T.
Our regret bounds eliminate the dependency on K. MR-LPF gradually queries only closely preferred actions, reducing the effective impact of the curvature of the link function. Our regret bounds also show an O (VT(T) improvement compared to Pásztor et al. (2024) and an O ((T(T)))\/1) improvement over Xu et al. (2024). This becomes particu- larly crucial for kernels with polynomially decaying eigen- values, where existing results may become vacuous, failing to guarantee sublinear regret in T.
Since the lower bound construction in Scarlett et al. (2017) assumes Gaussian noise, formal comparison is not strictly valid (as the BTL model corresponds to Gumbel noise). We therefore present this connection as an informal justifica- tion of the tightness of our bounds, rather than a formal optimality proof.
4.2. Confidence Intervals and Proofs
4.1. Sample Complexity and Simple Regret
An important building block in analyzing the performance of MR-LPF is the confidence intervals applied to the samples collected in each round. We now present a formal statement of this result.
In certain applications, the learner may be primarily con- cerned with eventual performance, specifically the simple regret after T' observations. Accordingly, we can pose the dual question: How many samples are required to achieve simple regret? This aspect of our algorithm's ' performance formalized in the following corollary.
Theorem 4.7 (Confidence Bounds). Consider the kernel- based prediction he and uncertainty estimate oi for a datasel H, and a known kernel 1k, as given in Equations (7) and (10) satisfying Assumption 2.1. Assume the observa- tion points (1,, d=) are independent of the observation values 1 For a fixed (x, X X for any 8 E (0, 1), we have, with probability at least 5,
Corollary 4.4. Under the setting of Theorem 4.1, assume T = tR the time step at the end of round R. For any action arr E MR+1, we have, with probability at least 5,
1 Ppx= > kr) - - (3)
RT (T)
(u(h((z,aa)) p(h(x,
(0,(xxx2))) x x0)11 S (0,)),(
(17)
(16)
T
where 3(0) L L(B+
x log L 2x
The proof is given in Appendix B, that follows from Theo- rem 4.
supz,'Ex (ah((,, x')) as defined in Theorem 4.1, B is the RKHS norm bound specified in Assumption 2.1, X is the parameter in kernel-based regression, and k. is defined in Equation (2).
Corollary 4.5. As consequence of Corollary 4.4, assume we run MR-IPF for T = In rounds and select ir E MM+1 arbitrarily. In the case of a linear kernel with some T =
Ö Aoogg 1)) an SE kernel with some T Ö
log( !)
A key distinction in our results is that our confidence interval is tighter than the one presented in Pásztor et al. (2024) by factor of O /T()). This improvement comes from the multi-round structure and action selection rule within each round of the algorithm, which ensures that the observation points used for confidence intervals at the end of rounds are independent of the observation values within that round. This removes certain intricate dependencies in deriving the confidence interval. Recall that the observation points in
and a Matérn kernel with some T = Ô log( +
with probability at least 8, at most e error guaranteed: P(x' (T) S
2+
Remark 4.6. Our sample complexities match the Ω
lower bounds for conventional BO with Matérn kernels, as established in Scarlett et al. (2017) (up to logarithmic terms).
7

---

Bayesian Optimization from Human Feedback
Morth LCB
Acaerppe Rogie
Step:
time Step:
Stepe
(a) SE kemel (RKHS)
(b) Matérn kernel with v = 2.5 (RKHS) (c) Matérn kernel with v = 1.5 (RKHS)
Aoerage begret
Avarago Reyne
Overgge Regret
Step:
Step:
Step.
(d) SE kernel (Ackley)
(c) Matérn kernel with v 2.5 (Ackley) (f) Matér kernel with v 1.5 (Ackley)
Figure 1. Average Regret against T with RKHS test functions (top row) and Ackley test function (bottom row). The shaded area represents the standard error.
each round, (f(n..) (nrr)) are collected solely based the variance, which is independent of the observation values by definition. In contrast, both the MaxMinLLB algorithm in Pásztor et al. (2024) and the POP-BO algorithm in Xu et al. (2024) select observation point at step t based on statistics that depend on {v:) 1 We emphasize that our algorithm is by no means pure exploration algorithm: it effectively balances exploration and exploitation by learning and updating M, at the end of each round.
2024, Algorithm 1) various test functions, including both synthetic and real-world cases. Our implementation is publicly available.
We first select the test function f as an arbitrary function in the RKHS of a known kernel. To do this, we choose 10 points in the [o, 1] interval and assign them random values. We then fit standard kernel ridge regression to these sam- ples using kernel & and use its mean f. The kernel k is set to the SE kernel and Matérn kernels with smoothness pa- rameters = 2.5 and v = 1.5. This is common approach to constructing functions in an RKHS (see, e.g., Chowd- hury & Gopalan, 2017). We also test the algorithms on the Ackley function, similar to Pásztor et al. (2024). The Ack- ley function has a diverse optimization landscape, featuring multiple local minima, flat plateaus, and valleys, making it popular choice in non-convex optimization literature (Jamil & Yang, 2013).
Given the confidence intervals in Theorem 4.7, the update rule of M, in MR-LPF ensures that the best action is not eliminated (Lemma B.2). Additionally, we can use the confidence intervals to bound the regret for each action in My. based on the maximum variance in predictions from previous rounds. By summing up the regret over all rounds, achieve the overall regret bound, with details provided in Appendix B. For proof of Theorem 4.7, see Appendix C.
To showcase the utility of our approach in real-world ap- plications, we experimented using the Yelp Open Dataset* of restaurant reviews. This serves as a proof of concept, demonstrating both the potential integration of BOHF with LLM-ggenrrted vector embeddings and the scalability of the method to nigher-dimensional domains. The objective is to learn user preferences from comparative feedback and recommend restaurants tailored to each user's choices. Af- ter data filtering and pre- pre-processing. the dataset consists of 275 restaurants, 20 users, and 2563 reviews. Each restau- rant is represented by 32-dimensional vector embedding of its text-based reviews, generated using OpenAl's text-
MONEFLES
Average Regret
Time Step:
T
Figure 2. Average regret against T for the experiment with Yelp Open Dataset. The shaded area represents the standard error.
Pnttps / htt///tttu/b.ee//////// com/ www.ayalkaaaaaaaa code_ s submiss sonn 'Yelp Open Dataset
5. Experiments
We run numerical experiments to evaluate the performance of MR-LPF and compare it to MaxMinI.CB (Pásztor et al.,
8

---

Bayesian Optimization from Human Feedback
embedding-3-BBl model?. Users rate restaurants on scale from 1 to 5. We adopt the experimental setup and Yelp data preprocessing from Pásztor et al. (2024) to ensure fair evaluation. While we implemented our own version instead of using their code directly, we acknowledge their contribution in establishing this benchmark, which inspired our experiment. We frame this problem within the BOHF framework, where the action set X consists of 275 restau- rants, each represented as a 32-dimensional vector, and the utility values correspond to user ratings. SE kernel is used for these experiments. For details on the experimental setup, see Appendix D.
References
Abbasi- Yadkor, Y.
Online learning for linearly parametrized control problems. 2013.
Ailon, N., Karnin, Z.., and Joachims, T. Reducing dueling bandits cardinal bandits. In International Conference on Machine Learning, pp. 856-864. PMIR, 2014.
Arora, S., Du, S. S., Hu, W. Li, Z., Salakhutdinov, R. R., and Wang, R. On exact computation with an infinitely wide neural net. Advances in Neural Information Pro- cessing Systems, 32, 2019.
We plot the average regret at each time step, averaged over 60 independent runs. Figure shows the results on the RKHS and Ackley test functions, while Figure presents the results the Yelp Open Dataset. MR-LPF consis- tently achieves lower regret than MaxMinI across all test functions. The initial regret of MR-LPF reflects highly exploratory behavior during the early rounds. At the end of each round r, suboptimal actions are removed from My, leading to the sharp drops that eventually result in near- optimal actions in later rounds. Relatively constant behavior within rounds represents exploration, while sharp drops in- dicate exploitation.
Balandat, M., Karrer, B., Jiang, D. R., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E. BoTorch: A Framework for Efficient Monte-Cart Bayesian Optimization. In Advances in Neural Information Processing Systems 33, 2020.
Bengs, V., Busa-Fekete, R., El Mesaoudi-Paul, A., and Hüllermeier, E. Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research, 22(7):1 2021.
Bengs, V., Saha, A., and Hüllermeier, E. Stochastic con- textual dueling bandits under linear stochastic transitivity models. In International Conference on Machine Learn- ing, pp. 1764-1786. PMLR, 2022.
6. Conclusion
Borovitskiy, V., Terenin, A., Mostowsky, P., et al. Matérn gaussian processes on riemannian manifolds. Advances in Neural Information Processing Systems, 33:12426- 12437, 2020.
We proposed MR-LPF for the BOHF problem and proved regret bounds and sample complexities, significantly im- proving upon existing work. We established that the number of preferential feedback samples required to identify near- optimal actions is of the same order as the number of scalar- valued feedback samples. Numerical experiments on both synthetic and real-world examples support our analytical results.
Bradley, R. A. and Terry, M. Rank analysis of incom- plete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-3)) -4424444,111 1952.
Brochu, E., Cora, V. M., and De Freitas, N. A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint urXiv: 2512,,599 2010.
Acknowledgments
We thank the reviewers and the Area Chair of ICML for their valuable feedback. We are especially grateful for the Area Chair's thorough and insightful comments, which clearly reflect a significant investment of time and have substantially improved the final version of this work.
Chen, L., Chen, J., Goldstein, T., Huang, H., and Zhou, T. Instructzero: Efficient instruction optimization for black- box large language models. In International Conference on Machine Learning, pp. 6503-6518. PMLR, 2024.
Impact Statement
Chen, X., Zhong, H. Yang. Z., Wang, Z. and Wang, L. Human- in-the-loop: Provably efficient preference- reinforcement learning with general function approxima- tion. In International Conference on Machine Learning, pp. 3773-3793 PMLR, 2022.
This work presents analytical research aimed at advancing the field of Machine Learning. While the work has potential societal implications, none are considered immediate or require specific emphasis at this time.
'OpenAl Vector Embeddings
Chowdhury, S. R. and Gopalan, A. On kernelized multi- armed bandits. In International Conference on Machine Learning, pp. 853. PMLR, 2017.
httpps: / thub. com / aagaaup/ LLC.

---

Bayesian Optimization from Human Feedback
Christmann, A. and Steinwart, I. Support Vector Machines. Springer New York, NY, 2008.
Lin, X., Wu, Z., Dai, Z., Hu, W. Shu, Y., Ng. S.-K., Jaillet, P., and Low, B. K. H. Use your instinct: Instruction opti- mization using neural bandits coupled with transformers. In NeurlPS 2023 Workshop on Instruction Tuning and Instruction Following, 2023.
Das, N., Chakraborty, S., Pacchiano, A., and Chowdhury, S. R. Active preference optimization for sample efficient rlhf. In ICML 2024 Workshop on Theoretical Foundations of Foundation Models, 2024.
Lin, X.,, Dai, Z., Verma, A., Ng. S.-K., Jaillet, P., and Low, B. K. H. Prompt optimization with human feedback. In ICML 2024 Workshop on Models of Human Feedback Al Alignment, 2024.
Dudík, M., Hofmann, K., Schapire, R. E., Slivkins, A., and Zoghi, M. Contextual dueling bandits. In Conference on Learning Theory, pp. 563-587. PMLR, 2015.
Mehta, V., Das, V., Neopane, O., Dai, Y., Bogunovic, I., Schneider, J., and Neiswanger, W. Sample efficient re- inforcement learning from human feedback via active exploration. arXiv preprint
Falahatgar, M., Orlitsky, A.,, Pichapati. V., and Suresh, A. T. Maximum selection and ranking under noisy compar- isons. In International Conference on Machine Learning, pp. 1088-1096. PM 2017.
2023a.
Mehta, V., Neopane, O., Das. V., Lin, S., Schneider, J., and Neiswanger, W. Kernelized offline contextual du- cling bandits. In ICML Workshop The Many Facets of Preference- Learning, 2023b.
Faury, L., Abeille, M., Calauzènes, C., and Fercoq. O. Im- proved optimistic algorithms for logistic bandits. In- ternational Conference on Machine Learning, pp. 3052- 3060. PMLR, 2020.
Mercer, J. Functions of positive and negative type, and their connection with the theory of integral equations. Philo- sophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physi- cal Character, 209:415 446, 1909. ISSN 02643952.
Frazier, P. I. A tutorial on bayesian optimization. arXiv 2018.
preprint
Gardner, J. R., Pleiss, G., Bindel, D., Weinberger, K. Q., and Wilson, A. G. Gpytorch: Blackbox matrix-matri gaus- sian process inference with gpu acceleration. In Advances in Neural Information Processing Systems, 2018.
Mikkola, P., Todorović, M., Järvi, J., Rinke, P., and Kaski, S. Projective preferential bayesian optimization. In Interna- tional Conference on Machine Learning, pp. 6884-6892. PMLR, 2020.
González, J., Dai, Z., Damianou, A., and Lawrence, N. D.
Preferential bayesian optimization. In International Con- ference on Machine Learning, pp. 1282-1291. PMLR, 2017.
Novoseller, E., Wei, Y., Sui, Y., Yue, Y., and Burdick, J. Dueling posterior sampling for preference-based rein- forcement learning. In Conference on Uncertainty in Artificial Intelligence, pp. 1029-1038. PMLR, 2020.
Griffith, S., Subramanian, K., Scholz, J., Isbell, C. L., and Thomaz, A. L. Policy shaping: Integrating human feed- back with reinforcement learning. Advances in Neural Information Processing Systems, 26, 2013.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 15:27730-27744 2022.
Jamil, M. and Yang, X.-S. A literature survey of benchmark functions for global optimisation problems. International Journal of Mathematical Modelling and Numerical Opti- misation, 4(2):150-194, 2013.
Pásztor, B., Kassraie, P., and Krause, A. Bandits with preference feedback: A stackelberg game perspective. In Advances in Neural Information Processing Systems 38, 2024.
Jones, D. R., Schonlau, M., and Welch, W. J. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13:455-492, 1998.
Pedregosa, F. Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D.,, Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2838 2011.
Li, X., Zhao, H., and Gu, Q. Feel-good thompson sampling for contextual dueling bandits. In Forty-first International Conference on Machine Learning, 2024.
Li, Z. and Scarlett, J. Gaussian process bandit optimiza- tion with few batches. In International Conference on Artificial Intelligence and Statistics, pp. 92-107. PMLR, 2022.
Saha, A. Optimal algorithms for stochastic contextual prefer- ence bandits. Advances in Neural Information Processing Systems, 34:30050-3000 30062, 2021.
10

---

Bayesian Optimization from Human Feedback
Saha, A. and Krishnamurthy, A. Efficient and optimal algo- rithms for contextual dueling bandits under realizability. In International Conference on Algorithmic Learning Theory, pp. 968-994, PMLR, 2022.
Verma, A., Dai, Z., Lin, X., Jaillet, P., and Low, B. K. H.
Neural dueling bandits: Preference- optimization with human feedback. In The Thirteenth International Conference on Learning Representations, 2025.
Saha, A., Pacchiano, A., and Lee, J. Dueling rl: Reinforce- ment learning with trajectory preferences. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 6263-6289. PMLR, 2023.
Vershynin, R. High-dimensional probability: An introduc- tion with applications in data science, volume 47. Cam- bridge university press, 2018.
Whitehouse, J., Ramdas, A., and Wu, S. On the sublin- ear regret of gp-ucb. Advances in Neural Information Processing Systems, 36, 2024.
Salgia, S., Vakili, S., and Zhao, Q. A domain-shrinkin based bayesian optimization algorithm with order- optimal regret performance. Advances in Neural Infor- mation Processing Systems, 34:28836 28847, 2021.
Wu, R. and Sun, W. Making RL with preference- -ased feedback efficient via randomization. In The Twelfth International Conference on Learning Representations 2024.
Scarlett, J., Bogunovic, I., and Cevher, Lower bounds on regret for noisy gaussian process bandit optimization. In Conference Learning Theory, pp. 1723 1742. PMLR, 2017.
Xu, W., Wang, W., Jiang, Y., Svetozarevic, B., and Jones, C. Principled preferential bayesian optimization, In In- ternational Conference on Machine Learning, pp. 55305- 55336. PMLR, 2024.
Schölkopf. B.. Herbrich, R., and Smola, A. J. A general- ized representer theorem. International conference on computational learning theory, pp. 416-426. Springer, 2001.
Xu, Y., Joshi, A., Singh, A., and Dubrawski, A. Zeroth order non-convex optimization with dueling-choice bandits. In Conference on Uncertainty Artificial Intelligence, pp. 899-908. PMLR, 2020a.
Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and De Freitas, N. Taking the human out of the loop: A review of bayesian optimization, Proceedings of the IEEE, 104 (1):148-11)) 175, 2015.
Xu, Y., Wang, R., Yang, L.,, Singh, A., and Dubrawski, A. Preference- reinforcement learning with finite-time guarantees. Advances in Neural Information Processing Systems, 33:18784-18777 18794, 2020b.
Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. Gaussian process optimization the bandit setting: No regret and experimental design. In International Confer- ence on Machine Learning, 2010.
Yue, Y. and Joachims, T. Interactively optimizing informa- tion retrieval systems as a dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 1201-1208, 2009.
Takeno, S., Nomura, M., and Karasuyama, M. Towards practical preferential bayesian optimization with skew gaussian processes. In International Conference on Ma- chine Learning, pp. 13516-335333 PMLR, 2023.
Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5): 1538-1581551 2012.
Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-2 294, 1933.
Zhan, W., Uehara, M., Kallus, N., Lee, J. D., and Sun, W. Provable offline preference-based reinforcement learning, The Twelfth International Conference on Learning Representations, 2024.
Vakili, S., Bouziani, N., Jalali, S., Bernacchia, A., and Shiu, D.-s. Optimal order simple regret for gaussian process bandits. Advances in Neural Information Processing Systems, 34:21202-21215, 2021a.
Zoghi, M., Whiteson, ative upper confidence bound for the k-armed ducling bandit problem. In International Conference on Machine Learning, pp. 10-18. PMLR, 2014.
S., Munos, R., and Rijke, M. Rel-
Vakili, S., Khezeli, K., and Picheny, V. On information gain and regret bounds in gaussian process bandits. In International Conference Artificial Intelligence and Statistics, pp. 92-90.11 PMLR, 2021b.
Zoghi, M., Whiteson, S., and de Rijke, M. Mergerucb: A method for large-scale online ranker evaluation. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining, pp. 17-26, 2015.
Valko, M., Korda, N., Munos, R., Flaounas, I., and Cris- tianini, N. Finite-time analysis of kernelised contextual bandits. In Uncertainty in Artificial Intelligence, 2013.

---

Bayesian Optimization from Human Feedback
A. RKHS and Mercer Theorem
Mercer's theorem (Mercer, 1909) provides a way to represent a kernel using an infinite-dimensionall feature map (see, e.g., Christmann Steinwart, 2008, Theorem 4.49). Let be compact metric space. and let be finite Borel measure Z (in this context, we consider the Lebesgue measure in a Euclidean space). Denote by (Z) the of square-integrable functions on 2 with respect Additionally, say that kernel is square-integrable if
J k2(,,, du(=) < Co.
Theorem A.1. (Mercer Theorem) Let Z be a compuct metric space and u be a finite Borel measure on Z. Let k be continuous and square-integratee kernel, inducing an integral operator Ta (Z) + (Z) defined by
(Taf) (l,
where f E LZ) Then, there exists sequence of ceriraalue-egeeffaturee pairs {17mm (m)) pm)mm=m such that Yn 0. and Teem Pm for 1. Moreover, the kernel function can be represented
20
((2,2)=
=
mm Pm (2) (z'),
m=1
where the convergence of the series holds uniformly on Z.
According to the Mercer representation theorem (e.g., see, Christmann & Steinwart, 2008, Theorem 4.51), the RKHS induced by can consequently be represented in terms of {(Tms pm))m==1
Theorem A.2. (Mercer Representation Theorem) Let {17m fm)) be the Mercer eigenvalueeeigenfeauuee pairs. Then, the RKHS of lo is given by
H4 f())
Σ
Wm (mm Wm @R
Mercer representation theorem indicates that the scaled eigenfeatures {m 1m form an orthonormal basis for Hk. Definition A.3. A kernel is said to have polynomial (exponential) eigendecay if 7m O(m -P) (Tm O(e")), for some p > 1 (c < 1), where 7m are the Mercer eigenvalues in decreasing order.
Specific kernel functions:
1. Linear kernel: ((x,x') = xTaa
2. Squared Exponential (SE) kernel: k(x, x²)= = 0² exp length-scale of the kernel.
[x==211 (-1e7)" 212
where o² is scalar and | > 0 is referred to the
3. Matérn kernel: k(x, Pel 22 (2 Kv 2v ( where > 0.5 is the smoothness parameter of the kernel, 1 referred to as the length-scale, K,, is the modified Bessel function, and I is the Gamma function. 7 where d is the input dimension.
For the Matérn kernel, the eigenvalues decay polynomially with = 1 +
20
B. Proof of The Regret Bound and Sample Complexities
In this section, we provide a detailed proof of Theorem 4.1 the regret bound of MR-LPF and following corollaries.
B.1. Proof of Theorem 4.1
To prove this theorem, we bound the regret for each round and then sum these bounds over all the rounds.
12

---

Bayesian Optimization from Human Feedback
Regret in the first round: The first round consists of N1 [v]] samples. We note that for all 1,
P(x* > xz) + F(x* > x 1 2
(18)
2
Consequently, the regret incurred in the first round in bounded by 1 T.V..
For the second round onwards (r 2 2), we introduce some notation and preliminaries that will assist in bounding the regret.
High probability events: Let us define the event &, as the event that all confidence intervals used in the round r the MR-LPF algorithm hold true. Specifically,
&, E, = = MMr (u(h(s.))(x,z')) p(h(a,,))) (((M,,) B()) (100
(19)
Recall that (8)) L B x log( 2R121) 8
We also define & U Ep.
Sum of the posterior variances for sequence of observations: variances in each round (see, c.g., Pásztor et al., 2024, Lemma 14).
We apply the following bound the sum of posterior
N in (n-1 (Rto)) S log(1 4(Ax,)--1) T (Amm,) (N,)))
8
(20)
By the selection rule of (I(m.)) vn Nr, o (N,..) x²) $ (n-1,r)
T (n.)) in MR-LPF as the points with the highest variance, we have that Vr, x' E Mr, and (I( (I(n.r) R )) Combining this with Equation (20), conclude that Vxx x' M,,
I (N),)
((N,))(Z,2)) V log(1 + 4(Ar,,))
(21)
Nr
The value of K,, 2: Recall the update rule for M, in MR-LPF:
M,41 = fx M,lVa's E MM ((hex.)))o)( + ()) 5)
(22)
Assuming ε1, for all x. M2, have
n(h(a,=²)) + (M. 2 ((hx),)(o,='))
(n),,))))
(23)
2'
where the first inequality holds under E and the second inequality is a consequence the update rule. Similarly, we have
u(h(2', x)) + (M, (d'
(24)
2
We note that Vz, x' e X, ((h(a', = p(h(2x, x')). Thus, Equation (24) implies that
u(h(z,2')) S 5 + ((.
(25)
Combining with (23), we obtain that
-23 (o. u(h(a, < ((
(26)
13

---

Bayesian Optimization from Human Feedback
We previously established bound on the standard deviation the end of rounds in (21). Applying this the first round, with length N1 [VT], bound ju(((x; x²)) for all x, E M2 within the interval [ 4] by ensuring 2y s 7. Specifically, let To be the smallest integer satisfying
8
T (Amo(VVo)) [Tbb]
2 log(1 + 4(Ax))
(27)
4
Then, for any T 2 To. for all 2,, x' E M2, we have jul(a,, x²)) E [ 11 Recall that the derivative of the sigmoid function given by j((x) (1(-)(1 - sd.)). Consequently, the inverse of the derivative of the sigmoid applied to h, for the values of n, v, M2, is bounded as follows. For all x, x' E MM2.
16
S < 6.
(28)
p(h(z, (1)( u(((a,,))))
3
Thus, can Ky for all 2. maintaining the validity of the confidence intervals.
Lemma B.1. For T Tu specified in Equation (27), we have PPE) S 1
The proof follows from Theorem 4.7, union bound over all action pairs and rounds, and the bound on K, derived above. We condition the remainder of the proof the event T > To and E
The hest action x² will not be removed. Assuming & the best action will not be removed from the sets M, by the MR-LPF algorithm in any round. We formalize this observation in the following lemma.
Lemma B.2. Under event E, x² Ma.
The proof follows from the observation that p(h(x", ,x)) 2 for all Combining with the confidence intervals in E, Vr, Vo E My, (r)((..))) (x", ,x)) +
(0)) (x", ,.) 2 Consequently, the best action x² will not be removed.
We are now ready to bound the regret in rounds r 2 2.
Regret bound in each round r 2 2: For each & E M,, we use the update rule MM in MR-LPF to bound the regret with respect to the optimal action. Recall that in Lemma B.2, we showed that the optimal action remains in M, for all r. We have
p(h(x,
1on 2 p(h(,,...-1)(0,,. (x,xx)))) + B ((r-1)(0)0 1.-- (0-1
(29)
where the first inequality holds under E, and the second inequality follows from the update rule of M,. Then, we have
p(h(x", x)) = p(h(2xx")
1
< 2 +
x*),
(30)
The equality follows from x(-.)= (u.),, and the inequality follows from (29).
We thus have for all x Mr.
1 28(r-11(0)0(M, 1,-,1)(11
p(h("" (x))
10
(31)
Nr-1
where the second incquality is proven in (21), and we use C'
log(1 (gg(1-4(6A) 1j to simplify the notation. This bound holds for all points in round r. Therefore, to obtain the regret in round r, it sufficient to multiply this bound by Nr. This results in the following bound on the regret in round
14

---

Bayesian Optimization from Human Feedback
T (amm-)((N--) Nr11
Regret in Round r r 2286--1((0)CN,
VTT(NN(T) + VN--, V S 220(-1)(88C
$ 2 (TT +T (TaN((T))
(32)
where the second inequality is obtained by substituting N, [VN--1T") and using |.1 S 1. We also use that To ()() S (42)()) since K4-1 2 4. The third inequality follows from N, 2 VT for all 1.
Total regret: The number of rounds R is at most [log log2(T) 1 (Li & Scarlett, 2022, Proposition 1). Using the bound on regret in each round, we can bound the total regret of MR-LPF algorithm as follows
R(T)= S (6) TI (T)) (C (T(ax)(T).
(33)
This completes the proof of Theorem 4.1.
B.2. Proof of Corollary 4.4
Since the size Ny of rounds increase with r, we have NR 2 R.R. In the proof of Theorem 4.1, in (31), we showed that, for all x E M,
()
u(h(x", 2 S 23 22)1-110)01
N,
Thus, for x E MR+1, we have
1 u(h(x*,2)) -
[(a)((N))
(8
NR
RT (A)) T
< (8)(
(34)
RT (4x) (8)
(35)
T
where, for the second inequality, we used NR 2 T. and for the third inequality, we used NR S T.
B.3. Proof Corollary 4.5
Following the bounds obtained in Corollary 4.4, we determine T that ensures p(h(ār, x)) S c, after T steps. For this, we need specification of (T).
In the case of linear kernels, we have ['x Oddlog(T)). Consequently, choice of T Ô ( [dlon(t) + ensures
u(h(x", x))) 1 Se.
In the of SE kernel, we have [T) Olog d+1 (T)). Consequently, choice of T Ô log(3)
ensures
u(h(o,, x)) S.
In the case of Matérn kernel, we have [T) Ö( xoत)). ). Consequently, a choice of T Ö u(h(x",,)) < e.
(log(?))
ensures
2+
For the bound on (T) see, e.g., Vakili al. (2021b).
15

---

Bayesian Optimization from Human Feedback
C. Proof of Theorem 4.7
Recall the conventional kernel-based regression discussed in Section 2. Various confidence intervals of the form If(x) f<(=)] & (z)) where fz(=) and (z(2) are the conventional prediction and standard deviation, and (()) is a confidence interval width multiplier for a 5 confidence level, have been demonstrated in several works (Abbasi-Yadkori, 2013; Chowdhury & Gopalan, 2017: Vakili et al., 2021a; Whitehouse et al., 2024). As discussed in the preference- case, the problem becomes more similar to a classification problem with binary feedback, and these confidence intervals are not directly applicable. Moreover, a dlosed-form solution for he is not available, as it is only provided as the minimizer of the loss function given in Equation (7). Additionally, discussed, this loss and its solution can be parameterized using the representer theorem.
(x [Hl+) =
Ui log u( a (xx,,
(1 Ue) log(1 - 110 1e + 2 211012
(36)
and
h.(-) Σ 0,k (1, (11;
(37)
For the remainder of the proof, and for simplicity of presentation, we use the notation = = (ar, 2²) and similarly 2; (x,, at).
In both Xu et al. (2020b) and Pásztor et al. (2024), confidence intervals for [h(=) - [=)] are derived, with Pásztor et al. (2024) establishing tighter bounds. Their confidence intervals based the results of Faury et al. (2020) for logistic bandits and Whitehouse et al. (2024) for confidence intervals in kernel bandits. In comparison, our confidence intervals are tighter than those presented in Pásztor et al. (2024) by a factor of O (T))). We achieve this improvement by assuming that the sequence of observation points {= is independent of the observation values M inspired by Vakili et al. (2021a). This assumption is made possible in our work due to the design of the MR-LPF algorithm, where within each round, the observation points are selected based solely on kernel-basee variance, which, by definition, does not depend on the observation values.
The main steps of the proof are similar to those in the proof of the confidence interval in Pásztor et al. (2024), and we will highlight the key differences in our proof. The key idea is that the derivative of the loss Lr. as given in Equation (36), is the null operator at the minimizer of the loss:
VL(O,, H.)
Σ
))) - (O.) 0,
(38)
i=1
where g: (0) :4 Hu is a linear operator defined as
ge (0) Σ k(zza-)uue )u(( IK(z, :) A0.
(39)
Recall that is the minimizer of the loss in Equation (36). Consequently, we have ge(O.) = Ei Vil((z,)) -).
Then, confidence intervals are proven for the gradient and extended to the preference function itself. We now introduce some auxiliary notation that will be helpful throughout the rest of the proof. Let + (K(21,)), ((22 which we define the kernel matrix K, 2 and the operator S; = Φ 4,, We also use 4 to denote the t-dimensional identity matrix and IN to denote the identity operator in the RKHS. Finally, we define V, = S. + kNH..
()] from
We also use the auxiliary notation G. as in Appendix of Pásztor et al. (2024), where
G.(01,02) = AI + Σ al2; 0, 01 (xs),
and
a(2,01,02) = =10 | ((v0)6())+(1-)11)))) du
16

---

Bayesian Optimization from Human Feedback
the coefficient arising from the mean value theorem, such that
m66 o(z)) - u (())) = a(2, 01, - 81)Td(2)
See Pásztor et al. (2024, Lemma 11) for details. It then follows that
ge (0)) Ge(O1. (2) 01),
(40)
as shown in the proof of Lemma 12 in Pásztor et al. (2024). We use this relation, along with the inequality
G,(01, 02) ž 'V,
(41)
where 2 denotes the Loewner order, also from the proof of Lemma 12, in our analysis.
We use the notation h=z) Φ (z)0* for the underlying preference function and 6; - y/ ((((zz)) to represent the sequence of observation noise.
Inspired by the proof of confidence intervals in Vakili et al. (2021a), we express the prediction error as
(n(h((z)) = (1)(2=) ( h(=)l
[=] -0)00)
(z) .0) -
= L Φ G. 0,)
Σ (vi m(h(zz))) ((z)) )
L Φ (2) G 0.)
Σ ((z)) 110
S Φ (2) (. 00)-1
Σ e ((2+))
LA 10 G: 0* Rias Term
Stochustic Term
The first line follows from the Lipschitz continuity of the sigmoid function. The second line uses the representer theorem to express (2)2) = o (z)0, and h22) = Φ (z)0+, where ((z) = k<zz -), defined similarly to (Pásztor et al., 2024, Appendix A). The third line uses (40). The fourth line uses that 0, is the minimizer the loss Equation (36). The fifth line uses the notation E, = yi - ())(2;)) for the observation noise. Finally, the expression is split into stochastic term and bias term, allowing to follow the proof structure of the confidence bound in (Vakili et al., 2021a, Theorem 1).
The stochastic term is sub-Gaussian random variable and can be bounded with high probability using standard concentra- tion results. In particular, the sub- Gaussian parameter is determined by the norm of the coefficients applied to the independent noise terms E,, which are 12-sub-Gaussiaa This follows from the fact that e; = y: -=(h2,)) E [-u(h(>;)), ((((2)))) and therefore the noise sequence has bounded support of length
1
L (2) -0a
10 0,) Φ, 11
2
1
[x|| D.
1 < 2 L (or(s))
k
(42)
where || llap denotes the operator (spectral) norm. The first inequality follows from matrix arithmetic and the definition of operator norm. The second uses (41). The third uses the identity [(o(z)llv,- = - 0e(2) (see, e.g., Pásztor et al., 2024). along with || V.b.V-1o 6, llop S 1, which follows from the eigenvalue bounds of Φ.Φ, and V,-1
17

---

Bayesian Optimization from Human Feedback
Therefore, by the concentration inequality for sub-Gaussian random variables (see, e.g., Vershynin, 2018), with probability least 1 d,
1 $ L / (
L ( Gz)
Σ E ((()))
The bias term is bounded as:
LA Φ "," S [x (: 00:0000000000000000000000
[Avll - 10"
s [.Bo(=);
(43)
where the second line uses (41), and the third line uses [l 10 $ 1 B, which follows from:
1 oe(2), as discussed above. It also uses the bound vAx
VAx
A
A
1 S
B,
(44)
V
where the first inequality follows from the fact that the smallest eigenvalue of Vi is least Ax, and the second follows from the RKHS norm bound ||0* I B.
Combining both bounds gives the following expression for 3(6):
2k
B(6) = LB + 2 x log(2/8).
(45)
D. Experimental Details
In this section, provide details the experimental setting. We describe the RKHS test functions, the Ackley function, and the Yelp Open Dataset used in experiments. Additionally, outline the selected hyperparameters and the computational resources utilized in our simulations. We also present the MaxMinLCB algorithm of Pásztor et al. (2024).
RKHS test functions: In Section 5, we outlined the procedure for generating the test function f as an arbitrary function within the RKHS of given kernel. In Figure we display the test functions generated in the RKHS for the SE kernel and the Matérn kernels with 2.5 and y 1.5. The figure includes plots of the utility function f, the preference function Mxxxx" xt) = f(x) f(x'), and the probability of preference μ u(h(2,,2 2²)).
Ackley test function: It is defined as follows (with and X (-5,5)
f(x) exp
0.2
x
exp
d
cos (2 + +2 + exx(11)
The preference function h (difference in utilities) is then scaled to the range [-3.3]. The Ackley function is shown in Figure 3.
We use a subset the Yelp Dataset, filtering to include only restaurants in Philadelphia, USA, with at least 500 reviews and users who review at least 90 restaurants. The final dataset consists of 275 restaurants, 20 users, and 2563 reviews. Reviews for each restaurant are concatenated and processed using OpenAl's TEXT- TEXT-EMBEDDING EMBEDDIING33-ARCE model to generate 32-dimensional vector embeddings, which serve as the action set in the BOHF framework. User ratings (ranging from to 5) are considered as the utility function f. which are then scaled to the range [-3. 33, 3). Missing ratings are handled using collaborative filtering. In each experimental run, we sample a random user from the set of 20 and conduct the experiment independently. We average the regret over 60 runs to produce the final plot.
Yelp Dataset
18

---

Bayesian Optimization from Human Feedback
nox
(a) ((), SE kernel
(b) lo(xe, x²), SE kernel
(c) p(h((,,z)) SE kernel
x(h(x,)))
hix
(d) (xx, Matém (v 2.5)
(c) (x,,2)), Matérn (v = 2.5)
(f) ((h(2,22)) Matérn (v = 2.5)
x
(g) (x), Matérn (v 1.5)
(h) 1u(r, x'), Matérn (v = 1.5)
i p(l((,, x')), Matérn (u = 1.5)
hix x)
xtbox.x))
(i) (x), Ackley function
(k) 10x x'), Ackley function
(1) p(h(x, x')), Ackley function
Figure Plots of utility function fxx) preference function he x') = f(x)- and the probability of preference p(l((z, x') for synthetic experiments. The rows correspond to: (Ist row) SE kernel (RKHS). (2nd row) Matém keree with 2.5 (RKHS), (3rd (RKHS), and (4th row) Ackley function.
row) Matém kernel
19

---

Bayesian Optimization from Human Feedback
Loss function optinization: To minimize the loss function given in (9) and obtain the parameters 0, any standard optimiza- tion algorithm be used. In experiments, we employ gradient descent. The learning rate is individually tuned for each algorithm, kernel, and test function by selecting the best-performing value from the grid {0.01, 0.005, 0.001, 0.0005, 0.0001 in each scenario.
Hyperparameters: We choose 1 = 0.1 as the length scale and À = 0.05 as the kernel- learning parameter across all cases. The horizon is set to 300 for RKHS test functions and 2000 for the Ackley function and the Yelp Dataset. For the RKHS and Ackley functions, the confidence interval width / is fixed at for both MR-LPF and MaxMinL.BB. For the Yelp dataset, we conduct grid search to tune 3 over f0.01, 0.1, 0.5, 1, 1.2] for both MR-LPF and MaxMinLCB algorithms. We determine 3 2 as optimal for Max and 0.1 for MR-LPE.
Computational Resources: For the experiments with the synthetic RKHS and Ackley functions, we utilize the Scikit- Learn library (Pedregosa et al., 2) for implementing Gaussian Process (GP) regression. The code is executed cluster with 376.2 GiB of RAM and an Intel(R) Xeon(R) Gold 5118 CPU running at 2.30 GHz. In the case of the Yelp Dataset experiments, we use the BoTorch library (Balandat et al., 2020) and its dependencies, including GPyTorch (Gardner et al., 2018), which offer efficient GP regression tools with GPU support. The simulations are carried out on a computing node equipped with an NVIDIA GeForce RTX 2080 GPU featuring 11 GB of VRAM, an Intel(R) (Ron(R) Gold 5118 CPU running 2.40 GHz with 24 cores, and 92 GB of RAM.
MaxMinL algorithm: Pásztor et al. (2024) proposed a zero-sum Stackelberg (Folaer-)Folloer) game for action selection, where the leader 2n maximizes the lower confidence bound (LCB), and the follower xy minimizes according the following:
s 24 arg max (1he( o' (x)) (1, (x)),
x' (xx) arg min ((ha(zxx2)) - B,o,(1,00))
E'MM
20


Reviews:
[{"review_id": "Q7g1nUIvlV", "reviewer": "Reviewer_ntoB", "summary": "This paper proposes a Bayesian optimisation method with only human preference-based feedback instead of classical scalar values. The order-optimal sample complexities of conventional BO are recovered. That means the number of preferential feedback samples is of the same order as the number of scalar feedback.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback and constructive comments. Below, we provide detailed responses and will incorporate these suggestions to further improve the presentation of the paper.\n\n\n> In Section 3, the main algorithm is introduced but how to train the utility function kernel ridge regression model is not clear. How is the preference data used for the model training?\n\nThe preference function prediction is described in Section 2.3. Specifically, we express the preference function in terms of parameters $\\boldsymbol{\\theta}$ as shown in Equation (8), and obtain these parameters by minimizing the regularized negative log-likelihood loss defined in Equation (9). From a theoretical standpoint, any optimization algorithm can be used for this minimization. In our experiments, we employ gradient descent, and we clarify the choice of learning rate under *Experimental Details* in the appendix. Thank you for highlighting this point—we will ensure that this clarification is made explicit throughout the paper, including in Section 3 following the algorithm description.\n\n> For Ackley and Yelp data, do they satisfy the RKHS assumption?\n\nThe Ackley function is infinitely differentiable. By the equivalence between the RKHS of Matérn kernels and Sobolev spaces, it belongs to the RKHS of all Matérn kernels with smoothness parameter $\\nu \\ge 1.5$, which includes the Squared Exponential kernel. However, its RKHS norm is difficult to characterize explicitly. For the Yelp dataset, we cannot assert that the utility function belongs to the RKHS.\n\nWe interpret our experimental setup as follows: the RKHS experiments (first row of Figure 1) exactly match our theoretical assumptions and support the theory; the Ackley function provides a diverse optimization landscape while still fitting the theoretical framework; and the Yelp dataset offers a real-world test of practical utility. \n\n> One concern is the novelty of the proposed algorithm in Section 3 where the preference-based function learning is mainly based on the existing approaches reviewed in Section 2.3.   \n> Is there any difference between the proposed algorithm with the ones from the literature?\n\nThe key novelty and contribution of our work is the performance guarantees (regret bounds and sample complexities) we establish, which achieve near-optimality. We establish the key result that the number of preference samples required to identify near-optimal actions matches the order of scalar-valued feedback samples. This is in sharp contrast to prior works—existing bounds become vacuous in many cases of practical and theoretical interest, such as Matérn and Neural Tangent kernels.\n\nTo achieve these results, we propose the MR-LPF algorithm. While MR-LPF and its analysis build on the well-established literature on kernel methods and Bayesian optimization, it introduces important algorithmic and analytical innovations. In particular, the multi-round structure enables precise control over the dependency on $\\kappa$, as detailed in our analysis, and allows us to leverage the new confidence interval in Theorem 4.7 to obtain tighter bounds with respect to $T$.\n\nWhile inspired by Li & Scarlett (2022)’s work on standard BO, our algorithm and analysis differ due to the reduced preference feedback model, which introduces new challenges we address both algorithmically and analytically—including removing the dependency on the curvature of the nonlinear link function and confidence intervals for kernel methods from preference feedback.\n\n\n\n> The experimental evaluation where only one comparative method (MaxMinLCB) is given.\n\nWe chose MaxMinLCB as the baseline because it is one of the two existing BOHF algorithms with theoretical guarantees (along with POP-BO), and Pásztor et al. (2024) show that it outperforms POP-BO and several heuristic methods. This makes it the strongest and most relevant baseline for comparison.\n\nOur goal is to demonstrate that our algorithm not only significantly improves theoretical guarantees but also performs well empirically. \n\n---\nWe thank the reviewer for the positive feedback and constructive comments. We believe that addressing these points will significantly enhance the clarity and quality of our paper.", "claims_and_evidence": "The claims are supported by thorough analysis and some empirical studies.", "methods_and_evaluation_criteria": "Yes, but the way to handle preferences is not clear. In Section 3, the main algorithm is introduced but how to train the utility function kernel ridge regression model is not clear. How is the preference data used for the model training? \n\nThe comparative method is only MaxMinLCB. It would be better to include more related methods as baselines.", "theoretical_claims": "No, I did not check the proof process in detail. The claimed results look reasonable to me.", "experimental_designs_or_analyses": "The comparative method is only MaxMinLCB. It would be better to include more related methods as baselines.\n\nFor Ackley and Yelp data, do they satisfy the RKHS assumption?", "relation_to_broader_scientific_literature": "The main contribution of this work is the derived tighter performance guarantees compared with related works.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "One concern is the novelty of the proposed algorithm in Section 3 where the preference-based function learning is mainly based on the existing approaches reviewed in Section 2.3. \n\nThe other concern is the experimental evaluation where only one comparative method is given.", "other_comments_or_suggestions": "If the theoretical analysis is the main contribution of this work and algorithm design is not, I would suggest moving the section to subsection 2.4? The readers may mainly focus on the Section 4.", "questions_for_authors": "Is there any difference between the proposed algorithm with the ones from the literature?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qhkPSS7K7R", "reviewer": "Reviewer_yQVc", "summary": "This paper proposes a new algorithm, Multi-Round Learning from Preference-based Feedback (MR-LPF), for Bayesian Optimization from Human Feedback (BOHF). MR-LPF achieves a significantly improved regret bound of $\\tilde{O}(\\sqrt{Γ(T)T})$, matching the optimal regret bounds of conventional Bayesian optimization and eliminating the dependency on the curvature of the link function present in prior work. The algorithm operates in rounds, selecting pairs of actions with maximum uncertainty for preference feedback and iteratively refining a set of potentially optimal actions using confidence bounds.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comprehensive review and positive feedback on our work. We are glad that you found our theoretical contributions substantial and the algorithm well-motivated and clearly presented. Below, we respond to your questions and comments, which we hope will further clarify and improve the paper. \n\n> Comparison with POP-BO (Xu et al., 2024)  \n> Question 1: Why was POP-BO (Xu et al., 2024) not included as a baseline in the empirical evaluation?\n\n\nTheoretically, as discussed in detail in the introduction and summarized in Table 1, POP-BO provides the weakest regret bound among existing methods. In contrast, we achieve near-optimal regret bounds, explicitly showing that the number of preferential feedback samples required to identify near-optimal actions matches the order of scalar-valued feedback samples. Both MaxMinLCB and POP-BO exhibit vacuous regret bounds for kernels of practical and theoretical importance, such as Matérn and Neural Tangent kernels—with POP-BO being the weaker of the two.\n\nEmpirically, we selected MaxMinLCB as the comparative baseline because Pásztor et al. (2024) have already demonstrated that MaxMinLCB outperforms POP-BO as well as several heuristic approaches. Thus, our choice ensures that our algorithm is compared against the strongest and most relevant available baseline. We appreciate the reviewer highlighting this point and will clarify this rationale in the revision.\n\n\n> While the experiments show MR-LPF performing better than MaxMinLCB, the improvement is often not dramatic.\n\nWe fully agree with this observation. Indeed, the main contribution of our paper is analytical, and we establish substantial theoretical improvements over existing methods. The theoretical bounds we provide are *upper bounds* on performance. Based on the lower bounds for standard Bayesian optimization from Scarlett et al. (2017), our results are essentially unimprovable. It remains an open question whether the weaker bounds of Pásztor et al. (2024) and Xu et al. (2024) are artifacts of their proof techniques or reflect fundamental limitations of their algorithms—that is, whether the suboptimal upper bounds in those works truly capture the algorithms’ performance or whether tighter bounds could be derived for their algorithms.\nNonetheless, our experiments show that the empirical performance of our algorithm is consistently strong across a range of synthetic RKHS examples that closely follow the theoretical assumptions, as well as on a real-world Yelp dataset.\n\nThe goal of these experiments is to demonstrate that our contributions are not merely theoretical—they also yield a practical and robust algorithm with solid empirical performance, consistently outperforming the current state-of-the-art. That said, the main focus of our paper is to establish the core theoretical result: that the same number of preference samples are sufficient to identify near-optimal actions as in standard Bayesian optimization with scalar-valued feedback.\n\n> Despite motivating BOHF with applications like prompt optimization for LLMs, the paper does not include any experiments directly involving LLMs. This creates a disconnect between the stated motivation and the empirical evaluation.\n\nWe agree with the reviewer that our experiments do not directly involve learning tasks using LLMs—we only use OpenAI's text embeddings model to generate vector embeddings for Yelp reviews. However, the BOHF framework is strongly motivated by an expanding body of work closely related to dueling bandits and reinforcement learning from human feedback (RLHF). This motivation is further supported by the growing number of recent papers addressing the same or similar problems.\n\nOur method can also be directly applied to prompt optimization for LLMs. However, such experiments require extensive setup and thorough implementations, which we view as an important and promising direction for a separate future work.\n\n> Question 2. Could you clarify the derivation of the inequality in Equation (42) within the proof of Lemma C.1?\n\nThe inequality follows from the Sherman–Morrison formula and a rearrangement of terms. We will add the intermediate steps here and carefully review the proof to include clearer explanations at each step.\n\n--- \nThank you again for your positive and constructive review, which helps clarify and improve the presentation of the paper.", "claims_and_evidence": "The theoretical claims regarding the regret bound of the MR-LPF algorithm are supported by rigorous mathematical proofs presented in the appendices. These proofs build upon established techniques in Bayesian optimization and kernel methods, providing a clear and convincing argument for the improved theoretical performance. However, the empirical evidence presented to demonstrate the practical superiority of MR-LPF compared to existing methods is less convincing. While the figures show MR-LPF achieving lower regret than MaxMinLCB in the tested scenarios, the improvement is often modest, and the figures do not clearly illustrate the theoretical order-of-magnitude improvement suggested by the regret bounds. Further experiments with a wider range of benchmark functions and baselines, potentially including statistical significance testing, would be needed to fully substantiate the claim of superior practical performance. Specifically, the paper lacks the comparsion with POP-BO (Xu et al., 2024), making the experiments less convincing.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria generally make sense for the problem at hand.", "theoretical_claims": "I have not thoroughly checked every step of the proofs, which are complex and contained in the appendices.", "experimental_designs_or_analyses": "1. While the Yelp dataset provides a real-world application, the experimental setup is relatively limited. As your initial answer mentions, the paper itself highlights the increasing importance of preference learning due to LLMs. However, no experiments directly involve LLMs. A more compelling demonstration of practical utility would involve a task where preference feedback is elicited from human interactions with an LLM, for example, prompt optimization or text summarization comparison. This would more closely align the experiments with the motivating applications.\n2. A crucial comparison is missing: POP-BO (Xu et al., 2024). POP-BO is a direct competitor in the BOHF literature, and omitting it significantly weakens the empirical evaluation. Without this comparison, it's difficult to definitively assess MR-LPF's relative performance within the current state-of-the-art.", "relation_to_broader_scientific_literature": "The key contribution of this paper, a tighter regret bound for Bayesian Optimization from Human Feedback (BOHF), builds upon and significantly improves existing work in several areas. It relates to the broader literature on conventional Bayesian optimization (BO), where order-optimal regret bounds of $\\tilde{O}(\\sqrt{Γ(T)T})$ have been established for algorithms like GP-UCB and GP-TS (Srinivas et al., 2009; Chowdhury & Gopalan, 2017). The paper directly addresses the limitations of prior BOHF algorithms, specifically MaxMinLCB (Pásztor et al., 2024) and POP-BO (Xu et al., 2024), which had weaker regret bounds $\\tilde{O}((Γ(T)κ^2\\sqrt{T})$ and $\\tilde{O}((Γ(T)T)^{\\frac{3}{4}})$ respectively). The paper's achievement of a regret bound matching that of conventional BO, despite using the weaker preference-based feedback, is a notable advancement, demonstrating that the same sample complexities are achievable. The multi-round structure of the MR-LPF algorithm is inspired by, but distinct from, the Batch Pure Exploration (BPE) algorithm (Li & Scarlett, 2022) in conventional BO. It also connects to, but distinguishes itself from, dueling bandits and reinforcement learning from human feedback (RLHF) literature by focusing on kernel-based settings rather than tabular or linear settings.", "essential_references_not_discussed": "As far as i know, there is no more related paper needing to be cited in the paper.", "other_strengths_and_weaknesses": "## Strengths:\n- The paper's main strength is its theoretical contribution. It provides a new algorithm, MR-LPF, for BOHF and proves a significantly improved regret bound. This matches the order-optimal regret bounds of conventional Bayesian optimization and, crucially, eliminates the dependence on the curvature of the link function (κ) that plagued prior work. This is a substantial theoretical advancement in the field.\n- The MR-LPF algorithm is well-motivated and clearly presented. The multi-round structure, with its variance-based action selection and confidence-bound-based pruning, is intuitive and logically sound. The algorithm description is easy to follow.\n- The paper provides detailed proofs for its theoretical claims, building upon established techniques in Bayesian optimization and kernel methods. The appendices contain the necessary mathematical derivations.\n\n## Weaknesses:\n\n- The one of the most significant weakness is the omission of a comparison with POP-BO (Xu et al., 2024), a direct and highly relevant competitor in the BOHF literature. This makes it difficult to assess the relative performance of MR-LPF within the current state-of-the-art.\n- While the experiments show MR-LPF performing better than MaxMinLCB (only after a large number of queries), the improvement is often not dramatic, and the figures don't clearly showcase the theoretical order-of-magnitude improvement.\n- Despite motivating BOHF with applications like prompt optimization for LLMs, the paper does not include any experiments directly involving LLMs. This creates a disconnect between the stated motivation and the empirical evaluation.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "1. Why was POP-BO (Xu et al., 2024) not included as a baseline in the empirical evaluation?\n2. Could you clarify the derivation of the inequality in Equation (42) within the proof of Lemma C.1?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dzi4qAlUxH", "reviewer": "Reviewer_6Kza", "summary": "This paper studies Bayesian optimization (BO) with preference feedback, in which every time a pair of inputs are selected and only a binary preference feedback is observed. The paper incorporates preference feedback into a multi-round structure inspired by previous works and prove that the resulting algorithm achieves $\\sqrt{\\Gamma(T)T}$ regret which is nearly optimal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed, comprehensive, and constructive feedback. We are glad that you found the theoretical results strong and the provided insights useful. Below, we address the questions, which we hope will help clarify and enhance your evaluation of the paper.\n\n> Could the constants in the regret bound for BOHF be worse than those for scalar-valued feedback? \n\nWe naturally expect the constants to be worse, as the reviewer suggested, given that standard BO provides stronger feedback. While it is beyond the scope of this rebuttal to characterize the constants precisely—we note that even in standard BO, despite its extensive literature, there is no clear characterization of such constants—we are inspired by your comment to run experiments comparing empirical regret. Specifically, we will compare the regret, measured in terms of the underlying function values, for our BOHF algorithm and standard BO algorithms such as GP-UCB and BPE. Intuitively and as expected, we anticipate observing lower empirical regret for standard BO.\n\n> The proposed algorithm does not make use of the preference observations when selecting queries within a batch? In practice, incorporating these observations should lead to better performance. Could the algorithm be extended to account for them?\n\nThe confidence intervals are explicitly utilized at the end of each round to eliminate actions that are unlikely to be optimal, making effective use of preference predictions. However, incorporating preference predictions within each round introduces intricate statistical dependencies that invalidate our current analysis framework, including the validity of confidence intervals derived at the end of such rounds. In short, employing preferences both during and at the end of each round cannot be handled with our current theoretical tools and would require further theoretical development.\n\nEmpirically, the strong eventual performance of our algorithm relative to the state of the art demonstrates that our current approach—using preferences solely at the end of each round—is already effective in practice. \n\n> Technical challenges:\n\nAlthough inspired by existing methods, we introduce notable algorithmic and analytical novelties. In particular, the multi-round structure enables careful control of the dependency on $\\kappa$, as detailed in our analysis and discussed at the bottom of page 6. Moreover, this structure allows us to leverage the new confidence interval established in Theorem 4.7, further improving the regret bounds with respect to $T$.\n\nTogether, these improvements contribute to our near-optimal performance guarantees—a substantial improvement over the state of the art, which often results in possibly vacuous regret bounds in many cases of theoretical and practical interest such as Matérn and Neural Tangent kernels. \n\n> Missing reference: “Neural Dueling Bandits. 2024”.\n\nThank you for mentioning this missing reference. We will include a review in the revision. They consider a wide neural network for target function prediction, in contrast to the kernel methods used in BOHF. However, their results are closely related, as a wide neural network can be approximated by the Neural Tangent Kernel as the layer widths grow. Beyond this modeling difference, their algorithm also differs from ours as well as from those of Pásztor et al., 2024 and Xu et al., 2024. Their method, referred to as Neural Dueling Bandit UCB (NDB-UCB), selects one action as the maximizer of the prediction and the other as the maximizer of the UCB. They also introduce a variant where the second action is selected via Thompson sampling instead of UCB. Their performance guarantees are expressed in terms of the effective dimension of the neural network model (see their equation (4)), which resembles the complexity term $\\Gamma(T)$ in BOHF. They assume that the effective dimension grows slower than $O(\\sqrt{T})$, which is a limitation, as otherwise their regret bounds become vacuous. Their regret bounds also scale with the curvature parameter $\\kappa$.\n\n*Verma, Arun, et al. \"Neural Dueling Bandits: Preference-Based Optimization with Human Feedback.\" The Thirteenth International Conference on Learning Representations, 2025.*\n\n---\nThank you again for your positive and constructive review. We are happy to answer any further questions during the rebuttal period.", "claims_and_evidence": "The paper claims that the proposed algorithm for BOHF can achieve a regret upper bound of $\\sqrt{\\Gamma(T)T}$, which is nearly optimal and matches the order of regret for scalar-valued feedback. These claims are supported by rigorous theoretical analysis, and the regret bound appears to be (nearly) tight. \nHowever, the experimental results show that the proposed method performs better only for very large horizons, which weakens the claim of practical superiority over existing methods like MaxMinLCB.", "methods_and_evaluation_criteria": "The methods are generally appropriate for the problem studies, as the paper effectively adapts previous techniques for batched Bayesian optimization to the preference feedback setting. However, there may be a practical limitation: the proposed algorithm does not utilize preference observations when selecting the queries within a batch, which could potentially improve performance. The method is evaluated based on regret from both selected arms, which is standard in the literature of dueling bandits and hence acceptable.", "theoretical_claims": "The most important strength of the paper is the theoretical results, since it provides a regret bound with the order of $\\sqrt{\\Gamma(T)T}$, which is near-optimal for the problem setting. I also appreciate the insights given in the theoretical analysis section (especially the one at bottom of page 6), which provides an explanation as to why the algorithm can achieve such a small regret. \nHowever, the technical novelty of the theoretical analysis is a concern. From a high level, the analysis techniques appear to a combination of those from existing works (Li & Scarlett, 2022; Pasztor et al., 2024; Xu et al., 2024). A clearer explanation of the technical challenges in the proof would enhance the contribution.", "experimental_designs_or_analyses": "The experimental results have a notable weakness: the proposed algorithm only outperforms the existing method of MaxMinLCB when the horizon is very large. This limits its practical applicability in scenarios with smaller observation budgets. So, the experiments do not convincingly demonstrate practical superiority across a range of settings.", "relation_to_broader_scientific_literature": "The paper builds on prior works in batched Bayesian optimization and dueling bandits (or preferential BO), particularly combining techniques from works such as Li & Scarlett, 2022, Pasztor et al., 2024, and Xu et al., 2024. The paper indeed makes an important theoretical contribution to the fields of Bayesian optimization and dueling bandits.", "essential_references_not_discussed": "The following is an importance missing reference: “Neural Dueling Bandits. 2024”. The paper uses neural networks to model the nonlinear function in dueling bandits and is hence highly related to the current paper.", "other_strengths_and_weaknesses": "Strengths:\n- The proposed algorithm achieves a near-optimal regret order, which is, to the best of my knowledge, the tightest regret bound for BOHF problems.\n\nWeaknesses:\n- The technical novelty is a concern, as the analysis seems to combine existing techniques without clearly discussing the technical challenges involved.\n- The proposed algorithm does not use the preference observations when selecting queries in a batch, which may limit its practical performance.\n- Experiments show poor performance for small horizons, which is a critical limitation for practical applications.", "other_comments_or_suggestions": "The paper would benefit from a clearer explanation of the technical challenges involved in the proof, as this would help establish the novelty of the theoretical contributions. Additionally, incorporating preference observations into the query selection process could potentially improve the algorithm's performance and address its main practical limitation (i.e., it may help the proposed algorithm perform better than MaxMinLCB even with small horizons).", "questions_for_authors": "- Could **the constants** in the regret bound for BOHF be worse than those for scalar-valued feedback? Intuitively, weaker feedback should degrade performance. Clarifying this could provide a more complete picture of the theoretical guarantees.\n- The proposed algorithm does not make use of the preference observations when selecting queries within a batch? In practice, incorporating these observations should lead to better performance. Could the algorithm be extended to account for them?\n- What are the technical challenges in the proof that distinguish this work from prior analyses (e.g., Li & Scarlett, 2022; Pasztor et al., 2024; Xu et al., 2024)? A clear explanation of these challenges would help establish the paper's novelty.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fef11jR5JG", "reviewer": "Reviewer_FPrS", "summary": "This paper studies the kernel-based decision making problems under preferential feedbacks. The author proposed the phased-elimination style algorithm (which is refered to as MR-LPF in the paper) for this problem, which leads to $O(\\sqrt{T \\gamma_T})$ cumulative regret, while the existing algorithm suffers from additional polynomial dependence of $T$ and the complexity term arising from the non-linearity of the link function.  The author also conducted a numerical experiment in a real-world motivated problem, although the baseline method is limited to the existing UCB-based algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback and careful review of the technical material, which is truly invaluable for us. Below, we address your comments and questions, which we hope will enhance your evaluation of the paper.\n\n> Interpretation of the lower bound of Scarlett et al., 2017 provided for standard BO with scalar feedback.\n\nWe appreciate your raising this subtle point. Here we provide a technical clarification on our result and the mentioned lower bound.\n\nConsider a standard BO setting with noisy scalar observations $o = f(x) + \\varepsilon$ (using the notation at the beginning of Section 2.3), where noise terms $\\varepsilon$ are zero-mean, independent, and identically distributed across samples. Suppose at each step we select two points $x_t$ and $x'_t$, but instead of observing scalar feedback $o_t$ and $o'_t$ (with $o_t=f(x_t)+\\varepsilon_t$ and $o'_t=f(x'_t)+\\varepsilon'_t$), we receive preference feedback as a Bernoulli random variable $y_t = I(o_t > o'_t)$. Under the Bradley–Terry–Luce model, this preference feedback corresponds exactly to the case where the noise difference $\\varepsilon'_t - \\varepsilon_t$ follows a logistic distribution, whose CDF is the sigmoid function: $P(\\varepsilon'_t - \\varepsilon_t < f(x)-f(x')) = \\mu(f(x)-f(x'))$.\nTo have this satisfied, the individual noise terms $\\varepsilon_t$ can be Gumbel-distributed.\n\nThus, the lower bound on regret in our BOHF setting should be at least twice the lower bound for standard BO with scalar observations under Gumbel noise. In our revision, we will explicitly state this as a lemma and provide all the details.\n\nWe acknowledge your remark that Scarlett et al. (2017) specifically use Gaussian noise in their lower bound example construction. However, it is standard practice in the BO literature to compare regret bounds under general sub-Gaussian noise (including bounded noise) with the lower bound result from Scarlett et al. (2017); see, for example, Salgia et al., 2021 and Li & Scarlett, 2022 among many others. \n\nFollowing your comment, we will explicitly state this result as a lemma in Section 4 and clarify the noise distribution assumption from Scarlett et al. (2017) in the revision. We are happy to discuss this further or answer any additional questions.\n\n> Novelty:\n\nWe agree with the reviewer’s understanding of our theoretical results. Within the multi-round structure of our algorithm, we carefully characterize the impact of curvature and successfully remove the dependency on $\\kappa$. Moreover, we leverage Theorem 4.7 to further improve regret with respect to $T$. These algorithmic and analytical contributions result in regret bounds of the same order as standard BO, providing a substantial improvement over existing methods, whose bounds can become vacuous for many kernels of theoretical and practical importance.\n\nWe support these results through synthetic experiments on RKHS functions, which closely align with our theoretical assumptions and corroborate our analytical results. Additionally, we show the utility of our algorithm using a real-world Yelp dataset, highlighting that we have introduced a practical algorithm accompanied by strong theoretical guarantees.\n\n> Other Comments Or Suggestions:\n\n*The average regrets at the initial step (t = 0) are different:* This is due to arbitrary implementation choices which does not have a significant effect on eventual performance seen in the figures. We will fix this in the revision. \n\n*Why the maximum information gain of the kernel Eq. (4) increases at the same rate as the kernel?* In Proposition 4 of Pásztor et al. (2024), it is shown (see their Appendix C.1) that the eigenvalues of the dueling kernel $\\mathbb{k}$ are exactly twice those of the original kernel $k$. Since the maximum information gain scales with the decay rate of the kernel eigenvalues (Vakili et al., 2021b, Corollary 1), both kernels exhibit the same scaling of the information gain. This property was also implicitly used in Pásztor et al. (2024). Following your comment, we will make this point explicit and clear. \n\nWe fixed the typos mentioned by the reviewer. Thanks. \n\n---\nWe again thank you for your invaluable technical comments, which significantly enhance the presentation of the work. We hope addressing your comments improves your evaluation of the paper and remain available for further discussion.", "claims_and_evidence": "The author claimed contributions of this paper are well supported by theoretical perspective, and I could not find any issues as far as I checked.", "methods_and_evaluation_criteria": "The author's proposed method can be interpreted as preferential variants of the existing phased-elimination or batched pure exploration-based approach. It makes sense to propose such a method to achieve better theoretical performance.", "theoretical_claims": "I checked all the theoretical claims except for the proof of Theorem 4.7 (Appendix C). The proof is based on the standard techniques of GP-bandits, and I could not find any questionable point regarding the correctness of the theoretical claims. On the other hand, one of my concerns is whether the algorithm's near optimality, which the author appeals to in the paper, is rigorously verified. The existing Scarlett's lower bound is given for the Gaussian reward, and its connection with the preferential feedback model, whose feedbacks are given based on the comparison of chosen pairs of query points and the realization of Bernoulli distribution, is not straightforward for me. \nIn my intuition, the near-optimality of $O(\\sqrt{\\gamma_T T})$ in this paper's setup is true (may be rigorously proved by modifying the KL divergence of the Gaussian in Scarlett's proof); however, I believe more careful arguments should be added to the revision if the author claims the optimality. If not, the presentation (including title) of this paper should be modified by mildening the claim relating to near-optimality.", "experimental_designs_or_analyses": "We only check the description of experimental sections in the main paper. The synthetic experiments conducted in this paper are a standard setup for the kernel bandit or Bayesian optimization field, and we did not find any issue in the setup. One concern is that the average regrets at the initial step (t = 0) are different. To make the fair comparison, I believe that the initial points of the experiments should be the same in this setup.", "relation_to_broader_scientific_literature": "This paper's results show improved results of the existing theoretical guarantees of kernel-based dueling bandits.", "essential_references_not_discussed": "To my knowledge, the existing results relating to this paper are well discussed in Section 1.1.", "other_strengths_and_weaknesses": "My main concern about this paper's weakness is the novelty. The algorithm construction itself seems to be the naive extension of the standard phased elimination. As far as I see the proof, the difference between the existing phased elimination is as follows:\n\n1. To keep $k_\\tau$ small, the learner has to allocate enough samples for the initial phase (the proof from Line 690).\n2. The non-adaptive confidence bound for preferential feedback (Theorem 4.7).\n\nI did not check the details of the point 2 so far; however, this part seems non-trivial as far as my knowledge, and does not follow directly from existing literature's technique. Therefore, my current score is leaning toward acceptance.", "other_comments_or_suggestions": "- Line 646: (x - x')^2 -> |x - x'|^2\n- Eq. (18): the second x_t should be modified to x_t'\n- The definition of R (e.g., Theorem 4.1, Line 782): log log (T) -> log_2 log_2 (T)\n- Line 817: O(log^d T) -> O(log^{d+1} T) (see, Vakilli's paper).\n- The arguments, why the maximum information gain of the kernel Eq. (4) increases at the same rate as the kernel $k$, should be added for the reader who is not familiar with this field. I did not find any arguments in existing papers, including the existing Pásztor's paper.", "questions_for_authors": "Please see \"Theoretical Claims\" section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers are in agreement that this paper makes a valuable contribution to the area of kernel bandits with preferential feedback.  In particular, a near-optimal regret bound is given via a batched algorithm, which is in analogy with the regular feedback setting but by no means a trivial extension.  I pointed out some technical concerns but they were ultimately minor, and no major concerns remain.  Please carefully incorporate the reviewer comments (and my comments) into the final version.
Decision: Accept (poster)