# Efficient Action Poisoning Attacks on Linear Contextual Bandits

Guanlin Liu, Lifeng Lai
Department of ECE, University of California, Davis
<EMAIL_ADDRESS>
###### Abstract

Contextual bandit algorithms have many applicants in a variety of scenarios.
In order to develop trustworthy contextual bandit systems, understanding the
impacts of various adversarial attacks on contextual bandit algorithms is
essential. In this paper, we propose a new class of attacks: action poisoning
attacks, where an adversary can change the action signal selected by the
agent. We design action poisoning attack schemes against linear contextual
bandit algorithms in both white-box and black-box settings. We further analyze
the cost of the proposed attack strategies for a very popular and widely used
bandit algorithm: LinUCB. We show that, in both white-box and black-box
settings, the proposed attack schemes can force the LinUCB agent to pull a
target arm very frequently by spending only logarithm cost.

##  1 Introduction

Multiple armed bandits (MABs), a popular framework of sequential decision
making model, has been widely investigated and has many applicants in a
variety of scenarios [1, 2, 3]. The contextual bandits model is an extension
of the multi-armed bandits model with contextual information. At each round,
the reward is associated with both the arm (a.k.a, action) and the context,
while the reward of stochastic MABs is only associated with the arm.
Contextual bandits algorithms have a broad range of applications, such as
recommender systems [4], wireless networks [5], etc.

In the modern industry-scale applications of bandit algorithms, action
decisions, reward signal collection, and policy iterations are normally
implemented in a distributed network. Action decisions and reward signals may
need to be transmitted over communication links. When data packets containing
the reward signals and action decisions etc are transmitted through the
network, the adversary can implement adversarial attacks by intercepting and
modifying these data packets. As the result, poisoning attacks on contextual
bandits could possibly happen. In many applications of contextual bandits, an
adversary may have an incentive to force the contextual bandits system to
learn a specific policy. For example, a restaurant may attack the bandit
systems to force the systems into increasing the restaurant’s exposure. Thus,
understanding the risks of different kinds of adversarial attacks on
contextual bandits is essential for the safe applications of the contextual
bandit model and designing robust contextual bandit systems.

While there are many existing works addressing adversarial attacks on
supervised learning models [6, 7, 8, 9, 10, 11, 12], the understanding of
adversarial attacks on contextual bandit models is less complete. Of
particular relevance to our work is a line of interesting recent work on
adversarial attacks on MABs [13, 14, 15] and on linear contextual bandits [16,
17]. In recent works in MABs setting, the types of attacks include both reward
poisoning attacks and action poisoning attacks. In the reward poisoning
attacks, there is an adversary who can manipulate the reward signal received
by the agent [13, 14]. In the action poisoning attacks, the adversary can
manipulate the action signal chosen by the agent before the environment
receives it [15]. Among existing works on adversarial attacks against linear
contextual bandits, they focus on the reward poisoning [16, 17] or context
poisoning attacks [17]. In the context poisoning attacks, the adversary can
modify the context observed by the agent without changing the reward
associated with the context. There are also some recent interesting work on
adversarial attacks against reinforcement learning algorithms under various
setting [18, 19, 20, 21, 22, 23, 24, 25].

In this paper, we aim to investigate the impact of action poisoning attacks on
contextual bandit models. To our best knowledge, this paper is the first work
to analyze the impact of action poisoning attacks on contextual bandit models.
More detailed comparisons of various types of attacks against contextual
bandits will be provided in Section 3. We note that the goal of this paper is
not to promote any particular type of poisoning attack. Rather, our goal is to
understand the potential risks of action poisoning attacks. We note that for
the safe applications and design of robust contextual bandit algorithms, it is
essential to address all possible weaknesses of the models and understanding
the risks of different kinds of adversarial attacks. Since the action
poisoning attack is an important aspect of poisoning attacks and may threaten
the bandit systems, it is important to understand the potential risks of
action poisoning attacks.

In this paper, we study the action poisoning attack against linear contextual
bandit in both white-box and black-box settings. In the white-box setting, we
assume that the attacker knows the coefficient vectors associated with arms.
Thus, at each round, the attacker knows the mean rewards of all arms. While it
is often unrealistic to exactly know the coefficient vectors, the
understanding of the white-box attacks could provide valuable insights on how
to design the more practical black-box attacks. In the black-box setting, we
assume that the attacker has no prior information about the arms and does not
know the agent’s algorithm. The limited information that the attacker has are
the context information, the action signal chosen by the agent, and the reward
signal generated from the environment. In both white-box and black-box
settings, the attacker aims to manipulate the agent into frequently pulling a
target arm chosen by the attacker with a minimum cost. The cost is measured by
the number of rounds that the attacker changes the actions selected by the
agent. The contributions of this paper are:

  * •

We propose a new online action poisoning attack against contextual bandit in
which the attacker aims to force the agent to frequently pull a target arm
chosen by the attacker via strategically changing the agent’s actions.

  * •

We introduce a white-box attack strategy that can manipulate any sublinear-
regret linear contextual bandit agent into pulling a target arm $T-o(T)$
rounds over a horizon of $T$ rounds, while incurring a cost that is sublinear
dependent on $T$.

  * •

We design a black-box attack strategy whose performance nearly matches that of
the white-box attack strategy. We apply the black-box attack strategy against
a very popular and widely used bandit algorithm: LinUCB. We show that our
proposed attack scheme can force the LinUCB agent into pulling a target arm
$T-O(\log^{3}T)$ times with attack cost scaling as $O(\log^{3}T)$.

  * •

We evaluate our attack strategies using both synthetic and real-world
datasets. We observe empirically that the total cost of our black-box attack
is sublinear for a variety of contextual bandit algorithms.

##  2 Related Work

In this section, we discuss related works on two parts: adversarial attacks
that cause standard bandit algorithms to fail and robust bandit algorithms
that can defend against such attacks.

Attacks Models. In MABs setting, [13] proposes an interesting reward poisoning
attack strategy that can force $\epsilon$-Greedy or upper confidence bound
(UCB) agent to select a target arm while only spending logarithmic effort. The
main idea of the attack scheme in [13] is to modify the reward signals
associated with non-target arms to smaller values. As the agent only observes
the modified reward signals, the target arm appears to the optimal arm for the
agent. [14] proposes an optimization based framework for offline reward
poisoning attacks on MABs. Furthermore, it studies the online attacks on MABs,
and proposes an adaptive attack strategy that is effective in attacking any
bandit algorithm without knowing what particular algorithm the agent is using.
[15] proposes an adaptive action poisoning attack strategy that can force the
UCB agent to pull a target arm $T-O(\log T)$ times over $T$ rounds while the
total attack cost being only $O(\log T)$.

In linear contextual bandit setting, [16] studies offline reward poisoning
attacks and investigates the feasibility and the impacts of such attacks. The
attacker in [16] aims to force the agent to pull a target arm on a particular
context. [17] extends the attack idea of [13, 14] to linear contextual
bandits. It proves that the proposed reward poisoning attack strategy can
force any bandit algorithms to pull a specific set of arms when the rewards
are bounded. It introduces an adaptive reward poisoning attack strategy and
observes empirically that the total cost of the adaptive attack is sublinear.
In addition, [17] analyzes the context poisoning attacks in white-box setting
and shows that LinUCB is vulnerable to such attack. In the filed of
adversarial attacks on RL, [25] studies black-box action poisoning attacks
against RL.

Robust algorithms. Lots of efforts have been made to design robust bandit
algorithms to defend adversarial attacks. In the MABs setting, [26] introduces
a bandit algorithm, called Multilayer Active Arm Elimination Race algorithm,
that is robust to reward poisoning attacks by using a multi-layer approach.
[27] presents an algorithm named BARBAR that is robust to reward poisoning
attacks and the regret of the proposed algorithm is nearly optimal. [28]
considers a reward poisoning attack model where an adversary attacks with a
certain probability at each round. As its attack value at each round can be
arbitrary and unbounded, the attack model could be powerful. The paper
proposes algorithms that are robust to these types of attacks. [29] introduces
a reward poisoning attack setting where each arm can only manipulate its own
reward. Every arm can be considered as an adversary and each arm seeks to
maximize its own expected number of pull count. Under this setting, [29]
proves that Thompson Sampling, UCB, and $\epsilon$-greedy can be modified to
be robust to such attacks.[30] introduce a bandit algorithm, called MOUCB,
that is robust to action poisoning attacks and achieves a regret upper bound
that increases over rounds in a logarithmic order or increases with attack
cost in a linear order.

In the linear contextual bandit setting, [31] proposes a stochastic linear
bandit algorithm, called Robust Phased Elimination (RPE), that is robust to
reward poisoning attacks. It provides two variants of RPE algorithm which
separately work on known attack budget case and agnostic attack budget case.
[32] provides a robust linear contextual bandit algorithm, called
RobustBandit, that works under both the reward poisoning attacks and context
poisoning attacks.

##  3  Problem Setup

Consider the standard contextual linear bandit model in which the environment
consists of $K$ arms. In each round $t=1,2,3,\dots,T$, the agent observes a
context $x_{t}\in\mathbb{R}^{d}$, pulls an arm $I_{t}$ and receives a reward
$r_{t,I_{t}}$. Each arm $i$ is associated with an unknown but fixed
coefficient vector $\theta_{i}\in\mathbb{R}^{d}$. In each round $t$, the
reward is

$r_{t,I_{t}}=\langle x_{t},\theta_{I_{t}}\rangle+\eta_{t},$

where $\eta_{t}$ is a conditionally independent zero-mean $R$-subgaussian
noise and $\langle\cdot,\cdot\rangle$ denotes the inner product. Hence, the
expected reward of arm $i$ under context $x_{t}$ follows the linear setting:

$\mathbb{E}[r_{t,i}]=\langle x_{t},\theta_{i}\rangle$ (1)

for all $t$ and all arm $i$. If we consider the $\sigma$-algebra
$F_{t}=\sigma(x_{1},\dots,x_{t+1},\eta_{1},\dots,\eta_{t})$, $x_{t}$ becomes
$F_{t-1}$ measurable and $\eta_{t}$ becomes $F_{t}$ measurable.

In this paper, we assume that there exist $L>0$ and $S>0$, such that for all
round $t$ and arm $i$, $\|x_{t}\|_{2}\leq L$ and $\|\theta_{i}\|_{2}\leq S$,
where $\|\cdot\|_{2}$ denotes the $\ell_{2}$-norm. We assume that there exist
$\mathcal{D}\subset\mathbb{R}^{d}$ such that for all $t$,
$x_{t}\in\mathcal{D}$ and, for all $x\in\mathcal{D}$ and all arm $i$, $\langle
x,\theta_{i}\rangle>0$.

The agent is interested in minimizing the cumulative pseudo-regret

$\bar{R}_{T}=\sum_{t=1}^{T}\left(\langle
x_{t},\theta_{I_{t}^{*}}\rangle-\langle x_{t},\theta_{I_{t}}\rangle\right),$
(2)

where $I_{t}^{*}=\arg\max_{i}\langle x_{t},\theta_{i}\rangle$.

