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

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

An interesting aspect of open-ended algorithms is that statistical comparisons can be challenging because such algorithms are not trying to perform well on a specific preconceived target, and thus some amount of post-hoc analysis is often necessary. That property is what motivates an analysis driven by choosing environments produced and solved by POET, and then checking whether direct optimization can solve these environments. However, from a statistical comparison standpoint it raises the challenge that because each environment created by POET is unique, we only have one score for POET to compare against a set of direct-optimization ES runs. For that reason, we use a single-sample t-test that assumes the POET distribution is centered on the single POET score and measures whether the direct optimization distribution’s mean is statistically significantly lower. As the very poor results for ES would suggest, based on single-sample t-tests for all five environments in figures 2 and 3 that are created by POET, the scores of agents optimized by ES alone are very unlikely to be from a distribution near the POET-level solutions ( p < 0.01 p<0.01 ).

One interpretation of POET’s ability to create agents that can solve challenging problems is that it is in effect an automatic curriculum builder. Building a proper curriculum is critical for learning to master tasks that are challenging to learn from scratch due to a lack of informative gradient. However, building an effective curriculum given a target task is itself often a major challenge. Because newer environments in POET are created through mutations of older environments and because POET only accepts new environments that are not too easy not too hard for current agents, POET implicitly builds a curriculum for learning each environment it creates. The overall effect is that it is building many overlapping curricula simultaneously, and continually checking whether skills learned in one branch might transfer to another.

A natural question then is whether the environments created and solved by POET can also be solved by an explicit, direct-path curriculum-building control algorithm. To test this approach, we first collect a sample of environments generated and solved by POET, and then apply the direct-path control to each one separately to see if it can reach the same capabilities on its own. In this control, the agent is progressively trained on a sequence of environments of increasing difficulty that move towards the target environment. This kind of incremental curriculum is intuitive and variants of it appear in the literature when a task is too hard to learn directly [ 67 , 68 , 69 , 70 , 40 ] . The sequence of environments start with an environment of only flat ground without any obstacles (which is easy enough for any randomly initialized agent to quickly learn to complete). Then each of the subsequent environments are constructed by slightly modifying the current environment. More specifically, to get a new environment, each obstacle parameter of the current environment has an equal chance of staying the same value or increasing by the corresponding mutation step value in Table 1 until that obstacle parameter reaches that of the target environment.

In this direct-path curriculum-building control, the agent moves from its current environment to the next one when the agent’s score in the current environment reaches the reproduction eligibility threshold for POET, i.e. the same condition for when an environment reproduces in POET. The control algorithm optimizes the agent with ES (just as in POET). It stops when the target environment is reached and solved, or when a computational budget is exhausted. To be fair, each run of the control algorithm is given the same computational budget (measured in total number of ES steps) spent by POET to solve the environment, which includes all the ES steps taken in the entire sequence of environments along the direct line of ancestors (taking into account transfers) leading to the target. This experiment is interesting because if the direct-path control cannot reach the same level as the targets, it means that a direct-path curriculum alone is not sufficient to produce the behaviors discovered by POET, supporting the importance of multiple simultaneous paths and transfers between them.

