What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?
Authors: Songyang Han
Sanbao Su
Sihong He
Shuo Han
Haizhao Yang
Shaofeng Zou
Fei Miao
Venue: Accepted by TMLR ()

Abstract: Various methods for Multi-Agent Reinforcement Learning (MARL) have been developed with the assumption that agents' policies are based on accurate state information. However, policies learned through Deep Reinforcement Learning (DRL) are susceptible to adversarial state perturbation attacks. In this work, we propose a State-Adversarial Markov Game (SAMG) and make the first attempt to investigate different solution concepts of MARL under state uncertainties. Our analysis shows that the commonly used solution concepts of optimal agent policy and robust Nash equilibrium do not always exist in SAMGs. To circumvent this difficulty, we consider a new solution concept called robust agent policy, where agents aim to maximize the worst-case expected state value. We prove the existence of robust agent policy for finite state and finite action SAMGs. Additionally, we propose a Robust Multi-Agent Adversarial Actor-Critic (RMA3C) algorithm to learn robust policies for MARL agents under state uncertainties. Our experiments demonstrate that our algorithm outperforms existing methods when faced with state perturbations and greatly improves the robustness of MARL policies. Our code is public on https://songyanghan.github.io/what_is_solution/.

Published in Transactions on Machine Learning Research (01/2024)
What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?
Songyang Han
songyang.harr hon Suconn.eeii
School of Computing University of Connecticul Sony Al
Sanbao Su
sanbuo, su www.oooo.nnccmmmmmmmmm eduu
School of Computing University of Connecticut
Sihong He
sshong.he@uconre edu
School of Computing University of Connecticut
Shuo Han
hanshuo@uic.ett edu
Department of Electrical and Computer Engineering University of Illinois Chicago
Haizhao Yang
hayang edu
Department of Mathematics and Department of Computer Science University of Moryland College Park
Shaofeng Zou
szou3@buuffalo.cd edu
Deportment of Electricnl Engineering Department of Computer Science and Engineering University at Buffalo, The State University of New York
Fei Miao
fei. fei.miao wacoono edu
School of Computing University of Connecticul
Reviewed on OpenReview: https: openreview. net/ forun? id= HyWHHg
Abstract
Various methods for Multi-Agent Reinforcement Learning (MARL) have been developed with the assumption that agents' policies are based on accurate state information. However, policies learned through Deep Reinforcement Learning (DRL) are susceptible to adversarial state perturbation attacks. In this work, we propose a State-Adversarial Markov Game (SAMG) and make the first attempt to investigate different solution concepts of MARL under state uncertainties. Our analysis shows that the commonly used solution concepts of optimal agent policy and robust Nash equilibrium do not always exist in SAMGs. To circumvent this difficulty, we consider maximize the worst-case expected state value. We prove the existence of robust agent policy for finite state and finite action SAMGs. Additionally, we propose Robust Multi-Agent Adversarial Actor-Critic (RMA3C) algorithm to learn robust policies for MARL agents under state uncertainties. Our experiments demonstrate that our algorithm outperforms existing methods when faced with state perturbations and greatly improves the robustness of MARL, policies. Our code is public on nttps://songyant github. 1o/what. is solution/
solution concept called robust agent policy, where agents aim to

---

Published in Transactions on Machine Learning Research (01/2024)
1 Introduction
Mueti-Agent Reinforcement Learning (MARL)) has been successfully used to solve problems such as multi-robot coordination (Hüttenrauch & Sošić 2017), resource management (Pretorius et al.
2020). etc. However, Deep
Reinforcement Learning (DRL) policies vulncrable to adyersarial state perturbation attacks [Behzadan &
Munir 2017 Pattanaik & Tang 2017 Huang et al. 2017 Lin et al.] 2017 Xiao el al.
2019 Even small changes to the state can lead to drastically different actions (Huang et al., 2017 Lin et al. 2017).
To address
this, it is important to develop robust policies that can handle adversarial state perturbations. An example of this is shown in Fig. where agents need to cooperate and avoid collisions while occupying landmarks.
(a) with no adversarial state, the agents are able target different landmarks, but (b) with adversarial state perturbations, agents head in the wrong direction.
True landmark state X Perturbed state for agent
Perturbed state for agent
Agent
Agent 2
Uncertainty set
Adversary
a) Cooperative Navigation
b) State Perturbations
b) Robust Agent Policy
Agent 1
Agent
landmarks
4
Agent 1
2
2
Agent
Agent 2
Agent
The agents' goal is to occupy and cover all landmarks, requiring cooperation to decide which landmark to cover. Figure a) illustrates the optimal target landmark for each agent without state perturbation. However, in figure b), an adversary perturbs the state observation of agents, causing agents to head in the wrong direction and leaving landmark 1 as uncovered. Our work demonstrates that traditional agent policies can be casily corrupted by adversarial state perturbations. To counter this, we propose a robust agent policy that maximizes average performance under worsl-case state perturbations.
Figure 1:
The adversarial state perturbation problem cannot be fully understood using existing research on the Partially Observable Markov Decision Process (POMDP) or Decentralized Partially Observable Markov Decision Process (Dec-POMDP) (Oliehoek al. 2016 Lerer et al. 2020), as the conditional observation probability cannot capture the worst-case uncertainty under adversarial attacks. Adversarial perturbations have greater impact on an agent's policy than random noise (Kos & Song 2017 Pattanaik al., 2018). However, due to the complexity of interactions among agents and adversaries, it remains challenging to formally analyze the existence of optimal or equilibrium solutions under adversarial state perturbations in MARL. Therefore, it is essential to study the fundamental properties of MARL under adversarial state perturbations.
To the best of our knowledge, we make the first attempt to investigate different solution concepts of robust MARL under adversarial state perturbations. We formulate State-Adversarial Markov Game (SAMG) study the properties and solution concepts of MARL under adversarial state perturbations. We prove that state-robust totally optimal agent policy or robust. lotal Nash equilibrium does not always exist in such scenarios. Instead, we consider new solution concept, the robust agent policy, and prove its existence for finite state and action spaces. We design an algorithm, called Robust Multi-Agent Adversarial Actor-Critte (RMA3C), to train robust policies for all agents under adversarial state perturbations. The algorithm uses a Gradient Descent Ascent (GDA) optimizer to update each agent's and adversary's policy network. Results from our experiments show that the proposed RMA3C algorithm improves the robustness of the agents" policies compared existing MARL methods.
In summary, the main contributions of this work are:
2

---

