summaries: The present paper proposes to consider features derived from PCA for the purposes of adversarial attack and defense. They argue that, based on these features, they can verify larger neighborhoods and provide stronger attacks. The neighborhoods are based on the ERAN verifier and the attacks are in comparison to a recent attack called AutoZoom. Defense performance is measured in number of images in the neighborhood, and attack performance in terms of L2 distance.

summaries: The authors study the problem of adversarial robustness, aiming to find regions of the input space for which a classifier is robust. Instead of the standard approach of defining a neighborhood around each data point based on some $\ell_p$-norm, they use PCA to identify directions along which the model is robust or brittle. They then use these methods to identify large regions of input space for which models are robust and, in a complementary direction, to craft imperceptible adversarial examples with few model queries.

summaries: The overall quality of the paper is good. This paper proposed a feature perturbation procedure, as a comparison to the commonly used perturbation to the original input data. Given access to a feature mapping and a black-box classifier, the proposed procedure is able to select the most robust/weak features. This then can be used for two important tasks: to determine a robust neighborhood for a data point using the robust features and to design adversarial examples using the weak features. For the first task, the feature-based robust neighborhood proposed by this paper is shown by experiments to contain far more points than the traditional input-based neighborhood. For the second task, the feature-based adversarial examples require less query to the black-box classifier and have less distortion from the original data points compared with other competitive methods, and thus are more human-imperceptible. These characteristics make the procedure appealing.

abstractText: A key challenge in analyzing neural networks’ robustness is identifying input features for which networks are robust to perturbations. Existing work focuses on direct perturbations to the inputs, thereby studies network robustness to the lowestlevel features. In this work, we take a new approach and study the robustness of networks to the inputs’ semantic features. We show a black-box approach to determine features for which a network is robust or weak. We leverage these features to obtain provably robust neighborhoods defined using robust features and adversarial examples defined by perturbing weak features. We evaluate our approach with PCA features. We show (1) our provably robust neighborhoods are larger: on average by 1.5x and up to 4.5x, compared to the standard neighborhoods, and (2) our adversarial examples are generated using at least 12.2x fewer queries and have at least 2.8x lower L2 distortion compared to state-of-the-art. We further show that our attack is effective even against ensemble adversarial training.

authors:
Moustafa Alzantot
Yash Sharma
Supriyo Chakraborty
Huan Zhang
Cho-Jui Hsieh
Mani B. Srivastava

title: Genattack: practical black-box attacks with gradient-free optimization

venue: Proceedings of the Genetic and Evolutionary Computation Conference,

authors:
Greg Anderson
Shankara Pailoor
Isil Dillig
Swarat Chaudhuri

title: Optimization and abstraction: a synergistic approach for analyzing neural network robustness

venue: In Proceedings of the 40th (ACM) (SIGPLAN) Conference on Programming Language Design and Implementation,

authors:
Mislav Balunovic
Maximilian Baader
Gagandeep Singh
Timon Gehr
Martin T. Vechev

title: Certifying geometric robustness of neural networks

venue: In Annual Conference on Neural Information Processing Systems

authors:
Arjun Nitin Bhagoji
Daniel Cullina
Chawin Sitawarin
Prateek Mittal

title: Enhancing robustness of machine learning systems via data transformations

venue: In 52nd Annual Conference on Information Sciences and Systems,

authors:
Akhilan Boopathy
Tsui-Wei Weng
Pin-Yu Chen
Sijia Liu
Luca Danie

title: Cnn-cert: An efficient framework for certifying robustness of convolutional neural networks

venue: In The Thirty-Third AAAI Conference on Artificial Intelligence,

authors:
Nicholas Carlini
David A. Wagner

title: Adversarial examples are not easily detected: Bypassing ten detection methods

venue: In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security,

title: Towards evaluating the robustness of neural networks

venue: In IEEE Symposium on Security and Privacy,

authors:
Pin-Yu Chen
Huan Zhang
Yash Sharma
Jinfeng Yi
Cho-Jui Hsieh

title: ZOO: zeroth order optimization based black-box attacks to deep neural networks without training substitute models

authors:
Pin-Yu Chen
Yash Sharma
Huan Zhang
Jinfeng Yi
Cho-Jui Hsieh

title: EAD: elastic-net attacks to deep neural networks via adversarial examples

venue: In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
Krishnamurthy Dvijotham
Robert Stanforth
Sven Gowal
Timothy A. Mann
Pushmeet Kohli

title: A dual approach to scalable verification of deep networks

venue: In Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence,

authors:
Logan Engstrom
Brandon Tran
Dimitris Tsipras
Ludwig Schmidt
Aleksander Madry

title: Exploring the landscape of spatial robustness

venue: In Proceedings of the 36th International Conference on Machine Learning,ICML,

authors:
Timon Gehr
Matthew Mirman
Dana Drachsler-Cohen
Petar Tsankov
Swarat Chaudhuri
Martin T. Vechev

title: AI2: safety and robustness certification of neural networks with abstract interpretation

authors:
Khalil Ghorbal
Eric Goubault
Sylvie Putot

title: The zonotope abstract domain taylor1+

venue: In Proc. Computer Aided Verification (CAV)

title: A discussion of ’adversarial examples are not bugs, they are features’: Two examples of useful, non-robust features. Distill, 2019

authors:
Ian J. Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

venue: In 3rd International Conference on Learning Representations (ICLR),

authors:
Gaurav Goswami
Nalini K. Ratha
Akshay Agarwal
Richa Singh
Mayank Vatsa

title: Unravelling robustness of deep learning based face recognition against adversarial attacks

authors:
Dan Hendrycks
Kevin Gimpel

title: Early methods for detecting adversarial images

venue: In 5th International Conference on Learning Representations, Workshop Track Proceedings,

authors:
Andrew Ilyas
Shibani Santurkar
Dimitris Tsipras
Logan Engstrom
Brandon Tran
Aleksander Madry

title: Adversarial examples are not bugs, they are features

venue: In Advances in Neural Information Processing Systems

authors:
Malhar Jere
Sandro Herbig
Christine Lind
Farinaz Koushanfar

title: Principal component properties of adversarial samples

authors:
Saumya Jetley
Nicholas A. Lord
Philip H.S. Torr

title: With friends like these, who needs adversaries

authors:
Guy Katz
Clark W. Barrett
David L. Dill
Kyle Julian
Mykel J. Kochenderfer

title: Reluplex: An efficient SMT solver for verifying deep neural networks

venue: In Computer Aided Verification - 29th International Conference (CAV),

authors:
Alexey Kurakin
Ian J. Goodfellow
Samy Bengio

title: Adversarial machine learning at scale

venue: In 5th International Conference on Learning Representations,

authors:
Xin Li
Fuxin Li

title: Adversarial examples detection in deep networks with convolutional filter statistics

venue: In IEEE International Conference on Computer Vision,

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

title: Towards deep learning models resistant to adversarial attacks

venue: In 6th International Conference on Learning Representations,

authors:
Nicolas Papernot
Patrick D. McDaniel
Ian J. Goodfellow
Somesh Jha
Z. Berkay Celik
Ananthram Swami

title: Practical black-box attacks against machine learning

venue: Proceedings of the 2017 ACM on Asia Conference on Computer and Communications Security, AsiaCCS,

authors:
Aditi Raghunathan
Jacob Steinhardt
Percy Liang

title: Certified defenses against adversarial examples

authors:
Andras Rozsa
Manuel Günther
Ethan M. Rudd
Terrance E. Boult

title: Facial attributes: Accuracy and adversarial robustness

authors:
Hadi Salman
Greg Yang
Huan Zhang
Cho-Jui Hsieh
Pengchuan Zhang

title: A convex relaxation barrier to tight robustness verification of neural networks

venue: In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems,

authors:
Amartya Sanyal
Varun Kanade
Philip HS Torr
Puneet K Dokania

title: Robustness via deep low-rank representations

authors:
Gagandeep Singh
Timon Gehr
Matthew Mirman
Markus Püschel
Martin T. Vechev

title: Fast and effective robustness certification

venue: In Advances in Neural Information Processing Systems 31 Conference,

authors:
Gagandeep Singh
Rupanshu Ganvir
Markus Püschel
Martin T. Vechev

title: Beyond the single neuron convex barrier for neural network certification

authors:
Gagandeep Singh
Timon Gehr
Markus Püschel
Martin T. Vechev

title: Boosting robustness certification of neural networks

venue: In 7th International Conference on Learning Representations,

authors:
Christian Szegedy
Vincent Vanhoucke
Sergey Ioffe
Jonathon Shlens
Zbigniew Wojna

title: Rethinking the inception architecture for computer vision

venue: In 2016 IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Vincent Tjeng
Kai Y. Xiao
Russ Tedrake

title: Evaluating robustness of neural networks with mixed integer programming

authors:
Florian Tramèr
Alexey Kurakin
Nicolas Papernot
Ian J. Goodfellow
Dan Boneh
Patrick D. McDaniel

title: Ensemble adversarial training: Attacks and defenses

authors:
Chun-Chen Tu
Pai-Shun Ting
Pin-Yu Chen
Sijia Liu
Huan Zhang
Jinfeng Yi
Cho-Jui Hsieh
Shin-Ming Cheng

title: Autozoom: Autoencoder-based zeroth order optimization method for attacking black-box neural networks

venue: The Thirty-Third AAAI Conference on Artificial Intelligence,

authors:
Shiqi Wang
Kexin Pei
Justin Whitehouse
Junfeng Yang
Suman Jana

title: Efficient formal safety analysis of neural networks

venue: In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems,

authors:
Matthew Wicker
Xiaowei Huang
Marta Kwiatkowska

title: Feature-guided black-box safety testing of deep neural networks. In Tools and Algorithms for the Construction and Analysis of Systems

venue: 24th International Conference,

authors:
Cihang Xie
Yuxin Wu
Laurens van der Maaten
Alan L. Yuille
Kaiming He

title: Feature denoising for improving adversarial robustness

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

authors:
Matthew D. Zeiler
Rob Fergus

title: Visualizing and understanding convolutional networks

venue: In Computer Vision - ECCV 2014 - 13th European Conference.,

authors:
Yonggang Zhang
Xinmei Tian
Ya Li
Xinchao Wang
Dacheng Tao

title: Principal component adversarial example

venue: IEEE Trans. Image Process.,

authors:
Huiyu Zhoua
Yuan YuanbAbdul
H.Sadkaa

title: Application of semantic features in face recognition

