Adversarial Attacks on Cooperative Multi-agent Bandits

Q1. First, the paper lacks discussion about the novelty and major technical challenges for various results.

A1. Regarding the homogeneous setting, please refer to A1 to Reviewer bPAF. For the heterogeneous setting, our work tackles several novel challenges in heterogeneous cooperative learning. These include identifying meaningful attack objectives and developing the AAS and TAS algorithms specifically tailored to heterogeneous environments. Furthermore, the theoretical analysis of our attack strategies is particularly challenging due to a unique aspect of the multi-agent heterogeneous setting: target agents may not consistently have sufficient attack opportunities. Resolving this issue requires a careful treatment, as detailed in Lines 383–404.

Q2. Second, many results and proofs are inaccurate. 1. In the statement of Theorem 1, the term "our attack strategy" is ambiguous. 2. “(f) is submodular and the greedy algorithm in Algorithm 1 gives a ((1 - 1/e))-approximation solution”. This is inaccurate – the paper needs to additional prove the function is monotone and non-negative. 3. In Theorem 3 (also Theorem 4), the term $\Delta(k, k+1)$ is not defined rigorously. Also, Equation (3) does not include $T_0$. The definition of $g(k)$ is missing.

A2.

1. Due to the space limit and since we treat the homogeneous setting as the warm-up result, we defer the detailed algorithm and analysis to Appendix B.1.

2. Thank you for pointing this out. $f$ is indeed both monotone and non-negative, as a larger input set of agents will always result in more conflict-free agents. We will revise the proof to explicitly demonstrate these properties and add citations in the updated version.

3. The definition of $\Delta(k, k') = \mu(k) - \mu(k')$, which represents the difference in expected rewards between any two arms $k$ and $k'$, is provided in Line 205. $T_0$ is a constant defined as the feasible solution to Eq. (3) with respect to $t$, where the right-hand side is a problem-specific coefficient independent of $t$. As for $g(k)$, it denotes the target agent assigned to attack arm $k$, as determined in Algorithm 2 (Line 7).

Q3. Line 111 to 112, the paper claims that “Our work is the first to study how an attacker may manipulate multi-agent cooperative learning”. Regarding the problem setting, what is the difference between this paper’s attack setting and previous works such as ICML’20, Mobihoc’21 and AAMAS’22?

A3. Our intention was to claim that we are the first to explore the vulnerabilities of cooperative multi-agent bandits specifically from the attacker's perspective, extending the single-agent attack model studied in the adversarial attack literature (e.g., Jun et al., 2018; Liu & Shroff, 2019; Zuo, 2024). We acknowledge that related works, such as ICML’20 and Mobihoc’21, examine settings involving honest and malicious (or selfish) agents in cooperative bandit frameworks. However, these studies do not approach the problem from an attacker's perspective aiming to mislead the entire learning system. While AAMAS’22 investigates how attackers can exploit "collisions" to influence Multi-Player Multi-Armed Bandits (MMAB), our work is distinct in that it follows the Cooperative Multi-Agent Multi-Armed Bandit (CMA2B) framework (Vial et al., 2021; Yang et al., 2021, 2022; Wang et al., 2022, 2023a,b), which assumes no collisions and emphasizes cooperative interactions.

Q4. In line 6 of Algorithm 1, what is $\omega(k)$?

A4. $\omega(k)$ is the sorted index corresponding to the $k$-th largest set of agents.

Q5. On Page 5, line 268, the stated goal is to “leverage sublinear attack costs to misguide the maximum number of agents, aiming to increase the overall count of agents enduring linear regrets.” Why using Algorithm 3 will lead to “attacking the maximum number of agents” is neither justified nor adequately explained in the subsequent paragraphs.

A5. Sorry for the confusion. The stated goal is achieved since the AAS algorithm identifies an approximately maximum set of agents that can be attacked without conflicts. By leveraging this set, Algorithm 3 focuses on attacking the largest possible group of agents while maintaining a sublinear attack cost.

Q6. The second claimed contribution appears to be inaccurate.

A6. We appreciate your suggestion regarding the second claimed contribution, and we will revise it to emphasize our identification of an appropriate and meaningful attack objective specifically tailored to the heterogeneous setting. However, we also want to highlight that our findings and the accompanying proofs, demonstrating the necessity of linear costs to achieve either the target arm attack or linear regrets for all agents, are non-trivial and represent novel contributions to the study of adversarial attacks on CMA2B.

Q1. My main concern is the applicability or relevance of the model. What exactly is the setting where one would encounter the scenario proposed and thus this work would be insightful? Could you provide some motivating examples?

