Year: 2021

Abstract:
Evaluating the worst-case performance of a reinforcement learning (RL) agent under the strongest/optimal adversarial perturbations on state observations (within some constraints) is crucial for understanding the robustness of RL agents. However, finding the optimal adversary is challenging, in terms of both whether we can find the optimal attack and how efficiently we can find it. Existing works on adversarial RL either use heuristics-based methods that may not find the strongest adversary, or directly train an RL-based adversary by treating the agent as a part of the environment, which can find the optimal adversary but may become intractable in a large state space. This paper introduces a novel attacking method to find the optimal attacks through collaboration between a designed function named “actor” and an RL-based learner named “director”. The actor crafts state perturbations for a given policy perturbation direction, and the director learns to propose the best policy perturbation directions. Our proposed algorithm, PA-AD, is theoretically optimal and significantly more efficient than prior RL-based works in environments with large state spaces. Empirical results show that our proposed PA-AD universally outperforms state-of-the-art attacking methods in various Atari and MuJoCo environments. By applying PA-AD to adversarial training, we achieve state-of-the-art empirical robustness in multiple tasks under strong adversaries.

heading: 1 INTRODUCTION
text: Deep Reinforcement Learning (DRL) has achieved incredible success in many applications. However, recent works (Huang et al., 2017; Pattanaik et al., 2018) reveal that a well-trained RL agent may be vulnerable to test-time evasion attacks, making it risky to deploy RL models in high-stakes applications. As in most related works, we consider a state adversary which adds imperceptible noise to the observations of an agent such that its cumulative reward is reduced during test time.
In order to understand the vulnerability of an RL agent and to improve its certified robustness, it is important to evaluate the worst-case performance of the agent under any adversarial attacks with certain constraints. In other words, it is crucial to find the strongest/optimal adversary that can minimize the cumulative reward gained by the agent with fixed constraints, as motivated in a recent paper by Zhang et al. (2021). Therefore, we focus on the following question:
Given an arbitrary attack radius (budget) for each step of the deployment, what is the worstcase performance of an agent under the strongest adversary?
Finding the strongest adversary in RL is challenging. Many existing attacks (Huang et al., 2017; Pattanaik et al., 2018) are based on heuristics, crafting adversarial states at every step independently, although steps are interrelated in contrast to image classification tasks. These heuristic methods can often effectively reduce the agent’s reward, but are not guaranteed to achieve the strongest attack under a given budget. This type of attack is “myopic” since it does not plan for the future. Figure 1 shows an intuitive example, where myopic adversaries only prevent the agent from selecting the best action in the current step, but the strongest adversary can strategically “lead” the agent to a trap, which is the worst event for the agent.
Achieving computational efficiency arises as another challenge in practice, even if the strongest adversary can be found in theory. A recent work (Zhang et al., 2020a) points out that learning the optimal state adversary is equivalent to learning an optimal policy in a new Markov Decision Process (MDP). A follow-up work (Zhang et al., 2021) shows that the learned adversary significantly outperforms prior adversaries in MuJoCo games. However, the state space and the action space of the new MDP are both as large as the state space in the original environment, which can be high-dimensional in practice. For example, video games and autonomous driving systems use images as observations. In these tasks, learning the state adversary directly becomes computationally intractable.
To overcome the above two challenges, we propose a novel attack method called Policy Adversarial Actor Director (PA-AD), where we design a “director” and an “actor” that collaboratively finds the optimal state perturbations. In PA-AD, a director learns an MDP named Policy Adversary MDP (PAMDP), and an actor is embedded in the dynamics of PAMDP. At each step, the director proposes a perturbing direction in the policy space, and the actor crafts a perturbation in the state space to lead the victim policy towards the proposed direction. Through a trail-and-error process, the director can find the optimal way to cooperate with the actor and attack the victim policy. Theoretical analysis shows that the optimal policy in PAMDP induces an optimal state adversary. The size of PAMDP is generally smaller than the adversarial MDP defined by Zhang et al. (2021) and thus is easier to be learned efficiently using off-the-shelf RL algorithms. With our proposed director-actor collaborative mechanism, PA-AD outperforms state-of-the-art attacking methods on various types of environments, and improves the robustness of many DRL agents by adversarial training.

heading: Summary of Contributions
text: (1) We establish a theoretical understanding of the optimality of evasion attacks from the perspective of policy perturbations, allowing a more efficient implementation of optimal attacks. (2) We introduce a Policy Adversary MDP (PAMDP) model, whose optimal policy induces the optimal state adversary under any attacking budget . (3) We propose a novel attack method, PA-AD, which efficiently searches for the optimal adversary in the PAMDP. PA-AD is a general method that works on stochastic and deterministic victim policies, vectorized and pixel state spaces, as well as discrete and continuous action spaces. (4) Empirical study shows that PA-AD universally outperforms previous attacking methods in various environments, including Atari games and MuJoCo tasks. PA-AD achieves impressive attacking performance in many environments using very small attack budgets, (5) Combining our strong attack PA-AD with adversarial training, we significantly improve the robustness of RL agents, and achieve the state-of-the-art robustness in many tasks.

heading: 2 PRELIMINARIES AND NOTATIONS
text: The Victim RL Agent In RL, an agent interacts with an environment modeled by a Markov Decision Process (MDP) denoted as a tuple M = 〈S,A, P,R, γ〉, where S is a state space with cardinality |S|, A is an action space with cardinality |A|, P : S × A → ∆(S) is the transition function 1, R : S × A → R is the reward function, and γ ∈ (0, 1) is the discount factor. In this paper, we consider a setting where the state space is much larger than the action space, which arises in a wide variety of environments. For notation simplicity, our theoretical analysis focuses on a finite MDP, but our algorithm applies to continuous state spaces and continuous action spaces, as verified in experiments. The agent takes actions according to its policy, π : S → ∆(A). We suppose the victim uses a fixed policy π with a function approximator (e.g. a neural network) during test time. We denote the space of all policies as Π, which is a Cartesian product of |S| simplices. The value of a policy π ∈ Π for state s ∈ S is defined as V π(s) = Eπ,P [ ∑∞ t=0 γ
tR(st, at)|s0 = s]. Evasion Attacker Evasion attacks are test-time attacks that aim to reduce the expected total reward gained by the agent/victim. As in most literature (Huang et al., 2017; Pattanaik et al., 2018; Zhang et al., 2020a), we assume the attacker knows the victim policy π (white-box attack). However, the attacker does not know the environment dynamics, nor does it have the ability to change the environment directly. The attacker can observe the interactions between the victim agent and the environment, including states, actions and rewards. We focus on a typical state adversary (Huang et al., 2017; Zhang et al., 2020a), which perturbs the state observations returned by the environment before the agent observes them. Note that the underlying states in the environment are not changed.
1∆(X) denotes the the space of probability distributions over X .
Formally, we model a state adversary by a function h which perturbs state s ∈ S into s̃ := h(s), so that the input to the agent’s policy is s̃ instead of s. In practice, the adversarial perturbation is usually under certain constraints. In this paper, we consider the common `p threat model (Goodfellow et al., 2015): s̃ should be in B (s), where B (s) denotes an `p norm ball centered at s with radius ≥ 0, a constant called the budget of the adversary for every step. With the budget constraint, we define the admissible state adversary and the admissible adversary set as below.
Definition 1 (Set of Admissible State AdversariesH ). A state adversary h is said to be admissible if ∀s ∈ S, we have h(s) ∈ B (s). The set of all admissible state adversaries is denoted by H . Then the goal of the attacker is to find an adversary h∗ in H that maximally reduces the cumulative reward of the agent. In this work, we propose a novel method to learn the optimal state adversary through the identification of an optimal policy perturbation defined and motivated in the next section.

