Bandits with Preference Feedback: A Stackelberg Game Perspective
Authors: Barna Pásztor
Parnian Kassraie
Andreas Krause
Venue: NeurIPS 2024 poster (2024)
Keywords: Preference Feedback
Duelling Bandits
Reproducing Kernel Hilbert Space
Stackelberg Games
Exploration-exploitation dilemma
Primary area: bandits

Abstract: Bandits with preference feedback present a powerful tool for optimizing unknown target functions when only pairwise comparisons are allowed instead of direct value queries. This model allows for incorporating human feedback into online inference and optimization and has been employed in systems for tuning large language models.
The problem is fairly understood in toy settings with linear target functions or over finite small domains that limits practical interest.
Taking the next step, we consider infinite domains and kernelized rewards. In this setting, selecting a pair of actions is quite challenging and requires balancing exploration and exploitation at two levels: within the pair, and along the iterations of the algorithm.
We propose MaxMinLCB, which emulates this trade-off as a zero-sum Stackelberg game and chooses action pairs that are informative and have favorable reward values. MaxMinLCB consistently outperforms algorithms in the literature and satisfies an anytime-valid rate-optimal regret guarantee. This is owed to our novel preference-based confidence sequences for kernelized logistic estimators, which are of independent interest.

Bandits with Preference Feedback: A Stackelberg Game Perspective
Barna Pásztor* *.12
Parnian Kassraie Andreas Krause 1.2
'ETH Zurich "ETH AI Center (bpasztor, pkassraie, krrassa))eeth..ch
Abstract
Bandits with preference feedback present powerful tool for optimizing unknown target functions when only pairwise comparisons are allowed instead of direct value queries. This model allows for incorporating human feedback into online inference and optimization and has been employed in systems for fine-tuning large language models. The problem is well understood in simplified settings with linear target functions or over finite small domains that limit practical interest. Taking the next step, we consider infinite domains and nonlinear (kernelizee) rewards. this setting, selecting a pair of actions is quite challenging and requires balancing exploration and exploitation at levels: within the pair, and along the iterations of the algorithm. We propose MAXMINLCB, which emulates this trade-off as a zero-sum Stackelberg game, and chooses action pairs that are informative and yield favorable rewards. MAXMINLCB consistently outperforms existing algorithms and satisfies an anytime-vale valid rate-optimal regret guarantee. This is due to our novel preference-basee confidence sequences for kernelized logistic estimators.
Introduction
In standard bandit optimization, a learner repeatedly interacts with an unknown environment that gives numerical feedback on the chosen actions according to a utility function f. However, in applications such as fine-tuning large language models, drug testing, or search engine optimization, the quantitative value of design choices or test outcomes are either not directly observable, or known to be inaccurate, or systematically biased, e.g., if they are provided by human feedback [Casper et al., 2023]. solution optimize for the target based on comparative feedback provided for a pair of queries, which is proven to be more robust to certain biases and uncertainties in the queries [Ji et al., 2023].
Bandits with preference feedback, or dueling bandits, address this problem and propose strategies for choosing query/action pairs that yield high utility over the horizon of interactions. At the core of such algorithms uncertainty quantification and inference for f in regions of interest, which is closely tied to exploration and exploitation dilemma over course of queries. Observing only comparative feedback poses an additional challenge, as we now need to balance this trade-off jointly over two actions. This challenge is further exacerbated when optimizing over vast infinite action domains. As remedy, prior work often grounds one the actions by choosing it either randomly greedily, and tries to balance first [Ailon et al., 2014, Zoghi et al., 2014a, Kirschner and Krause, 2021, Mchta et al., 2023b]. This approach works well for simple utility functions over low-dimensional domains, however does not scale to more complex problems.
for the second action as reaction to the
Aiming solve this problem, focus continuous domains in the Euclidean vector space and complex utility functions that belong to the Reproducing Kernel Hilbert Space (RKHS) of a poten- tially non-smooth kernel. We propose MAXMINLCB,, sample-efficient algorithm that every step chooses the actions jointly, by playing a zero-sum Stackelberg (a.k.a (older-Flllowe) game. We choose the Lower Confidence Bound (LCB) of the objective of this game which the Leader aims
"Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

to maximize and the Follower to minimize. The equilibrium of this game yields an action pair in which the first action is favorable candidate to maximize f and the second action the strongest competitor against the first. Our choice of using the LCB as the objective leads to robustness against uncertainty when selecting the first action. Moreover, it makes the second action an optimistic choice as a competi- tor, from its own perspective. We observe empirically that this approach creates a natural exploration scheme, and in turn, yields a more sample-efficient algorithm compared to standard baselines.
Our game-theoretic strategy leads to an efficient bandit solver, if the I.CB is a valid and tight lower bound on the utility function. To this end, we construct a confidence sequence for f given pairwise preference feedback, by modeling the noisy comparative observations with logistic-type likelihood function. Our confidence sequence is anytime valid and holds uniformly over the domain, under the assumption that f resides in RKHS. We improve prior work by removing relaxing assumptions on the utility while maintaining the same rate of convergence. This result on preference- based confidence sequences may be of independent interest, as it targets the loss function that is typically used for Reinforcement Learning with Human Feedback.
Contributions Our main contributions are:
We propose a novel game-theoretic acquisition function for pairwise action selection with preference feedback.
We construct preference- -based confidence sequences for kernelized utility functions that are tight and anytime valid.
Together this creates MAXMINLCB, an algorithm for bandit optimization with preference feedback over continuous domains. MAXMINI LCB satisfies ((7r regret, where 7 is the horizon and "/r is the information gain of the kernel.
We benchmark MAXMINI over a set of standard optimization problems and consistently outperform the common baselines from the literature.
2 Related Work
Learning with indirect feedback was first studied in the supervised preference learning setting [Aiolli and Sperduti, 2004, Chu and Ghahramani, 2005]. Subsequently, online and sequential settings were considered, motivated by applications in which the feedback is provided in an online manner, e.g.. by a human [Yue et al., 2012, Yue and Joachims, 2009, Houlsby et al., 201 IJ. Bengs et al. [2021] surveys this field comprehensively; here we include brief background.
Referred to as dueling bandits, a rich body of work considers (finite) multi-armed domains and learns preference matrix specifying the relation among the arms Such work often relies on efficient sorting or tournament systems based on the frequency of wins for each action [Jamieson and Nowak, 2011, Zoghi et al., 2014b, Komiyama et al., 2015, Wu and Liu, 2016, Falahatgar et al., 2017]. Rather than jointly selecting the arms, such strategies often simplify the problem by selecting one at random [Zoghi et al., 2014a, Zimmert and Seldin, 2018], greedily [Chen and Frazier, 2017], or from the set of previously selected arms [Ailon et al., 2014]. In contrast, we jointly optimize both actions by choosing them as the equilibrium of two-player zero-sum Stackelberg game, enabling a more efficient exploration/exploitaiii trade-off.
The multi-armed dueling setting, which is reducible to multi-armed bandits [Ailon et al., 2014], naturally fails to scale to infinite compact domains, since regularity among "similar" arms is not exploited. To go beyond finite domains, utility-based dueling bandits consider unknown latent function that captures the underlying preference, instead of relying on a preference matrix. The pref- erence feedback is then modeled as the difference in the utility of two chosen actions passed through a link function. Early work is limited to convex domains and imposes strong regularity assumptions [Yue and Joachims, 2009, Kumagai, 2017]. These assumptions are then relaxed to general compact domains if the utility function is linear [Dudík et al., 2015, Saha, 2021, Saha and Krishnamurthy, 2022]. Constructing valid confidence sets from comparative feedback is a challenging task. However, it is strongly related to uncertainty quantification with direct logistic feedback, which is extensively analyzed by the literature on logistic and generalized linear bandits [Filippi et al., 2010, Faury et al., 2020, Foster and Krishnamurthy, 2018, Beygelzimer et al., 2019, Faury et al., 2022, Lee et al., 2024].
Preference-basee bandit optimization with linear utility functions is well understood and is even extended to reinforcement learning with preference feedback on trajectories [Saha et al., 2023, Zhan et al., 2023, Zhu et al., 2023, Ji et al., 2023, Munos et al., 2023]. However, such approaches have limited practical interest, since they cannot capture real-world problems with complex nonlinear

---

utility functions. Alternatielly, Reproducing Kernel Hilbert Spaces (RKHS) provide rich model class for the utiliiyy, e.g., if the chosen kernel universal. Many have proposed heuristic algorithms for bandits and Bayesian optimization in kernelized settings, albeit without providing theoretical guarantees Brochu et al. [2010], González et al. [2017], Sui et al. [2017], Tucker et al. [2020], Mikkola et al. [2020], Takeno et al. [2023].
There have been attempts to prove convergence of kernelized algorithms for preference-based bandits [Xu et al., 2020, Kirschner and Krause, 2021, Mehta et al., 2023b,a]. Such works employ a regression likelihood model which requires them to assume that both the utility and the probability of preference, as a function of actions, lie in an RKHS. In doing so, they use regression model for solving a problem that is inherently a classification. While the model is valid, it does not result in sample-efficient algorithm. In contrast, use a kernelized logistic negative log-likelihood loss to infer the utility function, and provide confidence sets for its minimizer. In a concurrent work, Xu et al. [2024] also consider the kemeliied logistic likelihood model and propose variant of the MULTISBM algorithm [Ailon et al., 2014] which uses likelihood ratio confidence sets. The theoretical approach and resulting algorithm bear significant differences, and the regret guarantee has strictly worse dependency on the time horizon T, by factor of 7//4, This is discussed in more detail in Section 5.
3 Problem Setting
Consider an agent which repeatedly interacts with environment: at step t the agent selects two actions Vt. xy E X' and only observes stochastic binary feedback yt E {0, 1 indicating if æ; > xy, that is, if action De is preferred over action z/. Formally, P(y P(x; > zf). and y = 0 with probability 1 - P(#; > æ²). Based on the preference history H2 = 2 2/,1), ...... (are, x,,, ve)), the agent aims to sequentially select favorable action pairs.
1/ æ!)
Over a horizon of T steps, the success of the agent is measured through the cumulative dueling regret
T R (T(T)) = Σ
P( > xx) + P(#" x²))
2
which is the average sub-optimality gap between the chosen pair and globally preferred action xt. To better understand this notion of regret, consider the scenario where actions x, and af are both optimal. Then the probabilities are equal to 0.5 and the ducling regret will not grow further, since the regret incurred at step t is zero. This formulation of (T) is commonly used in the literature of dueling Bandits and RL with preference feedback [Urvoy et al., 2013, Saha et al., 2023, Zhu et al., 2023] and is adapted from Yue et al. [2012]. Our goal is to design an algorithm that satisfies a sublinear dueling regret, where RD + 0 as T - co. This implies that given enough evidence, the algorithm will converge to a globally preferred action. To this end, we take a muility-based approach and consider an unknown utility function f : X + R. which reflects the preference via
P(x; > x = s (f( - f(x)))
(2)
where R - [0,1] is the sigmoid function', i.c. s(a) = (1 + Referred to as the Bradley-Terry model [Bradley and Terry, 1952], this probabilistic model for binary feedback is widely used in the literature for logistic and generalized bandits [Filippi et al., 2010, Faury et al., 2020]. Under the utility- based model, x= = arg max,ex fxx and we can draw connections to a classic bandit problem with direct feedback over the utility f. In particular, Saha [2021] shows that the dueling regret of (1) is equivalent up to constant factors, to the average utility regret of the two actions, that is Ein (())) - [f(x)) + f=1)1/2.
Throughout this paper, we make two key assumptions over the environment. We assume that the domain X c. iRdo is compact, and that the utility function lies in Hy. a Reproducing Kernel Hilbert Space corresponding to some kernel function E X' x X -> R with a bounded RKHS norm Ilf < B. Without a loss of generality. we further suppose that the kernel function is normalized and k(x,, .x) < 1 everywhere in the domain. Our set of assumptions extends the prior literature on logistic bandits and dueling bandits from linear rewards or finite action spaces, to continuous domains with non- manpaarmetrrc rewards.
While our theoretical framework targets euclidean domains, our methodology may be used on general domains of text or images, given vector embeddings obtained via unsupervised learning. Solving a bandit problem on top of embeddings from pretrained language model is common practice in
May be generalized to differentiable monotonically increasing functions satisfying s(x) s(-2) = 1.
3

---

further fine-tuning of such models [e.g., Nguyen et al., 2024, Mehta et al., 2023a], and is further demonstrated in our Yelp experiment (c.f Section 6.3). Lastly, we highlight that our results may be smoothly extended to contextual bandits with stochastic context, by simply modifying the signature of the kernel function to k (ax, x', 2) X' x X x 2 - R, where E 2 denotes the context. This setting accommodates applications in active learning for fine-tuning of large language models, where the context the prompt and the two actions are two alternative responses.
Kernelized Confidence Sequences with Direct Logistic Feedback
As a warm-up, we consider a hypothetical scenario where a Tnull for all 2 such that [( 0. Therefore at every step, we suggest an action z; and receive noisy binary feedback yt. which is equal to one with probability (x))) This example reduces our problem to logistic bandits which has been rigorously analyzed for linear rewards [Filippi et al., 2010, Faury et al., 2020J. We extend prior work to the non-parametric setting by proposing a tractable loss function for estimating the utility function, a.k.a. reward. We present novel confidence intervals that quantify the uncertainty on the logistic predictions uniformly over the action domain. In doing so, we propose confidence sequences for the kerneiized logistic likelihood model that are of independent interest for developing sample-efficient solvers for online and active classification.
The feedback y/ is Bernoulli random variable, and its likelihood depends the utility function as s( sff(x)))) " [1 - sf (fx -". Then given history He, we can estimate f by ft. the minimizer the regularized negative log-likelihood loss
Ci = Σ yr log [s([(x)))] - (1 - yr) log [1 s(f(x,)) + fl
(3)
where A O the regularization coefficient. The regularization term ensures that ll finite and bounded. For simplicity, we assume throughout the main text that flfell S. B. However, we do not need rely on this assumption to give theoretical guarantces. In the appendix, we present more rig- orous analysis by projecting ft back into the RKHS ball of radius B to ensure that the B B-boundedness condition is met, instead of assuming We do not perform this projection our experiments.
Solving for Ja may seem intractable at first glance since the loss is defined over functions in the large space of Hy- However, it is common knowledge that the solution has parametric form and may be calculated by using gradient descent. This is direct application of the Representer Theorem [Schölkopf et al., 2001] and is detailed in Proposition
Proposition 1 (Logistic Representer Theorem). The regularized negative log- ligliike loss of (3) has a unique minimizer fe which takes the form fe(-) Et=1 ark((, x.) where (ar)..... ate =:
O2, E Re the minimizer of the strictly convex loss
> yr log (s(a T (xx))) - -11-1)) yr) log [1 s(a ke (xx))) + 2 |aal2
ck(a; H:) = Σ -リ
with kx(x)) = ()( k()))....,,,,,,,..... x)) E R'.
Given fú. we may predict the expected feedback for a point as sz)() Centered around this prediction, we construct confidence sets of the form (s(f(())) )) + (z)) and show their uniform anytime validity. The width of the sets are characterized by (ar) defined as
df(x) = k(x x)) k (z) (K) - (x))))
where x- = supasn 1/5(a), with s(a) = s(a) - s(a)) denoting the derivative of the sigmoid function, and K, E 1Rt is the kernel matrix satisfying [Kr] = k(æ,, Our first main result shows that for a careful choice of (8)) these sets contain s s(f())) simultaneously for all x X and
t t 1 with probability greater than 1 1-6. 5.
Theorem 2 (Kernelized Logistic Confidence Sequences). Assume E H4 and lfll S B. Let
0 <<< 6 < 1 and set
2n (n + log 1/6),
B,(6) = 4LB + 2 A 1 log del (I. + (Aks KT),, and L supaon s(a). Then
(5)
where 7t max
P P 1, X (f((z)) (f(=))) - (())) 2 11 8.

