Reinforcement Learning with Chromatic Networks
Authors: Xingyou Song
Krzysztof Choromanski
Jack Parker-Holder
Yunhao Tang
Wenbo Gao
Aldo Pacchiano
Tamas Sarlos
Deepali Jain
Yuxiang Yang
Venue:  (2020)
Keywords: reinforcement
learning
chromatic
networks
partitioning
efficient
neural
architecture
search
weight
sharing
compactification

Abstract: We present a neural architecture search algorithm to construct compact reinforcement learning (RL) policies, by combining ENAS and ES in a highly scalable and intuitive way. By defining the combinatorial search space of NAS to be the set of different edge-partitionings (colorings) into same-weight classes, we represent compact architectures via efficient learned edge-partitionings. For several RL tasks, we manage to learn colorings translating to effective policies parameterized by as few as 17 weight parameters, providing >90 % compression over vanilla policies and 6x compression over state-of-the-art compact policies based on Toeplitz matrices, while still maintaining good reward. We believe that our work is one of the first attempts to propose a rigorous approach to training structured neural network architectures for RL problems that are of interest especially in mobile robotics with limited storage and computational resources.

Under review as a conference paper at ICLR 2020
REINFORCEMENT LEARNING WITH CHROMATIC NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We present neural architecture search algorithm to construct compact reinforce- ment learning (RL) policies. by combining ENAS (Vinyals et al., 2015; Pham et al., 2018; Zoph & Le. 2017) and ES (Salimans et al., 2017) in a highly scalable and intuitive way. By defining the combinatorial search space of NAS to be the set of different sdge-partitionings (colorings) into same-weight classes, resent compact architectures via efficient learned RL tasks, manage learn colorings translating to effective policies parame- terized by as few as 17 weight parameters, providing > 90% compression over vanilla policies and 6x compression over state-of-the-art compact policies based on Toeplitz matrices (Choromanski et al., 201 8), while still maintaining good re- ward. We believe that our work is one of the first attempts to propose rigorous approach to training structured neural network architectures for RL problems that are of interest especially in mobile robotics (Gage, 2002) with limited storage and computational resources.
rep-
For several
INTRODUCTION
Consider a fixed Markov Decision Process (MDP) M and an agent aiming to maximize its total expected/discounted reward obtained in the environment & governed by M. An agent is looking for a sequence of actions ag. ar-1 leading to series of steps maximizing this reward. One of the approaches is to construct policy Te S + A, parameterized by vector 8 which is mapping from states to actions. Policy Th determines actions chosen in states visited by an agent. Such a reinforcement learning (RL) policy is usually encoded as a neural network, in which scenario pa- rameters 9 correspond to weights and biases neural network. Reinforcement learning policies Ty often consist of thousands millions of parameters (e.g. when they involve vision part of the state vector) and therefore training them becomes a challenging high-dimensional optimization problem. Deploying such high-dimensional policies on hardware raises additional concerns in source constrained settings (c.g. limited storage), emerging in particular in mobile robotics (Gage, 2002). The main question we tackle in this paper the following:
Are high dimensional architectures necessary for encoding efficient policies and if not, how compact can they be in in practice?
We show that finding such compact representations is nontrivial optimization problem despite recent observations that some hardcoded structured families (Choromanski et al., 2018) provide certain levels of compactification and good accuracy at the same time.
We model the problem of finding compact presentations by using joint objective between the combinatorial nature of the network's 's parameter sharing profile and the reward maximization of RL optimization. We leverage recent advances in the ENAS (Efficient Neural Architecture Search) literature and theory of pointer networks (Vinyals et al., 2015; Pham et al., 201 8; Zoph & Le, 2017) to optimize over the combinatorial component of this objective and state the art evolution strategies (ES) methods (Choromanski et al., 2018; Salimans et al., 2017: Mania et al., 2018a) to optimize over the RL objective. We propose to define the combinatorial search space to be the the set of different partitiootii (colorings) into same same-weight weight classes and construct policies with learned weight-sharing mechanisms. We call networks encoding our policies: chromatic networks.
We are inspired by two recent papers: (Choromanski et al., 2018) and (Gaier & Ha, 2019). In the former one, policies based on Toeplitz matrices were shown to match their unstructured counter- parts accuracy-wise, while leading to the substantial reduction of the number of parameters from

---

Under review as a conference paper at ICLR 2020
w
W
2/12
3
T
7Tg
w
w
w
w
Wn
1012
3/3
w
2
Figure/ 1: On the left: matrix encoding linear Toeplitz policy at time t for the RL task with 6- dimensional state vector and 4-dimensional action vector. On the right: that policy in the vector- ized form. As we see, a policy defined by a matrix with 24 entries effectively encoded by a 9-dimensional vector.
thousands (Salimans et al., 2017) to hundreds (Choromanski al., 2018). Instead of quadratic (in sizes of hidden layers), those policies use only linear number of parameters. The Toeplitz structure be thought of as a parameter sharing mechanism, where edge weights along each diagonal of the matrix are the same (see: Fig. 1). However, this is a rigid pattern that not learned. We show in this paper that weight sharing patterns be effectively learned, which further reduces the number of distinct parameters. For instance, using architectures of the same sizes as those (Choroman- ski al., 2018),
train effective policies for OpenAI Gym tasks with as few 17 distinct weights. The latter paper proposes an extremal approach, where weights are chosen randomly in- stead of being learned, but the topologies of connections biased towards RL tasks under consideration. It was shown in (Gaier & Ha, 2019) that such weight agnostic neural networks (WANNs) can encode effective policies for several nontrivial RL prob- lems. WANNs replace conceptually simple feedforward networks with general graph topologies using NEAT algorithm (Stanley & Miikkulainen, 2002) providing topological operators to build the network.
trained and thus are ultimately strongly
Our approach is a middle ground, where the topology is still a feedforward neural network, but the weights are partitioned into groups that are being learned in combinatorial fashion using reinforce- ment learning. While (Chen al., 2015) shares weights randomly via hashing, we learn a good partitioning mechanisms for weight sharing.
Our key observation is that ENAS and ES can naturally combined in a highly scalable but concep- tually simple way. To give context, vanilla NAS (Zoph & Le. 2017) for classical supervised learning setting (SL) requires a large population of 450 GPU-workers (child models) all training one-by-one, which results in many GPU-hours of training. ENAS (Pham al., 2018) uses weight sharing across multiple workers to reduce the time, although it can reduce computational resources at the cost of the variance of the controller's gradient. Our method solves both issues (fast training time and low controller gradient variance) by leveraging a large population of much-cheaper CPU workers (300) increasing the effective batch-size of the controller, while also training the workers simultaneously via ES. This setup is not possible in SI., as single CPUs cannot train large image-based classifiers practice. Furthermore, this magnitude of scaling by numerous workers can be difficult with pol- icy gradient or Q-learning methods as they can be limited by GPU overhead due to exact-gradient computation.
We believe that our work is one of the first attempts to propose flexible, rigorous approach to train- ing compact neural network architectures for RL problems. Those may be particular importance in mobile robotics (Gage, 2002) where computational and storage resources are very limited. We also believe that this paper opens several new research directions regarding structured policies for robotics.
1.1 BACKGROUND AND RELATED WORK
Network Architecture Search:
The subject of this paper can be put in the larger context of Neural Architecture Search (NAS) algorithms which recently became a prolific area of research with already voluminous literature (see: (Elsken et al., 2019) for an excellent survey). Interest in NAS algorithms started to grow rapidly when it was shown that they can design of-te----theart architectures for image recognition and language modeling (Zoph & Le, 2017). More recently it was shown that NAS
2

