summaries: The authors propose a framework where one component is an attacker network that keeps learning about how to perturb the loss more, and one component is a defense network that robustify learning with respect to the attacker network. The framework is flexible on how the attacker network can be trained, and advances over previous works where the attacker is a human-designed algorithm rather than a learning model. Experiment results show that the framework reaches superior defense performance. The authors also extend the framework to help imitation learning.

summaries: In general, this paper follows the min-max training framework for adversarial robustness. Instead of using a gradient-based attack to solve the inner maximization, the authors use a neural network to learn the attack results. From the experimental results, this method can effectively defend against CW and PGD on CIFAR-10 and CIFAR-100. But the clean accuracy is lower than Madry et al.

summaries: The paper proposes a new way of adversarial training by placing another neural network called "attacker" network, and let the attacker to learn how to generate adversarial examples during training. This training scheme is formulated to solving a joint training according to min-max problem. Experimental results show that the method outperforms existing adversarial training in CIFAR-10/100 once the gradient information can be provided into the attacker network.

abstractText: Adversarial training provides a principled approach for training robust neural networks. From an optimization perspective, the adversarial training is essentially solving a minimax robust optimization problem. The outer minimization is trying to learn a robust classifier, while the inner maximization is trying to generate adversarial samples. Unfortunately, such a minimax problem is very difficult to solve due to the lack of convex-concave structure. This work proposes a new adversarial training method based on a generic learning-to-learn (L2L) framework. Specifically, instead of applying the existing hand-designed algorithms for the inner problem, we learn an optimizer, which is parametrized as a convolutional neural network. At the same time, a robust classifier is learned to defense the adversarial attack generated by the learned optimizer. Our experiments over CIFAR-10 and CIFAR-100 datasets demonstrate that the L2L outperforms existing adversarial training methods in both classification accuracy and computational efficiency. Moreover, our L2L framework can be extended to the generative adversarial imitation learning and stabilize the training.

authors:
M. ANDRYCHOWICZ
M. DENIL
S. GOMEZ
M.W. HOFFMAN
D. PFAU
T. SCHAUL
B. SHILLINGFORD
N. DE FREITAS

authors:
A. ATHALYE
N. CARLINI
D. WAGNER

venue: arXiv preprint arXiv:1802.00420 .

authors:
S. BALUJA
I. FISCHER

venue: arXiv preprint arXiv:1703.09387 .

authors:
G. BROCKMAN
V. CHEUNG
L. PETTERSSON
J. SCHNEIDER
J. SCHULMAN
J. TANG
W. ZAREMBA

title: Openai gym

venue: arXiv preprint arXiv:1606.01540 .

authors:
N. CARLINI
A. ATHALYE
N. PAPERNOT
W. BRENDEL
J. RAUBER
D. TSIPRAS
I. GOODFELLOW
A. MADRY

title: On evaluating adversarial robustness

venue: arXiv preprint arXiv:1902.06705 .

authors:
N. CARLINI
D. WAGNER

authors:
DAI B.
HE N.
PAN Y.
BOOTS B.
SONG L.

venue: arXiv preprint arXiv:1607.04579 .

authors:
DONG Y.
LIAO F.
PANG T.
SU H.
ZHU J.
HU X.
LI J.

title: Boosting adversarial attacks with momentum

authors:
C. FINN
P. ABBEEL
S. LEVINE

venue: arXiv preprint arXiv:1703.03400 .

authors:
R. GIRSHICK
J. DONAHUE
T. DARRELL
J. MALIK

authors:
I. GOODFELLOW
J. POUGET-ABADIE
M. MIRZA
B. XU
D. WARDE-FARLEY
S. OZAIR
A. COURVILLE
Y. BENGIO

title: Generative adversarial nets

authors:
I.J. GOODFELLOW
J. SHLENS
C. SZEGEDY

title: Explaining and harnessing adversarial examples

venue: arXiv preprint arXiv:1412.6572 .

authors:
HE K.
ZHANG X.
REN S.
SUN J.

title: Deep residual learning for image recognition

authors:
M. HEUSEL
H. RAMSAUER
T. UNTERTHINER
B. NESSLER
S. HOCHREITER

authors:
J. HO
S. ERMON

title: Generative adversarial imitation learning

authors:
S. HOCHREITER
A.S. YOUNGER
P.R. CONWELL

title: Learning to learn using gradient descent

authors:
D. KINGMA
J. BA

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980 .

authors:
A. KRIZHEVSKY
G. HINTON

venue: Tech. rep., Citeseer.

authors:
A. KROGH
J.A. HERTZ

title: A simple weight decay can improve generalization

authors:
A. KURAKIN
I. GOODFELLOW
S. BENGIO

title: Adversarial machine learning at scale

venue: arXiv preprint arXiv:1611.01236 .

authors:
T. LIU
Z. CHEN
E. ZHOU
T. ZHAO

venue: arXiv preprint arXiv:1802.05155 .

authors:
W. LIU
ZHANG
LI Y.-M.
YU X.
DAI Z.
B.
T. ZHAO
L. SONG

title: Deep hyperspherical learning

authors:
Y. LIU
X. CHEN
C. LIU
D. SONG

venue: arXiv preprint arXiv:1611.02770 .

authors:
A. MADRY
A. MAKELOV
L. SCHMIDT
D. TSIPRAS
A. VLADU

venue: arXiv preprint arXiv:1706.06083 .

authors:
T. MIYATO
T. KATAOKA
M. KOYAMA
Y. YOSHIDA

authors:
A. NGUYEN
J. YOSINSKI
J. CLUNE

authors:
A. PASZKE
S. GROSS
S. CHINTALA
G. CHANAN
E. YANG
Z. DEVITO
Z. LIN
A. DESMAISON
L. ANTIGA
A. LERER

title: Automatic differentiation in pytorch

authors:
P. SAMANGOUEI
M. KABKAB
R. CHELLAPPA

venue: arXiv preprint arXiv:1805.06605 .

venue: hook. Ph.D. thesis,

venue: Neural Computation 4 131–139.

title: A neural network that embeds its own meta-levels

authors:
J. SCHULMAN
S. LEVINE
P. ABBEEL
M. JORDAN
P. MORITZ

title: Trust region policy optimization

venue: International conference on machine learning.

authors:
C. SZEGEDY
W. ZAREMBA
I. SUTSKEVER
J. BRUNA
D. ERHAN
I. GOODFELLOW
R. FERGUS

title: Intriguing properties of neural networks

venue: arXiv preprint arXiv:1312.6199 .

authors:
P. TABACOF
E. VALLE

title: Exploring the space of adversarial images

authors:
Y. TAIGMAN
M. YANG
M. RANZATO
L. WOLF

authors:
XIAO C.
LI B.
ZHU
J.-Y. HE
W. LIU
M.
SONG D.

venue: arXiv preprint arXiv:1801.02610 .

authors:
A.S. YOUNGER
S. HOCHREITER
P.R. CONWELL

title: Meta-learning with backpropagation

authors:
S. ZAGORUYKO
N. KOMODAKIS

title: Wide residual networks

venue: arXiv preprint arXiv:1605.07146 .

authors:
H. ZHANG
Y. YU
J. JIAO
E.P. XING
L.E. GHAOUI
M.I. JORDAN

venue: arXiv preprint arXiv:1901.08573 .

authors:
S. ZHENG
Y. SONG
T. LEUNG
I. GOODFELLOW

title: Improving the robustness

heading: 1 INTRODUCTION

