AI-GAs: AI-generating algorithms, an alternate paradigm for producing general artificial intelligence — part 4/8

Cleaned-text code points [46730, 61155). Bibliography omitted here; source.md includes it.

A second approach, which I believe is more likely to work for ambitious purposes like producing general AI, is to pursue open-ended search algorithms, meaning algorithms that endlessly generate new things [ 172 ] . In the AI-GA context, that would mean algorithms that endlessly generate an expanding set of challenging environments and solutions to each of those challenges. The expectation is that eventually general AI will emerge as a solution to one or a set of the generated environments. I call this the open-ended approach to creating effective learning environments. This path is what occurred on Earth. Natural evolution did not start out with the goal of producing general intelligence. Instead, a remarkably simple algorithm (Darwinian evolution) began producing solutions to relatively simple environments. The ‘solutions’ to those environments were organisms that could survive in them. Those organism often created new niches (i.e. environments, or opportunities) that could be exploited. For example, the existence of gazelles creates a niche for cheetahs, which in turn creates a niche for microorganisms that live inside of cheetahs, etc. The existence of trees enables vines, epiphytes, and canopy butterflies, each of which creates niches for other organisms. The result is an ever-expanding, open-ended collection of new niches (challenges) and solutions to those niches (agents with a variety of skills). Ultimately, that process produced all of the engineering marvels on the planet, such as jaguars, hawks, and the human mind. Note that this approach avoids the need to create a definition and measurement of general AI. It allows us to rely on the fact that we will know it when we see it.

What happened in natural evolution was extremely computationally expensive. The AI-GA paradigm motivates research into the following question: can we create computational systems that efficiently abstract the key ingredients that produce complexity explosions like those produced by evolution on earth? If so, we may be able to create algorithms that effectively endlessly innovate and could ultimately produce general AI. In other words, the goal is to create an AI-GA without requiring a planet-sized computer.

We of course do not know all of the key ingredients that made natural evolution so effective, nor do we know the best way to abstract them. However, we have made progress in identifying some of these key ingredients and how to abstract them. I will attempt to briefly summarize the work I consider promising in this direction.

#### 2.3.1 Encouraging behavioral diversity

An essential ingredient in the complexity explosion that occurred on earth is the creation of a diverse set of niches and organisms that can live in those niches. An abstract property that will almost certainly be key is thus diversity. For decades, researchers have known that diversity can help search algorithms get off of local optima. But the vast majority of approaches have encouraged diversity in the original search space, such as the weights of a neural network that controls a robot. Such search spaces are high-dimensional and often diversity in the weights of neural networks is not interesting diversity. For example, there are a near infinite number of weight vectors that can make a robot immediately fall over. A key insight came when Lehman and Stanley [92] emphasized the importance of encouraging behavioral diversity . The idea is to define a behavior space in which diversity is interesting, and then search for neural network weight vectors that produce different behaviors in that space. For example, imagine a simulation of the city of San Francisco. We might want to encourage a search algorithm to produce robots that visit not-yet-visited x , y , z x,y,z locations in San Francisco. Visiting new x , y , z x,y,z locations would require learning skills like walking, avoiding obstacles, climbing stairs, taking elevators, opening doors, crossing streets, climbing trees, picking locks, etc. In fact, Lehman and Stanley [92] showed that searching for novelty only (and completely ignoring the reward function), a algorithm they call Novelty Search , can solve problems that are not solvable with objective-driven search when local optima are present. We subsequently showed that novelty search does in fact learn general skills for how to move about an environment that can transfer to new environments [ 186 ] . In an algorithm called Curiosity Search [ 173 ] , we later showed that encouraging an agent to visit as many different locations within its lifetime (i.e. within an episode) as possible improved performance on the Atari game Montezuma’s Revenge, a notoriously difficult, sparse, hard-exploration problem, matching the then state of the art [ 174 ] . There have been many other important recent papers investigating how much agents can learn when motivated by curiosity alone [ 19 , 128 , 126 , 147 , 42 , 56 , 127 , 150 ] .