heading: 3 UNDERSTANDING OPTIMAL ADVERSARY VIA POLICY PERTURBATIONS
text: In this section, we first motivate our idea of interpreting evasion attacks as perturbations of policies, then discuss how to efficiently find the optimal state adversary via the optimal policy perturbation.
Evasion Attacks Are Perturbations of Policies Although existing literature usually considers state-attacks and actionattacks separately, we point out that evasion attacks, either applied to states or actions, are essentially equivalent to perturbing the agent’s policy π into another policy πh in the policy space Π. For instance, as shown in Figure 2, if the adversary h alters state s into state s̃, the victim selects an action ã based
on π(·|s̃). This is equivalent to directly perturbing π(·|s) to πh(·|s) := π(·|s̃). (See Appendix A for more detailed analysis including action adversaries.)
In this paper, we aim to find the optimal state adversary through the identification of the “optimal policy perturbation”, which has the following merits. (1) πh(·|s) usually lies in a lower dimensional space than h(s) for an arbitrary state s ∈ S. For example, in Atari games, the action space is discrete and small (e.g. |A| = 18), while a state is a high-dimensional image. Then the state perturbation h(s) is an image, while πh(·|s) is a vector of size |A|. (2) It is easier to characterize the optimality of a policy perturbation than a state perturbation. How a state perturbation changes the value of a victim policy depends on both the victim policy network and the environment dynamics. In contrast, how a policy perturbation changes the victim value only depends on the environment. Our Theorem 4 in Section 3 and Theorem 12 in Appendix B both provide insights about how V π changes as π changes continuously. (3) Policy perturbation captures the essence of evasion attacks, and unifies state and action attacks. Although this paper focuses on state-space adversaries, the learned “optimal policy perturbation” can also be used to conduct action-space attacks against the same victim.
Characterizing the Optimal Policy Adversary As depicted in Figure 3, the policy perturbation serves as a bridge connecting the perturbations in the state space and the value space. Our goal is to find the optimal state adversary by identifying the optimal “policy adversary”. We first define an Admissible Adversarial Policy Set (Adv-policy-set) BH (π) ⊂ Π as the set of policies perturbed from π by all admissible state adversaries h ∈ H . In other words, when a state adversary perturbs states within an `p norm ball B (·), the victim policy is perturbed within BH (π). Definition 2 (Admissible Adversarial Policy Set (Adv-policy-set) BH (π)). For an MDP M, a fixed victim policy π, we define the admissible adversarial policy set (Adv-policy-set) w.r.t. π, denoted by BH (π), as the set of policies that are perturbed from π by all admissible adversaries, i.e.,
BH (π) := {πh ∈ Π : ∃h ∈ H s.t ∀s, πh(·|s) = π(·|h(s))}. (1)
Remarks (1) BH (π) is a subset of the policy space Π and it surrounds the victim π, as shown in Figure 3(middle). In the same MDP, BH (π) varies for different victim π or different attack budget . (2) In Appendix B, we characterize the topological properties of BH (π). We show that for a continuous function π (e.g., neural network), BH (π) is connected and compact, and the value functions generated by all policies in the Adv-policy-set BH (π) form a polytope (Figure 3(right)), following the polytope theorem by Dadashi et al. (2019).

heading: An RL problem in a small MDPAn optimization problem
text: Given that the Adv-policy-set BH (π) contains all the possible policies the victim may execute under admissible state perturbations, we can characterize the optimality of a state adversary through the lens of policy perturbations. Recall that the attacker’s goal is to find a state adversary h∗ ∈ H that minimizes the victim’s expected total reward. From the perspective of policy perturbation, the attacker’s goal is to perturb the victim’s policy to another policy πh∗ ∈ BH (π) with the lowest value. Therefore, we can define the optimal state adversary and the optimal policy adversary as below.
Definition 3 (Optimal State Adversary h∗ and Optimal Policy Adversary πh∗ ). For an MDP M, a fixed policy π, and an admissible adversary set H with attacking budget , (1) an optimal state adversary h∗ satisfies h∗ ∈ argminh∈H V
πh(s),∀s ∈ S, which leads to (2) an optimal policy adversary πh∗ satisfies πh∗ ∈ argminπh∈BH (π)V
πh(s),∀s ∈ S. Recall that πh is the perturbed policy caused by adversary h, i.e., πh(·|s) = π(·|h(s)),∀s ∈ S.
Definition 3 implies an equivalent relationship between the optimal state adversary and the optimal policy adversary: an optimal state adversary leads to an optimal policy adversary, and any state adversary that leads to an optimal policy adversary is optimal. Theorem 19 in Appendix D.1 shows that there always exists an optimal policy adversary for a fixed victim π, and learning the optimal policy adversary is an RL problem. (A similar result have been shown by Zhang et al. (2020a) for the optimal state adversary, while we focus on the policy perturbation.)
Due to the equivalence, if one finds an optimal policy adversary πh∗ , then the optimal state adversary can be found by executing targeted attacks with target policy πh∗ . However, directly finding the optimal policy adversary in the Adv-policy-set BH (π) is challenging since BH (π) is generated by all admissible state adversaries in H and is hard to compute. To address this challenge, we first get insights from theoretical characterizations of the Adv-policy-set BH (π). Theorem 4 below shows that the “outermost boundary” of BH (π) always contains an optimal policy adversary. Intuitively, a policy π′ is in the outermost boundary of BH (π) if and only if no policy in BH (π) is farer away from π than π′ in the direction π′ − π. Therefore, if an adversary can perturb a policy along a direction, it should push the policy as far away as possible in this direction under the budget constraints. Then, the adversary is guaranteed to find an optimal policy adversary after trying all the perturbing directions. In contrast, such a guarantee does not exist for state adversaries, justifying the benefits of considering policy adversaries. Our proposed algorithm in Section 4 applies this idea to find the optimal attack: an RL-based director searches for the optimal perturbing direction, and an actor is responsible for pushing the policy to the outermost boundary of BH (π) with a given direction.
Theorem 4. For an MDP M, a fixed policy π, and an admissible adversary set H , define the outermost boundary of the admissible adversarial policy set BH (π) w.r.t π as ∂πBH (π) := {π′ ∈ BH (π) : ∀s ∈ S, θ > 0,@π̂ ∈ BH (π) s.t. π̂(·|s) = π′(·|s) + θ(π′(·|s)− π(·|s))}. (2) Then there exists a policy π̃ ∈ ∂πBH (π), such that π̃ is the optimal policy adversary w.r.t. π.
Theorem 4 is proven in Appendix B.3, and we visualize the outermost boundary in Appendix B.5.

heading: 4 PA-AD: OPTIMAL AND EFFICIENT EVASION ATTACK
text: In this section, we first formally define the optimality of an attack algorithm and discuss some existing attack methods. Then, based on the theoretical insights in Section 3, we introduce our algorithm, Policy Adversarial Actor Director (PA-AD) that has an optimal formulation and is efficient to use.
Although many attack methods for RL agents have been proposed (Huang et al., 2017; Pattanaik et al., 2018; Zhang et al., 2020a), it is not yet well-understood how to characterize the strength and the optimality of an attack method. Therefore, we propose to formulate the optimality of an attack algorithm, which answers the question “whether the attack objective finds the strongest adversary”.
Definition 5 (Optimal Formulation of Attacking Algorithm). An attacking algorithm Algo is said to have an optimal formulation iff for any MDPM, policy π and admissible adversary set H under attacking budget , the set of optimal solutions to its objective, HAlgo , is a subset of the optimal adversaries against π, i.e., HAlgo ⊆ H∗ := {h∗|h∗ ∈ argminh∈H V πh(s),∀s ∈ S}.
Many heuristic-based attacks, although are empirically effective and efficient, do not meet the requirements of optimal formulation. In Appendix D.3, we categorize existing heuristic attack methods into four types, and theoretically prove that there exist scenarios where these heuristic methods may not find the strongest adversary. A recent paper (Zhang et al., 2021) proposes to learn the optimal state adversary using RL methods, which we will refer to as SA-RL in our paper for simplicity. SA-RL can be viewed as an “end-to-end” RL attacker, as it directly learns the optimal state adversary such that the value of the victim policy is minimized. The formulation of SA-RL satisfies Definition 5 and thus is optimal. However, SA-RL learns an MDP whose state space and action space are both the same as the original state space. If the original state space is high-dimensional (e.g. images), learning a good policy in the adversary’s MDP may become computationally intractable, as empirically shown in Section 6.
Can we address the optimal attacking problem in an efficient manner? SA-RL treats the victim and the environment together as a black box and directly learns a state adversary. But if the victim policy is known to the attacker (e.g. in adversarial training), we can exploit the victim model and simplify the attacking problem while maintaining the optimality. Therefore, we propose a novel algorithm, Policy Adversarial Actor Director (PA-AD), that has optimal formulation and is generally more efficient than SA-RL. PA-AD decouples the whole attacking process into two simpler components: policy perturbation and state perturbation, solved by a “director” and an “actor” through collaboration. The director learns the optimal policy perturbing direction with RL methods, while the actor crafts adversarial states at every step such that the victim policy is perturbed towards the given direction. Compared to the black-box SA-RL, PA-AD is a white-box attack, but works for a broader range of environments more efficiently. Note that PA-AD can be used to conduct black-box attack based on the transferability of adversarial attacks (Huang et al., 2017), although it is out of the scope of this paper. Appendix F.2 provides a comprehensive comparison between PA-AD and SA-RL in terms of complexity, optimality, assumptions and applicable scenarios.
Formally, for a given victim policy π, our proposed PA-AD algorithm solves a Policy Adversary MDP (PAMDP) defined in Definition 6. An actor denoted by g is embedded in the dynamics of the PAMDP, and a director searches for an optimal policy ν∗ in the PAMDP.
Definition 6 (Policy Adversary MDP (PAMDP) M̂). Given an MDP M = 〈S,A, P,R, γ〉, a fixed stochastic victim policy π, an attack budget ≥ 0, we define a Policy Adversarial MDP M̂ = 〈S, Â, P̂ , R̂, γ〉, where the action space is Â :={d ∈[0, 1]|A|,∑|A|i=1 di = 0}, and ∀s, s′ ∈ S,∀â ∈ Â,
P̂ (s′|s, â) = ∑
a∈A π(a|g(â, s))P (s′|s, a), R̂(s, â) = − ∑ a∈A π(a|g(â, s))R(s, a),
where g is the actor function defined as
g(â, s) = argmaxs′∈B (s)‖π(s ′)−π(s)‖ subject to
( π(s′)−π(s) )T â = ‖π(s′)−π(s)‖‖â‖. (G)
If the victim policy is deterministic, i.e., πD := argmaxaπ(a|s), (subscript D stands for deterministic), the action space of PAMDP is ÂD :=A, and the actor function gD is
gD(â, s) = argmaxs′∈B (s) ( π(â|s′)−maxa∈A,a6=âπ(a|s′) ) . (GD)
Detailed definition of the deterministic-victim version of PAMDP is in Appendix C.1.
A key to PA-AD is the director-actor collaboration mechanism. The input to director policy ν is the current state s in the original environment, while its output â is a signal to the actor denoting “which direction to perturb the victim policy into”. Â is designed to contain all “perturbing directions” in the policy space. That is, ∀â ∈ Â, there exists a constant θ0 ≥ 0 such that ∀θ ≤ θ0, π(·|s) + θ â‖â‖ belongs to the simplex ∆(A). The actor g takes in the state s and director’s direction â and then computes a state perturbation within the attack budget. Therefore, the director and the actor together induce a state adversary: h(s) := g(ν(s), s),∀s ∈ S . The definition of PAMDP is slightly different for a stochastic victim policy and a deterministic victim policy, as described below. For a stochastic victim π, the director’s action â ∈ Â is designed to be a unit vector lying in the policy simplex, denoting the perturbing direction in the policy space. The actor, once receiving the perturbing direction â, will “push” the policy as far as possible by perturbing s to g(â, s) ∈ B (s), as characterized by the optimization problem (G). In this way, the policy perturbation resulted by the director and the actor is always in the outermost boundary of BH (π) w.r.t. the victim π, where the optimal policy perturbation can be found according to Theorem 4. For a deterministic victim πD, the director’s action â ∈ ÂD can be viewed as a target action in the original action space, and the actor conducts targeted attacks to let the victim execute â, by forcing the logit corresponding to the target action to be larger than the logits of other actions.
In both the stochastic-victim and deterministic-victim case, PA-AD has an optimal formulation as stated in Theorem 7 (proven in Appendix D.2).
Theorem 7 (Optimality of PA-AD). For any MDPM, any fixed victim policy π, and any attack budget ≥ 0, an optimal policy ν∗ in M̂ induces an optimal state adversary against π inM. That is, the formulation of PA-AD is optimal, i.e., HPA-AD ⊆ H∗ .
Efficiency of PA-AD As commonly known, the sample complexity and computational cost of learning an MDP usually grow with the cardinalities of its state space and action space. Both SARL and PA-AD have state space S, the state space of the original MDP. But the action space of SA-RL is also S, while our PA-AD has action space R|A| for stochastic victim policies, or A for deterministic victim policies. In most DRL applications, the state space (e.g., images) is much larger than the action space, then PA-AD is generally more efficient than SA-RL as it learns a smaller MDP.
Algorithm 1: Policy Adversarial Actor Director (PA-AD) 1 Input: Initialization of director’s policy ν; victim policy π; budget ; start state s0 2 for t = 0, 1, 2, ... do 3 Director samples a policy perturbing direction ât ∼ ν(·|st) 4 Actor perturbs st to s̃t = gD(ât, st) if Victim is deterministic, otherwise to s̃t = g(ât, st) 5 Victim takes action at ∼ π(·|s̃t), proceeds to st+1, receives rt 6 Director saves (st, ât,−rt, st+1) to its buffer 7 Director updates its policy ν using any RL algorithm
The attacking procedure is illustrated in Algorithm 1. At step t, the director observes a state st, and proposes a policy perturbation ât, then the actor searches for a state perturbation to meet the policy perturbation. Afterwards, the victim acts with the perturbed state s̃t, then the director updates its policy based on the opposite value of the victim’s reward. Note that the actor solves a constrained optimization problem, (GD) or (G). Problem (GD) is similar to a targeted attack in supervised learning, while the stochastic version (G) can be approximately solved with a Lagrangian relaxation. In Appendix C.2, we provide our implementation details for solving the actor’s optimization, which empirically achieves state-of-the-art attack performance as verified in Section 6.
Extending to Continuous Action Space Our PA-AD can be extended to environments with continuous action spaces, where the actor minimizes the distance between the policy action and the target action, i.e., argmaxs′∈B (s)‖π(s
′)− â‖. More details and formal definitions of the variant of PA-AD in continuous action space are provided in Appendix C.3. In Section 6, we show experimental results in MuJoCo tasks, which have continuous action spaces.

heading: 5 RELATED WORK
text: Heuristic-based Evasion Attacks on States There are many works considering evasion attacks on the state observations in RL. Huang et al. (2017) first propose to use FGSM (Goodfellow et al., 2015) to craft adversarial states such that the probability that the agent selects the “best” action is minimized. The same objective is also used in a recent work by Korkmaz (2020), which adopts a Nesterov momentum-based optimization method to further improve the attack performance. Pattanaik et al. (2018) propose to lead the agent to select the “worst” action based on the victim’s Q function and use gradient descent to craft state perturbations. Zhang et al. (2020a) define the concept of a state-adversarial MDP (SAMDP) and propose two attack methods: Robust SARSA and Maximal Action Difference. The above heuristic-based methods are shown to be effective in many environments, although might not find the optimal adversaries, as proven in Appendix D.3.
RL-based Evasion Attacks on States As discussed in Section 4, SA-RL (Zhang et al., 2021) uses an end-to-end RL formulation to learn the optimal state adversary, which achieves state-ofthe-art attacking performance in MuJoCo tasks. For a pixel state space, an end-to-end RL attacker may not work as shown by our experiment in Atari games (Section 6). Russo & Proutiere (2021) propose to use feature extraction to convert the pixel state space to a small state space and then learn an end-to-end RL attacker. But such feature extractions require expert knowledge and can be hard to obtain in many real-world applications. In contrast, our PA-AD works for both pixel and vector state spaces and does not require expert knowledge.
Other Works Related to Adversarial RL There are many other papers studying adversarial RL from different perspectives, including limited-steps attacking (Lin et al., 2017; Kos & Song, 2017), multi-agent scenarios (Gleave et al., 2020), limited access to data (Inkawhich et al., 2020), and etc. Adversarial action attacks (Xiao et al., 2019; Tan et al., 2020; Tessler et al., 2019; Lee et al., 2021) are developed separately from state attacks; although we mainly consider state adversaries, our PA-AD can be extended to action attacks as formulated in Appendix A. Poisoning (Behzadan & Munir, 2017; Huang & Zhu, 2019; Sun et al., 2021; Zhang et al., 2020b; Rakhsha et al., 2020) is another type of adversarial attacks that manipulates the training data, different from evasion attacks that deprave a well-trained policy. Training a robust agent is the focus of many recent works (Pinto et al., 2017; Fischer et al., 2019; Lütjens et al., 2020; Oikarinen et al., 2020; Zhang et al., 2020a; 2021). Although our main goal is to find a strong attacker, we also show by experiments that our proposed attack method significantly improves the robustness of RL agents by adversarial training.

heading: 6 EXPERIMENTS
text: In this section, we show that PA-AD produces stronger evasion attacks than state-of-the-art attack algorithms on various OpenAI Gym environments, including Atari and MuJoCo tasks. Also, our experiment justifies that PA-AD can evaluate and improve the robustness of RL agents.
Baselines and Performance Metric We compare our proposed attack algorithm with existing evasion attack methods, including MinBest (Huang et al., 2017) which minimizes the probability that the agent chooses the “best” action, MinBest +Momentum (Korkmaz, 2020) which uses Nesterov momentum to improve the performance of MinBest, MinQ (Pattanaik et al., 2018) which leads
the agent to select actions with the lowest action values based on the agent’s Q network, Robust SARSA (RS) (Zhang et al., 2020a) which performs the MinQ attack with a learned stable Q network, MaxDiff (Zhang et al., 2020a) which maximizes the KL-divergence between the original victim policy and the perturbed policy, as well as SA-RL (Zhang et al., 2021) which directly learns the state adversary with RL methods. We consider state attacks with `∞ norm as in most literature (Zhang et al., 2020a; 2021). Appendix E.1 provides hyperparameter settings and implementation details.
PA-AD Finds the Strongest Adversaries in Atari Games We first evaluate the performance of PA-AD against well-trained DQN (Mnih et al., 2015) and A2C (Mnih et al., 2016) victim agents on Atari games with pixel state spaces. The observed pixel values are normalized to the range of [0, 1]. SA-RL and PA-AD adversaries are learned using the ACKTR algorithm (Wu et al., 2017) with the same number of steps. (Appendix E.1 shows hyperparameter settings.) Table 1 presents the experiment results, where PA-AD significantly outperforms all baselines against both DQN and A2C victims. In contrast, SA-RL does not converge to a good adversary in the tested Atari games with the same number of training steps as PA-AD, implying the importance of sample efficiency. Surprisingly, using a relatively small attack budget , PA-AD leads the agent to the lowest possible reward in many environments such as Pong, RoadRunner and Tutankham, whereas other attackers may require larger attack budget to achieve the same attack strength. Therefore, we point out that vanilla RL agents are extremely vulnerable to carefully learned adversarial attacks. Even if an RL agent works well under naive attacks, a carefully learned adversary can let an agent totally fail with the same attack budget, which stresses the importance of evaluating and improving the robustness of RL agents using the strongest adversaries. Our further investigation in Appendix F.3 shows that RL models can be generally more vulnerable than supervised classifiers, due to the different loss and architecture designs. In Appendix E.2.1, we show more experiments with various selections of the budget , where one can see PA-AD reduces the average reward more than all baselines over varying ’s in various environments.
PA-AD Finds the Strongest Adversaries MuJoCo Tasks We further evaluate PA-AD on MuJoCo games, where both state spaces and action spaces are continuous. We use the same setting with Zhang et al. (2021), where both the victim and the adversary are trained with PPO (Schulman et al., 2017). During test time, the victim executes a deterministic policy, and we use the deterministic
version of PA-AD with a continuous action space, as discussed in Section 4 and Appendix C.3. We use the same attack budget as in Zhang et al. (2021) for all MuJoCo environments. Results in Table 2 show that PA-AD reduces the reward much more than heuristic methods, and also outperforms SA-RL in most cases. In Ant, our PA-AD achieves much stronger attacks than SA-RL, since PA-AD is more efficient than SA-RL when the state space is large. Admittedly, PA-AD requires additional knowledge of the victim model, while SA-RL works in a black-box setting. Therefore, SA-RL is more applicable to black-box scenarios with a relatively small state space, whereas PA-AD is more applicable when the attacker has access to the victim (e.g. in adversarial training as shown in Table 3). Appendix E.2.3 provides more empirical comparison between SA-RL and PA-AD, which shows that PA-AD converges faster, takes less running time, and is less sensitive to hyperparameters than SA-RL by a proper exploitation of the victim model.
strongest attack. The gray cells are the most robust agents with the highest average rewards across attacks. Our PA-AD achieves the strongest attack against robust models, and our PA-ATLA-PPO achieves the most robust performance under multiple attacks. The attack budget ’s are the same as in Zhang et al. (2021).
Training and Evaluating Robust Agents A natural application of PA-AD is to evaluate the robustness of a known model, or to improve the robustness of an agent via adversarial training, where the attacker has white-box access to the victim. Inspired by ATLA (Zhang et al., 2021) which alternately trains an agent and an SA-RL attacker, we propose PA-ATLA, which alternately trains an agent and a PA-AD attacker. In Table 3, we evaluate the performance of PA-ATLA for a PPO agent (namely PA-ATLA-PPO) in MuJoCo tasks, compared with state-of-the-art robust training methods, SA-PPO (Zhang et al., 2020a) and ATLA-PPO (Zhang et al., 2021) 2. From the table, we make the following observations. (1) Our PA-AD attacker can significantly reduce the reward of previous “robust” agents. Take the Ant environment as an example, although SA-PPO and ATLA-PPO agents gain 2k+ and 3k+ rewards respectively under SA-RL, the previously strongest attack, our PAAD still reduces their rewards to about -1.3k and 200+ with the same attack budget. Therefore, we emphasize the importance of understanding the worst-case performance of RL agents, even robustlytrained agents. (2) Our PA-ATLA-PPO robust agents gain noticeably higher average rewards across attacks than other robust agents, especially under the strongest PA-AD attack. Under the SA-RL attack, PA-ATLA-PPO achieves comparable performance with ATLA-PPO, although ATLA-PPO agents are trained to be robust against SA-RL. Due to the efficiency of PA-AD, PA-ATLA-PPO requires fewer training steps than ATLA-PPO, as justified in Appendix E.2.4. The results of attacking and training robust models in Atari games are in Appendix E.2.5 and E.2.6, where PA-ATLA improves the robustness of Atari agents against strong attacks with as large as 3/255.

