Beyond Worst-case Attacks: Robust RL with Adaptive Defense via Non-dominated Policies
Authors: Xiangyu Liu
Chenghao Deng
Yanchao Sun
Yongyuan Liang
Furong Huang
Venue: ICLR 2024 spotlight (2024)
Keywords: robust reinforcement learning; beyond worse-case
Primary area: reinforcement learning
TL;DR: We developed a general framework to improve victim performance against attacks beyond worst-case scenarios while maintaining robustness against worse-case attacks.

Abstract: In light of the burgeoning success of reinforcement learning (RL) in diverse real-world applications, considerable focus has been directed towards ensuring RL policies are robust to adversarial attacks during test time. Current approaches largely revolve around solving a minimax problem to prepare for potential worst-case scenarios. While effective against strong attacks, these methods often compromise performance in the absence of attacks or the presence of only weak attacks. To address this, we study policy robustness under the well-accepted state-adversarial attack model, extending our focus beyond merely worst-case attacks. We first formalize this task at test time as a regret minimization problem and establish its intrinsic difficulty in achieving sublinear regret when the baseline policy is from a general continuous policy class, $\Pi$. This finding prompts us to \textit{refine} the baseline policy class $\Pi$ prior to test time, aiming for efficient adaptation within a compact, finite policy class $\tilde{\Pi}$, which can resort to an adversarial bandit subroutine. In light of the importance of a finite and compact $\tilde{\Pi}$, we propose a novel training-time algorithm to iteratively discover \textit{non-dominated policies}, forming a near-optimal and minimal $\tilde{\Pi}$, thereby ensuring both robustness and test-time efficiency. Empirical validation on the Mujoco corroborates the superiority of our approach in terms of natural and robust performance, as well as adaptability to various attack scenarios.

Published as a conference paper at ICLR 2024
BEYOND WORST-CASE ATTACKS: ROBUST RL WITH ADAPTIVE DEFENSE VIA NON-DOMINATED POLICIES
Xiangyu Liu 1 Chenghao Dengi', Yanchao Sun', Yongyuan Liang', Furong Huang' Universiiy of Maryland, College Park, PJ.P. Morgan Al Research {xyliu999) @uudd. edu
ABSTRACT
In light of the burgeoning success of reinforcement learning (RL) in diverse real- world applications, considerable focus has been directed towards ensuring RL policies are robust to adversarial attacks during test time. Current approaches largely revolve around solving minimax problem to prepare for potential worst- case scenarios. While effective against strong attacks, these methods often com- promise performance in the absence of attacks the presence of only weak at- tacks. To address this, we study policy robustness under the well-accepted state- adversarial attack model, extending our focus beyond only worst-case attacks. We first formalize this task at test time as a regret minimization problem and establish its intrinsic hardness in achieving sublinear regret when the baseline policy is from a general continuous policy class, IT. This finding prompts us to refine the base- line policy class IT prior to test time, aiming for efficient adaptation within a finite policy class II, which can resort to an adversarial bandit subroutine. In light the importance of a small, finite II, we propose a novel training-time algorithm to iteratively discover non-dominated policies, forming a near-optimal and minimal II, thereby ensuring both robustness and test-time efficiency. Empirical validation on the Mujoco corroborates the superiority of our approach in terms of natural and robust performance, as well as adaptability to various attack scenarios.
INTRODUCTION
With increasing surge of successful applications powered by reinforcement learning (RL.) on robotics (Levine et al. 2016 Ibarz et al.] [202I), creative generation (OpenAI, 2023). etc, its safety issue has drawn more and more attention. There has been a series of works devoted to both the attack and defense aspects of RL (Kos & Song 2017: Huang et al. 2017, Pinto et al., 2017 Lin al. 2019bb Tessler et al., 2019 Gleave et al. 2019). Specifically, the vulnerability of RL policies has been revealed under various strong threats, which in turn facilitates the training of deep RL policies by accounting for the potential attacks to boost the robustness.
Existing approaches aimed at principled defense often prioritize robustness against worst-case at- tacks (Tessler et al.) 2019 Russo & Proutiere| [019 /hhng al., 202T) [unn et al. 2021 Liang et al.) 2022). focusing on the optimal attacker policy within potentially constrained attacker policy space. Such focus can lead to suboptimal performance when RL policies are subjected to no or weak at- tacks during test time. Real-world scenarios often diverge from these worst-case assumptions for several reasons: (1) Launching an attack against an RL policy might first require bypassing well- protected sensors, thus constraining the attack's occurrence in terms of time steps and its intensity. (2) Previous studies (Zhang et al.] 2021 [Sun et al. (02T)) have highlighted the intriguing difficulty of learning the optimal attack policy. particularly when attackers are constrained by algorithmic efficiency or computational resources. Given these practical considerations and the prevalence of non-worst-case attacks, we pose and endeavor to answer the following question:
Is it possible develop a comprehensive framework that enhances the performance of the victim against non-worst-cae case attacks, while maintaining robustness against worst-case scenarios?
1 Equal contribution. Codes available http://gghiiiiiommmmmmmmaaaaaaag

---

Published as a conference paper at ICLR 2024
Non-Dominated Policy Class fl
Agent
Ile.v">
Tor.y">
Jot
ABV
Ads
Iterative Discovery of Non-dominated Policies in Pre-training
Test-time Ontine Adaptation
Figure I: Diagram of our PROTECTED framework. During training, we iteratively discover non- dominated policies, forming a finite policy class II. The blue area delineates the reward landscape for victims against attackers, denoted {JJ(T, v²), x²)) E I].. Here, only attackers are visualized for clarity. The orange area, on the other hand, represents the space of policies that are "dominated" by the discovered policy class ПI. Dominated policies are those that are outperformed by at least one (mixed) policy in II across the specified range of attackers. We refer to $C for more detailed explanations. During test time, online adaptation mechanisms are activated to adjust the weight of each policy in response various attack scenarios adaptively.
To address these challenges, we introduce PROTECTED, which stands for pre-training non- dominated policies towards onling adaptation. In this work, the terms 'pre-training' and 'training' used interchangeably. At test time, rather than deploying single static policy, PROTECTED maintains of policies, denoted II, and adaptively updates the weight of each policy based on interactions with the attacker minimize regret. Before that, during training, a finite Il is con- structed by iteratively discovering non non-dominated policies, ensuring optimal defense against un- known attackers. In summary, our contributions encompass both training and online adaptation phases under the prevailing state-adversarial attack model:
>> (1) Online adaptation. We formalize the problem of online adaptation and introduce regret minimization the objective. We also highlight the inherent difficulty in achieving sublinear regret, advocating for refined policy class II for online adaptation.
D (2) Non-dominated policy discovery during training. For training, we characterize the opti- mality of πl and propose an algorithm for iteratively discovering non-dominated policies. This results in a IT that is both optimal and efficient for online adaptation, subject to certain mild conditions. Meanwhile, we also reveal the fundamental hardness of our problem that there are problem instances requiring a relatively large II achieve near pear-optimality.
(3) Empirical investigations. Through empirical studies Mujoco, validate the effective- ness of PROTECTED demonstrating both improved natural performance and robustness, as well adaptability against unknown and dynamic attacks.
By investigating defenses against attacks beyond worst cases, we hope this work paves the way for the development of more practical defense mechanisms against broader range of attack scenarios.
2 RELATED WORKS
JStasaraadversariaal attacks on deep RL. Early research by Huang et (2017 exposed the vul- nerabilities of neural policies by adapting adversarial attacks from supervised learning to RL. Lin al. (2019h) focused on efficient attacks, perturbing agents only at specific time steps. Following these works, there have been advancements in stronger pixel-based attacks (Qiaoben et al.) [202]] Pattanaik et al.) 2017 Oikarinen et al. 2020 Zhang et al. (2000)) introducing the theoretical framework SA-MDP for state adversarial perturbations and suggesting corresponding regularizer for more robust RL policies. Building upon these, Sun et al. (2021) refined the framework to PA- MDP for improved efficiency. Liang et al. 2022) further improved the efficiency of defense by introducing the worse-case Q function, avoiding the alternating training. Those works as mentioned before aim improving the robustness against worst-case attacks. Havens et al. (2088) also dealt
2

---

