That Escalated Quickly: Compounding Complexity by Editing Levels at the Frontier of Agent Capabilities
Authors: Jack Parker-Holder
Minqi Jiang
Michael D Dennis
Mikayel Samvelyan
Jakob Nicolaus Foerster
Edward Grefenstette
Tim Rocktäschel
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement Learning
Unsupervised Environment Design

Abstract: Deep Reinforcement Learning (RL) has recently produced impressive results in a series of settings such as games and robotics. However, a key challenge that limits the utility of RL agents for real-world problems is the agent's ability to generalize to unseen variations (or levels). To train more robust agents, the field of Unsupervised Environment Design (UED) seeks to produce a curriculum by updating both the agent and the distribution over training environments. Recent advances in UED have come from promoting levels with high regret, which provides theoretical guarantees in equilibrium and empirically has been shown to produce agents capable of zero-shot transfer to unseen human-designed environments. However, current methods require either learning an environment-generating adversary, which remains a challenging optimization problem, or curating a curriculum from randomly sampled levels, which is ineffective if the search space is too large. In this paper we instead propose to evolve a curriculum, by making edits to previously selected levels. Our approach, which we call Adversarially Compounding Complexity by Editing Levels (ACCEL), produces levels at the frontier of an agent's capabilities, resulting in curricula that start simple but become increasingly complex. ACCEL maintains the theoretical benefits of prior works, while outperforming them empirically when transferring to complex out-of-distribution environments.

Under review as a conference paper at ICLR 2022
THAT ESCALATED QUICKLY: COMPOUNDING COMPLEXITY BY EDITING LEVELS AT THE FRONTIER OF AGENT CAPABILITIES
Anonymous authors Paper under double-biee blind review
ABSTRACT
Deep Reinforcement Learning (RL) has recently produced impressive results in a series of settings such as games and robotics. However, a key challenge that limits the utility of RL agents for real-worlh problems is the agent's ability to generalize unseen variations (or levels). To train more robust agents, the field Unsupervised Environment Design (UED) seeks produce a curriculum by updating both the agent and the distribution over training environments. Recent advances in UED have come from promoting levels with high regres, which provides theoretical guar- antees in equilibrium and empirically has been shown to produce agents capable zero-shot transfer unseen ousannde environments. However, current methods require either learning an environment environment-generaiing adversary, which re- mains a challenging optimization problem, or curating a curriculum from randomly sampled levels, which is ineffective if the search space is too large. In this paper we instead propose to evolve curriculum, by making edits to previously selected levels. Our approach, which we call Adversarialyy Compounding Complexity by Editing Levels (ACCEL), produces levels at the frontier of an agent's 's capabilities, resulting in curricula that start simple but become increasingly complex. AC- CEL maintains the theoretical benefits of prior works, while outperforming them empirically when transferring complex -fitt--distiiuution environments.
INTRODUCTION
considers the problem of an agent learning from experience in an environment to maximize total (discounted) of reward. The past decade has seen surge of interest in RL, with high profile successes in games (Vinyals et al. 2019 |errer et al. 2019: Silver et al., 2016 Mnih et al. 2013 Hu & Foerster 2020) and robotics (OpenAl et al.) 2019 Andrychowiez et al., 2020). As such, there is tremendous excitement that RL may be a path towards generally capable agents (Silver et al. (021). Despite these successes, deploying RL agents in the real world remains a challenge simulation may not result in policies that are robust the many sources of variation in the real world.
Reinforcement Learning (RL., Sutton & Barto 1998)
Aaolac-Amood et al. 2019). Notably, strong training performance in
Addressing this challenge on the agent side has become an active area of research (Zhang et al. 2021a| Agarwal al.) [021a] Raileanu & Fergus) 2021). but in this paper instead focus on the impact of the training environment itself, which often has a significant impact on agent's 's ability to generalize (Co-Reyes al. 2020). For example in locomotion tasks, Reda Reess, al. (2020) found that the initial state distribution, survival bonus, reward structure and control frequency had significant impact on the performance an agent. Indeed, curricula over environments can also influence the generalization performance of the agent (Jiang et al., 2021b). Throughout this paper we consider distributions of environments, referring to each individual sample as a level. Given parameterized environment, the simplest approach one can consider is Domain Randomization (DR, Jakobi 1997]
Tobin et al. 20177 Sadeghi Levine 2017 7 Risi & Togelius| 2020 Peng et al. (017). whereby an agent trains on individual levels uniformly sampled from an underlying environment distribution. has been shown that training an agent with a DR-type approach can produce agents capable of
complex real-world skills (OpenAl et al. 2019). However, the performance of DR is only good
as the sampling distribution available thus it can be ineffective when the probability of sampling useful levels is too low.

---

Under review as a conference paper at ICLR 2022
Figure 1: The evolution of level: At first, the editor places blocks outside the trajectory of the optimal policy, which acts as an augmentation the agent has fully observable view. Then, the editor moves the agent further from the goal, hefore placing challenging obstacles in its path. Note that since the agent can move diagonally this environment, the final level is solvahle. Each level is a high Positive Value Loss at the time it is included in the level store, thus the level co-evolves with the agent over time.
Recently, Unsupervised Enviroument Design (UED, Dennis et al. 2020) has emerged as formalism for methods to design effective curricula. Given parameterized environment, UED methods frame learning as a game between teacher which generates a curriculum of levels, and a student seeking to maximize some notion of return. UED is a generalization of several other approaches. Indeed, DR can be considered as UED algorithm whereby the teacher generates environments uniformly at random from the environment distribution. Other approaches to UED consider learning teacher agent (or generator), with variety of adversarial objectives proposed (Dennis et al. 2020, Gur ict al., 2021). However, training teacher is a challenging optimization problem, suffering from both nonstationarity and sparse reward, as the teacher's s feedback only comes after evaluation by a changing student policy. Recent work showed can be more effective to simply curate levels produced by DR @iang et al. 22221b a Matiisen al.] 2020), producing curriculum of increasingly complex randomly generated levels. Despite their promise, these methods can only be as effective the best of the random levels they sample, which be limitation in high dimensional design spaces. Finally, another series of promising works seek to evolve populations of environments (Wang) al., 2019 2020 Dharna et al., 2020), but these methods heavily rely on handcrafted heuristics and also use up to 20x more compute since they also train a population of agents. In this paper, we seek a general method which harnesses the benefits of all three of these approaches. We posit the following: Rather than generate levels from scratch, it may be more effective to edit previously curated levels.
Our primary contribution is to propose a new method which we call Adversarially Compounding Complexity by Editing Levely, or ACCEL. ACCEL is an evolutionary process, with levels constantly changing to remain at the frontier of the student agent's capabilities (see: Figure 2
As such, levels generated by ACCEL begin simple but quickly become more complex. This benefits both the beginning of train- ing (Berthouze & Lungarella 2004), as the student begins learning much faster, while also facilitates the construction plex structures (see Figure []. We believe ACCEL provides the best of both worlds: an evolutionary approach that can generate increasingly complex environments, com- bined with regret-based curator which pro- vides theoretical robustness guarantees in equilibrium. We evaluate ACCEL on a se- ries of challenging procedurally generated grid world environments, where ACCEL demonstrates the ability rapidly increase complexity while maintaining performance. Finally, we show ACCEL makes it possible to train agents capable of transfer to mazes order of magnitude larger than training levels, achieving over double the success rate of the next best baseline.
Conerator
Curator
com-
Update buffer
Replay level
Student
R
Select for editing
An overview ACCEL. Levels are (randomly) sampled from a generator, and evaluated, with high regret levels added to the level buffer. The curator selects levels replay, which are used train the student agent. After training, the levels are passed to the editor and the edited levels are added to the level store they are high regret.
Figure 2:
2 BACKGROUND
2.1 FROM MDPs TO UNDERSPECIFIED POMDPS
Markov Decision Process (MDP) is defined as tuple (5, A, A, R,y) where and A stand for the sets of states and actions respectively and T S A ASS) is transition function representing the probability that the system/agent transitions from a state s, E to 8141 E S given action a, e A. Each transition also induces associated reward r. generated by reward functionR. S R. and
2

---

