Year: 2021

Abstract:
As reinforcement learning (RL) has achieved near human-level performance in a variety of tasks, its robustness has raised great attention when applied to safetycritical domains such as autonomous driving. Recent studies have explored testtime attacks in RL and corresponding defenses, while the robustness of RL against training-time attacks remains largely unanswered. In this work, we focus on certifying the robustness of offline RL in the presence of poisoning attacks, where a subset of training trajectories could be arbitrarily manipulated. We propose the first certification framework, COPA to certify the number of poisoning trajectories that can be tolerated regarding different certification criteria. Given the complex structure of RL, we propose two certification criteria: per-state action stability and cumulative reward bound. To tighten the certification, we also propose different partition and aggregation protocols to train robust policies. We further prove that some of the proposed certification methods are theoretically tight and some are NP-Complete problems. We conduct a thorough evaluation of COPA on different games trained with different offline RL algorithms: (1) The proposed temporal aggregation in COPA significantly improves certified robustness; (2) Our certifications for both per-state action stability and cumulative reward bound are efficient and tight; (3) The certification for different training algorithms and games are different, implying their intrinsic robustness properties.

text: As reinforcement learning (RL) has achieved near human-level performance in a variety of tasks, its robustness has raised great attention when applied to safetycritical domains such as autonomous driving. Recent studies have explored testtime attacks in RL and corresponding defenses, while the robustness of RL against training-time attacks remains largely unanswered. In this work, we focus on certifying the robustness of offline RL in the presence of poisoning attacks, where a subset of training trajectories could be arbitrarily manipulated. We propose the first certification framework, COPA to certify the number of poisoning trajectories that can be tolerated regarding different certification criteria. Given the complex structure of RL, we propose two certification criteria: per-state action stability and cumulative reward bound. To tighten the certification, we also propose different partition and aggregation protocols to train robust policies. We further prove that some of the proposed certification methods are theoretically tight and some are NP-Complete problems. We conduct a thorough evaluation of COPA on different games trained with different offline RL algorithms: (1) The proposed temporal aggregation in COPA significantly improves certified robustness; (2) Our certifications for both per-state action stability and cumulative reward bound are efficient and tight; (3) The certification for different training algorithms and games are different, implying their intrinsic robustness properties.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) has been widely applied to a range of applications, including robotics (Kober et al., 2013; Deisenroth et al., 2013; Polydoros & Nalpantidis, 2017) and autonomous vehicles (Shalev-Shwartz et al., 2016; Sallab et al., 2017). In particular, offline RL (Levine et al., 2020) is proposed to leverage previously observed data to 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 et al., 2020). For offline RL, the situation is even worse, and a recent theoretical study shows that the robust offline RL against poisoning attacks is a strictly harder problem than online RL (Zhang et al., 2021).
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 et al., 2020). Thus, robust 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 a 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 no robust RL 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 certification criteria, since the prediction consistency is no longer the only goal as in classification tasks. We propose two criteria based on the properties of RL: per-state action stability and cumulative reward bound. The per-state action stability guarantees that at a specific time, the policy learned with COPA will predict the same action before and after attacks under certain conditions. This criterion is important for guaranteeing the safety of the policy at critical states, e.g., stopping a vehicle when seeing pedestrians. For cumulative reward bound, a lower bound of the cumulative reward for the policy learned with COPA is guaranteed under certain poisoning conditions. This criterion directly guarantees the worst-case overall performance.
COPA Framework. COPA is composed of two components: policy partition and aggregation protocol and robustness certification method. We propose three policy partition aggregation protocols: 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 PARL and TPARL are theoretically tight. For cumulative reward bound, we propose an adaptive tree search algorithm, where we will compute the possible action set for each state under certain poisoning conditions. For PARL, we propose a novel method to compute the precise action set. For TPARL and DPARL, we propose efficient algorithms to compute a superset of the possible action set which leads to sound certification. We further prove that for PARL our 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 on 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 games with three offline RL
algorithms, demonstrating the effectiveness of COPA, together with several interesting findings.

heading: 2 CERTIFICATION CRITERIA OF COPA
text: In this section, we propose two robustness certification criteria for offline RL against general poisoning attacks: per-state action stability and cumulative reward bound.
Offline RL. We model the RL environment by an episodic finite-horizon Markov decision process (MDP) E = (S,A, R, P,H, d0), where S is the set of states, A is the set of discrete actions, R : S×A → R is the reward function, P : S×A → P(S) is the stochastic transition function withP(·) defining the set of probability measures, H is the time horizon, and d0 ∈ P(S) is the distribution of the initial state. At time step t, the RL agent is at state st ∈ S . After choosing action at ∈ A, the agent transitions to the next state st+1 ∼ P (st, at) and receives reward rt = R(st, at). After all H time steps, the agent’s cumulative reward J = ∑H−1 t=0 rt. We denote a consecutive sequence of all states between time step l and r as sl:r := [sl, sl+1, . . . , sr].
Here we focus on offline RL, for which the threat of poisoning attacks is practical and more challenging to deal with (Zhang et al., 2021). Concretely, in offline RL, a training dataset D = {τi}Ni=1 consists of logged trajectories, where each trajectory τ = {(sj , rj , aj , s′j)}lj=1 ∈ (S ×A×R×S)l consists of multiple tuples denoting the transitions (i.e., starting from state sj , taking the action aj , receiving reward rj , and transitioning to the next state s′j).
Poisoning Attacks. Training dataset D can be poisoned in the following manner. For each trajectory τ ∈ D, the adversary is allowed to replace it with an arbitrary trajectory τ̃ , generating a manipulated dataset D̃. We denote D D̃ = (D\D̃) ⋃ (D̃\D) as the symmetric difference between
two datasets D and D̃. For instance, adding or removing one trajectory causes a symmetric difference of magnitude 1, while replacing one trajectory with a new one leads to a 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 a clean environment. Specifically, in the training phase, the RL training algorithm and our aggregation protocol can be jointly modeled byM : 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 π̃ =M(D̃), given bounded poisoning size (i.e., |D D̃| ≤ K). Robustness Certification Criteria: Per-State Action Stability. We first aim to certify the robustness 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 a clean dataset D, we define the robustness certification for per-state action stability as that for any D̃ satisfying |D D̃| ≤ K, the action predictions of the poisoned and clean policies for the state (or state sequence) s 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 at step t by Kt.
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 as the poisoning size is within K (K computed in Section 3). In this definition, s could be either a state or a state sequence, since our aggregated policy (defined in Section 2) may aggregate multiple recent states to make an action choice.
Robustness Certification Criteria: Lower Bound of Cumulative Reward. We also aim to certify poisoned policy’s overall performance in addition to the prediction at a particular state. Here we measure the overall performance by the cumulative reward J(π) (formally defined in Appendix A).
Now we are ready to define the robustness certification for cumulative reward bound. Definition 2 (Robustness Certification for Cumulative Reward Bound). Robustness certification for cumulative reward bound is the lower bound of cumulative reward JK such that JK ≤ J(π̃) for any π̃ =M(D̃) where |D D̃| ≤ K, i.e., π̃ is trained on poisoned dataset D̃ within poisoning size K.

heading: 3 CERTIFICATION PROCESS OF COPA
text: In this section, we introduce our framework COPA, which is composed of training protocols, aggregation 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 2.
Overview of Theoretical Results. In Table 1, we present an overview of our theoretical results: For each proposed aggregation protocol and certification criteria, we provide the corresponding certification method and core theorems, and we also provide the tightness analysis for each certification.

heading: 3.1 PARTITION-BASED TRAINING PROTOCOL
text: COPA’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) byM0 : 2D → Π, where 2D is the power set ofD, and Π = {π : S → A} is the set of trained policies. Each trained policy in Π is a function mapping a given state to the predicted action.
Partitioning Stage. In this stage, we separate the training dataset D into u partitions {Di}u−1i=0 that satisfy ⋃u−1 i=0 Di = D and ∀i 6= j,Di ∩ Dj = ∅. Concretely, when performing partitioning, for each trajectory τ ∈ 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 a deterministic hash function h to compute the assignment, i.e., Di = {τ ∈ D | h(τ) ≡ i (mod u)},∀i ∈ [u]. Training Stage. In this stage, for each training data partition Di, we independently apply the chosen RL algorithmM0 to train a policy πi =M0(Di). Hereinafter, we call these trained polices as subpolicies to distinguish from the aggregated policies. Concretely, let [u] := {0, 1, . . . , u − 1}. For these subpolicies, the policy indicator 1i,a : S → {0, 1} is defined by 1i,a(s) := 1[πi(s) = a], indicating whether subpolicy πi chooses action a given current state s. The aggregated action count na : S → N≥0 is the number of votes across all the subpolicies for action a given current state s: na(s) := |{i | πi(s) = a, i ∈ [u]}| = ∑u−1 i=0 1i,a(s). Specifically, we denote na(sl:r) for∑r
j=l na(sj), i.e., the sum of votes for all states between time step l and r. A detailed algorithm description 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.

