Best-of-three-worlds Analysis for Dueling Bandits with Borda Winner
Authors: Zirui Hu
Tingyu Zhang
Fang Kong
Venue: ICLR 2026 Poster (2026)
Keywords: dueling bandits; borda winner; best of three worlds; FTRL
Primary area: learning theory

Abstract: The dueling bandits (DB) problem addresses online learning from relative preferences, where the learner queries pairs of arms and receives binary win-loss feedback. Most existing work focuses on designing algorithms for specific stochastic or adversarial environments. Recently, a unified algorithm has been proposed that achieves convergence across all settings. However, this approach relies on the existence of a Condorcet winner, which is often not achievable, particularly when the preference matrix changes in the adversarial setting. Aiming for a more general Borda winner objective, there currently exists no unified framework that simultaneously achieves optimal regret across these environments.
In this paper, we explore how the follow-the-regularized-leader (FTRL) algorithm can be employed to achieve this objective. We propose a hybrid negative entropy regularizer and demonstrate that it enables us to achieve $\tilde{O}(K^{1/3} T^{2/3})$ regret in the adversarial setting, ${O}({K \log^2 T}/{\Delta_{\min}^2})$ regret in the stochastic setting, and $O({K \log^2 T }/{\Delta_{\min}^2} + ({C^2 K \log^2 T }/{\Delta_{\min}^2})^{1/3})$ regret in the corrupted setting, where $K$ is the arm set size, $T$ is the horizon, $\Delta_{\min}$ is the minimum gap between the optimal and sub-optimal arms, and $C$ is the corruption level. These results align with the state-of-the-art in individual settings, while eliminating the need to assume a specific environment type. We also present experimental results demonstrating the advantages of our algorithm over baseline methods across different environments.

