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

## Abstract

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 ρ − 1 superscript 𝑡 𝜌 1 t^{\rho-1} italic_t start_POSTSUPERSCRIPT italic_ρ - 1 end_POSTSUPERSCRIPT for some “imperfection rate” ρ ∈ [ 0 , 1 ] 𝜌 0 1 \rho\in[0,1] italic_ρ ∈ [ 0 , 1 ] .
With T 𝑇 T italic_T as the total number of iterations, we establish a regret lower bound of Ω ⁢ ( max ⁡ { T , T ρ } ) Ω 𝑇 superscript 𝑇 𝜌 \Omega(\max\{\sqrt{T},T^{\rho}\}) roman_Ω ( roman_max { square-root start_ARG italic_T end_ARG , italic_T start_POSTSUPERSCRIPT italic_ρ end_POSTSUPERSCRIPT } ) for LIHF, even when ρ 𝜌 \rho italic_ρ is known. For the same setting, we develop the Robustified Stochastic Mirror Descent for Imperfect Dueling (RoSMID) algorithm, which achieves nearly optimal regret 𝒪 ~ ⁢ ( max ⁡ { T , T ρ } ) ~ 𝒪 𝑇 superscript 𝑇 𝜌 \tilde{\mathcal{O}}(\max\{\sqrt{T},T^{\rho}\}) over~ start_ARG caligraphic_O end_ARG ( roman_max { square-root start_ARG italic_T end_ARG , italic_T start_POSTSUPERSCRIPT italic_ρ end_POSTSUPERSCRIPT } ) . 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.

## 1 Introduction

Many real-world problems, such as personalized recommendation (Yue and Joachims, ; Immorlica et al., ; Yao et al., ) and fine-tuning generative models (Bai et al., ; Casper et al., ; Han et al., ), require learning from human feedback. Expressing preferences as numerical values or concrete functions is generally challenging for humans. Therefore, an approach that has achieved significant real-world success is to learn humans’ preferences by eliciting their comparative feedback between two options (Bai et al., ). A natural theoretical framework capturing such learning task is the seminal dueling bandits framework introduced by Yue and Joachims (). 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 a utility function of actions, alongside a link function that determines the probability of each action winning based on their utility difference. 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., ).

However, human feedback is often *imperfect*, a 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, ) neither perfectly know our preferences (Pu et al., ). A powerful framework that can capture this problem is robust bandit learning under adversarial corruption (Bogunovic et al., ; Saha and Gaillard, ; Di et al., ). However, assuming fully adversarial feedback from a regular human seems over-pessimistic at the first glance, hence might make our algorithm development overly conservative. 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., ; Wilson et al., ). 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 a lot in human feedback, one common finding in these studies is that *the feedback’s imperfection tends to decrease over time*, as humans interact more with the system (Cohen et al., ; Wilson et al., ; Immorlica et al., ; Yao et al., ).
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 a concave-utility continuous-action dueling bandit learning problem under adversarial utility corruption yet with decaying scale – formally, the scale is upper bounded by $\mathcal{O}(t^{\rho-1})$ at round $t$, for some $\rho\in[0,1]$ (hence the total amount of attack within time $T$ is $\mathcal{O}(T^{\rho})$). 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 a potentially negative answer to the above question. We prove a strong regret lower bound of $\Omega(d\max\{\sqrt{T},T^{\rho}\})$ under LIHF, where $d$ is the action’s dimension. This bound holds even when the decaying rate of imperfection index $\rho$ is known. This lower bound has the same order as recent lower bounds of dueling bandits under (the harder) arbitrary corruption (Agarwal et al., ; Di et al., ), 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. () and linear utility function case of Di et al. (). Therefore, neither their lower bounds nor their proof techniques are directly applicable to out 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 $\tilde{\mathcal{O}}(d\max\{\sqrt{T},T^{\rho}\})$ that matches the above lower bound, up to logrithmic terms, in the same setting (i.e., decaying corruption level $t^{\rho-1}$ with known $\rho$). Unlike previous corruption-robust dueling bandit algorithms based on robust $K$-armed bandits (Agarwal et al., ) or robustified LinUCB (Di et al., ), our algorithm is a gradient-based algorithm that is built upon the recent Noisy Comparison-based Stochastic Mirror Descent (NC-SMD) of Kumagai (). This is natural for our setup with continuous actions and strictly concave utility. While our algorithm itself can be viewed a natural generalization of Kumagai (), its analysis is highly non-trivial and much more complex, due to the necessity of accounting for corruption. Indeed, our main technical contribution in this result is the development of a new framework for analyzing the regret of gradient-based algorithms under (possibly arbitrary) corruption. Some novel ingredients of this framework includes a new regret decomposition lemma for dueling bandit which upper bounds total regret by the regret of decision and feedback error due to corruption and a lemma that quantifies bias in gradient estimation. This framework not only yields a tight analysis of our new algorithm, but also easily implies regret bounds for existing algorithms in *fully adversarial corruption environments*, such as the popular dueling bandit gradient descent (DBGD, Yue and Joachims ()). These upper bounds are looser than our lower bound for the LIHF setting. It is an intriguing open 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 LIHF. Finally, we conduct simulations which validate our theory.

Comparisons with Related Works. Since multiple recent works (Agarwal et al., ; Saha and Gaillard, ; Di et al., ) 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 et al., , ). This setting and our techniques are crucially different from earlier works.
Agarwal et al. (); Saha and Gaillard () consider the $K$-arm dueling bandit setting and utilizes the reduction of Ailon et al. () from dueling bandits to multi-$K$-armed bandits (MAB); (Di et al., ) considers linear utility setting where the unknowns is a parameter vector $\theta$, 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 and falls within the family of stochastic mirror descent. To the best of our knowledge, this is the first time a corruption-robust algorithm is developed for dueling bandits with continuous actions and strictly concave utilities, which is also why it 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 in 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 $\mathcal{O}(T^{3/4})$ (Flaxman et al., ; Yue and Joachims, ), which are considerably worse than the $\mathcal{O}(T^{1/2})$ for linear and for strongly concave utility.

The second main difference between our work and previous is the more restricted class of adversarial environments. Our model is motivated by imperfect human feedback whereas previous studies are motivated by arbitrarily adversarial adversaries. Finally, a more subtle difference is that the corruption 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 differences 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,\ldots,T\}$.
We use standard asymptotic notations including $\mathcal{O}(\cdot)$, $\Omega(\cdot)$, $\Theta(\cdot)$. We use $\tilde{\mathcal{O}}(\cdot)$, $\tilde{\Omega}(\cdot)$, $\tilde{\Theta}(\cdot)$ to hide logarithmic factors. We use $\|\cdot\|_{2}$ to define $L_{2}$ norm, $\|\cdot\|_{\infty}$ to define infinity norm, and $\lambda_{\max}(\cdot)$ to denote maximum eigenvalue.

Motivated by alignment of machine learning models with human preferences (Bai et al., ), we study learning from comparative human feedback within the seminal dueling bandit framework (Yue and Joachims, ) but account for “imperfections” in human feedback, as described below.

Basics of Continuous Dueling Bandits. We consider the dueling bandit framework with continuous *action* set $\mathcal{A}\subset\mathbb{R}^{d}$ (Yue and Joachims, ). At each round $t\in[T]$, the learner chooses two actions $a_{t},a^{\prime}_{t}$ to present to some human agent, henceforth denoted as the “user”. The user receives *utility* $\mu(a_{t}),\mu(a^{\prime}_{t})$ from the two actions respectively, and will pick one of these actions following a *link* function $\sigma(\cdot)$. In the absence of corruption, the user selects action $a_{t}$ with probability $\sigma(\mu(a_{t})-\mu(a^{\prime}_{t}))$ and chooses action $a^{\prime}_{t}$ otherwise. Since the comparison outcome has less errors compared to the exact utility value while still carries useful information about the underlying utility function $\mu$, this form of human feedback has been widely used for learning human preferences (Ailon et al., ; Maystre and Grossglauser, ; Bengs et al., ; Bai et al., ).
Following standard assumptions in this field (Yue and Joachims, ; Kumagai, ), we also assume

- 1.
the action set $\mathcal{A}$ is a convex compact set that contains the origin, has non-empty interior, and is contained in a $d$-dimensional ball of radius $R$;
- 2.
the utility function $\mu:\mathcal{A}\rightarrow\mathbb{R}$ is strongly concave and twice-differentiable. The following constants are useful for our algorithm analysis: $\mu$ is $L^{\mu}$-Lipschitz, $\alpha$-strongly concave,(^1^11 $\mu$ is $\alpha$-strongly concave for some $\alpha>0$ if $\mu(x)\geq\mu(y)+\langle\nabla\mu(x),x-y\rangle+\frac{\alpha}{2}\|y-x\|^{2}_{2}$ for any $x,y\in\mathcal{A}$.) $\kappa$-smooth, bounded, $R^{\mu}:=\sup_{a,a^{\prime}\in\mathcal{A}}\mu(a)-\mu(a^{\prime})$, and
$a^{*}:=\arg\max_{a\in\mathcal{A}}\mu(a)$ is the unique optimal within $\mathcal{A}$;
- 3.
the link function $\sigma:\mathbb{R}\rightarrow[0,1]$ is smooth, rotation-symmetric (i.e. $\sigma(x)=1-\sigma(-x)$), and concave for any $x\geq 0$. For the ease of analysis: let $l^{\sigma}_{1}$ [resp. $L^{\sigma}_{1}$] denote the lower [resp. upper] bound of the first-order derivative of $\sigma$. $\sigma$ is $L^{\sigma}$-Lipschitz and its second-order derivative $\sigma^{\prime\prime}$ is $L^{\sigma}_{2}$-Lipschitz and upper bounded by $R^{\sigma}_{2}$.

Some previous works restrict link function to specifically be the logistic link function (Saha, ; Xu et al., ). This, however, is not needed for our results.

Modeling Imperfect Human Feedback as a Restricted Form of Adversarial Corruption. To incorporate imperfect human feedback, we study a generalization of the dueling bandit framework above, by introducing a *corruption* term, $c(a,a^{\prime})$, to the utility difference. Formally, let $a\succ a^{\prime}$ represent the event where the user chooses $a$ over $a^{\prime}$. The probability of this event in the presence of corruption $c(a,a^{\prime})$ is denoted by $\hat{\mathbb{P}}(a\succ a^{\prime})$, expressed as $\hat{\mathbb{P}}(a\succ a^{\prime}):=\sigma(\mu(a)-\mu(a^{\prime})+c(a,a^{
\prime}))$. We denote the user’s preferential feedback under corruption as $\hat{\mathcal{F}}(a,a^{\prime})$, referred to as *imperfect dueling feedback*. Mathematically, $\hat{\mathcal{F}}(a,a^{\prime})$ follows a binomial distribution with mean $\hat{\mathbb{P}}(a\succ a^{\prime})$, as expressed by the following equation.

$$ $\hat{\mathcal{F}}(a,a^{\prime}):=\begin{cases}1\hskip 2.84526pt\text{w.p.} \hskip 2.84526pt\hat{\mathbb{P}}(a\succ a^{\prime})\\ 0\hskip 2.84526pt\text{w.p.}\hskip 2.84526pt1-\hat{\mathbb{P}}(a\succ a^{ \prime})\end{cases}$ $$

The “hat” notation in $\hat{\mathcal{F}}$ and $\hat{\mathbb{P}}$ is to emphasize the presence of corruption. When there is no corruption, we use $\mathbb{P}(a\succ a^{\prime}):=\sigma(\mu(a)-\mu(a^{\prime}))$ to represent the probability of the event $a\succ a^{\prime}$, and $\mathcal{F}(a,a^{\prime})$ to denote the corresponding dueling feedback.

We remark that the term $c(a,a^{\prime})$ above is often called “strong corruption” in the literature of adversarial corruption because it can be introduced after observing actions $a$ and $a^{\prime}$ and the corruption function, $c(\cdot)$, can depend on $\mu$ and past actions (Bogunovic et al., ; He et al., ; Di et al., ). 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,a^{\prime})$. 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 1 ( $\rho$ -Imperfect Human Feedback) .

The human feedback is said to be $\rho$-imperfect for some $\rho\in[0,1]$ if there exists a constant $C_{\kappa}$ such that corruption $c_{t}(a_{t},a^{\prime}_{t})$ satisfies $|c_{t}(a_{t},a^{\prime}_{t})|\leq C_{\kappa}t^{\rho-1},\forall t\in[T]$.(^2^22All our results naturally applies to $\rho<0$, which is a significantly easier situation since accumulated corruption is a constant in that case. Therefore, we will not explicitly consider it in this paper.)

The definition shows that $\rho$-imperfect human feedback is mathematically equivalent to a restricted form of strong adversarial corruption to user utility functions. The total corruption is bounded by $\sum_{t=1}^{T}|c_{t}(a_{t},a^{\prime}_{t})|\leq C_{\kappa}T^{\rho}$, which is a key parameter influencing the intrinsic difficulty of the learning 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” as corruption without decaying constraints and “$\rho$-Imperfect Human Feedback” as corruption with decaying constraints, as described in Definition 1. Through this modeling, we aim to: first create a 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.

Several points are worth noting about Definition 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 imperfect feedback (Immorlica et al., ; Yao et al., ; Wang et al., ). These studies assume that users do not know their true expected reward $\theta_{i}$ for each choice $i$ (i.e., arm) and instead behave based on an estimated reward $\hat{\theta}_{t,i}$ at time $t$. The utility difference $|\theta_{i}-\hat{\theta}_{t,i}|=c_{t}$ is modeled as a decreasing function of time, $t^{\rho-1}$, indicating that users improve their preference estimates over time. By viewing the human utility $\mu(a)$ as the average reward, our modeling of $\rho$-Imperfect Human Feedback shares the same spirit; it captures imperfect yet gradually improving human feedback (e.g., 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 could undergo a process of preference refinement during interactions with the model. Additionally, our model differs from recent corruption-robust dueling bandit studies (Komiyama et al., ; Saha and Gaillard, ; Di et al., ), which corrupt realized outcomes (e.g., flipping $a^{\prime}\succ a$ to $a\succ a^{\prime}$) and are motivated by adversaries like malicious users or fraudulent clicks (Deshpande and Montanari, ; Lykouris et al., ). 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 $\rho$-Imperfect Human Feedback ($\rho$-LIHF). The goal of the learner is to optimize her sequential actions to minimize the following dueling regret in the $\rho$-LIHF problem:

$$ $\text{Reg}_{T}:=\mathbb{E}\left(\sum^{T}_{t=1}\sigma(\mu(a^{*})-\mu(a_{t}))+ \sigma(\mu(a^{*})-\mu(a^{\prime}_{t}))-1\right).$ (1) $$

This regret measure has been extensively studied in prior literature (Yue and Joachims, ; Komiyama et al., ; Kumagai, ; Saha and Gaillard, ). 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 15.

###### Definition 1 ( ρ 𝜌 \rho italic_ρ -Imperfect Human Feedback) .

## 3 The Intrinsic Limit of LIHF

In this section, we study the intrinsic limit of learning from $\rho$-Imperfect Human Feedback. We are particularly interested in understanding whether learning from this restricted version of corrupted feedback is fundamentally “easier” than learning from arbitrarily adversarial corruption. Somewhat surprisingly, the answer seems to be *no*, as illustrated by the following lower bound result.

###### Theorem 1 .

There exists a $\rho$-Imperfect Human Feedback (see Definition 1), strongly concave utility function $\mu$, and link function $\sigma$ such that any learner has to suffer $\text{Reg}_{T}\geq\Omega\left(d\max\{\sqrt{T},T^{\rho}\}\right)$, even *with the knowledge of* $\rho$.

Notably, similar lower bound results have appeared in recent studies on adversarial corruption in bandits (Bogunovic et al., ), including dueling bandits (Agarwal et al., ; Di et al., ), showing the same lower bound $\Omega(d\max\{\sqrt{T},T^{\rho}\})$ (though they often use $C:=\Theta(T^{\rho})$ to denote total corruption budget). However, a few key distinctions are worth noting. First, Theorem 1 presents a 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 et al., ; Di et al., ). In their case, corruption can fully flip comparison outcomes, which is critical for promoting sub-optimal arms in their lower bound 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 $\mathcal{O}(t^{\rho-1})$.