The direct-path curriculum-building control is tested against a set of environments generated and solved by POET that encompass a range of difficulties. For these experiments, the environments have three obstacle types enabled: gaps, roughness, and stumps. Unlike when comparing to ES alone, he we allow POET to generate environments with multiple obstacles at the same time because the curriculum-based approach should in principle be more powerful than ES alone. To provide a principled framework for choosing the set of generated environments to analyze, they are classified into three difficulty levels. The difficulty level of an environment is based on how many conditions it satisfies out of the three listed in Table 2 . In particular, a challenging environment satisfies one of the three conditions; a very challenging environment satisfies two of the three; and satisfying all three makes an environment extremely challenging . It is important to note that these conditions all merit the word “challenging” because they all are much more demanding than the corresponding values used in the original Hardcore version of Bipedal Walker in OpenAI Gym [ 71 ] (denoted as reference in Table 2 , which was also used by Ha [64] . More specifically, they are 1.2, 2.0, and 4.5 times the corresponding reference values from the original OpenAI Gym environment, respectively.

In this experiment, each of three runs of POET takes up to 25,200 POET iterations with a population size of 20 active environments, while the number of sample points for each ES step is 512. These runs each take about 10 days to complete on 256 CPU cores. The mean (with 95% confidence intervals) POET iterations spent on solving challenging, very challenging, and extremely challenging environments starting from the iteration when they were first created are 638 ± 133 638\pm 133 , 1 1 , 180 ± 343 180\pm 343 , and 2 2 , 178 ± 368 178\pm 368 , respectively. Here, one POET iteration refers to creating new environments, optimizing current paired agents, and attempting transfers (i.e. lines 4-22 in Algorithm 2 ). The more challenging environments clearly take more effort to solve.

Figure 5 compares the POET environments and the direct-path curriculum-building control algorithm through a series of rose plots , wherein each rose plot compares the configuration of an environment solved by POET (red pentagons) with the closest that the direct-path control could come to that configuration (blue pentagons). For each red pentagon there are five such blue pentagons, each representing one of five separate attempts by the control to achieve the red pentagon target. The five vertices of each pentagon indicate roughness, the lower and upper bounds of the range of the gap width, and those of the stump height, respectively. Each column in figure 5 consists of six representative samples (the red pentagons) of environments that a single run of POET up to 25,200 iterations created and solved. As the rows descend from top to bottom, the difficulty level decreases. In particular, the top two rows are extremely challenging targets, the next two are very challenging, and the bottom two are challenging (all are randomly sampled from targets generated and solved at each difficulty level in each run). Qualitatively, it is clear from figure 5 that attempts by the direct-path control consistently fail to reach the same level as POET-generated (and solved) levels.

To more precisely quantify these results, we define the normalized distance between any two environments, E A E_{A} and E B E_{B} as 1 β ​ ‖ e ⁡ ( E A ) − e ⁡ ( E B ) e ⁡ ( E Max ) ‖ 2 \frac{1}{\beta}||{\frac{e(E_{A})-e(E_{B})}{e(E_{\textrm{Max}})}}||_{2} , where e ⁡ ( E ) e(E) is the genetic encoding vector of E E , and E Max E_{\textrm{Max}} is a hypothetical environment (for normalization purpose) with all genetic encoding values are maxed out. (The maximum values are roughness = 8 , Gap_lower = Gap_upper = 8 , Stump_lower = Stump_upper = 3 \textrm{roughness}=8,\textrm{Gap\_lower}=\textrm{Gap\_upper}=8,\textrm{Stump\_lower}=\textrm{Stump\_upper}=3 .) The constant β = 5 \beta=\sqrt{5} is simply for normalization so that the distance is normalized to 1 1 when E A = E Max E_{A}=E_{\textrm{Max}} and E B E_{B} is a purely flat environment (roughness zero) without any obstacles, which therefore contains an all-zero genetic encoding vector. Based on this distance measure, we can calculate the median values and confidence intervals of distances between target environments (created and solved by POET) and the corresponding closest-to-target environments that the control algorithms can solve. These values are calculated for all the environments of different challenge levels across all three runs shown in figure 5 .

The results, summarized in figure 6 , demonstrate that POET creates and solves environments that the control algorithm fails to solve at very and extremely challenging difficulty levels, while the curriculum-based control algorithm can often (though not always) solve environments at the lowest challenge level. One implication of these results is that the direct-path curriculum-building control is valid in the sense that it does perform reasonably well at solving minimally challenging scenarios. However, the very and extremely challenging environments that POET invents reach significantly beyond what the direct-path curriculum can match. There are a couple ways to characterize this significance level more formally. These analyses are based on the distance between the closest environment reached by the control and the POET-generated target . First, we can examine whether that distance is significantly greater the higher the challenge level. Indeed, Mann-Whitney U tests show that the difference between such distances between challenging and very challenging environments is indeed very significant ( p < 0.01 p<0.01 ), as is the difference between such distances between very challenging and extremely challenging. This test gives a quantitative confirmation of the intuition (also supported by figure 6 ) that these challenge levels are indeed meaningful, and the higher they go, the more out of reach they become for the control. Second, a single-sample t-test (which was previously used when comparing POET to the ES-alone control) can also here provide confidence that the distances from the targets are indeed far in an absolute sense: indeed, even at the lowest challenge level (and for all challenge levels), the one-sample t-test measures high significance ( p < 0.01 p<0.01 ) between the distribution of distances from the target and the target level.

In aggregate, the results from the direct-path curriculum-building control help to show quantitatively the advantage of POET over conventional curriculum-building. In effect, the ability to follow multiple chains of environments in the same run and transfer skills among them pushes the frontier of skills farther than a single-chain curriculum can push, hinting at the limitations of preconceived curricula in general. Thus, while POET cannot guarantee reaching a particular preconceived target, these results suggest that in some environment spaces POET’s unique ability to generate multiple different challenges and solve them may actually still provide a more promising path towards solving some preconceived target challenges (i.e. offering a powerful alternative to more conventional optimization), putting aside the additional interesting benefits of an algorithm that invents, explores, and solves new types of challenges automatically.

A fundamental problem of a pre-conceived direct-path curriculum (like the control algorithm above) is the potential lack of necessary stepping stones . In particular, skills learned in one environment can be useful and critical for learning in another environment. Because there is no way to predict where and when stepping stones emerge, the need arises to conduct transfer experiments (which POET implements) from differing environments or problems [ 44 ] . In conventional curriculum-building algorithms, the “transfer” only happens once, i.e. at the time when the new environment is created, and is unidirectional, i.e. from the agent paired with the parent environment ( parent agent ) to the child environment with the hope that the parent agent helps jump-start learning in the child environment.

In contrast, POET maintains parallel paths of environment evolution and conducts transfer experiments periodically that give every active agent multiple chances to transfer its learned skills to others, including the transfer of a child agent back to its parent environment, which continually creates and preserves opportunities to harness unanticipated stepping stones. Figure 7 presents an interesting example from POET where such transfers help a parent environment acquire a better solution: The parent environment includes only flat ground and the parent agent learns to move forward without fully standing up (top left), which works in this simple environment, but represents a local optimum in walking behavior because standing would be better. At iteration 400, the parent environment mutates and generates a child environment with small stumps, and the child agent inherits the walking gait from the parent agent.

At first, it can move forward in the new stumpy environment, but it often stumbles because of its crouching posture (top right). Later, through several hundred further iterations of ES, the child agent eventually learns to stand up and jump over the stumps. The interesting moment is iteration 1,175, when that skill is transferred back to the parent environment (middle row). For the first time, the parent environment (which is completely flat) now contains an agent who stands up while walking. Without the backward transfer, the agent in the simple flat environment would be stuck at its original gait (which is in effect a local optimum) forever, which was confirmed by separately turning off transfer and running the kneeling (local optimum) agent in the original (parent) environment for 3,000 iterations, which did not result in any substantive change. Interestingly, after transfer back to the parent environment, the transferred agent then continued to optimize the standing gait to the parent (stump-free) environment and eventually obtained a much better walking gait that moves faster and costs less energy due to less friction (bottom row). More specifically, given 3,000 iterations, the agent with the original kneeling walking gait reaches a score of 309, while the one with the more optimal walking gait illustrated in figure 7(b) reaches a score of 349.

To give a holistic view of the success of transfer throughout the entire system, we count the number of replacement attempts during the course of a run, which means the number of times an environment took a group of incoming transfer attempts from all the other active environments. The total number of such replacement attempts in RUN 1, RUN 2, and RUN 3 (labelled in Figure 5 ) are 18,894, 19,014, and 18,798, respectively, out of which, 53.62 % 53.62\% , 49.26 % 49.26\% , 48.89 % 48.89\% , respectively, are successful replacements (meaning one of the tested agents is better than the current niche champion). Note that each replacement attempt here encompasses both the direct transfer and proposal transfer attempts. These statistics show how pervasively transfer permeates (and often adds value to) the parallel paths explored by POET.