While fascinating, rewarding novelty alone is unlikely to reproduce the complexity explosion that occurred on Earth. One missing ingredient is that on Earth, while the creation of niches creates new environments (which indirectly create a pressure to produce diverse behaviors), within each niche there is a pressure to be high-performing. Such intra-niche competition is the most common way people think of ‘survival of the fittest’, wherein faster cheetahs replace slower ones, stronger elephant seals outcompete weaker rivals for control of the harem, etc. The most straightforward way to combine a pressure for novel behaviors and high performance is to optimize for both of them. Many have shown such a combination is effective, whether in a weighted combination of novelty and reward [ 30 ] , multi-objective algorithms [ 115 , 117 ] , or algorithms that intelligently rebalance between novelty and performance as a function of learning progress [ 30 ] . However, while the novelty pressure helps avoid local optima, such algorithms still tend to produce one or a few variations on the single theme that search converges on. They do not produce a wide variety of different, yet high-quality solutions.

#### 2.3.2 Quality Diversity algorithms

Ultimately, what we want are algorithms that create a diverse set of solutions where each of those solutions is as high-performing as possible for that type. For that reason, my colleagues and I have created a new family of search algorithms called Quality Diversity (QD) algorithms . The first of its kind was Novelty Search with Local Competition [ 93 ] followed by MAP-Elites [ 116 ] . The general idea is to define (or learn) a low-dimensional behavioral (or phenotypic) space and then explicitly search for the highest-performing solution in each region of that space. For example, if one was searching in the space of weights of a deep neural network that encodes the morphology of a robot body, the performance criterion might be walking speed and the space we want to encourage diversity in could be the height and weight of the robot. The QD algorithm would thus search for and return the fastest tall, skinny robot, the fastest tall, fat robot, the fasted short, skinny robot, etc.

QD algorithms have already been harnessed to solve very difficult machine learning problems. For example, in a paper in Nature [ 32 ] , we harnessed QD to obtain state-of-the-art robot damage recovery, wherein a robot can adapt to substantial damage in 1-2 minutes. We also showed that with access to a deterministic simulator for training, an enhanced version MAP-Elites called Go-Explore can solve the hard-exploration benchmark challenges of the Atari games Montezuma’s Revenge and Pitfall, dramatically improving the state of the art [ 38 ] .

One essential component of QD algorithms that fuels their success is goal switching [ 123 ] . The idea is that within a niche a parameter vector is optimized to perform well, but if at any point it turns out that a perturbed version of that parameter vector belongs to another niche and is better than its current champion, that perturbed parameter vector becomes the elite in the other niche. That enables one style of solutions in a niche (which may be stuck on a local optima) to be disrupted by another type of solution that was discovered via optimization on a different niche. This captures a dynamic similar to scientific and technological innovation (e.g. how microwaves invaded the kitchen niche despite their underlying technology being developed for radar, a very different purpose). It also captures the dynamic of natural evolution where a species optimized for one niche can invade a new niche if it is superior. Research has shown that such goal switching significantly improves the performance of QD algorithms [ 123 , 116 , 70 ] . For example, we showed how it can enable the creation and combination of different skills to produce multi-modal robots capable of jumping, crouching, running, and turning [ 70 ] .

QD algorithms can be used in many types of problem domains, such as solving different types of mathematical, writing, or musical challenges. For example, in our work on Innovation Engines [ 123 ] , we showed that the same ideas underlying QD algorithms could be used to generate different types of high-quality, recognizable images. Goal-switching proved essential to avoid local optima and was a catalyst for innovation. We also observed in that work another hallmark of biological complexity explosions: adaptive radiation. Innovations in one niche rapidly spread to many other niches, allowing key innovations to spread and become the foundation upon which additional innovations specific to different niches are built. This phenomenon is reminiscent of the Cambrian Explosion, wherein the innovation of the four-legged body plan led to a rapid radiation of that motif into a large number of different niches to ultimately produce all of the diverse four-legged creatures on Earth.

