summaries: The paper presents a method for identifying and selecting the most informative subset of the training dataset in order to reduce training time while maintaining test accuracy. The method consists of training a proxy model that is smaller and has been trained for fewer epochs, and which can optionally be ensembled. Experiments show promising results, indicating that some datasets can be reduced to half the size without impacting model performance.

summaries: This paper studies a very simple and intuitive method to boost the training speed of deep neural networks. The authors first train some light weighted proxy models, using these models to rank the data according to its uncertainty, and then pick the most uncertain subset to train the final model. Experiments on CIFAR10/SVHN/Amazon Review Polarity demonstrates the effectiveness.

abstractText: At internet scale, applications collect a tremendous amount of data by logging user events, analyzing text, and collecting images. This data powers a variety of machine learning models for tasks such as image classification, language modeling, content recommendation, and advertising. However, training large models over all available data can be computationally expensive, creating a bottleneck in the development of new machine learning models. In this work, we develop a novel approach to efficiently select a subset of training data to achieve faster training with no loss in model predictive performance. In our approach, we first train a small proxy model quickly, which we then use to estimate the utility of individual training data points, and then select the most informative ones for training the large target model. Extensive experiments show that our approach leads to a 1.6× and 1.8× speed-up on CIFAR10 and SVHN by selecting 60% and 50% subsets of the data, while maintaining the predictive performance of the model trained on the entire dataset.

authors:
Guillaume Alain
Alex Lamb
Chinnadhurai Sankar
Aaron Courville
Yoshua Bengio

title: Variance reduction in sgd by distributed importance sampling

venue: arXiv preprint arXiv:1511.06481,

authors:
Zeyuan Allen-Zhu
Zheng Qu
Peter Richtárik
Yang Yuan

title: Even faster accelerated coordinate descent using non-uniform sampling

venue: In International Conference on Machine Learning,

authors:
Dario Amodei
Danny Hernandez. Ai
compute
May

title: URL https://blog

authors:
Zalán Borsos
Andreas Krause
Kfir Y Levy

title: Online variance reduction for stochastic optimization

venue: arXiv preprint arXiv:1802.04715,

authors:
Guillaume Bouchard
Théo Trouillon
Julien Perez
Adrien Gaidon

title: Online learning to sample

venue: arXiv preprint arXiv:1506.09016,

authors:
Trevor Campbell
Tamara Broderick

title: Automated scalable bayesian inference via hilbert coresets

venue: arXiv preprint arXiv:1710.05053,

title: Bayesian coreset construction via greedy iterative geodesic ascent

venue: arXiv preprint arXiv:1802.01737,

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

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

venue: In Advances in Neural Information Processing Systems,

authors:
Alexis Conneau
Holger Schwenk
Loı̈c Barrault
Yann

title: Lecun. Very deep convolutional networks for text classification

venue: arXiv preprint arXiv:1606.01781,

authors:
Alexis Conneau
Holger Schwenk
Loı̈c Barrault
Yann Lecun

title: Very deep convolutional networks for text classification. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pp. 1107–1116

venue: Association for Computational Linguistics,

authors:
Yann N. Dauphin
Angela Fan
Michael Auli
David Grangier

title: Language modeling with gated convolutional networks

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

authors:
Yang Fan
Fei Tian
Tao Qin
Xiang-Yang Li
Tie-Yan Liu

title: Learning to teach

venue: In International Conference on Learning Representations,

title: Adaptive sampling for sgd by exploiting side information

authors:
Alon Halevy
Peter Norvig
Fernando Pereira

title: The unreasonable effectiveness of data

venue: IEEE Intelligent Systems,

authors:
Sariel Har-Peled
Akash Kushal

title: Smaller coresets for k-median and k-means clustering

venue: Discrete & Computational Geometry,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

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

title: Identity mappings in deep residual networks

venue: In European conference on computer vision,

authors:
Ruining He
Julian McAuley

title: Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering

venue: In proceedings of the 25th international conference on world wide web,

authors:
Xiangnan He
Lizi Liao
Hanwang Zhang
Liqiang Nie
Xia Hu
Tat-Seng Chua

title: Neural collaborative filtering

venue: In Proceedings of the 26th International Conference on World Wide Web, pp. 173–182. International World Wide Web Conferences Steering Committee,

authors:
Joel Hestness
Sharan Narang
Newsha Ardalani
Gregory Diamos
Heewoo Jun
Hassan Kianinejad
Md Patwary
Mostofa Ali
Yang Yang
Yanqi Zhou

title: Deep learning scaling is predictable, empirically

venue: arXiv preprint arXiv:1712.00409,

authors:
Gao Huang
Yu Sun
Zhuang Liu
Daniel Sedra
Kilian Q Weinberger

title: Deep networks with stochastic depth

venue: In European Conference on Computer Vision,

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

title: Densely connected convolutional networks

venue: In CVPR,

authors:
Jonathan Huggins
Trevor Campbell
Tamara Broderick

title: Coresets for scalable bayesian logistic regression

authors:
Armand Joulin
Edouard Grave
Piotr Bojanowski
Tomas Mikolov

title: Bag of tricks for efficient text classification

venue: arXiv preprint arXiv:1607.01759,

authors:
Rafal Jozefowicz
Oriol Vinyals
Mike Schuster
Noam Shazeer
Yonghui Wu

title: Exploring the limits of language modeling

venue: arXiv preprint arXiv:1602.02410,

title: Train ai 2018 - building the software 2.0 stack, 2018

venue: URL https://vimeo

authors:
Angelos Katharopoulos
François Fleuret

title: Biased importance sampling for deep neural network training

venue: arXiv preprint arXiv:1706.00043,

title: Not all samples are created equal: Deep learning with importance sampling

venue: arXiv preprint arXiv:1803.00942,

authors:
Tom Kocmi
Ondřej Bojar

title: Curriculum learning and minibatch bucketing in neural machine translation

venue: In Proceedings of the International Conference Recent Advances in Natural Language Processing, RANLP 2017,

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

venue: Technical report, Citeseer,

authors:
David D Lewis
Jason Catlett

title: Heterogeneous uncertainty sampling for supervised learning

venue: In Machine Learning Proceedings

authors:
David D Lewis
William A Gale

title: A sequential algorithm for training text classifiers

venue: In Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval,

authors:
Ilya Loshchilov
Frank Hutter

title: Online batch selection for faster training of neural networks

venue: arXiv preprint arXiv:1511.06343,

authors:
Deanna Needell
Rachel Ward
Nati Srebro

title: Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y Ng

title: Reading digits in natural images with unsupervised feature learning

venue: In NIPS workshop on deep learning and unsupervised feature learning,

authors:
Chongjia Ni
Cheung-Chi Leung
Lei Wang
Nancy F Chen
Bin Ma

title: Unsupervised data selection and word-morph mixed language model for tamil low-resource keyword search

venue: In Acoustics, Speech and Signal Processing (ICASSP),

authors:
Roi Reichart
Katrin Tomanek
Udo Hahn
Ari Rappoport

title: Multi-task active learning for linguistic annotations

venue: In Proceedings of ACL-08: HLT,

authors:
Ozan Sener
Silvio Savarese

title: Active learning for convolutional neural networks: A core-set approach

title: From theories to queries: Active learning in practice

venue: Proceedings of Machine Learning Research,

title: Active learning

venue: Synthesis Lectures on Artificial Intelligence and Machine Learning,

authors:
Chen Sun
Abhinav Shrivastava
Saurabh Singh
Abhinav Gupta

title: Revisiting unreasonable effectiveness of data in deep learning era

venue: In Computer Vision (ICCV),

authors:
Katrin Tomanek
Joachim Wermter
Udo Hahn

title: An approach to text corpus construction which cuts annotation costs and maintains reusability of annotated data

venue: In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL),

authors:
Ivor W Tsang
James T Kwok
Pak-Ming Cheung

title: Core vector machines: Fast svm training on very large data sets

venue: Journal of Machine Learning Research,

authors:
Sebastian Tschiatschek
Rishabh K Iyer
Haochen Wei
Jeff A Bilmes

title: Learning mixtures of submodular functions for image collection summarization

authors:
Marlies van der Wees
Arianna Bisazza
Christof Monz

title: Dynamic data selection for neural machine translation

venue: In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Rui Wang
Masao Utiyama
Eiichiro Sumita

title: Dynamic sentence sampling for efficient training of neural machine translation

venue: arXiv preprint arXiv:1805.00178,

authors:
Tianyang Wang
Jun Huan
Bo Li

title: Data dropout: Optimizing training data for convolutional neural networks

venue: arXiv preprint arXiv:1809.00193,

authors:
Kai Wei
Yuzong Liu
Katrin Kirchhoff
Jeff Bilmes

title: Using document summarization techniques for speech data subset selection

venue: In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,

authors:
Kai Wei
Yuzong Liu
Katrin Kirchhoff
Chris Bartels
Jeff Bilmes

title: Submodular subset selection for large-scale speech training data

authors:
Saining Xie
Ross Girshick
Piotr Dollár
Zhuowen Tu
Kaiming He

title: Aggregated residual transformations for deep neural networks

venue: In Computer Vision and Pattern Recognition (CVPR),

authors:
Dakun Zhang
Jungi Kim
Josep Crego
Jean Senellart

title: Boosting neural machine translation

