summaries: The authors study the sample complexity of adversarially robust learning with access to unlabeled samples. Theoretically, they consider the setting of Schmidt et al. 2018 (separating two class-conditional Gaussians) and present an algorithm which can learn a robust classifier with only a few labeled samples and a large number of unlabeled samples (circumventing the sample complexity separation of the original work). Then, the authors propose a modification of the VAT algorithm (Miyato et al. 2018) to train deep networks utilizing unlabeled samples. They find that, empirically, their algorithm achieves better performance compared to standard adversarial training on the labeled samples.

summaries: Paper summary: This paper seeks to improve robust generalization performance with the help of unlabeled data. The authors first consider the toy model presented in Schmidt et al. and show how the labeled sample complexity in the robust setting can be lowered to match the standard setting if sufficient unlabeled data is available. They then propose a practical algorithm to improve robust test accuracy and evaluate it on the MNIST and CIFAR datasets.

summaries: This paper considers the problem of adversarial robustness. The paper shows that (Theorem 1) robust generalization error can be bounded in terms of the standard generalization error and a stability term, that does not depend on the labels. The paper also shows that for a simple classification problem involving learning the separator for a symmetric 2 gaussian mixture data, we can solve this problem robustly without additional labeled examples. The paper suggests that we can use unlabeled data to improve the robust generalization. Towards this the paper regularizer on the unlabeled data, that promotes stability in the model prediction. The paper evaluates this on Mnist and Cifar showing the better performance of the proposed regularization over PGD adversarial training.

abstractText: Neural network robustness has recently been highlighted by the existence of adversarial examples. Many previous works show that the learned networks do not perform well on perturbed test data, and significantly more labeled data is required to achieve adversarially robust generalization. In this paper, we theoretically and empirically show that with just more unlabeled data, we can learn a model with better adversarially robust generalization. The key insight of our results is based on a risk decomposition theorem, in which the expected robust risk is separated into two parts: the stability part which measures the prediction stability in the presence of perturbations, and the accuracy part which evaluates the standard classification accuracy. As the stability part does not depend on any label information, we can optimize this part using unlabeled data. We further prove that for a specific Gaussian mixture problem illustrated by Schmidt et al. (2018), adversarially robust generalization can be almost as easy as the standard generalization in supervised learning if a sufficiently large amount of unlabeled data is provided. Inspired by the theoretical findings, we further show that a practical adversarial training algorithm that leverages unlabeled data can improve adversarial robust generalization on MNIST and Cifar-10.

authors:
Anish Athalye
Nicholas Carlini
David A. Wagner

title: Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples

authors:
Ben Athiwaratkun
Marc Finzi
Pavel Izmailov
Andrew Gordon Wilson

title: There are many consistent explanations of unlabeled data: Why you should average

venue: In International Conference on Learning Representations,

authors:
Mikhail Belkin
Partha Niyogi
Vikas Sindhwani

title: Manifold regularization: A geometric framework for learning from labeled and unlabeled examples

venue: Journal of machine learning research,

authors:
Battista Biggio
Igino Corona
Davide Maiorca
Blaine Nelson
Nedim Šrndić
Pavel Laskov
Giorgio Giacinto
Fabio Roli

title: Evasion attacks against machine learning at test time

venue: In Joint European conference on machine learning and knowledge discovery in databases,

authors:
Nicholas Carlini
David A. Wagner

title: Towards evaluating the robustness of neural networks

authors:
Yair Carmon
Aditi Raghunathan
Ludwig Schmidt
Percy Liang
John C Duchi

title: Unlabeled data improves adversarial robustness

venue: arXiv preprint arXiv:1905.13736,

authors:
Liang-Chieh Chen
Yukun Zhu
George Papandreou
Florian Schroff
Hartwig Adam

title: Encoderdecoder with atrous separable convolution for semantic image segmentation

venue: arXiv preprint arXiv:1802.02611,

authors:
Daniel Cullina
Arjun Nitin Bhagoji
Prateek Mittal

title: Pac-learning in the presence of evasion adversaries

venue: arXiv preprint arXiv:1806.01471,

title: Does baum-welch re-estimation help taggers

venue: Proceedings of the Fourth Conference on Applied Natural Language Processing,

authors:
Alhussein Fawzi
Hamza Fawzi
Omar Fawzi

title: Adversarial vulnerability for any classifier

venue: arXiv preprint arXiv:1802.08686,

authors:
Ruiqi Gao
Tianle Cai
Haochuan Li
Liwei Wang
Cho-Jui Hsieh
Jason D Lee

title: Convergence of adversarial training in overparametrized networks

authors:
Ian Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

authors:
Gao Huang
Zhuang Liu
Laurens Van Der Maaten
Kilian Q Weinberger

title: Densely connected convolutional networks

venue: In CVPR, volume 1(2),

authors:
Ruitong Huang
Bing Xu
Dale Schuurmans
Csaba Szepesvári

title: Learning with a strong adversary

venue: arXiv preprint arXiv:1511.03034,

title: Transductive inference for text classification using support vector machines

venue: In Proceedings of the Sixteenth International Conference on Machine Learning,

authors:
Samuli Laine
Timo Aila

title: Temporal ensembling for semi-supervised learning

authors:
Yann LeCun
Léon Bottou
Yoshua Bengio
Patrick Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
Tsung-Yi Lin
Priyal Goyal
Ross Girshick
Kaiming He
Piotr Dollár

title: Focal loss for dense object detection

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Jonathan Long
Evan Shelhamer
Trevor Darrell

title: Fully convolutional networks for semantic segmentation

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

venue: arXiv preprint arXiv:1706.06083,

authors:
Takeru Miyato
Shin-ichi Maeda
Shin Ishii
Masanori Koyama

title: Virtual adversarial training: a regularization method for supervised and semi-supervised learning

authors:
Mehryar Mohri
Afshin Rostamizadeh
Ameet Talwalkar

title: Foundations of Machine Learning

authors:
Seyed-Mohsen Moosavi-Dezfooli
Alhussein Fawzi
Pascal Frossard

title: Deepfool: A simple and accurate method to fool deep neural networks

venue: In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
Amir Najafi
Shin-ichi Maeda
Masanori Koyama
Takeru Miyato

title: Robustness to adversarial perturbations in learning from incomplete data

authors:
Nicolas Papernot
Patrick D. McDaniel
Ian J. Goodfellow

title: Transferability in machine learning: from phenomena to black-box attacks using adversarial samples

authors:
Antti Rasmus
Mathias Berglund
Mikko Honkala
Harri Valpola
Tapani Raiko

title: Semisupervised learning with ladder networks

venue: Advances in Neural Information Processing Systems

authors:
Joseph Redmon
Santosh Divvala
Ross Girshick
Ali Farhadi

title: You only look once: Unified, real-time object detection

authors:
Shaoqing Ren
Kaiming He
Ross Girshick
Jian Sun

title: Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing

authors:
Mehdi Sajjadi
Mehran Javanmardi
Tolga Tasdizen

title: Regularization with stochastic transformations and perturbations for deep semi-supervised learning

authors:
Ludwig Schmidt
Shibani Santurkar
Dimitris Tsipras
Kunal Talwar
Aleksander Madry

title: Adversarially robust generalization requires more data

venue: In Advances in Neural Information Processing Systems,

authors:
Ali Shafahi
Mahyar Najibi
Amin Ghiasi
Zheng Xu
John Dickerson
Christoph Studer
Larry S Davis
Gavin Taylor
Tom Goldstein

title: Adversarial training for free

authors:
Karen Simonyan
Andrew Zisserman

title: Very deep convolutional networks for large-scale image recognition

venue: arXiv preprint arXiv:1409.1556,

authors:
Christian Szegedy
Wojciech Zaremba
Ilya Sutskever
Joan Bruna
Dumitru Erhan
Ian J. Goodfellow
Rob Fergus

title: Intriguing properties of neural networks

authors:
Antti Tarvainen
Harri Valpola

title: Mean teachers are better role models: Weight-averaged

authors:
Xiaolong Wang
Ross Girshick
Abhinav Gupta
Kaiming He

title: Non-local neural networks

venue: Conference on Computer Vision,

authors:
PMLR. Bing Zhang
Mingguang Shi

title: Semi-supervised learning improves gene

authors:
Jun 2019b. PMLR. Hengshuang Zhao
Jianping Shi
Xiaojuan Qi
Xiaogang Wang
Jiaya Jia

title: Pyramid scene parsing

title: Under the same setting as in Theorem 4, for any p ≥ 1 and ≥ 0, and for any unit vector ŵ ∈ R such that 〈ŵ

heading: 1 INTRODUCTION

text:
Deep learning (LeCun et al., 2015), especially deep Convolutional Neural Network (CNN) (LeCun et al., 1998), has led to state-of-the-art results spanning many machine learning fields, such as image classification (Simonyan & Zisserman, 2014; He et al., 2016; Huang et al., 2017; Hu et al., 2017), object detection (Ren et al., 2015; Redmon et al., 2016; Lin et al., 2018), semantic segmentation (Long et al., 2015; Zhao et al., 2017; Chen et al., 2018) and action recognition (Tran et al., 2015; Wang et al., 2016; 2018).
Despite the great success in numerous applications, recent studies show that deep CNNs are vulnerable to some well-designed input samples named as Adversarial Examples (Szegedy et al., 2013; Biggio et al., 2013). Take image classification as an example, for almost every commonly used well-performed CNN, attackers are able to construct a small perturbation on an input image. The perturbation is almost imperceptible to humans but can fool the model to make a wrong prediction. The problem is serious as some designed adversarial examples can be transferred among different kinds of CNN architectures (Papernot et al., 2016), which makes it possible to perform black-box attack: an attacker has no access to the model parameters or even architecture, but can still easily fool a machine learning system.
There is a rapidly growing body of work on studying how to obtain a robust neural network model. Most of the successful methods are based on adversarial training (Szegedy et al., 2013; Madry et al., 2017; Goodfellow et al., 2015; Huang et al., 2015). The high-level idea of these works is that during training, we predict the strongest perturbation to each sample against the current model and use the perturbed sample together with the correct label for gradient descent optimization. However, the learned model tends to overfit on the training data and fails to keep robust on unseen testing data. For example, using the state-of-the-art adversarial robust training method (Madry et al., 2017), the defense success rate of the learned model on the testing data is below 60% while that on the training data is almost 100%, which indicates that the robustness fails to generalize. Some theoretical results further show that it is challenging to achieve adversarially robust generalization. Fawzi et al.
(2018) proves that adversarial examples exist for any classifiers and can be transferred across different models, making it impossible to design network architectures free from adversarial attacks. Schmidt et al. (2018) shows that adversarially robust generalization requires much more labeled data than standard generalization in certain cases. Tsipras et al. (2019) presents an inherent trade-off between accuracy and robust accuracy and argues that the phenomenon comes from the fact that robust classifiers learn different features. Therefore it is hard to reach high robustness for standard training methods.
Given the challenge of the task and previous findings, in this paper, we provide several theoretical and empirical results towards better adversarially robust generalization. In particular, we show that we can learn an adversarially robust model which generalizes well if we have plenty of unlabeled data, and the labeled sample complexity for adversarially robust generalization in Schmidt et al. (2018) can be largely reduced if unlabeled data is used. First, we show that the expected robust risk can be upper bounded by the sum of two terms: a stability term which measures whether the model can output consistent predictions under perturbations, and an accuracy term which evaluates whether the model can make correct predictions on natural samples. Given the stability term does not rely on ground truth labels, unlabeled data can be used to minimize this term and thus improve the generalization ability. Second, we prove that for the Gaussian mixture problem defined in Schmidt et al. (2018), if unlabeled data can be used, adversarially robust generalization will be almost as easy as the standard generalization in supervised learning (i.e. using the same number of labeled samples under similar conditions). Inspired by the theoretical findings, we provide a practical algorithm that can learn from both labeled and unlabeled data for better adversarially robust generalization. Our experiments on MNIST and Cifar-10 show that the method achieves better performance, which verifies our theoretical findings.
Our contributions are in three folds.
• In Section 3.2.1, we provide a theorem to show that unlabeled data can be naturally used to improve the expected robust risk in general setting and thus leveraging unlabeled data is a way to improve adversarially robust generalization.
• In Section 3.2.2, we discuss a specific Gaussian mixture problem introduced in Schmidt et al. (2018). In Schmidt et al. (2018), the authors proved that in this case, the labeled sample complexity for robust generalization is significantly larger than that for standard generalization. As an extension of this work, we prove that in this case, the labeled sample complexity for robust generalization can be the same as that for standard generalization if we have enough unlabeled data.
• Inspired by our theoretical findings, we provide an adversarial robust training algorithm using both labeled and unlabeled data. Our experimental results show that the algorithm achieves better performance than baseline algorithms on MNIST and Cifar-10, which empirically proves that unlabeled data can help improve adversarially robust generalization.