heading: 7 CONCLUSION
text: In this paper, we propose an attack algorithm called PA-AD for RL problems, which achieves optimal attacks in theory and significantly outperforms prior attack methods in experiments. PA-AD can be used to evaluate and improve the robustness of RL agents before deployment. A potential future direction is to use our formulation for robustifying agents under both state and action attacks.
2We use ATLA-PPO(LSTM)+SA Reg, the most robust method reported by Zhang et al. (2021).

heading: ETHICS STATEMENT
text: Despite the rapid advancement of interactive AI and ML systems using RL agents, the learning agent could fail catastrophically in the presence of adversarial attacks, exposing a serious vulnerability in current RL systems such as autonomous driving systems, market-making systems, and security monitoring systems. Therefore, there is an urgent need to understand the vulnerability of an RL model, otherwise, it may be risky to deploy a trained agent in real-life applications, where the observations of a sensor usually contain unavoidable noise.
Although the study of a strong attack method may be maliciously exploited to attack some RL systems, it is more important for the owners and users of RL systems to get aware of the vulnerability of their RL agents under the strongest possible adversary. As the old saying goes, “if you know yourself and your enemy, you’ll never lose a battle”. In this work, we propose an optimal and efficient algorithm for evasion attacks in Deep RL (DRL), which can significantly influence the performance of a well-trained DRL agent, by adding small perturbations to the state observations of the agent. Our proposed method can automatically measure the vulnerability of an RL agent, and discover the “flaw” in a model that might be maliciously attacked. We also show in experiments that our attack method can be applied to improve the robustness of an RL agent via robust training. Since our proposed attack method achieves state-of-the-art performance, the RL agent trained under our proposed attacker could be able to “defend” against any other adversarial attacks with the same constraints. Therefore, our work has the potential to help combat the threat to high-stakes systems.
A limitation of PA-AD is that it requires the “attacker” to know the victim’s policy, i.e., PA-AD is a white-box attack. If the attacker does not have full access to the victim, PA-AD can still be used based on the transferability of adversarial attacks (Huang et al., 2017), although the optimality guarantee does not hold in this case. However, this limitation only restricts the ability of the malicious attackers. In contrast, PA-AD should be used when one wants to evaluate the worst-case performance of one’s own RL agent, or to improve the robustness of an agent under any attacks, since PA-AD produces strong attacks efficiently. In these cases, PA-AD does have white-box access to the agent. Therefore, PA-AD is more beneficial to defenders than attackers.

heading: REPRODUCIBILITY STATEMENT
text: For theoretical results, we provide all detailed technical proofs and lemmas in Appendix. In Appendix A, we analyze the equivalence between evasion attacks and policy perturbations. In Appendix B, we theoretically prove some topological properties of the proposed Adv-policy-set, and derive Theorem 4 that the outermost boundary of BH (π) always contains an optimal policy perturbation. In Appendix D, we systematically characterize the optimality of many existing attack methods. We theoretically show (1) the existence of an optimal adversary, (2) the optimality of our proposed PA-AD, and (3) the optimality of many heuristic attacks, following our Definition 5 in Section 4. For experimental results, the detailed algorithm description in various types of environments is provided in Appendix C. In Appendix E, we illustrate the implementation details, environment settings, hyperparameter settings of our experiments. Additional experimental results show the performance of our algorithm from multiple aspects, including hyperparameter sensitivity, learning efficiency, etc. In addition, in Appendix F, we provide some detailed discussion on the algorithm design, as well as a comprehensive comparison between our method and prior works. The source code and running instructions for both Atari and MuJoCo experiments are in our supplementary materials. We also provide trained victim and attacker models so that one can directly test their performance using a test script we provide.

heading: A RELATIONSHIP BETWEEN EVASION ATTACKS AND POLICY PERTURBATIONS.
text: As mentioned in Section 2, all evasion attacks can be regarded as perturbations in the policy space. To be more specific, we consider the following 3 cases, where we assume the victim uses policy π.
Case 1 (attack on states): define the state adversary as function h such that ∀s ∈ S h(s) = s̃ ∈ B (s) := {s′ ∈ S : ‖s′ − s‖ ≤ }.
(For simplicity, we consider the attacks within a -radius norm ball.) In this case, for all s ∈ S, the victim samples action from πh(·|s) = π(·|h(s)) = π(s̃), which is equivalent to the victim executing a perturbed policy πh ∈ Π.
Case 2 (attack on actions for a deterministic π): define the action adversary as function h(A) : S ×A → A, and ∀s ∈ S, a ∈ A
h(A)(a|s) = ã ∈ B (a) := {a′ ∈ A : ‖a′ − a‖ ≤ }.
In this case, there exists a policy πh(A) such that πh(A)(s) = h(A)(a|s) = ã, which is equivalent to the victim executing policy πh(A) ∈ Π.
Case 3 (attack on actions for a stochastic π): define the action adversary as function h(A) : S×A → A, and ∀s ∈ S, a ∈ A
h(A)(a|s) = ã such that {‖π(·|s)− Pr(·|s)‖ ≤ }, where Pr(ã|s) denotes the probability that the action is perturbed into ã. In this case, there exists a policy πh(A) such that πh(A)(s) = Pr(·|s), which is equivalent to the victim executing policy πh(A) ∈ Π. Most existing evasion RL works (Huang et al., 2017; Pattanaik et al., 2018; Zhang et al., 2020a; 2021) focus on state attacks, while there are also some works (Tessler et al., 2019; Tan et al., 2020) studying action attacks. For example, Tessler et al. (Tessler et al., 2019) consider Case 2 and Case 3 above and train an agent that is robust to action perturbations.
These prior works study either state attacks or action attacks, considering them in two different scenarios. However, the ultimate goal of robust RL is to train an RL agent that is robust to any threat models. Otherwise, an agent that is robust against state attacks may still be ruined by an action attacker. We take a step further to this ultimate goal by proposing a framework, policy attack, that unifies observation attacks and action attacks.
Although the focus of this paper is on state attacks, we would like to point out that our proposed method can also deal with action attacks (the director proposes a policy perturbation direction, and an actor perturbs the action accordingly). It is also an exciting direction to explore hybrid attacks (multiple actors conducting states perturbations and action perturbations altogether, directed by a single director.) Our policy perturbation framework can also be easily incorporated in robust training procedures, as an agent that is robust to policy perturbations is simultaneously robust to both state attacks and action attacks.