venue: In Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 2: Short Papers),

authors:
Xiang Zhang
Junbo Zhao
Yann LeCun

title: Character-level convolutional networks for text classification

authors:
Peilin Zhao
Tong Zhang

title: Stochastic optimization with importance sampling for regularized loss minimization

venue: In international conference on machine learning,

heading: 1 INTRODUCTION

text:
Large-scale labeled data has been critical to the recent success of deep learning (Halevy et al., 2009; Sun et al., 2017; Hestness et al., 2017) and there are a variety of domains and settings where labeled data is plentiful, such as predicting the next word or character in language modeling and predicting user-provided image tags for image classification. However, for these large datasets, training deep networks can incur prohibitively long training times, measured in days, weeks, or even months (Sun et al., 2017). This overhead impedes the development of new machine learning models and uses large amounts of computational resources (Amodei & Hernandez, 2018).
Subsampling training data is a common solution to this problem, but naive, uniform subsampling can miss important rare examples. For instance, in many web applications, data is abundant for a small subset of core users/content but is scarce for new users/content. Similarly, when training autonomous vehicles, yellow lights occur less frequently than green and red lights but are equally important (Karpathy, 2018). While more sophisticated methods such as core-set selection techniques can select a representative subset, these methods are either algorithm-specific (Har-Peled & Kushal, 2007; Tsang et al., 2005; Huggins et al., 2016; Campbell & Broderick, 2017; 2018) and don’t apply to deep learning, or require a meaningful feature representation (Wei et al., 2013; 2014; Tschiatschek et al., 2014; Ni et al., 2015) that must either be hand-designed or learned for unstructured data, which requires substantial computational resources.
In this paper, we introduce a new method called Select Via Proxy (SVP) that provides a computationally efficient way of training large deep learning models while empirically maintaining model quality/performance. Our key idea is to quickly select a subset of the most informative data and then train a large model on this subset. Training with less data leads to faster training times, while training on the most informative data allows the model to learn as well as if it were trained on the full data. To identify informative data points we first quickly train a small proxy model, and then use this proxy to select data for training the large full model. The proxy model is a simple and fast-to-train model—for example, a small model architecture (e.g., ResNet20 instead of ResNet164) trained for a few epochs (e.g., 25% of the desired epochs). We subsequently select a training set for the larger model based on the predictions generated by this smaller proxy model. This selection process can be thought of as a preprocessing step that filters data before feeding it into an existing training pipeline,
as depicted in Figure 1. To select the points with highest informativeness, we leverage uncertainty sampling (Lewis & Gale, 1994) from active learning, where uncertainty can be measured by metrics such as entropy of the output probabilities. However, in active learning a model is generally trained to select the next point (or batch) (Settles, 2012), which is efficient in terms of labels, but often computationally expensive. While this can be effective when deciding which data to acquire labels for from an expensive labeler (e.g. a human), the computational cost is too high to accelerate training over an existing large labeled dataset. Using a proxy reduces the cost of selection by up to a 100×. The main benefits of our proposed method are (i) it can be easily added to a training pipeline without modifying the training procedure of the target model and (ii) the proxy is very fast to train and can substantially improve the training time of large deep models while maintaining the predictive performance. Extensive experimental evaluation shows the effectiveness of our approach. In general, the proxy is very fast to train. As a result, including the time to train the proxy, select points using the trained proxy, and train the large target model on the selected points, we find that SVP can substantially reduce training time compared to training over all the data while maintaining the same predictive performance. SVP leads to a 1.6× and 1.8× speed-up on CIFAR10 (Krizhevsky & Hinton, 2009) and SVHN (Netzer et al., 2011) by selecting 60% and 50% subsets of the data respectively while maintaining predictive performance. To explore the robustness of our proposed framework to the choice of proxy model architecture, we combine two approaches for sentiment analysis that represent separate extremes in speed and accuracy. Our experiments show that SVP with fastText (Joulin et al., 2016) as a proxy model can be used to remove 20% of the data from Amazon Review Polarity (Zhang et al., 2015; He & McAuley, 2016) for the target model VDCNN29 (Conneau et al., 2017), a fundamentally different architecture from the proxy that is over 100× slower to train (e.g., 17 hours instead of 10 minutes). This provides a simple but effective means of decreasing training time without increasing error.

heading: 2 RELATED WORK

text:
SVP builds upon a large body of related work on sampling and training data selection.
Core-set selection. Core-set selection attempts to find a representative subset of points to speed up learning or clustering; such as k-means and k-medians (Har-Peled & Kushal, 2007), SVM (Tsang et al., 2005), Bayesian logistic regression (Huggins et al., 2016), and Bayesian inference (Campbell & Broderick, 2017; 2018). However, these examples are algorithm-specific and do not directly apply to deep neural networks. Very recently, Sener & Savarese (2018) used core-set selection for active learning with convolutional neural networks. While this technique reduces sample complexity, the proposed technique is computationally intensive and does not save on training time. There is a body of work on data summarization based on submodular maximization (Wei et al., 2013; 2014; Tschiatschek et al., 2014; Ni et al., 2015). However, the techniques here are rather different as they do not incorporate a model prediction.
Subset selection to increase accuracy. Recently, Chang et al. (2017) proposed to choose data points whose predictions have changed most over the previous epochs as a lightweight estimate of uncertainty. From the machine teaching literature, Fan et al. (2018) demonstrated that data selection can be learned through reinforcement learning. By repeatedly training a student model over the
dataset or similar dataset, they train a teacher model to filter points for each update of the student model using the student’s final accuracy and training time as a reward. In comparison to our method, both of these approaches have substantial burn in periods (i.e., building a history of predictions or training the teacher) before data can be effectively selected.
In addition, Wang et al. (2018b) trains a model, selects a subset, and then retrains the same model on a subset of the data where a small fraction of unfavorable training examples (< 5%) are removed to give higher accuracy. The goal of the above work is to increase the accuracy of training rather than speed up training. However, these results make it less surprising that we can achieve the same accuracy with a subset of the full dataset even though we are able to remove up to 12× more points. Heterogeneous active learning. In the active learning literature, there are examples of using one model to select points for a different, more expensive model. For instance, (Lewis & Catlett, 1994) uses a probabilistic classifier to select points to label for a decision tree target model. Tomanek et al. (2007) uses a committee-based active learning algorithm for an NLP task and notes that the set of selected points are “reusable” across different models (maximum entropy, conditional random field, naive Bayes). In light of this work, we demonstrate this phenomena generalizes to modern deep learning models where model capacity and training time can be substantially reduced to effectively select informative examples.
Optimization and Importance Sampling. There is a large literature on weighting or sampling datapoints in the optimization procedure in order to speed up training or achieve higher accuracy. The most common paradigm is to perform importance sampling on training data points based on the gradient norm (Alain et al., 2015), loss (Loshchilov & Hutter, 2015), bound on the gradient norm (Katharopoulos & Fleuret, 2017), or approximate loss (Katharopoulos & Fleuret, 2018). There has also been work on learning the weights or sampling probabilities to minimize the variance of the stochastic gradient (Bouchard et al., 2015; Borsos et al., 2018; Gopal, 2016). In the theoretical optimization literature, there is work on importance sampling data points for faster convergence (Needell et al., 2014; Zhao & Zhang, 2015; Allen-Zhu et al., 2016). There has also been a line of work in the Neural Machine Translation literature focused on reducing training time by focusing more on “hard” examples in later epochs (Zhang et al., 2017; van der Wees et al., 2017; Wang et al., 2018a; Kocmi & Bojar, 2017). In comparison, our approach does not modify the training procedure of the target model, making it an easy addition to an existing training pipeline.
We note that our proposed method is orthogonal to the above. SVP could be used in conjunction with the algorithms above to further decrease training time or reduce computational complexity in the case of active learning and core-set selection, but we leave this for future work.

heading: 3 SELECT VIA PROXY

text: We now present our main contribution, Select via Proxy (SVP), for efficiently training expensive deep learning models. Our approach consists of three steps: 1) Create a proxy model that is fast to train and to provide us with an approximate decision boundary, 2) use the proxy model to select a subset of uncertain data points around the decision boundary, and 3) train the large target model on the selected subset via proxy to refine the decision boundary and get the final accurate model. In the following section, we discuss each step in detail.

heading: 3.1 CREATING A PROXY MODEL