Published in Transactions on Machine Learning Research (01/2024)
We study the fundamental properties of MARL under adversarial state perturbations and prove that widely used solution concepts such as optimal agent policy or robust Nash equilibrium do not always exist.
We consider new solution concept, robust agent policy, where each agent aims to maximize the worst-case expected state value. We prove the existence of a robust agent policy for SAMGs with finite state and action spaces. We propose a Robust Agett Adversarial Actor-Critàs (RMA3C) algorithm to solve the challenge of training robust policies under adversarial state perturbations based on gradient descent ascent algorithm.
We empirically evaluate our proposed RMA3C algorithm. Our algorithm outperforms baselines with random or adversarial state perturbations and improves agent policies' robustness under state uncertainties.
2 Related Work
Multi-Agent Reinforcement Learning (MARL) The MARL has long history in the AT field (ittman
1994 Hu et al. 1998 Busoniu et al. 2008). Recent works have been investigated to encourage the collaboration
of the agents by assigning rewards appropriately, such as a value decomposition network (Sunchag et al., 2018 Rashid et al. 2020 Su et al. 2021 subtracting a counterfactual baseline (Foerster & Farquhar 2018 or an implicit method (Zhou al. 2020). Multi-Agent Deep Deterministic Policy Gradient (MADDPG proposes a centralized Q-function to alleviate the problem caused by the non-stationary environment (Lowe et al. 2017). The scalability issue of MARL can be alleviated by adding attention to the critic (Iqbal & Sha 2019), using neighbor information (Qu et al. 2020), or using V-learning (Jin et al. 2021)_ The "team stochastic game" (Muniraj et al. 2018 Phan et al.
2020: splits the MARL agents into two teams to compete.
However, during training, all methods assumne that agents get the true state value. None of the recent MARL advances specifies how to deal with perturbed state values by malicious adversaries.
Robust Reinforcement Learning Most existing robust MARL works focus on uncertainties in reward, transition dynamics, and training partners' policies, while our work focuses on uncertainties the state. Robust reinforcement Icarning can be traced back to Morimoto & Doyal (2005) in the single-agent setting. With the advent of deep learning techniques, the robust MARL has been recently studied considering different.
types of uncertainties such as reward (Chen & Bowling
2012: Zhang et al. 2020b). transition dynamics (Zhang 2020b Sinha et al. 2020 Hu et al. 2020 Yu et al. 2021
Wang et al. 2023), training partner's 's 2019 van der Heiden et al. 2020 Sun et al. 2021 2022). The work in (Zhang et al. 2020b) considers the robust equilibrium of multi-agents with reward
et al.
type
Shen & How 2021), training partners' policies (Li et al.
uncertainties where agents can access true state information at each stage. The work in [Shen & How 20021 considers uncertain training partner's type (e.g. adversary, neutral, or leammate) to the protagonist in two-player scenarios. The M3DDPG algorithm extends the MADDPG get robust policy for the worst situation by assuming all the training partners adversaries [Li et al. 2019). However, none of the above MARL works consider the state perturbations.
For adversarial state perturbations, there are some works Mandlekar et al. 2017 Pinto et al. 2017 Pattanaik
ct al.) 2018: Zhang et al., 2020a; 2021 Liang et al.] 2022) considering a robust policy in single-agent reinforcement learning. Though the work Lin et al.) 2020a) studies state perturbation, only one single agent's state observation can be perturbed their MARL. The work (He et al., (023) shows Nash equilibrium exists under a specific condition (bijective mapping for adversary policies). However, in this work, we show the Nash equilibrium is not good solution concept it can be corrupted by state perturbation adversaries. We also propose a new robust agent policy concept for state-adversariag MARL that is proven to exist.
3 State Adversaial Markov Game (SAMG)
We formulate Stato-Adversarial Markov Game (SAMG) G = (N,S,A,r, PerP, (rPr(s)) with n agents joint action is (at "....""""" A, A A ... x A". The global joint state is E S. The probability distribution of the
the agent set N {1,...,n) n). Each agent is associated with an action a² E A'. The global
3

---

Published in Transactions on Machine Learning Research (01/2024)
initial state is Pr(su). All agents share stage-wise reward function : S A R. We consider that each agent is associated with an adversary shown in Fig. 2 Each adversary decides a perturbed state p² E & for the corresponding agent as the agent's 's perturbed knowledge or observation about the global state. We denote the joint perturbed state as p : [==kkke We consider the admissible perturbed state as a task-specific "neighboring" stale of 8, e.g. the bounded sensor measurement errors, to model the challenges of getting accurate states for multi-agent systems like connected and autonomous vehicles and multi-robots systems (Liu) ett al., 2021 Kothandaraman al. 2021 ) To analyze realistie problem, the power of the state perturbation should also be limited (Everett et al., 2021 Zhang et al., 2020a). We define an admissible perturbed state set P. to restrict the perturbed state only to be within a predefined subset of states such that E P.::
Definition 3.1 (Admissible Perturbed State Set). We consider the set of admissible perturbed state for agent i at state 8 as P C S. Denote the joint admissible perturbed state set at state 8 as P. == P1 x. x... x P
Note that the true state is included in the admissible perturbed state set, i.e, 8 E P; for any i N. For example, consider 2-agent 3-state system with S {ss, 82, $3}. When the current true state 81 for both agents, adversary perturbs agent I's state observation within Pa, $2}; adversary perturbs agent 2's state observation within P? {81, $3).
Observation of
Perturbed
p1-x' (e'
Observation Function
Adversary
Agent 1
Agent 1
:
:
- (p*|s)
Observation Function
Adversary
State St
Agent n
State St
Agent n
Reward Tt
Reward nt
Action af-n' (u
Action af (d'lp')
Ft+1
Vits
Environment
Environment
15tt1
18411
SAMG
Dec POMDP
Comparison between Dec-POMDP and SAMG. In Dec-POMDP, the observation probability function is fixed, and it will not change according to the change of the agent policy. However, in SAMG the adversary policy is not a fixed policy, it may change according to the agents' policies and always select the worst-case state perturbation for agents. In SAMG, each agent is associated with an adversary to perturb its knowledge or observation of the true state. Agents want to find a policy т to maximize their total expected return while adversaries want to find a policy X to minimize agents' total expected return.
Figure 2:
The state perturbation reflects the state uncertainty from the perspective of each agent, but does not change the true state of multi-agent systems. The state transition function is p S x A- A(S), where A(S) is a probability simplex denoting the set of all possible probability measures on S. The state still transits from the true state to the next state. Fach agent is associated with a policy n' : S A(A*) to choose an action a' E A given the perturbed state p². Note that the input of T' is the perturbed state p¹. The perturbed state affects each agent's 's action. The set A(A²) includes all possible probability measures on A'. We use π = (T' .??....,T?) to denote the joint agent policy.
The adversary policy, i.. the state perturbation policy, associated with agent i x'(+s) S A(P!), where the input of x is the true state E S. The power of the adversary is limited by the admissible perturbed state set P. We denote the joint adversary policy as X xx, ..... .2....,"),. x".. The agents want to find a policy a to maximize their total expected return while adversaries want to find a policy x to minimize the agents' total expected return. The total expected return is E is a discount. factor.
t0= 2'r,41 4z)lsu, ar ~ (T-Ppt) Pt ~ x(:1s()] where
Our SAMG problem cannot be solved by the existing work for single-agent RL with adversarial state perturbations (Mandlekar et al.) 2017 Pattanaik et al., 2018 Zhang al. 2020a 2021 Liang et al. 2022). Each agent's 's action in SAMG is selected based on its own perturbed state observation and the state knowledge
4

---

Published in Transactions on Machine Learning Research (01/2024)
State-of-the-Aie Solution Concepts
State Value Function (Equation 1)
Robust State Value
Function (Definition 4.4)
New Solution Concepts
Maximize State Value
Uniqueness Theorem 4.5;
Worst Case Expected State Value (Definition 4.8)
Maximize
Robust Agent Palicy (Definition 4.9)
Agent Unilsterally
Optimal Agent Policy (Definition 4.2)
Robust Nash Equilibrium (Definition 4.6)
Existence of Robust Agent Policy (Theorem 4.11)
Equivalent to a Maximin Problem (Theorem 4.10)
Non-existence (Theorem 4.3)
Non-existence (Theorem 4.7)
Figure 3: Solution concepts for the SAMGs. We first examine the widely used concepts (optimal agent policy and robust Nash Equilibrium) and demonstrate their non-existence under adversarial state perturbations. In response, we consider new objective, the worst-case expected state value, and new solution concept, the robust agent policy.
of each agent can be different after adversarial perturbations, so the SAMG problem cannot be solved by the above single-agent RI. where the agent has only one state observation at each stage.
Our SAMG problem cannot be solved by the existing work in the Decentralized Partially Observable Markov Decision Process (Dec-POMDP) (Bernstein et al., 2002 Olichock et al. 2016) as shown in Fig. In contrast, the poliey in SAMG needs to be robust under a set of admissible perturbed states. The adversary aims to find the worst-case state perturbation policy to minimize the MARL agents' total expected return, but the Dec-POMDP cannot characterize the worst-case state perturbations. Moreover, agents usually cannot get the true state in Dec-POMDP, while in SAMG, the true state s is known by the adversaries. Adversaries can take the true state information and use it to select state perturbations for the MARL agents. The following proposition 3.2 shows that under a fixed adversarial policy, the SAMG problem becomes a Dec-POMDP. However, in SAMG the adversary policy is not fixed policy, it may change according to the agents' policies (see Theorem 4.1 for detail) and always select the worst-case state perturbation for agents. The proof of proposition 3.2 is in Appendix A. We also give two-agent two-state SAMG that cannot be solved by
Dec-POMDP in Appendix A
Proposition 3.2. When the adversary policy is a fixed policy, the SAMG problem becomes Dec- POMDP OOiehock et al.] (0166).
Proposition 3.3. When the adversary policy is a fixed bijective mapping from S to S the SAMG problem becomes Markov game.
Additionally, our SAMG problem cannot be solved by existing methods for robust Markov games considering the uncortaintics from reward (Chen & Bowling 2012 Zhang et al.] 2020b), transition dynamics (Zhang et al,
2020b Hu al.] 2020 Sinha et al. 2020 Yu et al., 2021 Wang et al. 2023 training partner's policies (Li
et al. 2019 van der Heiden al. 2020). These methods are not applicable to our problem because the
agents do not have access to the true state information after adversarial perturbations.
4 Solution Concepts
In this section, we delve into the solution concepts of the SAMG. We formally define key concepts such an optimal adversary policy, state-robust totally optimal agent policy, and robust total Nash equilibrium. However, we also demonstrate that under an optimal adversary policy, the existence optimal agent policy or robust total Nash equilibrium is not guaranteed as they can easily corrupted by adversarics. Therefore, we introduce a new objective, the worst-case expected state value, and prove that there exists robust. agent policy to maximize it. A concept diagram of this section is shown in Fig. 3
state-robust totally
We first introduce the widely used state value function concept for our proposed SAMG as follows:
V8 Vr = Ba pp))
x ( 0z)(s0
(1)
5

---

Published in Transactions on Machine Learning Research (01/2024)
where y is the discount factor.
4.1 Optimal Adversary Policy
For fixed agent policy n; define the worst-case state value function V under π by
(s)) min (s)
(2)
X
for all 8 E S. An adversary policy x" said be optimal against an agent policy x if
Vaxx (s) (s)
(3)
for all s S S. The following proposition shows the existence of an optimal adversary for an SAMG.
Proposition (Existence of Optimal Adversary Policy.). Given an SAMG, for any given agent policy, there erists on optimal adversary policy.
The key process of the proof in Appendix B.4 is constructing an MDP for the adversary where the adversary gets the negative of the agent reward. Since for MDP with finite state and finite action spaces, there always exists an optimal policy [Theorem 6.2.10 in Puterman (2014)); an optimal adversary policy of the corresponding SAMG always exists as well.
4.2 State-robust Totally Optimal Agent Policy
An optimal adversary policy is very powerful and it can easily corrupt the MARL agents' policies through state perturbations. We first define state-robust totally optimal agent policy as follows:
Definition 4.2 (State-robust Totally Optimal Agent Policy). An agent policy x' is state-robust. totally optimal agent policy if (s) 2 (s(s) for any π and all S.
In the following theorem, we show that a statc-robust totally optimal agent policy x² does not always exist for SAMGs under an optimal state perturbation adversary.
Theorem 4.3 (Non-existence of State-robust Totally Optimal Agent Policy). A state-robust lolally optimal agent policy does not always exist for SAMGs.
The proof in Appendix B.5 is done by constructing counterexample where there is no optimal policy for the agents. A stale-robust totally optimal agent policy is expected to maximize the state value for all states. However, under the adversarial state perturbations, sometimes agents have make trade-offs between different state values and no agent policy can maximize all the state values.
4.3 Robust Total Nash Equilibrium
Then we look at the widely-usod Nash cquilibrium concept in MARL for SAMGs. Nash oquilibrium is used to describe policies where agent wants to deviale unilaterally. If an agent deviates from Nash equilibrium, its total expected return won't 't increase. Denote the agent policies and adversary policies of all other agents and adversaries except agent i and adversary i as π and x respectively. Before giving the definition of a robust total Nash equilibrium, we first show that there exists unique robust state value function for agent given any -- and -
Definition 4.4 (Robust state value function), A state value function V - iS + R for agent given -1 and x à is called a robust state value function if for all S,
Σ ((pls) PEP.
aEA Em(alp) r(s,a)+ + a Vi
V - max min X
s'ES
Theorem 4.5 (Existence of Unique Robust State Value Function). For an SAMG with finite state and fonile action spaces, for any E N, given any -h and x of other agents and adversories except agend

---

Published in Transactions on Machine Learning Research (01/2024)
and adversary i, there erists a unique robust state value function V -x : - R for agent such that for all E S,
V F xxx (6) max min
Σ PEP.
x(els)
Σ t(app) (1(6,0)+ +7 Vi aEd
S'ES
The proof is based on the contraction mapping properly and Banach's fixed point theorem in Appendix C.1 The theorem could also follow from viewing the SAMG an extensive form game under imperfect recall and applying the approaches used to analyze those games Chen & Bowling 20122)
Based on the well-defined robust state value function, robust total Nash equilibrium is defined considering each agent is associated with an adversary that tries to minimize its total expected return.
Definition 4.6 (Robus Total Nash Equilibrium). For an SAMG, the policy (x"; is robust total Nash equilibrium if for all 8 E S and all E N and all o and x", it holds that
xx (s) S xx I V --",,---,"-" -x (s).
(4)
where -' and x denotes the agent policies and adversary policies of all the other agents except agent i, respectively.
Definition 4.6 shows that n² is in a robust total Nash equilibrium if cach agent's policy a robust best response to the other agents' policies under adversarial state perturbations. When agent is calculating its robust best response, it assumes a worst-case perspective of the state perturbations.
Theorem 4.7 (Non-existence of Robust Total Nash Equilibrium). For SAMGs with finite state and finite action spaces, the robust total Nash equilibrium defined in Definition 4.6 does not always erist.
The proof in Appendix C.3 is done by constructing counterexample. For any state s E S, there exists stage-wise equilibrium among the agents and adversaries (See the proof for stage-wise equilibrium in Theorem C.6 in Appendix C.2 However, due to the uncertainty of the true state under adversarial state perturbations, it is possible that the stage-wise equilibrium in one state conflicts with the stage- wisc equilibrium in another state. As a result, the agents may be required to make trade-offs between different. states, making it impossible to find an equilibrium that holds for all states.
4.4 Robust Agent Policy
The state-robust totally optimal agent policy and robust total Nash equilibrium concepts do not always exist in our SAMG problem according to the above non-oxistence analysis. To circumvent this difficulty, we consider another solution concept. which each agent adopts policy (hereafter referred to as a robust agent policy) that maximizes the reward under the worst-case state perturbation. We further show that a robust policy always exists for all agents. We first introduce a new objective for SAMGs, the worst-case expected state value:
Definition 4.8 (Worst-case Expected State Value). The worst-case expected state value under the optimal state perturbation adversary is: Reg)))((u) [V()))] where Pr(sp) is the probability distribution of the initial state.
To account for the fact that a policy is not able to maximize all state values in SAMG, we can use the probability of each state as a measure of its importance, and balance the values of different states. The worst-case expected state value is calculated by taking a weighted sum of all state values based on their initial state distribution. The agent policy that aims to maximize this worst-case expected state value is referred to as robust agent. policy.
Definition 4.9 (Robust Agent Policy). An agent policy =² that maximizes the worst-case expected state value is called robust agent policy:
x² arg max E Bgo [V=(s))]
(5)
7

---

Published in Transactions on Machine Learning Research (01/2024)
The following theorem shows finding robust agent policy is equivalent to solving maximin problem.
Theorem 4.10. Finding an agent policy æ to mazimize the worst-cose case expected state value under an optimal adversory for is equivalent to the marimin problem: max, minx E. Pr(ss)V=xx(50)
In the following theorem, we show the existence of a robust agent policy for finite state and finite action spaces.
Theorem 4.11 (Existence of Robust Agent Policy). For SAMGs with finite state and finite action spaces, there ezists robust agent policy to marimize the worst-case expected state value defined in Definition 4.8
The proof in Appendix C.4 is based on the Weierstrass M-test (Rudin et al. 1976. uniform limit theo- rem [Rudin al. 1976), and the extreme value theorem. Different from the delinitions of the state-robust. totally optimal agent policy and robust total Nash equilibrium, the worst-case expected state value objective does not require the optimality condition to hold for all states. Agents won't get stuck in trade-offs between different states, therefore, we can find a robust agent policy to maximize the worst-case expected state value for the SAMG problem.
The robust agent policy, while motivated in specific instances of non-existence theorems, is designed to offer broader applicability. The significance of the new solution concept lies in providing alternative solutions where traditional methods may falter or be inapplicable. This versatility is crucial in advancing the field, particularly in complex scenarios where standard solutions are inadequate.
Multi-Agent Adversarial Actor-Critic (RMA3C) Algorithm In general, it is challenging to develop algorithms that compute optimal equilibrium policies for MARL under uncertainties (Zhang et al.) 2020b] 2021). We design a RMA3C Algorithm based on our theoretical analysis above. Each agent has one critic network, one actor network x' and one adversary network x'. The critic Q takes in the true global state and global action during the training process. It returns a Q-value denoting the total expected return given 8 and a. We use Gradient Descent Ascent (GDA) optimizer (Lin el al. (020b) to update parameters for each agent's actor network and adversary network for the maximin problem max, miny Es, Pr(so) (5o) in Theorem 4.10 A detailed introduction for the RMA3C and pscudocode is included in Appendix D
Cooperative navigation
Exchange target
Keep-awe away
-7.
400
-50
-10.0
-150
mC0m caloate (eword
meen s00800 reweard
200a aploado coward
-12.5
-300
-15.0
-55
-600
-17.5
goriin
Algrrthm
-650
MADDAO
-200
VADCPI
-20.0
HAZDYG
MADOIG with
-22.5
-750
MEDOPG with noton
MSSUINS with
noha
-250
MIDERG WIth nome
M.SEPR with e
-25.0
NAGGRO WITH noRe
MAUUPO WILL 1
MIDONG IotS
-200
500
-27.5
episodelk]
episode(k)
episodellk
Figure 4: Our RMA3C algorithm compared with several bascline algorithms in training. The results show that our RMA3C algorithm outperforms the baselines, achieving higher mean episode rewards and greater robustness to state perturbations. The baselines were trained under either random state perturbations or a well-trained adversary policy x" (adversaries that are trained for the maximun training episodes in RMA3C). Overall, our RMA3C algorithm achieved up to 58.46% higher mean episode rewards than the baselines.
5 Experiments
To demonnstrae the effectiveness of our algorithm, we utilize the multi-agent particle environments developed in Lowe et al.] (2017) which consist of multiple agents and landmarks in a 2D world. The host machine adopted in our experiments is server configured with AMD Ryzen Threadripper 2990WX 32-core processors and four Quadro RTX 6000 GPUs. Our experiments are performed on Python 3.5.4, Gym 0.10.5, Numpy 1.14.5, Tensorflow 1.8.0, and CUDA 9.0. In our experiments, we consider the set of admissible perturbed
8

---

Published in Transactions on Machine Learning Research (01/2024)
Table 1: Mean episode reward of 2000 episodes during testing. Our RMA3C policy achieves up to 46.56%
higher mean episode rewards than the basclines with random state perturbations N.
Environment
CN
ET
KA
PD
MA Lowe et al.
(017)
-388.59 = 60.72
-4..79 - 23.50
-8.80 = 5.07
3.03 = 0.67
M3 Li et al.
2019
-390.94 = 59.83
-39.55 + 20.53
-8.54 + 5.04
2.12 + 1.04
MP Yu ct al.
(2022)
-381.70 = 54.06
-37.62 + 18.94
MADDPG (MA) w/ N
-887.67 72.28
-55.79 = 26.78
-11.21 6.82
1.24 0.47
M3DDPG (M3) w/ N
-47.96 + 70.27
-54.40 + 26.64
-11.28 + 6.71
1.30 + 0.58
MAPPO (MP) w/ N
-523.83 = 78.45
-86.51 + 30.86
RMA3C w/ N (ours) -390.20 + 64.82
-46.23 = 24.76
-9.02 +5.87
2.48 + 1.26
state for agent at state as an for norm ball around demoting the perturbation budget. In implementation, the adversary network takes in the true state s and learns a state perturbation vector A' and we project s + A' to P:: The environments used in our experiments include cooperative navigation (CN), exchange target (ET), keep-away (KA), and physical deception (PD). A detailed introduction to these environments can be found in Appendix EE] All hyperparameters used in our experiments for RMA3C and the basclines are listed in Appendix E along with additional implementation details and experiment results.
S || S d} where d is radius
5.1 Baselines
In our experiment, we have a total of 9 baselines: MADDPG Lowe et al. 2017]. M3DDPG Li et al. (2019) MAPPO Yu et al. (2022), as well as versions of these algorit hiss with random and well-trained adversarial state perturbations. Detailed explanation of these baselines can be found in Appendix E.22 To evaluate robustness under state uncertainty, we add state noise to MADDPG, M3DDPG, and MAPPO producod by a truncated normal distribution NO,, X, u, I) where À is the uncertainty level, u and I are the upper and lower bounds to ensure noise's compactness. This simulates adversaries selecting random state perturbations. In contrast, our RMA3C algorithm trains agents under adversaries that try to minimize the agents' total expected return. We save the well-trained adversaries X" for each scenario in RMA3C to represent the optimal state perturbation adversaries. The well-trained adversaries are the adversary policies trained in the RMA3C algorithm when the algorithm reaches the maximum training episodes (100k episodes). We then use these adversaries to perturb the states for MADDPG, M3DDPG, and MAPPO to train and test their robustness under adversarial state perturbations. Because MAPPÓ provided in Yu al. (2022) only works in fully cooperative tasks, only report its results in cooperative navigation and exchange target. For both training and testing, report statistics that averaged across 10 runs in each scenario and algorithm.
5.2 Comparison Results
Training Comparison Under different Perturbations We compare our RMA3C algorithm with baselines during the training process to demonstrate its superiority in terms of mean episode rewards under different state perturbations as shown in Fig. 1 As RMA3C has a built-in adversary to perturb states, we do not train it under random state perturbations. In comparison to other baselines with different state perturbations, RMA3C consistently achieved higher mean episode rewards, demonstrating its robustness under varying state perturbations. Furthermore, when comparing each baseline with random state perturbations to the same baseline with the well-trained adversary policy x", we can see that the adversary policy trained by RMA3C is more effective than random state perturbations. This is because x" is designed to intentionally select state perturbations that minimize the agents' total expected return. The mean episode rewards of the last 1000 episodes during training are shown in the table Appendix E.5 Our RMA3C algorithm achieved up to 58.46% higher mean episode rewards than the baselines under different state perturbations.
Training Comparison With More Agents Our RMA3C algorithm is compared with baselines in the cooperative navigation scenario with an incrcasing number of agents. As shown in Fig/4 the original cooperative navigation environment has agents and our RMA3C algorithm outperforms the baselines in terms of mean episode rewards. In Fig we present the results of training with 4 agents, where our
9

---

Published in Transactions on Machine Learning Research (01/2024)
-600
Cooperative navigation with more agents
Cooperative navigation with different d-valuue
-400
1000
Aggrithm
neward
-1.00
RMAGC
MADUPG with nobe MADOPG
-150
Broala
W30DPG
6-100
WBDDPG
d=20
0-40
mean
-550
-1590
-1600
20
40
60
30
100
-000
spisode/k)
opisodatk)
(a)
(b)
Figure (a) Our RMA3C algorithm continues to achieve higher mean episode rewards, even with an increasing number of agents in the environment. 5ub RMA3C algorithm is trained in the cooperative navigation environment with different perturbation budgets d. When d increases, adversaries get more advantage, and may further decrease agents' total expected return.
RMA3C algorithm still surpasess the baselines. We include the training results with 6 agents in Appendix E.6 Our RMA3C algorithm continues to achieve higher mean episode rewards, even with an increasing number of agents in the environment.
Table 2: Our RMA3C policy achieves up to 54.02% higher mean episode reward than the baselines with well-trained x"
Environment
CN
ET
KA
PD
MADDPG (MA) w/X"
-537.56 + 72.28
-71.65 + 42.50
-14.72 + 5.44
-0.95 + 1.32
M3DDPG (M3) W/ X"
-515.85
74.58
-70.68 = 41.54
-13551 + 5.30
-0.70 + 0.96
MAPPO (MP) w/X"
-572.39
79.34
-109.26 + 47.97
RMA3C w/x" (ours)
-400.82 62.59
-50.23 26.97
-9.64 5.31
1.23
0.82
Training Comparison With Different Perturbation Budgets We compare our algorithm with baselines in the cooperative navigation scenario with varying levels of perturbation budgets d. We consider the set of admissible perturbed state for agent i at state as an foo norm ball around P = {p' E S ll - ssloo S d} where d is a radius denoting the perturbation budget. As shown in Fig. 5(b] when d increases, adversarics have greater freedom to perturb the stale within larger admissible perturbed state set. As d increases, adversaries get more powerful and lead decrease agents' total expected return.
Testing Comparison in different Environments Our RMA3C algorithm is tested in different envi- ronments demonstrate its robustness under state perturbations. As shown in Table [ the mean episode rewards are averaged across 2000 episodes and 10 test runs in each environment. The results of MADDPG, M3DDPG, and MAPPO, which are not designed to handle state perturbations, are shown a reference for the no state perturbation scenario. These algorithms perform poorly when random state perturbations are introduced, indicating the need for an algorithm that can handle state perturbations, As seen in Table 2 the RMA3C policy achieves up to 46.56% higher mean episode rewards than the baselines in environments with random state perturbations. Additionally, we also test the learned policies using different algorithms environments with well-trained adversary policies x" to perturb states. The results indicate that the RMA3C policy achieves up to 54.02% higher mean episode reward than the baselines with well-trained adversarial state betturbations. Overall, these tests demonstrate that the RMA3C algorithm achieves higher robustness in different environments with state perturbations.
6 Conclusion
In this work, we propose a Stato-Adversante Markov Game (SAMG) and investigate the fundamental properties of robust MARL under adversarial state perturbations. We prove that the widely used solution
10

---

Published in Transactions on Machine Learning Research (01/2024)
concepts such optimal agent policy and robust Nash equilibrium do not always exist for SAMGs. Instead, we consider new solution concept (the robust agent policy) to maximize the worst-case expected state value and prove its existence. This is the primary theoretical contribution of our work. Additionally, we also propose a RMA3C algorithm to find a robust policy for MARL agents under state perturbations. Our numerical experiments demonstrate that the RMA3C algorithm improves the robustness of the trained policies against both random and adversarial state perturbations. Some discussions and future directions are provided Appendix F
Acknowledgments
Songyang Han, Sanbao Su, Sihong He, and Fei Miao are supported by the National Science Foundation under Grants CNS- 1952019,, and CNS-2047354 grants. Haizhao Yang was partially supported by the US National Science Foundation under awards 2MS-2244988, DMS-2206333, and the Office of Naval Research Award N00014-23- 1-207.
Shaofeng Zou is supported by the National Science Foundation under Grants CCF-2106560, and CCF-2007783. This material is based upon work supported under the AI Research Institutes program by National Science Foundation and the Institute of Education Sciences, U.S. Department of Education through Award # 2229873 National AI Institute for Exceptional Education. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, the Institute of Education Sciences, the U.S. Department. of Education.
We extend our thanks to Peter Stone and Dustin Morrill in Sony AI for their assistance in proofreading this paper and for their insightful suggestions that have significantly enhanced the quality of this work. Their careful attention to detail and valuable feedback were greatly appreciated.
References
Vahid Behzadan and Arslan Munir. Vulnerability deep reinforcement learning to policy induction attacks. In ML.DM, pp. 262-275. Springer, 2017.
Daniel Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of markov decision processes. Mathematics of operations research, 27(4):819 840, 2002.
Lucian Busoniu, Robert Babuska, and Bart De Schutter. A comprehensive survey of multiagent reinforcement. learning. IEEE Trans. Syst., Mon, Cybern. Syst., 38(2):156 172, 2008
Katherine Chen and Michael Bowling. Tractable objectives for robust policy optimization. Advances in Neural Information Processing Systems, 25, 2012.
Gerard Debreu. A social equilibrium existence theorem. Proceedings of the National Academy of Sciences, 38 (10):886 1000-893, 1952.
Michael Everett, Björn Lütjens, and Jonathan P How. Certifiable robustness to adversarial state uncertainty in deep reinforcement learning. IEEE Trons. Neurol Netw. Learn. Syst., 2021.
Ky Fan. Fixed-point and minimax theorems in locally convex topological linear spaces. Proceedings of the National Academy of Sciences of the United States of America, 38(2):121, 1952.
Arlington M Fink. Equilibrium in stochastic n-person game. Journal of science of the hiroshima university, series ai (mathematics), 28(1):89 1989993,11111 1964.
Jakob Foerster and Gregory Farquhar. Counterfactual multi-agent policy gradients. In AAAI, 2018
Irving L Glicksberg. A further generalization of the kakutani fixed point theorem, with application to nash equilibrium points. Proceedings of the American Mathematical Society, 3(1):170-174, 1952.
Delin Guo, Lan Tang, Xinggan Zhang, and Ying-Chang Liang. Joint optimization of handover control and power allocation based on multi-agent deep reinforcement learning. IEEE Trans. Veh. Technol, 69(11): 13124-13138, 2020.
11

---

Published in Transactions on Machine Learning Research (01/2024)
Sihong He, Songyang Han, Sanbao Su, Shuo Han, Shaofeng Zou, and Fei Miao. Robust multi-agent reinforcement learning with state uncertainly. Transactions on Machine Learning Research, 2023.
Junling Hu, Michael P Wellman, al. Multiagent reinforcement learning: theoretical framework and an algorithm. In TCML, volume 98, pp. 242-250- Citeseer, 1998.
Yizheng Hu, Kun Shao, Dong Li, HAO Jianye, Wulong Liu, Yaodong Yang, Jun Wang, and Zhanxing Zhu. Robust multi-agent reinforcement learning driven by correlated equilibrium. 2020.
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. ICLR, 2017.
Maximilian Hüttenrauch and Adrian Sosić. Guided deep reinforcement learning for swarm systems. arXiv preprint arXiv:1709.000 00011, 2017.
Shariq Iqbal and Fei Sha. Actor-attention-critic for multi-agent reinforcement learning. In ICML, pp. 2961 2970. PMLR, 2019.
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280, 2005.
Chi Jin, Pranccth Netrapalli, and Michael Jordan. What is local optimality in nonconvcx-nonconeee minimax optimization? In ICML, pp. 4880 4889. PMLR, 2020.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110. 14555, 2021.
Erim Kardeş, Fernando Ordóñez, and Randolph W Hall. Discounted robust stochastic games and an application to queueing control. Operations research, 59(2):365-38) 2011.
Jernej Kos and Dawn Song. Delving into adversarial attacks on deep policies. ICLR, 2017.
Divya Kothandaraman, Rohan Chandra, and Dinesh Manocha. Ss-sfda: Self-supervised source-free domain adaptation for road segmentation hazardous environments. In ICCV, pp. 3049 3059, 2021.
Erwin Kreyszig. Introductory functional analysis with applications, volume 17. John Wiley & Sons, 1991.
Adam Lerer, Hengyuan Hu, Jakob Foerster, and Noam Brown. Improving policies via search cooperative partially observable games. In AAAI, volume 34, pp. 7187-710 7194, 2020.
Shihui Li, Yi Wu, Xinyue Cui, Honghua Dong, Fei Fang, and Stuart Russell. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In AAAI, volume 33, pp. 4213-4220, 2019.
Yongyuan Liang, Yanchao Sun, Ruijie Zheng, and Furong Huang, Efficient adversarial training without attacking: Worst-case-aware robust reinforccment learning. NewrIPS, 2022.
Jicyu Lin, Kristina Dzeparoska, Sai Qian Zhang, Alberto Loon-Garcia, and Nicolas Papernot. On the robustness of cooperative multi-agent reinforcement learning. In 2020 IEEE Securily and Privocy Workshops (SPW), pp. 62 68. IEEE, 2020a.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concal minimax problems. International Conference on Machine Learning, pp. 6083-6093. PMLR, 2020b.
Yen-Chen Lin, Zhang-War Wei Hong, Yuan- Hhan-Hong Liao, Meng-Li Li Shih, Ming- Yu Liu, and Min Sun. Tactics of adversarial attack on deep reinforcement learning agents. IJCAI, 2017.
Michael L Littman. Markov games framework for multi-agent reinforcement learning. In Machine learning proceedings 199,, pp. 157 163. Elsevier, 1994.
Ze Liu, Yingfeng Cai, Hai Wang, Long Chen, Hongbo Gao, Yunyi Jia, and Yicheng Li. Robust target recognition and tracking of self- self-driving cars with radar and camera information fusion under severe weather conditions. IEFE Trans. Intell. Transp. Syst., 2021.
12

---

Published in Transactions on Machine Learning Research (01/2024)
Ryan Lowe, Yi I Wu, Aviv Tamar, Jean Harb, OpenAI Picter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperaiiee-compettiie environments. In NewrIPS, pp. (379-63900 2017.
Ajay Mandlekar, Yuke Zhu, Animesh Garg, Li Fei-Fei, and Silvio Savarese. Adversarially robust policy learning: Active construction physically-pauusible perturbations. In TROS, pp. 3932-3939. TEEE, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529 533, 2015.
Jun Morimoto and Kenji Doya. Robust reinforcement learning. Neural computation, 17(2):335 359, 2005.
Devaprakash Muniraj, Kyriakos G Vamvoudakis, and Mazen Farhood. Enforcing signal temporal logic specifications in multi-agent adversarial environments: A deep q-laarning approach. In 2018 IEEE Conference on Decision and Control (CDC), pp. 4141-4146. IEFF, 2018.
John Nash. Non-cooperative games. Annals of malhemalics, pp- 286 295, 1951.
Arnab Nilim and Laurent El Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780070) 1978000--,--- 2005.
Frans A Oliehoek, Christopher Amato, et al. A concise introduction decentralized POMDPs, volume Springer, 2016.
Anay Pattanaik and Zhenyi Tang. Robust deep reinforcement learning with adversarial attacks. AAMAS, 2017.
Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks. In AAMAS, pp. 2040-2042, 2018.
Thomy Phan, Thomas Gabor, Andreas Sedlmeier, Fabian Ritz, Bernhard Kempter, Cornel Klein, Horst Sauer, Reiner Schmid, Jan Wieghardt, Mare Zeller, et al. Learning and testing resilience in cooperative multi-agent systems. In Proceedings of the 19th International Conference on Autonomous Agents and MulliAgent Systems, pp. 1055 1063, 2020.
Lerrel Pinto, James Davidson, and Rahul Sukthankar. Robust adversarial reinforcement learning, In ICML, pp. 2817-2826, PMLR, 2017.
Arnu Pretorius, Scott Cameron, et al. A game-theoretic analysis of networked system control for common-pool resource management using multi-agent reinforcement learning. In NewrlPS, volume 33, pp. 918399999999999 9994, 2020.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic progromming. John Wiley & Sons, 2014.
Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li. Scalable multi-agent reinforcement learning for networked systems with average reward. In NewrIPS, volume 33, pp. 2074-200000 2086, 2020.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. In NewrIPS, December 2020.
Mcisam Razaviyayn, Tianjian Huang, Songtao Lu, Maher Nouiched, Maziar Sanjabi, and Mingyi Hong. Nonconvex min-max optimization: Applications, challenges, and recent theoretical advances. IEEE Signal Process. Mag., 37(5):55-66 16,5566667666 2020.
Walter Rudin et al. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1976.
Lloyd Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10):1095 1100, 1953.
Macheng Shen and Jonathan P How. Robust opponent modeling via adversarial ensemble reinforcement learning. In ICAPS, volume 31, pp. 578 587, 2021.
13

---

Published in Transactions on Machine Learning Research (01/2024)
Aman Sinha, Matthew O'Kelly, et al. Formulazero: Distributionally robust online adaptation via offine population synthesis. In TCML, pp. 3992-9004, PMI.R, 2020.
Jianyu Su, Stephen Adams, and Peter Beling. Valne-decomposition multi-agent actor-critics, In AAAI, volume 35, pp. 11352 11360, 2021.
Chuangchuang Sun, Dong-Ki Kim, and Jonathan P How. Romax: Certifially robust deep multiagent reinforcement learning via convex relaxation. arXiv preprint arXie:2109.067 06795, 2021.
Yanchao Sun, Ruijie Zheng, Parisa Hassanzadeh, Yongyuan Liang, Soheil Feizi, Sumitra Ganesh, and Furong Huang. Certifiably robust policy learning against adversarial communicatio in multi-agent systems. JCLR, 2022.
Peter Sunchag, Guy Lever, et al. Value-docomposition networks for cooperative multi-agent learning based team reward. In AAMAS, pp.
2018.
Richard S Sutton, Andrew G Barto, et al. Introduction reinforcement learning, volume 135. MIT press Cambridge, 1998.
Tessa van der Heiden, C Salge, Efstratios Gavves, and H van Hoof. Robust multi-agent reinforcement learning with social empowerment for coordination and communication. arXiv preprint arxi::2012.088 0.0255, 2020.
Kaixin Wang, Uri Gadot, Navdeep Kumar, Kfir Levy, and Shie Mannor. Robust reinforcement learning via Tttle-Trattbble objectives for robust policy oplimization, author= Katherine and Bowling, Michael, journal=Advanees Advances in Neural Information Processing Systems, volume=25, year=2012 Xie preprint orXiv:2306.0588 2023.
adversarial kernel approximation. (iBarticlecenn2012rrrrce
Chaowei Xiao, Xinlei Pan, et al. Characterizing attacks deep reinforcement learning. ar preprint WrXiv:1907009/70 2019.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent gamos. NewrIPS, 2022.
Jing Yu, Clement Gehring, Florian Schäfer, and Animashree Anandkumar. Robust reinforcement learning: A constrained game-theoretic approach. Learning for Dynamics and Control, pp. 1242 1254. PMLR, 2021.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsich. Robust deep reinforcement learning against adversarial perturbations on state observations. NeurIPS, 33:21024- 21037, 2020a.
Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsich. Robust reinforcement learning on state observations with learned optimal adversary. arXic preprint arXim:2101.084 2021.
Kaiqing Zhang, Tao Sun, Yunzhe Tao, Sahika Gene, Sunil Mallya, and Tamer Basar. Robust multi-agent reinforcement learning with model uncertainty. In NewrIPS, 2020b.
Meng Zhou, Ziyu Liu, Pengwei Sui, Yixuan Li, and Yuk Ying Chung. Learning implicit credit assignment for cooperative multi-agent reinforcement learning. In NeWrIPS, volume 33, pp. 11853 11864, 2020.
14

---

Published in Transactions on Machine Learning Research (01/2024)
A Comparison with Dec-POMDP and Markov Games
A.1 Comparison with Dec-POMDP
Our SAMG problem cannot be solved by the existing work in the Decentralized Partially Observable Markov Decision Process (Dec-POMDP) (Oliehoek al. 2016). In contrast, the policy in our problem needs to be robust under set of admissible perturbed states. The adversary aims to find the worst-case state perturbation policy to minimize the MARL agents' total expected return. In the following proposition, we show that under certain additional conditions our proposed SAMG problem becomes a Dec-POMDP problem.
Observation of
Perturbed State p|-xx (s)
Observation Function
Adversary 1
Agent 1
Agent 1 :
Tt
:
Tt
:
p xxxx (o*ls)
Observation Function
Adversary n
Agent n
State St
Agent n
State
Reward Tt
Reward Tt
Action dt-n' (a
Action a (al1pf)
17t11
T++1
Environment
Environment
S
S
SAMG
Dec POMDP
Figure 6: Comparison between Dec-POMDP and SAMG. In Dec-POMDP, the observation probability function fixed, and will not change according to the change of the agent policy. However, SAMG the adversary policy is a fixed policy, may change according the agents' policies and always select the worst-case state perturbation for agents.
Proposition 3.2. When the adversary policy is fized policy, the SAMG problem becomes Dec- POMDP OOlihhokk et al. 2016).
Proof. When the adversary policy X is a fixed policy, an SAMG POMDP (W, S,A, 0, O, Pr(so)). The agent set N {1,..., n). The global joint state is S. Each agent i is associated with action a' E A'. The global joint action is (a' a!...))) A, A == A' x-.. X A All agents share a stage-wise reward function S' A + R. The state transition function is p S A(S), where A(S) is a probability simplex denoting the set of all possible probability measures on S. The state transits from the true state to the next state. The discount factor is 7. The joint observation set O is the same as the joint state set S. The observation probability function ((o)s) = ((oss) for any o E P. and O(ols) = for any & Ps, where the observation given the state s. The Pr(sp) is the probability distribution of the initial state.
r,, P..P. y, Pr(su)) bocomes a Dec-
In Dec- POMDP the observation probability function is fixed, and it will not change according to the change of the agent policy. However, in SAMG the adversary policy is not a fixed policy, it may change according to the agents' policies and always select the worst-case state perturbation for agents. In contrast to Dec-POMDP, the adversary's 's policy X is chosen minimize the total expected return of the agents in our problem. Additionally, in DocPP the agents do not have access the true state s, whereas in our problem, the adversaries aware of the true state and use it to select perturbed states.
15

---

Published in Transactions on Machine Learning Research (01/2024)
A.2 SAMG cannot be solved by Dec-POMDP: Two-Agent Two-State Game Example
We use a two-agent two-state game to show the difference between Dec-POMDP and SAMG. Consider game with two agents N = 2) and two states S = {si, 82} as shown in Fig. i Each agent has two actions A = A² = 02). The transition probabilitics are defined below.
p(s' = $1 s $1, * a²) = 1,
p(s' #2 51,a' a²) 1,
p(s' $2 s 52, a 4 a²) =1,
p(s' = 81 = 52, a = d²) =
(6)
Specifically, a' a² includes two cases: al a² = 01 or d² = 02 Similarly, a * a² includes two cases: a' 01, a 02 or a 022 a² 01
a² a²
a² # a² 0
a * a² T =
$1
S2
a² a²
Figure 7: A two-agent two-state game example. Agents get reward 1 at state $1 if they choose the same action. Agents get reward 1 at state if they choose different actions.
Two agents share the same reward function:
1, a = and 8 = 81,
0. a' + a² and 811
r(s,at
(7)
at a² and s 82,
1, at + a² and 8 82-
In a SAMG, cach agent is associated with an adversary to perturb knowledge or observation of the true state. For the power of the adversary, we allow the adversary to perturb any state the other state:
p = p? {s1,
(8)
We use 7 = 0.99 as the discount factor. Agents want to find a policy æ to maximize their total expected return while adversaries want to find policy X minimize agents' total expected return.
This problem cannot be formulated as Dec-POMDP Consider one agent policy where both agents select the same action in $1 and select different actions in 32: T (ai(s)) = x' (ails)) = <a(alss)) = x² (a22822) 82) =1 When there is no adversary, agents keep recciving rewards. The values for cach state are (s11) = (s2) = 1 = 100. Because agents share the same reward function, they also share the same values for each state. However, this policy receives V(s)) (ss2) = 0 when agents are facing the worst-case adversaries (82) = ('(s2(s)) = for i 1,2 and always taking the wrong actions with 0 reward.
I-
If the adversary policy is fixed at x'(>1 (82) = (82)(1))) = for i 1,2, this problem becomes a Dec-POMDS with the observation space = (or 81, 02 = $2). The observation function is d'(0)1s2) = ('(02(91) for 1, The agent poliey is . (a
(2 l02) (ai (a2/02) 1.
However, when we consider different agent policy where both agents select the same action in 82 and select different actions in $1: x r'(aa1s>) = x (11 = (a)(()))) = (a2(()))) 1, agents keep recciving 0 rewards even when the adversary does nothing. For the new agent policy, the worst-case adversary policy is x'(s1(s)) = x (s22122) = for i = =,,2. The corresponding observation function for the new adversary policy is (s)) = of (o2 82)) for i i= 1,2, which is completely different from the previous observation functions. Bocause the observation function in PecPP won't 't change according to agents' policies, therefore, the SAMG problem cannot. be formulated by Dec-POMDP when adversary policy is not fixed.
16

---

Published in Transactions on Machine Learning Research (01/2024)
Under different observation functions, Dec-POMDP can lead to contradictory agent policies. Besides the analysis of why this problem cannot be formulated as Dec-POMDP, we also demonstrate that. Dec-POMDPs fail to solve this problem from a different perspective.
Let's consider a Dec-POMDP with the observation space O = {or = 01 = $2). The observation function is defined as (0 (x2) of (02)+1) = for i= 1,2. In this scenario, the optimal agent policy to select the same action in response 02 and choose different actions for 01- Agents keep receiving rewards based on this policy.
Now let's consider another Dec-POMDP with the observation space O = (or 81, = 82) The observation function is defined as [s) = (02](82) = 1 for i = 2, In this case, the optimal agent policy is to select the same action in response to 0n and choose different actions for 02. Agents keep receiving rewards based on this policy. However, the new optimal agent policy contradicts the previous one.
By comparing these two Dec-PSMDPs with different observation functions, we observe that Dec-POMDPs can yield different agent policies based on different observation functions. This implies that Dec-POMDPs do not address the problem of selecting an agent policy when the observation function is determined by an adversary.
Furthermore, we will reanalyze this problem and demonstrate how a SAMG can solve this two-agent two-state game in Appendix B and [ The SAMG formulation addresses this problem by selecting the agent policy against the worst-case observation function.
A.3 Comparison with Markov Games
Under a specific condition, when the adversary policy X a bijective mapping from to S, the SAMG problem is equivalent to a Markov game, as demonstrated in the following proposition. This proposition illustrates the relationship between a SAMG and a Markov game with particular form of state perturbation.
When X is bijective mapping from S to S, the adversary policy follows x(pls) selecting the perturbed state for the true state with probability 1. Let us use the notation x(s) = p for this special case.
Proposition 3.3. When the adversary policy is a fixed bijective mapping from S to S, the SAMG problem becomes a Markov game.
Proof. When the adversary policy X is a fixed bijective mapping from S to S, an SAMG problem A, A,,,,,,,, p.,47; Pr(so)) becomes Markov game (Wnew: SSow: Anew, Teews Pnews 7, Pr(#new,))) that is con- structed as follows:
Taking Snew p x(s) the new state, the global joint state set is Snew == S. The global joint action set Anew A = Al x .... x A and the agent set Nnew = N stay the same.
We can construct a new reward function rhew Snew x Anew + R for each agent i as
new (Snew = X(s), anew = a) r(s, a),
(9)
and a new state transition function Prew Snew Anew A(Snew) defined
Pnew (p' = x(s')lp= x(s)))p=x((s,a)) = p(s'ls.
(10)
The new probability of the initial state is
Pr(snew,0 X(50)) = Pr(so).
(11)
Each agent uses a policy тं Tie Snew + A(A') to choose an action based on the new state. Hence, the
SAMG problem becomes a Markov game.
If the adversary's policy X is a fixed bijective mapping from S to S, the new global joint state sot Snew is a perturbation of S and each state is assigned new 'label' by the adversary. Under this condition, the SAMG is equivalent to a Markov game.
17

---

Published in Transactions on Machine Learning Research (01/2024)
B Optimal Adversary Policy and Optimal Agent Policy
In this section, we analyze the existence of the optimal adversary policy and the optimal agent policy. We will utilize the two-agent two-state game introduced in Appendix A For completeness, let us revisit this game with two agents N = [1, and two states S {s1, 82} as shown in Fig. Each agent has two actions A = A2 02). The transition probabilities are defined below.
p(s' 81 s $1, + a²) 1,
p(s' 82 s $1 a²) = 1,
p(s' = $2 82, a * a²) = 1,
p(s' 81 $ $2, a = a²) =1.
(12)
Specifically, a² a² includes two cases: at a² - or a² = 02 Similarly, at + includes two cases: a' a1, a² 02 or a 0g a² 01
a a²
* d² 0 S1
a² a² r =
S2
a a²
Figure A two-agent two-state game example. Agents get reward 1 state 81 if they choose the same action. Agents get reward at state $2 if they choose different actions. This example was used in Appendix to show the difference between Dec-POMDP and SAMG. We will revisit this game in Appendix B to discuss optimal adversary policy and optimal agent policy.
Two agents share the same reward function:
1, a a², and 8 = 81
0, a' + a², and s = 81,
r(s, a ,a²)
(13)
0. a' = a², and s = 82.
11 at + a² and 82-
In a SAMG, each agent is associated with an adversary to perturb its knowledge or obscrvation of the truc state. For the power of the adversary, we allow the adversary to perturb any state to the other state:
p! =? (81, 82).
(14)
We use 7 0.99 as the discount factor. Agents want to find a policy to maximize their total expected return while adversaries want to find policy x to minimize agents' total expected return.
B.1 Optimal Agent Policy Without Adversaries
When there is no adversary, the optimal policy for agents is to choose the same action in and choose different actions in 82. One example is (ai]s)) = (ai(5)) = T²(a1ls)) = x²(a2ls)) (32) = 1. The agents keep receiving rewards. The values for each state are ((s)) = (s2) = I- = 100. Because agents share the same reward function, they also share the same values for each state. However, this policy receives (s1) = (s2) 0 when agents are facing adversaries (((s1)52) x (s2/s)) 1 for i 1, and always taking the wrong actions with 0 reward.
B.2 Stochastic Policy With Adversaries
We consider stochastic policy x! (ai|sı) (arls2) (arls1) probabilities of taking the same different actions are the same for each state Pr(at a² |s)) Pr(a #
(az)(s)) =
0.5. Under this policy, the
18

---

Published in Transactions on Machine Learning Research (01/2024)
Pr(a' # 82) = 0.5. Agents randomly stay transit in each state and receive a positive reward with a 50% probability. The adversary has power under this policy because i is the same for both states. The values for each state are V(s1) = ((32) = (s1) = V(22) = T-> = 50.
a² 81) Pr(a' a² $2)
0.5
B.3 Deterministic Policies With Adversaries
Since cach agent has two actions for each state, there are in total 2 = 16 possible deterministic policies for the two-agent two-state game example. All possible deterministic policies can be classified into three cases: (1) If agents select the same action in one state 8, and select different actions the other state Sj, then we always have Vss)) ((2)) = This because adversarics can always use (=111s) = (*2 8;) for k = 1,2 such that agents always reccive a reward. (2) If agents always select different actions in both states, then V(si) 0, (82) 100. This is because agents never Iransit to the other state and keep receiving the same reward. (3) If agents always select the same action in both states, then V(s1) 1 adversaries have no power to change it.
1--2 R 50.25, ((s2)= = 1-1 = 49.75. This is because agents circulate through both states and
B.4 Optimal Adversary Policy
In this section, we examine optimal policies for both the adversary and the agent in a State-Adversarian Markov Game (SAMG). The following proposition demonstrates the existence of an optimal adversary in an SAMG.
Proposition 4.1 (Existence of Optimal Adversary Policy). Given an SAMG, for any given agent policy, there erists on optimal adversary policy.
Proof. We prove this by constructing MDP M (S, (S,A, such that optimal policy of M is optimal adversary policy x" for the SAMG given the fixed In the MDP M, take all adversarics joint adversary agent. The joint adversary learns a policy x to find joint perturbed state given the current true state. The action space Á = S x S x S. Note that the joint admissible perturbed state set in Definition 3.1 P. C Á.
The reward function defined as:
((s,a)= -- - x(al()r(s,a) for â e..
(15)
The transition probability P is defined as
p(s'|s,a) à)
Σ aEA
xalla)p(s'ss. for à P..
(16)
The reward function is defined based on the intuition that when the agent receives given 8, the reward of the adversary is the negative of the agent reward, that is to say, f -r. Considering that r(s, a) = [[]]s, a] = - [,]
((s,a) E[[Ass a]
> R Σ
Pr[f|s s. ()a(a
R
acA
Σ
Σ
A a) x(ala)
aEA
R
Σ
E {
aEA
Σ
E[R|s,
aEA
19

---

Published in Transactions on Machine Learning Research (01/2024)
Σ REA
((),))((aaa)
(17)
Puterman 2014 know that the MDP M has optimal policy x" that satisfies V (s) Vn, (3) for all and all X, where Paxx is the state value function of the MDP M.
Based on the properties of MDP (Sutton al. 1998
The Bellman equation for the MDP M is
Vxx (5)
E x(ols)
f+7 Σ
D(s' ())(ss,)V=xxx()
dEP,
s'ES
Σ x(ass) Σ T(ala)
-r+ Σ
p(s'lss, [pss)ss,a)Pxx((6)
(18)
aEP,
aEA
s'ES
By multiplying -1 on both sides, we have
(-)xx((s)= = Σ x(āls)
Σ T(ala)
AEP
aEA
p(s'ls, 10
(19)
e'ES
On the other side, for the SAMG, have the Bellman equation for any fixed policies and as
V (+)
Σ x(pls)
Σ x(alp)
PEP,
r+
Σ e'ES
p(8'1s, a) (V))))))))))
(20)
When π and X are fixed, they can be taken together as single policy, and the existing results from Dec- Rec-POMDP can be directly applied. Comparing Eq. (20) and (19), we know that V*x(2) = (-Vr.(()).
An optimal adversary policy x" for the MDP M satisfics (s) 2 (s) for any s and any X- Therefore, x" also satisfies (x) S V>.x (s) for any s and any X. and an optimal policy of the MDP M is an optimal adversary policy for the SAMG given the fixed w.
B.5
Optimal Agent Policy With Adversaries
We have established the existence of an optimal adversary in SAMGs. Next, we consider a state-robust totally optimal agent policy under this optimal adversary. The following proposition demonstrates that deterministic agent policy is not always superior to stochastic policy in SAMGs.
Proposition B.1. There exists SAMG and some stochastic policy π such that connot find better deterministic policy n' satisfying V=) 2 (s(s) for all S.
Proof. We prove this theorem by giving counter-exampli where no deterministic policy is better than a stochastic policy. As shown in the two-agent two-state game example in Fig. S all 16 deterministic policies are no better than the stochastic policy x (a1l81) = x xa (a1182) = म (a1 (1)) = (a2l82) = 0.5.
Finally, we show a state-robust totally optimal agent policy n* does not al always exist such that V.- (8) 2 (s() for any म and all E S SAMGs in the following theorem.
Theorem 4.3 (Non-existence of State-robust Totally Optimal Agent Policy). A state-robust totally optimal agent policy does not always erist for SAMGs.
20

---

Published in Transactions on Machine Learning Research (01/2024)
Proof. We prove this theorem by showing that the two-agent two-state game in Fig. g does not have an optimal policy. We first show that the policy Tı (01 = (a1 = T (a2ls1) = x² (a2 s2) 1 is not an optimal policy. Because agents always select different actions in both states, agents always stay in the same state and adversaries have no power to change it. The values for cach state are (s1) = 0, Vn, (52) = 100. Now we consider the stochastic policy m2 x [11] = x² ((11112)) = x² (a]1())) = (#2((2)) = 0.5. The values for cach state are Va (s1) (s2) = 50. Bocause Vn, (81) > VA, (81), the policy лi is not an optimal policy for agents.
If there exists an optimal policy x², then it must be better than иT and have (s- > 0, (s- = 100. In order to have (82) 100, agents must select different actions in and keep receiving the positive rewards from each step. In order to have (s1) ) > 0, agents must have a chance to select the same action in 81, i.e, Pr(a' = a² $1) > O. However, if Pr(a' = a² s1) > 0, then adversaries can have X' ($2) > 0 for i i= 1,2 to perturb the state 82 to 81 and reduce (82). Therefore, no policy can do better than ni and since x not an optimal policy, there no optimal policy for agents.
In the comparison of á and 22 in the above proof, is apparent that is not always possible to maximize the state value of all states and that tradc-offs may need to be made among different states. Using the traditional definition of an optimal policy, it is not possible to determine which policy, कi or T2, is better. However, if we use the worst-case expected state value concept from Definition [.8] and assumee that the initial state is always $2, then we can conclude that Tı is an optimal agent policy, as it gives the maximum worst-case expected state value of 100 in this case.
C Stage-wise Equilibrium, Robust Total Nash Equilibrium, and Robust Agent Policy
In Theorem 4.3 it has been proven that state-robust totally optimal agent policy does not always exist for SAMGs. This section explores alternative solution concepts for the agent policy in SAMGs. We begin by demonstrating the existence of a unique robust state value function for each agent in C.1. property, we establish the existence of a stage-wise equilibrium for each state in C.2 However, we show in C.3 that the robust total Nash equilibrium may not always exist. As an alternative, we propose the concept of a robust agent policy and demonstrate its existence in C.4
Building on this
We first give a review of the Nash equilibrium used in the literature. The Nash equilibrium is a widely used solution concept in game theory, first proposed by Nash in Nash (1951) for general-sum finite one-shot games. It states that each player selects the best response strategy to the others' strategies and no player would want to deviate from the equilibrium, as doing so would result in worse utility. This concept was later extended to infinite games by Debreu (Debreu 1952), Glicksberg [Glicksberg, 1952), and Fan (Fan 1952p. Markov games, which involve a sequential decision process in a two-player zero-sum setting, were first defined by Shapley in /Shapeyy| (1953). Fink extended the Nash equilibrium concept to Markov games in Fink (1964) and proved that an equilibrium point exists in n-player general-sum discounted Markov games. The uncertainty in transition dynamics of a Markov game was considered in Nilim & El Ghaoui (2005); [yengar (2005) using a robust optimization approach, with independent proofs for the existence of the equilibrium point. Additionally, uncertainty in utility (or 'reward" in reinforcement learning) was also taken into account in Kardey et al. T for n-player finite state/ /action discounted Markov games, with a proof for the existence of the equilibrium point.
Despite the extensive study of the Nash equilibrium in game theory, the uncertainty in the state has not yet been explored in the context of Markov games. To the best of our knowledge, we are the first to formulate the problem of n-player finite state/ fate/action discounted Markov games with state uncertainty and to demonstrate the existence of stage-wise equilibrium, as well as the non-existence of a robust total Nash equilibrium.
We use the following Assumption
C.1 throughout this section.
A Assumption C.I. The global state set 8 and the global action set A are finite sets.
21

---

Published in Transactions on Machine Learning Research (01/2024)
C.1 Unique Robust State Value Function
Denote the agent policies and adversary policies of all other agents and adversaries except agent i and adversary i as x- and x respectively. We show that there exists a unique robust state value function for agent i given any n² and x
Definition 4.4 (Robust state value function). state value function V ,, - : - R for agent. given T and x is called a robust state value function if for all S
Mxxx Vs Ri (()) max min
Σ ((pls)
Σ xalpp)
x²
X PEP
REA
r(s,a)+ + Σ
p(s'|s,
(21)
s'ES
Note that use <alp)) _ (a'lp') to denote the joint agent policy. We use x(pls) II _ ( to denote the joint adversary policy.
Before proving the existence of the unique robust state value function, we first introduce some notations for this proof. For a given state value function V -,,x- S - R defined on a finite state set S, we can construct state value vector vi = vec(VV 6, ',sx where vea(-) is a vectorization function. The infinity norm on V is 10'1 = max,es [V*(s)). Define the total expected return in state for x' and x" as
-,-x- :) = IV f,xx (s)] = Rl by traversing all states,
F' xx,xx))
Ex
E(pels
Σ x(alp)
PEP.
aEA
((()0)+ +7 p(s'ls (10))))))
(22)
EES
where x and x denotes the agent policies and the adversary policies of all other agents except agent i. Define the robust state value in state 8 given -² and x as function vif V + R,
( a xx==== ())))== max min fl x,, n x*)
(23)
x²
Note that by gives a real number that denotes the total expected return in state s given - and x We can construct mapping T + V from any state value vector w² a robust state value vector [T *,x (v (es) by traversing all s, that is to say, (v*) = vi (v*, x x= xt))
Lemma C.2. For any i N, the function T Fx V V is contraction mapping given any - and x of other agents and adversaries except agent i and adversary i.
Proof. Let us consider two vectors vt, E. For any i E EN, given any -- and x for all 8 S, we have
Vi n x1= = max min fi a5, π x1xxx=)
x" f''l", m
(24)
where i'* is the corresponding maximizer, and x is the corresponding optimizer for x Similarly, with the optimizers e and s for the following maximin optimization problem, we have
(1 : = max min (a ,,"","",, T -T x.x x
wt ip
= fl(z), with x - p
> fi , 1
(25)
22

---

Published in Transactions on Machine Learning Research (01/2024)
where
3 = arg min fi(z', ,,,,"" (1,,,''''))
(26)
Then, for any i E W, given any n- and x , for all & E S, it holds that
"l xx- , ;
fi(O', xh x xx",x" x f( ① sPI xX xx)
S So xx" xxx - l( m x 192 xx
S Sil0' x²
1 fz(=" T o 992 xx
E
22 (p'ls)
II (x'ssss Σ
n" (a'la')))
PEP. 87
aaA
II n (a"1"")
(++t)
Σ
p(s'ls a))vos (x9)0)
dEES
Σ
92 (o'ls)
(0²1s) [x'ss')ss)) Σ Th (a'lo))
PEP,
st
aEd
II n (a")
(++
Σ al (vee)))))==(()))(()))))) (21))166)
kfi
E'ES
Σ PEP.
2 (p' (8)
II (x' Σ (a'p))
i71
aEA
II (a y p(5'1s,a)x
$EES
{ivec (o')](s) - |vec [vee- (2')((s))
p (p'ls) II (p'ls) (s) Σ (a'()')
PEP
jz1
aEA
II 10t)) Σ (18')8,a)111 20100
e'ES
>llu* bo.
(27)
The second inequality in Eq.
27 follows
x" arg min fl n" x- -x,,x'x''
(28)
Because for any E M, given any क and x - for all s E
- vi(u', n xxx) (2,, x s 7/10²= =21loo
(29)
Based on symmetry, we have
(e T - v0 x xx- s 7110* v² -01
7110² 2¹ 201loc
(30)
Thus, it holds that for any i E N, given any म and x
I " " (l S >1lut - 20,
(31)
that is to say, the function V xx is contraction mapping.
23

---

Published in Transactions on Machine Learning Research (01/2024)
Theorem 4.5 (Existence of Unique Robust State Value Function). For SAMG with finite state and finile aclion spaces, for any E N, given any n- and x of other agents and adversories except agend and adversary's i, there exists a unique robust state value function ,,xx for all E S,
: - IR for agent such that
V -xx-
max min
Σ ((pss) PEP.
Σ x(app)
x²
x
REA
r(s,a) +7 Σ ((slss (
(32)
3'ES
Proof. For any i E N, there exists state value function Vi 4,x-1 satisfying 132 if and only if of vec(V. -x) fixed point of V x.x ~, where [Wr n. lses = (1 x
and vi n x=)
is definod in 23 We use Banach's ' fixed point theorem to prove this as follows.
Because any fiiteedimensional normed vector space is complete (Kreyszig 1991 the (V, llx)) is a complete Banach space. Also, for any i E N,, given any - and x the function V n, is a contraction mapping according to Lemma C.2 Therefore, by Banach's fixed point theorem, there a unique fixed point vt such that Ví xx (v²) = v². In other words, for any i NW, given any n= and x x there exists a unique V -x
such that
( max min fa a '')
(33)
Denote the state value function for agent i given any x and x of other agents and adversaries except agent i and adversary i as
a fxix (s)) fo m x))
(34)
where v' = vec(V") -oxo(V Then we have the following corollary for Theorem C.1
Corollary C.3. For an SAMG with finite state and finite action spaces, let V --xx--x be the unique robust state value function for agent i given any - and x such that for all E S,
V
V
max min fl n² T. x" zi
x²
S'( ,",
(35)
where of vee( ( ni* is the corresponding mazimizer at state s, and x the corresponding optimizer for th al slate 8, then for slate it holds that Vs " x 2 V x-xx"x for any n²
and Vi n x-- (s) < Vi.. x xxxx for any x².
C.2 Existence of the Stage-wise Equilibrium
Before show the existence of the robust lotal Nash equilibrium, we first show concept of the stage-wise equilibrium.
Definition C.4 (Stage-wise Equilibrium). For an SAMG, the policy (x*xx") is stage-wise equilibrium for state if for all i E N and all x' and x", it holds that
Vi
(s) 5 V Va x xx1 (8) <
Vi n a- x (s),
(36)
where - and x denotes the agent policies and adversary policies of all the other agents except agent i, respectively.
24

---

Published in Transactions on Machine Learning Research (01/2024)
The Nash equilibrium was originally proposed by Nash for finite one-shot games, in which the state transition of the environment is not considered. When the concept of Nash equilibrium is extended to Markov games, the existence of the equilibrium is shown through the existence of a state-wise equilibrium for each state. A policy that is a stage-wise wisc equilibrium for all states is considered a Nash equilibrium for the Markov game.
This idea brings the following proposition to show the relationship between the robust total Nash equilibrium and the stage-wise equilibrium for SAMGs.
Proposition C.5. The policy (x" xx") a robust total Nash equilibrium for an SAMG if the policy (x*, .x") is a slage-wise equilibrium for all E S.
Proof. It natural result according the Definition 4.6 and the Definition C.4
We show the existence of the stago-wise oquilibrium defined in Definition C.4 in the following theorem.
Thcorem C.6 (Existence of Stago-wisc cquilibrium). For SAMGs with finite state and finâte action spaces, the stage-wise equilibrium defined in Definition C.4 erists for any E.
Proof. Let us construct a 2n player game for any s S. We have n agents and n adversaries in the player set. We introduce uniform notations for the agents and adversaries to describe a 2n player game at state The player set I {1, ..., n, + 2n). The first half of the player set (1. represents agents, while the second half {n + 1, 1.... 2 represents adversarics. The set of available actions for player is
A' A' x A A² = total number: [PH] pi-n
i 1,..,, n,
(37)
n= + L,..., 2n.
Each adversary's action set includes all possible perturbed states in the admissible perturbed state sot at state s. Each agent's action set includes all possible joint actions given every possible perturbed state. Take the two-agent two-state game in Fig. as an example, the player set I = 21, 3, 3,4.. Player 3 is the adversary for agent player 1. Player 4 is the adversary for agent player 2. If the current true state is $1, then 4! = A = {(11001) (a1. 02), (a2, 02), (1)} are the action sets for two agent players. In A!, for agent 1, the joint action (01, (2)) means selecting a1 if the perturbed state for agent is 81 and selecting 02 if the perturbed state for agent is 82. For two adversary players, A = A4, = {51, s2 as adversaries can perturb the true state $1 $2-
We consider the mixed strategy of (AA)) for player i. Note that the mixed strategy for each adversary gives us the probability distribution of all possible perturbed states for state s, i.e. x²""(p""|ss) = (o--") for i = n 1,...,2r, 2n. Then we show how we can get each agent's policy N' T'')'lp") based on its mixed strategy of by calculating the marginal probabilities. Denote the total number of possible perturbed state for agent at state s as such that P = IPil- Here we drop the subscript s in Ps for a concise representation. The perturbed state set for agent i is represented as {pi ,pp...,pp). Denote the joint action of agent as b (bi, b2.... b6......6. (b,, b2. ......... (...b),'pp)) byp) gives us the joint probability of selecting by for P for all k = 1,,,..., P. We can get the marginal probability of selecting action a' given the perturbed state p E Pj as
........))))) bb)) where by is the action selected for the perturbed state p E Pi. Then the mixed strategy
T <'aa
Σ (MEAS
(b ((..,6)....,p))) bp).
(38)
The marginal probability of selecting action at given the perturbed state P is calculated by summing up the joint probability over all joint actions in which agent i selects a' given the perturbed state pt. Take the two-agent two-state game in Fig, as an example, if the current perturbed state for agent is p =1=s1, then agent I's policy is
x <ailpp = si) = o d' a1) + o (01, x <'zlpp = 91) o (02. + R² (02,
(39)
25

---

Published in Transactions on Machine Learning Research (01/2024)
Note that the mixed strategy o' A(A)) only gives part of the agent and adversary policies. For example, the mixed strategy for the adversaries only gives distribution of the perturbed states for = 8. We construct the complete agent and adversary policies as follows: For i = I,,,,, the agent i's policy is
=i o2 (g.....b)).
T| T'(a'p²²)- = for p¹ = Phe E P::
(40)
U(A'),
for p² P
where U(A*) represents uniform distribution on At. For i = 1,.... n, the adversary i's policy is
(( (p)) for = ((P))) for 8 + 8,
(41)
where U(P.) represents uniform distribution on P.
The utility function for player is
fi n x xt xxxxx :xxxx xx=x,)),
for i 1;
S (v(i-n) n (i-n)
(42)
inn X (1-1)).
for i =
2n.
where or denotes the strategies of all other players except player i, 1t* = veo(Vi --- and V - is the unique robust state value function of agent i when the policies of other agents and adversaries are given by x and = The w satisfies
[vec (1t)) max min fi( x², , ,x,xx"),
(43)
x x
where S3 is defined for player in 22 as
fl T x
x)x
Σ x(els) Σ x(alp)
PEP.
aEA
r(s,a) + Ep(''
p(s'la a) (c+)(()
e'SS
Note that o." includes both - and X for any i I, and the existence of V - guaranteed by Theorem C.1 Thus, the utility function is well-defined.
Since the state set S is finile, Pj C S is finile set for all i E W. Also, A' is a finite set for all i E N. Therefore, A(A is compact and convex for all i E I. Moreover, for all i e I, u - is linear in o² and therefore BraksbbergGGiccsberrg
continuous and concave in o'- According to the thcorem (Debreu Debreu 19522). Glicksberg Glicksberg (1552). Fan Fan 1952 ), the conditions for the existence of a Nash Equilibrium are satisfied, hence, there exists a Nash equilibrium of for this 2n player game for any & E S such that for any E I, u (a ( 2 u² (a (t))
for any of
Denote the agent and adversary policies as (TT,'*) that are constructed following Eq.
40 and Eq.
41 by
plugging in the Nash equilibrium (a "*)) (o"",,,")) Substituting the (n1 x²)) into ut (a plugging in the definition of the utility functions, for any i = 1, 2.... n, it holds that
2 wi (a
and
fl T
xxxx") fi = x x
(44)
for any w.. Also, for any i = 1, 1,2,..., n. it holds that
Sl n x (*) li , x xxxxx x*),,,
(45)
26

---

Published in Transactions on Machine Learning Research (01/2024)
for any X². Therefore,
max min fi .T', - (x)
fa xn , x" .x (1).
(46)
According to Corollary C.3
for any n², it holds that
V x xx x (s) Vi xx1))x
(47)
Also, for any x", it holds that
xin t xx x S nin x (s).
(48)
Thus, the stage-wise equilibrium defined in Definition C.4 exists for any E S.
C.3
Non-existence of Robust Total Nash Equilibrium
Theorem C.6 demonstrates the existence of a stage-wise equilibrium for any stale E S. In classic Markov
games Fink 1964p and Markov games with wwward/transttion uncertainties (Kardey et al. 2011 Nilim &
El Ghaoui 2005: Tyengar 2005), this result naturally extends to the existence of a Nash equilibrium policy, as all agents' and adversaries' policies are based on the current true state. If a stage-wise equilibrium exists for any state E S, then a Nash equilibrium can be constructed by taking the policies for each state from their corresponding stage-wise equilibrium for state s (Fink) 1964 Kardeş et al., 2011 Nilim & El Ghaoui 2005 Tyengar 2005). However, this natural extension cannot be used for our SAMG problem bocause the agent's 8 policy is based on the perturbed stale instead of the true state. The problem is that the agent's 's stage-wiss wise equilibrium in one state may not be consistent with its stage-wise equilibrium in different state. We illustrate this idea in the following theorem to show that the robust total Nash equilibrium does not always exist for SAMGs.
Theorem 4.7 (Non-existence of Robust Total Nash Equilibrium). For SAMGs with finite state and finite action spaces, the robust total Nash equilibriur defoned in Defimition 4.6 does not always exist.
Proof. We prove this theorem by showing that the following two-agent two-state game in Fig. 9 does not have a robust total Nash cquilibrium. The two-agent two-state game in Fig. is basically the same as the
a * a r
a
a # a r =
S
Sz
a² = a
Figure 9: A new two-agent two-state game example. Agents get reward 1 at state 81 they choose the same action. Agents get reward 1 at state if they choose different actions.
two-agent two-state game Fig. The only difference we changed the state transition for the state 81 The new state transition functions for the state 31 are
p(s' s2 $1 # a²) = 1,
p(s' = s1 = -11, = a²) = 1.
(49)
We first consider the stage-wise equilibriums for each state
For state $1, the stago-wisc cquilibrium requires Pr(at = af) for all One example the agent policy is I! (ag (s1) = n' (arls2) = x² (a)(s) = >²(a1 = 1. Note that the agent should have policy for both s and 82 even when considering the state-wise equilibrium for the state 81 (This means the current true state 81).
27

---

Published in Transactions on Machine Learning Research (01/2024)
This is because the adversary can perturb each agent's state observation to be 82. There is requirement for the adversary policy in the state-wise equilibrium because when Pr(a) = at) = 1, the true state never transits. The state value for $1 is ((s)) = 100.
Similarly, for state 82, the stage-wise equilibrium requires Pr(a) * aq} = 1 for all t. One example of the agent (22](2)) 1. There no requirement for the adversary policy in the state-wise equilibrium of 52. The state value for $2 is ((22) 100.
policy is (a1 = (a1 (82) (a2
Since the stage-wist wise equilibriums have conflict requirements for the agent policy in $1 and 82, there is no agent policy satisfying the requirements of the stage-wise equilibriums in both and 82 at the same time. Therefore, there is no robust total Nash equilibrium for agents in this two-agent two-state game.
In the proof of Theorem 4.7, we intended to present a straightforward example for ease of understanding, However, more counter-cxamples can be more illustrative in demonstrating the prevalence of non-existence scenarios. As long as the two stage-wise equilibriums have different requirements (not necessarily contrary to each other), there is no Nash equilibrium.
To elaborate, consider 2-state 2-action game. II, for state s the stage-wise equilibrium necessitates choosing action at with probability 0.2 and a² with probability 0.8, and for state $2, the stage-wise equilibrium requires choosing a² with probability 0.6 and a² with probability 0.4, then it's clear that no Nash equilibrium can simultaneously satisfy these requirements. This example illustrates the absence of a robust Nash equilibrium in such a 2-state 2-action game scenario.
Our conclusion similar to that of Theorem 4.3 in that is not always possible to find a policy that is a stage-wise equilibrium for all states. When facing adversarial state perturbations, trade-offs must be made among different states. As result, the traditional solution concepts of an optimal agent policy and the robust total Nash equilibrium cannot be applied to SAMGs.
C.4 Existence of Robust Agent Policy
We need to consider new objective that is not state-dependent. Thercfore, propose a objective, the worst-case expected state value, in Definition 4.8 as
Esg~Pr(so) [V=(s))]
where Pr(ss) is the probability distribution of the initial state.
The new objective of "worst-case expected state value" is designed specifically for the state perturbation problem present in SAMGs. It is proposed as response to analysis of the non-existence of widely-used concepts. We demonstrate that these concepts can be easily corrupted by adversaries, requiring agents to make trade-offss between different states. This is the reason for introducing the new objective. The agent policy that aims to maximize this worst-case expected state value referred to as a robust agent policy.
In this section, we show the existence of robust agent policy to maximize the worst-case expected state value. We first introduce lemmas for this proof.
Denote pd p (8:) the probability of reaching state given the agent policy n, adversary policy x, and initial state sg. Let pm (sp) 1. The connection between p and p (st) is:
p - ($1+1) =
Σ E Σ ((p(411lss (araa))))s -x00 EE
(50)
For concise representation, we omit the subscript s, of Pa, in this section. Consider the function
9t (T,)) = = Σ (s))
LEALEE a((a)p))x(oiss)))/mntt
(51)
28

---

Published in Transactions on Machine Learning Research (01/2024)
Lemma C.7. The function oi is continuous ((A) x ((P) for any 0,1,2...., where N_.
Proof. To prove the continuity, we construct some equivalent vectors follows. We define vector 7 E BlAIPP] and p) x(alp) for a E A, P, and vector X E R|P[SS] where x(p,s) = x(pls) for P E P, S. And vector constant F' |IS|IAI where F(s, a) = r(s,a).
(aalalllpp 10') x(a2\p1),, pla111) X )x. x(pl |st) x(p= ( (st)..... ..... x(plP1|sls)) }]
म (r(a"lp'), (
P. 1o= = st), ... , x (s: = [
(52)
Note that when $ Ps. then the entry x(pls) = 0. pe E R can be expressed as a linear combination of pr-1, 7 and & according to (50). Let's first consider the case = 0,
(T.)) = Σ E
(53)
POEP
Function 9 can be expressed as a linear combination of F. म and X. We consider the general case
9i t0 (T,)) = ΣΣ Σ p (s))
SES AEA PLEP
(54)
Function geeh can be expressed as a linear combination of F, and X- Therefore, ge" continuous on ((A) (P) for any 0, 2, where n E N+.
Lemma C.8. For any so E S, the series 1E (T. x) 1,2, ..., converges uniformly on A(A) A(P).
Proof. Consider Mt (T, x) 7² R where Rmaz the largest absolute value of the rewards. We can check that 19," (I, x)1 & M (T,, x) for 2 follows.
lst (H, x)1
ΣΣ Σ S:ES a P:EP
ΣΣ Σ p
9ESS EPPEP
= pmes x
ΣΣ
T-x.00 (s)
R.ES a.EA P.EP
= pmma x
ΣΣ Σ
at |s, T,))
RES PEP
=7¹ ..mer
x = M0000 (T,
(55)
Meanwhile,
66
Riaa
Σ 1=0
M 40 (T,))= = Σ
r pmar
(56)
t=0
29

---

Published in Transactions on Machine Learning Research (01/2024)
9t converges uniformly on A(A) x A(P) according to the Weierstrass M-test in Theorem 7.10 of Rudin
et al.
1976
Lemma
C.8 shows the series (Ei= 92 (T, x]}; n 1,2, ..., converges uniformly on A(A) x A(P) for any 50 E S. In the following lemma, we show Et gi (T, x) continuous on A(A) A(P) for any so 8. Denote o (IT, x) Ei=o 9 (T).
Lemma C.9. The function h continuous on A(A) x A(P) for any so E.
Proof. Consider h (TT, x) = EE (T, x) for n E N+. Since hn is linear combination of {9: 1t=0,1.2.... (T, and g," is continuous on A(A) x (PP) for any f t= 0,1,2,... according to Lemma C.7 the sequence (
is a sequence of continuous functions on ((A) A(P). Meanwhile, h + h uniformly on A(A) x A(P) for any 80 E S according to Lemma C.8 therefore h is continuous on (AA) A(P) for any 80 according
the uniform limit theorem in Theorem 7.12 of Rudin al. (1976).
The following theorem shows finding a robust agent policy is equivalent to solving maximin problem.
Theorem 4.10. Finding an agent policy æ to marimize the vorst-case expected state value under an optimal adversory for at is equivalent the marimin problem: max; miny Σ., Pr((o)
Proof. According to the Proposition 4.1 for any fixed agent policy æ, there exists optimal ad adversary policy x" such that (so) = miny (5)
(50) for any so E S. Thus,
max E Pr(so) [
min (5o max E Pr(so)
(Eq.
2
X
min V (80) Pr(so) max
(Definition of Expectation)
x
mnax min
Pr(so)V<xxX00 (80),
(Proposition 4.1
(57)
Finally, we show the existence of the robust agent policy to maximize the worst-case expected state value in the following theorem.
Theorem 4.11 (Existence of Robust Agent Policy). For SAMGs with finite state and finite action spaces, there exists robust agent policy to marimize the worsl-case expecled state value defined in Defivition 4.8
Proof. According to Theorem 4.10 finding an agent policy æ to maximize the worst-case expected state value under an optimal adversary for æ is equivalent to the following maximin problem:
max F(T)
max E Pr(sa) [V((s)
min Σ Pr(so)
max min J Jm, x),
(58)
where the objective function in 58 can be expanded follows:
J(T, x)
30

---

Published in Transactions on Machine Learning Research (01/2024)
Σ Pr(so)VaxXle Vxx(50)
Σ Pr(so) Bai 40
Σ
re+l (tt, ar) 80
2
Σ Pr(so)
T Ea [+ (+)) so]
4g
(linearity of the expectation)
Pr(ss)) ΣΣΣΣ E EEEPPE
p (8)))00(8)
a(a, d(alp)))(llss)))mmmm111
Pr(su) Σ (T,
t=
Pr(so)h
(59)
Because JTT, X) is a linear combination of } S is finite, and h000 is continuous on A(A) x A(P) for any so E according to Lemma C.9 the objective function J(T, = Emp Pr(so)h* is continuous on ((A) x A(P). Consider the function F(T) miny J x). Since the adversary policy space A(P) is compact, the function F is continuous in Mcanwhile, the agent policy space A(A) is closed. Therefore, there exists agent policy to maximize F according to the extreme value theorem.
Theorem 4.11 shows the existence of robust agent policy. Different from the definitions of the state-robust totally optimal agent policy and robust total Nash oquilibrium, the worst-casc expected state value objective does not require the optimality condition to hold for all states. Agents won't get sluck in trade-ofTs between different states, therefore, we can find a robust agent policy to maximize the worst-case expected state value for the SAMG problem.
Now look back at the two-agent two-state game in Fig. g If we use the worst-case expected state value concept from Definition 4.8 and assume that the initial state is always 82, then we can conclude that #1 r² (ails)) = x² (a1ls)) = n (a2lsi) = x² (ag(52) = 1 is robust agent policy, as it gives the maximum
worst-case expected state value of 100 for this game.
Robust Multi-Agent Adversarial Actor-Critic (RMA3C) Algorithm
In general, it challenging to develop algorithms that compute optimal or equilibrium policies for MARL under uncertainties (Zhang et al., 2020b 2021). Our algorithm adopts centralized training and decentralized execution paradigm following the popular framework in Lowe al. (017)). During training, there is a centralized critic Q(s,a) a) that records the total expected return given the global state and global action The connection between Q(+, a) and V(s) is that for any E N, S, A,
((s.a)=r(s.. + Σ p((s'ss.))V(ss)) EES
(60)
Each agent's state input for the actor is perturbed by an adversary (-(ss : - - A(P)). During execution, each agent i selects action a' based on the perturbed state of E S using a trained policy n' S + A(A'). We want to find a policy z for each agent to maximize the worst-case expected state value in Definition 4.8 under adversarial state perturbations.
As shown in Alg. ! our algorithm has a centralized critic network Q for training. Each agent has one actor network x' and one adversary network x The critic Q takes in the true global state and global action
31

---

Published in Transactions on Machine Learning Research (01/2024)
Algorithm 1: Robust Multi-Agent Adversarial Actor-Critic (RMA3C) Algorithm
Randomly initialize the critic network Q, the actor network x², and the adversary network x* for each agent;
Initialize larget networks Q', n² x²
for each episode do
The initial state 8u t- sample from Pr(so):
Initialize a random process X' for action exploration; for each time step do for i=1 to do p' - sample from (-Is);
9
a' < sample from x² (-lp") + X;;
end
Execute actions a= (at ...., -a'....,,"" a");
11
12
Obtain the reward and the next state s';
13
D + Ds,,,,,,
14
8-58; 8';
15
Q < MGD SaiD__Ottmizee44 D' x');;;
16
/* Mini-batch gradient descent optimizer for critic.
X GDA GDAADDDOOtttt PRtA__Opimizee(.....
18
/* Gradient descent ascent optimizer for policies.
19
Update all target networks: 8 + T8 + +1 -1-10 -)00
end
end
during the training process. It returns Q-value denoting the total expected return given s and a. The state transition experience is represented by (s, a, 8') where s' is the next state. It is stored in a replay bulfer D for the critic network's training. We apply 'replay buffer" and "target network' techniques (Mnih et al., 2015). The critic network trained with mini-batch gradient descent optimizer in line 15. In line 16, we use Gradient Descent Ascent (GDA) optimizer {Lin et al. 2020b) update parameters for each agent's actor network and adversary network for the maximin problem max, min, Σ Pr(so) (so) in Theorem 4.10 A detailed introduction for the GDA optimizer is included in Appendix E.4
We have added an adversarial network that inputs the true stale and outputs a perturbed state in RMA3C. This is in contrast to MADDPG and MAPPO, which do not include such a network. Compared to M3DDPG, which has a target policy network for each agent with outputs for the action space, our adversarial network's output pertains to the state space, indicating different computational load.
E Implementation Detail
All hyperparameters used in experiments are listed in table 3
E.1
Environments
We have tested our algorithm in environments provided by Lowe et al. 2017 as shown in Fig.
10
E.1.1 Cooperative navigation (CN)
This a cooperative task. There are agents and landmarks. Agents want occupy/cover all the landmarks. They need to cooperate through physical actions about their preferred landmark cover. Also, they will be penalized when collisions happen.
32

---

Published in Transactions on Machine Learning Research (01/2024)
Table 3: Hyperparameters for our RMA3C algorithm and the baselines.
Parameter
RMA3C
M3DDPG MADDPG MАPPO
optimizer for the critic network
Adam
Adam
Adam
Adam
learning rate for agent policy
0.01
0.01
0.01
0.0007
learning rate for adversary policy X discount factor replay buller size activation function number of hidden layers number of hidden units per layer
0.001
/
0.95
0.95
0.95
0.99
10
106
106
/
Relu
Relu
Relu
Relu
2
64
64
64
64
number of samples per miníbatch
1024
1024
1024
1
target network update coefficient
0.01
0.01
0.01
/
GDA optimizer steps radius
20
/
1.0
/
uncertainty level À upper boundary
0.5
0.5
0.5
0.5
1.0
1.0
1.0
1.0
lower boundary
-1.0
-1.0
-1.0
-1.0
episodes in training
10k
10k
10k
10k
time steps in one episode
25
25
25
25
a) Cooperative navigation
b) Exchange target
agent 1
agent
agent
agent 2
agent
c) Keep-way
d) Physical deception
agent 1
landmar
adversary
agent
agent 2
adversary
Figure 10: Some environments to test our algorithm, including a) Cooperative navigation (CN) b) Exchange target (ET) c) Keep-away (KA) d) Physical deception (PD). E.1.2 Exchange target (ET)
This a cooperative task. There are 2 agents and 3 landmarks. Each agent needs to get to its target landmark, which known only by another agent. They have to learn communication and get landmarks. Besides, both of them are generous agents that pay more attention to helping others, i.c. rewarded more if the other agent gets closer to the target landmark.
33

---

Published in Transactions on Machine Learning Research (01/2024)
E.1.3 away (KA)
This is a competitive task. There is 1 agent, 1 adversary, and 1 landmark. The agent knows the position of the target landmark and wants to reach it. The adversary does not know the target landmark and wants to prevent the agent from reaching the target by pushing them away or occupying the target temporarily.
E.1.4 Physical deception (PD)
This is a mixed cooperative and competitive task. There are collaborative agents, 2 landmarks including a largel, and adversary. Both the collaborative agents and the adversary want reach the larget, but only collaborative agents know the correct target. The collaborative agents should learn policy to cover all landmarks so that the adversary does not know which one is the true target.
E.2 Baselines
We compare the performance of our algorithm with MADDPG (Lowe et al. 2017j, M3DDPG (Li et al. 2019).
and MAPPO (Yu et al. 2022) and follow their open-source implementation. We have a brief introduction of these methods in the following sections. There is no robustness considered in MADDPG and MAPPO. The M3DDPG considers the robustness of Graining partner's policies, but it does not consider stale uncertainly. The MAPPO is the multi-agent. version of the Proximal Policy Optimization (PPO), popular policy gradient algorithm. Because MAPPO only works in fully cooperative tasks, only report its results in cooperative navigation and exchange target. Note that MAPPO is also used in Guo et al. (2020) but they do not provide
an open-source implementation. Therefore, we select the latest implementation Yu et al. (2022) with the open-source code.
E.3 Multi-Agent Deep Deterministic Policy Gradient (MADDPG)
It is difficult apply single-agent RL algorithms directly to the multi-agent because the environment's 's state transition is also influenced by the policy of other agents and it is non-stationary from single agent's 's view. To alleviate this problem and stabilize training, the MADDPG algorithm is proposed using centralized Q function that has global state and global action information (Lowe et al.) 2017). It assumes all agents are self relf-interested and every agent's ' objective to maximize its own total expected return. The objective for agent i is J((')= E[R]] and its gradient
Vo')(0') E ExDDD (Vo (o'''oo')VV (o')Va "".,""" "")==a"(==)))
(61)
where Q'(x, al "e....,a"') a²)) is centralized action-value function, x (o' (o'...., o²), and o' represents agent i's observation. The experience replay buffer D contains transition experience x, aa.,...a a", x rr,...,""" pd to decorrolate data. The centralized Q' can be trained using the Bellman loss:
L(0') ExarxxDly Q' "..""..."")) a,)) y y= + (x' " ...,
(62)
where Q" is the target network whose parameters copied from Q with delay to stabilize the moving target. Note that this algorithm adopts contralized training and decentralized execution paradigm. When testing, each agent can only access its local observation to select actions.
In M3DDPG (i et al. 2019), the uncertainty from the training partner's policies considered: all other partners are considered as adversarics that select actions minimize the total expected return of the training agent. In other words, when updating both actor and critic, they select training partner's actions by af = arg min Q'((x, a)).
34

---

Published in Transactions on Machine Learning Research (01/2024)
E.4 Gradient Descent Ascent (GDA)
Gradient Descent Ascent (GDA) Lin et al. 2020b is currently widely-used algorithm for solving the following minimax optimization problem:
min max fa. y).
(63)
GDA simultaneously performs gradient descent update the variable æ and gradient ascent update the variable y according to 664 with step sizes The and T/y
F++ = It. The V (Z 9t); Mt+1 y/ + Tly V yf (2,, Mt).
(64)
Tt has a variety of variants to accommodate different types of geometries of the minimax problem, such as convex-concave geometry, nonconvex-concav geometry, nonconvex-moncooeanr geometry, etc.
Cooperative navigation
Exchange target
Keep away
-7.5
400
-50
-10.0
-450
meen eaisode reNe
-100
mien egiiade roward
-12.5
-550
-15.0
micon caloode
155
-17.5
geriin RMA30
Aggrithnn
-200
MADDYG whth ue
MADOIG with robe
Agenthh
-700
with g*
MAUDFO
-750
MAFPO
MARRO
MIDOPG
HAFFC
MEDOPG with"
20
60
50
1.0
20
60
00
300
20
40
60
00
100
episodeik]
episode(k)
episadelk]
Figure 11: Our RMA3C algorithm compared with several baseline algorithms during the training process. The results showed that our RMA3C algorithm outperforms the baselines, achieving higher mean episode rewards and displaying greater robustness to state perturbations. The baselines were trained under either random state perturbations or well-trained adversary policy x" (adversaries that are trained for the maximum training episodes in RMA3C). Overall, our RMA3C algorithm achieved up to 58.46% higher mean episode rewards than the baselines.
E.5 Training Comparison Under different Perturbations
We first compare algorithm with baselines during the training process to show that our RMA3C algorithm outperform baselines to get higher mean episode rewards under different state perturbations. Note that our RMA3C algorithm has a built-in adversary to perturb states, so we do not train it under random state perturbations. Comparing RMA3C to other baselines with different state perturbations, the RMA3C gets higher mean episode rewards. It shows our RMA3C algorithm is more robust under different state perturbations. Comparing each baseline with random state perturbations to the same baseline with the well-traines adversary policy X", we can see the adversary trained by the RMA3C more powerful than the random state perturbations. Because the adversary policy x" intentionally selects state perturbations to minimize agents' total expected return. The mean episode reward of the last 1000 episodes during training is shown in Table 4 Our RMA3C algorithm achieves up to 58, 18.46% higher mean episode rewards than the baselines under different state perturbations.
E.6
Cooperative Navigation With Agents
We compare our RMA3C algorithm with basclines the cooperative navigation scenario with more agents added. The original cooperative navigation environment has 3 agents and the training results are shown
Fig. 4
We show the training results with 6 agents in Fig. T2 After increasing the total number of agents
35

