Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learning
Authors: Guanlin Liu
Lifeng Lai
Venue: NeurIPS 2023 poster (2023)
Keywords: adversarial attacks; multi agent reinforcement learning;
TL;DR: We study the adversarial attacks on online multi-agent reinforcement learning.

Abstract: Due to the broad range of applications of multi-agent reinforcement learning (MARL), understanding the effects of adversarial attacks against MARL model is essential for the safe applications of this model. Motivated by this, we investigate the impact of adversarial attacks on MARL. In the considered setup, there is an exogenous attacker who is able to modify the rewards before the agents receive them or manipulate the actions before the environment receives them. The attacker aims to guide each agent into a target policy or maximize the cumulative rewards under some specific reward function chosen by the attacker, while minimizing the amount of the manipulation on feedback and action. We first show the limitations of the action poisoning only attacks and the reward poisoning only attacks. We then introduce a mixed attack strategy with both the action poisoning and reward poisoning. We show that the mixed attack strategy can efficiently attack MARL agents even if the attacker has no prior information about the underlying environment and the agents’ algorithms.

Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learning
Guanlin Liu Lifeng Lai
Department of Electrical and Computer Engineering University of California, Davis One Shields Avenue, Davis, CA 95616 {glnliu, Iflai (lai)))ucdavisseet
Abstract
Due to the broad range of applications of multi-agent reinforcement learning (MARL), understanding the effects of adversarial attacks against MARL model is essential for the safe applications of this model. Motivated by this, investigate the impact of adversarial attacks on MARL. In the considered setup, there is an exogenous attacker who is able modify the rewards before the agents receive them or manipulate the actions before the environment receives them. The attacker aims to guide each agent into target policy or maximize the cumulative rewards under some specific reward function chosen by the attacker, while minimizing the amount of manipulation on feedback and action. We first show the limitations of the action poisoning only attacks and the reward poisoning only attacks. We then introduce a mixed attack strategy with both the action poisoning and the reward poisoning. We show that the mixed attack strategy can efficiently attack MARL agents even the attacker has no prior information about the underlying environment and the agents' algorithms.
Introduction
Recently reinforcement learning (RL), including single agent RL and multi-agent RL (MARL). has received significant research interests, partly due to its many applications a variety of scenarios such the autonomous driving, traffic signal control, cooperative robotics, economic molicy-making, and video games [Silver et al. 2016 Brown and Sandholm 2019 Vinyals et al. 2019. Berner et al. al.) 2016 Oroojlooy Jadid and Hajinezhad 2019 Baker al. 2020 Zhang et al. 2021a]. MARL, at each state, each agent takes its own action, and these actions jointly determine the next state of the environment and the reward of each agent. The rewards may vary for different agents. In this paper, we focus on the model of Markov Games (MG) [Shapley] 1953). In this class of problems, researchers typically consider learning objectives such Nash equilibrium (NE), correlated equilibrium (CE) and coarse correlated equilibrium (CCE) etc. A recent line of works provide non -symptttttoiic guarantees for learning NE, CCE or CE under different assumptions Sidford et al. 2020 Zhang et al. 2020a Bai and Jin 2020 Mao and Başar 2022).
2019 Shalev-Shwarte
Xie et al. 2020 Liu et al. 2021 Jin et al. 2021
As RL. models, including single agent RL and MARL, are being increasingly used in safety critical and security related applications, it is critical to developing trustworthy RL systems. As first step
towards this important goal, it is essential to understand the effects of adversarial attacks on RL systems. Motivated by this, there have been many recent works that investigate adversarial attacks on
single agent RL under various settings [Behzadan and Munir 2017 Huang and Zhu 2019 Ma et al.
2019 Zhang al. 2020b Sun et al. 2021 Rakhsha et al. 2020
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

On the other hand, except the ones that will be reviewed below, existing work on adversarial attacks on MARL limited. In this paper, we aim to fill in this gap and systematically investigate the impact of adversarial attacks on online MARL. We consider setting in which there is an attacker sits between the agents and the environment, and can monitor the states, the actions of the agents and the reward signals from the environment. The attacker is able to manipulate the feedback or action of the agents. The objective of the MARL learner is to learn an equilibrium. The attacker's 's goal is to force the agents to learn a target policy or to maximize the cumulative rewards under some specific reward function chosen by the attacker, while minimizing the amount of the manipulation on feedback and action. Our contributions are follows.
1) We propose an adversarial attack model in which the attacker aims to force the agent learn a policy selected by the attacker (will be called target policy in the sequel) or to maximize the cumulative rewards under some specific reward function chosen by the attacker. We use loss and cost functions to evaluate the effectiveness of the adversarial attack on MARL agents. The cost is the cumulative sum of the action manipulations and the reward manipulations. If the attacker aims to force the agents to learn target policy, the loss is the cumulative number of times when the agent does not follow the target policy. Otherwise, the loss is the regret to the policy that maximizes the attacker's 's rewards. It is clearly of interest to minimize both the loss and cost.
2) We study the attack problem in three different settings: the white-box, the gray-box and the black-box settings. In the white-box setting, the attacker has full information of the underlying environment. In the gray-box setting, the attacker has no prior information about the underlying environment and the agents' algorithm, but knows the target policy that maximizes its cumulative rewards. In the black-box setting, the target policy is also unknown for the attacker.
3) We show that the effectiveness of action poisoning only attacks and reward poisoning only attacks limited. Even in the white-box setting, we show that there exist some MGs under which no action poisoning only Markov attack strategy or reward poisoning only Markov attack strategy can be efficient and successful. At the same time, we provide some sufficient conditions under which the action poisoning only attacks or the reward poisoning only attacks can efficiently attack MARL algorithms. Under such conditions, we introduce an efficient action poisoning attack strategy and an efficient reward poisoning attack strategy, and analyze their cost and loss.
4) We introduce mixed attack strategy in the gray-box setting and an approximate mixed attack strategy in the box setting. We show that the mixed attack strategy can force any sub-linear- regret MARL agents choose actions according the target policy specified by the attacker with sub-linear cost and sub-linear loss. We further investigate the impact of the approximate mixed attack strategy attack on V-Jearning [Jin et al. 2021]. simple, efficient, decentralized algorithm for MARL.
1.1 Related works
Attacks on Single Agent RL: Adversarial attacks on single agent RL have been studied in various
settings [Behzadan and Munir, 2017, HHang and Zhu 2019 Ma et al., 2019, Zhang et al. 2020b
Sun et al. 2021 Rakhsha et al. 2020 2021]. For example, Behzadan and Munir 2017 Zhang
ett al. 2020b Rangi et al. [002 study online reward poisoning attacks in which the attacker could
manipulate the reward signal before the agent receives it. (Liu and Lail [021] studies online action poisoning attacks in which the attacker could manipulate the action signal before the environment
receives it [Rangi et al. 2022) studies the limitations of reward only manipulation or action only
manipulation in single-agent RL.
Attacks on MARL: [Ma ct al. 2022 considers a game redesign problem where the designer knows the full information of the game and can redesign the reward functions. The proposed redesign methods can incentivize players to take a specific target action profile frequently with a small cumulative design cost. [Gleave et al. 2020 Guo et al. 202T study the poisoning attack multi- agent reinforcement learners, assuming that the attacker controls one of the learners. [Wu et al. 2022 studies the reward poisoning attack on offline multi agget reinforcement learners.
Defense Against Attacks on RL: There is also recent work on defending against adversarial attacks
on RL [Banihashem et al. 2021 Zhang et al.) 2021b Lykouris et al. 2021 Chen et al. 2021 Wei
et al. 2022 Wu et al. [202]] IJ. These work focus on the single-agent RI. setting where an adversary can corrupt the reward and state transition.
2

---

2 Problem setup
2.1 Definitions
To increase the readability of the paper, we first introduce some standard definitions related to MARL that will be used throughout of the paper. These definitions mostly follow those defined in (Jin et al. 2021]. We denote a tabular episodic MG with m agents by a tuple MG(S, {A H, P. [R. J where is the state space with [S] = S, A, is the action space for the 7th agent with [A..] = A. H E - is the number of steps in each episode. We let := (a1,-.. , (m)) denote the joint action of all the m agents and A := A x x Am denote the joint action space. P = {Pa ( he(m] is a collection of transition matrices. PA : x A x S -> [0. 1] the probability transition function that maps state-action-stee state pair to probability, R.,A : S x - [0, 1] represents the reward function for the 1thh agent in the step h. In this paper, the probability transition functions and the reward functions can be different at different steps. We note that this MG model incorporates both cooperation and competition because the reward functions of different agents can be arbitrary.
The agents interact with the environment in a sequence of episodes. The total number of episodes is K. In each episode k E [K] of MG, the initial states 81 is generated randomly by distribution ..).). Initial states may be different between episodes. At each step h [H] of an episode, each agent observes the state S) and chooses an action 0g simultaneously. After receiving the action, the environment generates random reward r E [0, 1] for each agent i derived from a distribution with mean RiA (Sh, a2),, and transits to the next state 5h+1 drawn from the distribution Pa(-1s), (ss, az). Pa (-Is, a) represents the probability distribution over states if joint action is taken for state s. The agent stops interacting with environment after H steps and starts another episode. At each time step, the agents may observe the actions played by other agents.
Interaction protocol:
Policy and value function: A Markov policy takes actions only based on the current state. The policy W of agent i at step h is expressed as a mappings Tith : S - A, Ti,n (a, (s) represents the probability of agent i taking action a; in state & under policy π, at step h. A deterministic policy is a policy that maps each state a particular action. For notation convenience, for a deterministic policy Tú we use ,., ( to denote the action a; which satisfies (a: = 1. We denote the product policy Tm. We also denote π-; == म ... X Ti-1 X 1i+1 to be the product policy excluding agent i. If every agent follows deterministic policy, the product policy of all the agents is also deterministic. We use V S - IR denote the value function of
of all the agents π :- 1i X
Tm
agent i at step h under policy π and define VIT (5) = E = Te 8, ग Given a policy m
and step h, the hh agent's Q-function O7, S x A- + E of a state-action pair (s, a) is defined as:
Q7, a) = E Σ H
EN'A TUM |8h. 8, an a,
Best response: For any policy T-is there exists a best response of agent i, which is a policy that achieves the highest cumulative reward for itself if all other agents follow policy n- We
define the best response of agent i towards policy T- as μu (T=:), which satisfies j (π_;) ==
arg max, V.Th y,tx**-((s)) for any state and any step h. We denote max,, v,, viTAX=-((s) (s) V (s) for notation simplicity. By its definition, we know that the best response can always be achieved by deterministic policy.
Nash Equilibrium (NE) is defined as product policy where no agent can improve his own cumulative reward by unilaterally changing his strategy.
Nash Equilibrium (NE) [Jin et al., 2021]: A product policy и is a NE for all initial state s, max (V (s) V. (s)) = 0 holds. A product policy ı is an c-approximate Nash Equilibrium if for all initial state s, [m [V t.x
1,1 (s) (s) < holds.
General correlated policy: A general Markov correlated policy π is a set of H mappings ग := (NH : Ω x S - A The first argument of π. is random variable w E Ω sampled from some underlying distributions. For any correlated policy π = {TT {Th heem and any agent i, we can define a marginal policy т-; as set of H maps π. = {TTA-; Ω x S + Jh,,he where x A, x Ait1 .... Am. It easy verify that a deterministic joint policy is a product policy. The best response value of agent i towards policy π as jel (T= which satisfies
A_i Ai
ut (T= = arg max,, v.Txx=-((s) for any state and any step h.
3

---

Coarse Correlated Equilibrium (CCE) et al. 2021]: A correlated policy is an CCE if for all initial state maxaemm] (Vr11"(ss) Vi (s)) holds. A correlated policy is c-approximate CCE if for all initial state s, maxqe m ( (s) (.T(s)) (s)) S holds.
Strategy modification: A strategy modification Φ) for agent is set of mappings Φi == {(S x A)a-1 x x A, + Ai For any policy Tæ. the modified policy (denoted as o, o m;) changes the action Ti. s) under random sample w and state 8 to (i(($1, al...., Sh, as,h) ), Ti, (w, 8)). For any joint policy T,, we define the best strategy modification of agent i as the maximizer of max., V for any initial state s.
Correlated Equilibrium (Cn) et al.
2021]: :: A correlated policy π is an CE if for all initial state (8) = 0. A correlated policy π is an e-approximate CE
8, ma maxø, (Vil (V/(0o0:)00 *(s)
for all initial state 8, max4[[m] max (V 1.1
(0:00) Jor (ss) Vi, (s)) & holds.
In Markov games, it is known that an NE is an CE, and an CE is CCE.
Best-in-hindsight Regret: Let x² denote the product policy deployed by the agents for each episode k. After K episodes, the best-in-hindsight regret of agent i is defined as (eg H) =
K k= - (s)) V,JL (s/)]-
m
2.2 Poisoning attack setting
We are now ready to introduce the considered poisoning attack setting, in which there an attacker sits between the agents and the environment. The attacker monitor the states, the actions of the agents and the reward signals from the environment. Furthermore, the attacker can override actions and observations of agents. In particular, at each episode k and step h, after each agent i chooses an action ai,,. the attacker may change it to another action ai E A,. If the attacker does not override the actions, then att,, a,, When the environment receives x it generates random rewards r with mean RA, (s a for each agent and the next state s/ is drawn from the distribution (- at)). Before each agent receives the reward rf, the attacker may change it to another reward 7 i.h- Agent receives the reward P and the next state sh+1 from the environment. Note that agent i does not know the attacker's manipulations and the presence of the attacker and hence will still view i.6. as the reward and + as the next state generated from state-action pair (s at)).
In this paper, we call an attack action poisoning only attack, if the attacker only overrides the action but not the rewards. We call an attack as reward poisoning only attack if the attacker only overrides the rewards but not the actions. In addition, we call attack as mixed attack if the attack can carry out both action poisoning and reward poisoning attacks simultaneously.
The goal of the MARL learners is to learn an equilibrium. On the other hand, the attacker's goal is to either force the agents to learn a target policy π² of the attacker's 's choice or to force the agents to learn a policy that maximizes the cumulative rewards under specific reward function R S A - (0, 1] chosen by the attacker. We note that this setup is very general. Different choices of It or R A could lead to different objectives. For example, the attacker aims to reduce the benefit of the agent the attacker's reward function Ri., can be set detrimental to the agent i's reward. If the attacker aims to maximize the total rewards of a subset of agents C, the attacker's 's reward function R a can be set to Eiec Righ choose target policy n² arg max Evec V.T (s1) that maximizes the total rewards of agents in C. We assume that the target policy πt is deterministic and Re, (s, # (s)) > O. We measure the performance of the attack over K episodes by the total attack cost and the attack loss. Set 1-) as the indicator function. The attack cost over K episodes is defined as Cost(K, H) = Σ ΣH Em (IGāt, + af h) + 17 rlia)).
Ra,, choose target policy æ² that is
There are two different forms of attack loss based on the different goals of the attacker.
If the attacker's goal is force the agents to learn target policy nt, the attack loss over K episodes is defined as Loss (K, H) Σ
H 1= Em 1 (af,, # T., (+
If the attacker's goal is to force the agents to maximize the cumulative rewards under some specific re- ward function R& chosen by the attacker, the attack loss over K episodes is defined as Loss2(K, H)

---

ΣK (V (+4)(, Here, (s) is the expected cumulative rewards in state based on the attacker's reward function R4 under product policy т and V (s) = max; V., (s). x denote the product policy deployed by the agents for each episode k. x²" is the optimal policy that maximizes the attacker's cumulative rewards. We have Lo, H) S H * LossI(K, H).
Denote the total number of steps as 7 K H. In the proposed poisoning attack problem, we call an attack strategy successful if the attack loss of the strategy scales as o()). Furthermore, we call an attack strategy efficient and successfill if both the attack cost and attack loss scale as (T)).
The attacker aims to minimize both the attack cost and the attack loss, or minimize one of them subject to a constraint the other. However, obtaining optimal solutions to these optimization problems is challenging. As the first step towards understanding the attack problem, we show the limitations of the action poisoning only or the reward poisoning only attacks and then propose simple mixed attack strategy that is efficient and successful.
Depending on the capability of the attacker, we consider three settings: the white-box, the gray-box and the black-box settings. The table below summarizes the differences among these settings.
Table I: Differences of the white/gray/black- box attackers
white-box attacker
gray-box attacker
black-box attacker
MG
Has full information
No information
No information
T!
Can be calculated if R given
Required and given
Not given
R Lossl
Not required if πt given Suitable by specify n²
Not required if æt given Suitable
Required and given Not suitable Suitable
Loss2
Suitable if R2 given
Suitable if Rg given
3 White-box attack strategy and analysis
In this section, to obtain insights to the problem, we consider the white-box model, in which the attacker has full information of the underlying MG (S, (A.) 1. H, P, [R.) Even in the white- box attack model, we show that there exist some environments where the attacker's goal cannot be achieved by reward poisoning only attacks or action poisoning only attacks in Section 3.1 Then, in Section 3.2 and Section 3.3 we provide some sufficient conditions under which the action poisoning attacks alone or the reward poisoning attacks alone can efficiently attack MARL algorithms. Under such conditions, we then introduce an efficient action poisoning attack strategy and an efficient reward poisoning attack strategy.
3.1 The limitations of the action poisoning attacks and the reward poisoning attacks
As discussed in Section 2 the attacker aims to force the agents to either follow the target policy x² or to maximize the cumulative rewards under attacker's 's reward function R2. In the white-box poisoning attack model, these two goals are equivalent as the optimal policy π on the attacker's 's reward function R& can be calculated by the Bellman optimality equations. To maximize the cumulative rewards under attacker's ' reward function R2 is equivalent to force the agents follow the policy 7l = n²"
Existing MARL algorithms (Liu et al. 2021 Jin et al., 2021] can learn an e-approximate (NE, CE, CCE) with (11(2) sample complexities. To force the MARL agents to follow the policy nt, the attacker first needs attack the agents such that the target policy म the unique NE in the observation of the agents. However, this alone is not enough to force the MARL agents to follow the policy ग². Any other distinct policy should not be an e-approximate CCE. The reason is that, if there exists an e-approximate CCE such that T(r' (s){s) existing MARI, algorithms, may learn and then follow π, which will lead the attack loss to be O(T) = ((K K H). Hence, we need to ensure that any e-approximate CCE stays in the neighborhood of the target policy. This requirement equivalent to achieve the following objective: for all s E S, and policy n,
O for any state the agents, using
max Vii ((5) - (s)) 0: iE(m]
if n is a product policy and * न. then max 1l (s) - (.T( > O; iE[m]
(1)
if (T = O for all s', then max (V. (s) V7J (s)) > e,
-
sE(m]
5

---

where V is the expected reward based on the post-attack environments.
We now investigate whether there exist efficient and successful attack strategies that use action poisoning alone or reward poisoning alone. We first show that the power of action poisoning attack alone is limited.
Theorem There exists target policy I² and a MG (S, H, such that no action poisoning Markov attack strategy alone can efficiently and successfully attack MARL agents by achieving the objective in 4
We now focus strategies that use only reward poisoning. If the post-attack mean reward R is unbounded and the attacker can arbitrarily manipulate the rewards, there always exists an efficient and successful poisoning attack strategy. For example, the attacker can change the rewards of non-target actions to - H. However, such attacks can be easily detected, as the boundary of post-attack mean reward is distinct from the boundary of pre-attack mean reward. The following theorem shows that if the post-attack mean reward has the same boundary conditions as the pre-attack mean reward, the power of reward poisoning only attack is limited.
Theorem If we limit the post-attack mean reward to have the same boundary condition as that of the pre-attack mean reward R, ie. R E [0, 1}, there exists a MG (S, (A.) H, P. ) m and a target policy π! such that no reward poisoning Markov attack strategy alone can efficiently and successfully attack MARL agents by achieving the objective in 77)
The proof' of Theorem and Theorem 2 are provided in Appendix (F) The main idea the proofs is follows. In successful poisoning attacks, the attack loss scales (T)) so that the agents will follow the target policy π in at least T o(T) times. To efficiently attack the MARL agents, the attacker should avoid to attack when the agents follow the target policy. Otherwise, the poisoning attack cost proceedd
will grow linearly with T. The proofs of Theorem and Theorem proceed by constructing an MG and a target policy π² where the expected rewards under I is always the worst for some agents if the attacker avoids to attack when the agents follow the target policy.
3.2 White-box action poisoning attacks
Even though Section 3.1 shows that there exists MG and target policy such that the action poisoning only attacks cannot be efficienlly successful, here we show that it can be efficient and successful for class of target policies. The following condition characterizes such class of target policies.
Condition 1: For the underlying environment MG (S, [A: H, P, {Ra )m)) the attacker's target policy лt satisfies that for any state s and any step h, there exists an action a such that V.A (s) (,,,(s a), for any agent i.
Under Condition 1, we can find worse policy π. by
T (s) arg max min aEA rE[m)
(val (s) (r)(),a) s.LVi [m], Val (s) (s,
(2)
Under this condition, we now introduce an effective white-box action attack strategies: d-portion attack. Specifically, at the step and state 8, if all agents pick the target action, i.e., a = . (s). the attacker does not attack, i.c. ă = n (s). If some agents pick non-target action, i.c., + म| (s). the d-portion attack sets à as
/ (s), with probability da (s, a) ā
(3)
ne (+), with probability 1 - (s a)/m,
where di (s. = m/2 + EE 1(a; (s)/2)
Theorem 3 the altacker follows the d-portion attack strategy on the MG agents, the best response of each agent towards the target policy xL, is T/. The target policy n is an (NE, CE, CCEJ from any agent's 's point of view. If every state S is reachable at every step h E [H] under the target policy, n² is the unique (NE, CE, CCEJ.

---

The detailed proof can be found in Appendix G.1 Theorem shows that the target policy πf is the unique (NE, CE. CCE) under the d-portion attack. Thus, if the agents follow an MARL algorithm that is able to learn an 6-approximate (NE, CE, CCE), the agents will learn policy approximate to the target policy. We now discuss the high-level idea why the d-portion attack works. Under Condition 1, Tt is worse than the target policy n! at the step H from every agent's 'sss point of view. Thus, under the d- portion attack, the target action strictly dominates any other action at the step H, and ' is the unique (NE, CE, CCEJ at the step H. From induction on h H, H- 1, 1........... 1, we can further prove that the I is the unique (NE, CE, CCE) at any step h. We define A (5) = Q7 (s. क (s)) Q7, (s, Th (s)) and the minimum gap Amin [M see not an e-approximate CCE with different gap Amin/ /2. We can derive upper bounds of the attack loss and the attack cost when attacking some special MARL algorithms.
A (s). In addition, any other distinct policy
Theorem 4 If the
regret Reg(K,, H) of each agent's algorithm is bounded by sub-linear bound R(T) for any MG in the absence of attack, and minges (1) >
H =+= max [m]] A by (s) holds for any h E [H], then d-portion attack will force the agents to follow the target policy with the attack loss and the attack cost bounded by
E[[Los| (K. H)] < 2m R(T) B[Cosi(K, (,, H)] S 2m (m)R(T))A min-
(4)
3.3 White-box reward poisoning attacks
As stated in Theorem 2 the reward poisoning only attacks may fail, if we limit the post-attack mean reward R to satisfy the same boundary conditions as those of the pre-attack mean reward R, i.e. R E [o, I.. However, similar to the case with action poisoning only attacks, the reward poisoning only attacks can be efficiently successful for a class of target policies. The following condition specifies such class of target policies.
Condition 2: For the underlying environment MG (S, {A P. )) there exists constant " > 0 such that for any state s, any step h, and any agent i, (Ra, H (s) (n)) A > 0 where A = |maxaxaxx/ Rs, a) - milllxaxke Re a)}.
We now introduce an effective white-box reward attack strategies: ga- attack. Specifically, the step h and state s, if agents all pick the target action, i.e., . (s), the attacker does not attack, i.e. T = Tith for each agent i. If agent i picks a non non-target action, i.c., a # मं (s). the g7-gap attack sets FiLA (8, nt (s)) (n + (H- b))R) (a; + m. (5)) for each agent i. From Condition 2, we
have Fi, E 1].
Theorem If the attacker follows the 17-app attack strategy on the MG agents. the best response of each agent towards any policy TT is n!. The target policy at the (NE, CE, CCE) from any agent's 's point of view. If every state s E S is reachable at every step h E [H] under the target policy, It is the unique (NE, CE, CCEJ.
The detailed proof can be found in Appendix H.1
Theorem 5 shows that the target policy π/ is the unique (NE, CE, CCE} under the n-gap attack. Thus, if the agents follow an MARL algorithm that is able to learn an e-approximate INE, CE, CCE), the agents will learn a policy approximate to the target policy. Here, we discuss the high-level idea why the g-gapp attack works. AR is the difference between the upper bound and the lower bound of the mean rewards. Condition 2 implies that each action is close to other actions from every agent's 's point of view. Although we limit the post-attack mean reward Rt in J0, 1]. the target policy can still appear to be optimal by making small changing to the rewards. Under Condition 2 and the gap attacks, the target actions strictly dominates any other non- -arget actions by at least 77 and any other distinct policy is not an e-approximate CCE with different gap e < 17. Thus, of becomes the unique (NE, CE, CCE). In addition, we can derive upper bounds of the attack loss and the attack cost when attacking MARL algorithms with sub-linear best-in- hinddsig- regret.
Theorem 6 If the best-in-hindsight regret Reg , H) of each agent's 's algorithm is bounded by a sub lab-linear bound R(T) for any MG in the absence of attack, then g-gap attack will force the agents to follow the target policy with the attack loss and the attack cost bounded by
Elosss] (ks, H)] & mR((T)n. E[Cost( K, H)] S m (T))m
(5)
7

---

We note that proposed sufficient conditions (namely Condition and Condition 2), under which the action poisoning only attacks or the reward poisoning only attacks can be efficient and successful, may be strict. They may not always hold in practice. This motivates us to investigate mixed attack strategy to be discussed in the sequel.
Gray-box attack strategy and analysis
In the gray- attack setting, the attacker has no prior information about the underlying environment and the agents' algorithm, and it only observes samples generated when the agents interact with the environment. However, the attacker is given the target policy n². Since the 7/gap reward attack strategy and d-portion action attack strategy described in Section 3 for the white-box setting rely on the information of the underlying environment, these two attack strategies are not applicable in the gray-box setting. In addition, without the information of the underlying environment, the attacker cannot check whether the action poisoning attack alone or the reward poisoning attack alone can be efficiently successful. Building on insights obtained from the white-box attack strategies, we develop a mixed attack strategy for MG in the gray-box attack setting.
In the proposed mixed attack strategy, at the step h and state s, if agent i picks the target action, i..., ai.h = = (s), the attacker does not override the action and the reward, i.c. ãg = asS and AiA = Tith- If agent picks a non-target action, i.c., ai,h 7 T1, (3), the attacker overrides its action arh = = (s) and then overrides the reward Fe.h = O.
Theorem 7 If the attacker follows the mixed attack strategy the best response of euch agent i towards any product policy πー; is n.. The optimal policy π¹ is the unique (NE, CE. CCEJ.
The detailed proof can be found in Appendix [.1 Here, we discuss the high-level idea why the mixed attack works. Under the mixed attacks, the state transitions are the same over the different actions and the reward of the non-target actions is worse than the target action. Thus, in the post- attack environment, the target policy is better than any other policy from any agent's 'ss point of view, and any other distinct policy is not an e-approximate CCE with different gap < Rmmnn where Ramnn min min.es min.g(m) (s, T/ (s)). Thus, xf is the unique (NE, CE, CCE). In addition, we can derive upper bounds of the attack loss and the attack cost when attacking some special MARI algorithms.
If the best-in-hindae -i-niihsight regret Reg(K, H) of each agent's algorithm is bounded by sub-linear bound R() for any MG in the absence of attacks, then the mixed attacks will force the agents to follow the target policy n¹ with the attack loss and the attack cost bounded by
Theorem
E|Loss| (K, H)] S mR)(T) Rmmnn E[Cost( K, H)] S 2mmR(T)/ RRmin-
(6)
Black-box attack strategy and analysis
In the black-box attack setting, the attacker has prior information about the underlying environment and the agents' algorithm, and it only observes the samples generated when the agents interact with the environment. The attacker aims to maximize the cumulative rewards under some specific reward functions R4 chosen by the attacker. But unlike in the gray-box case, the corresponding target policy of is also unknown for the attacker. After each time step, the attacker will receive the attacker reward rr. Since the optimal (target) policy that maximizes the attacker's 's reward is unknown, the attacker needs to explore the environment to obtain the optimal policy. As the mixed attack strategy described in Section 4 for the gray-box setting relies on the knowledge of the target policy, it is not applicable in the black-box setting.
However, by collecting observations and evaluating the attacker's reward function and transition probabilities of the underlying environment, the attacker can perform an approximate mixed attack strategy. In particular, exploration phase and the attack phase. In the exploration phase, the attacker explores the environment to identify an approximate optimal policy, while in the attack phase, the attacker performs the mixed attack strategy and forces the agents to learn the approximate optimal policy. The total attack cost (loss) will be the sum of attack cost (loss) of these two phases.
propose an approximate mixed attack strategy that has two phases: the
In the exploration phase, the approximate mixed attack strategy uses an optimal-policy identification algorithm, which is summarized in Algorithm]] I listed in Appendix A It will return an approximate
8

---

optimal policy n². Note that xh denotes the product policy deployed by the agents for each episode k. V is the upper bound of V* and V is the lower bound of V By minimizing V V, Algorithm finds an approximate optimal policy x². Here, we assume that the reward on the approximate optimal
policy π² is positive, i.c Rmin m [M) min minge(m ml (s, (s)) > 0. In the exploration phase, the attacker will override both the agents' actions and rewards.
After the exploration phase, the approximate mixed attack strategy performs the attack phase. The attacker will override both the agents' actions and rewards in this phase. At the step and state if agent i picks the action (s), the attacker does not override actions and rewards, i.e. diSh 04,b and Fi,A ri,h- If agent picks action 4s + x x (s), the attacker overrides the action ãg,A 04,h and then overrides the reward Fi 0. The attack strategy in the attack phase is same with the mixed attack strategy. From Theorem 7 in the attack phase, the best response each agent towards product policy TL; is n. and x² is the unique NE. Here, we discuss the high-level idea why the approximate mixed attack works. The attacker finds approximate optimal policy n' by Algorithm T is close to v² and the exploration phase is sub-linear time dependent, the performance of the approximate mixed attack strategy will be close to the mixed attack strategy. We build a confidence bound to show the value function difference between ' and π the following lemma.
Lemma If the attacker follows the Algorithm 7 in Appendix A on the agents, for any å E (0, 1). with probability at least 1 - 56, the following bound holds:
E E Pa VV,i (s1) Vi.i (s1) s 2 2/
We now investigate the impact of the approximate mixed attack strategy attack on V-learning ( al. 202T]. a simple, efficient, decentralized algorithm for MARL. The reader's convienience, we list V-learning in Appendix J.2
Theorem 9 Suppose BAWTBBANND_DUUIE of Dectrmningfflllwwe Algorithm in Appendix J.2 H+1 For given K and any å E (0, 1), let log(mLlSAK/0) The attack loss and the attack cost of the approximate mixed attack strategy during these K episodes are bounded by
and it chooses hyper-paramette w. a4 (ITi=z(1- a.)) - -
H log B and a₁ H+1
Bt
40
E HK) < HT
mV H ASKI + 2H SK- /K
Rmin
(8)
80
E (Cost(K, H)] s 2mHT
H ASKL.
Rmin
Let à be the executing output policy of V-learning, the attack loss of the executing output policy upper bounded by
20mS Rman
2TmH2S
V (s1) V (s)) S
+2H²S/2AU/T
(9)
K
If choose the stopping time of the exploration phase 7 K2/3 the attack loss and the attack cost of the approximate mixed attack strategy during these K episodes are bounded by O(K2/3) and Viii (s1) V (s1)
6 Numerical Results
In this section, we empirically compare the performance of the action poisoning only attack strategy (d-portion attack), the reward poisoning only attack strategy (7-gap attack) and the mixed attack strategy.
We consider simple case of Markov game where m 2, H = 2 and |S| = 3. This Markov game is The initial state is s at ht = 1 and the transition probabilities are:
the example in Appendix F22
((s2(s1, 0.9, ((ss|s1. 0.1, if (Defect, Defect). a(s2(s1, = 0.1, P (1 = 0.9, if a + (Defect, Defect).
(10)

---

Table 2: Reward matrices
state #1
Cooperate
Defect
state #g
Cooperate
Defoct
state #s
Cooperate
Defoct
Cooperate (1. 1)
(0.5, 0.5)
Cooperate
(1. 1)
(0.5, 0.5)
Cooperate
(1, 1)
(0.5, 0.5)
Defect
(0.5, 0.5)
(0.2, 0.2)
Defect
(0.5, 0.5)
(0.1, 0.1)
Defect
(0.5, 0.5)
(0.9, 0.9)
The reward functions expressed in the following Table
We set the total number of episodes K 107. We set two different target policies. For the first target policy, no action/reward poisoning Markov attack strategy alone can efficiently and successfully attack MARL agents. For the second target policy, the d-portion attack and the 17-gap attack can efficiently and successfully attack MARL agents.
The target policy is that the two agents both choose defect at any state. As stated in Section 3 and Appendix 3.1 the Condition and Condition 2 do not hold for this Markov game and target policy, and no action/reward poisoning Markov attack strategy alone efficiently and successfully attack MARL agents.
Case 1.
In Figure I we illustrate the mixed attack strategy, the d-portion attack strategy and the n-gap attack strategy on V-lcarning agents for the proposed MG. The æ-axis represents the episode & in the MG. The y-axis represents the cumulative attack cost and attack loss that change over time steps. The results show that, the attack cost and attack loss of the mixed attack strategy sublinearly scale as T, but the attack cost and attack loss of the d-portion attack strategy and the 17-gap attack strategy linearly scale as T, which is consistent with our analysis.
400
Figure 1: The attack loss (cost) on case 1.
Figure 2: The attack loss (cost) on case 2.
The target policy is that the two agents choose to cooperate at state 81 and 82 but to defect at state s3. As stated in Section 3 and Appendix 3.I] the Condition I and Condition 2 hold for this Markov game and target policy. Thus, the d-portion attack strategy and the 17-ap attack strategy can efficiently and successfully attack MARL agents.
Case 2.
In Figure 2 we illustrate the mixed attack strategy, the d-portion attack strategy and the 77-app attack strategy on V-learning agents for the proposed MG. The results show that, the attack cost and attack loss of all three strategies sublinearly scale as T, which consistent with our analysis. Additional numerical results that compare the performance of the mixed attack strategy and the approximate mixed attack strategy are provided in Appendix
7 Conclusion
In this paper, we have introduced an adversarial attack model on MARL, We have discussed the attack problem in three different settings: the white-box, the gray-box and the black-box settings. We have shown that the power of action poisoning only attacks and reward poisoning only attacks is limited. Even in the white-box setting, there exist some MGs, under which no action poisoning only attack strategy or reward poisoning only attack strategy can be efficient and successful. We have then characterized conditions when action poisoning only attacks or only reward poisoning only attacks can efficiently work. We have further introduced the mixed attack strategy in the gray-box setting that can efficiently attack any sub-linear-regret MARL agents. Finally, we have proposed the approximate mixed attack strategy in the black-box setting and shown its effectiveness on V-learning. This paper raises awareness of the trustworthiness of online multi-agent reinforcement learning. In the future, will investigate the defense strategy to mitigate the effects of this attack.
10

---

8 Acknowledgement
This work was supported by the National Science Foundation under Grant CCF-22-32907.
References
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International conference machine learning, pages 551-560. PMLR, 2020.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In International Conference Learning Representations, 2020.
Kiarash Banihashem, Adish Singla, and Goran Radanovic. Defense against reward poisoning attacks in reinforcement learning. arXiv preprint urXiv:2102.05776 2021.
Vahid Behzadan and Arslan Munir. Vulnerability of deep reinforcement learning to policy induction attacks. In International Conference on Machine Learning and Data Mining in Puttern Recognition, pages 262-275. Springer, 2017.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Dçbiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint 19I:::::12.000 16660600, 2019.
Noam Brown and Tuomas Sandholm. Superhuman for multiplayer poker. Science, 365(6456))885 890, 2019.
Yiding Chen, Xuezhou Zhang, Kaiqing Zhang, Mengdi Wang, and Xiaojin Zhu. Byzantine-robuss online and offline distributed reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3230-330033 02600, PMLR, 2023.
Yifang Chen, Simon Du, and Kevin Jamieson. Improved corruption robust algorithms for episodic reinforcement learning. In International Conference on Machine Learning, pages 1561-1570. PMLR, 2021.
Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adversarial policies: Attacking deep reinforcement learning. In International Conference on Learning Representations, 2020.
Wenbo Guo, Xian Wu. Sui Huang, and Xinyu Xing. Adversarial policy learning in two-player competitive games. In International Conference Machine Learning, pages 3910-3919. PMLR, 2021.
Yunhan Huang and Quanyan Zhu. Deceptive reinforeement learning under adversarial manipulations cost signals. In International Conference Decision and Game Theory for Security, pages 217-237. Springer, 2019.
Jin. Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110.14555, 2021.
Guanlin Liu and Lifeng Lai. Provably efficient black-box action poisoning attacks against reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference on Machine Learning, pages 7001-7010. PMLR, 2021.
Xiangyu Liu, Souradip Chakraborty, and Furong Huang. Controllable attack and improved adversarial training in multi-agent reinforcement learning. In Workshop Trustworthy and Socially Responsible Machine Learning, NewrlPS 2022, 2022,
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Corruption-robeet exploration in episodic reinforeement learning. In Conference on Learning Theory, pages 9242-3245. PMLR, 2021.
Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jemry Zhu. Policy poisoning in batch reinforcement learning and control. In Advances in Neural Information Processing Systems, volume 32, 2019.
Yuzhe Ma. Young Wu, and Xiaojin Zhu. Game redesign in no-regret game playing. In Proceedings of the Thirty-First International Joint Conference Artificial Intelligence, pages 3321-3327, 2022.
Weichao Mao and Tamer Başar. Provably efficient reinforcement learning in decentralized general-sum markov games. Dynamic Games and Applications, pages 1-22, 2022.

---

Mohammad Mohammadi, Jonathan Nöther. Debmalya Mandal, Adish Singla, and Goran Radanovic. Implicit poisoning attacks in two-agent reinforcement learning: Adversarial policies for training- time attacks. arXiv preprint arXiv:2302. 13851, 2023.
Afshin OroojlooyJadid and Davood Hajinezhad. review of cooperative multi-agent deep reinforcement learning. arXiv preprint arXiv: /908, 03363, 2019.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via environment poisoning: Training- time adversarial attacks against reinforcement learning. In International Conference on Machine Learning, pages 7974 7784,,99,2227 2020.
Amin Rakhsha, Xuezhou Zhang, Xiaojin Zhu, and Adish Singla. Reward poisoning in reinforcement learning: Attacks against unknown learners in unknown environments. arXiv preprint arXiv:2 08492, 2021.
Anshuka Rangi, Haifeng Xu, Long Tran- Thanh, and Massimo Franceschetti. Understanding the limits of poisoning attacks in episodic reinforeement learning. In Lud De Raedt, editor, Proceedings of the Thirty- First International Joint Conference on Artificial Intelligence, IJCAI-22, pages 3394 3400. International Joint Conferences on Artificial Intelligence Organization, 2022.
Shai Shalev-Shwartz. Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint 110v::61. 2016.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10)10995 1100, 1953.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye, Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intelligence and Statisticx, pages 2992-3002. PMLR. 2020.
David Silver. Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre. George Van Den Driessche. Julian Schrittwieser, Ioannis Antonoglou, Veda Panncershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):481-49, 2016.
Yanchao Sun, Da Huo, and Furong Huang. Vulnerability-awarc poisoning mechanism for online rl with unknown dynamics. International Conference on Learning Representations, 2021.
Oriol Vinyals, Igor Bahuschkin, Wojciech M Czamecki, Michaäl Mathieu, Andrew Dudzik, Junyoung Chung, David Choi, Richard Powell, Timo Fwalds, Petko Georgiev, et al. Grandmaster level starcraft using multi-agent reinforcement learning. Nature, 575(7782)3300-354 2019.
Lun Wang, Zaynah Javed, Xian Wu, Wenbo Guo, Xinyu Xing, and Dawn Song. Backdoork: Backdoor attack against competitive reinforcement learning. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 6699-37055 8 2021. Main Track.
Chen-Yr Yu Wei, Christoph Dann, and Julian Zimmert. A model selection approach for corruption robust rein- forcement learning. In International Conference Algorithmic Learning Theory, pages 1043-1096. PMLR, 2022.
Tianhao Wu, Yunchang Yang, Simon Du, Liwei Wang. On reinforcement learning with adversarial corruption and its application to block mdp. In International Conference on Machine Learning, pages 1 1199-11306. PMLR, 2021.
Young Wu, Jermey McMahan, Xiaojin Zhu, and Qiaomin Xie. Reward poisoning attacks on offline multi-agent reinforcement learning. arXiv preprint Xr0: 01888, 2022.
Qiaomin Xie, Yudong Chen, Zhaoran Wang, and Zhuoran Yang. Learning zero-sum simultancous-movt markov games using function approximation and correlated equilibrium. In Conference on learning theory, pages 3674-3682. PMLR, 2020.
Hang Xu, Rundong Wang, Lev Raizman, and Zinovi Rabinovich. Transferable environment poisoning: Training- time attack on reinforcement learning. Proceedings of the 20th international conference on autonomous agents and multiagent systems, pages 1398-1406, 1406, 2021.
Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. Advances in Neural Information Processing Systems, 33: 1166-1178 178, 2020a.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021a.
12

---

Xuezhou Zhang, Yuzhe Ma. Adish Singla, and Xiaojin Zhu. Adaptive reward reward-poisonee poisoning attacks against reinforcement learning. In Proceedings the 37th International Conference Machine Learning, volume 119, pages 11225-11234, 2020b.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Robust policy gradient against strong data corruption. In International Conference on Machine Learning, pages 23911-1201, PMLR, 2021b.
13

---

A The exploration phase of the approximate mixed attack strategy
The exploration phase of the approximate mixed attack strategy uses optimal-policy identification algorithm, which is summarized in Algorithm 1 which is approximate optimal policy.
It will return an approximate optimal policy n!,
Algorithm 1: Exploration phase for Markov games
Input:
Stopping time Set BNN) (HvS (1
I: Initialize (s, a) = V V. a) = 2,, (,,
(s.
V 1,H+1 = -V 11
A cc, No(s) ((s and (s,,
for any
a. h.).
2: for episode k == 1,...,, do
3: for step h = ......1 do
4: for each (s. E x A with (s, a) > 0 do R, + P 1,441,s,, + B(Nn(s a)), H and
5:
Update (s, 2 (s, a) = max R1 + V - a)), end for for each s E with (s, a) > do
6:
7:
8:
Update (s) = maxaed Q (s,
9:
Update V (s) = 2t. nA (8)) and (t,n(s, a) = 21,1,0, Th (8)).
end for end for
11:
12:
if E PPPP)() BV (s) (x) + H
S 1log(27/))
then
2k
13:
= P Po)) (V (8) - (+) - H
(2gg(27/)) 2h
and o- = π.
14:
end if
for step 1 =1 1........ do
16:
Attacker overrides each agent's 's action by changing 0g to dg where ãn = (sa)
17:
The environment returns the reward rs, and the next state 5h+1 according to action ap. The attacker receive its reward T+.h-
18:
Attacker overrides each agent's 's reward by changing TiA to Pish = 1. Add to (sk, ān) and NA (sp, ān. 8h+1). ( ā.) (s,, āz. -)NN as) Update (sn, ān) (sp, ān) + (ri,e (s ax) (N,,,, (s),
19:
20:
21:
end for
22:
Update No(s1)= (o(s1) 1 and Po(-) No(-)/k.
23:
end for
24:
Return .!.
B Additional numerical results
In this section, we empirically compare the performance of the mixed attack strategy and the approximate mixed attack strategy. We consider a multi-agent system with three recycling robots. In this scenario, a mobile robot with rechargeable battery and a solar battery collects empty soda cans in city. The number of agents is 3, i.c. 3. Each robot has two different energy levels, high energy level and low energy level, resulting in states in total, i.c. =
Each robot can choose conservative action an aggressive action, so A; = 2 and A A= 8. At the high energy level, the conservative action to wait some place to save energy and then the mean reward is 0.4. At the high energy level, the aggressive action is to search for cans. All the robots that choose to search will get basic reward 0.2 and equally share an additionally mean reward 0.9. For example, if all robots choose to search at step, the mean reward of each robot is 0.5. At the low energy level, the conservative action to return to change the battery and find the cans on the way. In this state and action, the robot only gets a low mean reward 0.2. At the low energy level, the
14

---

conservative action is to wait in some place to save energy and then the mean reward is 0.3. We use Gaussian distribution to randomize the reward signal.
We set the total number of steps H = 6. At the step S 3, it is the daytime and the robot who chooses to search will change to the low energy level with low probability 0.3. At the step h 2 it is the night and the robot who chooses to search will change to the low energy level with high probability 0.7. The energy level transition probabilities are stated in Figure and Figure 4 'H' represents the high energy level. 'L' represents the low energy level. 'C' represents the conservative action. 'A' represents the aggressive action.
P=0.3
P-0.7
P=0.7 A
P=0.3
P=1
P=1
P-0.1
P=0.1
P=0.9
P=0.9
P=0.9
P=0.9
Figure 3: Energy level transitions S 3. Figure 4: Energy level transitions at z 4.
We consider two different attack goals: (1) maximize the first robot's rewards; (2) minimize the the second robot's 's and the third robot's rewards. For the gray box case, provide the target policy that maximizes the first robot's rewards or minimizes the the second robot's and the third robot's s rewards. For the black box case, set R R1. maximize the first robot's rewards and set R = R2,n/2 22- Ra,x/2 to minimize the second robot's and the third robot's rewards.
atoud
05gg 00000 10
Figure 5: The cumulative attack loss and cost of the mixed attack and the approximate mixed attack.
We set the total number of episodes K = 107. In Figure 5 we illustrate the mixed attack strategy and approximate-miis mixed attack strategy on V-learning agents for the proposed MG. The z-axis represents the episode in the MG. The y-axis represents the cumulative attack cost and attack loss that change over time steps. The results show that, the attack cost and attack loss of the mixed attack strategy and approximate-mise mixed attack strategy sublinearly scale T, which is consistent with our analysis. Furthermore, Figure 5) shows that the performance of the approximate-mixce attack strategy nearly match that of the mixed attack strategy. This illustrates that the proposed approximate-nn mixxxd attack strategy is very effective in the black-box scenario.
C Related works
Due to the page limit of the main paper, we do not provide a comprehensive comparison with prior research on adversarial attacks. We add the following discussion to Appendix.
Among the existing works attacks in single-agent RL, the most related paper is (Rangi al. 2022] which studies the limitations of reward only manipulation or action only manipulation in single-agent RL and proposed an attack strategy combining reward and action manipulation.
There are multiple differences between our work and [Rangi al. 2002]. First, the MARL is modeled Markov game, but the single-agent RL is modeled as MDP. In Markov game, each agent's
15

---

action will impact other agents' rewards. Second, the learning object of single-agent RL and MARL different. The single-agent RL algorithms learn the optimal policy, but MARL algorithms learn the equilibrium. Since the attacks on one agent will impact all other agents and the equilibrium is considered as the agents' learning object, we have to develop techniques to carefully analyze the impact of attacks and the bound of the attack cost.
Here, we discuss the related work on the adversarial attacks on single MARL. Maa al. 2019
studies reward poisoning attack against batch RL in which the attacker is able to gather and modily the collected batch data. (Rakhsha et al.
2020] proposes a white-box environment poisoning model
in which the attacker could manipulate the original MDP to a poisoned MDP. [Behzadan and Munir
2017 Zhang et al.) [020b] Rangi et al.) 2022] study online white-box reward poisoning attacks in
which the attacker could manipulate the reward signal before the agent receives it. (Sun et al.) [021] proposes a practical black-box poisoning algorithm called VA2C-P. Their empirical results show that VA2C-P works for deep policy gradient RL. agents without any prior knowledge of the environment.
[Rakhsha et al. 202T] develops a black-box reward poisoning attack strategy called U2 that can provably attack any efficient RL algorithms. (Xu et al., 2021] investigates training-time attacks on RL agents and the introduced attacker can manipulate the environment.
Here, we discuss the related work on the adversarial attacks on MARL. MMa el al., 2022] considers a game redesign problem where the designer knows the full information the game and can redesign the reward functions. The proposed redesign methods can incentivize players to take specific target action profile frequently with small cumulative design cost. Ma's 's work considered the norm-form game but we considered the Markov game. The norm-form game is simple case of the Markov game with horizon agent reinforcement learners, assuming that the attacker controls one of the learners. In our work, the attacker is not one of the learners, but an external unit out of the original Markov game. The attacker can poisoning the reward/action of all learners at the same time that can fool the learners to learn a specific policy. [Wu et al.) [022] studies the reward poisoning attack on offline multi-agent reinforcement learners. The attacker can poisoning the reward of the agents. We considered the online MARL. In offline MARL, the attacker can estimate the underline Markov game from the offline datasets. In online MARL, the attacker may not have the knowledge (reward/rransition functions) of the Markov game. (Wang et al.) 202T] studies the backdoor attack in two woo-player competitive RL systems. The trigger is the action of another agent in the environment. They propose a unified method to design fast-failing agents which will fast fail when trigger occurred. [Liu et al.) [022] studies the controllable attack by constraining the state distribution shift caused by the adversarial policy and offering a more controllable attack scheme. (Chen et al.) 2023) considers a situation that fraction of agents are adversarial and can report arbitrary fake information. They design two Byzantine-robuse distributed value iteration algorithms that can identify near-optimal policy with near-optimal sample complexity. [Mohammadi et al. 2023) studies targeted poisoning attacks in a two-agent setting where an attacker implicitly poisons the effective environment of one of the agents by modifying the policy of its peer.
1. [Gleave et al., 2020 Guo et al.) 2021] study the poisoning attack on multi
D Discussion
Due to the page limit of the main paper, we put the discussions regard the attack detection, the computational cost, the scalability of the attack strategies in Appendix.
Attack detection We did not consider the attack detection in our problem, but the attack detection problem is also important. In this paper, we assumed that the agents do not know the existence of the attacker. Under this assumption, if the agents have no prior information of the MG, the proposed white and gray box attack is hard be detected. As we consider the Markov attack strategy this paper, the post-attack environment under the Markov attack strategy is still a Markov game. Without reference or prior information of the MG, the agents can not figure out whether the environment they observe is a post-attack environment or an attack- frreck environment. The proposed black attack may be detected, as the transition probabilities of the post-attack environment change over time. The goal of our paper is to understand and identify the impacts of different adversarial attacks. We hope our work can inspire follow-up work that can detect and mitigate such attacks so that RL. models can be used in safety-critical applications. It is an important future direction for us to pursuc.
16

---

Computational cost For the proposed black-bon box attack strategy (the approximation mixed attack), the computational cost is O(S" AHT mKH). H. The proposed algorithm will compute the Q-values for each visited action-state pair at every steps and every episodes in the exploration phase. The computation of Q-value costs OSS). Thus, the total computational cost the exploration phase O AHr). In the attack phase, the attacker only need to change the action and the reward for each agent so that the computational cost in the attack phase is (m
The gray-box attack strategies can be directly used in large-scale environments, even in some high-dimensional continuous environment. However, in the continuous space, the attacker does not change the non target action to but Fi.h * c in order to avoiding sparse reward. The ideas of the black-box attack strategies still work. However, the exploration phase should resort to some function approximation methods to efficiently explore an approximate target policy. Then the attack phase keeps the same the gray-box attack.
Scalability
E Notations
In this section, we introduce some notations that will be frequently used in appendixes.
The attack strategies in this paper are all Markov and only depend on the current state and actions. The post-attack reward function has the same form as the original reward func- tion which is Markov and bounded in [0, 1]. Thus, the combination of the attacker and the environment MG(S, {A. J== H, P. (R, }m=)) can also be considered as new environment MG(S, [A H, P, { R. f ). and the agents interact with the environment. R.,, S -> [0, represents the post-attane reward function for the 7t agent in the step h. The post-attack transi- tion probabilities satisfy Pa (s' (s a) E. An (a') s, (s'
We use R₁ N₁ @, and V; to denote the mean rewards, counter, Q-values and value functions of the new post-attack environment that each agent observes. We use N V and x² to denote the counter, value functions, and policy maintained by the agents' algorithm at the beginning of the episode k.
For notation simplicity, we define two operators I' and D follows:
PA [N[V](s, a) (1 [V(s'),
(1I)
D=(0](s) = (a (Q(s. a)].
Furthermore, we let A denote the action manipulation. A = {AA) is collection of action- manipulation matrices, so that (-Is, a) gives the probability distribution of the post-attack action actions are taken at state and step h. Using this notation, in the d-portion attack strategy, we have A (+))s, a) = dy (s, a)/m, and (n (s)ls, a) = (s, a)/m.
F Proof of the insufficiency of action poisoning only attacks and reward poisoning only attacks
F.1 Proof of Theorem 1
We consider simple case of Markov game where m = 2, H = and |S] = 1. The reward function can be expressed in the matrix form in Table 3
Table 3: Reward matrix
Cooperate
Defect
Cooperate (1, I)
(0.5, 0.5)
Defect
(0.5, 0.5)
(0.1, 0.1)
The target policy that the two agents both choose to defect. In this MG, the two agents' rewards the same under any action. As the action attacks only change the agent's 's action, the post-attack
17

---

Table 4: Post-attack reward matrix
Cooperate
Defect
Cooperate
(r1, r1)
(r2, r2)
Defect
(73, r3)
(74, r4)
rewards have the same property. The post-attack reward function can be expressed in the matrix form in Table
To achieve the objective in ( we first have 12 S r4 and r3 S r4, as the target policy should be an NE. Since the other distinct policy should not be c-approximate CCE, consider the other three pure-strategy policies and have
> 12 +2, > tE
> r3 +, > 13 +
(12)
> + >1
Note that 73 > 11 + and r1 r'y + contradictory and 12 r and r1 12 + contradictory. We must have r4 > T3 + c or F4 > 12 + c. As the action attacks will keep the same boundary of the rewards, r3 0.1 and r2 2 0.1. Then,
0.1 +e.
Suppose there exists an action poisoning attack strategy that can successfully attack MARL agents. We have ΣxnΣ h= E (at = (st,)) T o()) (T()), i.e. the attack loss scales on o(T). To achieve the post-attack reward satisfy T4 0.1 + the attacker needs to change the target action (Defect, Defect) to other actions with probability at least c, when the agents choose the target action. Then, we have Σ Σ E (( # af. = ??eZ)) The expected attack cost is linearly dependent on T. Hence, there does not exist an action poisoning attack strategy that is both efficient and successful for this case.
F.2 Proof of Theorem 2
We consider simple case of Markov game where m 2, and [S] = 3. The reward functions are expressed in the following Table
Table 5: Reward matrix
state
Cooperate
Defect
Cooperate
(1, 1)
(0.5, 0.5)
Defect
(0.5, 0.5)
(0.2, 0.2)
state $2
Cooperate
Defect
Cooperate
(1, 1)
(0.5, 0.5)
Defect
(0.5, 0.5)
(0.1, 0.1)
state $3
Cooperate
Defect
Cooperate (1, 1)
(0.5, 0.5)
Defect
(0.5, 0.5)
(0.9, 0.9)
The initial state is s1 at h 1 and the transition probabilities are:
P(82|81, a) = 0.9, ((83/811 a) = 0.1, if a = (Defect, Defect), P(s2|s1, 0.1, P(sa 0.9, if + (Defect, Defect).
(13)
The target policy that the two agents both choose to defect any state. The post-attack reward function of the three states can be expressed in the matrix form in Table 6
18

---

Table 6: Post-attack reward matrix
state
Cooperate
Defect
Cooperate
(T1, r2)
(rs, 14)
Defect
(rs, rg)
(7r, rg)
state $2
Cooperate
Defect
Cooperate
(-,-)
(-,-)
Defect
(-.-) (rg, r10)
state 83
Cooperate
Defect
Cooperate
(-.-) (-,-)
Defect
(-.-) (f'1, r12)
We limit that the post-attack mean reward R has the same boundary condition with that of the pre-attack mean reward R, i.e. R E [0, 1]. Then, 0 S "1,-.., 112 1.
Suppose there exists reward poisoning attack strategy that can successfully attack MARL agents, H have E (at,, (st,,)) T o(T) SQ(T), i.e. the attack loss scales
oT").
rg 0.1| 0.1. r10 0.1 > 0.1, 1 0.9 0.1, or - 0.9 0.1, have the attack cost
Σk Em E E( - ) Q(0.1+KK) = ((T). Thus, (ra- 0.1 S 0.1, |r - 0.1| I 0.1,
I' 0.9 S 0.1 and |12 - 0.9| $ 0.1.
For the target policy, we have V (s1) = + 0.9 + 0.1 T11 For the policy n' with (s1) = (Cooperate, Defect), (12) = (Defect, Defect), T<(ss) (Defect, Defect), we have Vi (s1) rs + 0.1
0.9 * r11-
To achieve the objective in (T. the attacker should let the target policy to an NE. Thus, we have V (s) 2 a
1.1 (st) and then ry + 0.9 * 79 + 0.1rm 2 + +0.1 + +r9 As |rg 0.1 S 0.1 and |m - 0.9 < 0.1, we have r7 2 ra + 0.48. From the boundary condition, we have r3 2 0 and then r7 2 0.48. The attack cost scales at least on 120028 T) for successful reward attack strategy.
In summary, there does not exist an reward poisoning attack strategy that both efficient and successful for this case.
G Analysis of the d-portion Attack
G.1 Proof of Theorem
We assume that the minimum gap exists and is positive, i.e. A > 0. This positive gap provides an opportunity for efficient action poisoning attacks.
We assume that the agent does not know the attacker's manipulations and the presence of the attacker. The attacker's manipulations actions stationary. We consider the combina- tion of the attacker and the environment MG(S, HA H, P, {R, ) as new environment MG(S, {A) H, P. { (R,,,,) and the agents interact with the new environment. We define Q and Vú as the Q-values and value functions of the new environment MG that each agent observes.
We first prove that N. is an NE from every agent's 's point of view.
Condition 1 implies that m is not the worst policy from every agent's point of view, and there exists policy -- that is worse than the target policy from every agent's point of view. Denote Al, Q (s, (())) Q1 (s, th (s)). We define the minimum gap Amin Min (s).
19

---

We set Ph V i,+1 (s,a) -Errral V (5
From d-portion attack strategy. we have
da(s, a)
ViJ 1, (8, + (1 dn(s,a)
( Ph PPnVihhi (s)),
(s, (s, a)
P'
m
m
(14)
and
an(s,a) Rs,((s,a==
(s, + (1 (1- dp da(s,a)
(1-ahimm))
R (s, (s))
(15)
m
m
Since the attacker does not attack when the agents follow the target policy, we have V (s)
Vol 4,41 (s). Then,
(n(s,a) (/ + (1- dn(s,a)
(s,
(16)
m
m
If a; + (s), we have
x i) ( ()) 2m
(o - (5) z
Amin
(17)
2m
We have that policy ग| is best-in hhindigthindsight policy towards the target policy TL, at step h in the vital
observation of each agent i, i.e. V. xx!xx! --
(s) for any agent i, any state 8 and any policy Vi,441 (8) 3,44
Since the above argument works for any step E [H], we have that the best response of each agent towards the target product policy N is n. and the target policy is an (NE, CE, CCE) under d-portion attack.
Now we prove that the target policy क. is the unique (NE, CE, CCE), when every state s E S is reachable at every step [H] under the target policy.
1,1 (s) (.T(()) = 0 for ((t)-(((s)
If there exists an CCE ' under d-portion attack, we have max:e(m] any initial state s.
At the step H. (T, a) Ri. (s, (s) Since (s, 2 (s, TT(s)) Amin with Amin 0, the policy π1.1 is the unique best response towards any policy T-i ic. yi y (6)= 4,1 - Vi (s) and V.
- (8) > V.L.n---." (s) for any (-,n(-1s) & T. (-(s). Thus, we have (5H) (SH) for any state that is reachable at the time step H under policy T'. We assume that every state S is reachable at every step h E [H] under the target policy.
i,Hf
Under d-portion attacks, the post-attack action aA =s((s) with probability more than 0.5. Thus, reachable every step [H] under any policy i and d-portion attacks.
every state
Recall that for any a; # (s),
T (s, TL (s) x x.)
TT, a) Amin. 1mm../mm. 22..
(18)
Suppose (5 1H -h41 = { 1h#41 for any states. If (((((1s)) * n/. (11s) at a reachable state 8,
we have
(s)( = Earn (+10 (s,
Ea (1s) 1T
(19)
EE pسم (11) 2 m| (s) a:)) - cmmin/ 22m
x *(s) cD cDmin/m
20

---

with some constant 0. Then, n' is not an CCE in such case.
From induction h H, H -,.... n' x² for any states. every state S is reachable every step h E [H] under the target policy, n is the unique (NE, CE, CCE).
G.2 Proof of Theorem
Consider an arbitrary Markov policy и. From d-portion attack strategy, we have
( a) (s a)
Rs, x (s)) + dd(ss, a)
Rs, Th (s))
m +
m
(s a)
V i (s. [ + m dn a) P V 1i (T) (8))
m
m
(n, a)
(Ran(s, (())) Rea(s, (61)
(20)
m
da (s a) m (P PA Ph (8))
+
m
(s) (s, + (s,
PA ( (T))
and
(s) = Dr. ((s)
D mp [d](s) - m (Ra,n(s (8, (+)))
(21)
+ D (s) - m
(s)) - P ( (8))
+ R4 (s, T (s)) + PA VT V. (s, (s))
Now we bound the difference between V (s) and Vil (s) for any policy a.
ViA (8) - (x) = VIT (8) - Dry (T)) + Dra. (QT,)(s) (+).
(22)
(a)
(b)
For term (a), from equations
20 and 21
we have
Vi (8) DA,, (T)
DA (s)
m
[a,n [s) (s,
(23)
m
m D D=a (+)
(Pn Vos (s. PAi
(s
m
Since the attacker does not attack when the agents follow the target policy, we have Va (1)
Vet 1,h4((s). (s).
ViT (s) D.,, (TT)(ss) = m m-D.. [s](s)
(oth -O
(24)
Denote (s)(s)) (s,
(s))) (s)). We have
(1
m
V (s) DDr, (+) 2m Ea-th(-1))
Σ
1(a; + क -.. (s))
(25)
21

---

For term (b), from equations 20 and 21
we have
D=,
1Q
(
DT. [d](s)
m DT,, [d](s)
P Vit (b))
Pr 1/
i. TT (s))
D (+)
-D,,, PA V.TT
PA i, (s, (s))
i.+1 (5, T (8))
m
m
(26)
DD [s](s)
PA Vi
1h41 1
m
D. (s)
V. 1 Vih+al(s, Th (s))
+
m
(1) (h)+((8))
By combining terms (a) and (b), have
Vill (sh) (sh)
[I # (ha((ww)
2m
(27)
+ Esnti
Pa Pa (i-A (-oa))
(iih (s441)
H1
A 1. (sw)
A.P
ΣΣ
I(a # ((
2m
We i=1
From the definition of the best-in-hindsigee regret and 27
we have
Reg, (K, = max
xn
(st) - (s1)
111
1=1
(28)
K
x
(st) - (sf))-
A=1
Now, we bound E V. x (s1) - V755 (s1)) for any policy æ. We introduce some special strategy
modifications (dl 1 h=1- For any h 2 h, we have S.., Te. = Th (8) and for any < h, we
have 01 o n (8) = Ti,h (s). Thus,
V.l x xs1x (s1)
(29)
m
oo, x5 (81)
1.0
10 (81)).
4,1
1,1
When = H, we have
m2
oT, 00, xx (8))
o x (51)
0 10 ((s) i1
Vi Do 1 oT
-. A,P
(HH)
(SH)
(30)
x (=xx==((s))>>>> Vin((s)) V.H
=E,.A.P
(11
-E..A,
Σ 1(ai, + n. x),n(H))
2m
22

---

For h < H, we have
o0 (ss) (81) - 1,1
1:0/, 1, 1 (51)
p. xx '(sh) - p i
1. 11t1 o (8h)
A,
1.
(31)
Q (ah)
=FAAA
oll 0 -D Df (0
Shh (Sh (3))
Tith
(Ixx -Dx)) Rich + Pn P.io 1
-E..A,P
(8%)
2m
i,++1
where the second equation holds as o T x T- = 11,41 o Ti x n at any time step I/' > I and the last equation holds from equation (20).
Note that T = Ri, + Pr Pa 2 = Ri, + Ps Vxl +,++1
From equation 31
we have
bl (o (81) (s1) - V. pl
D.linttooe 1 (31)
1.1
1,1
8h, Tit (9t))
Tith
(ID -D,-) [ (sw)
E,
2m
m 1 Vish
Sh. n. (())
+ E A
2m
(Ixxt -
PA A
i,+
X
PP Vo
s,6+1
(st)
(32)
Denote (17(s)
(s, (s)))
Q7 (s, nh (s)). Thus,
(s,
Te, (sh, T/A (sn)
ET
A (n)(
(33)
2m
Now, we bound item @ (DD -Dx-)
PA 1
-P
Pi 211+1
(sk) 2
(Ixt DDx
PA 100l
PA V
(st)
i.1+1
2DD nm (s(h)
D
P.
Vint ((sh)
sh1+1
m
(34)
2 2(m DD,,, (sh))
Vil ((sH)
+
1,++1
m
=21B, A.P
Volintoo ox. Xx_ 1,4+1
(Sn+1)
(
Var
because the RHS of the inequality is smaller equal to 0.
23

---

Ph V 200,441011X
If (Dat xT Dx-)
Ps (,++
(sh) S 0.
i,h+1
(Dxt -Dx-)
Pn 10la4100,800
Vini PA
2,411 (sh)
i,++1
2D kn (sh)
(Txx Dx-)
PA V 1 10
Ph P 2 (8h)
m
2D Fn [d] (sh)
DxtPP
( 1 1m
(35)
111+1
m
2(m
Dx (s(()) Dz- 1
V (1)))
1,641
m
V (8n+1) (m
A,
Vil (i
1,441
From 27 we have
Vel 1ih+ (8h+1)
V. P
(sh+1)
1,++1
(ow)
(ain # n. (sw))) 2m
0 00 1 w1=h+1 1=1
(36)
(s)
(m 11 1)
max sES,i[[m]
2m
M=h+1
m 1) (sn).
2m
where the last inequality holds when min, (1)))) 2 Combine the above inequalities, we have
H = max A A/,r((s)
Sh: N. (8k))
Ts
(m - 1) D (sn) 5
ス - 2-EE, B.
(37)
2m
and
yol, 10 (x1) - polass 21 (81)
1=1
=0 + 2
m 1 - Tish
8h: T (((n(88)))
A A.t (sn)
A,P
2m2
(38)
m
1/ (8t)
A,
1aath # Tl(n(sh))
2m1
m
Amin
2 ZE,AA
1(ar,h # Tt.n (())
2m
In summary,
H
Amin
Amin
Reg, (eg,(K,H)) H) >
Σ 1=1
Er. A.P
Σ i=l
Ilain + n. ((.)))))
ELLos (K, H)]
(39)
2m
2mn
the best-in-hindsight regret Reg(K, K, H) of each agent's algorithm bounded by sub-linear bound RT"), then the attack loss is bounded by [E]Lsss (K, H)] < 2m 2m²R(T)/ Amin.
24

---

The d- d-portion attack strategy attacks all agents when any agent i chooses an non-target action. We have
K
Cost(K K H)
(1 # a + 17 v...1
(40)
Then, the attack cost is bounded by mos| (K, H)] S 2m ((T)
H Analysis of the 77-gap attack
H.1 Proof of Theorem
We assume that the agent does not know the attacker's manipulations and the presence of the attacker. The attacker's manipulations rewards stationary. We can consider the combina- tion of the attacker and the environment MG(S, {A: H, P, {R:)m) as a new environment (G(S, {A) H, P, (())) and the agents interact with the new environment. We define Q and Vi as the Q-values and value functions of the new environment MG that each agent observes.
We introduce some special strategy modifications
1# {o For any h' h, we have of, Tith (8) (s) and for any h' < h, have of (s) (s) Thus,
x (s1) (1
(51)
(81)
Doln 0x, (81)]-
(41)
1,1
We have that for any policy n,
(01)
4,1
(s1))
1 1o OOT NOTEX=-1 (88)) 1.6
- 10T (sh)
i.1t
(42)
-E,,A.P
(D
(DoInoREAxTiin -D D )
or x
(8h)
2,
(Dontaxr - -Dan)
RiL + PA i,++1
=FZ,A,
(8x)
Since Rs, Rapls, mt (s)) (H A) 1a; + (s) from r7-gap attack strategy
and (1f - h) mins x (s',' < PA PAV. 1,++ (s',a) d') (H h) max xa' xh Rs, (s', a') for any and a, we have
ola -T.
11 x (s1)
[V. 11
(s1) -
i,1
= -E A.P Σ Th(assn)(T -H -H (H))))R)d(aa * ,/, (3h))
+ A
Σ Th (a(als)) x
Pn i,41
polnni xx- (sn, ((n( x a..) - IP
0m, xx
(sh a)
i
> 2F.AA.
Σ Tn(alss)n1 F x(a()))
-Ex,A. [[aau # nh (s)) n
(43)
25

---

Thus,
xx_ (81) - (s1) 2 A.
Σ I(ash # s(a(6w)) 7 720.
(44)
The target policy is an NE, and then also an CE or CCE.
Now we prove that the target policy क. is the unique (NE, CE, CCE), when every state 8 E S is reachable at every step [H] under the target policy.
If there exists an CCE n' under 77-aap attack, we have maxie(m] (V,l (8) Vi (s))
O for any initial state 8. If (11)) * (11)) at a reachable state 8, we have that
Eg A.P E laain The (sN)) Thus,
H
Vi x (81) (x1) AA
Σ (ar, & π. =((((s)) 11 0,
(45)
and n' is not an CCE. summary, the target policy n. is the unique (NE, CE, CCE).
H.2 Proof Theorem
From the definition of the best dest-in-hingg -n-hiihsighh regret and 51 we have
((())=
x (st) Vे (sf)
Reg, (K, H) max
x
km
(46)
K
(8f) - VI (64))-
A=1
From 44
we have
Reg. (K H)
E A.P
Σ
Ia n # Nt. (s 1
(47)
and
Reg, (K, H) = nEE[Loss (K, H)]
(48)
the best-in-hindsight regret Reg( K, H) of each agent's 's algorithm bounded by a sub-linear bound (T),, then the attack loss is bounded by Lo[sss (K, H)] < mR(())n
The 77-gap attack strategy attacks all agents when any agent chooses an non-target action. Note that the rewards are bounded in [0, 1]. We have
m
Cost(A K, H)
ΣΣΣ
(1(0)A # alww) + 1F r(.
(49)
K
(att # n. (s:)mm.
h=1
Hence, the attack cost is bounded by mi[[Lsss H)) S m2 m²R((T)/
I Analysis of the gray-box attacks
I.1 Proof of Theorem
We assume that the agent does not know the attacker's manipulations and the presence of the attacker. The attacker's manipulations on actions are stationary. We can consider the combina- tion of the attacker and the environment MG(S, (m H, {R.)),) new environment
26

---

MG(S, H, (R and the agents interact with the new environment. We define Q: and Vú as the Q-values and value functions of the new environment MG that each agent observes. We first prove that the best response of each agent i towards any policy T-, is T!.
From the mixed attack strategy, we have
Th,n (s, a) = =1aa; = TI, (s) (s, (+)) + P (s)).
(50)
Consider an arbitrary policy л and an arbitrary initial state 81. We have
((s1)
Vi (s1)
1,1
-. x 1,1
(81)
D2 1Q,) --)0))(~((())) ((() + 1=
(())
(s1)
[|a #
+ +P 1 xm (s1 ((1)) P. (.(3(61T((ss))
Bai,
[[ar,1 + (81) (1)((
+ P x (((ls,,
H
=...= ....=E,rAA.
nutb
( (sn ( 2 0.
(51)
Since RE, (sh, TT (sn)) > O. V. x (s1) - V.5 (s1) = holds if and only if n! = n, holds for the states that are reachable under policy -t. We conclude that the best response of each agent i towards any policy T- is л! under the mixed attack strategy. The target policy nt is an NE, CE, CCE under the mixed attack strategy.
Now we prove that the target policy л! is the unique (NE, CE, CCE) under the mixed attack strategy. when every state E S is reachable every step h E [H] under the target policy.
If there exists an CCE x' under the mixed attack strategy, we have [mx (V/11 "(s) (z)) = 0 for any initial state
From 51.. we have that if (-1s) + (-Is) at a reachable state 8, Vei x (31) (
Then
T..= 1,1
((a1)>
V. xm ((s1) > V.A (81). ). x'
not an CCE in this case.
We can conclude that = . for the states that are reachable under policy x'. If every state s E is reachable at every step [H] under the target policy, of is the unique (NE, CE, CCE).
1.2 Proof of Theorem g
We set Rmin min min.es minieimi Ra, (s, (s)). From the definition of the best-in- hindsight regret and (1). we have
K Reg, (K, H) max T
(st)
-V," (sf)
k=1
XT
(s)) V (sf))
K
H
- ( (x)n())))s))) Ran
Eyg A.P
(52)
H
la # n|,n Ra
B
1=1
K
R Rmin
E
Σ
1a # TL (sta(s
-==1
27

---

and
Reg, ( K, H) 2 Lossl (K, H)).
(53)
If the best-in-hindsight regret Reg(K, H) each agent's algorithm bounded by sub-linear bound R() under the mixed attack strategy, then the attack loss is bounded by EE|ssss (K, H)) < mR(T)) Romin-
The mixed attack strategy only attacks agent i when agent chooses non-target action. We have
Cost(K, K H)
Σ
(1 + a + 15 r,,,.))
(54)
m
a (1+
Then, the attack cost is bounded by 2TE[Loss1 (K, H)) S 2mi((T) Rmin.
J Analysis of the black-box attacks
J.1 Proof of Lemma 1
We denote by Q O V² L.k. N Pt TH and R& the observations of the approximate mixed attacker at the beginning of episode k and time step h. As before, we begin with proving that the estimations value functions. We use n to denote the optimal policy that maximizes the attacker's rewards, i.e. V (s) max, V7.1 (s). 1,1
indeed upper and lower bounds of the corresponding Q-values and state
Lemma With probability 1- p. for any (s, a h) and S T. (5, 0f
as 2 (s, a), O
s (s,
(55)
V (s) (s), Vi vith
(56)
Proof. For each fixed k we prove this by induction from H + to h = 1. For the step H + 1,
we have V t = V H+ = Qf = Now, we assume inequality (56) holds for the step By the definition of --vuuu and Algorithm we have
( a) (s)
= R (s, a) - (s, a) + (t PA PA. + (s,
(57)
=PA(V 11+1 Vi.t (s, a) + (R) - R (s,,)sss)) (s. a))
Recall that B(N) = (1V5 + 1), /bg((AA1//////22 By Azuma-Hoeflding inequality, we have that with probability 2PHSAH
log(2SAHT/p)
Ak. TT, T. R/. (s, Ri,a(3,0) $1
(58)
(N)
and
S Slog(2S
Ak < r, (IP) PA)
s H
SH
(59)
(N,
Putting everything together, we have (s, Q7 a) 2 P P (Vi41 (i a) Similarly, 2t (s, a) & (s)
i.411
2 0.
28

---

Now we assume inequality (55) holds for the step h. As discussed above, if inequality (56) holds for
the step h + 1, inequality (55) holds for the step By Algorithm [
we have
(s)) - (s. 2 D (x, 2 (F,((,,77())) V.T (s).
(60)
Similarly, V (s) - (s).
Now, ready to prove Lemma] | By Azuma-Hoeffding inequality, have that with probability
1 2p,
( (Fgi~Po() E Bei [TT vy:
(71((11) <HV
S Slog(2r/1) /p)
(61)
2k
and Vk ST.
Σ
k
Ba-Po() 1(81 = of -Ba
[31 v (01)
s HH
S $log(27 /p)
(62)
2k
k'=1
Thus, for any k ST. T,
B, Po()
V ($1) - V (51)
T3 21 pP(()
Vi.l (81) Vे (81)
+ H V Slog Slog((2/))/222
(63)
<E 5, P6
(11(s)) (s1)
+ 11 /log(227/2/22
According to 61 and
62
we have
E SpS -Vh + H H (10)((22/p)))((1)
(64)
(V - -ii(st))
3H / (log((22/2// + Σ
k=1
We define A AV (s) V f.((s) (s).. (s = o a) (s, a). By the update
equations in Algorithm 1 we have (s) S P/AV (s, a) + +2B(N (s, a)) and (s)
( (s)). We define v AV, AQ ).) From 59 and (66). we have
* <P A (s), at + 2B ( at))
<P x AV h (3) a + 3B + (
(65)
<P & (3) a o + wht + 3B(N at))
By Azuma- Zzema-Hoeffding inequality, we have that with probability 1 p/ Vk ST.
k
Slogg(H /p)
P AVA
a Wharl s HHV
(66)
2k
Since witk
for all k, we have
#+11
H
hr a whail + Σ "
pPk
3B(N (sh, (
k=1 1=1
(3,5)))
S log (og(2HT/p)
log(2SAHT (/p)
(HVS+ + 1)
(67)
2T
2n
(s.a)
S log (2H1/PP)
2H²
1) (SA
2SAT
2T
29

---

and therefore
B s
V (ii(ss) - -Vi + H HV Slog(2T/p)/22H)
-
k=1
(68)
5 log (2Hr/p)
<H²
+ +3H 2ST 10
2T
Since
( (11) + H (1og((2/pp)2(2A)
n| min
E p)((
Σ
(69)
24
E E Po())
V (81) V7.1 (81)
< ())))())
11,1 (81) - Vi (81)
+ H H SVVoog(2//))/22)
(70)
S Slog (log(2HT/p)
SH²
3H -
2r3
$2H (og/
where the last inequality holds when S, H, A 2 2. Similarly,
K
Σ
( (7T1
(71)
J.2 Proof of Theorem
For completeness, we describe the main steps of V-learning algorithm [Jin and the adversarial bandit algorithm in Algorithm 3
2021 in Algorithm
Algorithm 2: V-learning [Jin et al. 2021]
1: For any (x, a, h), (8) +- H + h, (s)s) c (a(s)) + 1/A.
2: for episodes h: = 1, K do
3: receive 81
4: for episodes h = 1,..., H. do
5: take action On ~ mi mT (-(sn), observe reward Th and next state 8
6: == (s)) f (s,. 1.
Va(Sa) +- (1 (1-a,) V V (sa) ar(rh + Vh+i(sn+1) + Bi). 8: Vr(ss) +- min 1 - h, Vn(ss)}
7:
9: TA (+1ah) <- ADV
H-TA T-TA-VAnn --TA--Var(enn))) on (sh, 1ith adversarial
H
bandit.
end for
11: end for
Algorithm 3: FTRL for Weighted External Regret (Jin et al. 2021]
For any E B, (b) <- 1/B.
2: for episode f = 1...., K do
3: Take action by (e(-), and observe loss (b,).
4: (e(b) [bb (0) 71) for all B.
5: (b) x expl-(n//uil Ei= wx)((b)]
6:
end for
We use the same learning rate a; in JJin et al., 2021). We also use an auxiliary sequence { defined in [Jin et al. 2021 based on the learning rate, which will be frequently used in the proof:
a: H 11 0
H +1
I a,), of II (1-ag). az)
(72)
j=it1
30

---

We follow the requirement for the adversarial bandit algorithm used in V-learning, which is to have high probability weighted external regret guarantee follows.
Assumption For any E N and any E
(0, 1), with probability at least 1 - Ó, we have
max Σ (1) (0.4) - t,
(73)
In addition, there exists an upper bound E(B, t, log (1/5) 2 EV== E(B, (B,,,)))(1/)) where (i) E(B, t, (1g6)))) is non-decreasing in B for any 6; (ii) EB,t t, log( 1 1/)) is concave in t for any B,
In particular, it was proved in Jin et al, 2021 that the Dollow-the-Regulriize
(FTRL) algo-
rithm (Algorithm 3 satisfies Assumption with bounds E(B, t, log(1/o)) S O( log (B/3(/
and E(B,t, t, L.BB,,, (1/() I O(v O Log((/)))
By choosing hyper-parameter Wt
Or [II (1-a1))) -as) and =
< Blog Bt ((B,1,00((10))
10 HD/HlllBB///// and
E(B, L, (o/())))) 2 HBI (og(
We use V* N n² to denote the value, counter and policy maintained by V-learning algorithm at the beginning of the episode k. Suppose s was previously visited at episodes k2 ..... k' < at the step h. Set t' such that k² S r and E.' +1 > T.
In the exploration phase of the proposed approximate mixed attack strategy, the rewards are equal to 1 for any state 8, any action a, any agent and any step h. The loss updated to the adversarial bandit update step in Algorithm 2 is equal to A=1
In the attack phase, the expected loss updated to the adversarial bandit update step in Algorithm is equal to
Σ
Σ j=t'+1
H H-PAV s,h+1
(s)
Σ af
-ish
(s).
(74)
H
H
j=t++
Thus, in both of the exploration phase and the attack phase, nt is the best policy for the adversarial bandit algorithm.
By Assumption Tand the adversarial bandit update step in Algorithm 2 with probability at least
1-6 8, for any (s, h)) ESS [H] and any T, we have
VAS H PA
C(A,L,))
De
sh++1
(8) (8) +
Σ
a
-
(s)
H
H
H
j=1
==
j='+11
H - PA VR
a Dz
i,+11
(s) +
Σ
a
Dtt
-i
(s)
H
H
H
/=1
j=t'+1
j=t'41
Ti,n (s, (s))
Σ of (1-
-1-
H
-=
(75)
where log(mHSAK/0))
Note that Rmin minke [a] min minse(m) (s, (s)). We have
H
Σ af (1- (1)
{(A,t,))
(76)
R.nn
$=1+1
Let n = N and suppose & was previously visited at episodes 1at ... k < k at the step h.
Let (s) denote the episode that s was visited in j-th time.
H
((A,nt
dn (1 # n (1)
(77)
Rmin
N=N
31

---

According to the property of the learning rate we have
((A, nh
RA
Σ
H
{(A,J.0)
&
Σ
(1 (1- (1 (78)
Rmin
(+
(o
Then,
40H
/
(1- (T (+
(79)
Rumin
j= N2,
Computing the summation of the above inequality over / and 8, we have
la F =s,n(sh)]
k=T++
NĀ (8)
Σ
(1 (1- 1 (T)
(80)
h= SES j= (1)
40
H5ANK(s)
Rmin
SES
ASKI.
Rymi
In the exploration phase, the loss at each episode up to H. the attack phase, the expected number of episodes that the agents do not follow æ² up to 40 40_m/H HHASKL
According to Lemma the attack loss is bounded by
40 Rmin
E loss( K, H)] S HT +
mV H + 2H'SK /2A//T.
(81)
In the exploration phase, the approximate mixed attack strategy attacks at any step and any episode. In the attack phase, the approximate mixed attack strategy only attacks agent when agent i chooses a non-target action. We have
K
H
Cost( K, H)
(1
+
+ P - (
k=
h=
(82)
H
ΣΣ
1 lati # (1
+1+
k
Then, the attack cost is bounded by
80
E [osst( K, H)] < 2mHr +
VH*ASK.
(83)
Rmin
32

---

For the executing output policy म of V-learning, we have
a (o)
K (s)
Σ (N)
(1
((()) Tihh (s))))
(1)
Σ
2xz(os (L-
- (T(
Σ
Σ
Nx(a) (1 (1-
(T (T)
N=++1j=mM
(+)
(+)
Σ
Ng((s) (1-Teh
(T(
Tik
K
k=T+1 j=1
20
At
2T
Rmmin
K
(84)
The probability that the agents with á do not follow the target policy is bounded by
20mS Ryav
As
K
2rmSH
K
According to Lemma the attack loss of the executing output policy स is upper bounded by
20mS
Ab
2rmSH
V.1 (s1) V4.1(10 (s1) s H
+
+ S/AI/T
(85)
Rmin
K
K
33


Reviews:
[{"review_id": "ZRuKLCkssD", "reviewer": "Reviewer_SPgM", "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. ", "questions": "It would be great if the authors could additionally answer the following clarification questions:\n- Could you explain how these results compare to the ones from [Rangi et al., 2022] in terms of, e.g., proof techniques? \n- 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? \n- 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$?  \n- 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? \n- 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?\n- 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$? ", "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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "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. \n- 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.. \n- 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.  \n- 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. \n\n> - Wang et al;, BACKDOORL: Backdoor Attack against Competitive Reinforcement Learning\n> - Mohammadi et al., Implicit Poisoning Attacks in Two-Agent Reinforcement Learning: Adversarial Policies for Training-Time Attacks\n> - Liu et al., Controllable Attack and Improved Adversarial Training in Multi-Agent Reinforcement Learning\n> - Chen et al., Byzantine-Robust Online and Offline Distributed Reinforcement Learning\n", "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). \n-  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. \n- 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. \n- 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. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> \"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.\"\n\nThank you very much for bringing these very interesting papers to our attention. We will include these recent related works in the revised version.\n\n> \"In terms of results, the paper does not discuss 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).\"\n\nCurrently, we are not able to provide a information-theoretic lower bound, as the attack cost/loss depends on both the Markov game and the agent's learning algorithms. However, we can consider a special case of attacking V-learning to discuss the tightness of the bounds in Theorem 9.  V-learning uses an adversarial bandit method to choose actions, which has a regret lower bound scaling on  $\\Omega(\\sqrt{K})$. Consider a Markov game where the target policy that maximizes the attackers' rewards is the unique {NE, CE, CEE} of the original Markov game. The attacker does not need to attack. In this case, there exists a white-box attacker whose attack cost is $0$ and attack loss scales on $\\Omega(\\sqrt{K})$. The bounds in Theorem 9 scales on $\\Omega({K}^{2/3})$. The proposed black-box attack's cost and loss are sub-linear but are not optimal. It is because that we use a exploration-then-attack method. An adaptive attack method could potentially achieve optimal cost/loss dependency on $\\sqrt{K}$. Finding the optimal attack strategy is an interesting future direction for us to pursue.\n\n> \"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.\"\n\nThe assumption that the target policy receives strictly positive rewards is essential for the success of the gray-box attack. The attack cost/loss of the gray-box attack scale on $O(m \\mathcal{R}(T)/R_{min})$. If the target policy receives zero rewards and $R_{min} = 0$, the gray-box attack does not work.\n\nIn Theorem 1 and 2, we do not limit the learners' model, as the object in Equation (1) only includes the restriction of the post-attacked Markov game. The agents do not need to be an efficient learner. However, the object in Equation (1) implies that the learners are rational and can converge to one of NE, CE or CEE if any exists. As action poisoning only attacks and the reward poisoning only attacks can not always change the target policy to a NE, CE or CEE, so the rational learner can not converge to the target policy. \n\nWe will add these discussions in the revised paper.\n\n> \"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.\"\n\nThanks for the suggestion. We added more experimental results to discuss how the attack loss and cost are affected by the parameters in the author rebuttal pdf file.\n\n> \"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.\"\n\nThe gray-box attack strategies can be directly used in large-scale environments, even in some high-dimensional continuous environment.  However, in the continuous space, the attacker does not change the non-target action to $0$ but to $r_{i.h}*e^{c |a_{i,h}-a^+_{i,h}|}$, in order to avoiding sparse reward. The ideas of the black-box attack strategies still work. However, the exploration phase should resort to some function approximation methods to efficiently explore an approximate target policy. Then the attack phase keeps the same. We will add these discussions to the revised paper. \n\n>  \"Could you explain how these results compare to the ones from [Rangi et al., 2022] in terms of, e.g., proof techniques?\"\n\nWe added more discussion about our work with the existing work. Due to the rebuttal length limit, we put the discussion into the author rebuttal to every reviewers.\n\n> \"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?\"\n\nFor a normal-form game, the method suggested by you will work. However, it does not always work in Markov games. An example is provided in Appendix D.2. The intuitive idea is that reducing the current reward of the non-target action may not impact the agent's choice as the long-term reward of the non-target action could be huge.\n\n> \"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?\"\n\nThe proposed white-box attack strategies are the action poisoning only attacks and the reward poisoning only attacks, which only manipulate the reward or action. The proposed gray-box attack strategy (mixed attack strategy) requires the ability of manipulating the action and reward at the same time. The mixed attack strategy also works in white-box case. However, in some situations where the attacker can only manipulate the reward or action, the mixed attack strategy does not work but the proposed white-box attack strategies work.\n\n> More specifically, could you comment on the tightness of the bounds in Theorem 9, e.g., in terms of horizon?\n\nCurrently, we are not able to provide a formal information-theoretic lower bound, as the attack cost/loss depends on both the Markov game and the agent's learning algorithms. It is an important future direction for us to pursue."}, {"review_id": "fNoJVEAoLg", "reviewer": "Reviewer_YKVp", "summary": "This paper investigates the impact of adversarial attacks on Multi-Agent Reinforcement Learning (MARL) models. The authors propose an attacker who can manipulate rewards and actions to guide the agents into a target policy or maximize cumulative rewards under a specific reward function. The paper presents an adversarial attack model where the attacker aims to force the agents to learn a target policy or maximize cumulative rewards. Loss and cost functions are used to evaluate the effectiveness of the attack, with cost representing the cumulative manipulation and loss measuring the deviation from the target policy or regret compared to the attacker's optimal policy. The attack problem is studied in three settings: white-box, gray-box, and black-box. The paper demonstrates the limitations of action poisoning-only attacks and reward poisoning-only attacks. Certain Markov Games (MGs) are identified where these strategies are inefficient. However, sufficient conditions are provided under which these attacks can efficiently target MARL algorithms. Efficient strategies for action poisoning and reward poisoning attacks are introduced, and their costs and losses are analyzed. Then a mixed attack strategy is proposed in the gray-box setting, and an approximate mixed attack strategy is introduced for the black-box setting. These strategies can force sub-linear-regret MARL agents to choose actions according to the attacker's target policy with sub-linear cost and loss. The impact of the approximate mixed attack strategy on V-learning, a decentralized MARL algorithm, is investigated. No experiments have been done.", "questions": "Some experiments would benefit the paper. It would be great if the authors can resolve my concerns in the weakness.", "limitations": "N/A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality: Firstly, this paper introduces an adversarial attack model specifically tailored for Multi-Agent Reinforcement Learning (MARL) systems. While adversarial attacks in single-agent RL have been studied before, this paper focuses on the challenges and implications of attacks in the context of MARL. The consideration of both action poisoning and reward poisoning, as well as the introduction of a mixed attack strategy, adds originality to the research.\n\nQuality: The analysis considers different attack settings, providing a comprehensive understanding of the impact of adversarial attacks on MARL algorithms. The paper also provides conditions under which the attack strategies can be effective, contributing to the quality of the research.\n\nClarity: The paper is easy to follow. The introduction provides an overview of the problem and motivation, while the contributions are explicitly listed, making it easy for readers to understand what the paper aims to achieve. The attack model, attack settings, and attack strategies are explained in a concise and understandable manner.\n\nSignificance: With the increasing use of MARL in various applications, understanding the vulnerabilities and countermeasures against adversarial attacks is crucial for the safe and reliable deployment of these systems. By investigating the limitations of existing attack strategies and proposing new attack strategies, the paper sheds light on the security aspects of MARL and contributes to the development of more robust and trustworthy MARL algorithms.", "weaknesses": "Limited comparison with existing work: The paper lacks a comprehensive comparison with prior research on adversarial attacks in MARL. While it briefly mentions existing works on attacks in single-agent RL and MARL, it does not provide a detailed comparison or highlight the novelty and differentiation of its proposed attack model and strategies. A more extensive discussion and comparison with related works would strengthen the paper's contribution and contextualize its findings within the existing literature.\n\nNo empirical evaluation: The paper would benefit from an empirical evaluation of the proposed attack strategies. While the analysis provides theoretical insights into the effectiveness of the attack strategies, it lacks practical validation through experiments on real-world or simulated MARL environments. Conducting experiments and presenting empirical results would enhance the credibility and applicability of the proposed attack strategies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> \"Limited comparison with existing work\"\n\nThank you very much for your comment. We will add the following discussion to the revised paper.\n\nAdversarial attacks on single agent RL have been studied in various settings [Behzadan and Munir, 2017, Huang and Zhu, 2019, Ma et al., 2019, Zhang et al., 2020b, Sun et al., 2021, Rakhsha et al., 2020, 2021, Rangi et al., 2022]. Among the existing works on attacks in single-agent RL, the most related paper is [Rangi et al., 2022], which studies the limitations of reward only manipulation or action only manipulation in single-agent RL and proposed an attack strategy  combining reward and action manipulation. There are multiple differences between our work and [Rangi et al., 2022]. First, the MARL is modeled as a Markov game, but the single-agent RL is modeled as a MDP. In Markov game, each agent's action will impact other agents' rewards. Second, the learning object of single-agent RL and MARL is different. The single-agent RL algorithms learn the optimal policy, but MARL algorithms learn the equilibrium. Since the attacks on one agent will impact all other agents and the equilibrium is considered as the agents' learning object, we have to develop techniques to carefully analyze the impact of attacks and the bound of the attack cost. For example, we developed the value function difference decomposition in equations (22)-(27), (29)-(38), (41)-(43), and (51), which build a connection between the value function difference and the number of times that the non-target actions are chosen in MARL setting.\n\n[Ma et al., 2022] considers a game redesign problem where the designer knows the full information of the game and can redesign the reward functions. The proposed redesign methods can incentivize players to take a specific target action profile frequently with a small cumulative design cost.  Ma's work considered the norm-form game but we considered the Markov game. The norm-form game is a simple case of the Markov game with $H = 1$. [Gleave et al., 2020, Guo et al., 2021] study the poisoning attack on multi agent reinforcement learners, assuming that the attacker controls one of the learners. In our work, the attacker is not one of the learners, but an external unit out of the original Markov game. The attacker can poisoning the reward/action of all learners at the same time so that can fool the learners to learn a specific policy. [Wu et al., 2022] studies the reward poisoning attack on offline multi-agent reinforcement learners. The attacker can poisoning the reward of the agents. We considered the online MARL. In offline MARL, the attacker can estimate the underline Markov game from the offline datasets. In online MARL, the attacker may not have the knowledge (reward/transition functions) of the Markov game.\n\n> \"No empirical evaluation.\" \n\nDue to the page limitation, we put the Numerical results in Appendix B. In particular, in Section B.1, we empirically compared the performance of the action poisoning only attack strategy ($d$-portion attack), the reward poisoning only attack strategy ($\\eta$-gap attack) and the mixed attack strategy. We considered two different target policies. In Case 1, any action poisoning only attack and reward poisoning only attack will fail. In Case 2, condition 1 and 2 hold so that $d$-portion attack and $\\eta$-gap attack work.\nFurthermore, in Section B.2, we considered a synthetic environment and empirically compared the performance of the mixed attack strategy and the approximate mixed attack strategy.\n\nIn addition, in the author rebuttal pdf file, we also added more experimental results to discuss how the attack loss and cost are affected by the parameters."}, {"review_id": "L7RsbeiePY", "reviewer": "Reviewer_qHBd", "summary": "This paper presents a novel approach to adversarial attacks in Multi-agent Reinforcement Learning (MARL), offering significant insights into various attack settings.  The authors explore different attack strategies, including reward poisoning, action poisoning, and a combination of both, across various settings: white-box, grey-box, and black-box. The paper's key contribution is the efficient adversarial attack strategy that perturbs both the action and reward of the agents.", "questions": "See above", "limitations": "Authors do not seem to discuss limitations thoroughly.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper addresses a novel and significant problem of adversarial attacks in Multi-agent Reinforcement Learning (MARL) for reward/action poisoning.\n- The paper is  moderately easy to follow. \n- The authors have considered different settings such as white-box, grey-box, and black-box, which adds depth to the study. \n", "weaknesses": "- The related work section of the paper does not seem to cover the literature comprehensively. It would be beneficial for the authors to provide a more thorough review of the existing literature, especially focusing on the works that have addressed similar problems in the past, how they did it (for reward/attack poisoning).\n- The paper lacks numerical results. While the authors have provided some simulation results in the appendix, it would be beneficial to include more numerical results in the main body of the paper to strengthen their arguments. Furthermore, this is a quite practical problem, and it is  beneficial to thoroughly  assess the concepts introduced by the authors by means of numerical simulations.\n- Attack detection is not discussed by the authors.\n-The authors have analyzed the performance of the proposed attack algorithm on V-learning. It would be interesting to see how the proposed black-box strategy performs on other MARL algorithms.\n- It's not clear how tight the bounds proposed by the authors are. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The related work section of the paper does not seem to cover the literature comprehensively. It would be beneficial for the authors to provide a more thorough review of the existing literature, especially focusing on the works that have addressed similar problems in the past, how they did it (for reward/attack poisoning).\n\nThank you very much for this comment. We will add the following discussions to the revised paper:\n\n[Ma et al., 2019] studies reward poisoning attack against batch RL in which the attacker is able to gather and modify the collected batch data. [Rakhsha et al., 2020] proposes a white-box environment poisoning model in which the attacker could manipulate the original MDP to a poisoned MDP. [Behzadan and Munir, 2017, Zhang et al., 2020., Rangi et al., 2022] study online white-box reward poisoning attacks in which the attacker could manipulate the reward signal before the agent receives it. [Sun et al., 2021] proposes a practical black-box poisoning algorithm called VA2C-P. Their empirical results show that VA2C-P works for deep policy gradient RL agents without any prior knowledge of the environment. [Rakhsha et al., 2021] develops a black-box reward poisoning attack strategy called U2, that can provably attack any efficient RL algorithms. [Xu et al., 2021] investigates training-time attacks on RL agents and the introduced attacker can manipulate the environment. [Wang et al., 2021] studies the backdoor attack in two-player competitive RL systems. The trigger is the action of another agent in the environment. They propose a unified method to design fast-failing agents which will fast fail when trigger occurred. [Liu et al., 2022] studies the controllable attack by constraining the state distribution shift caused by the adversarial policy and offering a more controllable attack scheme. [chen et al., 2022] considers a situation that $\\alpha$-fraction of agents are adversarial and can report arbitrary fake information. They design two Byzantine-robust distributed  value iteration algorithms that can identify a near-optimal policy with near-optimal sample complexity. [Mohammadi et al., 2023] studies targeted poisoning attacks in a two-agent setting where an attacker implicitly poisons the effective environment of one of the agents by modifying the policy of its peer. [Ma et al., 2022] considers a game redesign problem where the designer knows the full information of the game and can redesign the reward functions. The proposed redesign methods can incentivize players to take a specific target action profile frequently with a small cumulative design cost. [Gleave et al., 2020, Guo et al., 2021] studies the poisoning attack on multi agent reinforcement learners, assuming that the attacker controls one of the learners. [Wu et al., 2022] studies the reward poisoning attack on offline multi-agent reinforcement learners.\n\n> The paper lacks numerical results.\n\nDue to the page limitation, we put the Numerical results in Appendix B. In addition, in the author rebuttal pdf file, we also added more experimental results to discuss how the attack loss and cost are affected by the environment's parameters. \n\n> Attack detection is not discussed by the authors.\n\nWe agree with the reviewer's comment that we did not consider the attack detection problem, which is certainly very important. \nIn this paper, we assumed that the agents do not know the existence of the attacker. In fact, in the online setting, if the agents have no prior information of the MG, the proposed white and gray box attack is hard to be detected. As we consider the Markov attack strategy in this paper, the post-attack environment under the Markov attack strategy is still a Markov game. Without reference, the agents can not figure out whether the environment they observe is a post-attack environment or an attack-free environment. The proposed black attack may be detected, as the transition probabilities of the post-attack environment change over time.\nThe goal of our paper is to understand and identify the impacts of different adversarial attacks. We hope our work can inspire follow-up work that can detect and mitigate such attacks so that RL models can be used in safety-critical applications.\nIt is an important future direction for us to pursue. We will add these discussions in the revised paper.\n\n> It's not clear how tight the bounds proposed by the authors are.\n\nCurrently, we are not able to give a information-theoretic lower bound, as the attack cost/loss depends on both the Markov game and the agent's learning algorithms. However, we can consider a special case of attacking V-learning to discuss the tightness of the bounds in Theorem 9. V-learning uses an adversarial bandit method to choose actions, which has a regret lower bound scaling on  $\\Omega(\\sqrt{K})$. Consider a Markov game where the policy that maximize the attackers' rewards is the unique {NE, CE, CEE} of the original Markov game. The attacker does not need to attack. In this case, there exists an white-box attacker whose attack cost is 0 and attack loss scales on $\\Omega(\\sqrt{K})$. The bounds in Theorem 9 scales on $\\Omega({K}^{2/3})$. The proposed black-box attack's cost and loss are sub-linear but are not optimal. It is because that we use a exploration-then-attack method. An adaptive attack method could potentially achieve optimal cost/loss dependency on $\\sqrt{K}$. Finding the optimal attack strategy is an interesting future direction for us to pursue."}, {"review_id": "QrkSVX2Bew", "reviewer": "Reviewer_Mdqm", "summary": "This paper proposes a series of novel attacks against MARL under different assumptions. From the theoretical perspective, it then analyzes the efficacy of the proposed attacks.", "questions": "1. Why the proposed assumptions that the attackers can freely alter the target agents' actions and rewards are practical and realistic? \n2. What are the practical suggestions for optimizing the proposed objective functions? \n3. What is the computational cost of solving the proposed attack objective functions?", "limitations": "This paper does not include a section discussing the limitation of the proposed attacks. Given that the paper is mainly about theoretical analysis of attack efficacy. It could include a discussion section (maybe in the appendix) to discuss the potential limitations maybe on the practical side, i.e., how realistic are the assumptions that the attackers can freely manipulate the action and reward? What is the computational cost of solving the proposed attack objective functions? \n\nIn addition, the authors checked the broader impact of the checklist. However, I do not find a (sub)section or paragraph clearly addressing the potential negative social impact.   ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper proposes a series of novel attacks against online MARL and provides a decent theoretical analysis for the efficacy of the proposed attack. This paper lays a theoretical foundation for the adversarial attacks against online MARL. The proposed attacks can be potentially extended by follow-up works to launch practical attacks against MARL systems. The novelty of the problem and the technical depth are enough for a top-tier ML conference. ", "weaknesses": "I do not idenitfy any critical weakness in the proposed technique and the corresponding theoretical analysis. As a theoretical paper, it is a little bit over to ask questions about the practical perspective.  However, as an attack paper, it is somewhat important to discuss the practicability of the proposed attacks. As such, I would suggest the authors add such a discussion related to the proposed technique. For example, the authors could provide some suggestions for practitioners to solve the proposed objective functions, which could be hard to optimize. In addition, what would be the computational cost for the proposed objective functions? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Why the proposed assumptions that the attackers can freely alter the target agents' actions and rewards are practical and realistic?\n\nIn some applications of RL models, action decisions and reward signals may need to be transmitted over communication links. When data packets containing the reward signals and action decisions etc are transmitted through the communication links, an attacker can implement adversarial attacks by intercepting and modifying these data packets. Hence, the proposed adversarial attacks are possible and realistic.\n\nAs the first step of understanding the potential risks of different adversarial attacks on online MARL, we did not limit the attacker's abilities. The attackers can freely alter the target agents' actions and rewards. There may exist some situation that the attacker can not freely alter any actions and rewards and can only manipulate part of actions or rewards. Considering limited attacker and finding the defending algorithms is an important future direction for us to pursue.\n\n> What are the practical suggestions for optimizing the proposed objective functions?\n\nIn the practical side, the proposed mixed attack strategy works for many realistic problems. The mixed attack strategy does not require any information about the underline Markov game. It is simple yet effective. As the first step of understanding the impact of adversarial attacks on online MARL, our analysis is focused on the tabular case. The proposed mixed attack strategy can work in some realistic problems where the action space is continuous. In the continuous action problems, the attacker does not aim to force the agents to learn the exactly target policy but some policies nearby the target policy. The proposed mixed attack strategy still works. For example, in the continuous space, the attacker can change the non-target action to $r_{i.h}*e^{c |a_{i,h}-a^+_{i,h}|}$ instead of $0$, in order to avoiding sparse reward. Then the agents will still learn a policy that is close to the target policy.\n\n> What is the computational cost of solving the proposed attack objective functions?\n\nFor the proposed black-box attack strategy (the approximation mixed attack), the computational cost is $O(S^2AH\\tau+mKH)$. The proposed algorithm will compute the $Q$-values for each visited action-state pair at every steps and every episodes in the exploration phase. The computation of $Q$-value costs $O(S)$. Thus, the total computational cost in the exploration phase is $O(S^2AH\\tau)$. In the attack phase, the attacker only need to change the action and the reward for each agent so that the computational cost in the attack phase is $O(mKH)$. We will add this discussion to the revised paper."}]

Author rebuttal:
We thank the reviewers for their valuable feedback, suggestions, and time invested. Here, we answer the reviewers' common concerns.

**Related works.** Due to the page limit of the main paper, we do not provide a comprehensive comparison with prior research on adversarial attacks. We will add the following discussion to the revised paper.

Among the existing works on attacks in single-agent RL, the most related paper is [Rangi et al., 2022], which studies the limitations of reward only manipulation or action only manipulation in single-agent RL and proposed an attack strategy  combining reward and action manipulation. 

There are multiple differences between our work and [Rangi et al., 2022]. First, the MARL is modeled as a Markov game, but the single-agent RL is modeled as a MDP. In Markov game, each agent's action will impact other agents' rewards. Second, the learning object of single-agent RL and MARL is different. The single-agent RL algorithms learn the optimal policy, but MARL algorithms learn the equilibrium. Since the attacks on one agent will impact all other agents and the equilibrium is considered as the agents' learning object, we have to develop techniques to carefully analyze the impact of attacks and the bound of the attack cost. For example, we developed the value function difference decomposition in equations (22)-(27), (29)-(38), (41)-(43), and (51), which build a connection between the value function difference and the number of times that the non-target actions are chosen in MARL setting.

Here, we discuss the related work on the adversarial attacks on single MARL.  [Ma et al., 2019] studies reward poisoning attack against batch RL in which the attacker is able to gather and modify the collected batch data. [Rakhsha et al., 2020] proposes a white-box environment poisoning model in which the attacker could manipulate the original MDP to a poisoned MDP. [Behzadan and Munir, 2017, Zhang et al., 2020., Rangi et al., 2022] study online white-box reward poisoning attacks in which the attacker could manipulate the reward signal before the agent receives it. [Sun et al., 2021] proposes a practical black-box poisoning algorithm called VA2C-P. Their empirical results show that VA2C-P works for deep policy gradient RL agents without any prior knowledge of the environment. [Rakhsha et al., 2021] develops a black-box reward poisoning attack strategy called U2, that can provably attack any efficient RL algorithms. [Xu et al., 2021] investigates training-time attacks on RL agents and the introduced attacker can manipulate the environment.

Here, we discuss the related work on the adversarial attacks on MARL. [Ma et al., 2022] considers a game redesign problem where the designer knows the full information of the game and can redesign the reward functions. The proposed redesign methods can incentivize players to take a specific target action profile frequently with a small cumulative design cost.  Ma's work considered the norm-form game but we considered the Markov game. The norm-form game is a simple case of the Markov game with $H = 1$. [Gleave et al., 2020, Guo et al., 2021] study the poisoning attack on multi agent reinforcement learners, assuming that the attacker controls one of the learners. In our work, the attacker is not one of the learners, but an external unit out of the original Markov game. The attacker can poisoning the reward/action of all learners at the same time so that can fool the learners to learn a specific policy. [Wu et al., 2022] studies the reward poisoning attack on offline multi-agent reinforcement learners. The attacker can poisoning the reward of the agents. We considered the online MARL. In offline MARL, the attacker can estimate the underline Markov game from the offline datasets. In online MARL, the attacker may not have the knowledge (reward/transition functions) of the Markov game.  [Wang et al., 2021] studies the backdoor attack in two-player competitive RL systems. The trigger is the action of another agent in the environment. They propose a unified method to design fast-failing agents which will fast fail when trigger occurred. [Liu et al., 2022] studies the controllable attack by constraining the state distribution shift caused by the adversarial policy and offering a more controllable attack scheme. [chen et al., 2022] considers a situation that $\alpha$-fraction of agents are adversarial and can report arbitrary fake information. They design two Byzantine-robust distributed  value iteration algorithms that can identify a near-optimal policy with near-optimal sample complexity. [Mohammadi et al., 2023] studies targeted poisoning attacks in a two-agent setting where an attacker implicitly poisons the effective environment of one of the agents by modifying the policy of its peer. 

**Experimental results**  Due to the page limitation, we put the Numerical results in Appendix B. In particular, in Section B.1, we empirically compared the performance of the action poisoning only attack strategy ($d$-portion attack), the reward poisoning only attack strategy ($\eta$-gap attack) and the mixed attack strategy. We considered two different target policies. In Case 1, any action poisoning only attack and reward poisoning only attack will fail. In Case 2, condition 1 and 2 hold so that $d$-portion attack and $\eta$-gap attack work. Furthermore, in Section B.2, we considered a synthetic environment and empirically compared the performance of the mixed attack strategy and the approximate mixed attack strategy. In addition, in the author rebuttal pdf file, we also added more experimental results to discuss how the final attack loss and cost (after $10^6$ episodes) are affected by the parameters $R_{min}$. Noted that the attack loss in mix-attack strategy (gray-box) is the count of the non-target arm defined in Loss1, but the attack loss in approximation mix-attack strategy (black-box) is the regret of the attacker's reward defined in Loss2.

Meta-review: In this paper the authors investigate adversarial poisoning attacks against online multi-agent RL algorithms, where the attacker can either manipulate reward or action feedbacks. 

In particular, they look at three different attack scenarios: white-box, gray-box and black-box attacks. The authors first show that action-only or reward-only poisoning attacks are not efficient in gray-box and back-box settings. On the other hand, for white-box case, the authors provide sufficient conditions that enable successful manipulations. For all three attack scenarios, they demonstrate that the combination of action and reward poisoning attacks can always succeed, and provide upper bounds on the expected cost and loss of proposed attack strategies.

After the rebuttal phase, perhaps the only remaining concern is that the numerical results were deferred to the appendix, and several reviewers suggested to move some of the main numerical evaluations into the main paper, subject to acceptance and space availability. I find this concern to be minor. However, I also strongly recommend the authors to revise the paper to comply with this suggestion, should the paper be accepted.
Decision: Accept (poster)