Another benefit of the goal-switching in QD algorithms is the creation of better underlying representations for search. If a structure is repeatedly optimized (or selected) to move in some dimensions and not others, it can restructure itself to make traversing the preferred dimensions of variation more likely than traversing non-preferred dimensions. In the literature of biological and computational evolution, this phenomenon is called evolvability [ 85 , 86 , 190 , 29 , 130 , 189 , 110 ] . Lehman and Stanley [92] showed that Novelty Search produces more evolvability than objective-based search. The reason is intuitive. With objective-based search, the optimization algorithm myopically adds any hack to the representation that improves performance. Like technological debt in software engineering, adding hacks upon hacks without paying the cost of refactoring (which temporarily makes things worse before they ultimately get much better) leads to code that is difficult to adapt to new use cases. In contrast, Novelty Search encourages the production of new behaviors, and thus perturbations that make major changes are less likely to be immediately rejected [ 94 ] . Specifically, Lehman and Stanley showed that neural networks subjected to novelty search were more compact than objective-based search [ 92 , 95 ] , in favor of the hypothesis that they are more evolvable. Novelty search was also shown to lead to representations that produce more behavioral diversity when perturbed, a measure of evolvability [ 95 ] . However, we found they were not faster in adapting to a new tasks [ 186 ] , which is contrary to this hypothesis, although more research needs to be done on this question. Additionally, we discovered that when something similar to a neural network encodes pictures and these networks are subject to constantly changing, human-defined goals, the resulting representations are significantly smaller (a proxy for evolvability), more modular, and more hierarchical [ 71 ] . Moreover, we found they are much more likely to produce sensible variations than nonsensical ones, and do so in a hierarchical way. For example, an image of a face might be changed to enlarge or shrink the entire face, or both eyes, or just one eye. Or a smile could be easily converted into a frown, etc. Less likely were changes that transformed a face into an eagle or a scrambled mess of pixels. When automatically generating images with Innovation Engines, we also found that goal-switching led to significantly more compact, adaptable representations [ 123 ] .

#### 2.3.3 Environment-generating quality-diversity algorithms

QD algorithms as originally conceived could create a high-quality set of diverse behaviors within a single, pre-defined environment only. However, for AI-GA’s Third Pillar we need to generate different types of environments and their solutions. That desire motived our recent Paired Open-Ended Trailblazer (POET) algorithm [ 192 ] . In it, a parameter vector θ E \theta_{E} specifies an environment. In our demonstration domain, the environments were obstacle courses that could have different degrees of being hilly, gaps in the ground of varying width, and tree trunks of varying height. An additional parameter vector θ A \theta_{A} contains the weights of a DNN that controls an agent, which in this case is a robot that has to traverse the obstacle course as quickly as possible. An initial agent θ A 1 \theta_{A^{1}} is optimized to solve the initial, simple environment θ E 1 \theta_{E^{1}} . Once the performance of θ A 1 \theta_{A^{1}} is good enough, we copy θ E 1 \theta_{E^{1}} and change it slightly to create θ E 2 \theta_{E^{2}} , which now represents a different environment. A copy of θ A 1 \theta_{A^{1}} is made to create θ A 2 \theta_{A^{2}} , which is then optimized to solve the new environment θ E 2 \theta_{E^{2}} . Importantly, optimization of θ A 1 \theta_{A^{1}} on θ E 1 \theta_{E^{1}} continues in parallel. Over time, environments are periodically generated by copying any of the current environments for which its agent performs above some threshold. All or a subset of the current agents are evaluated on each new environment. Environments are kept only if they are not too hard for all of the agents in the population, or are not too easy for any of the agents. A copy of the highest-performing agent is transferred to the new environment, where it begins optimizing to try solve it.