---

senction-valueeds confidence sets around the kernelized ridge estimator are analyzed and used exten- sively to design bandit algorithms with noisy feedback on the true reward values [Valko et al., 2013, Srinivas et al., 2010, Chowdhury and Gopalan, 2017, Whitehouse et al., 2023]. However, under noisy logistic feedback, this literature falls short as the proposed confidence sets are no longer valid for the kernelized logistic estimator f.- One could still estimate f using a kernelized ridge estimator and benefit from this line of work. However, as empirically demonstrated in Figure la, this will not be a sample-efficient approach.
Proof Sketch. When minimizing the kernelized logistic loss, we do not have a closed-form solution for ft. and can only formulate it using the fact that the gradient of the loss evaluated at ft is the null operator, i.c. VC(f;; Hz) : H + H = O. The key idea of our proof is to construct confidence intervals H-valued ellipsoids in the gradient space and show that the gradient operator evaluated at f belongs to it with high probability (c.f. Lemma 8). We then translate this back into intervals around point estimates ((fe(z) uniformly for all points E E X. The complete proof is deferred to Appendix A, and builds on the results of Faury et al. [2020] and Whitehouse et al. [2023].
Logistic Bandits. Such confidence sets and bandit algorithms often rely on them to balance exploration against exploitation. To demonstrate how Theorem 2 may be used for bandit optimization with direct logistic feedback, consider LGP-UCB, the kernelized Logistic GP-UCB algorithm. Presented in Algorithm 2, it extends the optimistic algorithm of Faury et al. [2020] from the linear to the kernelized setting, by using the confidence bound of Theorem 2 to calculate an optimistic estimate of the reward. We proceed to show that LGP-UCB attains sublinear logistic regret, which commonly defined
integral tool for action selection under uncertainty,
R²(T) - =>))>>s((aa>ii -(((=)))s((((x)))) s(f(x:)).
s(f(=*)))
To the best of our knowledge, the following corollary presents the first regret bound for logistic bandits in the kernelized setting and may be of independent interest.
Corollary 3. Let 8 E (0, 1] and choose the exploration coefficients 3,(5) as described in Theorem for all I 2 O. Then LGP-UCB salisfies the anylime cumulative regret guarantee of
P
VT 00 (T) S CLLB 2 21-8. 8.
where Ct / log(1 + (1x)
Main Results: Bandits with Preference Feedback
We return to our main problem setting in which a pair of actions, 2, and x/, are chosen and the observed response is noisy binary indicator of æ, yielding higher utility than x/j. While this type of feedback is more consistent in practice, it creates quite a challenging problem compared to the logistic problem of Section 4. The search space for action pairs X' x & is significantly larger than X. and the observed preference feedback of s(f))) f (x()) conveys only relative information between two actions. We start by presenting a solution to estimate f and obtain valid confidence sets under preference feedback. Using these confidence sets we then design the MAXMINI.C algorithm which chooses action pairs that are not only favorable, i.e., yield high utility, but are also informative for improving the utility confidence sets.
5.1 Preference-based Confidence Sets
We consider the probabilistic model of y as stated in Section 3, and write the corresponding regularized negative loglikelihood loss as
cD: = Σ - yr log (s(f(x))) f(x()))
(6)
リン) yz) (1 (10s111s__ppp) (f(xx) f(x())
11
This loss may be optimized over different function classes and is commonly used for linear dueling
bandits [e.g., Saha, 2021], I. and has been notably successful in reinforcement learning with human feedback [Christiano et al., 2017]. We proceed to show that the sefference-baseed loss LD is equivalent to Chp, the standard logistic loss (3) invoked with specific kernel function AD, This will
5

---

allow us to cast the problem of inference with preference feedback as a kernelized logistic regression problem. To this end, we define the dueling kernel as
( (22, x2)) = k(x1, 22) + k(x{, k k( k(2z/1 x22)
for all (2 x1), (222, x22) E X' X, and let HgD be the RKHS corresponding to it. While the two function spaces HED and Hu. are defined over different input domains, we can show that they are isomorphic, under simple regularity conditions.
Proposition 4. Let f X + R. Consider a kernel k and the sequence of its eigenfunctions ( E Assume the eigenfunctions are zero-mean, i.e. Smex Φ, (x))dx O. Then f E H4, if and only there exists h E HyD such that h(æ, x²) f(z)- f(x)). Moreover, || = ll.flla-
The proof is left to Appendix C.I. The assumption on eigenfunctions in Proposition 4 is primarily made to simplify the equivalence class. In particular, the relative preference function can only capture the utility/ up to a bias, i.e., if a constant bias b is added to all values of f. the corresponding function will not change. The value of b may not be recovered by drawing queries from h, however, this will not cause issues in terms of identifying arg max of f through querying values of h. Therefore, we set 0 by assuming that eigenfunctions of are zero-mean. This assumption automatically holds for all kernels that are translation rotation invariant over symmetric domains, since their eigenfunctions are periodic (2()) basis functions, c.g., Matérn kernels and sinusoids.
Proposition 4 allows us to re-write the preference-based loss function of (6) as logistic-type loss
C.0 H.) = Σ y- log (((h(xr,=())) - -1-18 (1-y+) [1 - (h(x,, 2111 + 1 1111,p, 2
>
that is equivalent (3) up to the choice of kernel. We define the minimizer h4 == arg min Cip (h; Ha) and use it to construct anytime valid confidence sets for the utility f given only preference feedback. Corollary 5 (Kernelized Preference- bassed Confidence Sequences). Assume f E Hr and llf S B. Choose 0 < 6 < 1 and set BP (8) and of in equations (4) and (5), with kD used as the kernel funcciin. Then,
P (AI 2 1, X: (he(ax,
2
where h4 = arg min L/. (h; Hz).
Corollary 5 gives valid confidence sets for kernelized utility functions under preference feedback and immediately improves prior results on linear dueling bandits and kernelized dueling bandits with regression-type loss, to kemeliied setting with logistic-type likelihood. To demonstrate this, in Appendix C.3 we present the kernelized extensions of MAXINP (Saha [2021], Algorithm 3), and IDS (Kirschner and Krause [2021], Algorithm 4) and prove the corresponding regret guarantees (cf. Theorems 15 and 16). Corollary 5 holds almost immediately by invoking Theorem 2 with the dueling kernel hD and applying Proposition A proof is provided in Appendix C. for completeness.
Comparison to Prior Work. A line of previous work assumes that both f and the probability s(f())) are B-bounded members of H4. This allows them to directly estimate s(f saf())) via ker- nelized linear regression [Xu et al., 2020, Mehta et al., 2023b, Kirschner and Krause, 2021]. The resulting confidence intervals are then around the least squares estimator, which does not align with the logistic estimator ft. This model does not encode the fact that s sx)())) only takes values in distribution for yt, instead of the Bernoulli formulation when calculating the likelihood. Therefore, the resulting algorithms require more samples to learn an accurate reward estimate. In a concurrent work, Xu et al. [2024] also consider the loss function of Equation (6) and present likelihood-ratio confidence sets. The width of the sets at time T. scales with Tolog (HH; 1/T)) where the second term is the metric entropy of the B-bounded RKHS at resolu- tion 1/T,, that is, the log-covering number of this function class, using balls of radius 1/T. is known that log.N (7H;; 1/T) x "Tr as defined in Theorem 2. This may be easily verified using Wainwright [2019, Example 5.12] and [Vakili et al., 2021, Definition 1]. Noting the definition of 8. we see that likelihood ratio sets of Xu et al. [2024] are wider than Corollary 5. Consequently, the presented regret guarantee in this work is looser by factor of 1/4 compared to our bound in Theorem 6.
[o, 1] and considers

---

Algorithm 1 MAXMINLCB
Input (8P))21 for / 2 do
Play the most potent pair (zz, 2/) according the Stackelberg game
Dt arg max s (ar o' 3, of (ar
æ
s.t. x' (x) arg min s(1,(z, 3.ooP (f
x EM;
and arj xx (mz))
Observe yr and append history. Update 1 and of41 and the set of plausible maximizers
M41 f E X Va' E X' ((22+1(0, x²)) + (21, 2 0.5}.
end for
5.2 Action Selection Strategy
Let x'' (x) arg ming'eM. LCB, (æ, x') denote response function. We propose MAXMINLCB in Algorithm for the preference feedback bandit problem that selects 22 and x' jointly as
Tt = arg max LCB, x (x)) æEM.
(Leader)
x x' exx)
(Follower)
where the lower-confidence bound (x, pessimistic estimate of h and M₁ = fx E Vo' E E s(h x
s(h,(x,
3.0 (x, x') presents
x²))+ + 0. (0l x') 2 0.5] is the
set of potentially optimal actions. The second action is chosen as x; = x' (xx) Equation (7) forms a zero-sum Stackelberg Lccaer-Folloower game where the actions H and z; are chosen sequentially [Stackelberg. 1952]. First, the Leader selects I;, then the Follower selects xy depending on the choice of 24. Importantly, due to the sequential nature of action selection, 2; is chosen by the Leader such that the Follower's action selection function, x'(-), is accounted for in the selection of xt- Sequential optimization problems are known to be computationally NP-hard even for linear functions [Jeroslow, 1985]. However, due to their importance in practical applications, there are algorithms that can efficiently approximate a solution over large domains [Sinha et al., 2017, Ghadimi and Wang, 2018, Dagréou et al., 2022, Camacho-Vallejo et al., 2023].
MAXMINLCB builds on simple insight: if the utility f is known, both the Leader and the Follower will choose x" yielding an objective value 0.5 for both players, and zero dueling regret. Since MAXMINLCB has no access to f. it leverages the confidence sets of Corollary 5 and uses a pessimistic approach by considering the LCB instead. There are two crucial properties of the Follower specific to this game. First, the Follower respect to the LCB,. In any scenario, the Follower can match the Leader's ' action which results in (C,, xt) 0.5. Second, for sufficiently tight confidence sets, the Follower will not select sub-optimal actions. In this case, the Leader's 's best action must be optimal as it anticipates the Follower's response and Equation (7) recovers the optimal actions. Therefore, the objective value of the game considered in Equation (7) is always less than, or equal to the objective of the game with known utility function i.e., LCB, (w,, x() < 0.5 fxx xx) and the gap shrinks with the confidence sets. Overall, the Stackelberg game in Equation (7) can be considered as a lower approximation of the game played with known utility function f.
not do worse than the Leader with
The primary challenge for MAXMINLCB is to sample action pairs that sufficiently shrink the confidence sets for the optimal actions without accumulating too much regret. MAXMINLCB trade-off naturally with its game theoretic formulation. We view
balances this the selection of 2; be exploitative by trying to maximize the unknown utility f(x;) and minimizing regret. On the other hand, x; is chosen to be the most competitive opponent to Z,, i.e., testing whether the condition LCB, (ær, at) 2 0.5 holds. Note that LCB, is pessimistic concerning æ, making robust against the uncertainty in the confidence set estimation. At the same time, LCB, is an optimistic estimate for a encouraging exploration. In our main theoretical result, we prove that under the assumptions of Corollary 5, MAXMINLCB achieves sublinear regret on the ducling bandit problem.
7

---

300
400
100
Regret: R(((r)
Regret: se
300
70m
200
50
20
0.01
700
1303
12501
1500
1750
2000
2.0
6.0
800
1000
Time Step:
Time Step:
IND-UCB
(Uur)))
MAsMisLCB:OOrrs)
DOUBLER
McLTISMM
Loo. UCBL
GP-UCB
MAXIsP
RUCB
IDS
(a) Logistic feedback
(b) Preference feedback
Figure 1: Regret of learning the Ackley function with logistic and preference feedback. (a) Same UCB algorithms, each using a different confidence set. LGP-UCB performs best, showcasing the power of Theorem (b): Algorithms with different acquisition functions, all using our confidence sets. MAXMINLCB is more sample-efficie
Theorem 6. Suppose the utility function lies in H. with a norm bounded by B, and that kernel satisfies the assumption of Proposition 4. Let 5 E (0, 1] and choose the exploration coefficient SP (5) as Corollary 5. Then MAXMINLCB satisfies the anytime dueling regret of
P VT 0: RP) C33 C.
8
where 7T is the T-step information gain of kernel DD and C3 (8
2x) hts//Voog Vlog(1 + 4(Ax)-1).
The proof is left to Appendix C.2. The information gain 7T' in Theorem 6 quantifies the structural complexity of the RKHS corresponding to kD and its dependence on T is fairly understood for kernels commonly used in applications of bandit optimization. As an example, for Matérn kernel of smoothness defined over a d-dimensional domain, pr ((Td/(2v+d) [Remark 2, Vakili et al., 2021] and the corresponding regret bound grows sublinearly with T.
Restricting the optimization domain M, X is common the literature [Zoghi al., 2014a, Saha, 2021] despite being challenging in applications with large continuous domains. We conjecture that MAXMINL would enjoy similar regret guarantees without restricting the selection domain M as done in Equation (7). This claim is supported by our experiments in Section 6.2 which are carried out without such restriction on the optimization domain.
Experiments
Our experiments are on finding the maxima of test functions commonly used in (non-convex) optimization literature [Jamil and Yang, 2013], given only preference feedback. These functions cover challenging optimization landscapes including several local optima, plateaus, and valleys, allowing test the versatility of MAXMINLCB. We the Ackley function for illustration in the main text and provide the regret plots for the remainder of the functions in Appendix E. For all experiments, we set the horizon T = 2000 and evaluate all algorithms 100. Additionally, we conducted experiments on the Yelp restaurant review dataset to demonstrate the applicability MAXMINLCB on real-world data and its scaling to larger domains. All experiments are run across 20 random seeds and reported values are averaged over the seeds, together with standard error. The environments and algorithms are implemented end-to-end in JAX [Bradbury et al., 2018 2018].
uniform mesh over the input domain of size
6.1 Benchmarking Confidence Sets
Performance of MAXMINLCB relies validity and tightness of the LCB. We evaluate the quality of our kernelized confidence bounds, using the potentially simpler task bandit optimization given logistic feedback. To this end, we fix the acquisition function for the logistic bandit algorithms to the Upper Confidence Bound (UCB) function, and benchmark different methods for calculating the confidence bound. We refer the algorithm instantiated with the confidence sets of Theorem 2 as LGP-UCB (c.f. Algorithm 2). The IND-UCB approach assumes that actions are uncorrelated, and
Thh code is made available githbb.omm/ssppgggtaaMMM..CC.

---

Table 1:
Benchmarking Ry for a variety of test utility functions, T 2000. The top 3 rows show results for smoother functions without steep gradients and local optima while the bottom rows show the results for more challenging problems.
MAXMINLCB DOUBLER
MULTISBM
MAXINP
RUCB
IDS
Branin
104 = 13
1
89 - 13
340
101
163 = 22
Matyas
125 + 5
136
106 7
136 6
128 5
Rosenbrock
27 +
44
25 5
109 2 2
58 7
58 = 13
Ackley
56 2
7212
0.5
120=1
0.7
1
Eggholder
113
154
134
230
213 40
141 + 12
Hoelder
141 + 26
154
136
204
200
28
132
+ 15
Michalewicz
138 + 14
183 11
155
- 10
260 + 40
269
+ 46
188
- 21
Yelp
175 = 22
263
=
199
25
409 = 15 214
22
255
= 22
maintains an independent confidence interval for each action as Lattimore and Szepesvári [2020.
Algorithm 3j. This demonstrates how LGP-UCB utilizes the correlation between actions. We also implement LOG-UCB, [Faury et al., 2020] that assumes that f a linear function, i.e., f(x) 8 x to highlight the improvements gained by kernelization. Last, we compare LGP-UCB with GP-UCB [Srinivas et al., 2010] that estimates probabilities s(f(-)) via a kernelized ridge regression task. This comparison highlights the benefits of using our kernelized logistic estimator (Proposition 1) over regression-basee approaches [Xu et al., 2020, Kirschner and Krause, 2021, Mehta et al., 2023b,a]. Figure la shows that the cumulative regret of LGP-UCB is the lowest among the baselines. GP-UCB performs closest to JGB-UCB, however, it accumulates regret linearly during the initial steps. Note that GP-UCB and LGP-UCB differ in the estimation of the utility function fr while estimating the width of the confidence bounds similarly. This result suggests that using the logistic-type loss (3) to infer the utility function is advantageous. As expected, IND-UCB converges at slower rate than LGP-UCB and GP-UCB due to ignoring the correlation between arms while LOG-UCB I's regret grows linearly the Ackley function is misspecified under the assumption of linearity. We defer the results on the rest of the utility functions to Table in Appendix E and the figures therein.
6.2 Benchmarking Acquisition Functions
In this section, we compare MAXMINLCB with other utility-based bandit algorithms. To isolate the benefits of our acquisition function, we instantiate all algorithms with the same confidence sets, and use our improved preferred-based bound of Corollary 5. Therefore, our implementation differs from the corresponding references, while we refer to the algorithms by their original name. We consider the following baselines. DOUBLER and MULTISBM [Ailon et al., 2014] choose I; as a reference action from the recent history of actions and pair it with z' which maximizes the joint UCB (cf. Algorithm 5 and 6). RUCB [Zoghi et al., 2014a] chooses x' similarly, however, it selects the reference action uniformly at random from M, (Algorithm 7). MAXINP [Saha, 202 1] also maintains the set of plausible maximizers M,, and at each time step, it selects the pair of actions that maximize of² (x, æ²) (Algorithm 3). IDS [Kirschner and Krause, 2021] selects the reference action greedily by maximizing ft, and pairs it with an informative action (Algorithm 4). Notably, all algorithms, with the exception of MAXINP, choose one of the actions independently and use it as a reference point when selecting the other one. Figure 3 illustrates the differences in action selection between UCB, maximum information, and MAXMINI.CB approaches. We note that POP-BO [Xu et al., 2024] and MULTISBM only differ in the estimation of the confidence set. Since we deploy the same confidence for all acquisition functions, the two algorithms are equivalent and we use MULTISBM in our results, however, comparisons hold for POP-BO as well.
Figure lb benchmarks the algorithms using the Ackley utility function, where MAXMINLCB out- performs the baselines. All algorithms suffer from close-to-linedt regret during the initial stages of learning, suggesting that there an inevitable exploration phase. Notably, MAXMINLCB, IDS, and DOUBLER are the first to select actions with high utility, while RUCB and MAXINP explore for longer. Table 1 shows the dueling regret for all utility functions. MAXMINLCB consistently outperforms the baselines across the analyzed functions and achieves low standard error, supporting its efficiency in balancing exploration and exploitation in the preference feedback setting. Only MULTISBM shows comparable performance to MAXMINI and even outperforms it on the Matyas function which is relatively smooth function posing simple optimization problem. However, MAXMINI.CH achieves lower regret on the Ackley and Eggholder functions which obtain many local optima and steeper

---

150
1254
Regret: RP(T).
100
76-
01
100
600
800
1000
Time Step:
DOUBLER
MMurIBMM
MAXINP
RUCB
IDS
Figure 2: LGP-UCB is more sample-efficient when making restaurant recommendations based on Yelp open dataset with preference feedback. All baselines use the confidence sets of Cor. 5.
gradients showing that MAXMINLCB is preferable for challenging optimization problems. Other acquisition functions work well only in certain cases, e.g., IDS achieves the smallest regret for opti- mizing Matyas, while RUCB excels on the Branin function. This indicates the challenges each utility function offers and the performance of the action selection is task dependent. The consistent perfor- mance of MAXMINLCB demonstrates its robustness against the underlying unknown utility function.
6.3 Real-world Experiment
To demonstrate the scalability and applicability of MAXMINLCB, we conduct an experiment on the Yelp dataset of restaurant reviews, which consists of 275 restaurants and users after the pre-processing stage. For each user, we want to find the restaurants that best fit their preference, via making sequential recommendations and receiving comparative feedback. We define the action space X' by assigning to each restaurant their respective 32-dimensional embedding of their reviews, i.e., X C 3R The dataset provides utility values for users the form of ratings on the scale of to however, not all users rated every restaurant.
We estimate missing ratings using collaborative filtering [Schafer al., 2007]. Further details on the data processing are deferred to Appendix D.1. Figure 2 shows that the results of this larger problem align with previous conclusions. MAXMINI.CB remains the bert-perfonning algorithm with MULTISBM following second. The cumulative regret is also reported in Table 1. Note that neither of the algorithms is tuned or modified for this experiment. These results are only intended to demonstrate that 1) the computations easily scale, and 2) the kernelized approach is still applicable in text-based domain, by using high-quality vector embeddings.
Conclusion
We addressed the problem of bandit optimization with preference feedback over large domains and complex targets. We proposed MAXMINI.BB which takes cheer-teeoettic approach the problem of action selection under comparative feedback, and naturally balances exploration and exploitation by constructing zero-sum Stackelberg game between the action pairs. MAXMINLCB achieves sublin- ear regret for kernelized utilities, and performs competitively across range of experiments. Lastly. by uncovering the equivalence of learning with logistic comparative feedback, we propose kernelized preference-basee based confidence sets, which may be employed in adjacent problems, such as reinforce- ment learning with human feedback. The technical setup considered in this work serves foun- dation for number of applications in mechanism design, such as preference elicitation and welfare optimization from multiple feedback sources for social choice theory, which we leave as future work.
Acknowledgments and Disclosure of Funding
We thank Scott Sussex for his thorough feedback. This research was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and Innovation Program Grant agreement No. 81 5943. Barna Pásztor was supported by an ETH AT Center doctoral fellowship, and Parnian Kassraic by Google PhD Fellowship.
10

---

References
Yasin Abbasi-Yadkori, Online learning for linearly parametrized control problems. PhD thesis, University of Alberta, 2013.
Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits, In International Conference Machine Learning, pages 856-864, PMLR, 2014.
Fabio Aiolli and Alessandro Sperduti. Learning preferences for multiclass problems. Advances in neural information processing systems, 17, 2004.
Sheldon Axler. Measure, integration & real analysis. Springer Nature, 2020.
Viktor Bengs, Róbert Busa-Fekete, Adil EI RessoudiiPaulle and Eyke Hüllermeier. Preference-basee online learning with dueling bandits: A survey. The Journal of Machine Learning Research, 2021.
Alina Beygelzimer, David Pal, Balazs Szorenyi, Devanathan Thiruvenkatachari, Chen-Yu Wei, and Chicheng Zhang. Bandit multiclass linear classification: Efficient algorithms for the separable case. In International Conference Machine Learning, pages 624 633. PMLR, 2019.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclau- rin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-MMine, al. JAX: compos- able transformations of Python+ NumPy programs, 2018. URL http::/githiii com/ google/ jax.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 1952.
Eric Brochu, Vlad M Cora, and Nando De Freitas. A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprint, 2010.
José-Fernande Camacho- Vallejo, Carlos Corpus, and Juan G Villegas. Metaheuristics for bilevel optimization: A comprehensive review. Computers & Operations Research, page 106410, 2023.
Camaeho-Vallejo,
Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al. Open problems and fundamental limitations of reinforcement learning from human feedback. Transactions Machine Learning Research, 2023.
Bangrui Chen and Peter Frazier. Dueling bandits with weak regret. In International Conference Machine Learning, pages 731-739. PMLR, 2017.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pages 844-853, PMLR, 2017.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Wei Chu and Zoubin Ghahramani. Preference learning with gaussian processes. In Proceedings of the 22nd international conference Machine learning, pages 137-144, 2005.
Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, and Thomas Moreau. A framework for bilevel optimization that enables stochastic and global variance reduction algorithms. Advances in Neural Information Processing Systems, 35:26698-266 10, 2022.
Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. Conference on Learning Theory, pages 563-587. PMLR, 2015.
Moein Falahatgar, Alon Orlitsky, Venkatadheeraj Pichapati, and Ananda Theertha Suresh. Maximum selection and ranking under noisy comparisons. In International Conference on Machine Learning, pages 1088-1096. PMLR, 2017.

---

Louis Faury, Mare Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pages 3052-3060. PMLR, 2020.
Louis Faury, Mare Abeille, Kwang- Sunng--Sngggaa Jun, and Clément Calauzènes. Jointly efficient and optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 546-580. PMIR, 2022.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. Advances in neural information processing systems, 2010.
Dylan Foster and Akshay Krishnamurthy. Contextual bandits with surrogate losses: Margin bounds and efficient algorithms. Advances in Neural Information Processing Systems, 31, 2018.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv: 02246. 2018
Javier González, Zhenwen Dai, Andreas Damianou, and Neil Lawrence. Preferential bayesian optimization. In International Conference Machine Learning, pages 1282-1291. PMLR, 2017.
Neil Houlsby, Ferene Huszár, Zoubin Ghahramani, and Máté Lengyel. Bayesian active learning for classification and preference learning. arXiv preprint arXiv:1112.5745, 2011.
Kevin G Jamieson and Robert Nowak. Active ranking using pairwise comparisons. Advances in neural information processing systems, 24, 2011.
Momin Jamil and Xin-She Yang. A literature survey of benchmark functions for global optimisation problems. International Journal of Mathematical Modelling and Numerical Optimisation, 4(2): 150-194, 2013.
Robert G Jeroslow. The polynomial hierarchy and simple model for competitive analysis. Mathe- matical programming, 52(2):146-166) 1985.
Xiang Ji, Huazheng Wang, Minshuo Chen, Tuo Zhao, and Mengdi Wang. Provable benefits of policy learning from human preferences in contextual bandit problems. arXiv preprint urXiv:2307.12975 2023.
Johannes Kirschner and Andreas Krause. Bias-robust bayesian optimization via ducling bandits. In International Conference on Machine Learning. PMLR, 2021.
Johannes Kirschner, Tor Lattimore, and Andreas Krause. Information directed sampling for linear partial monitoring. In Conference Learning Theory, pages 2328-2369 PMLR, 2020.
Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Optimal regret analysis of thompson sampling in stochastic multi-armes bandit problem with multiple plays. In International Conference on Machine Learning, pages 1152-1161. PMLR, 2015.
Wataru Kumagai. Regret analysis for continuous dueling bandit. Advances in Neural Information Processing Systems, 30, 2017.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Peter D Lax. Functional analysis, volume 55, John Wiley & Sons, 2002.
Junghyun Lee, Se- Yo-Young Yun, and Kwang-Sung Jun. Improved regret bounds of (multinomial) logistic bandits via regret-to-comffdence-e conversion. International Conference on Artificial Intelligence and Statistics, pages 4474-4482. PMLR, 2024.
Viraj Mehta, Vikramjeet Das, Ojash Neopane, Yijia Dai, Ilija Bogunovic, Jeff Schneider, and Willie Neiswanger. Sample efficient reinforcement learning from human feedback via active exploration. arXiv preprint, 2023a.
Viraj Mehta, Ojash Neopane, Vikramjeet Das, Sen Lin, Jeff Schneider, and Willie Neiswanger. Kemelized offline contextual dueling bandits. arXiv preprint, 2023b.
12

---

Petrus Mikkola, Milica Todorović, Jari Järvi, Patrick Rinke, and Samuel Kaski. Projective preferential bayesian optimization. In International Conference on Machine Learning. PMLR. 2020.
Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, et al. Nash learning from human feedback. arXiv preprint, 2023.
Tung Nguyen, Qiuyi Zhang, Bangding Yang. Chansoo Lee, Jorg Bornschein, Yingjie Miao, Sagi Perel, Yutian Chen, and Xingyou Song. Predicting from strings: Language model embeddings for bayesian optimization. arXiv preprint, 2024.
Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. Advances Neural Information Processing Systems, 34:30050-30062, 2021.
Aadirupa Saha and Akshay Krishnamurthy. Efficient and optimal algorithms for contextual dueling bandits under realizability. In International Conference on Algorithmic Learning Theory. PMLR, 2022.
Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajectory preferences. In Proceedings The 26th International Conference on Artificial Intelligence and Statistics. PMLR, 2023.
J Ben Schafer, Dan Frankowski, Jon Herlocker, and Shilad Sen. Collaborative filtering recommender systems. The adaptive web: methods and strategies of web personalization, pages 291-324. Springer, 2007.
Bernhard Schölkopf, Ralf Herbrich, and Alex Smola. A generalized representer theorem. In International conference on computational learning theory, pages 416-426. Springer, 2001.
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review on bilevel optimization: From classical to evolutionary approaches and applications. IEEE transactions evolutionary computation, 22(2): 276-295, 2017.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process opti-
mization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Leurning, 2010.
Heinrich von Stackelberg. Theory of the market economy. Oxford University Press, 1952.
Yanan Sui, Vincent Zhuang, Joel Burdick, and Yisong Yue. Multi-dueling bandits with dependent arms. arXiv preprint arXiv: 705.00055, 2017.
Shion Takeno, Masahiro Nomura, and Masayuki Karasuyama. Towards practical preferential bayesian optimization with skew gaussian processes. International Conference on Machine Learning, pages 33516-33533. PMLR, 2023.
Maegan Tucker, Ellen Novoseller, Claudia Kann, Yanan Sui, Yisong Yue, Joel W Burdick, and Aaron D Ames. Preference-based learning for exoskeleton gait optimization. In 2020 IEEE international conference robotics and automation (ICRA). IEEE, 2020.
Tanguy Urvoy, Fabrice Clerot, Raphael Féraud, and Sami Naamane. Generic exploration and k-armed voting bandits. In International Conference on Machine Learning. PMLR, 2013.
Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82-90. PMLR, 2021.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilas Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint 1309:6339.6669, 2013.
Martin J Wainwright. High-dimenssoonl statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
Justin Whitehouse, Zhiwei Steven Wu, and Aaditya Ramdas. Improved nolf-normalized concentration in hilbert spaces: Sublinear regret for gp-ucb. arXiv preprint 2307.0037 2023.
13

---

Huasen Wu and Xin Liu. Double thompson sampling for dueling bandits. Advances in neural information processing systems, 29, 2016.
Wenjie Xu, Wenbin Wang, Yuning Jiang, Bratislav Svetozarevic, and Colin N Jones. Principled preferential bayesian optimization. arXiv preprint crXiv:2402.05367, 2024.
Yichong Xu, Aparna Joshi, Aarti Singh, and Artur Dubrawski. Zeroth order non-convex optimization with dueling-choice bandits. In Conference on Uncertainty in Artificial Intelligence. PMLR, 2020.
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, 2009.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 2012.
Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Jason Lee, and Wen Sun. Provable offline reinforcement learning with human feedback. arXiv preprint, 2023.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning, pages 43037-43067. PMLR, 2023.
Julian Zimmert and Yevgeny Seldin. Factored bandits. Advances in Neural Information Processing Systems, 31, 2018.
Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. In International conference on machine learning. PMLR, 2014a.
Masrour Zoghi, Shimon A Whiteson, Maarten De Rijke, and Remi Munos. Relative confidence sampling for efficient on-line ranker evaluation. In Proceedings of the 7th ACM international conference on Web search and data mining, 2014b.
14

---

Contents of Appendix
Proofs for Bandits with Logistic Feedback
15
Helper Lemmas for Appendix A
18
C Proofs for Bandits with Preference Feedback
20
C.1 Equivalence of Preference- based and Logistic Losses
20
C.2 Proof of the Preference-basee
Regret Bound C33 Extending Algorithms for Linear Dueling Bandits to Kernelized Setting
21
23
C.4 Helper Lemmas for Appendix C.3
27
D Details of Experiments
28
D.I Yelp Experiment
30
Additional Experiments
30
A Proofs for Bandits with Logistic Feedback
We have written the equations in the main text in terms of kernel matrices and function evaluations, for easier readability. For the purpose of the proof however, we mainly rely on entities in the Hilbert space. Consider the operator Then by Mercer's theorem, any / E H& may be written f 0 cb, where B-bounded f2 norm. For a sequence of points 21...., D2 E X, we define the (infinite-dimensiioaa) feature map $ ( <b(ar))] which gives rise to the kernel matrix K, IRC TK. and the covariance operator S; Hd - H.. respectively defined as K, = 2 and S; = 2 4.. Let I, denote the t-dimensional identity matrix, and I be the identity operator acting on the RKHS, Then it is widely known that the covariance and kernel operators are connected via det Ix + --;) = det(L, + p p-2 Ki)) for any 2 and p * O. For operators on the Hilbert space, det(AA) (A) refer Fredholm determinant [c.f. Lax, 2002]. Lastly, in the appendix, we refer to the true unknown utility function as f (x: & (z)00. In the main text, the true utility is simply referred as
H. which corresponds to kernel and satisfies k(x,,) -) ((x). (N) and has
To analyze our function-valuu confidence sequences, we start by re- re-writing the logistic loss function
Fr log s (0T (()(((x))) - Σ wr) log s =00 ( ))) + 1
L(O; H.)
which is strictly convex in 0 and has a unique minimizer 0, which satisfies
VL H.)
-v+((x+)) + (0.)
where (0) H. + 7 is linear operator defined
g: ((a+)s((0) ((a:)s(0T<<a.))) X0.
In the main text, assumed that minimizer of L satisfies the norm boundedness condition. Here, we present a more rigorous analysis which does not assume so. Instead, we work with projected estimator defined via
0. = arg min (g) (((0,)ll
(8)
10
where V, = KAIN and O, is the minimizer of L(0; H.). Roughly put, 0." (NN is a norm B-bounded alternative to Q., who also satisfies a small VL, and therefore, is expected to result an ac- curate decision boundary. We will present our proof in terms of 0," This also proves the results in the main text, since 0." 0, if 0, itself happens to have B-bounded norm, as assumed in the main text.
Our analysis relies on a concentration bound for H-valued martingale sequences stated in Abbasi-Yadkori [2013] and later in Whitehouse al. [2023]. Below, we have adapted the statement to match notation.
15

---

Lemma 7 (Corollary Whitehouse et al. [2023]). Suppose the sequence (21)121 is addatted where F, == a :e.....,2:: El......... ,t-1), and E, are i.i.d. zero-mean o-subGaussian noise. Consider the RKHS H. corresponding a kernel k(æ,, x') we have that, with probability at least 1 6, simultaneously for all t t
(x)) Then, for any p and ò E (0, 1),
Σ e ((),) TSA
S ooy
2 log
+
Ve
where V,= = S IH
The following lemma, which extends Faury et al. [2020, Lemma 8] to H-valued operators, expresses the closeness of O, and 0* in the gradient space, with respect to the norm of the covariance matrix.
Lemma (Gradient Space Confidence Bounds). Set 0 < 8 1. Under the assumptions of Theorem
vt 0: ((.((0,) g: (l)00) $ 2 12v2222 2log 1/8 2YT +
2 B
2 21-
where Vg St KAIN-
Proof of Lemma 8, Recall that gi( s(5 = ((())))))) + 10. Then is straighforward to show that
VL(0: H.) Σ)tΦ(a))) 99 (0).
TSt
Since 0, is a minimizer of Lt, it holds that g:(0)) = Erse Ur (x;>) This allows us to write,
(0.) 9. (1,,
Σ
(yr s( (xr))*)) x(xx,) 20-
rst
1/-
Σ c pp x
+ llv--
where E = yr s(Φ (ax, )0) history dependent random variable [0, 1] due the data model. To bound the first term, recognize that any random variable in [0, 1] is sub-Gaussian with a = 0.3 and apply Lemma 7. We obtain that for all 2 0, with probability greater than 8
1 Vdee(L + (An)-1K))
Σ (xx)) rst
S 2 log
2V
V.-1
S v 2 log 1/0 2yr
since (p) supp......e 2 log det + p-2 K,)). To bound the second term in (9), note that S. T o; is PSD and therefore V. 2 RAIx. Then
X
1l10 1yy I
0
S
B. K
concluding the proof.
The following lemma shows the validity our parameter-space confidence sets. Lemma 9. Set 0 8 < 1 and consider the confidence sets
(x) { ||l|| < B, - < 2VARB 2 1/8 2
0f
Then,
P P(v 0: 0: 0- O,)))) 21-8
16

