summaries: The paper proposes to study how early stopping in optimization helps find confident examples. Overall, the paper is well-organized and easy to read. Although there is some parallel study regarding the theoretical aspect of how early stopping help finds confident examples (i.e., Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks, which has unfortunately not been cited), the paper focuses on the empirical perspective. A thorough empirical study illustrating how early stop works would interest the label noise community.

summaries: This paper presents a training approach on label noise datasets and outperforms state-of-art methods. It defines the samples whose average probability on assigned label in recent q iterations is largest among all labels as memorized samples, in the sense of the network memorize these samples. Then authors proposed two stage method which firstly early-stops at minimum validation error (or $\tau$ memorized rate), and then trains on maximal safe set that gathers memorized samples. The experiments compared several state-of-art approaches and showed that the proposed method benefits from early-stopping and safe set. Authors also showed that the prestopping idea can also be used to improve other approaches.

summaries: This paper proposes a training strategy for robustness against label noise. The training strategy is simple and straightforward. The neural network will first be trained on the entire dataset with all the noisy labels. After obtaining the network with lowest validation error, the network will be used to make a prediciton on the original training set and select a subset of it to construct a maximal safe set. Finally, the network will be findtuned on this maximal safe set. The training strategy is very similar to tradictional  self-training in semi-superivsed learning and co-training for domain adaptation ([Co-training for domain adaptation, NIPS 2011]), except that the proposed prestopping only iterate the procedure once.

abstractText: Noisy labels are very common in real-world training data, which lead to poor generalization on test data because of overfitting to the noisy labels. In this paper, we claim that such overfitting can be avoided by “early stopping” training a deep neural network before the noisy labels are severely memorized. Then, we resume training the early stopped network using a “maximal safe set,” which maintains a collection of almost certainly true-labeled samples at each epoch since the early stop point. Putting them all together, our novel two-phase training method, called Prestopping, realizes noise-free training under any type of label noise for practical use. Extensive experiments using four image benchmark data sets verify that our method significantly outperforms four state-of-the-art methods in test error by 0.4–8.2 percent points under existence of real-world noise.

authors:
Devansh Arpit
Stanislaw Jastrzebski
Nicolas Ballas
David Krueger
Emmanuel Bengio
Maxinder S Kanwal
Tegan Maharaj
Asja Fischer
Aaron Courville
Yoshua Bengio

title: A closer look at memorization in deep networks

venue: In ICML,

authors:
Avrim Blum
Tom Mitchell

title: Combining labeled and unlabeled data with co-training

venue: In COLT, pp

authors:
Lukas Bossard
Matthieu Guillaumin
Luc Van Gool

title: Food-101–mining discriminative components with random forests

venue: In ECCV, pp

authors:
Markus M Breunig
Hans-Peter Kriegel
Raymond T Ng
Jörg Sander

title: LOF: identifying densitybased local outliers

venue: In ACM sigmod record,

authors:
Haw-Shiuan Chang
Erik Learned-Miller
Andrew McCallum

title: Active Bias: Training more accurate neural networks by emphasizing high variance samples

venue: In NeurIPS,

authors:
Pengfei Chen
Ben Ben Liao
Guangyong Chen
Shengyu Zhang

title: Understanding and utilizing deep neural networks trained with noisy labels

venue: In International Conference on Machine Learning,

authors:
Bo Han
Quanming Yao
Xingrui Yu
Gang Niu
Miao Xu
Weihua Hu
Ivor Tsang
Masashi Sugiyama

title: Co-teaching: Robust training of deep neural networks with extremely noisy labels

authors:
Dan Hendrycks
Kimin Lee
Mantas Mazeika

title: Using pre-training can improve model robustness and uncertainty

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

title: Densely connected convolutional networks

venue: In CVPR,

authors:
Lu Jiang
Zhengyuan Zhou
Thomas Leung
Li-Jia Li
Li Fei-Fei

title: MentorNet: Learning datadriven curriculum for very deep neural networks on corrupted labels

authors:
Alex Krizhevsky
Ilya Sutskever
Geoffrey E Hinton

title: ImageNet classification with deep convolutional neural networks

venue: In NeurIPS, pp

authors:
Kuang-Huei Lee
Xiaodong He
Lei Zhang
Linjun Yang

title: Cleannet: Transfer learning for scalable image classifier training with label noise

authors:
Mingchen Li
Mahdi Soltanolkotabi
Samet Oymak

title: Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks

authors:
Xingjun Ma
Yisen Wang
Michael E Houle
Shuo Zhou
Sarah M Erfani
Shu-Tao Xia
Sudanthi Wijewickrema
James Bailey

title: Dimensionality-driven learning with noisy labels

authors:
Eran Malach
Shai Shalev-Shwartz

title: Decoupling “when to update" from “how to update

authors:
Samet Oymak
Zalan Fabian
Mingchen Li
Mahdi Soltanolkotabi

title: Generalization guarantees for neural networks via harnessing the low-rank structure of the jacobian

venue: arXiv preprint arXiv:1906.05392,

authors:
Giorgio Patrini
Alessandro Rozza
Aditya Krishna Menon
Richard Nock
Lizhen Qu

title: Making deep neural networks robust to label noise: A loss correction approach

authors:
Joseph Redmon
Santosh Divvala
Ross Girshick
Ali Farhadi

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

authors:
Scott Reed
Honglak Lee
Dragomir Anguelov
Christian Szegedy
Dumitru Erhan
Andrew Rabinovich

title: Training deep neural networks on noisy labels with bootstrapping

venue: In ICLR,

authors:
Mengye Ren
Wenyuan Zeng
Bin Yang
Raquel Urtasun

title: Learning to reweight examples for robust deep learning

authors:
Yanyao Shen
Sujay Sanghavi

title: Learning with bad training data via iterative trimmed loss minimization

authors:
Karen Simonyan
Andrew Zisserman

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

authors:
Hwanjun Song
Minseok Kim
Jae-Gil Lee

title: SELFIE: Refurbishing unclean samples for robust deep learning

authors:
Andreas Veit
Neil Alldrin
Gal Chechik
Ivan Krasin
Abhinav Gupta
Serge Belongie

title: Learning from noisy large-scale datasets with minimal supervision

authors:
Yisen Wang
Weiyang Liu
Xingjun Ma
James Bailey
Hongyuan Zha
Le Song
Shu-Tao Xia

title: Iterative learning with open-set noisy labels

authors:
Tong Xiao
Tian Xia
Yi Yang
Chang Huang
Xiaogang Wang

title: Learning from massive noisy labeled data for image classification

authors:
Xingrui Yu
Bo Han
Jiangchao Yao
Gang Niu
Ivor Tsang
Masashi Sugiyama

title: How does disagreement help generalization against label corruption

authors:
Chiyuan Zhang
Samy Bengio
Moritz Hardt
Benjamin Recht
Oriol Vinyals

title: Understanding deep learning requires rethinking generalization

heading: 1 INTRODUCTION

text:
By virtue of massive labeled data, deep neural networks (DNNs) have achieved a remarkable success in numerous machine learning tasks, such as image classification (Krizhevsky et al., 2012) and object detection (Redmon et al., 2016). However, owing to their high capacity to memorize any label noise, the generalization performance of DNNs drastically falls down when noisy labels are contained in the training data (Jiang et al., 2018; Han et al., 2018; Song et al., 2019). In particular, Zhang et al. (2017) have shown that a standard convolutional neural network (CNN) can easily fit the entire training data with any ratio of noisy labels and eventually leads to very poor generalization on the test data. Thus, it is challenging to train a DNN robustly even when noisy labels exist in the training data.
A popular approach to dealing with noisy labels is “sample selection” that selects true-labeled samples from the noisy training data (Jiang et al., 2018; Ren et al., 2018; Han et al., 2018; Yu et al., 2019; Song et al., 2019). Here, (1−τ)×100% of small-loss training samples are treated as true-labeled ones and then used to update a DNN robustly, where τ ∈ [0, 1] is a noise rate. This loss-based separation is well known to be justified by the memorization effect (Arpit et al., 2017) that DNNs tend to learn easy patterns first and then gradually memorize all samples. In practice, Han et al. (2018) empirically proved that training on such small-loss samples yields a much better generalization performance under artificial noise scenarios.
Despite its great success, Song et al. (2019) have recently argued that the performance of the lossbased separation becomes considerably worse depending on the type of label noise. For instance,
in symmetric noise (Figure 1(a)), the loss-based approach well separates true-labeled samples from false-labeled ones because many true-labeled ones exhibit smaller loss than false-labeled ones. On the other hand, in pair and real-world noises (Figures 1(b) and 1(c)), many false-labeled samples are misclassified as true-labeled ones because the two distributions overlap closely; this overlap confirms that the loss-based separation still accumulates severe label noise from many misclassified cases, especially in real-world noise or pair noise which is regarded as more realistic than symmetric noise (Ren et al., 2018; Yu et al., 2019). This limitation definitely calls for a new approach that supports any type of label noise for practical use.
In this regard, as shown in Figure 2(a), we thoroughly investigated the memorization effect of a DNN on the two types of noises and found two interesting properties as follows:
• A noise type affects the memorization rate for false-labeled samples: The memorization rate for false-labeled samples is faster with pair noise than with symmetric noise. That is, the red portion in Figure 2(a) starts to appear earlier in pair noise than in symmetric noise. This observation supports the significant overlap of true-labeled and false-labeled samples in Figure 1(b). Thus, the loss-based separation performs well only if the false-labeled samples are scarcely learned at an early stage of training, as in symmetric noise.
• There is a period where the network accumulates the label noise severely: Regardless of the noise type, the memorization of false-labeled samples significantly increases at a late stage of training. That is, the red portion in Figure 2(a) increases rapidly after the dashed line, in which we call the error-prone period. (See Section 3.2.1 for the details of estimating the error-prone period). We note that the training in that period brings no benefit. The generalization performance of “Default” deteriorates sharply, as shown in Figure 2(c).
Based on these findings, we contend that eliminating this error-prone period should make a profound impact on robust optimization.
In this paper, we propose a novel approach, called Prestopping, that achieves noise-free training based on the early stopping mechanism. Because there is no benefit from the error-prone period, Prestopping early stops training before that period begins. This early stopping effectively prevents a network from overfitting to false-labeled samples, and the samples memorized until that point are added to a maximal safe set because they are true-labeled (i.e., blue in Figure 2(a)) with high precision. Then, Prestopping resumes training the early stopped network only using the maximal safe set in support of noise-free training. Notably, our proposed merger of “early stopping” and “learning from the maximal safe set” indeed eliminates the error-prone period from the training process, as shown in Figure 2(b). As a result, the generalization performance of a DNN remarkably improves in both noise types, as shown in Figure 2(c).
1The learning rate, as usual, was decayed at 50% and 75% of the total number of training epochs.
To validate the superiority of Prestopping, DenseNet (Huang et al., 2017) and VGG-19 (Simonyan & Zisserman, 2015) were trained on both simulated and real-world noisy data sets, including CIFAR-10, CIFAR-100, ANIMAL-10N, and Food-101N. Compared with four state-of-the-art methods, Prestopping significantly improved test error by up to 18.1pp2 in a wide range of noise rates.

