Belief-Enriched Pessimistic Q-Learning against Adversarial State Perturbations
Authors: Xiaolin Sun
Zizhan Zheng
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement Learning
Robustness
Adversarial Attack
Adversarial Defense
Primary area: reinforcement learning

Abstract: Reinforcement learning (RL) has achieved phenomenal success in various domains. However, its data-driven nature also introduces new vulnerabilities that can be exploited by malicious opponents. Recent work shows that a well-trained RL agent can be easily manipulated by strategically perturbing its state observations at the test stage. Existing solutions either introduce a regularization term to improve the smoothness of the trained policy against perturbations or alternatively train the agent's policy and the attacker's policy. However, the former does not provide sufficient protection against strong attacks, while the latter is computationally prohibitive for large environments. In this work, we propose a new robust RL algorithm for deriving a pessimistic policy to safeguard against an agent's uncertainty about true states. This approach is further enhanced with belief state inference and diffusion-based state purification to reduce uncertainty. Empirical results show that our approach obtains superb performance under strong attacks and has a comparable training overhead with regularization-based methods. Our code is available at https://github.com/SliencerX/Belief-enriched-robust-Q-learning.

Published as a conference paper at ICLR 2024
BELIEF-ENRICHED PESSIMISTIC AGAINST ADVERSARIAL STATE PERTURBATIONS
Q-LEARNING
Xiaolin Sun
Zizhan Zheng
Department of Computer Science Tulane University New Orleans, LA 70118
Department of Computer Science
Tulane University
New Orleans, LA 70118
xsun12@tulane, edu
z # edu
ABSTRACT
Reinforcement learning (RL) has achieved phenomenal success in various domains. However, its data-driven nature also introduces new vulnerabilities that can be exploited by malicious opponents. Recent work shows that a well-trained RL agent can be easily manipulated by strategically perturbing its state observations at the test stage. Existing solutions either introduce a regularization term to improve the smoothness of the trained policy against perturbations agent's policy and the attacker's policy. However, the former does not provide sufficient protection against strong attacks, while the latter is computationally prohibitive for large environments. In this work, we propose a new robust RI. algo- rithm for deriving pessimistic policy to safeguard against an agent's uncertainty about true states. This approach is further enhanced with belief state inference and diffusion- based state purification reduce uncertainty. Empirical results show that our approach obtains superb performance under strong attacks and has compara- ble training overhead with regularization-bant methods. Our code available at ottp://eeeeeeeeeeccceeooooooeeaa
alternatively train the
INTRODUCTION
As one of the major paradigms for data-driven control, reinforcement learning (RI.) provides principled and solid framework for sequential decision-making under uncertainty. By incorporating the approximation capacity of deep neural networks, deep reinforcement learning (DRL) has found impressive applications in robotics (Levine et al. 2016), large generative models (OpenAl 2023). and autonomous driving (Kiran et al. 2021), and obtained super-human performance in tasks such as Go (iilver et al. 2016) and Gran Turismo (Wurman et al. 2022).
However, an RL agent is subject to various types of attacks, including state and reward perturbation, action space manipulation, and model inference and poisoning (Ilahi et al.) (0022). Recent studies have shown that an RL agent be manipulated by poisoning its observation (Huang al. 2017 Zhang et al. 2020a) and reward signals (Huang & Zhu 2019), and a well-trained RL agent can be easily defeated by malicious opponent behaving unexpectedly (Gleave et 2020). In particular, recent research has demonstrated the brittleness (Zhang et al. |020al (Snn et al. 2021 of existing RL algorithms in the face of adversarial state perturbations, where malicious agent strategically and stealthily perturbs the observations of trained RL agent, causing significant loss of cumulative reward. Such an attack can be implemented in practice by exploiting the defects in the agent's perception component, e.g., sensors and communication channels. This raises significant concerns when applying RI. techniques in security and safety-critical domains.
Several solutions have been proposed to combat state perturbation attacks. Among them, SA- MDP Zhang et al. 2020a) imposes a regularization term in the training objective to improve the smoothness of the learned policy under state perturbations. This approach is improved in WocaR- RL (Liang et al. 2022) by incorporating an estimate of the worst-case reward under attacks into the training objective. In different direction, ATLA (Zhang al. (2021) alternately trains the agent's 's policy and the attacker's 's perturbation policy, utilizing the fact that under a fixed agent policy, the attacker's problem of finding the optimal perturbations be viewed as Markov decision process

---

Published as a conference paper at ICLR 2024
(MDP) and solved by RL. This approach can potentially lead to more robust policy but incurs high computational overhead, especially for large environments such as Atari games with raw pixel observations.
Despite their promising performance in certain RL environments, the above solutions have two major limitations. First, actions are directly derived from value or policy network trained using true states, despite the fact that the agent can only observe perturbed states at the test stage. This mismatch between the training and testing leads to unstable performance at the test stage. Second, most existing work does not exploit historical observations and the agent's knowledge about the underlying MDP model characterize and reduce uncertainty and infer true states in a systematic way.
In this work, we propose a pessimistic DQN algorithm against state perturbations by viewing the defender's problem as finding an approximate Stackelberg equilibrium for a two-player Markov game with asymmetric observations. Given a perturbed state, the agent selects an action that maximizes the worst-case value across possible true states. This approach is applied both training and test stages, thus removing the inconsistency between the two. We further propose two approaches to reduce the agent's 's uncertainty about true states. First, the agent maintains a belief about the actual state using historical data, which, together with the pessimistic approach, provides a strong defense against large perturbations that may change the semantics states. Second, for games with raw pixel imput, such Atari games, train diffusion model using the agent's knowledge about valid states, which is then used to purify observed states. This approach provides superb performance under commonly used attacks, with the additional advantage of being agnostic the perturbation level. Our method achieves high robustness and significantly outperforms existing solutions under strong attacks while maintaining comparable performance under relatively weak attacks. Further, its training complexity is comparable to SA-MDP and WocaR-RL and is much lower than alternating training- brased approaches.
2 BACKGROUND
2.1 REINFORCEMENT LEARNING
reinforcement learning environment is usually formulated as a Markov Decision Process (MDP), denoted by tuple A, P. R. 7), where S is the state space and A is the action space. P S x A + A (SS) is the transition function of the MDP, where P(s' [s, a) gives the probability of moving state s' given the current state and action a. R S x
R is the reward function where R(s, a) = [[R 8 = 8, 0 a) and RG is the reward in time step L. Finally, y is the discount factor. An RL agent wants to maximize its cumulative reward G = E[ R, over time horizon T E z U { by finding a (stationary) policy π : S + A(A), which can be either deterministic or stochastic. For any policy x, the state-value and action-value functions are two standard ways to measure how good is. The state-value function satisfies the Bellman (a)s) (s, + EE (. V,),,(s)) and the action-value function satisfies (s a) = R(s,a) + PEssesssss (,,a) E (oodsssQQe.. sz)Q (s', a')]. For MDPs with finite or countably infinite state space and finite action space, there is a deterministic and stationary policy that is simultaneously optimal for all initial states s. For large and continuous state and action spaces, deep reinforcement learning (DRL) incorporates the powerful approximation capacity of deep learning into RL and has found notable applications in various domains.
equation (s)
2.2 STATE ADVERSARIAL ATTACKS IN RL
First introduced Huang al. (2017). ). state perturbation attack is a test stage attack targeting an agent with a well-trained policy и. At each time step, the attacker observes the true state 8; and generates a perturbed state 5, (see Figure [] for examples). The agent observes 8, but not 8; and takes an action a according to (-16:). The attacker's goal is to minimize the cumulative reward that the agent obtains. Note that the attacker only interferes with the agent's observed state but not the underlying MDP. Thus, the true
(a) Original (b) Perturbed
(c) Original (d) Perturbed
Figure Examples of perturbed states : (a) and (b)
show states in a continuous state Gridworld, and (c) and (d) show states in the Atari Pong game.
2

---

Published as a conference paper at ICLR 2024
state in the next time step is distributed according P(s TT- (()). To limit the attacker's capability and avoid being detected, we assume that 3, E (st) where (s()s) is the lp ball centered at 8, for some norm p. We consider a strong adversary that has access to both the MDP and the agent's policy æ and can perturb at every time step. With these assumptions, it is easy to see that the attacker's problem given a fixed π can also be formulated as an MDP (5, , P, R, R) where both the state and action spaces are S, the transition probability P(s'| s, E. < P(s a). and reward R)s Cn, π ( 8) [(s, a). Thus, RL algorithm can be used to find (nearly) optimal attack policy. Further, we adopt the common assumption (Zhng et al.) 2020a Liang et al. 2022) that the agent has access to intact MDP the training stage and has access
(or estimation of it). As we discuss below, our diffusion- approach is agnostic to e. Detailed discussions of related work attacks and defenses in RL, including and beyond state perturbation, in Appendix B
PESSIMISTIC Q-LEARNING WITH STATE INFERENCE AND PURIFICATION
In this section, we first formulate the robust RL prob- lem as two-player Stackelberg Markov game. We then present our pessimistic Q-learning algorithm that derives maximin actions from the Q-function using perturbed states as the input to safeguard against the agent's uncer- tainty about true states. We further incorporate a belief state approximation scheme and a diffusion- basod state pu- rification scheme into the algorithm to reduce uncertainty. Our extensions of the vanilla DQN algorithm that incor- porates all three mechanisms are given in Algorithms 7 in Appendix E We further give a theoretical result that characterizes the performance loss of being pessimistic.
R₂
T:: Mr de
a2
Agent
Environment
S2
St
ag. ..., 55 $33_1
Me
(5c)
adg: St
Pretrained
Attacker
Beliet/Diffusion
Model
Belief-enriched robust RL against state perturbations. Note that the agent can only access the true state st and reward RG at the training stage.
Figure 2:
3.1 STATE-ADVERSARIAN MDP AS STACKELBERG MARKOV GAME WITH ASYMMETRIC OBSERVATIONS
The problem of robust RL under adversarial state perturbations can be viewed as a two-player Markov game, which motivates our pessimistic Q-learning algorithm given in the next subsection. The two players are the RL agent and the attacker with their state and action spaces and reward functions described in Section 2.2] The RL agent wants to find policy π S - A(A) that maximizes its long-term return, while the attacker wants to find an attack policy w - S to minimize the RL agent's 's cumulative reward. The game has asymmetric observations in that the attacker can observe the true states while the RL agent observes the perturbed states only. The agent's value functions for given pair of policies and w satisfy the Bellman equations below.
Definition 1. Bellman equations for state and action value functions under a state adversarial attack:
ViOw (s) ( R(s, + TEvEs ((s'ls s, (
+ P(sesP(s')s.
a')].
To achieve robustness, common approach is to consider a Stackelberg equilibrium by viewing the RL agent as the leader and the attacker as the follower. The agent first commits to policy The attack observes and identifies an optimal attack, denoted by We, as response, where ( d'). As the agent has access to the intact environment at the training stage and the attacker's budget e, it can, in principle, identify a robust policy proactively by simulating the attacker's behavior. Ideally, the agent wants to find a policy x² that reaches a Stackleberg equilibrium of the game, which is defined as follows.
(x) = argminge
Definition 2. A policy xO is a Stackelberg equilibrium of a Markov game if
Vs E S, Vn, Vnroww- (8) 2 Viow, (s).
A Stackelberg equilibrium ensures that the agent's 's policy n² is optimal (for any initial state) against the strongest possible adaptive attack and, therefore, provides a robustness guarantee. However, previous work has shown that due to the noisy observations, finding stationary policy that is optimal
3

---

Published as a conference paper at ICLR 2024
for every initial state is generally impossible (hhang et al. 2020a). Existing solutions either introduce a regularization term to improve the smoothness of the policy or alternatively train the agent's 's policy and attacker's policy. In this paper, we take different path with the goal of finding an approximate Stackelberg equilibrium (the accurate definition is in Appendix DD3). which is further improved through state prediction and denoising. Segureessooy the high-level framework of our approach, which is discussed in detail below.
3.2 STRATEGY I- PESSIMISTIC Q-LEARNING AGAINST THE WORST CASE
Both value-based (Könönen 2004) and policy-basete (Zheng et al. 2022, Vu et al. 2022) approaches have been studied to identify the Stackelberg equilibrium (or an approximation of it) of a Markov game. In particular, Stackelberg Q-learning (Könönen 2004) maintains separate Q-functions for the leader and the follower, which are updated by solving a stage game associated with the true state in each time step. However, these approaches do not apply our problem as they all require both players to have access to the true state in each time step. In contrast, the RI agent can only observe the perturbed state. Thus, it needs commit state instead of a single action, as in the stage game of Stackelberg Q-learning.
policy for all states centered around the observed
In this work, we present a pessimistic Q-learning algorithm (see Algorithm I to address the above challenge. The algorithm maintains Q-function with the true state as the input, similar to vanilla Q-learning. But instead of using a greedy approach derive the target policy e-greedy approach to derive the behavior policy from the Q-function, maximin approach is used in both cases. In particular, the target policy is defined as follows (line 5). Given a perturbed state š, the agent picks an action that maximizes the worst-case Q-value across all possible states in B. (8), which represents the agent's uncertainty. We abuse the notation bit and let (-)) denote a deterministic policy in the rest of the paper since we focus on Q-learning- -based algorithms in this paper. The behavioral policy is defined similarly by adding exploration (lines 8 and 9). The attacker's 's policy Wa is derived as the best response to the agent's 's policy (line 6), where perturbed state is derived by minimizing the Q value given the agent's 's policy.
A few remarks follow. First, the maximin scheme is applied when choosing an action with exploration (line 9) and when updating the Q-function (line 11), and a perturbed state is used as the input in both cases. In contrast, in both SA-DQN (Zhang et al., 2020a) and WocaR-DQN (Liang al. 2022), actions are obtained from the Q-network using true states at the training stage, while the same network is used at the test stage derive actions from perturbed states. Our approach removes this inconsistency, leading to better performance, especially under relatively large perturbations. Second, instead of the pessimistic approach, we may also consider maximizing the average case or the best case across B, (3) when deriving actions, which provides different tradeoff between robustness and efficiency. Third, we show how policies are derived from the Q-function to help explain the idea of the algorithm. Only the Q-function needs to be maintained when implementing the algorithm.
Figure 3 in the Appendix Cillustrates the relations between a true state s, the perturbed state 8, the worst-case state & E ($) for which the action is chosen (line 5). In particular, it shows that the true state 8 must land in the e-ball centered at 5, and the worst-case state the RL agent envisions is at most 2e away from the true state. This gap causes performance loss that will be studied in Section 3.6 For environments with large state and action spaces, we apply the above idea to derive pessimistic DQN algorithms (see Algorithms 4 7 in Appendix ED. which further incorporate state inference and purification discussed below. Although we focus on value-based approaches in this work, the key ideas can also be incorporated into Stackelberg policy gradient (Vu et al. 2022) and Stackelberg actor-critic (Zheng et al. 2022) approaches, which is left to our future work.
3.3 STRATEGY II REDUCING UNCERTAINTY USING BELIIF
In Algorithm|| [ the agent's 's uncertainty against the true state is captured by the c-ball around the perturbed state. A similar idea is adopted in previous regularization-base
approaches (Zhang et al., 2020al Liang et al. 2022). For example, SA-MDP (Zhag et al.) 2020a) regulates the maximum difference between the top-1 action under the true state & and that under the perturbed state across all possible perturbed states in (s). However, this approach is overly conservative and ignores the temporal correlation among consecutive states. Intuitively, the agent can utilize the sequence of historical observations and actions ()),, U (5r) and the transition dynamics of the underlying
4

---

Published as a conference paper at ICLR 2024
Algorithm I: Pessimistic Q-Learning
Result: Robust Q-function Q
Initialize Q(s, a) O for all E S, a E A;
for epsiode = 1,2.... do
Initialize true state
repeat
Update agent's policy: VS S, (8) = argmax
Update attacker's policy: Vs E S wx (s) = (rgm
Generate perturbed state (s);
Choose a from & using with exploration:
x3) with probability 1-6 E'; otherwise is a random action;
Take action a, observe reward It and next true state 8';
10
Update Q-function: Q(s,a) a) (s, a) + + ((s,a) a) + 7Q(s', (((),,<((><<))))))) Q(s.
11
12
8 = s';
13
until is terminal;
14
end
MDP to reduce its uncertainty of the current true state s;, This is similar to the belief state approach in partially observable MDPs (POMDPs). The key difference is that in a POMDP. the agent's observation o, in each time step is derived from fixed observation function with o = O(s,, at). In contrast, the perturbed state $ is determined by the attacker's policy w, which is non-stationary at the training stage and is unknown to the agent the test stage.
To this end, we propose a simple approach to reduce the agent's worst-case uncertainty as follows. Let M, C (&x) denote the agent's belief about all possible true states at time step L. Initially, we let Mo = B. (50). At the end of the time step t, we update the belief to include all possible next states that reachable from the current state and action with non-zero probability. Formally, let Mj = {s' E S 3s E Mr P(s'|s, 0z) > 0}. After observing the perturbed state $141, we then update the belief to be the intersection of M; and (5++))), i.e., Mc+1 = M' n (e($++1), which gives the agent's 's belief at time t + 1. Figure [3 in the Appendix Seanddxxxjeemosssss [demonstrate this process, and the formal belief update algorithm given Algorithm algorithm can easily incorporate the agent's belief. In each time step I, instead of using B, (3) in Algorithm| T (line 5), the current belief M, can be used. It is an interesting open problem to develop a strong attacker that can exploit even manipulate the agent's 's belief.
Appendix D Our pessimistic Q-learning
Belief approximation in large state space environments. When the state space is high-dimensional and continuous, computing the accurate belief as described above becomes infeasible computing the intersection between high-dimensional spaces is particularly hard. Previous studies have proposed
various techniques to approximate the agent's belief about true states using historical data in partially observable settings, including using classical RNN networks (Ma et al. 2020) and flow-based recurrent belief state learning (Chen et al. 2022). In this work, we adapt the particle filter recurrent neural network (PF-RNN) technique developed in (Ma et al. 2020) to our setting due to its simplicity, In contrast to a standard RNN-based belief model B (S x A)" + that maps the historical observations and actions to a deterministic latent state h,, PF-RNN approximates the belief b (4)) by Kip weighted particles in parallel, which are updated using the particle filter algorithm according to the Bayes rule. An output function fout then maps the weighted average of these particles in the latent space to a prediction of the true state in the original state space.
To apply PF-RNN to our problem, we first train the RNN-based belief model N and the prediction function fout before learning a robust RL policy. This is achieved by using C' trajectories generated by random agent policy and a random attack policy in an intact environment. Then at each time step & during the RL training and testing, we use the belief model N and historical observations and actions generate Kp particles, map each of them to state prediction using fout, and take the set of Kp predicted states as the belief M, about the true state. PF-RNN includes two versions that support LSTM and GRU, respectively, and use PF-LSTM implement our approach. We define the complete belief model utilizing PE-RNN as N₂ Sout B.
5

---

Published as a conference paper at ICLR 2024
We remark that previous work has also utilized historical data to improve robustness. For example, Xiong et al. (2023) uses an LSTTM-autoencoder to detect and denoise abnormal states at the test stage, and Zhang et al. (22TT) considers an LSTM-based policy in alternating training. However, none of them explicitly approximate the agent's belief about true states and use to derive a robust policy.
3.4 STRATEGY III PURIFYING INVALID OBSERVATIONS VIA DIFFUSION
For environments that use raw pixels as states, such as Atari Games, perturbed states generated by adding bounded noise to each pixel are mostly "invalid" in the following sense. Let So C S denote the set of possible initial states. Let 5 denote the set of states that are reachable from any initial state in So by following an arbitrary policy. Then perturbed states will fall outside of 5 with high probability. This is especially the case for to attacks that bound the perturbation applied to each pixel as commonly assumed in existing work (see Appendix C.2 for an example). This observation points to a fundamental limitation of existing perturbation attacks that can be utilized by an RL agent to develop a more efficient defense.
One way to exploit the above observation is to identify a set of "valid" states near perturbed state and use that as the belief of the true state. However, it is often difficult to check if a state is valid or not and to find such set due to the fact that raw pixel inputs are usually high-dimensional. Instead, we choose to utilize a diffusion model to purify the perturbed states, which obtains promising performance, we show in our empirical results.
To this end, we first sample C' trajectories from a clean environment using a pre-trained policy without attack to estimate a state distribution q(-). which is then used to train Denoising Diffusion Probabilistic Model (DDPM) (Ho et al. 2020). Then during both RL training and testing, when the agent receives a perturbed state 8, applies the reverse process of the diffusion model for k steps to generate a set of purified states as the belief M, of size Kgz where k and Kd are hyperparameters. We let Na: : S + Sth. denote diffusion-basee belief model. Note that rather than starting from random noise in the reverse process as in image generation, we start from perturbed state that the agent receives and manually add small amount of pixel-wise noise ø to it before denoising, inspired by denoised smoothing in deep learning (Xiao et al. [0022). We observe in experiments that using a large k does not hurt performance, although it increases the running time. Thus, unlike previous work, this approach is agnostic to the accurate knowledge of attack budget One problem with DDPM, however, is that it incurs high overhead to train the diffusion model and sample from it, making less suitable for real-time decision- making. To this end, we further evaluate a recently developed fast diffusion technique, Progressive Distillation (Salimans & Ho 2022), which distills a multi-step sampler into few-step sampler. As we show in the experiments, the two diffusion models provide different tradeoffs between robustness and running time. A more detailed description of the diffusion models and our adaptations are given in Appendix B.6
3.5 PESSIMISTIC DQN WITH APPROXIMATE BELIEFS AND STATE PURIFICATION
Built upon the above ideas, we develop two pessimistic versions of the classic DQN algorithm (Mnih cet al., 2013) by incorporating approximate belief update and diffusion- purification, denoted by
BP-DQN and DP-DQN, respectively. The details are provided in Algorithms 4 7 in Appendix
Below we highlight the main differences between our algorithms and vanilla DQN.
The biggest difference lies in the loss function, where we incorporate the maximin search into the loss function to target the worst case. Concretely, instead of setting yi R² + EA a') as in vanilla DQN, we set y/1 R. + from the replay buffer and Q' is the target network. Similarly, instead of generating actions using the e-greedy (during training) or greedy approaches (during testing), the maximin search is adopted.
Q'(m, a') where R, S,, M, are sampled
To simulate the attacker's behavior, one needs to identify the perturbed state that minimizes the Q value under the current policy π subject to the perturbation constraint. As finding the optimal attack under large state space is infeasible, we solve the attacker's problem using projected gradient descent (PGD) with 7) iterations to find an approximate attack similar to the PGD attack in (Zhang et al. 2020a). In BP-DQN where approximate beliefs are used, the history of states and actions is saved to generate the belief in each round. In DP-DQN where diffusion is used, the reverse process is applied to both perturbed and true states. That is, the algorithm keeps the purified version of the true

---

Published as a conference paper at ICLR 2024
states instead of the original states in the replay buffer during training. We find this approach helps reduce the gap between purified states and true states. In both cases, instead training a robust policy from scratch, we find that helps to start with pre-trained model obtained from an attack-free MDP.
We want to highlight that BP-DQN is primarily designed for environments with structural input, whereas DP-DQN is better suited for environments with raw pixel input. Both approaches demonstrate exceptional performance in their respective scenarios, even when faced with strong attacks, as shown in our experiments. Thus, although combining the two methods by integrating history-based belief and diffusion techniques may seem intuitive, this is only needed when confronted with an even more formidable attacker, such as one that alters both semantic and pixel information in Atari games.
3.6 BOUNDING PERFORMANCE Loss DUE TO PESSIMISM
In this section, characterize the impact of being pessimistic in selecting actions. To obtain insights. we choose to work on a pessimistic version of the classic value iteration algorithm (see Algorithm in Appendix E. which is casier to analyze than the Q-learning algorithm presented in Algorithm To this end, we first define the Bellman operator for given pair of policies.
Definition 3. For given pair of agent policy æ and attack policy w, the Bellman operator for the Q-function is defined as follows.
TT Q(s a) R(s, a) +
((s(ss)
(I)
The algorithm maintains a Q-function, which initialized to 0 for all state-action pairs. In each round n, the algorithm first derives the agent's policy Th and attacker's policy wa,, from the current using the worst-case belief, where
Q-function Qn in the same way as in Algorithm D
n. (8) argna VE
Wxp (s) B, (3))) e
That is, Tn is obtained by solving a maximin problem using the current Qn. and Wi. is a best response to Tn. The Q-function is then updated as Qn+1 = TT owin Qn It is important to note that although groww is contraction for fixed x (see Lemma in Appendix D for proof), Two is typically not due its dependence on Qn Thus, On may not converge in general, which consistent with the known fact that aaversadvrraaial MDP may not have stationary policy that is optimal for every initial state. However, we show below that we can still bound the gap between the Q-value obtained by following the joint policy मn = nn WT,,, denoted by QTx,, and the optimal Q-value for the original MDP without attacks, denoted by Q" It is known that Q" is the unique fixed point of the Bellman optimal operator T"* i.e., T Q Q", where
T (*Q(s,a) a) = R(s a) + >Evess P('ll,, a
We first make the following assumptions about the reward and transition functions of an MDP and then state the main result after that. Assumption 1. The reward function and transition function are Lipschitz continuous. That is, there are constants 1, and Ip such that for Vsi, 82, s' E S, Va A, we have
(R(s),))-((s2000 a)l S 4.11s1 - s2ll. IP(s | a) P(s' |s, a)) S 1plls1 -s2ll-
Assumption 2. Reward R upper bounded where for any s E and a E A, R(s, a) S Rmaz.
Theorem 1. The gap between Q²n and Q* is bounded by
1+7
limsup no 11Q2 - -Q²x 100 S (1 7)2
where nn is obtained by Algorithm 3 and A = 21y + 1p111 Rmaz 1
We give a proof sketch and leave the detailed proof in Appendix D We first show that Q is Lipschitz continuous using Assumptior[] Then establish bound of I Qutall oo and prove that Trow, for a fixed policy π is a contraction. Finally, we prove Theorem Tolommm@ooloooo following the idea of Proposition 6.1 in (Bertsekas & Tsitsiklis 1996).
7

---

Published as a conference paper at ICLR 2024
Enviromment
Model
Natural Reward
0,1
PGD
0.5
0.1
MinBest
0.1
PA-AD
DDQ SA-DON
156.5 90.2
128 118
-53 2
98.2 137
982= 137
10.7
136
-35.9
GridWorld
20.8 4 140
46 142
- -100 0
-5.8 4 131
-100
97.5
13.6
-67.8 78.3
Continous
WocaR. DQN
63 88
100 0
63.2 +
100 +
63.2 88
100
63.2
BP.DON (Ouns)
163 26
165 4 29
176 16
147 58
114
1719
177.2 10.6
(a) Continuous Gridworld Results
Model
1723
137285
1/255
Minleat
3225
157255
PA-AD
13/255
-21
SA-DON
-008-
WozzRR-OO
-
-21
21-00
19.7+224
-21
DISDON-D (Cumr)
188004
107000
199
199=03
193
19.9
UP DKN (Ouns)
204
29
a
2:
20
21.0.:00
1.
2
DQN
20=0
00:00
2.
18.3
0=00
2
3.5
Freewuy
WocaR,
0..2404
=12=05
014
11
296
198
21.61
24.9
12.3
21.6
DP (Ours)
09109
202
28:5-1
26.6
28:323
1.1
DP-DQN-- (Ourd)
11.2+
300=00
=01=1
307 = 1.2
302 13
306=11 1.1
28.4 1.2
30.5
S1.4 4...
28.9 1.1
(b) Atari Games Results
Table 1: Experiment Results. We show the average episode rewards + standard deviation 10 episodes for our methods and three baselines. The results for our methods are highlighted in gray.
4 EXPERIMENTS
In this section, evaluate our belief-enriched pessimistic DQN algorithms by conducting experi- ments on three environments, a continuous state Gridworld environment (shown in Figure Ta) for BP-DQN and two Atari games, Pong and Freeway for DP-DQN-O and DP-DQN-F, which utilize DDPM and Progressive Distillation as the diffusion model, respectively. (See Appendix F. for justification.) We choose vanilla DQN (Mnih et al. 2015), SA-DQN (Zhang et al. 2020a WocaR- DQN (Liang et al. 2022), and Radial-DQN (Oikarinen et al. 2021) as defense baselines. We consider three commonly used attacks to evaluate the robustness of these algorithms: (1) PGD attack (Zhang
et al., 2020a). which aims to find perturbed state ğ that minimizes Q(s, (3)): (2) MinBest at- tack (Huang et al. 2017). which aims to find a perturbed state that minimizes the probability of choosing the best action under s; and (3) PA-AD (Sun et al.) 2021). which utilizes RL to find (nearly) optimal attack policy. Details on the environments and experiment setup can be found in
Appendix F2
Additional experiment results and ablation studies are given in Appendix F3
4.1 RESULTS AND DISCUSSION
Continuous Gridworld. As shown in Table la our method (BP-DQN) achieves the best performance under all scenarios in the continuous state Gridworld environment and significantly surpasses all the baselines. In contrast, both SA-DQN and WocaR-DQN fail under the large attack budget 0.5 and perform poorly under the small attack budget 0.1. We conjecture that this is because state perturbations in the continuous Gridworld environment often change the semantics states since most perturbed states are still valid observations. We also noticed that both SA-DQN and WocaR- DQN perform worse than vanilla DQN when there is no attack and when e = 0.1. We conjecture that this is due the mismatch between true states and perturbed states during training and testing and the approximation used to estimate the upper and lower bounds of Q-network output using the Interval Bound Propagation (IBP) technique (Gowal et al. 2019 in their implementations. Although WocaR-DQN performs better under 0.5 than e = 0.1, it fails in both cases to achieve the goal of the agent where the policies end up wandering in the environment reaching the bomb instead of finding the gold.
Atari Games, As shown in Table db our DP-DQN method outperforms all other baselines under a strong attack (e.g., PA-AD) or large attack budget (c.g.. e = 15/255), while achieving comparable performance as other baselines in other cases. SA-DQN and WocaR-DQN fail to respond to large state perturbations for two reasons. First, both of them use IBP to estimate an upper and lower bound of the neural network output under perturbations, which are likely to be loose under large perturbations. Second, both approaches utilize regularization-based approach to maximize the chance of choosing the best action for all states in the c-ball centered at the true state. This approach is effective under small perturbations but can pick poor actions for large perturbations as the latter can easily exceed the generalization capability of the -enttwor.. We observe that WocaR- -DQN performs better when the attack budget increases from 3/255 to 15/255 in Freeway, which is counter-intuitise
8

---

Published as a conference paper at ICLR 2024
PGD
PA-AD
Environment
Model
Environment
Model
0.5
15/255
Maximin Only
71 1: 91
Maximin Only
21 0
Continuous
Belief Only
45.7 + 134
Pong
DDPM Only
18.8 + 1.6
Gridworld
BP-DQN (Ours)
176 +: 16
DP-DQN-O (Ours)
19.3 -: 0.8
Table 2: Ablation Study Results. We compare our methods with variants that use maximin search or belief approximation only.
The reason is that under large perturbations, the agent adopts a bad policy by always moving forward regardless of state, which gives a reward of around 21. Further, SA-DQN and WocaR-DQN need to know the attack budget in advance in order to train their policies. A policy trained under attack budget e = 1/255 is ineffective against larger attack budgets. In contrast, our DP-DQN method is agnostic to the perturbation level. All results of DP-DQN shown in Table lb are generated with the same policy trained under attack budget c = 1/255.
We admit that our method suffers small performance loss compared with SA-DQN and WocaR- DQN in the Atari games when there is no attack or when the attack budget is low. We conjecture that single fixed policy is simultancously optimal against different types of attacks. A promising direction is to adapt pre-trained policy to the actual attack using samples collected online.
Importance of Combining Maximin and Belief. In Table 2 we compare methods (BP-DQN and DP-DQN-O) that integrate the ideas of maximin search and belief approximation (using either RNN or diffusion) with variants of methods that use maximin search or belief approximation only. The former is implemented using trained BP-DQN or DP-DQN-O policy together with random samples from the e-ball centered a perturbed state (the worst-case belief) during the test stage. The latter uses the vanilla DQN policy with single belief state generated by either the PF-RNN or the DDPM diffusion model at the test stage. The results clearly demonstrate the importance of integrating both ideas to achieve more robust defenses.
5 CONCLUSION AND LIMITATIONS
In conclusion, this work proposes two algorithms, BP-DQN and DP-DQN, to combat state per- turbations against reinforcement learning. Our methods achieve high robustness and significantly outperform state-of-the-art baselines under strong attacks. Further, our DP-DQN method has revealed an important limitation of existing state adversarial attacks on RL agents with raw pixel input, pointing to promising direction for future research.
However, our work also has some limitations. First, our method needs access to clean environment during training. Although the same assumption has been made in most previous work in this area, including SA-MDP and WocaR-MDPP a promising direction is to consider an offline setting to release the need to access a clean environment by learning directly from (possibly poisoned) trajectory data. Second, using a diffusion model increases the computational complexity of our method and causes slow running speed at the test stage. Fortunately, have shown that fast diffusion methods can significantly speed up runtime performance. Third, we have focused on value-based methods in this work. Extending our approach policy-based methods is an important next step.
ACKNOWLEDGMENTS
This work has been funded in part by NSF grant CNS-2146548 and Tulane University Jurist Center for Artificial Intelligence. We thank the anonymous reviewers for their valuable and insightful feedback.

---

Published as a conference paper at ICLR 2024
REFERENCES
Karl Astrom et al. Optimal control of markov processes with incomplete state information. Journal of mathematical analysis and applications, 10(1):174-25) 1965.
Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1st edition, 1996. ISBN 1886529108.
Shubham Bharti, Xuezhou Zhang, Adish Singla, and Jerry Zhu. Provable defense against backdoor policies in reinforcement learning. Advances in Neural Information Processing Jystems(NeurIPS)) 2022.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606.01540 2016.
Kangjie Chen, Shangwei Guo. Tianwei Zhang, Xiaofei Xie, and Yang Liu. Stealing deep reinforce- ment learning models for fun and profit. Proceedings of the 2021 ACM Asia Conference on Computer and Communications Security, pp. 307-319, 2021.
Xiaoyu Chen, Yao Mark Mu, Ping Luo, Shengbo Li, and Jianyu Chen. Flow-based recurrent belief state learning for pomdps. In International Conference on Machine Learning//MML), 2022.
Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In International Conference Machine Learning(ICMLI), 2020.
Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adver- sarial policies: Attacking deep reinforcement learning. In International Conference on Learning Represenntations//CLRR) 2020.
Sven Gowal, Krishnamurthy Dj Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. Scalable verified training for provably robust image classification. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019.
Danijar Hafner, Timothy P Lillicrap, Mohammad Norouzi, and Jimmy Ba. Mastering atari with discrete world models. In International Conference on Learning Representattioss(CCI... 2021.
Sihong He, Songyang Han, Sanbao Su, Shuo Han, Shaofeng Zou, and Fei Miao. Robust multi-agent reinforcement learning with state uncertainty. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. arXiv preprint arxiv:2006. / //339, 2020.
Mengdi Huai, Jianhui Sun, Renqin Cai, Liuyi Yao, and Aidong Zhang. Malicious attacks against deep reinforcement learning interpretations. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 472 482, 2020.
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. 1701v:1702.02284, 2017.
Yunhan Huang and Quanyan Zhu. Deceptive reinforcement learning under adversarial manipulations on cost signals. In Decision and Game Theory for Security (GameSec), pp. 217-237, 2019.
Inaam Ilahi, Muhammad Usama, Junaid Qadir, Muhammad Umar Janjua, Ala Al-Fuqaha, Dinh Thai Hoang, and Dusit Niyato. Challenges and countermeasures for adversarial attacks on deep reinforcement learning. IEEE Transactions on Artificial Intelligence, 3(2):90-109, 2022. doi: 10. 10.110//11122011111111
B Ravi Kiran, Ibrahim Sobh, Victor Talpaert, Patrick Mannion, Ahmad A. Al Sallab, Senthil Yogamani, and Patrick Pérez. Deep reinforcement learning for autonomous driving: A survey, 2021.
10

---

Published as a conference paper at ICLR 2024
Ville Könönen. Asymmetric multiagent reinforcement learning. Web Intelligence and Agent Systems: An international journal, 2(2):105-121) 2004.
Alex X Lee, Anusha Nagabandi, Pieter Abbeel, and Sergey Levine. Stochastic latent actor-critic: Deep reinforcement learning with a latent variable model. Advances in Neural Information Processing Systems(Neur/PS), 2020a.
Xian Yeow Lee, Sambit Ghadai, Kai Liang Tan, Chinmay Hegde, and Soumik Sarkar. Spatiotempo- rally constrained action space attacks deep reinforcement learning agents. In Proceedings of the AAAI conference on artificial intelligence(AAAA),, volume 34, pp. 4577-4584, 2020b.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):13341133,, 2016.
Yongyuan Liang. Yanchao Sun, Ruijie Zheng, and Furong Huang. Efficient adversarial training without attacking: Worst-case-awar robust reinforcement learning. In Advances in Neural Information Processing Systems SeurlPS), 2022.
Xiao Ma, Péter Karkus, David Hsu, and Wee Sun Lee. Particle filter recurrent neural networks. In The Thirty- Foirt-Fourth AAAI Conference on Artificial Intelligence(AAAI), 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, 2013.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 5 31875540:529-533 2015.
Tuomas Oikarinen, Wang Zhang, Alexandre Megretski, Luca Daniel, and Tsui- Wei Weng. Robust deep reinforcement learning through adversarial loss. Advances in Neural Information Processing Systems(Neur/PS), 2021.
OpenAL. Gpt-4 technical report, 2023.
Nicholas Roy, Geoffrey Gordon, and Sebastian Thrun. Finding approximate pomdp solutions through belief compression. Journal of artificial intelligence research, 23:1-40 2005.
Tim Salimans and Jonathan Ho. Progressive distillation for fast sampling of diffusion models. In International Conference on Learning Representations(/CLRR) 2022.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schritwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587)4844488) 2016.
Yanchao Sun, Ruijie Zheng, Yongyuan Liang, and Furong Huang. Who the strongest enemy? towards optimal and efficient evasion attacks in deep rl. arXiv preprint arXiv:2106.05087, 2021.
Sebastian Tschiatschek, Kai Arulkumaran, Jan Stühmer, and Katja Hofmann, Variational inference for data-efficient model learning in pomdps. arXiv preprint arXiv: /805, /00.00//00.0081,,, 2018.
Quoc-Liem Vu, Zane Alumbaugh, Ryan Ching, Quanchen Ding, Arna Mahajan, Benjamin Chasnov, Sam Burden, and Lillian Ratliff. Stackelberg policy gradient: Evaluating the performance of leaders and followers. /CLR 2022 Workshop on Gamification and Multiagent Solutions, 2022.
Peter R Wurman, Samuel Barrett, Kenta Kawamoto, James MacGlashan, Kaushik Subramanian, Thomas J Walsh, Roberto Capobianco, Alisa Devlic, Franziska Eckert, Florian Fuchs, et al. Outracing champion gran turismo drivers with deep reinforcement learning. Nature, 602(7896): 223-228. 2022.
Chaowei Xiao, Zhongzhu Chen, Kun Jin, Jiongxiao Wang. Weili Nie. Mingyan Liu, Anima Anand- kumar, Bo Li, and Dawn Song. Densepure: Understanding diffusion models towards adversarial robustness. arXiv preprint 2rXiv:22/1.0033 2022.

---

Published as a conference paper at ICLR 2024
Zikang Xiong, Joe Eappen, He Zhu, and Suresh Jagannathan. Defending observation attacks in deep reinforcement learning via detection and denoising, Berlin, Heidelberg, 2023. Springer- Verlag. ISBN 978-3-031-26408-5.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho-Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations on state observations. In Advances in Neural Information Processing Systems(Neur/PS)) 2020a.
Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsieh. Robust reinforcement learning on state observations with learned optimal adversary. In International Conference on Learning Representatiooss//CLR)) 2021.
Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive reward-poisoning attacks against reinforcement learning. In International Conference Machine Learning(ICML), 2020b.
Liyuan Zheng, Tanner Fiez, Zane Alumbaugh, Benjamin Chasnov, and Lillian Ratliff. Stackelberg actor-critic: Game-theoretic reinforcement learning algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence(AAAI), 2022.
12

