Scalable neuroevolution for reinforcement learning

The idea of using evolutionary computation to train artificial neural networks, or neuroevolution (NE), has now been around for over 20 years. The main appeal of this approach is that, because it does not rely on gradient information (e.g. backpropagation), it can potentially harness the universal function approximation capability of neural networks to solve reinforcement learning (RL) tasks, where there is no "teacher" (i.e. no targets or examples of correct behavior). Instead of incrementally adjusting the synaptic weights of a single network, the space of network parameters is searched directly according to principles inspired by natural selection: (1) encode a population of networks as strings, or genomes , (2) transform them into networks, (3) evaluate them on the task, (4) generate new, hopefully better, nets by recombining those that are most "fit", (5) goto step 2 until a solution is found. By evolving neural networks, NE can cope naturally with tasks that have continuous inputs and outputs, and, by evolving networks with feedback connections (recurrent networks), it can tackle more general tasks that require memory.

Early work in the field focused on evolving rather small networks (hundreds of weights) for RL benchmarks, and control problems with relatively few inputs/outputs. However, as RL tasks become more challenging, the networks required become larger, as do their genomes. The result is that scaling NE to large nets (i.e. tens of thousands of weights) is infeasible using a straightforward, direct encoding where genes map one-to-one to network components. Therefore, recent efforts have focused on indirect encodings [3,7,8,11,12,14] where the genome is translated into a network by a more complex mapping that allows small genomes to represent nets of potentially arbitrary size.

At IDSIA, in addition to state of the art direct methods [1,4,6,15,16], we have developed a novel indirect encoding scheme where networks are encoded by a set of Fourier coefficients which are converted into network weight matrices via an inverse Fourier-type transform [5, 9, 10, 13]. Since there often exist network solutions whose weight matrices contain regularity (i.e. adjacent weights are correlated), the number of coefficients required to represent these networks in the frequency domain is much smaller than the number of weights (in the same way that natural images can be compressed by ignore high-frequency components). This "compressed" encoding can reduce the search-space dimensionality by as much as two orders of magnitude, both accelerating convergence and yielding more general solutions.

We have also explored an entirely different approach where, instead of trying to efficiently search the space of compactly-encoded, large networks, NE is scaled by combining it with unsupervised learning (UL) [2]. Here, the standard NE architecture is augmented by a UL module that learns to transform high-dimensional inputs (e.g. video) generated by the controllers being evaluated, into a low-dimensional code that they use instead of the raw input. Because the number of inputs becomes small after the UL dimensionality reduction, the controllers can be small as well. Research is currently underway combining these two approaches (compressed nets fed by a small number UL features), to discover controllers for real robot manipulation using stereo vision input.