---

Under review as a conference paper at ICLR 2020
network generators can be improved to sample more complicated connectivity patterns based on random graph theory models such as Pedos--Renyl Barebasi-Albert or Satts--trroaaz to outperform human-designed networks, e.g. ResNet and ShuffleNet on image recognition tasks (Xic et al., 2019). However to the best of our knowledge, applying NAS to construct compact RL, policy architectures has not been explored before. On broader scope, there has been little work in applying NAS to general RL policies, partially because unlike SL, RL policies are quite small and thus do not require a search space involving hyperparameter primitives such as number of hidden layers, convolution sizes, etc. However, we show that the search space for RL policies can still be quite combinatorial, by examining partitionings of weights in our work.
Parameterizing Compact Architectures: Before NAS can be applied, a particular parameteriza- tion of a compact architecture defining combinatorial search space needs be chosen. That leads to the vast literature on compact encodings of NN architectures. Some of the most popular and efficient techniques regard network sparsification. The sparsity can be often achieved by pruning al- ready trained networks. These methods have been around since the 1980s, dating back to Rumelhart (Rumelhart, 1987; Chauvin, 1989; Mozer Smolensky, 1989), followed shortly by Optimal Brain Damage (Cun et al., 1990). which used second order gradient information to remove connections. Since then, a variety of schemes have been proposed, with regularization (Louizos et al., 2018) and magnitude- basde weight pruning methods (Han et al., 2015; See et al., 2016; Narang et al., 2017) increasingly popular. The impact of dropout (Srivastava et al., 2014) has added an additional perspective, with new works focusing attempts learn sparse networks (Gomez et al., 2019). Another recent work introduced the Lottery Ticket Hypothesis (Frankle & Carbin, 2019), which captivated the community by showing that there exist equivalently sparse networks which can be trained from scratch to achieve competitive results. Interestingly. these works consistently report similar levels of compression, often managing match the performance of original networks with up to 90% fewer parameters. Those methods are however designed for constructing classification networks rather than those encoding RL policies.
Quantization: Weight sharing mechanism can be viewed from the quantization point of view, where pre-trained weights are quantized, thus effectively partitioned. Examples include (Han al., 2016), who achieve 49x compression for networks applied for vision using both pruning and weight sharing (by quantization) followed by Huffman coding. However such partitions are not learned which is a main topic of this paper. Even more importantly, in RL applications, where policies are often very sensitive to parameters' weights (Iscen et al., 2018), centroid-based quantization is too crude to preserve accuracy.
Compact RL Policies In recent times there has been increased interest in simplifying RL poli- cies. In particular, (Mania et al., 2018b) demonstrated that linear policies are often sufficient for the benchmark MuJoCo locomotion tasks, while (Cuceu et al., 2019) found smaller policies could work for vision-based tasks by separating feature extraction and control. Finally, recent work found that small, sparse sub-networks can perform better than larger over paraaamtatteee ones (Frankle & Carbin, 2019), inspiring applications in RL (Yu al., 2019).
Our main contributions are:
1. We propose a highly scalable algorithm by combining ENAS and ES for learning compact representations that learns effective policies with over 92% reduction of the number of neural network parameters (Section 3).
2. To demonstrate the impact (and limitations) of pruning neural networks for RL, we adapt recent algorithms training both masks defining combinatorial structure as well as weights of deep neural network concurrently (see: (Lenc et al., 2019)). Those achieve otate-of- the-art results on various supervised feedforward and recurrent models. We confirm these findings in the RI. setting by showing that good rewards can be obtained up to high level of pruning. However, at the 80-90% level we see a significant decrease in performance which does not occur for the proposed by us chromatic networks (Section 4. Section 4.2).
3. We demonstrate that finding efficient weight-partitioniss mechanisms is a challenging problem and NAS helps to construct distributions producing good partitionings for more difficult RL environments (Section 4.3).
3

---

Under review as a conference paper at ICLR 2020
2 THE ARCHITECTURE OF NEURAL ARCHITECTURE SEARCH
The foundation of our algorithm for learning structured compact policies is the class of ENAS methods (Pham et al., 2018). To present our algorithm, we thus need to first describe this class. ENAS algorithms are designed to construct neural network architectures thus they aim to solve conbinatorial-flaoore optimization problems with exponential-sizz domains. The problems are cast as MDPs, where a controller encoded by the LSTM-based policy cont (0), typically parame- terized by few hundred hidden units, is trained to propose good-quality architectures, or to be more precise: good-quality distributions D()) over architectures. In standard applications the score of the particular distribution D(0) is quantified by the average performance obtained by trained mod- els leveraging architectures A ~ D(0) on the fixed-size validation set. That score determines the reward the controller obtains by proposing D()). LSTM-based controller constructs architectures using softmax classifiers via autoregressive strategy, where controller's s decision in step is given to it input embedding at time + 1. The initial embedding that the controller starts with is an empty one.
Weight Sharing Mechanism: ENAS introduces a powerful idea of a weight-sharing mechanism. The core concept is that different architectures can be embedded into combinatorial space, where they correspond to different subgraphs of the given acyclic directed base graph G (DAG). Weights of the edges of G represent the shared-pool Wshared from which different architectures will inherit dif- ferently by activating weights of the corresponding induced directed subgraph. At first glance such a mechanism might be conceptually problematic since, a weight of the particular edge e belonging to different architectures Ai, ...A (see: next paragraph for details regarding weight training) will be updated based on evaluations of all of them and different A,8 can utilize However it turns out that this is desirable in practice. As authors of (Pham et al., 2018) explain, the approach is motivated by recent work on transfer and multitask learning that provides theoretical grounds for transferring weights across models. Another way to justify the mechanism is observe that ENAS tries in fact to optimize a distribution over architectures rather than a particular architec- ture and the corresponding shared-pool of weights Wahared should be thought of as corresponding to that distribution rather than its particular realizations. Therefore the weights of that pool should be updated based on signals from all different realizations.
different ways.
Alternating Optimization: For a fixed parameterization 0 defining policy (0) of the controller (and thus also proposed distribution over architectures D(0)), the algorithm optimizes the weights of the models using M architectures: Ai.... sampled from D()), where the sampling is conducted by the controller's policy Teont (9). Models corresponding A1,..., AM are called child models. At iteration l of the weight optimization process, a worker assigned to the architecture A, computes the gradient of the loss function L.A. corresponding data with respect to the weights of the inherited edges from the base DAG. Since the loss function LB, on Wahared for a fixed distribution D(0) and batch B& iteration k is defined as an expected loss BA-a(o) [AA,s, (W sharea)]. where WA Whared stands for the projection of the set of shared- -pool weights Webared into edges defined by the induced subgraph determined by A, its gradient with respect to Wshared can be estimated via Monte Carlo procedure as:
the particular batch B₁ of the training
M V
1 M
Wathared LBy (Wshared)
Wa:
LA.B (WAt shared)
shared
After weight optimization is completed, ENAS updates the parameters A of the controller responsible for shaping the distribution used to sample architectures A. As mentioned before, this is done using reinforcement learning approach, where parameters 0 are optimized to maximize the expected reward (0) [R (A)], where this time set Wahared is frozen and Rwa (A) is given as
shared
the accuracy obtained by the model using architecture A and weights from WA Wisared on the validation set. Parameters 0 are updated with the use of the REINFORCE algorithm (Williams, 1992).
Controller's Architecture: The controller LSTM-based architecture uses pointer networks (Vinyals et al., 2015) that utilize LSSM-enncoer/ddecooer approach. where the decoder can look back and forth over input. Thus these models are examples of architectures enriched with attention.
4