text:
The key idea behind the proxy model is to create a small model that is fast to train and can provide a good approximation of the decision boundary of the large target model. In order to create such a model we rely on the following observations.
Creating a proxy by scaling down the target model. It has been observed that for deep models with many layers, reducing the dimension (narrowing) or number of hidden layers (shortening) leads to a considerably reduced training times with only a small drop in accuracy. For example, in image classification, the accuracy of deep networks with residual connections (e.g., ResNet164 and ResNet110) only slightly diminishes as layers are dropped from the network (He et al., 2016b;a). As Figure 2a shows, a model with 20 layers achieves an accuracy of 92.1% in 22 minutes, while a
larger model with 164 layers only improves performance by 2.4%, but takes 3 hours and 40 minutes to train.
Similar results have been shown for scaling down networks with a variety of model architectures (Huang et al., 2016; Xie et al., 2017; Huang et al., 2017) and a number of other tasks including language modeling, neural machine translation, text classification, and recommendation (Conneau et al., 2016; He et al., 2017; Jozefowicz et al., 2016; Dauphin et al., 2017; Vaswani et al., 2017). We exploit the diminishing returns property between training time and reductions in error to scale down a given target model to a small proxy that can be trained quickly but still provides a good approximation of the decision boundary of the target model.
Training for a smaller number of epochs. As shown in Figure 2b, a significant amount of training is spent to obtain a relatively small reduction in error. While training ResNet20, almost half of the training time (i.e., 10 minutes out of 22 minutes) is spent on a 1.3% improvement in error. Based on the above observation, we can train the proxy model for a smaller number of epochs and still get a good approximation from the decision boundary of the target model.
Boosting the performance by ensembling small models. Boosting is a common approach to get a strong learner by ensembling a set of weak learners. Similarly, a stronger proxy can be obtained by training a set of small models and combining their predictions. The stronger proxy can provide a better approximation from the decision boundary of the target model. Considering that the much smaller size of the proxy model compared to the size of the target model, multiple proxy models can be trained with little or no additional resources in parallel, with no increase to overall training time. Each learner within the ensemble has its own noisy approximation of the decision boundary. Hence, the small learners can be combined together through alternating selection or rank combination (Settles, 2011; Reichart et al., 2008). Figure 3 shows that ensembling improves the already high correlation between the proxy model’s ranking of points based on entropy and the same ranking produced by the model trained on the whole data.

heading: 3.2 SUBSET SELECTION VIA PROXY

text:
Having trained the small proxy model on the entire dataset, we can use its predictions to select informative subsets to train the large target model. As discussed in Section 3.1, the proxy model provides an approximation from the decision boundary between different classes. Considering that the large target model is able to learn a more refined decision boundary, we use the proxy model to select the most uncertain data points around the decision boundary (Lewis & Gale, 1994; Lewis & Catlett, 1994) and subsequently train the target model on the uncertain subsets.
Quantifying uncertainty. Various uncertainty metrics can be used, including confidence, margin, and entropy (Settles, 2012). For a classifier that for every data point x provides the probability
Algorithm 1 SELECT VIA PROXY (SVP) Input: Data set D, cardinality k, deep model architectureM. Output: Trained deep modelMt.
1: Create a proxy model by scaling down the target model as described in section 3.1. 2: Train the small proxy model on the entire dataset D. 3: Calculate uncertainty of data points via the proxy model using uncertainty metrics from sec-
tion 3.2. 4: Sort the examples in a decreasing order based on their uncertainty. 5: Train the target model M on the subset S of top k uncertain examples to get the final output Mt. 6: returnMt.
P (y|x) for x to belong to class y, the uncertainty function f can be defined as follow. fconfidence(x) = 1− P (ŷ|x) (1)
fmargin(x) = 1−min y 6=ŷ (P (ŷ|x)− P (y|x)) (2) fentropy(x) = − ∑ y P (y|x) logP (y|x), (3)
where ŷ = argmaxy P (y|x) is the most probable label for data point x. For all the above metrics, a value of 0 means no uncertainty and higher values mean more uncertainty. In general, we usually care about the ordering of data points by each uncertainty measure and not the uncertainty values. Note that for binary labels, the ordering between these three metrics are equivalent. The set of most uncertain k points in dataset D, i.e. S = argmaxA⊆D:|A|≤k ∑ i f(xi) can then be obtained by sorting the data points according to each uncertainty metric, and taking the top k uncertain points in the sorted order.
Training the target model on the subsets selected via proxy. Finally, the set of uncertain data points can be used to train the large target model. Here, the idea is to refine the decision boundary learned by the proxy model. Since the target model is able to learn a more complex decision boundary, we select the data points around the approximate decision boundary learned by the proxy and let the target model refine the decision boundary of the proxy model. The Pseudocode of the proposed method is outlined in Alg. 1.
Choosing subset cardinality. While our algorithm assumes the subset size is given, we describe two important use cases where this is a reasonable assumption. First, for large-scale applications where data is constantly collected based on user interactions, models are often re-trained periodically on the most recent data. In this case, the target model class is known, and the subset size can be determined once from historical data. Second, the dataset is too large to train on, forcing the data to
be subsampled to a fixed size to meet a computational or time budget. In this case, the subset size is known, and a new proxy can be created for each target. As demonstrated in section 4, in most cases, our method performs better than random for a fixed subset size with little additional overhead.
We note that while we discussed different steps in Section 3.1 to create the proxy model, and explored various uncertainty measures in Section 3.2 to select data points via proxy, our method is robust to a wide range of model architectures, training routines, and metrics for creating the proxy and selecting data from it. In section 4, we demonstrate this robustness concretely through a series of experiments examining our choice of proxy model relative to a given target model.

heading: 4 RESULTS

text:
To investigate the performance of SVP (Alg. 1), we perform experiments on three datasets: CIFAR10 (Krizhevsky & Hinton, 2009), SVHN (Netzer et al., 2011) and Amazon Review Polarity (Zhang et al., 2015; He & McAuley, 2016). We first evaluate the ability of a small ResNet model (He et al., 2016a;b) to select a subset of points for much larger ResNet model on CIFAR10 and SVHN datasets, which have 50,000 and 604,388 training examples respectively. Using the small proxy model is both fast and accurate enough to select 50% and 60% subsets of SVHN and CIFAR10 while speeding up end-to-end wall-clock time by 1.8× and 1.6× respectively. We further demonstrate SVP’s robustness by showing that it outperforms uniform subsampling for a variety of proxy models and metrics. Additionally, we provide an extreme example of this robustness using fastText (Joulin et al., 2016) as a proxy model for VDCNN29 (Conneau et al., 2017) on the Amazon Review Polarity dataset, which has 3,600,000 training examples. fastText is a fundamentally different architecture than VDCNN29 and over 100× faster to train (e.g., 10 minutes instead of 17 hours), yet SVP can remove 20% of the data while maintaining VDCNN29’s lower error.
Here, we compare the performance of SVP with uniform subsampling, as the other methods discussed in Section 2 require changes to the optimization procedure, and our method can be applied as a preprocessing step to improve their training time. We further note that core-set selection and class balancing techniques do not apply here as we do not have pre-designed features and the datasets are relatively balanced.
Implementation details. In our experiments, we first train the large target model on the full dataset for nt epochs and use it as the baseline. We then train the proxy model on the entire dataset for a smaller number np ≤ nt of epochs (as specified in Table 1). The trained proxy model is then used to select subsets of uncertain points to train the target model for the same nt number of epochs. Throughout this paper we report the mean error and standard deviation of 3 runs for each combination of proxy, target, and subset size, reducing the impact of random variations. For task specific hyperparameters, please see section 6.1.
Wall-clock time. To demonstrate the efficiency of SVP, we compare the wall-clock training time of selection via proxy to training over the full dataset with the target in Figure 4. For CIFAR10, we are able to maintain the same predictive performance as training over the entire dataset with 60% of the data, leading to an average speed-up of 1.6× over 3 runs. In more detail, we use an ensemble of 3 ResNet20 models, where each model is taken based on the best validation error after 50 epochs of training, and rank examples based on their entropy. The rankings from each individual model are combined through rank combination, where the new rank for each example is the sum of its rank from each ResNet20 model. With this new ranking, we take the top 60% of examples and train ResNet164 with preactivation from scratch for a full 181 epochs as in He et al. (2016b). The slowest ResNet20 model takes 6 minutes and 20 seconds to train, which is less than 1/30 of the original training time for ResNet164. However, using the ranking from this small proxy model, we are able to remove 40% of the data and make up for the increase in overhead as demonstrated in Figure 4a.
Similarly, for SVHN, we are able to maintain the same predictive performance as training over the entire dataset with 50% of the data, leading to an average speed-up of 1.8×. Unlike CIFAR10, ensembling does not improve or harm data selection, so we rank points based on loss from only a single ResNet20 model after 10 epochs of training, which takes an average of 13 minutes and 4 seconds on a Titan V GPU. Using this ranking, we eliminate 50% of the examples and train ResNet152 on the remaining images for a full 50 epochs as in Huang et al. (2016). Including the time to train the proxy and make the selection, training ResNet152 to the same error level takes 2
hours and 50 minutes rather than 5 hours and 5 minutes when training over all of the data as shown in Figure 4b.
For Amazon Review Polarity, we are able to maintain the same predictive performance with VDCNN29 as training over the entire dataset while removing 20% of the dataset using fastText as a proxy as shown in Table 1. In comparison to VDCNN29, which takes 16 hours and 40 minutes to train over the entire dataset on a Titan V GPU, fastText two orders of magnitude faster, taking less than 10 minutes on a laptop to train over the same data and compute output probabilities. This allows us to train VDCNN29 to the same error level in 13 hours and 30 minutes.
Comparing different proxies. Table 1 shows the impact of ensembling, partial training, and model architecture on selecting data from a proxy. Ensembling and partial training both improve performance, allowing a subset of 60% of the data to maintain the same predictive performance as the full dataset on CIFAR10. For ensembling, rank combination outperformed alternating selection (i.e., taking the most uncertain points from each model in a robin-round fashion). Without either ensembling or partial training, selection with ResNet20 degrades and requires 70% to 80% of the data instead. Surprisingly, using a fully trained ResNet164 with pre-activation performs worse than using ResNet20 with pre-activation to select examples for a separate ResNet164 with pre-activation. The favorable performance of smaller architectures and partial training might be a result of increased randomness and better coverage of the entire datasets.
Comparing uncertainty metrics. We experimented with various ways to quantify uncertainty and select points. Figure 5 shows the impact of different uncertainty metrics for a pair of proxy and target model. For both CIFAR10 and SVHN, all of the metrics performed similarly. While the metrics had a more variance on SVHN than CIFAR10 as shown in Figure 5b, this is mostly due to the variability between runs of the proxy model than the metrics. Unlike the Pearson correlation between models as shown in Figure 3, the correlation between metrics of the same model is always above 0.96.
Class imbalance. To understand which examples were being selected, we looked at the class distribution for multiple runs of ResNet20 with pre-activation on CIFAR10 at different subset sizes and points during training as shown in Table 2. Very small subsets had high class imbalance, but as training continues or the subset size increases the class distribution becomes more balanced. We hypothesized that forcing the selected subset to be more balanced would improve performance and reduce the size of the subset needed to maintain predictive performance, but we found that balancing the subset by selecting the most uncertain example from each class in a round-robin fashion actually harmed performance slightly.

