22footnotetext: Equal contribution.33footnotetext: Work done while visiting
University of Chicago.11footnotetext: This work is supported by the AI2050
program at Schmidt Sciences (Grant G-24-66104), Army Research Office Award
W911NF-23-1-0030, ONR Award N00014-23-1-2802 and NSF Award CCF-2303372.

# Learning from _Imperfect_ Human Feedback: a Tale from Corruption-Robust
$\text{Dueling}^{*}$

Yuwei Cheng1<EMAIL_ADDRESS>Fan Yao2,3$\dagger{\ddagger}$
<EMAIL_ADDRESS>Xuefeng Liu2$\dagger$<EMAIL_ADDRESS>Haifeng Xu2
<EMAIL_ADDRESS>
1Department of Statistics, University of Chicago, USA
2Department of Computer Science, University of Chicago, USA
3Department of Computer Science, University of Virginia, USA

###### Abstract

This paper studies Learning from _Imperfect_ Human Feedback (LIHF), motivated
by humans’ potential irrationality or imperfect perception of true preference.
We revisit the classic dueling bandit problem as a model of learning from
comparative human feedback, and enrich it by casting the imperfection in human
feedback as _agnostic_ corruption to user utilities. We start by identifying
the fundamental limits of LIHF and prove a regret lower bound of
$\Omega(\max\\{T^{1/2},C\\})$, even when the total corruption $C$ is known and
when the corruption decays gracefully over time (i.e., user feedback becomes
increasingly more accurate). We then turn to design robust algorithms
applicable in real-world scenarios with arbitrary corruption and unknown $C$.
Our key finding is that gradient-based algorithms enjoy a smooth efficiency-
robustness tradeoff under corruption by varying their learning rates.
Specifically, under general concave user utility, Dueling Bandit Gradient
Descent (DBGD) of Yue and Joachims (2009) can be tuned to achieve regret
$O(T^{1-\alpha}+T^{\alpha}C)$ for any given parameter
$\alpha\in(0,\frac{1}{4}]$. Additionally, this result enables us to pin down
the regret lower bound of the standard DBGD (the $\alpha=1/4$ case) as
$\Omega(T^{3/4})$ for the first time, to the best of our knowledge. For
strongly concave user utility we show a better tradeoff: there is an algorithm
that achieves $O(T^{\alpha}+T^{\frac{1}{2}(1-\alpha)}C)$ for any given
$\alpha\in[\frac{1}{2},1)$. Our theoretical insights are corroborated by
extensive experiments on real-world recommendation data.

##  1 Introduction

Many real-world problems, such as personalized recommendation (Yue and
Joachims, 2009; Immorlica et al., 2020; Yao et al., 2022a) and fine-tuning
generative models (Bai et al., 2022; Casper et al., 2023; Han et al., 2024),
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., 2022). A natural theoretical framework capturing such
learning task is the seminal dueling bandits framework introduced by Yue and
Joachims (2009). The dueling bandit problem features an 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., 2020).

However, human feedback is often _imperfect_ , a crucial factor that has been
largely overlooked in previous studies of dueling bandit. Ample behavioral
studies show that humans often refine their preferences through interactions
with the system, navigating a complex tradeoff between exploration and
exploitation (Wilson et al., 2014; Cohen et al., 2007). Furthermore, their
response errors may exhibit systematic patterns rather than merely random
noise. As we are all aware of, humans are not always rational (Posner, 1997)
neither perfectly know our preferences (Pu et al., 2012).

In this paper, we study learning from _imperfect_ human feedback (LIHF) by
casting the imperfection in the feedback as certain form of corruption to the
utilities. This leads us to study a natural variant of the continuous dueling
bandit with corrupted utilities. Notably, our study differs from recent robust
algorithms designed for corrupted dueling bandits (Di et al., 2024; Saha and
Gaillard, 2022; Komiyama et al., 2015) in three key aspects. Firstly, these
previous algorithms all focus on a finite action space whereas, to the best of
our knowledge, ours is the first to investigate a robust dueling bandit
algorithm under corruption for continuous action space. This focus is
motivated by the fact that many real-world applications have continuous or
extremely dense action spaces, such as token embeddings or content
recommendations (Chen et al., 2021, 2019). Second, our algorithms are designed
for _agnostic_ corruption without knowing the corruption levels, whereas Di et
al. (2024) requires knowledge of the total corruption amount. This focus on
agnostic corruption is motivated by realistic considerations, because systems
often cannot accurately discern the irrational or imperfect nature of human
feedback. Third, our corruption models are very different from the model
studied by Di et al. (2024); Saha and Gaillard (2022); Komiyama et al. (2015).
The corruption in their model contaminates feedback by flipping the realized
outcomes of the duels, whereas the corruption in our model is on utilities
which consequently only alter the winning probabilities of the duels. This
difference is due to our different motivation of corruption, which is to
capture imperfect human behavior while not intentional adversarial attack (see
more illustration in Section 3).

Our Contributions. By modeling LIHF as a continuous dueling bandit under
agnostic corruption, we start by characterizing its intrinsic hardness. We
prove a regret lower bound of $\Omega(d\max\\{\sqrt{T},C\\})$, even when the
total corruption $C$ is known and when corruption decays gradually over time.
Additionally, we prove that this lower bound result is tight by exhibiting an
algorithm that indeed achieves a matching upper bound for the aforementioned
setting. Next, we turn to design robust algorithms that are applicable to
arbitrary and agnostic corruption with unknown $C$. Our key finding is that
gradient-based algorithms offer a smooth efficiency-robustness tradeoff under
corruption by carefully tuning their learning rates. Specifically, let $d$
denote the problem dimension. For any given $\alpha\in(0,1/4]$, Dueling Bandit
Gradient Descent (DBGD) (Yue and Joachims, 2009) with carefully chosen
learning rate (that depends on $\alpha$) can achieve a regret of
$O(\sqrt{d}T^{1-\alpha}+\sqrt{d}T^{\alpha}C)$ under arbitrary concave user
utility. That is, by decreasing $\alpha$ from $1/4$ to $0$, the regret under
no corruption (i.e., learning efficiency) decays from $\sqrt{d}T^{3/4}$ to
$\sqrt{d}T$ but the algorithm’s tolerance to total amount of corruption
increases from $O(T^{3/4})$ to $O(T)$ (i.e., more robustness). Perhaps
surprisingly, this result turns out to allow us to pin down a regret lower
bound for the standard version of DBGD (the $\alpha=1/4$ case) as
$\Omega(T^{3/4})$, marking the first tight lower bound result for the DBGD
algorithm to the best of our knowledge. For strongly concave user utility, we
show that an improved tradeoff is possible: Noisy Comparison based Stochastic
Mirror Descent (NC-SMD) (Kumagai, 2017) can be refined to achieve a regret of
$O(dT^{\alpha}+\sqrt{d}T^{\frac{1-\alpha}{2}}C+dC)$ for any given
$\alpha\in[1/2,1)$. We remark that similar robustness-accuracy tradeoff has
been studied classification problem with adversarial examples, both
empirically (Tsipras et al., 2018) and theoretically (Zhang et al., 2019).
However, to the best of our knowledge, this is the first time such tradeoff is
formally analyzed for online learning. Finally, we conduct extensive
experiments on real-world recommendation data to validate our theoretical
insights.

##  2 Related Work

Hardness of Learning from Imperfect Human Feedback: To design algorithms
robust to adversarial corruption, it is crucial to understand the intrinsic
hardness of learning from corrupted feedback. Lattimore and Szepesvári (2020)
demonstrates that the minimax regret lower bound for stochastic linear bandits
is $\Omega(d\sqrt{T})$. Utilizing the regret lower bound for bandit convex
optimization (Shamir, 2013), Kumagai (2017) illustrates that dueling bandits
with a strongly concave utility function achieve a regret lower bound of
$\Omega(d\sqrt{T})$. In scenarios of adversarial corruption, Bogunovic et al.
(2020) proves that any algorithm faces regret at least $\Omega(dC)$ for
stochastic linear bandits. However, currently there is no literature that has
explored the intrinsic hardness of learning from corruption which decays
gradually over time (Wilson et al., 2014; Kumagai, 2017; Cohen et al., 2007),
despite its prevalence in learning from imperfect human feedback. It still
remains unknown whether learning from such corruption is fundamentally easier
than learning from arbitrary corruption.

Stochastic Bandits with Unknown Corruption: Applying the principle of optimism
in face of uncertainty and constructing estimators involving uncertainty
weighting, algorithms devised by He et al. (2022) and Ye et al. (2024a) attain
nearly optimal regret bounds for both linear and nonlinear contextual bandits
in presence of adversarial corruption. By leveraging the concept of phase
elimination, Bogunovic et al. (2022) introduces a robust algorithm capable of
handling corruption in rewards drawn from Gaussian processes. However, the
designs of these algorithms require explicit knowledge of the total corruption
level $C$ as an input. Gupta et al. (2019) employ novel sampling strategy to
channel resources to arms with better performance and craft algorithms robust
to agnostic corruption, yet restricted to finite action sets. In scenarios
involving continuous action set with unknown corruption level, even though
algorithms designed by Ding et al. (2022) and Bogunovic et al. (2020) have
sublinear regret guarantee, the regret is at least $C$ times worse than the
regret without corruption. It remains as an open problem of whether better
regret guarantee is achievable—that is, affording unknown corruption level
more than $\Omega(\sqrt{T})$ while maintaining $O(\sqrt{T})$ regret guarantee
in scenario without corruption.

Continuous Dueling Bandits with Unknown Corruption: In addition to stochastic
bandits, there exists an extensive body of literature studying the dueling
bandit problem with unknown corruption, given its prevalence in real-world
application (Bengs et al., 2021b; Sui et al., 2018). The literature on dueling
bandits with adversarial corruption has been initially explored by Agarwal et
al. (2021) and subsequently enhanced by Saha and Gaillard (2022), which
achieves optimality in term of $C$. However, their work is solely applicable
to finite action sets, which may not be feasible in many real-world scenarios
that have continuous or extremely dense action spaces, such as token
embeddings or content recommendations (Chen et al., 2021, 2019). Ailon et al.
(2014) introduced a reduction method that translates existing results from
conventional Multi-Armed Bandit algorithms to Dueling Bandits. This reduction
method is applicable to both finite and continuous action spaces, albeit
requiring a linear link function. DBGD (Yue and Joachims, 2009) and NC-SMD
(Kumagai, 2017) enjoy flexibility in choosing the link function but only work
for continuous dueling bandits. It still remains as an open problem for
developing provably efficient algorithm capable of learning from corrupted
dueling feedback with unknown corruption in continuous action space. This
serves as the driving force behind our theoretical analysis.

##  3 The Problem of Learning from Imperfect Human Feedback (LIHF)

Conventional Notation. Throughout the paper, for a positive integer $T$, we
use $[T]$ to denote $\\{1,2,\ldots,T\\}$. We use
$\mathcal{P}_{\mathcal{A}}(a)$ to denote the projection of action $a$ on
$\mathcal{A}$. We use standard asymptotic notations including $O(\cdot)$,
$\Omega(\cdot)$, $\Theta(\cdot)$. We use $\tilde{O}(\cdot)$,
$\tilde{\Omega}(\cdot)$, $\tilde{\Theta}(\cdot)$ to hide logarithmic factors.
We use $\|\cdot\|_{\infty}$ to define infinity norm. $\text{Reg}_{T}$
represents regret with dueling feedback over $T$ rounds.

