Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper proposed a new black-box attack method in the hard-label setting. By using a well-designed policy network in a novel reinforcement learning formulation, the new method learns promising search directions of the adversarial examples and showed that query complexity is significantly reduced in experiments.

A couple questions I have:

How are \beta_1 and \beta_2 chosen?

Is there any convergence analysis? How do we guarantee the proposed attacking method will converge?

The proposed method is introduced as an attack that minimize L_2 distance.  Is it possible to extend this attacking method to L_inf?

I am curious, have you tried evaluate the attacking methods on DenseNet as the victim model?

Overall, I think this paper is very readable and is clearly written with a very good background and context. I found the idea of the paper original and interesting. And the authors have conducted experiments that show their new method has the best query efficiency, which is reasonable and aligns with their idea. For cons, this paper does not have a convergence analysis. And if the experiments could be conducted on more data sets and more victim models, then it would be more convincing. 


review_title: Interesting paper, clearly written, with good empirical result

final_score: rating: 7: Good paper, accept
review_content: **Summary** :
This work proposes to formulate the problem of black-box adversarial attacks as learning a policy network that predicts offsets to some initial guesses of adversarial examples. The proposed PDA method tackles the problematic situation of queries with only hard labels. A specific reward, architecture, and pretraining setups are designed for the policy network to learn useful directions in updating the adversarial examples. Experiments on MNIST, CIFAR10, and ImageNet show the proposed PDA produced less distorted adversarial examples with less sampling budget for the black box attacks than two recent baseline attacks.

**Strengths** :
- The quarry efficiency is demonstrated compared to the two baselines (Boundary Attack, HopSkipJumpAttack) with less distortion on standard datasets and models.
- The paper is well written and well presented. The mathematical notations are clear and informative. 
- The use of policy networks to produce black-box adversarial attacks is a novel idea. It might open a direction for other fields interested in security besides the usefulness in the adversarial ML community. 

**Weaknesses**:
- The work has a limited ablation study. While the authors did provide an ablation on the policy network architecture and pretraining, some essential components of the reward setup and the algorithm are given without proper justification nor ablation study, e.g., the 0.5 and 0 of $\beta$ values in the reward limits in Algorithm 1. It would also be appreciated to show the attack's transferability between different models on the same datasets. 
- The proposed pipeline is complicated compared to the baselines. Pre-Training a policy network, then training the network adds to the computing complexity of the problem. While the sampling efficiency has increased, the compute and memory efficiency of the attacks have decreased. The baselines NATTACK: ( Li et. al , ICML 2019) and AutoZoom (Tu et. al, AAAI 2019 ) could have been adapted and compared against in the paper to see how useful are the policy networks.   
- Missing some references[a,b]. [a] uses a deep U-net network to produce adversarial attacks that are black box-transferable to unseen models. It bears similarity to the proposed network architecture in which the goal is to produce differences rather than predict the perturbation directly. The work in [b] formulates the problem of attacking black-box models as the perturbation to the victim's environment and tries to learn actions by the adversary that minimizes the victim model's reward.      



[a] Nasser at. al , "Cross-Domain Transferability of Adversarial Perturbations", ( NeurIPS 2019 )  
[b] Hamdi et. al, "SADA: Semantic Adversarial Diagnostic Attacks for Autonomous Applications" (AAAI 2020)



Minor issues :
The tables could have been illustrated as plots for easier following and comparisons 

review_title: promising new way of blackbox attacks 

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
This paper proposes a new hard-label black-box adversarial attack method based on reinforcement learning. The authors formulate the black-box attacking problem as a reinforcement learning problem, and design a policy network to learn the appropriate attack directions, in order to achieve more efficient attacks. The proposed policy-driven attack (PDA) algorithm is able to craft adversarial examples with lower distortions under the same query budgets. Experiment results show that with a pre-trained policy model, PDA outperforms two baseline methods, Boundary Attack and HopSkipJumpAttack.

Strengths:
1. This paper is the first to incorporate reinforcement learning into black-box attacking. The proposed reinforcement learning formulation and the architecture of policy network are interesting and novel.
2. A significant amount of experiments are done to show the effectiveness and efficiency of the proposed policy-driven attack compared with baselines. Moreover, the ablation experiment in the main paper and appendix provide useful insights of how every component of PDA works.
3. The paper is in general well-written and easy to follow. Implementation details are clearly described. 


