COPA: Certifying Robust Policies for Offline Reinforcement Learning against Poisoning Attacks
Authors: Fan Wu
Linyi Li
Huan Zhang
Bhavya Kailkhura
Krishnaram Kenthapadi
Ding Zhao
Bo Li
Venue: ICLR 2022 Poster (2022)
Keywords: certified robustness
poisoning attacks
reinforcement learning

Abstract: As reinforcement learning (RL) has achieved near human-level performance in a variety of tasks, its robustness has raised great attention. While a vast body of research has explored test-time (evasion) attacks in RL and corresponding defenses, its robustness against training-time (poisoning) attacks remains largely unanswered. In this work, we focus on certifying the robustness of ofﬂine RL in the presence of poisoning attacks, where a subset of training trajectories could be arbitrarily manipulated. We propose the ﬁrst certiﬁcation framework, COPA, to certify the number of poisoning trajectories that can be tolerated regarding different certiﬁcation criteria. Given the complex structure of RL, we propose two certiﬁcation criteria: per-state action stability and cumulative reward bound. To further improve the certiﬁcation, we propose new partition and aggregation protocols to train robust policies. We further prove that some of the proposed certiﬁcation methods are theoretically tight and some are NP-Complete problems. We leverage COPA to certify three RL environments trained with different algorithms and conclude: (1) The proposed robust aggregation protocols such as temporal aggregation can signiﬁcantly improve the certiﬁcations; (2) Our certiﬁcations for both per-state action stability and cumulative reward bound are efﬁcient and tight; (3) The certiﬁcation for different training algorithms and environments are different, implying their intrinsic robustness properties. All experimental results are available at https://copa-leaderboard.github.io.

Published as a conference paper at ICLR 2022
CОРA: CERTIFYING ROBUST POLICIES FOR OF-
FLINE REINFORCEMENT LEARNING AGAINST POISON- ING ATTACKS
Fan Wui* Linyi Li Chejian Xu²
Huan Zhang"
Bhavya Kailkhura"
Krishnaram Kenthapadi Ding Zhao² University of Illinois at Urbana-Champaign
Bo Li
Carnegie Mellon University
'Lawrence Livermore National Laboratory {fanw6, 1inyi2,, chejian2, wwtoeeiliiieee..
*Amazon AWS AI
huan@huan-zzang.com
dingzhao@andrew. cmmu.ed
* Equal contribution.
ABSTRACT
As reinforcement learning (RL) has achieved near human-level performance in a variety of tasks, its robustness has raised great attention. While vast body of research has explored test-time (evasion) attacks in RI. and corresponding de- fenses, its robustness against training-time (poisoning) attacks remains largely unanswered. In this work, we focus on certifying the robustness of offline RL in the presence of poisoning attacks, where subset training trajectories could be arbitrarily manipulated. We propose the first certification framework, COPA, to certify the number poisoning trajectories that can be tolerated regarding dif- ferent certification criteria. Given the complex structure of RL, we propose two certification criteria: per-state action stability and cumulative reward bound. To further improve the certification, we propose new partition and aggregation pro- tocols to train robust policies. We further prove that some of the proposed certifi- cation methods are theoretically tight and some are NP-Complete problems. We leverage COPA to certify three RL environments trained with different algorithms and conclude: (1) The proposed robust aggregation protocols such temporal aggregation can significantly improve the certifications; (2) Our certifications for both per-state action stability and cumulative reward bound efficient and tight; (3) The certification for different training algorithms and environments are dif- ferent, implying their intrinsic robustness properties. All experimental results are available at https:: : //copa/cpaapo////a/ weader git.ub.b......... io
INTRODUCTION
Reinforcement learning (RL) has been widely applied to a range of applications, including robotics (Kober et al. 2013 Deisenroth al. 2013) Polydoros Nalpantidis, 2017) and tonomous vehicles (Shalev-Shwartza al. Sallab et al. 2017). In particular, offline RI. (Levine) al., (2000) is proposed leverage previously observed data train the policy without requiring expensive interaction with environments or online data collection, and enables the reuse of training data (Agarwal et al., 2020). However, offline RL also raises a great safety concern on poisoning attacks (Kiourti et al. 2020; Wang et al. 2020 2021). A recent survey of industry reports that data poisoning is significantly more concerning than other threats (Kumar al. 2020). For offline RL, the situation is even worse, and recent theoretical study shows that the robust offline RI. against poisoning attacks strictly harder problem than online RI. (Zhang al. 202T).
Although there are several empirical and certified defenses for classification tasks against poisoning attacks (Peri et al., 2020 Levine & Feizi 2021 Weber et al., 2020), it is challenging and shown ineffective to directly apply them to RL given its complex structure (Kiourti al. 2020). Thus, ro- bust offline RL against poisoning attacks remains largely unexplored with no mention of robustness certification. In addition. though some theoretical analyses provide general robustness bounds for RL, they either assume bounded distance between the learned and Bellman optimal policies or are limited to linear MDPs (Zhang et al. 2021). To the best of our knowledge, there is robust RI.

---

Published as a conference paper at ICLR 2022
method that is able to provide practically computable certified robustness against poisoning attacks. In this paper, we tackle this problem by proposing the first framework of Certifying robust policies for general offline RL against poisoning attacks (COPA).
Certification Criteria. One critical challenge in certifying robustness for offline RL is the certifi- cation criteria, since the prediction consistency is no longer the only goal as classification. We propose two criteria based on the properties of RL: per-state action stability and cumulative reward bound. The former guarantees that at a specific time, the policy learned with COPA will predict the same action before and after attacks under certain conditions. This is important for guarantecing the safety of the policy at critical states, egg. braking when seeing pedestrians. For cumulative reward bound, lower bound of the cumulative reward for the policy learned with COPA is guaranteed under certain poisoning conditions. This directly guarantees the worst-case overall performance.
CОРА Framework. COPA composed of two components: policy partition and aggregation protocol and robustness certification method. We propose three policy partition aggregation pro- tocols: PARL (Per-State Partition Aggregation), TPARL (Temporal Partition Aggregation), and DPARL (Dynamic Temporal Partition Aggregation), and propose certification methods for each of them corresponding to both proposed certification criteria. In addition, for per-state action stability, we prove that our certifications for PARI. and TPARI. are theoretically tight. For cumulative reward bound, we propose an adaptive search algorithm, where we compute the possible action set for each state under certain poisoning conditions. Concretely, we propose novel method to compute the precise action set for PARL and efficient algorithms to compute a superset the possible action set which leads to sound certification for TPARL and DPARL. We further prove that for PARL certification is theoretically tight, for TPARL the theoretically tight certification is NP-complete, and for DPARL it is open whether theoretically tight certification exists.
Technical Contributions. We take the first step towards certifying the robustness of offline RL against poisoning attacks, and we make contributions both theoretical and practical fronts.
We abstract and formulate the robustness certification for offline RL against poisoning attacks, and we propose two certification criteria: per-state action stability and cumulative reward bound.
We propose the first framework COPA for certifying robustness of offline RL against poisoning attacks. COPA includes novel policy aggregation protocols and certification methods.
We prove the tightness of the proposed certification methods for the aggregation protocol PARL.
We also prove the computational hardness of the certification for TPARL.
We conduct thorough experimental evaluation for COPA on different RL environments with three offline RL algorithms, demonstrating the effectiveness of COPA, together with several interesting findings.
RELATED WORK
Poisoning attacks (Nelson et al. 2008 Diakonikolas et al., 2016) are critical threats in machine learning, which are claimed to be more concerning than other threats (Kumar et al. 2020). Poisoning attacks widely exist in classification (Schwarzschild et al. 20 and both empirical defenses (Liu et al. [018 Chacon et al.) [0199] Peri et 2020
(teiinaaaaaa Steinhardt al. 2017 and certified defenses (Weber et al. 2020 Jia et al. 2020 Levine & Feizi] 2021) have been proposed.
(2020) show the existence of effective backdoor poisoning attacks in RL, a recent work theoretically and empirically validates the existence of reward poisoning in online RL (Zhang et al.] 2020b). Furthermore, Zhhnn al.] (202T) theoretically prove that the offline RL is more difficult to be robustified against poisoning than online RL considering linear MDP. From the defense side, Zhang et al. (202T) propose robust variants of the Least-Square Value Iteration algorithm that provides probabilistic robustness guarantees under linear MDP assumption. In addition, Robust RL against reward poisoning is studied in |Banhhahhem et al. (202I). but robust RL against general poisoning is less explored. In this background, we aim to provide the certified robustness for general offline RL. algorithms against poisoning attacks, which is the first work that achieves the goal. We discuss broader related work in Appendix
After Kiourti et al.
CERTIFICATION CRITERIA OF COPA
In this section, we propose two robustness certification criteria for offline RL against general poi- soning attacks: per-state action stability and cumulative reward bound.
2

---