To capture learning from imperfect (comparative) human feedback, we now
introduce a natural variant of the seminal dueling bandit framework (Yue and
Joachims, 2009) by integrating the “imperfections” in human feedback as
certain corruption to human agents’ feedback. An immediate critique one might
have is that arbitrarily adversarial corruption seems too pessimistic as a way
to model humans’ inaccuracies which are often caused by uncertainty or
ignorance, rather than targeted attacks. While this may appear true at the
first glance, we provide strong theoretical and empirical evidences that
corruption caused by uncertainties generally is as hard as arbitrary
corruption. For such reasons, we coin the following problem _Learning from
Imperfect Human Feedback_ (LIHF).

Basics of Dueling Bandits and Assumptions. We consider the standard dueling
bandit framework with continuous _action_ set
$\mathcal{A}\subset\mathbb{R}^{d}$ (Yue and Joachims, 2009). At each round
$t\in[T]$, the learner (henceforth denoted as $\mathcal{L}$) 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)$. That
is, in absence of any corruption, the user picks action $a_{t}$ with
probability $\sigma(\mu(a_{t})-\mu(a^{\prime}_{t}))$, and action
$a^{\prime}_{t}$ otherwise. As clear from its definition, this choice
probability depends only on the utility difference
$\mu(a_{t})-\mu(a^{\prime}_{t})$. Notably, user’s randomized action does carry
information about underlying utility function $\mu$, which is why the action
is also called the “human feedback” (Bengs et al., 2021a; Maystre and
Grossglauser, 2017; Ailon et al., 2014). Following standard assumptions in
this literature (Kumagai, 2017; Yue and Joachims, 2009), we also assume

  1. 1.

the continuous action space $\mathcal{A}$ contains the origin, is compact,
convex and is contained in a $d$-dimensional ball of radius $R$;

  2. 2.

the utility function $\mu:\mathcal{A}\rightarrow\mathbb{R}$ is concave,
differentiable, $L_{\mu}$-Lipschitz and admits unique optimal within set
$\mathcal{A}$, denoted as $a^{*}:=\arg\max_{a\in\mathcal{A}}\mu(a)$;

  3. 3.

the link function $\sigma:\mathbb{R}\rightarrow[0,1]$ is rotational-symmetric,
$L_{\sigma}$-Lipschitz and its first derivative $\sigma^{\prime}$ is
$L_{2}$-Lipschitz.

For convenience, we further let $L=L_{\sigma}L_{\mu}$. Notably, some previous
works restrict link function to specifically be the logistic link function (Di
et al., 2024; Xu et al., 2024; Saha, 2021). However, our results shall be
applicable to any link functions that satisfy the natural assumptions above.

Inaccuracies in Human Feedback as Agnostic Corruption. Extending the standard
dueling bandit framework above, we introduce a _corruption_ term
$c_{t}(a_{t},a^{\prime}_{t})$ to the utility difference in order to model
potential inaccuracy in the user’s perception of underlying true utilities.
For all our positive results, we always work with the situation where this
corruption is _agnostic_ in the sense that the learner does not know the value
of each $c_{t}$ neither their accumulated sum. Such agnostic corruption is
natural because in reality it is very difficult to truly estimate how
imperfect a user is, hence we aim to develop algorithms whose execution is
agnostic to such parameters. Let $a\succ a^{\prime}$ denote the event that the
user chooses $a$ over $a^{\prime}$. Hence in our LIHF problem, the probability
of event $a\succ a^{\prime}$ in presence of corruption $c(a,a^{\prime})$,
denoted as $\hat{\mathbb{P}}(a\succ a^{\prime})$, can be expressed as follows
$\hat{\mathbb{P}}(a\succ
a^{\prime})=\sigma(\mu(a)-\mu(a^{\prime})+c(a,a^{\prime}))$. We further let
$\hat{\mathcal{F}}(a_{t},a^{\prime}_{t})$ denote user’s preferential feedback
under corruption, coined corrupted dueling feedback. Mathematically,
$\hat{\mathcal{F}}(a_{t},a^{\prime}_{t})$ follows a binomial distribution with
mean $\hat{\mathbb{P}}(a_{t}\succ a^{\prime}_{t})$, expressed by the following
equation.

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

The “hat” notation in $\hat{\mathcal{F}}$ and $\hat{\mathbb{P}}$ is to denote
corruption. When there is no corruption, we use $\mathbb{P}(a\succ
a^{\prime})=\sigma(\mu(a)-\mu(a^{\prime}))$ to denote the probability of event
$a\succ a^{\prime}$ and $\mathcal{F}(a,a^{\prime})$ to denote corresponding
dueling feedback. It is important to recognize the different roles of the link
function $\sigma$ and utility corruption $c_{t}$ — $\sigma$ captures the
inherent (often inevitable) randomness in human choice/behavior even given
true utilities (Fishburn et al., 1979; Becker et al., 1963; Bradley and Terry,
1952), whereas our $c_{t}$ is introduced to model inaccurate perception of
utilities due to not perfectly knowing her preferences and, importantly, can
be alleviated or even eliminated once the user has tried sufficient actions.

Imperfect user feedback generally is not as wild as arbitrary adversarial
corruption. A particularly natural pattern of human’s imperfection is that the
inaccuracy in our estimations often diminishes as we try more and more
actions. That is, humans learn along the way, though how fast the inaccuracy
decreases often depends on our learning rate. This hence motivates us to
consider the following notion of $\rho$_-imperfect user_ which significantly
constrain the corruption sequence $c_{1},c_{2},\cdots$, and force it to
diminish at the rate $\rho$.

######  Definition 1 ($\rho$-Imperfect User).

The user feedback is said to be $\rho$-imperfect for some $\rho\in[0,1]$ if
there exists a constant $C_{\kappa}>0$ such that the corruption $c_{t}$
satisfies $|c_{t}|\leq C_{\kappa}t^{\rho-1},\forall t\in[T]$.111All our
results naturally applies to $\rho<0$, which is a significantly easier
situation since accumulated corruption is a constant in that case. We hence
will not explicitly consider it in this paper.

For a $\rho$-imperfect user, the accumulated corruption
$\sum_{\tau=1}^{t-1}|c_{\tau}|\leq C_{\kappa}t^{\rho}$ for every $t$, which is
why this is coined $\rho$-imperfect. The diminishing inaccuracy of user
estimation in Definition 1 is a natural model for user’s learning behavior and
has already been used in various previous works to model user’s imperfect
feedback (Wang et al., 2023; Yao et al., 2022a; Immorlica et al., 2020)
(Details are presented at Appendix A). Note that agnostic corruption in this
situation means the learner know $|c_{t}|\leq C_{\kappa}t^{\rho-1}$ for some
$\rho$, but she does not know the value of $\rho$.

On the other hand, the corruption are said to be _arbitrary_ up to certain
budget $C$, if $\sum_{t=1}^{T}|c_{t}|\leq C$ for a given (hence fixed) time
horizon $T$. Our designed (positive) learning algorithmic will have guaranteed
regret upper bound under arbitrary corruption, though our lower bound (i.e.,
negative result) will hold even in the weaker $\rho$-imperfect user feedback.

We remark that another line of recent research studies a different type of
corruption that directly flip the outcomes of the duels; i.e., flipping the
realized event $a\succ a^{\prime}$ to its opposite $a^{\prime}\succ a$ (Di et
al., 2024; Saha and Gaillard, 2022; Komiyama et al., 2015). These corruption
models are motivated by the existence of true _adversaries_ , e.g., malicious
users in recommendation systems (Lykouris et al., 2018) or fraudulent clicks
(Deshpande and Montanari, 2013), who have the capability of altering user
choices. In contrast, only utilities are corrupted in our model. These two
models are not comparable. For instance, the adversary can induce a
deterministic event $a\succ a^{\prime}$ at any given round with one
corruption, whereas the outcomes in our model is almost always probabilistic
(unless the adversary uses an infinite budget $c_{t}$). Such modeling
difference inherently comes from the different motivations of our LIHF
problem. Specifically, our model is to capture imperfect human feedback due to
inaccurate perception of utilities or ignorance of true preferences. For
example, when recommender systems learn to find the optimal recommendation for
a user, the user may not know her true preference at the beginning and often
gradually refines her preferences through experiencing different items (Yao et
al., 2022b). Similarly, when generative models like ChatGPT learn to generate
personalized content for a user, the user may go through a similar procedure
of preference refinement during interactions with the model. These modelling
differences also necessitate our fundamentally different techniques. Our
approaches are based on gradient-based methods whereas Di et al. (2024) and
Saha (2021) employ the principle of optimistic in face of uncertainty and
construct the confidence set of preferences through querying the maximum
information pair. Their approaches inherently require the knowledge of total
corruption level $C$. In contrast, the analysis of our gradient-based methods
controls the impact of gradient bias (due to corruption) on regret. By
adjusting its learning rate, our algorithm will gracefully “trade” its
learning efficiency for more robustness against agnostic corruption. Moreover,
our algorithm is suitable for infinite _action_ space, whereas previous works
of Di et al. (2024); Saha (2021) are for finite action spaces.

Learning goal: agnostic corruption-robust regret minimization.  The goal of
the learner is to optimize her sequential actions to minimize the following
dueling regret against an arbitrary sequence of corruption
$\\{c_{t}\\}_{t=1}^{T}$:

$\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 is also studied in many prior literature (Saha and
Gaillard, 2022; Kumagai, 2017; Komiyama et al., 2015; Yue and Joachims, 2009).
Importantly, all our algorithms are agnostic to the corruption in the sense
that the algorithm does _not_ depend on any knowledge of
$\\{c_{t}\\}_{t=1}^{T}$.

##  4 The Intrinsic Limit of Learning from Imperfect Human Feedback

To understand the inherent difficulty of LIHF, in this section we develop
regret lower bounds for a setting that is even easier to learn – that is,
learning from a $\rho$-imperfect user (Definition 1) with a _known_ $\rho$.
While this non-agnostic may appear simpler, our main result of this section
exhibits a tight lower bound of $\Omega(d\max\\{\sqrt{T},T^{\rho}\\})$ for
strongly concave user utilities. We also show a similar lower bound hold for
linear user utility as well. Our lower bound result differs in two key aspects
from various previous lower bound results for online learning under
corruptions (Agarwal et al., 2021; Bogunovic et al., 2020). Firstly, previous
lower bound proofs require the adversaries’ capability to corrupt the reward
feedback in an _arbitrary_ way, whereas the corruption in our proof will
follow Definition 1. It is unclear whether such strictly more restrictive
corruption will be more tractable since it does offer the learner much more
accurate estimation about the amount of corruption at each round. Secondly,
previous construction of hard instances that attains regret lower bound relies
on linear reward, whereas our lower bound holds for strongly concave utility
functions, since they more realistically model human’s risk attitude and
consumption utilities (Chiappori and Rochet, 1987). Strongly concave utility
functions are generally perceived as easier to optimize and to learn, hence it
is unclear whether it is also the case under imperfect user feedback. While
both differences above seem to hint that our problem might be easier than
previous online learning problem under corruption, we show that the answer is
actually “No”.

######  Theorem 1 (A Tight Lower Bound).

There exists an LIHF instance with a $\rho$-imperfect user (Def. 1) and
strongly concave user utility such that any learner has to suffer
$\text{Reg}_{T}\geq\Omega(d\max\\{\sqrt{T},T^{\rho}\\})$ even _with the
knowledge of_ $\rho$. Moreover, this regret lower bound is tight, up to
logarithmic terms. That is, for the same setting, there exists an online
learning algorithm with
$\text{Reg}_{T}\leq\tilde{O}(d\max\\{\sqrt{T},T^{\rho}\\})$.

