Bandits with Preference Feedback: A Stackelberg Game Perspective

Thank you for your time and the points you raised. We addressed them in the paper and we believe it will help the paper to reach a broader community. Follows our response to your questions.

The major concern is the practical applicability of the algorithm. Seems that the proposed algorithm can hardly scale up to a higher dimension (e.g., dimension equals to 7). In the proposed algorithm, a complicated sequential optimization problem needs to be solved. Notably, the experiment only considers two-dimensional problem, in sharp contrast to recent works (e.g., 12-dimensional problem considered in Xu et al. [2024]).

We acknowledge that scalability is a crucial point for practicability. Bilevel optimization problems are known to be hard, however, due to their common large-scale applications (e.g. for data re-weighting in tuning LLMs[4]), there are efficient approximation algorithms. This is mentioned in Line 275, and given the technical tools for vectorizing, parallelizing, and utilizing multiple machines, we do not consider this to be a major concern for applicability.

To address your concern, we are adding an experiment on a 32-dimensional problem using restaurant reviews from the Yelp open dataset. We believe this further demonstrates the scalability of our approach. For further discussion, please see our general rebuttal and the uploaded PDF that contains its cumulative regret plot [Fig A-b], as a proof-of-concept. We highlight that we have not tuned or modified the algorithms for this experiment, and they are being used off-the-shelf. The regret curve is best viewed as a proof-of-concept, rather than an algorithmic benchmark.

In the abstract, the review claims that the regret bound is 'rate-optimal'. Is there a matching lower bound?

Thank you for raising this question. We realize that this claim is not accurate enough, and we have now updated the abstract.

There are no lower bounds, for dueling bandits or bandits with direct feedback, under the RKHS assumption. This has been an open problem [1] and is only resolved under a GP assumption [2] or for time-continuous bandits [3]. These papers hint that the existing upper bounds are not improvable.

Our regret rates in $T$, match the tightest existing upper bounds for cumulative regret in kernelized bandits, that is, $\tilde{\mathcal{O}}(\gamma_T \sqrt{T})$, up to the choice of kernel. We updated the abstract and specifically removed the word “rate-optimal” to avoid confusion. We have also included this remark about the rates, updating the paragraph on Lines 309-313.

Can the results be generalized to other link functions?

Our theoretical analysis does in fact hold under a broader set of link functions $s: \mathbb{R} \to [0, 1]$ as long as $s$ is,

• monotonically increasing and symmetric around $0$, i.e., $s(x) = 1-s(-x)$ and $s(0) = 0.5$,
• differentiable and $\kappa = \sup_{a \leq B} 1/\dot{s}(a)$ exists. We have kept the problem setting for the sigmoid function, as it has a simple probabilistic interpretation (feedback $y$ becomes a Bernoulli random variable) and connects to the common Bradly-Terry model.

However, we have added a remark to Section 3 and pointed out this extension.

In line 168, should it be $sup_{|a| \leq B}$ instead of $sup_{a \leq B}$?

The sigmoid function is symmetric therefore the two supremum are equivalent.

Could the authors explain the linear growth of multiSBM in Fig. 1 (b)?

Thank you for raising this point. The linear regret of MultiSBM was a result of a minor error in our implementation. We corrected it and updated our results. Fig A and Table B in the uploaded PDF include the corrected performance of MultiSBM. Due to the single-page limit of the PDF, we included only the Ackley function's cumulative regret plot but have updated all figures in the paper. MultiSBM is now a competitor to MaxMinLCB for smooth functions (e.g. Branin and Matyas), however, for the more challenging problems (e.g. Ackley and Eggholder) our algorithm maintains its performance advantage. MaxMinLCB remains the top-performing algorithm across the problem instances.

