Learning from Imperfect Human Feedback: A Tale from Corruption-Robust Dueling

We are happy to hear that the reviewer finds our paper “with a quite complete picture and nice results”. The reviewer has two major concerns/questions, which we believe we can fully address below (including clarifying a major misunderstanding about our assumption). Given the reviewer’s already positive impression and our resolution of both concerns, we would be grateful if the reviewer could consider re-evaluating our paper’s rating.

[W1 & Q1: stringent assumption on link functions]

We believe there might be some major misunderstandings here. Specifically, many natural link functions satisfy our assumptions, including the sigmoid function (as the reviewer mentioned), the cumulative Gaussian distribution function, and the linear function. We guess what the reviewer might have missed is that, we only require $\sigma(x)$ to be concave for x>0 (whereas the reviewer probably overlooked the x>0 condition and thought it has to be concave across the entire $\mathbb{R}$). The rotation-symmetry property then immediately implies that $\sigma(x)$ is convex for x<0. So it is really the same shape as sigmoid function (i.e., first convex and then concave), but is strictly more general by relaxing the specific format of sigmoid to a few smoothness properties. We remark that these assumptions about the link function are quite standard, and essentially no difference from the original (and widely-followed) dueling bandit paper in [Yue & Joachims, 2009; Kumagai, 2017].

In fact, our purpose of imposing these assumptions is exactly trying to be more general than merely sigmoid link functions [Maystre & Grossglauser, 2017; Saha, 2021; Xu et al., 2024] or linear link function [Ailon et al., 2014; Chen & Frazier, 2017; Zimmert & Seldin, 2018; Lin & Lu, 2018], as assumed in some earlier works . We will revise our discussions here to more clearly reflect this as a strength of our work, rather than a limitation. Please refer to the updated draft (lines 153-157).

[Q2: Regret upper bound for unknown $\rho$]

Please refer to the Common Response CR1, which we believe should fully address this question. We are happy to correspond with the reviewer if any further questions come up.

[Additional remarks]

Thank you for pointing out the inaccuracy in Lemma 3.1. In addition, we rely on the fact that $l^{\sigma}_1 > 0$. Since $R^{\mu}$ is finite, there exists a positive constants $l^{\sigma}_1 > 0$ and $L^{\sigma}_1 > 0$ such that $l^{\sigma}_1 \leq \sigma' \leq L^{\sigma}_1$ on $[- R^{\mu}, R^{\mu}]$. We made it explicit in the revised version. Please refer to the updated draft (lines 153-157) and Lemma 3.1.

[W1.1 - 1.3: discuss more relevant work]

We sincerely appreciate the reviewer's suggestion to include additional literature review, particularly regarding points 1.1, 1.2, and 1.3. One key distinction of our work lies in addressing corrupted dueling feedback, where the feedback is binary (0 or 1), providing significantly sparser information compared to standard bandit reward feedback, which contains observable numerical values. This fundamental difference partially explains why our methodology diverges from the approaches discussed in the suggested references.

That said, we acknowledge the importance of providing a more comprehensive discussion and are willing to expand on these points. However, given the space constraints, we decide to prioritize comparing our methodology to more closely related work, as we mentioned in Comparisons with Related Works in the Introduction section.

[W1.4 & Q1: validity of assumptions]

We respectfully point out that while these assumptions appear “complex”, but at the heart they are mostly standard regularity and smoothness assumptions that have been widely used in previous literature as well. We provide detailed clarifications below.

Assumption on link function:

Our assumption already includes many natural link functions, such as sigmoid function, the cumulative Gaussian distribution function, and the linear function. In fact, our purpose of imposing these assumptions is exactly trying to be more general than merely sigmoid link functions [Maystre & Grossglauser, 2017; Saha, 2021; Xu et al., 2024] or linear link function [Ailon et al., 2014; Chen & Frazier, 2017; Zimmert & Seldin, 2018; Lin & Lu, 2018], as assumed in some earlier works . We will revise our discussions here to more clearly reflect this as a strength of our work, rather than a limitation. Please refer to the updated draft which highlighted in blue.

Assumption on utility function:

We assumed strong concave utility functions. This is standard due to at least two reasons. First, there is already a rich literature studying online optimization of strongly convex or concave functions, and our work subscribes to that rich literature [Shamir, 2013; Kumagai, 2017; Wan et al, 2021; Saha et al, 2022]. Second, strongly concave utilities functions capture essential properties like diminishing marginal returns and risk-averse behavior. These characteristics align closely with real-world scenarios in economics, behavioral studies, and decision-making processes. Strongly concave functions are frequently utilized in economic literature for modeling utility functions such as the "indirect utility function" [Montrucchio, 1987; Sorger, 1995; Venditti, 1997], which represents the maximum utility a consumer can achieve based on a specific income level and set of prices.