Published as a conference paper at ICLR 2024
with the adversarial attacks for RL in an online setting, where it focuses on how to ensure robustness in the presence of attackers during RL training time.
Online learning and meta-learning. During the test phase, framework equips the victim with the capability to adjust its policy in response to an unknown or dynamically changing attacker. This is achieved through the utilization of feedback from previous interactions. In the literature, two distinct paradigms have been advanced to examine how an agent can leverage historical tasks or ex- periences inform future learning endeavors. The first paradigm, known as meta-learning (Schmid-) huber 1987 Vinyals et al. 2016 Finn et al. 2017), conceptualizes this as the task of "learning to learn. In meta-learning, prior experiences contribute to the formulation of prior distribution over model parameters or instruct the optimization of a learning procedure. Typically, in this frame- work, collection of meta-training tasks is made available together upfront. There are also works extending meta-learning to deal with the streaming of sequential tasks (Finn et al., 2019), which however require task-specific update subroutine. The second paradigm falls under the rubric of online learning (Hannan 1957: Cesa-Bianchi & Lugosi, 2006), wherein tasks-or in the context of our paper, attackers- are disclosed to the victim sequentially via bandit feedback. Extensive lit- erature has been devoted to the subject of online learning, targeting the minimization of regret in either stochastic settings (Lattimore & Szepesvári, (2200; Auer 2002, Russo & Van Roy 2016) or adversarial settings (Auer 20.| Neu 2015; Jin al. | 2020p. Our work primarily aligns with the latter paradigm. However, existing methodologies within this domain generally permit only re- ward functions to change arbitrarily, which is called the adversarial bandit problem or adversarial MDP problem. In contrast, our scenario permits the attacker to introduce partial observability for the victim, thereby also influencing the transition dynamics from the perspective of the victim.
3 PRELIMINARIES
In this section, we adopt the similar setup and notations as existing works ZZhngg et al. 2021 jt al. 202T]] Liang et al. 2022).
Sun
MDP and attacker model. We define Markov decision process (MDP) as
M
(8, A, T, (,,,r, where S is the state space, A the action space. T S x A + ASS) de- notes the transition kernel, μ1 E ASS) is the initial state distribution, T4 S x A - [0, is the reward function for each h E [H]. Given an MDP M. at each step h, the attacker sees the true state 8h S and selects perturbed state šn S in a potentially adversarial way. Then the victim only sees the perturbed state 8n instead of the true Sy and takes the corresponding action as E A. The goal of the victim is maximize its expected return while the attacker attempts to minimize it.
Policy and value function. We define the deterministic attacker policy v = (MN]NE(H) with 2/2 : S + S for any h E [H] and denote the corresponding policy space as ydet_ We also consider constraints on the attacker, where for any s, the attacker can only perturb to some 3 B(s) C S, e.g., (s)) can be the 1p ball. We allow randomized policies for the attacker and the policy space is denoted as V == A(Vder). For any y V, we adopt the representation that is conditioned on random seed 2 E Z sampled at the beginning of each episode from fixed probability distribution P(z). For the victim, we denote history Tn at time h as {8), a1, $2, 42 S.} and T as the space for all possible history at all steps. We consider πI as the corresponding policy space. Finally, we use πīder to denote deterministic victim policies. Given the victim policy æ and attacker policy v, the value function for the victim is defined as: J(T, v) (E) 88 ,98 )uppl (T. Tr.) E F' (8h, an)].
victim policy x T ((A) and
THE PROTECTED FRAMEWORK
4.1 ONLINE ADAPTATION FOR ADAPTIVE DEFENSES
Before delving into our approach of online adaptation for adaptive defenses, it essential to review the limitations of existing works concerning the trade-off between natural rewards and robustness. Then we discuss the necessity of an adaptive defending policy. Existing researches generally focus on worst-case performance, formally characterized as follows:
3

---

Published as a conference paper at ICLR 2024
Definition 4.1 (Exploitability). Given victim policy π, exploitabilityy is defined by: Expl(T) = max min J(x' (T'L,) min J(T, v).
x x'ell WEV
wEV
Existing works aim to obtain policy x² that minimizes exploitability, i..., n² E arg ming Expl(r), during the training phase to defend against worst-case or strongest attacks. Such a trained policy, x², is then deployed universally at test time. However, this approach can be overly cautious, com- promising performance under no or weak attacks (Zhang et al., 2021 Sun et al.] [202I). To address this limitation, we propose to consider new metric for test-time performance:
Definition 4.2 (Regret). Given T total episodes at test time, the start of each episode t, the victim selects a policy x² from II based on reward feedback from previous episodes, and the attacker selects an arbitrary policy v² V. The regret is defined as
Regret (T) = max
Σ xEll
J((
(4.1)
Therefore, instead of employing static victim policy, x², designed to minimize exploitability, we propose adaptively selecting {*" hetr during test time, based on online reward feedback, to minimize regret. Once the adaptively selected victims, het)) ensure low regret, the performance against either strong or weak (or even no) attacks is guaranteed to be near-optimal. While such an objective could ideally provide way to defend against non- worst-case attacks, unfortunately, turns out that there are no efficient algorithms that can always guarantee sublinear regret.
Proposition 4.3. Fix a E [0.1) 1). There does not exist an algorithm that produces a sequence of victim policies (x het( such that E(Regrett = poly(S, A, HYT for any {u' IEE[T)-
Remark 4.4. On the downside, Proposition 4.3 remains valid even when the attacker's 's actions are constrained such that [B(s]] = 2 and s E Bix) for each s E S. However, there is a silver lining: in the hard instance we constructed, the attacker must perturb a state 8 to another state 8 such that both the transition dynamics and the reward function differ greatly between s and 8. Therefore, if real-world scenarios impose constraints such as ||s 81| S e fforr some e in continuous control tasks, and if the transition dynamics and reward function are locally Lipschitz Proposition 4.3 may not apply. Further investigation of this avenue is left for future work.
The earlier negative results inform us to focus on online adaptation within a smaller, finite policy class II, rather than the broader class II. Specifically, in Equation 4.1 {x' heeerrr and the best policy in hindsight in Definition 4.2 belongs to rather large general policy class IT. Therefore, by relaxing the regret definition to ensure the baseline policy и to come from a smaller and finite policy class II C II, achieving sublinear regret becomes possible. This can be done by treating each policy in IT as one arm and running an adversarial bandit algorithm, e.g., EXP3 (Bubeck et al. 2012 Meanwhile, it is worth noting that if the test-time attacker unknown but fixed, stochastic bandit algorithms like UCB can be also effective. Given such a refined policy class II, we can perform online adaptation as in Algorithm which maintains a meta-policy w' E (iI during online adaptation and adjusts the weight each policy based on the online reward feedback. The key is that the victim should randomize its policy by sampling from II, following the distribution w' at the start of each episode t. Formally, such an algorithm ensures the guarantees for a relaxed definition of regret, following the analysis EXP3.
Proposition 4.5 (Bubeck et al. 2012). ). Given Îī S II with [ < cc, we define Regret (T) = m Σím (J(z, J(m v²)) for any T E N, {nr hee), (v' hem-- Algorithm ducing {m²) heey enjoys the guarantees R[egre (T))/T S 2H
for pro-
log [ T
Finally, we remark that the adaptation method used here is computationally efficient as it only main- tains and updates the vector w' E Rl rather than fine- tin-ttnnng a policy network (or its last layer). This makes it more suitable for scenarios where computational budgets are limited test time.
Regret depends on the specific attackers {2* 1e")e However, we omit such dependency in Regret(T)) for notational convenience since both the regret upper hound of interest for our paper and the literature of online learning and adversarial bandit (Hazan et al. 2016 Lattimore & Szepesvári 2020) will he for any {v/ hejrj-
4

---

Published as a conference paper at ICLR 2024
Algorithm Online adaptation with refined policy class
Input: I1, 17 Initialize w E AlI) to be the uniformly random distribution.
for L E [T] do
Draw n' ~'
sampling randomly
Execute T² in the underlying environment and observe total rewards Rº (x*))
> th
-H
for π E IT do
w (+) f
Ex'ch 8 2omt mar where (TT)
2" (m)
I²' (m) ="()) am for E [1]
end for end for
4.2 PRE-TRAINING FOR NON- NON-DOMINATED POLICIES VIA ITERATIVE DISCOVERY
The analysis above inspires us discover refined policy class, II, during training. At test time, the relaxed definition, (egret(T)), with respect to the refined policy class TT can be efficiently mini- mized. However, the gap between Regret and Regret(T)) can be significant when policies in II are suboptimal, meaning that policies from IT II could provide much higher rewards against some attacks. Consequently, we introduce the following definition characterize the optimality of IT.
Definition 4.6. For given policy class ÎI, we define the optimality gap between ĪI and II as
Gap(ii, II) == max DEV
max J( v) max J( J(T( .1)) FEll
a'ell
This definition implies that we have Gap( S e, then whatever policy the attacker uses, can relate the two notions of regret. Proposition 4.7. Given II. it holds that for any T e N, { hemm and (v' hee(T]
optimal policy in II is also e-optimal in I1. With this quantity, we can
Regret(T (T)
(egret(T)
+ GT,
T
T
If [T < oc, Algorithm satisfies E (T)egrot(T))/TT < 2H
i log
+ Ga, II).
T
According to this proposition, there is a clear trade-off between optimality, i.e., Gap II). and efficiency, i.e., [T]. A natural question arises: can we achieve small Gap(II, II) while IT is finite? Indeed, we answer this in the affirmative.
Proposition 4.8. There exists TI such that GT, IT) = 0 while [M| < co.
This confirms that we can always find an optimal IT with finite cardinality, enabling the execution of Algorithm However, [i] in our construction is contingent on the deterministic policy set, which is relatively large. This indeed arises because optimal IT can also encompass many redundant policies. Removing these redundant policies from Il does impact its optimality. To characterize such redundant policies, we define dominated policies as follows.
Definition 4.9 (Dominated and Non-dominated Policy). Given 8 2 and Î.. We define (5, (I. dominated policy & II as that there exists some w E (iII, for any V. J(T.)) < [J(T', v)] + 5. For = O, we also say π is dominated by ĪI. If a not a (0, \ {x})- dominated policy, we say is a non-dominated policy (w.r. IT).
It's clear that for (8, III domminatt policy i.c. min max, (J(z - Egrow [J(T' < 5, including in IT allows the optimality gap decrease by at most 8. With this principle,
5

---

Published as a conference paper at ICLR 2024
straightforward algorithm to construct small and optimal policy class is start from an optimal II (potentially with redundant policies), i.e., Gap IT) O, and then enumerate all IT to examine whether и is dominated by I т. If it is true, one can remove a from to reduce its cardinality. This process is akin to (iterated) elimination of dominated actions in normal-form games [Roughgarden] 2010).
While such procedures can maintain the optimality of fl and effectively reduce its cardinal- ity, the overhead of enumerating all π E II can be unacceptable. Consequently, a natural and more efficient approach is construct II from scratch by iteratively expanding II. Specif- ically, given II, any policy such that min max, (J v) - Ex' [J (T''v))) .v]]) > 8 be used to expand IT. Thus, propose to select the that maximizes this quantity min max, (J( [ v))) other words, at each iteration given IT {Ir, mh) already discovered, solve the following optimization problem:
π k+1
E arg max JEll ( ,))) NEY
min
max (J(x, - Ex' [J [ v))),
(4.2)
SK+1 = max fell WEA(( NEV
min
max (J(z, - Brrn v)])
turns out such an iterative process enjoys guarantees for both optimality and efficiency.
Theorem 4.10. For any δ >> O, there exists K N such that JK S 8. Correspondingly the policy class ITK {n² ... πk} satisfies that Gap(IIK III 8. Furthermore, have the regret K log K for Algorithm
guarantee that Reegrtt (T) s 2H
T
Moreover, let K = Gap [i| and KTn minkeN:fx= K, as long as our objective 4.2 admits unique solution at every iteration, our algorithm finishes within at most K - iterations, i.e, we have Kinn < K*
The first part of Theorem 4.10 implies that we can simply set error threshold and sequentially solve Equation until the optimal value is less than or equal to 5. Then, Theorem 4.10 predicts this process will always finish in finite iterations, thus leading to a finite II for any given 6. Once it converges, it is guaranteed that Gip II) < 8. In addition, the second part of Theorem 4.10 proves that, under mild conditions, once the algorithm discovers II such that the optimality gap is O, IT is guaranteed to be the smallest one.
Implications.
A practical algorithm. To solve the objective 4.2 and develop a practical algorithm, we leverage the fact by weak duality that
max fenl
min
max (J 1)) Enr [J(T' v)]) WEV
WEA(( (1))
max max Hell V WEA((F).....) ++}) (J(T, - Beinu ([t,
min
Therefore, propose optimize RHS, lower bound for the original problem, bringing two bene- fits: (1) the maximization for æ and v/ can be merged and updated together (2) the inner minimization problem is tractable. To solve RHS, follow the common practice for nonconcave-com mization problems, repeating the process of first solving the inner problem exactly, and then running gradient ascent for the outer Algorithm 2 Notably, the attacker y is not modeled as the worst-case to minimize the victim rewards anymore. For more intuitive illustration, we refer to the left part of Figure [
opti-
problem (Lin et al.) 2020). The detailed algorithm is presented in
Finally, to deepen the understanding of our problem and algorithm, we provide a negative result regarding ITT.. In Theorem 4.10) we have not shown how tii explicitly depends on 8 or other problem parameters (S, A, H). Indeed, this is not caveat of our algorithm or analysis. We point out in the following theorem that, for some problems, must be large to be near-optimal.
Theorem 4.11. There exists an MDP with S = 2, A = 2 such for any [IT| < 2 we must have GT, IT > +-

---

Published as a conference paper at ICLR 2024
Algorithm 2 Iterative discovery of non-dominated policy class
Input: 8, 21, 12, N
Initialize II < { k 1, fk + 00 for 1. K iterations do Initialize x *++10 v0, + 0, and fk+1 t- iterations do
for f = 1.
k- <- arg [a [ v²)
D estimating accumulative rewards with samples
vt+ f D² V (r 1²) -[ ,(TT"",²)) updating with SA-RL (Zhang al.
2021 or PA-AD (Sun et al. 202T)
x x+,,011
122 V
x. ( (1tt, ,24)
updating with PPO
fi+11
J J xt1)) (xth", /
t- (+1+1
end for T ++] f T ++11
11 + I1 U U
end for
Nevertheless, this does mean the problem always intractable. As for concrete applications, possible that S& can still converge to small value quickly as increases. Therefore, we shall investigate how the cardinality of II affects empirical performance standard benchmarks. We remark that Proposition [.3 and Theorem [.11 reveal the fundamental hardness of our problem setting for test time and training time respectively.
4.3 How TO ATTACK ADAPTIVE VICTIM POLICIES OPTIMALLY?
Although our primary focus on developing robust victims against attacks beyond worst-case sce- narios, also explore how to attack adaptive vietim optimally. Existing works typically formu- late this as a single-agent RL problem, as the attacker usually targets only a single static victim in stationary environment. However, once the victim can adapt, the attack problem becomes more challenging. Since our focus is on developing robust victims, we consider a white-box attack setup, where the attacker is aware that the victim will be adaptive and will use the refined policy class II at test time. Consequently, its attack objective can be framed
min max B ((,,)((TT))) v), P WEA(l)
accounting for the fact that the victim can adaptively identify its optimal choice from II in response any arbitrary static attacker as per Proposition While this objective might seem formidable to solve, it turns out that existing works have already laid the groundwork for this problem. In this context, the inner problem can be solved tractably, and the outer minimization problem can be addressed by employing existing RL--based methods, such as SA-RI (Zhang et al. (202T) and PA- AD (Sun et al.) 2021). Consequently, we can repeat the process of solving the inner maximization first and then applying gradient update for the outer minimization problem (l.in et al. 2019a).
5 EXPERIMENTS
In this section, our primary focus is to explore the following questions:
D Can our methods attain improved robustness against non-worst-cass static attacks in comparison formulations that explicitly optimize for worst-case performance, while maintaining compa- rable robustness against worst-case attacks?
D Can our methods render better test-time performance against dynamic attackers through online adaptation compared to baselines deploying a single, static victim?
D> Are our methods capable of achieving competitive performance with reasonably small ii?
5.1 EXPERIMENTAL SETUP AND BASELINES
For empirical studies, we implement our framework in four Mujoco environments with continuous action spaces, specifically, Hopper, Walker2d, Halfcheetah, and Ant, adhering setup similar to

---

Published as a conference paper at ICLR 2024
Natural Reward
Environment
Model
Random
RS
SA-RL
PA-AD
ATLA-PPO
3291 + 600
3165 + 576
2244 + 618
1772 + 802
1232 + 350
Hopper
PA-ATLA-PPO
3449 + 237
3325 = 239
3002 + 329
1529 + 284
2521 # 325
state-dim: 11
WocaR-PPO
3616 + 99
3633 +: 30
3277 + 159
2390 + 145
2579 + 229
c=0.075
Ours
3652 108
3653 57
3332 713
2526 682
2896 723
ATLA-PPO
3842 475
3927 368
3239 294
3663 707
1224 + 770
Walker2d
PA-ATLA-PPO
4178 = 529
4129 + 78
3966 + 307
3450 + 178
2248 +: 131
state-dim: 17
WocaR-PPO
4156 + 495
4244 + 157
4093 + 138
3770 + 196
2722 + 173
c=0.05
Ours
6319 + 31
6309 + 36
5916 + 790
6085 + 620
5803 + 857
ATLA-PPO
852
6164 603
392
418
548
Halfcheetah
PA-ATLA-PPO
6289 + 342
6215 = 346
5226 + 114
4872 : 379
3840 + 273
state-dim: 17
WocaR-PPO
6032 + 68
5969 + 149
5319 + 220
5365 + 54
4269 + 172
e=0.15
Ours
7095 88
6297 471
5457 + 385
5089 86
4411 + 718
ATLA-PPO
5359 153
5366 104
4136 149
3765 101
338
Ant state-dim: 111
PA-ATLA-PPO
5469 + 106
5496 + 158
4124 + 291
3694 + 188
2986 + 364
WocaR-PPO
5596 + 225
5558 + 241
4339 + 160
3822 + 185
3164 + 163
c00.5
Ours
5769 290
5630 146
4683 + 561
4524 + 79
4312 + 281
Table 1: Average episode rewards + standard deviation over 50 episodes with three baselines on Hopper, Walker2d, Halfcheetah, and Ant. stands for the attack budget chosen to be the same as related works. We use [I]] for ours and discuss its choice later. Natural reward and rewards under four types of attacks are reported. Under each column corresponding to an evaluation metric, we bold the best results. And the row for the most robust agent highlighted as gray
Rewardk
WoeoR
390
WoocR PL-ITL
PA-TIA
PA-AILAA
4000
200
4940
2000
Texting
79
179)
17.9
550
19)
1791
17M
150
750
1791
174
Auaa (60)
112
2.4
0.5
1.0
00
02
2.4
1.6
01
114
150
(a) Natural
(b) Random
PA-AD
Figure 2: Online adaptation when facing unknown static attackers. It can be seen that the best policy can be identified quickly and reliably within 800 episodes or less against different attackers.
most related works (Zhang al. 2020a 2021; Sun al., 2019: Liang al. 2022). We compare our
methods with several statc-of-the the--ar robust training methods including ATLA-PPP PPO (Zhang et al., 2021]. PA-ATLA-PPPO (Sun al., 2021), and WocaR-PPO (Liang et al.) 2022). WocaR-PPO is reported to be the most robust in most environments. We defer the comparison with other baselines, along with additional implementation and hyperparameter details the Appendix.
5.2 PERFORMANCE AGAINST STATIC ATTACKS
In this subsection, showcase improved performance against spectrum of attacks, ranging from no attacks to the strongest ones. Accordingly, we present the natural rewards to depict the scenario without any attacks. We incorporate two heuristic attacks: random perturbations and robust SARSA (RS) Zhang et al. 2020aa,, representing attacks beyond worst-case scenarios. We also include SA- RL attacks (Zhang et al. 2021 to reflect scenarios where the attacker might have limited algorithmic efficiency to devise an optimal attack policy since SA-RL can struggle with large action space in its formulation, and its attack performance can be further enhanced indicated by Sun et al. 2021
8

---

Published as a conference paper at ICLR 2024
MANTLA
DIATTA
DIAATLA
loing neRd
Scoting FOOmO
Wosting FrLnc
Teiking POREES
(a) Attack Period
1000
(b) Attack Period T 200
(c) Attack Probubility 0.4
(d) Attack Probability p 0.8.
Figure 3: Time averaged accumulative rewards during online adaptation against periodic and prob- abilistic switching attacks on Ant. The shaded area indicates PA-AD attacks are active while the unshaded area indicates attacks.
(a) Hopper
(b) Walker
(c) Halfcheetal
(d) Ant
Figure 4: Ablation study of [ii] against PA-AD attacks on environments.
making it non- worst-case as well. Lastly, we incorporate PA-AD. the currently strongest attack. As observed in Table our methods yield considerably higher natural rewards and consistently enhanced robustness against spectrum of attacks. To further show the improved performance against non-wond non-worst-case attacks, we report the robustness under random attacks with various intensities in $E.3, where our methods are consistently better. Given that our victim policy is adaptive, some additional adaptation steps might be necessary to identify the optimal policy against the attackers. To illustrate this, detail the adaptation process in Figure 2 showcasing that the best policy within IT can be identified rapidly and reliably.
5.3 PERFORMANCE AGAINST DYNAMIC ATTACKS
We also examine scenarios where the attacker can exhibit dynamic behavior. To model such scenar- ios, we let attackers switch between no attacks and PA-AD attacks in the following two fashions.
Periodic attacks. Here we examine mode where the attacker is weaker than in the worst-case scenarios, characterized by attacks appearing only periodically. We depict the performance against periodic attacks with varied frequencies.
Probabilistic switching attacks. this section, we explore another mode where the attacker less severe than in the worst-case scenarios. The attacker can toggle between being active and inactive. This switching is constrained to occur only with a probability p at regular intervals.
The results shown in Figure 3 illustrating that the average cumulative reward, conversely, the negative of the regret, consistently outperforms the baselines.
5.4
ON THE SCALABILITY OF III
One major concern regarding our approach that may require a rather large policy class ÎI to achieve desirable performance. We report the performance our methods with different [Ii] against PA-AD attacks in Figure 4 on all environments. Surprisingly, our methods only need within 3 policies for IT to achieve improved performance compared with baselines.
CONCLUDING REMARKS AND LIMITATIONS
In this paper, we develop general framework to improve victim performance against attacks beyond worst-case scenarios. There are two phases: pre-training of non-dominated policies and online adaptation via no-regret learning. One limitation is the potentially high overhead during training (approximately 2x running time compared with/Sun et al. 2021 Liang et al. (2022)). as highlighted by Theorem 4.11 Additionally, identifying natural conditions to circumvent the hardness results outlined in Proposition 4.3 not fully addressed and remains important topic for future works.
and and Theorem 4.1I such as Lipschitz transition dynamics and rewards, is

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGEMENT
Liu, Deng, Sun, Liang, and Huang are supported by National Science Foundation NSF-IISFAI pro- gram, DOD-ONR-Offic of Naval Research, DOD Air Force Office of Scientific Research, DOD- DARPA-Defent Advanced Research Projects Agency Guaranteeing Al Robustness against Decep- tion (GARD), Adobe, Capital One and JP Morgan faculty fellowships.
REFERENCES
Peter Auer. Using confidence bounds for exploitation-exploraaion trade-offs. Journal of Machine Learning Research, 3(Nov):397 2002.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multi- armed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
Leon Barrett and Srini Narayaman. Learning all optimal policies with multiple criteria. In Proceed- ings of the 25th international conference on Machine learning, pp. 41 41-47, 2008
Vahid Behzadan and Arslan Munir. Vulnerability of deep reinforcement learning to policy induc- tion attacks. In Machine Learning and Data Mining in Puttern Recognition: 13th International Conference, MLDM 2017, New York, NY, USA, July 15-20, 2017, Proceedings 13, pp. 262-275. Springer, 2017.
Sébastien Bubeck, Nicolo Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
Nicolo Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity all you need: Learning skills without a reward function. arXiv preprint arXiv: /802.0607,, 2018.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International conference machine learning, pp. 1126- 1135. PMLR, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In International Conference Machine Learning, pp. 1920-1930. PMLR, 2019.
Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adver- sarial policies: Attacking deep reinforcement learning. arXiv preprint arXiv: 1905. 10615, 2019.
James Hannan. Approximation to bayes risk in repeated play. Contributions to the Theory of Games, 3:97-139, 1957.
Aaron Havens, Zhanhong Jiang, and Soumik Sarkar. Online robust policy learning in the presence of unknown adversaries. Advances in neural information processing systems, 31, 2018
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-322) -25, 2016.
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. arXiv preprint 702.::1702..22844 2017.
Yunhan Huang and Quanyan Zhu. Deceptive reinforcement learning under adversarial manipula- tions on cost signals. In Decision and Game Theory for Security; 10th International Conference, GameSec 2019, Stockholm, Sweden, October 30-November 1, 2019, Proceedings 10, pp. 217- 237. Springer, 2019.
Julian Ibarz, Jie Tan, Chelsea Finn, Mrinal Kalakrishnan, Peter Pastor, and Sergey Levine. How to train your robot with deep reinforcement learning: lessons we have learned. The International Journal of Robotics Research, 40(4-5):698-75 2021.
10

---

Published as a conference paper at ICLR 2024
Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pp. 4860-4869, PMLR, 2020.
Yong Kim and Olivier L de Weck. Adaptive weighted sum method for multiobjective optimization: new method for pareto front generation. Structural and multidisciplinary optimization, 31)2): 105-116, 2006.
Abdullah Konak, David Coit, and Alice E Smith. Multi-objective optimization using genetic algorithms: A tutorial. Reliability engineering & system safety, 91(9):992-100) 2006.
Jernej Kos and Dawn Song. Delving into adversarial attacks on deep policies. arXiv preprint arXiv:1705.06455, 2017.
Saurabh Kumar, Aviral Kumar, Sergey Levine, and Chelsea Finn. One solution is not all you need: Few-shot extrapolation via structured maxent rl. Advances in Neural Information Processing Systems, 33:8198 8210, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Xian Yeow Lee, Yasaman Esfandiari, Kai Liang Tan, and Soumik Sarkar. Query-based targeted action-space adversarial policies deep reinforcement learning agents. In Proceedings of the ACM/IEEE 12th International Conference on Cyber-Physice Systems, pp. 87-97, 2021.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuo- motor policies. The Journal of Machine Learning Research, 17(1):1334-1373, 2016.
Yongyuan Liang Yanchao Sun, Ruijie Zheng, and Furong Huang. Efficient adversarial train- ing without attacking: Worst-case-awar robust reinforcement learning. arXiv preprint arXiv:2210.05927. 2022.
Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex-concave minimax problems. arXiv preprint arXiv: 1r00003990600331,, 2019a.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave mini- max problems. In International Conference on Machine Learning, pp. 6083-6093, PMLR, 2020.
Yen-Chen Lin, Zhang- Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming-Yu Yu Liu, and Min Sun. Tactics of adversarial attack on deep reinforcement learning agents, 2019b.
Hossam Mossalam, Yannis M Assael, Diederik M Roijers, and Shimon Whiteson. Multi-objective deep reinforcement learning. arXiv preprint arXiv:1610.02770 2016.
Hirotaka Nakayama, Yeboon Yun, and Min Yoon. Sequential approximate multiobjectivve optimiza- fion using computational intelligence. Springer Science & Business Media, 2009.
Sriraam Natarajan and Prasad Tadepalli. Dynamic preferences multi-criteria reinforcement learn- ing. In Proceedings of the 22nd international conference on Machine learning, pp. 601-608
2005.
Gergely Neu. Explore no more: Improved high-probability regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28, 2015.
Tuomas Oikarinen, Tsui-Wei Weng, and Luca Daniel. Robust deep reinforcement learning through adversarial loss, 2020.
OpenAL. Gpt-4 technical report. arXiv,, pp. 2303-08774, 2023.
Xinlei Pan, Chaowei Xiao, Warren He, Shuang Yang. Jian Peng, Mingjie Sun. Jinfeng Yi, Zijiang Yang, Mingyan Liu, Bo Li, et al. Characterizing attacks on deep reinforcement learning. arXiv preprint /t0Xvv:907.0944 00970,, 2019.
Anay Pattanaik, Zhenyi Tang, Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Robust deep reinforcement leamning with adversarial attacks, 2017.

---

Published as a conference paper at ICLR 2024
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforce- ment learning. In International Conference on Machine Learning, Pp. 2817-2826. 2017.
You Qiaoben, Chengyang Ying, Xinning Zhou, Hang Su, Jun Zhu, and Bo Zhang. Understanding adversarial attacks on observations in deep reinforcement learning, 2021.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via environment poisoning: Training-tine time adversarial attacks against reinforcement learning. In International Conference on Machine Learning, pp. 7974-7984, PMLR, 2020.
Diederik M Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley, A survey of multi- objective sequential decision-making. Journal of Artificial Intelligence Research, 48:67-113, 2013.
Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7):78 2010.
Alessio Russo and Alexandre Proutiere. Optimal attacks on reinforcement learning policies. arXiv preprint arXiv: 0001199977335 13548, 2019.
Daniel Russo and Benjamin Van Roy. An information-thhorrticc analysis of thompson sampling. The Journal of Machine Learning Research, 17(1):2442-25) 2272124222221,, 2016.
Jürgen Schmidhuber. Evolutionary principles in self-referential learning, learning how to learn: the meta-meta-.. hook. PhD thesis, Technische Universität München, 1987.
Wen Sun, Nan Jiang. Akshay Krishnamurthy, Alckh Agarwal, and John Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pp. 2898 2033, 2019.
Yanchao Sun. Da Huo, and Furong Huang. Vulnerability aware poisoning mechanism for online rl with unknown dynamics. arXiv preprint arXiv:2009.00774, 2020.
Yanchao Sun, Ruijie Zheng, Yongyuan Liang, and Furong Huang. Who is the strongest enemy? towards optimal and efficient evasion attacks in deep rl. arXiv preprint arXiv:2106.05007. 2021.
Kai Liang Tan, Yasaman Esfandiari, Xian Yeow Lee, Soumik Sarkar, al. Robustifying reinforce- ment learning agents via action space adversarial training. In 2020 American control conference (ACC), pp. 3959-3964. IEEE, 2020.
Chen Tessler, Yonathan Efroni, and Shie Mannor. Action robust reinforcement learning and appli- cations in continuous control. In International Conference Machine Learning, pp. 2215-6224 PMLR, 2019.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.
Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan. generalized algorithm for multi-objective reinforcement learning and policy adaptation. Advances in neural information processing systems, 32, 2019.
Tom Zahavy, Andre Barreto, Daniel Mankowitz, Shaobo Hou, Brendan O' O'Donoguue, Iurii Ke- maev, and Satinder Singh. Discovering set of policies for the worst reward. arXiv preprint arXiv:2102.04333 2021.
Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Duane S Boning, and Cho-Jui Hsich. Robust deep reinforcement learning against adversarial perturbations on observations. 2020a.
Huan Zhang, Hongge Chen, Duane Boning, and Cho-Jui Hsieh. Robust reinforcement learning on
state observations with learned optimal adversary. arXiv preprint arXiv:2 08452, 2021.
Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive reward-poisoning attacks against reinforcement learning. International Conference on Machine Learning, pp. 11225- 11234. PMLR, 2020b.
12

---

Published as a conference paper at ICLR 2024
Appendix for "Beyond Worst-case Attacks: Robust RL with Adaptive Defense via Non-dominated Policies"
Table of Contents
Additional related works
B
Thcoretical analysis
14
B.1
Supporting lemmas
14
B.2
Proof of Proposition 4.3
15
B.3
Proof of Proposition 4.7
15
B.4
Proof of Proposition 4.8
16
B,5
Proof Theorem
16
B.6
Proof Theorem 4.11
C Example and detailed explanations of iterative discovery
17
D Details of experimental settings
18
E
Additional experimental results
18
Robustness against various dynamic attacks
E,2
Ablation study the scalability of [1I|
19
E.3
Ablation study on the attack budget
20
E,4
Ablation study on the worst-case robustness
22
Ablation study on online reward for baselines.
22
A ADDITIONAL RELATED WORKS
Other works related to adversarial RI. Although our paper mainly studies the popular attack model of adversarial state perturbations, the vulnerability of RL is also studied under other different threat models. Adversarial action attacks are developed separately from state attacks including Pan
ctt al. 20199; Tessler et al.] (2019); Tan et al. (2020); Lee et al. (202I). Poisoning (Behzadan & Munir 2017 Huang & Zhu 2019 Sun et al. 2020 Zhang et al. 2020b Rakhsha al. 2020) is another type of adversarial attack that manipulates the training data, different from the test-time attacks that deprave well-trained policy.
Diverse multi-policy RL. There are also bunch of related works dedicated to developing RL policies that generalize unknown test environments. The main idea is encourage the di- versity of learned policies (Eysenbach et al., 2018 Kumar et al. 2020), by ensuring good coverage in the state occupancy space the training environment. However, the robustness against malicious, and even adaptive attackers during test time remains an open question. We posit that incorporating the possibility of adaptive test-time attackers into the training phase is critical for developing robust policies. Meanwhile, Zahavy et al. (2021) considers constructing diverse set of policies through a robustness objective, which targets the worst-case reward.
such policies
Multi-objective RL and optimization. In the training phase, the problem we investigate is con- ceptually similar to multi-objective RI, wherein the objective functions correspond to the victim's 's rewards against range of potential attackers. Extant literature primarily adopts one of two ap- proaches to this challenge (Roijers et al. 2013). The first approach converts the multi-objective problem into single-objective optimization task through a variety of techniques, subsequently em- ploying traditional algorithms to identify solutions (Kim & de Week 2006) Konak et al. (006) Nakayama et al.) 2009). However, such methods inherently yield average policy over the prefer- ence space and lack the flexibility to optimize for individualized preference vectors. In contrast, our methodology during the training phase aligns more closely with the second category of approaches,
13

---

Published as a conference paper at ICLR 2024
which seeks optimal policy set that spans the entire domain of feasible preferences NNtarajan & Tadepalli 2005; Barrett & Narayanan 2008 Mossalam et al. 2016 Yang et al. 2019). Unfor- tunately, existing techniques not well-suited to address the unique complexities of our problem. Specifically, conventional methods are predicated on the assumption that, in multi-objective RI,, distinct objectives only alter the reward function of the MDP, while the transition dynamics remain invariant. This structure facilitates the use of established algorithms such as value iteration or Q- learning. In the context of our problem, as mentioned before, this assumption does hold, as the attacker significantly influences the transition dynamics from the victim's 's standpoint.
B THEORETICAL ANALYSIS
B. SUPPORTING LEMMAS
Here prove the following series of lemmas for the proof of our propositions and theorems. From now on, for any E AlII) and v, we use the shorthand notation [w,, v) :- E (T,, v).
Lemma B.1. For any II, there always exists (IIIdtt) such that (TT J(w, v) for any E V.
Proof. Consider any trajectory {sh, En, an helH and random seed Z, we compute proba- bility under policy æ E II and V as follows pa." ((sn, Shy an x)
H II
(s1)) (8i 181, () (81)
T(sn 18-1, 18-11 ()) 88, z)
h=2
H
H II
T 81)
(()) (81 II a(an (1-))) h=2
T(sk sh-1, sh. 2).
h=2
Now we are ready to construct the mixture of policy w E A(TTeer). For any E lldet we define its probability in the mixture
w(T'==
II II
(1 B (1 d(.a-)).
(B.1)
ME(M) (3, (f)))))))))))))))
Now we can compute
pu.y (1sh, Sh. an anhnetn)
2) Bur " "(sh, Sn. on anemmm))2)
H
(S)) (8,,
II
T(sh 88 an (5n sn, z)
Ex [ai = ='((8), fan = = ()
h=2
H
(s))) (1)))
T(sa (0- 2)
PPaa n T'i)), {an n' a'En 11)
h=2
H II h=2
(S)))))))) 181 2)
II h=2
T(sh 8h-1; 8h, 2)
T (8))
a 8ash, (1Ah-1)
where the last step comes from the construction of w in Equation B.1 by marginalization. Therefore,
we conclude that [p.." (1sn, Sh. ah Jeelt 2) (p.. Sn, an Jhe , 2), where construction of w does not depend on proving our lemma.
Lemma B.2. The optimization problem of Equation always admits deterministic solution.
Proof. Note by the definition of V A (Dile), indeed strong duality holds:
max *f ET (
min
max DEY
(J k+1 v/) Eu [J(x', 1/]]
* NEV wEA((T rEA((""...aa))) (J( .V) Exr |
min
14

---

Published as a conference paper at ICLR 2024
Then for any x x, 2/2 E arg mag.aat--ieeee mi xx)) (J(x++),,) .2) ['('', v)]),
we denote o² (V*)= ;= arg max, 1 (x )/*). Note that n (v) can be always selected to be
deterministic policy by Lemma B.I Meanwhile, it is easy see that since xht1,*, v² is an optimal solution, πt T"(v"); V" is also an optimal solution, i.e.,
x x²(1"), v² E arg max
a wel (J( v) - Ear E
min
concluding our lemma.
Lemma B.3. Let K E N be the integer such that fK+1 0 and fK > 0. For any 2 < k S K, there does not exist some wt E A(I1drr {T²)) such that maxvev (J( v) - J j(w v) S 0.
Proof. To begin with, it is easy to see that there does not exist I k1 k2 S K such that Th = = This is because it will lead to the fact that faz- = 0. Now suppose there exists some
w' E A(I {T²}) such that
max (J( J(w",,,))) 5 NEV
This leads to the fact that
min
max
(J( .) - Jw, 5 (EA((T), 1)) NEV
min
max (J(w",)) v) - J(w
WEA((=) tk 1)) NEV
max
min
max (J(w' v)) J(W
WEATT ( WE .ak 13) PEV
max
max
min
(J(w' v) -w Dw,
WEAII \=* +] }} NEV wEA(
max TETTE (mk) NEV WEA((=)
max
min
(J(TT v) Jww v)
max TEITAIX WE x(-1
min
max NEV
(J(z,V) [w, v))
where the second last step comes from exactly the same as the proof of Lemma B.2 This contradicts the fact that nh is the unique optimal solution at iteration k.
B.2 PROOF OF PROPOSITION 4.3
Proof. We construct the MDP A with the state space S {sdood goad gdummyy) action space A = faoood abod). For the reward, we define rı. (:,--)) for h E H - 1] and F
( (s90od 1 and TH (staad :)==)===)) 0. For the transition, we define T(s90od ggood agoood) = (aa ggood abad ) = 1.
T(shadd ibbad
1. The initial state is always ggood, We consider the attacker's policy such that v(s (otummyy .) = 1, which means the attacker deterministically perturbs the state to ddimmy There- multi-arm bandit problem with 2 arms, for which the sample complexity of finding an approximately optimal policy must suffer from 2(2#). Meanwhile, if such desirable regret in the proposition is possible, means we can learn an c-optimal policy in such kind of multi-arm bandit problem with sample complexity poly(S, A, H1, 1), leading to the contradiction.
fore, for the victim to learn the optimal policy against such an attacker, it is equivalent
B.3 PROOF OF PROPOSITION 4.7
Proof. For any UI: we denote xt E arg max + Et J(z,V'). Then according to Definition
we have
(T) = Σ
(J( v(T),''))
t=1
T
Σ J(mT v4) max
Σ (1T
Σ
-(at)
max EEñ
*eñ
< T Gap([i, + (T))
where the last step comes from choosing Un in Definition 4.6
15

---

Published as a conference paper at ICLR 2024
B.4 PROOF OF PROPOSITION 4.8
Proof. Note since in this proposition, we only care about the existence of a finite II, we do not care about its efficiency, i... how large the constructed II is. Indeed, we can consider _1 which is a finite policy class with cardinality | = (((SA)*) Now we verify the opti- mality of Iī For any E V, assume ''' E arg max J uj. Then by Lemma B.1 we have there exists an w* E A(II=) such that J(T*,V)
E Bmtiing (Trle, v)), Now we choose nplt, = argmax J(m0,,) v). Then we have J .V) 2 Ea [(rde v) _ Therefore, we conclude that for any v E V, we have maX J v) = max (T, There- fore, Gap(IIde III = 0.
B.5 PROOF OF THEOREM 4.10
Proof. We begin with the proof for the part of the theorem. For 8 >> and any ,,, ... ippin
IT 11. we define the set D " -)pp)) = { E II (i, - 1)6 I J(,, vz) < i, E [|]a[]]]
Then according to Pigeonhole principle, there must exist K E N and k E [K] such that π K+ e
D . (ym)) and x* E D(', ((xen) for some $4, 1/,2"". .. livey E "] Therefore, we
conclude that [ (+1, 1) J(* v) S 8 for any // E ydet, and correspondingly for any v E V. This lead to that fx+1 I 5. Now we are ready to show that Gap(îi*+ .I) S 5. For any v E V, we define n¹ E arg max [ v). Meanwhile, there exists w E A A(TK+1) such that J(x", v) <
Jus, v) + since fK+1 S 8. This implies that J( v) - max - J( v) S 8, proving Gap(ITK<+1, II) S 6.
Now we prove the second part of our theorem. Suppose K* < Kfn 1, we denote the corresponding
TK*), ".", }. By Lemma B.1 for any k E [K*], there exists a optimal policy set as IT* = ( ...
w E (IIIdtt) such that
J( v) = Σ w (T))
for any V E V. where we have abused our notation for { ...... , < to denote deter- ministic policies, which are policies discovered by our algorithm since according to Lemma B.2 those policies are different and deterministic. Now since K* < K 1, there ex- ists some 2 <
K such that (²()) I 3/ for any k miT maxvev (J(T), - (w, > 0 by Lemma B.3 and let V²* E argmax minwEA(THO) (xi)) (J(T), (TT),,) - J(w,))) Therefore, it holds that M( 1²*) 2 ( v*) + for any E A {)) Then we are ready to examine Gap(II*, II) as follows:
[K*]. Now we de-
note
Gap(II', MI) 2 max J(T, v²) #Ell
max J(x', I(T²v²" J( max J(x', s'Ell
3 0,
x'Ell-
contradicting that Gap(II+, III =0.
B.6 PROOF OF THEOREM
Proof. Let us firstly consider a one-step MDP with state space S = (81,82). action space A (a1,a2) reward function r(s1, 01) = r(82, a2) otherwise O, and μ1 (s1) μu (1())
Now assume the attacker can only choose two policies poood such that ggo0d(s1) = $1, 2.oo (82) = 82, and s such that (a)()))
$1. Let consider four basis victim policies which select the action (01, (2),((1) (01, a1), (az, )1), (az, a2) respectively for states 81 and 82. Then it holds that for any policy æ E II, there exists a E [0 and E, a² = such that
$2, h/a (s2)
( ,...... ...,,, *)),
( - -+ (TT)) .) by Lemma B.1 Now we have either a' < or a < 2. Let us say at S and the case for 3 < 1 can be proved similarly. Consider the case where the attacker takes the policy yoood Then we have J(x² _0ooo) - -[(r,, (oood) 2 1 - G + 1 x 1 = 1 Therefore, we
2 2
4.
conclude that if [T| < 2, we must have Gap (T, IT) 2 1
16

---

Published as a conference paper at ICLR 2024
Now let extend it to the MDP with H steps, where in the previous MDP, at each time step, the current state transits to the next two states with uniform probability regardless of the action taken. We consider the attacker's policies, where at each time step it uses the policy 2oood or p'nd
resulting in totally 2" policies, {v²,-. ...,,""), =²") }. Similarly, we can define basis policies, which at each time step selects the policy from { ( .... ,"),, ignoring the history information except the current observation (perturbed state). This results
total of 4 policies, for which we denote J. Due to the transition dynamics we have defined, for any E 11, there exists some (T)) E [0, 1] and [T)((T) = such that J(TT,)) .) = Σj= a (T))( W.L.O.G. we say policies #1:2" as all the policies only selecting policies from {x',>") at each time step. Now consider any II = { , ,,,,,.... **) with K < 2 Then there must be some m E [24] such that a aTT(TT) S for any k E [K]. Let us say nrh is the policy always choosing x² at all time steps and correspondingly denote v as the policy always choosing poood at each step. Therefore, we have (a 2²) J( v²) 2 H. (H i + 2 + x GII 11) 2
( #**}
1/ for any & E [K]. This concludes that
C EXAMPLE AND DETAILED EXPLANATIONS OF ITERATIVE DISCOVERY
[(, 12)
(x,
[ v2)
Vxr,v*)
v(n,v')
[x,, v*)
Figure 5: Iteration discovery of non-dominated policies in two dimensions.
Here we explain how our algorithm discovers the four policies 11:4 in Figure 5 i.e., the left part of Figure [ For simplicity, we consider there are only two pure attackers v and v², and thus V A(v ,2)).
For the first iteration, since there are no policies already discovered, the optimization problem we need to solve n² E arg max max.ev J(z, v) = arg maxzen max (J(T,, v²), J[m, v²)]. By comparing vd and v², we can see the discovered policy is the rightmost one in Figure 5
For the second iteration, given îî = { already discovered, the optimization problem need to solve is x² E arg max max (J(m, v) J(x.,,)) v)). Since x² E arg max J(m, v²), we
have 2² E arg max max (J(TT, v) J(=', v)) arg max (J(T, v²) J(TT) ,,²))
arg max=en J(HT, v²). Therefore, x² is the uppermost one in Figure 5
For the third iteration, given II { m²} already discovered, the optimization problem we need to solve is 3 E arg max minwe ((*) max,ev (J(m, v) J(m², (1)), It easy that in Figure 5] the optimal solution should be the one that's farthest from the line segment between It and π². To see the reason, we can find that the optimal will be the point on the line segment between π' and 2 such that J(x²3 v²) J[w v') = (T² v²) (1²) - J(w 2²).
For the fourth iteration, given II {m², m r already discovered, the optimization problem we need to solve is x E arg max minwea((r'.at x*3)) maxvev (J(T, v) - J(x' ,)).. From Figure 5 the optimization for w will not put mass on policy n². Thus, what we need to solve is T² E arg eax min
max (J(z,)) v)) - J(x'; (()).)). Under the same reason as the third iteration, 7 will be the one that is farthest to the line segment between 7²2 and 3
Finally, it is worth mentioning that the analysis above holds only specifically (and roughly) for the reward landscape of Figure 5 for which we have simplified significantly to convey the intuitions. Actual problems aim to deal with can be much more complex.
17

---

Published as a conference paper at ICLR 2024
D DETAILS OF EXPERIMENTAL SETTINGS
In this section, provide details of implementation and training hyperparameters for MuJoCo experiments. All experiments are conducted on NVIDIA GeForce RTX 2080 Ti GPU.
Implementation details. For the network structure, employ a single-layer LSTM with 64 hidden neurons in Ant and Halfcheetah, and the original fully connected MLP structure in the other two environments. Both the victims and the attackers trained with independent value and policy optimizers by PPO.
Victim training. For the baseline methods, we directly utilize the well-trained models for ATLA- PPO (Zhng et al. (2021), PA-ATLA-PPO (Sun et al.) 2021), and WocaR-PPO (Liang et al. 2022) provided by the authors.
For the iterative discovery in Algorithm 2 we employ PA-AD to update attack models u' and PPO to update the victim. For the first policy I² in IT, we train for 5 million steps (2441 iterations) in Ant and 2.5 million steps (1220 iterations) in the other three environments. For subsequent policies, we use the previously trained policy the initialization and train for half of the steps of the first iteration to accelerate training.
Due to the high variance in RL training, the reported results reported as the median performance from 21 agents trained with the same set of hyperparameters for reproducibility.
Attack training. The reported results under RS attack are from 30 trained robust value functions.
For evasion attacks such as SA-RL and PA-AD, we conduct grid search of the optimal hyperparam- eters (including learning rates for the policy network and the adversary policy network, the ratio clip for PPO, and the entropy regularization) for each victim training method. We train for 10 million steps (4882 iterations) in Ant and 5 million steps (2441 iterations) in the other three environments. The reported results are from the strongest attack among all 108 trained adversaries.
E ADDITIONAL. EXPERIMENTAL RESULTS
E.I ROBUSTNESS AGAINST VARIOUS DYNAMIC ATTACKS
In this section, present the supplementary results demonstrating the robustness of our methods against various dynamic attacks. Two modes of dynamic attacks, periodic attacks, and probabilistic switching attacks, have been briefly introduced in $5.3 Here we show more details and results corresponding to these two dynamic attack modes.
Periodic attacks. We adjust the attack period T' from 1000 to 100 and examine the performance of our methods alongside two baselines. Additionally, we use non-fixed period where T alternates between 500 and 1000.
The average accumulative rewards and evolution of policy weights w are shown in plots and heat maps in $6 Our observations are as follows: (1) Regardless of the duration of the periods, our methods consistently achieve higher average accumulative rewards than the two baseline methods. This underscores the efficacy of online adaptation in Algorithm 1 (2) The values of w' exhibit noticeable shifts during each period, highlighting the online adaptation process. (3) Even when T alternates, our methods maintain their superiority over the baselines. The evolution of w' shows that our methods can effectively perceive the transition between two periods.
Probabilistic attack. We adjust the switching probability p from 0.2 0.8. A higher value of p signifies more frequent switching. We anticipate that it will be more challenging for the online adaptation of the agent. We keep the interval between two potential switching points as 50 rounds.
The results are exhibited in Figure 7 showcasing both the average accumulative rewards and the evolution of the weight w² We conclude that: (1) Our methods consistently outpace the two base- lines. The superiority becomes more pronounced the value of p increases. (2) In contrast to the scenario with periodic attacks, the weights w' display a more random evolution. Nonetheless, they effectively converge the arms yielding higher rewards.
18

---

Published as a conference paper at ICLR 2024
17.0
Avttoge www.mclcaaiiiii rew.oeeeeeese rowards
Average aec.mmllttiii nowardd
1250
1200
1200
Woodt RVAILA
Wozll BLAATA
Worli
BLAALA
Texinn munds
Texiin munds
Toeing munds
200
1300
2000
2500
200
1200
2000
2300
250
1200
2000
254
Azto (0F)
Armo
01
(a) = 1000
(b) T 500
(c) T 400
4750
6150
4:50
Averge scctmmlaehe rewemk.
Avamgs rewamb.
8300
2000
1000
3500
3000
10:0
3100
31:0
PA. ATLA
PN-ATLA
RV-ATLA
6.00
1200
3600 rounds
SCA0
4000
940
1200 Testing
2400
5200
43.0
940
34.0
3200
40.0
Testing
607
Anne 60'3
Anto (0)3
(d) T 250
(e) T -00
( 125
Averge www.nutaaeeeeeeeee cpwarrs
On Wecal
Wocal
Tealing rounds
Testing roundss
1580 2MC
0.0
Aume (oF)
1.4
3.8
2.4
0.5
(g)
100
(h) Alternativlly varying T
Figure 6: Time averaged accumulative rewards during online adaptation against periodic attacks Ant. The shaded area showed in the indicates PA-AD attacks are active while the unshaded area indicates attacks. The evolution of corresponding weights w is shown in the heatmap where the brighter color means the higher value.
E.2 ABLATION STUDY ON THE SCALABILITY [i
potential concern for our methods is the high computational cost iterative discovery, which could render them impractical. To tackle this concern, we assess our methods using different scales of the policy class [i] under PA-AD attacks across all four environments. The original value of [N] Table iis set to and we modify it to both and 7 for this ablation study. All other experimental parameters remain the same.
19

---

Published as a conference paper at ICLR 2024
$2.0
Aettoge wcc.mnlllaainn rowards
Aberage aec.mmaaitiinn nowardd
1750
0750
Woodi RLAILA
Wozll BLATTA
Woczi BLAITA
Texiing munds
Texiing munds
Texiing munds
230
150
1250
1750
250
130
1330
1750
230
750
1290
2740
Azto (o
(a) p 0.2
(b) p 0.4
(c) p = 0.5
XDM
Neergg accumelahh revandd
8250
1200
2750
2750
1000
1200
RA ATLA
ATLA
96
1900
2000
400
9l
1230
1540
200
Testing rounds
Testing
5.4
Anos OF3
(d) 0.6
(e) 0.8
Figure 7: Time averaged accumulative rewards during online adaptation against probabilistic switch- ing attacks Ant. The shaded area showed in the indicates PA-AD attacks active while the unshaded area indicates no attacks. The evolution of corresponding weights wf is shown in the heatmap where the brighter color means the higher value.
The results depicted in Figure We notice that: (1) The larger scale leads to higher rewards in all four environments. This implics that the non-dominated policy class, as it cxpands via iterative discovery, approaches the optimal relatively modest scale 3, our methods outpace the baseline methods Table This alleviates concerns about our methods being reliant unaffordable computational costs.
more accurately with increasing scales. (2) Even with
E.3 ABLATION STUDY ON THE ATTACK BUDGET
To examine how our methods perform under attacks with different values of the attack budget e, we evaluate their performance under a random attack across all four environments and compare them with two baselines. From Table [ we observe that the random attack is relatively mild. However, its impact can much worse if the attack budget higher. Our goal is evaluate the robustness of against non-worst-case attacks across various spectra.
The corresponding results are displayed in Figure We derive the following observations: (1) When is small, the rewards of our methods are slightly higher than the baseline methods in nearly all envi- ronments. The exception on Walker2d, where our methods distinctly outperform the baselines. indicates the effectiveness of our methods in relatively clean environments. (2) As becomes mod- erate and continues to increase, although the performances of our methods decrease as PA-ATLA and WocaR, the rate of decline is slower compared to the two baseline methods. Previously, we only consider the non-wond worst-case attacks with the same e by different modes. In this context, increasing values of for the same attack be also interpreted another oo--worst-case attack. Thus, the
20

---

Published as a conference paper at ICLR 2024
3000
Rewards
2890
(0] -5
-0
[0] -3
0
01-
(a) Hopper
(b) Walker2d
Rewards
43013311
[M]
[0
[A]
0--5
(c) Halfcheetah
(d) Ant
Figure 8: The performance for our methods with different non-dominant policy class scales [[]] in all four environments.
high rewards of our methods confirm their enhanced robustness against various types of nonsworst- case attacks. (3) When is large, methods continue to hold an advantage over the bascline methods. The only exception Hopper, where the rewards from all three methods are nearly identi- cal. This suggests that our methods compromise little in terms of robustness against worst-case attacks.
5000
S000
PA-ATLA
WhxaR
PA-ATLA
Whezi
Rewards
Rewards
2500
4000
0.125
(a) Hopper
(b) Walker2d
9000
6000
PA-ATELA
Wocsiit
PA-ATELA
Wivoitt
Rewards
Rewards
4500
3000
0.5
(c) Halfcheetah
(d) Ant
Figure 9: The performance for our methods and two baseline methods under attacks with different in all four environments.
21

---

Published as a conference paper at ICLR 2024
E.4 ABLATION STUDY ON THE WORST-CASE ROBUSTNESS
Although our primary goal is to improve the robustness against attacks beyond the worst cases, supprisiggl, we find the robustness our approach against currently strongest attacks PA-AD is also improved. To understand such reasons, we firstly notice that although related works including Zhang ct (202T); et al. (202T); [Liang ct al. (2022) share the same objective of explicitly max- imizing the worst-case performance, Sun al. (2021) improves over WhanZh et al. (2021) and Liang et al. (202)) improves over [Sun et al. (022)). Therefore, we make the hypothesis that baseline approach may not have found the global optimal solution for their objective of maximizing robustness against the worst-case attacks reliably. Specifically, one possible explanation from the perspective of optimization is that baselines could often converge to a local optima, while our approach explicitly encourages the new policy to behave differently in the reward space compared with policies discovered already, thus not stuck at a single local optimal solution easily. To further verify our hypothesis, we design the experiments as follows.
Firstly, note the number we report in Table I is a median number of 21 agents trained with the same set of hyperparameters following the set up of [Zhang et al. (2021); Sun et al. (2021): [Lingg et al. (2022). To verify our hypothesis, we compare the performance the best one and the median one of different approaches in Table We can see that baselines like [Sun et al. (2021 T): Liang et al. (2022) can match the high performance of ours in terms of the best run, while the median is low by large margin. This means it is possible for baselines to achieve high worst-case robustness occasionally as its objective explicitly encourages so, but not reliably. In contrast, our methods are much more stable. This effectively supports hypothesis.
PA-AD (Median)
PA-AD (Highest)
Environment
Model
Hopper
PA-ATLA-PPO
2521 + 325
3129 + 316
state-dim: 11
WocaR-PPO
2579 + 229
3284 + 193
e00.75
Ours
2896 723
3057 + 809
Walker2d
PA-ATLA-PPO
2248 + 131
3561 + 357
state-dim: 17
WocaR-PPO
2722 173
4239 = 295
=00.5
Ours
4239 295
6052 + 944
Halfcheetah
PA-ATLA-PPO
3840 273
4260 193
state-dim: 17
WocaR-PPO
4269 + 172
4579 + 368
e00.5
Ours
4411 + 718
4533 + 692
Ant
PA-ATLA-PPO
2986 364
3529 + 782
state-dim: 111
WocaR-PPO
3164 + 163
4273 + 530
c0.15
Ours
4273 + 530
4406 + 329
Table 2: Average episode rewards + standard deviation with two baselines on Hopper, Walker2d, Halfcheetah, and Ant. The median and highest performance from 21 agents trained with the same set of hyperparameters are reported in two columns respectively.
E.5 ABLATION STUDY ON ONLINE REWARD FOR BASELINES.
To clarify our novel Algorithm 2 to minimize Gip II) contributes to the major improvements of our approach instead of simply using online reward feedback, we conduct further ablation studies by also allowing baselines to use online reward feedbacks through our Algorithm [ However, all baselines are essentially a single victim policy instead of set, making it trivial to run Algorithm [] since it will only have one policy to select. To address such a challenge, we propose a new, stronger baseline as follows by defining buseeliee = { (ATLA-PPO, PA-ATLA-PPO WocaR-PPO). Note that since hhsseline has effectively aggregated all previous baselines, it should be no worse than them. Now hhseelnee and our II are comparable since they both Algorithm to utilize the online reward feedback. The detailed comparison is in Table 3
We can see that even with this new, stronger baseline utilizing the reward feedback in the same way as us, our results are still consistently better.
22

---

Published as a conference paper at ICLR 2024
Natural
Environment
Model
Random
RS
SA-RL
PA-AD
Reward
π hasellne
3624 + 186
3605 + 41
3284 + 249
2442 + 150
2627 + 254
Hopper
Ours
3652 + 108
3653 + 57
3332 713
2526
682
2896 + 723
17 baseline
4193
4256
4121
4069
3158:1
Walker2d
Ours
6319 + 31
6309 +
5916
790
6085
620
5803 857
baseline
6294 + 203
6213 + 245
5310 + 185
5369
61
43281139
Halfcheetah
Ours
7095 +: 88
6297 471
5457 385
5089
86
4411 718
11 baseline
5617 1 174
5569 1 132
4347
170
3889
142
3246 T 303
Ant
Ours
5769 + 290
5630
146
4683
561
4524
79
4312 281
Table 3: Average episode rewards + standard deviation over 50 episodes with three baselines on Hopper, Walker2d, Halfchectah, and Ant. Here II baseline is used as baseline policy class for online adaptation.
This justifies that it is our novel Algorithm 2 for discovering a set of high-quality policies II that makes ours improve over baselines.
23


Reviews:
[{"review_id": "tbwMQblsou", "reviewer": "Reviewer_F1uH", "summary": "This paper proposes a method to address performance loss of robust reinforcement learning under weak or no adversarial attacks. To be more specific, they propose a method called PROTECTED, which first find a suitable finite set $\\tilde\\Pi$ of non-dominated policie during the training, and them adaptively select the policy at each time in a bandit-like way when testing. Empirical results are presented to backup the method.", "questions": "Based on Theorem 4.11, will the method be very likely to fail for infinite horizon MDP?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper proposes an interesting approach for robust reinforcement learning by adaptively switch among non-dominated policies. The definition of \"non-dominated policy\" seems new. The algorithm to discover $\\tilde{\\Pi}$ is non-trivial and might be considered in future studies.", "weaknesses": "Overall, the presentation of the current paper can be improved. I find the settings in Section 4 confusing. Specifically, please consider the followings.\n1. While the authors define a discount factor $\\gamma$ in Section 3 (which seems to be used in an infinite horizon MDP), it is not used in the rest of the paper, where a MDP with finite horizon $H$ is considered. Can the result be extended to infinite horizon?\n2. The authors propose the new regret in equation 4.1 that is based on the value function rather than reward. I feel it is not fully discussed why such a regret is appealing and how is it related with the commonly used reward-based regret.  \n3. Also in equation 4.1, it seems that the regret depend on the attacker policy $\\nu^t$ for each time $t$, where $\\nu^t$ can be arbitrary. Is this regret well-defined without further confining $\\nu^t$?\n4. In the paragraph below equation 4.1, the term $\\pi^tt\\in[T]$ seems like typo. Should it be {$\\pi_t: t\\in [T]$} instead?\n\nWith above issues (especially 2 & 3), I do not fully understand the setting considered in this paper and am unable to evaluate its theoretical contribution accurately.\n\nBesides, another weakness is pointed out by authors in Theorem 4.11 that suggests the size of $\\tilde{\\Pi}$ can be very large in some cases that is exponential in time horizon $H$.", "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": "W6eEqzgn8x", "reviewer": "Reviewer_M1op", "summary": "This paper proposes an approach to learning robust RL policies that improve robustness in the case of no attacks or weak attacks while still maintaining robustness against worst-case attacks. This approach entails adaptively picking policies at each time step from a fixed policy class in order to minimize a particular notion of regret. The fixed policy class is constructed during training with the aim of minimizing its size while minimizing regret-related optimality gaps compared to using the full policy class - notably, via discovery of non-dominated policies. The authors provide theoretical results on the hardness of the problem, optimality gaps between the fixed (refined) policy class and the full policy class, the regret of their algorithm, and the worst-case size of the refined policy class. They demonstrate empirical performance on four Mujoco environments with continuous action spaces (Hopper, Walker2d, Halfcheetah, and Ant) and show strictly improved performance against baselines across no-attack, non-worst-case-attack, and worst-case-attack scenarios.", "questions": "* Why is the notion of regret that is defined not overly weak?\n* Why are the experimental results not too good to be true? Are there any tradeoffs inherent in the method or results?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Formulation: The authors formulate an interesting and important task of improving RL performance against non-worst-case state-adversarial attacks, in addition to no attacks and worst-case state-adversarial attacks. They theoretically establish its difficulty, opening up an interesting line of future research.\n\nTheoretical results: While I did not check the proofs in detail, the authors seemingly present useful theoretical results regarding optimality gaps presented by the use of non-infinite policy classes, as well as the performance of their algorithm.\n\nEmpirical results: The empirical performance is strong, with comparison on several environments against several baselines and attack strategies.", "weaknesses": "Questions regarding definition of regret (Definition 4.2): It is unclear to me why the notion of regret does not allow $\\pi \\in \\Pi$ to be picked adaptively at each time step in the same way that $\\pi^t \\in \\Pi$ is picked adaptively. While this may not matter in the case of an infinite $\\Pi$ given that the adaptive policy is likely contained within $\\Pi$, once $\\Pi$ is restricted to $\\tilde{Pi}$ with finite cardinality, this may no longer be the case. In other words, I wonder whether the notion of regret used in this work may be too weak.\n\nQuestions regarding experimental results: While the aim of the paper is stated as improving performance against no attacks/non-worst-case adversarial attacks while *maintaining* performance against worst-case adversarial results, the empirical results show the proposed method *exceeding* performance against worst-case adversarial attacks compared to baselines (in some cases, substantially - see e.g. Walker2d vs. PA-AD). This seems to contradict \"no free lunch\" intuitions. The authors should further explain why we are seeing this behavior in the experiments (potentially through the use of ablation studies), and whether there are any tradeoffs.\n\nMinor points:\n* Section 3: $H$ does not seem to be defined\n* Section 3: Typo - \"discounted factor\" --> \"discount factor\"\n* Proposition 4.3: How does the choice of $\\alpha$ relate to the rest of the problem setup?", "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": "h03ntZJ8Oq", "reviewer": "Reviewer_t6xM", "summary": "This paper introduces the test-time adaptation idea to adversarial robustness of RL models. More specifically at training time instead of identifying a single fixed policy, the learner maintains a set of policies, and then at the test time, it adapts to a particular trajectory and then chooses a good policy to react.\n\nThe authors have also considered how to attack such adaptation defense in a clear way. And various experiments have demonstrated the superiosity of the framework.", "questions": "No specific questions, my main concerns have been stated above.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A novel and natural idea to introduce test-time adaptation to the RL. The authors have done a great job in carefully considering the security model, and discussed in detail how to attack such a test-time adaptation framework.\n\nThe authors have also discussed in details both theoretical and empirical evidence of the proposed framework, and it seems that this work can improve state of the art by a large margin.\n\nOverall I found this paper a really nice to read.", "weaknesses": "The part about adaptive attacks seem somewhat weak -- namely, if the adversary has more knowledge about the defender, what can happen? The paper does not really seem to have clearly formulated what adaptivity really means in this case. However, I think this could be a future direction, given that this paper already has some novel ideas.", "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": "DDyhUle1xA", "reviewer": "Reviewer_xB8p", "summary": "The authors consider the problem of synthesising policies for reinforcement learning (RL) that are both robust to adversarial perturbations and accurate to natural data. In particular, the authors propose an online adaptive framework that learns a finite set of policies that is used to ensure protection to adversarial attacks. The effectiveness of the approach of the authors is investigated on several standard RL benchmarks.", "questions": "See Weaknesses Section", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Finding robust policies that are not overly conservative is an important problem and of interest for the ICLR community\n\n- The approach proposed by the authors is promising and shows empirical improvements compared to state of the art.\n\n- The authors provide bounds on the regret of the proposed algorithm", "weaknesses": "- The paper is not well written. There are typos, some notation is not defined, and some parts are not very clear. Some examples:\n\na) in the definition of J(\\pi,v) ,in the first expectation, it is missing where z is sampled from. \nb) \\pi^tt is not defined (I guess you missed {}, but the same notation appears multiple times)\nc)The update rule for \\omega is not explained in the main text\nd) in the abstract and intro the authors talk about \"the importance of a finite and compact \\mathcal{\\PI}\", but any finite set is also compact.\ne) k in line 6 of Algorithm 2 not defined\n\n- In order to talk about optimality, convergence guarantees, and scalability, in Theorem 4.10, it would be important that the authors report an upper bound of K. \n\n- I am confused by the result in Table 1. From the results it seems that the proposed approach obtains higher rewards against worst case perturbations compared to methods explicitly trained against worst case perturbations. Am I missed something? In any case, a discussion on the results and about their interpretation should be given", "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 (spotlight)