This theorem reveals the fundamental limits of learning from $\rho$-imperfect
users, even when the learner knows $\rho$. The core new lemma needed for
proving the regret lower bound in Theorem 1 is to show that even in standard
online learning with noisy bandit feedback about any pulled arm’s reward (as
opposed to comparative feedback in dueling setups), the same regret lower
bound holds. This is summarized in the following Lemma 1. We then convert this
lower bound for standard bandit reward feedback to our setting of
dueling/comparative feedback. Notably, Ye et al. (2024b) recently showed a
matching upper bound for the standard bandit reward feedback setting assuming
_arbitrary corruption_ with total amount $C$. Hence Lemma 1 and their results
together echoes our key insight in this section — that is, learning from
$\rho$-imperfect user is as hard as learning from arbitrarily corrupted
rewards in classic bandit reward feedback setting as well.

For linear user utility, perhaps unsurprisingly, we are able to show the same
lower bound as follows (see Prop. 1). En route, we similarly show that the
problem of learning directly from bandit linear reward feedback also suffers
the same regret lower bound $\Omega(d\max\\{\sqrt{T},T^{\rho}\\})$. This
happens to resolve an open problem proposed by Yao et al. (2022a) and implies
that the regret upper bound shown in (Yao et al., 2022a) for the “learning
from learning user” problem is tight in $T$.

######  Proposition 1.

There exists an LIHF instance with a $\rho$-imperfect user and linear user
utility such that any learner knowing $\rho$ has to suffer
$\text{Reg}_{T}\geq\Omega(d\max\\{\sqrt{T},T^{\rho}\\})$.

We defer the full proof of Theorem 1 and Proposition 1 to Appendix B.1 and
B.2. Below we only state a representative core lemma for the strongly concave
utility function case and its proof sketch, which is the crux of our lower
bound proof. Notably, the proof for the matching upper bound in Theorem 1 is
also highly non-trivial. Our starting point is the recent NC-SMD algorithm.
However, to achieve the tight regret upper bound, we have to employ a novel
and highly involved induction argument to identify the optimal learning rate.
Through this process, we established a new connection between the convergence
of the $L_{2}$-norm of the action $\|a_{t}-a^{*}\|_{2}$ and the regret itself
(It has been experimentally verified at Appendix D.1.2).

######  Lemma 1.

Assume that the action space $\mathcal{A}$ is contained in a $d$-dimensional
unit ball. Consider the utility function $\mu$ in the form
$\mu_{\theta}(a)=\theta^{\top}a-\frac{1}{2}\|a\|^{2}_{2}$, where
$\theta\in\mathbb{R}^{d},\|\theta\|_{2}\leq 1$, is a random vector. Under
corruption induced by $\rho$-_imperfect_ user (Def. 1), for any fixed number
of rounds $T$ and $d\leq\frac{1}{C_{\kappa}}T^{1-\rho}$, there exists a
preference parameter $\theta$ such that for any learner $\mathcal{L}$ under
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 (Proof Sketch of Lemma 1). We aim to show that there exists a corruption
strategy such that the regret incurred by any learner $\mathcal{L}$ with
_corrupted 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 $\mathcal{L}$ is bounded below by the sum of the Kullback-
Leibler (KL) divergence between the distribution of the _corrupted reward
feedback_ conditioned on different possible values of $\theta$. Specifically,
let $\theta$ be 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_{a_{t}}=\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_{a_{t}}.$
(2)

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

$\displaystyle\hat{v}^{\prime}_{t}=\mu_{\theta}(a_{t})+c_{t}(a_{t}|\theta_{i}<0)+\xi_{a_{t}}=\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_{a_{t}}.$
(3)

Consider the following corruption strategy which sets
$c_{t}(a_{t}|\theta_{i}>0)=-\beta a_{t,i}$ and $c_{t}(a_{t})=\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\\}.$
(4)

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 lower bound in Equation (4). 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 the _action_
space $\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
induced by $\rho$-_imperfect_ user, completing the proof.

##  5 The Efficiency-Robustness Tradeoff in LIHF

Section 4 shows that a lower bound regret of
$\Omega(d\max\\{\sqrt{T},T^{\rho}\\})$ is intrinsic for learning from
$\rho$-imperfect user, even with known $\rho$. In this section, we study what
would be possible — but in a significantly more challenging learning setting
with _arbitrary_ and _agnostic_ corruption. The reason for fighting for such
generality is due to practical considerations; in reality, it is rarely
possible to truly predict users’ irrationality or behaviors. Technique-wise,
gradient-based methods are the most commonly used for addressing continuous
action spaces, and so are our approaches. The key novelty in our results is
not about the development of fundamentally new algorithmic techniques, but
rather the conduct of more fine-grained analysis about two popular gradient-
based methods — Dueling Bandit Gradient Descent (DBGD (Yue and Joachims,
2009)) and Noisy Comparison-based Stochastic Mirror Descent (NC-SMD) (Kumagai,
2017) — and the proof of how these algorithms can be “tailored” to achieve
robustness against corruption. On a conceptual level, our key insight is that
one can carefully tune the learning rates of these gradient-based methods to
gracefully trade off learning efficiency for adversarial robustness — a
interesting concept which we coin the _efficiency-robustness tradeoff_.
Notably, en route developing our result, we also pin down a tight lower bound
of $\Omega(T^{3/4})$ for the well-known DBGD algorithm which surprisingly
remained an open question to date despite extensive studies of this algorithm.

Our finding reveals the intrinsic tradeoff between robustness and efficiency
for gradient-based algorithms under agnostic corruption (Theorem 2). In
general, the tradeoff is controlled by the exploration size in Algorithm 1
(depends on $\alpha$) (experimentally verified at Appendix D.1.4). A higher
tolerance of agnostic corruption comes at a cost of worse regret in scenario
without corruption, shown by Figure 1.

Input: Exploration rate $\delta$, exploitation rate $\gamma$, initial action
$a_{1}=\mathbf{0}\in\mathcal{A}$.

1 for  _$t\in[T]$_ do

2 Sample unit vector $u_{t}$ uniformly and set
$a^{\prime}_{t}:=\mathcal{P}_{\mathcal{A}}\left(a_{t}+\delta u_{t}\right)$.

3 Present action pair $(a_{t},a^{\prime}_{t})$ to user and receive corrupted
dueling feedback $\hat{\mathcal{F}}(a^{\prime}_{t},a_{t})$.

4 Compute gradient
$\hat{g}_{t}:=-\frac{d}{\delta}\hat{\mathcal{F}}(a^{\prime}_{t},a_{t})u_{t}$.

5 Set step size $\eta:=\frac{\gamma\delta}{d}$ and update
$a_{t+1}:=\mathcal{P}_{\mathcal{A}}(a_{t}-\eta\hat{g}_{t})$.

Algorithm 1 Dueling Bandit Gradient Descent (DBGD)

######  Theorem 2 (Efficiency-Robustness Tradeoff in DBGD).

For any $\alpha\in(0,\frac{1}{4}]$ and any number of round $T$ satisfying
$T>\left(\frac{\sqrt{2Rd}L_{\mu}L_{2}}{\sqrt{13L}L_{\sigma}}\right)^{4}$,
Algorithm 1 parameterized with $\gamma=\frac{R}{\sqrt{T}}$ and
$\delta=\frac{\sqrt{2Rd}}{\sqrt{13L}T^{\alpha}}$ achieves $\text{Reg}_{T}\leq
O(\sqrt{d}T^{1-\alpha}+\sqrt{d}T^{\alpha}C)$ for any total corruption level
$C$.

At the core of this proof is a novel development of a regret decomposition
lemma (Lemma 2), where we decompose the regret into two parts: regret of
decision making under uncertainty and regret due to feedback imperfection.
This decomposition has been proven to be useful for controlling regret of
interactive decision-making in reinforcement learning Foster et al. (2023).
However, to the best of our knowledge, Lemma 2 is the first to exhibit such a
decomposition for dueling feedback, which contains much sparser information
than the direct reward feedback as in RL or classic online learning in the
aforementioned studies. Hence we believe the lemma may be of independent
interest for future research on dueling bandits under corruption or erroneous
observation. Our proof employs new techniques and is also more involved.
Previous proofs of the decomposition lemma for reward feedback crucially
hinges on an online estimation oracle Foster et al. (2023), which however
cannot be constructed in our problem with dueling feedback with agnostic
corruption. We thus have to develop new proof ideas tailored specifically for
dueling bandit feedback. We start from quantifying the bias $b_{t}$ caused by
adversarial corruption in gradient estimation, and then show that we can
control the cumulative impact of bias by the exploration size $\delta$, i.e.
$\sum^{T}_{t=1}\mathbb{E}\left(b_{t}^{\top}(a_{t}-a^{*})\right)\leq
2RdL_{\sigma}C/\delta$. Consequently, Lemma 2 shows that the regret of
decision and observation error are jointly controlled by the exploration size
$\delta$. We choose $\delta$ in order of
$\Theta(T^{-\alpha}),\alpha\in(0,1/4]$ to achieve a balance between optimizing
the learning objective (1) and controlling the gradient bias arising from the
_corrupted dueling feedback_. Following this, we show $\text{Reg}_{T}$ is
upper bounded by $O(\sqrt{d}T^{1-\alpha}+\sqrt{d}T^{\alpha}C)$.

Figure 1: Efficiency-Robustness Tradeoff

######  Lemma 2 (Regret Decomposition).

Let $b_{t}:=\frac{d}{\delta}\left(\hat{\mathbb{P}}(a^{\prime}_{t}\succ
a_{t})-\mathbb{P}(a^{\prime}_{t}\succ a_{t})\right)u_{t},u_{t}\sim\mathbb{S}$,
and choose $\lambda=\frac{L_{\sigma}}{L_{\sigma}-\delta L_{\mu}L_{\sigma}}$,
we have

$\displaystyle\text{Reg}_{T}$
$\displaystyle\leq\underbrace{\lambda\left(\frac{R^{2}d}{\gamma\delta}+\frac{T\gamma
d}{\delta}+13\delta
LT\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}Observation\hskip
2.84526ptError}}.$

Note that Algorithm 1 works for general concave user utility. However, if the
user displays a strongly concave utility, we can tune learning rate of NC-SMD
to get better tradeoff. Specifically, we can get better regret upper bound
$\tilde{O}(d\sqrt{T})$ in scenario without corruption at the same time
affording $O(T^{3/4})$ agnostic corruption (see Prop 2). The proof of
Proposition 2 shares similar structure as the proof Theorem 2, however working
with a different algorithm. We direct readers to Appendix C.1 and C.4 to see
full statement of Theorem 2, details of the Algorithm NC-SMD and proof of
Proposition 2.

######  Proposition 2 (Efficiency-Robustness Tradeoff in NC-SMD).

For any $\alpha\in[\frac{1}{2},1)$, if the utility function is strongly
concave, by choosing learning rate $\eta=\frac{\sqrt{\log T}}{2d}T^{-\alpha}$,
for the Algorithm NC-SMD, we have
$\text{Reg}_{T}\leq\tilde{O}(dT^{\alpha}+\sqrt{d}T^{\frac{1}{2}(1-\alpha)}C+dC)$
for any total corruption level $C$.

Figure 2: DBGD Lower Bound

An interesting corollary of Theorem 2 is that we can use it to show the DBGD
upper bound proved in (Yue and Joachims, 2009) is tight, which to the best of
our knowledge, has not been realized in the previous literature. In the
following we provide a sketch of Corollary 1. It has been verified by
experiments (see Figure 2, simulation details in Appendix D.1.1). We direct
readers to Appendix C.2 for proof details.