When the user exhibits strictly concave utility, we have theoretical guarantees in Proposition 3.

Assumption on action spaces:

The assumptions of a continuous action space are standard in the online convex optimization literature [Flaxman et al., 2004; Shamir, 2013; Kumagai, 2017; Yue & Joachims, 2009]. Moreover, they are particularly natural for today’s preference learning for recommendation systems since languages, texts, videos are mostly processed as embedding vectors which are continuous by nature. The reviewer can find this motivation description in Line 93-96.

[Q2: Computational complexity and running time] Please refer to the Common Response CR2 for computational complexity. For running time, for RoSMID, it takes around 45 minutes for running T= 10^5 with $d = 5$, and for DBGD, it takes around 21 minutes, using Google Colab.

I would like to appreciate authors for getting back to me on my concerns. I have a better understanding of your work now.

For my concern 1.1-1.3, I understand that due to the space limit you can't include too much discussion to expand on these points. I know the dueling bandit only outputs binary feedback instead of a numeric one, but I can't tell if that will bring about extra difficulty. From my experience with dueling bandits, the technical analysis is not much more challenging and different compared with multi-armed ones. Therefore, I think it would be better to include more work on robust bandits and robust bandits on continuous space to highlight the technical contributions of yours. I kindly suggest adding a more comprehensive related work discussion as 1.1-1.3 at least in Appendix in the revision. That helps me understand your work a lot.

For my concern 1.4 and Q1, I also recommend you add this detailed discussion in your Appendix along with the related work expansion in the revision. That also helps me appreciate your work, and otherwise these assumptions look not very natural to me

For Q2, I think that is an important result and thanks for sharing. It would be better if you could add this running time information with more details in the revision, at least in Appendix.

Thank you. I will still keep my rating as 6 on this work for now.

We thank the reviewer for appreciating the value of our work. We respond to the reviewer’s criticisms mentioned in weaknesses and answer the raised questions in the following.

[W1 & Q1: knowledge of $\rho$]

In terms of Knowledge of $\rho$, please refer to the Common Response CR1.

[W2: discussion on how the design of RoSMID replies on decaying corruption assumption]

The design of RoSMID is not specifically motivated by the presence or absence of the decaying corruption assumption. Instead, the proof of the tight regret bound heavily relies on this assumption, as discussed extensively in Step 4 in Section 4. Without the decaying corruption assumption, it becomes theoretically challenging to derive a regret bound as tight as the one obtained under the decaying condition.

This challenge arises because the effective bias term that contributes to the regret upper bound is given by $c_t \cdot \sqrt{\lambda_{\max}(\nabla^2 R_t(a_t))} \cdot \|a_t - a^*\|_T$.

Notably, $\sqrt{\lambda_{\max}(\nabla^2 R_t(a_t))}$ scales as $\sqrt{t}$. If $c_t$ follows a decaying corruption condition, such as $c_t = t^{\rho-1}$, then in cases like $\rho = \frac{1}{2}$, the product $c_t \cdot \sqrt{\lambda_{\max}(\nabla^2 R_t(a_t))}$ stabilizes to a constant or increases monotonically when $\rho > \frac{1}{2}$.

This decaying property is theoretically advantageous because it introduces a well-behaved structure for the bias term. This structure can be effectively bounded using tools like the Abel summation lemma, facilitating the derivation of a tight regret bound.

[W3: computational efficiency and scalability]

Please refer to the Common Response CR2.

[Q2: is the continuous action space setting inherently more challenging to address than discrete action spaces under imperfect feedback? Could the proposed algorithm be adapted to discrete action spaces]

It is an intriguing question whether learning in continuous action spaces is more challenging than in discrete action spaces, or vice versa. Currently, these two settings employ distinct methodologies: gradient-based methods are typically used for learning in continuous action spaces [Ailon et al., 2014; Yue & Joachims, 2009; Kumagai, 2017], whereas UCB-type algorithms are commonly applied in discrete action spaces for utility estimation [Saha, 2021, Di, et. al, 2024]. However, these approaches and the challenges they address are not directly comparable due to the inherent differences in the action spaces. Exploring whether a unified methodology can effectively handle both settings would be an intriguing and valuable direction for future research.

References

Nir Ailon, Thorsten Joachims, and Zohar Karnin. Reducing dueling bandits to cardinal bandits, 2014

Yue, Y., & Joachims, T. (2009, June). Interactively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning (pp. 1201-1208).

Wataru Kumagai. Regret analysis for continuous dueling bandit. Advances in Neural Information Processing Systems, 30, 2017.

Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. Advances in Neural Information Processing Systems, 34:30050–30062, 2021.

