Playing Atari with Six Neurons (Extended Abstract)

1 Introduction

In deep reinforcement learning, a large network learns to map complex, high dimensional input to actions for direct policy approximation. When a giant network with hundreds of thousands of parameters learns a relatively simple task (such as playing Qbert) it stands to reason that only a small part of what is learned is the actual policy.

Separating the representation learning from policy learning allows in principle for higher component specialization, enabling smaller networks dedicated to policy learning to address problems typically tackled by much larger networks. Separating the policy network from image parsing also allows us to better understand how network complexity contributes to accurately representing the policy. Yet another reason to investigate how to learn smaller policy networks by addressing image processing with a separate component is that smaller networks may offer better generalization.

∗Original work published at AAMAS 2019 [Cuccu et al., 2019].

The key contribution of this paper is a new method for learning policy and features simultaneously but separately in a complex reinforcement learning setting. This is achieved through two novel algorithms: Increasing Dictionary Vector Quantization (IDVQ) and Direct Residuals Sparse Coding (DRSC).

IDVQ maintains a dictionary of centroids in the observation space, which can then be used for encoding. The two main differences with standard VQ are that the centroids are (i) trained online by (ii) disregarding reconstruction error. The dictionary trained by IDVQ is then used by DRSC to produce a compact code for each observation. This code is used in turn by the neural network (policy) as input to select the next action. The code is a binary string: a value of '1' indicates that the corresponding centroid contains information also present in the image, and a limited number of centroids are used to represent the totality of the information.

As the training progresses and more sophisticated policies are learned, complex interactions with the environment result in increasingly novel observations; the dictionary reflects this by growing in size, including centroids that account for newly discovered features.

With the goal of minimizing the network size while maintaining comparable scores, experimental results show that this approach can effectively learn both components simultaneously, achieving state-of-the-art performance on several ALE games while using a neural network of only 6 to 18 neurons, i.e. two orders of magnitude smaller than any known previous implementation. This extended abstract is based on the original AAMAS 2019 publication [Cuccu et al., 2019].

2 RelatedWork

Video games are frequently used for AI research [Yannakakis and Togelius, 2018]. The Arcade Learning Environment (ALE), based on an emulation of the Atari 2600, is a very popular benchmark set [Bellemare et al., 2013]. In the most common setup, the raw pixel output of the ALE framework is used as inputs to a neural network, and the outputs are interpreted as commands for playing the game. Using this setup, Mnih et al. reached above human level results on a majority of 57 Atari games that come with the standard distribution of ALE [Mnih et al., 2015]. Since then, a number of improvements have been suggested that have improved gameplaying strength on most of these games [Hessel et al., 2017; Justesen et al., 2019].

Neuroevolution uses evolutionary algorithms to train neural networks [Floreano et al., 2008; Yao, 1999; Igel, 2003; Risi and Togelius, 2017]. Typically, this means training the connection weights of a fixed-topology neural network, though some algorithms evolve the topology as well [Stanley andMiikkulainen, 2002]. Until recently, reinforcement learning generally relied on low-dimensional features, either by using intrinsically low-dimensional sensors (such as infrared or laser range-finders) or by using hard-coded computer vision techniques. Such hard mappings generalize badly; in order to create a more general reinforcement learning method, the mapping must be automatically constructed or learned.

3 Method

Our system is divided into four main components: i) the Environment is an Atari game, taking actions and providing observations; ii) the Compressor extracts a low-dimensional code from the observation, while being trained online with the rest of the system; iii) the Controller is our policy approximator, i.e. the neural network; finally iv) the Optimizer is our learning algorithm, improving the performance of the network over time, in our case an Evolution Strategy. Each component is described in more detail below.

3.1 Environment

We test our method on the Arcade Learning Environment (ALE), interfaced through the OpenAI Gym framework [Brockman et al., 2016]. As discussed above, ALE is built on top of an emulator of the Atari 2600, with all the limitations of that console. In keeping with ALE conventions, the observation consists of a [210×180×3] tensor, representing the RGB pixels of the screen input.

3.2 Compressor