---

Under review as a conference paper at ICLR 2020
3 TOWARDS CHROMATIC NETWORKS - ENAS FOR GRAPH PARTITIONINGS
Preliminaries: Chromatic networks are feedforward NN architectures, where weights are shared across multiple edges and sharing mechanism is learned via modified ENAS algorithm that we present below. Edges sharing particular weight form the so-called chromatic class. An example of the learned partitioniing is presented on Fig. 2. Learned weight-sharing mechanisms are more complicated than hardcoded ones from Fig. 1, but lead smaller-size partitionings. For instance, Toeplitz sharing mechanism for architecture from Subfigure (b) of Fig. 2 requires 103 weight- parameters, while ours: only 17.
Controller Architecture & Training: We standard ENAS reinforcement learning controller similar to (Pham et al., 2018), applying pointer networks. Our search space is the set of all possible mappings @ E' {0, 1, ,,..; M - 13, where E stands for the set of all edges of the graph encoding an architecture and M is the number of partitions, which the user sets. Thus as opposed to stan- dard ENAS approach, where the search space consists of different subgraphs, we instead deal with different colorings/partitionii D(0) over these partitionings. The shared pool of weights Wahared is a latent vector R where different entries correspond to weight values for different partitions enumerated from 0 to M - 1. As for standard ENAS, the controller x (0) consists of a encoder RNN and decoder RNN, in which the encoder RNN is looped over the embedded input data, while the decoder is looped to repeatedly output smaller primitive components of the final output.
of edges of given base graph. The controller learns distributions
In our setting, we do not possess natural numerical data corresponding to embedding of the inputs which are partition numbers and edges. Therefore we also train an embedding (as part of controller's
parameter vector 0) of both using tables: Vedge Idd and V Vpartition {0, M 1] + Rd.
6
10
(a) Linear Policy- 17 distinct parameters
(b) One--iideen- Layer Policy 17 distinct parameters
Figure 2: On the left: partitioning of edges into distinct weight classes obtained for the linear policy for HalfCheetah environment from OpenAl Gym. On the right: the same, but for a policy with one hidden layer encoded by two matrices. State and action dimensionalities are: = 17 and respectively and hidden layer for the architecture from (b) is of size 41. Thus the size of the matrices are: 17 6 for the linear policy from (a) and: 17 x 41, 41 x 6 for the nonlinear one from (b).
6
We denote by P partitioning of edges and define the reward obtained by controller for fixed distribution (()) produced by its policy (() as follows:
R(0)= Ep-x(")
R Raax
Warreed (P)],
where Wargree (P) stands for the maximal reward obtained during weight-optimization phase of the policy with partitioning P and with initial vector of distinct weights W As for the ENAS setup, in practice this reward is estimated by averaging over M workers evaluating independently different realizations P of D()). The updates of 0 are conducted with the use of REINFORCE.
3.1 WEIGHT UPDATES VIA ES
As opposed to standard ENAS, where weights for fixed distribution D(0) generating architectures were trained by backpropagation, we propose to apply recently introduced ES blackbox optimiza- tion techniques for RL (Choromanski et al., 2018). For fixed partitioning P. define the loss Cp with respect to weights as the negated reward obtained by an agent applying parti- tioning P and with vector of distinct weights Wahared- That expression function of Wahared
5

---

