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

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.

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–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–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–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, 21–28] 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–31]), such as competitive two-player RL competitions [14, 32] 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.

Related work. 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 [42–46, 49] 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, 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].

Method. POET is designed to facilitate an open-ended process of discovery within a single run. It maintains a population of environments (for example, various obstacle courses) and a population of agents (for example, neural networks that control a robot to solve those courses), and each environment is paired with an agent to form an environment-agent pair. POET in effect implements an ongoing divergent coevolutionary interaction among all its agents and environments in the spirit of MCC [27], but with the added goal of explicitly optimizing the behavior of each agent within its paired environment in the spirit of CMOEA [45, 46]. It also elaborates on the minimal criterion in MCC by aiming to maintain only those newly-generated environments that are not too hard and not too easy for the current population of agents. The result is a trailblazer algorithm, one that continually forges new paths to both increasing challenges and skills within a single run. The new challenges are embodied by the new environments that are continually created, and the increasing skills are embodied by the neural network controllers attempting to solve each environment. Existing skills are harnessed both by optimizing agents paired with environments and by attempting to transfer current agent behaviors to new environments to identify promising stepping stones.

The fundamental algorithm of POET is simple: The idea is to maintain a list of active environmentagent pairs EA_List that begins with a single starting pair (Einit(·), θinit), where Einit is a simple environment (e.g. an obstacle course of entirely flat ground) and θinit is a randomly initialized weight vector (e.g. for a neural network). POET then has three main tasks that it performs at each iteration of its main loop:

1. generating new environments E(·) from those currently active, 2. optimizing paired agents within their respective environments, and 3. attempting to transfer current agents θ from one environment to another.

Generating new environments is how POET continues to produce new challenges. To generate a new environment, POET simply mutates (i.e. randomly perturbs) the encoding (i.e. the parameter vector) of an active environment. However, while it is easy to generate perturbations of existing environments, the delicate part is to ensure both that (1) the paired agents in the originating (parent) environments have exhibited sufficient progress to suggest that reproducing their respective environments would not be a waste of effort, and (2) when new environments are generated, they are not added to the current population of environments unless they are neither too hard nor too easy for the current population. Furthermore, priority is given to those candidate environments that are most novel, which produces a force for diversification that encourages many different kinds of problems to be solved in a single run.

These checks together ensure that the curriculum that emerges from adding new environments is smooth and calibrated to the learning agents. In this way, when new environments do make it into the active population, they are genuinely stepping stones for continued progress and divergence. The population of active environments is capped at a maximum size, and when the size of the population exceeds that threshold, the oldest environments are removed to make room (as in a queue). That way, environments do not disappear until absolutely necessary, giving their paired agents time to optimize and allowing skills learned in them to transfer to other environments.

POET optimizes its paired agents at each iteration of the main loop. The idea is that every agent in POET should be continually improving within its paired environment. In the experiments in this paper, each such iteration is a step of ES, but any reinforcement learning algorithm could conceivably apply. The objective in the optimization step is simply to maximize whatever performance measure applies to the environment (e.g. to walk as far as possible through an obstacle course).

Discussion. The promise of open-ended computation is fascinating for its potential to enable systems that become more powerful and interesting the longer they run. There is always the possibility that the feats we observe in the system today will be overshadowed by the achievements of tomorrow. In these unfolding odysseys there is an echo of the natural world. More than just the story of a single intelligent lifetime, they evoke the history of invention, or of natural evolution over the eons of Earth. These are processes that produce not just a single positive result, but an ongoing cacophony of surprises – unplanned advances rolling ahead in parallel without any final destination.

Conclusion. POET is an attempt to move further down the road towards these kinds of systems. While the road remains long, the rewards for machine learning of beginning to capture the character of open-ended processes is potentially high. First, as the results show, there is the opportunity to discover capabilities that could not be learned in any other way, even through a carefully crafted curriculum targeted at the desired result. In addition, a diversity of such results can be generated in a single run, and the problems and solutions can both increase in complexity over time. Furthermore, the implicit result is that POET is self-generating multiple curricula simultaneously, all while leveraging the results of some as stepping stones to progress in others.

Limitations. The experiment in this article in 2-D walking establishes the potential of POET, but POET becomes more interesting the more unbounded its problem space becomes. The present problem space is a 2-D course of obstacles that can be generated within distributions defined by the genome describing the environment. This space is limited by the maximal ranges of those distributions. For example, there is a maximum possible gap width and stump height, which means that the system in effect can eventually “max out” the difficulty. While sufficiently broad to demonstrate POET’s functionality, in the future much more flexible or even unbounded encodings can enable POET to traverse a far richer problem space. For example, an indirect encoding like a compositional pattern-producing network (CPPN) [72] can generate arbitrarily complex patterns that can be e.g. converted into levels or obstacle courses. Such an encoding would allow POET to diverge across a much richer landscape of possibilities.