Action Poisoning Attacks on Linear Contextual Bandits
Authors: Guanlin Liu
Lifeng Lai
Venue: Accepted by TMLR ()

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 disjoint 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. We also extend the proposed attack strategies to generalized linear models and show the effectiveness of the proposed strategies.

Published in Transactions on Machine Learning Research (02/2023)
Action Poisoning Attacks on Linear Contextual Bandits
Guanlin Liu
gialiu edu
Deportment of Electrical and Computer Engineering University of California, Davis
Lifeng Lai
flai@uudavii.. edu
Deportment Electrical and Computer Engineering University of California, Davis
Reviewed on OpenReview: Atips: // openreview. net/ met/ forum? id- ghGCKUsKJS
Abstract
Contextual bandit algorithms have many applicants in a variety 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 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 disjoint 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 while-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. We also extend the proposed attack strategics to generalized lincar models and show the effectiveness of the proposed strategies.
1 Introduction
Multiple armed bandits(MABs)), a popular framework of sequential decision making model, has been widely investigated and has many applicants in varicty of scenarios (Chapelle et al., 2014; Lai et al. 2011 Kveton The contextual bandits model is extension of the multi-armed bandits model with contextual
et al. 2015). information. At each round, the reward is associated with both the arm (a.k.a, action) and the context. Contextual bandits algorithms have a broad range of applications, such as rocommender systems (Li ct al. 2010), wireless networks (Saxena et al. 2019), etc.
In the modern industry-scale applications of bandit algorithms, action decisions, reward signal collection, and policy iterations normally implemented in distributed network. Action dccisions and reward signals may need to be transmitted over communication links. For example, in recommendation systems, the transitions of the decisions and the reward signal rely feedback loop between the recommendation system and the user. 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 specific policy. For example, restaurant may attack the bandit systems to force the systems into increasing the restaurant's 's exposure. Thus, understanding the risks of different kinds of adversarial attacks contextual bandits is essential for the safe applications of the contextual bandit model and designing robust contextual bandit systems.
Depending on the target of the poisoning attacks, the poisoning attacks against contextual linear bandits can be categorized into four types: reward poisoning attack, action poisoning attack, context poisoning attack and the mix of them. In this paper, we aim to investigate the impact of action poisoning attacks contextual bandit models. To best knowledge, this paper is the first work to analyze the impact

---

Published in Transactions on Machine Learning Research (02/2023)
of action poisoning attacks on contextual bandit models. Detailed comparisons of various types of attacks against contextual bandits will be provided in Section B 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 essential to address all possible weaknesses of the models and understanding the risks of different kinds of adversarial attacks. Our hope is that the understanding of the potential risks of action poisoning attacks could motivate follow up research to design algorithms that are robust to such attacks.
In this paper, study the action poisoning attack against disjoint linear contextual bandit (Li et al. 2010 Kong et al. 2020 Garcelon et al. 2020: Huang et al. (021) in both white-box and black-box scttings. 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 scttings, the attacker aims to manipulate the agent into frequently pulling target arm chosen by the attacker with minimum cost. The cost is measublack by the number of rounds that the attacker changes the actions selected by the agent. The contributions of this paper are:
(1) We propose new online action poisoning attack against contextual bandit in which the attacker aims force the agent to frequently pull target arm chosen by the attacker via strategically changing the agent's 's actions.
(2) We introduce white-box attack strategy that can manipulate any sublinear- disjoint linear con- textual bandit agent into pulling a target arm T --o0 o(T) rounds over a horizon of T rounds, while incurring a cost that is sublinear dependent on T.
(3) 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: 2010 We show that our proposed attack scheme can force the LinUCB agent into pulling LinUCB (Li et al.) target arm T Ollgg T) times with attack cost scaling as Olog'" T))
(4) We extend the proposed attack strategies to generalized linear contextual bandits. We further analyze the cost of the proposed attack strategies for a generalized linear contextual bandit algorithm: UCB-GLM et al. 2017).
(5) We evaluate our attack strategies using both synthetic and real datasets. We observe empirically that the total cost of our black-box attack is sublinear for variety of contextual bandit algorithms.
2 Related Work
In this section, we discuss related works on two parts: attacks that cause standard bandit algorithms to fail and robust bandit algorithms that can defend attacks.
Attacks Models. While there are many existing works addressing adversarial attacks on supervised learning models (Szegody et al.
2014
Moosavi-Dezfooli et al. 2017 Cohen et al. 2019 Dohmatob 2019 Wang al. Cicalese et al. 2020), the understanding of adversarial attacks on contextual
2019 Dasgupta et al. 2019
bandit models is less complete. Of particular relevance to our work is line of interesting recent work adversarial attacks
MABs (Jun et al.] 2018 Liu & Shrofi 2019 Liu & Lai 2020b) and on linear contextual bandits (Ma et al. 2018 Garcelon et al. 2020). In recent works in MABs setting, the types of allacks include both reward poisoning allacks and action poisoning allacks. In the reward poisoning allacks, there is an adversary who can manipulate the reward signal received by the agent (Jun et al. 2018 Liu & Shroff 2019). In the action poisoning attacks, the adversary can manipulate the action signal chosen by the agent before the environment receives (Lin & Lai 2020b). Existing works on adversarial attacks against linear contextual bandits focus on the reward (Ma et. al. 2018 Garcelon et al. 2020) context poisoning
2

---

Published in Transactions on Machine Learning Research (02/2023)
attacks (Garcelon et al. p020p. In the context poisoning attacks, the adversary can modify the context observed by the agent without changing the reward associated with the context. (Wang et al. 2022 defines the concept of attackability of linear stochastic bandits and introduces the sufficient and necessary conditions on attackability. There are also some recent interesting work on adversarial attacks against reinforcement
learning (RI) algorithms under various selting (Belzadan & Munir 2017 Huang Zhu 2019 Ma el al.
2019 Zhang et al.) 2020; Sun et al., 2021 Rakhsha al.) 2020 2021 Liu Lail 2021; Rangi ct al. 2022)
Although there are some recent works on the action poisoning attacks against MABs and RL, the action poisoning attack on contextual linear bandit is not simple extension of the case of MAB or RL. Firstly, in the MAB settings the rewards only depend on the arm (action), while in the contextual bandit setting, the rewards depend on both the arm and the context (state). Secondly, (Liu & Laij 2021) discusses the action poisoning atlack in the tabular RL case where the number of states is finite. In the linear contextual bandit problem, the number contexts is infinite. These factors make the design of attack strategies and performance analysis for the contextual linear bandit problems much more challenging.
Robust algorithms. Lots of efforts have been made to design robust bandit algori to defend adversarial attacks. In the MABs setting, (Lykouris et al. 2018) introduces bandit algorithm, called Multilayer Active Arm Elimination Race algorithm, that is robust to reward poisoning attacks. (Gupta et al. 2019) presents an algorithm named BARBAR that is robust to reward poisoning attacks and the regret of the proposed algorithm is nearly optimal. (Guan et al. 2020) proposes algorithms that are robust to a reward poisoning attack model where an adversary attacks with a certain probability at each round. (Feng et al. 2020 proves that Thompson Sampling, UCB, and e-greedy can be modified to be robust self-interested reward poisoning attacks. (Liu & Lai 2020a) introduce bandit. algorithm, called MOUCB, that is robust to action poisoning attacks. The algorithms for the context-free stochastic multi-armed bandit (MAB) scttings are not suited for our settings. In the linear contextual bandit setting, (Bogunovic et al.) 2021 proposes two variants of stochastic linear bandit algorithm that is robust to reward poisoning attacks, which separately
work on known attack budget case and agnostic attack budget case. (Bogunovic et al.] 2021 also proves that a simple greedy algorithm based on linear regression can be robust to linear contextual bandits with shablack coefficient under a stringent diversity assumption on the contexts. (Ding al.) 2022) provides a robust linear contextual bandit algorithm that works under both the reward poisoning attacks and context poisoning attacks. (He et al. 2022) provides nearly optimal algorithms for lincar contextual bandits with adversarial corruptions.
3
Problem Setup
3.1 Review of Linear Contextual Bandit
Consider the standard disjoint linear contextual bandit model in which the environment consists of K arms. In each round 1,2, 3.2.3..... .....,,, T, the agent observes context 2, DD where D C R pulls an arm I, and receives reward re,r,- Each arm i is associated with an unknown but fixed coefficient vector 0g E θ where θ C Rd. In each round f, the reward satisfies
Te, = (Ze, 01.) + n).
(1)
where 7)t is a conditionally independent. zero-mean R-subgaussian noise and (:))) denotes the inner product. Hence, the expected reward of arm i under context x, follows the linear setting
Birisl (Zre
(2)
for all and all arm i. If we consider the o-algebra F, = omn.... Ne becomes F, measurable which is a conditionally independent zero-mean random variable. The agent aims to minimize the cumulative pseudo-regret
Rr Σ ((xe, 01:) 0r))
where TE arg max,(xi; 0.).
3

---

Published in Transactions on Machine Learning Research (02/2023)
In this paper, assume that there exist L and S > O, such that for all round t and arm || 22 L and ||0:122 S S, where || denotes the f2-norm. We assume that there exist 'D C Rd such that for all D and all arm i, (x, 0.) > 0. In addition, for all t, It E D.
3.2 Action Poisoning Attack Model
In this paper, introduce novel adversary sctting, in which the attacker can manipulate the action chosen by the agent. In particular, at each round after the agent chooses arm 4, the attacker manipulate the agent's action by changing I to another Tg E (1.....K) K). If the attacker decides not to attack, 7g = I. The environment generates a random reward 72 based on the post-attack arm 1 and the context æt. Then the agent and the attacker receive reward Tr.19 from the environment. Since the agent does not know the attacker's 's manipulations and the presence of the attacker, the agent will still view T.Jo as the reward corresponding to the arm 4. The action poisoning attack model summarized in Algorithm
Algorithm Action poisoning attacks contextual linear bandit agent for t 1,2..... T do
Agent chooses arm 4e after observing the context It.
Attacker observes the agent's action 1, If the attacker decides to attack, it manipulates the action to 1. If the attacker does not attack, 1 4t-
4: The environment generates reward 7r according to arm 1, and context 2t.
5: The agent and attacker receive reward Tt,
6: end for
The goal of the attacker is design attack strategy manipulate the agent into pulling a larget arm very frequently but by making attacks rarely possible. Without loss of generality, we assume arm K is the "attack target" arm target arm. Define the set of rounds when the attacker decides to attack ft: == decides to attack, i.e., [C]. The allacker can monitor the contexts, the actions of the agent and the reward signals from the environment.
T, 1 * I)) The cumulative attack cost is the total number of rounds where the attacker
arm arm
Mean Reward(< <x,0>> 0x)
arm
arm
Context(x)
Figure An example of one dimension lincar contextual bandit model.
As the action poisoning attack only changes the actions, can impact but does not have direct control of the agent's observations. Furthermore, when the action space discrete and finite, the ability of the action poisoning altacker severely limited. It is reasonable to limit the choice of the target policy. Here we introduce important assumption that the target arm is not the worst arm:
Assumption 1. For all D, the mean reward of the target arm satisfies (z,0x) 0x) mineep 0.)
If the target arm is the worst arm most contexts, the attacker should change the target arm to better arm or the optimal arm so that the agent learns that the target set optimal for almost every context. In this case, the cost of attack may be up O(T). Assumption does not imply that the target is optimal

---