######  Corollary 1 (Minimax Lower Bound for DBGD).

There exists a linear utility function $\mu$ and a link function $\sigma$ such
that choosing $\alpha=1/4$, $\text{Reg}_{T}$ suffered by Algorithm 1 is at
least $\Omega\left(T^{3/4}\right)$.

Proof  (Proof Sketch of Corollary 1). Corollary 1 shows that the standard DBGD
algorithm with $\alpha=\frac{1}{4}$ can afford $O(T^{3/4})$ agnostic
corruption. Moreover, we observe that we can make the sub-optimal arm and the
optimal arm indistinguishable by using the total corruption level in the same
order of the number of times sub-optimal arm that has been pulled. Therefore,
there must exist an problem instance such that the sub-optimal arm has been
pulled at least $\Theta(T^{3/4})$ times by DBGD. If not, we can create the
parallel world to make DBGD suffer linear regret in one of the environments by
using total corruption level less than $\Theta(T^{3/4})$, which contradicts
Theorem 2. Intuitively, it says that if an environment is ”easy” to attack,
the agnostic corruption level which an algorithm could afford can not exceed
the worst possible regret suffered by the algorithm in scenario without
corruption.

##  6 Experiments

In this section, we study the empirical performance of DBGD and NC-SMD to
validate our theoretical analysis by running simulations on both synthetic
datasets and real-world recommendation data in comparison with several
baseline algorithms. Experimental details can be found at Appendix D.

###  6.1 Synthetic Data

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}$, 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^{*}$ is $\theta$
and $\mu_{\theta}(a^{*})=50$. We simulate _agnostic_ _arbitrary_ corruption
for $C=T^{\rho},\rho\in[0.5,0.75]$. Specifically, we force the user to submit
her least preferred item to the algorithm over the first $C$ rounds (for
experiments on corruption induced by $\rho$-_imperfect_ user, see Appendix
D.1.3). For each value of $\rho$, we repeat the experiments for $5$ times,
each under a different seed. We use Doubler and Sparring proposed by Ailon et
al. (2014) as the baseline algorithms for comparison. We set bandit gradient
descent (Flaxman et al., 2004) as the black-box bandit algorithm.

Figure 3: We show the log-log plot for regret occurred by different algorithms
under arbitrary agnostic corruption. For each $\rho$, we present the line plot
of average regret over $5$ simulations. The shaded region is the average
regret $\pm$ one standard deviation. In addition, we fit the order of the
average regret, i.e. $\mathbb{E}(\text{Reg}_{T})=T^{o}$, by least squares
using last $1\%$ of data.

Results and Discussion. Figure 3 shows that standard DBGD ($\alpha=1/4$) and
NC-SMD ($\alpha=1/2$) are able to tolerate $O(T^{3/4})$ unknown corruption,
aligning with the theoretical result. Experimentally, NC-SMD enjoys the best
performance under strongly concave utility. Empirically, Sparring has
comparable performance as DBGD, even though it is a heuristic approach with no
theoretical guarantee. The worst performance of Doubler might be attributed to
the fact that its theoretical guarantee is only applicable to linear link
function, which is different from our experiment setup.

###  6.2 Spotify Recommendation Data

Figure 4: Results on Spotify Recommendation

Evaluation Setup. We also evaluate our approach on Spotify recommendation data
(Spotify, 2020). The objective is to recommend songs to incoming users. This
dataset includes $17\times 10^{4}$ songs ($|\mathcal{A}|=17\times 10^{4}$),
each is described by 15 distinct features (d = 15). We create 5 different user
types by clustering the dataset into 5 groups. We use the average of the song
embedding within each group as the user’s preference vector. Our aim is to
recommend songs to users that have the highest cosine similarity (utility
function) with their preference vectors. We rescale the cosine similarity to
$[-100,100]$. We simulate corruption induced by $\rho$-_imperfect_ user to
model imperfect human feedback. We only test the performance of DBGD and
Sparring because NC-SMD only works under strongly concave utility and Doubler
only works under linear link function.

Results and Discussion. Figure 4 show that the performance of DBGD aligns with
theoretical prediction on real-world recommendation data, even in the scenario
when $\mathcal{A}$ is discrete and nonconvex. Both DBGD and Sparring are
robust to agnostic corruption induced by $\rho$-_imperfect_ user, however,
empirically it seems that Sparring is invariant to $\rho$. This might because
the song embeddings are highly sparse, which results in the fact that the
proposed arms according to the heuristic approach are easy to distinguish,
even under agnostic corruption.

Additional Experiments. We also test the performance of Versatile-DB (Saha and
Gaillard, 2022), an approach robust to agnostic corruption with theoretical
guarantee. However, this approach is not computationally efficient. When
$K=2000$, running 100 iterations takes around 20 CPU hours and it’s
performance is dominated by DBGD. We direct readers to Appendix D.2.1 to see
the details.

##  7 Conclusion

In this paper, we model learning from _imperfect_ human feedback as a
corrupted continuous dueling bandit. We highlight the fundamental difficulty
of LIHF by developing a regret lower bound. Then we show that by carefully
tuning the learning rates of gradient-based methods, we can gracefully trade
off learning efficiency for adversarial robustness. Our theoretical
predictions also hold on real-world dataset. For future direction, it is
interesting to generalize our setting to include contextual information and
design algorithms robust to agnostic corruption. In addition, it is also an
interesting open problem to design algorithms performs best-of-both-worlds,
i.e. performing optimally both with and without agnostic corruption, in
continuous action space.

## References

  * Agarwal et al. (2021) Arpit Agarwal, Shivani Agarwal, and Prathamesh Patil.  Stochastic dueling bandits with adversarial corruption.  In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors, _Proceedings of the 32nd International Conference on Algorithmic Learning Theory_ , volume 132 of _Proceedings of Machine Learning Research_ , pages 217–248. PMLR, 16–19 Mar 2021.  URL https://proceedings.mlr.press/v132/agarwal21a.html.
  * Ailon et al. (2014) Nir Ailon, Thorsten Joachims, and Zohar Karnin.  Reducing dueling bandits to cardinal bandits, 2014.
  * Bai et al. (2022) Yuntao Bai, Andy Jones, Kamal Ndousse, Amanda Askell, Anna Chen, Nova DasSarma, Dawn Drain, Stanislav Fort, Deep Ganguli, Tom Henighan, et al.  Training a helpful and harmless assistant with reinforcement learning from human feedback.  _arXiv preprint arXiv:2204.05862_ , 2022.
  * Becker et al. (1963) Gordon M Becker, Morris H DeGroot, and Jacob Marschak.  Stochastic models of choice behavior.  _Behavioral science_ , 8(1):41–55, 1963.
  * Bengs et al. (2021a) Viktor Bengs, Róbert Busa-Fekete, Adil El Mesaoudi-Paul, and Eyke Hüllermeier.  Preference-based online learning with dueling bandits: A survey.  _Journal of Machine Learning Research_ , 22(7):1–108, 2021a.
  * Bengs et al. (2021b) Viktor Bengs, Robert Busa-Fekete, Adil El Mesaoudi-Paul, and Eyke Hüllermeier.  Preference-based online learning with dueling bandits: A survey, 2021b.
  * Bogunovic et al. (2020) Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett.  Stochastic linear bandits robust to adversarial attacks, 2020.
  * Bogunovic et al. (2022) Ilija Bogunovic, Zihan Li, Andreas Krause, and Jonathan Scarlett.  A robust phased elimination algorithm for corruption-tolerant gaussian process bandits, 2022.
  * Bradley and Terry (1952) Ralph Allan Bradley and Milton E Terry.  Rank analysis of incomplete block designs: I. the method of paired comparisons.  _Biometrika_ , 39(3/4):324–345, 1952.
  * Casper et al. (2023) Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al.  Open problems and fundamental limitations of reinforcement learning from human feedback.  _Transactions on Machine Learning Research_ , 2023.
  * Chen et al. (2019) Haokun Chen, Xinyi Dai, Han Cai, Weinan Zhang, Xuejian Wang, Ruiming Tang, Yuzhou Zhang, and Yong Yu.  Large-scale interactive recommendation with tree-structured policy gradient.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 33, pages 3312–3320, 2019.
  * Chen et al. (2021) Lili Chen, Kevin Lu, Aravind Rajeswaran, Kimin Lee, Aditya Grover, Misha Laskin, Pieter Abbeel, Aravind Srinivas, and Igor Mordatch.  Decision transformer: Reinforcement learning via sequence modeling.  _Advances in neural information processing systems_ , 34:15084–15097, 2021.
  * Chiappori and Rochet (1987) Pierre-André Chiappori and Jean-Charles Rochet.  Revealed preferences and differentiable demand.  _Econometrica_ , 55(3):687–691, 1987.  ISSN 00129682, 14680262.  URL http://www.jstor.org/stable/1913607.
  * Cohen et al. (2007) Jonathan D Cohen, Samuel M McClure, and Angela J Yu.  Should i stay or should i go? how the human brain manages the trade-off between exploitation and exploration.  _Philosophical Transactions of the Royal Society B: Biological Sciences_ , 362(1481):933–942, 2007.
  * Deshpande and Montanari (2013) Yash Deshpande and Andrea Montanari.  Linear bandits in high dimension and recommendation systems, 2013.
  * Di et al. (2024) Qiwei Di, Jiafan He, and Quanquan Gu.  Nearly optimal algorithms for contextual dueling bandits from adversarial feedback.  _arXiv preprint arXiv:2404.10776_ , 2024.
  * Ding et al. (2022) Qin Ding, Cho-Jui Hsieh, and James Sharpnack.  Robust stochastic linear contextual bandits under adversarial attacks.  In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, _Proceedings of The 25th International Conference on Artificial Intelligence and Statistics_ , volume 151 of _Proceedings of Machine Learning Research_ , pages 7111–7123. PMLR, 28–30 Mar 2022.  URL https://proceedings.mlr.press/v151/ding22c.html.
  * Fishburn et al. (1979) Peter C Fishburn, Peter C Fishburn, et al.  _Utility theory for decision making_.  Krieger NY, 1979.
  * Flaxman et al. (2004) Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan.  Online convex optimization in the bandit setting: gradient descent without a gradient.  _arXiv preprint cs/0408007_ , 2004.
  * Flaxman et al. (2005) Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan McMahan.  Online convex optimization in the bandit setting: gradient descent without a gradient.  In _Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’05, page 385–394, USA, 2005. Society for Industrial and Applied Mathematics.  ISBN 0898715857.
  * Foster et al. (2023) Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin.  The statistical complexity of interactive decision making, 2023.
  * Gupta et al. (2019) Anupam Gupta, Tomer Koren, and Kunal Talwar.  Better algorithms for stochastic bandits with adversarial corruptions.  In Alina Beygelzimer and Daniel Hsu, editors, _Proceedings of the Thirty-Second Conference on Learning Theory_ , volume 99 of _Proceedings of Machine Learning Research_ , pages 1562–1578. PMLR, 25–28 Jun 2019.  URL https://proceedings.mlr.press/v99/gupta19a.html.
  * Han et al. (2024) Zeyu Han, Chao Gao, Jinyang Liu, Jeff Zhang, and Sai Qian Zhang.  Parameter-efficient fine-tuning for large models: A comprehensive survey, 2024.
  * Hazan and Levy (2014) Elad Hazan and Kfir Levy.  Bandit convex optimization: Towards tight bounds.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 27. Curran Associates, Inc., 2014.  URL https://proceedings.neurips.cc/paper_files/paper/2014/file/c399862d3b9d6b76c8436e924a68c45b-Paper.pdf.
  * He et al. (2022) Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu.  Nearly optimal algorithms for linear contextual bandits with adversarial corruptions, 2022.
  * Immorlica et al. (2020) Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, and Zhiwei Steven Wu.  Incentivizing exploration with selective data disclosure.  In _Proceedings of the 21st ACM Conference on Economics and Computation_ , pages 647–648, 2020.
  * Komiyama et al. (2015) Junpei Komiyama, Junya Honda, Hisashi Kashima, and Hiroshi Nakagawa.  Regret lower bound and optimal algorithm in dueling bandit problem.  In _Conference on learning theory_ , pages 1141–1154. PMLR, 2015.
  * Kumagai (2017) Wataru Kumagai.  Regret analysis for continuous dueling bandit.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit Algorithms_.  Cambridge University Press, 2020.  doi: 10.1017/9781108571401.
  * Li et al. (2017) Lihong Li, Yu Lu, and Dengyong Zhou.  Provably optimal algorithms for generalized linear contextual bandits.  In _International Conference on Machine Learning_ , pages 2071–2080. PMLR, 2017.
  * Lykouris et al. (2018) Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme.  Stochastic bandits robust to adversarial corruptions, 2018.
  * Maystre and Grossglauser (2017) Lucas Maystre and Matthias Grossglauser.  Just sort it! a simple and effective approach to active preference learning.  In _International Conference on Machine Learning_ , pages 2344–2353. PMLR, 2017.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  _Journal of Machine Learning Research_ , 12:2825–2830, 2011.
  * Posner (1997) Richard A Posner.  Rational choice, behavioral economics, and the law.  _StAn. l. reV._ , 50:1551, 1997.
  * Pu et al. (2012) Pearl Pu, Li Chen, and Rong Hu.  Evaluating recommender systems from the user’s perspective: survey of the state of the art.  _User Modeling and User-Adapted Interaction_ , 22:317–355, 2012.
  * Saha (2021) Aadirupa Saha.  Optimal algorithms for stochastic contextual preference bandits.  _Advances in Neural Information Processing Systems_ , 34:30050–30062, 2021.
  * Saha and Gaillard (2022) Aadirupa Saha and Pierre Gaillard.  Versatile dueling bandits: Best-of-both world analyses for learning from relative preferences.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 19011–19026. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/saha22a.html.
  * Shamir (2013) Ohad Shamir.  On the complexity of bandit and derivative-free stochastic convex optimization, 2013.
  * Spotify (2020) Spotify.  Music recommendation system using spotify dataset.  https://www.kaggle.com/code/vatsalmavani/music-recommendation-system-using-spotify-dataset, 2020.
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano.  Learning to summarize with human feedback.  _Advances in Neural Information Processing Systems_ , 33:3008–3021, 2020.
  * Sui et al. (2018) Yanan Sui, Masrour Zoghi, Katja Hofmann, and Yisong Yue.  Advancements in dueling bandits.  In _IJCAI_ , pages 5502–5510, 2018.
  * Tsipras et al. (2018) Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry.  Robustness may be at odds with accuracy.  In _International Conference on Learning Representations_ , 2018.
  * Wang et al. (2023) Chaoqi Wang, Ziyu Ye, Zhe Feng, Ashwinkumar Badanidiyuru, and Haifeng Xu.  Follow-ups also matter: Improving contextual bandits via post-serving contexts, 2023.
  * Williams (1963) WE Williams.  A class of integral equations.  In _Mathematical Proceedings of the Cambridge Philosophical Society_ , volume 59, pages 589–597. Cambridge University Press, 1963.
  * Wilson et al. (2014) Robert C Wilson, Andra Geana, John M White, Elliot A Ludvig, and Jonathan D Cohen.  Humans use directed and random exploration to solve the explore–exploit dilemma.  _Journal of experimental psychology: General_ , 143(6):2074, 2014.
  * Xu et al. (2024) Wenjie Xu, Wenbin Wang, Yuning Jiang, Bratislav Svetozarevic, and Colin N Jones.  Principled preferential bayesian optimization.  _arXiv preprint arXiv:2402.05367_ , 2024.
  * Yao et al. (2022a) Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu.  Learning from a learning user for optimal recommendations.  In _International Conference on Machine Learning_ , pages 25382–25406. PMLR, 2022a.
  * Yao et al. (2022b) Fan Yao, Chuanhao Li, Denis Nekipelov, Hongning Wang, and Haifeng Xu.  Learning the optimal recommendation from explorative users.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 36, pages 9457–9465, 2022b.
  * Ye et al. (2024a) Chenlu Ye, Jiafan He, Quanquan Gu, and Tong Zhang.  Towards robust model-based reinforcement learning against adversarial corruption, 2024a.
  * Ye et al. (2024b) Chenlu Ye, Wei Xiong, Quanquan Gu, and Tong Zhang.  Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes, 2024b.
  * Yue and Joachims (2009) Yisong Yue and Thorsten Joachims.  Interactively optimizing information retrieval systems as a dueling bandits problem.  In _International Conference on Machine Learning_ , 2009.  URL https://api.semanticscholar.org/CorpusID:13141692.
  * Zhang et al. (2019) Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan.  Theoretically principled trade-off between robustness and accuracy.  In _International conference on machine learning_ , pages 7472–7482. PMLR, 2019.

