Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions
Authors: Jiafan He
Dongruo Zhou
Tong Zhang
Quanquan Gu
Venue: NeurIPS 2022 Accept (2022)
Keywords: linear bandits
adversarial corruption

Abstract: We study the linear contextual bandit problem in the presence of adversarial corruption, where the reward at each round is corrupted by an adversary, and the corruption level (i.e., the sum of corruption magnitudes over the horizon) is $C\geq 0$. The best-known algorithms in this setting are limited in that they either are computationally inefficient or require a strong assumption on the corruption, or their regret is at least $C$ times worse than the regret without corruption. In this paper, to overcome these limitations, we propose a new algorithm based on the principle of optimism in the face of uncertainty. At the core of our algorithm is a weighted ridge regression where the weight of each chosen action depends on its confidence up to some threshold. We show that for both known $C$ and unknown $C$ cases, our algorithm with proper choice of hyperparameter achieves a regret that nearly matches the lower bounds. Thus, our algorithm is nearly optimal up to logarithmic factors for both cases. Notably, our algorithm achieves the near-optimal regret for both corrupted and uncorrupted cases ($C=0$) simultaneously.

Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions
Jiafan He
Dongruo Zhou Department of Computer Science University of California, Los Angeles drzhou@cs ucla.
Department of Computer Science University of California, Los Angeles jiafanhe199uche wwweee9lcclll.... edu
Tong Zhang Google Research & HKUST
Quanquan Gu
Department of Computer Science University of California, Los Angeles qguêcs ucla.
tongzhang@tooggzhang- ml... org
Abstract
We study the linear contextual bandit problem in the presence of adversarial corruption, where the reward at each round is corrupted by an adversary. and the corruption level (i.e., the sum of corruption magnitudes over the horizon) is C 2 0. The best-known algorithms in this setting are limited in that they either are computationally inefficient or require strong assumption on the corruption, their regret is at least C' times worse than the regret without corruption. In this paper, to overcome these limitations, we propose new algorithm based on the principle of optimism in the face of uncertainty. At the core of our algorithm is weighted ridge regression where the weight of each chosen action depends on its confidence up some threshold. We show that for both known C' and unknown cases, our algorithm with proper choice of hyperparameter achieves regret that nearly matches the lower bounds. Thus, algorithm is nearly optimal up logarithmic factors for both cases. Notably, our algorithm achieves the near-optimal regret for both corrupted and uncorrupted cases (C 0) simultaneously.
Introduction
We study linear contextual bandits with adversarial corruptions. At each round, the agent observes a decision set provided by the environment, and selects an action from the decision set. Then an adversary corrupts the reward of the action selected by the agent. The agent then receives the corrupted reward of the selected action and proceeds until K rounds. The agent's goal is to minimize the regret Regret (K), which is the difference between the optimal accumulated reward and the selected accumulated reward. This problem can regarded as a combination the two classical bandit problems, stochastic bandits and adversarial bandits (Lattimore and Szepesvári, 2018). In practice, the contextual bandits with adversarial corruptions can describe many popular decision- making problems such as pay-per-click advertisements with click fraud (Lykouris al., 2018) and recommendation system with malicious users (Deshpande and Montanari, 2012).
Lykouris et al. (2018) first studied the multi-armed bandit with adversarial corruptions. Specifically, let C denote the corruption level which is the sum of the corruption magnitudes at each round. Lykouris al. (2018) proposed an algorithm with regret that C' times worse than the regret without corruption. Later, Gupta et al. (2019a) proposed an improved algorithm whose regret consists of two terms: corruption-indeeeddeer independent term that matches the optimal regret for multi-armed bandit without corruption, and coruptiio-depeeneen term that is linear in C' and independent of K, i.e.,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Regret(K)= = o(K) + OCC). The lower bound proved in Gupta et al. (2019a) suggests that the linear dependence on C' is near-optimal. Such a regret structure reveals an desirable property of corruption-robust bandit algorithms, that is, the algorithm should perform nearly the same as the bandit algorithms without corruption when the corruption level C' is small or diminishes.
Based on the above observation, a natural question arises:
Can we design computationally efficient algorithms for linear contextual bandits with corruption that can attain the best possible regret, similar to those in multi-armed bandits?
Some previous works have attempted to answer this question for the simpler stochastic linear bandit setting, where the decision sets at each round are identical and finite. Li et al. (2019) studied the stochastic linear bandits and proposed an instance-dependent regret bound. Later on, Bogunovic et al. (2021) studied the same problem and proposed an algorithm that achieves a regret with the corruption term depending on C' linearly and on K logarithmically. However, these algorithms are limited to the stochastic linear bandit setting since their algorithm design highly relies on the experiment design and arm- rrm-eliminttion techniques that require a multiple selection of the same action and can only handle fixed decision set. They are not applicable to contextual bandits, where the decision set is changing over time and can even be infinite. For the more general linear contextual bandit setting, Bogunovic et al. (2021) proved that a simple greedy algorithm based on linear regression can attain an ideal corruption term that has linear dependence on C' and logarithmic dependence on K, under a stringent diversity assumption on the contexts. Lee et al. (2021) proposed an algorithm and the K logarithmically, but only holds for the
corruption term in its regret depends on C' linearly and restricted case when the corruption at each round is a linear function of the action. Without special assumptions the contexts corruptions, Zhao et al. (2021); Ding et al. (2021) proposed a variant of the OFUL algorithm (Abbasi- Yadkori et al., 2011 1) and its regret has a corruption term depending on K polynomially. Recently, Wei et al. (2022) proposed Robust VOFUL algorithm that achieves a regret with a corruption term linearly dependent on C"l and only logarithmically dependent on K. However, Robust VOFUL is computationally inefficient since it needs to solve a maximization problem over a nonconvex confidence set that is defined as the intersection of exponential number of sets, and its regret has loose dependence on context dimension d. In addition, Wei et al. (2022) also proposed a Robust OFUL. algorithm and provided a regret guarantee that has a linear dependence on different notion of corruption level C,2, which strictly larger than the corruption level C considered in the previous work and the current paper. Thus, the above question remains open.
In this paper, we give affirmative answer the above question. We summarize contributions as follows.
We propose a computationally efficient algorithm based on the principle of optimism in the face of uncertainty (Abbasi- Yadkori al., 2011) 1), named Confidence- Weighted OFUL (CW-OFUL). At the core of our algorithm is a weighted ridge regression where the weight of each chosen arm is adaptive to its confidence, which is defined as the truncation of the inverse exploration bonus. Intuitively, such weighting strategy prevents the algorithm from exploiting the contexts whose rewards are more likely corrupted by a large amount.
For the case when the corruption level C' is known to the agent, we show that the proposed algorithm enjoys regret Regret( K) k dC), where d is the dimension of the contexts, C is the corruption level and K is the number of total iterations. The first term matches the regret lower bound of linear contextual bandits without corruption (dd K) (Lattimore and Szepesvári, 2018). 8). The second term matches the lower bound on the corruption term in regret M(dC)) (Bogunovic et al., 2021). They together suggest that our algorithm is not only robust but also near-optimal up logarithmic factors.
For the case when the corruption level C' is unknown to the agent, we show that CW-OFUL enjoys O(d K) regret for the case C S VK, with proper choice of the hyperparameter. Surprisingly,
'In Wei al. (2022), the adversary adds corruption to all actions in the decision set before observing the agent's action and they define the corruption level C' as the maximum corruption over the decision set. See Remark 2.2 for the formal definition and a more detailed discussion.
'hhe corruption level C, is defined as C, V kk cg where Ca 2 is the corruption magnitude round k. As a comparison, C' = >> |cu|. J. In the worst case, C, = O(VKC) and therefore the corruption term in the regret of Robust OFUL will depend on K polynomially.

