Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback

## Abstract

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 bandit ( RCDB ), which is based on uncertainty-weighted maximum likelihood estimation. Our algorithm achieves an O ~ ​ ( d ​ T + d ​ C ) \widetilde{O}(d\sqrt{T}+dC) regret bound, where T T is the number of rounds, d d is the dimension of the context, and 0 ≤ C ≤ T 0\leq C\leq 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 C=0 ) adversarial feedback.
Additionally, we conduct experiments to evaluate our proposed algorithm 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.

## 1 Introduction

Acquiring an appropriate reward proves challenging in numerous real-world applications, often necessitating intricate instrumentation (Zhu et al., ) and time-consuming calibration (Yu et al., ) 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., ).
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., ) provides a problem framework that focuses on optimal decision-making 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 vulnerable to manipulation through preference label flip. Adversarial feedback can significantly increase the risk of misleading a large language model (LLM) into erroneously prioritizing harmful content, under the false belief that it reflects human preference.
Despite the significant influence of adversarial feedback, there is limited existing research on the impact of adversarial feedback specifically within the context of dueling bandits. A notable exception is Agarwal et al. (), 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 the adversary.
However, their setting has the following two limitations.
First, their study was confined to a finite-armed setting, which renders their results less applicable to modern applications such as RLHF. Second, their adversarial feedback focuses on the comparison matrix. At each round, the adversary observes the outcomes of all pairwise comparisons and then decides to corrupt some of the pairs before the agent selects the actions.
This assumption does not align well with the real-world scenario, where the adversary often flips the preference label based on the information of the selected actions.

In this paper, to address the above challenge, we aim to develop contextual dueling bandit algorithms that are 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 only decision is whether to flip the preference label or not. We highlight our contributions as follows:

- •
We propose a new algorithm RCDB, which integrates uncertainty-dependent weights into the Maximum Likelihood Estimator (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 feedback.
- •
We analyze the regret of our algorithm under at most $C$ number of adversarial feedback. Our result consists of two terms: a $C$-independent term $\widetilde{O}(d\sqrt{T})$, which matches the lower bound established in Bengs et al. () for uncorrupted linear contextual dueling bandits, and a $C$-dependent term $\widetilde{O}(dC)$. Furthermore, we establish a lower bound for dueling bandits with adversarial feedback, demonstrating the optimality of our adversarial term. Consequently, our algorithm for dueling bandits attains the optimal regret in both scenarios, with and without adversarial feedback.
- •
We conduct extensive experiments to validate the effectiveness of our algorithm RCDB. To comprehensively assess RCDB’s robustness against adversarial feedback, we evaluate its performance under various types of adversarial feedback and compare the results with state-of-the-art dueling bandit algorithms. Experimental results demonstrate the superiority of our algorithm in the presence of adversarial feedback, which corroborate our theoretical analysis.

**Table 1: Comparison of algorithms for robust bandits and dueling bandits.**
| Model | Algorithm | Setting | Regret |
| --- | --- | --- | --- |
|  | Multi-layer<br>Active Arm Elimination Race |  |  |
|  | (Lykouris et al., ) | $K$-armed Bandits | $\widetilde{O}\big(K^{1.5}C\sqrt{T}\big)$ |
|  | BARBAR |  |  |
|  | (Gupta et al., ) | $K$-armed Bandits | $\widetilde{O}\big(\sqrt{KT}+KC\big)$ |
|  | SBE |  |  |
|  | (Li et al., ) | Linear Bandits | $\widetilde{O}\big(d^{2}C/\Delta+d^{5}/\Delta^{2}\big)$ |
| Bandits | Robust Phased Elimination |  |  |
|  | (Bogunovic et al., ) | Linear Bandits | $\widetilde{O}\big(\sqrt{dT}+d^{1.5}C+C^{2}\big)$ |
|  | Robust weighted OFUL |  |  |
|  | (Zhao et al., ) | Linear Contextual Bandits | $\widetilde{O}\big(dC\sqrt{T}\big)$ |
|  | CW-OFUL |  |  |
|  | (He et al., ) | Linear Contextual Bandits | $\widetilde{O}\big(d\sqrt{T}+dC\big)$ |
|  | WIWR |  |  |
|  | (Agarwal et al., ) | $K$-armed Dueling Bandits | $\widetilde{O}\big(K^{2}C/\Delta_{\text{min}}+\sum_{i\neq i^{*}}K^{2}/\Delta_{i}^{2}\big)$ |
|  | Versatile-DB |  |  |
| Dueling Bandits | (Saha and Gaillard, ) | $K$-armed Dueling Bandits | $\widetilde{O}\big(C+\sum_{i\neq i^{*}}1/\Delta_{i}+\sqrt{K}\big)$ |
|  | RCDB |  |  |
|  | (Our work) | Contextual Dueling Bandits | $\widetilde{O}\big(d\sqrt{T}+dC$) |

Notation.
In this paper, we use plain letters such as $x$ to denote scalars, lowercase bold letters such as $\mathbf{x}$ to denote vectors and uppercase bold letters such as $\mathbf{X}$ to denote matrices. For a vector $\mathbf{x}$, $\|\mathbf{x}\|_{2}$ denotes its $\ell_{2}$-norm. The weighted $\ell_{2}$-norm associated with a positive-definite matrix $\mathbf{A}$ is defined as $\|\mathbf{x}\|_{\mathbf{A}}=\sqrt{\mathbf{x}^{\top}\mathbf{A}\mathbf{x}}$. For two symmetric matrices $\mathbf{A}$ and $\mathbf{B}$, we use $\mathbf{A}\succeq\mathbf{B}$ to denote $\mathbf{A}-\mathbf{B}$ is positive semidefinite. We use $\operatorname{\mathds{1}}$ to denote the indicator function and 0 to denote the zero vector. For two actions $a$, $b$, we use $a\succ b$ to denote $a$ is more preferable to $b$. For a postive integer $N$, we use $[N]$ to denote $\{1,2,\ldots,N\}$. We use standard asymptotic notations including $O(\cdot),\Omega(\cdot),\Theta(\cdot)$, and $\widetilde{O}(\cdot),\widetilde{\Omega}(\cdot),\widetilde{\Theta}(\cdot)$ will hide logarithmic factors.

## 2 Related Work

Bandits with Adversarial Reward.
The multi-armed bandit problem, involving an agent making sequential decisions among multiple arms, has been studied with both stochastic rewards (Lai et al., ; Lai, ; Auer, ; Auer et al., ; Kalyanakrishnan et al., ; Lattimore and Szepesvári, ; Agrawal and Goyal, ), and adversarial rewards (Auer et al., ; Bubeck et al., ).
Moreover, a line of works focuses on designing algorithms that can achieve near-optimal regret bounds for both
stochastic bandits and adversarial bandits simultaneously (Bubeck and Slivkins, ; Seldin and Slivkins, ; Auer and Chiang, ; Seldin and Lugosi, ; Zimmert and Seldin, ; Lee et al., ), which is known as “the best of both worlds” guarantee.
Distinct from fully stochastic and fully adversarial models, Lykouris et al. () studied a setting, where only a portion of the rewards is subject to corruption. They proposed an algorithm with a regret dependent on the
corruption level $C$, defined as the cumulative sum of the corruption magnitudes at each round. Their result is $C$ times worse than the regret without corruption. Gupta et al. () improved the result by providing a regret guarantee comprising two terms, a corruption-independent term that matches the regret lower bound without corruption, and a corruption-dependent term that is linear in $C$. In addition, Gupta et al. () proved a lower bound demonstrating the optimality of the linear dependency on $C$.

Contextual Bandits with Corruption.
Li et al. () studied
stochastic linear bandits with corruption and presented an instance-dependent regret bound linearly dependent on the corruption level $C$. Bogunovic et al. () studied the same problem and proposed an algorithm with near-optimal regret in the non-corrupted case. Lee et al. () studied this problem in a different setting, where the adversarial corruptions are generated through the inner product of a corrupted vector and the context vector.
For linear contextual bandits, Bogunovic et al. () 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. () and Ding et al. () extended the OFUL algorithm (Abbasi-Yadkori et al., ) and proved a regret with a corruption term polynomially dependent on the total number of rounds $T$.
He et al. () proposed an algorithm for known corruption level $C$ to remove 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 dependency on $C$ for linear contextual bandits with a known corruption level. Additionally, He et al. () extended the proposed algorithm to an unknown corruption level and provided a near-optimal performance guarantee that matches the lower bound.
For more extensions, Kuroki et al. () studied best-of-both-worlds algorithms for linear contextual bandits. Ye et al. () proposed a corruption robust algorithm for nonlinear contextual bandits.

Dueling Bandits.
The dueling bandit model was first proposed in Yue et al. (). 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, including Condorcet winner (Zoghi et al., ; Komiyama et al., ), Copeland winner (Zoghi et al., ; Wu and Liu, ; Komiyama et al., ), Borda winner (Jamieson et al., ; Falahatgar et al., ; Heckel et al., ; Saha et al., ; Wu et al., ) and von Neumann winner (Ramamohan et al., ; Dudík et al., ; Balsubramani et al., ), along with their corresponding performance metrics.
To handle potentially large action space or context information,
Saha () 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. () studied contextual linear stochastic transitivity model with contextualized utilities. Di et al. () proposed a 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 and Krishnamurthy () designed an algorithm that
achieves the optimal regret for $K$-armed contextual dueling bandit problem. Sekhari et al. () studied contextual dueling bandits in a more general setting and proposed an algorithm the provides guarantees for both regret and the number of queries.

Dueling Bandits with Adversarial Feedback.
A line of work has focused on dueling bandits with adversarial feedback or corruption. Gajane et al. () studied a fully adversarial utility-based version of dueling bandits, which was proposed in Ailon et al. (). Saha et al. () considered the Borda regret for adversarial dueling bandits without the assumption of utility. In a setting parallel to that in Lykouris et al. (); Gupta et al. (), Agarwal et al. () 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 algorithm whose regret comprises two terms: one that is optimal in uncorrupted scenarios, and another that is linearly dependent on the total times of adversarial feedback $C$.
Later on, Saha and Gaillard () achieved “best-of-both world” result for noncontextual dueling
bandits and improved the adversarial term of Agarwal et al. () in the same setting. For contextual dueling bandits, Wu et al. () proposed an EXP3-type algorithm for the adversarial linear setting using Borda regret. 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-armed dueling bandit framework without integrating context information. The notable exception is Wu et al. (); however, this study does not provide guarantees regarding the dependency on the number of adversarial feedback instances.

## 3 Preliminaries

In this work, we study linear
contextual dueling bandits with adversarial feedback.
At each round $t\in[T]$, the agent observes the context
information $x_{t}$ from a
context set $\mathcal{X}$ and the corresponding
action set $\mathcal{A}$. Utilizing this context information, the agent selects two actions,
$a_{t}$ and $b_{t}$. Subsequently, the environment will
generate a binary feedback (i.e., preference label) $l_{t}=\operatorname{\mathds{1}}(a_{t}\succ b_{t})\in\{0,1\}$ indicating the preferable action. Following Bengs et al. (); Di et al. (), we assume the existence
of a reward function $r^{*}(x,a)$ dependent
on the context information $x$ and action $a$. Furthermore, there exists a monotonically increasing link function $\sigma$ satisfying $\sigma(x)+\sigma(-x)=1$.
The preference probability will be determined by the link function and the difference between the rewards of the selected arms, i.e.,

$$ $\displaystyle\mathbb{P}(a\succ b|x)$ $\displaystyle=\sigma\big(r^{*}(x,a)-r^{*}(x,b)\big).$ (3.1) $$

As a common practice in the study of dueling bandits (Saha, ; Di et al., ), we make a linear assumption on the reward function:

###### Assumption 3.1 .

Let $\bm{\phi}:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$ be a known feature map, with $\|\bm{\phi}(x,a)\|_{2}\leq 1$ for any $(x,a)\in\mathcal{X}\times\mathcal{A}$. We define the reward function $r_{\bm{\theta}}$ parameterized by $\bm{\theta}\in\mathbb{R}^{d}$, with $r_{\bm{\theta}}(x,a)=\langle\bm{\theta},\bm{\phi}(x,a)\rangle$. Moreover, there exists $\bm{\theta}^{*}$ satisfying $r_{\bm{\theta}^{*}}=r^{*}$, with $\|\bm{\theta}^{*}\|_{2}\leq B$.

Assumption 3.1 aligns with the setting studied in Xiong et al. () and acts as a special case of Sekhari et al. ().

During each round $t$, the optimal action is denoted by $a^{*}_{t}=\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}r^{*}(x_{t},a)$. The regret over the first $T$ rounds is defined as the cumulative sub-optimality between the rewards of the optimal actions and the rewards of the selected actions:

$$ $\displaystyle\text{Regret}(T)$ $\displaystyle=\sum_{t=1}^{T}2r^{*}(x_{t},a^{*}_{t})-r^{*}(x_{t},a_{t})-r^{*}(x_{t},b_{t}).$ (3.2) $$

###### Remark 3.2 .

The linear contextual dueling bandit model shares a similar parametric structure with both the generalized linear bandit model (Filippi et al., ; Li et al., ) and the logistic bandit model (Faury et al., ; Abeille et al., ; Faury et al., ). Specifically, in each round $t$, the act of selecting two arms, $a_{t}$ and $b_{t}$, in the dueling bandit framework can be reduced to pulling an auxiliary ”arm” $\phi(x,a_{t})-\phi(x,b_{t})$ with the linear parameter $\theta^{*}$, as in the logistic bandit or generalized bandit models.
However, a key distinction arises in the computation of regret between these tasks. In the dueling bandit problem, the reward for the selected action is represented as $r^{(}x_{t},a_{t})+r^{(}x_{t},b_{t})$, in contrast to $r^{(}x_{t},a_{t})-r^{(}x_{t},b_{t})$ in the single-arm analogy. This discrepancy implies that the linear contextual dueling bandit problem diverges significantly from both linear bandits and logistic bandits.

We also make an assumption on the derivative of the link function, which is common in the study of generalized linear models for bandits and dueling bandits (Filippi et al., ; Di et al., ).

###### Assumption 3.3 .

The link function $\sigma$ is differentiable. Furthermore, its first-order derivative satisfies:

$$ $\displaystyle\dot{\sigma}(\cdot)\geq\kappa$ $$

for some constant $\kappa>0$.

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. We represent the adversary’s decision at round $t$ by a corruption indicator $c_{t}$, which takes values from the set $\{0,1\}$. If the adversary chooses not to corrupt the result, we have $c_{t}=0$. Otherwise, we have $c_{t}=1$, which means adversarial feedback at this round, and the agent will observe a flipped preference label, i.e., the observation $o_{t}=1-l_{t}$. We define $C$ as the total number of adversarial feedback (^1^11Our corruption indicator $c_{t}$ is slightly different from the corruption level $c_{t}$ for general feedback (He et al., ). In the binary feedback scenario, the corruption level $c_{t}=|o_{t}-l_{t}|$ within each round is 0 or $1$. Therefore, the total number of adversarial feedback $C$ also equals the corruption level $\sum_{t=1}^{T}|o_{t}-l_{t}|$ with binary feedback.)

$$ $\displaystyle C=\sum_{t=1}^{T}c_{t}.$ $$

###### Remark 3.4 .

In our work, the adversary can corrupt the feedback after observing the action chosen by the agent, which is referred to as the strong adversary in Bogunovic et al. (); He et al. (). In comparison, a weak adversary is limited to corrupting feedback without knowledge of the agent’s selection.
Since the weak adversary lacks knowledge of the selected action, it usually predetermines a set of action pairs to corrupt. Under this situation, the number of adversarial feedback $c_{t}$ at round $t$ is defined either as the maximum corruption magnitude for all pairs (For our binary feedback, this would be 1 if adversarial feedback exists for one action, and 0 otherwise) or as the total number of corrupted pairs at round $t$ (Agarwal et al., ). Therefore, for a strong adversary with knowledge of the agent’s selected action, the problem of adversarial feedback becomes more challenging compared to scenarios involving a weak adversary.

###### Assumption 3.1 .

###### Remark 3.2 .

###### Assumption 3.3 .

###### Remark 3.4 .

## 4 Algorithm

In this section, we present our new algorithm RCDB, designed for learning contextual linear dueling bandits. The main algorithm is illustrated in Algorithm 1. At a high level, we incorporate uncertainty-dependent weighting into the Maximum Likelihood Estimator (MLE) to counter adversarial feedback. Specifically, for each round $k\in[K]$, we construct the estimator of parameter $\bm{\theta}$ by solving the following equation:

$$ $\lambda\bm{\theta}+\sum_{i}w_{i}\big(\sigma(\bm{\phi}_{i}^{\top}\bm{\theta})-o_{i}\big)\bm{\phi}_{i}=\mathbb{0},$ (4.1) $$

where we denote $\bm{\phi}_{i}=\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})$ for simplicity. Here, the uncertainty-aware weight $w_{i}$ is selected as a truncation of the exploration bonus $\|\bm{\phi}_{i}\|_{\bm{\Sigma}_{t}^{-1}}$, i.e.,