venue: In Pattern recognition,

heading: 1 INTRODUCTION

text:
The reliability of deep neural networks (DNNs) has been undermined by adversarial examples: small perturbations to inputs that deceive the network (e.g., Goodfellow et al. (2015)). A key step in recovering DNN reliability is identifying input features for which the network is robust. Existing work focuses on the input values, the lowest-level features, to evaluate the network robustness. For example, a lot of work analyzes networks’ robustness to neighborhoods consisting of all inputs at a certain distance from a given input (e.g., Boopathy et al. (2019); Katz et al. (2017); Salman et al. (2019); Singh et al. (2019a); Tjeng et al. (2019); Wang et al. (2018)). Despite the variety of approaches introduced to analyze robustness, the diameter (controlling the neighborhood size) of the provably robust neighborhoods is often very small. This may suggest an inherent barrier of the robustness of DNNs to distance-based neighborhoods. To illustrate, consider Figure 1(a) and Figure 1(b) – which are visibly the same but in fact each of their pixels differs by = 0.026. That is the maximal one for which the L∞ ball B (x) (x is Figure 1(a)) was proven robust by ERAN (Singh et al., 2018; Gehr et al., 2018), a state-of-the-art robustness analyzer.
Feature-defined neighborhoods We propose to analyze network robustness to perturbations of high-level input features. A small perturbation to a feature translates to changes of multiple input entries (e.g., image pixels) and as such may produce visible perturbations. To illustrate, consider a neighborhood around Figure 1(a) in which only the background pixels can change their color. It turns out that, for this neighborhood, ERAN – the same robustness analyzer – is able to prove a neighborhood which has 10672x more images. Figure 1(c) shows a maximally perturbed image in this neighborhood, and Figure 1(d) illustrates two other images in it. These images are visibly different from Figure 1(a). Proving such neighborhood robust, for many inputs, can suggest that the network is robust to background color perturbations, thereby provide insights to the patterns the network learned.
Key idea: robust features An inherent challenge in finding robust feature-defined neighborhoods is automatically finding good candidate features (e.g., background color). Part of this challenge stems from the substantial running time of any robustness analyzer on a single neighborhood. This makes brute-force search of feature-defined neighborhoods for a large number of features and inputs futile. We propose a sampling approach to identify features which are likely to be robust for many inputs. We call these robust features. We experimentally observe that our robust features generalize to unseen inputs, even though they were determined from a (small) set of inputs.
δ (x).
(e) A traffic light image from Imagenet, correctly classified by Inception-V3. (f) Our feature-based adversarial example classified by the same model as crane. (g) A visualization of the difference. (h) Perturbations to the image x using the second PCA feature (whose semantic meaning is sky color).
Feature-guided adversarial examples Dually to robust features, we define and identify weak features. We show how to exploit them in a simple yet effective black-box attack. Our attack perturbs a given input based on the weak features and then greedily reduces the number of modified pixels to obtain an adversarial example which minimizes the L2 distance from the original input. Figure 1 illustrates our attack on ImageNet with the Inception-V3 architecture (Szegedy et al., 2016). Figure 1(e) shows a traffic light image (correctly classified), Figure 1(f) shows our feature-guided adversarial example (classified as crane), and Figure 1(g) visualizes the difference between the two images. We experimentally show that our attack is competitive with state-of-the-art practical black-box attacks (AutoZoom by Tu et al. (2019) and GenAttack by Alzantot et al. (2019)) and fools the ensemble adversarial training defense by Tramèr et al. (2018). Our results strengthen the claim of Ilyas et al. (2019) who suggested that weak (non-robust) features of the data contribute to the existence of adversarial examples. However, unlike Ilyas et al. (2019), we do not focus on features that stem from the DNN. This allows us to expose interesting patterns, expressed via simple functions, that the DNN has learned or missed.
PCA features We obtain an initial set of features by running principal component analysis (PCA). PCA provides us with an automatic way to extract useful features from a dataset. For example, the sky color feature of the airplane in Figure 1(a) is in fact the second PCA dimension of this class of images in CIFAR10. Figure 1(h) shows the effect of perturbing this feature by small constants (multiplied by δ = 5) in the PCA domain and projecting it back to the image domain. Our choice of using PCA is inspired by earlier work. We hypothesized that DNN may learn (some) of the PCA features by relying on works that showed that PCA can capture semantic features of the dataset (e.g., Zhoua et al. (2008); Jolliffe (2002)) and that DNNs learn semantic features (e.g., Zeiler & Fergus (2014)). Further, PCA has been linked to adversarial examples: several works showed how to detect adversarial examples using PCA (Hendrycks & Gimpel., 2017; Jere et al., 2019; Li & Li, 2017), others utilized PCA to approximate an adversarial manifold (Zhang et al., 2020), and others constructed an attack that modified only the first PCA dimensions (Carlini & Wagner., 2017). Computing the exact PCA dimensions requires perfect-knowledge of the dataset and is time-consuming for large datasets (e.g., ImageNet). We show that an approximation of the PCA dimensions is sufficient to obtain robust and weak features and that these can be computed from a small subset of the dataset (not used for training). The assumption that the attacker has access to a small dataset of similar distribution to the training set is often valid in practice (e.g., for traffic sign recognition benchmarks, like GTSRB, or face recognition applications).
We evaluate our approach on six datasets and various network architectures. Results indicate that (1) compared to the standard neighborhoods, our provably robust feature-guided neighborhoods have larger volume, on average by 1.5x and up to 4.5x, and they contain 1079x more images (average is taken over the exponent), and (2) our adversarial examples are generated using at least 12.2x fewer queries and have at least 2.8x lower L2 distortion compared to state-of-the-art practical black-box attacks. We also show that our attack is effective even against ensemble adversarial training.
To conclude, our main contributions are:
• Definitions of networks’ robustness and weakness to feature perturbations (Section 2). • A sampling algorithm for finding the most robust and weakest features (Section 3). • Feature-based neighborhoods and their robustness analysis (Section 4). • Feature-based adversarial examples (Section 5). • Instantiation with PCA features (Section 6). • Extensive evaluation of our approach (Section 7).

heading: 2 ROBUST AND WEAK FEATURES

text:
In this section, we define robust and weak features. We focus on classifiers, D : Rd → Rc, given as a black-box, and trained on input-output pairs (x, z) sampled from a distribution T . We denote by class(D(x)) the classification of x by D (i.e., the index i maximizing D(x)i).
Features A feature function f : Rd → Rd is a bijective function mapping inputs to real-valued vectors. The assumption that f is bijective simplifies our definitions but these can be extended to other kinds of feature functions. The ith component of a feature function f is called the feature i of f .
Feature perturbation For a feature function f : Rd → Rd, index i, and a scalar δ ∈ R, we define the perturbation of x along feature i by δ as follows: xf,i,δ = f−1(f(x) + δ{i}), where δ{i} ∈ Rd is a vector whose entries are zero except for the ith entry which is δ.
Network robustness to features perturbations Given a feature function f , an index i, and a scalar δ ∈ R+, we say the feature i of f is δ-robust if any perturbation to the feature i up to δ does not decrease the class confidence of D on x denoted by CC(D,x) (shortly defined). Formally:
P(x,z)~T ([∀δ′ ∈ [0, δ].class(D(xf,i,δ′)) = class(D(x)) and CC(D,xf,i,δ′) ≥ CC(D,x)]) = 1.
The expression [·] is the Iverson bracket: it is 1 if the formula evaluates to true, and 0 otherwise. We define δ-robustness for δ ∈ R− similarly (except that δ′ ∈ [δ, 0]). If i is δ-robust and δ > 0, we say the robustness direction of i is + (positive); otherwise if δ < 0 the direction is − (negative). We define network weakness dually. The feature i of f is δ-weak if any perturbation to the feature i up to δ changes the classification or decreases the class confidence. Formally, for δ ∈ R+:
P(x,z)~T ([∀δ′ ∈ [0, δ].class(D(xf,i,δ′)) 6= class(D(x)) or CC(D,xf,i,δ′) ≤ CC(D,x)]) = 1.
Class confidence The definition of class confidence CC(D,x) is orthogonal to our approach. One can define it as the class probability. However, we experimentally observed that it is better to relax the requirement about the absolute value and instead focus on the difference between the probability of the highest ranked class and the second highest, that is:
CC(D,x) = D(x)class(D(x)) −max {D(x)i | i ∈ {0, . . . , c− 1} \ {class(D(x))}} .
Most robust and weakest features Generally, we do not expect to find robust features if the features are defined orthogonally to the network’s structure and parameters. However, if we relax the definition and quantify the robustness level of a feature, we can expose connections between the feature and the network’s robustness behavior. We define the robustness level RL as:
RL = P(x,z)~T ([∀δ′ ∈ [0, δ].class(D(xf,i,δ′)) = class(D(x)) and CC(D,xf,i,δ′) ≥ CC(D,x)]).
We define the problem of finding the most robust features as finding k features maximizing the robustness level. Dually, we define the weakness level and the problem of finding k weakest features.

heading: 3 MOST ROBUST AND WEAKEST FEATURES VIA SAMPLING

text:
In this section, we present our approach to approximate the most robust and weakest features via sampling. We approximate these features by checking robustness over inputs from a set S (drawn from the distribution T ) and by sampling the intervals [0, δ] and [−δ, 0] at several points determined by a step parameter η. Algorithm 1 depicts our computation. The time complexity of Algorithm 1 is
Algorithm 1: FindRobustWeakFeatures(D, S, f , d, k, δ, η) Input: A classifier D, input-output pairs S, a feature function f , a number of features d, a number k, scalars δ and η (precondition: 0 < η ≤ δ and k ≤ d ). Output: k most robust features and k weakest features along with their direction. RL = [0, . . . , 0]; WL = [0, . . . , 0]; for i ∈ [0, . . . , d− 1] do
for (x, z) ∈ S do r = true; w = true; for δ′ = η; δ′ ≤ δ; δ′+ = η do
if class(D(xf,i,δ′)) 6= class(D(x)) or CC(D,xf,i,δ′) < CC(D,x) then r=false; else w=false;
if r then RL[(i,+)] = RL[(i,+)] + 1; if w then WL[(i,+)] = WL[(i,+)] + 1; // a similar check for the negative direction − (with −η and −δ) to update the key (i,−)
return The keys (index-direction pairs) of the k maximal entries in RL and WL
linear in d · |S| · dδ/ηe · (Tp + TD), where d is the number of features, Tp the time to compute the feature perturbation xf,i,δ′ and TD the time to run xf,i,δ′ through the classifier D. The number of queries to the network is at most 2 · d · |S| · dδ/ηe+ |S|. The term |S| counts the number of queries for computing class(D(x)) and CC(D,x) for every (x, z) ∈ S, computed once at the beginning of Algorithm 1 (this step is omitted from Algorithm 1 for simplicity’s sake).
Our algorithm supports a trade-off between precision and performance: the larger the S and the smaller the η, the more precise the result, but with a higher number of queries to the network. In practice, even though Algorithm 1 is executed once per dataset (after which many neighborhoods can be analyzed for robustness or attacks), its running time can be high. Thus, in our experiments, we set |S| to 100, d to 1, 000 (i.e., we do not scan all features), and η = δ. Despite these substantial restrictions, we still observe good results in practice (see Section 7). This encourages us that even a coarse search for robust and weak features is sufficient to obtain larger provably robust neighborhoods and an adversarial example attack which is competitive with state-of-the-art attacks.