---

by proving lower bound on the regret, we show that our regret upper bound is already optimal for all algorithms that achieve near-optimal regret bound for uncorrupted bandits.
We compare our regret bounds with previous ones in Table 1. We can see that our algorithm matches the lower bound up logarithmic factors in both known C' and unknown C cases, and therefore is nearly optimal.
Table Comparisons of regrets for corrupted linear contextual bandits.
Algorithm
Regret
C
Efficiency
Adversary" 4
Robust weighted OFUL
MOWK+dC'V
Кnown
Yes
Weak
(Zhao et al., 2021)
Robust OFUL.
+
Known
Yes
Weak
(Wei et al., 2022)
Robust VOFUL
Кnown
No
Weak
(Wei ct al., 2022)
CW-OFUL
Ö(dVK +CC)
Known
Yes
Strong
(Theorem 4.2)
CW-OFUL
Ö(dyK + dC')
Known
Yes
Weak
(Remark 4.4)
Lower bound
(Lattimore and Szepesvári, 2018)
9(dvK + dC)
Known
N/A
Strong
(Bogunovic et al., 2021)
Multi-level weighted OFUL
O C' Q(1
Unknown
Yes
Weak
(Zhao et al., 2021)
Greedy
Ō((Vak + Ö((vak+C))) C)/2o)
Unknown
Yes
Strong
(Bogunovic et al., 2021)
COBE+OFUL
ŌldVK + +
Unknown
Yes
Wcak
(Wei al., 2022)
COBE | VOFUL
Ō (00)))
Unknown
No
Weak
(Wei et al., 2022)
CW-OFUL(C = VK)
Ö(dVK), CSVK O(K), C2
Unknown
Yes
Strong
(Theorem 4.9)
CОBE + CW-OFUL
Ō(dVK + +C")
Unknown
Weak
(Remark 4.10
Lower bound
(Lattimore and Szepesvári 2018)
9(dKK), C K Q(K), C VV
Unknown
N/A
Strong
(Theorem 4.12)
1.1 Additional Related Work
Bandits with Misspecification. Bandits with misspecification can be seen a special case of bandit with adversarial corruption since it is corrupted relative evenly at each round. Let e be the misspecification level. Ghosh et al. (2017) firstly studied the stochastic linear bandits and proved sublinear regret when is small. Lattimore and Szepesvari (2019) studied the stochastic linear bandit
'The weak adversary must corrupt the rewards before the agent selects its actions, while the powerful adversary (i.e., strong adversary) can corrupt the rewards after seeing the action being selected by the agent.
'In this work, we assume there a computation oracle to solve linear optimization problems over decision set D. (e.g., Line 3 of Algorithm 1). This is implicitly assumed in almost all existing works for solving contextual linear bandit problems with infinite arms (e.g., OFUL and LinUCB algorithms); otherwise, choosing computationally intractable. In the special case that the decision set
from the infinite decision finite or the convex hull of finite set, such a computation oracle apparently exists. )
in the decision set each round is sampled from *Greedy Bogunovic et al. (2021) assumes that each arm
distribution that satisfies (r. -diverre property (Kannan al., 2018). A distribution D is (r, Aa) ddiverse if
for any a = f+++ E with E Rd and & ~ DD Amin (EEED aaa g 2 b)) 2 Ao holds for all 0 Rd and b IR satisfying b < r||0
'The lower bound under a large corruption level C' 2 / K only holds for algorithms that can achieve near- optimal regret for uncorrupted bandits. It is possible for an algorithm that does not achieve the optimal regret for uncorrupted bandits (e.g.. Hx 0.159.75 0.75) to achieve sub-linear regret in the presence of corruptions.

---

setting under milder assumptions. With the knowledge of e, they proposed an algorithm with an Ö( (lyd dK +gg()+evdd' regret, where d is the dimension of the contextual vector, N is the number of arms. Their regret bound matches their proved lower bound up to logarithmic factors. Foster et al. (2020) further considered the more general linear contextual bandits with misspecification when c is unknown to the agent, and proposed an algorithm equipped with a CORRAL meta algorithm (Agarwal et al., 2017) to deal with the unknown e. Their algorithm enjoys an (dv K + ev ( regret. Krishnamurthy et al. (2021) proposed an algorithm without using a meta algorithm which has the same order of regret as Foster et al. (2020). Our algorithm can be directly applied to the misspecification setting by choosing the corruption level C' be Ke, which immediately gives us an O(dVK + dde)) regret upper bound.
Bandits with Adversarial Rewards. There exists a large body of literature on the problems of adversarial multi-armed bandits (Auer et al., 2002; Bubeck and a line of works trying to design algorithms that can achieve near-optimal regret bounds for both stochastic bandits and adversarial bandits simultaneously (Bubeck and Slivkins, 2012; Seldin and Slivkins, 2014; Auer and Chiang. 2016; Seldin and Lugosi, 2017; Zimmert and Seldin, 2019; Lee al., 2021). However, most of these algorithms focus on the general adversarial reward setting without specifying the total amount of corruption. One of the notable exceptions is Lee et al. (2021), which assumed that the adversarial corruptions are generated through the inner product of an adversarial vectors and the contextual vector. As comparison, our algorithm and result do not need such additional assumption on the structure of the corruption. Our algorithm can be applied to both corrupted and uncorrupted settings with different choices of hyperparameters, and achieves near-optimal regret for both cases.
2012). There is also
Notation We use lower case letters to denote scalars, and use lower and upper case bold face letters to denote vectors and matrices respectively. We denote by [n|] the set {1.....n) n). For vector Rd and a positive semi-definite matrix Σ E Rdxd we denote by ||x||2 the vector's l norm and by ||x||= = vx) Σx the Mahalanobis norm. For two positive sequences {ax} and {6x} with 1, .... we write On (6,,) if there exists absolute constant C' > 0 such that an Cb, holds for all n 2 and write on = ((bb,)) if there exists an absolute constant > such that an 2 Cb,, holds for all n 2 1. We use Ō(-) to further hide the polylogarithmic factors. We use 1 to denote the indicator function.
2 Preliminaries
In this section, we introduce the setting of linear contextual bandit with adversarial corruption.
Linear contextual bandit with corruption. We define linear contextual bandits with corruption as follows: at the beginning of each round k E [K]. the agent receives a decision set Da C R from the environment and chooses an action (i.e., arm, contextual vector) x Da. After choosing the action X2 at round k, the environment generates the corresponding rkk based on the stochastic linear model r/ (0", x) + T7k, where 0' E Rd is an unknown environment parameter and m7 is the stochastic noise. After seeing the stochastic reward r'K. the adversary (i.e., attacker) introduces an adversarial corruption e onto the reward, which may depend on the decision set Dr. action X5. stochastic reward rke Finally, the agent observes the corrupted reward 1% = (0", x) + 77K + C at round k. Following Abbasi- Yadkori et al. (2011), we make the following assumptions on the bandit model.
Assumption 2.1. The linear contextual bandit satisfies the following conditions:
At each round k and any action x E Dz, we have ||x||2 S L.
For the unknown environment parameter 0" it satisfies |10" ||2 S.
At each round k the corresponding stochastic noise 7) is conditional Resub-Gaussian i.e.,
AA R. E [eA X1:k, 71:-1 11:--1 I exp( R² X22))
Regret. The goal of the agent is to minimize the pseudo-regret in the first K rounds, which is defined follows:
Regret(K) =K
k= maxxED, 10" (0", xx).