heading: 5 CONCLUSION

text: In this work, we present Select Via Proxy (SVP), a novel approach to efficiently select a subset of training data to achieve faster training of deep learning models with no loss in predictive performance. Using this approach, we demonstrate that a small proxy model that is more than 30× faster to train can select a subset of data to train a large architecture, while maintaining the predictive performance. On CIFAR10 and SVHN, the speed of training the proxy model leads to a 1.6× and 1.8× speed-up in end-to-end training time by selecting 60% and 50% of data respectively to train the target model on. Aside from filtering input examples, we do not change the training procedure of the target model, making our method a modular component to add to existing training pipelines.

heading: 6 APPENDIX

heading: 6.1 HYPERPARAMETERS

text:
CIFAR10. We used ResNet164 with pre-activation from He et al. (2016b) as our large target model. Based on the trade-off between training time and error in Figure 2a, we chose ResNet20 with preactivation as the proxy architecture, where the filters and layers were scaled down to match He et al. (2016a). To avoid extensive hyperparameter search, we followed the same training procedure, initialization, and hyperparameter as He et al. (2016b) with the exception of weight decay, which was set to 0.0005 and decreased the model’s error under all conditions.
SVHN. We used ResNet152 and ResNet20 from He et al. (2016a) as the large target model and the small proxy model respectively. We followed the same training procedure, initialization, and hyperparameters from Huang et al. (2016).
Amazon Review Polarity. we used fastText as the proxy model and VDCNN29 as the target model and followed the same training procedure, initialization, and hyperparameters from Joulin et al. (2016) for fastText and from Conneau et al. (2017) for VDCNN29.


summaries: This paper proposes a sequential Monte Carlo Planning algorithm that depicts planning as an inference problem solved by SMC. The problem is interesting and the paper has a nice description of the related work. In terms of the connection between the the problem and Bayesian filtering as well as smoothing, the paper has novelty there. But it is unclear to me how the algorithm proposed is applicable in complex continuous tasks as claimed.

summaries: Sequential Monte Carlo (SMC) has since its inception some 25 years ago proved to be a powerful and generally applicable tool. The authors of this paper continue this development in a very interesting and natural way by showing how SMC can be used to solve challenging planning problems. This is a enabled by reformulating the planning problem as an inference problem via the recent trend referred to as "control as inference". While there is unfortunately no real world experiments, the simulations clearly illustrate the potential of the approach.

abstractText: In this work, we propose a novel formulation of planning which views it as a probabilistic inference problem over future optimal trajectories. This enables us to use sampling methods, and thus, tackle planning in continuous domains using a fixed computational budget. We design a new algorithm, Sequential Monte Carlo Planning, by leveraging classical methods in Sequential Monte Carlo and Bayesian smoothing in the context of control as inference. Furthermore, we show that Sequential Monte Carlo Planning can capture multimodal policies and can quickly learn continuous control tasks.

authors:
Abbas Abdolmaleki
Jost Tobias Springenberg
Yuval Tassa
Remi Munos
Nicolas Heess
Martin Riedmiller

title: Maximum a posteriori policy optimisation

venue: arXiv preprint arXiv:1806.06920,

authors:
Christophe Andrieu
Arnaud Doucet
Sumeetpal S Singh
Vladislav B Tadic

title: Particle methods for change detection, system identification, and control

venue: Proceedings of the IEEE,

title: Planning by probabilistic inference

venue: In AISTATS. Citeseer,

authors:
Matthew Botvinick
Marc Toussaint

title: Planning as inference

venue: Trends in cognitive sciences,

title: Two-filter formulae for discrete-time non-linear bayesian smoothing

venue: International Journal of Control,

authors:
Jacob Buckman
Danijar Hafner
George Tucker
Eugene Brevdo
Honglak Lee

title: Sample-efficient reinforcement learning with stochastic ensemble value expansion

venue: arXiv preprint arXiv:1807.01675,

authors:
Lars Buesing
Theophane Weber
Sébastien Racanière
S.M. Ali Eslami
Danilo Jimenez Rezende
David P. Reichert
Fabio Viola
Frederic Besse
Karol Gregor
Demis Hassabis
Daan Wierstra

title: Learning and querying fast generative models for reinforcement learning

authors:
Kurtland Chua
Roberto Calandra
Rowan McAllister
Sergey Levine

title: Deep reinforcement learning in a handful of trials using probabilistic dynamics models

venue: arXiv preprint arXiv:1805.12114,

authors:
Cédric Colas
Olivier Sigaud
Pierre-Yves Oudeyer

title: How many random seeds? statistical power analysis in deep reinforcement learning experiments

venue: arXiv preprint arXiv:1806.08295,

authors:
Peter Dayan
Geoffrey E Hinton

title: Using expectation-maximization for reinforcement learning

venue: Neural Computation,

authors:
Chelsea Finn
Sergey Levine

title: Deep visual foresight for planning robot motion

venue: In Robotics and Automation (ICRA),

authors:
Ian Goodfellow
Jean Pouget-Abadie
Mehdi Mirza
Bing Xu
David Warde-Farley
Sherjil Ozair
Aaron Courville
Yoshua Bengio

title: Generative adversarial nets

venue: In Advances in neural information processing systems,

authors:
Neil J Gordon
David J Salmond
Adrian FM Smith

title: Novel approach to nonlinear/non-gaussian bayesian state estimation

venue: In IEE Proceedings F-radar and signal processing,

authors:
Shixiang Gu
Zoubin Ghahramani
Richard E Turner

title: Neural adaptive sequential monte carlo

venue: In Advances in Neural Information Processing Systems,

authors:
Arthur Guez
Théophane Weber
Ioannis Antonoglou
Karen Simonyan
Oriol Vinyals
Daan Wierstra
Rémi Munos
David Silver

title: Learning to search with mctsnets

venue: arXiv preprint arXiv:1802.04697,

authors:
Tuomas Haarnoja
Aurick Zhou
Pieter Abbeel
Sergey Levine

title: Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor

venue: arXiv preprint arXiv:1801.01290,

authors:
Peter Henderson
Riashat Islam
Philip Bachman
Joelle Pineau
Doina Precup
David Meger

title: Deep reinforcement learning that matters

venue: arXiv preprint arXiv:1709.06560,

authors:
Sepp Hochreiter
Jürgen Schmidhuber

title: Long short-term memory

venue: Neural computation,

title: When is a linear control system optimal

venue: Journal of Basic Engineering,

title: Contributions to the theory of optimal control

venue: Bol. Soc. Mat. Mexicana,

authors:
Nikolas Kantas
JM Maciejowski
A Lecchini-Visintini

title: Sequential monte carlo for model predictive control

venue: In Nonlinear Model Predictive Control,

authors:
Michael Kearns
Yishay Mansour
Andrew Y Ng

title: A sparse sampling algorithm for near-optimal planning in large markov decision processes

venue: Machine learning,

authors:
Diederik P Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization

venue: arXiv preprint arXiv:1412.6980,

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: arXiv preprint arXiv:1312.6114,

title: The two-filter formula for smoothing and an implementation of the gaussian-sum smoother

venue: Annals of the Institute of Statistical Mathematics,

title: Monte carlo filter and smoother for non-gaussian nonlinear state space models

venue: Journal of computational and graphical statistics,

authors:
Thanard Kurutach
Aviv Tamar
Ge Yang
Stuart Russell
Pieter Abbeel

title: Learning plannable representations with causal infogan

venue: arXiv preprint arXiv:1807.09341,

authors:
Tuan Anh Le
Maximilian Igl
Tom Rainforth
Tom Jin
Frank Wood

title: Auto-encoding sequential monte carlo

venue: arXiv preprint arXiv:1705.10306,

title: Reinforcement learning and control as probabilistic inference: Tutorial and review

venue: arXiv preprint arXiv:1805.00909,

authors:
Sergey Levine
Vladlen Koltun

title: Variational policy search via trajectory optimization

authors:
Fredrik Lindsten
Michael I Jordan
Thomas B Schön

title: Particle gibbs with ancestor sampling

venue: The Journal of Machine Learning Research,

authors:
Chris J Maddison
Dieterich Lawson
George Tucker
Nicolas Heess
Arnaud Doucet
Andriy Mnih
Yee Whye Teh