Qiwei Di, Jiafan He, and Quanquan Gu. Nearly optimal algorithms for contextual dueling bandits from adversarial feedback. arXiv preprint arXiv:2404.10776, 2024.

We acknowledge that it indeed remains unclear whether an algorithm exists that achieves a matching bound as stated in Theorem 3.1 or if the lower bound for learning strongly concave utility functions under arbitrary adversarial corruption is inherently stronger. Closing this gap turns out to be a quite non-trivial question, despite our continuous effort even after the deadline. Currently, our gathered results and insights seem to support the conjecture that such an algorithm may be achievable. We have also mentioned in lines 536–538 that an intriguing direction for future research is to develop algorithms that achieve $\mathcal{O}(\sqrt{T} + T^{\rho})$ regret for strongly concave utilities under arbitrary adversarial corruption.

Furthermore, learning from strictly concave utility functions remains a longstanding open problem that has persisted for approximately 20 years [Belmega et al., 2018]. Specifically, there is a gap between the $\Omega(\sqrt{T})$ lower bound and the current best-known algorithms for learning strictly concave functions under bandit feedback, which only achieve a regret of $O(T^{\frac{3}{4}})$. Therefore, it is still meaningful to provide a robustness of the state-of-art algorithm under unknown corruption, even though the bound on $T$ might not be optimal.

Reference

Belmega, E. V., Mertikopoulos, P., Negrel, R., & Sanguinetti, L. (2018). Online convex optimization and no-regret learning: Algorithms, guarantees and applications. arXiv preprint arXiv:1804.04529.

We thank the reviewer for appreciating the value of our work, and believe most (if not all) of the reviewers’ concerns could be addressed. Please see our answers below and we would be eager to correspond with the reviewer, if there are any follow-up questions.

[W1 & W2: is the assumption of decaying corruption scales too strong?]

Our perspectives: it is a reasonable assumption for our purpose of learning from imperfect feedback. Certainly, coming up with better assumptions is an interesting future direction, but not a trivial task. The reviewer’s proposal of constant bias is also not ideal. Please see our more detailed clarifications below.

First, we appreciate the reviewer’s suggestion that human labelers may exhibit persistence bias. Our model actually captures this situation as a boundary case, with $\rho = 1$ and total corruption linear in $T$. It is not difficult to realize that this setting is not learnable – suppose the reward is always corrupted by a small yet unknown constant c, an algorithm can never figure out this c hence necessarily suffers linear regret. We mention this to respectfully point out that coming up with more natural models may not be as easy as the reviewer had thought, and our model is a reasonable starting point which hopefully could spur more thoughts from the community.

Second, the decaying constraint assumption may not be as restrictive as the reviewer might have thought. Particularly, we show that it does share the same learning lower bound as the scenario without such a constraint (see lines 229–240 and Theorem 3.1), implying that both scenarios exhibit comparable levels of learning difficulty.

Finally, the decaying constraint assumption is indeed grounded in much human behavior studies, and we are not the first to adopt it in learning human preferences (see cited previous works such as [Immorlica et al., 2020; Yao et al., 2022; Wang et al., 2023]). It simply captures the situations that noises or mistakes made by humans will decrease as time goes. While persistent bias may not always be like this, but many other human behaviors are like this. For instance, human labelers’ mistakes during labeling science questions will naturally decrease. Our methods are applicable to these situations.

References

Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu. Incentivizing exploration with selective data disclosure. In Proceedings of the 21st ACM Conference on Economics and Computation, pp. 647–648, 2020.

Chaoqi Wang, Ziyu Ye, Zhe Feng, Ashwinkumar Badanidiyuru, and Haifeng Xu. Follow-ups also matter: Improving contextual bandits via post-serving contexts, 2023.

Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu. Learning from a learning user for optimal recommendations. In International Conference on Machine Learning, pp. 25382–25406. PMLR, 2022.

We do have algorithm-independent lower bounds in this setting and the trade-off is in fact inherent. Please refer to the following two algorithm-independent lower bounds and our updated draft lines 477-481. The algorithm-independent lower bound are stated as follows.

1. For any learner with uncorrupted regret bound $\text{Reg}$, there exists a linear utility function $\mu$ and a link function $\sigma$ such that when the total corruption level $C = \Theta(\text{Reg})$, it will induce linear regret (See Appendix D.2).

2. For any learner with an uncorrupted regret bound $\text{Reg}$, there exists a strongly concave utility function $\mu$ and a link function $\sigma$ such that, when the total corruption level $C = \Theta(\sqrt{\text{Reg} \cdot T})$, the learner will incur linear regret (see Lemma C.1).

These algorithm-independent lower bounds demonstrate that improved learning efficiency comes at the expense of reduced robustness against unknown adversarial corruption.

