Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds

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.

Interpretation of the lower bound of Scarlett et al., 2017 provided for standard BO with scalar feedback.

We appreciate your raising this subtle point. Here we provide a technical clarification on our result and the mentioned lower bound.

Consider 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'))$. To have this satisfied, the individual noise terms $\varepsilon_t$ can be Gumbel-distributed.

Thus, 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.

We 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.

Following 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.

Novelty:

We 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.

We 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.

Other Comments Or Suggestions:

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.

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.

We fixed the typos mentioned by the reviewer. Thanks.

We 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.

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.

Could the constants in the regret bound for BOHF be worse than those for scalar-valued feedback?

We 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.

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?

The 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.

Empirically, 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.

Technical challenges:

Although 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$.

Together, 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.

Missing reference: “Neural Dueling Bandits. 2024”.

Thank 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$.

Verma, Arun, et al. "Neural Dueling Bandits: Preference-Based Optimization with Human Feedback." The Thirteenth International Conference on Learning Representations, 2025.

Thank you again for your positive and constructive review. We are happy to answer any further questions during the rebuttal period.

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.

Comparison with POP-BO (Xu et al., 2024)
Question 1: Why was POP-BO (Xu et al., 2024) not included as a baseline in the empirical evaluation?

Theoretically, 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.

Empirically, 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.

While the experiments show MR-LPF performing better than MaxMinLCB, the improvement is often not dramatic.

We 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. Nonetheless, 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.

The 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.

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.

We 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.

Our 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.

Question 2. Could you clarify the derivation of the inequality in Equation (42) within the proof of Lemma C.1?

The 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.

Thank you again for your positive and constructive review, which helps clarify and improve the presentation of the paper.

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.

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?

The 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.

For Ackley and Yelp data, do they satisfy the RKHS assumption?

The 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.

We 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.

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.
Is there any difference between the proposed algorithm with the ones from the literature?

The 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.

To 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$.

While 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.

The experimental evaluation where only one comparative method (MaxMinLCB) is given.

We 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.

Our goal is to demonstrate that our algorithm not only significantly improves theoretical guarantees but also performs well empirically.

We 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.