title: Particle value functions

venue: arXiv preprint arXiv:1703.05820,

authors:
Chris J Maddison
John Lawson
George Tucker
Nicolas Heess
Mohammad Norouzi
Andriy Mnih
Arnaud Doucet
Yee Teh

title: Filtering variational objectives

authors:
Ofir Nachum
Mohammad Norouzi
Kelvin Xu
Dale Schuurmans

title: Bridging the gap between value and policy based reinforcement learning

authors:
Christian A Naesseth
Scott W Linderman
Rajesh Ranganath
David M Blei

title: Variational sequential monte carlo

venue: arXiv preprint arXiv:1705.11140,

authors:
Anusha Nagabandi
Gregory Kahn
Ronald S Fearing
Sergey Levine

title: Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning

venue: arXiv preprint arXiv:1708.02596,

authors:
Brendan O’Donoghue
Remi Munos
Koray Kavukcuoglu
Volodymyr Mnih

title: Combining policy gradient and q-learning

venue: arXiv preprint arXiv:1611.01626,

authors:
Michael K Pitt
Neil Shephard

title: Filtering via simulation: Auxiliary particle filters

venue: Journal of the American statistical association,

authors:
Konrad Rawlik
Marc Toussaint
Sethu Vijayakumar

title: An approximate inference approach to temporal optimization in optimal control. In Advances in neural information processing

title: On stochastic optimal control and reinforcement learning by approximate inference

venue: In Robotics: science and systems,

authors:
RY Rubinstein
DP Kroese

title: A unified approach to combinatorial optimization, monte-carlo simulation, and machine learning

authors:
John Schulman
Xi Chen
Pieter Abbeel

title: Equivalence between policy gradients and soft q-learning

venue: arXiv preprint arXiv:1704.06440,

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

title: Mastering the game of go without human knowledge

authors:
Alec Solway
Matthew M Botvinick

title: Goal-directed decision making as probabilistic inference: a computational framework and potential neural correlates

venue: Psychological review,

authors:
Leland Stewart
Perry McCarty

title: Use of bayesian belief networks to fuse continuous and discrete information for target recognition, tracking, and situation assessment

venue: In Signal Processing, Sensor Fusion, and Target Recognition,

authors:
István Szita
András Lörincz

title: Learning tetris using the noisy cross-entropy method

authors:
Yuval Tassa
Tom Erez
Emanuel Todorov

title: Synthesis and stabilization of complex behaviors through online trajectory optimization

venue: In Intelligent Robots and Systems (IROS),

authors:
Emanuel Todorov
Weiwei Li

title: A generalized iterative lqg method for locally-optimal feedback control of constrained nonlinear stochastic systems

venue: In American Control Conference,

authors:
Emanuel Todorov
Tom Erez
Yuval Tassa

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

title: Robot trajectory optimization using approximate inference

venue: In Proceedings of the 26th annual international conference on machine learning,

authors:
Marc Toussaint
Christian Goerick

title: Probabilistic inference for structured planning in robotics

venue: In Intelligent Robots and Systems,

authors:
Marc Toussaint
Amos Storkey

title: Probabilistic inference for solving discrete and continuous state markov decision processes

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

authors:
Théophane Weber
Sébastien Racanière
David P Reichert
Lars Buesing
Arthur Guez
Danilo Jimenez Rezende
Adria Puigdomènech Badia
Oriol Vinyals
Nicolas Heess
Yujia Li

title: Imagination-augmented agents for deep reinforcement learning

venue: arXiv preprint arXiv:1707.06203,

title: Modeling purposeful adaptive behavior with the principle of maximum causal entropy

heading: 1 INTRODUCTION

text:
To exhibit intelligent behaviour machine learning agents must be able to learn quickly, predict the consequences of their actions, and explain how they will react in a given situation. These abilities are best achieved when the agent efficiently uses a model of the world to plan future actions. To date, planning algorithms have yielded very impressive results. For instance, Alpha Go (Silver et al., 2017) relied on Monte Carlo Tree Search (MCTS) (Kearns et al., 2002) to achieve super human performances. Cross entropy methods (CEM) (Rubinstein & Kroese, 2004) have enabled robots to perform complex nonprehensile manipulations (Finn & Levine, 2017) and algorithms to play successfully Tetris (Szita & Lörincz, 2006). In addition, iterative linear quadratic regulator (iLQR) (Kalman et al., 1960; Kalman, 1964; Todorov & Li, 2005) enabled humanoid robots tasks to get up from an arbitrary seated pose (Tassa et al., 2012).
Despite these successes, these algorithms make strong underlying assumptions about the environment. First, MCTS requires a discrete setting, limiting most of its successes to discrete games with known dynamics. Second, CEM assumes the distribution over future trajectories to be Gaussian, i.e. unimodal. Third, iLQR assumes that the dynamics are locally linear-Gaussian, which is a strong assumption on the dynamics and would also assume the distribution over future optimal trajectories to be Gaussian. For these reasons, planning remains an open problem in environments with continuous actions and complex dynamics. In this paper, we address the limitations of the aforementioned planning algorithms by creating a more general view of planning that can leverage advances in deep learning (DL) and probabilistic inference methods. This allows us to approximate arbitrary complicated distributions over trajectories with non-linear dynamics.
We frame planning as density estimation problem over optimal future trajectories in the context of control as inference (Dayan & Hinton, 1997; Toussaint & Storkey, 2006; Toussaint, 2009; Rawlik et al., 2010; 2012; Ziebart, 2010; Levine & Koltun, 2013). This perspective allows us to make use of tools from the inference research community and, as previously mentioned, model any distribution over future trajectories. The planning distribution is complex since trajectories consist of an intertwined sequence of states and actions. Sequential Monte Carlo (SMC) (Stewart & McCarty, 1992; Gordon et al., 1993; Kitagawa, 1996) methods are flexible and efficient to model such a
∗both authors contributed equally.
distribution by sequentially drawing from a simpler proposal distribution. From the SMC perspective, the policy can be seen as the proposal and a learned model of the world as the propagation distribution. This provides a natural way to combine model-free and model-based RL.
Contribution. We depict the problem of planning as one of density estimation that can be estimated using SMC methods. We introduce a novel planning strategy based on the SMC class of algorithms, in which we treat the policy as the proposed distribution to be learned. We investigate how our method empirically compares with existing model-based methods and a strong model-free baseline on the standard benchmark Mujoco (Todorov et al., 2012).

heading: 2 BACKGROUND

heading: 2.1 CONTROL AS INFERENCE

text:
We consider the general case of a Markov Decision Process (MDP) {S,A, penv, r, γ, µ} where S and A represent the state and action spaces respectively. We use the letters s and a to denote states and actions, which we consider to be continuous vectors. Further notations include: penv(s′|s,a) as the state transition probability of the environment, r(s,a) as the reward function, and γ ∈ [0, 1) as the discount factor. µ denotes the probability distribution over initial states.
This work focuses on an episodic formulation, with a fixed end-time of T . We define a trajectory as a sequence of state-action pairs xt:T = {(st,at), . . . , (sT ,aT )}, and we use the notation π for a policy which represents a distribution over actions conditioned on a state. Here π is parametrized by a neural network with parameters θ. The notation qθ(x1:T ) = µ(s1) ∏T−1 t≥1 penv(st+1|st,at) ∏T t≥1 πθ(at|st) denotes the probability of a trajectory x1:T under policy πθ.
Traditionally, in reinforcement learning (RL) problems, the goal is to find the optimal policy that maximizes the expected return Eqθ [ ∑T t=1 γ
trt]. However, it is useful to frame RL as an inference problem within a probabilistic graphical framework (Rawlik et al., 2012; Toussaint & Storkey, 2006; Levine, 2018). First, we introduce an auxiliary binary random variable Ot denoting the “optimality“ of a pair (st,at) at time t and define its probability1 as p(Ot = 1|st,at) = exp(r(st,at)). O is a convenience variable only here for the sake of modeling. By considering the variables (st,at) as latent and Ot as observed, we can construct a Hidden Markov Model (HMM) as depicted in figure 2.1. Notice that the link s→ a is not
present in figure 2.1 as the dependency of the optimal action on the state depends on the future observations. In this graphical model, the optimal policy is expressed as p(at|st,Ot:T ). The posterior probability of this graphical model can be written as2:
p(x1:T |O1:T ) ∝ p(x1:T ,O1:T ) = µ(s1) T−1∏ t=1 penv(st+1|at, st) exp ( T∑ t=1 r(st,at) + log p(at) ) .
(2.1)
It appears clearly that finding optimal trajectories is equivalent to finding plausible trajectories yielding a high return.
1as in Levine (2018), if the rewards are bounded above, we can always remove a constant so that the probability is well defined.
2Notice that in the rest of the paper, we will abusively remove the product of the action priors ∏T
t=1 p(at) = exp (∑T t=1 log p(at) )
from the joint as in Levine (2018). We typically consider this term either constant or already included in the reward function. See Appendix A.2 for details.
Many control as inference methods can be seen as approximating the density by optimizing its variational lower bound: log p(O1:T ) ≥ Ex1:T∼qθ [ ∑T t=1 r(st,at) − log πθ(at|st)] (Rawlik et al., 2012; Toussaint, 2009). Instead of directly differentiating the variational lower bound for the whole trajectory, it is possible to take a message passing approach such as the one used in Soft Actor-Critic (SAC) (Haarnoja et al., 2018) and directly estimate the optimal policy p(at|st,Ot:T ) using the backward message, i.e a soft Q function instead of the Monte Carlo return.