In this paper, we introduce a novel adversary setting, in which the attacker
can manipulate the action chosen by the agent. In particular, at each round
$t$, after the agent chooses an arm $I_{t}$, the attacker can manipulate the
agent’s action by changing $I_{t}$ to another $I_{t}^{0}\in\\{1,\dots,K\\}$.
If the attacker decides not to attack, $I_{t}^{0}=I_{t}$. The environment
generates a random reward $r_{t,I_{t}^{0}}$ based on the post-attack arm
$I_{t}^{0}$ and the context $x_{t}$. Then the agent and the attacker receive
reward $r_{t,I_{t}^{0}}$ from the environment. Since the agent does not know
the attacker’s manipulations and the presence of the attacker, the agent will
still view $r_{t,I_{t}^{0}}$ as the reward corresponding to the arm $I_{t}$.

The goal of the attacker is to design an attack strategy so as to manipulate
the agent into pulling a target arm very frequently but by making attacks as
rarely as possible. Without loss of generality and for notation convenience,
we assume arm $K$ is the “attack target” arm or target arm. Define the set of
rounds when the attacker decides to attack as $\mathcal{C}:=\\{t:t\leq
T,I_{t}^{0}\not=I_{t}\\}$. The cumulative attack cost is the total number of
rounds where the attacker decides to attack, i.e., $|\mathcal{C}|$. The
attacker can monitor the contexts, the actions of the agent and the reward
signals from the environment.

We now compare the three types of poisoning attacks against contextual linear
bandit: reward poisoning attack, action poisoning attack and context poisoning
attack. In the reward poisoning attack [16, 17], after the agent observes
context $x_{t}$ and chooses arm $I_{t}$, the environment will generate reward
$r_{t,I_{t}}$ based on context $x_{t}$ and arm $I_{t}$. Then, the attacker can
change the reward $r_{t,I_{t}}$ to $\widetilde{r}_{t}$ and feed
$\widetilde{r}_{t}$ to the agent. Compared with the reward poisoning attacks,
the action poisoning attack considered in this paper is more difficult to
carry out. In particular, as the action poisoning attack only changes the
action, it can impact but does not have direct control of the reward signal.
By changing the action $I_{t}$ to $I_{t}^{0}$, the reward received by the
agent is changed from $r_{t,I_{t}}$ to $r_{t,I_{t}^{0}}$ which is a random
variable drawn from a distribution based on the action $I_{t}^{0}$ and context
$x_{t}$. This is in contrast to reward poisoning attacks where an attacker has
direct control and can change the reward signal to any value
$\widetilde{r}_{t}$ of his choice. In the context poisoning attack [17], the
attacker only changes the context shown to the agent. The reward is also
generated based on the true context $x_{t}$ and the agent’s action $I_{t}$.
Nevertheless, the agent’s action may be indirectly impacted by the
manipulation of the context, and so as the reward. Since the attacker attacks
before the agent pulls an arm, the context poisoning attack is the most
difficult to carry out. As mentioned in the introduction, the goal of this
paper is not to promote any particular types of poisoning attacks. Instead,
our goal is to understand the potential risks of action poisoning attacks, as
the safe applications and design of robust contextual bandit algorithm relies
on the addressing all possible weakness of the models.

As the action poisoning attack only changes the actions, it can impact but
does not have direct control of the agent’s observations. Furthermore, when
the action space is discrete and finite, the ability of the action poisoning
attacker is severely limited. It is reasonable to limit the choice of the
target policy. Here we introduce an important assumption that the target arm
is not the worst arm:

######  Assumption 1.

For all $x\in\mathcal{D}$, $\langle x,\theta_{K}\rangle>\min_{i\in[K]}\langle
x,\theta_{i}\rangle$.

If the target arm is the worst arm in most contexts, the attacker should
change the target arm to a better arm or the optimal arm so that the agent
learns that the target set is optimal for almost every context. In this case,
the cost of attack may be up to $O(T)$. Assumption 1 does not imply that the
target arm is optimal at some contexts. The target arm could be sub-optimal
for all contexts. Fig. 1 shows an example of one dimension linear contextual
bandit model, where the $x$-axis represents the contexts and the $y$-axis
represents the mean rewards of arms under different contexts. As shown in Fig.
1, the arm 3 and arm 4 satisfy the assumption 1. In addition, the arm 3 is not
optimal at any context.

Figure 1: An example of one dimension linear contextual bandit model.

Under assumption 1, there exists $\alpha\in(0,\frac{1}{2})$ such that
$\max_{x\in\mathcal{D}}\frac{\min_{i}\langle x,\theta_{i}\rangle}{\langle
x,\theta_{K}\rangle}\leq(1-2\alpha)$. Equivalently, Assumption 1 implies that
there exists $\alpha\in(0,\frac{1}{2})$, such that for all $t$, we have

$(1-2\alpha)\langle x_{t},\theta_{K}\rangle\geq\min_{i\in[K]}\langle
x_{t},\theta_{i}\rangle.$ (3)

##  4 Attack Schemes and Cost Analysis

In this section, we introduce action poisoning attack schemes in the white-box
setting and black-box setting respectively. In order to demonstrate the
significant security threat of action poisoning attacks to linear contextual
bandits, we investigate our action poisoning attack strategy against a widely
used algorithm: LinUCB algorithm. Furthermore, we analyze the attack cost of
our action poisoning attack schemes.

###  4.1 Overview of LinUCB

For reader’s convenience, we first provide a brief overview of the LinUCB
algorithm [4]. The LinUCB algorithm is summarized in Algorithm 1. The main
steps of LinUCB are to obtain estimates of the unknown parameters $\theta_{i}$
using past observations and then make decisions based on these estimates.
Define $\tau_{i}(t):=\\{s:s\leq t,I_{s}=i\\}$ as the set of rounds up to $t$
where the agent pulls arm $i$. Let $N_{i}(t)=|\tau_{i}(t)|$. Then, at round
$t$, the $\ell_{2}$-regularized least-squares estimate of $\theta_{i}$ with
regularization parameter $\lambda>0$ is obtained by [4]

$\hat{\theta}_{t,i}=V_{t,i}^{-1}\left(\sum_{k\in\tau_{i}(t-1)}r_{t,i}x_{k}\right),$
(4)

where $V_{t,i}=\sum_{k\in\tau_{i}(t-1)}x_{k}x_{k}^{T}+\lambda\mathbf{I}$ with
$\mathbf{I}$ being identity matrix.

After $\hat{\theta}_{i}$’s are obtained, at each round, an upper confidence
bound of the mean reward has to be calculated for each arm (step 5 of
Algorithm 1). Then, the LinUCB algorithm picks the arm with the largest upper
confidence bound (step 7 of Algorithm 1). By following the setup in ”optimism
in the face of uncertainty linear algorithm” (OFUL) [33], we set

$\beta_{t,i}=\sqrt{\lambda}S+R\sqrt{2\log
K/\delta+d\log\left(1+L^{2}N_{i}(t)/(\lambda d)\right)}.$ (5)

We define $\omega(N)=\sqrt{\lambda}S+R\sqrt{2\log
K/\delta+d\log\left(1+L^{2}N/(\lambda d)\right)}$. It is easy to verify that
$\omega(N)$ is a monotonically increasing function over $N\in(0,+\infty)$.

Algorithm 1 Contextual LinUCB [4]

0: regularization $\lambda$, number of arms $K$, number of rounds $T$, bound
on context norms $L$, bound on parameter norms $S$.

1: Initialize for every arm $i$, $V_{i}\leftarrow\lambda\mathbf{I}$,
$b_{i}\leftarrow\textbf{0}$, $\hat{\theta}_{i}\leftarrow V_{i}^{-1}b_{i}$.

2: for $t=1,2,\dots,T$ do

3: observe the context $x_{t}$.

4: for $i=1,2,\dots,K$ do

5: Compute the upper confidence bound: $p_{t,i}\leftarrow
x_{t}^{T}\hat{\theta}_{i}+\beta_{t,i}\sqrt{x_{t}^{T}V_{i}^{-1}x_{t}}$.

6: end for

7: Pull arm $I_{t}=\arg\max_{i}p_{t,i}$.

8: The environment generates reward $r_{t}$ according to arm $I_{t}$.

9: The agent receive $r_{t}$.

10: $V_{i}\leftarrow V_{i}+x_{t}x_{t}^{T}$, $b_{i}\leftarrow
b_{i}+r_{t}x_{t}$, $\hat{\theta}_{i}\leftarrow V_{i}^{-1}b_{i}$.

11: end for

###  4.2 White-box Attack

We first consider the white-box attack scenario, in which the attacker has
knowledge of the environment. In particular, in the white-box attack scenario,
the attacker knows the coefficient vectors $\theta_{i}$’s for all $i$. The
understanding of this scenario could provide useful insights for the more
practical black-box attack scenario to be discussed in Section 4.3.

The proposed attack strategy works as follows. When the agent chooses arm $K$,
the attacker does not attack. When the agent chooses arm $I_{t}\neq K$, the
attacker changes it to arm

$I_{t}^{0}=\left\\{\begin{aligned} &K&&\text{with
probability}&&\epsilon_{t}\\\ &I_{t}^{\dagger}&&\text{with
probability}&&1-\epsilon_{t}\end{aligned}\right.$ (6)

where $I_{t}^{\dagger}=\arg\min_{i}\langle x_{t},\theta_{i}\rangle$ and

$\epsilon_{t}=\frac{(1-\alpha)\langle x_{t},\theta_{K}\rangle-\min_{i}\langle
x_{t},\theta_{i}\rangle}{\langle x_{t},\theta_{K}\rangle-\min_{i}\langle
x_{t},\theta_{i}\rangle}.$ (7)

We now explain the main idea behind the attack strategy specified in (6) and
(7). Intuitively speaking, using (6) and (7), the attacker can manipulate the
agent into learning some particular coefficient vectors. In particular, for
arm $K$ (the target arm), the agent obtains the true coefficient vector
$\theta_{K}$. For any arm $i\neq K$, because of the attacks, the agent will
obtain an estimate of arm $i$’s coefficient vector to be close to
$(1-\alpha)\theta_{K}$. This can be seen as follows. Under Assumption 1 and
the fact that the mean rewards are positive, we have that
$1/2<\epsilon_{t}<1-\alpha$. Under the white-box attack, when the agent pulls
a non-target arm $I_{t}\neq K$, the mean reward received by the agent should
satisfy

$\displaystyle\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]$
$\displaystyle=\mathbb{E}[\langle
x_{t},\theta_{I_{t}^{0}}\rangle|F_{t-1},I_{t}]$ (8)
$\displaystyle=\epsilon_{t}\langle
x_{t},\theta_{K}\rangle+(1-\epsilon_{t})\min_{i}\langle
x_{t},\theta_{i}\rangle$ $\displaystyle=(1-\alpha)\langle
x_{t},\theta_{K}\rangle.$

Because of the positive mean reward assumption and the fact that
$0<1-\alpha<1$, the target arm $K$ appears to be the optimal arm for any
context. Hence the proposed white-box attack strategy can easily mislead an
agent who employs a contextual bandit algorithm with sublinear pseudo-regret,
as shown in the following proposition whose proof can be found in Appendix A
of the supplementary material.

######  Proposition 1.

For $\delta>0$. Suppose the agent employs a contextual bandit algorithm whose
cumulative pseudo-regret is upper bounded by $o(T)$ over $T$ with probability
$1-\delta$. When using the proposed white-box attack scheme, with probability
$1-\delta$, the attacker can force the agent to pull the target arm for
$T-o(T)$ times, while the total attack cost $|\mathcal{C}|$ is upper bounded
by $o(T)$.

