Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considered expert problem and multi-armed bandits in stochastic environment with adversarial corruption. In this setting, an adversary modifies stochastic feedback up to total corruption level $C$. The authors analyzed Hedge algorithm with decreasing learning rate and algorithms with second-order regret bounds, and showed that the regret has a $\sqrt{C}$ dependency to the corruption level. Matching lower bound in the expert problem and near-tight lower bound up to logarithmic factor in the multi-armed bandit problem, suggesting the analyzed algorithms achieve optimal robustness.

main_review: Strength:

The paper studied an important problem: stochastic online decision making with adversarial corruption. Many recent works focused on this line of research. The key contribution is the refined regret analysis of Hedge algorithms for expert problem and multi-armed bandit problem under corruption. It is interesting to see that in both settings, the regret has a $\sqrt{C}$ dependency to the corruption level. Another contribution is the lower bound of the two problems, showing the analysis is (near) optimal. 

One thing to note is that the regret definition in this paper is based on losses after corruption. The authors explained the difference from defining regret based on losses before corruption and analyzed the regret difference in Remark 1.

Concern:

I do not have significant concerns about the paper. One comment is that the authors may want to discuss the technical novelty in Theorem 3 comparing with Amir et al. 2020, since both papers analyzed Hedge algorithm with $\eta_t = O(\sqrt{\log N / t}) learning rate. The authors already provided a comparison on the regret bounds in Remark 1; it would be better to provide more explanation on how the stronger result is achieved.

Quality and clarity:

The writing is clear. The related works are thoroughly discussed. The theoretical analysis looks sound to me although I did not check every step of proof.

References:
I. Amir, I. Attias, T. Koren, Y. Mansour, and R. Livni. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33, 2020.

limitations_and_societal_impact: The authors discussed the limitations and potential social impact of the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the online decision problems with corruptions and provide upper bounds on the regret of the Hedge algorithm and lower bounds for any algorithm.
main_review: This paper presents quite a rich amount of contents, but there seems to be lack of clear discussions. My major concerns are as follows:
1. In the abstract, it states that this work will study the problem of prediction with expert advice and the multi-armed bandit problem. However, somehow I failed to find the results of the problem of prediction with expert advice.
1. Definition 1 introduces the self-bounding constraint. Though this is implied by Zimmert and Seldin [2021], I think that some discussion on the motivation and the interpretation of this definition would be appreciated.
1. This work reviews the existing literature on corruptions, best-of-both-work algorithms and so on. However, I failed to find what is the focus of this work.
1. There are a bunch of theoretical results in this work, but somehow I cannot easily tell what is the specific problem (stochastic/adversarial? with or without corruption?) the result in each section is for. I think more discussions would be appreciated.
1. Furthermore, some experiments to show the regret of the algorithm (maybe the Hedge?) grows as shown in the upper/lower bounds would make the results more convincing.
1. Among the many results, is there any analytic challenge?

=====================================

Thanks you for your response.

Most of my concerns are solved. However, as claimed in the feedback, the results hold for any instances satisfy Definition 1. This suggests that some existing results should be comparable to your work. May you include some comparisons and discussions among the theoretical results in the paper? Numerical comparison is also appreciable but I understand that can be time-consuming.

Anyway, I would like to increase my rating to 6 for the time being.