heading: B TOPOLOGICAL PROPERTIES OF THE ADMISSIBLE ADVERSARIAL POLICY SET
text: As discussed in Section 3, finding the optimal state adversary in the admissible adversary set H can be converted to a problem of finding the optimal policy adversary in the Adv-policy-set BH (π). In this section, we characterize the topological properties of BH (π), and identify how the value function changes as the policy changes within BH (π). In Section B.1, we show that under the settings we consider, BH (π) is a connected and compact subset of Π. Then, Section B.2, we define some additional concepts and re-formulate the notations.
In Section B.3, we prove Theorem 4 in Section 3 that the outermost boundary of BH (π) always contains an optimal policy perturbation. In Section B.4, we prove that the value functions of policies in BH (π) (or more generally, any connected and compact subset of Π) form a polytope. Section B.6 shows an example of the polytope result with a 2-state MDP, and Section B.5 shows examples of the outermost boundary defined in Theorem 4.
B.1 THE SHAPE OF ADV-POLICY-SET BH (π)
It is important to note that BH (π) is generally connected and compact as stated in the following lemma. Lemma 8 (BH (π) is connected and compact). Given an MDPM, a policy π that is a continuous mapping, and admissible adversary set H := {h : h(s) ∈ B (s),∀s ∈ S} (where > 0 is a constant), the admissible adversarial policy set BH (π) is a connected and compact subset of Π.
Proof of Lemma 8. For an arbitrary state s ∈ S, an admissible adversary h ∈ H perturbs it within an `p norm ball B (s), which is connected and compact. Since π is a continuous mapping, we know π(s) is compact and connected.
Therefore, BH (π) as a Cartesian product of a finite number of compact and connected sets, is compact and connected.

heading: B.2 ADDITIONAL NOTATIONS AND DEFINITIONS FOR PROOFS
text: We first formally define some concepts and notations.
For a stationary and stochastic policy π : S → ∆(A), we can define the state-to-state transition function as Pπ(s′|s) := ∑ a∈A π(a|s)P (s′|s, a),∀s, s′ ∈ S,
and the state reward function as Rπ(s) := ∑ a∈A π(a|s)R(s, a),∀s ∈ S.
Then the value of π, denoted as V π , can be computed via the Bellman equation
V π = Rπ + γPπV π = (I − γPπ)−1Rπ.
We further use Πsi to denote the projection of Π into the simplex of the i-th state, i.e., the space of action distributions at state si.
Let fv : Π → R|S| be a mapping that maps policies to their corresponding value functions. Let V = fv(Π) be the space of all value functions. Dadashi et al. (Dadashi et al., 2019) show that the image of fv applied to the space of policies, i.e., fv(Π), form a (possibly non-convex) polytope as defined below. Definition 9 ((Possibly non-convex) polytope). A is called a convex polytope iff there are k ∈ N points x1, x2, · · · , xk ∈ Rn such that A = Conv(x1, · · · , xk). Furthermore, a (possibly nonconvex) polytope is defined as a finite union of convex polytopes.
And a more general concept is (possibly non-convex) polyhedron, which might not be bounded. Definition 10 ((Possibly non-convex) polyhedron). A is called a convex polyhedron iff it is the intersection of k ∈ N half-spaces B̂1, B̂2, · · · , B̂k, i.e., A = ∩ki=1B̂i. Furthermore, a (possibly non-convex) polyhedron is defined as a finite union of convex polyhedra.
In addition, let Y πs1,··· ,sk be the set of policies that agree with π on states s1, · · · , sk. Dadashi et al. (Dadashi et al., 2019) also prove that the values of policies that agree on all but one state s, i.e., fv(Y π S\{s}), form a line segment, which can be bracketed by two policies that are deterministic on s. Our Lemma 14 extends this line segment result to our setting where policies are restricted in a subset of policies.

heading: B.3 PROOF OF THEOREM 4: BOUNDARY CONTAINS OPTIMAL POLICY PERTURBATIONS
text: Lemma 4 in Dadashi et al. (2019) shows that policies agreeing on all but one state have certain monotone relations. We restate this result in Lemma 11 below. Lemma 11 (Monotone Policy Interpolation). For any π0, π1 ∈ Y πS\{s} that agree with π on all states except for s ∈ S, define a function l : [0, 1]→ V as
l(α) = fv(απ1 + (1− α)π0). Then we have (1) l(0) < l(1) or l(1) < l(0) (< stands for element-wise greater than or equal to); (2) If l(0) = l(1), then l(α) = l(0),∀α ∈ [0, 1]; (3) If l(0) 6= l(1), then there is a strictly monotonic rational function ρ : [0, 1] → R, such that l(α) = ρ(α)l(1) + (1− ρ(α))l(0).
More intuitively, Lemma 11 suggests that the value of πα := απ1 + (1 − α)π0 changes (strictly) monotonically with α, unless the values of π0, π1 and πα are all equal. With this result, we can proceed to prove Theorem 4.
Proof of Theorem 4. We will prove the theorem by contradiction.
Suppose there is a policy π̂ ∈ BH (π) such that π̂ /∈ ∂πBH (π) and fv(π̂) = V π̂ < V π̃,∀π̃ ∈ BH (π), i.e., there is no optimal policy adversary on the outermost boundary of BH (π). Then according to the definition of ∂πBH (π), there exists at least one state s ∈ S such that we can find another policy π′ ∈ BH (π) agreeing with π̂ on all states except for s, where π′(s) satisfies
π̂(·|s) = απ(·|s) + (1− α)π′(·|s) for some scalar α ∈ (0, 1). Then by Lemma 11, either of the following happens:
(1) fv(π) fv(π̂) fv(π′). (2) fv(π) = fv(π̂) = fv(π′);
Note that fv(π̂) fv(π) is impossible because we have assumed π̂ has the lowest value over all policies in BH (π) including π. If (1) is true, then π′ is a better policy adversary than π̂ in BH (π), which contradicts with the assumption.
If (2) is true, then π′ is another optimal policy adversary. By recursively applying the above process to π′, we can finally find an optimal policy adversary on the outermost boundary of BH (π), which also contradicts with our assumption.
In summary, there is always an optimal policy adversary lying on the outermost boundary of BH (π).

heading: B.4 PROOF OF THEOREM 12: VALUES OF POLICIES IN ADMISSIBLE ADVERSARIAL POLICY SET FORM A POLYTOPE
text: We first present a theorem that describes the “shape” of the value functions generated by all admissible adversaries (admissible adversarial policies). Theorem 12 (Policy Perturbation Polytope). For a finite MDP M, consider a policy π and an Adv-policy-set BH (π). The space of values (a subspace of R|S|) of all policies in BH (π), denoted by VBH (π), is a (possibly non-convex) polytope.
In the remaining of this section, we prove a more general version of Theorem 12 as below. Theorem 13 (Policy Subset Polytope). For a finite MDPM, consider a connected and compact subset of Π, denoted as T . The space of values (a subspace of R|S|) of all policies in T , denoted by VT , is a (possibly non-convex) polytope.
According to Lemma 8, BH (π) is a connected and compact subset of Π, thus Theorem 12 is a special case of Theorem 13.
Additional Notations To prove Theorem 13, we further define a variant of Y πs1,··· ,sk as T π s1,··· ,sk , which is the set of policies that are in T and agree with π on states s1, · · · , sk, i.e.,
T πs1,··· ,sk := {π ′ ∈ T : π′(si) = π(si),∀i = 1, · · · , k}.
Note that different from BH (π), T is no longer restricted under an admissible adversary set and can be any connected and compact subset of Π.
The following lemma shows that the values of policies in T that agree on all but one state form a line segment.
Lemma 14. For a policy π ∈ T and an arbitrary state s ∈ S, there are two policies in ∂πT πS\{s}, namely π−s , π + s , such that ∀π′ ∈ T πS\{s},
fv(π − s ) 4 fv(π ′) 4 fv(π + s ), (3)
where 4 denotes element-wise less than or equal to (if a 4 b, then ai ≤ bi for all index i). Moreover, the image of fv restricted to T πS\{s} is a line segment.
Proof of Lemma 14. Lemma 5 in Dadashi et al. (2019) has shown that fv is infinitely differentiable on Π, hence we know fv(T πS\{s}) is compact and connected. According to Lemma 4 in Dadashi et al. (2019), for any two policies π1, π2 ∈ Y πS\{s}, either fv(π1) 4 fv(π2), or fv(π2) 4 fv(π1) (there exists a total order). The same property applies to T πS\{s} since T π S\{s} is a subset of Y π S\{s}.
Therefore, there exists π−s and π + s that achieve the minimum and maximum over all policies in T πS\{s}. Next we show π − s and π + s can be found on the outermost boundary of T πS\{s}.
Assume π+s /∈ ∂πT πS\{s}, and for all π̃ ∈ T π S\{s}, fv(π̃) ≺ fv(π + s ). Then we can find another policy π′ ∈ ∂πT πS\{s} such that π + s = απ + (1 − α)π′ for some scalar α ∈ (0, 1). Then according to Lemma 11, fv(π′) < fv(π+s ), contradicting with the assumption. Therefore, one should be able to find a policy on the outermost boundary of T πS\{s} whose value dominates all other policies. And similarly, we can also find π−s on ∂πT πS\{s}.
Furthermore, fv(T πS\{s}) is a subset of fv(Y π S\{s}) since T π S\{s} is a subset of Y π S\{s}. Given that fv(Y π S\{s}) is a line segment, and fv(T π S\{s}) is connected, we can conclude that fv(T π S\{s}) is also a line segment.
Next, the following lemma shows that π+s and π − s and their linear combinations can generate values that cover the set fv(T πS\{s}).
Lemma 15. For a policy π ∈ T , an arbitrary state s ∈ S, and π+s , π−s defined in Lemma 14, the following three sets are equivalent: (1) fv(T πS\{s}); (2) fv ( closure(T πS\{s}) ) , where closure(·) is the convex closure of a set; (3) {fv(απ+s + (1− α)π−s )|α ∈ [0, 1]}; (4) {αfv(π+s ) + (1− α)fv(π−s )|α ∈ [0, 1]};
Proof of Lemma 15. We show the equivalence by showing (1) ⊆ (4) ⊆ (3) ⊆ (2) ⊆ (1) as below. (2)⊆ (1): For any π1, π2 ∈ T πS\{s}, without loss of generality, suppose fv(π1) 4 fv(π2). According to Lemma 11, for any α ∈ [0, 1], fv(π1) 4 απ1 + (1 − α)π2 4 fv(π2). Therefore, any convex combinations of policies in T πS\{s} has value that is in the range of fv(T π S\{s}). So the values of policies in the convex closure of T πS\{s} do not exceed fv(T π S\{s}), i.e., (2) ⊆ (1).
(3) ⊆ (2): Based on the definition, απ+s + (1− α)π−s ∈ closure(T πS\{s}), so (3) ⊆ (2).
(4)⊆ (3): According to Lemma 11, there exists a strictly monotonic rational function ρ : [0, 1]→ R, such that
l(α) = fv(απ + s + (1− α)π−s ) = ρ(α)fv(π+s ) + (1− ρ(α))fv(π−s ).
Therefore, due to intermediate value theorem, for α ∈ [0, 1], ρ(α) takes all values from 0 to 1. So (4) = (3).
(1) ⊆ (4): Lemma 14 shows that fv(T πS\{s}) is a line segment bracketed by fv(π + s ) and fv(π − s ). Therefore, for any π′ ∈ T πS\{s}, its value is a convex combination of fv(π + s ) and fv(π − s ).
Next, we show that the relative boundary of the value space constrained to T πs1,··· ,sk is covered by policies that dominate or are dominated in at least one state. The relative interior of set A in B is defined as the set of points in A that have a relative neighborhood in A ∩ B, denoted as relintBA. The relative boundary of set A in B, denoted as ∂BA, is defined as the set of points in A that are not in the relative interior of A, i.e., ∂BA = A\relintBA. When there is no ambiguity, we omit the subscript of ∂ to simplify notations.
In addition, we introduce another notation Fπs1,··· ,sk := V π + span(Cπk+1, · · · , Cπ|S|), where C π i stands for the i-th column of the matrix (I−γPπ)−1. Note that Fπs1,··· ,sk is the same withH π s1,··· ,sk in Dadashi et al. Dadashi et al. (2019), and we change H to F in order to distinguish from the admissible adversary set H defined in our paper.
Lemma 16. For a policy π ∈ T , k ≤ |S|, and a set of policies T πs1,··· ,sk that agree with π on s1, · · · , sk (perturb π only at sk+1, · · · , s|S|), define Vt := fv(T πs1,··· ,sk). Define two sets of policies X+s := {π′ ∈ T πs1,··· ,sk : π ′(·|s) = π+s (·|s)}, and X−s := {π′ ∈ T πs1,··· ,sk : π ′(·|s) = π−s (·|s)}. We have that the relative boundary of Vt in Fπs1,··· ,sk is included in the value functions spanned by policies in T πs1,··· ,sk ∩ (X + sj ∪X − sj ) for at least one s /∈ {s1, · · · , sk}, i.e.,
∂Vt ⊂ |S|⋃
j=k+1
fv(T πs1,··· ,sk ∩ (X + sj ∪X − sj ))
Proof of Lemma 16. We first prove the following claim:
Claim 1: For a policy π0 ∈ T πs1,··· ,sk , if ∀j ∈ {k+ 1, · · · , |S|}, @π ′ ∈ closure(T πs1,··· ,sk)∩ (X + sj ∪

heading: X−sj ) such that fv(π
text: ′) = fv(π0), then fv(π0) has a relative neighborhood in Vt ∩ Fπs1,··· ,sk .
First, based on Lemma 14 and Lemma 15, we can construct a policy π̂ ∈ closure(T πs1,··· ,sk) such that fv(π̂) = fv(π0) through the following steps:
Algorithm 2: Constructing π̂ 1 Set πk = π0 2 for j = k + 1, · · · , |S| do 3 Find π+sj , π − sj ∈ T πj−1 S\{sj} 4 Find πj = α̂jπ+sj + (1− α̂j)π − sj such that fv(πj) = fv(πj−1) 5 Return π̂ = π|S|
Denote the concatenation of αj’s as a vector α̂ := [α̂k+1, · · · , α̂|S|].
According to the assumption that ∀j ∈ {k + 1, · · · , |S|}, @π′ ∈ closure(T πs1,··· ,sk) ∩ (X + sj ∪X − sj ) such that fv(π′) = fv(π0), we have α̂j /∈ {0, 1},∀j = k + 1, · · · , |S|. Then, define a function φ : (0, 1)|S|−k → Vt such that
φ(α) = fv(πα), where
{ πα(·|sj) = απ+sj + (1− α)π − sj if j ∈ {k + 1, · · · , |S|}
πα(·|sj) = π̂(·|sj) otherwise
Then we have that
1. φ is continuously differentiable.
2. φ(α̂) = fv(π̂).
3. ∂φ∂αj is non-zero at α̂ (because of Lemma 11 (3)).
4. ∂φ∂αj is along the i-the column of (I − γP π̂)−1 (see Lemma 3 in Dadashi et al. Dadashi
et al. (2019)).
Therefore, by the inverse theorem function, there is a neighborhood of φ(α) = fv(π̂) in the image space.
Now we have proved Claim 1. As a result, for any policy π0 ∈ T πs1,··· ,sk , if fv(π0) is in the relative boundary of Vt in Fπs1,··· ,sk , then ∃j ∈ {k + 1, · · · , |S|}, π ′ ∈ closure(T πs1,··· ,sk) ∩ (X + sj ∪ X − sj ) such that fv(π′) = fv(π0). Based on Lemma 15, we can also find π′′ ∈ T πs1,··· ,sk ∩ (X + sj ∪ X − sj ) such that fv(π′′) = fv(π0). So Lemma 16 holds.
Now, we are finally ready to prove Theorem 13.
Proof of Theorem 13. We will show that ∀{s1, · · · , sk} ⊆ S, the value Vt = fv(T πs1,··· ,sk) is a polytope.
We prove the above claim by induction on the cardinality of the number of states k. In the base case where k = |S|, Vt = {fv(π)} is a polytope. Suppose the claim holds for k + 1, then we show it also holds for k, i.e., for a policy π ∈ Π, the value of T πs1,··· ,sk ⊆ Y π s1,··· ,sk ⊆ Π for a polytope.
According to Lemma 16, we have
∂Vt ⊂ |S|⋃
j=k+1
fv(T πs1,··· ,sk ∩ (X + sj ∪X − sj )) = |S|⋃ j=k+1 Vt ∩ (F+sj ∪ F − sj ))
where ∂Vt denotes the relative boundary of Vt in Fπs1,··· ,sk ; F + sj and F − sj are two affine hyperplanes of Fπs1,··· ,sk , standing for the value space of policies that agree with π + sj and π − sj in state sj respectively.
Then we can get
1. Vt = fv(T πs1,··· ,sk) is closed as T π s1,··· ,sk is compact and fv is continuous.
2. ∂Vt ⊂ ⋃|S| j=k+1(F + sj ∪ F − sj )), a finite number of affine hyperplanes in F π s1,··· ,sk .
3. Vt ∩ F+sj (or V t ∩ F−sj ) is a polyhedron by induction assumption.
Hence, based on Proposition 1 by Dadashi et al. Dadashi et al. (2019), we get Vt is a polyhedron. Since Vt ⊆ V is bounded, we can further conclude that Vt is a polytope. Therefore, for an arbitrary connected and compact set of policies T ⊆ Π, let π ∈ T be an arbitrary policy in T , then fv(T ) = fv(T π∅ ) is a polytope.

heading: B.5 EXAMPLES OF THE OUTERMOST BOUNDARY
text: See Figure 5 for examples of the outermost boundary for different BH (π)’s.

heading: B.6 AN EXAMPLE OF THE POLICY PERTURBATION POLYTOPE
text: An example is given by Figure 6, where we define an MDP with 2 states and 3 actions. We train an DQN agent with one-hot encodings of the states, and then randomly perturb the states within an `∞ ball with = 0.8. By sampling 5M random policies, and 100K random perturbations, we visualize the value space of approximately the whole policy space Π and the admissible adversarial policy set BH (π), both of which are polytopes (boundaries are flat). A learning agent searches for the optimal policy π∗ whose value is the upper right vertex of the larger blue polytope, while the attacker attempts to find an optimal adversary h∗, which perturbs a given clean policy π to the worst perturbed policy πh∗ whose value is the lower left vertex of the smaller green polytope. This also justifies the fact that learning an optimal adversary is as difficult as learning an optimal policy in an RL problem.
The example MDPMex:
|A| = 3, γ = 0.8 r̂ = [−0.1,−1., 0.1, 0.4, 1.5, 0.1] P̂ = [[0.9, 0.1], [0.2, 0.8], [0.7, 0.3], [0.05, 0.95], [0.25, 0.75], [0.3, 0.7]]
The base/clean policy π:
π(a1|s1) = 0.215, π(a2|s1) = 0.429, π(a3|s1) = 0.356 π(a1|s2) = 0.271, π(a2|s2) = 0.592, π(a3|s2) = 0.137

heading: C EXTENTIONS AND ADDITIONAL DETAILS OF OUR ALGORITHM

heading: C.1 ATTACKING A DETERMINISTIC VICTIM POLICY
text: For a deterministic victim πD = argmaxaπ(a|s), we define Deterministic Policy Adversary MDP (D-PAMDP) as below, where a subscript D is added to all components to distinguish them from their stochastic counterparts. In D-PAMDP, the director proposes a target action âD ∈ A(=: ÂD), and the actor tries its best to let the victim output this target action.
Definition 17 (Deterministic Policy Adversary MDP (D-PAMDP)). Given an MDP M = 〈S,A, P,R, γ〉, a fixed and deterministic victim policy πD, we define a Deterministic Policy Adversarial MDP M̂D = 〈S, ÂD, P̂D, R̂D, γ〉, where the action space is ÂD = ÂD, and ∀s, s′ ∈ S,∀â ∈ A,
P̂D(s ′|s, â) = P (s′|s, πD(g(â, s))), R̂D(s, â) = −R(s, πD(g(â, s))).

heading: The actor function g is defined as
text: gD(â, s) = argmaxs′∈B (s) ( π(â|s′)−maxa∈A,a 6=âπ(a|s′) ) (GD)
The optimal policy of D-PAMDP is an optimal adversary against πD as proved in Appendix D.2.2
C.2 IMPLEMENTATION DETAILS OF PA-AD
To address the actor function g (or gD) defined in (G) and (GD), we let the actor maximize objectives JD and J within the B (·) ball around the original state, for a deterministic victim and a stochastic victim, respectively. Below we explicitly define JD and J .
Actor Objective for Deterministic Victim For the deterministic variant of PA-AD, the actor function (GD) is simple and can be directly solved to identify the optimal adversary. Concretely, we define the following objective
JD(s ′; â, s) := π(â|s′)−maxa∈A,a6=âπ(a|s′), (JD)
which can be realized with the multi-class classification hinge loss. In practice, a relaxed crossentropy objective can also be used to maximize π(â|s′). Actor Objective for Stochastic Victim Different from the deterministic-victim case, the actor function for a stochastic victim defined in (G) requires solving a more complex optimization problem with a non-convex constraint set, which in practice can be relaxed to (Ĵ) (a Lagrangian relaxation) to efficiently get an approximation of the optimal adversary.
argmaxs′∈B (s)J(s ′; â, s) := ‖π(·|s′)− π(·|s)‖+ λ× CosineSim
( π(·|s′)− π(·|s), â ) (Ĵ)
where CosineSim in the second refers to the cosine similarity function; the first term measures how far away the policy is perturbed from the victim policy; λ is a hyper-parameter controlling the tradeoff between the two terms. Experimental results show that our PA-AD is not sensitive to the value of λ. In our reported results in Section 6, we set λ as 1. Appendix E.2.2 shows the evaluation of our algorithm using varying λ’s.
The procedure of learning the optimal adversary is depicted in Algorithm 3, where we simply use the Fast Gradient Sign Method (FGSM) (Goodfellow et al., 2015) to approximately solve the actor’s objective, although more advanced solvers such as Projected Gradient Decent (PGD) can be applied to further improve the performance. Experiment results in Section 6 verify that the above FGSMbased implementation achieves state-of-the-art attack performance.
What is the Influence of the Relaxation in (Ĵ)? First, it is important that the relaxation is only needed for a stochastic victim. For a deterministic victim, which is often the case in practice, the actor solves the original unrelaxed objective. Second, as we will discuss in the next paragraph, the optimality of both SA-RL and PA-AD is regarding the formulation. That is, SA-RL and PA-AD formulate the optimal attack problem as an MDP whose optimal policy is the optimal adversary. However, in a large-scale task, deep RL algorithms themselves usually do not converge to the globally optimal policy and exploration becomes the main challenge. Thus, when the adversary’s MDP is large, the suboptimality caused by the RL solver due to exploration difficulties could be much more severe than the suboptimality caused by
Algorithm 3: Policy Adversarial Actor Director (PA-AD) with FGSM 1 Input: Initialization of director’s policy ν; victim policy π; budget ; start state s0 2 for t = 0, 1, 2, ... do 3 Director samples a policy perturbing direction ât ∼ ν(·|st) 4 if Victim is deterministic then 5 # for a deterministic victim, JD() is defined in Equation (JD) 6 Actor computes the gradient of its objective∇δJD(st + δ; ât, st) 7 else 8 # for a stochastic victim, J() is defined in Equation (Ĵ) 9 Actor computes the gradient of its objective∇δJ(st + δ; ât, st)
10 Actor sets s̃t = st + · sign(δ) 11 Victim takes action at ∼ π(·|s̃t), proceeds to st+1, receives rt 12 Director saves (st, ât,−rt, st+1) to its buffer 13 Director updates its policy ν using any RL algorithm
the relaxation of the formulation. The comparison between SA-RL and PA-AD in our experiments can justify that the size of the adversary MDP has a larger impact than the relaxation of the problem on the final solution found by the attackers. Third, in Appendix F.1, we empirically show that with the relaxed objective, PA-AD can still find the optimal attacker in 3 example environments.
Optimality in Formulation v.s. Approximated Optimality in Practice PA-AD has an optimal formulation, as the optimal solution to its objective (the optimal policy in PAMDP) is always an optimal adversary (Theorem 7). Similarly, the previous attack method SA-RL has an optimal solution since the optimal policy in the adversary’s MDP is also an optimal adversary. However, in practice where the environments are in a large scale and the number of samples is finite, the optimal policy is not guaranteed to be found by either PA-AD and SA-RL with deep RL algorithms. Therefore, for practical consideration, our goal is to search for a good solution or approximate the optimal solution using optimization techniques (e.g. actor-critic learning, one-step FGSM attack, Lagrangian relaxation for the stochastic-victim attack). In experiments (Section 6), we show that our implementation universally finds stronger attackers than prior methods, which verifies the effectiveness of both our theoretical framework and our practical implementation.
C.3 VARIANTS FOR ENVIRONMENTS WITH CONTINUOUS ACTION SPACES
Although the analysis in the main paper focuses on an MDP whose action space is discrete, our algorithm also extends to a continuous action space as justified in our experiments.

