Year: 2019

Abstract:
Deep reinforcement learning agents are known to be vulnerable to adversarial attacks. In particular, recent studies have shown that attacking a few key steps is effective for decreasing the agent’s cumulative reward. However, all existing attacking methods find those key steps with human-designed heuristics, and it is not clear how more effective key steps can be identified. This paper introduces a novel reinforcement learning framework that learns key steps through interacting with the agent. The proposed framework does not require any human heuristics nor knowledge, and can be flexibly coupled with any white-box or black-box adversarial attack scenarios. Experiments on benchmark Atari games across different scenarios demonstrate that the proposed framework is comparable and could be superior to existing methods for learning key steps.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) is a framework for sequential decision problems, where an agent interacts with an unknown environment and tries to maximize the total reward it receives. With the rapid development of deep learning, RL agents parametrized by neural networks, usually referred to as deep RL agents, are able to learn complex policies from raw inputs (Mnih et al., 2015). Recently, deep RL agents have shown great success across various domains, such as achieving superhuman performance on games (Mnih et al., 2015; Silver et al., 2016; 2018), completing complex robotic tasks (Levine et al., 2016), optimizing patient treatments (Escandell-Montero et al., 2014; Raghu et al., 2017), and developing autonomous driving skills (Pan et al., 2017; Isele et al., 2018).
However, if we wish to deploy these RL agents into security-critical applications, we must take their reliability into consideration. It is discovered that neural network classifiers may make errors on deliberately crafted inputs, known as adversarial examples (Biggio et al., 2013; Szegedy et al., 2013; Behzadan & Munir, 2017a). Deep RL is no exception: Many works have demonstrated that deep RL agents are also vulnerable when attacked by adversarial examples (Behzadan & Munir, 2017a; Huang et al., 2017), raising serious concerns on the reliability of these agents for security-critical applications. For example, there may be severe consequences if an RL-agent-driven autonomous vehicle is compromised by adversarial examples fed from a malicious attacker.
Given the sequential nature of RL, it is not necessary to attack at every time step to degrade the agent’s performance significantly (Lin et al., 2017; Kos & Song, 2017). The reason is that not all decisions made by the agent are equally important. Some decisions may be critical to the agent, such as those for long-term planning or immediate reward gathering; some other decisions may not have much effect on the environment nor the rewards, and thus attacking those steps would not affects the agent’s performance. The critical steps will be named key steps in this work, and attacking these steps decreases the cumulative reward that the agent could gather.
Figure 1 illustrates a key step and a non-key step in Atari Pong, where the main difference between them is whether the ball has already passed through the agent. If the attacker is aware of this difference, the attacker can concentrate on attacking the key steps. By attacking fewer steps, the attacker reduces the costs of generating, injecting, and hiding the adversarial examples. Therefore, an intelligent attacker should prefer attacking key steps over non-key steps.
A natural question arises: How does an attacker identify the key steps to attack? As an initial attempt to address this question, Lin et al. (2017) formulate the problem from an optimization perspective,
and propose a heuristic that attacks the agent when it strongly prefers one action. Concurrently, Kos & Song (2017) propose another heuristic that attacks when the action appears rewarding to the agent. However, since these heuristics are designed based on human knowledge, it is unclear whether there exist more effective key steps. In this work, we study the possibilities of finding more effective key steps, and of finding them automatically without human knowledge. We confirm both possibilities by introducing an RL framework where the attacker learns the key steps from scratch through interacting with the agent.
In particular, we study the key-step identification problem proposed by Lin et al. (2017). We first make a crucial observation that this constrained optimization problem can be converted into another form that matches the objective of RL. Then, we design a corresponding RL environment to train the attacker. Our contributions are summarized as follows:
• We formulate the key-step identification problem in an unconstrained form, and introduce an RL framework that solves it directly without incorporating human knowledge. The proposed RL framework is independent of how adversarial examples are generated, and thus could be combined with white-box or black-box attacks.
• We justify our learning framework by giving a toy example where those human-designed heuristics fail to identify the key steps.
• To test the effectiveness of our framework, we conduct experiments on four benchmark Atari games. The results suggest that the attacker trained by our framework learns effective key steps and has the potential to outperform prior methods.