The aforementioned difference from previous works (Agarwal et al., ; Di et al., ) also render our proof of Theorem 1 fundamentally different from (and significantly 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-theoretic lower bounds of statistical distributions to understand how small-scale corruption at each round could influence the overall function estimation errors. At the core of our proof is the following lower bound result for a different, and intuitively easier, problem: the standard bandit setup with direct reward feedback, as shown in Lemma 1 below. We then convert this lower bound for direct reward feedback to dueling feedback through a linear link function, i.e. $\sigma(x)=\frac{1+x}{2}$.

###### Lemma 1 (Lower Bound under Direct Reward Feedback) .

Consider bandit learning with direct reward feedback, where reward $r(a):=\mu(a)+\epsilon$, $\epsilon$ follows standard normal distribution. The action space $\mathcal{A}$ is contained in a $d$-dimensional unit ball, and $\mu$ is $\mu_{\theta}(a):=\theta^{\top}a-\frac{1}{2}\|a\|^{2}_{2}$, with $\theta\in\mathbb{R}^{d},\|\theta\|_{2}\leq 1$ . Under $\rho$-Imperfect Human Feedback (Definition 1), for any $T$ and $d\leq\frac{1}{C_{\kappa}}T^{1-\rho}$, there exists a $\theta$ such that for any learner under direct reward feedback, *even with the knowledge of $\rho$(^3^33We only consider $\rho\geq\frac{1}{2}$. If $\rho<\frac{1}{2}$, the lower bound degenerates to $\Omega(d\sqrt{T})$ (Kumagai, ).)*, has to suffer regret
$\text{Reg}_{T}:=\mathbb{E}\{\sum^{T}_{t=1}\mu_{\theta}(a^{*})-\mu_{\theta}(a_{
t})\}\geq\frac{d}{4}C_{\kappa}T^{\rho}.$

Proof [Proof Sketch of Lemma 1]
We aim to show that there exists a corruption strategy such that the regret incurred by any learner with direct reward feedback is no less than $\Omega(dT^{\rho})$. 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-Leibler (KL) divergence between the distribution of the corrupted reward feedback $\hat{v}_{t}$ conditioned on different values of $\theta$. Specifically, let $\theta$ be uniformly drawn from $\{-\beta,\beta\}^{d}$, for some constant $\beta>0$. Given an action $a_{t}$ and index $i$, conditioned on the value of the $i$-th coordinate of $\theta$, $\theta_{i}$, if $\theta_{i}>0$, then $\hat{v}_{t}$ is

$$ $\displaystyle\hat{v}_{t}=\mu_{\theta}(a_{t})+c_{t}(a_{t}|\theta_{i}>0)+\xi_{a_ {t}}=\left(-\frac{1}{2}\|a_{t}\|^{2}+\sum_{j\neq i}\theta_{j}a_{t,j}\right)+ \beta a_{t,i}+c_{t}(a_{t}|\theta_{i}>0)+\xi.$ $$

Conditioned on $\theta_{i}<0$, the corrupted reward feedback $\hat{v}^{\prime}_{t}$ is

$$ $\displaystyle\hat{v}^{\prime}_{t}=\mu_{\theta}(a_{t})+c_{t}(a_{t}|\theta_{i}<0 )+\xi_{a_{t}}=\left(-\frac{1}{2}\|a_{t}\|^{2}+\sum_{j\neq i}\theta_{j}a_{t,j} \right)-\beta a_{t,i}+c_{t}(a_{t}|\theta_{i}<0)+\xi.$ $$

The noise $\xi$ follows standard normal distribution.
Consider the following corruption strategy which sets $c_{t}(a_{t}|\theta_{i}>0):=-\beta a_{t,i}$ and $c_{t}(a_{t}|\theta_{i}<0):=\beta a_{t,i}$ to minimizes the KL divergence between $\hat{v}_{t}$ and $\hat{v}^{\prime}_{t}$. Together with $1$-strongly concavity of $\mu_{\theta}$, we can establish
$\mathbb{E}\left\{\sum^{T}_{t=1}\mu_{\theta}(a^{*})-\mu_{\theta}(a_{t})\right\}
\geq\frac{1}{2}\max\left\{\sum^{T}_{t=1}(\frac{C_{\kappa}T^{\rho-1}}{\beta}-
\beta)^{2},\frac{dT\beta^{2}}{2}\right\}.$
Since $d\leq\frac{1}{C_{\kappa}}T^{1-\rho}$, we can set $\beta:=\sqrt{C_{\kappa}}T^{\frac{\rho-1}{2}}$ to satisfy $\|\theta\|_{2}\leq 1$ and
to optimize the aforementioned lower bound. Then we obtain $\mathbb{E}\left\{\sum^{T}_{t=1}\mu_{\theta}(a^{*})-\mu_{\theta}(a_{t})\right\}
\geq dC_{\kappa}T^{\rho}/4$. Notice that the corruption level each round is bounded by $\beta\|a_{t}\|_{\infty}$. In the scenario when the radius of $\mathcal{A}$ is upper bounded by $\beta$, the corruption budget each round is bounded by $C_{\kappa}t^{\rho-1}$. It implies that the corruption is $\rho$-Imperfect Human Feedback, completing the proof.

Theorem 1 can be proved by converting the lower bound in Lemma 1 for direct reward feedback to dueling feedback (see Lemma 7). Before concluding this section, we note that the strongly concave utility function in the lower bound of Theorem 1 is not necessary. In particular, Proposition 1 below shows that similar lower bound applies to linear utilities as well. This result happens to resolve an open problem posed by Yao et al. () which studies a similar learning from imperfect user problem with linear utility and dueling feedback (they termed it the “learning from a learning user” problem), develops a no-regret learning algorithm for that setting, but left the lower bound as an open problem. Proposition 1 implies that their upper bound’s dependence on $T$ is tight. We direct readers to Appendix A.1 and A.2 for proof details of Lemma 1 and Proposition 1.

###### Proposition 1 .

There exists an LIHF instance with $\rho$-Imperfect Human Feedback (Definition 1), linear user utility $\mu$, and link function $\sigma$, such that any learner has to suffer $\text{Reg}_{T}\geq\Omega(d\max\{\sqrt{T},T^{\rho}\})$, *even with the knowledge of $\rho$*.

###### Theorem 1 .

###### Lemma 1 (Lower Bound under Direct Reward Feedback) .

###### Proposition 1 .

## 4 An Efficient and Tight ρ 𝜌 \rho italic_ρ -LIHF Algorithm

In this section, we present a learning algorithm with a regret upper bound that matches the $\Omega(d\max\{\sqrt{T},T^{\rho}\})$ lower bound, up to a logarithmic term, for the $\rho$-LIHF setting discussed in Section 3. Our algorithm, Robustified Stochastic Mirror Descent for Imperfect Dueling (RoSMID), outlined in Algorithm 1, generalizes the Noisy Comparison-Based Stochastic Mirror Descent (NC-SMD) from Kumagai (). RoSMID employs a corruption-aware learning rate, $\eta_{\rho}:=\sqrt{\log T}/(dT^{\max\{0.5,\rho\}})$, to slow down the learning when the imperfection level $\rho$ is large, with NC-SMD being the special case with $\rho=0$. Although RoSMID may initially seem like a pretty natural extension of NC-SMD, the choice of optimal $\eta_{\rho}$ is 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 algorithms.

###### Theorem 2 .

RoSMID satisfies $\text{Reg}_{T}\leq\tilde{\mathcal{O}}(d\max\{\sqrt{T},T^{\rho}\})$ for any $\rho$-LIHF problem.

The main technical contribution underlying this theorem is a novel framework for analyzing continuous 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 2, but also allows us to easily derive regret guarantees for other dueling bandit algorithms under adversarial corruption, as demonstrated in Subsection 4.1. While recent works have explored corruption-robust regret analysis for dueling bandits with $K$ arms (Saha and Gaillard, ) or linear utilities (Di et al., ), neither their algorithmic approaches nor their analysis techniques can be applied to our setting with arbitrary concave utilities in continuous action space.

Figure: Algorithm 1 Robustified Stochastic Mirror Descent for Imperfect Dueling (RoSMID)

The full proof of Theorem 2 is quite involved and is deferred to Appendix B. 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 $\rho$-LIHF and is also the most involved and novel step.

Proof [Proof Sketch]
The proof of Theorem 2 is divided into four major steps.

Step 1: quantifying bias of gradient estimation in $\rho$-LIHF

Our proof starts from quantifying the bias of the gradient $\hat{g}_{t}$ caused by $\rho$-Imperfect Human Feedback, as shown in the following Lemma 2.

###### Lemma 2 (Corrupted Gradients Estimation) .

The gradient $\hat{g}_{t}$ in Line 6 of Algorithm 1 satisfies

$$ $\mathbb{E}\left(\hat{g}_{t}|a_{t}\right)=\nabla|_{a=a_{t}}\bar{P}_{t}(a)- \mathbb{E}\left(b_{t}|a_{t}\right).$ $$

where $\bar{P}_{t}(a):=\mathbb{E}_{x\in\mathbb{B}}\left[\mathbb{P}(a_{t}\succ a+
\nabla^{2}R_{t}(a_{t})^{-\frac{1}{2}}x)\right]$ (with $\mathbb{B}$ as the unit ball) is the smoothed probability that $a_{t}$ is preferred over any action $a$ , and $b_{t}=d\left(\mathbb{P}(a_{t}\succ a^{\prime}_{t})-\hat{\mathbb{P}}(a_{t}\succ
a
^{\prime}_{t})\right)\nabla^{2}\mathcal{R}_{t}(a_{t})^{\frac{1}{2}}u_{t}$.

That is, the scale of bias at round $t$, term $b_{t}$, defined in Lemma 2, depends linearly on $a$’s dimension $d$ and the difference between the true and corrupted probability that $a_{t}$ is preferred over $a^{\prime}_{t}$. The direction of $b_{t}$ is determined by the sampled direction $u_{t}$ projected by the square root of Hessian of the self concordant function $\mathcal{R}_{t}$, evaluated at $a_{t}$. This characterization is essential for our following regret decomposition.

Step 2: decomposing regret for dueling bandits into regret of decision and feedback error

Core to our proof is a “regret decomposition” 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 (2)), and regret due to corruption, referred as feedback error (second term in (2)).

###### Lemma 3 (Regret Decomposition for Dueling Bandits) .

The $\text{Reg}_{T}$ of Algorithm 1 satisfies:

$$ $\text{Reg}_{T}\leq\underbrace{\frac{C_{0}}{\eta_{\rho}}\log(T)+8d^{2}\eta_{ \rho}T+2L^{\mu}L^{\sigma}_{1}R}_{{\color[rgb]{1,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{1,0,0}Regret\hskip 2.84526ptof\hskip 2.84526ptDecision}}+ \underbrace{2\mathbb{E}\left\{\sum^{T}_{t=1}b^{\top}_{t}(a_{t}-a^{*}_{T}) \right\}}_{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0} Feedback\hskip 2.84526ptError}},$ (2) $$

where $C_{0}:=(2\nu+4L^{\sigma}_{1}\kappa+4R^{\sigma}_{2}(L^{\mu})^{2}+L^{\mu}L^{
\sigma}_{1}\kappa)/\lambda$, and $a^{*}_{T}:=\frac{1}{T}a_{1}+(1-\frac{1}{T})a^{*}$.

We remark that similar regret decomposition has been shown to be useful for reinforcement learning which has direct reward feedback (Foster et al., ). However, to the best of our knowledge, Lemma 3 is the first to exhibit such a decomposition for dueling feedback, which contains much sparser information 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 (2) is standard. Thus, this step develops a novel upper bound for bounding the regret from feedback error, as shown below.

###### Lemma 4 (Feedback Error) .

The feedback error term in (2) can be bounded as follows:

$$ $\displaystyle\mathbb{E}\left\{\sum^{T}_{t=1}b^{\top}_{t}(a_{t}-a^{*}_{T})\right\}$ $\displaystyle\leq C_{1}d\sqrt{\eta_{\rho}}\mathbb{E}\left\{\sum^{T}_{t=1}\sqrt {t}|c_{t}(a_{t},a^{\prime}_{t})|\sqrt{\mu(a^{*})-\mu(a_{t})}\right\}+C_{2}dT^{ \rho}+2d\sqrt{\lambda}\sqrt{\eta_{\rho}T},$ $$

where $C_{1}:=\sqrt{\frac{2\lambda(L^{\sigma})^{2}}{\alpha}}$, and $C_{2}:=2L^{\sigma}R\sqrt{\sup_{a\in\mathcal{A}}\lambda_{\max}\left(\nabla^{2}
\mathcal{R}(a)\right)+2\phi}$.

To our knowledge, such a bound is new for dueling bandits. The less common term in the bound is $\sqrt{\mu(a^{*})-\mu(a_{t})}$. It comes from the strong concavity of the utility function $\mu$, which implies $\langle b_{t},a_{t}-a^{*}\rangle\leq\|b_{t}\|_{2}\|a_{t}-a^{*}\|_{2}\leq\|b_{t
}\|_{2}\sqrt{\frac{2}{\alpha}(\mu(a^{*})-\mu(a_{t}))}$.

Step 4: The *iterative regret refinement* analysis and resultant optimal learning rate

Our last but the most intriguing step is to pin down the regret upper bound. Given the bounds from previous steps, the only remaining term to upper bound is
$\mathbb{E}\left\{\sum^{T}_{t=1}\sqrt{t}|c_{t}(a_{t},a^{\prime}_{t})|\sqrt{\mu(
a^{*})-\mu(a_{t})}\right\}$ in Lemma 4. We can upper bound $\sqrt{t}|c_{t}(a_{t},a^{\prime}_{t})|$ by $C_{\kappa}t^{\rho-\frac{1}{2}}$ under $\rho$-Imperfect Human Feedback assumption (this is the point where we start to need the decaying structure in Definition 1). This is a tricky question, since this term involving optimal action $a^{*}$ closely connects to the regret $\text{Reg}_{T}$ itself (see (1)). 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:=\mathbb{E}\left(\sum^{T}_{t=1}\mu(a^{*})-\mu(a_{t})\right)$ can be leveraged to derive a good upper bound for term $B:=\mathbb{E}\left\{\sum^{T}_{t=1}t^{\rho-\frac{1}{2}}\sqrt{\mu(a^{*})-\mu(a_{
t})}\right\}$, which can then be leveraged to derive a good upper bound for the regret $\text{Reg}_{T}$, 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 a tight bound. The first step is to derive a good upper bound for term $B$ using term $A$, which is shown in Lemma 5. The second step is to prove that this iterative refinement consistently improves the regret bound, eventually reaching a limit. This is demonstrated by Lemma 6. The choice of learning rate $\eta_{\rho}=\frac{\sqrt{\log T}}{dT^{\max\{1/2,\rho\}}}$ is crucial in the second step; in a sense, it is the only choice that converges to the tight regret upper bound $\tilde{\mathcal{O}}\left(d\max\{\sqrt{T},T^{\rho}\}\right)$ in the limit, rather than exploding the bound.

###### Lemma 5 .

If $A=\mathbb{E}\left(\sum^{T}_{t=1}[\mu(a^{*})-\mu(a_{t})]\right)\leq\mathcal{O}(
T^{\frac{1}{2}+\psi})$ for some $\psi\in[0,\frac{1}{2})$, then we must have $B=\mathbb{E}\left(\sum^{T}_{t=1}t^{\rho-\frac{1}{2}}\sqrt{\mu(a^{*})-\mu(a_{t}
)}\right)\leq\mathcal{O}(T^{-\frac{1}{4}+\frac{\psi}{2}+\rho})$.

To prove Lemma 5, we first bound term $B$ by $\sum^{T}_{t=1}t^{\rho-1/2}\sqrt{\mathbb{E}[\mu(a^{*})-\mu(a_{t})]}$ using the concavity of the square root function. The key novelty of our proof is to use the Abel’s equation (Williams, ) to re-arrange the term $\sum^{T}_{t=1}t^{\rho-1/2}\sqrt{\mathbb{E}[\mu(a^{*})-\mu(a_{t})]}$ and establish its connection with another term $C=\sum^{T}_{t=1}\sqrt{\mathbb{E}[\mu(a^{*})-\mu(a_{t})]}$.
We finally connect term $C$ with the term $A$ in the lemma statement, by proving $\sum^{T}_{t=1}\sqrt{\mathbb{E}[\mu(a^{*})-\mu(a_{t})]}\leq\mathcal{O}(T^{\frac
{3}{4}+\frac{\psi}{2}})$ if $\mathbb{E}\left(\sum^{T}_{t=1}\mu(a^{*})-\mu(a_{t})\right)\leq\mathcal{O}(T^{
\frac{1}{2}+\psi})$ via concavity of square root.
Together with the decay scale $t^{\rho-1}$, which allows $t^{\rho-1}-(t+1)^{\rho-1}\leq t^{\rho-2}$, we obtain the tight bound $\mathcal{O}(T^{-\frac{1}{4}+\frac{\psi}{2}+\rho})$.(^5^55If corruption $c_{t}$ was arbitrary, then $t^{\rho-1/2}$ is $\sqrt{t}|c_{t}|$, and the bound could deteriorate to $\mathcal{O}(T^{\frac{2\rho}{3}})$ in the first $T^{\rho}$ rounds.)

Armed with Lemma 5, we can use it to prove the induction claim (Lemma 6). 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 6 (Induction Claim) .

Consider $T>\sqrt{2L^{\mu}L^{\sigma}_{1}R}$ and $\eta_{\rho}=\frac{\sqrt{\log T}}{dT^{\max\{1/2,\rho\}}}$. If $\text{Reg}_{T}\leq 144dK\sqrt{\log T}T^{\rho+\frac{\frac{3}{2}-\rho}{2^{k}}}$ for some integer $k$, then we must also have $\text{Reg}_{T}\leq 144dK\sqrt{\log T}T^{\rho+\frac{\frac{3}{2}-\rho}{2^{k+1}}}$. $K$ is a instance-dependent constant, where $K:=\max\left\{C_{0},\frac{C_{2}C_{\kappa}}{\sqrt{\log T}},(L^{\sigma}C_{\kappa
})^{2},2\sqrt{\lambda}RC_{\kappa}L^{\sigma}\right\}$, $C_{0}$ and $C_{2}$ defined in Lemma 3 and 4 respectively,

###### Theorem 2 .

###### Lemma 2 (Corrupted Gradients Estimation) .

###### Lemma 3 (Regret Decomposition for Dueling Bandits) .

###### Lemma 4 (Feedback Error) .

###### Lemma 5 .

###### Lemma 6 (Induction Claim) .

### 4.1 Additional Applications of the Above Regret Analysis Framework

To showcase useful applications of the new regret analysis framework above for proving Theorem 2, in this subsection we employ the framework to study continuous dueling bandits under *arbitrary* and *agnostic* corruption — i.e., remove decaying constraints on $c_{t}$ and $\rho$ 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) (Yue and Joachims, ), 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 it is the only one requiring knowledge of $\rho$ and decaying corruption). Additionally, we present these results to offer a set of principled benchmark algorithms for the experiments in Section 5.

