summaries: In the article, the authors solve the problem of anomaly detection using a fully unsupervised approach. They try to deal with the main challenge of anomaly detection: a lack of certainty on what defines normal data and anomaly one. For this purpose, the authors iteratively use: 1) autoencoders to learn the representation of the data; 2) applying in the latent space clustering to get a new training set and retrain autoencoders. The experimental results show that the author’s method performed better results than such a baseline model as one-class SVM and one-class NN.

summaries: In this paper the authors propose a framework for anomaly detection. The method is based on autoencoders and reconstruction error, but instead of training the autoencoder using all the data-points, the method iteratively uses some form of clustering to determine the points which presumably belong to the normal set, and uses them for training the autoencoder. This helps make the method robust when the portion of anomalous data-points is high.

summaries: The paper proposed an unsupervised anomaly detection method for the scenarios where the training data not only includes normal data but also a lot of anomaly data. The basic idea of this paper is to iteratively refine the normal data subset, selected from the whole training data set. Specifically, the paper first train an auto-encoder (AE) and determine which are the normal data samples according to the reconstruction errors. Then, using the normal data to retrain the AE again, and re-select the normal samples. Repeat the above two steps until convergence.

abstractText: This paper proposes a novel method to detect anomalies in large datasets under a fully unsupervised setting. The key idea behind our algorithm is to learn the representation underlying normal data. To this end, we leverage the latest clustering technique suitable for handling high dimensional data. This hypothesis provides a reliable starting point for normal data selection. We train an autoencoder from the normal data subset, and iterate between hypothesizing normal candidate subset based on clustering and representation learning. The reconstruction error from the learned autoencoder serves as a scoring function to assess the normality of the data. Experimental results on several public benchmark datasets show that the proposed method outperforms state-of-the-art unsupervised techniques and is comparable to semi-supervised techniques in most cases.

authors:
Jinwon An
Sungzoon Cho

title: Variational autoencoder based anomaly detection using reconstruction probability

venue: Technical report,

authors:
Lars Buitinck
Gilles Louppe
Mathieu Blondel
Fabian Pedregosa
Andreas Mueller
Olivier Grisel
Vlad Niculae
Peter Prettenhofer
Alexandre Gramfort
Jaques Grobler
Robert Layton
Jake VanderPlas
Arnaud Joly
Brian Holt
Gaël Varoquaux

title: API design for machine learning software: experiences from the scikit-learn project

venue: In ECML PKDD Workshop: Languages for Data Mining and Machine Learning,

authors:
Emmanuel J. Candès
Xiaodong Li
Yi Ma
John Wright

title: Robust principal component analysis

venue: J. ACM,

authors:
Raghavendra Chalapathy
Aditya Krishna Menon
Sanjay Chawla

title: Anomaly detection using one-class neural networks

venue: arXiv preprint arXiv:1802.06360,

authors:
Varun Chandola
Arindam Banerjee
Vipin Kumar

title: Anomaly detection: A survey

venue: ACM computing surveys (CSUR),

authors:
Jesse Davis
Mark Goadrich

title: The relationship between precision-recall and roc curves

venue: In Proceedings of the 23rd international conference on Machine learning,

authors:
Jeremy Elson
John JD Douceur
Jon Howell
Jared Saul

title: Asirra: a captcha that exploits interest-aligned manual image categorization

title: An introduction to roc analysis

venue: Pattern recognition letters,

authors:
Izhak Golan
Ran El-Yaniv

venue: arXiv preprint arXiv:1805.10917,

authors:
JooSeuk Kim
C. Scott

title: Robust kernel density estimation

venue: IEEE International Conference on Acoustics, Speech and Signal Processing,

authors:
Aleksandar Lazarevic
Levent Ertoz
Vipin Kumar
Aysel Ozgur
Jaideep Srivastava

title: A comparative study of anomaly detection schemes in network intrusion detection

venue: In Proceedings of the 2003 SIAM International Conference on Data Mining,

authors: Corinna Cortes. MNIST handwritten digit database.

title: URL http://yann

authors:
Wen-Yan Lin
Siying Liu
Jian-Huang Lai
Yasuyuki Matsushita

title: Dimensionality’s blessing: Clustering images by underlying distribution

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

authors:
Leland McInnes
John Healy
Steve Astels

title: hdbscan: Hierarchical density based clustering

venue: J. Open Source Software,

authors:
G. Mishne
I. Cohen

title: Iterative diffusion-based anomaly detection

venue: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP),

authors:
Clifton Phua
Vincent Lee
Kate Smith
Ross Gayler

title: A comprehensive survey of data miningbased fraud detection research

venue: arXiv preprint arXiv:1009.6119,

authors:
Venkatesh Saligrama
Janusz Konrad
Pierre-Marc Jodoin

title: Video anomaly identification

venue: IEEE Signal Processing Magazine,

authors:
Thomas Schlegl
Philipp Seebck
Sebastian M. Waldstein
Georg Langs
Ursula Schmidt-Erfurth

title: f-anogan: Fast unsupervised anomaly detection with generative adversarial networks

venue: Medical Image Analysis,

authors:
Waqas Sultani
Chen Chen
Mubarak Shah

title: Real-world anomaly detection in surveillance videos

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Du Tran
Lubomir Bourdev
Rob Fergus
Lorenzo Torresani
Manohar Paluri

title: Learning spatiotemporal features with 3d convolutional networks

authors:
Y. Wang
B. Xue
L. Wang
H. Li
L. Lee
C. Yu
M. Song
S. Li
C. Chang

title: Iterative anomaly detection

venue: IEEE International Geoscience and Remote Sensing Symposium (IGARSS),

authors:
Yan Xia
Xudong Cao
Fang Wen
Gang Hua
Jian Sun

title: Learning discriminative reconstructions for unsupervised outlier removal

venue: In The IEEE International Conference on Computer Vision (ICCV),

authors:
Tao Xiang
Shaogang Gong

title: Video behavior profiling for anomaly detection

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Shuangfei Zhai
Yu Cheng
Weining Lu
Zhongfei Zhang

title: Deep structured energy based models for anomaly detection

venue: In Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48,

authors:
Chong Zhou
Randy C Paffenroth

title: Anomaly detection with robust deep autoencoders

venue: In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,

authors:
Bo Zong
Qiankun Song
Martin Renqiang Min
Wei Cheng
Cristian Lumezanu
Dae ki Cho
Haifeng Chen

title: Deep autoencoding gaussian mixture model for unsupervised anomaly detection

venue: In Proceedings of International Conference on Learning Representations (ICLR),

heading: 1 INTRODUCTION

text:
Anomaly detection refers to the identification of patterns that do not conform to expected normal behavior (Chandola et al. (2009)). It is a critical task in diverse application domains such as fraud detection (Phua et al. (2010)), intrusion detection (Lazarevic et al. (2003)) and surveillance video profiling (Xiang & Gong (2008); Saligrama et al. (2010)). While the concept of an anomaly is intuitively easy for humans to understand, it is hard to define mathematically. Fundamentally, an anomaly is something with insufficient similarity to the rest of the data. This similarity can be computed on the basis of some feature difference. However, what makes an ideal feature representation for the data depends on what constitutes an anomaly. This forces anomaly detection into a chicken-or-egg problem in which there are a pair of problems, neither of which can be solved before the other.
To date, a number of works have attempted this problem by training an autoencoder to create lowdimensional representations for anomaly detection (Chalapathy et al. (2018); Zhai et al. (2016); Zong et al. (2018)). The anomalies are rejected and the autoencoder retrained (Mishne & Cohen (2017); Wang et al. (2017)). While this gives reasonable results, it is fundamentally dependent on how well the first iteration solves the problem.
We propose a solution in which anomalies can be defined using approximately correct features. This is achieved through an observation. Given a feature, anomalies approximately correspond to instances of high variance distributions. Such instances can be identified using a distribution-clustering (Lin et al. (2018)) framework. This hypothesis provides a reliable starting point for normal data selection. We train an autoencoder from the normal data subset, and iterate between hypothesizing normal candidate subset and representation learning. The reconstruction error serves as a scoring function to assess the normality of the data. The proposed framework does not rely on any training labels. Instead, it iteratively distills out anomalous data and improves the learned representation of normal data by incorporating clustering techniques into the process.
We extensively assess the broad applicability of the proposed model on network intrusion, image and video data. Empirical results show that the proposed method outperforms the existing state-of-art approaches in terms of both accuracy and robustness to the percentage of anomalous data.

heading: 2 RELATED WORKS

text:
Existing anomaly detection methods can be grouped into three categories.
Reconstruction-based method These methods assume that anomalies are incompressible and thus cannot be effectively reconstructed from low-dimensional projections. Classical methods like Principle Component Analysis(PCA) (I.T.Jolliffe (1986)) and Robust-PCA (Candès et al. (2011)) are motivated by this assumption. In recent works, different forms of deep autoencoder are proposed to analyze the reconstruction error. Xia et al. (Xia et al. (2015)) show that by introducing a regularizing term to a convolutional autoencoder, the anomalies tend to produce a bigger reconstruction error. Variational Autoencoder (VAE) (An & Cho (2015)) and Generative Adversarial Networks (GANs) (Schlegl et al. (2019)) have also been introduced to perform reconstruction-based anomaly detection. These methods demonstrate promising results when the anomaly ratio is fairly low. Although the reconstruction of anomalous samples, based on a reconstruction scheme optimized for normal data, tends to generate a higher error, a significant amount of anomalous samples could mislead the autoencoders to learn the correlations in the anomalous data instead.
Density estimation and clustering Motivated by the assumption that anomalies occur less frequently, these algorithms treat anomalies as low-density regions in some feature space. Clustering analysis, such as Robust-KDE (JooSeuk Kim & Scott (2008)), is often used for density estimation and anomaly detection. Unfortunately, due to the curse of dimensionality, these methods are less applicable to analysing high-dimensional data, where density estimation is a challenge in itself.
A two-step approach is normally adopted to counter this issue, where dimensionality reduction is conducted first, followed by clustering analysis as a separate step. One drawback of this approach is that dimensionality reduction is trained without the guidance from the subsequent clustering analysis; hence the key information for clustering analysis could be lost during dimensionality reduction. Recent works jointly learn dimensionality reduction and clustering components based on deep autoencoder (Zhai et al. (2016); Zong et al. (2018)). Notably, DAGMM (Zong et al. (2018)) utilizes an autoencoder to generate a low-dimensional representation and its reconstruction error, which is further fed into an estimation network based on Gaussian Mixture Model(GMM). However, as its autoencoder was trained on the whole dataset, it is vulnerable to a high percentage of anomalous samples and may learn wrong correlations. In contrast, our proposed method addresses this issue by first finding a normal candidate subset to train an autoencoder and then iterating between representation learning and refinement of the normal candidate.
One-class classification One-class SVM (Erfani et al.; Chalapathy et al. (2018)) is also widely used. Under this framework, a discriminative boundary surrounding the normal instances is learned by algorithms. However, when dimensionality goes higher, such techniques often suffer from suboptimal performance due to the curse of dimensionality. OCNN (Chalapathy et al. (2018)) attempted to circumvent this problem by using an autoencoder for dimensionality reduction. However, OCNN requires training data with relatively low anomaly ratio, in order to obtain an optimized NN model to differentiate anomalies from single-class normal data.

