Tree-based Action-Manipulation Attack Against Continuous Reinforcement Learning with Provably Efficient Support

[1] Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning. NIPS 2021.

[2] Spatiotemporally constrained action space attacks on deep reinforcement learning agents. AAAI 2020.

[3] Vulnerability-aware poisoning mechanism for online rl with unknown dynamics. ICLR 2021.

Thanks for you feedback. I will response to the questions you mentioned.

Question 1: As stated above, one of my main concerns is the scalability of the algorithm as the numerical experiments were only shown for two extremely simple environments. Could the authors discuss the computational runtime for such the algorithm? It seemed to me that constructing the binary tree for environments which higher dimensional state spaces/action spaces would be prohibitively expensive. Furthermore, computation aside, the results would be more convincing and much stronger if the authors could show similar results on a much more conventional benchmark, like the MuJoCo environments.

1.computational runtime

The computational time complexity of the LCBT algorithm primarily emanates from two aspects:

(1) After each round, the attacker needs to update the corresponding $L$ and $B$ values for each node of every tree, and the complexity of this step is related to the number of nodes in the tree. Specifically, assuming that in the k-th episode, after completion, the attacker updates each node of H trees, according to the proof in Appendix F.1, the upper bound on the number of nodes in a tree is $O(k^E)$, where $E=\log_{2\rho^{-2}}2<1$. Therefore, for the total K episodes, the time complexity of this part is $O(K\cdot H\cdot K^E)$.

(2) When the attacker launches an attack, it is necessary to traverse from the root node to the leaf node (the WorTraverse function), and the complexity of this step is related to the depth of the tree. By employing a proof method akin to that in Appendix F.1, we can ascertain an upper bound for the depth of the tree as $O(\log_{\rho^{-2}}k)$ in episode $k$. Making an extreme assumption that the attacker launches an attack at every step, the time complexity for this part over the total K episodes is $O(K\cdot H \cdot \log_{\rho^{-2}}K)$.

In summary, the overall computational time complexity is given by: $O(H\cdot K^{1+E}+H\cdot K \cdot \log_{\rho^{-2}}K)$.

2.More conventional benchmark

We conducted an additional experiment in a five-dimensional space, the environmental setup of which is detailed in Environment 3 within Appendix A. The corresponding experimental outcomes are presented in Figure 7 of Appendix G.

Question 2: The results shown are also lacking comparison with existing threat models, even in terms of white-box attacks, such as the work by Sun et al. 2020.

In the above table, we conducted a comparative analysis of existing literature concerning attack methodologies centered on action manipulation. Notably, our comparison included the metric "The adversary's requisition for neural networks or gradient computations during attack," setting it as one of the distinctions between our approach and other studies. While existing works typically implement attacks from the neural network perspective in continuous action spaces, we consider the neural network as a black box, constructing attacks solely from the theoretical framework of reinforcement learning itself. This distinction forms a key aspect of our current work in contrast to others in the field. Hence, our work did not directly compare with other studies, such as [3], in the experimental setup.

Question 3: Could the authors elaborate why action space manipulation is more challenging than reward/state manipulation as this seem to be the core motivation for action space attacks over other forms of attack?

In the context of action-manipulation attacks, the fundamental factor influencing the intelligent agent lies in the attacker's manipulation of actions, thereby impacting rewards and consequently leading to the potential misguidance of the intelligent agent. Therefore, the action-manipulation attack method can be viewed as indirectly influencing the training of the intelligent agent by altering rewards. In contrast to the direct manipulation of observations, rewards, or the environment, action-manipulation represents a less direct approach. Additionally, a salient aspect of action-manipulation attacks is the constrained operational domain available to attackers, limited to the innate action space of the intelligent agent. In contrast, adopting reward manipulation allows attackers to modify rewards to values lower than those associated with the worst actions, presenting a more conspicuous avenue for manipulation.

Additionally, in black-box conditions, the method of manipulating rewards often only requires providing a minimal reward value during the attack, whereas finding an approximate worst-case action in a specific state is not a straightforward task.

Comment 1.

1. runtime

We reran the experiments for the LCBT attack corresponding to Environment 3, recording the time taken to execute the attack algorithm and the total time. The results are presented in the table below, wherein the "percentage" represents the ratio of the time taken to execute the attack algorithm up to that point compared to the total time.

Additionally, we included a figure (Figure 8) in Appendix G displaying the variation of the "percentage" metric with respect to the number of steps.

2. scalability

Here, we shall begin by conducting a theoretical analysis of the circumstances surrounding the method proposed by us in high-dimensional settings. One obvious point is that our method requires partitioning of the action and state spaces. With higher dimensions in the action space, even if we use binary tree partitioning, the sufficiency of partitioning will still be lower than in lower dimensions with the same number of partitions. This means that the LCBT algorithm converges slower towards the worst action, resulting in a higher level of non-stationarity in the environment and a larger D-Regret. According to Theorem 2, this also leads to higher attack cost.