The role of the compressor is to provide a compact representation for each observation coming from the environment, enabling the neural network to entirely focus on decision making. This is done through unsupervised learning on the very same observations that are obtained by the network interacting with the environment, in an online learning fashion.

We propose a new algorithm based on Vector Quantization (VQ) named Increasing Dictionary VQ (IDVQ), coupled with a new Sparse Coding (SC) method named Direct Residuals SC (DRSC). The following section gives a step-by-step guide on the application of IDVQ+DRSC. The full derivations and pseudocode algorithms are available in the main publication [Cuccu et al., 2019].

Step-by-Step Breakdown of IDVQ and DRSC

IDVQ is used to train a dictionary, which can then be used by DRSC to encode (i.e. extract features from) an observation (image). To understand how these two algorithms work together, let us hypothesize a working starting dictionary and see how DRSC produces an encoding.

Initialization. Two components need to b initialized: the code, as an arrays of zeros of the same size as the dictionary, and the residual information which still needs encoding, initially the whole original image.

Next centroid. The algorithm then loops to select centroids to add to the encoding, based on how much of the residual information they can encode. To select the most similar centroid, the algorithm computes the differences between the residual information and each centroid in the dictionary, aggregating each of these differences by summing all values. The centroid with the smallest aggregated difference is thereby the most similar to the residual information, and is chosen to be included in the encoding.

Encoding. The corresponding bit in the binary code is flipped to '1', and the residual information is updated by subtracting the new centroid.

Interpreting residual information. The signs of the values in the updated residual information (old residual minus new centroid, the order matters) are now significant: (i) values equal to zero mean a perfect correspondence between the pixel information in the old residual and the corresponding value in the new centroid; (ii) positive values correspond to information that was present in the old residual but not covered by the new centroid; (iii) negative values correspond to information present in the new centroid, but absent (or of smaller magnitude) in the old residual. This is crucial towards the goal of fully representing the totality of the original information, and to this end the algorithm is free to disregard reconstruction artifacts as found in (iii).

Loop. The algorithm then keeps looping and adding centroids until the (aggregated) residual information is lower than a threshold, corresponding to an arbitrary precision in capturing the information in the original image.

Dictionary training. The dictionary is trained with IDVQ by adding new centroids to minimize leftover residual information in the encoding. The training begins by selecting an image from the training set and encoding it with DRSC, producing the binary code as described above. A dot product between the code and the dictionary (i.e. summing the centroids selected by the code, since it is binary) produces a reconstruction of the original image, similarly to other dictionary-based algorithms.

Residual information. The difference between the training image and the reconstruction then produces a reconstruction error (-image), where the sign of the values once again correspond to their origin: positive values are leftover information from the image which is not encoded in the reconstruction, while negative values are reconstruction artifacts with no relation to the original image. This reconstruction error image is then aggregated (with a sum) to estimate the quantity of information missed by the encoding.

Adding new centroids. If it is above a given threshold, a new centroid should be added to the dictionary to enable DRSC to make a more precise reconstruction. But in that case the residual itself makes for the perfect centroid, as it exactly captures the information missed by the current encoding, and is then added to the dictionary.

3.3 Controller

The controller for all experiments is a single-layer fullyconnected recurrent neural network (RNN). The number of inputs is equal at any given point in time to the size of the code coming from the compressor. As the compressor's dictionary grows in size, so does the network's input. In order to ensure continuity in training (i.e. the change needs to be transparent to the training algorithm), it is necessary to define an invariance across this change, where the network with expanded weights is equivalent to the previous one. This is done by setting the weights of all new connections to zero, making the new network mathematically equivalent to the previous one, as any input on the new connections cancels out.

The number of neurons in the output layer is kept equal to the dimensionality of the action space for each game, as defined by the ALE simulator. No hidden layers nor extra neurons were used in any of the presented results.

3.4 Optimizer

The optimizer used in the experiments is a variation of Exponential Natural Evolution Strategy(XNES; [Glasmachers et al., 2010]) tailored for evolving networks with dynamic size.

Since the parameters are interpreted as network weights in direct encoding neuroevolution, changes in the network structure need to be reflected by the optimizer in order for future samples to include the new weights.