Published as a conference paper at ICLR 2022
Offline RL. We model the RL environment by episodic finite-horizon Markov decision pro- cess (MDP) 3 = R. do), where is the set of states, A is the set of discrete actions, R S x A + I is the reward function, P : S A + P(S) is the stochastic transition function with P(.) defining the set of probability measures, H is the time horizon, and do E P(() is the distribution of the initial state. At time step I, the RI. agent is at state 8, 8. After choosing action P(s,, ax) and receives reward r, R[s,, az). After H time steps, the cumulative reward J f= Tt- We denote consecutive sequence of all states between time step / and as Strr = [st, S141...., s,].
ag E A, the agent transitions to the next state st+1 H111
Here focus on offline RL, for which the threat of poisoning attacks is practical and more chal- lenging to deal with (Zhang et al. 2021). Concretely, in offline RL, a training dataset D = { consists of logged trajectories, where each trajectory т = {(5). Fay aj (11,,,)) 8,) E (S x A x IR S) consists of multiple tuples denoting the transitions (i.e., starting from state 8.. taking the action ay. receiving reward ry, and transitioning to the next state sz)).
Poisoning Attacks. Training dataset D can be poisoned in the following manner. For each tra- jectory 7 E D. the adversary is allowed to replace it with an arbitrary trajectory 7. generating a manipulated dataset D. We denote De D = (D) U(DD) D) as the symmetric difference between two datasets D and D. For instance, adding or removing
trajectory causes symmetric differ- ence of magnitude 1, while replacing one trajectory with a new one leads to symmetric difference of magnitude 2. We refer to the size of the symmetric difference as the poisoning size.
Certification Goal. To provide the robustness certification against poisoning attacks introduced above, we aim to certify the test-time performance of the trained policy in clean environment. Specifically, in the training phase, the RI training algorithm and our aggregation protocol can be jointly modeled by M : 'D - (S+ A) which provides an aggregated policy, where S* denotes the set of all consecutive state sequences. Our goal is to provide robustness certification for the poisoned aggregated policy ã = MDD,, given bounded poisoning size (i.e., |D e D S K).
Robustness Certification Criteria: Per-State Action Stability. We first aim to certify the ro- bustness of the poisoned policy in terms of the stability of per-state action during test time.
Definition 1 (Robustness Certification for Per-State Action Stability). Given clean dataset D, define the robustness certification for per-state action stability as that for any D satisfying De s K, the action predictions of the poisoned and clean policies for the state (or state sequence) are the same, i.e., M(D), , ग M(D), (s) π (s)) under the the tolerable poisoning threshold K. In an episode, we denote the tolerable poisoning threshold for the state step t by K₃-
The definition encodes the requirement that, for a particular state, any poisoned policy will always give the same action prediction as the clean one, as long the poisoning size is within K (K computed in in|Section 4). this definition, s could be either a state or a state sequence, since our ag- gregated policy (defined in[Section33 3) may aggregate multiple recent states to make action choice.
Lower Bound of Cumulative Reward. We also aim to cer- tify poisoned policy's 's overall performance in addition to the prediction at particular state. Here measure the overall performance by the cumulative reward (TT) (formally defined in Appenddi A).
Robustness Certification Criteria:
Now we are ready to define the robustness certification for cumulative reward bound.
Definition (Robustness Certification for Cumulative Reward Bound). Robustness certification for cumulative reward bound is the lower bound of cumulative reward Ju such that dx S (+) for any मे M(D where D DI < K, Le., से is trained on poisoned dataset D within poisoning size K.
4 CERTIFICATION PROCESS OF COPA
In this section, we introduce our framework COPA, which is composed of training protocols, ag- gregation protocols, and certification methods. The training protocol combined with an offline RL training algorithm provides subpolicies. The aggregation protocol aggregates the subpolicies as an aggregated policy. The certification method certifies the robustness of the aggregated policy against poisoning attacks corresponding to different certification criteria provided in Section 3
3

---

Published as a conference paper at ICLR 2022
Table 1: Overview of theoretical results in incetioon "Certification" columns entail our certification theorems.
"Analysis" columns entail the analyses of our certification bounds, where "tight" means our certification is theoretically tight, "NP-con timmoleeeee" means the tight certification problem is NP-complete, and "open" means the tight certification problem is still open. Theorems 8 andd 13 proposiioonoonnn 9 are in Appendices Cand JandFFo F.6.2
Certilication Criteria
Proposed Aggregation Protocol
PARL (Ep
Definition 7
TPARI.(sy
Definition 8
DPARI-(FT Certification
Definition
Certification
Analysi
Certification
Analyss
Analyss
StalStatte Action
Thevrem
right
Propostion
Theorem
tight Proposition 2
Theorem
open
Cumulative Reward
Theoreen
Lihht
Theorem 13
Theorem
NP-compiete
Theorem 6
Thearem
open
Overview of Theoretical Results. In Table we present an overview of our theoretical results: For each proposed aggregation protocol and certification criteria, we provide the corresponding cer- tification method and core theorems, and we also provide the tightness analysis for each certification.
4.1 PARTITION-BANE
TRAINING PROTOCOL
COPA's 's training protocol contains two stages: partitioning and training. We denote D as the entire offline RL training dataset. We abstract an offline RL training algorithm (e.g., DQN) by MM 2 - II, where 2D the power set of D, and II { S - A} is the set of trained policies. Each trained policy in II is function mapping given state to the predicted action.
Partitioning Stage. In this stage, we separate the training dataset D into u partitions { that satisfy UH D; = D and vi & j.D, = 0. Concretely, when performing partitioning, for each trajectory T E D, we deterministically assign it to one unique partition. The assignment is only dependent on the trajectory itself, and not impacted by any modification to other parts of the training set. One design choice of such a deterministic assignment is using deterministic hash function h to compute the assignment, ie.,, D; = (r E D h(T) = i (mod w) vi [u].
Training Stage. In this stage, for each training data partition D;, we independently apply an Mo D:). Hereinafter, we call these trained polices as
RL algorithm Mg to train a policy subpolicies to distinguish from the aggregated policies. Concretely, let [u] := (0. 1....,
,, u 1}. For
these subpolicies, the policy indicator 1,,0 S + {0,1} is defined by (s, = ((m
a),
indicating whether subpolicy Ty chooses action a at state s. The aggregated action count nu : S Nzo is the number of votes across all the subpolicies for action given state 8: nh (8) = (z)
a, E [u]]| = E i (s). Specifically, we denote n., (st..) for Σ/- n. (s,) ), i.e., the sum of votes for states between time step I and A detailed algorithm of the training protocol is in Appendix E.
Now we are ready to introduce the proposed aggregation protocols in COPA (PARL, TPARL, DPARL) that generate aggregated policies based on subpolicies, and corresponding certification.
4.2 AGGREGATION PROTOCOLS: PARL, TPARL, DPARL
With learned subpolicies 1 we propose three different aggregation protocols in COPA to form three types of aggregated policies for each certification criteria: PARL, TPARL, and DPARL.
Per-State Partition Aggregation (PARL). Inspired by aggregation in classification Levinne & Feizi 2021). PARL aggregates subpolicies by choosing actions with the highest votes. We denote the PARL aggregated policy by .P S + A.. When there are multiple highest voting actions, we break ties deterministically by returning the "smaller" (<) action, which can be defined by numeri- cal order, lexicographical order, etc. Throughout the paper, we assume arg max over AA always uses operator to break ties. The formal definition of the protocol is in Appendix A
The intuition behind PARL is that the poisoning attack within size K can change most K sub- policies. Therefore, as long as the margin between the votes for top and runner-up actions is larger than 2K for the given state, after poisoning, we can guarantee that the aggregated PARL policy will not change its action choice. We will formally state the robustness guarantee in Section 4.3
Temporal Partition Aggregation (TPARL). In the sequential decision making process of RL, it is likely that certain important states are much more vulnerable to poisoning attacks, which we refer to as bottleneck states. Therefore, the attacker may just change the action predictions for these bottleneck states to deteriorate the overall performance, say, the cumulative reward. For example, in Pong game, we may lose the round when choosing an immediate bad action when the ball is closely approaching the paddle. Thus, to improve the overall certified robustness, need to focus
4

---

Published as a conference paper at ICLR 2022
on improving the tolerable poisoning threshold for these bottleneck states. Given such intuition and goal, we propose Temporal Partition Aggregation (TPARL) and the aggregated policy is denoted as TT, which is formally defined in Definition in Appendix A.
TPARL is based on two insights: (1) Bottleneck states have lower tolerable poisoning threshold, which is because the vote margin between the top and runner-up actions is smaller such state; (2) Some RL tasks satisfy temporal continuity (Legenstein et al.) 2010 Veerapaneni et al.) 2020), indicating that good action choices are usually similar across states adjacent time steps, i.e. adjacent states. Hence, we leverage the subpolicies" votes from adjacent states to enlarge the vote margin, and thus increase the tolerable poisoning threshold. To this end, in TPARL, we predetermine a window size W, and choose the action with the highest votes acToss recent W states.
Dynamic Temporal Partition Aggregation (DPARL). The TPARL uses fixed window size W across all states. Since the specification of the window size W requires certain prior knowledge, plus that the same fixed window size W may not be suitable for all states, is preferable to perform dynamic temporal aggregation by using flexible window size. Therefore, we propose Dynamic Temporal Partition Aggregation (DPARL), which dynamically selects the window size W towards maximizing the tolerable poisoning threshold per step. Intuitively, DPARL selects the window size W such that the average vote margin over selected states is maximized. To guarantee that only recent states are chosen, we further constrain the maximum window size (Wmax).
Definition (Dynamic Temporal Partition Aggregation), Given subpolicies (m:) u-1 and maximum window size W maxx, at time step f. the Dynamic Temporal Partition Aggregation (DPARL) defines an aggregated policy TD Smmin(t+1, [mmx) + A such that
TDD (Smax(t- Wmax 1.0):a) == arg max The (w-)) where W' "EAA
arg max
AW
(1)
15W Smin Bouln (1)
In the above equation, n, is defined in Section and AW is given by
A
W. (May (st (1.)) Bag (st (S.-W)):)).
where
arg max The (= = arg max na ma(se-w+1)). aEA,t00
REAA
In the above definition, AW encodes the average vote margin between top action a and runner-up action 02 if choosing window size W. Thus, W' locates the window size with maximum average vote margin, and its corresponding action is selected. Again, we use the mechanism described in PARL to break ties. Robustness certification methods for DPARL are in Secetion 4.3) and 4.4
In Anppendii B we present a concrete example demonstrate how different aggregation protocols induce different tolerable poisoning thresholds, and illustrate bottleneck and non-bottleneck states.
4.3 CERTIFICATION OF PER-STATE ACTION STABILITY
In this section, we present our robustness certification theorems and methods for per-siate action. For each of the aggregation protocols (PARL, TPARL, and DPARL), at each time step t, we will compute valid tolerable poisoning threshold K defined in Definition 1, such that the chosen action at step t does not change as long as the poisoning size K K.
Certification for PARL. Due to the space limit, defer the robustness certification method for PARL to Appendix C The certification method is based on Theorem 8) We further show the theo- retical tightness of the certification in Proposition 9 All the theorem statements are in Appendix C
Certification for TPARL. We certify the robustness of TPARL. following Theorem
Theorem 1. Let D be the clean training dataset; let n. =
be the learned
subpolicies according to Section 4.1 from which we define nu (Section 3) and let let be the Temporal Partition Aggregation policy: тт M(D) where M abstracts the whole muining-aggregatie process. Đ a poisoned dataset and का is the poisoned policy: का = M(D).
For given state 8t encountered at time step I. during test time, let a == TT((mox(( 1,000)))) then at time step f the tolerable poisoning threshold (see Definition 7)
K.
min
max p
Σ a.a S Sa
(3)
a'Fa,a'EA
5

---

Published as a conference paper at ICLR 2022
where Vi a f is a nonincreasing permulation of
min (W- -1.0)
min[W -143
Σ 3=0
+ minn
ah him
(4)
and 8 = The (Smaxit (#mmx((-W++100x -+1.00:e) - (na (Sna(mmaxte (aaxx(--++o0fp + l[a' im0 a)). Here, 1;,(8) 1 [s)(s)= = a) (Section 3), and W the window size.
==
Remark. We defer the detailed proof to Appendix F.2 The theorem provides per-state action certification for TPARL. The detailed algorithm in Algorithm 3 Appendix E.2). The certification time complexity per state is ([|AA) (W(WWWWWWWW + +log u)) and can be further optimized to ([AA|u log u) with proper prefix sum caching across time steps. We prove the certification for TPARL. theoretically tight in Proposition 2] (proof in Apppendix F.3). We also prove that directly extending Theorem 8 for TPARL (Corollary 10p is loose in Appendixx F.4
Proposition 2. Under the same condition as Theorem 1. for any time step t, there exists an RL learning algorithm Mo. and a poisoned dataset D, such that ID a D Ke+ 1, and (t- + (=t"mmx(ttW-+1100)
Certification for DPARL. Theorem 3 provides certification for DPARL.
Theorem 3. Let D be the clean training dataset; let म. = Mo(DD) ( u-su-i Osisu-1 be the learned
subpolicies according to /ecction 4.7 4.7 from which we define na (see Section 3); and let aD be the Dynamic Temporal Purtition Aggregation: TD = MMD) where M abstracts the whole training- aggregation process. D is poisoned dataset and TD is the poisoned policy: FD = MMD).
For given state St encountered at time step i. during test time, let := TD( #D(5max(t-WW mase +1 +100ga) and W be the chosen time window (according to Equation (1), then tolerable poisoning threshold KP
min Kt,
min 1<W" Smin (Waae. WW 4W aa ta,a" th L'a'a""
I. IW",W" WW'
(5)
where K2 is defined by Equation (3)
with W W' and L a.a"
W defined by the below Definition 4
Definition (L in Theorem 3). Under the same condition as Theorem 3) for given W W a,
W'., a, a'""
we let a # arg max ag A.E Bap (se-w++1:)) then
. a a' = max
g + W' W - W' (' W m. 1[a > >a <0 (6)
where n a shorthand of na Ma(St-w41:) and (g (1) Jimi is nonincreasing permutation of {= Each gi is defined by
max (W" w')
9
(mT max o (uo) - (TT (8)- where agEA
o"((a))- =- W' (gg - a', w S W
W'llag w W W*1(a) - a, S W + W* a", w s W").
Proof sketch. A successful poisoning attack should change the chosen action from to an another a'. If after attack, the chosen window size is still W the poisoning size should be at least larger than K, according to Theorem I If the chosen window size is not W', we find out that the poisoning size
least min L. ,""
W +1 from greedy-based analysis. Formal proof in Appendix F.5 LI
Remark. The theorem provides a valid per-state action certification for DPARL policy. The de- tailed algorithm is in Algorithm 4 (Appendix E.2). The certification time complexity per state is O |A u W Wmax Al '1lluoog log u) which in practice adds similar overhead compared with TPARL certification (sce Appendix H.3). Unlike certification for PARL and TPARL, the certification given by Theorem 3) is not theoretically tight. An interesting future work would be providing a tighter per-state action certification for DPARL.
4.4 CERTIFICATION OF CUMULATIVE REWARD BOUND
In this section, we present our robustness certification for cumulative reward bound. We assume the deterministic RL environment throughout the cumulative reward certification for convenience, i.e., the transition function is P S x A + S and the initial state is a fixed 50 E S. The certification goal, as listed in Detinition 6 is to obtain a lower bound cumulative reward under poisoning attacks, given bounded poisoning size K. The cumulative reward certification is based a novel adaptive search algorithm SEARCH inspired from Wu et al. (2022); we tailor the algorithm to certify against poisoning attacks. We defer detailed discussions and complexity analysis to Appendix H.3

---

Published as a conference paper at ICLR 2022
COPA-SEARCH Algorithm Description. The pseudocode is in Algorithm 5 (Appendix E.3) The method starts from the base case: when the poisoning threshold Keur = 0, the lower bound of cumulative reward Jk... is exactly the reward without poisoning. The method then gradually increases the poisoning threshold Kour, by finding the immediate larger K' >> Keur that can expand the possible action set along the trajectory. With the increase of Keur + K', the attack may cause the poisoned policy स to take different actions at some states, thus resulting in new trajectories. We need to figure out a set of all possible actions to exhaustively traverse all possible trajectories. We will introduce theorems to compute this set of possible actions. With this set, the method effectively explores these new trajectories by formulating them as expanded branches of trajectory tree. Once all new trajectories are explored, the method examines all leaf nodes of the tree and figures the minimum reward among them, which is the new lower bound of cumulative reward _ under new poisoning size K'. We then repeat this process of increasing poisoning size from K' and expanding with new trajectories until we reach a predefined threshold for poisoning size K.
Definition 5 (Possible Action Set). Given previous states So:t, the subpolicies { the aggre- gation protocol (PARL. TPARL, or DPARL), and the poisoning size K, the possible action set A step is a subset of action space: S. A, such that for any poisoned policy म. long as the poisoning size is within K, the chosen action at step ł will always be in A, i.e., ag = =(50a) E A.
Possible Action Set for PARL. The following theorem gives the possible action set for PARL.
Theorem (Tight PARL Action Set). Under the condition of Definition 5] suppose the aggregation protocol is PARL as defined in Definition 7 then the possible action set at step
(K) = a AEA
Σ
max((ar - (s:) - K + 1 < a}.0) S K
(8)
a'EAA
We defer the proof to Appendix F.6.1] Furthermore, in Appendix F.6.2 we show that: 1) The theo-
rem gives theoretically tight possible action set; 2) In contrast, directly extending PARL's ptr-state certification gives loose certification.
The following theorem gives the possible action set for TPARL. Theorem 5. Under the condition of Desimition 5] suppose the aggregation protocol is TPARL as defined in Definition 8 then the possible action set at step I
Possible Action Set for TPARL.
K
A(K) = a CEEA
Σ
N Swla: Va' # #a
(6) where a' and 8 follow the definition in Theorem 1
We defer the proof to Appendix F.7. The possible action set here is no longer theoretically tight. Indeed, the problem of computing possible action set with minimum cardinality for TPARL is NP-complete as we shown in the following theorem (proved in Appendix F.8), where we reduce computing theoretically tight possible action set to the set cover problem (Karp) 1972). This result can be viewed as the hardness of targeted attack. In other words, the optimal untargeted attack on TPARL can be found in polynomial time, while the optimal targeted attack on TPARL is NP- complete, which indicates the robustness property of proposed TPARL.
Theorem 6. Under the condition of Definition 5, suppose we use TPARL (Definition 8 as the ag- gregation protocol, then computing a possible action set A(K) such that any possible action set S satisfies [A(K) S |S] is NP NP-complete.
The following theorem gives the possible action set for DPARL. Theorem 7. Under the condition of Definition 5) suppose the uggregation protocol is TPARL as defined in Definition 3 then the possible action set al step I
Possible Action Set for DPARL.
A(K) = (a.f u d' d'e.
min 18W Sainal (W d+.. W" 4w" aa for
W S SK
U DE
Vo #a
(10)
where =TD (T Wias 1.0)a)) ) is the clean policy's 's chosen action, W is defined by Equa- tion (1) " WW'WW' is defined by Definition 4 4 a being replaced by a, and h ar Sw a is defined in Theorem with W replaced by W'.
We prove the theorem in Appendix F.8 As summarized in Table 1 we further prove the tightness or hardness of certification for PARL and TPARL, while for DPARL it is an interesting open problem on whether theoretical tight certification is possible in polynomial time.
7

---

Published as a conference paper at ICLR 2022
TPARL (W-4)
DPARL
Freeway, 50
Breakout, 50
Highway, 50
DQN stability ralio
1.0
1.0
0.6
04
0.2
0.0
41
4,
CSL Stabiity ratio stabiity ralio
QR-DQN
0.8
0.4
0.4
0.2
0.2
0.0
0.0
1.0
6 0. R. 9. 88
0.8
0.6
0.6
0.4
UA
02
0.0
10
10
K
2 K
K
Figure 1: Robustness certification for per-state action stability. We plot the cumulative histogram of the tolerable poisoning size K for time steps. We provide the certification for different aggregation protocols (PARL, TPARL, DPARL) on three environments and #partitions u = 50. The results are averaged over 20 runs with the vertical bar on top denoting the standard deviation.
5 EXPERIMENTS
In this section, we present the evaluation for COPA framework, specifically, the aggregation protocols (Section 4.2) and the certification methods under different certification criteria (Sec- tions 4.3) 4.4 We defer the description of the offline RI. algorithms (DQN (Mnih al. 2013).
QR-DQN (Dabney et al. (2188). and C51 (Bellemare et al. (017)) used for training the subpolicies to Appendix G.T and the concrete experimental procedures to Appenddi G.2 As summary, we obtain similar conclusions from per-state action certification and reward certification: 1) QR-DQN and C51 are oftentimes more certifiably robust than DQN: 2) temporal aggregation (TPARL and DPARL) achieves higher certification for environments satisfying temporal continuity, e.g., Freeway; 3) larger partition number improves the certified robustness; 4) Freeway is the most stable and robust environment among the three. More interesting discussions are deferred to Appendixx H
5.1 EVALUATION OF ROBUSTNESS CERTIFICATION FOR PER-S STATE ACTION STABILITY
We provide the robustness certification for per-state action stability based on Section 4.3
Experimental Setup and Metrics. We evaluate the aggregated policies TP, TT. and TD following Section 4.2 Basically, in each run, we run one trajectory (of maximum length H) using the derived policy, and compute K, each time step t. Given Ho! obtain cumulative histogram- for each threshold K, count the time steps that achieve threshold no smaller than it and then normalize, i.e., Σn'1 K//HH We call this quantity stability ratio since it reflects the per-state action stability w.r.t. given poisoning thresholds. We also compute an average tolerable poisoning thresholds for a trajectory, defined as E K./H. More details are deferred to Appendix G.2
Evaluation Results. We present the comparison of per-state action certification for different RL methods and certification methods in Figure I] We plot partial poisoning thresholds on the T-axes here, and omit full results in Appendix H.6 where we also report the average tolerable poisoning thresholds. We additionally report benign empirical reward and the comparisons with standard training in AAppendices H.T and H.2 as well as more analytical statistics in AAppendices H.3 and H.4
The cumulative histograms in Figure I can be compared in different levels. Basically, we compare the stability ratio at each tolerable poisoning thresholds K K-higher ratio at larger poisoning size indicates stronger certified robustness. On the RL algorithm level, QR-DQN and C51 consistently outperform the baseline DQN, and C51 has a substantial advantage particularly in Highway. On the aggregation protocol level, we observe different behaviors in different environments. On Freeway, methods with temporal aggregation (TPARL and DPARL) achieve higher robustness, and DPARL achieves the highest certified robustness in most cases; while on Breakout and Highway, the single- step aggregation PARL is oftentimes better. This difference is due to the different properties of environments. Our temporal aggregation is developed based the assumption of consistent action
8

---

Published as a conference paper at ICLR 2022
d 30, PARL
3-30, TPARL IW
u- DPARL 11 5)
1. 50, TPARL IW
50, DPARL (Wrac 5)
Freeway, 200
Freeway, 400
Breakont, 50
Breakont,
Highway, 30
DQN
15
10
15
20
25
15
20
25
0
9
12
15
18
21
0
5
1.0
15
20
25
QR-DON
20
10
20
15121222
25
20
5-11
20 25
15 20 25 6 1512212427
5 10
5 15 20 25
Poisoning size
Poisoning size X
Poisoning size
Poisoning size K
Poisoning size K
Figure 2: Robustness certification for cumulative reward. We plot the lower bound of cumulative reward
bound Lx w.r.t poisoning size K under three aggregation protocols (PARL, TPARL (W = 4), DPARL (Wmax= = 5)) with two #partitions u, evaluated on three environments with different horizon lengths H.
selection in adjacent time steps. This assumption is true in Freeway while violated in Breakout and Highway. A more detailed explanation of environment properties is omitted to Appendix H.5 On the partition number level, a larger partition number generally allows larger tolerable poisoning thresholds as shown in Appenddi H.6 Finally, on the RL environment level, Freeway achieves much higher certified robustness for per-state action stability than Highway, followed by Breakout, implying that Freeway is an environment that accommodates more stable and robust policies.
5.2 EVALUATION OF ROBUSTNESS CERTIFICATION FOR CUMULATIVE REWARD BOUND
We provide the robustness certification for cumulative reward bound according to SScctinn 4.4
Experimental Setup and Metrics. We evaluate the aggregated policies Tp, TT, and TD follow- ing Theorem 4 Theorem 3) an Theoreme We compute the lower bounds of the cumulative reward Lk w.r.t. the poisoning size K using the COPA-SEARCH algorithm introduced in /Section 4.4 We provide details of the evaluated trajectory length along with the rationales in Appendix G.2
Evaluation Results. We present the comparison of reward certification for different RL algorithms and certification methods in Figure 2] Essentially, at each poisoning size K, we compare the lower bound of cumulative reward achieved by different RL algorithms and certification value of the lower bound implies stronger certified robustness. On the RL algorithm level, QR- DQN and C51 almost invariably outperform the baseline DQN algorithm. On the aggregation protocol level, methods with temporal aggregation consistently surpass the single-step aggregation PARL. on Freeway but not the other two, as analyzed in infecioo 5.1 In addition, we note that DPARL. is sometimes not as robust as TPARL. We hypothesize two reasons: 1) the dynamic mechanism is more susceptible the attack, e.g., the selected optimal window size is prone to be manipulated; 2) the lower bound is looser for DPARL given the difficulty of computing the possible action set in DPARL (discussed in Theorem 7). On the partition number level, a larger partition number (u = 50) demonstrates higher robustness. On the horizon length level, the robustness ranking of different policies is similar under different horizon lengths with slight differences, corresponding to the property of fnite-horizon RL. On the RL environment level, Freeway can tolerate larger poisoning size than Breakout and Highway. More results and discussions are in Apppeddix H.7
6 CONCLUSIONS
In this paper, we proposed COPA, the first framework for certifying robust policies for offline RL against poisoning attacks. COPA includes three policy aggregation protocols. For each aggregation protocol, COPA provides sound certification for both per-state action stability and cumulative reward bound. Experimental evaluations on different environments and different offline RL training algorithms show the effectiveness of our robustness certification in wide range of scenarios.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work is partially supported by the NSF grant No. 1910100, NSF CNS 20-46726 CAR, Alfred P. Sloan Fellowship, the U.S. Department of Energy by the Lawrence Livermore National Laboratory under Contract No. DE-AAC2-07NA27344 and LLNL LDRD Program Project No. 20-ER-014, and Amazon Research Award.
this paper, we prove the first framework for certifying robust policies for offline RI. against poisoning attacks. On the one hand, such framework provides rigorous guaran- tees in practice RL tasks and thus significantly alleviates the security vulnerabilities of offline RL algorithms against training-phas provides a better understanding about the different degrees of security vulnerabilities across differ- ent RL algorithms. On the other hand, the robustness guarantee provided by framework only holds under specific conditions of the attack. Specifically, we require the attack to change only a bounded number of training trajectories. Therefore, users should be aware of such limitations of our framework, and should not blindly trust the robustness guarantee when the attack can change large number of training instances or modify the training algorithm itself. As result, researchers to understand the potential risks, and evaluate whether our constraints on the attack align with their usage scenarios when applying our COPA real-world applications. We do not expect any ethics issues raised by our work.
Ethics Statement.
poisoning attacks. The evaluation of different RL algorithms also
encourage
Reproducibility Statement. All theorem statements are substantiated with rigorous proofs in Ap- pendix F. In Appendix E, we list the pseudocode for all key algorithms. Our experimental eval- uation is conducted with publicly available OpenAl Gym toolkit (Brockman et al.) 2016). We introduce all experimental details in both [Section 5) and [pppnddx GJ Specifically, code upon the open-source code base of Agarwal et al. (2020), and we upload the source code at https://github. how.hhubb.com///a www.e/////t./ee///////eoee swwure COPA for reproducibility purpose.
build the
REFERENCES
Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective offline reinforcement learning. In International Conference on Machine Learning, 2020.
Ilge Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, et al. Solving rubik's cube with robot hand. arXiv preprint arXiv: 191.:01110.7// 13, 2019.
Kiarash Banihashem, Adish Singla, and Goran Radanovic. Defense against reward poisoning attacks in reinforcement learning. arXiv preprint arXiv:2102.0577,, 2021.
Vahid Behzadan and Arslan Munir. Whatever does not kill deep reinforcement learning, makes it stronger. arXiv preprint arXiv:1712.09344 2017.
Vahid Behzadan and Arslan Munir. Mitigation of policy manipulation attacks on deep g-networks with parameter-space space noise. In International Conference on Computer Safery, Reliability, and Security, pp. 406 417. Springer, 2018
Mare G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective reinforcement learning. In International Conference on Machine Learning, pp. 449-458. PMLR, 2017.
Richard Bellman. Dynamic programming. Science, 153(3731):34-377 1966.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv:1606.01540 2016.
Henry Chacon, Samuel Silva, and Paul Rad. Deep learning poison data attack detection. In 2019 IEEE 31 International Conference on Tooly with Artificial Intelligence (ICTAI), pp. 971-978. IEEE, 2019.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference Machine Learning, pp. 1310-1320. PMLR, 2019.
10

---

Published as a conference paper at ICLR 2022
Will Dabney, Mark Rowland, Marc G Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. In Thirty- Searry--ecoodd AAAI Conference on Artificial Intelligence, 2018.
Mare Peter Deisenroth, Gerhard Neumann, Jan Peters, al. A survey on policy search for robotics. Foundations and trends in Robotics, 2 2(1-2):388-403, 2013.
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators in high dimensions without the computational intractability. In 57th Annual Symposium on Foundations of Computer Science, pp. 655-664, Institute of Electrical and Elec- tronics Engineers (TEEE), 2016.
Michael Everett, Björn Lütjens, and Jonathan P How. Certifiable robustness to adversarial state uncertainty in deep reinforcement learning. IEEE Transactions Neural Networks and Learning Systems, 2021.
Marc Fischer, Matthew Mirman, Steven Stalder, and Martin Vechev. Online robustness training for deep reinforcement learning. arXiv preprint arXiv:191..00850 2019.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. arXiv preprint arXiv: /706. /0295, 2017.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Ue- sato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint arXiv:1810.1277 2018.
IEEE Computer Society. Standards Committee. Working group of the Microprocessor Stan- dards Subcommittee and American National Standards Institute. IEEE standard for binary floating-poin arithmetic, volume 754. IEEE, 1985.
Dan Hendrycks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adver- sarial examples. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15262-15271, 2021.
Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial attacks on neural network policies. arXiv preprint urXiv:1702.02256 2017.
Yunhan Huang and Quanyan Zhu. Deceptive reinforcement learning under adversarial manipula- tions cost signals. In International Conference Decision and Game Theory for Security, pp- 217-237. Springer, 2019.
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of nearest neighbors against data poisoning attacks. arXiv preprint arXiv:2012.03765, 2020.
Richard M Karp. Reducibility among combinatorial problems. Complexity of computer compu- lations, pp. 85-103. Springer, 1972.
Panagiota Kiourti, Kacper Wardega, Susmit Jha, and Wenchao Li. Trojdrl: evaluation of backdoor attacks on deep reinforcement learning. In 2020 57th ACM/IEEE Design Automation Conference (DAC), pp. 1-6. IEEE, 2020.
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey, The International Journal of Robotics Research, (2(11))22881124, 2013.
Jernej Kos and Dawn Song. Delving into adversarial attacks on deep policies. arXiv preprint arXiv: 100.10005..55... 2017.
Ram Shankar Siva Kumar, Magnus Nyström, John Lambert, Andrew Marshall, Mario Goertzel, Andi Comissoneru, Matt Swann, and Sharon Xia. Adversarial machine lcarning-indus industry per- spectives. In 2020 IEEE Security and Privacy Workshops (SPW), pp. 69-75. IEEÉ, 2020.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFF, 86(1)) (1(1):2227-2324 1998.
11

---

Published as a conference paper at ICLR 2022
Robert Legenstein, Niko Wilbert, and Laurenz Wiskott. Reinforcement learning slow features of high-dimensional input streams. PLoS computational biology, 100)844, 2010.
Edouard Leurent. An environment for autonomous driving decision-making. https://githhl/
/ env 2018.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. International Conference on Learning Representations, 2020.
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against gen- eral poisoning attacks. In International Conference on Learning Representations, 2021. URL
htttss:/oppereviien net.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives on open problems. arXiv preprint arXiv:2005.0166 2020.
Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg. Fine-pruning: Defending against back- dooring attacks deep neural networks. In International Symposium on Research in Attacks, Intrusions, and Defenses, pp. 273-294. Springer, 2018.
Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Xiaojin Zhu. Policy poisoning in batch reinforcement learning and control. Advances in Neural Information Processing Systems, 2019.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint 17Xiv:1706.0660 2017.
Matthew Mirman, Timon Gehr, and Martin Vechev. Differentiable abstract interpretation for prov- ably robust neural networks. In International Conference on Machine Learning, pp. 3578-3586. PMLR, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
Blaine Nelson, Marco Barreno, Fuching Jack Chi, Anthony D Joseph, Benjamin IP Rubinstein, Udam Saini, Charles Sutton, J Doug Tygar, and Kai Xia. Exploiting machine learning to subvert your spam filter. LEET, 8:1-9, 2008
Tuomas Oikarinen, Tsui-Wei Weng, and Luca Daniel. Robust deep reinforcement learning through adversarial loss. arXiv preprint arXiv:2008. 01976, 2020.
Anay Pattanaik. Zhenyi Tang. Shuijing Liu, Gautham Bommannan, and Girish Chowdhary. Ro- bust deep reinforcement learning with adversarial attacks. In 17th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2018, pp. 2040-2042. International Foun- dation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2018.
Nechar Peri, Neal Gupta, W Ronny Huang, Liam Fowl. Chen Zhu, Soheil Feizi, Tom Goldstein, and John P Dickerson. Deep k-nn defense against clean-label data poisoning attacks. European Conference on Computer Vision, pp. 55-70. Springer, 2020.
Athanasios S Polydoros and Lazaros Nalpantidis. Survey of model-based reinforcement learning: Applications on robotics. Journal of Intelligent Robotic Systems, 86(2):153-177 173, 2017.
Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via environment poisoning: Training-ting adversarial attacks against reinforcement learning. In International Conference on Machine Learning, pp. 7974-7984. PMLR, 2020.
Ahmad EL Sallab, Mohammed Abdou, Etienne Perot, and Senthil Yogamani. Deep reinforcement
learning framework for autonomous driving. Electronic Imaging, 2017(19):70-76, 2017.
Hadi Salman, Greg Yang. Jerry Li, Pengchuan Zhang, Huan Zhang, llya Razenshteyn, and Sébastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. In Pro- ceedings of the 33rd International Conference on Neural Information Processing Systems, pp- 11292- 1303, 2019.
12

