Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback

Thanks for your valuable feedback. We will address your concerns one by one.

Q1: The weighted version for the estimator of dealing with corruption was first proposed in [1]. Their method highly relies on this method.

A1: While the weighted approach to address corruption was initially introduced in [1], it is limited to linear models. In contrast, our method extends this approach to handle nonlinear models. Detailed intuition behind our approach is provided in Lines 230-299, and a direct comparison with [1] is presented in Lines 299-303. Given the thorough citation of relevant literature and the comprehensive discussion of the relationship with prior work, we do not consider this a limitation of our study.

Q2: For the unknown number of adversarial feedback, it requires the information of upper bound of $C$.

A2: As outlined in Section 5.2, selecting a tolerance threshold $\bar{C}$ represents a balance between safety and efficiency—a common trade-off in this field. Moreover, fine-tuning hyperparameters during training to achieve desirable empirical results is a well-established standard practice in the field.

In the absence of fine-tuning, a practical approach is to set $\bar{C} = O(\sqrt{T})$. When the actual corruption level is below $\bar{C}$, the regret achieved is optimal. However, if the corruption level exceeds $\bar{C}$, the algorithm will incur linear regret. This result is optimal in the following sense: Theorem 4.12 in [1] demonstrates that any linear bandit algorithm achieving an optimal regret upper bound in the uncorrupted setting will fail when the corruption level exceeds $\Omega(\sqrt{T})$, where $T$ is the total number of steps. This observation naturally extends to the domain of dueling bandits. When the corruption level reaches $\bar{C} = \Omega(\sqrt{T})$, any algorithm that performs optimally in the uncorrupted case will suffer linear regret.

In general, it is fundamentally impossible to design an algorithm that adapts to an unknown corruption level while simultaneously maintaining efficient performance guarantees in the uncorrupted setting. This limitation is a well-known challenge when dealing with strong adversaries [1][2]. To further clarify this point, we have included a detailed discussion in Remark 5.8.

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

A3: As noted by the reviewer, our investigation of dueling bandits under adversarial feedback represents a novel contribution to the field, as this problem has not been previously explored. Given its relevance to real-world applications such as fine-tuning large language models (LLMs) using reinforcement learning from human feedback (RLHF) and the critical importance of developing robust algorithms, achieving optimal results in both uncorrupted and corrupted scenarios is itself a significant and meaningful achievement.

Moreover, we want to emphasize that we study the dueling bandit problem, which is different from the standard linear bandit problem in [1] and incurs several challenges when using uncertainty-based weight in the dueling bandit. As we study the dueling bandit setting, the feedback is binary, given by a preference model $\mathbb{P}(a \succ b| x) = \sigma(r^*(x,a)-r^*(x,b)).$ This divergence in settings leads to a different analysis. Unlike the weighted regression method, our model employs weighted maximum likelihood estimation (MLE) to estimate the underlying parameter $\theta$. The nonlinearity of the function stops us from having a closed-form solution of $\theta$, thus adding difficulty to obtaining the confidence radius. We bypass this difficulty by utilizing an auxilliary vector function $G_{t}({\theta}) = \lambda\kappa\mathrm{\theta} + \sum_{i = 1}^{t-1}w_i\Big[\sigma\big(({\phi}(x_i,a_i)-{\phi}(x_i,b_i))^\top {\theta}\big) -\sigma\big(({\phi}(x_i,a_i)-{\phi}(x_i,b_i))^\top {\theta}^*\big)\Big]\big({\phi}(x_i,a_i)-{\phi}(x_i,b_i)\big)$. The elliptical potential lemma provides an upper bound of $||G_{t}({\theta})||_ {\Sigma_t^{-1}}$. We bridge the gap between this and the confidence radius $||\theta-\theta^*||_{\Sigma_t}$ by mean value theorem (Lines 967 to 978). Therefore, our proof technique is novel.

[1] He et al., Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions, Neurips2022

[2] Ye et al., Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes, ICML2023

Dear Reviewer 8zGo,

Thank you again for your valuable feedback. In our rebuttal, we believe that we have addressed your concerns about the novelty and the case with unknown corruption level of $C$. As the discussion period is drawing to a close, we wanted to kindly check if you have any additional questions or concerns so that we may address them while there is still time for further discussion.

If our responses have sufficiently addressed your comments, we would sincerely appreciate it if you could consider increasing your score.

Best,

Authors

Thanks for your positive feedback! We will address your concerns one by one.

