Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the best-arm-identification problem in the Huber contamination model where each arm has some probability epsilon of being sampled from some adversarial distribution. 

The setting in [4] was modified by replacing the median estimator with a trimmed-mean estimator. Since adversarial corruptions can make the original mean unidentifiable, the authors assume that the corruptions do not change the ranking of the arms.

The authors propose a new bandit algorithm, based on this estimator, and provide upper bounds on its regret. They also provide a new lower bound for any partially identifiable bandit instance.

The proposed algorithms are evaluated on both real and synthetic data.


main_review: I'll be begin by saying that the paper was a pleasure to read; the prose was clear, the results complete (in that matching upper and lower bounds were provided), and paper as a whole flowed nicely. 

However, my huge reservation is that this work does not add much beyond the results from [4] aside from empirical evaluations. From what I can tell, the only difference is that the median estimator was replaced by a alpha-trimmed mean estimator which allows for correct identification of the mean when the arms are subgaussian. While the new algorithm is analyzed to a satisfactory extent, it does not add enough to our understanding of the contaminated bandit problem to warrant a separate publication. Additionally, the paper should be clearer about what is novel and what is inherited from prior work, as it occasionally reads as innovating much more than it should.

How are the assumptions on bandit instances which convergence of the median more restrictive, as claimed on line 246?

Another worry is that the experiments do not describe the corruption model; how sensitive are the algorithms to the strength of the corruptions, even in the oblivious setting?

I would also advise the authors to choose a different name, as the title is excatly shared with [4] except with an "in" replacing a "for."

post-discussion: I have increased my score to 5 as a result of my greater appreciation for the results.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider the problem of best arm identification in contaminated stochastic bandits. More precisely, in this framework, the reward probability distribution of each arm may be arbitrarily corrupted with probability $\varepsilon$. The authors focus on the fixed budget setting and propose two different algorithms with theoretical guarantees. Both algorithms use an $\alpha$-trimmed mean estimator to tackle the corruption problem.  The first algorithm (see Algorithm 1) is a gap-based algorithm that relies on the overlap between the confidence intervals of the best empirical arms and the remaining arms in its sampling, stopping, and decision rules. The second algorithm is an elimination-based algorithm, that eliminates arms as soon as they are deemed suboptimal. The authors complement their theoretical findings with experimental results.
main_review: 
The problem is interesting and the authors have successfully adapted existing algorithmic ideas in the bandit literature such as successive elimination and gap-based ideas with confidence intervals. It seems that the main challenge is to handle the corrupted samples when the algorithms build their estimates. The authors propose the $\alpha$-trimmed estimator with a theoretical guarantee. However, I am not fully convinced why this is better or worse than the median estimator used by Altschuler et al. in [4] (the authors cite this paper). The authors argue that using the median estimator might no be a good idea if the distributions are heavy-tailed or not unimodal, but after all in the considered setting the distributions are Gaussian. Besides, in the presented experiments the performance of algorithm 2 and that of Altshuler et al. [4] that uses the median estimator performs similarly. Perhaps the author should consider an experiment with synthetic data where the median estimator truly fails. Could the authors elaborate further on the matter?

The authors provide a lower bound (see Theorem 4) which is very much appreciated. However, it is a bit disappointing that the provided lower bound is essentially the same as the one provided for the classical bandit setting by Garivier et al [26], and does not provide any quantitative insight on how difficult is the contaminated setting in comparison with the classical setting in terms of sample complexity. After all, the obtained guarantees do depend on the contamination level $\varepsilon$, and would hope to obtain a lower bound that depends on $\varepsilon$ as well.


The authors provide theoretical guarantees on the sample complexity for both algorithms. However, the expressed guarantee for algorithm 1 (gap-based algorithm) is in the expected number of samples and is asymptotic in $\delta$ (see Theorem 4.3), while the expressed guarantee for algorithm 2 (elimination based algorithm) is in high probability and is non-asymptotic in $\delta$. The fact that these two guarantees are different blurs the comparison between the two algorithms. Could the authors explain why they cannot obtain similar types of guarantees? are there any challenges in obtaining similar guarantees? the experiments also indicate that algorithm 1 is superior compared to algorithm 2 (see Figure 1, 2, and 3), although some experiments indicate the opposite (see Figure 4).

In algorithm 1, the authors use the thresholds $\beta_a(t,\delta) = \sigma\sqrt{ 2/N_a(t)\log(\log(t/\delta))}$ which is not theoretically proven. Could this be the reason why algorithm 1 outperforms the other algorithms? If this is the case, then maybe the comparison is unfair. Have the authors checked the performance of algorithm 1 with the theoretically proven threshold? For more refined concentration bounds, perhaps the author should look at the paper titled "Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals" by Kaufmann and Koolen. Furthermore, it makes more sense to compare in the experiments the performance of optimal algorithms for best arm identification without corruption rather than with random arm selection.

limitations_and_societal_impact: I believe the authors have addressed these points adequately.  Perhaps there could be potentially negative impacts of the bandit framework in recommender systems. I invite the authors to look at the so-called bubble effect.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work studies the BAI problem with the fixed-confidence setting in the contaminated stochastic bandits, where the rewards can be corrupted with probability $\varepsilon$. It proposes two algorithms and derives upper bounds on their sample complexity. It also derives a lower bound to show the tightness of the bounds. Moreover, it shows numerical results in the end.

main_review: Generally speaking, this work is well-organized and it is interesting in the sense the mean-based BAI problem with fixed-confidence setting has not been explored for the contaminated bandits before. 

Besides, it shows that the theoretical and numerical performance of the two proposed algorithms. However, the analytical methods seem to be quite standard. It would be better if the author(s) can point out the challenge to derive the bounds. 

Lastly, it would be better if the notations can be introduced before they are presented. 


=========

Thanks for the detailed response from the author(s). I have read them and want to increase the rating from 6 to 7. 
limitations_and_societal_impact: The papers is generally well written. However, it would be better if the notations can be introduced before they are presented. I feel hard to find the definitions. The major suggestions are about the following:

1. Algorithm 1:    $\mathcal{U}_t$, $\hat{a}_t$, $\beta_a(t,\delta)$ are defined a bit far away from the algorithm.
2. Where is the the definition of $U_a$?
review_title: null

Meta-review: Overall, reviewers are mostly positive about this paper (especially after author response). The reviewers agree that the paper studies a new and relevant problem, and the concentration bound result is interesting. According to reviewers' comments and discussions, it would be nicer if authors can improve the presentation to highlight the challenges and improvement over prior work.
Decision: Accept (Poster)