Belief-Enriched Pessimistic Q-Learning against Adversarial State Perturbations

We appreciate your constructive comments and feedback. Now we will explain your concerns and questions point by point in the following.

Q1: The innovative aspects presented over WocaR-DQN appear to be incremental in nature.

A1: Our method differs from WocaR-DQN in three important aspects. First, we adopt the maximin framework as a principled approach for achieving robustness, which is applied at both training and test stages using the perturbed states as input. In contrast, WocaR-DQN uses a regularization term and an estimation of the worst-case loss in the loss function to gain robustness. While the former is insufficient in the face of strong attacks, the latter is estimated using a separate neural network, suffering from the gap between training and testing. Second, we incorporate belief modeling into robust decision making, which is crucial for combating strong attacks, but has not been considered in WocaR-DQN. Third, we introduce diffusion-based state purification for environments with raw-pixel input, which allows us to train a single policy against different attack budgets. In contrast, a separate policy is required in WocaR-DQN.

Q2: We only test on two atari games.

A2: We have conducted a new experiment and tested our methods on the Bankheist environment that is widely used in other baselines. However, due to the recent upgrade of the Gym package, all pre-trained models provided by other baselines failed to work anymore. Thus, we retrained all other baselines ourselves, which resulted in performances different from those reported in the original papers. The result of Bankheist is shown below.

Our DP-DQN-O and DP-DQN-F methods outperform other baselines in the BankHeist environment, although they suffer from a notable performance loss when the attack budget is 15/255 due to the complexity of the game. Also, DP-DQN-F shows better robustness than DP-DQN-O when $\epsilon=15/255$.

Answers for Q3 and Q4 are in the next comment due to the characters limitation.

Dear reviewer cDHy,

As the stage of the review discussion is ending soon, we would like to kindly ask you to review our response and consider making adjustments to the scores.

Sincerely,

Paper3965 Authors

We appreciate your constructive comments and feedback. Now we will explain your concerns and questions point by point in the following.

Q1: How sensitive our algorithm to the choice of hyperparameters?

A1: We did not fine-tune most of the hyperparameters. For training the RL policies, we used the same default hyperparameters (e.g. learning rate, batch size, buffer size) as SA-MDP. For training the belief model, we took the default hyperparameters from the PF-RNN paper. For training the diffusion models, we used the default parameters in the DDPM and Progressive Diffusion papers, except for the number of reverse steps, which was significantly reduced to adapt the models to adversarial perturbations. As discussed in the second question proposed by Reviewer QHWx and Appendix F.3.2, our DP-DPN-O method is less sensitive to the number of reverse steps during testing, while our DP-DQN-F method is more sensitive to it.

Q2: How would our method perform in a scenario where such an environment is not readily available?

A2: We have added a general response to this question.

Q3: PA-AD is not evaluated on continuous gridworld.

A3: Following the reviewer’s suggestion, we have adapted PA-AD to our continuous Gridworld environment and tested our methods and other baselines. The results are as follows:

Similar to other attack baselines reported in our paper, our BP-DQN method achieves the best robustness under the PA-AD attack.

Q4: Computational overhead brought by diffusion model.

A4: We admit that using a diffusion model introduces additional overhead to our methods, especially for the DP-DQN-O method where the DDPM model is used. In this work, we considered a fast diffusion method called Progressive Diffusion in our DP-DQN-F method. As shown in Table 2(b), DP-DQN-F has significantly lower training and testing overhead than DP-DQN-O. To further speed up state purification, one possibility is to change the U-net structure used by the diffusion models to accelerate the reverse process. Another direction is to utilize other generative models such as GANs and autoencoders for state purification, which may not be as effective as diffusion-based methods but incur less computational overhead.

We hope that our explanations address your major concerns. If there are still concerns or questions, we would be happy to hear and discuss them.

Dear reviewer GsDy,

As the stage of the review discussion is ending soon, we would like to kindly ask you to review our response and consider making adjustments to the scores.

Sincerely,

Paper3965 Authors

We appreciate your constructive comments and feedback. Now we will explain your concerns and questions point by point in the following.

A1: How our methods perform when a clean environment is unavailable?

Q1: We have added a general response to this question.

A2: How our methods perform when the attack budget is unknown?

Q2: Our BP-DQN method does not require accurate knowledge about the attack budget. The results in the paper were obtained using a single policy trained against the PGD attack with $\epsilon = 0.1$, without further adaptation at the test stage against the actual attack budget (0.1 or 0.5).