heading: 2 RELATED WORK

text:
Numerous studies have been conducted to address the problem of learning from noisy labels. A typical method is using “loss correction” that estimates the label transition matrix and corrects the loss of the samples in the mini-batch. Bootstrap (Reed et al., 2015) updates the network based on their own reconstruction-based objective with the notion of perceptual consistency. F-correction (Patrini et al., 2017) reweights the forward or backward loss of the training samples based on the label transition matrix estimated by a pre-trained normal network. R3: D2L (Ma et al., 2018) employs a simple measure called local intrinsic dimensionality and then uses it to modify the forward loss in order to reduce the effects of false-labeled samples in learning. Active Bias (Chang et al., 2017) heuristically evaluates uncertain samples with high prediction variances and then gives higher weights to their backward losses. Ren et al. (2018) include small clean validation data into the training data and re-weight the backward loss of the mini-batch samples such that the updated gradient minimizes the loss of those validation data. However, this family of methods is known to accumulate severe noise from the false correction, especially when the number of classes or the number of false-labeled samples is large (Han et al., 2018; Yu et al., 2019).
To be free from the false correction, many recent researches have adopted “sample selection” that trains the network on selected samples. These methods attempt to select true-labeled samples from the noisy training data for use in updating the network. Decouple (Malach & Shalev-Shwartz, 2017) maintains two networks simultaneously and updates the models only using the samples that have different label predictions from these two networks. R3: Wang et al. (2018) proposed an iterative learning framework that learns deep discriminative features from well-classified noisy samples based on the local outlier factor algorithm (Breunig et al., 2000). MentorNet (Jiang et al., 2018) introduces a collaborative learning paradigm that a pre-trained mentor network guides the training of a student network. Based on the small-loss criteria, the mentor network provides the student network with the samples whose label is probably correct. Co-teaching (Han et al., 2018) and Co-teaching+ (Yu et al., 2019) also maintain two networks, but each network selects a certain number of small-loss samples and feeds them to its peer network for further training. Compared with Co-teaching, Co-teaching+ further employs the disagreement strategy of Decouple. R1: ITLM (Shen & Sanghavi, 2019) iteratively minimizes the trimmed loss by alternating between selecting a fraction of small-loss samples at current moment and retraining the network using them. INCV (Chen et al., 2019) randomly divides the noisy training data and then utilizes cross-validation to classify true-labeled samples with removing large-loss samples at each iteration. However, their general philosophy of selecting small-loss samples works well only in some cases such as symmetric noise. RA: Differently to this family, we exploit the maximal safe set initially derived from the memorized samples at the early stop point.
Most recently, a hybrid of “loss correction” and “sample selection” approaches was proposed by Song et al. (2019). Their algorithm called SELFIE trains the network on selectively refurbished false-labeled samples together with small-loss samples. SELFIE not only minimizes the number of falsely corrected samples but also exploits full exploration of the entire training data. Its component for sample selection can be replaced by our method to further improve the performance. RA: For the completeness of the survey, we mention the work that provides an empirical or a theoretical analysis on why early stopping helps learn with the label noise. Oymak et al. (2019) and Hendrycks et al. (2019) have argued that early stopping is a suitable strategy because the network eventually begins to memorize all noisy samples if it is trained too long. Li et al. (2019) have theoretically proved that the network memorizes false-labeled samples at a later stage of training, and thus claimed that the early stopped network is fairly robust to the label noise. However, they did not mention how to take advantage of the early stopped network for further training. Please note that Prestopping adopts early stopping to derive a seed for the maximal safe set, which is exploited to achieve noise-free training during the remaining learning period. Thus, our novelty lies in the “merger” of early stopping and learning from the maximal safe set.
2A pp is the abbreviation of a percentage point.
3 ROBUST TRAINING VIA Prestopping

heading: 3.1 PRELIMINARIES

text:
A k-class classification problem requires the training data D = {xi, y∗i }Ni=1, where xi is a sample and y∗i ∈ {1, 2, . . . , k} is its true label. Following the label noise scenario, let’s consider the noisy training data D̃ = {xi, ỹi}Ni=1, where ỹi ∈ {1, 2, . . . , k} is a noisy label which may not be true. Then, in conventional training, when a mini-batch Bt = {xi, ỹi}bi=1 consists of b samples randomly drawn from the noisy training data D̃ at time t, the network parameter θt is updated in the descent direction of the expected loss on the mini-batch Bt as in Eq. (1), where α is a learning rate and L is a loss function.
θt+1 = θt − α∇ ( 1 |Bt| ∑ x∈Bt L(x, ỹ; θt) )
(1)
As for the notion of network memorization, a sample x is defined to be memorized by a network if the majority of its recent predictions at time t coincide with the given label, as in Definition 3.1.
Definition 3.1. (Memorized Sample) Let ŷt = Φ(x|θt) be the predicted label of a sample x at time t and Htx(q) = {ŷt1 , ŷt2 , . . . , ŷtq} be the history of the sample x that stores the predicted labels of the recent q times, where Φ is a neural network. Next, P (y|x, t; q) is formulated such that it provides the probability of the label y ∈ {1, 2, ..., k} estimated as the label of the sample x based on Htx as in Eq. (2), where [·] is the Iverson bracket3.
P (y|x, t; q) = ∑ ŷ∈Htx(q) [ŷ = y]
|Htx(q)| (2)
Then, the sample x with its noisy label ỹ is a memorized sample of the network with the parameter θt at time t if the condition in Eq. (3) holds.
argmaxyP (y|x, t; q) = ỹ (3)

heading: 3.2 TWO MAIN COMPONENTS AND PHASES

text: The key idea of Prestopping is learning from a maximal safe set with an early stopped network. Thus, the two components of “early stopping” and “learning from the maximal safe set” respectively raise the questions about (Q1) when is the best point to early stop the training process? and (Q2) what is the maximal safe set to enable noise-free training during the remaining period?

heading: 3.2.1 QUESTION 1: BEST POINT TO EARLY STOP

text:
It is desirable to stop the training process at the point when the network (i) not only accumulates little noise from the false-labeled samples, (ii) but also acquires sufficient information from the true-labeled ones. Intuitively speaking, as indicated by the dashed line in Figure 3(a), the best stop point is the moment when label precision and label recall in Definition 3.2 cross with each other because it is the best trade-off between the two metrics. The period beyond this point is what we call the error-prone period because label precision starts decreasing rapidly.
If the ground truth y∗ of a noisy label ỹ is known, the best stop point can be easily calculated by these metrics.
Definition 3.2. (Label Metrics) LetMt ⊆ D̃ be a set of memorized samples at time t. Then, label precision (LP) and recall (LR) (Han et al., 2018) are formulated as Eq. (4).
LP = |{(x, ỹ) ∈Mt : ỹ = y∗}|
|Mt| , LR = |{(x, ỹ) ∈Mt : ỹ = y∗}| |{(x, ỹ) ∈ D̃ : ỹ = y∗}|
(4)
However, it is not straightforward to find the exact best stop point without the ground-truth labels. Hence, we present two practical heuristics of approximating the best stop point with minimal supervision. These two heuristics require either a small clean validation set or a noise rate τ for the minimal supervision, where they are widely regarded as available in many studies (Veit et al., 2017; Ren et al., 2018; Han et al., 2018; Yu et al., 2019; Song et al., 2019).
3The Iverson bracket [P ] returns 1 if P is true; 0 otherwise.
• Validation Heuristic: If a clean validation set is given, we stop training the network when the validation error is the lowest. It is reasonable to expect that the lowest validation error is achieved near the cross point; after that point (i.e., in the error-prone period), the validation error likely increases because the network will be overfitted to the false-labeled samples. As shown in Figure 3(b), the estimated stop point is fairly close to the best stop point in both noise types.
• Noise-Rate Heuristic: If a noise rate τ is known, we stop training the network when the training error reaches τ×100%. If we assume that all true-labeled samples of (1−τ)×100% are memorized before any false-labeled samples of τ×100% (Arpit et al., 2017), this point indicates the cross point of label precision and label recall with their values to be all 1. This heuristic tends to perform worse than the validation heuristic because the assumption does not hold perfectly. We further discuss its quality in Appendix A.

heading: 3.2.2 QUESTION 2: CRITERION OF A MAXIMAL SAFE SET

text:
Because the network is early stopped at the (estimated) best point, the set of memorized samples at that time is quantitatively sufficient and qualitatively less noisy. That is, it can be used as a safe and effective training set to resume the training of the early stopped network without accumulating the label noise. Based on this intuition, we define a maximal safe set in Definition 3.3, which is initially derived from the memorized samples at the early stop point and gradually increased as well as purified along with the network’s learning progress. In each mini-batch Bt, the network parameter θt is updated using the current maximal safe set St as in Eq. (5), and subsequently a more refined maximal safe set St+1 is derived by the updated network.
Definition 3.3. (Maximal Safe Set) Let tstop be the early stop point. A maximal safe set St at time t is defined to be the set of the memorized samples of the network Φ(x; θt) when t ≥ tstop. The network Φ(x; θt) at t = tstop is the early stopped network, i.e., Ststop =Mtstop , and the network Φ(x; θt) at t > tstop is obtained by Eq. (5).
θt+1 = θt − α∇ ( 1 |B′t| ∑ x∈B′t L(x, ỹ; θt) )
B ′
t = {x|x ∈ St ∩ Bt}
(5)
Figure 4 shows the main advantage of learning from the maximal safe set during the remaining period. Even when the noise rate is quite high (e.g., 40%), this learning paradigm exploits most of true-labeled samples, in considering that the label recall of the maximal safe set was maintained very high in both CIFAR data sets regardless of the noise type. The label recall was maintained over 0.81 in symmetric noise and over 0.84 in pair noise even in CIFAR-100 with pair noise after the 80th epoch. Further, by excluding unsafe samples that might accumulate the label noise, the label precision of the maximal safe set tended to increase rapidly at the beginning of the remaining period; it was maintained over 0.98 in symmetric noise and over 0.94 even in CIFAR-100 with pair noise after the 80th epoch, which could not be realized by the small-loss trick (Han et al., 2018; Song et al., 2019; Shen & Sanghavi, 2019; Chen et al., 2019). R2:In Section 5.3, we have empirically verified that the maximal safe set is superior to the selected samples based on the small-loss trick.
0.7
0.8
0.9
1.0
64 70 80 90 100 110 120
L P
a n
d L
R
0.7
0.8
0.9
1.0
62 70 80 90 100 110 120
L P
a n
d L
R
Epochs Epochs
Approx. Stop Point Approx. Stop Point
Label Precision
Label Recall
“Symmetric Noise” “Pair Noise”
(a) R2:Label precision and label recall on CIFAR-10 (10 classes).
Algorithm 1 Prestopping with Validation Heuristic
INPUT: D̃: data, V: clean validation data, epochs: total number of epochs, q: history length OUTPUT: θt: network parameters
1: t← 1; θt ← Initialize the network parameter; 2: θtstop ← ∅; /* The parameter of the stopped network */ 3: for i = 1 to epochs do /* Phase I: Learning from a noisy training data set */ 4: for j = 1 to |D̃|/|Bt| do 5: Draw a mini-batch Bt from D̃; 6: θt+1 = θt − α∇ ( 1 |Bt| ∑ x∈Bt L(x, ỹ; θt) ) ; /* Update by Eq. (1) */ 7: val_err ← Get_Validation_Error(V , θt); /* A validation error at time t */ 8: if isMin(val_err) then θtstop ← θt; /*Save the network when val_error is the lowest*/ 9: t← t+ 1;
10: θt ← θtstop ; /* Load the network stopped at tstop */ 11: for i = stop_epoch to epochs do /* Phase II: Learning from a maximal safe set */ 12: for j = 1 to |D̃|/|Bt| do 13: Draw a mini-batch Bt from D̃; 14: St ← {x|argmaxyP (y|x, t; q) = ỹ}; /* A maximal safe set in Definition 3.3 */ 15: θt+1 = θt − α∇ ( 1 |St∩Bt| ∑ x∈St∩Bt L(x, ỹ; θt) ) ; /* Update by Eq. (5) */

