Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RL
Authors: Xiangyu Liu
Souradip Chakraborty
Yanchao Sun
Furong Huang
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement learning
adversarial policies
Primary area: reinforcement learning
TL;DR: In this paper, we reassess the threats posed to RL agents by adversarial policies and introduce a generalized attack formulation with the first provably efficient defense algorithm.

Abstract: Most existing works focus on direct perturbations to the victim's state/action or the underlying transition dynamics to demonstrate the vulnerability of reinforcement learning agents to adversarial attacks. 
However, such direct manipulations may not be always realizable.
In this paper, we consider a multi-agent setting where a well-trained victim agent $\nu$ is exploited by an attacker controlling another 
agent $\alpha$ with an \textit{adversarial policy}. Previous models do not account for the possibility that the attacker may only have partial control over 
$\alpha$ or that the attack may produce easily detectable ``abnormal'' behaviors. Furthermore, there is a lack of provably efficient defenses against these adversarial policies. 
To address these limitations, we introduce a generalized attack framework that has the flexibility to model to what extent the adversary is able to control the agent, and allows the attacker to regulate the state distribution shift and produce stealthier adversarial policies. Moreover, we offer a provably efficient defense with polynomial convergence to the most robust victim policy through adversarial training with timescale separation. 
This stands in sharp contrast to supervised learning, where adversarial training typically provides only \textit{empirical} defenses.
Using the Robosumo competition experiments, we show that our generalized attack formulation results in much stealthier adversarial policies when maintaining the same winning rate as baselines. 
Additionally, our adversarial training approach yields stable learning dynamics and less exploitable victim policies.

Published as a conference paper at ICLR 2024
RETHINKING ADVERSARIAL POLICIES: A GENER- ALIZED ATTACK FORMULATION AND PROVABLE DE- FENSE IN RL
Xiangyu Liu', Souradip Chakraborty', Yanchao Sun', Furong Huang! University of Maryland, College Park, J..P Morgan Al Research {xyliu999] (allllu999@unnee @udd...... edu
ABSTRACT
Most existing works focus direct perturbations to the victim's state/action the underlying transition dynamics to demonstrate the vulnerability of reinforce- ment learning agents adversarial attacks. However, such direct manipulations may not be always realizable. In this paper, we consider a multi-agent setting where well-trained victim agent is exploited by an attacker controlling another agent a with an adversarial policy. Previous models do not account for the pos- sibility that the attacker may only have partial control over a or that the attack may produce easily detectable "abnormal" behaviors. Furthermore, there is a lack of provably efficient defenses against these adversarial policies. To address these limitations, we introduce generalized attack framework that has the flexibility to model to what extent the adversary is able to control the agent, and allows the attacker regulate the state distribution shift and produce stealthier adversarial policies. Moreover, we offer a provably efficient defense with polynomial conver- gence the most robust victim policy through adversarial training with timescale separation. This stands in sharp contrast to supervised learning, where adversarial training typically provides only empirical defenses. Using the Robosumo com- petition experiments, we show that our generalized attack formulation results in much stealthier adversarial policies when maintaining the same winning rate as baselines. Additionally, our adversarial training approach yields stable learning dynamics and less exploitable victim policies
INTRODUCTION
Despite the huge success of deep reinforcement learning (RL) algorithms across various domains (Silver et al. 2017 Mnih al. [2055] (Schulman et al.) 2013). has been shown that deep reinforce- ment learning policies are highly vulnerable to adversarial attacks. That is, well-trained agent can produce wrong decisions under small perturbations, making risky to deploy RI. agents in real-life applications with noise and high stakes. The most popular attack methods focus on fooling the RL agent by adversarially perturbing the states, actions, or transition dynamics of the victim (Huang
et al. 2017 Pattanaik al. 2017 Zhang al. 2020b; Sun et al. 2021 Tessler et al. 2019).
However, in practice, many applications, such as air traffic control systems, are well-protected meaning that direct perturbations to the observations actions may not always be feasible. For instance, to perturb the readings of an air traffic control radar, an attacker might need to physically manipulate the sensor or infiltrate the communication system, tasks that can require significant effort. efforr. In this context, our paper explores attacks on a vietim agent, 2, executed by an attacker controlling another agent, a, in the same environment. Specifically, in the air traffic control example, an attacker could manipulate a commercial drone to interfere with the radar system of the victim. The strategy employed by the attacker in this scenario is known as an "adversarial policy".
Previous works (Gleave et al. 2019 Wu et al. 2021b; Guo et al. 2021) have adopted principled approaches to attack well-trained RL agents by developing an adversarial policy to directly minimize
Coodes available at http:///tht.aaaaaaaaiiiieeiiieee

---