heading: 3.2 AGGREGATION PROTOCOLS: PARL, TPARL, DPARL
text: With u learned subpolicies {πi}u−1i=0 , 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 (Levine & 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 numerical order, lexicographical order, etc. Throughout the paper, we assume arg max over A 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 at most K subpolicies. 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 3.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, we need to focus 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 πT, which is formally defined in Definition 8 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 at 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 of 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 across recent W states.
Dynamic Temporal Partition Aggregation (DPARL). The TPARL uses a 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, it is preferable to perform dynamic temporal aggregation by using a 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 3 (Dynamic Temporal Partition Aggregation). Given subpolicies {πi}u−1i=0 and maximum window size Wmax, at time step t, the Dynamic Temporal Partition Aggregation (DPARL) defines
an aggregated policy πD : Smin{t+1,Wmax} → A such that πD(smax{t−Wmax+1,0}:t) := arg max
a∈A na(st−W ′+1:t), where W ′ = arg max 1≤W≤min{Wmax,t+1} ∆Wt . (1)
In the above equation, na is defined in Section 2 and ∆Wt is given by ∆Wt := 1
W (na1(st−W+1:t)− na2(st−W+1:t)) ,
where a1 = arg max a∈A na(st−W+1:t), a2 = arg max a∈A,a6=a1
na(st−W+1:t). (2)
In the above definition, ∆Wt encodes the average vote margin between top action a1 and runner-up action a2 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 Sections 3.3 and 3.4.
In Appendix B, we use a concrete example to illustrate bottleneck states and non-bottleneck states, and demonstrate how different aggregation protocols induce different tolerable poisoning thresholds.

heading: 3.3 CERTIFICATION OF PER-STATE ACTION STABILITY
text: In this section, we present our robustness certification theorems and methods for per-state action. For each of the aggregation protocols (PARL, TPARL, and DPARL), at each time step t, we will compute a valid tolerable poisoning threshold K as 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, we defer the robustness certification method for PARL to Appendix C. The certification method is based on Theorem 8. We further show the theoretical 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 1. Theorem 1. Let D be the clean training dataset; let πi =M0(Di), 0 ≤ i ≤ u − 1 be the learned subpolicies according to Section 3.1 from which we define na (Section 2); and let πT be the Temporal Partition Aggregation policy: πT = M(D) where M abstracts the whole training-aggregation process. D̃ is a poisoned dataset and π̃T is the poisoned policy: π̃T =M(D̃). For a given state st encountered at time step t during test time, let a := πT(smax{t−W+1,0}:t), then at time step t the tolerable poisoning threshold (see Definition 1)
Kt = min a′ 6=a,a′∈A max { p ∣∣∣ p∑ i=1 h (i) a,a′ ≤ δa,a′ }
(3)
where {h(i)a,a′}ui=1 is a nonincreasing permutation of min{W−1,t}∑
j=0
1i,a(st−j) + min{W, t+ 1} − min{W−1,t}∑
j=0
1i,a′(st−j)  u−1
i=0
=: {hi,a,a′}u−1i=0 , (4)
and δa,a′ := na(smax{t−W+1,0}:t) − (na′(smax{t−W+1,0}:t) + 1[a′ < a]). Here, 1i,a(s) = 1[πi(s) = a] (Section 2), and W is the window size.
Proof sketch. Let ts = max{t −W + 1, 0}. We consider the condition of successful poisoning, which is to enable a′ to satisfy ña′(sts:t) + 1[a
′ < a] > ña(sts:t) after the poisoning. We figure out the optimal attack strategy towards satisfying this constraint and negation of this optimal attack brings the theorem statement. We defer the detailed proof to Appendix F.2.
Remark. The theorem provides a valid per-state action certification for TPARL. The detailed algorithm is in Algorithm 3 (Appendix E.2). The certification time complexity per state is O(|A|u(W + log u)) and can be further optimized to O(|A|u log u) with proper prefix sum caching across time steps. We prove the certification for TPARL is theoretically tight in Proposition 2 with proofs in Appendix F.3. We also prove that directly extending Theorem 8 for TPARL (Corollary 10) is loose in Appendix F.4. Proposition 2. Under the same condition as Theorem 1, for any time step t, there exists an RL learning algorithm M0, and a poisoned dataset D̃, such that |D D̃| = Kt + 1, and π̃T(smax{t−W+1,0}:t) 6= πT(smax{t−W+1,0}:t).
Certification for DPARL. Theorem 3 provides certification for DPARL.
Theorem 3. Let D be the clean training dataset; let πi =M0(Di), 0 ≤ i ≤ u − 1 be the learned subpolicies according to Section 3.1 from which we define na (see Section 2); and let πD be the Dynamic Temporal Partition Aggregation: πD = M(D) where M abstracts the whole trainingaggregation process. D̃ is a poisoned dataset and π̃D is the poisoned policy: π̃D =M(D̃). For a given state st encountered at time step t during test time, let a := πD(smax{t−Wmax+1,0}:t) and W ′ be the chosen time window (according to Equation (1)), then tolerable poisoning threshold
KDt = min { Kt, min
1≤W∗≤min{Wmax,t+1},W∗ 6=W ′,a′ 6=a,a′′ 6=a LW
∗,W ′
a′,a′′
} (5)
where Kt is defined by Equation (3) with W as W ′ and L W∗,W ′ a,a′′ defined by the below Definition 4.
Definition 4 (L in Theorem 3). Under the same condition as Theorem 3, for givenW ∗,W ′, a, a′, a′′, we let a# := arg maxa0 6=a′,a0∈A na0(st−W∗+1:t), then
LW ∗,W ′
a′,a′′ := max { p ∣∣∣ p∑ i=1 g(i) +W ′(nW ∗ a′ − nW ∗ a# )−W ∗(nW ′ a − nW ′ a′′ )− 1[a′ > a] < 0 } (6)
where nwa is a shorthand of na(st−w+1:t) and {g(i)}ui=1 is a nonincreasing permutation of {gi} u−1 i=0 .
Each gi is defined by
gi := max{W∗,W ′}∑ w=0 max a0∈A σw(a0)− σw(πi(st−w)), where (7)
σw(a0) := W ′1[a0 = a ′, w ≤W ∗]−W ′1[a0 = a#, w ≤W ∗]−W ∗1[a0 = a,w ≤W ′] +W ∗1[a0 = a′′, w ≤W ′].
Proof sketch. A successful poisoning attack should change the chosen action from a to an another a′. If after attack, the chosen window size is still W ′, the poisoning size should at least larger than Kt according to Theorem 1. If the chosen window size is notW ′, we find out that the poisoning size is at least mina′′ 6=a L W∗,W ′ a′,a′′ +1 from a greedy-based analysis. Formal proof is in Appendix F.5.
Remark. The theorem provides a valid per-state action certification for DPARL policy. The detailed algorithm is in Algorithm 4 (Appendix E.2). The certification time complexity per state is O(W 2max|A|2u+Wmax|A|2u log u), which in practice adds similar overhead compared with TPARL certification (see 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.

heading: 3.4 CERTIFICATION OF CUMULATIVE REWARD BOUND
text: In this section, we present our robustness certification methods for cumulative reward bound. We assume that the RL environment is deterministic throughout the cumulative reward certification for convenience, i.e., the transition function is P : S×A → S and the initial state is a fixed s0 ∈ S. The certification goal, as listed in Definition 6, is to obtain a lower bound of cumulative reward under poisoning attacks, as long as the poisoning size is within K. The cumulative reward certification is based on a novel adaptive tree search algorithm COPA-SEARCH inspired from Wu et al. (2021). We tailor the algorithm to certify against poisoning attacks instead of adversarial state perturbations as in Wu et al. (2021). A detailed discussion and complexity analysis of the algorithm is in Appendix E.3.
COPA-SEARCH Algorithm Description. The pseudocode is in Algorithm 5 (Appendix E.3). The method starts from the base case: when the poisoning threshold Kcur = 0, the lower bound of cumulative reward JKcur is exactly the reward without poisoning. The method then gradually increases the poisoning threshold Kcur, by finding the immediate larger K ′ > Kcur that can expand the possible action set along the trajectory. With the increase of Kcur ← 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 a trajectory tree. Once all new trajectories are explored, the method examines all leaf nodes of the tree and figures out the minimum reward among them, which is the new lower bound of cumulative reward JK′ 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 s0:t, the subpolicies {πi}u−1i=0 , the aggregation protocol (PARL, TPARL, or DPARL), and the poisoning size K, the possible action set A
at step t is a subset of action space: A ⊆ A, such that for any poisoned policy π̃, as long as the poisoning size is within K, the chosen action at step t will always be in A, i.e., at = π̃(s0:t) ∈ A.
Possible Action Set for PARL. The following theorem gives the possible action set for PARL. Theorem 4 (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 t
AT (K) = { a ∈ A ∣∣∣ ∑ a′∈A max{na′(st)− na(st)−K + 1[a′ < a], 0} ≤ K } . (8)
We defer the proof to Appendix F.6.1. Furthermore, in Appendix F.6.2 we show that: 1) The theorem gives theoretically tight possible action set; 2) In contrast, directly extending PARL’s per-state certification gives loose certification.
Possible Action Set for TPARL. The following theorem gives the possible action set for TPARL. Theorem 5. Under the condition of Definition 5, suppose the aggregation protocol is TPARL as defined in Definition 8, then the possible action set at step t
A(K) = { a ∈ A ∣∣∣ K∑ i=1 h (i) a′,a > δa′,a, ∀a ′ 6= a } , (9)
where h(i)a′,a and δa′,a 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 a 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 NPcomplete, which indicates the robustness property of proposed TPARL. Theorem 6. Under the condition of Definition 5, suppose the aggregation protocol is TPARL as defined in Definition 8, then computing a possible action set A(K) such that any possible action set S satisfies |A(K)| ≤ |S| is NP-complete.
Possible Action Set for DPARL. The following theorem gives the possible action set for DPARL. Theorem 7. Under the condition of Definition 5, suppose the aggregation protocol is TPARL as defined in Definition 3, then the possible action set at step t
A(K) = {at} ∪ { a′ ∈ A ∣∣∣ min 1≤W∗≤min{Wmax,t+1},W∗ 6=W ′,a′′ 6=at LW ∗,W ′ a′,a′′ ≤ K }
∪ { a ∈ A ∣∣∣ K∑ i=1 h (i) a′,a > δa′,a, ∀a ′ 6= a } (10) where at = πD(smax{t−Wmax+1,0}:t) is the clean policy’s chosen action, W ′ is defined by Equa-
tion (1), LW ∗,W ′
a′,a′′ is defined by Definition 4 with a being replaced by at, and h (i) a′,a, δa′,a is defined in
Theorem 1 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.

heading: 4 EXPERIMENTS
text: In this section, we present the evaluation for our COPA framework, specifically, the aggregation protocols (Section 3.2) and the certification methods under different certification criteria (Section 3.3 and 3.4). We defer the description of the offline RL algorithms (DQN (Mnih et al., 2013), QRDQN (Dabney et al., 2018), and C51 (Bellemare et al., 2017)) used for training the subpolicies to Appendix G.1, and the concrete experimental procedures to Appendix G.2. As a summary, we obtain similar conclusions for both per-state action certification and cumulative reward certification: 1) QR-DQN and C51 are more certifiably robust than DQN; 2) temporal aggregation (PARL and TPARL) achieves higher certification for games explicitly satisfying temporal continuity, e.g., Freeway; 3) larger partition number (u = 50) improves the certified robustness; 4) Freeway is a more stable and robust game than Breakout. More interesting discussions are deferred to Appendix H.

heading: 4.1 EVALUATION OF ROBUSTNESS CERTIFICATION FOR PER-STATE ACTION STABILITY
text: We provide the robustness certification for per-state action stability based on Section 3.3.
Experimental Setup and Metrics. We evaluate the aggregated policies πP, πT, and πD following Section 3.2. Basically, in each run, we run one trajectory (of maximum length H) using the derived policy, and compute Kt at each time step t. Given {Kt}H−1t=0 , we obtain a cumulative histogram— for each threshold K, we count the time steps that achieve a threshold no smaller than it and then normalize, i.e., ∑H−1 t=0 1[Kt≥K]/H. 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 ∑H−1 t=0 Kt/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 1. We plot partial poisoning thresholds on the x-axes here, and omit the full set of results in Appendix H.6, where we also report the average tolerable poisoning thresholds. In the Appendix, we additionally report benign empirical reward in H.1 and compare with standard training in H.2. We include more analytical statistics for DPARL in H.3, and report the maximum tolerable poisoning threshold vs. the total number of trajectories in H.4.
The cumulative histograms in Figure 1 can be compared in different levels. Basically, we compare the stability ratio at each tolerable poisoning thresholds 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 algorithm. On the aggregation protocol level, we observe different behaviors on different games. 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, the single-step aggregation PARL is oftentimes better. This difference is due to the different properties of games. Our temporal aggregation is developed based on the assumption of consistent action selection in adjacent time steps. This assumption is true in Freeway while violated in Breakout. A more detailed explanation of different game properties is omitted to Appendix H.5. On the partition number level, a larger partition number (u = 50) generally allows larger tolerable poisoning thresholds. Finally, on the game level, Freeway achieves much higher certified robustness for per-state action stability than Breakout, implying that Freeway is a game that accommodates more stable and robust policies than Breakout.

heading: 4.2 EVALUATION OF ROBUSTNESS CERTIFICATION FOR CUMULATIVE REWARD BOUND
text: We provide the robustness certification for cumulative reward bound according to Section 3.4.
Experimental Setup and Metrics. We evaluate the aggregated policies πP, πT, and πD following Theorem 4, Theorem 5 and Theorem 7. We compute the lower bounds of the cumulative reward JK w.r.t. the poisoning size K using the COPA-SEARCH algorithm introduced in Section 3.4. We adopt the trajectory length H = 400 for evaluating Freeway and H = 75 for Breakout.
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 methods—higher value of the lower bound implies stronger certified robustness. On the RL algorithm level, similar to the conclusion in Section 3.4, QR-DQN and C51 invariably outperform the baseline DQN algorithm. On the aggregation protocol level, on Freeway, methods with temporal aggregation consistently surpass the single-step aggregation PARL, while PARL achieves better performance on Breakout, which is due to the similar analysis in Section 4.2. In addition, we note that DPARL is sometimes not as robust as TPARL. We hypothesize two reasons: 1) the dynamic mechanism is more susceptible to 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 as discussed in Theorem 7. On the partition number level, a larger partition number (u = 50) demonstrates higher robustness. On the game level, Freeway can tolerate a larger poisoning size than Breakout. More results and discussions are omitted to Appendix H.7.

heading: 5 RELATED WORK
text: 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., 2021), and both empirical defenses (Liu et al., 2018; Chacon et al., 2019; Peri et al., 2020; Steinhardt et al., 2017) and certified defenses (Weber et al., 2020; Levine & Feizi, 2021) have been proposed. Robust RL against reward poisoning is studied in Banihashem et al. (2021), but robust RL against general poisoning is less explored.
From the attack side, Kiourti et al. (2020) show that effective poisoning attacks, in particular backdoor attacks, exist in RL. A recent work theoretically and empirically validates the existence of reward poisoning in online RL (Zhang et al., 2020b). Furthermore, Zhang et al. (2020a) 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. (2020a) propose robust variants of the Least-Square Value Iteration algorithm that provides probabilistic robustness guarantees under linear MDP assumption. In contrast, we aim to provide the first certified robustness for general offline RL algorithms against poisoning attacks. We discuss broader related work in Appendix I.