heading: 2.2 SEQUENTIAL MONTE CARLO METHODS

text:
Since distributions over trajectories are complex, it is often difficult or impossible to directly draw samples from them. Fortunately in statistics, there are successful strategies for drawing samples from complex sequential distributions, such as SMC methods.
For simplicity, in the remainder of this section we will overload the notation and refer to the target distribution as p(x) and the proposal distribution as q(x). We wish to draw samples from p but we only know its unnormalized density. We will use the proposal q to draw samples and estimate p. In the next section, we will define the distributions p and q in the context of planning.
Importance sampling (IS): When x can be efficiently sampled from another simpler distribution q i.e. the proposal distribution, we can estimate the likelihood of any point x under p straightforwardly by computing the unnormalized importance sampling weights w(x) ∝ p(x)q(x) and using the identity p(x) = w̄(x)q(x) where w̄(x) = w(x)∫
w(x)q(x)dx is defined as the normalized importance sampling
weights. In practice, one draws N samples from q: {x(n)}Nn=1 ∼ q; these are referred to as particles. The set of particles {x(n)}Nn=1 associated with their weights {w(n)}Nn=1 are simulations of samples from p. That is, we approximate the density p with a weighted sum of diracs from samples of q:
p(x) ≈ N∑ n=1 w̄(n)δx(n)(x), withx (n) sampled from q
where δx0(x) denotes the Dirac delta mass located as x0.
Sequential Importance Sampling (SIS): When our problem is sequential in nature x = x1:T , sampling x1:T at once can be a challenging or even intractable task. By exploiting the sequential structure, the unnormalized weights can be updated iteratively in an efficient manner: wt(x1:t) = wt−1(x1:t−1)
p(xt|x1:t−1) q(xt|x1:t−1) . We call this the update step. This enables us to sample sequentially
xt ∼ q(xt|x1:t−1) to finally obtain the set of particles {x(n)1:T } and their weights {w (n) T } linearly in the horizon T .
Sequential Importance Resampling (SIR): When the horizon T is long, samples from q usually have a low likelihood under p, and thus the quality of our approximation decreases exponentially with T . More concretely, the unnormalized weights w(n)t converge to 0 with t→∞. This usually causes the normalized weight distribution to degenerate, with one weight having a mass of 1 and the others a mass of 0. This phenomenon is known as weight impoverishment.
One way to address weight impoverishment is to add a resampling step where each particle is stochastically resampled to higher likelihood regions at each time step. This can typically reduce the variance of the estimation from growing exponentially with t to growing linearly.

heading: 3 PLANNING AS PROBABILISTIC INFERENCE

text:
In the context of control as inference, it is natural to see planning as the act of approximating a distribution of optimal future trajectories via simulation. In order to plan, an agent must possess a model of the world that can accurately capture consequences of its actions. In cases where multiple trajectories have the potential of being optimal, the agent must rationally partition its computational resources to explore each possibility. Given finite time, the agent must limit its planning to a finite horizon h. We, therefore, define planning as the act of approximating the optimal distribution over
trajectories of length h. In the control-as-inference framework, this distribution is naturally expressed as p(a1, s2, . . . sh,ah|O1:T , s1), where s1 represents our current state.

heading: 3.1 PLANNING AND BAYESIAN SMOOTHING

text:
As we consider the current state s1 given, it is equivalent and convenient to focus on the planning distribution with horizon h: p(x1:h|O1:T ). Bayesian smoothing is an approach to the problem of estimating the distribution of a latent variable conditioned on all past and future observations. One method to perform smoothing is to decompose the posterior with the two-filter formula (Bresler, 1986; Kitagawa, 1994):
p(x1:h|O1:T ) ∝ p(x1:h|O1:h) · p(Oh+1:T |xh) (3.1)
This corresponds to a forward-backward messages factorization in a Hidden Markov Model as depicted in figure 3.1. We broadly underline in orange forward variables and in blue backward variables in the rest of this section.
Filtering is the task of estimating p(x1:t|O1:t): the probability of a latent variable conditioned on all past observations. In contrast, smoothing estimates p(x1:t|O1:T ): the density of a latent variable conditioned on all the past and future measurements.
In the belief propagation algorithm for HMMs, these probabilities correspond to the forward message αh(xh) = p(x1:h|O1:h) and backward message βh(xh) = p(Oh+1:T |xh) , both of which are computed recursively. While in discrete spaces these forward and backward messages can be estimated using the sumproduct algorithm, its complexity scales with the square of the space dimension making it unsuitable for continuous tasks. We will now devise efficient strategies for estimating reliably
the full posterior using the SMC methods covered in section 2.2.

heading: 3.2 THE BACKWARD MESSAGE AND THE VALUE FUNCTION

text:
The backward message p(Oh+1:T |xh) can be understood as the answer to: “What is the probability of following an optimal trajectory from the next time step on until the end of the episode, given my current state?”. Importantly, this term is closely related to the notion of value function in RL. Indeed, in the control-as-inference framework, the state- and action-value functions are defined as V (sh) , log p(Oh:T |sh) and Q(sh,ah) , log p(Oh:T |sh,ah) respectively. They are solutions of a soft-Bellman equation that differs a little from the traditional Bellman equation (O’Donoghue et al., 2016; Nachum et al., 2017; Schulman et al., 2017; Abdolmaleki et al., 2018). A more in depth explanation can be found in (Levine, 2018). We can show subsequently that:
p(Oh+1:T |xh) = Esh+1|xh [ exp ( V (sh+1) )] (3.2)
Full details can be found in Appendix A.3. Estimating the backward message is then equivalent to learning a value function. This value function as defined here is the same one used in Maximum Entropy RL (Ziebart, 2010).

heading: 3.3 SEQUENTIAL WEIGHT UPDATE

text:
Using the results of the previous subsections we can now derive the full update of the sequential importance sampling weights. To be consistent with the terminology of section 2.2, we call p(x1:h|O1:T )
the target distribution and qθ(x1:h) the proposal distribution. The sequential weight update formula is in our case:
wt = wt−1 · p(xt|x1:t−1,O1:T ) qθ(xt|x1:t−1)
∝ wt−1 1 qθ(xt|x1:t−1) p(x1:t|O1:t) p(x1:t−1|O1:t−1) p(Ot+1:T |xt) p(Ot:T |xt−1)
∝ wt−1 · Est+1|st,at [exp ( A(st,at, st+1) ) ]
Where A(st,at, st+1) = rt − log πθ(at|st) + V (st+1)− logEst|st−1,at−1 [exp ( V (st) ) ] (3.3) is akin to a maximum entropy advantage function. The change in weight can be interpreted as sequentially correcting our expectation of the return of a trajectory.
The full derivation is available in Appendix A.4. Our algorithm is similar to the Auxilliary Particle Filter (Pitt & Shephard, 1999) which uses a one look ahead simulation step to update the weights. Note that we have assumed that our model of the environment was perfect to obtain this slightly simplified form. This assumption is made by most planning algorithms (LQR, CEM . . . ): it entails that our plan is only as good as our model is. A typical way to mitigate this issue and be more robust to model errors is to re-plan at each time step; this technique is called Model Predictive Control (MPC) and is commonplace in control theory.

heading: 3.4 SEQUENTIAL MONTE CARLO PLANNING ALGORITHM

text:
We can now use the computations of previous subsections to derive the full algorithm. We consider the root state of the planning to be the current state st. We aim at building a set of particles {x(n)t:t+h}Nn=1 and their weights {w(n)t+h}Nn=1 representative of the planning density p(xt:t+h|O1:T ) over optimal trajectories. We use SAC (Haarnoja et al., 2018) for the policy and value function, but any other Maximum Entropy policy can be used for the proposal distribution. Note that we used the value function estimated by SAC as a proxy the optimal one as it is usually done by actor critic methods.
Algorithm 1 SMC Planning using SIR 1: for t in {1, . . . , T} do 2: {s(n)t = st}Nn=1 3: {w(n)t = 1}Nn=1 4: for i in {t, . . . , t+ h} do 5: // Update 6: {a(n)i ∼ π(a (n) i |s (n) i )}Nn=1
7: {s(n)i+1, r (n) i ∼ pmodel(·|s (n) i ,a (n) i )}Nn=1 8: {w(n)i ∝ w (n) i−1 · exp ( A(s (n) i ,a (n) i , s (n) i+1) ) }Nn=1
9: // Resampling 10: {x(n)1:i }Nn=1 ∼ Mult(n;w (1) i , . . . , w (N) i ) 11: {w(n)i = 1}Nn=1 12: end for 13: Sample n ∼ Uniform(1, N). 14: // Model Predictive Control 15: Select at, first action of x (n) t:t+h 16: st+1, rt ∼ penv(·|st,at) 17: Add (st,at, rt, st+1) to buffer B 18: Update π, V and pmodel with B 19: end for We summarize the proposed algorithm in Algorithm 1. At each step, we sample from the proposal distribution or model-free agent (line 6) and use our learned model to sample the next state and reward (line 7). We then update the weights (line 8). In practice we only use one sample to estimate the expectations, thus we may incur a small bias. The resampling step is then performed (line 10-11) by resampling the trajectories according to their weight. After the planning horizon is reached, we sample one of our trajectories (line 13) and execute its first action into the environment (line 15-16). The observations (st,at, rt, st+1) are then collected and added to a buffer (line 17) used to train the model as well as the policy and value function of the model-free agent. An alternative algorithm that does not use the resampling step (SIS) is highlighted in Algorithm 2 in Appendix A.6.
A schematic view of the algorithm can also be found on figure 3.2.

