Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions — part 2/6
Cleaned-text code points [14869, 30645). Bibliography omitted here; source.md includes it.
Based on this idea, an approach called the Innovation Engine [ 44 ] is able to evolve a wide range of images in a single run that are recognized with high-confidence as different image classes by a high-performing deep neural network trained on ImageNet [ 50 ] . In this domain, the Innovation Engine maintains separate niches for images of each class, including the image that performed the best in that class (i.e. produced the highest activation value according to the trained deep neural network classifier). It then generates variants (perturbations/offspring) of a current niche champion and not only checks whether such offspring are higher-performing in that niche (class), but also checks whether they are higher-performing in any other niche. Interestingly, the evolutionary path to performing well in a particular class often passes through other (oftentimes seemingly unrelated) classes that ultimately serve as stepping stones to recognizable objects. In fact, it is necessary for the search to pass through these intermediate, seemingly unrelated stages to ultimately satisfy other classes later in the run [ 44 ] . More recently, to evolve multimodal robot behaviors, the Combinatorial Multi-Objective Evolutionary Algorithm (CMOEA) [ 45 , 46 ] builds on the Innovation Engine, but defines its niches based on different combinations of subtasks . This idea helps it to solve both a multimodal robotics problem with six subtasks as well as a maze navigation problem with a hundred subtasks, highlighting the advantage of maintaining a diversity of pathways and stepping stones through the search space when a metric for rewarding the most promising path is not known. POET will similarly harness goal-switching within divergent search.
While the general ideas of promoting diversity and preserving stepping stones grew up initially within the field of evolutionary computation, they are nevertheless generic and applicable in fields such as deep reinforcement learning (RL). For example, a recent work utilizes diversity maximization to acquire complex skills with minimal supervision, which improves learning efficiency when there is no reward function. The results then become the foundation for imitation learning and hierarchical RL [ 51 ] . To address the problem of reward sparsity, Savinov et al. [52] extend the archive-based mechanism from NS that determines novelty in behaviors to determine novelty in the observation space and then to formulate the novelty bonus as an auxiliary reward. Most recently, the Go-Explore algorithm by Ecoffet et al. [ 12 ] represents a new twist on QD algorithms and is designed to handle extremely sparse and/or deceptive “hard exploration” problems in RL. It produced dramatic improvements over the previous state of the art on the notoriously challenging hard-exploration domains of Montezuma’s Revenge and Pitfall. Go-Explore maintains an archive of interestingly different stepping stones (e.g. states of a game) that have been reached so far and how to reach them. It then returns to and explores from these stepping stones to find new stepping stones, and repeats the process until a sufficiently high-quality solution is found.
### 2.2 Open-Ended Search via Minimal Criterion Coevolution (MCC)
Despite the recent progress of diversity-promoting algorithms such as NS and QD, they remain far from matching a genuinely open-ended search in the spirit of nature. One challenge in such algorithms is that although they provide pressure for ongoing divergence in the solution space, the environment itself remains static, limiting the scope of what can be found in the long run. In this spirit, one fundamental force for driving open-endedness could come from coevolution [ 31 ] , which means that different individuals in a population interact with each other while they are evolving. Such multi-agent interactions have recently proven important and beneficial for systems with coevolutionary-like dynamics such as generative adversarial networks (GANs) [ 33 ] , self-play learning in board games [ 14 ] , and competitions between reinforcement-learning robots [ 32 ] . Because the environment in such systems now contains other changing agents, the challenges are no longer static and evolve in entanglement with the solutions.
However, in most, if not all, coevolutionary systems, the abiotic (non-opponent-based) aspect of the environment remains fixed. No amount of co-evolution with a fixed task (e.g. pushing the other enemy off a pedestal, or beating them at Go) will produce general artificial intelligence that can write poetry, engage in philosophy, and invent math. Thus an important insight is that environments themselves (including ultimately the reward function) must too change to drive truly open-ended dynamics. Following this principle, an important predecessor to the POET algorithm in this paper is the recent minimal criterion coevolution (MCC) algorithm [ 27 ] , which explores an alternative paradigm for open-endedness through coevolution. In particular, it implements a novel coevolutionary framework that pairs a population of evolving problems (i.e. environmental challenges) with a co-evolving population of solutions . That enables new problems to evolve from existing ones and for new kinds of solutions to branch from existing solutions. As problems and solutions proliferate and diverge in this ongoing coupled interaction, the potential for open-endedness arises.
Unlike conventional coevolutionary algorithms that are usually divided between competitive coevolution, where individuals are rewarded according to their performance against other individuals in a competition [ 29 ] , and cooperative coevolution, where instead fitness is a measure of how well an individual performs in a cooperative team with other evolving individuals [ 30 ] , MCC introduce a new kind of coevolution that evolves two interlocking populations whose members earn the right to reproduce by satisfying a minimal criterion [ 25 , 26 , 53 ] with respect to the other population, as both populations are gradually shifting simultaneously. For example, in an example in Brant and Stanley [27] with mazes (the problems) and maze solvers (the solutions, represented by neural networks), the minimal criterion for the solvers is that they must solve at least one of the mazes in the maze population, and the minimal criterion for the mazes is to be solved by at least one solver.
The result is that the mazes increase in complexity and the neural networks continually evolve to solve them. In a single run without any behavior characterization or archive (which are usually needed in QD algorithms), MCC can continually generate novel, diverse and increasingly complex mazes and maze solvers as new mazes provide new opportunities for innovation to the maze solvers (and vice versa), hinting at open-endedness. However, in MCC there is no force for optimization within each environment (or maze in the example experiment). That is, once a maze is solved there is no pressure to improve its solution; instead, it simply becomes a potential stepping stone to a solution to another maze. As a result, while niches and solutions proliferate, there is no pressure for mastery within each niche, so we do not see the best that is possible. Additionally, in MCC problems have to be solvable by the current population, so complexity can only arise through drift. As an example, imagine an environmental challenge E ′ E^{\prime} that is similar to a currently solved problem E E , but a bit harder such that none of the current agents in the population can solve it. Further imagine that if we took some of the current agents (e.g. the agent that solves E E ) and optimized them to solve E ′ E^{\prime} , at least one agent could learn to solve E ′ E^{\prime} in a reasonable amount of time. MCC would still reject and delete E ′ E^{\prime} if it was generated because none of the current population solves it right away. In contrast, in POET, we accept problems if (according to some heuristics) they seem likely to be improved upon and/or solved after some amount of dedicated optimization effort (so POET will likely keep E ′ E^{\prime} ), enabling a more direct and likely swifter path to increasingly complex, yet solvable challenges.
### 2.3 Evolution Strategies (ES)
In the POET implementation in this paper, ES plays the role of the optimizer (although other optimization algorithms should also work). Inspired by natural evolution, ES [ 54 ] represents a broad class of population-based optimization algorithms. The method referred to here and subsequently as “ES” is a version of ES popularized by Salimans et al. [47] that was recently applied with large-scale deep learning architectures to modern RL benchmark problems. This version of ES draws inspiration from Section 6 of Williams [55] (i.e. REINFORCE with multiparameter distributions), as well as from subsequent population-based optimization methods including Natural Evolution Strategies (NES) [ 56 ] and Parameter-Exploring Policy Gradients (PEPG) [ 57 ] . More recent investigations have revealed the relationship of ES to finite difference gradient approximation [ 58 ] and stochastic gradient descent [ 59 ] .
In the typical context of RL, we have an environment, denoted as E ( ⋅ ) E(\cdot) , and an agent under a parameterized policy whose parameter vector is denoted as w w . The agent tries to maximize its reward, denoted as E ( w ) E(w) , as it interacts with the environment. In ES, E ( w ) E(w) represents the stochastic reward experienced over a full episode of an agent interacting with the environment. Instead of directly optimizing w w to maximize E ( w ) E(w) , ES seeks to maximize the expected fitness over a population of w w , J ( θ ) = 𝔼 w ∼ p θ ( w ) [ E ( w ) ] J(\theta)=\mathbb{E}_{w\sim p_{\theta}(w)}[E(w)] , where w w is sampled from a probability distribution p θ ( w ) p_{\theta}(w) parameterized by θ \theta . Using the log-likelihood trick [ 55 ] and estimating the expectation above over n n samples allows us to write the gradient of J ( θ ) J(\theta) with respect to θ \theta as: ∇ θ J ( θ ) ≈ 1 n ∑ i = 1 n E ( θ i ) ∇ θ log p θ ( θ i ) . \nabla_{\theta}J(\theta)\approx\frac{1}{n}\sum_{i=1}^{n}E(\theta_{i})\nabla_{\theta}\log p_{\theta}(\theta_{i}).
Intuitively, this equation says that for every sample agent θ i \theta_{i} , the higher the performance of that agent E ( θ i ) E(\theta_{i}) , the more we should move θ \theta in the direction of the gradient that increases the likelihood of sampling that agent, which is ∇ θ log p θ ( θ i ) \nabla_{\theta}\log p_{\theta}(\theta_{i}) . Following the convention in Salimans et al. [47] , θ i , i = 1 , … , n , \theta_{i},i=1,\ldots,n, are n n samples of parameter vectors drawn from an isotropic multivariate Gaussian with mean θ \theta and a covariance σ 2 , \sigma^{2}, namely, 𝒩 ( θ , σ 2 I ) \mathcal{N}(\theta,\,\sigma^{2}I) . (The covariance can be fixed or adjusted over time depending on the implementation.) Note that θ i \theta_{i} can be equivalently obtained by applying additive Gaussian noise ϵ i ∼ 𝒩 ( 0 , I ) \epsilon_{i}\sim\mathcal{N}(0,\,I) to a given parameter vector θ \theta as θ i = θ + σ ϵ i \theta_{i}=\theta+\sigma\epsilon_{i} . With that notation, the above estimation of the gradient of J ( θ ) J(\theta) with respect to θ \theta can be written as: ∇ θ J ( θ ) ≈ 1 n σ ∑ i = 1 n E ( θ + σ ϵ i ) ϵ i . \nabla_{\theta}J(\theta)\approx\frac{1}{n\sigma}\sum_{i=1}^{n}E(\theta+\sigma\epsilon_{i})\epsilon_{i}.
Algorithm 1 illustrates the calculation of one optimization step of ES, which can efficiently be parallelized over distributed workers [ 47 ] . Once calculated, the returned optimization step is added to the current parameter vector to obtain the next parameter vector. Note that implementations of ES including our own usually follow the approach of Salimans et al. [47] and rank-normalize E ( θ + σ ϵ i ) E(\theta+\sigma\epsilon_{i}) before taking the weighted sum, which is a variance reduction technique. Overall, ES has exhibited performance on par with some of the traditional, simple gradient-based RL algorithms on difficult RL domains (e.g. DQN [ 7 ] and A3C [ 60 ] ), including Atari environments and simulated robot locomotion [ 47 , 61 ] . More recently, NS and QD algorithms have been shown possible to hybridize with ES to further improve its performance on sparse or deceptive deep RL tasks, while retaining scalability [ 61 ] , providing inspiration for its novel hybridization within an CMOEA- and MCC-like algorithm in this paper.
## 3 The Paired Open-Ended Trailblazer (POET) Algorithm
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 environment-agent pairs EA_List that begins with a single starting pair ( E init ( ⋅ ) , θ init ) (E^{\textrm{init}}(\cdot),\theta^{\textrm{init}}) , where E init E^{\textrm{init}} is a simple environment (e.g. an obstacle course of entirely flat ground) and θ init \theta^{\textrm{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 ( ⋅ ) E(\cdot) from those currently active,
2. optimizing paired agents within their respective environments, and
3. attempting to transfer current agents θ \theta 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.