heading: 6 CONCLUSIONS
text: In this paper, we proposed COPA, the first framework for certifying robust policies for offline RL against poisoning attacks. COPA proposes three different policy aggregation protocols: PARL, TPARL, and DPARL. For each aggregation protocol, COPA can provide a sound certification for both per-state action stability and cumulative reward bound. Our experimental evaluation on different games and different offline RL training algorithms shows the effectiveness of our robustness certification in a wide range of scenarios.
Ethics Statement. In this paper, we prove the first framework for certifying robust policies for offline RL against poisoning attacks. On the one hand, such framework provides rigorous guarantees in practice RL tasks and thus significantly alleviates the security vulnerabilities of offline RL algorithms against training-phase poisoning attacks. The evaluation of different RL algorithms also provides a better understanding about the different degrees of security vulnerabilities across different RL algorithms. On the other hand, the robustness guarantee provided by our 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 a large number of training instances or modify the training algorithm itself. As a result, we encourage researchers to understand the potential risks, and evaluate whether our constraints on the attack align with their usage scenarios when applying our COPA to real-world applications. We do not expect any ethics issues raised by our work.
Reproducibility Statement. All theorem statements are substantiated with rigorous proofs in Appendix F. In Appendix E, we list the pseudocode for all key algorithms. Our experimental evaluation is conducted with publicly available OpenAI Gym toolkit (Brockman et al., 2016). We introduce all experimental details in both Section 4 and Appendix G. Specifically, we build the code upon the open-source code base of Agarwal et al. (2020), and we upload the source code as the supplementary material for reproducibility purpose.

heading: A OMITTED DEFINITIONS

heading: A.1 CUMULATIVE REWARD
text: Definition 6 (Cumulative Reward). Let P : S × A → P(S) be the transition function with P(·) defining the set of probability measures. Let R, d0, H be the reward function, initial state distribution, and time horizon. We denote J(π) as the cumulative reward of the given policy π:
J(π) := E H−1∑ t=0 R(st, at), where at = π(st), st+1 ∼ P (st, at), s0 ∼ d0, (11)
It is natural to adapt this definition when there is a discount factor. If policy π considers recent nt states instead of only st to make action predictions, we can change at = π(st) to at = π(st−nt+1:t) in Equation (11).

heading: A.2 PARL (PER-STATE PARTITION AGGREGATION) PROTOCOL
text: Definition 7 (Per-State Partition Aggregation). Given subpolicies {πi}u−1i=0 , the Per-State Partition Aggregation (PARL) protocol defines an aggregated policy πP : S → A such that
πP(s) := arg max a∈A na(s), (12)
where na(s) is defined in Section 2.
As mentioned in Section 3, when the arg max in Equation (12) returns multiple elements, we break ties deterministically by returning the “smaller” (<) action, which can be defined by numerical order, lexicographical order, etc.

heading: A.3 TPARL (TEMPORAL PARTITION AGGREGATION) PROTOCOL
text: Definition 8 (Temporal Partition Aggregation). Given subpolicies {πi}u−1i=0 and window size W , at time step t, the Temporal Partition Aggregation (TPARL) defines an aggregated policy πT : Smin{t+1,W} → A such that
πT(smax{t−W+1,0}:t) = arg max a∈A na(smax{t−W+1,0}:t), (13)
where sl:r and na are defined in Section 2.
In the above definition, at time step t, the input of policy πT contains all states between time step max{t −W + 1, 0} and t within window size W ; and the output is the policy prediction with the highest votes across these states. Recall that in Section 2, we define na(sl:r) = ∑r j=l na(sj). We break ties in the same way as in PARL.
B ILLUSTRATION OF COPA AGGREGATION PROTOCOLS
We use a concrete example to illustrate bottleneck states and non-bottleneck states, and demonstrate how different aggregation protocols induce different tolerable poisoning thresholds.
Suppose the action space contains two actions A = {a1, a2}, and there are six subpolicies {πi}u−1i=0 where u = 6. We are at time step t = 7 now. When there is no poisoning, the subpolicies’ action predictions for state s0 to s7 are shown by Table 2. After aggregation, all aggregated policies will choose action a1 at t = 7.
Bottleneck States and Non-Bottleneck States. According to our illustration in Section 3.2, bottleneck states are those where subpolicies vote for diverse actions but the best action is the same as previous states, and non-bottleneck states are those where subpolicies mostly vote for the same action. As we can see, s0 to s6 are non-bottleneck states since the sub-policies almost unanimously vote for one action. In contrast, s7 is a bottleneck state.
PARL (Definition 7). The PARL aggregation protocol only uses the current state s7 to aggregate the votes. On s7, three subpolicies choose action a1 and three others choose action a2. By breaking the tie with a1 < a2, the PARL policy πP(s7) = a1. The tolerable poisoning threshold Kt = 0,
because one action flipping from a1 to a2 by poisoning only one subpolicy can change the aggregated policy to a2.
TPARL (Definition 8). The TPARL aggregation protocol uses window sizeW = 7. This implies that, we aggregate all states s1:7 to count the votes and decide the action. Since na1(s1:7) = 36 and na2(s1:7) = 6, after poisoning two subpolicies, we still ña1(s1:7) ≥ ña2(s1:7). Thus, we achieve an tolerable poisoning threshold Kt = 2.
Compared with PARL, the temporal aggregation in TPARL increases the vote margin between a1 and a2 and thus improve the tolerable poisoning threshold at current state.
DPARL (Definition 3). The DPARL aggregation protocol chooses the window sizeW ′ = 8 since this window size gives the largest average vote margin ∆W ′
t (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 a1 can be kept higher than votes for a2. However, when it comes to K = 2, if we totally flip subpolicies π0 and π1 to let them always predict action a2, then the DPARL aggregated policy will turn to chooseW ′ = 1 as the window size and then choose action a2 as the action output. Thus, we achieve a tolerable poisoning threshold Kt = 1 this time.
In summary, we can observe that for the bottleneck state s7, both TPARL and DPARL exploit temporal aggregation to boost the certified robust poisoning threshold (from 0 to 2 and from 0 to 1 respectively), thus demonstrating the effectiveness of TPARL and DPARL on improving certified robustness. On the other hand, for non-bottleneck states s0 to s6, we can easily see that different aggregation protocols do not differ much in terms of provided certified robustness levels.
More Discussion about Bottleneck and Non-Bottleneck States. We provide additional discussions regarding why bottleneck states are vulnerable and why our temporal aggregation strategy can effectively 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 sub-policies on such states, they may lie close to the decision boundary. This may be a 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., 2021)), and may induce high instability of the rollouts during testing. We next discuss additional intuitions for our temporal aggregation. Essentially, temporal aggregation effectively leverages the adjacent non-bottleneck states to rectify the decisions at the bottleneck states, based on the assumption of temporal continuity which has been revealed and utilized in several previous works (Legenstein et al., 2010; Veerapaneni et al., 2020; Ye et al., 2021).

heading: C CERTIFICATION OF PER-STATE ACTION STABILITY FOR PARL
text: We certify the robustness of PARL following Theorem 8.
Theorem 8. Let D be the clean training dataset; let πi =M0(Di), 0 ≤ i ≤ u − 1 be the learned subpolicies according to Section 3.1 from which we define na (see Section 2); and let πP be the PerState Partition Aggregation policy: πP =M(D) whereM abstracts the whole training-aggregation process. D̃ is a poisoned dataset and π̃P is the poisoned policy: π̃P =M(D̃). For a given state st encountered at time step t during test time, let a := πP(st), then
Kt =
⌊ na(st)−maxa′ 6=a (na′(st) + 1[a′ < a])
2
⌋ . (14)
Remark. The theorem provides a valid per-state action certification for PARL, since according to Definition 1, as long as the poisoning size is smaller or equal to Kt, i.e., |D D̃| ≤ Kt, the action of the poisoned policy is the same as the clean policy: π̃P(st) = πP(st) = a. To compute Kt, according to Equation (14), we rely on the aggregated action count na for state st from subpolicies. The a′ < a is the “smaller-than” operator introduced following Definition 7.
Proof of Theorem 8. Suppose the poisoning size is within K, then after poisoning, the aggregated action count ña(st) ∈ [na(st)−K,na(st)+K] where na(st) is such count before poisoning. Thus, to ensure the chosen action does not change, a necessary condition is that ña(st) ≥ ña′(st)+1[a′ < a] for any other a′ < a. Solving K yields Equation (14).
We use the theorem to compute the per-state action certification for each time step t along the trajectory, and the detailed algorithm is in Algorithm 2 (Appendix E). Furthermore, we prove that this certification is theoretically tight as the following proposition shows. The proof is in Appendix F.1.
Proposition 9. Under the same condition as Theorem 8, for any time step t, there exists an RL learning algorithmM0, and a poisoned dataset D̃, such that |D D̃| = Kt + 1, and π̃P(st) 6= πP(st).

heading: D A TABLE OF POSSIBLE ACTION SET
text: Table 3: Expressions of possible action set A(K) given poisoning threshold K for different aggregation protocols. Full theorem statements are in Theorems 4, 5 and 7 (in Section 3.4).
Protocol A(K) PARL
{
a ∈ A
∣∣∣ ∑a′∈Amax{na′(st)− na(st)−K + 1[a′ < a], 0} ≤ K}
TPARL { a ∈ A
∣∣∣ ∑Ki=1 h(i)a′,a > δa′,a,∀a′ 6= a} DPARL {at} ∪ { a′ ∈ A ∣∣∣ min 1≤W∗≤min{Wmax,t+1},W∗ 6=W ′,a′′ 6=at LW ∗,W ′ a′,a′′ ≤ K } ∪ { a ∈ A ∣∣∣ K∑ i=1 h (i) a′,a > δa′,a,∀a ′ 6= a }
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 3.

heading: E ALGORITHM PSEUDOCODE AND DISCUSSION

heading: E.1 COPA TRAINING PROTOCOL
text: Algorithm 1: COPA training protocol. Input: training dataset D, number of partitions k, deterministic hash function h Output: COPA subpolicies {πi}k−1i=0
1 for i ∈ [k] do 2 Di ← {τ ∈ D | h(τ) ≡ i (mod k)} . Separate the training data D into k partitions 3 for each partition Di do 4 πi ←M0(Di) . Subpolicy trained on partition Di with offline RL algorithm M0 5 return {πi}k−1i=0

heading: E.2 COPA PER-STATE ACTION CERTIFICATION

heading: Per-State Partition Aggregation (PARL).
text: Algorithm 2: COPA per-state certification algorithm for Per-State Partition Aggregation (PARL). Input: environment E = (S,A, R, P,H, d0), subpolicies {πi}k−1i=0 Output: COPA robust size at each time step {Kt}H−1t=0 1 s0 ∼ d0 . sample initial state 2 for t from 0 to H − 1 do 3 for each a ∈ A do 4 Compute na(st) from subpolicies’ {πi}k−1i=0 decisions . na is defined in Section 2 5 Determine the chosen action at ← πP(st) according to PARL (Definition 7) 6 Compute Kt according to Equation (14) in Theorem 8 7 st+1 ∼ P (st, at) 8 return {Kt}H−1t=0

heading: Temporal Partition Aggregation (TPARL).
text: Algorithm 3: COPA per-state certification algorithm for Temporal Partition Aggregation (TPARL). Input: environment E = (S,A, R, P,H, d0), subpolicies {πi}k−1i=0 , window size W Output: COPA robust size at each time step {Kt}H−1t=0 1 s0 ∼ d0 . sample initial state 2 for t from 0 to H − 1 do 3 for each a ∈ A do 4 Compute na(st) from subpolicies’ {πi}k−1i=0 decisions . na is defined in Section 2 5 Determine the chosen action at ← πT(st) according to TPARL (Definition 8) 6 pmin ←∞ 7 for each a′ ∈ A, a′ 6= at do 8 for i from 0 to k − 1 do 9 Compute hi,at,a′ according to Equation (4)
10 {h(i)at,a′} k i=1 ← sorted({hi,at,a′} k−1 i=0 , reverse = True) 11 Compute δat,a′ 12 sum← 0, p← 0 13 for j from 1 to k do 14 if sum + h(j)at,a′ > δat,a′ then 15 p← j − 1 16 break
17 p← j, sum← sum + h(j)at,a′ 18 pmin ← min{pmin, p} 19 Kt ← pmin 20 st+1 ∼ P (st, at) 21 return {Kt}H−1t=0

