Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback

Thank you for your insightful comments and suggestions! We answer your questions as follows.

Q1: Technical novelties

A1: We want to emphasize that we study the dueling bandit problem, which is different from the standard linear bandit problem and incurs several challenges when using uncertainty-based weight in dueling bandits. First, the feedback is binary, given by a preference model $\mathbb{P}(a \succ b| x) = \sigma(r^*(x,a)-r^*(x,b)).$ This difference 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 prevents us from obtaining a closed-form solution for $\theta$, adding difficulty in determining the confidence radius. Moreover, our analysis of weights for the nonlinear model in Section 4 is novel. We explain how our weight selection can cancel out the variance, resulting in a more robust theoretical analysis under adversarial feedback.

In our proof, we bypass the difficulty of nonlinearity by utilizing an auxiliary vector function $G_{t}({\theta}) = \lambda\kappa{\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_t}) \|| _ {\Sigma_t^{-1}}$. We bridge the gap between this and the confidence radius $\|| \theta_t-\theta^*\||_{\Sigma_t}$ by mean value theorem (Lines 525 to 527)

To make it clearer, we have provided a roadmap of proof in Appendix A.

Q2: Analysis of unknown $C$ is trivial

A2: While the analysis is simple, it does not diminish the significance of our result that our algorithm is able to achieve optimal regret even when faced with an unknown $C$ (see Remark 5.8). This is also included for the completeness of our work.

Q3: Conditions are not explicitly stated in the assumptions

A3: In Section 4, our argument aims to explain the motivation for introducing uncertainty-based weights. We want to clarify that we provide rigorous proof for the algorithm's performance in Appendix B.1, which relies solely on our specific choice of weights and does not depend on the conditions or analysis from Lines 207 to 210.

In the motivating analysis, we use $\sigma' \le 1$ since for many useful link functions (e.g., sigmoid function), the inequality does hold, In addition, $\phi_t^\top \theta \le 1$ is a typo and we only need $\sigma'( \phi_t^\top \theta^*) \le 1$, which always holds for the sigmoid link function. In our revision, we will correct the typo and make the writing clearer.

Q4: Assumption 3.2 could create bad dependencies in the bounds on $B$

A4: We can calculate $\kappa$ in Assumption 3.2 using $B$. Take $\sigma(x) = 1/ (1+e^{-x})$ for example. $\sigma(x)’ = e^{-x} /(1+e^{-x})^2$. Due to Assumption 3.1, $|(\phi(x,a)-\phi(x,b))^\top\theta| \le 2B$, therefore, $\sigma’((\phi(x,a)-\phi(x,b))^\top\theta) \le 1/(e^{-2B} + 2 + e^{2B})$ for all $a,b \in \mathcal A, \theta$. As a result, $\kappa = 1/(e^{-2B} + 2 + e^{2B})$. Our regret’s dependency on $B$ will be $O(e^{2B} + e^{-2B})$. Usually, $B$ is considered as a constant, , and thus it will not cause bad effects to our regret. Similar dependency on $B$ is widely seen in the literature, for example [1][2][3].

Q4: Hardness of computing the arms

A4: In this work, we assume there is a computation oracle to solve the optimization problems over the action set $\mathcal{A}$ (e.g., Line 6 of Algorithm 1). A similar oracle is implicitly assumed in almost all existing works for solving standard linear bandit problems with infinite arms (e.g., OFUL and CW-OFUL algorithms). Without such an oracle, choosing a pair of actions from the infinite decision set would be computationally intractable.

In the special case where the decision set is finite, we can iterate across all actions, resulting in $O(k^2d^2)$ complexity for each iteration, where $k$ is the number of actions, and $d$ is the feature dimension.

In our revision, we will add more discussion on the computational complexity.

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

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

[3] Li et al. Feel-Good Thompson Sampling for Contextual Dueling Bandits ICML

Thank you for your positive feedback! We answer your questions as follows.

Q1: Challenges to extend the linear reward to more general settings.

A1: It might be possible to consider the corruption problem for a nonlinear reward function class with finite Eluder dimension, like in [1]. However, it is worth noticing that the observed comparison feedback depends on the difference in the reward gap $r(x,a)-r(x,b)$, however, the regret/sub-optimality of the selected action is based on the summation of two reward function $r(x,a)+r(x,b)$. For the linear reward function, both the reward gap $r(x,a)-r(x,b)$ and reward summation $r(x,a)+r(x,b)$ fall into a linear region. However, for a general setting, the gap and summation may share different function classes, which makes it difficult to analyze. This is beyond the scope of our work and we leave it as a future work.

Q2: Will Taylor's expansion impact the regret analysis?

A2: In Section 4, we aim to provide a clear explanation of the chosen weights. Therefore, we apply Taylor's expansion to clarify its relation to the variance and use approximations to illustrate the motivation, making it easier to understand. We want to clarify that we provide rigorous proof for the algorithm's performance in Appendix B.1, which relies solely on our specific choice of weights and does not need to use Taylor’s expansion.

Q3: variance for the experiments

A3: Thank you for your advice. In the uploaded pdf, we have included the variance information for the experiments in the plot.

Q4: Paper is too dense

A4: Thanks for your suggestion. We will restructure the formulas to create more space and improve readability in our revision, given that there is one extra page for camera-ready.

[1] Ye et al.(2023) Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and Markov decision processes.

Thank you for your positive feedback! We answer your questions as follows.

Q1: Hard to follow the paper.

A1: Thank you for pointing out these issues. We will address your concerns one by one:

(1) $\Sigma_t$ appeared without introducing.