###### Proposition 2 (Efficiency-Robustness Tradeoff in RoSMID) .

If the total corruption level satisfies $\sum^{T}_{t=1}|c_{t}(a_{t},a^{\prime}_{t})|\leq\mathcal{O}(T^{\rho})$, then for any $\alpha\in[\frac{1}{2},1)$, if the utility function is strongly concave, for a sufficiently large round $T$, by choosing learning rate $\eta_{\rho}=\frac{\sqrt{\log T}}{2d}T^{-\alpha}$

- 1.
(Robustness) RoSMID incurs $\text{Reg}_{T}\leq\tilde{\mathcal{O}}(dT^{\alpha}+\sqrt{d}T^{\frac{1}{2}(1-
\alpha)+\rho}+dT^{\rho})$.
- 2.
(Efficiency) There exists a strongly concave utility function $\mu$ and a link function $\sigma$ such that $\text{Reg}_{T}$ suffered by RoSMID is at least $\Omega\left(T^{\alpha}\right)$ in scenario without corruption.

###### Proposition 3 (Efficiency-Robustness Tradeoff in DBGD) .

If the total corruption level satisfies $\sum^{T}_{t=1}|c_{t}(a_{t},a^{\prime}_{t})|\leq\mathcal{O}(T^{\rho})$, then for any $\alpha\in(0,\frac{1}{4}]$, if utility function $\mu$ is generally concave, for a sufficiently large round $T$, choosing $\gamma=\frac{R}{\sqrt{T}}$ and $\delta=\frac{\sqrt{2Rd}}{\sqrt{13L^{\sigma}L^{\mu}}T^{\alpha}}$ for DBGD

- 1.
(Robustness) $\text{Reg}_{T}$ incurred by DBGD satisfies $\text{Reg}_{T}\leq\mathcal{O}(\sqrt{d}T^{1-\alpha}+\sqrt{d}T^{\alpha+\rho})$.
- 2.
(Efficiency) There exists a linear utility function $\mu$ and a link function $\sigma$ such that $\text{Reg}_{T}$ suffered by DBGD is at least $\Omega\left(T^{1-\alpha}\right)$ in scenario without corruption.

Both propositions illustrate the tradeoff between *learning efficiency* and *robustness* to adversarial corruption, achieved through their tunable learning rate $\eta_{\rho},\gamma,\delta$ (learning rate in DBGD is $\frac{\gamma\delta}{d}$; we direct reader to Algorithm 3 for detail). Specifically, greater tolerance for agnostic corruption (i.e., larger $\alpha$ in Proposition 2) results in worse regret in non-corrupt settings. A similar robustness-accuracy trade-off has been studied in classification problems with adversarial examples, both empirically (Tsipras et al., ) and theoretically (Zhang et al., ). However, to our knowledge, this is the first formal analysis of such a trade-off in online learning. While expanding the confidence region for UCB-type algorithms to handle agnostic corruption in linear contextual dueling bandits increases tolerance for corruption but worsens regret—sharing a similar idea of a trade-off (Di et al., )—it’s unclear if this approach necessarily reduces efficiency. In contrast, our work demonstrates that adjusting learning rates in gradient-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 as algorithm-dependent lower bounds, concretely demonstrating that for certain problem instances, increasing robustness necessarily decreases the learning efficiency of the algorithm.

###### Proposition 2 (Efficiency-Robustness Tradeoff in RoSMID) .

###### Proposition 3 (Efficiency-Robustness Tradeoff in DBGD) .

## 5 Experiments

In this section, we validate our theoretical analysis of RoSMID and DBGD under $\rho$-Imperfect Human Feedback through simulations. We also compare their performance against two baseline algorithms: Doubler and the heuristic algorithm, Sparring, proposed by Ailon et al. (). For Sparring, we use bandit gradient descent (Flaxman et al., ) as the black-box bandit algorithm. We direct readers to Appendix E for implementation details.

Experiment Setup. We consider a standard experiment setup, which adopts a strongly concave utility $\mu_{\theta}(a):=\theta^{\top}a-\frac{1}{2}\|a\|^{2}_{2}$, and a logistic link function $\sigma(x)=\frac{1}{1+\exp(-x)}$. We choose $d=5$, and $T=10^{5}$. Our action space $\mathcal{A}$ is a $d$-dimensional ball with radius $R=10$. The preference parameter $\theta$ is randomly sampled from the surface of $\mathcal{A}$. In our problem setting, the optimal action $a^{*}=\theta$ and $\mu_{\theta}(a^{*})=50$. We simulate $\rho$-Imperfect Human Feedback for $\rho\in[0.5,1]$.

Figure: Figure 1: Robustness of RoSMID for $\rho$-LIHF
Refer to caption: extracted/5899968/ICLR25/image/known.png

Results and Discussion. Figure 1 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 a distinct value of $\rho$. The shaded region indicates $\pm$ 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 1 supports Theorem 2, as for $\rho\in[0.5,1)$, the estimated slope is less than $\rho$, suggesting that the choice of $\eta_{\rho}=\frac{\sqrt{\log T}}{dT^{\max\{1/2,\rho\}}}$ for RoSMID results in a regret bound of at most $\tilde{\mathcal{O}}(T^{\rho})$.

Figure 2 compares the performance of our proposed algorithms, variants of DBGD and RoSMID, with two baseline algorithms, Sparring and Doubler, in the setting when $c_{t}$ is arbitrary and agnostic. We set the parameter $\alpha=1/4$ for DBGD and $\alpha=1/2$ for RoSMID. When $\rho$ is unknown to the algorithms, these parameter choices enable DBGD and RoSMID to tolerate $\mathcal{O}(T^{3/4})$ levels of unknown corruption, 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 comparably to RoSMID, despite being a heuristic approach without theoretical guarantees. In contrast, Doubler exhibits the worst performance, likely because its theoretical guarantees are only applicable to linear link functions, which differs from our experimental setup. We direct readers to Appendix E for experiment results with other choice of $\alpha$ for efficiency-robustness tradeoff.

Figure: Figure 2: For each algorithm, we tested its performance under $\rho$-Imperfect Human feedback with $\rho=0.5,0.6,0.75$. For each $\rho$, we presented a line plot of the average regret over five simulations, accompanied by $\pm$ 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.
Refer to caption: extracted/5899968/ICLR25/image/lu.png

## 6 Conclusion

In conclusion, this paper enhances the understanding of continuous dueling bandits by addressing $\rho$-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 efficiency-robustness trade-off in gradient-based algorithms. Our experimental results corroborate the theoretical predictions. A promising future direction is the development of an algorithm that achieves $\tilde{O}(d\sqrt{T}+dT^{\rho})$ 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.

## A Proofs for Theorem 1

###### Theorem (Theorem 1 restated) .

There exists a $\rho$-Imperfect Human Feedback (see Definition 1), strongly concave utility function $\mu$, and link function $\sigma$ such that any learner has to suffer $\text{Reg}_{T}\geq\Omega\left(d\max\{\sqrt{T},T^{\rho}\}\right)$, even *with the knowledge of* $\rho$.

Proof
Before showing the regret lower bound proof for Theorem 1, let’s first establish the following Lemma 7, 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. (). To prove Lemma 7, in addition to $\text{Reg}_{T}$, we introduce a new metric to measure the performance of algorithm under dueling feedback, which we coin functional regret $\text{Reg}^{\text{FO}}_{T}$, defined as follows.

$$ $\text{Reg}^{\text{FO}}_{T}:=\mathbb{E}\left\{\sum^{T}_{t=1}\mu(a^{*})-\mu(a_{t })+\mu(a^{*})-\mu(a^{\prime}_{t})\right\}.$ (3) $$

###### Lemma 7 .

Given a utility function $\mu$, if the regret lower bound for algorithm with bandit reward feedback is $\overline{\text{Reg}}$, then
any learner with dueling feedback has to suffer regret $\text{Reg}^{\text{FO}}_{T}\geq 2\overline{\text{Reg}}$.

Proof
We prove our claim by contradiction. Let $(a_{0,t},a_{1,t})$ be the pair of recommendation at round $t$.
Suppose $\text{Reg}^{\text{FO}}_{T}<2\overline{\text{Reg}}$. As a result, at least one of the following inequality must hold:

$$ $\displaystyle\begin{split}\mathbb{E}\left\{\sum^{T}_{t=1}\mu(a^{*})-\mu(a_{0,t })\right\}&\leq\overline{\text{Reg}};\\ \mathbb{E}\left\{\sum^{T}_{t=1}\mu(a^{*})-\mu(a_{1,t})\right\}&\leq\overline{ \text{Reg}}.\end{split}$ (4) $$

Consider a principal who can observe the interaction between a user and the learner $\mathcal{L}$, then we can construct two algorithms $\mathcal{L}_{0}$ and $\mathcal{L}_{1}$ as follows.

Figure: Algorithm 2 Algorithm $\mathcal{L}_{i}$

From (4), we know that at least one of $\{\mathcal{L}_{0},\mathcal{L}_{1}\}$ achieves an expected regret lower than $\overline{\text{Reg}}$. However, we know all algorithm with bandit feedback with utility function $\mu$ has to occur regret at least $\overline{\text{Reg}}$, contradiction. Therefore, Lemma 7 must hold, which completes the proof.

Next, we prove Theorem 1. First, consider the case $\rho\leq 0.5$. Given that the utility function is strongly concave, by applying Lemma 8, we have $\overline{\text{Reg}}=0.02\min\{T,d\sqrt{T}\}$. From Lemma 7, we also obtain $\text{Reg}^{\text{FO}}_{T}\geq 0.04\min\{T,d\sqrt{T}\}$. Using the linear link function $\sigma(x)=\frac{1}{2}+\frac{1}{2}x$, it follows that $\text{Reg}_{T}\geq 0.02\min\{T,d\sqrt{T}\}\geq\Omega(d\max\{\sqrt{T},T^{\rho}\})$, completing the proof.

###### Lemma 8 (Theorem 6 in (Shamir, 2013 ) ) .

Let the number of rounds $T$ be fixed. Then for any learner, there exists a quadratic function of the form $\mu_{\theta}(a):=\theta^{\top}a-\frac{1}{2}\|a\|^{2}$ which is minimized at $\theta$ and $\|\theta\|_{2}\leq 0.5$ such that

$$ $\mathbb{E}\left(\sum^{T}_{t=1}\mu_{\theta}(a^{*})-\mu_{\theta}(a_{t})\right) \geq 0.02\min\left\{T,d\sqrt{T}\right\}.$ $$

Now, let’s focus on the scenario when $\rho>0.5$. In essence, we want to extend Lemma 8 to the scenario in presence of adversarial corruption induced by $\rho$-Imperfect Human Feedback. If we can show the regret lower bound can be generalized to $\Omega(dT^{\rho})$, then applying the same technique which uses Lemma 7 to connect regret suffered under bandit reward feedback and regret suffered under dueling feedback and choose linear link function to connect $\text{Reg}^{\text{FO}}_{T}$ and $\text{Reg}_{T}$, we will get the desired regret lower bound. The extension of Lemma 8 is proven at section A.1.

###### Theorem (Theorem 1 restated) .

###### Lemma 7 .

###### Lemma 8 (Theorem 6 in (Shamir, 2013 ) ) .

### A.1 Proof for Lemma 1

###### Lemma (Lemma 1 restated) .

Consider bandit learning with direct reward feedback, where reward $r(a):=\mu(a)+\epsilon$, $\epsilon$ follows standard normal distribution. The action space $\mathcal{A}$ is contained in a $d$-dimensional unit ball, and $\mu$ is $\mu_{\theta}(a):=\theta^{\top}a-\frac{1}{2}\|a\|^{2}_{2}$, with $\theta\in\mathbb{R}^{d},\|\theta\|_{2}\leq 1$ . Under $\rho$-Imperfect Human Feedback (Definition 1), for any $T$ and $d\leq\frac{1}{C_{\kappa}}T^{1-\rho}$, there exists a $\theta$ such that for any learner under direct reward feedback, *even with the knowledge of $\rho$*, has to suffer regret
$\text{Reg}_{T}:=\mathbb{E}\{\sum^{T}_{t=1}\mu_{\theta}(a^{*})-\mu_{\theta}(a_{
t})\}\geq\frac{d}{4}C_{\kappa}T^{\rho}.$

Proof
To prove Lemma 1, we aim to prove that there exists a corruption strategy such that the regret incurred by any learner with *imperfect dueling feedback* is not less than $\Omega(dT^{\rho})$. The formulation of such a corruption strategy hinges on the observation that when the utility function $\mu_{\theta}$ adopts the quadratic form parameterized by $\theta$, specifically $\mu_{\theta}(a)=\theta^{\top}a-\frac{1}{2}\|a\|^{2}_{2}$, which is both smooth and strongly concave, then the regret incurred by the learner is bounded below by the sum of the Kullback-Leibler (KL) divergence between the distribution of the *corrupted reward* feedback obtained at round $t$, denoted $\hat{v}_{t},t\in[T]$, conditioned on different possible values of $\theta$. (see Lemma 10). Assume that $\theta$ is uniformly drawn from $\{-\beta,\beta\}^{d}$, given an action $a_{t}$, conditioned on $\theta_{i}>0$, the corrupted reward feedback $\hat{v}_{t}$ is