heading: 2 RELATED WORKS

text:
Adversarial attacks and defense Most previous works study how to attack a neural network model using small perturbations under certain norm constraints, such as l∞ norm or l2 norm. For the l∞ constraint, Fast Gradient Sign Method (FGSM) (Goodfellow et al., 2015) finds a direction to which the perturbation increases the classification loss at an input point to the greatest extent; Projected Gradient Descent (PGD) (Madry et al., 2017) extends FGSM by updating the direction of the attack in an iterative manner and clipping the modifications in the norm range after each iteration. For the l2 constraint, DeepFool (Moosavi-Dezfooli et al., 2016) iteratively computes the minimal norm of an adversarial perturbation by linearizing around the input in each iteration. C&W attack (Carlini & Wagner, 2016) is a comprehensive approach that works under both norm constraints. In this work, we focus on learning a robust model to defend the white-box attack, i.e. the attacker knows the model parameters and thus can use the algorithms above to attack the model.
There are a large number of papers about defending against adversarial attacks, but the result is far from satisfactory. Remarkably, Athalye et al. (2018) shows most defense methods take advantage of so-called “gradient mask” and provides an attacking method called BPDA to correct the gradients. So far, adversarial training (Madry et al., 2017) has been the most successful white-box defense al-
gorithm. By modeling the learning problem as a mini-max game between the attacker and defender, the robust model can be trained using iterative optimization methods. Some recent papers (Wang et al., 2019; Gao et al., 2019) theoretically prove the convergence of adversarial training. Moreover, Shafahi et al. (2019); Zhang et al. (2019a) propose ways to accelerate the speed of adversarial training. Adversarial logit pairing (Kannan et al., 2018) and TRADES (Zhang et al., 2019b) further improve adversarial training by decomposing the prediction error as the sum of classification error and boundary error, and Wang et al. (2019) proposes to improve adversarial training by evaluating the quality of adversarial examples using the FOSC metric.
Semi-supervised learning Using unlabeled data to help the learning process has been proved promising in different applications (Rasmus et al., 2015; Zhang & Shi, 2011; Elworthy, 1994). Many approaches use regularizers called “soft constraints” to make the model “behave” well on unlabeled data. For example, transductive SVM (Joachims, 1999) uses prediction confidence as a soft constraint, and graph-based SSL (Belkin et al., 2006; Talukdar & Crammer, 2009) requires the model to have similar outputs at endpoints of an edge. The most related work to ours is the consistencybased SSL. It uses consistency as a soft constraint, which encourages the model to make consistent predictions on unlabeled data when a small perturbation is added. The consistency metric can be either computed by the model’s own predictions, such as the Π model (Sajjadi et al., 2016), Temporal Ensembling (Laine & Aila, 2016) and Virtual Adversarial Training (Miyato et al., 2018), or by the predictions of a teacher model, such as the mean teacher model (Tarvainen & Valpola, 2017).
Semi-supervised learning for adversarially robust generalization There are three other concurrent and independent works (Carmon et al., 2019; Uesato et al., 2019; Najafi et al., 2019) which also explore how to use unlabeled data to help adversarially robust generalization. We describe the three works below, and compare them with ours. See also Carmon et al. (2019) and Uesato et al. (2019) for the comparison of all the four works from their perspective.
Najafi et al. (2019) investigate the robust semi-supervised learning from the distributionally robust optimization perspective. They assign soft labels to the unlabeled data according to an adversarial loss and train such images together with the labeled ones. Results on a wide range of tasks show that the proposed algorithm improves the adversarially robust generalization. Both Najafi et al. (2019) and we conduct semi-supervised experiments by removing labels from the training data.
Uesato et al. (2019) study the Gaussian mixture model of Schmidt et al. (2018) and theoretically show that a self-training algorithm can successfully leverage unlabeled data to improve adversarial robustness. They extend the self-training algorithm to the real image dataset Cifar10, augment it with unlabeled Tiny Image dataset and improve state-of-the-art adversarial robustness. They show strong improvements in the low labeled data regimes by removing most labels from CIFAR-10 and SVHN. In our work, we also study the Gaussian mixture model and show that a slightly different algorithm can improve adversarially robust generalization as well. We observe similar improvements using our algorithm on Cifar-10 and MNIST.
Carmon et al. (2019) obtain similar theoretical and empirical results as in Uesato et al. (2019), and offer a more comprehensive analysis of other aspects. They show that by using unlabeled data and robust self-training, the learned models can obtain better certified robustness against all possible attacks. Moreover, they study the impact of different training components on the final model performance, such as the size of unlabeled data. We also study the influence of different factors in our experiments and have similar observations.

heading: 3 MAIN RESULTS

text: In this section, we illustrate the benefits of using unlabeled data for robust generalization from a theoretical perspective.

heading: 3.1 NOTATIONS AND DEFINITIONS