heading: 2 BACKGROUND AND RELATED WORK

heading: 2.1 REINFORCEMENT LEARNING BACKGROUND
text: We begin with an introduction to the Markov Decision Process (MDP) (Sutton & Barto, 2018). For a set S, we use ∆(S) to denote the set of probability distributions over S. Consider an agent interacting with an environment: At each step t, the agent picks an action at based on a current state st, and then the environment returns a reward rt and a next state st+1. We formalize this interaction as an MDP M, which is a 5-tuple (S,A, P,R, γ), where S is a finite set of states, A is a finite set of actions, P : S × A → ∆(S) defines the transition dynamics from st to st+1, R : S × A → ∆(R) defines the reward distribution, and γ ∈ [0, 1] is a discount factor. For convenience, we use r : (st, at) 7→ Ert∼R(st,at)[rt] to denote the mean reward function. We specify an agent by its (stochastic) policy π : S→ ∆(A), and define its Q-value function as
Qπ(st, at) = E [ ∞∑ k=0 γkr(st+k, at+k) ] ,
where si ∼ P (si−1, ai−1) and ai ∼ π(si) for all i > t. The agent’s goal is to find a policy that maximizes the expected cumulative reward, or expected return, defined by Qπ(s1, π(s1)), starting from an initial state s1. For finite-horizontal MDPs, we use T to denote the maximum number of steps, and define an episode to be a sample of (s1, a1, r1, . . . , sT , aT , rT , sT+1).
To learn the optimal policy, deep Q-network (DQN, Mnih et al. 2015) first approximates the Q-value function by a neural network that takes a state as input and outputs the Q-values for all actions. The policy is then induced by picking the action with the largest Q-value at each state. Given a transition step (st, at, rt, st+1), the network fθ is trained by minimizing the square loss
Lθ = (( rt + γmax
a fθ(st+1)a
) − fθ(st)at )2 ,
where we use fθ(s)a to denote the a-th entry of the Q-values fθ(s).

heading: 2.2 ADVERSARIAL ATTACK BACKGROUND
text: In the context of adversarial attacks, an attacker tries to craft adversarial examples that the target model would misclassify. In gradient-based adversarial attacks, the attacker generates adversarial examples by adding small perturbations to data examples, such that the perturbations are imperceptible to human eyes. Take the fast gradient sign method (FGSM) by Goodfellow et al. (2014) for example. Given a target model fθ parametrized by θ and an image–label pair (x, y), the FGSM computes the perturbation as η = sign(∇xJ(θ, x, y)), where is a scaling factor that controls the norm of the perturbation, and J(θ, x, y) is an objective function that depends on the attacker’s goal. In untargetted attacks, the attacker aims to minimize the target model’s classification accuracy. Thus, the objective J(θ, x, y) is substituted with DKL(e
(y)‖fθ(x)), the Kullback-Leibler divergence between the label’s one-hot encoding e(y) and the predicted probabilities fθ(x). However, this type of white-box attacks requires full knowledge of the network parameter θ, which may be hidden in practical tasks.
In contrast, black-box attacks assume no access to θ and study other conditions, such as the ability to query model outputs (Chen et al., 2017). One black-box attack of particular interest is the substitute model approach (Papernot et al., 2016a; 2017), where the attacker computes perturbation using a substitute model that is trained to perform the same task as the target model. This approach is based on the finding that adversarial examples are transferable; that is, if an adversarial example fools a model, it usually fools another models trained to perform the same task, regardless of the network architecture (Szegedy et al., 2013). Consequently, once the attacker gains access to the training set, black-box attacks reduce to white-box attacks with a lower attack success rate.