$$ $\displaystyle\hat{v}_{t}=\mu_{\theta}(a_{t})+c_{t}(a_{t}|\theta_{i}>0)+\xi= \underbrace{\left(-\frac{1}{2}\|a_{t}\|^{2}+\sum_{j\neq i}\theta_{j}a_{t,j} \right)+\beta a_{t,i}+c_{t}(a_{t}|\theta_{i}>0)}_{{\color[rgb]{1,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mu_{1}}}+\xi.$ (5) $$

Conditioned on $\theta_{i}<0$, the corrupted reward feedback $\hat{v}_{t}$ is

$$ $\displaystyle\hat{v}_{t}=\mu_{\theta}(a_{t})+c_{t}(a_{t}|\theta_{i}<0)+\xi= \underbrace{\left(-\frac{1}{2}\|a_{t}\|^{2}+\sum_{j\neq i}\theta_{j}a_{t,j} \right)-\beta a_{t,i}+c_{t}(a_{t}|\theta_{i}<0)}_{{\color[rgb]{1,0,0} \definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mu_{2}}}+\xi.$ (6) $$

We use $c_{t}(a_{t}|\theta_{i}>0)$ and $c_{t}(a_{t}|\theta_{i}<0)$ to empathize the fact that the magnitude and sign of corruption can be dependent on $\theta$. $\xi$ follows a standard Gaussian distribution. Therefore, $\hat{v}_{t}$ in Equation 5 follows $\text{N}(\mu_{1},1)$. $\hat{v}_{t}$ in Equation 6 follows $\text{N}(\mu_{2},1)$. By using Lemma 9, we have

$$ $\displaystyle\text{D}_{\text{KL}}(\text{N}(\mu_{1},1)||\text{N}(\mu_{2},1))=( \mu_{1}-\mu_{2})^{2}.$ $$

###### Lemma 9 (KL Divergence for Normal Distribution) .

Let $N(\mu,\sigma^{2})$ represent a Gaussian distribution variable with mean $\mu$ and variance $\sigma^{2}$. Then

$$ $\text{D}_{\text{KL}}(N(\mu_{1},\sigma^{2})||N(\mu_{2},\sigma^{2}))=\frac{(\mu_ {1}-\mu_{2})^{2}}{2\sigma^{2}}.$ $$

To optimize the lower bound in Lemma 10, the adversary selects $c_{t}(a_{t}|\theta_{i}>0)$ and $c_{t}(a_{t}|\theta_{i}<0)$ to minimize the difference between $\mu_{1}$ and $\mu_{2}$. Consider the following corruption strategy: when $\theta_{i}>0$, set $c_{t}(a_{t}|\theta_{i}>0)=-\beta a_{t,i}$; when $\theta_{i}<0$, set $c_{t}(a_{t}|\theta_{i}<0)=\beta a_{t,i}$. This strategy ensures that $\mu_{1}=\mu_{2}$.

Next step is to determine the value of $\beta$. Notice that the corruption budget is $C_{\kappa}T^{\rho}$. To execute the corruption strategy described above, it requires

$$ $\sum^{T}_{t=1}|c_{t}(a_{t})|\leq\beta\sum^{T}_{t=1}\|a_{t}\|_{\infty}\leq C_{ \kappa}T^{\rho}.$ (7) $$

Therefore, by exploiting the fact that $\mu_{\theta}$ is $1$-strongly concave, we establish another lower bound for the regret by

$$ $\displaystyle\mathbb{E}\left\{\sum^{T}_{t=1}\mu_{\theta}(a^{*})-\mu_{\theta}(a _{t})\right\}$ $\displaystyle\geq\frac{1}{2}\mathbb{E}\left\{\sum^{T}_{t=1}\|a_{t}-\theta\|^{2 }_{2}\right\}$ $\displaystyle\geq\frac{1}{2}\mathbb{E}\left\{\sum^{T}_{t=1}(\|a_{t}\|_{\infty} -\beta)^{2}\right\}$ $\displaystyle\geq\frac{1}{2}\sum^{T}_{t=1}(C_{\kappa}T^{\rho-1}/\beta-\beta)^{ 2}.$ $$

Since $|a_{t,i}-\theta_{i}|\geq||a_{t,i}|-\beta|$ for all $i$, we obtain the second inequality. By utilizing the corruption constraint (7), we derive the last inequality, which is minimized when $\|a_{t}\|_{\infty}=\frac{C_{\kappa}T^{\rho-1}}{\beta}$ for all $t$. Together with Lemma 10, we have:

$$ $\mathbb{E}\left\{\sum^{T}_{t=1}\mu_{\theta}(a^{*})-\mu_{\theta}(a_{t})\right\} \geq\frac{1}{2}\max\left\{\sum^{T}_{t=1}(C_{\kappa}T^{\rho-1}/\beta-\beta)^{2} ,\frac{dT\beta^{2}}{2}\right\}.$ (8) $$

We select $\beta$ to optimize the lower bound in Equation (8). Since $d\leq\frac{1}{C_{\kappa}}T^{1-\rho}$, we can set $\beta=\sqrt{C_{\kappa}}T^{\frac{\rho}{2}-\frac{1}{2}}$ to satisfy $\|\theta\|_{2}\leq 1$. Then we obtain $\mathbb{E}\left\{\sum^{T}_{t=1}\mu_{\theta}(a^{*})-\mu_{\theta}(a_{t})\right\}
\geq dC_{\kappa}T^{\rho}/4$. Notice that the corruption level each round is bounded by $\beta\|a_{t}\|_{\infty}$. Consider the scenario when the radius of the *action* space $\mathcal{A}$ is upper bounded by $\beta$, then the corruption budget each round is bounded by $C_{\kappa}t^{-1+\rho}$, which satisfies the definition of $\rho$-Imperfect Human Feedback, which completes the proof.

###### Lemma 10 .

Let’s consider the utility function $\mu_{\theta}(a):=\theta^{\top}a-\frac{1}{2}\|a\|^{2}_{2}$. Let $\hat{v}_{1},\hat{v}_{2},\ldots,\hat{v}_{T}$ be a sequence of *corrupted reward feedback* obtained by a learner. Then there exists a $\theta\in\mathbb{R}^{d},\|\theta\|_{2}\leq 1$, uniformly drawn from $\{-\beta,\beta\}^{d}$, such that the regret suffered by the learner is

$$ $\displaystyle\mathbb{E}\left\{\sum^{T}_{t=1}\mu_{\theta}(a^{*})-\mu_{\theta}(a _{t})\right\}\geq\frac{dT\beta^{2}}{4}\left(1-\sqrt{\frac{1}{d}\sum^{d}_{i=1} \sum^{T}_{t=1}\mathbb{D}_{t,i}}\right).$ $$

$\mathbb{D}_{t,i}:=\sup_{\{\theta_{j}\}_{j\neq i}}\text{D}_{\text{KL}}\left(
\mathbb{P}(\hat{v}_{t}|\theta_{i}>0,\{\theta_{j}\}_{j\neq i},\{\hat{v}_{l}\}^{
t-l}_{l=1})||\mathbb{P}(\hat{v}_{t}|\theta_{i}<0,\{\theta_{j}\}_{j\neq i},\{
\hat{v}_{l}\}^{t-l}_{l=1})\right)$. $\text{D}_{\text{KL}}$ is the KL divergence between two distributions.

Proof
Using the similar argument in Shamir (), assume that the learner is deterministic: $a_{t}$ is a deterministic function of the realized corrupted reward feedback $\hat{v}_{1},\hat{v}_{2},\ldots,\hat{v}_{t-1}$ at $a_{1},a_{2},\ldots,a_{t-1}$. This assumption is without loss of generality, since any random learners can be seen as a randomization over deterministic learning algorithms. Thus a lower bound which holds uniformly for any deterministic learner would also hold over a randomization. To lower bound (9), we use Lemma 11, which relates this to the question of how informative are the query values (as measured by Kullback-Leibler divergence) for determining the sign of $\theta$’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 $\theta_{i}$, leading to a larger lower bound. In addition, we are facing a powerful adversary who has the complete knowledge of the problem and is able to add corruption on the query value to make they are even more similar, which resulting a even smaller KL divergence, consequently, an even larger lower bound.
Let $\bar{a}_{T}:=\frac{1}{T}\sum^{T}_{t=1}a_{t}$ represent the average action, we have

$$ $\displaystyle\mathbb{E}\left\{\sum^{T}_{t=1}\mu_{\theta}(a^{*})-\mu_{\theta}(a _{t})\right\}$ $\displaystyle=T\mathbb{E}\left\{\frac{1}{T}\sum^{T}_{t=1}\mu_{\theta}(a^{*})- \mu_{\theta}(a_{t})\right\}$ $\displaystyle\geq T\mathbb{E}\left(\mu_{\theta}(a^{*})-\mu_{\theta}(\bar{a}_{T })\right)$ $\displaystyle\geq T\mathbb{E}\left(\frac{1}{2}\|\bar{a}_{T}-\theta\|^{2}\right)$ $\displaystyle=T\mathbb{E}\left(\frac{1}{2}\sum^{d}_{i=1}(\bar{a}_{i}-\theta_{i })^{2}\right)$ $\displaystyle\geq\mathbb{E}\left(\frac{\beta^{2}T}{2}\sum^{d}_{i=1}\mathbb{I}_ {\bar{a}_{i}\theta_{i}<0}\right)$ (9) $\displaystyle\geq\frac{dT\beta^{2}}{4}\left(1-\sqrt{\frac{1}{d}\sum^{d}_{i=1} \sum^{T}_{t=1}\mathbb{D}_{t,i}}\right).$ $$

We get the second inequality by using the fact that $\mu_{\theta}$ is 1-strongly concave. We get the last inequality by using Lemma 11, which completes the proof.

###### Lemma 11 (Lemma 4 in (Shamir, 2013 ) ) .

Let $\theta$ be a random vector, none of those coordinates is supported on 0 0. Let $\hat{v}_{1},\hat{v}_{2},\ldots,\hat{v}_{T}$ be a sequence of values obtained by a deterministic learner returning a point $\bar{a}_{T}$ (so that the action $a_{t}$ is a deterministic function of $\hat{v}_{1},\ldots,\hat{v}_{t-1}$ and $\bar{a}_{T}$ is a deterministic function of $\hat{v}_{1},\ldots,\hat{v}_{T}$). Then we have

$$ $\displaystyle\mathbb{E}\left(\sum^{d}_{i=1}\mathbb{I}_{\bar{a}_{i}\theta_{i}} \right)\geq\frac{d}{2}\left(1-\sqrt{\frac{1}{d}\sum^{d}_{i=1}\sum^{T}_{t=1} \mathbb{D}_{t,i}}\right),$ $$

where $\mathbb{D}_{t,i}=\sup_{\{\theta_{j}\}_{j\neq i}}\text{D}_{\text{KL}}\left(
\mathbb{P}(\hat{v}_{t}|\theta_{i}>0,\{\theta_{j}\}_{j\neq i},\{\hat{v}_{l}\}^{
t-l}_{l=1})||\mathbb{P}(\hat{v}_{t}|\theta_{i}<0,\{\theta_{j}\}_{j\neq i},\{
\hat{v}_{l}\}^{t-l}_{l=1})\right)$, $\text{D}_{\text{KL}}$ represents the KL divergence between two distributions.

###### Lemma (Lemma 1 restated) .

###### Lemma 9 (KL Divergence for Normal Distribution) .

###### Lemma 10 .

###### Lemma 11 (Lemma 4 in (Shamir, 2013 ) ) .

### A.2 Proof for Proposition 1 :

###### Proposition (Proposition 1 restated) .

There exists an LIHF instance with $\rho$-Imperfect Human Feedback (Definition 1), linear user utility $\mu$, and link function $\sigma$, such that any learner has to suffer $\text{Reg}_{T}\geq\Omega(d\max\{\sqrt{T},T^{\rho}\})$, *even with the knowledge of $\rho$*.

Proof
The proof structure is very similar to the lower bound proof in Theorem 1. We start by discussing the value of $\rho$. Consider the scenario when $\rho\leq 0.5$. Applying Lemma 12 and 7 together with linear link function, we have $\text{Reg}_{T}\geq\Omega(d\max\{\sqrt{T},T^{\rho}\})$, which completes the proof.

###### Lemma 12 ( (Dani et al., 2008 ) ) .

Let $\mathcal{A}=[-1,1]^{d}$ and $\Theta=[-T^{-\frac{1}{2}},T^{-\frac{1}{2}}]^{d}$. Consider the linear reward function $r_{t}=\theta^{\top}A_{t}+\epsilon_{t}$, $\epsilon_{t}$ is independent standard Gaussian noise. Then for any learner, there exists a vector $\theta\in\Theta$ such that

$$ $\text{Reg}_{T}(\mathcal{A},\theta)\geq\frac{\exp(-2)}{8}d\sqrt{T}.$ $$

Now, let’s focus on the scenario when $\rho>0.5$ and the essence is to extend Lemma 12 to the scenario in presence of $\rho$-Imperfect Human Feedback, which is shown in Lemma 13

###### Lemma 13 .

Assume that the *action* space $\mathcal{A}\subset[-1,1]^{d}$. Given $\rho$-Imperfect Human Feedback (Definition 1), for stochastic linear bandit, there exists a $\theta\in[-C_{\kappa}T^{\rho-1},C_{\kappa}T^{\rho-1}]^{d}$ such that any learner even with the knowledge of $\rho$ has to suffer regret no less than $\frac{d}{8}C_{\kappa}T^{\rho}.$

Proof
The proof extends Lemma 12 to a scenario in presence of corruption. We want to construct a parameter family and a corruption strategy such that for all algorithm, it will occur at least $\Omega(dT^{\rho})$ regret. Consider the action set $\mathcal{A}\in[-1,1]^{d}$ and $\Theta=\{-\beta,\beta\}^{d}$. For any learner, we can lower bound its regret by

$$ $\displaystyle\text{Reg}_{T}(\mathcal{A},\theta)$ $\displaystyle=\mathbb{E}_{\theta}\left[\sum^{T}_{t=1}\sum^{d}_{i=1}(\text{sign }(\theta_{i})-a_{ti})\theta_{i}\right]$ $\displaystyle\geq\beta\sum^{d}_{i=1}\mathbb{E}_{\theta}\left[\sum^{T}_{t=1} \mathbb{I}\{\text{sign}(a_{ti})\neq\text{sign}(\theta_{i})\}\right]$ $\displaystyle\geq\frac{T\beta}{2}\sum^{d}_{i=1}\mathbb{P}_{\theta}\left(\sum^{ T}_{t=1}\mathbb{I}\{\text{sign}(a_{ti})\neq\text{sign}(\theta_{i})\}\geq\frac{ T}{2}\right)$ $$

Let’s denote

$$ $p_{\theta_{i}}=\mathbb{P}_{\theta}\left(\sum^{T}_{t=1}\mathbb{I}\{\text{sign}( a_{ti})\neq\text{sign}(\theta_{i})\}\geq\frac{T}{2}\right)$ $$

Let $i\in[d]$ and $\theta\in\Theta$ be fixed, and let $\theta^{\prime}_{j}=\theta_{j}$, for $j\neq i$ and $\theta^{\prime}_{i}=-\theta_{i}$. Then using Lemma 14, we have

$$ $p_{\theta_{i}}+p_{\theta^{\prime}_{i}}\geq\frac{1}{2}\exp\left(-\mathbb{E} \left[\sum^{T}_{t=1}\text{D}_{\text{KL}}(P_{a_{t}},P^{\prime}_{a_{t}})\right] \right).$ $$

$P_{a_{t}}$ is the distribution of corrupted reward observed by the learner after playing action $a_{t}$ when reward parameter is $\theta$. Similarly, $P^{\prime}_{a_{t}}$ is the distribution of corrupted observed by the learner after playing action $a_{t}$ when the reward parameter is $\theta^{\prime}$.

###### Lemma 14 (Bretagnolle-Huber inequality) .

Let $\mathbb{P}$ and $\mathbb{Q}$ be probability measures on the same measurable space $(\Omega,\mathcal{F})$. Let $A\in\mathcal{F}$ be any arbitrary event and $A^{c}$ is the complement of $A$. Then we have

$$ $\mathbb{P}(A)+\mathbb{Q}(A^{c})\geq\frac{1}{2}\exp\left(-D_{\text{KL}}(\mathbb {P},\mathbb{Q})\right).$ (10) $$

In presence of adversarial corruption, for $\theta$, the corrupted reward is

$$ $\hat{r}_{t}=\sum_{j\neq i}a_{tj}\theta_{j}+a_{ti}\theta_{i}+c_{t}(a_{t}|\theta )+\epsilon_{t}.$ (11) $$

For $\theta^{\prime}$, we have

$$ $\hat{r}_{t}=\sum_{j\neq i}a_{tj}\theta_{j}-a_{ti}\theta_{i}+c_{t}(a_{t}|\theta ^{\prime})+\epsilon_{t}.$ (12) $$

Consider the corruption strategy such that $c_{t}(a_{t}|\theta)=-a_{t,i}\theta_{i}$ in (11) and $c_{t}(a_{t}|\theta^{\prime})=a_{t,i}\theta_{i}$ in (12). This is achievable since we assume the adversary has complete knowledge of the problem instance. By doing so, the corrupted reward $\hat{r}_{t}$ are from the same distribution regardless whether the preference parameter is $\theta$ or $\theta^{\prime}$. This is because $\theta$ and $\theta^{\prime}$ only differs in the $i$-th coordinate with the magnitude $\beta$, and this difference could be masked by the corruption, resulting in $\mathbb{E}\left[\sum^{T}_{t=1}D_{\text{KL}}(P_{a_{t}},P^{\prime}_{a_{t}})
\right]=0$, which makes it indistinguishable by the learner. Notice that executing such a corruption strategy requires total corruption budget

$$ $\sum^{T}_{t=1}|c_{t}(a_{t})|\leq\beta\sum^{T}_{t=1}\|a_{t}\|_{\infty}\leq C_{ \kappa}T^{\rho}.$ (13) $$

Choose $\beta=C_{\kappa}T^{\rho-1}$, Equation (13) holds. Therefore, we have

$$ $p_{\theta_{i}}+p_{\theta^{\prime}_{i}}\geq\frac{1}{2}.$ $$

Applying an ”averaging hammer” over all $\theta\in\Theta$, which satisfies $|\Theta|=2^{d}$, we get

$$ $\sum_{\theta\in\Theta}\frac{1}{|\Theta|}\sum^{d}_{i=1}p_{\theta_{i}}=\frac{1}{ |\Theta|}\sum^{d}_{i=1}\sum_{\theta\in\Theta}p_{\theta_{i}}\geq\frac{d}{4}.$ $$

This implies that there exists a $\theta\in\Theta$ such that $\sum^{d}_{i=1}p_{\theta_{i}}\geq\frac{d}{4}$. Therefore we have

$$ $\text{Reg}_{T}(\mathcal{A},\theta)\geq\frac{dC_{\kappa}}{8}T^{\rho},$ $$

which completes the proof. We want to highlight that the corruption level each round $|c_{t}(a_{t})|$ is bounded by
$\beta\|a_{t}\|_{\infty}\leq C_{\kappa}T^{\rho-1}\leq C_{\kappa}t^{\rho-1},\forall
t$,
satisfying definition of $\rho$-Imperfect Human Feedback.

###### Proposition (Proposition 1 restated) .

###### Lemma 12 ( (Dani et al., 2008 ) ) .

###### Lemma 13 .

###### Lemma 14 (Bretagnolle-Huber inequality) .

## B Proof for Theorem 2

###### Theorem (Theorem 2 restated) .

RoSMID satisfies $\text{Reg}_{T}\leq\tilde{\mathcal{O}}(d\max\{\sqrt{T},T^{\rho}\})$ for any $\rho$-LIHF problem.

Proof
At the beginning of the proof, we formally define self-concordance (see Definition 2). The input, $\nu$-self-concordant function $\mathcal{R}$, serves as a regularizor in RoSMID (see Algorithm 1).

###### Definition 2 .

(Self-concordance.)
A function $\mathcal{R}:\text{int}(\mathcal{A})\rightarrow\mathbb{R}$ is self-concordant if it satisfies

- 1.
$\mathcal{R}$ is three times continuously differentiable, convex, and approaches infinity along any sequence of points approaching the boundary of $\text{int}(\mathcal{A})$.
- 2.
For every $h\in\mathbb{R}^{d}$ and $x\in\text{int}(\mathcal{A})$, $|\nabla^{3}\mathcal{R}(x)[h,h,h]|\leq 2\left(h^{\top}\nabla^{2}\mathcal{R}(x)h
\right)^{\frac{3}{2}}$ holds, where $|\nabla^{3}\mathcal{R}(x)[h,h,h]:=\frac{\partial^{3}\mathcal{R}}{\partial t_{1
}\partial t_{2}\partial t_{3}}(x+t_{1}h+t_{2}h+t_{3}h)|_{t_{1}=t_{2}=t_{3}=0}.$

In addition to these two conditions, if for every $h\in\mathbb{R}^{d}$ and $x\in\text{int}(\mathcal{A})$, $|\nabla\mathcal{R}(x)^{\top}h\leq\nu^{\frac{1}{2}}(h^{\top}\nabla^{2}\mathcal{
R}(x)h)^{\frac{1}{2}}|$ for a positive real number $\nu$, $\mathcal{R}$ is $\nu$-self-concordant.

Additionally, we remind the reader of the standard assumptions (Yue and Joachims, ; Kumagai, ) used in our analysis.

- 1.
the action set $\mathcal{A}$ is a convex compact set that contains the origin, has non-empty interior, and is contained in a $d$-dimensional ball of radius $R$;
- 2.
the utility function $\mu:\mathcal{A}\rightarrow\mathbb{R}$ is strongly concave and twice-differentiable. The following constants are useful for our algorithm analysis: $\mu$ is $L^{\mu}$-Lipschitz, $\alpha$-strongly concave, $\kappa$-smooth, bounded $R^{\mu}:=\sup_{a,a^{\prime}}\mu(a)-\mu(a^{\prime})$, and
$a^{*}:=\arg\max_{a\in\mathcal{A}}\mu(a)$ is the unique optimal within $\mathcal{A}$;
- 3.
the link function $\sigma:\mathbb{R}\rightarrow[0,1]$ is smooth, rotation-symmetric (i.e. $\sigma(x)=1-\sigma(-x)$), and concave for any $x\geq 0$. For the ease of analysis: let $l^{\sigma}_{1}$ [resp. $L^{\sigma}_{1}$] denote the lower [resp. upper] bound of the first-order derivative of $\sigma$. $\sigma$ is $L^{\sigma}$-Lipschitz and its second-order derivative $\sigma^{\prime\prime}$ is $L^{\sigma}_{2}$-Lipschitz and upper bounded by $R^{\sigma}_{2}$.

Under these assumption, Lemma 15 implies $\text{Reg}_{T}$ defined in (1) and $\text{Reg}^{\text{FO}}_{T}$ defined in (3) has the same order.

###### Lemma 15 (Lemma 12 in Kumagai ( 2017 ) ) .

With $\text{Reg}^{\text{FO}}_{T}$ defined in (3), we have

$$ $\frac{\text{Reg}_{T}}{L^{\sigma}_{1}}\leq\text{Reg}^{\text{FO}}_{T}\leq\frac{ \text{Reg}_{T}}{l^{\sigma}_{1}}.$ (14) $$

In the following, we show the proof. The main proof can be divided into four key steps. Step 1 is natural, which quantifies the bias in gradient estimation by RoSMID due imperfect feedback from corrupted utilities. Building on this, Step 2 develops a 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 to bound the regret from feedback error, a 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 $\rho$-imperfect human feedback, uses this assumption, along with the carefully chosen learning rate $\eta_{\rho}$ 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 $\rho$-LIHF

Our proof starts from quantifying the bias of the gradient $\hat{g}_{t}$ caused by $\rho$-imperfect human feedback, as shown in the following Lemma 2.

###### Lemma (Lemma 2 restated) .

The gradient $\hat{g}_{t}$ in Line 6 of Algorithm 1 satisfies

$$ $\mathbb{E}\left(\hat{g}_{t}|a_{t}\right)=\nabla|_{a=a_{t}}\bar{P}_{t}(a)- \mathbb{E}\left(b_{t}|a_{t}\right).$ $$

where $\bar{P}_{t}(a):=\mathbb{E}_{x\in\mathbb{B}}\left[\mathbb{P}(a_{t}\succ a+
\nabla^{2}R_{t}(a_{t})^{-\frac{1}{2}}x)\right]$ (with $\mathbb{B}$ as the unit ball) is the smoothed probability that $a_{t}$ is preferred over any action $a$, and $b_{t}=d\left(\mathbb{P}(a_{t}\succ a^{\prime}_{t})-\hat{\mathbb{P}}(a_{t}\succ
a
^{\prime}_{t})\right)\nabla^{2}\mathcal{R}_{t}(a_{t})^{\frac{1}{2}}u_{t}$.

Proof
If we do not have corruption (i.e. the probability for observing noisy comparative feedback $\mathcal{F}(a,a^{\prime})=1$ is based on true cost difference $\mu(a)-\mu(a^{\prime})$), then the uncorrupted gradient $g_{t}:=\mathcal{F}(a^{\prime}_{t},a_{t})d\nabla^{2}\mathcal{R}_{t}(a_{t})^{1/2
}u_{t}$ should be an unbiased estimate of $\nabla\bar{P}_{t}(a_{t})$, i.e.

$$ $\mathbb{E}(g_{t}|a_{t})=\nabla\bar{P}_{t}(a_{t}).$ $$

We use $\nabla\bar{P}_{t}(a_{t})$ as a shorthand of $\nabla|_{a=a_{t}}\bar{P}_{t}(a)$. We use $P_{t}(a)$ as a shorthand of $P_{t}(a):=\sigma(\mu(a_{t})-\mu(a))$ equivalent to $\mathbb{P}(a_{t}\succ a)$, and $\hat{P}_{t}(a):=\sigma(\mu(a_{t})-\mu(a)+c_{t}(a_{t},a^{\prime}_{t}))$, equivalent to $\hat{\mathbb{P}}(a_{t}\succ a)$ under our modelling assumption.
The proof is similar to Lemma 2.1 in Flaxman et al. (). Using the Law of total expectation, we have

$$ $\displaystyle\mathbb{E}(g_{t}|a_{t})$ $\displaystyle=\mathbb{E}_{u_{t}}[\mathbb{E}(g_{t}|a_{t},u_{t})]$ $\displaystyle=\mathbb{E}_{u_{t}}\left(d\mathbb{E}(P_{t}(a_{t}+\nabla^{2} \mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}u_{t})\nabla^{2}\mathcal{R}_{t}(a_{t})^{ \frac{1}{2}}u_{t}|a_{t},u_{t})\right)$ $\displaystyle=d\mathbb{E}(P_{t}(a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac {1}{2}}u_{t})\nabla^{2}\mathcal{R}_{t}(a_{t})^{\frac{1}{2}}u_{t}|a_{t})$ $\displaystyle=\nabla\mathbb{E}_{x\in\mathbb{B}}\left(P_{t}(a_{t}+\nabla^{2} \mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}x|a_{t})\right)$ $\displaystyle=\nabla\bar{P}_{t}(a_{t}).$ $$