---

Published as a conference paper at ICLR 2022
Avi Schwarzschild, Micah Goldblum, Arjun Gupta, John P Dickerson, and Tom Goldstein. Just how toxic is data poisoning? unified benchmark for backdoor and data poisoning attacks. In International Conference Machine Learning, pp. 9389-9398, PMLR, 2021.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv: 2016.
Jacob Steinhardt, Pang Wei Koh, and Percy Liang. Certified defenses for data poisoning attacks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp- 3520-3532, 2017.
Yanchao Sun, Da Huo, and Furong Huang. Vulnerability-wware poisoning mechanism for online [rl} with unknown dynamics. In International Conference on Learning Representations, 2021. URL httphhss///ppeeeeeeeeee net htte:/oooommmnnnmeoeA0
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Do- main randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pp. 23-30. IEEE, 2017.
Rishi Veerapaneni, John D Co-Reyes, Michael Chang, Michael Janner, Chelsea Finn, Jiajun Wu, Joshua Tenenbaum, and Sergey Levine. Entity abstraction in visual model-based reinforcement learning. In Conference Robot Learning, pp. 43591 PMLR, 2020.
Lun Wang, Zaynah Javed, Xian Wu, Wenho Guo, Xinyu Xing, and Dawn Song. Backdoorl: Back- door attack against competitive reinforcement learning. arXiv preprint trXiv:2105.0057: 2021.
Yue Wang, Esha Sarkar, Wenging Li, Michail Maniatakos, and Saif Eddin Jabari. Stop-and-ge -o: Ex- ploring backdoor attacks on deep reinforcement learning- saaedd traffic congestion control systems. arXiv preprint arXiv:2003.0788. 2020.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-25) 292, 1992.
Maurice Weber, Xiaojun Xu, Bojan Karlas, Ce Zhang, and Bo Li. Rab: Provable robustness against backdoor attacks. arXiv preprint arXiv:2003.0800 08904, 2020.
Lily Weng, Huan Zhang, Hongge Chen, Zhao Song, Cho-Jui Hsich, Luca Daniel, Duane Boning, and Inderjit Dhillon. Towards fast computation of certified robustness for relu networks. In International Conference Machine Learning, pp. 5276-5285. PMLR, 2018.
Fan Wu, Linyi Li. Zijian Huang, Yevgeniy Vorobeychik, Ding Zhao, and Bo Li. Crop: Certify- ing robust policies for reinforcement learning through functional smoothing. In International Conference Learning Representations, 2022.
Weirui Ye, Shaohuai Liu, Thanard Kurutach, Pieter Abbeel, and Yang Gao. Mastering atari games with limited data. Advances in Neural Information Processing Systems, 34, 2021.
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 obser- vations. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 21024-21037. Curran Asso- ciates, Inc., 2020a. URL httpttts//////ccednnnee 1 4baeaaaeeae22909033344444------3
neurips wwtp.ett.wepppppppeeeeeeee.ee pc/ppaperr/222//ieeee pdf
Xuezhou Zhang, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. Adaptive reward-poisoning attacks against reinforcement learning. In International Conference on Machine Learning, pp. 11225- 11234, PMLR, 2020b.
Xuezhou Zhang, Yiding Chen, Jerry Zhu, and Wen Sun. Corruption-robust offline reinforcement learning. arXiv preprint arXiv:2 100.2000000000 06630, 2021.
13

---