In order to respect the network's invariance, the expected value of the distribution (µ) for the new dimension should be zero. As for Σ, we need values for the new rows and columns in correspondence to the new dimensions.

Example. Take for example a one-neuron feed-forward network with 2 inputs plus bias, totaling 3 weights. Let us select a function mapping the optimizer's parameters to the weights in the network structure (i.e. the genotype to phenotype function), as to first fill the values of all input connections, then all bias connections. Extending the input size to 4 requires the optimizer to consider two more weights before filling in the bias:

with cij being the covariance between parameters i and j, σ2 k the variance on parameter k, and ϵ being arbitrarily small (0.0001 here). The evolution can pick up from this point on as if simply resuming, and learn how the new parameters influence the fitness.

4 Experimental Setup

The following covers the most important choices in our experimental setup. Please refer to the main paper for a detailed description [Cuccu et al., 2019].

• Population size and learning rates are dynamically adjusted based on the number of parameters, based on the XNES minimal population size and default learning rate [Glasmachers et al., 2010].
• The average dictionary size by the end of the run is around 30-50 centroids, but games with many small moving parts tend to grow over 100. In such games there seems to be direct correlation between higher dictionary size and performance, but our reference machine performed poorly over 150 centroids.
• Every individual is evaluated on 5 environment initializations to reduce fitness variance.
• Experiments are allotted a mere 100 generations, which averages to 2 to 3 hours of run time on our reference machine.

These restrictions are extremely tight compared to what is typically used in studies utilizing the ALE framework. Limited experimentation indicates that relaxing any of them, i.e. by accessing the kind of hardware usually dedicated to modern deep learning, consistently improves the results on the presented games. The full implementation is available on GitHub under MIT license 1 .

1 https://github.com/giuse/DNE/tree/six neurons

5 Results

The goal of this work is not to propose a new generic feature extractor for Atari games, nor a novel approach to beat the best scores from the literature. Our declared goal is to show that dividing feature extraction from decision making enables tackling hard problems with less resources, and that the deep networks typically dedicated to this task can be substituted for simple encoders and tiny networks while maintaining comparable performance. Table ?? emphasizes our findings in this regard. Under these assumptions, Table ?? presents comparative results over a set of 10 Atari games from the hundreds available on the ALE simulator.

The resulting scores are compared with recent papers that offer a broad set of results across Atari games on comparable settings, namely HyperNeat [Hausknecht et al., 2014], OpenAI ES [Salimans et al., 2017], GA (1B) [Such et al., 2017], and NSRA-ES [Conti et al., 2018], showing comparable results (and sometimes better). Notably, our setup achieves high scores on Qbert, arguably one of the harder games for its requirement of strategic planning.

The real results of the paper are however highlighted in Table ??, which compares the number of neurons, hidden layers and total connections utilized by each approach. Our setup uses up to two order of magnitude fewer neurons, two orders of magnitude fewer connections, and is the only one using only one layer (no hidden layer, equivalent to a simple linear controller).

6 Conclusions

We presented a method to address complex learning tasks, such as learning to play Atari games, by decoupling policy learning from feature construction, learning them independently but simultaneously to further specializes each role. Features are extracted from raw pixel observations coming from the game using a novel and efficient sparse coding algorithm named Direct Residual Sparse Coding. The resulting compact code is based on a dictionary trained online with yet another new algorithm called Increasing Dictionary Vector Quantization, which uses the observations obtained by the networks' interactions with the environment as policy search progresses. Finally, tiny neural networks are evolved to decide actions based on the encoded observations, achieving results comparable with the deep neural networks typically used for these problems while being two orders of magnitude smaller.

The implication is that feature extraction on some Atari games is not as complex as often considered. On top of that, the neural network trained for policy approximation is also very small in size, showing that the decision making itself can be done by relatively simple functions. One goal of this paper is to clear the way for new approaches to learning, and to call into question a certain orthodoxy in deep reinforcement learning, namely that image processing and policy should be learned together (end-to-end).

Acknowledgments

This work received support from the Swiss NSF under grant number 407540 167320.