heading: 16: t← t+ 1;

text: 17: return θt, St;

heading: 4 ALGORITHM DESCRIPTION

text:
4.1 MAIN ALGORITHM: Prestopping WITH VALIDATION HEURISTIC
Algorithm 1 describes the overall procedure of Prestopping with the validation heuristic, which is self-explanatory. First, the network is trained on the noisy training data D̃ in the default manner (Lines 3–6). During this first phase, the validation data V is used to evaluate the best point for the early stop, and the network parameter is saved at the time of the lowest validation error (Lines 7–8). Then, during the second phase, Prestopping continues to train the early stopped network for the remaining learning period (Lines 10–12). Here, the maximal safe set St at the current moment is retrieved, and each sample x ∈ St ∩ Bt is used to update the network parameter. The mini-batch samples not included in St are no longer used in pursuit of robust learning (Lines 14–15).
4.2 COLLABORATION WITH SAMPLE REFURBISHMENT: Prestopping+
To further improve the performance of Prestopping, we introduce Prestopping+ that employs the concept of selectively refurbishing false-labeled samples in SELFIE (Song et al., 2019). In detail,
the final maximal safe set Stend is retrieved from the first run of Prestopping, and then it is used as the true-labeled set for the next run of SELFIE with initializing the network parameter. Following the update principle of SELFIE, the modified gradient update rule in Eq. (6) is used to train the network. For each sample x in the mini-batch Bt, the given label ỹ of x is selectively refurbished into yrefurb if it can be corrected with high precision. However, the mini-batch samples included in Stend are omitted from the refurbishment because their label is already highly credible. Then, the mini-batch samples in the refurbished setRt are provided to update the network together with those in the final maximal safe set Stend . Refer to Song et al. (2019)’s work for more details.
θt+1 = θt−α∇ ( 1 |{x ∈ Bt|x ∈ Rt ∪ Stend}| ( ∑ x∈Rt∪Sctend L(x, yrefurb; θt)+ ∑ x∈Stend L(x, ỹ; θt) )) (6)

heading: 5 EVALUATION

text:
Data Sets: To verify the superiority of Prestopping, we performed an image classification task on four benchmark data sets: CIFAR-10 (10 classes)4 and CIFAR-100 (100 classes)4, a subset of 80 million categorical images (Krizhevsky et al., 2014); ANIMAL-10N (10 classes)5, a real-world noisy data of human-labeled online images for confusing animals (Song et al., 2019); FOOD-101N (101 classes)6, a real-world noisy data of crawled food images annotated by their search keywords in the FOOD-101 taxonomy (Bossard et al., 2014; Lee et al., 2018). We did not apply any data augmentation.
Noise Injection: As all labels in the CIFAR data sets are clean, we artificially corrupted the labels in these data sets using typical methods for the evaluation of synthetic noises (Ren et al., 2018; Han et al., 2018; Yu et al., 2019). For k classes, we applied the label transition matrix T: (i) symmetric noise: ∀j 6=iTij = τk−1 and (ii) pair noise: ∃j 6=iTij = τ ∧ ∀k 6=i,k 6=jTik = 0, where Tij is the probability of the true label i being flipped to the corrupted label j and τ is the noise rate. For the pair noise, the corrupted label j was set to be the next label of the true label i following the recent work (Yu et al., 2019; Song et al., 2019). To evaluate the robustness on varying noise rates from light noise to heavy noise, we tested five noise rates τ ∈ {0.0, 0.1, 0.2, 0.3, 0.4}. In contrast, we did not inject any label noise into ANIMAL-10N and FOOD-101N7 because they contain real label noise estimated at 8.0% and 18.4% respectively (Lee et al., 2018; Song et al., 2019).
Clean Validation Data: Recall that a clean validation set is needed for the validation heuristic in Section 3.2.1. As for ANIMAL-10N and Food-101N, we did exploit their own clean validation data; 5, 000 and 3, 824 images, respectively, were included in their validation set. However, as no validation data exists for the CIFAR data sets, we constructed a small clean validation set by randomly selecting 1, 000 images from the original training data of 50, 000 images. Please note that the noise injection process was applied to only the rest 49, 000 training images.
Networks and Hyperparameters: For the classification task, we trained DenseNet (L=40, k=12) and VGG-19 with a momentum optimizer. Specifically, we used a momentum of 0.9, a batch size of 128, a dropout of 0.1, and batch normalization. Prestopping has only one unique hyperparameter, the history length q, and it was set to be 10, which was the best value found by the grid search (see Appendix B.1 for details). The hyperparameters used in the compared algorithms were favorably set to be the best values presented in the original papers. As for the training schedule, we trained the network for 120 epochs and used an initial learning rate 0.1, which was divided by 5 at 50% and 75% of the total number of epochs.
Algorithms: We compared Prestopping and Prestopping+ with not only a baseline algorithm but also the four state-of-the-art robust training algorithms: Default trains the network without any processing for the label noise; Active Bias re-weights the backward loss of training samples based on their prediction variance; Co-teaching selects a certain number of small-loss samples to train the network based on the co-training (Blum & Mitchell, 1998); Co-teaching+ is similar to Co-teaching, but its small-loss samples are selected from the disagreement set; SELFIE selectively refurbishes noisy samples and exploits them together with the small-loss samples. All the algorithms were implemented
4https://www.cs.toronto.edu/~kriz/cifar.html 5https://dm.kaist.ac.kr/datasets/animal-10n 6https://kuanghuei.github.io/Food-101N 7In FOOD-101N, we used a subset of the entire training data marked with whether the label is correct or not.
using TensorFlow 1.8.0 and executed using 16 NVIDIA Titan Volta GPUs. For reproducibility, we provide the source code at https://bit.ly/2l3g9Jx. R2:In support of reliable evaluation, we repeated every task thrice and reported the average and standard error of the best test error, which was evaluated using the network at the time of the lowest validation error. Thus, the clean validation set was used to select the best model in all algorithms during the training procedure.

heading: 5.1 PERFORMANCE COMPARISON

text: Figures 5 and 6 show the test error of the seven training methods using two CNNs on two data sets with varying pair and symmetric noise rates, respectively. The results of Prestopping and Prestopping+ in Section 5 were obtained using the validation heuristic. See Appendix A for the results of the noise-rate heuristic. In order to highlight the improvement of Prestopping and Prestopping+ over the other methods, their lines are dark colored. Figure 7 shows the test error on two real-world noisy data sets with different noise rates. The best test errors are detailed in Tables 1 and 2 of Appendix C. RA: In addition, more experimental results on Tiny-ImageNet and Clothings (Xiao et al., 2015) data sets are discussed in Appendix B.2 and B.3.

heading: 5.1.1 RESULT WITH PAIR NOISE (FIGURE 5)

text: The performance trend in the two network architectures was similar with each other. In general, either Prestopping or Prestopping+ achieved the lowest test error in a wide range of noise rates on both CIFAR data sets. With help of the refurbished samples, Prestopping+ achieved a slightly better performance than Prestopping in CIFAR-10. However, an opposite trend was observed in CIFAR-100; this phenomenon was due to a large number of falsely corrected labels under the pair noise, especially when the number of classes is large (see Appendix B.4 for details). Although SELFIE achieved relatively lower test error among the existing methods, the test error of SELFIE was still worse than that of Prestopping. Co-teaching did not work well because many false-labeled samples were misclassified as clean ones; Co-teaching+ was shown to be even worse than Co-teaching despite it being an improvement of Co-teaching (see Section 5.4 for details). The test error of Active Bias was not comparable to that of Prestopping. The performance improvement of ours over the others increased as the label noise became heavier. In particular, at a heavy noise rate of 40%, Prestopping or Prestopping+ significantly reduced the absolute test error by 2.2pp–18.1pp compared with the other robust methods.

heading: 5.1.2 RESULT WITH SYMMETRIC NOISE (FIGURE 6)

text:
Similar to the pair noise, both Prestopping and Prestopping+ generally outperformed the other methods. In particular, the performance of Prestopping+ was the best at any noise rate on all data sets, because the synergistic effect was higher in symmetric noise than in pair noise. Quantitatively, at a heavy noise rate of 40%, our methods showed significant reduction in the absolute test error
by 0.3pp–17.5pp compared with the other robust methods. Unlike the pair noise, Co-teaching and SELFIE achieved a low test error comparable to Prestopping because true-labeled samples could be well separated from false-labeled ones by their small-loss criteria; hence, the dominance between Co-teaching and Active Bias was reversed so that the former slightly outperformed the latter.

heading: 5.1.3 RESULT WITH REAL-WORLD NOISE (FIGURE 7)

text: Both Prestopping and Prestopping+ maintained their dominance over the other methods under real-world label noise as well. Prestopping+ achieved the lowest test error when the number of classes is small (e.g., ANIMAL-10N), while Prestopping was the best when the number of classes is large (e.g., FOOD-101N) owing to the difficulty in label correction of Prestopping+. (Thus, practitioners are recommended to choose between Prestopping and Prestopping+ depending on the number of classes in hand.) Specifically, they improved the absolute test error by 0.4pp–4.6pp and 0.5pp–8.2pp in ANIMAL-10N and FOOD-101N, respectively. Therefore, we believe that the advantage of our methods is unquestionable even in the real-world scenarios.

heading: 5.2 CONVERGENCE ANALYSIS ON CLEAN VALIDATION DATA (FIGURE 8)

