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

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

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). The fact that each agent-environment pair is being optimized independently affords easy parallelization, wherein all the optimization steps can in principle be executed at the same time.

Finally, attempting transfer is the ingredient that facilitates serendipitous cross-pollination: it is always possible that progress in one environment could end up helping in another. For example, if the paired agent θ A \theta^{A} in environment E A ​ ( ⋅ ) E^{A}(\cdot) is stuck in a local optimum, one remedy could be a transfer from the paired agent θ B \theta^{B} in environment E B ​ ( ⋅ ) E^{B}(\cdot) . If the skills learned in the latter environment apply, it could revolutionize the behavior in the former, reflecting the fact that the most promising stepping stone to the best possible outcome may not be the current top performer in that environment [ 62 , 44 , 42 ] . Therefore, POET continually attempts transfers among the active environments. These transfer attempts are also easily parallelized because they too can be attempted independently.

More formally, Algorithm 2 describes this complete main loop of POET. Each component is shown in pseudocode: creating new environments, optimizing each agent, and attempting transfers. The specific implementation details for the subroutines MUTATE_ENVS (where the new environments are created) and EVALUATE_CANDIDATES (where transfers are attempted) are given in Supplemental Information.

As noted above, the independence of many of the operations in POET, such as optimizing individual agents within their paired environments and attempting transfers, makes it feasible to harness the power of many processors in parallel. In the implementation of the experiment reported here, each run harnessed 256 parallel CPU Cores. Our software implementation of POET, which will be released as open source code shortly, allows seamless parallelization over any number of cores: workers are managed through Ipyparallel to automatically distribute all current tasks so that requests for specific operations and learning steps can be made without concern for how they will be distributed.

Provided that a space of possible environmental challenges can be encoded, the hope is that the POET algorithm can then start simply and push outward in parallel along an increasingly challenging frontier of challenges, some of which benefit from the solutions to others. The next section describes a platform designed to test this capability.

## 4 Experiment Setup And Results

An effective test of POET should address the hypothesis that it can yield an increasingly challenging set of environments, many with a satisfying solution, all in a single run. Furthermore, we hope to see evidence for the benefit of cross-environment transfers. The experimental domain in this work is a modified version of the “Bipedal Walker Hardcore” environment of the OpenAI Gym [ 63 ] . Its simplicity as a 2-D walking domain with various kinds of possible terrain makes it easy to observe and understand qualitatively different ambulation strategies simply by viewing them. Furthermore, the environments are easily modified, enabling numerous diverse obstacle courses to emerge to showcase the possibilities for adaptive specialization and generalization. Finally, it is relatively fast to simulate, allowing many long experiments compared to the more complex environments where we expect this algorithm to shine in the future.

### 4.1 Environment and Experiment Setup

The agent’s hull is supported by two legs (the agent appears on the left edge of figure 1 ). The hips and knees of each leg are controlled by two motor joints, creating an action space of four dimensions. The agent has ten LIDAR rangefinders for perceiving obstacles and terrain, whose measurements are included in the state space. Another 14 state variables include hull angle, hull angular velocity, horizontal and vertical speeds, positions of joints and joint angular velocities, and whether legs touch the ground [ 63 ] .

Guided by its sense of the outside world through LIDAR and its internal sensors, the agent is required to navigate, within a time limit and without falling over, across an environment of a generated terrain that consists of one or more types of obstacles. These can include stumps, gaps, and stairs on a surface with a variable degree of roughness, as illustrated in Figure 1 .