Q1: In Assumption 3.1., you assume the reward is a linear model. Can your method extend to non-linear cases?

A1: The use of a linear reward model with known features is a well-established setting in the literature on dueling bandits, as demonstrated in works such as [1][2][3]. Extending this framework to handle more general nonlinear settings is an exciting and challenging problem. The primary focus of this paper is on designing algorithms that are robust to adversarial feedback. Developing robust algorithms for nonlinear functions falls beyond the scope of this work. We consider this an important direction for future research.

Q2: How to choose the value of the regularization parameter in algorithm 1 specifically?

A2: In Theorem 5.3, we outline how to select the value of the hyperparameters when $C$ is known. When $C$ is unknown, a practical approach is to begin by choosing a tolerance threshold $\bar{C}$. The choice of $\bar{C}$ reflects a trade-off between safety and efficiency, a common practice in this field. Moreover, in practical scenarios, hyperparameters can be fine-tuned during the training phase to achieve favorable empirical outcomes, which is a well-established convention in machine learning.

Q3: In the experiment setup, you choose the sigmoid function for the preference model. How about the other preference model?

A3: We choose the sigmoid function because it is the most commonly used choice for modeling preference feedback [1][2][3]. As demonstrated in Assumption 3.2, our theoretical results can work for various kinds of preference models. Thus, the algorithm's performance guarantees remain valid when using other preference models.

[1] Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits, Neurips2021

[2] Bengs et al., Stochastic contextual dueling bandits under linear stochastic transitivity models, ICML2022

[3] Xiong et al., Gibbs sampling from human feedback: A provable kl-constrained framework for rlhf. ICML2024

Thank you for your careful review and detailed feedback. We will address your concerns one by one.

Q1: Novelty: It seems to me that the main algorithm is a somewhat extension of the non-dueling counterpart in [1], 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.

A1: We want to emphasize that we study the dueling bandit problem, which is different from the standard linear bandit problem in [1] and incurs several challenges when using uncertainty-based weight in the dueling bandit. As we study the dueling bandit setting, the feedback is binary, given by a preference model $\mathbb{P}(a \succ b| x) = \sigma(r^*(x,a)-r^*(x,b)).$ This divergence in settings leads to a different analysis. Unlike the weighted regression method, our model employs weighted maximum likelihood estimation (MLE) to estimate the underlying parameter $\theta$. The nonlinearity of the function stops us from having a closed-form solution of $\theta$, thus adding difficulty to obtaining the confidence radius. We bypass this difficulty by utilizing an auxilliary vector function $G_{t}({\theta}) = \lambda\kappa\mathrm{\theta} + \sum_{i = 1}^{t-1}w_i\Big[\sigma\big(({\phi}(x_i,a_i)-{\phi}(x_i,b_i))^\top {\theta}\big) -\sigma\big(({\phi}(x_i,a_i)-{\phi}(x_i,b_i))^\top {\theta}^*\big)\Big]\big({\phi}(x_i,a_i)-{\phi}(x_i,b_i)\big)$. The elliptical potential lemma provides an upper bound of $||G_{t}({\theta})||_ {\Sigma_t^{-1}}$. We bridge the gap between this and the confidence radius $||\theta-\theta^*||_{\Sigma_t}$ by mean value theorem (Lines 967 to 978). Therefore, our proof technique is novel.

Q2: 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)?

A2: Thank you for your valuable feedback. In Theorem 5.3, we have demonstrated the dependence of our results on $1/\kappa$. To the best of our knowledge, there is no existing study that examines the optimal dependency of $\kappa$ for dueling bandits in both non-corrupted and corrupted terms. While this is an important issue in logistic bandits, as discussed in the 'Related Works' section (Lines 149-155), it falls outside the scope of our current paper. We will consider this as part of our future work.

Q3: 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. Are they comparable in the dueling bandit setting?

A3: Thank you for your valuable feedback. The key difference between these two models lies in their definitions: the total budget model considers the numerical corruption of the reward, while the strong corruption model focuses on the number of corrupted rounds. In our setting, we consider the label-flipping attack, where the magnitude of adversarial feedback is always 1. Under this condition, the two corruption models are equivalent in the dueling bandit setting. In our revision, we have cited and discussed the mentioned paper to make it more clarified.

[1]: He et al., Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions Neurips2022

Dear Reviewer qjiZ,