text:
We consider a standard classification task with an underlying data distribution PXY over pairs of examples x ∈ Rd and corresponding labels y ∈ {1, 2, · · · ,K}. Usually PXY is unknown and we can only access to S = {(x1, y1), · · · , (xn, yn)} in which (xi, yi) is independent and identically
drawn from PXY , i = 1, 2, · · · , n. For ease of reference, we denote this empirical distribution as P̂XY (i.e. the uniform distribution over i.i.d. sampled data). We also assume that we are given a suitable loss function l(f(x), y), where f ∈ F is parameterized by θ. The standard loss function is the zero-one loss, i.e. l0/1(y′, y) = I[y′ 6= y]. Due to its discontinuous and non-differentiable nature, surrogate loss functions such as cross-entropy or mean square loss are commonly used during optimization.
Our goal is to find an f ∈ F that minimizes the expected classification risk. Without loss of any generality, our theory is mainly based on the binary classification problem, i.e. K = 2. All theorems below can be easily extended to the multi-class classification problem. For a binary classification problem, the expected classification risk is defined as below. Definition 1. (Expected classification risk). Let PXY be a probability distribution over Rd×{±1}. The expected classification risk R of a classifier f : Rd → {−1, 1} under distribution PXY and loss function l is defined as
R = E(x,y)∼PXY l(f(x), y) (1)
We use R(f) to denote the classification risk under the underlying distribution and use R̂(f) to denote the classification risk under the empirical distribution. We use R0/1(f) to denote the risk with the zero-one loss function. The classification risk characterizes whether the model f is accurate. However, we also care about whether f is robust. For example, when input x is an image, we hope a small change (perturbation) to x will not change the prediction of f . To this end, Schmidt et al. (2018) defines expected robust classification risk as follows. Definition 2. (Expected robust classification risk). Let PXY be a probability distribution over Rd× {±1} and B : Rd → P ( Rd )
be a perturbation set. Then the B-robust classification risk RB−robust of a classifier f : Rd → {−1, 1} under distribution PXY and loss function l is defined as
RB−robust = E(x,y)∼PXY sup x′∈B(x)
l(f(x′), y) (2)
Again, we use RB−robust(f) to denote the expected robust classification risk under the underlying distribution and use R̂B−robust(f) to denote the expected robust classification risk under the empirical distribution. We use R0/1B−robust(f) to denote the robust risk with the zero-one loss function. In real practice, the most commonly used setting is the perturbation under -bounded l∞ norm constraint B ∞(x) = { x′ ∈ Rd| ‖x′ − x‖∞ ≤ ε } . For simplicity, we refer to the robustness defined by this perturbation set as ` ∞-robustness.

heading: 3.2 ROBUST GENERALIZATION ANALYSIS

text: Our first result (Section 3.2.1) shows that unlabeled data can be used to improve adversarially robust generalization in general setting. Our second result (Section 3.2.2) shows that for a specific learning problem defined on Gaussian mixture model, compared to previous work (Schmidt et al., 2018), the sample complexity for robust generalization can be significantly reduced by using unlabeled data. Both results suggest that using unlabeled data is a natural way to improve adversarially robust generalization. All detailed proofs of the theorems and lemmas in this section can be found in the appendix.

heading: 3.2.1 GENERAL RESULTS

text:
In this subsection, we show that the expected robust classification risk can be bounded by the sum of two terms. The first term only depends on the hypothesis space and the unlabeled data, and the second term is a standard PAC bound. Theorem 1. Let F be the hypothesis space. Let S = (xi, yi)ni=1 be the set of n i.i.d. samples drawn from the underlying distribution PXY . For any function f ∈ F , with probability at least 1− δ over the random draw of S, we have
R 0/1 B−robust(f) ≤ Ex∼PX sup x′∈B(x) (I(f(x′) 6= f(x))︸ ︷︷ ︸ (1) + R̂0/1(f) +RadS(F) + 3
√ log 2δ 2n︸ ︷︷ ︸
(2)
, (3)
where (1) is a term that can be optimized with only unlabeled data and (2) is the standard PAC generalization bound. PX is the marginal distribution for PXY and RadS(F) is the empirical Rademacher complexity of hypothesis space F .
From Theorem 1, we can see that the expected robust classification risk is bounded by the sum of two terms: the first term only involves the marginal distribution PX and the second term is the standard PAC generalization error bound. This shows that the expected robust risk minimization can be achieved by jointly optimizing the two terms simultaneously: we can optimize the first term using unlabeled data sampled from PX and optimize the second term using labeled data sampled from PXY , which is the same as the standard supervised learning.
While Cullina et al. (2018) suggests that in the standard PAC learning scenario (only labeled data is considered), the generalization gap of robust risk can be sometimes uncontrollable by the capacity of hypothesis space F , our results show that we can mitigate this problem by introducing unlabeled data. In fact, our following result shows that with enough unlabeled data, learning a robust model can be almost as easy as learning a standard model.

heading: 3.2.2 LEARNING FROM GAUSSIAN MIXTURE MODEL

text:
The learning problem defined on Gaussian mixture model is illustrated in Schmidt et al. (2018) as an example to show adversarially robust generalization needs much more labeled data compared to standard generalization. In this subsection, we show that for this specific problem, just using more unlabeled data is enough to achieve adversarially robust generalization. For completeness, we first list the results in Schmidt et al. (2018) and then show our theoretical findings. Definition 3. (Gaussian mixture model (Schmidt et al., 2018)). Let θ∗ ∈ Rd be the per-class mean vector and let σ > 0 be the variance parameter. Then the (θ∗, σ)-Gaussian mixture model is defined by the following distributionPXY over (x, y) ∈ Rd×{±1}: First, draw a label y ∈ {±1} uniformly at random. Then sample the data point x ∈ Rd from N (y · θ∗, σ2Id).
Given the samples from the distribution defined above, the learning problem is to find a linear classifier to predict label y from x. Schmidt et al. (2018) proved the following sample complexity bound for standard generalization. Theorem 2. (Theorem 4 in Schmidt et al. (2018)). Let (x, y) be drawn from the (θ?, σ)-Gaussian mixture model with ‖θ?‖2 = √ d and σ ≤ c ·d1/4 where c is a universal constant. Let ŵ ∈ Rd be the vector ŵ = y · x. Then with high probability, the expected classification risk of the linear classifier fŵ using 0-1 loss is at most 1%.
Theorem 2 suggests that we can learn a linear classifier with low classification risk (e.g., 1%) even if there is only one labeled data. However, the following theorem shows that for adversarially robust generalization under ` ∞ perturbation, significantly more labeled data is required. Theorem 3. (Theorem 6 in Schmidt et al. (2018)). Let gn be any learning algorithm, i.e. a function from n samples to a binary classifier fn. Moreover, let σ = c1 · d1/4, let ≥ 0, and let θ ∈ Rd be drawn from N (0, Id). We also draw n samples from the (θ, σ)-Gaussian mixture model. Then the expected ` ∞-robust classification risk of fn using 0-1 loss is at least 1 2 (1 − 1/d) if the number of labeled data n ≤ c2 2 √ d
log d .
As we can see from above theorem, the sample complexity for robust generalization is larger than that of standard generalization by √ d. This shows that for high-dimensional problems, adversarial robustness can provably require a significantly larger number of samples. We provide a new result which shows that the learned model can be robust if there is only one labeled data and sufficiently many unlabeled data. Our theorem is stated as follow: Theorem 4. Let (xL, yL) be a labeled point drawn from (θ∗, σ)-Gaussian mixture model PXY with ‖θ∗‖2 = √ d and σ = O(d1/4). Let xU1 , · · · , xUn be n unlabeled points drawn from PX . Let
v ∈ Rd such that v ∈ arg max‖v‖=1 ∑n i=1(v >xUi ) 2. Let ŵ = sign(yL · v>xL)v. Then there exists a constant D such that for any d ≥ D, with high probability, the expected ` ∞-robust classification risk of fŵ using 0-1 loss is at most 1% when the number of unlabeled points n = Ω(d) and ≤ 12 .
From Theorem 4, we can see that when the number of unlabeled points is significant, we can learn a highly accurate and robust model using only one labeled point.
Proof sketch The learning process can be intuitively described as the following three steps: in the first step, we use unlabeled data to estimate the direction of θ∗ although we do not know the label that θ∗ (or −θ∗) corresponds to. Specifically, we choose the direction v which maximizes the quantity ∑n i=1(v >xUi ) 2 which can be viewed as a measure of the confidence at data points. In the second step, we use the given labeled point to determine the sign of θ∗ with high probability, we note that when the direction is correctly estimated in the first step, then the only one labeled point is sufficient to give the correct sign with high probability. Finally, we give a good estimation of θ∗ by combining the two steps above and learn a robust classifier. The three key lemmas corresponding to the three steps are listed below (ci are constants for i = 0, 1, 2, 3).
Lemma 1. Under the same setting as Theorem 4, suppose that n > d and σ √
σ2+d nd < 1 128 . Then,
with probability at least 1− c1e−c2nmin{ √ dc3 σ ,( √ dc3 σ )
2}, there is a unique unit maximal eigenvector v of the sample covariance matrix Σ̂ = 1n ∑n i=1 x U i x
U> i such that∥∥∥∥v − θ∗√d ∥∥∥∥ 2 ≤ c0σ √ σ2 + d nd + c3 (4)
Lemma 2. Under the same setting as Theorem 4, suppose v is a unit vector such that ∥∥∥v − θ∗√
d ∥∥∥ 2 ≤
τ for some constant τ < √ 2. Then with probability at least 1− exp(−d(1− τ2 2 ) 2
2σ2 ), we have
sign(yL · v>xL)v>θ∗ > 0 (5) Lemma 3. (Lemma 20 in Schmidt et al. (2018)). Under the same setting as Theorem 4, for any p ≥ 1 and ≥ 0, and for any unit vector ŵ such that 〈ŵ, θ?〉 ≥ ‖ŵ‖∗p , where ‖ · ‖∗p is the dual norm of
‖ · ‖p, the linear classifier fŵ has ` p -robust classification risk at most exp ( − (〈ŵ,θ ∗〉− ‖ŵ‖∗p) 2
2σ2
) .
Our theoretical findings suggest that we can improve the adversarially robust generalization using unlabeled data. In the next section, we will present a practical algorithm for real applications, which further verifies our main results.
Algorithm 1 Generalized Virtual Adversarial Training over labeled and unlabeled data 1: Input: Datasets SL and SU . Hypothesis space F . Coefficient λ. PGD step size δ. Number of
PGD steps k. Maximum l∞ norm of perturbation . 2: for each iteration do 3: Sample a mini-batch of labeled data ŜL from SL. 4: Sample a mini-batch of unlabeled data ŜU from SU . 5: for each x ∈ ŜL ∪ ŜU do 6: Fix f and attack x with PGD-(k, , δ) on loss L1/L2 to obtain x′. 7: Perform gradient descent on f over the perturbed samples on loss LSSL. 8: end for 9: end for

heading: 4 ALGORITHM AND EXPERIMENTS

heading: 4.1 PRACTICAL ALGORITHM

text:
Let SL = {(xL1 , yL1 ), · · · , (xLn , yLn )} be a set of labeled data and SU = {xU1 , · · · , xUm} be a set of unlabeled data. Motivated by the theory in the previous section, to achieve better adversarially robust generalization, we can optimize the classifier to be accurate on SL and robust on SL ∪ SU . This is also equivalent to making the classifier accurate and robust on SL and robust on SU . Therefore, we design two loss terms on SL and SU separately.
For the labeled dataset SL, we use the standard ` ∞-robust adversarial training objective function, i.e.,
L1(f, S L) =
1
n n∑ i=1 max x′i∈B ∞(xi) lCE(f(x′i), yi). (6)
Following the most common setting, during training, the classifier outputs a probability distribution over categories and is evaluated by cross-entropy loss defined as
lCE(f(x), y) = − K∑ k=1 log fk(x)I[y = k] (7)
where fk(x) is the output probability for category k.
For unlabeled data SU , we use an objective function which measures robustness without ground truth
L2(f, S U ) =
1
m m∑ i=1 max x′i∈B ∞(xi) lCE(f(x′i), ŷi),where ŷi = arg max k {fk(xi)}. (8)
Putting the two objective functions together, our training loss is defined as a combination of L1 and L2 as follows:
LSSL(f, SL, SU ) = L1(f, S L) + λL2(f, S U ). (9)
Here λ > 0 is a coefficient to trade off the two loss terms. In real practice, we use iterative optimization methods to learn the function f . In the inner loop, we fix the model and use Projected Gradient Descent (PGD) to learn the attack x′ for any x. In the outer loop, we use stochastic gradient descent to optimize f on the perturbed x′s. The general training process is shown in Algorithm 1.
Remark We notice that Algorithm 1 is a generalized version of Virtual Adversarial Training (VAT) (Miyato et al., 2018). When setting the PGD step k = 1, the algorithm is almost equivalent to the original VAT algorithm, which is particular useful for improving standard generalization. However, according to our experimental results below, setting k = 1 does not help improve adversarial robust generalization. The improvement of adversarial robust generalization using unlabeled data exists when setting a relatively larger k.

heading: 4.2 EXPERIMENTAL SETTING

text:
We verify Algorithm 1 on MNIST and Cifar-10. Following Madry et al. (2017), we use the Resnet model and modify the network incorporating wider layers by a factor of 10. This results in a network with five residual units with (16, 160, 320, 640) filters each. During training, we apply data augmentation including random crops and flips, as well as per image standardization. The initial learning rate is 0.1, and decay by a factor of 10 twice during training. In the inner loop, we run a 7-step PGD with step size 2255 for each mini-batch. The perturbation is constrained to be 8 255 under l∞ norm.
Following many previous works (Laine & Aila, 2016; Tarvainen & Valpola, 2017; Miyato et al., 2018; Athiwaratkun et al., 2019), we sample 5k/10k labeled data from the training set and use them as labeled data. We mask out the labels of the remaining images in the training set and use them as unlabeled data. By doing this, we conduct two semi-supervised learning tasks and call them the 5k/10k experiments. In a mini-batch, we sample 25/50 labeled images and 225/200 unlabeled images for the 5k/10k experiment respectively. In both experiments, we use several different values of λ as an ablation study for this hyperparameter by setting λ = 0.1, 0.2, 0.3. Learning rate is decayed at the 60th and the 120th epoch. We use the original PGD-based adversarial training (Madry et al., 2017) on the sampled 5k/10k labeled data as the baseline algorithm for comparison (referred to as PGD-adv). Our algorithm is referred to as Ours.

heading: 4.3 EXPERIMENTAL RESULTS