heading: 4 MAXIMALLY ROBUST FEATURE-GUIDED NEIGHBORHOODS

text:
In this section, we define feature-guided neighborhoods and explain how we find maximally robust neighborhoods. Given an input x, a feature i of f , and a scalar δ ∈ R+, the (f, i, δ)-neighborhood of x is the set Nf,iδ (x) = {xf,i,δ′ | δ′ ∈ [0, δ]} (the definitions for δ ∈ R− are similar and thus omitted). Given a DNN D, we say that Nf,iδ (x) is robust if D classifies all inputs in N f,i δ (x) the same. Our goal is to find maximally robust (f, i, δ)-neighborhoods for a given x and feature i of f (i.e., we look for a maximal scalar δ ∈ R+). To this end, we employ a binary search in a given range [0, uN ] (where uN is a constant). In each iteration of the search, we reason about the robustness of the current neighborhood using an existing analyzer, as shortly described. We note that for linear feature functions (e.g., PCA), the binary search is optimal. We further note that although our definition is general for any feature, larger neighborhoods are likely to be defined using the (most) robust features.
To verify robustness of a given (f, i, δ)-neighborhood, we translate it to an L∞-norm neighborhood. This neighborhood can be then analyzed using an existing local robust analyzer (e.g., Gehr et al. (2018); Katz et al. (2017); Singh et al. (2019b)). In L∞-norm neighborhoods, each input entry (e.g., a pixel) can be perturbed independently. Formally, given an input x and lower and upper bounds for every jth entry lj , u j , the L∞-norm neighborhood is: N(x) = {x′ | ∀j, x′j ∈ [x− lj , x+ uj ]}. (A special case is B neighborhoods, in which all bounds are , i.e., for all j, lj = u j = .) For linear feature functions (e.g., PCA), we translate (f, i, δ)-neighborhoods to L∞-norm ones as follows:
N∞f,i,δ(x) = {x′ | ∀j, x′j ∈ [min(xj , (xf,i,δ)j),max(xj , (xf,i,δ)j)]}.
For other feature functions, one has to obtain the minimal and maximal values of each input entry.

heading: 5 FEATURE-GUIDED ADVERSARIAL EXAMPLES

text:
In this section, we present our feature-guided attack which perturbs the weakest features. Our attack consists of two steps: perturbing the weakest features by a small δ and then greedily refining the adversarial example. In addition to the expected parameters (the classifier D, the input-output pair (x, z), and the feature function f ), the attack takes as input the set of weak features W consisting of indices and directions, a step scalar δadvs , and a maximal distortion scalar δ
M . The first step of the attack looks for the smallest δ ≤ δM , with granularity δadvs , for which xf,W,δ′ is an adversarial example. Here, xf,W,δ′ = f−1(f(x) + δW ), where δW ∈ Rd is a vector whose entries are zero except for indices from W whose entries are δ or −δ depending on their direction. If an adversarial example is found, the second step of the attack refines it by greedily attempting to recover pixels to their original value in x, while still guaranteeing that the example is misclassified by D. To reduce the number of queries to D and converge faster to a minimal adversarial example, the attack attempts to recover groups of adjacent pixels (e.g., of size 50) together. If it fails, it cuts the group size in half. In practice, we observe that this approach provides a good balance between reducing the number of queries and recovering many input entries to their original value.

heading: 6 INSTANTIATION WITH PCA

text:
In this section, we explain how we use PCA to instantiate our approach. We begin with a brief background, then present our instantiation and exemplify PCA-guided neighborhoods and attacks.
Background PCA projects inputs into an (interesting) set of features (dimensions), each represents a different aspect of the data and captures a different amount of variance (information). Technically, PCA is a statistical framework that projects a random variable x ∈ Rd onto a random variable y ∈ Rd, such that the components {yi}di=1 are uncorrelated and have maximal variance values. The set {yi}di=1 is defined by yi = uTi x ∈ R, such that ui ∈ Rd, where the ui-s are the principal components of x. The principal components are computed with the goals of (1) maximizing the variance of the components {yi}di=1 and (2) keeping these components uncorrelated. In practice, instead of the random variable x, we consider a data matrix X , consisting of n input samples. Given the principal components, we define the PCA transformation matrix by U = [u1, u2, . . . , ud]. We use U to project the dataset into the PCA domain and vice versa: Y = XU ∈ Rn×d, X = Y UT ∈ Rn×d.
PCA feature functions We observed that PCA provides better features when computed for inputs of the same class. Thus, for each class z, we define a feature function PCAz(x) = xTUz , where Uz is the PCA transformation matrix computed from inputs with output z. As a result, Algorithm 1 is executed c times, where c is the number of classes. The running time of computing the PCA feature functions is c ·min(|S|3, d3). In practice, we only compute the first d = 1, 000 PCA dimensions. Combined with the small size of S (|S| = 100 per class), the running time is a few minutes per class. We next show an example of a (PCA, i, δ)-neighborhood (Appendix A shows more examples). Figure 2(a) shows a frog image x from CIFAR10. The maximal for which the B (x) was proven
robust by ERAN (Gehr et al., 2018) was = 0.024. Figure 2(b) shows a maximally perturbed image in this neighborhood. The maximal δ for which the NPCA,0δ (x) was proven robust by ERAN was δ = −6.66 (the feature 0 represents lighting conditions). This PCA-guided neighborhood contains 10703x more images than the B (x) neighborhood. Figure 2(c) shows a maximally perturbed image in this neighborhood, while Figure 2(d) and Figure 2(e) show two other images in it. Figure 2(f) illustrates the semantic meaning of the feature we perturb (background lighting conditions): it shows several images obtained by first perturbing this feature in the PCA domain by a small constant (a multiplication of δ = 5) and then projecting the PCA perturbation back to the image domain.
Figure 3 shows examples of our PCA-guided attack (Appendix A has more examples). Each example shows a correctly classified input, our adversarial example, and the perturbation (scaled for better visualization). The leftmost example shows a traffic sign image from ImageNet whose adversarial example is classified as a missile by Inception-V3. The middle example shows an ostrich image from ImageNet whose adversarial example is classified as an hartebeest by the same model. The rightmost image shows an image of Blair whose adversarial example is classified by RESNET20 as Bush.

heading: 7 EVALUATION

text:
In this section, we evaluate our approach and the applications from Sections 4 and 5.
Setup We implemented our approach in Python using PyTorch (we also support Tensorflow models). We trained models and ran most experiments on a Tesla K80 GPU with 12GB RAM. Only for running ERAN (Gehr et al., 2018), we used a dual AMD EPYC 7742 server with 1TB RAM running Ubuntu 20.04.1. For computing the most robust and weakest features of a given class, we defined S as a set of 100 random inputs of that class (which were not part of the training set), d = 1, 000 (i.e., we considered only the first 1, 000 PCA features), k = 250, and δ = η = 1. For (f, i, δ)-neighborhoods, we set uN = 100. For our attack, we set δadvs = 0.1 and δ
M = 10. As an optimization, our attack iterates over k ∈ {50, 100, 250} to reduce the distortion level. We evaluate our approach on six datasets (described in Appendix B). Each is split into a training set, a set for computing PCA+Algorithm 1, and a set to evaluate our neighborhoods and attack. Our attack was tested on state-of-the-art networks, and our robustness analysis was done on networks taken from ERAN’s repository (denoted by E) and networks whose size is similar to the large networks from that repository. We trained most models, except for Inception-V3 for ImageNet (Szegedy et al., 2016) and the C&W models (Carlini & Wagner, 2017) for MNIST and CIFAR10 (and models marked with E).
PCA + Algorithm 1 analysis For each dataset, we computed the first d PCA features from the set S containing 100 images. This step took less than two minutes for all datasets. Then, for each model, we computed the most robust and weakest features among these dimensions. This step is executed once, after which these features are used to define multiple neighborhoods and adversarial examples. This step is executed separately for each class and thus can be naturally parallelized. The average running time of Algorithm 1 was less than 90 seconds for most datasets and models, and at most ten minutes for ImageNet. The number of queries is 2 · |S| · d · c = 2 · 105 · c, where c is the number of classes. While this number is not negligible, it is done as a preprocessing step (similarly to training a model as done by other attacks, e.g., Tu et al. (2019)). The amortized added queries of this step over the dataset ranges from a handful of queries (for ImageNet) to a few dozens (for MNIST).
Feature-guided neighborhoods To evaluate robustness of (f, i, δ)-neighborhoods, we ran several experiments. In each experiment, we fixed a model, a dataset, a class, and a robust feature i. We considered small models (3×100 and 5×250), medium-sized models (LeNet5 with ~10,000 neurons), models that are considered big for robustness analysis (C&W with ~77,000 neurons), convolutional
models of different sizes from ERAN’s repository, and a VGG-based model that we trained (~141,000 neurons). We computed the maximally robust (PCA, i, δ)-neighborhoods for the first ten images of that class. Table 1 reports the results: the average neighborhood volume (v= Σj uj − lj), the number of images in the neighborhood (shown as a power of ten: 10e; we take the average over the exponent; for average e = 0, we write 1), and the maximal pixel range (i.e., max{ uj − lj | j}). We compare our approach with the standard approach of computing maximally robust B (x) neighborhoods (using binary search and ERAN). Results indicate that (1) our neighborhoods have larger volumes: on average by 1.5x and up to 4.5x; (2) our neighborhoods have 1079x more images (average is over the exponent) and, for deep networks or complex datasets, often the maximal B neighborhood contains a single image, and (3) our neighborhoods have larger maximal pixel range. Figure 4 illustrates the semantic meaning of the PCA features presented in Table 1. For each dataset, class, and feature, it shows three images: an initial image (middle) and two images obtained by perturbing the feature by ±δ (for some δ). The three images are ordered by the feature’s robustness direction: if the direction is positive, then the rightmost image is the perturbation with respect to +δ; otherwise, the rightmost image is the perturbation with respect to −δ. The arrows in the figure show the robustness direction.
PCA-guided adversarial examples We next evaluate our attack. In each experiment, we fix a dataset and model, and run our attack for 100 correctly classified inputs (not used during training or computing the most robust/weakest features). For each adversarial example, we measure the number of queries posed to the network and the L2 distance from the original image. We measure these twice: (1) after perturbing the weakest features and obtaining the first adversarial example (denoted Qb and Lb2) and (2) after the refinement postprocessing step (denoted Q and L2). We compare our approach with state-of-the-art practical black-box attacks: AutoZOOM by Tu et al. (2019) (which also has a refinement postprocessing step) and GenAttack by Alzantot et al. (2019) . We also compare our attack to the C&W attack Carlini & Wagner (2017), which is a white-box attack (with a full access to the model, including the internal layers – unlike our setting which assumes access only to the input and output layers). Table 2 shows the results for our attack, AutoZoom, and C&W, all of which have success rate of 100%. Results indicate that (1) our attack obtains the initial adversarial examples (before postprocessing) with 12.2x fewer queries and with 2.5x less L2 distortion compared to AutoZOOM, (2) considering postprocessing, our attack generates adversarial examples with fewer queries and 2.8x less L2 distortion compared to AutoZOOM, and (3) our black-box attack has 1.8x more L2 distortion than the white-box attack of C&W (this is expected as a white-box setting provides the attacker with more knowledge). Due to lack of space, results for GenAttack are in Appendix C. Compared to GenAttack: (1) our attack obtains the initial adversarial examples with 18.7x fewer queries and with 4.1x less L2 distortion, and (2) our final adversarial examples have 16.7x less L2 distortion but with 29x more queries.
We next evaluate our attack for the same 100 inputs on models trained with ensemble adversarial training (Tramèr et al., 2018). To this end, we trained defended models for three datasets using trained RESNET50, RESNET20, and C&W models. We limited the query number to 10, 000. We compare our approach with AutoZoom and GenAttack. Table 3 shows the results. Results indicate that our attack has a higher success rate and in most cases it obtains smaller L2 distortion.
In Appendix D, we provide experiments comparing our approach to an attack which uses random PCA features instead of the weakest features. These experiments show the advantage of our attack.