$$ $\displaystyle w_{t}=\min\{1,\alpha/\|\bm{\phi}_{t}\|_{\bm{\Sigma}_{t}^{-1}}\}.$ (4.2) $$

This type of weighting is initially introduced by He et al. () for the linear bandit problem.
Intuitively speaking, the exploration bonus captures the uncertainty associated with the duel $(a_{i},b_{i})$ in the learning process. For duel $(a_{i},b_{i})$ with high uncertainty, it becomes challenging for the agent to detect whether the observation has been corrupted. Under this situation, the Algorithm 1 will only assign a small weight to the observation, aiming to avoid potentially large estimation errors resulting from adversarial feedback. Conversely, for duels with low uncertainty, a larger weight (up to $1$) is assigned. With the help of this mechanism, the estimation error between ${\bm{\theta}}_{t}$ and $\bm{\theta}$ is upper bounded by

$$ $\displaystyle\big\|\bm{\theta}_{t}-\bm{\theta}^{*}\big\|_{\bm{\Sigma}_{t}}\leq\widetilde{O}(\alpha C+\sqrt{d})/\kappa.$ $$

Furthermore, by selecting a proper threshold parameter, e.g., $\alpha=\sqrt{d}/C$, the weighted MLE shares the confidence radius with that of the no-adversary scenario. In contrast, the standard regularized estimator employed in dueling bandits (Di et al., ) displays a linear dependence in the confidence radius, notably characterized by $\widetilde{O}(C+\sqrt{d})$.

After constructing the estimator $\bm{\theta}_{t}$ from the weighted MLE, the estimated reward for each duel $(a,b)$ can be denoted by $\big(\bm{\phi}(x_{t},a)+\bm{\phi}(x_{t},b)\big)^{\top}\bm{\theta}_{t}$.
To encourage the exploration of duel $(a,b)$ with high uncertainty during the learning process, we
introduce an exploration bonus with the following $\beta\big\|\bm{\phi}(x_{t},a)-\bm{\phi}(x_{t},b)\big\|_{\bm{\Sigma}_{t}^{-1}}$, which is a well-established technique in the context of linear bandit problems (Abbasi-Yadkori et al., ). The selection of action pairs $(a,b)$ is subsequently determined by maximizing the estimated reward with the exploration bonus term, i.e.,

$$ $\displaystyle\big(\bm{\phi}(x_{t},a)+\bm{\phi}(x_{t},b)\big)^{\top}\bm{\theta}_{t}+\beta\big\|\bm{\phi}(x_{t},a)-\bm{\phi}(x_{t},b)\big\|_{\bm{\Sigma}_{t}^{-1}}.$ $$

More discussion about the selection rule was discussed in Appendix A of Di et al. ().

Figure: Algorithm 1 Robust Contextual Dueling Bandit (RCDB)

## 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 $\bm{\theta}_{t}$ can be characterized by the following lemma.

###### Lemma 5.1 .

If we set $\beta=\sqrt{\lambda}B+\big(\alpha C+\sqrt{d\log((1+2T/\lambda)/\delta)}\big)/\kappa$, then with probability at least $1-\delta$, for any $t\in[T]$, we have

$$ $\displaystyle\big\|\bm{\theta}_{t}-\bm{\theta}^{*}\big\|_{\bm{\Sigma}_{t}}\leq\beta.$ $$

###### Remark 5.2 .

If we set $\alpha=(\sqrt{d}+\sqrt{\lambda}B)/C$, then the bonus radius $\beta$ 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$.

With Lemma 5.1, we can present the following regret guarantee of our algorithm RCDB in the dueling bandit framework.

###### Theorem 5.3 .

Under Assumption 3.1 and 3.3, let $0<\delta<1$, the total number of adversarial feedback be $C$. If we set the bonus radius to be

$$ $\displaystyle\beta=\sqrt{\lambda}B+\big(\alpha C+\sqrt{d\log((1+2T/\lambda)/\delta)}\big)/\kappa,$ $$

then with probability at least $1-\delta$, the regret in the first $t$ rounds can be upper bounded by

$$ $\displaystyle\text{Regret}(T)$ $\displaystyle\leq 4\big(\sqrt{\lambda}B+\alpha C/\kappa\big)\sqrt{dT\log(1+2T/\lambda)}$ $\displaystyle\qquad+4d\big(\sqrt{T}/\kappa+\sqrt{\lambda}B/\alpha+4C/\kappa\big)\log\big((1+2T/\lambda)/\delta\big)$ $\displaystyle\qquad+4d^{1.5}\sqrt{\log^{3}\big((1+2T/\lambda)/\delta\big)}/{(\alpha\kappa)}.$ $$

Moreover, if we set $\alpha=(\sqrt{d}+\sqrt{\lambda}B)/C$, $\lambda=1/B^{2}$, the regret upper bound can be simplified to

$$ $\displaystyle\text{Regret}(T)=\widetilde{O}\Big(\frac{d\sqrt{T}}{\kappa}+\frac{dC}{\kappa}\Big),$ $$

where $\widetilde{O}$ hides logarithmic factors on $T,B$ and $1/\delta$.

###### Remark 5.4 .

Our regret bound consists of two terms. The first one is a $C$-independent term $\widetilde{O}(d\sqrt{T})$, which matches the lower bound $\widetilde{\Omega}(d\sqrt{T})$ proved in Bengs et al. (). This indicates that our result is optimal in scenarios without adversarial feedback ($C=0$). Additionally, our result includes an additive term that is linearly dependent on the number of adversarial feedback $C$. When $C=O(\sqrt{T})$, the order of regret will be the same as the stochastic setting. It indicates the robustness of our algorithm to adversarial feedback. Additionally, the following theorem we present establishes a lower bound for this adversarial term, indicating that our dependency on the number of adversarial feedback $C$ and the context dimension $d$ is also optimal.

###### Theorem 5.5 .

For any dimension $d$, there exists an instance of dueling bandits with $|\mathcal{A}|=d$, such that any algorithm with the knowledge of the number of adversarial feedback $C$ must incur $\Omega(dC)$ regret with probability at least 1/2.

###### Remark 5.6 .

The proof of Theorem 5.5 follows Bogunovic et al. (). In the constructed instances, only one action has reward 1, while others have 0. Compared with linear bandits, where the feedback is an exact reward, dueling bandits deal with the comparison between a pair of actions. A critical observation from our preference model, as formulated in (3.1), is that two actions with identical rewards result in a pair that is challenging to differentiate.
The lower bound can be proved by corrupting every comparison into a random guess until the total times of adversarial feedback have been used up. For detailed proof, please refer to Section A.2.
Our proved lower bound $\Omega(dC)$ shows that our result is nearly optimal because of the linear dependency on $C,d$ and only logarithmic dependency on the total number of rounds $T$.

###### Lemma 5.1 .

###### Remark 5.2 .

###### Theorem 5.3 .

###### Remark 5.4 .

###### Theorem 5.5 .

###### Remark 5.6 .

### 5.2 Unknown Number of Adversarial Feedback

