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

Authors: Fan Yao, Yuwei Cheng, Ermin Wei, Haifeng Xu
Primary area: learning on time series and dynamical systems
Keywords: Multi-agent learning, reward poisoning attack, Nash equilibrium, monotone game, convergence, robustness

Abstract:
We investigate the robustness of multi-agent learning in strongly monotone games with bandit feedback. While previous research has developed learning algorithms that achieve last-iterate convergence to the unique Nash equilibrium (NE) at a polynomial rate, we demonstrate that all such algorithms are vulnerable to adversaries capable of poisoning even a single agent's utility observations. Specifically, we propose an attacking strategy such that for any given time horizon $T$, the adversary can mislead any multi-agent learning algorithm to converge to a point other than the unique NE with a corruption budget that grows sublinearly in $T$. To further understand the inherent robustness of these algorithms, we characterize the fundamental trade-off between convergence speed and the maximum tolerable total utility corruptions for two example algorithms, including the state-of-the-art one. Our theoretical and empirical results reveal an intrinsic efficiency-robustness trade-off: the faster an algorithm converges, the more vulnerable it becomes to utility poisoning attacks. To the best of our knowledge, this is the first work to identify and characterize such a trade-off in the context of multi-agent learning.

Decision: accept (poster)
Reviewer scores: 8, 8, 6, 6

Reviews and discussion:
<thread>
creation date:
1729263023412

thread_type:
official_review

<thread_object>
creator: reviewer_oyqk

<content>
summary:
This paper considers the poisoning attacks in multi-agent learning, targeting a single agent. The authors first propose the attack strategy which steers the game from the NE with sublinear attack cost. They then explore the robustness of learning algorithms, analyzing how the convergence rate can affect the algorithms' robustness. Finally, the experiments verify the theories by showing the derivative and the cost under different parameters.

strengths:
This paper considers an interesting topic: Attacking a single agent in multi-agent learning. The two main contributions are both noteworthy:

* The first main result indicates that to shift the global equilibrium, an attacker only needs to target one agent with sublinear cost. This practical finding provides valuable insights into the potential risks of multi-agent learning. 

* Second, the trade-off between efficiency and robustness is very interesting. I believe this will provide some heuristic for the design of robust algorithms.

Moreover, this paper is well-written.

weaknesses:
I have several concerns about this paper:

1. The assumptions underlying the proposed attack are quite strong. (1) As the author admits,the adversary is assumed to have complete knowledge of the victim agent's utility function. This assumption, while useful for theoretical analysis, may not hold in practical scenarios, potentially limiting the contribution. (2) The agent is assumed to be unaware of the attacker's presence. If the agents do know, will the attack still work?

2. There’s no knowledge regarding the difficulty of the problem. In other words, can the authors show any lower bound on the cost, which will further indicate the efficiency of the attack? It is worth noting that in a similar topic which is also mentioned by this paper, $[1]$ has already closed such a gap. Furthermore, Figure 2 illustrates the significance of this concern, as in the last sub-figure, the cost increases at an almost linear rate. What’s more, this $\alpha$ is determined by the dynamic itself, therefore it cannot be well controlled. Thus, the cumulative cost is quite large to some degree. After all, both $\log(\log(T))$ and $T^{1-\alpha}$ are sublinear, but their outcomes are totally different.

3. The authors may have partially overstated their work. The problem they considered is a specific attack problem in monotone games, however, the title and introduction demonstrate greater ambition (in general games). Whether the results can be generalized remains unknown.

[1] Zuo, S. (2024, April). Near Optimal Adversarial Attacks on Stochastic Bandits and Defenses with Smoothed Responses. In International Conference on Artificial Intelligence and Statistics (pp. 2098-2106). PMLR.

questions:
Please try to solve the problems in weaknesses. Besides, there are some extra questions:

* The trade-off between robustness and efficiency is very intriguing. I suggest authors further highlight this part in the next version.
* In Line 169-170, is the parameter $L$ known to the adversary? How can the adversary select the target agent “smartly”?
* In Line 295-301, the authors want to show that more information will lead to the ability to control the attack direction. However, without more knowledge (which means more assumptions), this is not addressed. Similarly, in Line 319-322, the same issue arises for the derivative distance.
* In Proposition 1, what will happen if the target agents are a subset of all agents? I.e., for example, if the attacker can manipulate the utilities of two agents, is there any related result?
* Minor typo: There is a missing "." in Line 390.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730274869719

thread_type:
official_review

<thread_object>
creator: reviewer_3kaq

<content>
summary:
This paper investigates the vulnerability of multi-agent learning (MAL) systems in strongly monotone games with bandit feedback. Specifically, the authors propose an attack strategy called Single-agent Utility Shifting Attack (SUSA), which can steer the learning dynamics away from the Nash equilibrium with a sublinear (w.r.t. T) budget. The authors also provide theoretical and empirical results to validate their points.