---

Corruption level. To measure the level of adversarial corruptions, we define the corruption level as C= K |cx| With this definition, say linear contextual bandit problem is C-corrupted if and only the corruption level is no larger than C.
Remark 2.2. The adversary in setting and the corresponding definition of corruption level is the same as that in Bogunovic et al. (2021) and slightly different from that in prior works such as Lykouris al. (2018); Gupta al. (2019h); Zhao et al. (2021). More specifically, in these works, the adversarial corruption C₁ is chosen before the choice of action X₃ E "Dz. Since the actions selected by the agent may not be deterministic, the adversary chooses different corruption Ck,x for different action X E DR. With this notion of corruption, the corresponding corruption level is defined as C" === maxxED, (ttx) As comparison, our adversary chooses the corruption after observing the action 2ig and for the corruption level. We have
K
K
C=
CRIXE
XE
max
|Cxx] C",
xED
A=1
k=1
which implies that corruption level C' is always larger than the corruption level C' in Lykouris et al. (2018); Gupta et al. (2019b); Zhao et al. (2021).
Algorithms
In this section, we review existing algorithms for lincar contextual bandits (and stochastic linear bandits) and discuss their limitations when they are applied to the adversarial corruption setting. Then we present our algorithm CW-OFUL and illustrate how our algorithm design can overcome the these limitations.
3.1 Existing Algorithms
We begin with reviewing the classical OFUL algorithm (Abbasi- Yadkori et al., 2011). Under Assumption 2.1, at round OFUL. estimates 0 by online ridge regression over all the past observed actions and rewards, i.e.,
0₂ + argmin A| -k- ( rT)
(3.1)
0E3d
With 0g in hand, OFUL constructs a confidence set for 0" as follows Cx { 0 1 01E S
where / is the confidence radius and Σ₁- AI Σ x is the covariance matrix of contexts X;, i = 1,..., k. Without corruption, is known that setting 3 = Ö(Rvd) guarantees that 0 e Ck with high probability, which further leads to sublinear regret (dvvK). However, with corruption, such a choice of /3 is not sufficient. To see why, we take closer look at the closed-form solution 0₂ to (3.1):
0 -
Σ X E xxx 0" +m) E
Σ X,C+.
By simple calculation and assuming À to constant, we can show that 0 - 001| x,, can be upper bounded by
| - -00 SO
Σ x
Σ
X,C
Σ
The first term 4 corruption-indeeendee and bounded by Ō according to Abbasi-Yadkor al. 1). The challenge is to bound the second term 12, which depends on the corruption. Existing approaches (Zhao et al., 2021; Ding et al., 2021) bound 12 by triangle inequality and Cauchy-Schwart inequality,
1 <
lasl max
| E
(3.2)
15
5