We get the second inequality by using the definition of $\mathcal{F}(a^{\prime}_{t},a_{t})$. We use the Stroke’s Theorem to get the second last equality. The gradient which we get to perform gradient descent $\hat{g}_{t}$ is corrupted. If we let $a^{\prime}_{t}=a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}u_{t}$, we have

$$ $\displaystyle\mathbb{E}(\hat{g}_{t}|a_{t})$ $\displaystyle=\mathbb{E}_{u_{t}}(\mathbb{E}(\hat{g}_{t}|a_{t},u_{t}))$ $\displaystyle=\mathbb{E}_{u_{t}}\left(d\mathbb{E}(\hat{P}_{t}(a^{\prime}_{t}) \nabla^{2}\mathcal{R}_{t}(a_{t})^{\frac{1}{2}}u_{t}|a_{t},u_{t})\right)$ $\displaystyle=d\mathbb{E}\left(\hat{P}_{t}(a^{\prime}_{t})\nabla^{2}\mathcal{R }_{t}(a_{t})^{\frac{1}{2}}u_{t}|a_{t}\right)$ $\displaystyle=d\mathbb{E}\left(\left[P_{t}(a^{\prime}_{t})+\hat{P}_{t}(a^{ \prime}_{t})-P_{t}(a^{\prime}_{t})\right]\nabla^{2}R_{t}(a_{t})^{\frac{1}{2}}u _{t}|a_{t}\right)$ $\displaystyle=\nabla\mathbb{E}_{x\in\mathbb{B}}\left(P_{t}(a_{t}+\nabla^{2} \mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}x|a_{t})\right)+d\mathbb{E}\left[\left( \hat{P}_{t}(a^{\prime}_{t})-P_{t}(a^{\prime}_{t})\right)\nabla^{2}\mathcal{R}_ {t}(a_{t})^{\frac{1}{2}}u_{t}|a_{t}\right]$ $\displaystyle=\nabla\bar{P}_{t}(a_{t})+d\mathbb{E}\left[\left(\hat{P}_{t}(a^{ \prime}_{t})-P_{t}(a^{\prime}_{t})\right)\nabla^{2}\mathcal{R}_{t}(a_{t})^{ \frac{1}{2}}u_{t}|a_{t}\right]$ $\displaystyle=\mathbb{E}(g_{t}|a_{t})+d\mathbb{E}\left[\left(\hat{P}_{t}(a^{ \prime}_{t})-P_{t}(a^{\prime}_{t})\right)\nabla^{2}\mathcal{R}_{t}(a_{t})^{ \frac{1}{2}}u_{t}|a_{t}\right].$ $$

We get the second last equality by using the fact that $g_{t}$ is unbiased, which we proved earlier. If we defined $b_{t}$ as

$$ $b_{t}:=d\left(P_{t}(a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}u_{t} )-\hat{P}_{t}(a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}u_{t}) \right)\nabla^{2}\mathcal{R}_{t}(a_{t})^{\frac{1}{2}}u_{t},$ $$

we get

$$ $\mathbb{E}(g_{t}|a_{t})=\mathbb{E}(\hat{g}_{t}|a_{t})+\mathbb{E}\left[b_{t}|a_ {t}\right].$ $$

Step 2: decomposing regret for dueling bandits into regret of decision and feedback error

Core to our proof is 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 (2)), and feedback error (second term in (2)).

###### Lemma (Lemma 3 restated) .

The $\text{Reg}_{T}$ of Algorithm 1 satisfies:

$$ $\text{Reg}_{T}\leq\underbrace{\frac{C_{0}}{\eta_{\rho}}\log(T)+8d^{2}\eta_{ \rho}T+2L^{\mu}L^{\sigma}_{1}R}_{{\color[rgb]{1,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{1,0,0}Regret\hskip 2.84526ptof\hskip 2.84526ptDecision}}+ \underbrace{2\mathbb{E}\left\{\sum^{T}_{t=1}b^{\top}_{t}(a_{t}-a^{*}_{T}) \right\}}_{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0} Feedback\hskip 2.84526ptError}},$ $$

where $C_{0}:=(2\nu+4L^{\sigma}_{1}\kappa+4R^{\sigma}_{2}(L^{\mu})^{2}+L^{\mu}L^{
\sigma}_{1}\kappa)/\lambda$, and $a^{*}_{T}:=\frac{1}{T}a_{1}+(1-\frac{1}{T})a^{*}$.

Proof
The cornerstone of the analysis below is to separate the impact of $b_{t}$ from the total regret.

$$ $\displaystyle\text{Reg}_{T}\leq 2\mathbb{E}\left[\sum^{T}_{t=1}(P_{t}(a_{t})-P _{t}(a^{*}_{T})\right]+\frac{L^{\mu}L^{\sigma}_{1}\kappa}{\lambda\eta_{\rho}}+ 2L^{\mu}L^{\sigma}_{1}R$ $\displaystyle\leq 2\left(\mathbb{E}\left\{\sum^{T}_{t=1}(\bar{P}_{t}(a_{t})- \bar{P}_{t}(a^{*}_{T}))\right\}+\mathbb{E}\left\{\sum^{T}_{t=1}(P_{t}(a_{t})- \bar{P}_{t}(a_{t}))\right\}+\mathbb{E}\left\{\sum^{T}_{t=1}(\bar{P}_{t}(a^{*}_ {T})-P_{t}(a^{*}_{T}))\right\}\right)$ $\displaystyle+\frac{L^{\mu}L^{\sigma}_{1}\kappa}{\lambda\eta_{\rho}}+2L^{\mu}L ^{\sigma}_{1}R$ $\displaystyle\leq 2\mathbb{E}\left\{\sum^{T}_{t=1}(\bar{P}_{t}(a_{t})-\bar{P}_ {t}(a^{*}_{T}))\right\}+\frac{4L^{\sigma}_{1}\kappa+4R^{\sigma}_{2}(L^{\mu})^{ 2}+L^{\mu}L^{\sigma}_{1}\kappa}{\lambda\eta_{\rho}}\log T+2L^{\mu}L^{\sigma}_{ 1}R.$ $$

We get the first inequality by using Lemma 16. We get the last inequality by because

$$ $\bar{P}_{t}(a)-P_{t}(a)\leq\frac{L^{\sigma}_{1}\kappa+R^{\sigma}_{2}(L^{\mu})^ {2}}{2}\|\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}u_{t}\|^{2}\leq\frac{L ^{\sigma}_{1}\kappa+R^{\sigma}_{2}(L^{\mu})^{2}}{\lambda\eta_{\rho}t},$ $$

and

$$ $\displaystyle\mathbb{E}\left\{\sum^{T}_{t=1}(P_{t}(a_{t})-P_{t}(a^{*}_{T}))\right\}$ $\displaystyle\leq\mathbb{E}\left\{\sum^{T}_{t=1}(\bar{P}_{t}(a_{t})-\bar{P}_{t }(a^{*}_{T}))\right\}+2\frac{L^{\sigma}_{1}\kappa+R^{\sigma}_{2}(L^{\mu})^{2}} {\lambda\eta_{\rho}}\log T.$ $$

###### Lemma 16 (Lemma 5 in Kumagai ( 2017 ) ) .

$$ $\text{Reg}_{T}\leq 2\mathbb{E}\left[\sum^{T}_{t=1}(P_{t}(a_{t})-P_{t}(a^{*}_{T })\right]+\frac{L^{\mu}L^{\sigma}_{1}\kappa}{\lambda\eta_{\rho}}+2L^{\mu}L^{ \sigma}_{1}R.$ $$

Then it remains to bound $\mathbb{E}\{\sum^{T}_{t=1}\bar{P}_{t}(a_{t})-\bar{P}_{t}(a^{*}_{T})\}$. And we have the following.

$$ $\displaystyle\mathbb{E}\{\bar{P}_{t}(a_{t})-\bar{P}_{t}(a^{*}_{T})\}$ $\displaystyle\leq\mathbb{E}\left[\nabla\hat{P}^{\top}_{t}(a_{t})(a_{t}-a^{*}_{ T})-\frac{L^{\sigma}_{1}\alpha}{4}\|a_{t}-a^{*}_{T}\|^{2}\right]$ $\displaystyle=\mathbb{E}\left[g_{t}^{\top}(a_{t}-a^{*}_{T})-\frac{L^{\sigma}_{ 1}\alpha}{4}\|a_{t}-a^{*}_{T}\|^{2}\right]$ $\displaystyle=\mathbb{E}\left[(\hat{g}_{t}+b_{t})^{\top}(a_{t}-a^{*}_{T})- \frac{L^{\sigma}_{1}\alpha}{4}\|a_{t}-a^{*}_{T}\|^{2}\right]$ $\displaystyle=\mathbb{E}\left[\hat{g}_{t}^{\top}(a_{t}-a^{*}_{T})-\frac{L^{ \sigma}_{1}\alpha}{4}\|a_{t}-a^{*}_{T}\|^{2}\right]+\mathbb{E}\{b^{\top}_{t}(a _{t}-a^{*}_{T})\},$ $$

where the first and second equality is resulted from Lemma 2. Using the definition of $a_{t+1}$ in Algorithm 1, we have

$$ $\nabla\mathcal{R}_{t}(a_{t+1})-\nabla\mathcal{R}_{t}(a_{t})=\eta_{\rho}\hat{g} _{t}.$ $$

Therefore we have

$$ $\displaystyle\mathbb{E}\left[\hat{g}_{t}^{\top}(a_{t}-a^{*}_{T})-\frac{L^{ \sigma}_{1}\alpha}{4}\|a_{t}-a^{*}_{T}\|^{2}\right]$ $\displaystyle=\frac{1}{\eta_{\rho}}\mathbb{E}\left[(\nabla\mathcal{R}_{t}(a_{t +1})-\nabla\mathcal{R}_{t}(a_{t}))^{\top}(a_{t}-a^{*}_{T})-\frac{L^{\sigma}_{1 }\alpha\eta_{\rho}}{4}\|a_{t}-a^{*}_{T}\|^{2}\right]$ $\displaystyle=\frac{1}{\eta_{\rho}}\mathbb{E}\left[D_{\mathcal{R}_{t}}(a^{*}_{ T},a_{t})+D_{\mathcal{R}}(a_{t},a_{t+1})-D_{\mathcal{R}_{t}}(a^{*}_{T},a_{t+1} )-\frac{L^{\sigma}_{1}\alpha\eta_{\rho}}{4}\|a_{t}-a^{*}_{T}\|^{2}\right].$ $$

$D_{\mathcal{R}}(a,b)$ is the Bregman divergence associated with $\mathcal{R}$, defined by

$$ $D_{\mathcal{R}}(a,b)=\mathcal{R}(a)-\mathcal{R}(b)-\nabla\mathcal{R}(b)^{\top} (a-b).$ $$

Then we can get (15) by using Lemma 17, 18, 19.

$$ $\displaystyle\mathbb{E}\left\{\sum^{T}_{t=1}(\bar{P}_{t}(a_{t})-\bar{P}_{t}(a^ {*}_{T}))\right\}\leq\frac{\nu\log(T)}{\eta_{\rho}}+4d^{2}\eta_{\rho}T+\mathbb {E}\{\sum^{T}_{t=1}b_{t}^{\top}(a_{t}-a^{*}_{T})\}.$ (15) $$

###### Lemma 17 (Lemma 10 in Kumagai ( 2017 ) ) .

Let $\mathcal{R}^{*}_{t}(a)=\sup_{x\in\mathbb{R}^{d}}x^{\top}a-\mathcal{R}_{t}(a)$ denote the Frenchel dual of $\mathcal{R}_{t}$. Then we have

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E}\left[\hat{g}_{t}^{\top}(a_{t}-a^{*}_{T}) -\frac{L^{\sigma}_{1}\alpha}{4}\|a_{t}-a^{*}_{T}\|^{2}\right]\leq\frac{1}{\eta _{\rho}}\left(\mathcal{R}(a^{*}_{T})-\mathcal{R}(a_{1})+\mathbb{E}\left[\sum^{ T}_{t=1}D_{\mathcal{R}^{*}_{t}}(\nabla\mathcal{R}_{t}(a_{t})-\eta_{\rho}\hat{g }_{t},\nabla\mathcal{R}_{t}(a_{t}))\right]\right).$ $$

###### Lemma 18 (Lemma 11 in Kumagai ( 2017 ) ) .

When $\eta_{\rho}\leq\frac{1}{2d}$, we have

$$ $D_{\mathcal{R}^{*}_{t}}(\nabla\mathcal{R}_{t}(a_{t})-\eta_{\rho}\hat{g}_{t}, \nabla\mathcal{R}_{t}(a_{t}))\leq 4d^{2}\eta^{2}_{\rho}.$ $$