Thank you once again for your valuable and insightful feedback. In our revised paper, we have incorporated a detailed discussion on the two types of corruption models mentioned. In our specific setting with binary feedback, they are indeed equivalent. We are grateful for your remarks, which helped us refine this aspect of our work.

Regarding the novelty concern you raised, we have clarified the technical challenges in our rebuttal. Additionally, we believe our work's novelty lies not only in addressing these challenges but also in the importance of the studied setting. To the best of our knowledge, this is the first theoretical result in contextual dueling bandit with adversarial corruption, and drive a optimal performance within this area.

We are reaching out to see if you have any further concerns or feedback. If our responses have adequately addressed your comments, we would sincerely appreciate it if you could consider increasing your score.

Best,

Authors

Thanks for your helpful suggestions and comments. We will address your concerns one by one.

Q1: the reward function is linear, which may limit its applicability to real-world settings where the reward functions are non-linear. Moreover, the feature map must be known upfront.

A1: Using a linear reward model with known features is a well-established framework in the dueling bandits literature, as demonstrated in prior works [1][2][3]. We want to highlight that even in the linear setting, the problem of adversarial feedback by label-flipping has never been fully studied, let alone its extension to general function approximation. Without first establishing a robust and optimal solution for the linear case, generalizing effectively to broader contexts with general reward structures would be highly challenging, if not impossible. Thus, we believe it is important to start with the linear setting as the first step, and the setting we study is significant.

Extending this framework to accommodate more general nonlinear settings is indeed an exciting and challenging direction. After reviewing the paper [4] recommended by the reviewer, we note that it explores approximating the reward model with neural networks, addressing the challenges of nonlinear rewards in dueling bandits. However, the primary focus of our paper is on designing algorithms that are robust to adversarial feedback. Developing robust algorithms for nonlinear functions, such as those modeled with neural networks, falls beyond the current scope of our work. We consider this an important direction for future research. In our revision, we have addressed this limitation and discussed it in the future works section.

Q2: Good performance of RCDB requires accurately tuning the tolerance threshold depending on the number of adversarial feedback.

A2: As outlined in Section 5.2, a practical approach involves selecting a tolerance threshold $\bar{C}$, which strikes a balance between safety and efficiency---a common trade-off in this domain. Moreover, fine-tuning hyperparameters during training to achieve desirable empirical results is a standard practice in the field. Therefore, we do not view this aspect as an issue.

Q3: It is unclear how to distinguish among the following cases:

Two actions have similar rewards; hence, the preference probability is close to 0.5.

A weak labeler who gives bad quality preference feedback, which may be common in practice.

Adversarial labeler who manipulates the feedback

A3: Thank you for raising this insightful question. Let us clarify these scenarios further:

1. Preference Probability Close to 0.5 This situation reflects a fundamental challenge faced by all bandit models: decision-making under uncertainty. In our setting, this uncertainty arises from the randomness of the BTL model. When the preference probability is close to 0.5, the comparison is nearly random, meaning the information gain is minimal. However, this is a normal characteristic of the problem and represents the inherent difficulty of learning from uncertain or low-signal comparisons. Addressing this is central to the challenge of dueling bandits.

2. Weak Labeler In this case, we assume that some of the feedback originates from a reward model $r$ that differs from the true reward $r^*$. This corresponds to a scenario where a labeler has incorrect or inconsistent viewpoints, leading to low-quality feedback.

3. Adversarial Labeler An adversarial labeler poses a more significant challenge. Unlike a weak labeler, the adversarial labeler can exploit full access to contextual information, actions, and true feedback to craft feedback specifically designed to degrade the algorithm's performance. This scenario includes the weak labeler as a special case when we restrict it to corrupt the data aligned with another reward model $r$. However, adversarial behavior is more general and flexible, resembling strategies such as adversarial attacks or misleading attacks, as discussed in our paper. Each of these cases has its own distinct mathematical formulation. The setting we study, which includes adversarial labelers, is the most difficult and general of these cases. Consequently, addressing this setting is very significant.

Dear Reviewer q8Fc,

Thank you once again for your valuable feedback. In our rebuttal, we have carefully addressed the concerns you raised and provided clarifications where needed. Regarding the problem of linear rewards, we have thoroughly reviewed the paper you suggested and think that it can be an interesting future extension of our work. We have included a discussion of its relevance to our work in the revised manuscript.

As the discussion period is close to the conclusion, we want to kindly ask if you have any additional concerns or questions. If our responses have sufficiently addressed your feedback, we would greatly appreciate it if you could consider increasing the score.

Best,

Authors