The paper discusses the comparisons to [Xu et al. 2024]. Seems that the theoretical gain of $T^{\frac{1}{4}}$ mainly comes from tighter confidence set rather than the design of the algorithm. If the algorithm POP-BO in [Xu et al. 2024] is equipped with this tighter confidence set, it could also achieve the same regret bound. To see which algorithm is empirically better, it would be interesting to compare the proposed algorithm with POP-BO equipped with the tighter confidence set in this paper.

The POP-BO algorithm is built on the same logic as the MultiSBM that we included in our experimental results. We have updated the paper specifying this connection. MultiSBM (POP-BO) performs competitively on smooth and simpler reward functions, however, our algorithm maintains its performance advantage on the more challenging functions and the Yelp experiment. We kindly refer the reviewer to the general rebuttal for a further discussion on the similarities between MultiSBM, POP-BO, and MaxMinLCB.

References:

[1] Vakili, Sattar, Jonathan Scarlett, and Tara Javidi. "Open problem: Tight online confidence intervals for RKHS elements." Conference on Learning Theory. PMLR, 2021.

[2] Scarlett, Jonathan, Ilija Bogunovic, and Volkan Cevher. "Lower bounds on regret for noisy gaussian process bandit optimization." Conference on Learning Theory. PMLR, 2017.

[3] Lattimore, Tor. "A lower bound for linear and kernel regression with adaptive covariates." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

[4] Pan, Rui, et al. "ScaleBiO: Scalable Bilevel Optimization for LLM Data Reweighting." arXiv preprint arXiv:2406.19976 (2024).

I would like to thank the authors for the detailed responses. Most of my concerns are addressed. And I would like to maintain my rating.

Thank you for your time and comments. We are glad that you find our contributions to be timely and strong. We have reflected your suggestions in the paper, making it more clear for future readers.

In practice, how to determine the hyper-parameters like 𝛾𝑡, 𝐿, and 𝐵 in (5)? Is there any data-driven way to select them?

There are two common ways:

• If there's enough budget for data acquisition, these can be selected via cross-validation on a small sampled pool.
• Another approach is to create a second bandit instance on top, to optimize for these parameters [1, 2].

In practice, we directly tune for $\beta\_t$, rather than separately for its elements (e.g. no need to tune $\gamma\_t$). In our experiments, we just set $\beta\_t = 1.0$ without tuning it.

In the main Theorem 6, the regret bound is $\gamma_T\sqrt{T}$. The term $\gamma_T$ is the T-step information gain of kernel, which is also a function of 𝑇. The authors claim that this rate improves that of Xu et al. (2024) by a factor of 𝑇1/4. However, the cumulative regret bound in Theorem 5.2 of Xu et al. (2024) is of a similar order. Xu et al. (2024) also provided explicit regret upper bounds for various common kernels in Theorem 5.5. Hence, it is also interesting to provide an explicit form of $\gamma_T^{(D)}$ for some common kernels, and to compare these regret upper bounds in a fair way.

On the regret rate. Please note that the definition of $\beta_T$ in [Xu et al.] is looser by a factor of $T^{1/4}$ than ours. In Theorem 5.2, the regret bound is: $\sqrt{\beta_T} \sqrt{T} = T^{3/4}\gamma_T$ This looseness by a factor of $T^{1/4}$ can also be viewed in Theorem 5.5, where the regret of a linear bandit is reported to be $O(T^{3/4})$.

Regarding the dueling information gain. Our regret bounds are indeed in terms of $\gamma_T^{(D)}$ and Xu et al. presents their result for $\gamma_T$. We have now updated the text, refraining from directly comparing the tightness of rates, for the comparison to be more rigorous. However, we expect $\gamma_T^{(D)}$ and $\gamma_T$ to exhibit identical rates with $T$ which is the case for linear kernels. We are working on extending this result to more complex kernels. Our intuition is that summing two kernels (to create the dueling kernel) does not change the kernel complexity. Thank you for this suggestion!