strengths:
1. The paper introduces a novel type of poisoning attack that focuses on a single agent in multi-agent systems, a context underexplored in prior work. The proposed poisoning strategy can mislead any MAL dynamics in strongly monotone games away from the original NE, with a sublinear corruption budget.  

2. The authors show a trade-off between convergence speed and the robustness to attacks.

3. The authors provide a thorough theoretical analysis to validate theoretical results.

weaknesses:
In the attack model, the authors assume full knowledge of the victim agent’s utility function, which may not always be practical in real-world applications. Moreover, since the agent is unaware of their utilities and the adversary has such knowledge which further allows to compute more information such as gradient, misleading the system not to converge the original NE looks not surprising due to the information asymmetry. It could be more interesting to restrict the adversary. For example, the adversary only observes the noisy rewards.

questions:
Can the authors discuss the attack strategy if the adversary only observes noisy rewards, e.g.,  sub-gaussian rewards?

Is there any lower bound on the budget that misleads the convergence?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730654664893

thread_type:
official_review

<thread_object>
creator: reviewer_vqqa

<content>
summary:
This paper designs the attack policy for multi-agent learning in monotone games. It shows that attacking a single agent is enough to diverge the convergence away from NE. The paper also studies the robustness of the MAL algorithm, presenting several interesting open problems and numerical simulations.

strengths:
1. This paper's writing is clear and easy to follow. The figures (especially Figure 1) and remarks help readers understand the paper. 
2. The contributions of the attack policy to a single agent and proving a sublinear attack is theoretically enough (Theorem 1) are novel in the literature. 
3. The discussion of the robustness and efficiency trade-off is very insightful and opens the door for more interesting future works.

weaknesses:
1. As the authors mentioned that the trade-off had been studied in a single agent, it would be helpful to discuss whether or not the three raised open problems are also present in the single-agent setting. If so, can we extend the single-agent results? If not, why?

questions:
Minor comments:

1. Line 147, “will useful” → “will be useful”.
2. Line 242 is a “strong” attack, [Lykouris et al., 2018] is a “medium” attack before observing the action. For strong attack, the related literature has: 
    1. Jun, Kwang-Sung, et al. "Adversarial attacks on stochastic bandits." *Advances in neural information processing systems* 31 (2018).
    2. Liu, Fang, and Ness Shroff. "Data poisoning attacks on stochastic bandits." *International Conference on Machine Learning*. PMLR, 2019
</content>
</thread_object>

</thread>
<thread>
creation date:
1730906122155

thread_type:
official_review

<thread_object>
creator: reviewer_mptu

<content>
summary:
This paper studies the robustness of multi-agent learning (MAL) algorithms in strongly monotone games with bandit feedback. The authors propose the Single-agent Utility Shifting Attack (SUSA) method to shift the Nash Equilibrium of monotone games by corrupting a single agent's utility feedback, using a sublinear corruption budget relative to the time horizon. Their analysis uncovers a trade-off between efficiency and robustness, showing that faster-converging MAL algorithms are more vulnerable to such attacks. They also validate their theoretical findings via numerical experiments.

strengths:
1) The paper highlights a significant and underexplored vulnerability in multi-agent learning (MAL), specifically through single-agent utility poisoning attacks. It may stimulate further research into designing MAL algorithms that are robust to adversarial attacks.

2) The authors provide a rigorous theoretical analysis of the Single-agent Utility Shifting Attack (SUSA), clearly outlining the conditions under which SUSA can effectively alter the Nash Equilibrium (NE). The exploration of the efficiency-robustness trade-off is valuable, highlighting the increased vulnerability of faster-converging algorithms.

3) The authors conduct extensive empirical simulations, showcasing the practical impact and effectiveness of their proposed method

weaknesses:
1) The current attack objective is focused on shifting the Nash Equilibrium (NE) with specific distance guarantees. While the paper briefly discusses steering the NE deviation in a desired direction (lines 295-300), it remains unclear if it is feasible to mislead agents toward specific, predefined strategies.
2) The study is primarily focused on monotone games, illustrated through Cournot competition and Tullock contests. It would be valuable to examine whether these insights hold in other game-theoretic contexts. For instance, in non-monotone games with multiple NEs, it would be interesting to explore alternative attack objectives, such as guiding agents toward an NE with low utility outcomes.
3) The paper evaluates the effectiveness of attacks based on NE shift and cumulative budget. Expanding the evaluation to include additional robustness metrics, such as stability and utility outcomes, would provide a more comprehensive understanding of the impact of attacks on MAL.