heading: C.3.1 FOR A DETERMINISTIC VICTIM
text: In this case, we can still use the formulation D-PAMDP, but a slightly different actor function gD(â, s) = argmins′∈B (s)‖πD(s ′)− â‖. (GCD)

heading: C.3.2 FOR A STOCHASTIC VICTIM
text: Different from a stochastic victim in a discrete action space whose actions are sampled from a categorical distribution, a stochastic victim in a continuous action space usually follows a parametrized probability distribution with a certain family of distributions, usually Gaussian distributions. In this case, the formulation of PAMDP in Definition 6 is impractical. However, since the mean of a Gaussian distribution has the largest probability to be selected, one can still use the formulation in (GCD), while replacing πD(s′) with the mean of the output distribution. Then, the director and the actor can collaboratively let the victim output a Gaussian distribution whose mean is the target action. If higher accuracy is needed, we can use another variant of PAMDP, named Continuous Policy Adversary MDP (C-PAMDP) that can also control the variance of the Gaussian distribution.
Definition 18 (Continuous Policy Adversary MDP (C-PAMDP)). Given an MDP M = 〈S,A, P,R, γ〉 where A is continuous, a fixed and stochastic victim policy π, we define a Con-
tinuous Policy Adversarial MDP M̂C = 〈S, ÂC , P̂C , R̂C , γ〉, where the action space is ÂD = A, and ∀s, s′ ∈ S,∀â ∈ A,
P̂ (s′|s, â) = ∫ A π(a|g(â, s))P (s′|s, a) da, R̂(s, â) = − ∫ A π(a|g(â, s))R(s, a)da.

heading: The actor function g is defined as
text: g(â, s) = argmins′∈B (s)KL(π(·|s
′)||N (â, σ2I|A|)). (GC) where σ is a hyper-parameter, and N denotes a multivariate Gaussian distribution.
In short, Equation (GC) encourages the victim to output a distribution that is similar to the target distribution. The hyperparameter σ controls the standard deviation of the target distribution. One can set σ to be small in order to let the victim execute the target action â with higher probabilities.

heading: D CHARACTERIZE OPTIMALITY OF EVASION ATTACKS
text: In this section, we provide a detailed characterization for the optimality of evasion attacks from the perspective of policy perturbation, following Definition 5 in Section 4. Section D.1 establishes the existence of the optimal policy adversary which is defined in Section 3. Section D.2 then provides a proof for Theorem 7 that the formulation of PA-AD is optimal. We also analyze the optimality of heuristic attacks in Section D.3.