text: To verify that the error-prone period is eliminated, we plot the convergence of validation error for the seven training methods. The validation error of Default, Active Bias, and Co-teaching+ first reached their lowest values before the error-prone period, and then increased rapidly in the error-prone period. On the other hand, the remaining methods kept reducing the validation error even in that period. Notably, Prestopping+ achieved the lowest validation error at the end, owing to the successful merger of the advanced sample selection in Prestopping and the sample refurbishment in SELFIE. In addition, the performance of Prestopping was shown to be almost the same as and comparable to that of Prestopping+ in pair and symmetric noises, respectively. The validation error of SELFIE also converged faster than those of the other existing methods, but it was still inferior to Prestopping+. Thus, these results confirm that our two methods effectively overcome the error-prone period.

heading: 5.3 ACCURACY OF SAMPLE SELECTION (FIGURE 9)

text:
RA: Figure 9 shows the average accuracy of sample selection for two different selection strategies using DenseNet. Average accuracy is defined as the average ratio of the true-labeled samples in selected mini-batch samples during the training process. As mentioned earlier in Section 1, because the loss distribution of false-labeled samples was overlapped closely with that of true-labeled ones in pair noise, the average accuracy of the small-loss trick was worse with pair noise than with symmetric noise; it decreased to 75.0% as the noise rate increased in CIFAR-100 with pair noise. On the other hand, the maximal safe set maintained its dominance over the small-loss trick in all data sets regardless of the noise type. In particular, the average accuracy of the maximal safe set was 93.2%
Under review as a conference paper at ICLR 2020 Default Active Bias Co-teaching Co-teaching+ SELFIE LESSON LESSON+
Default Active Bias Co-teaching Co-teaching+ SELFIE Prestopping (Validation) Prestopping+ (Validation)
Small-loss Trick (Co-teaching) Maximal Safe Set (Prestopping)
6%
11%
16%
21%
0% 10% 20% 30% 40%
A v
er ag
e A
cc u
ra cy
Noise Rate Noise Rate
73%
82%
91%
100%
0% 10% 20% 30% 40%
73%
82%
91%
100%
0 30% 40%
CIFAR-100CIFAR-10 6%
11%
16%
21%
0% 10% 20% 30% 40%
A v
er ag
e A
cc u
ra cy
Noise Rate Noise Rate
73%
82%
91%
100
0 20 30% 40% 73%
82%
91%
100%
0% 10% 20% 30% 40%
CIFAR-100CIFAR-10
(a) Pair Noise. (b) Symmetric Noise.
even in CIFAR-100 with pair noise of 40%, which led to the huge performance improvement of Prestopping over Co-teaching in Figure 5(b).
5.4 ANATOMY OF Co-teaching+ (FIGURE 10)
Although Co-teaching+ is the latest method, its performance was worse than expected, as shown in Section 5.1. Thus, we looked into Co-teaching+ in more detail. A poor performance of Co-teaching+ was attributed to the fast consensus of the label predictions for true-labeled samples, especially when training a complex network. In other words, because two complex networks in Co-teaching+ start making the same predictions for true-labeled samples too early, these samples are excluded too early. As shown in Figures 10(a) and 10(b), the disagreement ratio with regard to the true-labeled samples dropped faster with a complex network than with a simple network, in considering that the ratio drastically decreased to 49.8% during the first 5 epochs. Accordingly, it is evident that Co-teaching+ with a complex network causes a narrow exploration of the true-labeled samples, and the selection accuracy of Co-teaching+ naturally degraded from 60.4% to 44.8% for that reason, as shown in Figure 10(c). Therefore, we conclude that Co-teaching+ may not suit a complex network.

heading: 6 CONCLUSION

text: In this paper, we proposed a novel two-phase training strategy for the noisy training data, which we call Prestopping. The first phase, “early stopping,” retrieves an initial set of true-labeled samples as many as possible, and the second phase, “learning from a maximal safe set,” completes the rest training process only using the true-labeled samples with high precision. Prestopping can be easily applied to many real-world cases because it additionally requires only either a small clean validation set or a noise rate. Furthermore, we combined this novel strategy with sample refurbishment to develop Prestopping+. Through extensive experiments using various real-world and simulated noisy data sets, we verified that either Prestopping or Prestopping+ achieved the lowest test error among the seven compared methods, thus significantly improving the robustness to diverse types of label noise. Overall, we believe that our work of dividing the training process into two phases by early stopping is a new direction for robust training and can trigger a lot of subsequent studies.

heading: 17: t← t+ 1;

text:
18: return θt, St;
A.1 RESULT WITH SYNTHETIC NOISE (FIGURE 11)
To verify the performance of Prestopping and Prestopping+ with the noise-rate heuristic in Section 3.2.1, we trained a VGG-19 network on two simulated noisy data sets with the same configuration as in Section 5. Figure 11 shows the test error of our two methods using the noise-rate heuristic as well as those of the other five training methods. Again, the test error of either Prestopping or Prestopping+ was the lowest at most error rates with any noise type. The trend of the noise-rate heuristic here was almost the same as that of the validation heuristic in Section 5.1. Especially when the noise rate was 40%, Prestopping and Prestopping+ significantly improved the test error by 5.1pp–17.0pp in the pair noise (Figure 11(a)) and 0.3pp–17.3pp in the symmetric noise (Figure 11(b)) compared with the other robust methods.
A.2 COMPARISON WITH VALIDATION HEURISTIC (FIGURE 12)
Figure 12 shows the difference in test error caused by the two heuristics. Overall, the performance with the noise-rate heuristic was worse than that with validation heuristic, even though the worse one outperformed the other training methods as shown in Figure 11. As the assumption of the noise-rate
heuristic does not hold perfectly, a lower performance of the noise-rate heuristic looks reasonable. However, we expect that the performance with this heuristic can be improved by stopping a little earlier than the estimated point, and we leave this extension as the future work.

heading: B SUPPLEMENTARY EVALUATION

text:
B.1 HYPERPARAMETER SELECTION (FIGURE 13)
Prestopping requires one additional hyperparameter, the history length q in Definition 3.1. For hyperparameter tuning, we trained DenseNet (L=40, k=12) on CIFAR-10 and CIFAR-100 with a noise rate of 40%, and the history length q was chosen in a grid ∈ {1, 5, 10, 15, 20}. Figure 13 shows the test error of Prestopping obtained by the grid search on two noisy CIFAR data sets. Regardless of the noise type, the lowest test error was typically achieved when the value of q was 10 in both data sets. Therefore, the history length q was set to be 10 in all experiments.
B.2 EXPERIMENT USING TINY-IMAGENET DATA SET (FIGURE 14)
R3: For a larger-scale experiment, we repeated the image classification task on Tiny-ImageNet (200 classes), a subset of ImageNet (Krizhevsky et al., 2012), with 100, 000 training and 10, 000 validation images. Because no test set exists, randomly selected 9, 000 images from the validation set were used as the test set, and the rest 1, 000 validation images were used as the clean validation set for the validation heuristic. The experimental configurations were the same as those in Section 5.
Figure 14 shows the test error of the seven training methods using VGG-19 on Tiny-ImageNet with varying noise rates. Similar to CIFAR data sets in Figures 5 and 6, both Prestopping and Prestopping+ outperformed the other robust methods in both noise types. The only difference wasDefault Active Bias Co-teaching Co-teaching+ SELFIE LESSON LESSON+
that there was no synergistic effect from collaboration with sample refurbishment because of the larger number of classes (i.e., 200). In particular, compared with other robust methods, Prestopping showed significant reduction in the absolute test error by 7.8pp–12.7pp at pair noise of 40% and 1.7pp–13.9pp at symmetric noise of 40%.
B.3 EXPERIMENT USING CLOTHING DATA SET (FIGURE 15)
R2: We additionally evaluated the superiority of Prestopping(+) on another challenging real-world noisy data set Clothing70k (14 classes), a subset8 of Clothing1M (Xiao et al., 2015), where its noise rate was estimated at 38.5%. For the Clothing70k data set, we randomly selected 70, 000 images from 1 million noisy training images in Clothing1M and used them as its noisy training set; we did exploit the original clean validation and test sets consisting of 14, 313 and 10, 526 images, respectively. The experimental configurations were the same as those in Section 5.
Figure 15 shows the test error of the seven training methods using two CNNs on Clothing70k with real-world noise of 38.5%. Overall, Prestopping and Prestopping+ significantly outperformed the other robust methods. In particular, Prestopping+ achieved the lowest test error because the number of classes was not that large (i.e., 14 classes). Compared with other state-of-the-art methods, it improved the absolute test error by 1.1pp–3.3pp using DenseNet and 0.7pp–5.8pp using VGG-19.
Default Active Bias Co-teaching Co-teaching+ SELFIE LESSON LESSON+
B.4 IMPACT OF NUMBER OF CLASSES ON Prestopping+ (FIGURE 16)
We investigate the impact of the number of classes on Prestopping+ under the pair noise of 40%. Figure 16 shows the ratio of refurbished samples used for training (hatched bar) with the refurbishing accuracy (solid line) on two data sets with 10 and 100 classes. When the number of classes is small (e.g., 10), Prestopping+ refurbished most of false-labeled samples very accurately; the refurbishing accuracy was consistently over 91.6% during the entire training period. On the other hand, when the number of classes is large (e.g., 100), the refurbishing accuracy drastically dropped from 92.0% to 76.7% as more samples were refurbished. Thus, as shown in Figure 16(b), collaboration with sample refurbishment is not always synergistic because such a significant drop in the refurbishing accuracy could induce many falsely corrected samples, especially when there are many classes.
8R2:We used a subset of Clothing1M to finish this experiment within the ICLR’20 rebuttal period.

heading: C COMPLETE RESULTS ON BEST TEST ERROR

text: Table 1 shows the test error of seven training methods using two CNNs on two simulated noisy data sets with varying noise rates. Table 2 shows the test error of seven training methods using two CNNs on two real-world noisy data sets with different noise rates.

heading: D CASE STUDY: NOISY LABELS IN ORIGINAL CIFAR-100

text: One interesting observation is a noticeable improvement of Prestopping+ even when the noise rate was 0%, as shown in Table 1(a). It was turned out that Prestopping+ sometimes refurbished the labels of the false-labeled samples which were originally contained in the CIFAR data sets. Figure 17 shows a few successful refurbishment cases. For example, an image falsely annotated as a “Boy” was refurbished as a “Baby” (Figure 17(a)), and an image falsely annotated as a “Mouse” was refurbished as a “Hamster” (Figure 17(c)). Thus, this sophisticated label correction of Prestopping+ helps overcome the residual label noise in well-known benchmark data sets, which are misconceived to be clean, and ultimately further improves the generalization performance of a network.

title: PRESTOPPING: HOW DOES EARLY STOPPING HELP GENERALIZATION


summaries: This paper addresses the very interesting problem of generalising to new actions after only training on a subset of all possible actions. Here, the task falls into different contexts, which are inferred from an associated dataset (like pixel data). Having identified the context, it is used in the policy which therefore has knowledge of which actions are available to it.

