Single-agent Poisoning Attacks Suffice to Ruin Multi-Agent Learning

We thank the reviewer for appreciating the representation and insights of our work. Below we address the raised concerns and questions in order.

W1: Assumption about attacker’s knowledge

For the first question, please refer to the second bullet point of our common response. For the second question, our Theorem 3 in Section 5 provides an answer. Specifically, if agents can estimate an upper bound $T^{\rho}$ of the total budget, they can adjust their learning rate accordingly to achieve a certain level of robustness. This insight is visually represented in the green region of Figure 1. To see this, observe that within the green region, drawing a horizontal line for any fixed $\rho$ results in a corresponding range of $\alpha$ on the $x$-axis. This range of $\alpha$ identifies the learning rates that ensure resilience against NSA.

W2: Lower bound on corruption budget

We kindly remind the reviewer that we do have comprehensive algorithm-dependent lower bounds in Section 5 (specifically, Corollary 2 and Proposition 4), similar to Theorem 3,4,5 in [Zuo, 2024]. We chose not to explicitly emphasize these aspects, as they are inherently embedded within our robustness-efficiency tradeoff analysis, which we believe offers deeper and more exciting insights. For detailed explanations, please refer to the last bullet points of our common response. That said, we sincerely appreciate the reviewer for bringing this relevant work to our attention, and we will add a discussion of [Zuo, 2024] in the revised version.

Regarding the concern that our upper bound might be too large, we note that our polynomial-order lower bounds are reasonably tight. For example, in the case of MD-SCB, the lower bound is $\Omega(T^{1-\alpha})$, while the upper bound is $\Omega(T^{1-\frac{2\alpha}{3}})$. Therefore, such a seemingly large required budget is not a result of loose analysis but rather reflects the intrinsic difficulty of the attacking goal.

This larger budget requirement in multi-agent settings starkly contrasts with [Zuo, 2024]’s single-agent learning setting, where the required budget has a matched bound of $O(\log T)$. We find this distinction particularly intriguing, as it may suggest a fundamental gap between single-agent and multi-agent learning environments, an area we believe is worthy of further exploration.

W3: Generalization to other game-theoretic context Please refer to the third bullet point of our common response.

Q1/Q5: We will address your comments in revision.

Q2: Choosing victim agent

In many critical security applications, the adversary likely has limited options because being able to compromise some agent is likely the most difficult step in practice (which is why we believe our result is particularly valuable by showing it actually suffices to poison a single agent, if done properly). In such situations, the adversary will likely target the agent that it knows the best or a certain insider who has already been infiltrated and compromised.

In other scenarios, where the adversary has greater freedom to choose the victim, it can strategically select agents to achieve specific goals. For instance, the adversary may choose the agent with the greatest potential to induce a desirable equilibrium deviation direction, as demonstrated in Proposition 1. Alternatively, it may target the agent whose compromise results in the most significant welfare reduction, as highlighted in Theorem 2 of the new draft (Section 4.3).

Q3: More knowledge requirement for manipulating attack direction

Your understanding is correct. First, as we clarified in the second bullet point of our common response, in many applications, the adversary does have access to additional knowledge, enabling more detailed control over the attack outcome.

Second, we acknowledge that in cases where the adversary lacks additional knowledge about the environment, achieving refined control over the outcome is not guaranteed. However, this does not render the discussion meaningless. From a system or defender’s perspective, our discussion highlights potential threats to any MAL system by illustrating what an adversary could possibly achieve. We will add further discussion on this point in the revised version.

Q4: Target at a subset of agents

If the attacker manipulates $k$ agents, theoretically it can induce an NE shifting direction that lies in a $kd$-dimensional hyperplane, a sub-space of the $nd$-dimensional joint strategy space. This is why the ability to manipulate all agents’ utilities enables the attacker to achieve arbitrary NE deviation directions. However, characterizing this $kd$-dimensional hyperplane is highly nuanced, as it depends on a linear transformation induced by the inverse of the game’s Hessian (an $nd$-by-$nd$ matrix). Given the complexity and limited relevance of this characterization to our main contributions, we decided not to include a detailed discussion in the paper.