text:
This decade has witnessed great breakthroughs in deep learning in a variety of applications, such as computer vision (Taigman et al., 2014; Girshick et al., 2014; He et al., 2016; Liu et al., 2017). Recent studies (Szegedy et al., 2013), however, show that most of these deep learning models are very vulnerable to adversarial attacks. Specifically, by injecting a small perturbation to a normal sample, one can obtain an adversarial example. Although the adversarial example is semantically indistinguishable from the normal one, it can fool deep learning models and undermine the security of deep learning, causing reliability problems in autonomous driving, biometric authentication, etc.
Researchers have devoted many efforts to studying efficient adversarial attack and defense (Szegedy et al., 2013; Goodfellow et al., 2014b; Nguyen et al., 2015; Zheng et al., 2016; Madry et al., 2017; Carlini and Wagner, 2017). There is a growing body of work on generating adversarial examples, e.g., fast gradient sign method (FGSM, Goodfellow et al. (2014b)), projected gradient method (PGM, Kurakin et al. (2016)), Carlini-Wagner (CW, Paszke et al. (2017)) etc. As for defense, Goodfellow et al. (2014b) propose to robustify the network by adversarial training, which trains over the adversarial examples and still requires the network to output the correct label. Further, Madry et al. (2017) formalize the adversarial training as the following minimax optimization problem:
minθ 1 n ∑n i=1 [ maxδi∈B `(f(xi + δi;θ), yi) ] , (1)
where {(xi, yi)}ni=1 ⊂ Rd × Y are n pairs of input feature and the corresponding label, ` denotes a loss function, f(·;θ) denotes the neural network with parameter θ, and δi ∈ B denotes the perturbation for xi in constraint B. The existing literature on the optimization also refers to θ as the primal variable and δi’s as the dual variables. Different from the well-studied convex-concave problem1, problem (1) is very challenging since ` is nonconvex in θ and nonconcave in δ. As a result, there may be many equilibria, and majority of them are unstable. In the existing optimization literature, there is no algorithm to converge to a stable equilibrium with theoretical guarantees. Empirically, the existing primal-dual algorithms may perform poorly for solving (1).
Minimax formulation (1) naturally provides us with a unified perspective on prior works of adversarial training. Such a minimax problem consists of two optimization problems, an inner maximization problem and an outer minimization problem: The inner problem targets on finding an optimal attack
1Loss function `(θ; δ) is convex in primal variable θ and concave in dual variable δ.
for a given data point (x, y) maximizing the loss, which essentially is the adversarial attack; The outer problem aims to find a θ so that the loss given by the inner problem is minimized.
For solving (1), Goodfellow et al. (2014b) propose to use FGSM to solve the inner problem. Kurakin et al. (2016) then find that FGSM with true label predicted suffers from a “label leaking” effect, which can ruin the adversarial training. Madry et al. (2017) further suggest to solve the inner problem by PGM and obtain a better result than FGSM, since FGSM essentially is one iteration PGM. However, adversarial training needs to find a δi for each (xi, yi), thus the dimension of the overall search space for all data is substantial, which makes the computation expensive.
Instead, we propose a new learning-to-learn (L2L) framework that provides a more principled and efficient way for adversarial training. Specifically, we parameterize the optimizer of the inner maximization problem by a neural network denoted by g(A(x, y,θ);φ), where A(x, y,θ) denotes the input of the optimizer g. We also call the optimizer as the attacker network. Since the neural network is very powerful in function approximation, our parameterization ensures that g is able to yield strong adversarial perturbations. Under our framework, instead of directly solving δi, we update the parameter φ of g. Our training procedure becomes updating the parameters of two neural networks, which is very similar to generative adversarial network (GAN, Goodfellow et al. (2014a)). The proposed L2L is a generic framework and can be extended to other minimax optimization problems, e.g., generative adversarial imitation learning, which is studied in Section 4.
Different from the hand-designed methods that compute the adversarial perturbation for each individual sample using gradients from backpropagation, our methods generate the perturbations for all samples through the shared attacker g. This enables the attacker g to learn potential common structures of the perturbations. Therefore, our method is capable of yielding strong perturbations and accelerating the training process. Furthermore, L2L framework is very flexible: we can either choose different inputA(x, y,θ), or use different attacker architecture. For example, we can include gradient information in A(x, y,θ) and use a recurrent neural network (RNN) to mimic multi-step gradient-type methods. Instead of simply computing the high order information with finite difference approximation or multiple gradients, by parameterizing the algorithm as a neural network, our proposed methods can capture this information in a much smarter way (Finn et al., 2017). Our experiments demonstrate that our proposed methods not only outperform existing adversarial training methods, e.g., PGM training, but also enjoy the computational efficiency over CIFAR-10 and CIFAR-100 datasets (Krizhevsky and Hinton, 2009).
The research on L2L has a long history (Schmidhuber, 1987; 1992; 1993; Younger et al., 2001; Hochreiter et al., 2001; Andrychowicz et al., 2016). The basic idea is that one first models the updating formula of complicated optimization algorithms in a parametric form, and then uses some simple algorithms, e.g., stochastic gradient algorithm to learn the parameters of the optimizer. Among existing works, Hochreiter et al. (2001) propose a system allowing the output of backpropagation from one network to feed into an additional learning network, with both networks trained jointly; Based on this, Andrychowicz et al. (2016) further show that the design of an optimization algorithm can be cast as a learning problem. Specifically, they use long short-term memory RNNs to model the algorithm and allow the RNNs to exploit structure in the problems of interest in an automatic way, which is undoubtedly one of the most popular methods for learning-to-learn.
However, there are two major drawbacks of the existing L2L methods: (1) It requires a large amount of datasets (or a large number of tasks in multi-task learning) to guarantee the learned optimizer to generalize, which significantly limits their applicability (most of the related works only consider the image encoding as the motivating application); (2) The number of layers/iterations in RNNs for modeling algorithms cannot be large to avoid significant computational burden in backpropagation.
Our contribution is that we fill the blank of the L2L framework in solving the minimax problem, and our proposed methods do not suffer from the aforementioned drawbacks: (1) The attacker g with a different φ essentially generates a different task/dataset. Therefore, for adversarial training, we have sufficiently many tasks for learning-to-learn; (2) The inner problem does not need a large scale RNN, and we use a convolutional neural network (CNN) or a length-two RNN (the sequence of length equals 2) as our attacker network, which eases the computation.
Our work is also related to GAN and dual-embedding (Dai et al., 2016). All three solve minimax problems and share some common ground. We discuss these works in Section 5.
Notations. Given a ∈ R, denote (a)+ as max(a, 0). Given x,y ∈ Rd, denote xi as the i-th element of x, ||x||∞ = maxi |xi| as `∞-norm of x, and x◦y = [x1y1, · · · , xdyd]> as element-wise product.
2 METHOD
This paper focuses on `∞-norm attack. We define the `∞-ball with center 0 and radius by B( ) = {δ ∈ Rd : ||δ||∞ ≤ } and the corresponding projection as follows:
ΠB( )(δ) = sign(δ) ◦max(|δ|, ), where sign and max are element-wise operators.

heading: 2.1 ADVERSARIAL TRAINING

text:
The goal of adversarial training is to robustify neural networks. Recall that from a robust optimization perspective, given n samples {(xi, yi)}ni=1, where xi is the i-th feature vector and yi is the corresponding label, adversarial training is reformulated as the following optimization problem (1):
minθ 1 n ∑n i=1 [ maxδi∈B `(f(xi + δi;θ), yi) ] ,
where f denotes the network with parameter θ, ` denotes a loss function, and is the maximum perturbation magnitude.
We first demonstrate the hardness of solving problem (1). Ideally, we want to obtain the optimal solution for the inner problem
δ∗i := argmaxδi∈B `(f(xi + δi;θ), yi).
However, note that the loss function `(f(xi + δi;θ), yi) is highly nonconcave in δi. Therefore, in reality the δi we obtained is very unlikely to be the optimum δ∗i . This then often leads to a highly unreliable or even completely wrong search direction, e.g.,
〈∇θ`(f(xi + δi;θ), yi),∇θ`(f(xi + δ∗i ;θ), yi)〉 < 0, which may further results in a limiting cycle shown in Figure 1 (Detailed discussion is provided in Appendix D). This becomes even worse when sample noises exist.
Algorithm 1 Standard pipeline of adversarial training Input: {(xi, yi)}ni=1: clean data, α: learning rate, N : number of epochs, : maximum perturbation magnitude. for t← 1 to N do
Sample a minibatchMt for i inMt do
δi ← argmaxδi∈B( ) `(f(xi + δi;θ), yi) Generate adversarial perturbation for (xi, yi)
θ ← θ − α 1|Mt| ∑ i∈Mt ∇θ`(f(xi + δi;θ), yi) Update θ over adversarial data {(xi + δi, yi)}i∈Mt In the existing literature, the standard pipeline of adversarial training is shown in Algorithm 1. Since the step of generating adversarial perturbation δi in Algorithm 1 is intractable, most adversarial training methods adopt hand-designed algorithms. For example, Kurakin et al. (2016) propose to solve the inner problem approximately by first order methods such as PGM. Specifically, PGM iteratively updates the adversarial perturbation by the projected sign gradient ascent method for each sample: Given one sample (xi, yi), at the t-th iteration, PGM takes
δti ← ΠB( ) ( δt−1i + η · sign ( ∇x`(f(x̃ti;θ), y) )) , (2)
where x̃ti = xi + δ t−1 i , η is the perturbation step size, T is a pre-defined total number of iterations, and δ0i = 0, t = 1, · · · , T . Finally PGM takes δi = δTi . Note that FGSM essentially is one-iteration PGM. Besides, some works adopt other optimization methods, such as momentum gradient method (Dong et al., 2018), and L-BFGS (Tabacof and Valle, 2016). However, except for FGSM, all require numerous queries for gradients through backpropagation, which is computationally expensive.

heading: 2.2 LEARNING TO DEFENSE BY LEARNING TO ATTACK (L2L)