heading: 8 RELATED WORK

text:
Adversarial examples and PCA Several works consider PCA for finding and defending against adversarial examples. Some works use it to detect adversarial examples (Hendrycks & Gimpel., 2017; Jere et al., 2019; Li & Li, 2017). Bhagoji et al. (2018) train a model using the top-k PCA components, while Carlini & Wagner. (2017) show that this approach is not immune to adversarial examples. These works focus on employing PCA as a detector of adversarial examples. In contrast, we use PCA as a feature extractor. Sanyal et al. (2020) show that encouraging DNNs to learn representations in lower-dimensional linear subspaces (including PCA) increases their robustness. Jetley et al. (2018) study classification quality versus vulnerability to adversarial attacks through principal directions and curvatures of the decision boundary. Zhang et al. (2020) use PCA to approximate an adversarial region which enables them to generate adversarial examples without a classifier. In contrast, we look for connections between features and classifiers’ behavior.
Feature analysis of DNNs Many works analyze a DNN with respect to features. Goswami et al. (2018) perturb face features manually, e.g., by covering the beard or eyes. Rozsa et al. (2019) focus on face images with pre-labeled features to study DNNs’ robustness. Wicker et al. (2018) suggest using SIFT to extract images’ local features and perturb them. Xie et al. (2019) suggest to denoise the features of the hidden CNN layers to increase robustness. In contrast, we take a black-box approach and automatically derive input features for which a DNN is robust. Ilyas et al. (2019) and Goh (2019) define robust and non-robust features (differently from us) and show that adversarial examples are linked to non-robust features. However, their features are inferred from the DNN, unlike our approach which considers features computed from the dataset. Further, we provide an approach to approximate the most robust and weakest features from a large set of features using a black-box access to the DNN.
Adversarial examples Many adversarial example attacks were introduced. Some are white-box attacks with full access to the model, e.g., FGSM (Goodfellow et al., 2015), IFGSM (Kurakin et al., 2017), PGD (Madry et al., 2018), C&W (Carlini & Wagner, 2017), and EAD (Chen et al., 2018). While successful, all rely on the assumption that the attacker has full access to the model’s parameters, which is often not true in practice. This encouraged others to study black-box attacks which only assume access to network’s input and output layers (i.e., with no information on the internal layers). Papernot et al. (2017) show a black-box attack relying on a substitute technique, where the adversary trains a representative network. Such methods suffer from low success-rate because they rely on the assumption of adversarial example transferability, which does not always hold. Chen et al. (2017) present a black-box attack relying on gradient-estimation. This approach obtains high success-rate, however it is inefficient because it requires a high number of queries to the network. Recent works introduce practical and efficient black-box techniques: AutoZoom (Tu et al., 2019) uses efficient random gradient-estimation, while GenAttack (Alzantot et al., 2019) employs a genetic algorithm. In contrast to these approaches, our black-box attack depends on weak dataset’s features.
Local robustness Several works present approaches to analyze local robustness of DNNs. Anderson et al. (2019); Gehr et al. (2018); Ghorbal et al. (2009); Singh et al. (2018) rely on abstract interpretation, Katz et al. (2017) extend the simplex method, Boopathy et al. (2019); Salman et al. (2019) rely on linear relaxations, Dvijotham et al. (2018); Raghunathan et al. (2018) use duality, and Singh et al. (2019c); Wang et al. (2018) combine solvers with approximate methods. These works analyze the robustness of L∞-norm neighborhoods. Balunovic et al. (2019); Engstrom et al. (2019); Fawzi et al. (2017); Singh et al. (2019b) analyze robustness to geometric transformations (e.g., rotation, scaling). In contrast, we analyze robustness of neighborhoods defined by input features.

heading: 9 CONCLUSION

text: We presented the concept of network robustness and weakness to feature perturbations. We approximated the most robust and weakest features via sampling and leveraged them to define feature-guided neighborhoods and adversarial examples. Experimental results show that our provably robust featureguided neighborhoods are much larger than the standard provably robust neighborhoods and that our adversarial examples require fewer queries and have lower L2 distortion compared to state-of-the-art.

heading: A ADDITIONAL EXAMPLES

text:
In this section, we show more examples of provably robust feature-guided neighborhoods and PCA-guided adversarial examples.
In Figure 5, we show for each dataset:
• an image; • a maximally perturbed input from the B (x) neighborhood, for the maximal that ERAN
proved robust ( is shown in the figure); • a maximally perturbed input from the (PCA, 1, δ)-neighborhood (δ is shown in the figure); • two more input examples from the (PCA, 1, δ)-neighborhood.
In the figure, we also indicate the average range of pixels (when translating the PCA features to the input domain) |u− l|avgPCA, and the maximal range of pixels |u− l|maxPCA. In B (x) neighborhoods, |u− l| = 2 · , for all pixels. These examples demonstrate that (1) provably robust PCA-guided neighborhoods are larger than their corresponding B (x) neighborhoods and (2) provably robust PCA-guided neighborhoods contain inputs which are semantically similar to the original image but are also visually different from it.
In Figure 6, we show PCA-guided adversarial examples, for ImageNet and an Inception-V3 model, computed on correctly classified inputs. The figure shows: the original image (left), the PCA-guided adversarial example (center), and the perturbation (right).

heading: B DATASETS

text:
In this section, we describe the datasets we used in our evaluation.
• MNIST: 28× 28 images of 0-9 digits, ten classes. • Fashion MNIST (F-MNIST): 28× 28 pixel images of fashion items, ten classes. • CIFAR10: 32× 32× 3 pixel images, ten classes.
We imported these datasets from the PyTorch library. We also considered the following datasets:
• LFW sklearn version: 62 × 47 images of funneled faces, each classified as a person. In total, there are 5,749 different people (i.e., classes) and the dataset contains 13,233 images. We ignored classes with fewer than 100 samples, and thus remained with 1,140 samples and five classes (Colin Powell, Donald Rumsfeld, George W. Bush, Gerhard Schroeder, and Tony Blair). We imported this dataset from the sklearn library.

heading: C COMPARISON TO GENATTACK

text: In this section, we compare our attack to GenAttack (Alzantot et al., 2019) on 100 correctly-classified inputs. Since GenAttack has no postprocessing step, we only report the number of queries Q and the L2 distortion. We limited the query number of both approaches to 5,000 (for lower number of queries, GenAttack has lower success rate). Table 4 shows the results. Results indicate that (1) our attack obtains the initial adversarial examples with 18.7x fewer queries and with 4.1x less L2 distortion, and (2) our final adversarial examples have 16.7x less L2 distortion but with 29x more queries.

heading: D COMPARISON TO RANDOM BASELINE

text: In this section, we show the advantage of using the weakest PCA features in our attack over randomlypicked PCA features. In each experiment, we fix a dataset and a model and run our attack. Figure 7 shows the success rate (S) as a function of the number of weak features (k). The success rate is the fraction of inputs for which the PCA-guided perturbation (Section 5) resulted in an adversarial example. We compare our approach to a random baseline which generates perturbations using k random PCA features. Results indicate that: (1) our approach succeeds in generating adversarial examples for all models (though smaller models are easier to fool); (2) using weak features has significantly better success rate than randomly selected features: on average 6x higher and up to 32x; (3) in most cases, the higher the k, the higher the success rate.

heading: E DISTORTION IN THE PCA DOMAIN

text: In this section, we report the L2 distortion of our attack in the PCA domain. Table 5 summarizes the results for all the benchmarks in Table 2.


summaries: In this paper, the authors present a new multi-task reinforcement learning (RL) algorithm. Since In general, the relationships between tasks is unknown a-priori, directly applying classical multi-task learning approaches that assume all tasks are related, could suffer from negative transfer. The authors propose to cluster tasks into disjoint groups: The proposed algorithm iterates through steps of assigning tasks to specific policies and training each policy only based on the respective assigned tasks (clusters). In the experiments, the authors compare their algorithm with two single-task learning baselines (SP: a single policy for all tasks and PPT: a policy per task) and a recent multi-task RL algorithm of Eramo et al. 2020 on Pendulum, Bipedal Walker, and Atari problems.