We appreciate the reviewer's understanding and helpful thoughts and we will definitely integrate these comments into our next version.

Regarding the trade-off and lower bound, we would like to clarify that we believe that these aspects have been emphasized in our section 5. Specifically:

Figure 1: This figure summarizes and contrasts the upper and lower bound results, highlighting the gaps as open questions for further exploration.

Lower Bound: In Section 5, we highlight the corresponding results in red text for better visibility. For instance, in Equation (17), $\rho_+(\alpha)$ denotes the algorithm-independent lower bound, while $\rho(MD-SCB(\alpha))$ corresponds to an algorithm-dependent lower bound. These elements and their interpretations are clearly presented in the following discussion below Corollary 2.

That said, we would greatly appreciate it if the reviewer could provide more details on what considerations they feel are currently missing and suggest specific in-depth results or analyses regarding the trade-off that could further strengthen our paper. Thanks!

We are happy to learn that the reviewer likes our results and insights. To address your concern regarding our assumption of the attacker's knowledge, please refer to the second bullet point of our common response.

We address the reviewer’s two other questions below.

Q1: Noisy Rewards

Our attack can afford noisy $c_t$, i.e., the amount of utility corruption can only be estimated up to a Gausian noise (see the second Bullet point of our common response). However, we do not have a theoretical guarantee regarding what an adversary can achieve if it does not observe any agent’s utility but only has access to their noisy reward observations. We do appreciate the reviewer for bringing up this interesting direction that is worth future investigation. Additionally, we note that if the adversary possesses partial knowledge of the victim agent’s utility function $u_k$​, even noisy reward observations could enable it to refine its estimation of $u_k$ by probing the MAL system. Specifically, the adversary could implement trial attacks to gather information and subsequently solve an inverse problem to execute a successful attack. For a more detailed discussion, please refer to Bullet Point 2 in our common response.

Q2: Lower bound on corruption budget

We kindly point out that we did provide a set of lower bound results in Section 5 (specifically, Corollary 2 and Proposition 4). We chose not to explicitly emphasize these aspects, as they are inherently embedded within our robustness-efficiency tradeoff analysis, which we believe offers deeper and more exciting insights. Please refer to the last bullet point of our common response for more detailed discussion.

We sincerely appreciate the reviewer's very positive feedback, and we are happy to address any further questions if the reviewer might have. If the reviewer thinks that we have fully addressed the concerns, we respectfully request the reviewer to reevaluate the rating of our paper (as our understanding is that a score of 6 means the paper is only “marginally” above the bar).

In addition, we would like to further emphasize our contribution regarding the attacking scheme, SUSA. We respectfully disagree with the reviewer’s assessment that our result for SUSA is unsurprising in the full-information setting (actually we should call it “partial-information setting” since it only assumes that the attacker knows his attacked agent’s utility instead of the entire game) for the following two reasons.

Firstly, we believe our assumption is “moderate” in the adversarial attack or “equilibrium steering” literature [1]. For example, [2] considers a game redesign problem by assuming the designer knows the entire game (equivalent to knowing every agents’ utility). [3,4] assume the attacker can completely control one of the learners in multi-agent learning.

Secondly, while it is indeed expected that agents can be misled to converge to a new NE, our contribution lies in demonstrating that this can be accomplished with merely a sublinear budget on attacking previously already convergent algorithm, which is stronger than attacking merely no regret learning algorithms studied in other relevant literatures [5]. Therefore, we believe that the design of such an attacking strategy to achieve this outcome is non-trivial.

However, we agree that it will be an intriguing open direction to further relax the attacker’s knowledge and design optimal attack strategies for the black-box setting (the attacker has no information of the game and has to learn it from past trajectories). We mention it in the Limitation section and leave it as our future work. Please refer to the updated draft.

[1] A survey on the analysis and control of evolutionary matrix games