heading: 3.5 OPTIMISM BIAS AND CONTROL AS INFERENCE

text:
We now discuss shortcomings our approach to planning as inference may suffer from, namely encouraging risk seeking policies.
1
1
1
Bias in the objective: Trajectories having a high likelihood under the posterior defined in Equation 2.1 are not necessarily trajectories yielding a high mean return. Indeed, as logEp [ expR(x) ] ≥
Ep [ R(x) ] we can see that the objective function we maximize is an upper bound on the quantity of interest: the mean return. This can lead to seeking risky trajectories as one very good outcome in logE exp could dominate all the other potentially very low outcomes, even if they might happen more frequently. This fact is alleviated when the dynamics of the environment are close to deterministic (Levine, 2018). Thus, this bias does not appear to be very detrimental to us in our experiments 4 as our environments are fairly close to deterministic. The bias in the objective also appears in many control as inference works such as Particle Value Functions (Maddison et al., 2017a) and the probabilistic version of LQR proposed in Toussaint (2009).
Bias in the model: A distinct but closely related problem arises when one trains jointly the policy πθ and the model pmodel, i.e if q(x1:T ) is directly trained to approximate p(x1:T |O1:T ). In that case, pmodel(st+1|st,at) will not approximate penv(st+1|st,at) but penv(st+1|st,at,Ot:T ) (Levine, 2018). This means the model we learn has an optimism bias and learns transitions that are overly optimistic and do no match the environment’s behavior. This issue is simply solved by training the model separately from the policy, on transition data contained in a buffer as seen on line 18 of Algorithm 1.

heading: 4 EXPERIMENTS

heading: 4.1 TOY EXAMPLE

text:
In this section, we show how SMCP can deal with multimodal policies when planning. We believe multimodality is useful for exploring since it allows us to keep a distribution over many promising trajectories and also allows us to adapt to changes in the environment e.g. if a path is suddenly blocked.
We applied two version of SMCP: i) with a resampling step (SIR) ii) without a resampling step (SIS) and compare it to CEM on a simple 2D point mass environment 4.1. Here, the agent can control the displacement on (x, y) within the square [0, 1]2, a = (∆x,∆y) with maximum magnitude ||a|| = 0.05. The starting position (•) of the agent is (x = 0, y = 0.5), while the goal (?) is at g = (x = 1, y = 0.5). The reward is the agent’s relative closeness increment to the goal:
(a) Sequential Importance Resampling (SIR): when resampling the trajectories at each time step, the agent is able to focus on the promising trajectories and does not collapse on a single mode.
(b) Sequential Importance Sampling (SIS): if we do not perform the resampling step the agent spends most of its computation on uninteresting trajectories and was not able to explore as well.
(c) CEM: here the agent samples all the actions at once from a Gaussian with learned mean and covariance. We needed to update the parameters 50 times for the agent to find one solution, but it forgot the other one.
Figure 4.1: Comparison of three methods on the toy environment. The agent (•) must go to the goal (?) while avoiding the wall ( | ) in the center. The proposal distribution is taken to be an isotropic gaussian. Here we plot the planning distribution imagined at t = 0 for three different agents. A darker shade of blue indicates a higher likelihood of the trajectory. Only the agent using Sequential Importance Resampling was able to find good trajectories while not collapsing on a single mode.
rt = 1− ||st+1−g|| 2
||st−g||2 . However, there is a partial wall at the centre of the square leading to two optimal trajectories, one choosing the path below the wall and one choosing the path above.
The proposal is an isotropic normal distribution for each planning algorithm, and since the environment’s dynamics are known, there is no need for learning: the only difference between the three methods is how they handle planning. We also set the value function to 0 for SIR and SIS as we do not wish to perform any learning. We used 1500 particles for each method, and updated the parameters of CEM until convergence. Our experiment 4.1 shows how having particles can deal with multimodality and how the resampling step can help to focus on the most promising trajectories.

heading: 4.2 CONTINUOUS CONTROL BENCHMARK

text:
The experiments were conducted on the Open AI Gym Mujoco benchmark suite (Brockman et al., 2016; Todorov et al., 2012). To understand how planning can increase the learning speed of RL agents we focus on the 250000 first time steps. The Mujoco environments provide a complex benchmark with continuous states and actions that requires exploration in order to achieve state-of-the-art performances.
The environment model used for our planning algorithm is the same as the probabilistic neural network used by Chua et al. (2018), it minimizes a gaussian negative log-likelihood model: LGauss(θ) = 12 N∑ n=1 [µθ(sn,an)−(sn+1−sn)]>Σ−1θ (sn,an)[µθ(sn,an)−(sn+1−sn)]+log detΣθ(sn,an),
where Σθ is diagonal and the transitions (sn,an, sn+1) are obtained from the environment. We added more details about the architecture and the hyperparameters in the appendix A.5.
We included two popular planning algorithms on Mujoco as baselines: CEM (Chua et al., 2018) and Random Shooting (RS) (Nagabandi et al., 2017). Furthermore, we included SAC (Haarnoja et al., 2018), a model free RL algorithm, since i) it has currently one of the highest performances on Mujoco tasks, which make it a very strong baseline, and ii) it is a component of our algorithm, as we use it as a proposal distribution in the planning phase.
Our results suggest that SMCP does not learn as fast as CEM and RS initially as it heavily relies on estimating a good value function. However, SMCP quickly achieves higher performances than CEM and RS. SMCP also learns faster than SAC because it was able to leverage information from the model early in training.
Note that our results differ slightly from the results usually found in the model-based RL literature. This is because we are tackling a more difficult problem: estimating the transitions and the reward function. We are using unmodified versions of the environments which introduces many hurdles. For instance, the reward function is challenging to learn from the state and very noisy. Usually, the environments are modified such that their reward can be computed directly from the state e.g. Chua et al. (2018) 3.
As in Henderson et al. (2017), we assess the significance of our results by running each algorithm with multiple seeds (20 random seeds in our case, from seed 0 to seed 19) and we perform a statistical significance test following Colas et al. (2018). We test the hypothesis that our mean return on the last 100k steps is higher than the one obtained by SAC. Our results are significant to the 5% for HalfCheetah and Walker2d. See Appendix A.7 for additional details.
We also report some additional experimental results such as effective sample size and model loss in Appendix A.8.

heading: 5 RELATED WORK

text:
Planning as inference: Seeing planning as an inference problem has been explored in cognitive neuroscience by Botvinick & Toussaint (2012) and Solway & Botvinick (2012). While shedding light on how Bayesian inference could be used in animal and human reasoning, it does not lead to a practical algorithm usable in complex environments. In the reinforcement learning literature, we are only aware of Attias (2003) and Toussaint & Goerick (2007) that initially framed planning as an inference problem. However, both works make simplifying assumptions on the dynamics and do not attempt to capture the full posterior distribution.
Control and planning: In the control theory literature, particle filters are usually used for inferring the true state of the system which is then used for control (Andrieu et al., 2004). Kantas et al. (2009) also combined SMC and MPC methods. While their algorithm is similar to ours, the distribution they approximate is not the Bayesian posterior, but a distribution which converges to a Dirac on the best trajectory. More recently, Kurutach et al. (2018) achieved promising results on a rope manipulation task using generative adversarial network (Goodfellow et al., 2014) to generate future trajectories.
Model based RL: Recent work has been done in order to improve environment modeling and account for different type of uncertainties. Chua et al. (2018) compared the performance of models that account for both aleatoric and epistemic uncertainties by using an ensemble of probabilistic models. Ha & Schmidhuber (2018) combined the variational autoencoder (Kingma & Welling, 2013) and a LSTM (Hochreiter & Schmidhuber, 1997) to model the world. Buckman et al. (2018) used a model to improve the target for temporal difference (TD) learning. Note that this line of work is
3https://github.com/kchua/handful-of-trials/tree/e1a62f217508a384e49ecf7d16a3249e187bcff9/ dmbrl/env
complementary to ours as SMCP could make use of such models. Other works have been conducted in order to directly learn how to use a model (Guez et al., 2018; Weber et al., 2017; Buesing et al., 2018).
Particle methods and variational inference: Gu et al. (2015) learn a good proposal distribution for SMC methods by minimizing the KL divergence with the optimal proposal. It is conceptually similar to the way we use SAC (Haarnoja et al., 2018) but it instead minimizes the reverse KL to the optimal proposal. Further works have combined SMC methods and variational inference (Naesseth et al., 2017; Maddison et al., 2017b; Le et al., 2017) to obtain lower variance estimates of the distribution of interest.

heading: 6 CONCLUSION AND FUTURE WORK

