Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: 
This paper studies a variant of collaborative linear bandits where $\alpha$ fractions of M-agents act adversarially in a centralized setting. They propose a phased elimination algorithm with robust confidence intervals that achieves \tilde{O}((\alpha M+\sqrt{M})\sqrt{dT})  bound for the group regret. They also provide a lower bound on a slightly different model where each agent acts adversarially with probability $\alpha$, showing that the additive term $\alpha \sqrt{T}$ term is unavoidable. They further consider generalized linear bandit setting and contextual bandit setting.

strengths_and_weaknesses: Strength:
They propose a novel problem for the collaborative bandit learning with adversarial agents. This problem is a good capture of the real-world case of multiple data observation points, some of which are spammed or collapsed.

They propose a first algorithm named Robust Collaborative Phased Elimination: good agents follow the arm selection based on G-optimal design and report their estimate and adversarial agents report arbitrary vectors. The central server must consider both statistical uncertainty and adversarial one. To overcome this, they consider a robust confidence interval for each active arm and employ robust mean pay-offs. The server decides which to eliminate in each phase. The presented regret analysis and lower bound shows the optimality of the algorithm.

They further consider generalized linear bandit setting and contextual bandit setting.



Weakness:
Sometimes a sentence is too long or difficult to read (but in general, the paper is well structured)

The section “Related Work” is cluttered, citing more than 10 papers at a time. If you are proposing a new model, please provide a more careful summary of existing research and its position in the literature. 

questions: What if corruption fraction $\alpha$ is unknown to the system?


In algorithm 1, how do good agent's performance affect the resulting group regret? Indeed, it is not clear to me why G-optimal design is just solved approximately, though it can be exactly solved efficiently via convex optimization. 

＝＝Post Rebuttal＝＝

Thank you for author's detailed response. I have read other reviews and its response, which even made me vote for acceptance. 
Hence I will keep my score.
limitations: -
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 work focused on the collaborative linear bandit problem with adversarial agents. The author proposes novel robust algorithms for the linear bandit and general linear bandit problems, with a $(\alpha+1/\sqrt{M})\sqrt{dT}$ regret guarantee for each good agent. In addition, the author also provides a theoretical lower bound for the regret with adversarial agents and shows that the $\alpha \sqrt{T}$ regret is unavoidable.
strengths_and_weaknesses: Strength:

1. The author provides theoretical guarantees for the algorithms and achieves a near-optimal regret guarantee without adversarial agents. In addition, the lower bound suggest that the adversarial-dependent term $\alpha \sqrt{dT}$ is near optimal with the factors $T$ and $\alpha$.

2. For this problem, the author also provides a theoretical guarantee for the lower regret bound. 

Weakness:

 The algorithms require the stochastic noise to be Gaussian rather than sub-Gaussian, which is much more restrictive than previous work in linear bandit. In addition, for the contextual linear bandit and general linear bandit requires that all agents have the same feature vectors, which is far from the practice.

questions: 1. In the related work part, the author mentions recent advances in regret guarantees for the adversarial corruption bandit problem. More recent advanced works have focused on using the function approximation techniques. For instance, He et al. [2022] obtain a near-optimal regret guarantee with adversarial corruption. It is better if the author can mention them or discuss them.

He J, Zhou D, Zhang T, et al. Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions

2. Since all theorems focus on regret for a single good agent, it seems unnecessary to consider total regret in equation (11).
limitations: This paper provides theoretical guarantees for learning linear bandit and linear mixture MDP. There is no negative societal impact.
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 considers the collaborative linear bandit problem in the case of adversarial agents. In the proposed setting, a fraction $\alpha$ of agents can be adversarial. The main dilemma comes from the fact that although the collaboration reduces the number of required samples when adversarial agents are present, this can also work in the opposite direction. Besides the introduced setting, the authors propose a novel phased elimination algorithm that archives tight regret guarantees in the considered setting. Besides, the results are also provided for the two related settings: generalized linear bandit and the contextual bandit setting. 
strengths_and_weaknesses: This is a well-written paper that considers an interesting twist to the collaborative linear bandit problem inspired by some recent works in the corrupted bandit literature. One of the main contributions is a novel and interesting setting that is first introduced in this paper, and that is not (to my knowledge) considered before.

