Neural Dueling Bandits: Preference-Based Optimization with Human Feedback
Authors: Arun Verma
Zhongxiang Dai
Xiaoqiang Lin
Patrick Jaillet
Bryan Kian Hsiang Low
Venue: ICLR 2025 Poster (2025)
Keywords: Contextual Dueling Bandits
Preferences Learning
Human Feedback
Neural Bandits
Thompson Sampling
Primary area: reinforcement learning
TL;DR: We study contextual dueling bandits problem and propose upper confidence bound- and Thompson sampling-based algorithms that use a neural network to estimate the reward function using human preference feedback and have sub-linear regret guarantees.

Abstract: Contextual dueling bandit is used to model the bandit problems, where a learner's goal is to find the best arm for a given context using observed noisy human preference feedback over the selected arms for the past contexts. However, existing algorithms assume the reward function is linear, which can be complex and non-linear in many real-life applications like online recommendations or ranking web search results. To overcome this challenge, we use a neural network to estimate the reward function using preference feedback for the previously selected arms. We propose upper confidence bound- and Thompson sampling-based algorithms with sub-linear regret guarantees that efficiently select arms in each round. We also extend our theoretical results to contextual bandit problems with binary feedback, which is in itself a non-trivial contribution. Experimental results on the problem instances derived from synthetic datasets corroborate our theoretical results.

Published as a conference paper at ICLR 2025
NEURAL DUELING BANDITS: PREFERENCE-BASED OPTIMIZATION WITH HUMAN FEEDBACK
Arun Verma' Zhongxiang Dai Xiaoqiang Lin
Patrick Jaillet', Bryan Kian Hsiang Low
1 SSngaapore-Mi Alliance for Research and Technology, Republic of Singapore
"The Chinese University of Hong Kong, Shenzhen, China
3 DDepartment of Computer Science, National University of Singapore, Republic of Singapore
LLIDS and EECS, Massachusetts Institute of Technology, USA
aunn ve rma sma rt. mi t..t.... edu, da i zwoogoooniiinn ange cuhk edu xi xiaoqiang lin@u. nus edu, Faillet@mit.cm 1owkh&comp nus edu.
ABSTRACT
Contextual dueling bandit is used to model the bandit problems, where a learner's goal is to find the best arm for given context using observed noisy human preference feedback over the selected arms for the past contexts. However, existing algorithms assume the reward function is linear, which non-linear in many real-life applications like online recommendations or ranking web search results. To overcome this challenge, we use neural network estimate the reward function using preference feedback for the previously selected arms. We propose upper confidence bound- and Thompson sampling-base -ased algorithms with sub-linear regret guarantees that efficiently select arms in each round. We also extend our theoretical results to contextual bandit problems with binary feedback, which is in itself non-trivial contribution. Experimental results on the problem instances derived from synthetic datasets corroborate our theoretical results.
be complex and
INTRODUCTION
Contextual dueling bandits (or preference-baset bandits) (Saha, 2021; Bengs et al., 2022; Li et al., 2024) is a sequential decision maasionnmaaing framework that is widely used to model the contextual bandit problems (Li et al., 2010; Chu et al., 201 1; Krause & Ong, 2011: Zhou et al., 2020; Zhang al., 2021) in which a learner's goal is to find an optimal arm by sequentially selecting a pair of arms (also refers duel) and then observing noisy human preference feedback (i.e., one arm is preferred over another) for the selected arms. Contextual dueling bandits has many real-life applications, such online recommendation ranking web search, fine-tuning large language models, and rating two restaurants or movies, especially in the applications where it is easier to observe human preference between two options (arms) than knowing the absolute reward for the selected option (arm). The preference feedback between two arms' is often assumed to follow the Bradley-Terry-LLe model (Hunter, 2004; Luce, 2005; Saha, 2021; Bengs al., 2022; Li al., 2024) in which the probability of preferring an arm is proportional to the exponential of its reward.
(BTL.
Since the number of contexts (e.g., users of online platforms) and arms (e.g., movies/search results to recommend) can be very large (or infinite), the reward of an arm is assumed to be parameterized by an unknown function, e.g., a linear function (Saha, 2021: Bengs et al., 2022; Li et al., 2024). However, the reward function may not always be linear in practice. To overcome this challenge, this paper parameterizes the reward function via a non-linear function, which needs to be estimated using the available preference feedback for selected arms. To achieve this, non-linear function by using either a Gaussian processes (Williams & Rasmussen, 2006; Srinivas al., 2010; Chowdhury & Gopalan, 2017) neural network (Zhou et al., 2020; Zhang al., 2021). However, due to the limited expressive power of the Gaussian processes, it fails when optimizing
estimate the
"quual contribution and corresponding authors.
For more than two arms, the preferences assumed to follow the Plackett-Luue model (Saha, 2021; Soufiani et al., 2014).

---

Published as a conference paper at ICLR 2025
highly complex functions. In contrast, neural networks (NNs) possess strong expressive power and can model highly complex functions (Dai et al., 2023; Lin et al., 2023).
In this paper, we first introduce the problem setting of neural dueling bandits, in which we use neural network to model the unknown reward function in contextual ducling bandits. As compared to the existing work neural contextual bandits (Zhou al., 2020; Zhang et al., 2021), we have to use cross-entropy loss as an objective function for training the neural network to estimate the unknown non-linear reward function due to the preference feedback (i.e., 0/1). We next propose two neural dueling bandit algorithms based on, respectively, upper confidence bound (UCB) (Auer et al., 2002; Li al., 2010; Chu et al., 2011: Abbasi- Yadkori et al., 2011; Li et al., 2017; Zhou et al., 2020) and Thompson sampling (TS) (Krause & Ong, 2011: Agrawal & Goyal, 201 Chowdhury & Gopalan, 2017: Zhang et al., 2021) (more details are in Section 3.2). Note that the existing contextual dueling bandit works (Saha, 2021; Bengs et al., 2022; Li et al., 2024) use different ways to select the pair of arms (more details are given in Appendix C.2), hence leading to different arm-selection strategies as compared to our work. Due to the differences in arm-sclection strategy and reward function (which is non-linear and estimated using NNs), our regret analysis is also completely different.
Furthermore, existing neural contextual bandit works use root mean square error (RMSE) as an objective function for training the neural networks due to the assumption of real-valued reward or feedback. Therefore, their key results, especially the confidence ellipsoid, only hold for RMSE and can not be straightforwardly extended to our setting, which uses cross-entropy loss. Nevertheless, derive an upper bound on the estimation error (i.e., represented difference between the reward values of any pair of arms (Theorem 1) predicted by the trained neural network, which is valid as long as the neural network sufficiently wide. This result provides theoretical assurance of the quality of our trained neural network using the preference feedback to minimize the cross-entropy loss. Based on the theoretical guarantee on the estimation error, we derive upper bounds on the cumulative regret of both of our algorithms (Theorem 2 and Theorem 3). which are sub-linear under some mild conditions. Our regret upper bounds lead to several interesting and novel insights (more details are given in Section 3.3).
confidence ellipsoid) of the
As special case, we extend our results to neural contextual bandit problems with binary feedback in Appendix D, which is itself of independent interest. Interestingly, our theoretical results also provide novel theoretical insights regarding the reinforcement learning with human feedback (RLHF) algorithm (Appendix E). Specifically, our Theorem 1 naturally provides a theoretical guarantee on the quality of the learned reward model in terms of its accuracy in estimating the reward differences between pairs of responses. Finally, we empirically validate the different performance aspects of our proposed algorithms in Section 5 using problem instances derived from synthetic datasets.
2 PROBLEM SETTING
Contextual dueling bandits. We consider a contextual dueling bandit problem in which a learner selects two arms (also refers as a duel) for given context and observes preference feedback over selected arms. The learner's 's goal is to find the best arm for each context. Our problem differs from standard contextual bandits in which a learner selects single arm and observes an absolute numerical reward for that arm. Let C C Rdd be the context set and A C IRd be finite arm set, where d, 2 1 and d, 2 1. At the beginning of round f, the environment generates context e2 E C and the learner selects two arms (i.e., 1,,1, and at,2) from the finite arm set A. After selecting two arms, the learner observes stochastic preference feedback y for the selected arms, where y1 1 implies the arm a,, is preferred over arm 422 and y/2 = 0 otherwise. We assume that the preference feedback depends on an unknown non-linear reward function f : C x A - R. For brevity, context-arm feature vectors in the round t by X, We also use X' to denote the set of all feature vectors: X, C X, Vt and Tt to represent the context-arm feature vector for context e and an arm a.
denote the set of all
Stochastic preference model. We assume the preference has a Bernoulli distribution that follows (BTL) model (Hunter, 2004; Luce, 2005), which is commonly used in the dueling bandits (Saha, 2021; Bengs et al., 2022; Li et al., 2024). Under the BTL preference model, the probability that the first selected arm (œx,1) is preferred over the second selected arm (2x.2 for the the given context e and latent reward function f is given by
the Bradley-Terry-Lee
exp (fxr,))
P (Ir,1 > x4,23 = TP [yv = 1 (1,2) =
exp (f(x1))) + exp (f(11)) = (f(())))) - f(x,2))
2

---

