Summary
This paper studies adversarial attacks in online multi-agent RL, focusing on reward and action poisoning attacks. It provides a set of characterization results for three different attack modalities: white-box, gray-box and black-box attacks. The authors first discuss the limitation of action-only or reward-only poisoning attack, showing that there are instances of the problem setting where these are not efficient and successful. However, for white-box versions of these attacks, the authors provide sufficient conditions that enable feasibility. For all three attack modalities, they demonstrate that the combination of action and reward poisoning attacks can always force targeted behavior, and provide upper bounds on the expected cost and loss of proposed attack strategies.
Strengths
- The paper is clearly written and is enjoyable to read. While there are typos, these should be easy to fix. More importantly, the technical content is clearly conveyed, and the paper provides intuitions bending the main technical results.
- The paper complements prior work on poisoning attacks in MARL, which considered offline RL setting. Hence, the characterization results are novel and contribute to the line of work on poisoning attacks in RL. That said, the results appear to be similar to the ones presented in [Rangi et al., 2022]. It would be useful to have additional discussions on how these differ in terms of their technical content, proof techniques, etc..
- The paper considers several variations of poisoning attacks under different attack modalities, while showcasing the existence of efficient and successful reward+action poisoning attack strategies. Such a systematic study is likely to be valuable to researchers working on poisoning attacks in RL.
- The paper provides a good overview of the related work on adversarial attacks in RL. Specifically for MARL, the most important references seem to be covered. However, there are a couple of recent references that could be included in the list (see below). I encourage the authors to do so.
> - Wang et al;, BACKDOORL: Backdoor Attack against Competitive Reinforcement Learning
> - Mohammadi et al., Implicit Poisoning Attacks in Two-Agent Reinforcement Learning: Adversarial Policies for Training-Time Attacks
> - Liu et al., Controllable Attack and Improved Adversarial Training in Multi-Agent Reinforcement Learning
> - Chen et al., Byzantine-Robust Online and Offline Distributed Reinforcement Learning
Weaknesses
- In terms of results, the paper does not discus the optimality of the upper bounds in their formal results. For example, it could be interesting to discuss the tightness of the bounds in Theorem 9, and how they compare to those of the underlying learning algorithms (V-learning).
- Following up on my previous remark, additional discussions regarding some of the assumptions in the problems setting would be useful to have. For example, the paper assumes that the target policy receives strictly positive rewards (page 4). Additionally, it would be good to formally specify the learners' model, and reference it in Theorem 1 and 2.
- This work is primarily theoretical, but the paper could benefit from having additional experiments (in addition to the numerical simulations reported in the appendix), e.g., those that would demonstrate the efficacy of the black-box approach. Namely, bound in (8) and (9) are inversely proportional to $R_{min}$, so it would be interesting to investigate how this dependency affects the practicality of the proposed approach.
- Practical considerations are not discussed, e.g., it would be useful to have some discussion on how to enable scalability and go beyond the tabular setting.
Questions
It would be great if the authors could additionally answer the following clarification questions:
- Could you explain how these results compare to the ones from [Rangi et al., 2022] in terms of, e.g., proof techniques?
- For Eq. (1), Theorem 1 and 2, what is the assumed model of the MARL agents? I.e., what is needed for these statements to hold?
- Can you explain why the analysis does not allow sparse rewards for the target policy (the assumption on page 4)? What happens if the rewards are equal to $0$?
- In the section that talks about reward-only white-box attacks, why doesn't it suffice to set the reward to the lowest value whenever the target action is not taken?
- The dependency on $m$ seems to be smaller in gray-box than in white-box attacks. Could you comment on the practical benefits of white-box attacks?
- Could you comment the optimality of the upper bounds (attack loss/cost)? More specifically, could you comment on the tightness of the bounds in Theorem 9, e.g., in terms of horizon $H$?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
This paper provides a theoretical analysis of poisoning attacks in multi-agent RL, so I don't believe this work will have any negative societal impact. The limitations of this work could have been discussed in greater detail, e.g., in the concluding remarks. For example, instead of summarize the results of the paper, the concluding remarks could focus more on the tightness of the bounds in Theorem 9, or the practical aspects of this work, e.g., how to go beyond the tabular setting.