Our DP-DQN methods also do not require accurate knowledge about the attack budget at the training stage. All the results shown in the paper for DP-DQN-O (resp. DP-DQN-F) were obtained using a single policy trained against the PGD attack with $\epsilon = 1/255$, and with the reverse steps $k= 5$ in DDPM (resp. $k=1$ in Progressive Distillation). However, we did adapt the value of $k$ at the test stage according to the actual attack budget in the paper. To understand the performance of our algorithms under an unknown attack budget at the test stage, we have conducted a new ablation study on these methods using the Pong environment with a fixed number of reverse steps in the diffusion model ($k = 30$ for DP-DQN-O and $k = 1$ for DP-DQN-F) and a fixed level of manually added noise (1/255) at the test stage, and tested them on PGD attacks with three different attack budgets (1/255, 3/255 and 15/255). The results for DP-DQN-O are $\epsilon = 1/255: 20 \pm 0$, $\epsilon = 3/255: 19.8 \pm 0.4$, $\epsilon = 15/255: 19.7 \pm 0.5$, which are on par with the results using an adapted $k$ shown in the paper. On the other hand, the results for DP-DQN-F are $\epsilon = 1/255: 20.4 \pm 0.9$, $\epsilon = 3/255: 13 \pm 7.4$, $\epsilon = 15/255: -20.6 \pm 0.4$, showing that it is more sensitive to attack budget. As a comparison, we have also tested other baselines using the policy trained under $\epsilon = 1/255$ against a PGD attack with budget $\epsilon = 3/255$, and the results are SA-DQN: $12 \pm 1.2$, WocaR-DQN: $-21 \pm 0$, showing that these methods are also sensitive to attack budget.

We hope that our explanations address your major concerns. If there are still concerns or questions, we would be happy to hear and discuss them.

We appreciate your constructive comments and feedback. Now we will explain your concerns and questions point by point in the following.

Q1: It has been shown that Stackelberg Equilibrium as defined in Definition 2 need not always exist, refer to theorem 4.3 https://arxiv.org/pdf/2212.02705.pdf. So, finding an approximate solution for them is meaningless. However, non-existence of Stackelberg equilibrium is a worst case phenomenon. Authors should incorporate this in their paper.

A1: We are aware of the negative result the reviewer mentioned. Please see the discussion below Definition 2 in Section 3, where we have cited the SA-MAP paper where this result was originally proved (Theorem 4 in the SA-MDP paper). We are also aware of the paper the reviewer mentioned and have cited its journal version in the Related Work section (Appendix B.1). The negative result implies that a policy that obtains the best possible value (against the strongest attack) across all states does not exist in general, but it does not exclude the possibility of finding an approximate solution that is close to the optimal state-wise. Although we were not able to identify a policy that obtains an approximate Stackelberg Equilibrium in the standard sense, we showed that our pessimistic Q learning algorithm (Algorithm 1) obtains a value function that is close to the optimal Q function without attacks (Theorem 1) under common assumptions.

Q2: It will be great if authors can include a short paragraph before section 3.2 discussing a big picture of their strategies before diving into each one of them.

A2: We present our basic solution framework, pessimistic Q-learning, in Section 3.3. Our approach derives maximin actions from the Q-function using perturbed states as input to safeguard against the agent’s uncertainty about true states. Notably, this approach is applied at both training and test stages, thus bridging the gap between the two as in previous work. We then improve the algorithm by incorporating the agent’s belief about true states into action selection in Section 3.4. To obtain a practical solution in high-dimensional state spaces, we present our BP-DQN algorithm in this section, which incorporates the above ideas into the classic Deep Q-Network (DQN) algorithm to obtain pessimistic DQN with belief states approximated using the PF-RNN method. To further scale our method to environments with raw-pixel input, we present another algorithm, DP-DQN, in Section 3.5, where we incorporate a diffusion-based purification scheme into pessimistic DQN to purify the pixel-wise perturbations.

Q3: Abstract wrongly mentions that past methods either regularize or retrain the policy. However, methods like Bharti et.al. just purify the states directly.

A3: We would like to thank the reviewer for pointing out the work beyond regularization-based methods and alternating training methods. We are aware of the purification-based methods, including the work by Bharti et al., and have provided a detailed comparison between our method and Bharti et al. in Appendix B.3. In particular, our method has two important components not considered in Bharti et al., namely, the maximin formulation and belief update. There also exist studies that detect if a state is perturbed or not at the test stage, e.g., Xiong et al., which uses an autoencoder-based method to detect perturbations, as we mentioned in Section 3.3 and Appendix B.1. We did not mention them in the abstract because Bharti et al. focuses on the backdoor attack rather than test-stage state perturbation we considered, while Xiong et al. focuses on test stage detection given a pre-trained policy.