In our previous analysis, the selection of parameters depended on having prior knowledge of the total number of adversarial feedback $C$, which be impractical in certain scenarios. In this subsection, we extend our previous result to address the challenge posed by an unknown number of adversarial feedback $C$. Our approach to tackle this uncertainty is straightforward: we introduce an adversarial tolerance threshold $\bar{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 1 in the case of an unknown number of adversarial feedback $C$.

###### Theorem 5.7 .

Under Assumptions 3.1 and 3.3, if we set the the confidence radius as

$$ $\displaystyle\beta=\sqrt{\lambda}B+\Big(\alpha\bar{C}+\sqrt{d\log\big((1+2T/\lambda)/\delta\big)}\Big)/\kappa,$ $$

with the pre-defined adversarial tolerance threshold $\bar{C}$ and $\alpha=(\sqrt{d}+\sqrt{\lambda}B)/\bar{C}$, then with probability at least $1-\delta$, the regret of Algorithm 1 can be upper bounded as following:

- •
If the actual number of adversarial feedback $C$ is smaller than the adversarial tolerance threshold $\bar{C}$, then we have
$\displaystyle\text{Regret}(T)=\widetilde{O}(d\sqrt{T}+d\bar{C}).$
- •
If the actual number of adversarial feedback $C$ is larger than the adversarial tolerance threshold $\bar{C}$, then we have $\text{Regret}(T)=O(T)$.

###### Remark 5.8 .

For the weak adversary discussed in Remark 3.4, the COBE framework (Wei et al., ) can be applied to adapt an algorithm with a known corruption level $C$ to an algorithm facing an unknown corruption level. However, our focus is on the strong adversary, and our results are optimal in the following sense. Theorem 4.12 in He et al. () demonstrates that any linear bandit algorithm with an optimal regret upper bound in an uncorrupted setting will fail when the corruption level exceeds $\Omega(\sqrt{T})$, where $T$ is the total number of steps.
This result also extends to the domain of dueling bandits. When the corruption level reaches $\bar{C}=\Omega(\sqrt{T})$, every algorithm that is optimal when uncorrupted will incur linear regret. Thus, it is impossible to design an algorithm that adapts to an unknown level of corruption while maintaining efficient performance guarantees in the uncorrupted case.

###### Remark 5.9 .

It is important to highlight that the effectiveness of our algorithm is highly related to the choice of the pre-defined adversarial tolerance threshold $\bar{C}$. When this threshold is conservative, our algorithm fails to provide a non-trivial performance guarantee. Conversely, an excessively optimistic adversarial tolerance threshold $\bar{C}$ can defend against a diverse range of attacks but may deteriorate the overall algorithmic performance.
Therefore, there exists a trade-off between robust adversarial defense and near-optimal algorithmic performance. For a special scenario, when we set $\bar{C}=\widetilde{O}(\sqrt{T})$, our algorithm achieves $\widetilde{O}(d\sqrt{T})$ regret. This result implies that our algorithm can exhibit similar performance as the no-adversary case, even
in the presence of an unknown number of adversarial feedback $C\leq\sqrt{T}$.

###### Theorem 5.7 .

###### Remark 5.8 .

###### Remark 5.9 .

## 6 Roadmap of the Proof

### 6.1 Uncertainty-weighted MLE with Adversarial Feedback

In this section, we offer an overview of the proof for Lemma 5.1. The general proof idea for the uncertainty-weighted MLE with adversarial feedback lies in decomposing the estimation error into three terms, a stochastic error term, an adversarial term, and an additional regularization term.
Following the analysis of standard (weighted) MLE (Li et al., ), we introduce an auxiliary function:

$$ $\displaystyle G_{t}(\bm{\theta})$ $\displaystyle=\lambda\kappa\bm{\theta}+\sum_{i=1}^{t-1}w_{i}\Big[\sigma\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bm{\theta}\Big)$ $\displaystyle\qquad-\sigma\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bm{\theta}^{*}\Big)\Big]\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big).$ $$

It satisfies two conditions: First, for the true parameter value
$\bm{\theta}^{*}$,
$G_{t}(\bm{\theta}^{*})$ has a simple expression, i.e.,

$$ $\displaystyle G_{t}(\bm{\theta}^{*})=\lambda\kappa\bm{\theta}^{*}.$ $$

Second, according to (4.4), we can get the value of function $G_{t}$ at the MLE $\bm{\theta}_{t}$,

$$ $\displaystyle G_{t}(\bm{\theta}_{t})=\sum_{i=1}^{t-1}w_{i}\gamma_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big),$ (6.1) $$

where $\gamma_{t}=o_{t}-\sigma\big((\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t}))^{\top}\bm{\theta}^{*}\big)$.
To connect the desired estimation error with the function $G_{t}$, we use the mean value theorem. This leads to an upper bound of the estimation error:

$$ $\displaystyle\|\bm{\theta}_{t}-\bm{\theta}^{*}\|_{\bm{\Sigma}_{t}}\leq\frac{1}{\kappa}\big\|G_{t}(\bm{\theta}_{t})-G_{t}(\bm{\theta}^{*})\big\|_{\bm{\Sigma}_{t}^{-1}}\leq\underbrace{\frac{1}{\kappa}\lambda\|\bm{\theta}^{*}\|_{\bm{\Sigma}_{t}^{-1}}}_{\text{Regularization term}}+\underbrace{\frac{1}{\kappa}\big\|G_{t}(\bm{\theta}_{t})\big\|_{\bm{\Sigma}_{t}^{-1}}}_{I_{1}}.$ $$

For term $I_{1}$, we can decompose the summation in (6.1) based on the adversarial feedback $c_{t}$, i.e.,

$$ $\displaystyle G_{t}(\bm{\theta}_{t})$ $\displaystyle=\sum_{i<t:c_{i}=0}w_{i}\gamma_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)+\underbrace{\sum_{i<t:c_{i}=1}w_{i}\gamma_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)}_{I_{2}},$ $$

where $I_{2}$ can be further decomposed as

$$ $\displaystyle I_{2}$ $\displaystyle=\sum_{i<t:c_{i}=1}w_{i}\epsilon_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)+\sum_{i<t:c_{i}=1}w_{i}(\gamma_{i}-\epsilon_{i})\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big).$ $$

where $\epsilon_{t}=o_{t}-\sigma\big((\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t}))^{\top}\bm{\theta}^{*}\big)$. With our notation of adversarial feedback, when $c_{i}=0$, we have $\gamma_{i}=\epsilon_{i}$. Therefore, we have $|\gamma_{i}-\epsilon_{i}|\leq 1$ and

$$ $\displaystyle I_{1}$ $\displaystyle\leq\underbrace{\frac{1}{\kappa}\Big\|\sum_{i=1}^{t-1}w_{i}\epsilon_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)\Big\|_{\bm{\Sigma}_{t}^{-1}}}_{\text{Stochastic term}}+\underbrace{\frac{1}{\kappa}\Big\|\sum_{i<t:c_{i}=1}w_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)\Big\|_{\bm{\Sigma}_{t}^{-1}}}_{\text{Adversarial term}}.$ $$

The stochastic term can be upper bounded with the concentration inequality (Lemma C.2). Additionally, by employing our specifically chosen weight, as (4.2), we can control the adversarial term, with $w_{i}\|\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\|_{\bm{\Sigma}_{t}^{-1}}\leq\alpha$. Therefore, the adversarial term can be bounded by $\alpha C/\kappa$.

### 6.2 Regret Upper Bound

With a similar discussion of the symmetric arm selection rule to Di et al. (),
the regret defined in (3.2) can be bounded by

$$ $\displaystyle\text{Regret}(T)\leq\sum_{t=1}^{T}\min\Big\{4,2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\Big\}.$ $$

Note that in our selection of weight $w_{t}$, it has two possible values. We decompose the summation based on the two cases separately. We have

$$ $\displaystyle\text{Regret}(T)$ $\displaystyle\leq\underbrace{\sum_{w_{t}=1}\min\Big\{4,2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\Big\}}_{J_{1}}+\underbrace{\sum_{w_{t}<1}\min\Big\{4,2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\Big\}}_{J_{2}}.$ $$

We consider $J_{1},J_{2}$ separately. For the term $J_{1}$, we define $\bm{\Lambda}_{t}=\lambda\mathbf{I}+\sum_{i\leq t-1,w_{i}=1}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}$. Then, we have $\bm{\Sigma}_{t}\succeq\bm{\Lambda}_{t}$, and therefore

$$ $\displaystyle\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\leq\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Lambda}_{t}^{-1}}.$ $$

Using Lemma C.3 with $\mathbf{x}_{t}=\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})$, we have

$$ $\displaystyle J_{1}\leq 4\beta\sqrt{dT\log(1+2T/\lambda)}.$ (6.2) $$

For term $J_{2}$, we note that $w_{t}<1$ implies that $w_{t}=\alpha/\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}$. Therefore, we have

$$ $\displaystyle J_{2}$ $\displaystyle\leq\sum_{t=1}^{T}\frac{4\beta}{\alpha}\min\Big\{1,\|\sqrt{w_{t}}(\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t}))\|^{2}_{\bm{\Sigma}_{t}^{-1}}\Big\}.$ $$

Using Lemma C.3 with $\mathbf{x}_{t}^{\prime}=\sqrt{w_{t}}(\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t}))$, we have

$$ $\displaystyle J_{2}\leq\frac{4d\beta\log(1+2T/\lambda)}{\alpha}.$ (6.3) $$

We conclude the proof of regret by combining (6.2) and (6.3).

## 7 Experiments

### 7.1 Experiment Setup

#### Preference Model.