---

Published as a conference paper at ICLR 2024
APPENDIX
A BROADER IMPACTS
As RL is increasingly being used in vital real-world applications like autonomous driving and large generative models, we are rapidly moving towards an Al-assisted society. With Al becoming more widespread, it is important ensure that the policies governing Al are robust. An unstable policy could be easily exploited by malicious individuals or organizations. causing damage to property, productivity, and even loss of life. Therefore, providing robustness is crucial the successful deployment of RL and other deep learning algorithms in the real world. Our work provides new insights into enhancing the robustness of RL policies against adversarial attacks and contributes to the foundation of trustworthy AI.
B RELATED WORK
B. STATE PERTURBATION ATTACKS AND DEFENSES
State perturbation attacks against RL policies are first introduced in Huang al. (2017), where the MinBest attack that minimizes the probability choosing the best action is proposed. Zhang et al. (2020a) show that when the agent's 's policy is fixed, the problem of finding the optimal adversarial policy is also an MDP, which can be solved using RL. This approach is further improved in (Sun et al.) 2021
where a more efficient algorithm for finding the optimal attack called PA-AD is developed.
On the defense side, Zhang et al. (2020a) prove that policy that is optimal for any initial state under optimal state perturbation might not exist and propose set of regularization-bet
algorithms (SA-DQN, SA-PPO, SA-DDPG) to train a robust agent against state perturbations. This approach is improved in (Liang et al. 2022 by training additional worst-case Q-network and introducing state importance weights into regularization. In different direction, an alternating training framework called ATLA is studied in (Zhang al., 202I) that trains the RL attacker and RL agent alternatively in order to increase the robustness of the DRL model. However, this approach suffers from high computational overhead. Xiiong et al. (2023) propose an auto-encoder-basse detection and denoising framework to detect perturbed states and restore true states. Also, He et al. (2023) show that when the initial distribution is known, policy that optimizes the expected return across initial states under state perturbations exists.
B.2 ATTACKS AND DEFENSES BEYOND STATE PERTURBATIONS
This section briefly introduces other types of adversarial attacks in RL beyond state perturbation. As shown in (Huang & Zhu 2019), manipulating the reward signal can successfully affect the training convergence of Q-learning and mislead the trained agent follow policy that the attacker aims at. Furthermore, an adaptive reward poisoning method is proposed by (Zhang et al.) 2020b) to achieve a nefarious policy in steps polynomial in state-space size |S) in the tabular setting.
Lee et al. 2020b) propose two methods for perturbing the action space, where the LAS (look-ahead action space) method achieves better attack performance in terms of decreasing the cumulative reward of DRI. by distributing attacks across the action and temporal dimensions. Another line of work investigates adversarial policies in a multi-agent environment, where it has been shown that an opponent adopting adversarial policy could casily beat agent with well-trained policy in zero-sum game (Gleave et al. 2020).
For attacking an RL agent's policy network, both inference attacks (Chen et al.) 202 1) where the attacker aims to steal the policy network parameters, and poisoning attacks (Huai et al. 2020) that directly manipulate model parameters have been considered. In particular, optimization- based technique for identifying an optimal strategy for poisoning the policy network is proposed in (Hual et al. 2020
13