heading: Dynamic Temporal Partition Aggregation (DPARL).
text: Algorithm 4: COPA per-state certification algorithm for Dynamic Temporal Partition Aggregation (DPARL). Input: environment E = (S,A, R, P,H, d0), subpolicies {πi}k−1i=0 , maximum window size Wmax Output: COPA robust size at each time step {Kt}H−1t=0 1 s0 ∼ d0 . sample initial state 2 for t from 0 to H − 1 do 3 for each a ∈ A do 4 Compute na(st) from subpolicies’ {πi}k−1i=0 decisions given st . na is defined in Section 2 5 Determine the chosen action at ← πD(st) and chosen window size W ′ according to DPARL (Definition 3) 6 pmin ←∞ 7 Kt ← Algorithm 3 . use Algorithm 3 with W replaced by W ′ to compute Kt 8 KDt ← Kt 9 for each a′ ∈ A, a′ 6= at do
10 for each a′′ ∈ A, a′′ 6= at do 11 for W ∗ from 1 to min{Wmax, t+ 1} do 12 a# ← arg maxa0 6=a′,a0∈A na0(st−W∗+1:t) 13 for w from 1 to max{W ′,W ∗} do 14 Compute maxa0∈A σ w(a0) according to Equation (7)
15 for i from 0 to k − 1 do 16 for w from 1 to max{W ′,W ∗} do 17 Compute σw(πi(st−w)) according to Equation (7)
18 Compute gi according to Equation (7)
19 {g(i)}ki=1 ← sorted({gi}k−1i=0 , reverse = True) 20 Compute nW ∗ a′ , n W∗ a# , n W ′ at , n W ′ a′′ 21 tmp←W ′(nW ∗ a′ − nW ∗ a# )−W ∗(nW ′ at − n W ′
a′′ )− 1[a′ > at] 22 sum← 0, p← 0 23 for j from 1 to k do 24 if sum + tmp ≥ 0 then 25 p← j − 1 26 break
27 p← j, sum← sum + g(j)
28 LW ∗,W ′
a′,a′′ ← p,K D t ← min{KDt , LW
∗,W ′
a′,a′′ }
29 st+1 ∼ P (st, at) 30 return {KDt }H−1t=0

