Efficient and Near-Optimal Algorithm for Contextual Dueling Bandits with Offline Regression Oracles
Authors: Aadirupa Saha
Robert E. Schapire
Venue: NeurIPS 2025 poster ()
Keywords: contextual dueling bandits
relative
dueling feedback
preference
offline regression oracle
regret minimization
continuous decision spaces
Primary area: theory
TL;DR: We design the first efficient, near-optimal regret algorithm for contextual dueling bandits using offline oracles, enabling scalable preference-based learning in RLHF and resolving a key open problem in AI alignment.

Abstract: The problem of contextual dueling bandits is central to reinforcement learning with human feedback (RLHF), a widely used approach in AI alignment for incorporating human preferences into learning systems. Despite its importance, existing methods are constrained either by strong preference modeling assumptions or by applicability only to finite action spaces. Moreover, prior algorithms typically rely on online optimization oracles, which are computationally infeasible for complex function classes, limiting their practical effectiveness. In this work, we present the first fundamental theoretical study of general contextual dueling bandits over continuous action spaces. Our key contribution is a novel algorithm based on a regularized min-max optimization framework that achieves a regret bound of $\tilde{O}(\sqrt{dT})$—the first such guarantee for this general setting.  By leveraging offline oracles instead of online ones, our method further improves computational efficiency. Empirical evaluations validate our theoretical findings, with our approach significantly outperforming existing baselines in terms of regret.

Efficient and Near-Optimal Algorithm for Contextual Dueling Bandits with Offline Regression Oracles
Aadirupa Saha"
Robert E. Schapire Microsoft Research
University of Illinois, Chicago aadi rupa. saha@ $ com
schapirremiccroooff.ccm
Abstract
The problem of contextual dueling handits is central to reinforcement learning with human feedback (RIHF), widely used approach in Al alignment for incorpo- rating human preferences into learning systems. Despite its importance, existing methods are constrained either by strong preference modeling assumptions by applicability only to finite action spaces. Moreover, prior algorithms typically rely on online optimization oracles, which are computationally infeasible for complex function classes, limiting their practical effectiveness. In this work, we present the first fundamental theoretical study of general contextual dueling bandits over continuous action spaces. Our key contribution is a novel algorithm based on a regularized min-max optimization framework that achieves a regret bound of Ó(VaT) the first such guarantee for this general setting. By leveraging offline oracles instead of online ones, our method further improves computational effi- ciency. Empirical evaluations validate our theoretical findings, with our approach significantly outperforming existing baselines in terms of regret.
1 Introduction
Preference- -bssn feedback is widely used in applications like online retail, prediction markets, tournament ranking, recommender systems, search optimization, robotics, and multiplayer games. Compared to ordinal or absolute rewards, it often provides more reliable insights, such as in book summarization (36]. training language models like ChatGPT and LLAMA [9], and designing robotic reward functions via trajectory preferences [2] . A well-studied variant of the multi-armed bandit model [4] (1), the dueling bandit problem, addresses decision-makinn under pairwise preference feedback with noise and limitations. has been key research area for over decade 43 29 7 26).
aiming identify 'good' arms by actively gathering preference feedback from chosen item pairs.
With the success of reinforcement learning with human feedback (RLHF) 12
a key tool for
aligning language models with human values and designing AI behavior, interest in the theoretical foundations of personalized learning with preference feedback has grown, particularly in contextual dueling bandits. The fundamentals of dueling bandits and their generalizations have been widely studied in the bandit and learning theory literature 41 3
A major limitation of dueling bandits is the assumption of a fixed preference relation P. whereas real-world preferences vary with context (e.g., user demographics, search queries, seasonal trends). Studies on non -tatiiot preferences often benchmark against the best single item in hindsight, as in adversarial dueling bandits 29, 18) which is often unrealistic. Some approaches mitigate this with a dynamic regret objective, competing with the best action per round
(2 19], but these require impractical knowledge of non-stationary complexity measures [10]. Moreover, such measures can be large, potentially linear in OTT). and fail leverage contextual information effectively. development of the line of contextual dueling bandit research is given in Table 1.
In the study of contextual bandits 32 [6], the primary focus has been on value reward feedback. However, there is a notable searcity of research concentrating on preference or relative feedback (i.e. in the dueling bandits framework). Some recent attempts address the problem of linear contextual
corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

