Linear Contextual Bandits with Adversarial Corruptions
Authors: Heyang Zhao
Dongruo Zhou
Quanquan Gu
Venue: NeurIPS 2021 Submitted (2021)

Abstract: We study the linear contextual bandits problem in the presence of adversarial corruption, where the interaction between the player and a possibly infinite decision set is contaminated by an adversary that can corrupt the reward up to a corruption level $C$ measured by the sum of the largest alteration on rewards in each round. 
We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$. The key algorithmic design includes (1) a multi-level partition scheme of the observed data, (2) a cascade of confidence sets that are adaptive to the level of the corruption, and (3) a variance-aware confidence set construction that can take advantage of low-variance reward. We further prove that the regret of the proposed algorithm is $\tilde{O}(C^2d\sqrt{\sum_{t = 1}^T \sigma_t^2} + C^2 \sqrt{dT} + CR\sqrt{dT})$, where $d$ is the dimension of context vectors, $T$ is the number of rounds, $R$ is the range of noise and $\sigma_t^2,t=1\ldots,T$ are the variances of instantaneous reward. We also prove a gap-dependent regret bound for the proposed algorithm, which is instance-dependent and thus leads to better performance on good practical instances. To the best of our knowledge, this is the first variance-aware corruption robust algorithm for contextual bandits. 

Linear Contextual Bandits with Adversarial Corruptions
Anonymous Author(s)
Affiliation Address email
Abstract
We study the linear contextual bandits problem in the presence of adversarial corruption, where the interaction between the player and a possibly infinite decision set is contaminated by an adversary that can corrupt the reward to a corruption level measured by the sum of the largest alteration on rewards in each round, We present variance-awan algorithm that is adaptive to the level of adversarial contamination C. The key algorithmic design includes (1) a multi-level partition scheme of the observed data, (2) cascade of confidence sets that adaptive the level of the corruption, and (3) a variance-aware confidence set construction that can take advantage of low-variance reward. We further prove that the regret of the proposed algorithm Ö(C²d dy Et_ of + CR + CRVdT), where d is the dimension of context vectors, T the number rounds, R is the range of noise and of 1 ... T are the variances of instantaneous reward. We also prove a gap-dependent regret bound for the proposed algorithm, which is instance- dependent and thus leads to better performance good practical instances. To the best of our knowledge, this is the first variance-aware corruption robust algorithm for contextual bandits.
2
6
10
11
13
15
18
Introduction
18
Multi-armed bandits algorithms are widely applied in online advertising (Li et al., 2010), clinical
19 trials (Villar al., 2015), recommendation system (Deshpande and Montanari, 2012) and many other real-world tasks. In the model of multi-armed bandits, the algorithm needs to decide which action
20
21 (or arm) to take (or pull) at each round and receive reward for the chosen action. In the stochastic
22 setting, the reward is subject to fixed but unknown distribution for each action. In reality, however,
23 these rewards can easily be "corrupted" by some malicious users. A typical example click fraud
24 (Lykouris et al., 2018 8), where botnets simulate the legitimate users clicking an ad to fool the recommendation systems. This motivates the studies of the bandits algorithms that are robust to adversarial corruptions.
25
26
27 For example, Lykouris al. (2018) introduced bandit model in which an adversary could corrupt
28 the stochastic reward generated by an arm pull. They proposed an algorithm and show that the
29 regret of this "middle ground" scenario degrades smoothly with the amount corruption injected
30 by the adversary. Gupta et al. (2019) proposed an alternative algorithm which gives a significant improvement regret.
31
32 While the algorithms that are robust to the corruptions have been studied in the setting of multi-armed bandits in number of prior works, they still understudied in the setting of linear contextual 34 bandits. The linear contextual bandits problem can be regarded as an extension of the multi-armed
35 bandit problem linear optimization, in order tackle unfixed and possibly infinite set of feasible
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