Proposition 1 applies to any contextual bandit algorithm whose cumulative
pseudo-regret is upper bounded by $o(T)$. To further illustrate the proposed
attack scheme, we now provide a finer analysis the impact of this attack on
LinUCB described in Algorithm 1. We first build a high probability bound for
the estimate of parameter at the agent, when the agent computes the estimate
of $\theta_{i}$ by (4) and the attacker employs the white-box attack. Recall
that $\omega(N)=\sqrt{\lambda}S+R\sqrt{2\log
K/\delta+d\log\left(1+L^{2}N/(\lambda d)\right)}$.

######  Lemma 1.

Under the proposed white-box attack, the estimate of $\theta_{i}$ for each arm
$i$ obtained by LinUCB agent as described in Algorithm 1 satisfies

$\displaystyle|x_{t}^{T}\hat{\theta}_{t,i}-x_{t}^{T}(1-\alpha)\theta_{K}|\leq\left(\omega(N_{i}(t))+LS\sqrt{0.5\log\left(2KT/\delta\right)}\right)\|x_{t}\|_{V_{t,i}^{-1}},$
(9)

with probability $1-2(K-1)\delta/K$, for all arm $i\neq K$ and all $t\geq 0$.
Here, $\|x\|_{V}=\sqrt{x^{T}Vx}$ is the weighted norm of vector $x$ for a
positive definite matrix $V$.

The proof of Lemma 1 is provided in Appendix B of the supplementary material.
Lemma 1 shows that, under our white-box attack, the agent’s estimate of the
parameter of non-target arm, i.e. $\hat{\theta}_{i}$, will converge to
$(1-\alpha)\theta_{K}$. Thus, the agent is misled to believe that arm $K$ is
the optimal arm for every context in most rounds. The following theorem
provides an upper bound of the cumulative cost of the attack.

######  Theorem 1.

Define $\gamma=\min_{x\in\mathcal{D}}\langle x,\theta_{K}\rangle$. Under the
same assumptions as in Lemma 1, for any $\delta>0$ with probability at least
$1-2\delta$, for all $T\geq 0$, the attacker can manipulate the LinUCB agent
into pulling the target arm in at least $T-|\mathcal{C}|$ rounds, using an
attack cost

$\displaystyle|\mathcal{C}|\leq\frac{2d(K-1)}{(\alpha\gamma)^{2}}\log\left(1+TL^{2}/(d\lambda)\right)\left(2\omega(T)+LS\sqrt{0.5\log\left(2KT/\delta\right)}\right)^{2}.$
(10)

The proof of Theorem 1 is provided in Appendix C of the supplementary
material. Theorem 1 shows that our white-box attack strategy can successfully
force LinUCB agent into pulling the target arm $T-O(\log^{2}T)$ times with
attack cost scaled only as $O(\log^{2}T)$.

###  4.3 Black-box Attack

We now focus on the more practical black-box setting, in which the attacker
does not know any of arm’s coefficient vector. The attacker knows the value of
$\alpha$ (or a lower bound) in which the equation (3) holds for all $t$.
Although the attacker does not know the coefficient vectors for all arms, the
attacker can compute an estimate of the unknown parameters by using past
observations. On the other hand, there are multiple challenges brought by the
estimation errors that need to properly addressed.

The proposed black-box attack strategy works as follows. When the agent
chooses arm $K$, the attacker does not attack. When the agent chooses arm
$I_{t}\neq K$, the attacker changes it to arm

$I_{t}^{0}=\left\\{\begin{aligned} &K&&\text{with
probability}&&\epsilon_{t}\\\ &I_{t}^{{\dagger}}&&\text{with
probability}&&1-\epsilon_{t}\end{aligned}\right.$ (11)

where

$I_{t}^{{\dagger}}=\arg\min_{i\neq K}\left(\langle
x_{t},\hat{\theta}_{t,i}^{0}\rangle-\beta_{t,i}^{0}\|x_{t}\|_{(V_{t,i}^{0})^{-1}}\right),$
(12)

and

$\displaystyle\beta_{t,i}^{0}=\phi_{i}\left(\omega(N_{i}^{{\dagger}}(t))+LS\sqrt{0.5\log\left(2KT/\delta\right)}\right),$
(13)

$\phi_{i}=1/\alpha$ when $i\neq K$ and $\phi_{K}=2$, and

$\displaystyle\epsilon_{t}=\text{clip}\left(\frac{1}{2},\frac{(1-\alpha)\langle
x_{t},\hat{\theta}_{t,K}^{0}\rangle-\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle}{\langle
x_{t},\hat{\theta}_{t,K}^{0}\rangle-\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle},1-\alpha\right),$ (14)

with $\text{clip}(a,x,b)=\min(b,\max(x,a))$ where $a\leq b$.

For notational convenience, we set $I_{t}^{{\dagger}}=K$ and $\epsilon_{t}=1$
when $I_{t}=K$. We define that, if $i\neq K$,
$\tau_{i}^{{\dagger}}(t):=\\{s:s\leq t,I_{s}^{{\dagger}}=i\\}$ and
$N_{i}^{{\dagger}}(t)=|\tau_{i}^{{\dagger}}(t)|$ ;
$\tau_{K}^{{\dagger}}(t):=\\{s:s\leq t\\}$ and
$N_{K}^{{\dagger}}(t)=|\tau_{K}^{{\dagger}}(t)|$.

$\hat{\theta}_{t,i}^{0}=\left(V_{t,i}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}w_{k,i}r_{k,I_{k}^{0}}x_{k}\right),$
(15)

where
$V_{t,i}^{0}=\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}x_{k}x_{k}^{T}+\lambda\mathbf{I}$
and

$w_{t,i}=\left\\{\begin{aligned} &1/\epsilon_{t}&&\text{if}~{}i=I_{t}^{0}=K\\\
&1/(1-\epsilon_{t})&&\text{if}~{}i=I_{t}^{0}=I_{t}^{{\dagger}}\\\
&0&&\text{if}~{}i\neq I_{t}^{0}\end{aligned}\right..$ (16)

Here, $\hat{\theta}_{t,i}^{0}$ is the estimation of $\theta_{i}$ by the
attacker, while $\hat{\theta}_{t,i}$ in (4) is the estimation of $\theta_{i}$
at the agent side. We will show in Lemma 2 and Lemma 4 that
$\hat{\theta}_{t,i}^{0}$ will be close to the true value of $\theta_{i}$ while
$\hat{\theta}_{t,i}$ will be close to a sub-optimal value chosen by the
attacker. This disparity gives the attacker the advantage and foundation for
carrying out the attack.

We now highlight the main idea why our black-box attack strategy works. As
discussed in Section 4.2, if the attacker knows the coefficient vectors of all
arms, the proposed white-box attack scheme can mislead the agent to believe
that the coefficient vector of every non-target arm is $(1-\alpha)\theta_{K}$,
hence the agent will think the target arm is optimal. In the black-box
setting, the attacker does not know the coefficient vector for any arm. The
attacker should estimate the coefficient vector of each arm. Then, the
attacker will use the estimated coefficient vector to replace the true
coefficient vector in the white-box attack scheme. As the attacker does not
know the true values of $\theta_{i}$’s, we need to design the estimator
$\hat{\theta}_{t,i}^{0}$, the attack choice $I_{t}^{{\dagger}}$ and the
probability $\epsilon_{t}$ carefully. In the following, we explain the main
ideas behind our design choices.

Firstly, we explain why we design estimator $\hat{\theta}_{t,i}^{0}$ using the
form (15), in which the attacker employs the importance sampling to obtain an
estimate of $\theta_{i}$. There are two reasons for this. Firstly, for a
successful attack, the number of observation in arm $i\neq K$ will be limited.
Hence if the importance sampling is not used, the estimation variance of the
mean reward $\langle x,\theta_{i}\rangle$ at the attacker side for some
contexts $x$ may be large. Secondly, the attacker’s action is stochastic when
the agent pulls a non-target arm. Thus, the attacker uses the observations at
round $t$ when the attacker pulls arm $i$ with certain probability, i.e. when
$t\in\tau_{i}^{{\dagger}}$, to estimate $\theta_{i}$. At the agent side, since
the agent’s action is deterministic, the agent uses the observations at round
$t$ when the agent pulls arm $i$, i.e. when $t\in\tau_{i}$, to estimate
$\theta_{i}$.

Secondly, we explain ideas behind the choice of $I_{t}^{{\dagger}}$ in (12).
Under our black-box attack, when the agent pulls a non-target arm $I_{t}\neq
K$, the mean reward received by the agent satisfies

$\displaystyle\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]$
$\displaystyle=\mathbb{E}[\langle
x_{t},\theta_{I_{t}^{0}}\rangle|F_{t-1},I_{t}]$ (17)
$\displaystyle=\epsilon_{t}\langle
x_{t},\theta_{K}\rangle+(1-\epsilon_{t})\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle.$

In our white-box attack scheme, $I_{t}^{\dagger}$ is the worst arm at context
$x_{t}$. In the black-box setting, the attack does not know a prior which arm
is the worst. In the proposed black-box attack scheme, as indicated in (12),
we use the lower confidence bound (LCB) method to explore the worst arm and
$I_{t}^{\dagger}$ is the arm whose lower confidence bound is the smallest.

Finally, we provide reasons why we choose $\epsilon_{t}$ using (14). In our
white-box attack scheme, we have that $1/2<\epsilon_{t}<1-\alpha$. Thus, in
our black-box attack scheme, we limit the choice of $\epsilon_{t}$ to
$[1/2,1-\alpha]$. Furthermore, in (7) used for the white-box attack,
$\epsilon_{t}$ is computed by the true mean reward. Now, in the black-box
attack, as the attacker does not the true coefficient vector, the attacker use
the estimation of $\theta$ to compute the second term in the clip function in
(14).

In summary, intuitively speaking, our design of $\hat{\theta}_{t,i}^{0}$,
$I_{t}^{{\dagger}}$ and $\epsilon_{t}$ can ensure that the attacker’s
estimation $\hat{\theta}_{t,i}^{0}$ will be close to $\theta_{i}$, while the
agent’s estimation $\hat{\theta}_{t,i}$ will be close to
$(1-\alpha)\theta_{K}$. In the following, we make these statements precise,
and formally analyze the performance of the proposed black-box attack scheme.

First, we analyze the estimation $\hat{\theta}_{t,i}^{0}$ at the attacker
side. We establish a confidence ellipsoid of $\langle
x_{t},\hat{\theta}_{t,i}^{0}\rangle$ at the attacker.

######  Lemma 2.

Assume the attacker performs the proposed black-box action poisoning attack.
With probability $1-2\delta$, we have

$\displaystyle|x_{t}^{T}\hat{\theta}_{t,i}^{0}-x_{t}^{T}\theta_{i}|\leq\beta_{t,i}^{0}\|x_{t}\|_{\left(V_{t,i}^{0}\right)^{-1}}.$
(18)

holds for all arm $i$ and all $t\geq 0$ simultaneously.

Lemma 2 shows that $\hat{\theta}_{i}^{0}$ lies in an ellipsoid with center at
$\theta_{i}$ with high probability, which implies that the attacker has good
estimate of each arm.

We then analyze the estimation $\hat{\theta}_{t,i}$ at the agent side. The
following lemma provides an upper bound on the absolute difference between
$\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]$ and $(1-\alpha)\langle
x_{t},\theta_{K}\rangle$.