summaries: This paper proposes a multi-task RL algorithm that leverages unsupervised task clustering. The authors propose to initialize a number of policies, cluster each task based on its performance on different policies, and train each policy with data coming from tasks within the cluster. The paper shows that such kind of an EM style clustering can lead to better performance than single-task training and be more sample efficient more training each task independently on both tabular settings, continuous control experiments, and Atari.

summaries: The authors propose to approach multi-task RL problems in which tasks may differ considerably in transition functions/dynamics and reward functions as well as in the action space through task clustering. Specifically, tasks are modeled as belonging to separate task clusters defined by the return obtainable by individual policies i. All policies are evaluated on a single task and the relative cumulative discounted rewards over some iterations determines the assignment of tasks to policies. Simulations show the advantage in terms of number of training iterations on several tasks compared to a selection to other related algorithms.

abstractText: Meta-learning, transfer learning and multi-task learning have recently laid a path towards more generally applicable reinforcement learning agents that are not limited to a single task. However, most existing approaches implicitly assume a uniform similarity between tasks. We argue that this assumption is limiting in settings where the relationship between tasks is unknown a-priori. In this work, we propose a general approach to automatically cluster together similar tasks during training. Our method, inspired by the expectation-maximization algorithm, succeeds at finding clusters of related tasks and uses these to improve sample complexity. We achieve this by designing an agent with multiple policies. In the expectation step, we evaluate the performance of the policies on all tasks and assign each task to the best performing policy. In the maximization step, each policy trains by sampling tasks from its assigned set. This method is intuitive, simple to implement and orthogonal to other multi-task learning algorithms. We show the generality of our approach by evaluating on simple discrete and continuous control tasks, as well as complex bipedal walker tasks and Atari games. Results show improvements in sample complexity as well as a more general applicability when compared to other approaches.

authors:
Joshua Achiam
Harrison Edwards
Dario Amodei
Pieter Abbeel

title: Variational Option Discovery Algorithms. 2018

venue: URL https://arxiv.org/abs/1807.10299

authors:
Timo Bräm
Gino Brunner
Oliver Richter
Roger Wattenhofer

title: Attentive Multi-task Deep Reinforcement Learning

venue: In ECML PKDD,

authors:
James L. Carroll
Kevin Seppi

title: Task similarity measures for transfer in reinforcement learning task libraries

venue: In IJCNN,

authors:
Pablo Samuel Castro
Subhodeep Moitra
Carles Gelada
Saurabh Kumar
Marc G. Bellemare

title: Dopamine: A Research Framework for Deep Reinforcement Learning. 2018

venue: URL http: //arxiv.org/abs/1812.06110

authors:
Antoine Cully
Yiannis Demiris

title: Quality and Diversity Optimization: A Unifying Modular Framework

venue: IEEE Trans. Evol. Comput.,

authors:
Will Dabney
Georg Ostrovski
David Silver
Remi Munos

title: Implicit quantile networks for distributional reinforcement learning

venue: In ICML,

authors:
Marc Peter Deisenroth
Gerhard Neumann
Jan Peter

title: A Survey on Policy Search for Robotics

venue: Found. Trends Robot.,

authors:
A.P. Dempster
N.M. Laird
D.B. Rubin

title: Maximum likelihood from incomplete data via the em algorithm

venue: Journal of the Royal Statistical Society. Series B (Methodological),

authors:
Carlo D Eramo
Davide Tateo
Andrea Bonarini
Marcello Restelli
Politecnico Milano
Jan Peters

title: Sharing Knowledge in Multi-Task Deep Reinforcement Learning

venue: In ICLR,

authors:
Benjamin Eysenbach
Abhishek Gupta
Julian Ibarz
Sergey Levine

title: Diversity is all you need: Learning skills without a reward function

authors:
Scott Fujimoto
Herke van Hoof
David Meger

title: Addressing Function Approximation Error in Actor-Critic Methods

authors:
Matteo Hessel
Hubert Soyer
Lasse Espeholt
Wojciech Czarnecki
Simon Schmitt
Hado Van Hasselt

title: Multi-Task Deep Reinforcement Learning with PopArt

authors:
Timothy Hospedales
Antreas Antoniou
Paul Micaelli
Amos Storkey

title: Meta-learning in neural networks: A survey

authors:
R A Jacobs
M I Jordan
S E Nowlan
G E Hinton

title: Adaptive mixture of experts

venue: Neural Comput.,

authors:
Robert Jacobs
Michael Jordan

title: A competitive modular connectionist architecture

venue: Advances in neural information processing systems,

authors:
Robert A. Jacobs
Michael I. Jordan

title: Learning piecewise control strategies in a modular neural network architecture

venue: IEEE Trans. Syst. Man Cybern.,

authors:
Michael I. Jordan
Robert A. Jacobs

title: Hierarchical mixtures of experts and the EM algorithm

title: Transfer in Reinforcement Learning : a Framework and a Survey

authors:
Alessandro Lazaric
Mohammad Ghavamzadeh

title: Bayesian Multi-Task Reinforcement Learning

authors:
Kimin Lee
Younggyo Seo
Seunghyun Lee
Honglak Lee
Jinwoo Shin

title: Context-aware Dynamics Model for Generalization in Model-Based Reinforcement Learning

authors:
Hui Li
Xuejun Liao
Lawrence Carin

title: Multi-task reinforcement learning in partially observable stochastic environments

venue: J. Mach. Learn. Res.,

authors:
Marlos C. Machado
Marc G. Bellemare
Erik Talvitie
Joel Veness
Matthew J. Hausknecht
Michael Bowling

title: Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents

venue: Journal of Artificial Intelligence Research,

title: Some methods for classification and analysis of multivariate observations

venue: In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability,

authors:
M M Hassan Mahmud
Majd Hawasly
Benjamin Rosman
Subramanian Ramamoorthy

title: Clustering Markov Decision Processes

venue: For Continual Transfer

authors:
Marina Meila
Michael I. Jordan

title: Learning fine motion by markov mixtures of experts

venue: Advances in Neural Information Processing Systems 8,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei a Rusu
Joel Veness
Marc G. Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski
Stig Petersen
Charles Beattie
Amir Sadik
Ioannis Antonoglou
Helen King
Dharshan Kumaran
Daan Wierstra
Shane Legg
Demis Hassabis

title: Human-level control through deep reinforcement learning

venue: Nature,

authors:
Rémy Portelas
Cédric Colas
Katja Hofmann
Pierre-Yves Oudeyer

title: Teacher algorithms for curriculum learning of Deep RL in continuously parameterized environments

venue: CoRL,

authors:
Justin K. Pugh
Lisa B. Soros
Kenneth O. Stanley

title: Quality diversity: A new frontier for evolutionary computation

venue: Front. Robot. AI,

authors:
Matthew Riemer
Miao Liu
Gerald Tesauro

title: Learning abstract options

venue: In NeurIPS,

authors:
Sahil Sharma
Ashutosh Kumar Jha
Parikshit S. Hegde
Balaraman Ravindran

title: Learning to multi-task by active sampling

venue: ICLR 2018 - Conference Track,

authors:
Richard S. Sutton
Andrew G Barto

title: Reinforcement learning: an introduction

authors:
Gao Tang
Kris Hauser

title: Discontinuity-sensitive optimal control learning by mixture of experts

venue: In International Conference on Robotics and Automation,

authors:
Sebastian Thrun
Joseph O’Sullivan

title: Discovering Structure in Multiple Learning Tasks : The TC Algorithm

authors:
Rui Wang
Joel Lehman
Jeff Clune
Kenneth O. Stanley

title: Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions

authors:
Rui Wang
Joel Lehman
Aditya Rawal
Jiale Zhi
Yulun Li
Jeff Clune
Kenneth O. Stanley

title: Enhanced POET: Open-Ended Reinforcement Learning through Unbounded Invention of Learning Challenges and their Solutions

title: Learning from delayed rewards

venue: PhD thesis, King’s College,

authors:
Aaron Wilson
Alan Fern
Soumya Ray
Prasad Tadepalli

title: Multi-task reinforcement learning: A hierarchical Bayesian approach

authors:
Jiachen Yang
Brenden Petersen
Hongyuan Zha
Daniel Faissol

title: Single Episode Policy Transfer in Reinforcement Learning

authors:
Tianhe Yu
Saurabh Kumar
Abhishek Gupta
Sergey Levine
Karol Hausman
Chelsea Finn

title: Gradient Surgery for Multi-Task Learning

venue: URL

authors: Qiang Yang. A Survey on Multi-Task Learning.

title: URL https://arxiv

authors:
Zhuangdi Zhu
Kaixiang Lin
Jiayu Zhou

title: Transfer learning in deep reinforcement learning: A survey

authors:
Luisa Zintgraf
Kyriacos Shiarlis
Maximilian Igl
Sebastian Schulze
Yarin Gal
Katja Hofmann
Shimon Whiteson

title: VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via MetaLearning

authors: Bond MsPacman Phoenix RiverRaid SpaceInvaders

venue: B ADDITIONAL RESULTS