A1. Thank you for your thoughtful question. To address the applicability and relevance of our model, we provide a motivating example in the context of online advertisements on e-commerce platforms (e.g., Amazon, eBay). In this scenario, recommendation systems on different platforms can be viewed as learning agents, and the arms represent products recommended to users. These learning systems, often belonging to the same advertising company, share user feedback with each other to collaboratively improve their understanding of user preferences. This naturally creates a cooperative learning problem.

In this context, the two attack objectives studied in this paper can be interpreted as follows.

• Target Arm Attack Objective (e.g., in the homogeneous setting): One product (or its associated seller) might aim to manipulate the recommender systems to increase its exposure to users. This could be achieved by targeting a platform (agent) and injecting fake user feedback (commonly known as click fraud). Our theoretical findings suggest that it is feasible for an attacker to influence the entire system with a small attack cost by leveraging such strategies. This highlights the potential risks of subtle manipulation in cooperative learning environments.

• Linear Regret Objective (e.g., in the heterogeneous setting): In this scenario, the attacker could be a competing advertising company aiming to undermine the reputation and performance of the recommendation system. The competitor may have already collected user preference data through its own systems and could potentially infer the original company’s recommendation algorithm using simulated or fake users. Based on our findings, the competitor can strategically target a limited number of platforms to mislead the original company’s learning system, again at a low cost. Notably, our algorithms remain effective even when the set of attackable agents is restricted (footnote 1 on page 3), so the competitor does not need to access all platforms.

These attack objectives are not limited to online advertisements but extend to other domains where competition exists either between arms (e.g., products, services) or between learning systems (e.g., service providers). For instance, in cooperative navigation systems where autonomous vehicles share data to optimize routes, a malicious actor could manipulate shared information to disrupt traffic flow or bias route selection toward specific paths. Similarly, in sensor networks used for cooperative source localization or environmental monitoring, an attacker could interfere with a subset of sensors to mislead the system and obscure the true source of the signal or data.

In summary, the scenarios explored in our paper are relevant to a variety of cooperative learning systems. The insights gained from studying adversarial attacks in this framework contribute to a deeper understanding of vulnerabilities and the development of robust systems. We will expand on these examples and motivations in the revised version to better contextualize our contributions.

Q2. In the paper, it is assumed that the attacker knows the algo used by the learner.

A2. Please see A5 to Reviewer jeLP.

We sincerely thank the reviewer for highlighting the minor issues, which we will thoroughly address in the updated version.

Q1. This work is not written clearly and assumes the reader possesses extensive technical knowledge about adversarial attacks in bandits. For example, the term attack value is not explained in the main text, and the idea behind equation (2) is also unclear. The parameters in Thm 1 are undefined as well: What are $\alpha, \Delta_0$?

A1. Thank you for pointing this out. The term "attack value" refers to the amount added by the attacker to the reward generated from the original distribution. Regarding the parameters in Theorem 1.

• $\alpha$ is a parameter of the UCB algorithm, which controls the width of the confidence interval. Specifically, in the CO-UCB algorithm, the confidence interval for arm $k$ at round $t$ is defined by a radius of $\sqrt{\frac{\alpha \log(t)}{\hat{n}_t(k)}}$, where $\hat{n}_t(k)$ is the number of times arm $k$ has been pulled.

• $\Delta_0$ is a parameter in our attack strategy. It is used to compute the attack value, ensuring that the post-attack empirical mean reward of a targeted arm is manipulated to be less than the empirical mean reward of the desired arm. Intuitively, $\Delta_0$ controls the margin by which the attacker shifts the rewards to influence the agent’s decision-making process.

We will clarify these terms and the underlying ideas behind Equation (2) more explicitly in the revised version to improve accessibility for a broader audience.

Q2. Table 1 is misleading. For the first and second lines, it is unclear whether knowledge about the time horizon $T$ is needed. The authors can cite [1] rather than [2] if it is not. More importantly, the third line assumes oracle knowledge of the attacker about arm rankings (Thm 3), which is a strong assumption. When using the version that does not use this assumption, the attack cost becomes much larger at $O(K\log(T)/\Delta_{\min}^2)$ (Thm 4).

A2. Thank you for your careful review. We will revise Table 1 to explicitly clarify whether knowledge of the time horizon $T$ is required in each case. For the heterogeneous setting, we acknowledge that the attack cost of the LTA algorithm is $O(K\log(T)/\Delta_{\min}^2)$, as shown in Theorem 4. This cost arises due to the rank learning phase. We believe it could potentially be optimized with a more refined design for learning under attack. While this remains an open direction, we will update the table to clearly specify the assumptions made in the heterogeneous setting and include the corresponding results of the LTA algorithm to provide a balanced presentation.