Published as a conference paper at ICLR 2022
A OMITTED DEFINITIONS
A.1 CUMULATIVE REWARD
(Cumulative Reward). Let P S A P(S) be the transition function with P(.)) defining the set of probability measures. Let R, do, H be the reward function, initial state distribu- tion, and time horizon. We denote (TT) the cumulative reward of the given policy
Definition 6
((m) =
R(st, oc), where a, 8(4)), ~ P(st, at), 80 ~ do,
(11)
It is natural adapt this definition when there is discount factor. If policy considers recent ne states instead only 8t to make action predictions, we can change a, = ((t) to at ((tt-n.+it)) in Equation (II)
A.2 PARL (PER-STATE PARTITION AGGREGATION) PROTOCOL
Definition (Per-State Partition Aggregation). Given subpolicies {-, 1--1 the Per-State Partition
Aggregation (PARL) protocol defines an aggregated policy тP :S - A such that
Tp (a) arg max no (8),
(12)
aeA
where na (s) is defined in Section 3
As mentioned in Section 4 when the arg max in Equation ties deterministically by returning the "smaller" (<) action, which can be defined by numerical order, lexicographical order, etc.
multiple elements, break
A.3 TPARL (TEMPORAL PARTITION AGGREGATION) PROTOCOL
Definition 8 (Temporal Partition Aggregation). Given subpolicies ) and window size W, at time step the Temporal Partition Aggregation (TPARL) defines aggregated policy TT {min - A such that (f arg max (3m.x((---1110)))))
(13)
aEA
where Strr and na are defined in Section
In the above definition, at time step L, the input of policy कт contains all states between time step max(t - W + 13 and t within window size W; and the output is the policy prediction with the highest votes across these states. Recall that in Section 3 we define (st.r) Σ5= (s)).. We break ties in the same way in PARL.
B ILLUSTRATION OF COPA AGGREGATION PROTOCOLS
We present concrete example demonstrate how different aggregation protocols induce different tolerable poisoning thresholds, illustrate bottleneck and non-bottleneck states, and provide addi- tional discussions.
Suppose the action space contains two actions = {a1, a2), and there are six subpolicies { ( where u 6. We are at time step = now. When there no poisoning, the subpolicies' action predictions for state 80 87 are shown by Table 2 After aggregation, all aggregated policies will choose action a₃ at =
PARL DDeinition 7). The PARL aggregation protocol only uses the current state 37 to aggregate the votes. On 87, three subpolicies choose action aj and three others choose action dg. By breaking the tie with a1 < a2, the PARL policy TP(s7) a1- The tolerable poisoning threshold K, 0, because one action flipping from a1 to 02 by poisoning only one subpolicy can change the aggregated policy 02.
TPARL (Definition 8) The TPARL aggregation protocol uses window size W = 7. This implies that, aggregate all states 81:7 count the votes and decide the action. Since na, (81:7) 36 and
14

---

Published as a conference paper at ICLR 2022
Table concrete example action predictions, where "I" means action d1 and means action d2. When there is no poisoning attack, the corresponding time window spans by PARL, TPARL, and DPARL are shown by green blue and pink respectively. aggregated policies choose action d1, have different tolerable poisoning thresholds shown the last column.
Action Prediction for
80
82
83
84
85
86
87
K 87
1
1
1
1
1
72
1
1
1
1
43
1
1
2
74
1
1
1
1
2
25
1
2
2
PARL (Tp, Definitio 7
TPARL with W 7 (mT- Dehnition DPARL with Wmax = 8 (xD. Definitio 3)
Maz ($1:7) = 6, after poisoning two subpolicies, we still May (81:7) 2 Mag (81:7). Thus, we achieve an tolerable poisoning threshold K, = 2.
Compared with PARL, the temporal aggregation in TPARL increases the vote margin between di and and thus improve the tolerable poisoning threshold at current state.
DPARL Definition 3).
The DPARL aggreggtion protocol chooses the window size W since this window size gives the largest average vote margin A!"" (defined in Equation (1)). We can easily find out that with poisoning size K = 1, we will still choose W = 8 as the window size and the resulting votes for aj can be kept higher than votes for a2 However, when comes K 2, if we totally flip subpolicies policy will turn to choose W 1 as the window size and then choose action ag as the action output. Thus, we achieve tolerable poisoning threshold K. this time.
and Ti to let them always predict action 02 then the DPARL aggregated
Illustrations of Bottleneck and Non-Bottleneck States. According to our illustration in Sec- tion 4.2) bottleneck states are those where subpolicies vote for diverse actions but the best action is the same as previous states, and bon-bootleneck states are those where subpolicies mostly vote for the same action. As can 5p to are non-bottleneck states since the subpolicies almost unanimously vote for one action. In contrast, 87 is bottleneck state.
From the perspectives of different aggregation protocols, observe that for the bottleneck state 87, both TPARL and DPARL exploit temporal aggregation to boost the certified robust poisoning threshold (from 0 to 2 and from to respectively), thus demonstrating the effectiveness of TPARL. and DPARL on improving certified robustness. On the other hand, for non-hottleneck states 8o to s6, we can easily see that different aggregation protocols do differ much in terms of provided certified robustness levels.
Explanations for Bottleneck and Non-Bottleneck States. We provide additional discussions regarding why bouteencc states are vulnerable and why our temporal aggregation stralegy can ef- fectively alleviate the problem. We first explain the existence of the bottleneck states. Given the property of the bottleneck states that there is high disagreement among different subpolicies on such states, they may lie close the decision boundary. This may result of poisoning, or simply due to the intrinsic difficulty of the state. On the other hand, such states naturally exist in the rollouts (like natural adversarial examples (Hendrycks et al. (021)), and may induce high instability of the rollouts during testing. We next discuss additional intuitions for our temporal aggregation. Essen- tially, temporal aggregation effectively leverages the adjacent non- non-bottleneck states to rectify the decisions the bottleneck states, based on the assumption of temporal continuity which has been revealed and utilized in several previous works (Legenstein et al. 20100) Veerapaneni et al. 2020 Ye
al. 2021
15

---

PARL Published as a conference paper at ICLR 2022
C CERTIHICATION OF PER-STATE ACTION STABILITY FOR PARL
We certify the robustness of PARL following Theorem
be the learned subpolicies according to Section 4.7 from which define na (see Section 3); and let xy be the Per- State Partition Aggregation policy: ap = MM() where M abstracts the whole process. D is poisoned dataset and Tp is the poisoned policy: TP -M(D)
Theorem 8. Let D be the clean training dataset; let n. = M,(i),,,
For given state st encountered at time step t during test time, let (st). then
(8+) max tha (nr (8t) 1[a' < a))
K
(14)
Remark. The theorem provides valid per-state action certification for PARL., since according to Definition 1 as long as the poisoning size is smaller or equal to K, i.e., D e DI < K, the action of the poisoned policy is the same as the clean policy: (st) = (5() = a. To compute K,, according to Equation (14) rely on the aggregated action count n2, for state st from subpolicies.
The a' < a is the "smaller-than" operator introduced following Definition 7
Proof of Theorem Suppose the poisoning size within K, then after poisoning, the aggregated
action count (a(ss) (st) (s) K, Ra (st) + K] where (s(s) is such count before poisoning. Thus,
to ensure the chosen action does not change, necessary condition is that n. (9t) 2 Naa (8t) +
<
for any other a' < Solving K yields Equation (14)
L
We use the theorem to compute the per-state action certification for each time step along the tra- jectory, and the detailed algorithm Algorrithh 2 (Appendix E). Furthermore, we prove that this certification is theoretically tight the following proposition shows. The proof is in Appendii F.T
Proposition 9. Under the same condition as Theorem 8 for any time step I, there exists an RL learn- ing algorithm Mo. and a poisoned dataset D, such that D & DJ = K + 1, and (p(s)) # TP(s)).
D A TABLE OF POSSIBLE ACTION SET
Table 3: Expressions of possible action set A(K) given poisoning threshold K for different aggregation
protocols. Full theorem statements are in Theorems 4 and (in Section 4.4).
Protocol
A(A
A
Σ D'ea (s. na(se) K + 1[d <a),0) (.00)5 K
TPARL
{a E 1
EE Wil > Sa val #2
DPARL
(ar) u d'
min 15W Smin (Wane Wwn..ff1).... W fo"
w.w & sKJU a
Σ
K
10
>
ber o
For all three aggregation protocols, we summarize the expressions used for computing the possible action set A(K) given tolerable poisoning threshold K in Table
E ALGORITHM PSEUDOCODE AND DISCUSSION
E.1 COPA TRAINING PROTOCOL
Algorithm 1: COPA training protocol.
Input: training dataset D, number partitions k, deterministic hash function
Output: COPA subpolicies 6-1
for
[k] do
D. - fT h(()) = (mod k)}
b Separate the training data D into k partitioos
for each partition D; do L
Mo(D.)
Subpclicy trained partition D, offline algorithn Mo
return (m:)/-0
16

---

Published as a conference paper at ICLR 2022
E.2 CОРA PER-STATE ACTION CERTIRICATION
Per-State Partition Aggregation (PARL).
Algorithm 2: COPA per-state certification algorithm for Per-State Partition
Aggrega-
tion (PARL).
Input: environment = (S, R, P, H, do), subpolicies [m)
Output: COPA robust size at each time step {Ki)
80 ~v do
b sample initial state
for from 0 to H do
for each A do
L Compute na (5e) from subpolicies' {Ti) decisions
in defined in Saction 3
Determine the chosen action (st) according PARL (Definition 7
Compute K, according to Equation (14) Theorem 8 Se+1 as)
return (
Temporal Partition Aggregation (TPARL).
Algorithm 3: CОPA per-state certification algorithm for Temporal Partition Aggrega- tion (TPARL).
Input: environment (S, R, P, H, da), subpolicies (n, 1k-1 window size W
Output: COPA robust size each time step { 1
80 do
sample initial state
for I.rrom 0 to H do
for euch E - do
Compute na (8t) from subpolicies" {T, V decisions
ngg 18 definee in Section 3
Determine the chosen action <- (s:) according to TPARL DDfinition 8)
Paiin 4- 00
for each a' E A, a' F do for from 0 to do Compute a according Equation (4)
(100 oe Yém + sorted (hi,a T reverse True) Compute 8a..a'
11
12
sum <- 0.P
13
for from to k do
14
sum + (,)))
p ac.u" > Sagaa then
break
p + J. sum f- sum (3)
17
us.a"
Puin min (Pmin p}
K. Puni
29
Sc+1 P(ss, az)
H-1 return (Ke Fi=o
17

---

Published as a conference paper at ICLR 2022
Dynamic Temporal Partition Aggregation (DPARL).
Algorithm 4: COPA per-state certification algorithm for Dynamic Temporal Partition Aggrega- tion (DPARL).
do), subpolicies [m.)== maximum window size Wmax Output: COPA rohust size at each time step {Ke) 1
Input: environment
8o
D sample initial state
for from to for each a E -.
do
L Compute na (8e) from subpolicies" {m k= decisions given 8, Ra 1a defined Sect
Determine the chosen action + TD (s.) and chosen window size W" according to DPARL [Deiiniiion 3)
Pinin
Ks Algorithm 3
Aigorithm
replaced W compute
KP + K; for each a' E A,, a: do for each a" E A. d" 0r do for W from 1 min(W Wmxx, 1 do a # + arg max an aa5 Rag ($:-
10
12
for from to max W*} do | Compute m o (ao) according to Equation (7)
for i from 0 to k do (W' W*} do
for w from Compute o² (") according to Equation (7)
Compute according to Equation (7)
(g Mi=1 + -sorted({g) 1 reverse = True)
1
Compute n. :uu# -aa tmp +W"(m
W W' W.
W.
W (n m 1aa'= arl
sum <- -- 0
23
for j from to l: do
if aum tmp 0 then
p - break
P + J. sum
60
I T.W'
t P. KP + min KP. R, W.""
at
29
SC+1 P(st, at)
30 return (KP) 1
E.3 CОРА CUMULATIVE REWARD CERTIFICATION
COPA-SEARCH alternately executes the procedure of trajectory exploration and expansion and poisoning threshold growth. In trajectory exploration and expansion, COPA-SEARCH organizes all possible trajectories the form of search tree and progressively grows For each node (represent- ing state), leverage Theorems 4 5 and 7 to compute the Possible Action Set. We then expand the tree branches corresponding to the actions the derived set. In poisoning threshold growth, explored,
when all trajectories for the current poisoning threshold
increase K' to seek certi- fication under larger poisoning sizes, via maintaining a priority queue of all poisoning sizes during the expansion of the tree. The iterative procedures end when the priority queue becomes empty.
18

---

Published as a conference paper at ICLR 2022
The highlighted line in the following algorithm needs to inject different algorithms based the aggregation protocol: for PARL (Tp), use Theorem 4 for TPARL (TT). use Theorem for DPARL (Tp), use Theorem
Algorithm 5: COPA-SEARCHS
adaptive tree search for cumulative reward certification.
Input: environment & = (8, R, H, do), subpolicies {Tr) aggregated policy (with W) ær (with W max) Output: a map that maps poisoning size to corresponding certified bound cumulative reward _x
b. Initialize global variables
p-que +
initialize empty priority queue containing tuples (staze historydo. a poisoning size rewewadd J) serced by increaeing initialize global minimum reward
Jelobal f- 0e
Function GETACTIONS (80:; Kim, Jeur):
possibleActions(so.. (Ti 16-1 Tay Kim) P compate the possible action set given state history, pubpoliases aggragation policy Ra, and paisoning size aecording to thcorams in Section 4.4
-
list +
for each action A then continue & game terminate here, no possible larger or lower cumulative reward to search
((s a)
+ fa}
zecord possible actions expand
10
A + then
11
K' + min
[essbbooction(sssss() . K)AA K
12
Anew + possibleections(((e Aoce: (T, hil Tay K") \A b compute the "mmed' ate actionn that w1 possioly be chosen if enlarging the ponsoning size. for each action Anew do P que. quu..puh((Sa.e... K" Jeur))
15
return list
16
Procedure EXPAND (80:1; Krim )
17
if Jeur 2 Jelobal A (step reward is non-negative) then
18
return
pruning
19
list +- GETACTIONS (80st ( : mx, Kimm)
compute according to theorems in
Section 4.4 if list = then
21
Jalobal t min (Jgobbal, Jeur return
22
23
for E list do
8141 ((s,,a) a) if 5141 then
25
26
Jotabal <- minn J
27
else
28
EXPAND (S0a41, Kums Jeur R(si, a))
M 0
30
8o
<- do
D initial state in expand initial trajectory
31
EXPAND (Sa, Kim O, Jeur 0)
while True do
33
p_que = then break
34
no state to expand pos first element examine the next element obtain new point of certification reault D expand the tree from the new node indeed the algoritha can terminate any Lime within while 1oop
35
(80:e, 0, K, J) p. pop((((p((
36
(_,,, K' () t topp)
37
M(K) + Jglobal
Sct1 + a))
39
EXPAND (50441, K", J R(sI,a)) a))
return M
19

---

Published as a conference paper at ICLR 2022
Time Complexity. The complexity of COPA-SEARCH is [(H]Sexplored Sagllore((ooggaa Sexplooed + [A(T)), where Sexplored is the number of explored states throughout the search procedure, which is no larger than cardinality of state set S, H is the horizon length, |.|] is the cardinality of action set, and 7 is the time complexity of per-state action certification. The main bottleneck of the algorithm the large number of possible states, which is in the worse case exponential to state dimension. However, to provide a deterministic worst-case certification agnostic to environment properties, ex- ploring all possible states may be inevitable.
Relation with Wu et al. 20022). The COPA-SEARCI algorithm is inspired from Wu et al. [002 Algorithm 3), which also leverages tree search to explore all possible states and thus derive the robustness guarantee, However, the major distinction is that their algorithm tries to derive probabilistic guarantee of RI. robustness against state perturbations, while COPA-SFARCH derives deterministic guarantee of RI robustness against poisoning attacks. We think this general tree search methodology can be further extended to provide certification beyond evasion attack (Wu al. 2022) and poisoning attack (our work) and we leave it as future work.
Extension to stochastic MDPs.
current version of COPA-SEARCH the exhaustive search is enabled by the deterministic MDP assumption. However, we foresee the potential of conveniently extending COPA-SEA SEARCH to stochastic MDPs and will discuss one concrete method below. con- trast to interacting with the environment for time obtain the deterministic next state transition in the deterministic MDP case, in the case of stochastic MDPs, we can leverage sampling (i.e., by repeatedly taking the same action the same state) to obtain the set of high probability next state transitions with high confidence. In this way, our COPA-SEARCI will be able to yield a proba- bilistic bound, comparison with the deterministic bound achieved in this paper enabled by the deterministic MDP assumption.
F PROOFS
F.1 TIGHTNESS OF PER-STATE ACTION CERTIFICATION IN PARL
Proof of Proposition 9 We prove by construction. Given the state st, we first locate the subpolicies whose chosen action is a, and denote the set of them
== {i E [u] (s;) = a = (p()))}
We also denote a' arg max at Re (s,) < a). According to K definition (Equation (14)
[B] = (*)) > no (x)) ( 2 K₁-
We now pick an arbitrary subset B' C B such that BB = K2 + For each i E B', we locate its corresponding parititioned dataset D, for training subpolicy we We insert point p; to D, such that our chosen learning algorithm Mo can train subpolicy मं Mo(D; U {p:}) that satisfies (*:) a'. For example, the point could be p; = {(s,, } and Mo learns the action with maximum reward for the memorized nearest state, where s' can be adjusted to make sure the point hashed parition i Then, we construct the poisoned dataset
(
ò = U D (pot D.U U
U sE|u](B'
D.)
LIEB'
Therefore, we have ò D Use 13' +.
On this poisoned dataset, train subpolicies {5. [-- and get the aggregated policy 7p. To study Tp (8t), we compute the aggregated action count nr on these poisoned subpolicies. We found that
'Strictly speaking, we need choose determinisite hash function for dataset partitioning such that adjustment on s' and reward (currently co, but can be an arbitrary large enough number) can make the point being partitioned to i, i... 1x(p.) = (mod u). Since our adjustment space is infinite due to infinite number of large enough reward, such assumption can he casily achieved. Same applies to other attack constructions in the following proafs.
20

---

Published as a conference paper at ICLR 2022
(s() na(ss) |BB| and (s)) = (ar ) + |B|. Therefore,
na (8x) Naa (st) (8(8)) nha (8t) 2(K, + +1
(8(())) - nad (8t) - (1 (n((s)) (1ma(es) no (5) - 1laa < al
+
2
< (st) - no (s) (sa( nod (st 1/a a)) = 1/dd < <a).
Therefore, if a' < a, (st) I Th (st). and has higher priority to be chosen than a; if > a,
(s:) Mar (st) 1, and a' still has higher priority be chosen than Hence, (Tt
Tp (8t). To this point, we conclude the proof with a feasible construction.
F.2 PER-STATE ACTION CERTIFICATION IN TPARL
For ease of notation, we let w = min Wt++1} so w is the actual window size used at step We let to f + f.e., to is the actual start time step for TPARL aggregation at step t. Now we can write the chosen action at step without poisoning as a = (
Proof of Theorem I
We prove the theorem by contradiction: We assume that there is poisoning attack whose poisoning size K S K, where K, is defined by Equation (3) in the theorem, and after poisoning, the chosen action is a² * a. We denote { to the poisoned subpolicies and कт to the poisoned TPARL. aggregated policy. From the definition of Kr, we have
K
K.
h
aaa S 8
(15)
a.a
i=1
since K S Ke, and each h
is an element of av, for some i' where
0,a
h aa,0
1y (sta() + Σ 1y (5c-))
1=0
f=0
by Equation (4) in the theorem. Since the poisoning attack within threshold K can at most affect K subpolicies, we let be the set of affected policies and assume B = K without loss of generality. 3t' E [fo, (s()) + (se)).. Therefore, according to the monotonicity
Formally, B = -i fie [u]
of h (i) a. from Equation (15)
K
Σ DhaaaT
(0) a.o
(16)
According to the assumption of successfully poisoning attack, after attack, the sum of aggregated vote for a plus 1 ja" < a] should be larger then that of a. Formally, after the poisoning,
naz (stozt 1[a" < <a] > na (Stg:t)
or equivalently
n. (Stpa) - (Maz (Sto2) + 1aa" < al) < O.
From the statement of Theorem 1.
da = na (St.a)) - (nar (Stact) + 1aa" < al).
Take the difference of the above two equations, we know that the attack satisfies
na ( Via (8tott) (nar(Stg:)) - nar (8tg:))) 00
(17)
Since the attack only changes the subpolicies in B, we have
10
w-
na (s - na (S
Σ
1[m((t-))) =
Σ
1 ( =
iEB
j=0
w w-1
1 (st-g))
iEB 1=0
na. (8bgtt) - (Stott) =
(m((8)))) a
Σ ());))
=
iEB
==
w-1
> Σ
Σ
1 a (st,)
iEB
1=0
21

---

Published as a conference paper at ICLR 2022
Inject them into Equation (17)
yields
w-1 Liarr(se-1) d
Σ
4a(5)-5)+ w
BEB
1=0
which contradicts Equation (16) and thus concludes the proof.
and
F.3 TIGHTNESS OF PER-STATE ACTION CERTIFICATION IN TPARL
Proof of Proposition 2| For case of notation, we let w = min ( + + 1} so w is the actual window size used at step t. We let to t at step Now we can write the chosen action at step without poisoning as = (T((t.:))
1, i.e., to is the actual start time step for TPARL aggregation
We prove by construction, i.e., we construct an poisoning attack with poisoning size K, + that deviates the prediction of the poisoned policy. Specifically, we aim to craft a poisoned dataset D with poisoning size DeĐ = k,+ such that for certain learning algorithm Mo, after partitioning and learning on the poisoned dataset, the poisoned subpolicies मं MM can be aggregated to produce different action prediction: Tr (stg:t) * a.
Before construction, we first show that K, given by Equation (3) satisfies K, < u. If = u, means that for arbitrary d' #
hi.aaa
Σ 1. +
Σ
1 1i (8L-s)
= na (a(( + uw na na (S
j=0
S 0n,a' (Rtge)) nha (Sto2)) 1 laa n)
which implies uw I contracting uw > 0. Now, we know K, < u, So K + 1, our poisoning size, smaller or equal to
We start our construction by choosing an action at:
arg min arg max P.
a' y (6 Ss
According to the definition of K, in Equation (3) for af we have
K,+1
0.07 8 So
(18)
We locate the subpolicies to poison as
B {i E [u]
1i is h (1) a in the nonincreasing permutation in Equation (4)
S K,
1}
(19)
Therefore, |B| K. and
Σ Dhia, da.a7 iEB
(20)
by Equation (18) For each of these subpolicies E B, we locate its corresponding partitioned dataset D; for training subpolicy n. and insert one trajectory Ps to D,. such that our chosen learning algorithm Mo can train a subpolicy गे = M(D; U {px } satisfying (svr = a" for any t' e [to, t]. For example, the trajectory could be p; = {(st, a .s', of and MM learns the action with maximum reward for the memorized nearest state, where can be adjusted to make sure the trajectory is hashed to partition i. Then, we construct the poisoned dataset
D
(pi) D.
U D. iE[u](B'
NEE
Therefore, we have D e D = Ueep': for a and a" before and after poisoning:
B'
K, + 1. Now, we compare the aggregated votes
no (5 - n2 (st
Σ
Σ
1 ((T((st))) =
Σ
1 [[T al
iEB
1=0
1=
22

---

Published as a conference paper at ICLR 2022
(8t(5)))) =a],
IEB 1=0
na (Stg:))
noo (81o1)
Σ
(T = =a
Σ
1 1|m (s-,)
= a"1
iEB
Σ
1 (8,))) a²'
EEB
J=0
Now we compare the margin between aggregated votes for and a" after poisoning: na (stg:t) - na (Stgct) + [[a" <
( - na (Stort) + lsa" <a) + n.r (sto:t) - no= (Sto:t)
(Na (Ma(sta:t) - na (S(()))))
w-1
=- = - +
(((-)) = a] w v- Σ (T) a²1
iEB
0
a
hi,a,a 0.
iEB
As a result, after poisoning, a" has higher priority to be chosen than a, i.e., (T( # TT (Start) To this point, we conclude the proof with feasible attack construction.
F.4 LOOSE PER-STATE ACTION CERTIFICATION IN TPARL AND COMPARISION WITH TIGHT ONE
The following corollary of Theorem 8 states a loose per-state action certification.
Corollary 10. Under the same condition as Theorem 1
K, nh - maXa'sa toa < (Smax(1-W+1.0..) + 1/a' < al)
(21)
min W + 1}
a tolerable poisoning threshold at time step in Defnition where W is the window size.
Proof of Corollary 10 We let w min(t + 1, W} } to be the actual aggregation window size time step t. After poisoning with size K, at most K subpolicies are affected and each affected policy can only make =w changes the aggregated action count. This implies that, after poisoning, for any action a' E A. the aggregated vote count N. (s ww). Thus, when K < K, where Kg is defined in Theorem for any a' a, we have
[nar ( w+11t) ww, (1+= +
n (x($1-w41it) No (St-w41))) - 1[a' < <a]
=n (at no (8t- 1[a' < a]
2Kw
2n. ($t-w+1:)) ne ( (st- 1[a' < a] - 2w K,
2n (
nha ( (8t-w+1a)) 1 1/a < a] - na (a((5t-t1=)) - (St- + 1[a" < al)
a² a/a
= max((g" (A ($1-w+1:t) + 1(a" < al) (na' (st- + 1[a' < al) 0. alyaa
From the definition of TPARL protocol, the poisoned policy still chooses action which implies
K, is tolerable poisoning threshold.
In the main text, mention that the certification from Corollary 10 is looser than that from Theo- rem This assertion based on the following two facts:
According Prrpposition 2 the certification given by Theorem is theoretically tight, which means that any other certification can only be as tight as Theorem or looser than it.
There exists examples where the computed K, from Theorem is larger than that from Corol-
lary 10
For instance, suppose W = 5, action set A = {a), 02), and there are three subpolicies. At time step mi for 8n 84 (a), (n 01, 01, a2) for all subpolicies (i.e,, (3). Thus, the
23

---

Published as a conference paper at ICLR 2022
benign policy (5(44:4) d1- By computation, the K2 from Theorem is 1; while the K from Corollary i0 0.
Indeed. Corollary 10 can be viewed as using 2w to upper bound hi = w Σj=o i (5t-a)
2j- 1 (8t_g), Intuitively, Corollary assumes every subpoliey can provide 2w vote margin shrinkage, and Theorem Juees hi, to capture the precise worse-case margin shrinkage and thus provides a tighter certification.
F.5 PER-STATE ACTION CERTIFICATION IN DPARL
Proof of Theorem 3 Without loss of generality, we assume W Wmax S + 1 and otherwise we let W max min W max; t + 1}. We let to max(t W Waxx 1, 0} be the start time step of the maximum possible window. To prove the theorem, our general methodology is to enumerate all possible cases of a successful attack, and derive the tolerable poisoning threshold for each case respectively. Taking minimum over these tolerable poisoning thresholds gives the required result.
Specifically, we denote to the predicate of robustness under poisoning attack: P (statt a). and denote K' to the poisoning attack size. Therefore, we can decompose P as such:
P P==PP P(W")
Q((" ,a)).
(22)
SSW*SWaas W #W" a'
Recall that W is the chosen window size by the protocol DPARL with unattacked subpolicies TD [Equation (1)). In Equation (22) the predicate P(W") means that after poisoning attack, whether the prediction under window size W is still a; the predicate Q(W", a') means that after poisoning attack, whether the chosen action is a' window size W* and average vote margin is larger (or equal a < a) at window size W' compared to W'. Formally, let 7a be the aggregated action count after poisoning and Á. be the average vote margin after poisoning at window W (see Equation (2)).
P(W")-
arg max na (s =a)
aEA
@(W",
arg max i. (3t ($t-W+41:t) = ^ REA
(23)
(((A"* [w 2 A ^ (a' < <a)) v ((Ar" > A!"') (a' > (id>aa)))
According to Theorem
K k
where Ke is defined by Equation (3) with W replaced by W', The following Lemma 11 shows sufficient condition for Q(W", .²). We then aggregate these conditions together with minimum to obtain a sufficient condition for P:
K S min
K
min IgW- mm.. 111, +W at 4a
W L
and thus conclude the proof.
Lemma 11. Let Q(W" a'),, K, W' be the same defined in proof of Theorem 3 then K min L W .w
a" a' a' -Q(W"
(24)
W W where La dl is defined in Definition 4
WW,WW
Proof. We prove the equivalent form:
Q(W a')
K> min I W W",W" w aa "''a""
(25)
Suppose poisoning attack can successfully achieve Q(W+, we now induce the requirement on its poisoning size First, we notice that
(A 2 AW) A <al <a)< ((Tr > Am"' (a' (a'> =0)
(26)
W'W' 2 W'W' +1/d' a]
24

---

Published as a conference paper at ICLR 2022
since W W//W is an integer by definition. According to the definition and Q(W", a'''s assumption that arg aa (=())-W=+1=)== = =a'
W"W'A W. I W' (Taa (1:1 - (st-
where "=" comes from the fact that the margin in A!!" should be with respect to the runner-up class after poisoning, and computing with respect to any other class provides an upper bound. Here aaa (St-WW
choose a# arg maxaazaa' poisoning, to empirically shrink the gap between the bound and actual margin. On the other hand,
(see Definitton 48, the runner-up class before
W"W'A!" 2 W' Tia (o.t--441))) max Na" (8t-w4))))))))
a"Ea
where "2" comes from the fact that the margin in A." should use the top class after poisoning, and computing with any other class provides a lower bound. Thus, from Equation (26) and the above two relaxations, we get
QW",a')
W (s--W() nan (8L-W++1a)) 2 W (oo(s:-444a)) max far (8L-W1410) +1/a' > a"ta
3a" # a,
W' (Nzz (8) Na= (st-W++=))) 2 W (#a(()- na- (st- (et+t)+1:t)) + 1(a' > a).
For each a" * a, now
the last equation the condition, and show that K necessary condition. This proposition is equivalent to W", WWW""" K Lo
L W' _W'
La al!
is
W (st (11- - na
< W* (Ma(St- (s-- 1[a' > a].
(27)
Suppose a poisoning attack within poisoning size K changes the subpolicies in set S [u]. Note
that B S K. We inspect the objective in Equation (27)
W" (Tar ($1- n (S-- (t-w-+1:)) W (na (Mo(3)-((41a) - Tua (8t- (1--((11:)) 1 > a)
=W' (na w1a) Th (se-W.41:e) W (na (M:- Tha"" (8t-W()1:t) 1 > a)
W
W
W
(s. = = W
1 (st- = a#1
EEB
0=0
w=
W
W
W*
1 [8 m+1 = W
[ 1))
m=
W
W
W
(8: (8--w=)) -1) ac] W
1 nT (3t-w+1) = a#1
iEB
w=0
W
W1
W
Σ
1 1/TT ( -)) = =|] W
Σ
1 [[::( (1)
0=
w=0
=W' =W'(ng (91-W-+11d Ru (8t-W-41:t) W
(no (no(s)-(41a)) nuy (5)- 1[a' > a]
W W')
" (8t-wo)))) -0" -"
1EB
SW' (na (8t-
n (st- (xt- w (No(St-W'41z))
1la' > a)
max (W' w')
Σ
max (ao) - -00 (TT((r)))) anEA
iEB
(a)
k
W' (no (81- nww (#x))+ W (no(#1-W441a) nay (( 1[a' > a] + Σ
(
25

---

Published as a conference paper at ICLR 2022
(6)
W' (S--WW41)))) nu (SL-WW11)))) W (Na(S1-W(41a) Tar (s 1 > al +
g
(c)
<0.
Thus, Equation (27) is proved. Therefore, K
I.
W .W .a"
necessary condition for Q(W", ,d),,
i... Equation (25)
In the above deriviation, the definitions g', g¹, and o are from Equation (7) (a) comes from
the facts that (g(*) J is a nondecreasing permutation of {9. 9t 2 0, and [B] < K. (b)
comes from the assumption K L W and also g( 2 0. (c) comes from the definition in Equation (6)
F.6 POSSIBLE ACTION SET IN PARL AND COMPARISON
F. CERTIFICATION
Proof of Theorem 4 According to the definition of possible action set, we only need to prove the contrary: for any E A (K), within poisoning size K, the poisoned policy cannot choose at (s:) * a.
According to Equation (8) any E A (K) satisfies
max (St) na (5t) K + 1 a].0} K.
(28)
Given poisoning size K, since each poisoning size affect only subpolicy, know
(s:))) S nu (St) ( K
where n. denotes to the poisoned aggregated action count. We suppose the attack could be success-
ful, then for a' < a, Naa (3t) S. (xt) - 1, and thus naa (s:)):) na (Be) 2 (s:) - (s())) - K + 1. Similarly, for > a, a' (1t) ) S (8t). and thus niz (8x)= (st) ) 2 na (8t) (ma -. Also, for any a' * after poisoning nh (se) - (s:) 2 otherwise deviating the difference subpolicies' decisions' from a' to is strictly no-worse. Given these facts, the amount of votes that need to be reduced the LHS of Equation (28) which larger than K. However, we only have K poisoning size, i.e., K votes that can be reduced. As result, our assumption that the attack could be successful falsified and the poisoned policy cannot choose a.
Corollary 12 (Loose PARL Action Set). Under the condition of DDeiinition 5 suppose the aggrega- tion protocol is PARL as defined in Definition 7 then the possible action set at step
(K) a E A max (5t) nT(ss)) < 2K 1[a > arg max na (86)
(29)
d'EA
a'EA
Proof of Corollary 12 Again, we prove the contrary, for any a E A (K)), within poisoning size K, the poisoned policy cannot choose Tp (s:))) #
According to Equation (29) let Om = arg max &' Tey (8t), then any E A AL(K) satisfies
na. (8t) na (8t) 2K 1aa am).
After poisoning, we thus have
Nam (s:) (3, 1aa aml Re (st) na (st) > 1 1/a am]
From the definition, a & (K) so a & am If a. a, nam (s:) 2 nu (s:); am > a, Taa (st) >
(s:))). In both cases, am has higher priority to be chosen than a, and thus the poisoned policy cannot choose a.
F.6.2 COMPARISON
Theorem 13, Under the condition of Deeiiiition S suppose the aggregation protocol is PARL as de- fined in Desinition 7. A (K), AL(K) ) are defined according to Equations (8) and (29) accordingly, then
1. AT(K) (L)); and there subpolicies (m, {m)) and state st such that AT & (K).).
26

---

Published as a conference paper at ICLR 2022
2. Given subpolicies { )i= and state st any A (I). there exists a poisoned training set D whose poisoning size [D O D S K and some RL training mechanism, such that (Tp( where Tp is the poisoned PARL policy trained on D.
Proof of Theorem 13 We prove the two arguments separately.
1. We first prove (K) C (K). For any a A (K). let am arg aa na (5t), then max (st) na (st) - K + 1/a < a]. 0} s K
E'EAA
10am (8e) - (8x) K + 1+11/ (im a| SK
-ag (5e) - nie (st) S 2K 1a > am]
where the last proposition is exactly the set selector of A (K) so a E AK)...
We then prove that (K) _ (K) can happen by construction. Suppose that there are three actions in the action space: A = {ai, a2. 0z). We construct subpolicies for current state 8t such that the aggregated action counts are
Ray (5t) = 10, nog (8x) = 9, nas (8t) = 1.
Given poisoning size K = 5, we find that
May (8+) Rag (8x) = 9 < 10 - lag 2 ai] =9
=
=ag ag E (K),
(Nai (8t) nos (8t) K + 1aa < ag)) +
(nag (st) nay (s;) K + 1[a2 < agl) 9 9 K = a3 $ a" (K).
Therefore, AT (KK(K) & (K) for these subpolicies and state 8t-
2. We prove by construction. For any a E AK), we construct the set of subpolicies to poison 8a S [u] such that [B' < K, then describe the corresponding poisoned dataset Dr and finally prove that the poisoned policy कp. (s:) = a.
For E AT (KK,,, by definition (Equation (8) we know
Σ
max
no (8t) (st) K + 1la' a). 03 S K.
(30)
a'EAA
:=fa,a'
We now define a set of actions
Ca C A such that
C fa' A ta.a' > 0).
According to this definition, & C since ta,a I 0.
Fact F1. For E (KK and any a' E A, no (3:) + K - lsa' < a) 2 0.
Proof of Fact F. Suppose na (8t) + K - 1aa < a) s O, then na(st) K = 0 and a' < a.
Then
max (8t) -n))nna K (a' < 0) > Σ na ( (8)- Σ na (8t) = u > 0
EAA
a'EA
d'EA
which contradicts the requirement that the LHS of the above inequality should be S K = 0. L
Fave F.1, for any a' E C", (st) 2 la.a. Notice that ni (st) is the number of subpolicies
that vote for action a' at state st. Therefore, we can pick an arbitrary subset of those subpolicies whose cardinality is ta.a'. We denote B3, to such subset:
Ba C {ie [u] (s:) a'), }. |B5]| to,a'.
Now define B.: B% = Un'ecr Ba We construct B3 to be an arbitrary subset of those subpoli-
cies whose prediction is not a and who are not in B% and limit the B ' cardinality:
B C (i E [u] (s:) A a} \ Ba, [B = min{ K - | u na (st) - BB
Such Bg can be selected, because:
From definition, Ba C (i E [M] (x)) + a), where the cardinality of (i E [M] (c( +
a} is u na())) So 0 S u- (st))) |Ba..
Since
Ba <
B = Σ
la.a!
la. S K,
a' E'ECa
a' "
d'Ed.aa.
27

---

Published as a conference paper at ICLR 2022
K [&l 2 0, and thus [B 2 0. Here (*) is due to Equation (30)
The superset {i E [u]
| (*t) # a) \ B has cardinality -n((st) - B and Bgl s
u - u
B-
To this point, we can define the of subpolicies to poison:
_ := B U Bi:
and | = B + S
In a similar fashion the attack construction in proof of Proposition 9] for each i E Ba, we locate its corresponding partitioned dataset D; for training subpolicy म. We inset one trajectory Pf D; such that our chosen learning algorithm Mg can train subpolicy #3 = (DD such that (st)
For example, the trajectory could be pf = (st,, 0, 8 [o)] where 8' is an arbitrary state that guarantees yf hashed to partition and Mo learns the action with maximum reward for the memorized nearest state. Then, the poisoned dataset
De "U=UD. D. D.U (
U D; iE[u]\B
iE
Thus, De is D Doy |Ba| I K, i.e., the constructed attack's poisoning size is within K.
We now analyze the action prediction of the poisoned policy Tp. For action a, after poisoning. (a())) = na (s:) + = no (s.) min ( u- (a--nn())))) min((. (,, K, 7., (8x) u, then all subpolicies vote for a, apparently тP (sx) = a; otherwise, (a((s) = na + K. In this case, for any action a' C"", since at least choose subpolicies in B and change their action prediction to a, the aggregated action count after poisoning is n. (st) S na
B (a)))) & Ca and a' # a, 1 1aa < <.. Thus, a' has lower priority to be chosen than a. For any action
(sx)
ne (8t) n (8t) +s) K- < aj na (s K-1 <
by the definition of C ta,a' na (s.) (s.) K + 1a < a] < 0. After poisoning. the vote of a' does not increase, i.e., Fi. (st) S nh (5t) S na ($t) + K - 1[a' < a] n. (st) ) 1[a' < a]. Thus, a' also has lower priority to be chosen than a. In conclusion, we have πP (s:)
To this point, for any a E AT(K), we successfully construct the corresponding poisoned dataset Da within poisoning size K such that TP" (s:) a, thus concludes the proof.
F.7 POSSIBLE ACTION SET IN TPARL
Proof of Theorem 5 For ease of notation, we let w mW, 1}. w is the actual window size used at step t. We let to = f- w 1, i.e., to is the actual start time step for TPARL aggregation our current step Now we can write chosen action at step t without poisoning as (T(.t).
We only need to prove the contrary: for any E A \ A(K). within poisoning size K, the poisoned policy cannot choose a: TT( # a.
According to Equation (9). for such there exists a' o such that
a' I Sataa = na (Srga) - na (S1oa) 1aa a').
(31)
Suppose there exists such poisoning attack that lets (8 = a. This implies that for d', after poisoning, we have
The (Stgit) - Ner (Sto:e) - 1aa < a) < 0, where R. is the aggregated action count after poisoming. Since the poisoning size is within K, it can affect at most K subpolicies. We let B C [M], S K to represent the affected subpolicy set. Therefore, The (8to:t) Ria (8to:t) 1 1/a' < a)
(32)
(Stattt ne (Stgit) 1/a' < a) + +(7 (Staat) nea (Stoit)) (fa()t))) no (s10a))
28

---

Published as a conference paper at ICLR 2022
w-
w-
00''a +
Σ
1 ( = =d, ( dd
Σ
(d a1)
iEB
1=0
w-1
1
E
1 - aa
(
/=
j=0
200',a
((t())))) # a' (1) a')
Σ
1 = #a]
200',a Σ
((- = =dp+ Σ
1| ( al
iEB B
1=0
=8 a0
1 1 (s:
+
Σ
1 1i (8r1))
iEB
i=0
1=
B
(0) =8a' hi,a' 8e
80
a' O.
iEB This contradicts with Equation (32) and thus the assumption is falsified, i.e. there is no such poi-
soning attack that let कr (Stgtt) = a. In the above equations, (a) is due to the fact that ()) is
nonincreasing permutation of { 1u-1 (b) is due to the facts that |B] < K and (8) 2 0. (c)
comes from Equation (31)
F.8 HARDNESS FOR COMPUTING TIGHT POSSIBLE ACTION SET IN TPARL.
Proof of Theorem 6 By Definition 5| the possible action set with minimum cardinality (called min- imal possible action set hereinafter) is unique. Otherwise, suppose A and B are both minimal possible action set, but f B, then A n B smaller and valid possible action set. Therefore, the oracle that returns the minimal possible action set, denoted by MINSET, can tell whether any action a E MINSET and thus whether any action a can be chosen by some poisoned policy fे whose poisoning size is within K. In other words, the problem of determining whether action a can be chosen by some poisoned policy स whose poisoning size is within K, denoted by ATTKACT, is polynomially equivalent MINSET: MINSET =p ATTKACT. Now, show a polynomial reduction from the set cover problem to ATTKACT, which implies that our MINSET problem is an NP-complete problem.
The decision version of the set cover problem Karp known NP-complete problem and is defined as follows. The inputs are
1972). denoted by SETCOVER, is a well-
1. universal set of n elements: U {ui, u2, "....,,,, 3
a set subsets Uf: = -V1, .V,,.... Vn V. u, Cu, V; =
3. a positive number K E R4..
The output a boolean variable b, indicating that whether there exists a subset W C V. W < K, such that Vu; E 24 3V W, u, E V. Given oracle ATTKACT, we need show SETCOVER can be solved in polynomial time, i.e., SETCOVER Sp ATTKACT.
If K 2
We scan all sets V; E V. To being with, we have a record set S <- (6, and an answer set W + 0. Whenever we encounter
that contains a new element u, & S, we put W W U {V)), and record this element S + SU {u.). After one scan pass, W covers all elements of U (since U V 2), and |W| S n K. Therefore, W is valid set cover. Since we can always find such W. we can directly answer true.
29

---

Published as a conference paper at ICLR 2022
If K 2 m.
We can directly return V as a valid set cover, since Uf= V = 2 and M S m S K. Thus, we answer true.
If K mn:
This is the general case which we need to handle. Now we construct the ATTKACT(K) problem that can trigger its oracle solve SETCOVER.
1. The poisoning size is K.
2. The action space A = 4 U (b) UT where I {# (..... # ((A)
m²n.)
The sorting of actions is U1 < U2 < .... <
< <b< < #1 < #m
3. The subpolicies are {T]] J==1 U { 1 E S n, S j S K 1}, where T.
corresponds Vj E V. and Ti correspond to un E u. (Number of subpolicies
m Kn m n²²)
4. The current time step is t- nm, and the window size W nm.
5. The input action is b, i.e., asking whether can be chosen by some poisoned TPARL policy,
i... (51.) = the poisoning size is within K.
Now, we construct the states at each step / (1 < < nm) so that the subpolicies action predictions these steps are as follows.
1. Count the appearing time of each u, in V, and denote it by c;: G; = -y 1|: V3J. For each uy select Vi, that contains u4 and in the corresponding T.. assign G; 1 steps to predict un; for all other Vj that contains us in the corresponding Tj. assign one step to predict ut.
2. After this process, each xz at least has time step whose action prediction is u, for each u, Vy. Among all {Λ J==1 1i and all time steps 1 I t nm, step-action cells are filled, and the remaining (m2n mn) cells are filled by #1 sequentially.
3. For each 7/. arbitrarily select W m time steps assign action prediction as uy; and fill in other m time steps by remaining #i E I' sequentially.
4. For each -ं.-- for all time steps, let the action prediction be u,.
As we can observe, the number of actions, the number of subpolicies, and the window size are all bounded by polynomial of and m. Therefore, such construction be done in polynomial time.
We then show SETCOVER true 3K' b. ATTKACT( K'SK.
Suppose the covering set is W C V. we denote K' to [W]. and construct the ATTKACT problem with poisoning size K' as described above.
We can construct poisoning strategy to let (51mm) 6. The poisoning strategy is to find out πミ for each V3 W, and to let them predict action b throughout all time steps: TH (s{) = b, < t' < nm.
After poisoning, the aggregated action count (3:mm)))) = [ x nm K'nm. Since W covers every u; U, for each u, E U there exists set V2 uy whose corresponding मडद is poisoned to predict b. Thus, nu, ($1mm) < nu, ($1:mm) = + (W m) + W (K' -
WK' = K' K'm. For any #1 E r, N4 ( < R44 (144($mmm) ($1:m)) = 1. In summary, K' K''m, n4. ($1:mm) 1. Thus, after TPARL aggregation, the poisoned policy (81m8m))) = b, and therefore b E ATTKACT(K").
nu ($1:mm) K'nm, nm, Nig (11mm)
Suppose is K' that letb E (TTKACT(K"), which implies that there exists such a poisoning attack within size K' that misleads the poisoned policy to b: का (81:mm) b. Since the poisoning size is K", after poisoning the aggregated action count
Th (81mmm) < K" K' K'nm.
For each u; E U, since nu, (81:mm) m + (W m) + W x (K" 1) = K' n', we always have
Bog (81:m)) 2 (81 S Thyg (81:nm)
(33)
30

---

Published as a conference paper at ICLR 2022
where (+) is due to the condition of successful attack. We denote the set of poisoned subpoli- cies by II (III) I K'). Therefore, Equation (33) implies that for each u, E U1 there exists at least one subpolicy
Tu. E II, ueu {mg u, E V3) U (x)) U ( 1 K - that is poisoned by the attack, otherwise the aggregated vote Thu cannot change.
(34)
We partition I by r and Déc where
T = I' {xz ym 1.=1. = I'n (' {
We construct additional poisoning set r4 following this process: the beginning, r 0. For each E U, if 1 n [T)
u, Vj} is not empty, skip. Otherwise, according to
Equation (34) 1 { m 1131 S ---1]
1 is not empty. In this case, we find
an arbitrary covering set of ug namely Vi e uy and put "jo into 1 When the process terminates, we find that for each u, E U,
(TU n t
44 =EV)+
(35) ) S
Following the mapping {ー
(V isism. m] = V. the subset (T (T
(T) ) can be mapped to (W UW? V. From Equation (35) (Wa U is a valid set cover for U. We now study the cardinality of this set cover. From the process, we know that
every Vi2 E Wt corresponds to a different set in 1 Thus, w < [1%, which implies that
M U U < |M + | < | ||| S K"
To this point, we successfully construct a set cover within cardinally K" S K that covers U, so SETCOVER = true.
Therefore, we can check whether SETCOVER true by iterating K' from 1 K (< min(n, m} iterations), constructing the ATTKACT(K") problem, and querying the oracle. The whole process can be done in polynomial time assumping ((1) computation time of the ATTKACT(K") oracle.
To this point, have shown SETCOVER Sp ATTKACT. On the other hand, an undeterminisitic Turing machine can try different poisoning strategies by branching on whether to poison current
subpolicy and what actions be assigned to each poisoned subpolicy. The decision of whether the poisoning is successful can be done in polynomial time and 6 E ATTKACT (K) corresponds to the existence of successfully attacked branches. Thus, ATTKACT NP. Given that SETCOVER is an NP-complete problem, so does ATTKACT and MINSET (since MINSET = ATTKACT). 0
F.9 POSSIBLE ACTION SET IN DPARL
Proof of Theorem? 7 For case notation, we assume that Wmax I t + 1, and otherwise we let W max f- + 1. We let to max{f- Wmax + 1, 0} be the start time step of the maximum possible window.
We only need to prove the contrary: for any A \ A(K). within poisoning size K, the poisoned policy cannot choose a: (D(st.a) * a. We prove by contradiction: we assume that there exists such poisoning attack within poisoning size K that lets (Stgee: A(K) (Equation (10), a * a4 === =x((8t;)) Suppose the selected time window before the attack is W' (selected according to [Equation (1) based on AW and na), and the selected time window after the attack is W" (selected according to Equation (1) based on A W and Ng).
a. From the expression of
If W" = W
Suppose we use the TPARL aggregation policy with window size W = W instead of current DPARL aggregation policy, then will have (f(5-W"411)) a₂ and (+ = a. Thus, according to the definition of possible action set (Definition 5) a e A(K) where A(K) is defined by Equation (9) Theorem This implies that A(K) where A(K) defined by
Equation (10) which contradicts the assumption that a E A A(K).
If W' + W":
According to the definition in Equation (10)
I WW"
min W WWW 40
L.a > K.
15 W.
31

---

Published as a conference paper at ICLR 2022
We define of
arg aa Map ( Then, the above equation implies that
L W W
K
a.0
and thus
W
0.0g
g0)) + ('
W w
(n
-n nw 1aa > ail <0.
axt
Since g 2 0 by definition Equation (7))
(0) W'
W' n
(n W' - ot 1aa > arl < 0,
(36)
where a arg max su auEA nop (w-w) and n is a shorthand of na no(s(-w+11)
Following the derivation from Equation (27) to (a): we have
Σ + n
W" (m
-1 1-1|a > ad 2 W' -
W (mar
-W
) - > ar}.
Combined with Equation (36)
W (ia
W (Na
n a
1/a > arl <0
(37)
On the other hand, the successful attack assumption, Le., TD (Stort)) and TD (Stoa) implies that
ax.
W Paw
- n2 W
(2)
ow
AW
(38)
W
W
where ">" is ">" if de In the above equation,
(2) arg max Nap aw = arg max Rao ao
W
aW
(2)
arg max n ao fo AgEA
aoEA
Intuitively, after poisoning, (2) is the runner-up action at window W ow is the action at window (2) W', and ow is the runner-up action at window W". We rewrite Equation (38)
W' 7 W
2 W
- 7 (2) + 1/a > ag)
(39)
We have the following two observations:
1. W - W margin should be the smallest.
** 2 W W als, since a the top action and (22) is the runner-up action and their
WW W" W W because 1) if a; aw,, LHS equals to RHS; 2) if a, + ow
Paw
at
LHS 2 O and RHS < 0.
Plugging these two observations to two sides of Equation (39) we get
W
WW'
2 W n 1/a a.).
(40)
This contradicts with Equation (37)
Since in both cases, we find contradictions. Now we can conclude that for any a E A\A(K), within poisoning size K, the poisoned policy cannot choose a: (s # a.
G ADDITIONAL EXPERIMENTAL DETAILS
G.1 DETAILS OF THE OFFLINE RL ALGORITHMS AND IMPLEMENTATIONS
We experimented with three offline RL algorithms: DQN Mnih et al. 2013). QR-DQN (Dabney
et al. 2018). and C51 (Bellemare et al. 2).7). The first one is the standard baseline, while the latter two are distributional RL algorithms which show SOTA results in offline RL tasks. We first briefly introduce the algorithm ideas, followed by the implementation details.
32

---

Published as a conference paper at ICLR 2022
Algorithm Ideas. The core of Q-learning WWakkins & Dayan 1992) is the Bellman optimality
equation (Bellman 1966)
(s = ER(s,a) + + max Q" (s',
(41)
d'EAA
where a parameterized Q" is adopted to approximate the optimal Q and iteratively improved. In DQN (Mnih et al.] (013) specifically, the parameterization is achieved by using a convolutional neural network (LeCun et al. 1998). In contrast to estimating the mean action value Q" (s, a) in DQN, distributional RL algorithms estimate a density over the values of the state-action pairs. The distributional Bellman optimality can be expressed as follows:
(42) Concretely, QR-DQN (Dabney et al. 2018) approximates the density D with a uniform mixture of K Dirac delta functions, while CSI (Bellemare et al., 2017) approximates the density using a categorical distribution over a set of anchor points.
Z' (s, - r + +Z* (s', arggmaaateA Q" (s',a') where r R(ssa)).
Implementation Details. For training the subpolicies using offline RL training algorithms, we use the code base of AAgawal et al. 2020). The configuration files containing the detailed hyperparam- eters can be found their public repository https: / com/ gowglooogeeee.ooo research batch r rl/tree/ / master/ (batch_rrrri rt/fnrrr/eeeeeeeee replay hatplllyccooiggg
For the three methods DQN, QR-DQN, and C51, the names of the configuration files are dqn gin, quantile gin, and c51 . gin, respectively. On each partition, we train the subpolicy for 50 epochs.
G.2 CONCRETE EXPERIMENTAL. PROCEDURES
We conduct experiments on two Atari 2600 games. Freeway and Breakout from OpenAl Gym (Brockman et al. 2016), and one autonomous driving environment Highway (Leurent 2018).
Bollowing/Section 4
Concretely, in the training stage, we first partition the training dataset into u partitions (u 30, 50, or 100) by using the hash function h(()) pre-defined in each environment. Let s be the i-th value in the state representation and d be the dimensionality of the state. In Atari games where the state is the game frame, /(T) is defined as the sum of all pixel values of all frames in the trajectory i.e., ((TT) = E.er Evelay s². In Highway where the state a floating point number scalar containing the positions and velocities of all vehicles, we define h(T) =.er Eig(a f(s') where f R + Z a deterministic function that maps the given float value integer space. Concretely, we take f(x as the the sum of the higher 16 bits and the lower 16 bits of its 32-bit representation under IEEE 754 standard (group of the Microprocessor Standards Subcommittee & Institute, 1985). We then train the subpolicies on the partitions with offline RI. training algorithm Mo E (DQN (Mnih et al., 2013), QR-DQN (Dabney et al. 2018), C5I (Bellemare et al. 2017)). The detailed description of the algorithms can be found in Appendix G.I
In the aggregation stage, we apply the three proposed aggregation protocols (PARL (Theremm 8). TPARL Theorem I), and DPARL (Theorem 3)) on the trained u subpolicies and derive the aggre- gated policies np. TT. and TD accordingly.
Finally, in the certification stage, for each aggregated policy, we provide the per-state action and cumulative reward certification following our theorems. When certifying the per-state action, we constrain the maximum trajectory length H 1000 for Atari games and H 30 for Highway (which is the full length in Highway) and report results averaged over 20 runs; for the cumulative reward certification, we adopt the trajectory length H 400 for evaluating Freeway, H 75 for Breakout, and H = 30 for Highway.
Configuration of Trajectory Length H. For Atari games, we do not evaluate the full episode length (up to tens of thousands steps), since our goal is to compare the relative certified robustness of different RL algorithms, and the evaluation on relatively short trajectory is sufficient under af- fordable computation cost. Moreover, different episodes in Atari games are oftentimes of different lengths; thus it necessary that we restrict the episode length to enable fair comparison. For Highway, we evaluate the full episode (Hf = 30) where we can efficiently achieve effective comparisons.
33

---

Published as a conference paper at ICLR 2022
Table Benign empirical performance of three aggregation protocols (PARL, TPARL, and DPARL) applied on subpolicies trained using three offline RL algorithms (DQN, QR-DQN, and C51). with the number of sub- policies (i.e #partitions) equal to 30 or 50. We report results averaged over 20 runs of varying randomness in the environment.
Freeway
50
TPARI.
TPARI
TPARI
TPARI
TPARI.
TPARI.
DPARI.
PARI
(W
2)
(W =3) 3)
(W 4)
(Wrox 5)
PARI:
(W 2)
(W 3)
(W
(W
5)
DQN
10.90 2.77
11.65
2:30
11.25 1:35
12,00 a.0
11.45 2034
10,95 2000
11.60 10
12.40 200
g00
11.90 1:00
QR-DQV
11.60 20s
11.85
11,25
1:0
11.80
gm
11,50
200
11.50
12.15
go0
12.80 2001
11.90
2:777
C51
11.20 2aw
12:45
1:30
12:55
1:10
11.40 4.
12.40 c0
11.70
am
11.80 200
12.70 201
11.50 2m0
11.95 1000
Breakont
50
TEARL
IPARL
TRARL
TPARL
DPARL
PARL
(W 2)
(W 3)
(W 4)
(Waus 5)
PARI
(W 2)
(W - 3)
(W 4)
(W Wans 5)
DQN
58.65
38.05
26.00
1
36,00
60.25
37.90
25.90
14.95
45,00
QR-DQN 76.50 mas
45.25
2.4300
22.05 aM
19.05 1mm
42.05
ms
62.80
2m
32.10
40.25 1
17.30 2m
41.00 =000
C51
51.80
1834
37.60
1123
24.75
1227
13.55
2m
34.75
1291
60.55
224
34,85
108
26,15 km
19.65
130
39.90 600
Highway
50
TPARL
TPARL
TEARL
DPARL
TPARL
TPARL
TPARL
DPARL
PARL
(W 2)
(W
(W
max 5)
PARL
(W
(W
(W Wase 5)
DQN
28.07 136
19.16 1a3
16.83 aM
12.69 ac.
23.55 9m0
29.05 ao0
16.63 9.0
15.85 a:::
13.43 1:3
22.51
QR-DON
28.52
15.53
12.77 632
23.11
TM
am
20.59
10
14.94
14.13
23.49
C51
28.86 us
20.20 922
13.30 500
9.36 333
21.51
201
27.44
432
15.12
16.13
10.61
a:
19.94 1134
H ADDITIONAL EVALUATION RESULTS AND DISCUSSIONS
H.1 BENIGN EMPIRICAL PERFORMANCE
We present the benign empirical cumulative rewards the three aggregation protocols (PARL, TPARL, and DPARL) applied on subpolicies trained using three offline RL algorithms (DQN, QR- DQN, and C51) in Table 4 The cumulative reward is obtained by running a trajectory of maximum length H and accumulating the reward achieved at each time step.
We discuss the conclusions on multiple levels. We choose H = 1000 for Atari games and H = 30 for Highway environment and report results averaged over 20 runs On the RL algorithm level, we see that QR-DQN achieves the highest score in most cases. On the aggregation protocol level, temporal aggregation enhances the performance Breakout and Highway. We particularly note that the results obtained by using temporal aggregation (TPARL and DPARL) gives significantly smaller variance compared the single-step aggregation PARL, especially in Breakout. This implies that temporal aggregation can help stabilize the policy. However, the conclusion does not hold in Highway, which is an interesting phenomenon that is worth investigating. On the partition number level, a larger partition number can give slightly better results. On the environment level, Freeway is simpler and more stable than Breakout and Highway.
Freeway while dampens the performance on
H.2 COMPARISON OF COPA WITH STANDARD TRAINING
We provide additional experimental results on the comparison between the empirical performance of our COPA and the standard training in terms of the convergence speed (Figure 3) and policy quality
Table 5).
we aim to show the comparison of the convergence speed. For our proposed training, we plot all training curves of the sampled 5 subpolicies in blue, where each subpolicy is trained on one partition of the dataset. (We do not plot all 50 curves for visual clarity.) For standard training, we plot the training curve of the standard policy in red, where the single policy is trained on the entire dataset. We see that on Freeway, most subpolicies converge slower than the standard policy, but will reach similar convergence value the standard training one; while there also exist a few subpolicies that fail to be trained. On Breakout, within 50 epochs, we observe substantial fluctuation for the training curves of all the policies, well large variance for the achieved reward at the last
In Figure: 3
34

---

Published as a conference paper at ICLR 2022
training curve (Freeway)
training curve (Breakout)
training curve (Highway)
20
200
subpolidee
25
250
standard policy
25
20
subpolices
standare polcy
150
100
subpelicies standard
10
10
2400 3000
Figure 3: The convergence speed of the proposed partition-based fraining compared with the standard training. For proposed training, plot all training curves of the sampled 5 subpolicies in blue, where each subpolicy trained one partition of the dataset. (We do not plot all 50 curves for visual clarity). For standard training, we plot the training curve the standard policy in red, where the single policy is trained on the entire dataset. In Atari games, we train each policy (or subpolicy) for a fixed number of 50 epochs, where each epoch consumes 1M randomly sampled training data. In Highway environment, we train each policy (or subpolicy) for fixed number of 3000 epochs, where each epoch consumes 1K randomly sampled training data. The offline RL algorithm used is DQN.
Table 5: The policy quality measured by empirical cumulative reward of the proposed aggregation proto- cols (PARL, TPARL, and DPARL) compared with the standard training. In our aggregation, we aggregate over subpolicies with equal 30 50. We report results averaged over 20 runs of varying randomness the environment, where each run episade of length at most 1000 for Atari games and 30 for Highway environment. The offline RL algorithm used DQN.
standard trained policy
1 30
50
TPARL
DPARL
TPARL (W 4)
DPARL
PARL
(W 4)
(Wmax 5)
PARL
(W
5)
Freeway 12.00 + 0.89
10.90 0.0.1
12,00 0.4
11.45 + 0.74
10.95 = 0.9
11.65 + 6.0.5
11.90 0.9
Breakout 97.60 + 11n.2
58.65
+ 40.3
13.50
+ 11.11
36.00 + 13:30
60.25 31.99
14.95
+:224
45.00 + 13.44
Highway 28.90 + o.7
28.07 + 3.6
12.69 6.13
23.55 + 9:01
29.05 as2
13.43
+ 8.29
22.51 800
epoch. Thus, on these two Atari games, we cannot draw conclusions w.r.t. the convergence. Given more computational resources run more epochs, we would be able to draw more informative conclusions. In contrast, on Highway, all subpolicies display similarly good convergence properties, showing comparable convergence speed and value with the standard training the entire dataset.
In Table 5]
we aim to compare the policy quality of the aggregated policy derived in our COPA framework (i.e., PARL, TPARL,, and DPARL) with the policy obtained from standard training. We see that on Freeway, our three protocols achieve comparable results with the policy obtained by standard training on the entire dataset; on Breakout, although the quality our obtained policies is lower, our policies are much more stable with significantly lower variance than the standard training; on Highway, only PARL obtains comparable results to the standard training policy, indicating the lack of temporal continuity in this environment.
Table 6: Average window size (i.e., Et,, We/T) for the aggregation protocol DPARL (Wixx = 5) ap- plied on subpolicies trained using three offline RL. algorithms (DQN, QR-DQN, and C51), with the number of subpolicies (i.e,, #partitions) a equal 30 50. We report results averaged over all time steps 20 runs.
u 30
u 50
DQN
QR-DQN
C51
DQN
QR-DQN
C51
Freeway 2.69 im
2.59
2.64 1.44
2.79 am
2.70 2
2.72 1.73
Breakout
2.28 146
2.44
2.32
2.33
1.4
2.40
1.52
2.39
Highway
1.97 + 044
2.21 4 uz7
2.16 0.3
2.23
2.26
+ 0224
2.18 = 0.37
35

---

Published as a conference paper at ICLR 2022
Table 7: Runtime (unit: seconds) the aggregation protocol DPARL (Wmax 5) applied on subpolicies trained using offline RL algorithm DQN, with the number of subpolicies (i.e., partition number) u equal to 30 or 50. We compare with the standard testing which tests the runtime of single trained DQN policy without using our framework. We report results averaged over 20 runs of varying randomness in the environment, where each is an episode of length at most 1000.
standard testing
DPARL (ar = 30)
DPARL (u 50)
Freeway
2.53 1 0.50
56.37 1 1.75
79.05 1 4.27
Breakout
2.00 + 0.56
72.05 1309
108.05 #.71
H.3 MORE ANALYTICAL STATISTICS FOR DPARL
Selected Window Size. We provide the mean and variance for the selected window sizes in DPARL in Table 6. In our experiments, the maximum window size Wmax = 5, while the aver- age selected window sizes are all around half of the maximum value. Thus, the average certification time is expected to be much smaller compared with the worst-case time complexity.
Running Time. We provide the running time in Table Specifically, we compare the running time of DPARL (W 5) applied on 30 or 50 subpolicies trained using offline RL algorithm DQN with the normal testing which tests the runtime framework. As we have shown in the remark Theorem 3 Jin[Section 4.3, the time complexity of DPARL is (Wanxl_A) lA|uu + W Wmax|A| [A(2u log 2). In Table 7, we also see that the runtime of DPARL scales roughly quasilinearly with the number of subpolicies and quadratically with the action set size [A], which 3 for Freeway and 4 for Breakout. We omit the runtime for Highway, since the horizon length, the environment type, and the neural network size are all different for Highway and Atari games.
single trained DON policy without using
H.4 MAXIMUM TOLERABLE POISONING THRESHOLD vS. TOTAL TRAJECTORY NUMBER
We provide the total number of trajectories in the offline dataset used for training the environments Freeway, Breakout and Highway below, well as the corresponding ratio of the maximum tolerable poisoning threshold w.r.t. the total number of trajectories. For Freeway, the total number of trajec- tories in the entire offline dataset is 121,892, and the ratio (max K, / # total trajectories) is 0.0002; for Breakout, the number is 209,049, and the ratio is 0.0001. We emphasize that, as shown in previ- work on probable defense against poisoning in supervised learning (Levine & Feizi, 2020). the number of instances they can certify is also not high especially for challenging tasks (e.g.. certifying 20 instances on the dataset GTSRB in Levine & Feizi| (2020), attaining the ratio 0.0005), which may imply the intrinsic difficulty of certifying against poisoning attacks. Given such difficulty, we already achieve reasonable certification as the first work on certified robust RL against poisoning, and we hope future works can further improve upon results.
H.S COMPARISON OF FREEWAY, BREAKOUT, AND HIGHWAY
Freeway and Breakout are two typical types of games with distinctive game properties. Freeway is simple game where the agent aims to cross the road and avoid the traffic. In most of the time steps, the agent would take the "forward" action; only when there is need to avoid the traffic will the agent stop and wait. In comparison, the game Breakout involves more complicated interactions between the paddle and the environment. The paddle position and velocity both play important roles in order to eatch and bounce the ball at an appropriate angle, which requires a frequent switch of the paddle moving direction. Similar to Breakout, as autonomous driving environment, Highway requires the agent to accurately analyze the rapidly changing environment around it and react quickly, leading to frequent changes in vehicle's actions.
Given the properties of the environments, we note that in Freeway, adjacent time steps may share consistent action selections, which is not necessarily true in the Breakout would be expected to be beneficial to consider the past history for making the current decision in Freeway, while the past history may interfere with the action selection in Breakout and Highway.
and Highway. Thus, it
36

---

Published as a conference paper at ICLR 2022
Table 8: Action change ratio (in percentage) of three aggregation protocols (PARL, TPARL, and DPARL)
applied on subpolicies trained in Highway environment using three offline RL algorithms (DQN, QR-DQN, and C51), with the number of subpolicies (i.e., #partitions) u equal to 30, 50, or 100. We report results averaged over 20 runs of varying randomness in the environment.
Aggregation Protocol
RL Algorithm
TPARL (W = 4)
DPARL
PARL
(W max
5)
DQN QR-DQN
59.79
24.89 10447
33.82 8.5
30
61.00
31.14
37.80
7.66
C51
59.00 10.30
18.17 11.52
35.44 8.5
DQN
55,50 1: 8M4
26.05 11,09
40.07 1374
50
QR-DQN
60.37
10.31
28.48
37.78
12:15
C51
59.39
12.34
28.04 10.71
38.21 = 11.23
DQN
48,67
22.17 7.65
33.45
9.70
100
QR-DQN
61.17 8
24.12 9.8
36.76 7887
C51
61.83 10.41
22.91
34.06 9.19
Comparisons of Bottleneck states in Atari Games. In Breakout, the game goal is to control the paddle so that the ball is bounced to hit the brick. There are clearly very different stages in the Breakout game, egg., when the ball is flying towards the paddle and when it is bounced back. An example of the bottleneck stale is when the ball is approaching the paddle. The poisoning behavior may lead to the disastrous effect that the policy learns to control the paddle to slide in the opposite direction of the ball at such bottleneck states, while other states may not be as vulnerable. In comparison, in Freeway, the game goal is to control the agent to cross the road while avoiding the traffic. The agent faced with similar traffic conditions everywhere on the road, and can make stable choices regardless of the complex situation. Thus there are very few bottleneck states.
Study on the Frequeney of Action Change in Highway. In Table we present the action change ratio (# action changes / trajectory length) in Highway environment. Comparing among the aggregation protocols, we first note that the single-step aggregation policy тт frequently alters actions as the reaction to the rapidly changing driving environment, while the temporal aggregation protocol Wy changes actions less frequently. This is because in TPARL, the agent explicitly forced to take stable actions based fixed window size. Second, comparing the action change ratio with the benign empirical performance in TTalle 4 we observe that TP and TT achieves the highest and lowest empirical performance respectively, which indicates the correlation between action change ratio with the achieved empirical reward. Specifically, in TPARL, the action change is limited as result of the enforced window size, leading to the limited benign performance.
H.6 FULL RESULTS OF ROBUSTNESS CERTIFICATION FOR PER-STATE ACTION STABILITY
As complete set of results for per-state action certification apart from Figure in Section 5. present the entire cumulative histogram of tolerable poisoning thresholds in Figure 4 Figure 5] together with the average tolerable poisoming thresholds in Table 9 The definitions of the two metreis can be found in Section 5.1
Basically, the conclusions in terms of the comparisons the RL algorithm level, the aggregation protocol level, the partition number level, and the game level are all similar to that derived in Sec-
tion 5.1
H.7 FULL RESULTS OF ROBUSTNESS CERTIFICATION FOR CUMULATIVE REWARD BOUND
In addition the evaluation results provided in Figure 2 in section 5.2 we provide
compre-
hensive set of evaluation results with more settings of trajectory length H here in Figure 6
We draw similar conclusions discussed in Section 5.2 Specifically, in Highway, C51 achieves higher certified lower bounds than other two when the poisoming size is large, which can be explained by the larger portion of states that can tolerate large poisoning sizes shown in Figure 5
37

---

Published as a conference paper at ICLR 2022
PARL
TPARL (W - 4)
DPARL (Wmax 5)
Freeway, 30
Freeway, 50
subiiity rañño
1.0
DQN
0.4
0,2
0.2
0.0
012345 1011121314
0.0
012345672 20112114155711892222222
QR-DQN stabiiity ra80o
0.6
0.4
0.2
0.0
01234567
1011121314 991111211111
0.0
012345678 90112133555011160022222
stabiitty ralto
1.0
C51
0.6
0.6
0.4
0.2
0.0
1011121314
01234567 901182114456011119222222222
2 K
2 K
(a) Freeway
Breakout, a == 30
Breakout, a == 50
1.0
1.0
0.8
0.8
DQN
stability
0.6
0123456 1011121314
0
1.0
1.0
QR-DQN siibility
0.8
0,8
01234567 1011121314
0123456788
stabiitt nitio
1.0
0.8
1.0
0.8
C51
0.6
0.0
1011121111
0123450
2011221344111171152222222
2
2
(b) Breakout
Figure 4: Robustness certification for per-state action stability on Atari games (full results). We plot the cumulative histogram the tolerable poisoning size K for all time steps in one trajectory. We provide results on two games (Freeway and Breakout), two partition numbers
30 and u = 50), and a comparison of three certification methods (PARL, TPARL, and DPARL). The results are averaged over 20 runs considering the randomness in the game environment, and the short vertical bar on top of each bar represents the standard deviation.
38

---

Published as a conference paper at ICLR 2022
PARL
TPARL 4W
DPARL (Wms= 5)
Highway, 30
Highway, 50
1.0
DQN
stability
Ap.
1011121314
0
QR-DQN stabiltyy Ralo
K..
0.0
012342 1011121314
2021222324
stability rablo
CSI
44
1011121314
2 K
K
Highway, 100
subility ratta
DQN
0.3 89868
QR-DQN subliit mill
01234500
394041 4849
stabiiity raba
2.0 23 99888
C51
0123456
2627202830
46474849
2 KK
Figure 5: Robustness certification for per-state action stability Highway environment (full results). We plot the cumulative histogram of the tolerable poisoning size K for all time steps in one trajectory. We provide results on Highway environment, three partition numbers (u 30, comparison of three certification methods (PARL, TPARL, and DPARL). The results averaged over 20 runs considering the randomness standard deviation.
50 and = 100), and
environment, and short vertical bar on top of each bar represents
PARL
30, TPARL (W
30, DPARL (Wre: =5)
TPARL
Freeway, H 100 Freeway, H 200 Freeway, H 400 Breakout, H 50 Breakout, H 75 Highway, H 30
K
33
QR-DON -K
20
15
25
12
15
20
25
13
15
20
25
336
202222
12 15
20
25
C51
K
Poisoning size K
Poisoning size Poisoning size K
Poisoning size K
Poisoning size K
Poisoning size
Figure 6: Robustness certification for cumulative reward (full results), We plot the lower bound of cumu- lative reward Jx w.t.t poisoning size K under three different certification methods (PARL, TPARL (W = 4), DPARL (W max 5)) with two partition numbers (u {30, 50)). Each row corresponds to one RL algorithm, and each column corresponds setting of trajectory length H.
39

---

Published as a conference paper at ICLR 2022
Table 9: Average tolerable poisoning thresholds of three aggregation protocols (PARL, TPARL, and DPARL) applied on subpolicies trained using three offline RL algorithms (DQN, QR-DQN, and C51), with the number of subpolicies (i.e, #partitions) equal to 30 or 50. We report results averaged over 20 runs of varying randomness in the environment.
Freeway
50
TPARL
DPARI.
TPARL.
DPARI.
PARL
(W 4)
(Wiax 5)
PARL
(W = 4)
(Winx 5)
DQN
9,90 0014
10.21 =:
10.30
16.78
17.16 0.29
16.88
QR-DQN
9.87 0:20
10.11 0.30
10.16 0.4
16.79 0.52
17.31 0.29
17.03 0.40
C51
9.57 0.2
0.15
10.11 0.19
16.82 a.
17.08 0.34
17.61 0.15
u 30
a 50
Breakout
TPARL
DPARL
TPARL (W
DPARL
PARL
(W
(W max
PARL
(W
DQN
1.08 0.09
1.28 0.15
0.85 20000
2.07 0
1.92 0:30
1.55 0.28
OR-DQN
1.38
1.33
1.18
2.12
1.93 0.14
1.71 2.19
C51
1.10
0.08
1.42 0.19
0.93 2.13
2.43 1 0211
2.37 4:0.9
6.19
M 30
50
Highway
TPARL
DPARL
TPARL
DPARL
PART.
(W = 4)
(W max
PART.
(W = 4)
(W max 5)
DQN
4.38
2.99 1.08
3.75
7.16
6.27 1.1
6.32
QR-DQN
4.18 am
3.35
1.44
2.84 0.5
6.52
1.17
5.02 1.00
4.61 1.20
C51
4.97 1.8
4.31
+ 1.45
4.12 0.8
7.95
à 1.46
6.55 1:00
6.69 1,47
We additionally point out that the value Jx achieved at poisoning size (e.g. Lx =
for Freeway, 2 for Breakout, and 28.31 for Highway under тт over = 50 DQN subpolicies) corresponds to the case where there is no poisoning at all on the training set. Our successive bounds under larger K are non-vacuous compared to this value.
I A BROADER DISCUSSION ON RELATED WORK
1.1 POISONING ATTACKS IN RI.
Below, we provide brief discussion on the related works on policy poisoning and reward poison- ing (Ma et al., 20199) Sun al. 2021 Huang & Zhu 2019).
Ma et al. (2019) and Huang & Zhu 2019) study reward poisoning where the attacker can modify rewards an offline dataset or reward signals during the online interaction. The attacker's goal is to force learning a particular target policy, or minimize the agent's 's reward in the original task. Under this framework, Ma et al. (2019) considers two victim learners with specific assump- tions on the learner structure and develops attacks for them, while Huang & Zhu (2019) provides theoretical analysis on the conditions for successful attacks against a Q-learning agent. In compari- to only reward poisoning in Ma al. (2019) and Huang et al. (2017). Sun al. (2021) focuses on general policy poisoning attacks for policy gradient learners in the online RL setting by using the vulnerability-wwaree
metric to decide when poison, and the adversarial critic guide the
poisoning. [Sun et al. (202T) achieve successful poisoning against policy-based agents in various complex environments online RL, but it remains an interesting open problem as to how to poison the offline RL dataset which is agnostic to the learning algorithm.
1.2 EMPIRICALLY ROBUST RL
Robust RL against Evasion Attacks. We briefly review several categories of RL methods that demonstrate empirical robustness against evasion attacks.
40

---

Published as a conference paper at ICLR 2022
Randomization methods (Tobin et al., exploration. This type of method was later systematically studied for its potential to improve model robustness. NoisyNet (Fortunato et al. 2017) adds parametrie noise to the network's 's weight during training, providing better resilience to both training-time and test-time attacks (Behzadan & Munir, 2017 2018), also reducing the transferability of adversarial examples, and enabling quicker recovery with fewer number of transitions during phase transition.
2017 Akkaya et al. 2019) were first proposed to encourage
Under the adversarial training framework, Kos Song (017) and Behzadan & Munir (2017) show that re-training with random noise and FGSM perturbations increases the resilience against adversarial examples. Pattanaik et al.] (2018) leverage attacks using an engineered loss function specifically designed for RL to significant increase the robustness to parameter variations. RS- DQN (Fischer et al. 2019) an imitation learning based approach that trains a robust student-DQN in parallel with standard DQN in order to incorporate the constrains such as SOTA adversarial defenses (Madry et al. 2017; Mirman et 2018).
SA-DQN (hhng et al.
2020a) is a regularization based method that adds regularizers to the training loss function to encourage the top-1 action to stay unchanged under perturbation.
Built on top of the neural network verification algorithms (Gowal et al. 2018 Weng et al. 2018), Radial-RL. (Oikarinen et al.] 2020) proposes to minimize an adversarial loss function that incor- porates the upper bound of the perturbed loss, computed using certified bounds from verification algorithms. CARRL (Everett et al., (02T)) aims to compute the lower bounds of action-values under potential perturbation and select actions according to the worst-case bound, but it relies linear bounds (Weng et al. 2018) and is only suitable for low-dimensional environments.
These robust RL methods only provide empirical robustness against perturbed state inputs during test time, but cannot provide theoretical guarantees for the performance of the trained models under any bounded perturbations.
Robust RL against Poisoning Attacks. Baanhaahhmm et al. (202 considers the threat model of reward poisoning attacks proposed by Ma et al. (2019); Rakhsha et al. (2020); [Zhang al. (2020b), where the attacker aims to force learning a target policy while minimizing the cost of reward manip- ulation. As shown in Ma et al. ) Rakhsha et al. (2020): Zhang et al. (2020b), this optimization problem is feasible and always has a unique optimal solution. Leveraging this property. [Banihashem al. (202T) formulates the defense task as another optimization problem which aims optimize the agent's s worst case performance among the set of plausible candidates of the true reward function. They specifically consider two settings regarding the agent's 's knowledge of the attack parameter, and provide lower bounds on the performance of the defense policy. In contrast to Banihashem et al. (022I) which focuses on a specific type of attack, our paper considers the threat model of general poisoning attacks, where the attacker has the power to manipulate the training trajectories arbitrarily. Given limited knowledge regarding the attack, our proposed COPA framework is general and appli- cable to any potential attack. Our robustness is derived from the aggregation over both sub -olipolic level and temporal level. One similarity between [Banihashem et al. (2021) and our work is that we both aim to provide lower bounds of the cumulative reward for our proposed method the provable guarantee/ / certification criteria.
1.3 ROBUSTNESS CERTIFICATION FOR RL
Wu et al. (2022) provide the first robustness certification for RL against test-time evasion attacks following the line of work on randomized smoothing (Cohen et al. 2019 Salman et al. 2019). Con- cretely, they apply per-state smoothing to achieve the certification for per-state action stability, as well trajectory smoothing to obtain the certification for cumulative reward. Notably, Wu et al. (022) propose an adaptive tree search algorithm to explore all possible trajectories and thus de- rive the robustness guarantee for cumulative reward. The relationship between our COPA-SEARCH and their Algorithm 3 is discussed in detail in Appendix E.3] In comparison, robustness in their work is derived from smoothing, while our robustness comes from aggregation. We propose aggre- gation protocols and certification methods that leverage the temporal information by dynamically aggregating over the past time steps, which is not covered in Wu et al. (2022).
41


Reviews:
[{"review_id": "zUHjNzR6Vu_", "reviewer": "Reviewer_6rjC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n\n1. The studied problem, certifiable defense against poisoning in offline RL, is important to the community. As far as I know, this is the first method in certifying both per-state action stability and cumulative reward against offline poisoning attacks in RL.\n2. The problem setup is clearly stated. The authors provide analysis for 3 aggregation protocols, which could be helpful for understanding the  partition-aggregation based methods in RL.\n3. The experiment compares several deep RL methods in terms of their intrinsic vulnerability, which is interesting.  \n\nWeaknesses:\n\n1. For writing:\n\n(1) Many details and definitions that are essential for understanding the method are omitted to the Appendix, which makes the flow of the paper not very smooth, especially in Section 3. \n\n(2) I don't see the necessity of separately discussing 3 aggregation protocols in the main paper. The 3 methods do not differ by a lot. The empirical results in Figure 1 and 2 also show that they do not have significant differences. Discussing all 3 protocols separately results in the weakness mentioned above -- too many details are omitted in the main paper. I would like to see the authors focus on the most interesting one in the main paper and provide detailed explanations, then put the other two variants to the Appendix.\n\n(3) Some notations are not very clear. For example, $K_t$ is not defined in or before Theorem 1. Does it mean the poisoning threshold such that the action in the $t$-th step does not change? What is $p$ in Theorem 1? What is the argmax operation in Equation 3 maxing over? This is the most important result in the paper, but the presentation is really confusing.\n\n2. For the proposed algorithm:\n\n(1) The temporal continuity assumption does not seem to be a standard one in RL literature. Can the authors justify how realistic this assumption is?\n\n(2) I am very confused by the COPA-SEARCH algorithm. Why can the learner search in the MDP in the offline setting where the agent is only supposed to have access to a set of trajectories? For example, in Algorithm 5 Line 24, the learner directly queries the transition function P for the next state of $s_t,a$. The Input of Algorithm 5 also requires the environment $\\mathcal{E}$. If the algorithm requires to query the environment arbitrarily, the algorithm does not make any sense. If you already know the MDP dynamics, the poisoning in trajectories do not matter at all. This is the biggest concern I have. Please let me know if I missed any important statement.\n\n3. For the evaluation:\n\n(1) The authors compute the certified poisoning threshold $\\bar{K}$, but do not present the number of total trajectories. \n\n(2) The experiment results are not convincing. Deep RL training requires a large number of trajectories (millions of interactions), but the certified $\\bar{K}$ provided by the proposed method is too small (around 10) based on Figure 1. That is, the defense method is too weak. In the cumulative certification, there is no comparison between the performance of the proposed method and the vanilla training method under practical poisoning attacks, so that we do not know how good the method is in terms of practical defending. There is only the result of the computed reward lower bound in Figure 2. More importantly, the certified lower bounds are too low, and become vacuous (lower bound=0) when $K>10$ or $K>5$. A normal DQN agent in Breakout should get >300 rewards. But the lower bound is 0~2, which does not make much sense, because the reward in Breakout is no smaller than 0.\n\n4. Some related works are missing. For example, [1] also proposes a defense method agains poisoning attacks, although in a different setting. It is worth mentioning this work and discussing the differences between the settings of this paper and [1].\n\n[1] Banihashem, Kiarash, Adish Singla, and Goran Radanovic. \"Defense Against Reward Poisoning Attacks in Reinforcement Learning.\" arXiv preprint arXiv:2102.05776 (2021).", "summary_of_the_paper": "This paper proposes a defense method against poisoning attacks in offline RL. The authors propose a framework named COPA to certify the number of tolerable poisoned trajectories. The proposed defense includes a partitioning stage which separate the (possibly poisoned trajectories), a training stage where $u$ sub-policies are trained with $u$ partitions,  and an aggregation stage where the sub-policies are aggregated to produce the final policy. Three aggregation protocols are proposed with corresponding certification results.", "summary_of_the_review": "This paper studies an interesting and important topic, and the proposed method makes intuitive sense. However there are many flaws in terms of writing, algorithm assumption, and empirical results. So I do no think this paper can be accepted before a major modification is made.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "xlW_lDt4gYr", "reviewer": "Reviewer_RQX2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Generally, the paper was well-written, although there are some organisational problems I would like to see addressed. As the authors mention, although poisoning attacks are major concern in practical settings, one may argue they are under-researched compared to test-time attacks. As far as I am aware, this is the first paper that proposes methods to certify an RL algorithm is robust to poisoning attacks, and the results look convincing. I will go through each of my main concerns / questions / misunderstandings below in no particular order:\n\n\n1. What is the motivation for developing three separate aggregation protocols? From the experiments, TPARL and DTPARL provide similar certification results. I would suggest the authors choose to present one protocol and defer the other two to the appendix, it would dramatically improve the readability of the work.\n\n\n2. As far as I understand, the number of sub-policies, *u*,  that need to be trained needs to be *at least* as large as the number of poisoned action-states / trajectories, *K*. Given that in offline RL one has a finite dataset to learn a policy on, what is the affect of varying *u* on the quality of these learned sub-policies? The certification method is dependent on some level of agreement between sub-policies, but if *u* needs to be very large will this not increase sub-policy variance? It seems from Appendix H.1 this is not true for *u*=30, 50, but it would be useful to show the utility and certification over a larger sweep of *u*.\n\n\n3. TPARL and DTPARL are based on the insight that not all states are created equal, and bottleneck / critical states are more important from a poisoning perspective. How much variance in window size is there for DPTARL? I'm interested in this because although the worst-case complexity is based on *W_max* should one not expect average certification time to be much smaller if the average window size is << *W_max*?\n\n\n4. Related to (3), it is claimed that certification time complexity *per state*  \"in practice adds negligible overhead compared with standard network policy inference.\". Maybe I missed this but I couldn't see any empirical results that back up this claim. The complexity looks like a bottleneck to me, being quadratic in the space of actions and linear in *u*. The latter is perhaps to be expected since this essentially says that if one wants to certify a policy is robust to a large adversarial poisoning budget, it will take more time than certifying against a smaller budget.\n\n\n5. The COPA-search algorithm is not clearly presented. Could the authors comment of the time-complexity of the search as I had trouble understanding this part.\n\n\n6. Could the authors comment on why QR-DQN and C51 are more certifiably robust than DQN? Initially I thought this may just be because they achieve higher utility but this is not the case (according to Appendix H.1)\n\n\n7.  How were the trajectory lengths chosen in Section 4.2?\n\n\n8. What is the intuition behind why Breakout is less stable than Freeway? Does it contain more critical / bottleneck states? It would have been very useful to perform a deeper analysis of robustness to poisoning attacks wrt bottleneck and non-bottleneck states.\n\n9. Could the authors comment on the relation between this work and [1]? Although the goals are different it feels like there is a surprising amount of overlap for an uncited paper: the name and organisation are similar, algorithms for per-state and cumulative reward certification are given, and are evaluated on similar datasets.\n\n[1] Wu et al. CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing. 2106.09292", "summary_of_the_paper": "This paper studies the problem of certifying a policy learned via an offline RL algorithm is robust to poisoning attacks. The authors propose two certification criteria: per-state action stability and lower bound of cumulative reward. Three different protocols are proposed, although they all based on ensembling / aggregation of sub-policy decisions. For the certification of cumulative reward, a tree-based search approach is given that evaluates all possible actions within a set. Experiments on Freeway and Breakout for a few different offline RL algorithms are given, showing Freeway can be certified to be robust to poisoning attacks for a large poisoning threshold, while Breakout cannot.\n\n", "summary_of_the_review": "Overall, I think this work represents a solid contribution to the field of robustness certification and RL, against what some may consider a more practical adversary than in evasion attack settings. There are a number of subtle algorithmic and experimental points that I would like the authors to clarify before raising my score, such as the complexity of COPA-search, and a more in-depth analysis of robustness to poisoning critical / bottleneck states over non-bottleneck states. I feel like this is a key point to address as it will provide stronger evidence of the deltas between the different aggregation protocols.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "wBAvqOOFGNK", "reviewer": "Reviewer_zvac", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n\n(1). This paper is the first to study policy certification for offline reinforcement learning. Given that \"poisoning attacks in RL\" is a popular recent topic, this paper is able to push the frontier of this research line even more and open potential future research questions.\n\n(2). The paper provided a systematic theoretical study of policy certification based on two criteria --- per-state action stability and cumulative reward lower bound. Both criteria are sensible since they characterize the objective of general RL tasks. The theoretical results can provide guidance for designing robust RL algorithms in the future research.\n\n(3). Experiments consolidated the theoretical findings in this paper.\n\nWeaknesses:\n\n(1). The idea of splitting the training set into subsets and then apply aggregation on sub-policies trained on each subset is not surprising, and has been studied a lot in previous works, e.g., in [1]. Therefore, the technical contribution of this paper seems a little bit weak, although it studied a new problem.\n\n(2). The applicability of the COPA certification framework is limited in the sense that it only applies to poisoning attacks where the attacker poisons a small fraction of training trajectories. However, an attacker may be able to slightly perturb all trajectories without incurring much effort. For example, the attacker just need to change the data point of a single step (e.g. the first step) in each trajectory, and that already breaks the assumption made in this paper. With all that, I mean the attacker ability is very weak and the certification against weak attackers is not a strong certification.\n\n(3). Another disadvantage of the paper is that the theorems involves very intensive symbols, which can be confusing to readers. The authors should consider adjusting how the results are stated to make it super clear.\n\n(4). Very related papers are missing in the reference. To list a few, please see [2-4]. The authors should discuss them in the related work.\n\n[1] Certified Robustness of Nearest Neighbors against Data Poisoning Attacks\n[2] Policy poisoning in batch reinforcement learning and control\n[3] Vulnerability-aware poisoning mechanism for online rl with unknown dynamics\n[4] Deceptive reinforcement learning under adversarial manipulations on cost signals", "summary_of_the_paper": "This paper studied how to certificate a policy when the training dataset is partially corrupted in the offline reinforcement learning scenario. Two criteria including per-state action stability certificate and cumulative reward lower bound certificate are proposed. Based on these two criteria, the paper designed the COPA, a general certificate framework, which provably achieved certain level of certificate. The COPA went through two phases during training, where in the first phase, the trajectories are split into subsets of equal size, then sub-policies are trained on each subset, and finally the sub-policies are aggregated to form a single learned policy. Experiments demonstrate the effectiveness of the proposed COPA certification framework. ", "summary_of_the_review": "Overall, I think the paper studied a very important and interesting problem, but the paper needs to be improved in writing, related work, and discussions on potential weakness of the COPA framework.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Es0x6RMTu9p", "reviewer": "Reviewer_xuEG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n\n1. The paper is well-written. It clearly states its main contributions and the intuition of the techniques used in  COPA.\n\n2. The paper proposes a certification framework against poisoning attacks in deep reinforcement learning, which is non-trivial. It advocates two certification criteria: per-state action stability and lower bound of cumulative reward.\n\n3. For each certification criteria, it provides bounds for different proposed aggregation protocols.\n\n4. In addition to theoretical results, the paper also presents numerical results.\n\n\nWeaknesses:\n\n1. I appreciate the authors' providing numerical results and the theoretical studies. However, it is unclear to me to what extent the introduction of the proposed method degrades the training of the RL algorithms (in terms of convergence speed and policy quality).  In particular, how does the proposed method perform compared with vanilla DRL algorithms when there are no adversarial attacks?  \n\n2. While the paper claims that \"there is no robust RL method that is able to provide practically computable certified robustness against poisoning attacks,\"  it might not be accurate.  There are a few related works on certified robustness in DRL.  For instance, \"Certifiable Robustness to Adversarial State Uncertainty in Deep Reinforcement Learning\" by Everett et al., and \"CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothing\" by Wu et al..  Though the exact settings could be different, the authors might want to compare the proposed method with the existing literature. \n", "summary_of_the_paper": "This paper proposes a certification method against poisoning attacks in offline reinforcement learning, where attackers can manipulate a subset of the training trajectories. It presents two certification criteria: per-state action stability and cumulative reward bound. It also introduces different aggregation protocols to train the policies and provides some bounds regarding the certification. In addition to theoretical results, it also has ablation studies to identify the implications of different parameters. ", "summary_of_the_review": "Solid work with minor issues that can be fixed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors develop a novel framework for certifying the robustness of RL agents against data poisoning attacks. They obtain lower bounds on the cumulative reward for several benchmark tasks.

Reviewers had concerns about certain organizational and technical aspects of the paper, but these were addressed well in the discussion phase and author responses. Hence, I recommend acceptance. However, I would urge the authors to incorporate points from the discussion phase into the revised version, in particular the discussion with reviewers xuEG and RQX2.
Decision: Accept (Poster)