text:
1 INTRODUCTION
Imagine we are given an arbitrary set of tasks. We know that dissimilarities and/or contradicting objectives can exist. However, in most settings we can only guess these relationships and how they might affect joint training. Many recent works rely on such human guesses and (implicitly or explicitly) limit the generality of their approaches. This can lead to impressive results, either by explicitly modeling the relationships between tasks as in transfer learning (Zhu et al., 2020), or by meta learning implicit relations (Hospedales et al., 2020). However, in some cases an incorrect similarity assumption can hurt learning performance (Lazaric, 2012). Our aim with this paper is to provide an easy, straightforward approach to avoid human assumptions on task similarities.
An obvious solution is to train a separate policy for each task. However, this leads to a large amount of experience being required to learn the desired behaviors. Therefore, it is desirable to have a single agent and allow the sharing of knowledge between tasks. This is generally known as multi-task learning, a field which has received a large amount of interest in both the supervised learning and reinforcement learning (RL) community (Zhang & Yang, 2017). If tasks are sufficiently similar, a policy that is trained on one task provides a good starting point for another task, and experience from each task will help training in the other tasks. This is known as positive transfer (Lazaric, 2012). However, if the tasks are sufficiently dissimilar, negative transfer occurs and reusing a pre-trained policy
is disadvantageous. It can even lead to a worse performance than simply starting with a random initialization. Here using experience from the other tasks might slow training or even prevent con-
vergence to a good policy. Most previous approaches to multi-task learning do not account for problems caused by negative transfer directly and either accept its occurrence or limit their experiments to sufficiently similar tasks. We present a hybrid approach that is helpful in a setting where the task set contains clusters of related tasks, amongst which transfer is helpful. To illustrate the intuition we provide a conceptualized example in Figure 1. The figure shows a grid world with 12 tasks that can be naturally clustered in 4 clusters. Note however that our approach goes beyond this conceptual ideal and can be beneficial even if the clustering is not perceivable by humans a-priori.
Our approach is inspired by the expectation-maximization framework and uses a set of completely separate policies within our agent. We iteratively evaluate the set of policies on all tasks, assign tasks to policies based on their respective performance and train policies on their assigned tasks. This leads to policies naturally specializing to clusters of related tasks, yielding an interpretable decomposition of the full task set. Moreover, we show that our approach can improve the learning speed and final reward in multi-task RL settings. To summarize our contributions:
• We propose a general approach inspired by Expectation-Maximization (EM) that can find clusters of related tasks in an unsupervised manner during training.
• We provide an evaluation on a diverse set of multi-task RL problems that shows the improved sample complexity and reduction in negative transfer in our approach.
• We show the importance of meaningful clustering and the sensitivity to the assumed number of clusters in an ablation study

heading: 2 RELATED WORK

text:
Expectation-Maximization (EM) has previously been used in RL to directly learn a policy. By reformulating RL as an inference problem with a latent variable, it is possible to use EM to find the maximum likelihood solution, corresponding to the optimal policy. We direct the reader to Deisenroth et al. (2013) for a survey on the topic. Our approach is different: We use an EM-inspired approach to cluster tasks in a multi-task setting and rely on recent RL algorithms to learn the tasks.
In supervised learning, the idea of subdividing tasks into related clusters was proposed by Thrun & O’Sullivan (1996). They use a distance metric based on generalization accuracy to cluster tasks. Another popular idea related to our approach that emerged from supervised learning is the use of a mixture of experts (Jacobs et al., 1991). Here, multiple sub-networks are trained together with an input dependent gating network. Jordan & Jacobs (1993) also proposed an EM algorithm to learn the mixture of experts. While those approaches have been extended to the control setting (Jacobs & Jordan, 1990; 1993; Meila & Jordan, 1995; Cacciatore & Nowlan, 1993; Tang & Hauser, 2019), they rely on an explicit supervision signal. It is not clear how such an approach would work in an RL setting. A variety of other methods have been proposed in the supervised learning literature, for brevity we direct the reader to the survey by Zhang & Yang (2017), which provides a good overview of the topic. Our work differs in that we focus on RL, where no labeled data set exists.
In RL, task clustering has in the past received attention in works on transfer learning. Carroll & Seppi (2005) proposed to cluster tasks based on a distance function. They propose distances based on Q-values, reward functions, optimal policies or transfer performance. They propose to use the clustering to guide transfer. Similarly, Mahmud et al. (2013) propose a method for clustering Markov Decision Processes (MDPs) for source task selection. They design a cost function for their chosen transfer method and derive an algorithm to find a clustering that minimizes this cost function. Our approach differs from both in that we do not assume knowledge of the underlying MDPs and corresponding optimal policies. Furthermore, the general nature of our approach allows it to scale to complex tasks, where comparing properties of the full underlying MDPs is not feasible. An earlier approach by Wilson et al. (2007) developed a hierarchical Bayesian approach for multi-task RL. Their approach uses a Dirichlet process to cluster the distributions from which they sample full MDPs in the hope that the sampled MDP aligns with the task at hand. They then solve the sampled MDP and use the resulting policy to gather data from the environment and refine the posterior distributions for a next iteration. While their method is therefore limited to simple MDPs, our approach can be combined with function approximation and therefore has the potential to scale to MDPs with large or infinite state spaces which cannot be solved in closed form. Lazaric & Ghavamzadeh (2010) use a hierarchical Bayesian approach to infer the parameters of a linear value function and utilize
EM to infer a policy. However, as this approach requires the value function to be a linear function of some state representation, this approach is also difficult to scale to larger problems which we look at. Li et al. (2009) note that believe states in partially observable MDPs can be grouped according to the decision they require. Their model infers the parameters of the corresponding decision state MDP. Their approach scales quadratically with the number of decision states and at least linearly with the number of collected transitions, making it as well difficult to apply it to complex tasks.
More recent related research on multi-task RL can be split into two categories: works that focus on very similar tasks with small differences in dynamics and reward, and works that focus on very dissimilar tasks. In the first setting, approaches have been proposed that condition the policy on task characteristics identified during execution. Lee et al. (2020) use model-based RL and a learned embedding over the local dynamics as additional input to their model. Yang et al. (2020) train two policies, one that behaves in a way that allows the easy identification of the environment dynamics and another policy that uses an embedding over the transitions generated by the first as additional input. Zintgraf et al. (2020) train an embedding over the dynamics that accounts for uncertainty over the current task during execution and condition their policy on it. Our approach is more general than these methods as our assumption on task similarity is weaker. In the second group of papers, the set of tasks is more diverse. Most approaches here are searching for a way to reuse representations from one task in the others. Riemer et al. (2018) present an approach to learn hierarchical options, and use it to train an agent on 21 Atari tasks. They use the common NatureDQN network (Mnih et al., 2015) with separate final layers for option selection policies, as well as separate output layers for each task to account for the different action spaces. Eramo et al. (2020) show how a shared representation can speed up training. They then use a network strucuture with separate heads for each task, but shared hidden layers. Our multi-head baseline is based on these works. Bräm et al. (2019) propose a method that addresses negative transfer between multiple tasks by learning an attention mechanism over multiple sub-networks, similar to a mixture of expert. However, as all tasks yield experience for one overarching network, their approach still suffers from interference between tasks. We limit this interference by completely separating policies. Wang et al. (2020) address the problem of openended learning in RL by iteratively generating new environments. Similar to us, they use policy rankings as a measure of difference between tasks. However, they use this ranking as a measure of novelty to find new tasks, addressing a very different problem. Hessel et al. (2019) present PopArt for multi-task deep RL. They address the issue that different tasks may have significantly different reward scales. Sharma et al. (2018) look into active learning for multi-task RL on Atari tasks. They show that uniformly sampling new tasks is suboptimal and propose different sampling techniques. Yu et al. (2020) propose Gradient Surgery, a way of projecting the gradients from different tasks to avoid interference. These last three approaches are orthogonal to our work and can be combined with EM-clustering. We see this as an interesting direction for future work.
Quality-Diversity (QD) algorithms (Pugh et al., 2016; Cully & Demiris, 2018) in genetic algorithms research aim to find a diverse set of good solutions for a given problem. One proposed benefit of QD is that it can overcome local optima by using the solutions as ”stepping stones” towards a global optimum. Relatedly in RL, Eysenbach et al. (2018) and Achiam et al. (2018) also first identify diverse skills and then use the learned skills to solve a given task. While we do not explicitly encourage diversity in our approach, our approach is related in that our training leads to multiple good performing, distinct policies trained on distinct tasks. This can lead to a policy trained on one task becoming the best on a task that it was not trained on, similar to the ”stepping stones” in QD. However, in our work this is more a side-effect than the proposed functionality.

heading: 3 BACKGROUND AND NOTATION

text:
In RL (Sutton & Barto, 2017) tasks are specified by a Markov Decision Process (MDP), defined as tuple (S,A, P,R, γ), with state space S, action space A, transition function P (·|s, a), reward function R(s, a) and decay factor γ. As we are interested in reusing policies for different tasks, we require a shared state-space S and action-space A across tasks. Note however that this requirement can be omitted by allowing for task specific layers. Following prior work, we do allow for a task specific final layer in our Atari experiments to account for the different action spaces. In all other experiments however, tasks only differ in their transition function and reward function. We therefore describe a task as τ = (Pτ , Rτ ) and refer to the set of given tasks as T . For each task τ ∈ T we aim to maximize the discounted return Gτ = ∑t=L t=0 γ trτt , where r τ t ∼ Rτ (st, at) is the reward at
time step t and L is the episode length. Given a set of policies {π1, ..., πn}, we denote the return obtained by policy πi on task τ as Gτ (πi).

heading: 4 CLUSTERED MULTI-TASK LEARNING

text:
Algorithm 1: EM-Task-Clustering Initialize n policies {π1, ..., πn} while not converged do
. E-Step Ti ← ∅ for i ∈ {1, . . . , n} for τ ∈ T do
k ← argmaxiGτ (πi) Tk ← Tk ∪ τ
Ti ← T where Ti = ∅ . M-Step for πi ∈ {π1, ..., πn} do
t← 0 while t < TM do
τ ∼ Ti Train πi on τ for an
episode of L steps t← t+ L
As the growing body of literature on meta-, transfer- and multi-task learning suggests, we can expect a gain through positive transfer if we train a single policy πi on a set of related tasks Tk ⊂ T . On the flip side, the policy πi might perform poorly on tasks τ /∈ Tk. Moreover, training policy πi on a task τ /∈ Tk might even lead to a decrease in performance on the task set Tk through negative transfer. We incorporate these insights into our algorithm by modeling the task set T as a union of K disjoint task clusters T1, . . . , TK , i.e., T = ⋃K k=1 Tk with Ti ∩ Tj = ∅ for i 6= j. Tasks within a cluster allow for positive transfer while we do not assume any relationship between tasks of different clusters. Tasks in different clusters may therefore even have conflicting objectives. Note that the assignment of tasks to clusters is not given to us and therefore needs to be inferred by the algorithm. Note also that this formulation only relies on minimalistic assumptions. That is, we do not assume a shared transition function or a shared reward structure. Neither do we assume the underlying MDP to be finite and/or solvable in closed form. Our approach is therefore applicable to a much broader range of settings than many sophisticated models with stronger assumptions. As generality is one of our main objectives, we see the minimalistic nature of the model as a strength rather than a weakness.
Given this problem formulation we note that it reflects a clustering problem, in which we have to assign each task τ ∈ T to one of the clusters Tk, k ∈ {1, . . . ,K}. At the same time, we want to train a set of policies {π1, ..., πn} to solve the given tasks. Put differently, we wish to infer a hidden latent variable (cluster assignment of the tasks) while optimizing our model parameters (set of policies). An Expectation-Maximization (EM) (Dempster et al., 1977) inspired algorithm allows us to do exactly that. On a high level, in the expectation step (E-step) we assign each of the tasks τ ∈ T to a policy πi representing cluster Ti. We then train the policies in the maximization step (M-step) on the tasks they got assigned, specializing the policies to their clusters. These steps are alternatingly repeated — one benefiting from the improvement of the other in the preceding step — until convergence. Given this general framework we are left with filling in the details. Specifically, how to assign tasks to which policies (E-step) and how to allocate training time from policies to assigned tasks (M-step).
For the assignment in the E-step we want the resulting clusters to represent clusters with positive transfer. Given that policy πi is trained on a set of tasks Ti in a preceding M-step, we can base our assignment of tasks to πi on the performance of πi: Tasks on which πi performs well likely benefited from the preceding training and therefore should be assigned to the cluster of πi. Specifically, we can evaluate each policy πi ∈ {π1, . . . , πn} on all tasks τ ∈ T to get an estimate ofGτ (πi) and base the assignment on this performance evaluation. To get to an implementable algorithm we state two additional desiderata for our assignment: (1) We do not want to constrain cluster sizes in any way as clusters can be of unknown, non-uniform sizes. (2) We do not want to constrain the diversity of the tasks. This implies that the assignment has to be independent of the reward scales of the tasks, which in turn limits us to assignments based on the relative performances of the policies π1, ..., πn. We found a greedy assignment — assigning each task to the policy that performs best — to work well. That is, a task τk is assigned to the policy π = argmaxπi Gτk(πi). A soft assignment based on the full ranking of policies might be worth exploring in future work. Given the greedy assignment, our method can also be seen as related to k-means (MacQueen, 1967), a special case of EM.
In the M-step, we take advantage of the fact that clusters reflect positive transfer, i.e., training on some of the assigned tasks should improve performance on the whole cluster. We can therefore
randomly sample a task from the assigned tasks and train on it for one episode before sampling the next task. Overall we train each policy for a fixed number of updates TM in each M-step with TM independent of the cluster size. This independence allows us to save environment interactions as larger clusters benefit from positive transfer and do not need training time proportional to the number of assigned tasks.
Note that the greedy assignment (and more generally any assignment fulfilling desiderata 1 above) comes with a caveat: Some policies might not be assigned any tasks. In this case we sample the tasks to train these policies from all tasks τ ∈ T , which can be seen as a random exploration of possible task clusters. This also ensures that, early on in training, every policy gets a similar amount of initial experience. For reference, we provide a simplified pseudo code of our approach in Algorithm 1. Note that we start by performing an E-Step, i.e., the first assignment to clusters is based on the performance of the randomly initialized policies. Note also that our approach is independent of the RL algorithm used to train the policies in the M-step and can therefore be combined with any state-of-the-art RL algorithm.

heading: 5 EXPERIMENTS

text:
As a proof of concept we start the evaluation of our approach on two discrete tasks. The first environment consists of a chain of discrete states in which the agent can either move to the left or to the right. The goal of the agent is placed either on the left end or the right end of the chain. This gives rise to two task clusters, where tasks within a cluster differ in the frequency with which the agent is rewarded on its way to the goal. The second environment reflects the 2-dimensional gridworld presented in Figure 1. Actions correspond to the cardinal directions in which the agent can move and the 12 tasks in the task set T are defined by their respective goal. We refer an interested reader to Appendix A.1 for a detailed description of the environments.1
We train policies with tabular Q-learning (Watkins, 1989) and compare our approach to two baselines: In the first we train a single policy on all tasks. We refer to this as SP (Single Policy). In the other we train a separate policy per task and evaluate each policy on the task it was trained on. This is referred to as PPT (Policy per Task). Our approach is referred to as EM (Expectation-Maximization).
The learning curves as well as the task assignment over the course of training are shown in Figure 2 and Figure 3. Looking at the assignments, we see that in both environments our approach converges to the natural clustering, leading to a higher reward after finding these assignments. Both our EMapproach and PPT converge to an optimal reward in the chain environment, and a close to optimal reward in the corner-grid-world. However, PPT requires a significantly higher amount of environment steps to reach this performance, as it does not share information between tasks and therefore
1The implementation of all our experiments is also available in the supplementary material
has to do exploration for each task separately. SP fails to achieve a high reward due to the different tasks providing contradicting objectives.

heading: 5.1 PENDULUM

text:
Next we consider a simple continuous control environment where tasks differ in their dynamics. We use the pendulum gym task (Brockman et al., 2016), in which a torque has to be applied to a pendulum to keep it upright. Here the environment is the same in all tasks, except for the length of the pendulum, which is varied in the range {0.7, 0.8, ..., 1.3}, giving a total of 7 tasks. Note that there is no clear cluster boundary here.
We use Twin Delayed Deep Deterministic Policy Gradient (TD3) (Fujimoto et al., 2018) with hyperparameters optimized as discussed in Appendix A.2. We use n = 4 policies in all experiments (except for the ablation studies) and did not tune this hyperparameter. This was done to give a fair comparison to baseline approaches which do not have this extra degree of freedom. For application purposes the number of clusters can be treated as a hyperparameter and included in the hyperparameter optimization. We compare against a SP, PPT, gradient surgery Yu et al. (2020) and a multi-head network structure similar to the approach used by Eramo et al. (2020). Each policy in our approach uses a separate replay buffer. The multi-head network has a separate replay-buffer and a separate input and output layer per task. We adjust the network size of the multi-head baseline and SP to avoid an advantage of our method due to a higher parameter count, see Appendix A.2 for details.
The results are shown in Figure 4. In the figure we excluded 3 from the 12 runs of the gradient surgery baseline as those did not converge to a performance better than random. Still, the results show a worse sample complexity and higher variance compared to our approach. We also again observe that our approach clusters similar tasks together, leading to a better performance than with a SP agent, and a faster convergence than with PPT. Also the multi-head approach needs more experience to converge than our approach in this setup, even more than the PPT approach. We believe this is due to the inherent interference of learning signals in the shared layers. The cluster assignment in our approach is also intuitive, with two clusters focusing on the extremes (cf. Figure 4).

heading: 5.2 BIPEDAL WALKER

text:
As a more complex continuous control environment we focus on BipedalWalker from the OpenAI Gym (Brockman et al., 2016), which has previously been used in multi-task and generalization literature (Portelas et al., 2019; Wang et al., 2019; 2020). It consists of a bipedal robot in a twodimensional world, where the default task is to move to the right with a high velocity. The action space consists of continuous torques for the hip and knee joints of the legs and the state space consists of joint angles and velocities, as well as hull angle and velocity and 10 lidar distance measurements.
To test our approach, we designed 6 tasks inspired by track and field sports: Jumping up at the starting position, jumping forward as far as possible, a short, medium and long run and a hurdle run. As a second experiment, we create a set of 9 tasks by varying the leg length of the robot as well as the number of obstacles in its way. This task set is inspired by task sets in previous work (Portelas et al., 2019). Note that we keep the objective — move forward as fast as possible — constant here. We again use TD3 and tune the hyperparameters of the multi-head baseline and our approach (with n = 4 fixed) with grid-search. Experiment details and hyperparameters are given in Appendix A.3.
The results in Figure 5 (left) on the track and field tasks show a significant advantage in using our approach over multi-head TD3 or SP and a slightly better initial performance than PPT, with similar final performance. SP fails to learn a successful policy altogether due to the conflicting reward functions. In contrast, the results in Figure 5 (right) from the second task set show that SP can learn a policy that is close to optimal on all tasks here. The multi-head and PPT approaches suffer in this setup as each head/policy only gets the experience from its task and therefore needs more time to converge. Our approach can take advantage of the similarity of the tasks. We note that the experiments presented here reflect two distinct cases: One in which it is advantageous to separate learning, reflected by PPT outperforming SP, and one where it is better to share experience between tasks, reflected by SP outperforming PPT. Our approach demonstrates general applicability as it is the only one performing competitively in both. We provide an insight into the assignment of tasks to policies in Appendix B.1.

heading: 5.3 ATARI

text:
To test the performance of our approach on a more diverse set of tasks, we evaluate on a subset of the Arcade Learning Environment (ALE) tasks (Machado et al., 2018). Our choice of tasks is similar to
those used by Riemer et al. (2018), but we exclude tasks containing significant partial-observability. This is done to reduce the computational burden as those tasks usually require significantly more training data. We built our approach on top of the Implicit Quantile Network (IQN) implementation in the Dopamine framework (Dabney et al., 2018; Castro et al., 2018). We chose IQN due to its sample efficiency and the availability of an easily modifiable implementation. As the different ALE games have different discrete action spaces, we use a separate final layer and a separate replay buffer for each game in all approaches. We use the hyperparameters recommended by Castro et al. (2018), except for a smaller replay buffer size to reduce memory requirements. As in the Bipedal Walker experiments we fix the number of policies in our approach without tuning to n = 4. We choose the size of the network such that each approach has the same number of total tunable parameters. We provide the details in Appendix A.4.
The results are given in Figure 6. The good performance of PPT shows that the diversity of this task set is best addressed with a policy per task. Note that we did not expect our approach to outperform PPT here as our approach can only outperform PPT if there are similar tasks that can be clustered together. The diverse set of Atari games seems to violate this assumption. We note also that the multi-head approach is unable to learn any useful policy here due to negative transfer between tasks. This is in line with experiments in other research (Hessel et al., 2019). Our approach manages to overcome most of this negative interference, even with just 4 clusters. Task assignments in our approach are given in Appendix B.2.

heading: 5.4 ABLATIONS

text:
To gain additional insight into our approach, we perform two ablation studies on the discrete cornergrid-world environment and the pendulum environment.
First, we investigate the performance of our approach for different numbers of policies n. The results in Figure 7 show that using too few policies can lead to a worse performance, as the clusters cannot distinguish the contradicting objectives. On the other hand, using more policies than necessary increases the number of environment interactions required to achieve a good performance in the pendulum task, but does not significantly affect the final performance.
As a second ablation, we are interested in the effectiveness of the clustering. It might be possible that simply having fewer tasks per policy is giving our approach an advantage compared to SP or multi-head TD3. We therefore provide an ablation in which task-policy assignments are determined randomly at the start and kept constant during the training. Results from this experiment can be seen in Figure 8, with additional results in Appendix C. The results show that using random clusters performs significantly worse than using the learned clusters. This highlights the importance of clustering tasks meaningfully.