Q3. The problem addressed in this paper could be motivated better.

A3. Thank you for highlighting the concern regarding privacy preservation in multi-agent bandit systems. While privacy is indeed a critical consideration in certain applications involving user data, there are many scenarios where privacy constraints are less stringent or irrelevant. For instance, recommendation systems with multiple servers operated by the same organization often involve internal information sharing, where privacy is not a concern. Similarly, in robotic systems, cooperative tasks such as source search [A, B] represent practical scenarios where agents collaborate without privacy constraints. Moreover, the CMA2B framework has been extensively studied in contexts that do not involve privacy-sensitive data, as demonstrated by prior work (e.g., Vial et al., 2021; Yang et al., 2021, 2022; Wang et al., 2022, 2023a,b). We will revise the introduction to include these examples and references, providing a broader and more practical motivation for the problem.

[A] Shuai Li, Ruofan Kong, and Yi Guo. Cooperative distributed source seeking by multiple robots: Algorithms and experiments. IEEE/ASME Transactions on mechatronics, 19(6):1810–1820, 2014.

[B] Long Jin, Shuai Li, Lin Xiao, Rongbo Lu, and Bolin Liao. Cooperative motion generation in a distributed network of redundant robot manipulators with noises. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 48(10):1715–1724, 2017.

Q4. While the attack design for heterogeneous systems is novel, it should be mentioned that the attack itself used in this paper technically resembles techniques from previous works [1,2] (for instance, equation (2)).

A4. Thank you for pointing this out. As mentioned in Lines 202 and 223, we acknowledge that the attack value design draws on techniques from [1, 2]. We will explicitly clarify this connection for equation (2) as well. However, the primary focus of this paper is to address the novel challenges posed by cooperative multi-agent learning. We contribute by introducing non-trivial results, including the AAS and TAS algorithms tailored for heterogeneous settings, accompanied by rigorous theoretical analyses.

Q1. Limited novelty of the results in homogeneous settings.

A1. We acknowledge that the analysis of attacking CO-UCB in the homogeneous setting shares similarities with the single-agent UCB analysis in Jun et al. [2018] and Zuo [2024]. However, we would like to highlight the following points: (a) We are the first to formally prove the cost of attacking homogeneous CO-UCB and clearly position this as a warm-up result, as presented in Table 1. Our result demonstrates that it is sufficient to ruin the entire multi-agent system by attacking only one agent in homogeneous settings. This finding provides a baseline for comparison with the heterogeneous setting and highlights the vulnerabilities inherent in cooperative multi-agent systems. (b) We prove that our attack policy remains effective against more sophisticated homogeneous algorithms, such as those with delayed feedback or leader-follower structures. These results, detailed in Appendices B.3 and B.4, address new challenges specific to these scenarios, such as managing asynchronous reward updates and accounting for the distinct roles of leaders and followers. We hope these points clarify the novelty and relevance of our results in the homogeneous setting.

Q2. What happens when the communication model is constrained through addition structures?

A2. We agree that exploring communication models with graph structures, such as those discussed in Landgren et al. [2016], is an important and promising direction for future research. In such scenarios, identifying the most impactful target agents for attack becomes more complex, as the influence of each agent on the cooperative learning system would depend on the graph topology and connectivity. While our current work does not address these more complex communication graphs, our analysis in the heterogeneous settings provides insights into identifying target agents based on their relative importance and influence within the cooperative framework.

Additionally, we would like to emphasize that the communication model impacts both the effectiveness of cooperative learning and the vulnerability to attacks. When communication is constrained (e.g., by a graph structure), it is true that attacks may become more challenging. However, the benefits of cooperation would also diminish due to limited information sharing. This highlights an intriguing trade-off between cooperation efficiency and system robustness. The primary goal of this paper is to uncover vulnerabilities in fully collaborative systems, and we hope our findings can motivate further research into addressing these trade-offs in more constrained communication settings.

Q3. Refinement of assumptions for attacks against general algorithms.

A3. We apologize for any confusion caused by Assumption 1 and sincerely appreciate the reviewer’s suggestion to reference Xu et al. [2021]. We agree that refining Assumption 1 to explicitly consider a class of mean-based CMA2B algorithms, such as those defined in Xu et al. [2021], would provide better clarity and a more precise scope for our analysis. Regarding Assumption 2, we acknowledge the concern about the changing sample distributions under attack. The post-attack distribution can be viewed as a shifted version of the pre-attack distribution with a gap of $\Delta(k, K) + 4\beta(1)$. In this context, we expect general bandit algorithms would still identify $K$ as the best arm and pull suboptimal arms limited times. We will explicitly clarify these assumptions in the updated version.