Published in Transactions on Machine Learning Research (02/2023)
at some contexts. The target arm could be sub-optimal for all contexts. Fig. shows example of one dimension linear contextual bandit model, where the z-axis represents the contexis and the y-axis represents the mean rewards of arms under different contexts, As shown in Fig. | arms 3 and 4 satisfy Assumption []] In addition, arm 3 is not optimal at any context.
Under Assumption there exists a E (0, 2)) such that
(1, 0i) (x, (0,0x)
max ZED
S (1 -2a).
Equivalently, Assumption implies that there exists E (0, }2), such that for all 6, we have
(1 (2 0k) 2
min (Te, Oz).
(3)
kE(K]
Equation 3 describes the relation of the target arm and the worst arm at context zt. The action poisoning allack can only indirectly impacts the agent's 's rewards. The mean rewards at te after the action atlack must be larger or equal to minge (2c, 0z). Under Equation 3 (1 2x)(x,; 2 mingg (2z, 0.) at any context z4. Then, with (22,, 0x) > 0, (1- (1,, 0x) > min;g[K] (#e, 02) at any context xt. Thus, the attacker can indirectly change the agent's 's mean reward of the non-target arm to (1 (2 0x). Then, the agent's 's estimate of each non-target arm's coefficient vector is close to (1-a)0x. which is worse than the target arm at any context. Equation 3 brings the possibility of successful action attacks.
Assumption is necessary in our analysis to prove a formal bound of the attack cost. In A Appendix A we show that this assumption is necessary the sense that, if this assumption does not hold, there exist a sequence of contexts herr such that no efficient action poisoning attack scheme can successfully attack LinUCB. Certainly, these sequences of contexts are worst case scenarios for attacks. In practice, if these worst case scenarios do not occur, the proposed algorithms in Sections 4.2 and 4.3 may still work even if the target arm is the worst in a small portion of the contexts (as illustrated in the numerical example soction).
3.3 Comparisons with Different Poisoning Attacks
We now compare the three types of poisoning attacks against contextual lincar bandit: reward poisoning attack, action poisoning attack and context poisoning attack. In the reward poisoning atlack (Ma et al. 2018 Garcelon et al. 2020), after the agent observes context Ig and chooses arm 7, the environment will generate reward Ts, based on context H, and arm 4. Then, the attacker can change the reward Tı to it and foed Ft to the agent.
Compablack with the reward poisoning attacks, the action poisoning attack consideblack 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, to 19 the reward received by the agent is changed from Tt, to Tt.1g which is random variable drawn from a distribution based the action I and context Iz. This is in contrast to reward poisoning attacks where attacker has direct control and can change the reward signal to any value 7, of his choice.
In the context poisoning attack (Garcelon et al. 2020), the attacker changes the context shown to the agent. The reward is generated based on the true context 2n and the agent's action 4. Nevertheless, the agent's '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 the most difficult to carry out.
For numerical comparison, contextual lincar bandits, there is no existing action poisoning attack method to compare. One could run simulations to compare with reward or context poisoning altacks, but the atlack costs are defined differently, due to the different nature of attacks. For example, for reward poisoning attacks, (Garcelon et al. 2020) proposed a reward poisoning attack method whose attack cost scales as ( However, the definition of the attack cost in (Garcelon al.) (020) is different from that of our paper. The cost of the reward attack is defined as the cumulative differences between the post-attack rewards and the pre-attack rewards. The
paper is the first paper that discusses the action poisoning attack against
5

---

Published in Transactions on Machine Learning Research (02/2023)
cost of the action attack is defined as the number of rounds that the attacker changes the actions selected by the agent. Although the definition of the attack cost of these two different kinds of attacks are different, the attack cost of our proposed white-box attack strategy scales on O(log(T))), which is same with the results in (Garcelon et al. 2020
As mentioned the introduction, the goal of this paper not to promote any particular types of poisoning attacks. Instead, our goal is to understand the potential risks of action poisoning attacks, the safe applications and design of robust contextual bandit algorithm relies on the addressing all possible weakness of the models.
4 Attack Schemes and Cost Analysis
In this section, we introduce the proposed 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 attack strategies 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 (Li et al. 2010 The LinUCB algorithm is summarized Algorithm 2 The main steps of LinUCB are obtain estimates of the unknown parameters 0, using past observations and then make decisions based on these estimates. Define +() (s: S I, I, i) the set of rounds up to I where the agent pulls arm i. Let N₂(() |r;( Then, at round t, the ég-regular least-squares estimate of 0g with regularization parameter À > is obtained by Li et al. 2010)
-v=
Σ KET((I-1)
(4)
where
V4,1
Σ (En((t-)
T2at + AI
with I being identity matrix.
After 0,'s are obtained, at each round, upper confidence bound of the mean reward has to be calculated for each arm (step 4 of Algorithm 2 Then, the LinUCB algorithm picks the arm with the largest upper
confidence bound (step 5 of hm 2). By following the setup in "optimism in the face of uncertainty
linear algorithm' (OFUL) (Abbasi- Yadkori et al.) 2011). we set
w(N) = VAS + R222og K/8 + dlog (1 + L2N/(Ad))
and
B., = (N) = VAS + 2/0 dlog (1+
It is easy to verify that w(N) is a monotonically increasing function over N (0, +00)
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 atlack scenario, the attacker knows the coefficient vectors 0,'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
Our proposed attack strategy works as follows. When the agent chooses arm K, the al aackrr does not al lack.
When the agent chooses arm 1 * K, the attacker changes it to arm
{ [K with probability
10
(5)
4 with probability 1 1-6
6

---

Published in Transactions on Machine Learning Research (02/2023)
Algorithm 2 Contextual LinUCB (Li et al. 2010)
Require: X, K T, L, S.
1: Initialize for every arm i, V1 + AI, b, + 0, 0 + bi
for t 2....... T do
Observe the context 2t--
Compute the upper confidence bound: Pt, +- x. 0; + Pe. V xn for all arm E [K].
Pull arm I, = arg max; Pt.s-
The environment generates reward r according to arm Le The agent receive rt.
V1, < Vr, + Iety br, + br. Tette Ór, t Vi.
end for
where 1f arg min; (Te, 0,) and
(12, 0x) ( (Ie, 0x) - (1n, 0.)
Et
(6)
We now explain the main idea behind the allack strategy specified in Equation Bnd Equation 6 Intuitively speaking, using Equation 5 and Equation G 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 0x. For any arm i * K, because of the attacks, the agent will obtain an estimate of arm i's coefficient vector that is close (1 - x)xxx. This can be seen as follows. Under Assumption [ and the fact that the mean rewards are positive, we have that 1/2 E 11-a. Under the white-box attack, when the agent pulls non-target arm * K, the post-attack action 1 is a random variable and the mean reward received by the agent should satisfy
Elr,, 1 4.] [x 0p))1 edte,, 0k) + (1 ea) min( 0,) = () 0k).
(7)
Because the positive mcan reward assumption and the fact that a < 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, shown in the following proposition.
Proposition 1. For 8 > O. Suppose the agent employs linear contertual bandit algorithm whose cumulative pseudo-regret is upper bounded by o(T) with probability at least 1 1 5. When using the proposed white-bor allack scheme, with probubility al. least 1 - 8, the allacker can force the agent to pull the larget arm for T - o(T) times, while the total attack cost IC) is upper bounded by o(T).
Proposition D 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 2 We first build a high probability bound for the estimate of parameter at the agent, when the agent computes the estimate of 0, by equation 4 andd the attacker employs the white-box allakk. Recall that w(N) = VXS + R2/2 2 log K/8 + d (1 L.2N/(dd).
Lemma 1. Under the proposed while-box allack, the estimate of 0g for each arm i oblained by LinUCB agent as described in Algorithm 3 satisfies
|o] 0. - xz (1- a1)xkl S (w(N((t) + /0.5lo (2KT/8) || leaelly.:
(8)
with probability 1 - 2(K - 1)6/K, for all arm i + K and all t 2 0. Here, [allv = Vx norm of vector x for a posilive definile malvia V.
Vx Va
the weighted
Lemma Ishows that, under our white box attack, the agent's estimate of the parameter of non-target arm, i.c. 0,, will converge to (1 - a)0x. Thus, the agent is misled 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.

---

Published in Transactions on Machine Learning Research (02/2023)
Theorem 1. Define ? min 0k)- Under the same assumptions in Lemma 1 for any 8 > 0 with probability of least 1 - 28, for all T 2 0, the allacker can manápulate the LinUCB agent into pulling the target arm in at least T - [C] rounds, using an attack cost
IC| $ 2d(K 1) (a7)2
log (1 (1+ ((TT/((A))) (2w(T) + 0.5 (2KT/6) 2
Theorem shows that white-box atlack strategy can force LinUCB agent into pulling the target amm T - (log T) times with attack cost scaled only as T).
Proof. Detailed proof of Theorem can be found in Appendix B.3 idea.
Here provide sketch of the main proof
For round and context Vt, if LinUCB pulls arm o K, we have
x 0. + BL,K v a V S x De. + Pesy ze Ve, It.
Since the attacker does not attack the target arm, the confidence bound of arm does not change and 2. 0K S xt. 0z + Br, / ooVV holds with probability 1 x-
Then, by Lemma
0x S x (1 a]0x + &ellleelly +
1 LS
log
2KT
+ w (N((1)) Ieillvs
(10)
2
By multiplying both sides [4,= and summing over rounds, we have
[1==13 0K
(11)
T
2KT 5
K
(1+
L (2N((K)
)) ||
(+=1)
BKi VAS LS
log
+ R
2 2 + dlog
1+
Ad
Here, we use Lemma from
Abbbasi-adkorri al. 2011 and obtain
T
tL?
Σ
1 (1=i)
1 aelll S
(((22dllgg 1
(12)
dx
1=1
Set 7 min Ox) Since N:(1) Ei 1[1==1); we have
N:(1)= < (2 log 1+
tL dA
2VA5 + LS
log
2KT
+ 2R
2 2
+ dlog 1
tL?
(13)
Xd
4.3 Black-box Attack
We now focus on the more practical black-box setting, in which the allacker does not know any of arm's coefficient vector. The attacker knows the value of a (or a lower bound) in which the Equation holds for all Although the attacker does not know the cocfficient vectors, 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.
8

---

Published in Transactions on Machine Learning Research (02/2023)
The proposed black-bos box attack strategy works as follows. When the agent chooses arm K, the attacker does not attack. When the agent chooses arm 1 + K, the attacker changes it to arm
{
K with probability
1
(14)
I
with probability 1-c
where
1. arg min of
(LEL, 022)) =
(15)
and
8/ di (w)))(()) LS (2KT/8))
6. = 1/a when i + K and ox = 2, and
(1 - (12,, 06 (1re, 60 On,1)
4 = clip
(16)
2'
(1r, Op,k) - (1r, 00 00,1))
with clip(a, x, b) = min(b, max(x, a)) where a S.b. b.
For notational convenience, we set 1, = K and e when 4. = K. We define that, i K,
(t) = {s s 1 =
and N((() = (t)). We also define (t) = {s : s S t} and (x( = (
00, = (Vi.) -1 Σ
(17)
(t-1(
where
Σ
TRTE + AI
NET!
and
1/a
if i = 1 K
Wt.j 1/(1 6t)
if 1 1!
(18)
if i 1
Here, 0g is the estimation of 0, by the attacker, while d., in Equation is the estimation of 0g at the agent side. We will show Lemma and Lemma that 09 will be close the true value of 0, while Or will be close a sub-optimal value chosen by the attacker. This disparity gives the attacker the advantage for carrying out the attack.
We now highlight the main idea of 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 - a)0x: hence the agent will think the target arm is optimal. In the black-bor setting, the attacker does not know the coefficient vector for any arm. The altacker should estimate an coefficient vector of each arm. Then, the attacker will use the estimated coefficient vector replace the true coefficient vector in the white-box attack scheme. As the attacker does not know the true values of 0,'s, need to design the estimator 62, the attack choice I! and the probability & carefully. In the following, we explain the main idcas behind our design choices. 1): Firstly, we explain why we design estimator 09, using the form Equation 17 in which the tacker employs the importance sampling to obtain an estimate of 0, There are two reasons for this. The first reason is that, for successful attack, the number of obscrvations arm i + K will be limited. Hence if the importance sampling not used, the estimation variance of the mean reward (x, 02) at the attacker side for some contexts may be large. The second reason is that the attacker's action is stochastic when the agent
9

---

Published in Transactions on Machine Learning Research (02/2023)
pulls non-target arm. Thus, the attacker uses the observations at round t when the attacker pulls arm with certain probability, i.e. when 1 E T, to estimate 0.. Since the agent's is action is deterministic, the agent uses the observations at round t when the agent pulls arm i, i.e. when t E T, to estimate 0,. 2): Secondly, we explain ideas behind the choice of ! in Equation 15 Under our black-box attack, when the agent pulls non-target arm Ie + K, the mean reward received by the agent satisfies
Ei FF-11 Tt] = Ea,, F 74] = ce( 0x) + - (1), 12²)-
(19)
In white-box attack scheme, I3 is the worst arm at context 2t. In the black-box setting, the attacker does not know a priori which arm is the worst. In the proposed black-box attack scheme, indicated in Equation 15 we use the lower confidence bound (LCB) method to explore the worst arm and arm I/ has the smallest lower confidence bound. 3): Finally, we provide reasons why we choose e, using Equation 16 In our white-box attack scheme, we have that 1/2 < 4 < 1 a. Thus, in our black-box attack schome, we limit the choice of 6r to [1/2,1 1 - al. Furthermore, in Equation t used for the white-box allack, 6, is computed by the true mean reward. Now, in the black-box attack, as the attacker does not know the true coefficient vector, the attacker uses cstimation of 0 to compute the second term in the clip function in Equation [6
In summary, our design of 02.,- 1 and can ensure that the attacker's estimation 0g is close to 0;, while the agent's estimation d.. will be close to (1-a)0k. 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 82 at the attacker side. We establish confidence ellipsoid of (Iz, (9,)) at the attacker.
Lemma 2. Assume the attacker performs the proposed black-box action poisoning attack. With probability 26, we have
| TTTO. - x xT S &L (l
(V7.)
holds for all arm and all 2
Lemma 2 shows that 0 lies in an ellipsoid with center at 0g with high probability, which implies that the attacker has good estimate. We then analyze the estimation &g at the agent side. The following lemma provides an upper bound on the difference between rll-,, and (1 - (xx 0k)-
Fr-1,
Lemma 3. Under the black-bor attack, the estimate obtained by an LinUCB agent satisfies
El Ft-1, It] - (1 -1- a1- (1 (1- [stel (VC.))((
(vCx)) 1 + (1 + 3 (,1 1|:1|1
(20)
V/
simaltancously for all t 2 0 when 4 # K, with probability 1 -68
The bound Lemma consists of the confidence ellipsoid of the estimate of arm I and that of arm K. As mentioned above, for a successful attack, the number of pulls on arm I will be limited. Thus, in our proposed algorithm, the attacker use the importance sampling to obtain the estimate of 6,, which will increases the number of observations that can be used estimate the coefficient vector of arm I!. Using Lemma we have the following lemma regarding the estimation Oz,i at the agent side.
Lemma 4. Consider the same assumption as in Lemma 2 estimate ô,, obtained by the LinUCB agent will satisfy
With probability at least 1- (3K 1)4 K
the
[x] 0., xT & (1 (1+ K log (1 + 1L2 (L2/(d))) (w(0) LS (2KT/6))
(21)
simullaneously for all arm + K und all 1 2 0.
Lemma 4 shows that, under the proposed black- box attack scheme, the agent's estimate of the parameter of the non-target arm, ie. d,, will converge (1 - a0 Hence 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.
10

---

Published in Transactions on Machine Learning Research (02/2023)
Theorem 2. Define "y mingep(e, 8k). Under the some ossumptions in Lemma 4 with probability at least 1 36, for all T 2 O, the allacker can manipulate LinUCB agent into pulling the targel arm in al least T -CI rounds, using an attack cost
2
|C| = 2d(K - 1) (a7)2
2 4d
TL di
log (1 + (1+TL>/(da)) (w(T) + LS LSV 0.5 (2KT/6)
2
log 1+
(22)
Proof. Detailed proof of Theorem can be found in Appendix C.4 proof idea.
Here we provide a sketch of the main
For round and context 2t, if LinUCB pulls arm o K, we have
x 0,K + Br of Vi x 0c. + Bes of Veli It.
Since the attacker does not attack the target arm, the confidence bound arm does not change and o. OK S x. 0r,x k + 8e, / of Ve holds with probability K
Thus, by Lemma
24 0k Sx. (1 - a)Ok + +N(N(tt))
4d Klog
(22) ))
(u(0)
(KT log
(23)
+
( dd
Ls
lIaelll,, 1-
2
By multiplying both sides by 1 ((==)) and summing over rounds, we have
11= 0k
(24)
4d
kL2
2KT
1 [m==))
2
K log
1+
w(t) + LS
log
| lly
d)
2
8
Herc, we use Lemma 11 from
Abbasi- Yadkori et al.
2011 and get
T
(1+ II?
(m==)) | 1 S (1)2ddlog
(25)
dd
R=
Thus, we have
T Σ
(.(1)=
1 [[m=))
k=1
(26)
? LL2) dA ))
2
2d
(1+
tL2² +1²2)
4d
(1
(w()) + LS
2KT 8
< (a7))
log
2
V
KKlog
log
dA
where 7 = min (x. 0x)
Theorem shows that our black-box attack strategy can manipulate a LinUCB agent into pulling a target arm T Olog T) times with attack cost scaling Ollog* T). Compablack with the result for the white-box attack, the black-box attack only brings additional log T factor.
11

---

Published in Transactions on Machine Learning Research (02/2023)
4.4 Generalized Linear Models
We note that the proposed allack strategies can also be extended to generalized linear models. Detailed analysis of the cost of the proposed attack strategies for the generalized linear contextual bandit model can be found in Appendix D
5 Numerical Experiments
In this section, we provide numerical examples to illustrate the impact of proposed action poisoning attack schemes.
5.1 Attack Linear Contextual Bandit Algorithms
We first empirically evaluate the performance of the proposed action poisoning attack schemes on three contextual bandit algorithms: LinUCB (Abbasi- Yadkori et al. 2011), LinTSS (Agrawal & Goyal 2013), and e-Greody. 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 (- - / Thus, ||>|| S v2, ||01|2 S v2 and mean rewards (x, 0) > 0. The reward noise tit drawn from a Gaussian distribution (00, 0.01).
Jester dataset (Goldberg et al., 2001): Jester contains 4.1 million ratings of jokes in which the rating values scale from 10000 to +0.000. We normalize the rating to [0, 4J. 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 drawn from a Gaussian distribution 0.0,0.01).
MovieLens 25M dataset: (Harper & Konstan, 2015) 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 consider 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 W0 0.01).
We set 8 = 0.1 and X = 2. For all the experiments, we set the total number rounds T = 10 and the number of arms K = 10. We independently run ten repeated experiments. Results reported are averaged over the len experiments. We set to 0.2 for the two proposed atlack strategies, hence the target arm may be the worst arm in some rounds. Each of the individual experimental runs costs up 10 minutes on one physical CPU core. The type of CPU is Intel Core 17-8700.
White box attack on LinTS Black-box sllack LinTS box attack
-lackbor box attack on LinUCB
White box attack Greeady
0.5
Black-box sllack GGeeedy
Timetti
S/10
Tieot)
<110
Tinetti
Figure 2: The cumulative cost of the attacks for the synthetic (Left), Joster (Center) and MovicLens (Right) datasets.
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 lincar as the target arm is not optimal for most context. Table show the number of rounds the agent pulls the target arm among 10 total rounds. In the synthetic dataset, under the proposed white-box attacks, the target arm is pulled more
12

---

Published in Transactions on Machine Learning Research (02/2023)
Synthotic
Jester
MovicLons
G-rreedy without atlacks
2124.6
5908.7
3273.5
White-box attack on e-Greeedy
982122.5
971650.9
980065.6
Black-box attack on e-Grooody
973378.5 5
939090.2 2
935293.8
LinUCB without attacks
8680.9
16927.2 2
13303.4 4
White-box attack on LinUCB 981018.7
911676.9
969118.6
Black-box attack 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 nunber of rounds when the agent pulls the larget arm over T = 10 rounds.
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 Lin LCB.. Fig 2 shows the cumulative cost of the attacks on three agents for the three datasets. The results show that the attack cost [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 lincar contextual bandits.
5.2 Attack Robust Algorithms
We now discuss existing robust linear bandit algorithms (Ding et al. 2022 Bogunovic et al. 2021 and evaluate the performance of the proposed attack strategy on these algorithms.
In particular, (Bogunovic et al., 2021 focuses on special case in which the context and coefficient vectors are assumed to be fixed over rounds, and developed Robust Phased Elimination (RPE) algorithm. In contrast, our paper focuses on the general setting where the contexts are different for each round and coefficients are different for each arm. Hence the RPE algorithm will not work for the contextual bandit setting consideblack in our paper. (Bogunovic et al., 2021 also proves that a simple greedy algorithm based on linear regression can be robust to linear contextual bandits with shablack coefficient under a stringent diversity assumption on the contexts. We empirically evaluate the action attacks on the greedy algorithm in (Bogunovic et al., 2021 The greedy algorithm is designed in the shablack coefficient setting and may not work in the disjoint sctting.
(Ding et al. 2022) provides a linear contextual bandit algorithm that is robust to rewards attacks and context attacks. The scheme in (Ding et al. 2022) could be used to defend against the action attacks. However, our numerical results show that the proposed attack strategy can successfully defeat the scheme in (Ding et al. 2022). In the following, we empirically evaluate the performance of the proposed action poisoning allack schemes on RobustBandit algorithm in (Ding et al. 2022).
(He et al.
2022 provides nearly optimal algorithms for linear contextual bandits with adversarial corruptions. He et al.
2022 consider two cases: 1) the agent knows the corruption budget; and 2) the agent does not know the corruption budget. We also empirically evaluate the action attacks on CW-OFUL algorithm in
(e et al.
2022
We set 8 8= 0.1 and X = 2. For all the experiments, we set the total number of rounds T = 10 and the number of arms K = 10. We independently run ten repeated experiments. Results reported are averaged over the ten experiments. We set a to 0.2 for the two proposed attack strategies. For the action attacks on CW-OFUL algorithm, two cases that the agent know the corruption budget and the agent does not know the corruption budget. For the case that the agent know the corruption budget, we set the attack budget to 3000 and the attacker will stop the attack the budget is exhaust. For the case that. the agent does not know the corruption budget, we does not limit the attack budget.
We use the same synthetic data setting in Section 5.1
run the simulation
the
The simulation results in Figure 3 show that our proposed white-box action poisoning attack can force the greedy contextual agent in (Bogunovic et al. 2021 to pull the target arm. Although the black-box
13

---

Published in Transactions on Machine Learning Research (02/2023)
Figure 3: The cumulative cost of the attacks against greedy contextual algorithm in (Bogunovic et al.
2021
action poisoning attack strategy fails, it causes linear regret on the agent. The greedy contextual algorithm in [Bogunovie et al.] 2 highly relies a stringent diversity assumption on the contexts. In the disjoint sctting, the agent will pull each arm in some correlated contexts. The stringent diversity assumption may not be salisfied in disjoint setting. The greedy contextual algorithm in [Bogunovie el al. 2021] will induced to linear regret as shown in Figure
x10
Cost
0.5
White box attack RebustBandit Black-box etlack RebustBendit
2
8
10
Time(t)
x10
Figure 4: The cumulative cost of the attacks against Robust Bandit algorithm for the synthetic datasets.
The simulation results in F that our proposed action poisoning attack can force the RobustBandit agent to pull the target arm with T - o(T") times. The attack cost also scales sublinearly on T. The reason why the BabustBandit agent cannot defend against the action attacks is that its regret scales on OCVVT). If the attack cost O(VT), the regret will be linear and the agent will fooled.
x10
Aback Cora
was on dhe
Troe Pagget
What foc slan 5O0 CRUL unMMON
Timett)
<10
Figure 5: The cunulative cost of the attacks against CW-OFUL algorithm for the synthetic datasets.
The simulation results in Figure 3 show that our proposed action poisoning attack can force the CW-OFUL agent to pull the target arm the case that the agent does not know the corruption budget and the attack budget is unlimited. The attack cost also scales sublinearly on T. The reason why the CW-OFUL agent cannot defend against the action attacks is that its regret scales ((T) once the corruption level is larger
14

---

Published in Transactions on Machine Learning Research (02/2023)
than VT. CW-OFUL agent can defend the action poisoning attack and achieve sublinear regret when the agent knows the corruption budget and the attack budget is limited.
5.3
The Attack Performance When the Assumption Violates
x10
7
White-box attack on e-Greeedy
Tolal Attack Costs
6
Black-box attack on e-Greeedy White-box attack on LinUCB
5
4-
Black-box attack on LinUCB
3
White-box attack on LinTS
2
Black-box attack on LinTS
0
0.1
0.2
0.3
0.4
0.5
The proportion of contexts when the larget arm is the worst
Figure 6: The total costs of the attacks for the synthetic datasets when the Assumption | violates.
We now evaluate the sensitivity of the proposed algorithms on Assumption D We empirically evaluate the performance of the proposed action poisoning attack schemes on three contextual bandit algorithms: LinUCB, LinTS, and e-greedy, when the target arm is the worst for some contexts.
We use the same synthetic data setting in Section 5.1, We set d 8= 0.1 and X x= 2. For all the experiments, we set the total number of rounds T 10 and the number of arms K 10. We independently run ten repeated experiments. Results reported are averaged over the ten experiments. We set to 0.2 for the two proposed attack strategies. We manipulate the simulation environments so that the proportions of contexts, at which the target arm is the worst, are separately controlled around: 0.001, 0.01, 0.02, 0.05, 0.1, 0.2, 0.5.
The results in Figure D show the total costs under different proportions of contexts when the target arm is the worst. The z-axis represents the proportions of context when the target arm is the worst. The y-axis represents the total cost over 10 rounds. The results shows that the total attack costs scale linearly on the proportions of contexts when the target arm is the worst. When the proportions of contexts when the target arm is the worst is small, our proposed attack strategies still efficiently attacks.
5.4
The Attack Performance When the Rewards Are Normalized in [-1,1]
Here, we would like to note that we make the positive reward assumption for the formal analysis, our results actually can be generalized to the case with negative rewards. If the positive reward assumption does not hold, for the case with negative rewards, the attacker can preprocess the reward by adding a positive constant to all rewards such that all rewards become positive. As long as Assumption holds, the proposed attack strategy can mislead the agent believe that the target arm optimal regardless of the positive reward assumption.
To illustrate this, we evaluate the performance of the proposed algorithms when negative rewards exist. We use the same synthetic data setting in Section 5.1 We set ő = 0.1 and X = 2. For all the experiments, we set the total number of rounds = 10 and the number of arms K = 10. We independently run ten repeated experiments. Results reported are averaged over the ten experiments. We set to 0.2 for the two proposod atlack strategies. We normalize the rewards in [-1,1]. The attacker preprocesses the rewards by adding constant = to the rewards in his algorithms. In the white-box attack setting, the attacker adds e = 3 to every (x, 0) and use the preprocessed (x, 0) to compute er. In the black-box attack setting, the attacker adds = 3 to every reward rt and use the preprocessed r, to compute ① and et-
15

---

Published in Transactions on Machine Learning Research (02/2023)
15 x10
White-bou attack on LinTS Black-box attack on LinTS
White-box attack on LinUCB
Cost
Black-box attack on LinUCB
White-box attack on e-Greeedy
Black-box attack on e e-Greeedy
2
4
6
10
Time(t)
x100
Figure 7: The cumulative cost of the attacks when the rewards are normalized in [-1,1].
The results in Figure show that our proposed attack strategies still work for the case with negative rewards.
6 Future Works
In this section, discuss several future directions.
Linear Bandits with Shablack Coefficients. In this paper, we discuss the disjoint linear contextual model, similar to those consideblack in (Li et al.) 2010 Kong et al. 2020 Garcelon et al. 2020 Huang et al. 2021), where each arm is associated with its own coefficient vector. At each time, the agent observes a contextual vector xe that is shablack with all arms.
Our model different from the linear contextual bandit model with shablack coefficient. In that model, the coefficient vector l" is shablack with all arms. At each time, each arm is given a specific contextual vector Z4, These contextual vectors form the decision set. The decision set changes over time and can even be infinite. In this model, adversarial attacks may not always be successful. For example, (Wang et al. 2022) shows that some allack goals can never be achieved in linear stochastic bandits due to the shablack coefficient. This may also occur in the linear contextual bandit model with shablack coefficient. is of interest to conduct rigorous analysis of action attacks the shablack cocfficient model in the future work.
Attack Strategy without Assumption 1. In Section 5.3 we empirically evaluate the sensitive of the proposed algorithms Assumption ! The results shows that the total attack costs seem to scale linearly the proportions of contexts when the target arm is the worst. It is of interest to further theoretically analyze the phenomenon shown in the simulation results in Section 5.3 However, using current tools analysis developed in the paper, it is challenging to formally analyze the relationship between the effectiveness of the action attack strategies and the portion of contexts when the target arm the worst. On the other hand, we can try find new algorithm that can force the agent to choose the target arm when the target arm is not the worst. In the following, we provide our initial ideas for this direction.
In the action attack strategies consideblack in the paper, the attacker misleads the agent to obtain estimate of the non-target arms' coefficient vectors that are close to (1 - a)0x- However, this can not be always achieved without Assumption ! since the target arm is the worst at some contexts but (1 - a)0x is worse than the target arm. Action attacks can not force the agent to Icarn (1 a)ok- We need some new aakk strategies. Here, we provide our initial thoughts on theoretical insights to solve this challenge in the white-box attack scenario.
If the Assumption 1 docs not hold, we set
Dx == (x EDDD (x. 0x) min (x. 0,))
iE[K]
16

---

Published in Transactions on Machine Learning Research (02/2023)
the set of context where the target arm is the worst. We consider such sequence of contexts ( that Et E DD for all 1 < Tx and Tx linearly depends on T.
We consider a r-neighborhood of Dr:
DK == UzEDx (x),
where (x(x) = (x' E D ||-- - < r). In the white-box atlack case, we can find a coefficient. vector Of such that x Ok > x T for all context I Dx and x zT0x > T for all context D/Dx. Then the attacker force the agent to obtain an estimate of the non-target arms' coefficient vectors that are close to ot, Then the target arm is the optimal in D D/Dx, and the distribution of Dr is limited.
The proposed atlack strategies in this paper may make the larget arm to be the optimal in D/Dx with some r. Thus, even when the target arm is the worst arm, the attack algorithm designed in this paper can still work.
Ii is of interest to conduct rigorous analysis of this statggyy in the future work. Furthermore, it is of interest to carry out the design and analysis for algorithms for the black box attack strategy under this scenario, which will be more challenging.
7 Conclusion
In this paper, we have proposed class of action poisoning attacks on linear contextual bandits. 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. We have also shown that our white-box attack strategy can force LinUCB agent into pulling a target arm T- (log² T) times with attack cost scaled as O(log" T). We have further shown that the proposed black- box attack strategy force LinUCB agent into pulling target arm T- O(lg T) times with attack cost scaled O(log" 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.
8 Acknowledgement
This work was supported in part by the National Science Foundation under Grants ECCS-1824553, CCF- 1908258 and -CCS-200041.
References
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312 1-222222220,, 2011.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payolls. In Pro- ceedings of the 30th International Conference on Machine Learning, Proceedings of Machine Learning Research, pp. 127 135, Atlanta, Georgia, USA, 17 19 Jun 2013. PMLR.
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, pp. 262-275. Springer, 2017.
Ilija Bogunovic, Arpan Losalka, Andreas Krause, and Jonathan Scarlett. Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pp. 991-999.
PMLR, 2021.
Olivier Chapelle, Eren Manavoglu, and Romer Rosales. Simple and scalable response prediction for display advertising. ACM Transactions on Intelligent Systems and Technology (TIST), 5(4):61:1 61:34, December 2014. ISSN 2157-6904. doi: 10.1145/2532111 URL Inttp:///ol acm. org/10 1144/2232222
Ferdinando Cicalese, Eduardo Laber, Marco Molinaro, et al. Teaching with limited information on the learner's behaviour. In International Conference Machine Learning, pp. 2016-2026, 2020.
17

---

Published in Transactions on Machine Learning Research (02/2023)
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-1320, 2019.
Sanjoy Dasgupta, Daniel Hsu, Stefanos Poulis, and Xiaojin Zhu. Teaching a black-boo learner. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 1547-1555, 2019.
Qin Ding, Cho-Jui Hsich, and James Sharpnack. Robust stochastic linear contextual bandits under adver- sarial attacks. In International Conference on Artificial Intelligence and Statislics, pp. 7111 7123. PMLR, 2022.
Elvis Dohmatob. Generalized no free lunch theorem for adversarial robustness. In Proceedings of the 36th International Conference on Machine Learning, pp. 1646-1654, 2019.
Zhe Feng, David Parkes, and Haifeng Xu. The intrinsic robustness of stochastic bandits to strategic manip- ulation. In International Conference on Machine Learning, pp. 3092-3101. PMLR, 2020.
Evrard Garcelon, Baptiste Rozicre, Laurent Meunier, Jean Tarbouricch, Olivier Teytaud, Alessandro Lazaric, and Matteo Pirouta. Adversarial attacks on linear contextual bandits. In Advances Neural Information Processing Systems, pp. 14362 14373, 2020.
Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins. Figentaste: A constant time collaborative filtering algorithm. information retrieval, 4(2):133-151, 2001.
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, pp. 4036-4043, 4043, New York City, NY, Feb. 2020.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pp. 1562 1578. PMLR, 2019.
F Maxwell Harper and Joseph A Konstan. The moviclens datasots: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1-19, 2015.
Jiafan He, Dongruo Zhou, Tong Zhang, and Quanquan Gu. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. arXiv preprint drXiv:2205.06811, 2022.
Ruiquan Huang, Weiqiang Wu, Jing Yang, and Cong Shen. Federated linear contextual bandits. Advances Neural Information Processing Systems, 44:27057-27063 2021.
Yunhan Huang and Quanyan Zhu, Deceptive reinforcement learning under adversarial manipulations cost signals. In International Conference on Decision and Game Theory for Security, pp. 217-237. Springer, 2019.
Kwang-Sung Jun, Lihong Li, Yuzhe Ma, and Jerry Zhu. Adversarial attacks on stochastic bandits. In Advances in Neural Information Processing Systems, pp. 3644 3653, Montréal, Canada, Dec. 2018.
Weihao Kong, Emma Brunskill, and Gregory Valiant. Sublinear optimal policy value estimation in contextual bandits. In International Conference on Artificial Intelligence and Statistics, pp. 4377-4387. PMLR, 2020.
Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan. Cascading bandits: Learning to rank in the cascade model. In International Conference on Machine Learning, pp. 767-776, Lille, France, July 2015. PMLR.
Lifeng Lai,, Hesham El Gamal, Hai Jiang, and H Vincent Poor. Cognitive medium access: Exploration, exploitation and competition. IEEE transactions on mobile computing, 10(2):239 253, Feb. 2011.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalizod news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670 2010.
18

---

Published in Transactions on Machine Learning Research (02/2023)
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pp. 2081-2080. PMT.R, 2017.
Fang Liu and Ness Shroff. Data poisoning attacks on stochastic bandits. In International Conference on Machine Learning, volume 97, pp. 1112-055,, Long Beach, CA, June 2019.
Guanlin Liu and Lifeng Lai. Action-mannpplation attacks against stochastic bandits: Attacks and defense. IEEE Transactions on Signal Processing, 68:5152-5165, 2020a.
Guanlin Liu and Lifeng Lai. Action-manipulation attacks on stochastic bandits. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3112 3116, 2020b.
Guanlin Liu and Lifeng Lai. Provably efficient black-box action poisoning attacks against reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Stochastic bandits robust to adversarial cor- ruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pp. 114-122, Los Angeles, CA, June 2018. ISBN 978-1-4503-5359-9
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, pp. 186-204. Springer, 2018.
Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu. Policy poisoning in batch reinforcement learning and control. In Advances in Neural Information Processing Systems, volume 32, 2019.
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, pp. 1765 1773, 2017.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via en- vironment poisoning: Training-time adversarial attacks against reinforcement learning. In International Conference on Machine Learning, pp. 7974-7967 2020.
Amin Rakhsha, Xuezhou Zhang, Xiaojin Zhu, and Adish Singla. Reward poisoning in reinforcement learning:
Attacks against unknown learners in unknown environments. arXiv preprint rrXtt:2102.08492 2021.
Anshuka Rangi, Haifeng Xu, Long Tran-Thanh, and Massimo Franceschetti. Understanding the limits of poisoning attacks in episodic reinforcement learning. In Proceedings of the Thirty-Fire First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 2394-3400 International Joint Conferences on Artificial Intelligence Organization, 2022.
Vidit Saxena, Joakim Jaldén, Joseph E Gonzalez, Mats Bengtsson, Hugo Tullberg, and lon Stoica. Contex- tual multi-armed bandits for link adaptation in cellular networks. In Proceedings of the 2019 Workshop on Network Meets AI 8 ML, pp. 44-49, 2019.
Yanchao Sun, Da Huo, and Furong Huang. Vulnerabiiit-awwaee poisoning mechanism for online rl with unknown dynamics. In International Conference Learning Representations, 2021.
Christian Szegedy, Wojciech Zaremba, Tlya Sutskever, Joan Bruna, Dumitru Erhan, Tan Goodfellow and Rob Fergus. Intriguing properties of neural networks. In International Conference Learning Representations, 2014.
Huazheng Wang, Haifeng Xu, and Hongning Wang. When are linear stochastic bandits attackable? In Proceedings of the 39th International Conference on Machine Learning, pp. 23254 23273, 2022.
Yisen Wang, Xingjun Ma, James Bailey, Jinfeng Yi, Bowen Zhou, and Quanquan Gu. On the convergence and robustness of adversarial training. In Proceedings of the 36th International Conference on Machine Learning, volume 1, pp. 2, 2019.
Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive seward-poisoning attacks against reinforeement learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. -1234, 2020.
19

---

Published in Transactions on Machine Learning Research (02/2023)
A Necessity of Assumption 1
In the main paper, we show that, if Assumption 1 holds, our proposed attack schemes can successfully attack LinUCB regardless the context.
Here, we highlight the necessity of Assumption | in the sense that, if Assumption does not hold, for some
sequence of context (Ee) there is no efficient action poisoning attack scheme that can successfully attack LinUCB. If the Assumptioo does not hold, we
DR = for E (i
min (ar, 0t) (E(K]
as the set of context where the target arm is the worst. We consider such sequence of contexts (arherr that 2, E Dx for all t < Tx and Tx lincarly depends on T.
If the attacker does not attack the target arm, the target arm is the worst in Dx- No matter how we change the non-target arms to another arm, the cost and loss will linearly depend on Tx and therefore linearly depend on T.
If the attacker attacks the target arm when He Dx and changes the target to better arm the optimal arm that the agent learns that the target set is optimal even in the context set Dx, the cost of atlack may be up to O(Tx) and hence scales O(T). We define
TK TK.(K-I((t) {s: st:sst,le K but + + K}
as the set of rounds up to I where the attacker attacks arm K and Cx(() = |TK, as the attack cost of attacking arm K. We can show that if we attack the target arm, for any attack scheme,
110, 0xllvxx S IVER
Σ
LSRallvi.
-ETK,IK-I(0)
Σ
LS x.
Vi
aETx(ix-1(0)
(27)
< LS Ck(()
Σ
|< 1.8
(ETx,(M-1)(()
NK (t)
< LS
2dCx (t) log
1+
d)
where the last inequality is obtained by the Lemma 11 from Abbasi-- Yadkori et al. estimation error of the mean reward of arm K is bounded by
2011 Then, the average
Tx
1/TK
1 (0., - -kk]
Tx
<1/Tk
1 0x exll ll
(28)
<2dLSlog
1+
NK dA
VCR(TK)/TK
Note that we consider a sequence of contexts {ax herr that x; E DR for all t < TK and t linearly depends on T. In the action poisoning attacks, the attacker tries blackuce the rewards of non-target arms, he can change the non-target arm to worse arm the worst arm. However, the target for all t Tk- The mean rewards of the non-target to x 0g. If the attacker tries force the agent to pull the target arm in linear time at the first Tk rounds, the attacker needs to let the post-attack arm K be A-optimal than the original arm K. If the attacker tries
K is the worst arm at the contexts {at)et]Tk] must be larger or equal
20

---

Published in Transactions on Machine Learning Research (02/2023)
to let the post-attack arm K be A-optimal than the original arm K, we have Ck Ö(Tx), where Ō ignores the logarithm dependency.
In summary, without the prior information of the context distribution or the context sequence, there is no action poisoning attack scheme that can always efficiently attack without Assumption [ However, some situations, some action poisoning attack scheme may still work even if the target arm the worst a small portion of the contexts, shown in the numerical result session.
B Attack Cost Analysis of White-box Setting
B.1 Proof of Proposition 1
When the agent pulls non-target arm + K, the mean reward received by the agent should satisfy
[B-1,4]] = (1-a) (21,
In the observation of the agent, the target arm becomes optimal and the non-target arms are associated with the coefficient vector (1 a)0k. In addition, the cumulative pseudo-regret should satisfy
T
T
0k) 2 Ry Σ (u
1 11
We define y (2, If Ry is upper bounded by o(T), Et (1 is also upper bounded by oT))
B.2 Proof of Lemma i
If the agent computes estimate of 0g by equation 4 and V (ENET(t-1) Iz0% + +11, we have
z 0 x IT[[1
a)0k
=x, T
Σ
24 Vo Vo. - a0)0x
KET((I-1)
(29)
=x, V23
Σ
Ib Tr, -11 (1- (1-a)xT08) (xxxx))
Ax, 1 -a)6K
(tT.(t-1)
Σ
Fe Vi- Ik
Fg 0, + mE a))x0x 0x) -x. -00kk
(En((-1)
and by triangle inequality,
x 0 x7 (1 - a)0kl
(30)
Σ 2. Vina 2b (xT 01 - (1 -1)xxxx 0xx)
+
Σ
x. T
Ve, 2x77 + + Ve (1 aa)xxl
(E)((-11
kEr.(t-1)
Now we separately bound the three items in the RHS of Equation 30
(1) In model, the mean reward is bounded by 0 (x,, 0,) 131.113100.133 LS. Since the mean rewards are bounded and the rewards are generated independently, we have 0 S n._ 0 (1 a)a 0x S LS and El 0rp [1- = (1-ol -a)x 0k, where the post-attack action 17 is the random variable. Thus, x. (T, aa Or - - -a)x ) (tE is a bounded martingale difference sequence w.r.t the filtration (Fr)ken((-1)-
21

---

Published in Transactions on Machine Learning Research (02/2023)
Then, by Azuma's inequality,
P( Σ
It Ve. I/k ( (1 a)oā0x² 12 B)
kET:(t-1)
-2B²
(31)
exx
Exer,(t-1)
(2g Vi,i Iu LS)2
=Pr
where B represents confidence bound. In order to ensure the confidence bounds hold for all arms and all round simultaneously, we set Pt, = KT so
2KT log
2KT
B = LS
Σ
(e V xx)² xx)²
& LS
log
| lly 2
(32)
8
2
(t-:(t-1)
where the last incquality is obtained from the fact that
| li = It VoT
Σ
T + AI
Vintor xe
KETx(t-1)
2 x V
Σ
Virlos
(33)
KET(((-1)
Σ
(x.VV Ve, xx)
REr:(e-1)
In other words, with probability 1- Ö, we have
Σ
Vis (x - -(1 -1- -(1aa)=T0k) 0k)
$ LS
log
2KT 8
Izelly
(34)
(t-,(I-1)
for all arms and all t.
(2) Note that V. = Ek 2 + XI is positive definite. We define (1,8)v = x. VVy as the weighted inner-product. According to Cauchy-Scwwarz inequality, we have
Σ (ET:(t-1)
Tall
|
Σ (t
(35)
Assume that 2 L. From Theorem and Lemma 11 in (Abbasi- Yadkori et al. 2011 we know that for any 0, with probability at least 8
K det( ( -1/2 1/2
Σ
< 2R² log
TR (t-1(t-1)
5
(36)
K 2 2log
(1 L2N,(t))
))
< R²
+ dlog
g
Ad
for all arms and all > 0.
(3) For the third part of the right hand side of Equation
30
Ax V a)0xl < [|(1 a.) A0 llv, 1,o
(37)
22

---

Published in Transactions on Machine Learning Research (02/2023)
Since Vi, 2 AI, the maximum eigenvalue of Ve, 1 is smaller or equal to 1/X. Thus,
1 |(1 - a1)) $ x 11( x))0x11 S 22
In summary,
By 005 - x.c [ - =k)0kl
1
2KT ô
K
L L2N((t))
))
(38)
a)-a) + L
log
+ R
2
dlog
1+
|æellyz'
Ad
B.3 Proof of Theorem 1
For round and context 24, if LinUCB pulls arm i o K, we have
x k + BrK v al Vi S x de.: + Besy 27 Ve,i It.
Recall Br, VĀS + /V/ 2 2
K 8 + dog 12N,(0) Ad
Since the attacker docs not attack the target arm, the confidence bound of arm does not change and zTOK Ok S 0n fe, / oo ar holds with probability 1- R- Then, by Lemma 1
F. 0 Sx, 0. + 8e.K V 1i Vi
Sz T 0.,5 + Br,s x7 ViTiaa
(39)
2KT
(N(())) ) Islllvas
Sx (1 0x + Br, loell
LS
log 8
By multiplying both sides [4r= and summing over rounds, we have
(22 0k
(40)
T
2KT 5
L (2N,(k)
)) ||axllleet
(1==1)
BR,i+ + VĀS + LS
log
+ R 2 log
+ dlog
1+
2
Ad
Here, we use Lemma 11 from
Abbasi- Yadkori et al. 2011 and obtain
T
S 2d log(1 + N2(2)L2
U+=
||=0||1011
dx
1=1
(41)
IL?
< 2d log
1
dA
According to Etn 1 11.=0 & Ni(1) Ei= 14 | 1ل we have
T
I1,2
Σ
1 [ S (i(t)ddlgg
1
(42)
dl
23

---

Published in Transactions on Machine Learning Research (02/2023)
Thus, we have
12=10004 Ok
Arm
(43)
1122) (12)) (1+
dA )
2KT
K
dlog (1+ t1?
N((t)2dlog
LS
log
+ +VVSS + 2R1
2
1+
2
8
Ad
and
T
(1==
k=1
(44)
1
1L2
1
2KT
K dlog
tL2
Ni(1)2d log 1+
LS //
log
21og 2VĀS + 2R
1
07
dx
Ad
where y = mingeD (z, 0x). Since N;(t) = EEEz ((==1), we have
2d
LL2
2KT
K dlog
112
(.) < (an)²
log 1
2VA5 + T.S.
log
2R
2 2log
1+
(45)
Ad
C Attack Cost Analysis of Black-box Setting
C.1 Proof of Lemma 2
Since the estimate of 0, obtained by the agent satisfies
00. = (V%))- -1
Σ
WK.TFK.10 ).
(46)
(t-1(
we have
x 0
x 0:
=xm (V.))
Wk - x (Vo0) -1 V2,0s
KET/
=xm (V2))
(Wi. J 0z)orx
-xx7 (V2.) 0:
kE-/(t-1)
=x (Vi.)
Σ
(Wisst 01g- 0,)0a
(tr(((-1)
+ x (Vo.) -1
-ay (V2))= 0,
Wk.alkk
(E-)(1-1)
Now we separately bound the three items in the RHS of Equation 47
(1) We have 0 < ww O1g =r < TKS and Elur,, 0rg Fe-1] 2h 0,, where the post-attack action
To is the random variable. In addition, by the definition of wk,s, have that wae S 1/a if + K,
24

---

Published in Transactions on Machine Learning Research (02/2023)
and Wkii & if K. Thus, ( Eker/(e-n(Wu.. 01 - } (er.(t-1)
also a bounded
martingale difference sequence w.r.t the filtration {Fr (Fe)te)(t-1). By following the steps in Section B.2 have, with probability K
K-18, 8, for any arm & K and any round t,
LS
2KT 8
Ft (Vei)
Σ
(Wk
0.)=
S
log
1 (va))
2
(1-1(
and with probability 1 - Ō, for arm K and any round t,
2KT
2 (Vi,))
(ww.Kak 01g-
2x0x)5 xxxx)²x 2z
I 2LS
V
log
| (VPx)
(t-1)
(2) The confidence bound of the second item of the right side hand of Equation 47 can be obtained from Equation 36 With probability, K-1 8, for any arm + K and any round t,
K + dlog (1+ L2NT(() log
R
2y (V%))
Σ
WkK
S
1+
|1 [[vel
(47)
Ad
KET, (t-1)
With probability, 1 oo for arm K and any round t,
2t T
(VoR))
Σ
Wk.K Tk
S 2R,
2 2
K dlog 1+
I2N
L
(48)
Ad
AET (t-1)
(3) For the third part of the right hand side of Equation 47
Axx (V2) 0,1 s || [10.11(22)) | ([2))((v))) S VĀS |2 (2)))(
(49)
In summary,
Jxp 00: - xz TToll
2KT 8
K log
LAN! (t)
(50)
<s:
ViS+ VāS+ LS
log
+ R.
dlog
1
||
8
Ad
where 1/a when i + K and Øx 2.
C.2 Proof of Lemma
Recall the definition of ex:
(1 (2,, 86,x) - (I O0 t.11)
G clip
1
(51)
2'
(xe, 80,xx) - (2,, 80
(,
and the definition of T!:
/ = arg min K
(lrr, 02,) -
(52)
25

---

Published in Transactions on Machine Learning Research (02/2023)
By Lemma 2 (re, 80 (.1!) -/.. ( )-1 I min 0t) with probability 1 26.
Because c, is bounded by [1/2, 1 a), we analyze Elr, Fr-1; Ie] in four cases.
Case 1: when (Te, 0g,x) < (Fe, 00 t,1!? and = 1 - a, we have
Fe Ipl = (1 (22,,, + ta(x 01))
(53)
Then, by Lemma 2
(1 - a) 0k + az, 0r! - -1)-) 0x
S(1 (1l-a) a) of (2T08xx + flx (xxlleel(veex)
00 lif
+ 3000 ||=eell
(1 11)=)( a)x 0x
1o
t.1?
(54)
sz, 80 t.
+(1 - S. | (12l a.5
||
- (1 - -x) 0x
5(1 a) | ((e)) (1 a1) (,17 1|zll
-1,
Va
where the second inequality is obtained by the condition of Case 1 and the last inequality is obtained by n, go 800
||
I (x, 02) and Assumption 1
V..!!
On the other side, we have
01: - (1 - aa)x 0k = ax, 023 2 0. (1 - a)2, 0k + axx ax;0,;
(55)
Case 2: when (Fe, 09,x) 2 (re, @0 02,,)) > (1 20) 07,x) and e: = 1/2, we have
1 E E(r,11///-111 4c] (1x, 0k) (eee 01))
(56)
Then, by Lemma
[ 0x + x x=] -a)x
1
I 01 -(1 (1-201) =1= 0x)
1
x4 t.1
T 0
+ 32. ||20|1
-1-(1- (1- 20)xx 0k
2
vo
1,2
$180
||sa|l
1.17
yo 1.1
where the last inequality is obtained by 2.
80
50
||ee||
< min, (x,, 0:) and Assumption
t.
t
26

---

Published in Transactions on Machine Learning Research (02/2023)
On the other side, by Lemma 2
J 0K + o 01;) (1 10)xx 0x
T
T T0 24 t.1
|2ell
1 (1
2a) (xT0h.x [1-a)]
Bl,x 1 (v2l)()gg)))
2
(57)
re
6.17
2 2 1.11
300 ||,|||
-1
2 (1 1-20)) xxlltelll (xex))))
Vo 6.]
where the last inequality is obtained by the conditions of Case 2.
Case 3: when 0 & (me,
60 (.1 s (1 (1, 0f,x)) and 1/2 < & S a, we have
1g 4. c, 0x) + (1 (o) 01)))).1)))
(58)
We can find that
<x 0k) + (1 (z), 01)) (1)- (1 (21, 0k)
=e(((2 0k) (It: 01 )) (Iz, (1:) (1 a) (T=; 0k)
=er((xe, 02,k) )- - ( 00 1,1 )) + (Tt, 01:) - (1 x)) (Tr, 0k)
+ (e 00 (1,1)) (2x, (11)) ) + er Ex((2r, 0k) (Et, 02,x))
(59)
-(1 () 02,x) (x,,, (., + (rr, ( 017) - (1 x)) (Ii,, 0x]
+ ce((11 80 ((.1)) - (me, 01,)) + ce((2re 0x) (Ie, 06,k))
=(1 - a -()
(me. 02,xx) - (ze. 0x)) + (1 -Ee) ( 00 Or,,, (1r. 012))
which is equivalent to
E Elrr, rol Fi-1, Lc] - (1- a) (2 0x:
<(1 (e) (ig,Il1z 1| [[vo]] (1 k0).30.1 2,19
|sell
(60)
(vo.
1.27
Case 4: when (1e, 80 0,,;)) 0 and e 1 a, we have
Bir 1 (1 -a)(z2, 0k) af(x 01)).
(61)
Then, by Lemma 2
(1 a)x, 0x axx 01: - (1 -a)x 0x
=ox, 0,;
San, 00,r
0,000 e.
||e
-1
(62)
sa.0 t,1 ||Ee||
1,
vo 5.1
where the last inequality is obtained by the condition of Case 4. We also have
(1 a)2 0x + ca. aTTO; (1 axa 0x = axr 0₁3 2 0.
(63)
27

---

Published in Transactions on Machine Learning Research (02/2023)
Combining these four cases, we have
Blre, 10.r.19//i11,44 18--1,41
(1- (1 0x)
<(1 2)) ( + (1 0x) ||
(64)
6,17
-1.
Vo 1.]
C.3
Proof of Lemma
From Section B.2 we have, for any arm + K,
| Br, - x4 x
Σ
Tt Vi di x 0r. -1 -o)a +
Σ
Vesa Fx +
V.7 (1))
(tT((t-1)
(t
Σ kET((--1
Ty Vise 2b [ rpp - ex (xkx,00k) - (601-x)((o ( 0 012))
(65)
Σ REri(t-1)
Te Vela Is
V--ta
(et + (x)( 01) (1 a))
Σ (En((I-1)
x ViS IAll
+ V1 a0)kk))k
Now we separately bound the first item and second item in the RHS of Equation 65
The bounds of the
third item and fourth item in the RHS of Equation 65 are provided in Section B.2
(1) Since the mean rewards are bounded and the rewards are generated independently, we have s 0r cx 0k) (1 (IK 0 < LS and 11 = e 0k) (1 <x), 0z)).
Then x. V dn (IT 01 E[x 01gl Fi- kEr,(t-1) also a bounded martingale difference sequence w.r.t
the filtration ( (Fa)ken((-1)- By following the steps in Section B.2 we have, with probability 5, for any arm i and any round t,
2KK log 6
Σ (ET;(1-1)
2 VV 2b 0g - BBaT (ggFFFFFF)))
S LSS
|
(66)
(2) From Equation 33 in Section
B.2
have
| |
2
Σ
(of Vo- x2
V
(67)
(t-:(t-1)
28

---

Published in Transactions on Machine Learning Research (02/2023)
Then, the second item of the right hand side of Equation 65 can be upper bounded by
Σ (ET(((-1)
Li Ve,e ti (EN(Ex, 0k) + (1 Ex)(er, (1 a)xz [x)
Σ
(Elr..rg/Fss111 [u] (()))))
E
(1) Ves' xx)²
(C-1()-1)
V
(ETI(1-1)
(68)
)
Σ (ET((t-1)
(1 + a)
||
| laxllv..?
2,
Va kit!
where the first inequality is obtained from Cauchy-Schwazz inequality, the second inequality is obtained from Lemma 3 and Equation 33
addition, by the fact that (a+ < 2a² + 2b2 for any real number, we have
Σ (tT((t-1)
(1 xl0alll + (1 a))5
||
vo Nish
(69)
2
Σ (11 (1= || (12)) +
Σ
(1+ + ax
||
k.1
-1
kEr((I-))
(tr((t-1)
vo R.1
Here, we use Lemma 11 from (Abbasi- Yadkori al. 2011 and get, for any arm i,
1+ NHUUL 2dlog (1+ d)
112
Σ
I leve S 2d
dA
(70)
kET
By the fact that E, (i 1) = [/t(t= 1), and ΣiSK Te(t -1) 1)= ELEK T/ 1), we have, for any arm i,
T(( 1) (1 - 1), and Ti(1 - 1) C EjjR r3 (1 16l11). 1). Thus,
1L?
Σ
|
Σ
|| | 2d 1 11
(vo R.
dx
(71)
(t-((t11)
(t-1)
and
1+ (1+ tIa
Σ
|xx|2 1
-1
| | S 2(K 1)dlog
dA
(72)
kEr((t-1)
V4
Ki RET/((-1)
k.17
29

---

Published in Transactions on Machine Learning Research (02/2023)
By combining the definition of Ph,, Equation 69
Equation
71 and Equation
72
we have
E (t)(
(1 (1- 1 (v2xx) -
+ (1 +1++0 a))
|
po mith
(Bxxllzal(rra)) )
Σ (ET((t-1)
+
Σ
2
2,30 ||
kEr.(1-1) 1)
k.rl
(73)
2KT
tL?
S16d
w(1)+ + LSS
log
log
+
dA
16d (1)
2KT 8
tL?
w(t) + LS V
log
log
1
a²
dd
16d2K K a²
(2KT)
LT,
w(t) + LS
log
log
1+
6
yd
In summary, we have
| 0z,4
x1 (1 a00xx
4d
tL2
(<(1) + LS
2KT
(74)
K log
1
log
| l
d)
C.4 Proof of Theorem
?
For round and context 21, if LinUCB pulls arm + K, we have
x T0 + Re,K v o7 Vi S xx Ae. + Be, / 27 Ven Vi-tan Fz.
In this case, Re, = w(N((t)) = VäS 22og K 3 + dlog (1+
L.N.(()) Ad
Since the attacker does not attack the target arm, the confidence bound of arm does not change and z.T Txxx I x.. 0e,x + Se, / nr Vi holds with probability 1
Thus, by Lemma
3y 0g Sxz T 00, + Be, xt VV. x
Sx T (1 a))xx + (NN)(ll)l
(75)
+ 1 + 4d
(1 +x+tt) (w(t)= - LS
(2KT)
K log
2 log
||relly,
By multiplying both sides by 1 ((r,))) and summing over rounds, we have
(1=ajaa/ Ox
(76)
T
2+ 4d
k12
))
(2KT)
(Tu=i)
V
log
1+
dA
w(t)) + LS
log
5
|| llv.
k=l
30

---

Published in Transactions on Machine Learning Research (02/2023)
Here, Lemma 11 from
(Abaasi- Yadkori al. 2011 and get
S 2d 1 N2
tL?
1 (==1) [
- 2d
1
(77)
dd
dd
According to Ex=1 1 (+= [==nl|loxllly?? & V (a(1)) Ek=1 1 (12=1) 2 (axl2y- بي have
(1==1) xxx = S (1(122dlog (1+ dd
11
112
(78)
Thus, we have
(79)
N. (t)
(1+
tL?
2+ 4d
K log
1+
tL? 112
)
w(t) + LS
log
(KT
d2
dA
2
and
T
N:(1) Σ
[+==)]
k=1
(80)
S 2d log
IL2
4d
1+ LL2 dA
))
(w(() + I.S
2KT
2
{ar))
(1+
dA
2 +
V
K Klog
log
5
where 7 = mingep (1r, 0k)
Attacks on Generalized Linear Contextual Bandits
In the generalized linear model (GLM), there is a fixed, strictly increasing link function μ -> such that the reward satisfies
Mt.4 (1 01.)) + T)s
where t/ is a conditionally independent zero-mean R-subgaussian noise and (.)) denotes the inner product. If we consider the o-algebra F. - :/), dp becomes F, measurable.
Hence, the expected reward of arm under context 2, follows the GLM setting: E[re,] = ((( 0,)) for all and all arm i. One can verify that p(z) leads to the linear model and μ(z) = exp(x)/ (1+ exp(()) exp(x)) leads to the logistic model.
We assume that the link function f is continuously twice differentiable, Lipschitz with constant ky and such that cu infege.ren Aax ((x) T)) O, where á denote the first derivatives of p. It can be verified that the link function of the linear model is Lipschitz with constant ky 1 and which of the logistic model is Lipschitz with constant k; 1/4.
The agent is interested in minimizing the cumulative pseudo-regret, and the cumulative reereo-regret for the GLM can be formally written as
T RTT Σ (u(((e;01:)) (r))))
(81)
where 1 = arg max; (((2,,0.)))
For the GLM consideblack here, μ is a strictly incrcasing function and I arg max; p (x,, 0.)) arg max, (ax 0.). As the link function j is strictly increasing, the target arm is the worst arm under Assumption
31

---

Published in Transactions on Machine Learning Research (02/2023)
D.1 Overview of UCB-GLM
For reader's convenience, first provide a brief overview of the UCB-GLM algorithm (Li et al. 2017 The UCB-GLM algorithm is summarized in Algorithm 3
The algorithm is simply initialized by play every arm j times to ensure a unique solution 0 for each ar We assume that after playing arm times, V3 invertible and the minimal eigenvalue of V, is greater or equal to Åo for all arm i. We assume that 24 is drawn iid from some distribution with support in the unit ball and set Σ = ]. Proposition in (Li et al. 2017 shows that there exist positive, universal constants D1 and D2 such that Amia (V.) 2 Ao with probability least - 8, as long as
Divd+ D2v D2vlog(1/0)
+ 2Ao
JZ
(82)
Amin )
Amin (2)
Algorithm UCB-GLM Lii et al. 2017
Require:
number of arms K, number of rounds T, number of initial rounds j.
Initialize for every arm
Play every arm J times. At each time, update VI, Vt, + ZT
for t KJ + KJ + 2..... T do observe the context
5: for i= 1,2,..., K do Calculate the maximum-likelibodd estimator ò; by solving the equation
6:
Σ
(nn (xxTT,))
(E
Compute the upper confidence bound: Pt. t x. 0, + Bu 17 V, m
8:
end for
Pull arm I, arg max, Pt,s-
10: The environment, generates reward r, according to T
11: The agent receive Tt.
12: V1, + Vi. + J42
13:
end for
By following the setup in (Li et al. 2017), set Sr,
28 cp
log K + dlog (1+ 1.2N((t) And for GLM.
D.2 White-box Attack Strategy
Similar to the white-box attack strategy for linear contextual bandits, the white-box attack strategy for GLM works as follows. When the agent chooses arm K, the attacker does not attack. When the agent chooses arm I, + K, the attacker changes arm
with probability
70
(83)
I!
with probability 1-c c2
where 1t = arg min O,) and
m(11 (x1, 0k)) - p(min (xre, 0.))
6,
u((x,, 0x)) - j(min, (xe, (xte00) 0,))
(84)
The attacker can manipulate the agent into learning some particular coefficient vectors. In particular, for K (the target arm), the agent obtains the true coefficient vector 0x. For any i * K, because of
32

---

Published in Transactions on Machine Learning Research (02/2023)
the attacks, the agent will obtain estimate of arm i's coefficient vector to be close to (1 a)0xx Under the white-box attack, when the agent pulls non-target arm 1 * K, the mean reward received by the agent should satisfy
Fe-1,, - p((1 - (I,, 0k)).
Proposition 2. For 5 O. Suppose the agent employs a generalized linear contertual bandit algorithm whose cumulative pseudo-regret is upper bounded by o(T)) over T with probability at least 1 5. When using the proposed white-box allack scheme, with probability at least - 6, the atlacker can force the agent to pull the target arm for T - o(T) times, while the total attack cost |C| is upper bounded by o(T)).
The proof of Proposition 2 is provided in Appendix E.1 To further illustrate the proposed attack scheme, we now provide finer analysis the impact this attack on UCB-GLM described Algorithm 3
Lemma 5. Under the proposed white-bor bor attack, the estimate of 0, for each arm # K obtained by UCB- GLM agent as described in Algorithm 3 satisfies
LS + 2R
K log
I2N((t) Aod || llv.
1 OT, z7 (1 a00x1
+ dlog 1+
(85)
Cp
The proof of Lemma 5 is provided in Appondix
E.2
Theorem 3. Define
minzED (zz, 0k). Under the same assumptions as in Lemma for any 5 > 0 with probability at least 28, for all T 2 0, the allacker can manipulate the UCB-GIA GLM agent inlo pulling the target arm in at least T [C] rounds, using an attack cost
11? ICI S 4d(K 1) log 1 dAu (ar))2
(
(2kyLiS +
2k LS 4R
2
K log ④
+ dloo (1+ 1,T 12T))
And ))
(86)
The proof of Theorem is provided Appendix
D.3
D.3 Black-box Attack Strategy
The modified black-bor attack strategy for GLM works as follows. When the agent chooses arm K, the attacker does not attack. When the agent chooses arm 4 # K, the attacker changes it to arm
K
with probability
7
(87)
r
with probability 1-
where
1f
arg min i
(ar, B2,) 3.. - (ll
(88)
and
ky LS +
R
K
(2) And
86,
20,
log ④
dlog
1+
(89)
Φi
&u. epa
when i K and Φx =
by, and
1((1 a)x, 0g u12
00
Cy
2,17
a Cp
6 = clip
(90)
Cu th
u(xT0g,x) plx 00 02.1)
kip
with clip(a, x, b) = min(b, (ax a)) where a b. b.
For notational convenience, set IJ = K and = 1 when I, = K. We define that, if K, 7/ = {s: 11 i) and NT(1) (r/(0) (1)= {8:8 1) and N (1) 1rk (1)
33

---

Published in Transactions on Machine Learning Research (02/2023)
Calculate the maximum likelhooo estimator 8i, by solving the equation
(Wi,ann 01x = O.
(t- 1)1
where V2 = -ker!(-11)BB)) Tbth
1/er
i = 1 = K
W1,s
1/(1 62)
if 19 11 i 10
(91)
First, we analyze the estimation 0% at the attacker side. We establish a confidence ellipsoid of (m,, 00 at the attacker.
Lemma 6. Assume the attacker performs the proposed black-bor action poisoning attack. With probability 28, we have
| T 6%,
x.
0sl S BY, 22 (vo.)-
(92)
holds for all arm and all 2 simaltaneoussy.
The proof of Lemma i is provided in Appendix
E.4
Lemma 7. Under the black-bor boz attack, with probability 1 1-28 28, the estimate obtained by an JCB-GLM agent satisfies
Elre,po/Fi-1 Tt] 10(1 -a), 0x) 2 (leelll + 2k 2k, 22211122l1
simullancoussy for all t when T + K.
Lemma 8. Assume the attacker performs the proposed black-boz action poisoning attack. With a probability least K the estimale Ōz,; oblained by the UCB-GLM agent will salisfy
1 00, xx7 -1)x00
2k LS + +2R
16k
tL2 1+
tr2) dio
K log
L2t And
(93)
1+
K log
+ dlog 1
|,0||
Cμ
C
simullaneously for all arm i K and all 12122 0.
Theorem 4. Define y min (x. Assume the attacker performs the proposed black-bor action poisoning atlack. For any 8 > 0 with probability at least 1 - 25, for all T 2 0, the allacker can manipulate the UCB-GLM agent into pulling the target arm in at least T |C| rounds, using an attack cost
|C| Ad(K 11) (2k LS + (ar)3
TL2
log
1
Cμ
ddo
2
(94)
K log dog (1+
I2T
16k2,d C
TI2 1+
K Klog
And
dAo
The proof of Theorem 4 is provided in Appendix E.7 Theorem can manipulate UCB-GLM agent into pulling a target arm O T) times with attack cost scaling as Oloog T). Compablack with the result for the white-box attack, the black-box attack only brings an additional log T factor.
g shows that our black- attack strategy
34

---

Published in Transactions on Machine Learning Research (02/2023)
E
Attack Cost Analysis of GLM
E.1 Proof of Proposition 2
Let us consider a contextual bandit problem PI, in which the arm K (the target arm) is associated with a fixed coefficient vector 0x and all other arms are associated with the coefficient vector (1 a)0x. For a generalized linear contextual bandit algorithm s we suppose that the cumulative pseudo-regret regret of algorithm of for the problem P1 upper bounded with probability at least 8 by a function (I)(T) such that (T) o()) o(T).
Under the proposed white-box attack, when the agent pulls non-target arm 4 + K, the mean reward received by the agent should satisfy E[ra,1 Ft-1, Ii] μl(1 - a) 0x)). In the obscrvation of the agent, the larget arm becomes optimal and the non-target arms are associated with the coefficient vector (1 (1-a)0x- For the agent, the combination of the attacker and the environment form problem P1. The cumulative pseudo-regret should satisfy
RT
1u (# ((x,, - u ((re, (1- a)0x)))
T Σ 11
which is equivalent to Σ LUzRy s Rr Rr/(c))). Since Rr is upper bounded by fa(T) o(T), |c|
Σen
[44K) is also upper bounded by o(T).
E.2 Proof of Lemma
The Maximum--lkeliiene estimation can be written as the solution to the following equation
Σ (rn Oc.))a,
(95)
(t
EnE (xxT0))=m Sc. (0.,)) Ener(e-1) Tn Since μ is contimuuusly twice differen- tiable, Vga, is continuous, and for any 0 E O, (o),(0) Ener(e-1)) In (xxT Vgr,(()) denotes the Jacobian matrix of It,s at 0. By the Fundamental Theorem of Calculus,
Define (0)
(r,s(O.s)) - ((, - a)0k) = (0, - (1-c0 al)0)xx)
(96)
where
G = ('VgL. (s0L, + (1 s)(1 -x)0x) =))1-<x)0k)
(1-s)(1
ds.
(97)
Note that Vgr,(() EmEr((-1) En [xxx ()). According to the assumption that eμ infoce. juxx () > O, we have Gr,, 2 en Vi,i 2 e. C.V... 2 AoT > O, where in the last two step we used the assumption that the minimal eigenvalue of V, is greater or equal to An after playing arm times. Thus, GG, is positive definite and non-singular. Therefore,
- = Gr. (o..(0.) 9r,((1 - a)lx))
(98)
For K, (0.) (0k( Ener((--1) Mn
35

---

Published in Transactions on Machine Learning Research (02/2023)
For all arm i + K, the right hand side of Equation 98 is equivalent to
(0.)(0.) - ge,i a)0x)
Σ (In 14(1 a 0x Tn
nE
(99)
Σ
(u(m, 11(1 -a)s 0k ))
Σ
Mn
nET:(t-1)
nET((1-1)
We set Z1 = EnET)(t-1)(((())) 012) -u((11 - -x)x and Zz = En nn
We have (0.) (() = 21 + Z2 and
x4 (0. (1 - -a)0x) = I G (Z) + 72).
(100)
For any context a E D and arm i + K, we have
Ir T (0r, - (1 - xx)xx]
rr (T + Z2)1
(101)
$ <1r GIr Z1| + |x T G Zz|.
We first bound |x G Z2). Since Ge is positive definite and G 1 is also positive definite, |x T G. S || 122lla,,7
Since Ge, ž cu Ve, implies that G I op 4,
we have || S Jou læll, holds for any x Rd. Thus,
G Zzl S - - Zz Zellv
(102)
Cp
Note that Vú, V4, + AI. Hence, for all vector x E Rd
| | = || y + (Ve.) Vila )r.
(103)
Since (A+ BB+ = --1---1BA B)-1,
Vi = Ve.1 -VV
(104)
The above implics that
<x [V V.
(AV 1 Ve.e
(105)
|| 12=
Ao
and | 2- S (1+
Xa |=
From Theorem 1 and Lemma 11 in (Abbasi- Yadkori el al. at least 1 1-6
2011 we know that for any 8 > 0, with probability
K det det(AI)-1/2
<2R² log
(ET((t-1)
(106)
K <2R² (log
1 Lt),(t)
))
+ dlog
Xd
36

---

Published in Transactions on Machine Learning Research (02/2023)
for all arms and all > 0.
Set À = λo we have
K ||2lll,, S <2 log 8
(22)(11)
+ dlog
1+
(107)
Aod
Now we bound |x G Z. Similarly,
x GT Z11 S 4p
|| p
(108)
In our model, we have 0 < (1e, 0,) S | 00:1 _ LS. Further,
|u(z T 0p)) p((1 -a)= 0k)
kp
I 01g. - (1 -a)x 0K
(109)
S LB
Since we have Eiu(2T (1g) = ((11 a) 0k), { (u(o] 01g) - ((1 a)) kEr,(t-1) a bounded
martingale difference sequence w.r.t the filtration {1 (t-( and is also
From Theorem 1 and Lemma 11 in [Abbasi- Yadkori et al. 2011 we know that for any 8 > 0, with probability
15 at least K
K
+ dlog (1+ L²N:(1))
Iz ? S LS log
(110)
dod
for any arm i K and all 0. In summarr, for all arm i + K;
LS 2R
K
1 Nc)
T - -a)0000)=
log 8
+ dloog
|
(111)
Cn
And
E.3 Proof of Theorem
For round and context 24, if UCB-GLM pulls arm + K, we have
TTO,KK + Br, o7 Vinkan x 0e + Bes x. Ve, Ft.
Recall Br, Gn log K dog (1+ (aN(()) Aod
in GLM.
Since the attacker does not attack the target arm, the confidence bound of arm K does not change and nI xTOx 0x S xt 0z,x + Br, / af Ve holds with probability 1- K
Thus, by Lemma
1 0x Sx, 0,, + 3r,K V 2, Vi
Sx, Ons + Be,1 1/ T.V. -ra
Sz, 0,, + 2k LS + 2R
Cu
3r,
12 V 2s + Br 2V at
Vi
(112)
Cn
2R
<0 (1 - a000 + LS 2R
B Be.ll=
R
37

---

Published in Transactions on Machine Learning Research (02/2023)
By multiplying both sides (s)=)) and summing over rounds, have
T
T S
LL +
2R
(1= ar 0K
Σ
1
(1=i))
Se Seallzellez?"
(113)
R
k=1
Here, Lemma 11 from Abbasi- Yadkori et al.
2011 and obtain
(1+
tI?
U1 (1am)) 1ox 1 = S 2ddlog[+
2d
(114)
dA
dA
According to Ex=1
11 Ilollly & (((t) ((,==)) || 122 ve.!" we have
Σ
T
| S Ni()2dlog (1+
tL?
(115)
dd
1=1
Set Ao, we have ||
S (1 + )|||]| = 2|1-012 Thus, we have
T
k,LS + 2R
tL?
1 111=0000 0x s
Ben (N,(t)dlog
1+ dAo
(116)
R
km
and
4d
tL?
(R..L.. + 2R 2
N.(t)= Σ (1a=]) S (az)2
log 1+
dAg )
Be,
(117)
R
where 7 = m (2. 0k)-
E.4 Proof of Lemma 6
The attacker calculate the maximum-lkkllihodd estimator 00, by solving the equation
Σ
(Wn,Tn (.)x,,))) 0.
(118)
(EF
Note that (.( = Ener! (1-1) ((xx,0))z,, (.,0 = Ener)((-1) Wn.innia-
For all arm
-9,,(0))
Σ
(Wn,ira - [1(x11 0,))san
(t-((
(119)
Σ
((11T00)) +
Σ
Wniihhnnn
nEr(((-1)
NET,
Similarly, we set Za = Ener (t-1) Un and Zs = Ener/((-I)wunn)) 010) - 1n(1 - -.)x).00
We have o., (0,,) (0,) 7g + 74 and
2 1,1 - 02) = =x] (G.,) -l -( + Zz),
(120)
38

---

Published in Transactions on Machine Learning Research (02/2023)
where
C2 = S Vol. (sOf, +1 (1-s));) ds.
(121)
For any context x E D, we have
x T T0 - 81)l
x (Gt,)) + +Zal
(122)
x (G (G |x (G - -Zal
We first bound |x (G),) (Zz). We have
|o (CT Zzl
S 5-|| (
(123)
where V. = EnEnn((--)) In
Note that V. + AI. Hence,
1 (Pg) 1 =1|Zal )- Z3 - -(VE))--
(124)
1 ) 2 1 (y..--
5(1
From Theorem 1 and Lemma 11 in (Abbasi- Yadkori et al.
2011 we know that for any 5 > 0, with probability
at least 1 -
K det (det(Ve,)) det())) -1/2
<2R² log
(ET((t-1)
(125)
K
1+ (1+ (t),(())
Ad ))
log 8 <2R²
+ dlogg
for all arms and all > 0.
Set A = Ao we have
K log 5
1 (2N
12all < 200, Ro
+ dlog
(126)
Agd
Now we bound |x (GG,)) Similarly,
1
1x (G -Z
- | -1=llogg-~
(127)
Cμ
In our model, we have 0 < (x,, 0,) < | 11.111 L.S Further,
0 <
Wk.iH(Z 2 01g) (0(1 a)z s o.k,LS.
(128)
Since we have (u 01)) ((x: (ww.a((xT0rp) 1 (5T 0:) difference sequence w.r.t the filtration {Fi)ien((e-)) and is also LS LS-sLb---uaaaa Saauussian-sb-Gaussii
(ET((t-1) is bounded martingale
From Theorem 1 and Lemma in (Abbasi- Yadkori et al. 2011 we know that for any > O, with probability
al least 1
K
(2N And
| livl S LS log
dlog
1+
(129)
39

---

Published in Transactions on Machine Learning Research (02/2023)
for any arm i + K and all f > 0. In summary, for all arm i + K;
Ls + R
K
x (0: (1)-)xxx] s 20,
log
dlog
1+
(130)
Cp
Agd
E.5 Proof of Lemma 7
Recall the definition of G::
pu(1 axxx 02 (2,k) u(x, 80 02.15)
Cp
= clip
Cu kin
Mlx1 00 00.k) p10) 80 00,1!)
a
(131)
and the definition of r::
1. arg min if
(0,) -lol1=e ((
(132)
By Lemma 6. (Iz, 2.12) 56 Ileellloo
(.1.) )- S min, 0.) with probability 25. Thus, with probability
28, u (.1?) - min, plxx 0,) S k t,1 | "..:)"
Because is bounded by loyth, 1 - a 1 we can analyze E|ra,g F1 in four cases.
Case 1: when (1e, 0f,x) < (1t, 00 02,)) we have = 1- a Su and u((r,, 0g,x)) < ml( 00 (?,))) Thus,
E Fr- = (1 - a So )((x 0x) + a Cu p( 01))) ky
(133)
kn
Then, by Lemma
6
(1
Cu ky
[x 0k) + a - u1zz 01)) ) pd(1 a)2, 0k)
ky
<(1
Cy ky
(1(xz 09.0x) + kn || (V2x)) + Cp
plxx u(IT 00 02.1)) + + k ||oel| 1
)
ky
po
-m((1 - a22 [x][Ox) 0x)
(134)
Su(x,
T (..))) + ac 00
||-e|l
+1 (1
a Cu
)k
30 || (10x)) p((1 - ax) 0k)
pa 2.17
111
Skk, ( (l=ell
+ (ky + ac,))00
1.19 ||
where the second incquality is obtains by pl(ar 02 < pl (10,, 80 () and the last incquality is obtained by (.))))
nxxx ) min; p(xTT0) 0,) k t. Il1ellleo, ;- and Assumption
40

---

Published in Transactions on Machine Learning Research (02/2023)
On the other side, we have
(1 a CH (1 [x) + cp ulzz 01:)) (1x) 1e(11 a)zi 0k)
kp
2(1 a (
ky
p1xx 07,x) - k |keell (Pic))
+ a
ky
Cu
plxx 02.1)) - k
2,1,
|
po
- 1d(1 - =a) 0x)
2 0g,k) - 1M(1 - -a)x 0x) acuu
(1
Gp a
)kin || (1xe)((
(135)
kn
po
2 0xk) 1M(1 a)xx 0x) acui
(.17 ||12|||
Cp )kp || (vex)(()ex==
po
(2kg - ac (aexll/ellll1 - acu. 1|2111
-1
po
Case 2: when ua 02, (2,k) 2 ulx1 80 (.,2))
> (1 + 9z
((((1 - ax)2 02,k)
- Gn
u(21 0g,k)
and at
we have
ky
App
Efr Ft-1, =
Cp Cp kp
ulæt 0x) +
ky p(xT
(136)
Cp + kp
By Lemma with probability 1 1-28,
plx 0,.;)) min p(x 0.) S kn an [Eeellpo )-
Since min; xz 0, (1- 20)22, 0x, we have
Max (0.1)) S p((1 20)x 0x) K a. tis! )-
and then
u(x7 m(xT0,;) - (((1 22)x2 0k) + 2k,3,, IIeellloo
Thus,
cup(xTT01) 0x)
+ kpp(z1 (11)
(u((1 [xk
Cy + k2
Cp. + kr
Cn
(xxxxx)=
0x)
(((1 a)oo7 0x)
Cp kpp
Cp + kin
bu
ky
+
uxxz [0;))
ce(11 axx2 0k)
(137)
Cn
kip
Cp ky.
(u(x²) TllT00r0 0k)) - :M(1 - -a)xz 0k))
+ kyp
Bi
2k2
(u((1 22x) 0x) 11(1 aa)o 0k))
ou + k 22,1
Iseellio )-1 (po) css
Cu + k
41

---

Published in Transactions on Machine Learning Research (02/2023)
According to the definition of ky and en and Lemma 6
Cuf((x, + kumlar 01;)
11(1 a) 0k) cu Ki
cu + Kip
kp (x,0x- 0x - -11-)) 0k) +
((1 2a)x 0x - (1-a)z) 0k)
Cu + kp
Cu Ki
(138)
2k
30
||
Cau + kip
1,1
2k
80
|I )-1
cu + kp
t.l.
t.1
In addition, by Lemma 6
knullx O11)
Cuulat 0x)
-(((1 aa22 0x)
cu kp
cH + kp
caplar 0x)
knulIz 01:) :1((1 a)2; 02
cn + Kp
CH + kp
+ +[((1 -a)x a)xTT(kk)) - pl(1 - -x)x 0k)
(139)
[(x]0k) 0kk) + ky Cp u(x;
cu + kp u(Iz 01,)) - cu + kn
CH plxz 02.x)
ulxx 0r,
Cu + kip
Cu + kip
+ 1((1 -a)x 09,k) 1l(1 -a)xz 0x)
2- (1 a +
Cp + kig
Cu MinBhkkll M
Cp Rip
kn
||stell
Vo -t,
1,1t
where the first inequality is obtained by the condition of case
Mxx To (1 kp
> (1+ Cr
) ax)2,, 0g,k)
Cp
11xx 0g.k)
hip
which is equivalent to
cuplxr 02.x) Cu + kp
kuptla 80 (e.1))
> u((1 (a(1-a)z)) a)xT
Cp + kp
Case 3: when the attacker's estimates satisfy
ky 11(1 - -0)xx -0)x)00xx) - 1 - 1)u(xz 02.k) ace
kp are
Su(i, 80 8P.17)
(140)
<(1 + Cp ) a1)/ 00, 00,x) ky
Cμ p1 00,x)
and hence cu S 5 - a Ce have outh
Blra.rp P7-1, [2] enp(11 0k) + +1 =x)u(xT 01))
(141)
42

---

Published in Transactions on Machine Learning Research (02/2023)
We can find that
epp22 0k) + (1 et)((x) 01,) - p((1-a)zz
(a(xx (0((=]]0))))))))){{)))))))) 0k) - p(x] + +plz] (1)) - (((1 a)z]0x) 0x)
(u(xx 0k,k)= - -u(xi 0r,/ + cl(((x 0,,1)) pla) 011)) - =c(u(x] - ulx7 x(x]0(.x))
+ +mz=] 01)) u((1 _a)x 0k)
=n((1 - a) 02, mlx1 02, (r.1)) ) ex(u(xz 02,))) ulxt 11))) + ex(u(x,
u 09,k))
+ plxz 012) u((1 - aa)x 0x)
=u a)), 00, n((1 -a)x, 0x) + ce(u(x, 0x) 1l k) + (1 -ca) (u(x) 112z, 11.1))
(142)
From Lemma
Elre, Fe-1, 11] (M((1 - a)x 0x
5(1 - a + e, ) 0l. | (P(x))
(143)
+ (1 - f K 30 1.11
||=2|||
-1.
Case 4: when ulx, 80 (..)))
<
hn acy
p((1 - ox)x1 T,0 89.k)
(ace - 1)1(2, 0l,k) and c = =1
he
-
Okk,' we have
Bira,1p/ FF-1, =1 (1
Cp yuxx 0x) + a Cv pxx 01z)-
(144)
kip
kip
Then, by Lemma 0
(1 a Go
jusr TouT0xx 0k) + a [xx 01²)) - (p(11 - a)x, 0x)
Cp
kp
kp
<(1
Gy )1(xz [ 0k) :M(11 a)rT 0x) + kip
Cy
p ( 60 00,;) + acc (0. v.,
kp
<(1 Ca ju(I] T 0k) - m((1 - a)xz 0k) + u((1 a)zz 02,x) - (1-
9y )lat 0p,k) + ac, t. | )
kip
S(kp cp) 3, |0 (vox)= + acuit t.1 || |0:11100 ".: --..
(145)
Since x 01 0, ulx? Ox)) - ulx; 11;) S k 0k. Hence, we also have
(1 a a |u T 0k) + k du
Cu
01z) - m((1 - p((1-a)x 0k)
kip
kp
=plxl [xxx 1n(1 -x) 0x)
a Cp
(u(oT(x) u1x,7 0/t))
(146)
kp
Cy kpot 0K O.
0k
a
kiy
Combining these four cases, we have
El Elra.rp Fr Tt] - 11(11 o)oo [x)
<2k Se (12l + 2k. 211 |2x||
(147)
43

---

Published in Transactions on Machine Learning Research (02/2023)
E.6
Proof of Lemma
The agent's s maximmn--lkellhood estimation can be written the solution to the following equation
Σ (rn - --(=- O(t))an =0 (e
(148)
As described in the section E.2 we have gr, - gr. - aa)kk)))))))))))))))))))))) = Z1 + Zz and
x, (0. - ()(x))))))))))))))))) = x, GTJ (2) + Z2).
(149)
We set Zi Et (n(( n((1 0k) ))), 0
and 7/2 EnEr((t-)) 1) In
In the white-box attack case, we have [ 0 Px-1] = (()-0)) 0k) and hence || = 0. Under the proposed black-box attack, F[ + 0 but
Bl 01p Fr Li] - (1 ((1-a)6 (z) 0x)
<2k (())))) + 2kin. 1.1 |2se||
(150)
Do
c.s7
We Z Z5 + Z6, where
Zs =
Σ
(m(x))0r)) - Elu(ad (1))[12111 I,))
(ET:(I-1)
and
Z6
Σ
(Elu(x) [E]u(1T01p)) 0p:) -1(1)-((1111)))(11111111 a)xx, 0xx) 0x)) kx
nEr((t-1)
For any context & E D and i + K, have
1. (0e, (1 - x))x)]
(151)
S|x T G Lzl + [x' G Es! + 1 G.. Zol.
Since we have { [u(=Tppp ( 1ul (Er((--1)
is bounded martingalc difference sequence w.r.t
the filtration {Fss (=) and also ky J...S-sub--Gauusian--u---- Gaassssiin.
From Theorem 1 and Lemma 11 in (Abbasi- Yadkori et al. 2011 we know that for any 8 > 0, with probability
at least 1 K-15
K
K IZolly S 2 log
L2N,(t)
+ dlog
1+
(152)
Aod
for any arm i + and all & > 0.
We have the fact that
|2 112 = xz Vis
Σ
FaSt + AI
Vi
1ET(((-1)
2 x V
Σ
IKTK
Virlor
(153)
KEri(t-1)
Σ
(x] V x22)
(ET:(t-1)
44

---

Published in Transactions on Machine Learning Research (02/2023)
Hence,
o. Gr G.,
2 Cyity
Σ Tkol
Vestoa
(154)
kEn(t-1)
Cp Σ
(x) Gr, xx)))) xx))
kEn(t-1)
and hence Eker((t-) G xx)
2ेf |ل
Then, |x Gr Lol can be upper bounded by
Jx: G Zal
Σ
Blra.plFk-11 1((1 - ax)x(())
Σ
(x. ox)
(CT((C-1)
AET.(C-1)
(155)
Σ
2k || ((ex)((Fe.x)) + 2k
||=x||
|
k.1
(t-1(
po
Cp
k.rl
where the first inequality is obtained from Cauchy-Schware inequality, the second inequality is obtained from Lemma 7 and Equation 153
In addition, by the fact that (a + b)2 < 2a² + 2b for any real number, we have
Σ
2kpPk. (ll,kll111l((000 + 2h k,
(E)((t-1)
(156)
2
Σ kET((t-1)
Σ
2
2k
k
||
-1
(E 1)
pa
k.1l
Here, we use Lemma 11 from (Abbasi- Yadkori et al. 2011 and get, for any arm i,
|x lovelive.) S 2d 1+ No(5)22)
tL?
Σ
S 2d
1+
dd
dx
(157)
(t-1)
Set A do, we have || 6,1
51 2 ||,1|| <211=11/2
By the fact that E,
Ti 1) (t 1), and Σijk Ti(t 1] ΣitK -1,, have, for any arm i,
- - 1) S (t - 1), and 7i(t - 1) S Ejkk 73(1- - 1). Thus,
11
| Evellve (ve.x) -1 s Σ
| [Exl S 4dlog
1+
dhp
(158)
(fT((f-1)
KET (t-1)
and
1 (1+ tIa ++2
Σ
||
5
Σ
|
Seellvv S 4(K 1)dlog
dAo
(159)
(t-1(1-1)
70
iy (t-1)
45

---

Published in Transactions on Machine Learning Research (02/2023)
By combining Equation 156
Equation 158
and Equation 159
and when K 2 3, we have
Σ
2ki || (ve,x)= + 2k |
k.s
I))
vo
k.1k
2
2 2k Bknpkin 11 (ve.))
Σ kET((t-1)
2
+
Σ
2
2k k.ll
||0x|||
-1
(ET,(e-1)
vo
A.1h
k +
2
K
Aod )) x 8k x 16d log
I.2t
1 tL?
$ 20K
log
+ dlog
1+
Cp
8
dAo
Ky L R.
K
T.2t
))
11 tT.
2
log
dlog
1+ Agd
x 8k x 16d2(K
1)g
aua
Cμ
8
ddo
(2,,LS <128h2 de 21
2
K
1+ L2t
1L2)
(K (KK-
k2
ky Keeg
log
dlog
log
1+ dAa
+
(1 +
Cp
Agd
c2 22 2
Cp
[2 + 2R
K
L2t
t 1
k2
<128k d
log
+
dlog
1
log
x 2K
#
C₁
And
dAo
c a²
(160)
In summary, have
| 0.. - 2, a)0xl
2k LS + 22
16k2d
tL? dAo
K log σ
L
(161)
1
K log
1+
dlog
1+
|
|0l
C₁
c
Aad
E.7 Proof of Theorem 4
For round and context Ht, if UCB-GLM pulls arm + K, we have
1 -TO,K k + Br,K / oe Vi S x O.. + Bes V al Ve. xc.
Recall Be, on / log K 8 dlog (1+ (2N.(1) And
4R
Since the attacker does not attack the target arm, the confidence bound arm does not change and TTOx I zτ TT + 8e, / of Vi holds with probability K- Thus, by Lemma Equation
2, 0K Sz. + 3e,
2, Vi, Zt
2k L.S + 2R
16k3d Cya
t1,22
K log
I,21
<a](1- - a00k +
1+
K log
1+
+ dlog
1+
||
Cn
duo
And
(162)
By multiplying both sides [ue= and summing over rounds, have
km/
(163)
T
2k I.S 2R
16k
(1+ IT.2
dio ))
K + d
1,2t
1 (I==))
Cμ
1+
a 1
Klog
1+
log 5
1+
And
|| |
k=1
46

---

Published in Transactions on Machine Learning Research (02/2023)
Here, Lemma 11 from (Abbasi- Yadkori al. 2011 and obtain
Nitt
tL?
(1=i))
1a v
2dlog([
2d 2d
1+
(164)
dA
dd
According E 11m=1)|lalll 2 (i(t) 1 (1,=1)) || | we have
T
( S Ni(1)2dlog (1+
1L?
Σ
(165)
dd
k=1
Set A = do, we have ||
(1 + ب 2 Thus, we have
T
1 1a O
k=1
2k LS + 22
16k dl C
tL? dho
K + dlog
L2t
(1
tL?
1
K log
1+
log
1+ Aod
(N:(()dlog
dho
(166)
and
(t(t) Σ (T==))
4d
LS +2R
2
log
1
(167)
(a>))2
ddo
log
K
+ dlog
[+
I.2t
)
16k2d d
K Klog
1
tI? dbo
And
C
where 7 minser (1c, 0k).
47


Reviews:
[{"review_id": "jIyI1tWRmc", "reviewer": "Reviewer_26LQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n\\- The authors propose an interesting problem -- backbox action-based attacking algorithm, which is more difficult compared to reward poisoning.\n\n\\- This paper is the first one discussing this problem in the contextual linear bandits. The theoretical proofs are correct and the empirical results seem convincing. One nontrivial proof is that, in the black-box attack, the attacker needs to simultaneously estimate the minimum arms in a pessimistic way and employ the attacking strategy based on this estimated arm.\n\nWeakness:\n\n\\-- First of all, I think it is not quite right to state their model as “linear contextual bandits”, because they only tackle the disjoint linear models scenario in Section 3.1 in (Li et al., 2010) where each arm $i$ has a distinct $\\theta_i$. But this setting is not much different from MAB, when people talked about “linear contextual bandits”, they usually referred to a shared $\\theta^\\*$, which is the simplified version of Section 3.2 (Li et al., 2010). So when goes to the latter scenario, I am not sure whether this algorithm still works well or not. My conjecture is that it might work but maybe not very optimal and requires some more complicated analysis.\n\nBesides, from the theoretical perspective, I found that the motivations of some statements are not very clearly motivated (although correct) and results are relatively incremental.\n\n\\-- Eqn. (3) is basically a restatement of Assumption 1. To me, it is unclear what is the intuition behind this $\\alpha$, and therefore the final $\\alpha$-based result, although correct, is hard to interpret. For example, instead of assuming $ \\langle x,\\theta_K \\rangle > \\min_{i \\in [K]} \\langle x,\\theta \\rangle$, I wonder why not define  $\\Delta = \\langle x,\\theta_K \\rangle > \\min_{i \\in [K]} \\langle x,\\theta \\rangle$ and state the result in terms of $\\Delta$ ? The latter one seems more standard in the linUCB scenario.\n\n\\-- Only doing an attack on LinUCB is a little bit weak to me because LinUCB is similar to a hard elimination algorithm -- Once the learner decides some arm is inferior with high probability, it will stop pulling the arm forever.  So the main technique here is just cheating the learner to eliminate all the other arms, which is not very surprising to me.\n\n\\-- It is unclear to me why randomness in Eqn.(5) is necessary. Because the LinUCB is a deterministic algorithm, it seems to me totally possible to design a deterministic attacking algorithm to cheat the learner.\n\nFrom the experiment perspective, first of all, as I stated before, they are not tackling the same setting so I am not sure how they did the experiments.\n\nAlso, I think maybe more content can be added to Section 5.2.\n\n\\-- The author does not choose Bogunovic et al., 2021) because it does not apply to linear contextual bandits setting. But to me, if the attacking algorithm works for general linear contextual bandits, then it must work for linear bandits with fixed candidate arms. Why not give a test?\n\n\\-- The (Ding et al., 2022), like the author stated, has bound $O(C\\sqrt{T})$, which is not that good. Why not test on other robust algorithms even in MAB setting which has better $C$ dependent bounds?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "From the theoretical perspective, this paper proposed a provable action-based attacking algorithm on the linUCB, as well as a generalized linear model. From the empirical perspective, the author shows the effectiveness of their algorithm on multiple datasets. Their experiments not only include the LinUCB but are also compared with other usual algorithms including $\\epsilon$-Greedy, LinTS and a robust linear bandits algorithm.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major concern. The linear contextual bandits settings the author states in their paper are not quite the same as those they compared with. So the author should make it more clear. (This will directly affect my decision. For the current version, I will say reject.)\n\nOther concerns: (These will strengthen the work)\n\n\\--As I stated in the theoretical perspective of weakness, some statements and algorithm designs do not have a clear motivation. The author should make those more clear.\n\n\\-- Add more empirical results.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zffiaYraVp", "reviewer": "Reviewer_Dc1B", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n(1). The paper considered a very novel problem in attacking contextual bandits. Prior works were focused mostly on reward poisoning attacks where the attacker perturbs the reward of the selected arm. However, less attention has been paid to the action poisoning scenario, which is equivalently important from a practical perspective. This paper is the first to design action poisoning attack algorithms on contextual bandits, and revealed the security vulnerability of typical contextual bandit algorithms such as LinUCB. This is very novel and important work along this topic.\n\n(2). The paper is technically solid and strong. In both white-box and black-box attack scenarios, the authors designed attack algorithms that provably achieves T-o(T) target action selections while incurring only o(T) cumulative attack cost. A log of Lemmas are derived to achieve the main theoretical results in this paper. I can see that these Lemma are also technically interesting and hard to prove. Furthermore, the authors provided intuitive explanations and remarks after main theoretical results, which better facilitates readers to understand their results. I like these explanations as they make the paper easier to read.\n\nWeaknesses:\n\n(1). I am very concerned about the assumptions in this paper. There are two major assumptions made in this paper. First, the target action is not the worst action on all possible contexts. Although I feel this might be too restrictive at first glance, I was convinced that this assumption is necessary. However, what really makes me worried is the second major assumption that the expected reward of all arms must be strictly positive. This barely holds especially when the context set D is dense, e.g., in high dimensional space, it's very likely that some action coefficient is orthogonal to some context, and as a result, the expected reward is 0. This assumption is also used in proving the main theoretical results (e.g., Theorem 1) to lower bound the expected reward of the target arm. In practice, this may not hold. \n\n(2). The proof of the necessity for Assumption 1 does not seem very rigorous to me. It argues around two situations that the attacker either attacks or does not attack the target arm. Also in the end of the proof it says that in order to boost the expected reward of the target arm by Delta, the cumulative attack cost is at least linear. However, why the attacker has to boost the expected reward of the target arm? Is it possible that the attacker intermittently increases the reward of the target arm (but does not boost the expected reward) and always reduce rewards of non-target arms so that the attack is still efficient? I just feel like the argument is not rigorous enough because it does not consider all possible attacks.\n\n(3). The authors empirically showed that even when the target arm is the worst arm, the attack algorithm designed in this paper can still be efficient. This is great! However, that makes me wonder if the authors should further theoretically study this phenomenon. For example, if the target arm is the worst arm on epsilon fraction of contexts, how much degradation would happen in terms of the attack performance. This might be an interesting research question to study, although I understand that it can be hard to answer.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studied a new security threat to linear contextual bandits called action poisoning attacks. The attacker in this paper overwrites the arm selected by the bandit agent so that the generated reward alters. The bandit agent then uses the true arm and the reward of the altered arm to update its policy. Under this setup, the paper studied how to manipulate the selected action such that the bandit agent is misled to prefer some target action over the learning process. Two concrete scenarios are considered --- the white-box scenario where the attacker knows the environment, the true arm coefficients and the bandit algorithm, versus the black-box scenario in which the attacker does not know the arm coefficients. The authors provided attack algorithms in both scenarios that provably achieves T-o(T) target arm selections while inducing only o(T) cumulative attack cost. The authors complimented the theoretical results with solid empirical study to demonstrate that the attack algorithms are indeed effective and efficient on synthetic datasets. The paper exposed a severe security caveats in contextual bandits and helps guide the design of more robust algorithms in related applications.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Based on the current draft, I suggest the authors to make the following changes, although I am OK if no changes are made in the final version because those changes can be hard to achieve.\n\n(1). Think about the main assumption 1, and study theoretically (or provide some theoretical insights and arguments) what if the target arm is the worst arm on epsilon fraction of contexts, where epsilon fraction is in terms of the context distribution. How much degradation may happen in terms of attack efficiency?\n\n(2). Think about how to relax the assumption that the expected reward must be positive on all contexts. This is really a strong assumption that barely holds in real-world applications of contextual bandits. I understand that this can be hard to achieve so I am OK if this assumption can not be relaxed, but maybe provide some thoughts on how to address that in follow-up works.", "broader_impact_concerns": "This paper has no negative ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OMDhvN3XZA", "reviewer": "Reviewer_5QpP", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a paper on a relevant topic and seems to have good results. However, I am concerned with the writing. I believe that the technical stuff is sound, but I have some parts that I do not understand because of the writing - I do not want to be second guessing as a reviewer, hence I believe that these things should be fixed. Below, I have the list of major and minor concerns:\n\nMinor:\n1) The sigma algebra is introduced on page 3, but is not used at all in the main paper (only in appendix). \n2) last line of Sec 3.1: there is a forall quantification over t, x_t but these do not appear in the statement within the scope of the quantifier\n3) Above algorithm 2, the step referred to in brakcets (5,7) do not match the description preceding the bracket.\n4) omega(N) is introduced but no reason stated why which is surprising, it is not used immediately but only later on.\n5) Referring to specific equation should start with capital E, e.g., Equation 5 and not equation 5 (many instances throughout the paper).\n6) Sec 4.3 second line: equation written twice.\n\nMajor:\n1) T is used for vector transpose as well at time horizon T - this is very confusing.\n2) It is better to recognize random variables differently. Related to this, I am not sure whether x (context) is a random variable or sometimes a realized value of the random variable. The sigma algebra introduced on page 3 makes x's a random variable. (In some works, x can be fixed or adversarially chosen chosen http://proceedings.mlr.press/v15/chu11a/chu11a.pdf). Continuing along the same lines, in the proof of Lemma 1, I am not sure how the bounded martingale came about, especially if x's are random variables. This part needs more explanation and clarification. Clearly state what are random variables.\n3) The paper is mainly a theory paper, thus it is surprising that all proofs are in appendix and there is not even a proof sketches in the main paper. Please add some proof sketch.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an attack on linear contextual bandit where the actions chosen by the defender ar modified but the defender is unaware of such change. The goal is to make the defender play an arm K as much as possible with least action modifications needed. The authors present a white box and a black box setting that are different based on whether the adversary knows the coefficients of the linear mean of each arm or not. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the list of major and minor concerns in weakness and strength. I want to see those fixed.\nMy changes are more of what is typically a major revision in journals. ", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Based on discussions among the reviewers and the authors, the reviewers think that although the contribution and technical innovation might be moderate, it:
* studies a timely and interesting topic
* contains solid results (some assumptions may be unrealistic but necessary from a technical point of view)
* has novel and interesting methodology in theory and practice

The revised version of the paper addressed the reviewers' concerns about problem setup, necessity of some assumptions, details of simulations, and general presentation. 

Overall it satisfies TMLR's acceptance criteria. 
Decision: Accept (poster)