---

Published as a conference paper at ICLR 2024
B.3 BACKDOOR ATTACKS IN RL
Recent work investigating defenses against backdoor attacks in RL also considers recovering true states to gain robustness (Bharti al. 2022). However, there are important differences between our work and (Bharti et al., 2022]. First, our work contains two important parts that (Bharti et al.) 2022) does not have, which are the maximin formulation and belief update. The former allows us to obtain a robust policy by making fewer assumptions about attack behavior compared to (Bharti et al. (022). Note that this approach is unique to state-per cette-eeturbation attacks, as it is difficult to define a worst-case scenario for backdoor attacks. The latter is crucial to combat adaptive perturbations that can change the semantic meaning of states, which can potentially be very useful to backdoor attacks as well. Second, our Lipschitz assumptions differ from those in (Bharti et al., 2022). We assume that the reward and transition functions of the underlying MDP are Lipschitz continuous while Bharti et al. (2022) assume that the backdoored policies are Lipschitz continuous.
B.4 PARTIALLY OBSERVABLE MDPS
As first proposed by Astrom et al. 1965). Partially Observable MDP is generalization of an MDP where the system dynamics are determined by an MDP, but the agent does not have full access to the state. The agent could only partially observe the underlying state that is usually determined by fixed observation function O. POMDPs could model lot of real-life sequential decision-making problems such as robot navigation. However, since the agent does not have perfect information about the state, solutions for POMDPs usually need to infer a belief about the true state and find an action that is optimal for each possible belief. To this end, algorithms for finding a compressed belief space in order to solve large state space POMDPs have been proposed (Roy et al., 2005). State-of-the-arr solutions approximate the belief states with distributions such as diagonal Gaussian (Lee et al. 2020a),
Gaussian mixture (T'schiatsheek et al. 2018), categorical distribution (Hafner et al. (021) or particle filters (Ma et al. 2020). Most recently, a flow-based recurrent belief state modeling approach has been proposed in (Chen et al. 2022) to approximate general continuous belief states.
The main difference between POMDPs and MDPs under state adversarial attacks is the way the agent's observation is determined. In a POMDP, the agent's partial observation at time step is determined by a fixed observation function O, where oe = (ss,, at). And it is independent of the agent's policy æ. Instead, in an MDP under state adversarial attacks, a perturbed state is determined by the attack policy w, which can adapt to the agent's policy æ in general.
B.5 RL FOR STACKELBERG MARKOV GAMES
Previous work has studied various techniques for solving the Stackelberg equilibrium of asymmetric Markov games, with one player the leader and the rest being followers. Kononen (Könönen 2004) proposes an asymmetric multi-agent Q-Learning algorithm and establishes its convergence in the tabular setting. Besides value-based approaches, Fiez et al. (Fiez al., 2020) recently investigated sufficient conditions for a local Stackelberg equilibrium (LSE) and derived gradient-basee based learning dynamics for Stackelberg games using the implicit function theorem. Follow-up work applied this idea to derive Stackelberg actor-critic (Zheng et al.) 2022) and Stackelberg policy gradient (Vu et al. 2022) methods. However, all these studies assume that the true state information is accessible to all players, which does not apply to our problem.
B.6 MORE DETAILS ABOUT DIFFUSION-BASHE DENOISING
In DDPM model, the forward process constructs discrete-time Markov chain as follows. Given an initial state Xy sampled from g-). ). it gradually adds Gaussian noise to X to generate a sequence of noisy states X1 X where q (x; xx-1) := N (x;; /1 3,,,-1, B,I) so that X approximates the Gaussian white noise. Here 3; is precalculated according to a variance schedule and I is the iden- tity matrix. The reverse process again a Markov chain that starts with ж sampled from the Gaussian white noise (0, I) and learns to remove the noise added in the forward process to regenerate q(-). This is achieved through the reverse transition pe (x:-1 x2) := N (x;-1: [4g (x,,). Eg (x,, i)) where 0 denotes the network parameters used approximate the mean and the variance added in the forward process. As mentioned in the main text, we modify the reverse process by starting from perturbed state instead of xx, where is pixel-wise noise sampled from Gaussian
14

---

Published as a conference paper at ICLR 2024
81
90
$0
a0
Figure 3: True, perturbed, and worst-case states in Algorithm I and belief update. Beginning with true state and perturbed state So, the agent will have initial belief. i... the ball centered šo. After taking action do- belief is updated to the region marked by purple ball. When observing the next perturbed state 81, agent will update belief by taking the intersection of the purple ball and the green ball.
(a) Original
(b) Perturbed
Figure 4: An example of valid vs. invalid states in Pong.
distribution Wi0, 2)). 2. We then take reverse steps with k < K, according to the observation that perturbed state only introduces small amount of noise to the true state due to the attack budget We observe our experiments that using large does not hurt the performance, although increases the rumning time (see Figures 5d
and 5e in Appendix F.3
The progressive distillation diffusion model (Salimans Ho 2022) can distill an N steps sampler to new sampler of N/ /22 steps with little degradation of sample quality. Thus with 1024 step sampler, we could generate 512 step, 256 step, and step samplers. Notice that a single reverse step in an 8 step sampler will have equivalent effect of sampling multiple steps in the original 1024 step sampler. By choosing a proper sampler generated by progressive distillation (we report every model used in [.2 could accelerate diffusion process while preserving sample quality the same time.
C MORE GRAPHS AND EXAMPLES
C.I AN EXAMPLE OF BELIEF UPDATE
Figure fillustrates the relations between true state 8, the perturbed state 3, and the worst-case state 3 E (s) for which the action is chosen.
C.2 AN EXAMPLE OF INVALID STATES IN PIXEL-WISE PERTURBATIONS
For example, the white bar shown in Figure in the Atari Pong game will not change during gameplay and has grayscale value of 236 255. However, pixel-wise state perturbation attack such as PGD with attack budget = 15/25% will change the pixel values the white bar to a range of 221 /55 251 /55 that the perturbed states become invalid.
15

---

Published as a conference paper at ICLR 2024
D PROOFS
D.I PROOF OF THEOREM 1
In this section, we prove Theorem Recall that 7 = Town. We first establish the Lipchitz continuity of Q* the Q-value when the agent follows policy и and the attack follows policy wx-
Lemma 1. Q" is Lipchitz continuous for any क i.e. Vs, E S.Va E A.
(s*(s,)) (*(ss fo s'1l
(3)
where Lo, = lp Rmax. S 1-y
Proof.
Based on the definition of the action value function under state perturbation, we have
Q (s.a) R(ss, a) + ( (5')
R(s, a) +
Thus.
(s - (s2,
= a|((s,,)) - R(s2, + Eese((P(ssssssi))e p(ss)ss a)) (s')l
< <(8(1, R((2, a) - Evss][
P(s'|s2. (s))
(2)
4.11s11 -s2ll + max,es V (
(())(s2,a))
(6)
Rmaz S1[p11s1 - s2ll
21,1131 - 82ll 1-7
S(4, + Ryaz (11p)lls1 s2
= -6 ||$1 821
where (a) follows from Assumption and (b) follows from Assumptions ]and 2 and the definition of Vg
Lemma 2. For Qu defined in Algorithm 3 the Bellman approximation error is bounded by
Rmaz 1-7
I Qn- aml0 S 2ee((1r + 1p
(4)
Proof.
11T*Qu Qntilloo
max AEA
R[ss a) P aEA
P Tn(wn. (s')))]
-Y max Σ P(s' s, ())asaa)mm@uuefee a) - (s, #n()))
aEd
<ymax max Qn (8', Qni(s' (s')) e'ES' aEA
Let = (s") denote the perturbation of the true state s' and and 5 denote the agent's 's action when observing 3 and the worst-case state in (z)) that solves the maximin problem, respectively. We then have
max min (s) oEAsEB.(s)
(5)
16

---

Published as a conference paper at ICLR 2024
where the first inequality is due the fact that s obtains the worst-case Q-value under action ä, across all states in (s') including s'. It follows that
117 - 1utillo SennalmmaxQu(ee aEA
(m(d',=(''))
Symaxi aanaaQu(ss' E'E dEA
max min Qn(s,a) sE
5y max s' S'ES,
1Qn(s',a)
min (n(s,a) sEB,(s)
(a)
S 7 max #' VEE,
(n)(s',a)
min (x(),a)) BE)
2
where (a) due to 11 - 8'11 S 6 and (b) follows from Lemma
Lemma 3. Given any policy म wa where is fixed policy, T is contraction.
Proof.
1 = max E (s ())))(( - ((((s Qa ( - (
AES
e'ES
max
7 1/ Q2(s'aa)
A'ES
=1 - 1211x
Thus, for any given policy म, T is a contraction.
With Lemmas 2 and 3. we are ready to prove Theorem ! Theorem 1. The gap between Q²= and Q* is bounded by
1 1+7
limsup l1 - *** 11x0 S
(1 7)
where 7n is obtained by Algorithm 3 and A = 20y(4, + 4p111
Rymn 1-7
Proof.
l|Q - Q"11 -|T00 T + 11 Qn - 1100
< 11"' T T*Q 110000000000 + 11 Qn - 7h Qn + 11 Qn - Q=' 11
- -
+ 1 - Qntillac + ^11Q, Q' + +1Q 2* |1ا
where (a) follows from Q' is the fixed point of T Q is the fixed point of T and the triangle inequality, and (b) follows from both T and 7 (for fixed T.) are contractions. This together with Lemma 2 implies that
2+11Q¹ - Qnlloo) +A 10 - QF= S
(6)
1-?
We then bound |Q- - 2o as follows
|Q 1l < 1 Q T Qnlllo 1T Qntilloo ~1 - Qulla + +A,
which implies that
A
limsup |Q" Qulloo I
(7)
n-
1-7
Plug this back in equation we have
1+7
limsupllQ Q 1l00 < - 71
(8)
n
where A -6 S T-7
17

---

Published as a conference paper at ICLR 2024
Q1
81
$2
$3
Q2
$1
$2
$3
a1
12
11
Q1
4
2
-2
22
12
10
2
42
4
0
-1
a3
12
03
-3
Table 3: A counterexample to Taawwr being a contraction
D.2 A COUNTEREXAMPLE TO TOOT BEING A CONTRACTION WHEN o Wa., IS NOT FIXED
Consider an MDP AS, where S (81, $2 83) and A = {a1: 02 az). Suppose that for any
8 E S and E A, P(sl|s (s)) sider the two Q-functions shown in 3 We have However, when 지 = m Way is derived from QI and π2 = m2 o Way is derived from Q2.
and P(s'|s. 1|Q1-IQQ1000 -2 = (82, a2) Q2 a2)l = 10.
for s' + 82, and (s) {81. 82, 83). Con-
| Q1 12
max Σ sES,
a) क (wa, (s'))) Q2(5', 72(wan (s')))
max 7Q (wxr (8')) Q2(x (W (s')))
sES,aEA
2 (122 Tı (w/ (s2)) Q2 Ty (Wir (s2)))
(0) 1/Q1(82 a1) Q2(82,
y x 11
())
10 = ||Q1 - Q21loc
where (a) is due to the fact that matter what (=(s)) ) is, Be (w((()2)) {si, 82, sz} S, which implies that тi (Wa, ($2)) argmax, min (5 = aj, and similarly, Tz 72(wno (82)) = a2; (b) holds when 7 > 10 II
Therefore, 7 owr, is not contraction.
D.3 APPROXIMATE STACKELBERG EQUILIBRIUM
As shown in Theorem 4.11 of (He et al. 2023), when the initial state distribution Pr(so) is known, there is an agent policy n² that maximizes the worst-case expected state value against the optimal state perturbation attack, that is
VT, ELEES Pr( own (80) 2 EagEs Pr(so) (8o)
In particular, when the initial state is fixed, an optimal policy that maximizes the worst-case state value (against the optimal state perturbation attack) exists. Let V*((s) denote this optimal state value. Note that V*((s) is obtained using different policy for different 8o. Then reasonable definition of an approximate Stackelberg Equilibrium is a policy и where its state value under each state 8g close to V (so). that is. VVoow (so) V*(s)) < A for some constant A. Note that this condition should hold for each state sp. Also note that we compare π with different optimal policy with respect each So, thus bypassing the impossibility result stated in Section 3.1
In the paper, we further approximated V*(su) by the optimal value without attacks and derived A in this simplified setting (Theorem [ However, we believe that the general definition given above presents a novel extension of approximate Stackelberg Equilibrium in the standard sense and it an interesting open problem derive policy that is nearly optimal under this new definition.
18

---

end 10 end Published as a conference paper at ICLR 2024
E ALGORITHMS
Algorithm 2: Belief Update
Data: Old Belief M,, action a, perturbed state 1-
Result: Updated Belief Mc+1
Initialize My to be empty
for s in M₁ do
for s' in S do if Pss'|s, a) * 0 then Add s' to M₁
end
end
end
M M. (e((++1 10 RETURN M,41
Algorithm 3: Pessimistic Q-Iteration
Result: Robust Q-function Q
Initialize Qo a) 0 for all S, a E A; for n = 0, 1, ... do
Update RL agent policy: vš (n)) argmax minser (5) Qn(,
Update attacker policy: Vs S, S,Wk, (s) argminge Qn(s, (5));
for & E do for a E A do
Qu+1(s, = R(s,a) P (()))
end
Algorithm 4: Belief-Enriched Pessimistic DQN (BP-DQN) Training. We highlight the difference between our algorithm and the vanilla DQN algorithm brown.
Data: Number of iterations T, trained vanilla Q network Qu PF-RNN belicf model Np. target
network update frequency Z, batch size D, exploration parameter
Result: Robust Q network Q,
Initialize replay buffer B, robust Q network Q = Qu. target Q network Q' = Qu. observation history Shis. action history Anisi
for = 0, I...,, do
Use PGD find the best perturb state s, that minimizes Q+ (s:)), where is derived
from Q, by taking greedy action;
M, = M, O (5));
Choose an action based on belief M, and Qr using e-greedy:
a, argmax,............ minma
minmeM M, Q (m, a) with probability d'; otherwise at is random
action;
Append & and d, to Shis and Abie and use belief model N, (Shis Ania) to generate M Execute action in the environment and observe reward R₁ and next true state $t41;
s141 is terminal state then
Reset Shis and Apis
10
end
Store transition (8t: (t, Re, 8 M,) in B;
12
Sample random minibatch of size D of transitions {st, az, R2, S141, M.} from B; for terminal 81+1
R,
Set y/4
R, + ymmamaa minn ('m,, d') for non-terminal 8;41
14
Perform gradient descent step to minimize Huber (E,y; Qr(,,aa)))
15
Update target network every Z steps;
end
19

---

Published as a conference paper at ICLR 2024
Algorithm 5: Belief-Enriched Pessimistic DQN (BP-DQN) Testing
Data: Trained robust Q network Qr, PFRNN belief model Np Initialize observation history Shis and action history Ahisi
for / 0.I,.., do
Observe the perturbed state 3t; i then
Mo = (5:):
end
Select action based belief M, and Q a, argmax pe mi Q (m, Append 8 and or to Shis and Apis and use belief model Np(Shis, Anis) to generate Met1; Execute action az in the environment;
end
Algorithm Iuffusion-Assistie Pessimistic DQN (DP-DQN) Training. We highlight the difference between our algorithm and the vanilla DQN algorithm in brown.
Data: Number of iterations T, trained vanilla Q network Qu. diffusion belief model Na. target network update frequency Z, batch size D, belief size Kg. exploration parameter é', noise
level Esp
Result: Robust Q network Qr
Initialize replay buffer B, robust Q network Q = Qu. target Q network Q' = Qui
for O.I.... do
Use PGD to find the best perturb state & that minimizes (r π ($:),, where æ is derived from Q, by taking greedy action;
Sample noise from Gaussian distribution (0, e pixel-wise with same dimension 86;
Use the diffusion belief model generate belief M, Na + Φ) of size Kd;
Select an actions based on belief M, and Q, using e-greddy:
a, = argmax,c. minme M. Q (m, a) with probability d'; otherwise at is random
action;
Execute action a, in environment and observe reward R; and next true state 8141;
Apply the reverse diffusion process to 8 and 84+1: 8 Na(se), 8641 Na(8641);
Store transition {t, ag, R2, $141, ] in B; Sample random minibatch of size D of transitions
{8), a,, R4, $141, M, from B:
Rs
for terminal 8
11 Set
R, + ym min Q'mm,a') for non-terminal 8441
12
Perform gradient descent step to minimize Huber(Eity (8 a)));
13
Update target network every Z steps:
end
Algorithm 7: Diffussin-AAsiisted Pessimistic DQN (DP-DQN) Testing
Data: Trained robust Q network Q,, diffusion belief model Na, noise level Co
for 1 O.I....?' do
Observe the perturbed state ăz;
Sample noise & from Gaussian distribution (0, < pixel-wise with same dimension Generate belief using the diffusion belief model M, Na(5; + o);
Choose an action based on belief M, and Q,: ag = argmax Min M, (m, a);
Execute action a; in the environment;
end
F EXPERIMENT DETAILS AND ADDITIONAL RESULTS
F.1 EXPERIMENT SETUP JUSTIFICATION
Although both the BP-DQN and DP-DQN algorithms follow our idea of pessimistic Q-learning the former is more appropriate for games with discrete continuous but low-dimensional state space
20

---

Published as a conference paper at ICLR 2024
such the continuous Gridworld environment, while the latter is more appropriate for games with raw pixel input such as Atari Games.
In the Gridworld environment, state perturbations can manipulate the semantics of states by changing the coordinates of the agent. In this case, historical information can be utilized to generate beliefs about true states. Following this idea, BP-DQN uses the particle filter recurrent neural network (PF- RNN) method to predict true states. In principle, we can also use BP-DQN on the Atari environments to predict true states through historical data. In practice, however, it computationally challenging to do so due to the high-dimensional state space (84 x 84) of the Atari environments. Developing more efficient belief update techniques for large environments remains an active research direction.
On the other hand, state perturbations are injected pixel-wise in state-of-the-ar attacks in Atari games. Consequently, they can barely change the semanties of true states Atari environments. In this case, historical information becomes less useful, and the diffusion model can effectively "purify" the perturbed states to recover the true states from high-dimensional image data. Although it is theoretically possible to use DP-DQN on the Gridworld environment, we conjecture that it is less effective than BP-DQN since does not utilize historical data, which is crucial to recover true states when perturbations can change the semantic meaning of states as in the case of continuous Gridworld. In particular, we observe that the distributions of perturbed states and true states are very similar in this environment, making it difficult to learn diffusion model that can map the perturbed states back to true states.
It is interesting direction develop strong perturbation attacks that can manipulate the semantics of true states for games with raw pixel input. As a countermeasure, we can potentially integrate diffusion-based state purification and belief-based history modeling craft a stronger defense.
F.2 EXPERIMENT SETUP
The continuous state Gridworld is modified from the grid maze environment in (Mal et al. 2020). We create 10 x 10 map with walls inside. There also gold and bomb in the environment where the agent aims to find the gold and avoid the bomb. The state space is a tuple of two real numbers in (0, 10) [0, 10) representing the coordinate of the agent. The initial state of the agent is randomized. The agent can move in 8 directions, which are up, up left, left, down left, down, down right, right, and up right. By taking an action, the agent moves distance of 0.5 units in the direction they choose. For example, if the agent is currently positioned at (z. y) and chooses to move upwards, the next state will be (z, y + 0.5). If the agent chooses to move diagonally to the upper right, the next state will be (æ + 0.5/ y + 0.5/ If the agent would collide with a wall by taking an action, it remains stationary at its current location during that step. The agent loses 1 point for each time step before the game ends and gains a reward of 200 points for reaching the gold and -50 points for reaching the bomb. The game terminates once the agent reaches the gold or bomb or spends 100 steps in the game. For Atari games, we choose Pong and Freeway provided by the OpenAl Gym (Brockman et al. 2016
Environments.
Baselines. We choose vanilla DQN (Mnih et al. 2015). SA-DQN Zhang et al. 2020a) and WocaR- DQN (Liang al. 2022) defense baselines. We consider three commonly used attacks to evaluate the robustness of these algorithms: (1) PGD attack Zhang et al. (2020a), which aims to find a perturbed state 5 that minimizes ((s, क (5)) and we set PGD steps n = 10 for both training and lesting usage; (2) MinBest attack (Huang et al. 2017), which aims to find a perturbed state 8 that minimizes the probability of choosing the best action under 8, with the probabilities of actions represented by a softmax of Q-values; and (3) PA-AD (Sun et al., 202I). which utilizes RL to find a (nearly) optimal attack policy. For each attack, we choose e E 0.51 for the Gridworld environment and e E (1/255, 1155,,/220 3/255, 15/255] for the Atari games. Natural rewards (without attacks) are reported using policies trained under = 0.1 for continuous state Gridworld and c = 1/255 for Atari games.
Training and Testing Details. We use the same network structure as vanilla DQN (nnih et al. 2015), which is also used in SA-DQN (Zhang et al. 2020a) and WocaR-DQN (Liang et al. 2022). We set all parameters as default in their papers when training both SA-DQN and WocaR-DON, For training our pessimistic DQN algorithm with PF- Re----N--aaeeee belief (called BP-DQN, see Algorithm 4
in Appendix [), we set Kip = [M, = 30, i..., the PF-RNN model will generate 30 belief states in each time step. For training our pessimistic DQN algorithm with diffusion (called DP-DQN, see
21

---

Published as a conference paper at ICLR 2024
Eny
Parumeter
1/255
PGD
3/255
15/255
1/255
<= 372M
MinBest
157235
17255
PA-AD
5726
15/255
noise 6o
3255
5/255
10/255
22155
32255
10225
Pong
reverse step
1
2
sampler step
128
61
128
128
128
32
61
61
32
noise
3/55
3/255
3/255
3/255
3255
3/555
3/255
3/255
32555
Freeway
reverse Mep
stmnpler stop
64
64
64
64
64
64
Table 4: Parameters Used to Test DP-DQN-F
Algorithm 6 in Appendix we set Kid = [M,] = 4, that is, the diffusion model generates 4 purified belief states from perturbed state. We consider two variants of DP-DQN, namely, DP-DQN-O and DP-DQN-F. which utilize DDPM and Progressive Distillation as the diffusion model, respectively. For DP-DON-O, we set the number of reverse steps to k = 10 for 1/255 3/ 3/255 and k: 30 for e = 15/255, and do not add noise e when training and testing DP-DQN-O. For DP-DQN-F, we set k 1, sampler step to 64, and add random noise with eg 5/255 when training DP-DQN-F. We report the parameters used when testing DP-DQN-F in Table 4 We sample C C' = 30 trajectories train PF-RNN and diffusion models. All other parameters are set as default for training the PF-RNN and diffusion models. For all other baselines, we train million frames for the continuous Gridworld environment and million frames for the Atari games. For our methods, we take the pre-trained vanilla DQN model, and train our method for another 1 million frames. All training and testing are done on a machine equipped with an 19- 1990KFF CPU and single RTX 3090 GPU. For each environment, all RL policies are tested in 10 randomized environments with means and variances reported.
F.3 MORE EXPERIMENT RESULTS
F.3.1 MORE BASELINE RESULTS
Tables 5a and 5b give the complete results for the continuous space Gridworld and the two Atari games, where we include another baseline called Radial-DQN (Oikarinen et al. (021), which adds an adversarial loss term to the nominal loss of regular DRL in order to gain robustness. We find that Radial-DON fails to learn a reasonable policy in continuous Gridworld as other regularization-base methods. However, Radial-DON performs well under small attack budget in Atari games but still fails to respond when the attack budget is high. Our Radial-DQU results for the Atari games were obtained using the pre-trained models (Oikarinen et al. 2021), which might explain why the results better than those reported in (Liang al. 2022).
PGD
MinBest
PA-AD
Environment
Model
Natural Reward
11.
0.5
0.5
0.5
IXQN
90.2
128
-3
182
137
35.9
GridWorld Continous
WocaR-DON
SA-DON
20.8
63
46 142
100 +-0
63.2 +
-..8 131
100 0
63.2-888
-100-1
-97.5
100 +
13.6
-7.88
61.2-+88
78.3
Radial-DONN
-100 =00000
96.1 12.3
96.1 + 12.3
-100
-100
100 2:0
-100
BP-IXN
171.011
177.2
(a) Continuous Gridworld Results
Eay
Moddl
Reward
Natural
1/255
PCD
8/255
115/200
1/256
MimBest
8/250
15/203
1/205
PA-AD
8/253
15/206
DQN
2110
2120
21 20:00
21 11200
11200
21100
2121
-19222
21.00
SA DQN
21
2::00
-2.8 0.4
21
2:0
21:20
21:00
18.7 2.6
20
Ponx
WocaR DUN
Kadial DQN
2110
21100
21
2
2::00
2::00
-21.2 2:0
0:0
21
21 2:0
2:::0
21::0
-21 2.1
-21.000
21:00
21:00
10.7 2:2.4
21 4:0
-1 0:0
10 0
DP-DQN- -0 (Dim)
0:3
109
108:200
197
199:200
19995
193
19.
19.993003
19:3008
DI-IXNN-F (Ouns)
0.4
20:
20.4::09
183
1.9
20.68:00 0.
20.4-008
21:0:::000
1..6
20.0
18/2= 1.8
51*00.1
0+00
0++.0
0-700
0.0
0-0
0+0
0.1
RA-DiN
30++00
90-0
90-00
0=:00
27.2 3-1
18.3 5.0
0-0
20.1 4.0
9.5
0++-0
Freeway
WoccR-DDNN
Ralial-DON
0.54
03.24:0044
31:2=006
05.4
314=003
21.6+11
21.6
20.6
35.4
2.5
0.5
=2.8 08
19.8
20.6+
21.
3.7
12.5++.3.
0..4
21.6
21.6
DP.DON-O (Cuns)
25.81111
2911 1.1
29:3
28.0 = 0.7
282
1.0
28.5
25. 1.8
2508
28.3
28.8 1.1
DI-I0NN-F (Ohrrs
51.2
300
68
30.
3022
30.6
1.2
30.8
S1.1
(b) Atari Games Results
Table 5: Experiment Results. We show the average episode rewards + standard deviation over 10 episodes for our methods and three baselines. The results for our methods are highlighted in gray.
22

---

Published as a conference paper at ICLR 2024
Prrt, 10:00
N
13
3.39
Party LE:55
311
(a)
(b)
(c)
(d)
(e)
Figure 5: a), b) and c) show the 22 distance between perturbed states and original states before and after purification under different attack budgets in the Pong environment using DDPM. d) shows the performance of DP-DQN-O under different diffusion steps in the Freeway environment under PGD attack with 15 25/255. e) shows the testing stage speed of DP-DQN- (measured by the number of frames processed per second) under different diffusion steps in the Freeway environment.
Training (hours)
Testing (FPS)
Training (hours)
Testing (FPS)
Environment
Model SA-DON
Environment
Model
GridWorld
3
607
SA-DON
38
502
Continous
WocaR-DON
3.5
721
Pong
WocaR-DON
50
BP-DQN (Ours)
0.6+1.447
192
DP-DQN-O (Ours)
1,5+18430
6.6
DP-DQN-F (Ours)
1+18+24
93
Table 6: Training and Testing Time Comparison. The training of our methods contains three parts: a) training the PF-RNN or diffusion model, b) training a vanilla DQN policy without attacks, and c) training a robust policy using BP-DQN, DP-DQN-O, or DP-DQN-F.
F.3.2 MORE ABLATION STUDY RESULTS
Diffusion Effects. In Figures 5c we visualize the effect of DDPM--bsed diffusion by recording the le distance between a true state and the perturbed state and that between a purified true state and the purified perturbed state. For all three levels of attack budgets, our diffusion model successfully shrinks the gap between true states and perturbed states.
Performance vs. Running Time in DP-DQN. We study the impact of different diffusion steps on average return of DP-DQN-O in Figure 5d and their testing stage running time in Figure 5e Figure [5d]shon shows the performance under different diffusion steps of our method in the Freeway environment under PGD) attack with budget = 15 255. It shows that we need enough diffusion steps to gain good robustness, and more di diffusion steps do not harm the return but do incur extra overhead, as shown in Figure(5e) [5]] where we plot the testing stage running time in Frame Per Second (FPS). As the number of diffusion steps increases, the running time of our method also increases, as expected.
On the other hand, as DP-DQN-F uses distilled sampler, it can decrease the reverse sample step k: to as small as I, which greatly reduces the testing time as reported in Table We report the performance results of DP-DQN-E in Table Tb and we find that DP-DQN-E improves DP- OP-DQN-O under small perturbations, but suffers performance loss in Pong under PA-AD attack and large perturbations. Further, DP-DON- has a larger standard deviation than DP-DQN in the Pong environment, indicating that DP-DQN-F is less stable than DP-DQN-O in Pong. We conjecture that the lower sample quality introduced by Progressive Distillation causes less stable performance and performance loss under PA-AD attack compared to DP-DQN-O that utilizes DDPM.
Training and Testing Overhead. Table the training and test-stage overhead of SA-DQN, WocaR- DQN, and our methods. Notice that the training of our methods consists of three parts: a) training the PF-RNN belief model or the diffusion model, b) training a vanilla DQN policy without attacks, and c) training a robust policy using BP-DQN, DP-DQN-O or DP-DQN-F. In the continuous state Gridworld environment, our method takes around 9 hours to finish training, which is higher than SA-DQN and WocaR-DQN But our method significantly outperforms these two baselines as shown in Table Ia In the Atari Pong game, our method takes about 50 hours to train, which comparable to WocaR-DQN but slower than SA-DQN. In terms of running time at the test stage, we calculate the FPS of each method and report the average FPS over 5 testing episodes. In the continuous Gridworld environment, method is slower but comparable SA- SA-DQN and WocaR-DQN due to the belief update and maximin search. However, in the Atari Pong game, our DP-DQN-O method is much slower than both SA-DON and WocaR-DQN. This is mainly due to the use of large diffusion model
23

---

Published as a conference paper at ICLR 2024
Enviromment
Model
Natural Reward
0.1
PGD
0.5
0.1
MinBest
0.1
PA-AD
K-03
Grddorldd Continous (Clkan)
BR-DQN
163
88
1144:114
1719
10.
GridWorld Continous
BP-DQN
102 + 110
101 5 + 108
56 + 135
79.3
126
90.7 138
78.6 125
+3.1++100
(a) Continuous Gridworld Results
MinBest
L- 17205
572th
15:20
12205
322t
Freeway (Clean)
Freeua
DIDQNEF
28.4
2.5+0.1
2015
(b) Atari Games Results
Table 7: Noisy Environment Results. We show the average episode rewards + standard deviation over 10 episodes for methods trained in noisy environment.
in our method. However, our DP-DQN-F method is around 13 times faster than DP-DQN-O and is comparable to SA-DQN and WocaR-DQN.
Noisy Environment Results. Existing studies (including all the baselines we used) robust RI. against adversarial state perturbations commonly assume that the agent has access to a clean environment the training stage. This is mainly because an RL agent may suffer from significant amount of loss if has to explore poisoned environment on the fly, which is infeasible for security- sensitive applications. However, it an important direction to study the more challenging setting where the agent has access to a noisy environment only, and we have conducted a preliminary investigation. We assumed that the agent could access small amount of clean data (30 episodes of clean trajectories were used in the paper) to train a belief model or diffusion model. Note that learn the diffusion model, we only need set of clean states but not necessarily complete trajectories. We then trained an RL policy in poisoned environment by modifying the BP-DQN and DP-DQN algorithms as follows. For BP-DQN, we changed line 11 of Algorithm (in Appendix E) to store the average of belief states (obtained from the perturbed states) instead of the true states in the replay buffer. For DP-DQN, we changed lines and of Algorithm the frftusiio-bbseed purification against PGD-poisoned continuous Gridworld and Freeway environments, with an attack budget of 0.1 and 1/255, respectively, and then tested them in the same environment. The results are shown in Table 7a and (76] Although our algorithms suffer from a small performance loss when the training environment noisy, they can still achieve high level of robustness under all test cases.
Appendix [ to apply perturbed states instead of true states. We trained these policies
24


Reviews:
[{"review_id": "mcRQltYSgH", "reviewer": "Reviewer_QHWx", "summary": "This paper proposes two new algorithms to robustify agent policies against adversarial attacks. It formulates the problem of finding a robust policy as a Stacleberg game (where agents choose policies), and then further incorporates beliefs into the derived algorithm. For pixel-based observation spaces, the game uses a diffusion-based method to derive valid possible states. The paper is very well structured and easy to follow.", "questions": "see weaknesses", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- the paper addresses many shortcomings of current works\n- the theoretical algorithms and derivations are insightful\n- the practical implementation of the derived algorithms are well motivated", "weaknesses": "- the paper assumes that both the clean MDP and the perturbation budget are known to both the victim and the attacker\n- it would be interesting to run an ablation on these assumptions. How well does the method work if the budget is not known exactly, or if the MDP transition function is not known exactly?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7T2OU6u2pH", "reviewer": "Reviewer_achV", "summary": "The authors study the problem of defense in presence of perceived state attack in Reinforcement learning and propose a method to approximately solve the Stackelberg equilibrium between the agents and the adversary. Their method involves solving pessimistic Q-learning and estimating belief state of the agent and using them for state purification. They propose two algorithms called BP-DQN and DP-DQN to defend against adversarial attacks.", "questions": "1. It is well known that defense against perceived state attack requires solving a partially observable MDP which is a hard problem to solve in general. Could you clarify how your method is able to avoid these hardness issues?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. Proposes a novel method to defend against adversarial attacks in RL by combining pessimistic Q-learning with belief state estimation and state purification objective.\n    \n2. Authors provided theoretical results to compare the policy found by their algorithm to the optimal policy.\n    \n3. Presented interesting empirical experiments to demonstrate effectiveness of their algorithm on several examples.", "weaknesses": "1. It has been shown that Stackelberg Equilibrium as defined in Definition 2 need not always exist, refer to theorem 4.3 [https://arxiv.org/pdf/2212.02705.pdf](https://arxiv.org/pdf/2212.02705.pdf). So, finding an approximate solution for them is meaningless. However, non-existence of Stackelberg equilibrium is a worst case phenomenon. Authors should incorporate this in their paper.\n    \n2. It will be great if authors can include a short paragraph before section 3.2 discussing a big picture of their strategies before diving into each one of them. It would also help to include some mathematical details in each section.\n    \n3. Abstract wrongly mentions that past methods either regularize or retrain the policy. However, methods like Bharti et.al. just purify the states directly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UwfCirMikx", "reviewer": "Reviewer_GsDy", "summary": "The paper introduces a novel RL algorithm that aims to protect RL agents from adversarial state perturbations. The authors propose a pessimistic DQN algorithm that takes into consideration both the worst-case scenarios and belief about the true states. The algorithm also features a diffusion-based state purification method for applications like Atari games. The paper shows empirical results demonstrating that their approach significantly outperforms existing solutions in robustness against strong adversarial attacks, while maintaining comparable computational complexity.", "questions": "1. How sensitive is your algorithm to the choice of hyperparameters?\n2. Given the requirement for a clean training environment, how would your method perform in a scenario where such an environment is not readily available?\n3. The diffusion model increases computational complexity during the test stage. Are there ways to optimize this without compromising the robustness?\n4. Why PA-AD is not evaluated on continuous gridworld?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The empirical results show performance improvement under strong attacks compared to baseline methods. The algorithm works well for both simplistic environments and more complex scenarios like Atari games with raw pixel input.\n2. The algorithm's computational overhead is comparable to existing methods that use regularization terms.", "weaknesses": "1. The algorithm assumes access to a clean environment during training, which may not always be the case in real-world applications.\n2. While the diffusion model adds robustness, it also adds computational overhead, potentially making it slower at test time.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KOZahWTXUL", "reviewer": "Reviewer_cDHy", "summary": "This paper addresses the vulnerability of reinforcement learning agents to adversarial attacks by manipulating state observations. The authors propose a algorithm focusing on developing a pessimistic policy that accounts for uncertainties in state information. This is supplemented by belief state inference and diffusion-based state purification techniques.", "questions": "How extensive or generalizable are the empirical results presented? Given that the study focuses on the Continuous Gridworld, which is relatively simple, and only includes two Atari games. \n\nConsidering that Atari game screens are depicted using 8-bit (256 levels) RGB, yet typically select colors from a narrower palette, how effective are the different attack budgets (15/255, 3/255, 1/255) tested in this study? Specifically, can these perturbations alter the colors enough to cause confusion with other colors in the game's limited palette? If not, could the observed robustness of the learning method simply be a consequence of learning to filter out specific colors?\n\nIs the proposed method also applicable to environments like Mujoco or Mountain Car, where the input variables are more continuous and less discrete than those in Atari games?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Addressed an important problem in Reinforcement Learning, providing fresh perspective and insights.\nThe experimental design and methodology are well-constructed.", "weaknesses": "The innovative aspects presented over WocaR-DQN appear to be incremental in nature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)