summaries: This paper studies the problem of generalization of reinforcement learning policies to unseen spaces of actions. To be specific, the proposed model first extracts actions’ representations from datasets of unstructured information like images and videos, and then the model trains a RL policy to optimize the objectives based on the learned action representations. Experiments demonstrate the effectiveness of the proposed model against state-of-the-art baselines in four challenging environments. This paper could be improved in the following aspects:

summaries: This paper deals with the problem of how to enable the generalization of discrete action policies to solve the task using unseen sets of actions. The authors develop a general understanding of unseen actions from their characteristic information and train a policy to solve the tasks using the general understanding. The challenge is to extract the action's characteristics from a dataset. This paper presents the HVAE to extract these characteristics and formulates the generalization for policy as the risk minimization.

abstractText: A fundamental trait of intelligence is the ability to achieve goals in the face of novel circumstances. In this work, we address one such setting which requires solving a task with a novel set of actions. Empowering machines with this ability requires generalization in the way an agent perceives its available actions along with the way it uses these actions to solve tasks. Hence, we propose a framework to enable generalization over both these aspects: understanding an action’s functionality, and using actions to solve tasks through reinforcement learning. Specifically, an agent interprets an action’s behavior using unsupervised representation learning over a collection of data samples reflecting the diverse properties of that action. We employ a reinforcement learning architecture which works over these action representations, and propose regularization metrics essential for enabling generalization in a policy. We illustrate the generalizability of the representation learning method and policy, to enable zero-shot generalization to previously unseen actions on challenging sequential decision-making environments. More training and testing videos can be found at sites.google.com/view/action-generalization/

authors:
Alessandro Achille
Giovanni Paolini
Glen Mbeng
Stefano Soatto

title: The information complexity of learning tasks, their structure and their distance

authors:
Jacob Andreas
Dan Klein
Sergey Levine

title: Modular multitask reinforcement learning with policy sketches

authors:
Yoshua Bengio
Aaron Courville
Pascal Vincent

title: Representation learning: A review and new perspectives

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Olivier Bousquet
Stéphane Boucheron
Gábor Lugosi

title: Introduction to statistical learning theory

venue: In Summer School on Machine Learning,

authors:
Yash Chandak
Georgios Theocharous
James Kostas
Scott Jordan
Philip S Thomas

title: Learning action representations for reinforcement learning

authors:
Maxime Chevalier-Boisvert
Lucas Willems
Suman Pal

title: Minimalistic gridworld environment for openai gym

authors:
John Co-Reyes
YuXuan Liu
Abhishek Gupta
Benjamin Eysenbach
Pieter Abbeel
Sergey Levine

title: Self-consistent trajectory autoencoder: Hierarchical reinforcement learning with trajectory embeddings

authors:
Karl Cobbe
Oleg Klimov
Chris Hesse
Taehoon Kim
John Schulman

title: Quantifying generalization in reinforcement learning

venue: arXiv preprint arXiv:1812.02341,

title: Unsupervised learning of disentangled representations from video

venue: In Advances in neural information processing systems,

authors:
Gabriel Dulac-Arnold
Richard Evans
Hado van Hasselt
Peter Sunehag
Timothy Lillicrap
Jonathan Hunt
Timothy Mann
Theophane Weber
Thomas Degris
Ben Coppin

title: Deep reinforcement learning in large discrete action spaces

venue: arXiv preprint arXiv:1512.07679,

authors:
Frederik Ebert
Chelsea Finn
Alex X Lee
Sergey Levine

title: Self-supervised visual planning with temporal skip connections

venue: In Conference on Robot Learning,

authors:
Harrison Edwards
Amos Storkey

title: Towards a neural statistician

venue: In International Conference on Learning Representations,

authors:
Kuan Fang
Yuke Zhu
Animesh Garg
Andrey Kurenkov
Viraj Mehta
Li Fei-Fei
Silvio Savarese

title: Learning task-oriented grasping for tool manipulation from simulated self-supervision

venue: arXiv preprint arXiv:1806.09266,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

authors:
Oliver Groth
Fabian B Fuchs
Ingmar Posner
Andrea Vedaldi

title: Shapestacks: Learning visionbased physical intuition for generalised object stacking

venue: In Proceedings of the European Conference on Computer Vision (ECCV),

authors:
Silviu Guiasu
Abe Shenitzer

title: The principle of maximum entropy

venue: The mathematical intelligencer,

authors:
Matthew Hausknecht
Peter Stone

title: Deep reinforcement learning in parameterized action space

venue: arXiv preprint arXiv:1511.04143,

authors:
Karol Hausman
Jost Tobias Springenberg
Ziyu Wang
Nicolas Heess
Martin Riedmiller

title: Learning an embedding space for transferable robot skills

authors:
Ji He
Jianshu Chen
Xiaodong He
Jianfeng Gao
Lihong Li
Li Deng
Mari Ostendorf

title: Deep reinforcement learning with a natural language action space

venue: arXiv preprint arXiv:1511.04636,

authors:
Irina Higgins
Arka Pal
Andrei Rusu
Loic Matthey
Christopher Burgess
Alexander Pritzel
Matthew Botvinick
Charles Blundell
Alexander Lerchner. Darla

title: Improving zero-shot transfer in reinforcement learning

title: Information theory and statistical mechanics

venue: Physical review,

authors:
Hyoungseok Kim
Jaekyeom Kim
Yeonwoo Jeong
Sergey Levine
Hyun Oh Song

title: EMI: Exploration with mutual information

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

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

title: Pytorch implementations of reinforcement learning algorithms

authors:
Adrien Laversanne-Finot
Alexandre Pere
Pierre-Yves Oudeyer

title: Curiosity driven exploration of learned disentangled goal spaces

venue: Proceedings of The 2nd Conference on Robot Learning,

authors:
Adam Lerer
Sam Gross
Rob Fergus

title: Learning physical intuition of block towers by example

authors:
Timothy P. Lillicrap
Jonathan J. Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement

authors:
Liyuan Liu
Haoming Jiang
Pengcheng He
Weizhu Chen
Xiaodong Liu
Jianfeng Gao
Jiawei Han

title: On the variance of the adaptive learning rate and beyond

authors:
Francesco Locatello
Stefan Bauer
Mario Lucic
Gunnar Raetsch
Sylvain Gelly
Bernhard Schölkopf
Olivier Bachem

title: Challenging common assumptions in the unsupervised learning of disentangled representations

authors:
Corey Lynch
Mohi Khansari
Ted Xiao
Vikash Kumar
Jonathan Tompson
Sergey Levine
Pierre Sermanet

title: Learning latent plans from play

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

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

title: Asynchronous methods for deep reinforcement learning

authors:
Ashvin V Nair
Vitchyr Pong
Murtaza Dalal
Shikhar Bahl
Steven Lin
Sergey Levine

title: Visual reinforcement learning with imagined goals

venue: In Advances in Neural Information Processing Systems,

authors:
Alex Nichol
Vicki Pfau
Christopher Hesse
Oleg Klimov
John Schulman

title: Gotta learn fast: A new benchmark for generalization in rl

venue: arXiv preprint arXiv:1804.03720,

authors:
Junhyuk Oh
Satinder Singh
Honglak Lee
Pushmeet Kohli

title: Zero-shot task generalization with multi-task deep reinforcement learning

authors:
German I Parisi
Ronald Kemker
Jose L Part
Christopher Kanan
Stefan Wermter

title: Continual lifelong learning with neural networks: A review

venue: arXiv preprint arXiv:1802.07569,

authors:
Deepak Pathak
Chris Lu
Trevor Darrell
Phillip Isola
Alexei A. Efros

title: Learning to control self-assembling morphologies: A study of generalization via modularity

venue: In arXiv preprint arXiv:1902.05546,

authors:
David Rohde
Stephen Bonner
Travis Dunlop
Flavian Vasile
Alexandros Karatzoglou

title: Recogym: A reinforcement learning environment for the problem of product recommendation in online advertising

venue: arXiv preprint arXiv:1808.00720,

authors:
Alvaro Sanchez-Gonzalez
Nicolas Heess
Jost Tobias Springenberg
Josh Merel
Martin Riedmiller
Raia Hadsell
Peter Battaglia

title: Graph networks as learnable physics engines for inference and control

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

title: Proximal policy optimization algorithms

venue: arXiv preprint arXiv:1707.06347,

authors:
Mike Schuster
Kuldip K Paliwal

title: Bidirectional recurrent neural networks

venue: IEEE Transactions on Signal Processing,

authors:
Xander Steenbrugge
Sam Leroux
Tim Verbelen
Bart Dhoedt

title: Improving generalization for abstract reasoning tasks using disentangled feature representations

venue: arXiv preprint arXiv:1811.04784,

authors:
Richard S Sutton
Andrew G Barto

title: Reinforcement learning: An introduction

venue: MIT press,

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

title: Policy gradient methods for reinforcement learning with function approximation

authors:
Guy Tennenholtz
Shie Mannor

title: The natural language of actions

venue: arXiv preprint arXiv:1902.01119,

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

title: Mujoco: A physics engine for model-based control

venue: In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems,

authors:
Hado Van Hasselt
Marco A Wiering

title: Using continuous action spaces to solve discrete problems

venue: In 2009 International Joint Conference on Neural Networks,

title: Principles of risk minimization for learning theory

title: The nature of statistical learning theory

venue: Springer science & business media,

authors:
Tingwu Wang
Renjie Liao
Jimmy Ba
Sanja Fidler

title: Nervenet: Learning structured policy with graph neural networks

authors:
Ziyu Wang
Josh S Merel
Scott E Reed
Nando de Freitas
Gregory Wayne
Nicolas Heess

title: Robust imitation of diverse behaviors

venue: Advances in Neural Information Processing Systems

authors:
Annie Xie
Frederik Ebert
Sergey Levine
Chelsea Finn

title: Improvisation through physical understanding: Using novel objects as tools with visual foresight, 2019

authors:
Danfei Xu
Suraj Nair
Yuke Zhu
Julian Gao
Animesh Garg
Li Fei-Fei
Silvio Savarese

title: Neural task programming: Learning to generalize across hierarchical tasks

venue: In International Conference on Robotics and Automation,

authors:
Brian D Ziebart
Andrew Maas
J Andrew Bagnell
Anind K Dey

title: Maximum entropy inverse reinforcement learning

heading: 1 INTRODUCTION

text:
Imagine visiting your friend for the first time, and you decide to cook your favorite dish there. But since you have never been in their kitchen before, there could be certain tools you have never seen, like an odd-shaped sponge. However, by looking at its porous texture or observing its interaction with water, you can understand that this object can absorb liquid. Later during cooking when you want to clean the table, you can select that sponge since you can relate its absorbing characteristics with another tool you have used for cleaning. Just like in this scenario, our tasks often involve making selections from novel or unseen entities. When we encounter such choices, we examine them to first understand their functionality which informs our selection process while solving a task.
Can machines also understand previously unseen choices and subsequently use them for solving tasks? From a reinforcement learning perspective, this brings an interesting question of how to enable generalization of discrete action policies to solve tasks using unseen sets of actions. Prior work in deep reinforcement learning has explored generalization over environments (Cobbe et al., 2018; Nichol et al., 2018), and tasks (Finn et al., 2017; Parisi et al., 2018). However, action space generalization is relatively unexplored and is crucial for agents to be flexible in the face of novel circumstances, like selecting an unseen sponge for a known task of cleaning in above example.
In this work, our goal is to develop a framework that reflects the two phases of solving action generalization: (1) general understanding of unseen discrete actions from their characteristic information (like appearance or behaviors), and (2) training a policy to solve tasks by utilizing this general understanding. However, an action can have diverse behaviors and hence requires a collection of data (e.g. different viewpoints, videos or state trajectories of how it effects on environment) to sufficiently express this diversity. Hence, the primary challenge is to develop a generalizable unsupervised learning method which can extract an action’s characteristics from a dataset constituting its diverse effects. To this end, we propose to embed actions’ datasets by extending the work on hierarchical variational autoencoders (Edwards & Storkey, 2017).
The obtained embeddings reflect an action’s general utility, and can be used as action representations in the downstream task of reinforcement learning. However, conventional reinforcement learning
algorithms utilize the available actions in a way that best optimizes a reward. This directly incentivizes a policy to overfit to the actions seen during training, just like the problem of overfitting to training data in supervised learning. To address this challenge, we formulate this problem as risk minimization (Vapnik, 1992) for reinforcement learning, and propose regularization objectives to enforce generalization of policy to unseen actions.
The main contributions of this paper are: (1) introducing the problem and a proposed solution to enable action space generalization in reinforcement learning, (2) representing an action with a dataset reflecting its diverse characteristics, and employing a generalizable unsupervised learning approach to embed these datasets. (3) a method to use learned action representations in reinforcement learning, and regularization methods to enable learning of generalizable policies.

heading: 2 RELATED WORK

text:
Generalization in reinforcement learning In typical deep reinforcement learning (RL) settings (Mnih et al., 2015; 2016; Lillicrap et al., 2015; Schulman et al., 2017), a policy or value network learns to act over an action space of fixed dimensionality. By taking states or observations as input to neural networks, these methods are able to generalize to unseen environment states drawn from a similar distribution as training (Cobbe et al., 2018; Nichol et al., 2018). Similarly, prior works have explored generalization in RL for unseen instructions (Oh et al., 2017), new sequences of subtasks (Andreas et al., 2017), manipulation of unseen tools (Fang et al., 2018; Xie et al., 2019), task demonstrations (Xu et al., 2017), and agent morphologies (Wang et al., 2018; Sanchez-Gonzalez et al., 2018; Pathak et al., 2019). In contrast, our framework enables zero-shot generalization of RL policies when the agent gets a previously unseen action set.
Unsupervised representation learning for downstream tasks Bengio et al. (2013) state representation learning of data makes it easier to extract useful information when building predictors. Prior
works show that such representations have been useful for a variety of downstream tasks, like classification and video prediction (Denton et al., 2017), visually representing objects for relational reasoning tasks (Steenbrugge et al., 2018), representing image-states for domain adaptation in RL (Higgins et al., 2017), and, representing goals for better exploration (Laversanne-Finot et al., 2018) and sample efficiency (Nair et al., 2018) in RL. In this paper, we show how unsupervised representation learning over datasets (Edwards & Storkey, 2017) can be used for embedding discrete actions, and enable generalization in the downstream task of reinforcement learning.
Action Representations Using continuous representations of discrete actions, a policy can be trained through a combined Q-function over state and action representations (He et al., 2015), or in an actor-critic architecture by selecting the nearest neighbor action vector to the policy’s continuous output (Van Hasselt & Wiering, 2009; Dulac-Arnold et al., 2015). Unlike our work, these prior works assume access to ground truth action representations, which are usually not readily available. In other related work, action representations are learned implicitly through inverse model on a fixed action space to ease learning in large discrete action spaces (Chandak et al., 2019) or for intrinsic reward (Kim et al., 2019). In contrast, we do not have the assumption of fixed action space as we learn action representations separately, and hence are able to incorporate new actions for the same policy. While Tennenholtz & Mannor (2019) pre-learn action representations explicitly using co-occurrence of actions in task-specific demonstrations, our generic embedding method applies to various modalities of datasets to represent actions, which are task-independent and hence suited for generalization to unseen actions.
Skill and Trajectory Embeddings In reinforcement learning, variational autoencoders (VAE) (Kingma & Welling, 2014) are often used for learning an abstraction for continuous entities like skills and state-action trajectories. Specifically, Co-Reyes et al. (2018) utilize a trajectory autoencoder for hierarchical RL, and Lynch et al. (2019) learn a latent space of trajectories and employ a goal-conditioned planner over it. Hausman et al. (2018) learn an embedding space of skills through a shared policy for different tasks, and utilize this space for solving other related tasks. In this paper, we extend the framework of hierarchical VAE (Edwards & Storkey, 2017; Achille et al., 2019) to trajectories, so as to embed even sequential datasets which are better indicative of action behavior. In general, an action can be a discrete skill choice, and an action’s behavior can be represented as the trajectory of effects it causes on the environment. Since individual trajectories are incapable of capturing the diverse effects of actions, we propose to use datasets for representing actions.

heading: 3 GENERALIZATION TO UNSEEN ACTIONS

text:
Our approach is based on the intuition that when humans encounter previously unseen discrete entities, we examine them to understand their functionality through visual inspection or physical interaction, before deciding what to select for a task. Once the general functionality is inferred, these discrete objects can be used as actions in decision-making tasks, like selecting a tool for cooking or furniture assembly. In this paper, we incorporate these two phases (Figure 2) to enable agents to utilize previously unseen actions: (1) extracting representations of actions from datasets of unstructured information (e.g. image, videos), and (2) training a reinforcement learning policy to utilize these action representations with the joint objective of generalization and reward maximization.
In order to represent actions, we note that an action can have diverse behaviors like how it interacts with its environment. Further, there can be various ways an agent observes this dataset. In the sponge example, the action exhibits diverse properties like absorption or compression, and the agent can observe this through porous texture (image) or through interacting with it (states trajectory). Therefore, in its most general form, information about an action can be expressed in the form of a diverse collection of unstructured data like images, videos or trajectories. To learn action representations in an unsupervised and generalizable, we use a hierarchical VAE and extend it to sequence data like videos (Section 3.2). Next, we show how a policy is trained to use these action representations as input, and propose training objectives for enabling generalization (Section 3.3).

heading: 3.1 PRELIMINARIES

text:
For a learning agent, we denote the entire set of possible discrete actions as A. For evaluation, we assume an episodic setting, where the agent only has a subset A ⊂ A of actions available to it. Each action a ∈ A has an associated dataset D = {x1, . . . ,xL} of observable samples xn ∼ P (x|a)
which are characteristic of the action a. During training, the agent only has access to a subset AK ⊂ A of known actions. During evaluation, action set A can even be totally unseen for the agent. The action set A constitutes the discrete action space of an episodic Markov decision process (MDP). Formally, {S,A, T , R, γ} defines the set of states, actions, transition probability, reward function, and discount factor of an MDP. Given a set of available actions A ⊂ A at any time step t, the core problem is to learn parameters θ of a policy πθ(at|st), which defines a probability distribution over actions at ∈ A for a state st. Since the available action sets A are stochastically sampled and the environments are in general stochastic, we primarily consider stochastic policies in this paper. The performance of πθ is evaluated based on a discounted return R = ∑T−1 t=0 γ
tr(st, at) where r is the reward function and T is the episode horizon. The aim is to train a policy which only has access to the known actions AK and its datasets, but generalizes to maximize reward on unseen actions.

heading: 3.2 UNSUPERVISED LEARNING OF ACTION REPRESENTATIONS

text:
We represent the diverse characteristics of an action with a dataset of observed information. To extract usable information from these action datasets, we propose an unsupervised representation learning method to learn action embeddings. Our key insight is that the common information underlying different samples of an action’s dataset best represents the general properties of that action.
Therefore, we aim to learn an action encoder to map each discrete action’s entire dataset to a continuous representation. For unsupervised learning of this encoder, we can use a variational autoencoder (VAE) with reconstruction objective (Kingma & Welling, 2014). However, since the input to VAE is in the form of a dataset, it should capture the information shared across multiple data samples. Therefore we encode both, the action datasets and the sample within each action’s dataset into a hierarchy of connected latent spaces.
Such a hierarchical VAE (HVAE) architecture has been explored by Edwards & Storkey (2017) for few-shot classification and clustering of datasets. We use it for the purpose of encoding action datasets and using them for generalization (Figure 2). HVAE is composed of an action VAE over datasets and an instance VAE over samples. The encoders and decoders of the instance VAE are conditioned on its parent action latent vector. For each action a and its associated dataset D = {x1, . . . ,xL}, the action encoder qa(c|D) is used to sample an action latent c, while regularized by an action prior pa(c). For each action sample x ∈ D, the instance encoder qs(z|x, c) is used to sample a latent z encoding the sample instance x, while conditioned on c. The prior distribution ps(z|c) as well as the decoder p(x|z, c) are also conditioned on the action latent. For each action dataset, ELBO comprises of reconstruction over data samples and the two KL divergence terms (Edwards & Storkey, 2017):
LD = Ec∼qa(.|D) [ ∑ x∈D Ez∼qs(.|x,c)[log p(x|z, c)]−D[qs(z|x, c)||ps(z|c)] ] −D[qa(c|D)||pa(c)]
(1)
We further extend this framework to incorporate sequential data like state trajectories and videos, as that is more suitable to express behaviors of actions. For a dataset of trajectories τ , we use a Bi-LSTM encoder for qa(c|D), and LSTM decoder p(τ |z, c, s) which also takes the initial state s of τ and reconstructs the rest of it (Schuster & Paliwal, 1997; Wang et al., 2017; Co-Reyes et al., 2018). For the case of video datasets, we also incorporated temporal skip connections (Ebert et al., 2017) from s by predicting an extra mask channel, to weigh contributions from the predicted frame and the first frame s.
For getting representations of any action a ∈ A (seen or unseen) through a trained HVAE, we use the action dataset encoder qa(c|Da) output’s mean as the representation ca (Figure 2). This choice of using mean as representation follows prior work like Higgins et al.; Steenbrugge et al. (2018), but one could also use sampling from the output distribution as representation, as done in Locatello et al. (2019). The generalizability of these representations to unseen actions depends on whether the action’s behaviors lie in the distribution of behaviors of known actions. Hence, the hierarchy in HVAE makes it an expressive encoder for actions, since even seemingly new discrete actions can have characteristics which belong to the distribution of previously seen effects.

heading: 3.3 LEARNING POLICIES OVER ACTION REPRESENTATIONS

text:
While solving tasks with new actions, humans first form a general interpretation of the behaviors of actions, and then utilize it to take appropriate actions. Similarly, once our agent learns actions representations based on observed datasets (section 3.2), it should learn to utilize them for solving tasks. This involves not only extracting the task-specific information from the representations, but also doing so in a generalizable manner so that it can utilize previously unseen action representations.
Here we assume access to an embedder φ, and hence the associated action representations ca = φ(Da) for each a ∈ A. Our aim is to learn a policy πθ(a|s,A, φ) which maximizes the expected reward under any set of available actions A ⊂ A. We propose to utilize the action representations ca as inputs to the policy, which acts as a function approximator over action representations and states. Specifically, our policy consists of a utility function fθ : S × Rd → R, which maps a d-dimensional action embedding and a state to its utility. The probability distribution over actions is simply defined as the Softmax over the utilities of each available action a′ ∈ A.
πθ(a|s,A) = efθ(s,ca)∑
a′∈A e fθ(s,ca′ )
(2)
We can train the parameters θ using policy gradient methods on π.

heading: 3.4 ENABLING GENERALIZATION TO UNSEEN ACTIONS

text:
The primary objective is to find parameters θ of a policy which maximizes rewards on unseen action sets A ⊂ A. We formulate this generalization problem with statistical learning theory (Vapnik, 1998; 2013), and propose regularization objectives which aim to satisfy its assumptions. The theory mainly deals with generalization in supervised learning problems with an assumption on training examples to be independent and identically distributed (i.i.d. sampled). In a reinforcement learning setup with action representations ca, the objective becomes minimizing the theoretical risk of the policy:
min θ Risk(πθ) = min θ Es,ca [L(fθ(s, ca), y∗)] = max θ EA∼A,a∼πθ(.|s,A)[Rπθ (s, ca)] (3)
Here L is a real-valued loss function which measures the optimality of policy hypothesis πθ (equivalently the utility function fθ) with respect to the output y∗ of an optimal stochastic policy π∗ at state s. While L, π∗ or y∗ cannot be defined in closed form, the definition of optimal policy (Sutton & Barto, 2018; Sutton et al., 2000) makes this objective equivalent to maximizing the cumulative reward R, given an unseen action space A and their action representations ca. Note that the expectation in Eq. 3 is also over states s drawn from environment, but dropped for readability.
During training, the agent only has access to a limited set of known actions AK ⊂ A. The standard reward maximization objective in RL with training set of actions, AK is equivalent to Empirical Risk Minimization (ERM) of the hypothesis πθ (Vapnik, 1992). Hence, the ERM training objective is:
max θ Ea∼πθ(.|s,AK)[Rπθ (s, ca)] (4)
However, a policy trained with ERM is prone to overfitting to data seen during training, just like in supervised learning. This problem becomes more severe for on-policy RL because the distribution of input data, (s, ca) used for training πθ is governed by the actions taken by πθ itself. This means that the policy can bias its own training data distribution towards a small subset of actions, while ignoring other actions, which could actually be more informative about the actions available at test time. Since there is no prior information on the distribution over action space A ⊂ A at test time, it is assumed to be uniform. Therefore, this discrepancy between training and evaluation due to the non-stationarity of RL training, breaks the identical distribution (in i.i.d.) assumption in statistical learning theory (Bousquet et al., 2003). To address this non-uniformity in training data, the following regularizing techniques are proposed to augment the ERM objective in Eq. 4:
(1) Maximum entropy regularization: Maximum entropy objective (Ziebart et al., 2008) augments Eq. 4 with the stochastic policy’s entropy H[πθ(a|s)] with weight β, as in Eq. 5. This makes the policy maximize environment reward, under the constraint of taking diverse actions. This helps generalization in two ways: (a) the input data distribution used for training the policy becomes more uniform over action representations, and (b) the policy outputs maximum entropy distributions which make the least assumptions about the possibly unseen set of available actions A ⊂ A, and hence by the principle of maximum entropy (Jaynes, 1957; Guiasu & Shenitzer, 1985) overfits the least.
max θ Ea∼πθ(.|s,AK)[R(s, ca) + βH[πθ(a|s)]] (5)
(2) Changing action spaces: The training data distribution can be made more uniform by sampling a set of available actions A ⊂ AK , uniformly in every episode. This blocks certain actions, making the policy select appropriate actions only from the available set A. Hence, the experience collected by the policy is uniformly spread over the known actions AK , making the training data distribution more identical to the assumed uniform distribution at test time. Eq. 6 shows this training objective:
max θ EA⊂AK ,a∼πθ(.|s,A)[R(s, ca) + βH[πθ(a|s)]] (6)
(3) Clustering similar actions: The known action space AK can contain several groups of similar actions (e.g. various knives for cutting), and a randomly sampled action space A may contain actions from each group. This can be exploited by the reward-maximizing policy during training to overfit to actions from particular groups, but it will fail to generalize if similar actions are unavailable while testing. To avoid this, we propose to utilize the pre-learned action representations (section 3.2) to partitionAK into a set of k groups GK = {g1 . . . gk}, where k is a hyperparameter. For every episode during training, an action set AG is built by sampling a subset of groups, G ⊂ GK and then sampling actions from G only. Two-step sampling ensures that certain groups of actions are blocked every episode, encouraging the policy to utilize underused action groups as well, making training data more uniform over the action representation space. We use equal-sized variant of k-means for clustering. The overall objective is formalized in Eq. 7 below:
max θ Ea∼πθ(.|s,AG)[R(s, ca) + βH[πθ(a|s)]], where AG ⊂ {a|a ∈ g, g ∈ G} and G ⊂ GK (7)
In experiments (Section 5), we perform model selection based on a validation set of actions. We further ablate each regularization techniques and analyze their contribution in different environments.

heading: 4 ENVIRONMENTS

heading: 4.1 GRID WORLD

text:
In GRID WORLD environment (Chevalier-Boisvert et al., 2018), an agent navigates a 2D 9x9 maze to reach a goal cell for a sparse reward. A column of lava is randomly placed in every episode, touching which ends the episode. The discrete action space consists of all 5-step macro actions, where each
macro-action is defined by a 5-length sequence of left, right, up or down movement. The entire action space of size 45 = 1024 actions is randomly split into a train and test set of 512 actions. The action datasets are collected on an empty grid where the agent is initialized at random locations. Two kinds of data types are used to represent the state sequence of agent - one-hot vectors and continuous (x,y) grid coordinates.

heading: 4.2 RECOMMENDER SYSTEM

text: The RECOMMENDER SYSTEM environment (Rohde et al., 2018) simulates how users may respond to product recommendations. Every episode, the agent must recommend items to a new user with the objective of maximizing the click through rate (CTR) for the recommendations. This simulated environment uses randomly initialized embeddings for recommendations (actions), and we use the same to demonstrate policy generalization to new actions. Action space of size 10,000 is randomly split equally into train and test actions.

heading: 4.3 CHAIN REACTION TOOL ENVIRONMENT (CREATE)

text: CREATE is a physics-based puzzle where the goal is to make a specified ball reach a goal position (blue), inspired by the popular video game The Incredible Machine. The agent must place tools in real time to manipulate the path of the ball to reach the goal position. The environment presents a challenging multi-step task, requiring the agent to select the tool to place as well as its position (x, y) on the screen. The agent has access to a subset of diverse tools such as trampolines, see-saws, cannons, funnels, and conveyor belts (Appendix C.2). The position aspect makes this a parameterized action space Hausknecht & Stone (2015) with both discrete and continuous components. Our policy architecture consists of another head to output this continuous vector and it is trained jointly with the discrete action. We solve 3 different CREATE tasks: Push, Navigate and Obstacle. The tools evaluated at test time are completely unseen tool types from those seen during training.

heading: 4.4 SHAPE STACKING

text: In SHAPE STACKING the agent must drop blocks on a table to build the highest standing tower. Our objective is different from prior works (Groth et al., 2018; Lerer et al., 2016) in that we maximize the tower height in an RL setting, whereas the prior work predicts the stability of the tower. Similarly to CREATE, the action space in Object Stacking, consists of (x, y) coordinates of where the object should be dropped above the table. This environment is shows our ability to generalize problem solving ability to a new action space in a complex 3D task. The action dataset here are images of the objects from various angles (or viewpoints). In this case the visual appearance of the object is sufficient to infer its functionality.

heading: 5 EXPERIMENTS

heading: 5.1 BASELINES & ABLATIONS

text:
Baselines: We compare against two policy architectures which can utilize action representations for generalization to unseen action sets. We also compare against a VAE-based non-hierarchical embedding learning method, to learn action representations from unstructured action data (see Fig. 3).
• Nearest Neighbor: During training, a policy is learned over all known actions. Given unseen actions, the policy’s output is used to select the nearest available action in embedding space. • Distance Based: Based on Dulac-Arnold et al. (2015), a continuous action-space policy outputs in the action embedding space and the closest available action to this output is selected. • Non hierarchical VAE: A shared VAE is trained over the samples across all action datasets. An action’s embedding is then computed as the mean over the embeddings of samples in its dataset.
Ablations: We individually ablate each of the three proposed regularization metrics in our method.
• Ours: no entropy: Trained without entropy regularization by setting entropy coefficient to zero. • Ours: no changing: Trained over the entire set of known actions without any action space sampling. • Ours: no clustering: Training action-space is uniformly sampled (Eq. 6), no k-means clustering. Alternate embeddings: We compare how the embedding learning method (HVAE) applies to various forms of unstructured data (Fig. 3). In CREATE, action datasets comprise of state trajectories for
tool behavior, except Ours (video) where video datasets are used instead. In Grid World, action datasets contain trajectories of states in one-hot representation, except in Ours (state) where states are real-valued 2D coordinates. Ours (Ground Truth) representations are not learned, but instead uses manually engineered representations for the actions. Detailed descriptions are present in Appendix C.

heading: 5.2 QUANTITATIVE RESULTS

text:
The generalization performance of the policy to unseen actions across all environments and method variations is shown in 3. As seen from the results our method or ablations all of our methods have the strongest ability to generalize to unseen actions across a variety of environments. The difference among our ablations is smaller in simpler environments like Grid World, Recommender systems and Shape Stacking, where the unseen action spaces are very similar to training actions. The effect of clustering-based sampling and entropy regularization can be seen for Obstacle and Navigate environments, which require solving the task with quite different tools at testing. CREATE Push is solvable with a wide variety of tools, and hence the no-entropy policy trains to a higher reward, and is able to generalize as well as many unseen tools can solve the task easily. The performance of our method against its variant with non-hierarchical VAE embeddings shows the importance of hierarchy in latent space to represent actions.
We test the generalizability of our embedder and policy for the task of zero-shot generalization to unseen actions. Specifically, our primary experiments across all four environments, discussed in section 4, train a policy on a fixed set of actions, tune hyperparameters on a separate evaluation set, and then test the ability to generalize to a new set of actions. We further provide qualitative analysis on cases where this generalization succeeds and fails. Finally, we evaluate how our method’s generalizability varies with the degree of difference between seen and unseen.