######  Lemma 3.

Under the black-box attack, with probability $1-2\delta$, the estimate
obtained by an LinUCB agent satisfies

$\displaystyle\left|\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]-(1-\alpha)\langle
x_{t},\theta_{K}\rangle\right|$ $\displaystyle\leq$
$\displaystyle(1-\alpha)\beta_{t,K}^{0}\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}}+(1+\alpha)\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}.$

simultaneously for all $t\geq 0$ when $I_{t}\neq K$.

The bound in Lemma 3 consists of the confidence ellipsoid of the estimate of
arm $I_{t}^{{\dagger}}$ and that of arm $K$. As mentioned above, for a
successful attack, the number of observations on arm $I_{t}^{{\dagger}}$ will
be limited. Thus, in our proposed algorithm, the attacker use the importance
sampling to obtain the estimate of $\theta_{i}$, which will increases the
number of observations that can be used to estimate the coefficient vector of
arm $I_{t}^{{\dagger}}$. Using Lemma 3, we have the following lemma regarding
the estimation $\hat{\theta}_{t,i}$ at the agent side.

######  Lemma 4.

Consider the same assumption as in Lemma 2. With a probability at least
$1-\frac{(3K-1)\delta}{K}$, the estimate $\hat{\theta}_{t,i}$ obtained by the
LinUCB agent will satisfy

$\displaystyle|x_{t}^{T}\hat{\theta}_{t,i}-x_{t}^{T}(1-\alpha)\theta_{K}|$
(19) $\displaystyle\leq$
$\displaystyle\left(1+4d/\alpha\sqrt{K\log\left(1+tL^{2}/(d\lambda)\right)}\right)\left(\omega(N_{i}(t))+LS\sqrt{0.5\log\left(2KT/\delta\right)}\right)\|x_{t}\|_{V_{t,i}^{-1}},$

simultaneously for all arm $i\neq K$ and all $t\geq 0$.

Lemma 4 shows that, under the proposed black-box attack scheme, the agent’s
estimate of the parameter of non-target arm, i.e. $\hat{\theta}_{i}$, will
converge to $(1-\alpha)\theta_{K}$. As the result, the agent will believe that
the target arm $K$ is the optimal arm for any context in most rounds. Using
these supporting lemmas, we can then analyze the performance of the proposed
black-box attack strategy.

######  Theorem 2.

Under the same assumptions as in Lemma 4, with probability at least
$1-3\delta$, for all $T\geq 0$, the attacker can manipulate a LinUCB agent
into pulling the target arm in at least $T-|\mathcal{C}|$ rounds, using an
attack cost

$\begin{split}&|\mathcal{C}|\leq\frac{2d(K-1)}{(\alpha\gamma)^{2}}\left(2+\frac{4d}{\alpha}\sqrt{K\log\left(1+\frac{TL^{2}}{d\lambda}\right)}\right)^{2}\log\left(1+TL^{2}/(d\lambda)\right)\left(\omega(T)+LS\sqrt{0.5\log\left(2KT/\delta\right)}\right)^{2}.\end{split}$

Theorem 2 shows that our black-box attack strategy can manipulate a LinUCB
agent into pulling a target arm $T-O(\log^{3}T)$ times with attack cost
scaling as $O(\log^{3}T)$. Compared with the result for the white-box attack,
the black-box attack only brings an additional $\log T$ factor.

##  5 Numerical Experiments

In this section, we empirically evaluate the performance of the proposed
action poisoning attack schemes on three contextual bandit algorithms: LinUCB
[33], LinTS [34], and $\epsilon$-Greedy. We run the experiments on three
datasets:

Synthetic data: The dimension of contexts and the coefficient vectors is
$d=6$. We set the first entry of every context and coefficient vector to $1$.
The other entries of every context and coefficient vector are uniformly drawn
from $(-\frac{1}{\sqrt{d-1}},\frac{1}{\sqrt{d-1}})$. Thus, for all round $t$
and arm $i$, $\|x_{t}\|_{2}\leq\sqrt{2}$, $\|\theta_{i}\|_{2}\leq\sqrt{2}$ and
mean rewards $\langle x_{t},\theta_{i}\rangle>0$. The reward noise $\eta_{t}$
is drawn from a Gaussian distribution $\mathcal{N}(0,0.01)$.

Jester dataset [35]: Jester contains 4.1 million ratings of jokes in which the
rating values scale from $-10.00$ to $+10.00$. We normalize the rating to
$[0,1]$. The dataset includes 100 jokes and the ratings were collected from
73,421 users between April 1999 - May 2003. We consider a subset of 10 jokes
and 38432 users. Every jokes are rated by each user. We perform a low-rank
matrix factorization ($d=6$) on the ratings data and obtain the features for
both users and jokes. At each round, the environment randomly select a user as
the context and the reward noise is drawn from a Gaussian distribution
$\mathcal{N}(0,0.01)$.

MovieLens 25M dataset: [36] MovieLens 25M dataset contains 25 million 5-star
ratings of 62,000 movies by 162,000 users. The preprocessing of this data is
almost the same as the Jester dataset, except that we consider a subset of 10
movies and 7344 users. At each round, the environment randomly select a user
as the context and the reward noise is drawn from a Gaussian distribution
$\mathcal{N}(0,0.01)$.

We set $\delta=0.1$ and $\lambda=2$. For all the experiments, we set the total
number of rounds $T=10^{6}$ and the number of arms $K=10$. We independently
run ten repeated experiments. Results reported are averaged over the ten
experiments.

The results are shown in Table 1 and Figure 2. These experiments show that the
action poisoning attacks can force the three agents to pull the target arm
very frequently, while the agents rarely pull the target arm under no attack.
Under the attacks, the true regret of the agent becomes linear as the target
arm is not optimal for most context. Table 1 show the number of rounds the
agent pulls the target arm among $T=10^{6}$ total rounds. In the synthetic
dataset, under the proposed white-box attacks, the target arm is pulled more
than $98.1\%$ of the times by the three agent (see Table 1). The target arm is
pulled more than $91.6\%$ of the times in the worst case (the black-box
attacks on LinUCB). Fig 2 shows the cumulative cost of the attacks on three
agents for the three datasets. The results show that the attack cost
$|\mathcal{C}|$ of every attack scheme on every agent for every dataset scales
sublinearly, which exposes a significant security threat of the action
poisoning attacks on linear contextual bandits.

| Synthetic | Jester | MovieLens
---|---|---|---
$\epsilon$-Greeedy without attacks |  2124.6 |  5908.7 |  3273.5
White-box attack on $\epsilon$-Greeedy | 982122.5 | 971650.9 | 980065.6
Black-box attack on $\epsilon$-Greeedy | 973378.5 | 939090.2 | 935293.8
LinUCB without attacks |  8680.9 | 16927.2 | 13303.4
White-box attack on LinUCB | 981018.7 | 911676.9 | 969118.6
Black-box attack on LinUCB | 916140.8 | 875284.7 | 887373.1
LinTS without attacks |  5046.9 | 18038.0 |  9759.0
White-box attack on LinTS | 981112.8 | 908488.3 | 956821.1
Black-box attack on LinTS | 918403.8 | 862556.8 | 825034.8
Table 1: Average number of rounds when the agent pulls the target arm over
$T=10^{6}$ rounds. Figure 2: The cumulative cost of the attacks for the
synthetic (Left), Jester (Center) and MovieLens (Right) datasets.

##  6 Conclusion

In this paper, we have proposed a new class of attacks on linear contextual
bandits: action poisoning attacks. We have shown that our white-box attack
strategy is able to force any linear contextual bandit agent, whose regret
scales sublinearly with the total number of rounds, into pulling a target arm
chosen by the attacker. In addition, we have shown that our white-box attack
strategy can force LinUCB agent into pulling a target arm $T-O(\log^{2}T)$
times with attack cost scaled as $O(\log^{2}T)$. We have further shown that
the proposed black-box attack strategy can force LinUCB agent into pulling a
target arm $T-O(\log^{3}T)$ times with attack cost scaled as $O(\log^{3}T)$.
Our results expose a significant security threat to contextual bandit
algorithms. In the future, we will investigate the defense strategy to
mitigate the effects of this attack.