---

Proof of Lemma 9. We check if 0 E (x(6) by bounding the following norm
0 -0, 01l.v I (0)) (.(0
(Lem. 12)
[1 (0*) gr(0,) ll, + (1)) gi (0)(
2x (o))lll,,
(Eq. 8)
<v 2 1/6 27T 2VABB
(Lem. 8)
Lastly, we prove a formal extension of Theorem 2. Theorem 10 (Theorem 2 Formal). Ser
and consider the confidence sets Ee(6) Hx
(( = ( (f()) aT x()) 0 E {,)))-
Then, simultanously for all E X, E E() and t 2
|s(f(x)) (x))) s ((()),(())
with probability greater than - 6, where
K X
(6) = 4LB 2L
log 1/6 + 2
Proof of Theorem 10. For simplicity in notation let us define
(5) 2v BV 2og 1/6 + 2
Suppose f = - (-) in & (0). Then
(()'(x)0) s (z)0) (,(x;;,0") (z) 0*)
Lem. 11 is L-Lipschitz
s L (x) 0*)
S L)( 0*1|v;
L||Ø(x))
(10 0 ll, =100," 001lv:)
< 77110(())lly;-
(3)(5) 0 01llv))
0 (.())
whp
2L3((0)(0(z))1
Lem.
2LB,(0) 0. (x)))
Lem. 13
VXv
= (x)
[L.B + 2T, 2 logg11 1/8 27T
where the third to last inequality holds with probability greater than - 6, but the rest of the inequalities hold deterministically.
Given the confidence set of Theorem 2, we give extend the LGP-UCB algorithm of Faury et al. to the kernelized setting (c.f. Algorithm and prove that it satisfies sublinear regret.
Proof of Corollary 3. Recall that if æ; is the maximizer of the UCB, then
s( (x" )0!) s( (z,)0?)) < or (zx o,(x (,()))8
Then using Theorem 10, obtain the following for the regret at step t,
rt = s( (a (a*))")= s(6 =( (a:))*)
= =(Φ (a:" 0-) =<="T("")00
-( (x= )(') ) + s(6 (m:))))) =( (x)) + + (x=))/² (<x, (x.)))
5 <o,(2") + (.:) a. (x:) - (
17

---

Algorithm 2 LGP-UCB
Initialize Set (5))221 according to Theorem 2. for i 2 do
Choose an optimistic action via
Tt arg max (f=xx(((=1 + 11-1(0))r-1(z))
zex
Observe Yt and append history. Calculate ft to Proposition and update o Theorem 2. end for
with probability greater than 8 for all t 0. Which allows us bound the cumulative regret as,
T
T
Rr
rt
S
T
1=1
1=1
T
$ =28r(0),
T
Be(6) - (r(
Lem. 14
where C1 18/log(1 + (Ars)
B Helper Lemmas for Appendix
Lemma 11 (Mean-Vale Value Theorem). For any X and 02, 02 (g(NN it holds that
<00 (fx))) - =00 ((x)) = alæ; 0, (2) - 01) ((x))
where
(x 01, 02) 1-' 8(v0, ((x) + (1 (1- ((x))du
(10)
R by the fundamental theorem of Proof of Lemma 11. For any differentiable function
calculus we have
s(22) - 5(21) = 1 8(2)d2.
We change the variable of integration to v (z - 21)/ - 21), then v22 + (1 v)2 and re-writing the integral in terms of v gives.
s(2)) (22 - 21) / 3(V22 + dd
122)
Letting 21 = ((x) and 22 = 0 (xx) concludes the proof.
Lemma 12 (Gradients to Parameters Conversion). For all t 2 0 norm B-bounded 01, (2
0 02llv, S <lllg. g.(02)llv,.-
Proof of Lemma 12. We prove the lemma through an auxiliary operator G,(0,, 02) operating on He
G. AIu
Σ 02))b (xx,)
TSt
where a is defined in (10).
Step 1. First establish how
go back and forth between the operator norms defined based
on G, and V.. Recall that k = sup.5B a(=)- Therefore, x < 8(2) for all 2 < B. implying that
a(:; 0, 02) 2 So K dv = -! We can then conclude.
G,(0,,02 > NJy + Σ
(x (xx) (T),)))((<)))) =R"" -
(II)
18

---

Step 2. Now by the definition of ge(O),
g: g:(02) - = X(02 - -01)+ +
Σ o(x,) [s o(x,)) - s00, ((xx))))
TSt
= x(02 01) + Σ
Φ(x,) |a(2,; 01,02) 02) (z,) 01)
(Lem. 11)
rst
MHx + Σ
a(x,; 01, (2)02)(((,))))) (x,) (x+)) (02 01)
-5t
GO, 02) (02 01)
Therefore,
19:: g gc (((0))l (0) = (0x) (:()))] (0) - -2)
(02 01) G. (02 01)
00 01 Cill,, o.)
(12)
Step 3. Putting together the previous two steps, we can bound the Vi-norm over the parameters to the V,-1 role in the gradients,
(1)) 10: 0211v. S Vk 0 - 0211c, 0.)
Vx (())) -e(02)ll
w (0)) - (,(0))ll,,-
concluding the proof.
The following two lemmas are standard results in kernelized bandits [Srinivas al., 2010, Chowdhury and Gopalan, 2017, e.g... We include it here for completeness.
Lemma 13. Let or be defined in (4), Then v Vxxilo(<=)lll orr(x) for for any E X.
Proof of Lemma 13. We start by stating some identities which will later be of use. First note that
( th ARIH) Φ. Φ (0.07 Amsi))
which gives
T ( + AmII) -1 (Ø, th + ARTI))) -1 TT
(13)
Moreover, by definition of k2 we have
(xx)) 11Φ(x))
(14)
which allow to write
(4) 4, + \nlz) ((x) = 2 (x) + \mc(())
and obtain
(xx) = ( t AmIz)
क. (x) + Au ( t2 + AxT) -1
x(x))
+ DT + AwIi)) (x) + Ax (o. 4; + ArI) Φxx).
Given the above equation, we conclude the proof by the following chain equations: k(x, x)) Φ (x))(x))
( ( + AkI.) kx((a)) Am (0] 8r + AsIz) -1 ((x)) Φ(x)
kef (x) (D. + AmI.)) (p)(())) And T (æ)) (0, t, + AmIz)) (xx))
(4) xTT (a) (K, + AKI,) (x) + Ano V.- (xx)
To obtain the third equation have used the fact that for bounded operators on Hilbert spaces, the inverse of the adjoint is equal to the adjoint of the inverse [e.g., Theorem 10.19, Axler, 2020]. Re-ordering the equation above we obtain (z)) ><<
concluding the proof.
D
19

