Multi-level Certified Defense Against Poisoning Attacks in Offline Reinforcement Learning

We thank the reviewer for their assessment of our paper.

1. Yes, it is true that an attacker could manipulate the trajectories in a manner that does not influence the resultant policies. However, for certifications, we are concerned about quantifying the impact of a worst-case perturbation to the trajectory set.

   As such, when we evaluate against $r$, we are not measuring the effectiveness against any empirical attack of size $r$, but rather calculating the guaranteed resistance of the certified defence to the worst possible perturbation of size $r$.

   In the experiments, we adhere to standard procedures in certified robustness papers by providing a theoretical certification calculated based on training on a clean dataset $D$. The certification of any given size $r$ (transition or trajectory-level) is calculated theoretically measuring the resistance to the worst possible poisoning attack bounded by $r$.

   While this is discussed in Section 3.2, we have added some additional language here as in lines 175-179, and within the experimental section lines 377-379 to help further clarify this point.

2. Regarding the concern about backdoor attacks, we would like to clarify that backdoor attacks were not explicitly discussed because they can be considered as a subset of poisoning attacks (i.e., training-time attacks) with a specific attack objective. They operate under the same threat model as we considered in the paper (Sec 3.1)---a bounded number/fraction of training data can be corrupted. This threat model is applied in the referenced papers [2] Section 5.2, [3] Section 3.1, and [4] Section 3.4) as well.

   Thus, our proposed certified defense is applicable to backdoor attacks, by offering the same action-level robustness (e.g., ensuring actions remain unchanged in triggered states) and policy-level robustness (e.g., guaranteeing that triggering the backdoor function does not degrade the agent's performance below the certified lower bound) for bounded corruptions in the training dataset.

We again thank the reviewer for their valuable feedback.

We thank the reviewer for their assessment of our paper.

1. DP is employed through the SGM or DP-FEDAVG mechanisms and used as the basis for our guarantees, as noted in lines 236-241 and detailed in Appendix A.2. This includes our discussion about the algorithms for achieving transition- and trajectory-level guarantees respectively and provides the pseudo-code (Algorithm 1 and Algorithm 2) for implementation details. To help clarify this, we have added additional discussion on this in lines 236-241.

2. Relative to Wu et al., 2022,

   • As for the first concern, Wu et al.'s robustness criteria can only be applied to deterministic environments with discrete actions, while our new robustness criteria extend applicability to stochastic environments and those with continuous action spaces.

     Moreover, the proposed policy-level robustness is novel and different from the ''Lower Bound of Cumulative Reward" in Wu et al. As discussed in lines 118-124 and 506-520, the lower bound in Wu et al. is defined as the minimum cumulative reward of a set of specific trajectories. Instead, the policy-level robustness (lines 180-187) is the lower bound of the policy's primary metric---expected cumulative reward, measuring the overall performance over all possible trajectories induced by the given policy.

     Finally, Wu et al's criteria only covers trajectory-level poisoning, while ours covers both trajectory- and transition-level. Therefore, we highlight the multi-level robustness.

   • Regarding the second concern, the limitations of Wu et al. are due to the Deep Partition Aggregation and tree-search methods they used, which essentially exhaustively iterate through all possible trajectories in a deterministic and discrete setting to find the minimum cumulative reward, as detailed in lines 118-124. Instead, our approach is based on differential privacy (Sec 4.2) which has no such limitation.

3. Regarding the variants of PARL, we would like to note that the action-level robustness of PARL, TPARL, and DPARL are effectively interchangeable (less than 0.05 gap in stability ratio for a given radius) as reported in their paper Sec 5.1, Figure 1 (PARL actually achieves slightly better performance in Breakout than the others). We conducted a direct comparison with PARL on action-level under the same experiment setting (Freeway/Breakout using DQN/C51 with 50 partitions) and achieved significant improvement as shown in Figure 1. Considering the similar performance across the variants in Wu et al., we believe it is evident that our method outperforms all variants. We have added more discussion in lines 447-450.

   For policy-level robustness, comparisons are conducted implicitly due to differences in robustness criteria. The advantages of our method as discussed in lines 506-520 are applicable to all the variants in Wu et al.

4. In responding to the minors

   • It would be much appreciated if the mathematical rigor and typos could be specified and we will fix that in the revision.
   • The $Q_{\tilde{\pi}_i}$ represents the standard definition of action-value in RL as $\mathbb{E}_{\tilde{\pi}_i} [ \sum_{t=0}^{H-1} \gamma^t r_{t+1} \mid s_0 = s_t, a_0 = a_l]$. We have added details relating to this point in line 316.
   • We have clarified the SimuEM method more in lines 364-373 and detailed in Appendix A.5.
   • The domain of $\mathcal{K}$ consists of a set of parameters as outlined in Definition 3.5. For a given value of $\alpha$ (or $\delta$), the corresponding $\epsilon$ can be calculated as detailed in Appendix A.2. The binary search searches through a given range of $\alpha$ (or $\delta$) with the corresponding calculated $\epsilon$ to identify the parameter pairs that yield the largest $r$ subject to Eq 13. We have clarified it more in lines 364-373 and detailed in Appendix A.5.

5. For the choice of DP mechanisms, we selected ADP as it is the basic and widely used format in DP research, and most DP mechanisms provide privacy bound in Eq 15, enabling the wide applicability of our approach. RDP is chosen because of its tighter privacy quantification through sequential function composition, making it popular in deep learning contexts (lines 770-773). We have clarified it more in lines 766-775.

   More advanced DP mechanisms are applicable to the defense through our certification framework as discussed in lines 211-221. For instance, the method in Gopi et al. offers precise privacy loss computation in DP-SGD, which could strengthen our transition-level algorithm. We have added additional discussion on this in lines 861-867.

6. As discussed, ADP is not as suitable as RDP in managing iterative function composition within deep networks (lines 506-507 and 770-773). Therefore, a tighter accounting of privacy leads to more precise bounds and stronger robustness certification.

We again thank the reviewer for their valuable feedback.

We thank the reviewer for their assessment of our paper.

1. Regarding the optimality of our proposed certified defense, we would like to note that the optimality of our certification relies on the optimality of the DP mechanisms. Research efforts [1,2,3] focusing on optimality in DP could serve as valuable references, and integrating these methods for optimal certification presents an interesting direction for future work. However, we also want to address that the focus of our work is providing a general framework for leveraging DP in certified defenses of offline RL, which enables the application and optimal analysis of more advanced DP mechanisms in the future. We have added additional discussion of this in lines 861-867.

2. As for the attacker's power, we believe the strength of this threat model is equivalent to the assumptions of white-box access in traditional adversarial ML research. In offline RL, a set of trajectories may not be collected immediately by the system as discussed in lines 97-105, 152-157 --- it may be collected in advance, stored, and eventually transferred to the RL learner, which introduces more opportunities for an attacker to compromise the training dataset.

3. For the concern on practical attacks, we emphasize that the current evaluation follows from traditional certification research, where the model is trained on a clean dataset and the certification gives us a measure of what will happen under the worst possible attack. Empirical attacks confined within the radius $\mathcal{B}(D,r)$ will not result in an impact that is larger than the certified bound.

4. We have added a discussion of the application of DP to RL in lines 791-795.

5. We have added the legends to the figures.

6. We would like to give an acronym for our Multi-level Certified Defence as MuCD, and have updated it in the paper.

We greatly value your insights and feedback.

[1] Q. Geng and P. Viswanath, "The optimal mechanism in differential privacy," 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, 2014, pp. 2371-2375, doi: 10.1109/ISIT.2014.6875258. keywords: {Privacy;Probability distribution;Noise;Data privacy;Laplace equations;Probability density function;Databases}

[2] Q. Geng and P. Viswanath, "The Optimal Noise-Adding Mechanism in Differential Privacy," in IEEE Transactions on Information Theory, vol. 62, no. 2, pp. 925-951, Feb. 2016, doi: 10.1109/TIT.2015.2504967. keywords: {Privacy;Data privacy;Sensitivity;Databases;Laplace equations;Probability distribution;Context;Data privacy;randomized algorithm;Data privacy;randomized algorithm}

[3] Murtagh, Jack, and Salil Vadhan. "The complexity of computing the optimal composition of differential privacy." In Theory of Cryptography Conference, pp. 157-175. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015.

We thank the reviewer for their assessment of our paper.

• With regard to the results in Table 1, we would like to clarify that a fair comparison between our method and COPA should be conducted under a noise level that yields a similar performance (Avg. Cumulative Reward) in a benign environment as discussed in lines 447-451, specifically this corresponds to a noise level of $2$ in Freeway and $1.5$ in Breakout. When the average cumulative reward is controlled for, our technique significantly improves upon the reference cases, demonstrating the utility of our approach. Additionally, Figure 1 provides a more comprehensive comparison with COPA by presenting the full distribution of radii, rather than the mean values shown in Table 1, thereby offering a clearer illustration of the improvements achieved by our method. We have added more clarification to this part in lines 449-452.

• Regarding the concern about training multiple policies, we acknowledge that this requirement introduces some overhead compared to standard training processes. However, our randomized training process can be executed on a subset of the dataset $D_{sub} \subseteq D$, which enhances efficiency while still ensuring certification for $D$, as indicated in lines 234-235 and further detailed in Appendix A.2.

• Our threat model follows from Kumar et. al., which we believe is indicative of potential risks against ML. While we do not have examples of these attacks being deployed in the wild, we believe that security by obscurity is not a viable defensive strategy for those deploying RL. As such, our intent in this work is to elucidate how the mechanisms of certification can be extended to RL, in order to guard against viable threats. The practice of the attack could be conducted in a manner as we discussed in lines 152-157, 162-166.

Once again, we appreciate your valuable insights and feedback.