heading: D.1 EXISTENCE OF AN OPTIMAL POLICY ADVERSARY
text: Theorem 19 (Existence of An Optimal Policy Adversary). Given an MDPM = 〈S,A, P,R, γ〉, and a fixed stationary policy π onM, let H be a non-empty set of admissible state adversaries and BH (π) be the corresponding Adv-policy-set, then there exists an optimal policy adversary πh∗ ∈ BH (π) such that πh∗ ∈ argminπh∈BH (π)V πh M (s),∀s ∈ S.
Proof. We prove Theorem 19 by constructing a new MDP corresponding to the original MDPM and the victim π.
Definition 20 (Policy Perturbation MDP). For a given MDP M, a fixed stochastic victim policy π, and an admissible state adversary set H , define a policy perturbation MDP as MP = 〈S,AP , PP , RP , γ〉, where AP = ∆(A), and ∀s ∈ S, aP ∈ AP ,
RP (s, aP ) := { − ∑ a∈A aP (a|s)R(s, a) if ∃h ∈ H s.t. aP (·|s) = π(·|h(s))
−∞ otherwise (4)
PP (s ′|s, aP ) := ∑ a∈A aP (a|s)P (s′|s, a) (5)
Then we can prove Theorem 19 by proving the following lemma.
Lemma 21. The optimal policy inMP is an optimal policy adversary for π inM.
Let NP denote the set of deterministic policies in MP . According to the traditional MDP theory (Puterman, 1994), there exists a deterministic policy that is optimal in MP . Note that H is non-empty, so there exists at least one policy inMP with value ≥ −∞, and then the optimal policy should have value≥ −∞. Denote this optimal and deterministic policy as ν∗P ∈ NP . Then we write the Bellman equation of ν∗P , i.e.,
V ν∗P P (s) = max
νP∈NP RP (s, νP (s)) + γ ∑ s′∈S PP (s ′|s, νP (s))V νPP (s ′)
= max νP∈NP [ − ∑ a∈A νP (a|s)R(s, a) + γ ∑ s′∈S ∑ a∈A νP (a|s)P (s′|s, a)V νPP (s ′) ]
= max νP∈NP ∑ a∈A νP (a|s)
[ −R(s, a) + γ
∑ s′∈S P (s′|s, a)V νPP (s ′)
] (6)
Note that ν∗P (s) is a distribution on action space, ν ∗ P (a|s) is the probability of a given by distribution ν∗(s).
Multiply both sides of Equation (6) by −1, and we obtain
−V ν ∗ P
P (s) = min ν∈NP ∑ a∈A νP (s)(a|s)
[ R(s, a) + γ
∑ s′∈S P (s′|s, a) ( − V νPP (s
′) )]
(7)
In the original MDPM, an optimal policy adversary (if exists) πh∗ for π should satisfy
V πh∗ (s) = min πh∈BH (π) ∑ a∈A πh(a|s)
[ R(s, a) + γ
∑ s′∈S P (s′|s, a)V πh(s′)
] (8)
By comparing Equation (7) and Equation (8) we get the conclusion that ν∗P is an optimal policy adversary for π inM.

heading: D.2 PROOF OF THEOREM 7: OPTIMALITY OF OUR PA-AD
text: In this section, we provide theoretical proof of the optimality of our proposed evasion RL algorithm PA-AD.

heading: D.2.1 OPTIMALITY OF PA-AD FOR A STOCHASTIC VICTIM
text: We first build a connection between the PAMDP M̂ defined in Definition 6 (Section 4) and the policy perturbation MDP defined in Definition 20 (Appendix D.1).
A deterministic policy ν in the PAMDP M̂ can induce a policy ν̂P inMP in the following way: ν̂P (s) = π(·|g(ν(s), s)),∀s ∈ S . More importantly, the values of ν and ν̂P in M̂ and MP are equal because of the formulations of the two MDPs, i.e., V̂ ν = V ν̂PP , where V̂ and VP denote the value functions in M̂ and VP respectively. Proposition 22 below builds the connection of the optimality between the policies in these two MDPs. Proposition 22. An optimal policy in M̂ induces an optimal policy inMP .
Proof of Proposition 22. Let ν∗ be an deterministic optimal policy in M̂, and it induces a policy in MP , namely ν̂P . Let us assume ν̂P is not an optimal policy in MP , hence there exists a policy ν∗P in MP s.t. V ν∗P P (s) > V ν̂P P (s) for at least one s ∈ S. And based on Theorem 4, we are able to find such a ν∗P whose corresponding policy perturbation is on the outermost boundary of B(π), i.e., ν∗ ∈ ∂πBH (π).
Then we can construct a policy ν′ in M̂ such that ν′(s) = ν∗P (s) − π(s),∀s ∈ S. And based on Equation (G), π(·|g(ν′(s), s)) is in ∂πB(π(s)) for all s ∈ S. According to the definition of ∂π , if two policy perturbations perturb π in the same direction and are both on the outermost boundary, then they are equal. Thus, we can conclude that π(g(ν′(s), s)) = ν∗P (s),∀s ∈ S. Then we obtain V̂ ν ′ (s) = V ν∗P P (s),∀s ∈ S.
Now we have conditions: (1) V̂ ν
∗ (s) = V ν̂PP (s),∀s ∈ S;
(2) V ν ∗ P
P (s) > V ν̂P P (s) for at least one s ∈ S;
(3) ∃ν′ such that V̂ ν′(s) = V ν ∗ P
P (s),∀s ∈ S.
From (1), (2) and (3), we can conclude that V̂ ν ′ (s) > V̂ ν ∗ (s) for at least one s ∈ S, which conflicts with the assumption that ν∗ is optimal in M̂. Therefore, Proposition 22 is proven.
Proposition 22 and Lemma 21 together justifies that the optimal policy of M̂, namely ν∗, induces an optimal policy adversary for π in the originalM. Then, if the director learns the optimal policy in M̂, then it collaborates with the actor and generates the optimal state adversary h∗ by h∗(s) = g(ν∗(s), s),∀s ∈ S.

heading: D.2.2 OPTIMALITY OF OUR PA-AD FOR A DETERMINISTIC VICTIM
text: In this section, we show that the optimal policy in D-PAMDP (the deterministic variant of PAMDP defined in Appendix C.1) also induces an optimal policy adversary in the original environment.
Let πD be a deterministic policy reduced from a stochastic policy π, i.e., πD(s) := argmaxa∈Aπ(a|s),∀s ∈ S. Note that in this case, the Adv-policy-set BH (π) is not connected as it contains only deterministic policies. Therefore, we re-formulate the policy perturbation MDP introduced in Appendix D.1 with a deterministic victim as below:
Definition 23 (Deterministic Policy Perturbation MDP). For a given MDPM, a fixed deterministic victim policy π, and an admissible adversary set H , define a deterministic policy perturbation MDP asMDP = 〈S,ADP , PDP , RDP , γ〉, where ADP = A, and ∀s ∈ S, aDP ∈ ADP ,
RDP (s, aDP ) := { −R(s, aDP ) if ∃h ∈ H s.t. aDP (s) = πD(h(s)) −∞ otherwise (9)
PDP (s ′|s, aDP ) := P (s, aDP ) (10)
MDP can be viewed as a special case ofMP where only deterministic policies have≥ −∞ values. Therefore Theorem 19 and Lemma 21 also hold for deterministic victims.
Next we will show that an optimal policy in M̂D induces an optimal policy inMDP .
Proposition 24. An optimal policy in M̂D induces an optimal policy inMDP .
Proof of Proposition 24. We will prove Proposition 24 by contradiction. Let ν∗ be an optimal policy in M̂D, and it induces a policy inMDP , namely ν̂DP . Let us assume ν̂DP is not an optimal policy inMDP , hence there exists a deterministic policy ν∗DP in MDP s.t. V ν∗DP DP (s) > V ν̂DP DP (s) for at least one s ∈ S. Without loss of generality, suppose V ν∗DP DP (s0) > V ν̂DP DP (s0).
Next we construct another policy ν′ in M̂D by setting ν′(s) = ν∗DP (s),∀s ∈ S . Given that ν∗DP is deterministic, ν′ is also a deterministic policy. So we use ν∗DP (s) and ν
′(s) to denote the action selected by ν∗DP and ν ′ respectively at state s.
For an arbitrary state si, let ai := ν∗DP (si). Since ν ∗ DP is the optimal policy in MDP , we get that there exists a state adversary h ∈ H such that πD(h(si)) = ai, or equivalently, there exists a state s̃i ∈ B (si) such that argmaxa∈Aπ(s̃i) = ai. Then, the solution to the actor’s optimization problem (GD) given direction ai and state si, denoted as s̃∗, satisfies
s̃∗ = argmaxs′∈B (s) ( π(â|s′)− argmaxa∈A,a 6=âπ(a|s′) ) (11)
and we can get π(â|s̃∗)− argmaxa∈A,a6=âπ(a|s̃∗) ≥ π(â|s̃i)− argmaxa∈A,a 6=âπ(a|s̃i) > 0 (12) Given that argmaxa∈Aπ(ai|s̃i) = ai, we obtain argmaxa∈Aπ(ai|s̃∗) = ai, and hence πD(gD(ai, si)) = ai. Since this relation holds for an arbitrary state s, we can get
πD(gD(ν ′(s), s)) = πD(gD(ν ′(s), s)) = ν′(s),∀s ∈ S (13)
Also, we have ∀s ∈ S V̂ ν ′
D (s) = R̂D(s, ν ′(s)) + ∑ s′∈S P̂D(s ′|s, ν′(s))V̂ ν ′ D (s ′) (14)
V ν∗DP DP (s) = RDP (s, ν ∗ DP (s)) + ∑ s′∈S PDP (s ′|s, ν∗DP (s))V ν∗DP DP ((s ′) (15)
Therefore, V̂ ν ′ D (s) = V ν∗DP DP (s),∀s ∈ S.
Then we have V̂ ν ′ D (s0) ≤ V̂ ν ∗ (s0) = V ν̂DP DP (s0) < V ν∗DP DP (s0) = V̂ ν′ D (s0) (16) which gives V̂ ν ′
D (s0) < V̂ ν′ D (s0), so there is a contradiction.
Combining the results of Proposition 24 and Lemma 21 , for a deterministic victim, the optimal policy in D-PAMDP gives an optimal adversary for the victim.

heading: D.3 OPTIMALITY OF HEURISTIC-BASED ATTACKS
text: There are many existing methods of finding adversarial state perturbations for a fixed RL policy, most of which are solving some optimization problems defined by heuristics. Although these methods are empirically shown to be effective in many environments, it is not clear how strong these adversaries are in general. In this section, we carefully summarize and categorize existing heuristic attack methods into 4 types, and then characterize their optimality in theory.
D.3.1 TYPE I - MINIMIZE THE BEST (MINBEST)
A common idea of evasion attacks in supervised learning is to reduce the probability that the learner selects the “correct answer” Goodfellow et al. (2015). Prior works Huang et al. (2017); Kos & Song (2017); Korkmaz (2020) apply a similar idea to craft adversarial attacks in RL, where the objective is to minimize the probability of selecting the “best” action, i.e.,
hMinBest ∈ argminh∈H πh(a +|s),∀s ∈ S (I)
where a+ is the “best” action to select at state s. Huang et al.Huang et al. (2017) define a+ as argmaxa∈AQ
π(s, a) for DQN, or argmaxa∈Aπ(a|s) for TRPO and A3C with a stochastic π. Since the agent’s policy π is usually well-trained in the original MDP, a+ can be viewed as (approximately) the action taken by an optimal deterministic policy π∗(s).
Lemma 25 (Optimality of MinBest). Denote the set of optimal solutions to objective (I) as HMinBest. There exist an MDP M and an agent policy π, such that HMinBest does not contain an optimal adversary h∗, i.e., HMinBest ∩H∗ = ∅.
Proof of Lemma 25. We prove this lemma by constructing the following MDP such that for any victim policy, there exists a reward configuration in which MinBest attacker is not optimal.
Here, let r1 = r(s4|s2, a1), r2 = r(s5|s2, a2), r3 = r(s3|s1, a2). Assuming all the other rewards are zero, transition dynamics are deterministic, and states s3, s4, s5 are the terminal states. For the
sake of simplicity, we also assume that the discount factor here γ = 1. Now given a policy π such that π(a1|s1) = β1 and π(a1|s2) = β2 (β1, β2 ∈ [0, 1]), we could find r1, r2, r3 such that the following constraints hold:
r1 > r2 ⇐⇒ Qπ(s1, a1) > Qπ(s1, a2) (17) β2r1 + (1− β2)r2 > r3 ⇐⇒ Qπ(s2, a1) > Qπ(s2, a2) (18)
r3 > (β2 − 2)r2 + (1− β2 + 2)r2 ⇐⇒ r3 > Qπ(s1, a1)− 2(r1 − r2) (19) Now we consider the Adv-policy-set
BH (π) = { π′ ∈ Π ∣∣∣ ‖π′(·|s1)− π(·|s1)‖ < 1, ‖π′(·|s2)− π(·|s2)‖ < 2}. Under these three linear constraints, the policy given by MinBest attacker satisfies that πhMinBest(a1|s1) = β1 − 1, and πhMinBest(a1|s2) = β2 − 2. On the other hand, we can find another admissible policy adversary πh∗(a1|s1) = β1 + 1, and πh∗(a1|s2) = β2 − 2. Now we show that V πh∗ (s1) < V πhMinBest (s1), and thus MinBest attacker is not optimal.
V πhMinBest (s1) = (β1 − 1) [ (β2 − 2)r1 + (1− β2 + 2)r2 ] + (1− β1 + 1)r3 (20)
= (β1 − 1)(β2 − 2)r1 + (β1 − 1)(1− β2 + 2)r2 + (1− β1 + 1)r3 (21) V πh∗ (s1) = (β1 + 1) [ (β2 − 2)r1 + (1− β2 + 2)r2 ] + (1− β1 − 1)r3 (22)
= (β1 + 1)(β2 − 2)r1 + (β1 + 1)(1− β2 + 2)r2 + (1− β1 − 1)r3 (23) Therefore,
V πh∗ (s1)− V πhMinBest (s1) = 2 1(β2 − 2)r2 + 2 1(1− β2 + 2)r2 − 2 1r3 (24)
= 2 1 [ (β2 − 2)r2 + (1− β2 + 2)r2 − r3 ] (25)
< 0 Because of the constraint (19) (26)
D.3.2 TYPE II - MAXIMIZE THE WORST (MAXWORST)
Pattanaik et al. (Pattanaik et al., 2018) point out that only preventing the agent from selecting the best action does not necessarily result in a low total reward. Instead, Pattanaik et al. (Pattanaik et al., 2018) propose another objective function which maximizes the probability of selecting the worst action, i.e.,
hMaxWorst ∈ argmaxh∈H πh(a −|s),∀s ∈ S (II)
where a− refers to the “worst” action at state s. Pattanaik et al.(Pattanaik et al., 2018) define the “worst” action as the actions with the lowest Q value, which could be ambiguous, since the Q function is policy-dependent. If a worst policy π− ∈ argminπV π(s),∀s ∈ S is available, one can use a− = argminQπ − (s, a). However, in practice, the attacker usually only has access to the agent’s current policy π, so it can also choose a− = argminQπ(s, a). Note that these two selections are different, as the agent’s policy π is usually far away from the worst policy.
Lemma 26 (Optimality of MaxWorst). Denote the set of optimal solutions to objective (II) as HMaxWorst, which include both versions of MaxWorst attacker formulations as we discussed above. Then there exist an MDP M and an agent policy π, such that HMaxWorst contains a non-optimal adversary h∗, i.e., HMaxWorst 6⊂ H∗ .

heading: Proof of Lemma 26.
text: Case I: Using current policy to compute the target action We prove this lemma by constructing the MDP in Figure 8 such that for any victim policy, there exists a reward configuration in which MaxWorst attacker is not optimal. Here, let r1 = r(s11|s1, a1), r2 = r(s12|s1, a2), r3 = r(s21|s2, a1), r4 = r(s22|s2, a2). Assuming all the other rewards are zero, transition dynamics are deterministic, and states s11, s12, s21, s22 are the terminal states. For the sake of simplicity, we also assume that the discount factor here γ = 1. Now given a policy π such that π(a1|s0) = β0, π(a1|s1) = β1, and π(a2|s2) = β2 (β0, β1, β2 ∈ [0, 1]), consider the Adv-policy-set
BH (π) = { π′ ∈ Π ∣∣∣ ‖π′(·|s1)−π(·|s1)‖ < 0, ‖π′(·|s1)−π(·|s1)‖ < 1, ‖π′(·|s2)−π(·|s2)‖ < 2,}.
We could find r1, r2, r3, r4 such that the following linear constraints hold: β1r1 + (1− β1)r2 >β2r3 + (1− β2)r4 ⇐⇒ Qπ(s0, a1) > Qπ(s0, a2) (27)
r1 >r2 ⇐⇒ Qπ(s1, a1) > Qπ(s1, a2) (28) r3 >r4 ⇐⇒ Qπ(s2, a1) > Qπ(s2, a2) (29)
(β1 − 1)r1 + (1− β1 + 1)r2 <(β2 − 2)r3 + (1− β2 + 2)r4 (30) Now, given these constraints, the perturbed policy given by MaxWorst attaker satisfies πhMaxWorst(a1|s0) = β0 − 0, πhMaxWorst(a1|s1) = β1 − 1, and πhMaxWorst(a1|s2) = β2 − 2. However, consider another perturbed policy πh∗ in Adv-policy-set such that πh∗(a1|s0) = β0 + 0, πh∗(a1|s1) = β1 − 1, and πh∗(a1|s2) = β2 − 2. We will prove that V πh∗ (s1) < V πhMaxWorst (s1), and thus MaxWorst attacker is not optimal. On the one hand,
V πhMaxWorst (s1) =(β0 − 0) [ (β1 − 1)r1 + (1− β1 + 1)r2 ] + (1− β0 + 0) [ (β2 − 2)r3 + (1− β2 + 2)r4 ] (31)
=(β0 − 0)(β1 − 1)r1 + (β0 − 0)(1− β1 + 1)r2 + (1− β0 + 0)(β2 − 2)r3 + (1− β0 + 0)(1− β2 + 2)r4 (32)
On the other hand, V πh∗ (s1) =(β0 + 0) [ (β1 − 1)r1 + (1− β1 + 1)r2 ] + (1− β0 − 0) [ (β2 − 2)r3 + (1− β2 + 2)r4 ] (33)
=(β0 + 0)(β1 − 1)r1 + (β0 + 0)(1− β1 + 1)r2 + (1− β0 − 0)(β2 − 2)r3 + (1− β0 − 0)(1− β2 + 2)r4 (34)
Therefore, V πh∗ (s1)− V πhMaxWorst (s1) =2 0(β1 − 1)r1 + 2 0(1− β1 + 1)r2
− 2 0(β2 − 2)r3 − 2 0(1− β2 + 2)r4 (35) < 0 Because of the constraint (30) (36)
Case II: Using worst policy to compute the target action
Same as before, we construct a MDP where HMaxWorst contains a non-optimal adversary. Let r1 = r(s1|s0, a1), r2 = r(s2|s0, a2), r3 = r(s3|s0, a3). Assuming all the other rewards are zero, transition dynamics are deterministic, and states s1, s2, s3 are the terminal states. For the sake of simplicity, we also assume that the discount factor here γ = 1. Let pi be the given policy such that π(a1|s0) = β1 and π(a2|s0) = β2. Now without loss of generality, we assume r1 > r2 > r3 (∗). Then the worst policy π′ satisfies that π′(a3|s0) = 1. Consider the Adv-policy-set BH (π) = { π′ ∈ Π
∣∣∣ ‖π′(·|s0) − π(·|s0)‖1 < }. Then HMaxWorst = {π′ ∈ Π ∣∣∣ π′(a3|s0) = (1− β1 − β2) + }.
Now consider two policies πh1 , πh2 ∈ HMaxWorst, where πh1(a1|s0) = β1, πh1(a2|s0) = β2 − , πh2(a1|s0) = β1 − , πh2(a2|s0) = β2. Then V πh1 (s0)− V πh2 (s0) = (r1 − r2) > 0. Therefore, πh1 ∈ HMaxWorst but it’s not optimal.
D.3.3 TYPE III - MINIMIZE Q VALUE (MINQ).
Another idea of attacking Pattanaik et al. (2018); Zhang et al. (2020a) is to craft perturbations such that the agent selects actions with minimized Q values at every step, i.e.,
hMinQ ∈ argminh∈H ∑
a∈A πh(a|s)Q̂π(s, a),∀s ∈ S (III)
where Q̂ is the approximated Q function of the agent’s original policy. For example, Pattanaik et al.Pattanaik et al. (2018) directly use the agent’s Q network (of policy π), while the Robust SARSA (RS) attack proposed by Zhang et al.Zhang et al. (2020a) learns a more stable Q network for the agent’s policy π. Note that in practice, this type of attack is usually applied to deterministic agents (e.g., DQN, DDPG, etc), then the objective becomes argminh∈H Q̂
π(s, πh(s)),∀s ∈ S Pattanaik et al. (2018); Zhang et al. (2020a); Oikarinen et al. (2020). In this case, the MinQ attack is equivalent to the MaxWorst attack with the current policy as the target.
Lemma 27 (Optimality of MinQ). Denote the set of optimal solutions to objective (III) as HMinQ, which include both versions of MinQ attacker formulations as we discussed above. Then there exist an MDP M and an agent policy π, such that HMinQ contains a non-optimal adversary h∗, i.e., HMinQ 6⊂ H∗ .

heading: Proof of Lemma 26.
text: Case I: For a deterministic victim In the deterministic case
hMinQ ∈ argminh∈H Q̂ π(s, πh(s)) = argmaxh∈H πh(argminaQ̂ π(s, a)|s),∀s ∈ S (IIID) In this case, the objective is equivalent to objective (II), thus Lemma 27 holds.
Case II: For a stochastic victim In this case, we consider the MDP in Figure 8 and condition (27) to (30). Then the MinQ objective gives πhMinQ(a1|s0) = β0 − 0, πhMinQ(a1|s1) = β1 − 1, and πhMinQ(a1|s2) = β2 − 2. According to the proof of the first case of Lemma 26, πhMinQ = πhMaxWorst is not an optimal adversary. Thus Lemma 27 holds.
D.3.4 TYPE IV - MAXIMIZE DIFFERENCE (MAXDIFF).
The MAD attack proposed by Zhang et al. (Zhang et al., 2020a) is to maximize the distance between the perturbed policy πh and the clean policy π, i.e., hMaxDiff ∈ argmaxh∈H DTV[πh(·|s)||π(·|s)],∀s ∈ S (IV) where TV denotes the total variance distance between two distributions. In practical implementations, the TV distance can be replaced by the KL-divergence, as DTV[πh(·|s)||π(·|s)] ≤ (DKL[πh(·|s)||π(·|s)])2. This type of attack is inspired by the fact that if two policies select actions with similar action distributions on all the states, then the value of the two policies is also small (see Theorem 5 in Zhang et al. (2020a)).
Lemma 28 (Optimality of MaxDiff). Denote the set of optimal solutions to objective (IV) as HMaxDiff. There exist an MDPM and an agent policy π, such that HMaxDiff contains a non-optimal adversary h∗, i.e., HMaxDiff 6⊂ H∗ .
Proof of Lemma 28. The proof follows from the proof of lemma 25. In the MDP we constructed, π′ = β1 − 1, πhMinBest(a1|s2) = β2 − 2 is one of the policies that has the maximum KL divergence from the victim policy within Adv-policy-set. However, as we proved in 25, this is not the optimally perturbed policy. Therefore, MaxDiff attacker may not be optimal.

heading: E ADDITIONAL EXPERIMENT DETAILS AND RESULTS
text: In this section, we provide details of our experimental settings and present additional experimental results. Section E.1 describes our implementation details and hyperparameter settings for Atari and MuJoCo experiments. Section E.2 provide additional experimental results, including experiments with varying budgets ( ) in Section E.2.1, more comparison between SA-RL and PA-AD in terms of convergence rate and sensitivity to hyperparameter settings as in Section E.2.3, robust training in MuJoCo games with fewer training steps in Section E.2.4, attacking performance on robust models in Atari games in Section E.2.5, as well as robust training results in Atari games in Section E.2.6.
E.1 IMPLEMENTATION DETAILS

heading: E.1.1 ATARI EXPERIMENTS
text: In this section we report the configurations and hyperparameters we use for DQN, A2C and ACKTR in Atari environments. We use GeForce RTX 2080 Ti GPUs for all the experiments.
DQN Victim We compare PA-AD algorithm with other attacking algorithms on 7 Atari games. For DQN, we take the softmax of the Q values Q(s, ·) as the victim policy π(·|s) as in prior works (Huang et al., 2017). For these environments, we use the wrappers provided by stablebaselines (Hill et al., 2018), where we clip the environment rewards to be −1 and 1 during training and stack the last 4 frames as the input observation to the DQN agent. For the victim agent, we implement Double Q learning (Hado Van Hasselt, 2016) and prioritized experience replay (Tom Schaul & Silver, 2016). The clean DQN agents are trained for 6 million frames, with a learning rate 0.00001 and the same network architecture and hyperparameters as the ones used in Mnih et al. (2015). In addition, we use a replay buffer of size 5 × 105. Prioritized replay buffer sampling is used with α = 0.6 and β increases from 0.4 to 1 linearly during training. During evaluation, we execute the agent’s policy without epsilon greedy exploration for 1000 episodes.
A2C Victim For the A2C victim agent, we also use the same preprocessing techniques and convolutional layers as the one used in Mnih et al. (2015). Besides, values and policy network share the same CNN layers and a fully-connected layer with 512 hidden units. The output layer is a categorical distribution over the discrete action space. We use 0.0007 as the initial learning rate and apply linear learning rate decay, and we train the victim A2C agent for 10 million frames. During evaluation, the A2C victim executes a stochastic policy (for every state, the action is sampled from the categorical distribution generated by the policy network). Our implementation of A2C is mostly based on an open-source implementation by Kostrikov Kostrikov (2018).
ACKTR Adversary To train the director of PA-AD and the adversary in SA-RL, we use ACKTR (Wu et al., 2017) with the same network architecture as A2C. We train the adversaries of PA-AD and SA-RL for the same number of steps for a fair comparison. For the DQN victim, we use a learning rate 0.0001 and train the adversaries for 5 million frames. For the A2C victim, we use a learning rate 0.0007 and train the adversaries for 10 million frames. Our implementation of ACKTR is mostly based on an open-source implementation by Kostrikov Kostrikov (2018).
Heuristic Attackers For the MinBest attacker, we following the algorithm proposed by Huang et al. (2017) which uses FGSM to compute adversarial state perturbations. The MinBest + Mo-
mentum attacker is implemented according to the algorithm proposed by Korkmaz (2020), and we set the number of iterations to be 10, the decaying factor µ to be 0.5 (we tested 0.01, 0.1, 0.5, 0.9 and found 0.5 is relatively better while the difference is minor). Our implementation of the MinQ attacker follows the gradient-based attack by Pattanaik et al. (2018), and we also set the number of iterations to be 10. For the MaxDiff attacker, we refer to Algorithm 3 in Zhang et al. (2020a) with the number of iterations equal to 10. In addition, we implement a random attacker which perturbs state s to s̃ = s + sign(µ), where µ is sampled from a standard multivariate Gaussian distribution with the same dimension as s.

heading: E.1.2 MUJOCO EXPERIMENTS
text: For four OpenAI Gym MuJoCo continuous control environments, we use PPO with the original fully connected (MLP) structure as the policy network to train the victim policy. For robustness evaluations, the victim and adversary are both trained using PPO with independent value and policy optimizers. We complete all the experiments on MuJoCo using 32GB Tesla V100.
PPO Victim We directly use the well-trained victim model provided by Zhang et al. (2020a).
PPO Adversary Our PA-AD adversary is trained by PPO and we use a grid search of a part of adversary hyperparameters (including learning rates of the adversary policy network and policy network, the entropy regularization parameter and the ratio clip for PPO) to train the adversary as powerful as possible. The reported optimal attack result is from the strongest adversary among all 50 trained adversaries.
Other Attackers For Robust Sarsa (RS) attack, we use the implementation and the optimal RS hyperparameters from Zhang et al. (2020a) to train the robust value function to attack the victim. The reported RS attack performance is the best one over the 30 trained robust value functions.
For MaxDiff attack, the maximal action difference attacker is implemented referring to Zhang et al. (2020a).
For SA-RL attacker, following Zhang et al. (2021), the hyperparameters is the same as the optimal hyperparameters of vanilla PPO from a grid search. And the training steps are set for different environments. For the strength of SA-PPO regularization κ, we choose from 1 × 10−6 to 1 and report the worst-case reward.
Robust Training For ATLA Zhang et al. (2021), the hyperparameters for both victim policy and adversary remain the same as those in vanilla PPO training. To ensure sufficient exploration, we run a small-scale grid search for the entropy bonus coefficient for agent and adversary. The experiment results show that a larger entropy bonus coefficient allows the agent to learn a better policy for the continual-improving adversary. In robust training experiments, we use larger training steps in all the MuJoCo environments to guarantee policy convergence. We train 5 million steps in Hopper, Walker, and HalfCheetah environments and 10 million steps for Ant. For reproducibility, the final results we reported are the experimental performance of the agent with medium robustness from 21 agents training with the same hyperparameter set.

heading: E.2 ADDITIONAL EXPERIMENT RESULTS

heading: E.2.1 ATTACKING PERFORMANCE WITH VARIOUS BUDGETS
text: In Table 1, we report the performance of our PA-AD attacker under a chosen epsilon across different environments. To see how PA-AD algorithm performs across different values of ’s, here we select three Atari environments each for DQN and A2C victim agents and plot the performance of PA-AD under various ’s compared with the baseline attackers in Figure 10. We can see from the figures that our PA-AD universally outperforms baseline attackers concerning various ’s.
In Table 2, we provide the evaluation results of PA-AD under a commonly unused epsilon in four MuJoCo experiments (Zhang et al. (2020a; 2021)) to show that PA-AD attacker also has the best attacking performance compared with other attackers under different ’s in Figure 11.

heading: E.2.2 HYPERPARAMETER TEST
text: In our Actor-Director Framework, solving an optimal actor is a constraint optimization problem. Thus, in our algorithm, we instead use Lagrangian relaxation for the actor’s constraint optimization. In this section, we report the effects of different choices of the relaxation hyperparameter λ on the final performance of our algorithm. Although we set λ by default to be 1 and keep it fixed throughout all of the other experiments, here we find that in fact, difference choice of λ has only minor impact on the performance of the attacker. This result demonstrates that our PA-AD algorithm is robust to different choices of relaxation hyperparameters.

heading: E.2.3 EMPIRICAL COMPARISON BETWEEN PA-AD AND SA-RL
text: In this section, we provide more empirical comparison between PA-AD and SA-RL. Note that PAAD and SA-RL are different in terms of their applicable scenarios: SA-RL is a black-box attack methods, while PA-AD is a white-box attack method. When the victim model is known, we can see that by a proper exploitation of the victim model, PA-AD demonstrates better attack performance, higher sample and computational efficiency, as well as higher scalability. Appendix F.2 shows detailed theoretical comparison between SA-RL and PA-AD.
PA-AD has better convergence property than SA-RL. In Figure 12, we plot the learning curves of SA-RL and PA-AD in the CartPole environment and the Ant environment. Compared with SARL attacker, PA-AD has a higher attacking strength in the beginning and converges much faster. In Figure 12b, we can see that PA-AD has a “warm-start” (the initial reward of the victim is already significantly reduced) compared with SA-RL attacker which starts from scratch. This is because PA-AD always tries to maximize the distance between the perturbed policy and the original victim policy in every step according to the actor function (G). So in the beginning of learning, PA-AD works similarly to the MaxDiff attacker, while SA-RL works similarly to a random attacker. We also note that although PA-AD algorithm is proposed particularly for environments that have state spaces much larger than action spaces, in CartPole where the state dimensions is fewer than the number of actions, PA-AD still works better than SA-RL because of the distance maximization.
PA-AD is more computationally efficient than SA-RL. Our experiments in Section 6 show that PA-AD converges to a better adversary than SA-RL given the same number of training steps, which verifies the sample efficiency of PA-AD. Another aspect of efficiency is based on the computational resources, including running time and required memory. For RL algorithms, the computation cost comes from the interaction with the environment (the same for SA-RL and PA-AD) and the policy/value update. If the state space S is higher-dimensional than the action space A, then SA-RL requires a larger policy network than PA-AD since SA-RL has a higher-dimensional output, and thus SA-RL has more network parameters than PA-AD, which require more memory cost and more computation operations. On the other hand, PA-AD requires to solve an additional optimization problem defined by the actor objective (G) or (GD). In our implementation, we use FGSM which only requires one-step gradient computation and is thus efficient. But if more advanced optimization algorithms (e.g. PGD) are used, more computations may be needed. In summary, if S is much larger than A, PA-AD is more computational efficient than SA-RL; if A is much larger than S, SARL is more efficient than PA-AD; if the sizes of S and A are similar, PA-AD may be slightly more expensive than SA-RL, depending on the optimization methods selected for the actor.
To verify the above analysis, we compare computational training time for training SA-RL and PAAD attackers, which shows that PA-AD is more computationally efficient. Especially on the environment with high-dimensional states like Ant, PA-AD takes significantly less training time than SA-RL (and finds a better adversary than SA-RL), which quantifies the efficiency of our algorithm in empirical experiments.
PA-AD is less sensitive to hyperparameters settings than SA-RL. In addition to better final attacking results and convergence property, we also observe that PA-AD is much less sensitive to hyerparameter settings compared to SA-RL. On the Walker environment, we run a grid search over 216 different configurations of hyperparameters, including actor learning rate, critic learning rate, entropy regularization coefficient, and clipping threshold in PPO. Here for comparison we plot two histograms of the agent’s final attacked results across different hyperparameter configurations.
The perturbation radius is set to be 0.05, for which the mean reward reported by Zhang et al. (2020a) is 1086. However, as we can see from this histogram, only one out of the 216 configurations of SARL achieves an attacking reward within the range 1000-2000, while in most hyperparameter settings, the mean attacked return lies in the range 4000-4500. In contrast, about 10% hyperparameter settings
of PA-AD algorithm are able to reduce the reward to 500-1000, and another 10% settings could reduce the reward to 1000-2000. Therefore, the performance of PA-AD attacker is generally better and more robust across different hyperparameter configurations than SA-RL.

heading: E.2.4 ROBUST TRAINING EFFICIENCY ON MUJOCO BY PA-ATLA
text: In the ATLA process proposed by Zhang et al. (2021), one alternately trains an agent and an adversary. As a result, the agent policy may learn to adapt to the specific type of attacker it encounters during training. In Table 3, we present the performance of our robust training method PA-ATLAPPO compared with ATLA-PPO under different types of attacks during testing. ATLA-PPO uses SA-RL to train the adversary, while PA-ATLA-PPO uses PA-AD to train the adversary during alternating training. As a result, we can see that ATLA-PPO models perform better under the SA-RL attack, and PA-ATLA-PPO performs better under the PA-AD attack. However, the advantage of ATLA-PPO over PA-ATLA-PPO against SA-RL attack is much smaller than the advantage of PAATLA-PPO over ATLA-PPO against PA-AD attack. In addition, our PA-ATLA-PPO models significantly outperform ATLA-PPO models against other heuristic attack methods, and achieve higher average rewards across all attack methods. Therefore, PA-ATLA-PPO is generally more robust than ATLA-PPO.
Furthermore, the efficiency of training an adversary could be the bottleneck in the ATLA Zhang et al. (2021) process for practical usage. Appendix E.2.3 suggests that our PA-AD generally converges faster than SA-RL. Therefore, when the computation resources are limited, PA-ATLA-PPO can train robust agents faster than ATLA-PPO. We conduct experiments on continuous control environments to empirically show the efficiency comparison between PA-ATLA-PPO and ATLA-PPO. In Table 6, we show the robustness performance of two ATLA methods with 2 million training steps for Hopper, Walker and Halfcheetah and 5 million steps for Ant (Compared with results in Table 3, we have reduced training steps by half or more). It can be seen that our PA-ATLA-PPO models still significantly outperform the original ATLA-PPO models under different types of attacks. More importantly, our PA-ATLA-PPO achieves higher robustness under SA-RL attacks in Walker and Ant, suggesting the efficiency and effectiveness of our method.
row. The gray cells are the most robust agents with the highest average rewards across all attacks.

heading: E.2.5 ATTACKING ROBUSTLY TRAINED AGENTS ON ATARI
text: In this section, we show the attack performance of our proposed algorithm PA-AD against DRL agents that are trained to be robust by prior works (Zhang et al., 2020a; Oikarinen et al., 2020) in Atari games.
Zhang et al. (2020a) propose SA-DQN, which minimizes the action change under possible state perturbations within `p norm ball, i.e., to minimize the extra loss
RDQN(θ) := ∑ s max { max ŝ∈B(s) max a6=a∗ Qθ(ŝ, a)−Qθ (ŝ, a∗(s)) ,−c }
(37)
where θ refers to the Q network parameters, a∗(s) = argmaxaQθ(a|s), and c is a small constant. Zhang et al. (2020a) solve the above optimization problem by a convex relaxation of the Q network, which achieves 100% action certification (i.e. the rate that action changes with a constrained state perturbation) in Pong and Freeway, over 98% certification in BankHeist and over 47% certification in RoadRunner under attack budget = 1/255.
Oikarinen et al. (2020) propose another robust training method named RADIAL-RL. By adding a adversarial loss to the classical loss of the RL agents, and solving the adversarial loss with interval bound propagation, the proposed RADIAL-DQN and RADIAL-A3C achieve high rewards in Pong, Freeway, BankHeist and RoadRunner under attack budget = 1/255 and = 3/255.
Implementation of the Robust Agents and Environments. We directly use the trained SA-DQN agents provided by Zhang et al. (2020a), as well as RADIAL-DQN and RADIAL-A3C agents provided by Oikarinen et al. (2020). During test time, the agents take actions deterministically. In order to reproduce the results in these papers, we use the same environment configurations as in Zhang et al. (2020a) and Oikarinen et al. (2020), respectively. But note that the environment configurations of SA-DQN and RADIAL-RL are simpler versions of the traditional Atari configurations we use (described in Appendix E.1.1). Both SA-DQN and RADIAL-RL use a single frame instead of the stacking as 4 frames. Moreover, SA-DQN restricts the number of actions as 6 (4 for Pong) in each environment, although the original environments have 18 actions (6 for Pong). The above simplifications in environments can make robust training easier since the dimensionality of the input space is much smaller, and the number of possible outputs is restricted.
Attack Methods In experiments, we find that the robust agents are much harder to attack than vanilla agents in Atari games, as claimed by the robust training papers (Zhang et al., 2020a; Oikarinen et al., 2020). A reason is that Atari games have discrete action spaces, and leading an agent to make a different decision at a state with a limited perturbation could be difficult. Therefore, we use a 30-step Projected Gradient Descent for all attack methods (with step size /10), including MinBest (Huang et al., 2017) and our PA-AD which use FGSM for attacking vanilla models. Note that the PGD attacks used by Zhang et al. (2020a) and Oikarinen et al. (2020) in their experiments are the same as the MinBest-PGD attack we use. For our PA-AD, we use PPO to train the adversary since PPO is relatively stable. The learning rate is set to be 5e − 4, and the clip threshold is 0.1. Note that SA-DQN, RADIAL-DQN and RADIAL-A3C agents all take deterministic actions, so we use the deterministic formulation of PA-AD as described in Appendix C.1. In our implementation, we simply use a CrossEntropy loss for the actor as in Equation (38).
gD(â, s) = argmins′∈B (s)CrossEntropy(π(s ′), â). (38)
Experiment Results In Table 7, we reproduce the results reported by Zhang et al. (2020a) and Oikarinen et al. (2020), and demonstrate the average rewards gained by these robust agents under different attacks in RoadRunner and BankHeist. Note that SA-DQN is claimed to be robust to attacks with budget = 1/255, and RADIAL-DQN and RADIAL-A3C are claimed to be relatively robust against up to = 3/255 attacks. (`∞ is used in both papers.) So we use the same ’s for these agents in our experiments.
It can be seen that compared with vanilla agents in Table 1, SA-DQN, RADIAL-DQN and RADIALA3C are more robust due to the robust training processes. However, in some environments, PA-AD can still decrease the rewards of the agent significantly. For example, in RoadRunner with =
3/255, RADIAL-DQN gets 1k+ reward against our PA-AD attack, although RADIAL-DQN under other attacks can get 10k+ reward as reported by Oikarinen et al. (2020). In contrast, we find that RADIAL-A3C is relatively robust, although the natural rewards gained by RADIAL-A3C are not as high as RADIAL-DQN and SA-DQN. Also, as SA-DQN achieves over 98% action certification in BankHeist, none of the attackers is able to noticeably reduce its reward with = 1/255.
Therefore, our PA-AD can approximately evaluate the worst-case performance of an RL agent under attacks with fixed constraints, i.e., PA-AD can serve as a “detector” for the robustness of RL agents. For agents that perform well under other attacks, PA-AD may still find flaws in the models and decrease their rewards; for agents that achieve high performance under PA-AD attack, they are very likely to be robust against other attack methods.
E.2.6 IMPROVING ROBUSTNESS ON ATARI BY PA-ATLA
Note that different from SA-DQN (Zhang et al., 2020a) and RADIAL-RL (Oikarinen et al., 2020) discussed in Appendix E.2.5, we use the traditional Atari configurations (Mnih et al., 2015) without any simplification (e.g. disabling frame stacking, or restricting action numbers). We aim to improve the robustness of the agents in original Atari environments, as in real-world applications, the environments could be complex and unchangeable.
Baselines We propose PA-ATLA-A2C by combining our PA-AD and the ATLA framework proposed by Zhang et al. (2021). We implement baselines including vanilla A2C, adversarially trained A2C (with MinBest (Huang et al., 2017) and MaxDiff (Zhang et al., 2020a) adversaries attacking 50 frames). SA-A2C (Zhang et al., 2020a) is implemented using SGLD and convex relaxations in Atari environments.
In Table 6, naive adversarial training methods have unreliable performance under most strong attacks and SA-A2C is ineffective under PA-AD strongest attack. To provide evaluation using different , we provide the attack rewards of all robust models with different attack budgets . Under all attacks with different value, PA-ATLA-A2C models outperform all other robust models and achieve consistently better average rewards across attacks. We can observe that our PA-ATLA-A2C training method can considerably enhance the robustness in Atari environments.
BankHeist. In each row, we bold the strongest attack. The gray cells are the most robust agents with the highest average rewards across all attacks.

heading: F ADDITIONAL DISCUSSION OF OUR ALGORITHM

heading: F.1 OPTIMALITY OF OUR RELAXED OBJECTIVE FOR STOCHASTIC VICTIMS

heading: Proof of Concept: Optimality Evaluation in A Small MDP
text: We implemented and tested heuristic attacks and our PA-AD in the example 2-state MDP used in Figure 6, and visualize the results in Figure 14. For simplicity, assume the adversaries can perturb only perturb π at s1 within a `2 norm ball of radius 0.2. And we let all adversaries perturb the policy directly based on their objective functions. As shown in Figure 14a, all possible π̃(s1)’s form a disk in the policy simplex, and executing above methods, as well as our PA-AD, leads to 4 different policies on this disk. All these computed policy perturbations are on the boundary of the policy perturbation ball, justifying our Theorem 4.
As our theoretical results suggest, the resulted value vectors lie on a line segment shown in Figure 14b and a zoomed in version Figure 14c, where one can see that MinBest, MaxWorst and MAD all fail to find the optimal adversary (the policy with lowest value). On the contrary, our PA-AD finds the optimal adversary that achieves the lowest reward over all policy perturbations.

heading: For Continuous MDP: Optimality Evaluation in CartPole and MountainCar
text: We provided a comparison between SA-RL and PA-AD in the CartPole environment in Figure 15, where we can see the SA-RL and PA-AD converge to the same result (the learned SA-RL adversary and PA-AD adversary have the same attacking performance).
CartPole has a 4-dimensional state space, and contains 2 discrete actions. Therefore since SA-RL has an optimal formulation, we expect SA-RL to converge to the optimal adversary in a small MDP like CartPole. Then the result in Figure 15 suggests that our PA-AD algorithm, although with a relaxation in the actor optimization, also converges to the optimal adversary with even a faster rate than SA-RL (the reason is explained in Appendix E.2.3).
In addition to CartPole, we also run experiments in MountainCar with a 2-dimensional state space against a DQN victim. The SA-RL attacker reduces the victim reward to -128, and our PA-AD attacker reduces the victim reward to -199.45 within the same number of training steps. Note that the lowest reward in MountainCar is -200, so our PA-AD indeed converges to a near-optimal adversary, while SA-RL fails to converge to a near-optimal adversary. This is because MountainCar is an environment with relatively spare rewards. The actor in PA-AD utilizes our Theorem 4 and only focuses on perturbations in the outermost boundary, which greatly reduces the exploration burden in solving an RL problem. In contrast, SA-RL directly uses RL algorithms to learn the perturbation, and thus it has difficulties in converging to the optimal solution.

heading: F.2 MORE COMPARISON BETWEEN SA-RL AND PA-AD
text: We provide a more detailed comparison between SA-RL and PA-AD from the following multiple aspects to claim our contribution.

heading: 1. Size of the Adversary MDP
text: Suppose the original MDP has size |S|, |A| for its state space and action space, respectively. Both PA-AD and SA-RL construct an adversary’s MDP and search for the optimal policy in it. But the adversary’s MDPs for PA-AD and SA-RL have different sizes.
PA-AD: state space is of size |S|, action space is of size R|A|−1 for a stochastic victim, or |A| for a deterministic victim. SA-RL: state space is of size |S|, action space is of size |S|.

heading: 2. Learning Complexity and Efficiency
text: When the state space is larger than the action space, which is very common in RL environments, PAAD solves a smaller MDP than SA-RL and thus more efficient. In environments with pixel-based states, SA-RL becomes computationally intractable, while PA-AD still works. It is also important to note that the actor’s argmax problem in PA-AD further accelerates the convergence, as it rules out the perturbations that do not push the victim policy to its outermost boundary. Our experiment and analysis in Appendix E.2.3 verify the efficiency advantage of our PA-AD compared with SA-RL, even in environments with small state spaces.

heading: 3. Optimality
text: PA-AD: (1) the formulation is optimal for a deterministic victim policy; (2) for a stochastic victim policy, the original formulation is optimal, but in practical implementations, a relaxation is used which may not have optimality guarantees. SA-RL: the formulation is optimal. Note that both SA-RL and PA-AD require training an RL attacker, but the RL optimization process may not converge to the optimal solution, especially in deep RL domains. Therefore, SA-RL and PA-AD are both approximating the optimal adversary in practical implementations.

heading: 4. Knowledge of the Victim
text: PA-AD: needs to know the victim policy (white-box). Note that in a black-box setting, PA-AD can still be used based on the transferability of adversarial attacks in RL agents, as verified by Huang et al. (2017). But the optimality guarantee of PA-AD does not hold in the black-box setting. SA-RL: does not need to know the victim policy (black-box). It should be noted that the white-box setting is realistic and helps in robust training: (1) The white-box assumption is common in existing heuristic methods. (2) It is always a white-box process to evaluate and improve the robustness of a given agent, for which PA-AD is the SOTA method. As discussed in our Ethics Statement, the ultimate goal of finding the strongest attacker is to better understand and improve the robustness of RL agents. During the robust training process, the victim is the main actor one wants to train, so it is a white-box setting. The prior robust training art ATLA (Zhang et al., 2021) uses the black-box attacker SA-RL, despite the fact that it has white-box access to the victim actor. Since SA-RL does not utilize the knowledge of the victim policy, it usually has to deal with a more complex MDP and face converging difficulties. In contrast, if one replaces SA-RL with our PA-AD, PA-AD can make good use of the victim policy and find a stronger attacker with the same training steps as SA-RL, as verified in our Section 6 and Appendix E.2.6.

heading: 5. Applicable Scenarios
text: SA-RL is a good choice if (1) the action space is much larger than the state space in the original MDP, or the state space is small and discrete; (2) the attacker wants to conduct black-box attacks. PA-AD is a good choice if (1) the state space is much larger than the state space in the original MDP; (2) the victim policy is known to the attacker; (3) the goal is to improve the robustness of one’s own agent via adversarial training.
In summary, as we discussed in Section 4, there is a trade-off between efficiency and optimality in evasion attacks in RL. SA-RL has an optimal RL formulation, but empirical results show that SA-RL usually do not converge to the optimal adversary in a continuous state space, even in a lowdimensional state space (e.g. see Appendix F.1 for an experiment in MountainCar). Therefore, the difficulty of solving an adversary’s MDP is the bottleneck for finding the optimal adversary. Our PA-AD, although may sacrifice the theoretical optimality in some cases, greatly reduces the size and the exploration burden of the attacker’s RL problem (can also be regarded as trading some estimation bias off for lower variance). Empirical evaluation shows our PA-AD significantly outperforms SARL in a wide range of environments.
Though PA-AD requires to have access to the victim policy, PA-AD solves a smaller-sized RL problem than SA-RL by utilizing the victim’s policy and can be applied on evaluating/improving the robustness of RL policy. It is possible to let PA-AD work in a black-box setting based on the transferability of adversarial attacks. For example, in a black-box setting, the attacker can train a proxy agent in the same environment, and use PA-AD to compute a state perturbation for the proxy agent, then apply the state perturbation to attack the real victim agent. This is out of the scope of this paper, and will be a part of our future work.
F.3 VULNERABILITY OF RL AGENTS
It is commonly known that neural networks are vulnerable to adversarial attacks (Goodfellow et al., 2015). Therefore, it is natural that deep RL policies, which are modeled by neural networks, are also vulnerable to adversarial attacks (Huang et al., 2017). However, there are few works discussing the difference between deep supervised classifiers and DRL policies in terms of their vulnerabilities. In this section, we take a step further and investigate the vulnerability of DRL agents, through a comparison with standard adversarial attacks on supervised classifiers. Our main conclusion is that commonly used deep RL policies can be instrinsically much more vulnerable to small-radius adversarial attacks. The reasons are explained below.

heading: 1. Optimization process
text: Due to the different loss functions that RL and supervised learning agents are trained on, the size of robustness radius of an RL policy is much smaller than that of a vision-based classifier. On the one hand, computer vision-based image classifiers are trained with cross-entropy loss. Therefore, the classifier is encouraged to make the output logit of the correct label to be larger than the logits of other labels to maximize the log probability of choosing the correct label. On the other hand, RL agents, in particular DQN agents, are trained to minimize the Bellman Error instead. Thus the agent is not encouraged to maximize the absolute difference between the values of different actions. Therefore, if we assume the two networks are lipschitz continuous and their lipschitz constants do not differ too much, it is clear that a supervised learning agent has a much larger perturbation radius than an RL agent.
To prove our claim empirically, we carried out a simple experiment, we compare the success rate of target attacks of a well-trained DQN agent on Pong with an image classifier trained on the CIFAR-10 dataset with similar network architecture. For a fair comparison, we use the same image preprocessing technique, which is to divide the pixel values by 255 and no further normalization is applied. On both the image-classifier and DQN model, we randomly sample a target label other than the model predicted label and run the same 100-step projected gradient descent (PGD) attack to minimize the cross-entropy loss between the model output and the predicted label. We observe that for a perturbation radius of 0.005 (l∞ norm), the success rate of a targeted attack for the image classifier is only 15%, whereas the success rate of a targeted attack for the DQN model is 100%. This verifies our claim that a common RL policy is much more vulnerable to small-radius adversarial attacks than image classifiers.

heading: 2. Network Complexity
text: In addition, we also want to point out that the restricted network complexity of those commonly used deep RL policies could play an important role here. Based on the claim by Madry et al. (2018), a neural network with greater capacity could have much better robustness, even when trained with only clean examples. But for the neural network architectures commonly used in RL applications, the capacity of the networks is very limited compared to SOTA computer vision applications. For example, the commonly used DQN architecture proposed in Mnih et al. (2015) only has 3 convolutional layers and 2 fully connected layers. But in vision tasks, a more advanced and deeper structure (e.g. ResNet has 100 layers) is used. Therefore, it is natural that the perturbation radius need for attacking an RL agent is much smaller than the common radius studied in the supervised evasion attack and adversarial learning literature.

Review summaries:
The paper proposes a method for computing the strongest adversarial perturbation on state observations of an RL agent from a specified set of perturbations. It relates perturbations on states to perturbations on policies. It poses a specific problem to this end, develops a solution, and establishes its optimality. 

The paper studies evasion attacks in deep reinforcement learning (RL). More specifically, the paper considers a novel approach to performing evasion attacks based on two-component design --- director and actor modules, where the latter perturbs a given state based on the policy direction that the former specifies. Effectively, the search for an optimal attack is performed in the policy space, and since the policy space is typically more compact than the state space, the search is more efficient. The paper formally justifies its design choices, and experimentally validates the efficacy of the propose approach, showing that it yields significant improvements compared to the state-of-the-art methods.  

The paper introduces a novel algorithm to find the optimal evasion attack against RL in scenarios where the agent's policy is known. The key idea is to only learn the aspect of problem depending on the environment and is unknown through a clever decomposition. The algorithm shows promising empirical results.

The paper proposes a method to craft stronger and more efficient attacks on state observation of the RL agent.  Here, the 'strongest' attacks refer to the attacks that minimize the reward the most. An 'efficient' attacker can craft such attacks using the least computational resources. In the work of (Zhang et al., 2021), the attacking strategy is described by a mapping from the state space of the underlying MDP problem to the same space. The agent observes the falsified states rather than the actual ones and takes actions based on the observed states. This misinformation eventually tricks the agent into taking a different action. In this paper, the authors argue that instead of finding the mapping from the state space to the same space, the attacker can first find the mapping from the state space to the action space that generates the least accumulated rewards to the agent. The 'strongest' attacks on the state observation can then be crafted based on the mapping found. Since in many deep RL applications, the state space is much larger than the action space. Hence, finding the mapping from the state space to the action space is more efficient than finding the one from the state space to the state space.