Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study a threat to adversarial multi-armed bandit, in which an attacker perturbs the loss or reward signal to force the defender to select a suboptimal target action in every but (T −o(T)) number of rounds, while incurring only o(T) cumulative attack cost. This result try to motivate the problem through online recommendation. The proposed attack algorithms require knowledge of only the regret rate, and is agnostic to the bandit algorithm used by the victim player. A theoretical lower bound on the cumulative attack cost tis also presented.
strength_and_weaknesses: This is primarily a theory paper. The experiments are in simulation. Overall results look fine; for a theory paper the theory is not too much of an advance but ok.

The attacks are straightforward enough, essentially making all other arms unattractive. But I am left wondering what would happen (theoretically) if a robust algorithm was being used, meaning the defender is aware of an attacker of the type in this paper - would the result of the attack be different? My view is possibly not, because the attacker has no much power here as to arbitrarily modify the reward (with a liberal cost allowance that can grow with T), which in my view also makes the attacker's task simple.
Is the concept of regret w.r.t. to the original rewards meaningful here? (meaning the defender observes changed rewards but collects the true reward in practice) If meaningful, what happens to this original regret value?


It would have been easier to see the graphs if the quantities were plotted averaged over T. It would have been nice if the dependence on the number of arms was also included in the formulas of the results. (which can be extracted from the regret guarantee).

Typos:
Example 1 - the word "contract" should be contradict
clarity,_quality,_novelty_and_reproducibility: Writing and clarity is clear, I have no issues.
Some math proof sketched in the main paper would be better, as I am not sure if the math is hard or easy. 
The idea appear novel to me.

summary_of_the_review: I think the work is novel, but not a big advance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper develops some attack strategies for adversarial bandits. They design two attack policies that need a sublinear cost of corrupting the original loss of arms and resulting in a linear regret for the bandit algorithm. On the lower bound side, the authors show their attack policy is optimal in the sense that there is no better attack policy with less cost that can degrade the regret of the bandit algorithms. Last, experimental results show that the proposed attack policy can degrade the regret of the existing bandit algorithms. 
strength_and_weaknesses: **Strengths:**
- The paper is well-written and easy to follow. 
- The topic of bandits with corruption is a timely topic.
- The motivation for adversarial bandits with corruption is less clear, but it is well justified in this paper. 
- The proposed attacks are easy to understand and intuitive. 

**Weaknesses:**
- This paper has a foundational issue with the way that the cost associated with the attacker is calculated. Consider the easy attack setting. The attacker will set the loss of all arms but the target arm to 1. This means that the attacker has to pay at most $(K-1)\times T$ for corrupting the loss of all other arms. However, the authors simply ignore this huge cost and calculate the cost only for the selected arm. This is the case for the general attack case also. If this observation is correct (I urge the authors to clarify this in rebuttal), the contribution of this paper is not interesting at all since the attacker is paying a huge cost of changing the entire game in their favor, but the authors just claim this is still good (sublinear cost) since only they count the cost when a corrupted arm is selected. 

- Beyond the above major issue, I think the contribution of this paper is interesting but not surprising in terms of the attack design. The attack idea is very straightforward, i.e., set the loss of all arms except the target arm to 1. Nothing intellectually interesting here. 


clarity,_quality,_novelty_and_reproducibility: The clarity of the presentation is good. The quality of writing and organization is great, but in terms of technical contribution, the paper is not tackling a challenging research question. The paper is novel in the sense that it is the first that designs attacks for adversarial bandits. 
summary_of_the_review: Overall, I found this paper borderline. My major issue is that the attack policies are very straightforward to design, which might be ok since this is the first paper introducing attacks for adversarial bandits. However, I would like to see how convincing is the response from the authors regarding the cost associated with the attackers.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the problem of how to manipulate an adversarial bandit algorithm. In the problem an attacker can perturb the loss function and wants to steer the bandit algorithm to select a target action of the attacker's choice. The authors presented methods to pertub the loss function to achieve this goal in two different settings, and showed that the methods incur only sublinear attack costs. Experiments were also conducted to evaluate the performance of the proposed methods.
strength_and_weaknesses: Strengths:

The paper is very well-written. The problem setting and assumptions used are all clearly described. The idea of manipulating an adversarial bandit is novel and very interesting. The theoretical results are well-presented. They are concise and easy to follow but tell a complete story at the same time. 

Weaknesses: 

The proposed methods require knowledge of the bandit algorithm's regrete rate in some cases.
clarity,_quality,_novelty_and_reproducibility: The paper is clear. The idea of manipulating an adversarial bandit is novel and very interesting. The theoretical results are well-presented and solid. 
summary_of_the_review: Overall, a well-executed paper, consise and easy to follow. The key idea is novel and has the potential of inspiring follow-up work. The results are solid and coherent.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies adversarial bandits, a setting in which an attacker can alter the reward received by a MAB to alter their behavior, a topic that has recently received attention. The main contribution of the paper is that a sublinear (o(T)) attack "budget" suffices to yield suboptimal target actions in T-o(T) rounds. Interestingly, this can be accomplished even though the attacker is assumed to have quite limited knowledge; in particular, the attacker only knows the regret rate but not the specific MAB algorithm used. A lower bound is that matches the strength of the attack is also provided.

The authors are encouraged to include the results on robust MABs to the paper: both the experiments, and the a discussion as to why the attack is still valid even in the presence of a robust MAB algorithm, would improve the overall contribution. The same is true about the dependence on arm cardinality, and the meaning of original rewards.
justification_for_why_not_higher_score: Reviewers overall liked the paper and the contribution, though they also find some of the results not that surprising.
justification_for_why_not_lower_score: Reviewers overall liked the paper and the contribution, though they also find some of the results not that surprising.
Decision: Accept: notable-top-25%