First, we argue that strong concavity is a standard assumption, due to at least two reasons. (A) There are already a rich literature studying online optimization of strongly convex or concave functions, and our work subscribes to that rich literature [Shamir, 2013; Kumagai, 2017; Wan et al, 2021; Saha et al, 2022]. (B) strongly concave utilities functions capture essential properties like diminishing marginal returns and risk-averse behavior. These characteristics align closely with real-world scenarios in economics, behavioral studies, and decision-making processes. Strongly concave functions are frequently utilized in economic literature, particularly in modeling utility functions such as the "indirect utility function" [Montrucchio, 1987; Sorger, 1995; Venditti, 1997], which represents the maximum utility a consumer can achieve based on a specific income level and set of prices.

Second, we do have results under weaker utility assumption for strictly concave utility, though we did not view that as our main results, and embedded into the robustness-efficiency tradeoff analysis since we thought that is a deeper and more insightful phenomenon. For example, Proposition 3 extends the current state-of-the-art DBGD algorithm, which is capable of learning from generally concave utilities, by generalizing its regret bound of $O(\sqrt{d}T^{\frac{3}{4}})$ (achieved with $\alpha = \frac{1}{4}$) to a more flexible bound of $O(\sqrt{d}T^{1 - \alpha} + \sqrt{d}T^{\alpha + \rho})$, where the total corruption is bounded by $T^{\rho}$. This result highlights the trade-off between learning efficiency and adversarial robustness, which can be achieved by appropriately tuning the learning rate, as discussed in lines 464–469.

References

Alain Venditti. Strong concavity properties of indirect utility functions in multisector optimal growth models. Journal of Economic Theory, 74(2):349–367, 1997.

Gerhard Sorger. On the sensitivity of optimal growth paths. Journal of Mathematical Economics,24(4):353–369, 1995.

Luigi Montrucchio. Lipschitz continuous policy functions for strongly concave optimization problems. Journal of mathematical economics, 16(3):259–273, 1987.

Ohad Shamir. On the complexity of bandit and derivative-free stochastic convex optimization, 2013.

Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization with general preferences, 2022. URL https://arxiv.org/abs/2210.02562.

Wan, Y., Tu, W. W., & Zhang, L. (2022). Online strongly convex optimization with unknown delays. Machine Learning, 111(3), 871-893.

[W1: better emphasis of analysis novelty]

We thank the reviewer for their feedback. Our main technical contribution is a new framework for analyzing the regret of gradient-based algorithms under arbitrary corruptions. This framework introduces a novel regret decomposition lemma for dueling bandits, which upper bounds total regret by combining decision regret and feedback error due to corruption, based on quantifying bias in gradient estimation. Please refer to our updated draft in the introduction section which now highlights this contribution in blue for your suggestions.

[W2: why need a lemma (i.e., Lemma 3.1) to discuss direct reward feedback?]

This lemma is stated just as an intermediate step for the proof of Theorem 3.1, which is why it is named a lemma. At a high level, the proof of Theorem 3.1 has two major steps: (1) proving a lower bound for the direct reward feedback setting (intuitively an easier problem); (2) converting the above lower bound to the (intuitively more difficult) problem of dueling feedback. It just happened so that step (1) above was the core difficulty of the proof, hence we stated it as a lemma.

Firstly, we would like to highlight that our robustified algorithm maintains the same computational complexity as the original algorithm of NC-SMD [Kumagai, 2017]. This demonstrates that our addition of robustness did not compromise computational efficiency, ensuring that the enhanced algorithm remains practical and scalable for real-world applications.

RoSMID’s running time is $O(d^3 T)$, where d^3 comes from singular value decomposition.

Robustified DBGD runs in $O(dT)$, if we assume $P_{A}(a_t + \delta u_t)$ can be effectively performed by matrix transformation

Since we are the first to address corruption-robust learning from a continuous-action strictly-concave utility, there is no existing literature that directly matches this exact setting for comparison. However, we provide some closely relevant ones for the reviewers’ reference.

1. RCDB’s [Di. et al, 2024] running time is $O(K^2 d^2 T)$ for learning from linear contextual dueling bandit under corruption, $K$ is the number of actions

2. Versatile-DB’s [Saha & Gaillard, 2022] running time is $O(K^2 T)$ for learning from dueling bandit in multi-armed setting under adversarial attacks, $K$ is the number of arms

References:

Qiwei Di, Jiafan He, and Quanquan Gu. Nearly optimal algorithms for contextual dueling bandits from adversarial feedback. arXiv preprint arXiv:2404.10776, 2024.

Aadirupa Saha and Pierre Gaillard. Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 19011–19026. PMLR, 17–23 Jul 2022. URL https://proceedings.mlr.press/v162/saha22a.html.