Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
Writing: The paper is well written and easy to follow. The short calculations are quite helpful.

Related work and comparison: The known C part is well written and compared with the previous literature quite exhaustively.

Weakness:
I 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.

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

Validation: 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)

questions: See the weakness part

Thanks to the authors for providing a convincing response. I increase my score to 6 now.
limitations: Not applicable
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
In 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.
In contrast, the current approach achieves the correct dependency on $d$ and on $C$ up to logarithmic factors without being as computationally expensive.  

 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.
Importantly, 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$.

The 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.
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.   
It is nice that problem dependent type of bounds are also presented in the appendix.

The paper is well written, with a particular focus on relating their results with the rest of the litterature. 
I 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. 


 
questions: Section 4 could be rephrased to improve clarity and readability. 
In particular:
- in section 4.1, paragrpah titles could benefit from being more highlighted than the remarks title  (see Lower bound line 262 for example).
- the phrasing of line 292 in theorem 4.9 is not very intuitive.
- remark 4.13 seems to be a proof sketch of theorem 4.12, and could be identified as such.
limitations: NA
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This study considers linear contextual bandits with adversarial corruption and proposes a UCB-based algorithm.
When the corruption level $C$ is the proposed algorithm with a tuned hyperparameter achieves a tight regret bound depending on $C$.
For 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.
This result turns out to be in some sense the best theoretical guarantee, which follows from a newly proven lower bound.

strengths_and_weaknesses: Strengths:

- Regret bounds are nearly tight.
- The proposed algorithm is simple and computationally efficient.

Weaknesses:

- 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}.
- There is little novelty in the algorithm and analysis.

Comments:

I 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.
The proposed algorithm is surprisingly simple compared to that of existing studies, and appears to be practical.

The description of lower bound for unknown C in Table 1 ($\Omega(K), C \geq \sqrt{K}$) may be misleading.
What 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.
I don't think this conditioning of the algorithm should be omitted.


Line 19: an decision set <- a decision set

Line 266: a environment parameter <- an environment parameter

Supplementary (G.4): $\lambda \| theta^* \|_{\Sigma_k}$
 <- 
$\lambda \| theta^* \|_{\Sigma_k}^{-1}$
questions: 
- 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.

- 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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}. 
strengths_and_weaknesses: Strength: 

This 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. 
The 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. 

Weakness:

There 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. 
In 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. 

Detailed comments:

Line 123: D_k\in R^d should be D_k\subseteq R^d

Line 134 equation: what is \epsilon_{1:k-1}?

Line 198: estimated

Line 40-46: Li et al., 2010 can also handle infinite arm case. 
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.
review_title: null

Meta-review: metareview: The paper was generally well-received by the reviewers, who appreciated the contributions, especially the tightness of the bounds and the simplicity of the algorithm. The minor concerns raised in the original reviews were all addressed in the rebuttal, and eventually all reviewers agreed that the paper is suitable for publication at NeurIPS 2022. The authors are encouraged to take all the reviewers' comments into account when preparing the final version of the paper.

One remaining technical concern that needs to be clarified in the final version is the computational efficiency of the proposed algorithm, as raised by reviewers MF5t and Ccme. In their response to reviewer MF5t, the authors erroneously claimed that a linear optimization oracle suffices to implement their algorithm, even though the objective function maximized in the implementation is a nonlinear, strictly convex function. However, the challenge of solving such potentially intractable optimization problems is not unique to this particular algorithm, and indeed all OFUL / LinUCB style methods require solving similar problems --- see, e.g., the discussion in Section 19.3.1. in "Bandit Algorithms" by Lattimore and Szepesvari. The final version should correct the confusing claims about this computational issue, for example by simply updating footnote 4 in the current draft.
confidence: Certain
Decision: Accept