##  A Connection between Imperfect User and Generalized Learnability

In this section, we establish the connection between adversarial corruption,
corruption induced by generalized learnability, and corruption induced by
$\rho$-_imperfect_ user. Broadly speaking, holding total corruption budget $C$
constant, corruption induced by generalized learnability is a specific type of
_arbitrary_ corruption. Furthermore, if the proposed action pairs exhibit
sufficient diversity, corruption induced by $\rho$-_imperfect_ user is
equivalent to corruption induced by generalized learnability.

In the following, we introduce the concept of the generalized learnability of
the utility function $\mu$ in the scenario of pairwise comparison and the
associated corruption induced throughout the user’s learning process.

######  Definition A.1 (Corruption induced by Generalized Learnability).

There exists an algorithm $\mathcal{G}$ such that, given any arbitrary $t$
pairs of actions $\\{a_{s},a^{\prime}_{s}\\}^{t}_{s=1}$ and the associated
utility differences $\\{y_{s}\\}^{t}_{s=1}$, where
$y_{s}:=\mu(a_{s})-\mu_{(}a^{\prime}_{s})$, $\mathcal{G}$ can output an
estimated utility function $\mu_{t}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ of
the true utility function $\mu:\mathbb{R}^{d}\rightarrow\mathbb{R}$ such that
for any action pair $(a,a^{\prime})$ the following equation holds

$\displaystyle|c_{t}(a,a^{\prime})|=|\mu_{t}(a)-\mu(a)-(\mu_{t}(a^{\prime})-\mu(a^{\prime}))|\leq
C_{0}\left(\|a-a^{\prime}\|^{2}_{\bar{V}_{t}^{-1}}\right)^{1-\rho}.$

$C_{0}$ is some positive constant, $\rho\in[0,1]$, and
$\bar{V}_{t}:=\lambda\mathbb{I}_{d}+\sum^{t}_{s=1}(a_{s}-a^{\prime}_{s})(a_{s}-a^{\prime}_{s})^{\top}$,
where $\lambda$ is some positive constant to ensure that $\bar{V}_{t}$ is full
rank.

Def. A.1 is a variant of the generalized learnability assumption proposed by
Wang et al. (2023) and Yao et al. (2022a). Essentially, the parameter $\rho$
can be viewed as the user’s irrationality level. A higher value of $\rho$
implies lower learning speed of the user’s utility function $\mu$, hence a
larger magnitude of the total induced corruption. Let’s consider _arbitrary_
corruption with total corruption budget $C=\Theta(T^{\rho})$. Using Lemma A.1,
we can show that $c_{t}(a,a^{\prime})$ induced by the generalized learnability
of $\mu$ satisfies $\sum^{T}_{t=1}|c_{t}(a_{t},a^{\prime}_{t})|\leq
O(T^{\rho})$, implies that it is a specific type of _arbitrary_ corruption.

In the scenario when $\lambda_{\min}(\bar{V}_{t})$ increases in the order of
$\Theta(t)$, $(\|a-a^{\prime}\|^{2}_{\bar{V}^{-1}_{t}})^{1-\rho}$ has the
order $\Theta(t^{\rho-1})$, which implies there exists a positive constant
$C_{\kappa}$ that at round $t$, given arbitrarily proposed action pairs
$(a,a^{\prime})$, the magnitude of corruption $|c_{t}(a,a^{\prime})|\leq
C_{\kappa}t^{\rho-1}$, which means that corruption induced by a
$\rho$-_imperfect_ user coincides with corruption induced by the generalized
learnability of $\mu$.

We would like to highlight that the condition which
$\lambda_{\min}(\bar{V}_{t})$ increases in the order of $\Theta(t)$ could be
satisfied by gradient-descent based algorithm. Take Algorithm 1 as an example.
For simplicity, let’s assume $a^{*}$ is far away from the boundary of
$\mathcal{A}$ and projection never happens. It implies that
$a^{\prime}_{t}=a_{t}+\delta u_{t},\forall t\in[T]$. This assumption is
without loss of generality, since most of the proposed action $a^{\prime}_{t}$
will belong to the interior of the _action_ space $\mathcal{A}$. This is
because we start with $a_{0}=0$ and has small exploration size
$\delta\sim\Theta(T^{-\alpha})$. Roughly speaking, we can express
$\bar{V}_{t}=\lambda\mathbb{I}_{d}+\delta^{2}\sum^{t}_{s=1}u_{s}u^{\top}_{s}$,
where $u_{s}$ is uniformly sampled from $\mathbb{S}^{d}$. Then applying Lemma
A.2, we have $\lambda_{\min}(\bar{V}_{t})\sim\Theta(t)$ with high probability.

######  Lemma A.1 (Generalized Elliptical Lemma in Wang et al. (2023)).

Suppose $V_{0}\in\mathbb{R}^{d\times d}$ is any positive definite matrix,
$a_{1},\ldots,a_{T}\in\mathbb{R}^{d}$ is a sequence of vectors with bounded
$l_{2}$ norm and $\bar{V}_{t}:=V_{0}+\sum^{t}_{s=1}a_{s}a^{\top}_{s}$. Then
for any $\rho\in[0,1]$, the following inequality holds with probability at
least $1-\delta$

$\sum^{T}_{t=1}\left(\min\left\\{1,\|a_{t}\|^{2}_{\bar{V}^{-1}_{t}}\right\\}\right)^{1-\rho}\leq
2^{1-\rho}T^{\rho}\log^{1-\rho}\left(\frac{\det(\bar{V}_{t})}{\det(V_{0})}\right).$

######  Lemma A.2 (Proposition 1 in Li et al. (2017)).

Define $V_{t}:=\sum^{t}_{s=1}u_{s}u^{\top}_{s}$, where $u_{s}$ is drawn iid
from some distribution $\nu$ with support on the unit ball, $\mathbb{B}^{d}$.
Furthermore, let $\Sigma:=\mathbb{E}[u_{s}u^{\top}_{s}]$ be the second moment
matrix. $B$ and $\delta>0$ are two positive constants. Then, there exist
positive, universal constants $C_{1}$ and $C_{2}$ such that
$\lambda_{\min}(V_{s})\geq B$ with probability at least $1-\delta$, as long as

$t\geq\left(\frac{C_{1}\sqrt{d}+C_{2}\sqrt{\log(1/\delta)}}{\lambda_{\min}(\Sigma)}\right)^{2}+\frac{2B}{\lambda_{\min}(\Sigma)}.$