dueling bandits for linear score- based preferences (25 8 34 however, due to the restrictive linearity assumption, or lack of reasonable performance guarantees, are often far from practical deployment.
Seeking inspiration from these system needs, the work of [14] first formulated the problem of contextual dueling bandits for any general context space and preference relations. However, their proposed algorithms are either computationally intractable that use the computationally inefficient EXP4 algorithms or yield suboptimal ( regret bounds. [30] resolves the above limitation of [14] by proposing a computationally efficient and statistically optimal algorithm for contextual dueling bandits, under a natural 'realizability assumption,' that assumes that all the preference relations (Pys) can be approximated by (suitably large) function class M. (1). One of the caveat in their result was it requires access to an online square loss regression oracle for M whose Ttep square loss regret, M (T), needs to be 'small" (o(T) for reasonable regret guarantee.
Feedback
Runtime
Regret (Optimality)
Oracle
Reference
Setting Efficiency
Type/Calls
(Contextual)
ILTC8
Bandit
Efficient
O V KT (TIn))
Offline oracle
(reward)
(II: Policy classs)
Öly KT/ //ng (Fi) calls calls
Squa reC8
Bandit
Inefficient
O (FF
Online oracle
16
(reward)
Optimal (up K or log factors)
O(T) calls
FALCON+
Bandit
Efficient
0 ( /KEarr
(T)
Offline oracle/ (log
62
(reward)
Optimal (up to K or log factors)
or O(log log T) calls
1pprringgXP4.. P.P
Dueling
Inefficient
o (V (CT log (TilI))
N/A
14
preference
Optimal (up to log factors)
Max mp
Dueling
Inefficient
O( /dT log
Online
25
preference
Optimal (up to log factors)
O(T) calls
Mi Ma
Dueling foedback
Efficient
o OlyKEannww
Online
Optimal (up or log 7 factors)
O(T) calls
MMonater
Dueling
Efficient
O (Ky (or.. (
Offline oracle/ (log T)
(this paper)
feedback
Optimal /K and log T factors)
or Olog log T) calls
Double-Mord KKonseer-o Inf (this paper)
Cont space
Efficient
O (dv/T log
Offline oracle/ Oloo T)
ducling
Optimal (up log factors)
or Ollog T) calls
feedback
Table 1: Developments in Contextual Dueling Bandits. EO Averaged regression loss of the online square loss regressor over T rounds for the function class F. EMH.M (F,TTF) Expected regression loss of the offline square loss regressor upon T samples for the function class F and confidence parameter 8. Ö(-) hides logarithmic factors in the O(-) notation.
Offline regression oracles work on static datasets, where all input-output pairs are available upfront. The goal is to find the best-fitting function using the entire dataset at once. The oracle can not fit new data points outside the training distribution, making it suited for batch learning tasks.
Unlike offline regression, an online regression oracle operates in a dynamic setting where data arrives sequentially and the model must adapt real-time, making significantly more powerful but also substantially harder to design-especiall for general function classes where achieving low regret is often infeasible. For example, no online oracle exists for the class of one-dimensional linear threshold functions due to its infinite Littlestone dimension [23 Example 3], and similarly, the class of all non-decreasing [-1,+1] +1]-vllued functions over IR is not online learnable despite admitting simple offline oracles [22 Example 1]. Further (2). the second major limitation of the work lies in their algorithm only applies to finite action spaces of size K. It's not generalizable to continuous decision spaces, which is, however, a much more practical and realistic scenario to work
Noting these precise limitations of the prior works, the natural question to ask thus whether an optimal regret general (continuous) decision space contextual dueling bandit algorithm can be designed with an offline regression orucle? Note the task of incorporating offline oracles with online learning algorithms is particularly challenging since due to the interactive nature of online learning algorithms, the data generated by the algorithm could arbitrary (not necessarily following specific distribution), which makes it much harder to use offline oracle. There lies of the main contributions of this work. Towards this, we first analyze the (i) Best- Rest-Res regret for finite K -armed contextual dueling bandit, and further extend the setting to (ii) The more practical framework of continuous decision space with potentially infinite arms.
2

---

1.1 Our contributions
(I), Warm-Up: Best-Response Regret with Offline Oracles: Our first contribution in proposing new efficient algorithm for contextual dueling bandits with offline regression oracle. To state the guarantee, let X be a context space, let A == [K] be an action space of size K, and let P(i,j] -P Plú, 0} denote the of preference matrices, P (P E 1-1, which are skew-symmetric matrices with bounded entries and 0 along the diagonal. In a stochastic contextual dueling bandit instance, the learner interacts with distribution D over X P via the following protocol: at each round & (1) nature samples (zz, Pt) ~ D and reveals 22 to the learner, (2) learner chooses (potentially randomly) two actions (at, b.) E [K]P, (3) learner observes
or ~ Ber( ( ), where Ber(-) denotes Bernoulli random variable. Thus O, E {0. 1 indicating the preferred feedback between de and by At each round 6, the goal of the learner is choose dueling action pair (a,,b, and minimize the performance loss against the dynamic best-action for Te over T rounds (see Objective-1, Section 2)
For this problem, we propose an algorithm in Section 4 with the following regret performance:
Theorem 1 (Main result: Best-Response Regret (informal)). Under 'realizable' preference functions and assuming the existence of a 'strongest (set of) best item(s)', with probability at least (1-6) for any 5 E (0, 1), the best-respont regret (BR-Regr)) of our algorithm Double-Monster (Algorithm
after T rounds is bounded by: O K EORMM
(IÉT. for any T E N4, where Eost, ().
denotes the estimation square loss of the regression oracle when trained on n iid instances, with confidence probability at least 1 1-5. 5.
We introduce the problem and the assumptions more formally in Section and Section
(2) Main Results: Best-Response Regret in Continuous Decision Spaces: We further extend the results of Theorem 5 to continuous decision space K. C Rd, where each action
I. is represented by a d-dimensional embedding. Assuming continuous action spaces makes the setting suitable for real world problems like recommender systems language models where the action set is often large, and potentially infinite. In this case, the preference relation of any action pair (a, b) under Pe is defined as: (a b) = o (s( a) - s b)). where a denotes the sigmoid function. The scoring function comes from a realizable function class +, a set of functions mapping X' to I&,, such that for any action a E IC and context X, we have E(s( a) Ir, a
(0b (z), a) for some unknown mapping 6² 4. A detailed description is given in Section 2 We propose an algorithm for this general problem Section 6 with near-optimal best-response regret bound (up to log factors).
(3) Experimental evaluation: We also report experiments to validate our theoretical analysis and runtime efficiency of the proposed methods (Section 7p and Appendix E
2 Problem Setup
Notation. Let [n] == (1, .... for any E N. Also [n]] [m] x [n] denotes the cartesian
nn.
product of [n]] with itself. We use lowercase bold letters for vectors and uppercase bold letters for matrices. L2 denotes the d x d identity matrix. For any vector E Rd ||x|| denotes the &g norm of
x. A, == (p E [0, 1]m Σn p(i) = 1, p(1) Z 0, Vi E [n]] denotes the n-simplex. c; denotes the i-th standard basis vector in R". If lfpe Anx is a joint distribution over [n] x [m]. then we denote
by pe and p" respectively the left and the right marginal of p, defined as p (1) = Σ p(i.)) and
pr( = EK= p(i In this work, we consider the zero-sum representation of preference matrices: P. = (P E 11-1,]_xx P[i.j] - -PGj a), P(i, i] 0, Vi.j E [na]].
Note any P E P can be viewed as a zero-sum game, where the two players, called row and column player, simultaneously choose two (possibly randomized) items from [ro]. with their goal being to respectively maximize and minimize the value of the selected entry.
Setting. We assume any arbitrary context set X, an action space of K items denoted by A := [K],
and a function class M C [M| M : X' + Px) }. all known to the learner ahead of the game. At
FStandard dueling bandit literature represents preference matrices Q E [0, 1|"x", such that Q j.. indicates
the probability of item i being preferred over item j. Here Q satisties Qli - 11 - QQj i] and Q = 0.5. Note both representations equivalent as there exists one to one mapping P = (2Q - 1) E P 77
3

---

each round, we assume a context-preferent pair Pr) ~ D is drawn from joint-distribuionn D. such that 2, X, and P. Px- We will denote the marginal distribution of the context X as Dx. The task of the learner is to select an action pair (at, E [K] [K] upon which a relative feedback Or E {0, 1] is revealed according to Pt; specifically the probability that o, is preferred over b. indicated by = 1, is given by Pr(o, = =1) b.] and hence Pr(o: = 0) = L-Pafa.be)
2
Assumption 1 (Realizability). Consider a function class M (M M X + Pk } consisting of mappings from context X' to preference space Pk. Realizability assumption entails EM E E such
that Va, b [K] and any x E X, we have E(a.P)-D|P(a.
x] M (=) (a)
Objective (1): Best- Best-Response Regret [30] Assuming the learner selects the duel (at, be) P AK at each round. i, we measure the learner's performance via a notion of best response regret:
1
BR- BR-Regr
Ea
max
E Ba-q
R
(ac (M)) as] + M (aa)) be]]
2
where Dx denotes the marginal distribution over X.
Objective (2): Best-Response Regret for Continuous Arm Spaces In this setting, we relax the assumed of finite K K-armed action space and assume general continuous (potentially infinite) decision space X C RR. In order to model the preference relation for an action pair (a, b) E K. x K:: We further assume that given any context F2 each action a, E K. first gets assigned to a stochastic score 8t E [-1,1]] such that E 8t F₁ = I, a = al (a, o (zr),, where o" : X + RRd is a unknown mapping that embeds every context to d-dimensional feature space. In particular, with the realizability assumption, one can typically assume the learner has access to a class of functions S {Ø X + [R such that 6² E Ø. Then at time t, the preference relation of any action pair (a, b) under the above realizable score setting is: Pa b) (+) denotes the sigmoid transformation, i.c.
((' - b)), where (o(x) = T+e-a Vo E R). Similar to before, the learner's 's task to select an action pair (a,, by) E K. x IC time t, upon which a relative feedback or E {0, 1 ~ Ber(Pr (a,, b.)) is revealed according to P,.
Under this model of continuous action space IC, one could define best-response regret as:
T
max o²"xx))) ((a, + by), di (are))
BR-Reg (cont)
Dx
2
3 A Primer on Regression Oracles
We now introduce the concepts of offline and online regression oracles to familiarize readers with their structural disparities and performance--elatee distinctions.
3.1 Offline Regression Oracles [32
Consider any abstract input space and output space y. Assume a given dataset Dn := ((2). 3/ )2
consists of n data points, each (input, output) pair (2,,3) sid D being drawn iid from a fixed
underlying distribution D on Z x y. Given general function class F C {f I Z + }}, a general offline regression oracle associated with F, denoted by Of OffReg an algorithm, operates on the given dataset D, and outputs a mapping f: Z + V. In learning theory, the quality of f is measured by its "out-of-sample error," i.e., its expected error on random and unseen test data.
Assumption 2 (Guarantee of Offline Regression Oracles). Consider general function class F C (ff:: 2 + y}. Then given a dataset Dn == {(z,, v:) Vi that consists of n data points, s.t. (ze, M.) sid D. we assume that the output fn + offReg=(Da) of the offline regression oracle OffReg satisfies that: For any ö E (0, 1], with probability at least 1 - 5,
( (fn(=)-u)}
inf (f(2) (()))-)) (f())-
< (of
fer
where Eoit, n) denotes the square loss of the regression oracle when trained on n-iid instances.
Assumption uuder Realizability, Moreover, if we further assume realizability, in the sense that there exists f E F such that (=) (a [y =), then it is well-known that Assumption further implies: For any ō E (0, 1]. with probability at least 1 - ō, we have
E (( (fn(=)= - [3)) S Eo n).
(1)

---

ver Remark 2. The advantage of an offline regression oracle is that it can consider all the data available for training, the training data is generated iid from some underlying distribution and therefore, can often produce more accurate model. See Remark for for the advaniuges of offline regressors. Conversely, online regression is a real-time processing approach that involves analyzing data as it becomes available, updating the model as new data points arrive. Thus finding efficient online oracles for any arbitrary function class could be much harder compared to its offline counterpart (e.g. see 123 Example 3], [22 Example 1]) See Appendix A for detailed discussion.
4 Warm-Up: K-Armed General Contextual DB with Offline Oracles
This section presents our algorithm for the contextual best-response regret (Objective-1 in Section 2
Double-Monstent Key Algorithmic Ideas. To adapt with the offline regression oracle, our algorithm runs in epochs, with a specific (and predetermined) epoch schedule, where the offline regression oracle is called only at rounds 71, 72. ....... and each set of rounds between Tm-1 + 1 and Tm is considered to be within the m-th epoch. For example, if we set fm 2n our algorithm runs in Olog T') epochs for any unknown T, but one can also use more complex epoch schedules, such as Tm 27 which results in only Olog log 7') epochs and oracle calls.
At the beginning of each epoch m, the algorithm computes estimated function M,, using the offline arg minMEM E 2+1 (M(r)) [a,, bz] - o,)². We next assume access to an algorithm Convex-Constrre nt- Sol ver, which is a randomized algorithm that for given X, M .M and y R. outputs joint distribution p E Aкxк, such that:
regression oracle: M. :=
Ba-p' M(r][,, al] + Em- [M
+
2 1
5K2
Vi.j E [K]
(2)
7 p(i.j)
where recall we denote by pd and p" respectively the left and the right marginal of p. defined as ΣØ= =
j(i,j) and p² = = j). Note p being the solution of (Ø) + K-convex con- straints, such a solver can be designed computationally efficiently using standard tools from convex programming. Moreover, in Appendix justify that a E Δκ will always exist. Now, at any time / in epoch m, given the context xy the estimated least square function estimate Mn, and some tun- ing parameter "/ (exact expression is given later), we query the Convex-Const with the triplet (va, Mm: 7m) and obtain pa E Δ using:
Pi Convex Convex-Constra serrrainnttoovee(er Mm, 7mm
(3)
Next, the algorithm samples duel b., P Noting Eanq Mm (x,)
(xx(2) Dr can be alternatively expressed as:
5K2
Mm (1e) + q" (M:)))P +
Einqgiq'
Vq and q' E Ax 7'm
(4)
Pi
(t(),))
which implies the mixed strategy p, a 'nearly unbeatable by any pair opponent q and q' the zero-sum game Mm. (x:). Recall, any distribution p* E AK is a Nash Equilibrium of a symmetric zero-sum square matrix P E I R if vq E AK : PP' S 0 unbeatable. However, to incorporate the additional 'explorative component' of p. need to ensure () has significant mass based on the quality of action i and j. This is enforced through the term Pe(E.) in Eq. (4h. In Appendix B.2 prove that Eq. (2) always adheres valid solution and hence one can always find Pt for Eq. 4 The pseudocode is given in Algorithm 7 in Appendix
[ and Nash strategies are
4.1 Performance Guarantees of Algorithm
Useful Concepts towards proving Theorem 5 We analyze the regret of Algorithm iin Theorem but need to define some concepts before that.
Definition 1 (Policy Class). A standard policy class II := {T π. : Ax is set containing all the mappings from context space X to the K K-simplex. Further we also define by policy class 112 = [ π X + AK*K) } set of all mappings from context X to K. x K K-simplex.
5

---

For any policy æ II we denote by T(i x) the i-th component of vector π (2), Vi E [K], E X. Similarly, for any policy π II2, we denote by π(i.j æ), the i, i,j-th component of the matrix (x:). Definition 2 (Decision policy of Epoch-m), At any epoch m and x E X, the decision policy of epoch is defined mm :I:: (x) t-
-eaiint-Sooo verle,, M 7m).
Note that at any time in epoch m. Tm (Iz) Ps. where Pt is as defined in Eq. 3 Thus am II?
We will further denote by T T. 1I the left and right marginal policies of m defined as: T (a)
x)) =
Ex
E/= Tm (i.j x)) and T (i = ExwDx E (i. [r) Vi,j E [K]
Definition 3 (Instantaneous Regret against a Fixed Policy). For any arbitrary preference relation M E M, we denote the regret of policy π against 't' as:
RegM πT' E (T()) (x))+(()))
In particular, for M = M Reg(RT π') Regm- (T,, x') defines true regret of policy π against n'' and for M M.. Regg... (TI, n²) simply denotes the instantaneous empirical regret of ı against '' in epoch m. For simplicity, we denote Regm (T, n²' Reg (TT, T').
Further since for any E Pk. ie. Pii,]] = -Lj i]. Vi,j E [K] x [K]. we note that: Remark 3 (Properties of Policy Regret), For any pair of policies and n² E II: (1) Reg( n²) Reg'(T', x). (2) Regm. (TT, TT' Regg (Tr', πT).
Definition 4 (Best-Response Policy). We let rb" : II M - II be best-response policy, mean- ing, for any context
X, policy π E II and function M E M, (T( maximizes Eornpaann(z) [M(x)(a* al] PMM(2))((Z over P E Ag. More precisely for any æ X.
and M M, 2p* [TT, M (I) II can be defined as:
46" [T, = arg max p (M(x)x(z) PEλx
Note that the due linearity of the above objective, the corresponding argmax always occurs of the K extreme points of K -simplex Åк-
Definition (Instantaneous Best Response Policy Regret). For any arbitrary underlying preference relation M E M, we denote the instantaneous best-response regret of any decision policy π E II as:
BRegM( = EENDx
max p' ((() p'EAx
In particular, for M M" BRegM- (T) denotes the instantaneous true best-response regret of any decision policy π IT. For simplicity we will denote BReg(T) = BRegM- (Tr). Further for M = Mm, BReg (x) simply defines the instantaneous empirical best-response regret of π in epoch m. For simplicity, we will BRegm (T)) BReg (T)).
Remark Note that for any II, one can write
BReg( Reg((b" (Tr Mr,,,,,,,, and BRegm (Tt) Reg( ab" (1""("rr [T, Mm),
This implies that the instantaneous true and empirical regret of any fixed policy against its corresponding best response policy, respectively yield the instantaneous true and empirical best response regret of
Assumption (Idempotent Responess (IBR)). A function class M: X + said to satisfy Idempotent Rest-Res for all M M and all π 11, BRegM (1b" [T, M)) = 0.
Roughly speaking, any preference matrix with 'total-ordering'. where there a specific un- derlying ranking of the K items, satisfies the above structure: The class of random util- ity (RUM) based preferences 5 27,, or matrices with strong stochastic transitivity (SST)
[2). always satisfies the above property. However, the class 'Idempotent
Best- Rest-Response' is larger, in particular, any preference matrix, which has
set of equally strong best items also satisfies the structure. The figure on the right shows the dependencies of different preference classes. We
RUM
SST
IBR Preferences
Preferences
Proferunces
state our main result towards analyzing Algorithm

---

Theorem 5 (Regret Analysis of Algorithm D.. Consider any function class M that satisfies Assump-
tion] 3 Then under realizability (Assumption D. and with an epoch schedule T....., mm such that
Tm 2 2 for & log T, with probability at least (1 - 8 for any d E (0, 1) the best-response regret (BR-Regr) of Double-Monsted after rounds bounded by:
(()
M (6/ Tm-1 - Tm 2m Tm-11)
(5)
Corollary 6 (Theorem for Special Function Classes), Algorithm@yiela the following best-response regret guarantees for some of the special function classes:
For finite M, for the choice of 5 = 1/T, the regret of Algorithm is bounded by O(K /Tog [[M[[llog]] The results follows since for finite M, we have offline regres- sion oracles with EoH.M((, n) 0 [og(l>M)a) no
B21. For completeness, the proof is given in
Appendix C.5
For a general, potentially nonparametric function class F with empirical entropy is O(e")), VE > 0 for some constant p > O, results of [40] and (24] gives offline regression oracles such that 2/(2+)) -(m=2/((4+) O(
log(1 (1))). Again assuming T/T, this implies a regret bound of Eoit, M 1+n log I') of Algorithm for this function class.
O(KTF
For low dimensional linear predictors F = {(x, b) + 10.66 2z o. b)) : :0 E RR 1011 S 1}.
instantiating OffReg as the least squared estimator 39 13 and ó 1/T, the regret
guarantee of Algorithm becomes
[15] gives regression error bounds for deep neural networks for F GK being the class of Multi-Layer Perceptrons (MIP), and (x( a, (x)) for X, n, E [K]. Assume that 'D continuous distribution [-1, and Pa.b lie in a Sobolev ball with smoothness
N, by
Theorem of 15 deep MLP-ReLU network estimator attains Eoft. 8) = Ö(n Dia log 1/5) 22d estimation error. Consequently, the regret bound of Algorithm boils down to Ö(KT 25428 regret.
Regret Analysis of Double-Monster. Proof Analysis of Theorem 5
Towards proving Theorem 5
will first prove Lemma 7 that guarantees on the empirical regret performance of Algorithm But it will be worth introducing a few more notations first:
Definition 6 (Decision variance). For any two policies TT, T2 E II the decision variance of TT, T2 with respect another decision policy t E III is defined as: V (x(T1, E Ex Ti (ala))
a(a,blu)
Intuitively V*( т2) captures the selection-variance of से for any expected duel (a, b) played by the joined policy πI, π2. particular, when the base policy ग = Tm, for any epoch m, we will use the shorthand notation Vm (TT, πT2 to represent V= (TT1 722..
Lemma 7 (Properties of decision policy nm in Algorithm D. At any epoch m, Vn, n E II, the decision policy of epoch m Tmm satisfies:
5K2
BRegm (TT)) + BRegm (TT)
Yim
2vm (T, X') 5K2 7m ( тT) Vm Ymg,enn. (TT), T²).
Lemma 7 establishes an important result for bounding the empirical performance of the decision policy Wm- for any epoch m: Precisely it shows that the empirical best response regret of πm is bounded by O(K2//in /mm) and the decision variance of any pair of policies π, π' w.r.t. T. is bounded by empirical regret bound and n' against n. The proof is given in Appendix B
5.1 Relating Empirical Performance to True Performance through Decision Variance
We will first show how to relate the true and empirical performance of any policy terms of their corresponding decision variance, as given below:
7

---

Lemma 8. For any epoch and any two decision policies π and π²'
V (T', π
3k
Reg(I' n πT) Reg... (T'',
37m
47m
Proof of this lemma is deferred to Appendix C.2 We note that Lemma 8 further implies:
Corollary 9. For any epoch m, and any policy π
BReg(( (m) + BReg (TTe)((m))))))) [BRegm (TT) + BRegm (Tm)
Vm- (T Mr TTm Vm- 8/5 [TT M
π
3K²
3/m
2mm
5.2 The Recursion: Bounding Empirical Regret by True Regret and Vice-Versa:
Using Corollary 9 we now prove crucial recursive relation between empirical resp-nes and true best-response regret for any decision policy any epoch m. This lemma ensures that the estimated empirical (best-response) regret of the algorithm's 's decision policy mm becomes more and more accurate and eventually matches its true best-response regret for large m.
Lemma 10 (Epochwise Recursion). Let π be any policy in 112. Then all epochs m E N4.:
BReg( n ) (Reg(T"))) (T) < 2BReg (TT" + 2BRegm (TT")
+ 11K2
/ 7m/
BRegm ( BRegm (T²) < 2BReg(Tr (T²) + 2BReg (T")
+ +1K22 111K2//m //m-
Given Lemma
10
Theorem follows by combining with Lemma
Complete proof is given in
Appendix C.4
Main Algorithm:
General Contextual DB for Continuous Action Spaces
In this section, we extend the results of the previous section to continuous action spaces KC C Rd as defined in Objective-(2), Section 3). We present our algorithm in Algorithm 2 which is shown to yield Ö dd) contextual best-response regret as analyzed in Theorem 11 We explain the key ideas behind Aggorithm@jbar below detail but it would be useful introduce few notations before that.
For a set X, we let A(X) denote the set of all probability distributions over X. If X is continuous, we typically denote A (X) the of all probability measures the measurable space (X, B), where B is the Borel o-field on the set X. Further, for any E N., we denote the n-simplex by An, So, X is finite, A(X) D|i I, denotes the identity matrix of dimension n for any n N.. We use ||x|| (or ||x(|2) to denote the euclidean norm for IRd, For any positive definite matrix H E Idd we denote the induced norm on æ E Rd by ||x|| = (x, Hx), and det (H) represents the determinant of matrix H.
Additional Notations:
Algorithm 2 Double-Konster-Ite (for Continuous Action Spaces)
< ... Confidence parameter Tuning parameter c, "Y 72.... 2: Arm set: K. Rdd An instance of offg for function class
1: input Epoch schedule
3: for epach m 1, 2,.. do
Vd
4: Set Tmm
2 2 2- (f/(2m²), Tm-1 Tm-2) (for epoch 1,7 1).
)-== 5: Compute om + offReg ((0r, ar, br), m== ) i.c.
6n arg minge@ mm 2 (o((((())))
b,)) o.)² via the offline least squares oracle
6: for round = Tm-1 + 1,... Tm do
7: Observe context
X.
8:
Compute p. Cont Soont-rrCoostraint--Boo
Om, 7mm ie::
pa argmax (abyq om (xz)) + 7m log det (Ha)].
where ab; = E E(ab))~al(a b) H. E(ab)>all(a (a b)(a +
Sample (ac, b.) ~ Dr and observe preference feedback or ~ Ber (0(10" (x)), b.l))
9:
10:
end for
11:
end for

---

Double-Monster-Inf: Key Algorithm Ideas. The main ideas of this algorithm are similar to Double-Menster (Algorithm{)) which also runs in epochs with a predetermined epoch schedule To, T....., and tries to estimate the underlying linear score mapping o' with @m at each epoch m. However, the key difference from Double-Monster (Algorithm [ lies in the duel-selection routine which requires using a different convex constraint solver for continuous domains as it is not possible to maintain distribution over pairs of actions in the continuous space. The key steps are:
At the beginning of each epoch m, the algorithm computes an estimated scoring function @m using the offline regression oracle that yields:
pm arg min AE
Σ
(o(()(x,),, bb,) o,)²
Once 6m is computed, at any time t epoch m, given the context x, the estimated least square func-
vd
tion estimate @m. and some tuning parameter 7m
2 2E (6/(2mmmm))))) Tm-1 Tm-2)
query the Cont CCw-Costonttttoo rainttrrannnt. wwiintStlveeteeteeeeeeeeeeee Solver with the triplet (Ie, Pmr Ymm and obtain P. E AxxX using continuous convex constraint solver. More precisely, Cont-Crxconsttanntttoolll. is defined as a (possibly randomized) algorithm, s.t. given any triplet (z, o),, with æ E X, E and y R, it outputs p AEXE:
p - gr ((bbq: (x)) + 1 log det(H,))) (Hq)],
where
(6)
ab.- ((a,b)-qg(e + b)/2]. H4 baa. ((a () b) cla. > O tuning parameter.
Above is the key step of Algorithm 2 which sets it fromt our previous arm selection technique of Algorithm D proposed for the finite action space. Formally, p AgXI in Eq. (6) captures a distribution over "high-scoring' action pairs (owing to the term ((abp: ((x)) ') with sufficiens Importantly, the tradeoff between the first and second terms of Eq. ( the first term would like to put mass on the actions that align with dm (z+) - ensuring 'exploitation" of the regressed model Φm: the second term would want to put more mass on distinct pairs of actions in K. to induce higher variability - The challenge was to incorporate this explore-exploi tradeoff in the duel-selection rule p. for continuous action spaces.
variability (owing to the term } log det(H,))
Next, the algorithm simply samples a duel (a,, by) ~ Pt from the joint distribution Pa and the rest of the algorithm proceeds almost the same as Algorithm | except for the choice of the tuning parameters 7m. The complete pscudocode of the algorithm is given in Algorithm 2
Notably, our selection technique is inspired from 17 Alg. 2]. which introduced the idea of logdet-barrier distribution based arm-selection for contextual bandits which represents a regularized empirical risk minimization procedure. (1) We however had to modify their proposed distribution due to the dueling (preference) nature of the feedback. (2) More importantly, our regret analysis is different their analysis relies on the existence of an online regression oracle while we design and analyze all algorithms with (the weaker) offline oracles as motivated in Section T and Section 3
6.1 Performance Guarantees Algorithm 2]
Theorem 11 (Regret Analysis of Algorithm D Assume Vx E X, 11001 (I)
< D for some D > O. and suppose we choose GADD>mmeri' Then under realizability (Assumption of the function class t and with an epoch schedule Ti,..., Tm such that Tm 2 2 for m log T. with probability at least (1 6) for any E (0, 1) the best-response regret of Algorithm BR-Reg (cont) in T rounds m(T)
5d
(cont)
IC is bounded by: O
Σ 1==2
dE x (8/(2m²), Tm-1 - 2 Tm-1)
Tallying the result of Theorem II with 17 Theorem 2], which however only applies to the simpler setting of reward feedback models, one can claim that regret guarantee of Algorithm is optimal up to log factors. The proof analysis of Theorem I is given in Appendix D.I
7 Experiments
In this section, we report the empirical regret performance of our proposed algorithm Maablle-MMntter---nffffe ((Algorrmm) on different environments for general continuous decision spaces. All results are averaged across 100 runs.

---

We set the decision set K C IR' to the unit ball in dimension-d. We run experiments on two different problem instances (instantiated by its feature maps Φ): (1) Inst-1: Here the preference class M is characterized by linear feature map Φ : X' + R2 where for any x E X C Re, context dimension e N, s.t. ((x) [ for some arbitrary choice of Z E Rdxe, For our experiment, we set
c = 8, and report the experiments for = 2,5, 10, 15. (2) Inst-2: Here the preference class M is characterized by a quadratic feature map Φ
R4 where for any x X R e E N, s.t.
<(x) = (I1, Fee ii, 2,....;;2.2 2e 2122, ..... Ze-1 Te. 1) E (2)++ Note thus d = 2c + ② +
We consider 2, 2,3, respectively, yielding d 3, 6, 10, 15.
Regret with increasing d. As shown in the figure below, we see that for both the above instances,
the contextual regret scales O(VdT) corroborating Theorem 11 Note our decision space is fully continuous and with infimite arms, unlike the previous work of (30), which also used online regression oracles. Also, our preference relations are much more general that can be built non-lincar utilities (e.g., Inst 2), unlike the previous attempts of [I 25 19, which were also inefficient to implement additionally. Consequently, these works could only report experiments finite decision spaces.
Deudlto Mo
1000
Double Moroter-iff
88
Time (1
Time
Figure I: (Left) Inst-1 (linear transformation) and (Right) Inst-2 (quadratic transformation).
Comparing with Non- Non-Contextual Baselines. We ran experiments with Double-Monster-Tne
for finite-K' armed non-contextual MAB setting and compared with the following existing finite-arm Dueling-Bande -Bandt baselines: (i) RUCB 43]. (ii) REX3 [18) (iii) [35), (iv) RMED [20]. Results show we outperformed almost every baseline and performed comparably with DTSS, even though these baselines only apply to finite-amended non-contextual settings. We assumed 3 different types of scores
8: Base(20 arms): s11 = 1. s(i) = 0.7 for E {2, .... 10). and sii) 0.4 for i {11,.., 203.-
Hard (20 arms): s1) = 1 and sii) 0 0.05 for i E (2, .... 20-. Worst Case (WC, 40 arms):
Considers a worst-case instance s(1) = 1 and s1) = 0.9 for (2..... 40).
benchetta (1-1) unters
barcheerta sooierd
Figure/ 2: Comparing with Finite-armed Con-Contextual Baselines
Runtime. We also report the runtime comparison of different algorithms in Appendix
8 Perspectives
This work provides the first computationally efficient and near-optimal algorithm for contextual dueling bandits using offline oracles, resolving key open problem from [30) and enabling scalable solutions for preference-baie
personalized learning in real-worke applications. Additionally, we, for the first time, analyze the problem of for the continuous action space and propose near-optimal Ö(VaT) regret algorithm for this setting. We hope this advancement will offer more practical and scalable solutions for contextual dueling bandits, contributing to more worldw prediction models, including LLMs, human-assisted robotics, recommender systems, etc.
Future Work. Moving forward it would be interesting to analyze the problem beyond pairwise preference, generalizing it to mulitset/ ranking preferences. Additionally, does the complexity of the performance limit alter when employing an offline oracle compared to an online oracle? Deploying the proposed algorithms in practical use-case scenarios, e.g., tuning LLMs, training autonomous vehicles, Al-alignment in robotics, would also be an interesting empirical study. Another interesting direction would be to extend the proposed algorithmic framework to more general frameworks, like reinforcement learning or RLHF, and understand the corresponding theoretical guarantees.
10

---

References
[1] Alekh Agarwal, Miroslav Dudik, Satyen Kale, John Langford, and Robert Schapire. Contextual bandit learning with predictable rewards. In Artificial Intelligence and Statistics, pages 19-26. PMLR, 2012.
[2] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, 2014.
[3] Nir Ailon, Zohar Shay Karnin, and Thorsten Joachims. Reducing dueling bandits to cardinal bandits. In International Conference on Machine Learning, 2014.
[4] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 2002.
[5] Hossein Azari, David Parkes, and Lirong Xia. Random utility theory for social choice. In Advances Neural Information Processing Systems, 2012.
[6] Nathan Barezi. Lecture notes: 14.102, math for economists. 2004.
[7] Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul,, and Eyke Hüllermeier. Preference- based online learning with dueling bandits: A survey, Journal of Machine Learning Research, 2021.
[8] Viktor Bengs, Aadirupa Saha, and Eyke Hüllermeier. Stochastic contextual dueling bandits under linear stochastic transitivity models. In International Conference Machine Learning, pages 1764-1786 PMLR, 2022.
[9] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[10] Thomas Kleine Buening and Aadirupa Saha. Anaconda: An improved dynamic regret algo- rithm for adaptive non-stationary ducling bandits. In International Conference on Artificial Intelligence and Statistics, pages 3854-3878, PMLR, 2023.
[11] Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[12] Paul Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
[13] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Artificial Intelligence and Statistics, 2011.
[14] Miroslav Dudík, Katja Hofmann, Robert E Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Conference on Learning Theory, 2015.
[15] Max H Farrell, Tengyuan Liang, and Sanjog Misra. Deep neural networks for estimation and inference. Econometrica, 89(1):18 1111)21811, 2021.
[16] Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, 2020.
[17] Dylan Foster, Claudio Gentile, Mehryar Mohri, and Julian Zimmert. Adapting to misspecifica- tion in contextual bandits. In Advances in Neural Information Processing Systems, 2020.
[18] Pratik Gajane, Tanguy Urvoy, and Fabrice Clérot. A relative exponential weighing algorithm for adversarial utility-based dueling bandits. In International Conference on Machine Learning. 2015.
[19] Patrick Kolpaezki, Viktor Bengs, and Eyke Hüllermeier. Non-stationary dueling bandits. arXiv preprint arXiv:2202.00935, 2022.

---

[20] Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. Conference on Learning Theory, 2015.
[21] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[22] Haipeng Luo. Theoretical machine learning (csci699))lecture 6. Lecture Note, 2019.
[23] Nishant Mchta. Introduction to online learning (esc 482a/58 la)-lecture 2. Lecture Note, 2023.
[24] Alexander Rakhlin, Karthik Sridharan, and Alexandre B Tsybakov. Empirical entropy, minimax regret and minimax risk. 2017.
[25] Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits, Advances in Neural Information Prucessing Systems, 34:30050-30062, 2021.
[26] Aadirupa Saha and Aditya Gopalan. Combinatorial bandits with relative feedback. In Advances in Neural Information Processing Systems, 2019.
[27] Aadirupa Saha and Aditya Gopalan. Best-item learning in random utility models with subset choices. In Artificial Intelligence and Statistics. PMLR, 2020.
[28] Aadirupa Saha and Shubham Gupta. Optimal and efficient dynamic regret algorithms for non-stationary dueling bandits. In International Conference on Machine Learning, pages 19027-19049. PMLR, 2022.
[29] Aadirupa Saha, Tomer Koren, and Yishay Mansour. Adversarial dueling bandits. In International Conference Machine Learning, 2021.
[30] Aadirupa Saha and Akshay Krishnamurthy. Efficient and optimal algorithms for contextual dueling bandits under realizability. In International Conference on Algorithmic Learning Theory, pages 168-994. PMLR, 2022.
[31] Aadirupa Saha, Aldo Pacchiano, and Jonathan Lee. Dueling rl: Reinforcement learning with trajectory preferences. In International Conference Artificial Intelligence and Statistics, pages 6263-6289. PMLR, 2023.
[32] David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 1943)1190- 2022.
[33] Hossein Azari Soufiani, David C Parkes, and Lirong Xia. Computing parametric ranking models via rank-breaking. International Conference on Machine Learning, 2014.
[34] Arun Verma, Zhongxiang Dai, Xiaoqiang Lin, Patrick Jaillet, and Bryan Kian Hsiang Low. Neural dueling bandits: Preference-based optimization with human feedback. In International Conference on Learning Representations, 2024.
[35] Huasen Wu and Xin Liu. Double Thompson sampling for dueling bandits. In Advances in Neural Information Processing Systems, 2016
[36] Jeff Wu, Long Ouyang, Daniel M Ziegler, Nisan Stiemnon, Ryan Lowe, Jan Leike, and Paul Christiano. Recursively summarizing books with human feedback. arXiv preprint 1XXi:2110.10066: 2021.
[37] Tengyang Xie, Dylan Foster, Akshay Krishnamurthy, Corby Rosset, Ahmed Awadallah, and Alexander Rakhlin. Exploratory preference optimization: Harnessing implicit appappooximttion for sample-efficient rlhf. arXiv preprint arXiv:2405.2104 2024.
[38] Wei Xiong, Hanze Dong, Chenlu Ye, Ziqi Wang, Han Zhong, Heng Ji, Nan Jiang, and Tong Zhang. Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. Forty-first International Conference on Machine Learning, 2024.
[39] D. Pal Abbasi- Yadkori and Szepesvari. Improved algorithms for linear stochastic bandits.
In Neural Information Processing Systems, 201
12

---

[40] Yuhong Yang and Andrew Barron. intormation-thoorelee determination of minimax rates of convergence. Annals of Statistics, pages 1564-1599, 1999.
[41] Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 2012.
[42] Yisong Yue and Thorsten Joachims. Beat the mean bandit. In International Conference Machine Learning, 2011.
[43] Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. In International Conference on Machine Learning, 2014.
[44] Masrour Zoghi. Shimon A Whiteson, Maarten De Rijke, and Remi Munos. Relative confidence sampling for efficient on-line ranker evaluation, In International Conference on Web search and Data Mining, 2014.
13

---

Supplementary: Efficient and Near-Optimal Algorithm for Contextual Dueling Bandits with Offline Regression Oracles
A A Primer on Regression Oracles
In this section, we introduce the concepts of offline and online regression oracles to familiarize readers with their structural disparities and performance-related distinctions.
A.1 Offline Regression Oracles
32
Consider any abstract input space 2 and ouiput space V. Assume given dataset D, :- {(zi, ((i,):)) Mi=
consists of n data points, each (input, output) pair (zi,8t) iid D being drawn iid from a fixed underlying distribution D on 2 y. Given general function class S {f I f: Z + 3). general offline regression oracle associated with F, denoted by OffReg is an algorithm, operates on the given dataset D, and outputs a mapping f 2 + y. In learning theory, the quality of f is measured by its -fammll error," i.e., its expected error on random and unseen test data.
Assumption 4 (Guarantee of Offline Regression Oracles). Consider a general function class F S { s 2 + y). Then given a dataset Da = ((zi. th: Vi=1 that consists of data points, s.I. (2), y.) fid D, we assume that the output fn + offRegr (Dn) of the offline regression oracle OffReg satisfies that: For any E (0, 1). with probability at least 1 - 8,
(xyy)D (fan(e) - v)² inf
(5(=)
u)² v)² S E n),
fEF
where Eoft.M n) denotes the square loss of the regression oracle when trained n-iid instances.
Assumption 4 under Realizability. Moreover, if we further assume realizability, in the sense that
there exists f E F such that f=()) = -E(ay))~D( (y z). then well-known that Assumption
further implies: For any 5 E (0, 1], with probability at least 1 - 5, we have
E ((
s F (+)))
-
The offline regression error bound F 8) is a function that decreases with n. Note, for our problem, we have 2 (X x [K])) to be the set of (context, action-pair) tuples such that 2 (I,, a, by) with E X' and (a,, b,) E [K]2. Our output space is y = [-1, as note or E V
A.2 Online Regression Oracles
An online regression oracle [T] Chapter 3]. is algorithm, which we denote by OnReg, and which operates in the following online protocol on each round t: (1) it receives an abstract input 2; E Z from some input space 2, chosen adversarially by the environment; (2) it produces real-valued
prediction Ot E y C IR. where y is some output space; (3) it observes the true response y/ E ) and incurs loss Egt, 3/0) := (ge )2 The goal of the oracle is predict the outcomes as well as the best function in given function class F = { Z + R}, such that for every sequence of outcomes, the square loss regret bounded.
More formally, at time f and for input E Z, the online regression oracle associated to the function class F, denoted by OnReg,r, can be seen as mapping (<()) Re (2r, y- )=1== Note this corresponds to the prediction the algorithm would make at time i if we passed in the input although this input may not be what ultimately selected by the environment.
Assumption 5. Online Regression Oracle Guarantee: Given any function class F }}. the online regression oracle OnRegr guarantees for every sequence {(z,, y: heenl its regret is bounded as:
-n)² < (n),
Σ (D.(ze) v.)²
inf (((=)) FEF 1=1
where (nn. o(1) is known upper bound and a decreasing function of n.
14

---

Assumption under Realizability. Moreover, if we further assume realizability, in the sense that there exists f F such that Vt (2+) Ely. 2r]. then one can show that the guarantee further
implies:
1 Σ (0((z)) S (n).
(8)
Remark 12 (Some examples). Online square loss regression is well-studied problem, and efficient algorithms with provable regret guarantees are known for many specific function classes including finite classes where [F] < xc, finite and infinite dimensional linear classes, and others 11 17y. For completeness, we provide formal definition for some specific classes and instantiations of the regression oracles in Appendix
A.3 Examples: Some Specific Regression Function Classes:
1. Finite regression function class F. such that | 00.
2. Class of linear predictors F {(x, a) (0, Ha) 0 E R. 1011 1
3. Class of generalized linear predictors F [(z a) o(10,z,)) 0 Rd, R0, s 13 where IR + [0, 1] is fixed non-decreasing I-Lipschitz link function.
4. Reproducing kernel hilbert space (RKHS) F == {f I| S 1, K(ra, xa) S 1}.
5. Banach Spaces F = {(x; a) - ma) 0 E B, ||@|| 1), where (B, is separable Banach space and x belongs to the dual space (B, [--)-
batch-processing approach that involves analyzing the entire dataset at once to build regression model. The advantage of offline oracles lies in that they can consider all the data available for training, the training data is generated iid from some underlying distribution and therefore, can often produce more accurate model. On the contrary, OnReg, requires a much stronger guarantee compared to Of OffReg since they are required to fit any arbitrary test instance, even adversarially generated (input,output) pair (=t, (=t,le), whereas an offline oracle only promises that when (2,, yt) ~ 'D is sampled from the same distribution D where it has been trained. Overall, the choice between offline and online regression oracles depends on the specific use case. If the entire datasct is available and accuracy is the primary concern, then offline regression may be the better approach. However, if real-time processing and adaptability required, then online regression may be a better choice; although finding efficient online oracles for any arbitrary function class could be hard (e.g. see [23 Example 3], [22] Example 1)). It is also worth noting that an online oracle can always be converted to an offline one but not vice-versa since the former offers much stronger regression guarantee compared the latter.
Remark 13 (Online vs Offline Oracles). Offline regression
B Appendix for Section
B.1 Double-Monsted (Algorithm) I:: Pseudocode of Algorithm for the Best-Response Regret
B.2 Justification of existence of p in Eq. 2
Proof. Let us start by recalling the Eq. requires finding a p E A k such that:
Vi.j E [K], Ea-p' [Mr u] En-pr [)
8]
+ f(..
2 1
S
5K
7
?
Towards proving this, let us fix the context x X' and denote by P M(x) Then note we essentially need to solve the following minimax game (for any arbitrary preference matrix P):
Σ ())))),))p(()))) 1.
+ Σ (d()))N))')))) + 7 1. p(i.j)
2 Σ
())
min P
max
q.q EAA
J
15

---

Algorithm Double-Monster: Efficient Contextual Dueling Bandit with Offline Regressors
1: input Epoch schedule 0
TI < 72
<
Confidence parameter Tuning parameter
Y1, .2.....
2: Arm set: [K]. An instance of OffReg for function class M
3: for epoch m 1,2,.... do
K
4: Let mm
(for epoch I, 71 1).
Tm-1 Tm
5: Compute Mm + OffReg (1ir, ar br), Or mm-1 .ie. i.e.
Mm = arg MinMEM Σ Tm -=m -t1 (M(x)) (a,, d7] o,)² via the offline least squares oracle, where o = 20, - 1, for any T E [mm=2 + 1, mmll
6: for round / = Tm-1 + +,,1-- 1, Tm
7: Observe context E X.
8:
Compute Pt Convex Connvee-oonsstaintt-to Solverrr Mm, Ym) s.t. Pr satisfies:
2
5k2
Vi,j E [K] Ea [i] Ea-p; (
I'm Pe(i.
7'm
9: Sample (a:: b4) ~ Pa, and observe preference feedback Ber
M' (ms) (as)
10: end for
11: end for
Let us denote the minmax value of the above game, associated to the preference matrix P by
V(P) minpελιx maxg,q'Edx q Pp' q" Pp" E
a(0g' (i)
p(a.)
Now fixing >> 0, for any p E A define the e-relaxation of p as P(c) == (1- c)p c
As p()) itself is distribution, this upper bounds our objective while ensuring that the conditions for applying the Sion's minimax theorem are satisfied As such, obtain
Σ ((1)d(())
V(P) < min max DελRх qa''dx
Pp td (P + 7 (())),))
Ppfa + +q" T + Σ g())g'(1)
= max min
q.q'EA PEARX
P(e) (i,
Now let define another distribution E Δкжк such that j) ())) Vi,j E [K] It is easy to note that qqº and qq" q' Similarly, defining the e-approximation of qq as qq. == -1 +)qq +e1/K K2, further note qq = (l1-e)-+e3 e)q+ e//K, and qq. (1 (1-e)q' + +el// <l/K. KK
Then replacing by qq in the above expression, we can further upper bound V/P)) by:
V(P) < max
Σ
(() ((g
Σ
(()))) +
2 Σ 7 1
Li)gq'(1 (i)
9.9' Ax
qq (i.
i,k
3.k
(1 - E) Σ
Alo + K
Σ (())
max q.q'EAK
i
+ (1
c) Σ
2 7 (1
Σ
(()''
K
())
j.k
Note that the expression convex in p and quasi-concave in qq', required, following 6
16

---

(1-c) Σ (()) klq(k))
Σ 9(1) Eg(i)
S max 9.9'EAK
i,
a00 ()(())
+(1 - Ad
K Ed)++ Σ w
3.k
Here, the first inequality restricts the domain for P using the smoothing operator, the first equality is the minimax swap, and the second inequality follows by choosing p = q- The remaining three terms are bounded as follows: (i) the first term is zero since P is a preference matrix, (ii) the second term could trivially be upper bounded by c, and (iii) the third term most 4K2 as long as S 1/2. K
Setting K2 /2%, we obtain the result, as long
C Appendix for Section 5
C.1 Proof of Lemmas
Lemma 7 (Properties of decision policy n. in Algorithm I At any epoch m, Vn, n E II, the decision policy of epoch m n. satisfies:
5K
BRegm (TT) + BRegm (TT)
Yim
2V (T, x²) 5K2 Ym Regm (T π + 7m Reg (TT T²).
Proof of Lemma 7 Note by our algorithm selection rule, at any time t in epoch m, our decision
policy nm. X A KxK (see Definition satisfies:
5K2
Vq and q' E Ax q (T + q (T Einasina
T (i,j xx)
7m
Ym
but this implies that for any policy II and ' II.
2 7/m.
K
K
[ill,, ) ((((()))))))))))))))))()))))(( Tm (i, (12))
5K2
T (Ix)) Mm (M + n x'x)) "M (xe) (xx)
7/m
Further taking expectation over Dx along with Definition 3 and Definition yields:
6 above inequality
2V 2V T²)
5K2 7/m
Regm (T,, T + Regm (T', TT)
Ym
This proves the first part of the proof since by definition setting π *b* Im and the fact Vm (T, )²) 2
Mr), TT'
<bb [TT M
Additionally, due to the anti-symmetric property of preference matrix P, we have Reg,, (T π)) = - Reg,,, (T, of and Reg, (TT' T') Reg, (T'' Trm) (see Remark 3 Applying this which
further to Eq. 9 we get:
2V (T, x') S 5k² 7m Regm (T π)) Ymn Rogm (TT) π²).
This proves the second part of the proof.
17

---

C.2
Proof of Lemma
Lemma 8. For any epoch m. and any two decision policies π and πτ',
Vn 1 n
3K
Reg(T T π Regm ,
3
4'm
Proof of Lemma 8 any time
Let us analyze the difference between the true and empirical response regret at
Rog(T', (og(T', πT) Reg, (T', TT) ENND n (x) " (x))(())- x'x)) MMm()
+'xx) (MM (x) - Mm(t)) (((()))(((()) m(0))
E
Let us consider any x E X, and denote by q q= =')), p = Tσx), Pm- = Im)) m(t) = m. Now the term inside the expectation can be further bounded as:
K
K
q (x) - Mm(v))
Σ
(())(())
M (x)
g(a)
p())
(1)1/2 The Pm - (m- [M
Mm (a),
Tim Pm- (a) 1/2 Pm
1/2
(0)
((a))p²())
3mm
K
Pm- (0- (x)
37m
Pm (a)pm (1)
4
a=1
K
K
(())((t)
3m
K
K
Pm- (0) (=) il)²
3mm
Pm Pm-1 (a)
4
where (a) uses the Cauchy-Schward inequality followed by AM-GM inequality. Using similar ideas one can derive:
EDNDx (x)x (e)T((MM (Mr(x) - (M)))-Mmm())) (x) [xx)
1
r'aa x))(( x))
37m Tm-1(a m) (M
(a)
3'm a=l mm m))mmm1 x))
1 V (T', TT)
3/m East. 2//mm, Tm-1 Tm-2) V in--(( nT)
3K2
3%m
3'm
4Tmm
where the second last equation follows from Assumption and the last equation from the choice of
1/2
R²
Ym Eost, (5/am 7m- Tm-2)
C.3 Proof of Lemma 10
Recall the notations introduced Section 4.1 that will be used throughout the proof.
Lemma 10 (Epochwise Recursion). Let be any policy in IT? Then for all epochs E N4:
BReg(T + BReg(T") s 2BRegm (T²)) + 2BReg, (TT) ) + 11K2 /mm
BRegm, (T') BReg,, (T*) < 2BReg(m²) 2BRee (T") + 11K2 //m-
Proof of Lemma 10 Let us fix co = 11 for the rest of the proof. We prove the claim via induction on
m. We first consider the base case where m and < t S T1. In this case, since 71 1,
BReg(T") + BReg(T") < < ko //. BReg, (т²) + BRegi (T") ) s S co /m1
Thus the claim holds in the base case.
18

---

For the inductive step, let us fix some epoch m > 1. We assume that for all epochs m' < m, all II?
BReg(T T + BReg(TT) S 2BRegm (T²) 2BRegm (T + cooK2///m /mmm
(10)
BRegm (x²) + BRegm (T²) S 2BReg( (T') + 2BReg( + cok /mc.
(11)
Part-1: We will first show that for epoch m, and π E 113
BReg(T") + BReg(x") < 2BRegm (T²) + 2BRegm (TT) ) + cgK2 / /Tm-
For simplicity let us denote the policies ( ,M", 2b [Tt", M*] respectively by π ne T" and ab'(rr (Tr",, .M,mm 2b" [T",, MmJ. respectively by TT "h,"". Then we start by noting that:
BReg(TT)) BRegm (T") Reg( or t x²) Regm m σ²)
Reg(TT* T²' - Regm (TT* n²),
(as Regm (T/i" ,T²) Regm (TT xT')
(a) Vm 1 ( 3R2
3mm
4m
where the first inequality is by the optimality of n by definition and (a) follows from Lemma 8 Similarly, we can show that
BReg(x*) BRegm (I²" ( V Vm-1 1n0"." 3K2
3%m 4
Combining both we get:
Vn (TT*,,,7))
1
Vm (TT"'", π²))
3K²
BReg(T") + BReg(Tr") [BRegm. (TT' + BRegm (T'))
+
+
3'm
3mm
2
(12)
Now using Lemma this implies for both n² and n², we have:
2V
(T e π I 5K2 + 7/ Regm (m n: x=*) + 7m Regm (Tm-11 T²),
(13)
21 mm 1TT" πt") 5K2 + Ym- Regm- - (I mm Th" + Tm- Reg -1 (m (14)
Now note that Eq.
further implics:
2V 2Vm-1 177 n
5K2 + 7o Regm ( T+(²) + Pm- Reg... (m
6%m
6mm
5k2 7m- Rogm (xb"(TT<)) M 1), T)) + Ym Regm. (1b"(7r' M, 1), TT
6mm (by definition of ai [n Mm- (Tt", Mm-1))
5K2 + B (T+ + Pm BReg..................__.....B ((T))
6m
Similarly can show that:
2Vm (T T"))
5K2 Ym Reg. (T (1
TT*'") ) + 7m 1m-1 Rogg 118m-11 (TT π²")
6%m
6ym
5K2 + 7m- Regm-1 Mm (+*) + 7m Reg (2b*( [TT", M 11, TT)
6mm
(by definition of ( Mm (T'"" Mm-
5K2 + 7m BReg (T) )++ + 7m BReg (TT")
6%m
19

---

Summing the results from the above two inequalities:
2V m 2 (T²'
2V -10""",, TT")
67m
10K + -1 1 (T) + BReg - + 1 (TT'.' + BReg (
6m
(a) 2(5k2 +ccK2)) 2mm (BReg( π ( + BReg(TT" + BReg( (1 + BReg(TT)
6mmm
(0) 2(5K2 + took2) 2m
1 (BReg(TT)) BRRe((TT)
6m
2k 2(BReg(T + BReg(T")
where (a) follows from Eq. (10), and (b) follows from the fact that BReeg(=*: BReeg(T*
by Assumption Combining the above two inequalities with (2)
Vm- (TT* xT))
Vm- 1 (,t*.".0 πT)
3K²
BReg(T TT)) + BReg(T") - [BReg (Tr') + BReg,,. (T¹)] <
+
3mm
37m
27m
(5 + co)
(BRog ( + BReg TT))
3K
3 +
3mm
2
which implies
K² ( co)
3K²
[BReg(=") BReg(T")) [BRegm (T²) BReg (T")
+
3/m
2mm
Consequently, get:
BReg(T") + BReg(T") 3
BRegm + BRegm (T")) + K2 co)
9K2
+ 4mmm
2%m
finally leading to:
Kg
BReg( n²) - BReg(T") < 2[BRegm (T²) BReg ( (T')]
(15)
7/m
for the choice oo = 11 and recall that we assumed that π is any arbitrary policy. This concludes the first part of the proof.
The second part of the claim can be proved almost following the similar tricks. We add the analysis below for completeness.
Part-2: To prove the second part we start by noting that we can show:
Vma 1 (Tr Aetifi.m T²) Vma (TT T²)
3K²
BRog( + BRog(T)) (T") [BRggm (T²) + BRog,, (T*)] S
3%m
3
2
(16)
Following a similar analysis from above, we can obtain:
2Vm Tie T²) + 2Vm 1 (T"""" TT")
6%m
20

---

10K2 7m (BRegm- (TT + Reeem-1(m) BRegm. 1 BReg (T
6mm
(lBReg( 2(5K2 + +cok22 + 2mm 1 mm m BReg iT (2
m0 (BReg(TT) + BReg((T (T'
6m
W 2(5K2 +20gK2) mm (2 BReg (TT)
BRegm (TT""") + [BRgg (T') BReg(R nT"
67m
2(5K2 =2ogK2)
mm (BReg( + BReg
6m
25 + 2co)
(BReg(Ti x²) + BRog((r"))
6%m
where (a) follows from Eq. [1]. (b) follows since we have already proved the first part of the induction for epoch m as concluded in Eq. (15) and (c) follows from the fact that BReg.. (TTTaa) BRegm. (xm = 0 by Assumption
Combining this with (6):
Vm (T T²)
V, (TT TT)
3K²
BRegm (T²)= ) BRegm (T²) - [BReg(=²) + (Reg(="") S
+
3mm
3
27m
(5 + 200)
(BRog(T)) + BRog (T'))
3K²
+
3m
3
2mm
which implies
4
K2 + +20)
3K2
BRegm (T BRegm (T*)
BReg(TT) (BRe(((")) ]]
+ 2mm
3mm
Consequently have:
BReg (T') BRegm (RRegm("")) (T)) 4 [BReg(x') + BReg(R"))) (T)] 12 + 200)
3k2
3%m
2
finally leading to:
BRegm (TT² ( BRegm (T") S BReg (I²) + BRegm (I²)) + oo
7/m
which is again satisfied for any choice of co = 11, concluding the entire proof.
C.4 Proof of Theorem
ready to prove the final regret bound of Theorem Theorem 5 (Regret Analysis of Algorithm []. Consider any function class M that satisfies Assump- Then under realizability (Assumption 7). and with an epoch schedule TI,..., Tm such that Tm 2 for m. < log T, with probability at least (1 8) for any & E (0, 1) the best-response regret (BR-RegT) of Double-Monster after T rounds bounded by:
Given the result of Lemmal 10
tion
m((")
O
K
X m
Eost (66r,(66/22m23 Tm- (T Tim-1)
(5)
Proof of Theorem
Applying Lemma 10 over the phases m = 1, I,..., m((')) we get:
T
BR-Regr
Emg Dx
max qEAx
Earq
Elan (Me)))aaaa as] + (xxx) be]l
2
[=1
21

---

m
BRegm (T BRegm (Tm) (Tm Tm-1)
(2')
2BRegm. 5m (Tm) + 22222Bgggm (T + 11K2
Σ
(Tm - Tm-1)
2 mam
mm
(6) m((2)
21
Σ
(Tm Tm-1)
Y'
m(T) TT
11K
v (/22m(2 (Tm- Fm-2) +
where (a) follows from Lemma 10
follows from Lemma and the last inequality follows by the choice of Tmm in Double-Monster (Algorithm) 1.
The proof is concluded noting 71 = 0(1). LI
C.5 Proof of Corollary 6 for Finite M
Proof. In particular for the special case when M is finite, we know it is possible design offline regression oracles (see [24] Table 1J) such that the offline loss that for any phase m could be bounded by by
2log(2) log(Tm-1)m/0))
(,/m((2m)) (Tm-1 (2mmmmmmmmmmm1
Tm
Tm-1
as follows from
32 Now using the derivation of Theorem
we specifically derive for å 1/T:
BR-Regy
E
Ex,Dx
max
Eowa
[M' (2))aa + (x:))aaa b,]]
m²(T)
1
Σ
BReg( mm BReg mm) (Tm Tm
m=1
m(?)
2BReg (TT) + 2BRegm (Tm) + 11K2
(Tm Fm-1)
7/m
(6)
21
(Tm 1m-
Im
m(T)
< 11K
(r,8/(2m²)(TTm1 7m-2) +1
m=2
m(T)
log(2| (og((m--1)D (Tm (m--1 + - (2 log T)).
22K
Tm
m=
D Supplementary for Section
D.1 Regret Analysis
Proof Analysis Theorem
As discussed in the algorithm description of Section one of the key contributions of this work lies in the analysis our proposed method which is the first attempt address the contextual dueling bandit problem with offline regression. The overall proof structure adapts the same line of argument given Section 5.2 however, the challenge was to reproduce the equivalent intermediate lemmas (precisely the results of Lemma 88] Lemma 7 and Lemma (T0) for the continuous action space. We will discuss the proof of Theorem TT in detail the rest of this section. We will find useful define some notations for the case of exposition.
22

---

D.1.1 Additional Concepts towards proving Theorem
11
We will start with defining an important concept of Epsilon-net of K. We will later see the usefulness of this concept while proving Lemma a5 explained the associated Remark 17
Definition (Epsilon-Net K. (w.r.t Euclidean Norm)). (finite or countable) set Ne S K is called an E-net of KC with respect to the Euclidean norm if
YaEK 3b E Ne such that ||a - bll2 S E.
Equivalently,
C U ca) where (2(a, {b E R la
bl22 Se).
DEN,
Definition (Projection E-net), Given any point K., we denote the projection of a to e-net as PNv, (a) == arg minbeN, l|a bbl2, where fies are broken arbitrarily.
Note for any a E K. ||a - Px. (a)l2 S E.
Remark 14. & E (0, 1) is a tunable parameter, and we will see in the proof of Theorem below how to choose it optimally.
Definition 9 (Policy Class over K.). A standard policy class & == {ab +b X + A(K) is set containing all the set of all probability measures
Further we also define by policy class T² == { 2/² : + A(K x K.)} be the set of all probability measures on K. x K.
Definition 10 (Policy Class over Epsilon-Net of K.). A standard policy class 11 := { π X ([N:)} is set containing all the probability distributions over Ng. Further we also define policy class 112 := { π² X + ( x Ne)} be the set of all probability measures on Ne x No.
Definition 11 (Decision policy of Epoch-m). At any epoch m and x E X, the decision policy of eepoch m is defined ti.... ? (x) t Cont Cont-CvxConstraaiie -Solean Φm: Tmm), Vo E X.
Note that at any time in epoch m, (xt) Pt E A(K x KC) is a probability measure over the will further denote by vhe E and ab", E T respectively the left and right marginal policies of nm Tp2 i.e.:
product space K x K. Similar to Section 5
fm (a x)) ExnDx Dx Jee 4/ (a, b w)dbb and (b x))
Ex-Dx [1/ v (a, b xr)da
Definition 12 (Approximate Decision policy of Epoch-m). At any epoch and x E X, the decision policy of epoch m is defined as nm E II? such that:
Tm (x) = argmax,
GEA(N argmax xe) (aby o(x)) + 1 log det(HH)) (Hq))
Similarly we define T E II and Th E II respectively be the left and right marginal of nm II? Definition 13 (d-Best-Response Policy). Given any scoring function & E 4, we define the è-best response policy uh X + K as:
(x) = arg (ox()(z) a), Va E
aek
which denotes the best-response ka. highest decision/action for the scoring function 6.
Definition 14 (Instantaneous Regret of Policy). For any arbitrary underlying preference mapping 4 we denote the best-repponse regret of policy 1b E as:
BReg (v) Ev-Dx (2)) ((x)) (1b(z), o())),
where (x) E is as defined in Definition 13 and with a slight abuse of notation (zb(z), 6(x)) = Ear (a, ((x))).
Given the above definition, for the true scoring function Φ", we will denote BRog (1b) simply by B.
23

---

Definition 15 (Approximate
Policy). Given any scoring function ó E Q we define the approximate Ø-best response policy T X Nr as:
T T = arg max (1bxx), a); Va DEN.
which denotes the best-response (a.k.a. highest-scoring) decision/action for the scoring function within Ne, the e-net of K.
Definition 16 (Approximate Instantaneous Regret of Policy). For any arbitrary underlying prefer-
ence mapping & E ④ we denote the approximate best-response regret of policy т E as:
BRegg (T) == ( ((x)) (T)) ((x))),
where Te (x) E Ne is defined in Definition 13 and again with slight abuse of notation, denote by (T)),, ((x)) = Eaww(s)) (u) (a, ((x))
For the true scoring function 6", we will denote BRegg- (TT) simply by BReg( and for Om the estimated feature mapping at epoch m (see Algorithm 2 we will denote BRegø.. (πT) by
BRegm, (T)) Further, we will also define the decision variance of any policy π E II defined Definition 17 (Decision variance of a policy). For any two policies Tı, T22 E 11 the decision variance of Ti, T2 with respect to another decision policy स 112 is defined as:
(T TT) := ExnDx || (x) - T2(2)) (2(()))H(((())))
In particular, when ग Tms where recall that Tm the decision policy of epoch m, we will use the shorthand Vm 1T1, T2) to denote V* (TT, T2). ). To understand the term from an intuitive level, roughly V* 1 TΣ2 indicates the selection variance policy on the random pairs of actions generated by the pair of policies (TT1 T2).
D.1.2 Proof of Main Theorem
Given the above definitions and setting the preliminaries, Theorem II Let us start with recalling Theorem I1 first:
now ready explain the proof
Theorem 11 (Regret Analysis of Algorithm - Assume Vo E X, (x))
D for some D >
and suppose choose
5d Then under realizability (Assumption of the function class
Φ and with an epoch schedule TI,..., Tm such that Tm. 2 2 for m < log T, with probability at least (1- () for any E 10, the best-response regret of Algorithm
2 BR-Reg
(cont) in T rounds
m(TT)
K. is bounded by: O
dEon, (8/(2m?), Tm-1 (T Tm-1)
We start with a generalization of Lemma for continuous decision spaces which establish the empirical performance of Algorithm 2 as given below:
Proof of Theorem 77
Lemma 15 (Properties of decision policy n. in Algorithm 2 of epoch m, n., satisfies:
At any epoch m, the decision policy
BReg (T()) + BReg, (TT)) <
7m
Vm( ( T²) S d + Ym [BRegm (T) BRegm (=)')
for any two policies π and nt E II.
The next key step is to connect the empirical performance of any policy π to its true performance. Our next result carries similar spirit of Lemma however the proof analysis if very different as follows from our detailed proof analyses in Appendix D.2
Lemma 16 (Emp vs True Performance). Let π be any policy in II². Then for all epochs m N4:
BReg(T (T) BReg(=") 2BReg, (m") 2BReg, (TT) + 6d/Tim
BReg (T') (r()+ + BReg (T") < 2BReg( x²) + 2BReg(T7) + 6d /m
24

---

Now the final regret bound of Algorithm 2 now follows by combining the statements of Lemma 15 and Lemma T6 as shown given below:
Given the above results, the proof of Theorem ffoloows combining the results of Lemma 16 Lemma 15 Applying Lemma 16 the phases -.....,,i. mm() get:
((a + bi), (xxe)
BR-Regt
3R-Reg(cont) (cont)
E Ex
max (a", 60 (xx)) be
a' a'
2
mT)
1
Σ
BRegm (+/))) BRegm (+)))) (Tm mm--1)
2
(2))
E
(0 (x),,,, (/0) (x) (m))) + (x), (x) - 2 (2)) (Tm mm
2
m==1
E
(z) क.. (x)) (Tm (Tm- Tm-
m==
E[2 (z), PN. (5- (1 PN. (1ho (2) (T) T (x))) (Tm Tm-1)
m(T)
E E
2x0) (N. (x:)) + 2=D - 100 (x), (IT (x) + n (x))) (Tm -m
m=1
m(7)
E
max
2(0² (z), a) - (T + म.
(x))) - (mm
aEN:
E 2(0'(x), T (x)) (6 (T (x) + T.. (+)))
-m +ED
m(T)
BRegm (TT)) + BReg (TTT)) (Tm 1m- + EDT
2
m(3)
+ 6d
2BReg ( (TT( + 2BRegm ( (mm)+
(Tm - Fm-1) + DDT
7m
m=1
m(T)
(4)
8d
(Tm Tm- + EDT
Ym
m(T)
<d
Σ
V E0.s/(2m2)(TT-1) Tm-2) t =DT
m=2
where (a) follows from Definition 8 (b) applies Cauchy-Schwar and the fact that o (x)ll <
D. Vr E X' by assumption, (c) follows from Lemma 16 (d) follows from Lemma 15 and the
last inequality follows by the choice of Ym Double Morble-Moona Monster (Algorithm 2). The proof is concluded noting 7i (by parameter choice) and setting DT
This gives an overall roadmap of the proof of Theorem lemmas in the following subsection.
We give the detailed proofs of the above
D
25

---

D.2 Proof of Key Lemmas for Theorem 11
Proof of Lemma 15
Lemma 15 (Properties of decision policy nm in Algorithm 2 At any epoch m, the decision policy of epoch m, nm, satisfies:
BRegm (T + BRegm (TT) S 7mm
(m x²) S d + 7m (BRegm (T)) BReg
(
for any two policies and nt' TT.
Proof of Lemma
15. Note that at any epoch m and context i E X, we have:
Tin (2) = arg
min qEA(NexN..)
E (aa (T (x), (x)) ((a + b)/2, - log det (Hq)
Tm
(17)
A(N, Ne) be the optimal solution of the above optimization. Then consider the Lagrangian of the above optimization and setting the derivative with respect to (" b) zero, we obtain logdet determinant:
Fixing a z X, let q"
@m (x), (x)) - ((a + 2)/ om (x))
b b( X(a, b) + = 0.
(18)
7m
where À E R and A(a, b) 2 O, are the Lagrangian multipliers. The interesting thing to note the third term in the above expression which obtain using the known fact about the derivative of the determinant of any invertible (full rank) matrix A is given by
d(det(A) A)) = det(A) Tr(A- dA),
where Tr(-) the trace function of the matrix. For any q A(N, Ne). using this we get:
(log det (Hq)) det(Hl y Hag Tr ( d dgob
d
Hg Tr H (a b)(a (9(a-b))) b)T)
dqab
Tr (a (a-b) b) (a b))
||a -bb
b H(
where the last equality uses that the trace of matrix product is invariant under cyclic permutations, Le. Tr(ABC) Tr(CAB) = Tr(BCA) given any d dimensional matrices A, B, C.
Further, multiplying above by q (a, b) and summing over all pairs (a, b), we get:
Σ
(a, b) (T (x), (m)()) ((a + b)/2, b2
a.b x xN.
bl b
Σ
(o), +^= = (19)
7m (a.b)E(N NN.
(a.b)E(N.XN..)
One important observation to note
Σ
(a b)lla bl2 b(
Σ q"aa b) H(q")-"(6 b)
(a.b)E(N,xM) N..
(s.b)E(N,
Σ
q' (aa (a-b)) H(q') -b))
(N.
Σ
(" b) Tr (aa b) " - -1
b))
(a.b)E(N
= Σ
( b) (H( b)(a (-)abb))) b)T)
(N.))E(NeX...)
26

---

=Ir
Σ
(a b)H((') b)(( -b)7)
(N.b)E(N.xNN))
Tr (H("") (a.b)e(NeNN.))
Σ
q' (()a)-b)))) b)7) d
where the third inequality again follows by applying the cyclic permutation invariance property of trace function describe above. Further the last inequality can be justified through Lemma 19 and noting (Q"") (a..))((N q (a, b) () - b) + Ala-
Rearranging the terms in 19 and noting Σ (aa.b)e(NxxN.) (a b)lla b S d, we have:
Σ
F( b) ((T (z), (m)) - ((a + b)/2, (m()))) +
d
Σ
(a b I
(20)
7m (N.
I'm
Note the first equality uses complementary slackness and set ((..))E (a) b) 0.
Now interesting observation is that, setting Ten.. (x) in 18 that 20 simply yields:
get: d X(a, b) 2 0. But
Σ
((T..))) ((a + b)/ om (m())))
d
7m
[N,
which proves the first claim.
On the other hand, 20 also implies:
d
Σ
T' (a, ((T (z), - ((a + b)/2, (x))) + X s
7m
(u,b)E(N,xNN,) NN))
i.c.
A
d
Σ
(' ((To) (o) (z)) ((a b)/2, om (x)))
7m
(aN
which further implics
d
7m
since E(a.bie(N,xN,) (a b) ((Tom (z), om (x)) {(a + b)/2, pm) (x))) 2 0 by definition of
Tom But since X(a, b) 2 0 Va E (Ne x No), 18) further implies:
- bl + = X b) 2 0,
(T (I), o (z)) ((a + b)/2, om)
7m
i.e.
2112 la
((
((T (x), (m(())) ((a + b)/2, om (x)))
Ym
d + ((TT (x), (x:) ((a + (m)))
7m
Since above inequality holds true for any pair (a, b) (Ne e), the second claim of Lemma 15 now follows for any two policies and n' E 11 by taking expectation over and replacing by π())) and by T' (z). Precisely, the last incquality gives:
EgnDy [1] -x'''' x'(x)) ) S Tm ((T (x), (m())) - ((T(()) + n (x))))/, + d 2m.
Vm (TT, x') S 7m [BReg (T) + BReg(T (T')) + d,
(21)
where the last claim follows noting that 9"' the optimal solution of the initial optimization problem in Eq. 17 and hence can always set n (2) q" for the given context X.
D
27

---

Remark 17 (A comment on correct application of KKT conditions). It is crucial to observe that the proof of Lemma relies on the E-net construction precisely because it allows to invoke the (KKT) conditions. To apply KKT, the optimization variable must live in fiite-dimeensioall space; here that variable is q A(N, x Ne), whose dimensionality is finite by definition of the e-net. In contrast, the original problem over A x K.) is inherently infinite dimensional, so any Lagrange multipliers would themselves be infinite dimensional, and the standard KKT machinery would break down.
Importantly, introducing the E-net purely a proof device; it does not alter the algorithm or its outputs in any way. Clarifying this technical point corrects a gap that appears in several prior contextual bandit papers for continuous action spaces-for example, the proof of [17] Proposition 3] informally applies KKT conditions to an attendant issues of uncountably many Lagrange multipliers! Our analysis closes that loophole by first projecting onto a finite e-net and only then applying KKT. This requires significant modifications the proof of regret analysis of Theorem Tass detailed above.
variable without addressing the
Proof of Lemma 16
We will state another important result before proving Lemma To]tha that expresses the difference between the (approximate) true regret and empirical regret in terms of decision variance. The formal claim is as follows:
Lemma 18. For any epoch m and policy π E IT
1m-1(TTT- T)
5d
BRe - BRegm (T) 1
+
5m
16
V (T π
5d
BRegm (T) BReg(T)) <
5m
167m
Proof of Lemma 18 Consider any epoch m, and let g denote the best sooor-maximizing policy
for the scoring function o, for any o E 4 (as defined in Definition 14). Then we start by noting that by definition,
BReg(T)) - BRegm (T)
E (T (I:), o² (x)) - ((T)) - (EnwDx (iT (x), pm (x))] E Dx [TT( om (z))))
EDNDA (T)) (x))] ILTDA (x)) - (E Dxx ((T @m) (x)) E Dx [(T om (x)))
-E
(T (x) (x)
(x)) (0 om (z))
(0)
ExnDx
v 22 |T (x) π (x)) ((Tm)))))) 1V 55m //55m/21(0 22|00
(b)
2 ExnDx
|| -- {<))|| 1(x))-1+ +
5%m
100 6m H(
(1))) 1(x))
57m
4
(c)
5
ExnDx
|| (x) π
(z) (
nm En (1/22m² Tm- Tm-2)
5%/m
V Vm-1( ( (T
5d
57m
167m
where (a) uses Holder's inequality, (b) applies Cauchy's Schwarz and AM-GM inequality. Inequality (c) follows noting that
11 (x) Φm (x)) (1))
= pm (x), (a b)) cllø" (x) - pm -x)(3))
(a)
Σ
Tm Tm-1 (m) bld (x) 6m (x)) (a-
b)) + 2c
(a.b)E(N,
5d
= (o/F..M5/2m2 Jm-1 7m-2) + 32
28

---

where (a) applied Cauchy-Schwand and the last equality follows from Definition 17 our choice
1/2
of Tmm 2v2 Ea (1/am= (Fm 1m
and since we set 647mery 122
5d
5d
This
64
122
completes the first part of the proof. The second part of the proof follows almost with the same argument as shown above, with the additional observation that:
BRegm (T) (R)g(T))
EnNDx (To (I)), &m (x))) Eu- (TT( (m (Ez-Dxl(TT- (x). En ((T(x), 00 (*))))
((TTm (x)) (1-T(()) (x)), (xm -x(())
EENDx
Given the results of Lemma 18
now ready proof Lemma T6
Lemma 16 (Emp vs True Performance), Let π be any policy in II². Then for all epochs m E N4.
BReg( (T)) + BReg(x") S 2BRogm (TT) + 2BRegm (Tr) + 6d/
BReg (T²) + BReg (T*) S 2BReg T + 2BReg( + 6d/
Proof of Lemma 16
The proof follows exactly the same as the proof of Lemma 10
Let us fix co 6 for the rest of the proof. We prove the claim via induction on m. We first consider the base case where m and S Ti. In this case, since 7/1 1,
BReg(T') + BReg(=") < 2 < cod/n,
BReg, (T²) + BReg, (Tr" < 2 S cod/m1
Thus the claim holds in the base case.
For the inductive step, let us fix some epoch m > 1. We assume that for all epochs m' < m, all IT?
BReg( BReg(TT) 2BRegm. (T²) 2BReg (T") + cod//mms
(22)
BRegm (T') ) + BReg (T²) < 2BReg(T + 2BReg(T") + cod//mm
(23)
Part-1: We will first show that for epoch m, and π E II?,
BReg( + 3Reg(T") < 2BReg, (T') + 2BReg (T*) ) + cod/
We start by noting that using Lemma 18 we have:
BReg(T ( BReg, (T7) 5 Vm (To,,
5d
5mm
167m
Similarly, applying Lemma 18 we get that:
BReg( (T)) BReg (TT") vm 1 (
x²)
5d
+
5%m
167m
Combining the above inequalities we get:
Vm (TT,,
Vm (T T²)
5d
BReg(T*) BReg(T")) [BRegm (m() BRegm (T*))
5%/m
5%m
8
(24)
Now applying Lemma 15 we know that:
V V x²) + 7m (iReg--(TTT))) 7m BRemm.-
(25)
29

---

Vm T²) S d + "m-: + 7m-1 BaeiBBReggmm 1
(26)
Summing the results from the above two inequalities, we get:
- a x²) + Vm (TT", TT)
5m
2d + 7m-1 (BRegm (T
BReg (T²) + BReg (TT- ) + BReg (T¹)
5m
(a) 2(d cod) + 2m (BRog(2TTo)) BReg (TT) BReg(T"))
5m
(1) 2(d + cod) + 2m (BReg( σ²) + (R)e(TT))
7m
2d(1 + co)
((RRgg(")) + BReg(T"))
5mm
5
where (a) follows from Eq. 23). and (b) follows from the fact that (Re = 0 by Definition
The last inequality follows since by choice 7m-1 Tm Combining the above two inequalities with
we get:
Vm (TTT, x²)
Vn (Ta. T
BReg(T)) + (Reg((T") [BRegm (T + BRegm (T*)) S
+
5%
5%m
8/
2d(1 + co) + 2(BReg( n ( BReeBRggT (T*))
5d
+
5m
5
8%m
which implies
5 3
BRegm (T BRegm (T S 2d(1 + co)
5d
BReg n + BReg(r")
+
5%m
8%
Consequently, get:
BReg(T (T)) + BReg(=") S 5
BRegm (x BReg (T²)) 2d(1 + cu)
25d
3
24
finally leading to:
Kg
BReg Tr") BReg(x"") < 2[Beg (T²) BReg (π +]"
(27)
7/m
for the choice of = 6 and recall that assumed that is any arbitrary policy. This concludes the first part of the proof.
The second part of the claim can be proved almost following the similar tricks. We add the analysis below for completeness.
Part-2: To prove the second part, we start by noting that, similar to
24 we can show:
BReg(T") + BReg(T") TT)) [BReg.. (T') + BRegm. (T")) Vm (T "
Vm
T Tmm
5d
+
5%m
5%
87m
(28)
Following a similar analysis from above, we can obtain:
Vm 1 (Tom T²) + Vm- 1 (TT o' π
5mm
30

---

2d 7m-1 [BRegm 1BRegm-1(0 (T ++ 11 BReg (Tom) ) BReg (TT)
5m
(4) 22d + +cod) 2mm ((BReg Temm (T..((T...)) ) + [BReg(TT)) BReg
5m
3 2(d 2cnd) 2m - (4 BReg (T ) [BReg(TT) + BReg(
5m
( 2(d + 20nd) 2m (BReg(TT) (TT) + (Reg(TT))
5%m
2d(1 2co)
2(BReg( + BRog(TT))
5%mm
5
where (a) follows from Eq. (3). (b) follows since we have already proved the first part of the
induction for epoch m concluded in Eq. 27). and (c) follows from the fact that BRegm (T by Assumption 3 Combining this with (28):
Vm (T : T²) +
Vm 1 (To.. x²))
5d
BRegm (T²)) BRegm (T²) - [BReg( T + BReg(T") $
+
5mm
5mm
8mm
2d(1 200)
2 2(BReg( (T') BReg(Tt)
5d
5mm
5
87mm
which implies
7 [BReg(T") + BReg(T")) (R)eg(T") 2d(1 + 200)
5d
BRegm (T')) + BRegm (T")
+
5mm
8mm
Consequently, we have:
BRegm (T") + BRegm(T [Reg(T ( + BReg(T"))) 2d(1 + 200)
5d
+
5%
8m
finally leading to:
BRegm (T²) + BRegm (TT) < 2 BBRgg (T²) BReg,. (T (T))] + Cod
which is again satisfied for any choice of ca 6, concluding the entire proof.
D.3 Additional useful results for proving Theorem
Lemma 19. Let A be any d-dimensional postive semi-definite matrix and À' + clr some positive constant 0. Then
Tr(Â AA) s.
Proof of Lemma 19 Consider the eigen decomposiionnnnn of A =
d.u.u. where
a; 0 is the i-th eigenvalue of A E is the diagonal matrix with E(i, a,), and U [u.... orthogonal matrix with its columns, u,,..., u2 being orthogonal vectors.
By definition of A, it then follows that the eigen-decomposition of Á Easlas + c)u,u, and hence Ä -1 Dd - T
o.to
Combining the above insights, get: À-'A Ed a,to u,u represents the eigen- decomposition of A This further given Tr(Â-1A) E matrix is the sum of its cigenvalues.
Di=1 ofte I d since the trace of
31

---

E
Supplementary for Section 7 Additional Experiments
E.1
Running Time Performance
We also report the running time performance of Mouble-Monster on Inst-1:
We here report the (averaged) runtimes of the above executions (in seconds) with increasing to check its runtime efficiency of Double-Monster- Inf. We report this for Inst-1 for T 10, 000. Despite large T and the complete runs of the algorithm are finished within a few minutes, which demonstrates its computational efficiency. The experiments are run on a standard MacBook Pro (36GB RAM).
d
runtime (scc)
4
24.481216
6
117.084477
10
176.244782
15
501.716698
T 10,000 (Inst-1)
32

---

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

---

Answer: [Yes]
Justification:
The assumptions can be found Sections 2 and and the paragraphs
before the theorems. We provide proof sketches in the main text and complete proofs in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We explain the experiment setup in detail in the submission draft.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
34

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Guidelines: Our experiments are performed on synthetically generated data, and all details are provided in the submission draft.
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nips) cc/
public/ /uwlc// Codees/mmd cossoooooicyyy for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https //nips. cct pucllppllii i c/ des CodeSubmi ss i onPol icy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All details mentioned in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Details are provided the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
35

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://tttss/e.........o//aaaaaa
Answer: [Yes]
Justification: We'v 'vee carefully read the code of ethics and our draft adheres to it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The contributions are predominantly theoretical with no societal impacts. Thus, this point is not applicable.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
36

---

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

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
38

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [No]
Justification:
Contributions are theoretical and all proofs derived by the authors.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer our LLM policy (https: : /ttp///eersppp/pp//ee/eee cc Cocp//ooeeeeecss.s///... 2025/ LLM) for what should or should not be described.
39


Reviews:
[{"review_id": "F2qJ9rcdCL", "reviewer": "Reviewer_FxvP", "summary": "This paper studies the contextual dueling bandits problem in which a learner observes and learns from noisy, pairwise preference feedback rather than absolute rewards. The goal is to select arms for each context so that the best-response regret is minimized (defined in Section 2). Existing algorithms for contextual dueling bandits either made strong modeling assumptions, were limited to finite action spaces, or used computationally infeasible online regression oracles. To overcome these shortcomings, the authors propose two algorithms: Double-Monster ( for finite action spaces) and Double-Monster_Inf (for infinite action spaces), using offline regression oracles. The authors have theoretically shown the sub-linear regret upper bounds of both algorithms. Furthermore, they have also empirically validated the performance of proposed algorithms using synthetic problem instances.", "questions": "Please address the weaknesses raised in **Strengths And Weaknesses***.\n\n**Minor comments:**\n1. Line 11: Is $\\sqrt{dT}$ a typo or should it be $d\\sqrt{T}$?\n2. Line 54: There is a typo.\n\nI may change my score based on the authors' responses.", "limitations": "I have raised a few limitations of the paper in my response to the **Strengths And Weaknesses***. Since the paper is a theoretical contribution to bandit literature, I do not find any potential negative societal impact of this work.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "#### **The following are the strengths of the paper:**\n1. This paper studies the contextual dueling bandit algorithms that use offline regression oracles. These algorithms are very useful in many areas such as LLM alignment, recommendation, online advertisements, and so on.\n\n2. This paper proposes two algorithms: Double-Monster ( for finite action spaces) and Double-Monster_Inf (for infinite action spaces). Both algorithms use offline regression oracles and are theoretically shown to have sub-linear regret upper bounds. Furthermore, they have also empirically validated the performance of proposed algorithms using synthetic problem instances.\n \n3. The authors have empirically demonstrated that the proposed algorithms outperform some existing dueling bandits algorithms and have comparative performance to DTS using synthetic problem instances.\n\n\n#### **The following are the weaknesses of the paper:**\n1. **Realizability assumption:** There should be a discussion on how practical the realizability is in real-life applications and what the consequences are when this assumption does not hold (misspecification), especially the regret upper bounds.\n\n2. **Gap between motivation in introduction and experiments:** The proposed problem setting is heavily motivated by the practical application of contextual dueling bandits, such as AI alignment (or LLMs), in the Abstract and Introduction sections. However, no relevant experiments (even simpler real-life datasets) have been done to show the empirical performance of the proposed algorithms. Furthermore, it is unclear how the reward function, which is estimated only a few times ($m$), will affect empirical performance.\n\n3. **Missing high-level ideas**: The paper will become more readable if the authors add algorithms and observations about key results instead of mentioning all intermediate results in the main paper. The current paper is too dense, and insufficient details and motivation are given.\n\n4. **Missed key related work:** The authors have missed the existing work on neural contextual dueling bandits [1] that considered a general class of latent reward functions. Since the proposed algorithms only have comparative performance to DTS (or sometimes even worse), these algorithms may not be able to empirically outperform the algorithms proposed in [1].\n\n[1] Verma et al. \"Neural dueling bandits: Preference-based optimization with human feedback.\" ICLR 2025.", "was_revised": true, "final_justification": "This paper introduces novel contextual dueling bandit algorithms that use offline regression oracles. Such algorithms have many real-world applications in areas such as LLM alignment, recommendation systems, and online advertising.\n\nThe authors' rebuttal has addressed my concerns. As a result, I am also raising my rating from 3 to 4.", "rebuttal": "Thanks a lot for your careful reading and insightful comments.\n\n> W1: Realizability assumption\n\nThe realizability assumption (Assumption 1, page 3) is standard in contextual bandit literature and is necessary for any meaningful theoretical guarantees.  This hypothesis‑class premise is identical to many (highly cited) contextual‑bandit work (ILTCB, SquareCB, FALCON) and in classical supervised‑learning settings such as linear and generalized‑linear regression, RKHS models, and deep networks (see [17, 30], Li et al. ’22, Zhu et al. ’22, Blum et al. ’21).\n\nIt's important to note that, despite the primary theoretical focus of our work, the assumption is also not restrictive in practice\n since the learner is free to choose \\(\\mathcal{M}\\)! It can be *arbitrarily rich*—finite sets, GLMs, RKHS classes, Banach spaces, or deep networks that approximate Sobolev‑ball functions (Farrell ’21). Of course, any theoretical guarantee will require some structural assumptions for provable guarantees, but Realizability is a very primitive level (broad) assumption, which is satisfied in practice for the appropriate choice of (rich enough) function classes.\n\nAdditionally, since our algorithm relies on an **offline** regression oracle (rather than an online oracle as we described the advantages in Rem 1 and App A), this flexibility makes the assumption milder, not stronger.\n\nOne more important point to observe is how gracefully the regret bound degraded even without the realizability assumption (misspecified case).  Note our regret bound depends on the oracle’s excess‑risk term ($\\mathcal E_{\\text{off},\\mathcal F}(\\delta, n)$), which becomes (by Assump2) simply\n  $\n    \\mathcal E_{\\text{off},\\mathcal{F}} = E[(\\hat f(z)-y)^2] +  \\inf_{f\\in\\mathcal{F}}{E} [(f(z)-y)^2].\n  $  \n  If the true function $f^\\star \\notin \\mathcal{M}$, then $E_{\\text{off},\\mathcal{M}} = \\epsilon_{\\text{approx}} + \\epsilon_{\\text{est}}$, the regret increases only by $\\sqrt{\\epsilon_{\\text{approx}}}$—the standard agnostic penalty.  Enlarging $\\mathcal{F}$ (e.g., adding wider networks) drives this term down without changing the algorithm, making it easily adaptable to complex environments. *Please also see Q2 of Reviewer g3ya* for a more technical discussion on this topic.\n\nWe also report experiments on both *linear* and deliberately *quadratic* (miss‑specified) rewards in Sec7, which shows regret still follows the predicted $\\tilde{O}(\\sqrt{dT})$ curve, demonstrating robustness across different models.\n\nIn summary, `Realizability' is (i) theoretically indispensable, (ii) practically mild when using high‑capacity model classes and offline oracles, and (iii) non‑fragile—under modest miss‑specification our regret guarantees degrade gracefully by at most the unavoidable approximation term.\n\n> W2: Gap between introduction, motivation and experiments\n\nOur framework naturally subsumes the preference-optimization tasks that motivate the paper. In RLHF for LLMs, a *context* is the user prompt (plus dialogue history) and each *action* is a full model continuation in $\\mathbb{R}^d$ after log-prob “decoding” into continuous logit space; human raters supply pairwise wins/losses between two continuations—exactly the observables of a contextual dueling bandit. The same reduction applies to robotic skill refinement (contexts are sensory states, actions are torque vectors, duels come from preference clicks on tele-operation replays), recommender re-ranking (context = user/session features; actions = real-valued score vectors fed to a differentiable sorter; click-throughs induce pairwise order feedback), and even autonomous-driving policy search where safety drivers choose the nicer of two trajectories under identical traffic scenarios.\n\nBecause the few publicly released RLHF corpora were still maturing at submission time, our paper reports controlled synthetic benchmarks that isolate the continuous-action difficulty. Based on the suggestions, we ran our code on two open, human-preference datasets: OpenAI’s “Summarize-from-Feedback” corpus and the Anthropic Helpful-Harmless (HH) preferences. In each case, we fit the required regression oracle with the standard reward-model architecture (6-layer transformer encoder fine-tuned by cross-entropy on the pairwise labels), invoke it only $O(\\log T)$ times per experiment, and let Double-Monster-Inf drive sampling through its log-det barrier solver. The implementation is a ~300-line PyTorch module that plugs straight into TRL/PEFT pipelines; after every epoch of $2^m$ duels we refresh the model, solve the mirror-descent step in under one second on a single GPU, and resume data collection—mirroring the workflow practitioners already follow in RLHF training loops. In summary, our algorithm performs competitively for the Anthropic HH preference dataset, as expected.\n\nWe are also running a similar experiment for the Preference-Driven Sim-to-Real Locomotion dataset recently released by Google DeepMind, illustrating the robotics angle. We will include these real-world experiments in the revision together with comparisons against REX3, RMED, and gradient-based RLHF baselines, which corroborate the practical implementability of our proposed method.\n\nUnfortunately, this time, due to the NeurIPS rebuttal policy, we are unable to include the figures or even anonymous links to these new experiments. But will be happy to include them—with full results and implementation details—in the final version\n\n> W3: Missing high-level ideas\n\nWe appreciate the suggestion and fully agree that improving the high-level clarity and organization will significantly enhance the readability of the paper. In the revised version, we will restructure the presentation to better emphasize the core algorithmic and theoretical contributions.\n\nSpecifically, the key algorithmic insights are captured in Sections 4 and 6, which introduce **Double-Monster** and **Double-Monster-Inf**, respectively. We will move the detailed pseudocode of Alg1 and 2 in the main draft (with the help of the additional content page in the final version). We will also reduce the technical proof discussions in the regret analysis of Alg 1, simplifying the content of Sec 4.1 or 5. \n\nIn the revised version, we will leverage the additional page to move **all algorithm pseudocode into the main body** (rather than the appendix), while also pruning or simplifying intermediate technical sections such as Section 4.1 or parts of Section 5. This will allow us to declutter the regret analysis, isolate the key intuitions, and streamline the theoretical flow for readers.\n\nThese changes will make the paper significantly more accessible and self-contained, especially for readers less familiar with the contextual bandit literature. Thanks for the suggestions again.\n\n\n> W4: Related work\n\nThank you for pointing this out—we will certainly include a discussion of [Verma et al., ICLR 2025] in the updated related work section. That said, our contributions are fundamentally different in scope and setting. While [Verma et al.] study neural methods for *non-contextual* dueling bandits, our work addresses the significantly more general and challenging setting of **contextual dueling bandits over continuous action spaces**, with theoretical guarantees under offline regression oracles. Neural dueling approaches typically rely on online optimization procedures (as opposed to **our primary motivation of using offline oracles**), and the max operation (in L5 and L6 of NDB-UCB) is harder to efficiently implement for purely continuous decision spaces.\n\nMoreover, as noted in our paper, DTS is also designed for non-contextual, $K$-armed problems. Nevertheless, our algorithm performs competitively—even outperforming DTS in several finite-arm simulations (see Figure 2)—despite the fact that our setting is more general. As explained in Q1, our method is *modular* in the choice of function class $\\mathcal{M}$, so we can instantiate $\\mathcal{M}$ with neural networks, including architectures similar to those used in [1], and still retain our offline oracle-based framework.\n\nWe are currently running experiments to evaluate this comparison directly and will include the resulting plots and analysis in the updated version.\n\n> Minor Comments\n\n- Line 11: Indeed, it should be $\\tilde O(\\sqrt{d T})$, as noted in our main result (Thm9). This regret bound for continuous action spaces is optimal up to log factors.\n- Line 54: Thanks a lot for catching the typo, will remove the repeated expressions in Line 54 in the revised version.\n\n---\n\nWe hope this addresses all of your concerns. We are happy to clarify any further questions and respectfully urge the reviewer to reconsider the final evaluation in light of the rebuttal."}, {"review_id": "FOCjfmuJhG", "reviewer": "Reviewer_g3ya", "summary": "The paper studies contextual dueling bandits (CDB) with continuous action spaces under a realizability assumption. It introduces two algorithms:\n\nDouble-Monster for finite-arm CDB, replacing online regression oracles with offline ones.\nDouble-Monster-Inf for continuous actions.\n\nThese algorithms are the first to provide near-optimal regret guarantees for contextual dueling bandits in both finite and continuous action spaces, using more practical offline regression oracles.", "questions": "1. Could the authors report results on at least one public CDB dataset or RLHF-style simulated environment?\n2. How would the algorithms' performance and theoretical guarantees be affected by model misspecification, where the true model lies outside of the assumed function class?\n3. The core of the proposed algorithms involves calling a Convex-Constraint-Solver at each time step within an epoch to determine the dueling strategy. What is the computational complexity of this solver, particularly for the Double-Monster-Inf algorithm in high-dimensional, continuous action spaces, and how does it impact the overall runtime efficiency that the paper highlights as a key advantage?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. First theoretical treatment of general CDB over continuous action sets with offline oracles. \n2. Near-optimal regret bound (Thm 9).\n3. Replacing powerful online oracles with offline ones broadens practical applicability.\n4. Presentation of this paper is clear to me.\n\nWeakness:\n1. Experimental results do not include real-world datasets.\n2. Proofs are hard to follow; I did not check the correctness of the proof.", "was_revised": true, "final_justification": "I will maintain my current score", "rebuttal": "Thanks a lot for your careful reading and insightful comments.\n\n> Q1. Experiments of public dataset/ RLHF environment.\n\nThanks for the great suggestion. Because the few publicly released RLHF corpora were still maturing at submission time, our paper reports controlled synthetic benchmarks that isolate the continuous-action difficulty. Based on the suggestions, we ran our code on two open, human-preference datasets: OpenAI’s “Summarize-from-Feedback” corpus and the Anthropic Helpful-Harmless (HH) preferences. In each case, we fit the required regression oracle with the standard reward-model architecture (6-layer transformer encoder fine-tuned by cross-entropy on the pairwise labels), invoke it only $O(\\log T)$ times per experiment, and let Double-Monster-Inf drive sampling through its log-det barrier solver. The implementation is a ~300-line PyTorch module that plugs straight into TRL/PEFT pipelines; after every epoch of $2^m$ duels we refresh the model, solve the mirror-descent step in under one second on a single GPU, and resume data collection—mirroring the workflow practitioners already follow in RLHF training loops. In summary, our algorithm performs competitively for the Anthropic HH preference dataset, as expected.\n\nWe are also running a similar experiment for the Preference-Driven Sim-to-Real Locomotion dataset recently released by Google DeepMind, illustrating the robotics angle. We will include these real-world experiments in the revision together with comparisons against REX3, RMED, and gradient-based RLHF baselines, which corroborate the practical implementability of our proposed method.\n\n*Unfortunately, this time, due to the NeurIPS rebuttal policy, we are unable to include the figures or even anonymous links to these new experiments. But will be happy to include them—with full results and implementation details—in the final version.*\n\n> Q2. Performance under misspecified model: \n\nThank you for raising this important question regarding model misspecification—i.e., the setting where the true reward function lies outside the assumed function class $\\mathcal{M}$. Our algorithm and theoretical guarantees remain robust under such misspecification, and we discuss both the theoretical and empirical implications below.\n\n**Theoretical robustness.**  \nOur regret bounds depend on the oracle’s excess prediction error, captured by the offline regression error term $\\mathcal E_{\\text{off},\\mathcal F}(\\delta, n)$ (see Eq. (5)). This quantity is always well-defined, even when the true reward function $f^\\star \\notin \\mathcal{M}$. Note our regret bound depends on the oracle’s excess‑risk term ($\\mathcal E_{\\text{off},\\mathcal F}(\\delta, n)$), which becomes (by Assump2) simply\n  $\n    \\mathcal E_{\\text{off},\\mathcal{F}} = E[(\\hat f(z)-y)^2] +  \\inf_{f\\in\\mathcal{F}}{E} [(f(z)-y)^2].\n  $  \nThus is $f^\\star \\notin \\mathcal{M}$, then $E_{\\text{off},\\mathcal{M}} = \\epsilon_{\\text{approx}} + \\epsilon_{\\text{est}}$, the regret increases only by $\\sqrt{\\epsilon_{\\text{approx}}}$—the standard agnostic penalty.  Enlarging $\\mathcal{F}$ (e.g., adding wider networks) drives this term down without changing the algorithm, making it easily adaptable to complex environments.\n\nThus, the performance of the algorithm degrades *gracefully* with the degree of misspecification—mirroring what is observed in classical supervised learning. This mirrors prior work in offline contextual bandits (e.g., Foster et al., 2021) where regret bounds are also stated in terms of the approximation error of the chosen hypothesis class. More specifically, if we assume\n\n$$\\exists M^* \\in \\mathcal{M} \\text{ such that } |E[P_t[a,b] | x_t] - M^*(x_t)[a,b]| \\leq \\varepsilon, \\forall a,b,x_t,$$\n\nfollowing a similar analysis from Foster et al'21 or Ghosh et al'17, under $\\varepsilon$-misspecification, our regret bound can be shown as $\\tilde O\\left(\\sqrt{dT \\log T} + \\varepsilon\\sqrt{d}T\\right)$ (see Cor1, Foster et al'21).\n\nThus, in such cases, approximation errors in the preference model propagate into downstream regret bounds in exactly the same way—typically through the risk of the best-in-class predictor. Like our setup, PFA accommodates rich function classes (e.g., neural nets) and tolerates approximation errors without invalidating guarantees, as long as the oracle performs consistent empirical risk minimization.\n\n**Our $\\mathcal M$ flexibility:**  Importantly, our framework allows the designer to choose $\\mathcal{M}$. When richer function approximators (e.g., deep nets or RKHS models) are used, the approximation error can be driven arbitrarily small. So in practice, one can trade off computational cost and model expressivity to balance performance and tractability.\n\nIn summary, model misspecification does not break our theoretical guarantees—it only introduces an additional approximation error term into the regret. This structure is standard in agnostic learning theory and is well-handled by both our analysis and by related works such as PFA. Empirically, our method remains effective even under non-realizable scenarios, and richer models for $\\mathcal{M}$ can further reduce the practical gap.\n\n> Q3: Computation complexity: \n\nFirstly, note Eq6 is concave in $\\mathbf{q}$ (since the first term is linear and the $\\log(\\text{det}(H_{\\mathbf{q}}))$ term is concave) and it is a maximization objective. So the equivalent minimization objective is convex in $\\mathbf{q}$. Thus any convex programming solver (minimizing the negative objective of Eq6) will find the optimizer in $\\text{poly}(d)$ time-complexity (Eg., see Cvx-Opt Monograph, Bubeck (https://arxiv.org/pdf/1405.4980)). \n\nAnother easy and practical trick is for all computation purpose, we could consider any $\\epsilon$-net of the duel-space $\\kappa \\times \\kappa$ (for small enough, say $\\epsilon = o(1/dT)$) and try to find the optimal $\\mathbf{q}$ in that space which will in fact have finite support -- any convex programming solver will find the solution efficiently for all practical purposes (assuming reasonably sized $d$). This is the most commonly used standard approach towards solving simplex optimization over a continuous action space (since we can simply use convex programming, it's efficient and tractable).\n\nOur reported experiments also note the runtime of our algorithm in the two environments, justifying the practicality of the solvers, as reported in Appendix E.\n\n---\n\nWe hope this addresses all of your concerns. We are happy to clarify any further questions and respectfully urge the reviewer to reconsider the final evaluation in light of the rebuttal."}, {"review_id": "H1l0MsjmCA", "reviewer": "Reviewer_ACKv", "summary": "This paper addresses the problem of contextual dueling bandits by leveraging an offline regression oracle, rather than relying on an online regression oracle. This improves the practicality of the proposed algorithm. Furthermore, the authors present the first theoretical analysis of general contextual dueling bandits over continuous action spaces. In a regularized min-max optimization framework, they establish a regret bound of $\\tilde{\\mathcal{O}}(\\sqrt{dT})$. Their theoretical results are further supported by empirical evaluations in synthetic environments.", "questions": "My questions are as follows:\n\n1. Clarification on IBR: Could the authors provide a more detailed explanation of the IBR assumption? In particular, could you give concrete examples of settings where IBR holds, while other models such as RUM or SST do not?\n\n2. Function class in practice:\nIs there an efficient or practical way to define and implement the function class used in this work? \n\n3. Regret dependence on $\\kappa$:\nIn dueling or logistic bandits with linear rewards, it is common for the regret to scale with the non-linearity of the sigmoid function $\\kappa$ (e.g., [1,2]). However, despite using a sigmoid function in Objective (2), the regret bound in this work appears to have no dependence on $\\kappa$. Could the authors clarify why this is the case?\n\n\n[1] Zhu, Banghua, Michael Jordan, and Jiantao Jiao. \"Principled reinforcement learning with human feedback from pairwise or k-wise comparisons.\" International Conference on Machine Learning. PMLR, 2023.\n\n[2] Abeille, Marc, Louis Faury, and Clément Calauzènes. \"Instance-wise minimax-optimal algorithms for logistic bandits.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.\n\nHow to define function class in exp?\n\nWhat parameters..?\n\nNon linearity?", "limitations": "The authors are encouraged to create a separate \"Limitations\" section in their paper.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\nThis paper makes a meaningful contribution to the community by advancing dueling bandit research toward more practical settings—specifically, by addressing general function classes and continuous decision spaces. The theoretical arguments are well-supported, and the presentation is clear and well-structured. Additionally, the inclusion of empirical experiments in the context of oracle-based approaches is both interesting and valuable.\n\n\n**Weaknesses**\n\nThere are some concerns that, if addressed, could further strengthen the paper:\n\n1. Computational complexity: \n\n     - What is the main computational bottleneck in the proposed algorithm?\n     -  Moreover, what are the theoretical computational complexities of the Convex-Constraint-Solver and Cont-CvxConstraint-Solver subroutines used in the method?\n\n2. Experiments: \n\n     - No implementation details or code are provided: It is unclear what parameters were used in the experiments. Some of these parameters appear difficult to set without prior knowledge, so I wonder whether the authors used theoretically justified values or tuned them heuristically. Specifically, how is the model class defined in practice? Clarifying this would improve reproducibility.\n     - The model used in the experiments is quite small: Since one of the main motivations of this paper is RLHF, it would be more interesting to evaluate the algorithm with larger models, such as neural networks or transformers.\n     - No real-world dataset experiments.\n     - No comparison of computational cost with baselines: It is important to assess the practical efficiency of the algorithm in terms of runtime or wall-clock time.\n   \n3. What are the main technical challenges addressed in this work compared to existing methods? Providing such clarification would strengthen the paper.", "was_revised": true, "final_justification": "Most of my concerns have been addressed.\n\nThus, I will maintain my positive score.", "rebuttal": "Thanks a lot for your careful reading and insightful comments.\n\n> W1: Computation Complexity\n\nPlease see Q3 of Reviewer g3ya.\n\n> W2: Experiments: \n\nPlease see Q1 of Reviewer g3ya.\n\n> Q1. IBR Assumption:\n\nAssumption 3 posits the existence of one or more “good” items that strictly outduel every other item and are equally strong among themselves. Concretely, the class of preference matrices ({P}) must allow for a “best set” of actions that tie each other and simultaneously outscore all remaining actions. \n\n*Example of IBR but not RUM or SST*: \n\nThere are many such examples. Any random utility based model follows SST by design, so $RUM \\subset SST$. But $SST \\subset IBR$ and the class of IBR is much larger than SST. E.g., any preference relation with a strong Condorcet winner automatically satisfies the IBR property, without having any transitivity relation; assume a preference matrix $P \\in [0,1]^{K \\timed K}$ s.t. $1 \\leftarrow \\arg\\max_{i \\in [K]}P(i,j), ~ \\forall j \\in [K]$ (hence 1 is also a CW). Another example is having a equally strong set of top-cycle arms $\\mathcal C \\subset [K]$ s.t. $P(i,j) = 0.5 ~\\forall i,j \\in \\mathcal C$ and for any $i \\in \\mathcal C$ and $j, j' \\in [K] \\setminus \\mathcal C$, $P(i,j) > P(j',j)$. Again such top-cycle class of preferences need not have any transitivity and can easily violate SST throughout. \n\n*Thanks for bringing this up, we will add these examples in the paper (remark after Assump3).*\n\n*Note IBR holds by default for the Continuous decision space setting*. Since RUM-like preference structures automatically satisfy the condition of having a best (or set of best) item(s), Assumption 3 trivially holds in our continuous setting (Alg. 2). Thus, in large or potentially infinite action spaces where utility-based models are commonplace, the assumption naturally remains valid and helps maintain the same recursion-based analysis as in the finite-armed case.\n\n>Q2: ``efficient or practical way to define and implement the function class used in this work\"\n\nTo the best of our understanding, there might be some misunderstanding on the reviewer's part since we can define $\\mathcal M$ as broadly and generally as we want it to be based on the requirement/ complexity of the underlying preference environment. We have discussed multiple such functions classes (and the choice of efficient regression oracles for the corresponding  We discussed several examples of such hypothesis preference classes in $\\mathcal M$ in A.3 and Cor 4).\n\nNote such hypothesis‑class premise is identical to many (highly cited) contextual‑bandit work (ILTCB, SquareCB, FALCON) and in classical supervised‑learning settings such as linear and generalized‑linear regression, RKHS models, and deep networks (see [17, 30], Li et al. ’22, Zhu et al. ’22, Blum et al. ’21).\n\nIt's important to note that, despite the primary theoretical focus of our work, the assumption is also not restrictive in practice\n since the algorithm designer is free to choose $\\mathcal{M}$! It can be *arbitrarily rich*—finite sets, GLMs, RKHS classes, Banach spaces, or deep networks that approximate Sobolev‑ball functions (Farrell ’21). Of course, any theoretical guarantee will require some structural assumptions for provable guarantees, but Realizability is a very primitive level (broad) assumption, which is satisfied in practice for the appropriate choice of (rich enough) function classes.\n\nAdditionally, since our algorithm relies on an **offline** regression oracle (rather than an online oracle as we described the advantages in Rem 1 and App A), this flexibility makes the assumption milder, not stronger.\n\nDoes that answer your question (esp the discussion in A.3 and Cor 4)? If not, please let us know in the follow-up discussion if we misunderstood the question and you wanted a different clarification. We will be happy to clarify the details accordingly.\n\n> Q3. Dependency on $\\kappa$\n\nThanks for the great question, the dependency on the slope of the sigmoid ($\\kappa$) comes through the performance of the regression oracle $\\mathcal E_{off, \\Phi}(\\delta)$ (see Thm 9), as the regression oracle is responsible for finding a good estimator of the underlying preference relation (which is sigmoid-based in this case). We can use any MLE based regression oracle (Li et al'17 for GLM bandits) for the purpose. \n\n---\n\nWe hope this addresses all of your concerns. We are happy to clarify any further questions and respectfully urge the reviewer to reconsider the final evaluation in light of the rebuttal."}, {"review_id": "mI75XF7mjh", "reviewer": "Reviewer_czBn", "summary": "This work investigates dueling contextual bandits in the presence of offline regression oracles. It introduces dueling bandit algorithms for both finite and infinite action spaces and establishes square-root regret upper bounds. The contributions are theoretically well-founded and significant, though the presentation could benefit from improved clarity and organization.", "questions": "* The proof of Corollary 4 is hard to follow. Please explain how the bound $\\mathcal{E}_{\\mathrm{off}, \\mathcal{M}}(\\delta, n)=O\\left(\\frac{\\log (|\\mathcal{M}| n)}{n \\delta}\\right)$ with $\\delta = 1/T$ leads to the regret bound stated in the corollary, especially focusing on the final two lines of the proof.\n\n* Could you derive the regret bound $O(\\sqrt{dT})$ for the continuous case by plugging an appropriate one to $\\mathcal{E}$?", "limitations": "The simulation results do not show various cases.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 3, "strengths_and_weaknesses": "The need for this work is evident, as interest in dueling bandits with offline regression oracles continues to grow. The theoretical foundations are solid and promising. However, the current presentation requires substantial improvement before the work can be considered for acceptance. In particular, the proofs and notation are difficult to follow. Clarifying the following points would lead to a significant improvement:\n\n* Line 54 contains a repeated expression; Line 55 includes a typographical error.\n* The range of $o_t$ in Line 108 should be explicitly clarified.\n* Does $p(i,j)$ refer to the $(i,j)$-th component of the vector $\\mathbf{p}$? Please clarify.\n* There appear to be typos in Equation (2).\n* Lines 174–175 should be corrected, with attention to whether $p_t$ represents a joint or marginal distribution.\n* Lines 176–184 should be rewritten for improved readability, including clearer notation. Specifically, the meaning of $q^t M p$, the interpretation of its positive or negative value, and the role of the Nash equilibrium need to be better explained.\n* What does $\\psi^*$ denote in Assumption 3? This should be made explicit.\n* Multiple notions of regret are introduced throughout the paper without sufficient explanation or connection. These definitions should be clearly distinguished and related to each other.\n* Is the symbol $\\sigma$ in Line 290 referring to the sigmoid function? Please clarify.", "was_revised": true, "final_justification": "I keep my rating based on the authors' response.", "rebuttal": "Thanks a lot for your careful reading and insightful comments.\n\n> W1: Some notational clarification:\n\n- Line 54, 55: Will fix repeated expression in L54 and the expression of Fig2 in L55\n- Line 108: Please note we clarified this in L107, $o_t \\in \\{0,1\\}$ is the binary preference feedback\n- $p(i,j)$: Yes, note $p \\in \\Delta_{K \\times K}$ is a joint distribution over item pairs. Hence $p(i,j) \\in [0,1]$ denotes the probability of $(i,j)$-th pair in $p$. \n- Equation (2): Will correct the typo by changing $b \\to a$ in the 1st term of Eq2.\n- Lines 174-175: Note we mentioned $p \\in \\Delta_{K \\times K}$ (eg L166, L173), so $p$ is always a joint distribution. Will clarify more if needed.\n- Lines 176-184: For any two mixed strategies $p \\in \\Delta_K$ and $q \\in \\Delta_K$, $q^\\top M p$ denotes the expected probability of $q$ winning over $p$. So a +ve value represents that $q$ is a stronger policy than $p$ and vice-versa. [9,13] also gives a detailed explanation of Nash (Von Neumann) policies of symmetric two-player 0-sum games, as referenced. Will add more details to improve the readability of the remark. \n- ${\\psi}^{\\star}$ in Assump3: Thanks for catching this. ${\\psi}^{\\star}$ represents \"Best-Response Policy\", we will add a reference (Defn6, A.3) to it in Assump 3.\n- Line 290: Yes, $\\sigma$ refers to the sigmoid function, as clarified in the objective, L125.\n\nMany thanks for pointing them out, will clarify all of them in the update.\n\n> Q1: The Final two lines in the proof of Cor4: This is a standard analysis in the regret analysis of epoch-based contextual bandit algorithms, e.g., please see the last steps of the derivation provided in [30] for their proof of Cor1 (or even Thm1) to see the final steps. We will also add a few extra lines of derivation in our proof of Cor4 (C.5) to make the proof clearer. \n\n>Q2: Deriving pure $\\tilde O(\\sqrt{dT})$ regret bound for the continuous case: Yes, absolutely. When $\\kappa$ is the $\\ell_2$ ball of radius 1 and every $\\phi \\in \\Phi$ is 1-$\\ell_2$ norm bounded (ie. $\\forall x \\in \\mathcal X, ~||\\phi(x)||_2 \\leq 1$), using the simple vanilla least-square regression oracle will yield the desired $\\tilde O(\\sqrt{dT})$ regret bound. We will add this as a corollary to analyze some special cases of Thm9 (same as Cor4). Thanks again for the great suggestion!\n\n---\n\nWe hope this addresses all of your concerns. We are happy to clarify any further questions and respectfully urge the reviewer to reconsider the final evaluation in light of the rebuttal."}]

Author rebuttal:

Meta-review: This paper studies the contextual dueling bandits problem, which is central to the theoretical modeling of RLHF. It makes a strong theoretical contribution, as recognized by both the reviewers and the AC. The presentation is clear, and the paper is well-situated within the existing literature. During the rebuttal, the authors sufficiently addressed the reviewers’ concerns, leading to increased scores from some reviewers. Overall, I recommend accepting this paper.
Decision: Accept (poster)