Under review as a conference paper at ICLR 2022
is discount factor. When provided with MDP, the goal of Reinforcement Learning (RL, Sutton & Barto 1998) is to learn a policy ι that maximizes expected discounted reward, i.e. E E ran"].
Despite the generality of the MDP framework, it is often an unrealistic model for real world en- vironments. First, it assumes full observability of the state, which often impossible in practice. This is addressed in partially observable MDPs, or POMDPs, which include an observation function I: O which maps the true state (which is unknown to the agent) (potentially noisy) set of observations O. Secondly, the traditional MDP framework assumes single reward and transition function, which are fixed throughout learning. Instead, in the real world, agents may experiend experience variations not seen during training, which makes it crucial that policies are capable of robust transfer.
To address both of these issues, we use the recently introduced Underspecifted POMDP, or UPOMDP, given by .M- = (A, O S.M TM I-M, RMM, 7)). This definition is identical to POMDP with the addition of to represent the free parameters of the environment, similar to the context in Contextual MDP (Modi et al.) 2017). These parameters can be distinct at every time step and incorporated into the transition function TM x A x e - A (S). Following Jiang et al. (2021a) we define a level Mo as environment resulting from fixed 8. We define the value of in Me to be (T) E -ا== rr7"]] where rr are the rewards achieved by क in MM. UPOMDPs benefit from their generality, since θ can represent possible dynamics (for example in sim2real (Peng et al. 2017 OpenAl al.j [019 Andrychowicz al., 2020i). changes in observations, different reward functions or differing game maps in procedurally generated environments.
2.2 METHODS FOR UNSUPERVISED ENVIRONMENT DESIGN
The goal of Unsupervised Environment Design (UED, Dennis al. 2020 to generate a series of levels that form curriculum for a student agent, such that the student agent is capable of transfer, by maximizing some utility function U, 0). In the case of DR, the utility function is simply:
(1) for any constant C. When learning a teacher, recent approaches proposed to use objectives seeking to maximize regret, defined as the difference between the expected return of the current policy and the optimal policy, ie:
U (T, 0) CC
U. [T, 0) argmax (T, x²) argmax (""")) V (T)) "*Ell
"-"Ill
Unlike other objectives, which may promote unsolvable environments, regret-based objectives have been shown to promote the simplest possible environments that the agent cannot currently solve (Dennis et al. 2020) in range of settings. However, since do not have access x", key challenge in UED algorithms utilizing objectives inspired by Equation 2 is to approximate the regret. Recently, the Prioritized Level Replay (PLR, Jiang et al. 2021 ab algorithm introduced an additional teacher agent in the form of a curator, forming a "dual curriculum game". The curator maintains a buffer of previously experienced levels and selects levels to be replayed by the student policy using objectives approximating regret. One of the objectives used by PLR is Positive Value Loss, given by:
1
T
EGAA)A 15,,
Σ max 1=0
T
where À and 7 are the Generalized Advantage Estimation (GAE, Schulman et al. (006)) and MDP discount factors respectively, and 8, the TD-error at timestep t. Since Positive Value Loss approximates regret, if the student trains solely on curated levels (i.e. does not take gradient steps on levels from the generator), then PLR achieves robustness guarantees in equilibrium. More formally, if S, II is the strategy set of the student and S, = θ is the strategy set of the teacher (in this case the curator), then (by Corollary of Jiang et al. (021aa), in equilibrium the resulting student policy converges to a minimax regret policy, ie:
argmin max [REGRET (TA, FAElI
(4)
Empirically PLR has also been shown produce policies with strong generalization capabilitie yet it's main weakness is that it still relies on randomly sampling useful levels. Next, we introduce our new approach which seeks to leverage the curator to produce batches of high regret levels.
To see the impact of PLR simple example, we include visualization in Figure 19 in the Appendix.
3

---

Under review as a conference paper at ICLR 2022
3 COMPOUNDING COMPLEXITY BY EDITING LEVELS
In this section we introduce our new method for UED, building on regret-based methods such PLR. As the dimensionality of the design space increases, it becomes increasingly challenging to randomly sample effective levels for learning-a problem we call "the curse of dimensionality in UED". Thus, rather than solely rely on curating random levels, we instead look to evolution to produce new batches of levels, by making edits to previously curated ones. This is direct attempt to produce more levels at the "frontier" of agent capabilities, which has been shown to be useful in variety of recent works (Wang et al.) 2019 Jiang et al. 2021b, Zhang et al. 2020p. Evolutionary methods are suitable for this, yet often require heuristics to define a workable fitness function. For example, POET pre-filters levels using handcrafted criteria to have a reward in the range [50, 300). We propose a more general approach using regret in the form of Positive Value Loss to assess learning potential. We call our method Adversarially Compounding Complexity by Editing Levels, or ACCEL.
The key idea of ACCEL is to introduce an ed- itor, which produces new levels for the agent by making edits levels previously sampled by the curator. Editing involves making a hand- ful of changes (e.g. adding/removing tiles a maze), but could be extended to generative models (c.g. perturbations in a latent space). Equipped with the ability to edit levels, it is pos- sible to produce an entire batch of useful levels from single example, while incrementally in- creasing complexity. We consider both learned editor, optimizing for Positive Value Loss (Equa- tion 3). and a random one. Following Robust PLR (Jiang et al. 2a2 we do not initially train on edited levels. Instead, we evaluate them and only add them the replay buffer if they meet the threshold for the scoring function (high regret). We consider two different criteria for se- lecting which replay levels to edit: those which the agent can now solve with low future learning potential, approximated as return minus regret, which we call "easy", and "batch" where we use the entire batch. The full procedure is shown in Algorithm|]
Algorithm 1 ACCEL (changes w.r. Robust PLR) Buffer size K, initial fill ratio p. level generator. Initialize: Initialize policy x (Ø), level buffer A.
Input:
# Initial Data Collection
Sample K * p initial levels.
# Main Training Loop while not converged do
Sample replay decision d ~ (d(d) if d 0 then
Sample level 0 from level generator Collect r's trajectory T on 0, with a stop-
gradient Φb
Compute PLR score, S = score(r,
Add A to A if score S meets threshold
else
Sample replay level. 0 ~ A
Collect policy trajectory T on 0
Update with rewards I?(T)
Edit to produce 6'
Collect wts trajectory T on 6', with a stop- gradient d
Compute PLR score, 5 score(T, T) Add H' to A if score meets threshold (Optionally) Update Editor using score S
end end
We posit that editing is effective for two reasons. First, small incremental changes to level can lead to diverse batch of new ones (Sturtevant et al.) 2020), which may move those that are currently too hard or too easy towards the frontier of the agent's capabilities. This may also prevent overfit- ting, for example, in Figure 3 we see three levels generated by ACCEL in grid world environment (Chevalier-Boisver et al., 2018). Each is an edit of the same level, and has a similar initial obser- vation, yet requires the agent to explore
Levels generated by ACCEL. Though all levels are evolved from the same DR level, they re- quire different behaviors to solve. Left: the agent go up left and reach the goal. Middle: the goal on the left, while on the right the left path is blocked.
Figure 3:
different fashion to reach the goal. Training on these environments simultaneously will teach the agent to actively explore the environment. Second, making edits outside of the direct trajectory of the agent can be seen as form of data augmentation, which has been shown to improve sample efficiency in RL (Laskin et al. 2020 Kostrikov et al. 2021 Raileanu et al. 2020), since it changes the observation but not the optimal policy.
ACCEL is an Evolutionary algorithm, whereby the "fitness" is (approximate) regret, since levels only stay in the "population" (or level replay buffer) they meet the criteria for curation. Evolution has led to many successes in other domains (Stanley al.) 2019 Pugh al. 2016), and even proven useful for UED with the POET algorithm. Compared to POET we have two key differences: first, we have a population of levels but not population of agents, thus we have single, generally capable
4

---

Under review as a conference paper at ICLR 2022
agent. This likely leads to lower computational cost. In addition, ACCEL uses minimax regrer (rather than minimax) objective, which means we do not need handcrafted rules to select levels, since optimizing for regret naturally promotes levels at the frontier of agent's 's capability. Indeed, training on high regret levels also means that ACCEL inherits the robustness guarantees in equilbrium from Robust PLR (Corrollary 1 in Inniang et al. (2021a))
Remark 1. If the procedure described in Algorithm Finds a Nash equilibrium, then the student policy is following a minimax regret strategy.
This is in stark contrast with other evolutionary approaches, which rely solely on empirical results.
4 EXPERIMENTS
In our experiments we seek to answer the following two questions: 1) Can ACCEL lead to sample efficient learning in complex design spaces? 2) Can ACCEL compound complexity to asymptotically produce agents capable of zero-shot transfer to challenging out-of-distribution environments? We conduct series of experiments
grid world environments, as have been used in previous UED works (Dennis et al. 2020: Jiang et al.) 202 These environments are made challenging by high dimensional observations and sparse rewards, thus they are often used to test state-of-the-ar exploration methods (Raileanu & Rocktäschel 2020 Zhang et al. 2021b Flet-Berliac et al. 2021)
In all cases, we seek to train a student agent via Proximal Policy Optimization (PPO, Schulman ct al. 2016-2018), with a ResNet policy (He ct al. 2016) as originally proposed in Espeholt et al. (2018). To evaluate the quality of the curricula, we show all performance with respect to the number of student gradient updates opposed to total environment interactions, which is often comparable for PLR and ACCEL. For a full list of hyperparameters for each experiment please see Table 6 in Section
B.3 As baselines we consider the following:
Domain Randomization (DR): Randomly sampling from a parameterized distribution.
Prioritized Level Replay (PLR): We use Robust PLR from Jiang et al. (202
PAIRED: Placing fixed number of blocks, using the algorithm described in Dennis et al. (2020).
Minimax Adversarial: Placing blocks using an adversarial objective seeking to minimize return.
As in Dennis et al. (2020), we use a single minimax represent the POET objective when it is not combined with hand-coded constraints on the levels generated. We leave the comparison to population-based methods to future work due to the computational expense.
4.1
LEARNING WITH LAVA
PAIRED
DR
PLR
DR (U)
PLR (U)
ACCEL
1.00
Mean Agent Return
Shortest Path Length
10.
Number of Lava Tiles
Positive Value Loss
0.06
0.75
0.06
0.50
0.25
4
0.52
0.00
0.00
1000
1000
1000
Student PPO Updates
Student Updates
Student PPO Updates
Number of Edits
(a) Training Complexity
(b) Edit Efficacy
Figure 4: Lava grid training data. a) Left right: mean agent return training levels, the shortest path length and the number of lava tiles, plots show and sem. b) Positive Value Loss by number of edits for ACCEL
We begin with simple grid environment, whereby the agent must navigate to goal in the presence of lava blocks. The grid is small, only 7x7, however, it challenging for RL agents since exploring with random actions often leads to instant death, which makes it unlikely to receive signal from the sparse reward. Indeed, this makes the choice of DR parameterization crucial, since sampling too many blocks early will be prohibitive for learning. We compare two different parameterizations: "Binomial" where the agent samples from (lava, none) for 20 steps, and "Uniform" where the agent samples the number of tiles to place from the range [0,20]. For ACCEL,
generator that
5

---

Under review as a conference paper at ICLR 2022
produces empty rooms and then proceed to edit the levels to add (or remove) lava blocks. The environment is built with MiniHack, thus the agent has a global observation (details in the Appendix, We ran each method for five seeds, showing the results in Fig
Section:
B.I.
As we see, ACCEL quickly produces levels with more lava than the other methods, while also getting near-perfect return its training distribution. Interestingly, with the Uniform parameterization, see that PLR is able to produce a similar training profile to ACCEL, but achieves a lower value in every individual metric. The methods with learned generators (PAIRED and minimax) fail to learn anything, thus are unable to form a curriculum (Figure E.. Finally on the right we took a snapshot of the level replay buffer for ACCEL. where we clearly see that the levels which have been edited more have higher approximate regret. After one thousand PPO updates (around 20M timesteps) we tested each agent on series test tasks, which we show the Appendix (see Section A.3). We thus have answered our first question: in design space with high proportion of challenging levels, ACCEL is able to build an effective curriculum which quickly facilitates learning on the full distribution.
4.2 PARTIALLY OBSERVABLE NAVIGATION
To answer the second question, we now scale the MiniGrid (Chevalier-Boiseerl al. 2018 setting originally introduced in Dennis et al. (020). Despite being a conceptually simple environment, this large experiment: our agents tram for 20k updates (around 350M steps, see Table 5 learning an LSTM-baaed policy with a 147 dimension partially observable observation. We use the Uniform parameterization for DR which first samples the number of blocks to place, ranging from zero (an empty room) to sixty, since previous works showed that DR is sensitive to the number of blocks placed (Jiang et al. 20) For ACCEL we begin with empty rooms and randomly edit the block locations (adding removing them) as well of the goal location. After replay, edit the "easy" levels, essentially moving levels back to the frontier once their learning potential has been reduced.
PAIRED
Minimax
DR
PLR
ACCEL
PLR
ACCEL
Shortest Path Length
Number of Blocks
40
40
20
20-
0
20000
20000
Student Updates
Student Updates
(a) Emergent Complexity
(b) Example Levels
Figure 5: MiniGrid training data. a): the performance of all agents the the shortest path length and number of blocks on training levels, where ACCEL quickly develops highly challenging levels. Plots show the mean and standard error across five runs. b) Example levels generated by DR, PLR and ACCEL..
In Figure aaa) we show the training performance, where ACCEL does exactly as intended compounds initial complexity to ultimately train on levels with high block count and long paths to the goal. This can be seen in 5bb). where ACCEL produces more structured mazes than the baselines. We evaluate all five methods zero-shot
series of held-out environments used in prior works (see Figure 16), with the mean and sem per environment shown in Figure 6 For DR, PLR and ACCEL the evaluation is after 20k student updates, thus it solely compares the quality of the curriculum, while we use the Minimax and PAIRED results from Jiang et al. (202 la) at 250M training steps (>30kk updates). As see, ACCEL performs least well as the next best method in almost all settings, with particular strength in the more complex Labyrinth and Maze environments.
16Rooms 16Rooms2 Crossing FourRooms SmCoridor LgCorrdor Labyrinth Labyrinth2
Maze2
Maze3
PerfoctMaze
Solved Rate
PAIRED
Minimax
ACCEL
Figure 6: Zero-shot transfer results. Agents are evaluated for 100 episodes on series human designed mazes, plots show mean and standard error for each environment, across five runs.

---

Under review as a conference paper at ICLR 2022
Solved Rate
Median
IQM
PAIRED
Minimax
PAIRED
0.0
0.3
0.6
0.9
0.0
0.3
0.6
0.9
DR
Mean
Optimality Gap
PLR
ACCEL
PAIRED
0.25
0.50 0.75
0.25
0.50 0.75 1.00
0.0
0.5
Normalized
(a) PerfectMazze
(b) Aggregate Performance
Figure 7: Zero-shot performance large rroeduurall-geneeraeedd maze environment. Agents are evaluated for 100 episodes, bars show and standard error. ACCEL achieves double the success rate of the next best method, despite beginning with empty rooms. b) Example levels produced by each UED algorithm.
To evaluate the performance at the aggregate level, we make use of the recently introduced r riiaii liable library (Agarwal et al., 2021b) in Figure Zb). At the aggregate level the strength of ACCEL is clear, with an IQMP near 100% solved rate compared to below 80% for PL., with a probability of improvement of 80.2%. It is clear that ACCEL significantly stronger in these test environments.
Next we consider an even more challenging setting we use larger version of the "PerfectMaze", procedurally-generaie maze environment, shown in Figure The maze has 51x51 tiles, an order of magnitude larger than the training environment, and has maximum episode length of over 5k steps. This daunting navigation challenge, requiring extensive use of memory so as not to get lost in a loop of repeatedly exploring the same paths. We evaluate the agents at the checkpoint from Figure 6] testing each seed for 100 episodes, showing the mean and standard error in Figure aa). Both versions of ACCEL significantly outperform all baselines, achieving success rates of 53% and 52% compared to the next best 25% for PLR, while all other methods fail. Notably, ACCEL appears approximately follow the "left-hand" rule for solving mazes
What if we edit DR levels? We also consider an ablation of ACCEL where instead of beginning with empty rooms, we instead begin with levels sampled from the DR distribution. In Figure [8]c we show the performance of ACCEL, DR and PLR on the same generator distribution during training, where we see that ACCEL outperforms both. We also tested this version of ACCEL on the same held out tasks, where it achieved a mean performance comparable to the version presented Figure 6 while it also achieved 52% success on the large perfect maze. We conducted other ablations such as using learned editor, editing the full batch, with only small changes in performance (see Section A..4). We believe this shows the strength of ACCEL,, that it robust multitude of factors, even the generator distribution.
DR Generator Return
DR
PLR
ACCEL
0
20000
Student Updates
Figure 8: Performance of ACCEL when using the Uniform DR generator, com- pared DR and PL.. We test all agents during training on the same DR distrihu- tion. Curves show mean with sem shaded.
4.3 DISCUSSION AND LIMITATIONS
In our experiments we have demonstrated that ACCEL is capable of forming highly effective curricula in two challenging navigation environments. In the first, we showed ACCEL can facilitate learning in a design space with a high proportion of hard levels, which could have an impact in improving exploration in safety-critical settings. In the second, mazes which facilitate zero-shot transfer to human-designed ones, scaling to environments an order of magnitude larger than the training environment. This is made possible since ACCEL produces a high frequency of solvable mazes with a high block count, regardless of the DR generator used. Note that PLR is capable of sampling 60 block levels, but it will infrequently sample those that also contain useful (solvable) path to the goal. We thus believe we have shown evidence that ACCEL would be an effective method for training agents in more open-ended UED design spaces.
showed it is possible to produce complex
Inteequurttile Mean (IQM) is the recommended rohust statistic in Agarwal ct al. 2021b)
For more details see https:://///........ s tes. google e. com hommvvieww compound www.:mnddnngooooo www.mplcooeooooooooooowoooooocm. wewmmppexxiii eexeitt
7

---

Under review as a conference paper at ICLR 2022
However, as with any method, ACCEL comes with limitations. Our approach includes an inductive bias with the ability to begin with a simple base case (an empty room). This may not always be possible in practice, while in some settings the simplest example (in terms of entities placed in the environment) may actually be a more difficult environment to solve (for example in a Hide and Seek game). In addition, our experiments thus far only consider navigation tasks, and while the MiniGrid experiments are one of the largest settings used in UED, for the field more broadly to become useful for real-world problems it will be necessary test new environments. On the algorithmic side, potential limitation of ACCEL is there may be a lack of diversity in the level replay buffer. In this work we do not explicitly optimize for diversity, but instead, seek to reduce the impact through level replay hyperparameters (see the Appendix, Figure 21.. However, scaling ACCEL further may require a mechanism to directly encourage diversity.
RELATED WORK
Our work straddles a variety of interrelated fields, which we discuss in this section. For a summary of the most closely related methods see Table Our paper focuses testing agents on distributions of environments, which has long been known to be crucial to evaluate the generalization capability of RL. agents (Whiteson et al. 2009). The failure of agents in this setting has recently drawn considerable
attention (Packer et al. 2019 Lgl et al. 2019 Cobbe et al.) [2020] Agarwal et al. 202 Zhang et al., 20188; Ghosh et al.] (021). with policies often failing to adapt to changes in the observation (Song et al. 2020), dynamics (Ball et al. (021) or reward (Zhang et al. [2018)). In this work, we seek to provide agents with set of training levels to produce a policy that is robust to these variations.
In particular, we focus on the Unsupervised Environment Design (UED, Denmis et al., (2200) paradigm, which shifts from designing agents that can generalize from a fixed distribution of environments towards designing the environments themselves. The most popular method for UED is Domain randomization (DR, Jakobi 1997 Sadeghi & Levine, 2017) which has been particularly successful in
areas such robotics (Tobin et al. 2017 James et al. 2017 Andrychowicz et al. [2020] OpenAl et al.,
2019), with extensions proposing to actively update the DR distribution Mchta et al. (2020); Raparthy
eet al. (2020). This paper direetly extends Prioritized Level Replay (PLR, Jiang
al. 2001b a),
method for curating DR levels such that those with high learning potential can be replayed a student
agent. PLR is related TSCL (Matiisen al., (220)), self-paced learning (Klink et al. 2019 Eimer
let al. 202T) and ALP-GMM Portelas et al. (2019), which seek to maintain and update distributions over environment parameterizations. Very recently it was shown that with a smooth task space, a method similar to PLR is capable of producing generally capable agents in a simulated game world
(Team et al. 202T), using large scale compute and Population Based Training (Jaderberg et al. 2017).
However, this work relied on highly optimized task design space, which is rarely present in practice.
Dennis et | (2020) introduced the PAIRED algorithm, an elegant approach for UED, whereby an environment adversary optimizes for minimax regret (Savage 1951). defined as the difference in performance between an antagonist agent (colluding with the adversary) and the protagonist. This guarantees the adversary produces solvable mazes, which allows the protagonist to transfer to unseen environments and even learn to navigate the web (Gur et al., 202T). Adversarial objectives have also been considered in robotics (Pinto et al. 2017). POET (Wang et al., 2019 2020) considers evolving a population of environments, each paired with an agent, using an objective similar to minimax adversarial, which needs to be combined with domain-specifie rules to prevent unsolvable environments from being proposed. We take inspiration from the evolutionary nature of POET but train single agent, which is beneficial as it takes significantly fewer resources, while also removing the agent selection problem. UED is inherently related to the field of Automatic Curriculum Learning (ACL, Portelas et al. 2020 Florensa et al.) 2017 Baranes & Oudeyer, 2009), which seeks to provide a curriculum of increasingly challenging tasks or goals given (typically) fixed environment. A canonical approach is Hindsight Experience Replay (Andrychowicz et al. (017) which was shown to be effective for sparse reward tasks. Asymmetric Self Play (Sukhbaatar et al. 2018) takes the form of one agent proposing goals for another, which was shown to be effective for challenging robotic manipulation tasks (OpenAl et al. 2021). AMIGo (Campero et al. 2021 and APT-Gen (Fang et al. 2021) provide solutions to problems where the target task is known, providing curriculum of increasing difficulty. Indeed, many ACL methods emphasize learning to reach goals
or states with high uncertainty (Racaniere et al. 2020, Pong et al., (2220] [Zann et al.) 2020). either
using generative (Florensa et al. 2018) or world models (Mendonca et al. 2021)
Unlike these
8

---

Under review as a conference paper at ICLR 2022
Table I: The components of related approaches. Like POET, we evolve levels, but use single agent rather than a population, while also using minimax regret objective, which ensures the environments generated are solvable. PAIRED uses minimax regret for the generator, which is often challenging to optimize, while it does not replay levels so may suffer from cycling. Finally, PLR curates levels using minimax regret, but relies solely on domain randomization for generation.
Algorithm
Generation Strategy
Generator Obj
Curation Obj
Setting
POET (Wang et al. 2019
Evolution Reinforcement Learning
Minimax Minimax Regret
MCC
Population- Based
PAIRED (Dennis al. 2020
None
Single Agent
PLR (Jiag et al 20216
Random
None
Minimax Regret
Single Agent
ACCEL
Random + Evolution
Minimax Regret
Minimax Regret
Single Agent
methods, UED approaches seek to fully specify environments, rather than just goals within fixed environment.
In the symbolic AI community, environment design has been considered means to alter an environment to influence an agent's 's decisions (Zhang & Parkes 2008 Zhang et al. 2009). This was extended with automated design (Keren et al. 2017 2017||019) which seeks to redesign environments given the limitations of agents, to improve their performance. Unlike these works, ACCEL seeks to automatically design environments in order to produce curriculum for a learned agent.
Our work also closely relates to the field of Procedural Content Generation (PCG, Risi & Togelius 2020; Justesen et al., 2018), where levels are sampled from a distribution. Popular PCG settings include the Procgen Benchmark (Cobbe et al., (2200), MiniGrid (Chevalier-Boisver et al., 2018). Obstacle Tower (Juliani al. 2019p, GVGAT (Perez-Liebana et al. 2019) and the NetHack Learning Environment (Küttler et al. 2020p. This work uses the recently proposed MiniHack environment (Samvelyan et al.] 2021), which provides a flexible framework for creating diverse environments. Within the PCG community, automatically generating game levels has been of interest for more than a decade (Togelius& & Schmidhuber 2008). More recently, machine learning has proven to be effective (Summerville et al. 2018 Bhaumik al. 2020; Liu et al. 2021). Related to our work, PCGRL [Khalifa et al. 2020 Earle et al. 2021a) framed level design as an RL problem, designing environments by making incremental changes. However, it makes
of hand-designed dense
rewards, and focuses on the design of levels for human players. By contrast, ACCEL seeks to train a student agent and does not require domain-specific feedback.
CONCLUSION AND FUTURE WORK
In this paper we proposed new method for Unsupervised Environment Design (UED), ACCEL, which evolves a curriculum by editing previously curated levels. This makes it possible to constantly generate wide variety of environments at the frontier of the agent's 's capabilities, producing curricula that start simple and quickly compound. We believe ACCEL offers the best of both worlds: a principled regret-based curriculum that does not require domain-specific heuristics, alongside an evolutionary process that produces a broad spectrum of complexity catering to the agent's 's current capabilities. In our experiments we showed that ACCEL is capable of efficiently training agents that can transfer to a series of human-designed environments, outperforming competitive baselines.
For future work, it may be possible use ideas from Neural Cellular Automata to enhance the editing process (Earle et al. 2021b), possibly making use of controllable editors that can boost specific properties of levels (Earle et al. 2021a). We could also consider generative modelling approaches to level editing, training on PLR levels to produce new frontier levels. We did not explore methods to encourage levels to be diverse, but this would likely be important for larger-scale experiments. Another possibility is to actively seek levels which have high "Evolvability" (Gajewski et al., (219)). This could be increased by introducing so-called "extinction events" (Raup) 1986), which have been shown to increase Evolvability (Lehman & Mikkkulainen 2015) and are believed to play crucial role in natural evolution. Equipped with some of these ideas, we could go significantly further towards open-en endeddesssssss (Earle et al.) 2021ch. We believe it may be possible to increase the search space such that MiniHack can make broader use of the richness of the NetHack world, possibly aiding us in making progress in the full game of Nethack grand challenge in reinforcement learning.

---

Under review as a conference paper at ICLR 2022
STATEMENT
We do not perceive any potential ethical issues to arise from this work, beyond those typically associated with reinforcement learning. However, key issue RL reproducibility, and as such we will be open sourcing our code alongside the camera ready version of our paper. Both environments we used are open sourced (MiniGrid and MiniHack) and we based our code on an open source repo.
REFERENCES
Rishabh Agarwal, Marlos Machado, Pablo Samuel Castro, and Mare G Bellemare. Contrastive behavioral similarity embeddings for generalization in reinforcement learning. In International Conference on Learning Representations, 2021a.
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Mare G. Bellemare. Deep reinforcement learning at the edge of the statistical precipice. In Advances in Neural Information Processing Systems. 2021b.
Marcin Andrychowicz, Dwight Crow, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. In Isabelle Guyon, Ulrike von Luxburg. Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances Neural Information Processing Systems 30, 2017.
OpenAI: Marcin Andrychowicz, Bowen Baker, Maciek Chociej, Rafal Józefowicz, Bob McGrew, Jakub Pachocki, Arthur Petron, Matthias Plappert, Glenn Powell, Alex Ray, Jonas Schneider, Szymon Sidor, Josh Tobin, Peter Welinder, Lilian Weng, and Wojeiech Zaremba. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 39(1):3-20, 2020.
Philip J. Ball, Cong Lu, Jack Parker-Holdes and Stephen J. Roberts. Augmented world models facilitate zeoo-shot dynamics generalization from single offline environment. In The International Conference on Machine Learning, 2021.
Adrien Baranes and Pierre Yves Oudeyer. Robust intrinsically motivated exploration and active learning. pp. 1 6, 07 2009, doi: 10.1 B0.10000DELLRN.200.55555555
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, Rafal 16zefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, Ilya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota 2 with large scale deep reinforcement learning. CoRR, abs/1911 hts//191.nnm 1966006680 2019.
Lue Berthouze and Max Lungarella. Motor skill acquisition under environmental perturbations: On the necessity of alternate freezing and freeing of degrees of freedom. Adapt. Behav,, 12(1):47-64, 2004.
Debosmita Bhaumik, Ahmed Khalifa, M. C. Green, and Togelius. Tree search versus optimization approaches for map generation. In AAAI 2020, 2020.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. OpenAl Gym, 2016
Andres Campero, Roberta Raileanu, Heinrich Kuttler, Joshua B. Tenenbaum, Tim Rocktäschel,
and Edward Grefenstette. Learning with AMIGo: Adversarially motivated intrinsic goals. In International Conference on Learning Representations, 2021.
Maxime Chevalier-Boisvert,, Lucas Willems, and Suman Pal. Minimalistic gridworld environment for OpenAl Gym. httpp::/giie
com. max meaximeeee me cbcb///c///ccc hts//yygmmmmiiie minigrid 2018
John D. Co-Reyes, Suvansh Sanjeev, Glen Berseth, Abhishek Gupta, and Sergey Levine. Ecological reinforcement learning. CoRR, abs/2006. 12478, 2020.
10

---

Under review as a conference paper at ICLR 2022
Karl Cobbe, Chris Hesse, Jacob Hilton, and John Schulman. Leveraging procedural generation to benchmark reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, pp. 2048-20000 2056, 2020.
Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. In Advances in Neural Information Processing Systems, volume 33, 2020.
Aaron Dharna, Julian Togelius, and L. B. Soros. Co-generation of game levels and game-playing agents. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 16()):203-20, Oct. 2020.
Gabriel Dulac-Arnold, Daniel Mankowitz, and Todd Hester. Challenges of real-world reinforcement learning. arXiv preprint a9Xiv: 12901, 2019.
Sam Earle, Maria Edwards, Ahmed Khalifa, Philip Bontrager, and Julian Togelius. Learning controllable content generators. In IEEE Conference on Games (CoG), 2021a.
Sam Earle, Justin Snider, Matthew C. Fontaine, Stefanos Nikolaidis, and Julian Togelius. Illuminating diverse neural cellular automata for level generation, 2021b.
Sam Earle, Julian Togelius, and LB Soros. Video games as a testbed for open-ended phenomena. In IEEE Conference Games (CoG), 2021c.
Theresa Eimer, André Biedenkapp, Frank Hutter, and Marius Lindauer. Self-paced context evaluation for contextual reinforcement learning. In The International Conference on Machine Learning. 2021.
Lasse Espeholt, Hubert Soyer, Rémi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, Shane Legg, and Koray Kavukcuoglu. IMPALA: scalable distributed deep-rl with importance weighted actor-learner architectures. In Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, Proceedings of Machine Learning Research, pp. 1406-1415. PMLR, 2018
Kuan Fang. Yuke Zhu, Silvio Savarese, and Fei-Fei Li. Adaptive procedural task generation for hard-exploration problems. International Conference on Learning Representations, 2021. URL
https://openneet iew net wor.forrmmmoooooo it kv0.dx0vv0000000000
Yannis Flet- Bie-BBeriac,, Johan Ferret, Olivier Pietquin, Philippe Preux, and Matthieu Geist. Adversarially guided actor-critic. International Conference on Learning Representations, 2021.
Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse curriculum generation for reinforcement learning. In 1st Annual Conference on Robot Learning, CoRL 2017, Mountain View California, USA, November 13-15, 2017, Proceedings, volume 78 of Proceedings of Machine Learning Research, pp. 482-495. PMLR, 2017.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1515-1528, PMLR, 10-15 Jul 2018
Alexander Gajewski, Jeff Clune, Kenneth O. Stanley, and Joel Lehman. Evolvability ES: Scalable and direct optimization of evolvability. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 19, pp. 107-115, New York, NY, USA, 2019, ACM. ISBN 978-1-4533-6111 URL http:://oi. acm. w0w httpp//..1111113131111 http::///oo...ac...r10111.....11
8. doi: 02.145533211777.3328888 3321186
Dibya Ghosh, Jad Rahme, Aviral Kumar, Amy Zhang, Ryan P Adams, and Sergey Levine. Why generalization in is difficult: Epistemic pomdps and implicit partial observability. arXiv preprint arXiv:2107.06277. 2021.
Izzeddin Gur, Natasha Jaques, Kevin Malta, Manoj Tiwari, Honglak Lee, and Aleksandra Faust. Adversarial environment generation for learning to navigate the web, 2021.
11

---

Under review as a conference paper at ICLR 2022
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pp. 770-778. IEEE Computer Society, 2016. doi: 10.1 1..100/922.2006.90
Hengyuan Hu and Jakob N. Foerster. Simplified action decoder for deep multi-agent reinforcement learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL
Eorum 21=BB d= xm 3RVEWBB
Maximilian Igl, Kamil Ciosek, Yingzhen Li, Sebastian Tschiatschek, Cheng Zhang, Sam Devlin, and Katja Hofmann. Generalization in reinforcement learning with selective noise injection and information bottleneck. In Advances in Neural Information Processing Systems. 2019.
Max Jaderberg. Valentin Dalibard, Simon Osindero, Wojeiech M. Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals. Tim Green, lain Dumning, Karen Simonyan, Chrisantha Fernando, and Koray Kavukcuoglu. Population based training of neural networks. CoRR,
2017.
Nick Jakobi. Evolutionary robotics and the radical eyeloop--ofnoiiae hypothesis. Adaptive Behavior, 6(2):325-368, 1997.
Stephen James, Andrew J. Davison, and Edward Johns. Transferring end-to-end visuomotor control from simulation to real world for multi-stage task. In 1st Conference on Robot Learning. 2017.
Minqi Jiang, Michael Dennis, Jack Barker-Holdes Jakob Foerster, Edward Grefenstette, and Tim Rocktäschel. Replay-guided adversarial environment design. In Advances in Neural Information Processing Systems. 2021a.
Minqi Jiang, Edward Grefenstette, and Tim Rocktäschel. Prioritized level replay. In The International Conference on Machine Learning. 2021b.
Arthur Juliani, Ahmed Khalifa, Vincent-Pierr Berges, Jonathan Harper, Ervin Teng, Hunter Henry, Adam Crespi, Julian Togelius, and Danny Lange. Obstacle Tower: A Generalization Challenge in Vision, Control, and Planning. In IJCAI, 2019.
Niels Justesen, Ruben Rodriguez Torrado, Philip Bontrager, Ahmed Khalifa, Julian Togelius, and Sebastian Risi. Procedural level generation improves generality of deep reinforcement learning. CoRR, abs/1806. 10729, 2018
Sarah Keren, Luis Pineda, Avigdor Gal, Erez Karpas, and Shlomo Zilberstein. Equi-reward utility maximizing design in stochastic environments. In Proceedings of the International Conference on Automated Planning and Scheduling. 2017.
Sarah Keren, Luis Pineda, Avigdor Gal, Frez Karpas, and Shlomo Zilberstein. Efficient heuristic search for optimal environment redesign. In Proceedings of the International Conference Automated Planning and Scheduling, volume 29, pp. 246-254, 2019.
Ahmed Khalifa, Philip Bontrager, Sam Earle, and Julian Togelius. Pegrl: Procedural content genera- tion via reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 16(1):95-101, Oct. 2020.
Pascal Klink, Hany Abdulsamad, Boris Belousov, and Jan Peters. Self Self-paced contextual reinforcement learning. In Conference on Robot Learning. 10 2019.
Ilya Kostrikov, Denis Yarats, and Rob Fergus. Image augmentation all you need: Regularizing deep reinforcement learning from pixels. In International Conference on Learning Representations. 2021.
Heinrich Küttler, Nantas Nardelli, Alexander H. Miller, Roberta Raileanu, Marco Selvatici, Edward Grefenstette, and Tim Rocktäschel. The NetHack Learning Environment. In Proceedings of the Conference Neural Information Processing Systems (NeurIPS), 2020.
12

---

Under review as a conference paper at ICLR 2022
Michael Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas. Reinforcement learming with augmented data. In Advances in Neural Information Processing Systems 33. 2020.
Joel Lehman and Risto Mikkkulanenn. Extinction events can accelerate evolution. PloS one, 10(8): c0132886, 2015.
Jialin Liu, Sam Snodgrass, Ahmed Khalifa, Sebastian Risi, Georgios N. Yannakakis, and Julian
Togelius. Deep learning for procedural content generation. Neural Comput. Appl., 13(1), 2021. doi: 10.1007/500521002--5555
Tambet Matüsen, Avital Oliver, Taco Cohen, and John Schulman. Teacher-student curriculum learning. IEEE Trans. Neural Networks Learn. Syst. 319))3332--3377 2020.
Bhairav Mchta, Manfred Diaz, Florian Golemo, Christopher J. Pal, and Liam Paull. Active domain randomization. In Proceedings of the Conference on Robot Learning, 2020.
Russell Mendonca, Oleh Rybkin, Kostas Danilidis, Danijar Hafner, and Deepak Pathak. Discovering and achieving goals via world models, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing atari with deep reinforcement learning. ArXiv, abs/1312.5602, 2013.
Aditya Modi, Nan Jiang, Satinder Singh, and Ambuj Tewari. Markov decision processes with continuous side information. In Algorithmic Learning Theory. 2017.
OpenAI, lige Akkaya, Marcin Andrychowicz. Maciek Chociej. Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, Jonas Schneider, Nikolas Tezak, Jerry Tworek, Peter Welinder, Lilian Weng, Qiming Yuan, Wojeiech Zaremba, and Lei Zhang. Solving rubik's ' cube with a robot hand. CoRR, abs/1910.07113, 2019.
OpenAI OpenAI, Matthias Plappert, Raul Sampedro. Tao Xu, 1lge Akkaya, Vineet Kosaraju, Peter Welinder, Ruben D'Sa, Arthur Petron, Henrique Ponde de Oliveira Pinto, Alex Paino, Hyconwoo Noh, Lilian Weng, Qiming Yuan, Casey Chu, and Wojciech Zaremba. Asymmetric self-play for automatic goal discovery in robotic manipulation, 2021.
Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krahenbuhl, Vladlen Koltun, and Dawn Song. Assessing generalization in deep reinforcement learning, 2019.
Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. CoRR, abs/1710.06573 2017.
Diego Perez-Liebana, Jialin Liu, Ahmed Khalifa, Raluca D Gaina, Julian Togelius, and Simon M Lucas. General video game ai: A multitrack framework for evaluating agents, games, and content generation algorithms. IEEE Transactions on Games, 11(3):195-214 2019.
Lerrel Pinto, James Davidson, and Abhinay Gupta. Supervision via competition: Robot adversaries for learning tasks. In 2017 IEEE International Conference Robotics and Automation (ICRA), doi: 10.1 0009//CAA.201..7993
pp. 1601-1608, 2017.
Vitchyr Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew-fit State-covering self- supesiuee reinforcement learning. In Proceedings of the 37th International Conference on Machine Leurning, pp. 7783-7792, 2020.
Rémy Portelas, Cédric Colas, Katja Hofmann, and Pierre-Yves Oudeyer. Teacher algorithms for curriculum learning of deep RL in continuously parameterized environments. In Leslie Pack Kael- bling, Danica Kragic, and Komei Sugiura (eds.), 3rd Annual Conference on Robot Learning. CoRL 2019, Osaka, Japan, October 30 November 1, 2019, Proceedings, volume 100 of Proceedings of Machine Learning Research, pp. 835-853, PMLR, 2019.
Rémy Portelas, Cédric Colas, Lilian Weng, Katja Hofmann, and Pierre- Yves Oudeyer. Automatic curriculum learning for deep rl: A short survey. arXiv preprint arXiv:2003.0466 046664, 2020.
13

---

Under review as a conference paper at ICLR 2022
Justin K. Pugh, Lisa B. Soros, and Kenneth O. Stanley. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and Al, 3:40, 2016. ISSN 2296-9144. doi: 1..339/frrobt.2016.00044
Sebastien Racaniere, Andrew Lampinen, Adam Santoro, David Reichert Vlad Firoiu, and Timothy Lillicrap. Automated curriculum generation through setter-solver interactions. In International Conference on Learning Representations, 2020.
Roberta Raileanu and Rob Fergus. Decoupling value and policy for generalization in reinforcement learning. The International Conference on Machine Learning. 2021.
Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-driven exploration for procedurally- generated environments. In International Conference on Learning Representations, 2020.
Roberta Raileanu, Max Goldstein, Denis Yarats, Ilya Kostrikov, and Rob Fergus. Automatic data augmentation for generalization in deep reinforcement learning. CoRR, abs/2006. 18862, 2020.
Sharath Chandra Raparthy, Bhairav Mehta, Florian Golemo, and Liam Paull. Generating automatic curricula via self-surervvised active domain randomization. CoRR, abs/2002.07911, 2020. URL
https::/arxiv.orrg/ wwwp:axwwwi..rraa///aaaaaa/ 07911
David M Raup. Biological extinction earth history. Science, 23144)))::5288-133 1986.
Daniele Reda, Tianxin Tao, and Michiel van de Panne. Learning locomote: Understanding how environment design matters for deep reinforcement learning. In Motion, Interaction and Games, 2020.
Sebastian Risi and Julian Togelius. Increasing generality machine learning through procedural content generation. Nature Machine Intelligence, 2, 08 2020. doi: 10.10388/42255-020-00000
Fereshteh Sadeghi and Sergey Levine. CAD2RL: real single-image flight without a single real image. In Nancy M. Amato, Siddhartha S. Srinivasa, Nora Ayanian, and Scott Kuindersma (eds.), Robotics: Science and Systems XIII, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, July 12-16, 2017, 2017.
Mikayel Samvelyan, Robert Kirk, Vitaly Kurin, Jack Parker-Holder, Minqi Jiang, Eric Hambro, Fabio Petroni, Heinrich Kuttler, Edward Grefenstette, and Tim Rocktäschel. Minihack the planet: sandbox for open-ended reinforcement learning research. In Thirty-fitth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
L. J. Savage. The theory of statistical decision. Journal of the American Statistical association, 1951.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. In Proceedings of the International Conference on Learning Representations (ICLR), 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2016-2018.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driess- che, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529:484 489, 2016.
David Silver. Satinder Singh, Doina Precup, and Richard S. Sutton. Reward is enough. Artificial Intelligence, 299: 103535, 2021. ISSN 0004-3702. doi: https://doi.org/10.. 10t.1.0...111111 a016//..rtinn..000 103535.
Xingyou Song, Yiding Jiang, Stephen Tu, Yilun Du and Behnam Neyshabur. Observational overfitting in reinforcement learning. 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
14

---

Under review as a conference paper at ICLR 2022
Kenneth Stanley, Jeff Clune, Joel Lehman, and Risto Mikkkulainen. Designing neural net- works through neuroevolution. Nature Machine Intelligence. 1, 01 2019. doi: 10.1038/ s42256-018-0006
Nathan Sturtevant, Nicolas Decroocq. Aaron Tripodi, and Matthew Guzdial. The unexpected consequence of incremental design changes, In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 16, pp. 130-136, 2020.
Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play In International Conference on Learning Representations, 2018.
Adam Summerville, Sam Snodgrass, Matthew Guzdial, Christoffer Holmgård, Amy K. Hoover, Aaron Isaksen, Andy Nealen, and Julian Togelius. Procedural content generation via machine learning (PCGML). IEEE Trans. Games, 10(3):257-270, 2018.
Richard S. Sutton and Andrew G. Barto. Introduction to Reinforcement Learning. MIT Press, Cambridge, MA, USA, 1st edition, 1998. ISBN 0262193981.
Open Ended Learning Team, Adam Stooke, Anuj Mahajan, Catarina Barros, Charlie Deck, Jakob Bauer, Jakub Sygnowski, Maja Trebacz, Max Jaderberg, Michaël Mathieu, Nat McAleese, Nathalie Bradley-Schmieg, Nathaniel Wong, Nicolas Porcel, Roberta Raileanu, Steph Hughes-Fitt, Valentin Dalibard, and Wojciech Marian Czamecki. Open-ended learning leads to generally capable agents. CoRR, abs/2107. 2021.
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojeiech Zaremba, and Pieter Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEFE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, September 24-28, 2017, pp. 23-30. IEEE, 2017.
Julian Togelius and Jurgen Schmidhuber. An experiment in automatic game design. In 2008 IEEE Symposium On Computational Intelligence and Games, pp. 111-118, 2008. doi: 10.1 109//IG.
2008.5035629.
Oriol Vinyals, Igor Babuschkin, Wojeiech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, Petko Georgiev, Junhyuk Oh, Dan Horgan, Manuel Kroiss, Ivo Danihelka, Aja Huang. Laurent Sifre, Trevor Cai, John P. Agapiou, Max Jaderberg. Alexander Sasha Vezhnevets, Rémi Leblond, Tobias Pohlen, Valentin Dalibard. David Budden, Yury Sulsky, James Molloy, Tom L.. Paine, Çaglar Gülçehre, Ziyu Wang, Tobias Pfaff, Yuhuai Wu, Roman Ring, Dani Yogatama, Dario Wünsch, Katrina McKinney, Oliver Smith, Tom Schaul, Timothy Lillicrap, Koray Kavukcuoglu, Demis Hassabis, Chris Apps, and David Silver. Grandmaster level in starcraft II using multi-agent reinforcement learning. Nat., 575(7782): 350-354, 2019. doi: 10. 1038//4156--019 -86-011-1724-2
Rui Wang. Joel Lehman, Jeff Clune, and Kenneth O. Stanley. Paired open-ended trailblazer (POET); endlessly generating increasingly complex and diverse learning environments and their solutions. CoRR, abs/1901.01153. 2019.
Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeffrey Clune, and Kenneth Stanley. Enhanced POET: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning PMLR, 13-18 Jul 2020.
Research, pp.
Shimon Whiteson, Brian Tanner, Matthew E. Taylor, and Peter Stone. Generalized domains for empirical evaluations in reinforcement learning. 2009.
Amy Zhang, Nicolas Ballas, and Joelle Pincau. A dissection of overfitting and generalization in continuous reinforcement learning. CoRR, htwp/886607999 2018a.
Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. International Conference Learning Representations, 2021a.
15

---

Under review as a conference paper at ICLR 2022
Chiyuan Zhang, Oriol Vinyals, Rémi Munos, and Samy Bengio. A study overfitting in deep reinforcement learning. CoRR, abs/1804.06893, 2018b.
Haoqi Zhang and David Parkes. Value-based policy teaching with active indirect elicitation. In Proceedings of the 23rd National Conference Artificial Intelligence Volume 1, AAAL08, pp. 208-214. AAAI Press, 2008. ISBN 9781577353683.
Haoqi Zhang. Yiling Chen, and David Parkes. A general approach to environment design with one agent. Proceedings of the 2 International Jont Conference on Artifical Intelligence, LJCAL'09, pp. 2002-2008, 2009.
Tianjun Zhang, Huazhe Xu, Xiaolong Wang. Yi Wu, Kurt Keutzer, Joseph E. Gonzalez, and Yuandong Tian. Bebold: Exploration beyond the boundary of explored regions, 2021b.
Yunzhi Zhang, Pieter Abbeel, and Lerrel Pinto. Automatic curriculum learning through value disagreement. H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7648-7659, Curran Associates, Inc.,
2020.
16

---

Under review as a conference paper at ICLR 2022
A ADDITIONAL EXPERIMENTAL RESULTS
A.1 LEVEL EVOLUTION
In Fig 9 and and show additional levels produced by ACCEL for the MiniHack lava environment and MiniGrid mazes respectively. Note that in all cases, each incremental step along the evolutionary process produces a level that has high learning potential that point in time.
Figure 9: Levels generated by ACCEL. Note that in all cases, cach individual level along the evolutionary path is at the frontier for the student agent at that stage of training. As series of challenges: in the first level the lava gradually surrounds the agent, such that they initially explore multiple directions but
the edits compound to produce
the right. In the middle row we see a level where the agent always has a direct run at the goal, but corridor is evolved over time to become increasingly narrow, before being filled in the agent has go around. Finally in the bottom row the level begins with simple augmentations before moving the agent behind barrier, which results in challenging task where the agent has move diagonal direction escape
end
can only solved by going down
Figure 10: A single level evolved in the MiniGrid environment, starting from top left, ending bottom right. Throughout the process the agent experiences diverse set of challenges.
17

---

Under review as a conference paper at ICLR 2022
Figure 11: Maze evolution with the DR generator. Top shows starting DR levels, originally included in the replay buffer due to having high positive value loss. After many edits (up to 40), they produce the bottom row, which were all chosen to be in the highest 50 replay scores after 10k gradient steps. As we see, the same DR level can produce distinct future levels, in some cases multiple high regret levels.
A.2 THE EXPANDING FRONTIER
Here analyze the performance of agents levels produced by ACCEL. We have four agent checkpoints, from 5k, 10k, 15k and 20k student gradient updates. In Figure [2 we show four generations of level, where see that the later generations become harder for the 5k checkpoint, while the 20k checkpoint gets the highest learning signal (Positive Value Loss) from Generation 63.
Generation 27
Generation 45
Generation 53
Generation 63
Returns
PVL
Returns
PVL
Returns
PVL
Returns
PVL
Student Agent Checkpoint:
5000
10000
15000
20000
Figure 12:
The top row shows four levels from the lineage, generations 27, 45, and 63. Underneath each bar plot showing the Return and Positive Value Loss (PVL) for four different ACCEL policies, saved after 5k, 10k, 15k and 20k updates. At generation 27, all four checkpoints can solve the level, but the Sk checkpoint has the highest learning potential (PVL). On the right see that by generation 63, only the 15k and 20k checkpoints able achieve high return on the level.
The Evolving Frontier.
<30
30-45
45-60
>65
Returns
0.07
0.07
0.07
0.07
PVL
5000
10000
20000
Figure 13: Aggregate metrics for each band of generations. For example, "30-45" refers all the levels between generation 30-45. The later generation are harder the early agents to solve, while early agents have higher return and PVL for the earlier levels.
18

---

Under review as a conference paper at ICLR 2022
In Figure 13 we show all generations for the level included in Figure 12 grouped by generation. We then show the mean Return and Positive Value loss (PVL) for all four agent checkpoints. is clear to see that the later generations have the highest learning potential for the 20k checkpoint, with the lowest return for the 5k checkpoint.
Next in Figure 14 we show data for all generations of 20 levels, chosen those which were present in the 20k checkpoint replay buffer but also had ancestors in the 5k checkpoint buffer. For each checkpoint we plot all levels along the dimensions of Number of Blocks and Shortest Path, with the color corresponding to the solved rate. On the left, the 5k checkpoint agent can only repeatedly solve the shorter path levels with low block count. Later on, the 20k checkpoint agent performs well across the entire space.
5k
15k
20k
20
20
20
Shortest Patn
15-
15
15
15
10-
10
10
5
0
50
75
25
50
75
75
Number of Blocks
Number of Blocks
Number of Blocks
Number of Blocks
Solved
00.5
0.25-0.5
0.5-0.75
<0.25
Figure 14: How do complexity metrics relate difficulty? The plot shows the block count and shortest path length. From to right we evaluate the agents four checkpoints: 5k, 10k, 15k, 20k PPO updates. The color represents the solved rate. As we see, the 5k agent is unable to solve the levels with higher block count and longer paths to the goal, while the 20k agent is able to solve almost all levels.
A.3 FULL EXPERIMENTAL RESULTS
Lava Grid Extended Results Table 2 and Figure 15 we include the full results for the MiniHack lava experiments. The first three (Empty, 10 Tiles and 20 Tiles) evaluate the performance of the agent within its training distribution, while we also include a held-out human designed environment, LavaCrossing S9N1, ported from MiniGrid Chevalier- Boisvert al. (2018). As we see, ACCEL performs best on all of the in sample environments, while also being only one of two approaches to get meaningfully above zero in the human designed task.
Empty
Tiles
Tiles
Crossing S9N1
1.00
Salved hate
0.75
0.3
0.50
0.2
0.04
0.1
PAIRED
Minimax
DR
PLR
DR (U)
PLR (U)
ACCEL
Figure 15: Test performance, both in distribution (Empty, and 20 Tiles) and out distribution (Crossing
S9N1). Each evaluation is conducted for 100 trials. Plots show the mean and standard error across five runs.
Table Test performance four environments. Each data point corresponds to the mean (and standard error) of five independent runs, where each run is evaluated for 100 trials on each environment. indicates the generator distribution is Binomial, wherehy the generator can place 20 blocks, each is either lava tile empty. f indicates the generator first samples the number of lava tiles to place, between zero and 20, then places that many. Bold indicates being within one standard error of the best mean.
Test Environment
PAIRED
Minimax
DR
PLR
DRT
PLR1
ACCEL
Empty
0.77 0.03
0.76 0.02
0.81
0.03
0.97 + 0.03
0.89 + 0.05
0.96 0.04
1.0 + 0.0
10 Tiles
0.12 + 0.03
0,05 0.01
0.12 - 0.02
0.35 + 0.18
0.33 + 0.15
0.3 + 0.05
0.49 + 0.07
20 Tiles
0.06 : 0.01
0.11 0.04
0.06 = 0.01
0.15 0.09
0.23 0.12
0.206
0.35 - 0.08
LavaCrossing
0.0
0.0 0.0
0.0 0.0
0.01
0.05 0.05
0.0
0.05 0.04
19

---

Under review as a conference paper at ICLR 2022
Partially-Observal Navigation Next show the extended results for the MiniGrid experiments. We use a series of challenging seoo environments (see Figure [6). introduced in the UED literature (Dennis et al., 2020: Jiang et al. 2021a). We include the full results in Table B
SixteenRooms
RiomeenRooms2
SmallCorridor"
LargeCorridor"
SimpleCrossing"
FourRooms"
Labyrinth
Labyrinth2
Maze
Maze2
Maze3
PerfectMaze
11.y
Figure 16: MiniGrid Zero-Shot Environments. Those with an asterisk are procedurally generated: For Small and Large Corridor, the position the goal can be in any of the corridors, for SimpleCrossing and Four Rooms see Brovalicr-Boisveee et al. (2018) and for PerfectMaze see Jiang al. (202Ta) aa
Table Zero-Shot transfer human-designed environments. Each data point corresponds to mean (and standard error) of five independent rums, where each run is evaluated for 100 trials on each environment. indicates the generator first samples the number of blocks to place, between zero and sixty, then places that many. $ indicates the generator produces empty rooms. Bold indicates being within standard стrоr of the best mean. indicates p 0.05 Welch's t-test against PLR. Note that all methods are evaluated after 20k student updates, aside from PAIRED and Minimax which have 30k updates.
Environment
PAIRED
Minimax
DRf
PLRf
ACCEL
ACCEL$
16Rooms
0.63 0.14
0.01 + 0.01
0.87
0.06
0.95 + 0.03
1.0
1.0
16Rooms2
0.53 : 0.15
0.0 0.0
0.53
0.18
0.49 + 0.17
0.62
0.92 0.06
SimpleCrossing
0.55 0.11
0.11+0.04
0.57 0.15
0.87
0.05
0.92
0.84+0.16
FourRooms
0.46 0.06
0.14
0.77
0.64
0.08
0.72
SmallCorridor
0.37:100
0.09
1.0
0.18
1.0
LargeCorridor
0.08
0.14
0.05
0.79
0.05
1.0
Labyrinth
0.14
0.0
0.25
0.25
0.97
0.86
Labyrinth2
0.38 - 0.12
0.0
0.14
0.16
1.00
1.0
Maze
0.02 - 0.01
0.0
0.23
0.19
0.52
0.72
Maze2
0.37 + 0.13
0.0
0.16
0.74
0.93
1.0
Maze3
0.3 0.12
0.0
0.69 0.19
0.75
0.06
0.8
PerfectMaze (M)
0.32 + 0.06
0.01 +.0
0.1
0.62 0.09
0.82
0.07
Mean
0.39 + 0.03
0.05 0.01
0.62 0.05
0.71 + 0.04
0.88 + 0.04"
0.9 0.03*
Algorithm X ACCEL (Empty)
Algorithm PLR
ACCEL (DR)
PLR
0.4 0.5 0.6 0.7 0.8
0.9
1.0
P(X Y)
Probability improvement of ACCEL PLR across all the benchmark environments in Figure 16 using the open source notebook fromm Agarwal (2021b). The probability of improvement represents the probability that Algorithm outperforms Algorithm on a new task from the same distribution.
Figure 17:
As see, both versions of ACCEL significantly outperform the baselines. Particularly in the more complex environments like Labyrinth we see large gains vs. the baselines. Also note that PLR outperforms all other baselines, and ACCEL outperforms PLR. We show this in the Table with statistically significant point estimate, but also using the more robust metrics in x iable AAarwal et al. (2021b), for example the "probability of improvement" shown in Figure 17
20

---

Under review as a conference paper at ICLR 2022
Testing the Limits of Current Approaches In the experimental section showed the results for a large procedurally generated maze, of size 51x51. ACCEL averaged a 53% and 52% success rate when using the empty DR generator respectively, consider going even further. We tested both versions ACCEL, as well as DR and PLR, on an even larger maze, this time 101x101 101, shown in Figure [8] Note that this would be challenging human players, since the agent has partially observable view. The performance of all methods is significantly weaker, with DR and PLR achieving a mean of 4% success rate. However, ACCEL still outperforms, achieving 7% and 8% success rate with the DR and empty generators respectively. We believe this point the bottleneck for further improvement may not be the curriculum, but instead the LSTM-bbased policy which has to remember all previous paths, solve the maze in the allotted 20,402 steps.
next best PLR with 25%. Now
for
Figure 18: PerfectMazesX1.. A 101x101 seneddurally-eeeraatee MiniGrid environment. The agents have to transfer zero-shot from training in 1.5155 grid. This environment is challenging even for humans, since the agent only has partially observable view, it requires memorizing the current location all times ensure exploring corners of the grid.
A.4 ADDITIONAL EXPERIMENTS
In this section we show a series of additional experiments to understand the performance of ACCEL.
The Sensitivity of Domain Randomization Consider simple parameterized grid world environ- ment where an agent has to navigate towards goal. Each level varies in terms of the location of the agent, goal and placement obstacles. When these obstacles are walls the agent is able learn quickly, achieving high performance on the training distribution. However, when these obstacles are lava, which causes instant death on collision, the agent unable learn (Figure 19 a). left). If we change the DR parameterization to not only sample the locations of the lava tiles, but the number of tiles to place, then the agent does indeed learn (Figure 19 a), right). This subtle change illustrates the sensitivity of DR to the environment parameterization. We refer to this problem as "curse of dimensionality for UED", whereby increasing the design space leads to a crowding out levels that effective for learning.
In Figure b) we show the test performance for the three DR agents at the same checkpoint (1000 updates), as well PL.R agent using the Binomial DR levels. Despite the poor performance for the
21

---

Under review as a conference paper at ICLR 2022
Levals
Levels
L0Tiles
3.5
Positive Volue Loos
Training Return
Binomial
Salved Rate
7.
Lava Walls
Unitorm
2000
2000
Floed
Lnii (BR))
Student PPO Updates Student PPO Updates
Bin
(a) Training Performance
(b) Test Return
(c) Level Profile
Figure 19: Small grid results: a) On the left, compare training with DR, randomizing obstacles that walls lava, on the right see that when the obstaeles are lava the choice of DR parameterization has a significant impact on performance. applied to the Binomial (Bin) levels is able to produce strong agent, why? In c) we see density plot of DR and PLR levels, showing frequency by Return and Positive Value Loss, which shows PLR curates solvable levels where the agent receives learning signal.
b) we see the test performance of these agents after 1 updates, PLR
DR agent, PLR is able to achieve strong performance, outperforming even the Uniform DR agent. To how this is possible, in Figure [9cc) we compare the density of levels sampled by DR those in the PLR buffer, sorted by Return and Positive Value Loss. Notably, the levels chosen by PLR are inherently higher return levels, thus,
that PLR is able find the frontier without handcrafted heuristics. This example illustrates the importance of having a sufficient quantity of frontier levels. Indeed, the success of PLR hinges on the ability to reliably sample new levels at the ever-changing frontier of the agent's capabilities. This is the key motivation for ACCEL.
Next, in Figure 20 we show the performance of the three DR agents when tested on each other's training distributions after one thousand training steps. All agents perform worst on the Fixed levels, slightly better on the Binomial ones, with the best performance on Uniform. Notably, even the Fixed agent, the weakest of the three, is able to see almost double the performance on the Uniform levels. This indicates that a key ingredient learning potential having sufficient number of easier levels to generate learning signal. Indeed, this noted in Jiang et al. (022b) in their MiniGrid experiments.
Fixed Agent
Binomial Agent
Uniform Agent
Return
Binomial
Uniform
Figure 20:
Performance of agents trained on different level distributions when tested on cach the distributions. It is clear to see the Uniform distribution contains more solvable levels-al all three agents perform better on it.
Ablation Studies To investigate the design choices that led to the success of ACCEL, consider variety of ablations:
ACCEL Using the DR generator.
Edit Batch The same ACCEL algorithm but editing the entire replay batch rather than the "casy"
levels from the batch.
Learned Editor The same algorithm changing only the editor, which is optimized for positive value loss.
No Editor This is an ablation on the algorithm structure, we use Algorithm I but sample more DR levels instead of editing.
Each of these uses the same exact structure, sampling levels from the DR distribution 10% of the time, and editing levels after replaying from the curator. For the first, we edit the entire replay batch, rather than just the top four casiest (high return minus positive value loss) that experiments. The results after 10k updates are shown in Table4 As we see, Editing the batch levels performs slightly worse than easy, while there is also decrease in performance for the learned editor.
in the main
22

---

Under review as a conference paper at ICLR 2022
Table Zero-Shot transfer to human-designed environments. Each data point corresponds to mean (and standard error) of five independent runs, where each run evaluated for 100 trials on each environment. All methods use DR generator which places between zero and sixty blocks.
Test Environment
ACCEL
Edit Batch
Learned Editor
No Editor
16Rooms
1.0
0.76 + 0.19
0.9 0.07
0.84 + 0.06
16Rooms2
0.51 0.28
0.23 + 0.16
0.41 + 0.19
0.68 : 0.18
SimpleCrossing
0.8
1.0
0.9
0.75 = 0.05
FourRooms
0,85 0.05
0.88 0.04
0.88 = 0.05
SmallCorridor
0.1
0.74
0.6
0.7
LargeCorridor
0.91
0.75
0.56
0.63 0.18
Labyrimth
0.02
0.15
0.99
0.67
Labyrimth2
0.03
0.83
0.7
0,48
Maze
0.28
0.07
0,57
0.15
Maze2
0.24
0.18
0.65
0,23
Maze3
0.79
0.08
0.95 0.05
0.56 0.17
Mean
0.79 + 0.04
0.76 + 0.04
0.74 0.04
0.58 + 0.05
Note however that of these ablations still outperform the next best baseline (PLR, mean 0.69). Finally, the ablation using additional DR levels instead of edited ones performs poorly, showing the strong performance for ACCEL comes from editing rather than the structure of the algorithm.
Concentration
Return
0.5
0.0
0.0
Small
Large
Small
Large
Figure 21: Replay buffer diversity return in the lava environment. On the left show the concentration of the replay buffer, measured the percentage of the top 100 high-regret levels that be produced by just ten parents. On the right we compare the average return on ten-tile test enviromments. "Small" corresponds a buffer of size 4k, with no generator, while "Large" indicates buffer of size 10k, using a generator 10% of the time.
Diversity of the Level Buffer we compare a buffer of size 4k with no DR sampling against our method with buffer size of 10k and 10% sampling. The plots show the proportion of the top 200 levels produced by just ten initial generator levels, with a significant increase for the smaller buffer. We also compare the performance of the two agents test levels with ten tiles, showing clear outperformance for the lower concentration agent. is likely that hyperparameters alone will not be sufficient if want scale ACCEL more open-ended problems, which leave to future work.
B IMPLEMENTATION DETAILS
In this section detail the training procedure for all our experiments. Training for all methods is conducted on a single V100 GPU, using ten CPUs. The codebase is built on top of open source repos. For PAIRED and Minimax
results from the authors of ofain et al. (022a).
B.1 ENVIRONMENT DETAILS
Learning with Lava The MiniHack environment is an open-source Gym (Brockman et al. 2016 environment which provides a wrapper around the full game of NetHack via the NetHack Learning Environment Küttler et al. (2020). MiniHack allows users (or agents) the ability the fully specify environments leveraging the full game engine from NetHack. For our experiments we use a simple 7x7 grid, and allow the agent to place lava tiles in any location of their choice. We considered three different DR parameterizations
Figure 19 These are: "Fixed" which always places ten lava blocks, "Binomial" which places twenty blocks, with 50-50 chance of the block being lava nothing, and "Uniform" which selects the number of lava blocks to place from the range [0, 20). The reward is sparse, with the agent receiving +1 for reaching the goal, with per timestep penalty of 0.01.
23

---

Under review as a conference paper at ICLR 2022
Partially-Observable Navigation Each maze consists of a 15 x 15 grid, where each cell can contain a wall, the goal. the agent, or navigable space. The student agent receives a reward of 1 T T/Tmax upon reaching the goal, where T is the episode length and T max is the maximum episode length (set to 250). Otherwise, the agent receives a reward of O if fails to reach the goal.
Table 5: Total number of environment interactions for 20k PPO updates.
PPO Updates
PLR
ACCEL (DR)
ACCEL (Empty)
20k
327M
347M
369M
B.2 ENVIRONMENT DESIGN PROCEDURE
The environment design procedure works as follows: at each timestep the adversary agent receives an observation consisting of map of the entire level and then takes two dimensional action, consisting of an object and a location, which can be anywhere in the grid. This is similar to several recent works Dennis al. (2020); [iang et al./ (2021b) a): Khalifa al. (2020). For MiniGrid the object always wall. For both methods, the goal and agent location are placed in the final two steps.
When editing, the editor has five steps to alter the environment. For the lava environment we only edit to add or remove lava tiles, while for MiniGrid we allow the editor to also change the goal location. lava or walls (or lava) are placed in the current location of the goal or agent, then these replace goal or agent, which must then be relocated in the final two steps of the editing episode. If the editor attempts to remove the goal or agent location the final two steps then the action void.
B.3 HYPERPARAMETERS
The majority of hyperparameters are inherited from previous works such Dennis al. (2020): ;
Jiang et al. 2222bb a) with few small changes. The first, for MiniHack we use the agent model from the NetHack paper (Kittler et al., 2020). using the glyphs and blstats as observations. The agent has both a global and a locally cropped view (produced using the coordinates in the blstats).
For MiniHack we conduct grid search across the level replay buffer size (4000, 10000) for both PLR and ACCEL, and for ACCEL we sweep across the edit method from (random, positive value loss} where positive value loss equates learned editor. For MiniGrid we maintain the replay buffer size from Jiang et al. (2021a) and only conduct the ACCEL grid search over the edit objective, again running both {random, positive value loss), as well as the levels edit from (easy, batch} and replay rate from {0.8, 0.9). For MiniGrid, we follow the protocol from Jiang et al. (2021a) and select the best hyperparameters using the validation levels ( [16oooms, Labyrinth, Maze The final hyerpparameters chosen are shown in Table 6
24

---

Under review as a conference paper at ICLR 2022
Table 6: Hyperparameters used for training each method in the maze and car racing environments.
Parameter
MiniHack (Lava)
MiniGrid
PPO
Y
0.995
0.995
AGAE
0.95
0.95
PPO rollout length
256
256
PPO epochs
5
PPO minibatches per epoch
PPO clip range
0.2
0.2
PPO number of workers
32
32
Adam learning rate
lc-4
lc-4
Adam
le-5
1c-5
PPO max gradient norm
0.5
PPO value clipping
yes
yes
return normalization
value loss coefficient student entropy coefficient
0.5
0.5
generator entropy coefficient
0.0
0.0
ACCEI.
Edit rate,
1.0
1.0 DR: 0.9, Empty: 0.8 4000
Replay rate, p
0.9
Buffer size, K Scoring function
10000
positive value loss positive value loss batch rank 0.3
positive value loss random casy rank
Edit method Levels edited Prioritization Temperature,
0.3
Staleness coefficient,
0.5
0.5
PLR
Scoring function
positive value loss 0.5
positive value loss
Replay rate, p Buffer size, K
0.5
10000
4000
25


Reviews:
[{"review_id": "s8eSac5sLqn", "reviewer": "Reviewer_Sh63", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strength\nI am convinced that this is generally a useful problem to solve, and the existing results seem good. \nThe paper is easy to follow, the method is clearly explained, and the experiment is well presented.\n\n## Weakness\n\nI would say the environment considered are too simple, where the editing functions are fairly restrictive to the kind of \"changing the landscape of the level\" kind. I would have liked experiments where the dynamics of the game can be altered, for instance, the game of pong or break out with additional balls in play, or maybe mario or minecraft where the agent and the world interacts in richer ways. If we are calling them levels, I truly expect it should work for a more extensive level editor.\n\nIt is still unclear to me why the proposed method solves the problem of not having the editor generating levels that are straight up unsolvable. Or, put it in another way, how do you measure regret of a newly generated level without access to pi* ? Maybe I mis-read part of the paper but I could not find the answer to this fairly important question. Perhaps the answer to this question should be highlighted further?\n\nminor: \nI appreciated the consistent usage of pink to indicate ACCEL results, making the result section easy to read.", "summary_of_the_paper": "A simple method of curriculum design by editing existing levels solvable by the agent to more challenging ones. Empirically it performs well, as it resolves the difficulty of randomly searching globally for a challenging curriculum by building on already challenging ones incrementally. ", "summary_of_the_review": "there is not much to say except that this is an intuitive solution to a good problem. the results over existing tasks look promising, but it would really benefit from more complex environments and edits, where the agents and environments interact in more ways than simply pathing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hejdUFP8MF", "reviewer": "Reviewer_dd8g", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n\n**Strenghts:**\n\n- The idea is straight-forward.\n- The paper is well-written.\n- Table 1 is a nice comparison\n- S.4 The results seems mostly good. (On some levels, DR performs on-par and that's never really explained)\n\n**Weaknesses:**\n\n- W.1 I think it's hard to generalize this method to other domains without a lot of domain knowledge on what constitutes small incremental changes for the agent. For example I could see this being applied to generate a curriculum for a robot arm to learn grasping different objects by incrementally deforming a mesh but I think a lot of trial-and-error would be required to find the right deformation size that's enough change to be interesting but not enough to make grasping the object physically impossible. So maybe the authors could give a few examples of how this applies to other possibly non-discrete domains or if the paper should get rejected, include an experiment in a non-gridworld setting (i.e. something where it's not trivial what the incremental changes are), like the POET paper.\n- W.2 Clarity - (a) Is Fig.4 reported on a held-out test set or during training? Because if it's from during training, the level difficulty would dictate the meaning of the return plot. So maybe a different metric would be better like return divided by  difficulty metric (like shortest path length) or something like that. (b) How do you calibrate the threshold that the PLR score has to match?  (c) In Fig.6, why is DR performing on-par with ACCEL in 3 cases?\n\n**Nitpicks & Questions:**\n\n- Q.1 Fig.2 is well-made but unintuitive and I don't think in its current state it does a great job at summarizing your method: (a) The order of things is unclear. Adding numbers to indicate the order of operations would be helpful. (b) The generator isn't really crucial in that sure, it creates the initial set of levels but shouldn't it generate them into the level buffer on the left? From the current diagram it's not clear if the generator is a one-off or a recurring thing. (c) What's the \"Curator\" in practice? The level buffer + threshold? I.e. if a given level has a PLR value above the threshold, it's considered ready for play? This is a very personal opinion but I think \"Curator\" implies more of an active system than what's currently there. (d) Why is there a red-tinged level in the level buffer? (e) Why are there 2 arrows going from the student into the level buffer? (f) What is \"update buffer\" from the student?\n- Q.2 I feel like you're glossing over a lot of non-uniform domain randomization literature that's also maintaining a population of environments and tries to make them harder one step at a time like ADR, and SS-ADR [1,2]. Wouldn't these methods also work (similarly) to generate the curriculum for your agent?\n\n**References:**\n\n- [1] Mehta, Bhairav, Manfred Diaz, Florian Golemo, Christopher J. Pal, and Liam Paull. \"Active domain randomization.\" In Conference on Robot Learning, pp. 1162-1176. PMLR, 2020.\n- [2] Raparthy, Sharath Chandra, Bhairav Mehta, Florian Golemo, and Liam Paull. \"Generating Automatic Curricula via Self-Supervised Active Domain Randomization.\" arXiv preprint arXiv:2002.07911 (2020).\n\n", "summary_of_the_paper": "The paper introduces the idea of adding small incremental changes to grid world levels, to create an automatic curriculum for navigating agents.", "summary_of_the_review": "The paper feel like it's a small incremental change to existing literature and since I can't really imagine how this is going to generalize to non-gridworld domains, I can't recommend acceptance at the moment. If the authors could maybe include additional discussion of how their method applies to other environments or better, include experiments in non-gridworld settings, I would change my rating.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "d70yJweg2vl", "reviewer": "Reviewer_MHvz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe main idea of the paper is intuitively reasonable and the experimental section shows promising performance on the investigated tasks. The related work section is extensive and adequately situates the conducted research in a broad context.\n\nWeaknesses:\n\nAlthough the actual idea behind the paper is very incremental, the reader is still left with questions particularly w.r.t. details of the method and Remark 1:\n- In Remark 1, the authors state that if their method finds a Nash Euqilibrium, then the student policy is following a minimax regret strategy. I understand that the authors take this result from the Robust PLR paper, to which their method is very similar. However, I have certain concerns regarding this statement:\n    - The proofs in the Robust PLR paper are relying on the assumption that the replay teacher is utilizing the true regret to guide its sampling. However, there is no guarantee that either the MaxMC or PositiveValueLoss are actually estimating the true regret in a realistic setting. If e.g. an agent is not observing any reward signal in a sparse reward task, it can have zero residuals by predicting a value of 0 in all states, although there may exist a policy solving the task. In this case, MaxMC and PositiveValueLoss would not estimate the true regret.\n     - By using the level editing scheme, the second teacher in the dual curriculum seems to employ a different utility function than the constant one assumed in Robust-PLR. Does this change the theoretical results?\n     - These disconnects between the theory in the Robust-PLR method and the presented method should be carefully addressed in order to avoid false conclusions from reader of the papers.\n- Looking at Table 5, it is unclear whether the additional environment interaction required to estimate the regret on the edited levels is taken into account in the presented results. Table 5 already shows that the number of environment steps differs by around 10% between methods. Can the authors explain the reason for this difference? Further, the plots in the main paper use \"Student PPO Updates\" as the x-axis unit. I guess that this unit only takes into account the environment steps taken in levels WITHOUT the stop gradient, i.e. does not take into account the additional required evaluations incured by the level generator? Given that multiple new levels can be generated for each level selected for student training, this could be a high hidden cost.\n- From the statements at the beginning and end of Section 4.2, it seems that ACCEL does not use the random level generation, as the authors state that \"for ACCEL we begin with empty rooms and randomly edit the block locations\" and further investigate an ablation where they edit uniformly sampled levels. If the regular ACCEL algorithm is not using the domain randomization, Algorithm 1 yields a wrong picture of the ACCEL algorithm, as the random sampling case will never take place in practice.\n\nGiven the large amount of space that the authors spend on high-level introduction and discussion w.r.t. related work, it seems unsatisfying that these technical details are not clarified in the main paper.\n\nMinor Points:\n - Question: Would it be possible to compare to some adaptive domain randomization methods that do not just randomly sample tasks? Or are they ill-suited for the investigated experiments? If so, why? It would be interesting to see how a method following a different methodology performs in these experiments.\n - Another related work that should be mentioned is the work on contextual MDPs [1], which is conceptually similar to the UPOMDPs used to model the space of possible tasks.\n\n[1] Modi, Aditya, et al. \"Markov decision processes with continuous side information.\" Algorithmic Learning Theory. PMLR, 2018.", "summary_of_the_paper": "The work proposes an extension to the recently proposed \"Robust Prioritized Level Replay\" (R-PLR) method that aims to train RL agents capable of generalizing to a large range of parameterized tasks by curating a curriculum over training tasks. The authors show that by editing levels that are at the frontier of the current agent capabilities instead of proposing novel ones by random sampling, the performance of agents trained with R-PLR can be further increased.", "summary_of_the_review": "The incremental nature of the method in combination with the unclarity w.r.t. details and theory behind the method are not allowing me to recommend acceptance. I may improve my score if my concerns are adequately addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FZ2oimYEKK", "reviewer": "Reviewer_Xz9V", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper puts forth compelling evidence that it is the state-of-the-art UED algorithm, at least within experimental domains it considers. Its suite of baselines (DR, PAIRED, PLR, Minimax adversarial) are to my knowledge well-chosen: PAIRED and PLR represent prior state-of-the-art UED approaches, and DR and Minimax adversarial simpler baselines. It highlights, by certain measures, higher levels of emergent complexity as well as superior performance on heldout environments both within the training distribution and outside of it. While some comparisons (esp. the Lava ones) show modest gains, others show more meaningful ones, especially the PerfectMaze heldout environment performance. Aside from the main comparison, it contains ablation studies helpful for understanding the utility of various choices made.\n\nThe paper is well-written and fairly easy to understand. The authors make effective summaries: Figure 2 and Algorithm 1 (especially with the highlighted difference from PLR, which can be confusing otherwise) are useful, and Table 1 is helpful as well.\n\nMy main criticism is that the evaluations seem somewhat limited in scope. While Lava and MiniGrid comparisons of this form are standard for UED methods, they are not the only ones, and in particular, they seem to be the most obvious contenders for an editing-type approach to be successful. As the paper points out, these environments have a natural empty-room starting point from which to build the curriculum and edit off of. These edits naturally seem to curricularize and, small edits easily make for what can be readily interpreted as reasonable additions for training: edits that functionally change how an agent must explore, encouraging exploration generally, or data augmentations that change irrelevant bits. Other benchmarks that existing works use (CarRacing, MuJoCo Hopper, Procgen) intuitively have a different flavor. This makes me wonder whether this method is useful beyond these sorts of environments that this sort of editing process is intuitively suited for.\n\nThe ablation study also raises questions. If I am interpreting this correctly, it seems to show that, at least on MiniGrid metrics, several versions with pieces stripped out perform statistically very similarly, except when editing is removed, which substantially drops performance. This makes me think two things. (1) It heightens my worry about the limited scope of evaluations, where editing seems tailor-made to succeed. (2) It makes me wonder whether something a good deal simpler than that proposed algorithm works just as well.\n\nOne choice that I found odd was the inclusion of Figure 4 in the main text but the placement of Figure 15 in the appendix. While emergent complexity is interesting to see, it is hard to judge whether obtaining higher scores on these metrics is objectively \"good\" (and e.g. I can imagine ways in which adding more lava tiles is not particularly useful towards an end performance objective. Figure 15 is, on the other hand, a more straightforward comparison of methods.\n\nMinor: Figure 4 color choices are confusing. If I am reading correctly, (b) contains information entirely about the ACCEL runs, but it uses the same color scheme as the baseline.", "summary_of_the_paper": "This paper introduces Adversarially Compounding Complexity by Editing Levels (ACCEL). ACCEL is an Unsupervised Environment Design (UED) algorithm, a method of generating a curriculum of environments so as to train agents that generalize well to either a training distribution of environments or off-distribution environments. ACCEL bares similarity to a recent addition in the UED literature, Robust PLR, but importantly uses an editor to modify previously seen environments. Edited levels are used if they satisfy a criterion based on the PLR score, and hence this can be thought of as a sort of evolutionary algorithm.\n\nAfter introducing ACCEL, the paper presents a series of experiments in the Lava grid and Minigrid environments, benchmarking ACCEL against a suite of UED and simpler baselines. It demonstrates emergent complexity generated in algorithms' curricula (with metrics such as number of lava tiles/blocks, shortest path length) as well as generalization to held-out levels.", "summary_of_the_review": "This paper presents a novel UED approach that presents performance gains on several baselines. My chief concern is that the benchmarks are limited in scope to situations that seem most likely for an editing process to succeed, whereas prior work demonstrates efficacy in domains that seem less suited for editing approaches. I recognize that this is an intuitive judgement about the benchmarks on my part; if the authors can put forth a compelling argument that the experiments are not so limited in scope, I would be inclined to raise my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the problem of Unsupervised Environment Design to train more robust agents. The proposed method trains RL agents by generating a curriculum of training tasks to enable agents to generalize to many tasks. The key contribution is an algorithm to generate this curriculum by incremental edits of the grid world environments. The reviewers all agreed that the paper is well-written and the method is intuitive. However, the weakness of this work is also obvious: the proposed method is only evaluated in grid worlds, and it's unclear how the editing approach can be easily generalized to more complex environments. This submission would benefit from more comprehensive evaluation in non-grid world environments, especially given that the compared baselines have results in other environments too.
Decision: Reject