##  B Missing Proofs in Theorem 1 and Proposition 1

###  B.1 Proof for Theorem 1: A Tight Lower Bound

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

There exists an LIHF instance with a $\rho$-imperfect user (Def. 1) and
strongly concave user utility such that any learner has to suffer
$\text{Reg}_{T}\geq\Omega(d\max\\{\sqrt{T},T^{\rho}\\})$ even _with the
knowledge of_ $\rho$. Moreover, this regret lower bound is tight, up to
logarithmic terms. That is, for the same setting, there exists an online
learning algorithm with
$\text{Reg}_{T}\leq\tilde{O}(d\max\\{\sqrt{T},T^{\rho}\\})$.

Proof (Proof for Regret Lower Bound in Theorem 1). Before showing the regret
lower bound proof for Theorem 1, let’s first establish the following Lemma
B.1, which builds the connection between regret occurred under bandit reward
feedback and dueling feedback. This proof is inspired by Theorem 6 in Yao et
al. (2022a). To prove Lemma B.1, 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\\}.$
(5)

######  Lemma B.1.

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

Proof  (Proof for Lemma B.1).  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}f(a_{0,t})-f(a^{*})\right\\}&\leq\overline{\text{Reg}};\\\
\mathbb{E}\left\\{\sum^{T}_{t=1}f(a_{1,t})-f(a^{*})\right\\}&\leq\overline{\text{Reg}}.\end{split}$
(6)

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

Input: the time horizon $T$

1 for  _$t\leq T$_ do

2 Call algorithm $\mathcal{L}$ to generate two candidates $(a_{0,t},a_{1,t})$.

3 Present $(a_{0,t},a_{1,t})$ to user and received the feedback.

4 Return the feedback $a_{*,t}$ to algorithm $\mathcal{L}$ and update
$\mathcal{L}$.

Output : the sequential decision $\\{a_{i,t}\\}^{T}_{t=1}$

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

From Equation (6), 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 B.1 must hold, which
completes the proof.

At the next step, we will prove Theorem 1 by discussing the value of $\rho$
case by case. Consider the scenario when $\rho\leq 0.5$. This is equivalent to
say the total corruption level $C\leq\sqrt{T}$. In this scenario, since the
utility function is strongly concave, applying Lemma B.2, we know
$\overline{\text{Reg}}=0.02\min\left\\{T,d\sqrt{T}\right\\}$. By Lemma B.1, we
get $\text{Reg}^{\text{FO}}_{T}\geq 0.04\min\left\\{T,d\sqrt{T}\right\\}$.
Consider a linear link function $\sigma(x)=\frac{1}{2}+\frac{1}{2}x$, we have
$\text{Reg}_{T}\geq
0.02\min\left\\{T,d\sqrt{T}\right\\}\geq\Omega(d\max\\{\sqrt{T},T^{\rho}\\})$,
which completes the proof.

######  Lemma B.2 (Theorem 6 in (Shamir, 2013)).

Let the number of rounds $T$ be fixed. The for any learner $\mathcal{L}$,
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$, which is equivalent to
$C>\sqrt{T}$. In essence, we want to extend Lemma B.2 to the scenario in
presence of adversarial corruption induced by $\rho$-_imperfect_ user. If we
can show the regret lower bound can be generalized to $\Omega(dT^{\rho})$,
then applying the same technique which uses Lemma B.1 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 B.2 is proven at section B.1.1.

####  B.1.1 Proof for Lemma 1: Regret Lower Bound for Strongly Concave Utility

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

Assume that the action space $\mathcal{A}$ is contained in a $d$-dimensional
unit ball. Consider the utility function $\mu$ in the form
$\mu_{\theta}(a)=\theta^{\top}a-\frac{1}{2}\|a\|^{2}_{2}$, where
$\theta\in\mathbb{R}^{d},\|\theta\|_{2}\leq 1$ is a random vector. Under
corruption induced by $\rho$-_imperfect_ user (Def. 1), for any fixed number
of rounds $T$ and $d\leq\frac{1}{C_{\kappa}}T^{1-\rho}$, there exists a
preference parameter $\theta$ such that for any learner $\mathcal{L}$ under
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  (Proof for Lemma 1). To prove Lemma 1, we aim to prove that there
exists a corruption strategy such that the regret incurred by any learner
$\mathcal{L}$ with _corrupted 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 $\mathcal{L}$ 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[1,T]$, conditioned on different possible values of $\theta$.
(see Lemma B.4). 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_{a_{t}}=\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_{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_{a_{t}}=\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_{a_{t}}.$

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_{a_{t}}$ follows a standard Gaussian distribution.
Therefore, $\hat{v}_{t}$ in Equation 2 follows $\text{N}(\mu_{1},1)$.
$\hat{v}_{t}$ in Equation 3 follows $\text{N}(\mu_{2},1)$. By using Lemma B.3,
we have

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

######  Lemma B.3 (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 B.4, 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 B.4, 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
corruption induced by $\rho$-_imperfect_ user, which completes the proof.

######  Lemma B.4.

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 $\mathcal{L}$. Then there exists a
$\theta\in\mathbb{R}^{d},\|\theta\|_{2}\leq 1$, uniformly drawn from
$\\{-\beta,\beta\\}^{d}$, such that the regret occurred by $\mathcal{L}$ 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  (Proof for Lemma B.4). Using the similar argument in Shamir (2013),
assume that the leaner $\mathcal{L}$ 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 $\mathcal{L}$ would also hold over a randomization. To lower
bound Equation (9), we use Lemma B.5, 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 B.5, which
completes the proof.

######  Lemma B.5 (Lemma 4 in (Shamir, 2013)).

Let $\theta$ be a random vector, none of those coordinates is supported on
$0$. Let $\hat{v}_{1},\hat{v}_{2},\ldots,\hat{v}_{T}$ be a sequence of values
obtained by a deterministic learner $\mathcal{L}$ 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.

We defer reader to Appendix C.3 for the proof of matching regret upper bound
and the detailed description of the algorithm which achieves that upper bound.

###  B.2 Proof for Proposition 1: Regret Lower Bound for Linear Utility

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

There exists an LIHF instance with a $\rho$-imperfect user and linear user
utility such that any learner knowing $\rho$ has to suffer
$\text{Reg}_{T}\geq\Omega(d\max\\{\sqrt{T},T^{\rho}\\})$.

Proof  (Proof for Proposition 1). 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 B.6 and B.1 together
with linear link function, we have
$\text{Reg}_{T}\geq\Omega(d\max\\{\sqrt{T},T^{\rho}\\})$, which completes the
proof.

######  Lemma B.6 ((Lattimore and Szepesvári, 2020)).

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 Gaussian noise with mean 0 variance 1. Then for any learner
$\mathcal{L}$, 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 B.6 to the scenario in presence of adversarial corruption induced by
$\rho$-_imperfect_ user, which is shown in Lemma B.7

######  Lemma B.7.

Assume that the _action_ space $\mathcal{A}\subset[-1,1]^{d}$. Given
corruption induced by $\rho$-_imperfect_ user (Def. 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 $\mathcal{L}$ even with the knowledge of $\rho$ has to suffer regret
no less than $\frac{d}{8}C_{\kappa}T^{\rho}.$

Proof  (Proof for Lemma B.7). The proof extends Lemma B.6 to a scenario in
presence of corruption. We want to construct a parameter family and a
corruption strategy such that for all algorithm $\mathcal{L}$, 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 $\mathcal{L}$, 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 B.8, we have

$p_{\theta_{i}}+p_{\theta^{\prime}_{i}}\geq\frac{1}{2}\exp(-\mathbb{D}(\mathbb{P}_{\theta},\mathbb{P}_{\theta^{\prime}}))=\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 $\mathcal{L}$
after playing action $a_{t}$ when reward parameter is $\theta$. Similarly,
$P^{\prime}_{a_{t}}$ is the distribution of corrupted observed by
$\mathcal{L}$ after playing action $a_{t}$ when the reward parameter is
$\theta^{\prime}$.

######  Lemma B.8 (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}\mathbb{D}(P_{A_{t}},P^{\prime}_{A_{t}})\right]=0$,
which makes it indistinguishable by $\mathcal{L}$. 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 the
corruption induced by $\rho$-_imperfect_ user.

##  C Missing Proofs in Theorem 2 and Proposition 2

###  C.1 Proof for Theorem 2: Efficiency-Robustness Tradeoff in DBGD

In this section, we present the regret upper for dueling bandit gradient
descent Yue and Joachims (2009) in presence of _arbitrary_ and _agnostic_
corruption. Before presenting the proof, we make several remarks.

First, in Yue and Joachims (2009), 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 (2009) 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 (2009), 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 (2009). 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 (2009), except different notation.

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

For any $\alpha\in(0,\frac{1}{4}]$ and any number of round $T$ satisfying
$T>\left(\frac{\sqrt{2Rd}L_{\mu}L_{2}}{\sqrt{13L}L_{\sigma}}\right)^{4}$,
Algorithm 1 parameterized with $\gamma=\frac{R}{\sqrt{T}}$ and
$\delta=\frac{\sqrt{2Rd}}{\sqrt{13L}T^{\alpha}}$ achieves $\text{Reg}_{T}\leq
O(\sqrt{d}T^{1-\alpha}+\sqrt{d}T^{\alpha}C)$ for any total corruption level
$C$.

Proof  (Proof for Theorem 2). The proof of Theorem 2 builds on the proof of
Yue and Joachims (2009), where we extend it to a setting in presence of
agnostic corruption. The cornerstone of the theoretical analysis relies on
developing the regret decomposition lemma (Lemma 2), where we novelly
decompose the regret into two parts: regret of decision and observation error.
This decomposition is achieved through quantifying the bias, $b_{t}$, caused
by adversarial corruption, in gradient estimation (Lemma C.1). We further use
Lemma C.5 to upper bound the observation error in terms of the exploration
size $\delta$. Lemma 2 and Lemma C.5 reveal that the regret of decision and
observation error are jointly controlled by the exploration size $\delta$. We
choose $\delta$ in order of $O(T^{-\alpha})$ to achieve a balance between
optimizing the learning objective (1) and controlling the gradient bias
arising from the _corrupted dueling feedback_. Consequently, we have
$\text{Reg}_{T}$ is upper bounded by
$O(\sqrt{d}T^{1-\alpha}+\sqrt{d}T^{\alpha}C)$.

The development of the proof is based on the observation that 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 in the following lemma.

####  C.1.1 Proof for Lemma C.1: Gradient Estimation Under Corruption

######  Lemma C.1.

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 C.1). 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]$
(14)
$\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].$
(15)

We get the equation (14) by using Lemma C.2. We get equation (15) by using
Lemma C.3.

######  Lemma C.2 (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 C.3 (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]$.

####  C.1.2 Proof for Lemma 2: Regret Decomposition

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

Choose $\lambda=\frac{L_{\sigma}}{L_{\sigma}-\delta
L_{\mu}L_{\sigma}},\gamma=R/\sqrt{T}$, for $b_{t}$ defined in Lemma C.1, we
have

$\displaystyle\text{Reg}^{\text{DB}}_{T}$
$\displaystyle\leq\underbrace{\lambda\left(\frac{2Rd\sqrt{T}}{\delta}+13\delta
LT\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}Observation\hskip
2.84526ptError}}.$

Proof  (Proof for Lemma 2). Because of Lemma C.4, 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\right)$
$\displaystyle=\lambda\sum^{T}_{t=1}\mathbb{E}(\mathbb{E}(g_{t}|a_{t})^{\top}(a_{t}-a^{*}))+(3+\lambda)\delta
LT$
$\displaystyle=\lambda\sum^{T}_{t=1}\mathbb{E}(\mathbb{E}(\hat{g}_{t}+b_{t}|a_{t})^{\top}(a_{t}-a^{*}))+(3+\lambda)\delta
LT$
$\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
LT$

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

Fix $\delta\in(0,\frac{L_{\sigma}}{L_{\nu}L_{\sigma}})$ and define
$\lambda=\frac{L_{\sigma}}{L_{\sigma}-\delta L_{\nu}L_{2}}$, 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\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, we can control the
observation error by the following.

####  C.1.3 Proof for Lemma C.5: Observation Error

######  Lemma C.5.

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

Proof  (Proof for Lemma C.5).

$\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}C}{\delta}.$

######  Lemma C.6 (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
LT$

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

$\text{Reg}_{T}\leq\lambda\left(\frac{2Rd\sqrt{T}}{\delta}+13\delta
LT\right)+4R\frac{\lambda dL_{\sigma}C}{\delta}.$

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

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

$\lambda_{T}=\frac{L_{\sigma}\sqrt{13L}T^{\alpha}}{L_{\sigma}\sqrt{13L}T^{\alpha}-L_{v}L_{2}\sqrt{2Rd}}$.

###  C.2 Proof for Corollary 1: Minimax Lower Bound for DBGD

Theorem 2 implies that DBGD could afford agnostic corruption level
$O(T^{3/4})$. This implies that there exists a hard instance which makes DBGD
attain regret in order of $\Omega(T^{3/4})$, formally described as follows.

######  Corollary (Corollary 1 restated).

There exists a linear utility function $\mu$ and a link function $\sigma$ such
that choosing $\alpha=1/4$, $\text{Reg}_{T}$ suffered by Algorithm 1 is at
least $\Omega\left(T^{3/4}\right)$.

Proof  (Proof for Corollary 1). To start a proof by contradiction, we assume
that Theorem 2 is false. Specifically, for all problem instance $\mu,\sigma$,
there exist a $\epsilon>0$ such that $\text{Reg}_{T}\leq O(T^{3/4-\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^{3/4-\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^{3/4-\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 $R_{T}$ as the regret occurred by
DBGD on this problem instance. We know $R_{T}\leq
O(T^{\frac{3}{4}-\epsilon})$. Consequently, it implies that $a_{2}$ is at most
proposed $8c_{0}T^{\frac{3}{4}-\epsilon}$ times. This is because $R_{T}\leq
c_{0}T^{\frac{3}{4}-\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 $C=2c_{0}T^{\frac{3}{4}-\epsilon}$, the adversary can afford to
corrupt $8c_{0}T^{\frac{3}{4}-\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^{\frac{3}{4}-\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^{\frac{3}{4}-\epsilon}$, which is
linear in $T$. This contradicts Theorem 2, which says that when agnostic
corruption $C=2c_{0}T^{\frac{3}{4}-\epsilon}$, the regret upper bound is
$O(T^{1-\epsilon})$, which is sublinear. To reconcile the conflicts, we must
have Proposition 1 true to make the agnostic corruption
$C\geq\Omega(T^{\frac{3}{4}})$ to make the parallel world argument valid.

###  C.3 Proof for Matching Regret Upper Bound in Theorem 1

In this section, we consider the setting when human has strongly concave
utility function. When $\rho$ is known, we optimally adjusts the learning rate
of the algorithm, Noisy Comparision-based Stochastic Mirror Descent (NC-SMD),
proposed in Kumagai (2017), to achieve a balance between optimizing the
learning objective (1) and controlling the gradient bias arising from the
_corrupted dueling feedback_. Then we show that it attains the matching regret
upper bound of $\tilde{O}(d\max\\{\sqrt{T},T^{\rho}\\})$ under corruption
induced by $\rho$-_imperfect_ user.

For the ease of delivering proof, in this section, we work with the cost
function $f$, opposite of the utility function $\mu$, We restate the modelling
of inaccuracies from human feedback and the learning objective using $f$ as
follows.

######  Assumption C.1.

(Corrupted Utility-Based Dueling Bandit). For a pair of actions
$(a,a^{\prime})\in\mathcal{A}\times\mathcal{A}$ and the corruption level
$c(a,a^{\prime})$, there exists function $f:\mathcal{A}\rightarrow\mathbb{R}$
and $\sigma:\mathbb{R}\rightarrow[0,1]$ such that the probability that $a\succ
a^{\prime}$ happens of receiving _corrupted dueling feedback_ can be
represented follows

$\hat{\mathbb{P}}(a\succ a^{\prime})=\sigma(f(a^{\prime})-f(a)+c(a,a)).$

Additionally, we assume that the cost function $f$, the link function
$\sigma$, and the action space $\mathcal{A}$ exhibit the following properties,
which align precisely with those assumed in Kumagai (2017).

######  Assumption C.2.

The cost function $f:\mathcal{A}\rightarrow\mathbb{R}$ is twice continuously
differentiable, $L$-Lipschitz, $\alpha$-strongly convex and $\beta$-smooth
with respect to the Euclidean norm.

######  Definition C.1.

(Strong Convexity). A function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is
$\alpha$-strongly convex over the set $\mathcal{A}\subset\mathbb{R}^{d}$ if
for all $x,y\in\mathcal{A}$ it holds that

$f(y)\geq f(x)+\nabla f(x)^{\top}(y-x)+\frac{\alpha}{2}\|y-x\|^{2}_{2}.$

######  Definition C.2.

(Smoothness). A function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is
$\beta$-smooth over the set $\mathcal{A}\subset\mathbb{R}^{d}$ if for all
$x,y\in\mathcal{A}$ it holds that

$f(y)\leq f(x)+\nabla f(x)^{\top}(y-x)+\frac{\beta}{2}\|y-x\|^{2}_{2}.$

######  Assumption C.3.

Let $B:=\sup_{a,a^{\prime}\in\mathcal{A}}f(a^{\prime})-f(a)$, $f$ is defined
in Assumption C.2. The link function $\sigma:\mathbb{R}\rightarrow[0,1]$ is
three times differentiable and rotational-symmetric. Its first derivative is
positive and monotonically non-increasing on $[0,B]$.

######  Assumption C.4.

We assume the action space $\mathcal{A}\in\mathbb{R}^{d}$ is convex, compact
and has non-empty interior.

######  Definition C.3.

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

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

Through interactions with the user, the learner $\mathcal{L}$ endeavors to
minimize the dueling regret, as defined below.

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

Our minimization objective in (16) aligns with the regret definition in Yue
and Joachims (2009). Under Assumptions C.1, C.2, and C.3, the regret defined
in (16) is equivalent to the regret defined in Kumagai (2017). Assumption C.2
suggests the existence of a unique minimizer $a^{*}$ for the cost function $f$
due to its strict convexity. Assumptions C.2 and C.4 imply that the diameter
$R:=\sup_{a,a^{\prime}\in\mathcal{A}}|a-a^{\prime}|$ and $B$ are finite.
Assumption C.3 implies the existence of positive constants $l_{0}$, $L_{0}$,
$B_{2}$, and $L_{2}$ such that the first derivative $\sigma^{\prime}$ of the
link function is bounded, satisfying $l_{0}\leq\sigma^{\prime}\leq L_{0}$ on
$[-B,B]$. Furthermore, the second derivative $\sigma^{{}^{\prime\prime}}$ is
bounded above by $B_{2}$ and is $L_{2}$-Lipschitz on $[-B,B]$. Lemma C.7
establishes the relationship between $\text{Reg}^{\text{FO}}_{T}$ and
$\text{Reg}^{\text{DB}}_{T}$.

######  Lemma C.7 (Lemma 12 in Kumagai (2017)).

$\frac{\text{Reg}^{\text{DB}}_{T}}{L_{0}}\leq\text{Reg}^{\text{FO}}_{T}\leq\frac{\text{Reg}^{\text{DB}}_{T}}{l_{0}}.$
(17)

####  C.3.1 Noisy Comparison-based Stochastic Mirror Descent

Input: Learning rate $\eta_{\rho}$, $\nu$-self-concordant function
$\mathcal{R}$, time horizon $T$, tuning parameters $\lambda$, $\mu$.

1 Initialize $a_{1}=\arg\min_{a\in A}\mathcal{R}(a)$

2 for  _$t\in[T]$_ do

3 Update
$\mathcal{R}_{t}(a)=\mathcal{R}(a)+\frac{\lambda\eta_{\rho}}{2}\sum^{t}_{i=1}\|a-a_{i}\|^{2}+\mu\|a\|^{2}$

4 Pick a unit vector $u_{t}$ uniformly at random

5 Receive the corrupted feedback $\hat{\mathcal{F}}(a^{\prime}_{t},a_{t})$,
for $a_{t}$ and
$a^{\prime}_{t}=a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-1/2}u_{t}$

6 Compute the corrupted gradient:
$\hat{g}_{t}=\hat{\mathcal{F}}(a^{\prime}_{t},a_{t})d\nabla^{2}\mathcal{R}_{t}(a_{t})^{1/2}u_{t}$

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

Output : $a_{T+1}$

Algorithm 3 Noisy Comparison-based Stochastic Mirror Descent (NC-SMD)

######  Remark C.1.

Note that
$a^{\prime}_{t}=a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}x$ for
$x\in\mathbb{B}$ is included in $\mathcal{A}$ due to the properties of the
Dikin ellipsoid.

Now we begin to prove the matching regret upper bound in Theorem 1.

######  Proposition C.1 (Full Statement of Matching Regret Upper Bound in
Theorem 1).

Let the number of rounds $T$ be fixed and $T>\sqrt{2LL_{0}R}$. Consider a
corruption induced by $\rho$-_imperfect_ user (Def. 1) with known $\rho$.
Under Assumptions C.2, C.3, and C.4, choose $\lambda\leq l_{0}\alpha/2$,
$\mu\geq(L^{3}_{0}L_{2}/\lambda)^{2}$, and set the learning rate
$\eta_{\rho}:=\frac{\sqrt{\log T}}{dT^{\max\\{1/2,\rho\\}}}$ for Algorithm 3.
We have we have:

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

Proof  (Proof for Proposition C.1). The formal proof of Proposition C.1 relies
on Lemmas C.8, C.9, and C.10. Lemma C.8 establishes a connection between the
gradient estimation corrupted by the bias term $b_{t}$ and the quantity
$\bar{P}_{t}(a)$ (defined in Lemma C.8), which is the main component we aim to
analyze in the regret definition (16). Lemma C.9 decomposes the regret into
two parts: a regret of decision independent of $b_{t}$ and an error in
observation summarizing the cumulative impact of $b_{t}$.

The optimization error can be explicitly upper bounded by $T$ and
$\eta_{\rho}$ using techniques similar to those employed in Kumagai (2017).
The upper bound of the estimation error is further established in Lemma C.10,
wherein we utilize the $\alpha$-strong convexity of $f$ to establish a
connection between the convergence of the $L_{2}$-norm of the action
$\|a_{t}-a^{*}\|_{2}$ to itself.

######  Lemma C.8 (Gradient Estimation under Corruption).

Let $P_{t}(a)$ represent the likelihood of action $a_{t}$ being preferred over
$a$, where $P_{t}(a):=\sigma(f(a)-f(a_{t}))$. Likewise, the corrupted version
is defined as
$\hat{P}_{t}(a)=\sigma(f(a)-f(a_{t})+c_{t}(a_{t},a^{\prime}_{t}))$. The
smoothed version of $P_{t}$ over $\text{int}(\mathcal{A})$ is
$\bar{P}_{t}(a):=\mathbb{E}_{x\in\mathbb{B}}\left[P_{t}(a+\nabla^{2}R_{t}(a_{t})^{-\frac{1}{2}}x)\right]$.
$\mathcal{R}_{t}(a)$ is defined in Algorithm 3. Let
$a^{\prime}_{t}=a_{t}+\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}u_{t}$,
where $u_{t}$ is uniformly sampled from $\mathbb{S}$. Let
$b_{t}:=d\left(P_{t}(a^{\prime}_{t})-\hat{P}_{t}(a^{\prime}_{t})\right)\nabla^{2}\mathcal{R}_{t}(a_{t})^{\frac{1}{2}}u_{t}$,
we have

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

######  Lemma C.9 (Regret Decomposition).

Define $C_{0}:=(2\nu+4L_{0}\beta+4B_{2}L^{2}+LL_{0}\beta)/\lambda$, and let
$a^{*}_{T}=\frac{1}{T}a_{1}+(1-\frac{1}{T})a^{*}$. By Assumption C.3,
executing Algorithm 3, we obtain:

$\displaystyle\text{Reg}^{\text{DB}}_{T}$
$\displaystyle\leq\underbrace{\frac{C_{0}}{\eta_{\rho}}\log(T)+8d^{2}\eta_{\rho}T+2LL_{0}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}Observation\hskip
2.84526ptError}}.$

######  Lemma C.10 (Estimation Error Upper Bound).

Under Assumption C.2, and C.4, we have

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

where we have
$\lambda^{*}_{\mathcal{R}}:=\sup_{a\in\mathcal{A}}\lambda_{\max}\left(\nabla^{2}\mathcal{R}(a)\right)$,
and $m_{t},n_{t},C_{2}$ defined as

$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(f(a_{t})-f(a^{*})\right)}\right),C_{2}:=2L_{\sigma}R\sqrt{\lambda^{*}_{R}+2\mu}.$