Under review as a conference paper at ICLR 2020
not necessarily differentiable, since it involves calls the simulator. This also implies that plicit backpropagation is not possible. We propose to instead estimate the gradient of its Gaus- sian smoothing L'p (Wshaea) defined as: (WWaarr))))
(0 (n)(rrWssaadd + ag)l for fixed smoothing parameter >. We approximate its gradient given by: Waassrd Cp. (WWhared) = (u [ (WWhared + og)g] with the folloar finite difference unbiased estimator introduced in (Choromanski et al., 2018):
1
1
Lp(Wehared +g:) (p)=z()) [Cp [Cp(Wshared)]
Washared (P((Wshree))
_ ge
0
where g....., ge are sampled independently at random from (0, Iyr) and the pivot point is defined average loss for given set of weights Wahared over partitionings sampled from (0)).
We note that a subtle key difference here from vanilla ES is by using the pivot point Ep-n(() [[saaeare)) as the expectation over distribution of partitions P T(0) rather than static single-query objective L(W) used for e.g. a basic Mujoco task. From a broader perspective, this comes from the fact that ES can optimize any objective of the form Ep-p [f where P is any (possibly discrete) object with distribution P and W is continuous weight vector, by assigning both a perturbed weight W + og and a sampled P to a CPU worker for function evaluation on f(W + og. P).
EXPERIMENTAL RESULTS
The experimental section is organized follows:
In Subsection I show the limitations of the sparse network approach for compactifying RL policies on the example of state-of-the-art class of algorithms from (Lene et al., 2019) that aim to simultaneously train weights and connections neural network architectures.
This approach is conceptually the most similar to ours.
Subsection 4.2 we present exhaustive results on training our chromatic networks with ENAS on OpenAT Gym and quadruped locomotion tasks. We compare sizes and rewards obtained by our policies with those using masking procedure from (Lene et al., 2019), ap- plying low displacement rank matrices for compactification as well as unstructured base- lines.
In Subsection 4.3 analyze in detail the impact of ENAS steps responsible for learning partitions, in particular compare it with the performance random partitionings.
We provide more experimental results in the Appendix.
4.1 LEARNED SPARSE NETWORKS VIA SIMULTANEOUS WEIGHT-TOPOLLOGY TRAINING
The mask m, drawn from multinomial distribution, is trained in (Lenc et al., 2019) using ES and element-wist wise multiplied by the weights before forward pass. In (Lenc et al., 2019), the sparsity of the mask fixed, however, to show the effect of pruning, we instead initialize the sparsity at 50% and increasingly reward smaller networks (measured by the size of the mask (m]) during optimization. Using this approach on several Open AI Gym tasks, we demonstrate that masking mechanism is capable of producing compact effective policies up to a high level of pruning. At the same time, show significant decrease of performance at the 80-90% compression level, quantifying accurately its limits for RI. tasks (see: Fig. 3).

---

Under review as a conference paper at ICLR 2020
Swimmer
HalrCheetah
Striker
Walker2d
Reward Usage
0.4
Roward
2000
600
Usnge
200
2000
400
0,2
1000
3000
200
01
0.0
0.5
1.0
2
0.0
0.5
Timesteps
X10*
Timestops X10*
Timesteps x10"
Timesteps x10*
(a)
(b)
(c)
(d)
Figure 3: The results from training both mask and weights A of neural network with two hidden layers, 41 units each. 'Usage' stands for number of edges used after filtering defined by the mask. At the beginning, the mask is initialized such that |m] is equal 50% of the total number of parameters in the network.
4.2 RESULTS CHROMATIC NETWORKS
We perform experiments on the following OpenAl Gym tasks: Swimmer, Reacher, Hopper, HalfCheetah, Walker2d, Pusher, Striker, Thrower and Ant as well as quadruped locomotion task of forward walking from (Iscen et al., 2018). The performance our algorithm constructing chromatic networks is summarized in Table 1. We tested three classes of feedforward architectures: linear from (Mania et al., 2018a), and nonlinear with one or two hidden layers and tanh nonlincari- ties.
We see a general trend that increasing hidden layers while keeping number partitions fixed, im- proves performance well as increasing the number of partitions while keeping the architecture fixed. The relation between the expressiveness of a linear, high-partitinn policy vs a -lyee,, low-partition policy is however ronment's complexity as well. For HalfCheetah, the linear 50-partition policy performs better than hidden layer 17-partition policy, while this is reversed for for the Minitaur.
well understood. As shown in Table this depends the envi-
In Table we directly compare chromatic networks with a masking approach as discussed in Section 4.1, well as other structured policies (Toeplitz from (Choromanski al., 2018) and circulant) and the unstructured baseline. In all cases we use the same hyper-parameters, and train until convergence for five random seeds. For masking, we report the best achieved reward with 90% of the network pruned, making the final policy comparable in size to the chromatic network. For each class of policies, we compare the number of weight parameters used ("# of weight-params" field), since the compactification mechanism does not operate on bias vectors. We also record compression in respect to unstructured networks in terms of the total number of parameters ("# compression" field). This number determines the reduction of sampling complexity with respect to unstructured networks (which a bottleneck of ES training), since the number of RL blackbox function queries needed to train/up-trac the policy is proportional to the total number of weights and biases of the corresponding network.
Finally, for working policy we report total number of bits required encode it assuming that real values are stored the float format. Note that for chromatic and masking networks this includes bits required to encode dictionary representing the partitioning. Further details are given in the Appendix (Section E). Top two performing networks for each environment are in bold. Chromatic networks are the only to provide big compression and quality the same time across all tasks.
Similarly Toeplitz, chromatic networks also provide computational gains. Us- ing improved version of the mailman-algorith (Liberty & Zucker, 2009), matrix-vecta multipli- cation part of the inference can be run on the chromatic network using constant number of distinct weights and deployed on real hardware in time O [og[max(mmn))) where (m, n) is the shape of the matrix.
Inference Time:
mn
4.3 FURTHER ANALYSIS: RANDOM PARTITIONINGS VERSUS ENAS
A natural question ask is whether ENAS machinery is required or maybe random partitioning is good enough to produce efficient policies. To answer it, we trained joint weights for fixed population of random partitionings without NAS, well with random NAS controller.
7

---

Under review as a conference paper at ICLR 2020
Environment
Dimensions
Architecture
Partitions
Mean Reward
Max Reward
Swimmer
(8,2)
L
97
365
Reacher
(11,2)
L
-144
-6
Hopper
(11.3)
L
11
216
999
Hopper
(11.3)
H41
11
247
3408
HalíChertah
(17,6)
L
17
1812
3653
HalfChertah
(17,6)
L
50
1383
4318
HalCCheetah
(17.6)
H41
2148
3779
HalfCheetah
(17,6)
H41, H41
17
3036
5285
Walker2d
(17,6)
H41
17
1943
3695
Pusher
(23,7)
H41
23
-419
-144
Striker
(23,7)
-992
-248
Thrower
(23,7)
H41
-1651
-61
Ant
(111,8)
H41, H41
50
1047
1440
Minitaur
(7, 13)
L
13
4.84
7.2
Minitaur
(7, 13)
L
50
6.08
7.91
Minitaur
(7. 13)
H44
7.12
9.34
Table 1: Statistics for training chromatic networks. For mean reward, take the average 301 worker rollout-rewards each step, and output the highest average over timesteps. max reward, we report maximum reward ever obtained during the training process by any worker. "L", "H41" and "H41, H41" stand for: lincar policy, policy with one hidden layer of size 41 and policy with two such hidden layers respectively.
Environment
Architecture
Reward
weight-params
compression
bits
Striker
Chromatic
-248
23
95%
8198
Masked
-967
25
95%
8262
Toeplitz
-129
110
88%
4832
Circulant
-120
82
90%
3936
Unstructured
-117
1230
0%
40672
HalfCheetah
Chromatic
3779
17
94%
6571
Masked
4806
40
92%
8250
Toeplitz
2525
103
85%
4608
Circulant
1728
82
88%
3936
Unstructured
3614
943
0%
31488
Hopper
Chromatic
3408
11
92%
3960
Masked
2196
17
91%
4726
Toeplitz
2749
94
78%
4320
Circulant
2680
82
80%
3936
Unstructured
2691
574
0%
19680
Walker2d
Chromatic
3695
17
6571
Masked
1781
19
94%
6635
Tocplitz
1
103
85%
4608
Circulant
3
82
88%
3936
Unstructured
2230
943
0%
31488
Table 2: Comparison of the best policies from five distinct classes of RI networks: chromatic (ours), masked (networks from Subsection 4)1), Toeplitz networks from (Choromanski al., 2018), circulant networks and unstructured trained standard ES algorithm (Salimans al., 2017). All results are for feedforward nets with one hidden layer of size 41.
Our experiments show that these approaches fail by producing suboptimal policies for harder tasks (see: Fig. 4). Note also that if partitioning distribution fixed throughout the entire optimization, training policies for such tasks and restarting to fix another partitioning distribution can cause substantial waste of computational resources, especially for the environments requiring long training time. However also notice intriguing fact that random partitionings still lead nontrivial rewards. We find it similar to the conclusions NAS for supervised learning (Pham et al., 2018) while training random child model sampled from reasonable search space may produce >
8

---

Under review as a conference paper at ICLR 2020
80 % accuracy, the most gains from controller will ultimately be at the tail end; ie. at the 95% accuracies.
4000
1230
4000
1900
3000
2000
2003
2500
390
1397
1020
(a) Fixed Random Population
(b) Random Controller
(c) ENAS Optimization.
Figure 4: Random partitioning experiments versus ENAS for Walker2d. Curves of different colors correspond different workers. The maximal obtained rewards for random partitioinggsdiisrrbuiiii chromatic networks by about 1000. (a): Fixed random population of 301 partitioning for joint training. (b): Replacing ENAS population sampler with random agent. (c): Training with ENAS.
smaller than for
We observe that by training with ENAS, the entire optimization benefits in ways by: (1) select- ing partitionings leading to good rewards, (2) resampling good partitionings based on the controller replay buffer, and breaking through local minima inherently caused by the weight-sharing mech- anism maximizing average reward. We see these benefits precisely when a new ENAS iteration abruptly increases the reward by large amount, which we present Fig. 5.
5000
HatiCheetan, Linear Policy, Parttions, 500 Timesteps
30"-
Stricar, midden Layer Size Potey, 23 Partzions 200 Timestpps
4000
1000
-3000
3500
Layer Timesteps
30*
Layers
Partitons,
307
3000
30
164.
2000
1500
300
30
20000
2000
3000
40000
5000
5000
1000
2000
3000
4000
5000
Figure 5: Training curves for four OpenAT Gym environments: HalfCheetah, Striker, Hopper and Ant. Timesteps when training curves abruptly increase are correlated with those when ENAS controller produces partitioning suggestions (that marked black vertical lines).
CONCLUSION & FUTURE WORK
We presented a principled and flexible algorithm for learning structured neural network architectures for RL policies and encoded by compact sets of parameters. Our architectures, called chromatic networks, rely on partitionings of a small sets of weights learned via ENAS methods. Furthermore, we have also provided scalable way of performing NAS techniques with RL policies which is not limited to weight-sharing, but can potentially also be used to construct several other combinatorial structures in a flexible fashion, such as node deletions and edge removals.
We showed that chromatic networks provide more aggressive compression than their state-of-the-an counterparts while preserving efficiency of the learned policies. We believe that our work opens new research directions, especially from using other combinatorial objects. Detailed analysis of obtained partitionings (see: Appendix C) also shows that learned structured matrices are very different from previously used state-of-tt -o-thh--rtt-tt-- (in particular they are characterized by high displacement rank), yet it is not known what their properties are. It would be also important to understand how transferable those learned partitionings across different RL tasks (see: Appendix D).

---

Under review as a conference paper at ICLR 2020
REFERENCES
Yves Chauvin, A back-propagation algorithm with optimal use of hidden units. In David S. Touret- zky (cd.), Advances in Neural Information Processing Systems pp. 519-526, San Francisco, CA, USA, 1989. Morgan Kaufmann Publishers Inc.
Wenlin Chen, James Wilson, Stephen Tyree, Kilian Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. In International Conference on Machine Learning. pp- 2285-2294, 2015.
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard E. Turner, and Adrian Weller. Structured evolution with compact urchitectures for scalable policy optimization. In Proceed- ings of the 35th International Conference on Machine Learning, 1CML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp. 969-977, 2018.
Giuseppe Cuccu, Julian Togelius, and Philippe Cudré-Maute Maaroux. Playing atari with six neurons. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Sys- lems, AAMAS '1, Richland, SC, 2019.
Yann Le Cun, John S. Denker, and Sara Solla. Optimal brain damage. David S. Touretzky (ed.), Advances in Neural Information Processing Systems 2, San Francisco, CA, USA, 1990. Morgan Kaufmann Publishers Inc.
James Demmel and Plamen Koev. Matrices with displacement structure.
URL
attp::/mathe:
plamen/talks/men tatttaaaaakksttteese pdf.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 20:55:1-55:21, 2019.
Jonathan Frankle and Michael Carbin. networks. In International Conference on Learning Representutions. 2019.
The lottery ticket hypothesis: Finding sparse, trainable neural
Douglas W. Gage (ed.). Mobile Robots XVII, Philadelphia, PA, USA, October 25, 2004,
volume 5609 of SPIE Proceedings, 2002. SPIE. ISBN 978-0-8194-5562-8,
URL
http://proceeding
Adam Gaier and David Ha. Weight agnostic neural networks. CoRR, abs/1906.04358, 2019.
Aidan N. Gomez, Ivan Zhang, Kevin Swersky, Yarin Gal, and Geoffrey E. Hinton. Learning sparse networks using targeted dropout. ArXiv, abs/1905. 13678, 2019.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 1135-1143. Curran Asso- ciates, Inc., 2015.
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and Huffman coding. International Conference on Learning Representations, 2016.
Atil Iscen, Ken Caluwaerts, Jie Tan, Tingnan Zhang, Erwin Coumans, Vikas Sindhwani, and Vincent Vanhoucke. Policies modulating trajectory generators. In 2nd Anmual Conference on Robot Learn- ing, CoRL. 2018, Zürich,, Switzerland, 29-31 October 2018, Proceedings, pp. 916-9996666611 2018.
Karel Lene, Erich Elsen, Tom Schaul, and Karen Simonyan. Non-differentiable supervised learning with evolution strategies and hybrid methods. arXiv, abs//906s 139,, 2019.
Edo Liberty and Steven W Zucker. The mailman algorithm: A note on matrix- multiplication. Information Processing Letters. 109 2009.
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning sparse neural networks through 10 regularization. In International Conference on Learning Representations, 2018.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search provides a competitive approach reinforcement learning CoRR, abs/1 803.0755, 2018a.
10

---

Under review as a conference paper at ICLR 2020
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In Advances in Neural Information Processing Systems, pp. 1800-1809, 2018b.
Marina Meilä. Comparing clusterings by the variation of information. In Bernhard Schölkopf and Manfred K. Warmuth (eds.), Learning Theory and Kernel Machines, pp. 173-187, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. ISBN 978-3-540-45167.9,
Michael C. Mozer and Paul Smolensky. Skeletonization: technique for trimming the fat from a network via relevance assessment. In David S. Touretzky (ed.), Advances in Neural Information Processing Systems I, pp. 107-115, San Francisco, CA, USA, 1989. Morgan Kaufmann Publish- Inc.
Sharan Narang, Gregory Diamos, Shubho Sengupta, and Erich Elsen. Exploring sparsity in recurrent neural networks. In International Conference on Learning Representations, 2017.
Hicu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pp- 4092 4101, 2018.
William M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the Amer- ican Statistical Association, 66(336):846 850, 1971. ISSN 01621459.
D. E Rumelhart. Personal communication. Princeton, 1987.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies as scalable alternative to reinforcement learning, arXiv, 703/1703,,3 2017.
Abigail See, Minh-Thang Luong, and Christopher D. Manning. Compression of neural machine translation models via pruning. In Proceedings of The 20th SIGNLL Conference on Computa- tional Natural Language Learning, Berlin, Germany, August 2016. Association for Computa- tional Linguistics.
Vikas Sindhwani, Tara N. Sainath, and Sanjiv Kumar. Structured transforms for small-footprint deep learning. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal. Quebec, Canada, pp. 3088-3098 2015.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15:1929-1955 1958, 2014.
Kenneth O. Stanley and Risto Miikkulainen. Evolving neural network through augmenting topolo- gies. Evolutionary Computation, 10(2):99-127, 2002.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In Advances in Neural In- formation Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 2692-22222222 2690, 2015.
Ronald J. Williams. Simple statistical seudient-following algorithms for connectionist reinforce- ment learning. Machine Learning, 8:229-256 1992. doi: 10.1007/BF00992266. URL
http:://dooooog///// https://bbb..cr//00000////5555 1ttp:///..100///009922220
Saining Xie, Alexander Kirillov, Ross B. Girshick, and Kaiming He. Exploring randomly wired neural networks for image recognition. CoRR, abs/1994.01556 2019.
Haonan Yu, Sergey Edunov. Yuandong Tian, and Ari Morcos. Playing the lottery with rewards and multiple languages: lottery tickets in rl and nlp. arXiv, hts/1996.02766 2019.
Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning, In 5th In- ternational Conference on Learning Representations. ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
11

---

Under review as a conference paper at ICLR 2020
APPENDIX
A FULL PLOTS
A.1 TRAINING CURVES
We plot black vertical bars in order to denote a NAS update iteration. Different curves correspond to different workers.
10 Minitatar, inear Pairy, 13 Partitions, 200 Timesteps
10
Miritaur, Hiddlnn oyer Sop d1 Policy, 18 Partitions, 200 Timestaps
600
10
Minitaaur, Linear Palicy, 50 Partitions, 200 Timesteps
1400
(a)
Minitaur, Linear Policy 13 Parbition,, limesteps
Minituu, Hodden Layer Size Policy, 1d Partitions, S0U Timesteps
500
1000
1300
500
2003
1500
10
Mintauur, Pertitions, limesteps
500
1500
(b)
Figure 6: Minitaur Ablation Studies
12

---

Under review as a conference paper at ICLR 2020
5000
HottChootph, Uneer Partitions, 200
5000
HaltChettah: Pollcy, Partttios, Timestops
3000
1000
2000
1000
-1000
1000
5000
HalfCheetaa. Hidden Layer Size 41 Policy, 17 Pertitions. 200 Timesteps,
Me /C ICheetahr, Hidder Leyers Size 41 Policy, 17 Partit 200 Timestero
3000
2000
1000
2000
-1000
500
100
2000
5000
(a)
HelfCheelahh, Linwar Pulicy, Parti Ditiooons 500 Tep
HellChwetehs Policy, Partiiom,, Timnetteps
4000
40.00
2000
2000
1030
2000
3000
4000
5030
6000
7000
8000
1000
2000
2000
4000
5000
5000 HalfChoctaly,
Partitions, 500
sooo #Cheatah, Hidsor
Size Policy: Partie Timestepg
3000
3000
2000
2000
1000
500
1500
2000
2500
3000
1530
2000
3000
(b)
Figure 7: HalfCheetah Ablation Studies
13

---

Under review as a conference paper at ICLR 2020
Sptimmer, Linpar Policy, Partitions, 200 Timestops
Reacher, Linear Policy, 11 Partitions, 200 Timestops
300
100
-200
-0"
-400
Hopper. Unear Pojayy 11 Partitions, 200 Timesteps
Hopper Hidden Layer Size 41 Folicy, 11 Partitions, 200 Timesteps
2000
1500
1500
1000
1000
500
500
(a)
Layer Folicy, Timesteps
Pusher, Layer Folicy, Parttions, Timestaps
2000
-30>
1500
2000
500
-500
-00*
8000
307-
Policy,
30
Layer Poticy,
Timestegs
107
100
'00
8000
10a
10"
100
-30
-00
-105
2000
1000
4000
5000
(b)
Figure 8: Other environments (Swimmer, Reacher, Hopper, Walker, Pusher, Striker, Thrower, Ant)
14

---

Under review as a conference paper at ICLR 2020
A.2 MAXIMUM REWARD CURVES
In order to view the maximum rewards achieved during the training process, for each worker every NAS iteration, we record the maximum reward within the interval [NAS itterrttoio T, (NAS_iteration +1) TT), where stadns for the current number of conducted timestpes.
10
Minituur. L near Palicy, 13 Partitions, 200 Timestops
1C Miritaur. Hidden Layer Size 41 Palicy. 13 Partitions 20C Timestops
10.
Mirshappr, I. neg Paliry, 50 Partitions, 200 Timpsshaps
(a)
Minitaur, Policy, Partitions, 500 Timestaps
Minitaur, Hiddlen Layer Palicy, 333. Partittops, 500 Timesteeps
10
Lneg Policy,
300 Timestegs
(b)
Figure Maximum Reward Curves Minitaur Ablation Studies
15

---

Under review as a conference paper at ICLR 2020
5000
HaltChootph, Linear Policy, 17 Fartitions, 200 Timestags
5000
HaitChpotah, Linear Po Icy, 50 Partitions, 200 Timestops
4020
3000
3000
1000
1000
11000
1000
HellCheegahh Hidden Layer Size 42, Policy. 17 Portttions. 200 Timesteps
5000 Harthhethh. Hidden Layers Size 41 Policy, 17 Partitions, 200 Timesteps
4020
4000
1000
3000
2000
2000
1000
1000
11000
1.000
(a)
HellCheetsh, Lineer Policy, 17 Partitions, Timestegs
HeiCCheetah, Lineer Poicy, 50 Pertitions, Timesteps
4000
4000
2000
2000
1000
1000
-1000
U00
Layer Policy, Partitions, Timesteos, so0c HalrCheetah, Layers 41 Policy, Timestand
1030
0000
2000
2000
1000
-1000
(b)
Figure 10: Maximum Reward Curves HalfCheetah Ablation Studies
16

---

Under review as a conference paper at ICLR 2020
Spimmer. Policy. Timesteps
Reapher, Policy. Timesteps
300
-20
-40
-10
-140
-200
Hooper, Linea Polcy, 11 Partition, 290 timesteps
Hopper. Hicpen Laver Size Policy,, Partitions, 200 timesteos
2300
2000
1500
1500
1000
1003
800
300-
3000
Walker, Hidden Loyer Size 41 Pollcy, 17 Partition. 200 Timestopp
Pusher, Hidden Layer Size 41, Rolley, 23 Fartitions, 200 TImestops
4000
-200
2000
1000
-000
12
Striker, Hidden Laver Size $1, Poticy, 2.5 Partitoo, 2001 mesteps
Ihrower. Midee Laver bize 41 Poticyy 23 Partitions, 20U Limestego
-500
1000
1500
1500
2200
10
20
75
10
10
70
Ant. Hidden Layers Size Policy. 50 Pertt ons. 200 Timestaps
1000
800
600
-200
10
20
(b)
Figure 11: Maximum Reward Curves other environments (Swimmer, Reacher, Hopper, Walker, Pusher, Striker, Thrower, Ant)
17

---

Under review as a conference paper at ICLR 2020
B EXACT SETUP AND HYPERPARAMETERS
B.I CONTROLLER SETUP
We set LSTM hidden layer size to be 64, with hidden layer. The learning rate was 0.001, and the entropy penalty strength was 0.3. We used moving average weight of 0.99 for the critic, and used a temperature of 1.0 for softmax, with the training algorithm as REINFORCE.
B.2 POLICY
We use tanh non-linearities. For all the environments, used reward normalization, and state normalization from (Mania et al., 2a) except for Swimmer. We further used action normalization for the Minitaur tasks.
B.3 AL-ARIIRITHM
For ESSooptimization, we used algorithm from (Choromanski et al., 2018), where we applied Monte Carlo estimators of the Gaussian smoothings to conduct gradient steps using forward finite- difference expressions. Smoothing parameter and learning rate were: 0.1, 0.01.
C PARTITIONINGS METRICS
We analyzed obtained partitionings to understand whether they admit simpler representations and how they relate to the partitionings corresponding to Toeplitz-like matrices that are used on a regular basis for the compactification of RI. policies.
C.I SINGLE PARTITIONING METRICS
Partitionings' Entropies: We analyze the distribution of color assignments for network edges for partitioning, by interpreting the number of edges assigned for each color as count, and therefore probability after normalizing by the total number of edges. We computed entropies of the corresponding probabilistic distributions encoding frequencies of particular colors. We noticed that entropies are large, in particular the representations will not substantially benefit from further compacification using Huffman coding (see: Fig. 12).
Partition Assignment Entroples
40-
40.
45
35
35
35
25
25
20
20
15
10.
10.
5
9.5
2.43
3.50
2.50
40
P110
2:433
2.000
2.60
HalfCheetah, 17P, 500
Hopper,
Ant
35
35
30
25
25
20
20
10
10
5-
2000
8cco
I.h
(a)
Figure 12: The blue bars count the number of produced partitionings with the entropy within given range. For comparison the entropy of the random uniform partitioning is presented red line.
18

---

Under review as a conference paper at ICLR 2020
Displacement Rank: Recall that the displacement rank (Sindhwani et al., 2015; Demmel & Koev) of a matrix R with respect to two matrices: A, A is defined as the rank of the resulting matrix VR) FR R.A. Toeplitz-type matrices are defined those that have displacement rank with respect to specific band matrices (Sindhwani et al., 2015; Demmel & Koev). We further analyze the displacement ranks of the weight matrices for chromatic networks, and find that they are full displacement rank using band matrices (P, A) for both the Toeplitz- and the matrices (see: Fig. 13).
Topelitz Displacement Ranks
JaliCheetah, L17P,500
5000,
HalfCheetah, 17P,
50
50
50
0
huntah, T.
Hopaer, 11P,
50
50
0
40
12
10
20
25
30
35
40
(a)
Topelitz-Hankel Displacement Ranks
350
HallCheetah, 17P, 200
350
HalfCheetah, L S0P, 500
350
HartCheetah, H 17P, 500
300
300
300
250
250
200
200
150
150
150
100
100
100
50
50
50
10
12
14
16
4
5
8
10
12
14
16
0
8
10
12
14
16
18
350
HalfCheetah, HH. 17P,
500
350
Hopper, 11P,
200
350
Antt
HH SQP,
200
300
300
250
250
200
200
200
150
150
150
100
100
100
50
50
50
0
15
20
25
30
35
40
0
4
8
10
12
0
10
15
20
25
30
35
40
45
(b)
Figure 13: Displacement Ranks Weight Matrices induced by Partitions at the end of training. We round entry of the matrix to if its absolute value is less than 0.1.
19

---

Under review as a conference paper at ICLR 2020
C.2 PAIRWISE PARTITIONINGS METRICS
We examine the partitionings produced by the controller throughout the optimization by defining different metrics in the space of the partitionings and analyzing convergence of the sequences of produced partitionings in these matrics. We view partitionings as clusterings in the space of all edges of the network. Thus we can use standard cluster similarity metrics such as RandIndex (Rand, 1971) and Variation of Information (Meilä, 2003). Distance metric counts the number of edges that reside in different clusters (indexed with the indices of the vector of distinct weights) in two compared partitoningssclusteringg. We do not observe any convergence in the analyzed metrics (see: Fig. 14). This suggests that the space the partitionings found training is more complex. We leave its analysis for future work.
Painwise Partition Metrics
7300
230
2580
2560
2540
320
190
2600
2520
7100
300
7050
280
160
2360
7000
0.900
Rand Index
0.9370
0.885
0.855
0.800
0.851
0.820
0.950
0.830
09955
305
10c-
350
1210
1200
300
100
90
1170
1300
1330
16
HalfCheetah, 17P, 500
HalfCheetah, 50P,
Hopper, 11P, 200
Striker, 23P, 200
(a)
Figure 14: Variation of Information (VT), RandIndex, and Distance. X-axis corresponds NAS iteration number during training.
20

---

Under review as a conference paper at ICLR 2020
D TRANSFERABILITY
We tested transferability of partitionings across different RL tasks by using the top-5 partitionings (based maximal reward) from HalfCheetah (one-hidden-layer network of size using them to train distinct weights (for the inherited partitionings) using vanilla-ES for Walker2d (both environments have state and action vectors of the same sizes). This compared with the results when random partitionings were applied. Results are presented on Fig. 15. We notice that transfered partitionings do not underperform. We leave understanding the scale in which these learned partitionings can be transfered across tasks to future work.
41), and
Single Random Partitions, 1 Hidden Layer Size 41
Transfer Partitions from HallCheetah, Hidden Layer Size 41
3500
3500
3000
2500
2500
2000
2000
1500
1500
1000
1000
500
%
5000
10000
15000
20000
5000
10000
15000
20000
(a)
(b)
Figure 15: (a): Random partitioning used train Walker2d. (b): Transfer of the partitioning from HalfCheetah to Walker2d. Transfered partitionings do not underperform.
E EXPERIMENT SETUP FOR BASELINES IN TABLE
We compare the Chromatic network with other established frameworks for structrued neural network architectures. In particular, we consider Unstructured, Toeplitz, Circulant and masking mechanism (Choromanski et al., 2018; Lenc et al., 2019). We introduce their details below.
Notice that all baseline networks share the same general architecture: 1-hidden layer with = 41 units and tanh non-linear activation. To be concrete, we only have two weight matrices W1 R(Sixh W2 e |RA and two bias vectors by E IRh b2 RRA- where |-],|-4| are dimensions of state/action spaces. These networks differ in how they parameterize the weight matrices.
Unstructured. A fully-connected layer with unstructured weight matrix W e Boxb has total of ab independent parameters.
Toeplitz. toeplitz weight matrix W E Raxb has a total of a 1 independent parameters. This architecture has been shown to be effective in generating good performance on benchmark tasks yet compressing parameters (Choromanski et al., 2018).
Circulant. A circulant weight matrix W Raxb is defined for square matrices b. We generalize this definition by considering square matrix of size n x n where n = max (a, b} and then do proper truncation. This produces independent parameters.
Masking. One additional technique for reducing the number of independent parameters in a weight matrix is mask out redundant parameters (Lene al., 2019). This slightly differs from the other aforementioned architectures since these other architectures allow for parameter sharing while the masking mechanism carries out pruning. To be concrete, we consider fully-connected matrix W E Raxb with ab independent parameters. We also setup another mask weight S Raxb, Then the mask is generated via
M = softmax(M/a),
where softmax is applied elementwise and is constant. We 0.01 that the softmax effectively a thresolding function wich outputs near binary masks. We then treat the entire con- catenated parameter 0 [W, S] trainable parameters and optimize both using ES methods. At
21

---

Under review as a conference paper at ICLR 2020
convergence, the effective number of parameter is ab l where 1) is the proportion of M components that are non-zero. During optimization, we implement a simple heuristics that encourage sparse network: while maximize the true environment return R E."r. Tr. we also maximize the number of
mask entries that are zero - v). The ultimate ES objective is: R' = B R+ (1 B) (1 - v)) where
[0,) 1] is combination coefficient which anneal training progresses. We also properly normalize R and (1 - 77) before the linear combination to ensure that the procedure is not sensitive
reward scaling.
22


