Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This work focuses on Gaussian Process Bandits setting where the reward observations are corrupted by an adversary. The work proposes an algorithm robust to adversarial corruption. The work shows that the regret of the algorithm in O(C\gamma^{3/2}_T), where C is the amount of corruption, T is the time horizon, and \gamma_{T} is the maximal information gain. This bound is tighter than the previously existing bound O(C\sqrt{T\gamma_{T}}). 

The key difference between the proposed algorithm and the previous algorithm in this setting is that the proposed algorithm uses the trick of phased elimination based on confidence bounds to achieve this additive dependence on C (instead of multiplicative dependence). The analysis is carried out under an additional assumption, Assumption 1,  on the non-corrupted observations. 

strengths_and_weaknesses: Originality:
The novelty of the algorithm is limited. A phased elimination trick is applied to the previously known UCB estimator of parameters in Gaussian Process Bandits setting. In literature, this strategy of Phased elimination has been applied in linear bandits to achieve a robust phased elimination algorithm. Since Gaussian Process Bandits setting has been studied previously, the proposed algorithm is a combination of these works.

Additionally, the technical analysis is carried out under Assumption 1. This assumption is not common in the previous works in the literature. The need for this assumption is unclear since it is applied over an estimator used in a setting without corruption. 

The work presents a few examples of sampling strategies that satisfy Assumption 1. However, in Lemma 4, the assumption states that the sample x_t is independent of all y_i, i<t. In an online setting, this assumption may not hold since sample x_t is dependent on the previously collected samples. 

Quality and Clarity: Paper is well-written and key ideas developed in the paper are discussed. 

Significance:

The significance of the setting and the paper is unclear because the results are not directly comparable with the literature, and the novelty in the algorithm is limited. 

questions: 1)	I would suggest authors to clarify the motivation behind Assumption 1. Is it common in the literature? If yes, please point to the references? If not, please clarify the comparison of the theoretical results with the literature.

2)	Can you please provide intuition regarding the Assumption 1 being applicable to a specific estimator? Is there an analogue of this assumption in terms of assumption on the setting instead of a specific estimator? 

3)	How does the strategy in Lemma 4 applicable to the proposed algorithm under Assumption 1 given the independence assumption? 

limitations: Yes
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 paper proposes a new algorithm for robust optimization of Gaussian process bandits and prove that it provides tighter regret guarantees with respect to the corruption budget (in an additive model of reward corruptions). The algorithm divides the time horizon into phases of increasing length, where in each phase the action set is pruned and only a limited number of actions (based on an information gain criterion) are actually played. The proofs and the empirical proofs both show that the algorithm is robust to corruptions.
strengths_and_weaknesses: Strengths:
- The paper is very well-written -- the setting, comparison with related work, the algorithm and their main contributions are all clearly identified.
- The work covers significant ground, such as, working through older techniques that do not readily lead to the tighter bounds provable with the proposed algorithm.

Limitations:
- The proposed algorithm assumes that the corruption budget $C$ of the adversary is known in advance (that is, knowledge of $C$ is needed to operationalize the algorithm itself, not just to prove its regret bounds). It is not clear how to set this practically, or what the effect of misspecification might be.
- The algorithm introduces significant complexity which may not be justified by the benefits it brings. The empirical results show that the regret scales similar to another robust GP algorithm [1] (and the performance is in fact worse in absolute terms). It leaves the open the question of whether a tighter bound can be obtained for the previous approach. As such, it is not clear if there exists a setting where this algorithm shines and how important the corruption term itself is.
- Minor: the results hold under fairly strong assumptions on the model (e.g. variance in eq (6) unaffected by corruptions by design, bounded rewards which satisfy budget constraints under addition)

[1] http://proceedings.mlr.press/v108/bogunovic20a/bogunovic20a.pdf  
questions: 1. It would be useful to understand the performance of the algorithm in a setting where the corruption budget $C$ is misspecified, and compare it with the other robust GP algorithm [1].
1. What is the optimal adversarial strategy for allocating corruption budget? Including it as one of the attack methods in Section 4, if feasible, would be useful.
1. Minor: please define before you use SE (line 62) and $GP(0,k)$ (line 99) .

