Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions — part 1/6

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

# Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions

###### Abstract

While the history of machine learning so far largely encompasses a series of problems posed by researchers and algorithms that learn their solutions, an important question is whether the problems themselves can be generated by the algorithm at the same time as they are being solved. Such a process would in effect build its own diverse and expanding curricula, and the solutions to problems at various stages would become stepping stones towards solving even more challenging problems later in the process. The Paired Open-Ended Trailblazer (POET) algorithm introduced in this paper does just that: it pairs the generation of environmental challenges and the optimization of agents to solve those challenges. It simultaneously explores many different paths through the space of possible problems and solutions and, critically, allows these stepping-stone solutions to transfer between problems if better, catalyzing innovation. The term open-ended signifies the intriguing potential for algorithms like POET to continue to create novel and increasingly complex capabilities without bound. We test POET in a 2-D bipedal-walking obstacle-course domain in which POET can modify the types of challenges and their difficulty. At the same time, a neural network controlling a biped walker is optimized for each environment. The results show that POET produces a diverse range of sophisticated behaviors that solve a wide range of environmental challenges, many of which cannot be solved by direct optimization alone, or even through a direct-path curriculum-building control algorithm introduced to highlight the critical role of open-endedness in solving ambitious challenges. The ability to transfer solutions from one environment to another proves essential to unlocking the full potential of the system as a whole, demonstrating the unpredictable nature of fortuitous stepping stones. We hope that POET will inspire a new push towards open-ended discovery across many domains, where algorithms like POET can blaze a trail through their interesting possible manifestations and solutions.

## 1 Introduction

Machine learning algorithms are often understood as tools for solving difficult problems. Challenges like image classification and associated benchmarks like ImageNet [ 1 ] are chosen by people in the community as solvable and researchers focus on them to invent ever-more high-performing algorithms. For example, ImageNet was proposed in 2009 and modern deep neural networks such as ResNet [ 2 ] began to beat humans in 2015 [ 3 , 4 ] . In reinforcement learning (RL) [ 5 ] , learning to play Atari was proposed in 2013 [ 6 ] and in recent years deep reinforcement learning (RL) algorithms reached and surpassed human play across a wide variety of Atari games [ 7 , 8 , 9 , 10 , 11 , 12 ] . The ancient game of Go has been a challenge in AI for decades, and has been the subject of much recent research: AlphaGo and its variants can now reliably beat the world’s best human professional Go players [ 13 , 14 , 15 ] . Each such achievement represents the pinnacle of a long march of increasing performance and sophistication aimed at solving the problem at hand.

As compelling as this narrative may be, it is not the only conceivable path forward. While the story so far relates a series of challenges that are conceived and conquered by the community algorithm by algorithm, in a more exotic alternative only rarely discussed (e.g. [ 16 , 17 ] ), the job of the algorithm could be to conceive both the challenges and the solutions at the same time. Such a process offers the novel possibility that the march of progress, guided so far by a sequence of problems conceived by humans, could lead itself forward, pushing the boundaries of performance autonomously and indefinitely. In effect, such an algorithm could continually invent new environments that pose novel problems just hard enough to challenge current capabilities, but not so hard that all gradient is lost. The environments need not arrive in a strict sequence either; they can be invented in parallel and asynchronously, in an ever-expanding tree of diverse challenges and their solutions.

We might want such an open-ended [ 18 , 19 , 20 , 21 , 22 ] process because the chain that leads from the capabilities of machine learning today to e.g. general human-level intelligence could stretch across vast and inconceivable paths of stepping stones. There are so many directions we could go, and so many problems we could tackle, that the curriculum that leads from here to the farthest reaches of AI is beyond the scope of our present imagination. Why then should we not explore algorithms that self-generate their own such curricula? If we could develop and refine such algorithms, we might find a new approach to progress that relies less upon our own intuitions about the right stepping stones and more upon the power of automation.

In fact, the only process ever actually to achieve intelligence at the human level, natural evolution, is just such a self-contained and open-ended curriculum-generating process. Both the problems of life, such as reaching and eating the leaves of trees for nutrition, and the solutions, such as giraffes, are the products of the same open-ended process. And this process unfolds not as a single linear progression, but rather involves innumerable parallel and interacting branches radiating for more than a billion years (and is still going). Nature is also a compelling inspiration because it has avoided convergence or stagnation, and continues to produce novel artifacts for beyond those billion years. An intriguing question is whether it is possible to conceive an algorithm whose results would be worth waiting a billion years to see. Open-ended algorithms in their most grandiose realization would offer this possibility.

While a small community within the field of artificial life [ 18 , 19 , 23 , 24 , 25 , 26 , 27 , 21 , 28 , 22 ] has studied the prospects of open-ended computation for many years, in machine learning the prevailing assumption that algorithms should be directed (e.g. towards the performance objective) has pervaded the development of algorithms and their evaluation for many years. Yet this explicitly directed paradigm has begun to soften in recent years. Researchers have begun to recognize that modern learning algorithms’ hunger for data presents a long-term problem: the data available for progress diminishes as the appropriate tasks for leveling up AI competencies increase in complexity. This recognition is reflected in systems based on self-play (which is related to coevolution [ 29 , 30 , 31 ] ), such as competitive two-player RL competitions [ 32 , 14 ] wherein the task is a function of the competition, which is itself changing over time. Generative adversarial networks (GANs) [ 33 ] , in which networks interact as adversaries, similarly harness a flavor of self-play and coevolution [ 34 ] to generate both challenges and solutions to those challenges.

While not explicitly motivated by open-endedness, recognition of the importance of self-generated curricula is also reflected in recent advances in automatic curriculum learning for RL, where the intermediate goals of curricula are automatically generated and selected. A number of such approaches to automatic curriculum building have been proposed. For example, the curriculum can be produced by a generator network optimized using adversarial training to produce tasks at the appropriate level of difficulty for the agent [ 35 ] , by applying noise in action space to generate a set of feasible start states increasingly far from the goal (i.e. a reverse curriculum) [ 36 ] , or through intrinsically motivated goal exploration processes (IMGEPs) [ 16 ] . The POWERPLAY algorithm offers an alternative approach to formulating continual, concurrent searches for new tasks through an increasingly general problem solver [ 17 ] . In Teacher-Student Curriculum Learning [ 37 ] , the teacher automatically selects sub-tasks that offer the highest slope of learning curve for the student. Ideas from the field of procedural content generation (PCG) [ 38 , 39 ] , where methods are developed to generate diverse sets of levels and other contents for games, can also generate progressive curricula that help improve generality of deep RL agents [ 40 ] .

The ultimate implication of this shift towards less explicitly-directed processes is to tackle the full grand challenge of open-endedness: Can we ignite a process that on its own unboundedly produces increasingly diverse and complex challenges at the same time as solving them? And, assuming computation is sufficient, can it last (in principle) forever?

The paired open-ended trailblazer (POET) algorithm introduced in this paper aims to confront open-endedness directly, by evolving a set of diverse and increasingly complex environmental challenges at the same time as collectively optimizing their solutions. A key opportunity afforded by this approach is to attempt transfers among different environments. That is, the solution to one environment might be a stepping stone to a new level of performance in another, which reflects our uncertainty about the stepping stones that trace the ideal curriculum to any given skill. By radiating many paths of increasing challenge simultaneously, a vast array of potential stepping stones emerges from which progress in any direction might originate. POET owes its inspiration to recent algorithms such a minimal criterion coevolution (MCC) [ 27 ] , which shows that environments and solutions can effectively co-evolve, novelty search with local competition [ 41 ] , MAP-Elites [ 42 , 43 ] , Innovation Engines [ 44 ] , which exploit the opportunity to transfer high-quality solutions from one objective among many to another, and the combinatorial multi-objective evolutionary algorithm (CMOEA), which extends the Innovation Engine to combinatorial tasks [ 45 , 46 ] . POET in effect combines the ideas from all of these approaches to yield a new kind of open-ended algorithm that optimizes, complexifies, and diversifies as long as the environment space and available computation will allow.

In this initial introduction of POET, it is evaluated in a simple 2-D bipedal walking obstacle-course domain in which the form of the terrain is evolvable, from a simple flat surface to heterogeneous environments of gaps, stumps and rough terrain. The results establish that (1) solutions found by POET for challenging environments cannot be found directly on those same environmental challenges by optimizing on them only from scratch; (2) neither can they be found through a curriculum-based process aimed at gradually building up to the same challenges POET invented and solved; (3) periodic transfer attempts of solutions from some environments to others–also known as “goal switching” [ 44 ] –is important for POET’s success; (4) a diversity of challenging environments are both invented and solved in the same single run. While the 2-D domain in this paper offers an initial hint at the potential of the approach for achieving open-ended discovery in a single run, it will be exciting to observe its application to more ambitious problem spaces in the future.

The paper begins with background on precedent for open-endedness and POET, turning next to the main algorithmic approach. It finally introduces the 2-D obstacle-course domain and presents both qualitative an quantitative results.

## 2 Background

This section first reviews several approaches that inform the idea behind POET of tracking and storing stepping stones, which is common in evolutionary approaches to behavioral diversity. It then considers a recently proposed open-ended coevolutionary framework based on the concept of minimal criteria and, lastly, evolution strategies (ES) [ 47 ] , which serves as the optimization engine behind POET in this paper (though in principle other reinforcement learning algorithms could be substituted in the future).

### 2.1 Behavioral Diversity and Stepping Stones

A common problem of many stochastic optimization and search algorithms is becoming trapped on local optima, which prevents the search process from leaving sub-optimal points and reaching better ones. In the context of an open-ended search, becoming trapped is possible in more than one way: In one type of failure, the domains or problems evolving over the course of search could stop increasing their complexity and thereby stop becoming increasingly interesting. Alternatively, the simultaneously-optimizing solutions could be stuck at sub-optimal levels and fail to solve challenges that are solvable. Either scenario can cause the search to stagnate, undermining its open-endedness.

Population-based algorithms going back to novelty search [ 48 ] that encourage behavioral (as opposed to genetic) diversity [ 43 , 42 , 49 , 45 , 44 , 46 ] have proven less susceptible to local optima, and thus naturally align more closely with the idea of open-endedness as they focus on divergence instead of convergence . These algorithms are based on the observation that the path to a more desirable or innovative solution often involves a series of waypoints, or stepping stones , that may not increasingly resemble the final solution, and are not known ahead of time. Therefore, divergent algorithms reward and preserve diverse behaviors to facilitate the preservation of potential stepping stones, which could pave the way to both a solution to a particular problem of interest and to genuinely open-ended search.

In the canonical example of novelty search (NS) [ 48 ] , individuals are selected purely based on how different their behaviors are compared to an archive of individuals from previous generations. In NS, the individuals in the archive determine the novelty of a solution, reflecting the assumption that genuinely novel discoveries are often stepping stones to further novel discoveries. Sometimes, a chain of novel stepping stones even reaches a solution to a problem, even though it was never an explicit objective of the search. NS was first shown effective in learning to navigate deceptive mazes and biped locomotion problems [ 48 ] .

Other algorithms are designed to generate, retain, and utilize stepping stones more explicitly. To retain as much diversity as possible, quality diversity (QD) algorithms [ 41 , 43 , 42 , 49 ] keep track of many different niches of solutions that are (unlike pure NS) being optimized simultaneously and in effect try to discover stepping stones by periodically testing the performance of offspring from one niche in other niches, a process referred to as goal switching [ 44 ] .