Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback

Thank you for your positive feedback! We will address your concerns.

Q1: Empirical results for RCDB-S

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})$. Theoretically, 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. This further explains the improved performance as $t$ increases. Therefore, our experimental results are well aligned with the theoretical findings.

Q2: Heuristics to approximate the adversarial corruption level

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.

Q3: Eliminate the $\kappa$-dependence for weak regret

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.

Thank you for your positive feedback! We will address your questions one by one.

Q1: Typos and suggestions

A1: Thank you for pointing these out. We will address them in our next revision.

Q2: The writing of lower bound

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$.

Q3: Relation with Jun et al. (2021)

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.

Furthermore, 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. We will explicitly discuss this comparison with Jun et al.. (2021) in the revised version.

Q4: The combination of ideas and techniques from logistic bandits, adversarial bandits, and dueling bandits is also a minor weakness

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.

We will next address your ''questions for authors'' part.

Q5: Correct $\kappa$

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.

Q6: Referring the reader to Appendix A of Di et al. (2023)

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.

Q7: Local minimax lower bound

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.

Q8: Extend the analysis to self-concordant link function

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.

Thank you for your positive feedback! We will address your concerns.

Q1: Direct extension of He et al. 2022 using standard analysis techniques from the Duelling Bandits

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.

Next, 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.

Finally, 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

Thank you for your feedback. We will address your concerns one by one.

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

A1: We 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]. Moreover, 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.

[1] Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons, Zhu et al. 2023, ICML2023

[2] Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-constraint Xiong et al. 2024 ICML2024

[3] Value-incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF Cen et al.2025 ICLR2025

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

[5] Feel-good thompson sampling for contextual dueling bandits Li et al. 2024 ICML2024

Q2: Relation with He et al. (2022) and Di et al. (2023)

A2: First, 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.

Second, 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).

Last 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.