---

Lemma 14 (Controlling posterior variance with information gain). For all T 2 1,
T
2
878 Top (x))) - log(1 ((Ax))
(+))
- log(1 (Ax)-
Proof of Lemma 14. By Srinivas et al. [2010, Lemma 5.3],
T
1
log(1 + (Ax) (x)-
YT
max
201 .TT
2
Following the technique in Srinivas et al. [2010, Lemma 5.4), since of < 1, then (Ax)-lo? E [0, (. Now for any E [0, (Ax) 2 s C'log(1 2) where C = (AAA + (Ax)-1)). We then may write,
T
T
Σ 1=1
of (1t)
Me(Aks)-oa
T
AsClog (1 (Ax) tof(()))
log(1 + (Ak) ( [z(())
log (1 + (1x)-11
Putting both together proves the first inequality of the lemma. As for the dueling case, we can easily check that of 2, and similar argument yields the second inequality.
C Proofs for Bandits with Preference Feedback
This section presents the proof of main results in Section 5, and our additional contributions in the kernelized Preference-based setting.
C.1 Equivalence of Preference- and Logistic Losses
We start by establishing the equivalence between the logistic loss (3) and dueling loss (6).
Proof of Proposition 4. By Mercer's theorem, we know that the kernel function k has eigen- value eigenfunction pairs (V), Φ.) for 2 where o; are orthonormal. Then k(x, x') = (zz)) with (x(x)) (λ),(z)) Now applying the definition of kD, it holds that -P2,z')= = vs (z)) where (/(()) = ( (xx)). is straighforward to check that sis are the eigenfunctions of ID, however, they may not be orthonormal. We have,
(vi, (1) = 21, - b2) (1h,, b5)), = 2V/Aibbbbby
where ( By the assumption of the proposition, we have b, However, this assumption holds automatically for all kernels commonly used in applications, e.g. any translation invariant kernel, over many domains, since Φ; for such kernels are sine basis.
Now since f E Hs. it may be decomposed difference function to h(x, x') Σi>1 (z)) We can then bound the RKHS norm of h w.r.t. the
E(>1 Beor and [l Σ 63 < co. And set the
20

---

kernel kD as follows
(h, d )
|
Σ
(ete, Vir)
121
121 Bg (0,,,85522
21:(1 - bi)
121
2
bj
8
Σ EBbby 3t1
V bi)
b=0
| B².
Now by Mercer's theorem, h HAD since it is decomposable sum of kD eigenfunctions, and attains a B-bounded D. -norm which we showed to be equal to [| The other direction of the statement is proved the same way.
Proof of Corollary 5. Consider the utility function f and define h(x, x²) = f(x) - f(x'). Then by Proposition 4, h RKHS of ID with kP -norm bounded by We may estimate by minimizing C (:; Hc). Now invoking Theorem 2 with the dueling kernel we have,
P ( 1, x, E x:: (h,(2, - s (h(2, e' = (6)o, (2,, 2 1
concluding the proof by definition of h.
C.2 Proof of the Preference-based Regret Bound Recall Corollary 5, which states
|s(f(x*) f((==))f((x))) s(ho(=" xx)) (f)))(((x)))
with high probability simultancously for all (x, x') and 2 1. For simplicity in notation in the rest of this section, we define w: x²) = 3, ( (x, x') and
LCB,( x s(1u (a, x')) )} wr( x'), UCB,(x, x²) s(h (z, x') ) + wz,
Note that (xx = wi (a', x) by the symmetry of the dueling kernel I.,. Furthermore, recall the notation h(x,)) = f(x) f(x).
Proof of Theorem 6. Step 1: First, connect the term of x in the dueling regret defined in Equation (1) to that of x;, Note that both s(f(( - f(x()) and -(f fxx)) are greater than 0.5 due to the optimality of x" and the sigmoid function is concave the interval [0.5, oc). Using the definition of concavity, we get
=(s(x)) - [(x\)) S s(((x)) - f(x:)) + - (aa)))((())))
s(f(x*) - f(zx)) + +(f(x*) f(x:))s(f(xx.) - -f(=')(((())))
h(2 x'1) s( s(f(x") - -xx)))
(15)
where the second line comes from the derivative of the sigmoid function, s(x) = s(x) - s(x)) = s(r)s(-2), and in the last line use sxx) f(x') )) < 0.5.
Using Equation (15), we can upper bound the dueling regret in Equation (1) as
2rp = s(f(x") - f(x))) + s(f((')) -faee))((xx))) f(x()) -
<s(f(x") - f(zi)) + (1 1 h(2,, x1()
s(f(x") - -f(x))) -
2
< <2s(f(x") - f(xx)) - 1 h(I x()
s(f(x") -f(xi))
(16)
2
21

---

Step 2: Next, we show that the single-step regret is bounded by wi (2 a/).
First, consider the term s(f(x)) f(x)))
=(s(x²) (xx)) 0.5 S (0<x(a" ax))
+ ( wa a²) 0.5
Corollary 5
S 0.5 (2 x²)) )) + we (a x²)
Sigmoid equality
I 2wr (
(17)
In the last inequality, we used that 2t Mr implying that 0.5 s(hs (x), S wi wi x*). Combining Equation (16) and Equation (17) implies that
2rp I 4w4 x²) M(r, mn)) s(f(x=) f(x+1)
(18)
2
Now, we bound We (a,, x²) by w x/). If x = x", then wi (2 x²) = I wr( x²).
x/= x², then the two expressions equivalent. Now, assume that æt # xx and x # xx and consider (at, x²).
Case 1: Assume that UC,, UCB 2/). Then,
2wh (ze x²) UCB, (m,, x²) [. x²)
I UCB, xx) - LCB,,(B,, x*)
I UCB, (z), x/) - LLL, (I,, x/) = 2wr x²)
(19)
where we used the assumption in the first inequality and the definition of æ in the second inequality. Case 2: Assume that UC, æ+) 2 UCB, æt). First note the following connection between LCB, and UCB,.
LC x') = s()((z,, x')) - we( x')
= 1 - s(hy(a', x)) - we wi x))
= 1 UCB:(w',
(20)
where we used the equality = 1- s(-2) in the second equality. Using Equation (20), the assumption of Case 2 can be rewritten as UCB,( x²) 2 UC xt), implying that
T./, ax) I.C,,
(21)
Similarly, (C,, x/)= S (CB, x²) implies
(C,, ox) 2 UCB,(*", wt)
(22)
Combining Equation (21) and Equation (22), we get
(x),,,,=") UCB, (x*, LCB,(x",ar
< UCB, (x", ...) LCB,(11) v3,)
S UCB, (.).,.) I.B,, ( ax)) 204((r, x()
(23)
Combining Equation (19) and Equation (23), we can
can rewrite the first term in Equation (18) to get
2r S 4wr x/) + h(x,, x!) s(f(x*) - f(xx)).
(24)
It remains to bound the second term of Equation (24). By the Mean-Value Theorem, 3z [0, h(,, x:)] such that
(=))( mi) 0) ((((x,,,)))) S(0)
Now since k = sup,58 1/5(2) then,
h(x, .t) S ((s((( ax{)) -05)
(25)
Next, we consider the term slh(,, xz)) 0.5 in Equation (25). Note that I4, at E Mr implies that
UCB,(#,, x²)) > 0.5
(1,, xx)) 2 0.5 We (x,, x.))
(26)
22

---

Additionally note that (xt, æ;) LC,, 2x) ) I 0.5. It implies that
0.5 for all 2s. therefore, by the definition of z/
(C at) S 0.5
(h1e(2 x()) S 0.5 (a a/).
(27)
From Equation (26) and Equation (27), follows that
((h4(<z,, x/)) - 0.5| - ( x/)
furthermore,
UCB,(Zz, - 0.5 = s(ha x²()) - 0.5 + wi w0 x²))
S (o (20e; xx)) - 0.5| + wx at))
v (2r, ar()
(28)
and similarly
0.5 - I.,,,(a,,,,)) S 2wr (xte x/))
(29)
From Equation (28) and Equation (29), it follows that [s(f(x;) f(x()) 0.5| < (a æ/) - 0.5, 0.5 (CB,
Corollary
< 2wl ( a1).
(30)
Combining Equation (30) with Equation (25), it follows
h( m!)) S 2nwu x!)
(31)
Using Equation (31) in Equation (24) and the fact that s (I(x")) (xx)) < 1, we get
2r D < (4 + (x) xt))
Therefore, for the cumulative dueling regret it holds
T RT = Σ
T
(n
t=1
T
$ (2+ x2+
T
(x)) vAn)
s C33PP(0) T-P
Lem. 14
with probability greater than for all 2 1.
C.3 Extending Algorithms for Linear Dueling Bandits to Kernelized Setting
Maximum Informative Pair Algorithm. Proposed in Saha [2021] for linear utilities, the MAXINP algorithm similarly maintains a set of plausible maximizer arms, and picks the pair of actions that have the largest joint uncertainty. and therefore are expected to be informative. Algorithm present the kernelized variant of this algorithm. Using Corollary 5, we can show that the kernelized MAXINP also satisfies a ((rr/T) regret.
Theorem 15. Let 8 (0, 1] and choose the exploration coefficient 3. (8) as defined in Corollary 5. Then MAXINP satisfies the anytime dueling regret guarantee of
P
VT VT 0: R C2P(() C
2 21-8
where TD is the T-step information gain of kernel ID and C2 4/ V/g((11 4(Ax)-1).
23

---

Algorithm 3 MAXINP- Kernelized Variant
Input (BP))z) (221 for / 2 do
Play the most informative pair via
Tt | = arg max of (2, x') n. a.
Observe ye and append history. Update 1 and 041 and the set of plausible maximizers
M {x X Va' X' (x,4)((xxx))))) (42 > 1/2].
end for
Proof of Theorem 15. When selecting (x,, æ²)) according to Algorithm choose the pair via
2t, ozd arg max (x a²) a.w'MM
(32)
where action space is restricted to M, and therefore,
<hh(w ax)) < 1/2 + we ( (x), <hh(w .x)) - 1/2 + we wa x")
(33)
where we have used the identity s(-2) = s(2). Simultancously for all 1, we can bound the single-step ducling regret with probability greater than 1 6
2rp s(f(x)) - f(x))) s(f(x*) f(x()) -
I <hi(a=" mx)) wi(a" (x.) sah, aa)) wo a!) -1
(w.h.p.)
s 2 (wi(x", mi) wi(a"" x/)) I xx);,
Eq. (33)
Eq. (32)
where for the first inequality have invoked Corollary 5. Then for the regret satisfies
T
RD(T) = Σ
(r
1=1
1=1
T
T Σ I =20P(0)
(o)) vdx)
Bv(8) S (8)
S C20p TTP
Lem. 14
with probability greater than 1 - for all > 1. Dueling Information Directed Sampling (IDS) Algorithm. To choose actions each iteration t. MAXINP and MAXMINLCB require solving an optimization problem on N' X. The Ducling IDS approach addresses this issue and presents algorithm which requires solving an optimization prob- lem on A' x [0, 1] and computationally more efficient when do 1. This work considers kernelized utilities, however, assumes the probability of preference itself is in an RKHS and solves kernelized ridge regression problem to estimate the probability s(h(æ, x'). In the following, we present an improved version of this algorithm, by considering the preference-based loss (6) for estimating the utility function. We modify the algorithm and the theoretical analysis to accommodate this.
Consider the sub-optimality gap A(x) h(==" x) for action X. We may estimate this gap using the reward estimate maximizer a == arg max fr(x:). Suppose we choose a; as one of the actions. Then U, shows optimistic estimate of the highest obtainable reward this step:
Ug = max f(xx,
2;) + 3.07 (x, x)).
x
where 3, is the exploration coefficient. We bound (xx) by the estimated gap
Á,(x) = u, + xx)
(34)
24

---

Algorithm 4 Preference-based IDS Kernelized Logistic Variant
Initialize Set (3t)x21 according to Theorem 2. for 1 2 do Find a greedy action via fixing any point Fuull E A and maximizing
z = ã
arg max (T, Tmult).
=EX
Update u, and (z) acc. (34).
Find an informative action and the probability of selection via
((1 ((1- p)ue + pá1 2
(2)
z Pr arg min
WEX
plog
(1
(o) (2) xz))²)
pE|0.1]
Draw a2 ~ (pr
if 04 then choose pair (æt, æ!) (ao .. 22 else choose (a2,, az) (xx)
(1) zz. )
Observe Ye and append history.
Update 1 and 0411
end for
and show its uniform validity in Lemma 17. We can now propose the Kernelized Logistic IDS algo- rithm with preference feedback in Algorithm 4, as variant of the algorithm of Kirschner and Krause.
Theorem 16. Let E (0, 1] and all 2 1, set the exploration coefficient as B (8)(8) Then Algorithm 4 satisfies the anytime cumulative dueling regret guarantee of
P (VT 00: (T) 0 (BP(8) (
+ log 1/0) 2 1 5.
Proof of Theorem 16. Our approach closely follows the proof Kirschner and Krause [2021, The- orem 1]. Let P()) show the set of continuous probability distributions expected average gap for a policy E P(X X')
domain. Define the
(a( =
2 Em Ar(x) + Ae(x')
and the expected information ratio
(7(M)
(u)
E En log (Ax) (o (oP((x xx,,,')))
Algorithm 4 draws actions via ir (1 - P0)0 (1) (e.)) + Prò (eo(ae()) ( where )(a,))) denotes Direct delta. Then by Kirschner al. [2020, Lemma 1].
(1-P))0
Σ h(w"", a.) + h"xa",""" "aa"",)/)"" s
Σ (x()) (or + O(log 1/8)) + Ollog
2
which allows us to bound the regret with probability greater than 1 - 5 as
T
RP & L
Σ E((He) (vr + O(log 1/8)) + Oo
(35)
since s(-) with its domain restricted to 1-2B, 22B2BB] is L-Lipschitz. It remains to bound Er(pc), the expected information ratio for Algorithm 4. Now by definition of /4:
(p.) (2 p. Ax + (xx
(2 p.) U4 + h (z: (1) _=x("))) (x!2)
2( - pr + pr( (x) (2)) + u.).
25

---

and similarly
Ey, log 1 of =xx,'x11" AN
1 (at ,
1 oe (00 xx. )
= (1 Pt) log
pt log
An
An
= Pp log (1+ + (Ats) 0, (m) (1)
mm (2)
(op x)) =
allowing us to re-write the expected information ratio
(2(1 pe)ue + pe (2x ue)
2,(44)
4pr log
1+ 10 xi )2)
(11 pi)u + pr.i (2))) 2
(u. S (x)))
Pt. log
11 (Ars (1x)) 10, (z/ (2) 2i 1/21/2
(1 - p)ue + p)e
min
Def. (pt, x2²)
2, plog
1 + (Ak)) -op (a, (1) x2)
(7(x))
min
Set p
log
+ (Ax))-1o (-x)" (zx ,z)3
Now consider the definition of ue and let z, denote the action for which u, is achieved, i.e. 2, arg max (1x 2;;) + (, 2;). Then
(+(z,) = h( 21) + 3,(5)oP af) + M(z,, 2/) = Be(5)oP (zx ai),
therefore using the above chain of equations we may write
i
(p()) min
log
1 1+ o+ (a) .x2)
log
1+ (Ak)) -o, (z/ (1)
=213)
log
[ (Ak))1of
(2) -x (1)
=2122)
4,7(0)
(36)
log (1 4(xx)
where last inequality holds due to the following argument. Recall that k(x, x) I 1, implying that (x, x²)² 4 and therefore log(1 + o. (x. x' 2²)²) > log (1 + (o)))))oo(p x/) similar to
Lemma 14. To conclude the proof, from (35) and (36) it holds that
(P))) L
Be(He) (vr + O
(,)
L
log (1 (1+ 41Ax))) O O
(0)
L V log (1 + 4()x)-1) (rr (1r O(log
+Olog 1/8)) + (o. T/8)
o (B) TTrrrTrrr-- + log 1/6)
with probability greater than 1 8, simultancously for all T > 1.
26

---

C.4 Helper Lemmas for Appendix C.3 Lemma 17. Let 0 d and Hy. Suppose supasB s(a) L and sup, agB 1/5(a)
Then
P(VI 0 A < (1)(2)) -
Proof of Lemma 17. Note that for any three inputs I1 22 I3
(m 2z) h (m1, x2) h (x 23).
(37)
Therefore, from the definition of the estimated gap get
(x) max h(2, (2) + hr (+ x) + (,)oo, (z,
=EX
max h(2, az) + 3,)00, (z, 2)) =EX
2 (( x)) + (6)60 (xx xx)
= ( (xx x.))
(38)
Then going back to the definition of the true gap we may write
(xx) = max (z, x)
*Ed
max (1, -t h(#; x) =E.
Eq. (37)
w.h.p.
Σ
max hi (z, ) + (e x)) + 3,(5) (2, + 0, (2 xx)
Lem. 18
#EX
44 + hi (#t x) + (5) (
Def. ue
(.) + ())))) (xt (x)
Def. A,(x)
(x)
Eq. (38)
with probability greater than
Lemma 18. Assume f E H4. Suppose supaga 1/5(a) K. Then for any 8
P P E ;:: 11(x,2') hf (x, x')l s 3.
(z, (, 2 1-
where
==) 2B + V 2 log 1/5 22
Proof of Lemma 18. This lemma effectively a weaker parallel of Corollary We have
[1(xx h2 (x. x²) = [f(x)) ) - f(x') (f((2,) (x('))
l (x. (0 0,55
S 11bb(a, x' )1 -1000 0.'1 l.'l
whp.
Lem.
< 3,(5)) (ær, / Am)
Lem. 13
where the third to last inequality holds with probability greater than 5, but the rest of the inequalities hold deterministically.
D
27

---

D Details of Experiments
1.0
MAXMINLCB
OPTIMISM
MAX INPO
0.5
0.0
(1,2)
(1.3)
(2,3) Actions: (x. x
(2.1)
(3,1)
(3,2)
True Prob.
Estimated Prob.
Confidence Set
Figure 3: Confidence sets for illustrative problem with 3 arms at single time step. Annotated arrows highlight the action selection for three common approaches. MAXMINLCB selects the action pair (1,2) with the least regret. Upper-bound maximization (OPTIMISM) and information maximization (MAX INFO) choose sub-optimal arms.
Test Environments. We use wide range of larget functions common the optimization literature [Jamil and Yang. 2013], to evaluate the robustness of MAXMINLCB. The results are reported in Table and Table Note that for the experiments we negate them all to get utilities. We use uniform grid of 100 points over their specified domains and scale the utility values to [-3.3].
Ackley: X = [-5, 5]" d =
d
1 exp
f(x) = 20 exp -0.2,
x
2 d
cos (2TT;))))) + +0 + exp(1)
d i=1
1=1
Branin: X' = [-55, 10) x [0, 15]
5.1
2
f(x) x2
+
-
- 6
10
cos(x1) 10
4T
8T
Eggholder: X = 112,, 512]2
[(x) - (I2 47) sin (v 1022 +
11 +
471
xı sin (Vlz) (x2 47))
Hölder: X' = [0100, 10j²
VoJ+ (1
f(x) = = -isin(() cis((r))os((2) exp
Matyas: X = [-10,
((x) 0.26(2² + +z²) 0.48.1102
Michalewiez: x= T] d 10
d f(x) Σ
(ix?
sin 2m
Rosenbrock: X= [-5,107
f(x) Σ
100(z.41 - x2)² + (x: - 1)2
28

---

Algorithm 5 DOUBLER [Ailon et al., 2014]
Input (221- Let L be any action from A'
for t 1 do
for jr 1......, do
Select æi uniformly randomly from C
Select 2; - arg m. s(hi(z) æ()) + (
Observe ye and append history.
Update h and D)
end for C <- the multi-set of actions played as a/ in the last for-loop over index
end for
Algorithm 6 MULTISBM [Ailon al., 2014]
Input (8P) (z21- for / 2 do
Set 2; + -/1-1
Select x = arg max s(h((z, xx)) + PPoo x.)
Observe Ye and append history.
Update h4+1 and 0f41 and the set of plausible maximizers
M (ar X Val X i(he41(a, (xr,x')) + (0 1/2].
end for
Algorithm 7 RUCB [Zoghi et al., 2014a]
Input (8P)(21- for t 2 1 do
Select æ uniformly randomly from Mr
Select x arg max s(h((x, x{)) + o &Pop (x, xt)
Observe y and append history.
Update h,41 and of41 and the set of plausible maximizers
M1+1 fxr E Va' X: (2, (x 1/2].
end for
Acquisition Function Maximization. In our computations, eliminate additional noise coming from approximate solvers, we use an exhaustive search over the domain for the action selection of LGP-UCB, MAXMINICB, and other presented algorithms. For the numerical experiments presented in this paper, we do not consider this as a practical limitation. Due to our efficient implementation in JAX, this optimization step can be carried out in parallel and seamlessly support accelerator devices such as GPUs and TPUs.
Hyper-parameters for Logistic Bandits. We set 8 0.1 for all algorithms. For GP-UCB and LGP-UCB, we set 3 = 1, and 0.25 for the noise variance. We use the Radial Basis Function (RBF) kernel and choose the variance and length scale parameters from [0.1, 1.0] to optimize their performance separately. For LGP-UCB, we tuned X. the L2 penalty coefficient in Proposition 1, on the grid [0.0, 0.1, 1.0, 5.0) and on [1.0, 2.0, 3.0). The hyper paramer selections were done for each algorithm separately to create fair comparison.
Hyper-parameters for Preference-based Bandits. We tune the same parameters of I.GP-UCH
for the preference feedhack bandit problem on the following grid: À [0, 0.1, B E 2, 3), and [0.1, 1] for the kernel variance and length scale. The same hyper-parameters are tuned separately for every baseline.
Pseudo-code for Baselines. Algorithm 5, Algorithm 6, and Algorithm described the baselines used for the benchmark of Section 6.2. MAXINP and IDS are defined in Algorithm 3 and Algorithm 4,
29

---

respectively, in Appendix C.3 alongside with their theoretical analysis. We note that DOUBLER includes an internal for-loop, therefore, we adjusted the tme-horizon T such that it observes the same number of feedback Yt as the other algorithms for a fair comparison.
Computational Resources and Costs. We ran our experiments on shared cluster equipped with various NVIDIA GPUs and AMD EPYC CPUs. Our default configuration for all experiments was a single GPU with 24 GB of memory,
CPU cores, and 16 GB RAM. Each experiment of the 11 configurations reported in Section 6.2 ran for about 12 hours and the experiment reported in Section 6. ran for hours. The total computational cost to reproduce our results around 140 hours of the default configuration. Our total computational costs including the failed experiments are estimated to 2-3 times more.
D.1 Yelp Experiment
We filter the Yelp data for restaurants in Philadelphia, USA with at least 500 reviews and users who reviewed at least 90 restaurants, The final dataset includes 275 restaurants, 20 users, and a total 2563 reviews. We define the action space X' by assigning to each restaurant their respective 32-dimensional embedding of their reviews, i.e., X' C R For each restaurant, we concatenate all reviews the filtered dataset and we use the TEXT-EEBEDDDING--LLLAA model to retrieve the embeddings. The Yelp dataset provides utility values for users in the form of ratings on the scale of to 5, however, not all users rated every restaurant. filtering estimate the missing reviews [Schafer et al., 2007]. For each user, these values used as the utilities for restaurants during the simulation. Experiments are conducted separately for each user, therefore, utility values are not aggregated but the action space is identical for each experiment.
OpenAl embedding
use collaborative
Note that we do not assume any explicit functional form of the utility functions ff that we calibrate to this data. Instead, the actions space X' and utility values derived separately from the dataset. Regardless, the results presented in Section 6.3 show that our kernelized method achieves good performance on this task.
E Additional Experiments
In this section, provide Table 2 that details our logistic bandit benchmark, complementing the results in Section 1. Figure 4 and Figure 5 show the logistic and dueling regret of additional test functions, complementing the results of Table
Table 2: Benchmarking R/e for a variety of test utility functions, 2000.
LGP-UCB
GP-UCB
IND-UCB
LOG-UCBI
Ackley
23.97 1.54
96.35 + 1.27
479.63 + 3.42
1810.30 + 0.00
Branin
75.23 17.51
44.81 2.81
142.37 1.33
1810.30 0.00
Eggholder
167.11 31.26
152.34
559.56 4.15
1041.00 0.00
Hoelder
1.0.41
426.28
105.64 = 4.88
Matyas
3..64
50.21
1
920.48 = 0.57
Michalewicz
283.85 3.66
175.46 + 2.86
166.36+3.77
1810.30 + 0.00
Rosenbrock
8.92 + 0.33
26.14 + 0.87
76.13 0.84
897.04 + 120.68
300
Regret: 124(1))
150
Regret: 110 (1')
200
100-
100
2.0
750
1.00
1250
1500
250
3.0
1000
1250
2000
Time Step:
7'
Time Step: '
IND-UCB
LGP-UCH (CP-U
MxxMMsLCCB.Orre
DOUBLER
McLTSBM
Loo-UCRI
IDS
Figure 4: Regret with Branin utility function with logistic (left) and preference (right) feedback.
'Source: http::/www.yclp.com/// com/daasset
"Source: https://plafoom.opeaaii. wwwpp/awww...ooooococeeeeeeeeiia
30

---

500
2
400
Regret: R (7)
2004
Regret: R
1604
3004
1004
604
04
250
500
1750
1000
1750
9000
250
800
750
1000
1500
1750
Step:
Time Step:
IND UCB
LGP UCB(Ours)
MAXMINLCB(OOrs)
DOUBLER
MULTESD
Lou-UCBB
GP-UCB
MAXINP
RCCB
IDS
500
400
2004
Regnet: R (2)
Regret re"(2)
150m
200-
504
230
500
750
10:0
1950
1500
1750
5000
750
800
750
1000
1250
1500
1750
200
Step:
Time Step:
DX--UC
L.G-UUCB(Oorr)
MAXAINS.CIR(Oora)
Dornn
MurmSRM
Loo-UCB1
GP-UCB
MAXINP
RCCB
IDS
125
Regret: R'(T)
Regret: RPTT)
100+
70+
60-
254
200
300
1001
11001
1250
1000
1750
2000
200
300
754
10:0
1200
1M1
1750
200
Step:
Time Step:
ISD-UCB
LGP-UCD(Oura)
MAxMMnLLCB(Oera)
DOUBLES
MULISBM
Loc UCBI
GP-UCB
MAxINP
RUCB
300
0004
Regret: (T(T)
Regret: (P(T))
2004
2004
3004
3004
230
300
750
10:0
1200
1500
1750
2000
250
800
750
1000
1250
1500
1750
2000
Time Step: 7
Time Step:
IND-UC UCB
MaXMMINL.CBB/Omma)
DOUBLES BR
MULTIBM
LoG-UBBI
GP UCB
MAXINP
100
50-
Regret: (2
Regret: (39)
St-
20-
20
250
1001
750
1300
1250
1500
1700
2000
220
1200
750
1001
1250
10.0
3750
2000
Time Step:
7'
Time Step:
7
IND-UCB
(CP)U)))(Our))
Domaan
MernSBM
LoG. UCBL
GP-UCR
MAxISP
RUCB
IDS
Figure 5: Top to bottom Regret for Eggholder, Hölder, Matyas Michalewicz, Rosenbrock functions, with logistic (left) and preference (right) feedback.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide theoretical guarantees of the proposed algorithms in Section 4 and Section 5. In Section 6, provide the results for numerical experiments supporting
claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors? Answer: [Yes]
Justification: The paper is of thcoretical nature. All theoretical assumptions are presented in the text, and we discuss how limiting they are. This is mainly in the Problem Setting section, or theorem statements.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specificatiin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
32

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Proposition I, Theorem 2, Corollary Proposition 4, Corollary 5, Theorem describe our theoretical proof' with detailed explanation of the assumptions.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We describe the experimental setting in Section while providing further details the hyperparameter selection, pseudocode, and utility function definition in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility.
33

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We include the code used to carry out the experiments in the Supplementary Material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: chiis.cc/publie htppllic/giieeeee CooeeSumiiiieeee ssicnPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide comprehensive explanations of the setting, hyperparameters, algorithms, and functions used in Section 6 and in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report all results in our figures and tables as the average and standard error over 20 random seeds.
Guidelines:
The answer NA means that the paper does not include experiments.
34

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We describe computation resources and time used for the experiments in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't ' make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttppp///arrrps..ccppbbbb/////// de ines?
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics and conducted the research following the guidelines.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
35

---

Justification:
The research presented in this paper is theoretical without any immediate societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
To the best of the authors' knowledge, there is no such risk involved.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Assets used to conduct the research presented in this paper are always cited and properly credited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
36

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
37

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "Hn9bPeXEBJ", "reviewer": "Reviewer_zRaD", "summary": "This paper considers bandit optimization with preference feedback over continuous action spaces and kernelized reward function. The goal in this problem is to minimize the dueling regret against an optimal action over a finite time-horizon. Previous works on this problem are either restricted to finite action spaces or linear reward functions. The proposed algorithm casts the problem as kernalized logistic regression and designs confidence sets for the relative preference between two actions. It then proposes an action selection strategy based on a game theoretic Leader-Follower formulation that utilizes these confidence intervals. The paper provides a regret bound as well as empirical evaluation for the proposed algorithm.", "questions": "It would be interesting to see if the current approach can be extended to other link functions beyond the sigmoid such as probit.", "limitations": "The paper can include a section of limitations of the current work in terms of social impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The main contributions of the paper are two-fold:\n\n1. Expanding the existing literature on dueling bandits by studying kernelized reward functions under infinite and continuous action sets. This requires new techniques to bound the confidence intervals. \n\n2. Proposing a principled game-theoretic approach to action selection in dueling bandits that can be of further interest.\n\nIn my opinion these are two important contributions to the literature. Since these ideas are likely to be relevant to other learning problems with preference feedback such as RLHF, I think that the results in this paper have a good scope. The paper is well-written and the contributions are clear.", "weaknesses": "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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable review and constructive suggestions. Please find below our comments on the raised questions.\n\n> 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).\n\nWe 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.**\n\nIn 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.\nIn 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.\nNonetheless, we are keen to hear if you have a suggestion on how to incorporate these algorithms into our comparisons.\n\n> It would be interesting to see if the current approach can be extended to other link functions beyond the sigmoid such as probit.\n\nThank 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,\n- monotonically increasing and symmetric around $0$, i.e., $s(x) = 1-s(-x)$ and $s(0) = 0.5$,\n- differentiable and $\\kappa = \\sup_{a \\leq B} 1/\\dot{s}(a)$ exists.\nWe 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. \n\nHowever, we have **added a remark to Section 3 and pointed out this extension**.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "MqGtV6ARVj", "reviewer": "Reviewer_Hhi1", "summary": "The paper examines the problem of bandit optimization with preference feedback in large domains and nonlinear (kernelized) rewards. It introduces MAXMINLCB, which adopts a game-theoretic approach to action selection under comparative feedback. Additionally, it proposes kernelized preference-based confidence sets, which can be utilized in related problems.", "questions": "(1) Can you implement the algorithms compared in Section 6.2 using the original confidence sets from the references?\n\n(2) Can this work be extended to contextual bandits with preference feedback?", "limitations": "Please see weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "(1) Rather than jointly selecting the arms in dueling bandits, the proposed method jointly optimizes both actions by choosing them as the equilibrium of a two-player zero-sum Stackelberg game. This approach enables a more efficient exploration/exploitation trade-off.\n\n(2) The regret guarantee presented in this paper is tighter by a factor of  $T^{1/4}$ compared to Xu et al. (2024).", "weaknesses": "(1) 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.\n\n(2) The paper lacks a comparison in the experiments with the related work by Xu et al. (2024).\n\n(3)  In real applications, it is more common to rank between two state-action pairs. However, the paper does not consider contextual information and solely focuses on the multi-armed setting, which is less interesting and useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n\n> 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.\n\nWe 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.\n\nWe 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].\n\nWe 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.\n\nWhile 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.\n\n> 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.\n\nThank you for the interesting question! We have been thinking about contextual extensions as future work. Here’s our take:\n\n1) If the context is stochastic and given by the environment, **our approach almost immediately applies**. \n\n    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*.\n\n2) 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**. \n\n    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.*\n\n\n> The paper lacks a comparison in the experiments with the related work by Xu et al. (2024).\n\nWe 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. \nOur 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. \n\n\n> Can you implement the algorithms compared in Section 6.2 using the original confidence sets from the references?\n\n\nMost 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.\n\nThe 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!\n\n---\n### References:\n\n[1] Lattimore, Tor, and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.\n\n[2] Krause, Andreas, and Cheng Ong. \"Contextual gaussian process bandit optimization.\" Advances in neural information processing systems 24 (2011).\n\n[3] Das, Nirjhar, et al. \"Active Preference Optimization for Sample Efficient RLHF.\" ICML 2024 Workshop on Theoretical Foundations of Foundation Models.\n\n[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.]", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "82qszbNQ4J", "reviewer": "Reviewer_kTTb", "summary": "This paper considers novel game-theoretic acquisition function for pairwise action selection with preference feedback. It is tailored to the setting with infinite domains and nonlinear kernelized rewards. The preference-based confidence sequences for kernelized utility functions are shown to be tight and anytime valid. The proposed algorithm MAXMINLCB is shown to satisfy a sublinear regret. Various simulations were conducted to showcase the advantage of the proposed method.", "questions": "see Weakness", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Although preference-based bandit optimization with linear utility functions is fairly well understood, such approaches cannot capture real-world problems with complex nonlinear utility functions. This paper aims to close this gap. The considered problem is timing and interesting. \n\n2. The technical contribution is non-trivial. Although there have been attempts to prove convergence of kernelized algorithms for preference-based bandits, such works employ a regression likelihood model which requires them to assume that both the utility and the probability of preference lie in an RKHS. Moreover, a sample-efficient algorithm is lacking for such approaches. In contrast, this work uses a kernelized logistic negative log-likelihood loss to infer the utility function, and provide confidence sets for its minimizer.\n\n3. Some theoretical result, like Kernelized Logistic Confidence Sequences in Theorem 2, is also of independent interest. \n\n4. In spite of a theoretical paper, it is well written and is easy to follow.", "weaknesses": "1. In practice, how to determine the hyper-parameters like $\\gamma_t$, $L$, and $B$ in (5)? Is there any data-driven way to select them?\n\n2. In the main Theorem 6, the regret bound is $\\gamma_T^{D}\\sqrt{T}$. The term $\\gamma_T^{D}$ is the T-step information gain of kernel, which is also a function of $T$. The authors claim that this rate improves that of Xu et al. (2024) by a factor of $T^{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. \n\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> In practice, how to determine the hyper-parameters like 𝛾𝑡, 𝐿, and 𝐵 in (5)? Is there any data-driven way to select them? \n\nThere are two common ways:\n- If there's enough budget for data acquisition, these can be selected via cross-validation on a small sampled pool.\n- Another approach is to create a second bandit instance on top, to optimize for these parameters [1, 2].\n\nIn 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.\n\n> 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.\nXu 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.\n\n**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:\n$$\\sqrt{\\beta_T} \\sqrt{T} = T^{3/4}\\gamma_T$$\nThis 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})$.\n\n**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!\n\n> 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.\n\nWe appreciate the observations and agree that a discussion on these results is beneficial for practitioners.\nOverall, we see MaxMinLCB as a robust choice demonstrated by its consistent performance across the wide range of optimization problems considered in our experimental results.\n\nBranin, 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.\n\nIn 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.\n\n**Figure C** in the uploaded PDF visualizes the Ackley, Matyas, and Branin functions to highlight these differences. \n\nWe 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.\n\n\nReferences\n---\n[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.\n[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "wUpA1tiYmC", "reviewer": "Reviewer_K7qo", "summary": "This paper considers bandits with preference feedback. It first constructs a novel confidence set that covers the ground truth with high probability. Then from a Stackelberg game perspective, it proposes an efficient algorithm that enjoys tighter regret bound than SOTA.", "questions": "1. In the abstract, the review claims that the regret bound is 'rate-optimal'. Is there a matching lower bound?\n2. Can the results be generalized to other link functions?\n3. In line 168, should it be $\\sup_{|a|\\leq B}$ instead of $\\sup_{a\\leq B}$?\n4. Could the authors explain the linear growth of multiSBM in Fig. 1 (b)?", "limitations": "Some major comments:\n1. 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.\n\nBesides the points mentioned above, here are some minor comments:\n1. In line 109, I guess it should be {$0, 1$} instead of $[0, 1]$.\n2. In line 178 to 179, typo in \"ridge estimator estimator\".\n3. In line 574, abuse of the notation $s$.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The technique used to construct the confidence set is interesting. The resulting confidence set is tighter.\n2. The Stackelberg game perspective is interesting, and allows the author(s) to design the algorithm with better exploration-exploitation trade-off as demonstrated in the experiment.", "weaknesses": "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]).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> 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]).\n\nWe 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.\n\nTo 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.\n\n> In the abstract, the review claims that the regret bound is 'rate-optimal'. Is there a matching lower bound?\n\nThank you for raising this question. We realize that this claim is not accurate enough, and we have now updated the abstract.\n\nThere 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*.\n\nOur 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.\n\n> Can the results be generalized to other link functions?\n\nOur theoretical analysis does in fact hold under a broader set of link functions $s: \\mathbb{R} \\to [0, 1]$ as long as $s$ is,\n- monotonically increasing and symmetric around $0$, i.e., $s(x) = 1-s(-x)$ and $s(0) = 0.5$,\n- differentiable and $\\kappa = \\sup_{a \\leq B} 1/\\dot{s}(a)$ exists.\nWe 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. \n\nHowever, we have *added a remark to Section 3 and pointed out this extension*.\n\n> In line 168, should it be $sup_{|a| \\leq B}$  instead of $sup_{a \\leq B}$?\n\nThe sigmoid function is symmetric therefore the two supremum are equivalent.\n\n> Could the authors explain the linear growth of multiSBM in Fig. 1 (b)?\n\nThank 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.\nMultiSBM 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.\n\n> 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.\n\nThe 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*. \nMultiSBM (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. \nWe kindly refer the reviewer to the general rebuttal for a further discussion on the similarities between MultiSBM, POP-BO, and MaxMinLCB.\n\n---\n### References:\n\n[1] Vakili, Sattar, Jonathan Scarlett, and Tara Javidi. \"Open problem: Tight online confidence intervals for RKHS elements.\" Conference on Learning Theory. PMLR, 2021.\n\n[2] Scarlett, Jonathan, Ilija Bogunovic, and Volkan Cevher. \"Lower bounds on regret for noisy gaussian process bandit optimization.\" Conference on Learning Theory. PMLR, 2017.\n\n[3] Lattimore, Tor. \"A lower bound for linear and kernel regression with adaptive covariates.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n[4] Pan, Rui, et al. \"ScaleBiO: Scalable Bilevel Optimization for LLM Data Reweighting.\" arXiv preprint arXiv:2406.19976 (2024).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
We thank all reviewers and chairs for their work reviewing our paper.

We are delighted to receive high-quality constructive feedback highlighting that our contributions are “clear” and our “ideas are likely to be relevant to other learning problems with preference feedback such as RLHF”. We are certain that these inputs are going to improve our work and enhance the paper’s contribution to the community.

In the following, we address questions that appear in more than one reviews, and could be valuable in a broader context.

## Connection between MaxMinLCB, MultiSBM, and POP-BO

We would like to highlight that both POP-BO[Xu et al., 2024] and MultiSBM [Ailon et al., 2014] build on the *same* ideas. These algorithms select one action $\mathbf{x}\_t$ in each time step by maximizing an optimistic estimate of the winning probability against the action chosen in the previous time step $\mathbf{x}\_{t-1}$. Then compares the actions $\mathbf{x}\_t$ and $\mathbf{x}\_{t-1}$.

Even though this connection is not mentioned in [Xu et al. 2024], the two algorithms are equivalent if used with the same confidence sets. Consequently, the results we present for MultiSBM in Section 6 carry over to POP-BO.

Additionally, we would like to note that the MaxMinLCB acquisition function can be viewed as a generalization of the above-mentioned strategies. One could formulate both POP-BO and MultiSBM as follows:

$\max\_\{\mathbf{x} \in \\{\mathbf{x}’\_{t-1} \\}\}  LCB\_{t}(\mathbf{x}, \mathbf{x}'(\mathbf{x}))$
$s.t.  \mathbf{x}'(\mathbf{x}) = \min\_\{\mathbf{x} \in \mathcal{M}_t\}  LCB\_{t}(\mathbf{x}, \mathbf{x}')$.

The main difference between this optimization problem and the MaxMinLCB defined in Eq. (7) is that domain for $\mathbf{x}\_t$ is restricted to the singleton $\mathbf{x}’\_{t-1}$ instead of $\mathcal{M}_t$, therefore, MaxMinLCB can be considered a more general acquisition function than the other two.

## Further experiments on applicability

To further demonstrate the scalability and applicability of our approach, we included preliminary results of an ongoing experiment in the uploaded PDF [**Fig A-b, Tab B** - Uploaded PDF] that provide evidence for scaling our approach to complex real-world problems. 

In this setting, we use the Yelp open dataset of restaurant reviews to learn the preferences of users and recommend restaurants. We subset the data for restaurants in Philadelphia, USA with at least 500 reviews and users who reviewed at least 90 restaurants. **The final dataset includes 275 restaurants, 20 users, and a total of 2563 reviews.**

We consider the action space of vector embeddings of the reviews for each restaurant for which we use the *text-embedding-3-large* OpenAI embedding model and have a **dimensionality of 32**. We consider each user separately and estimate their utilities for restaurants not yet reviewed using collaborative filtering.

Please note that *neither of the algorithms are tuned or modified for this experiment*. The intention on releasing pre-liminary result, is to demonstrate that 1) the computations easily scale, 2) kernelized approach is still applicable on a text-based domain. The regret result on the Yelp data, *shall be viewed as a proof-of-concept, rather than a benchmark*.

In the uploaded PDF, **Figure A-b** (right) shows that the results of this larger problem align with previous conclusions. MaxMinLCB remains the best-performing algorithm with MultiSBM following second. We included the cumulative regret in **Table B** (final row) as well. 

## Correction

Since the initial submission, we identified a minor error in the code for generating Table 1 in our paper. The conclusions drawn from these results remain unchanged. The correction slightly affected numerical values in the table but not qualitative relationships. We refer reviewers to Table B in the uploaded PDF for the corrected version of Table 1.

Meta-review: The paper studies multi-armed bandit with preference feedback under the continuous action domain and kernelized reward function. All reviewers acknowledge the novelty and technical contributions of the paper and recommend acceptance to the paper. Congratulations to the authors, and please revise the paper to address the issues raised by the reviewers, such as enriching experimental evaluations.
Decision: Accept (poster)