Q4. It's difficult to understand the $T_0$ term in the heterogeneous results, and how it's always a constant.

A4. $T_0$ represents a threshold that ensures our selected target agents consistently pull the arms intended for attack before other agents, thereby providing sufficient opportunities for successful attacks. Without this threshold, other agents might collect too many unattacked samples, which would increase the attack costs of the target agents.

$T_0$ is a constant since it is determined as the feasible solution of Eq. (3) with respect to $t$, where the right-hand side is a problem-dependent coefficient that does not vary with $t$. For a more detailed explanation, please refer to Lines 383–391.

Q5. Experiments are limited with no error bars. Can we experimentally verify if these results would work for cooperative versions of simple MAB algorithms like $\epsilon$-greedy or Thompson sampling?

A5. Thank you for your valuable suggestions regarding the experiments. We will include error bars in the updated version and extend our experiments to validate the effectiveness of our attack strategies on other simple cooperative MAB algorithms.

Q1. While the paper is presented well, the assumptions are highly restrictive, and the proposed attack algorithms apply only to specific CMA2B algorithms (i.e., CO-UCB or UCB-TCOM), which limits the general applicability of this work.

A1. Thank you for highlighting these detailed potential extensions. We acknowledge that many of these points are promising directions for future work. However, before addressing each point individually, we would like to emphasize that the primary objective of this paper is to expose the vulnerabilities inherent in collaborative learning by analyzing representative CMA2B algorithms. Specifically, we have conducted a rigorous study of both homogeneous and heterogeneous cooperative settings, yielding non-trivial theoretical results . We believe our work uncovers core vulnerabilities in multi-agent cooperative bandits, laying a foundation that can inspire future research in this field.

Q2. No Collision: The authors overlook collisions in the multi-agent MAB (MMAB) problem, lacking literature support for this choice.

A2. We agree that addressing the collision problem in MMAB is important, particularly in applications such as cognitive networks. However, it is also crucial to study multi-agent cooperative learning settings without collisions, as highlighted in the CMA2B literature (e.g., Vial et al., 2021; Yang et al., 2021, 2022; Wang et al., 2022, 2023a,b). In this paper, we focus on vulnerabilities introduced by cooperation under these non-collision settings, which align with the assumptions in much of the CMA2B literature. While we acknowledge that incorporating collisions could introduce additional challenges for attack design, we believe the insights presented in our work provide a valuable foundation that can inspire advancements in addressing vulnerabilities in collision-based settings.

Q3. Pre-Attack Reward Observability: The paper assumes that the attacker can observe pre-attack rewards for all agents, which seems unrealistic in practical applications. It remains unclear how an attacker would access this information.

A3. Building on adversarial attacks in single-agent bandits, we adopt the same threat model commonly used in the single-agent literature (e.g., Jun et al., 2018; Liu & Shroff, 2019; Zuo, 2024). This model assumes that the attacker has access to all pre-attack reward information. However, it is important to highlight that our attack algorithms rely on reward information from the target agents (including shared samples from other agents). Notably, our algorithms can still function effectively even when the set of attackable agents is restricted (footnote 1 on page 3).

Q4. Prior Knowledge of Local Arm Sets: In the heterogeneous setting, the assumption that the attacker knows each agent’s local arm set also seems impractical.

A4. Since the CMA2B model enables agents to communicate with one another, local arm set information can be easily shared across the system, incurring only a constant communication cost. This assumption aligns with the practices in the heterogeneous CMA2B literature (Baek & Farias, 2021; Yang et al., 2022; Wang et al., 2023b).

Q5. Algorithm Awareness: The assumption that the attacker knows each agent’s exact algorithm is the strongest and most limiting.

A5. In this paper, we primarily focus on representative CMA2B algorithms, assuming that the attacker has knowledge of the agents' algorithms, which enables more efficient attacks. However, as discussed in Section 4.2.4, we also extend our findings to general homogeneous CMA2B algorithms without requiring knowledge of the exact algorithms and provide a cost analysis in Appendix B.5. For heterogeneous settings, AAS and TAS remain effective tools for identifying agents vulnerable to attacks and selecting target agents, even without precise algorithm awareness. Developing more general attack strategies for heterogeneous CMA2B algorithms remains an open and promising direction for future research.