text:
We list all results of the 5k/10k experiments in Tables 1 and 2. We use five criteria to evaluate the performance of the model: the natural training/test accuracy (NAtrain and NAtest), the robust training/test accuracy using PGD-7 attack (RAtrain and RAtest) and the defense success rate (DSR).
First, we can see that in both experiments, the robust test accuracy is improved when we use unlabeled data. For example, on Cifar-10 the robust test accuracy of the models trained under SSL with λ = 0.3 for the 5k/10k experiments increase by 3.0/5.0 percents compared to the PGD-adv baselines. We also check the defense success rate which evaluates whether the model is robust given
the prediction is correct. As we can see from the last column in Tables 1 and 2, the defense success rate of models trained using our proposed method is much higher than the baselines. In particular, the defense success rate of the model trained with λ = 0.3 in the 10k experiment is competitive to the model trained using PGD-adv on the whole dataset. This clearly shows the advantage of our proposed algorithm.
Second, we can also see the influence of the value of λ. The model trained with a larger λ has higher robust accuracy. For example, in the 10k experiment, the robust test accuracy of the model trained with λ = 0.3 is more than 3% better than that with λ = 0.1. However, we observe that training will become hard to converge if λ > 0.5.
Third, using larger k produces more robust models. As we can see from the table, in the 5k/10k experiment, relatively higher natural training/test accuracy can be achieved by setting k = 1 (vanilla VAT algorithm). However, the robust training/testing accuracy are significantly worse and are near zero. This clearly shows that using a stronger attack on both labeled and unlabeled data leads to better adversarially robust generalization, which is also consistent with our theory.

heading: 5 CONCLUSION

text: In this paper, we theoretically and empirically show that with just more unlabeled data, we can learn models with better adversarially robust generalization. We first give an expected robust risk decomposition theorem and then show that for a specific learning problem on the Gaussian mixture model, the adversarially robust generalization can be almost as easy as standard generalization. Based on these theoretical results, we develop an algorithm which leverages unlabeled data during training and empirically show its advantage. As future work, we will study the sample complexity of unlabeled data for broader function classes and solve more challenging real tasks.

heading: A BACKGROUND ON GENERALIZATION AND RADEMACHER COMPLEXITY

text:
The Rademacher complexity is a commonly used capacity measure for a hypothesis space. Definition 4. Given a set S = {x1, ..., xn} of n samples, the empirical Rademacher complexity of function class F (mapping from Rd to R) is defined as:
RadS(F) = 1
n E [ sup f∈F n∑ i=1 if(xi) ] , (10)
where = ( 1, · · · , n)> contains i.i.d. random variables drawn from the Rademacher distribution unif({1, -1}).
By using the Rademacher complexity, we can directly provide an upper bound on the generalization error. Theorem 5. (Theorem 3.5 in Mohri et al. (2012)). Suppose l(·, ·) is the 0−1 loss, let S = (xi, yi)ni=1 be the set of n i.i.d. samples drawn from the underlining distribution PXY . Let F be the hypothesis space, then with probability at least 1− δ over S, for any f ∈ F:
R(f) ≤ R̂(f) +RadS(F) + 3 √ log 2δ 2n
(11)

heading: B PROOF OF THEOREM 1