Published as a conference paper at ICLR 2025
where Fe.1 > F2,2 denotes that F1,1 is preferred over 21,2, ju(z) = =1/(1e==)) is the sigmoid function and f(x2,s) is the latent reward of the i-th selected arm. Our results hold for other preference models like the Churstone-Mostellee model and Exponential Noise as long as the stochastic transitivity holds (Bengs et al., 2022). To generalize our results across preference models, we make the following assumptions on function μr (also known link function (Li et al., 2017; Bengs al., 2022)):
Assumption 1.
f(x')) > 0 for all pairs of context-arm. TThe link function jr R + [0, 1] is continuously differentiable and Lipschitz. with constant Lyg For sigmoid function, Lp S 1/4.
Kip = x (=((()) ix((()
Performance measure. After selecting two arms, denoted by Tt and 2t,2, in round t, the learner incurs instantaneous regret. There are common notions of instantaneous regret in the dueling bandits setting (Saha, 2021; Bengs et al., 2022; Li et al., 2024), i.e., average instantancous regret: re = f(xī) - (f(=,1)+ f(x:2)) /2, and weak instantaneous regret: r!" = fxz]) max (f(,),), f f((22)) where x = argınax f(x) denotes the best arm for given context that maximizes the value of the underlying reward function. After observing preference feedback for T pairs of arms, the cumulative regrer (or regret, in short) of a sequential policy is
given by R. > r7, where = {a, w}. Note that Ry < Rg Any good policy should have sub-linear regret, i.c., lim / T = 0. A policy with a sub-linear regret implics that the policy will eventually find the best arm and recommend only the best arm in the duel for the given contexts.
NEURAL DUELING BANDITS
Having good reward function estimator is the key for any contextual bandit algorithm to achieve good performance, i.e., smaller regret. As the underlying reward function is complex and -ineereer, we use fully connected neural networks (Zhou et al., 2020; Zhang et al., 2021) to estimate the reward function only using the preference feedback. Using this estimated reward function, we propose two algorithms based on the UCB and TS with sub-linear regret guarantees.
3.1 REWARD FUNCTION ESTIMATION USING NEURAL NETWORK
To estimate the unknown reward function f. we use fully connected neural network (NN) with depth L 2 2, the width of hidden layer m, and ReLU activations as done in Zhou al. (2020) and Zhang et al. (2021). Let h(r; 0) represent the output of a full-connected neural network with parameters 0 for context-arm feature vector x, which is defined follows:
Mx:; 0) Wr, Wr,Rel ReLU (W, L-1 (... ReLU (W w2)))
where ReLU(xx) = max (r, 0}. Wi E Rmxxd W, E Rmxm for S < L, W. E RM1 We denote the parameters of NN by 0 = (vec (Wi); :.. vec (W L)), where vec (A) converts M x N matrix A into a .M N- -dmmensioonll vector. We use m to denote the width of every layer of the NN, use p to represent the total number of NN parameters, i..., p dm + m2 1) m, and use g(:; 0) to denote the gradient of (x;; 0) with respect to 0.
The arms selected by the learner for context received in round is denoted by 1..1 E X, and the observed stochastic preference feedback is denoted by ys = 1(x,,1 > 22,2), which is equal to the arm F,, is preferred over the arm x,,2 and 0 otherwise. At the beginning of round i, we use the current history of observations {(T,,1 22 ya)] to train the neural network (NN) using gradient descent to minimize the following loss function:
C((
- m Σ
1 1-1
1 log p ((-1)2-v- - + 2 110 60ll2
(I)
Here Og represents the initial parameters of the NN, and we initialize Og following the standard practice of neural bandits (Zhou et al., 2020; Zhang et al., 2021) (refer to Algorithm 1 in Zhang et al. (2021) for details). Here, minimizing the first term in the loss function (i.e., the term involving the summation from t 1 terms) corresponds to the maximum log likelihood estimate (MLE) of the parameters 0. Next, we develop algorithms that use the trained NN with parameter 9, to select the best arms (duel) for each context.
3

---

Published as a conference paper at ICLR 2025
3.2 NEURAL DUELING BANDIT ALGORITTMM
With the trained NN as an estimate for the unknown reward function, the learner has to decide which two arms (or duel) must be selected for the subsequent contexts. We UCB- and TS-based algorithms that handle the exploration-eexllitttion trade-off efficiently.
UCB-based algorithm. Using upper confidence bound for dealing with the exploration-exploiatioo trade-off is common in many sequential decision-making problems (Bengs et al., 2022; Zhou et al., 2020; Auer al., 2002). We propose UCB- algorithm named NDB-UCB, which works as follows: At the beginning of the round f, the algorithm trains the NN using available observations. After receiving the context, selects the first arm greedily (i.e., by maximizing the output of the trained NN with parameter 0,) as follows:
Ft arg max (ax;; =EX,
Next, the second arm 2, is selected optimistically, i... by maximizing the UCB value:
NDB-UCB Algorithm for Neural Dueling Bandit based on Upper Confidence Bound
Tuning parameters: 5 E (0, 1), O, and m >
2: for / = 1,...,7 , do
3: Train the NN using {I (4, (a)) e=1 by minimizing the loss function defined in Eq. (I)
4: Receive a context and Xr denotes the corresponding context-arm feature vectors
5: Select 21,1 arg max h(2; 0/) given in Eq. (2))
6: Select 24,2 = arg max,ex, [h(x;; 8.) + Vr 2+,1)l (as given in Eq. (3))
7: Observe preference feedback ye (1.1)))2))
8: end for
24,2 = arg max [h(2;; 0z) + UTO:-1 (1,1) SEXt
where UT (BT BB A/K 1)Vkk// wn/A in which B7 - V log((18) and d is the effective dimension. We define the effective dimension in Section 3.3 (see Eq. (4)). We define
A 1 (((x1) (2(x2))
of (21,
Kip
vm
V=
where V (Z.))
AL Here, (x(x)) = ((F,,,)) - ((x,,2) = ((x,,1:0))
g(as.22 06) and g(z; 06)0 / is used as the random features approximation for context-arm feature vector x. Intuitively, after the first Ft, is selected, larger (1, indicates that is very different from Ie,1 given the information of the previously selected pairs of arms. Hence, the second term in Eq. (3) encourages the second selected arm to be different from the first arm.
TS-based algorithm. Thompson sampling (Li et al., 2024; Agrawal & Goyal, 2013b) selects an arm according to its probability being the best. Many works (Li al., 2024; Chowdhury Gopalan, 2017; Agrawal & Goyal, 2013b; Chapelle & Li, 2011) have shown that TS is empirically superior than to counterpart UCB-based bandit algorithms. Therefore, in addition, we also propose another algorithm based on TS named NDB-TS, which works similarly to NDB-UCB except that the second arm 24 is selected differently. To select the second arm Tt,2, for every arm æ E X₁, it firstly samples a reward r=(x)) ~ N (h(1;;0) - h( 0,), arm F4,2 = arg max
2))1)) and then selects the second
3.3 REGRET ANALYSIS
Let K denote the finite number of available arms in each round, H denote the NTK matrix for all
x K context-an arm feature vectors in the T rounds, and = (f(=l)..... fx f.. )). The NTK matrix H definition is adapted our setting from Definition 4.1 of Zhou al. (2020). We denote the j-th element of the vector x by z,. We now introduce the assumptions needed for our regret analysis, all of which standard assumptions in neural bandits Zhou et al. (2020); Zhang et al. (2021).
4

---

Published as a conference paper at ICLR 2025
Assumption 2. Without loss of generality, assume that
the reward function is bounded: [f(x)] $ V1 E &. [T].
there exists Ào > 0 s.t. H = Aul, and
all context-arm context-armeeaturee vectors satisfy || = 1 and x, = Ij44/2 Vx E X, Vt E [T].
The last assumption in Assumption 2 above, together with the way we initialize fo (i.e., following standard practice neural bandits Zhou al. (2020); Zhang et al. (2021)), ensures that h(:; 0b) 0, Vx E X, Vt [T]. The assumption of x = //+///2 is mild assumption and commonly used in the neural bandits literature Zhou et al. (2020); Zhang et al. (2021). This assumption is just for convenience in regret analysis: for any context x, ||x]| 1, we can always construct new context x' = (x x T)T/ /v2 that satisfies this assumption Zhou et al. (2020).
Let = E Euneecy ()) m in which 2)( = (((..)) - ((x,,)) and C denotes
all pairwise combinations of K arms. We now define the effective dimension as follows:
d logog
Kig (x II).
Compared to the previous works on neural bandits, our definition of d features extra dependencies on Kip- Moreover, our H' contains T x K x (K - 1) contexts, which is more than the T x K contexts of Zhou et al. (2020) and Zhang et al. (2021).² Hence, our d is expected to be larger than their standard effective dimension. It follows from the Determinant-Trasn Inequality (Lemma 10 of Abbasi Yadkori et al. (2011)), the determinant of a covariance matrix in directly proportional the number of feature vectors. In our setting, the effective dimension d is log det ("x H' + +I) and H' contains T K x (K - 1) contexts (i.e., feature vectors), which is more than the x contexts in the standard neural bandits. Therefore, the effective dimension d in the neural dueling bandits is larger than that of the standard neural bandits.
Note that placing an assumption on d above analogous to the assumption on the eigenvalue of the matrix M, in the work on linear dueling bandits Bengs et al. (2022). For example, in order for our final regret bound be sub-linear, we only need assume that d = ö( (VT)), which is analogous to X-1/2 the assumption from Bengs et al. (2022): Σ > (M, S cVT..
We use the above fact to prove our following result, which is equivalent to the confidence ellipsoid results used in the existing bandit algorithms (Li et al., 2017).
Theorem 1. Let 5 E 1), e/mt = C2m-1/6 Vlog 3 (+) 4/3 for some absolute constant C2 0. As long as 2 poly(TT, L, K, 1/Kpr Lus 1/>0, 1/X, log(1 (/6)), then with probability of at least - 8,
[1[(x) - f(x')] - (1(x;; 0c) h(z':0.)) S (TT + 2
for all x, E N, E [T].
The detailed proof of Theorem I and all other missing proofs are given in the Appendix. Note that as long as the width m of the NN is large enough (i.e., if the conditions on m in (8) are satisfied), we have that e'm,, = (1/T). Theorem ensures that when using our trained NN h to estimate the latent reward function f. the estimation error of the reward difference between any pair of arms is upper-bounded. Of note, it is reasonable that our confidence ellipsoid in Theorem is in terms of the difference between reward values, because the only observations we receive are pairwise comparisons. Now, we state the regret upper bounds of our proposed algorithms.
Theorem 2 (NDB-UCB), Let À > Ky. B be constant such that 22h H < B, and co > 0 be absolute constant such that 1 [|(p(z) p(x'))1 co. x' E X,,t [T]. For m 2 m poly(T, L, K, 1/Kips L,s 1/20, 1/2, log (1/5). then with probability of at least 1 - ō, we have
Ri < 2
3 B1 + B V
Ku +1)
X
T2oud (122od+1=10 +1
(
Vā Kgp
A
v
Td
Kpp
2 The effective dimension in Zhou et al. (2020) and Zhang al. (2021) is defined using H: d log det (H/A T) /ooo/ol((]]))) However, it of the same order (up log factors) as log det H + 1).
with म = E. Σx, g( (0) 00)" /mm (see Lemma B.7 of Zhang al. (2021)).
5

---

Published as a conference paper at ICLR 2025
The detailed requirements the width m of the NN are given by Eq. (8) in Appendix A. Theorem 3 (NDB-TS). Let ej and 02 be two constants. Under the same conditions as those in Theorem 2, then with probability of at least 1 - 6, we have
(1
[vaa + B Kp
Vā
Ry =
VTd
Kip
Note that in terms of asymptotic dependencies (ignoring the log factors), our UCB- and TS- algorithms have the same growth rates. The upper regret bounds also hold for weak cumulative regret as is upper-bounded by average cumulative regret.
When we assume that the effective dimension d= Ō(vT(T (which is analogous to the assumption on the minimum cigenvalue from Bengs et al. (2022)), then the regret upper bounds for both NDB-UCB and NDB-TS are sub-linear. The dependence of our regret bounds on and E (i.e., the parameters of the link function defined Assumption 1) are consistent with the previous works on generalized linear bandits (Li al., 2017) and linear dueling bandits Bengs et al. (2022).
Compared with the regret upper bounds of NeuralUCB Zhou et al. (2020) and NeuralTSS Zhang et al. (2021), the effective dimension d in Theorem 2 and Theorem are expected to be larger than the effective dimension d' from Zhou et al. (2020); Zhang et al. (2021) because our d results from significantly larger number of contexts. Therefore, our regret upper bounds (Theorem 2 and Theorem 3) expected to be worse than that of Zhou et al. (2020); Zhang et al. (2021): Õ VT). This downside can be attributed to the difficulty of our neural ducling bandits setting, in which we can only access preference feedback.
the summation
3.4 PROOF SKETCH
In this section, we give brief proof sketch of our regret analysis in Section 3.3.
3.4.1 SKETCH OF PROOF FOR THEOREM
We start by presenting outline for the proof of our Theorem 1. To begin with, by applying the theory the NTK (Jacot et al., 2018) to our NN for reward estimation (Section 3.1), we show that as long as the NN is wide enough, its output can be approximated by linear function (see Appendix A. for details). More specifically, for a pair of arms x and x', the difference between their predicted latent reward values (x:; 0.) h(x;; 0,) can be approximated by the difference between the linear approximations of the NN:
Lemma 1. Let E'm,t A C2m 1/6 Vlogmm mL (4) 4/3 where C2 is an absolute constant. Then ((p(z) - ((x'), O, 0o) (h(r;0) - ((z(00;)) s 2 25'm,t> Vt E (T),,, E X.
Of note, the approximation error eim,, becomes smaller the width of the NN is increased.
Proof the Confidence Ellipsoid. Next, we derive the confidence ellipsoid for our algorithms, which is formalized by Lemma 6 (see its detailed proof in Appendix A.2). Lemma 6 allows to derive the following incquality, which shows that for a pair of arms x and x', the difference between their latent reward values f(x) f(x') can be approximated by the difference between their predicted values by the linearized NN:
((()) Go)l | (p(xx) ,(x')) (=())))((())))
Br + B
Kips +
(5)
Importantly, Eq. (5) guarantees that our trained NN with parameters 0, (after linearization) is an accurate approximation of the latent reward function f in terms of pairwise differences. This crucial theoretical guarantee is achieved thanks our carefully designed loss function Eq. (1). Specifically, a key step in the proof of our confidence ellipsoid (i.e., Lemma 6) is the following equality:
(a (h(x),1;0,) - hax,,; 0z)) ys) (g(x.,100) - g(r..2; 0,)) ) + A(0, -06) = 0, (6)

---

Published as a conference paper at ICLR 2025
which is achieved by obtaining the NN parameters 9e by minimizing loss function Eq. (1). This is, in fact, analogous to using maximum likelihood to estimate the unknown vector in the linear reward function in linear ducling bandits (Bengs et al., 2022) and linear bandits with binary feedback (Li et al., 2017). In addition, another important step in the proof of Lemma 6 is the recognition that the observation noise &t y/ [u[ (1),,) / (2),,2) is conditionally
(more details can be found in the proof of Lemma 8 in Appendix A.2). After the proof of the confidence ellipsoid as described above, we then combine Eq. (5) and Lemma to derive an upper bound on the difference
between fz) faz) and h(x; 8e) h(z'; which completes the proof of Theorem 1.
3.4.2 SKETCH OF PROOF FOR THEOREM AND THEORRM
To obtain a regret upper bound for the NDB-UCB algorithm (i.e., to prove Theorem 2). we firstly use Theorem I to derive upper bound on the average instantaneous regret r f(xt) - (f(1))) + f(x4,22) /2 (see the detailed proof in Appendix A.3):
Fi o ( + 35m
r $ 2
Br +
B
Kpp
Our strategies to select the two arms 21,1 and 2i,2 (i.e., Eq. (2) and Eq. (3)) are essential for deriving the upper bound in Eq. (7). Subsequently, we follow similar steps to the analysis of the kernelized bandit algorithms (e.g., GP-UCB (Srinivas et al., 2010)) to obtain an upper bound on Ei=1 0=1 (e,2) in terms of d. This then provides with an upper bound the average regret Rg. = - r2. (as well as the weak regret Ry since Ny < Ri)) and hence completes the proof Theorem 2. The proof of Theorem 3 for the NDB-TS algorithm is also based on Theorem 1 and largely follows from the analysis of the GP-TS algorithm (Chowdhury & Gopalan, 2017). However, non-trivial modifications need be made in order incorporate our strategies to select the two arms It,1 and Zt,2- The detailed regret analysis for Theorem 2 and Theorem can be found in Appendix A.3 and Appendix B, respectively.
FURTHER IMPLICATIONS OF OUR ALGORIHTMMS AND THEORY
Our results to learn the latent non-linear reward function using preference feedback is not only limited to dueling bandits, but it can be adapted to other settings as discussed in the following sections.
4.1 NEURAL CONTEXTUAL BANDITS WITH BINARY FEEDBACK
In many real-world applications, the learner can only observe binary feedback, e-g., whether user clicks in an online recommendation system or whether treatment is effective in clinical trials, and these problems are commonly modeled as contextual GLM bandits (Filippi et al., 2010; Li et al., 2017; Faury et al., 2020), which assume the probability of success (i.e., 1) is proportional to exponential of its reward that a linear function of action-context features. However, in many real-life applications, the reward can be non-linear function of action-context features, which modeled using suitable neural network. We refer to this problem as neural contextual bandits with binary feedback. Therefore, our results can be extended to the neural contextual bandit problem, where the learner only receives binary feedback for the selected arms, which depends on the non-linear reward function. This adaption not straightffrward as the learner selects only one arm and observes binary feedback (success or failure) for the selected action. This difference leads to different arm selection strategies as only one needs to be selected in neural contextual bandits, and different loss functions must be optimized to train the neural network to estimate the unknown reward functions. The main challenge derive the confidence ellipsoid result, which a crucial component for proving the regret bounds. While some ideas are common, the derivations differ due to the underlying differences in the problem settings. We have given more details of the neural contextual bandit with binary feedback problem and our regret bounds of algorithms proposed for this setting in Appendix D.
4.2 REINFORCEMENT LEARNING FROM HUMAN FEEDBACK
Our algorithms and theoretical results can also provide insights on the celebrated reinforcement learning with human feedback (RIHF) algorithm (Chaudhari et al., 2024), which has been the most
7

---

Published as a conference paper at ICLR 2025
widely used method for aligning large language models (LLMs). Firstly, our Theorem provides a theoretical guarantee on the quality of the learned reward model during RLHF This is because Theorem 1 serves an upper bound on the estimation error of the estimated reward differences between any pair of prompts. Secondly, our proposed algorithms can be used to improve the quality of the human preference dataset for RL.F. That is when collecting the dataset for RLHF, we can let the LLM generate a large number of responses, from which we can use our algorithms for neural dueling bandits to select two responses (corresponding to two arms) be shown to the user for preference feedback. More details can be found in Appendix E.
5 EXPERIMENTS
To corroborate our theoretical results, we empirically demonstrate the performance of our proposed algorithms on different synthetic reward functions. We adopt the following two synthetic functions from earlier work neural bandits (Zhou et al., 2020; Zhang al., 2021; Dai et al., 2023): f(z) 10(x 0)² (Square) and (xx = cos(3x 0) (Cosine). We repeat all our experiments 20 times and show the average and weak cumulative regret with 95% confidence interval (represented by the vertical line on each curve) Due to space constraints, additional results are given in the Appendix C.
The details of our experiments features of each context-arm pair. We denote the context-arm feature vector for context & and arm by zi. where za (xi,a....,, 24,a), V L 2 1. The value of i-the element of xg vector is sampled uniformly at random from (-, Note that the number of arms remains the same across the rounds, i.c., K. We then select a d-dimensional vector 0 by sampling uniformly at random from (-1, 1)d In all our experiments. the binary preference feedback about 21 being preferred over Z2 (or binary feedback in Appendix D) is sampled from a Bernoulli distribution (x2))). In all our experiments, we use a NN with 2 hidden layers with width 50, À = 1.0, ā = 0.05, d = 5, K = 5, and fixed value of DT having a fair comparison, we choose the value of after doing hyperparameter search over set {10.0, 5.0, 1.0, 0.1, 0.01, 0.001, 0.0} for linear baselines, i.e., LinDB-UCB and LinDB-TS. As shown in Fig. I, the average cumulative regret is minimum for y = 1.0. Note that we did not perform any hyperparameter search for NDB-UCB and NDB-TS, whose performance can be further improved by doing the hyperparameter search
follows: We use d-dimensional space to generate the sample
with parameter p = μ (f
= 1.0. For
Cumaaat Regest devergge
8000-
Lege 11
2010 2407
jum Thy 180
1606370 5.0
LEOD-UCER 1.4
Lice-Uck
U100-153 0.11
Lindo
L-00 ucik 201)
0001
UniO 2801)
200
450
68)
530
1030
202
B3) 1990
Raunds
Rounde
(a) Square (UCB)
(b) Square (TS)
(c) Cosine (UCB)
(d) Cosine (TS)
Figure I: Average cumulative regret of LinDB-UCB and LinDB-TS vs. different values of v for Square reward function (i.e., 10(x 0)²).
As supported by the neural tangent kernel (NTK) theory, we can substitute the initial gradient g(z; 0b) for the original feature vector x as (x;; 0b) represents the random Fourier features for the NTK Jacot al. (2018). In this paper, use the feature vectors g(x; 0.) instead of (x;; 06) and recompute all g(x; 0.) in each round for all past context-arm pairs. Additionally, compared to NTK theory, we have designed our algorithm be more practical by adhering the common practices in neural bandits Zhou et al. (2020); Zhang et al. (2021). Specifically, in the loss function for training our NN (as defined in Eq. (1)), we replaced the theoretical regularization parameter 1m l|e lol12 (where m is the width of the NN) with the simpler > ||01|2- Similarly, for the random features of the NTK, we replaced the theoretical g(;; 0t) with g (x;; 0.). We retrain the NN after every 20 rounds and set the number of gradient steps to 50 in all our experiments.
Regret comparison with baselines. We compare regret (average/weak of our proposed algorithms with three baselines: LinDB-UCB (adapted from (Saha, 2021)), LinDB- B-DD,,,SaaA and CoLSTIM (Bengs et al., 2022). LinDB-UCB and LinDB-TS can be treated variants of NDB-UCB and NDB-TS.
8

---

Published as a conference paper at ICLR 2025
respectively, in which a linear function approximates the reward function. As expected, NDB-UCB and NDB-TS outperform all linear baselines as these algorithms cannot estimate the non-lineat reward function and hence incur linear regret. For fair comparison, LinDB-UCB and LinDB-TS (see Fig. 1) for NDB-UCB and NDB-TS. We observe the same trend for different non-linear reward functions (see Fig. 5 and Fig. 6 in Appendix C) and also for neural contextual bandit with binary feedback (see Fig, 7 in Appendix D).
used the best hyperparameters of
Cumuaatre Rogret laveagee
Lino MAC CccSTI
1.300
CARTRAAIOON Roqjed CONDD
L8000 CALSTER STLSTR
1202
1503
CaL ALLTTM
1000
Cu
2000
190
1503
Bourds
RoUTIS
Boonnss
Square (Average)
(b) Square (Weak)
(c) Cosine (Average)
(d) Cosine (Weak)
Figure 2: Comparisons of cumulative regret (average and weak) of different dueling bandits algorithms for non-linear reward functions: Square (10(x' T))² and Cosine (cos(3r' Q)).
Varying dimension and arms regret Increasing the number of arms (K) and the dimension
of the context-arm feature vectors (d) makes the problem more difficult. To see how increasing K and d affects the regret of our proposed algorithms, = (5, 10, 15, 20, 25} while keeping the other problem parameters constant. As expected, the regret of NDB-UCB increases with iecrasse in K and as shown in Fig. We also observe the same behavior for NDB-TS as shown Fig. 4. All missing figures from this section are in the Appendix C.
vary the K {5, 10, 15, 20, 25) and
Cumraat Regret taverage)
5003
LOB
MEB UCB 31
LDO
3007
sobrqua
Curv LOVe. Rogged
NOO-LCE up
sebeesa 201
1922
420
600
060
1030
300
480
966
1030
(a) Varying K (Average) (b) Varying K (Wcak)
(c) Varying d (Average)
(d) Varying d (Weak)
Figure 3: Cumulative regret (average and weak) of NDB-UCB vs. different number of arms (K) and
dimension of the context-arm feature vector (d) for Square reward function (i.e., 10(x T))3).
17300
30030
15D-15 10 30
11/00
Cumuutue Bopee
185-15 22-
10000
628-15
CLAV Dt0 Megurtt
9003
75.0
1500
30000
330
689
1890
400
800
1000
(a) Varying d (Average)
(b) Varying d (Weak)
(c) Varying K (Average)
(d) Varying K (Weak)
Figure 4: Cumulative regret (average and weak) of NDB-TS vs. different number of arms (K) and dimension of the context-arm feature vector (d) for Square reward function (i.e., 10(x 0))2).
Practical challenges. Applying algorithms in scenarios requiring fast online interactions can be challenging for two reasons: updating the neural network (NN) and the arm-selection strategy. To address the first challenge, can batched version of our algorithm, where the NN is updated only after a fixed interval. To address the second challenge, we can use an & Er-greddy method for selecting arms when computing optimistic values using UCB TS is not computationally feasible.
Computational resources used for all experiments. All the experiments are run on a server with AMD EPYC 7543 32-Core Processor, 256GB RAM, and GeForce RTX 3080.

---

Published as a conference paper at ICLR 2025
6 RELATED WORK
We now review the relevant work, especially in dueling bandits and contextual bandits, to our problem.
Finite-Armed Dueling Bandits. Learning from pairwise or K-wise comparisons has been thoroughly explored in the literature. In the context of finite-armed dueling bandits, the learner only observes a pairwise preference between two selected arms, and the goal find the best arm (Yue & Joachims, 2009; 2011; Yue et al., 2012). In dueling bandit literature, different criteria (e.g.. Borda winner, Condorcet winner, Copeland winner, or von Neumann winner) are used to find the best arm while focusing on minimizing the regret only using preference feedback (Zoghi et al., 201 4b; Ailon et al., 2014; Zoghi et al., 2014a; 4a; Komiyama et al., 2015; Gajane et al., 2015; Saha & Gopalan, 2018; 2019;;b; Zhu et al., 2023). We refer the readers to (Bengs et al., 2021) for a detailed survey on various works covering different settings of dueling bandits.
Contextual Bandits. Many real-life applications in online recommendation, advertising, web search, and e-commerce can be modeled as contextual bandits (Slivkins, 2019; Lattimore Szepesvári, 2020). In the contextual bandit setting, a learner receives context (information before selecting an arm), selects an action for that context, and then receives a reward for the selected action. To deal with the large (or infinite) number of context-action pairs, the mean reward of each action is assumed to be parameterized by an unknown function of action-context features, e.g., linear (Li et al., 2010; Chu al., 201 I; Abbasi- Yadkori al., 2011: Agrawal & Goyal, 2013b), GLM (Filippi al., 2010; Li et al., 2017; Jun et al., 2017), and non-linear (Valko et al., 2013; Chowdhury & Gopalan, 2017: Zhou al., 2020; Zhang et al., 2021). We adopt the simplest neural contextual bandit algorithms for dealing with non-lineat rewards, i.c., NeuralUCB (Zhou et al., 2020) and NeuralTS (Zhang et al., 2021) to our setting, as also done in earlier works (Dai al., 2023; Lin al., 2023). Since NeuralUCB or NeuralTS primarily influences the arm selection strategy, we can incorporate any variants of these algorithms by making appropriate modifications to Assumption 2 and Theorem 1. These adoptions can be challenging because of our setting solely relies on pairwise comparisons.
Contextual Dueling Bandits. The closest work to ours is contextual dueling bandits (Saha, 2021; Saha & Krishnamurthy, 2022; Bengs et al., 2022; Di et al., 2023; Li et al., 2024). Specifically, Saha (2021); Saha & Krishnamurthy (2022) proposed algorithms for contextual linear ducling bandits with pairwise and subset-wise preference feedback and established lower bounds for contextual preference bandits using a logistic link function. Whereas Bengs et al. (2022) generalized the setting to the contextual linear stochastic transitivity model, Di et al. (2023) considered the variance-awan algorithm, and Li et al. (2024) proposed an algorithm based on Feel-Good Thompson Sampling (Zhang, 2022). However, there are two key differences: non-linear reward function and arm-selection strategy. Existing work only considers the linear reward function, which may not be practical in many real-life applications. Our work fills this gap in the literature and generalizes the existing setting by considering the non-linear reward function in contextual dueling bandits. Furthermore, the existing works use different ways to select the pair of arms, leading to different arm-selection strategies than ours. Due to the differences in arm-selection strategy and non-linear reward function (which is estimated using an NN), our regret analysis is completely different than existing works.
7 CONCLUSION
Due to their prevalence in many real-life applications, from online recommendations to ranking web search results, we consider contextual dueling bandit problems that can have a complex and non-linear reward function. We used a neural network to estimate this reward function using human preference feedback observed for the previously selected arms. We proposed upper confidence bound- and Thompson sampling- sampling-based based algorithms with sub-linear regret guarantees for contextual dueling bandits. Experimental results using synthetic functions corroborate our theoretical results. Our algorithms and theoretical results can also provide insights into the celebrated reinforcement learning with human feedback (RLHF) algorithm, such as a theoretical guarantee on the quality of the learned reward model. We also extend our results to contextual bandit problems with binary feedback, which in itself a non-trivial contribution. A limitation of our work is that we currently do not account for problems where multiple arms are selected simultaneously (multi way preference). which is an interesting future direction. Another future topic is to apply our algorithms to important real-wor world problems involving preference or binary feedback, e.g., LLM alignment using human feedback.
10

---

Published as a conference paper at ICLR 2025
ETHICS STATEMENT
The contributions of our work are primarily theoretical. Therefore, we do not foresee any immediate negative societal impact in the short term. Regarding our longer-term impacts, discussed in Appendix E, our algorithms can be potentially adopted to improve online RLHF. On the positive side, our work can lead to better and more efficient alignment of LLMs through improved online RLHF, which could benefit society. On the other hand, the potential negative societal impacts arising from RLHF may also apply to our work. On the other hand. potential mitigation measures to prevent the misuse of RLHF would also help safeguard the potential misuse of our algorithms.
ACKNOWLEDGEMENTS
This research is supported by the National Research Foundation (NRF), Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme. The Mens, Manus, and Machina (M3S) is an interdisciplinary research group (IRG) of the Singapore MIT Alliance for Research and Technology (SMART) centre. DesCartes: this research is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Campus for Research Excellence and Technological Enterprise (CREATE) programme.
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Proc. NeurlPS, pp. 2312-2320, 2011.
Shipra Agrawal and Navin Goyal. Further optimal regret bounds for thompson sampling. In Proc. AISTATS, pp. 99-107, 30.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff'. In Proc. ICML, pp. 127-135, 2013b.
Nir Ailon, Zohar Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In Proc. ICML, pp. 856-864, 2014.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, pp. 235-256, 2002.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv:2204.05862 2022.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Pand Paul, and Eyke Hüllermeier. Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research, pp. 1-108, 2021.
Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual dueling bandits under linear stochastic transitivity models. In Proc. ICML, pp. 1764-1786. 2022.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In Proc. NeurlPS, pp. 2249-2257, 2011.
Shreyas Chaudhari, Pranjal Aggarwal, Vishvak Murahari, Tanmay Rajpurohit, Ashwin Kalyan, Karthik Narasimhan, Ameet Deshpande, and Bruno Castro da Silva. Rlhf deciphered: A critical analysis of reinforcement learning from human feedback for 1mms. arXiv:2404.00855. 2024.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proc. ICML, pp. 844-853, 2017.
Wei Chu, Lihong Li, Lev Reyzin, and Robert E Schapire. Contextual bandits with linear payoff functions. In Proc. AISTATS, pp. 204-214,7 2011.
Zhongxiang Dai, Yao Shu, Arun Verma, Flint Xiaofeng Fan, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated neural bandits. In Proc. ICLR, 2023.

---

Published as a conference paper at ICLR 2025
Nirjhar Das, Souradip Chakraborty, Aldo Pacchiano, and Sayak Ray Chowdhury. Provably sample efficient rlhf via active preference optimization. 10Xi::2402.10500, 2024.
Qiwei Di, Tao Jin, Yue Wu, Heyang Zhao, Farzad Farnoud, and Quanquan Gu. Variance-aware regret bounds for stochastic contextual dueling bandits. arXiv:2310.0090 10.000600, 2023.
Vikranth Dwaracherla, Seyed Mohammad Asghari, Botao Hao, and Benjamin Van Roy. Efficient exploration for Ilms. arXiv:2402.00396 2024.
Louis Faury, Marc Abeille, Clément Calauzènes, and Olivier Fercoq. Improved optimistic algorithms for logistic bandits. In Proc. ICML, pp.
2020.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In Proc. NeurIPS, pp. 586-594, 2010.
Pratik Gajane, Tanguy Urvoy, and Fabrice Clérot. A relative exponential weighing algorithm for adversarial utility-based dueling bandits. In Proc. ICMI., pp. 218-227, 2015.
David R Hunter. Mm algorithms for generalized bradley-terry models. Annals of Statistics, pp. 384-406 2004.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Proc. NeurlPS, pp.
2018.
Kaixuan Ji, Jiafan He, and Quanquan Gu. Reinforcement learning from human feedback with active queries. arXiv:2402.0944) 2024.
Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable generalized linear bandits: Online computation and hashing. In Proc. NeurlPS, pp. 99-109, 2017.
Parnian Kassraie and Andreas Krause. Neural contextual bandits without regret. In Proc. AISTATS, pp. 240-278. 2022.
Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Proc. COLT, pp. 1141-1154, 2015.
Andreas Krause and Cheng S Ong. Contextual gaussian process bandit optimization. In Proc. NeurIPS, pp. 2447-2455, 2011.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bandit approach to personalized news article recommendation. In Proc. WWW, pp. 661-670, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual
bandits. In Proc. ICML, pp. 2071 1-2080, 2017.
Xuheng Li, Heyang Zhao, and Quanquan Gu. Feel-good thompson sampling for contextual dueling bandits. arXiv:2404.0600 000111, 2024.
Xiaoqiang Lin, Zhaoxuan Wu, Zhongxiang Dai, Wenyang Hu, Yao Shu, See-Kiong Ng, Patrick Jaillet, and Bryan Kian Hsiang Low. Use your instinct: Instruction optimization using neural bandits coupled with transformers. arXiv:2310.02900 2023.
Xiaoqiang Lin, Zhongxiang Dai, Arun Verma, See-Kiong Ng, Patrick Jaillet, and Bryan Kian Hsiang Low. Prompt optimization with human feedback. arXiv:2405. 17346, 2024.
R Dunean Luce. Individual choice behavior: A theoretical analysis. Courier Corporation, 2005.
Viraj Mchta, Vikramjeet Das. Ojash Neopane, Yijia Dai, Iliaa Bogunovic, Jeff Schneider, and Willie Neiswanger. Sample efficient reinforcement learning from human feedback via active exploration. arXiv:2312.0022/7 2023.
Jacob Menick. Maja Trebacz, Vladimir Mikulik, John Aslanides, Francis Song, Martin Chadwick. Mia Glaese Susannah Young. Lucy language models support answers with verified quotes. arXiv:2203. /1/47, 2022.
Geoffrey Irving, et al. Teaching
12