text:
Since the objective function is nonconvex-nonconcave, there is no guarantee for hand-designed methods to perform well. Instead, we propose to learn an optimizer for the inner problem. Specifically, we parameterize the attacker by a Neural Network g(A(x, y,θ);φ), where A(x, y,θ), the
input of the network g, summaries the information of data and neural network f(·;θ). We then convert problem (1) to
minθ 1 n ∑n i=1 [ `(f(xi + g(A(xi, yi,θ);φ∗);θ), yi) ] , (3)
where φ∗ is defined as the solution to the following optimization problem:
φ∗ ∈ argmax φ
1
n n∑ i=1 `(f(xi + g(A(xi, yi,θ);φ);θ), yi) subject to g(A(x, y,θ);φ) ∈ B( ).
Solving problem (3) naturally consists of two stages. In the first stage, the classifier f aims to fit over all perturbed data; While in the second stage, given a certain f obtained in the first stage, the attacker network g targets on generating optimal perturbations under constraints δi’s ∈ B( ). Since δi = g(A(xi, yi;θ);φ), constraints can be simply handled by a tanh activation function in the last layer of g. Specifically, because the magnitude of tanh output is bounded by 1, after we rescale the output by , the output of g automatically satisfies the constraints.
This framework is very flexible. We can choose different A(x, y,θ) as the input and mimic multi-step gradient algorithms shown in Figure 2. Here we provide three examples:
Naive Attacker Network. This is the simplest example among our methods, taking the original image xi as the input, i.e., A(xi, yi,θ) = xi and δi = g(xi;φ).
Under this setting, L2L training is similar to GAN training. The major difference is that the generator in GAN yields synthetic data by transforming random noises, while the naive attacker network generates perturbations by transforming training samples.
Gradient Attacker Network. Motivated by handdesigned methods, e.g., FGSM, we design an attacker which takes the gradient information into computation. Specifically, we concatenate image xi and gradient ∇x`(f(xi;θ), yi) from backpropagation as the input of g, i.e.,
A(xi, yi,θ) = [ xi,∇x`(f(xi;θ), yi) ] and δi = g ( xi,∇x`(f(xi;θ), yi);φ ) .
Since more information is provided, we expect the attacker network to be more effective to learn and yield more powerful perturbations.
Multi-Step Gradient Attacker Network. We adapt the RNN to mimic a multi-step gradient update. Specifically, we use the gradient attacker network as the cell of RNN sharing the same parameter φ. As we mentioned earlier, the number of layers/iterations in the RNN for modeling algorithms cannot be very large so as to avoid significant computational burden in backpropagation. In this paper, we focus on a
length-two RNN to mimic a two-step gradient update. The corresponding perturbation becomes:
δi = ΠB( ) ( δ (0) i + g ( x̃i,∇x`(f(x̃i, yi;θ);φ )) ,
where x̃i = xi + δ (0) i and δ (0) i = g ( xi,∇x`(f(xi, yi;θ);φ ) .
Taking gradient attacker network as an example, Figure 3 illustrates how L2L works and jointly trains two networks: The first forward pass is used to obtain gradient of the classification loss over clean data; The second forward pass is used to generate perturbation δi by attacker g; The third forward pass is used to calculate the adversarial loss ` in (3). Since our gradient attacker network only needs one backpropagation to query gradient, it amortizes the adversarial training cost, which leads to better computational efficiency. Moreover, L2L may adapt to the underlying optimization problem and yield better solution for the inner problem. The corresponding procedure of L2L is shown in Algorithm 2.
3 EXPERIMENTS Algorithm 2 Learning-to-learn-based adversarial training with gradient attacker network Input: {(xi, yi)}ni=1: clean data, α1, α2: learning rates, N : number of epochs, : maximum perturbation magnitude. for t← 1 to N do
Sample a minibatchMt for i inMt do
ui ← ∇x`(f(xi;θ), yi) δi ← g(xi,ui;φ) Generate perturbation by g
θ ← θ − α1 1|Mt| ∑ i∈Mt ∇θ`(f(xi + δi;θ), yi) Update θ over adversarial data {(xi + δi, yi)}i∈Mt φ← φ+ α2 1|Mt| ∑ i∈Mt ∇φ`(f(xi + δiθ), yi) Update φ over adversarial data {(xi + δi, yi)}i∈Mt
To demonstrate the effectiveness and computational efficiency of our methods, we compare our methods with PGM training over CIFAR-10 and CIFAR-100 datasets. All experiments are done in PyTorch with one NVIDIA 2080 Ti GPU.
For simplicity, we denote Plain Net as the classifier network trained over clean data only, PGM Net as the classifiers with PGM training, and Naive L2L, Grad L2L, and 2-Step L2L as classifiers using L2L training with corresponding attacker networks.
Classifier Network. All experiments adopt a 34-layer wide residual network (WRN-34-10, Zagoruyko and Komodakis (2016)) implemented by Zhang et al. (2019) as the classifier network. For each method, we train the classifier network from scratch. For Plain Nets, we adapt the same training procedure as Zagoruyko and Komodakis (2016). We use cross entropy as the loss function.
Attacker Network. Table 1 presents the architecture of our attacker network2. The ResBlock uses the same structure as the generator proposed in Miyato et al. (2018). The detailed structure of ResBlock is provided in Appendix B. Batch normalization (BN) and activations, e.g., ReLU and tanh, are applied when specified. The tanh function easily makes the output of attacker satisfy the constraints.
White-box and Black-box. We compare different methods under both white-box and black-box settings. Under the white-box setting, attackers can access all parameters of target models and generate adversarial examples based on the models; whereas under the black-box setting, accessing parameters is prohibited. Therefore, we adopt the standard transfer attack method from Liu et al. (2016). Due to the space limit, we leave results of the black-box setting in Appendix A.
Robust Evaluation. We evaluate the robustness of the networks by PGM and CW attacks with the maximum perturbation magnitude = 0.031 (after rescaling the pixels to [0, 1]) over CIFAR-10 and CIFAR-100. For PGM attack, we use 20 and 100-iteration PGM with a perturbation step size η = 0.003, and for each sample we initial the adversary randomly in the `∞ ball of radius centered at the natural sample. For CW attack, we adopt the implementation from Paszke et al. (2017), and set the maximum number of iterations as 100. For each method, we repeat 5 runs with different random initial seed and report the worst result. For CIFAR-10, we also evaluate the robustness of our Grad L2L and 2-Step L2L networks using random attacks, for which we uniformly sample 10000 perturbations in the `∞ ball with radius = 0.031 adding to each test sample. We also evaluate the robustness of our Grad L2L and 2-Step L2L networks under their own attackers.
L2L. To update classifier’s parameter θ, we use the SGD algorithm with Polyak’s momentum (parameter 0.9, Liu et al. (2018)) and weight decay (parameter 2× 10−4, Krogh and Hertz (1992)); To update the attacker’s parameter φ, we use the Adam optimizer (parameter [0.9, 0.999], Kingma and Ba (2014)) and weight decay (parameter 2× 10−4) so that it adaptively balances the inner and outer optimization. In addition, we train the whole network for 100 epochs and set the initial learning rate for SGD as 0.1, the learning rate decay parameter as 0.1 with decay schedule [30,60,90], and the initial learning rate for Adam optimizer as 0.001 without learning rate decay.
2We provide another attacker architecture with down-sampling modules in the Appendix B. With such an attacker, L2L adversarial training is less stable, but much faster.
PGM Adversarial Training. For CIFAR-10, we directly report the result from Madry et al. (2017) as the baseline; For CIFAR-100, we train a PGM Net as a baseline. To update the parameter θ, we use the same configuration of SGD algorithm in L2L. Moreover, we adopt the setting from Madry et al. (2017), that is, we first use 10-iteration PGM with the perturbation step size 0.007 in (2) to generate the adversarial samples, and then train the PGM Net over these samples.
Experiment Results. Table 2 shows the results of all methods over CIFAR-10 and CIFAR-100 under the white-box setting. As can be seen, without gradient information, Naive L2L is vulnerable to the PGM attack. However, when the attacker utilizes the gradient information, Grad L2L and 2-Step L2L significantly outperform the PGM Net over CIFAR-10 and CIFAR100, with a small loss for the clean accuracy. From the experiments on CIFAR10, our Grad L2L and 2-Step L2L are robust to random attacks, where the accuracy is only slightly lower than the clean accuracy. Furthermore, the accuracy of our Grad/2-Step L2L model under the Grad/2Step L2L attacker is comparable to the accuracy under PGM attacks, which shows
that L2L attackers are able to generate strong attacks. As can be seen, PGM-100 is stronger than Grad L2L attacker (47.72% vs. 49.68%), but similar to the 2-Step L2L attacker (52.07% vs. 52.71%). This means the strength of 2-Step L2L attacker is much stronger than Grad L2L attacker and explains why 2-Step L2L is stronger than Grad L2L and PGM net. In addition, Table 3 shows the one epoch running time of all methods over CIFAR-10 and CIFAR-100. As can be seen, Grad L2L and 2-Step L2L is much faster than PGM Net. By further comparing the accuracy of Grad/2Step L2L and PGM Net in Table 2, we find that L2L enjoys computational efficiency. In addition,
Figure 4 presents the robust accuracy against number of iterations (fixed perturbation magnitude = 0.031) and perturbation magnitude (fixed number of iterations T = 10). As can be seen, 2-Step L2L is much more robust than PGM Net.
Visualization of Adversarial Examples. Figure 5 provides an illustrative example of the adversarial perturbations generated by FGSM, PGM-20 and 2-Step L2L attacker for a cat over CIFAR-10. As can be seen, the attacks for these two networks are very different. Moreover, the perturbation generated by the 2-Step L2L attacker is much more smooth than FGSM and PGM. In this example, 2-Step L2L labels all adversarial samples correctly; whereas the PGM Net is fooled by the PGM-20 attack and misclassifies it as a dog.

heading: 4 EXTENSION: GENERATIVE ADVERSARIAL IMITATION LEARNING

text:
Our proposed L2L is a generic framework and can be applied to a broad class of minimax optimization problems. Here, we investigate the generative adversarial imitation learning (GAIL, Ho and Ermon (2016)). GAIL aims to learn a policy from expert’s behavior, by recovering the expert’s cost function and extracting a policy from the recovered cost function, which can also be formulated as a minimax optimization problem. We then show that under the L2L framework, we stabilize the GAIL training by replacing the inner optimizer with a neural network.
Original GAIL. GAIL solves the following minimax optimization problem: min θπ max θD Es,a∼π(s;θπ)[log (D(s, a; θD))] + Es̃,ã∼πE [log(1−D(s̃, ã; θD))]− λH(π), (4) where π(·; θπ) is the trained policy parameterized by θπ , πE denotes the expert policy, D(·, ·; θD) is the discriminator parameterized by θD, λH(π) denotes a entropy regularizer with tuning parameter λ, (s, a) and (s̃, ã) denote the state-action for the trained policy and expert policy, respectively. By optimizing 4, the discriminator D distinguishes the state-action (s, a) generated from the learned policy π with the sampled trajectories (s̃, ã) generated from some expert policy πE. In the original GAIL training, for each iteration, we update the parameter of D, θD, by stochastic gradient ascend and then update θπ by the trust region policy optimization (TRPO, Schulman et al. (2015)).
GAIL with L2L. Similar to the adversarial training with L2L, we apply our L2L framework to GAIL by parameterizing the inner optimizer as a neural network U(; θU) with parameter θU. Its input contains two parts: parameter θD and the gradient of loss function with respect to θD:
gD(θD, θπ) = Es,a∼π(s;θπ)[∇θD log (D(s, a; θD))] + Es̃,ã∼πE [∇θD log(1−D(s̃, ã; θD))]. In practice, we use a minibatch (several sample trajectories) to estimate gD(θD, θπ), denoted as ĝD(θD, θπ). Specifically, at the t-th iteration, we first calculate ĝtD = ĝD(θ t D, θ t π) and then update θt+1D = U(θ t D, ĝ t D; θ t U). Next, we update θU by gradient ascend based on the sample estimate of Es,a∼π(s;θtπ)[∇θU log (D(s, a;U(θ t D, ĝ t D; θ t U)))] + Es̃,ã∼πE [∇θU log(1−D(s̃, ã;U(θtD, ĝtD; θtU)))]. The detailed algorithm is presented in Appendix C.
Experiments. We compare the performance of the original GAIL and GAIL with L2L on two simulated environments: CartPole and Mountain Car (Brockman et al., 2016). As can be seen in
Figure 6, we find that GAIL has a sudden performance drop after training for a long time. We conjecture that this is because the discriminator overfits the expert trajectories and converges to a bad optimum, which is not generalizable. On the other hand, GAIL with L2L is much more stable. It is very important to real applications of GAIL: since the reward in real-world environment is usually unaccessible, we cannot know whether there is a sudden performance drop or not. With L2L, we can stabilize the training and obtain a much more reliable algorithm for real-world applications.

heading: 5 DISCUSSIONS

text:
Closely related works: • By leveraging the Fenchel duality and feature embedding technique, Dai et al. (2016) convert a learning conditional distribution problem to a minimax problem , which is similar to naive attacker network. Both approaches, however, lack the primal information. In contrast, gradient attacker network considers the gradient information of primal variables, and achieves good results. • Goodfellow et al. (2014a) propose the GAN, which is very similar to our L2L framework. Both GAN and L2L contain one generator network and one classifier network, and jointly train these two networks. There are two major difference between GAN and our framework: (1) GAN aims to transform the random noises to the synthetic data which is similar to the training examples, while ours targets on transforming the training examples to the adversarial examples for robustifying the classifier; (2) Our generator network does not only take the training examples (analogous to the random noise in GAN) as the input, but also exploits the gradient information of the objective function, since it essentially represents an optimization algorithm. The training procedure of these two, however, are quite similar. We adopt some tricks from GAN training to our framework to stabilize training process, e.g., in Grad L2L, we adopt the two-time scale trick (Heusel et al., 2017). • There are some other works simply combining the GAN framework and adversarial training together. For example, Baluja and Fischer (2017) and Xiao et al. (2018) propose some ad hoc GANbased methods to robustify neural networks. Specifically, for generating adversarial examples, they only take training examples as the input of the generator, which lacks the information of the outer mimnimization problem. Instead, our proposed L2L methods (e.g., Grad L2L, 2-step L2L) connect outer and inner problems by delivering the gradient information of the objective function to the generator. This is a very important reason for our performance gain on the benchmark datasets. As a result, the aforementioned GAN-based methods are only robust to simple attacks, e.g., FGSM, on simple data sets, e.g., MNIST, but fail for strong attacks, e.g., PGM and CW, on complicated data sets, e.g. CIFAR, where our L2L methods achieve significantly better performance.
Training Stability: For improving the training stability, we use both clean image and the corresponding gradient as the input of the attacker. Without such gradient information, the attacker severely suffers from training instability, e.g., the Naive Attacker Network. Furthermore, we try another architecture with downsampling modules, called “slim attacker” in Appendix B. We observed that the slim attacker also suffers from training instability. We suspect that the downsampling causes the loss of information. Thus, we tried to enhance the slim attacker by skip layer connections. Although the robust performance is still worse than the proposed architecture, it improves a lot.
Benefits of our neural network approach in adversarial training: (1) Since the neural network has been known to be powerful in function approximation, Our attacker network g can yield strong adversarial perturbations. Since they are generated by the same attacker, the attacker g essentially learns some common structures across all samples; (2) The attacker networks in our experiments are actually overparametrized, which is conjectured to ease the training of deep neural networks. We believe that similar phenomena happen to our attacker network, and ease the adversarial training.

heading: ANDRYCHOWICZ, M., DENIL, M., GOMEZ, S., HOFFMAN, M. W., PFAU, D., SCHAUL, T.,

text:
SHILLINGFORD, B. and DE FREITAS, N. (2016). Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems.
ATHALYE, A., CARLINI, N. and WAGNER, D. (2018). Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. arXiv preprint arXiv:1802.00420 .
BALUJA, S. and FISCHER, I. (2017). Adversarial transformation networks: Learning to generate adversarial examples. arXiv preprint arXiv:1703.09387 .
BROCKMAN, G., CHEUNG, V., PETTERSSON, L., SCHNEIDER, J., SCHULMAN, J., TANG, J. and ZAREMBA, W. (2016). Openai gym. arXiv preprint arXiv:1606.01540 .
CARLINI, N., ATHALYE, A., PAPERNOT, N., BRENDEL, W., RAUBER, J., TSIPRAS, D., GOODFELLOW, I. and MADRY, A. (2019). On evaluating adversarial robustness. arXiv preprint arXiv:1902.06705 .
CARLINI, N. and WAGNER, D. (2017). Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP). IEEE.
DAI, B., HE, N., PAN, Y., BOOTS, B. and SONG, L. (2016). Learning from conditional distributions via dual embeddings. arXiv preprint arXiv:1607.04579 .
DONG, Y., LIAO, F., PANG, T., SU, H., ZHU, J., HU, X. and LI, J. (2018). Boosting adversarial attacks with momentum. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
FINN, C., ABBEEL, P. and LEVINE, S. (2017). Model-agnostic meta-learning for fast adaptation of deep networks. arXiv preprint arXiv:1703.03400 .
GIRSHICK, R., DONAHUE, J., DARRELL, T. and MALIK, J. (2014). Rich feature hierarchies for accurate object detection and semantic segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
GOODFELLOW, I., POUGET-ABADIE, J., MIRZA, M., XU, B., WARDE-FARLEY, D., OZAIR, S., COURVILLE, A. and BENGIO, Y. (2014a). Generative adversarial nets. In Advances in Neural Information Procesing Systems.
GOODFELLOW, I. J., SHLENS, J. and SZEGEDY, C. (2014b). Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572 .
HE, K., ZHANG, X., REN, S. and SUN, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
HEUSEL, M., RAMSAUER, H., UNTERTHINER, T., NESSLER, B. and HOCHREITER, S. (2017). GANs trained by a two time-scale update ReLU converge to a local nash equilibrium. In Advances in Neural Information Processing Systems.
HO, J. and ERMON, S. (2016). Generative adversarial imitation learning. CoRR abs/1606.03476. URL http://arxiv.org/abs/1606.03476
HOCHREITER, S., YOUNGER, A. S. and CONWELL, P. R. (2001). Learning to learn using gradient descent. In International Conference on Artificial Neural Networks. Springer.
KINGMA, D. and BA, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 .
KRIZHEVSKY, A. and HINTON, G. (2009). Learning multiple layers of features from tiny images. Tech. rep., Citeseer.
KROGH, A. and HERTZ, J. A. (1992). A simple weight decay can improve generalization. In Advances in neural information processing systems.
KURAKIN, A., GOODFELLOW, I. and BENGIO, S. (2016). Adversarial machine learning at scale. arXiv preprint arXiv:1611.01236 .
LIU, T., CHEN, Z., ZHOU, E. and ZHAO, T. (2018). Toward deeper understanding of nonconvex stochastic optimization with momentum using diffusion approximations. arXiv preprint arXiv:1802.05155 .
LIU, W., ZHANG, Y.-M., LI, X., YU, Z., DAI, B., ZHAO, T. and SONG, L. (2017). Deep hyperspherical learning. In Advances in Neural Information Processing Systems.
LIU, Y., CHEN, X., LIU, C. and SONG, D. (2016). Delving into transferable adversarial examples and black-box attacks. arXiv preprint arXiv:1611.02770 .
MADRY, A., MAKELOV, A., SCHMIDT, L., TSIPRAS, D. and VLADU, A. (2017). Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.06083 .
MIYATO, T., KATAOKA, T., KOYAMA, M. and YOSHIDA, Y. (2018). Spectral normalization for generative adversarial networks. In International Conference on Learning Representations. URL https://openreview.net/forum?id=B1QRgziT-
NGUYEN, A., YOSINSKI, J. and CLUNE, J. (2015). Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
PASZKE, A., GROSS, S., CHINTALA, S., CHANAN, G., YANG, E., DEVITO, Z., LIN, Z., DESMAISON, A., ANTIGA, L. and LERER, A. (2017). Automatic differentiation in pytorch .
SAMANGOUEI, P., KABKAB, M. and CHELLAPPA, R. (2018). Defense-gan: Protecting classifiers against adversarial attacks using generative models. arXiv preprint arXiv:1805.06605 .
SCHMIDHUBER, J. (1987). Evolutionary principles in self-referential learning, or on learning how to learn: the meta-meta-... hook. Ph.D. thesis, Technische Universität München.
SCHMIDHUBER, J. (1992). Learning to control fast-weight memories: An alternative to dynamic recurrent networks. Neural Computation 4 131–139.
SCHMIDHUBER, J. (1993). A neural network that embeds its own meta-levels. In Neural Networks, 1993., IEEE International Conference on. IEEE.
SCHULMAN, J., LEVINE, S., ABBEEL, P., JORDAN, M. and MORITZ, P. (2015). Trust region policy optimization. In International conference on machine learning.
SZEGEDY, C., ZAREMBA, W., SUTSKEVER, I., BRUNA, J., ERHAN, D., GOODFELLOW, I. and FERGUS, R. (2013). Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199 .
TABACOF, P. and VALLE, E. (2016). Exploring the space of adversarial images. In 2016 International Joint Conference on Neural Networks (IJCNN). IEEE.
TAIGMAN, Y., YANG, M., RANZATO, M. and WOLF, L. (2014). Deepface: Closing the gap to human-level performance in face verification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
XIAO, C., LI, B., ZHU, J.-Y., HE, W., LIU, M. and SONG, D. (2018). Generating adversarial examples with adversarial networks. arXiv preprint arXiv:1801.02610 .
YOUNGER, A. S., HOCHREITER, S. and CONWELL, P. R. (2001). Meta-learning with backpropagation. In Neural Networks, 2001. Proceedings. IJCNN’01. International Joint Conference on, vol. 3. IEEE.
ZAGORUYKO, S. and KOMODAKIS, N. (2016). Wide residual networks. arXiv preprint arXiv:1605.07146 .
ZHANG, H., YU, Y., JIAO, J., XING, E. P., GHAOUI, L. E. and JORDAN, M. I. (2019). Theoretically principled trade-off between robustness and accuracy. arXiv preprint arXiv:1901.08573 .
ZHENG, S., SONG, Y., LEUNG, T. and GOODFELLOW, I. (2016). Improving the robustness of deep neural networks via stability training. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.

heading: Appendix

heading: A BLACK-BOX ATTACK

text:
Under the black-box setting, we first train a surrogate model with the same architecture of the target model but a different random seed, and then attackers generate adversarial examples to attack the target model by querying gradients from the surrogate model.
The black-box attack highly relies on the transferability, which is the property that the adversarial examples of one model are likely to fool others. However, the transferred attack is very unstable, and often has a large variation in its effectiveness. Therefore, results of the black-box setting might not be reliable and effective. Thus we only present one result here to demonstrate the robustness of different models.

heading: B SLIM NETWORK

text:
Table 7 presents another architecture that we used in the L2L. In this network, the second convolutional layer uses downsampling, while the second last deconvolutional layer uses upsampling. Due to the downsampling, this network is computationally cheap and thus it is computationally fast. For example the running time of per epoch for L2L with slim attacker is 480; whereas L2L with the original architecture is 620. However, it loses some information of input and is less stable than the original architecture (Table 1). Inspired by residual learning in He et al. (2016), we address the above issues by using a skip layer connection to ease the training of this network. Specifically, the last layer takes the concatenation of A(x, y,θ) and the output of the second last layer as input. Figure 7 presents the architecture of ResBlocks. PReLU is a special type of Leaky ReLU with a learnable slope parameter.
Table 8 shows the results of L2L with the architecture shown in Table 7.

heading: C GENERATIVE ADVERSARIAL IMITATION LEARNING

heading: C.1 ALGORITHMS

text:
Algorithm 3 Learning-to-learn-based generative adversarial imitation learning Input: Expert trajectories (s̃, ã ∼ πE(s̃)), initial policy, discriminator and updater parameters θπ, θD, θU. for t← 1 to N do
Sample trajectories (s, a ∼ π(a; θπ)) Compute gradient: gtD ← 1|(s,a)| ∑ (s,a)[∇θD log (D(s, a; θtD))] + 1|(s̃,ã)| ∑ (s̃,ã)[∇θD log(1−D(s̃, ã; θtD))] Update the discriminator parameters: θt+1D = U(θ t D, g t D; θ t U). Update the updater parameters θU by minimizing: 1
|(s,a)| ∑ (s,a)[log (D(s, a;U(θ t D, g t D; θ t U)))] + 1 |(s̃,ã)| ∑ (s̃,ã)[log(1−D(s̃, ã;U(θtD, gtD; θtU)))]. Update the policy parameters θπ by a policy step using the TRPO rule (Ho and Ermon (2016))

heading: C.2 EXPERIMENT SETTING

text:
Updater Architecture We use simple 3-layer perceptron with a skip layer as our updater. The number hidden units are (2m→ 8m→ 4m→ m), wherem is the dimension of θD that depends on the original task. For the first and the second layer, we use PReLu as the activation function, while the last layer has no activation function. Finally we add the output to θD in the original input as the updated parameter for the discriminator network.
Hyperparameter Settings For all baselines we exactly follows the setting in Ho and Ermon (2016), except that we use a 2-layer discriminator with number of hidden units ((s, a) → 64 → 32 → 1) using tanh as the activation. We use the same neural network architecture for π and the same optimizer configuration. The expert trajectories are obtained by an expert trained using TRPO. For L2L based GAIL, we also use Adam optimizer to update the θU with the same configuration as updating θD in original GAIL.

heading: D LIMITING CYCLE

text:
Limiting cycle is a well-known issue for minimax machine learning problem [4,5]. The reason behind limiting cycle is that different from minimization problems, a minimax optimization problem is more complicated and can be highly nonconvex-nonconcave, where the inner problem can not be solved exactly. Here we provide a concrete example: we consider the following optimization problem:
min x max y f(x, y) = xy.
Then at the t-th iteration, the update direction will be (−yt, xt). If we start from (1, 0) with a stepsize of 0.0001, this update will result in a limiting circle: x2 +y2 = 1 and never reach the stable equilibrium (0, 0) as shown in Figure 8.

heading: E ROBUSTNESS EVALUATION CHECKLIST

text:
Recently, there are many works on robustness defense that have been proven ineffective (Athalye et al., 2018; Carlini et al., 2019). Our work follows the most reliable and widely used robust model
approach — adversarial training, which finds a set parameters to make the model robust. We do not make any modification to final classifier model. Unlike previous works (e.g. Defense-GAN, Samangouei et al. (2018)), our model does not take the attacker as a part of the final model and does not use shattered/obfuscated/masked gradient as a defense mechanism. We also demonstrate that the evaluation of the robustness of our proposed L2L method is trustworthy by verifying all items listed in (Carlini et al., 2019).

heading: E.1 SHATTERED/OBFUSCATED/MASKED GRADIENT

text:
In this section we verify that our proposed L2L method does not fall into the pitfall of shattered/obfuscated/masked gradient, which have proven ineffective. To see this, we checked every item recommended in section 3.1 of Athalye et al. (2018):
• One-step attacks perform better than iterative attacks: Figure 4 shows that the PGM attack is stronger with larger number of iterations.
• Black-box attacks are better than white-box attacks: Appendix A shows that the black-box transfer attack is much weaker than white white-box attacks.
• Unbounded attacks do not reach 100% success: We evaluate the model robustness against attack with extremely large perturbation to show that unbounded attacks do reach 100% success. Specifically, we use the PGM-10 attack with various perturbation magnitudes ∈ [0, 1] and stepsize 10 . Figure 9 shows that the PGM attack eventually reach 100% success as the perturbation magnitude increases.
• Random sampling finds adversarial examples: In Table 2, we show that random search is not better than gradient-based method and is rather weak against our model.
• Increasing distortion bound does not increase success: Figure 4 shows that the PGM attack becomes stronger as the perturbation magnitude increases.

heading: E.2 ROBUSTNESS EVALUATION CHECKLIST

text:
Carlini et al. (2019) also provide an evaluation checklist, and we now check each of common severe flaws and common pitfalls as follows:
• State a precise threat model: We do not have any adversary detector; We do not use shattered/Obfuscated/Masked gradient. We do not have a denoiser. Our model has no aware of the attack mechanism, including PGM and CW attacks.
• Adaptive attacks: We used CW, PGM, and L2L attacker attack. • Report clean model accuracy: We reported. • Do not use Fast Gradient Sign Method. We use PGM-20 and PGM-100 and CW. • Do not only use attacks during testing that were used during training. We use different
evaluation criteria to evaluate all models.
• Perform basic sanity tests: It is provided in Figure 4.
• Generate an attack success rate vs. perturbation budget: Figure 4. • Verify adaptive attacks perform better than any other (e.g., blackbox, and brute-force
search): The above table and Appendix A in the paper. • Describe the attacks applied: In Section 3. • Apply a diverse set of attacks: We tried PGM attack (with different perturbation magnitude
and iterations), blackbox attack (transfer attack), CW attack (adaptive attack), L2L attack (adaptive and designed for this particular model), Bruteforce random search (gradient-free attack) • Suggestions for randomized defenses: We are not. • Suggestions for non-differentiable components (e.g., by performing quantization or adding
extra randomness): We have no additional non-differentiable component. • Verify that the attacks have converged: Figure 4 shows that the PGM attack eventually
converges. • Carefully investigate attack hyperparameters: Figure 4 • Compare against prior work: We compared our algorithm to PDM net. L2L is more com-
putationally efficient and the L2L model is more robust due to the fact that L2L attack is strong enough. Unlike Defense-GAN, we do not use the generator (attacker in L2L) as the denoising module and do not change the final prediction model.


summaries: The paper considers learning of constraints in MDPs in an IRL setting with the goal of maximizing the likelihood of demonstrations (in the constrained MDP). The constraints come in the form of avoiding certain states, actions or features. The authors propose an algorithm for learning the constraints and evaluate their approach in synthetic and a real-world experiment.

summaries: The submission considers estimating the constraints on the state, action and feature in the provided demonstrations, instead of learning rewards. The authors use the likelihood as MaxEnt IRL methods to evaluate the "correctness" of the constraints, and find the most likely constraints given the demonstrations. While the problem is challenging (NP-hard), suboptimality of the proposed algorithm is analyzed. Experiments are provided to demonstrate the performance of the proposed method.

summaries: In this work, a novel inverse constraint learning method is proposed, where the goal is to find out the constraints over state-action pairs for given demonstration and MDP **including a reward function** (so different from inverse cost learning). The novelty of this work comes from introducing maximum entropy inverse reinforcement learning (MaxEntIRL) framework to previous works [1, 2], and this work mainly focused on the tabular setting. The objective of this work is to solve the optimization in (8), which tries to find out the constraint that maximizes the probability of trajectories that cannot be generated if that constraint is applied. (Such an objective minimizes the normalization constant in (5) and results in maximization of the demonstration likelihood under the constraint.) To solve this objective, the proposed algorithm first computes the feature occupancy (Algorithm 1), and then use those feature occupancy with greedy iterative constraint inference (Algorithm 2 that motivated by maximum coverage problem) to get constraints. Two experiments in the GridWorld show that the proposed method effectively works.

abstractText: While most approaches to the problem of Inverse Reinforcement Learning (IRL) focus on estimating a reward function that best explains an expert agent’s policy or demonstrated behavior on a control task, it is often the case that such behavior is more succinctly represented by a simple reward combined with a set of hard constraints. In this setting, the agent is attempting to maximize cumulative rewards subject to these given constraints on their behavior. We reformulate the problem of IRL on Markov Decision Processes (MDPs) such that, given a nominal model of the environment and a nominal reward function, we seek to estimate state, action, and feature constraints in the environment that motivate an agent’s behavior. Our approach is based on the Maximum Entropy IRL framework, which allows us to reason about the likelihood of an expert agent’s demonstrations given our knowledge of an MDP. Using our method, we can infer which constraints can be added to the MDP to most increase the likelihood of observing these demonstrations. We present an algorithm which iteratively infers the Maximum Likelihood Constraint to best explain observed behavior, and we evaluate its efficacy using both simulated behavior and recorded data of humans navigating around an obstacle.

authors:
Pieter Abbeel
Andrew Y Ng

title: Apprenticeship learning via inverse reinforcement learning

venue: In Proceedings of the twenty-first international conference on Machine learning,

authors:
Pieter Abbeel
Adam Coates
Morgan Quigley
Andrew Y Ng

title: An application of reinforcement learning to aerobatic helicopter flight

venue: In Advances in neural information processing systems,

authors:
Glen Chou
Dmitry Berenson
Necmiye Ozay

title: Learning constraints from demonstrations

authors:
Mark K Ho
Michael L Littman
Fiery Cushman
Joseph L Austerweil

title: Teaching with rewards

venue: (WAFR

title: Algorithms for inverse reinforcement learning

authors:
Nathan D Ratliff
J Andrew Bagnell
Martin A Zinkevich

title: Maximum margin planning

venue: Robotics and Automation (ICRA),

authors:
Dexter R R Scobee
Vicenc Rubies Royo
Claire J Tomlin
S Shankar Sastry

title: Haptic assistance

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

authors:
Guru Subramani
Michael Zinn
Michael Gleicher

title: Inferring geometric constraints in human

venue: Cybernetics (SMC),

authors:
Dizan Vasquez
Billy Okal
Kai O Arras

title: Inverse reinforcement learning algorithms and features

venue: demonstrations. In Conference on Robot Learning,

authors:
Marcell Vazquez-Chanlatte
Susmit Jha
Ashish Tiwari
Mark K Ho
Sanjit Seshia

title: Learning task

venue: Conference on Intelligent Robots and Systems,

heading: 1 INTRODUCTION

text:
Advances in mechanical design and artificial intelligence continue to expand the horizons of robotic applications. In these new domains, it can be difficult to design a specific robot behavior by hand. Even manually specifying a task for a reinforcement-learning-enabled agent is notoriously difficult (Ho et al., 2015; Amodei et al., 2016). Inverse Reinforcement Learning (IRL) techniques can help alleviate this burden by automatically identifying the objectives driving certain behavior. Since first being introduced as Inverse Optimal Control by Kalman (1964), much of the work on IRL has focused on learning environmental rewards to represent the task of interest (Ng & Russell, 2000; Abbeel & Ng, 2004; Ratliff et al., 2006; Ziebart et al., 2008). While these types of IRL algorithms have proven useful in a variety of situations (Abbeel et al., 2007; Vasquez et al., 2014; Ziebart, 2010; Scobee et al., 2018), their basis in assuming that reward functions fully represent task specifications makes them ill suited to problem domains with hard constraints or non-Markovian objectives.
Recent work has attempted to address these pitfalls by using demonstrations to learn a rich class of possible specifications that can represent a task (Vazquez-Chanlatte et al., 2018). Others have focused specifically on learning constraints, that is, behaviors that are expressly forbidden or infeasible (Pardowitz et al., 2005; Pérez-D’Arpino & Shah, 2017; Subramani et al., 2018; McPherson et al., 2018; Chou et al., 2018). Such constraints arise in safety-critical systems, where requirements such as an autonomous vehicle avoiding collisions with pedestrians are more naturally expressed as hard constraints than as soft reward penalties. It is towards the problem of inferring such constraints that we turn our attention.
In this work, we present a novel method for inferring constraints, drawing primarily from the Maximum Entropy approach to IRL described by Ziebart et al. (2008). We use this framework to reason about the likelihood of observing a set of demonstrations given a nominal task description, as well as about their likelihood if we imposed additional constraints on the task. This knowledge allows us to select a constraint, or set of constraints, which maximizes the demonstrations’ likelihood and
best explains the differences between expected and demonstrated behavior. Our method improves on prior work by being able to simultaneously consider constraints on states, actions and features in a Markov Decision Process (MDP) to provide a principled ranking of all options according to their effect on demonstration likelihood.

heading: 2 RELATED WORK

heading: 2.1 INVERSE REINFORCEMENT LEARNING

text:
A formulation of the IRL problem was first proposed by Kalman (1964) as the Inverse problem of Optimal Control (IOC). Given a dynamical system and a control law, the author sought to identify which function(s) the control law was designed to optimize. This problem was brought into the domain of MDPs and Reinforcement Learning (RL) by Ng & Russell (2000), who proposed IRL as the task of, given an MDP and a policy (or trajectories sampled according to that policy), find a reward function with respect to which that policy is optimal.
One of the chief difficulties in the problem of IRL is the fact that a policy can be optimal with respect to a potentially infinite set of reward functions. The most trivial example of this is the fact that all policies are optimal with respect to a null reward function that always returns zero. Much of the work in IRL has been devoted to developing approaches that address this ambiguity by imposing additional structure to make the problem well-posed (Abbeel & Ng, 2004; Ratliff et al., 2006). Ziebart et al. (2008) approach the problem by employing the principle of maximum entropy (Jaynes, 1957), which allows the authors to develop an IRL algorithm that produces a single stochastic policy that matches feature counts without adding any additional constraints to the produced behavior. This so called Maximum Entropy IRL (MaxEnt) provides a framework for reasoning about demonstrations from experts who are noisily optimal. The induced probability distribution over trajectories forms the basis for our efforts in identifying the most likely behavior-modifying constraints.

heading: 2.2 BEYOND REWARD FUNCTIONS

text:
While Markovian rewards do often provide a succinct and expressive way to specify the objectives of a task, they cannot capture all possible task specifications. Vazquez-Chanlatte et al. (2018) highlight the utility of non-Markovian Boolean specifications which can describe complex objectives (e.g. do this before that) and compose in an intuitive way (e.g. avoid obstacles and reach the goal). The authors of that work draw inspiration from the MaxEnt framework to develop their technique for using demonstrations to calculate the posterior probability that an agent is attempting to satisfy a Boolean specification.
A subset of these types of specifications that is of particular interest to us is the specification of constraints, which are states, actions, or features of the environment that must be avoided. Chou et al. (2018) explore how to infer trajectory feature constraints given a nominal model of the environment (lacking the full set of constraints) and a set of demonstrated trajectories. The core of their approach is to sample from the set of trajectories which have better performance than the demonstrated trajectories. They then infer that the set of possible constraints is the subset of the feature space that contains the higher-reward sampled trajectories, but not the demonstrated trajectories. Intuitively, they reason that if the demonstrator could have passed through those features to earn a higher reward, but did not, then there must have been a previously unknown constraint preventing that behavior. However, while their approach does allow for a cost function to rank elements from the set of possible constraints, the authors do not offer a mechanism for determining what cost function will best order these constraints.
Our approach to constraint inference from demonstrations addresses this open question by providing a principled ranking of the likelihood of constraints. We adapt the MaxEnt framework to allow us to reason about how adding a constraint will affect the likelihood of demonstrated behaviors, and we can then select the constraints which maximize this likelihood. We consider feature-space constraints as in Chou et al. (2018), and we explicitly augment the feature space with state- and action-specific features to directly compare the impacts of state-, action-, and feature-based constraints on demonstration likelihood.

heading: 3 MAXIMUM LIKELIHOOD CONSTRAINT INFERENCE

heading: 3.1 PROBLEM FORMULATION

text:
Following the formulation presented by Ziebart et al. (2008), we base our work in the setting of a (finite-state) Markov Decision Process (MDP). We define an MDP M as a tuple (S, {As}, {Ps,a} , D0, φ,R) where S is a finite set of discrete states; {As} is a set of the sets of actions available to be taken for each state s, such that As ⊆ A, where A is a finite set of discrete actions; {Ps,a} is a set of state transition probability distributions such that Ps,a(s′) = P (s′|s, a) is the probability of transitioning to state s′ after taking action a from state s; D0 : S → [0, 1] is an initial state distribution; φ : S × A → Rk+ is a mapping to a k-dimensional space of non-negative features; and R : S ×A→ R is a reward function. A trajectory ξ through this MDP is a sequence of states st and actions at such that s0 ∼ D0 and state si+1 ∼ Psi,ai . Actions are chosen by an agent navigating the MDP according to a, potentially time-varying, policy π such that π(·|s, t) is a probability distribution over actions in As. We denote a finite-time trajectory of length T + 1 by ξ = {s0:T ,a0:T }. At every time step t, a trajectory will accumulate features equal to φ(st, at). We use the notation φi(·, ·) to refer to the i-th element of the feature map, and we use the label φi to denote the i-th feature itself. We also introduce an augmented indicator feature mapping φ̃1 : S ×A→ {0, 1}nφ , where nφ = k+ |S|+ |A|. This augmented feature map uses binary variables to indicate the presence of a feature and expands the feature space by adding binary features to track occurrences of each state and action, such that
φ̃1φi(s, a) = { 1 if φi(s, a) > 0 0 otherwise , φ̃1si(s, a) = { 1 if s = si 0 otherwise , φ̃1ai(s, a) = { 1 if a = ai 0 otherwise .
(1)
Typically, agents are modeled as trying to maximize, or approximately maximize, the total reward earned for a trajectory ξ, given by R(ξ) = ∑T t=0 γ
tR(st, at), where γ ∈ (0, 1] is a discount factor. Therefore, an agent’s policy π is closely tied to the form of the MDP’s reward function.
Conventional IRL focuses on inferring a reward function that explains an agent’s policy, revealed through the behavior observed in a set of demonstrated trajectories D. However, our method for constraint inference poses a different challenge: given an MDPM, including a reward function, and a set of demonstrations D, find the most likely set of constraints C∗ that could modifyM to explain these demonstrations. We define our notion of constraints in the following section.

heading: 3.2 CONSTRAINTS FOR MDPS

text:
Constraints are those behaviors that are not disallowed explicitly by the structure of the MDP, but which would be infeasible or prohibited for the underlying system being modeled by the MDP. This sort of discrepancy can occur when a generic or simplified MDP is designed without exact knowledge of specific constraints for the modeled system. For instance, for a generic MDP modeling the behavior of cars, we might want to include states for speeds up to 500km/h and actions for accelerations up to 12m/s2. However, for a specific car on a specific roadway, the set of states where the vehicle travels above 100km/h may be prohibited because of a speed limit, and the set of actions where the vehicle accelerates above 4m/s2 may be infeasible because of the physical limitations of the vehicle’s engine. Therefore, any MDP trajectory of this specific car system would not contain a state-action pair which violates these legal and physical limits. Figure 1 shows an example of constraints driving behavior.
We define a constraint set Ci ⊆ S ×A as a set of state-action pairs that violate some specification of the modeled system. We consider three general classes of constraints: state constraints, action constraints, and feature constraints. A state constraint set Csi = {(s, a) | s = si} includes all stateaction pairs such that the state component is si. An action constraint set Cai = {(s, a) | a = ai} includes all state-action pairs such that the action component is ai. A feature constraint set Cφi = {(s, a) | φi(s, a) > 0} includes all state-action pairs that produce a non-zero value for feature φi.
If we augment the set of features as described in (1), it is straightforward to see that state and action constraints become special cases of feature constraints, with constraint sets given by
Ci = {(s, a) | φ̃1i (s, a) = 1}. It is also evident that we can obtain compound constraints, respecting two or more conditions, by taking the union of constraint sets Ci to obtain C = ⋃ i Ci.
3.2.1 ADDING CONSTRAINTS TO AN MDP
We need to be able to reason about how adding a constraint to an MDP will influence the behavior of agents navigating that environment. If we impose a constraint on an MDP, then none of the state-action pairs in that constraint set may appear in a trajectory of the constrained MDP. To enforce this condition, we must restrict the actions available in each state so that it is not possible for an agent to produce one of the constrained state-action pairs. For a given constraint C, we can replace the set of available actions As in every state s with an alternative set ACs given by
ACs = As \ {a ∈ As | (s, a) ∈ C} . (2)
Performing such substitutions for an MDPM will lead to a modified MDPMC such thatMC = (S, {ACs }, {Ps,a}, D0, φ,R). The question then arises as to the how we should treat states with empty action sets ACs = ∅. Since an agent arriving in such an empty state would have no valid action to select, any trajectory visiting an empty state must be deemed invalid. Indeed, such empty action sets will be produced for any state si such that Csi ⊆ C. For MDPs with deterministic transitions, agents know precisely which state they will arrive in following a certain action. Therefore, any agent respecting constraints will not take an action that leads to an empty state, since doing so will lead to constraint violations. If we consider the set of empty states Sempty, then for the purposes of reasoning about an agent’s behavior, we can impose an additional constraint set Cempty = {(s, a) | ∃ sempty ∈ Sempty : Ps,a(sempty) = 1}. In this work, we will always implicitly add this constraint set, such thatMC will be equivalent toMC∪Cempty , and we recursively add these constraints until reaching a fixed point.
For MDPs with stochastic transitions, the semantics of an empty state are less obvious and could lend themselves to multiple interpretations depending on the nature of the system being modeled. We offer a possible treatment in the appendix.

heading: 3.2.2 NOMINAL MDPS

text:
The nominal MDPs to which we will add constraints fall into two broad categories, which we denote as generic and baseline. The car MDP described at the beginning of Section 3.2 is an example of a generic nominal model: its state and action spaces are broad enough to encompass a wide range of car models, and we can use this nominal model to infer constraints that specialize the MDP to a specific car and task. For a generic nominal MDP, the reward function may also come from a generic, simplified task, such as “minimize time to the goal” or “minimize energy usage.”
A baseline nominal MDP is a snapshot of a system from a point in time where it was well characterized. With a baseline nominal MDP, the constraints that we infer will represent changes to the system with respect to this baseline. In this case, the nominal reward function can be learned using existing IRL techniques with demonstrated behavior from the baseline model. We take this approach in our human obstacle avoidance example in Section 4.2: we use demonstrations of humans walking through the empty space to learn a nominal reward, then we can detect the presence of a new obstacle in the space from subsequent demonstrations.

heading: 3.3 DEMONSTRATION LIKELIHOOD MAXIMIZATION

text:
Our goal is to find the constraints C∗ which are most likely to have been added to a nominal MDP M, given a set of demonstrations D from an agent navigating the constrained MDP. Let us define PM to denote probabilities given that we are considering MDPM. Our problem then becomes to select the constraints that maximize PM(C | D). If we assume a uniform prior over possible constraints, then we know from Bayes’ Rule that PM(C | D) ∝ PM(D | C). Therefore, in order to find the constraints that maximize PM(C | D), we can solve the equivalent problem of finding which constraints maximize the likelihood of the given demonstrations. In this section, we present our approach to solving maximum likelihood constraint inference via solving demonstration likelihood maximization.
Under the maximum entropy model presented by Ziebart et al. (2008), the probability of a certain finite-length trajectory ξ being executed by an agent traversing a deterministic MDP M is exponentially proportional to the reward earned by that trajectory.
PM(ξ) = 1
Z eβR(ξ)1M(ξ), (3)
where Z is the partition function, 1M(ξ) indicates if the trajectory is feasible for this MDP, and β ∈ [0,∞) is a parameter describing how closely an agent adheres to the task of optimizing the reward function (as β →∞, the agent becomes a perfect optimizer, and as β → 0, the agent’s actions become perfectly random). In the sequel, we assume that a given reward function will appropriately capture the role of β, so we omit β from our notation without loss of generality.
In the case of finite horizon planning, the partition function will be the sum of the exponentially weighted rewards for all feasible trajectories on MDPM of length no greater than the planning horizon. We denote this set of trajectories by ΞM. Because adding constraints C modifies the set of feasible trajectories, we express this dependence as
Z(C) = ∑ ξ∈ΞM eR(ξ)1M C (ξ). (4)
Assuming independence among demonstrated trajectories, the probability of observing a set D of N demonstrations is given by the product
PMC (D) = 1
Z(C)N ∏ ξ∈D eR(ξ)1M C (ξ). (5)
Our goal is to maximize the demonstration probability given by (5). Because we take the reward function and demonstrations as given, our only available decision variable in this maximization is the constraint set C which alters the indicator 1M C and partition function Z(C).
C∗ = arg max C∈C PMC (D), (6)
where C ⊆ 2S×A is the hypothesis space of possible constraints. From the form of (5), it is clear that to solve (6), we must choose a constraint set that does not invalidate any demonstrated trajectory while simultaneously minimizing the value of Z(C). Consider the set of trajectories that would be made infeasible by augmenting the MDP with constraint C, which we denote as Ξ−MC = {ξ ∈ ΞM | 1
MC (ξ) = 0}. The value of Z(C) is minimized when we maximize the sum of exponentiated rewards of these infeasible trajectories. Considering the form of the trajectory probability given by (3), we can see that this sum is proportional to the total probability of observing a trajectory from Ξ−MC on the original MDPM∑
ξ∈Ξ− MC
eR(ξ) ∝ ∑
ξ∈Ξ− MC
PM(ξ) = PM(Ξ − MC ). (7)
This insight leads us to the final form of the optimization
C∗ = arg max C∈C PM(Ξ − MC )
s.t. D ∩ Ξ−MC = ∅ . (8)
In order to solve (8), we must reason about the probability distribution of trajectories on the original MDP M, then find the constraint C such that Ξ−MC contains the most probability mass while not containing any demonstrated trajectories. Figure 2 provides a graphical representation of this reasoning. We highlight here that the fact that the chosen C must not conflict with any demonstration is an important condition: all provided demonstrations must perfectly respect a constraint in order for it to be learned, otherwise a less restrictive set of constraints may be learned instead. Future work will look to relax this requirement in order to learn about constraints that are generally respected by a set of demonstrations, without needing to first isolate just the successful, constraint-respecting demonstrations.
While equation (8) is derived for deterministic MDPs, if we can assume, as proposed by Ziebart et al. (2008), that for a given stochastic MDP, the stochastic outcomes have little effect on an agent’s behavior and the partition function, then the solution to (8) will also approximate the optimal constraint selection for that MDP. However, in order to fully address the stochastic case, we would need to reformulate our approach based on maximum causal entropy (Ziebart, 2010). We save this extension for future work.

heading: 3.3.1 CONSTRAINT HYPOTHESIS SPACE

text:
In order for the solutions to (8) to be meaningful, we must be careful with our choice of the constraint hypothesis space C. For instance, if we let C = 2S×A, then the optimal solution will always be to choose the most restrictive C to constrain all state-action pairs not observed in the demonstration set.
One approach to avoid this trivial solution is to use domain knowledge of the modeled system to restrict C to a library of plausible or common constraints. McPherson et al. (2018) construct such a library by using reachability theory to calculate a family of likely unsafe sets.
We could also potentially address this problem by adding a regularization term to the optimization that would penalize constraints based on some notion of “size,” which would encourage the selection of “smaller” constraints. The size of a constraint set could be defined by the number of minimal constraints that it contains. These minimal constraint sets constrain a single state, action, or feature, and were introduced in Section 3.2 asCsi , Cai , andCφi , respectively. While penalizing this definition of size would effectively discourage overfitting, considering every possible combination of minimal constraints causes the hypothesis space to grow exponentially in the number of states, actions, and features of the MDP, which may make directly solving this formulation intractable.
Another approach, which avoids this combinatorial explosion, is to use the minimal constraint sets themselves, not their combinations, as our hypothesis space, and to select from among these constraints in an iterative, greedy manner. By iteratively selecting individual minimal constraint sets, and choosing a proper stopping condition, it is possible to gradually grow the full estimated constraint
set and avoid overfitting to the demonstrations. It is this method that we will utilize in this work. Section 3.4 details our approach for selecting the most likely minimal constraint, and Section 3.5 details our approach for iteratively growing the estimated constraint set.

heading: 3.4 PROBABILITY MASS FOR MINIMAL CONSTRAINTS

text:
Algorithm 1 Feature Accrual History Calculation Input: an MDPM, a policy π(a|s, t), a time horizon T Output: expected feature accrual history Φ̃[1,T ] /* Initialize state visitation and feature accrual history */
1: for s ∈ S do 2: Ds,0 ← D0(s) 3: Φ̃s,0 ← 0nφ×1 4: end for
/* Track feature accruals over the time horizon */ 5: for t ∈ [0, T − 1] do 6: for s ∈ S do 7: for a ∈ As do 8: /* New feature accruals */ 9: /* “ ” denotes element-wise multiplication */
10: ∆Φ̃s,t(a)← φ̃1(s, a) ( Ds,t1nφ×1 − Φ̃s,t ) 11: end for 12: end for 13: for s′ ∈ S do 14: Ds′,t+1 ←
∑ s∈S ∑ a∈As Ds,tπ(a|s, t)P (s′|s, a)
15: Φ̃s′,t+1 ←∑ s∈S ∑ a∈As ( Φ̃s,t + ∆Φ̃s,t(a) ) π(a|s, t)P (s′|s, a)
16: end for 17: Φ̃t+1 ← ∑ s∈S Φ̃s,t+1 18: end for 19: Return Φ̃[1,T ] As detailed in Section 3.3, the most likely constraint set is the one whose eliminated trajectories Ξ−MC have the highest probability of being demonstrated on the original, unconstrained MDP. Therefore, to find the most likely of the minimal constraints, we must find the expected proportion of trajectories which will contain any state or action, or accrue any feature. By using our augmented indicator feature map from (1), we can reduce this problem to only examine feature accruals. Ziebart et al. (2008) present their forward-backward algorithm for calculating expected feature counts for an agent following a policy in the maximum entropy setting. This algorithm nearly suffices for our purposes, but it computes the expectation of the total number of times a feature will be accrued (i.e. how often will this feature be observed per trajectory), rather than the expectation of the number of trajectories that will accrue that feature at any point in time. To address this problem, we present a modified form of the “forward” pass as Algorithm 1. Our algorithm tracks state visitations as well as feature accruals at each state, which allows us to produce the same maximum entropy distribution over trajectories as Ziebart et al. (2008) while not counting additional accruals for trajectories that have already accrued a feature.
The input of Algorithm 1 includes the MDP itself, a time horizon, and a time-varying policy. This policy should capture the expected behavior of the demonstrator on the nominal MDPM, and it can be computed via the “backward” part of the algorithm from Ziebart et al. (2008). The output of Algorithm 1, Φ̃[1,T ], is an nφ × T array such that the t-th column Φ̃t is a vector whose i-th entry is the expected proportion of trajectories to have accrued the i-th feature by time t. In particular, the i-th element of Φ̃T is equal to PM(Ξ−MCi ), which allows us to now directly select the most likely constraint according to (8).

heading: 3.5 MAXIMUM-COVERAGE-BASED ITERATIVE CONSTRAINT INFERENCE

text:
When using minimal constraint sets as the constraint hypothesis space, it is possible that the most likely constraint still does not provide a satisfactory explanation for the demonstrated behavior. In this case, it can be beneficial to combine minimal constraints. If the task of solving (8) is framed as finding the combination of constraint sets that “covers” the most probability mass, then the problem becomes a direct analog for the classic maximum coverage problem. While this problem is known to be NP-hard, there exist a simple greedy algorithm with known suboptimality bounds (Hochbaum & Pathria, 1998).
We present Algorithm 2 as our approach for adapting this greedy heuristic to solve the problem of constraint inference. At each iteration, we grow our estimated constraint set by augmenting it with the constraint set in our hypothesis space that covers the most currently uncovered probability mass. By analogy to the maximum coverage problem (Hochbaum & Pathria, 1998), we derive the following bound on the suboptimality of our approach. Theorem 1. Let Cnc be the set of all constraints Cnc such that Cnc = ⋃nc i=1 Ci for Ci ∈ C, and let C∗nc be the solution to (8) using Cnc as the constraint hypothesis space. It follows, then, that at the end of every iteration i of Algorithm 2,
P (
Ξ− MĈ∗
) ≥ ( 1− ( i− 1 i )i) P ( Ξ− MC ∗ i ) .
Algorithm 2 Greedy Iterative Constraint Inference Input: MDPM, constraint hypothesis space C,
empirical probability distribution PD, threshold dDKL Output: estimated constraint set Ĉ∗
1: Ĉ∗ ← ∅ 2: for i ∈ [1, |C| ] do 3: Ci ← solution to (8) usingMĈ ∗ , C, and D
4: ∆DKL = DKL ( PD ||PMĈ∗ ) −DKL ( PD ||PMĈ∗∪Ci ) 5: if ∆DKL ≤ dDKL then 6: break 7: end if 8: Ĉ∗ ← Ĉ∗ ∪ Ci 9: end for
10: Return Ĉ∗
This bound is directly analogous to the suboptimality bound for the greedy solution to the maximum coverage problem proven by Hochbaum & Pathria (1998). For space, the proof is included in the appendix.
Rather than selecting the number of constraints nc to be used ahead of time, we check a stopping condition to decide if we should continue to add constraints. Because we are attempting to maximize PMC (D), it might seem natural to use a probabilitybased stopping condition. However, choosing a stopping criterion based on probability is problematic because the probability of observing a set of demonstrations is dependent on the number of demonstrations in the set, even if each individual demonstration has the same probability. We instead base our stopping condition on KL divergence, which depends only on the distribution of trajectories in D and not on the number of demonstrations. The quantity DKL ( PD ||PMĈ∗ ) provides a measure of how well the distribution over trajectories induced by our inferred constraints, PMĈ∗ , agrees with the empirical probability distribution over trajectories observed in the demonstrations, PD. Using this KL divergence in the stopping condition actually preserves a link to the probability of the demonstration set, since the KL divergence will decrease monotonically as PMC (D) increases. The threshold parameter dDKL is chosen to avoid overfitting to the demonstrations, combating the tendency to select additional constraints that may only marginally better align our predictions with the demonstrations.

heading: 4 EXAMPLES

heading: 4.1 SYNTHETIC GRID WORLD

text:
We consider the grid world MDP presented in Figure 3. The environment consists of a 9-by-9 grid of states, and the actions are to move up, down, left, right, or diagonally by one cell. The objective is to move from the starting state in the bottom-left corner (s0) to the goal state in the bottom-right corner (sG). Every state-action pair produces a distance feature, and the MDP reward is negative distance, which encourages short trajectories. There are additionally two more features, denoted green and blue, which are produced by taking actions from certain states, as shown in Figure 3.
The true MDP, from which agents generate trajectories, is shown in Figure 3a, including its constraints. The nominal, more generic MDP shown in Figure 3b is what we take asM for applying the iterative maximum likelihood constraint inference in Algorithm 2, with feature accruals estimated using Algorithm 1. While Figures 3c through 3e show the iteratively estimated constraints, which align with the true constraints, it is interesting to note that not all constraints present in the true MDP are identified. For instance, it is so unlikely that an agent would ever select the up-left diagonal action, that the fact that demonstrated trajectories did not contain that action is unsurprising and does not make that action an estimated constraint.
Figure 4 shows how the performance of our approach varies based on the number of available demonstrations and the selection for the threshold dDKL . The false positive rate shown in Figure 4a is the proportion of selected constraints which are not constraints of the true system. We can observe two trends in this data that we would expect. First, lower values of dDKL lead to greater false positive rates since they allow Algorithm 2 to continue iterating and accept constraints that do less to align expectations and demonstrations. Second, having more demonstrations available provides more information and reduces the rate of false positives. Further, Figure 4b shows that more demonstrations also allows the behavior predicted by constraints to better align with the observations. It is interesting to note, however, that with fewer than 10 demonstrations and a very low dDKL , we may produce very low KL divergence, but at the cost of a high false positive rate. This phenomenon highlights the role of selecting dDKL to avoid over-fitting. The threshold dDKL = 0.1 achieves a good balance of producing few false positives with sufficient examples while also producing lower KL divergences, and we used this threshold to produce the results in Figures 3 and 5.

heading: 4.2 HUMAN OBSTACLE AVOIDANCE

text:
In our second example, we analyze trajectories from humans as they navigate around an obstacle on the floor. We map these continuous trajectories into trajectories through a grid world where each cell represents a 1ft-by-1ft area
on the ground. The human agents are attempting to reach a fixed goal state (sG) from a given initial state (s0), as shown in Figure 5. We performed MaxEnt IRL on human demonstrations of the task without the obstacle to obtain the nominal distance-based reward function. We restrict ourselves to estimating only state constraints, as we do not supply our algorithm with knowledge of any additional features in the environment and we assume that the humans’ motion is unrestrained.
Demonstrations were collected from 16 volunteers, and the results of performing constraint inference are shown in Figure 5. Our method is able to successfully predict the existence of a central obstacle. While we do not estimate every constrained state, the constraints that we do estimate make all of the obstacle states unlikely to be visited. In order to identify those states as additional constraints, we would have to decrease our dDKL threshold, which could also lead to more spurious constraint selections, such as the three shown in Figure 5.

heading: 5 CONCLUSION AND FUTURE WORK

text:
We have presented our novel technique for learning constraints from demonstrations. We improve upon previous work in constraint-learning IRL by providing a principled framework for identifying the most likely constraint(s), and we do so in a way that explicitly makes state, action, and feature constraints all directly comparable to one another. We believe that the numerical results presented in Section 4 are promising and highlight the usefulness of our approach.
Despite its benefits, one drawback of our approach is that the formulation is based on (3), which only exactly holds for deterministic MDPs. As mentioned in Section 3.3, we plan to investigate the use of a maximum causal entropy approach
to address this issue and fully handle stochastic MDPs. Additionally, the methods presented here require all demonstrations to contain no violations of the constraints we will estimate. We believe that softening this requirement, which would allow reasoning about the likelihood of constraints that are occasionally violated in the demonstration set, may be beneficial in cases where trajectory data is collected without explicit labels of success or failure. Finally, the structure of Algorithm 1, which tracks the expected features accruals of trajectories over time, suggests that we may be able to reason about non-Markovian constraints by using this historical information to our advantage.
Overall, we believe that our formulation of maximum likelihood constraint inference for IRL shows promising results and presents attractive avenues for further investigation.

heading: ACKNOWLEDGMENTS

text: This work is supported by the National Science Foundation through grant CNS-1545126 (VeHICaL). We would like to thank Jaime Fisac, Andrea Bajcsy, Sylvia Herbert, and David Fridovich-Keil for their insightful discussions and for sharing their collected data.

heading: A ADDING CONSTRAINTS TO STOCHASTIC MDPS

text:
For MDPs with stochastic transitions, the semantics of an empty state are less obvious and could lend themselves to multiple interpretations depending on the nature of the system being modeled. In our context, we use constraints to describe how observed behaviors from demonstrations differ from possible behaviors allowed by the nominal MDP structure. We therefore assume that any demonstrations provided are, by the fact that they were selected to be provided, consistent with the system’s constraints, including avoiding empty states. This assumption implies that any stochastic state transitions that would have led to an empty state will not be observed in trajectories from the demonstration set. The omission of these transitions means that, for a given (s, a), if Ps,a(Sempty) = p, then a proportion p of these (s, a) pairs which occur as an agent navigates the environment will be excluded from demonstrations. Therefore, as we modify the MDP to reason about demonstrated behavior, we need updated transition probabilities which eliminate the probability mass of transitioning to empty states, an event which will never be observed in a demonstration. Such modified probabilities can be given as
PCs,a(s ′) =
{ 0 if s′ ∈ Sempty
Ps,a(s′) 1−Ps,a(Sempty) otherwise
. (9)
We must also capture the change to observed state-action pair frequencies by understanding that any observed policy πC will be related to an agent’s actual policy π according to
πC(a|s, t) = π(a|s, t)(1− Ps,a(Sempty))∑
a′∈ACs π(a′|s, t)(1− Ps,a(Sempty))
. (10)
It is important to note that the modifications presented in (9) and (10) for non-deterministic MDPs are not meant to directly reflect the reality of the underlying system (we wouldn’t expect the actual transition dynamics to change, for instance), but to reflect the apparent behavior that we would expect to observe in the subset of trajectories that would be selected as demonstrations. We further note that applying these modifications to deterministic MDPs will result in the same expected behavior as augmenting the constraint set with Cempty.

heading: B PROOF FOR THEOREM 1

text:
Theorem 1. Let Cnc be the set of all constraints Cnc such that Cnc = ⋃nc i=1 Ci for Ci ∈ C, and let C∗nc be the solution to (8) using Cnc as the constraint hypothesis space. It follows, then, that at the end of every iteration i of Algorithm 2,
P (
Ξ− MĈ∗
) ≥ ( 1− ( i− 1 i )i) P ( Ξ− MC ∗ i ) .
Proof. The problem of finding C∗nc is analogous to solving the maximum coverage problem, discussed by Hochbaum & Pathria (1998), where the set of elements to be covered is the set of trajectories {ξ | ∃C ∈ C : ξ ∈ Ξ−MC and D ∩ Ξ − MC = ∅} and the weight of each element ξ is PM(ξ). Because Algorithm 2 constructs Ĉ∗ iteratively by taking the union of the previous value of Ĉ∗ and the set Ci ∈ C which solves (8), the value of Ĉ∗ at the end of the i-th iteration is analogous to the greedy solution of the maximum coverage problem with nc = i. Therefore, we can directly apply the suboptimality bound for the greedy solution proven in Hochbaum & Pathria (1998) to arrive at our given bound on eliminated probability mass.