Our definition of $\Sigma_t$ is provided in line 3 of Algorithm 1. In our revision, we will add a reference to this definition when we use it to avoid confusion.

(2) specify exactly where in the supplementary materials proofs of these results (Lemma 5.1 ~ Theorem 5.7)

Due to page limits, we do not provide links in the main paper. However, the subtitles in the appendix clearly indicate where the results are proved. To be more specific, the proofs for the main theorems are in Appendix B, while other technical lemmas are placed in Appendix C. We will be sure to specify it in the revision.

(3) The initial weight $w_t$ is not specified before use

It is important to note that for each round $t$, the covariance matrix $\Sigma_t$ in Algorithm 1 (Line 3) only depends on the previous weights $w_1,...,w_{t-1}$. For the initial round where $t=1$, the covariance matrix $\Sigma_t$ is initialized as $\Sigma_1=\lambda \boldsymbol{I}$ and is not related to $w_0$. For subsequent rounds, the weights $w_1,...,w_{t-1}$ have already been calculated in the previous rounds.

(4) Further explanation is needed for lines 204-209. For instance, clarify the property of $\mathcal F_t$-measurability, and explain Taylor's expansion.

In Section 4, we introduce Taylor's expansion to explain the motivation for introducing uncertainty-based weights. We want to clarify that we provide rigorous proof for the algorithm's performance in Appendix B.1, which relies solely on our specific choice of weights and does not need to use Taylor’s expansion.

Intuitively, even without the weighting, a similar analysis to Lemma 5.1 can show that the estimated parameter $\theta_t$ will approach $\theta^*$ with a larger confidence radius, e.g., $||\theta_t - \theta^*||_{\Sigma_t} \leq \tilde{O}(\sqrt{d} C)$. Under this situation, we almost have $| \phi_t^\top \theta - \phi_t^\top \theta^*| \leq \tilde O(\sqrt{d} C) \cdot \||\phi_t|| _ {\Sigma^{-1}} \ll 1$ for a large round $t$, which encourages us to use Taylor's expansion.

For the property of $\mathcal F_t$-measurability, we aim to use the following property of conditional expectation with respect to a sub-$\sigma$-algebra.

Lemma: (Pulling out known factors): If $X$ is $\mathcal {H}$ measurable, then $E[XY|\mathcal {H}] = XE[Y|\mathcal {H}]$. By taking $Y=1$, we have $E[X|\mathcal {H}] = X$. Therefore, when calculating $\sigma(\phi_t^\top \theta_t) - \mathbb E[\sigma(\phi_t^\top \theta_t)| \mathcal F_t]$, the $\mathcal F_t$ measurable part will be canceled out. In our revision, we will add more explanation for our analysis.

(5) Prior to Section 5, it is unclear whether this paper considers both aspects or only one of them.

Thank you for your advice. Our paper considers both known and unknown number of adversarial feedbacks. We will add more discussion to clarify this point in our revision.

In our revision, we will modify our paper to address these issues and make the content easier to understand.

Q2:Calculating the argmax might be infeasible

A2: In this work, we assume there is a computation oracle to solve the optimization problems over the action set $\mathcal{A}$ (e.g., Line 6 of Algorithm 1). A similar oracle is implicitly assumed in almost all existing works for solving standard linear bandit problems with infinite arms (e.g., OFUL and CW-OFUL algorithms). Without such an oracle, choosing a pair of actions from the infinite decision set would be computationally intractable.

In the special case where the decision set is finite, we can iterate across all actions, resulting in $O(k^2d^2)$ complexity for each iteration, where $k$ is the number of actions, and $d$ is the feature dimension.

In our revision, we will add more discussion about the calculation complexity.

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

Q1: The title may be a little bit misleading, I think the setting of this paper is the adversarial corruption setting, not the setting with completely adversarial feedback. And the setting is the linear reward model, which is not specified in the title.

A1: In previous studies on standard linear bandit problems, including both adversarial corruption and adversarial bandits, the adversary directly targets the reward. In contrast, our setting involves binary preference feedback rather than direct reward feedback, with the adversary attacking by flipping the preference labels. We use “adversarial feedback” to differentiate our work from prior studies on corrupted or adversarial reward settings, for example [1][2]. Indeed, our setting focuses on the linear reward model, and we will specify this in the title in the revision. Thank you for your suggestion.

Q2: The uncertainty-weighted technique is based on previous works. What are the technical difficulties?

A2: We want to emphasize that we study the dueling bandit problem, which differs from the standard linear bandit problem in [3] and incurs several challenges when using uncertainty-based weights in the dueling bandit context. Specifically, in the dueling bandit setting, the feedback is binary and given by a preference model $\mathbb{P}(a \succ b| x) = \sigma(r^*(x,a)-r^*(x,b))$. This difference in feedback necessitates a different analytical approach.

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$, making it difficult to determine the confidence radius. Additionally, in Section 4, we discuss the weight selection, explaining how our uncertainty-based weights can cancel out the variance of the estimated preference probability.

To overcome the nonlinearity challenge in our proof, we utilize an auxiliary vector function $G_{t}({\theta}) = \lambda\kappa{\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)$. Then, the elliptical potential lemma provides an upper bound of $\||G_{t}({\theta_t}) || _ {\Sigma_t^{-1}}$. We bridge the gap between this and the confidence radius $\||\theta-\theta^*\||_{\Sigma_t}$ by mean value theorem (Lines 525 to 527).

To make it clearer, we have provided a roadmap of proof in Appendix A.

[1] Gajane et al., A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits. ICML

[2] Saha et al., Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences. ICML

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