---

Algorithm 1 CW-OFUL
Require: Regularization parameter A, confidence radius 3 and threshold parameter
1: for round & = 1, 2. do
2: Set Σg = +I - X
3: Set by - - k-1 WxX,r, and O2 2x bB
4: Receive the decision set Di
5: Choose action X3 + argmax XED, Dr. 0xxx+ + B
6: Set wkk min [1, =
7:
end for
where is the corruption level and maxi ||x||| " is bounded by the crude upper bound L/VA. Unfortunately, such a bound makes the confidence radius be the order of O(Rvd + C), which eventually leads to an term O(CVK) in the regret, which is C times worse than the regret without corruption.
In order to obtain tighter bound of 1g. for stochastic linear bandits, Bogunovic et al. (2021) proposed a Robust Phase Elimination (RPE) algorithm, which employs optimal design (Lattimore and Szepesvári, 2018) to select the arms. In this setting, the decision set is finite and fixed over time, ie., D2 D for all i [K] and [D] S co. More specifically, RPE divides the time horizon into several phases. Within each phase, RPE performs linear regression on a multiset A C DD, which is the G-optimal design of DD Here the multiset means has duplicate elements. Let Σ be the covariance matrix defined over A, then the following upper bound holds (Lattimore and Szepesvári, 2018):
Vx E D, ||x|I== 1/4)
(3.3)
By choosing large enough [A]. (3.3) provides uniformly small upper bound for maxigisk-1 [|x ||ا"" for any k. Substituting (3.3) back into (3.2) with |AA] O(2)), we can
show that /2 is bounded by some small constant, which therefore eliminates the O(CV term the final regret. Although the optimal design- based approach RPE (Bogunovic et al., 2021) successfully eliminates the multiplicative term CVK K, it is not applicable to our linear contextual bandit setting: (1) it needs to select a multiset from the decision set, which is impossible for the general contextual bandit setting: (2) the complexity of optimal design introduces some additional quadratic term C2 in their final regret, which makes their algorithm non-optimal (See Bogunovic et al. (2021) for more details).
3.2 Our Algorithm
As we have seen before, it pivotal to bound the corruption-depencee term 1g tightly. overcome the limitations of existing approaches,
propose fundamentally new approach and present CW-OFUL in Algorithm At a high level, Algorithm I is an extension of the OFUL algorithm (Abbasi-Yadie) et al., 2011), which is also based the principle of optimism in the face of uncertainty.
Our algorithm assigns weight W/ to each selected action x More specifically, at round k, we use the following weighted ridge regression to estimate the unknown vector 0*:
O3 argmin A 2||0|| Σ w; (0 Txx rr
(3.4)
DER
The closed-form solution to the above optimization problem is displayed in Line 3 of Algorithm 1. While weighted ridge regression is not new and has been used in prior work on bandits (Kirschner and Krause, 2018; Zhou al., 2021: Russac et al., 2019), the setting, motivation and the choice of weight are fundamentally different. More specifically, we choose the weight as the truncation of the inverse exploration bonus, which is wy = min { a,a/ /|//x//122,//// Here a > 0 threshold parameter. We that for action X with large exploration bonus |x (low confidence), CW-OFUL will assign a small weight to avoid the potentially large regret caused by both the stochastic noise and the adversarial corruption. On the other hand, for the action with small exploration bonus (high

---

confidence). CW-OFUL will assign large weight to it (it can be as large as 1). Another interesting observation that by setting a be sufficiently large, the weight will become for every action, and CW-OFUL will degenerate to OFUI. -abkasi-Yadkori et al., 2011).
As comparison, Kirschner and Krause (2018); Zhou al. (2021) used the inverse of the noise variance as the weight to normalize the noise and derived tight variance-dependent regret guarantees. Russac al. (2019) set the weight as geometric sequence perform moving average deal with the non-stationary environment.
To how our choice of weight can lead to tighter regret, first write down the closed-form solution to (3.4)
k-1 x x 0" + mh) +
0 D
Σ Σ W;x;C;
where the covariance matrix Σg be a constant, we can obtain
AI Ei=1 -xx:X..
With some calculation and assuming À to
h-1
|0 00
11
50
Σ
+
A=
12
1 is the coruution-independenn term and can still be bounded by Ö(Rvd) according to Abbasi- Yadkori al. (2011). For /2, we have
Σ wXX;c
| xx
Jeja Ca.
It is evident that with our carefully designed weight, the cerruptionddpenndee term 12 can be uniformly bounded by some constant Co, the same as that in Bogunovic et al. (2021). Therefore, by setting a to be sufficiently small, our CW-OFUL can get rid of the CVK K term the final regret.
Main Results
In this section, we present the main theoretical guarantees of CW-OFUL.
4.1 Known Corruption Level C: Upper Bound
We first consider the case when C' is known to the agent. In this case, we choose RVd/C. The following lemma characterizes the estimation error of 0g with respect to 0*, which a formal summary of our discussion in Section 3.
Lemma 4.1. Suppose that Assumption 2.1 holds. For any 0 < 5 < 1 and corruption budget C' 2 0. set the confidence radius 3 = R doo ((1 + KL2/A)/0) + Vxs + aC' in Algorithm 1, then with probability least 1 8, for every round k, the estimator 0 satisfies that | 0" 01 S
The following theorem provides the regret bound of Algorithm 1.
Theorem 4.2. Suppose that Assumption 2.1 holds. For any 0 < 8 < 1 and corruption budget C' 2 0. set the confidence radius 33 in Algorithm as follows:
B = Rv d log ((1 + KLL + aC + VÁS.
Then with probability least 8, its regret in the first K rounds is upper bounded by
Regret(K) o dR (dRR
K log" ((1+ KL2/A)/8) + aCV dK log² ((L + KL2/A)/8)
Rd..
+ MXK + KL2/X)
log ((1 KL2/A)/8)
a
7

---

dSvA x log" ((1 (KLKK/3//)))) + dC vlg ((++ KL2/2//6)
In addition, if choosing (Rvd+ + VAS)/C and À /52. its regret can be upper bounded by Regret K) Ö(dVK +C).
few remarks about Theorem 4.2 are in order.
Remark 4.3. Compared with the O(dy dCvK) regret proved in Zhao al. (2021); Ding et al. (2021), our algorithm improves the multiplicative dependence on corruption level C' to additive dependence. In particular, CW-OFUL achieves the same order of regret as the uncorrupted setting when C O(vK) and it attains a sublinear regret as long as C' o(K). In sharp contrast, the algorithm proposed in Zhao et al. (2021) achieves the same order of regret as the uncorrupted setting only when C' = (1), and has a sublinear regret only when C o( K).
Remark 4.4. We also compare our result with that in Wei et al. (2022). The Robust+OOUL
algorithm in Wei et al. (2022) achieves an Ō(dv K + C,)) regret with C, = VT & which will degenerate to Ö(dvK + dvKC) in the worst case. Their regret guarantee is always worse than ours when C' < V. In addition, according the discussion in Remark 2.2, Theorem 4.2 also implies an OldvK K dC') regret under the notion of the corruption level C". In contrast, the Robust VOFUL algorithm in Wei et al. (2022) has an Ö + d'C") regret, which is also inferior to our regret. Furthermore, Robust VOFUL is computationally inefficient.
Remark 4.5. We further compare our result with previous additive regrets derived for stochastic linear bandits. Let Dj DD be the decision set. Compared with the O( dk log [D] + Cd9/2) regret for stochastic linear bandit with corruption derived Bogunovic et al. (2021), our regret improves the corruption term by a factor of vd. Note that the v difference the leading vK term between our regret and theirs is caused by the fact that Bogunovic et al. (2021) considered the finite-arm setting, while we consider the infinite-arm setting. Our algorithm will have the same regret as theirs when [D] (exp(d)).
Remark 4.6. For the uncorrupted setting where C = 0, Theorem 4.2 suggests that the threshold parameter a should be to infinity. Then by Line in Algorithm each weight we becomes 1, and CW-OFUL degenerates to OFUL. Meanwhile, the regret in Theorem also becomes O(d K) that matches the regret of OFUL (Abbasi-Yadkori et al., 2011).
4.2 Known Corruption Level C: Lower Bound
In this subsection, we refer two existing lower bound results to show that when C is known, our Ō(dVK + dC) regret is optimal up to logarithmic factors. The first proposition shows that the O(dVK) K) corruptio-inneependent term in our regret is near-optimal.
Proposition 4.7 (Theorem 24.2, Lattimore and Szepesvári 2018). Assume z 2K, R and Dr = f||x||2 < 1} for all & 2 1. Then for any algorithm, there exists an environment parameter vector 0 Rd satisfying |0* ||3 dt (48K)) such that ((Regret((K)) 2 dv (16/3)
The second proposition suggests that the (dC) corruption term in our regret is optimal.
Proposition 4.8 (Theorem 3, Bogumovic al. 2021). For any dimension d, for any algorithm that has the knowledge of C, there exists an instance satisfying with probability at least 0.5, Regret( K) R(dC).
Combining Propositions 4.7 and 4.8, we can conclude that for any algorithm, there exists a corrupted bandit instance such that the algorithm suffers at least 12max((dv (dvK/ dd')) regret. Such a lower bound matches upper bound up to logarithmic factors. Therefore, our algorithm is nearly optimal.
4.3 Unknown Corruption Level C: Upper Bound
Now we consider the case when is unknown. Our solution is quite simple for this case: we introduce tuning parameter C, which can be viewed an estimate of C, and select the threshold
8

---

parameter a as Theorem 4.2 suggests. The following theorem gives the regret upper bound of CW-OFUL for the unknown C' case.
Theorem 4.9, Under the same conditions of Theorem 4.2 except that we a (Rvd+ VAS)/C
with C being an estimated corruption level, = R² e5 and B = 2Rv dlog ((1 + KT2/2)/))
2 XS in Algorithm 1. The regret of CW-OFUI. can be upper bounded in the following two cases:
If the corruption level C' satisfies that 0 Σ C S Č, then with probability least the regret upper bounded by Regret( = O(dRv K + dC'..
If the corruption level C satisfies that C > C, the regret is upper bounded by Regret K) = O(K).
In addition, if we set the estimation C = VK, then when 0 S C S VK, the regret is upper bounded
by O(dvK).
Remark 4.10. Zhao et al. (2021) proposed an O(CPdv K) regret with unknown C' = (2(1.. Com- pared with their result, our regret (with C = VK) is strictly better in the corruption term. Bogunovic et al. (2021) proposed dK log DD Cdt. C²a) regret for the stochastic linear bandit with unknown C, in the regime C O(VK/d) /d), where D is the finite decision set. Such a regret becomes (dv/K + Cdt.5 + C²) when the size of 'D becomes exponentially large in d or even infinite. Compared with their regret, our regret is not only smaller, but also holds for a wider regime (i.e.. C ())))) Compared with the greedy algorithm in Bogunovic et al. (2021), our result does not rely on the stringent (r, Advverre property assumption on the contexts.
Remark 4.11. We also compare our result (choosing C VK) with those in Wei al. (2022) for the unknown C' case. Wei et al. (2022) proposed a COBE+OFUL algorithm with an ((d K KC,) regret, and a COBE- algorithm with an (dd.5 /K + +""C") regret, analogous to their results for the known C case discussed in Remark 4.4. Our CW-OFUL enjoys better regret than COBE+OFUL for all C, and is better than COFU+ for C' < vk. In addition, for the modified notion of corruption level C", if we choose the basic algorithm in COBE (Wei et al.. 2022) as our CW-OFUL algorithm, then Theorem 3 in Wei et al. (2022) suggests that COBE+CW-OFF OFUL can deal with unknown corruption level C' and obtained an Öd K + dC") regret guarantee, which matches the regret of CW-OFUL algorithm with known corruption level C". Note that COBE+VOFU is also computationally inefficient.
4.4 Unknown Corruption Level C: Lower Bound
With Ö = K. for the case when 0 S C S VK, our regret result is already near-optimal, due to the lower bound for the uncorrupted bandit in Proposition 4.7. Now we show that our O(K) bound, seemingly trivial is actually optimal for a large class of bandit algorithms. In detail, the following theorem provides lower bound result for any algorithm for the unknown case. This is an extension of the lower bound result in Bogunovic et al. (2021) from d = 2 to general d.
Theorem 4.12. For any algorithm Alg, let Rx be an upper bound of Regret K) such that for any bandit instance satisfying Assumption 2.1 with C = 0, it satisfies the E (Regret(K)) S Rx < O(K), where the expectation is with respect the randomness of the algoríthm and the stochastic noise. Then for the general case with C = 2 Rx(xx/ ////// /d), such an algorithm will have E. Regret( K)] = Q(K).
Remark 4.13. If we selects the estimated corruption Ö (2(Rk/d) Theorem 4.9 immediately implies that CW-OFUL enjoys a O(Rx) regret when corruption level C' < ( /d) and O(K) regret when corruption level C > 9(Rx/d) Compared with the algorithm Alg, Theorem 4. suggests that CW-OFUL is no worse than the algorithm Alg no matter whether the corruption level More discussion can be found in Appendix A.
C' < (((x/dd
Conclusion and Future Work
In this work, we study corrupted linear contextual bandits. We propose CW-OFUL algorithm based on weighted ridge regression with truncated inverse exploration bonus weights. We show that for

---

both cases when the corruption level C' is known or unknown to the agent, CW-OFUL achieves regret that matches the lower bound up logarithmic factors.
We are also interested in achieving the optimal regret when specializing our algorithm to the misspec- ified linear contextual bandits.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers and area chair for their helpful comments. JH, DZ and QG are supported in part by the National Science Foundation CAREER Award 1906169 and the Sloan Research Fellowship. TZ is supported in part by the GRF 16201320 320.. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
ABBASI- YADKORI, Y., PÁL, D. and SZEPESVÁRI, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems.
AGARWAL, A., LUO, H.. NEYSHABUR, B. and SCHAPIRE, E. (2017). Corralling a band of bandit algorithms. In Conference on Learning Theory. PMLR.
AUER, P., CESA- BBAANHI, N., FREUND, Y. and SCHAPIRE, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM journal computing 32 48-77.
AUER, P. and CHIANG, C.-K. (2016). An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Conference Learning Theory. PMLR.
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. PMLR.
BUBECK, S. and CESA-BIANCHI, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. arXiv preprint arXiv: 1204.7221
BUBECK, S. and SLIVKINS, A. (2012). The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory. JMLR Workshop and Conference Proceedings.
CESA-BIANCHI, N. and LUGOSI, G. (2006). Prediction, learning, and games. Cambridge university press.
DESHPANDE, Y. and MONTANARI, A. (2012). Linear bandits in high dimension and recommendation systems. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE.
DING, Q., HSIEH, C.-J. and SHARPNACK, J. (2021). Robust stochastic lincar contextual bandits under adversarial attacks. arXiv preprint arXiv:2106.02978.
FOSTER, J., GENTILE, C., MOHRI, M. and 7IMMERT, J. (2020). Adapting to misspecification
in contextual bandits. Advances in Neural Information Processing Systems 33 11 11478-1 1149.
GHOSH, A., CHOWDHURY, S. R. and GOPALAN, A. (2017). Misspecified linear bandits. In Thirty-First AAAI Conference on Artificial Intelligence.
GUPTA, A., KOREN, T. and TALWAR, K. (2019a). Better algorithms for stochastic bandits with adversarial corruptions. Conference on Learning Theory. PMLR.
GUPTA, A., KOREN, T. and TALWAR, K. (2019b). Better algorithms for stochastic bandits with adversarial corruptions. Conference on Learning Theory. PMLR.
HORN, R. A. and JOHNSON, C. R. (2012). Matrix analysis. Cambridge university press.
10

---

KANNAN, S., MORGENSTERN. J. H., ROTH, A., WAGGONER, B. and WU. Z. S. (2018). A smoothed analysis of the greedy algorithm for the linear contextual bandit problem. Advances in neural information processing systems 31.
KIRSCHNNR, J. and KRAUSE, A. (2018). Information directed sampling and bandits with het- eroscedastic noise. In Conference On Learming Theory. PMLR.
KRISHNAMURTHY, S. K., HADAD, V. and ATHEY, S. (2021). Adapting to misspecification in contextual bandits with offline regression oracles. In International Conference on Machine Learning. PMLR.
LATTIMORE, T. and SZEPESVÁRI, C. (2018). Bandit algorithms. preprint 28.
LATTIMORE, T. and SZEPESVARI, C. (2019). Learning with good feature representations in bandits and in rl with generative model. arXiv preprint urXiv:191..07670
LEE, C.-W., LUO, H., WEI, C.-Y., ZHANG, M. and ZHANG, X. (2021). Achieving instance- optimality and minimax minimax-optimality in stochastic and adversarial linear bandits simultaneously. In International Conference Machine Learning. PMLR.
LI, Y., LoU, E. Y. and SHAN, L. (2019). Stochastic linear optimization with adversarial corruption. 1etp::9990000000
arXiv preprint
LYKOURIS, T., MIRROKNI, V. and PAES LEME, R. (2018). Stochastic bandits robust to adversarial corrpptions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing.
RUSSAC, Y.. VERNADE, and CAPPÉ, O. (2019). Weighted linear bandits for non-stationary environments. Advances in Neural Information Processing Systems 32.
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.
SELDIN, Y. and SLIVKINS, A. (2014). One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning. PMLR.
WEL, C.-Y., DANN, C. and ZIMMERT, J. (2022). A model selection approach for corruption robust reinforcement learning. In International Conference on Algorithmic Learning Theory. PMLR.
Zuao,, H., Zuoo, and GU, Q. (2021). Linear contextual bandits with adversarial corruptions. arXiv preprint arXi:2110.12615.
ZHOU D., GU, Q. and SZEPESVARI, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory. PMLR.
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
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes]. [No], or [N/A]. You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We study corrupted linear contextual bandits and propose a computation efficient algorithm with near-optimal regret guarantee.
(b) Did you describe the limitations of your work? [Yes] See the discussion about Misspecified linear bandits in subsection 4.1.
(c) Did you discuss any potential negative socictal impacts of your work? [N/A] Our work focuses purely theoretical problem and does not have any negative social impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes) See Assumption
2.1.
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect 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]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "d76496zjzcW", "reviewer": "Reviewer_vcvT", "summary": "The authors consider the problem of linear contextual bandits with adversarial corruptions. In this framework, at each iteration k of the game, the learner has to select one action x from a decision set D_k.  The environment then generates a reward based on that action, an unknown environment parameter and some stochastic noise. The adversary observes the rewards and then decides how much corruption to add to it using the knowledge of the action set, the chosen action, and the stochastic reward.  This definition of corruption is similar to the one in the recent work of Bogunovic et al. (2021), but prior works (in particular Lykouris et al. (2019)) consider a model where the adversary sets the corruption before the learner chooses an action. \nIn this work, the authors consider both the settings with known and unknown corruption levels and derive algorithms which are optimal up to logarithmic factors, improving the state of the art in both cases. In the case with known corruption level, prior works could be suboptimal due to different factors: the corruption level was either a mutliplicative factor in the regret bound, giving a term that depends on the product of the total corruption and the square root of the number of iterations, or, in the work of Wei et al. (2022) ifthe corruption level was an additive terms, then the algorithm suffered a worst dependency in the dimension of the context $d$ as well as being computationally inefficient.\nIn contrast, the current approach achieves the correct dependency on $d$ and on $C$ up to logarithmic factors without being as computationally expensive.  \n\n In the case with unknown corruption level, they notably complete the analysis of the problem by providing a lower bound for problems that have a large corruption level ($C >= \\sqrt K$) and derive upper bounds for both small and large values of corruptions, matching up to logarithmic factors when the level of corruption is small and up to constants when it is large, as the bound is in $\\theta (K)$, making it impossible to achieve sublinear regret.\nImportantly, this result is robust to a larger amount of corruptions than some of the previous results (Zhao et al. 2021), and similarly to the case with known corruption level, it achieves the correct dependency on $d$ and on $C$.\n\nThe method is based on the OFUL framework (optimism in face of uncertainty), which is similar to the rest of the litterature, and uses  weighted ridge regression with a novel choice of weights, which are based on the inverse of an exploration parameter that is trunctated to provide stability and robustness against noise and adversarial corruption.", "questions": "Section 4 could be rephrased to improve clarity and readability. \nIn particular:\n- in section 4.1, paragrpah titles could benefit from being more highlighted than the remarks title  (see Lower bound line 262 for example).\n- the phrasing of line 292 in theorem 4.9 is not very intuitive.\n- remark 4.13 seems to be a proof sketch of theorem 4.12, and could be identified as such.", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper follows a long line of works on the problem of linear contextual bandits with adversarial corruptions, and provides substantial improvements by being the first capable to match lower bounds up to logarithmic factor, improving upon the dependency on the corruption level or the dimension of the context.  The results are significant, yet the proposed algorithm is elegant and relatively simple, and the proofs look sound.   \nIt is nice that problem dependent type of bounds are also presented in the appendix.\n\nThe paper is well written, with a particular focus on relating their results with the rest of the litterature. \nI would still point out that section 4 is really dense, making it somewhat difficult to identify the key results. The remarks in the section are important and should not be removed, but there may be a way to restructure that section such that the results of this work are easier to identify. \n\n\n ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6kkcZPdWciu", "reviewer": "Reviewer_ka6i", "summary": "This paper studies the problem of linear contextual bandits with adversarial corruptions. They focus on the setting with a powerful adversary who attacks after seeing the learner’s action. The authors propose a weighted-OFUL algorithm for this setting, which is also the first to use weighted least square for solving adversarial corruption problems. They derive the near-optimal \\tilde{O}(d\\sqrt{K}+dC) regret upper bound for the C-known setting. And for the unknown setting, they show O(d\\sqrt{K}) regret when C\\le \\sqrt{T} and \\Theta(T) regret when C>\\sqrt{T}. ", "questions": "Can you incorporate more discussions on how the current analysis dealt with the powerful adversary and why previous works fail? For example, the algorithm in Zhao et al. is also weighted OFUL with enlarged confidence radius. What is the key difference that make their algorithm work with a weaker adversary?", "limitations": "The work is about online learning theory and does not have negative societal impact. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n\nThis paper studies the linear contextual bandit problem with potential infinite arms and dynamic action sets. Their proposed algorithm is a novel attempt using the previously well-known weighted least square technique to solve the corruption problem. \nThe derived results show an advantage over previous works. When C is known, they provide a near-optimal upper bound of order O(d\\sqrt{T}+dC), which matches the lower bound in both the uncorrupted setting and corruption setting. This result also improves previous results in the corruption setting. When C is unknown, they show that the regret is Theta(d\\sqrt{T}) when C\\le \\sqrt{T} and is \\Theta(T) otherwise. \n\nWeakness:\n\nThere are too many remarks in the paper. And the presentation in each remark is not easy to follow. I think a clearer way to compare with previous works would be to complete the table to incorporate more comparable information, e.g, powerful adversary, computation efficiency, (in)finite (fixed) action set, (un)known C and its value range, the value of Cr and C’, etc. \nIn stochastic linear bandits, the O(d\\sqrtT+C) regret derived by Chung-Wei Lee et al [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously, ICML2021] is also comparable. \n\nDetailed comments:\n\nLine 123: D_k\\in R^d should be D_k\\subseteq R^d\n\nLine 134 equation: what is \\epsilon_{1:k-1}?\n\nLine 198: estimated\n\nLine 40-46: Li et al., 2010 can also handle infinite arm case. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "23NBGAuqOTP", "reviewer": "Reviewer_Ccme", "summary": "The paper considers the linear bandits setup with adversarial corruptions. Although the problem is well studied, the authors propose a variant of the well known OFUL algorithm, where the weights are chosen in a specific manner. It is argued that if the corruption level is known, giving weight inverse to the confidence radius makes the algorithm robust. The analysis is done in both settings where the level of corruption is known and unknown. Appropriate lower bounds are provided to support the claims.", "questions": "See the weakness part\n\nThanks to the authors for providing a convincing response. I increase my score to 6 now.", "limitations": "Not applicable", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nWriting: The paper is well written and easy to follow. The short calculations are quite helpful.\n\nRelated work and comparison: The known C part is well written and compared with the previous literature quite exhaustively.\n\nWeakness:\nI think the main weakness of the paper is the setup where the corruption level is not known. What is the algorithm here? How will I estimate \\bar{C}? If I overestimate, I would incur linear regret, and so it is of importance to know how this estimation is done.\n\nIn practical situations, the total level of corruption won’t be provided in advance, and so an algorithm must estimate it in a structured manner, not leave it as tuning parameter. I know some previous work have done so, but that seems incomplete--although a lot of non trivial unknown C papers are written, as the author themselves refer. Please comment on this.\n\nValidation: It would be great if the weighted OFUL can be implemented, even in a simple finite arm setting (or using the tricks, via Thompson Sampling etc, Russo and Van Roy)\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0DfCWPOA90x", "reviewer": "Reviewer_MF5t", "summary": "This study considers linear contextual bandits with adversarial corruption and proposes a UCB-based algorithm.\nWhen the corruption level $C$ is the proposed algorithm with a tuned hyperparameter achieves a tight regret bound depending on $C$.\nFor the case of unknown $C$, the algorithm achieves a nearly optimal bound if $C$ is at most the square root of the number of rounds.\nThis result turns out to be in some sense the best theoretical guarantee, which follows from a newly proven lower bound.\n", "questions": "\n- What exactly does \"computationally efficient\" mean? Even when the decision set is a convex set as in Proposition 4.7., I don't think it is clear whether the optimization problem in Step 5 of Algorithm 1 can be solved in polynomial time as the objective function is nonconvex. The case of exponentially large decision set (e.g., $D_k = \\{-1  , 1 \\}^d$) is also non-trivial.\n\n- Can we obtain improved regret bounds for the case in which the size of $D_k$ is bounded? (e.g., regret bound depending on $\\sqrt{d \\log |D_k| }$ instead of $d$?)", "limitations": "The limitations are adequately addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Regret bounds are nearly tight.\n- The proposed algorithm is simple and computationally efficient.\n\nWeaknesses:\n\n- The \"optimality\" of the algorithm in the case where $C$ is unknown is somewhat limited. In fact, the algorithm is nearly optimal among \\textit{algorithms that achieve a near-optimal regret bound for uncorrupted cases}.\n- There is little novelty in the algorithm and analysis.\n\nComments:\n\nI believe that the results are sufficiently impactful, as they provide a nearly tight regret bound for the important problem of contextual linear bandit with adversarial corruption.\nThe proposed algorithm is surprisingly simple compared to that of existing studies, and appears to be practical.\n\nThe description of lower bound for unknown C in Table 1 ($\\Omega(K), C \\geq \\sqrt{K}$) may be misleading.\nWhat we can actually say would be that: any algorithm that achieves $O(d \\sqrt{K})$-regret for $C = 0$ suffers $\\Omega(K)$-regret for some $C \\geq \\sqrt{K}$ in the worst case.\nI don't think this conditioning of the algorithm should be omitted.\n\n\nLine 19: an decision set <- a decision set\n\nLine 266: a environment parameter <- an environment parameter\n\nSupplementary (G.4): $\\lambda \\| theta^* \\|_{\\Sigma_k}$\n <- \n$\\lambda \\| theta^* \\|_{\\Sigma_k}^{-1}$", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept