Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions — part 5/6
Cleaned-text code points [61829, 77468). Bibliography omitted here; source.md includes it.
While transfer is pervasive, that does not in itself prove it is essential. To demonstrate the value of transfer, a control is needed: We relaunched another three POET runs, but with all the transfers disabled (which we call POET without transfer ). In this variant, POET runs as usual, but simply never tries to transfer paired solutions from one environment to another. We can then calculate the coverage of the environments that are created and solved by POET and the control, respectively, following a similar metric as defined in Lehman and Stanley [41] : We first uniformly sample 1,000 challenging , 1,000 very challenging , and 1,000 extremely challenging environments. For each of the total 3,000 sampled environments, the distance to the nearest one of the challenging , very challenging , or extremely challenging environments created and solved by POET (and by the control, respectively) is calculated. Note that the better covered the environment space is, the lower the sum of all such nearest distances will be. The result is that the coverage of environments created and solved by POET is significantly greater than by POET without transfer ( p < 2.2 e − 16 p<2.2e{-16} based on Mann-Whitney U test), meaning POET with transfer explores more of the space of environments, including creating (and solving) more difficult environments. In an even more dramatic statistic showing the essential role of transfer in open-ended search, in POET without transfer, no extremely challenging environments are solved at all (Fig. 8 ).
Finally, one of the primary hypothesized benefits of POET is its ability to produce a broad diversity of different problems with functional solutions in a single run. The environments (depicted as red pentagons) shown in each column of Figure 5 are created and solved in a single run of POET. Each such column exhibits diversity in the values and/or value ranges in roughness, gap width of gaps, and height of stumps. Take the environments in the middle column (labelled “RUN 2”) for example. In figure 9 , each image of a section of an environment from top to bottom corresponds to the same row of rose plot for RUN 2 in Figure 5 . For instance, the topmost environment has narrow ranges and high values in gap width and stump height, and high value in roughness; in stark contrast the plot at the bottom depicts a less challenging environment with a wide range of stump heights, but low gap width and roughness. This diversity of environments also implies diverse experiences for the agents paired with them, who in turn thereby learn diverse walking gaits. This diversity then supplies the stepping stones that fuel the mutual transfer mechanism of POET. For a more objective statement of POET’s ability to cover much of the possibility space through its diversity, all three POET runs created and solved sufficiently diverse environments to cover all three challenge levels.
## 5 Discussion, Future Work, and Conclusion
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.
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.
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.
An additional constraint that exists in this initial work is that the body of the agent is fixed, ultimately limiting the sort of obstacles it can overcome (e.g. how big of a gap it can jump over). Here too a more powerful and expressive encoding of morphologies, including those like CPPNs that are based on developmental biology, could allow us to co-evolve the morphology and body of the agent along with its brain in addition to the environment it is solving. Previous research has shown that using such indirect encodings to evolve morphologies can improve performance and create a wide diversity of interesting solutions [ 73 ] . Even within the 2-D Bipedal Walker domain from this paper, research has shown that allowing the morphology to be optimized can improve performance and provide a diversity of interesting solutions [ 64 ] .
Furthermore, the CPPN indirect encoding can also encode the neural network controllers in an algorithm called HyperNEAT [ 74 ] . Work evolving robot controllers with HyperNEAT has shown it can produce neural networks with regular geometric patterns in neural connectivity that exploit regularities in the environment to produce regular behaviors that look natural and improve performance [ 75 , 76 , 76 , 77 ] . POET allows us to create the interesting combination of using an indirect encoding like a CPPN to encode the environment, the body of the agent, and the neural network controller of that agent, allowing each of the three to benefit from and exploit the regularities being produced by the others.
While ES is the base optimization algorithm in this paper for training solvers for various tasks under POET, including the main transfer mechanism, POET can be instantiated with any RL or optimization algorithm. Trust Region Policy Optimization (TRPO) [ 78 ] , Proximal Policy Optimization (PPO) [ 79 ] , genetic algorithms, other variants of ES, and many other such algorithms are all viable alternatives. This plug-and-play aspect of the overall framework presents an intriguing set of future opportunities to hybridize the divergent search across environments with the most appropriate inner-loop learning algorithms, opening up the investigation of open-endedness itself to diverse research communities.
POET could also substantially drive progress in the field of meta-learning, wherein neural networks are exposed to many different problems and get better over time at learning how to solve new challenges (i.e. they learn to learn). Meta-learning requires access to a distribution of different tasks, and that traditionally requires a human to specify this task distribution, which is costly and may not be the right or best distribution on which to learn to learn. Gupta et al. [ 80 ] note both that the performance of meta-learning algorithms critically depends on the distribution of tasks they meta-train on, and that automatically producing an effective distribution of tasks for meta-learning algorithms would represent a substantial advance. That work took an important initial step in that direction by automatically creating different reward functions within one fixed environment [ 80 ] . POET takes the important further step of creating entirely new environments (or challenges, more abstractly). While the version of POET in this initial work does not also also create a unique reward function for each environment, doing so is a natural extension that we leave for future work. One possibility is that the reward function could be encoded in addition to the rest of the environment and optimized similarly in parallel.
Another promising avenue for exploration in POET is its interaction with generalization versus specialization. Interestingly, the environments in POET themselves can foster generalization by including multiple challenges in the same sequence. However, alternate versions of POET are also conceivable that take a more explicit approach to optimizing for generality; for example, compound environments could be created whose scores are the aggregate of scores in their constituent environments (borrowing a further aspect of the CMOEA algorithm [ 45 , 46 ] ).
Finally, it is exciting to consider for the future the rich potential for surprise in all the possible domains where POET might be applied. For example, 3-D parkour was explored by Heess et al. [81] in environments created by humans, but POET could invent its own creative parkour challenges and their solutions. The soft robots evolved by Cheney et al. [73] would also be fascinating to combine with ever-unfolding new obstacle courses. POET also offers practical opportunities in domains like autonomous driving, where through generating increasingly challenging and diverse scenarios it could uncover important edge cases and policies to solve them. Perhaps more exotic opportunities could be conceived, such as protein folding for specific biological challenges invented by the system, or searching for new kinds of chemical processes that solve unique problems. The scope is broad for imagination and creativity in the application of POET.
## Acknowledgments
We thank all of the members of Uber AI Labs, in particular Joost Huizinga and Zoubin Ghahramani for helpful discussions. We also thank Alex Gajewski (from his internship at Uber AI Labs) for help with implementation and useful discussions. Finally, we thank Justin Pinkul, Mike Deats, Cody Yancey, Joel Snow, Leon Rosenshein and the entire OpusStack Team inside Uber for providing our computing platform and for technical support.
## 6 Supplemental Information
The first section in this supplement details the procedure in POET for generating and choosing new environments, which is followed by an explanation of how POET attempts to transfers agents from one environment to another.
### 6.1 Producing New Environments
New environments are produced by copying the current environments and making random changes to them (in the language of evolutionary algorithms, the environments reproduce through mutation ). Algorithm 3 formalizes the single mutation step, given a list of environment-agent pairs. The primary logic in this process is: (1) Each environment evaluates its paired agent. When the reward obtained by the agent satisfies a predefined reproduction eligibility condition for the environment (denoted as ELIGIBLE_TO_REPRODUCE()), the environment is added to the list of parent environments. (2) Once the list of eligible parents is complete, mutations of the parent environments return a list of child environments (through the function ENV_REPRODUCE()). Each child environment’s paired agent is initialized as a clone of its parent environment’s paired agent. (3) Each child environment E child ( ⋅ ) E^{\textrm{child}}(\cdot) , together with its paired agent θ child \theta^{\textrm{child}} , is checked against a predefined minimal criterion (reminiscent of the minimal criterion in the MCC algorithm [ 27 ] ) and only those satisfying the minimal criterion are kept (denoted as MC_SATISFIED()), ensuring that potential new environments are not too trivial and not too hard (which would lead to little progress). (4) All remaining child environments are then ranked based on their novelty (detailed shortly), which is calculated with respect to the current active population of environments and an archive of all previously active environments (i.e. those that were allowed to enter the population previously). (5) A transfer attempt is then performed to see whether an agent from a different environment could lead to the best performance in a new child environment. The logic of transfer is described in the next section (Section 6.2 ). Each pair is then checked against the minimal criterion again in case some pairs no longer satisfy the minimal criterion after the transfer (e.g. if an environment is exposed as too easy).
To limit the usage of computational resources, (6) POET caps the number of child environments that can be created during one iteration of POET’s main loop. The number of new environments that can be admitted is max_admitted and the maximum number of active environments at any time is capacity . If adding new environments exceeds the system’s capacity, the oldest environments and their paired agents in the system are removed to make room (also as in the MCC algorithm).
The encoding of an environment in POET is its underlying description in the system, such as a vector of numbers that specify the distribution of obstacles in an obstacle course. As mentioned in step (4) above, POET calculates the novelty of the child environments. This novelty calculation is based on the encoding. Child environments are ranked based on their novelty. For readers familiar with the novelty search algorithm [ 82 ] , it is important to note here that the encoding of an environment is in effect a genetic representation, which means that in POET in effect novelty is a genetic diversity measure. That way, POET does not in principle require a behavior characterization (BC) [ 82 ] to be devised for environments, though doing so is also not precluded.
Measuring novelty introduces an explicit pressure for diversity among the environments by encouraging newly admitted environments to have notably different encodings than those previously admitted. Given an environment E E with an encoding denoted as e ( E ) e(E) , and a list L L containing the encodings of all the environments currently in the population plus those previously admitted but no longer active (which are stored in an archive ), the novelty of E E , denoted as N ( E , L ) N(E,L) , is then computed by selecting the k-nearest neighbors of e ( E ) e(E) from L L and computing the average distance between them: N ( e ( E ) , L ) = 1 | S | ∑ j ∈ S ‖ e ( E ) − e ( E j ) ‖ 2 N(e(E),L)=\frac{1}{|{S}|}\sum_{j\in{S}}||{e(E)-e(E_{j})}||_{2}
S = kNN ( e ( E ) , L ) S=\textrm{kNN}(e(E),L)
= { e ( E 1 ) , e ( E 2 ) , … , e ( E k ) } =\{e(E_{1}),e(E_{2}),...,e(E_{k})\}
Note that in this work the distance between genetic encodings of environments is calculated with an L 2 L2 -norm and the number of nearest neighbors k k in the calculation of novelty is 5.
### 6.2 ES-Based Transfer