###### Lemma 19 (Lemma 4 in Hazan and Levy ( 2014 ) ) .

$\mathcal{R}(a^{*}_{T})-\mathcal{R}(a_{1})\leq\nu\log(T).$

If we let $C_{0}:=(2\nu+4L^{\sigma}_{1}\kappa+4R^{\sigma}_{2}(L^{\mu})^{2}+L^{\mu}L^{
\sigma}_{1}\kappa)/\lambda$, we have

$$ $\displaystyle\text{Reg}_{T}$ $\displaystyle\leq\frac{2\nu\log(T)}{\eta_{\rho}}+8d^{2}\eta_{\rho}T+2\mathbb{E }\left\{\sum^{T}_{t=1}b_{t}^{\top}(a_{t}-a^{*}_{T})\right\}+\frac{4L^{\sigma}_ {1}\kappa+4R^{\sigma}_{2}(L^{\mu})^{2}+L^{\mu}L^{\sigma}_{1}\kappa}{\lambda \eta_{\rho}}\log T+2L^{\mu}L^{\sigma}_{1}R$ $\displaystyle=\underbrace{\frac{C_{0}}{\eta_{\rho}}\log(T)+8d^{2}\eta_{\rho}T+ 2L^{\mu}L^{\sigma}_{1}R}_{{\color[rgb]{1,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{1,0,0}Regret\hskip 2.84526ptof\hskip 2.84526ptDecision}}+ \underbrace{2\mathbb{E}\left\{\sum^{T}_{t=1}b^{\top}_{t}(a_{t}-a^{*}_{T}) \right\}}_{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0} Feedback\hskip 2.84526ptError}},$ $$

which completes the proof.

Step 3: upper bounding the regret from feedback error

Bounding the regret of decision term in (2) is standard. Thus, this step develops a novel upper bound for bounding the regret from feedback error, as shown below.

###### Lemma (Lemma 4 restated) .

The feedback error term in (2) can be bounded as follows:

$$ $\displaystyle\mathbb{E}\left\{\sum^{T}_{t=1}b^{\top}_{t}(a_{t}-a^{*}_{T})\right\}$ $\displaystyle\leq C_{1}d\sqrt{\eta_{\rho}}\mathbb{E}\left\{\sum^{T}_{t=1}\sqrt {t}|c_{t}(a_{t},a^{\prime}_{t})|\sqrt{\mu(a^{*})-\mu(a_{t})}\right\}+C_{2}dT^{ \rho}+2d\sqrt{\lambda}\sqrt{\eta_{\rho}T},$ $$

where $C_{1}:=\sqrt{\frac{2\lambda(L^{\sigma})^{2}}{\alpha}}$, and $C_{2}:=2L^{\sigma}R\sqrt{\sup_{a\in\mathcal{A}}\lambda_{\max}\left(\nabla^{2}
\mathcal{R}(a)\right)+2\phi}$.

Proof
In the following, we will analyze the expected cumulative sum of the bias $b_{t}$ on the total regret, which is $\mathbb{E}\left\{\sum^{T}_{t=1}b^{\top}_{t}(a_{t}-a^{*}_{T})\right\}$. By Cauchy-Schwartz inequality, $b^{\top}_{t}(a_{t}-a^{*}_{T})\leq\|b_{t}\|_{2}\|(a_{t}-a^{*}_{T})\|_{2}$. We can bound the $\|b_{t}\|_{2}$ by the following.

$$ $\displaystyle b^{\top}_{t}b_{t}$ $\displaystyle=d^{2}\left(P_{t}(a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{ 1}{2}}u_{t})-\hat{P}_{t}(a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1}{2}} u_{t})\right)^{2}u^{\top}_{t}\nabla^{2}\mathcal{R}_{t}(a_{t})u_{t}$ $\displaystyle\leq\left(P_{t}(a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1} {2}}u_{t})-\hat{P}_{t}(a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}u_ {t})\right)^{2}d^{2}\lambda_{\max}(\nabla^{2}\mathcal{R}_{t}(a_{t})).$ $$

We get the first equality by Lemma 2. We get the inequality by using the fact $\|u_{t}\|_{2}=1$. If we let $a^{\prime}_{t}=a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}u_{t}$, then we have