Q4: How do our methods avoid the hardness in POMDP?

A4: We first note that while training a robust agent against adversarial state perturbations is closely related to POMDPs, they are also fundamentally different. In POMDPs, the agent’s observation is derived from a predetermined observation function as part of the environment. In contrast, the agent’s observation is determined by the attacker’s policy in adversarial state perturbations, which might be non-stationary or even adaptive, making the problem even harder.

In this work, we have exploited two key observations to bypass this obstacle. First, the attacker has a bounded budget to avoid detection, where the perturbed state must land in the \epsilon ball centered at the true state so that the agent could utilize historical information to generate a relatively accurate belief about true states, which might not be the case in general POMDPs. Further, for environments with raw-pixel input, existing attacks generate perturbations in the form of pixel-wise noise, which could be purified with the help of a diffusion model to generate a belief about the true state. These ideas together with our pessimistic training framework ensure high robustness against strong state perturbation attacks.

We hope that our explanations address your major concerns.

Dear authors, Thank you for your response! I am not very satisfied with the response to Q1(it is still not clear to me how can your algorithm provide an approximate solution to the problem which admits no solution? The notion of "approximate solution" being used does not seem to be a standard one) and also Q4(In my opinion just by constraining the attacker in $\epsilon$-ball radius would not permit the defender to recover back true states even if uses the historical information. If it can indeed do so, is there some threshold on $\epsilon$ above which defense is not possible and does your theory say something about it - because for large epsilon one can always change any state to any other state?). Hence, I would maintain my score for now.

Thank you for carefully reading our response and we are glad to further clarify your concerns.

For Q1, an accurate definition of approximate Stackelberg Equilibrium is as follows. First, as shown in Theorem 4.11 of https://arxiv.org/pdf/2212.02705.pdf, when the initial state distribution $Pr(s_0)$ is known, there is an agent policy $\pi^*$ that maximizes the worst-case expected state value against the optimal state perturbation attack, that is

$\forall \pi$, $\Sigma_{s_0\in S} Pr(s_0) V_{\pi^*\circ\omega_{\pi^*}}(s_0) \ge \Sigma_{s_0\in S} Pr(s_0) V_{\pi\circ\omega_{\pi}}(s_0)$

In particular, when the initial state $s_0$ is fixed, an optimal policy that maximizes the worst-case state value (against the optimal state perturbation attack) can be found. Let $V^*(s_0)$ denote this optimal state value. Note that $V^*(s_0)$ is obtained using a different policy for different $s_0$. Then a reasonable definition of approximate Stackelberg Equilibrium is a policy $\pi$ where its state value under each state $s_0$ is close to $V^*(s_0)$, that is, $|V_{\pi\circ\omega_{\pi}}(s_0) - V^*(s_0)| \leq \Delta$ for some constant $\Delta$. Note that this condition should hold for each state $s_0$. Also note that we compare $\pi$ with a different optimal policy with respect to each $s_0$, thus bypassing the impossibility result.

In the paper, we further approximated $V^*(s_0)$ by the optimal value without attacks and derived $\Delta$ in the simplified setting (Theorem 1). However, we believe that this definition presents a novel extension of approximate Stackelberg Equilibrium in the standard sense and will incorporate it into the next version of the paper.

For Q4, we did not claim that our method can recover the exact true state from the perturbed state. Both our historical information-based and diffusion-based belief models generate a set of belief states $M_t$ to approximate the true state. Ideally, the belief states should provide a better approximation of the true state beyond what can be estimated from the epsilon ball centered at the perturbed state. Although we do not have a theoretical characterization of how the belief model reduces the defender’s uncertainty about the true state, we have provided some empirical evidence in the paper. Figures 5 (a)-(c) (Appendix F.3.2) show that the $l_2$ distance between the denoised state (generated from the belief) and the true state is significantly smaller than the $l_2$ distance between the perturbed state and the true state.

Further, Theorem 1 shows that the performance loss of our pessimistic Q-learning approach (compared with the optimal policy without attacks) increases linearly over the defender’s uncertainty about the true state, showing the importance of reducing this uncertainty.

We hope that our explanations address your concerns.

Dear reviewer achV,

As the stage of the review discussion is ending soon, we would like to kindly ask you to review our response and consider making adjustments to the scores.

Sincerely,

Paper3965 Authors