Additionally, in the new experiment, the LCBT algorithm demonstrates commendable performance. Hence, in practical terms, factors influencing the efficacy of the LCBT algorithm encompass not only its intrinsic parameters such as $\nu_1$, $\rho$, $d_s$ (For instance, the settings of $\nu_1$ and $\rho$ can influence the speed of tree node expansion), but also encompass the environment and the algorithms employed by the agent.

3. completeness

We have included the following table in Appendix G.

The similarity between the original target policy and attacked policy in environment 3. Using a similar method as in Table 2, we select the attacked policies for $8\cdot 10^{5}$ steps and match their similarity with the original target policy. In this experiment, we set the similarity radius $r_a=0.497$, which is consistent with the training phase mentioned in the paper. Then, in the testing phase, we calculated the percentage of target actions executed by the attacked strategy within $1\cdot 10^5$ steps.

Comment 3.

For this matter, tampering with actions inevitably affects subsequent states; however, the extent of this influence might be less significant than directly altering the state itself. Additionally, considering action manipulation solely as an existing means of attack, it warrants further research and exploration. Lastly, concerning the issue you raised, we will also contemplate refining our presentation in the paper.

Thanks for your feedback. I will response to the weaknesses and questions you mentioned.

Weakness 1: The paper's efficacy could be improved through a more thorough examination of prior research in the realm of adversarial attacks on reinforcement learning. While the paper briefly references previous work, a more detailed comparison with existing attack techniques on continuous action spaces and their inherent limitations would serve to underscore the novelty and merits of the proposed methods.

In the above table, we conducted a comparative analysis of existing literature concerning attack methodologies centered on action manipulation. Notably, our comparison included the metric "The adversary's requisition for neural networks or gradient computations during attack," setting it as one of the distinctions between our approach and other studies. While existing works typically implement attacks from the neural network perspective in continuous action spaces, we consider the neural network as a black box, constructing attacks solely from the theoretical framework of reinforcement learning itself. This distinction forms a key aspect of our current work in contrast to others in the field.

Additionally, regarding the algorithm LCB-H[1] in discrete environments, we conducted a more detailed comparison in Appendix H. This examination primarily focuses on exploring the fundamental reasons for the discrepancies between the two in terms of attack cost.

Weakness 2: Although the paper introduces inventive attack methodologies, the potential complexity of these methods could pose practical challenges for their implementation. Specifically, it would be beneficial to provide an in-depth analysis of the computational complexity associated with the oracle and tree-based attacks.

Regarding the oracle attack, the adversary is already cognizant of the worst action, thereby enabling a direct manipulation replacement during the attack. At any given step of launching the attack, the time complexity is $O(1)$, and for the overall $K$ episodes, the computational time complexity amounts to $O(|\tau|)$.

The computational time complexity of the LCBT algorithm primarily emanates from two aspects:

(1) After each round, the attacker needs to update the corresponding $L$ and $B$ values for each node of every tree, and the complexity of this step is related to the number of nodes in the tree. Specifically, assuming that in the k-th episode, after completion, the attacker updates each node of H trees, according to the proof in Appendix F.1, the upper bound on the number of nodes in a tree is $O(k^E)$, where $E=\log_{2\rho^{-2}}2<1$. Therefore, for the total K episodes, the time complexity of this part is $O(K\cdot H\cdot K^E)$.

(2) When the attacker launches an attack, it is necessary to traverse from the root node to the leaf node (the WorTraverse function), and the complexity of this step is related to the depth of the tree. By employing a proof method akin to that in Appendix F.1, we can ascertain an upper bound for the depth of the tree as $O(\log_{\rho^{-2}}k)$ in episode $k$. Making an extreme assumption that the attacker launches an attack at every step, the time complexity for this part over the total K episodes is $O(K\cdot H \cdot \log_{\rho^{-2}}K)$.

In summary, the overall computational time complexity is given by: $O(H\cdot K^{1+E}+H\cdot K \cdot \log_{\rho^{-2}}K)$.

Question 1: Where can we get the target policy? How to specify a target policy in a complex task?

The essence of a policy lies in mapping states to actions. Therefore, when configuring the target policy, attackers can partition the states into sub-intervals according to their objectives. Each sub-interval corresponds to a target action, or attackers can choose to set target actions only for certain states while leaving the rest unaffected by attacks. In our experiments, we prefer to use a stricter target policy where each state has a corresponding target action. This allows us to evaluate the effectiveness of our algorithm. To achieve this, we introduce additional constraints in the original environment. For instance, in environment 2, we provide a negative reward when the distance between the car and the target point < 1. By training a supplementary model with these extra constraints, we obtain an additional model that represents the attacker's target policy.

Question 2: Could the authors provide more experiments on complex tasks?

We conducted an additional experiment in a five-dimensional space, the environmental setup of which is detailed in Environment 3 within Appendix A. The corresponding experimental outcomes are presented in Figure 7 of Appendix G.

[1] Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning. NIPS 2021.

[2] Spatiotemporally constrained action space attacks on deep reinforcement learning agents. AAAI 2020.