In Figure 1, the authors presented the result for the Ackley function, which shows a clear advantage of the proposed method. However, in more extensive simulations (e.g., Matyas function in Figure 6, ) in the appendix, the proposed method is outperformed by the competitors. It is helpful to provide some discussion on these results, and offer some insights on when the proposed method would work well. This is helpful for practitioners.

We appreciate the observations and agree that a discussion on these results is beneficial for practitioners. Overall, we see MaxMinLCB as a robust choice demonstrated by its consistent performance across the wide range of optimization problems considered in our experimental results.

Branin, Matyas, and Rosenbrock are relatively smooth functions that present easier optimization problems. We observe less differentiated performance between the algorithms. For example, MultiSBM excels and outperforms MaxMinLCB for Branin and Matyas.

In contrast, functions such as Ackley, Eggholder, Hoelder, and Michalewicz present more challenging optimization problems characterized by larger gradients, valleys, ridges, and numerous local optima. In these cases, MaxMinLCB demonstrates a clear advantage.

Figure C in the uploaded PDF visualizes the Ackley, Matyas, and Branin functions to highlight these differences.

We will include a detailed discussion in the revised manuscript to provide practitioners with insights into when the proposed method is most effective and how it compares to other algorithms under various conditions.

References

[1] Berkenkamp, Felix, Angela P. Schoellig, and Andreas Krause. "No-regret Bayesian optimization with unknown hyperparameters." Journal of Machine Learning Research 20.50 (2019): 1-24. [2] Sessa, Pier Giuseppe, et al. "Multitask learning with no regret: from improved confidence bounds to active learning." Advances in Neural Information Processing Systems 36 (2023): 6770-6781.

Thank you for your time and the points you raised. We addressed them in the paper and we believe it will help the paper to reach a broader community. In light of these updates, we appreciate if you can reconsider your assessment on the scope and relevance of the paper.

Although the paper uses a kernelized logistic model to approximate the rewards, this approach may remain too simplistic for capturing the complexity of rewards in real-world applications.

We would first like to highlight that the MaxMinLCB acquisition function is not tied to the kernelized model in this paper and may be used together with any calibrated model, e.g. a Bayesian Neural Network with valid uncertainty estimates.

We believe that a kernelized approach for adaptive learning is still relevant in real-world problems, e.g. if vector embeddings of the data are available. For complex data modalities, finding an accurate feature map is beyond the computational budget of many practitioners, and we believe there is value in developing computationally light methodology which can be set up on top of available vector embeddings. It is in fact common to use kernelized and linear models on top of LLM embeddings in Active Preference Optimization [3, 4].

We are conducting a new experiment to demonstrate this claim given vector embeddings of Yelp reviews for restaurants [Fig. A Tab. B- Uploaded PDF]. We can find the preferred choices, based on comparative feedback of a user and observe that the algorithm still works on a text-based domain, even though it is designed for euclidean spaces. Please refer to the general response for details of this experiment. Note that neither of the algorithms have been modified or tuned to this new domain, therefore the regret act as a proof-of-concept, rather than a benchmark.

While the key contributions of this paper are intended to be primarily theoretical, we aim to add this experiment to demonstrate the practical applicability of our problem setting. We hope that this experiment can make the paper more accessible to a broader community.

Can this work be extended to contextual bandits with preference feedback? The paper does not consider contextual information and solely focuses on the multi-armed setting, which is less interesting and useful.

Thank you for the interesting question! We have been thinking about contextual extensions as future work. Here’s our take:

1. If the context is stochastic and given by the environment, our approach almost immediately applies.

   Contextual bandits and linear/kernelized bandits are equivalent up to choice of the feature map/kernel. This is extensively discussed in Chapter 19.1 and 19.2 of the bandit book [1] for the linear setting, and analyzed in [2] for the kernelized setting. We updated section 3 and added this remark.