heading: 2.3 ADVERSARIAL ATTACK ON DEEP RL AGENTS
text: As opposed to traditional adversarial attacks, attacking an RL agent is a unique and challenging task. When we attack a classifier, we typically aim to minimize the classification accuracy or to maximize the probability that the classifier predicts some given class. When we attack an RL agent, however, we usually do not care about the individual actions that the agent picks. In this paper, we choose to minimize the agent’s cumulative reward (Huang et al., 2017; Lin et al., 2017) as the attacker’s goal. Other possible goals include luring the agent into a designated state (Lin et al., 2017), or misguiding the agent to optimize an adversarial reward (Tretschk et al., 2018).
Previous works have investigated the effects of white-box and black-box attacks against RL agents on the Atari benchmark. Given full knowledge of the target agent’s network parameters, an attacker can craft adversarial examples to fool the target agent into picking wrong actions (Behzadan & Munir, 2017a; Huang et al., 2017; Kos & Song, 2017; Mandlekar et al., 2017; Pattanaik et al., 2018; Hussenot et al., 2019) using the FGSM. Other white-box methods such as the Jacobian saliency map algorithm (Papernot et al., 2016b) and the attack proposed by Carlini & Wagner (2017) are also effective against RL agents (Behzadan & Munir, 2017a; Lin et al., 2017). Even if the attacker cannot access the target agent’s network parameters, adversarial examples can still be crafted with a substitute agent that is trained in the same environment as the target agent (Behzadan & Munir, 2017a; Huang et al., 2017), similar to the substitute model approach.
Another line of studies tries to improve the RL agent’s robustness with adversarial attacks. Several works improve the agent’s robustness to visual perturbations through adversarial training (Kos & Song, 2017; Mandlekar et al., 2017; Behzadan & Munir, 2017b; Pattanaik et al., 2018), which is a defense technique that adds adversarial examples into training sets (Goodfellow et al., 2014). On the other hand, Pinto et al. (2017) propose to improve the agent’s robustess to environment changes by training the agent and an adversary in an alternating procedure, where the attacks are operated on the environment dynamics. Tessler et al. (2019) study the agent’s robustness to action-space perturbations in continuous control domains, and achieve better performance even in the absence of the adversary.

heading: 3 LEARNING KEY STEPS TO ATTACK

heading: 3.1 THE KEY-STEP IDENTIFICATION PROBLEM
text: Suppose that an attacker would like to attack a target agent with policy π by adding perturbations to the states. We use η to denote an arbitrary attack method that maps from a state to a perturbation. Let B be the budget, the maximum number of attacks permitted in one episode. The key-step identification problem (Lin et al., 2017) can be formulated as follows:
min b1,...,bT∈{0,1}
E [ T∑ t=1 r(st, at) ] s.t. at ∼ π(st + btη(st)), st+1 ∼ P (st, at), ∀1 ≤ t ≤ T,
T∑ t=1 bt ≤ B.
(1)
In this problem. the attacker aims to minimize the expected return of the target agent under the budget constraint. The binary variable bt indicates whether the perturbation η(st) is added to the state st, and t is a key step found by the attacker if bt = 1.
Problem (1) is a difficult combinatorial problem with exponentially large search space. Each decision of the attacker changes the subsequent steps. Moreover, the transition dynamics and reward distribution may be random. Even if the attacker manages to search the whole space by brute force, the collected episodes are merely samples. The attacker still needs to estimate the expected return.
Due to these difficulties, previous works (Lin et al., 2017; Kos & Song, 2017) design simple heuristics to find the key steps. Suppose that the target agent is parametrized by a Q-network fθ.1 Kos & Song (2017) observe that steps with large Q-value are usually followed by large immediate reward, and hypothesize that an attack is effective at steps with large Q-value. They propose to set bt = 1 if the maximum Q-value maxa fθ(st)a is larger than a given threshold. On the other hand, Lin et al. (2017) propose to add perturbations when the agent is confident about its action. They use the softmax function to convert the Q-values into a probability distribution (let π = softmax ◦ fθ), and set bt = 1 if the probability gap maxa π(st)a −mina π(st)a is larger than a given threshold.