[3] Vulnerability-aware poisoning mechanism for online rl with unknown dynamics. ICLR 2021.

Thanks for your feedback. I will response to the weaknesses and questions you mentioned.

Weaknesses

There are no comparisons with existing RL attack methods, so it's hard to gauge the empirical effectiveness of this approach.

[1] Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning. NIPS 2021.

[2] Spatiotemporally constrained action space attacks on deep reinforcement learning agents. AAAI 2020.

[3] Vulnerability-aware poisoning mechanism for online rl with unknown dynamics. ICLR 2021.

In the above table, we conducted a comparative analysis of existing literature concerning attack methodologies centered on action manipulation. Notably, our comparison included the metric "The adversary's requisition for neural networks or gradient computations during attack," setting it as one of the distinctions between our approach and other studies. While existing works typically implement attacks from the neural network perspective in continuous action spaces, we consider the neural network as a black box, constructing attacks solely from the theoretical framework of reinforcement learning itself. This distinction forms a key aspect of our current work in contrast to others in the field. Hence, our work did not directly compare with other studies, such as [3], in the experimental setup.

"The environments considered are extremely low-dimensional, even by the standards of formal methods research" and "There are only two environments".

We conducted an additional experiment in a five-dimensional space, the environmental setup of which is detailed in Environment 3 within Appendix A. The corresponding experimental outcomes are presented in Figure 7 of Appendix G.

Question: Does the analysis hold for stochastic policies? I was a bit unclear on this since the definitions of $Q$ and $V$ both use the notation introduced for deterministic policies. Moreover it seems to me that some parts of the proofs rely on the assumption that all policies are deterministic (including the exploration policies of the RL algorithm), but most RL algorithms do not work by evaluating deterministic policies.

In fact, in this paper, we only require the target policy, i.e., $\pi^{\dagger}$ is a deterministic policy. There is no specific requirement for the reinforcement learning algorithm used by the agent. In addition, we also discuss the impact of the reinforcement learning algorithm (D-Regret) used by the agent on our attack cost in the remark of Theorem 2. Also, we carry out experiments to apply the LCBT attack against DDPG, PPO, and TD3. Furthermore, in the proof section, a portion of the proof statements at the beginning of Appendix C (Proof of Theorem 1) could be refined without affecting the subsequent proof (We have performed updates in Appendix C, specifically focusing on the derivation of $\overline{V}^o_1(s^k_1) - \overline{V}^{\pi^k}_1(s^k_1)$).

Thanks for your feedback. I will response to the questions you mentioned.

Question 1: What is the method of dividing the continuous subset of the action space when new leaves are generated?

When partitioning a node, it is essential to ensure that the action space corresponding to the child nodes satisfies the condition $diam_a(\mathcal{P}_{D,I})\leq\nu_1\rho^D$, where $D$ represents the depth of the child nodes. In practical applications, the action space is multidimensional, allowing for the configuration of a dimension for each layer in a binary tree. Through iterative correspondence, when a node at a certain layer is partitioned to generate its child nodes, the action space can be halved along the corresponding dimension.

Question 2: Can the method be directly used in high-dimensional action space case?

Here, we shall begin by conducting a theoretical analysis of the circumstances surrounding the method proposed by us in high-dimensional settings. One obvious point is that our method requires partitioning of the action and state spaces. With higher dimensions in the action space, even if we use binary tree partitioning, the sufficiency of partitioning will still be lower than in lower dimensions with the same number of partitions. This means that the LCBT algorithm converges slower towards the worst action, resulting in a higher level of non-stationarity in the environment and a larger D-Regret. According to Theorem 2, this also leads to higher attack cost.

Additionally, we have introduced a new experiment in a 5-dimensional space, as described in Environment 3 in Appendix A. The corresponding experimental outcomes are presented in Figure 7 of Appendix G. Remarkably, under the conditions of a 5-dimensional space, the LCBT algorithm demonstrates commendable performance. Hence, in practical terms, factors influencing the efficacy of the LCBT algorithm encompass not only its intrinsic parameters such as $\nu$, $\rho$, $d_s$, but also encompass the environment and the algorithms employed by the agent.

Question 3: How can a black-box attacker find a proper discretization of the state space? It seems unrealistic in the high-dimensional state space.

For the partitioning of the state space, theoretically, each substate should satisfy $diam_s(S_i)\leq L_s d_s < \Delta^o_{\dagger}+\Delta^{\dagger}_{min}$. In practical implementation, due to the diversity of the environment, for each subinterval, an attacker only needs to ensure that, for different initial states within the same subinterval and adopting the same policy, the generated Q-values are approximately close, with differences not exceeding the disparity between Q-values produced by employing the target policy and the worst policy for the same initial state (equivalently understood as trajectories being roughly similar, with differences not exceeding the trajectory disparities between employing the target policy and the worst policy for the same initial state). Although Q-values cannot be directly computed, there exists a certain degree of assessability in determining the similarity of trajectories.