heading: 5.3 FURTHER ANALYSIS

text:
Qualitative results of the policy test performance are shown in 5. The left and middle column contain success cases. In the left column for CREATE we seen the policy, despite never having used on of the tools before, still be able to solve the task. Likewise, for shape stacking we see the policy able to use novel shapes to build a tall and stable pile to maximize the height. We also show cases of failure
to generalize in the right most column. In both cases the policy chooses the right types of actions and barely misses the objective.
We also analyze the conditions needed for generalization to unseen actions. We perform all analyses on CREATE Push task because of the large diversity of tool functionalities. We show generalization across changing physical tool parameters with angle and the embeddings the policy is trained and tested on. Finally, we show the effect of unseen versus seen actions on performance.

heading: 6 CONCLUSION

text: Generalization to novel circumstances is an important ability to have, for robust and widely applicable artificial agents. In this paper we propose the problem of generalization of reinforcement learning policies to unseen spaces of actions, with the use of action representations learned in an unsupervised manner. Our two-phase framework demonstrates how representation learning can be combined with the downstream task of reinforcement learning, specifically to represent actions. We demonstrate the efficacy of our methods on four challenging environments, and discuss which variants work when. The key takeaway is that when unseen actions are quite different from known actions, then more regularization helps to train generalizable policies.

heading: A ALGORITHM

text:
Algorithm 1 Training Require: Set of known actions AK = {a1, . . . aN} , associated action datasets {D1, . . . DN},
number of clusters k and number of clusters to sample from S Initialize HVAE model parameters for epoch = 1, 2, . . . do
Sample ai ∼ AK Compute loss in Eq. 1 for Di Update HVAE model with gradient of Eq. 1
end for Initialize empty set CK = {} Infer action representations cai = q µ a (c|Di),∀ai ∈ AK {µ denotes mean of distribution} Store action representations CK ← {cai . . . caN } Initialize policy parameters θ Compute k-means clustering on CK : Gk ← {g1, . . . , gk}
t← 0 Receive initial state s0 from ENV and initialize replay buffer while not done do
for step in rollout buffer do Sample clusters G ⊂ GK Sample action set Ag from clusters G as in Eq. 7 Compute fθ(st, caj ),∀aj ∈ Ag Sample action at ∼ πθ(s) using Eq. 2 st+1, rt ← ENV(st, at) Store experience (st, at, st+1, rt) in replay buffer t← t+ 1 end for Update θ based with PPO using rollout buffer
end while
Algorithm 2 Testing Require: Set of test actions AT = {aN+1, . . . aN+M} and action datasets {DN+1, . . . DN+M}
Infer action representations cai = q µ a (c|Di),∀ai ∈ AT while not done do Compute fθ(st, cai),∀ai ∈ AT Sample action at ∼ πθ(s) using Eq. 2 st+1, rt ← ENV(st, at) t← t+ 1 end while
HVAE implementation is based on the PyTorch implementation of Neural Stastician (Edwards & Storkey, 2017), and we use RAdam optimizer (Liu et al., 2019). For training our policy, we use PPO (Schulman et al., 2017; Kostrikov, 2018) with Adam optimizer (Kingma & Ba, 2015).

heading: B ANALYSIS OF TRAINING PROCEDURE AND MODELS

text:
B.1 VISUALIZATION OF HIERARCHICAL EMBEDDING SPACES
B.2 PERFORMANCE CURVES FOR ABLATIONS
B.3 FINE-TUNING COMPARISON
One possible way to adapt a policy to an unseen set of actions is to spend time fine-tuning the learned policy for the new action space. This process keeps the earlier layers of the policy but fine-tunes the actual action selection in the final layer by re-initializing the output layer. This process is able to adapt to an unseen action set of any size. However, this fine-tuning process can be time consuming which is why we try to achieve generalization in this paper. In Figure 10, we show the performance
of such fine tuning on the three CREATE tasks. As seen from the figure, it takes millions of steps to fine-tune, proving prohibitive for adaptive policies. On the other hand our framework generalizes to the new action space without the need for expensive RL retraining.

heading: C ENVIRONMENT DETAILS

text:
C.1 GRID WORLD
GRID WORLD environment consists of an agent and a lava wall with an opening as shown in figure 11. The lava wall can be either horizontal or vertical. The agent is spawned in a random position and can move in 4 directions (up, down, left, and right). The objective of the agent is to reach the goal in the bottom-right corner while avoiding lava.
Observation
Observation
Put trampoline Put trampoline
Put ramps Put trampoline Put bump ramp Put bump ramp
Action
Action
Observations: The observation space is 9x9x3 where three channels represent (1) object id (agent, wall, goal, lava), (2) color of an object, and (3) zero in each cell. The agent gets a flattened vector of this 9x9x3 matrix.
Actions: An action of the agent is 5 consecutive moves in 4 directions. Hence, 45 = 1, 024 actions are possible in total. Once the agent selects an action, it executes 5 sequential moves step-by-step. During an action execution, if the agent hits the boundary, it will stay in the current cell. If the agent steps on lava, the game will be terminated. The whole action set is divided into 8:1:1 split of train, validation and test action sets.
Rewards: GRID WORLD provides a sparse reward, 1− 0.9× (step/max_step), only when the agent reaches the goal. The reward is discounted based on the number of actions taken to encourage a shorter path to the goal.
Termination: Each game is terminated when the agent takes max_steps (64) actions or the agent reaches the goal or the lava wall.
Action Datasets: The action datasets are observations of an agent performing actions in a 80x80 grid with no obstacles. The observations constitute the trajectory of states the agent sees during application of a macro-action, starting from randomized initial states. A dataset of 1024 such trajectories is used to represent a single macro-action, and is encoded by the HVAE to an action representation which identifies the underlying action behavior. We consider three kinds of embeddings in our experiments:
• One-hot (default): State is represented by two 80-dimensional one-hot vectors of x and y coordinates of the agent’s locations on the 80x80 grid. Autoencoder reconstruction is based on a softmax cross-entropy loss over the states in the trajectory. The learned action embeddings are 16-dimensional.
• State: Two-dimensional continuous vector of x and y coordinates of the agent in the 80x80 grid. Reconstruction loss is computed based on Gaussian log-likelihood over the states in the trajectory. The learned action embeddings are 16-dimensional.
• Ground-truth: These are 5-dimensional embeddings containing the true knowledge of the five moves (up, down, left, right) that constitute a macro-action.
C.2 CHAIN REACTION TOOL ENVIRONMENT (CREATE)
CHAIN REACTION TOOL ENVIRONMENT (CREATE) is a physics-based puzzle where the objective is to make a target ball reach a goal position by placing variety of tools, inspired by the popular video game “The Incredible Machine”. The environment contains two movable objects, a marker ball (green) and a target ball (red). When a game starts, the marker ball is falling off from the top of the screen and an agent requires to place tools to redirect the kinetic energy of the marker ball to the target ball so that the target ball reaches the goal position (blue) as illustrated in Figure C.2. Observation
1
3
2
4
22 1
Put trampoline Put trampoline
Action
Observations: An observation for each time-step is an 84x84x3 image of a game screen and we use 3 frame stack to provide information about velocity and acceleration of the balls. Initially, the game contains 3 balls in the observation: marker ball (green), target ball (red), and goal ball (blue).
Actions: CREATE contains 1,737 tools of type: ramps, trampolines, walls, balls, floor, conveyor belts, funnel, polygons of different shapes, cannons, fans and buckets. We also have an action for No-Operation. The whole tool set is divided into train (939), validation (400) and test sets (400). Every time-step, the agent outputs a parameterized action, i.e. a discrete-continuous action which has three values (tool, x, y), where tool specifies which tool to place and (x, y) represents the position of the tool in the screen.
Rewards: The agent gets +1 reward when the marker ball hits the target ball, and +10 reward when the target ball passes the goal. In addition to reward for success, the environment provides some intermediate rewards. For every time-step, +0.01 reward is given to encourage the agent to keep balls inside the screen. At the same time, an invalid action is penalized by giving -0.01 reward (e.g., placing a tool outside of the screen or placing a tool on top of other tools).
Termination: Each game is terminated when the agent takes 20 actions, or the marker ball goes out of the screen before it hits the target ball, or the target ball goes out of the screen before it passes the goal.
Action Dataset: The action dataset is constructed by testing the properties of each tool through scripted interactions with a probe ball. A ball is launched at a given tool from various angles and speeds and then interacts with the tool. The properties of the tool will determine the deflection path of the ball. Testing interaction from various angles and speeds helps to build a better understanding of the tool. The collected datasets consist of 1024 trajectories of length 10 of the ball’s interaction with the tool. Each trajectory consists of observations in the form of either environment state (default) or 48x48 gray-scale images (Ours (image) in Fig. 3). We consider three kinds of embeddings in our experiments:
• State trajectory (default): Each environment state in a trajectory is represented by 2D coordinates and 2D velocity of the probe ball, concatenated with 2D tool’s location. Autoencoder reconstruction is based on Gaussian log-likelihood over the states in the trajectory. The learned action embeddings are 128-dimensional.
• Video: Each state in a trajectory is represented by 48x48 gray-scale image, which makes the trajectory a video of probe ball’s interaction with the tool. Autoencoder reconstruction is based on Gaussian log-likelihood over the images in the input video. The learned action embeddings are 128-dimensional. • Ground-truth: These are 32-dimensional embeddings containing the true knowledge of the
tool in the form of a one-hot encoding of the tool type along with its properties such as angle, length, elasticity, etc.
C.3 SHAPE STACKING
SHAPE STACKING is a mujoco simulation environment (Todorov et al., 2012) where the agent is given a set of objects of different shapes of varying sizes, for instance, cubes, rectangles, spheres, round cylinders, archs, etc. The objective is to stack a tower as high as possible by choose the appropriate objects given in a particular episode.
Observations: An observation for each time-step is an 84x84x3 image of the shapes laying on the table.
Actions: In total there are 900 distinct shapes in the environment. 675 are used for learning the policy. The remaining 225 are used for evaluating performance on unseen actions. The same types of polygons do not appear in both train and test. Like CREATE the action space includes making a discrete selection over the shape to drop and the x, y coordinates to drop the shape above the scene.
Rewards: The agent receives a reward for the positive difference in height of the tower. A penalty of −0.25 is given for every repeated shape. Termination: The game is terminated either after the tower of shapes exceeds 3 in height or after 10 shape placements.
Action Dataset: In Shape Stacking the functionality of each action is characterized by the physical appearance of the shape. For this reason, the action dataset consists of images of the shape from various angles and heights (viewpoints). 1,024 images of resolution 84x84 constitute the dataset to represent a single shape.