[2] Game Redesign in No-regret Game Playing

[3] Adversarial policies: Attacking deep reinforcement learning

[4] Adversarial policy learning in two-player competitive games.

[5] Steering No-Regret Learners to a Desired Equilibrium

We appreciate the reviewer’s positive feedback on our presentation and contributions. Regarding the minor comments, we find them very helpful and will surely address the typo and include relevant literature on strong attacks in our next revision. Below, we respond to the question raised under Weaknesses.

Trade-offs in single agent setting

The problem of closing the gap between budget lower and upper bounds has been addressed in some single-agent online learning settings, such as Stochastic Linear Bandits [Bogunovic et al., 2021]. However, to the best of our knowledge, previous work on reward poisoning against bandits does not study the efficiency-robustness trade-offs, as they mainly focus on the vulnerability of the most efficient learning algorithms with the best regret guarantees. [Cheng et al., 2024] discussed efficiency-robustness trade-offs in the context of reward poisoning in dueling bandits, as mentioned in Section 5 of our paper. Nonetheless, these results cannot be directly applied to multi-agent learning scenarios, where each agent’s utility observations are influenced by the actions of all agents. This interdependence makes the effects of adversarially "hacking" the utility of a single agent—whose observations may impact others—both complex and unpredictable. The fundamental barriers to adapting algorithmic designs from single-agent to multi-agent settings have also been discussed in prior works [Wu et al., 2021, Wang et al., 2022], implying the challenges inherent in studying the robustness of MAL algorithms, which is the focus of our work.

[1] Bogunovic, Ilija, et al. "Stochastic linear bandits robust to adversarial attacks." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

[2] Cheng, Yuwei, et al. "Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Dueling." arXiv preprint arXiv:2405.11204 (2024).

[3] Wu, Jibang, Haifeng Xu, and Fan Yao. "Multi-Agent Learning for Iterative Dominance Elimination: Formal Barriers and New Algorithms." COLT. 2022.

[4] Wang, Yuanhao, et al. "Learning Rationalizable Equilibria in Multiplayer Games." arXiv preprint arXiv:2210.11402 (2022).

We thank the reviewer for appreciating the value of our work. We respond to the reviewer’s criticisms mentioned in weaknesses and answer the raised questions in the following.

W1/W3: Mislead agents towards specific strategies / bad outcomes, and implications in stability and utility outcome

Please refer to the first bullet point of our common response and our updated draft.

W2: Extend to other game-theoretic context

Please refer to the third bullet point of our common response.

Q1: Attack under limited information

Please refer to the second bullet point of our common response.

Q2: Relax the strong attack assumption

First, we would like to clarify that our focus is on strong attack settings because, in many application scenarios, adversaries can indeed observe all players’ actions. For example, the adversary can be an incentive-misaligned platform designer, e.g., an online content platform might prioritize revenue at the expense of content providers' overall welfare. In this case, the adversary inherently has full knowledge of all agents' actions, and thus can easily apply SUSA to one agent in order to steer the entire MAL system (this actually happens in reality, known as platform subsidy to few selected agents). While we have justified our focus on the current setting, we do find the reviewer’s suggestion to investigate weak attacks very insightful. We agree that studying the implementation of and defense mechanisms against weak attacks are both practical and valuable, and we plan to explore this direction in future work.

Q3: Result for non-monotone games and towards a low-utility NE

For the extension to non-monotone games, please refer to the last bullet point of our common response. For the attack towards a low-utility NE, please refer to the first bullet point of our common response and our updated draft.

(Continued from Common Response-1)