Under review as a conference paper at ICLR 2026
000
BEST-OF-THREE-WORDD ANALYSIS FOR DUELING
001
BANDITS WITH BORDA WINNER
002
003
004
005
Anonymous authors
Paper under double-blind review
006
007
008
009
ABSTRACT
010
011
The dueling bandits (DB) problem addresses online learning from relative prefer- ences, where the learer queries pairs of arms and receives binary win-loss feed- back. Most existing work focuses on designing algorithms for specific stochastic adversarial environments. Recently, a unified algorithm has been proposed that achieves convergence across all settings. However, this approach relies on the existence of Condorcet winner, which is often not achievable, particularly when the preference matrix changes in the adversarial setting. Aiming for a more general Borda winner objective, there currently exists no unified frame- work that simultaneously achieves optimal regret across these environments. In this paper, we explore how the follov-teerrgullarizee--ee can be employed to achieve this objective. We investigate a hybrid negative en- tropy regularizer and demonstrate that it enables us to achieve Ö (KK1/3T2/3) re- gret in the adversarial setting, O(K log" T //Aamm regret in the stochastic setting, and O(K log" T / + (C K log" T/ )1/a) regret in the corrupted setting, where K the arm set size, T is the horizon, Amin the minimum gap between the optimal and sub-optimal arms, and C' is the corruption level. These results align with the ofate-of-the-art in individual settings, while eliminating the need to assume a specific environment type. We also present experimental results demon- strating the advantages of our algorithm over baseline methods across different environments.
012
013
014
015
016
017
018
019
(FTRL) algorithm
020
021
022
023
024
025
026
027
028
029
030
031
INTRODUCTION
032
033
In online sequential decision making, the multi-armed bandit framework (MAB) has played crucial role in optimizing decisions under uncertainty (Lattimore & Szepesvári, 2020). Traditional MAB relies on absolute numerical rewards, which can often be noisy or challenging to obtain from users. To overcome this limitation, the dueling bandits (DB) problem provides a robust alternative using relative comparisons, where the learner queries pairs of actions (arms) and receives binary feedback on the preferred option (Bengs et al., 2021). This approach closely mirrors real-world scenarios where comparative judgments are more natural and reliable and has broad applications in areas such as search optimization. tournament ranking, retail management, and reinforcement learning from human feedback (RLHF) Yuue & Joachims 2009; Dudik al. 201 Christiano et al. 2017
034
035
036
037
038
039
040
041
042
DB algorithms aim to minimize regret over a given horizon, defined as the cumulative gap between the rewards of designated winners and the rewards obtained. The Condorcet and Borda winners are among the most widely studied winner objectives (Yue et al.) 2012 Bengs et al., 2021). Exist- ing research has explored various preference settings, including the stochastic case where relative preferences are fixed (Yue & Joachims 2009). the adversarial case with arbitrarily changing prefer- ences(Saha et al. 2021), and the corrupted case, which lies between them (Agarwal et al., 2021).
043
044
045
046
047
048
Despite the importance of these contributions, they provide convergence guarantees only under spe- cific environments. Once the environment shifts-for instance, when an algorithm tailored for the stochastic setting is applied to an adversarial one-the performance can degrade to linear regret. De- signing algorithms that achieve optimal performance across environments without relying on prior knowledge has therefore become problem of broad interest in the field (Bubeck & Slivkins 2012
049
050
051
052
053
Zimmert & Seldin 202T: Kong et al., 2023 Tsuchiya et al., 2023: Ito & Takemura, 2023b a Ito
et al. (022)..

---

Under review as a conference paper at ICLR 2026
054
Table 1: Regret bounds comparison under different environments and winners, where K is the num- ber of arms, T is the time horizon, C' is the corruption level, Amin is the minimum sub-optimality gap (to the optimal arm). O hides polylogarithmic factors.
055
056
057
058
Environment
059
Algorithm
Adversarial
Stochastic
Corrupted Stochastic
060
061
Condorcet
062
Saha & Gaillard
2022
O(VKT)
O
K log Amia
o
A log T Amin + v K + C)
Versatile-DB
063
064
Borda
065
Saha et al. )
0(K1/372/3)
066
Dueling- EXP3
067
Saha et al. 2021
O
K Klog(KT) Amin
068
BCB
069
Ours
0(K1/372/3)
o
K log T Tlog( (TT)
K log T log(KT) A
070
Auia
071
C² log T (oT(
1/3)
072
A
073
074
075
Saha & Gaillard (2022) study the best-of-three-world problem for dueling bandits under the Con- dorcet winner. They propose DB-MAB reduction framework and demonstrate that existing analy- ses for MAB can be adapted to yield best-of-three-wort guarantees for the DB setting. However, the Condorcet winner-defined as the arm that is preferred over every other arm with probability greater than 0.5 may not always exist, particularly in adversarial environments where the preference matrix evolves over time. By contrast, the Borda winner, defined as the arm that maximizes the average preference probability over all other arms, always exists regardless of the environment. Neverthe- less, extending [Saha Gaillard (2022)'s DB-MAB reduction to the Borda winner is challenging because the regret definitions fundamentally differ: Condorcet regret decomposes into dominance gaps that enable a clean MAB mapping. whereas Borda regret aggregates average scores, render- ing the Theorem 2 in Saaa & Gaillard wwich assumes pairwise independence for regret bounds- inaplldsia from the outset. Therefore, establishing a best-of-three. three-world analysis for dueling bandits under the Borda winner remains open problem.
076
077
078
079
080
081
082
083
084
085
086
087
In this paper, we address these gaps by developing an FTRL-bbased framework that directly opti- mizes the Borda score of the selected arms, rather than reducing the problem standard MAB formulation. Our approach leverages a hybrid negative entropy regularizer and demonstrates that the proposed algorithm simultaneously achieves performance guarantees across different environ- ments. Specifically, we establish regret upper bounds of O(K1/372/3) in the adversarial setting.
088
089
090
091
092
O(K log"///A T/ in the stochastic setting, and O(K log T + (C2 K log T/Ai,. 1/33) in the corrupted setting, where K is the arm set size, T' is the horizon, Amin is the minimum gap between the optimal and sub-optimal arms, and C' the corruption level. Table [ summarizes these results and compares our guarantees with those of existing works. To the best of our knowl- edge, this is the first algorithm to achieve a problem under the general Borda winner objective. Moreover, our algorithm achieves the optimal (KK1/3T2/3) adversarial regret of Saha et al. (202)) and retains the key Ó(K/22 min)) scaling for stochastic environments. We also provide empirical validation on different environments where our algorithm demonstrates consistent advantages over baselines for fixed environment type.
093
094
095
096
guarantee for the dueling bandit
097
098
099
100
101
102
2
RELATED WORK
103
104
Research has mostly targeted specific settings-stochasiie adversarial, and corrupted stochastic- along with key winner types, such as the Condorcet winner (an arm that beats all others more than half the time) and the Borda winner (an arm with the highest average preference score). In stochastic settings with Condorcet winners, where preferences stay constant, algorithms like RUCB perform well under Condorcet winners by balancing exploration and exploitation (Zoghi et al.) 2014); fur-
105
106
107
2

---

Under review as a conference paper at ICLR 2026
108
ther progress includes approaches that test for winners to identify them more efficiently in low-noise cases (Haddenhorst et al., 2021) and versatile methods that work across stochastic and adversarial worlds while keeping strong stochastic guarantees (Saha & Gaillard 2022). For Borda winners in stochastic DB, techniques based on generalized linear models help estimate the full preference ma- trix to reduce regret (Wu et al., 2024), and adaptations for non-stationary environments use weighted Borda scores to handle slight changes over time (Suk & Agarwal (224b). Moving to adversarial settings, where preferences can shift unpredictably, MAB-style reductions allow algorithms han- dle Condorcet winners robustly (Saha & Gaillard (022). For Borda winners here, the Dueling- -xp33 algorithm delivers strong results even without Condorcet winner existing (Saha al.. (021). and multi-dueling versions manage interactions between dependent arms (Gajane) 2024). In corrupted environments, which mix stable stochastic preferences with bounded adversarial noise, robust meth- ods like Winner Isolation with Recourse protect against disruptions for Condorcet winners (Agarwal ct al. 202I), and studies of attacks show how stochastic setups can be vulnerable (Jun et al. 2018); however, no tailored approaches yet exist for Borda winners in this mixed setting. Other winner concepts, like Copeland winners (which maximize direct wins against others) for handling cycles in preferences (Zoghi et al. 2015) and Von Neumann winners (mixed strategies that tie beat all pure arms) for contextual scenarios (Di et al.) 2025), broaden the framework further. Overall, while these works advance DB in isolated cases, unified best-of-three- whree-worlds solution for Borda winners- delivering top performance without knowing the environment in advance- is still missing, which inspires our FTRL-based method.
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
(BoTW) algorithms deliver near-optimal re- gret without prior environment knowledge, adapting across stochastic, adversarial, and corrupted settings. In multi-armed bandits, foundational BoBW methods introduce algorithms that perform well in both stochastic and adversarial regimes by integrating exploration mechanisms (Bubeck & Slivkins 2012). while subsequent work achieves nearly optimal pseudo-regret bounds for these settings (Auer Chiang 2016) Zimmert & Seldin) 202T). Notably, (Zimmert & Seldin, 2021) introduces optimal FTRL-based algorithm using Tsallis entropy regularization, providing tight pseudo-regret bounds in both stochastic and adversarial regimes. For linear bandits, BoBW W de- signs attain near instance-optimallty in stochastic cases and minimax-optimality in adversarial ones using optimistic online mirror descent with loss estimators (Lee et al., 2021), or exploration-by- optimization to balance exploration and optimization (Ito & Takemura 2023a). In BoTW for lin- ear bandits, which incorporates corrupted environments, follow-the-regularie www.-reguulaizz--leaeedee (FTRL) with negative entropy regularization and self-bounding analysis yields adaptive regret across all three worlds (Kong et al., 2023),, and variance- adaptive algorithms tune bounds hierarchically to noise levels in stochastic, corrupted, and adversarial regimes (Ito & Takemural (2023b). For linear contex- tual bandits, BoBW methods provide near-optimal regret in stochastic and adversarial settings via debiased estimators and FTRL with tailored perturbations (Kuroki et al.) 2024). dueling bandits, BoBW analyses via multi-armed bandit reductions offer guarantees under Condorcet winners for stochastic and adversarial preferences (Saha & Gaillard, (202];; yet, no Bo frameworks exist, especially for Borda winners, creating a gap in unified adaptation that our FTRL approach fills.
Best-of- bothh-f-otthworrdd (BoBW) and
128
129
130
131
132
133
134
135
136
137
138
139
variance-adaptive
140
141
142
143
144
145
146
147
3
PROBLEM SETTING
148
149
150
We study the problem dueling bandits, an online decision-making framework that involves a set of K items, denoted by [K] = 21, K}. over time horizon of T rounds. At the beginning of the process, the environment determines a sequence of preference matrices MI, M2,..,, MT in advance, where each M, [0, x encodes the pairwise preference probabilities in round
151
152
153
I E [T) : (1, .., T}. Each matrix M, satisfies the following structural properties: Mi
154
1/ for all E [K]. Here, Mi represents the probability that item i beats item j in a pairwise comparison in round t. At each round t e (T). the learner selects two distinct items Ft, Vt E [K]. and observes stochastic feedback ft ~ Bernoulli (Zt,,, Jt)), where ft = 1 indicates that item F, wins, and ft = O indicates that item y wins. To evaluate item quality, we introduce the Borda score of item i E [K] at round t, defined as  E (i.j..) which measures the average probability that item i wins against a randomly chosen distinct item. And the Borda winner i" E [K] is the item with the highest cumulative Borda score over all rounds: i" arg max Σl= (i).
1 () for all i E [K], and ii)
155
156
157
158
159
(i)
160
161
3

---

Under review as a conference paper at ICLR 2026
162
The learner's performance is quantified by the total regret: R -E= Pt. where Pt oc({²) (xx( + (3r)), which compares the Borda score of the Borda winner with the average score of the items chosen by the learner at each round.
163
164
165
For convenience, we also define the shifted Borda score for item i E [K] round t as wr(()
166
167 K K 3)-1MM(iij),, which includes the self-comparison term Mi(i, 2. The corresponding
168
shifted regret is RlJ Ei= [wx((*) (1x( we (ve)). where i is the same Borda winner
169
as defined above.
170
This is shifted version of the original Borda score or (1) -ーं Eje Mc(t,j), where the summa-
171
tion now includes the term Me a) ./b The relationship between them is (i) K K o + 2K which does not change the identity of the optimal item or the proportionality of the regret (with K K-1 Rf).
172
173
RT
174
175
The shifted Borda score is defined and used primarily to simplify the construction of unbiased esti- mates for item scores in adversarial dueling bandits problem with Borda winner (Saha al. [021). In our algorithm, estimates are derived from binary preference feedback on pairs sampled i.i.d. with replacement from a distribution dz. Including self-comparisons in wy allows for symmetric and straightforward expectation calculations, avoiding the need to exclude self-pairs (which would com- plicate sampling without replacement and increase variance).
176
177
178
179
180
181
182
3.1
PREFERENCE REGIMES
183
We define the stochastic, adversarially corrupted stochastic, and adversarial environments for du- eling bandits using the self-bounding constraint framework from Zimmert & Seldin (2021). These adapt standard multi-armed bandit models to pairwise comparisons, fitting dueling bandits. They unify regret analysis across adversarial levels, as in Zimmert & Seldin (202I). An environment follows self-bounding constraint with (A, C, if, for any algorithm,
184
185
186
187
188
189
R4J 2 E Σ AT.) -c.
190
191
192
where A : [K] + [0, 1]. Here, 7, is representative arm sampled from the algorithm's 's distribution Te, and since Te and Yr are independently and identically distributed from ny, the average score over the pair is equivalent to the performance of single arm Le,
193
194
195
Stochastic Environments: This is a special case with a (A,0, T)) self-bounding constraint (Zimmert
196
197 & Seldin 2021), where A(i) w(i") w(i) for a fixed distribution D over scores Wi-(In the stochastic dueling bandits setting, the Borda score of any arm/item a fixed deterministic constant that remains identical across all rounds) Scores w, drawn independently from D for each t, and the (pseudo-)rege) satisfies the inequality with C = 0.
198
199
200
201 Ad Adversarially Corrupted Stochastic Environments with Corruption Level C': This is case with a (A, 2C, T) self-bounding constraint (Zimmert & Seldin 2021). where C 2 0 is the total corrup- tion budget (adjusted for the factor of 2 from bounded regret differences). A is as in the stochastic case for some D. Scores w, satisfy Σ max; [w, - (i) I for w D independently per
202
203
204
t. When C = 0, it reduces to stochastic.
205
206
This covers all adversarial settings as a regime with a (A, 2T, T) self- bounding constraint (Zimmert & Seldin 2021) for any A [K] - [0, 1]. Scores w, are chosen arbitrarily by an adversary without assumptions. The constraint is vacuous with C = 2T (from bounded losses in [0, 1] and max deviation), including all adversarial cases.
Adversarial Environments:
207
208
209
210
These regimes span settings for regret analysis, from adversarial to stochastic.
211
212
ALGORITHM
213
214
215
In this section, we introduce the proposed wewoowtth-regulliiiee algorithm for dueling ban- dits in adversarial, stochastic, and corrupted environments, and present its pseudocode in [
4

---

Under review as a conference paper at ICLR 2026
216
In this approach, define probability distribution xe A[K] (the K-simplex), follows:
217
218
()...)) o0(o))
| {. (1 5:)de + 6,UK,
de E arg max PεA[K]
219
220
221
Where UK is an uniform distribution which satisfies UK (i) = 1/K. And for initialization, set d1 as the uniform distribution with each component equal K
222
223
224
Algorithm FTRL for Dueling Bandits
225
Require: Regularizers {Φr he parameters {5,) arm count K
226
1: for each round = 1, .,. To do
227
L.d.d
2: Draw 24, Vt
228
3: Observe f((211 y1) ~ Ber(M y1))
229
4: Set (i) + 1/2=
Eje(K] 1im / for all e [K]
230
Km((f)
m=(s)
231
5:
d. + arg maxpe
- 1 ( p) {c())
232
6:
Ti + (1 6,)d4 + 8,uk
233
7: end for
234
235
236
The algorithm computes a distribution over the K-simplex A(K {p [K] + [0.1]
237
ΣielK] p(i) = 1} in each round t, defined in 2
from the original formulation. Firstly, it pro-
238
ceeds to independently sample Iy and Y/ from Teg
The preference feedback fe y1) follows S Based observations, the unbiased estima- tor ūn [K] + IR updates as shown in Then it solves for d, by maximizing the sum of inner
239
Bernoulli distribution with parameter M, Ut
240
products with prior unbiased estimators minus regularizer 5 where (a, b) EiE(K) a(i)b(i). and
241
242
6: (KK) + a convex Legendre function. Next, ne mixes de, using ó, E [0,0.5] 6
243
244
REGRET-BOUND ANALYSIS
245
246
Using the regularizer defined we can gain the regret bound in We consider the regularizer functions defined as
247
248
(p(p) = Σ g(p(i)), where g(x) = x In x) In(1 x),,
249
(3)
250
*E[K]
251
where the parameters & and ar are defined by a max (m2, 8K} and
252
253
8. =
mi
0+++ = 0u+
1224/
6, = 8,+ V
K
(4)
254
4
+ E Uo
8% mi
f-1
mecot
1/2
s==1
255
256
with mi, m2 > 0 as input parameters such that my 2 2 log K (used for computing 8 and ag to
257
ensure lower bounds) and m2 (used initialize a1 max max(my, 8K} and update a1+1),
258
Additionally, {ec). {ea} are defined by
259
260
e, =
Σ (d)(), e, -00(1-0())) iE[K]
261
SE[K]
262
Remark 1. The step sizes are designed to enable the algorithm to adapt automatically to the under- lying environment. In the adversarial setting, to achieve the 22/3 regret bound, we set 8, 1-1 ae ~ 12/3, and 01+1
263
264
1-1/3, as these rales ensure that the regret terms in Lemma balance appropriately when v4 and e, remain constant. In the stochastic setting, where v; and e decrease from non-zero values to zero the distribution concentrates
265
266
the optimal arm, the step sizes are chosen such that the regret can be controlled through the 52/3 term. By applying the inequal- ity y-/3,22/3 < 3, + zy in the self-bounding analysis (cf. equation equation 20 derive the logarithmic regret bound of Ollog T A2 )
267
268
269
5

---

Under review as a conference paper at ICLR 2026
270
Theorem 1. For any T, 7 wwtt or, 8G. and ae defined by 3and| 4 enjoys regret bound of
271
272
Rr S k max g2/3 mm)
where
273
274
1 0 ++
K log
+ m2)
Vlog(KT))
log (T))
(5)
275
v mm
m2
276
Consequently, if KS, we have Rr = 0 (KTT2/3) in the adversarial regime and
277
278
1.3
C
1/3
279
RT= 0
RT
+
A
(6)
min
280
281
in adversarial regimes with self-bounding constraints.
282
This implies: O(K1/37223) for adversarial environments, O log Toog(KT) for stochastic envi- ronments, and O K log (TT
283
A
284
C log T /T/////3 for corrupted stochastic environments.
285
A7
A?
286
The core challenge in extending best-of- botthhh--oo---oe both-worlds (BoBW) or best-of-three- worlds (BoTW) analyses to dueling bandits under the Borda winner benchmark lies in the fun- damental mismatch between existing frameworks, such as the DB-MAB reduction in [Shaa Gail- lard (2022). and the inherent global nature of Borda scores. [Saha & Gaillard (2022) provides unified algorithm achieving optimal regrets across stochastic and adversarial environments under the Condorcet winner (CW) assumption, relying
Discussions.
287
288
289
290
291
regret definition that decomposes into dom- inance gaps (c.g., R[ = [ + R41,T]. In their setting where R_1, and R41, are the regrets achieved by the two multi-armed bandit algorithms corresponding the two duelists, where (i. = j) - 1/2) to enable clean mapping to independent MAB instances. How- ever, this fails for Borda winners because the regret definitions fundamentally differ: CW regret leverages pairwise independence via uniform dominance, whereas Borda regret aggregates average scores (i,())) } (x.) + oe (Be))), rendering the Theorem 2 in Saha & Gaillard 2022)whicch whiic assumes such decomposition for regret counds-iaapllcablle from the outset. This disparity arises from Borda's lack of uniform dominance, necessitating global preference matrix estimation that troduces coupled dependencies across all pairs. To circumvent this, we adopt an FTRL approach, directly optimizing over the simplex to embrace Borda's global averages.
292
293
294
295
296
297
298
299
300
301
302
Our FTRL algorithm uses a hybrid negative entropy regularizer (,(p) a, E, s(p(i)), where g(x) = x In + (1- - z) [1(1 x). to address problems when using the standard Shannon en- tropy (p)(p) = 04 p() In p()). In the stability bound [ Shannon entropy produces positive quadratic term in the Taylor expansion for small (E; (())s(i) + E ((i)s(i)²/a: O(s /a?)), which disrupts the recursive closure the self-bounding inequality in and fails to control the pro- cess quantity 1; = Σ, (1) (i)). This stalls the analysis, it cannot maintain the recursive structure needed for unified regret bounds. Our regularizer, however, yields a negative quadratic term / /or + O(s* /az)), which enables tight recursive control of Ut, ensuring the self- bounding inequality closes effectively across all regimes.
303
304
305
306
307
308
(i) - (i)ss)()))
309
310
311
Proof of the main theorem. The proof relies on series of lemmas and key proposition, which we present as they are used to establish the result.
312
313
314 We begin by introducing the proposition that bounds a specific regret term R
315
Proposition 1. We begin by introducing the proposition that bounds specific regret term Ry. which is an auxiliary regret term based on the shifted Borda score. Let us define parameters ór and of as in then R2 satisfying 10 is bounded
316
317
318
319
R4
O
E
m
2/3
+ k
m2 (log K + Fer) (m +V21 v213)
320
321
where Er Σt- Co Vj Dr Us and o (oog m2
+ m2
322
323
This proposition is supported by the following lemmas which provide the intermediate bounds.

---

Under review as a conference paper at ICLR 2026
324
Lemma 1. The Bregman divergence that use is Do, (p.q) - Vol(o),p= q). If I is chosen following Ti so that Pr[d, T.) = (i),,, the regret is bounded by
325
326
327
R4
Σ (ō. (0,, d de-1) Do. (d(+1 1. de) + or(de+)) 1
328
(8)
329
+ th (di);
330
331
where ex- (1) = -ifi=="* i' and ex- (1) f E [K] {it}.
332
Lemma 2. When the traditional Shannon entropy is used as the regularizer, de is defined
333
334
Φc(p) -p) where f(v)
Σ
p())
p(1)
335
kE|K]
336
It holds for any 8: [K] + R and p. P(K) that
337
338
(s.q - p) - Do. (g.p) S at Σ p(i)s
ss())
339
iE(K)
340
341
where ((x) = exp(-x) + + 1.
342
Lemma 3. If 0t given by 3 it holds for any s: [K] + R. and p. E P(K) that
343
(8,9- - p) Dø, (1.P) S an Σ min p(i)( (=s(i)
s(1)
344
(1 -((())(
(9)
04
345
=E[K]
346
where ((x) exp(-xx) + 1-
348
Lemma 4. Suppose de is defined as in
and 8,
K
Then, the regret satisfies Rr S Rg te100
349
where
350
K Seat
+ (a0+1 az) (eeee)))) )
351
PG = O E Σ
(10)
352
and the sequences {Ee} and {vz) are given by
353
354
e Σ g (i), EE[K]
U1 Σ d(()(1-
(11)
355
KE[K]
356
357
We use the above proposition along with the following lemma, which bounds the sums Er and Vi. Lemma 5, Consider the following definitions:
358
359
360
T ET
T
log
+ m2 +m²) ))
361
Ct2
V1
Ut
(12)
m2
362
363
with input parameters my m2 satisfying m. 2 2 K. Then, for any i E [K], the sums Er and Vr are bounded by
364
eKT S(ir)' Fr s 228(1") In
365
Vr Vr 2S(i),
(13)
366
367
where S(i*) is as given in 17
368
From Proposition (the bound in and Lemma (the bounds
13 S m³. we have
369
370
R9 0 E Smi) / S(i*) log (o(k)))((())))
371
372
<0 <0(mm- & (og((TT) 52/3)
(14)
373
374
where the inequality follows from Jensen's 's inequality. Hence, there exists ie such that, RG $ k. 52/3
375
376
377
(15)
where 1: = 0 mm + Mnn+Tolo(( (Vog(KT)

---

Under review as a conference paper at ICLR 2026
378
As consequence, we obtain 5 Since S S T, in adversarial regimes, it follows from that
379
R = O (i max { (T mi)) =0 - T2/8.
380
(16)
381
382
Let us next show 6 This relies on the following lemma, which provides a lower bound on the regret using self-bounding parameters.
383
384
Lemma 6. We introduce the following parameters S(i*) and S, which will be used when applying the self-bounding technique:
385
386
387
S(:) (1-d()),
= - $ min S(i"); PE(
(17)
388
389
390
We note that these values are clearly bounded O S S S(i S T for any it E [K]. In an adversarial regime with a self-bounding construint, the regret can be bounded from below:
391
392
Amin 5 C. C.
393
R4
(18)
2
394
395
From and Lemma 6 for any A E (0, 1], have
15
396
R4 = (1 (1+ one o ((1 0)k 52/3 0A 0C)
397
(19)
398
We have
399
400
(1 (1+ + 0)333
1/3
(1 (1+0) 0)k 52/3 0Amin =
5)
0 minS
401
0 02 min
402
(1 + 2)2k3
0 (( [1
1 0
403
(20)
A2 min
A
404
405
where the second equality follows from x /3/32223 < j + f for any 2, y 2 Combining these inequalities, we obtain
406
407
R4 10=0(( 02
13
+ 0C
(21)
408
2 min
409
By choosing 9 that minimizes the right-hand side, we obtain
410
411
Setting mi + loKlog T -log( (13) and m2 = loK we obtain
412
413
I k= (K log log log(KT))2//3)
(22)
414
415
Then we get that an algorithm achieves R4 0(K1/3T2/3) for adversarial environments,
416
R2 = 0 log T log(KT) for stochastic environments, and R = 0
K log T log(KT)
+
417
log (c2Klog (TT)(())))) )1/3)) for adversarially
418
stochastic environments. Finally, since R
AP
419
K-T R4. this does not change the order of magnitude we have obtained. Therefore, we can subse-
K
420
quently arrive at the result in T
421
422
423
EXPERIMENTS
424
425
To represent an environment, we use a preference matrix, where the first row corresponds to the arm with the highest total value, the second corresponds to the second-best arm, and on (Figure [ (a)). For the adversarial setting, we construct a reversed preference matrix (Figure (b)), where the first corresponds the worst arm and the last row the best.
426
427
428
429
The environment alternates between the original and reversed matrices: the algorithm learns on the original matrix for 100 rounds, then the reversed one for 150 rounds. The extra 50 rounds help offset any residual influence from learning in the original environment. And due to the rearrange- ment inequality, this setting of the environment can cause the most severe regret when changing the
430
431
8

---

Under review as a conference paper at ICLR 2026
432
environment. In the corrupted setting, modify the preference matrix by swapping the first and second rows (Figure (c)) every 500 rounds.
433
434
435
436
437
438
439
440
441
442
443
444
(a) Preference Matrix
(b) Reversed Preference Matrix
(c) Corrupted Preference Matrix
445
Figure 1: Experimental Setting of Three Preference Matrices.
446
447
448
449
For comparison, evaluate established algorithms for dueling bandits with Borda winner: Norda-Confideece--Baa (BCB) for stochastic environments, and Dueling-EXP3 (D-EXP3) for ad- versarial environments (Saha al. 2021). each experiment, the reported results are averaged over five independent runs. As shown in Figure 2 our algorithm achieves better performance than D-EXP3 in the stochastic setting, outperforms BCB in the adversarial setting, and surpasses both
450
451
452
453
algorithms in the corrupted setting.
454
455
456
457
458
459
460
461
462
463
Stochastic Environment
Adversarial Enviroument
(c) Corrupted Environment
464
Figure 2: Experimental Results in Three Environments.
465
466
467
468
7 CONCLUSION AND FUTURE SCOPES
469
470
We address the dueling bandits problem under the Borda winner benchmark, where the goal is to minimize regret from relative preferences across stochastic, corrupted stochastic, and adversarial environments without prior knowledge of the setting. We overcome the challenge of extending existing frameworks, such as the DB-MAB reduction tailored for Condorcet winners, which fails due Borda's 's global averaging nature requiring full preference matrix estimation. Our key tributions include: (1) the first unified bfst-of-three-worldd (BoTW) framework for Borda winners, achieving nearly optimal regrets of ( in adversarial, O(K log A in stochastic, and O(K T/A2 + (C log" T/ 1//3) in corrupted settings; (2) an FTRL algorithm with a hybrid negative entropy regularizer and time-varying rates for adaptive self-bounding: (3) empirical validation demonstrating superior robustness over baselines.
471
472
473
474
475
476
477
478
479
480
Our BoTW framework for Borda winners opens potential extensions to contextual dueling bandits, where preferences depend on side information (Dudík et al., 2015). By adapting our FTRL with hybrid regularization, we could explore unified BoTW regret bounds for stochastic, corrupted, and adversarial settings. addition, our framework can be extended to human feedback reinforcement leamning (RLHF), where dueling bandits model preference-batee alignment (Christiano et al. (017)) potentially achieving robust BoTW guarantees under noisy or adversarial feedback by using our adaptive regularization approach.
481
482
483
484
485

---

Under review as a conference paper at ICLR 2026
486
REFERENCES
487
488
Arpit Agarwal, Shivani Agarwal, and Prathamesh Patil. Stochastic dueling bandits with adver- sarial corruption. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato (eds.), Proceedings of Algorithmic Learning Theory, volume 132 of Proceed- ings of Machine Learning Research, pp. 217-248. PMLR, 16-19 Mar 2021. URL https: //proceedings.oo ml www.mmm..prrss..mmmmmmmmmm
489
the 32nd International Conference
490
491
strpoeedss v132 agarwa 21a html
492
493
Peter Auer and Chao- Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochas- tic and adversarial bandits. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), 29th Annual Conference Learning Theory, volume 49 of Proceedings of Machine Learning Re- search, pp. 116-120, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https: htttps://pooceedinng/ mlr. http://sw........////////s//
494
495
496
497
6. html
498
499
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi- and Eyke Hüllermeier. Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research, 22:1-108, 2021.
500
501
502
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adver- sarial bandits. In Shie Mannor, Nathan Srebro, and Robert C. Williamson (eds.), Proceed- ings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Ma- chine Learning Research, pp. 42.1 42.1-44. 12.22,,, Edinburgh, Scotland, 25-27 Jun 2012. PMLR. URL ml r press vv23/ htt/////ew//eeeeeee// html
503
504
505
506
507
508
Paul F. Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg. and Dario Amodei. Deep reinforcement learning from human preferences. In Proceedings of the 31st International Con- ference on Neural Information Processing Systems (NeurIPS), pp. 4302 4310, 2017.
509
510
511
Qiwei Di, Jiafan He, and Quanquan Gu. Nearly optimal algorithms for contextual dueling bandits from adversarial feedback. In secood International Conference on Machine Learning, 2025.
512
513
URL
514
515
Miroslav Dudik, John Langford, and Lihong Li. Doubly robust policy evaluation and learning. In Proceedings of the 28th International Conference on Machine Learning, ICML'11, pp. 1097-
516
517
1104, June 2011.
518
Miroslav Dudík, Katja Hofmann, Robert E. Schapire, Aleksandrs Slivkins, and Masrour Zoghi. Contextual dueling bandits. In Proceedings of The 28th Conference on Learning Theory, vol- ume 40 of Proceedings of Machine Leurning Reseurch, pp. 563-587, Paris, France, 03-06 Jul 2015. PMLR. htt.hhttt////oooeeee
519
520
521
ml
.ntml.
522
523
Pratik Gajane. Adversarial multi-dueling bandits. In ICMI. 2024 Workshop on Models of Hu- man Feedback for Alignment, 2024. URL 5dhgCowdri
524
net/ forum?id
525
526
527
Björn Haddenhorst, Viktor Bengs, Jasmin Brandt, and Eyke Hüllermeier. Testification of condorcet winners in dueling bandits. In Cassio de Campos and Marloes H. Maathuis (eds.), Proceed- ings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 1205. PMLR, 27-30 Jul 2021. URL html
528
529
530
https: http:://ppcceedingg. mw..rrr...... http://ppp...eeeeaaaaaaaaaeaaaaa
531
532
Shinji Ito and Kei Takemura. An exploration- linear bandits. In seirth-e Conference on Neural Information Processing Systems, 2023a.
approach to best of both worlds in
533
534
http://pppnneeeieeeeeeeeeeee URL //
535
536
Shinji Ito and Kei Takemura. Best-of linear bandit algorithm with variance-adaptiver re- gret bounds. In Gergely Neu and Lorenzo Rosasco (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings Machine Learning Research, pp. 2653-26777
537
538
PMLR. 12-15 Jul 2023b. URL httpp:: sttpa://pproceedingg mmlr. http://ww.....m.es//s//e///e///s wwwss/v195/ito225
539
html
10

---

Under review as a conference paper at ICLR 2026
540
Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-both-worldd al- gorithms for online learning with feedback graphs. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Infor- mation Processing Systems, volume 35, pp. 28631-28643. Curran Associates, Inc.,
541
542
543
544
2022. URL https::/proceed http://proceeddd.........rre neurips cC fitapprrrilesepppeereeeee Paper Conference pdf
545
546
Kwang-Sunn Jun, Lihong Li, Yuzhe Ma, and Xiaojin Zhu. Adversarial attacks on stochastic ban- dits. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, 2018.
547
548
549
pp.
550
Johannes Kirschner, Tor Lattimore, and Andreas Krause. Information directed sampling for linear partial monitoring. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp-
551
552
553
PMLR, 09-12 Jul 2020. URL. /tt.:hhts:://tttt http:se//proccedle mogs.mlz. wwwps//ssssss.
554
kirschner20a.
555
556
Fang Kong, Canzhe Zhao, and Shuai Li. fest-of-three-worlde analysis for linear bandits with follow- the-regularized--ladde algorithm. In Proceedings Thirty Sixth Conference on Learning Theory, volume 195, pp. 657-673. PMLR, 2023.
557
558
559
Yuko Kuroki, Alberto Rumi, Taira Tsuchiya, Fabio Vitale, and Nicolò Cesa-Bianchi Best-of- both-worlds algorithms for linear contextual bandits. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), Proceedings of The 27th International Conference on Artificial Intel- ligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 1216 1224. PMLR, 02-04 May 2024. URL cestps:/pproeeeee www.eeriinnm..m.......mmmm..mmmm mlr. press/v238/
560
561
562
563
564
kuroki24a. html
565
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
566
567
Chung-War Wei Lee, Haipeng Luo, Chen- Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near instance-optimality and minimaax-ppimalle in stochastic and adversarial linear bandits simulta- neously. In Marina Mcila and Tong Zhang (eds.), Proceedings of the 38th International Con- ference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 6142 6151. PMLR, 18-24 Jul 2021. URL https: http:////ccceeeegg....... mlr. ptw.i..rees///139
568
569
570
571
lee21h.
572
573
Aadirupa Saha and Pierre Gaillard. Versatile ducling bandits: Best-of-both world analyses for learn- ing from relative preferences. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepes- vari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Ma- chine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 19011-19022 PMLR, 17-23 Jul 2022. URL https:: https:://proceedingg mll. wtt.:..peeess/1//22aaaaoe
574
575
576
577
html
578
579
Aadirupa Saha, Tomer Koren, and Yishay Mansour. Adversarial dueling bandits. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 9235-9244. PMLR, 18-24 Jul htte::://proeeddnggggm......prpe
580
581
582
2021.
html
583
Joe Suk and Arpit Agarwal. Non-stationary dueling bandits under a weighted borda criterion. Transactions on Machine Learning Research, 2024a. ISSN 2835-8856. URL https::/ openreview net/ forum? wiw.ummdddkkkRDD222 7022 Featured Certification.
584
585
586
587 Joe Suk and Arpit Agarwal. Non-stationary dueling bandits under weighted borda criterion. Transactions on Machine Learning Research, 2024b. ISSN 2835-8856. URL https:://
588
openreview. net. wwwpeee///r///eee wtt.rrummmidkknnnzZZ.000 Featured Certification.
589
590 Taira Tsuchiya, Shinji Ito, and Junya Honda. Best-of-bott-worldds algorithms for partial monitoring. In Shipra Agrawal and Francesco Orabona (eds.), Proceedings of The 34th International Con- ference Algorithmic Learning Theory, volume 201 of Proceedings of Machine Learning Re- search, pp. 1484-1534 PMLR, 20 Feb-23 Feb 2023. URL hctps: http::////cceeeee....// mmr. press/ v201 wtw.hss.ccc.t.tcc..t ya2.a. html
591
592
593

---

Under review as a conference paper at ICLR 2026
594
Yue Wu, Tao Jin, Qiwei Di, Hao Lou, Farzad Farnoud, and Quanquan Gu. Borda regret mini- mization for generalized linear dueling bandits. In Ruslan Salakhutdinov, Zico Kolter, Kather- ine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Pro- ceedings of the 41st International Conference on Machine Learning, volume 235 of Proceed- ings of Machine Learning Research, pp. 53571-53550 PMLR, 21-27 Jul 2024. URL https: //proceedings.nt mix
595
596
597
598
599
mlr. wwwps/eess.. ww25//u244mm html
600
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In ICML '09: Proceedings of the 26th Annual International Conference
601
602
on Machine Learning, pp. 1201-1208, 2009. doi: 10.1145/153374415553333 URL https:
603
//doi. wet...111111131111 1553527
604
605
Yisong Yue, Josef Broder, Robert Kleinberg, and Thorsten Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78: 18:155515 2012. doi: 10.1016/j.jcss. 2011.12.028. URL
606
607
http:/.....1111111 jass 2011. 12. 028
608
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-44 49,, 2021. URL hhtp:: jmlr.
609
610
arc/papers/v22/15 953.1/997733.mmm l
611
612
Masrour Zoghi, Shimon Whiteson, Remi Munos, and Maarten De Rijke. Relative upper con- fidence bound for the k-armed dueling bandit problem. In Proceedings of the 31st Interna- tional Conference on Machine Learning (ICML), volume 32, pp. 10-18. PMLR, 2014. URL m.e..ress/ /v2/evv32//2 1232/ogghii42 pddf
613
614
615
htttps://proceet/
616
Masrour Zoghi, Zohar Karnin, Shimon Whiteson, and Maarten de Rijke. Copeland dueling ban- dits. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 307-315, 2015.
617
618
619
620
621
622
A SUPPLEMENTARY PROOF OF LEMMAS AND PROPOSITION IN THE MAIN
623
TEXT
624
625
A.1
LEMMA
626
627
If I, is chosen following ग. so that Pr[Z, = - nel = (i), the regret is bounded by
628
629
RT S
Σ (ō. - (ūc, de d-1) Do, (de+1, de) + de de(eet1) Oe (de+1))
630
(23)
631
+ - t2 (11)),
632
633
where e,. (i) -00=110 i = 1 and e 0 for i [K] (
634
635
Proof. From the definition of the algorithm, we have
636
637
T
638
RT((") We
(Ti)
E
Wt, Te cx-)
639
640
T
We, dl - ex.) + Σ
8r ( ( uk - di)
641
=
642
t=1
643
T
644
< E
We, dl - - + >d
6
645
1=1
646
T Σ
E
ú4 de ex) +
8
647
1=1
12

---

This establishes the Under review as a conference paper at ICLR 2026
648
where the second equality follows from I Te. the inequality follows from (-w,, uk -d+) S (-W,, uk) I 1, and the last equality follows from the fact that úy is an unbiased estimator for wi- Further, from Exercise 28.12 of the book by Lattimore & Szepesvári (022)), have
649
650
651
652
T Σ (ū,, d2 ex)) S
Σ 1=1
(- (ūe, de d(+1) Der (d)+1, + (x(d++1) (c+1(d++1)
653
654
655
+ 0T+1(e)+) -11(d))
656
Combining this, we obtain the regret bound g
657
658
659
A.2
LEMMA 2
660
661
Proof. Consider the partial derivative of the left-hand side expression with respect to each (
662
①
663
(q) ((5, p) Dos (p.()) = s(i a. (In ((1) - In p(t)).
664
665
Since the expression is concave in q, the maximum over q R occurs where this derivative
666
667
vanishes, namely q" (i) p(i) exp
s()) Therefore, de
668
669
(8, - p) - Do, (p.P) S (8, - p) - Do, (4",p)
670
Σ [s(i)(q (1) - p(1)) - az (4 (n) (1)-(()))m))
671
672
{E|K]
673
- (i) p()) +1)]
674
E (-s(i)p(i) + s(i)q" (i) ang (i) (i) (i) + lxp(i)
675
(E(K]
676
tai(a" (1) ((n +1)
677
678
Σ (-s(i)p(t) (2 (8) -p()))
679
KE(K]
680
s(i)
s(i)
Σ p(i)
681
az
exp
0
an
682
(E(K]
683
s(i)
a Σ p(i)
684
02
685
KE[K]
686
The initial equality stems from the Bregman divergence formula. The subsequent simplification uses
687
In n" (i) In p(i) + e(d) a, and the later step substitutes q" (i) p(i) exp ac
((s)
688
689
result for Lemma 2.
690
691
A.3
LEMMA
692
Proof.
Let us introduce non-negative function d(y, x) for x, E (0, 1), given by
694
695
d(y, = y In y - -r-y- y In ynn----- - x x (y x: (In 2 + 1).
696
x
697
This d represents the Bregman divergence the interval (0, 1) corresponding to the potential
698 6 (x) xln.. When o, follows 3 its associated Bregman divergence Dø. (g. p) can be writ-
699
ten as
700
701
Do. (g.r) at sE[K]
(d(a(i),p()) + d(1 q(t), p()))]
13

---

Under review as a conference paper at ICLR 2026
702
Consequently, derive
703
(8. - p) Do. (). [s())(((i) -())) - -a (d(g())). -d(-)))))))((()00)))))) -0), 1-))))
704
705
KE[K]
706
min (s())(((1) p(t)) a.d(g(t).p())
707
ke[K]
708
(p((() - (()) - - 1 p()))
709
Drawing from the reasoning in the proof of lemma2 follows that
710
711
( a.d(a(0), So.p(i) (=s(i)
s(i
712
0t
713
Analogously, we can establish
714
(()( - p(i)) - a,d(1 - q()), p(i))
715
716
=(()(((1 - -(()) - (())) at (1 - (n() (n(11((()) - - (1-p(i)) p(i))
717
-((1 - q())) - -(1 (1- (1-p( - +1]
718
719
s(i)
720
S Sas(1 -(())s
721
By integrating these, we arrive at the inequality stated in
9 This concludes the demonstration of
722
Lemma 3.
723
724
A.4
LEMMA 4
725
726
Proof. To establish this result, we start by applying Lemma 3 analyze the term (-úz, dl -d+1)
727 D&, (d++1, de). For every E [T'] and i E [K]. we notice that (i) < K/0?. This inequality arises from the expression for (i( in combined with the lower bound Te(i) 2 6 for all i [K].
728
729
Since &, 2 (K/a))2/3, it follows that ag 2 K6,-" implying (i I azd;
730
Using the inequality ((x)= S x2/22 for [a|| s 1, and noting that |s(i)]/a+ 5, for s = úr we derive
731
732
733
(-ù,, det1) Dor (d441, d,) a₁ Σ min di(()s
-ui(i)
(1 d((1)ss
(e(()
734
at
a2
iE[K]
735
Kv,
736
5,04
737
738
where the last step uses the definition of 0s in
and the bound
((e(()) ai
S (x((i)
a
26
739
Next, we bound (e(++))) - (d+1)))+1). Since dc(p) = Eie[K] g(p(i)) and g(x) < 0 for
740
741
1), have
742
(d++1) - (x+1(d++1) = (a: a1+1)
Σ g(d++1(0) = -(a++1 - -a)) Σ g(de+1
743
kE[K]
KE|K]
744
= (at+1 - ox) Et+11
745
746
where the last equality follows from 6++1 Eseja o(de+1(1)).
747
Combining this with the bound from
8 in Lemma Tand the inequality above, we obtain
748
Ke -aa411-aa) -as)e4t) ]
749
R E
8
+ or+z(ee) (1(11).
750
8,at
751
752
Note that ΦT+1 (err) aT+1 Eie(K] g(e:-((() (i)) 0, since 9(1) 0 and g(0) 0. Additionally,
753
(di) = aa Eie(K] g(di Q1e1. Therefore.
754
Ry S R + e101,
755
where R2. defined as in T0 This completes the proof.
14

---

Under review as a conference paper at ICLR 2026
756
A.5
LEMMA 5
757
758
Proof. Since de(i) 2 6./K 2 1/(2K) for all E [K] and & E [T]. we have 1s = Σie[K] de(i)(1
759
de(1) 11-1(1d06)) -iff de(i)² 1 1 de (i)) (K 1) (
de(i") ik' Therefore,
760
761
1 1-d( S u +
4K S 201
1
762
763
which implies S(i*) - 2V.. Next, we bound ET using the concavity of g. From Jensen's 's inequality and the definition of Et = LiE(K] g()) we have
764
765
ek + (K 1) In(K - 1) - K Kn 2 In(eK),
766
et 2 Kg
K = In
1
767
768
where the second inequality follows from In(K K 1) 2 In K - 1. For the upper bound, note that g(x) = in x + (1 .²) In(1 2) < = + (1 z) In(1 x) + xx1 (1 - x) and thus -gx) 1
769
-I r (1 - In(1 z). Therefore,
770
771
c ~ Σ (id (1 - (() (((1(()))
772
kE[K]
773
= (and()))(1-((1)))) (n( dc("))
774
775
Σ
- (1-))dd)))(-d()))))))
776
777
Σ In 1
s (dd(())d((()) - ( ((((())))((((((((())))))
778
de(2)
779
de())) (K - in 1- dii())
780
Ind((i))) (1 de (((
781
K-1
782
< 2(1 - de())) In e(K- - 1)T
783
1 (i*)
784
where the third inequality uses the concavity of In and Jensen's inequality, and the last inequality follows from -x x In < x for x E [0.1] and di()") s 1 - 1/T. Summing over t and using the bound above, obtain the bounds in 13
785
786
787
788
A.6
LEMMA 6
789
790
Proof. From the definition of the regret and the self-bounding constraint, we have
791
RT > E Σ AU,) - c > Amin E
T
792
(1-d(())) - C- Amin S(it) - C,
793
1==1
1=1
794
where the second inequality follows from A 2
Amin
1fi i²}) and the fact that (i)
795
(1 (t) + 8, K (1 (d) 2 (1) due to the assumption of 6, S 1/2 and the definitions
796
of S(i)) and S in 17
797
798
A.7 PROPOSITION
799
800
Proof. Observe that vt & 1 and v, S e, < log K. Introduce the auxiliary variables 4
8
801
and L. = Ei=1.. 4. By the definition of 8/, it follows that
802
803
4 e++14
Ct+1 (ms + v.!/)) ce+1 2 vc+1,
804
&
mi
805
since 82 S e₁ implies the second inequality. Additionally,
806
1/3
1-1
807
Ct+1 4 mn
(m)
v2/08)= < 4 (m /1/ < 4m +4 U1
Σ
1
808
809
< 8 (m1 L(-1);
15

---

Under review as a conference paper at ICLR 2026
810
where the initial inequality uses ct+1 2 log K combined with ma 2 2 2og K, and the final step relies on m1 2 and 01 I 1. Consequently,
811
812
813
T
4
La TT-1
814
au+1 est1 m2
mh + -
4m2
m1 + 1u-1 + vmn + Tu-1 1=1
815
t=1
816
L, -
4m
817
vm1 + Li + vm + L
818
819
820
=
4m
m1 + Li - mm + L S 4mz v Lt,
821
822
with the equality arising from the definitions of a and 4, and the inequality stemming from the bound above.
823
824
Next, define ni = 62 and N₂ = Ex_1 ng.. From the expression for 8,
825
826
4 (1 1
1 Vel
827
n4 8,
2 4.
me
828
Moreover,
829
831
830
n1 8, n++1 4
(1+ mi
v1/3
S 4 2a(1+
1
(Vz 1)218)
< 2n
mi
832
n s 4 (1+11/3
833
834
The parameter ot admits the lower bound
835
836
837
0g = 122 + m2
n2
2
m2
1+
Th
838
m1
+ L--1
Vml + Ts
8=1
839
m2
m2zt
N--1)
840
Vm + Tte
Vmn TTa
841
utilizing the definition in the last step. Therefore,
842
844
843
Vt
U2 Mat
mi +L
T4
Vm + LT
T
14
845
m2
1+ N+N11
m22
1 + N
1=1
(=1
1=1
[=1
846
Vmi +
LT
logT) T)
847
log
m2
848
849
where the concluding inequality derives from
850
1 No In
(1 n4
1 n4
851
(1 + N₂) (1 + N₂-1) In 1 N₂
5
1
1 N
852
853
valid since In(1 +x) 2 for for o: E [0, 8). and the bounds ensure
for every
854
I+N.11
855
Furthermore,
856
T
T
857
mi + Le
m1 +
LT m2
=0
[/m +
LT
log T
858
02
m21
m2
859
860
Additionally,
861
T
862
122
3m1
2/3
-V2/3)
3mm1 2/3
<
863
V
1/
2
2
[=1
t=]
16

---

Under review as a conference paper at ICLR 2026
864
leveraging the relation 2 - x2//3 2 5 x)y-1/3
1/3 for y 2 x > O. Integrating these yields
865
866
T
Kit
867
56 +
+ +a0++1 - ar) ctt1
d,at
868
869
K
Ket + (al+1 -a) c++1
870
Σ 1=1
6
+
at
871
K Klog T
872
0
mi 2/2
+ mz
v /m1= LT
873
m2
874
875
my 2/2/3_
K logg T
T c++1 my + + m2)
mi + V v!/ia)
=0
+
876
12
m2
877
878
V2/3
(oggT
m + (log K + ET) mm + Vi v3//0)
m:
+ m2
V
879
mmi
12
880
881
where the third line applies the bound, and the final step uses er+1 S 2log K.
882
883
884
B CONNECTIONS TO PARTIAL MONITORING FRAMEWORKS
885
886
In this section, we discuss the relationship between dueling bandits with Borda winner and par- tial monitoring games, highlighting how our approach connects to and differs from existing PM methodologies.
887
888
889
890
B.1 CONCEPTUAL RELATIONSHIP BETWEEN DUELING BANDITS WITH BORDA WINNER AND PARTIAL MONITORING GAMES
891
892
While previous studies have explored connections between dueling bandits and partial monitoring (Kirschner al. 2020 Suk & Agarwal 2024a), none provide a complete treatment of the Borda winner setting. Kirschner el al. (2020) analyze the Condorcet winner case, while (Suk & Agarwal (2024a) address a generalized Borda formulation but not specifically the standard Borda dueling bandits problem. Their Remark 3 suggests that such generalized Borda problems may be reduced to partial monitoring with non- non-global observability, leading to a worst-case regret bound of ((T)), which is not informative for our setting. Neither analysis applies directly to the DB problem with Borda winner.
893
894
895
896
897
898
899
900
We address this gap by proposing reduction that maps the Borda dueling bandits problem to finite PM game and by characterizing the resulting PM structure. Our reduction scheme is constructed as follows. The action set consists of all arm pairs a {i.j} (i < j) with k = (K) total actions.
901
902
903
The outcome set contains all possible tournament preference matrices æ E (0. (5) with d = 2 outcomes. The feedback Pa. reveals the winner of duel [i,j] through (+1, -1} signals. We define the Borda score as (i) K-1 Ees 1[ > 4 and identify the optimal Borda arm 8 (z) arg max; by (i). The loss function implements standard Borda regret: La, = (i*(z)) 1 (b, (i)+
904
905
906
907
b. (j).
908
909
Because the Borda score aggregates comparisons against all other arms, we prove that the re- sulting PM game is globally observable with parameter kn = K - 1, the weight function w. for any two neighboring Pareto optimal actions a = {i" (f",p} and = (i*,4) as w. we(c,)) = 2 (u,l))(c,)) - n.(4) (c, a)). where (e, = K-i if e = ( for some and a indicates i wins, and otherwise. This construction satisfies the global observability condition in Definition
910
911
912
913
914
1 of (Tsuchiya et al. 2023), since Σ (c, ee..)) = La,z Lo.z for all x E [d], as required by
915
equation (1) in their paper. And cg = m1 ||]]]|]>>] < (K) )- 1/(2(K 1)) ~ K/4.
916
Applying the global-observabiiity guarantees of Tsuchiya et al. (023) to our reduced game yields regret bounds of OKK1/372/3 log T) for the adversarial setting and O(K2 log" T/ 2 min) for the
917
17

---

Under review as a conference paper at ICLR 2026
918
stochastic setting. Both bounds incur additional multiplicative factor of K compared with tailored results for DB with a Borda winner. Thus, while partial monitoring offers a useful con- ceptual perspective, applying its general guarantees to the Borda ducling bandits problem results in strictly suboptimal results.
919
920
921
922
923
B.2
ALGORITHMIC AND ANALYTICAL DISTINCTIONS
924
925
Our approach also differs fundamentally from general partial monitoring methodologies. Although both employ FTRlestyyle algorithms, the choice of regularizer and the resulting analysis are substan- tially different. globally observable PM games, the feedback matrix + provides strong stability guarantees: loss differences be estimated with low variance, quantified by the game-dependent constant cg. This structure allows Tsuchiya et al. (2023) to use the standard Shannon entropy reg- ularizer control the key intermediate term (1/, 4t q++1) Di(g++1, 9t) demonstrated in the proof of their Lemma 11.
926
927
928
929
930
931
932 In contrast, the Borda dueling bandits problem does not possess such global stability properties. The Borda score depends on comparisons with all other arms, and there no analogue the PM constant cg that would enable the same Shammon-entropy-baseed argument. As result, the analytical steps used in general PM frameworks cannot be directly replicated our setting. To overcome this problem, we employ the hybrid entropy regularizer to derive the intermediate upper bound shown in Lemma [3 This lemma is essential for both our adversarial and stochastic analyses and represents key technical innovation beyond standard PM approaches.
933
934
935
936
937
938
939
LLM USAGE C
940
941
In the draft of this paper, we utilized Grok Specifically. Grok was employed for language polishing to improve the clarity. grammar, and flow of the text; generating and formatting tables based on provided data and deseriptions; and suggesting adjustments to the paper's layout and struc- ture for better readability and organization. These uses were limited to editorial and presentational enhancements and did involve generating original research ideas, technical content, proofs, or experimental designs. The authors take full responsibility for all content in the paper, ensuring its originality and scientific integrity.
943
944
945
946
947
948
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
18


Reviews:
[{"review_id": "fZEd97p5zF", "reviewer": "Reviewer_bvPj", "summary": "This paper studies the \"best-of-three-worlds\" problem in dueling bandits, where the goal is to attain regret bounds in adversarial, stochastic and corrupted problem simultaneously. In particular, they show such guarantees in terms of the Borda regret, which is the cumulative difference in Borda score between the played arms and hte Borda-optimal pair of arms. The proposed algorithm for this task estimates the pairwise probabilities using so-called importance weighted estimators, and then runs a regularized-follow-the-leader (RFTL) algorithm using these estimators. The output of RFTL is then mixed with a uniform distribution to get the policy for a given round.", "questions": "- Should the $R_T$ in (1) be $R_T^b$? The environment definitions that follow use $w(i)$, which makes it seem that it is in reference to the shifted regret $R_T^b$.\n- In line 203, it appears that the expectation is over the $w$, but the expectation is written as $E_{s \\sim D}$. I found this to be confusing, and would suggest that the authors modify for clarity.\n- Equation (2) uses $u_K$, but it hasn't been defined yet.\n- In line 242, it says that $x_t$ and $y_t$ are sampled from $d_t$, but the Algorithm 1 shows them being sampled from $\\pi_t$.\n- I would suggest adding an intuitive explanation for the algorithm step sizes in (5).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- To my knowledge, the best-of-three-worlds with Borda score is a new contribution.\n- The regret bounds for the adversarial and stochastic settings match the optimal regret in those settings up to log factors. (Per the lower bounds in Saha et al., 2021).\n- The paper gave a clear explanation of how the analysis of best-of-three worlds with Cordocet regret does not transfer to Borda regret, and therefore they require a new algorithm/analysis approach.", "weaknesses": "- Although the best-of-three worlds guarantees are new for this setting, the actual individual guarantees do not necessarily improve on those that have been attained previously. In particular, the guarantees on the corrupted setting are $1/\\Delta^2$, while prior work (Agarwal et al, 2021) showed $1/\\Delta$ dependence. This renders the claim on line 99 incorrect, that the guarantees match the state-of-the-art for the corresponding setting.\n- I found the presentation to somewhat confusing at places, which I have detailed in the Questions box.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JMqZn9uBGF", "reviewer": "Reviewer_57Uf", "summary": "This paper considers a relaxed comparator for setting up the regret where a uniformly winning arm is not achievable.", "questions": "See the previous section", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The relaxed regret benchmark makes sense and the regret bounds derived therein is meaningful.\n- The best-of-both-worlds results are of relevance when the underlying environment is uncertain.", "weaknesses": "- While it makes sense to assume the environment is static and is either stochastic, corrupted, or adversarial, I wonder if it makes more sense to assume that the environment may switch among these three regimes as the number of rounds increases. This is for example considered in Cortes, C., DeSalvo, G., Gentile, C., Mohri, M., & Yang, S. (2018, July). Online learning with abstention. In International conference on machine learning (pp. 1059-1067). PMLR.\n- One of the motivation to consider dueling bandits is RLHF. I wonder how would the borda winner setting be better elaborated in such settings? And how are computational efficiency be guaranteed beyond being a convex optimization problem, that is, is there any scalable method to use for solving FTRL problems in huge scale?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o0IZ67fSis", "reviewer": "Reviewer_zTzf", "summary": "This work establishes the first best-of-three-worlds algorithm for dueling bandits under the Borda winner objective, developing a single FTRL-based algorithm which achieves order-optimal regret in both stochastic and adversarial settings, as well as in settings with a corruption budget. Previously, such a result was shown for dueling bandits with Condorcet winner and regret notion, but the regret scales differently in such a setting and so the Borda result requires new innovations, namely a hybrid negative entropy regularizer.", "questions": "Please see my main question above in \"Weaknesses\".", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper shows the first best-of-three-worlds regret bound for Borda dueling bandits.\n* The writing is generally clear and presentation is easy to follow.\n* There are also experiments to validate theoretical results, i.e. superiority of their FTRL algorithm over other approaches for the various settings.", "weaknesses": "I think there could be more discussion of related works to better highlight the technical novelty of this work. In particular, there are other works [1]-[3] on getting best-of-both or best-of-three-worlds results in settings where the regret scales like $T^{2/3}$ that should be definitely be mentioned. My understanding is that the hybrid regularizer used in this work is required to adapt the self-bounding analysis for this type of regret scaling rather than the $\\sqrt{T}$ rate seen in Condorcet dueling bandits. My main concern is whether this Borda dueling bandit problem can in fact be instantiated as a partial monitoring problem and inherit the results of [2]. For instance, it is known that Condorcet dueling bandits can be viewed as a partial monitoring problem in some instances (see mentions of dueling bandits in \"Information Directed Sampling for Linear Partial Monitoring\" Kirschner et al., 2020) and also in some generalized versions of the Borda problem (see Remark 3 in the cited paper Suk and Agarwal., 2024), or whether the adaptations required in the FTRL self-bounding analysis are already implicit in the works [1]-[3].\n\n[1] Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs, Ito et al., NeurIPS 2022.\n\n[2] Best-of-Both-Worlds Algorithms for Partial Monitoring. Tsuchiya et al., ALT 2023.\n\n[3] Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback. Kong et al., ICML 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)