heading: E.3 COPA CUMULATIVE REWARD CERTIFICATION
text: 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 in the form of search tree and progressively grows it. For each node (representing a game state), we leverage Theorems 4, 5 and 7 to compute the Possible Action Set. We then expand the tree branches corresponding to the actions in the derived set. In poisoning threshold growth, when all trajectories for the current poisoning threshold are explored, we increase K ′ to seek for certification 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.
The highlighted line in the following algorithm needs to inject different algorithms based on the aggregation protocol: for PARL (πP), use Theorem 4; for TPARL (πT), use Theorem 5; for DPARL (πD), use Theorem 7.
Algorithm 5: COPA-SEARCH: adaptive tree search for cumulative reward certification. Input: environment E = (S,A, R, P,H, d0), subpolicies {πi}k−1i=0 , aggregated policy πP or πT (with W ) or πT (with Wmax) Output: a map M that maps poisoning size K to corresponding certified lower bound of cumulative
reward JK . Initialize global variables
1 p que← ∅ . initialize an empty priority queue containing tuples of (state historys0:t, action a, poisoning size K, reward J) sorted by increasing K 2 Jglobal ←∞ . initialize global minimum reward 3 Function GETACTIONS(s0:t,Klim, Jcur): 4 A← possibleActions(s0:t, {πi}k−1i=1 , π∗,Klim) . compute the possible action set given
state history, subpolicies, aggregation policy π∗, and poisoning size according to theorems in Section 3.4
5 a list← ∅ 6 for each action a ∈ A do 7 if P (s, a) = ⊥ then 8 continue . game terminate here, no possible larger or lower cumulative reward
to search
9 a list← a list ∪ {a} . record possible actions to expand 10 if A 6= A then 11 K′ ← min
possibleActions(s0:t,{πi} k−1 i=0 ,π∗,K)6=A
K
12 Anew ← possibleActions(s0:t, {πi}k−1i=1 , π∗,K ′) \A . compute the immediate actions that
will possibly be chosen if enlarging the poisoning size
13 for each action a ∈ Anew do 14 p que.push((s0:t, a,K ′, Jcur))
15 return a list 16 Procedure EXPAND(s0:t,Klim, Jcur): 17 if Jcur ≥ Jglobal ∧ (step reward is non-negative) then 18 return . pruning
19 a list← GETACTIONS(s0:t, {πi}k−1i=0 , π∗,Klim) . compute according to theorems in Section 3.4 20 if a list = ∅ then 21 Jglobal ← min{Jglobal, Jcur} 22 return 23 for a ∈ a list do 24 st+1 ← P (st, a) 25 if st+1 = ⊥ then 26 Jglobal ← min{Jglobal, Jcur} 27 else 28 EXPAND (s0:t+1,Klim, Jcur +R(st, a))
29 M ← ∅ 30 s0 ← d0 . initial state is s0 31 EXPAND (s0,Klim = 0, Jcur = 0) . expand initial trajectory 32 while True do 33 if p que = ∅ then 34 break . no state to expand 35 (s0:t, a,K, J)← p que.pop() . pop out the first element 36 ( , ,K′, )← p que.top() . examine the next element 37 M(K)← Jglobal . obtain one new point of certification result 38 st+1 ← P (st, a) 39 EXPAND (s0:t+1,K ′, J +R(st, a)) . expand the tree from the new node
40 return M . indeed the algorithm can terminate at any time within the while loop
Time Complexity. The complexity of COPA-SEARCH is O(H|Sexplored|(log |Sexplored| + |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, |A| is the cardinality of action set, and T is the time complexity of per-state action certification. The main bottleneck of the algorithm is 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 game properties, exploring all possible states may be inevitable.
Relation with Wu et al. (2021). The COPA-SEARCH algorithm is inspired from Wu et al. (2021, 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 a probabilistic guarantee of RL robustness against state perturbations, while COPA-SEARCH derives deterministic guarantee of RL robustness against poisoning attacks. We think this general tree search methodology can be further extended to provide certification beyond evasion attack (Wu et al., 2021) and poisoning attack (our work) and we leave it as future work.

heading: F PROOFS

heading: F.1 TIGHTNESS OF PER-STATE ACTION CERTIFICATION IN PARL
text: 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 as B = {i ∈ [u] | πi(st) = a = πP(st)}. We also denote a′ = arg maxa′ 6=a na′(st)+1[a
′ < a]. According toKt’s definition (Equation (14)), |B| = na(st) > na(st)/2 ≥ Kt.
We now pick an arbitrary subset B′ ⊆ B such that |B′| = Kt + 1. For each i ∈ B′, we locate its corresponding parititioned dataset Di for training subpolicy πi. We insert one point pi to Di, such that our chosen learning algorithm M0 can train a subpolicy π̃i = M0(Di ∪ {pi}) that satisfies π̃i(st) = a
′. For example, the point could be pi = {(st, a′, s′,∞)} andM0 learns the action with maximum reward for the memorized nearest state, where s′ can be adjusted to make sure the point is hashed to parition i.1 Then, we construct the poisoned dataset
D̃ = ( ⋃ i∈B′ Di ∪ {pi} ) ∪  ⋃ i∈[u]\B′ Di  . Therefore, we have D̃ D = ∪i∈B′pi = |B′| = Kt + 1.
On this poisoned dataset, we train subpolicies {π̃i}u−1i=0 and get the aggregated policy π̃P. To study π̃P(st), we compute the aggregated action count ña on these poisoned subpolicies. We found that ña(st) = na(st)− |B′| and ña′(st) = na′(st) + |B′|. Therefore,
ña(st)− ña′(st) = na(st)− na′(st)− 2(Kt + 1) = na(st)− na′(st)− 2 (⌊na(st)− na′(st)− 1[a′ < a]
2
⌋ + 1 ) < na(st)− na′(st)− (na(st)− na′(st)− 1[a′ < a]) = 1[a′ < a].
Therefore, if a′ < a, ña(st) ≤ ña′(st), and a′ has higher priority to be chosen than a; if a′ > a, ña(st) ≤ ña′(st) − 1, and a′ still has higher priority to be chosen than a. Hence, π̃P(st) 6= a = πP(st). To this point, we conclude the proof with a feasible construction.
1Strictly speaking, we need to choose a determinisitc hash function h for dataset partitioning such that adjustment on s′ and reward (currently∞, but can be an arbitrary large enough number) can make the point being partitioned to i, i.e., h(pi) ≡ i (mod u). Since our adjustment space is infinite due to infinite number of large enough reward, such assumption can be easily achieved. Same applies to other attack constructions in the following proofs.

heading: F.2 PER-STATE ACTION CERTIFICATION IN TPARL
text: Proof of Theorem 1. For ease of notation, we let w = min{W, t+1} so w is the actual window size used at step t. We let t0 = t− w + 1, i.e., t0 is the actual start time step for TPARL aggregation at step t. Now we can write the chosen action at step t without poisoning as a = πT(st0:t).
We prove the theorem by contradiction: We assume that there is a poisoning attack whose poisoning size K ≤ Kt where Kt is defined by Equation (3) in the theorem, and after poisoning, the chosen action is aT 6= a. We denote {π̃i}u−1i=0 to the poisoned subpolicies and π̃T to the poisoned TPARL aggregated policy. From the definition of Kt, we have
K∑ i=1 h (i) a,aT ≤ Kt∑ i=1 h (i) a,aT ≤ δa,aT , (15)
since K ≤ Kt, and each h(i)a,aT is an element of hi′,a,aT for some i ′ where
hi′,a,aT = w−1∑ j=0 1i′,a(st−j) + w − w−1∑ j=0 1i′,aT (st−j) ≥ 0
by Equation (4) in the theorem. Since the poisoning attack within threshold K can at most affect K subpolicies, we let B be the set of affected policies and assume |B| = K without loss of generality. Formally,B = {i ∈ [u] | ∃t′ ∈ [t0, t], π̃i(st′) 6= πi(st′)}. Therefore, according to the monotonicity of h(i)
a,aT , from Equation (15), ∑
i∈B hi,a,aT ≤ K∑ i=1 h (i) a,aT ≤ δa,aT . (16)
According to the assumption of successfully poisoning attack, after attack, the sum of aggregated vote for aT plus 1[aT < a] should be larger then that of a. Formally, after the poisoning,
ñaT (st0:t) + 1[a T < a] > ña(st0:t)
or equivalently ña(st0:t)− (ñaT (st0:t) + 1[aT < a]) < 0. From the statement of Theorem 1, δa,aT = na(st0:t)− (naT (st0:t) + 1[aT < a]). Take the difference of the above two equations, we know that the attack satisfies na(st0:t)− ña(st0:t)− (naT (st0:t)− ñaT (st0:t)) > δa,aT . (17) Since the attack only changes the subpolicies in B, we have
na(st0:t)− ña(st0:t) = ∑ i∈B w−1∑ j=0 1[πi(st−j) = a]− w−1∑ j=0 1[π̃i(st−j) = a]  ≤ ∑ i∈B w−1∑ j=0 1i,a(st−j),
naT (st0:t)− ñaT (st0:t) = ∑ i∈B w−1∑ j=0 1[πi(st−j) = a T ]− w−1∑ j=0 1[π̃i(st−j) = a T ]  ≥ ∑ i∈B w−1∑ j=0 1i,aT (stj )− w
 . Inject them into Equation (17) yields∑
i∈B w−1∑ j=0 1i,a(st−j) + w − w−1∑ j=0 1i,aT (st−j)  ︸ ︷︷ ︸
hi,a,aT
> δa,aT
which contradicts Equation (16) and thus concludes the proof.

heading: F.3 TIGHTNESS OF PER-STATE ACTION CERTIFICATION IN TPARL
text: Proof of Proposition 2. For ease of notation, we let w = min{W, t+ 1} so w is the actual window size used at step t. We let t0 = t−w+ 1, i.e., t0 is the actual start time step for TPARL aggregation at step t. Now we can write the chosen action at step t without poisoning as a = πT(st0:t).
We prove by construction, i.e., we construct an poisoning attack with poisoning size Kt + 1 that deviates the prediction of the poisoned policy. Specifically, we aim to craft a poisoned dataset D̃ with poisoning size |D D̃| = Kt+1, such that for certain learning algorithmM0, after partitioning and learning on the poisoned dataset, the poisoned subpolicies π̃i =M0(D̃i) can be aggregated to produce different action prediction: π̃T(st0:t) 6= a.
Before construction, we first show that Kt given by Equation (3) satisfies Kt < u. If Kt = u, it means that for arbitrary a′ 6= a, u∑ i=1 h (i) a,a′ = u−1∑ i=0 hi,a,a′ = u−1∑ i=0 w−1∑ j=0 1i,a(st−j) + w − w−1∑ j=0 1i,a′(st−j)  = na(st0:t) + uw − na′(st0:t) ≤ δa,a′ = na(st0:t)− na′(st0:t)− 1[a′ < a], which implies uw ≤ 0 contracting uw > 0. Now, we know Kt < u, so Kt + 1, our poisoning size, is smaller or equal to u.
We start our construction by choosing an action aT : aT = arg min
a′ 6=a,a′∈A arg max∑p
i=1 h (i) a,a′≤δa,a′ p.
According to the definition of Kt in Equation (3), for aT we have Kt+1∑ i=1 h (i) a,aT > δa,aT . (18) We locate the subpolicies to poison as B = {i ∈ [u] | hia,aT is h (j) a,aT in the nonincreasing permutation in Equation (4), j ≤ Kt + 1} (19) Therefore, |B| = Kt + 1 and ∑
i∈B hi,a,aT > δa,aT (20)
by Equation (18). For each of these subpolicies i ∈ B, we locate its corresponding partitioned datasetDi for training subpolicy πi, and insert one trajectory pi toDi, such that our chosen learning algorithm M0 can train a subpolicy π̃i = M(Di ∪ {pi}) satisfying π̃i(st′) = aT for any t′ ∈ [t0, t]. For example, the trajectory could be pi = {(st′ , aT , s′,∞)}tt′=t0 andM0 learns the action with maximum reward for the memorized nearest state, where s′ can be adjusted to make sure the trajectory is hashed to partition i. Then, we construct the poisoned dataset
D̃ = ( ⋃ i∈B′ Di ∪ {pi} ) ∪  ⋃ i∈[u]\B′ Di  . Therefore, we have D̃ D = ∪i∈B′pi = |B′| = Kt + 1. Now, we compare the aggregated votes for a and aT before and after poisoning:
ña(st0:t)− na(st0:t) = ∑ i∈B w−1∑ j=0 1[π̃i(st−j) = a]− w−1∑ j=0 1[πi(st−j) = a]  = −
∑ i∈B w−1∑ j=0 1[πi(st−j) = a],
ñaT (st0:t)− naT (st0:t) = ∑ i∈B w−1∑ j=0 1[π̃i(st−j) = a T ]− w−1∑ j=0 1[πi(st−j) = a T ] 
= ∑ i∈B w − w−1∑ j=0 1[πi(st−j) = a T ]  . Now we compare the margin between aggregated votes for a and aT after poisoning:
ñaT (st0:t)− ña(st0:t) + 1[aT < a] =naT (st0:t)− na(st0:t) + 1[aT < a] + ñaT (st0:t)− naT (st0:t)− (ña(st0:t)− na(st0:t)) =− δa,aT + ∑ i∈B w−1∑ j=0 1[πi(st−j) = a] + w − w−1∑ j=0 1[πi(st−j) = a T ]
 =− δa,aT +
∑ i∈B hi,a,aT > 0.
As a result, after poisoning, aT has higher priority to be chosen than a, i.e., π̃T(st0:t) 6= a = πT(st0:t). To this point, we conclude the proof with a feasible attack construction.

heading: F.4 LOOSE PER-STATE ACTION CERTIFICATION IN TPARL AND COMPARISION WITH TIGHT ONE
text: The following corollary of Theorem 8 states a loose per-state action certification.
Corollary 10. Under the same condition as Theorem 1,
Kt =
⌊ na(smax{t−W+1,0}:t)−maxa′ 6=a ( na′(smax{t−W+1,0}:t) + 1[a ′ < a] )
2 min{W, t+ 1}
⌋ (21)
is a tolerable poisoning threshold at time step t in Definition 1, where W is the window size.
Proof of Corollary 10. We let w = min{t+ 1,W} to be the actual aggregation window size at time step t. After poisoning with size K, at most K subpolicies are affected and each affected policy can only make ±w changes to the aggregated action count. This implies that, after poisoning, for any action a′ ∈ A, the aggregated vote count ña′(st−w+1:t) ∈ [na′(st−w+1:t) − uw, na′(st−w+1:t) + uw]. Thus, when K ≤ Kt where Kt is defined in Theorem 1, for any a′ 6= a, we have ña(st−w+1:t)− ña′(st−w+1:t)− 1[a′ < a] =na(st−w+1:t)− na′(st−w+1:t)− 1[a′ < a]− 2Kw ≥na(st−w+1:t)− na′(st−w+1:t)− 1[a′ < a]− 2w ·Kt
≥na(st−w+1:t)− na′(st−w+1:t)− 1[a′ < a]− ( na(st−w+1:t)− max
a′′ 6=a (na′′(st−w+1:t) + 1[a
′′ < a]) ) = max a′′ 6=a (na′′(st−w+1:t) + 1[a ′′ < a])− (na′(st−w+1:t) + 1[a′ < a]) ≥ 0. From the definition of TPARL protocol, the poisoned policy still chooses action a, which implies Kt is a tolerable poisoning threshold.
In the main text, we mention that the certification from Corollary 10 is looser than that from Theorem 1. This assertion is based on the following two facts:
1. According to Proposition 2, the certification given by Theorem 1 is theoretically tight, which means that any other certification can only be as tight as Theorem 1 or looser than it.
2. There exists examples where the computed Kt from Theorem 1 is larger than that from Corollary 10. For instance, suppose W = 5, action set A = {a1, a2}, and there are three subpolicies. At time step t = 4, πi for s0 to s4 are [a1, a1, a1, a1, a2] for all subpolicies (i.e., i ∈ [3]). Thus, the benign policy πT(s0:4) = a1. By computation, the Kt from Theorem 1 is 1; while the Kt from Corollary 10 is 0. Indeed, Corollary 10 can be viewed as using 2w to upper bound hi,a,a′ = w + ∑w−1 j=0 1i,a(st−j)−∑w−1
j=0 1i,a′(st−j). Intuitively, Corollary 10 assumes every subpolicy can provide 2w vote margin
shrinkage, and Theorem 1 uses hi,a,a′ to capture the precise worse-case margin shrinkage and thus provides a tighter certification.

heading: F.5 PER-STATE ACTION CERTIFICATION IN DPARL
text: Proof of Theorem 3. Without loss of generality, we assume Wmax ≤ t + 1 and otherwise we let Wmax ← min{Wmax, t + 1}. We let t0 = max{t −Wmax + 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 a minimum over these tolerable poisoning thresholds gives the required result.
Specifically, we denote P to the predicate of robustness under poisoning attack: P = [π̃D(st0:t) = a], and denote K to the poisoning attack size. Therefore, we can decompose P as such: P = P(W ′) ∧ ∧
1≤W∗≤Wmax,W∗ 6=W ′ a′ 6=a
¬Q(W ∗, a′). (22)
Recall thatW ′ is the chosen window size by the protocol DPARL with unattacked subpolicies 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′ at window size W ∗ and average vote margin is larger (or equal if a′ < a) at window size W ∗ compared to W ′. Formally, let ña be the aggregated action count after poisoning and ∆̃Wt be the average vote margin after poisoning at window W (see Equation (2)),
P(W ′) = (
arg max a∈A ña(st−W ′+1:t) = a
) ,
Q(W ∗, a′) = (
arg max a∈A ña(st−W∗+1:t) = a ′ ) ∧(((
∆̃W ∗ t ≥ ∆̃W ′ t ) ∧ (a′ < a) ) ∨ (( ∆̃W ∗ t > ∆̃ W ′ t ) ∧ (a′ > a) )) .
(23)
According to Theorem 1, K ≤ Kt =⇒ P(W ′) where Kt is defined by Equation (3) with W replaced by W ′. The following Lemma 11 shows a sufficient condition for Q(W ∗, a′). We then aggregate these conditions together with minimum to obtain a sufficient condition for P:
K ≤ min { Kt, min
1≤W∗≤min{Wmax,t+1},W∗ 6=W ′,a′ 6=a,a′′ 6=a LW
∗,W ′
a′,a′′ } and thus conclude the proof.
Lemma 11. Let Q(W ∗, a′), K, W ′ be the same as defined in proof of Theorem 3, then K ≤ min
a′′ 6=a LW
∗,W ′
a′,a′′ =⇒ ¬Q(W ∗, a′), (24)
where LW ∗,W ′
a′,a′′ is defined in Definition 4.
Proof. We prove the equivalent form: Q(W ∗, a′) =⇒ K > min
a′′ 6=a LW
∗,W ′
a′,a′′ . (25)
Suppose a poisoning attack can successfully achieve Q(W ∗, a′), we now induce the requirement on its poisoning size K. First, we notice that((
∆̃W ∗ t ≥ ∆̃W ′ t ) ∧ (a′ < a) ) ∨ (( ∆̃W ∗ t > ∆̃ W ′ t ) ∧ (a′ > a) ) ⇐⇒W ∗W ′∆̃W ∗ t ≥W ∗W ′∆̃W ′ t + 1[a ′ > a]
(26)
since W ∗W ′∆̃W∗/W ∗
t is an integer by definition. According to the definition and Q(W ∗, a′)’s assumption arg maxa∈A ña(st−W∗+1:t) = a
′, W ∗W ′∆̃W ∗
t ≤W ′ (ña′(st−W∗+1:t)− ña#(st−W∗+1:t)) , where “≤” comes from the fact that the margin in ∆̃W∗t should be with respect to the runner-up class after poisoning, and computing with respect to any other class provides an upper bound. Here we choose a# = arg maxa0 6=a′,a0∈A na0(st−W∗+1:t) (see Definition 4), the runner-up class before
poisoning, to empirically shrink the gap between the bound and actual margin. On the other hand,
W ∗W ′∆̃W ′ t ≥W ∗ ( ña(st−W ′+1:t)− max
a′′ 6=a ña′′(st−W ′+1:t)
) ,
where “≥” comes from the fact that the margin in ∆̃W ′t 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
Q(W ∗, a′) =⇒W ′ (ña′(st−W∗+1:t)− ña#(st−W∗+1:t)) ≥W ∗ ( ña(st−W ′+1:t)− max
a′′ 6=a ña′′(st−W ′+1:t)
) + 1[a′ > a]
=⇒∃a′′ 6= a, W ′ (ña′(st−W∗+1:t)− ña#(st−W∗+1:t)) ≥W ∗ (ña(st−W ′+1:t)− ña′′(st−W ′+1:t)) + 1[a′ > a]. For each a′′ 6= a, now we use the last equation as the condition, and show that K > LW ∗,W ′
a′,a′′ is a necessary condition. This proposition is equivalent to
K ≤ LW ∗,W ′
a′,a′′
=⇒W ′ (ña′(st−W∗+1:t)− ña#(st−W∗+1:t)) < W ∗ (ña(st−W ′+1:t)− ña′′(st−W ′+1:t)) + 1[a′ > a]. (27)
Suppose a poisoning attack within poisoning size K changes the subpolicies in set B ⊆ [u]. Note that |B| ≤ K. We inspect the objective in Equation (27): W ′ (ña′(st−W∗+1:t)− ña#(st−W∗+1:t))−W
∗ (ña(st−W ′+1:t)− ña′′(st−W ′+1:t))− 1[a′ > a] =W ′ (na′(st−W∗+1:t)− na#(st−W∗+1:t))−W ∗ (na(st−W ′+1:t)− na′′(st−W ′+1:t))− 1[a′ > a]
+ ∑ i∈B
( W ′
W∗−1∑ w=0 1[π̃i(st−w+1) = a ′]−W ′ W∗−1∑ w=0 1[π̃i(st−w+1) = a #]
−W ∗ W ′−1∑ w=0 1[π̃i(st−w+1) = a] +W ∗ W ′−1∑ w=0 1[π̃i(st−w+1) = a ′′]  − ∑ i∈B ( W ′ W∗−1∑ w=0 1[πi(st−w+1) = a ′]−W ′ W∗−1∑ w=0 1[πi(st−w+1) = a #]
−W ∗ W ′−1∑ w=0 1[πi(st−w+1) = a] +W ∗ W ′−1∑ w=0 1[πi(st−w+1) = a ′′]  =W ′ (na′(st−W∗+1:t)− na#(st−W∗+1:t))−W ∗ (na(st−W ′+1:t)− na′′(st−W ′+1:t))− 1[a′ > a]
+ ∑ i∈B max{W∗,W ′}∑ w=0 σw(π̃i(st−w))− σw(πi(st−w))
≤W ′ (na′(st−W∗+1:t)− na#(st−W∗+1:t))−W ∗ (na(st−W ′+1:t)− na′′(st−W ′+1:t))− 1[a′ > a]
+ ∑ i∈B max{W∗,W ′}∑ w=0 max a0∈A
σw(a0)− σw(πi(st−w))︸ ︷︷ ︸ gi
(a) ≤W ′ (na′(st−W∗+1:t)− na#(st−W∗+1:t))−W ∗ (na(st−W ′+1:t)− na′′(st−W ′+1:t))− 1[a′ > a] + K∑ i=1 g(i)
(b) ≤W ′ (na′(st−W∗+1:t)− na#(st−W∗+1:t))−W ∗ (na(st−W ′+1:t)− na′′(st−W ′+1:t))− 1[a′ > a] + L W∗,W ′ a′,a′′∑ i=1 g(i)
(c) <0. Thus, Equation (27) is proved. Therefore, K > LW ∗,W ′
a′,a′′ is a necessary condition for Q(W ∗, a′),
i.e., Equation (25).
In the above deriviation, the definitions of gi, gi, and σw are from Equation (7). (a) comes from the facts that {g(i)}ui=1 is a nondecreasing permutation of {gi} u−1 i=0 , gi ≥ 0, and |B| ≤ K. (b) comes from the assumption K ≤ LW ∗,W ′
a,a′′ and also g (i) ≥ 0. (c) comes from the definition in
Equation (6).

heading: F.6 POSSIBLE ACTION SET IN PARL AND COMPARISON

heading: F.6.1 CERTIFICATION
text: Proof of Theorem 4. According to the definition of possible action set, we only need to prove the contrary: for any a ∈ A \ AT (K), within poisoning size K, the poisoned policy cannot choose a: π̃P(st) 6= a. According to Equation (8), any a ∈ A \AT (K) satisfies∑
a′∈A max{na′(st)− na(st)−K + 1[a′ < a], 0} > K. (28)
Given poisoning size K, since each poisoning size can affect only one subpolicy, we know ña(st) ≤ na(st) +K where ña denotes to the poisoned aggregated action count. We suppose the attack could be successful, then for a′ < a, ña′(st) ≤ ña(st)− 1, and thus na′(st)− ña′(st) ≥ na′(st)−na(st)−K + 1. Similarly, for a′ > a, ã′(st) ≤ ña(st), and thus na′(st)−ña′(st) ≥ na′(st)−na(st)−K. Also, for any a′ 6= a after poisoning na′(st) − ña′(st) ≥ 0; otherwise deviating the difference subpolicies’ decisions’ from a′ to a is strictly no-worse. Given these facts, the amount of votes that need to be reduced is the LHS of Equation (28) which is larger than K. However, we only have K poisoning size, i.e.,K votes that can be reduced. As a result, our assumption that the attack could be successful is falsified and the poisoned policy cannot choose a.
Corollary 12 (Loose 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 t
AL(K) = { a ∈ A ∣∣∣ max a′∈A na′(st)− na(st) ≤ 2K − 1[a > arg max a′∈A na′(st)] } . (29)
Proof of Corollary 12. Again, we prove the contrary, for any a ∈ A\AL(K), within poisoning size K, the poisoned policy cannot choose a: π̃P(st) 6= a. According to Equation (29), let am = arg maxa′∈A na′(st), then any a ∈ A \AL(K) satisfies nam(st)− na(st) > 2K − 1[a > am]. After poisoning, we thus have nam(st)− na(st) > −1[a > am] =⇒ nam(st)− na(st) ≥ 1− 1[a > am] From the definition, a /∈ AL(K) so a 6= am. If am < a, nam(st) ≥ na(st); if am > a, nam(st) > na(st). In both cases, am has higher priority to be chosen than a, and thus the poisoned policy cannot choose a.

heading: F.6.2 COMPARISON
text: Theorem 13. Under the condition of Definition 5, suppose the aggregation protocol is PARL as defined in Definition 7, AT (K), AL(K) are defined according to Equations (8) and (29) accordingly, then
1. AT (K) ⊆ AL(K); and there are subpolicies {πi}u−1i=0 and state st such that AT (K) ( AL(K).
2. Given subpolicies {πi}u−1i=0 and state st, for any a ∈ AT (K), there exists a poisoned training set D̃ whose poisoning size |D D̃| ≤ K and some RL training mechanism, such that π̃P(st) = a where π̃P is the poisoned PARL policy trained on D̃.
Proof of Theorem 13. We prove the two arguments separately.
1. We first prove AT (K) ⊆ AL(K). For any a ∈ AT (K), let am = arg maxa′∈A na′(st), then∑ a′∈A max{na′(st)− na(st)−K + 1[a′ < a], 0} ≤ K
=⇒nam(st)− na(st)−K + 1[am < a] ≤ K =⇒nam(st)− na(st) ≤ 2K − 1[a > am]
where the last proposition is exactly the set selector of AL(K) so a ∈ AL(K). We then prove that AT (K) ( AL(K) can happen by construction. Suppose that there are three actions in the action space: A = {a1, a2, a3}. We construct subpolicies for current state st such that the aggregated action counts are
na1(st) = 10, na2(st) = 9, na3(st) = 1. Given poisoning size K = 5, we find that
na1(st)− na3(st) = 9 ≤ 10− 1[a3 ≥ a1] = 9 =⇒ a3 ∈ aL(K), (na1(st)− na3(st)−K + 1[a1 < a3]) + (na2(st)− na3(st)−K + 1[a2 < a3]) = 9 > K = 5 =⇒ a3 /∈ aT (K).
Therefore, AT (K) ( AL(K) for these subpolicies and state st.
2. We prove by construction. For any a ∈ AT (K), we construct the set of subpolicies to poison Ba ⊆ [u] such that |Ba| ≤ K, then describe the corresponding poisoned dataset D̃a, and finally prove that the poisoned policy π̃P a (st) = a.
For a ∈ AT (K), by definition (Equation (8)), we know∑ a′∈A max{na′(st)− na(st)−K + 1[a′ < a]︸ ︷︷ ︸ :=ta,a′ , 0} ≤ K. (30) We now define a set of actions Ca ⊆ A such that Ca = {a′ ∈ A | ta,a′ > 0}. According to this definition, a /∈ Ca since ta,a ≤ 0.
Fact F.1. For a ∈ AT (K) and any a′ ∈ A, na(st) +K − 1[a′ < a] ≥ 0.
Proof of Fact F.1. Suppose na(st) + K − 1[a′ < a] ≤ 0, then na(st) = K = 0 and a′ < a. Then∑ a′∈A max{na′(st)−na(st)−K+1[a′ < a], 0} ≥ ∑ a′∈A na′(st)−na(st)−K = ∑ a′∈A na′(st) = u > 0 which contradicts the requirement that the LHS of the above inequality should be ≤ K = 0.
Give Fact F.1, for any a′ ∈ Ca, na′(st) ≥ ta,a′ . Notice that na′(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 Baa′ to such subset: Baa′ ⊆ {i ∈ [u] | πi(st) = a′}, |Baa′ | = ta,a′ . Now define Baα: B a α = ⋃ a′∈Ca B a a′ . We construct B a β to be an arbitrary subset of those subpolicies whose prediction is not a and who are not in Baα, and limit the B a β’s cardinality: Baβ ⊆ {i ∈ [u] | πi(st) 6= a} \Baα, |Baβ | = min{K − |Baα|, u− na(st)− |Baα|}. Such Baβ can be selected, because:
• From definition,Baα ⊆ {i ∈ [u] | πi(st) 6= a}, where the cardinality of {i ∈ [u] | πi(st) 6= a} is u− na(st). So 0 ≤ u− na(st)− |Baα|. • Since
|Baα| ≤ ∑ a′∈Ca |Baa′ | = ∑ a′∈Ca ta,a′ = ∑ a′∈A,ta,a′>0 ta,a′ (∗) ≤ K,
K − |Baα| ≥ 0, and thus |Baβ | ≥ 0. Here (∗) is due to Equation (30). • The superset {i ∈ [u] | πi(st) 6= a} \ Baα has cardinality u − na(st) − |Baα| and |Baβ | ≤ u− na(st)− |Baα|.
To this point, we can define the set of subpolicies to poison: Ba := Baα ∪Baβ ,
and |Ba| = |Baα|+ |Baβ | ≤ K.
In a similar fashion as the attack construction in proof of Proposition 9, for each i ∈ Ba, we locate its corresponding partitioned dataset Di for training subpolicy πai . We inset one trajectory pai toDi such that our chosen learning algorithmM0 can train a subpolicy π̃ai =M0(Di∪{pai }) such that π̃ai (st) = a. For example, the trajectory could be p a i = {(st, a, s′,∞)} where s′ is an arbitrary state that guarantees pai is hashed to partition i; andM0 learns the action with maximum reward for the memorized nearest state. Then, the poisoned dataset
D̃a = ( ⋃ i∈Ba Di ∪ {pai } ) ∪  ⋃ i∈[u]\B′ Di  . Thus, D̃a is |D D̃a| = |Ba| ≤ K, i.e., the constructed attack’s poisoning size is within K. We now analyze the action prediction of the poisoned policy π̃P. For action a, after poisoning, ña(st) = na(st)+ |Ba| = na(st)+min{K,u−na(st)} = min{na(st)+K,u}. If ña(st) = u, then all subpolicies vote for a, apparently π̃P a (st) = a; otherwise, ña(st) = na(st) + K. In this case, for any action a′ ∈ Ca, since we at least choose subpolicies in Baa′ and change their action prediction to a, the aggregated action count after poisoning is ña′(st) ≤ na′(st)−|Baa′ | = na′(st)−ta,a′ = na′(st)−na′(st)+na(st)+K−1[a′ < a] = na(st)+K−1[a′ < a] = ña(st)− 1[a′ < a]. Thus, a′ has lower priority to be chosen than a. For any action a′ /∈ Ca and a′ 6= a, by the definition of Ca, ta,a′ = na′(st)−na(st)−K+1[a′ < a] ≤ 0. After poisoning, the vote of a′ does not increase, i.e., ña′(st) ≤ na′(st) ≤ na(st) +K −1[a′ < a] = ña(st)−1[a′ < a]. Thus, a′ also has lower priority to be chosen than a. In conclusion, we have π̃P a (st) = a.
To this point, for any a ∈ AT (K), we successfully construct the corresponding poisoned dataset D̃a within poisoning size K such that π̃P a (st) = a, thus concludes the proof.

heading: F.7 POSSIBLE ACTION SET IN TPARL
text: Proof of Theorem 5. For ease of notation, we let w = min{W, t + 1}, so w is the actual window size used at step t. We let t0 = t−w+ 1, i.e., t0 is the actual start time step for TPARL aggregation at our current step t. Now we can write chosen action at step t without poisoning as πT(st0:t).
We only need to prove the contrary: for any a ∈ A \ A(K), within poisoning size K, the poisoned policy cannot choose a: π̃T(st0:t) 6= a. According to Equation (9), for such a, there exists a′ 6= a such that
K∑ i=1 h (i) a′,a ≤ δa′,a = na′(st0:t)− na(st0:t)− 1[a < a ′]. (31)
Suppose there exists such poisoning attack that lets π̃T(st0:t) = a. This implies that for a ′, after poisoning, we have ña′(st0:t)− ña′(st0:t)− 1[a′ < a] < 0, (32) where ña is the aggregated action count after poisoning. Since the poisoning size is within K, it can affect at most K subpolicies. We let B ⊆ [u], |B| ≤ K to represent the affected subpolicy set. Therefore,
ña′(st0:t)− ña(st0:t)− 1[a′ < a] =na′(st0:t)− na(st0:t)− 1[a′ < a]︸ ︷︷ ︸
δa′,a
+(ña′(st0:t)− na′(st0:t))− (ña(st0:t)− na(st0:t))
=δa′,a + ∑ i∈B w−1∑ j=0 1[π̃i(st−j) = a ′, πi(st−j) 6= a′]− w−1∑ j=0 1[π̃i(st−j) 6= a′, πi(st−j) = a′]  − ∑ i∈B w−1∑ j=0 1[π̃i(st−j) = a, πi(st−j) 6= a]− w−1∑ j=0 1[π̃i(st−j) 6= a, πi(st−j) = a] 
≥δa′,a − ∑ i∈B w−1∑ j=0 1[π̃i(st−j) 6= a′, πi(st−j) = a′] + w−1∑ j=0 1[π̃i(st−j) = a, πi(st−j) 6= a]  ≥δa′,a −
∑ i∈B w−1∑ j=0 1[πi(st−j) = a ′] + w−1∑ j=0 1[πi(st−j) 6= a]  =δa′,a −
∑ i∈B w−1∑ j=0 1i,a′(st−j) + w − w−1∑ j=0 1i,a(st−j)  =δa′,a −
∑ i∈B hi,a′,a (a) ≥ δa′,a − |B|∑ i=1 h (i) a′,a (b) ≥ δa′,a − K∑ i=1 h (i) a′,a (c) ≥ 0.
This contradicts with Equation (32), and thus the assumption is falsified, i.e., there is no such poisoning attack that let π̃T(st0:t) = a. In the above equations, (a) is due to the fact that h (i) a′,a is a nonincreasing permutation of {hi,a′,a}u−1i=0 . (b) is due to the facts that |B| ≤ K and h (i) a′,a ≥ 0. (c) comes from Equation (31).

heading: F.8 HARDNESS FOR COMPUTING TIGHT POSSIBLE ACTION SET IN TPARL
text: Proof of Theorem 6. By Definition 5, the possible action set with minimum cardinality (called minimal possible action set hereinafter) is unique. Otherwise, suppose A and B are both minimal possible action set, but A 6= B, then A ∩ B is a 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 ∈ MINSET and thus whether any action a can be chosen by some poisoned policy π̃ whose poisoning size is within K. In other words, the problem of determining whether an action a can be chosen by some poisoned policy π̃ whose poisoning size is within K, denoted by ATTKACT, is polynomially equivalent to MINSET: MINSET ≡P ATTKACT. Now, we 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, 1972), denoted by SETCOVER, is a wellknown NP-complete problem and is defined as follows. The inputs are
1. a universal set of n elements: U = {u1, u2, · · · , un}; 2. a set of subsets of U : V = {V1, · · · , Vm}, Vi ⊆ U , 1 ≤ i ≤ m, ⋃m i=1 Vi = U ;
3. a positive number K ∈ R+.
The output is a boolean variable b, indicating that whether there exists a subsetW ⊆ V, |W| ≤ K, such that ∀ui ∈ U ,∃V ∈ W, ui ∈ V . Given an oracle to ATTKACT, we need to show SETCOVER can be solved in polynomial time, i.e., SETCOVER ≤P ATTKACT.
• If K ≥ n: We scan all sets Vi ∈ V . To being with, we have a record set S ← ∅, and an answer setW ← ∅. Whenever we encounter a set that contains a new element ui /∈ S, we put W ← W ∪ {Vj}, and record this element S ← S ∪ {ui}. After one scan pass, W covers all elements of U (since⋃m j=1 Vj = U), and |W| ≤ n ≤ K. Therefore,W is a valid set cover. Since we can always find
suchW , we can directly answer true.
• If K ≥ m: We can directly return V as a valid set cover, since ⋃m j=1 Vj = U and |V| ≤ m ≤ K. Thus, we
can answer true.
• If K < min{n,m}: This is the general case which we need to handle. Now we construct the ATTKACT(K) problem so that we can trigger its oracle to solve SETCOVER.
1. The poisoning size is K. 2. The action space A = U ∪ {b} ∪ Γ where Γ := {#1, . . . ,#m2n}. (|A| = n + 1 + m2n.)
The sorting of actions is u1 < u2 < · · · < un < b < #1 < · · · < #m2n. 3. The subpolicies are {πaj }mj=1 ∪ {πbi , πci,j | 1 ≤ i ≤ n, 1 ≤ j ≤ K − 1}, where πaj
corresponds to Vj ∈ V , and πbi , πci,j correspond to ui ∈ U . (Number of subpolicies u = m+Kn ≤ m+ n2.)
4. The current time step is t = nm, and the window size W = nm. 5. The input action is b, i.e., asking whether b can be chosen by some poisoned TPARL policy,
i.e., π̃T(s1:t) = b, if the poisoning size is within K.
Now, we construct the states at each step t (1 ≤ t ≤ nm) so that the subpolicies’ action predictions at these steps are as follows.
1. Count the appearing time of each ui in V , and denote it by ci: ci = ∑m j=1 1[ui ∈ Vj ]. For
each ui, select a Vj0 that contains ui, and in the corresponding π a j0 , assign m− ci + 1 steps to predict ui; for all other Vj that contains ui, in the corresponding πaj , assign one step to predict ui. 2. After this process, each πaj at least has one time step whose action prediction is ui for each ui ∈ Vj . Among all {πaj }mj=1 and all time steps 1 ≤ t ≤ nm, mn step-action cells are filled, and the remaining (m2n−mn) cells are filled by #l ∈ Γ sequentially. 3. For each πbi , arbitrarily select W −m time steps to assign action prediction as ui; and fill in other m time steps by remaining #l ∈ Γ sequentially. 4. For each πci,j , for all time steps, let the action prediction be ui.
As we can observe, the number of actions, the number of subpolicies, and the window size are all bounded by a polynomial of n and m. Therefore, such construction can be done in polynomial time.
We then show SETCOVER = true ⇐⇒ ∃K ′, b ∈ ATTKACT(K ′), 1 ≤ K ′ ≤ K.
– =⇒: Suppose the covering set is W ⊆ V , we denote K ′ to |W|, and construct the ATTKACT problem with poisoning size K ′ as described above. We can construct a poisoning strategy to let π̃T(s1:nm) = b, The poisoning strategy is to find out πaj for each Vj ∈ W , and to let them predict action b throughout all time steps: π̃aj (s ′ t) = b, 1 ≤ t′ ≤ nm.
After poisoning, the aggregated action count ñb(s1:nm) = |W| × nm = K ′nm. Since W covers every ui ∈ U , for each ui ∈ U there exists a set Vj 3 ui, whose corresponding π̃aj is poisoned to predict b. Thus, ñui(s1:nm) < nui(s1:nm) = m+ (W −m) +W × (K ′− 1) = WK ′ = K ′nm. For any #l ∈ Γ, ñ#l(s1:nm) ≤ n#l(s1:nm) = 1. In summary,
ñui(s1:nm) < K ′nm, ñb(s1:nm) = K ′nm, ñ#l(s1:nm) = 1. Thus, after TPARL aggregation, the poisoned policy π̃T(s1:nm) = b, and therefore b ∈ ATTKACT(K ′). – ⇐=: Suppose it isK ′ that let b ∈ ATTKACT(K ′), which implies that there exists such a poisoning attack within size K ′ that misleads the poisoned policy to b: π̃T(s1:nm) = b. Since the poisoning size is K ′, after poisoning the aggregated action count
ñb(s1:nm) ≤ K ′W = K ′nm. For each ui ∈ U , since nui(s1:nm) = m+ (W −m) +W × (K ′ − 1) = K ′nm, we always have
ñui(s1:nm) (∗) < ñb(s1:nm) ≤ nui(s1:nm), (33)
where (∗) is due to the condition of successful attack. We denote the set of poisoned subpolicies by Π (|Π| ≤ K ′). Therefore, Equation (33) implies that for each ui ∈ U , there exists at least one subpolicy
π′ui ∈ Π, π ′ ui ∈ {π a j | ui ∈ Vj} ∪ {πbi } ∪ {πci,j | 1 ≤ j ≤ K − 1} (34)
that is poisoned by the attack, otherwise the aggregated vote ñui cannot change. We partition Γ by Γa and Γbc, where
Γa = Γ ∩ {πaj }mj=1,Γb = Γ ∩ {πbi , πci,j | 1 ≤ i ≤ n, 1 ≤ j ≤ K − 1}.
We construct additional poisoning set Γa+ following this process: In the beginning, Γ a + ← ∅. For each ui ∈ U , if Γa ∩ {πaj | ui ∈ Vj} is not empty, skip. Otherwise, according to Equation (34), Γb ∩ {πbi , πci,j | 1 ≤ j ≤ K − 1} is not empty. In this case, we find an arbitrary covering set of ui, namely Vj0 3 ui, and put πaj0 into Γ a +. When the process terminates, we find that for each ui ∈ U , (Γa ∪ Γa+) ∩ {πaj | ui ∈ Vj} 6= ∅. (35) Following the mapping {πaj }mj=1 ←→ {Vj | 1 ≤ j ≤ m} = V , the subset (Γa ∪ Γa+) ⊆ {πaj }mj=1 can be mapped to (Wa∪Wa+) ⊆ V . From Equation (35), (Wa∪Wa+) is a valid set cover for U . We now study the cardinality of this set cover. From the process, we know that every Vj0 ∈ Wa+ corresponds to a different set in Γb. Thus, |Wa+| ≤ |Γb|, which implies that |Wa ∪Wa+| ≤ |Wa|+ |Wa+| ≤ |Γa|+ |Γb| = |Γ| ≤ K ′. To this point, we successfully construct a set cover within cardinally K ′ ≤ K that covers U , so SETCOVER = true.
Therefore, we can check whether SETCOVER = true by iterating K ′ from 1 to K (< min{n,m} iterations), constructing the ATTKACT(K ′) problem, and querying the oracle. The whole process can be done in polynomial time assumping O(1) computation time of the ATTKACT(K ′) oracle.
To this point, we have shown SETCOVER ≤P 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 to be assigned to each poisoned subpolicy. The decision of whether the poisoning is successful can be done in polynomial time and b ∈ 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 ≡P ATTKACT).

heading: F.9 POSSIBLE ACTION SET IN DPARL
text: Proof of Theorem 7. For ease of notation, we assume that Wmax ≤ t + 1, and otherwise we let Wmax ← t+ 1. We let t0 = max{t−Wmax + 1, 0} be the start time step of the maximum possible window.
We only need to prove the contrary: for any a ∈ A \ A(K), within poisoning size K, the poisoned policy cannot choose a: π̃D(st0:t) 6= a. We prove by contradiction: we assume that there exists such a poisoning attack within poisoning size K that lets π̃D(st0:t) = a. From the expression of A(K) (Equation (10)), a 6= at = πD(st0:t). Suppose the selected time window before the attack is W ′ (selected according to Equation (1) based on ∆Wt and na), and the selected time window after the attack is W̃ ′ (selected according to Equation (1) based on ∆̃Wt and ña).
• If W̃ ′ = W ′: Suppose we use the TPARL aggregation policy with window size W = W ′ instead of current DPARL aggregation policy, then we will have πT(st−W ′+1:t) = at and π̃T(st−W ′+1:t) = a. Thus, according to the definition of possible action set (Definition 5), a ∈ A(K) where A(K) is defined by Equation (9) in Theorem 5. This implies that a ∈ A(K) where A(K) is defined by Equation (10), which contradicts the assumption that a ∈ A \A(K).
• If W̃ ′ 6= W ′: According to the definition in Equation (10),
min 1≤W∗≤Wmax,W∗ 6=W ′,a′′ 6=at
LW ∗,W ′
a,a′′ > K.
We define a#t = arg maxa0 6=at ña0(st−W ′+1:t). Then, the above equation implies that
LW̃ ′,W ′
a,a#t > K
and thus LW̃ ′,W ′
a,a # t∑
i=1
g(i) +W ′(nW̃ ′ a − nW̃ ′ a# )− W̃ ′(nW ′ at − n W ′
a#t )− 1[a > at] < 0.
Since g(i) ≥ 0 by definition (Equation (7)), K∑ i=1 g(i) +W ′(nW̃ ′ a − nW̃ ′ a# )− W̃ ′(nW ′ at − n W ′ a#t )− 1[a > at] < 0, (36) where a# = arg maxa0 6=a′,a0∈A na0(st−W̃ ′+1:t) and n w a is a shorthand of na(st−w+1:t).
Following the derivation from Equation (27) to (a), we have K∑ i=1 g(i)+W ′(nW̃ ′ a −nW̃ ′ a# )−W̃ ′(nW ′ at −n W ′ a#t )−1[a > at] ≥W ′(ñW̃ ′ a −ñW̃ ′ a# )−W̃ ′(ñW ′ at −ñ W ′ a#t )−1[a > at]. Combined with Equation (36), W ′(ñW̃ ′ a − ñW̃ ′ a# )− W̃ ′(ñW ′ at − ñ W ′
a#t )− 1[a > at] < 0. (37)
On the other hand, the successful attack assumption, i.e., π̃D(st0:t) = a and πD(st0:t) = at, implies that
∆̃W̃ ′ t = ñW̃
′ a − ñW̃ ′
a(2) W̃ ′ > ñW
′ aW ′ − ñW ′ a (2)
W ′
W ′ = ∆̃W
′
t , (38)
where “>” is “≥” if a < at. In the above equation, a(2) = arg max
a0 6=a,a0∈A ñW̃
′
a0 , aW ′ = arg max a0∈A
ñW ′ a0 , a (2) W ′ = arg max
a0 6=aW ′ ,a0∈A ñW
′
a0 .
Intuitively, after poisoning, a(2) is the runner-up action at window W̃ ′, aW ′ is the action at window W ′, and a(2)W ′ is the runner-up action at window W
′. We rewrite Equation (38) to W ′(ñW̃ ′ a − ñW̃ ′ a(2)) ≥ W̃ ′(ñW ′ aW ′ − ñW ′ a (2)
W ′ ) + 1[a > at]. (39)
We have the following two observations:
1. ñW̃ ′ a − ñW̃ ′ a# ≥ ñ W̃ ′ a − ñW̃ ′ a(2) , since a is the top action and a(2) is the runner-up action and their
margin should be the smallest. 2. ñW ′
aW ′ − ñW ′ a (2) W ′ ≥ ñW ′at − ñ W ′ a#t , because 1) if at = aW ′ , LHS equals to RHS; 2) if at 6= aW ′ ,
LHS ≥ 0 and RHS ≤ 0.
Plugging these two observations to two sides of Equation (39), we get W ′(ñW̃ ′ a − ñW̃ ′ a# ) ≥ W̃ ′(ñW ′ at − ñ W ′
a#t ) + 1[a > at]. (40)
This contradicts with Equation (37).
Since in both cases, we find contradictions. Now we can conclude that for any a ∈ A\A(K), within poisoning size K, the poisoned policy cannot choose a: π̃D(st0:t) 6= a.

heading: G ADDITIONAL EXPERIMENTAL DETAILS

heading: G.1 DETAILS OF THE OFFLINE RL ALGORITHMS AND IMPLEMENTATIONS
text: We experimented with three offline RL algorithms: DQN (Mnih et al., 2013), QR-DQN (Dabney et al., 2018), and C51 (Bellemare et al., 2017). 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.
Algorithm Ideas. The core of Q-learning (Watkins & Dayan, 1992) is the Bellman optimality equation (Bellman, 1966)
Q?(s, a) = ER(s, a) + γEs′∼P max a′∈A Q? (s′, a′) , (41)
where a parameterized Qθ is adopted to approximate the optimal Q? and iteratively improved. In DQN (Mnih et al., 2013) 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:
Z?(s, a) D = r + γZ? (s′, argmaxa′∈AQ ? (s′, a′)) where r ∼ R(s, a), s′ ∼ P (· | s, a). (42)
Concretely, QR-DQN (Dabney et al., 2018) approximates the density D? with a uniform mixture of K Dirac delta functions, while C51 (Bellemare et al., 2017) approximates the density using a categorical distribution over a set of anchor points.
Implementation Details. For training the subpolicies using offline RL training algorithms, we use the code base of Agarwal et al. (2020). The configuration files containing the detailed hyperparameters can be found at their public repository https://github.com/google-research/ batch_rl/tree/master/batch_rl/fixed_replay/configs. 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.

heading: G.2 CONCRETE EXPERIMENTAL PROCEDURES
text: We conduct experiments on two Atari 2600 games Freeway and Breakout from OpenAI Gym (Brockman et al., 2016) following Section 3. Concretely, in the training stage, we first partition the training dataset into u partitions (u = 30 or 50) by using the hash function h(τ) as the sum of all pixel values of all frames in the trajectory τ . We then train the subpolicies on the partitions with offline RL training algorithmM0 ∈ {DQN (Mnih et al., 2013), QR-DQN (Dabney et al., 2018), C51 (Bellemare et al., 2017)}. The detailed description of the algorithms can be found in Appendix G.1. In the aggregation stage, we apply the three proposed aggregation protocols (PARL, TPARL, and DPARL) on the trained u subpolicies and derive the aggregated policies πP, πT, and πD 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 and report results averaged over 20 runs; for the cumulative reward certification, we adopt the trajectory length H = 400 for evaluating Freeway and H = 75 for Breakout.

heading: H ADDITIONAL EVALUATION RESULTS AND DISCUSSIONS

heading: H.1 BENIGN EMPIRICAL PERFORMANCE
text: We present the benign empirical cumulative rewards of the three aggregation protocols (PARL, TPARL, and DPARL) applied on subpolicies trained using three offline RL algorithms (DQN, QRDQN, 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 and report results averaged over 20 runs. On the RL algorithm level, we see that QR-DQN achieves the highest score in almost all cases. On the aggregation protocol level, temporal aggregation enhances the performance on Freeway while dampens the performance on Breakout. We particularly note that the results obtained by using temporal aggregation (TPARL and DPARL) gives significantly smaller variance compared
to the single-step aggregation PARL, especially in Breakout. This implies that temporal aggregation can help stabilize the policy. On the partition number level, a larger partition number can give slightly better results. On the game level, Freeway is simpler and more stable than Breakout.

heading: H.2 COMPARISON OF COPA WITH STANDARD TRAINING
text: 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).
In Figure 3, 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 as 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, as well as large variance for the achieved reward at the last epoch. Thus, we cannot draw conclusions w.r.t. the convergence. Given more time and computational resources, we would be able to run for more epochs and draw more informative conclusions.
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 of our obtained policies is lower, our policies are much more stable with significantly lower variance than the standard training.

heading: H.3 MORE ANALYTICAL STATISTICS FOR DPARL
text: 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 average 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 7. Specifically, we compare the running time of DPARL (Wmax = 5) applied on u = 30 or 50 subpolicies trained using offline RL algorithm DQN with the normal testing which tests the runtime of a single trained DQN policy without using our framework. As we have shown in the remark of Theorem 3 in Section 3.3, the time complexity of DPARL isO ( W 2max|A|2u+Wmax|A|2u log u ) . In Table 7, we also see that the runtime of DPARL scales roughly quasilinearly with the number of subpolicies u, and quadratically with the action set size |A|, which is 3 for Freeway and 4 for Breakout.

heading: H.4 MAXIMUM TOLERABLE POISONING THRESHOLD VS. TOTAL TRAJECTORY NUMBER
text: We provide the total number of trajectories in the offline dataset used for training the games Freeway and Breakout below, as 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 trajectories in the entire offline dataset is 121,892, and the ratio (maxKt / # total trajectories) is 0.0002; for Breakout, the number is 209,049, and the ratio is 0.0001. We emphasize that, as shown in previous 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 our results.

heading: H.5 COMPARISON OF FREEWAY AND BREAKOUT
text: Freeway and Breakout are two typical types of games with distinctive game properties. Freeway is a 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 a 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 catch and bounce the ball at an appropriate angle, which requires a frequent switch of the paddle moving direction.
Given the properties of the games, we note that in Freeway, adjacent time steps may share consistent action selections, which is not necessarily true in the game Breakout. Thus, it 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.
Bottleneck states in Breakout vs Freeway. 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, e.g., when the ball is flying towards the paddle and when it is bounced back. An example of the bottleneck state 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 is 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.

heading: H.6 FULL RESULTS OF ROBUSTNESS CERTIFICATION FOR PER-STATE ACTION STABILITY
text: As a complete set of results for per-state action certification apart from Figure 1 in Section 4.1, we present the entire cumulative histogram of tolerable poisoning thresholds in Figure 4 and the average tolerable poisoning thresholds in Table 8. The definitions of the two metrcis can be found in Section 4.1. Basically, the conclusions in terms of the comparisons on the RL algorithm level, the aggregation protocol level, the partition number level, and the game level are all similar to that derived in Section 4.1.

heading: H.7 FULL RESULTS OF ROBUSTNESS CERTIFICATION FOR CUMULATIVE REWARD BOUND
text: In addition to the evaluation results provided in Figure 2 in section 4.2, we provide a more comprehensive set of evaluation results with more settings of trajectory length H here in Figure 5. We draw similar conclusions as discussed in Section 4.2.

heading: I A BROADER DISCUSSION ON RELATED WORK

heading: I.1 POISONING ATTACKS IN RL
text: Below, we provide a brief discussion on the related works on policy poisoning and reward poisoning (Ma et al., 2019; Sun et al., 2021; Huang & Zhu, 2019).
Ma et al. (2019) and Huang & Zhu (2019) study reward poisoning where the attacker can modify the rewards in an offline dataset or the reward signals during the online interaction. The attacker’s goal is to force learning a particular target policy, or minimize the agent’s reward in the original task. Under this framework, Ma et al. (2019) considers two victim learners with specific assumptions on the learner structure and develops attacks for them, while Huang & Zhu (2019) provides a theoretical analysis on the conditions for successful attacks against a Q-learning agent. In comparison to only reward poisoning in Ma et al. (2019) and Huang et al. (2017), Sun et al. (2021) focuses on general policy poisoning attacks for policy gradient learners in the online RL setting by using the vulnerability-awareness metric to decide when to poison, and the adversarial critic to guide the poisoning. Sun et al. (2021) achieve successful poisoning against policy-based agents in various complex environments in 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.

heading: I.2 EMPIRICALLY ROBUST RL
text: Robust RL against Evasion Attacks. We briefly review several categories of RL methods that demonstrate empirical robustness against evasion attacks.
Randomization methods (Tobin et al., 2017; Akkaya et al., 2019) were first proposed to encourage exploration. This type of method was later systematically studied for its potential to improve model robustness. NoisyNet (Fortunato et al., 2017) adds parametric noise to the network’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.
Under the adversarial training framework, Kos & Song (2017) 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. RSDQN (Fischer et al., 2019) is an imitation learning based approach that trains a robust student-DQN in parallel with a standard DQN in order to incorporate the constrains such as SOTA adversarial defenses (Madry et al., 2017; Mirman et al., 2018).
SA-DQN (Zhang 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 incorporates the upper bound of the perturbed loss, computed using certified bounds from verification algorithms. CARRL (Everett et al., 2021) aims to compute the lower bounds of action-values under potential perturbation and select actions according to the worst-case bound, but it relies on 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. Banihashem et al. (2021) considers the threat model of reward poisoning attacks proposed by Ma et al. (2019); Rakhsha et al. (2020); Zhang et al. (2020b), where the attacker aims to force learning a target policy while minimizing the cost of reward manipulation. As shown in Ma et al. (2019); Rakhsha et al. (2020); Zhang et al. (2020b), this optimization problem is feasible and always has a unique optimal solution. Leveraging this property, Banihashem et al. (2021) formulates the defense task as another optimization problem which aims to optimize the agent’s worst case performance among the set of plausible candidates of the true reward function. They specifically consider two settings regarding the agent’s knowledge of the attack parameter, and provide lower bounds on the performance of the defense policy. In contrast to Banihashem et al. (2021) 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 applicable to any potential attack. Our robustness is derived from the aggregation over both sub-policy 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 as the provable guarantee / certification criteria.

heading: I.3 ROBUSTNESS CERTIFICATION FOR RL
text: Wu et al. (2021) 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). Concretely, they apply per-state smoothing to achieve the certification for per-state action stability, as well as trajectory smoothing to obtain the certification for cumulative reward. Notably, Wu et al. (2021) propose an adaptive tree search algorithm to explore all possible trajectories and thus derive 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 aggregation 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. (2021).

Review summaries:
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.

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.  

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. 

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.