---

Published in Transactions on Machine Learning Research (01/2024)
Table Mean episode reward of the last 1000 episodes during the training. Our RMA3C algorithm achieves up to 58.46% higher mean episode rewards than the basclines. The corresponding figure 11 and it also included in the main content.
CN
ET
KA
RMA3C (ours)
-00.77
-47.02
-8.93
MADDPG w/ N
-506.48
-63.76
-13.76
M3DDPG w/ N
-506.54
-61.71
-13.45
MAPPO w/
-569.07
-94.28
MADDPG W/ X" -548.80
-77.01
-16.30
M3DDPG W X" -54.999
-75.87
-16.26
MAPPO X -585.83
-113.19
Cooperative navigation with 6 agents
-3000
-300
mean episode reward
3400
-3000
-3800
4000
Algorithm
-4200
RMA3C
M3DDPS with
-4400
MAPPO with x
20
10
60
100
episode(k)
Figure 12: Our RMA3C algorithm compared with baselines during the training process in the cooperative navigation scenario with 6 agents added. Our algorithm gets higher mean episode rewards in the environment with an increased agent number.
in the environment, our RMA3C algorithm still gets higher mean episode rewards than baselines under adversarial state perturbations.
We also test the learned policies in the 6-agent Cooperative Navigation (CN) environment to show our RMA3C policy is more robust under adversarial state perturbations. During testing, the mean episode rewards are averaged across 2000 episodes and 10 test runs for each algorithm. We put all the well-trained agents using different algorithms into the 6-agent CN environment with well-trained adversary policies x" perturb states. The rcsult shown in Table Our RMA3C policy achieves up to 9.57% higher mcan episode reward than the baselines with well-trained adversarial state perturbations. The result shows that our RMA3C algorithm achieves higher robustness for multi-agent system under adversarial state perturbations.
F Discussions and Future Work
In this section, add several discussions of our work as a first attempt to study different solution concepts of the SAMG problem. We also point out several future directions for the SAMG problem.
F.1 GDA Convergence
In our RMA3C algorithm, we use Gradient Descent Ascent (GDA) optimizer (Lin et al. 2020b to update parameters for each agent's actor net work and the adversary network. Each agent updates the actor network lo maximize the worst-case expected state value in Definition 4.8] while the corresponding adversary updates the adversary network to minimize the worst-case expected state value. How solve non-convex non-concave minimax problem is a very challenging and not yet well-solved problem. To the best of our knowledge, the GDA optimizer is currently of the most widely used and accepted optimizers for this type of problem,
36

---

Published in Transactions on Machine Learning Research (01/2024)
Table 5: Mean episode rewards 2000 episodes during testing under well-trained adversarial state perturba- tions in the cooperative navigation environment with 6 agents. Our RMA3C policy achieves up to 9.57% higher mean episode reward than the baselines with well-trained X"
Environment
CN with agents
MADDPG w/x"
-3405.274 = 66.18
M3DDPG w/x"
-3452.22 + 80.16
MAPPO w/x"
-3121.90 + 18.49
RMA3C w/x"
-3079.37 = 16.16
Razaviyayn et al. 2020 Lin al. 2020b Our RMA3C algorithı with GDA optimizer shows performance improvement in terms of policy robustness in our experiments. Note that we only use the GDA optimizer as a tool in our algorithm by leveraging the existing literature on solving non-convex non-concave minimax problems. Future advances of numerical algorithms and solvers for this kind of minimax problem will also benefit our algorithm by replacing the GDA optimizer with new advances.
though it is not guaranteed to always converge (Jin et al.
2020
F.2 Non-Markovian Policy
In this work, we give the first attempt to focus on the Markovian policy under adversarial state perturbations. Dealing with the non-Markovian policy will significantly complicate the problem. We are aware of the suboptimality of Markovian policies, however, considering the computational cost of the non-Markovian policy of MARL, we decide to focus Markovian policies in this work for computational tractability. Moreover, shown in Proposition 3.2 our SAMG problem is different from Dec-POMDP. Considering non-Markovian policy based on the observation-action history may not give an advantage to the agents. For example, for the two-agent two-state game in Fig. g if the adversary randomly perturbs the state with x'(21182) = 0.5 for = 1,2, then the agents still only have a 50% chance to guess the true state even with observation-action history. Considering another example for the two-agent two-state game in Fig, S the adversary perturbs all states to state $1 with x'(s1[52) cannot get extra information for the true state even with observation-action history. We leave the formal analysis of non-Markovian, non-stationary policy as future work.
and (((s1(s1) for i 1,2, then the agents
F.3
Non-collaborative Game
In the problem formulation, we consider a collaborative game, where all agents share one stage-wise reward function. The new objective for the SAMG, the worst-case expected state value under state perturbations, is well-defined as proved in Theorem 4.11 For non-collaborative games, if each agent has its own reward function, and adversary i wants to minimize the total expected return of agent i, then for fixed agent policy æ, the n adversaries are playing a Markov game. In this case, only the Nash equilibrium exists among n adversaries, but optimal adversary policy may not exist. Therefore, for non-collaborative games, the worst-case expected state value is not well-defined. Even though the worst-casc expected state value not well-defined for non-collaborative games, the experiment results of the competitive games and game enviromments in Table T also show that RMA3C algorithm can get larger mean episode rewards in non-collaborative games under adversarial state perturbations. Hence, our RMA3C algorithm can increase the robustness of policies of non-collaborative games in empirical experiments. We leave the formal analysis of the non-collaborative games as future work.
37


Reviews:
[{"review_id": "ZxS8DG0kjd", "reviewer": "Reviewer_Gvvo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- The question studied in the paper is interesting because having robust MARL methods is of importance for applications. \n\n- There are both theoretical results and numerical experiments.\n\n- Generally speaking, the paper is well written. \n\nWeaknesses: \n\n- Some details need to be clarified.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies multi-agent systems under adversarial perturbations. The authors propose new notions of solutions, analyze them and then provide numerical experiments on several problems, including comparisons with several baselines from the literature. Overall, the main ideas are relatively well explained, although some details need to be clarified.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Questions:\n\n- (1) Page 5, equation (2): Could you please clarify how $s$ is taken into account? Does $\\bar{V}_\\pi$ depend on $s$? Or do you take the minimum over all states $s$?m\n\n- (2) Section 5: For the numerical experiments, could you please comment on the computational time of each method? Also, how did you choose the hyperparameters for the baselines? Did you sweep over hyperparameters to make sure you choose the values giving the best possible results?\n\nTypos:\n- Page 4: (??)\n- Page 8: “to ensure noise compact”", "broader_impact_concerns": "No particular concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pgrYDyjMVW", "reviewer": "Reviewer_cWut", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The investigated topic is quite interesting and relevant to the community. The paper is well written and easy to follow.\n2. The paper is well motivated and looks technically sound in terms of theoretical contributions and promising empirical results.\n\nWeaknesses:\n1. Some technical detail is missing, particularly when the authors mentioned in the paper that SAMG problem cannot be solved by existing solutions for robust Markov games and existing work for single-agent RL with adversarial state perturbations. The authors may have to add some more detail about the difference between the proposed SAMG and existing works.\n2. In this work, the authors assume the adversaries access the true state. Would this assumption be required always to apply SAMG? Also, in Definition 3.1, the authors include the true state inside the admissible perturbed state set. I am confused about this. Why couldn't exclude the true state from set, as long as it follows some constraints, such as the bounded distance between the true state and any perturbed state? How realistic is such a definition?\n3. To prove the Proposition 4.1, the authors need to construct an MDP. Why did the authors need MDP to show a conclusion stemming originally from SAMG? This is confusing.\n4. In the paper, the authors say \"When agent i is calculating its robust best response, it assumes a worst-case perspective of the state perturbations.\" Would such an assumption be strong and why?\n5. Though the experimental results look promising, the construction of the perturbed state set seems to fall back to just noise addition. But in the paper, the authors said adversary is not just noise. How did the authors construct such a set? Though we have known the difference between the true state and adversarial state is bounded by a constant $d$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "To address the issue of state perturbation in multi-agent RL (MARL) frameworks, the authors propose the state-adversarial Markov games (SAMG) and investigate the state uncertainty for MARL. Specifically, they first show the non-existence of optimal agent policy and robust Nash equilibrium in SAMGs. To overcome such a difficulty, they develop the concept called robust agent policy against the state adversary, which aims to maximize the so-called worst-case expected state value. They theoretically prove the existence of robust agent policy for SAMGs and on top of this framework, designing an algorithm Robust Multi-Agent Adversarial Actor Critic (RMA3C) to learn efficiently the robust policies for all agents under state uncertainty. To validate the proposed framework and solutions, they use multi-agent particle environments and a few baselines to demonstrate the superiority and robustness.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the above weaknesses to address the concerns and issues.", "broader_impact_concerns": "The authors may add one paragraph in the paper to address the broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZSB0DNbjAC", "reviewer": "Reviewer_7VyL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- The paper studies interesting nuances in using adversarial training methods in multi-agent domains\n- The paper contains a collection of useful existence and non-existence results about a collection of natural solution concepts\n- Overall, the paper is quite careful in its methodology\n- The theorems in the paper are all correct and important for practitioners to understand.\n\n**Weaknesses:**\n- My main concern is that a few of the definitions are quite confusingly named.  \n\nDefinition 4.2 is a very generic \"optimal agent policy\", though it is defined differently than I would expect. I would imagine the optimal agent to be one that \"maximizes the worst-case value function\". This makes much of the paper confusing, as the thing called \"the optimal agent policy\" is said not to exist, when the thing I would expect \"optimal agent policy\" to refer to clearly does exist.\n\nThe name used for the object in Definition 4.2 thus has to be made more specific for the paper to be easily understandable. I would suggest something like the \"state-robust everywhere optimal policy\" or the \"state-robust totally optimal policy,\" which would be unambiguous.\n\n\n- A similar concern holds for definition 4.6. The thing that is called the \"Robust Nash Equilibrium\" is not what I would call the \"Robust Nash Equilibrium\" since I would expect that to be \"no agent can unilaterally change its policy to more effectively maximize the worse-case value function\".  Again, this is confusing because the object I would call the \"Robust Nash Equilibrium\" does exist, and the object called the \"Robust Nash Equilibrium\" in the paper is shown not to. I would again suggest changing this to \"Robust Everywhere Nash Equilibrium\" or \"Robust Total Nash Equilibrium\".\n\n\n- Most of the theorems in the paper would follow from viewing the SAMG as an extensive form game under imperfect recall and applying the approaches used to analyze those games. They are still useful and represent a significant amount of work, as most readers will not be familiar with those approaches and the steps are carefully walked through in the appendix. However, it would at least be useful for the reader to reference this way of thinking.\n\nThe one result that does not follow from this perspective is Theorem 4.11, which would only be easy to translate in the finite case. Essentially, by imagining the the policy as a T sampled actions for each state, and then noticing that there must exist a Nash equilibrium in this game of selecting policies -- since it is finite Nash's theorem applies. The proof technique the authors use in the infinite case I have not seen before, and I would be interested in any reference to similar cases.\n\n**Minor Concerns:**\nThere are  a few typos, and missed references that make the paper more difficult to read than necessary:\n\"adversarial state\" -> \"adversarial state perturbations\" in the first paragraph\n- bad reference at the end of page 4, and in the proof of Theorem 4.10", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of learning a multi-agent RL policy that is robust to adversarial state perturbations. The paper shows solution concepts in this formalism must be nuanced as there is not a single policy that is optimal in every state, nor is there a set of policies that are in Nash-Equalibrium in every state. The paper proposes instead to look for a policy that has the optimal worst-case performance in expectation and proposes an algorithm to solve for it.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I request that the names of the \"optimal agent policy\" and \"Robust Nash Equilibrium\" be changed to avoid confusion.\n\nI would also recommend the Theorem statements are contextualized with references to similar proof techniques used in the study of imperfect recall in extensive form games, or other literature where relevant, so that the reader can more easily bring themselves up to speed.", "broader_impact_concerns": "There are no particularly worrying ethical implications of this work warranting a specific additional Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EMUeVdKnSw", "reviewer": "Reviewer_smAS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have not verified all of the proofs, but I am assuming they are correct.\n\nStrength:\n* The writing is clear and easy to follow.\n* The paper is very detailed and provides a comprehensive appendix.\n\nWeaknesses and questions:\n* Current experiments are limited to the small-scale particle environments. It would further strengthen the paper if the proposed method can be evaluated in more complicated environments.\n* The non-existence theorems (Theorem 4.3 and 4.7) depend on specially crafted example SAMGs. How the non-existence holds in general (e.g., with a random SAMG) is unclear.\n* The code is not in the supplementary material, unlike the authors have stated in Section 5.\n* In the last paragraph on page 7, why is the critic allowed to take in the true state? Shouldn't the agents be restricted to the perturbed states?\n* Is the setting of global state space a bit unrealistic for multi-agent RL? Can you give some examples for this setting?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of state-adversarial multi-agent reinforcement learning. The authors prove that optimal agent policy and robust Nash equilibrium do not always exist in the considered setting. To address this problem, this paper introduces a new solution concept called robust agent policy and proposes a Robust Multi-Agent Adversarial Actor-Critic (RMA3C) algorithm. The experiments on multi-agent particle environments demonstrate the effectiveness of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses\n\nMinor changes:\n* Broken references on page 4 (below Prop. 3.3).\n* Moving Figure 3 to the top might look more clear.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors greatly improved the manuscript during the review process. All the reviewers agree, and I concur, that the is a great fit for TMLR. For the camera-ready version the authors should clarify the experimental details, specifically related to the computational cost discussion and reviewer Gvvo's comments, which did not fully make it into the current version of the paper.
Decision: Accept (poster)