[1] http://proceedings.mlr.press/v108/bogunovic20a/bogunovic20a.pdf  
limitations: Not applicable.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considered the bandits problem where the result function lives in an RKHS space and can be corrupted within C budgets. When C is known in advance, the author proposed a robust elimination-type algorithm that achieves a regret bound with the C term only appearing in additive terms, which significantly improves the current result where the C appears multiplicatively.   This result is near-optimal in the SE kernel. Besides the theoretical results, the authors also provide simulation results with a different type of attack.
strengths_and_weaknesses: Strength:

1\ The author gives the first near-optimal result (in some special cases) in RKHS setting with sound proofs.

2\ The author gives refined enlarged confidence bound analysis compared to C in [7], which is somehow interesting.

3\ The authors provide simulation results for various attacks.

Shortcoming：

1) This rare switch technique, although claimed by the authors that “To our knowledge, we are the first to use rare switching to achieve adversarial robustness; previous works instead used it for reducing computational complexity.” I personally think it has been used in many other places to get stability in the algorithm analysis. Of course not totally the same, but not that novel. Especially, the author states “we obtain more samples of the same point, allowing us to average more of them together and making the “averaged” observation harder to corrupt.” But to me, it is just a variant of basic doubling techniques in most elimination-type algorithms.

Maybe there is some difficulty/novelty in incorporating “rare switch” technique in this particular framework that I do not correctly understand? If the author can illustrate more on this I am willing to adjust my score.

2)  I am not totally convinced by the author’s claim that the Gaussian process with KNOWN corruptions is a hard problem because this algorithm is mainly improved upon on the framework of [7][8] with some well-known techniques (rare-switch, enlarged confidence). Giving a complete result with unknown corruption may make the paper stronger.


questions: Can you give more explanation on the intuition behind the result of Lemma 2? It is not very clear to me. From its proofs in the appendix, it seems to me just a direct but more careful calculation result with corruption presented. So I am just curious why no one achieve that before. Are there any particular techniques I need to pay attention to?
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: Setting:
A sequential decision-making problem- Gaussian process bandit optimization, where the signal observed by the learner may be adversarially corrupted up to some budget parameter C.

More specifically, there is an unknown reward function f with a bounded norm in a Reproducing Kernel Hilbert Space. 
In the standard model without corruptions, the learner chooses a strategy x and observes f(x) + stochastic (sub-gaussian) noise. In the model with corruption, additional adversarial noise is added to the observed signal.
The learner would like to minimize its cumulative loss over T rounds.

The main contribution is an algorithm with regret of sqrt{T*Info-gain}+C*info-gain^3/2, which improves on a previous bound of C*sqrt{T*info-gain} for some types of kernels. 
The algorithm is based on confidence bounds that take into account the corruptions.
Moreover, the algorithm obtains more samples of the same point such that the average is harder to corrupt - "rare switching".


strengths_and_weaknesses: The paper improves on a previous result from "Corruption-tolerant Gaussian process bandit optimization" (AISTATS 20).

The "rare switching" idea is nice for improving robustness.

On the negative side, C is known to the learner, as opposed to some other related models (not bandit optimization). Crucially, the corrupted confidence bounds depend on that.
questions: I think that it is worth mentioning other papers that study very related models with corruptions, for example:
Prediction with Corrupted Expert Advice (Neurips 20),
Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs (Neurips 21),
Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds (COLT 22),
and many references therein.
limitations: -
review_title: null

Meta-review: metareview: The paper studies Gaussian process bandit optimization in the adversarial corruption model. This setting was considered in the work of [7] and regret bounds were presented where the adversarial term contains both the time horizon T and the corruption level C, which is not ideal. The current paper presents an improved algorithm that for certain kernels such as SE removes the dependence on T in the adversarial term and for other settings such as linear recovers the current best results. 

The reviewers likes the contributions of the paper. One of the reviewers (objk) raised an objection about one of the assumptions mentioned in the paper and the authors clarified that the assumption is just a condition that can always be satisfied by appropriate choices of parameters. While the reviewer was not convinced, based on my own reading of the paper, I side with the authors.

This is a decent theoretical contribution. The one weakness of the work is that it assumes that the corruption level (C) is known in advance (or an upper bound on it). Prior works on GP bandit optimization and also in the case of multi-armed bandit settings handle unknown corruptions. As a result this is a borderline paper but I'm slightly leaning towards acceptance at this time.
confidence: Less certain
Decision: Accept