We study the effect of adversarial feedback with the preference model determined by (3.1), where $\sigma(x)=1/(1+e^{-x})$. We randomly generate the underlying parameter in $[-0.5,0.5]^{d}$ and normalize it to be a vector with $\|\bm{\theta}^{*}\|_{2}=2$. Then, we set it to be the underlying parameter and construct the reward utilized in the preference model as $r^{*}(x,a)=\langle\bm{\theta}^{*},\bm{\phi}(x,a)\rangle$. We set the action set $\mathcal{A}=\big\{-{1}/{\sqrt{d}},{1}/{\sqrt{d}}\big\}^{d}$. For simplicity, we assume $\bm{\phi}(x,a)=a$. In our experiment, we set the dimension $d=5$, with the size of action set $|\mathcal{A}|=2^{d}=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. In 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.
- •
“Random Attack”: At each round, the adversary will flip the preference label with the probability of $0<p<1$, until the times of adversarial feedback reach $C$.
- •
“Adversarial Attack”: The adversary can have access to the true preference model. It will only flip the preference label when it aligns with the preference model, i.e., 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 of adversarial feedback reach $C$. In this way, it will mislead the agent to believe this action is the optimal one.

#### Experiment Setup.

For each experiment instance, we simulate the interaction with the environment for $T=2000$ rounds. At each round, the feedback for the action pair selected by the algorithm is generated according to 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 regret defined in (3.2) averaged across 10 random runs.

Figure: (a) Greedy Attack
Refer to caption: x1.png

### 7.2 Performance Comparison

We first introduce the algorithms studied in this section.

- •
MaxInP: Maximum Informative Pair by Saha (). It involves maintaining a 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 to maximize the uncertainty in the difference between the two arms within this promising set, referred to as “maximum informative”.
- •
CoLSTIM: The method by Bengs et al. (). It involves maintaining a 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 toughest competitor, with an added uncertainty bonus.
- •
MaxPairUCB: This algorithm was proposed in Di et al. (). It uses the regularized MLE to estimate the parameter $\bm{\theta}^{*}$. Then it selects the actions based on a symmetric action selection rule, i.e. the actions with the largest estimated reward plus some uncertainty bonus.
- •
RCDB: Algorithm 1 proposed in this paper. The key difference from the other algorithms is the use of uncertainty weight in the calculation of MLE (4.4). The we use the same symmetric action selection rule as MaxPairUCB. 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 1(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 1(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 it results in the agent encountering only incorrect preference labels at 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 1(d), the adversary employs a strategy aimed at misleading algorithms into believing a suboptimal action is 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 1(c) and Figure 1(d), our 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.

Figure: Figure 2: The relationship between cumulative regret and the number of adversarial feedback $C$. For this specific experiment, we employ the ”greedy attack” method to generate the adversarial feedback. $C$ is selected from the set $[20,40,60,80,100,120,140,160,180,200]$ (10 adversarial levels).
Refer to caption: x5.png

### 7.3 Robustness to Different Numbers of Adversarial Feedback

In this section, we test the performance of algorithms with increasing times of adversarial feedback. Our results show a linear dependency on the number of adversarial feedback $C$, which is consistent with the theoretical results we have proved in Theorem 5.3 and 5.5. In comparison to other algorithms, RCDB demonstrates superior robustness against adversarial feedback, as evidenced by its notably smaller regret.

## 8 Conclusion

In this paper, we focus on the contextual dueling bandit problem from adversarial feedback. We introduce a novel algorithm, RCDB, which utilizes an uncertainty-weighted 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 future direction, we aim to extend our uncertainty-weighted method to encompass more general settings involving preference-based data. A particularly promising future direction of our research lies in addressing adversarial feedback within the process of aligning large language models using Reinforcement Learning from Human Feedback (RLHF).

## Appendix 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

$$ $\displaystyle\mathcal{E}=\Big\{\big\|\bm{\theta}_{t}-\bm{\theta}^{*}\big\|_{\bm{\Sigma}_{t}}\leq\beta,\forall t\in[T]\Big\}.$ $$

Let $r_{t}=2r^{*}(x_{t},a^{*}_{t})-r^{*}(x_{t},a_{t})-r^{*}(x_{t},b_{t})$ be the regret incurred at round $t$. The following lemma provides the upper bound of $r_{t}$.

###### Lemma A.1 .

Let $0<\delta<1$. If we set $\beta=\sqrt{\lambda}B+\big(\alpha C+\sqrt{d\log((1+2T/\lambda)/\delta)}\big)/\kappa$, on event $\mathcal{E}$, the regret of Algorithm 1 incurred at round $t$ can be upper bounded by

$$ $\displaystyle r_{t}\leq\min\Big\{4,2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\Big\}.$ $$

With Lemma A.1, we can provide the proof of Theorem 5.3.

###### Proof of Theorem 5.3 .

Using Lemma A.1,
the total regret can be upper bounded by

$$ $\displaystyle\text{Regret}(T)\leq\sum_{t=1}^{T}\min\Big\{4,2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\Big\}.$ $$

Our weight $w_{t}$ has two possible values. We decompose the summation based on the two cases separately. We have

$$ $\displaystyle\text{Regret}(T)$ $\displaystyle\leq\underbrace{\sum_{w_{t}=1}\min\Big\{4,2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\Big\}}_{J_{1}}+\underbrace{\sum_{w_{t}<1}\min\Big\{4,2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\Big\}}_{J_{2}}.$ $$

For the term $J_{1}$, we consider a partial summation at rounds when $w_{t}=1$. Let $\bm{\Lambda}_{t}=\lambda\mathbf{I}+\sum_{i\leq k-1,w_{i}=1}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}$. Then we have

$$ $\displaystyle J_{1}$ $\displaystyle\leq 4\beta\sum_{t:w_{t}=1}\min\Big\{1,\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\Big\}$ $\displaystyle\leq 4\beta\sum_{t:w_{t}=1}\min\Big\{1,\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Lambda}_{t}^{-1}}\Big\}$ $\displaystyle\leq 4\beta\sqrt{T\sum_{t:w_{t}=1}\min\big\{1,\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|^{2}_{\bm{\Lambda}_{t}^{-1}}\big\}}$ $\displaystyle\leq 4\beta\sqrt{dT\log(1+2T/\lambda)},$ (A.1) $$

where the second inequality holds due to $\bm{\Sigma}_{t}\succeq\bm{\Lambda}_{t}$. The third inequality holds due to the Cauchy-Schwartz inequality, The last inequality holds due to Lemma C.3.

For the term $J_{2}$, the weight in this summation satisfies $w_{t}<1$, and therefore $w_{t}=\alpha/\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}$. Then we have

$$ $\displaystyle J_{2}$ $\displaystyle=\sum_{w_{t}<1}\min\Big\{4,2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}w_{t}\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}/\alpha\Big\}$ $\displaystyle\leq\sum_{t=1}^{T}\min\Big\{4,2\beta/\alpha\|\sqrt{w_{t}}(\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t}))\|^{2}_{\bm{\Sigma}_{t}^{-1}}\Big\}$ $\displaystyle\leq\sum_{t=1}^{T}\frac{4\beta}{\alpha}\min\Big\{1,\|\sqrt{w_{t}}(\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t}))\|^{2}_{\bm{\Sigma}_{t}^{-1}}\Big\}$ $\displaystyle\leq\frac{4d\beta\log(1+2T/\lambda)}{\alpha},$ (A.2) $$

where the first equality holds due to the choice of $w_{t}$. The first inequality holds because each term in the summation is positive. The last inequality holds due to Lemma C.3.
Combining (A.1) and (A.2), we complete the proof of Theorem 5.3.
∎

###### Lemma A.1 .

###### Proof of Theorem 5.3 .

### A.2 Proof of Theorem 5.5

###### Proof of Theorem 5.5 .

Our proof adapts the argument in Bogunovic et al. () to dueling bandits.
For any dimension $d$, we construct $d$ instances, each with $\bm{\theta}_{i}=\mathbf{e}_{i}$, where $\mathbf{e}_{i}$ is the $i$-th standard basis vector. We set the action set $\mathcal{A}=\{\mathbf{e}_{i}\}_{i=1}^{d}$. Therefore, in the $i$-th instance, the reward for the $i$-th action will be 1. For the other actions, it will be 0. 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 $Cd/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 $\Omega(dC)$ regret. This completes the proof of Theorem 5.5.
∎

###### Proof of Theorem 5.5 .

### A.3 Proof of Theorem 5.7

###### Proof of Theorem 5.7 .

Here, based on the relationship between $C$ and the threshold $\bar{C}$, we discuss two distinct cases separately.

- •
In the scenario where $\bar{C}<C$, Algorithm 1 can ensures a trivial regret bound, with the guarantee that $\textbf{Regret}(T)\leq 2T$.
- •
In the scenario where $C\leq\bar{C}$, we know that $\bar{C}$ is remains a valid upper bound on the number of adversarial feedback. Under this situation, Algorithm 1 operates successfully with $\bar{C}$ adversarial feedback. Therefore, according to Theorem 5.3, the regret is upper bounded by
$\displaystyle\textbf{Regret}(T)\leq\widetilde{O}(d\sqrt{T}+d\bar{C}).$

∎

###### Proof of Theorem 5.7 .

## Appendix 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 in Li et al. (), we define some auxiliary quantities

$$ $\displaystyle G_{t}(\bm{\theta})$ $\displaystyle=\lambda\kappa\bm{\theta}+\sum_{i=1}^{t-1}w_{i}\Big[\sigma\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bm{\theta}\Big)$ $\displaystyle\qquad-\sigma\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bm{\theta}^{*}\Big)\Big]\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big),$ $\displaystyle\epsilon_{t}$ $\displaystyle=l_{t}-\sigma\Big(\big(\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\big)^{\top}\bm{\theta}^{*}\Big),$ $\displaystyle\gamma_{t}$ $\displaystyle=o_{t}-\sigma\Big(\big(\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\big)^{\top}\bm{\theta}^{*}\Big),$ $\displaystyle Z_{t}$ $\displaystyle=\sum_{i=1}^{t-1}w_{i}\gamma_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big).$ $$

In Algorithm 1, $\bm{\theta}_{t}$ is chosen to be the solution of the following equation,

$$ $\displaystyle\lambda\kappa\bm{\theta}_{t}+\sum_{i=1}^{t-1}w_{i}\Big[\sigma\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bm{\theta}_{t}\Big)-o_{i}\Big]\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)=\textbf{0}.$ (B.1) $$

Then we have

$$ $\displaystyle G_{t}(\bm{\theta}_{t})$ $\displaystyle=\lambda\kappa\bm{\theta}_{t}+\sum_{i=1}^{t-1}w_{i}\Big[\sigma\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bm{\theta}_{t}\Big)$ $\displaystyle\qquad-\sigma\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bm{\theta}^{*}\Big)\Big]\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)$ $\displaystyle=\sum_{i=1}^{t-1}w_{i}\Big[o_{i}-\sigma\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bm{\theta}^{*}\Big)\Big]\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)$ $\displaystyle=Z_{t}.$ $$

The analysis in Li et al. (); Di et al. () shows that this equation has a unique solution, with $\bm{\theta}_{t}=G_{t}^{-1}(Z_{t})$.
Using the mean value theorem, for any $\bm{\theta}_{1},\bm{\theta}_{2}\in\mathbb{R}^{d}$, there exists $m\in[0,1]$ and $\bar{\bm{\theta}}=m\bm{\theta}_{1}+(1-m)\bm{\theta}_{2}$, such that the following equation holds,

$$ $\displaystyle G_{t}(\bm{\theta}_{1})-G_{t}(\bm{\theta}_{2})$ $\displaystyle=\lambda\kappa(\bm{\theta}_{1}-\bm{\theta}_{2})+\sum_{i=1}^{t-1}w_{i}\Big[\sigma\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bm{\theta}_{1}\Big)$ $\displaystyle\qquad-\sigma\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bm{\theta}_{2}\Big)\Big]\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)$ $\displaystyle=\Big[\lambda\kappa\mathbf{I}+\sum_{i=1}^{t-1}w_{i}\dot{\sigma}\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bar{\bm{\theta}}\Big)$ $\displaystyle\qquad\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\Big](\bm{\theta}_{1}-\bm{\theta}_{2}).$ $$

We define $F(\bar{\bm{\theta}})$ as

$$ $\displaystyle F(\bar{\bm{\theta}})=\lambda\kappa\mathbf{I}+\sum_{i=1}^{t-1}w_{i}\dot{\sigma}\Big(\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\bar{\bm{\theta}}\Big)\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}\Big].$ $$

Moreover, we can see that $G_{t}(\bm{\theta}^{*})=\lambda\kappa\bm{\theta}^{*}$. Recall $\bm{\Sigma}_{t}=\lambda\mathbf{I}+\sum_{i=1}^{t-1}w_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)^{\top}$. We have

$$ $\displaystyle\big\|G_{t}(\bm{\theta}_{t})-G_{t}(\bm{\theta}^{*})\big\|^{2}_{\bm{\Sigma}_{t}^{-1}}$ $\displaystyle=(\bm{\theta}_{t}-\bm{\theta}^{*})^{\top}F(\bar{\bm{\theta}})\bm{\Sigma}_{t}^{-1}F(\bar{\bm{\theta}})(\bm{\theta}_{t}-\bm{\theta}^{*})$ $\displaystyle\geq\kappa^{2}(\bm{\theta}_{t}-\bm{\theta}^{*})^{\top}\bm{\Sigma}_{t}(\bm{\theta}_{t}-\bm{\theta}^{*})$ $\displaystyle=\kappa^{2}\|\bm{\theta}_{t}-\bm{\theta}^{*}\|^{2}_{\bm{\Sigma}_{t}},$ $$

where the first inequality holds due to $\dot{\mu}(\cdot)\geq\kappa>0$ and $F(\bar{\bm{\theta}})\succeq\kappa\bm{\Sigma}_{t}$.
Then we have the following estimate of the estimation error:

$$ $\displaystyle\left\|\bm{\theta}_{t}-\bm{\theta}^{*}\right\|_{\bm{\Sigma}_{t}}$ $\displaystyle\leq\frac{1}{\kappa}\big\|G_{t}(\bm{\theta}_{t})-G_{t}(\bm{\theta}^{*})\big\|_{\bm{\Sigma}_{t}^{-1}}$ $\displaystyle\leq\lambda\|\bm{\theta}^{*}\|_{\bm{\Sigma}_{t}^{-1}}+\frac{1}{\kappa}\|Z_{t}\|_{\bm{\Sigma}_{t}^{-1}}$ $\displaystyle\leq\sqrt{\lambda}\|\bm{\theta}^{*}\|_{2}+\frac{1}{\kappa}\|Z_{t}\|_{\bm{\Sigma}_{t}^{-1}},$ $$

where the second inequality holds due to the triangle inequality and $G_{t}(\bm{\theta}^{*})=\lambda\kappa\bm{\theta}^{*}$. The last inequality holds due to $\bm{\Sigma}_{t}\succeq\lambda\mathbf{I}$.
Finally, we need to bound the $\|Z_{t}\|_{\bm{\Sigma}_{t}^{-1}}$ term.
To study the impact of adversarial feedback, we decompose the summation in (6.1) based on the adversarial feedback $c_{t}$, i.e.,

$$ $\displaystyle Z_{t}$ $\displaystyle=\sum_{i<t:c_{i}=0}w_{i}\gamma_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)+\sum_{i<t:c_{i}=1}w_{i}\gamma_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big),$ $$

When $c_{i}=1$, i.e. with adversarial feedback, $|\gamma_{i}-\epsilon_{i}|=1$. On the contrary, when $c_{i}=0$, $\gamma_{i}=\epsilon_{i}$. Therefore,

$$ $\displaystyle\sum_{i<t:c_{i}=0}w_{i}\gamma_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)$ $\displaystyle=\sum_{i<t:c_{i}=0}w_{i}\epsilon_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big),$ $\displaystyle\sum_{i<t:c_{i}=1}w_{i}\gamma_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)$ $\displaystyle=\sum_{i<t:c_{i}=1}w_{i}\epsilon_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)$ $\displaystyle\qquad+\sum_{i<t:c_{i}=1}w_{i}\big(\gamma_{i}-\epsilon_{i})(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big).$ $$

Summing up the two equalties, we have

$$ $\displaystyle Z_{t}=\sum_{i=1}^{t-1}w_{i}\epsilon_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)+\sum_{i<t:c_{i}=1}w_{i}(\gamma_{i}-\epsilon_{i})\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big).$ $$

Therefore,

$$ $\displaystyle\|Z_{t}\|_{\bm{\Sigma}_{t}^{-1}}$ $\displaystyle\leq\underbrace{\bigg\|\sum_{i=1}^{t-1}w_{i}\epsilon_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)\bigg\|_{\bm{\Sigma}_{t}^{-1}}}_{I_{1}}+\underbrace{\bigg\|\sum_{i<t:c_{i}=1}w_{i}\big(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\big)\bigg\|_{\bm{\Sigma}_{t}^{-1}}}_{I_{2}}.$ $$

For the term $I_{1}$, with probability at least $1-\delta$, for all $t\in[T]$, it can be bounded by

$$ $\displaystyle I_{1}\leq\sqrt{2\log\Big(\frac{\det(\bm{\Sigma}_{t})^{1/2}\det(\bm{\Sigma}_{0})^{-1/2}}{\delta}\Big)},$ $$