36 actions. There is large body of literature on efficient algorithms for linear contextual bandits with no corruptions (Abe al., 2003; Auer, 2002; Chu al., 2011; Dani al., 2008; Rusmevichientong and Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011; Li et al., 2019b), to mention a few. The significance of this setting lies in the fact that linear regression approaches are widely used in recommendation systems and advertising (Li et al., 2010; Jhalani et al., 2016; Deshpande and Montanari, 2012). Linear contextual bandits with adversarial corruptions is an arguably more challenging setting since most of the previous corruption-robust algorithms are based on the idea of action elimination (Lykouris et al., 2018; Gupta et al., 2019; Bogunovic et al., 2021), I, which is not applicable to the contextual bandits settings where the decision set is time varying and possibly infinite at each round. In Garcelon et al. (2020), is shown that a malicious agent can force a linear contextual bandit algorithm to take any desired action T - o(T)) times over T rounds, while applying adversarial corruptions to rewards with a cumulative cost that only grow logarithmically. This poses a big challenge for designing corruption robust algorithms for linear contextual bandits.
37
38
39
40
41
43
45
46
47
49 In this paper, we make first attempt to study a linear contextual bandit model where an adversary can corrupt the rewards up to corruption level C, which is defined the the sum of biggest alteration the adversary made on rewards in each round. We propose a linear contextual bandits algorithm that is robust to reward corruption, dubbed multi-level weighted learning (Multi-level OFUL). More specifically, our algorithm consists of the following novel techniques: (1) We design multi- level partition scheme and adopt the idea of sub- sampling to 55 do the robust estimation of the model parameters; (2) We maintain a cascade of candidate confidence sets corresponding to different corruption level (which is unknown) and randomly select confidence
51
of
53
57 set at each round to take the action; and (3) We design confidence sets that depend on the variances of rewards, which lead to potentially tighter regret bound.
58
59
Our contributions are summarized as follows:
60
We propose a variance-aware algorithm which is adaptive to the amount of adversarial corruptions C. To the best of our knowledge, it is the first algorithm for the setting of linear contextual bandits with adversarial corruptions which does not rely on the finite number of actions and other additional assumptions.
61
63
64
We prove that the regret of our algorithm in Ō of
+ CRVJT
where
d is the dimension of context vectors, T is the number of rounds, R the range noise and of = 1..., I are the variances of instantaneous reward. Our regret upper bound has multiplicative dependence on C which indicates that our algorithm achieves a sub-linear regret when the coruptiion level satisfies C = /4).
65
66
67
68
We also derive gap-dependent regret bound Ō (1 proposed algorithm, which is instance dependet and thus leads to a better performance on good practical instances.
CdRdd+ dCC max of) for our
69
70
71
72 Notation. We use lower case letters to denote scalars, and use lower and upper case bold face letters
73 to denote vectors and matrices respectively. We denote by [n] the set (1..... n). For a vector x E Rd
74 and matrix Σ E idxd a positive semi-definite matrix, we denote by ||x||2 the vector's Euclidean
75 norm and define ||x||> x Vx Σx. For two positive sequences {u,] and [b.. with n 1,2,
76 we write On (b,,) if there exists an absolute constant C such that a, S Cb2 holds for all
and write an (bb,,) if there exists an absolute constant C' > 0 such that a, Cb, holds 78 for all 1. We use (-) to further hide the polylogarithmic factors. We use 1(-) denote the
79
indicator function.
2 Related Work
81 Bandits with Adversarial Attacks: There is large body of literature on the problems of multi-
82 armed bandits with adversarial corruptions. Most research in this area aims to design algorithms that
83 achieve desirable regret bound in both stochastic multi-armed bandits and adversarial bandits, known
84 as "the best of both worlds" guarantees (Bubeck and Slivkins, 2012; Seldin and Slivkins, 2014; Auer
85 and Chiang, 2016; Seldin and Lugosi, 2017: Zimmert and Seldin, 2019). These works mainly focus on achieving bounds in the worst case and the case where there is no adversary. As result, these

---

87 algorithms are either not robust to instances that moderate amount of cortuptions occur, or suffer from restrictive assumptions on adversarial corruptions. Distinctive from the above line of research. 89 I. yykouri et al. (2018) focus on a variant of classic multi-armed bandit model in which each pull of an
86
90
revealed to the player. In their work, the corruption level C is defined as C = >, max, (a) - (a)( where r's (a) is the stochastic reward of arm a and r' is the corrupted reward of arm a at round t. They develop algorithms adaptive to the unknown corruption level, which achieves an regret bound. Gupta et al. (2019) proposed improved algorithm that can achieve regret bound with only additive dependence on C.
arm generates stochastic reward that may be contaminated by an adversary before
91
92
99
94
95
96
On the other hand, many research efforts have also been devoted into designing adversarial attacks that cause standard algorithms to fail (Jun et al., 2018; Liu and Shroff, 2019; Gupta et al., 2019; Garcelon et al., 2020).
97
99
et al. (2019a) studied stochastic linear bandits with adversarial Linear Bandits with Corruptions: Li
I -d x .29) regret bound where d is the dimension of the context vectors, A is the gap between the rewards of the best and the second best action in the decision set D. The distinction between Li et al. (2019a) and our work is that Li et al. (2019a) considers a fixed decision set D throughout all I rounds, while we consider contextual bandits with changing decision set observed before each round. Bogunovic et al. (2021) also studied linear bandits with adversarial corruptions and considered the setting under the assumption that context vectors undergo small random perturbations, which is previously introduced by Kannan et al. (2018). Aside from the additional assumption, another major distinction in Bogunovic et al. (2021) is that the number of actions & is finite and the regret bound depends on k in the contextual setting with unknown corruption level C. Recently, Lee et al. (2021) considered corrupted linear bandits with finite and regret of O(d'T + C). Though both their work and the work by Li et al. (2019a) focus on corrupted linear stochastic bandits, Lee et al. (2021) have a slightly different definition of regret and adopt a strong assumption on corrpttion that in each round I, the corruptions on rewards are linear in the actions. Neu and Olkhovskaya (2020) studied linear contextual bandits with a finite decision set (i.e., K actions) and an adversary. Unlike our model, they assume that the adversary can add an arbitrary noise to the loss under limited amount and prove an (((K)) à 'T ) + e. vdT regret bound for their proposed algorithm. Kapoor et al. (2019) considered the corrupted linear contextual bandits setting under a strong assumption on
conruptions and achieved O ]
100
102
104
106
108
109
110
fixed decision set and achieve an mostance-indepenee
111
112
115
114
115
116
117
118
corruptions that for any prefix, at most an 17 fraction of the rounds are corrupted.
3 Preliminaries
119
120
In this paper, we study linear contextual bandits with adversarial corruptions. We will introduce our model and some basic concepts in this section.
122
Corrupted linear contextual bandits. We consider the the linear contextual bandits model studied in Abbasi-Yadkori Yadkori et al. (2011) 1) under the same corruption studied by Lykouris et al. (2018). In detail, distinctive from the linear contextual bandits Abbasi- Yadkori et al. (2011), the interaction between the agent and the environment is now contaminated by an adversary. The protocol between the agent and the adversary at each round / E [T] can be described as follows:
123
124
125
126
127
1.
At the beginning of round t, the environment generates an arbitrary decision set D, S Rd where each element represents feasible action that can be selected by the agent.
129
The environment generates stochastic reward function (a) (a, μ²) + (a together with an upper bound on the standard variance of ca (a),, i.e., 0y(a) for all a E D..
130
3. The adversary observes D,, ra()),, (a) for all a E D, and decides a corrupted reward function rt defined over D,,
132
133
4. The agent observes D, and selects a E D,
134
5. The adversary observes a, and then returns ra())) and (a,).
135
6. The agent observes ri ((
136 Let F, be the alalgebra generated by Dist. a1 EL.c-1, F1a-1 and 013-1-
3

---

137
At step 2, μ² is a hidden vector unknown to the agent which can be observed by the adversary at the beginning. We assume that for all 2 1 and all a E D,, ||a|| S A, (a, 1² 1 and almost surely. (a(a) can be any form of random noise as long as it satisfies
138
|| 122 12 S B
139
Vt 2 1, Va E De, [e)( S R, (a) = O, (a)(F) & (a)..
(3.1)
140
This assumption on Er is a variant of that in Zhou et al. (2020): We now require the noise to be generated for all a E D; in advance before the adversary decides the corrupted reward function. Our assumption on noises is more general than those in (Li et al., 2019a; Bogunovic et al., 2021; Kapoor et al., 2019) where they are assumed be BauuSaassiinn or Gaussian.
141
142
143
144
At step 3, we assume that the adversary has observed all the previous information and thus may predict which policy the agent will take at the current round. However, since the agent can take randomized policy, the adversary may not know exactly which action the agent will take.
146
147
Corruption level. We define corruption level
Σ
C
sup [r/(a) - (a)). DED;
(3.2)
R
148
to indicate the level of adversarial contamination. We say a model is C-corrupted if the corruption level no larger than C.
149
150
Our definition of corruption level is equivalent to the counterpart in Lykouris et al. (2018) and Gupta et al. (2019) where they define C = Σt= | maxa (a) - Ti (a)l in our notation of rewards. We
151
introduce a factor of 1 since the noise is of range It in our model, while they assume all the π++1 rewards are in range [0, 1].
152
153
154
Regret. Since the actions selected by the agent may not be deterministic, define the regret for this
155
model as follows:
T Regret (T)ret(T)== = Σ (a 11)) - E
T a }
(3.3)
156
Our definition follows from the definition in Gupta et al. (2019) where the standard metric in stochastic multi-armed bandit models of pseudo-regret is adopted. But note that need to take the expectation
157
on Σi= (a.) (the second term in (3.3)). since a randomized policy applied in each round.
158
159
Gap. Let A, be the gap between the rewards of the best and the second best action in the decision set Dr as defined in Dani et al. (2008) which can be formally written
160
A min agA;
((a) :²) - (a, 11 fz"))
(3.4)
161
where A; = argmaxnep, (a, n²) and at is an arbitrary element in AÇ. Let A denotes the smallest gap min A..
162
The Proposed Algorithm
163
164
In this section, we propose a variance- aware algorithm, Multi-level OFUL, in Algorithm 1, to tackle the corrupted linear contextual bandits problem. At the core of our algorithm is an action partition scheme to group historical selected actions and use them to select the future actions in different groups with different probabilities. Such a scheme is introduced to deal with the unknown corruption level. For simplicity, we denote ri (a.),, (a.)) in Section 3 by Tt, or in our algorithm.
185
166
167
189
Main difficulty in our setting. We begin with the main difficulty that prevents us from applying existing algorithms to our setting. Consider a simpler setting where the agent knows the corruption
170
171
level C in prior, and we have o; = R for all t. Then we can apply OFUL (Abbasi-Yadda) et al.,
172
2011) to solve our problem. In detail, in each round we estimate μ by μt, which is the minimizer of the following ridge regression problem:
173
t-1 KH, a.) - r.]2.
f: argmin X uERd
A|I + Σ
(4.1)