## References

  * [1] Olivier Chapelle, Eren Manavoglu, and Romer Rosales,  “Simple and scalable response prediction for display advertising,”  ACM Transactions on Intelligent Systems and Technology (TIST), vol. 5, no. 4, pp. 61:1–61:34, Dec. 2014.
  * [2] Lifeng Lai, Hesham El Gamal, Hai Jiang, and H Vincent Poor,  “Cognitive medium access: Exploration, exploitation and competition,”  IEEE transactions on mobile computing, vol. 10, no. 2, pp. 239–253, Feb. 2011.
  * [3] Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan,  “Cascading bandits: Learning to rank in the cascade model,”  in International Conference on Machine Learning, Lille, France, July 2015, PMLR, pp. 767–776.
  * [4] Lihong Li, Wei Chu, John Langford, and Robert E Schapire,  “A contextual-bandit approach to personalized news article recommendation,”  in Proceedings of the 19th international conference on World wide web, 2010, pp. 661–670.
  * [5] Vidit Saxena, Joakim Jaldén, Joseph E Gonzalez, Mats Bengtsson, Hugo Tullberg, and Ion Stoica,  “Contextual multi-armed bandits for link adaptation in cellular networks,”  in Proceedings of the 2019 Workshop on Network Meets AI & ML, 2019, pp. 44–49.
  * [6] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus,  “Intriguing properties of neural networks,”  in International Conference on Learning Representations, 2014.
  * [7] Seyed-Mohsen Moosavi-Dezfooli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard,  “Universal adversarial perturbations,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 1765–1773.
  * [8] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter,  “Certified adversarial robustness via randomized smoothing,”  in International Conference on Machine Learning, 2019, pp. 1310–1320.
  * [9] Elvis Dohmatob,  “Generalized no free lunch theorem for adversarial robustness,”  in Proceedings of the 36th International Conference on Machine Learning, 2019, pp. 1646–1654.
  * [10] Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu,  “On the convergence and robustness of adversarial training.,”  in ICML, 2019, vol. 1, p. 2.
  * [11] Sanjoy Dasgupta, Daniel Hsu, Stefanos Poulis, and Xiaojin Zhu,  “Teaching a black-box learner,”  in Proceedings of the 36th International Conference on Machine Learning, 2019, vol. 97, pp. 1547–1555.
  * [12] Ferdinando Cicalese, Eduardo Laber, Marco Molinaro, et al.,  “Teaching with limited information on the learner’s behaviour,”  in International Conference on Machine Learning, 2020, pp. 2016–2026.
  * [13] Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu,  “Adversarial attacks on stochastic bandits,”  in Advances in Neural Information Processing Systems, Montréal, Canada, Dec. 2018, pp. 3644–3653.
  * [14] Fang Liu and Ness Shroff,  “Data poisoning attacks on stochastic bandits,”  in International Conference on Machine Learning, Long Beach, CA, June 2019, vol. 97, pp. 4042–4050.
  * [15] Guanlin Liu and Lifeng Lai,  “Action-manipulation attacks on stochastic bandits,”  in ICASSP, 2020, pp. 3112–3116.
  * [16] Yuzhe Ma, Kwang-Sung Jun, Lihong Li, and Xiaojin Zhu,  “Data poisoning attacks in contextual bandits,”  in International Conference on Decision and Game Theory for Security. Springer, 2018, pp. 186–204.
  * [17] Evrard Garcelon, Baptiste Roziere, Laurent Meunier, Jean Tarbouriech, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirotta,  “Adversarial attacks on linear contextual bandits,”  in Advances in Neural Information Processing Systems, 2020, pp. 14362–14373.
  * [18] Vahid Behzadan and Arslan Munir,  “Vulnerability of deep reinforcement learning to policy induction attacks,”  in International Conference on Machine Learning and Data Mining in Pattern Recognition. Springer, 2017, pp. 262–275.
  * [19] Yunhan Huang and Quanyan Zhu,  “Deceptive reinforcement learning under adversarial manipulations on cost signals,”  in International Conference on Decision and Game Theory for Security. Springer, 2019, pp. 217–237.
  * [20] Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu,  “Policy poisoning in batch reinforcement learning and control,”  in Advances in Neural Information Processing Systems, 2019, vol. 32.
  * [21] Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu,  “Adaptive reward-poisoning attacks against reinforcement learning,”  in Proceedings of the 37th International Conference on Machine Learning, 2020, vol. 119, pp. 11225–11234.
  * [22] Yanchao Sun, Da Huo, and Furong Huang,  “Vulnerability-aware poisoning mechanism for online rl with unknown dynamics,”  in International Conference on Learning Representations, 2021.
  * [23] Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla,  “Policy teaching via environment poisoning: Training-time adversarial attacks against reinforcement learning,”  in International Conference on Machine Learning, 2020, pp. 7974–7984.
  * [24] Amin Rakhsha, Xuezhou Zhang, Xiaojin Zhu, and Adish Singla,  “Reward poisoning in reinforcement learning: Attacks against unknown learners in unknown environments,”  arXiv preprint arXiv:2102.08492, 2021.
  * [25] Guanlin Liu and Lifeng Lai,  “Provably efficient black-box action poisoning attacks against reinforcement learning,”  Advances in Neural Information Processing Systems, vol. 34, 2021\.
  * [26] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme,  “Stochastic bandits robust to adversarial corruptions,”  in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, Los Angeles, CA, June 2018, pp. 114–122.
  * [27] Anupam Gupta, Tomer Koren, and Kunal Talwar,  “Better algorithms for stochastic bandits with adversarial corruptions,”  in Conference on Learning Theory. PMLR, 2019, pp. 1562–1578.
  * [28] Z. Guan, K. Ji, D. Bucci, T. Hu, J. Palombo, M. Liston, and Y. Liang,  “Robust stochastic bandit algorithms under probabilistic unbounded adversarial attack,”  in Proceedings of the AAAI Conference on Artificial Intelligence, New York City, NY, Feb. 2020, pp. 4036–4043.
  * [29] Zhe Feng, David Parkes, and Haifeng Xu,  “The intrinsic robustness of stochastic bandits to strategic manipulation,”  in International Conference on Machine Learning. PMLR, 2020, pp. 3092–3101.
  * [30] Guanlin Liu and Lifeng Lai,  “Action-manipulation attacks against stochastic bandits: Attacks and defense,”  IEEE Transactions on Signal Processing, vol. 68, pp. 5152–5165, 2020.
  * [31] Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett,  “Stochastic linear bandits robust to adversarial attacks.,”  in International Conference on Artificial Intelligence and Statistics. PMLR, 2021, p. 991–999.
  * [32] Qin Ding, Cho-Jui Hsieh, and James Sharpnack,  “Robust stochastic linear contextual bandits under adversarial attacks,”  arXiv preprint arXiv:2106.02978, 2021.
  * [33] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári,  “Improved algorithms for linear stochastic bandits,”  Advances in neural information processing systems, vol. 24, pp. 2312–2320, 2011.
  * [34] Shipra Agrawal and Navin Goyal,  “Thompson sampling for contextual bandits with linear payoffs,”  in Proceedings of the 30th International Conference on Machine Learning, Atlanta, Georgia, USA, 17–19 Jun 2013, Proceedings of Machine Learning Research, pp. 127–135, PMLR.
  * [35] Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins,  “Eigentaste: A constant time collaborative filtering algorithm,”  information retrieval, vol. 4, no. 2, pp. 133–151, 2001.
  * [36] F Maxwell Harper and Joseph A Konstan,  “The movielens datasets: History and context,”  Acm transactions on interactive intelligent systems (tiis), vol. 5, no. 4, pp. 1–19, 2015.

##  Appendix A Proof of Proposition 1

When the agent pulls a non-target arm $I_{t}\neq K$, the mean reward received
by the agent should satisfy
$\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]=(1-\alpha)\langle
x_{t},\theta_{K}\rangle$. In the observation of the agent, the target arm
becomes optimal and the non-target arms are associated with the coefficient
vector $(1-\alpha)\theta_{K}$. In addition, the cumulative pseudo-regret
should satisfy $\bar{R}_{T}=\sum_{t=1}^{T}\mathbbm{1}_{\\{I_{t}\neq
K\\}}\alpha\langle x_{t},\theta_{K}\rangle$. If $\bar{R}_{T}$ is upper bounded
by $o(T)$, $\sum_{t=1}^{T}\mathbbm{1}_{\\{I_{t}\neq K\\}}$ is also upper
bounded by $o(T)$.

##  Appendix B Proof of Lemma 1

If the agent computes an estimate of $\theta_{i}$ by (4) and
$V_{t,i}=\left(\sum_{k\in\tau_{i}(t-1)}x_{k}x_{k}^{T}+\lambda\mathbf{I}\right)$,
we have

$\displaystyle x_{t}^{T}\hat{\theta}_{t,i}-x_{t}^{T}(1-\alpha)\theta_{K}$ (20)
$\displaystyle=$ $\displaystyle
x_{t}^{T}V_{t,i}^{-1}\left(\sum_{k\in\tau_{i}(t-1)}r_{t,I_{k}^{0}}x_{k}\right)-x_{t}^{T}V_{t,i}^{-1}V_{t,i}(1-\alpha)\theta_{K}$
$\displaystyle=$ $\displaystyle
x_{t}^{T}V_{t,i}^{-1}\left(\sum_{k\in\tau_{i}(t-1)}x_{k}\left(r_{t,I_{k}^{0}}-(1-\alpha)x_{k}^{T}\theta_{K}\right)\right)-\lambda
x_{t}^{T}V_{t,i}^{-1}(1-\alpha)\theta_{K}$ $\displaystyle=$
$\displaystyle\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\left(x_{k}^{T}\theta_{I_{k}^{0}}+\eta_{k}-(1-\alpha)x_{k}^{T}\theta_{K}\right)-\lambda
x_{t}^{T}V_{t,i}^{-1}(1-\alpha)\theta_{K},$

and by triangle inequality,

$\displaystyle|x_{t}^{T}\hat{\theta}_{t,i}-x_{t}^{T}(1-\alpha)\theta_{K}|$
(21) $\displaystyle\leq$
$\displaystyle\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\left(x_{k}^{T}\theta_{I_{k}^{0}}-(1-\alpha)x_{k}^{T}\theta_{K}\right)\right|+\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\eta_{k}\right|+\left|\lambda
x_{t}^{T}V_{t,i}^{-1}(1-\alpha)\theta_{K}\right|.$

In our model, the mean reward is bounded by $0<\langle
x_{t},\theta_{i}\rangle\leq\|x_{t}\|_{2}^{2}\|\theta_{i}\|_{2}^{2}=LS$. Since
the mean rewards are bounded and the rewards are generated independently, we
have
$0\leq\left|x_{k}^{T}\theta_{I_{k}^{0}}-(1-\alpha)x_{k}^{T}\theta_{K}\right|\leq
LS$ and
$\mathbb{E}[x_{k}^{T}\theta_{I_{k}^{0}}|F_{k-1}]=(1-\alpha)x_{k}^{T}\theta_{K}$.
Thus,
$\left\\{x_{t}^{T}V_{t,i}^{-1}x_{k}\left(x_{k}^{T}\theta_{I_{k}^{0}}-(1-\alpha)x_{k}^{T}\theta_{K}\right)\right\\}_{k\in\tau_{i}(t-1)}$
is a bounded martingale difference sequence w.r.t the filtration
$\\{F_{k}\\}_{k\in\tau_{i}(t-1)}$.

Then, by Azuma’s inequality,

$\displaystyle\mathbb{P}\left(\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\left(x_{k}^{T}\theta_{I_{k}^{0}}-(1-\alpha)x_{k}^{T}\theta_{K}\right)\right|\geq
B\right)$ (22) $\displaystyle\leq$ $\displaystyle
2\exp\left(\frac{-2B^{2}}{\sum_{k\in\tau_{i}(t-1)}(x_{t}^{T}V_{t,i}^{-1}x_{k}LS)^{2}}\right)$
$\displaystyle=$ $\displaystyle P_{i,t},$

where $B$ represents confidence bound. In order to ensure the confidence
bounds hold for all arms and all round $t$ simultaneously, we set
$P_{i,t}=\frac{\delta}{KT}$ so

$\displaystyle B$
$\displaystyle=LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)\sum_{k\in\tau_{i}(t-1)}(x_{t}^{T}V_{t,i}^{-1}x_{k})^{2}}$
(23) $\displaystyle\leq
LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\|x_{t}\|_{V_{t,i}^{-1}},$

where the last inequality is obtained from the fact that

$\displaystyle\|x_{t}\|_{V_{t,i}^{-1}}^{2}$
$\displaystyle=x_{t}^{T}V_{t,i}^{-1}\left(\sum_{k\in\tau_{i}(t-1)}x_{k}x_{k}^{T}+\lambda\mathbf{I}\right)V_{t,i}^{-1}x_{t}$
(24) $\displaystyle\geq
x_{t}^{T}V_{t,i}^{-1}\left(\sum_{k\in\tau_{i}(t-1)}x_{k}x_{k}^{T}\right)V_{t,i}^{-1}x_{t}$
$\displaystyle=\sum_{k\in\tau_{i}(t-1)}(x_{t}^{T}V_{t,i}^{-1}x_{k})^{2}.$

In other words, with probability $1-\delta$, we have

$\displaystyle\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\left(x_{k}^{T}\theta_{I_{k}^{0}}-(1-\alpha)x_{k}^{T}\theta_{K}\right)\right|$
(25) $\displaystyle\leq$ $\displaystyle
LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\|x_{t}\|_{V_{t,i}^{-1}},$

for all arms and all $t$.

Note that $V_{t,i}=\sum_{k\in\tau_{i}(t-1)}x_{k}x_{k}^{T}+\lambda\mathbf{I}$
is positive definite. We define $\langle x,y\rangle_{V}=x^{T}Vy$ as the
weighted inner-product. According to Cauchy-Schwarz inequality, we have

$\displaystyle\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\eta_{k}\right|\leq\left\|x_{t}\right\|_{V_{t,i}^{-1}}\left\|\sum_{k\in\tau_{i}(t-1)}x_{k}\eta_{k}\right\|_{V_{t,i}^{-1}}.$
(26)

Assume that $\lambda\geq L$. From Theorem 1 and Lemma 11 in [33], we know that
for any $\delta>0$, with probability at least $1-\delta$