$$ $\displaystyle|P_{t}(a^{\prime}_{t})-\hat{P}_{t}(a^{\prime}_{t})|$ $\displaystyle=|\sigma(f(a_{t})-f(a^{\prime}_{t}))-\sigma(f(a_{t})-f(a^{\prime} _{t})+c_{t}(a_{t},a^{\prime}_{t}))|$ $\displaystyle\leq\min\left(2,L^{\sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right).$ $$

We get the first equality by using the definition of $P_{t}(a_{t})$ and $\hat{P}_{t}(a_{t})$. We get the first inequality by using the Lipschitz property of $\sigma$.
Therefore, we have

$$ $\|b_{t}\|_{2}\leq d\sqrt{\lambda_{\max}(\nabla^{2}\mathcal{R}_{t}(a_{t}))}\min \left\{2,L^{\sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right\}.$ $$

If we use $\lambda^{*}_{R}:=\sup_{a\in\mathcal{A}}\lambda_{\max}\left(\nabla^{2}\mathcal{
R}(a)\right)$, then we have

$$ $\displaystyle\lambda_{\max}(\nabla^{2}\mathcal{R}_{t}(a_{t}))$ $\displaystyle=\lambda_{\max}(\nabla^{2}\mathcal{R}(a_{t}))+\lambda\eta_{\rho}t +2\phi\leq\lambda^{*}_{R}+2\phi+\lambda\eta_{\rho}t.$ $$

Therefore we have

$$ $\displaystyle\mathbb{E}\left\{\sum^{T}_{t=1}b^{\top}_{t}(a_{t}-a^{*}_{T}) \right\}\leq\mathbb{E}\left\{\sum^{T}_{t=1}\|b_{t}\|_{2}\|a_{t}-a^{*}_{T}\|_{2 }\right\}$ $\displaystyle\leq\mathbb{E}\left\{\sum^{T}_{t=1}(d\sqrt{\lambda_{\max}(\nabla^ {2}\mathcal{R}_{t}(a_{t}))}\min\left(2,L^{\sigma}|c_{t}(a_{t},a^{\prime}_{t})| \right))\|a_{t}-a^{*}_{T}\|_{2}\right\}$ $\displaystyle\leq\mathbb{E}\left\{\sum^{T}_{t=1}(d\sqrt{\lambda^{*}_{R}+2\phi+ \lambda\eta_{\rho}t}\min\left(2,L^{\sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right) )\|a_{t}-a^{*}_{T}\|_{2}\right\}$ $\displaystyle\leq\mathbb{E}\left\{\sum^{T}_{t=1}(d\sqrt{\lambda^{*}_{R}+2\phi} \min\left(2,L^{\sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right)\|a_{t}-a^{*}_{T}\|_ {2}\right\}+\mathbb{E}\left\{\sum^{T}_{t=1}(d\sqrt{\lambda\eta_{\rho}t}\min \left(2,L^{\sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right)\|a_{t}-a^{*}_{T}\|_{2}\right\}$ $\displaystyle\leq 2RdL^{\sigma}\sqrt{\lambda^{*}_{R}+2\phi}T^{\rho}+d\sqrt{ \lambda\eta_{\rho}}\mathbb{E}\left\{\sum^{T}_{t=1}\sqrt{t}\min\left(2,L^{ \sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right)\|a_{t}-a^{*}_{T}\|_{2}\right\}$ (16) $\displaystyle\leq 2RdL^{\sigma}\sqrt{\lambda^{*}_{R}+2\phi}T^{\rho}+2d\sqrt{ \lambda\eta_{\rho}T}+d\sqrt{\lambda\eta_{\rho}}\mathbb{E}\left\{\sum^{T}_{t=1} \sqrt{t}\min\left(2,L^{\sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right)\|a_{t}-a^{* }\|_{2}\right\}$ (17) $\displaystyle\leq 2RdL^{\sigma}\sqrt{\lambda^{*}_{R}+2\phi}T^{\rho}+2d\sqrt{ \lambda\eta_{\rho}T}$ $\displaystyle+d\sqrt{\lambda\eta_{\rho}}\mathbb{E}\left\{\sum^{T}_{t=1}\sqrt{t }\min\left(2,L^{\sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right)\min\left(2R,\sqrt{ \frac{2}{\alpha}\left(\mu(a^{*})-\mu(a_{t})\right)}\right)\right\}.$ (18) $$

We get (16) by using the fact that $\|a_{t}-a^{*}_{T}\|_{2}\leq 2R$, $\sum^{T}_{t=1}|c_{t}(a_{t},a^{\prime}_{t})|\leq T^{\rho}$. We get (17) the definition of $a^{*}_{T}$, and the fact $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$. Using the $\alpha$-strong convexity of $\mu$, we have $\|a_{t}-a_{*}\|_{2}\leq\min\left(2R,\sqrt{\frac{2}{\alpha}\left(\mu(a^{*})-\mu
(a_{t})\right)}\right)$ we get the last inequality, which completes the proof.

Step 4: The *iterative regret refinement* analysis and resultant optimal learning rate

###### Lemma (Lemma 5 restated) .

If $A=\mathbb{E}\left(\sum^{T}_{t=1}[\mu(a^{*})-\mu(a_{t})]\right)\leq\mathcal{O}(
T^{\frac{1}{2}+\psi})$ for some $\psi\in[0,\frac{1}{2})$, then we must have $B=\mathbb{E}\left(\sum^{T}_{t=1}t^{\rho-\frac{1}{2}}\sqrt{\mu(a^{*})-\mu(a_{t}
)}\right)\leq\mathcal{O}(T^{-\frac{1}{4}+\frac{\psi}{2}+\rho})$.

Proof
To prove Lemma 5, it is equivalent to prove the following Lemma 20. If Lemma 20 holds, let $n_{t}=\sqrt{\mathbb{E}(\mu(a^{*})-\mu(a_{t}))}$, $m_{t}=\min\left(2,L^{\sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right)$, proves Lemma 5.

###### Lemma 20 .

Consider $\sum^{T}_{t=1}n^{2}_{t}\leq C^{\prime}T^{\frac{1}{2}+\alpha}$, with constants $\alpha\geq 0$, $C^{\prime}>0$. In addition, $n_{t}$ is uniformly upper bounded by a constant $K$. Specifically, we have $0\leq n_{t}\leq K,\forall t$. $m_{t}\leq c_{k}t^{\rho-1}$ with constant $c_{k}\geq 0$. Then we have $\sum^{T}_{t=1}\sqrt{t}m_{t}n_{t}\leq 5\sqrt{C^{\prime}}c_{k}T^{-\frac{1}{4}+
\frac{\alpha}{2}+\rho}$.

Proof

Using Abel’s equality (Lemma 21), we have

$$ $\sum^{T}_{t=1}\sqrt{t}m_{t}n_{t}\leq\sqrt{T}\left(\sum^{T}_{t=1}m_{t}n_{t}\right)$ $$

Since we have $\sum^{T}_{t=1}n^{2}_{t}\leq C^{\prime}T^{\frac{1}{2}+\alpha}$ and $0\leq n_{t}\leq K,\forall t$, we have $\sum^{T}_{t=1}n_{t}\leq\sqrt{C^{\prime}}T^{\frac{3}{4}+\frac{\alpha}{2}},\forall
t$. Moreover, for $t\geq 1$, $t^{-1+\rho}-(t+1)^{-1+\rho}\leq t^{\rho-2}$ holds for all $t\geq 1$. This is because

$$ $f(t)=t^{-1+\rho}\left((1+\frac{1}{t})^{-1+\rho}+\frac{1}{t}-1\right).$ $$

is decreasing over $t\geq 1$ and $\lim_{t\rightarrow\infty}f(t)=0$. Consequently, applying Abel’s Summation Equation again, we have

$$ $\displaystyle\sum^{T}_{t=1}m_{t}n_{t}$ $\displaystyle=\left(\sum^{T}_{t=1}n_{t}\right)m_{T}+\sum^{T-1}_{t=1}\left(\sum ^{t}_{i=1}n_{i}\right)(m_{t}-m_{t+1})$ $\displaystyle\leq\sqrt{C^{\prime}}c_{k}T^{\frac{3}{4}+\frac{\alpha}{2}}T^{-1+ \rho}+\sqrt{C^{\prime}}c_{k}\sum^{T-1}_{t=1}\left(\sum^{t}_{i=1}n_{i}\right) \left(t^{-1+\rho}-(t+1)^{-1+\rho}\right)$ $\displaystyle\leq\sqrt{C^{\prime}}c_{k}T^{\frac{3}{4}+\frac{\alpha}{2}}T^{-1+ \rho}+\sqrt{C^{\prime}}c_{k}\sum^{T-1}_{t=1}\left(\sum^{t}_{i=1}n_{i}\right)t^ {-2+\rho}$ $\displaystyle\leq\sqrt{C^{\prime}}c_{k}T^{\frac{3}{4}+\frac{\alpha}{2}}T^{-1+ \rho}+\sqrt{C^{\prime}}c_{k}\sum^{T-1}_{t=1}t^{\frac{3}{4}+\frac{\alpha}{2}}t^ {-2+\rho}$ $\displaystyle\leq 5\sqrt{C^{\prime}}c_{k}T^{-\frac{1}{4}+\frac{\alpha}{2}+\rho}.$ $$

Since $0\leq n_{t}\leq K$, $\sum^{t}_{i=1}n_{i}$ is increasing and the increasing rate is upper bound by $t$. Together with the constraint $\sum^{T}_{t=1}n_{t}\leq\sqrt{C^{\prime}}T^{\frac{3}{4}+\frac{\alpha}{2}}$, $\sum^{T-1}_{t=1}\left(\sum^{t}_{i=1}n_{i}\right)t^{-\frac{1}{2}+\rho}$ is optimized when $\sum^{t}_{i=1}n_{i}$ increasing in the speed of $\sqrt{C^{\prime}}t^{\frac{3}{4}+\frac{\alpha}{2}}$. Because of this, the second last inequality holds.

###### Lemma 21 .

(Abel’s Summation Equation (Williams, )). For any numbers $a_{k}$, $b_{k}$, we have

$$ $\sum^{n}_{k=1}a_{k}b_{k}=\left(\sum^{n}_{k=1}b_{k}\right)a_{n}+\sum^{n-1}_{k=1 }\left(\sum^{k}_{i=1}b_{i}\right)(a_{k}-a_{k+1}).$ $$

After establishing Lemma 5, we can use it to prove the induction claim (Lemma 6). The challenge in this proof lies in 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 6 restated) .

Consider $T>\sqrt{2L^{\mu}L^{\sigma}_{1}R}$ and $\eta_{\rho}=\frac{\sqrt{\log T}}{dT^{\max\{1/2,\rho\}}}$. If $\text{Reg}_{T}\leq 144dK\sqrt{\log T}T^{\rho+\frac{\frac{3}{2}-\rho}{2^{k}}}$ for some integer $k$, then we must also have $\text{Reg}_{T}\leq 144dK\sqrt{\log T}T^{\rho+\frac{\frac{3}{2}-\rho}{2^{k+1}}}$. $K$ is a instance-dependent constant, where $K:=\max\left\{C_{0},\frac{C_{2}C_{\kappa}}{\sqrt{\log T}},(L^{\sigma}T^{\rho}_
{\kappa})^{2},2\sqrt{\lambda}RC_{\kappa}L^{\sigma}\right\}$, $C_{0}$ and $C_{2}$ defined in Lemma 3 and 4 respectively,

Proof
In the following, we denote

$$ $m_{t}:=\min\left(2,L^{\sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right),n_{t}:=\min \left(2R,\sqrt{\frac{2}{\alpha}\left(\mu(a^{*})-\mu(a_{t})\right)}\right)$ $$

Continue from (18), we have the following.

The Base Case: When $k=1$, let $C_{3}=C_{2}dT^{\rho}+2d\sqrt{\lambda\eta_{\rho}T}$, we have

$$ $\displaystyle\text{Reg}_{T}$ $\displaystyle\leq\frac{C_{0}}{\eta_{\rho}}\log(T)+8d^{2}\eta_{\rho}T+2L^{\mu}L ^{\sigma}_{1}R+2C_{3}+2d\sqrt{\lambda\eta_{\rho}}\mathbb{E}\left(\sum^{T}_{t=1 }\sqrt{t}m_{t}n_{t}\right).$ (19) $\displaystyle\leq\frac{C_{0}}{\eta_{\rho}}\log(T)+8d^{2}\eta_{\rho}T+2L^{\mu}L ^{\sigma}_{1}R+2C_{3}+4dR\sqrt{\lambda\eta_{\rho}}\mathbb{E}\left\{\sum^{T}_{t =1}\sqrt{t}m_{t}\right\}$ (20) $\displaystyle\leq\frac{C_{0}}{\eta_{\rho}}\log(T)+8d^{2}\eta_{\rho}T+2L^{\mu}L ^{\sigma}_{1}R+2C_{3}+4dR\sqrt{\lambda\eta_{\rho}T}\left(\sum^{T}_{t=1}m_{t}\right)$ (21) $\displaystyle\leq\frac{C_{0}}{\eta_{\rho}}\log(T)+8d^{2}\eta_{\rho}T+2L^{\mu}L ^{\sigma}_{1}R+2C_{3}+4dL^{\sigma}R\sqrt{\lambda\eta_{\rho}}C_{\kappa}T^{\rho}.$ (22) $$

We get (19) according to Lemma 3 and 4. We get (20) because of $\mathbb{E}\left(n_{t}\right)\leq 2R$. We get (21) by Abel’s Summation Equation (see Lemma 21). We get (22) because of corruption budget. Choosing the learning rate $\eta_{\rho}$ according to Theorem 2, we obtain $\text{Reg}_{T}\leq 144\sqrt{\log T}KdT^{\frac{\rho+1}{2}}$. This confirms the validity of the claim when $k=1$.

The Induction Argument: Let’s assume that the claim holds true for a general step $k$. In the following, we will demonstrate that the claim also holds true for step $k+1$. Because of Equation (14) and the induction claim, we obtain $\text{Reg}^{\text{FO}}_{T}\leq\frac{144}{l^{\sigma}_{1}}dK\sqrt{\log T}T^{\rho
+\frac{3/2-\rho}{2^{k}}}.$ This suggests that

$$ $\sum^{T}_{t=1}\mathbb{E}\left(\mu(a^{*})-\mu(a_{t})\right)\leq\frac{144}{l^{ \sigma}_{1}}dK\sqrt{\log T}T^{\rho+\frac{3/2-\rho}{2^{k}}}.$ $$

By Jensen’s inequality, we have

$$ $\mathbb{E}(n_{t})=\min\left\{2,\sqrt{\frac{2}{\alpha}}\mathbb{E}\left(\sqrt{ \mu(a^{*})-\mu(a_{t})}\right)\right\}\leq\sqrt{\frac{2}{\alpha}}\sqrt{\mathbb{ E}\left(\mu(a^{*})-\mu(a_{t})\right)}.$ $$

Therefore we have

$$ $\mathbb{E}\left(\sum^{T}_{t=1}\sqrt{t}m_{t}n_{t}\right)\leq\sqrt{\frac{2}{ \alpha}}\sum^{T}_{t=1}\sqrt{t}m_{t}\sqrt{\mathbb{E}\left(\mu(a^{*})-\mu(a_{t}) \right)}.$ $$

By the definition of $\rho$-Imperfect Human Feedback, we have $|c_{t}(a_{t},a^{\prime}_{t})|$ is upper bounded by $C_{k}t^{-1+\rho}$.

Therefore, using Lemma 5 we can upper bound $\sqrt{\lambda}\sum^{T}_{t=1}\sqrt{t}m_{t}n_{t}$ by

$$ $\sqrt{\lambda}\sum^{T}_{t=1}\sqrt{t}m_{t}n_{t}\leq 60L^{\sigma}\sqrt{\frac{2 \lambda}{\alpha l^{\sigma}_{1}}}(\log T)^{0.25}C_{\kappa}\sqrt{dK}T^{\frac{3}{ 2}\rho+\frac{3/2-\rho}{2^{k+1}}}$ $$

Since $\lambda\leq\alpha l^{\sigma}_{1}/2$, choosing $\eta_{\rho}=\frac{1}{d}\frac{\sqrt{\log T}}{T^{\rho}}$, we have

$$ $\displaystyle\text{Reg}_{T}$ $\displaystyle\leq 2d\left(C_{0}+\frac{C_{2}}{\sqrt{\log T}}+60C_{\kappa}\sqrt{ K}T^{\frac{3/2-\rho}{2^{k+1}}}\right)\sqrt{\log T}T^{\rho}+12Kd\sqrt{\log T}T^ {\rho}$ $\displaystyle\leq 144dK\sqrt{\log T}T^{\rho+\frac{3/2-\rho}{2^{k+1}}}.$ $$

The claim holds true for step $k+1$. Therefore, it implies that the claim holds true for all k. Repeating this process infinitely many times, we obtain

$$ $\text{Reg}_{T}\leq\mathcal{O}\left(d\sqrt{\log T}T^{\rho}\right),$ $$

which completes the proof when $\rho\in[0.5,1]$.

###### Theorem (Theorem 2 restated) .

###### Definition 2 .

###### Lemma 15 (Lemma 12 in Kumagai ( 2017 ) ) .

###### Lemma (Lemma 2 restated) .

###### Lemma (Lemma 3 restated) .

###### Lemma 16 (Lemma 5 in Kumagai ( 2017 ) ) .

###### Lemma 17 (Lemma 10 in Kumagai ( 2017 ) ) .

###### Lemma 18 (Lemma 11 in Kumagai ( 2017 ) ) .

###### Lemma 19 (Lemma 4 in Hazan and Levy ( 2014 ) ) .

###### Lemma (Lemma 4 restated) .

###### Lemma (Lemma 5 restated) .

###### Lemma 20 .

###### Lemma 21 .

###### Lemma (Lemma 6 restated) .

## C Proof for Proposition 2

###### Proposition (Proposition 2 restated) .

If the total corruption level satisfies $\sum^{T}_{t=1}|c_{t}(a_{t},a^{\prime}_{t})|\leq\mathcal{O}(T^{\rho})$, then for any $\alpha\in[\frac{1}{2},1)$, if the utility function is strongly concave, for sufficiently large round $T$, by choosing learning rate $\eta_{\rho}:=\frac{\sqrt{\log T}}{2d}T^{-\alpha}$

- 1.
(Robustness) RoSMID incurs $\text{Reg}_{T}\leq\tilde{\mathcal{O}}(dT^{\alpha}+\sqrt{d}T^{\frac{1}{2}(1-
\alpha)+\rho}+dT^{\rho})$.
- 2.
(Efficiency) There exists a strongly concave utility function $\mu$ and a link function $\sigma$ such that $\text{Reg}_{T}$ suffered by RoSMID is at least $\Omega\left(T^{\alpha}\right)$ in scenario without corruption.

###### Proposition (Proposition 2 restated) .

### C.1 Proof for Robustness Statement in Proposition 2

Proof
From Lemma 4, we know

$$ $\displaystyle\mathbb{E}\left\{\sum^{T}_{t=1}b^{\top}_{t}(a_{t}-a^{*}_{T})\right\}$ $\displaystyle\leq 2RdL^{\sigma}\sqrt{\lambda^{*}_{R}+2\phi}T^{\rho}+d\sqrt{ \lambda\eta_{\rho}}\mathbb{E}\left\{\sum^{T}_{t=1}\sqrt{t}\min\left(2,L^{ \sigma}|c_{t}(a_{t},a^{\prime}_{t})|\right)\|a_{t}-a^{*}_{T}\|_{2}\right\}$ $\displaystyle\leq 2RdL^{\sigma}\sqrt{\lambda^{*}_{R}+2\phi}T^{\rho}+2Rd\sqrt{ \lambda\eta_{\rho}}L^{\sigma}\sum^{T}_{t=1}\sqrt{t}|c_{t}(a_{t},a^{\prime}_{t})|$ $\displaystyle\leq 2RdL^{\sigma}\sqrt{\lambda^{*}_{R}+2\phi}T^{\rho}+2Rd\sqrt{ \lambda\eta_{\rho}T}L^{\sigma}T^{\rho}.$ $$

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 Lemma 21). Therefore, by Lemma 3, we have

$$ $\displaystyle\text{Reg}_{T}\leq\frac{C_{0}}{\eta_{\rho}}\log(T)+8d^{2}\eta_{ \rho}T+2L^{\mu}L^{\sigma}_{1}R+4RdL^{\sigma}\sqrt{\lambda^{*}_{R}+2\phi}T^{ \rho}+4Rd\sqrt{\lambda\eta_{\rho}T}L^{\sigma}T^{\rho}.$ $$

Choosing $\eta_{\rho}=\frac{\sqrt{\log T}}{2d}T^{-\alpha},\alpha\in[0.5,1)$, we have

$$ $\displaystyle\text{Reg}_{T}$ $\displaystyle\leq 2dC_{0}\sqrt{\log T}T^{\alpha}+4d\sqrt{\log T}T^{1-\alpha}+4 RdL^{\sigma}\sqrt{\lambda^{*}_{R}+2\phi}T^{\rho}+4R\sqrt{d}L^{\sigma}(\log T)^ {0.25}T^{\frac{1}{2}(1-\alpha)}T^{\rho}+2L^{\mu}L^{\sigma}_{1}R$ $\displaystyle\leq O\left(d\sqrt{\log T}T^{\alpha}+\sqrt{d}(\log T)^{\frac{1}{4 }}T^{\frac{1}{2}(1-\alpha)}T^{\rho}+dT^{\rho}\right),$ $$

which completes the proof of robustness statement.

### C.2 Proof for Efficiency Statement in Proposition 2

Proof
The robustness statement in Proposition 2 implies that RoSMID could afford agnostic corruption level $\mathcal{O}(T^{\frac{1+\alpha}{2}})$. If Lemma 22 holds, this implies that there exists a hard instance which makes RoSMID incur regret in order of $\Omega(T^{\alpha})$ in non-corrupt setting. We can prove this by contradiction. Assume the efficiency statement in Proposition 2 is not true, which implies that for all $\mu$, and $\sigma$, there exists an $\epsilon>0$ such that $\text{Reg}_{T}=c_{0}T^{\alpha-\epsilon}$, for some constant $c_{0}>0$, we assume $\epsilon$ to be the least possible. In this scenario, when we consider a linear link function $\sigma(x)=\frac{1+x}{2}$, Lemma 22 implies that an agnostic corruption budget $2\sqrt{c_{0}}T^{\frac{1+\alpha-\epsilon}{2}}$ suffices to induce linear regret, which contradicts the robustness statement in Proposition 2.

###### Lemma 22 .

For any algorithm $\mathcal{G}$ incurs regret $\text{Reg}_{T}\leq c_{0}T^{\alpha}$, for some constant $c_{0}>0$, on learning from bandit with reward feedback for strongly concave utilities $\mu$ in non-corrupted setting, then there exists an instance $\mu$ such that $\mathcal{G}$ will suffer linear regret under agnostic corruption with budget $\sqrt{c_{0}}T^{\frac{1+\alpha}{2}}$.

Proof
Consider the scenario when $d=2$, the action space $\mathcal{A}:=\{(a_{1},a_{2}):a_{1}\geq 0,a_{2}\geq 0,a_{1}+a_{2}\leq 1\}$, the utility function $\mu_{\theta}(a)=\langle\theta,a\rangle-\frac{1}{2}\|a\|^{2}_{2}$ with $\theta:=[1,0]$. In this scenario, the optimal action is $a^{*}:=[1,0]$. Assume that the adversary want to “fool” the algorithm $\mathcal{G}$ to make it believe the $\theta:=[1,1]$, with optimal arm $a^{*}=[\frac{1}{2},\frac{1}{2}]$, each round, the corruption it should introduce is $c_{t}(a_{t})=a_{t2}$, where $a_{ti}$ is the $i$-th coordinate value of action $a_{t}$. To make reward indistinguishable from these two environments, the total corruption budget which the adversary has to pay is $\sum^{T}_{t=1}|a_{t2}|$. We know that $\mathcal{G}$ incurs regret $\text{Reg}_{T}:=\sum^{T}_{t=1}\langle\theta,a^{*}-a_{t}\rangle-\frac{1}{2}\|a^
{*}\|^{2}_{2}+\frac{1}{2}\|a_{t}\|^{2}_{2}=\frac{1}{2}-a_{t1}+\frac{1}{2}a^{2}
_{t1}+\frac{1}{2}a^{2}_{t2}\leq c_{0}T^{\alpha}$. Given this constraint, the maximum possible corruption paid by the adversary to make $\theta=[1,1]$ and $\theta=[1,0]$ indistinguishable is $\max\sum^{T}_{t=1}|a_{t2}|=\sqrt{c_{0}}T^{\frac{\alpha+1}{2}}$. Therefore, for any agnostic corruption no less than $\sqrt{c_{0}}T^{\frac{\alpha+1}{2}}$, $\mathcal{G}$ can not distinguish $\theta=[1,0]$ and $\theta=[1,1]$ and has to incur linear regret in either of these environments.

###### Lemma 22 .

## D Proof for Proposition 3 :

In this section, we present the regret upper for dueling bandit gradient descent Yue and Joachims () in presence of *arbitrary* and *agnostic* corruption. Before presenting the proof, we make several remarks. First, in Yue and Joachims (), the utility function $\mu$ 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 $\mu$, the requirement for “strictness” can be relaxed. Second, we highlight the notation differences. We use $a$ to denote actions while Yue and Joachims () uses $w$. In our proof, we define $P_{t}(a):=\sigma\left(\mu(a_{t})-\mu(a)\right)$ to represent the probability of the event $a_{t}\succ a$. While in Yue and Joachims (), it is denoted as $c_{t}(w)$. Just to highlight, its corrupted version $\hat{P}_{t}(a):=\sigma\left(\mu(a_{t})-\mu(a)+c_{t}(a_{t},a)\right)$ is newly introduced in our paper. Moreover, $\bar{P}_{t}(a):=\mathbb{E}_{x\in\mathbb{B}}\left[P_{t}(\mathcal{P}_{\mathcal{A
}}(a+\delta x))\right]$ is denoted as $\hat{\epsilon}_{t}(w)+\frac{1}{2}$ in Yue and Joachims (). The definition of $\mathcal{F}\left(\mathcal{P}_{\mathcal{A}}\left(a_{t}+\delta u_{t}\right),a_{t
}\right)$ is same as $X_{t}\left(\mathcal{P}_{W}(w_{t}+\delta u_{t})\right)$ defined in Yue and Joachims (), except different notation. We remark $\mathcal{P}_{\mathcal{A}}(a)$ represent the projection of action $a$ on $\mathcal{A}$.

Figure: Algorithm 3 Dueling Bandit Gradient Descent (DBGD) (Yue and Joachims, )

###### Proposition (Proposition 3 restated) .

If the total corruption level satisfies $\sum^{T}_{t=1}|c_{t}(a_{t},a^{\prime}_{t})|\leq\mathcal{O}(T^{\rho})$, then for any $\alpha\in(0,\frac{1}{4}]$, if utility function $\mu$ is generally concave, for a sufficiently large round $T$, choosing $\gamma:=\frac{R}{\sqrt{T}}$ and $\delta:=\frac{\sqrt{2Rd}}{\sqrt{13L^{\sigma}L^{\mu}}T^{\alpha}}$ for Algorithm 3

- 1.
(Robustness) $\text{Reg}_{T}$ incurred by Algorithm 3 satisfies $\text{Reg}_{T}\leq\mathcal{O}(\sqrt{d}T^{1-\alpha}+\sqrt{d}T^{\alpha+\rho})$.
- 2.
(Efficiency) There exists a linear utility function $\mu$ and a link function $\sigma$ such that $\text{Reg}_{T}$ suffered by Algorithm 3 is at least $\Omega\left(T^{1-\alpha}\right)$ in scenario without corruption.

###### Proposition (Proposition 3 restated) .

### D.1 Proof for Robustness Statement in Proposition 3

Proof
The proof of Theorem 3 builds on the proof of Yue and Joachims (), where we extend it to a setting in presence of agnostic corruption. The proof follows Step 1-3 introduced in Theorem 2. 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 $g_{t}$ is defined as follows

$$ $g_{t}=-\frac{d}{\delta}\mathcal{F}\left(\mathcal{P}_{\mathcal{A}}\left(a_{t}+ \delta u_{t}\right),a_{t}\right)u_{t}.$ $$

In the presence of adversarial corruption, the corrupted gradient is

$$ $\hat{g}_{t}=-\frac{d}{\delta}\hat{\mathcal{F}}\left(\mathcal{P}_{\mathcal{A}} \left(a_{t}+\delta u_{t}\right),a_{t}\right)u_{t}.$ $$

Therefore, we quantify the bias $\mathbb{E}(b_{t}|a_{t})$ in the following lemma.

###### Lemma 23 .

Let $P_{t}(a)$ represent the likelihood of action $a_{t}$ being preferred over $a$, where $P_{t}(a):=\sigma(\mu(a_{t})-\mu(a))$. Likewise, the corrupted version is defined as $\hat{P}_{t}(a)=\sigma(\mu(a_{t})-\mu(a)+c_{t}(a_{t},a))$. The smoothed version of $P_{t}$ over $\mathcal{A}$ is $\bar{P}_{t}(a):=\mathbb{E}_{x\in\mathbb{B}}\left[P_{t}(\mathcal{P}_{\mathcal{A
}}(a+\delta x))\right]$. Let $a^{\prime}_{t}=\mathcal{P}_{\mathcal{A}}(a_{t}+\delta u_{t})$, where $u_{t}$ is uniformly sampled from $\mathbb{S}$ and $\hat{g}_{t}=-\frac{d}{\delta}\hat{\mathcal{F}}\left(a^{\prime}_{t},a_{t}\right
)u_{t}$. Let $b_{t}:=\frac{d}{\delta}\left(\hat{P}_{t}(a^{\prime}_{t})-P_{t}(a^{\prime}_{t})
\right)u_{t}$. We have $\mathbb{E}(\hat{g}_{t}|a_{t})=\mathbb{E}(\nabla\bar{P}_{t}(a_{t})|a_{t})-
\mathbb{E}(b_{t}|a_{t}).$

Proof
(Proof for Lemma 23).
Since $a^{\prime}_{t}:=\mathcal{P}_{\mathcal{A}}(a_{t}+\delta u_{t})$, we have

$$ $\displaystyle\mathbb{E}(\hat{g}_{t}|a_{t})$ $\displaystyle=\mathbb{E}_{u_{t}}(\mathbb{E}(\hat{g}_{t}|a_{t},u_{t}))$ $\displaystyle=-\frac{d}{\delta}\mathbb{E}_{u_{t}}\left(\mathbb{E}(\hat{ \mathcal{F}}(a^{\prime}_{t},a_{t})u_{t}|a_{t},u_{t})\right)$ $\displaystyle=-\frac{d}{\delta}\mathbb{E}\left(\hat{P}_{t}(a^{\prime}_{t})u_{t }|a_{t}\right)$ $\displaystyle=-\frac{d}{\delta}\mathbb{E}\left(\left[P_{t}(a^{\prime}_{t})+ \hat{P}_{t}(a^{\prime}_{t})-P_{t}(a^{\prime}_{t})\right]u_{t}|a_{t}\right)$ $\displaystyle=\nabla\mathbb{E}_{x\in\mathbb{B}}\left(P_{t}(\mathcal{P}_{ \mathcal{A}}(a_{t}+\delta x))|a_{t}\right)-\frac{d}{\delta}\mathbb{E}\left[ \left(\hat{P}_{t}(a^{\prime}_{t})-P_{t}(a^{\prime}_{t})\right)u_{t}|a_{t}\right]$ (23) $\displaystyle=\nabla\bar{P}_{t}(a_{t})-\frac{d}{\delta}\mathbb{E}\left[\left( \hat{P}_{t}(a^{\prime}_{t})-P_{t}(a^{\prime}_{t})\right)u_{t}|a_{t}\right]$ $\displaystyle=\mathbb{E}(g_{t}|a_{t})-\frac{d}{\delta}\mathbb{E}\left[\left( \hat{P}_{t}(a^{\prime}_{t})-P_{t}(a^{\prime}_{t})\right)u_{t}|a_{t}\right].$ (24) $$

We get the equation (23) by using Lemma 24. We get equation (24) by using Lemma 25.

###### Lemma 24 (Lemma 2 in Yue and Joachims ( 2009 ) ) .

Fix $\delta>0$, over random unit vector $u$, we have

$$ $\mathbb{E}[P_{t}(\mathcal{P}_{\mathcal{A}}(a+\delta u))u]=\frac{\delta}{d} \nabla\bar{P}_{t}(a).$ $$

###### Lemma 25 (Lemma 1 in Yue and Joachims ( 2009 ) ) .

$\mathbb{E}_{\mathcal{F},u}[\mathcal{F}(a^{\prime}_{t},a_{t})u]=-\mathbb{E}_{u}
[P_{t}(a^{\prime}_{t})u]$.

In Step 2, we decompose regret under dueling bandits into two parts, regret of decision and feedback error.

###### Lemma 26 (Regret Decomposition for DBGD) .

Define $\lambda:=\frac{L^{\sigma}}{L^{\sigma}-\delta L^{\mu}L_{2}}$, $L_{2}$ is the Lipschitz constant for $\sigma^{\prime}$, $\gamma=R/\sqrt{T}$, for $b_{t}$ defined in Lemma 23, we have

$$ $\displaystyle\text{Reg}_{T}$ $\displaystyle\leq\underbrace{\lambda\left(\frac{2Rd\sqrt{T}}{\delta}+13\delta L ^{\sigma}L^{\mu}T\right)}_{{\color[rgb]{1,0,0}\definecolor[named]{ pgfstrokecolor}{rgb}{1,0,0}Regret\hskip 2.84526ptof\hskip 2.84526ptDecision}}+ \underbrace{2\lambda\sum^{T}_{t=1}\mathbb{E}\left(b_{t}^{\top}(a_{t}-a^{*}) \right)}_{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0} Feedback\hskip 2.84526ptError}}.$ $$

Proof
Because of Lemma 27, we have

$$ $\displaystyle\mathbb{E}\left[\sum^{T}_{t=1}\bar{P}_{t}(a_{t})-\bar{P}_{t}(a^{* })\right]\leq\sum^{T}_{t=1}\mathbb{E}\left(\lambda\nabla\bar{P}_{t}(a_{t})(a_{ t}-a^{*})+(3+\lambda)\delta L^{\sigma}L^{\mu}\right)$ $\displaystyle=\lambda\sum^{T}_{t=1}\mathbb{E}(\mathbb{E}(g_{t}|a_{t})^{\top}(a _{t}-a^{*}))+(3+\lambda)\delta L^{\sigma}L^{\mu}T$ $\displaystyle=\lambda\sum^{T}_{t=1}\mathbb{E}(\mathbb{E}(\hat{g}_{t}+b_{t}|a_{ t})^{\top}(a_{t}-a^{*}))+(3+\lambda)\delta L^{\sigma}L^{\mu}T$ $\displaystyle=\lambda\sum^{T}_{t=1}\mathbb{E}(\hat{g}_{t}^{\top}(a_{t}-a^{*})) +\lambda\sum^{T}_{t=1}\mathbb{E}(b_{t}^{\top}(a_{t}-a^{*}))+(3+\lambda)\delta L ^{\sigma}L^{\mu}T$ $$

###### Lemma 27 (Lemma 4 in Yue and Joachims ( 2009 ) ) .

Fix $\delta\in(0,\frac{L^{\sigma}}{L^{\mu}L_{2}})$, for $\lambda$ defined in Lemma 26, we have

$$ $\mathbb{E}\left[\sum^{T}_{t=1}\bar{P}_{t}(a_{t})-\bar{P}_{t}(a^{*})\right]\leq \sum^{T}_{t=1}\mathbb{E}\left(\lambda\nabla\bar{P}_{t}(a_{t})^{\top}(a_{t}-a^{ *})+(3+\lambda)\delta L^{\sigma}L^{\mu}\right).$ $$

Since $a_{t+1}=\mathcal{P}_{\mathcal{A}}(a_{t}-\eta\hat{g}_{t})$, and $\eta=\frac{\gamma\delta}{d}$, by applying the telescoping sum and because $a_{1}=0$, $\|g_{t}\|_{2}\leq G,\forall t$, we have

$$ $\displaystyle\lambda\sum^{T}_{t=1}\mathbb{E}\left(\hat{g}_{t}^{\top}(a_{t}-a^{ *})\right)\leq\lambda\left(\frac{R^{2}}{2\eta}+\frac{T\eta G^{2}}{2}\right).$ $$

Noticing that $\|b_{t}\|_{2}\leq\frac{d}{\delta}\min\left(2,L^{\sigma}|c_{t}(a_{t},a^{\prime}
_{t})|\right)$. Moreover, $\|a_{t}-a^{*}\|_{2}\leq 2R$. Therefore, in Step 3, we can control the feedback error by the following.

###### Lemma 28 .

$\sum^{T}_{t=1}\mathbb{E}\left(b_{t}^{\top}(a_{t}-a^{*})\right)\leq 2RdL^{
\sigma}T^{\rho}/\delta$.

Proof
(Proof for Lemma 28).

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E}(b_{t}(a_{t}-a^{*}))$ $\displaystyle\leq 2R\frac{d}{\delta}\sum^{T}_{t=1}\min\left(2,L^{\sigma}|c_{t} (a_{t},a^{\prime}_{t})|\right)$ $\displaystyle\leq 2R\frac{dL^{\sigma}}{\delta}\sum^{T}_{t=1}|c_{t}(a_{t},a^{ \prime}_{t})|$ $\displaystyle=2R\frac{dL^{\sigma}T^{\rho}}{\delta}.$ $$

###### Lemma 29 (Lemma 3 in Yue and Joachims ( 2009 ) ) .

$\text{Reg}_{T}\leq 2\mathbb{E}\left[\sum^{T}_{t=1}\bar{P}_{t}(a_{t})-\bar{P}_{
t}(a^{*})\right]+5\delta L^{\sigma}L^{\mu}T$

Set $G=\frac{d}{\delta}$, and by Lemma 29, we have

$$ $\text{Reg}_{T}\leq\lambda\left(\frac{2Rd\sqrt{T}}{\delta}+13\delta L^{\sigma}L ^{\mu}T\right)+4R\frac{\lambda dL^{\sigma}T^{\rho}}{\delta}.$ $$

Therefore, by choosing $\delta:=\frac{\sqrt{2Rd}}{\sqrt{13L^{\sigma}L^{\mu}}T^{\alpha}},\gamma:=\frac{
R}{\sqrt{T}}$, and $T>\left(\frac{\sqrt{2Rd}L_{\mu}L_{2}}{\sqrt{13L^{\sigma}L^{\mu}}L^{\sigma}}
\right)^{4}$, we have

$$ $\text{Reg}_{T}\leq 2\lambda_{T}\sqrt{26RdL^{\sigma}L^{\mu}}T^{1-\alpha}+2L^{ \sigma}\sqrt{26RdL^{\sigma}L^{\mu}}T^{\alpha+\rho}.$ $$

$\lambda_{T}=\frac{L^{\sigma}\sqrt{13L^{\sigma}L^{\mu}}T^{\alpha}}{L^{\sigma}
\sqrt{13L^{\sigma}L^{\mu}}T^{\alpha}-L^{\mu}L_{2}\sqrt{2Rd}}$, completes the proof.

###### Lemma 23 .

###### Lemma 24 (Lemma 2 in Yue and Joachims ( 2009 ) ) .

###### Lemma 25 (Lemma 1 in Yue and Joachims ( 2009 ) ) .

###### Lemma 26 (Regret Decomposition for DBGD) .

###### Lemma 27 (Lemma 4 in Yue and Joachims ( 2009 ) ) .

###### Lemma 28 .

###### Lemma 29 (Lemma 3 in Yue and Joachims ( 2009 ) ) .

### D.2 Proof for Efficiency Statement in Proposition 3

Proof
The robustness statement in Proposition 3 implies that DBGD could afford agnostic corruption level $\mathcal{O}(T^{1-\alpha})$. This implies that there exists a hard instance which makes DBGD attain regret in order of $\Omega(T^{1-\alpha})$ in non-corrupt setting, formally described as follows. To start a proof by contradiction, we assume that the efficiency statement in Proposition 3 is false. Specifically, for all problem instance $\mu,\sigma$, there exist a $\epsilon>0$, such that $\text{Reg}_{T}\leq\mathcal{O}(T^{1-\alpha-\epsilon})$. We assume $\epsilon$ to be the least possible. In particular, there exists a pair of instance $\mu,\sigma$ such that $\text{Reg}_{T}=c_{0}T^{1-\alpha-\epsilon}$, $c_{0}$ is a positive constant. In other words, it says that there exists a pair of instance $\mu,\sigma$ such that DBGD suffers regret in $\Theta(T^{1-\alpha-\epsilon})$.

Consider the following problem instance. $\mu(a)=\theta^{\top}a$, specifically $\mu$ is linear function. Let $d=2$ with action set $\mathcal{A}_{1}:=\{(a_{1},a_{2}):a_{1}\geq 0,a_{2}\geq 0,\frac{1}{2}a_{1}+a_{2
}-\frac{1}{4}\leq 0\}$ with $\theta=[\frac{1}{2},\frac{1}{2}]$. The optimal arm is $a_{1}=[\frac{1}{2},0]$, which is unique. Let the link function $\sigma(x)=\frac{1}{2}+\frac{1}{2}x$. It is easy to verify that it is rotational symmetric and Lipschitz. Denote $\text{Reg}_{T}$ as the regret occurred by DBGD on this problem instance. We know $\text{Reg}_{T}\leq\mathcal{O}(T^{1-\alpha-\epsilon})$. Consequently, it implies that $a_{2}$ is at most proposed $8c_{0}T^{1-\alpha-\epsilon}$ times. This is because $\text{Reg}_{T}\leq c_{0}T^{1-\alpha-\epsilon}$ and if the proposed action pair $(a_{t},a^{\prime}_{t})$ including $a_{2}$ at round $t$, it occurs regret at least $\frac{1}{8}$.

Now consider a different problem instance with the same $\mu,\sigma$ but different action set, which is $\mathcal{A}_{2}:=\{(a_{1},a_{2}):a_{1}\geq 0,a_{2}\geq 0,\frac{3}{2}a_{1}+a_{2
}-\frac{3}{4}\leq 0\}$. The optimal arm in this action set $a_{2}=[0,\frac{3}{4}]$, which is also unique. Proposing arm $a_{1}=[\frac{1}{2},0]$ occurs at least $\frac{1}{8}$ regret. Consider an adversary that pulls the utility of $a_{2}$ from $\frac{3}{8}$ down to $\frac{1}{8}$ whenever it is pulled at a cost of $c_{t}(A_{t})=\frac{1}{4}$. It is equivalent to say that every time when the proposed arm $w$ falls in the region $\mathcal{W}=\{a_{1}\geq 0,a_{2}\geq 0,\frac{1}{2}a_{1}+a_{2}-\frac{1}{4}\geq 0
,\frac{3}{2}a_{1}+a_{2}-\frac{3}{4}\leq 0\}$, we assume that the utility is sampled from $\theta^{\top}\mathcal{P}_{\mathcal{A}_{1}}(w)$ and $|c_{t}(w)|=|\theta^{\top}\mathcal{P}_{\mathcal{A}_{1}}(w)-\theta^{\top}w|\leq
\frac{1}{4}$. Choosing the total corruption budget as $2c_{0}T^{1-\alpha-\epsilon}$, the adversary can afford to corrupt $8c_{0}T^{1-\alpha-\epsilon}$ 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 $a_{2}$ as most $8c_{0}T^{1-\alpha-\epsilon}$. However, $a_{2}$ is the optimal arm in the second problem instance, which implies that the regret occurred on the second problem instance is at least $T-8c_{0}T^{1-\alpha-\epsilon}$, which is linear in $T$. This contradicts the robustness statement in Proposition 3, which says that when agnostic corruption is $2c_{0}T^{1-\alpha-\epsilon}$, the regret upper bound is $O(T^{1-\epsilon})$, 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 $\Omega(T^{1-\alpha})$ to make the parallel world argument valid.

## E 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 $\text{Reg}_{T}$ 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 to estimate the slope of the line, which is the *fitted order* of $\text{Reg}_{T}$.

Baseline Algorithms. We consider three baseline algorithms for comparison, Doubler (Ailon et al., ) and Sparring (Ailon et al., )

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 et al., )), with regret $\mathcal{O}(T^{3/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 a regret upper bound guarantee, it is reported to enjoy better performance compared to Doubler (Ailon et al., ). We also choose BGD as the underlying MAB algorithm.

To validate efficiency-robustness trade-off in Proposition 2 and Proposition 3, we try different $\alpha$ values. In the first row of Figure 3, we consider $\alpha=0.05$ for DBGD and $\alpha=0.9$ for RoSMID. We consider $\rho\in[0.5,0.95]$. According to the theoretical prediction, both DBGD and RoSMID can tolerate at most $\mathcal{O}(T^{0.95})$ 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 3, we consider $\alpha=0.1$ for DBGD and $\alpha=0.8$ for RoSMID. According to the theoretical prediction, both DBGD and RoSMID can tolerate at most $\mathcal{O}(T^{0.9})$ agnostic corruption. From the figure, we can see they have smaller fitted order of regret when $\rho=0.5$ while at a cost of tolerating smaller magnitude of agnostic corruption (it has linear regret when $\rho=0.95$), which reveals intrinsic tradeoff between efficiency and robustness.

Figure: Figure 3: In the first row, we consider $\alpha=0.05$ for DBGD and $\alpha=0.9$ for RoSMID. In the second row, we consider $\alpha=0.1$ for DBGD and $\alpha=0.8$ for RoSMID. Given the $\alpha$, for each algorithm, we tested its performance under $\rho$-Imperfect Human feedback with $\rho=0.5,0.8,0.95$. For each $\rho$, we presented a line plot of the average regret over five simulations, accompanied by $\pm$ 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.
Refer to caption: extracted/5899968/ICLR25/image/beta5LU.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Please refer to the 'Weaknesses' section.
soundness: 3
strengths: 1. The paper is generally easy to follow.
1. The proposed RoSMID algorithm is nearly optimal when the gap between its upper bound and the lower bound is only $\log T$.
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.

==========

After rebuttal: I would like to keep the score.
weaknesses: 1. The paper repeatedly emphasize the novelty of the analysis. It would be appreciated to summarize the novelty in a few words.
1. Lemma 3.1: I am confused why the author(s) discussed the direct reward feedback setting here.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
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. 

2. What is the regret upper bound when the utility function is just concave (and not strongly concave)?

3. 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?
soundness: 3
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.

2. 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).
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.
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.

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

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

4. 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?

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 2
questions: - Could RoSMID use an upper bound on $\rho$ if the exact decay rate is unknown? How would this affect the performance of RoSMID?
- 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?
soundness: 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.
- 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.
- 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.
- 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.
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.
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.
- 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.
- 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.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: 1. Why do you think the assumptions made in line 143-152 are reasonable? I feel they are very specific.

2. 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.
soundness: 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.
2. The paper is clearly written and easy to understand.
3. This paper studies a timely topic of robust bandits to adversarial corruptions.
4. Experimental results are presented after theoretical analysis.
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.
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:

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

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

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

1.4 For the assumptions made in line 143-152, it is better to highlight where these assumptions come from one by one.

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

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: - Can you relax the assumptions on the link function $\sigma$, so that it includes natural functions?
- 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?
soundness: 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 :
- 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
- 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

Overall, 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
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)$.

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

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

Additionally, this is not explicitly written, but it seems that the authors rely on the fact that $l_1^{\sigma}>0$ in the whole paper. 

-------

Here are some minor remarks:
- 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 ..."

Meta-review: This paper addresses the concave-utility continuous-action dueling bandit problem, particularly focusing on a model that includes time-decaying corruption with an eye toward applications in Learning from Imperfect Human Feedback. The authors propose an algorithm for this problem setting and provide regret upper bounds. The effectiveness of the results is also validated through experiments.  

Weaknesses of the paper include concerns that the scenario where corruption decays at a fixed rate is overly restrictive, that knowledge of the decay rate parameter $\rho$ is required in advance to achieve optimal bounds, and that the computational complexity is significant. However, the authors have provided reasonably convincing rebuttals to these concerns.  

Most of the reviewers rated the paper near the borderline, but there was overall agreement on its positive contributions. As such, I support its acceptance.

Decision: Accept (Poster)