---

Published as a conference paper at ICLR 2025
Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks. In Proc. EMNLP, pp. 3982-3992, 2019.
Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. In Proc. NeurIPS, pp. 30050-30062, 2021.
Aadirupa Saha and Aditya Gopalan. Battle of bandits. In Proc. UAI, pp. 505-814, 2018.
Aadirupa Saha and Aditya Gopalan. Active ranking with subset-wise preferences. In Proc. AISTATS, pp. 3312-3321, 2019a.
Aadirupa Saha and Aditya Gopalan. Pac battling bandits in the plackett-luce model. In Proc. ALT, pp. 700-737, 2019b.
Aadirupa Saha and Akshay Krishnamurthy. Efficient and optimal algorithms for contextual dueling bandits under realizability. In Proc. ALT, pp- 968 198,994,225 2022.
Aleksandrs Slivkins. Introduction multi-armed bandits. Foundations and Trends@) Machine
Learning, 2019.
Hossein Azari Soufiani, David Parkes, and Lirong Xia. Computing parametric ranking models via rank-breaking. In Proc. ICMI., pp. 360-368, 2014.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICML, pp- 1015-1022, 2010.
Michal Valko, Nathan Korda, Rémi Munos, Ilias Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Proc. UAI, pp. 654-663, 2013.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian Processes for Machine Learning. MIT press, 2006.
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems ducling bandits problem. In Proc. ICML, pp. 1201-1208, 2009.
Yisong Yue and Thorsten Joachims. Beat the mean bandit. In Proc. ICML, pp. 241-248, 2011.
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, pp. 1538-1533 1556, 2012.
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, pp. 834-857, 2022.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural Thompson sampling. In Proc. ICLR, 2021.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with UCB-hased exploration. In Proc. ICML, pp. 11492-11502 2020.
Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise k-wise comparisons. In Proc. ICMI, pp. 43037-43067, 2023.
Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. In Proc. ICML, pp. 10-18, 2014a.
Masrour Zoghi, Shimon A Whiteson, Maarten De Rijke, and Remi Munos. Relative confidence sampling for efficient on-line ranker evaluation. Proc. WSDM, pp. 73-82, 2014b.
13