limitations_and_societal_impact: More discussions on the results may make the big picture and the focus of this paper clearer.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper investigates on the regret bounds for the expert advice problem and the multi-armed bandit in a quite general intermediate regime so called adversarial regime with a self-bounding constraint provided by Zimmert and Seldin (2021) (henceforth ZS21). For the expert advice problem in this general regime, the authors provide two regret bounds and a matching lower bound for an instance of Decreasing Hedge algorithm and algorithms with the second-order bounds. For the multi-armed bandit problem they achieve a lower bound in the mentioned intermediate regime that matches with the state-of-the-art result by ZS21 up to a logarithmic factor.       
main_review: Originality:
- Theorem 3 and Theorem 4 are new bounds for already existing algorithms for the expert advice problem. 
The analysis of these two theorems consist of two key steps:  1) Providing upper bound for the regret in terms of probabilities played by the player. 2) Combining this upper bound with the self-bounding constraint. 
Lemma 1 in the paper provides the first step for the proof of Theorem 3  that I believe this is almost same bound as Lemma 6 of Amir et al., (2020). Also Theorem 2 in the paper (Theorem 5 of Cesa-Bianchi et al., (2007)) provides the first step for the proof of Theorem 4. The second step, which I think is the most important step, follows the same idea and steps provided by ZS21 for the analysis of Tsallis-INF algorithm for MAB problem that combines self-bounding constraint to their provided upper bound. Hence, I think the novelty is questionable here since the main contribution of these Theorems is applying ZS21 idea to combine the existing upper bounds and self-bounding constraint.   
 - Theorem 5 and Theorem 6 provide lower bounds for the regret in expert advice and MAB problem. In spite of the fact that the example construction provided for lower bound is similar to the prior works but the inference steps for the intermediate regimes seems interesting.

Quality:
- There are many minor issues and small bugs in the proofs but after reading the details of the proofs, finally found out they are technically sound.  I noticed small bugs in the analysis steps of the regret upper bounds, Mostly in Theorem 3, but they won't change the order of the regret bounds however they still affect the constants factors in the regret bounds. Generally I suggest that the authors revise the equations at the end of page 6 and page 7 and also construction of example for lower bound in page 8.

Clarity: 
- The writing is generally clear. However reading the proofs takes too much energy from a reader since in many equations the intermediate steps are missing. 
- There are some small typos and grammatical issues throughout the paper.

Significance:
- As it is mentioned in the paper there is a work by Amir et al., (2020) that studies the expert advice problem with adversary corruptions and give linear regret on the _original version of losses_ w.r.t. total amount of corruption. However, there is no regret bound on the _corrupted version of losses_ and this paper gives a the tight one for this. So the result on expert advice problem seems significant to me but I would still like to see some motivating examples and practical real world examples of such problems.
- The multi-armed bandit part of paper has no important significance since the provided lower bound have quite naive construction and doesn't match completely with the state-of-the-art result by ZS21. 
 
limitations_and_societal_impact: Limitations:
- As I mentioned earlier, the analysis of the paper follows the ZS21 approach. The main drawback of ZS21 in analyzing Tsallis-INF algorithm was that their analysis technique relies on the uniqueness zero entry (i*) of the self-bounding constraint. One of the important open problem followed by ZS21 is to remove this assumption. This paper also implicitly have the same assumption in their analysis so the authors must clearly state this issue in the paper. 

- Two notions of regret have been expressed in the paper: 1- Regret on original version of losses, 2- Regret on corrupted version of losses. It is clear that the regret bounds with these two notions are not comparable but in Table 1 the regret bound by Amir et al., (2020) is compared to the results of Theorems 3 and 4. At least the notions of regret used for evaluation must be represented clearly in the table.

- In MAB problem the authors compare their provided lower bound to ZS21 result, however, recently ZS21 result was improved by a paper titled: "Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits" (Masoudian and Seldin, 2021).  So it is better that the authors compare their lower bound with the improved result.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper study the expert problem and multi-armed bandit problem in the adversarial regive with self-bounding constraints. Compared to prior work, this paper provides tight lower-bound for both problems and refined upper-bound for the expert setting, achieving matching upper and lower bounds in both settings up to constant and logT factors respectively.
main_review: This paper nearly closes the theoretical gap between the upper and lower bounds in both problems mentioned above, effectively solved these two problems to completion. The presentation is clear and the analysis is intuitive. It is obviously above the acceptance threshold of the conference.
limitations_and_societal_impact: NA
review_title: null

Meta-review: The reviewers unanimously support acceptance of the paper.
Decision: Accept (Poster)