text:
In this work, we have introduced a connection between planning and inference and showed how we can exploit advances in deep learning and probabilistic inference to design a new efficient and theoretically grounded planning algorithm. We additionally proposed a natural way to combine model-free and model-based reinforcement learning for planning based on the SMC perspective. We empirically demonstrated that our method achieves state of the art results on Mujoco. Our result suggest that planning can lead to faster learning in control tasks.
However, our particle-based inference method suffers some several shortcomings. First, we need many particles to build a good approximation of the posterior, and this can be computationally expensive since it requires to perform a forward pass of the policy, the value function and the model for every particle. Second, resampling can also have adverse effects, for instance all the particles could be resampled on the most likely particle, leading to a particle degeneracy. More advanced SMC methods dealing with this issue such as backward simulation (Lindsten et al., 2013) or Particle Gibbs with Ancestor Sampling (PGAS) (Lindsten et al., 2014) have been proposed and using them would certainly improve our results.
Another issue we did not tackle in our work is the use of models of the environment learned from data. Imperfect model are known to result in compounding errors for prediction over long sequences. We chose to re-plan at each time step (Model Predictive Control) as it is often done in control to be more robust to model errors. More powerful models or uncertainty modeling techniques can also be used to improve the accuracy of our planning algorithm. While the inference and modeling techniques used here could be improved in multiple ways, SMCP achieved impressive learning speed on complex control tasks. The planning as inference framework proposed in this work is general and could serve as a stepping stone for further work combining probabilistic inference and deep reinforcement learning.

heading: ACKNOWLEDGMENTS

text: The authors would like to thank Julien Cornebise, Philippe Beaudoin and Alexandre Bouchard-Côté for their interest and useful discussions. The authors would like to thank Stephanie Long, Anqi Xu, Kris Sankaran, Adrien Ali-Taı̈ga, Rémi Le Priol, and Christian Rupprecht for reviewing an earlier version of the paper. The authors want to thank the Open Philanthropy Project, NSERC, Canada Research Chairs, CIFAR AI Chairs, National Science Foundation awards EHR-1631428 and SES-1461535 as well as NVIDIA for equipment.

heading: A APPENDIX

heading: A.1 ABBREVIATION AND NOTATION

heading: A.2 THE ACTION PRIOR

text:
The true joint distribution 2.1 in section 2.1 should actually be written:
p(x1:T ,O1:T ) = µ(s1) T−1∏ t=1 penv(st+1|at, st) T∏ t=1 p(at) exp ( T∑ t=1 r(st,at) )
= µ(s1) T−1∏ t=1 penv(st+1|at, st) exp ( T∑ t=1 r(st,at) + log p(at) )
In Mujoco environments, the reward is typically written as
r(st,at) = f(st)− α||at||22
where f is a function of the state (velocity for HalfCheetah on Mujoco for example). The part α||at||22 can be seen as the contribution from the action prior (here a gaussian prior). One can also consider the prior to be constant (and potentially improper) so that is does not change the posterior p(x1:T |O1:T ).
A.3 VALUE FUNCTION: BACKWARD MESSAGE p(Ot+1:T |xt) = ∫ xt+1 p(Ot+1:T ,xt+1|xt)dxt+1
= ∫ xt+1 p(xt+1|xt,Ot+1:T )p(Ot+1:T |xt+1)dxt+1
= ∫ st+1 penv(st+1|st,at) [∫ at+1 p(at+1|st+1,Ot+1:T ) expQ(st+1,at+1)dat+1 ] dst+1
= ∫ st+1 penv(st+1|st,at) exp ( V (st+1) ) dst+1
= Est+1|st,at [exp ( V (st+1) ) ] (A.1)
By definition of the optimal value function in (Levine, 2018).
A.4 RECURSIVE WEIGHTS UPDATE
wt = p(x1:t|O1:T ) q(x1:t)
= p(x1:t−1|O1:T ) q(x1:t−1) p(xt|x1:t−1,O1:T ) q(xt|x1:t−1) = wt−1 · p(xt|x1:t−1,O1:T ) q(xt|x1:t−1)
= wt−1 1 q(xt|x1:t−1) p(x1:t|O1:T ) p(x1:t−1|O1:T )
We use there the forward-backward equation 3.1 for the numerator and the denominator
∝ wt−1 1 q(xt|x1:t−1) p(x1:t|O1:t) p(x1:t−1|O1:t−1) p(Ot+1:T |xt) p(Ot:T |xt−1) = wt−1 p(xt|x1:t−1) q(xt|x1:t−1) p(Ot|xt) p(Ot+1:T |xt) p(Ot:T |xt−1)
= wt−1 penv(st|st−1,at−1) pmodel(st|st−1,at−1) exp(rt) πθ(at|st) Est+1|st,at [exp
( V (st+1) ) ]
Est|st−1,at−1 [exp ( V (st) ) ]
= wt−1 penv(st|st−1,at−1) pmodel(st|st−1,at−1)
Est+1|st,at [exp ( rt − log πθ(at|st) + V (st+1)− logEst|st−1,at−1 [exp ( V (st) ) ] ) ]
(A.2)

heading: A.5 EXPERIMENT DETAILS

text:
Random samples: 1000 transitions are initially collected by a random policy to pretrain the model and the proposal distribution. After which the agents start following their respective policy.
Data preprocessing: We normalize the observations to have zero mean and standard deviation 1.
Model Predictive Control: The model is used to predict the planning distribution for the horizon h of N particles. We then sample a trajectory according to its weight and return the first action of this trajectory. In our experiments, we fix the maximum number of particles for every method to 2500. For SMCP, the temperature and horizon length are described in Table A.3.
Soft Actor Critic: We used a custom implementation with a Gaussian policy for both the SAC baseline and the proposal distribution used for both versions of SMCP. We used Adam (Kingma & Ba, 2014) with a learning rate of 0.001. The reward scaling suggested by Haarnoja et al. (2018) for all experiments and used an implementation inspired by Pong (2018). We used a two hidden layers with 256 hidden units for the three networks: the value function, the policy and the soft Q functions.
Model: We train the model pmodel to minimize the negative log likelihood of p(st+1|st + ∆t(st, at), σt(st, at)). The exact architectures are detailed in Table A.3. We train the model to predict the distribution of the change in states and learn a deterministic reward function from the current state and predict the change in state. Additionally, we manually add a penalty on the action magnitude in the reward function to simplify the learning. At the end of each episode we train the model for 10 epochs. Since the training is fairly short, we stored every transitions into the buffer. The model is defined as:
∆st ∼ p(·|st, at) (A.3) rt = g(st,∆st)− α‖a‖2 (A.4)
where α was taken from the Mujoco gym environments. We used Adam (Kingma & Ba, 2014) with a learning rate of 0.001 and leaky ReLU activation function.

heading: A.6 SEQUENTIAL IMPORTANCE SAMPLING PLANNING

text:
Algorithm 2 SMC Planning using SIS 1: for t in {1, . . . , T} do 2: {s(n)t = st}Nn=1 3: {w(n)t = 1}Nn=1 4: for i in {t, . . . , t+ h} do 5: // Update 6: {a(n)i ∼ π(a (n) i |s (n) i )}Nn=1
7: {s(n)i+1, r (n) i ∼ pmodel(·|s (n) i ,a (n) i )}Nn=1 8: {w(n)i ∝ w (n) i−1 · exp ( A(s (n) i ,a (n) i , s (n) i+1) ) }Nn=1
9: end for 10: Sample n ∼ Categorical(w(1)t+h, . . . , w (N) t+h). 11: // Model Predictive Control 12: Select at, first action of x (n) t:t+h 13: st+1, rt ∼ penv(·|st,at) 14: Add (st,at, rt, st+1) to buffer B 15: Update π, V and pmodel with B 16: end for

heading: A.7 SIGNIFICANCE OF THE RESULTS

text:
The significance of our results is done following guidelines from Colas et al. (2018). We test the hypothesis that the mean return of our method is superior to the one of SAC. We use 20 random seeds (from 0 to 19pro) for each method on each environment.
For this we look at the average return from steps 150k to 250k for SIR-SAC and SAC, and conduct a Welch’s t-test with unknown variance. We report the p-value for each environment tested on Mujoco. A pval < 0.05 usually indicates that there is strong evidence to suggest that our method outperforms SAC.
• HalfCheetah-v2: pval = 0.003. There is very compelling evidence suggesting we outperform SAC. • Hopper-v2: pval = 0.09. There is no significant evidence suggesting we outperform SAC. • Walker2d-v2: pval = 0.03. There is compelling evidence suggesting we outperform
SAC.

heading: A.8 ADDITIONAL EXPERIMENTAL RESULTS

heading: A.8.1 EFFECTIVE SAMPLE SIZE

text:
The values reported on Figure A.1 are the harmonic mean of the ratio of the effective sample size by the actual number of particles.
More precisely the values are
yt = ( h∏ i=1 ESSi(t)/N )1/h
where i is the depth of the planning, N is the number of particles and ESSi(t) = ( ∑N n=1 w (n) t+i)
2∑N n=1(w (n) t+i) 2
We can see that as the proposal distribution improves the ESS also increases. The ESS on HalfCheetah is representative of the one obtained on the other environments. While these values are not high, we are still around 15% thus we do not suffer heavily from weight degeneracy.

heading: A.8.2 MODEL LOSS

text: We also report the negative log likelihood loss of the environment’s model during the training on Figure A.2.

title: SEQUENTIAL MONTE CARLO METHODS