---

Published as a conference paper at ICLR 2025
A THEORETICAL ANALYSIS FOR NDB-UCB
LTK be a set of all possible context-arm feature vectors: (sta)ssss where Let [z(m))n=
n [(t- - 1) + a. Define
)
H P-1
Σ P.j
(I(p). R())) A
p.g
P.q
9.9
(1+1)) 21E
(u,)) [uaax 0} max 0}},
(++1) 2H!!) E p.g (1.0)~ [F 2 0) 2 0)] p.
(1+1)
Then, H (H + /2 is called the neural tangent kernel (NTK) matrix on the set of context-arm feature vectors {T(m)] )2
Next, we first list the specific conditions we need for the width m of the NN:
m 2 CT L L m(logm) > Cx "
(8)
m(log m) m)- 2 Cx p 11 1 -11 7 m(log m 3 2 C7 18 -8
1s:
for some absolute constant C > 0. To ease exposition, we express these conditions above as m poly(T, K, 1/ Lyz, 1/>o. 1/2, log(1/))).
To simplify exposition, we use an error probability of å for all probabilistic statements. Our final results hold naturally by taking union bound over all required 0's. The lemma below shows that the ground-truth utility function can be expressed as a linear function.
Lemma 2 (Lemma B.3 of Zhang et al. (2021)). As long as the width m of the NN is wide enough:
m 2 CoT K 4 log(T K2 2² L/8)/>/:
then with probability of at least - 8, there exits a O such that
f(x) = (g(x; 0o), 0 - 0o), v |0, Boll2 S 22 1 B.
for all x. E Xr 1L E (T).
Let V/ = [(x,,1 > x2,2). then we can write P (y= =) a (h(xe,1;0) hxx.2200) and P (y. 0) = a (h(I,,1;0) h(x.2;0)) (h(I,.2;0) - h(z
A.I THEORETICAL GUARANTEE ABOUT THE NEURAL NETWORK
The following lemma gives an upper bound on the distance between O, and 0p:
Lemma 3. We have that 100 loll2 2 mX Vt [T].
Proof. As ((-) E 10, 1], then using Eq. (1) gives
2 > 1|0 0ol12 s (o.) S L.(0))
1
I 1 log (1) - -1(xx,2;00) +
1
(1 - 1 log e (h(x,,2; Au) - h(Fs,1:00))
+ 2 16u -b012
14

---

Published as a conference paper at ICLR 2025
(a)
log (0) + (1 10 log (0)
21,1
22
log 0.5
#=1
t( log 0.5)
m7
IA
Step (a) follow because h(2;; 0o) = 0, Vo E &,,6E [2] which is ensured by Assumption 2, step (6)
follows because - log 0.5 < 1. Therefore, we have that ||0 - 00 - 2 S 2 mx
Now, Lemma allows us to obtain the following lemmas regarding the gradients the NN.
Lemma 4. Let r 2
t mx
Then for absolute constants C3, C1 >> O, with probability of at least
1 1-6, 8,
(g(x;0:))l2 S &CVVmL,
11g(2;00) 0(x;00)l2 S CIv 1/ Cim V t 1/3 x
T/2
for all x E Xe, [T].
Proof. It can be easily verified that our 7 = 2 mx satisfies the requirement on T specified in Lemmas B.5 and B.6 from Zhang al. (2021). Therefore, the results from Lemmas B.5 and B.6 from
Zhang et al. (2021) are applicable for 0g because our Lemma guarantees that || - 00ll2 I т.
In addition, Lemmas B.4 from Zhou et al. (2020) allows us to obtain the following lemma, which shows that the output of the NN be approximated its linearization.
Lemma Let t - 2 mx Let E'm, & C2m 1/6 Vlog (4) 4/3 constant C2 > O, with probability of at least 1- 6,
+
Then for some absolute
t 4/3
[n(2;; 0.) (0, 0o. g(;; 0o)) s 1/3 1 mmllg O2m 1166
1/6 V /logmlm mL
e m
for all x E Nx, E [T].
An immediate consequence of Lemma is the following lemma.
Lemma 1. Let e'm,t C2m 1/6 Vlog (+) 4/3 where O2 > O is an absolute constant. Then
((p(x) - (1x'),())0)))))) 0: 0o) (h(r; 02) - h(x': & 25'm.s Vt Vt (T),a, E X.
Proof. By re-arranging the left-hand side and then using Lemma 5, we get
1(x(x) - :p(z), Os - Ou) (h(2; 02) 0.))
(p(()), O2 0o) - -1(2; 0z) + 11(2;; 0z) - (p(('), Or 0o)
< ((p(x)) O2 0o) - -A(2;; 0c) + 1h(2'; 0²)) - ((p(x)) Or 0o)1
< 202m -1/6 Vlommt L
4/3
-
15

---

Published as a conference paper at ICLR 2025
A.2 PROOF OF CONFIDENCE ELLIPSOID
In our next proofs, we denote s/x g(z,,1; 0o) g(x2,2; 80). p. - g( g 8t), and hag _ 1( 0+) 2 ; 0.). Recall that p is the total number of parameters of the NN. We next prove the confidence ellipsoid for algorithm, including Lemma 6 and Theorem below.
Let 3T - 2. V d 20g((1/6). Assuming that the conditions on mn from Eq. (8) are Pip
Lemma 6.
satisfied. With probability of at least we have that
A Kije
Vm 1
- Ocllva. S BT + B1
1
V e [T].
A.2.1 PROOF OF LEMMA 6
For any O E RR, define
G. G(
Σ
P (10g: - 0v (.)) (10g Go (())) [ & + A(09 - -00)
(9)
We start by decomposing | Oz Dellvi_, in terms of Ge in the following lemma.
Lemma 7. Choose À > 0 such that A/Kp 1. Define Vz-1 E5=1 '''ip''
+ AI I.
My
A Ky
100 Oe Bellv,
I
Kip
-I,((0))lly. +
V
mm
Proof. Let X E (0, 1). For any 0z, 0zz E IR, setting =X0;; +(1 ~)0 and using mean-value
theorem, we get:
G.(Og;) -G((p;))==
p( 8. ('))44'''' + AI, (0,; -0:)
2 Kp Σ P.. -T
-
1p
(0 0
m
Kip
kp V. 10 0z)-
Note that G,(0,) 1(0,- 0g). Let fo be the estimate of f the beginning of the iteration and ft.- = (0, (.). Now using the equation above,
[[G;(0,) -(00 0o) lo) ||G((0)) (())))l
2 (1 - 0e)) (V-10
(00 0.)
=2 Vı Tv V 0e)
N² 110, 0, 1 l
This allows us to show that
110 - Oz 0ellv.,, S - [G. - -0000)))(00--00 -00 S Ky Kip
1 ||(0, 00) (10)
[G.(O,)llv:3
+ Kw
in which have made of the triangle inequality.
16

---

Published as a conference paper at ICLR 2025
Note that choose À such that A This allows to show that Vi-1 A I and hence V z 1.. Recall that Lemma tells us that 1|05 00ll2 S
Ki
B which tells us that
7m
1 |A(0, Kip
A
00)1l
V (03 0o) TV) 0o)
Kip
X
Kip (0, - Bb)
x
V
(0, - 00)
(11)
100 0ol12
B
Ky
m
Plugging Eq. (11) into Eq. (10) completes the proof.
Recall that denote y/s - e.. in which ys is binary observation and e, can be seen as the observation noise. Next, we derive an upper bound on the first term from Lemma 7:
1
[G,(B))llvzz
1
0. v22) 1d(0, 0o, (b.,4))) 2(0. 00) cu(0:
Kp
m
1
- - A(0, -0o)
Kpp
1
(m(fr.)) - =0)) 60. + X(0: 00)
(m(fe.)) v.44' 1 1-1
1
m Σ
Eaply + A(0: 60)
Kp
m
V
1
Σ
(m(Se,)) - -v4)6 + A(0, - 0o)
+
1
Σ
Kp
Rp
(12)
Next, we derive an upper bound on the first term in Eq. (12). To simplify exposition, we define
A 4 1-1 (u(fex)) vo) v.) -v)).
-
A₂ A
(u(Sr.)-H(0) u(hess)
(13)
s=1
a=1
17

---

Published as a conference paper at ICLR 2025
Now the first term in Eq. (12) can be decomposed as:
Us) v.)a''s - + 2(0; - 80) 6001l v=
(p(fe.)) -v) (0's + p - -V.) + >(0 - B0) 1=
(plfe.)) vo v.) 0% + 1(0, - -00 + A1l 11,, 1
(M(Fe.) m((1s,))) - m(thaa)) Uo/) 8 + 1(= Oo) + A1 A1l1233
(14)
(m(h..)) -v1) + 1(0 00) + A2 A
m
10
A2 + A1
V,
AZllly= + || AAllll
By |A22ll2 + v Fi ||
- X
A
Note that step (a) above follows because
((chett) - 81) 8. + A(0=- - -00
m ==1
Σ (u(h(zs,110))) - M(x22200) Ma) (o(xr,,10)) - g(xx,2;00)) 0.)) + A(0, - -0o)
0,
(15)
which is ensured by the way in which we train our NN (see Eq. (6)). Next, we derive an upper bound on the norm of A1. To begin with, we have that
11 - -.1l2= (10( g 0o)
+ g(x,,2; ( 0e))l2
(19((r,11;8) 0u) - (( 0:)11 + [1g(#..2; 0b) g 01)12
Ct
1/3
20 1/3 Vlgmm
7/2
in which the last inequality follows from Lemma 4. Now the norm of A can be bounded as:
18

---

Published as a conference paper at ICLR 2025
(p(fec) -va) (10. - (.
||
m
(plfes) - v1) (1) -5.)
In(Se,s) Mol vallls's -Pall2
(16)
1149's -Va112
1/3
20 m 1/3
log
1
772
m 2/3 Vlgg ml 1///0//-1///333
Next, proceed to bound the norm of A2. Let X E 1), and let de,s N + Nhhn. Following the mean-value theorem, we have for some X' that
p(fi,s) ((h.,)) (fe,s (ar,))
Note that (((ars)) S Ln which follows from our Assumption 1. This allows us to show that
(m(fe,s) ,(h,,))) = 1(fe, ((a.))))
= lfc h [l(e,))
S Lulfe. Tegeel
Lul (B: Go, 1 0o)) (0: G.. g(x,,;;;;; (h(2,,1;0) h(x,,2;; 0t))
I Lu (B( - u. 1: : Bo)) - ((x),,1:0)) + /(xx,220)) 01) (0, 0o. g( 0b))
4/3
S Ln x x2 x C2m - 1/6 Vlog 3 (x)
4/3
22m 1/6 Vlo mI.
in which have used Lemma 5 in the last inequality. Also, Lemma 4 allows to show that 1 (1, (2)) g 0.)l12 I (1 + (2 0:)l2 - 20,vmL.
Now we can derive an upper bound on the norm of A2:
A
1
(u(fi.)) -((h.))h)))) &%
m
(v(ft.)) - ((heel)
(17)
(M(F.,))
1175112
4/3
2I, C2m 1/6
1/6 Vlog
2C3mmL
m
< 42ym
2/3 / Tog mt?
7/3
/ 7/2
4/3
19

---

Published as a conference paper at ICLR 2025
Lastly, plugging Eq. (16) and Eq. (17) into Eq. (14), can derive upper bound the first term in Eq. (12):
(n(Se,s) va)(''s + 1(0, 00)
Kp
m
1
2/3 Vlog mt 4/ ///4//321 2012-112111-0
(18)
m
4L C2C 2/3
/log 27
Rag
Next, plugging equation Eq. (18) into equation Eq. (12), and plugging the results into Lemma 7, we have that
1 0ellv--1
[-1
B
<
EgG's
+
m
2/3
Vlog mt 23,a////22/1//p3/
Ky m
m
Ku
m
VKRA
s=1
V
4l C2Cmm 2/3
Vlg mt
7/3 7/3
K
Here define
A
1
A B
m m-166 2
Em,t
Kig
VENA
(19)
1
CL,.C 1/6 /t
AL,
VnyA
easy to verify that as long as the conditions on m from Eq. (8) are satisfied (i.e., the width m of the NN is large enough), have that C,,t B
This allows us to show that
[-1
mm 10, Vellv-
S
Σ
Ealp'e
1
Em,t
Ky
Vm
+=1
V=l
(20)
1
Σ
E
1
B
+1.
Kp
m
Ky
V=
Finally, in the next lemma, we derive an upper bound on the first term in Eq. (20).
Lemma 8. Let BT A 1. Ku Vā d 2 1og(1/6). With probability of at least 1 8, we have that
Σ
S Br.
Kyp
Vm
|=
Proof. To begin with, derive upper bound the log determinant of the matrix V, AI Here O/ to denote all possible pairwise combinations of the indices Σ'= D''p'' Ke of K arms. Here denote 2s) A ((xs,)) p(xxs)) Also recall we have defined in the main text
20

---

Published as a conference paper at ICLR 2025
that H' E L(seec (s) Now the determinant of Vú can be upper- upper-bounded bounded
A
det(V() = det
Σ (p(#),1) 2(x,,2) (f((2.11) - (x)
+
Rip
d
$ det
Σ (p(()21) (0xx222)) (10(x),1) - (2(2)22)))
Pip
(21)
$ det
(s)
Ki
#=1 (KJ))C
H' =11
det
Kige
Recall that in our algorithm, we have set Vo
A Ip. This leads
det H'' (H'+
ò Kp
det V4
log
S log det Vo det Vo
(N/Kz)) det ("Mx H' + +1)
(22)
log
(A/ki))
Kip H' + 1
log det
[T]: u(f(xs,)) f(x22)) + Es. Let Fi-1 denote the sigma algebra generated by history {( Jz.2, Ex) sx) 2t,1, 21 Here justify that the sequence of noise {==)s.1.....r is conditionally Huub-Gaussian conditioned on Ft
We use E, to denote the observation noise in iteration
Note that the observation yı equal 1 if x4,1 is preferred 24,2 and O otherwise. Therefore, the noise E, can be expressed as
- f(xe22),, w.p.
f( w.p. 1 - ((I( ((x,2))
E
It can be easily seen that e, is -emesuurable. Next, if can be easily verified that that conditioned on Fi-1 (i.e., given Ft,1 and 24,2), we have that E. [ex[FF,-1] = 0. Also note that the absolute value of e is bounded: |ev| < Therefore, we can infer that e, is conditionally Ssub-Gaussian, i.e.,
10
E [exp(Ae:)) S exp
YA E.
with o = 1.
Next, making use of the Abbasi- Yadkori et al. (2011), we can show that with probability at least - 6,
of the sequence of noise {s.} and Theorem from
det Vi-1 det Vo
E
log
+ 2 (og(1/8)
Fig H' +1) log(1/6)
log det
J 210g
in which we have made use of the definition of the effective dimension d' = log det (5 H' + 1). This completes the proof.
Finally, we plug Lemma 8 into equation Eq. (20) to complete the proof of Lemma 6:
A
m 1 - Bellv.., $ 3r + B
+1,
e ET
Ey
21

---

Published as a conference paper at ICLR 2025
A.2.2 PROOF OF THEOREM 1
Theorem 1. Let ó E (0, E,, = 126 Vlgg mL (4) for some absolute constant C2 > 0. As long as m 2 poly(T, I,, K, 1/6p, Tup, 1/>0, 1/,, log(1 /6)), then with probability of at least - 6, - - f(x') - (+( - h(2'; 0:)] I P1o + m,
for all x E N,, E [T].
Proof. Denote ppxx) g(x; 0n). Recall that Lemma 2 tells us that f(x)) (g(x;; (o;;00))0, - -00)
(p(x), 0y - 0o) for all x E dg, t E [T]. To begin with, for all x; x' E &2 E [T] we have that
[x() f(x') - (f(x)) p(x'), 02 - Ba)1
= 1(p(z) - 0(z'),0,
0, - Oo) (p(()) - ((xx), 0, - 0o}l
= 1(p(x)) - ((x'),0- - 0,)11
1
1( Vm p(x) p(x)), vm (0, -oa)
(23)
Vm (p(x) - p(x1))
Vm 110s Oellve-
1/
(g(x)) - p(x1))
Br + B1
Kiy +1
Vm
in which we have used Lemma 6 in the last inequality. Now making use of the equation above and Lemma 1, we have that
1f(x) f0=')-='------)
(h(æ; 02) - n(x'; -s(x)) -
- -(xx)) (o('), - 0o)
+ (x(xx) - p(z'), - -0) - (h(x; 02) h(x(:0,))) S (f(x) f(z')) (p(z) p(x'), -80)
+ ((p(x)) - ((xx), 0: - -Oo) (h(2;; 0+) 11(a''
(p(x) - =((0))
Br + BB
+ 1)
+ 26'm.."
Kip
This completes the proof of Theorem 1.
A.3 REGRET ANALYSIS
Now we can analyze the instantaneous regret. To begin with, we have
2r.- = f(x[) f(x,,)) + fait) - 22
(0) - (g(x;) - 1( 0, -Oo) + Vm
1 (
(((.)))) vm (p(x;)
(v(x;))
|-=
(B B By/a/m
v:
+ (((x)) ((1),2), 0: 0g) +
1
(((r)2))
(rr /// +1)
(v(()) - p(x,11); O2 - 00) +
(p(xz) ((())))
Br + BB++B///igg +1)
vm
+ (((())) - ((x 0, - 0o) + (v(().1)) - ((()22) O2 - (b)
+ (v(x7) - (((..)) + (((())) - ((((,2))
Br + B / 1//
22

---

Published as a conference paper at ICLR 2025
s 2((((x)) - (((t,,), - 00) +
(p(x)) - v(((11))
(7 + BB A/Knpt Bv/mt///
vm
+ ( ((xr,2) 0g 0o) +
(50(x),1) - (2())22)
3 BB 1/1b/t +1)
mm
1==1
(
2 22(x1;00) 02) 22(0011;00 01) + 4em,, +2
1
(v((x)) - (0(0)11))
3r +r+ Ty+BB By 2/mii +
vm
1
+ + 06) h(21,2; 01) + +22mm,t +
((((x).1) (((222)
(8r+ BB+BBAD 1/ +
m
1/
(
1 (p((),2) - v(((211)
S 2/( 01) 2h(3),1;01 01) +
By Br /2/K +1
1ELl
+ h(0111;0) h(x 6e +
1 (p(()).)) (0(22)2)
BT Bv 2/ri +1)
vm
Vi-
h( h( 0,) + 3
1
((((0),)) ((
(8 + B //1/// +1) + 65
mm
V,
(d)
< 3
BT + B B \/ +1 (p(()),)) - (((r12))
+ 6E
[,
Step (a) follows from
Eq. (23), step
(6)
results from
Lemma
step
(c)
follows from the way in which
Ft,2
is selected:
Ft,2
e
M[x;; 0.) + to (p(x) - p((r),))) [= (8r
B
V
A Kp
+1)
and step (d)
follows from the way in which 1 selected: x2,1 = arg max h(x; 0t).
Now denote 02-1(01,1, = A (p(=)1)) p(x)22) k= Of note, (f-1
can be interpreted as the Gaussian process posterior variance with the kernel defined as 1e ((111 (z1 xb)) ( (f((1)) - ((xx)) A (p(21) ((x)))), and with a noise variance of A. is easy to see that the kernel is positive semi-definite and is hence valid kernel. Following the derivations of the Gaussian process posterior variance, it is easy verify that
of (x1,1, I ((((1),1) - (((,,2)) (1((1),)) - =(xx,2))
(o(or.)) - v((2,2) 1 2
/m 12
1 m 1 (( 11 co:
in which we have denoted co 0 as absolute constant such that + ||<((x) p(x')l s co. Va, E X,,t E [T]. Note that this is similar to the standard assumption in the literature that the value of the NTK is bounded by constant (Kassraic & Krause, 2022). Therefore, this implies that of_ (21,1, 22,2)) co & 1 for some constant cp 2 1. Recall that we choose À such that A/RR 1. Note that for any E [0, 1]. we have that a/2 < log(1 a). With these, we have that
1
A
(21,1, 21.2)
A
of (1,,1,
< log
1+
2
Kyp
60
Kpp
C
A
< log
1
( 21,2)
Kpp
which leads to
(2 $ 200
log
(1
+
Kip
02
1
(24)
Kp
X
23

---

Published as a conference paper at ICLR 2025
Following the analysis of Chowdhury & Gopalan (2017) and using the chain rule of conditional information gain, we can show that
Σ log (1 (1+
Ki 0² (F5, log det (I Mip k.),.
X
which K, is at X & matrix in which every element is K Ji = i (p(()1)) - (((1,2)) ( (1((2).) ((x),2)) Define the x l matrix J. V (p(1111) - (p(Ts,2))
Then we have that
K2 = J. Jr. This allows us to show that
log (
Ku o² (2 va,2) - log det (I+ X K.)
Ru
(I+
Ke Jj Jz)
log det
A
= log det
II+
x J.J.
(25)
= log det
I+
Ki
Σ
(0(())1) - (((222) (v((2,,1) v((x,22))
1
X
m
Ni H' +1)
I log det
=d
in which we have followed the same line of analysis as Eq. (21) and Eq. (22) in the second last inequality.
Combining the results from Eq. (24) and Eq. (25), we have that
Σ (0.1011)))))))
2c0-
log (1 + Ku o
A d.
2co Ki
Finally, we can derive an upper bound on the cumulative regret:
T
T
Ry
Σ
P
3
Br
+
B
+ 1
Ki oe- 21.,) + 66'm,e
Ky
1=1
1=
3
BT
+
B
+1
Tt (1t,1, + +6T'sm
2
Kyp
3
BT B
+1
F
oz (1), 21,2) + 6T
Kp
3
A
A d 6T T'
BT
B
+1
T200
V
Kp
Kip
3
5
BT BA
B
+1
T2c0d + 66TE'm.T
Kp
Recall that e'm,t C2m 1/6 3 (1) on specified in Eq. (8) are satisfied (i.e., as long as the NN is wide enough), we have that
be easily verified that as long as the conditions
6Te' 6Te'm.r E 1. Recall that Br = 0(1 VT). This allows us to simplify the regret upper bound to be
V +1 ((
3 2 Ri <
A +1) 3r + B BV
+ B
d
Kp
Kip
24

---

Published as a conference paper at ICLR 2025
B THEORETICAL ANALYSIS FOR NDB-TS
Denote uT A (Br ByA/Kp +1) Ra/d a A uT(1 + v log Kt²)), and 1 x2) -
Ap (+((a))) (((22) | Here we use Fi-1 denote the filtration containing the history
of selected inputs and observations up to iteration t 1. To use Thompson sampling (TS) to select the second arm Z4,2, firstly, for each arm x E X, we sample a reward value Fr(2)) from the normal distribution N (M(r;; 0x) - h(x,,1 0z), ( (x, Then, we choose the second arm as 2t2 arg max xeaxxexxTr(22 (x)).
Lemma 9, Let 5 E (0, Define Ex (t) as the following event:
[[(xx) [(=),)] [b(x;; 0z) - 1((x,,15e)) 0.)] S prot-1 Ft,1) + 28mm,
According Theorem 1, we have that the event E (t) holds with probability of at least - 6.
Lemma 10. Define F. (t) as the following event
Fz(z) - [2; 02) - h( B011 S
We have that E Fi1] 2 - 1/t2 for any possible filtration Fi-1. Definition 1. In iteration t, define the set of saturated points as
S: = {a E X₂ (x) > (x, + m,,,,)
where ((x) f(=;) (z) and 2 E arg max f(x).
Note that according to this definition, xद is always unsaturated. Lemma 11. For any filtration Ft-1, conditioned on the event E (t), we have that Vo E Q
P (F((a)) m,, f(x) f(x(1))FF-11 2 P.
where p 4cc/F
Proof. Adding and subtracting (x) both sides of P (ft(z) > Pm (x:))FF-))) we get 1()
(1) + 25/m. > f(x) f ((
Fr (x) + 25, [2; 0.) (xT1,1;0.)
> f(x) - f(x,,1) - - [1( 0z) ((,)
P
[F
VIO (2, x1,1)
Vro Ix,1)
Fr (x) + 26 2mm [x 0,) - (1(1,1000)]
1f(x) - f(x(11) - [h(2;; 0,) h( 1F
P
(2, 21,1)
V1 21,1)
Fr (x) [1(2;; 02) h (
1f(x) f(x,,1) - [1(2;; 0,) h( 0c)] 25' m.! F
Pro--1 It.1)
(I,
Fr (x)
[b(x;; 0.) 1 (((,,1;000)
P
> 1[Fr-1
110
1
4
in which the third inequality makes use of Lemma 9 (note that we have conditioned on the event Ef (t) here), and the last inequality follows from the Gaussian anti-concentration inequality: P( > a) 2 exp(_a²) (44/m)) where z ~ (N,0 1).
The next lemma proves a lower bound on the probability that the selected input x4,2 is unsaturated. Lemma 12. For any filtration Fr-1, conditioned on the event ES (1), we have that,
IP ( X, S.(FF > 1/12.
25

---

Published as a conference paper at ICLR 2025
Proof. To begin with, we have that
IP ( E E, \ S1FF-11) P(()))) (.)) Ve E S
(26)
This inequality can be justified because the event on the right hand side implies the event on the left hand side. Specifically, according to Definition I, 2 is always unsaturated. Therefore, because 2 selected by 2i,2 = arg max 7x (x), we have that if Fr (x;;) > Fr(x), Var E S., then the selected Jt, guaranteed to be unsaturated. Now conditioning on both events E (t) and (t), for all St, we have that
(z) z f(x) f( + 00t-1 + 22'm,
f(x) f(z11) + (2, + 4 25 m,
s f(xr) f(xx, + A(x) - 22 m,
(27)
=f(x) f(x,,1) + f=,,) f(x) -2é
-[(]] [(x,,) 2e'm,
in which the first inequality follows from Lemma 9 and Lemma 10 and the second incquality makes use of Definition 1. Next, separately considering the cases where the event E (t) holds or not and making use of Eq. (26) and Eq. (27), have that
IP ( E Ne F(11) 2 IP (a) > Fr(z), Ve E S,(F(-1)
2 P (z) f(x)) - f(11,1) -2 F PP (t)-t))
p 1/t2
in which the last inequality has made use of Lemma 10 and Lemma 11.
Next, we use the following lemma to derive an upper bound on the expected instantaneous regret.
Lemma 13. For any filtration Fr-1, conditioned the event F (f), we have that,
23c, E (1., + 185 +
4
1[2r1FF-11] <
1
Proof. To begin with, define n, as the unsaturated input with the smallest o,- (xx,
Tt arg 1
This definition gives us:
E (Fx,,, 2 E 0o (Ir,2 Ft, F1 E P E X, Fr
(28)
2 - (Ir, Zo,1 (p 1/t²),
which the second incquality makes use of Lemma 12, as well as the definition of zt,
Next, conditioned on both events (t() and F. (t), we can decompose the instantaneous regret as
2r. = f(x))= - f(x11) + f(x)) - f(x122
fx()) - f(112) + f(1,2) f(111) + f(x7)) f2122)
(29)
=2[f(x]) - f(x12)) + f(x1,2) - f(1,1))
Next, we separately analyze the two terms above. Firstly, we have that
f(x;) - f(x,2) [(x;) f(x)) + f(x)) - f(x1,2
A(x) (fx) - [xt,1))
$ ( (z.) -. -, 2 Fe(22.2) (10 + 2
-0.- < A(x)) +,00- ( 2t,,) + 4
$ 9101-1(51,, + 4 ' + -0 (7,, v1,1) + 2 (x0,,, + 45m
< 2400 (1t1) + -- (
1 + '.mm.:
(30)
26

---

Published as a conference paper at ICLR 2025
in which the first inequality follows from Lemma 9 and Lemma 10, the second inequality follows from the way in which žt,2 is selected: Σ422 = arg m (z()) which guarantees that (Tee I (2)1)) The third inequality follows because 2, is unsaturated. Next, analyze the second term from Eq. (29).
f(2122) f(1(1)) - h( 01) h(xx,11;1) 01) (100)-((2122 + 25
S Pror- (2t,, + 22
(31)
$ (0 22,1) + 2
in which the first inequality follows from Lemma 9, the second inequality results from the way in which Ta, is selected: 21,1 arg maxxex, h(z; 8t), and the third inequality follows because UT S ar by definition. Now we can plug Eq. (30) and Eq. (31) into Eq. (29):
2r. S 2 1 + G. ( Lt,1) + m),,)) + ( + 25'm.
(32)
$ (2 + 3 21,1) + 18 m,t"
Next, by separately considering the cases where the event E (t) holds and otherwise, we are ready upper-bound the expected instantaneous regret:
4
E|2r, Fi < 1 1 + 3c,
(11,2, I + 18 18 [Fr- +
1
30,0 (2,11 + 18e'm,,IFe- 4
< E
4G,, (2 02,11
p p- 1/t2
4
186' m, a 1/t2 +33 E (1)1
8
23
< a E
18 m,,,
+ y
in which the first inequality have made use of Eq. (32), the second inequality results from Eq. (28),
and the last inequality follows because p-1/1z S 5/p and 1 < 1/p.
Next, we define the following stochastic process (Y, t = ......)), super-martingale in the subsequent lemma by making use of Lemma 13. Definition 2. Define Yo O. and for all I.
T), which we prove is
F. = :=)(((((()), X, = Tt
23c,
at Fe-1(au (I1,2, - 95'm, 2
and
Y, Σ X,.
2p
Lemma 14. (Y, 1. = O.... T) is super-martingale with respect to the filtration Fr.
Proof. As X₁ Y, - YY-1, we have
E E Y 1 = E X, Fe-1l
23c,
2 72 Fr-1
E
T,
01-1(11,, - 95'm,t
2p
230
E Fe-11
E
D6',. + 42
2p
0
When the event E (t) holds, the last inequality follows from Lemma 13; when E (t) false, Fr and hence the inequality trivially holds.
Lastly, we are ready to prove the upper bound on the cumulative regret of ou algorithm by applying the Azuma-Hon Hoeff-igni Inequality the stochastic process defined above.
27

---

Published as a conference paper at ICLR 2025
Proof. To begin with, we derive upper bound on |Y, Y(-1/:
23ct
2
Y - Y1-1 = Xxol - |Fll +
(21,2, R2,1) + 95'm, + t2
2p
23ct
S 2
co + m
2p
$ (4 + 120.00 + DEm,))
where the second inequality follows because o (2-1 S co. and the last inequality follows since 1 2 1. Now we are ready to apply the Azuma-Hoeffülee Inequality to (Yz : ....., with an error probability of d:
T
23cz
T
2
o1 121,2, 21,1)
+
Do m,
2p
t2
t=1
t=1
2
+
2log(1/6)
(4
120,00 + 9c
< 12cr
-z- Te,,1
97 TT T
+ 2 1/12
t=
1 (4 120Tco 95'm,)) +
/2T log(0/))
X d 9T m. +
n² 4 + 120rco + 95 mem.T 27 1og(1/8).
< 12eT T260
+
Kp
3
p
The second inequality makes use of the fact that ot and s'm are both monotonically increasing in I. The last inequality follows because Σt= Tt- (Ir, Te,2) S T2c0 Ad which we have shown Kp
in the proof of the UCB algorithm, and Σ 1/1 S 7//6. Note that Appendix B holds with probability 2 1- 8. Also note that F; = T2 with probability of 2 ô because the event E (f) holds with probability of 2 - 8 (Lemma 9). Therefore, replacing by 6/2, the upper bound from Appendix B is an upper bound on Ry ΣT= re with probability of 1-
Lastly, recall have defined that VT =
BT B/A/F +1) Vy/AA. a
uT V (llog) and BT
Õ VV..
This implies that er
Kr ( B/D/F/) V /u//A conditions on specified in Eq. (8) are satisfied (i.e., as long as the NN is wide enough), we can ensure that 97's m I 1. Therefore, the final regret upper bound can be expressed as:
Also recall that long the
Ri Ō
d Kipd
+
B
T Kig
A
J-
(V====
d +
B
VT
ā
X
VVd
A
=
+
B
T
=
+
B
v Td
Kip
Ki
Kip
This completes the proof. As we can see, our TS algorithm enjoys the same asymptotic regret upper bound our UCB algorithm, ignoring the log factors.
28

---

Published as a conference paper at ICLR 2025
C
ADDITIONAL EXPERIMENTS FOR SECTION 5
Uneliis IDO 1ale
13000
16000
Cummuaieee Regget
4003
NOBTTS
C ROSINE
SEAFTS
2003
2003
430
080
1030
20
1880
(a) 10(x 0)2 (Average)
(b) 10(x 00 (Weak)
(c) 20(x' T 0)" (Average)
(d) 20 T 0)2 (Weak)
Comdantrv Begeet taxtrog)
Corruastie Rogject Daweooopt
CecTTI IEDETS
13000
COUSTIN SAIN
5000
200
400
830
16:0
200
400
830
1099
(e) 30(x' 0)² (Average)
(1) 30 0)2 (Weak)
(g) 40 0)3 (Average)
(h) 40 0) (Weak)
Figure 5: Comparisons of cumulative regret (average and weak) of different dueling bandits algorithms for different form of Square function, i.c., a(x 0)2, where a = {10, 20, 30, 40}.
LEGHHOI CALITN
LIDBILEA
LHOSTS
UHOSTS
Camurato Ragget
ADB LCB
500
NOB-UCE
330
400
600
900
3000
380
400
050
830
3000
(a) cos 8) (Average)
(b) c3s(3n 0) (Weak)
(c) 30os(x T) (Average)
(d) 3cos(x 0) (Weak)
LiKE CoLSTIM MOSTS
1003
Corrral Litr Bug Canceooee
Landb
Cumulattvve Nequett
CALSTE
COLSTIN ND6-72
COLSTIR
Cumuratre Tagget
80
222
(e) 5cos(x 0) (Average)
(f) 5cos(1 0) (Weak)
(g) 10cos(x O) (Average) (h) 10cos(1 0) (Weak)
Figure Comparisons of cumulative regret (average and weak) of different dueling bandits algorithms for different form of Cosine function, i.e., cos (3x 0) and bcos(x 0), where = {3, 5, 10).
C.1 COMPUTATIONAL EFFICIENCY AND SCALABILITY
To discuss the computational efficiency and scalability of our proposed algorithms, we consider the following two key aspects:
Size of the neural network (NN): from the NN used to estimate the latent reward function. Let d be the dimension of the context-arm feature vector (input dimension for the NN). Assume the NN has L hidden layers, each with m neurons. Then, the inference cost from the input layer to the first hidden layer is ((dm), the inference cost for hidden layers is O(Lm²) and the inference cost for the final layer is O(m). Therefore, the overall inference cost for each context-arm pair is O(dm + Lm + m). Note that p = dm + Lm? + m is the total number of NN parameters. The training time for the NN is O O(ECIm²)). where E is
The primary computational complexity of our proposed algorithms
29

---

Published as a conference paper at ICLR 2025
the number of training epochs and C' is the number of context-arm pairs observations. Therefore, choosing the appropriate size of NN for the given problem is very important, as having smaller NNs may not accurately approximate the latent reward function, while larger NNs can incur significant training and inference costs.
Number of contexts and arms: Let K be the number of arms and p be the total number of NN parameters. Since we use the gradients with respect to the current estimate of NN as context-arm features, the gradient computation cost for each context is O(Kdp), where d is the dimension of the context-arm feature vector. The computational costs for computing reward estimate and confidence terms are (p)) and (Kp)), respectively. For selection arms, the computational cost for the first arm is (Kp- + K), which includes estimating the reward for each context-arm pair ((K)) and then selecting the arm with the highest estimated reward OK)); and the computational cost for the second arm is O(Kp + (K 1)p"), i.e., computing estimated reward O (Kp) and confidence terms O(KK' 1))²) ) for all arm with respect to the first selected arm Thus, the overall computational cost of our proposed algorithms for selecting a pair of arms for each context is (KKpp + Kp²). Since each context-arm pair is independent of others, each arm's s gradients, reward estimate, and optimistic term be computed in parallel. Consequently, the computational cost for selecting pair of arms for each context can reduced to (dp + p²).
C.2 COMPARISION WITH EXISTING CONTEXTUAL DUELING BANDIT ALGORITHMM
Saha (2021) proposed a contextual linear dueling bandits algorithm using a logistic link function with pairwise and subset-wise preference feedback. Whereas Bengs et al. (2022) generalized the setting to the contextual linear stochastic transitivity model, and Li et al. (2024) proposed an algorithm based on Feel-Good Thompson Sampling (Zhang, 2022). These existing works only consider the linear reward function, which may not be practical in many real-life applications. Our work fills this gap in the literature and generalizes the existing setting by considering the non-linear reward function in contextual dueling bandits. Furthermore, the arm-selection strategies are different, as Saha (2021) and Li et al. (2024) select the most informative pair of arms, and Bengs et al. (2022) select the first arm optimistically and select the second arm that beats the first arm optimistically. In contrast, we select the first arm greedily to ensure the best pest-peefonming arm is always selected and then the second arm optimistically to focus exploration, making the arm-selection process computationally efficient as our algorithms only need to compare K 1 pairs instead of all possible pairs (i.e., O(K))) Since we an NN-based reward estimator, our optimistic term caleulations for the context-arm pairs differ from the existing work. Therefore, our regret analysis uses techniques different from existing algorithms for contextual dueling bandits.
C.3 WHAT IF FIRST AND SECOND ARM ARE SAME
Since our proposed algorithms have a sub-linear regret guarantee, they will eventually select the best arm and recommend it in duels. This implies that for given context, both the first and second arms chosen may ultimately be the same, representing the best-performing arm. Therefore, the first and second arms can be the same in our proposed algorithms. However, observations in which both arms are the same do not provide any useful preference information for estimating the latent reward function, as no comparison is being made. Including such observations for estimating latent reward function would only contribute to noise and result in a constant loss. Thus, we have to exclude these observations from the reward estimation.
D NEURAL CONTEXTUAL BANDITS WITH BINARY FEEDBACK
We extend our results to the neural contextual bandit problem in which a learner only observes binary feedback for the selected anms (note that the learner only selects one arm in every iteration). Observing binary feedback is very common in many real-life applications, e.g., click or not in online recommendation and treatment working or not in clinical trials (Li et al., 2017; Faury et al., 2020).
Contextual bandits with binary feedback. We consider contextual bandit problem with binary feedback. In this setting, we assume that the action set is denoted by A. Let X; C Rd denote the set of all context-arm feature vectors in the round i and Vt,a represent the context-arm feature
30

---

Published as a conference paper at ICLR 2025
vector for context C and a E A. At the beginning of round the environment generates context-arm feature vectors {Tr,a and the learner selects an ar a,. whose corresponding context-arm feature vector is given by Zt,a. After selecting the arm, the learnr observes stochastic binary feedback E {0, for the selected arm. We assume the binary feedback follows a Bernoulli distribution, where the probability of y/+
for context-arm feature vector zz,a is given by P' (y/e 1 = μ (f))..)) where R - [0, 1] is continuously differentiable and Lipschitz with constant Ly. e.g., logistic function, i.e. pax) 1/(1+e "). The link function must also satisfy Rig. = infzex (x)) > 0 for all arms.
Performance measure. The learner's goal is to select the best arm for each context, denoted by =; argmaxxex, fa)) Since the reward function is unknown, the learner uses available observations ( Vs I 1== to estimate the function f and then use the estimated function to select the arm (3 for context Tt. After selecting the arm 0r, the learner incurs an instantaneous regret, rt = / (f(=))) y ()) For T contexts, the (cumulative) regret of policy that selects action aj for a context observed round is given by Ry =E fr = =i= [p (f(zz) y (z)) Any good policy should have sub-linear regret, i.e., limm- Rt = O. Having sub-linear regret implies that the policy will eventually select the best arm for the given contexts.
D.1 REWARD FUNCTION ESTIMATION USING NEURAL NETWORK AND OUR ALGORITTMM
To estimate the unknown reward function S. we use a fully connected neural network (NN) with parameters 0 as used in the Section 3. The context-arm feature vector selected by the learner in round 8 is denoted by Vs.a E Xg, and the observed stochastic binary feedback is denoted by ya- At the beginning of round f, we use the current history of observations {< 3=)) and use it to train the neural network (NN) by minimizing the following loss function (using gradient descent):
A | Boll2 (33)
(() = Σ Us log (h( 0)) + (1 ys) log (1 u (h(# ())) 0))]
2
where 6n represents the initial parameters of the NN. With the trained NN, we use UCB- and TS-based algorithms that handle the exploration-exxloitttion trade-off efficiently.
UCB-based algorithm. We propose a UCB-based algorithm named NCBF-UCB, which works as follows: At the beginning of the round t, it trains the NN using available observations. After receiving a context, the algorithm selects the arm optimistically as follows:
Fta
arg max (1( 0c) 1T))-1(2)), zEX:
(34)
where (x) 2 Nn
g(x:0p) Vm
in which V = E. g(:; 00)g 0o)
TL 1IL++111 P VT = (3r Ap
v=l
B B// + 1R in which 3r = K, v vd 2 log(1 and do is the effective dimension. We define the effective dimension later in this section (see Eq. (35)), which is different from Eq. (4).
NCBF-UCB Algorithm for Neural Contextual Bandits with Binary Feedback based UCB
Tuning parameters: 8 (0, 1) and X >
2: for = 1,...,7' , do
3: Train the NN using {z),,.,,){{= by minimizing the loss function defined in Eq. (33)
4: Receive a context and X, denotes the corresponding context-arm feature vectors
5: Select Vt,a = arg maxzex, [h(x;; 0.) + uro.-1 (1:) (as given in Eq. (34))
6: Observe preference feedback binary yt
7:
end for
TS-based algorithm. We also propose TS-based algorithm named NCBF-TS, which is similar NCBF-UCB except select the arm Tt,a it firstly samples reward re(w)) N (1),;))), 1fo0 for every x E X, and then selects the arm Fta = arg max (1(x).
31

---

Published as a conference paper at ICLR 2025
Regret analysis. Let K denote the finite number of available arms. Our analysis here makes of the same assumptions as the analysis in Section (i.e., Assumption 1 and Assumption 2). Let H₂ = - E g (ds 0o) We now define the effective dimension as follows:
dn log del ( + +1)
(35)
Compared to H' defined in Section 3.3, H. contains only K contexts, which is less than the x K x (K - 1) contexts in H'. Therefore, our de is expected to be generally smaller than in the neural dueling bandit feedback, as binary reward is more informative than preference feedback. A key step in our proof is that minimizing the loss function Eq. (1) allows us to achieve the following:
Ia (h(xz,a00)) Vel g( 0,) ) + X(O; - 00) O.
(36)
We use the above fact to prove the following confidence ellipsoid result as done in linear reward function (Li et al., 2017; Jun et al., 2017; Faury et al., 2020).
Theorem 4. Let å E (0, 1), e = C2m 1/6 Vlog mL (+) 4/3 for absolute constant C2 0. As long as 2 poly(T, L, K, 1/Kps , Ln 1/ 1/A, log(1 1/)), then with probability of at least 8, we have
If(x) h(2; 0,) S VTO (x) +
for all x E e
Similar to Theorem 1, long the NN is wide enough (i.e., if the conditions on m in Eq. (8) satisfied. More details are in Appendix A), we have that emm, OL/TT). Also note that in contrast Theorem I whose confidence ellipsoid is in terms of reward differences, our confidence ellipsoid in Theorem 4 is in terms of the value of the reward function. This is because in contrast to neural dueling bandits (Section 3), here we get to collect an observation for every selected arm.
In the following results, we state the regret upper bounds of our proposed algorithms for neural contextual bandits with binary feedback.
Theorem 5 (NCBF-UCB). Let X > Kp, B be constant such that /2h H S B, and co > be absolute constant such that [19( 0o)l1 < co. Vr X,, [T]. For 2 poly(T, L,, K, 1/Kip Lug 1/20, 1 1/2, log(1 /8)). then with probability of at least 1 - 5, we have
(
Vā Ky
My Ō
+
BB
A
Tdb
Theorem 6 (NCBF-TS), Under the conditions those in Theorem holds, then with probability of at least 8, we have
[V
Ry =ō
B
V Tdb
K6p
Note that in terms of asymptotic dependencies (ignoring the log factors), our UCB- and TS- algorithms have similar growth rates. All missing proofs and additional details are in Appendix D.2.
Comparison with Neural Bandits. The regret upper bounds of our NCBF-UCR and NCBF-TS algorithms are worse than the regret of NeuralUCB Zhou et al. (2020) and NeuralTSS Zhang et al. K2 and L,,. Specifically, note
(2021): ((d, /T) (with Kμ 1) because of our extra dependency that Ki < 1, therefore, the regret bounds in Theorem 5 and Theorem 6 are increased as a result of the dependency on Fig. In addition, the dependency Ly also places
requirement on the width
"Note that effective dimension d, is defined using H, Eq. (35), while the effective dimension d' in Zhou al. (2020) and Zhang et al. (2021) are defined using H. However, as we have discussed in Footnote 2, has the same order of growth log det (Hg/X) I). So, our regret upper bounds are comparable with those from Zhou (2020) and Zhang al. (2021).
32

---

Published as a conference paper at ICLR 2025
m of the NN. Therefore, our regret bounds are worse than that of standard neural bandit algorithms that do not depend on Ri and Ly- This can be attributed to the additional difficulty of our problem setting, i.e., only have access to binary feedback, whereas standard neural bandits Zhou et al. (2020); Zhang et al. (2021) can use continuous observations.
Also note that regret upper bounds here (Theorem 5 and Theorem 6) expected to be smaller than those of neural dueling bandits (Theorem and Theorem 3), because de here is likely to be smaller than d from Theorem 2 and Theorem 3. This may be attributed to the extra difficulty in the feedback in neural dueling bandits, i.e., only pairwise comparisons are available.
D.2 THEORETICAL ANALYSIS
In this section, we show the proof of Theorem 5 and Theorem 6 for neural contextual bandits with binary feedback (Appendix D). We can largely reuse the proof from Appendix A, and here we will only highlight the changes we need to make to the proof in Appendix A.
To begin with, in our analysis here, we adopt the same requirement on the width of the NN specified in Eq. (8). First of all, Lemma 2 still holds in this case, which allows us to approximate the unknown utility function f using a linear function. It is also easy verify that Lemma 3 still holds. As consequence, Lemma 4 and Lemma 5 both hold naturally.
D.2.1 PROOF OF CONFIDENCE ELLIPSOID
Similar to the our proof in Appendix A.2, in iteration we denote v/. g(==;; 3. e g(x.; 0z), and hag - h()z;00). Here we show how the proof of Lemma 6 should be modified. For any 0, E IP, define
1-1
G,(0p)
A
Σ s=1
p (10 - 0o, (()) (10, 0, ('))) (3))){b 9/, A(0p- - -0))
(37)
m
Note that the definition of G2 Eq. (37) exactly the same as that in Eq. (9), except that here we use
modified definition of up's. Note that here Vú is defined as V/, = E. ; 0o)g 0o) T m + AI=
Ei=1 p.pp + A I. In addition, the definition of ft,s remains: ft,, (0, o.. P2))- With the Ku
modified definitions of Vi-1, we can easily show that Lemma 7 remains valid. Note that here the binary observation can be expressed as y. = ((((x,)) + Ex, in which 6, the observation noise. is easy to verify that the decomposition in Eq. (12) remains valid.
Next, defining A₁ and A2 in the same way as Eq. (13), it is easy to verify that Eq. (14) is still valid. Note that during the proof of Eq. (14), we have made use of Eq. (36), which allows us to ensure the validity of 1 Σ (u(hha))= Us 7% + A(0; - 0n) = 0 in Eq. (15). This ensured by the way we train our neural network with the binary observations. Next, we derive an upper bound on the norm of Aj. To begin with, we have that
lly4 Flll2 = (1g(x.; g(xs; 06)l12
Cl
1/3
< 1/ Vlog m
1/2
in which the inequality follows from Lemma 4. Then, the proof in Eq. (16) can be reused to show that
v.)((1) - x.) S 2/3 ",
A 122
Σ a
Note that the upper bound above is smaller than that from Eq. (16) by a factor of 2. Similarly, we can follow the proof of Eq. (17) to derive upper bound the norm of Ag:
A
Σ
(p(Fe.)) - ((hha)))
< 2,C,, 44/3 2/3 mtg / 4/3
33

---

Published as a conference paper at ICLR 2025
in which the upper bound is also smaller than that from Eq. (17) by factor 2. As a result, defining Em,t in the same way as Eq. (19) (except that the second and third terms in Em,a are reduced by factor of 2), show that Eq. (20) is still valid:
1 Kip
vm 10, Oellv
Σ
B
+1
(38)
Vm
Kip
V=
Now derive upper bound on the first term in Eq. (38) in the next lemma, which is proved by modifying the proof Lemma
Lemma 15.
Let Br = Ki V do log(1/8). With probability of at least we have that
1 Kg
S Br.
m
Proof. Note that the main text, we have the following modified definitions: Σ Eiek ( ( 0o) t,, and ds = log det Hx+
H
To begin with, we derive an upper bound on the log determinant of the matrix 1/ Ei g(xx; (o)g 0o) A Now the determinant of V, can be upper-bounded as
de) = det
Σ
g(x.; (o)g 00)
[T_ +
A
m
Kp
T
A Kige
< det
Σ Σ
g( (0) 00) 0o)
KEK
det
H
Kip
A Ip. This leads to Recall that in our algorithm, we have set Vo
2 I det Ho + Kg
det V/
log
< log det Vo
det Vo
(A/ det (5E Ha +1
log
(A/kp)P
(8p H, +1)
log det
X
Next, following the same line of argument in the proof of Lemma 8 about the observation noise can easily show that in this case of neural contextual bandits with binary observation, the sequence of noise { is also conditionally
Next, making use the L-sub-sub-Guussinnty Gaussianity of the sequence of noise {=.) and Theorem from Abbasi- Yadkori et al. (2011),
show that with probability of at least - 6,
[-
dett Vi-1 /detVi-1) det Vo )
E Σ
log
2 log(1/8)
Vm
Re ("HH, +I) log(1/6)
log det
do + llgg(16)).
in which we have made use of the definition of the effective dimension d, = let (* H, + 1). This completes the proof.
11
34

---

Published as a conference paper at ICLR 2025
Finally, plugging Lemma 15 into Eq. (38) allows to show that Lemma 6 remains valid:
A +1, Kip
Vm 1 Dellve S fr + B
E (T].
(39)
Now we can prove the confidence ellipsoid in Theorem 4:
Theorem 4. Let ā E (0, 1), m,, C2m-1/6 Vlg mT & (4) 4/3 for some absolute constant C2 > 0.
As long as m 2 polyloyTTTTom0p L, K, 1/Kps L,s 1/20, 1/2, log(1 16)), then with probability of at least - we have
[f() - h(x; 0.)1 S PTO (x)) + e
for all x E X1, [T].
Proof. Denote ((x) = g(:; 0o). Recall that Lemma 2 tells us that f(x) = (g(2; 0o), B, Oo) =
(p(x),, 0o) for all E X,, f E [2]. To begin with, for all X2, [T'] have that
(f(z) (f(x)), 0. 0n)1 (()(1)), O 0a) (v((x), 0₂ 0o)
= [(((x)) 8 0,))1
v (0s 0.331 Vm
((r),
(40)
Vm ((x)
Vm 110g Os lellvi..
V,
A
$
p(z)
Br+BB
Br 3T
B
+1
v.
Kips
which we have used Lemma 6 (reproduced in Eq. (39)) in the last inequality. Now making use of
the equation above and Lemma 5, we have that
ff()) h(2; 0:))
= (f()) (p((x), 0: 0o) + ((((x), - h(x;; 06) s [f(x) (1(xx), O2 - -bo) + (1)(())),))))))))))(()))))) 0, 0o) - h(x; 0.) 1 ((x))
2
Br + BV
+1)
+ 6'm,es
Kp
in which the last inequality follows from Eq. (40) and Lemma 5.
Recall that we have defined in the paper x
[(2:0)) Vmn
and PT = (Br B A/mm
v=
1) / in which Br = Ky Vo log((16)) This completes the proof of Theorem
D.2.2 REGRET ANALYSIS
Now we can analyze the instantaneous regret:
[(x)) - fwx)
I h(t 01) + Pr () + E'm. - h(a;; 0.) + 1100-11 + E'm
< hia, 0t) + VTO (I+) - h(xx;;,) + uroz-1 26
= 2 + 26'm...
Next, the subsequent analysis in Appendix A.3 follows by replacing az- (x1,, by a (xt)) which allows to show that
T
Σ
of (xt) < 200
do
Kp
35

---

Published as a conference paper at ICLR 2025
Finally, derive an upper bound on the cumulative regret:
Rt
Σ
Tt
(2 26
T
T
S
UTO (37) +
m
1=1
1=1
2/T
T Σ
o (It) + 22T'Em.
1=1
A do + 2T's m'
s 2
T2co
Kyp
Again can be easily verified that as long as the conditions on m specified in Eq. (8) are satisfied (i.e., as long as the NN is wide enough), we have that 27's m.T S 1. Also recall that B7 O db).
and Mr (3r + B B A/p + 1) k Ō Vepp do + B + v Kep A). This allows us to simplify the regret upper bound to be
X do +1
Rr S 2
T200
V de
VāL
B
Ki
Kip
The proof for the Thompson sampling algorithm follows similar spirit, which we omit here.
D.3 EXPERIMENTS FOR NEURAL GLM BANDITS
Cuncrative Rageet
LICER SCEF-ICE
LYCRR
LIGERTTS
ICCRTTS
SCEF-T
R001105
(a) 10(x 0)2
(b) 40 TooTooy 0)2
(c) co ()
(d) 10cos(æ
Figure 7: Comparing cumulative regret of GLM bandits algorithms for non-linear reward functions.
Carmaative Ragnn
5003
2003
420
483
1000
450
24
1030
(a) Varying d (UCB)
(b) Varying K (UCB)
(c) Varying d (TS)
(d) Varying K (TS)
Figure 8: Cumulative regret of Algorithm NCBF-UCB and NCBE-TS vs. different number of arms
(K) and dimension of the context-arm feature vector (d) for Square reward function (i.c., 10(x T0))).
36

---

Published as a conference paper at ICLR 2025
E THEORETICAL INSIGHTS FOR REINFORCEMENT LEARNING WITH HUMAN FEEDBACK
Our algorithms and theoretical results can also provide insights on the celebrated reinforcement learning with human feedback (RLHF) algorithm (Chaudhari et al., 2024), which has been the most widely used method for the alignment of large language models (LLLMs). In RLHF, we given a dataset of user preferences, in which every data point consists of a prompt and a pair of responses generated by the LLM, as well as a binary observation indicating which response is preferred by the user. Following our notations in Section 2, the action I2,1 (resp. T²,2) corresponds to the concatenation of the prompt and the first response (resp. second response). Of note, RLHF is also based on the assumption that the user preference over pair of responses is governed by the BTL model (Section 2). That is, the binary observation 3/+ is sampled from a Bernoulli distribution, in which the probability that the first response is preferred over the second response is given by Here f is often referred to as the reward function, which is equivalent to the latent utility function in our setting (Section 2).
(# > 21,2] = y (fr,)) - f (x)2)))
Typically, RLHF consists of two steps: (a) learning a reward model using the dataset of user preferences and (b) fine-tuning the LLM to maximize the learned reward model using reinforcement learning. In step (a), same as our algorithms, RLHF also uses an NN h (which takes as input the embedding from pre-trained LLM) to learn the reward model by minimizing the loss function (1). The accuracy of the learned reward model is crucial for the success of RLHF (Chaudhari et al., 2024). Importantly, our Theorem / provides theoretical guarantee on the quality of the learned reward model h, i.c., an upper bound on the estimation error of the estimated reward differences between any pair of responses. Therefore, our Theorem provides a theoretically principled measure of the accuracy of the learned reward model in RLHF, which can potentially be used to evaluate the quality of the learned reward model.
In addition, some recent works have proposed the paradigm of online/iterative RLHF (Bai et al., 2022; Menick et al., 2022; Mehta et al., 2023; Ji et al., 2024; Das al., 2024) to further improve the alignment of L.M In online RLHE, the RLHF procedure is repeated multiple times. Specifically, after an I.LM fine-tuned to maximize the learned reward model, is then used to generate pairs of responses to be used to query the user for preference feedback; then, the newly collected preference data is added to the preference dataset to be used to train a new reward model, which is again used to fine-tune the LLM. In this case, as the alignment of the LLM is improved after every round, the newly generated responses by the improved LLM are expected to achieve progressively higher reward values, which have been shown to lead better alignment of LLMs (Bai et al., 2022; Menick et al., 2022: Mehta et al., 2023; Ji et al., 2024; Das et al., 2024). In every round, we can let the LLM generate a large number of responses (i.e., the actions in our setting, see Section 2), from which we can use our algorithms to select two responses 2t,1 and 2t, to be shown to the user for preference feedback. In addition, our algorithm can also potentially be used select the prompts shown the user, which correspond to the contexts in our problem setting (Section 2). Our theoretical results guarantee that our algorithms can help select responses with high reward values (Theorem 2 and Theorem 3). Therefore, our algorithms can be used to improve the efficiency of online RLHF.
F RESPONSE OPTIMIZATION IN LARGE LANGUAGE MODELS (LLMs)
As demonstrated in recent works (Bai et al., 2022: Menick et al., 2022: Mehta et al., 2023; Das al., 2024; Ji al., 2024), using responses with higher reward values can significantly improve the alignment of LLMs, especially in online/iterative RLHF where the responses generated by the initial LLM tend have low rewards. Motivated by this, we use our proposed algorithms, NDB-UCE and NDB-TS, to select the responses with higher estimated reward values for a given prompt. In our experiment, we use the following setting from Lin al. (2024): In each iteration, a user provides a prompt (context in our setting) to ChatGPT, and then ChatGPT generates 50 responses (arms in our setting). We use Sentence- BER (Reimers& & Gurevych, 2019) to get embedding representation for each prompt-response pair. Specifically, for iteration i, we use It,i (Ct, at.;) to denote the embedding representation generated by Sentence-BERR response. Of note, we adopt a reward model that is pre-trained using the Anthropic Helpfulness and Harmlessness datasets (Bai et al., 2022). For every prompt-response pair Zy,i. we use the output from this pre-trained reward model the value of the unknown reward function ((x,.). This approach
where e denotes the prompt and at,, represents the i-th
37

---

Published as a conference paper at ICLR 2025
allows to simulate the preference feedback in this experiment. Note that approach to simulating preference feedback is common the literature (Dwaracherla et al., 2024).
The embeddings Zt, used as input to trained neural network (NN) that estimates the latent reward model. Our proposed algorithms compute the reward estimate for each prompt-response pair to select the first response (using Eq. (2)) and then use it with the optimistic reward estimates of other responses to select the second response (using either Eq. (3) TS-based selection criterion for the second response). This way, our algorithms will ensure the selection of responses with consistently high reward estimates. As shown in Fig. 9, we compare the score (caleulated as the sum of rewards for selected responses divided by the number of iterations) after ' iterations (multiple 10) of NDB-UCB and NDB-TS and against two baselines: Linear variants (which uses linear model to estimate latent reward model instead of an NN): inCUCB and Lin-TS, and Random (where two responses are selected randomly). The results clearly show that our algorithms achieve the highest score (especially NDB-UCB), demonstrating the superior performance of our proposed algorithm in identifying high-reward responses.
Resporse Gprimirel
30.
Roadon
Lapkiis
HEW
HODAUCE
1.0 180
Figure Scores of different algorithms for response optimization.
The experimental results shown in Fig. corroborate theoretical results, which guarantee the selection of responses with high reward values, as also discussed in Section 4.2 and Appendix E. This result further shows that our proposed algorithms can be used improve the quality of the human preference dataset, which could then be used to improve the efficiency of online RLHF/DPO for LLM alignment. We leave it future works verify that the preference dataset with high-reward responses collected using our algorithms can indeed lead to better LLM alignment, which is beyond the scope of the current work (since the focus of this work primarily theoretical) and will require significantly more extensive experiments.
38


Reviews:
[{"review_id": "UvyvoKR6X4", "reviewer": "Reviewer_nPZh", "summary": "The paper studies the challenge of modeling dueling bandit problems where the reward function is non-linear. Traditional algorithms assume a linear reward function, which can be restrictive in real-life applications like online recommendations or web search rankings. The authors propose using neural networks to estimate the non-linear reward function using noisy preference feedback. They introduce upper confidence bound (UCB) and Thompson sampling (TS) based algorithms with sub-linear regret guarantees for efficient arm selection. Their theoretical results extend to contextual bandit problems with binary feedback, provide meaningful discussion with LLMs and experimental results on synthetic datasets support their theoretical findings.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces neural network-based methods to estimate the non-linear reward function using preference feedback observed for previously selected arms. The paper proposes two algorithms: one based on UCB and another based on TS. Both algorithms are equipped with sub-linear regret guarantees, ensuring their effectiveness in selecting the best arm over time. Moreover, the authors provide the interesting discussion with contextual bandits with binary feedback and RLHF.", "weaknesses": "However, for the regret analysis, the authors still require the NTK gram matrix to be positive definite. This assumption can be a limitation in real-world applications, as it can be easily violated by repeating observed arm contexts, thereby hindering the practicality of the proposed methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "sH3GMy8G3h", "reviewer": "Reviewer_uMSZ", "summary": "In this paper, the authors extend the contextual dueling bandit formulation to neural bandit settings, where the reward function is arbitrary and does not assume linearity. To address this task, they propose two methods based on the existing NeuralUCB and NeuralTS algorithms. Both theoretical and empirical analyses on synthetic datasets are provided.", "questions": "Please refer to \"Weaknesses\" above.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The application of neural bandits to solve real-world dueling bandit problems is intuitive, as existing linear contextual dueling bandit algorithms may fail to capture complex reward relationships.\n\nAdditionally, the analysis of neural bandits with binary feedback may be of particular interest to the bandit research community.", "weaknesses": "Firstly, my concerns are with the problem formulation and theoretical analysis. I will list a few below. For instance:\n\nIf my understanding is correct, the problem formulation heavily relies on the link function $\\mu$, whose properties significantly influence the regret bound, particularly through terms such as $\\kappa\\_{\\mu}$ and $L\\_{\\mu}$. Furthermore, unlike conventional stochastic bandit works, this paper assumes the reward feedback associates with the sub-Gaussian noise, which in this case, depends on the chosen link function. Typically in stochastic bandit settings, sub-Gaussian noise is independent of the learning formulation and is determined solely by environmental settings, which makes this formulation unnatural.\n\nAdditionally, in Assumption 1, $\\mathcal{X}$ is not clearly defined. Does $\\mathcal{X}$ represent the entire arm context space with $\\mathcal{X}\\_t \\subset \\mathcal{X}$? If so, how would the learner possess prior knowledge of $\\mathcal{X}$ to select the optimal $\\kappa\\_{\\mu}$ value for exploration (i.e., the $\\beta\\_T$ term in Equation 3)? A similar issue also exists for $\\tilde{d}$, as it is unrealistic to assume the learner has prior knowledge of this parameter.\n\nThe theoretical analysis appears to rely heavily on the proof framework of NeuralUCB and NeuralTS, adapting assumptions like the positive definite NTK matrix for arm context. The authors also mention the $c_0$ term, representing gradient differences between arm contexts in Theorem 2. This term should be clearly shown in the regret bound, as its data dependence could lead it to grow with $T$ and should not be hidden by big-O notation.\n\nAll experiments are conducted on synthetic datasets with predefined configurations. While the authors claim the paper is motivated by dueling bandit applications in LLM tuning, no experiments are included to support this claim. Furthermore, the theoretical analysis may not align with real RLHF settings, particularly given the strong over-parameterization assumption, which may not be realistic. In practice, each arm could be a generated response from an LLM, with high-dimensional vector representations and complex reward mappings. While RLHF methods like DPO employ powerful neural architectures, the analysis in this paper assumes an MLP, which may be insufficient. Therefore, I believe real dataset experiments relevant to LLM tuning, as indicated by the authors, are necessary.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "o1cY8RqBpE", "reviewer": "Reviewer_aXCy", "summary": "The paper titled *Neural Dueling Bandits: Principled Preference-Based Optimization with Non-Linear Reward Function* tackles the challenge of dueling bandits in contexts where the reward function is non-linear—a common scenario in real-world applications like recommendation systems and search ranking. The authors propose leveraging neural networks to model these non-linear reward functions based on preference feedback. They introduce two algorithms, *NDB-UCB* and *NDB-TS*, which are extensions of the Upper Confidence Bound and Thompson Sampling frameworks, respectively. Both algorithms come with sub-linear regret guarantees. The paper also extends the analysis to binary feedback settings and discusses implications for reinforcement learning from human feedback (RLHF). Theoretical results are supported by experiments on synthetic datasets.", "questions": "**Real-World Dataset Evaluation**: Have you considered evaluating your algorithms on real-world datasets, such as those from recommendation systems or search logs, to demonstrate their practical applicability and effectiveness?\n\n**Computational Efficiency and Scalability**: Can you provide insights into the computational complexity of your algorithms? How do they scale with the number of contexts and arms, and are there strategies (e.g., model compression, online learning techniques) to mitigate computational overhead?\n\n**Comparison with Other Non-linear Methods**: How does your approach compare to other non-linear bandit algorithms, particularly those leveraging Gaussian processes or deep kernel learning? Including comparisons with these methods could strengthen your empirical evaluation.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**: The paper makes a significant contribution by extending the dueling bandit framework to accommodate non-linear reward functions using neural networks. This advances the field beyond the limitations of linear assumptions prevalent in prior work, allowing for more realistic modeling of user preferences.\n\n**Theoretical Rigor**: The authors provide rigorous theoretical analysis, deriving sub-linear regret bounds for the proposed algorithms under standard assumptions. Extending these results to binary feedback settings enhances the robustness and applicability of their approach.\n\n**Practical Relevance**: By addressing non-linear reward functions, the work is directly applicable to practical domains such as recommendation systems and web search, where user preferences are inherently complex. This increases the algorithms' relevance and potential impact on real-world applications.\n\n**Clarity and Structure**: The paper is well-organized and clearly written. It presents the problem, proposed solutions, and theoretical foundations in a logical and accessible manner, making it easier for readers to comprehend the complex concepts involved.\n\n**Impact on RLHF**: The exploration of reinforcement learning from human feedback broadens the impact of the work. By aligning AI systems more closely with human preferences, the paper contributes to an important area of AI research focused on ethical and user-aligned AI.", "weaknesses": "**Experimental Validation**: The empirical evaluation is limited to synthetic datasets. Testing the proposed algorithms on real-world datasets would strengthen the claims regarding their practical utility and effectiveness.\n\n**Computational Complexity**: The paper lacks a detailed discussion on the computational demands of the algorithms, particularly concerning the training of neural networks in an online setting. Insights into scalability and efficiency are essential for practical deployment.\n\n**Baseline Comparisons**: While comparisons are made with linear dueling bandit algorithms, the paper does not benchmark against other non-linear methods (e.g., those using Gaussian processes or kernel methods). Including such comparisons would provide a more comprehensive performance analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "3IcC6xW29E", "reviewer": "Reviewer_kAG9", "summary": "This work studies dueling bandits based on neural networks. UCB and TS algorithms are suggested, and sublinear regret bounds are achieved for both algorithms. The theoretical analysis is robust as well.", "questions": "The reviewer notes that while the suggested setup differs somewhat from previous works (Zhou et al., 2020; Zhang et al., 2021), the analysis appears to be quite similar, based on the main manuscript. Although certain distinctions are mentioned in the introduction, the reviewer finds it challenging to identify the specific differences. Could you clarify more explicitly the technical novelty of this work compared to the existing literature?\n\nAs the authors provide two algorithms, the reviewer would like to know some comparisons between these two. While some comparative simulation results are provided, could you also include a more qualitative analysis, incorporating some mathematical insights, to highlight the differences between the two algorithms?\n\nFor regret analysis, what kind of regret is analyzed between average instantaneous regret and weak\ninstantaneous regret?\n\nFor TS, what do we do if the first and second arms are the same?\n\nCould the authors define the matrix H in any way? What are the differences between H and H’?\n\nIn Assumption 2, [x]_k = [x]_k+d/2, [] is used for multiple purposes, making some confusion. It should be defined clearly.\n\nL191: Is \\phi is g? Could the authors please explain why a different notation is needed if they are the same?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This work provides theoretical results of two mainstream algorithms, UCB and TS, for neural dueling bandits. These results are significant contributions to bandits.", "weaknesses": "Overall, this paper is difficult to follow due to the use of numerous quantities and notations that are not explicitly defined. Given the long-standing history and inherent complexity of neural network analysis, it is understandable that some notations and intermediate reasoning steps are abbreviated. However, the reviewer believes that enhancing clarity would greatly improve readability for uninitiated readers.\n\nL59-63: Could you be more specific?\n\nL85-94: Since many readers may be unfamiliar with dual bandits, the description should be more detailed. For instance, the authors should clarify that the learner selects two arms from the action set with multiple arms, plays both arms, and receives feedback from both, which is captured as the preference y_t. It would be helpful to emphasize how this differs from standard contextual bandits. Additionally, the authors introduce the context-arm set X_t. As the reviewer understands, this is no different from setups where either an action or context set is considered as long as a context and action pair is in R^d. Is there any technical distinction between the two? If not, this setup seems to introduce unnecessary complexity.\n\nL95-111:  The authors stated that the logistic function is considered as the link function, but stated in Assumption 1 that a class of link functions satisfying two conditions is considered in this work. For the reviewer, this description is confusing. \n\nL112-120: As these regrets are not common in other literature, regret should be better explained with the basic ideas of regret.\n\nCould you provide more specific practical applications of dueling bandits?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)