heading: 3 PROBLEM FORMULATION

text:
Let X = {xi}, i = 1, . . . , N , x ∈ Rk be the set of input data points that contains a certain percentage of anomaly. The goal of anomaly detection is to learn a scoring function h(x), h : Rk 7→ R, to classify samples xi based on some threshold λ:
yi = { 0, if h(xi) < λ 1, if h(xi) ≥ λ
(1)
where yi are the labels. yi = 0 indicates xi is normal and yi = 1 indicates anomalous.
An overview of the proposed end-to-end anomaly detection system is presented in Fig. 1. The major component of this system is an autoencoder that learns a low-dimensional representation of the input data that are often of high dimensions, to enable simplified modeling of the underlying distribution of the data. Under a fully unsupervised setting, the only information we are given is the set of input data X, without any label information. As an initialization, we leverage the latest clustering technique for high-dimensional data (Lin et al. (2018)) to provide soft supervisory signals.
Since our input data is unlabelled, we derive a “training” set Strain, where Strain ⊂ X based on the following:
Strain = C(X, p0) (2)
where C represents a selection process based on clustering output, and p0 represents the percentage of anomaly, it controls which are the clusters to be accepted into the “training” set. In our experiments, we compute the threshold as the (100− p0)th percentile of cluster variance, and accept clusters with variance smaller than this threshold. The assumption here is that clusters with large variance are likely to contain anomalous members.

heading: 3.1 SCORING FUNCTION LEARNING

text:
The autoencoder network provides two sources of features: (1) a low-dimensional representation of the original input data; and (2) the reconstruction error by comparing the input with its decoded counter-part. Using the training set Strain = {s1, s2, · · · , sM}, the autoencoder learns the encoding function fen: zc = fen(s; Θen), ∀s ∈ Strain, zc ∈ Rkbn (3) where Θen are the learned parameters for the encoder. zc are known as the bottle-neck features of dimension kbn.
Similarly, for the decoding part, we have:
x′ = fde(zc; Θde), (4)
where Θde are the learned parameters for decoding. x′ are the reconstructed features.
Upon training, we have a learned autoencoder with optimized parameters {Θen,Θde}. We run the entire input set X forward through the encoder network and produce a set of new features Z = {z1, z2, · · · , zN}, by concatenating the bottle-neck feature with the reconstruction error:
z = [zc; zr] , z ∈ Rkbn+1, (5)
where the reconstruction error zr is measured in terms of cosine similarity between x and its decoded counter-part:
zr = d(x,x ′) = cos−1
( xTx′
‖ x ‖‖ x′ ‖
) (6)
Note that Z is now of a much lower dimension than the input data X. Hence, traditional clustering techniques such as Gaussian Mixture Model would suffice for subsequent training set selection. To ensure the initial training set can capture most of the normal samples, we adopt a more conservative cluster variance threshold.
With the new encoding scheme, the entire input set X is now represented as Z. We can “re-label” the training set X by using Z as a proxy. Similar to the initial training set selection, we select members that belong to low-variance clusters in Z. The process of Training set selection → Autoencoder training→ New feature computation is performed iteratively. The training set is updated as follows:
Zt+1train = C(Z t, p), (7)
St+1train = {xj : ∀zj ∈ Z t+1 train}, (8)
where the superscript t here refers to the tth iteration.
Finally, the training process terminates when there is no change in the set of selected normal samples between two successive iterations. After the last iteration, t = tF , we obtain the autoencoder parameters {ΘtFen,Θ tF de}, and use it to construct the scoring function:
h(x) = d(x,x′) = d(x, fde(fen(x; Θ tF en); Θ tF de )), (9)
where x′ is the result of going through the encoding-decoding process according to the trained autoencoder.

heading: 3.2 ALGORITHM

text:
The proposed framework is summarized in Algorithm 1. We obtain an initial split of the data into normal and abnormal subsets through clustering (i.e. GMM for KDDCUP data and Distribution Clustering (Lin et al. (2018)) for image and video data). Selected outputs for CIFAR-10 and MNIST datasets using Distribution Clustering are presented in Fig. 4 in the appendix. We observe that as cluster variance increases, the samples’ appearance become more anomalous.
Algorithm 1 Deep end-to-end Unsupervised Anomaly Detection Input: X = {xi}, i = 1, 2..., N : set of normal and anomalous input examples.
r: number of epochs required for re-evaluation of the membership of the entire input set X. p0 and p: thresholds for initial and subsequent training set selection, respectively
Output: Reconstruction-based anomaly score function h(x) and trained autoencoder {ΘtFen,Θ tF de},
1: procedure GET DECISION SCORE(X, r, p, fen, fde) 2: Strain ← C(X, p0) . Run clustering, select instances from low-variance clusters 3: L = {k : ∀xk ∈ Strain} . L is the set of indices of selected normal training samples 4: Lold := ∅ 5: while setdiff(Lold,L) 6= ∅ do 6: for each epoch do 7: if ((CurrentEpoch+ 1) mod r) == 0 then . Re-evaluate normality every r epochs 8: Zc ← fen(X,Θen) . Bottle-neck features 9: X′ ← fde(Zc,Θde) 10: Zr ← d(X,X′) . Reconstruction error 11: Z← [Zc;Zr] 12: Strain ← C(Z, p) . Get new training set according to threshold p 13: Lold := L 14: L← Strain . Update set of indices for training samples 15: else 16: Train fen, fde on Strain to obtain {Θen,Θde} 17: end for 18: end while 19: ΘtFen = Θen, Θ tF de = Θde 20: Output h(x) according to finalized autoencoder {ΘtFen,Θ tF de} base on Eq. (9) 21: end procedure
Convergence Assuming a p% anomaly ratio, our algorithm starts with a tight cut-off, accepting clusters with variances below (100− p0)th percentile as an initial training set, where p0 > p. This ensures the initial training set is as pure as possible. Our assumption is that given partial normal data, the autoencoder would be able to learn a representation and generalize well on the “unseen” normal data that was discarded, and progressively recover them as iterations go on. Empirically, we plotted the AUROC, AUPRC and F-score for 20 iterations for the KDDCUP experiment, presented in Fig. 5 of the appendix. It demonstrates the convergence as iteration progresses. The same behavior was observed throughout our experiments on other datasets.

heading: 4 EXPERIMENTS

heading: 4.1 BASELINE METHODS

text:
On the topic of anomaly detection, there exist different terminologies concerning the nature of supervision: (a) Algorithm uses label information of the normal class for training (label information could be used in part, or all of the stages of an algorithm); (b) No training labels are given, algorithm treats the entire dataset with both normal and anomalous classes as input. For the purpose of this paper, we term type (a) semi-supervised and type (b) unsupervised. We evaluate our proposed algorithm against the following state-of-the-art methods:
OC-NN (semi-supervised) One-class neural networks (OC-NN) (Chalapathy et al. (2018)) contains 2 major components: a deep autoencoder and a feed-forward convolutional network. The deep encoder is trained on normal data for representation learning. The trained encoder, with its parameters frozen, is subsequently used as the input layers of a feed-forward network with 1 extra hidden layer. Variants of OC-NN employ different activation functions (i.e. linear, sigmoid, relu) in the hidden layer. We report the best score attained among all possible activation functions in our experiments.
OC-SVM (unsupervised) One-class support vector machine (OC-SVM) (Erfani et al.) is a kernelbased method for anomaly detection. The algorithm searches for best-performing hyper-parameters γ (kernel coefficient) and ν (upper bound of the fraction of training errors and lower bound of the fraction of support vectors) to obtain the optimal AUROC (Buitinck et al. (2013)).
DAGMM (unsupervised) Deep autoencoding Gaussian mixture model (DAGMM) (Zong et al. (2018)), comprised of one compression net and one estimation net, is a method based on representation learning. The compression network provides low-dimensional representations of input samples and the reconstruction error features. They are fed into the estimation network, which functions as a Gaussian Mixture Model, to predict the mixture membership for each sample. We modify the original DAGMM algorithm by adding a small value to the diagonal elements of the covariance matrix. The model achieves better results than the reported score from the original work.
Deep anomaly detection using geometric transformations (semi-supervised) This method (Golan & El-Yaniv (2018)) employs a deep neural model to identify out-of-distribution samples of image data, given only the examples from the normal class. A series of geometric transformations are applied to the normal class to create a multi-class dataset. A deep neural net, trained using this dataset, is then employed to discriminate the transformations applied. Subsequently, given an unseen instance, the model applies each transformation on it and assigns membership scores. The final normality score is determined based on the combined log-likelihood of softmax response vectors.

heading: 4.2 DATASETS

text:
We employ five benchmark datasets, namely, KDDCUP, MNIST, CIFAR-10, CatVsDog and UCFCrime, to evaluate our proposed method, together with other methods described above.
• KDDCUP: The KDDCUP network intrusion dataset (Lichman et al. (2013)) contains samples of 41 dimensions. Similar to (Zong et al. (2018)), categorical features are prepared by applying one-hot encoding. 20% of the ”normal” samples form the minority group, while the rest 80% are treated as ”attackers”. As ”normal” samples are the minorities, they are treated as anomalies
• MNIST: The MNIST dataset (LeCun & Cortes (2010)) consists of 60,000 gray-scale 28 × 28 images of handwritten digits from 0 to 9. We formulate an anomaly detection task as per described in (Chalapathy et al. (2018)) and (Zhou & Paffenroth (2017)), where 4,859 images of digit 4 are randomly sampled as normal instances and 265 images are evenly sampled from all other categories as anomalies.
• CatVsDog: The CatVsDog dataset consists of dogs and cats images of varying sizes, which are extracted from the ASIRRA dataset (Elson et al. (2007)) following the settings specified in (Golan & El-Yaniv (2018)). 12,500 images of dogs and 2,500 images of cats are sampled to form an anomaly detection task. The cat images are treated as anomalies.
• UCF-Crime: The UCF-Crime dataset (Sultani et al. (2018)) contains 1,900 long and untrimmed videos captured from CCTV cameras. It covers 13 real-world anomalies, including incidents like fighting, burglary, abuse and etc. In both of the training and testing sets, videos are of different length and anomalies happens at various temporal locations. Some of the videos may have multiple anomalies. In the experiment, we randomly select reasonably long videos with at least 1000 frames and anomaly ratio less than 0.35 across 4 categories.

heading: 4.3 EVALUATIONS

text:
We adopt Area Under the curve of the Receiver Operating Characteristic (AUROC) as the main evaluation metric to measure the discrimination power of different models. AUROC is a standard method to assess the effectiveness of a classifier (Fawcett (2006)). It can be interpreted as the probability that an anomalous instance is assigned to a higher anomaly score than a normal instance (Davis & Goadrich (2006)). In this section, we compare the performance of our method against other baseline methods.
KDDCUP: Network Intrusion Data In this experiment, we divide the KDDCUP dataset following the setting in (Zong et al. (2018)). 50% of the data is reserved for testing by random sampling. From the remaining 50% of the data reserved for training, we take all samples from the normal class and mix them with different percentages of samples from the anomaly class to form the training set. Parameters for this experiment (see Algorithm 1) are set to: p0 = 35%, p = 30%, r = 10.
Table 2 and 3 reports the AUROC and AUPRC of OC-SVM, DAGMM and our model on the KDDCUP dataset after 200 epochs, with anomaly ratio in training set being 5%, 10% and 20%, respectively. It can be observed that the increase in ratio of anomalous data undermines the detection performance of OC-SVM and DAGMM more severely, while our method remains robust to such changes.
Figure 2 shows the Receiver Operating Characteristic (ROC) curves of different models when the anomaly ratio of the training data is 20%. In our unsupervised setting where no prior knowledge of normal class is known, our method is clearly more robust to contaminated training data.
Image Data In table 4, we compare the AUROC scores obtained from OC-NN, OC-SVM, DAGMM, Geometric Transformation and our model, based on multiple image datasets. It should be noted that Geometric Transformation approach trains on data from the normal class only (hence classified as semi-supervised). Our method, on the other hand, does not require label information.
Results in Table 4 demonstrate an outstanding performance of our method over other unsupervised approaches. In addition, on CIFAR-10, the performance of our proposed algorithm is comparable to that of Geometric Transformation, a semi-supervised method. In the last column of Table 4, we report results obtained using distribution clustering alone. The combination of distribution clustering and autoencoder significantly improves the discrimination against anomalies. Details of the parameters used in the experiments are reported in the appendix.
We make several key observations based on the attained results in Table 4. Unlike all other methods that tend to perform better on simpler datasets (e.g. MNIST), the advantage of our method becomes more evident on datasets with higher complexity. Notably, our method outperforms other unsupervised approaches on CIFAR-10 and CatVsDog. The shortfall of our method on MNIST dataset could be due to the adoption of NetVLad feature extractor (4096-d feature vectors), which may not be an ideal choice of feature representation since the images are pre-aligned and hence of low dimensionality. We repeat the same experiment using raw image features from MNIST. It shows improved AUROC score, suggesting that raw feature is a better representation.
We also observe that while our method is able to produce results comparable to semi-supervised approaches, the gap is wider on CatVsDog dataset as compared to CIFAR-10. We attribute this to the high noise level in the CatVsDog dataset. For example, some images consist of both dog and cats. Moreover, training on normal data (with augementation through geometric transformation) gives
Geometric Transform a natural advantage. According to (Elson et al. (2007)), ASIRRA dataset, from which the CatVsDog is extracted, is deemed extremely challenging for computers. Sample images of the dataset are presented in the appendix.
Video Data We apply the proposed approach on UCF-Crime dataset (Sultani et al. (2018)), with features extracted using C3D (Tran et al. (2015)) descriptor. In default C3D settings, every 16 frames are aggregated to generate 1 feature vector. As our method is unsupervised, it needs a sufficient amount of feature vectors for training. We select videos with at least 65 vectors (1040 frames).
In (Sultani et al. (2018)), although the AUROC score of each video category is not reported, the AUROC averaged across the entire testing set of UCF-Crime dataset is 75.4%. It is achieved by adopting a semi-supervised method of multiple instance learning (MIL). The AUROC scores on 4 randomly selected video categories, using our method and DAGMM, are reported in Table 7. The parameters used in training, as well as individual video-level scores are detailed in the appendix.
A good correspondence between the ground truth and our anomaly scores can be observed in Figure 3, where frames with anomalous events under the orange lines are assigned to higher anomaly scores. It can be observed that our method significantly out-performs DAGMM. Moreover, our method is able to produce AUROC higher than 75.4% for some action categories. Despite under a fully unsupervised setting, our method is as effective in detecting anomalies from video data as its semi-supervised competitor, demonstrating its strength in handling complex and high-dimensional data.
Run Time Excluding feature extraction and clustering process, on a single NVIDIA Tesla P100 GPU, our method takes 4 minutes 20 seconds on average to complete the CIFAR-10 experiment described above (consisting of 5,500 instances). This timing is averaged over 5 runs.

heading: 4.4 ABLATION STUDY

text:
Initialization To examine the effect of adopting distribution clustering as the initialization method for high-dimensional data, a variety of other mainstream clustering methods, including K-means, HDBSCAN (McInnes et al. (2017)) and Gaussian Mixture Model (GMM) are used to replace the distribution clustering component in the initial normal subset selection. We compare results on the CIFAR-10 task.
For K-means and GMM, prior information on the number of clusters/components is set to 20, which is consistent with the setting of the GMM employed in the proposed model. For HDBSCAN, the minimum size of a cluster is set to 5, that follows the setting as distribution clustering. Table 6 reports the AUROC scores obtained from CIFAR-10 anomaly detection task with different clustering techniques. The results demonstrate that using distribution clustering initialisation provides better supervisory signals and leads to favourable performance.
To further understand the effectiveness of distribution clustering, we tabulated in the AUROC achieved using distribution clustering alone, for the experiments on image data (refer to right-most column of Table 4). Surprisingly, this result is even better than those of DAGMM and OC-NN on the challenging CatVsDog dataset.

heading: 5 DISCUSSION AND CONCLUSION

text:
This paper presents an end-to-end method for anomaly detection under a fully unsupervised setting. The key insight of our algorithm is to model normal data. We leverage distribution clustering technique to make an educated guess on the normal data subset. By incorporating clustering to provide supervisory signals, we iterate between hypothesizing normal candidate subset and representation learning. This framework iteratively distills out anomalous data and improves the learned representation of normal data. Extensive experiments on benchmark datasets demonstrate our proposed method outperforms existing unsupervised approaches and is comparable to semi-supervised solutions in most cases.
Limitations and future work: Using only an autoencoder, our current method may be insufficient to handle highly complex patterns and hence falls short on difficult dataset such as CatVsDog. For future work, we seek to explore more sophisticated generative frameworks for representation learning.

heading: B CONVENGENCE

text: To investigate the convergence behavior, we plotted the AUROC, AUPRC and F-score for 20 iterations for the KDDCUP experiment in Fig. 5 in the appendix, where the ground truth anomaly ratio is 20%. It demonstrates the convergence as iteration progresses. The same behavior was observed throughout our experiments.

heading: C RESULT BREAKDOWN OF UCF CRIME

text:
Video with less than 65 segments or anomaly ratio higher than 0.35 are not taken into consideration.
Results obtained after running 5 rounds of experiments. (take average and standard deviation)

heading: D NETWORK PARAMETERS

text:
Table 8 reports the settings and parameters for each experiments.
Note: for video with small number of segments, the value of p is set to be larger because anomalous samples take larger proportion given the small number of total segments.
Note: Relu is adopted as the activation function except for static data where tanh is used instead.

heading: E PARAMETER OF DISTRIBUTION CLUSTERING

text: Please refer to the original work on distribution clusteringLin et al. (2018) for more information on parameters. Table 9 reports the parameters used for distribution clustering.

heading: F SAMPLE CATVSDOG DATA

text: Figure 7 and 6 presents some example images of dogs and cats from ASIRRA dataset.


summaries: This paper introduces a constrained policy optimization algorithm by introducing a two-step optimization process, where policies that do not satisfy the constraint can be projected back into the constraint set. The proposed PCPO algorithm is theoretically analyzed to provide an upper bound on the constraint violation. The proposed constrained policy optimization algorithm is shown to be useful on a range of control tasks, satisfying constraints or avoiding constraint violation significantly better than the compared baselines.

summaries: This paper proposes a new algorithm - Projection based Constrained Policy Optimization, that is able to learn policies with constraints, i.e., for CMDPs. The algorithm consists of two stages: first an unconstrained update for maximizing reward, and the second step for projecting the policy back to the constraint set.  The authors provide analysis in terms of bounds for reward improvement and constraint violation.  The authors characterize the convergence with two projection metrics: KL divergence and L2 norm.  The new algorithm is tested on four control tasks: two mujoco environments with safety constraints, and two traffic management tasks, where it outperforms the CPO and lagrangian based approaches.

summaries: The paper proposes a technique to handle a certain type of constraints involved in Markov Decision Processes (MDP). The problem is well-motivated, and according to the authors, there is not much relevant work. The authors compare with the competing methods that they think are most appropriate. The numerical experiments seem to show superiority of their method in most of the cases. The proposed method has 4 main variants: (1) define projection in terms of Euclidean distance or (2) KL-divergence, and (a) solve the projection problem exactly (usually intractable) or (b) solve a Taylor-expanded variant (so there are variants 1a,1b,2a,2b).

abstractText: We consider the problem of learning control policies that optimize a reward function while satisfying constraints due to considerations of safety, fairness, or other costs. We propose a new algorithm, Projection-Based Constrained Policy Optimization (PCPO). This is an iterative method for optimizing policies in a two-step process: the first step performs a local reward improvement update, while the second step reconciles any constraint violation by projecting the policy back onto the constraint set. We theoretically analyze PCPO and provide a lower bound on reward improvement, and an upper bound on constraint violation, for each policy update. We further characterize the convergence of PCPO based on two different metrics: L norm and Kullback-Leibler divergence. Our empirical results over several control tasks demonstrate that PCPO achieves superior performance, averaging more than 3.5 times less constraint violation and around 15% higher reward compared to state-of-the-art methods.1

authors:
Joshua Achiam
David Held
Aviv Tamar
Pieter Abbeel

title: Constrained policy optimization

venue: In Proceedings of International Conference on Machine Learning,

authors:
Riad Akrour
Joni Pajarinen
Gerhard Neumann
Jan Peters

title: Projections for approximate policy iteration algorithms

title: Constrained Markov decision processes, volume 7

venue: CRC Press,

authors:
Yinlam Chow
Mohammad Ghavamzadeh
Lucas Janson
Marco Pavone

title: Risk-constrained reinforcement learning with percentile risk criteria

venue: Journal of Machine Learning Research,

authors:
Yinlam Chow
Ofir Nachum
Aleksandra Faust
Mohammad Ghavamzadeh
Edgar DuenezGuzman

title: Lyapunov-based safe policy optimization for continuous control

authors:
Yan Duan
Xi Chen
Rein Houthooft
John Schulman
Pieter Abbeel

title: Benchmarking deep reinforcement learning for continuous control

authors:
Yang Gao
Ji Lin
Fisher Yu
Sergey Levine
Trevor Darrell

title: Reinforcement learning from imperfect demonstrations

venue: arXiv preprint arXiv:1802.05313,

authors:
Javier Garcia
Fernando Fernandez

title: A comprehensive survey on safe reinforcement learning

authors:
Sham Kakade
John Langford

title: Approximately optimal approximate reinforcement learning

authors:
Sergey Levine
Chelsea Finn
Trevor Darrell
Pieter Abbeel

title: End-to-end training of deep visuomotor policies

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin Riedmiller

title: Playing atari with deep reinforcement learning

venue: arXiv preprint arXiv:1312.5602,

authors:
Aravind Rajeswaran
Vikash Kumar
Abhishek Gupta
Giulia Vezzani
John Schulman
Emanuel Todorov
Sergey Levine

title: Learning complex dexterous manipulation with deep reinforcement learning and demonstrations

venue: arXiv preprint arXiv:1709.10087,

authors:
Stéphane Ross
Geoffrey Gordon
Drew Bagnell

title: A reduction of imitation learning and structured prediction to no-regret online learning

venue: In Proceedings of International Conference on Artificial Intelligence and Statistics,

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: Highdimensional continuous control using generalized advantage estimation

venue: arXiv preprint arXiv:1506.02438,

title: An introduction to the conjugate gradient method without the agonizing pain

authors:
David Silver
Julian Schrittwieser
Karen Simonyan
Ioannis Antonoglou
Aja Huang
Arthur Guez
Thomas Hubert
Lucas Baker
Matthew Lai
Adrian Bolton

title: Mastering the game of go without human knowledge

authors:
Richard S. Sutton
David A. McAllester
Satinder P. Singh
Yishay Mansour

title: Policy gradient methods for reinforcement learning with function approximation

venue: In Advances in Neural Information Processing Systems,

authors:
Chen Tessler
Daniel J. Mankowitz
Shie Mannor

title: Reward constrained policy optimization

venue: arXiv preprint arXiv:1805.11074,

authors:
Eugene Vinitsky
Aboudy Kreidieh
Luc Le Flem
Nishant Kheterpal
Kathy Jang
Fangyu Wu
Richard Liaw
Eric Liang
Alexandre M. Bayen

title: Benchmarks for reinforcement learning in mixed-autonomy traffic

venue: In Proceedings of Conference on Robot Learning,

heading: 1 INTRODUCTION

text:
Recent advances in deep reinforcement learning (RL) have demonstrated excellent performance on several domains ranging from games like Go (Silver et al., 2017) and StarCraft (AlphaStar, 2019) to robotic control (Levine et al., 2016). In these settings, agents are allowed to explore the entire state space and experiment with all possible actions during training. However, in many realworld applications such as self-driving cars and unmanned aerial vehicles, considerations of safety, fairness and other costs prevent the agent from having complete freedom to explore. For instance, an autonomous car, while optimizing its driving policies, must not take any actions that could cause harm to pedestrians or property (including itself). In effect, the agent is constrained to take actions that do not violate a specified set of constraints on state-action pairs. In this work, we address the problem of learning control policies that optimize a reward function while satisfying predefined constraints.
The problem of policy learning with constraints is more challenging since directly optimizing for the reward, as in Q-Learning (Mnih et al., 2013) or policy gradient (Sutton et al., 2000), will usually violate the constraints. One approach is to incorporate constraints into the learning process by forming a constrained optimization problem. Then perform policy updates using a conditional gradient descent with line search to ensure constraint satisfaction (Achiam et al., 2017). However, the base optimization problem can become infeasible if the current policy violates the constraints. Another approach is to add a hyperparameter weighted copy of the constraints to the objective function (Tessler et al., 2018). However, this incurs the cost of extensive hyperparameter tuning.
To address the above issues, we propose projection-based constrained policy optimization (PCPO). This is an iterative algorithm that performs policy updates in two stages. The first stage maximizes reward using a trust region optimization method (e.g., TRPO (Schulman et al., 2015a)) without
1 For code see the project website: https://sites.google.com/view/iclr2020-pcpo
constraints. This might result in a new intermediate policy that does not satisfy the constraints. The second stage reconciles the constraint violation (if any) by projecting the policy back onto the constraint set, i.e., choosing the policy in the constraint set that is closest to the selected intermediate policy. This allows efficient updates to ensure constraint satisfaction without requiring a line search (Achiam et al., 2017) or adjusting a weight (Tessler et al., 2018). Further, due to the projection step, PCPO offers efficient recovery from infeasible (i.e., constraint-violating) states (e.g., due to approximation errors), which existing methods do not handle well.
We analyze PCPO theoretically and derive performance bounds for the algorithm. Specifically, based on information geometry and policy optimization theory, we construct a lower bound on reward improvement, and an upper bound on constraint violations for each policy update. We find that with a relatively small step size for each policy update, the worst-case constraint violation and reward degradation are tolerable. We further analyze two distance measures for the projection step onto the constraint set. We find that the convergence of PCPO is affected by the smallest and largest singular values of the Fisher information matrix used during training. By observing these singular values, we can choose the appropriate projection best suited to the problem.
Empirically, we compare PCPO with state-of-the-art algorithms on four different control tasks, including two Mujoco environments with safety constraints introduced by Achiam et al. (2017) and two traffic management tasks with fairness constraints introduced by Vinitsky et al. (2018). In all cases, the proposed algorithm achieves comparable or superior performance to prior approaches, averaging more reward with fewer cumulative constraint violations. For instance, across the above tasks, PCPO achieves 3.5 times fewer constraint violations and around 15% more reward. This demonstrates the ability of PCPO robustly learn constraint-satisfying policies, and represents a step towards reliable deployment of RL in real problems.

heading: 2 PRELIMINARIES

text:
We frame our policy learning as a constrained Markov Decision Process (CMDP) (Altman, 1999), where policies will direct the agent to maximize the reward while minimizing the cost. We define CMDP as the tuple < S,A, T,R,C >, where S is the set of states, A is the set of actions that the agent can take, T : S ×A×S → [0, 1] is the transition probability of the CMDP, R : S ×A → R is the reward function, and C : S × A → R is the cost function. Given the agent’s current state s, the policy π(a|s) : S → A selects an action a for the agent to take. Based on s and a, the agent transits to the next state (denoted by s′) according to the state transition model T (s′|s, a), and receives the reward and pays the cost, denoted by R(s, a) and C(s, a), respectively.
We aim to learn a policy π that maximizes a cumulative discounted reward, denoted by
JR(π) . = Eτ∼π [ ∞∑ t=0 γtR(st, at) ] ,
while satisfying constraints, i.e., making a cumulative discounted cost constraint below a desired threshold h, denoted by
JC(π) . = Eτ∼π [ ∞∑ t=0 γtC(st, at) ] ≤ h,
where γ is the discount factor, τ is the trajectory (τ = (s0, a0, s1, · · · )), and τ ∼ π is shorthand for showing that the distribution over the trajectory depends on π : s0 ∼ µ, at ∼ π(at|st), st+1 ∼ T (st+1|st, at), where µ is the initial state distribution. Kakade & Langford (2002) give an identity to express the performance of policy π′ in terms of the advantage function over another policy π :
JR(π′)− JR(π) = 1 1− γ E s∼dπ ′
a∼π′ [AπR(s, a)], (1)
where dπ is the discounted future state distribution, denoted by dπ(s) .= (1 − γ) ∑∞ t=0 γ
tP (st = s|π), and AπR(s, a) is the reward advantage function, denoted by AπR(s, a) . = QπR(s, a) − V πR (s). Here Q π R(s, a) . = Eτ∼π [∑∞ t=0 γ tR(st, at)|s0 = s, a0 = a ]
is the discounted cumulative reward obtained by the policy π given the initial state s and action a, and V πR (s) . =
Eτ∼π [∑∞ t=0 γ tR(st, at)|s0 = s ] is the discounted cumulative reward obtained by the policy π given the initial state s. Similarly, we have the cost advantage function AπC(s, a) = QπC(s, a) − V πC (s), where QπC(s, a) . = Eτ∼π [∑∞ t=0 γ tC(st, at)|s0 = s, a0 = a ] , and V πC (s) . =
Eτ∼π [∑∞ t=0 γ tC(st, at)|s0 = s ] .

heading: 3 PROJECTION-BASED CONSTRAINED POLICY OPTIMIZATION

text:
To robustly learn constraint-satisfying policies, we develop PCPO – a trust region method that performs policy updates corresponding to reward improvement, followed by projections onto the constraint set. PCPO, inspired by projected gradient descent, is composed of two steps for each update, a reward improvement step and a projection step (This is illustrated in Fig. 1).
Reward Improvement Step. First, we optimize the reward function by maximizing the reward advantage function AπR(s, a) subject to a Kullback-Leibler (KL) divergence constraint. This constraints the intermediate policy πk+ 1 2 to be within a δ-neighbourhood of πk:
πk+ 1 2 = argmax
π E s∼dπ k a∼π [Aπ
k
R (s, a)]
s.t. E s∼dπk [ DKL(π||πk)[s] ] ≤ δ. (2)
This update rule with the trust region, {π : E s∼dπk [ DKL(π||πk)[s] ] ≤ δ}, is called Trust Region Policy Optimization (TRPO) (Schulman et al., 2015a). It constraints the policy changes to a divergence neighborhood and guarantees reward improvement.
Projection Step. Second, we project the intermediate policy πk+ 12 onto the constraint set by minimizing a distance measure D between πk+ 1 2 and π:
πk+1 = argmin π D(π, πk+ 1 2 )
s.t. JC(πk) + E s∼dπ k a∼π [Aπ
k
C (s, a)] ≤ h. (3)
The projection step ensures that the constraint-satisfying policy πk+1 is close to πk+ 1 2 . We consider two distance measures D: L2 norm and KL divergence. In contrast, using KL divergence projection in the probability distribution space allows us to provide provable guarantees for PCPO.

heading: 3.1 PERFORMANCE BOUND FOR PCPO WITH KL DIVERGENCE PROJECTION

text:
In safety-critical applications such as autonomous cars, one cares about how worse the performance of a system evolves when applying a learning algorithm. To this end, for PCPO with KL divergence projection, we analyze the worst-case performance degradation for each policy update when the current policy πk satisfies the constraint. The following theorem provides a lower bound on reward improvement, and an upper bound on constraint violation for each policy update.
Theorem 3.1 (Worst-case Bound on Updating Constraint-satisfying Policies). Define π k+1 R . =
max s ∣∣Ea∼πk+1 [AπkR (s, a)]∣∣, and πk+1C .= maxs ∣∣Ea∼πk+1 [AπkC (s, a)]∣∣. If the current policy πk satisfies the constraint, then under KL divergence projection, the lower bound on reward improvement, and upper bound on constraint violation for each policy update are
JR(πk+1)− JR(πk) ≥ − √ 2δγ π k+1 R
(1− γ)2 , and JC(πk+1) ≤ h+
√ 2δγ π k+1
C
(1− γ)2 ,
where δ is the step size in the reward improvement step.
Proof. See the supplemental material.
Theorem 3.1 indicates that if δ is small, the worst-case performance degradation is tolerable.
Due to approximation errors or the random initialization of policies, PCPO may have a constraintviolating update. Theorem 3.1 does not give the guarantee on updating a constraint-violating policy. Hence we analyze worst-case performance degradation for each policy update when the current policy πk violates the constraint. The following theorem provides a lower bound on reward improvement, and an upper bound on constraint violation for each policy update.
Theorem 3.2 (Worst-case Bound on Updating Constraint-violating Policies). Define π k+1 R . =
max s ∣∣Ea∼πk+1 [AπkR (s, a)]∣∣, πk+1C .= maxs ∣∣Ea∼πk+1 [AπkC (s, a)]∣∣, b+ .= max(0, JC(πk) − h), and αKL . = 1
2aTH−1a , where a is the gradient of the cost advantage function and H is the Hessian
of the KL divergence constraint. If the current policy πk violates the constraint, then under KL divergence projection, the lower bound on reward improvement and the upper bound on constraint violation for each policy update are
JR(πk+1)− JR(πk) ≥−
√ 2(δ + b+2αKL)γ πk+1
R
(1− γ)2 ,
and JC(πk+1) ≤ h+
√ 2(δ + b+2αKL)γ πk+1
C
(1− γ)2 ,
where δ is the step size in the reward improvement step.
Proof. See the supplemental material.
Theorem 3.2 indicates that when the policy has greater constraint violation (b+ increases), its worstcase performance degradation increases. Note that Theorem 3.2 reduces to Theorem 3.1 if the current policy πk satisfies the constraint (b+ = 0). The proofs of Theorem 3.1 and Theorem 3.2 follow from the fact that the projection of the policy is non-expansive, i.e., the distance between the projected policies is smaller than that of the unprojected policies. This allows us to measure it and bound the KL divergence between the current policy and the new policy.

heading: 4 PCPO UPDATES

text:
For a large neural network policy with many parameters, it is impractical to directly solve for the PCPO update in Problem 2 and Problem 3 due to the computational cost. However, with a small step size δ, we can approximate the reward function and constraints with a first order expansion, and approximate the KL divergence constraint in the reward improvement step, and the KL divergence measure in the projection step with a second order expansion. We now make several definitions:
g . = ∇θE
s∼dπ k a∼π
[Aπ k
R (s, a)] is the gradient of the reward advantage function,
a . = ∇θE
s∼dπ k a∼π
[Aπ k
C (s, a)] is the gradient of the cost advantage function,
Hi,j . =
∂2E s∼dπk
[ DKL(π||πk)[s] ] ∂θj∂θj
is the Hessian of the KL divergence constraint (H is also called the Fisher information matrix. It is symmetric positive semi-definite), b .= JC(πk)− h is the constraint violation of the policy πk, and θ is the parameter of the policy.
Reward Improvement Step. We linearize the objective function at πk subject to second order approximation of the KL divergence constraint in order to obtain the following updates:
θk+ 1 2 = argmax θ gT (θ − θk)
s.t. 1
2 (θ − θk)TH(θ − θk) ≤ δ. (4)
Algorithm 1 Projection-Based Constrained Policy Optimization (PCPO)
Initialize policy π0 = π(θ0) for k = 0, 1, 2, · · · do
Run πk = π(θk) and store trajectories in D Compute g,a,H, and b using D Obtain θk+1 using update in Eq. (6) Empty D
Projection Step. If the projection is defined in the parameter space, we can directly use L2 norm projection. On the other hand, if the projection is defined in the probability space, we can use KL divergence projection. This can be approximated through the second order expansion. Again, we linearize the cost constraint at πk. This gives the following update for the projection step:
θk+1 = argmin θ
1 2 (θ − θk+ 12 )TL(θ − θk+ 12 )
s.t. aT (θ − θk) + b ≤ 0, (5)
where L = I for L2 norm projection, and L = H for KL divergence projection. One may argue that using linear approximation to the constraint set is not enough to ensure constraint satisfaction since the real constraint set is maybe non-convex. However, if the step size δ is small, then the linearization of the constraint set is accurate enough to locally approximate it.
We solve Problem (4) and Problem (5) using convex programming (See the supplemental material for the derivation). For each policy update, we have
θk+1 = θk+
√ 2δ
gTH−1g H−1g −max
0, √ 2δ gTH−1g aTH−1g + b
aTL−1a L−1a. (6) We assume thatH does not have 0 as an eigenvalue and hence it is invertible. PCPO requires to invertH , which is impractical for huge neural network policies. Hence we use the conjugate gradient method (Schulman et al., 2015a). Algorithm 1 shows the pseudocode. (See supplemental material for a discussion of the tradeoff between the approximation error and computational efficiency of the conjugate gradient method.)
Analysis of PCPO Update Rule. For a problem including multiple constraints, we can extend the update in Eq. (6) by using alternating projections. This approach finds a solution in the intersection of multiple constraint sets by sequentially projecting onto each of the sets. The update rule in Eq. (6) shows that the difference between PCPO with KL divergence and L2 norm projections is the cost update direction, leading to a difference in reward improvement. These two projections converge to different stationary points with different convergence rates related to the smallest and largest singular values of the Fisher information matrix shown in Theorem 4.1. For our analysis, we make the following assumptions: we minimize the negative reward objective function f : Rn → R (We follow the convention of the literature that authors typically minimize the objective function). The function f is L-smooth and twice continuously differentiable over the closed and convex constraint set C. Theorem 4.1 (Reward Improvement Under L2 Norm and KL Divergence Projections). Let η . = √
2δ gTH−1g in Eq. (6), where δ is the step size for reward improvement, g is the gradient of f,
and H is the Fisher information matrix. Let σmax(H) be the largest singular value of H, and a be the gradient of cost advantage function in Eq. (6). Then PCPO with KL divergence projection converges to a stationary point either inside the constraint set or in the boundary of the constraint set. In the latter case, the Lagrangian constraint g = −αa, α ≥ 0 holds. Moreover, at step k + 1 the objective value satisfies
f(θk+1) ≤ f(θk) + ||θk+1 − θk||2− 1ηH+L2 I .
PCPO with L2 norm projection converges to a stationary point either inside the constraint set or in the boundary of the constraint set. In the latter case, the Lagrangian constraintH−1g = −αa, α ≥
0 holds. If σmax(H) ≤ 1, then a step k + 1 objective value satisfies
f(θk+1) ≤ f(θk) + (L 2 − 1 η )||θk+1 − θk||22.
Proof. See the supplemental material.
Theorem 4.1 shows that in the stationary point g is a line that points to the opposite direction of a. Further, the improvement of the objective value is affected by the singular value of the Fisher information matrix. Specifically, the objective of KL divergence projection decreases when Lη2 I ≺ H, implying that σmin(H) > Lη2 . And the objective of L
2 norm projection decreases when η < 2 L , implying that condition number of H is upper bounded: σmax(H) σmin(H) < 2||g||22 L2δ . Observing the singular values of the Fisher information matrix allows us to adaptively choose the appropriate projection and hence achieve objective improvement. In the supplemental material, we further use an example to compare the optimization trajectories and stationary points of KL divergence and L2 norm projections.

heading: 5 RELATED WORK

text:
Policy Learning with Constraints. Learning constraint-satisfying policies has been explored in the context of safe RL (Garcia & Fernandez, 2015). The agent learns policies either by (1) exploration of the environment (Achiam et al., 2017; Tessler et al., 2018; Chow et al., 2017) or (2) through expert demonstrations (Ross et al., 2011; Rajeswaran et al., 2017; Gao et al., 2018). However, using expert demonstrations requires humans to label the constraint-satisfying behavior for every possible situation. The scalability of these rule-based approaches is an issue since many real autonomous systems such as self-driving cars and industrial robots are inherently complex. To overcome this issue, PCPO uses the first approach in which the agent learns by trial and error. To prevent the agent from having constraint-violating behavior during exploring the environment, PCPO uses the projection onto the constraint set to ensure constraint satisfaction throughout learning.
Constraint satisfaction by Projections. Using a projection onto a constraint set has been explored for general constrained optimization in other contexts. For example, Akrour et al. (2019) projects the policy from a parameter space onto the constraint. This ensures the updated policy stays close to the previous policy. In contrast, we examine constraints that are defined in terms of states and actions. Similarly, Chow et al. (2019) proposes θ-projection. This approach projects the policy parameters θ onto the constraint set. However, no provide provable guarantees are provided. Moreover, the
problem is formulated by adding the weighted constraint to the reward objective function. Since the weight must be tuned, this incurs the cost of hyperparameter tuning. In contrast, PCPO eliminates the cost of the hyperparameter tuning, and provides provable guarantees on learning constraintsatisfying policies.
Comparison to CPO (Achiam et al., 2017). Perhaps the closest work to ours is the approach of Achiam et al. (2017), who proposes the constrained policy optimization (CPO) algorithm to solve the following:
θk+1 = argmax θ gT (θ − θk) s.t. 1 2 (θ − θk)TH(θ − θk) ≤ δ, aT (θ − θk) + b ≤ 0. (7)
CPO simultaneously considers the trust region and the constraint, and uses the line search to select a step size (This is illustrated in Fig. 2). The update rule of CPO becomes infeasible when the current policy violates the constraint (b > 0). CPO recovers by replacing Problem (7) with an update to
purely decrease the constraint value: θk+1 = θk − √
2δ aTH−1a H−1a. This update rule may lead
to a slow progress in learning constraint-satisfying policies. In contrast, PCPO first optimizes the reward and uses the projection to satisfy the constraint. This ensures a feasible solution, allowing the agent to improve the reward while ensuring constraint satisfaction simultaneously.

heading: 6 EXPERIMENTS

text:
Tasks. We compare the proposed algorithm with existing approaches on four control tasks in total: two tasks with safety constraints ((a) and (b) in Fig. 3), and two tasks with fairness constraints ((c) and (d) in Fig. 3). These tasks are briefly described in the caption of Fig. 3. The first two tasks – Gather and Circle – are Mujoco environments with state space constraints introduced by Achiam et al. (2017). The other two tasks – Grid and Bottleneck – are traffic management problems where the agent controls either a traffic light or a fleet of autonomous vehicles. This is especially challenging since the dimensions of state and action spaces are larger, and the dynamics of the environment are inherently complex.
Baselines. We compare PCPO with four baselines outlined below.
(1) Constrained Policy Optimization (CPO) (Achiam et al., 2017).
(2) Primal-dual Optimization (PDO) (Chow et al., 2017). In PDO, the weight (dual variables) is learned based on the current constraint satisfaction. A PDO policy update solves:
θk+1 = argmax θ gT (θ − θk) + λkaT (θ − θk), (8)
where λk is updated using λk+1 = λk + β(JC(πk)− h). Here β is a fixed learning rate. (3) Fixed-point Policy Optimization (FPO). A variant of PDO that solves Eq. (8) using a constant λ.
(4) Trust Region Policy Optimization (TRPO) (Schulman et al., 2015a). The TRPO policy update is an unconstrained one: θk+1 = θk + √
2δ gTH−1g H−1g.
Note that TRPO ignores any constraints. We include it to serve as an upper bound baseline on the reward performance.
Since the main focus is to compare PCPO with the state-of-the-art algorithm, CPO, PDO and FPO are not shown in the ant circle, ant gather, grid and bottleneck tasks for clarity.
Experimental Details. For the gather and circle tasks we test two distinct agents: a point-mass (S ⊆ R9, A ⊆ R2), and an ant robot (S ⊆ R32, A ⊆ R8). The agent in the grid task is S ⊆ R156, A ⊆ R4, and the agent in bottleneck task is S ⊆ R141, A ⊆ R20. For the simulations in the gather and circle tasks, we use a neural network with two hidden layers of size (64, 32) to represent
Gaussian policies. For the simulations in the grid and bottleneck tasks, we use a neural network with two hidden layers of size (16, 16) and (50,25) to represent Gaussian policies, respectively. In the experiments, since the step size is small, we reuse the Fisher information matrix of the reward improvement step in the KL projection step to reduce the computational cost. The step size δ is set to 10−4 for all tasks and all tested algorithms. For each task, we conduct 5 runs to get the mean and standard deviation for both the reward and the constraint value over the policy updates. The experiments are implemented in rllab (Duan et al., 2016), a tool for developing and evaluating RL algorithms. See the supplemental material for the details of the experiments.
Overall Performance. The learning curves of the discounted reward and the undiscounted constraint value (the total number of constraint violation) over policy updates are shown for all tested algorithms and tasks in Fig. 4. The dashed line in the constraint figure is the cost constraint threshold h. The curves for baseline oracle, TRPO, indicate the reward and constraint value when the constraint is ignored. Overall, we find that PCPO is able to improve the reward while having the fastest constraint satisfaction in all tasks. In particular, PCPO is the only algorithm that learns constraintsatisfying policies across all the tasks. Moreover we observe that (1) CPO has more constraint violation than PCPO, (2) PDO is too conservative in optimizing the reward, and (3) FPO requires a significant effort to select a good value of λ.
We also observe that in Grid and Bottleneck task, there is slightly more constraint violation than the easier task such as point circle and point gather. This is due to complexity of the policy behavior and non-convexity of the constraint set. However, even with a linear approximation of the constraint set, PCPO still outperforms CPO with 85.15% and 5.42 times less constraint violation in Grid and Bottleneck task, respectively.
These observations suggest that projection step in PCPO drives the agent to learn the constraintsatisfying policy within few policy updates, giving PCPO an advantage in applications. To show that PCPO achieves the same reward with less constraint violation, we examine the reward versus the cumulative constraint value for the tested algorithms in point circle and point gather task shown in Fig. 5. We observe that PCPO outperforms CPO significantly with 66 times and 15 times less constraint violation under the same reward improvement in point circle and point gather tasks, respectively. This observation suggests that PCPO enables the agent to cautiously explore the environment under the constraints.
Comparison of PCPO with KL Divergence vs. L2 Norm Projections. We observe that PCPO with L2 norm projection is more constraint-satisfying than PCPO with KL divergence projection. In addition, PCPO with L2 norm projection tends to have reward fluctuation (point circle, ant circle, and ant gather tasks), while with KL divergence projection tends to have more stable reward improvement (all the tasks).
The above observations indicate that since the gradient of constraint is not multiplied by the Fisher information matrix, the gradient of the constraint is not aligned with the gradient of the reward. This reduces the reward improvement. However, when the Fisher information matrix is ill-conditioned or not well-estimated, especially in a high dimensional policy space, a bad constraint update direction may hinder constraint satisfaction (ant circle, ant gather, grid and bottleneck tasks). In addition, since the stationary points of KL divergence and L2 norm projections are different, they converge to policies with different reward (observe that PCPO with L2 norm projection has higher reward than the one with KL divergence projection around 2250 iterations in ant circle task, and has less reward in point gather task).
Discussion of PDO and FPO. For the PDO baseline, we see that its constraint values fluctuate especially in the point circle task. This phenomena suggests that PDO is not able to adjust the weight λk quickly enough to meet the constraint threshold, which hinders the efficiency of learning constraint-satisfying policies. If the learning rate β is too big, the agent will be too conservative in improving the reward. For FPO, we also see that it learns near constraint-satisfying policies with slightly larger reward improvement compared to PDO. However, in practice FPO requires a lot of engineering effort to select a good value of λ. Since PCPO requires no hyperparameter tuning, it has the advantage of robustly learning constraint-satisfying policies over PDO and FPO.

heading: 7 CONCLUSION

text: We address the problem of finding constraint-satisfying policies. The proposed algorithm – projection-based constrained policy optimization (PCPO) – optimizes for the reward function while using the projections to ensure constraint satisfaction. This update rule allows PCPO to maintain the feasibility of the optimization problem of each update, addressing the issue of state-of-the-art approaches. The algorithm achieves comparable or superior performance to state-of-the-art approaches in terms of reward improvement and constraint satisfaction in all cases. We further analyze the convergence of PCPO, and find that certain tasks may prefer either KL divergence projection or L2 norm projection. Future work will consider the following: (1) examining the Fisher information matrix to iteratively prescribe the choice of projection for policy update, and hence robustly learn constraint-satisfying policies with more reward improvement, and (2) using expert demonstration or other domain knowledge to reduce the sample complexity.

heading: ACKNOWLEDGMENTS

text: The authors would like to thank the anonymous reviewers and the area chair for their comments. Tsung-Yen Yang thanks Siemens Corporation, Corporate Technology for their support.

heading: S SUPPLEMENTARY MATERIALS

heading: S.1 PROOF OF THEOREM 3.1: PERFORMANCE BOUND ON UPDATING THE CONSTRAINT-SATISFYING POLICY

text:
To prove the policy performance bound when the current policy is feasible (i.e., constraintsatisfying), we prove the KL divergence between πk and πk+1 for the KL divergence projection. We then prove our main theorem for the worst-case performance degradation.
Lemma S.1. If the current policy πk satisfies the constraint, the constraint set is closed and convex, the KL divergence constraint for the first step is E s∼dπk [ DKL(π k+ 12 ||πk)[s] ] ≤ δ, where δ is the step size in the reward improvement step, then under KL divergence projection, we have
E s∼dπk [ DKL(π k+1||πk)[s] ] ≤ δ.
Proof. By the Bregman divergence projection inequality, πk being in the constraint set, and πk+1 being the projection of the πk+ 1 2 onto the constraint set, we have
E s∼dπk [ DKL(π k||πk+ 12 )[s] ] ≥ E s∼dπk [ DKL(π k||πk+1)[s] ] + E s∼dπk [ DKL(π k+1||πk+ 12 )[s] ]
⇒ δ ≥E s∼dπk [ DKL(π k||πk+ 12 )[s] ] ≥ E s∼dπk [ DKL(π k||πk+1)[s] ] .
The derivation uses the fact that KL divergence is always greater than zero. We know that KL divergence is asymptotically symmetric when updating the policy within a local neighbourhood. Thus, we have
δ ≥ E s∼dπk [ DKL(π k+ 12 ||πk)[s] ] ≥ E s∼dπk [ DKL(π k+1||πk)[s] ] .
Now we use Lemma S.1 to prove our main theorem.
Theorem S.2. Define π k+1 R . = max
s ∣∣Ea∼πk+1 [AπkR (s, a)]∣∣, and πk+1C .= max s
∣∣Ea∼πk+1 [AπkC (s, a)]∣∣. If the current policy πk satisfies the constraint, then under the

text:
JR(πk+1)− JR(πk) ≥ − √ 2δγ π k+1 R
(1− γ)2 , and JC(πk+1) ≤ h+
√ 2δγ π k+1
C
(1− γ)2 ,
where δ is the step size in the reward improvement step.
Proof. By the theorem in Achiam et al. (2017) and Lemma S.1, we have the following reward degradation bound for each policy update:
JR(πk+1)− JR(πk) ≥ 1 1− γ E s∼dπ k
a∼πk+1
[ Aπ k R (s, a)− 2γ π k+1 R
1− γ
√ 1
2 DKL(πk+1||πk)[s] ] ≥ 1
1− γ E s∼dπ k
a∼πk+1
[ − 2γ πk+1 R
1− γ
√ 1
2 DKL(πk+1||πk)[s] ] ≥ − √ 2δγ π k+1 R
(1− γ)2 .
Again, we have the following constraint violation bound for each policy update:
JC(πk) + 1
1− γ E s∼dπ k
a∼πk+1
[ Aπ k R (s, a) ] ≤ h, (9)
and
JC(πk+1)− JC(πk) ≤ 1 1− γ E s∼dπ k
a∼πk+1
[ Aπ k C (s, a) + 2γ π k+1 C
1− γ
√ 1
2 DKL(πk+1||πk)[s]
] . (10)
Combining Eq. (9) and Eq. (10), we have
JC(πk+1) ≤ h+ 1 1− γ E s∼dπ k
a∼πk+1
[2γ πk+1C 1− γ √ 1 2 DKL(πk+1||πk)[s] ] ≤ h+ √ 2δγ π k+1 C
(1− γ)2 .

heading: S.2 PROOF OF THEOREM 3.2: PERFORMANCE BOUND ON UPDATING THE CONSTRAINT-VIOLATING POLICY

text:
To prove the policy performance bound when the current policy is infeasible (i.e., constraintviolating), we prove the KL divergence between πk and πk+1 for the KL divergence projection. We then prove our main theorem for the worst-case performance degradation.
Lemma S.3. If the current policy πk violates the constraint, the constraint set is closed and convex, the KL divergence constraint for the first step is E s∼dπk [ DKL(π k+ 12 ||πk)[s] ] ≤ δ, where δ is the step size in the reward improvement step, then under the KL divergence projection, we have
E s∼dπk [ DKL(π k+1||πk)[s] ] ≤ δ + b+2αKL,
where αKL . = 1
2aTH−1a , a is the gradient of the cost advantage function, H is the Hessian of the
KL divergence constraint, and b+ .= max(0, JC(πk)− h).
Proof. We define the sublevel set of cost constraint function for the current infeasible policy πk:
Lπ k
= {π | JC(πk) + E s∼dπ k a∼π [Aπ
k
C (s, a)] ≤ JC(πk)}.
This implies that the current policy πk lies in Lπ k , and πk+ 1 2 is projected onto the constraint set:
{π | JC(πk)+E s∼dπ k a∼π [Aπ
k
C (s, a)] ≤ h}. Next, we define the policy π k+1 l as the projection of π k+ 12
onto Lπ k . By the Three-point Lemma, for these three polices πk, πk+1, and πk+1l , with ϕ(x) . = ∑ i xi log xi (this is illustrated in Fig. 6), we have
δ ≥ E s∼dπk [ DKL(π k+1 l ||π k)[s] ] = E s∼dπk [ DKL(π k+1||πk)[s] ]
− E s∼dπk [ DKL(π k+1||πk+1l )[s] ]
+ E s∼dπk [ (∇ϕ(πk)−∇ϕ(πk+1l )) T (πk+1 − πk+1l )[s] ]
⇒ E s∼dπk [ DKL(π k+1||πk)[s] ] ≤ δ + E s∼dπk [ DKL(π k+1||πk+1l )[s] ]
− E s∼dπk [ (∇ϕ(πk)−∇ϕ(πk+1l )) T (πk+1 − πk+1l )[s] ] . (11)
The inequality E s∼dπk [ DKL(π k+1 l ||πk)[s] ] ≤ δ comes from that πk and πk+1l are in Lπ k
, and Lemma S.1.
If the constraint violation of the current policy πk is small, i.e., b+ is small, E s∼dπk [ DKL(π k+1||πk+1l )[s] ] can be approximated by the second order expansion. By the
update rule in Eq. (6), we have
E s∼dπk [ DKL(π k+1||πk+1l )[s] ] ≈ 1
2 (θk+1 − θk+1l ) TH(θk+1 − θk+1l )
= 1
2 ( b+ aTH−1a H−1a )T H ( b+ aTH−1a H−1a )
= b+
2
2aTH−1a
= b+ 2 αKL, (12)
where αKL . = 1
2aTH−1a .
And since δ is small, we have ∇ϕ(πk) −∇ϕ(πk+1l ) ≈ 0 given s. Thus, the third term in Eq. (11) can be eliminated.
Combining Eq. (11) and Eq. (12), we have
Es∼dπk [ DKL(π k+1||πk)[s] ] ≤ δ + b+2αKL.
Now we use Lemma S.3 to prove our main theorem.
Theorem S.4. Define π k+1 R . = max
s ∣∣Ea∼πk+1 [AπkR (s, a)]∣∣, πk+1C .= maxs ∣∣Ea∼πk+1 [AπkC (s, a)]∣∣, b+ . = max(0, JC(πk) − h), and αKL . = 1
2aTH−1a , where a is the gradient of the cost advantage
function andH is the Hessian of the KL divergence constraint. If the current policy πk violates the constraint, then under the KL divergence projection, the lower bound on reward improvement and the upper bound on constraint violation for each policy update are
JR(πk+1)− JR(πk) ≥−
√ 2(δ + b+2αKL)γ πk+1
R
(1− γ)2 ,
and JC(πk+1) ≤ h+
√ 2(δ + b+2αKL)γ πk+1
C
(1− γ)2 ,
where δ is the step size in the reward improvement step.
Proof. Following the same proof in Theorem S.2, we complete the proof.
Note that the bounds we obtain for the infeasibe case; to the best of our knowledge, are new results.

heading: S.3 PROOF OF ANALYTICAL SOLUTION TO PCPO

text:
Theorem S.5. Consider the PCPO problem. In the first step, we optimize the reward:
θk+ 1 2 = argmax θ gT (θ − θk)
s.t. 1
2 (θ − θk)TH(θ − θk) ≤ δ,
and in the second step, we project the policy onto the constraint set:
θk+1 = argmin θ
1 2 (θ − θk+ 12 )TL(θ − θk+ 12 )
s.t. aT (θ − θk) + b ≤ 0,
where g,a,θ ∈ Rn, b, δ ∈ R, δ > 0, and H,L ∈ Rn×n,L = H if using the KL divergence projection, and L = I if using the L2 norm projection. When there is at least one strictly feasible point, the optimal solution satisfies
θk+1 = θk +
√ 2δ
gTH−1g H−1g −max(0,
√ 2δ
gTH−1g aTH−1g + b
aTL−1a )L−1a,
assuming thatH is invertible to get a unique solution.
Proof. For the first problem, sinceH is the Fisher Information matrix, which automatically guarantees it is positive semi-definite. Hence it is a convex program with quadratic inequality constraints. Hence if the primal problem has a feasible point, then Slaters condition is satisfied and strong duality holds. Let θ∗ and λ∗ denote the solutions to the primal and dual problems, respectively. In addition, the primal objective function is continuously differentiable. Hence the Karush-Kuhn-Tucker (KKT) conditions are necessary and sufficient for the optimality of θ∗ and λ∗. We now form the Lagrangian:
L(θ, λ) = −gT (θ − θk) + λ (1 2 (θ − θk)TH(θ − θk)− δ ) .
And we have the following KKT conditions:
−g + λ∗Hθ∗ − λ∗Hθk = 0 ∇θL(θ∗, λ∗) = 0 (13) 1 2 (θ∗ − θk)TH(θ∗ − θk)− δ = 0 ∇λL(θ∗, λ∗) = 0 (14) 1 2 (θ∗ − θk)TH(θ∗ − θk)− δ ≤ 0 primal constraints (15)
λ∗ ≥ 0 dual constraints (16) λ∗ (1 2 (θ∗ − θk)TH(θ∗ − θk)− δ ) = 0 complementary slackness (17)
By Eq. (13), we have θ∗ = θk + 1λ∗H −1g. And by plugging Eq. (13) into Eq. (14), we have λ∗ = √ gTH−1g
2δ . Hence we have our optimal solution:
θk+ 1 2 = θ∗ = θk +
√ 2δ
gTH−1g H−1g, (18)
which also satisfies Eq. (15), Eq. (16), and Eq. (17).
Following the same reasoning, we now form the Lagrangian of the second problem:
L(θ, λ) = 1 2 (θ − θk+ 12 )TL(θ − θk+ 12 ) + λ(aT (θ − θk) + b).
And we have the following KKT conditions:
Lθ∗ −Lθk+ 12 + λ∗a = 0 ∇θL(θ∗, λ∗) = 0 (19) aT (θ∗ − θk) + b = 0 ∇λL(θ∗, λ∗) = 0 (20) aT (θ∗ − θk) + b ≤ 0 primal constraints (21) λ∗ ≥ 0 dual constraints (22) λ∗(aT (θ∗ − θk) + b) = 0 complementary slackness (23)
By Eq. (19), we have θ∗ = θk+1 + λ∗L−1a. And by plugging Eq. (19) into Eq. (20) and Eq. (22),
we have λ∗ = max(0, a T (θk+
1 2−θk)+b
aL−1a ). Hence we have our optimal solution:
θk+1 = θ∗ = θk+ 1 2 −max(0, a
T (θk+ 1 2 − θk) + b
aTL−1aT )L−1a, (24)
which also satisfies Eq. (21) and Eq. (23). Hence by Eq. (18) and Eq. (24), we have
θk+1 = θk +
√ 2δ
gTH−1g H−1g −max(0,
√ 2δ
gTH−1g aTH−1g + b
aTL−1a )L−1a.

heading: S.4 PROOF OF THEOREM 4.1: STATIONARY POINTS OF PCPO WITH THE KL DIVERGENCE AND L2 NORM PROJECTIONS

text:
For our analysis, we make the following assumptions: we minimize the negative reward objective function f : Rn → R (We follow the convention of the literature that authors typically minimize the objective function). The function f is L-smooth and twice continuously differentiable over the closed and convex constraint set C. We have the following lemma to characterize the projection and for the proof of Theorem S.7. (See Fig. 7 for semantic illustration.)
Lemma S.6. For any θ, θ∗ = ProjLC (θ) if and only if (θ − θ∗)TL(θ′ − θ∗) ≤ 0,∀θ′ ∈ C, where ProjLC (θ) . = argmin
θ′∈C ||θ − θ′||2L, and L = H if using the KL divergence projection, and L = I if
using the L2 norm projection.
Proof. (⇒) Let θ∗ = ProjLC (θ) for a given θ 6∈ C, θ′ ∈ C be such that θ′ 6= θ∗, and α ∈ (0, 1). Then we have
||θ − θ∗||2L ≤ ||θ − ( θ∗ + α(θ′ − θ∗) ) ||2L
= ||θ − θ∗||2L + α2||θ′ − θ∗||2L − 2α(θ − θ∗)TL(θ′ − θ∗)
⇒ (θ − θ∗)TL(θ′ − θ∗) ≤ α 2 ||θ′ − θ∗||2L. (25)
Since the right hand side of Eq. (25) can be made arbitrarily small for a given α, and hence we have:
(θ − θ∗)TL(θ′ − θ∗) ≤ 0,∀θ′ ∈ C.
(⇐) Let θ∗ ∈ C be such that (θ − θ∗)TL(θ′ − θ∗) ≤ 0,∀θ′ ∈ C. We show that θ∗ must be the optimal solution. Let θ′ ∈ C and θ′ 6= θ∗. Then we have ||θ − θ′||2L − ||θ − θ∗||2L = ||θ − θ∗ + θ∗ − θ′||2L − ||θ − θ∗||2L
= ||θ − θ∗||2L + ||θ′ − θ∗||2L − 2(θ − θ∗)TL(θ′ − θ∗)− ||θ − θ∗||2L > 0
⇒ ||θ − θ′||2L > ||θ − θ∗||2L.
Hence, θ∗ is the optimal solution to the optimization problem, and θ∗ = ProjLC (θ).
Based on Lemma S.6, we have the following theorem. Theorem S.7. Let η .= √
2δ gTH−1g in Eq. (6), where δ is the step size for reward improvement, g is
the gradient of f,H is the Fisher information matrix. Let σmax(H) be the largest singular value of H, and a be the gradient of cost advantage function in Eq. (6). Then PCPO with the KL divergence projection converges to stationary points with g ∈ −a (i.e., the gradient of f belongs to the negative gradient of the cost advantage function). The objective value changes by
f(θk+1) ≤ f(θk) + ||θk+1 − θk||2− 1ηH+L2 I . (26)
PCPO with the L2 norm projection converges to stationary points with H−1g ∈ −a (i.e., the product of the inverse ofH and gradient of f belongs to the negative gradient of the cost advantage function). If σmax(H) ≤ 1, then the objective value changes by
f(θk+1) ≤ f(θk) + (L 2 − 1 η )||θk+1 − θk||22. (27)
Proof. The proof of the theorem is based on working in a Hilbert space and the non-expansive property of the projection. We first prove stationary points for PCPO with the KL divergence and L2 norm projections, and then prove the change of the objective value.
When in stationary points θ∗, we have
θ∗ = θ∗ −
√ 2δ
gTH−1g H−1g −max(0,
√ 2δ
gTH−1g aTH−1g + b
aTL−1a )L−1a.
⇔
√ 2δ
gTH−1g H−1g = −max(0,
√ 2δ
gTH−1g aTH−1g + b
aTL−1a )L−1a
⇔H−1g ∈ −L−1a. (28)
For the KL divergence projection (L = H), Eq. (28) boils down to g ∈ −a, and for the L2 norm projection (L = I), Eq. (28) is equivalent toH−1g ∈ −a. Now we prove the second part of the theorem. Based on Lemma S.6, for the KL divergence projection, we have
(θk − θk+1)TH(θk − ηH−1g − θk+1) ≤ 0
⇒ gT (θk+1 − θk) ≤ −1 η ||θk+1 − θk||2H . (29)
By Eq. (29), and L-smooth continuous function f, we have
f(θk+1) ≤ f(θk) + gT (θk+1 − θk) + L 2 ||θk+1 − θk||22
≤ f(θk)− 1 η ||θk+1 − θk||2H + L 2 ||θk+1 − θk||22
= f(θk) + (θk+1 − θk)T (−1 η H + L 2 I)(θk+1 − θk)
= f(θk) + ||θk+1 − θk||2− 1ηH+L2 I .
For the L2 norm projection, we have (θk − θk+1)T (θk − ηH−1g − θk+1) ≤ 0
⇒ gTH−1(θk+1 − θk) ≤ −1 η ||θk+1 − θk||22. (30)
By Eq. (30), L-smooth continuous function f, and if σmax(H) ≤ 1, we have
f(θk+1) ≤ f(θk) + gT (θk+1 − θk) + L 2 ||θk+1 − θk||22
≤ f(θk) + (L 2 − 1 η )||θk+1 − θk||22.
To see why we need the assumption of σmax(H) ≤ 1, we defineH = UΣUT as the singular value decomposition ofH with ui being the column vector of U . Then we have
gTH−1(θk+1 − θk) = gTUΣ−1UT (θk+1 − θk) = gT ( ∑ i 1 σi(H) uiu T i )(θ k+1 − θk)
= ∑ i 1 σi(H) gT (θk+1 − θk).
If we want to have
gT (θk+1 − θk) ≤ gTH−1(θk+1 − θk) ≤ −1 η ||θk+1 − θk||22,
then every singular value σi(H) of H needs to be smaller than 1, and hence σmax(H) ≤ 1, which justifies the assumption we use to prove the bound.
To make the objective value for PCPO with the KL divergence projection improves, the right hand side of Eq. (26) needs to be negative. Hence we have Lη2 I ≺ H, implying that σmin(H) > Lη 2 . And to make the objective value for PCPO with the L2 norm projection improves, the right hand side of Eq. (27) needs to be negative. Hence we have η < 2L , implying that
η =
√ 2δ
gTH−1g <
2
L
⇒ 2δ gTH−1g < 4 L2
⇒g TH−1g 2δ > L2 4 ⇒L 2δ
2 < gTH−1g
≤ ||g||2||H−1g||2 ≤ ||g||2||H−1||2||g||2 = σmax(H
−1)||g||22 = σmin(H)||g||22
⇒σmin(H) > L2δ
2||g||22 . (31)
By the definition of the condition number and Eq. (31), we have 1
σmin(H) < 2||g||22 L2δ
⇒ σmax(H) σmin(H) < 2||g||22σmax(H) L2δ
≤ 2||g|| 2 2
L2δ ,
which justifies what we discuss.

heading: S.5 ADDITIONAL COMPUTATIONAL EXPERIMENTS

text:
S.5.1 IMPLEMENTATION DETAILS
For detailed explanation of the task in Achiam et al. (2017), please refer to the appendix of Achiam et al. (2017). For detailed explanation of the task in Vinitsky et al. (2018), please refer to Vinitsky et al. (2018).
We use neural networks that take the input of state, and output the mean and variance to be the Gaussian policy in all experiments. For the simulations in the gather and circle tasks, we use a neural network with two hidden layers of size (64, 32). For the simulations in the grid and bottleneck tasks, we use a neural network with two hidden layers of size (16, 16) and (50, 25), respectively. We use tanh as the activation function of the neural network.
We use GAE-λ approach (Schulman et al., 2015b) to estimate AπR(s, a) and A π C(s, a). For the simulations in the gather and circle tasks, we use neural network baselines with the same architecture and activation functions as the policy networks. For the simulations in the grid and bottleneck tasks, we use linear baselines.
The hyperparameters of each task for all algorithms are as follows (PC: point circle, PG: point gather, AC: ant circle, AG: ant gather, Gr: grid, and BN: bottleneck tasks):
Parameter PC PG AC AG Gr BN discount factor γ 0.995 0.995 0.995 0.995 0.999 0.999
step size δ 10−4 10−4 10−4 10−4 10−4 10−4
λGAER 0.95 0.95 0.95 0.95 0.97 0.97 λGAEC 1.0 1.0 0.5 0.5 0.5 1.0
Batch size 50,000 50,000 100,000 100,000 10,000 25,000 Rollout length 50 15 500 500 400 500
Cost constraint threshold h 5 0.1 10 0.2 0 0
Note that we do not use a learned model to predict the probability of entering an undesirable state within a fixed time horizon as CPO did for cost shaping.

heading: S.5.2 EXPERIMENT RESULTS

text:
To examine the performance of the algorithms with different metrics, we provide the learning curves of the cumulative constraint value over policy update, and the reward versus the cumulative constraint value for the tested algorithms and task pairs in Section 6 shown in Fig. 8. The second metric enables us to compare the reward difference under the same number of cumulative constraint violation.
Overall, we find that,
(a) CPO has more cumulative constraint violation than PCPO.
(b) PCPO with L2 norm projection has less cumulative constraint violation than KL divergence projection except for the point circle and point gather tasks. This observation suggests that the Fisher information matrix is not well-estimated in the high dimensional policy space, leading to have more constraint violation.
(c) PCPO has more reward improvement compared to CPO under the same number of cumulative constraint violation in point circle, point gather, ant circle, ant gather, and bottleneck task.

heading: S.5.3 CPO WITHOUT LINE SEARCH

text:
Due to approximation errors, CPO performs line search to check whether the updated policy satisfies the trust region and cost constraints. To understand the necessity of line search in CPO, we conducted the experiment with and without line search shown in Fig. 9. The step size δ is set to 0.01. We find that CPO without line search tends to (1) have large reward variance especially in the point circle task, and (2) learn constraint-satisfying policies slightly faster. These observations
suggest that line search is more conservative in optimizing the policies since it usually take smaller steps. However, we conjecture that if using smaller δ, the effect of line search is not significant.

heading: S.5.4 THE TASKS WITH HARDER CONSTRAINTS

text:
To understand the stability of PCPO and CPO when deployed in more constraint-critical tasks, we increase the difficulty of the task by setting the constraint threshold to zero and reduce the safe area. The learning curve of discounted reward and constraint value over policy updates are shown in Fig. 10.
We observe that even with more difficult constraint, PCPO still has more reward improvement and constraint satisfaction than CPO, whereas CPO needs more feasible recovery steps to satisfy the constraint. In addition, we observe that PCPO with L2 norm projection has high constraint variance
in point circle task, suggesting that the reward update direction is not well aligned with the cost update direction. We also observe that PCPO with L2 norm projection converges to a bad local
optimum in terms of reward in point gather task, suggesting that in order to satisfy the constraint, the cost update direction destroys the reward update direction.

heading: S.5.5 SMALLER BATCH SAMPLES

text:
To learn policies under constraints, PCPO and CPO require to have a good estimation of the constraint set. However, PCPO may project the policy onto the space that violates the constraint due to the assumption of approximating the constraint set by linear half space constraint. To understand whether the estimation accuracy of the constraint set affects the performance, we conducted the experiments with batch sample size reducing to 1% of the previous experiments (only 500 samples for each policy update) shown in Fig. 11.
We find that smaller training samples affects the performance of the algorithm, creating more reward and cost fluctuation. However, we observe that even with smaller training samples, PCPO still has more reward improvement and constraint satisfaction than CPO.

heading: S.6 ANALYSIS OF THE APPROXIMATION ERROR AND THE COMPUTATIONAL COST OF THE CONJUGATE GRADIENT METHOD

text:
In the Grid task, we observe that PCPO with KL divergence projection does worse in reward than TRPO, which is expected since TRPO ignores constraints. However, TRPO actually outperforms PCPO with KL divergence projection in terms of constraint, which is unexpected since by trying to consider the constraint, PCPO with KL divergence projection has made constraint satisfaction worse.
The reason for this observation is that the Fisher information matrix is ill-conditioned, i.e., the condition number λmax(H)/λmin(H) (λmax is the largest eigenvalue of the matrix) of the Fisher information matrix is large, causing conjugate gradient method that computes constraint update direction H−1a with small number of iteration output the inaccurate approximation. Hence the inaccurate
approximation ofH−1a cause PCPO with KL divergence projection have more constraint violation than TRPO.
To solve this issue, one can have more epochs of conjugate gradient method. This is because that the convergence of conjugate gradient method is controlled by the condition number (Shewchuk, 1994); the larger the condition number is, the more epochs the algorithm needs to get accurate approximation. In our experiments, we set the number of iteration of conjugate gradient method to be 10 to tradeoff between the computational efficiency and the accuracy across all tested algorithms and task pairs.
To verify our observation, we compare the condition number of the Fisher information matrix, and the approximation error of the constraint update direction over training epochs with different number of iteration of the conjugate gradient method shown in Fig. 12.
We observe that the Fisher information matrix is ill-conditioned, and the one with larger number of iteration has less error and more constraint satisfaction. This observation confirms our discussion.

heading: S.7 COMPARISON OF OPTIMIZATION PATHS OF PCPO WITH KL DIVERGENCE AND L2 NORM PROJECTIONS

text:
Theorem 4.1 states that a stationary point of PCPO with KL divergence projection is different from the one of PCPO with L2 norm projection. See Fig. 13 for illustration. To compare both stationary points, we consider the following example shown in Fig. 14. We maximize a non-convex function f(x) = xT diag(y)x subject to the constraint xT1 ≤ −1, where y = [5,−1]T , and 1 is an all-one vector. An optimal solution to this constrained optimization problem is infinity. Fig. 14(a) shows the update direction that combines the objective and the cost constraint update directions for both projections. It shows that PCPO with KL divergence projection has stationary points with g ∈ −a in the boundary of the constraint set (observe that the update direction is zero for PCPO with KL divergence projection at x = [0.75,−1.75]T , [0.25,−1.25]T , and [−0.25,−0.75]T ), whereas PCPO with L2 norm projection does not have stationary points in the boundary of the constraint set. Furthermore, Fig. 14(b) shows the optimization paths for both projections with one initial starting point. It shows that starting at the initial point [0.5,−2.0]T , PCPO with KL divergence projection with the initial point [0.5,−2.0]T converges to a local optimum, whereas L2 norm projection converges to
infinity. However, the above example does not necessary means that PCPO with L2 norm projection always find a better optimum. For example, if the gradient direction of the objective is zero in the constraint set or in the boundary, then both projections may converge to the same stationary point.

title: PROJECTION-BASED CONSTRAINED POLICY OPTIMIZATION