heading: 3.2 AN RL FRAMEWORK FOR LEARNING THE KEY STEPS
text: To address these challenges, we design an RL framework that directly solves the key-step identification problem. Based on the Lagrange relaxation technique (Bertsekas, 1997), we first replace the hard budget constraint with a soft penalty term:
min b1,...,bT∈{0,1}
E [ T∑ t=1 r(st, at) ] + λ T∑ t=1 bt
s.t. at ∼ π(st + btη(st)), st+1 ∼ P (st, at), ∀1 ≤ t ≤ T,
(2)
where λ is a parameter that controls the penalty for each attack. Now Problem (2) becomes a sequential decision problem without additional constraints. We then propose to solve this problem through
1These heuristics can be applied to attack other value-based or policy-based agents in a similar way.
RL by training an attack policy that identifies the key steps. Figure 2 illustrates the interactions among the environment, the target agent, and the attacker.
Here we describe our proposed RL framework in details. Suppose that the target agent with policy π is trained to maximize the expected return in an MDPM = (S,A, P,R, γ). We propose to train the attack policy π′ in another MDPM′ = (S′,A′, P ′, R′, γ′), where each component is defined as follows:
• S′ = S, and γ′ = γ.
• The attacker’s action space A′ = {0, 1}.
• For all s ∈ S′, b ∈ A′, the transition dynamics P ′(s, b) = P (s, a), and the reward R′(s, b) = −R(s, a)− bλ, where a ∼ π(s+ bη(s)) is the target agent’s action.
The new environment M ′ has the same state space as M , but reduces to binary action space with the action “1” representing an attack at that step and “0” otherwise. The attacker’s reward is the negative of the target agent’s reward, plus a penalty of λ for each attack. Therefore, maximizing the expected return inM′ is equivalent to minimizing the objective in Problem (2). Our proposed RL framework is general. We make no assumptions on the environment or on the target agent. In addition, our RL framework can be freely paired with any RL algorithm and any attack method when training the attack policy. Thus, both white-box and black-box attack scenarios can be considered in this framework.

heading: 3.3 THE POTENTIAL OF LEARNING THE KEY STEPS
text: Here we justify our RL framework by giving a toy example where the prior methods fail to identify the key steps. Consider a simple MDP shown in Figure 3. Suppose that we would like to attack an agent with its policy and Q-value function given in the figure. If we set the budget constraint B = 2, the most effective attack policy should attack steps 1 and 3. However, both heuristics are unable to find these two key steps.
This toy example highlights the potential drawback of these heuristics. Since the attacker might change the agent’s policy in the future steps, the agent’s Q-value estimates in the current step could be inaccurate. As a result, heuristics based on these Q-value estimates may not find the most effective key steps. In contrast, our framework trains the attacker from scratch. We do not rely on humandesigned heuristics, and thus the learned attacker may be able to identify the most effective key steps in this example.

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENTAL SETUP
text: We evaluate the proposed RL framework on four Atari 2600 games in the Arcade Learning Environment (Bellemare et al., 2013) (Pong, Space Invaders, Seaquest, and Riverraid), which covers a variety of environments. The environment setting and preprocessing match the guidelines suggested by Machado et al. (2018). In particular, we use a sticky-action probability of 0.25 in these environments. For the target agent, we take pretrained DQN agents from Dopamine (Castro et al., 2018), which have the same network architecture as Mnih et al. (2015), and fix them thereafter. We train the attack policy using DQN with this same architecture. It is worth mentioning that we train each attack policy for 10M frames, which is only 1/20 of the frames used to train the target agents. Other hyperparameters are reported in Appendix (Table 2).
Throughout the experiments, we use the untargetted FGSM to generate perturbations due to its computation efficiency. Although we only test our framework in this setting, we expect the framework to generalize to the case of targetted attack, or to other adversarial attack algorithms. We use Foolbox (Rauber et al., 2017) to generate the adversarial examples, with the norm constraint set to 0.01. Figure 4 shows an example of the perturbation, which is imperceptible to human and can only be visualized after rescaled. To make the scenario more realistic, we follow Hussenot et al. (2019) and
perturb the target agent’s observation, rather than the whole state. That is, although the target agent stack the latest four frames as its current state, the attacker is only allowed to add perturbation to the latest frame.

