Learning from Imperfect  Human Feedback: A Tale from Corruption-Robust Dueling
Authors: Yuwei Cheng
Fan Yao
Xuefeng Liu
Haifeng Xu
Venue: ICLR 2025 Poster (2025)
Keywords: online learning
dueling bandit
Primary area: other topics in machine learning (i.e., none of the above)

Abstract: This paper studies Learning from Imperfect Human Feedback (LIHF), addressing the potential irrationality or imperfect perception when learning from comparative human feedback. Building on evidences that human's imperfection decays over time (i.e., humans learn to improve), we  cast this problem as a concave-utility continuous-action dueling bandit but under a restricted form of  corruption:  i.e., the corruption scale is decaying over time as $t^{\rho-1}$ for some ``imperfection rate''  $\rho \in [0, 1]$.  
With $T$ as the total number of iterations, we establish a regret lower bound of $ \Omega(\max\{\sqrt{T}, T^{\rho}\})$ for LIHF, even when $\rho$ is known. For the same setting, we develop the Robustified Stochastic Mirror Descent for Imperfect Dueling (RoSMID) algorithm, which achieves nearly optimal regret $\tilde{\mathcal{O}}(\max\{\sqrt{T}, T^{\rho}\})$. Core to our analysis is a novel framework for analyzing gradient-based algorithms for dueling bandit under corruption, and we demonstrate its general applicability by showing how this framework can be easily applied to obtain corruption-robust guarantees for other popular gradient-based dueling bandit algorithms. Our theoretical results are validated by extensive experiments.

Published as a conference paper at ICLR 2025
LEARNING FROM IMPERFECT HUMAN FEEDBACK: A TALE FROM CORRUPTION-ROBUST DUELING
Yuwei Cheng Department of Statistics
Fan Yao"
Department of Computer Science University of Virginia
University of Chicago Chicago, IL 60637, USA
Charlottesville, VA 22904, USA fy4bcevirginia edu
yuweichhnng@uchiccgg.... edu
Xuefeng Liu"
Haifeng Xu
Department of Computer Science University of Chicago Chicago, IL 60637, USA
Department of Computer Science University of Chicago Chicago, IL 60637, USA hai haifengxxu@uhhccaoo edu
xuefengeuchicago.. edu
ABSTRACT
This paper studies Learning from Imperfect Human Feedback (LIHF), addressing the potential irrationality or imperfect perception when learning from comparative human feedback. Building on evidences that human's imperfection decays over time (i.e., humans learn to improve), we cast this problem as a concave-utility continuous-action dueling bandit but under restricted form of corruption: i.e.. the corruption scale is decaying over time t²-1 for some "imperfection rate" P E [0, 1]. With as the total number of iterations, we establish regret lower bound (mmax (V,, T))) for LIHF, even when p is known. For the same set- ting, develop the Robustified Stochastic Mirror Descent for Imperfect Dueling (RoSMID) algorithm, which achieves nearly optimal regret Omax VT, }T)). Core to our analysis is a novel framework for analyzing gradient-based algorithms for dueling bandit under corruption, and we demonstrate its general applicability by showing how this framework can be easily applied to obtain corruption-robut guarantees for other popular gradient-based dueling bandit algorithms. Our theo- retical results are validated by extensive experiments.
INTRODUCTION
Many real-world problems, such personalized recommendation Yue & Joachims 2009 Immor- lica et al.) 2020; Yao et al.) 2022) and fine-tuning generative models (Bai et al.) 2022 Casper et al., 2023 Han al. 2024), require learning from human feedback. Expressing preferences as numer- ical values or concrete functions is generally challenging for humans. Therefore, an approach that learn humans' preferences by eliciting their com- parative feedback between two options (Bai et al., 2022). A natural theoretical framework capturing such learning task the seminal dueling bandits framework introduced by Yue & Joachims (2009). The dueling bandit problem features a sequential online learning problem, during which a pair of actions are selected at each round and only their comparison result is revealed to the learner. The comparison outcome between two actions is modeled using utility function of actions, alongside a link function that determines the probability of each action winning based on their utility differ- ence. This modeling approach is termed as utility-based dueling bandit and achieves great success in generating summaries closely aligned with human preferences (Stiennon et al.] (202)). However, human feedback is often imperfect, crucial factor that has been largely overlooked in previous studies of dueling bandit. As we are all aware of, humans are not always rational (Posner 1997) neither perfectly know our preferences (Pu et al. 2012). powerful framework that can capture this problem is robust bandit learning under adversarial corruption (Bogunovic et al. 2020 Saha &
has achieved significant real-world success
Equual contribution.

---