$\displaystyle\left\|\sum_{k\in\tau_{i}(t-1)}x_{k}\eta_{k}\right\|_{V_{t,i}^{-1}}^{2}$
(27) $\displaystyle\leq$ $\displaystyle
2R^{2}\log\left(\frac{K\det(V_{t,i})^{1/2}\det(\lambda\mathbf{I})^{-1/2}}{\delta}\right)$
$\displaystyle\leq$ $\displaystyle
R\sqrt{2\log\frac{K}{\delta}+d\log\left(1+\frac{L^{2}N_{i}(t)}{\lambda
d}\right)},$

for all arms and all $t>0$,

For the third part of the right hand side of (29),

$\displaystyle|\lambda x_{t}^{T}V_{t,i}^{-1}(1-\alpha)\theta_{K}|$
$\displaystyle\leq\left\|(1-\alpha)\lambda\theta_{K}\right\|_{V_{t,i}^{-1}}\left\|x_{t}\right\|_{V_{t,i}^{-1}}.$
(28)

Since $V_{t,i}\succeq\lambda\mathbf{I}$, the maximum eigenvalue of
$V_{t,i}^{-1}$ is smaller or equal to $1/\lambda$. Thus,
$\left\|(1-\alpha)\lambda\theta_{K}\right\|_{V_{t,i}^{-1}}^{2}\leq\frac{1}{\lambda}\left\|(1-\alpha)\lambda\theta_{K}\right\|_{2}^{2}\leq(1-\alpha)^{2}\lambda
S^{2}$.

In summary,

$\displaystyle|x_{t}^{T}\hat{\theta}_{t,i}-x_{t}^{T}(1-\alpha)\theta_{K}|$
(29) $\displaystyle\leq$
$\displaystyle\left((1-\alpha)\sqrt{\lambda}S+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}+R\sqrt{2\log\frac{K}{\delta}+d\log\left(1+\frac{L^{2}N_{i}(t)}{\lambda
d}\right)}\right)\|x_{t}\|_{V_{t,i}^{-1}}.$

##  Appendix C Proof of Theorem 1

For round $t$ and context $x_{t}$, if LinUCB pulls arm $i\neq K$, we have

$\displaystyle
x_{t}^{T}\hat{\theta}_{t,K}+\beta_{t,K}\sqrt{x_{t}^{T}V_{t,K}^{-1}x_{t}}\leq
x_{t}^{T}\hat{\theta}_{t,i}+\beta_{t,i}\sqrt{x_{t}^{T}V_{t,i}^{-1}x_{t}}.$

Recall
$\beta_{t,i}=\sqrt{\lambda}S+R\sqrt{2\log\frac{K}{\delta}+d\log\left(1+\frac{L^{2}N_{i}(t)}{\lambda
d}\right)}$.

Since the attacker does not attack the target arm, the confidence bound of arm
$K$ does not change and $x_{t}^{T}\theta_{K}\leq
x_{t}^{T}\hat{\theta}_{t,K}+\beta_{t,K}\sqrt{x_{t}^{T}V_{t,K}^{-1}x_{t}}$
holds with probability $1-\frac{\delta}{K}$.

Thus, by Lemma 1,

$\displaystyle x_{t}^{T}\theta_{K}\leq$ $\displaystyle
x_{t}^{T}\hat{\theta}_{t,i}+\beta_{t,i}\sqrt{x_{t}^{T}V_{t,i}^{-1}x_{t}}$ (30)
$\displaystyle\leq$ $\displaystyle
x_{t}^{T}(1-\alpha)\theta_{K}+\left(LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\omega(N_{i}(t))+\beta_{t,i}\right)\|x_{t}\|_{V_{t,i}^{-1}}.$

By multiplying both sides $\mathbbm{1}_{\\{I_{t}=i\\}}$ and summing over
rounds, we have

$\displaystyle\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\alpha
x_{k}^{T}\theta_{K}$ (31) $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\left(\beta_{k,i}+\sqrt{\lambda}S+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}+R\sqrt{2\log\frac{K}{\delta}+d\log\left(1+\frac{L^{2}N_{i}(k)}{\lambda
d}\right)}\right)\|x_{k}\|_{V_{k,i}^{-1}}.$

Here, we use Lemma 11 from [33] and obtain

$\displaystyle\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\|x_{k}\|_{V_{k,i}^{-1}}^{2}$
$\displaystyle\leq 2d\log(1+\frac{N_{i}(t)L^{2}}{d\lambda})\leq
2d\log\left(1+\frac{tL^{2}}{d\lambda}\right).$ (32)

According to
$\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\|x_{k}\|_{V_{k,i}^{-1}}\leq\sqrt{N_{i}(t)\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\|x_{k}\|_{V_{k,i}^{-1}}^{2}}$,
we have

$\displaystyle\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\|x_{k}\|_{V_{k,i}^{-1}}^{2}\leq\sqrt{N_{i}(t)2d\log\left(1+\frac{tL^{2}}{d\lambda}\right)}.$
(33)

Thus, we have

$\displaystyle\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\alpha
x_{k}^{T}\theta_{K}$ (34) $\displaystyle\leq$
$\displaystyle\sqrt{N_{i}(t)2d\log\left(1+\frac{tL^{2}}{d\lambda}\right)}\left(LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}+2\sqrt{\lambda}S+2R\sqrt{2\log\frac{K}{\delta}+d\log\left(1+\frac{tL^{2}}{\lambda
d}\right)}\right),$

and

$\displaystyle N_{i}(t)=\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}$ (35)
$\displaystyle\leq$
$\displaystyle\frac{2d}{(\alpha\gamma)^{2}}\log\left(1+\frac{tL^{2}}{d\lambda}\right)\left(2\sqrt{\lambda}S+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}+2R\sqrt{2\log\frac{K}{\delta}+d\log\left(1+\frac{tL^{2}}{\lambda
d}\right)}\right)^{2},$

where $\gamma=\min_{x\in\mathcal{D}}\langle x,\theta_{K}\rangle$.

##  Appendix D Proof of Lemma 2

Since the estimate of $\theta_{i}$ obtained by the agent satisfies

$\hat{\theta}_{t,i}^{0}=\left(V_{t,i}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}w_{k,i}r_{k,I_{k}^{0}}x_{k}\right),$
(36)

we have

$\displaystyle x_{t}^{T}\hat{\theta}_{t,i}^{0}-x_{t}^{T}\theta_{i}$
$\displaystyle=$ $\displaystyle
x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}w_{k,i}r_{k,I_{k}^{0}}x_{k}\right)-x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}V_{t,i}^{0}\theta_{i}$
$\displaystyle=$ $\displaystyle
x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}(w_{k,i}r_{k,I_{k}^{0}}-x_{k}^{T}\theta_{i})x_{k}\right)-\lambda
x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}\theta_{i}$ $\displaystyle=$
$\displaystyle
x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}(w_{k,i}x_{k}^{T}\theta_{I_{k}^{0}}-x_{k}^{T}\theta_{i})x_{k}\right)+x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}w_{k,i}\eta_{k}\right)-\lambda
x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}\theta_{i}.$

We have
$0\leq\left|w_{k,i}x_{k}^{T}\theta_{I_{k}^{0}}-x_{k}^{T}\theta_{i}\right|\leq
w_{k,i}LS$ and
$\mathbb{E}[w_{k,i}x_{k}^{T}\theta_{I_{k}^{0}}|F_{k-1}]=x_{k}^{T}\theta_{i}$.
In addition, by the definition of $w_{k,i}$, we have that $w_{k,i}\leq
1/\alpha$ if $i\neq K$, and $w_{k,i}\leq 2$ if $i=K$. Thus,
$\left\\{x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}(w_{k,i}x_{k}^{T}\theta_{I_{k}^{0}}-x_{k}^{T}\theta_{i})x_{k}\right)\right\\}_{k\in\tau_{i}(t-1)}$
is also a bounded martingale difference sequence w.r.t the filtration
$\\{F_{k}\\}_{k\in\tau_{i}(t-1)}$. By following the steps in Section B, we
have, with probability $1-\frac{K-1}{K}\delta$, for any arm $i\neq K$ and any
round $t$,

$\displaystyle\left|x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}(w_{k,i}x_{k}^{T}\theta_{I_{k}^{0}}-x_{k}^{T}\theta_{i})x_{k}\right)\right|$
$\displaystyle\leq$
$\displaystyle\frac{LS}{\alpha}\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\|x_{t}\|_{\left(V_{t,i}^{0}\right)^{-1}},$

and with probability $1-\frac{1}{K}\delta$, for arm $K$ and any round $t$,

$\displaystyle\left|x_{t}^{T}\left(V_{t,K}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}(w_{k,K}x_{k}^{T}\theta_{I_{k}^{0}}-x_{k}^{T}\theta_{K})x_{k}\right)\right|$
$\displaystyle\leq$ $\displaystyle
2LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}}.$

The confidence bound of the second item of the right side hand of (D) can be
obtained from (27). With probability, $1-\frac{K-1}{K}\delta$, for any arm
$i\neq K$ and any round $t$,

$\displaystyle\left|x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}w_{k,i}\eta_{k}\right)\right|$
(37) $\displaystyle\leq$
$\displaystyle\frac{R}{\alpha}\sqrt{2\log\frac{K}{\delta}+d\log\left(1+\frac{L^{2}N_{i}^{{\dagger}}(t)}{\lambda
d}\right)}\|x_{t}\|_{\left(V_{t,i}^{0}\right)^{-1}}.$

With probability, $1-\frac{1}{K}\delta$, for arm $K$ and any round $t$,

$\displaystyle\left|x_{t}^{T}\left(V_{t,i}^{0}\right)^{-1}\left(\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}w_{k,i}\eta_{k}\right)\right|$
(38) $\displaystyle\leq$ $\displaystyle
2R\sqrt{2\log\frac{K}{\delta}+d\log\left(1+\frac{L^{2}N_{K}^{{\dagger}}(t)}{\lambda
d}\right)}\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}}.$

In summary,

$\displaystyle|x_{t}^{T}\hat{\theta}_{t,i}^{0}-x_{t}^{T}\theta_{i}|$ (39)
$\displaystyle\leq$
$\displaystyle\phi_{i}\left(\sqrt{\lambda}S+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}+R\sqrt{2\log\frac{K}{\delta}+d\log\left(1+\frac{L^{2}N_{i}^{{\dagger}}(t)}{\lambda
d}\right)}\right)\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}},$

where $\phi_{i}=1/\alpha$ when $i\neq K$ and $\phi_{K}=2$.

##  Appendix E Proof of Lemma 3

Recall the definition of $\epsilon_{t}$:

$\displaystyle\epsilon_{t}=\text{clip}\left(\frac{1}{2},\frac{(1-\alpha)\langle
x_{t},\hat{\theta}_{t,K}^{0}\rangle-\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle}{\langle
x_{t},\hat{\theta}_{t,K}^{0}\rangle-\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle},1-\alpha\right),$ (40)

and the definition of $I_{t}^{{\dagger}}$:

$I_{t}^{{\dagger}}=\arg\min_{i\neq K}\left(\langle
x_{t},\hat{\theta}_{t,i}^{0}\rangle-\beta_{t,i}^{0}\|x_{t}\|_{(V_{t,i}^{0})^{-1}}\right).$
(41)

By Lemma 2, $\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle-\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{(V_{t,I_{t}^{{\dagger}}}^{0})^{-1}}\leq\min_{i}\langle
x_{t},\theta_{i}\rangle$ with probability $1-2\delta$.