Now, we present the proof of Proposition C.1. The key technical innovation
lies in realizing that the upper bound of $\text{Reg}^{\text{DB}}_{T}$
contains itself. This implies that we can initially obtain a rough upper bound
and then refine it until it becomes tight. The proof follows a mathematical
induction argument. For the ease of notation, we reparameterize
$C=C_{\kappa}T^{\rho}$. In the following proof, we consider $\rho>0.5$ to make
$T^{\rho}=\max\\{\sqrt{T},T^{\rho}\\}$. If $\rho\leq 0.5$, the following proof
can be easily modified to make upper bounds involving $T^{\rho}$ as
$\sqrt{T}$.

In the first step, we employ a rough upper bound, specifically
$\mathbb{E}\left(n_{t}\right)\leq 2R$. This yields $\text{Reg}^{DB}_{T}\leq
O(dT^{\frac{\rho+1}{2}})$. Since $\text{Reg}^{DB}_{T}$ and
$\text{Reg}^{\text{FO}}_{T}$ share the same order (see Equation (17)), it
implies that $\sum^{T}_{t=1}\mathbb{E}\left(n_{t}\right)$ must be sublinear as
well. Therefore, in the second step, we can use Abel’s Summation Equation
(Lemma C.16) to refine the upper bound of
$\mathbb{E}\left(\sum^{T}_{t=1}\sqrt{t}m_{t}n_{t}\right)$.

In particular, we rigorously prove the following claim:

The Induction Claim: Given the number of iteration $T$. $T>\sqrt{2LL_{0}R}$.
At k-th step, we have $\text{Reg}^{\text{DB}}_{T}\leq 144dK\sqrt{\log
T}T^{\rho+\frac{\frac{3}{2}-\rho}{2^{k+1}}}$, where
$K:=\max\left\\{C_{0},\frac{C_{2}C_{\kappa}}{\sqrt{\log
T}},L^{2}_{\sigma}C^{2}_{\kappa},2\sqrt{\lambda}RC_{\kappa}L_{\sigma}\right\\}$.

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

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

We get Equation (18) according to Lemma C.9 and C.10. We get Equation (19)
because of $\mathbb{E}\left(n_{t}\right)\leq 2R$. We get Equation (20) by
Abel’s Summation Equation (see Lemma C.16). We get get Equation (21) because
of corruption budget. Choosing the learning rate $\eta_{\rho}$ according to
Proposition C.1, we obtain $\text{Reg}^{\text{DB}}_{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 (17) and the induction claim, we obtain
$\text{Reg}^{\text{FO}}_{T}\leq\frac{144}{l_{0}}dK\sqrt{\log
T}T^{\rho+\frac{3/2-\rho}{2^{k+1}}}.$ This suggests that

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

By Jensen’s inequality, we have

$\mathbb{E}(n_{t})=\min\left\\{2,\sqrt{\frac{2}{\alpha}}\mathbb{E}\left(\sqrt{f(a_{t})-f(a^{*})}\right)\right\\}\leq\sqrt{\frac{2}{\alpha}}\sqrt{\mathbb{E}\left(f(a_{t})-f(a^{*})\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(f(a_{t})-f(a^{*})\right)}.$

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

######  Lemma C.11.

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

Therefore, using Lemma C.11 (details of proof is listed at Appendix C.3.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_{0}}}(\log
T)^{0.25}C_{k}\sqrt{dK}T^{\frac{3}{2}\rho+\frac{3/2-\rho}{2^{k+2}}}$

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

$\displaystyle\text{Reg}^{\text{DB}}_{T}$ $\displaystyle\leq
2d\left(C_{0}+\frac{C_{2}}{\sqrt{\log
T}}+60C_{\kappa}\sqrt{K}T^{\frac{3/2-\rho}{2^{k+2}}}\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+2}}}.$

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}^{\text{DB}}_{T}\leq O\left(d\sqrt{\log T}T^{\rho}\right),$

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

####  C.3.2 Proof for Lemma C.8: Gradient Estimation Under Corruption

Proof  (Proof for Lemma C.8). 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
$f(a^{\prime})-f(a)$), 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}).$

The proof is similar to Lemma 2.1 in Flaxman et al. (2005). 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].$

####  C.3.3 Proof for Lemma C.9: Regret Decomposition

Proof  (Proof for Lemma C.9). The cornerstone of the analysis below is to
separate the impact of $b_{t}$ from the total regret.

$\displaystyle\text{Reg}^{\text{DB}}_{T}\leq
2\mathbb{E}\left[\sum^{T}_{t=1}(P_{t}(a_{t})-P_{t}(a^{*}_{T})\right]+\frac{LL_{0}\beta}{\lambda\eta}+2LL_{0}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{LL_{0}\beta}{\lambda\eta}+2LL_{0}R$ $\displaystyle\leq
2\mathbb{E}\left\\{\sum^{T}_{t=1}(\bar{P}_{t}(a_{t})-\bar{P}_{t}(a^{*}_{T}))\right\\}+\frac{4L_{0}\beta+4B_{2}L^{2}+LL_{0}\beta}{\lambda\eta_{\rho}}\log
T+2LL_{0}R.$

We get the first inequality by using Lemma C.12. We get the last inequality by
because

$\bar{P}_{t}(a)-P_{t}(a)\leq\frac{L_{0}\beta+B_{2}L^{2}}{2}\|\nabla^{2}\mathcal{R}_{t}(a_{t})^{-\frac{1}{2}}u_{t}\|^{2}\leq\frac{L_{0}\beta+B_{2}L^{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_{0}\beta+B_{2}L^{2}}{\lambda\eta_{\rho}}\log
T.$

######  Lemma C.12 (Lemma 5 in Kumagai (2017)).

$\text{Reg}^{\text{DB}}_{T}\leq
2\mathbb{E}\left[\sum^{T}_{t=1}(P_{t}(a_{t})-P_{t}(a^{*}_{T})\right]+\frac{LL_{0}\beta}{\lambda\eta}+2LL_{0}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_{0}\alpha}{4}\|a_{t}-a^{*}_{T}\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[g_{t}^{\top}(a_{t}-a^{*}_{T})-\frac{l_{0}\alpha}{4}\|a_{t}-a^{*}_{T}\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[(\hat{g}_{t}+b_{t})^{\top}(a_{t}-a^{*}_{T})-\frac{l_{0}\alpha}{4}\|a_{t}-a^{*}_{T}\|^{2}\right]$
$\displaystyle=\mathbb{E}\left[\hat{g}_{t}^{\top}(a_{t}-a^{*}_{T})-\frac{l_{0}\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 C.8. Using the
definition of $a_{t+1}$ in Algorithm 3, 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_{0}\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_{0}\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_{0}\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 Equation (22) by using Lemma C.13, C.14, C.15.

$\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})\\}.$
(22)

######  Lemma C.13 (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_{0}\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 C.14 (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}.$

######  Lemma C.15 (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_{0}\beta+4B_{2}L^{2}+LL_{0}\beta)/\lambda$, we have

$\displaystyle\text{Reg}^{\text{DB}}_{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_{0}\beta+4B_{2}L^{2}+LL_{0}\beta}{\lambda\eta_{\rho}}\log
T+2LL_{0}R$
$\displaystyle=\underbrace{\frac{C_{0}}{\eta_{\rho}}\log(T)+8d^{2}\eta_{\rho}T+2LL_{0}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}Observation\hskip
2.84526ptError}},$

which completes the proof.

####  C.3.4 Proof for Lemma C.10: Observation Error

Proof  (Proof for Lemma C.10) 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-Schwarz 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 C.8. 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$ (see Assumption C.3) 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\mu\leq\lambda^{*}_{R}+2\mu+\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\mu+\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\mu}\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\mu}C+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\\}$
(23) $\displaystyle\leq
2RdL_{\sigma}\sqrt{\lambda^{*}_{R}+2\mu}C+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\\}$
(24) $\displaystyle\leq
2RdL_{\sigma}\sqrt{\lambda^{*}_{R}+2\mu}C+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)\min\left(2R,\sqrt{\frac{2}{\alpha}\left(f(a_{t})-f(a^{*})\right)}\right)\right\\}.$

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

####  C.3.5 Proof for Lemma C.11

Proof  (Proof for Lemma C.11). Using Abel’s Summation Equation (Lemma C.16),
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-\frac{1}{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^{-\frac{1}{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^{-\frac{1}{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 C.16.

(Abel’s Summation Equation (Williams, 1963)). 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}).$

###  C.4 Proof for Proposition 2: Efficiency-Robustness Tradeoff in NC-SMD

######  Theorem (Full Statement of Proposition 2).

Let the number of rounds $T$ be fixed and $T>\sqrt{2LL_{0}R}$. Under
Assumptions C.2, C.3, and C.4, by choosing $\lambda\leq l_{0}\alpha/2$,
$\mu\geq(L^{3}_{0}L_{2}/\lambda)^{2}$, and setting the learning parameter
$\eta_{\rho}=\frac{\sqrt{\log T}}{2d}T^{-\alpha},\alpha\in[0.5,1]$, regret
occurred by Algorithm 3 satisfies

$\text{Reg}_{T}\leq\tilde{O}\left(dT^{\alpha}+\sqrt{d}T^{\frac{1}{2}(1-\alpha)}C+dC\right)$

for any corruption with budget $C$.

Proof  (Proof for Proposition 2). From Lemma C.10, 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\mu}C+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\mu}C+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\mu}C+2Rd\sqrt{\lambda\eta_{\rho}T}L_{\sigma}C.$

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 C.16). Therefore, by Lemma C.9, we have

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

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}+4RdL_{\sigma}\sqrt{\lambda^{*}_{R}+2\mu}C+4R\sqrt{d}L_{\sigma}(\log