heading: 4.2 PERFORMANCE COMPARISON OF THE ATTACK POLICY
text: We compare the attack policy trained by our RL framework, to a random baseline that attacks uniformly at random, and to two heuristics, large-value (Kos & Song, 2017) and large-prob-gap (Lin et al., 2017). Figure 5 plots the results in the white-box setting, where the attacker has full knowledge of the target agent’s network parameters. The attack policy learned in our RL framework shows comparable performance to human-designed heuristics across different attack ratios consistently, and achieves superior performance in Pong and Riverraid. These results suggest that the key steps are learnable, and that it is possible to identify more effective key steps using our method.
We also test our framework with black-box attacks, where the attacker cannot access the target agent’s network parameters. We adopt the substitute model approach, and take the substitute agent from Dopamine, which is a DQN agent trained with a different random seed. The substitute agent is used to compute the perturbations and the statistics needed in the two heuristics. The results are shown in Figure 6. Compared to white-box attacks, black-box attacks are of less success rate, and thus the effect of the attacks is weakened (cf. Figure 5). Still, our method is able to perform comparably to (in Space Invaders, Seaquest, Riverraid) or outperform (in Pong) previous methods.

heading: 4.3 THE EFFECT OF THE PENALTY PARAMETER
text: To investigate the penalty parameter λ, we summarize the performance of the learned attack policies with white-box attacks in Table 1. Results obtained with black-box attacks can be found in Appendix (Table 3). As λ decreases, our RL framework tends to learn an attack policy with higher attacker ratio. Training with too large values of λ would restrict the attack policy from launching any attacks. Therefore, choosing an appropriate λ is important for learning effective key steps. Empirically, we
observe that setting λ around the same order of magnitude as
Potential reward loss = Original return of target agent−Minimum return of environment
Number of steps per episode would produce stable results (see Table 4 and Figure 8 in Appendix). This observation could guide the choice of λ in different environments.

heading: 4.4 BEHAVIOR COMPARISON OF THE ATTACK POLICY
text: To understand to what extent the attack policy learned in our RL framework is different from the heuristics, we attack the target agent by the learned attack policy, and compute the statistics used by the two heuristics at each step. Figure 7 plots the histogram of those statistics in one episode of Pong. We can see that the key steps found by our method spread across different intervals, rather than focusing on the largest intervals. This result suggests that our method does not simply mimic the heuristics, but indeed learns unique key steps to attack. The results of other environments are similar and can be found in Appendix (Figure 9).

heading: 5 DISCUSSION
text: We show that the key-step identification problem can be solved by training an attack policy through RL. Compared to existing works, our method learns different key steps without any human knowledge. Results on Atari benchmarks validate our belief that the proposed method may learn more effective key steps. This raises safety concerns on the real-world applications of deep RL agents. One possible future direction is to study how we can improve the RL agent’s robustness to this kind of key-step attacks. For example, combining the idea of alternating training (Pinto et al., 2017; Tessler et al., 2019) into our RL framework could be a fruitful research direction. Since the RL agent’s robustness is mostly studied in continuous environments (e.g., MuJoCo), we hope that this work attracts more attention into studying this topic in environments with discrete actions.

heading: A APPENDIX

Review summaries:
This paper proposes to learn the ‘key-steps’ at which to to apply an adversarial attack on a reinforcement learning agent. The framing of this problem is a Lagrangian relaxation of a constrained minimization problem which takes the form of an RL problem itself, where the attacking agent’s reward is the negative reward of the target agents plus a penalty (lambda, hyper-parameter) for choosing to attack. The attacking agent’s action space is binary, attack or no attack.