As described in the following equation, reward is given for moving forward, with almost no constraints on agents’ behaviors other than that they are encouraged to keep their hulls straight and minimize motor torque. If the agent falls, the reward is − 100 -100 . Reward per step = { − 100 , if robot falls 130 × Δ ​ x − 5 × Δ ​ hull_angle − 0.00035 × applied_torque , otherwise. \text{Reward per step}=\begin{cases}-100,&\text{if robot falls }\\ 130\times\Delta x-5\times\Delta\text{hull\_angle}-0.00035\times\text{applied\_torque},&\text{otherwise.}\end{cases} The episode immediately terminates when the time limit (2,000 time steps) is reached, when the agent falls, or when it completes the course. In this work, we define an environment as solved when it both reaches the far end of the environment and obtains a score of 230 or above. Based on our observations, the score of 230 ensures that the walker is reasonably efficient.

Following the architecture of controllers for the same domain by Ha [64] , all controllers in the experiments are implemented as neural networks with 3 fully-connected layers with t ​ a ​ n ​ h tanh activation functions. The controller has 24 inputs and 4 outputs, all bounded between - 1 and 1, with 2 hidden layers of 40 units each. Each ES step (Algorithm 1 ) has a population size of 512 (i.e. the number of parameters sampled to create the weighted-average for one gradient step is 512) and and updates weights through the Adam optimizer [ 65 ] . The learning rate is initially set to 0.01 0.01 , and decays to 0.001 0.001 with a decay factor of 0.9999 0.9999 per step. The noise standard deviation for ES is initially set to 0.1 0.1 , and decays to 0.01 0.01 with a decay factor of 0.999 0.999 per step. When any environment-agent pair accepts a transfer or when a child environment-agent pair is first created, we reset the state of its Adam optimizer, and set the learning rate and noise standard deviation to their initial values, respectively.

### 4.2 Environment Encoding and Mutation

Intuitively, the system should begin with a single flat and featureless environment whose paired policy can be optimized easily (to walk on flat ground). From there, new environments will continue to be generated from their predecessors, while their paired policies are simultaneously optimized. The hope is that a wide variety of control strategies and skill sets will allow the completion of an ever-expanding set of increasingly complex obstacle courses, all in a single run.

To enable such a progression, we adopt a simple encoding to represent the search space of possible environments. As enumerated in Table 1 , there are five types of obstacles that can be distributed throughout the environment: (1) stump height, (2) gap width, (3) step height, (4) step number (i.e. number of stairs), and (5) surface roughness. Three of these obstacles, e.g. stump height, are encoded as a pair of parameters (or genes ) that form an interval from which the actual value for each instance of that type of obstacle in a given environment is uniformly sampled. As will be described below, in some experiments, some obstacle types are intentionally omitted, allowing us to restrict the experiment to certain types of obstacles. When selected to mutate for the first time, obstacle parameters are initialized to the corresponding initial values shown in Table 1 . For subsequent mutations, an obstacle parameter takes a mutation step (whose magnitude is given in Table 1 ), and either adds or subtracts the step value from its current value. Note that for surface roughness, both the initial value and every subsequent mutation step are sampled uniformly from ( 0 , 0.6 ) (0,0.6) because the impact of roughness on the agent was found to be significant sometimes even from very small differences. The value of any given parameter cannot exceed its maximum value .

Because the parameters of an environment define a distribution, the actual environment sampled from that distribution is the result of a random seed . This seed value is stored with each environment so that environments can be be reproduced precisely, ensuring repeatability. (The population of many environments and the mutation of environments over time still means that training overall does not occur on only one deterministic environment.) With this encoding, all possible environments can be uniquely defined by the values for each obstacle type in addition to the seed that is kept with the environment.

Any environments that satisfy the reproduction eligibility condition in Line 7 of Algorithm 3 (which is given in Supplemental Information) are allowed to mutate to generate a child environment. In our experiments, this condition is that the paired agent of the environment achieves a reward of 200 or above, which generally indicates that the agent is capable of reaching the end of the terrain (though slightly below the full success criterion of 230). To construct child_list in Line 15 in Algorithm 3 , the set of eligible parents is sampled uniformly to choose a parent, which is then mutated to form a child that is added to the list. This process is repeated until child_list reaches max_children , which is 512 in our experiments. Each child is generated from its parent by independently picking and mutating some or all the available parameters of the parent environment and then choosing a new random seed. The minimal criterion (MC) 50 ≤ E child ​ ( θ child ) ≤ 300 50\leq E^{\textrm{child}}(\theta^{\textrm{child}})\leq 300 then filters out child environments that appear too challenging or too trivial for the current level of capability of agents. In case the number of child environments that satisfy the MC is more than the maximum number of children admitted per reproduction, those with lower E child ​ ( θ child ) E^{\textrm{child}}(\theta^{\textrm{child}}) are admitted until the cap is reached.

### 4.3 Results

An important motivating hypothesis for POET is that the stepping stones that lead to solutions to very challenging environments are more likely to be found through a divergent, open-ended process than through a direct attempt to optimize in the challenging environment. Indeed, if we take a particular environment evolved in POET and attempt to run ES (the same optimization algorithm used in POET) on that specific environment from scratch, the result is often premature convergence to degenerate behavior. The first set of experiments focus on this phenomenon by running POET with only one obstacle type enabled (e.g. gaps in one case, roughness in another, and stumps in another). That way, we can see that even with a single obstacle type, the challenges generated by POET (which POET solves) are too much for ES on its own.

Figure 2 shows example results that illustrate this principle. Three challenging environments that POET created are shown, with wide gaps, rugged hillsides, and high stumps, respectively. To demonstrate that these environments are challenging, we ran ES to directly optimize randomly initialized agents for them. More specifically, for each of the three environments, we ran ES five times with different initialization and random seeds up to 16,000 ES steps (which is twice as long as Ha [64] gives agents in the same domain with ES). Such ES-optimized agents are consistently stuck at local minima in these environment. The maximum scores out of the five ES runs for the environments illustrated in Figure 2(a) , 2(b) , and 2(c) are 17.9, 39.6, and 13.6, respectively, far below the success threshold of 230 that POET exceeds in each case. In effect, to obtain positive scores, these agents learn to move forward, but also to freeze before challenging obstacles, which helps them avoid the penalty of − 100 -100 for falling. This behavior is a local optimum: the agents could in principle learn to overcome the obstacles, but instead converge on playing it safe by not moving. Note that ES had previously been shown to be a competent approach [ 66 ] on the original Bipedal Walker Hardcore environment in OpenAI Gym, which, as illustrated later in Table 2 , consists of similar, but much less difficult obstacles. The implication is that the challenges generated and solved by POET are significantly harder and ES alone is unable to solve them.

For example, in Figure 2(a) , the sequence in the top row illustrates the agent choosing to stop to avoid jumping over a dangerously wide gap: it slowly sticks one of its feet out to reach the bottom of the first wide gap and then maintains its balance without any further movement until the time limit of the episode is reached. Videos of this and other agents from this paper can be found at eng.uber.com/poet-open-ended-deep-learning . In contrast, POET not only creates such challenging environments, but also in this case learns a clever behavior to overcome wide gaps and reach the finish line (second row of Figure 2(a) ).

Figure 3 illustrates two more interesting examples of challenging environments and the highly adapted capabilities of their paired agents. In the first, the agent navigates a very steep staircase of oversized steps, which ES alone cannot solve. In the second, an experiment in heterogeneous environments (with both gaps and stumps available) yields a single obstacle course of varying gap widths and stump heights where the POET agent succeeds and ES fails. The maximum scores out of the five ES runs for the environments illustrated in Figure 3(a) and 3(b) are 24.0 and 19.2, respectively, again far below the success theshold for POET of 230. Figure 4 illustrates the dramatic failure of ES to match the performance of POET in these relatively simple environments that POET generated and solved.