Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback
Authors: Qiwei Di
Jiafan He
Quanquan Gu
Venue: ICML 2025 poster (2025)
Keywords: Dueling Bandits
Adversarial feedback
optimal
uncertainty-weighted maximum likelihood estimation.
Primary area: theory->online_learning_and_bandits
TL;DR: We study a specific model within this problem domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary.

Abstract: Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM). However, the effectiveness of this approach can be influenced by adversaries, who may intentionally provide misleading preferences to manipulate the output in an undesirable or harmful direction.
To tackle this challenge, we study a specific model within this problem domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary. We propose an algorithm namely robust contextual dueling bandits ($\texttt{RCDB}$), which is based on uncertainty-weighted maximum likelihood estimation.  Our algorithm achieves an $\tilde O(d\sqrt{T}/\kappa+dC/\kappa)$ regret bound, where $T$ is the number of rounds, $d$ is the dimension of the context, $\kappa$ is the lower bound of the derivative of the link function, and $  0 \le C \le T$ is the total number of adversarial feedback. 
We also prove a lower bound to show that our regret bound is nearly optimal, both in scenarios with and without ($C=0$) adversarial feedback. Our work is the first to achieve nearly minimax optimal regret for dueling bandits in the presence of adversarial preference feedback. 
Additionally, for the sigmoid link function, we develop a novel algorithm that takes into account the effect of local derivatives into maximum likelihood estimation (MLE) analysis through a refined method for estimating the link function's derivative. This method helps us to eliminate the $\kappa$ dependence in the leading term with respect to $T$, which reduces the exponential dependence on the parameter radius $B$ to a polynomial dependence. We conduct experiments to evaluate our proposed algorithm $\texttt{RCDB}$ against various types of adversarial feedback. Experimental results demonstrate its superiority over the state-of-the-art dueling bandit algorithms in the presence of adversarial feedback.

Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback
Qiwei Di Jiafan He?
Quanquan Gu
Abstract
ial feedback. Experimental results demonstrate its superiority over the state-of-the-art dueling bandit algorithms in the presence of adversarial feedback.
Learning from human feedback plays an impor- tant role in aligning generative models, such as large language models (LLM). However, the ef- fectiveness of this approach can be influenced by adversaries, who may intentionally provide mis- leading preferences manipulate the output in undesirable or harmful direction. To tackle this challenge, we study specific model within this problem domain domain-contextun contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary. We propose algorithm namely robust contextual dueling bandits (RCDB), which is based uncertainty- weighted maximum likelihood estimation. Our algorithm achieves an Ö(dVT/n /n + dC/k) re- gret bound, where T is the number of rounds, d is the dimension of the context, k is the lower bound of the derivative of the link function, and 0 < C < T is the total number of adversarial feedback. We also prove lower bound to show that our regret bound is nearly optimal, both in scenarios with and without (C 0) adversarial feedback. Our work is the first to achieve nearly minimax optimal regret for ducling bandits in the presence adversarial preference feedback. Additionally, for the sigmoid link function, we develop novel algorithm that takes into account the effect of local derivatives into maximum likeli- hood estimation (MLE) analysis through refined method for estimating the link function's deriva- tive. This method helps us to eliminate the i
1 Introduction
Acquiring appropriate reward proves challenging in nu- merous real-world applications, often necessitating intricate instrumentation (Zhu et al., 2020) and time-consuming cal- ibration (Yu et al., 2020) to achieve satisfactory levels of sample efficiency. For instance, in training large language models (LLM) using reinforcement learning from human feedback (RLHF), the diverse values and perspectives of humans can lead to uncalibrated and noisy rewards (Ouyang et al., 2022). In contrast, preference-based data, which involves comparing or ranking various actions, is a more straightforward method for capturing human judgments and decisions. In this context, the dueling bandit model (Yue et al., 2012) provides problem framework that focuses optimal decision maisiinn-maing through pairwise comparisons, rather than relying on the absolute reward for each action. However, human feedback may not always be reliable. In real-world applications, human feedback is particularly vul- nerable to manipulation through preference label flip. Ad- versarial feedback can significantly increase the risk of mis- leading large language model (LLM) into erroneously prioritizing harmful content, under the false belief that reflects human preference. Despite the significant influence of adversarial feedback, there is limited existing research the impact of adversarial feedback specifically within the context of dueling bandits. A notable exception is Agar- wal et al. (2021), which studies dueling bandits when an adversary can flip some of the preference labels received by the learner. They proposed an algorithm that is agnostic to the amount of adversarial feedback introduced by adversary. However, their setting has the following two limitations. First, their study was confined finite-armed setting, which renders their results less applicable to modern applications such RLHF. Second, their adversarial feed- back is defined on the whole comparison matrix. In each round, the adversary observes the outcomes all pairwise comparisons and then decides to corrupt some of the pairs before the agent selects the actions. This assumption does
dependence in the leading term with respect to which reduces the exponential dependence on the parameter radius B to a polynomial dependence. We conduct experiments to evaluate our proposed algorithm RCDB against various types of adversar-
'Department of Computer Science. University of California, Los Angeles, CA 90095, USA. Correspondence Quanquan Gu <qgu@cs..uca.cdux
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
not align well with the real-world scenario, where the adver- sary often flips the preference label based the information of the selected actions.
We conduct experiments to validate the effectiveness of our algorithm RCDB (See Appendix E). To further assess RCDB's robustness against adversarial feedback, we eval- uate its performance under various types of adversarial feedback and compare the results with state-of-the-ae dueling bandit algorithms. Experimental results demon- strate the superiority of our algorithm in the presence of adversarial feedback, which corroborate our theoretical analysis.
In this paper, to address the above challenge, we aim to develop contextual dueling bandit algorithms that robust to adversarial feedback. This enables us to effectively tackle problems involving a large number of actions while also taking advantage of contextual information. We specifically consider a scenario where the adversary knows the selected action pair and the true preference of their comparison. In this setting, the adversary's 's only decision is whether to flip the preference label or not. We highlight our contributions as follows:
Notation. In this paper, we use plain letters such as z to denote scalars, lowercase bold letters such as x to denote vectors and uppercase bold letters such as X to denote matri- ces. For a vector x, ||x||2 denotes its f--nomm The weighted f--norm associated with a positive-definite matrix A is de- fined as ||x||A vx Ax. For two symmetric matrices A and B, we use A > B to denote A B is positive semidefinite. We use Il to denote the indicator function and O to denote the zero vector. For two actions a, b, we use a > to denote a is more preferable to b. For a postive integer N, we use [N] to denote {1, 2, ....,........... NJ. We use stan- dard asymptotic notations including O(-). (()), O()), and Ō(), θ(.) will hide logarithmic factors.
We propose a new algorithm called robust contextual dueling bandits (RCDB), which integrates uncertainty- dependent weights into the Maximum Likelihood Estima- tor (MLE). Intuitively, our choice of weight is designed to induce a higher degree of skepticism about potentially "untrustworthy"" feedback. The agent is encouraged to focus more on feedback that is more likely to be genuine, effectively diminishing the impact of any adversarial feed- back.
2 Related Work
We analyze the regret of our algorithm under at most C' number of adversarial feedback. For known adversarial level, our result consists of two terms: a C-independent term ((dVT/Kk) and a C-dependent term OdC//k) where & is the lower bound of the derivative of the link function. Additionally, we establish a lower bound for dueling bandits with adversarial feedback, which demon- strates that our algorithm achieves optimal regret both in settings with and without adversarial feedback.
Bandits with Adversarial Reward. The multi-armed ban- dit problem, involving an agent making sequential decisions among multiple arms, has been studied with both stochas- tic rewards (Lai et al., 1985; Lai, 1987: Auer. 2002; Auer et al., 2002a; Kalyanakrishnan et al., 2012; Lattimore Szepesvári, 2020; Agrawal & Goyal, 2012), and adversarial rewards (Auer et al., 2002b; Bubeck al., 2012). More- over, a line of works focuses on designing algorithms that can achieve near-optimal regret bounds for both stochastic bandits and adversarial bandits simultaneously (Bubeck & Slivkins, 2012: Seldin & Slivkins, 2014; Auer & Chiang, 2016; Seldin & Lugosi, 2017: Zimmert & Seldin, 2019; Lee et al., 2021). which known as "the best of both worlds" guarantee. Distinet from fully stochastic and fully adversar- ial models, Lykouris et al. (2018) studied setting, where only a portion of the rewards is subject to corruption. They proposed an algorithm with a regret dependent on the corrup- tion level C, defined as the cumulative sum of the corruption magnitudes in each round. Their result is C times worse than the regret without corruption. Gupta et al. (2019) im- proved the result by providing a regret guarantee comprising term that matches the
When the adversarial level is unknown, we conduct our algorithm with an optimistic estimator of the number of adversarial feedback and prove the optimality of our result in case of a strong adversary. To the best of our knowledge, our work is the first to achieve nearly minimax optimal regret for dueling bandits in the presence of adversarial preference feedback, regardless of whether the amount of adversarial feedback is known.
For the sigmoid link function, we develop a novel al- gorithm called Robust Contextual Ducling Bandit for Sigmoid link function (RCDB-S). Rather than using the uniform lower bound k, we introduce local derivatives in maximum likelihood estimation (MLE) analysis through a refined estimation method of the link function's 's derivative. Our theoretical analysis establishes that RCDB-S achieves a regret bound of (dB1. /T+ k)., where we elim- inate the k dependence in the leading term with respect to T. This represents a significant improvement over prior works, reducing the exponential dependence on the parameter radius B to a polynomial dependence.
two terms, a cerruption-independee regret lower bound without corruption, and corruption- dependent term that is linear in C. In addition, Gupta et al. (2019) proved a lower bound demonstrating the optimality of the linear dependency on C.
Contextual Bandits with Corruption. Li et al. (2019) stud- ied stochastic linear bandits with corruption and presented an instance- -eeendeed regret bound linearly dependent on the corruption level C. Bogunovic et al. (2021) studied the
2

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
Table I. Comparison of algorithms for rohust bandits and ducling bandits.
Model
Algorithm
Setting
Regret
Multi-layer Active Arm Elimination Race
K-armed Bandits
Ö(K)SVVT)
(Lykouris et al., 2018)
BARBAR
K-armed Bandits
O(VKT+KO)
(Gupta et al., 2019)
Bandits
SBE et et al., 2019)
Linear Bandits
Ö(PC/A+ A2)
Robust Phased Elimination
Linear Bandits
Ö(vaT + d d
(Bogunovic et al., 2021)
Robust weighted OFUL
Linear Contextual Bandits
Ö(dCVT)
(Zhao et al., 2021)
CW-OFUL
Linear Contextual Bandits
o(dVT+dC)
(He el al., 2022)
WIWR
K-armed Dueling Bandits
o + Eipr K2/23)
(Agarwal et al., 2021)
Versatile-DB
Dueling Bandits
K-armed Dueling Bandits
o(C+ 1/4, + +K)
(Saha & Gaillard, 2022)
RCDB
Contextual Dueling Bandits
Ö(dVT dC))
(Our work)
same problem and proposed an algorithm with near-optimal regret in the non-corrupted case. Lee et al. (2021) studied this problem in a different setting, where the adversarial corruptions are generated through the inner product of corrupted vector and the context vector. For linear con- textual bandits, Bogunovic et al. (2021) proved that under an additional context diversity assumption, the regret of a simple greedy algorithm is nearly optimal with an additive corruption term. Zhao et al. (2021) and Ding et al. (2022) extended the OFUL algorithm (Abbasi- Yadkori et al., 201 I)
et al., 2015; Falahatgar et al., 2017; Heckel et al., 2018; Saha et al., 2021; Wu et al., 2023) and von Neumann winner (Ramamohan et al., 2016; Dudík et al., 2015; Balsubramani et al., 2016), along with their corresponding performance metrics. To handle potentially large action space or context information, Saha (2021) studied a structured contextual dueling bandit setting. In this setting, each arm possesses an unknown intrinsic reward. The comparison is determined based on a logistic function of the relative rewards. In a similar setting, Bengs et al. (2022) studied contextual linear stochastic transitivity model with contextualized utilities. Di et al. (2023) proposed layered algorithm with variance aware regret bound. Another line of works does not make the reward assumption. Instead, they assume the preference feedback can be represented by a function class. Saha & Krishnamurthy (2022) designed an algorithm that achieves the optimal regret for K- K-armed contextual dueling bandit problem. Sekhari et al. (2023) studied contextual dueling bandits in a more general setting and proposed an algorithm the provides guarantees for both regret and the number of queries. Another related area of research is the logistic ban- dits, where the agent selects one arm in each round and receives a Bernoulli reward. Faury et al. (2020) studied the dependency with respect to the degree of non-linearity of the logistic function K. They proposed an algorithm with no dependency in Abeille et al. (2021) further improved the dependency on and proved a problem dependent lower bound. Faury et al. (2022) proposed computationally effi- cient algorithm with regret performance still matching the lower-bound proved in Abeille et al. (2021).
and proved a regret with a corruption term polynomially dependent on the total number of rounds T. He et al. (2022) proposed an algorithm for known corruption level C' to re- move the polynomial dependency on T in the corruption term, which only has a linear dependency on C. They also proved a lower bound showing the optimality of linear de- pendency on C' for linear contextual bandits with a known corruption level. Additionally, He et al. (2022) extended the proposed algorithm to unknown corruption level and pro- vided near-optimal performance guarantee that matches the lower bound. For more extensions, Kuroki et al. (2023) studied best-of-both-worldds algorithms for linear contex- tual bandits. Ye et al. (2023) proposed a corruption robust algorithm for nonlinear contextual bandits.
Dueling Bandits and Logistic Bandits. The ducling bandit model was first proposed in Yue et al. (2012). Compared with bandits, the agent will select two arms and receive the preference feedback between the two arms from the environment. For general preference, there may not exist the "best" arm that always wins in the pairwise comparison. Therefore, various alternative winners are considered, in- cluding Condorcet winner (Zoghi et al., 2014; Komiyama et al., 2015), Copeland winner (Zoghi et al., 2015; Wu & Liu, 2016; Komiyama et al., 2016), Borda winner (Jamieson
Dueling Bandits with Adversarial Feedback. A line of work has focused on dueling bandits with adversarial feed- back or corruption. Gajane et al. (2015) studied a fully ad adversarial -aie version of ducling bandits, which
3

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
was proposed in Ailon al. (2014). Saha et al. (2021) considered the Borda regret for adversarial dueling bandits without the assumption of utility. In a setting parallel to that in Lykouris et al. (2018); Gupta et al. (2019), Agarwal et al. (2021) studied K-armed dueling bandits in a scenario where an adversary has the capability to corrupt part of the feedback received by the learner. They designed an algo- rithm whose regret comprises two terms: one that is optimal in uncorrupted scenarios, and another that is linearly de- pendent on the total times of adversarial feedback C. Later on, Saha & Gaillard (2022) achieved "best-of-bott world" result for noncontextual dueling bandits and improved the adversarial term of Agarwal et al. (2021) in the same setting. For contextual dueling bandits, Wu et al. (2023) proposed an EXP3-type algorithm for the adversarial linear setting using Borda regret. For comparison of the most related works for robust bandits and ducling bandits, please refer to Table 1. In this paper, we study the influence of adversarial feedback within contextual dueling bandits, particularly in a setting where only a minority of the feedback is adversarial. Compared to previous studies, most studies have focused on the multi-aru dueling bandit framework without inte- grating context information. The notable exception is Wu et al. (2023); however, this study does not provide guaran- tees regarding the dependency on the number of adversarial feedback instances.
et al., 2023). We also make an assumption on the deriva- tive of the link function, which is common in the study of generalized linear models for bandits (Filippi et al., 2010), Assumption 3.2. The link function o is differentiable. Fur- thermore, its first-order derivative satisfies that there exists a constant K 0 such that
à (( a) ((x, b), 0)) 2 Ki
for all x E a, E E,
In our setting, however, the agent does not directly observe the true binary feedback. Instead, an adversary will see both the choice of the agent and the true feedback. Based on the information, the adversary can decide whether to corrupt the binary feedback or not. Such adversary is referred to as strong adversary (He et al., 2022), compared with the weak adversary who cannot obtain the information before the decision. We represent the adversary's 's decision in round by an adversarial indicator cr which takes values from the set {0, 13. If the adversary chooses not to corrupt the result, we have Ct = O. Otherwise, we have c = 1, which means adversaria feedback in this round. As result, the agent will observe a flipped preference label, i.e., the observation o = 1 - 4. We define C' as the total level of adversarial feedback, i.e.,
Σx ΣI
3 Preliminaries
Remark 3.3. There are two commonly used corruption models for bandits. One is the total budget model (Lykouris et al., 2018), where in each round f, the agent selects an action ar and the environment generates a numerical reward re(a)). The adversary observes the reward and returns a corrupted reward r,- The corruption level C is defined by Eh Ire(a)) - Fel C. Another considers the number of corrupted rounds (Zhang et al., 2021). In our setting, we consider the label-flipping attack. Thus, the magnitude of adversarial feedback is always and these two types of corruption models are equivalent. Moreover, adversar- ial feedback in our setting involves comparing two arms, whereas in bandits pertains the reward of a single arm. The only previous work that studied label aabp-inip is (Agar- wal et al., 2021), where the adversary cannot observe the action selected by the agent. In contrast, our setting fo- cuses on scenarios where this information is available to adversaries, which is common in many real-life applications. We use the term "adversarial feedback" to differentiate our work from prior studies on corrupted or adversarial reward settings.
In this work, we study linear contextual dueling bandits with adversarial feedback. In each round t E [T]. the agent observes the context information It from context set X and the corresponding action set A. Utilizing this context information, the agent selects two actions, ag and by. Sub- sequently, the environment will generate a binary feedback (i.e.. preference label) 4 = I(a bi) E {0, 1} indicating the preferable action. We assume the existence of reward function r" (zz, a) dependent on the context information x and action a, and monotonically increasing link function a satisfying or (xx) ) + (-x)) = 1. The preference probability will be determined by the link function and the difference between the rewards of the selected arms, i.e.,
P(a > b1x)
- (x,
(3.1)
We assume that the reward function linear with respect to some known feature map á0z, a). To be more specific, we make the following assumption:
Assumption 3.1. Let Φb X x A TRd be known feature map, with ([ a)lla Z 1 for any (x,a) X x A. We define the reward function re parameterized by 0 E θ, with ro(x, a) (0, Φfx, a)). Moreover, there exists 0" satisfying rg. = r" For all with 0 E 0|12 < B.
As the context is changing, the optimal action is different in each round, denoted by aj argmax r* (Iz, a). The goal of our algorithm is to minimize the cumulative gap between the rewards of both selected actions and the optimal action
Similar linear assumptions have been made in the literature of dueling bandits (Saha, 2021; Bengs et al., 2022; Xiong
Regret(T") DT 2r Ext,, a7) - r" (Iz, ac) r" -ax,, be).
4

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
This regret definition is the same as that in Saha (2021) and the average regret defined in Bengs al. (2022). It is typically stronger than weak regret defined in Bengs et al. (2022), which only considers the reward gap of the better action.
Let A, - + E d' 0" (') we have
0, R 0. + AA, o
(o(o) -(0
4 Algorithm
In this section, we present our new algorithm RCDB, de- signed for learning contextual linear dueling bandits. The main algorithm is illustrated in Algorithm 1. At high level, we incorporate uncertainty-dependeett weighting into the Maximum Likelihood Estimator (MLE) to counter ad- versarial feedback. Specifically, in each round E [T]. we construct the estimator of parameter 0 by solving the following equation:
Therefore, applying the pulling-out-known-fareee property of the conditional expectation, the Fi-measurable part will cancel out when calculating the conditional variance. Then, we can approximate the variance of the estimated preference probability by
[ar F.
EE (Bloro' (0) (T) " )
~
0 + E (o( -,) =
(4.1)
s 100'( 0 10
where the last inequality holds due to Elo, [F] S Us- ing I (') 0*) S 1, A, Σx+1 > Σ,, where E, is defined in Line 1 of Algorithm 1, we can see that Var [ 0.) S 1 Since higher variance leads to larger uncertainty, which harms the credibility of the data, it natural to assign a smaller weight to the data with high uncertainty. Thus, we choose the weight to cancel out the uncertainty follows
where we denote Φ; = Hl a;) ((2, ba) for simplicity, we is the uncertainty weight we are go- ing to choose. To obtain an intuitive understanding of our weight, we consider any action-observation se-
quence (I1, a1, , bj, 01, P2, 02 b2, 02,...,,T, az, by, 0z) up to round I. For simplicity, we denote F. a a1, b1, 22, 02, b2. ........ 2t, ae b.) as the filtra- tion. Suppose the estimated parameter 0, is the solution to the unweighted version equation of (4.1), i.e.,
w a1, [[),)
(4.3)
10 + Ei (o(0)) 0.) - -o:) = O.
(4.2)
where a/||>b/|>,;- normalizes the variance of the estimated probability. To prevent excessively large weights, we apply truncation to this value. A similar weight has been used in He et al. (2022) for linear contextual bandits under cor- ruption. Different from their setting where the weight is an estimate of the variance of the linear model, our weight is estimate of generalized linear model. Furthermore, by selecting a proper threshold parameter, e.g., = vd/C, the weighted MLE shares the same confidence radius with that of the no-adversary scenario.
When we receive Φ = (xx, a²) - (1x, be). the probabil- ity of receiving 4 = 1 can be estimated by ( O.). We consider the conditional variance of the estimated probabil- ity a 0,) in round f, i.e., Var ( 0,) Fi]. involving posterior estimate of the prediction's 's variance. Intuitively, even without the weighting, we can show that the solution of (4.2), i.c., O,, will approach 0", using the arguments similar to Lemma 5.1, what we will present next. This inspires us to consider the approximation of Taylor's expansion:
Remark 4.1. Here, we use approximations to illustrate the motivation of our uncertainty- based weight. Rigorous proof for the algorithm's ''s performance is presented in Section A. which relies solely our specific choice of weights and does not use the approximation.
[[o(AT0))) R [ 0+) d' d' (0) Fi]
F. mensurable
+ = )T 0.IFF]
After constructing the estimator O, from the weighted MLE, the sum of the estimated reward for each duel (a. b) can be calculated as (œ((,,, a) + ((x,,)) b)) O,. To encourage the exploration of duel (a, b) with high uncertainty during the learning process, we introduce an exploration bonus with the following (](()<;, a) Φ(z,, b) |ل|| which follows a similar spirit to the bonus term in the context of linear bandit problems (Abbasi-Yadkori the reward term and the bonus term exhibit different combi- nations of the feature maps Φfx+, a) and (FF,, b), which
Moreover, using the Taylor's 's expansion to (4.2), we have
0- 10, + (0 0.) 0b
+I Eo 00 0 O:
Yadkori et al., 2011). However,
(o 0*) 0:) Σ d' d 00) 0').0000
5

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
Algorithm 1 Robust Contextual Dueling Bandit (RCDB)
The proof of this lemma is postponed to Section B.
1: Require: a > O, regularization parameter A, derivative
Remark 5.2. If set (Vd + VXB)/C, then the confidence radius / has no direct dependency on the number of adversarial feedback C. This observation plays a key role in proving the adversarial term in the regret without polynomial dependence on the total number of rounds T.
lower bound K, confidence radius B.
2: for [. ,...,, do
3: Compute Σ,
AI Di
((I,,, (Ø(x; a.) (Z 6.))
4: Calculate the MLE 0 by solving the following equa-
With Lemma 5.1, we can present the following regret guaran- tee of our algorithm RCDB in the dueling bandit framework. Theorem 5.3. Under Assumption 3.1 and 3.2, let <
tion:
A0 + Σ wi ((0(1z; az) b;);,)))))
o.]
1. the total number of adversarial feedback be C. If we set the confidence radius to be
(d(2;, ax) ( bi)) = O.
(4.4)
5: Observe the context vector Zt-
3 = = + aC + (1ogg((1+////////))
6: Choose ac bt = argmax,,6 { +
A = 1/B², a== vd/(CV/R) then with probability at least 6, the regret of Algorithm in the first T rounds can be upper bounded by
((z,,b)) b)) 0: + 33 ( a) - o( b) 1-1 }
7: The adversary sees the feedback 4 = (a; > bt)
and decides the indicator e.. Observe or = le when
Regret( (T) = (
C: = 0, otherwise observe Or -t.
8: Set weight wa as (4.3).
The proof of Theorem 5.3 is postponed to Section A. The following theorem provides lower bound for the dueling bandit problem and demonstrates that regret guarantee is optimal for general link functions.
9: end for
the key difference between bandits and dueling bandits. The selection of action pairs (a, b) is subsequently determined by maximizing the estimated reward with the exploration bonus term, i.e.,
Theorem 5.4. For any algorithm Alg and any d, d, 2 max maxx((4d)) (4d2)/25, dC), > O, there exists an instance of dueling bandit with link function o, satisfying
(0(1), b)) 0. Bl|o(1r) a) - o(0, ((,,,)))
à ((0(x, a) ()z, 0)) 2 n. Vr E N. A
As the arm-selection rules involving the selection of two arms has already been studied and is not the central contri- bution of our algorithm, we refer the readers to Appendix C of Di et al. (2023) for a detailed discussion.
such that the regret of Alg over T rounds is 2((dvT + dK)/k).
For the proof of Theorem 5.4, please refer to Appendix A.2. Theorem 5.4 indicates that the regret guarantee ((dvT + (K) in Theorem 5.3 for ducling bandits with adversarial feedback is optimal not only in d, T and C' but also in k. Notably, the constructed link function has a uniform first- order derivative, with value k even around O. As discussed in the next section, for the sigmoid function a (xx) = 1/(1 + e ")", whose first-order derivative is constant around 0, the dependency K can be further improved.
Computational Complexity. We assume there is a compu- tation oracle to solve the optimization problems of the action selection over A. A similar oracle is implicitly assumed in almost all existing works for solving standard linear bandit problems with infinite arms (e.g., (Abbasi- Yadkori et al., 2011 I; He et al., 2022)). In the special case where the deci- sion set is finite, we can iterate across all actions, resulting in Okk2d() complexity for each iteration, where & is the number of actions, and d is the feature dimension.
5.2 Unknown Number of Adversarial Feedback In our previous analysis, the selection of parameters de- pends on having prior knowledge of the total number of adversarial feedback C. In this subsection, we extend our previous result to address the challenge posed by an un- known number of adversarial feedback C. Our approach to tackle this uncertainty follows He et al. (2022), we introduce adversarial tolerance threshold C for the adversary count. This threshold can be regarded as an optimistic estimator of the actual number of adversarial feedback C'. Under this situation, the subsequent theorem provides an upper bound for regret of Algorithm in the case of an unknown number of adversarial feedback C.
5
Main Results
5.1
Known Number of Adversarial Feedback
At the center of our algorithm design is the uncertainty- weighted MLE. When faced with adversarial feedback, the estimation error of the weighted MLE 0 can be character- ized by the following lemma.
Lemma 5.1. If we set 3 (dlog(1 + 2T/A)/0)/R, then with probability at least 1 - 5, for any E [7), we have
VAB + aC
00. - 0¹ Σ, S.
6

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
Theorem 5.5. Under Assumptions 3.1 and 3.2, if we set the the confidence radius as
1/k, which translates to exponential dependence on B. This exponential dependence B is frequently observed in the literature of dueling bandits and RLHF (Zhu et al., 2023; Xiong et al., 2023; Li et al., 2024).
β = vBB + aC + Vdlog((1 2
with the pre-defined adversarial tolerance threshold C and = 1/B2, a = vd/ (FVF), then with probability at least
To improve the dependency on Ki present new algo- rithm that exploits the structure of the sigmoid link function. In Section 6.1, we outline the key ideas behind our algo- rithm design. Subsequently, in Section 6.2, we provide a theoretical analysis to establish the regret guarantee of our algorithm.
1 5, the regret of Algorithm can be upper bounded as following:
If the actual number of ad adversarial feedback C' is smaller than the adversarial tolerance threshold C, then we have
6.1 Key Ideas of the Algorithm
Regret(T) T) = ÖdVVT/R dC/rs).
In this section, we present the key innovation of our al- gorithm that improves upon Algorithm 1. Let Φ (( a;) - ( b;) for notational simplicity. Following the standard (weighted) MLE analysis (Li et al., 2017), we introduce an auxiliary function:
If the actual number of adversarial feedback C is larger than the adversarial tolerance threshold C, then we have (T") = O(T).
Remark 5.6. The COBE framework (Wei et al., 2022) con- verts any algorithm with the known adversarial level to an algorithm in the unknown case. However, such a frame- work only works for weak adversaries and does not work in our strong adversary setting. In fact, He et al. (2022) proved that any algorithm cannot simultaneously achieve near-optimal regret when uncorrupted and maintain sublin- ear regret with corruption level C = 2( ((VT). Therefore, there exists a trade-off' between robust adversarial defense and near-optimal algorithmic performance, which very common in dealing with strong adversaries (He al., 2022: Ye et al., 2023). Our algorithm achieves the same nearly optimal O(dvT) regret as the no-adversary case even when C' = O ((TT), which indicates that our results are optimal in the presence of an unknown number of adversarial feedback.
Σ wi
()) = 10 +
Using the mean- value theorem, G. G, can be represented as:
G,(O,) - G)()")
= +I Σ
w.o (0) 0) )
(0: 10: 07), (6.1)
i=1
where 0 m0, (1 m)0" for some m E [0.1]. In Algorithm 1, we use the unified lower bound x to replace the local derivative T 0). Thus, we define Σ; = ^II + E' W.K.p.p. and the following inequality holds: ||0, 0' S (G,) (.")))l
Relaxing the local derivative ó O) to the unified lower bound к works well for smooth link functions where the derivative has little variation (e.g.. the instance in Theo- rem 5.4). However, this approach becomes less effective for the sigmoid link function, whose derivative (xx) = e / + e =)²² exhibits exponential decay with respect to x. In this case, the local derivative can significantly differ from k, particularly when both actions a, and b, near- optimal. In such situations, 6 0 se 0 and consequently d Φ 0) ~ 1/4, a constant value. To address this limitation, our new algorithm introduces refined method to estimate the local derivative ( 0) and directly uses it as weight in the matrix.
Improved Results for Sigmoid Link Function
While Algorithm 1 can handle all link functions and achieves optimal worst-case regret guarantees, it can be improved for some specific link functions. In this section, we demonstrate this improvement for the sigmoid link func- tions.
We begin by calculating the coefficient k for the sig- moid link function and analyzing the corresponding re- gret guarantee in Theorem 5.3. For the sigmoid function (x) = 1/(1+==*) its derivative given by (zx) = e-a (== Under Assumption 3.1, we have
Following Abeille et al. (2021), we begin by expressing o( 0) in integral form:
(0( - ((x,b). b) < 2B, Vz X. A.
In the worst case, we have
[. à (0. (0, + - -0.)))-)))0)))) 0:)))au (o))
à 0 0)
min "((( (b1,,,))00)) 2 + e 2B 2,0
e-2 eeB
By applying Lemma F.5, we have:
à a 0n)
o(0T00)
which implies k < 1/(2+ e 2B + e 2 Therefore, the previous regret bound exhibits polynomial dependence on
0Φ 0 2
1 +
( (0. (0-0
1+4B
7

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
Based this inequality, we can estimate the local derivative by constructing lower bound of a ( 0*). To this end, we construct a confidence set for 0":
Algorithm 2 Robust Contextual Dueling Bandit for Sigmoid link function (RCDB-S)
Require: a O, regularization parameter X, derivative
lower bound K, confidence radius Br, 3e.
i (0: 0
0
S Br, VtJ.
Set ÅS
3: for 1. = 1,..., T,,,Ta do
Supposing & holds, then for any i, the following inequality holds:
4: Compute Eg
A Einwe (= (( b.)) (16 a.) - (( 44)
0 1 - $ 10,
0zl + Bell _ - A.
5: // Construct a new weighted covariance matrix
6: Compute A. = Al w wi (0(I,, 0:)
By defining = max (x. 8 (.:)]. we have 6(5 (0) 2 fi and consequently 0 0) 2 (1 4B). Based on this result, we use u; as a optimistic estimator of local derivative [ 0) to define a refined covariance matrix A, = AI + Ess w.u. (Line 6). For action selection, we apply the pairwise selection rule from Section 4 using A,:
D( b;)) (Ø(2;, ai) 0 b.))
7: Calculate the MLE Oe by solving the following equa-
tion:
0O + ++ Wi (o (() -(0a))))((((,
((x,,b))) 0) 0)--0 -0) -,
(,) - o (z bi)) = O.
(6.2)
Oz, b = argmax ( a) + ((x); b)) O.
8: Observe the context vector Zt-
a,b
9: Use Ag to do exploration
+ +B.1lo(zx a) - Φ( b) }
argmax { ( +
10:
Choose a2 by
In Algorithm 2, we highlight the differences from Algorithm I with red color for clarity.
(fF,, b)) 0. + Be a) b0,,,)))
11: The adversary sees the feedback 4 = (a: be)
6.2 Theoretical Results
and decides the indicator ce. Observe Or = la when
C. O. otherwise observe o, = 1 - 4.
In this section, we provide the upper bound of regret for our algorithm with the sigmoid link function.
12:
Set weight we as (4.3).
13:
// Calculate the weight et
Theorem 6.1. For the sigmoid link function (x) 1/(1+ +1+ e) under Assumption 3.1, let 0 < 5 < 1 and the total number of adversarial feedback be C. If we set the confi- dence radius to be
14:
A, = [[ ax) bc) 0. (1
( be) "xs''
15: Set 2 max(k, (K, a(i)))
16: end for
B. VBB + VR
V dloog(2(1 + 21/2)/5) + aC,
actions are far from optimal, the local derivative may ap- proach k, resulting in a k-dependent constant factor; And in the corruption term, since the strong adversary, who can observe the actions selected by the agent, can strategically flip labels anytime, particularly when the local derivative is close to K. This leads to polynomial dependency on in the corruption term.
3. = (1 + 4B) VXB+ +
dlog dd 2t
+ +ac|
Vx
dAd
and x = a/ a (Vd+ (VD+VAB)/C then with probability at least 1 - 8, the regret of Algorithm 2 in the first rounds can be upper bounded by
Regret(T) = 5(BBL5 + dBC/k
7 Conclusion
+ BBB2(1/12 + B/K)).
In this paper, we focus on the contextual dueling bandit problem from adversarial feedback. We introduce a novel algorithm, RCDB, which utilizes an mncertainty-weightee Maximum Likelihood Estimator (MLE) approach. This algorithm not only achieves optimal theoretical results in scenarios with and without adversarial feedback but also demonstrates superior performance with synthetic data. For the sigmoid link function, we develop novel algorithm called Robust Contextual Ducling Bandit for Sigmoid link function (RCDB-S). Through a refined estimation method of the link function's 's derivative, RCDB-S achieves a regret bound of O(dB1. /T + dBC/k), where we eliminate the
Remark 6.2. Compared to the result in Theorem 5.3, our new regret bound has a leading term of O(dB1.5/T) with respect to T, which eliminates the polynomial dependency on 1/x by utilizing the local derivative rather than the uni- form lower bound This implies reduction from exponential dependence to a polynomial dependence on B. To the best of our knowledge, this is the first work to achieve such a reduction in regret for contextual dueling bandits. However, there are two scenarios where k depen- dency remains: during the warm-up period when selected
8

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
dependence in the leading term with respect to T.
Agrawal, S. and Goyal, N. Analysis of thompson sampling for the multi-armed bandit problem. In Conference on learning theory, pp. 39-1. JMLR Workshop and Confer- ence Proceedings, 2012.
Limitations and Future Works. We assume that the re- ward is linear with respect to some known feature maps. Although this setting is common in the literature, we ob- serve that some recent works dueling bandits can deal with nonlinear rewards (Li et al., 2024; Verma et al., 2024). Recently, Verma et al. (2024) studied the problem of approx- imating reward models using neural networks, addressing nonlinear rewards for dueling bandits. It is an interesting future direction to design robust algorithms for nonlinear reward functions, such as with neural networks. Another promising direction is to design more computationally efficient algorithm that avoids computing the MLE in each round (Jun et al., 2017; Zhang & Sugiyama, 2024; Sawarni et al., 2024).
Ailon, N., Karnin, Z., and Joachims, T. Reducing dueling bandits to cardinal bandits. In International Conference on Machine Learning, pp. 856-864. PMLR, 2014.
Auer,
Using confidence bounds for exploitation- exploration trade-offs. Journal of Machine Learning Research, 3(Nov):397-423 2002.
Auer, P. and Chiang, C.-K. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Conference on Learning Theory, pp. 116-120. PMIR, 2016.
Impact Statement
This paper studies contextual dueling bandits with adver- sarial feedback. Our primary objective is to propel ad- vancements in bandit theory by introducing more ro- bust algorithm backed by solid theoretical guarantees. The severtaintt-weighhee approach we have developed for duel- ing bandits holds significant potential to address the issue of adversarial feedback in preference-basee data, which could be instrumental in enhancing the robustness of generative models against adversarial attacks. Moreover, our study on dueling bandits with a logistic link function suggests that the leading term of the regret can remain unaffected by the derivative lower bound k. This novel result provides valuable insights and may positively impact the study of machine learning theory and its applications.
Auer, P., Desa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235 2002a.
Auer, P., Cesa-Bianche N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77, 2002b.
Balsubramani, A., Karnin, Z., Schapire, R. E., and Zoghi, M. Instance-dependent regret bounds for dueling bandits. In Conference on Learning Theory, pp. 336-333633333 360. PMLR, 2016.
Bengs, V., Saha, A., and Hüllermeier, E. Stochastic con- textual dueling bandits under linear stochastic transitivity models. In International Conference on Machine Learn- ing, pp. 1764-1786. PMLR, 2022.
leknowledgements
We thank the anonymous reviewers for their helpful com- ments. JH is supported by the UCLA Dissertation Year Fellowship. QD and QG are supported in part by the Na- tional Science Foundation CPS-2312099) The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
Bogunovic, I., Losalka, A., Krause, A., and Scarlett, J. Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pp. 991-999 PMLR, 2021.
Bubeck, S. and Slivkins, A. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pp. 42-1. JMLR Workshop and Confer- ence Proceedings, 2012.
References
Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Bubeck, S.,
N., et al. Regret analysis of stochastic and nonstochastic multi-armed bandit prob- lems. Foundations and Trends@ in Machine Learning, 5 (1):1-122, 2012.
Abeille, M., Faury, L., and Calauzènes, C. Instance-wise mmiimmax-optimal algorithms for logistic bandits. In Inter- national Conference on Artificial Intelligence and Statis- tics, pp. 3691-3699, PMLR, 2021.
Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
Agarwal, A., Agarwal, S., and Patil, P. Stochastic duel- ing bandits with adversarial corruption. In Algorithmic Learning Theory, pp. 217-248. PMLR, 2021.
Di, Q., Jin, T., Wu, Y., Zhao, H., Farnoud, F., and Gu, Q. Variance-aware regret bounds for stochastic contextual dueling bandits, arXiv preprint 1exXi:22/00009990 2023.

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
Ding, Q., Hsieh, C.-J,, and Sharpnack, Robust stochastic linear contextual bandits under adversarial attacks. In International Conference Artificial Intelligence and Statistics, pp. 7111-7123. PMLR, 2022.
Jun, K.-S., Jain, L., Mason, B., and Nassif, H. Improved confidence bounds for the linear logistic model and ap- plications to bandits. In International Conference Machine Learning, pp. 3318-51551 PMLR, 2021.
Dudík, M., Hofmann, K., Schapire, R. E., Slivkins, A., and Zoghi, M. Contextual dueling bandits. In Conference on Learning Theory, pp. 563-587. PMLR, 2015.
Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, P. Pac subset selection in stochastic multi-armed bandits. In ICML, volume 12, pp. 655-6622 2012.
Falahatgar, M., Hao. Y., Orlitsky, A., Pichapati, V., and Ravindrakumar, V. Maxing and ranking with few as- sumptions. Advances in Neural Information Processing Systems, 30, 2017.
Komiyama, J., Honda, J., Kashima, H., and Nakagawa, H. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference on learning theory, pp- 1141-1154. PMLR, 2015.
Komiyama, J., Honda, J., and Nakagawa, H. Copeland dueling bandit problem: Regret lower bound, optimal algorithm, and computationally efficient algorithm. In International Conference on Machine Learning, pp. 1235- 1244. PMLR, 2016.
Faury, L.,, Abeille, M., Calauzènes, C., and Fercoq, O. Im- proved optimistic algorithms for logistic bandits. In- ternational Conference on Machine Learning, pp. 3052- 3060. PMLR, 2020.
Faury, L., Abeille, M., Jun, K.-S., and Calauzènes, C. Jointly efficient and optimal algorithms for logistic bandits. In International Conference Artificial Intelligence and Statistics, pp. 546-580 PMLR, 2022.
Kuroki, Y., Rumi, A., Tsuchiya, T., Vitale, F., and Cesa- Bianchi, N. Best-of-bothhworrdd algorithms for linear contextual bandits. arXiv preprint arXiv:2312.15333, 2023.
Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. Para- metric bandits: The generalized linear case. Advances in Neural Information Processing Systems, 23, 2010.
Lai, T. L. Adaptive treatment allocation and the multi-armed bandit problem. The annals of statistics, pp. 1091-1114, 1987.
Gajane, P., Urvoy, T., and Clérot, F. A relative exponential weighing algorithm for adversarial utility- dueling bandits. In International Conference on Machine Learn- ing. pp. 218-227. PMLR, 2015.
Lai, T. L., Robbins, H., al. Asymptotically efficient adap- tive allocation rules. Advances in applied mathematics, 6 (1):4-22, 1985.
Lattimore, T. and Szepesvári. C. Bandit Algorithms. Cambridge University Press, 2020. doi: 10.1017/ 9781 108571401.
Gupta, A., Koren, T., and Talwar, K. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pp. 1562-1578. PMLR, 2019.
Lee, C.-W., Luo, H., Wei, C.-Y., Zhang, M., and Zhang, X. Achieving near instance-optimality and minimax- optimality in stochastic and adversarial linear bandits simultaneously. In International Conference on Machine Learning, pp. 6142-6151. PMLR, 2021.
He, J., Zhou, D., Zhang, T., and Gu, Q. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. Advances in Neural Information Processing Systems, 35:34614-3466 2022.
Li, L., Lu, Y., and Zhou, D. Provably optimal algorithms for generalized linear contextual bandits. In Interna- tional Conference on Machine Learning, pp. 2071-2080. PMLR, 2017.
Heckel, R., Simchowitz, M., Ramchandran, K., and Wain- wright, M. Approximate ranking from pairwise compar- isons. In International Conference Artificial Intelli- gence and Statistics, pp. 1057-1066. PMLR, 2018
Li, X., Zhao, H., and Gu, Q. Feel-good thompson sam- pling for contextual ducling bandits. arXiv preprint arXi::2404.0000 2024.
Jamieson, K., Katariya, S., Deshpande, A., and Nowak, R. Sparse dueling bandits. In Artificial Intelligence and Statistics, pp. 416-424. PMLR, 2015.
Li, Y. Lou, E. Y., and Shan, L. Stochastic linear opti- mization with adversarial corruption. arXiv preprint arXiv: 1909.02109, 2019.
Jun, K.-S., Bhargava, A., Nowak, R., and Willett, R. Scal- able generalized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems, 30, 2017.
Lykouris, T., Mirrokni, V., and Paes Leme, R. Stochastic bandits robust to adversarial corruptions. Proceedings
10

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 114-122, 2018.
Wu, H. and Liu, X. Double thompson sampling for duel- ing bandits. Advances in neural information processing systems, 29, 2016.
Ouyang, I.,, Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744 2022.
Wu, Y., Jin, T., Lou, H., Farnoud, F., and Gu, Q. Borda regret minimization for generalized linear ducling bandits. arXiv preprint arXiv:2303..888 230.008 2023.
Xiong, W., Dong, H., Ye, C., Zhong, H., Jiang, N., and Zhang, T. Gibbs sampling from human feedback: A prov- able kl-constrained framework for rlhf. arXiv preprint 0rX1v:2312.11456 2023.
Ramamohan, S. Y., Rajkumar, A., and Agarwal, S. Dueling bandits: Beyond condorcet winners to general tournament solutions. Advances in Neural Information Processing Systems, 29, 2016.
Ye, C., Xiong, W., Gu, Q and Zhang, T. Corruption- robust algorithms with uncertainty weighting for nonlin- ear contextual bandits and markov decision processes. In International Conference on Machine Learning, pp. 39834-39863. PMLR, 2023.
Saba, A. Optimal algorithms for stochastic contextual prefer- ence bandits. Advances in Neural Information Processing Systems, 11330050-30062 2021.
Saha, A. and Gaillard, P. Versatile dueling bandits: Best-of- both world analyses for learning from relative preferences. In International Conference on Machine Learning, pp. 199026. PMLR, 2022.
Yu, T., Quillen, D., He, Z., Julian, R., Hausman, K., Finn, C., and Levine, S. Meta-world: A benchmark and evalua- tion for multi-task and meta reinforcement learning. In Conference on robot learning, pp. 1094-1100 110.. PMLR, 2020.
Saha, A. and Krishnamurthy, A. Efficient and optimal algo- rithms for contextual dueling bandits under realizability. In International Conference on Algorithmic Learning Theory, pp. 168.994. PMLR, 2022.
Yue, Y., Broder, J., Kleinberg, R., and Joachims, T. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538-135 2012.
Saha, A., Koren, T., and Mansour, Y. Adversarial duel- ing bandits. In International Conference on Machine Learning, pp.
PMLR, 2021.
Zhang, X., Chen, Y., Zhu, X., and Sun, W. Robust policy gra- dient against strong data corruption. In International Con- ference on Machine Learning, pp. 12391-12401. PMLR, 2021.
Sawarni, A., Das, N., Barman, S., and Sinha, G. Generalized linear bandits with limited adaptivity. arXiv preprint arXiv:2404.0683 06831, 2024.
Zhang, Y.-J. and Sugiyama, M. Online (multinomial) logis- tie bandit: Improved regret and constant computation cost. Advances in Neural Information Processing Systems, 36, 2024.
Sekhari, A., Sridharan, K., Sun, W., and Wu, R. Contextual bandits and imitation learning via preference-baeee active queries. arXiv preprins arXiv:2307. 12926, 2023.
Seldin, Y. and Lugosi, G. An improved parametrization and analysis of the exp3++ algorithm for stochastic and adversarial bandits. In Conference on Learning Theory, pp. 1743-1759. PMLR, 2017.
Zhao, H., Zhou, D., and Gu, Q. Linear contextual bandits with adversarial corruptions. arXiv preprint 1.Xi:21110.121111 2021.
Seldin, Y. and Slivkins, A. One practical algorithm for both stochastic and adversarial bandits. In International Con-
Zhu, B., Jiao, J., and Jordan, M. I. Principled reinforcement learning with human feedback from pairwise k-wise comparisons. arXiv preprint 10.Xi:::301.1127000 2023.
ference on Machine Learning, pp. 1287-1295. PMLR, 2014.
Zhu, H., Yu, J., Gupta, A., Shah, D.,, Hartikainen, K., Singh, A., Kumar, V., and Levine, S. The ingredients of real- world robotic reinforcement learning. arXiv preprint arXiv:2004. /2570, 2020.
Verma, A., Dai, Z., Lin, X., Jaillet, P., and Low, B. K. H. Neural dueling bandits. arXiv preprint arXiv:2407.1711 2024.
Wei, C.-Y., Dann, C., and Zimmert, J. A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, pp. 1043-1096. PMLR, 2022.
Zimmert, J. and Seldin, Y. An optimal algorithm for stochas- tic and adversarial bandits. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 467-475. PMLR, 2019.

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
Zoghi, M., Whiteson, S., Munos, R., and Rijke, M. Rel- ative upper confidence bound for the k-armed dueling bandit problem. In International conference machine learning, pp. 10-18. PMLR, 2014.
Zoghi, M., Karnin, Z. S., Whiteson, S., and De Rijke, M. Copeland dueling bandits. Advances in neural informa- tion processing systems, 28, 2015.
12

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
A Proof of Theorems in Section 5
A.1 Proof of Theorem 5.3
In this subsection, we provide the proof of Theorem 5.3. We condition on the high-probability event in Lemma 5.1
& = (1 0 E. SB.W
where 3 VBB aC' + Vdlog (1 2T/))/)) 1/B2.
Let 72- = 2r"((1 a,) - (x 01) - -r" by) be the regret incurred in round t. The following lemma provides the upper bound of rt-
Lemma A.1. Suppose the event & holds. If we set 3 vBB + +a + V the regret of Algorithm
1 incurred in round can be upper bounded by
Tt min (42281((Iz+ as) b(xx,,)))
Moreover, the regret can be upper bounded by
S Σ min (4, ((r,, - ((I,, be)llx }.
Regret(T)
With Lemma A.I, we can provide the proof of Theorem 5.3.
Proof of Theorem 5.3. Using Lemma A.I, the total regret can be upper bounded by
Regret () $ Σ min [42 ((1,, - Φ(x,, be)lls;
Our weight wa has two possible values. We decompose the summation based on the two cases separately. We have
Regret (T) < Σ min { [,223 2/ a.) - ((x,, bi)l,, }
min {4, 20 a.) ((I(b()))
<1
J2
For the term J1, we consider a partial summation in rounds when wt 1. Let A, = AI Eish- n(p(o1,)))
((x,, b:)) (Ø(2,, a;) - <b(x,, b.)) T Then we have
48
J1
<
Σ min (1.IVE((((())))) belrrr
K
43
min (1) be)llaa)
K
43
T
min (1. VV ax) - b())11)))1
be))
t:w==1
48
dl log + 2T/A),
(A.1)
where the second inequality holds due to E, 2 A,. The third inequality holds due to the Cauchy- Schwartz inequality, The last inequality holds due to Lemma F.3.
13

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
For the term 22 the weight in this summation satisfies wa < 1, and therefore wi = (1) ae) ol bi) b.) Then have
J2
min (4,88] Φ(xx, be))) b:)12; w. (0( ar) (zt,, (,),,,))l1xx
<1
min (4.23/all - (o(xe,be))1
48 min (. 01 bo))))))
1=1
4d3 log(1 + 2)
(A.2)
where the first equality holds due to the choice wt. The first inequality holds because each term the summation positive. The last inequality holds due Lemma F.3. Combining (A.1) and (A.2), we have
43 dT + 2T/X) 4d3 log (1 + 2T/A)
(e) s
By setting VBB + aC ( 1/B², a= va)(OvR), we complete the proof of Theorem 5.3.
A.2 Proof of Theorem 5.4
Proof of Theorem 5.4. We consider the following link function
0
if v <
o
(x))
if E F,
1 2'
(A.3)
1
if >
Firstly, we prove minimax lower bound. We follow the proof techniques in et al. (2024). The difference lies in that they consider the sigmoid link function, while consider another. Consider the parameter set θ (-A, A-,,A A)d, where A 0 is constant to be determined. Let the action set be A {x E [g ||*||| S 1]. We assume the feature map o(x a) a. For any algorithm, denote the trajectories of actions by {a,, b,)T We require that for any action x E A, 0 E O, we have x < 1/8. For this reason, we assume VdA < 1/8.
We fix i E [d]. Define
2T d
7 = A'A min
T + (bt) N
(A.4)
where a 6 min(a, b} and al means the i-th coordinate a, Intuitively, t; acts as the first time in which the amount of information gathered for coordinate i until time (quantified the sum of squares of the i-th coordinates the chosen arms) exceeds the average amount of information expected, which is 27/d. For any O E O, we denote IP and Egg the distribution and expectation over the trajectories. We define the following function
2
T2
2
(x,(xx) = F. Σ
a
big
Vd
with x (11, which can be understood the lower bounding term that pops up when lower bounding the average dueling regret. We greatly appreciate this insightful explanation above from the autonomous reviewer. Moreover, we define O' to be vector whose i-th coordinate is different from 0, while the other coordinates are the same. Denote the i-th coordinate of 0 by 6, We consider the following term:
Uo (0)) + Uo, Vuri:(sign(0)) (0)) = (s..(sig((O)) Uo (.r.g(sign((.)) + Uor (sr.n(sig)(O.)) + Up. Uor, (sign
(A.5)
h
12
14

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
First, we have
vd - af sign((.))
Σ
1 vd
bj sign((:))
_
2
+
2(a{)²
+ +Σ t=1
2
+ 2(b))
d
d
1=1
1=1
4r
+
(at)² + (b/)²)
d
1=1
4T 4T
+4
d
8T
+ 4,
d
where the first inequality holds due to (a - b)2 < 2a² + 262.
The second inequality holds due to (A.4). Therefore, we have
a sign((,)) 2
bj sign (a)))
1 = Eg
+
Vd
(=1
a sign((.)) 2
T2
sign (0.) )
Egg
+
bj
vd
Vd
8T
+ +4
(L Po.)/2
(A.6)
d
where the first inequality holds due to the Pinsker's inequality. Next, we compute the KL--divergence.
KL [Po = Σ (P
(A.7)
which holds due to the chain rule of KL-divergence. At each step t, the distribution is Bernoulli. Using the link function (A.3), we have Py Ber(r)), P. Ber(yg)), where ràè 1/2 + (a, b 0). Direct calculations show that
KL = pb log
Pb Pg
+ (1 pb) log
[ - P/g
1 P/d
I'1
1/2
S r0
1
+ (1 - v66)
P/
1 pz.
(rè
Po
$ )2
p/
p
where the first inequality holds due to log
1. Using vdA 1/8, we have
16 ((ar b., 0 0²))
(L è
p.. -
(A.8)
Substituting (A.7) and (A.8) into (A.6), we have
12 -3
8T
+4)
Σ
((a: b 0 0
2 -3 d + 4)A
87
Σ |aj b/l3/2
2 -3 88
+ 4
Σ [a])² + (b:)²]
d
15

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
where the second inequality holds due to 0 only differs from O' at the i-th coordinate. The third inequality holds due (a- b)2 s 2a² + 212. Using (A.4), we have
8T
2T +22
1 -3 ( +
AV
(TA
(A.9)
For 1z, we have
2 = Uo (sign(0:)) + Up [ (sign(()))
at ) + + 1
27
2 +
+Σ + +Z( )
Egr
Va
by
Eg Σ
a,
2T
(at)² + (b:)2)
2TE
4T
2 d
(A.10)
Substituting (A.9) and (A.10) into (A.5), have
4T _ (sign(()) + (sign((()) 2 d
40 (T/AL/
Using the randomization hammer, we have
Uo (sign())))) 27 1-
13--0
DE
Therefore, there exists 0 E O, such that
Σ Uo. 2T 2 1.
(A.11)
Using this 0, we can decompose the regret into
T
af sign sign((.))
Vd - bj sign (8))
Regret(T)) = AE
+ AE
Moreover, we have
at sig)((.))
Σ
1
a sign(0.))
Vd
Vd
2/d
2
d
+ vd
a sign((.))
(at)
2vd
2
i=1
Vd
d
2 - a sign(0:)
2
where the first inequality holds due to ||a/12 < 1. Similarly, we have
Vd
bj sign(0.) )² 2
bj sign((.))
Vd
2
Vd
16

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
As result, we have
dA
bj sign(0.)) )
Regret(T)
Eg
af
sign((.)
E0
2
Vd
Vd
i=1
1=1
i=1
1=1
VdA
Ti
2
VdA
71
2
E.
a sign(0.)
E.
Σ
bj sign(0:)
2
vd
Vd
VdA
Uo. (sig(sig)(O.))
2
1=1
VdA
2T
20A7
where the last inequality holds due to (A.11). Set A 1
20 V- Then we have proved a lower bound Regret(T) 2 dyT/444 Moreover, when T > (4d2)/25, we have Via 1/8. In conclusion, for the link function defined in (A.3) and any algorithm, there exists dueling bandit instance such that the regret is (2d Secondly, we consider the lower bound of the corruption term. Our proof adapts the argument in Bogunovic et al. (2021) to dueling bandits. For any dimension d, we construct d instances, each with 0; e,/4, where e; is the i-th standard basis vector. We set the action set A {e:) Therefore, in the i-th instance, the reward for the i-th action will be 1/4. For the other actions, it will be O. Therefore, the i-th action will be more preferable to any other action. While for other pairs, the feedback is simply a random guess.
Consider an adversary that knows the exact instance. When the comparison involves the i-th action, it will corrupt the feedback with a random guess. Otherwise, it will not corrupt. In the i-th instance, the adversary stops the adversarial attack only after C times of comparison involving the i-th action. However, after C'/4 4 rounds, at least d/2 actions have not been compared for C' times. For the instances corresponding to these actions, the agent learns no information and suffers from (dCC) regret.
Combining the results above, for the link function (defined in (A.3)), the lower bound for dueling bandits is M(dv + +CC). Finally, for any K, we define (x) = (Kz)). Then min (-) = k. For any algorithm Alg, consider the hard instance T + dC). Define another instance /' = (0", A/H,, ax). The interaction with the environment with I and I' are exactly the same. However, the regret with I' is Regret (T)/n, /R. This indicates a lower bound of Q(dvT= + dC)/K, which completes the proof of Theorem 5.4.
T= (0" (0", A.,o) o) with the link function a, and Regret (T) = Q(dvT
A.3 Proof of Theorem 5.5
Proof of Theorem 5.5. Here, based on the relationship between C and the threshold Č, we discuss two distinct cases separately.
In the scenario where Ö C, Algorithm can ensures a trivial regret bound, with the guarantee that Regret(T) S 2T.
In the scenario where C < C, we know that Ö is remains a valid upper bound on the number of adversarial feedback. Under this situation, Algorithm operates successfully with C adversarial feedback. Therefore, according to Theorem 5.3, the regret is upper bounded by
Regret(T) < +
17

---

Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback
B
Proof of Lemmas 5.1 and A.1
B.1 Proof of Lemma 5.1
Proof of Lemma 5.1. Using a similar reasoning Li al. (2017), we define some auxiliary quantities
G,(0) X0
Wi Σ
0 ((b(x),))) ((xr T0)
i=1
(0(z,,,) - ((z; 0-) (Ø(I,, az) bi),
4 4 (10(2)) 0(1,, be)) (.)
71 0 ((0(1), at)
(, - T )0))
1-1
2 ( a.) ((5,, b,)).
In Algorithm 1, 0, is chosen to be the solution to the following equation,
10 + Σ wi [o (((((11)
b(),,b)) To.) -a,] (0(11) a.) b,),,,,)) = 0.
Then we have
G..).) 20, Σ mi (o ( (()r, T 0.)
((( bi)) 00) -
ai) (()))))))
Σ
Wi 0z - (()(1,a))) ( bi)) ( (0b az) (x..)))))
1=1
Ze.
(B.1)
The analysis Li al. (2017); Di et al. (2023) shows that this equation has unique solution, with 0. 0.= the mean value theorem, for any 01, 02 E Rd. there exists E [0, 1] and m0 + (1 -m)) mm)02. such that the following equation holds.
= G, (Zz). Using
G.(O,) - G. = A(0 02) + +- wi oo ((0(2;)))) o(xx, (..)
i=1
- ( ax) bi)) T 02)) (0( as) - p(a, bi))
XX + Σ wio a:) - ((z (((,,)) T0)
i=1
(0(I,, (((z,))))) ( o( 7 (0, 02).
We define (()) as
F(O) AI Σ w.o ( (x)) T0) (0(#,, a.) ((o,, (1)) -((E)))))
18

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
Moreover, we can see that G:(0") = >00. Recall Σ, XI Σ wwx -1( - o(x,, b,), T
We have
[.((.)) - G.(0') (1) = (0:- - -0) F - 0*)
2 (0: 0*) 0
100 0 11.
where the first inequality holds due a(.) 2 x and F(0) = Σ. Then we have the following estimate of the estimation emor:
100 - 0-112 < [G) - G.(0") E,
S 1|10"1|>; || E,¹
$ <A100 + 11 |
where the second inequality holds due to the triangle inequality and (, Xe.. The last inequality holds due E, - AI. Finally, need bound the || term. To study the impact of adversarial feedback, we decompose the summation in (B.1) based on the adversarial feedback ct, i.e.,
Z =
w a:) ((z;, +
E winh (p(z;, a;) Φ(2,, b.)),
i<be==
icte=1
When Q 1, with adversarial feedback, hi - Gl On the contrary, when G; = =0, = c.. Therefore,
Σ
wni(o(a, a,) (xxx,,,))
Σ
(; a.) ((xx,,,))
ictres=0
i<too=0
Σ
wnx( a.) b(),,b,)) Kta==
( a;) - ((xx,,,,)))
<cb:=1
Σ
w,(n: (d((,)))))) - (1 b,)).
itt==
Summing up the two equalities, we have
Z.
wees (0(#), az) b(xi,bi)) +
Σ
wi(n - ( - (((xt)b)))
ictoo=l
Therefore,
Σ wi (oG - olz, b.))
Zz | x I
Σ ietreem
wi (i(((zi,a)) o(I;, bi))
Ex
For the term 4, with probability at least 1 8, for all t [T', it can be bounded by
2 det det(E,)) 1/2 det(Eo)-13)
8
due to Lemma F22 Using Wt < 1 K S 1, we have Vin (1 a4) - 6(z,, b,)1l s Moreover, we have
Tr Tr(E,)
det Ex) 5
dd Σ winll(((E,,a) a4) -(I,, by)) d
dd 27 d
19

---

Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback
where the first inequality holds because for every matrix A E Rddd det. A < (Tr(A)/d) The second inequality holds due to ( 0:) (0 b.)ll2 2. Easy that det A The term 1 can be bounded by
1 S vdlog((1 + 22/22//).
(B.2)
For 12, with our choice of the weight w/, have
1 <
Σ
a)) (i)):bi))ll;;
Σ
w: wi][(d(x;; a;) - 6l b.))l1,;'
Ktb=1
<che=l
S aC,
(B.3)
where the second inequality holds due to Σ, ट E, The third inequality holds due to w, S <a/l(((x,, a.) o b,)) x 1 The last inequality holds due to the definition of C. Combining (B.2) and (B.3), we complete the proof of Lemma 5.1.
B.2 Proof of Lemma A.1
Proof of Lemma A.I. Let the regret incurred in the t-th round by 2r - r (x(,, - r (xt, be). It can be decomposed as
Tt = (xr, a;) r" (zt, a.) r (Zz,
= (0(12, ai) o(z,, 0*) + (Ø(0,, b(x),
bx), 0")
= (D(1s, ai) Φ(v,, a:), 0" 01) (0(2,, 05) - (x),,,bb), - -0.)
+ (2.((1e: az) (( 0t) ((s,, O₂)
S || aj) - Φ( ")]| 0 0.l12, + 110(z)) 0,) Φ(I1, b()),;)))l 110 0clls,
+ (20(11 (.) < (:) 6( b)), O₂)
S Bllo(a,, at) - 6l 01) 1|, x + Bl| ai) (xx bi)llx. + (20(1,, a.) p(,,, a,) 6( b,), 0z),
where the first inequality holds due to the Cauchy-Schward inequality. The second inequality holds due to the high probability confidence event E. Using our action selection rule, we have
(Øp(,,, at) ((x, 0x), 0,) + (1 at) - (1x,, ot)
S (0(2,, b,) ((z,, 0) + (1( 0r) ((
(Ø(1,, (1.. Bl ai) (l b.) bi)lls;'
S { a+) - (,), 01) + (1 an) ol bi)ls,
Adding the above two inequalities, we have
B Bl| uf) - ΦlV,, a:) ()), + B11 az) ( ((rb,)))l
S ( a4) + ((v,, b.) - 2Φ(2;, a;) 0,) + ( at) D(x, bi)l Therefore, we prove that the regret in round t can be upper bounded by
$ 28 a4) ((0,, bi)ll,,,)
With a simple observation, have r. S 4. Therefore, the total regret can be upper bounded by
min { 2, (Dre,, an) ((r.be))lE.)) }
Regret(T)
20

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
C Proof of Theorem 6.1
To start with, we define some high-proboen probability events. Recall that
a.) Φ( bi)) (1. - b,)) T
Σ = +
A = AI Σ - iai w (0(2,, ai) - Φ(z,, b,)) (6(x, a,) o( bi))
Then we define the following events:
& {10- 0,112, 1 B,, v2 [T]) & {10- - Oella. S B, Vt E [T]}
The following lemma indicates that with some well-chosen confidence radius, both & and & will happen with high probability.
Lemma C.1. When selecting
1
3 = VAB+ +
2//1)/6) + aC,
VK
3 = (1 4B)
VBB +
VA
+
2
dlog
(d) + 2f d)
+ dlog(1/0) + ac
2
2
vT
then we have
P| n &2) 2 1 - 6.
Proof of Theorem 6.1. Consider the case when & & holds. Recall that A is defined by
u ( ae) (b(),,))) 0.1 (ell ((sr,b
then we have
A 2 ((((I))))) ΦI b)))
- T 00| + 31(((,, olIz, bo)l,,)) -((o,,,)) "( T - -0)) 0:)
2 (0(Ez) oz) ol b))) 0%
where the first inequality holds due the triangle inequality. The second inequality holds due to E and the Cauchy-Schwarg inequality. Let 2i2 max{x, ō {.)] Using the fact that a--) is even function decreasing when > O, we have T i I (((((1, at) - (( bt)) 0*) Let the regret incurred in the f-th round by rz = 2r" (xt, az) - r (xz, ae) - r (x,, bt). can be decomposed as
Ti = =r' a²) r" (" a:) - be)
(0(E,, at) a.), + ( at) 61 by), 0
(d(a), a/) (l 0z), 0" - 0,) + (0(a), aE) (0I be), 0- - -O.)
(20(21, ai) ol ()) - Hl b,), 0₂)
< || ai) - Gl0, a)) A- 1 - 0. A + +1 (t)) - G1I,, bill - -elll,
(20(z1, at) 66 01) Φ(z,, br), O.)
< 3,l1o(1, ai) - (12, A- + 3.llo(zz [z,, a.))
Dla, bi)ll,
+ (20(1,, at) px ar) (z b,), 0.):
where the first inequality holds due to the Cauchy-Schwaad inequality. The second inequality holds due to the high probability confidence event &g. Using our action selection rule, we have
(a(a,, at) - ((I,, ax), 0.) 3. (a,, az) at)ll,,
S (0lx - 0.) + 3, (1 at) - ((ar, be)l
(Ø(oe, a4) - ((1,, + 3 (x,, at) $( be)ll
s (0(1), ar) bz), 0,) + ( az) - 611 be)l ll),
21

---

Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback
Adding the above inequalities, we have
(e oi) a:),, (ell at) (()x,bi)lla I (1) + b(),,b)) 20(21, ai). 0.) + 23:11 ar) Φ( (( b.)l, Therefore, we prove that the regret in round l can be upper bounded by
Ti 23 (2),) ai) o0(,,
As result, the total regret can be upper bounded by
T
(Tg S 23r
Σ
where we use that 3, is increasing in t. Since our weight wy has two possible values, we can decompose the regret into two terms:
(T) S 23r
Σ
(1 ar) - (11,, be)ll,
t:w,==
+ 2BT tomi
Σ
[((()),)))) - ((FI,
f2
For the term L, we consider a partial summation in rounds when w, = Let A, AI Eige- (:(o(z;,a)) Φ(I, bi)) (6(z,, a;) - $(2,, b;)) T. Then we have
11 =223r
Σ [[ve((((nna)) b()r,b)))lla
A:w,
< 2,T
Σ ( Dlur, be))
Arany
< 23r
Σ
(1b(t)))))) - ((0,, 61
< 44BTvdlog(1 - 22T/A)
Σ A000
1 U
(C.I)
where the first inequality holds due to the Cauchy-Schwarz Schwarz inequality. The second inequality holds due to A, 2 Å.. The last inequality holds due to Lemma F.3 and / (Ø(2,, a.) Φ(x, b.)) 1l, I 2. Next, we will bound Et.w: 1/0,-
Let L1 = {t We = 1. = max(k: a ((A))) L2 = (t w. = 1, (A.) = max ò (A))) Then, we have {t: w. = 1} = L1 Lz. Therefore, we have the following decomposition
Σー ト
w==1
tEC
LEL2
J2
For J1, we have
J
Σ
1
11
LEL1
-
1
(C.2)
K
22

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
This equality holds because for / L1, U/ k. Using the high-probability event & the following inequality holds:
A [ a,) Φ b.) 0.1 + B a.) o 6x),,,
< [0(2) a1) o(z), b1)] 0- + 2 ((2), Φ( bi)ll,,
On the other hand, for E L1, we have
2 o o(A,)
((0,, à (100112 - b 0- To 23)l)o(m,, Φ(1,, bi)llz
where the first inequality holds due the definition of L1 The second inequality holds due the function d() is decreasing when 0. Using d(xx)) e |ml /(1 - 2 e e-1= /4, have |xr| log(1/40(1z))). Therefore, the following inequality holds
(())) - (xxe,bb) To + +22ello(ze,, az) - o(z1, bi)ll, 2 log 45(A,)
2 llggL//ni)
Let Σ, AI Eis 1,0y 16 ((((x; a;) 6(r,, b,)) (#(x;,, (((x,,,))) T. Summing over t L1, we obtain
1og(1/44 (gg(1/4x))L41
[o( ((1, bn)
0- 2
Σ
110(I2;; (e
1
DEL,
<
Σ
[ 0r) - ((x,, br]
0-
+ 2,3r
Σ
||
ax) - ((E,, be)l
trang
Σ
[0(x), 6(1
0t
+ 238
T
(1 ( bi)l
[ ur) (55,, be]]
0"
23T
Σ
(V((b() 6l bi)) |s
VK
1:00
2,T Kk
S Σ [db 0x) (( be]] be] 0"
v
dT log(1 27/A),
where the first inequality holds due to 3g is increasing in t. The second inequality holds because partial summation is less than total summation. The third inequality holds due to the Cauchy-Schwald inequality and E, Σ,. The last inequality holds due to Lemma F.3. Therefore, we have
23r Vx
C S log(1/An)
Σ (1)) - (III,
0"
df log(1 21/A)
(C.3)
Substituting (C.3) into (C.2), we have
J1 S x <log(1/4x)
1
[olon, ar) - ((2r,
0-
20r Vn
v /dT log(1 + 2T/A)
(C.4)
For Jz, have
J/ =
CCC2 Ut
Σ
t( (,
A.1
< 4
(C.5)
23

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
where the last inequality holds due to ((xr))
e e-1ai /4. For L L2, we have
K (Ar)) S Se -
where the last inequality holds due to (1x=) S e |a|, Then we have
Ad S log(1/k)
Since the function f(x) = ex is convex, for any A > 0, we have for all E [
1
S1+ A z.
Setting x = Ar and A = log(1/k), we have
A < 1
log(1/m) (1/x) Del.
1/K-- 1
(C.6)
Substituting (C.6) into (C.5), we have
1/K 1 log( log(1/ (1/x)
J2 S 4 Σ
1 +
Eel
1EC,
Moreover, we know that
A, = ((b(s), ae) 01 b.)) T 0.| + (+Bllo((z;; az) -5 be)) x,
S (0(I); at) - (((,,bb)) 0- + (, a.) Φ( belllr...
(C.7)
Therefore, we have
J/ S T +
23r
T
| ar) )((,,,i)ll + x xlog(1/k)
( (ō(z), - ((22,)))))) 00
ki <log(1/K)
t=1
T - - ((2), bi)) E- #log(1/K
2,37
(5(2), ar) Dl be)) 001
< 4 T + kI. log(1 1/K)
< 47
83T
dT log(1 + + Ki (0/(1/))
4
Σl [I(((z),))) - ((I,,)))) 001
(C.8)
k1.5 log( 1/x)
where the first inequality holds due to (C.7). The last inequality holds due to Lemma F.3 and the Cauchy-Sehie Schwarz inequality. Combining (C.4) and (C.8), we have
Σ t:
1 < U1
T
[sb(r,, at) (()r,bb)] 0-
+
2,r Vk
v dT log(1 + 2T/
(log(1/4m))
+ 4T +
8,37
dT log(11(1 + +TT/A) +
1
- -
T 0.
1.5 log L/K)
k log(11 1/k)
T
< 47 + k1. log(1/
103r
ddTlogl1 - ( + log(1
[ 0r) :lx,; be)) T
(C.9)
(1/))
For the term Iz, the weight in this summation satisfies w. 1. and therefore we = aalla//l1220 at) 6 bi) bi), Then we have
In = 23r
Σ
-ole,, - bi) w (1 at) bi Dl b.) bi)l_//))
wi<1
2
(wrr((((2)))a)) Glo,, be) E
OK
4d3T log(1 1 + 2T/
(C.10)
an
24

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
where the first equality holds due the choice of wt The first inequality holds because A₁ Σt. The last inequality holds due to Lemma F.3. Moreover, we notice that the following inequality holds:
(Ø(I), ar) 0(zr, b.)) 00
(0(z,, ai) ((E), To" (0(z), at) Φ( bi)) T 0r
T (o(x,, 0,) - (()),)))) '0"
0" + (0(x,, a;) ,(z,,,b)) "0"
==1
(T)
(C.11)
Substituting (C.9) and (C.11) into (C.1), we have
30
I s dlog/ 2T Combining (0) and (C.12), we have Regret(T) < 43r /dlogl1 /
4T
dT log(1 + 2T/A) +
Regret(T)
(C.12)
1. log(1/n))
klog(1/x)
103r
2
4T
V ddT /d + 2T/AA) + <log(1/k) Regret(T)
k:15 log(1/k)
4d (
ak
105r
2 k. log((//x) v Reegret(T)
$ 43r / dlog(( - 2T//
3 1.. log(1/k)
Vdlog(1 + 2T/A) + |
AdBrlog(( + 22
ak
where the last inequality holds due to Young's inequality and va - cs v Vb + Vc. Using x sa/z +b a² 2b, we have
Regret(T) < 245r / log(1 (T//A)+ + 80 30(3//n /n + 3r Br / 1 / dl + 27/A)
log(1/m)
8d5T log 27/A)
(C.13)
OK
Recall that
8. = VAB +
d dlog (2(g((21111 + (2 21/A)/5) 2112/)))))) + aaC,
VK
V1
2
(d + 2t
2
dlog(110)) ac
3 (1 4B)
VBB
dlog
2
d)
Choose A = d/B, (vd+ + VAB/
Then we have
2
B. <
dB + /dlog(11 (110/((1+1///0/0) 21B/d//8)
Vk
3. m 4(1 4B)
4B) log ((1 + 21)/d)))))
(C.14)
Substituting (C.14) into (C.13), have
Regret(T) < 150 d /Tlg 1.5 (1+2TBB/d/1)
10000(B/K- / 1/k²) 8² log (11+2T B/d))/
log(1/n)
+ +2ddB log² ((1 + (
This completes the proof of Theorem 6.1.
25

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
D Proof of the Lemmas in Section C
We first prove Lemma C.I. Before start, will mention that Jun et al. (2021) considered slightly different but relevant confidence bound. Specifically, they studied the logistic bandit problem with pure exploration and proposed an algorithm with sample complexity guarantee. In contrast, our work focuses on the regret of dueling bandits, with the approach involving reward estimation complemented by bonus term. Furthermore, Jun et al. (2021) derived a concentration inequality under fixed design assumption, given by (a,, 0 1*) Σ ((())) However, this assumption is too restrictive for our setting with adaptive action selection. In contrast, our concentration inequality (Lemma C.I) is applicable to adaptive designs that holds for any arm, which works for the adaptive arm-selection inherent to bandit algorithms.
D.I Proof of Lemma C.I
We define some auxiliary quantities
G, - Xo + Σ Wi o (((()) - o(x;; To)
i=1
(o(x), a.) - 0 b.)) 0.) } (Ø(I,,, az) b(x,,b))),
4 = 4 (0(12,, ax) - Φ(1,, br)) (.)
((o(2), ar) - o( be)) T 0r)
7 0:
[-1
2, = Σ
w a.) b();,b)))
1=1
In Algorithm& 2, 0, is chosen to be the solution to the following equation,
1 + Σ wi
[o
((0(z), o(zn,))) 0.) o.] (0(I))))) -0(x1,,))) = 0.
Then we have
[-1
G,(O,) 10, +
Σ
wi (( bi)) 0.)
i=1
((((I,));) - ((,,,)))) T0)) ) ( (2,, ai) ((xx,,b))
Σ We 0i -o (((((())) o(z, bi)) T 0r) (0(5,, as) - ((1., bi))
Ze.
First, we will bound| || Following the technique used in Section B. decompose the summation in (B.1) based on the adversarial feedback Cr, i.e.,
Z, = w a;) b(),,b;)) bi)
Σ
w 0,) (022, b.)).
i
When q = i.e. with adversarial feedback, his - Eil 1. On the contrary, when =0 7i = e;. Therefore,
Σ
wri(o(x,, ai) - ((Z;,b))) = Σ
wrei (oli( ai) - bi)),
icta==
Σ
w ai) - -0(21 = Σ
wie (0(2,, as) - -5x b.))
ixct:e;=1
ict:q==
Σ
wi(n (;)( a.) (lzx, bi)).
icteo=1
26

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
Summing up the two equalities, we have
Z, Σ wie; (0( ((),,b,))
+
Σ
wi(n - =))((2))))) -
icto
Therefore, we have
| | E.
Σ
way Kes (#(2s, ai) - Φ( bi))
Σ KcGG=
wi wi(((ri; - b(zz,b)))
(D.1)
VR
For the term /, with probability at least
5/2, for all / E (T). it can be bounded by
ddet(E,) det Ev) 1/2 -1/2
h S Vx V
2oo
6
due to Lemma F.2. Using wi < 1, we have /wil (will((Ii,n as) - b,),l, < 2. Moreover, we have
Tr(E,))
det(E,) -
dd + ΣE will will(((I,,a)) (o,,,,)))1 a
d
yA 21 d
where the first inequality holds because for every matrix A E Rddd det A < (Tr(A)/d) The second inequality holds due to Vio ((x; a:) - ((x,, b:)lla & 2. Easy to see that det (o)) = A The term Jı can be bounded by
v dlog(((1 21/A)//)))
(D.2)
For 1g, with our choice of the weight ws, we have
S
Σ
(()((a;;))-(laa) wi w;]((((s;;a;) az) - pl b:)),,,))
Kcb=1
Σ
w/
[o][((((;;) a;) Dla, b:)ll,,))
ictq=1
<
Σ a
<<tro=1
< aC,
(D.3)
where the second inequality holds due to E, 2 E. The third inequality holds due to wy S {all(((z,) 6la, b:)) The last inequality holds due to the definition of C. Substituting (D.2) and (D.3) into (D.1), we have
| | S VR
//lgg(221111 + 21/1)/0) aC.
Therefore, using the triangle inequality, we have
|[G)(0") - G.(0))l 1 1l ||,
1 / + aC
vk
1
S VAB+
v dlog(2(1 21/2)/8) + +
(D.4)
Vk
27

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
Using the Newton-Leiiniiz formula, we have
G.(0*) - ((.0)))G(00))- [[ (G) v 0.))du (0- Os)-
Recall the definition
1-1
G( = 00 + Σ wi o a) -((;, '0)
i=1
- (((()))) ((,,, (o))) (p(()))) - ((0,,b)))
then we have
VG, AI Σ wHā (1b(22; -ob(abb)) '0) (#b()i, ((xx, (0(r; az) (b(x,bb)) -
We define V, as follows:
V, / (O, -
AI Σ we [. ó ((0(E))))) - (((, b:)) (0, + v - 0.)) 0.))) de
(Ø(2, a:) - p(z,, (0(2)) a.) Φ( b,))
(D.5)
Therefore, we have V. - Eg. We know that Gi(0") G.)))) = Vi(0~ Ot). Then the following incquality holds:
GG,(0.) - -G:(0)) - = (0: 0*) V. - 0*)
2 (0: - )r) E. - 0*)
As result, have
110, - 001122 $ <[,Gr(0,) (r) x
S VBB +
Vx dlog(2(1 + 21/1)/8) + aC
= =,,
where the first inequality holds due to (D.4). Consequently, have P(&]] 2 1 - -5/2.
Let
1-1 H +
Σ wnd
(00,;, bi)) (o) (oo))))TTo))))))) (o((s, ( - 1000--((xee (o) - (lor,bi)) T.
Next, we consider the following term:
[-1
Zz |
waes (Ø(2;, as) - ((o.,bb)) bi))
+
Σ istior=
wi wi(o(z;;a)) - H(2,, bi))
H.
H
For J1, let F, = a111, 01, by, 01, x2, a2 b2, 02, Dt, ae, be). We know that e, It's F.41 measurrble.
E|e ((0(z)) ((xx, )r)
28

---

Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback
Using Lemma F.4, with probability least
8/2, for all E [T], have
J1 wie; w (0(Ix; a.) ((zz; b;))
H
2 log
dd) 1/2 d/2
2 d d'log(2).
2
Using wy 1,,0() & 1, we have via ( a+)
(frr, Moreover, we have
(r(H,)
det(H)) -
dd + Σ W/ (o(2; as) - b,))
d
yY 27 d
d
where the first inequality holds because for every matrix E Rddd det A < (Tr(A)/d)* The second inequality holds due to /wa (0 a,) - Φ(x,, b:) & 2. Therefore, we have
V +
dd + 2T
J1 S
d log
+
dloo(118).
(D.6)
2
dA
V1
For Jz, we have
J2 =
Σ
will(o(z,,ai) $< bi))la,))
Kto0=1
Σ wx]((o(x;;a)) a,) - 2(xx; bi))l,
ictea=
Σ a Kto:=
S aC,
(D.7)
where the first inequality holds due to H, ž H, The second inequality holds due to w; < a/l[(((z;, a.)
Φ(I, (rt.b,))lls b, and H. > E.. The last inequality holds due to the definition of C. Combining (D.6) and (D.7), we have
VA
2
yd dd + 2t
2 VX
|[G((0)) - Go(O)llH S 0
H.
+
2
+
Vx
d log
dΛ
+ dloo(1/8) + aa
VX
2
yd + 2t
2 dlog(1/8) +aC
VAB+
+
d log
(D.8)
2
VX
dd
VX
where the first inequality holds due to the triangle inequality. Recall V, defined in (D.5). Using Lemma F.5, we have
[-1
a((((1;))) 0:) ((rr, T 0*)
V, 2 AI +
Wi 1 (6(z;,a)) - ((I;, (0- - -0:) (Ø(x).a)) - Φ b;). (()) - b.),,b,))
1+4B H
(D.9)
where the last inequality holds due to ( - ((I;,b))) (0) - -0)) < 4B. This leads to
|[G((0)) - (O.) (A)) = (0" -1) V.H, 'v 0,)
1 + 4B 0 0.) V 01).
(1 + 4B)2 (0" 0,) H. 0²).
(D.10)
29

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
where the first equality holds due Conditioned on the event ε₁, recall that A, defined by
Vi(0" "((0~-0,) -0)) The first and second inequalities hold due (D.9).
A = 1 ax) (1 b.) 0,1 + Bell a.) - Φ(F,, b,)),
Therefore, have
A 2 ((0(z), 0z) -(x, b.)) 0-1 Bl( b(xx,)))lx, 1(6(2), (()rs, (0r 2 ( oz) - -((,, be)) 0%).
(0) -0i)
where the first inequality holds due the triangle inequality. The second inequality holds due to E and the Schwary inequality. Let ii = max (k. ai {.)]- Using the fact that d--) is even function decreasing when > 0, we have 2 S ((0(zz)))) ((z,,,))) 07. Therefore, we have A, = Hμ. As a result, (D.10) indicates that
1 0.112.. $ - 1.1.
< (1 + (0) - (,)
Using (D.8), we have
|10" OillA, $ (1+4B)|G, -G(o))l,a,
$ (1 4B))
VXB+ + Vī + dlog
2
(d) 21
+
dlog(118)+ ac
VX
dd
Vx
Be.
Taking a union bound, we complete the proof of Lemma C.I.
E
Experiments
In this section, we conduct simulation experiments to verify our theoretical results.
E.1 Experiment Setup
Preference Model. We study the effect of adversarial feedback with the preference model determined by (3.1), where (x) = 1/(1 + + We randomly generate the underlying parameter [-0.5, 0.5] and normalize it to be vector with |10|1|2 2. Then, we set be the underlying parameter and construct the reward utilized in the preference model as r"(x,a) = (0", Φ(I, a)). We set the action set A = (- 1/Vd, 1/ 1/va]* d For simplicity, we assume (2z a) = In our experiment, we set the dimension d = 5, with the size of action set |A|| = 2d = 32.
Adversarial Attack Methods. We study the performance of our algorithm using different adversarial attack methods. We categorize the first two methods as "weak" primarily because the adversary in these scenarios does not utilize information about the agent's actions. contrast, we classify the latter two methods as "strong" attacks. In these cases, the adversary leverages a broader scope of information, including knowledge of the actions selected by the agent and the true preference model. This enables it to devise more targeted adversarial methods.
"Greedy Attack": The adversary will flip the preference label for the first C rounds. After that, it will not corrupt the result anymore.
In each round, the adversary will flip the preference label with the probability 0 < < < 1, until the times adversarial feedback reach C.
"Random Attack":
"Adversarial Attack": The adversary can have access to the true preference model. It will only flip the preference label when aligns with the preference model, i.c., the probability for the preference model to make that decision is larger than 0.5, until the times of adversarial feedback reach C.
"Misleading Attack": The adversary selects a suboptimal action. It will make sure this arm is always the winner in the comparison until the times adversarial feedback reach C. In this way, it will mislead the agent to believe this action is the optimal one.
30

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
Greedy Attack
Random Attack
Maxinp
4000
Maxinp CoLSTIM
3500
CoLSTIM
ManPairUCB
MaxPairUCB
3000
RCDB-5
3000
RCDB-5
2500
2000
1500
1500
1000
500
500
0
250
500
750
1000
1250
1500
1750
2000
0
250
500
750
1000
1250
1500
1750
2000
(a) Greedy Attack
Random Attack
Misleading Attack
6000
Maxinp
4000
Maxinp
COL.TTM MaxPairUCB RCDB RCDB-S 5
CoL.
3500
MaxPairUCB
5000
RCDB
RCDB 5
4000
2500
3000
2000
1000
0-
0-
250
500
750
1000
1250
1500
1750
2000
250
500
750
1000
1250
1500
1750
2000
(c) Adversarial Attack
(d) Misleading Attack
Figure 1. Comparison of RCDB (Our Algorithm 1). MaxInp (Saha, 2021). CoLSTIM (Bengs et al., 2022) and MaxP airE (Di al., 2023). We report the cumulative regret with various adversarial attack methods (Greedy, Random, Adversarial. Misleading). For the haselines, the parameters are carefully tuned to achieve better results with different attack methods. The total number adversarial feedback is C [-T].
Experiment Setup. For each experiment instance, simulate the interaction with the enviromment for T 2000 rounds. In each round, the feedhack for the action pair selected by the algorithm is generated according the defined preference model. Subsequently, the adversary observes both the selected actions and their corresponding feedback and then engages in one of the previously described adversarial attack methods. We report the cumulative regret averaged across 10 random runs.
E.2 Performance Comparison
first introduce the algorithms studied in this section.
MaxInP: Maximum Informative Pair by Saha (2021). It involves maintaining standard MLE. With the estimated model, it then identifies a set of promising arms possible to beat the rest. The selection of arm pairs is then strategically designed maximize the uncertainty the difference between the two arms within this promising set, referred to as "maximum informative".
CoLSTIM: The method by Bengs et al. (2022). It involves maintaining standard MLE for the estimated model. Based on this model, the first arm is selected as the one with the highest estimated reward, implying it is the most likely to prevail over competitors. The second arm is selected to be the first arm's 's toughest competitor, with an added uncertainty bonus.
MaxP airUBB: This algorithm was proposed in Di et al. (2023). It uses the regularized MLE to estimate the parameter 0". Then selects the actions based on symmetric action selection rule, i.e. the actions with the largest estimated reward
31

---

Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback
plus some uncertainty bonus.
RCDB: Algorithm proposed in this paper. The key difference from the other algorithms the use of uncertainty weight in the calculation of MLE (4.4). The use the same symmetric action selection rule MaxPai LaxPairUCE, OCB. Our experiment results show that the uncertainty weight is critical in the face of adversarial feedback.
Our results are demonstrated in Figure 1. In Figure ((a) and Figure 1(b), we observe scenarios where the adversary is "weak" due to the lack of access to information regarding the selected actions and the underlying preference model. Notably, in these situations, our algorithm RCDB outperforms all other baseline algorithms, demonstrating its robustness. Among the other algorithms, COLSTIM performs as the strongest competitor.
In Figure I(c), the adversary employs a 'stronger' adversarial method. Due to the inherent randomness of the model, some labels may naturally be 'incorrect'. An adversary with knowledge of the selected actions and the preference model can strategically neglect these naturally incorrect labels and selectively flip the others. This method proves catastrophic for algorithms to learn the true model, as results the agent encountering only incorrect preference labels the beginning. Our results indicate that this leads to significantly higher regret. However, it's noteworthy that our algorithm RCDB demonstrates considerable robustness.
In Figure (dd), the adversary employs a strategy aimed at misleading algorithms into believing a suboptimal action the best choice. The algorithm COLSTIM appears to be the most susceptible to being cheated by this method. Despite the deployment of 'strong' adversarial methods, as shown in both Figure I(c) and Figure 1(d), algorithm, RCDB, consistently demonstrates exceptional robustness against these attacks. A significant advantage of RCDB lies in that our parameter is selected solely based on the number of adversarial feedback C, irrespective of the nature of the adversarial methods employed. This contrasts with other algorithms where parameter tuning must be specifically adapted for each distinct adversarial method.
Cumulative Regret versus Adversarial Feedback
35.00
COLSTIN
NaxFarUCe
RCDB
3000
25:00
Rogres
2000
1500
1000
500
Adversarial Feedback
Figure 2. The relationship between cumulative regret and the number of adversarial feedback C. For this specific experiment, employ the "greedy attack" method to generate the adversarial feedback. is selected from the set [20, 40, 60, 80, 100, 120, 140, 160, 180, 200] (10 adversarial levels).
E.3 Robustness to Different Numbers of Adversarial Feedback
In this section, we test the performance of algorithms with increasing times of adversarial feedback. As shown in Figure our algorithm has a linear dependency on the number of adversarial feedback C, which consistent with the theoretical results we have proved in Theorem 5.3. In comparison to other algorithms, RCDB demonstrates superior robustness against adversarial feedback, as evidenced by its notably smaller regret.
F Auxiliary Lemmas
Lemma F.1 (Azuma-Hoeffddin inequality, Cesa-Bianchi & Lugosi 2006). Let {m be martingale difference sequence with respect to filtration (Fi) satisfying Ind S R for some constant R, n) is Feas-maasra,bl,, E[ [F] 0. Then for any 0 < < 1, with probability at least 1 - 8, we have
T
Σ t=1
The S RV 2T log 1/8.
Lemma E2 (Lemma Abbasi- Yadkori et 2011). Let { be real-valued stochastic process with corresponding
32

---

Nearly Optimal Algorithms for Contextual Ducling Bandits from Adversarial Feedback
filtration (Fitzo such that e, is Fe-measurable and e, conditionally R-sub-Gaussian, i.e.
E E Fr- exp (>)
x² ^²
Let {x+)r=) be an -aluuee stochastic process where X; is Fi-1-measurabl and for any t E (T), we further define
n, A Ei=1 x,x," Then with probability at least 1 - 6, for all E [T], we have
1/2 det (Eo) -1/2
Σ
2 log
X
8
Σ
Lemma E.3 (Lemma 11, Abbasi- Yadkori et al. 2011). For any > and sequence {x+]==1 S Rd for E [T], define
Z, = Al + Ex x,x Then, provided that ||x||2 S L holds for all / E [T], we have
min 1, |xx 2,2 2- } 2d /d2)
Lemma F.4 (Theorem in Faury al. 2020). Let {Fiji= be filtration. Let {x:}i= be stochastic process, such that x; is F--maauurabl.. Suppose |xx |l2 s 1. Furthermore, let { J be stochastic process which is F141-measuree Assume lal < 1. [F] = O. E[e Fil = o². Let À > 0 and for any t 2 define:
H. x + AI
Then with probability at least 1 - 8, for all & [T]. we have
Σ
X
V
2
log
det ( d/2
+
dloo(().
V
8
Ví
H
Lemma F.5 (Lemma 7 in Abeille et al. 2021). Let f' be a strictly increasing function such that [Ji s f. and let be any bounded interval of R. Then, for all ž1, 22 E I, the following inequality holds:
L (a - v(22 =))dv 2 1+ 21 22
f(2)
for E (21,
33


Reviews:
[{"review_id": "8jY0QUmjyX", "reviewer": "Reviewer_TxSJ", "summary": "The paper studies the contextual dueling bandits with adversarial feedback, where a strong adversary may manipulate the preference label to mislead the agent, and the number of adversarial feedback is bound by $C$.\nThe authors propose an algorithm named RCDB to solve the problem. RCDB utilizes uncertainty-weighted maximum likelihood estimation (MLE) to reduce the effect of adversarial feedback.\nThe authors provide the regret upper bounds for both known and unknown $C$ and show the proposed regret bound is nearly minimax optimal with a lower bound.\nThe authors also present the RCDB-S algorithm for the sigmoid link function and provide an improved regret bound.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We will address your concerns one by one.\n\n**Q1**: mismatch between motivation and model: the reward function is assumed to be linear, which oversimplifies the complex, high-dimensional reward structures typically used in LLM training\n\n**A1**: \nWe believe that our motivation closely aligns with our contextual dueling bandit model, as the core challenge we address—effectively learning from preference feedback—is central to RLHF settings. Specifically, our model shares the same conceptual pipeline commonly used in RLHF: optimizing a reward function followed by applying a link function (such as the Bradley-Terry model) to derive preference scores. For clarity of representation, we focus on the linear reward function class, so as not to distract from our main contribution: addressing the challenges posed by adverarial preference feedback. This assumption is both standard and widely adopted in the literature [1–3]. \nMoreover, it's straightforward to extend our techniques to more general nonlinear reward function classes [4][5]. We have discussed this in the future direction part.\n\n[1] Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons, Zhu et al. 2023, ICML2023\n\n[2] Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint Xiong et al. 2024 ICML2024\n\n[3]  Value-incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF Cen et al.2025 ICLR2025\n\n[4] Corruption robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes. Ye et al. 2023, ICML2023\n\n[5] Feel-good thompson sampling for contextual dueling bandits Li et al. 2024 ICML2024\n\n---\n\n**Q2**: Relation with He et al. (2022) and Di et al. (2023)\n\n**A2**: \nFirst, Reviewer TxSJ claims that our work builds heavily on He et al. (2022), particularly in the extension to the unknown $C$ scenario, thus limiting our contribution. However, we clarify that this aspect represents only a minor section of our overall work. We incorporate this analysis, with explicit reference to He et al. (2022), primarily to demonstrate completeness to highlight that our proposed algorithm remains optimal even when $C$ is unknown, provided we select $\\bar{C} = O(\\sqrt{T})$. Including this discussion enhances, rather than diminishes, the significance and completeness of our work.\n\nSecond, we acknowledge that weighted MLE has been previously explored by Di et al. (2023). However, we emphasize that both the selection of the weights and the intended purposes differ significantly from that work. Specifically, Di et al. (2023) select weights as $\\alpha/||\\phi_t|| _ {\\Sigma_t^{-1}}^{2}$ to achieve a variance-aware regret bound. In contrast, our weight choice is $w_t = \\min \\lbrace 1, \\alpha/||\\phi_t|| _ { \\Sigma_t^{-1}} \\rbrace$ (equation 4.3, Line 235), strategically designed to cancel out the uncertainty. More precisely, our choice allows the equality $w_t ||\\phi_t||_{\\Sigma_t^{-1}} \\alpha = 1$ when $w_t \\le 1$ (Lines 663-672), effectively reducing the dependence on $T$ in the corruption term from $O(\\sqrt{T})$ to $O(\\log(T))$. This crucial difference highlights that our analytical goal and results are novel contributions distinct from those presented by Di et al. (2023).\n\nLast but not least, the reviewer overlooks several significant contributions of our work. To be more specific, through a more detailed analysis of the impact of $\\kappa$ on the MLE, we identify the critical role of local derivatives and introduce a novel refined covariance matrix $\\Lambda_t = \\lambda I + \\sum w_i v_i \\phi_i \\phi_i^\\top$, where $v_i$ serves as an optimistic estimator of the local derivative (Lines 388-389). With our analysis, the \"correct\" weight ideally should be $\\dot \\sigma(\\phi_i^\\top \\bar{\\theta})$ (Line 348), where $\\bar \\theta$ is an intermediate value between $\\theta^*$ and $\\theta_t$. One might consider approximating this weight using either $\\dot \\sigma(\\phi_i^\\top \\theta^*)$ or $\\dot \\sigma(\\phi_i^\\top \\theta_t)$ directly. However, both direct approaches encounter critical issues: the first relies on the unknown parameter $\\theta^*$, preventing us from applying the bonus term in Line 10 of Algorithm 2; the second fails due to the covariance matrix $\\Lambda_t = \\lambda I + \\sum \\dot\\sigma(\\phi_i^\\top \\theta_t) \\phi_i\\phi_i^\\top$ depending on varying $\\theta_t$, thus causing the matrix to not be monotonically increasing with $t$, posing significant analytical difficulties. Therefore, we propose constructing the weight $v_t$ as a carefully designed lower bound of the ideal weight. To the best of our knowledge, this specific technique has not appeared in prior logistic, adversarial, or dueling bandit literature.", "claims_and_evidence": "All claims are well-supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem.", "theoretical_claims": "I have not checked all the proofs in detail. I did not identify any obvious errors.", "experimental_designs_or_analyses": "The paper compares the proposed algorithm against several existing methods, such as MaxInP, CoLSTIM, and MaxPairUCB. \nThese comparisons are conducted using the cumulative regret metric, which is a standard metric in contextual bandits literature. \nThe relationship between cumulative regret and the number of adversarial feedback $C$ is evaluated.", "relation_to_broader_scientific_literature": "The paper is closely related to He et al. (2022) and Di et al. (2023). He et al. (2022)  study the problem of linear bandits with adversarial corruption, where weighted linear regression is used to deal with corruption, and Di et al (2023) study weighted maximum likelihood estimation.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n\n1. The problem of contextual dueling bandits with adversarial attacks is important.\n2. Theoretical analysis shows that the regret is nearly minimax-optimal.\n3. Empirical results show the performance of RCDB over existing dueling bandit algorithms in the presence of adversarial feedback.\n4. The paper is well organized and all assumptions are clearly listed. \n\nWeaknesses:\n\n1. There is a mismatch between motivation and model. Although linear contextual dueling bandits are important and interesting, the authors motivate their setting by training LLM using RLHF. However, the reward function is assumed to be linear, which oversimplifies the complex, high-dimensional reward structures typically used in LLM training.\n2. The paper builds heavily on the prior work of He et al. (2022), particularly in extending results to the **unknown** $C$, and using the argument that no algorithm can simultaneously achieve near-optimal regret when uncorrupted and maintain sublinear regret when  $C=\\Omega(\\sqrt{ T })$. This limits the contribution of this paper.\n3. The weighted MLE to estimated $\\theta$ has been studied by Di et al. (2023), where an auxilliary function are introduced.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": {"ethical_review_concerns": "N/A"}}, {"review_id": "8D4F9HYtME", "reviewer": "Reviewer_t957", "summary": "The paper considers the adversarial corruption setup in Dueling bandits and proposes an algorithm using the uncertainty-weighted maximum likelihood estimation and provides regret bounds and empirical evaluations.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback! We will address your concerns.\n\n**Q1**: Direct extension of He et al. 2022 using standard analysis techniques from the Duelling Bandits\n\n**A1**: We believe that the reviewer overlooks several significant contributions in our work. First, we carefully analyze the dependency on $\\kappa$ in Theorems 5.3 and 5.4. We introduce a new algorithm that achieves an $O((d\\sqrt{T} + dC)/\\kappa)$ regret bound. Furthermore, Theorem 5.4 establishes a matching lower bound, demonstrating that our result is optimal with respect to all involved parameters $d,T,C,\\kappa$. Specifically, a $O(1/\\kappa)$ dependency is both necessary and sufficient under the general assumption 3.2.\n\nNext, in Section 6, we illustrate how this dependency can be improved when considering specific link functions, such as the logistic function. To be more specific, through a more detailed analysis of the impact of $\\kappa$ on the MLE, we identify the critical role of local derivatives and introduce a novel refined covariance matrix $\\Lambda_t = \\lambda I + \\sum w_i v_i \\phi_i \\phi_i^\\top$, where $v_i$ serves as an optimistic estimator of the local derivative (Lines 388-389). With our analysis, the \"correct\" weight ideally should be $\\dot \\sigma(\\phi_i^\\top \\bar{\\theta})$ (Line 348), where $\\bar \\theta$ is an intermediate value between $\\theta^*$ and $\\theta_t$. One might consider approximating this weight using either $\\dot \\sigma(\\phi_i^\\top \\theta^*)$ or $\\dot \\sigma(\\phi_i^\\top \\theta_t)$ directly. However, both direct approaches encounter critical issues: the first relies on the unknown parameter $\\theta^*$, preventing us from applying the bonus term in Line 10 of Algorithm 2; the second fails due to the covariance matrix $\\Lambda_t = \\lambda I + \\sum \\dot\\sigma(\\phi_i^\\top \\theta_t) \\phi_i\\phi_i^\\top$ depending on varying $\\theta_t$, thus causing the matrix to not be monotonically increasing with $t$, posing significant analytical difficulties. Therefore, we propose constructing the weight $v_t$ as a carefully designed lower bound of the ideal weight. To the best of our knowledge, this specific technique has not appeared in prior logistic, adversarial, or dueling bandit literature.\n\nFinally, applying our new technique, we can remove the $\\kappa$ dependency in the leading term of the regret upper bound, a result that has never been obtained in previous works for dueling bandits, even in the non-corrupted case. Thus, we firmly believe our contributions are substantial and that it is unfair to claim our work lacks novelty", "claims_and_evidence": "Yes all theoretical claims have proofs and experimental results are provided.", "methods_and_evaluation_criteria": "Methods And Evaluation Criteria are fair.", "theoretical_claims": "None of the theoretical claims are proven in the main body of the paper.", "experimental_designs_or_analyses": "The experimental designs are fair. However, they are on synthetic data and therefore are fairly limited and therefore the authors' description \" We conduct extensive experiment\" seems a bit exaggerated.", "relation_to_broader_scientific_literature": "The contribution would be useful to the bandits/ sequential learning community.", "essential_references_not_discussed": "All essential references have been discussed.", "other_strengths_and_weaknesses": "Weakness:\n\n* The main contribution of the paper seems to be a direct extension of the algorithm developed in He et al 2022 for the linear bandit setup to the dueling bandit framework, uses the standard machinery from the dueling bandit literature, and as such lacks novelty.", "other_comments_or_suggestions": "-", "questions_for_authors": "* Since this seems to be a direct extension of He et al 2022 using standard analysis techniques from the Duelling Bandits literature, could the authors describe novel aspects of their contribution in relation to existing literature.\n\n* The contribution in Section 6 seems to be novel and provides tighter results for the Sigmoid Link function. Are there existing papers that analyze this special case for the non-corrupted case?", "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": "uOb0QdmFvr", "reviewer": "Reviewer_Jfpo", "summary": "The paper considers the problem of average regret minimization in stochastic contextual dueling bandits under the linear transitivity model and *strong* corruption. The authors first propose RCDB, a robustified version of MaxInP (Saha, 2021) that computes a weighted MLE, and proves its regret bound of $\\widetilde{O}(d(\\sqrt{T} + C)/\\kappa)$, where $\\kappa$ is some curvature-dependent, problem difficulty quantity. This regret holds when $C$ is known or unknown; in the latter case, $C$ can be replaced with $\\overline{C}$, an adversarial tolerance threshold. This is complemented with a lower bound that holds for a piecewise linear link function, for which the optimality of RCDB in $d, C, T, \\kappa$ follows. When the link function is sigmoidal, the authors propose RCBD-S, an improved version of RCDB that more effectively utilizes the local derivative information of sigmoids. This leads to an improved guarantee of $\\widetilde{O}(d \\sqrt{T} + dC/\\kappa + d^2 / \\kappa^2)$, where the leading term is $\\kappa$-free, the first result to show such improvement in contextual dueling bandits literature. The efficacy of the algorithms is shown numerically as well.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback! We will address your questions one by one.\n\n**Q1**:  Typos and suggestions\n\n**A1**: Thank you for pointing these out. We will address them in our next revision.\n\n---\n\n**Q2**: The writing of lower bound\n\n**A2**: There seems to be a misunderstanding regarding our claim about the lower bound. Our established lower bound works for the general class of link functions constrained only by Assumption 3.2. Within this general class, we construct a piecewise-linear example to establish the lower bound of $\\Omega((d\\sqrt{T} + dC)/\\kappa)$. This bound matches the upper bound achieved by our RCDB algorithm, which operates under the same general Assumption 3.2. Consequently, our algorithm is minimax optimal in this general scenario. As explicitly noted at the beginning of Section 6, when we move beyond the general assumption, focusing on specific link functions (e.g., sigmoid function), we show that it is possible to achieve improved dependency on $\\kappa$.\n\n---\n\n**Q3**: Relation with Jun et al. (2021)\n\n**A3**:  Jun et al.(2021) considered the logistic bandit problem with pure exploration and proposed an algorithm with a sample complexity guarantee. In contrast, our work focuses on the regret of dueling bandits, with the approach involving reward estimation complemented by a bonus term.\n\nFurthermore, Jun et al. (2021) derived a concentration inequality under a fixed design assumption, given by $|\\langle x, \\hat{\\theta} - \\theta^* \\rangle|\\leq\\beta||x|| _ {H_t(\\theta^*)^{-1}}$. However, this assumption is too restrictive for our setting with adaptive action selection. Therefore, we establish a concentration inequality applicable to adaptive designs that holds for any arm $x$ ($\\mathcal{E} _ 2$ in Line 1054), which works for the adaptive arm-selection inherent to bandit algorithms. \nWe will explicitly discuss this comparison with Jun et al.. (2021) in the revised version.\n\n---\n\n**Q4**: The combination of ideas and techniques from logistic bandits, adversarial bandits, and dueling bandits is also a minor weakness\n\n**A4**: We'd like to mention that besides integrating concepts from logistic bandits, adversarial bandits, and dueling bandits, we propose a novel idea of a well-constructed weight $v_t$ (Line 15 of Algorithm 2), representing a significant contribution. For a detailed discussion, please refer to **A2** to Reviewer TxSJ due to space constraints of the rebuttal.\n\n---\n\nWe will next address your ''questions for authors'' part.\n\n**Q5**: Correct $\\kappa$\n\n**A5**: The \"correct\" $\\kappa$ for logistic bandits is exactly given by $\\kappa^*=1/\\dot \\sigma(x _ * ^\\top\\theta ^*)$, where $x_ * =\\text{argmax }x^\\top\\theta^*$. As the analogy, the corresponding $\\kappa$ in the dueling bandit setting should be $\\kappa^* = 1/\\dot \\sigma(x_* ^\\top \\theta^*-x _ * ^\\top\\theta^*) $, with $x_* = \\text{argmax } x^\\top \\theta^*$. It is a constant and it's exactly what we use. This difference stems from the nature of dueling bandits, which require **both** arms to approach optimality, unlike standard logistic bandits that involve only one arm. Indeed, if we define $\\kappa^*$ explicitly as $\\max_x \\max_{a,b}1/\\dot \\sigma((r^*(x,a) - r^*(x,b))$, this corresponds precisely to the inverse of the $\\kappa$ presented in Assumption 3.2, leading to a worse regret bound similar to that of Theorem 5.3.\n\n---\n\n**Q6**: Referring the reader to Appendix A of Di et al. (2023)\n\n**A6**: We apologize for the earlier typos. We intended to refer to Appendix C of Di et al. (2023), which discussed different arm-selection rules involving the selection of two arms. As this aspect has already been studied and is not the central contribution of our algorithm, we have included a reference for readers seeking a detailed discussion. \n\n---\n\n**Q7**: Local minimax lower bound\n\n**A7**: It is possible to establish a local minimax lower bound. In our current proof, we consider the parameter set $\\Theta = \\lbrace -\\Delta, \\Delta \\rbrace^{d}$ (Line 693). If we instead focus on a local parameter class such as $\\Theta = \\theta^* + \\lbrace -\\Delta, \\Delta \\rbrace^{d}$, similar to the approach in Abeille et al. (2021), we believe that a local minimax lower bound can be derived. \n\n---\n\n**Q8**: Extend the analysis to self-concordant link function\n\n**A8**: We believe our analysis can be extended to the self-concordant setting, although this extension requires some additional nontrivial effort. Specifically, regarding the part mentioned by the reviewer where we apply properties of the logistic function, we could instead leverage a Taylor expansion to achieve similar results. For example, in lines 1210–1220, we can derive $\\frac{1}{\\dot \\sigma(\\hat \\Delta_t)} \\le \\frac{1}{\\dot \\sigma(0)} + \\int_0^{\\hat \\Delta_t} \\frac{|\\ddot \\sigma(s)|}{|\\dot \\sigma^2(s)|} ds$. Then, utilizing the self-concordance property, we can bound the integral term by $\\hat\\Delta_t R_s/\\kappa$. allowing the subsequent steps in our proof to proceed similarly.", "claims_and_evidence": "See my comments on Theoretical Results and Experiments", "methods_and_evaluation_criteria": "See Experimental Designs or Analyses", "theoretical_claims": "I checked all proofs and concur that they are generally correct. There are very minor issues that I list below, but they do not harm the theoretical claims in any way:\n1. Line 666: $\\leq$ => $=$\n2. Line 687: $0$ if $x < -1/2$\n3. Line 735: missing $1/2$ in the $\\sqrt{}$ from Pinsker's inequality\n\nAlso, the lower bound (Theorem 5.4) and the following paragraph should be written more clearly to avoid any misunderstanding. The lower bound is only for the specific form of piecewise-linear linear function, and thus, RCDB is (minimax) optimal *only* for that link function.", "experimental_designs_or_analyses": "The experimental designs seem appropriate. Some minor comments:\n1. Figure 2 is never referenced explicitly in the text.\n2. Error bars missing from Figure 2.", "relation_to_broader_scientific_literature": "- To the best of my knowledge, it tackles a new problem setting of contextual dueling bandits with adversarial corruptions.\n- Integrates three lines of works (logistic bandit, dueling bandit, bandits with adversarial corruption)", "essential_references_not_discussed": "To my knowledge, no *essential* references were left out. \n\nAlthough slightly different, please consider discussing Jun et al. (2021), where a $\\kappa$-free confidence bound for $|\\langle x, \\hat{\\theta} - \\theta_\\star \\rangle|$ was proved under a fixed design. This seems relevant to the $\\Lambda_t$-based confidence sequence that the authors prove in Appendix C (event $\\mathcal{E}_2$).\n\n\nhttps://proceedings.mlr.press/v139/jun21a.html", "other_strengths_and_weaknesses": "**Strengths:**\n1. Clearly and well written\n2. The dependencies on all the problem-dependent quantities are well-tracked. This includes $d, T, \\kappa, B$.\n3. Nontrivial combination of ideas and techniques from logistic bandit (Abeille et al., 2021), adversarial bandits (He et al., 2022), and dueling bandits (Saha, 2021), especially RCDB-S where several (new) properties of sigmoid were used in conjunction with the mentioned techniques\n\n**Weaknesses:**\n1. Strength #3 is also partially a weakness, but not a huge one.", "other_comments_or_suggestions": "**Suggestions:**\n1. I think it would be better to move footnote 1 to the main text.\n2. Although all relevant citations are included, I still believe that they should be appropriately cited when needed. For instance,\n   - At the end of Section 4, the authors should mention that the precise form of estimated reward + exploration bonus for dueling bandits is basically MaxInP of Saha (2021)\n   - The Taylor expansion argument combined with self-concordance (e.g., Section 6.1), as well as the self-bounding equation (e.g., last part of the proof of Theorem 6.1), were pioneered by Abeille et al. (2021).\n   - It seems that the overall proof flow of Theorem 5.4 resembles the lower bound proof of Li et al. (2024)\n3. There is no mention of experiments nor its location in the main text. The authors should mention somewhere that they have provided extensive numerical experiments in Appendix E.\n4. Theorem 5.5 (and Sec 5.2 in general) seems redundant with Section 5.1. \n5. It would be helpful to put in the citation/exact reference for the averaging hammer in Line 792, e.g., Section 24.1 of Lattimore & Szepesvari (2020).\n6. Another interesting future work that I ask the authors to consider putting in would be making the algorithm more efficient in the sense that MLEs do not get computed at every iteration [1,2,3] or use hashing [4].\n7. For the proof of the lower bound, the authors define a stopping time $\\tau_i$ and some function $U_{\\theta,i}(x)$ similar to Li et al. (2024). Some intuition would be nice on what these two quantities mean. I understood $\\tau_i$ as the first time $\\tau$ in which the amount of information gathered for coordinate $i$ til time $\\tau$ (quantified as the sum of squares of the $i$-th coordinates of the chosen arms) exceeds the average? amount of information expected, which is $2T/d$ ($T/d$ per coordinate times 2). I understood $U_{\\theta,i}(x)$ as the lower bounding term that pops up when lower bounding the average dueling regret. Are my intuitions correct?\n\n\n**Typos:**\n1. Line 231 (right column): What are the \"first\" and \"last\" inequalities?\n2. Line 233 (right column): $\\geq$ => $\\succeq$\n3. Line 965: equalties => equalities\n\n\n[1] https://openreview.net/forum?id=FTPDBQuT4G\n\n[2] https://openreview.net/forum?id=ofa1U5BJVJ\n\n[3] https://proceedings.mlr.press/v151/faury22a.html\n\n[4] https://papers.nips.cc/paper_files/paper/2017/hash/28dd2c7955ce926456240b2ff0100bde-Abstract.html", "questions_for_authors": "1. In logistic and GLM bandit literature, the \"correct\" kappa is $\\kappa_\\star = \\frac{1}{\\dot{\\sigma}(\\langle x_\\star, \\theta_\\star \\rangle)}$. Indeed, to me, both the upper and lower bounds for the considered dueling bandits setting should depend on something like $\\kappa_\\star = \\max_{x \\in \\mathcal{X}} \\max_{a, b \\in \\mathcal{A}} \\frac{1}{\\dot{\\sigma}\\left( r^*(x, a) - r^*(x, b) \\right)}$. Given that the proofs utilize Taylor expansion of $\\sigma(\\phi^\\top \\theta)$ about $\\theta = \\theta_\\star$ as in Abeille et al. (2021), I strongly believe that the current analysis can be (somewhat easily) improved. If I am missing something, please let me know! \n2. At the end of Section 4, what is the authors' intention for referring the reader to Appendix A of Di et al. (2023) in the current context? Appendix A of Di et al. (2023) seems to be regarding the layered version of MaxInP for variance-aware regret guarantees. Is it to allude that a similar variance-aware guarantee can also be obtained in the adversarial dueling setting? If this is the intention, it should be made more explicit.\n3. I am curious about whether one can use similar techniques from Abeille et al. (2021) to show a *local* minimax lower bound, i.e., given some instance $\\theta_\\star$, there exists another $\\theta_\\star'$ in its neighborhood such that .... Similarly, I wonder whether one can show a local minimax lower bound of $\\Omega(d \\sqrt{T} + ...)$ for sigmoidal $\\sigma$. These two points would have made the paper much stronger in my opinion.\n4. The proof of RCDB-S seems to use properties highly specific to sigmoid (e.g., Line 1165-1172, Line 1210-1220). In general, can the similar algorithm principle and analysis be extended to $\\sigma : \\mathbb{R} \\rightarrow [0, 1]$ is a link function that is 1. monotone increasing, 2. $\\sigma(z) + \\sigma(-z) = 1$, and 3. self-concordant (i.e., $|\\ddot{\\sigma}| \\leq R_s \\dot{\\sigma}$)?\n5. For constructing the weighted confidence sequence, could one obtain further improvements in factors of $B$ via the likelihood-based confidence sequences of [1,2,3]? If yes, I would suggest including this as a potential future direction as well.\n\n\n[1] https://openreview.net/forum?id=4anryczeED\n\n[2] https://proceedings.mlr.press/v238/lee24d.html\n\n[3] https://openreview.net/forum?id=MDdOQayWTA", "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": "7jLaV7GjdU", "reviewer": "Reviewer_X3W6", "summary": "This paper addresses the problem of adversarial attack in contextual dueling bandits. The authors propose a new algorithm (RCDB) that integrates uncertainty-weighted maximum likelihood estimation to mitigate the impact of adversarial feedback. They obtain a near-optimal regret bound that is robust to adversarial feedback. Moreover, the authors develop an enhanced variant (RCDB-S) that eliminates exponential dependencies. Empirical evaluations confirm the superiority of the proposed methods over existing algorithms under various adversarial conditions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback! We will address your concerns.\n\n**Q1**: Empirical results for RCDB-S\n\n**A1**: We will add the empirical results for RCDB-S in our revision. As an example, the performance under the greedy attack setting (as described in Section E.1) is summarized in the table below. Compared to RCDB, RCDB-S performs similarly or slightly worse in the early rounds (e.g., at t=500,1000). This is consistent with our theoretical analysis, where RCDB-S incurs a larger corruption term of  $\\tilde O(dBC/\\kappa)$ (along with some other lower order terms), compared with $\\tilde O(dC/\\kappa) $ of RCDB. As $t$ increases, RCDB-S gradually outperforms RCDB due to its improved dependence on the dominant term in $T$ of $\\tilde O(d\\sqrt{T})$. \nTheoretically, as discussed in Section 6.1, our algorithm relies on the local derivative, which starts close to the lower bound $\\kappa$ and gradually increases toward a constant during the learning process. This creates a growing gap between the current local derivative and the initial lower bound $\\kappa$. As the number of rounds $T$ grows, this gap widens, and the difference between the two methods becomes more significant. As a result, the regret growth of RCDB-S slows down significantly over time—for instance, between $t=1500$ and $t=2000$, its regret increases by only 11.1, compared to 64.9 for RCDB—demonstrating its increasingly improved performance in later stages.\nThis further explains the improved performance as $t$ increases. Therefore, our experimental results are well aligned with the theoretical findings.\n\n| |  t = 500 | t = 1000 | t = 1500 | t = 2000|\n| ----------|------------|------------|------------|------------|\nRCDB |  547.0 | 642.2 | 713.8 | 778.7|\nRCDB-S|  556.4 | 642.7| 680.1| 691.2|\n\n---\n\n**Q2**: Heuristics to approximate the adversarial corruption level\n\n**A2**: The adversarial corruption level inherently depends on the environment. In extreme cases, it can become arbitrarily large, inevitably causing any algorithm to fail. Therefore, attempting to approximate the corruption level $C$ precisely is generally not meaningful. A practical and theoretically justified heuristic, as discussed in Section 5.2, is to set $C = O(\\sqrt{T})$. Adopting this heuristic choice ensures theoretical optimality, and our simulation experiments demonstrate its good empirical performance.\n\n---\n\n**Q3**: Eliminate the $\\kappa$-dependence for weak regret\n\n**A3**: We are not entirely clear on the definition of weak regret, as mentioned in your question. Could you please clarify its meaning? We will address your questions in the discussion that follows.", "claims_and_evidence": "The overall claims in the paper are clear and well-supported by both theoretical analysis and empirical results.", "methods_and_evaluation_criteria": "Overall, the proposed methods are well-suited to the addressed problem setting. \nHowever, there are practical concerns since the algorithm requires knowledge of both parameters $C$ and $\\kappa$, which are typically hard to determine in practice. The authors do discuss scenarios with an unknown number of adversarial attacks; however, if the true $C$ exceeds the adversarial tolerance threshold, performance can degrade significantly. Moreover, the first algorithm (RCDB) is  highly rely on the method proposed in He et al. 2022. \n\nOn a positive note, the second proposed method (RCDB-S) is particularly interesting, as it is the first to eliminate the dependency on $\\kappa$ in the regret bound for contextual dueling bandits.", "theoretical_claims": "The theoretical claims are well-reasoned, and the proofs appear to be correct", "experimental_designs_or_analyses": "The empirical results for the second algorithm (RCDB-S) are missing. It would be helpful if the authors included experiments to clearly demonstrate the practical advantages and performance improvements of RCDB-S compared to RCDB and other existing methods.", "relation_to_broader_scientific_literature": "I find the $\\kappa$-independent regret bound particularly intriguing, as it represents a significant theoretical improvement and clearly differentiates this work within the broader literature on contextual dueling bandits.", "essential_references_not_discussed": "I think the paper covers the related work quite thoroughly.", "other_strengths_and_weaknesses": "No other comments.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "1. Can the authors provide empirical results for RCDB-S? How does its practical performance compare with RCDB and other baseline methods?\n\n2. Are there practical methods or heuristics to estimate or approximate the adversarial corruption level $C$, instead of assuming it's known in advance?\n\n3. If the regret definition is changed to \"weak regret,\" is it still possible to eliminate the $\\kappa$-dependence from the regret bound?", "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:

Meta-review: The paper considers contextual dueling bandits with adversarial attacks. This is an important problem in the bandit literature. There were initially some concerns with parts of the paper but they were resolved during the author-reviewer rebuttal period and several reviewers raised their score accordingly, pointing to some novel techniques. Hence, I'm happy to recommend the paper to be accepted. Please take reviewers' comments into consideration when preparing the final version.
Decision: Accept (poster)