2. If the context can be actively chosen by the agent (e.g. choosing a prompt from a fine-tuning dataset), we require a non-trivial extension of our algorithm.

   This is an interesting scenario, in which the agent is optimizing both for the context and action pairs. We are in fact working on a follow-up project, which uses our novel MaxMinLCB acquisition function to solve this problem, with an eye to active preference optimization [3, 4]. Here, the aim is to give a worst-case sample complexity bound. We now mention this in the Conclusion section.

The paper lacks a comparison in the experiments with the related work by Xu et al. (2024).

We would like to highlight that the POP-BO algorithm proposed by Xu et al. (2024) uses the same action selection logic as the MultiSBM algorithm, which is already included in our benchmarks. We have updated section 6, specifying this connection. Our experimental results indicate that MultiSBM performs comparably or even slightly better than MaxMinLCB on smooth functions. However, MaxMinLCB outperforms MultiSBM on more challenging functions such as Ackley and Eggholder. Figure A and Table B in the uploaded PDF compare performance on smooth and wilder functions.

Can you implement the algorithms compared in Section 6.2 using the original confidence sets from the references?

Most baselines are designed for linear settings, which is misspecified for the complex test functions that we consider [c.f. Fig. C in the rebuttal PDF]. This would result in linear regret curves [c.f. Fig. 1a of the paper]. Therefore, we implemented the baselines using our improved confidence sets to make the regret curves more informative. This allows the reader to compare the acquisition functions more fairly.

The IDS algorithm and POP-BO have kernelized confidence sets but are (theoretically) expected to be looser [c.f. Fig. 1a of the paper]. We will update the paper with a comparison to these algorithms (using their original confidence sets). Thank you for this suggestion!

References:

[1] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.

[2] Krause, Andreas, and Cheng Ong. "Contextual gaussian process bandit optimization." Advances in neural information processing systems 24 (2011).

[3] Das, Nirjhar, et al. "Active Preference Optimization for Sample Efficient RLHF." ICML 2024 Workshop on Theoretical Foundations of Foundation Models.

[4] Mehta, V., Das, V., Neopane, O., Dai, Y., Bogunovic, I., Schneider, J., & Neiswanger, W. (2023). Sample Efficient Reinforcement Learning from Human Feedback via Active Exploration.]

Thank you for the valuable review and constructive suggestions. Please find below our comments on the raised questions.

Experimental evaluation can include other algorithms that are known to perform better than RUCB such as RMED (Komiyama et al., 2015) and Double Thompson Sampling (Wu and Liu, 2016).

We appreciate the recommendation and acknowledge that RMED and Double Thompson Sampling (D-TS) perform better than some of our benchmark algorithms on the finite arm dueling bandit problem. However, our paper focuses on the continuous domain, making these algorithms less comparable for our study. We have added the references to the related works section.

In our experimental setup, we intentionally separated the confidence set estimation and action selection to evaluate these problems independently. Although many of the action selection algorithms we used are designed for the finite arm problem, they can be adapted to the continuous domain with minor modifications, as detailed in appendix D and E. In contrast, for RMED and D-TS we have not found straightforward extensions to the continuous domain. For instance, D-TS depends on counting the number of times arm $i$ beats arm $j$, which is challenging to interpret in a continuous setting. Nonetheless, we are keen to hear if you have a suggestion on how to incorporate these algorithms into our comparisons.

It would be interesting to see if the current approach can be extended to other link functions beyond the sigmoid such as probit.

Thank you for this suggestion! Our theoretical analysis does in fact hold under a broader set of link functions $s: \mathbb{R} \to [0, 1]$ as long as $s$ is,

• monotonically increasing and symmetric around $0$, i.e., $s(x) = 1-s(-x)$ and $s(0) = 0.5$,
• differentiable and $\kappa = \sup_{a \leq B} 1/\dot{s}(a)$ exists. We have kept the problem setting for the sigmoid function, as it has a simple probabilistic interpretation (feedback $y$ becomes a Bernoulli random variable) and connects to the common Bradly-Terry model.

However, we have added a remark to Section 3 and pointed out this extension.