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. Consider a fixed Markov Decision Process (MDP) M and an agent aiming to maximize its total expected/discounted reward obtained in the environment E governed by M. An agent is looking for a sequence of actions a 0 , ..., a T −1 leading to a series of steps maximizing this reward. One of the approaches is to construct a policy π θ : S → A, parameterized by vector θ, which is a mapping from states to actions. Policy π θ 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 parameters θ correspond to weights and biases of a neural network. Reinforcement learning policies π θ often consist of thousands or millions of parameters (e.g. when they involve vision as 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 resource constrained settings (e.g. limited storage), emerging in particular in mobile robotics (Gage, 2002) . The main question we tackle in this paper is 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 a 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 a joint objective between the combinatorial nature of the network'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., 2018; Zoph & Le, 2017) to optimize over the combinatorial component of this objective and state of 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 edge-partitioning (colorings) into same-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 counterparts accuracy-wise, while leading to the substantial reduction of the number of parameters from 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 vectorized form. As we see, a policy defined by a matrix with 24 entries is effectively encoded by a 9-dimensional vector. thousands (Salimans et al., 2017) to hundreds (Choromanski et al., 2018) . Instead of quadratic (in sizes of hidden layers), those policies use only linear number of parameters. The Toeplitz structure can 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 is not learned. We show in this paper that weight sharing patterns can be effectively learned, which further reduces the number of distinct parameters. For instance, using architectures of the same sizes as those in (Choromanski et al., 2018) , we can train effective policies for OpenAI Gym tasks with as few as 17 distinct weights. The latter paper proposes an extremal approach, where weights are chosen randomly instead of being learned, but the topologies of connections are trained and thus are ultimately strongly 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 problems. WANNs replace conceptually simple feedforward networks with general graph topologies using NEAT algorithm (Stanley & Miikkulainen, 2002) providing topological operators to build the network. 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 a combinatorial fashion using reinforcement learning. While (Chen et 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 be combined in a highly scalable but conceptually 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 et 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 SL, as single CPUs cannot train large image-based classifiers in practice. Furthermore, this magnitude of scaling by numerous workers can be difficult with policy 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 a flexible, rigorous approach to training compact neural network architectures for RL problems. Those may be of 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. 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 a 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-art 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-the-art (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 are across different RL tasks (see: Appendix D). We set LSTM hidden layer size to be 64, with 1 hidden layer. The learning rate was 0.001, and the entropy penalty strength was 0.3. We used a moving average weight of 0.99 for the critic, and used a temperature of 1.0 for softmax, with the training algorithm as REINFORCE.
We show that ENAS with ES-optimization in RL is highly scalable, and use it to compactify neural network policies by weight sharing. The authors construct reinforcement learning policies with very few parameters by compressing a feed-forward neural network, forcing it to share weights, and using a reinforcement learning method to learn the mapping of shared weights. This paper combines ideas from ENAS and ES methods for optimisation, and introduces the chromatic network architecture, which partitions weights of the RL network into tied sub-groups.