Because $\epsilon_{t}$ is bounded by $[1/2,1-\alpha]$, we can analyze
$\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]$ in four cases.

Case 1: when $\langle x_{t},\hat{\theta}_{t,K}^{0}\rangle<\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle$ and
$\epsilon_{t}=1-\alpha$, we have

$\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]=(1-\alpha)\langle
x_{t},\theta_{K}\rangle+\alpha\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle.$ (42)

Then, by Lemma 2,

$\displaystyle(1-\alpha)x_{t}^{T}\theta_{K}+\alpha
x_{t}^{T}\theta_{I_{t}^{{\dagger}}}-(1-\alpha)x_{t}^{T}\theta_{K}$ (43)
$\displaystyle\leq$
$\displaystyle(1-\alpha)\left(x_{t}^{T}\hat{\theta}_{t,K}^{0}+\beta_{t,K}^{0}\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}}\right)+\alpha\left(x_{t}^{T}\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}+\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}\right)-(1-\alpha)x_{t}^{T}\theta_{K}$
$\displaystyle\leq$ $\displaystyle
x_{t}^{T}\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}-(1-\alpha)x_{t}^{T}\theta_{K}+(1-\alpha)\beta_{t,K}^{0}\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}}+\alpha\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}$
$\displaystyle\leq$
$\displaystyle(1-\alpha)\beta_{t,K}^{0}\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}}+(1+\alpha)\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}},$

where the last inequality is obtained by
$x_{t}^{T}\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}-\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}\leq\min_{i}\langle
x_{t},\theta_{i}\rangle$ and Assumption 1. We also have

$\displaystyle(1-\alpha)x_{t}^{T}\theta_{K}+\alpha
x_{t}^{T}\theta_{I_{t}^{{\dagger}}}-(1-\alpha)x_{t}^{T}\theta_{K}=\alpha
x_{t}^{T}\theta_{I_{t}^{{\dagger}}}\geq 0.$ (44)

Case 2: when $\langle x_{t},\hat{\theta}_{t,K}^{0}\rangle\geq\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle>(1-2\alpha)\langle
x_{t},\hat{\theta}_{t,K}^{0}\rangle$ and $\epsilon_{t}=1/2$, we have

$\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]=\frac{1}{2}\langle
x_{t},\theta_{K}\rangle+\frac{1}{2}\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle.$ (45)

Then, by Lemma 2,

$\displaystyle\frac{1}{2}(x_{t}^{T}\theta_{K}+x_{t}^{T}\theta_{I_{t}^{{\dagger}}})-(1-\alpha)x_{t}^{T}\theta_{K}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\left(x_{t}^{T}\theta_{I_{t}^{{\dagger}}}-(1-2\alpha)x_{t}^{T}\theta_{K}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\left(x_{t}^{T}\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}+\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}-(1-2\alpha)x_{t}^{T}\theta_{K}\right)$
$\displaystyle\leq$
$\displaystyle\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}$

where the last inequality is obtained by
$x_{t}^{T}\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}-\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}\leq\min_{i}\langle
x_{t},\theta_{i}\rangle$ and Assumption 1.

In addition, by Lemma 2,

$\displaystyle\frac{1}{2}(x_{t}^{T}\theta_{K}+x_{t}^{T}\theta_{I_{t}^{{\dagger}}})-(1-\alpha)x_{t}^{T}\theta_{K}$
(46) $\displaystyle\geq$
$\displaystyle\frac{1}{2}\left(x_{t}^{T}\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}-\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}-(1-2\alpha)\left(x_{t}^{T}\hat{\theta}_{t,K}^{0}+\beta_{t,K}^{0}\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}}\right)\right)$
$\displaystyle\geq$
$\displaystyle-\frac{1}{2}\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}-\frac{1}{2}(1-2\alpha)\beta_{t,K}^{0}\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}}.$

Case 3: when $0\leq\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle\leq(1-2\alpha)\langle
x_{t},\hat{\theta}_{t,K}^{0}\rangle$ and $1/2\leq\epsilon_{t}\leq 1-\alpha$,
we have

$\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]=\epsilon_{t}\langle
x_{t},\theta_{K}\rangle+(1-\epsilon_{t})\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle.$ (47)

We can find that

$\displaystyle\epsilon_{t}\langle
x_{t},\theta_{K}\rangle+(1-\epsilon_{t})\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle-(1-\alpha)\langle
x_{t},\theta_{K}\rangle$ (48) $\displaystyle=$
$\displaystyle\epsilon_{t}(\langle x_{t},\theta_{K}\rangle-\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle)+\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle-(1-\alpha)\langle
x_{t},\theta_{K}\rangle$ $\displaystyle=$ $\displaystyle\epsilon_{t}(\langle
x_{t},\hat{\theta}_{t,K}^{0}\rangle-\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle)+\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle-(1-\alpha)\langle
x_{t},\theta_{K}\rangle$ $\displaystyle+\epsilon_{t}(\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle-\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle)+\epsilon_{t}(\langle
x_{t},\theta_{K}\rangle-\langle x_{t},\hat{\theta}_{t,K}^{0}\rangle)$
$\displaystyle=$ $\displaystyle(1-\alpha)\langle
x_{t},\hat{\theta}_{t,K}^{0}\rangle-\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle+\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle$ $\displaystyle-(1-\alpha)\langle
x_{t},\theta_{K}\rangle+\epsilon_{t}(\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle-\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle)+\epsilon_{t}(\langle
x_{t},\theta_{K}\rangle-\langle x_{t},\hat{\theta}_{t,K}^{0}\rangle)$
$\displaystyle=$ $\displaystyle(1-\alpha-\epsilon_{t})\left(\langle
x_{t},\hat{\theta}_{t,K}^{0}\rangle-\langle
x_{t},\theta_{K}\rangle\right)+(1-\epsilon_{t})\left(\langle
x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle-\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle\right),$

which is equivalent to

$\displaystyle\left|\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]-(1-\alpha)\langle
x_{t},\theta_{K}\rangle\right|$ (49) $\displaystyle\leq$
$\displaystyle(1-\alpha-\epsilon_{t})\beta_{t,K}^{0}\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}}$
$\displaystyle+(1-\epsilon_{t})\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}.$

Case 4: when $\langle x_{t},\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}\rangle<0$
and $\epsilon_{t}=1-\alpha$, we have

$\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]=(1-\alpha)\langle
x_{t},\theta_{K}\rangle+\alpha\langle
x_{t},\theta_{I_{t}^{{\dagger}}}\rangle.$ (50)

Then, by Lemma 2,

$\displaystyle(1-\alpha)x_{t}^{T}\theta_{K}+\alpha
x_{t}^{T}\theta_{I_{t}^{{\dagger}}}-(1-\alpha)x_{t}^{T}\theta_{K}$ (51)
$\displaystyle=$ $\displaystyle\alpha x_{t}^{T}\theta_{I_{t}^{{\dagger}}}$
$\displaystyle\leq$ $\displaystyle\alpha
x_{t}^{T}\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}+\alpha\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}$
$\displaystyle\leq$
$\displaystyle\alpha\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}},$

where the last inequality is obtained by
$x_{t}^{T}\hat{\theta}_{t,I_{t}^{{\dagger}}}^{0}-\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}\leq\min_{i}\langle
x_{t},\theta_{i}\rangle$ and Assumption 1. We also have

$\displaystyle(1-\alpha)x_{t}^{T}\theta_{K}+\alpha
x_{t}^{T}\theta_{I_{t}^{{\dagger}}}-(1-\alpha)x_{t}^{T}\theta_{K}=\alpha
x_{t}^{T}\theta_{I_{t}^{{\dagger}}}\geq 0.$ (52)

Combining these four cases, we have

$\displaystyle\left|\mathbb{E}[r_{t,I_{t}^{0}}|F_{t-1},I_{t}]-(1-\alpha)\langle
x_{t},\theta_{K}\rangle\right|$ (53) $\displaystyle\leq$
$\displaystyle(1-\alpha)\beta_{t,K}^{0}\|x_{t}\|_{\left(V_{t,K}^{0}\right)^{-1}}+(1+\alpha)\beta_{t,I_{t}^{{\dagger}}}^{0}\|x_{t}\|_{\left(V_{t,I_{t}^{{\dagger}}}^{0}\right)^{-1}}.$

##  Appendix F Proof of Lemma 4

From Section B, we have, for any arm $i\neq K$,

$\displaystyle|x_{t}^{T}\hat{\theta}_{t,i}-x_{t}^{T}(1-\alpha)\theta_{K}|$
(54) $\displaystyle\leq$
$\displaystyle\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\left(x_{k}^{T}\theta_{I_{k}^{0}}-(1-\alpha)x_{k}^{T}\theta_{K}\right)\right|$
$\displaystyle+\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\eta_{k}\right|+\left|\lambda
x_{t}^{T}V_{t,i}^{-1}(1-\alpha)\theta_{K}\right|$ $\displaystyle\leq$
$\displaystyle\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\left(x_{k}^{T}\theta_{I_{k}^{0}}-\epsilon_{k}\langle
x_{k},\theta_{K}\rangle-(1-\epsilon_{k})\langle
x_{k},\theta_{I_{k}^{{\dagger}}}\rangle\right)\right|$
$\displaystyle+\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\left(\epsilon_{k}\langle
x_{k},\theta_{K}\rangle+(1-\epsilon_{k})\langle
x_{k},\theta_{I_{k}^{{\dagger}}}\rangle-(1-\alpha)x_{k}^{T}\theta_{K}\right)\right|$
$\displaystyle+\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\eta_{k}\right|+\left|\lambda
x_{t}^{T}V_{t,i}^{-1}(1-\alpha)\theta_{K}\right|.$

Since the mean rewards are bounded and the rewards are generated
independently, we have
$0\leq\left|x_{k}^{T}\theta_{I_{k}^{0}}-\epsilon_{k}\langle
x_{k},\theta_{K}\rangle-(1-\epsilon_{k})\langle
x_{k},\theta_{I_{k}^{{\dagger}}}\rangle\right|\leq LS$ and
$\mathbb{E}[x_{k}^{T}\theta_{I_{k}^{0}}|F_{k-1}]=\epsilon_{k}\langle
x_{k},\theta_{K}\rangle+(1-\epsilon_{k})\langle
x_{k},\theta_{I_{k}^{{\dagger}}}\rangle$.

Then
$\left\\{x_{t}^{T}V_{t,i}^{-1}x_{k}\left(x_{k}^{T}\theta_{I_{k}^{0}}-\mathbb{E}[x_{k}^{T}\theta_{I_{k}^{0}}|F_{k-1}]\right)\right\\}_{k\in\tau_{i}(t-1)}$
is also a bounded martingale difference sequence w.r.t the filtration
$\\{F_{k}\\}_{k\in\tau_{i}(t-1)}$. By following the steps in Section B, we
have, with probability $1-\delta$, for any arm $i$ and any round $t$,

$\displaystyle\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\left(x_{k}^{T}\theta_{I_{k}^{0}}-\mathbb{E}[x_{k}^{T}\theta_{I_{k}^{0}}|F_{k-1}]\right)\right|$
(55) $\displaystyle\leq$ $\displaystyle
LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\|x_{t}\|_{V_{t,i}^{-1}}.$

From (24) in Section B, we have