Weakness:
1. My main concern is that there is a mismatch between the claim and the experiment. In the experiments, the paper mainly shows the results with pre-trained policy networks. However, the pertaining dataset S requires a lot of queries to the victim, which is conflictive with the purpose to reduce the number of queries. Although the authors mention that they consider the case where a large number of adversarial examples are required so that the pre-training samples can be omitted, the experiment setting does not match this assumption (500 queries * 5000 images in the pretraining dataset, versus 25 queries * 1000 images in the testing dataset which is used to evaluate the performance). It is not clear whether the performance of PDA is still the best when the number of adversarial examples keeps increasing, as it is a deep RL network, not guaranteed to be stable. ———— The authors may consider the following ways to make the experiment more convincing: (1) using much more images in the testing phase than in the pertaining phase; (2) sampling the pre-training dataset from another classifier on the same dataset, rather than from the real victim (in this way the queries to the victim can be really saved); (3) incorporating both the pre-training dataset and the testing dataset in the final performance evaluation. 
2. As also pointed out by the authors, reinforcement learning is itself sample-consuming. Applying RL to a complicated task could be difficult and non-stable. This paper proposes a few methods to facilitate learning, e.g.,  domain knowledge, pre-training, which are nice. But according to table 5, without pre-training, PDA performs similarly to HopSkipJumpAttack (even worse when internal classifier h is used), while the latter is easier to implement. This is a little concerning, suggesting the necessarily of pre-training for PDA if one wants to benefit from using PDA. I might be wrong, but if this is the case, it will be better for the authors to emphasize the importance of pre-training, and show the reasonability of using pre-training samples as stated in point 1 above.

Minor comments:
- Although the authors formulate the attacking process as a decision making problem and use a policy network to generate actions / search directions, I do not see the necessity of using RL techniques. The main reason is, there is no “horizon”, as the agent does not consider future rewards. (I am not sure whether the authors consider the future rewards in the implementation, but the description seems to only consider the current state.) Thus it might be enough to formalize this problem as a contextual bandit. This point does not influence my rating though.
review_title: The idea is good, but evaluation is biased

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a new hard-label black-box adversarial attack method based on reinforcement learning. The general idea is to improve the adversarial noise compressing efficiency taking advantage of past queries and the policy network. Experiments are conducted on MNIST, CIFAR-10 and ImageNet and achieved superior performance compared to other hard-label black-box attacks. In addition, ablation studies are conducted to verify the effectiveness of the proposed attack.

There is almost no intersection between reinforcement learning and adversarial attacks for three main reasons. First of all, the action space of optimizing adversarial noises is too large for the reinforcement learning algorithm to converge. Secondly, the optimal attack strategies of different images are quite different, so it is difficult to learning a unified policy network to attack the whole image classification dataset. In addition, it is difficult to design the value function to guide the attack process. This paper innovatively applies reinforcement learning in the neighborhood of the decision boundary and solves the above problem, realizing the adaptive adjustment of the noise-searching direction. 

I have three questions about the practicality of the proposed attack. First, according to algorithm 1, the single action in the policy-driven attack is a direction sampled from Gaussian distribution, so the dimensionality of the action space is still high. Will this affect the convergence of the policy network? Secondly, if the policy network is optimized after each query, will the attack speed be severely lagged? In addition, section 3.5 of this paper discussed the pre-training of the policy network. I wonder whether the policy and the target model are coupled. If the target model changes, is it necessary to retrain the policy network? This may affect the practicability of the attack.

review_title: Official Blind Review #2

Meta-review: The paper proposes an RL-based approach for decision-based attack. All the reviewers like the paper after the rebuttal phase, and we would like to encourage the authors to incorporate the new experiments in the camera-ready version. Furthermore, some recent decision-based attacks should also be included in the comparisons, such as

Li et al., QEBA: Query-Efficient Boundary-Based Blackbox Attack. (CVPR 2020) 

Cheng et al., Sign-OPT: A Query-Efficient Hard-label Adversarial Attack. (ICLR 2020)
Decision: Accept (Poster)