questions:
1) Given that the attack model assumes full knowledge of the victim agent’s utility function, do the authors believe that SUSA could still be effective in a limited-information setting? Are there alternative attack strategies that might be feasible with only partial information?

2) The attack model relies on "strong" corruption, where the attacker observes the current round action. It would be valuable to investigate whether the results extend to scenarios where the attacker lacks this observational ability, as well as whether it becomes easier to design robust algorithms against such "weaker" attackers.

3) To what extent might the findings on NE shifting and efficiency-robustness trade-offs apply to non-monotone games or games with multiple NEs? Could the authors envision scenarios where the attack objective is to guide agents toward a low-utility NE?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731903472354

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Common Response-1

comment:
We appreciate the reviewers' overall positive evaluations about our work, especially the acknowledgement of the significance of the problem we study and the new insight from our results. We are happy to integrate the reviewers’ suggestions for improving the current version. 

In the following, we first respond to the common questions raised by reviewers, and then answer each reviewer’s questions separately. 

1. **Additional results about attack guarantees beyond just shifting NE** 

Some reviewers expressed interest in additional characterizations of the outcome of our attack beyond simply shifting the NE, such as its impact on social welfare or the utilities of other agents. **We have thoroughly addressed this problem** in our revised draft and included new theoretical results in Section 4.3 (theoretical guarantees with proofs provided in Appendix B.3) and additional experiments to support our new results in Appendix F (in the right bottom panel of Figure 6, 7), with updates marked in blue text. 
The new draft with section 4.3 exceeds the page limit. However, should this work be accepted, we plan to address this by merging Sections 4.1 and 4.3 into a single subsection and combining Theorem 1 and Theorem 2. These adjustments will ensure the final camera-ready version complies within the page limit.

In summary, we prove in Theorem 2 and Corollary 1 that for almost any function $W$ defined w.r.t. agents’ joint strategies, the adversary can implement a SUSA that strictly decreases the value of this $W$ at the corrupted NE compared to its value at the original NE. This result is particularly compelling as $W$ can represent a wide range of metrics. For instance, $W$ could be a reasonable social welfare metric, such as the sum of all agents’ utilities, the sum of a targeted subset of agents’ utilities, or even a metric unrelated to any specific agent (e.g., an environmental or systemic metric). Surprisingly, the adversary can achieve this attack goal by targeting just a single agent while incurring an imperceptible total cost. This demonstrates a more significant implication than merely shifting the equilibrium, highlighting the broader vulnerabilities of such systems.

2. **Full knowledge of the victim agent’s utility** 

Reviewers raised a common concern that the information required by the adversary to implement SUSA appears too strong. We argue that this assumption is not as stringent as it may first appear, for the following reasons:

* First, our attack success only requires the adversary to know the utility function of any single agent, not every agent's. In practice, it is plausible for an adversary to target an agent that it knows the best or one that can be easily infiltrated or probed (e.g., an insider). 
* To implement SUSA, the corruption $c_t$ does not need to be calculated with perfect precision. We can show that even if $c_t$​ is computed with zero-mean sub-Gaussian noise, the same success and budget guarantees still hold. This relaxed requirement broadens the applicability of the attack, as it allows the adversary to probe the victim agent’s utility over time within a tolerable margin of error. We will include this discussion in the revision.
* Finally, in some application scenarios (e.g., e-commerce platforms), the “adversary” may not be an external entity but rather an incentive-*misaligned* platform designer. For instance, an online content platform might prioritize revenue at the expense of content providers' overall welfare. In these scenarios, the adversary inherently has full knowledge of all agents’ utility functions since these payoffs are designed and assigned by the adversary itself. Hence the adversary 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).

Moreover, as this is the first work to explore the vulnerability of MAL systems, our primary objective is to reveal the potential risks to MAL algorithms. The development of more nuanced attack strategies under various partial information structures is an interesting and important open problem, which we intend to explore in future work. Nonetheless, our work reveals the feasibility of attacks under partial knowledge, uncovering the vulnerability of MAL.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper studies how easy it would be to disrupt learning dynamics in strongly-monotone games under bandit feedback. 

Overall, the reviewers agreed that this paper is a significant contribution to the field, providing theoretical and practical insights into the vulnerabilities of MAL systems. In the words of Reviewer oyqK, “The two main contributions are noteworthy [..] This practical finding provides valuable insights into the potential risks of multi-agent learning.”

Reviewer mptu highlighted the value of the work in exposing vulnerabilities in MAL: “The paper highlights a significant and underexplored vulnerability in multi-agent learning [..] showing that faster-converging algorithms are more vulnerable to such attacks.” This insight was echoed by Reviewer oyqK: “to shift the global equilibrium, an attacker only needs to target one agent with sublinear cost,” a practical finding with implications for understanding MAL system resilience.

All the reviewers agreed that the paper deserves presentation at ICLR.