$\displaystyle\|x_{t}\|_{V_{t,i}^{-1}}^{2}\geq\sum_{k\in\tau_{i}(t-1)}(x_{t}^{T}V_{t,i}^{-1}x_{k})^{2}.$
(56)

Then, the second item of the right hand side of (54) can be upper bounded by

$\displaystyle\left|\sum_{k\in\tau_{i}(t-1)}x_{t}^{T}V_{t,i}^{-1}x_{k}\left(\epsilon_{k}\langle
x_{k},\theta_{K}\rangle+(1-\epsilon_{k})\langle
x_{t},\theta_{I_{k}^{{\dagger}}}\rangle\right.\right.$ (57)
$\displaystyle\left.\left.-(1-\alpha)x_{k}^{T}\theta_{K}\right)\right|$
$\displaystyle\leq$
$\displaystyle\sqrt{\sum_{k\in\tau_{i}(t-1)}\left(\mathbb{E}[r_{k,I_{k}^{0}}|F_{k-1},I_{k}]-(1-\alpha)x_{k}^{T}\theta_{K}\right)^{2}}\sqrt{\sum_{k\in\tau_{i}(t-1)}(x_{t}^{T}V_{t,i}^{-1}x_{k})^{2}}$
$\displaystyle\leq$
$\displaystyle\left(\sum_{k\in\tau_{i}(t-1)}\left((1-\alpha)\beta_{k,K}^{0}\|x_{k}\|_{\left(V_{k,K}^{0}\right)^{-1}}+(1+\alpha)\beta_{k,I_{k}^{{\dagger}}}^{0}\|x_{k}\|_{\left(V_{k,I_{k}^{{\dagger}}}^{0}\right)^{-1}}\right)^{2}\right)^{\frac{1}{2}}\|x_{t}\|_{V_{t,i}^{-1}},$

where the first inequality is obtained from Cauchy-Schwarz inequality, the
second inequality is obtained from Lemma 3 and (24).

In addition, by the fact that $(a+b)^{2}\leq 2a^{2}+2b^{2}$ for any real
number, we have

$\displaystyle\sum_{k\in\tau_{i}(t-1)}\left((1-\alpha)\beta_{k,K}^{0}\|x_{k}\|_{\left(V_{k,K}^{0}\right)^{-1}}+(1+\alpha)\beta_{k,I_{k}^{{\dagger}}}^{0}\|x_{k}\|_{\left(V_{k,I_{k}^{{\dagger}}}^{0}\right)^{-1}}\right)^{2}$
(58) $\displaystyle\leq$
$\displaystyle\sum_{k\in\tau_{i}(t-1)}2\left((1-\alpha)\beta_{k,K}^{0}\|x_{k}\|_{\left(V_{k,K}^{0}\right)^{-1}}\right)^{2}+\sum_{k\in\tau_{i}(t-1)}2\left((1+\alpha)\beta_{k,I_{k}^{{\dagger}}}^{0}\|x_{k}\|_{\left(V_{k,I_{k}^{{\dagger}}}^{0}\right)^{-1}}\right)^{2}.$

Here, we use Lemma 11 from [33] and get, for any arm $i$,

$\displaystyle\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}\|x_{k}\|_{(V_{k,i}^{0})^{-1}}^{2}$
$\displaystyle\leq 2d\log\left(1+\frac{N_{i}(t)L^{2}}{d\lambda}\right)$ (59)
$\displaystyle\leq 2d\log\left(1+\frac{tL^{2}}{d\lambda}\right).$

By the fact that $\sum_{i}\tau_{i}(t-1)=\tau_{K}^{{\dagger}}(t-1)$, and
$\sum_{i\neq K}\tau_{i}(t-1)=\sum_{i\neq K}\tau_{i}^{{\dagger}}(t-1)$, we
have, for any arm $i$, $\tau_{i}(t-1)\subseteq\tau_{K}^{{\dagger}}(t-1)$, and
$\tau_{i}(t-1)\subseteq\sum_{j\neq K}\tau_{j}^{{\dagger}}(t-1)$. Thus,

$\displaystyle\sum_{k\in\tau_{i}(t-1)}\|x_{k}\|_{\left(V_{k,K}^{0}\right)^{-1}}^{2}$
$\displaystyle\leq\sum_{k\in\tau_{K}^{{\dagger}}(t-1)}\|x_{k}\|_{(V_{k,K}^{0})^{-1}}^{2}$
(60) $\displaystyle\leq 2d\log\left(1+\frac{tL^{2}}{d\lambda}\right),$

and

$\displaystyle\sum_{k\in\tau_{i}(t-1)}\|x_{k}\|_{\left(V_{k,I_{k}^{{\dagger}}}^{0}\right)^{-1}}^{2}$
$\displaystyle\leq\sum_{i\neq
K}\sum_{k\in\tau_{i}^{{\dagger}}(t-1)}\|x_{k}\|_{(V_{k,i}^{0})^{-1}}^{2}$ (61)
$\displaystyle\leq 2(K-1)d\log\left(1+\frac{tL^{2}}{d\lambda}\right).$

By combining (58), (60) and (61), we have

$\displaystyle\sum_{k\in\tau_{i}(t-1)}\left((1-\alpha)\beta_{k,K}^{0}\|x_{k}\|_{\left(V_{k,K}^{0}\right)^{-1}}+(1+\alpha)\beta_{k,I_{k}^{{\dagger}}}^{0}\|x_{k}\|_{\left(V_{k,I_{k}^{{\dagger}}}^{0}\right)^{-1}}\right)^{2}$
(62) $\displaystyle\leq$
$\displaystyle\sum_{k\in\tau_{i}(t-1)}2\left(\beta_{k,K}^{0}\|x_{k}\|_{\left(V_{k,K}^{0}\right)^{-1}}\right)^{2}+\sum_{k\in\tau_{i}(t-1)}2\left(2\beta_{k,I_{k}^{{\dagger}}}^{0}\|x_{k}\|_{\left(V_{k,I_{k}^{{\dagger}}}^{0}\right)^{-1}}\right)^{2}$
$\displaystyle\leq$ $\displaystyle
16d^{2}\left(1+\frac{(K-1)}{\alpha^{2}}\right)\left(\omega(t)+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\right)^{2}\log\left(1+\frac{tL^{2}}{d\lambda}\right)$
$\displaystyle\leq$
$\displaystyle\frac{16d^{2}K}{\alpha^{2}}\left(\omega(t)+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\right)^{2}\log\left(1+\frac{tL^{2}}{d\lambda}\right).$

In summary, we have

$\displaystyle|x_{t}^{T}\hat{\theta}_{t,i}-x_{t}^{T}(1-\alpha)\theta_{K}|$
(63) $\displaystyle\leq$
$\displaystyle\left(1+\frac{4d}{\alpha}\sqrt{K\log\left(1+\frac{tL^{2}}{d\lambda}\right)}\right)\left(\omega(N_{i}(t))+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\right)\|x_{t}\|_{V_{t,i}^{-1}}.$

##  Appendix G Proof of Theorem 2

For round $t$ and context $x_{t}$, if LinUCB pulls arm $i\neq K$, we have

$\displaystyle
x_{t}^{T}\hat{\theta}_{t,K}+\beta_{t,K}\sqrt{x_{t}^{T}V_{t,K}^{-1}x_{t}}\leq
x_{t}^{T}\hat{\theta}_{t,i}+\beta_{t,i}\sqrt{x_{t}^{T}V_{t,i}^{-1}x_{t}}.$

In this case,
$\beta_{t,i}=\omega(N_{i}(t))=\sqrt{\lambda}S+R\sqrt{2\log\frac{K}{\delta}+d\log\left(1+\frac{L^{2}N_{i}(t)}{\lambda
d}\right)}$.

Since the attacker does not attack the target arm, the confidence bound of arm
$K$ does not change and $x_{t}^{T}\theta_{K}\leq
x_{t}^{T}\hat{\theta}_{t,K}+\beta_{t,K}\sqrt{x_{t}^{T}V_{t,K}^{-1}x_{t}}$
holds with probability $1-\frac{\delta}{K}$.

Thus, by Lemma 2,

$\displaystyle x_{t}^{T}\theta_{K}\leq$ $\displaystyle
x_{t}^{T}\hat{\theta}_{t,i}+\beta_{t,i}\sqrt{x_{t}^{T}V_{t,i}^{-1}x_{t}}$ (64)
$\displaystyle\leq$ $\displaystyle
x_{t}^{T}(1-\alpha)\theta_{K}+\omega(N_{i}(t))\|x_{t}\|_{V_{t,i}^{-1}}$
$\displaystyle+\left(1+\frac{4d}{\alpha}\sqrt{K\log\left(1+\frac{tL^{2}}{d\lambda}\right)}\right)\left(\omega(N_{i}(t))+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\right)\|x_{t}\|_{V_{t,i}^{-1}}.$

By multiplying both sides by $\mathbbm{1}_{\\{I_{t}=i\\}}$ and summing over
rounds, we have

$\displaystyle\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\alpha
x_{k}^{T}\theta_{K}$ (65) $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\left(2+\frac{4d}{\alpha}\sqrt{K\log\left(1+\frac{kL^{2}}{d\lambda}\right)}\right)$
$\displaystyle\left(\omega(N_{k}(t))+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\right)\|x_{k}\|_{V_{k,i}^{-1}}.$

Here, we use Lemma 11 from [33] and get

$\displaystyle\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\|x_{k}\|_{V_{k,i}^{-1}}^{2}$
$\displaystyle\leq 2d\log\left(1+\frac{N_{i}(t)L^{2}}{d\lambda}\right)$ (66)
$\displaystyle\leq 2d\log\left(1+\frac{tL^{2}}{d\lambda}\right).$

According to
$\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\|x_{k}\|_{V_{k,i}^{-1}}\leq\sqrt{N_{i}(t)\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\|x_{k}\|_{V_{k,i}^{-1}}^{2}}$,
we have

$\displaystyle\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\|x_{k}\|_{V_{k,i}^{-1}}^{2}\leq\sqrt{N_{i}(t)2d\log\left(1+\frac{tL^{2}}{d\lambda}\right)}.$
(67)

Thus, we have

$\displaystyle\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}\alpha
x_{k}^{T}\theta_{K}$ (68) $\displaystyle\leq$
$\displaystyle\sqrt{N_{i}(t)2d\log\left(1+\frac{tL^{2}}{d\lambda}\right)}\left(2+\frac{4d}{\alpha}\sqrt{K\log\left(1+\frac{tL^{2}}{d\lambda}\right)}\right)$
$\displaystyle\left(\omega(t)+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\right),$

and

$\displaystyle N_{i}(t)=\sum_{k=1}^{t}\mathbbm{1}_{\\{I_{k}=i\\}}$ (69)
$\displaystyle\leq$
$\displaystyle\frac{2d}{(\alpha\gamma)^{2}}\log\left(1+\frac{tL^{2}}{d\lambda}\right)\left(2+\frac{4d}{\alpha}\sqrt{K\log\left(1+\frac{tL^{2}}{d\lambda}\right)}\right)^{2}$
$\displaystyle\left(\omega(t)+LS\sqrt{\frac{1}{2}\log\left(\frac{2KT}{\delta}\right)}\right)^{2},$

where $\gamma=\min_{x\in\mathcal{D}}\langle x,\theta_{K}\rangle$.