---

By slightly modifying the self-normalized martingale concentration inequality proposed in Abbasi- Yadkori et al. (2011), we can conclude that μ belongs to the ellipsoid || - Mel|, S B, with high probability, where 3, = Ō(Rvd + Cvd).. Such a confidence bound leads to a final regret which has polynomial dependence on C. However, such simple approach have two limitations. First, the agent does not know C' apriori in our setting, thus it is impossible to set Br to be dependent on C. Second, vanilla ridge regression estimator does not consider different variances og in each round, Algorithm 1 Multi-level OFUL
1: Set the largest level of confidence sets: Emax [log, 27'
2: For & E [max] set D1, + MI, t 0, C1, + 0.
3: Set Σ1 AI, 14 f 01 0.
4: fort= 1,... - do
5: Observe Dr.
6: f= 1, mmax do
7: Set Be, and Y as defined in (4.5) and (4.6).
8:
C/e - {ulll -illz, S 3e,) {ullla H.ll. S mme)
C Ch..r c
9:
Cc,e41
otherwise
10:
end for
Set f(t) = fe
with probability 2-
IEES fmax otherwise
(1
11:
12:
Select a, - argmax aED, maxpec., (1,,) a) and observe rt, ot- 1)/vd,or).
Set
Ee+1 E. + a,a, 1o, C411 t Ci - trata Me-1 E141 C++1.
15:
for f(t) do
16:
E1+1,E t Ee,, t C1..: He+1l + PL,-
end for
18:
Ex+15(1) t E1,1(0 + ata / / + C,S(0) + mar/o.i
19:
M2+1,((1) + E-1 2111,110 c(t,)(())
20:
end for
175
176
177
178
179
180
thus it only gives a very conservative estimation.
Action partition scheme. To address the unknown C' issue. besides the original estimator μe, which uses all previous data, Algorithm maintains several additional learners to learn μO' at different accuracy level simultaneously, and it randomly selects one of the learners with different probabilities at each round. Such a "parallel learning" idea is inspired by Lykouris et al. (2018). In detail, partition the observed data into fmax levels indexed by [fmax] and maintain max sub-sampled estimators ,,,,,,""" mmx. According to line 11, the observed data in round goes into level with probability 2- if < Emax and it goes to level with probability 1 1- -E 2 = 1/2+2-fmm The intuition is that if 2 2 C, then the corruption level experienced by level E
182
183
184
186
Corruption, e = (f()) =)
sup (r:(a) - ra)) aED
(4.2)
1=1 R+1
189
can be bounded by some quantity that is independent of C. That says, the individual learners whose level is greater than log C' can learn fz" successfully, even with the corruption. For the learners whose level less than log C, we can also control the error by controlling the probability for the agent to select them.
190
191
192
193
Weighted regression estimator. After introducing the partition scheme, we still need deal
184
with the varying variance (heteroscedastic) case. Similar to (Kirschner and Krause, 2018; Zhou al., 2020), we proposed the following weighted ridge regression estimator, which incorporates the variance information of the rewards into estimation:
195
196
μ: = argmin Al|k|/ +
ai) - rr../0%
(4.3)
#ERd
5

---

197
Here 5t is defined as the upper bound of the true variance in line 13. The closed-form solution to (4.3) is calculated at each round in line 14. The use of o, as we will show later, makes our estimator more efficient in the heteroscedastic case. Meanwhile, we also apply our weighted regression estimator each individual learner, and their estimator pe,e can be written as follows:
198
199
200
1-1
+ L argmin > Allaa1
Σ 1(((0) = 1V, a.) - r..
(4.4)
MEB
:=1
The closed-fone solution to (4.4) is calculated at each round in lines 15-20.
202
Final Multi-Level confidence sets. With the estimators pt, Pr. ... Mrt at the beginning of round 1, we define cascade of candidate confidence sets as in lines 6-10, where
(R + 1)3} t.2
Be, 8V
dloog
log(4t2/8) 4
VAB, (4.5)
(R + 1)2A
(R + 1)2X + 1
n // dog
(R+1)>> 1og(812T/8) + (
vAB,
(4.6)
with C2 = log(222 (2)2/6) + 3. For simplicity, we define
204
8" 8"= max [lgg C7}
(4.7)
205
as an important threshold in our later proof for regret bound analysis. Later we will prove that Cz contains μr" for all l 2 f t Z with high probability.
206
207
Note that each candidate confidence set can be written as the intersection of two ellipsoids. The intuition behind our construction of candidate confidence sets is that we hope that C.. is robust
208
209
enough to handle the c'rcrrupte case, i.c., μ é Ci.e with high probability. To achieve this, the first ellipsoid makes use of the global information and the "radius" 3e, need contain factor of 2 to tolerate a corruption level of 2 and the second ellipsoid makes of the observed data in level é since this level only contain a few times of corruptions in 2 c'-corrupeed case.
210
212
Action selection. With the candidate confidence sets, we use line 11 randomly decide one confidence set and select an action based on the optimism-in sietnism-ii-tte-faaeeee wn-the-facc-of-----------------e face--f-uncertainty (OFU) principle in line 12. Then we update the estimators for the next round +
214
216
Remark 4.1. Our algorithm shares a similar strategy for partitioning the observed data with the algorithm in I Lykouris et al. (2018) but note that there is major difference in that: Lykouris et al. (2018) regard the partition scheme as "layer structure", i.e., their algorithm further uses different estimators in layers of parallel learners and do action elimination layer by layer in each round. In
218
220
contrast, the sub-sampled estimators in our algorithm are used independently, i.c. the selected action
only relies one of the partitions. As result, Algorithm I does not need to do action elimination, thus is capable of handling the cases where the number of actions is huge or even infinite.
222
Main Results
223
224
In this section we present our main theorem, which establishes the regret bound for Multi-level OFUL.
225
Theorem 5.1. Set A = 1/B². Suppose that C' = 2(1), = 2(1), for all f 2 and all a E De (a, n²) E [-,, Then with probability least 1 - 35, the regret of Algorithm is bounded as
follows:
Regret(T) = C²d
('d
Σ o V
226
Remark 5.2. When o,, = 11)), the regret bound Theorem 5.1 matches the regret bound of OFUL proposed in Zhou et al. (2020) when the corruption level C' is constant.
Remark 5.3. Compared with the Ö(d'T + C') result in Lee et al. (2021), our result has multi- plicative quadratic dependence on C, which seems to be worse. However, we want to emphasize that
228
229
we focus on more challenging contextual bandits setting where the decision sets D, at each round are not identical, which is different from that in Lee et al. (2021). Therefore, our result and that in
231
Lee et al. 12021) not directly comparable.

---

233
Remark 5.4. Note that this Dnstance-independed regret upper bound also holds in stronger model than the one described in Section 3. where the adversary can even decide the decision D, each round since our regret bound can hold without any assumption on the decision sets.
234
Corollary 5.5. Under the same conditions as in Theorem 5.1, if of given by the environment are all R. the regret of Algorithm 1 is bounded by:
Regret (7) = O
236 We also provide gap-dependent regret bound.
Theorem 5.6. Suppose that C' ((1), R 2(1), for all / 1 and all E Dr, (a, 1²) E [-1,1]. Then with probability at least 33, the regret of Algorithm bounded as follows:
(Tg ( caRd . 1 d² max oi A
(E(T)
Remark 5.7. Theorem 5.6 automatically suggests an (2 regret bound, by the fact
237
ot ( Compared with previous result O(d + d, /2) (Lee et al., 2021), our result has a better dependence on the dimension but a worse dependence on the corruption level C. As
239
Remark 5.3 suggests, we focus more challenging contextual bandits setting, and the worse dependence on C' might be due to this.
241
Proof Outline
242
First we have the following lemma which is corruption-tolerant variant of Bernstein inequality for self-normalized vector-valued martingales introduced in Zhou et al. (2020).
244
Lemma 6.1 (Bernstein inequality for vector-valued martingales with corruptions). Let { be filtration, {x,; Me1 a stochastic process so that x, E Rdd is G--masuuable and 7 IR is measurable. Fix R, L, À > O, μa E IRd. For & 2 let y soch {n", xx) 1/t and suppose that Th, X2 also satisfy
Ind S R. Elm G.] 0, EEn 9il 0 |xell S L.
Suppose {yr) } is sequence such that Σ 1y gocb| C(t) for all & 1. Then, for any 246 0 < 6 < 1, with probability at least - ô we have Vt > O,
|| 1ll1,, S Br C(I) + V1ll21112
where fort 2 1, ue Z, b,, Z. = XI 1 T, b, Ei=1 B/X,, and
dA + 112
8, 80 dog
log (12 + 4R 4R (4t)(44)//))
247 Next, we have that with high probability, all the level / 2 le only influenced by limited amount of 248 corruptions as mentioned in Section 4.
Lemma 6.2. Let Corruption, be defined in (4.2). Then we have with probability least 1 6, for all l 2 2,, f2 1:
Corruption, S C, = log(26 /5) 3.
249 We denote by Exub the event that the above inequality holds.
250 We define the following event to further show that our candidate confidence sets with é 2 E* are
251 "robust" enough, i.e. Ca,e contains 4x' with high probability.
252
Definition 6.3. Let l" be defined in (4.7). We introduce the event E as follows.
ε, = (VL and /. 2 1, -| - -1:l S Se, and | mrlll S m.,.. where B Te.t are defined in (4.5) and (4.6).
(6.1)
7

---

254
Next lemma suggests that the event E happens with high probability.
255
Lemma 6.4. Let & be defined in (6.1). For any 0 < 5 < 1/3, we have P(E1) 2 1 36.
For simplicity, define a,, argmax maxpecC. (M,, a) for each level l. a, be seen action vector randomly chosen from at,, & [fmax] Next two lemmas suggest that under event &1. at each round, the gap between the optimal reward and the selected reward can be upper bounded by some bonus terms related to a,,e-
258
Lemma 6.5. Suppose E occurs. If f(t) & f" we have (a? - ac. (e) S e. ||a,lxx + 280
2. + ar,e- "|
Lemma 6.6. On event & if [(1) = =>> 8 we have (a - a. 1²) S 27e 27eellaull2x
263
Now we provide the proof sketch Theorem 5.1.
Proof sketch of Theorem 5.1. Suppose ε occurs. The main idea to bound the regret is to decompose 285 the total rounds [T] into two non-overlapping parts, based on which individual learner is selected at that round. In detail, have
(aai, (ac, (r"h)
Regret (T) E
E
(f(() S (') (a,, 11))
aaax
T
E
((f(t) = ()) ( (²)) (aa, 21*))
(6.2)
(a(
257
Here 1 represents the regret where the the "low-level" learner is selected, where the corruption level beyond the learner level.For this case, by Lemma 6.5, we can directly show that
288
T
1
ISE
E
Σ (((()) min 2, ||are 1xx + +2 Iladll
(6.3)
269
We further bound (6.3). Let F. be the o-algebra generated by a, Ts, Ts sx f() for s < 1. Then by the property of our partition scheme (note that ((f(t) (*) =- we can show that
270
E
[(f(t) ||a,, ||x F
2"
||a.
[F Therefore, can further bound I, by
T
1 < 4. 2
min Br. Σ
Sr.e. ||ay ||a)| 12,
(6.4)
272 To further bound 13, we split [T] into 2 parts, I (t E [T]lla// > 1},I2 = {t E [Ta|laa// < 1} to bound Iz. The intuition here is that the cardinality of Iı is bounded, and the sum of terms with é Ia can be bounded using Mauchy-Schwarc inequality.
Σ min (1. |aa// Aar/oell 1 } 4d (R + 1)2x+ T
Σ min {2, Br.er ||atll, Bree- TET1
2/ < 2
Tell
(R + 1)22
t=1
(6.5)
275 where the first inequality holds since min {2, Br ||a (
$ 2, the second inequality follows
from the definition of Iı, the third inequality holds by Lemma C.2.
8

---

E TEZ2
min {2, 1r.3111111ll2
S Sr
Σ oz
Σ AEIz
min 11,1la//0113 1s
IEI2
(R + +
S BT
(R+1)
o
2d
(R+ 1)²A
(6.6)
277
where the first inequality follows from Cauchy-Schwarz inequality, the second inequality follows from the definition of o and Lemma C.2.
279 Substituting (6.5) and (6.6) into (6.3), we have
I Ō c²d of + C- + +
(6.7)
Now it remains to bound T2()). By Lemma 6.6, have
T = RRTTd+d
T2(() S 2
min {1 [1, n.. m.elaa (f(1) min
Σ o3
(6.8)
where the second equality can be proved by analysis similar to that of (6.5) and (6.6). Finally, substituting (6.7) and (6.8) into (6.2) ends our proof.
282
7
Conclusion and Future Work
285
In this paper, we have considered the linear contextual bandits problem the presence of adversarial corruptions. We propose Multi-level OFUL algorithm, which is provably robust the adversarial
attacks. We prove a gap-independent regret bound of Ō (CaN
V + CRV
287
together with a gap-dependent bound of Ō ( C² C2RRd+ CC maximm ot)
We leave it open question that whether the multiplicative dependence on C22 in the regret upper bounds can be removed without making additional assumptions in our setting.
290
281
References
292
ABBASI-YADKORK Y., PÁL, D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. In NIPS, vol. 11.
ABE. N., BIERMANN, A. W. and LONG, P. M. (2003). Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica 37 263-293.
295
296
AUER, P. (2002). Using confidence bounds for applotatioo-eexploattiin trade-offs. Journal of Machine Learning Research 3 397-422.
298
AUER, P. and CHIANG, C.-K. (2016). An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Conference on Learning Theory. PMLR.
289
300
BOGUNOVIC, I., LOSALKA, A., KRAUSE, A. and SCARLETT, J. (2021). Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics.
302
PMLR.
303
BUBECK, S. and SLIVKINS, (2012). The best of both worlds: Stochastic and adversarial bandits. In Conference Learning Theory. JMLR Workshop and Conference Proceedings.

---

305
CHU, W., LI, L., REYZIN, L. and SCHAPIRE, R. (2011), Contextual bandits with linear payoff functions. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings.
306
DANI, V., HAYES, T. P. and KAKADE, S. (2008). Stochastic linear optimization under bandit feedback. In COLT.
309
310
DESHPANDE, Y. and MONTANARI, A. (2012). Linear bandits in high dimension and recommendation
311
systems. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE.
GARCELON, E., ROZIERE, B., MEUNIER, L., TARBOURIECH, J., TEYTAUD, O., LAZARIC, A. and PIROTTA, M. (2020). Adversarial attacks on linear contextual bandits. arXiv preprins 0oXi::2002.03839..
314
315
316
GUPTA, A., KOREN, T. and TALWAR, K. (2019). Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory. PMLR.
317
JHALANI, T., KANT, V. and DWIVEDI, P. (2016). A linear regression approach to multi-criteria
319
recommender system. In International Conference on Data Mining and Big Data. Springer.
320
JUN, K.-S., LI, L.. MA, Y. and ZHU, X. J. (2018). Adversarial attacks on stochastic bandits. In NeurlPS.
321
322
KANNAN, S., MORGENSTERN, J. H., ROTH, A., WAGGONER, B. and Wu, Z. (2018). A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. In Neur/PS.
324
KAPOOR, S., PATEL, K. and KAR, (2019). Coruption-tolerant bandit learning. Machine
325
Learning 108 687-715.
KIRSCINNE, J. and KRAUSE, A. (2018). Information directed sampling and bandits with het- eroscedastic noise. In Conference On Learning Theory. PMLR.
327
328
LEE, C.-W., LUO, H., WEL, C.-Y., ZIANGG, M. and ZHANG, X. (2021). Achieving near instance- optimality and minimax-optimality in stochastic and adversarial linear bandits simultaneously. arXiv preprint arXiv:2102.05858
329
330
LI, L., CHU, W., LANGFORD, J. and SCHAPIRE, R. E. (2010). A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web.
332
334 LI, Y., Lou, E. Y. and SHAN, (2019a). Stochastic linear optimization with adversarial corruption. arXiv preprint
335
LI, Y.. WANG. Y. and ZHOU, Y. (2019b). Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory. PMLR.
337
338
LIU, F. and SHROFF, N. (2019). Data poisoning attacks on stochastic bandits. In International Conference on Machine Learning. PMLR.
339
340
LYKOURIS, T., MIRROKNI, V. and PAES LEME, R. (2018). Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing.
342
NEU, G. and OLKИOVSKAYA, J. (2020). Efficient and robust algorithms for adversarial linear contextual bandits. In Conference on Learning Theory. PMLR.
343
RUSMEVICHIENTONG, P. and TSITSIKLIS, J. N. (2010). Linearly parameterized bandits. Mathemat- ics of Operations Research 35 395-431111
345
346
SELDIN, Y. and LUGOSI, G. (2017). An improved parametrization and analysis of the exp3++ algorithm for stochastic and adversarial bandits. In Conference on Learning Theory. PMLR.
347
348
SELDIN, Y. and SLIVKINS, A. (2014). One practical algorithm for both stochastic and adversarial bandits. In International Conference Machine Learning. PMLR
10

---

350
VILLAR, S. S., BOWDEN, J. and WASON, J. (2015). Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: review journal of the Institute of Mathematical Statistics 30 199.
351
ZIOO, D., GU, Q and SZEPESVARI, C. (2020), Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. arXiv preprint arXiv:2012.08507.
354
355
ZIMMERT, J. and SELDIN, Y. (2019). An optimal algorithm for stochastic and adversarial bandits. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR.
Checklist
358
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
360
381
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work studies the regret bounds for contextual linear bandits with corruption. That a pure theoretical problem, thus it does not have any negative social impact.
363
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
386
367
2. If you are including theoretical results...
388
(a) Did you state the full of assumptions of all theoretical results? [Yes]
369
(b) Did you include complete proofs of all theoretical results? [Yes]
370
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [N/A]
372
373
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
374
375
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
378
379
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
380
(a) If your work uses existing assets, did you cite the creators? [N/A]
381
(b) Did you mention the license of the assets? [N/A]
382
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
304
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
387
388
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
380
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
382
393
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
11


Reviews:
[{"review_id": "umvcsuxZTKb", "reviewer": "Reviewer_N6Ux", "summary": "This paper proposes an algorithm that achieves the first corruption-robust result for contextual linear stochastic bandits with infinite arms using the idea of multi-level sampling rates. The regret bound has multiplicative dependence on C^2 and is variance-aware. The algorithm recovers the optimal regret in terms of T and gap when no corruptions are presented.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "--Originality:\nThe main idea to achieve robustness, as the authors stated, is from Lykouris et al. (2018), where the algorithm assigns multi-level sampling rates and therefore remains multi-level confidence sets. One major concern to me is that, although the authors claim in Remark 4.1 that, instead of doing arm elimination as in Lykouris et al. (2018), they are using UCB-type (OFUL) algorithm and maintain multi-level estimators, I find such idea is similar to Lykouris et al. (2020).  Lykouris et al. (2020) also combine UCB-type methods with the multi-layer sampling scheme and maintain different base learners for each layer. Because Lykouris et al. (2020) are considering linear MDP and here the authors are considering contextual linear bandits with changing decision set, so these two results are not directly comparable. But due to these previous works, I think the technical novelty of this paper is relatively limited. \nLykouris et al. (2018): Stochastic bandits robust to adversarial corruption\nLykouris et al. (2020): Corruption robust exploration in episodic reinforcement learning.\n\n--Quality:\nI think all the claims are well supported but this C^2 multiplicative dependence seems not good enough. It would be better if authors can provide some lower bound or at least some intuition on this C^2 multiplicative term.\n\nI also have some suggestions on the experiment although this is not the main part of this paper: Both OFUL and weighted OFUL are deterministic algorithms, and the Greedy are designed for a stronger adversary where it can decide corruption after observing the learner’s action. So I am not surprised that Multi-level OFUL can outperform these three. Could you compare Multi-level OFUL with some randomized algorithms, for example, exp3?\n\n--Clarity:\nThis paper is clearly written overall but the proof sketch is a little confusing: At the first glance I am not sure where the C^2 comes from, then I realize it comes from $C\\beta_{t,l}$ where $\\beta_{t,l}$ contains another C. But at the first glance I saw another $\\beta_t$ in line 246, which makes me a little confused. I would like to suggest the author give some intuitive explanation on why getting this extra C dependence compared to Lykouris et al. (2018). Is there any specialty in contextual linear bandits analysis that results in this extra C?\n\n--Significance\nThis is the first corruption-robust result in contextual linear bandits with infinite arms, so the result is non-trivial. Nevertheless, I think it is not good enough and the technical novelty is limited.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have clearly stated the theoretical limitation of their works.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "l7Xs5z7mZb5", "reviewer": "Reviewer_9fU4", "summary": "The authors study  a linear contextual bandit problem in the presence of adversarial corruptions that are bounded by an unknown C.  Specifically, they propose an algorithm that uses a parallel-learning idea from Lykouris et. al, 2019 using multi-level partition of the observed data.  To deal with varying variance in the observations, they use a ridge regression estimator similar to the earlier work of Kirschner and Krause, 2018; and Zhou et al., 2020.   Finally, they show their algorithm produces a regret that is quadratic in C and the dimensionality of the context vectors. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The algorithm proposed in this paper borrow heavily from earlier works - Lykouris et. al, 2019 for the parallel-learning idea using partitioning of the observed data; Kirschner and Krause, 2018; and Zhou et al., 2020 for dealing with variance in the observed data; and almost mirrors the results of Lee et. al., 2021.  In fact, when C is large, their result can be seen to be underperforming compared to the result in Lee et. al, 2021. \n\nHow does this model compare to others when the corruption is unbounded but only corrupts \\eps fraction of the observations and stochastic in the remaining observations?  The assumption of a bounded C seems a bit strong.  Further, does one need all the parallel-learning machinery to estimate C?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Modeling the corruptions realistically is an important aspect of such studies.  I am not completely bought into the proposed model of corruptions in this paper.  An adversary in general does not have the power to corrupt all observations.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "HJTostSloea", "reviewer": "Reviewer_3jZ9", "summary": "This paper studies the linear contextual bandit problem with adversarial noises in the reward function. The authors assume that the decision set can change over time; that reward can be corrupted up to a corruption level (similar to previous work); and that an upper-bound on the true variance of the reward is revealed after each instance. An algorithm, which is based on the linear bandit algorithm OFUL with two notable modifications, is proposed for the problem. First, it considers multiple levels of possible corruption noise to deal with unknown value of C and second it considers a weighted version of the ridge regression estimator to deal with varying variances (this modification was already present in previous work). The authors prove a regret upper-bound for their algorithm and compare it to the literature. They also provide some experiments in the supplementary material.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers an existing problem: linear contextual bandit problem with adversarial noises (li et al, 2019; Bogunovic et al. 2021; Lee et al. 2021). The main contribution is to incorporate the possibility to deal with varying decision sets, together with varying variances and an unknown corruption level. The upper-bounds have no dependence on the number of actions but are linear in the dimension d which is also common for linear contextual bandits.\n\n\nOn the other hand, the paper suffers in my opinion the following weaknesses:\n\t1. The paper appears to be limited to a combination of existing techniques: adaptation to an unknown level of corruption (Lykouris et al., 2018); varying variances treated with a weighted version of OFUL (Zhou et al., 2021); variable decision sets (standard in contextual linear bandits). The fact that these results can be combined together is not surprising, and thus the contribution could be considered incremental. \n\t2. The regret bounds seem sub-optimal in the level of corruption (they are of order C^2 when existing bounds seem to be of order C). The authors should discuss more this sub-optimality, is it due to the unknown corruption level? Why should we incur it?\n\nOther comments:\n--------------\n3. The authors state that if C is known and the variances are fixed then one could directly apply OFUL with a modified variance (to add the corruption). This yields several questions:\n\ta. The regret bound would then be of order O((R+C)d\\sqrt{T}), right? It would be informative to write it, so that we can compare it with the bound of Thm. 5.1. \n\tb. It is then claimed that one of the problems is the varying variances. But this problem was already solved by Weighed OFUL (Thm. 4.2 of Zhou et al 2021) for OFUL without corruption. Isn't it possible to apply the same reasoning with this algorithm?\n\tc. For the adaptation to the unknown value of C, I am wondering whether it is not possible to just apply the Corral algorithm (see Cor. 6 of [1]) to (Weighed)-OFUL with an exponential grid of possible values for C (from 1 to T). Wouldn't this imply a bound of order C \\sqrt{T} log T? \n\n4. The assumption that the variance is revealed by the adversary (l. 135) is not clear and should be better motivated. We understand that it was already done by Kirschner and Krause (2018) and Zhou et al (2021) but examples of practical applications would be enjoyable to make the paper more self-contained. Similarly, the assumption of varying decision sets is standard in linear bandits but a few lines to recall why this allows dealing with contexts could be helpful for a reader new to the area.\n\n\n5. About the experiments: \n\ta.The results seem significantly different when C = 0 and 300. What is the intermediate regime? For what level of corruption does Multi-level OFUL outperform algorithms that do not consider corruption? \n\tb. I regret that the algorithm is only compared to baselines that are not designed to deal with corruption and suffer linear regrets. It would be interesting to compare Multi-level OFUL with algorithms for linear bandits with corruptions. This could be done by considering fixed variance and fixed decision sets for instance to apply existing algorithms, so that we can see the actual cost of having a more general algorithm. The algorithm could also be compared with the version of OFUL which knows C and takes into account the corruption.\n\n\nMinor remarks:\n-------------\n- How a \\min in (6.3) is obtained using lemma 6.5 is not clear and should be clarified. Same for the \\min in (6.8) using lemma 6.6?\n- How substituting (6.5) and (6.6) into (6.3) gives (6.7) should also be more detailed.\n\n\n\n[1] Agarwal et al. Corralling a Band of Bandit Algorithms, 2017.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors did not mention the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "FJr6vQeloc", "reviewer": "Reviewer_5Lqk", "summary": "The paper studies the problem of linear contextual bandits where the rewards of the actions are not always stochastic but rather they are corrupted in C of the T rounds. This model of adversarial corruptions is well understood in the multi-armed bandit setting. The paper combines the OFUL algorithm that works for linear contextual bandits without corruptions with a multi-level algorithm that is robust to corruptions for the multi-armed bandit setting. Unlike multi-armed bandits, in linear contextual bandits, the action space is not finite and therefore techniques that are based on eliminating actions after selecting them enough times are not as direct. Moreover, the variance of the estimator can be changing over time which is dealt with via the use of a weighted ridge regression estimator. The resulting guarantee of Theorem 5.1 matches the regret bound of OFUL when C is constant and adapts to the corruption level C.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall I enjoyed reading the paper as it provides a nice extension of the multi-level algorithm to the linear contextual bandit setting and tackles the additional complications. The paper is well written, modularly explained, and, to the best of my understanding, correct. \n\nOn the other hand, there are a few places that would be worth clarifying.\n\n1. My first question is with respect to the comparison to the work of Lee et al. (2021) which has a stronger regret guarantee. The authors distinguish their work via mentioning that the latter paper has a stronger assumption. Is there a reason why the algorithm of Lee et al. (2021) would not extend to the setting studied in this paper? \n\n2. My second question is with respect to the variance $\\sigma_t$. It seems that  the paper does not allow the variance to also be corrupted and it also requires $\\sigma_t$ to be observable. It would be great if these assumptions are necessary or if they are for convenience of exposition. A related question: Do we know anything about the case where $\\sigma_t$ is not observable in the uncorrupted case?\n\n3. The claim that the non-finiteness of the version space means that elimination techniques cannot be applied is not really accurate. There are settings such as dynamic pricing where elimination-based application of a similar multi-level technique provide robustness to adversarial corruptions. For example, here are two references:\n\n-- Robust Dynamic Pricing with Demand Learning in the Presence of Outlier Customers (Chen and Wang, 2020)\n\n-- Contextual Search in the Presence of Irrational Agents (Krishnamurthy, Lykouris, Podimata, Schapire, STOC 2021)\n\nIt would be useful if the paper pinpoints what is the feature that exists in linear contextual bandits that requires to move beyond elimination-based techniques.\n\n4. Extending the above point, I have a concern that, on a technical level, the paper combines three existing techniques (multi-level technique for MAB with corruptions, OFUL for linear contextual bandits, and weighted ridge regression for varying variance). It is not clear to me whether there exists some insight that is really required when these techniques need to coexist. It would be great if the authors could explain whether there is some roadblock that arises in the intersection of these techniques that does not exist in each of them independently.\n\nDespite the above concerns, I am generally positive about the paper and would be happy to see the paper at NeurIPS. I encourage the authors to respond to the above comments and I am looking forward to the author rebuttal.\n\n\nMinor comments and typos:\n-- In line 11, probably you mean \"Lee et al. (2021)\" instead of \"Li et al. (2019)\".\n-- In line 137, I think it would be cleaner to say that $\\mu^*$ is selected arbitarily in the beginning rather than \"observed by the adversary\"; in the protocol, the adversary (or nature) selects $\\mu*$ as well.el ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see a negative societal impact of the work. As explained above, I would like to have more clarity with respect to technical limitations of the work and I am looking forward to their response.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the review team appreciated the model and the new algorithms designed, they also identified a couple of weaknesses which I summarize below:

* While the results are interesting, they follow from a combination of previously known techniques.
* Dependency $C^2$ seems suboptimal and un-natural
* There is no strong evidence of why a simpler algorithm (like Corral or MWU on the corruption level) wouldn't work here.
* The model could be better motivated (e.g. why is the variance revealed by the adversary).

Although the reviewers address some of that in their response, that wasn't enough to substantially change the sentiment towards the paper.
Decision: Reject