heading: 6 CONCLUSION

text:
We present an approach for multi-task learning in reinforcement learning (RL) that automatically clusters tasks into related subsets. Our approach uses a set of policies and alternatingly evaluates the policies on all tasks, assigning each task to the best policy and then trains policies on their assigned tasks. Since our approach can be combined with any underlying RL method, we evaluate it on a varied set of environments. We show its performance on sets of simple discrete tasks, simple continuous control tasks, two complex continuous control task sets and a set of Arcade Learning Environment tasks. We show that our approach is able to identify clusters of related tasks and use this structure to achieve a competitive or superior performance. We further provide an ablation over the number of policies in our approach, showing that too many policies can lead to slower convergence while too few policies can hurt performance. In another ablation we also highlight the need to cluster tasks meaningfully.
Our approach offers many possibilities for future extensions. One interesting direction would be hierarchical clustering. This could prove helpful for complicated tasks like the Atari games. It would also be interesting to see how our approach can be applied to multi-task learning in a supervised setting. Further, different assignment strategies with soft assignments could be investigated. Overall, we see our work as a good stepping stone for future work on structured multi-task learning.

heading: APPENDIX

heading: A EXPERIMENT DETAILS

text: In addition to the details provided here, the implementation of all experiments can be found in the supplementary material.

heading: A.1 GRID WORLD EXPERIMENTS

text:
In the first discrete task set we use a one-dimensional state-chain with 51 states, in which the agent starts in the middle and receives a reward for moving toward either the left or right end. As a reward we use r = 1|xag−xgoal| where xag is the position of the agent and xgoal is the goal position (either the left or right end of the chain). We give a reward of r = 20 if the goal position is reached. Depending on the task, the reward is given every 2, 4, 8 or 16 steps, or only at the goal position, and otherwise replaced by r = 0.
For our corner grid-world task set we use a 2D-grid-world with edge length 7 and three goal positions per corner (as depicted in Figure 1). The agent always starts in the center and receives a reward based on the distance to the target r = 1||xag−xgoal||2 , with || · ||2 being the Euclidean norm. A reward of r = 10 is given when the agent reaches the goal position.
In both tasks we use tabular Q-Learning with -greedy exploration. We start with 0 = 0.2 and decay the value as t = γt 0 with γ = 1 − 1 × 10−6. We use a learning rate of α = 0.2 to update the value estimates, as from the perspective of a single agent the environment can be regarded as stochastic. Further, we use a discount factor of γ = 0.9 and TM = 500 training steps per policy in each M-step and evaluate each policy on each task for three episodes during the E-step, using the greedy policy without exploration.

heading: A.2 PENDULUM

text: In our pendulum tasks we use a modified version of the Pendulum environment provided in OpenAI gym (Brockman et al., 2016). This environment consists of a single pendulum and the goal is to balance it in an upright position. The observation consists of the current angle θ, measured from the upright position, and current angular velocity represented as (sin θ, cos θ, θ̇). The reward for each time step is rt = −(θ2 + 0.1θ̇2 + 0.001a2), with a being the torque used as action. Every episode starts with a random position and velocity. To provide a set of tasks we vary the length of the pendulum in {0.7, 0.8, ..., 1.3}.

heading: A.2.1 HYPERPARAMETERS

text: Hyperparameters for our EM-TD3 and multi-head TD3 were tuned on the pendulum task set by grid search over learning rate α = {1×10−2, 3×10−3, 1×10−3}, batch-size b = {64, 128} and updaterate u = {1, 3, 5}, specifying the number of collected time-steps after which the value-function is updated. We increased the network size for multi-head TD3, so that it overall had more parameters than EM-TD3. This is done to eliminate a potential advantage of our approach stemming from a higher representational capacity. The tuned hyperparameters are given in Table 1. To represent the value functions and policies we use fully connected multi-layer perceptrons (MLPs) with two hidden layers with 64 units each. As activations we use ReLU on all intermediate layers, and tanh activations on the output. The values are then scaled to the torque limits per dimension. In EM, SP and PPT we use a separate network for each policy. For our multi-head baseline we share the hidden layers between tasks, but use separate input and output layers per task. Additionally, we increase the size of the first hidden layer to 96 in the multi-head approach, such that it has a similar total number of parameters as our EM approach. For SP and PPT we reuse the hyper-parameters from our EM approach. During the M-step, we train the agent for 5 × 104 steps per policy and during the E-step we evaluate each agent on each task by running 20 episodes without added exploration noise.

heading: A.3 BIPEDALWALKER

text:
For the BipedalWalker tasks we look at two different sets of tasks. The first set of tasks consists of different reward functions with mostly similar environments, inspired by track and field events. The tasks are jumping up, jumping a long distance, runs for different distances and a run with obstacles. In all tasks a reward of − ||a||1 is given to minimize the used energy. The position of the hull of the bipedal walker is denoted as (x, y). In the jump up task a reward of y − |x| is given upon landing, and = 3.5× 10−4. For the long jump task a reward of x−x0 is given upon landing, with x0 being the hull position during the last ground contact, = 3.5 × 10−4. The three runs consist of a sprint over a length of 67 units, with = 3.5×10−4, a run over 100 units, with = 3.5×10−4, and a long run over 200 units with = 6.5 × 10−4. The hurdles task is identical to the long run, but every 4 units there is an obstacle with a height of 1. Additionally, a reward of 0.1ẋ — a reward proportional to the velocity of the agent in the x-direction — is given during the run and hurdle tasks, to reward movement to the right.
The second set of tasks consists of varying obstacles and robot parameters. We vary the length of the legs in {25, 35, 45} and either use no obstacles, or obstacles with a spacing of 2 or 4 units apart and height of 1. This results in a total of 9 tasks. Here we use the standard reward for the BipedalWalker task r = 4.3ẋ−5|θ|− ||a||1 with θ being the angle of the walker head. Additionally, in all experiments r = −100 is given if the robot falls over or moves to far to the left.

heading: A.3.1 HYPERPARAMETERS

text: Hyperparameters for our EM-TD3 and multi-head TD3 approaches were tuned on the track and field task set by grid search over α = {1× 10−3, 3× 10−4, 1× 10−4}, batch-size b = {100, 1000} and update-rate u = {1, 3, 5}, u specifying the number of collected time-steps after which the valuefunction is updated. We reuse the optimal parameters found here on the task set with varying leg lengths and obstacles. For the SP and PPT baselines we reused the parameters from EM-TD3. We increased the network size for multi-head TD3, so that it overall had more parameters than EM-TD3. All hyperparameters are given in Table 2. During the M-step, we train the EM agent with 2 × 105 steps per policy and during the E-step we evaluate each agent on each task by running 20 episodes without added exploration noise.

heading: A.4 ATARI

text:
To test our approach on a more complex task, we evaluate it on a subset of the Atari games. The set of chosen games consists of Alien, Assault, BankHeist, ChopperCommand, DemonAttack, JamesBond, MsPacman, Phoenix, RiverRaid, SpaceInvaders, WizardOfWor and Zaxxon. As stated above, this task set is similar to the set of games used in Riemer et al. (2018), but without tasks requiring a large amount of exploration to save computation time.
Our implementation is based on the IQN implementation in the Dopamine framework (Dabney et al., 2018; Castro et al., 2018). As hyperparameters we use the default values recommended by Dopamine for Atari games, except the changes listed below: Due to the different action spaces, we use a separate replay buffer for each game, as well as a separate output layer, both for our EM, multihead and PPT approaches. We reduce the size of the replay buffer to 3 × 105 compared to 1 × 106 in the original paper, to reduce the memory demand. We use the normal NatureDQN network, but scale the size of the layers to ensure that each approach has a similar number of parameters. For our EM approach, we use TM = 2.5 × 105 trainings steps per M-step, and evaluate all policies on all tasks for 27000 steps in the E-step, using the greedy policy without random exploration. In both EM and the multi-head approach, we record how many transitions were performed in each M-Step and sample the task with the least transitions as next training task. This is done to ensure a similar amount of transitions and training steps per game, as episode lengths vary. This approach was proposed in Riemer et al. (2018).

heading: B ADDITIONAL RESULTS

heading: B.1 BIPEDAL WALKER

text:
In Figure 9 the assignments for 4 randomly chosen trials on the track and field task set are shown. We can see that in all trials the runs over different distances are grouped together with the long jump task. This is likely due to these tasks aligning well, as they both favor movements to the right. It is possible to learn the hurdles task with the same policy as the runs, due to the available LIDAR inputs. The hurdle task therefore sometimes switches between policies, but usually is learned by a separate policy. The jump up task is very different from the other tasks, as it is the only one not to involve movement to the right, and is therefore assigned to a separate policy.
In Figure 10 the assignments for 4 randomly chosen trials on the leg-length and obstacle task set are shown. As illustrated by the good performance of the SP approach shown in Figure 5, it is possible to learn a nearly optimal behavior with a single policy here. This makes learning a meaningful clustering significantly harder and sometimes leads to a single policy becoming close to optimal on all tasks, as in Trial 2. In most other trials the task set is separated into two or three different clusters based on the different leg lengths.

heading: B.2 ATARI

text: In Figure 11 the assignments of all three trials of our approach on the Atari task set are shown. While we see a consistency in assignments, we cannot identify a clearly repeated clustering across trial. We assume this is due to the high diversity of tasks preventing the identification of clearly distinguishable clusters. This lack of clearly distinguishable clusters might also be the reason for failing to reach the performance of PPT. Yet, the specialization of policies in our approach helps to avoid negative transfer as seen in Figure 6.

heading: C PERFORMANCE GAP TO RANDOM CLUSTERS

text:
In Figure 8 we investigated the importance of the E-Step in our approach, by comparing to an ablation which randomly assigns tasks to policies at the start. These results showed that using random assignments performs worse, highlighting the importance of using related clusters of tasks. Here we will investigate how the difference between the return when using our EM method GEM or random assignments Grand changes depending on the number of tasks. When using a single policy or a policy for each task our method becomes identical to the baselines. We hypothesize that the difference should be maximal when using as many policies as there are true underlying clusters in the task set.
To test this hypothesis we perform experiments on our grid-world task set with 12 goals distributed to the four corners and show the return gap GEM − Grand in Figure 12. The experiments confirm our hypothesis, showing that the return gap increases with the number of policies before reaching a maximum when it matches the true clusters at n = 4. Afterwards it starts to decrease.