Reviews:
[{"review_id": "ryxxgC3nYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper focuses on neural architecture search for constructing compact RL policies. It combines ideas from the popular ENAS and ES methods for optimisation. Recent work defined a family of compact policies by imposing a fixed Toeplitz structure. This paper introduces the so-called “chromatic network” architecture, which partitions weights of the RL network into tied sub-groups. The partitioning is searched with ENAS and shared weights are updated via ES. Experiments on continuous control benchmarks show that good performance can be obtained using a very small number of parameters. Favourable reward-compression outcomes can be achieved compared to some baseline alternatives.\n\nTo my understanding the main contributions are (1) the Chromatic parameter sharing scheme and (2) the combined ENAS+ES learning procedure.  \n\nPros:\n+ Chromatic networks provide a neat idea for managing compact networks via parameter sharing. (Although not dramatically novel given cited work by Salimans, Gaier, etc)\n+ Searching both the partitioning + weight values with ENAS and ES provides a nice way to do learning & compact architecture search simultaneously.\n+ Results generally show favourable compression/reward performance vs Mask, Toeplitz  and Circulant baselines. \n\nCons & Questions: \n0. Motivation. The paper claims that RL can be high-dimensional with millions of parameters, and so there is a need to apply NAS to RL. But experiments are conducted in low dimensional environments with only 100s of parameters. The empirical validation doesn’t match the motivating scenario. We would want to see results on successful compression of larger vision-based networks to be fully persuaded. Without this it undermines the significance of the paper. The paper makes a claim about embedded devices, but this is unconvincing, as for these proprioceptive control tasks, the uncompressed networks are already small enough to run on most embedded devices. \n\n 1. ENAS vs Chromatic. Both use RL controllers. The main difference to ENAS seems to be the Chromatic sharing scheme, and use of ES rather than Backprop to update the weights. Some points of motivation/justification are not very clear after reading: (1) Why vanilla ENAS can’t be used for RL? (with the modification of replacing standard backdrop with any standard continuous control RL algorithm for weight updates). It is sort of claimed that ENAS can’t be used, it’s not obvious to me that this is true. (2) How is the  Chromatic strategy specific for RL? In principle it should also be usable in SL. Assessing its performance in SL would be more broadly relevant, interesting and significant since there is more prior compression work in SL.\n\n2. The paper is a bit vague about how number of partitions is set. Is it a user-specifiable parameter, if so how do we set it? It’s suggested that partition number is included in the reward function, but then it’s even more unclear how to calibrate this to hit a particular performance or size target (or optimize performance for fixed size, size for fixed performance constraint) that a user may require in practice.\n\n3. The real (wall-clock) running time for different NAS methods should be reported in the results. \n\n4. Baselines. The presented results are a reasonable start, but they are all very much variations within the same family. One would like to know how the current method compares to: (i) Direct application of ENAS (See also Q1), (ii) Training the full network and applying standard NN pruning techniques (such as magnitude based), (iii) Baseline of training a comparably small sized network directly. (ivv) Importantly, since the size of networks here are very small, classic neuro-evolution algorithms from evolutionary robotics such as NEAT (Stanley & Miikkulainen) seem to provide a reasonable alternative. It’s hard to know if to be impressed with the current result or not without seeing the results for a decent NEAT-like competitor. (See also Q0).\n\nOther:\nA. A presentation of the algorithm with pseudocode would help the reader follow an overview of the algorithm. \nB. Is the RL network/method used for the tasks the same as the network used in paper “Structured Evolution with Compact Architectures for Scalable Policy Optimization”? If so what is the source of the discrepancy between Tab 2 here and Tab 1 in that paper? \nC. The title doesn’t make the content obvious to a naive prospective reader. At least something like “RL with Chromatic Networks for Compact Architecture Search” would be more informative.\nD. Eq (1) has a vspace error. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SyeLlLDCKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper compresses policy networks using approaches inspired by neural architecture search. The main idea is to have a fixed size weight matrix, but learn how to share weights, so that the resulting network can be compressed by storing only unique weights values. Both the partitioning and weights are trained simultaneously, inspired by ENAS. The partitioning is modeled by an autoregressive RNN and trained via REINFORCE. The weights are modeled by a single set of weights (as opposed to a distribution) which is then updated by using a gradient approximation based on ES. The experiments carried out include comparing to existing works on policy network compression, ablating against random partitioning, as well as a few experiments meant to increase understanding of the learned partitions.\n\nPros:\n - Overall, paper is well-presented and is generally quite clear on its contributions, place in the literature, and experiment details.\n - The approach is straightforward and has applications in compressing RL policies.\nCons:\n - There should be standard deviations in Table 2 across multiple seeds, as it is unclear whether the differences in reward are significant.\n- There is some discussion on scalability in the introduction as part of the motivation, though would be nice to see some quantitative numbers. Is the current method already highly scalable, or is scalable still a potential that has yet to be reached?\n\nQuestions:\n - What is the computational cost in total CPU time, compared to baselines such as fixed random partitioning? The autoregressive sampling of partitioning seems to be a bottleneck during training, as sampling may be slow, especially when scaling to larger weight matrices. Is this why the partitioning is updated much more sparsely (as shown in Figure 5)?\n - For the gradient estimation in eq 3, what exactly is this unbiased with respect to? Did you mean asymptotically unbiased in the limit as sigma -> 0?\n - Do Chromatic networks always use M partitions? (How exactly were the number of partitions chosen, for Tables 1 and 2?) If I understood correctly, Figure 3 is about the Masked networks from (Lenc et al., 2019). If so, is there a similar method in which the number of partitions of Chromatic networks can be learned (or regularized)?\n - (I may have misunderstood these figures, but:) There seems to be quite a large difference in training curves for different workers, e.g. shown in Figures 4 and 5. The red curve seems to almost always be best, while the green curve is much higher variance. Why is this? I also couldn't tell exactly how many colors there are in these plots (introduction mentions 300?), but wouldn't a mean/std plot be easier to parse (or do the specific colors mean something significant)?\n - Is there a reason why Toeplitz and Circulant have missing numbers in the #bits columns in Table 2?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "BklD1K8hFr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to construct reinforcement learning policies with very few parameters. For this purpose, they force a feed-forward neural network to share most of its weights, reducing the total number of different weights to at most 23 and therefore compress the network. Instead of manually encoding which weights are shared, the authors propose to use a reinforcement learning method to learn this mapping. The values of all parameters are learned with a gradient-based method.\n\nThe paper is very well-written. The concepts are easy to follow, the related work covers a lot of different but related domains. The experimental section sheds light on some important aspects. However, I have few concerns regarding Table 2.\n\nTable 1 considers more tasks than Table 2. Why did you decide to use only a subset and why these tasks? The architecture of the FFNN is not part of your search space but you admit it is very important. For the experiments you chose a FFNN with one hidden layer. Furthermore, you manually adapted the number of partitions. Would fixing the architecture to one hidden layer work in general? How do you select the number of partitions? Both these choices seem crucial and to invalidate the automation aspect. You select the best run of 300. Do your baselines follow a comparable setup? What if you compare mean rewards? The discussion of random partitions is very important and it is nice to see that you discuss this in Section 4.3. As you mentioned, in NAS random search is a strong competitor. Therefore, this method deserves to be added to Table 2 as well.\nConcluding, this is an okay paper with limited innovation. The comparison to baseline need to be improved or at least justified.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper describes a method for learning compact RL policies suitable for mobile robotic applications with limited storage.  The proposed pipeline is a scalable combination of efficient neural architecture search (ENAS) and evolution strategies (ES).  Empirical evaluations are conducted on various OpenAI Gym and quadruped locomotion tasks, producing policies with as little as 10s of weight parameters, and significantly increased compression-reward trade-offs are obtained relative to some existing compact policies.

Although reviewers appreciated certain aspects of this paper, after the rebuttal period there was no strong support for acceptance and several unsettled points were expressed.  For example, multiple reviewers felt that additional baseline comparisons were warranted to better calibrate performance, e.g., random coloring, wider range of generic compression methods, classic architecture search methods, etc.  Moreover, one reviewer remained concerned that the scope of this work was limited to very tiny model sizes whereby, at least in many cases, running the uncompressed model might be adequate.
Decision: Reject