Published as a conference paper at ICLR 2024
the expected return of the victim. These methods have effectively defeated ttate-of-the-an agents trained through slay (Bansal et al. 2018). even when the adversarial policy has been trained for less than 3% of the self-play training time steps. However, existing models do not adequately address situations where the attacker might face resistance and only achieve partial control, which also lead to conspicuous behaviors. Despite the common occurrence of such attacks, provably efficient defenses are not well investigated yet.
To address these issues, our generalized attack formulation introduces an "attack budget", effec- tively capturing the attacker's partial control. This metric accurately reflects the attacker's capacity to degrade victim's 's performance. Within this framework, the attacker can self-regulate the attack budget, aligning with state distributions (Gleave et al.. 2019) and marginalized transition dynam- ies (Russo Proutiere, 2021] Franzmeyer et al.; 2022 to craft stealthier, less detectable attacks. Notably, our attack model extends single-agent action adversarial RI. (Téssler et al.) 2019) to multi- agent setting. On the defense side, merely retraining the victim agent against specific strong attacks may not necessarily improve overall robustness; in some cases, it could even worsen performance against other potential attacks. We propose an adversarial training algorithm featuring timescale separation, which avoids overfitting to specific attacks and focuses optimizing the agent's worst- case performance. Unlike existing methods of timescale separation in GANs and adversarial training in supervised learning, which may converge local solutions (Heusel al. 2017) or provide only empirical defenses (Madry et al. 2017]] (Shafahi et al., (019), our algorithm converges to the most robust policy globally, offering defenses with provably efficient guarantees - even in the face of the problem's 's non-convexity and non-concavity.
Our key contributions in the realm of both attack and defense are summarized as follows. (1) We introduce a generalized attack formulation that captures the "partial control" of the attacker. This formulation allows for stealthier attacks and extends the concept of action adversarial RL more generalized settings. (2) We address the issue of non-convergence in adversarial training within our attack framework. By incorporating the principle of timescale separation, we achieve provable defenses and ensure theoretical guarantees for convergence to the globally most robust policy. (3) Empirical results affirm the efficacy of our generalized attack formulation in minimizing state dis- tribution shifts and generating stealthier behaviors, compared bascline unconstrained methods. Additionally, in tasks like Kuhn Poker and Robosumo, our timescale-separat adversarial train- ing demonstrates superior stability and robustness when compared to popular baselines, including single single-timescale timescale adversarial training, self- eelf,pla, and fictitious-play
PRELIMINARIES ARIES
The extension of Markov decision processes (MDPs) with more than one agent is commonly mod- eled as Markov games (Littman 1994). A Markov game with N agents defined by a tuple J G ><< N,S, [A: P. (r:): i= P. >, where S denotes the state space and A; is the action
space for agent i. The function P controls the state transitions by the current state and one action from each agent: P: S x Ai x... x AAN + A(S), where A(S) denotes the set of probability distributions over the state space S. Given the current state st and the joint action (aI,.... aN) the transition probability to 8141 is given by P(s St, 01, ax). The initial state is sampled from the initial state distribution p E A(S). Each agent also has an associated reward function AN [0, 1]. whose goal is to maximize the y-discounted expected return
S:S x Ai o als "), where -i is a compact representation of all complementary agents of i.
In Markov games, each agent is equipped with a policy म; S ((A:) in policy class πI, and Specifically, the value function for the victim
the joint policy is defined as π (als)) NT 1= (a, (
agent v given joint policy (Tv, Ta) is defined by (TT, na) = ET,,. EDi 7'rr ar) so s], where agent y attempts to maximize the value function and attacker aims to minimizes it. We abuse the notation to use VT Ta) == EV
Ta).. We further define state visitation, which reflects how often the policy visits different states in the state space.
Definition 2.1. (Stationary State Visitation) Let d E A(S) denote the normalized distribu- tion of state visitation by following the joint policy π in the environment: (s) = -11 T) E PTT (st = =s(s)).
3 A GENERALIZED ATTACK FORMULATION
Problem description. For simplicity, we consider a multi-agent system with two agents, // and a, following policies क. and म. respectively. The interactions between these agents can be cooperative,
2

---

Published as a conference paper at ICLR 2024
competitive, mixed. As motivated earlier, we consider the attack scenario as described in Gleave jet al. (2019); Wu et al. (2021b): Guo et al. (202I), where the threat comes from an attacker control- ling agent a. This attacker deviates from To to adversarial policy ... aiming to minimize the performance of the victim agent v. Correspondingly, the victim's 's goal is to develop a more robust policy Ty in anticipation of such adversarial policies. The interaction between the attacker and the victim can thus be modeled as a zero-sum game, regardless of the initial relationship between the P This framework can also be extended settings with more than two agents, where the attacker controls multiple agents and adopts joint adversarial policy.
two agents
Attack formulation. Although such attacks can effectively exploit the victim, in many practical scenarios, unlike the attacks in Gleave et (2019); Wu et al. (2021)): Guo et al. (2021), the attacker may face resistance and achieve only partial control of agent a, e.g., hijack scenario. Therefore, we propose more generalized attack framework. Here, the attacker aims to manipulate agent using an adversarial policy a.. but may not fully control the agent, which can still follow its original benign policy n. with probability 1 e, at each time step, where Enr [0, 1]. Formally, under these conditions, the attacker solves the following attack objective:
min Va(TTe Na)
(3.1)
S.L.
Ta (1- + (.))))
Vs E.
(3.2)
Objective 3.1 is a standard attack objective (Gleave et al. 2019 Guo et al. 2021 Wu et al. 202
focused on minimizing the value of the victim v. The additional constraint 3.2 captures the prob- ability 6x at which the attacker can control agent a. When ex 1. the setting degenerates to full control, aligning with Gleave et al.] (2019; Guo et al.] (2021); Wu et al. (202 Conversely, at 6x O, no attack occurs. This probability, denoted as the attack budget, effectively models the resistance encountered by the attacker. Its suitability as a budget will be further connected to action adversarial RL later (Tsssler et al. 2019).
(a) Effects of the attack budget. Our proposed attack budget effectively characterizes the vic- tim's performance degradation, serving as viable measure of agent vulnerability. To substantiate this, we note a key observation related to a standard discrepancy measure (Kakade & Langford Schulman et al., 2015).. Given the constraint in Equation 3.2 for any To. the inequality D Ta (a) < En holds. Here, DTVX ||aa) is defined as max. Drv (Ta (-Is)][fa and Drv(plla) == = Ex p;; -gl. This observation allows us to establish an upper bound on the victim's performance under an attack budget of 6z. ex.
2002
Proposition 3.1 (Bounded policy discrepancy induces bounded value discrepancy). For two policy pairs (#y R.) and (Ty, such that D (Tall S cn the difference between the victim value can be bounded as: (fy, Rt) - (T Fa)l S 26
(1-7)².
This establishes a link between the attack budget and IV,(T,, Ra) 1 -V,(7,, Ta)l. Specifically, the value function inherently satisfies a global Lipschitz condition. This implies that the attacker needs a sufficiently large attack budget en to cause significant degradation in performance. This contrasts with supervised learning attacks at test time, where small perturbations can result in large perfor- mance shifts. Although this is worst-case upper bound and may not be tight especially when is close to 1 - it still indicates that a longer effective game horizon grants the attacker greater capacity to degrade the victim's performance.
(b) Attack model's stealthiness and detectability. While the unconstrained attack in Gleave et al. (2019) significantly impairs the victim's 's performance, its overt nature makes it easy to detect even through static images. This deviates from the stealthy ethos of adversarial attacks in supervised learning (Goodfellow et al. 2014). In contrast, our generalized attack framework allows for par- tial control of an agent and enables stealthier attacks by regulating the attack budget 67. Specif- ically, leveraging insights that static images alone can reveal attacks, we use generative modeling techniques for distribution matching to align the state distributions dft..āa and d dit induced by (#.. R.)) and (f,, Ta) respectively. Though exact state visitation is difficult to compute, regulating G allows us manage the discrepancy between these distributions. We adopt total variation distance as our measure of discrepancy, offering the following guarantees.
EEve if क. and R. are trained competitively, successful attacks can still occur due to sub-optimality of training Gleave et al. (2019; Bansal (011
3

---

Published as a conference paper at ICLR 2024
Proposition 3.2 (Bounded policy discrepancy induces bounded state distribution discrepancy). Fix
any 6x E [0. For two policy pairs (uv. and (Ry, Ta) such that DTy (Ta discrepancy between the state distributions can be bounded as: [|dBu. daviRo 1-7"
Taa) I 6x. the
276r_
Proposition 3.2 demonstrates that as long G is sufficiently small, the state distribution is well preserved, thus yielding images that are visually more similar to the original ones. This suggests that in practice, εx can be treated as hyper-parameter, balancing the attacker's performance with stealthiness. Finally, comparing actions or rewards is also a viable method to detect potential attacks. However, in many practical multi-agent systems, agents are decentralized, and actions or rewards are private to each agent (Zhang et al. 2018b), not always available to humans aiming to detect potential adversarial attacks.
Comparison with single-agent stealthy attacks. Russo & Proutiere (2021): Franzmeyer et al. (2022) consider stealthy attacks in a different setting, involving adversarial state or action perturbations, within single-agent RL. Their concept of unstealthiness or detectability is predicated on the incon- sistencies in the transition dynamics when states or actions are adversarially perturbed, necessitating an accurate world model. However, in our scenario, even if such a world model ís accessible, the (global) transition dynamics P remain unaffected by the adversarial policy. Concurrently, compar- ing the marginalized transition dynamics induced by a and Ta is plausible from the perspective of the victim v. Based on Proposition 3.3 inconsistencies in the marginalized transition dynamics can also be upper-bounded by the variation in the policy space, assuring low detectability considered in Russo & Proutiere| 202T); Franzmeyer et al. (2022). Thus, even if humans or detectors can ac- cess the private actions of the agent y and establish accurate corresponding marginalized transition dynamics, discrepancies might remain undetected as long as e is maintained minimal.
Proposition 3.3 (Bounded policy discrepancy induces bounded marginalized transition dynamics inconsistencies). We define the marginalized transition dynamic of agent as PT (s' | s,ay) == (. 8, aas ]u) for given Ta- Pă" is defined similarly for the policy Tea Then for any s and a E Av, we have D, (P7 (:18,ap) av) || P. az)) S Dy (-(-)s)) (-)))))) where Dj is any f-divergence, which includes Dry. connecting back to the attack budget.
(c) Connection to action adversarial RL. Intriguingly, our attack formulation also extends the single-agent action adversarial RL (Tessler et al. 2019) to a multi-agent setting. Specifically, in PR-MDP (cf. Definition 1 of Tessler et al. (2019)), the policy under attack aligns with our Equation 3.2 In the context of single-agent action adversarial RL, the policy Ta is only a part of the finally executed policy, while the policy f. represents the victim. Thus, our formulation broadens the attack setting Tessler et al. (2019) to multi-agent RL, considering the other agent v as the victim instead of the agent itself. Moreover, determining the most robust policy for the victim using the policy iteration scheme for PR-MDP from Tessler et al. (2019) becomes inefficient in our context due to the absence of specific structures inherent in PR-MDP (Section 4 Tessler et al. (2019). ).
Henceforth, we will abbreviate 7o as To without ambiguity, and the actually deployed policy for agent a is represented as (1 cx) aa + T.. Detailed proofs and discussions related to this section are available in $
4 IMPROVED ADVERSARIAL TRAINING WITH TIMESCALE SEPARATION
On the necessity and challenge of provably efficient defenses. As discussed before, to provide effective defenses. there are unique challenges standing out compared with single-agent robust RL (Tessler et al., 2019). Mcanwhile, finding the celebrated solution concept Nash Equilibrium (NE) between the attacker and the victim suffices for finding the most robust victim policy during robust training but may not be necessary since NE guarantees that the attacker is also non-exploitable. We provide more detailed discussions on the relationship between NE and robustness in $ There are bunch of existing works solving NE for structured extensive-form games (Lockhart et al. 2019 Brown et al., 2019 Sokota et al. 2022) or for general games but without provably efficient guar- antees (Fudenberg & Levine 1995 Lanctot et al., 2017] Balduzzi al., 2019 Muller et al. 2019). In practice, general game- theoretical methods often require solving best response problems itera- tively, thus being computationally expensive. In theory, simply plugging in black-box NE solvers
4

---

Published as a conference paper at ICLR 2024
may not solve problem with provable efficiencies since finding even local NE for general nonconvex nonconvex--ooncoecvve nonconcave problem is computationally hard (Daskalakis et al. 2021). Therefore, in- stead of adopting a black-box game theooretttttal solver, we investigate adversarial training, a popular
and more efficient paradigm for robust RI. (Pinto et al. 2017 Zhang et al., 2021a Sun et al. 2021
There are prior works that utilize well-trained attacks for re-training fortify the robustness of the victim (Gleave et al. 2019; Guo et al.) 2021] Wu et al.) 202 However, it has been demonstrated that while re-training against a specific adversarial policy does augment robustness against it, the performance against other policies may be compromised as validated by Gleave et al. (2019). In- tuitively, if the victim is retrained against specific attacker, its policy might be overfitted to that attacker. Thus, it is vital to uphold the performance of the victim against all potential attackers. Rather than merely re-training against specific attacker, adversarial training methods have been shown to be effective in bolstering robustness against broad spectrum of adversarial attacks. In these methods, the victim and the attacker are trained alternatively or simultaneously (Zhang al.] 2020b, Pinto et al., 2017). Here, we re-examine adversarial training in the RL domain and demon- strate that prevalent adversarial training methods encounter a non-converging problem with either alternative simultaneous training, for which we defer examples and detailed discussions to $ To address these issues formally, we contemplate the robustness of the victim and define the ex- ploitability of ny under the worst-case attack follows.
Definition 4.1 ((One-side) exploitability). Given Gr E [0.1] and Ra. for victim policy ny. measure the robustness of nu by: Expl(T>) = minn, Vp(TT. (1 -1-c0 C )a + C )
Intuitions of timescale separation. The smaller Fx,I(TT,) is, the more robust ny is. Therefore, to ensure the worst-case performance against the strongest adversarial policy, the victim should opti- mize the policy according to min,, Exp((xz). Ideally, if we can derive an analytical form of the function Expl(-) compute its gradient, then we can simply Unfortunately, it is not obvious how to derive an analytical form and the function may not be even differentiable, let alone computing the gradient since the function relies on solving minimization problem. However, is possible to first solve the minimization problem, getting T and compute the gradient w.r.t Tu. namely V V2 (1 - Ex Ra + E, m as if nā is fixed, hoping could serve as a good descent direction. Formalizing this intuition, we propose to improve adversarial training via timescale separation with Min oracle (shown in Algorithm D. where timescale separa- tion comes from the fact the attacker takes min step against the victim in line 3 while the victim takes only one gradient update in line 4. Note Lockhart et al. (2019) also considers directly minimiz- ing the exploitability function but the algorithm and analysis are only applicable to extensive-form games. Finally, we remark that Algorithm [ is consistent with the leader-follower update style that is developed for Stackelberg equilibrium in multi-agent RL Gerstgrasser & Parkes 2023).
gradient descent to optimize it.
Algorithm Adversarial Training with Min-oracle
1: Input: random policy T.. learning rate sequence {π²²
2: for = 0 to T do
3: T/ 4- arg minx, Vo(Ti (1 -1-66 - + Ca))
4: nf+1 - Pu, (1t, + + Vo(= (1 - (11=())o, x²) + <=T)). // projection onto the simplex
5: Output: sample T. with probability proportional to 17².
Efficient approximation. The min oracle used in Algorithm I can be implemented with standard RL algorithms like PPO. When the game has special structures like extensive-form games (Lockhart) ct al., 2019) or one agent has a substantially smaller statc/action space, such min oracle can be even implemented quite efficiently. However, in general, to make one gradient update for agent v, agent a needs to compute a complete best response, which is computationally expensive in practice. To fix this issue, we utilize the idea of using a much faster update scale for agent a so that when agent v performs the gradient update, the policy = is always and already an approximate solution of arg minx,, Vo(Ti, (1 Ex ) + T.).). Formally, in addition to Algorithm [ we present an alternative efficient Al Algorithmm] [ where the min oracle is replaced by a gradient update with larger step size and both agents only need to perform gradient update independently. Therefore, our final algorithm is simple and compatible with standard RL algorithms, like PPO to implement the gradient update step for both agents, avoiding solving best responses at each iteration under popular
5

---

Published as a conference paper at ICLR 2024
game-theoretical approaches (Fudenberg & Levine
1995- Lanctos et al. 2017 Balduzzi al. 2019
Muller et al. 2019.. To validate our intuitions and verify that our algorithms do provide provably efficient defenses, shall prove the convergence guarantee of both algorithms in the next section.
Algorithm 2 Adversarial Training with Two Timescales
1: Input: random policy my. T learning rate sequence {n (nal such that nú & the
2: for = 0 to 7 do
m++1 <- Pu. (T n V Vo (1- ) tx
4: mf+1 Pu, (T + Th V. V V (1 G + (z7()).
5: Output: sample ni with probability proportional to ny.
THEORETICAL ANALYSIS
To understand and verify approaches, start by considering direct policy parameterization for both agents v and o, which is already challenging due to the non-convexity, non-concavity, and serves the first step analyze complex function approximations.
Definition 5.1 (Direct parameterization). The policies Tr and Ta have the parameterization (a Vs.a- Ta(a as,ar where v E (8) and a E A(AA))s)
For convenience of discussions, given c and aa. we will write Je, (Ty, Ta) := (T (1-c,) a. Before proving the convergence of our methods, we define the mismatch coefficient to measure the intrinsic hardness of the environment. This is achieved by comparing the stationary state occupancy frequencies under certain policies against the initial state distribution. In simpler terms, a smaller value of this quantity indicates that the environment is more easily explorable.
Definition 5.2. Given the Markov game G, benign policy Ra. and attack budget cn we define the minimax mismatch coefficient as
d (1-ex 1
Fu ( ) Ten
CF
max
min
min Sl (x))
WwEll,
where IT; (mv) = arg min ETT Je, (To, Na), and IT; (Ta) = arg max ETT, Je, (TeD na).
With those two definitions, we can analyze how the robustness of the victim improves during adver- sarial training follows:
suppose the learning rate nu x 5, after T iterations, is guaranteed that 1 Σ Expl( S ming, Expl(T)) + 6, where T = I 82 poly(C5" (|S), Aal, lAvl 14):: while for Algorithm 2 suppose the learning rate ni x 58, n x
Theorem 5.3. Fix any 5 > O. [0, 1). For Algorithm
84, after T iterations, it is guaranteed that T ET= (xpp((x)) I min., Expl(TT) + 5, where T p)ly(} CG [Aa), |Avl. 1-g)
Remark 5.4. To get a non-vacuous finite time convergence, the mismatch coefficient needs to be bounded, which is standard and necessary in the analysis of policy gradient methods (Daskalakis et al.) 2020; Agarwal et al. 22021), where our definition of C is based on the definition in DDakaatkıss et at. 20200. It worth noticing that such an assumption is weaker than other sim- ilar notions such as concentrability (Munos) 2003 Chen & Jiang 2019), without requiring every visitable state be visited the first time step.
Implications. This theorem demonstrates that, on average, the victim policy =f. is assured con- verge the most robust one; that is, the solution of arg maxa, min,,, Vo(Tu, (1 e, ) eTT.) ) Theorem 3.33mmm33111 reveals that Algorithm Jachieees better iteration complexity owing to a larger learning rate. Meanwhile, the convergence for Algorithm 2 also substantiates the necessity of timescale sep-
aration due to n & yf.-- To the best our knowledge, the analysis for Algorithm is new, even for the e 1 case, and the analysis for Algorithm leverages Daskalakis et al. (2020) Jin at 2020);

---

Published as a conference paper at ICLR 2024
Feature28
5
Orighs Atack
Feature11
0.25
Ofgirll Locd Klack
Feature32
10
Lacn Aracs
Orginn
0.00
-0.25
0
-0.5
0.0
0.5
-10
0
10
Feature
Feature
Feature
Feature28
5
Origial CantalARace
Feature f1
0.25
Fealure32
10
Greaa Araos
Olggnal
0.00
-0.25
Feature
Feature_10 10
Feature
Figure 1: Visualization and comparison of our proposed constrained attack with E, 0.2 (first row)
vs. an unconstrained attack (second row, E = 1), under the condition that both achieve the same attacking success rate. The most important state features are shown. clear that our constrained adversarial policy induces much smaller state distribution shifts.
Zhang et al. (2021b) but addresses the more prevalent discounted reward setting without assuming the game to cease at every state with a positive probability. It also permits the attacker to exert only partial control over the agent a within any stipulated attack budget éx- Importantly, our theorem can be readily extended to encompass results of last-iterate convergence using the regularization techniques highlighted in Zeng et al. (2022) and stochastic gradients by deploying popular gradient estimators from finite samples, with the central concept remaining timescale separation. Detailed proofs are available in $
RELATED WORK
Stealthy adversarial attacks in RL. To render attacks on RL policies more feasible and practi- cal, cal.[Sun et al. (2020) demonstrates that targeting critical points can facilitate efficient and stealthy attacks. Russo Proutiere (021) optimizes both attack detectability and victim performance, an- alyzing the tradc-off between them. Franzmeyer et al. (2022) introduces an illusionary attack that maintains consistency with the environment's s transition dynamics, necessitating a world model. The aforementioned stealthy attacks focus on perturbing the victim's 's state observations/actions In con- trast, this paper presents generalized attack framework for multi-agent systems, allowing for stealth by managing the attack budget, wherein the attacker indirectly influences the victim by altering an- other agent's ' policy.
Timescale separation for adversarial training. Adversarial training is widely-adopee method for cultivating models robust against adversarial attacks. The efficacy of timescale separation in this context has been empirically affirmed; having increased loops for the inner attack subroutine trans- lates to enhanced robustness Madry et al. (2017); [Shafahi et al. (2019). Likewise, in training GANs (Heusel et al. 2017). utilizing larger learning rate for the discriminator surpasses conventional GAN training and ensures convergence to a local NE. Moreover,[iee, & Ratlifi (202T) explores more general non-convex non-concave zero-sum games and elucidates the local convergence to strict local minimax equilibrium with finite timescale separation. Contrarily, our adversarial training algorithm assured to converge to the (globally) most robust policy.
7 EXPERIMENTS
Our experiments utilize two standard environments: Kuhn Poker (uuhn 1950 Lanctot et al. 2019) and RoboSumo (Al-Shedivat et al. 2017). Detailed introductions to these environments, implemen- tation specifics, and hyper-parameter are outlined in $E Unless specified otherwise, the results are averaged over 5 seeds. In this section, we seek to address the following pivotal questions:
> Q1. Can our generalized attack formulation produce fewer state distribution variations and more stealthy behaviors compared to unconstrained attack?

---

Published as a conference paper at ICLR 2024
rog Exolotabiity
Senta
Number cptsodes
Numberof sodes
Number opisades
Number colsodes
Number of spisodes
(a) Exploitability of the victim when using RPG for policy gradient.
Nimber epandes
Nimber sodes
Number expendes
Number epprndes
Namber epixndes
(b) Exploitability of the victim when using A2C for policy gradient.
Figure 2: Exploitability of victim policy in Kuhn Poker trained by two timescale and single timescale (min indicates the policy trained with a min oracle).
Q2. Will adversarial training with timescale separation (involving a min oracle and two timescales) exhibit more stable learning dynamics, and can the two timescales algorithm ef- fectively approximate the adversarial training with min oracle?
D
Q3. In complex environments, where min oracle may not be available, can adversarial training with two timescales enhance robustness compared to prevalent and acclaimed baselines?
Controllable adversarial attack (Q1). We conduct experiments environment. To verify that our attack formulation indeed achieves smaller state distribution variations, strained policy with the same winning rate for fair comparisons. Specifically, we in- vestigate the distribution shift in the victim's observation part of the state features. To select essential state features, we employ the variance- based feature importance method to filter out state fea- tures with small variances as they are deemed unimpor- tant. The sorted feature importance for the RoboSumo games is depicted in Figure E.2] Figure [ demonstrates that the adversarial policy, derived from our generalized attack framework, induces much smaller state distribu- tion shift compared to the unconstrained adversarial pol- icy when assessed under the same winning rate. Addi- tionally, we quantify the state-distribution shift brought about by the constrained and unconstrained attacks by calculating the Wasserstein-2 distance between their state distributions, illustrated in Figure Our constrained attack results in significantly lower state distribution shift compared to the unconstrained one. To confirm that our generalized attack methods, with a regulated at- tack budget, do indeed produce more stealthy behaviors, we visualize agents with & E 0.3, 0.7, 1; here, a smaller e, induces behaviors that are visually more similar the system without an attack (see gifs ltttss://sites. wwogll..comvieewee com/viewwstealtthy attack). An ablation study on the trade-off between stealthiness and the attacker's performance is also presented in $E.4. also validating the effectiveness of 6x in regulating the attacker's strength, in line with Proposition 3.1 We show in $E.4. even when there is mismatch for attack budgets between training time and test time, the vietim policy still shows greatly improved robustness.
the Robosumo
choose an unconstrained adversarial policy and
attack
Skool
Lecel.
400
Local
300
200
100
Art vst Artt
Big ve Envrerment
Scear vs Spider
Figure 3: State-distribution shift w.r.t Wasserstein-2 distance (squared) in- curred due to the Global (E₃ = 1), Lo- cal (Eą = 0.7), Local 2(e, 0.3) at- tacks in 3 Robosumo environments.
Adversarial Training with Timescale Separation (Q2&3). To address Q2&3, examine the learning dynamics and robustness of policies trained with and without timescale separation, com- paring these to other baselines in both Kuhn Poker and Robosumo environments.
Kuhn Poker. We implement Algorithm I and under OpenSpiel (Lanctot et al. 2019), with the min oracle achieved through game tree search. For gradient update, utilize Regret Policy Gradient (RPG) (Srinivasan et al.) 2018) and Advantage Actor-Critt (A2C) (Mnih et al. 2016) in lieu of the vanilla policy gradient. Figure illustrates the exploitability of the victim policy nys where adver-
8

---

Published as a conference paper at ICLR 2024
Vid Sron
Send
Card
(a) Score of the victim policy, which is computed by winning rate + tie rate/2. Note here different from other plots. to show the potential oscillation behaviors during training, we show just one seed instead of multiple ones.
Gradient Norm
Gradiien Norm 1 1 1
Gradient Norm
ut Se
Number of Berations
Number ofltetations
Numrittt of Retations
(b) Norm of the gradient Va (T at). Epoilon
Epsiion=1
Epction 0.3
led
Alte
Number of Timesteps
Number Timesteps
(c) Score of the attacker against robustified policy (final output of adversarial training). Lower is better.
Figure 4: (a). The score of the victim policy trained with two timescales converges rapidly, while the policy trained only with single timescale suffers from much more oscillations. (b). The gradient norm trained by two timescales is also much smaller. (c). Under different e, = 1, 0.7, 0.3, when attacking the robustified vietim policy, i.e. computing minz,, VA (1 ( + with standard RI. algorithm, victim trained by two timescales achieves the lowest exploitabilityyhest robustness.
sarial training with the min oracle exhibits the fastest convergence, lowest exploitability, and least variance. Meanwhile, policies trained with a sufficient timescale separation parameter / closely approximate the algorithm with min oracle, outperforming single timescale algorithms.
Robosumo Competition. To demonstrate the scalability of timescale separation, we evaluate our methods on Robosumo-a a high- -igeeniiensin,,,, continuous control task, representing a significant challenge in terms of both training and evaluation. Although a min oracle with game tree search is unattainable in such a continuous control task, earlier experiments suggest that an ample timescale separation ratio can effectively approximate it. We monitor the score, Vo(T, (1 ) ao (T)) +G and the norm of gradient V.,, (T (1 ex ) + TT)TT during adversarial training. As per Figure 4a and 4b] we ascertain that single timescale training results in unstable behaviors, large variance, and gradient norm, while the two timescale training achieves quick convergence and signif- icantly smaller gradient norm. Crucially, to affirm the robustness of methods, compare them with single timescale adversarial training, self-play (Bansal et al. 2017). and fictitious-play (Heinrich & Silver 2016). Self-play and fictitious-play-ban play-based methods are renowned for training adversarially robust RI. agents (Pinto et al., 2017 Zhang et al.] 2021a Tessler et al.) 2019). We employ PPO to calculate the best response of the finalized robustified victim policy, illustrating the performance of the attacker during the victim attack process in Figure/4c Here, a lower winning rate for the attacker signifies enhanced robustness. This demonstrates that our adversarial training with two timescales leads to victim policies with enhanced robustness compared to popular baseline methods, single timescale adversarial training, self-play, and fictitious-play.
DISCUSSION AND LIMITATIONS
In this paper, reassess the threats posed to RL agents by adversarial policies by introducing gen- eralized attack formulation and develop the first provably efficient defense algorithm, "adversarial training with timescale separation", with convergence to the most robust policy under mild condi- tions. Meanwhile, we leave how to scale our formulation to accommodate multiple independent attackers with self-interested adversarial policies future works.

---

Published as a conference paper at ICLR 2024
9 ACKNOWLEDGEMENT
Liu, Chakraborty, Sun, and Huang are supported by National Science Foundation NSF-IIS-FAI pro- gram, DOD-ONR-Offic of Naval Research, DOD Air Force Office of Scientific Research, DOD- Advanced Research Projects Agency Guaranteeing AI Robustness against Decep- tion (GARD), Adobe, Capital One and JP Morgan faculty fellowships. The authors also thank Kaiqing Zhang and Soheil Feizi for the valuable discussions at the initial stages.
REFERENCES
Alckh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22 (98):1-76, 2021.
Maruan Al-Shedivat, Trapit Bansal, Yuri Burda, Ilya Sutskever, Igor Mordatch, and Pieter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments, arXiv preprint (Tt::::7110004111 2017.
David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech Czarnecki, Julien Perolat, Max Jader- berg, and Thore Graepel. Open-ended learning in symmetrie zero-sum games. In International Conference on Machine Learning, pp. 434 443. PMLR, 2019.
Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. Emergent com- plexity via multi-agent competition. arXiv preprint arXiv:1710.03744, 2017.
Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. Emergent com- plexity via multi-agent competition, 2018.
Jan Blumenkamp and Amanda Prorok. The emergence of adversarial communication in multi-agent reinforcement learning, 2020.
Noam Brown, Adam Lerer, Sam Gross, and Tuomas Sandholm. Deep counterfactual regret mini- mization. In International conference on machine learning, pp. 793-802. PMLR, 2019.
Jinglin Chen and Nan Jiang. Information-theorede considerations in batch reinforcement learning. In International Conference on Machine Learning, pp. 1042-1051. PMLR, 2019.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-1320. PMLR, 2019.
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33: 2020.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Anmual ACM SIGACT Symposium on Theory of Computing, pp. 1466-1478, 2021.
Tanner Fiez and Lillian Ratlfff. Local convergence analysis of gradient descent ascent with finite timescale separation. In Proceedings of the International Conference Learning Representation, 2021.
Mare Fischer, Matthew Mirman, Steven Stalder, and Martin Vechev. Online robustness training for deep reinforcement learning. arXiv preprint arXiv:1911.00830 2019.
Tim Franzmeyer, João F Henriques, Jakob N Foerster, Philip HS Torr, Adel Bibi, and Chris- tian Schroeder de Witt. Illusionary attacks on sequential decision makers and countermeasures. arXiv preprint 207. 2022.
Drew Fudenberg and David Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19(5-7): (0557)):165-10000 1089, 1995.
10

---

Published as a conference paper at ICLR 2024
Matthias Gerstgrasser and David C Parkes. Oracles & followers: Stackelberg equilibria in deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp- 11213-11230 PMLR, 2023.
Adam Gleave, Michael Demnis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adver- sarial policies: Attacking deep reinforcement learning. arXiv preprini arXiv:1905. 10615, 2019.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572. 2014.
lan J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.). ) 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceed- ings, 2015. URL http:: arxiv. org abs 1412. 6572
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv: 12715, 2018.
Sven Gowal, Krishnamurthy Dj Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic. Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 4842-4851, 2019.
Wenbo Guo, Xian Wu, Sui Huang, and Xinyu Xing. Adversarial policy learning in two-player competitive games. International Conference on Machine Learning, pp. 3910-3919, PMLR,
2021.
Jamie Hayes. Extensions and limitations of randomized smoothing for robustness guarantees. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Work- shops. pp. 786-787, 2020.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. arXiv preprint drXiv:1603.0112), 2016.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to local nash equilibrium. Advances in neural information processing systems, 30, 2017.
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies, 2017.
Chi Jin, Pranceth Netrapalli, and Michael Jordan. What local optimality in monconvex-moncomcaan minimax optimization? In International conference machine learning, pp. 4880-4889. PMLL. 2020.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In In Proc. 19th International Conference on Machine Learning. Citeseer, 2002.
Harold W Kuhn. simplified two-person poker. Contributions to the Theory of Games, 1:97-103, 1950.
Aounon Kumar, Alexander Levine, and Soheil Feizi. Policy smoothing for provably robust rein- forcement learning. arXiv preprint arXiv:2106. 1420, 2021.
Mare Lanetot, Vinieius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent rein- forcement learning. Advances neural information processing systems, 30, 2017.
Mare Lanctot, Edward Lockhart, Jean- Cann-Bapisste Lespiau, Vinicius Zambaldi, Satyaki Upadhyay, Julien Pérolat, Sriram Srinivasan, Finbarr Timbers, Karl Tuyls, Shayegan Omidshafiei, et al. Openspiel: A framework for reinforcement learning in games. arXiv preprint arXiv:1908. 1908,09453, 2019.
11

---

Published as a conference paper at ICLR 2024
Yongyuan Liang. Yanchao Sun, Ruijie Zheng, and Furong Huang. Efficient adversarial training without attacking: Worst-case-aware robust reinforcement learning. In Alice H. Oh, Alekh Agar- wal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing net / forum?
Systems, 2022. URL
Jieyu Lin, Kristina Dzeparoska, Sai Qian Zhang, Alberto Leon-Garcia, and Nicolas Papernot. On the robustness of cooperative ageti-agent reinforcement learning. In 2020 IEEE Security and Privacy Workshops (SPW), pp. 62-68. IEEE, 2020.
Yen-Chen Lin, Zhang- Wei Hong, Suan-Hong Liao, Meng-Li Shih, Ming- Yu Liu, and Min Sun. Tactics of adversarial attack on deep reinforcement learning agents, 2019.
Michael L Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Xiangyu Liu, Hangtian Jia, Ying Wen, Yujing Hu, Yingfeng Chen, Changjie Fan, Zhipeng Hu, and Yaodong Yang. Towards unifying behavioral and response diversity for open-ended learning in zero-sum games. Advances in Neural Information Processing Systems, 34:941-952, 2021.
Edward Lockhart, Mare Lanctot, Julien Pérolat, Saa-tttt Lespiau, Dustin Morrill, Finbarr Tim- bers, and Karl Tuyls. Computing approximate equilibria in sequential adversarial games by ex- ploitability descent. arXiv preprint arXiv: /903. 05611, 14, 2019.
Björ Lütjens, Michael Everett, and Jonathan How. Certified adversarial robustness for deep reinforcement learning. In Conference Robot Learning, pp. 1328-1337, PMLR, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv: I 770606083.. 2017.
Stephen McAleer, John Lanier, Roy Fox, and Pierre Baldi. Pipeline psro: scalable approach for finding approximate nash equilibria in large games. arXiv preprint arXiv:2006.0885 2020.
Stephen McAleer, John B Lanier, Kevin A Wang, Pierre Baldi, and Roy Fox. Xdo: A double oracle algorithm for extensive-form games. Advances in Neural Information Processing Systems, 34: 23128-23132 2021.
Rupert Mitchell, Jan Blumenkamp, and Amanda Prorok. Gaussian process based message filtering for robust multi-agent cooperation in the presence of adversarial communication, 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski. et al. Human-level control through deep reinforcement learning, nature, 5 518(7540):529-553 533, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928-1937. PMLR, 2016.
Paul Muller, Shayegan Omidshafiei, Mark Rowland, Karl Tuyls, Julien Perolat, Siqi Liu, Daniel Hennes, Luke Marris, Mare Lanctot, Edward Hughes, et al. A generalized training approach for multiagent learning. arXiv preprint 19t9./1999.22888 2019.
Rémi Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pp. 560-567. Citeseer, 2003.
Tuomas Oikarinen, Tsui-Wal Weng, and Luca Daniel. Robust deep reinforcement learning through adversarial loss, 2020.
Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement learning with adversarial attacks, 2017.
Nicolas Perez-Nieves, Yaodong Yang. Oliver Slumbers, David H Mguni, Ying Wen, and Jun Wang. Modelling behavioural diversity for learning in open-ended games. International Conference Machine Learning, pp. 8514-8522 8524. PMLR, 2021.
12

---

Published as a conference paper at ICLR 2024
Julien Perolat, Remi Munos, Jean- lean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, et al. From poincaré re- currence to convergence in imperfect information games: Finding equilibrium via regularization. In International Conference on Machine Learning, pp. 8525-8535, PMLR, 2021.
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In International Conference on Machine Learning, pp. 2817-2826. PMLR, 2017.
You Qiaoben, Chengyang Ying, Xinning Zhou, Hang Su, Jun Zhu, and Bo Zhang. Understanding adversarial attacks on observations in deep reinforcement learning, 2021.
Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. arXiv preprint
2018a.
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. Advances Neural Information Processing Systems, 31, 2018b.
Alessio Russo and Alexandre Proutiere. Balancing detectability and performance of attacks on the control channel of markov decision processes. arXiv preprint arXiv:2109.07171, 2021.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on muchine learning, pp. 1889-1897. PMLR, 2015.
Ali Shafahi, Mahyar Najbbi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry S Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! Ad- vances Neural Information Processing Systems, 32, 2019.
David Silver, Julian Schrittwisser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthe Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676)3354 -39, 2017.
Samuel Sokota, Ryan D'Orazio, J Zico Kolter, Nicolas Loizou, Marc Lanetot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal re- sponse equilibria, and two-player zero-sum games. arXiv preprint arXiv:2206.0580 2022.
Sriram Srinivasan, Mare Lanetot, Vinicius Zambaldi, Julien Pérolat, Karl Tuyls, Rémi Munos, and Michael Bowling. Actor-critic policy optimization in partially observable multiagent environ- ments. Advances in neural information processing systems, 31, 2018.
Jianwen Sun, Tianwei Zhang, Xiaofei Xie, Lei Ma, Yan Zheng, Kangjic Chen, and Yang Liu. Stealthy and efficient adversarial attacks against deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5883-5891, 2020.
Yanchao Sun, Ruijie Zheng, Yongyuan Liang, and Furong Huang. Who the strongest enemy? towards optimal and efficient evasion attacks in deep rl. arXiv preprint arXiv:2106.05mm 2021.
Yanchao Sun, Ruijic Zheng, Parisa Hassanzadch, Yongyuan Liang, Soheil Feizi, Sumitra Ganesh, and Furong Huang. Certifiably robust policy learning against adversarial communication in multi- agent systems. arXiv preprint arXiv:2206. 10158, 2022.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Good- fellow, and Rob Fergus, Intriguing properties of neural networks. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings. 2014. URL http:
//axxiv.org/bblt
6199
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and appli- cations in continuous control. In International Conference on Machine Learning, pp. 6215-6224. PMLR, 2019.
13

---

Published as a conference paper at ICLR 2024
James Tu, Tsunhsuan Wang. Jingkang Wang, Sivabalan Manivasagam, Mengye Ren, and Raquel Urtasun. Adversarial attacks on multi-agent communication, In Proceedings of the IEEE/CVF International Conference Computer Vision (ICCV), pp. 7768-7777, October 2021.
Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pp. 5286-5295. PMLR, 2018.
Fan Wu, Linyi Li, Zijian Huang, Yevgeniy Vorobeychik, Ding Zhao, and Bo Li. Crop: Certi- fying robust policies for reinforcement learning through functional smoothing. arXiv preprint 10i:22206.09222, 2021a.
Xian Wu, Wenbo Guo, Hua Wei, and Xinyu Xing. Adversarial policy training against deep rein- forcement learning. In 30th {USENIX) Security Symposium ( ({USENIX) Security 21), 2021b.
Wanqi Xue, Wei Qiu, Bo An, Zinovi Rabinovich, Svetlana Obraztsova, and Chai Kiat Yeo. Mis- spoke or mis-lead: Achieving robustness in multi-agent communicative reinforcement learning. In Proceedings of the 2 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '22, pp. [418-1426 Richland, SC, 2022. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 978 450392136.
Sihan Zeng, Thinh Doan, and Justin Romberg. Regularized gradient descent ascent for two-player zero-sum markov games. Advances in Neural Information Processing Systems, 35:34546-34555
2022.
Huan Zhang, Tsui-Wei Weng, Pin- Yu Chen, Cho-Jui Hsich, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 4944 4953, Red Hook, NY, USA, 2018a. Curran Associates Inc.
Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, and Cho-Jui Hsich. Towards stable and efficient training of verifiably robust neural networks. In International Conference on Learning Representations, 2020a. URL Utt/tttss:://pperee///
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane S Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations on observations. 2020b.
Huan Zhang, Hongge Chen, Duane S Boning, and Cho-Jui Hsieh. Robust reinforcement learning
on state observations with learned optimal adversary. In International Conference on Learning Representations, 202 la. URL http:/tttt///eeeeeee wttperewwwwwweeeeeeeeeeeeeeeeeee net Scooormeaaidss
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. International Conference on Machine Learming, pp. 5872-5881. PMLR, 2018b.
Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in stochastic games: stationary points, con- vergence, and sample complexity, arXiv preprint 2rX0::2006.00198, 2021b.
14

---

Published as a conference paper at ICLR 2024
Appendix for "Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RL
Table of Contents
Additional related work
15
B Relationship between NE and robustness
16
Motivation and examples of timescale separation
17
D Full proof
18
D.1 Proof of Proposition 3.1 and 3.2
18
D.2 Proof of Proposition 3.3
................................
20
D.3 Proof of Theorem|5.3
20
E
Experimental details
24
E.1
Introduction to the environment
................................
24
B.2
Feature importance Robosumo environments
................................
24
E.3
Implementation details,
25
Additional experimental results
25
A ADDITIONAL RELATED WORK
Two-player zero-sum games. The interaction between the attacker and the victim can be modeled
two-player zero-sum game. There is a large body of work using RL solve Nash equilibrium (NE). For example, Sokota et al. (2022); Perolaat et al. (2021): McAleer et al. (2021); Brown et al.
(0099 Lockhart et al. (2019) considers the normal-form and eatensive-form games. Heinrich &
Silver 2016): Lanctot et al. (2017); McAleer et al. 2020); Perez-Nieves et al. (2021): Liu et al.
2022 deal with more general two-player zero-sum games and propose population-based RI,
gorithms showing empirical success but lacking provable finite-time guarantees. Daskalakis et al.)
2020); Zeng et al. (2022) analyze the theory of independent gradient with different learning rates in Markov game, which is special case of our defense problem against unconstrained attack and serves as the inspiration for us to develop provable adversarial training algorithms.
Adversarial attacks on RL policies. As deep neural networks shown to be vulnerable to ad- versarial attacks (Szegedy et al.) 2014 Goodfellow et al. 2015), the adversarial robustness of deep RL policies has also attracted increasing attention. One of the earliest works by Huang et al.) (2017) reveals the vulnerability of neural policies by adapting various adversarial attacks from supervised learning to RL policies. [in et al. (2019) consider an efficient attack that only perturbs the agent at subset of time steps. There has been subsequent research in developing stronger pixel-based attacks
(iaoben al. 2021 Pattanaik al., [017 Oikarinen al. 2020). Zhang al, (2020b) built the theoretical framework SA-MDP for adversarial state perturbation and proposed the corresponding regularizer for more robust reinforcement learning policies. Subsequent work by [Sun al. (2021)
improves ZZhang et al. (2020b) with the framework of PA-MDP for better efficiency. The major- ity of related work on adversarial RI. focuses on perturbing state observations (Huang et al., 2017] Oikarinen et al. 2020 Sun et al. 2021). and assumes that the perturbation is small in ép distance. In contrast, our paper considers the attack generated by other agents in a multi-agent system and does not restrict the perturbation distance in every single step, allowing for more flexible and practical attack models.
al. (2019) investigate adversarial poli- cies a two-player zero-sum game, where a victim can be exploited and significantly misled by the opponent's 's changed behavior. Guuo al. (021 remove the zero-sum assumption in Gleave et al.
Gleave et Adversarial attacks multi-agent RL (leae)
15

---

Published as a conference paper at ICLR 2024
2019) and construct new formulation for the adversarial policy. Lin al. (2020) study adversarial attacks in cooperative MARL systems and reveal that attacking one the agents in the team can greatly reduce the total reward. However, these adversarial policies are unconstrained and could cause abnormal behaviors that are easily detectable, while our attack model can be made stealthy by restricting the state distribution shifts. We also propose provably robust defense algorithms to learn a policy that is unexploitable.
Attacks and defenses on communication in MARL. There is also line of work studying attacks and defenses on communications in MARL (Blumenkamp & Prorok 2020 Tu et al. 2021:: Mitchell al. 2020 Xue al. 2022), where the communication among cooperative agents could be per- turbed to influence the decisions of victims, However, we consider ad adversarial behaviors or policies of other agents, which affect the victim by the actions taken by other agents.
Provably robust defenses. To provide guaranteed robustness for deep neural networks, many ap- proaches have been developed certify the performance of neural networks, including semidefi- nite wrogramming-basee defenses (Raghunathan et al., [01 b). convex relaxation of neural net- works (Gowal et al., 2019: Zhang et al., [018a| Wong & Kolter 2018 Zhang et al. [2020a] Gowal et al. 2018), randomized smoothing of a classifier (Cohen et al.) 2019 Hayes] 2020), etc. In an effort to certify RL agents' robustness, some approaches (Lütjens et al. 2020; Zhang et al. 2020b Oikarinen al. 2020 Fischer et al., (019) apply network certification tools bound the Q net- works. Kumar et (2021) and Wu et al. (2021a) apply randomized smoothing (Cohen et al. 2019) to RL to achieve provable robustness. These defenses mainly focus the adversarial perturbations directly applied to the agent's 's inputs. Sun et al. (2022) propose a certifiable defense against adver- sarial communication in MARL systems. To the best of knowledge, our paper the first to provide provable convergence guarantees for adversarial training against adversarial attacks on the behaviors of other agents in the environment.
Improving policy robustness by adversarial training. Prior work shows that the competition between the victim agent and the adversary can be regarded as a two-player zero-sum game while training agents with learned adversarial attacks can improve the robustness of the victim. Such an adversarial training paradigm has been shown effective under state perturbations (Zhang et al., 202 Sun et al., 202 Liang et al. 2022) and action perturbations (Pinto et al. [017 Tessler al. 2019) on a single victim. In the context of perturbing the actions of the victim, Tessler et al. (2019) presents two-plas two-player policy iteration algorithm that is proved to converge to the Nash Equilibrium. In contrast, we consider the adversarial behaviors of other agents, and we provide both theoretical guarantees and empirical evidence for the effectiveness of our adversarial training.
B RELATIONSHIP BETWEEN NE AND ROBUSTNESS
To understand the relationship between NE and robustness, we formally define the NE as follows.
Definition B.1 (Nash equilibrium). Fix no and En 2 O. We say a pair of policy (m Ta) the Nash equilibrium for the zero-sun game between the victim and the attacker if holds that for any nt, and T
Vo(Tū, (1 - (1-
) + (TTTT) 2 Vo (1 6x ) + TT)
(B.1)
Vo (1-
-1 Ex a + T)TT))= S Vo (1 ex Ma + Ta).
(B.2)
Now we have the following proposition showing the robustness of the NE.
Proposition B.2. Fix Ro and 6 E [0, 1). If (xt, n²) is the Nash equilibrium for the zero-sum game between the victim and the attacker, then nt is the minimizer for the function Expl(TT)).
Proof. According to Definition B.I it holds that
min (T (1 cx aa c, Vo (1 ()) + (x7+)) max Vo(Te, (1 Ta + (77))) m/a
(B.3)
16

---

Published as a conference paper at ICLR 2024
Combining Equation equation B.3 with the fact that for any function f it holds that ming maxy fIz y) 2 max, min, f(z y). we conclude that
Vo (1 ex a + Tx)T)) = max max Vo - E-eea)aa + enT
"t %
min V (p (1 - cx) + cr
Now given an NE pair (TT) ma), consider the exploitability of n.. Expl(Tş)
min (T (1 En Ja Tx)
Na
(T 6, ) + 6
min (T (1 ex Ta Ta) min %
min Expl( x
Therefore, the solution concept NE guarantees the most robust policy for the victim. Indeed, it is stronger than the goal of the most robust policy since by following exactly the same procedure, one verify NE also guarantees the most robust policy for the attacker. However, as remarked previously, we only care about the robustness of the victim.
C MOTIVATION AND EXAMPLES OF TIMESCALE SEPARATION
To motivate the necessity of timescale separation in adversarial training for robust RL policy, revisit some known issues of naive single-timescale methods including Gradient Descent Ascent (GDA) and iterative best response (IBR) with both simultaneous and alternating update using simple normal-form game Kock-Paper-Scissoor which corresponds to our defense problem with single state and Eş = 1.
Example C.1. The zero-sum game Rock-Paper-Scissee includes two players with the same action
space A = [Rock, Paper, Scissor). The payoff matrix P is given as P -1
1 for
1
the row player. The row player has the mixed strategy x X A(A), where I; represents the probability of choosing ith action. The column player holds similar mixed strategy V. The cor- responding payoff given by V V(x,y) y) Py. Our objective is given by max minyey Py. Note here c, 1.
Formally, compare the following methods; the first 4 methods have only single timescale while the last GAMin method highlights timescale separation, where one player takes a gradient step, and then another one takes the best response.
Simultaneous gradient descent ascent (SGDA): 3/+1 = Py(u - -1pP xx). 3441 = Px Pyy)).
A Alternate gradient descent ascent (AGDA): Ve+1 Py(u T/PTT,)) a++1 Px +
1) Pytt+))
Simultaneous iterative best response (SIBR): 3/+1 arg min z Py, Z(+1
arg min x TP
Alternate iterative best response (AIBR): ye+1 arg I Py. E(41
arg min x Py4+1-
(With timescale separation) Gradient ascent with min oracle (GAMin): V1+1 arg min x. Py, F++1 = Px + 1/Pyt+1).
We show the exploitability of the x player during the learning process in Figure 5 It is clear that the first four single-timese timescale training methods (SGDA, AGDA, SIBR, AIBR) fail to achieve low exploitability, while only GAMin achieves the near-optimal exploitability 0.
17

---

Published as a conference paper at ICLR 2024
1.0
Exploltability
0.6
AGDA
AIBR
GAMin
0.0
2000
4000
6000
8000
10000
Figure 5: Exploitability test on Rock-Paper-See Scissor. Note that the green line is overlapped with the red.
D
FULL PROOF
D.1 PROOF OF PROPOSITION 3.1 AND 3.2
Proof. For simplicity, shall prove Proposition 3.2 first, and then prove Proposition 3.1
Let us first review the following facts for any joint policy क (Te; na): n²' (Tu; ma) such that Dima(TTT (=())=(a) S and the transition matrix Px. where Px 8) >a π P(8"ls, a). In the following proof, we use Pa (1, to denote Pa (8))
d 7) PP))
Px 11 = and || - P 111 - 1-7
|Px - 11 5 2cx
According to Definition 2.1 one can verify that dø satisfies that:
dr (1 - 7)p + PP
which gives the solution dm = - (I- -
For Px:
|P max Σ P (i.j)
-max ΣΣ Σ T(als,)
Σ Talss))) Σ P(ssss;, a)
max
For (()
|[(-~PP)) Σ
(y $ Σ
11(
* $ Σ
1-7
k=1
For Pr P
18

---

Published as a conference paper at ICLR 2024
To begin with, since ny remains unchanged in our proof, let abuse the notation little bit and define the marginalized transition P(s' 8, Gaa = Ea, Ty Ty(ap P(s (ss||s, av, aa). We have
P - PTr 111
max Σ Pa (i.j) - -x
Σ
Ta (Aals)) aaa 181) Σ ( av aa) Σ
-mxx
J
aa
av
max
(Ta (0a1s;) (a (s))) an]l=
Now any index j. define m (P(s)lsj, a N=n! M = (m).... (mi)) and n (Talaalss) Tea (a(aal)))) Then the following holds
Σ (To (0als;) v'a (a, (ss))(s)({s; a.)l
Σ mm nl || < || [M][||/l] = 2e M
According to the definition of M, it is easy to check
M |
max Σ P(s =1
Therefore, conclude that for any fixed index have
Σ Σ (ma((al)))) T' (aala)))))))) ((s(l) an) S 2em:
aa
which proves Pr
Pr 111 S 2c
Now are ready to prove Proposition
3.2
|| d5 ||1 ||(1 -1--)) (1----))--0 -Ppx) -1pll
$ (1 - -pp (
- < (1 7)1((1 - -111
26 1-
Now we can use Proposition following holds
3.2 to prove Proposition 3.1
To begin with, it is easy to verify that the
Vi(T)) = Σ dh (8) Σ x (als))(ss,)
Now let us define the marginalized reward n (s) = E. (a) s)r(s, a). and further define the vector notation T (r (s*) )) Then for the difference of the value function, it holds that
(V) - Vo(TT)) = (d rx) (d .mm)
1
7 (d (x) (d + (d rxx) - (d rx))l
1
5
(Kdd (d Tm)) + [d rw/) - (d) r
1 ?
1
<
(1dd/11ll1r
r 1bo + 11 dn |111)>>1bb>)
1
1
2eaT
(2ea +
7
1-7
26
<
(1 7)2²
19

---

Published as a conference paper at ICLR 2024
D.2 PROOF OF PROPOSITION 3.3
Proof. For any fixed E S and au E Au. the channel that produces the distribution of next state 8' based on the input distribution of da is exactly P(-1 8, au. Therefore, applying the data processing inequality for f-divergence, we prove our proposition.
D.3 PROOF OF THEOREM
In the following discussions, we will use Je, (v, a)) and Jr. (Te, Ta) interchangeably according to Definition 5.1 Once we have a bounded mismatch coefficient in Definition 5.2 we are ready to analyze the properties of the function Je. Je.(v, (v, a) in the following lemma.
Lemma D.1. For any v, v' E A(A,)( and a; a' E ((Aa)))), the function Je, satisfies
Lipschitzness
Ve [V,ae, ViA.n (1 7)2
| (u, <vV/AN
(1 7)2
Smoothness
- Vude, (V' S A. (1 7)3
| 11 1/1 + -lAallla-d/1]
-
2ea / AAa
VaJe I [V (v',
(VIAolll- -/1 V//blll- - a'l).
7)3
Gradient domination
C max V JaJe, (u,a), a).
Je, (), min Je, (v, v 1- à a'
(D.1)
max -e (v, - 1 - max V JJ (v, a), v).
(D.2)
Proof. With the definition of the function Je,, we have Je. (v, Vir (1 en ) + En Ta).
For Lipschitzness, it is easy to compute of gradient of Jc, with respect to v and a using chain rules. Let's denote u/aiz = (1-6z ) To Then the following holds using chain rules and standard policy gradient expression Zhang et al. 2021bb)
OJc, (v,a)
@v VVp(Tu,
To mizz
dp Funtiii
(s)
do F
(s) Ammir IQ T mix (s, aa)) S
Ovsaav
Ovsa
1
(1 7
ÖJe, (v, aasaas
OV (V minr
mis Stunaa
(s) 1u (s, aa))
das
1 -
(1 7)2
V (v, a))l S cvV/Aal
Therefore, we have Vide, (u, S (1-7),
* For Smoothness, it holds that
VeJer V VeJe a1)) -V, ViTu, (1 cx ) (xTTTa n, V (1-ex) ) en
2/ < (1 - 7)3 (VAllle 1/1l + A - d'l))
where the last step comes from Lemma 19 in (Zhang al. 2021b). Similarly, using chain rules, it holds that
V VaJe, (u,,,,(,,,) at) - VaJe, (v',a')))
= En V Vigiie V VTTr, T miz)]
) (xmio=(1-e)) 18 ten rrgii V (TT n miz) mmii= B. text
< 26n v AAa
(v
<VAb/ll=-/ll +
(1
20

---

Published as a conference paper at ICLR 2024
The most challenging step is establishing the gradient domination properties. We will show that objective Je, (Ty, Na) is indeed value function of some other Markov games 9 with modified transition and reward compared with the original g, which is defined as for any given 8, ays ax.S s',
Ti av, 0a) = (s, (1- Cx)
Σ
r'vss, au dadTaaadss (s) + (s,
%
(s Ovs = =1 (s) 0a) (1 Σ
(x)
P(s 8, Ov, d' d' (a 8) + ca P(s' 8, 0, Ga).
For this modified Markov game, we denote the corresponding value function as V Ta).
and the stationary state visitation as dgu."o Then is easy to verify that for any Tu E Il To II
Jep (Tv: Ta) = VT Ta): (- tr dr dou.ta
(D.3)
(D.4)
Similarly, define the mismatch coefficient for & as follows:
Tannte p
drunta
C3 = max {
max min 5, Ell,l (lggg()))
max Tu Ell xu (m))
min
}.
where II; (m₂) == arg min..en.... en. (T(Te, Ta). and IT, (ma) == arg m V Ta) Next, we use the gradient domination property of the value function of Lemma 3 Zhang et al. 2021b). holds that for any n'a and TT.
dp
Vp(T'o na) - Vo(To, Ta) S
max nu (T Ta), -TT)
dp
dp T
Vp(Mu,
VV(TTo maa
max V no Vo na), aa))
de
To
To prove Equation equation
D.l
we denote म E I1 (Tv) to be the policy minimizing the
Teumn
quantity
Then, we have
Je. (v, min Je. (v, (T Ta) a
min V. (T( %
Vo(Ti, Ta)) - Vo(TTo, Tta)
max V Vo (T), Ra - -Ta)
dp
nu
dp
max V Na Vo(Te, Ta), To Ta)
C max no
V V. (T na); Fa ma)-
1
Note due to Equation equation V... Vo(TTu Vn.,, Jc, (Tu, Na)
D.3 and equation
D.4 we have Cg -C and
VaJe, (u, a)., proving Equation equation D.1
21

---

Published as a conference paper at ICLR 2024
To prove Equation equation D.2 we denote Tे (Taa to be the policy minimizing the
quantity
Therefore, we have that
max Je, (v/ (v, max Vo TT) (Tn Ta)
V TT)
Vo(TTe, Taa)
max Ne V (TT, Ta), -Tp)
Up
To
dp
max V Fo 1/ (T (Ta) th nz)
C3 max V nu Vp(Tes Ta); By TT) Rv
Note due to Equation equation
D.3 and equation
D.4 we have Cg - and
Tu (T(TTT Ta)) = V Je, (Tu, To
V vder (v, a), proving Equation equation D.2
we need the following additional lemmas. Firstly, we define o(-) min, Je, (-, 0., and the Moreau envelope for any > dx(v) == max, ((v') 2 || v 1
Before proving Theorem 5.3
Lemma D.2 (Theorem 31 (Jinet al. 2020)). Suppose the function Je, is l-smooth and L- L-Lipschitz. Then the output of Algorithm with step size 1f VT+I satisfies
[o)22((0)) <2 max, Φ(v) 6(1)) + +IL?
VT 1
Lemma D.3 (Lemma 12 (Daskalakis et al. 20201). Suppose Jen is 1-smooth and L-Lipschitz. If there is some uy such that for any v, a
max Je, Je" a) - (e, a) s u, max (ox
then it holds that
L
max :6(2)((() - (VV) S (u, +
27 (1)))(1
Lemma D.4 (Theorem 2a Daskalakis et al. 2020 there is some Uv Un such that for any v,
Suppose Je, is I-smooth and L-Lipschitz. If
max Je, (v",a) Je, (v, s u max
Je (v, a) min Jep (v,a*) S ua max VaJe. (v,
a²
n Then it holds that for ni. = Ba = ( and ni = m = (min|
/LL 1I=
we have that
T
L max Ó(v*)(((+)) - -6(²)= < uy +
8.
T
21
(Dn, + Dn,,
for T 2 Ω
iterations, where DII, and Dn. is the radius of the set 11,, and 11
8mm
Now are ready to prove Theorem 5.3
22

---

Published as a conference paper at ICLR 2024
Proof. We start from proving the convergence of Algorithm 1 By substituting the parameters into
Lemma D.2 we notice that the parameters satisfy that L < and (vV) Therefore, we get
+
2(1A.I+AA.)
"y
C
1-7
/ 2 max, ((v) 6(v + +I1?
2
4(1Aa |Aa 1)3
VT +1
(1 (1-7) (1-7)VT+1 -)- /T +
Now we use Lemma D.3 and conclude that
1 T max (ax)d)(((v")>> vT+1 poly( 1- (S], |All
1
Therefore, for Algorithm ! to achieve accuracy 8, combined with the fact that Φ(-) Expl(-). one needs T = poly 1- (S), [Aal, [Abl, (ig") total number of iterations, concluding the proof for Algorithm
The proof for Algorithm follows similar steps. We notice the instantiation of the parameters I. [A.]+|A11
Co 2 [( Myy Uha S I-q- DII, Dn, vlS). Bt substituting the parameters into Lemma D.4 and combing with the fact that (()) = - Expl(.) :) we set total number
(I-7)"
of iterations T poly C 18], |Aal [Av), r- to achieve accuracy 6, concluding the proof
for Algorithm 2
L
23

---

Published as a conference paper at ICLR 2024
E EXPERIMENTAL DETAILS
E.1 INTRODUCTION TO THE ENVIRONMENT
Kuhn Poker is popular research game, which extensive-form and zero-sum with discrete obser- vation and action space. There exists efficient min oracle with game tree search. For Robosumo competition, both agents are multi-leg robots and observe the position, velocity, and contact forces of joints in their body, and the position of their opponent's joints, which is much more challenging due to the high dimensional observation and action space.
E.2 FEATURE IMPORTANCE IN ROBOSUMO ENVIRONMENTS
We show the important features for the Robosumo environment in Table
Original
Local
Global
38
32
31
32
43
33
38
29
43
37
43
41
31
41
29
35
34
35
42
42
39
41
35
42
40
37
26
28
Table 1: Feature Importance (Subset) Robosumo Spider vs Spider. "Original": Index of the most important features of the victim's 's observation while playing against normal opponents. "Local": Index of the most important features of the victim's 's observation while playing against the attacker trained via constrained attack method. "Global": Index of the most important features of the victim's 's observation while playing against the attacker trained via the unconstrained attack method as done in (Gleave al. 2019
Original
Local
Global
25
25
23
145
26
1 146
26
145
145
146
24
25
24
22
22
142
146
21
144
23
24
22
143
144
143
27
142
23
142
143
Table 2: Feature Importance (Subset) in Robosumo Ant vs Ant. "Original": Index of the most important features of the victim's 's observation while playing against normal opponents. "Local": Index of the most important features of the victim's 's observation while playing against the attacker trained via our constrained attack method. "Global": Index of the most important features of the victim's 's observation while playing against the attacker trained via the unconstrained attack method as done in (Gleave et al. 2019
24

---

Published as a conference paper at ICLR 2024
Original
Local
Global
193
27
33
197
35
25
25
25
35
197
27
27
193
35
29
189
191
199
36
199
34
34
190
191
36
36
26
Table 3: Feature Importance (Subset) in Robosumo Bug vs Bug. "Original": Index of the most important features of the victim's s observation while playing against normal opponents. "Local": Index of the most important features of the victim's observation while playing against the attacker trained via our constrained attack method. "Global": Index of the most important features of the victim's 's observation while playing against the attacker trained via the unconstrained attack method as done in (Gleave et al. 2019
E.3 IMPLEMENTATION DETAILS.
Kuhn Poker. For implementing our adversarial training approach, we adopt both advanced A2C and RPG policy gradient methods. The policy is parameterized by an MLP with a hidden layer size of 128. We use batch size of 16 and SGD as the optimizer.
Robosumo competition. We use PPO as base policy optimization algorithm. We use clip range of 0.2 and 0.95 for GAE. The number hidden units for parameterization of the policy is 64. For all adversarial training algorithms with both a single timescale and two timescales and the baseline algorithm self-play and fictitious-play. we train by 3e7 timesteps with a batch size of 64. For attack, we train for 2c7 timesteps with batch size of 2048. We use Adam the optimizer.
E.4 ADDITIONAL EXPERIMENTAL RESULTS
Trade-off between stealthiness and winning rate. We have mentioned that there is trade-off between stealthiness and the winning rate. To quantitatively show the trade-off, we show the com- parison of our constrained attack and unconstrained one in Figure 6 where éx in the figures.
Rabosumo Ant vs Ant
Rabosumo Bug vs Bug
Robasumo Spidia vs Spider
Whing Rate
016
0.4
0.2
2.0
1.5
0.5
1.0
Timestopp
107
Timastops
167
1.0
0.8
1.0
Nor-fal Rale
0.9
0.6
0.6
04
0.2
0.6
0.2
0.4
2.5
0.5
3.0
1- 0.5
0.2
1.5
Timestops
Timesteps
Timestops
Figure 6: Winning rate and Non-fail rate of different attack methods.
Additional results on the state-distribution shifts. To quantify the state distr-iistibutton shift in- duced due the unconstrained (global) and constraint (local) attacks, in addition the Wasserstein
25

---

Published as a conference paper at ICLR 2024
1.75
Global
1.90
Local 2
1.25
1.00
HL
0.50
Bug Bug Environment
Spider
(a) KL-DivergeeneeSSalel)
atlack
Giobal
0.8
Local1
Hcllnger(scalet)
0.8
0.2
0.0
Bug Environment
Spider
(b) Hellinger Distance(Scaled)
Figure 7: This figure compares the state-distribution shift w.r.t KL-Divergence(Sealed) and Hellinger Distance(scaled) incurred due to the Global (e, = 1), Local-1 (E, = 0.7), Local- 2(e, 0.3) attacks in 3 Robosumo environments. The plot clearly demonstrates the Stealthiness of constraint (local) attacks in preserving the state-distribution shifts and achieving stealthiness.
distance in Figure 3 we also compute the KL-Divergence and Hellinger distance between the state- distribution of the unattacked policy with the global and local attacks respectively. We observe that state-distribution shift incurred is much lesser in local attacks than global, as also can be seen in highlighting the stealthiness of our attack.
Figure 3
Mismatch of attack budgets between training time and test time. We show the attacker's per- formance when there is mismatch between the actual attack budget and the budget used train the robust victim in the following table. It is clear that even the defense budget is not correctly specified, the victim policy still shows greatly improved robustness, although a bit worse than the case when the defense budget is correctly specified.
Attacker score
Attack budget 0.3
Attack budget 0.7
Attack budget 1.0
Defense budget 0.3
0.38
0.50
0.71
Defense budget 0.7
0.41
0.43
0.53
Defense budget 1.0
0.44
0.45
0.50
No defense
0.59
0.78
0.90
Table 4: Attacker's score with different attack budgets against robust victim policies with different defense budgets and without defenses
26


Reviews:
[{"review_id": "ocRIFfWqJf", "reviewer": "Reviewer_RFDQ", "summary": "The paper studies RL in an adversarial setting. In particular, the focus is on multi- (specifically 2) agent setting in which an agent $\\alpha$ has the goal of harming the other agent $\\nu$. So, the goal of $\\nu$ is to find the most return (based on the discount factor $\\lambda$) while $\\alpha$ aims to the opposite direction for $\\nu$.\n\nThe paper then models a form of \"budget\" for the adversarial agent, but letting them impose a policy that is a probabilistic (linear) combination of the original (non-adversarial) policy and a fully malicious adversarial one. So, a parameter $\\epsilon \\in [0,1]$ is introduced here to control this budget.\n\nSome initial (proposition) results are proved showing that with small $\\epsilon$, the effect of adversary's strategy is limited (which is expected, but proving them formally is not completely trivial).\n\nThe paper then aims at designing a form of adversarial training. They propose a method with \"two separated timescale\" meaning that the optimization is done in iterations between two types of operations. In one type of operation one fixes the adversary's strategy and optimizes the victim policy, and then switches to to the opposite.\n\nThe paper proves converges properties for their defense, and then move to do experiments to show the capability of the defense in different senses (such as convergence and robustness of the final policy).", "questions": "You say \"performance. This contrasts with supervised learning attacks, where small perturbations can result in large performance shifts.\" but this seems to be only applicable to test time attacks, as poisoning has a limited effect if it is limited to eps-fraction of data (e.g, ERM will be effected by eps increase in its probability of error as well).\n\nWhen you say \"However, it has been demonstrated that while re-training against a specific adversarial policy does augment robustness against it, the performance against other policies may be compromised.\" what is the reference?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Studying RL's robustness in the multi-agent setting is a natural in interesting problem. The formulation is clean and the proposed defense is analyzed well, both theoretically and experimentally.", "weaknesses": "Despite numerous references to previous work, there is no clean depicted picture of how this work on multi agent robustness fits in the context of previous work. I am not complaining for lack of references here, I just think the presentation should be more clear.\n\nSome corrections needed (see comments below as well).\n\nsome example of typos:\nDef 5.1 : \"has\" -> 'have\"\n\nparagraph \"(c) Connection to action adversarial RL.\" in page 4, has \"\\tilde{\\pi}\\alpha\" in which alpha needs to be the index.\n\nDefinition 5.2. : please give an intuition of what this is, before giving a full line math formula.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "Na20oZB9m2", "reviewer": "Reviewer_wz1v", "summary": "This paper introduces a new attack formulation in multi-agent reinforcement learning, where an attacker can have partial control over agent  $\\alpha$ to attack against a well-trained victim agent $v$. The paper highlights the limitations of existing attack models and proposes a more generalized attack framework that takes into account the level of attack budget and the attack model’s detectability. The paper offers a provably efficient defense with polynomial convergence to the most robust victim policy through adversarial training with timescale separation. The empirical results on two standard environment,: Kuhn Poker and RoboSumo, showcasing the proposed attack algorithm's effectiveness.", "questions": "See in the weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The proposed attack framework in multi-agent reinforcement learning takes into account the level of control the attacker has over the agent by introducing an \"attack budget\". This attack budget characterizes the partial control of the attacker and regulates the strength of the attacker in degrading the victim's performance. Regulating the attack budget allows us to manage the discrepancy between the state distributions and the transition dynamics before and after the attack, allowing for more stealthy attacks. The paper is well-written and presents the concepts, definitions, and analyses. A provably efficient defense with polynomial convergence have practical implications for the application of the proposed adversarial training.", "weaknesses": "In my understanding, the novelty of the paper is mainly the \"partial control\" and \"attack budget\", compared with the previous work: Gleave et al. (2019); Wu et al. (2021b); Guo et al. (2021). However, the partial control is previously introduced in PR-MDP, Tessler et al. (2019). \n\nThe motivation of the attack budget and partial control is not enough convincing. From the attack side, it is true that the setting of attack budget can improve the stealthiness, but it is hard to say that the proposed attack is optimal subject to the limitation of the discrepancy between the state distributions (or marginalized transition dynamics). From the side of the defense (adversarial training), there is no insight into the choice of the defense budget which is the budget used to train the robust victim. What is the benefit of introducing this defense budget? More discussion would be helpful.\n\nThe result in Figure 1 is confusing. 1. Why the bottom-right subfigure is empty? 2. Is original state distribution means that the distribution without any attack? If it is true, should not the original state distribution be same in the bottom and top subfigures? The original state distributions in top-mid and bottom-mid subfigures are different. Could you explain the reason? 3. Where do the results in Figure 1 come from? The paper only mentions that two attack polices are assessed under the same winning rate. However, according to the Figure 6, the unconstrained policy has higher wining rate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "0JasPY8wD5", "reviewer": "Reviewer_GBTd", "summary": "This paper investigates adversarial attacks in multi-agent environments. Specifically, it considers a two-agent environment where one agent is controlled (hijacked) by an adversary, with the goal of minimizing the other agent's cumulative reward. The paper introduces the idea of a reduced capacity attack, where the adversary can only control the action of the hijacked adversary at each time step with a probability p. The paper derives a bound on policy discrepancy given p and investigates the stealthiness of an attack for a given p, where stealthiness is defined either as variation in the induced state distribution or as variation in the conditional transition dynamics. The paper then investigates adversarial training with timescale separation to achieve provably robust victim policies and derives a convergence bound that is polynomial with respect to the size of the state and action space. The paper then verifies the stealthiness of the proposed attack and the exploitability of robustified victim policies in two benchmark environments.", "questions": "See weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- the paper studies a very valid scenario for adversarial attacks in multi-agent systems\n- the derived bounds on policy similarity, state distribution and conditional transition probabilities are insightful\n- the conducted experiments indicate that their attacks are more stealthy than prior work\n- the conducted experiments indicate that the robustification of victim policies results in significantly improved exploitability of victim agents", "weaknesses": "- Stealthiness is defined as the difference in state distributions. This is a step in the right direction and seems like a good proxy for real-world problems. However, two identical state distributions can come from very different trajectories (e.g. just inverting the order of states within all trajectories does not change the state distribution). This should be considered and discussed in more detail.\n- The empirical results wrt stealthiness are very limited. Only three videos are provided for the qualitative comparison. A larger study and/or quantitative results would much improve the paper.\n- The theoretical results are interesting, but the applicability of the given bounds to larger environments remains unclear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "1un8r4KYs8", "reviewer": "Reviewer_gybG", "summary": "The paper considers a two-player Markov game where an attacker controls one player to minimize the performance of the victim player. Thus, the game is essentially zero-sum. The setting has been considered in some recent work. The paper considers an extension where a player is partially controlled by the attacker and follows the original policy with a certain probability and the malicious policy otherwise. The paper derives some analytic results regarding the effects of attack budget on attack detectability. It then formulates the victim's problem of minimizing the one-side exploitability, proposes two algorithms, and establishes their convergence.", "questions": "Although I agree that directly perturbing the perceived state of an agent is not always feasible in practice, I don't see why controlling another agent against the victim is easier, as claimed in the introduction. They are just different types of attacks. In the air traffic control example, what is the Markov game between the radar system and the commercial drone? \n\nAlthough it makes sense to consider a constrained attack model to obtain better stealthiness, the proposed formulation is a bit confusing. In particular, if the agent is only partially controlled by the attacker, there is a three-player game between the victim, the agent partially controlled by the attacker, and the attacker.  In this case, why should the agent adopt a fixed policy without adapting to the victim's policy? \n\nIn Figure 1, it says that an unconstrained adversarial policy and a constrained policy with the same winning rate are chosen. How is this achieved? Also, is the same victim policy used in both cases? Intuitively, a smaller epsilon should produce a lower state distribution shift and a stealthier attack, but at the same time, the victim's (best possible) performance should improve, given that the attacker becomes weaker.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Previous work on adversarial policies has mainly focused on unconstrained attacks, which can be easily detected. Thus, it makes sense to consider a constrained attacker. The paper shows that the approach leads to stealthier attacks with significantly lower state distribution shifts. \n\nThe paper establishes the convergence of adversarial training with an inner oracle and two-timescale adversarial training for two-player zero-sum Markov games when the attacker is constrained by extending previous results on the unconstrained case, which may find applications in other settings where asymmetric Markov games with constrained followers can be applied", "weaknesses": "It seems that minimizing the so-called one-side exploitability (definition 4.1) is the same as finding the Stackelberg equilibrium, a well-studied concept in game theory and multi-agent RL. Both Algorithm 1 and Algorithm 2 follow the general framework for finding the Stackelberg equilibrium in deep multi-agent RL summarized in Gerstgrasser et al. (2023). The convergence analysis of the two-timescale approach follows Daskalakis et al. (2020) and Zeng et al. (2022). Thus, the technical contribution of the paper seems limited. \n\nThe paper assumes that the original policy \\hat{\\pi}_alpha of the agent partially controlled by the attacker is fixed so that existing algorithmic and analytic frameworks can be applied. However, this is not a reasonable assumption. Since the agent is playing a game with the victim (even without the attacker), it should adapt its (original) policy against the victim's policy rather than using a fixed policy. \n\nIn Section 3, since the victim's policy is assumed to be fixed, the problem reduces to a single agent MDP, and Propositions 3.1-3.3 are simple variants of well-known results in approximate dynamic programming. Also, I don't see the purpose of mentioning concepts such as generative modeling and distribution matching.  \n\nMatthias Gerstgrasser and David C. Parkes. Oracles & Followers: Stackelberg Equilibria in Deep Multi-Agent Reinforcement Learning. 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)