text:
Proof. For indicator function I, we have for any x, I(f(x′) 6= y) ≤ I(f(x) 6= y) + I(f(x) 6= f(x′)). (12)
According to Definition 2, we have RB−robust(f) = E(x,y)∼PXY sup
x′∈B(x) l(f(x′), y) = E(x,y)∼PXY sup x′∈B(x) I(f(x′) 6= y)
≤ E(x,y)∼PXY sup x′∈B(x)
(I(f(x) 6= y) + I(f(x) 6= f(x′))) (13)
= Ex∼PX sup x′∈B(x) (I(f(x′) 6= f(x)) + E(x,y)∼PXY l(f(x), y)
= Ex∼PX sup x′∈B(x)
(I(f(x′) 6= f(x)) +R(f),
where (13) is derived from (12). We further use Theorem 5 to bound R(f). It is easy to verify that with probability at least 1− δ, for any f ∈ F :
RB−robust(f) ≤ Ex∼PX sup x′∈B(x)
(I(f(x′) 6= f(x)) +R(f)
≤ Ex∼PX sup x′∈B(x) (I(f(x′) 6= f(x)) + R̂(f) +RadS(F) + 3 √ log 2δ 2n
which completes the proof.

heading: C PROOF OF THEOREM 4

text:
For convenience, in this section, we use ci or c′i to denote some universal constants, where i = 0, 1, 2, 3, 4.
In the proof of Theorem 4, we will use the concentration bound for covariance estimation in Wainwright (2019). We first introduce the definition of spiked covariance ensemble. Definition 5. (Spiked covariance ensemble). A sample xi ∈ Rd from the spiked covariance ensemble takes the form
xi = √ νξiθ0 + wi, (14)
where ξi ∈ R is a zero-mean random variable with unit variance, ν ∈ R is a fixed scalar, θ0 ∈ Rd is a fixed unit vector andwi ∈ Rd is a random vector independent of ξi, with zero mean and covariance matrix Id.
To see why spiked covariance ensemble model is useful, we note that the Gaussian mixture model is its special case. Specifically, let xUi ’s be the unlabeled data in Theorem 4. Then x U i follows the Gaussian mixture distribution 12N (θ ∗, σ2Id) + 1 2N (−θ ∗, σ2Id), and xUi σ is a spiked covariance ensemble with parameter ν = dσ2 , ξi uniformly distributed on {±1}, wi ∼ N (0, Id) and θ0 = θ∗√ d .
The following theorem from Wainwright (2019) characterizes the concentration property of spiked covariance ensemble, which we will further use to bound the robust classification error. Intuitively, the theorem says that we can approximately recover θ0 in the spiked covariance ensemble model using the top eigenvector θ̂ of the sample covariance matrix Σ̂. Theorem 6. (Concentration of covariance estimation, see Corollary 8.7 in Wainwright (2019)). Given i.i.d. samples {xi}ni=1 from the spiked covariance ensemble with sub-Gaussian tails (which means both ξi and wi are sub-Gaussian with parameter at most one), suppose that n > d and√
ν+1 ν2 √ d n < 1 128 . Then, with probability at least 1 − c1e −c2nmin{ √ νc3,νc 2 3}, there is a unique
maximal eigenvector θ̂ of the sample covariance matrix Σ̂ = 1n ∑n i=1 xix
> i such that∥∥∥θ̂ − θ0∥∥∥
2 ≤ c0
√ ν + 1
ν2
√ d
n + c3. (15)
Using the theorem above, we can show that for the Gaussian mixture model, one of the top unit eigenvector of the sample covariance matrix is approximately θ
∗ √ d . In other words, we can approxi-
mately recover the parameter θ∗ up to a sign difference: the principal component analysis of Σ̂ gives either v or −v, while θ
∗ √ d is close to v. Lemma 4. Under the same setting as Theorem 4, suppose that n > d and σ √
σ2+d nd < 1 128 . Then,
with probability at least 1− c1e−c2nmin{ √ dc3 σ ,( √ dc3 σ )
2}, there is a unique maximal eigenvector v of the sample covariance matrix Σ̂ = 1n ∑n i=1 x U i x
U> i with unit `2 norm such that∥∥∥∥v − θ∗√d ∥∥∥∥ 2 ≤ τ0 = min{c0σ √ σ2 + d nd + c3, √ 2} (16)
Proof. As discussed above, x U i
σ is a spiked covariance ensemble. By Theorem 6 we have with
probability at least 1 − c1e−c2nmin{ √ dc3 σ ,( √ dc3 σ )
2}, there is a unique maximal eigenvector ṽ of the sample covariance matrix Σ̂ = 1n ∑n i=1 x U i x
U> i such that∥∥∥∥ṽ − θ∗√d ∥∥∥∥ 2 ≤ c′0σ √ σ2 + d nd + c′3. (17)
Let τ = c′0σ √ σ2+d nd + c ′ 3, we have ∥∥∥ṽ − θ∗√ d ∥∥∥ 2 ≤ τ . Below we need to consider two cases, τ ≤ 1 and τ > 1.
Case 1: τ ≤ 1. Let v = ṽ‖ṽ‖ , since both v and θ∗√ d
are unit vectors, we have∥∥∥∥v − θ∗√d ∥∥∥∥2 = ‖v‖2 + ∥∥∥∥ θ∗√d ∥∥∥∥2 − 2〈v, θ∗√d 〉 = 2− 2〈v, θ∗√d 〉 (18) Recall that ∥∥∥ṽ − θ∗√ d ∥∥∥ 2 ≤ τ , which is equivalent to
τ2 ≥ ‖ṽ‖2 + ∥∥∥∥ θ∗√d ∥∥∥∥2 − 2〈ṽ, θ∗√d 〉 = ‖ṽ‖2 + 1− 2 ‖ṽ‖ 〈v, θ
∗ √ d 〉
Rearranging the terms and using AM-GM inequality gives
2〈v, θ ∗ √ d 〉 ≥ ‖v‖+ 1− τ 2 ‖v‖ ≥ 2 √ 1− τ2 (19)
Therefore, by equation 18, ∥∥∥∥v − θ∗√d ∥∥∥∥ = √ 2− 2〈v, θ ∗ √ d 〉
≤ √ 2− 2 √ 1− τ2
=
√ 2τ2
1 + √ 1− τ2
≤ √ 2τ
= √
2(c′0σ
√ σ2 + d
nd + c′3).
By substituting c0 = √ 2c′0, c2 = 1 2c ′ 2 and c3 = √ 2c′3, we complete the proof.
Case 2: τ > 1. Let v be one of ± ṽ‖ṽ‖ such that the the inner product 〈v, θ ∗〉 is nonnegative. Since both v and θ ∗ √ d
are unit vectors, we have∥∥∥∥v − θ∗√d ∥∥∥∥2 = ‖v‖2 + ∥∥∥∥ θ∗√d ∥∥∥∥2 − 2〈v, θ∗√d 〉 = 2− 2√d 〈v, θ∗〉 ≤ 2 (20) Therefore, ∥∥∥v − θ∗√ d
∥∥∥ ≤ √2 = τ0. Now we have proved that by using the top eigenvector of Σ̂, we can recover the θ∗ up to a sign difference. Next, we will show that it is possible to determine the sign using the labeled data. Lemma 5. Under the same setting as Theorem 4, suppose v ∈ Rd is a unit vector such that∥∥∥v − θ∗√ d ∥∥∥ 2 ≤ τ0 where τ0 ≤ √ 2. Then with probability at least 1 − exp ( −d(1− τ20 2 ) 2 2σ2 ) , we have sign(yL · v>xL)v>θ∗ > 0. Proof. Since ∥∥∥v − θ∗√
d ∥∥∥ 2 ≤ √ 2, and both v and θ ∗ √ d are unit vectors, we have v>θ∗ > 0. So the
event {sign(yL · v>xL)v>θ∗ ≤ 0} is equivalent to the event {yL · v>xL ≤ 0}, i.e.
P[sign(yL · v>xL)v>θ∗ ≤ 0] = P[yL · v>xL ≤ 0] (21)
Recall that xL is sampled from the Gaussian distribution N (yL · θ∗, σ2Id), where yL is sampled uniformly at random from {±1}, we have (yLxL) follows the Gaussian distribution N (θ∗, σ2Id). Hence,
P[yL · v>xL ≤ 0] = P(yLxL)∼N (θ∗,σ2Id)[v >(yLxL) ≤ 0] = Pg∼N (0,1)
[ g ≤ −θ
∗ · v σ
] (22)
Moreover, from ∥∥∥v − θ∗√
d ∥∥∥2 2 ≤ τ20 we can get
〈θ∗, v〉 ≥ √ d(1− τ 2 0
2 ) (23)
So, using the Gaussian tail bound PX∼N (0,1)[X ≤ −t] ≤ exp(−t2) for all t ∈ R, and combining with equation 21, equation 22, equation 23, we have
P[sign(yL · v>xL)v>θ∗ ≤ 0] ≤ exp ( − d(1− τ 2 0 2 ) 2
2σ2
) , (24)
as stated in the lemma.
Armed with Lemma 4 and Lemma 5, we now have a precise estimation of θ∗ in the Gaussian mixture model. Then, we will show that the high precision of the estimation can be translated to low robust risk. To achieve this, we need a lemma from Schmidt et al. (2018), which upper bounds the robust classification risk of a linear classifier ŵ in terms of its inner product with θ∗. Lemma 6. (Lemma 20 in Schmidt et al. (2018)). Under the same setting as in Theorem 4, for any p ≥ 1 and ≥ 0, and for any unit vector ŵ ∈ Rd such that 〈ŵ, θ?〉 ≥ ‖ŵ‖∗p , where ‖ · ‖∗p is the dual norm of ‖ · ‖p, the linear classifier fŵ has ` p -robust classification risk at most
exp ( − (〈ŵ,θ ∗〉− ‖ŵ‖∗p) 2
2σ2
) .
Lemma 6 guarantees that if we can estimate θ? precisely, we can achieve small robust classification risk. Combine with Lemma 4 and Lemma 5 which provide such estimation, we are now ready to prove the robust classification risk bound stated in Theorem 4. We can actually prove a slightly more general theorem below with some extra parameters, and obtain Theorem 4 as a corollary. Theorem 7. Let (xL, yL) be a labeled data drawn from (θ∗, σ)-Gaussian mixture model PXY with ‖θ∗‖2 = √ d. Let xU1 , · · · , xUn be n unlabeled data drawn from PX . Let τ0 be as stated in Lemma 4, and v ∈ Rd be the normalized eigenvector (i.e. ‖v‖2 = 1) with respect to the maximal eigenvalue of ∑n i=1 x U i x U> i such that ∥∥∥v − θ∗√ d ∥∥∥ 2 ≤ τ0 with probability at least 1 − c1e−c2nmin{ √ dc3 σ ,( √ dc3 σ ) 2}. Let ŵ = sign(yL · v>xL)v. Then with probability at least 1 − c1e−c2nmin{ √ dc3 σ ,( √ dc3 σ ) 2} − exp(−d(1− τ20 2 ) 2
2σ2 ), the linear classifier fŵ has ` ∞-robust classi-
fication risk at most β when
≤ 1− τ 2 0 2 − σ √ 2 log 1β √ d . (25)
Proof. By the choice of v we have equation 23 holds, i.e.
〈θ∗, v〉 ≥ √ d(1− τ 2 0
2 ), (26)
with probability at least 1− c1e−c2nmin{ √ dc3 σ ,( √ dc3 σ ) 2}.
Applying Lemma 5 to v yields sign(yL · v>xL)v>θ∗ > 0, (27)
with probability at least 1− exp(−d(1− τ20 2 ) 2
2σ2 ).
Notice that ŵ = sign(yL · v>xL)v. So by union bound on events equation 26 and equation 27, we have
〈θ∗, ŵ〉 = sign(yL · v>xL)〈θ∗, v〉 ≥ √ d(1− τ 2 0
2 ), (28)
with probability at least 1− c1e−c2nmin{ √ dc3 σ ,( √ dc3 σ ) 2} − exp(−d(1− τ20 2 ) 2
2σ2 ).
Since ‖ŵ‖2 = 1, we have ‖ŵ‖∗∞ = ‖ŵ‖1 ≤ √ d. (29)
By Lemma 6, we have the ` ∞-robust error is upper bounded by
RB−robust(fŵ) ≤ exp ( − (〈ŵ, θ ∗〉 − ‖ŵ‖∗∞) 2
2σ2
) . (30)
Combining this with equation 28, equation 29 and the assumption equation 25, we have
〈ŵ, θ∗〉 − ‖ŵ‖∗∞ ≥ √ d(1− τ 2 0 2 )− √ d 1− τ20 2 − σ √ 2 log 1β √ d  = σ√2 log 1 β . (31)
Hence,
RB−robust(fŵ) ≤ exp − ( σ √ 2 log 1β )2 2σ2  = β, (32) with probability at least 1−c1e−c2nmin{ c3 σ ,( c3 σ ) 2}−exp(−d(1− τ20 2 ) 2
2σ2 ), as stated in the theorem.
Now we are ready to prove Theorem 4.
Proof of Theorem 4: Let c be a constant such that σ ≤ c · d1/4 for sufficiently large d. Notice that the ŵ in Theorem 4 is same as the ŵ in Theorem 7 since the maximal eigenvector of ∑n i=1 x U i x U> i
also maximizes ∑n i=1(v >xUi ) 2 over the unit sphere ‖v‖ = 1, v ∈ Rd. Theorem 7 guarantees that with probability at least 1− c1e−c2nmin{ √ dc3 σ ,( √ dc3 σ ) 2}− exp(−d(1− τ20 2 ) 2
2σ2 ), ` ∞-robust classification
risk is less then β = 0.01 for
≤ 1− τ 2 0 2 − σ √ 2 log 1β √ d
= 1− τ 2 0 2 − c √ 2 log 1β d1/4 .
Choose c3 to be 12 . Since n = Ω(d), 1 2 ≤ τ0 = c0σ √ σ2+d nd + c3 ≤ c4 d1/4 + 12 , and consequently
τ20 ≤ 14+ c4 d1/4 + c24√ d . So by Theorem 7, with probability at least 1−c1 exp ( −c′2d7/4 ) −exp ( −c √ d )
, ` ∞-robust classification risk is less then β = 0.01 for
≤ 1− τ 2 0 2 − c √ 2 log 1β d1/4
≤ 3 4 − c √ 2 log 1β d1/4 .
Since c4, c are numerical constants, there exists a constant D such that when d ≥ D, ` ∞-robust classification risk is less then β = 0.01 for ≤ 12 , thus we have completed the proof.

title: ADVERSARIALLY ROBUST GENERALIZATION JUST REQUIRES MORE UNLABELED DATA


summaries: The paper studies the problem of advantage estimation for actor-critic RL algorithms. The key observation is that the advantage can be computed using 1-step returns, 2-step returns, etc. The paper suggests that, instead of choosing a fixed n, we should aggregate these advantageous together. If the maximum is taken, the resulting policy will be exploratory (i.e., have a "promotion focus"); if the minimum advantage is taken, the resulting policy will be risk sensitive (i.e., have a "regulatory focus").

summaries: This paper focuses on risk-aware reinforcement learning, where an agent could be encouraged to take more risk (high reward, high variance states) or avoid risk (low variance states). Risk control is instantiated by different ways of estimating the advantage of a state (max/min instead of average). Experiments on several environments show good performance of the proposed algorithm.

summaries: This paper presents a modification to policy gradient methods that are computed from advantage function estimates. For a given trajectory of n steps, there are n different advantage function estimates: from 1-step to n-step. GAE (Schulman, 2016) proposes to take an exponentially weighted average of these estimates to compute the policy gradients. This paper proposes instead to use order statistics to compute the policy gradient; e.g. the most optimistic estimate, the most pessimistic estimate, or the most extreme estimate.  The paper introduces a regulatory ratio: the probability of using the averaged advantage estimate vs using the order statistic, for computing the policy gradients. This hyper-parameter is justified on the optimistic case (max advantage), as a way to prevent overtly optimistic estimates. The paper conducts experiments on  different domains (sparse and dense rewards, discrete and continuous actions, fully observable and partially observable environments) which show the effect of choosing different order statistics and regulatory ratio on the policy performance.

abstractText: The estimation of advantage is crucial for a number of reinforcement learning algorithms, as it directly influences the choices of future paths. In this work, we propose a family of estimates based on the order statistics over the path ensemble, which allows one to flexibly drive the learning process in a promotion focus or prevention focus. On top of this formulation, we systematically study the impacts of different regulatory focuses. Our findings reveal that regulatory focus, when chosen appropriately, can result in significant benefits. In particular, for the environments with sparse rewards, promotion focus would lead to more efficient exploration of the policy space; while for those where individual actions can have critical impacts, prevention focus is preferable. On various benchmarks, including MuJoCo continuous control, Terrain locomotion, Atari games, and sparse-reward environments, the proposed schemes consistently demonstrate improvement over mainstream methods, not only accelerating the learning process but also obtaining substantial performance gains.

title: An introduction to motivation

authors:
Gabriel Barth-Maron
Matthew W Hoffman
David Budden
Will Dabney
Dan Horgan
Alistair Muldal
Nicolas Heess
Timothy Lillicrap

title: Distributed distributional deterministic policy gradients

venue: arXiv preprint arXiv:1804.08617,

authors:
M.G. Bellemare
Y. Naddaf
J. Veness
M. Bowling

title: The arcade learning environment: An evaluation platform for general agents

venue: Journal of Artificial Intelligence Research,

authors:
Marc G Bellemare
Will Dabney
Rémi Munos

title: A distributional perspective on reinforcement learning

venue: In Proceedings of the 34th International Conference on Machine Learning-Volume

authors:
Yinlam Chow
Mohammad Ghavamzadeh

title: Algorithms for cvar optimization in mdps

venue: In Advances in neural information processing systems,

authors:
Yinlam Chow
Aviv Tamar
Shie Mannor
Marco Pavone

title: Risk-sensitive and robust decisionmaking: a cvar optimization approach

authors:
Ellen Crowe
E Tory Higgins

title: Regulatory focus and strategic inclinations: Promotion and prevention in decision-making

venue: Organizational behavior and human decision processes,

authors:
Will Dabney
Georg Ostrovski
David Silver
Remi Munos

title: Implicit quantile networks for distributional reinforcement learning

venue: In International Conference on Machine Learning,

authors:
Erick Delage
Shie Mannor

title: Percentile optimization in uncertain markov decision processes with application to efficient exploration

venue: In Proceedings of the 24th international conference on Machine learning,

title: Percentile optimization for markov decision processes with parameter uncertainty

venue: Operations research,

authors:
Justin Fu
John Co-Reyes
Sergey Levine

title: Ex2: Exploration with exemplar models for deep reinforcement learning

authors:
Scott Fujimoto
Herke van Hoof
David Meger

title: Addressing function approximation error in actor-critic methods

venue: arXiv preprint arXiv:1802.09477,

title: Précis of the neuropsychology of anxiety: An enquiry into the functions of the septo-hippocampal system

venue: Behavioral and Brain Sciences,

authors:
Nicolas Heess
Srinivasan Sriram
Jay Lemmon
Josh Merel
Greg Wayne
Yuval Tassa
Tom Erez
Ziyu Wang
SM Eslami
Martin Riedmiller

title: Emergence of locomotion behaviours in rich environments

venue: arXiv preprint arXiv:1707.02286,

title: Beyond pleasure and pain

venue: American psychologist,

title: Making a good decision: value from fit

authors:
E Tory Higgins
Lorraine Chen Idson
Antonio L Freitas
Scott Spiegel
Daniel C Molden

title: Transfer of value from fit

venue: Journal of personality and social psychology,

authors:
Ronald A Howard
James E Matheson

title: Risk-sensitive markov decision processes

venue: Management science,

authors:
Angela Y Lee
Jennifer L Aaker

title: Bringing the frame into focus: the influence of regulatory fit on processing fluency and persuasion

authors:
Shie Mannor
Ofir Mebel
Huan Xu

title: Lightning does not strike twice: robust mdps with coupled uncertainty

venue: In Proceedings of the 29th International Coference on International Conference on Machine Learning,

authors:
Volodymyr Mnih
Adria Puigdomenech Badia
Mehdi Mirza
Alex Graves
Timothy Lillicrap
Tim Harley
David Silver
Koray Kavukcuoglu

title: Asynchronous methods for deep reinforcement learning

venue: In International conference on machine learning,

authors:
Tetsuro Morimura
Masashi Sugiyama
Hisashi Kashima
Hirotaka Hachiya
Toshiyuki Tanaka

title: Nonparametric return distribution approximation for reinforcement learning

venue: In Proceedings of the 27th International Conference on Machine Learning

authors:
Arnab Nilim
Laurent El Ghaoui

title: Robustness in markov decision problems with uncertain transition matrices

title: Policy gradients for cvar-constrained mdps

venue: In International Conference on Algorithmic Learning Theory,

authors:
LA Prashanth
Mohammad Ghavamzadeh

title: Actor-critic algorithms for risk-sensitive mdps

authors:
John Schulman
Sergey Levine
Pieter Abbeel
Michael Jordan
Philipp Moritz

title: Trust region policy optimization

authors:
John Schulman
Philipp Moritz
Sergey Levine
Michael Jordan
Pieter Abbeel

title: High-dimensional continuous control using generalized advantage estimation

venue: arXiv preprint arXiv:1506.02438,

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

authors:
Harm Seijen
Rich Sutton

title: True online td (lambda)

authors:
Elena Smirnova
Elvis Dohmatob
Jérémie Mary

title: Distributionally robust reinforcement learning

venue: arXiv preprint arXiv:1902.08708,

authors:
Richard S Sutton
Andrew G Barto

title: Reinforcement learning: An introduction

authors:
Aviv Tamar
Dotan Di Castro
Shie Mannor

title: Policy gradients with variance related risk criteria

authors:
Aviv Tamar
Yonatan Glassner
Shie Mannor

title: Optimizing the cvar via sampling

venue: In Twenty-Ninth AAAI Conference on Artificial Intelligence,

title: Reinforcement Learning in Continuous State and Action Spaces, pp. 207–251

authors:
Hado Van Hasselt
Marco A Wiering

title: Reinforcement learning in continuous action spaces

venue: IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning,

authors:
Oriol Vinyals
Timo Ewalds
Sergey Bartunov
Petko Georgiev
Alexander Sasha Vezhnevets
Michelle Yeo
Alireza Makhzani
Heinrich Küttler
John Agapiou
Julian Schrittwieser

title: Starcraft ii: A new challenge for reinforcement learning

venue: arXiv preprint arXiv:1708.04782,

title: Learning from delayed rewards

authors:
Huan Xu
Shie Mannor

title: The robustness-performance tradeoff in markov decision processes

heading: 1 INTRODUCTION

text:
It is not enough to do good; one must do it the right way.
The best-known motivational principle that has been recognized in psychology (Gray, 1982; Atkinson, 1964) is the hedonic principle that people approach pleasure and avoid pain. However the principle does not explain how people approach and avoid. Higgins (1997) proposes the regulatory focus theory to address this question. A promotion focus is concerned with advancement, growth, and accomplishment, and a prevention focus is concerned with security, safety, and responsibility (Crowe & Higgins, 1997). The theory hypothesized that the promotion focus inclination insures against errors of omission, and the prevention focus inclination insures against errors of commission. Furthermore, the regulatory fit theory (Higgins, 2000; Higgins et al., 2003) proposes that when people pursue a goal in a manner that fit their regulatory orientation, they are stronger motivated during goal pursuit. For example, Lee & Aaker (2004) showed that ads are more persuasive if there is a regulatory fit: use gain frames (e.g. “great looks and exceptional engineering”) for individuals who are eager to approach positive outcomes, and use loss frames (e.g. “don’t be stranded with a disabled vehicle without an emergency safety kit”) for individuals who are vigilant to avoid negative outcomes.
We study the phenomenon of regulatory fit in the context of reinforcement learning (RL). Be aware that humans own real emotions and are fundamentally more complex than RL agents, thus we borrow terminologies in psychology while trying to retain the resemblance. We hypothesize that different RL environments are more fit with agents of different regulatory focus. For example, in the environments with sparse rewards, it might be advisable to actively exploring those policies that show potentials without being discouraged by a few failed trials; while in the environments that are fragile, e.g. those where a wrong choice of action can lead to catastrophic consequences down the path, a more conservative, risk-averse stance might be preferable. There are three questions need to answer: (1) How to automatically determine the suitable regulatory focus for an environment; (2) How to train an agent with a specified regulatory focus; (3) Is there any benefit when training the agent with the regulatory focus that fits the environment? In this article, we aim to answer the second and third questions and leave the first question open.
The research on deep reinforcement learning is gaining momentum in recent years. A number of learning methods, such as Proximal Policy Optimization algorithm (PPO) (Schulman et al., 2017),
Trust-Region Policy Optimization algorithm (TRPO) (Schulman et al., 2015a), and Advantage ActorCritic algorithm (A2C) (Mnih et al., 2016), have been developed. These methods and their variants have achieved great success in challenging problems, e.g. continuous control (Schulman et al., 2015b), locomotion (Heess et al., 2017), and video games (Vinyals et al., 2017). The core of all these methods is the estimation of the advantage A(st, at), i.e. the gain in the expected cumulative reward relative to the state value V (st) if a certain action at is taken. A common practice is to use the n-step estimate over the sampled trajectories. This way has been widely used in actor-critic algorithms such as the A2C. Schulman et al. presents a generalization called Generalized Advantage Estimator (GAE) (Schulman et al., 2015b), which blends 1 to n-step estimators with exponentially decayed weights, thus reducing the variance of policy gradients. For convenience, we refer to the set of 1 to n-step estimators along a trajectory as the path ensemble.
We propose to take the maximum over path ensemble to implement the promotion focus inclination, and take the minimum over path ensemble to implement to prevention inclination during training. Intuitively, when taking the maximum or minimum, the agent is comparing a list of counterfactual speculations. When it looks at a k-step estimation where k ≤ n, it is thinking what if it didn’t took those actions after step k? For a promotion focus, in order to insure hits and insure against omission, it would favor the estimation with largest value because it has the possibility of being that good. Similarly, for a prevention focus, it prefers the minimum to insure against errors of commission.
We systematically studied different estimation schemes on various environments, including the sparse-reward environments (Fu et al., 2017), the Terrain RL Simulator (Berseth et al., 2018) for biped locomotion, the Atari games (Bellemare et al., 2013), and the set of MuJoCo environments for continuous control (Brockman et al., 2016). Our study shows that the proposed estimation strategies, when chosen appropriately, can substantially outperform the standard way. In particular, the promotion focus inclination, i.e. taking the maximum over path ensemble, greatly improves the learning efficiency in the environments with sparse rewards. On the other hand, the prevention focus inclination, i.e. taking the minimum, can effectively stabilize the learning by avoiding risky actions.
It is noteworthy that the proposed strategic inclinations differ essentially from the recent two lines of work on robustness (Smirnova et al., 2019; Delage & Mannor, 2007) and risk-sensitivity (Tamar et al., 2012; Chow & Ghavamzadeh, 2014). Robust MDP optimizes for the worst case when there exist uncertainties in the parameters; risk-sensitive MDP optimizes the value of a risk measure. Our method does not modify the training objective. Instead, it controls the policy gradient towards policies with promotion or prevention inclinations through the alternative ways of estimating the advantage.

heading: 2 RELATED WORK

text:
Estimation of Advantage and Action-Value The n-step advantage estimation is derived from the n-step return, which is used in the n-step TD or the n-step Sarsa method (Sutton & Barto, 2011). Similarly, the generalized advantage estimator (Schulman et al., 2015b) is analogous to the λ-return (Watkins, 1989) in the TD(λ) method (Seijen & Sutton, 2014). They are all linear combinations over the path ensemble. A nonlinear combination scheme is seen in the work of Twin Delayed DDPG (TD3) (Fujimoto et al., 2018), which uses the min of two critics to estimate Q. However, it aims to mitigate the overestimation problem in deep Q-learning, and the objects be combined are the network outputs instead of the estimators based on the cumulative rewards. Another nonlinear combination is the Positive Temporal Difference (PTD) (Van Hasselt & Wiering, 2007; van Hasselt, 2012), where the advantage is set as 1 when the 1-step estimate of advantage is positive, and is set to 0 otherwise. The benefit of limiting policy updates only toward those actions that have positive advantages is increasing the stability of learning.
Robustness and Risk-Sensitivity in RL In the assumption of robust MDPs (Nilim & El Ghaoui, 2004; Xu & Mannor, 2007; Delage & Mannor, 2010; Mannor et al., 2012; Smirnova et al., 2019), the parameters of the problem lie in an uncertainty set, and the target is to find a solution that performs best under the worst cases. On the other hand, risk-sensitive MDPs consider the uncertainty of the rewards. The objective is to minimize the risk-measure, which is defined by the exponential utility (Howard & Matheson, 1972), the Conditional Value-at-Risk (CVaR) (Chow & Ghavamzadeh, 2014; Prashanth, 2014; Chow et al., 2015; Tamar et al., 2015), the percentile (Delage & Mannor, 2007) or the variance (Tamar et al., 2012; Prashanth & Ghavamzadeh, 2013) of the cumulative
rewards. The statistics over the path ensemble is not the same as those statistics for advantage. However, using a suitable nonlinear combination of the numbers in the path ensemble, the exploration strategy in our algorithms can bias the learning toward risk-averse or risk-seeking policies. Unlike the robust and risk-sensitive approaches, which typically introduce involved computations, our approach is straightforward to implement and requires minimal changes to incorporate the idea into existing algorithms such as A2C, PPO, TRPO and their variants.
Distributional RL The value distribution is the object of study in distributional RL. Since the full distribution of return is difficult to estimate, researchers have adopted nonparametric methods (Morimura et al., 2010) or used simple distributions (Bellemare et al., 2017; Dabney et al., 2018; Barth-Maron et al., 2018) to approximate it. The RL algorithms can be formulated with any criterion based on the distribution of return, such as the aforementioned risk-sensitivity measures. Again, the distribution formed by elements in the path ensemble does not represent the full distribution of return, but some joint distribution that we can exploit.

heading: 3 REGULATORY FOCUS BY ORDER STATISTICS OVER PATH ENSEMBLE

text: In this section, we first review the preliminary knowledge on RL. Then we introduce the central concept of this article: regulatory focus implemented by estimators over path ensembles. Specifically, we focus on the family of order statistics. Next, we give an illustrative study on the max statistics over the path ensemble, where we show that the induced estimator of action-values would influence the optimization process of RL algorithms. With this specific example in mind, we give a practical algorithm to incorporate the general estimators into existing RL algorithms in the last section.

heading: 3.1 PRELIMINARY

text:
We consider the standard formulation of RL, which is typically modeled as an MDP (S,A, T , γ, R), where S is the state space, A is the action space, T = {Psa(·) | s ∈ S, a ∈ A} is the transition probabilities, γ ∈ (0, 1] is the discount factor, and R is the reward function. At timestep t, the agent in state st interacts with the environment by choosing an action at ∼ π(st) following the policy π, and receives a reward Rt from the environment. The environment then transits to the next state st+1. The discounted return is defined as Gt := ∑T−1 i=t γ
i−tRi, and the goal of RL is to maximize the expected return J = Es0∼S0 [G0 | s0], where S0 is the distribution of initial states. The action-value function Qπ(st, at) := E [Gt | st, at] under a policy π is the expected return of taking action at ∼ π(st) in state st. In policy-based model-free deep RL algorithms, policy πθ with parameters θ is optimized via gradient ascent. An estimation of the gradient is the policy gradient
∇θJ(θ) = Eτ∼πθ(τ) [ T∑ t=0 ∇θπθ(at | st) πθ(at | st) A(st, at) ] , (1)
where τ = {s0, a0, s1, a1, . . . , sT , aT } is a trajectory following the policy. A(st, at) := Q(st, at)− V (st) is the advantage function. The n-step look ahead estimation of advantage function is given by
Â (n) t := n−1∑ i=0 ( γirt+i ) + γnV (st+n)− V (st), n = 1, 2, . . . , T − t. (2)

heading: 3.2 ORDER STATISTICS OVER THE PATH ENSEMBLE

text:
Given a trajectory, the set of n-step estimators E := {Â(1)t , Â (2) t , . . . } is defined as the path ensemble for the pair (st, at). We have briefly mentioned that the maximum over path ensemble can achieve the promotion focus, and the minimum over path ensemble can achieve the prevention focus in Introduction. The max statistics and the min statistics over the path ensemble are respectively computed by
Âmaxt := max i
{ Â
(i) t } , Âmint := min
i
{ Â
(i) t
} . (3)
For many environments that are neither sparse nor fragile, whether they are more close to promotion focus or prevention focus is unclear without in-depth inspection. They also might be too complex to
be simply described by any one of the two regulatory types. For these cases, we propose a generalized order statistics which is a hybrid of the maximum and minimum. We call it the max-abs statistics which took the element with the maximum absolute value,
Âmax-abst := argmax A∈{Â(i)t } |A|. (4)
To understand how elements in the path ensemble relates to regulatory focus, we interpret the k-step estimation as counterfactual speculations when k ≤ n. Since k-step estimation only involves the first k states after the evaluated state, all actions and the followed observations are dropped and be replaced by the state-value at step-k. This underlies a counterfactual thinking that what if the agent didn’t do the action sequence at+k+1, at+k+2, . . ., and replace the situation by the average behavior? Then different regulatory focus would treat the set of counterfactual speculations in different ways.
The max Statistics and the Promotion Focus A promotion focus is concerned with advancement, growth, and accomplishment. The promotion focus inclination is to insure hits and insure against errors of omission. Facing the set of counterfactual speculations, it would choose the one with the maximum value to insure any action at in st that is possibly to behave good to have more importance. The max statistics leads to optimistic estimation of advantages. It is beneficial for sparse-reward environments as actions that may lead to large returns will not be buried by the later bad actions.
The min Statistics and the Prevention Focus A prevention focus is concerned with security, safety, and responsibility. The prevention focus inclination is to insure correct rejections and insure against errors of commission. Facing the set of counterfactual speculations, it would choose the one with the minimum value to avoid wrongly acknowledge an action that only temporarily leads to high rewards. The min statistics implies the risk-averse bias. It avoids actions that may cause bad states later. By decreasing the advantage estimation of those actions, it makes the optimization direction away from them. This property is useful for fragile environments, such as the biped locomotion environments which are sensitive to joint motions of the characters.
The max-abs Statistics and Overreaction In the max-abs statistics, the estimator with the largest absolute value in the path ensemble is chosen. This means that an action is evaluated as either overly good when the largest positive advantage is selected, or overly bad when the smallest negative advantage is selected. We refer to this behavior as overreaction. Overreaction is not a terminology in regulatory focus theory, but a descriptive term for the phenomenon concerning the effects of the max-abs statistics. This statistics implements a heuristic that makes the good paths look better and the bad paths look worse. As will be shown in experiments, this heuristic generally improves sample efficiency for the MuJoCo and Atari environments, where their regulatory focuses are unclear.
Both the maximum and the minimum belong to the family of order statistics, where the k-th order statistics equals to the k-th smallest value. From computational perspective, it is also viable to test whether the more general order statistics are effective for training, although lacking strong explanations. We put the study on general order statics in Appendix A.
3.3 AN ILLUSTRATIVE STUDY ON THE max STATISTICS
Before delving into the discussion of estimating advantages, we first look at a concrete example of how the max statistics ofQ-values affect the learning process of the policy iteration algorithm (Sutton & Barto, 2011, Section 4.3). In Figure 1(a), an MDP with 6 states is drawn. For simplicity, we assume that both the state transitions and the rewards are deterministic, and the discount factor is 1. In this example, only the two actions in state s3 can get rewards, where R(s3, a1, s5) = −2 and R(s3, a2, s6) = 2. At the initialization step of the policy iteration algorithm, the policy is initialized as the uniform random policy π1. In the first step of the policy iteration, we evaluate the Q function and value function V of this random policy π1. Under policy π1, all possible trajectories are also shown in Figure 1(a). We compute that Qπ1(s1, a1) = 0, and Qπ1(s1, a2) = 0. So in the next step, the greedy policy π2 for state s1 is still at random. We compute Q̂max using the max statistics,
Q̂max(s1, a1) = E [ max i {R(i)} | s1, a1 ] = 0, Q̂max(s1, a2) = E [ max i {R(i)} | s1, a2 ] = 1.
(5)
Using Q̂max, the greedy policy at state s1 is argmaxa Q̂ max(s1, a) = a2. Actually, the algorithm with max statistics finds the optimal policy within only 1 step in this example.
We see that the max statistics over the path ensembles converges faster in the toy example because it discovers the potentially good action a2 at state s1 earlier than using the standard way. As the computation of the second trajectory in Figure 1(a) shows, the max statistics blacklists the bad action a1 in state s3. In a trajectory, when an action is so bad that the later actions cannot compensate for the caused loss, it will be replaced by the average actions. This good-action discovering ability is a characteristic of promotion focus, and is suitable for sparse-reward environments. In the early exploration stage in the training, the agent barely receives positive signals. Many trajectories might happens to act well at some time, but then go to bad states later due to wrong actions. The max statistics can highlight actions that are possible to get high rewards in any middle step of the trajectory. By effectively discovering good actions, this method is expected to improve the sampling efficiency.
The foundational position of advantage in actor-critic algorithms is attributed by the policy gradient theorem in Equation (1). A sample (st, at) makes the policy network πθ adjust its parameters according to the estimation of advantage Ât(st, at). The probability of πθ(st) = at is increased when the advantage is positive, and decreased when the advantage is negative. If the estimation of advantage Ât(st, at) is manipulated to be larger, the learned policy is then biased toward the action at at state st. Thus when the estimation of certain advantages Ât(st, at) is manipulated properly, the learned policy can be biased toward the desired regulatory orientation.

heading: 3.4 INCORPORATING REGULATORY FOCUS INTO RL ALGORITHMS

text:
We should be careful that in the presence of uncertainty or noise, applying the max statistics in policy iteration may fail to improve policy. We give two examples when the estimation is overly optimistic. The first example, which is shown in Figure 1(b), is caused by the uncertainty in state transitions. We have Q̂max(s1, a1) = 0.5 and Q̂max(s1, a2) = 1, which implies that action a2 should be chosen in state s1. However, the optimal strategy is to select a1. This is caused by the the max statistics’ ignorance on the coupling risks. When taking an action, both good and bad may happen. The bad cases is ignored in the estimation. However, we cannot avoid bad next-state when selecting that action. The second example, shown in Figure 1(c), is a case when the reward owns randomness. The problem is that the maximum operation over the ensemble causes overestimation, a symptom that also troubles the Q-learning algorithm as discussed in TD3 (Fujimoto et al., 2018).
We overcome this shortcoming from two aspects: (1) implement the regulatory focus as an exploration strategy. Namely, the estimation from path ensemble is used with a probability ρ. We call ρ as the regulatory ratio. (2) using a small ensemble size. We argue that a small ensemble size is sufficient for practical use because elements in the path ensemble are inter-related. Roughly speaking, the difference between the i-step advantage estimator Â(i)t and the j-step estimator Â (j) t in a path ensemble is discounted exponentially with the minimum step index min(i, j) of the two. In fact, let j > i, then
Â (j) t − Â (i) t = γ i ( j−i−1∑ s=0 (γsrt+s+i) + γ j−iV (st+j)− V (st+i) ) . (6)
The sum in the big bracket can be assumed to be bounded. Based on this observation, the values of the estimation Â(k)t would not change too much when k becomes large. In practice using a subset of the full ensemble also reduces the computational cost. For example, we used an ensemble with only four elements E = {Â(1)t , Â (16) t , Â (64) t , Â (2048) t } in the MuJoCo physics simulator experiments.
Summarizing the above discussion, our algorithm is designed as follows.
Algorithm 1 Regulatory Focus by Order Statistics over Path Ensembles 1: Parameters: the ensemble set E , the order statistics Âorder over E , and the regulatory ratio ρ. 2: for each iteration do 3: Collect trajectories. 4: Compute the advantage Â and the estimation Âorder. 5: Update the policy network according to PPO, A2C, or TRPO, in which Âorder is used with
probability ρ, and Â is used otherwise. 6: Update the critic network using the estimation of Q value, which equals to V + Â. 7: end for
Our method can be easily plugged into any actor-critic algorithms with a minimal code change and a small computational overhead.

heading: 4 EXPERIMENT

text: We evaluate the performance of our algorithm on four different types of problems, including the environment with sparse reward, biped locomotion, continuous control and Atari games.

heading: 4.1 SPARSE REWARD AND THE PROMOTION FOCUS INCLINATION

text:
The amortized EX2 algorithm (Fu et al., 2017) is designed for tasks with sparse rewards. Three environments were chosen from their paper, which represent three types of problems. The order statistics over path ensemble was implemented by modifying the advantage estimation procedure of the authors’ original code, where the TRPO is used for policy optimization. The path ensemble was composed of k-step estimators where k ∈ {1, 16, 64, 4000} for Maze and Doom, and k ∈ {1, 16, 64, 5000} for SparseHalfCheetah. The numbers 4000 and 5000 originated from the respective batch sizes. The regulatory ratio for both the max and the min statistics was set to ρ = 0.5 for Maze and Doom, and ρ = 0.3 for SparseHalfCheetah. All hyper-parameters followed the settings of the amortized EX2. The result is shown in Figure 2.
2D Maze This environment provides a sparse reward function, where the agent can only get the reward when it is within a small radius of the goal. From the figure, we observed that the max statistics started to gain rewards at the very early stage, which indicates the promotion focus provides a supreme sample efficiency over other methods. After 500 updates, the average episodic reward of max was much higher than that of the EX2 algorithm. The min statistics was worse than EX2.
Doom MyWayHome is a vision-based maze navigation benchmark, where the agent is required to navigate through a series of interconnected rooms before reaching the goal. A +1 reward is given for reaching the goal before timeout. The task is challenging because the inputs are realistic images in the first-person perspective. The max statistics was very effective for this challenge and it reached nearly 100% success rate. In comparison, EX2 only got an average of 0.6 episode rewards.
SparseHalfCheetah It is a challenging continuous control task with sparse reward. Our promotion focus significantly improved the sample efficiency, and the reward after 1000 updates was 40% higher than the EX2 algorithm. Also, the min statistics was less effective than EX2 in all three benchmarks, which demonstrates that prevention focus is not effective in sparse environments.

heading: 4.2 BIPED LOCOMOTION AND THE PREVENTION FOCUS INCLINATION

text: The prevention focus is very useful for environments that are fragile to actions, i.e., one wrong action would lead to catastrophic results later on. The Terrain RL simulator (Berseth et al., 2018) provides such environments. Two biped walking tasks were selected, where a character needs to learn how to walk steadily forward in two different terrains, the flat and the incline, as shown in Figure 3. The character continuously receives rewards until it fells down or is stuck, in which case the episode terminates. This task is challenging because the observation only contains the pose of the character, which forces the character to learn how to walk without memorizing actions based on its location. In contrast, the locomotion tasks in MuJoCo environments contain absolute world coordinates in the observation. The action space is 11-dimensional, which corresponds to the joints of the character. The environment is fragile. If a wrong action is performed, the character might lose balance and fall down. We used PPO in this experiment. The hyper-parameters were borrowed from those designed for MuJoCo environments in the baselines’ (Dhariwal et al., 2017) PPO implementation and are also listed in Appendix. The min and max statistics were implemented on top of the PPO algorithm. The path ensemble consisted of k-step estimators where k ∈ {1, 16, 64, 2048}, and the regulatory ratio is ρ = 0.3. The results are shown in Figure 3. The prevention focus inclination via the min statistics successfully mastered the task while the vanilla PPO algorithm failed. The promotion focus inclination by the max was not very effective in these environments as the low reward curves indicate that the character fells down at the beginning of the episode. We conclude that prevention focus by the min statistics of the path ensemble helps the agent to learn in fragile environments.

heading: 4.3 CONTINUOUS CONTROL AND THE OVERREACTION INCLINATION

text: We tested various advantage estimations on 5 continuous control benchmarks based on the MuJoCo physics simulator. They are not sparse-reward environments, and most of them are also not sensitive to individual actions. For example, the design of the HalfCheetah agent makes it seldom fall down or be stuck. We used PPO in this set of experiments. The implementation was based on the baselines (Dhariwal et al., 2017) code repository, and the default hyper-parameters were adopted. We tested three order statistics including the max, the min and the max-abs statistics. In all settings, the path ensemble had index set {1, 16, 64, 2048}, and the regulatory ratio was set to ρ = 0.4. Results are shown in Figure 4. We observed that the max-abs statistics was consistently better than the baseline PPO algorithm, while the performances of the max and the min statistics depended upon the specific environment. So we conclude that the overreaction inclination by the max-abs statistics is generally effective for a wide range of environments.

heading: 4.4 ATARI GAMES AND THE OVERREACTION INCLINATION

text: The new advantage estimations were also tested on a subset of Atari game environments. We used the A2C algorithm with 4 paralleled threads. The implementation was based on the A2C codes in baselines (Dhariwal et al., 2017). Hyper-parameters were the defaults for Atari games. Since the sampled trajectory length was 5 in the default setting, the path ensemble had fewer elements, which was composed of {1, 3, 5}. The maximum trajectory length of 5 in a batch was too small to gather enough data on k-step estimations when k > 1. For example, only the first state has a valid 5-step advantage estimation in a length-5 trajectory. This affects the power of the path ensemble. To circumvent this limitation, we collected paths of length 5n, and then computed the advantage estimators using these longer trajectories. Since the batch size was n times of the original setting, it was split into n mini-batches. For Seaquest and Breakout, n = 20; for Pong and Qbert, n = 10; and for BeamRider, n = 60. The result is shown in Figure 5. In these environments, the sparsity and fragility were unknown. Obviously, the overreaction inclination generally improves the performance, whereas the max and the min statistics are only effective for a subset of environments.

heading: 5 CONCLUSION

text: According to the regulatory fit theory in psychology, when people engage in goal pursuit activities in a manner that fits their regulatory orientation, they feel right about what they are doing. In this paper, we proposed a simple yet effective way of exploration using the idea of regulatory fit. The regulatory focus is implemented in the context of reinforcement learning via the order statistics over path ensembles, which formed nonlinear combinations of different n-step advantage estimators. The maximum, the minimum, and the element with the maximum absolute value were studied in detail. We incorporated these advantage estimators into three widely used actor-critic algorithms including A2C, TRPO and PPO. When the promotion or prevention focus inclination fits the environment, the proposed algorithm could be effective in solving sparse-reward environments, or the fragile environments which are sensitive to individual actions. We verified the effectiveness of our approach by extensive experiments on various domains, including the continuous control, locomotion, video games, and sparse-reward environments.

heading: A ABLATION STUDY

text:
In this section we study the behavior of general order statistics on MuJoCo environments, and then discuss the sensitivity of the algorithms to hyper-parameters.
The General Order Statistics As shown in Figure 6, in three (InvertedDoublePendulum, Ant, and Humanoid) of the five environments, the max and min were better than the 2nd and the 3rd order statistics. This means that some environments welcome both optimistic and risk-averse exploration. Overall, the intermediate order statistics was better than the baseline, which used the GAE estimator.
Sensitivity on the Regulatory Ratio Generally speaking, the regulatory ratio ρ had a great influence on the performance. As shown in Figure 6, the range [0.2, 0.4] is a plausible choice for most experiments. If the ratio is further increased, the performance may degrade. This is consistent with our analysis, and shows the necessity of using regulatory focus as an exploration strategy.
Effect of Ensemble Size We built another path ensemble whose index set consisted of 12 elements. They were {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. Final performances of the three order statistics, max, min and max-abs, were tested under the regulatory ratio ρ = 0.4. For the ensemble with 4 elements {1, 16, 64, 2048}, the average episode reward in the end of the training was 928, 927, 974, respectively; and for the ensemble of size 12, the numbers were 767, 854 and 867. It shows that a small ensemble size can already get most of the performance boost.

heading: B COMPARE WITH -GREEDY EXPLORATION

text: As an exploration method, it is helpful to compare the regulatory focus exploration with the basic -greedy exploration. The results are shown on Mujoco environments in Figure 7. We can see that completely random exploration, even in small proportion, makes the results worse.

heading: C COMPARE WITH DIFFERENT CLIP THRESHOLD OF PPO

text: The clipping threshold of PPO also affects the estimation of advantage. A smaller clipping threshold would result in a more conservative policy iteration. We compare the effect of smaller clipping threshold with the min statistics over path ensemble on the biped locomotion task. Results are shown in Figure 8. Clipping is adding a global minimum constraint, meaning that all trajectories share the same clipping constant. In contrast, the min of path ensemble gives prevention focus inclination in a momentary manner, i.e. per trajectory. The performance of min path ensemble is much better.

heading: D PATH ENSEMBLE OF GAES

text:
The generalized advantage estimator GAE(γ, λ) is an exponentially-weighted average of different n-step estimators,
GAE(γ, λ) := (1− λ) ( Â
(1) t + λÂ (2) t + λ 2Â (3) t + · · ·
) . (7)
With different hyper-parameter λ, the estimator focus on different time ranges. For example, if λ is small, then the decay would be very fast and effectively only the first steps in the trajectory is considered; if λ is close to 1, then GAE takes longer time ranges into account. Having the above observation, we can use the path ensemble of GAEs with different λs as an alternate version of the path ensemble of n-step advantages. The GAE formulation would have a smaller variance and may be beneficial for some environments. We tested the formulation of ensembling GAEs on the Mujoco environments and found substantial improvements on the Ant-v2 and Humanoid-v2 environments. Note also that on HalfCheetah-v2 and Walker2d-v2, performance drops compared to ensembling n-step advantages. The results are drawn in Figure 9.

heading: E DETAILED EXPERIMENT SETTINGS

text: The detailed hyper-parameter settings of the experiments are listed in Table 1.