We also provide a proposal for relaxing the full-knowledge utility assumption for future studies. Here we outline a method for learning the victim agent's utility function using a preliminary probing phase. Suppose the victim’s utility $u_k(\boldsymbol{x};\theta)$ is parameterized by $\theta$, where the adversary knows the function form of $u_k$ but not the parameter $\theta$. During the probing phase, the adversary can design and apply a sequence of corruptions $c_t$​, fixing each $c_t$​ for a sufficient duration to observe the induced corrupted equilibrium. By doing so, the adversary can estimate the victim’s best-response function at various points, gradually refining its knowledge of the utility parameter $\theta$. To ensure the success of the attack while maintaining a sublinear corruption budget, the adversary must carefully balance the length of the probing phase. A longer probing phase improves the accuracy of the utility estimation but incurs higher overall costs, as probing involves linear budget growth. While a detailed discussion of this process is beyond the scope of this work, we intend to address it in future research.

3. Extensions to more general game classes

Some reviewers pointed out that our results are established within the context of monotone games and inquired whether they can be extended to other settings. The answer is Yes; however, before discussing the generalizability of our results, it is important to emphasize that our attack is not targeted at a specific class of games $\mathcal{G}$, but rather at a class of MAL algorithms $\mathcal{A}$ running on an environment defined by a class of games $\mathcal{G}$.

In fact, the fundamental requirements for $\mathcal{G}$ and $\mathcal{A}$ in Theorem 1 to establish the same attack success guarantees are quite broad:

• (1) condition for $\mathcal{G}$: Any game such that: 1. each agent has a compact, continuous action set, and a well-defined best-response mapping; 2. it has a unique PNE, and if one player’s utility $u_k(x_k,x_{-k})$ changes to $u_k(x_k+\delta,x_{-k})$, the new game also has a unique PNE.
• (2) condition for $\mathcal{A}$: MAL algorithms that convergence to the PNE for any $G\in\mathcal{G}$.

In our current draft, we chose to present our results in the context of monotone games and refrained from stating Theorem 1 in this more abstract and general form for a practical reason: to the best of our knowledge, the only well-established class of MAL algorithms with rigorous guarantees of convergence to a unique PNE currently exists is within the monotone game context. That said, should future work develop classes of new MAL algorithms for other types of games that satisfy the above requirements (1) and (2), our SUSA attack would remain a valid threat to such systems. If this more general description clarifies the broader applicability of our results, we are happy to revise the draft to incorporate this general setting.

4. Lower bounds on corruption budget

We appreciate the reviewers’ inquiry regarding lower bound results. In fact, our paper includes a comprehensive discussion of algorithm-dependent lower bounds, as explained below. They are implicit within our robustness-efficiency tradeoff analysis in Section 5, which we are more excited about since we believe robustness-efficiency tradeoff conveys deeper and more novel insights. Meanwhile, we also acknowledge that: 1. We do not have algorithm-independent lower bounds, 2. There are still gaps between our lower and upper bounds. As discussed in Section 5, addressing these gaps presents novel and intriguing challenges due to the inherent complexity of multi-agent learning in game-theoretic environments. We have outlined these challenges explicitly as Open Questions 1, 2, and 3 (OP 1,2,3) in Section 5, and we plan to explore them in future work.

• Algorithm-dependent budget lower bounds for achieving NE Shifting Attack (NSA) We provide budget lower bounds for achieving NSA against MD-SCB and MAMD algorithms.

  • a. MD-SCB. Corollary 2 presents the lower bound for MD-SCB. The LHS inequality $\rho(MD-SCB(\alpha))\geq 1-\alpha$ in Eq. (14) demonstrates that a total budget of $\Omega(T^{1-\alpha})$ is necessary to achieve NSA for MD-SCB with a convergence rate $(\alpha, 2)$. This result complements the upper bound in the right-side inequality of Eq. (14) — a restatement of Theorem 1— indicating that SUSA with a budget of $O(T^{1-\frac{2\alpha}{3}})$ suffices to achieve NSA for any MAL algorithm (see the green solid line in Figure 1).

  • b. MAMD. A similar lower bound of $\Omega(T^{2/3})$ for MAMD is derived from Proposition 4 (Appendix C.4). This result is further discussed in the final paragraph of Appendix D.1. While this bound aligns with our theoretical insights from Theorem 3 and Corollary 2, it is relegated to the appendix due to its relatively limited standalone value in the main narrative.