Published as a conference paper at ICLR 2025
Gaillard 2022 Di et al. 2024]. However, assuming fully adversarial feedback from regular human seems over pessiiisiiii at the first glance, hence might make our algorithm development overly con- servative. Indeed, ample behavioral studies show that humans often refine their preferences through interactions with the system, navigating a complex tradeoff between exploration and exploitation (Cohen et al. 2007 Wilson et al. 2014). Furthermore, their response errors may exhibit systematic patterns that depend on their past consumption history, rather than merely random noise. Though the sources of imperfections vary lot in human feedback, one common finding in these studies that the feedback's 's imperfection tends to decrease over time, as humans interact more with the system
(Cohen et al.) |007] Wilson al., 2014] [Immrlicca et al.) [2200] Yao et al.) 2022). This premise is the core motivation of this work, which studies dueling bandit learning under corruption that can be arbitrary but have decaying scales.
Our Model and Contributions. We cast Learning from Imperfect Human Feedback (LIHF) as concave-utilityy continuous-action dueling bandit learning problem under adversarial utility corrup- tion yet with decaying scale, upper bounded by O(te-1) at round t, for some P [o, 1] (hence the total amount of attack within time I' is (TT)). A fundamental research question that motivates our study is whether LIHF is fundamentally easier than learning under arbitrarily corrupted feedback.
Our first main technical result hints on potentially negative answer to the above question. We prove a strong regret lower bound of (2 max VT,T") .T))) under LIHF, where d' is the action's dimension. This bound holds even when the decaying rate of imperfection index p is known. This lower bound has the same order as recent lower bounds of dueling bandits under (the harder) arbitrary corruption (Agarwal et al., 2021 Di et al. 2024), thus hinting that learning from imperfect human feedback may be no easier than learning from arbitrary adversarial corruption. Notably, however, we use the phrase "hint", while not an affirmative claim, because our setting with continuous action space and concave utility function is different from the K-armed bandits setting of Agarwal et al. (2021) and linear utility function case Di et al. (2024). Therefore, neither their lower bounds nor their proof techniques are directly applicable to our setting with corruption to strictly concave utilities; see more discussions and comparisons below.
Our second main result is an efficient algorithm with regret upper bound m VT, T")) that matches the above lower bound, up to logarithmic terms, in the same setting (i.e., decaying corrup- tion level 1P-1 with known p). Unlike previous corruption-ron crruptto---obustt dueling bandit algorithms based on robust K-armed bandits (Agarwal et al. [021] robustified LinUCB (Di et al., 2024), our algo- rithm is a gradient-baset algorithm that is built upon the recent Noisy Comparison- based Stochastic Mirror Descent (NC-SMD) of Kumagai (011)). This is natural for our setup with continuous ac- tions and strictly concave utility. While our algorithm itself can be viewed a natural generalization of Kumagai 2017), its analysis is highly non-trivial and much more complex, due to the necessity of accounting for corruption.
Our main technical contribution is new framework for analyzing the regret of gradient-based algo- rithms under arbitrary corruption. 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. It yields a tight analysis of our new algorithm and implies regret bounds for popular existing algorithms in (even fully) adversarial corruption settings, such as the dueling bandit gradient descent (DBGD, Yue & Joachims (2009).
These upper bounds are looser than our lower bound for the LIHF setting. question to understand whether these upper bounds under arbitrary corruption are tight, or the lower bound under arbitrary corruption may be stronger than our lower bound under LIHE. Finally, we conduct simulations which validate our theory.
an intriguing open
Comparisons with Related Works. Since multiple recent works (Agarwal et al. 2021 Saha & Gaillard 2022 Di et al.) 2024) study dueling bandits under arbitrarily adversarial corruption it is worthwhile to discuss the key difference between these works and ours. The first key difference is the setting, which leads to fundamentally different algorithms hence analysis. Specifically, our setting with continuous action space and a completely unknown concave utility function is motivated by addressing problems from modern recommender systems where the action (i.e., contents) space is extremely large, not enumerable, thus often embedded as high-dimensional continuous vectors (Chen al., 2019 2021). ). This setting and our techniques are crucially different from earlier works. Agarwal et al. 2021 Saha & Gaillard (022) consider the K-arm dueling bandit setting and utilizes
2

---

Published as a conference paper at ICLR 2025
the reduction of [Ailon al. (2014) from dueling bandits to multi- K-ammed bandits (MAB); Di et al. 2024) considers linear utility setting where the unknowns is parameter vector 8 and utilizes techniques from linear contextual bandits based on the optimism principle. The methods all rely on parameter estimation which are not applicable to our setting with arbitrary concave utilities. Moreover, they often need to enumerate all actions to identify the best one under optimism, which are not computationally efficient for our setting with continuous action space. This is why our algorithm is gradient-based based and falls within the family of stochastic mirror descent. To the best of our knowledge, this is the first time corruption- robust algorithm is developed for dueling bandits with continuous actions and strictly concave utilities, which is also why is necessary for us to develop a new analysis framework. Additionally, we also note that dueling bandits with strictly concave utility and linear utility are generally not comparable, both terms of their problem difficulties and methodologies. A strictly more general situation is the concave utility case (no need to be strongly concave). however the best upper bound so far for general concave utility is (TT//4) (Flaxman et al. 2005 Yue & Joachims 2009), which are considerably worse than the /2) for linear and for strongly y concave utility.
The second main difference between our work and previous is the more restricted class of adversar- ial environments. Our model motivated by imperfect human feedback whereas previous studies are motivated by arbitrarily adversarial adversaries. Finally, a more subtle difference is that the cor- ruption in our model is on utility with motivations from learning from imperfect human feedback, whereas corruption in all previous settings directly flip the comparison outcome. These two dif- ferences lead to a very different proof techniques of our lower bound. Our proof is more involved because the adversary has limited capability to alter the comparison outcomes. Specifically, the corruption are decaying; moreover, a constant amount of utility corruption only slightly shifts the outcome probability whereas in previous settings each corruption completely changes the outcome.
2 THE PROBLEM OF LEARNING FROM IMPERFECT HUMAN FEEDBACK
Notation. For a positive integer T,, we use [T] to denote {1,2,... T3. We use standard asymptotic notations including (.), (2.). O(.). We use Ō-)) (2(-), 6(-) hide logarithmic factors. We use |1-112 to define L2 norm, || Il to define infinity norm, and Amax (-) to denote maximum eigenvalue.
Motivated by alignment of machine learning models with human preferences (Bai et al. 2022), we study learning from comparative human feedback within the seminal dueling bandit framework ( (Yue) & Joachims
2009) but account for "imperfections" human feedback, as described below.
Basics of Continuous Dueling Bandits. We consider the dueling bandit framework with continuous action set A C IRdd (Yue & Joachims 2009 At each round / E [7]. the learner chooses two actions azya, at to present to some human agent, henceforth denoted as the "user". The user receives utility u(az), (aa)) from the two actions respectively, and will pick one of these actions following a link function (-). In the absence of corruption, the user selects action a, with probability (H(a:) (uaa)) and chooses action af otherwise. Since the comparison outcome has less errors compared to the exact utility value while still carries useful information about the underlying utility function μ,, this form of human feedback has been widely used for learning human preferences (Ailon et al.)
2014 Maystre & Grossglauser 2017 Bengs et al. 2021 Bai et al. 2022).. Following standard assumptions in this field Yue & Joachims 2009 Kumagai 2017). we also assume
1. the action set A is a convex compact set that contains the origin, has non-empty interior, and is contained in d-dimensional ball of radius Rt
2. the utility function ya : A -> IR is strongly concave and twice-differentiable The following constants are useful for our algorithm analysis: μ. is T.*-Lipschitz, a-strongly concave x-smooth, bounded, R ;= sup (MPa.'EAA(O)) - u(a'), and a* == arg max.e.A((()) ((a) is the
unique optimal within A:
3. the link function : R [0, is smooth, rotation-symmetric (i.e. (xx) - =1-o(-z)) and concave for R+ Since Rt is finite, there exists positive 19, Li and R2 such that If 5 L on [- R² R²), and the second derivative is bounded above by itS and Lg- Lipschitz on - R" R. For more detailed discussion on the generality of the modeling assumptions, please refer to Appendix A
I is a--strongly concave for some 0 p()) 2 p(v) + (V)()), x + fly x113 for any J. y E A.
3

---

Published as a conference paper at ICLR 2025
A broad range of natural link functions satisfy our assumptions, including the standard logistic distribution function, the cumulative standard Gaussian distribution function, and the linear function. This distinguishes our work from some prior studies, working with concrete link function formats such as logistic function (Maystre & Grossglauser 2017; Saha 2021 Xu et al.
2024) or the linear
function (Ailon et al. 2014 Chen & Frazier 2017 Zimmert & Seldin 2018: Lin & Lu 2018).
Modeling Imperfect Human Feedback as a Restricted Form of Adversarial Corruption. To incorporate imperfect human feedback, we study generalization of the dueling bandit framework above, by introducing a corruption term, c(a, d'), to the utility difference. Formally, let > a' represent the event where the user chooses over a'. The probability of this event in the presence of corruption c(a, a') is denoted by P(aa > a'), expressed as P(a a') == ((((a) - m(aa) + c(a, We denote the user's preferential feedback under corruption as F(a, a'). referred to as imperfect dueling feedback. Mathematically, F(a, al) follows binomial distribution with mean P(a > d'), as expressed by the following equation.
F(a, = [ w.p. P(aa > d') 0. w.p. 1 Pa-aaaa
The "hat" notation in f and is to emphasize the presence of corruption. When there is no corrup- tion, we use Pa( > a') == al((a) uua')) to represent the probability of the event > a', and F(a, a') to denote the corresponding dueling feedback.
We remark that the term c(a, a') above often called "strong corruption" in the literature of adver- sarial corruption because it can be introduced after observing actions a and a' and the corruption function, c(-), can depend on μ and past actions (Bogunovic et al. 2020 He et al., 2022 Di et al., 2024). The only difference between our model and the above works on adversarial corruption is a natural restriction to the scale of the corrupted term c(a, d'). Our motivation is that human feedback, while imperfect, should not be arbitrarily adversarial and tends to improve as human agent interact with the learner. This motivates our following definition of imperfect human feedback.
Definition 2.1 (p-Imperfect Human Feedback). The human feedback is said to be p-imperfect for some p E [0, 1] if there exists a constant C₁. such that corruption ce ca(a,, df) satisfies (cl(a,, df) S CRL 11 E [
The definition shows that p-imperfect human feedback is mathematically equivalent to a restricted form of strong adversarial corruption to user utility functions. The total corruption is bounded by 3.=1lce(a,, af) S C. which is key parameter influencing the intrinsic difficulty of the learn- ing problem. We thus cast the Learning from Imperfect Human Feedback (LIHF) problem as dueling bandits under strong corruption but with decaying scales. For clarity, we use "arbitrary adversarial corruption" corruption without decaying constraints and "p-Imperfect Human Feedback" as cor- ruption with decaying constraints, as described in Definition 2.1] Through this modeling, we aim to: first create more optimistic framework for LIHF compared to arbitrary adversarial corruption, and second, explore LIHF's intrinsic difficulty to achieve more efficient learning guarantees than those possible under arbitrary adversarial corruption. We direct readers Appendix B for more com- prehensive discussion on challenges in developing robust algorithms for continuous dueling bandits with generally concave utility under arbitrary adversarial corruption.
Several points are worth noting about Definition 2.1 While we are not the first to model imperfect human feedback, we are the first to apply it to dueling bandits with strictly concave utilities. Recent works, motivated by recommendation systems, have explored learning user preferences from imper- fect feedback (Immorlica et al. 2020; Yao et al., 2022, Wang et al., (023). These studies assume that users do not know their true expected reward 0, for each choice (i.e., arm) and instead behave based on an estimated reward ò,. at time 1. The utility difference 10, 0,,l ea is modeled as a decreasing function of time, 18-1, indicating that users improve their preference estimates over time. By viewing the human utility (((a) as the average reward, our modeling of p-Imperfect Hu- man Feedback shares the same spirit; it captures imperfect yet gradually improving human feedback (e.g., s, due to inaccuracies in utility perception or initial ignorance of true preferences). As one of our motivations, when generative models like ChatGPT learn to create personalized content, the user
2 All our results naturally applies to م O, which is significantly easier situation since accumulated corruption is constant in that case. Therefore, we will not explicitly consider in this paper.
4

---

Published as a conference paper at ICLR 2025
could undergo process of preference refinement during interactions with the model. Additionally, our model differs from recent corruption-rouus dueling bandit studies (Komiyama et al. 2015 Saha & Gaillard 2022: Di et al. 2024), which corrupt realized outcomes (c.g., flipping a' > to a' and are motivated by adversaries like malicious users or fraudulent clicks (Deshpande & Montanari, 2013 Lykouris et al. 2018). In contrast, our model focuses on utility corruption caused by imperfect perception of true utility, not outcome manipulation.
Learning goal: regret minimization by Learning from p-Imperfect Human Feedback (p- LIHF). The goal of the learner is to optimize her sequential actions to minimize the following dueling regret in the p-LIHF problem:
T Σ E((u(a") - u(a.)) + o(u(a") - -m(a))) -1)
-o(u(a")-p(aa))
Regr ==
(I)
This regret measure has been extensively studied in prior literature (Yue & Joachims) [209 Komiyama et al. 2015; Kumagai 2017: Saha & Gaillard 2022). Other regret measures, such as the cumulative difference between optimal and obtained utility, are also considered. We discuss the equivalence of various regret measures in Lemma D.1
3 THE INTRINSIC LIMIT OF LIHF
In this section, we study the intrinsic limit of learning from p-Imperfect Human Feedback. We are particularly interested in understanding whether learning from this restricted version of corrupted feedback is fundamentally "casier" than learning from arbitrarily ad adversarial corruption. Somewhat surprisingly, the answer seems to be no, as illustrated by the following lower bound result.
Theorem 3.1. There exists p-Imperfect Human Feedback (see Definition 2.1). strongly con- cave utility function p. and link function o such that any learner has to suffer Regr N Ω (VT, even with the knowledge of p.
Notably, similar lower bound results have appeared in recent studies on adversarial corruption in bandits (Bogunovic et al. 2022), including dueling bandits (Agarwal al., 2021 Di et al. 2024), showing the same lower bound (2dd VT, TT)) (though they often use C' == OTT) to denote total corruption budget). However, a few key distinctions are worth noting. First, Theorem 3.1 presents stronger result, showing that even when corruption decays over time, this structure (which defines our LIHF problem) does not make learning easier. Second, our corruption targets utility values, which is quite different from the corruption of comparison outcomes studied in (Agarwal fully flip comparison outcomes, which
et al. 2021 Di al. 2024). In their case, corruption is critical for promoting sub-optimal arms in their lower hound proofs. However, such full control of the outcome is infeasible in our corruption of only the utility, which only slightly shifts the comparison probabilities since the scale of the corruption is also upper bounded by O(t--1).
The aforementioned difference from previous works (Agarwal al. 2021: Di et al., 2024) also render our proof of Theorem 3.1 fundamentally different from (and much more involved than) their proofs. Specifically, due to limited and diminishing corruption power, the corruption in our LIHF problem are insufficient to completely "mask" the instance as one with a different sub-optimal arm, which is the key strategy in previous lower bound proofs. Thus, our proof has to leverage information-theoretii lower bounds of statistical distributions to understand how small-scale cor- ruption at each round could influence the overall function estimation errors. Core of our proof is the follow lower bound result for a different, and intuitively easier, problem: the standard bandit setup with direct reward feedback shown in Lemma 3.1 below. We then convert this lower bound for direct reward feedback dueling feedback through a linear link function, i.e. (xx) 1+=
Lemma 3.1 (Lower Bound under Direct Reward Feedback). Consider bandit learning with direct reward feedback, where reward r(a) == p(a) + follows standard normal distribution. The action space A is contained in a d-dimensional unit ball, and μ is po(a) := TT 1 ||a]] with 0 E Rd. 10012 S 1. Under p-Imperfect Human Feedback (Definition 2.1, for any T, d < C - and for any learner, there exists a O such that under direct
even with the knowledge of has to suffer regret Regr : TEA (E po(a") ) po((.)} } 2 C,PP
We only consider p 2 1. If <, J, the lower bound degenerates 2(dvT) (Kumagai 2017
5

---

Published as a conference paper at ICLR 2025
Proof Sketch of Lemmal] 3.7 regret incurred by any learner with direct reward feedback is no less than (((dT"). The formulation of such a corruption strategy hinges on the observation that the regret incurred by the learner is bounded below by the sum of the Kullback-Leibbe corrupted reward feedback ét conditioned drawn from {-8, 3.dd for some constant 8 > O. Given an action or and index i, conditioned on the value of the i-th coordinate of 0, 0,, if 0, 0, then 6g is
We aim to show that there exists corruption strategy such that the
(KL. divergence between the distribution of the different values of 0. Specifically, let 0 be uniformly
1
i = (a)) + (o, > 0) + Ea,
||ael | + Σojan,) + Buu, + ca(a000; > 0) E.
2
J#1
Conditioned on 0g < O, the corrupted reward feedback 8%
8 = pa((t) + ca(ar(0, < 0) + Ea, ( 1
||ae11 EOsans) Bar, + ca(arl0; <0) E.
jzt
The noise & follows standard normal distribution. Consider the following corruption strategy which sets ca(a,)0; > 0) := -Bar, and cx (ae((0; < 0) : Bug to minimizes the KL divergence between &z and 8/2- Together with 1-strongly concavity of pe, we can establish
{Ei (o(==)o(aa))) - -mo(a) 2 1/ max [Ei,( ( 3)2 "rg² Since d S d. we
can set B = VOTT" to satisfy |10||2 I 1 and to optimize the aforementioned lower bound. Then we obtain E (===)=((a) mo(as) 2 dC,T%/4. Notice that the corruption level each round is bounded by $1Ia, bl In the scenario when the radius A is upper bounded by 3, the corrup- tion budget each round is bounded by Cxtl-11 It implies that the corruption is p-Imperfect Human Feedback, completing the proof.
Theorem 3. can be proved by converting the lower bound in Lemma 3.1 for direct reward feedback to dueling feedback (see Lemma C.I). Before concluding this section, we note that the strongly concave utility function in the lower bound of Theorem 3.1 not necessary.
particular, Proposi- tion bellow shows that similar lower bound applies to linear utilities as well. This result happens to resolve an open problem posed by Yao et al. (2022) which studies a similar learning from imperfect user problem with linear utility and dueling feedback (they termed it the "learning from learning user" problem), develops a no-regret learning algorithm for that setting, but left the lower bound as an open problem. Proposition| Timplies that their upper bound's 'ss dependence on T is tight. We direct readers to Appendix C and C.2 for proof details of Lemma 3.1 and Proposition [
Proposition 1. There exists an LIHF instance with p-Imperfect Human Feedback (Definition 2. linear user utility μ. and link function a, such that any learner has to suffer Regr Z a(d { (V,, TT)), even with the knowledge of p.
4 AN EFFICIENT AND TIGHT P-LIHF ALGORITHM
In this section, we present a learning algorithm with a regret upper bound that matches the ((d max ( / T/T TP)) lower bound, up to logarithmic term, for the p-LIHF setting discussed in Section 3 Our algorithm, Robustified Stochastic Mirror Descent for Imperfect Dueling (RoS- MID), outlined in Algorithm [ generalizes the Noisy Comparison-Bare Based Stochastic Mirror De- scent (NC-SMD) from Kumagai (017)). ROSMID employs a corruption-aware learning rate, slow down the learning when the imperfection level p is large,
Uo : vlog (dxx with NC-SMD being the special case with p O. Although RoSMID may initially seem like a pretty natural extension of NC-SMD, the choice of optimal 7n in fact through careful derivation from a novel framework for analyzing continuous bandits under utility corruption. We conclude by demonstrating the applicability of this new framework to analyzing other gradient- based al algorithms.
Theorem 4.1. RoSMID satisfies Regr S O(d (o,, for any p-LIHF problem.
The main technical contribution underlying this theorem is novel framework for analyzing contin- uous dueling bandits with arbitrary strongly concave, yet possibly imperfect or corrupted utilities, which we believe has independent value. This framework not only enables a tight regret upper bound analysis, as shown in Theorem 4.1 but also allows to casily derive regret guarantees for other dueling bandit algorithms under adversarial corruption, as demonstrated in Subsection [.] While recent works have explored corruption- regret analysis for dueling bandits with K arms

---

Published as a conference paper at ICLR 2025
Algorithm 1: Robustified Stochastic Mirror Descent for Imperfect Dueling (RoSMID)
Input: Learning rate 7p == V/ (dI'max((.5.p)) p-self--oncorrdan function R time horizon T' tuning parameters À -
Ga 2 o (GL)))
Initialize a = arg min R(aa)
for i [T'] do
Update concordant function R₂(a) R(a) + Ale Σi= a,,l? + +|lal1
Sample direction u4 uniformly at random from a unit sphere 3
Obtain corrupted feedback Flay, az) {0, 1}. for a and aj = ( -1/2
1/2ue
Compute the corrupted gradient: Dt = F(a,, a)) (2R,(a,)) 1/22.m m
Set Oc+11 VR, (VR,(())) - -)ptt)
Output: 0T+1
(ahaa & Gaillard 2022) or linear utilities (Di et al. 2024). neither their algorithms nor analysis can be applied to our setting with arbitrary concave utilities in continuous action space.
The full proof of Theorem 4.1 is quite involved and is deferred to Appendix [ Here, we outline the main ideas, divided into four key steps. Step 1-3 are applicable for analyzing continuous dueling bandits under any form of corruption, whereas last Step 4 is the only step that hinges on the decaying corruption level assumptions of p-LIHH and is also the most involved and novel step.
Proof Sketch. The proof of Theorem 4. is divided into four major steps.
Step 1: quantifying bias of gradient estimation in p-LIHF
Our proof starts from quantifying the bias of the gradient 9e caused by p-Imperfect Human Feedback, as shown in the following Lemma 4.1
Lemma 4.1 (Corrupted Gradients Estimation). The gradient 9t. in Line 6 of Algorithm 7 satisfies
E (âela)) = V Vle=a, Pa(a) E (b.la.).
where Pt(a) := EzEB P(a, > a (e)) (aalaa)-a00) xx) (with B as the unit ball) is the smoothed proba-
bility that at is preferred over any action a, and b, d (P(a, > a)) P(a. at) (=)a(a,)
Step 2: decomposing regret for dueling bandits into regret of decision and feedback error
Core our proof a "regret decomposion" lemma below that upper bounds the regret by two parts: regret of sub-optimal decision making under uncertainty, referred as regret of decision (first term in equation 2 and regret due to corruption, referred feedback error (second term in equation 2
Lemma 4.2 (Regret Decomposition for Dueling Bandits). The Regr of Algorithm 7
satisfies:
Co log (T) sel n,T 21 2F
Regt <
Σ bu (0+ at)
Pp
Regret of Decision
Feedback Frvor
where Co = (2v K + 4Rg (L*)² + L and 07 == $ + - 3)a
Similar regret decomposition has been shown to be useful for reinforcement learning which has di- rect reward feedback (Foster et al. 2023). However, to the best of our knowledge, Lemma 4.2 is the first to exhibit such a decomposition for ducling feedback, which contains much sparser infor- mation than direct reward feedback as in classic RL or online learning. Hence the lemma may be of independent interest for future research on dueling bandits under corruption or erroneous feedback.
Step 3: upper bounding the regret from feedback error
Bounding the regret of decision term in equation 2 is standard. Thus, this step develops novel upper bound for bounding the regret from feedback error, shown below.

---

Published as a conference paper at ICLR 2025
Lemma 4.3 (Feedback Error).
The feedback enror term in equation 2 can be bounded follows:
T
T
by (a= at))
S CidyTTBl Σ
Vilealar, (DlV)((r))))))))) - u((a))
C2dTT + 2dv AVTNT
where C1 ==
2ML and C2 == 2L R /suPaEA Amax (V²R(a)) +
To our knowledge, such bound is new for dueling bandits. The less common term in the bound is vu(a") p(aa)) It comes from the strong concavity of the utility function 14, which implies (be, 0g a²) S |26la 12 S /
/ (u(aa)
p(a))).
Step 4: The iterative regret refinement analysis and resultant optimal learning rate
Our last and also the most intriguing step is pin down the regret upper bound. Given the bounds from previous steps, the only remaining term to upper bound is [
BEE=vAlo Vlca(a af)ly p(at)] in Lemma 4.3 We can upper bound vilcs(ae,a)) by
C2ta- & under p-Imperfect Human Feedback assumption (this is the point where we start to need the decaying structure in Definition I.I). This is a tricky question, since this term involving optimal action a" closely connects to the regret Reg, itself (see equation TD. This is precisely the motivation for our analysis approach of "iterative regret refinement". Concretely, it turns out that a good upper bound for the term A E (E - pla:)) can be leveraged derive good upper bound
for term B == Et= 10- VM(aa) p(a+)) which can then be leveraged to derive a good upper bound for the regret Regr. which can be used to refine the original upper bound of term A, at which point we can re-apply the above refinement process.
Two key factors are essential for the iterative regret refinement mentioned above to result in tight bound, The first step is to derive good upper bound for term B using term A, which shown in Lemma 4.4 The second step is to prove that this iterative refinement consistently improves the regret bound, eventually reaching a limit. This demonstrated by Lemma 4.5] The choice of learning rate VlogT Uo (1/2ax(1/2,p is crucial in the second step; in sense, it is the only choice that converges to the tight regret upper bound Ô (dmax Beeaxx/T,TT) (T,T%) in the limit, rather than exploding the bound.
T. (E - m(ax))) -(())) S +(T++*) for some E [0, 2), then we must
Lemma 4.4. If
have B = E 1P-3 a/ula))j((a)) S 0
To prove Lemma 4.4 we first bound term B by ET= 10-1/2 /--(aa/ cavity of the square root function. The key novelty of our proof is to use the Abel's equation (Williams 1963) re-arrange the term -t=10-1/22 10-1/2 / Blu(a=)~ u(a:)] and establish its con- nection with another term C = Σt (E(u((a)-(())) - u(a))]- We finally connect term C with the term A in the lemma statement, by proving Σ /Elu(a*) pla))] I o(r if (IT -(at)_a(((())_)))) - m(ox) < o(T via concavity of square root. Together with the decay scale 1P-1, which allows p0-1 - (1 + 1)p-1 < 18-2, we obtain the tight bound -
using the con-
-u(())
Armed with Lemma 4.4 we can use it to prove the induction claim (Lemma 4.5p. The challenge in this proof lies in identifying the constant K, which must hold across all iterations, k. of the analysis to ensure the bound remains stable and does not explode.
Lemma 4.5 (Induction Claim). Consider T V2LPLRR and Tp
Vlg (7/2pp]
$- T for some integer k, then we must also have
If Regr
144dK /log T
'If corruption e was arbitrary, then 1/2 is Vflee and the bound could deteriorate to O(T")) in the first T rounds.
8

---

Published as a conference paper at ICLR 2025
1 144dK Vlg TTot It... K is a dustance-depender constant, where K
RegT
max
{Co,
CoCo
Co and C2 defined in Lemma 4.2 and 4.3 respectively,
vlog
4.1 ADDITIONAL. APPLICATIONS OF OUR REGRET ANALYSIS FRAMEWORK
To showcase useful applications of the regret analysis framework above for proving Theorem 4.1 in this subsection we employ the framework to study continuous dueling bandits under arbi- trary and agnostic corruption - i... remove decaying constraints on C and p is unknown to the learner. We analyze natural variants of RoSIMD, which apply to strongly concave utilities, and the well-known algorithm Dueling Bandit Gradient Descent (DBGD) (uue & Joachims 2009), which apply to general concave utilities. The proofs of these results are direct applications of the analysis from Steps 1-3 outlined above (without Step 4, since is the only one requiring knowledge of p and decaying corruption). Additionally, we present these results to offer a set of principled bench- mark algorithms for the experiments in Section 5 One thing to highlight is that our robustified algorithms retain the same computational complexity as the originals, ensuring added robustness without compromising efficiency. For further details, see appendix[G.I]
Efficiency-Robustness Proposition 2 (Efficiency- Robustness Tradeoff in RoSMID). If the total corruption level satisfies
Et (celat, af)) S ((T)), then for any a E [2, 1), if the utility function is strongly concave, for sufficiently large round T, by choosing learning rate nj >/gg T
1. (Robustness) RoSMID incurs Regr S Ó(T + VaT + dT
2. (Efficiency) There exists a strongly concave utility function and a link function a such that Regt suffered by RoSMID is at least St (To) in scenario without corruption.
Proposition 3 Seffeiencc-Robustten Tradeoff in DBGD). If the total corruption level satisfies
E (ee(ar, at)) S O(T)), for any a E (0, 3.. if function is generally concave, for sufficiently large round T, choosing 7 = VT
R and V13L. LeTa for DBGD
V2Rd
1. (Robustness) Reg, incurred by DBGD satisfies Reg S <O(VTTi-o + vdT
2. (Ffficiency) There exists a linear utility function Is and a link function a such that RegT suffered by DBGD is at least Ω (T!-a) in scenario without corruption.
Both propositions illustrate the tradeoff between learning efficiency and robustness to adversarial corruption, achieved through their tunable learning rate np 7, 5 (learning rate in DBGD is 25, direct reader to Algorithm for detail). Specifically, greater tolerance for agnostic corruption (i.e., larger a Proposition 2 results in worse regret non-corrupt settings. A similar robustness- accuracy trade-off has been studied in classification problems with adversarial examples, both em- pirically (Tsipras et al., 2018) and theoretically (Zhang al.) (019).. However, to our knowledge, this is the first formal analysis of such a trade-off in online learning. While expanding the confi- dence region for UCB-type algorithms to handle agnostic corruption linear contextual dueling bandits increases tolerance for corruption but worsens regret- sharing similar idea of trade-off Di et al. 2023)-it unclear if this approach necessarily reduces efficiency. contrast, our work demonstrates that adjusting learning rates in gradient-based based algorithms to enhance robustness against agnostic corruption inevitably decreases efficiency when no corruption is present. In particular, the efficiency statements in both propositions can be interpreted concretely demonstrating that for certain problem instances, increasing robustness necessarily de- creases the learning efficiency of the algorithm. In fact, the "efficiency-robusteess tradeoff* is inherent under unknown adversarial attacks. Lemma E. in the appendix shows that algorithms that learn faster tend to be more vulnerable unknown corruption. However, the nature of this tradeoff varies across different algorithms. It is very intriguing and fundamental open question to study what the optimal tradeoff is under unknown adversarial corruption and how achieve
algorithm-dependent lower bounds,
EXPERIMENTS
In this section, we validate our theoretical analysis of RoSMID and DBGD under p- pmpeeeeec Hu- man Feedback through simulations. We also compare their performance against two baseline algo-

---

Published as a conference paper at ICLR 2025
rithms: Doubler and the heuristic algorithm, Sparring, proposed by Ailon al. (2014). For Sparring, we use bandit gradient descent (Flaxman et al. 2005) as the black box bandit algorithm. We direct readers to Appendix G implementation details.
Experiment Setup. We consider a standard experiment sctup, which adopts a strongly concave utility [
0 a 2 ||a|| [. and logistic link function ((x) [+exp(-2)- We choose 5, and T = 10 Our action space A is a d-dimensional ball with radius R = 10. The preference parameter 0 is randomly sampled from the surface of A. In our problem setting, the optimal action a" = 0 and (a(aa) = 50. We simulate p-Imperfect Human Feedback for P [0.5, 1].
Results and Discussion. Figure I presents a log-log plot of regret versus iteration, t, which the order of regret in T is represented by the slope of the line. Each line represents the average over five trials with different random seeds, and each line corresponds to distinct value of p. The shaded region indicates one standard deviation. In the legend, "o" denotes the estimated order of regret. We estimate it using least squares on the last 1% of the data. Figure [ supports Theorem 4.1 as for p [0.5, 1), the estimated slope is less than p.
RoSMID
107
0.8, a-0.76
1.0, o-1.02
Regret
100
suggesting that the choice of 11p = d7 (1/2.p) for RoSMID results
vlog
in regret bound of at most (TT").
10a
10*
16*
Figure 2 compares the performance of our proposed algorithmss, variants of DBGD and RoSMID, with two baseline algorithms, Sparring and Doubler, in the setting when c is arbitrary and ag- 1/2
Figure 1: Robustness of RoS- MID for p-LIHF
nostic. We set the parameter a 1/4 for DBGD and for RoSMID. When is unknown to the algorithms, these parameter choices enable DBGD and RoSMID to tolerate (TT3/4) levels of unknown corrpption, since the slope estimates are less than 1, implying sublinear regret, aligning with our theoretical predictions. Experimentally. RoSMID demonstrates the best performance under strongly concave utility functions. Sparring performs com- parably to RoSMID, despite being heuristic approach without theoretical guarantees. In contrast, Doubler exhibits the worst performance, likely because its theoretical guarantees are only applicable linear link functions, which differs from our experimental setup. We direct readers Appendix for experiment results with other choice of a for efficiency-robustnes tradeoff.
DBGD
RoSMID
Sparring
Doubler
e:0.2
0:0.45
0:0.34
0:0.99 p:0.5
10a
0:0.35
0:0.99 p:0.6
0:0.96
010.91
0:0.27
0:0.99 p:0.75
10c
10a
10
10a 10
10" 10
101 10
10
Figure 2: For each algorithm, we tested its performance under p-Imperfect Human feedback with p 0.5, 0.6, 0.75. For each p. we presented a line plot of the average regret over five simulations, accompanied by + one standard deviation shown by the shaded region. In the legend, o denotes the estimated line slope, calculated using least squares on the last 1% of the data.
CONCLUSION
In conclusion, this paper enhances the understanding of continuous dueling bandits by addressing p- Imperfect Human Feedback with concave utilities. We established fundamental regret lower bounds, introduced the RoSMID algorithm with nearly optimal performance, and developed a novel regret analysis framework that highlights the inherent efficienny-robustnesss robustness trade-off in gradient-based algorithms. Our experimental results corroborate the thcoretical predictions. A promising future direction is the development of an algorithm that achieves Õ(dvT + dT²) regret for continuous dueling bandits with strongly concave utilities under arbitrary adversarial corruption. Additionally, incorporating contextual information to better model real-world scenarios could further enhance the applicability and robustness of these algorithms. We left these directions for future research.
10

---

Published as a conference paper at ICLR 2025
Acknowledgment. This work is supported by the AI2050 program Schmidt Sciences (Grant G-24-66104), Army Research Office Award W911NF23-1-0030, and NSF Award CCF-2303372. Fan Yao conducted this research while he is visiting the University of Chicago.
REFERENCES
Arpit Agarwal, Shivani Agarwal, and Prathamesh Patil. Stochastic dueling bandits with adver- sarial corruption. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato (eds.), Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceed- ings of Machine Learning Research, pp. 217-248, PMLR, 16-19 Mar 2021. URL https: pppoceediigs.. mnl..mmr.... press satess/v1322 v132/ htw11//agaaaaa22// html.
Nir Ailon, Thorsten Joachims, and Zohar Karnin. Reducing dueling bandits to cardinal bandits, 2014.
Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, al. Training helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:220400866, 2022.
Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paute and Eyke Hüllermeier. Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research, 22(7): 1-108, 2021.
Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust to adversarial attacks, 2020.
Ilija Bogunovic, Zihan Li, Andreas Krause, and Jonathan Scarlett. A robust phased elimination algorithm for corruptiontooleran gaussian process bandits, 2022.
Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al. Open problems and fundamental limitations of reinforcement learning from human feedback. Transactions on Machine Learning Research, 2023.
Bangrui Chen and Peter Frazier. Dueling bandits with weak regret. International Conference Machine Learning, pp. 731-739. PMLR, 2017.
Haokun Chen, Xinyi Dai, Han Cai, Weinan Zhang, Xuejian Wang, Ruiming Tang, Yuzhou Zhang, and Yong Yu. Large-scale interactive recommendation with tree-structured policy gradient. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 3312-3320, 2019.
Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Picter Abbeel, Aravind Srinivas, and Igor Mordatch. Decision transformer: Reinforcement learning via sequence modeling. Advances in neural information processing systems, 34:1 11055004415555 15097, 2021.
Jonathan D Cohen, Samuel M McClure, and Angela Yu. Should stay should go? how the human brain manages the trade-off between exploitation and exploration. Philosophical Trans- actions of the Royal Society B: Biological Sciences, 362((4811:933-944 2007.
Varsha Dani, Thomas Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Annual Conference Computational Learning Theory, 2008. URL httphhttt//aaaa
semantt www.tttrscchll.....ommmo.m org/ /treg//orree CorpusID: 9134969
Yash Deshpande and Andrea Montanari. Linear bandits in high dimension and recommendation systems, 2013.
Qiwei Di, Tao Jin, Yue Wu. Heyang Zhao. Farzad Farnoud, and Quanquan Gu. Variance-awan regret bounds for stochastic contextual dueling bandits, 2023.
Qiwei Di. Jiafan He, and Quanquan Gu. Nearly optimal algorithms for contextual dueling bandits from adversarial feedback. arXiv preprint 240::2404.17774 2024.

---

Published as a conference paper at ICLR 2025
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007, 2004.
Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, pp. 385-394, USA, 2005. Society for Industrial and Applied Mathematics. ISBN 0898715857.
Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making, 2023.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings the Thirty- Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Re- search, pp. 1562-1578. PMLR, 25-28 Jun 2019. URL hntpss:/proceeddngg mmlr.
press/v99 gwwp:/a..uaaaaa.aaagma html
Zeyu Han, Chao Gao, Jinyang Liu, Jeff Zhang, and Sai Qian Zhang. Parameter-effiiient fine-tuning for large models: A comprehensive survey, 2024.
Elad Hazan and Kfir Levy. Bandit convex optimization: Towards tight bounds. In
Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Ad- vances in Neural Information Processing Systems, volume 27. Curran Associates, Inc.,
2014. URL https: CLLe/c39966200 (et.b//aabbb7766666222226362
files/paper/2014/ pdf
Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions, 2022.
Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu. Incentivizing explo- ration with selective data disclosure. In Proceedings of the 21st ACM Conference on Economics and Computation, pp. 647-648, 2020.
Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Robust lipschitz bandits to adversarial corruptions. Advances in Neural Information Processing Systems, 36, 2024.
Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Conference on learning theory, pp. 1141-1154. PMLR, 2015.
Wataru Kumagai. Regret analysis for continuous dueling bandit. Advances in Neural Information Processing Systems, 30, 2017.
Chuang- Chich Lin and Chi-Jen Lu. Efficient mechanisms for peer grading and dueling bandits. In Asian Conference on Machine Leurning, pp. 740-755. PMLR, 2018.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme, Stochastic bandits robust to adversarial corruptions, 2018
Lucas Maystre and Matthias Grossglauser. Just sort it! simple and effective approach active preference learning. In International Conference on Machine Learning, pp. 2017.
PMLR,
Luigi Montrucchio. Lipschitz continuous policy functions for strongly concave optimization prob- lems. Journal of mathematical economics, 16(3):259-273, 1987.
Richard A Posner. Rational choice, behavioral economics, and the law. StAn. I. reV., 50:1551, 1997.
Pearl Pu, Li Chen, and Rong Hu. Evaluating recommender systems from the user's perspective: survey of the state of the art. User Modeling and User-Adapted Interaction, 22:317-355, 2012.
Aadirupa Saha. Optimal algorithms for stochastic contextual preference bandits. Advances in Neural Information Processing Systems, 34:30050-30062 2021.
12

---

Published as a conference paper at ICLR 2025
Aadirupa Saha and Pierre Gaillard. Versatile dueling bandits: Best-of-boot world analyses for learn- ing from relative preferences. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepes- vari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Ma- chine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 19011-19026. PMLR, 17-23 Jul 2022. URL https::/prrceedii:: http:///ccceeddeeeoo mlr 12
62
html
Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization with general preferences, 2022. URL pentts://arxio org/abs/2210) 02562
Ohad Shamir. On the complexity of bandit and derivative-free stochastic convex optimization, 2013.
Gerhard Sorger. On the sensitivity of optimal growth paths. Journal of Mathematical Economics, 24(4):353-300 1995.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021, 2020.
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In International Conference on Learning Representa- tions, 2018.
Alain Venditti. Strong concavity properties of indirect utility functions in multisector optimal growth models. Journal of Economic Theory, 74(2):499-367, 1997. ISSN 0022-0531. doi: https://
htt.org/10..006/jjjee 1996. URL httpp:://ww. www.::/wwwnnneeie..............e wttpt/tt.cccccccccc//c/eee
paticcle/pl//00222551162222
Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. Online strongly convex optimization with unknown delays. Machine Learning, 11 111888871-893, 2022.
Chaoqi Wang, Ziyu Ye, Zhe Feng, Ashwinkumar Badanidiyuru, and Haifeng Xu. Follow-ups also matter: Improving contextual bandits via post-serving contexts, 2023.
Chen-Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory, pp. 1043-1096. PMLR, 2022.
WE Williams. A class integral equations. Mathematicul Proceedings of the Cambridge Philo- sophical Society, volume 59, pp. 589-597. Cambridge University Press, 1963.
Robert C Wilson, Andra Geana, John M White, Elliot A Ludvig, and Jonathan D Cohen. Humans use directed and random exploration to solve the explore-exploit dilemma. Journal of experimental psychology: General, 143(6):2074, 2014.
Wenjie Xu, Wenbin Wang, Yuning Jiang, Bratislav Svetozarevic, and Colin Jones. Principled preferential bayesian optimization. arXiv preprint arXiv:2402.053377 2024.
Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu. Learning from a learn- ing user for optimal recommendations. In International Conference Machine Learning, pp- 25382-25406. PMLR, 2022.
Yisong Yue and Thorsten Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In International Conference on Machine Learning, 2009. URL https:
//api. www.nteetttt..e...m.....e.... www.:seetaannncooo.oo..m wcschhlar..a..cccccooocccccca..e htr.pooaa...rgr/oooruuDD-1111111
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. In International conference on machine learning, pp. 7472-7482. PMLR, 2019.
Julian Zimmert and Yevgeny Seldin. Factored bandits. Advances in Neural Information Processing Systems, 31, 2018
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits Journal of Machine Learning Research, 22((8):1 2021. URL hhtp:: / jmlr.
prc/pappas/w/2/11 753.. html
13

---

Published as a conference paper at ICLR 2025
Appendix to Soorningfrom Imperfect Human Feedback: A Tale from Corruption-Robust Dueling
A DISCUSSION ON THE GENERALITY OF MODELING ASSUMPTIONS
The assumptions of a continuous action space are standard in the online convex optimization litera- ture (Flaxman et al., 2004] Yue & Joachims, 2009 Shamir 2013 Kumagai 2017). Moreover, they are particularly natural for today's s preference learning for recommendation systems since languages, texts, videos are mostly processed as embedding vectors which are continuous by nature. We as- sumed 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 work subscribes to that rich literature (Shamir 2013 Kumagai 2017 Wan al., 2022 Saha jet al. 2022). Second, strongly concave utilities functions capture essential properties like diminish- ing marginal returns and risk-averse behavior. These characteristics align closely with real-world scenarios in economics, behavioral studies, and decision-making processes. Strongly concave func- tions frequently utilized in economic literature for modeling utility functions such 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 of prices. Our assumption on the link function aligns with those in Kumagai (211)) but is slightly stronger than those in Yue & Joachims| (2009). Nevertheless, it encompasses many natural link functions, including the sigmoid function, the cumulative Gaussian distribution function, and the linear function, more general than merely sigmoid link functions (Maystre & Grossglauser, 2017) [021 1; Xu et al. (0024) or linear
link function (Ailon et al.] 2014] & Frazier 2017 Zimmert & Seldin 2018 Lin & Lu 2018)
as assumed in some earlier works.
B CHALLENGES IN DEVELOPING ROBUST ALGORITHMMS FOR CONTINUOUS DUELING BANDITS WITH GENERALLY CONCAVE UTILITY UNDER CORRUPTION INDUCED BY STRONG ADVERSARY
There is a line of work that studies bandits under corruption by a weak adversary (Lykouris et al., 2018 Gupta et al. 2019] Agarwal al., [021] Zimmert Seldin 202T] [ahha & Gaillard [202]] Weil et al. 2022), where the corruption is introduced before observing the agent's actions. This research develops efficient algorithms that achieve sublinear regret without requiring prior knowledge of the total corruption. Specifically, for corruption induced by weak adversary. Wei et al. (2022) adopts the idea of model selection and introduces a robust framework called Corruption-Robut Robustness through Balancing and Elimination (COBE). This framework allows algorithm designed for known corruption level to be adapted for scenarios with an unknown corruption level. Notably, in the case of weak adversaries, Zimmert & Seldin (2021) )); Saha & Gaillard (2022) develop "best-of-both- world' algorithms, which achieve optimal performance under both begin and corrupted settings.
However, for corruption induced by strong adversary-whert the corruption occurs after observing the agent's s actions (the scenario considered in our setting) it may not be possible to develop a best- of- world algorithm. This limitation arises because, for any algorithm that does not know the total corruption, there exists problem instance where the algorithm suffers linear regret (Bogunovic al., 2020 Kang et al., 2024). To achieve sublinear regret in such settings, crucial for the algorithm to have precise knowledge of the total corruption or at least an accurate estimation of its upper bound.
For cases with known corruption, nearly optimal algorithms are proposed for various settings, in- cluding stochastic linear bandits in discrete action spaces (Bogunovic et al. 2020). Gaussian process bandits (Bogunovic al.) (022),, linear contextual bandits (He et al. 2022). Lipschitz bandits (Kang) ct al. 2024), and linear contextual dueling bandits (Di et al. (024).. These approaches typically rely on phase elimination techniques to eliminate suboptimal arms Upper Confidence Bound (UCB)-
based algorithms to pull optimal arms with high probability. The success these methods heavily depends constructing precise utility estimates to guide decision-makinn
However, for learning from nonlinear utility, constructing utility estimates under dueling feedback is very challenging problem, as only preferential (directional) information is available. This limited
14

---

Published as a conference paper at ICLR 2025
information motivates the exploration of approach: robust gradient- pradient-based algorithms. Zim- mert & Seldin (021) and Saha & Gaillard (2022) utilize robust stochastic mirror descent algorithms to update the probability distribution for sampling K arms. However, is difficult to efficiently gen- eralize this design to continuous action spaces, as it requires transforming the probability vector into probability density function and efficiently managing its updates and approximations. While Yue & Joachims (2009) and Kumagai (2017) exploits dueling bandit gradient descent and stochastic mir- ror descent and achieves sublinear regret for continuous dueling bandits, their performance under corruption remains unexplored. It is nontrivial question and still remains an interesting open prob- lem of developing robust and computationally efficient algorithms for continuous dueling bandits with generally concave utility functions under corruption induced by strong adversaries.
C PROOFS FOR THEOREM 3.
Theorem (Theorem restated). There exists p-Imperfect Human Feedback (see Definition 2.7 strongly concave utility function l4, and link function such that any learner has to suffer Regt 2 max (VT, W/,,T% TO)). even with the knowledge of
Proof. Before showing the regret lower bound proof for Theorem 3.1 let's first establish the follow- ing Lemma C.I]] which builds the connection between regret incurred under bandit reward feedback and dueling feedback. This proof is inspired by Theorem 6 in Yao et al. (2022). To prove Lemma metric measure the performance of algorithm under
C.T in addition Regr, introduce ducling feedback, which we coin functional regret Reg defined as follows.
T
RegT = EE
Σ
p(a)) - m(a:) + +(aa)) - (((at)
(3)
Lemma C.1. Given a utility function ps, if the regret lower bound for algorithm with bandit reward feedback Reg, then any learner with dueling feedback has suffer regret Reg 22Reg.
Proof. We prove our claim by contradiction. Let (ao, 01.z) be the pair recommendation at round Suppose Regh 2Reg. As result, least one of the following inequality must hold:
T
E
u(a") -((a,.))
S
Reg:
(4)
EE u(a") plan,)) Reg.
Consider principal who can observe the interaction between user and the learner L, then we can construct two algorithms Lo and L1 as follows.
Algorithm 2: Algorithm L,
Input: the time horizon T
for t S do
Call the learner L to generate candidates (av,e, 01,1).
Present (4o,t, (1.+) to user and received the feedback. Return user feedback to the learner and update L.
Output: the sequential decision {ar,))==
From equation 4 we know that at least one of (Co, }1 achieves expected regret lower than Reg. However, we know all algorithm with bandit feedback with utility function j has to occur regret at least Reg, contradiction. Therefore, Lemma C.1 must hold, which completes the proof.
Next, prove Theorem 3.1 First, consider the p 0.5. Given that the utility function is strongly concave, by applying Lemma C.2 have Reg 0.02 min (T, dvT). From Lemma C.1
15

---

Published as a conference paper at ICLR 2025
also obtain Regr 2 0.04 dvT). Using the linear link function o(x) 2/2 22, follows that Regr 2 0.02 mT, dvT} 2 (d max| max.xxTTT ("), completing the proof.
FO
Lemma C.2 (Theorem 6 in (Shamir 2013)). Let the number of rounds T be fixed. Then for any which is minimized at
learner, there exists a quadratic function of the form uo == 0' - 2/| - 8 and |00||2 < 0.5 such that
E
Σ
Ho uo(a") mo(ai) 2 0.02 min {I. [V.]
Now, let's focus the scenario when p 0.5. In essence, want to extend Lemma C.2 to the scenario in presence of adversarial corruption induced by p-Imperfect Human Feedback. we can show the regret lower bound can be generalized to S2(dT"), then applying the same technique which uses Lemma C.I to connect regret suffered under bandit reward feedback and regret suffered under dueling feedback and choose linear link function to connect Reg7 and Regz, we will get the desired regret lower bound. The extension of Lemma C.2 is proven section C.I
C.I PROOF FOR LEMMA
Lemma (Lemma 3.1 restated). Consider bandit learning with direct reward feedback, where reward r(a) == p(a) + e, e follows standard normal distribution. The action space A is contained d-dimensional unit ball, and μ is pe po(aa) 0 a E1[a|l with 0 E R, .1011|2 S 1. Under p- Imperfect Human Feedback (Definition 2. for any T, d S T and for any learner, there exists a such that under direct reward jeedback, with the knowledge of p. has to suffer regret Regr = == ( po(a))} 2 C,TT..
Proof. To prove Lemma 3.1 aim prove that there exists corruption strategy such that the regret incurred by any learner with imperfect dueling feedbuck is not less than ((dTP). The for- mulation of such corruption strategy hinges the observation that when the utility function μs
adopts the quadratic form parameterized by 0, specifically (a(aa) = 0 - [| 1 smooth and strongly concave, then the regret incurred by the learner is bounded below by the sum of the Dallback-Leible (KL) divergence between the distribution of the corrupted reward feedback obtained round t, denoted ig, E [T), conditioned on different possible values of 0. (see Lemma C.4). Assume that O is uniformly drawn from {-3, 3] given an action a,, conditioned on 0 > 0, the corrupted reward feedback 6; is
which both
:o(oa) + celarl0 > >0) +5= - la.1 + Boass
+ Bar, + ca > 0) +g. (5)
iti
Conditioned on 0; < 0, the corrupted reward feedback ég is
i = Ho(ae) + 0 < +5 1|re112 + Σ jøi
0,ars
Bar, + c(a/00) < 0) +G. (6)
We use Ca > 0) and (0 < 0) to empathize the fact that the magnitude and sign of corruption can be dependent on 0. & follows standard Gaussian distribution. Therefore, ét in Equation follows N(H1, 1). O, in 6 N(U2, 1). By using Lemma C.3 we have
DEL (N(H1, ()12, 1)) = (p1 =22
Lemma C.3 (KL Divergence for Normal Distribution). Let N (N, represent Gaussian distri- bution variable with mean μ and variance o². Then
Dxa (N o² o2 ) (11 - 212)
202
16

---

Published as a conference paper at ICLR 2025
To optimize the lower bound in Lemma to minimize the difference between μl and uig- Consider the following corruption strategy: when 0, > 0, set (a, 0) , when 0 < 0, set ca 0 < 0) Bo,.i. This strategy ensures that = J22-
C.4 the adversary selects c₂ (a, 0) and ca 0)
Next step is to determine the value of B. Notice that the corruption budget is C,TP. To execute the corruption strategy described above, it requires
T 1loloo S C.T.
Σ 1=1
ce((a))
S B
Therefore, by exploiting the fact that po is 1-strongly concave, we establish another lower bound for the regret by
E
ua(aa) mo(as)
E
|a, 013
IV
(11eello 332
T 29
IV
(C,T 10rr0-18--0 -3-
Since la,,; - 0,1 2 [0,ii - 31 for all i, we obtain the second inequality. By utilizing the corruption
constraint equation we derive the last inequality, which minimized when || C. for all Together with Lemma C.4 we have:
T rolca) max E B)2
dT
Σ pola") - -mola')-ooaa))
(8)
2
1T we can set B = We select 3 to optimize the lower bound in Equation equation 8 Since S C.
VC,I5- satisfy ||0|2 S Then we obtain IE {Ei Me (a((a) us (a( 2 dC,Tp/4. Notice
that the comuptiin level each round is bounded by [3]|a]]ooo- Consider the scenario when the radius of the action space A is upper bounded by 33, then the corruption budget each round is bounded by C.t-1+p, which satisfies the definition of p-Imperfect Human Feedback, which completes the proof.
Lemma C.4. Let's consider the utility function := aT Il1 Let ê1, :2...., bo be sequence of corrupted reward feedback obtained by a learner. Then there exists a E Rd, 1|01| S 1, uniformly drawn from {-3,33 such that the regret suffered by the learner is
:=
T Σ va(a")
-mo(())) uo(an) }
d2
d T
Dr.i
4
Di.; sup(o))ar DR. (P(6. 10 O, (0))its the KL divergence between two distributions.
< 0, (, (MHH)) DxL.
Proof. Using the similar argument in Shamir (2013). assume that the learner is deterministie: a, is deterministie function the realized corrupted reward feedback é1 ....... 6z-1 at 01, 02 4--1- This assumption is without loss of generality, since any random learners can be seen as random- ization over deterministic learning algorithms. Thus a lower bound which holds uniformly for any deterministic learner would also hold over randomization. To lower bound equation 9 we use Lemma C.5 which relates this to the question of how informative are the query values (as measured by Bullback-Leiblee divergence) for determining the sign of 0's coordinates. Intuitively, the more similar the query values are, the smaller is the KL divergence and the harder it is to distinguish the true sign of 0,, leading larger lower bound. In addition, we facing powerful adversary who
17

---

Published as a conference paper at ICLR 2025
has the complete knowledge of the problem and is able add corruption the query value make they are even more similar, which resulting a even smaller KL divergence, consequently, an even larger lower bound. Let är == + Σi=1 represent the average action, we have
T
T
E
(a(a") ) -molae)
= TE
Σ mo(a") - mo((as)
T
1=1
2 TE (10 vo(
2 7E
ÜT 0|(
TE
(a; 0.)²
2
2m
PT
E
000000
dT
1
d T
Di.
1=1
We get the second inequality by using the fact that μı is 1-strongly concave. We get the last inequal- ity by using Lemma C.5 which completes the proof.
Lemma C.5 (Lemma 4 in (Shamir 2013)). Let A be random vector, none of those coordinates supported on O. Let 01, U2.... ÖT a sequence of values obtained by a deterministic learner returning point (so that the action a is deterministic function of 01...., 02-1 and or is deterministic funcetioo of 01, (r)) Then we have
E
0:0:
D4a
where 1D, (up(o,) DEL (P( 00 > O, (0, (6r ( < O, (0ibi4h: (6)))
DKL. represents the KL divergence between two distributions.
C.2 PROOF FOR PROPOSITION
Proposition (Proposition restated,, There exists an LIHF instance with p-Imperfect Human Feed- back (Definition 2.7). linear user utility μ. and link function a, such that any learner has to suffer Regr 2 max VT, T")), even with the knowledge of p.
Proof. The proof structure very similar the lower bound proof in Theorem 3.1 We start by discussing the value of p. Consider the scenario when p 0.5. Applying Lemma C.6 and C.I together with linear link function, we have Regr 2 2(dmax( I")), which completes the proof.
Lemma C.6 Dani et al. 2008)). Let A= and θ -
41d. - Consider the linear is independent standard Gaussian noise. Then for any learner,
reward function v. A there exists vector such that
A. +
Reg (A,0) exp(-2) 2VT dVT.
Now, let's focus on the scenario when > 0.5 and the essence is to extend Lemma C.6 to the scenario in presence of p-Imperfect Human Feedhack, which is shown in Lemma C.7
18

---

Published as a conference paper at ICLR 2025
Lemma C.7. Assume that the action space A [-1,1]4. Given p-Imperfect Human Feedback (Definition p for stochastic linear bandit, there exists a E [-CxIP-1 _CxTP=11 such that any learner even with the knowledge of p has to suffer regret no less than $
8 CP
Proof. The proof extends Lemma C.6 to scenario in presence of corruption. We want construct a parameter family and a corruption strategy such that for all algorithm, it will occur at least ((dTP) regret. Consider the action set A [-1, 1]dd and e (-3, For any learner, we can lower bound its regret by
T
Reg (A,0) = Egg
(sign(0.) - ams),,
2
Eg
(siign(an)) o sign(0.))
1=1
T3
((sig((an) + sign(0:)) 2 T
Po
2
Let's denote
T
Po: = Po
Σ
(sign((an) + sign(0,)) 2 2
Let i E [d] and 0 E θ be fixed, and let 04 = Oj. for j + and 0 = -0;- Then using Lemma C.8
have
T DKL. (Pa Pao)
po, + Po; 2
2 exp
TE
Σ
Pa, is the distribution of corrupted reward observed by the learner after playing action de when reward parameter is Similarly, Pd, is the distribution corrupted observed by the learner after playing action a when the reward parameter is 8'.
Lemma C.8 (Bretagnolle-Hun Huber inequality). Let and Q be probability measures on the same measurable space (S,, Let A E F be any arbitrary event and A is the complement of A. Then we have
1
P(A) + Q(A9) 2 exp DF Q))
(10)
In presence of adversarial corruption, for 0, the corrupted reward is
ft
O1z0, + a.,0, + ce () Ec.
(11)
jfi
For 8', we have
ft Σ a a, cco(aal0') + jfi
(12)
Consider the corruption strategy such that e (ay aa, in equation 11 and (aal0'0)) = a, in equation 12 This is achievable since we assume the adversary has complete knowledge of the problem instance. By doing so, the corrupted reward i are from the same distribution regardless whether the preference parameter ordinate with the magnitude 3, and this difference could be masked by the corruption, resulting in T (P., P(,) = 0, which makes it indistinguishable by the learner. Notice that execut- ing such corruption strategy requires total corruption budget
or 0', This is because and 0' only differs in the i-th co-
(x(a:)) < B ||aellx S C.T..
(13)
Choose 3 = C-T--1 Equation equation 13 holds. Therefore, we have
1
po. + po; N 2
19

---

Published as a conference paper at ICLR 2025
Applying an "averaging hammer" over all f E θ which satisfies |0] = 2d,
get
po. 2 d
Po:
AEB
This implies that there exists a 8 E θ such that Σi=1 Po, 2 Therefore we have
(A, 2 dC,, T
8
which completes the proof. We want to highlight that the corruption level each round [ex(ar)] is bounded by Sl looo I C2TP-1 I C,ta- Vt, satisfying definition of p-Imperfect Human Feed- back.
D PROOF FOR THEOREM
Theorem (Theorem 4.1 restated). RoSMID satisfies Regr S O(dmax(VT,TT)) for any p-LIHF problem.
Proof. At the beginning the proof, we formally define self-concordance (see Definition D.I. The input, y-selffconcordaat function R, serves regularizor in RoSMID (see Algorithm [
Definition D.1. (Self-concordance.) A function R in)( + R is self-concordant if it satisfies
1. is three times continuously differentiable, convex, and approaches infinity along any sequence of points approaching the boundary of int(.A).
2. For every h pd and x E int(A),, [V²R(=) h h]] S 2 (h (Z)))))) & holds, where [8R(z) = 8²R
ōtgdtzdaa (x t + 12h tah) =g======
In addition to these two conditions, if for every h E g and a E in((A), [R(()) s už v {2) positive real number v, R is u-self-concordum.
Additionally, we remind the reader of the standard assumptions (Yue & Joachims 2009 Kumagai 2017 used in our analysis.
1. the action set A is a convex compact set that contains the origin, has non-empty interior, and is contained in d-dimensional ball of radius Rt
2. the utility function μ : A F. is strongly concave and twice-differentiable The following constants are useful for our algorithm analysis: is L'-Lipschitz, a-strongly concave, с- smooth, bounded R == supa,a' p(a) - p(aa), and == arg max p(a) is the unique optimal within A:
3. the link function R. J0, 1] is smooth, rotation-symmetrie (i.e. axz) 11 and concave for any x 2 For the case of analysis: let 17 [resp. L denote the lower [resp. upper] bound of the first-order derivative of a. is T." T."-Lipschitz and its second-order derivative o is I -isschitz and upper bounded by Rg
FO defined in Under these assumption. Lemma D.1 implies Regr defined in equation and Regr equation B has the same order.
Lemma D.1 (Lemma 12 in Kumagai 2017
With Reg Fo defined in equation we have
RegT L
Regr
< Reg <
(14)
19
20

---

Published as a conference paper at ICLR 2025
In the following, we show the proof. The main proof can be divided into four key steps. Step is natural, which quantifies the bias in gradient estimation by RoSMID due imperfect feedback from corrupted utilities. Building this, Step 2 develops regret decomposition lemma for dueling bandits under corruption, decomposing the regret into two components: regret from sub-optimal decisions and regret from feedback error. Techniques from previous analyses of continuous dueling bandits handle the sub-optimal decision regret, thus in Step 3, we focus on deriving new techniques bound the regret from feedback error, unique challenge in our setting. We identify a tight upper bound for this error. Finally, Step 4, the only step relying on the decaying corruption level in p- imperfect human feedback, uses this assumption, along with the carefully chosen learning rate "]p and an iterative regret refinement process, to ensure the tightness of the analysis in Step 3, thus completing the proof.
Step 1: quantifying bias of gradient estimation in P-LIHF
Our proof starts from quantifying the bias of the gradient 9: caused by p-imperfect human feedback, as shown in the following Lemma 4.1
Lemma (Lemma restated). The gradient gr. in Line 6 of Algorithm 7 satisfies
E (oelas) V laa=a Pa(a) E (b.la.).
where Pa(a) == ELEB [F(a x a (a)) m)] (with B as the unit ball) is the smoothed prob-
ability that a, is preferred over any action o, and by d (P((a > a4) P(an dt)) (
Proof. If we do not have corruption (i.e. the probability for observing noisy comparative feedback Fla, a') = is based on true cost difference p(a) p(a')), then the uncorrupted gradient gr. := Flal,
should be an unbiased estimate of PP((),
E(g:la;) (a.)).
We use (a,) as shorthand of V a=a. Pa(a). We use Pa(a) as shorthand of P:(a) : a(u(a,)~ u(a)) equivalent to P(a, > a). and (a) == (u(a,) μu(a + c,(a,, a.)).. equivalent to ((, > a) under our modelling assumption. The proof is similar to Lemma 2. in Flaxman et al. (2005) Using the Law of total expectation, we have
E(gila)) Eu, [B(gila, 4)]
Eu, (dE(Pi(at+ +
b u.)
dIE(P((a: + (2Ra(a:)
urlaa)
VELER (ellat + ("R =
(..(a.).
We get the second inequality by using the definition of F(d),a)) We use the Stroke's Theorem to get the second last equality. The gradient which we get to perform gradient descent 9; is corrupted. If we let a; = + (a),(ar)) 24, we have
E(Gr(o,) = E... (B(ârla): u.))
= E...
dE (a
dE ([P((a)) + Pa(af) Pi(ai)] V2 V2
VEZEB (Pi(ae + (a)) kas(as) + dI
(Pa(ot) - -P(())) V2Re(as) (
VP((a.) + dE (PPi(a)) Pi(a()) V (²R((ar) +
E(gelar) + dE
(P/((a) Pi(ol)) (iRe(ar)
21

---

Published as a conference paper at ICLR 2025
We get the second last equality by using the fact that St is unbiased, which proved earlier. If we defined by as
by = Pi(( + (2Ra(a)) Pi(a, + (2r) -zue) (a,)(a))2us
we get
B (z) = Eggh (a,) + E [b.
Step 2: decomposing regret for dueling bandits into regret of decision and feedback error
Core our proof "regret decomposion" lemma below that upper bounds the regret by two parts: regret of sub-optimal decision making under uncertainty, referred as regret of decision (first term in equation and feedback error (second term in equation 2)
Lemma (Lemma 4.2 restated). The Regr of Algorithm
satisfies:
Co log(T) &dn,T 21 21" L 2E
Regt S
Σ (a of)
Regret of Decision
Feedback Error
where Co = (2u + 4LgK + 4Rg (TM*) I///R)/ and oz = taa + (1 )aa"
Proof. The cornerstone of the analysis below is to separate the impact of by from the total regret.
L"LK
Regr-
S 2E
P((aT)
+ 22
AMP
<
T
(P((ar) - Pc(at))
T +E + -(P(())-PP(o)))
T
- -P((a)))
(P((())) -(((t)))P
LLL
+ 2
[=1
4LJK + 2 + log T + 21
< 2FE
Σ (P.(a.) - P.(att)
XMp
t=1
We get the first inequality by using Lemma D.2
We get the last inequality by because
P.(a) P.(a)= < I Rg )2
1 R2 (TM2²
-at)
Ampt
and
Σ (P)(ar) (P((at)) P((ot)) + Li + R2 (LM)2
(Pi(a))) -(((tt) E
E
log T.
XMp
Lemma D.2 (Lemma in Kumagai (017)).
T Σ
LPL
Regr < 2E
(Pa(at) - Pp(att
+
+ +
Amp
Then it remains to bound E TT 1-1 P((aa)) P((at)}. And we have the following.
VP, (a:)(ar - -at) Lia 1la. 11
E(P((a)) - P((a))) < E
E
91 (a: -ai))
T
I|a, -aiil3?
4
L
E
(ā. bt) (ar
b.)T(a
o
Ila+
17
4
Lia
E
9t (a+ ax)
| az11?
+ E(bl (a+ -a
4
22

---

Published as a conference paper at ICLR 2025
where the first and second equality is resulted from Lemma 4.1 we have
Using the definition of d++1 in
Algorithm |
VRy(a(+1) (R((ar) 779r.
Therefore we have
Lia aa, - -ap.13 91 (at a7)
(VR((ac+1> - vR((ar)) (a: az)) Li00
-E
4
1/p
4
Li 1la 071?
( ai) + DR(ac, ac+1) (a7, a4+1)
np
4
(x(a, b) is the Bregman divergence associated with R. defined by Dx (a, b) = R(a) - R(b) VR(b) (a- b).
Then we can get equation 15 by using Lemma D.3 D.4 D.5
v (T)
T
E
(P((as) Pr(at)
+ nn T + E
6, (at -
(15)
Up
7ml
Lemma D.3 (Lemma 10 in Kumagai Frenchel dual of Rr. Then we have
2017 Let RT(a)
supEER x TT Re(a) denote the
T
T R(a7) - -((ai) +E
DR: (VRi(a:) - nnae, VR.(ai)) )
Lga | 1/
Σ
E 9r (a: 07)
Σ
Tpp
Lemma D.4 (Lemma 11 in Kumagai (017 When 11p S 28' we have
DR; (R))
Noği. VR, S 4.2-112
Lemma D.5 (Lemma 4 in Hazan & Levy 20144). R(a7)) R(a1) S v log(T))
If we let Co == (2v 4LgK k + 412 (L
L LMLgK)/A A, we have
2v log(T))
4L AR2 (2 + L"LiK log T + 2L
Regy
8d 8d 2E
by (at at)
dpp
XMp
Co log(T) + od n T 2
Σ b. (at af))
7p
Regret Decision
Feedback Exvor
which completes the proof.
Step upper bounding the regret from feedback error
Bounding the regret of decision term in equation 2 is standard. Thus, this step develops novel upper bound for bounding the regret from feedback error, as shown below.
Lemma (Lemma
4.3 restated). The feedback error term in equation 2
caa be bounded as follows:
T
E
b (a+
at)
Vtlca(ar, dDIVH((") u(aa)
+ C2dTT + 2dv X VnTT
where C :
2X(LoJ
and C2 == 2L R SupARAA Amax (V²R(a))+2g +2)
Proof. In the following, we will analyze the expected cumulative sum of the bias b, on the to- tal regret, which is E E 6J (at - at)}. By Cauchy-Schwartz inequality, 6J (a, at) s ||b, (22 - 12) We can bound the ||b|l12 by the following.
b.bb d (Pi(a) (2R - P.(aa + (2Ri(ar) 2 u. TVRR((a;)u
(Pi(a)+ + V²R((a,) -m) -P((as (a) d dmmmax (2² (2)(()))))
23

---

Published as a conference paper at ICLR 2025
We get the first equality by Lemma 4.1 We get the inequality by using the fact |/ul|22 1. If we let dg at + (a)) kuc, then we have
(P(a)) - Pr(af)) = (o([(a))) - s(a()) - -(((a)) ce(ar,a)))
S <in (2, (2, d,)l).
We get the first equality by using the definition of ((a) and Pi(as). We get the first inequality by using the Lipschitz property of a. Therefore, we have
|bba - Ammaxx ( min {2, (2, df)3
we use Xp = supae AEA Amax (v²R(a)), then we have
Amax (V2 = Amax V (22(()))) + Amp + 20 S Xn 26 + Anpt.
Therefore we have
T
T lbellalla, 0ñl12
6 (a: az.))
SE
T
E
(dv Amax (2RR((a)) min L2
L (el(ar, a() - -0rll
E
(dvAR + 22 |/ a7
E
(dv2% X/ 20min min (2, L (c a')l) ||a: - azl12
(dy Ampt min (2, L [e, a()l) ||
at
< 2RdL" Xx + 26T + dv An
V min (2, La (c((,,))))) || - -
(16)
T
2RdL' X 26T + 2d A + dv Anp
Vt min (2, Lale 43)) llay a"lle
(17)
2RdT Xxn + 20T + 2d + M
Mimi (2, 1. (er(ae, (f)) min 2R,
/ 2
2 (n(a*)
(a(a")-a((as)) m((x))
(18)
We get equation 16 by using the fact that 1|a;-ail)y S 2R, Σt (e((a,, af) S TP. We get equation 17 the definition of az, and the fact Va+ Va + Vb. Using the a-strong convexity of we have ||a, - l2ll2 I min 2R, V (p(a*) m(ax)) we get the last inequality, which completes the proof.
Step 4: The iterative regret refinement analysis and resultant optimal learning rate
Lemma (Lemma 4.4 restated). If A = E (laaa((a)) =<(ai)) s O(T)+*) for some eb e Σ 1= 10- Vulat) - m(ve) s O
[0, 1), then must have B =
Proof. To prove Lemma 4.4 it is equivalent to prove the following Lemma D.6 If Lemma D.6 holds, let VE(u(a*) plaa)), m4 = min (2, (c, df)l), proves Lemma4.4
Lemma D.6. Consider Σtn nł C' with constants > C² 0. In addition, is uniformly upper bounded by constant K. Specifically, we have 0 < K, Vt. m. S cgl with constant Cs 0. Then have Σ Vimin I 5 +
24

---

Published as a conference paper at ICLR 2025
Proof. Using Abel's equality (Lemma D.7p. we have
Σ
Vimin S VT
Σ ment
Since we have Σ n & t and 0 S T4 S K, VI, we have Σi=1 s V vL.
Moreover, for t 2 1, 1,t - (t + 1)-1+ I t0-2 holds for all 2 1. This is because
S(1) - (1 (1+ 1 -
is decreasing over 2 1 and 1im [(1 = 0. Consequently, applying Abel's Summation Equation again, we have
T
T
T-1
Σ
mi7
Σ
141
MI
+
Thi
(ms - -m{+1)
T-1
S
V + VC'ck
-=1te((++1)-11)
t=1
1=1
< &V + VC
1-2
S VC + VC'ck
/ + 22+p
< 1
Since < n4 I K, Eis nie is increasing and the increasing rate is upper bound by L. Together with the constraint Σ The I VCTi+,, Ein (Ei n4 L + is optimized when Σ
increasing in the speed of + Because of this, the second last inequality holds.
Lemma D.7. (Abel's Summation Equation
(Williams)
1963)). For any numbers ak. bj. we have
anbb
Σbe A
bk
On
+
Σ 1=1
bi
(ax - (x-+1)-
A=
After establishing Lemma 4.4 we can use it to prove the induction claim (Lemma 4.5) The chal- lenge in this proof lies identifying the constant K, which must hold across all iterations of the analysis to ensure the bound remains stable and does not diverge. This requires careful refinement of the analysis and calculations.
Lemma (Lemma
V 4.5 restated). Consider T > V2L=LąR and Top TTTan (1/2.p) $- RegT S 144dK Vlog T
25 for some integer k, then we must also have K is instance-dependen constant, where K C.C,, (LTTT), LVARC, Co and C2 defined in Lemma 4.2 and respectively.
4-c
Regr S 144dK Mog o
2411
max {Co, VlogT
Proof. In the following, we denote
2
m. = min (2, (c, d()l) (m)) n = min 2R,
(u(a*) - p(ar))
25

---

Published as a conference paper at ICLR 2025
Continue from equation 18
have the following.
The Base Case: When k = 1, let C3 C2dT 2d An,T, we have
Co
Regr _ log(T) + &d log(T)++ 21 2 2C3 + 2d XT
Vtmmme
(19)
1
Co log(T) + 80 21 R 2C's + 4dR An
$
Vime
(20)
Cu log(T) 8d n 21 21 R + 2C3 4dR Mnp
m
(21)
n Cu log(T) + 8d n, l 21 L 2C3 + 4dL RV C.
M
(22)
We get equation
19 according to Lemma 4.2 and 4.3 We get equation 20 because of E (n;) < 2R.
We get equation [1 by Abel's Summation Equation (see Lemma D.7). We get equation 22
because of corruption budget. Choosing the learning rate Tip according to Theorem 4.1 we obtain Regr S T This confirms the validity of the claim when ==
The Induction Argument: Let's assume that the claim holds true for general step k. In the following, we will demonstrate that the claim also holds true for step + 1. Because Equation
equation 14 and induction claim, we obtain Regr KD
S T
144 dk /og TT 8/2
This suggests
that
144 Σ E (u(e") u(ar)) s dK /log TTM+ 92-0
25
1=1
By Jensen's inequality, we have
2 E (Vu(ar) - -m(a)) } $ S / VVB((((a*) m(at)).
E(n,) = min
Therefore we have
2 Therefore, using Lemma 4.4 we can upper bound VAET E Vimin by
T Vimeny
$ vV Σ ((((a))(((a)))) p(ar)).
By the definition of p-Imperfect Human Feedback, we have lex(ar, af) is upper bounded by Cgl-1+p.
Vtmane S 60L
2x all
(log T 0.25 C, d 3/2-
Since s alq 12, choosing 7,
Mlg T
we have
C2 60C K
222 VlogTT 1 T
Regr < 2d
Co
Vlog T
144dK Vlog T
3/2 2F.T
The claim holds true for step k+ 1. Therefore, implies that the claim holds for all k. Repeating this process infinitely many times, we obtain
Reg, 2 -0(d (TTT)
which completes the proof when p E [0.5.
26

---

Published as a conference paper at ICLR 2025
E PROOF FOR PROPOSITION 2
Proposition (Proposition restated). If the total corruption level satisfies Ets (c)(a,,(H) S ) then for any a E 1), if the utility function is strongly concave, for sufficiently large round' T, by choosing learning rate Tpp == y/wg T
2d
1. (Robustness) RoSMID incurs Regr OldTa VdTill-a)+o dT²).
2. (Efficiency) There exists strongly concave utility function μ and a link function such that Reg, suffered by RoSMID is at least Qt (T*) in scenario without corruption.
E.1 PROOF FOR ROBUSTNESS STATEMENT IN PROPOSITION 2
Proof. From Lemma
we know
T
T
be (a+ az)
2RdL VRR + 20T d
Vt mini (2, Iolela
4() I1+ ajl12
+ 26T + +2Rd X L < 2RdL +
Vtla af)
1=1
$ 2RdL" A 28T 2Rd A
We get the second inequality by using the fact that the diameter of the action space of R. We get the last inequality by using Abel Summation Equation (see Lemmal D.7.. Therefore, by Lemma we have
Cu
Regr
log(T) sd + ARdL A 20T + +4Rdy M ?p
Choosing 17p
log' T T .aE [0.5, we have
Reg, S 2dC L log T + 4d T 4RdL" /Xn + 20T + 4RV (RV (log 0. 21/ L
00 < (d/log TT + : + dT
which completes the proof of robustness statement.
E.2 PROOF FOR EFFICIENCY STATEMENT IN PROPOSITION 2
2 implies that RoSMID could afford agnostic cor- ruption level #rr If Lemma E.1 holds, this implies that there exists hard instance which makes RoSMID incur regret in order of ((T)))))))))))))))))) in non-corrupt setting. We can prove this by contra- diction. Assume the efficiency statement in Proposition 2 is not true, which implies that for all μ, and σ, there exists an e 0 such that Regr T for some constant Go > we assume to be the least possible. In this scenario, when we consider a linear link function o (z) 1+z Lemma E. implies that agnostic corruption budget 2/oo7 Lig suffices to induce linear regret, which contradicts the robustness statement in Proposition 2
Proof. The robustness statement in Proposition
Lemma E.1.
For any algorithm G incurs regret Regr S coT", for some constant Co
learning from bandit with reward feedbbakk for strongly concave utilities μ in non-corrupted setting, then there exists an instance μ such that G will suffer linear regret under agnostic corruption with budget VcTT'
Proof. Consider the scenario when d - 2. the action space A := {(a), (2) aj 0,a2 0, 01 + 42 < 1), the utility function (a) = (8, a) ||a]]] with := [1. 0j. In this scenario, the optimal action is a*
[1.0). Assume that the adversary want to "fool" the algorithm to
make it believe the 0 := [1, 1]. with optimal arm a" = 1 }.1 each round, the corruption it should introduce is ca(a:) -a2, where de is the i-th coordinate value of action at. To make reward
27

---

Published as a conference paper at ICLR 2025
indistinguishable from these two environments, the total corruption budget which the adversary has
pay is Σ ar2) We know that & incurs regret Regy- = Σi= (0, a -a,) / ||a 11 + l
- + 2 + aa I c,T". Given this constraint, the maximum possible corruption paid by the adversary to make 0- = [1, 1] and 0 [1, 0J indistinguishable is max Σ |4zl = /ool =
a=1
Therefore, for any agnostic corruption no less than V 9 can not distinguish 0 = [1. and 0 [1, 1] and has incur linear regret in either of these environments.
F PROOF FOR PROPOSITION 3
In this section, we present the regret upper for dueling bandit gradient descent Yue & Joachims 2009) in presence of arbitrary and agnostic corruption. Before presenting the proof, we make several remarks. First, in Yue & Joachims (2009), the utility function 1 is assumed to be strictly concave to ensure the uniqueness of the maximizer. However, in scenarios where the maximizer is unique within the action set for a concave utility function Ju, the requirement for "strictness" can be relaxed. Second, we highlight the notation differences. We use a to denote actions while Yue & Joachims 2009) uses w. In our proof, we define P.(a) == (p((r) ) (u(a)) to represent the probability of the event d, > a. While in Yue & Joachims (2009), it denoted (ww). Just to highlight, its corrupted version P((a) == a (p(at) (a(a) ot (a(aaa)) is newly introduced in our paper. Moreover, (a) = ErEB (P + 8z))] is denoted as (xw) + 2 in Yue & Joachims (Pw(we
20099. The definition of F (PA (a, + +uu)) at) is same as X2 (Pw (we + dd,)) defined in Yue &
Joachims 2009), except different notation. We remark Pa(a) represent the projection of action
on A.
Algorithm 3: Dueling Bandit Gradient Descent (DBGD) Yuu & Joachims, 2009)
Input: Exploration rate 6, exploitation rate y, initial action 01 0 A.
for t E (T] do
Sample unit vector un uniformly and set d' = PA (a, + Ouz).
Present action pair (4t,a) to user and receive corrupted dueling feedback Flals oz).
Compute gradient Ô: - ((c,, at)ur.
Set learning rate 17 d
2á and update a++1 = Pa(a: - :(ge).
Proposition (Proposition restated). If the total corruption level satisfies Σtn (ce(ar,a)) S (TT)), then for any a E (0, 1)) if utility function is generally concave, for a sufficiently large round T, choosing 7 JT
R and 6 VI3L" L for Algorithm
2/RR
1. (Robustness) Reg, incurred by Algorithm satisfies Regr I O(VaTi-a + VdT
2. (Ffficiency) There exists linear utility function y and a link function such that Regt suffered by Algorithm 3 is least Q (T!-a) in scenario without corruption.
F.1 PROOF FOR ROBUSTNESS STATEMENT IN PROPOSITION
3
Proof. The proof of Theorem 3 builds on the proof of Yue & Joachims 2009). where we extend it to setting in presence of agnostic corruption. The proof follows Step 1-3 introduced in Theorem 4.1 Similarly, in Step 1, we decompose bias in the gradient caused by corruption. Notice that without corruption, DBGD performs expected gradient ascent, where the gradient ge is defined follows
gt (PA (a; + duz) aa)) uz-
In the presence of adversarial corruption, the corrupted gradient is
g. 8 (PA (a: + 8u4) ,a,) u+-
Therefore, quantify the bias E(bb in the following lemma.
28

---

Published as a conference paper at ICLR 2025
Lemma F.1. Let Pa(a) represent the likelihood of action a, being preferred over over a, where Pi(a) (p(()) - p(a)). Likewise, the corrupted version is defined Pa(a) d(((a)) - -u(a) + cc((at a)). The smoothed version of Pt over A is P:(a) := BBEB (P 6x))), Let oj = PAlee + duu), where u, is uniformly sampled from and St = - (a,, a4) ui Let b, = / (P((a)) P:(a)) u.
We have (g)) = (((V))(a)))a))) - (bbb(
Proof. (Proof for Lemma F.1 Since di = Pa Pulat + g(ee, we have
E a,) = E,,, (B(g, az, uz))
d Ru, (R(F (E(F(al, ai)e ue)
6
d (P((a))uular)
- ([P((a)) + - velae)
" [Pi(a))- - P.((()) u uilas)
VELEB (Pa(Pa(a: 5x))]aa))
(23)
8
P(((a.)) 1 [((((a)) Po(aa))
u uolas
B(grla)) B (Pr(cc)) -P((()) ue (as
(24)
We get the equation equation 23 by using Lemma F.2 F3
We get equation equation 24 by using Lemma
Lemma F22 (Lemma 2 in Yue & Joachims 2009
Fix 8 O, over random unit vector u, we have
(PP.(PA(a + su] 5 P.())).
Lemma F.3 (Lemma in Yue & Joachims 2009 ). (F,a EE,(P((d)u))
In Step 2, we decompose regret under dueling bandits into two parts, regret of decision and feedback егror.
Lemma F.4 (Regret Decomposition for DBGD). Define X
1. La is the Lipschitz con- LO-
stant for a', R/ TT, for by defined in Lemma F. have
2RdvT
T
Regr AA A
138L"L'T
+ 2X
E (b, (at a²))
8
tm1
Regret of Decision
Feedback Ervor
Proof. Because of Lemma
F.5
we have
E
P.(a:) - -p(aa) < SD
1=1
E(B(grl:)) a²)) (3++
E(B(G. + belax) (on)((uu) (a: -a)) (3 X)8L LTT
T
E(gE (at - a. a²)) -
E(b (a, a²)) + (3 X/8L LT
1=1
29

---

Published as a conference paper at ICLR 2025
Lemma F,5 (Lemma 4 in Yue & Joachims
2009)).
Fix 8 (0, ). for X defined in Lemma F.4
have
T
T P((a)) - Pi(a") -
E
E (AVP)((a) (at- -a"a--")=- (3+ 1)61
Since ac-1 Pa(a: 19:). and 17 d by applying the telescoping sum and because 01 0, llgel12 I G, Vt, we have
2ó
R2
Tn/G²
B (e (at a²)) S
27
2
Noticing that ||bal|2 min (2, I. (cx d.))). Moreover, ||a, -a'll2 s 2R. Therefore, in Step 3, we can control the feedback error by the following.
Lemma F6.
Σ E (b, (a. a²)) 2RdL
Proof. (Proof for Lemma F.6)
Σ B Blbelat- - a²)) s 2R Σ
min (2, I (e(a,, d())
- 2R dL
T
ce((,, df)
1=1
2R TL
Lemma E. (Lemma 3 in Yue & Joachims GSL"LeT
2009
Regr < 2E ET= Po(as)- P.(aa) +
Set 5. and by Lemma F.7
we have
2RdVT
Td
Regr S A
+ L
+ +4R 8
Therefore, by choosing 8 = VI3L LFT 1=
V/Rdd
R VT
and T
V2RdL Jag
we have
VI3L L
RegT < 2 26RdL LeT -a + 2L /26RdLo LeT000,
AT LVVILL LP completes the proof.
1" LET
F.2 PROOF FOR EFFICIENCY STATEMENT IN PROPOSITION
Proof. The robustness statement in Proposition S implies that DBGD could afford agnostic cor- ruption level O(Tl-a). This implies that there exists hard instance which makes DBGD attain regret in order of 2(T in non-corrupt setting, formally described as follows. To start a proof by contradiction, we assume that the efficiency statement Proposition 3 is false. Specifically, for all problem instance μ1, a. there exist a e > 0, such that Regr < OTT --). We assume to be the least possible. In particular, there exists pair of instance μ,, such that Reg, -- cu is a positive constant. In other words, it says that there exists a pair of instance μl, a such that DBGD suffers regret in @TTl-a-t).
30

---

Published as a conference paper at ICLR 2025
Consider the following problem instance. ju(a) = specifically f is linear function. Let d with action set A1 := {(11. a2) : a1 - 0, 2 0. 2 + d2 - 0} with 0 = 1/2 2 The optimal arm is d₁ = - 0J. which is unique. Let the link function (zz) = 2 12. It is easy to verify that it rotational symmetric and Lipschitz. Denote Regr as the regret occurred by DBGD on this problem instance. We know Regr I O(TI-a-). Consequently, it implies that 02 is at most proposed Sc, times. This is because Regr I cgTi-a-e and if the proposed action pair (at, a() including 02 at round t, it occurs regret at least g.
Now consider a different problem instance with the same (4, a but different action set, which is A : {(a), : a1 2 0, 02 2 0, faj + 02 1/2 S 0}. The optimal arm in this action set 42 = [0, f). which is also unique. Proposing arm d = [ 0] occurs at least regret. Consider an adversary that pulls the utility of a2 from v down to } whenever it is pulled at a cost of (f = 1. It is equivalent say that every time when the proposed arm w: falls in the region W = {ai 2 0, 02 2 1
0, 2 01 + 02 - 1
S 0}, we assume that the utility is sampled from 0 PA, (w) I I. Choosing the total corruption budget as 2c, 2 the adversary can afford to corrupt Sc,
1 - 0, 3,ya1 + 02
and [c((w] = 10 PA. (w) 0 w
times.
This means that as long as the adversary is corrupting, the utility observed in the first problem instance is exactly the same as the utility observed in the second problem instance, in which we pull 02 as most 80, 71-a-- However, d2 is the optimal arm in the second problem instance, which implies that the regret occurred on the second problem instance is at least 7 8 wwich is linear in T. This contradicts the robustness statement in Proposition[] which says that when agnostic corruption is 2cp7'² - the regret upper bound is O(T"= which is sublinear. To reconcile the conflicts, we must have the efficiency statement in Proposition 3 true to make the agnostic corruption budget at least Q(T to make the parallel world argument valid.
G ADDITIONAL EXPERIMENTS
In this section, we list all the experiment details. At the beginning, we introduce the regret order fitting method, and baseline algorithms for comparison.
Fitted Order of Regret. We introduce the methodology that we use to compute the order of Regr in terms of the number of iteration, T. To fit the order of the regret, we first convert it into log scale. Then we input the last 1% of data, run linear regression, and use ordinary least squares estimate the slope of the line, which is the fitted order of Regr.
Baseline Algorithms. We consider three baseline algorithms for comparison, Doubler (Ailon al., 2014) and Sparring (Ailon et al. 2014)
Doubler is the first approach that transforms a dueling bandit problem into a standard multi-armed bandit (MAB) problem. It operates in epochs of exponentially increasing length: in each epoch, the left arm is sampled from a fixed distribution, and the right arm is selected using a MAB algorithm to minimize regret against the left arm. The feedback received by the MAB algorithm is the number of wins the right arm achieves compared to the left arm. Under linear link assumption, Doubler has been proven to experience regret as the same order as underlying MAB algorithm. For continuous action space and general concave utility, we choose Bandit Gradient Descent (BGD, (Flaxman ct al. 2004 ) with regret (TT3/4), as the underlying MAB algorithm.
Sparring initializes two MAB instances and lets them compete against each other. It is a heuristic improvement over Doubler. Although it does not come with regret upper bound guarantee, it is reported to enjoy better performance compared to Doubler (Ailon et al. 2014). We also choose BGD as the underlying MAB algorithm.
To validate rfficiency-robusteesss trade-off in Proposition 2 and Proposition we try different a values. In the first row of Figure 3 we consider a = 0.05 for DBGD and a 0.9 for RoSMID. We consider م E |0.5, 0.95). According to the theoretical prediction, both DBGD and RoSMID can tolerate at most ( agnostic corruption, which aligns with experiment results. This is because the estimated order of regret is less than 1. In the second row of Figure Bl we consider a = 0.1 for DBGD and a = 0.8 for RoSMID. According to the theoretical prediction, both DBGD and RoSMID can tolerate at most O(70.9) agnostic corruption. From the figure, see they
31

---

Published as a conference paper at ICLR 2025
have smaller fitted order of regret when p 0.5 while cost of tolerating smaller magnitude of agnostic corruption (it has linear regret when = 0.95). which reveals intrinsic tradeoff between efficiency and robustness.
DBGD
RoSMID
Sparring
Doubler
e:0.09
o:0.89
0:0.34
o:0.99 p:0.5
10
p:0.8
0:0.88
0:0.99
0:1.17
0:1.01 pr0.95
103
10
16a 10*
10a 10
16a 10*
10
DBGD
RoSMID
Sparring
Doubler
pr0.5
107
0:0.43
0:0.75
0:0.38
o:0.95 p:0.8
0:1.04
0:1.0
0:1.17
10a
10a
Figure 3: In the first row, we consider 0.05 for DBGD and a 0.9 for RoSMID. In the second row, we consider a = 0.1 for DBGD and a 0.8 for RoSMID. Given the a, for each algorithm, tested its performance under p-Imperfect Human feedback with 0.5, 0.8, 0.95. For each p, we presented a line plot of the average regret over five simulations, accompanied by + one standard deviation shown by the shaded region. In the legend, denotes the estimated line slope, calculated using least squares on the last 1% of the data.
G.1 COMPUTATIONAL COMPLEXITY
Firstly, we emphasize that our robustified algorithm retains the same computational complexity as the originals. This indicates that incorporating robustness does not compromise computational efficiency, ensuring the practicality and scalability of the enhanced algorithm for real-world appli- cations. Specifically, RoSMID has a rumning time of O(d"T", where the d term arises from the singular value decomposition. Similarly, the robustified DBGD algorithm runs (dT), assuming that (a + 5u,) can be efficiently computed through matrix transformations.
As our work the first to address corruption- robusst learning from a continuous- action strictly con- cave utility, there is no directly comparable literature for this exact setting. However, provide relevant comparisons for reference. RCDB (Di et al. 2024), designed for corruption-robust learning in linear contextual dueling bandit framework, has running time of O O(K2TT)), where K is the number of actions. Similarly. Versatile- DB (Saha & Gaillard (022), which addresses ducling bandit problems multi-armed bandit setting under adversarial attacks, has running time of O(K?T', where K represents the number of arms. K²2 comes from solving arg max y) f(x)) using second order Newton methods and f convex function.
32


Reviews:
[{"review_id": "QchuBjlaGf", "reviewer": "Reviewer_NYfx", "summary": "This paper studied the dueling bandit problem with constraint corruption. It first proved that the problem is not easier with the constraint on the corruption with a lower bound. Next, it showed the efficiency of the proposed RoSMID algorithm with theoretical upper bound and numerical experiments. It also discussed the application of its analytical techniques.\n\n==========\n\nAfter rebuttal: I would like to keep the score.", "questions": "Please refer to the 'Weaknesses' section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is generally easy to follow.\n1. The proposed RoSMID algorithm is nearly optimal when the gap between its upper bound and the lower bound is only $\\log T$.", "weaknesses": "1. The paper repeatedly emphasize the novelty of the analysis. It would be appreciated to summarize the novelty in a few words.\n1. Lemma 3.1: I am confused why the author(s) discussed the direct reward feedback setting here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ypMgBxdpYZ", "reviewer": "Reviewer_kiH5", "summary": "This paper studies the problem of dueling bandits with continuous actions when the outcomes are corrupted. In particular, the authors assume that the comparison at time is perturbed by an amount $c_t(a_t, a_t')$ which is $t^{\\rho - 1}$. First, the authors demonstrate a lower bound of $\\Omega(\\max( \\sqrt{T}, T^\\rho ) )$ on the regret even when $\\rho$ is known. The authors complement this result by proving a matching upper bound by robustifying stochastic mirror descent algorithms proposed in prior work on dueling bandits literature. Furthermore, they also study the setting where the total amount of corruption is bounded i.e. $\\sum_t c_t(a_t, a_t') \\le T^\\rho$ and need not follow the decaying pattern. For this setting, robust versions of stochastic mirror descent and bandit gradient descent are studied.", "questions": "1. Can you generalize your results to consider the case when the link function might have an unbounded derivative or non-smooth? This covers a large class of link functions. \n\n2. What is the regret upper bound when the utility function is just concave (and not strongly concave)?\n\n3. Finally, can you explain the weaker regret upper bounds for the setting of bounded corruption (subsection 4.1)? In particular, does there exist some algorithm that provides a matching bound (as stated in theorem 3.1), or is the lower bound even stronger in this case?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The proposed algorithm (robust version of stochastic mirror descent) is simple and elegantly generalizes prior algorithm proposed in the literature on dueling bandits.\n\n2. The paper is well-written and the authors have clearly explained the main difficulties in proving the regret upper bound. Moreover, it is also interesting to see that the regret lower and upper bounds match (up to logarithmic factors).", "weaknesses": "1. The model of corruption assumes that the amount of corruption decays over time. Therefore, when $t$ is large, the corruption encountered by the algorithm is quite small. I believe this is a strong assumption and severely restricts the adversary. Although the authors have results when the total amount of corruption is bounded (proposition 2 and 3) the bounds are suboptimal in such a setting.\n\n2. Although the authors have motivated the use of decaying corruption, I believe human labelers often display persistence bias and therefore it is not clear that the corruption will decay to zero over time. Perhaps another setting could be that the feedbacks display some non-negligible bias over time.\n\n3. The authors proposed several assumptions on the link function. For example, the derivatives are bounded (both below and above). This is not satisfied for many link functions e.g. logistic functions. Furthermore, the setting assumes that the utility function is strongly concave which is also a strong assumption.\n\n4. The result is subsection 4.1 is presented as efficiency-robustness tradeoff in learning from imperfect feedback. However, the results are specific to two learning algorithms and it is not clear whether such a trade-off exists for any learning algorithm. In particular, can the authors provide an algorithm independent lower bound for this setting?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rPcUIqQBnY", "reviewer": "Reviewer_aLPp", "summary": "This paper studies This paper studies Learning from Imperfect Human Feedback, where human's imperfection decays over time. The authors begin by establishing a theoretical lower bound, suggesting that learning from imperfect human feedback can be as challenging as learning under arbitrary adversarial corruption. They then propose a new algorithm RoSMID, designed for continuous action spaces, which achieves a near-optimal regret bound under decaying corruption.", "questions": "- Could RoSMID use an upper bound on $\\rho$ if the exact decay rate is unknown? How would this affect the performance of RoSMID?\n- 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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Learning from imperfect human feedback with decaying imperfection is interesting and well-motivated. This provides a valuable extension to traditional dueling bandit frameworks by allowing for dynamic, time-decaying corruption in feedback, aligning well with real-world applications.\n- The authors establish a rigorous lower bound for regret under imperfect feedback, showing that even when corruption decays, learning remains as challenging as in adversarially corrupted settings. This theoretical insight highlights the inherent challenges in dealing with imperfect human feedback.\n- RoSMID is a novel algorithm that achieves a near-optimal regret bound in the presence of decaying corruption. The algorithm's reliance on gradient-based techniques in the dueling bandit setting is an innovative approach that bridges traditional bandit learning with more advanced optimization methods.\n- Extensive experiments validate the theoretical bounds. These experiments also underscore the efficiency-robustness trade-off, an important consideration for the settings where feedback corruption is inevitable.", "weaknesses": "- RoSMID requires prior knowledge of the decay rate $\\rho$ of the human feedback, which may be an unrealistic assumption in practical settings. A discussion of this limitation and insights into possible relaxations would be beneficial.\n- Though the theoretical result is new, it is not entirely surprising given the similarities between decaying corruption and adversarial corruption. A more detailed discussion on the difference between decaying corruption and adversarial corruption and how it informs the design of RoSMID would enhance the paper's contribution.\n- While RoSMID's theoretical performance is strong, the empirical evaluation could be more comprehensive. For example, it would be useful for the authors to include insights into RoSMID's computational efficiency relative to other methods and its scalability with increasing problem size.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1qL9kwJLbt", "reviewer": "Reviewer_pdpN", "summary": "This paper studies a new problem of LIHF under the dueling bandit setting with a continuous action space. This paper proposed a regret lower bound for this problem and then introduced a new algorithm based on gradient-based mirror descent that attains this lower bound. Experimental results are further conducted to validate the high efficiency of the proposed algorithm.", "questions": "1. Why do you think the assumptions made in line 143-152 are reasonable? I feel they are very specific.\n\n2. Can you report the running time of your proposed algorithm compared with baselines? Since you study a practical problem and hence the algorithmic efficiency is also an important factor.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I didn't check all the proof in Appendix due to limited bandwidth, but after taking a close look at the theoretical results and the proof outlines, I feel the technical results are sound and reasonable.\n2. The paper is clearly written and easy to understand.\n3. This paper studies a timely topic of robust bandits to adversarial corruptions.\n4. Experimental results are presented after theoretical analysis.", "weaknesses": "1. I feel there should be more literature review to help readers better understand your problem setting. I am not familiar with robust bandits, so after reading some existing literature, I suggest the authors to add the following discussion:\n\n1.1 It's better to highlight the starting point of this line of work (Lykouris et al. Stochastic bandits robust to adversarial corruptions; Gupta et al. Better Algorithms for Stochastic Bandits with Adversarial Corruptions, etc.) and their formulation of this problem.\n\n1.2 Since this paper consider the continuous action space/Lipschitz concave utility function under adversarial corruptions, it is better to mention some similar existing work on continuous action space such as robust kernelized bandit (Bogunovic et al. A robust phased elimination algorithm for corruption-tolerant Gaussian process bandits, etc.) and robust Lipschitz bandit (Kang et al. Robust Lipschitz bandit to adversarial corruptions, etc.), and discuss the connections with these existing works. It seems that this line of work still uses the classic bandit theory framework which is different from your gradient-based one, but I feel this point should be highlighted in your main paper.\n\n1.3 More existing literature on gradient-based mirror descent should also be presented. It is important to let readers know how you modify the gradient-based idea to deal with the adversarial corruptions.\n\n1.4 For the assumptions made in line 143-152, it is better to highlight where these assumptions come from one by one.\n\n2. Since you studied a very new problem of decaying corruptions and argue that this is a practical problem, I feel it is better to add some real-world experimental results in your study. Simulations can hardly validate the high efficiency of your problem setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XySlRhPOrt", "reviewer": "Reviewer_5vny", "summary": "This paper studies the problem of corrupted dueling bandits with strictly concave reward functions. It also considers a specific assumption (motivated by empirical observations on human behaviors), that the corruption budget at each time step decreases as $t^{\\rho-1}$ for $\\rho\\in(0,1)$.\n\nFor that problem, the authors propose a lower bound in $\\Omega(\\max(\\sqrt{T},T^{\\rho}))$ and a stochastic mirror descent algorithm matching this bound, up to logarithmic terms.", "questions": "- Can you relax the assumptions on the link function $\\sigma$, so that it includes natural functions?\n- Your algorithm requires a prior knowledge of the corruption budget $\\rho$. Do you have any idea if we could design an algorithm with reasonable regret guarantees in the scenario where $\\rho$ is unknown?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "It is the first work treating the problem of bandits with (strictly) concave utility functions and continuous actions spaces and it manages to do so with a quite complete picture and nice results :\n- a lower bound, similar to linear bandits with corruption is proven: its proof nicely adapts to the fact that the corruption budget is individually bounded at each time step, rather than only having a bounded sum\n- an algorithm with a nearly optimal (up to logarithmic terms) bound is proven. Moreover, its proof nicely constructs on the assumption that the corruption budget decay with time, making this assumption necessary for its good functioning\n\nOverall, I find the problem interesting and the paper well written: it nicely discusses all the limitations of their results and why extending them is not obvious", "weaknesses": "My main concern is on the assumption of the link function. More precisely, it seems to me that the only link function $\\sigma$ satisfying the conditions given between lines 143 and 153 is the constant function $1/2$.\nI guess the reason for this is mainly due to the fact that either (or both) $\\sigma$ should not be defined on $\\mathbb{R}$ (but on an interval), nor that it is concave. \n\nFor instance, I would have liked that these conditions include the simoid function (which is the mostly used link function in the literature) and would suggest the authors to provide at least one example of link function that satisfies their conditions. Actually, I am quite surprised of the concavity assumption of $\\sigma$. I guess a monotonicity assumption would be more desirable and natural here.\n\nAdditionally, this is not explicitly written, but it seems that the authors rely on the fact that $l_1^{\\sigma}>0$ in the whole paper. \n\n-------\n\nHere are some minor remarks:\n- I think the quantifiers in the lower bound results (Theorem 3.1, Lemma 3.1, Proposition) are given in a wrong order. It should typically be instead \"for any learner, there exists an instance ...\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)