When it comes to the setting, one might argue why such a clean distinction among adversarial and non-adversarial agents, i.e., perhaps, in practice, it might make sense that even “good” agents suffer some adversarial observations. On the other hand, I can see how this clean separation (coming from the problem setting) is suitable for the median of means tools used in the analysis. 

Can you please comment on  $\alpha \in [0, 0.5)$, and what prevents us from $\alpha > 0.5$? What are the limits here? For example, in case each good agent plays individually the bound $(1-\alpha) M \sqrt{dT}$ should still hold, i.e., it does not depend on $\alpha$ being in  $[0, 0.5)$.

While the phased algorithm and inflated confidence bounds are used in some similar adversarial settings, I still think the theoretical results of this paper are solid, and the techniques used in the analysis are different from the previous works. The obtained results are tight, as is evident by the lower bound result. Finally, the results are also provided for the GLM and contextual settings. 

The paper is missing simulations. I would argue that a natural baseline is an algorithm that ignores collaboration. Depending on $\alpha$, one can compare the proposed algorithm to that non-collaborative but completely robust one. Also, it is very easy to generate attacks in this setting by simply generating various $\hat{\theta}$’s in the case of adversarial agents. 

Finally, I think that this is an interesting work with solid theoretical results that can be of interest to the community. After the discussion period, I might rethink my score and consider increasing it. 

Some minor suggestions to improve:
- I’m not sure that Corollary 1 is needed. Too much space is used to multiply the result of Theorem 1 with M. Perhaps, consider removing it and using this additional space to provide more intuition on the “Construction of Robust Arm-Payoff Estimates and Confidence Intervals”. 
- Problem formulation: Line 95: ”Based on all the information acquired by an agent ut to time…” This sentence was confusing because it was not clear how this is collaborative. It reads as if the agent only has access to its own observed rewards. Later on, this was explained, but a more careful introductory paragraph could avoid confusion. 

questions: Please see the previous section.
limitations: Yes, I think so.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers the collaborative stochastic linear bandit problem where an $\alpha$ portion of the $M$ agents may act arbitrarily.
* The authors provided an algorithm RCLB that enjoys $\mathcal O((\alpha+1/\sqrt M)\sqrt{dT})$-style regret bound for each good agent.
* They also proved that regardless of $M$, an $\alpha\sqrt{dT}$ factor is unavoidable. So the regret bound of RCLB is nearly tight.
* They generalized the results to generalized linear bandits (GLM) and contextual linear bandits (CLB), giving near-optimal guarantees as well.
strengths_and_weaknesses: Pros:
* This work is the first to consider the presence of misbehaving adversaries among the agents, showing that it is still possible to achieve $\mathcal O(\sqrt{MdT})$ total regret even with adversaries.
* The algorithm is not much more complicated compared to usual phase elimination algorithms (where there is no adversaries).
* The authors justified that the algorithm is worst-case optimal by showing both $\sqrt{MT}$ and $\alpha \sqrt{dT}$ factors are unavoidable.
* The algorithm is also the first to work in harder generalizations (collaborative GLMs and CLBs with adversaries) while achieving near-optimal regret.

Cons:
* The algorithm is not computationally efficient as it builds on phased elimination.
* The noise model is assumed to be independent Gaussians.
questions: * Is it possible to implement this algorithm more efficiently?
* Is this algorithm able to handle more general noise models other than independent Gaussians (e.g., conditionally 1-sub-Gaussian or $[-1,1]$-bounded noises which are common in the linear bandit literature)?
limitations: See Questions.
review_title: null

Meta-review: metareview: This work studies an interesting collaborative linear bandits problem and makes solid technical contributions (efficient algorithms, optimal regret, and generalization to other settings). Clear accept. Please do address the minor issues pointed out by the reviewers in the final version.
confidence: Certain
Decision: Accept