due to Lemma C.2.
Using $w_{i}\leq 1$, we have $\sqrt{w_{i}}\|\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\|_{2}\leq 2$. Moreover, we have

$$ $\displaystyle\det(\bm{\Sigma}_{t})$ $\displaystyle\leq\bigg(\frac{\text{Tr}(\bm{\Sigma}_{t})}{d}\bigg)^{d}$ $\displaystyle=\bigg(\frac{d\lambda+\sum_{i=1}^{t-1}w_{i}\|(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i}))\|^{2}_{2}}{d}\bigg)^{d}$ $\displaystyle\leq\bigg(\frac{d\lambda+2T}{d}\bigg)^{d},$ $$

where the first inequality holds because for every matrix $\mathbf{A}\in\mathbb{R}^{d\times d}$, $\det\mathbf{A}\leq(\text{Tr}(\mathbf{A})/d)^{d}$. The second inequality holds due to $\sqrt{w_{i}}\|\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i})\|_{2}\leq 2$.
Easy to see that $\det(\bm{\Sigma}_{0})=\lambda^{d}$. The term $I_{1}$ can be bounded by

$$ $\displaystyle I_{1}\leq\sqrt{d\log((1+2T/\lambda)/\delta)}.$ (B.2) $$

For $I_{2}$, with our choice of the weight $w_{i}$, we have

$$ $\displaystyle I_{2}$ $\displaystyle\leq\sum_{i<t:c_{i}=1}w_{i}\big\|(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i}))\big\|_{\bm{\Sigma}_{t}^{-1}}$ $\displaystyle\leq\sum_{i<t:c_{i}=1}w_{i}\big\|(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i}))\big\|_{\bm{\Sigma}_{i}^{-1}}$ $\displaystyle\leq\sum_{i<t:c_{i}=1}\alpha$ $\displaystyle\leq\alpha C,$ (B.3) $$

where the second inequality holds due to $\bm{\Sigma}_{t}\succeq\bm{\Sigma}_{i}$. The third inequality holds due to $w_{i}\leq\alpha/\|(\bm{\phi}(x_{i},a_{i})-\bm{\phi}(x_{i},b_{i}))\big\|_{\bm{\Sigma}_{i}^{-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.
∎

###### Proof of Lemma 5.1 .

### B.2 Proof of Lemma A.1

###### Proof of Lemma A.1 .

Let the regret incurred at the $t$-th round by $r_{t}=2r^{*}(x_{t},a^{*}_{t})-r^{*}(x_{t},a_{t})-r^{*}(x_{t},b_{t})$.
It can be decomposed as

$$ $\displaystyle r_{t}$ $\displaystyle=2r^{*}(x_{t},a^{*}_{t})-r^{*}(x_{t},a_{t})-r^{*}(x_{t},b_{t})$ $\displaystyle=\langle\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},a_{t}),\bm{\theta}^{*}\rangle+\langle\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},b_{t}),\bm{\theta}^{*}\rangle$ $\displaystyle=\langle\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},a_{t}),\bm{\theta}^{*}-\bm{\theta}_{t}\rangle+\langle\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},b_{t}),\bm{\theta}^{*}-\bm{\theta}_{t}\rangle$ $\displaystyle\qquad+\langle 2\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t}),\bm{\theta}_{t}\rangle$ $\displaystyle\leq\|\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},a_{t})\|_{\bm{\Sigma}_{t}^{-1}}\|\bm{\theta}^{*}-\bm{\theta}_{t}\|_{\bm{\Sigma}_{t}}+\|\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\|\bm{\theta}^{*}-\bm{\theta}_{t}\|_{\bm{\Sigma}_{t}}$ $\displaystyle\qquad+\langle 2\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t}),\bm{\theta}_{t}\rangle$ $\displaystyle\leq\beta\|\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},a_{t})\|_{\bm{\Sigma}_{t}^{-1}}+\beta\|\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}$ $\displaystyle\qquad+\langle 2\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t}),\bm{\theta}_{t}\rangle,$ $$

where the first inequality holds due to the Cauchy-Schwarz inequality. The second inequality holds due to the high probability confidence event $\mathcal{E}$.
Using our action selection rule, we have

$$ $\displaystyle\langle\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},a_{t}),\bm{\theta}_{t}\rangle+\beta\|\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},a_{t})\|_{\bm{\Sigma}_{t}^{-1}}$ $\displaystyle\qquad\leq\langle\bm{\phi}(x_{t},b_{t})-\bm{\phi}(x_{t},a_{t}),\bm{\theta}_{t}\rangle+\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}$ $\displaystyle\langle\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},b_{t}),\bm{\theta}_{t}\rangle+\beta\|\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}$ $\displaystyle\qquad\leq\langle\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t}),\bm{\theta}_{t}\rangle+\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}.$ $$

Adding the above two inequalities, we have

$$ $\displaystyle\beta\|\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},a_{t})\|_{\bm{\Sigma}_{t}^{-1}}+\beta\|\bm{\phi}(x_{t},a_{t}^{*})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}$ $\displaystyle\qquad\leq\langle\bm{\phi}(x_{t},a_{t})+\bm{\phi}(x_{t},b_{t})-2\bm{\phi}(x_{t},a_{t}^{*}),\bm{\theta}_{t}\rangle+2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}.$ $$

Therefore, we prove that the regret at round $t$ can be upper bounded by

$$ $\displaystyle r_{t}\leq 2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}.$ $$

With a simple observation, we have $r_{t}\leq 4$. Therefore, the total regret can be upper bounded by

$$ $\displaystyle\text{Regret}(T)\leq\sum_{t=1}^{T}\min\Big\{4,2\beta\|\bm{\phi}(x_{t},a_{t})-\bm{\phi}(x_{t},b_{t})\|_{\bm{\Sigma}_{t}^{-1}}\Big\}.$ $$

∎

###### Proof of Lemma A.1 .

## Appendix C Auxiliary Lemmas

###### Lemma C.1 (Azuma–Hoeffding inequality, Cesa-Bianchi and Lugosi 2006 ) .

Let $\{\eta_{k}\}^{K}_{k=1}$ be a
martingale difference sequence with respect to a filtration $\{\mathcal{F}_{t}\}$ satisfying $|\eta_{t}|\leq R$ for some constant
$R$, $\eta_{t}$ is $\mathcal{F}_{t+1}$-measurable, $\mathbb{E}[\eta_{t}|\mathcal{F}_{t}]=0$. Then for any $0<\delta<1$, with probability at least $1-\delta$, we have

$$ $\displaystyle\sum_{t=1}^{T}\eta_{t}\leq R\sqrt{2T\log{1/\delta}}.$ $$

###### Lemma C.2 (Lemma 9 Abbasi-Yadkori et al. 2011 ) .

Let $\{\epsilon_{t}\}^{T}_{t=1}$ be a real-valued stochastic
process with corresponding filtration $\{\mathcal{F}_{t}\}^{T}_{t=0}$ such that $\epsilon_{t}$ is $\mathcal{F}_{t}$-measurable and $\epsilon_{t}$ is conditionally
$R$-sub-Gaussian, i.e.

$$ $\displaystyle\forall\lambda\in\mathbb{R},E[e^{\lambda\epsilon_{t}}|\mathcal{F}_{t-1}]\leq\exp\Big(\frac{\lambda^{2}R^{2}}{2}\Big).$ $$

Let $\{\mathbf{x}_{t}\}^{T}_{t=1}$ be an $\mathbb{R}^{d}$-valued stochastic process where $\mathbf{x}_{t}$ is $\mathcal{F}_{t-1}$-measurable and for any $t\in[T]$,
we further define $\bm{\Sigma}_{t}=\lambda\mathbf{I}+\sum^{t}_{i=1}\mathbf{x}_{i}\mathbf{x}^{\top}_{i}$ . Then with probability at least $1-\delta$, for all $t\in[T]$, we
have

$$ $\displaystyle\bigg\|\sum_{i=1}^{T}\mathbf{x}_{i}\eta_{i}\bigg\|^{2}_{\bm{\Sigma}^{-1}_{t}}\leq 2R^{2}\log\bigg(\frac{\det(\bm{\Sigma}_{t})^{1/2}\det(\bm{\Sigma}_{0})^{-1/2}}{\delta}\bigg).$ $$

###### Lemma C.3 (Lemma 11, Abbasi-Yadkori et al. 2011 ) .

For any $\lambda>0$ and sequence $\{\mathbf{x}_{t}\}_{t=1}^{T}\subseteq\mathbb{R}^{d}$ for $t\in[T]$, define $\mathbf{Z}_{t}=\lambda\mathbf{I}+\sum_{i=1}^{t-1}\mathbf{x}_{i}\mathbf{x}_{i}^{\top}$. Then, provided that $\|\mathbf{x}_{t}\|_{2}\leq L$ holds for all $t\in[T]$, we have

$$ $\displaystyle\sum_{t=1}^{T}\min\{1,\|\mathbf{x}_{t}\|_{\mathbf{Z}_{t}^{-1}}^{2}\}\leq 2d\log(1+TL^{2}/(d\lambda)).$ $$

###### Lemma C.1 (Azuma–Hoeffding inequality, Cesa-Bianchi and Lugosi 2006 ) .

###### Lemma C.2 (Lemma 9 Abbasi-Yadkori et al. 2011 ) .

###### Lemma C.3 (Lemma 11, Abbasi-Yadkori et al. 2011 ) .

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: Please address the weaknesses of the paper. I have a few more questions/comments:
1. Is the maximum likelihood estimator $\theta_t$ biased due to the small weights of some data without no adversarial manipulation, which is possible as $ ||\phi_i|_ {\Sigma_i^{-1}}$ may be large in the initial rounds.

2. Is there a way to set the weights $(\alpha)$ without knowing the amount of adversarial feedback?


**Minor comment:**
1. Line 248 - Line 293 (expect algorithm description) may not be needed as this is not critical, but it can n create confusion due to the use of Taylor approximation. 

2. The authors can check the following paper that considers non-linear reward functions in contextual dueling bandits:
Verma et al., [Neural Dueling Bandits](https://arxiv.org/pdf/2407.17112).

I am open to changing my score based on the authors' responses.
soundness: 3
strengths: **The following are the strengths of the paper:**
1. This paper considers a contextual dueling bandit problem with adversarial preference feedback, which is motivated by real-world applications like training LLMs using RLHF.

2. The authors propose a contextual dueling bandi algorithm RCDB that handles adversarial manipulations and then show that RCDB achieves a nearly optimal regret bound.

3. Finally, the authors have demonstrated the different performance aspects (comparing the regret bound of existing dueling bandit algorithms and regret vs the amount of adversarial feedback) of the proposed algorithms on synthetic problem instances.
summary: This paper studies the contextual dueling bandit problem with adversarial preference feedback in which adversaries may intentionally provide misleading preference feedback. The goal is to design an algorithm that is robust to these adversarial manipulations and has sub-linear regret, i.e., the sum of the difference between two times the maximum reward and total reward of a selected pair of arms.

The authors propose an algorithm named RCDB (Robust Contextual Dueling Bandits) for this problem, which uses uncertainty-dependent weights in the maximum likelihood estimator. They have shown that RCDB achieves a nearly optimal regret bound as long as the number of adversarial feedback, $C=O(\sqrt{T})$. Finally, the authors have shown that RCDB outperforms existing algorithms with various adversarial strategies in different synthetic scenarios, validating its robustness and effectiveness.
weaknesses: **The following are the weaknesses of the paper:**
1. The proposed algorithm RCDB assumes the reward function is linear, which may limit its applicability to real-world settings where the reward functions are non-linear. Even though one can assume a feature map ($\phi$) exists for which reward is a linear function. However, a feature map must be known upfront (Assumption 3.1), which may not always be possible in real-world applications. 

2. The performance of RCDB depends on accurately tuning the tolerance threshold $\alpha$ and confidence bound $\beta$, which may vary depending on the number of adversarial feedback. In practice, knowing the amount of adversarial feedback upfront may be impossible (as they are adversarial).

3. It is unclear how to distinguish among the following cases:

    1. Two actions have similar rewards; hence, the preference probability is close to 0.5.
    2. A weak labeler who gives bad quality preference feedback, which may be common in practice.
    3. Adversarial labeler who manipulates the feedback

4. It is not clear why setting weights as defined in Eq. (4.3) is a good approach to dealing with adversarial feedback because it is possible that there is no adversarial feedback in data and still has a high uncertainty.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. It seems to me that the main algorithm is a somewhat extension of the non-dueling counterpart in He et al 2022, i.e., the same uncertainty weight and the same update rule of the weights. Except for the possible non-linearity in dueling (logistic) bandit (which can be handled by existing techniques), it seems to me that the proposed algorithm and its analysis largely follow from prior work. 

2. As the dependence of \kappa is a key factor in the logistic bandit, can the authors comment on the optimality of \kappa in the regret upper bound (for both non-corrupted and corrupted terms)?

3. If I understand it correctly, there are two commonly used corruption models. One is the total budget model used in the current paper and the other is the strong corruption model from robust statistics (see Definition 3.1 in [R1). In general, these two models are not comparable. But, given the fact that under the dueling bandit setting, the label is only 0 or 1, it seems to me that these two models are somewhat comparable, especially given the fact the current paper considers the strong adversary model where the adversary can observe the actions. It would be good to see some comments on the comparison of the two commonly used corruption models, i.e., if they are equivalent or one implies the other one. This kind of discussion is useful, since it might make the current results even stronger in the sense that it can be used to talk about some results in another corruption model. 



[R1] Zhang, Xuezhou, et al. "Robust policy gradient against strong data corruption." International Conference on Machine Learning. PMLR, 2021.
soundness: 3
strengths: + The problem is timely and important
+ The proposed algorithm achieves (nearly) optimal performance bounds
+ Experiments are also provided
summary: This paper introduces a new approach for contextual dueling bandits under adversarial feedback by proposing the Robust Contextual Dueling Bandits (RCDB) algorithm. RCDB incorporates uncertainty-weighted maximum likelihood estimation (MLE) to handle adversarial interference in preference labels, aiming to minimize regret even in adversarial scenarios. The algorithm achieves a near-optimal regret bound that is robust to adversarial feedback, showing both a baseline optimal performance in uncorrupted cases and effective scaling with adversarial interference. Extensive experiments validate RCDB’s superiority over existing dueling bandit algorithms under various adversarial conditions, underscoring its potential for applications that rely on preference-based learning models.
weaknesses: - Some technical novelty needs to be clarified

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. In Assumption 3.1., you assume the reward is a linear model. Can your method extend to non-linear cases?
2. How to choose the value of the regularization parameter in algorithm 1 specifically?
3. In the experiment setup, you choose the sigmoid function for the preference model. How about the other preference model?
soundness: 3
strengths: It is good to provide both upper bound and lower bound for the problem of contextual dueling bandits with adversarial feedback. And they also provide both theoretical and experimental results.
summary: The paper studied contextual dueling bandits with adversarial feedback and proposed an uncertainty-weighted MLE algorithm. The authors also provided theoretical upper bound and lower bound for regret. And they also run experiments to verify their findings.
weaknesses: See questions for more details.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. The main concern is regarding theoretical contribution. Could you explain the nontrivial theoretical contribution?
2. Could you provide a more detailed formulation for $\sigma$?
soundness: 3
strengths: 1. They study dueling bandits under adversarial feedback, which has not been studied before.
2. The achieved regret bound is near optimal.
3. They demonstrate their algorithm using synthetic datasets.
summary: The authors study contextual dueling bandits under adversarial feedback. They propose an algorithm, RCDB, which utilizes uncertainty-weighted maximum likelihood estimation (MLE). The algorithm achieves a regret of $\tilde{O}(d\sqrt{T} + dC)$, where $C$ is the total number of adversarial feedback instances. They also provide a regret lower bound, showing that the achieved regret bound is nearly optimal. Finally, they conduct numerical experiments to demonstrate the superiority of the proposed algorithm over state-of-the-art dueling bandit algorithms.
weaknesses: 1. The weighted version for the estimator of dealing with corruption was first proposed in He et al. 2022. Their method is highly rely on this method.

2. For the unknown number of adversarial feedback, it requires the information of upper bound of C.

3. There seems to be a lack of novelty in theoretical analysis.

Meta-review: This paper examines the contextual dueling bandit problem with potentially adversarial feedback and proposes a robust algorithm. The algorithm is shown to achieve a regret upper bound that depends on the total amount of adversarial feedback, $C$. The main weaknesses include the requirement of knowing $C$ in advance, the limited technical novelty, and the restriction of the approach to linear models. 

I do not consider the limitation to linear models to be a significant issue in itself. However, since the primary motivation of the paper is the application to training large language models (LLMs) via RLHF, it is essential to provide a justification for the use of linear models in this context, which is insufficiently addressed in the paper. 

The reviewers’ evaluations are borderline, but the above concerns remain unresolved and lean slightly negative. Therefore, I cannot support the acceptance of this paper.

Decision: Reject