Replay-Guided Adversarial Environment Design
Authors: Minqi Jiang
Michael D Dennis
Jack Parker-Holder
Jakob Nicolaus Foerster
Edward Grefenstette
Tim Rocktäschel
Venue: NeurIPS 2021 Poster (2021)
Keywords: deep reinforcement learning
multi-agent reinforcement learning
self-supervised learning
environment design
curriculum learning
continual learning

Abstract: Deep reinforcement learning (RL) agents may successfully generalize to new settings if trained on an appropriately diverse set of environment and task configurations. Unsupervised Environment Design (UED) is a promising self-supervised RL paradigm, wherein the free parameters of an underspecified environment are automatically adapted during training to the agent's capabilities, leading to the emergence of diverse training environments. Here, we cast Prioritized Level Replay (PLR), an empirically successful but theoretically unmotivated method that selectively samples randomly-generated training levels, as UED. We argue that by curating completely random levels, PLR, too, can generate novel and complex levels for effective training. This insight reveals a natural class of UED methods we call Dual Curriculum Design (DCD). Crucially, DCD includes both PLR and a popular UED algorithm, PAIRED, as special cases and inherits similar theoretical guarantees. This connection allows us to develop novel theory for PLR, providing a version with a robustness guarantee at Nash equilibria. Furthermore, our theory suggests a highly counterintuitive improvement to PLR: by stopping the agent from updating its policy on uncurated levels (training on less data), we can improve the convergence to Nash equilibria. Indeed, our experiments confirm that our new method, PLR$^{\perp}$, obtains better results on a suite of out-of-distribution, zero-shot transfer tasks, in addition to demonstrating that PLR$^{\perp}$ improves the performance of PAIRED, from which it inherited its theoretical framework.

Replay-Guided Adversarial Environment Design
Minqi Jiang" UCL, FAIR
Michael Dennis*
Jack Parker-Holder University of Oxford
UC Berkeley
Jakob Foerster FAIR
Edward Grefenstette
Tim Rocktäschel UCL, FAIR
UCL, FAIR
Abstract
Deep reinforcement learning (RL) agents may successfully generalize to new settings if trained on an appropriately diverse set of environment and task configurations. Unsupervised Environment Design (UED) is a promising self- supervised RI. paradigm, wherein the free parameters of an underspecified environment are automatically adapted during training to the agent's s capabilities, leading to the emergence of diverse training environments. Here, we cast Prioritized Level Replay (PLR), empirically successful but theoretically unmotivated method that selectively samples randomly-generatee training levels, as UED. We argue that by curating completely random levels, PLR. too, can generate novel and complex levels for effective training. This insight reveals a natural class of UED methods call Dual Curriculum Design (DCD). Crucially, DCD includes both PLR and a popular UED algorithm, PAIRED, as special cases and inherits similar theoretical guarantees. This connection allows to develop novel theory for PLR, providing a version with robustness guarantee at Nash equilibria. Furthermore, theory suggests highly counterintuitive improvement PLR: by stopping the agent from updating its policy on uncurated levels (training on less data), we can improve the convergence Nash equilibria. Indeed, our experiments confirm that new method, PLR- obtains better results suite of aattof-diitribution. zero-shot transfer tasks, in addition to demonstrating that PLR- improves the performance of PAIRED, from which it inherited its theoretical framework.
Introduction
While deep reinforcement learning (RL) approaches have led to many successful applications in challenging domains like Atari [21]. Go [35], Chess [36], Dota [4], and StarCraft [40] in recent years, deep RL agents still prove be brittle, often failing transfer environments only slightly different from those encountered during training [44, 9]. To ensure learning of robust and well-generalizing policies, agents must train sufficiently diverse and informative variations of environments (e.g. Section 3.1 of [8]. However, it is not always feasible to specify an appropriate training distribution or generator thereof. Agents may therefore benefit greatly from methods that automatically adapt the distribution over environment variations throughout training [10, 17]. Throughout this paper we will call particular environment instance or configuration (e.g. an arrangement blocks, race tracks, or generally any of the environment's 's constituent entities) a level.
Two recent works [10, 17] have sought to empirically demonstrate this need for more targeted agent- adaptive mechanism for selecting levels on which to train RI. agents, so to ensure efficient learning and generalization to unseen levels-as well provide methods implementing such mechanisms. The first method, Protagonist Antagonist Induced Regret Environment Design (PAIRED) [10),
Equual contribution. Correspondence msjefb. com and mi michaell_demiss@errklllyy
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

(a) DR
(b) PAIRED
(c) REPAIRED
(d) PLR
(e) Human
Figure 1: Randomly drawn samples of CarRacing tracks produced by different methods. (a) Domain Randomization (DR) produces tracks of average complexity, with few sharp turns. (b) PAIRED often overexploits the difference in the students, leading to simple tracks that incidentally favor the antagonist. (c) REPAIRED mitigates this degeneracy, recovering track complexity. (d) PLR selects the most challenging randomly generated tracks, resulting in tracks that more closely resemble human-designed tracks, such as (e) the Nürburgring Grand Prix.
introduces a self-supervised RL paradigm called Unsupervised Environment Design (UED). Here, an environment generator (a teacher) is co-evolved with student policy that trains levels actively proposed by the teacher, leading to a form of adaptive curriculum learning. The aim of this coevolution is for the teacher to gradually learn to generate environments that exemplify properties of those that might be encountered at deployment time, and for the student to simultaneously learn a good policy that enables gero-shot transfer to such environments. PAIRED's ' specific adversarial approach to environment design ensures a useful robustness characterization of the final student policy in the form of minimax regret guarantee [31] assuming that its underlying teacher-student multi-agent system arrives at a Nash equilibrium (NE, 24]. In contrast, the second method, Prioritized Level Replay (PLR) [17], embodies alternative form of dynamic curriculum learning that does not assume control of level generation, but instead, the ability to selectively replay existing levels. PLR tracks levels previously proposed by black-box environment generator, and for each, estimates the agent's learning potential in that level, in terms of how useful it would be to gather new experience from that level again in the future. The PLR algorithm exploits these scores to adapt schedule for revisiting or replaying levels to maximize learning potential. PLR has been shown to produce scalable and robust results, improving both sample complexity of agent training and the generalization of the learned policy in diverse environments. However, unlike PAIRED, PLR is motivated with heuristic arguments and lacks a useful theoretical characterization of its learning behavior.
In this paper, we argue that PLR is, in and of itself, an effective form UED: Through curating even randomly generated levels, PLR can generate novel and complex levels for learning robust policies. This insight leads to a natural class of UED methods which we call Dual Curriculum Design (DCD). In DCD, student policy is challenged by a team of co-evolving teachers. One teacher actively generates new, challenging levels, while the other passively curates existing levels for replaying, by prioritizing those estimated to be most suitably challenging for the student. We show that PAIRED and PLR are distinct members of the DCD class of algorithms and prove in Section 3 that all DCD algorithms enjoy similar minimax regret guarantees to that of PAIRED.
We make use of this result to provide the first theoretical characterization of PLR, which immediately suggests a simple yet highly counterintuitive adjustment to PLR: By only training trajectories in replay levels, PLR becomes provably robust NE. We call this resulting variant PLR (Section 4). From this perspective, PLR effectively performs level design in a diametrically opposite manner to PAIRED through prioritized selection rather than active generation. A second corollary to the provable robustness of DCD algorithms shows that PLR can be extended make use of the PAIRED teacher as level generator while preserving the robustness guarantee of PAIRED, resulting in method we call Replay-Enhanced PAIRED (REPAIRED) (Section 5). We hypothesize that in this arrangement, PLR plays complementary role to PAIRED in robustifying student policies.
Our experiments in Section investigate the learning dynamics of PLR- REPAIRED, and their replay-free counterparts
challenging maze domain and novel continuous control UED setting based on the popular CarRacing environment [5]. In both of these highly distinct settings, our methods provide significant improvements over PLR and PAIRED, producing agents that can perform out-of-distributte (OOD) generalization to a variety of human designed mazes and Formula I tracks.
In summary, we present the following contributions: (i) We establish common framework, Dual Curriculum Design, that encompasses PLR and PAIRED. This allows us to develop new theory, which provides the first robustness guarantees for PLR at NE as well for REPAIRED, which

---

augments PAIRED with a PLR-based replay mechanism. (ii) Crucially, our theory suggests a highly counterintuitive improvement to PLR: the convergence to NE should be assisted by training on less namely data when using P by only taking gradient updates from data that originates from the PLR buffer, using the samples from the environment distribution only for computing the prioritization of levels in the buffer. (iii) Our experiments in a maze domain and a novel car racing domain show that our methods significantly outperform their replay-free counterparts in zero-shot generalization. We open source our methods at https:// /tt:://gttttt com wtt.////acboorseerrrccoo//c////e
Background
2.1 Unsupervised Environment Design
Unsupervised Environment Design (UED), as introduced by [10], is the problem of automatically
designing a distribution of environments that adapts to the learning agent. UED is defined in terms of an Underspecified POMDP (UPOMDP), given by .M (A, O O S.M T. I.M, RMM, ,7), where A is a set of actions, is a set of observations, is a set of states, T S x x θ + (S) is a transition function, I S -> O is observation (or inspection) function, R S - R is reward function, and F is a discount factor. This definition is identical to a POMDP with the addition of O to represent the pee-parameters of the environment. These parameters step and incorporated into the transition function TM S x A x θ + (S)) For example, θ could represent the possible positions of obstacles in a maze. We will refer to the environment resulting from a fixed 0 E @ as Ms, or with a slight abuse of notation, simply 0 when clear from context. We define the value of æ in Mg to be (T)) = BE =i= "rY"]] where are the rewards attained by π in Mg. Aligning with terminology from [17], we refer to fully- selly-speeified environment as level.
be distinct at every time
2.2 Protagonist Antagonist Induced Regret Environment Design
Protagonist Antagonist Induced Regret Environment Design [PAIRED, 10] presents a UED approach consisting of simultaneously training agents in a three player game: the protagonist nA and the antagonist лH are trained in environments generated by the teacher Ò. The objective of this game is defined by AB. = Eg_ [REeg_RRRRRT(CC AT TB)], where regret is defined by REGRET (T),TH) (TT) (TTA). The protagonist and antagonist are both trained to maximize their discounted environment returns while the teacher is trained to maximize U. Note that by maximizing regret, the teacher is disincentivized from generating unsolvable levels, which will have a maximum regret of O. As shorthand, we will sometimes refer to the protagonist and antagonist jointly as the student agents. The counterclockwise loop beginning the student agents in Figure summarizes this approach, with the students being both the protagonist and antagonist.
As both student agents grow more adept solving different levels, the teacher continues to adapt its level designs to exploit the weaknesses of the protagonist in relation to the antagonist. As this dynamic unfolds, PAIRED produces an emergent curriculum of progressively more complex levels along the boundary of the protagonist's capabilities. PAIRED is a creative method in the sense that the teacher may potentially generate an endless sequence of novel levels. However, as the teacher only adapts through gradient updates, it is inherently slow to adapt to changes in the student policies.
2.3 Prioritized Level Replay
Prioritized Level Replay [PLR, 17] is an active-learning strategy shown to improve a policy's 's sample efficiency and generalization to unseen levels when training and evaluating on levels from a common UPOMDP, typically implemented as seeded simulator. PLR maintains level buffer A of the top K visited levels with highest learning potential as estimated by the time-averaged LI value loss of the learning agent over the last episode on each level. At the start of each training episode, with some predefined replay probability p. PLR uses bandit to sample the level from A to maximize the estimated learning potential; otherwise, with probability - p. PLR samples new level from the simulator. contrast to the generative but slow-adapting PAIRED, PLR does not create new levels, but instead, acts fast-adapting curation mechanism for selecting the next training level among previously encountered levels. Also unlike PAIRED, PLR does not provide robustness guarantee. By extending the theoretical foundation of PAIRED to PLR, we will show how PLR can be modified
3

---

to provide a robustness guarantee at NE, as well as how PAIRED can exploit PLR's complementary curation to quickly switch among generated levels to maximize the student's 's regret.
The Robustness of Dual Curriculum Design
Train on generated level
Curator
Generate new level
Select replay level
Ganer abor ANA
R
Update with level
Update regret
Student
Overview Dual Curriculum Design (DCD). The student learns in the presence of two co-adapting teachers that aim to maximize the student's 's regret: The generator teacher designs now levels to challenge the agent, and the curator teacher prioritizes set of levels already created, selectively sampling them for replay.
Figure 2:
The previous approaches of PAIRED and PLR reveal natural duality: Approaches that gradually learn to generate levels like PAIRED, and methods which cannot generate levels, but instead, quickly curate existing ones, like PLR. This duality suggests combining slow level generators with fast level curators. We call this novel class of UED algorithms Dual Curriculum Design (DCD). For instance, PLR can be seen curator with prioritized sampling mechanism with random generator, while PAIRED, as a gggret-maximizing generator without a curator. DCD can further consider Domain Randomization (DR) degenerate case of random level generator without a curator.
To theoretically analyze this space of methods, we model DCD as three player game among a student agent and two teachers called the dual curriculum game. However, to formalize this game, we must first formalize the single-teacher setting: Suppose the UPOMDP is clear from context. Then, given utility function for single teacher, U, UT, 0). we can naturally define the base game between the student s and teacher as = (S = Sg x St, U = U, x U2). where S₂ = 11 is the strategy set of the student, S, = θ is the strategy set of the teacher, and (T, 8) (TT) is the utility function of the student. In Sections 4 and 5, we will study settings corresponding to different choices of utility functions for the teacher agents, namely the maximum-regre objective UzR(z, 0) and the uniform objective U. (T,, 0). These two objectives are defined as follows (for any constant C):
U,((T, (IT, 0) argmax (V (x*) - v (T))
(V'
x'ell U. (T, 0) =
(2)
In the dual curriculum game G. the first teacher plays the game with probability and the second, with probability (1 p)-or or more formally, G = (3 S. S₁ Se, U = U, x U, x U.). where the utility functions for the student and two teachers respectively, U., U U? are defined follows:
(' 02) = pU, (m, (T,
(3)
F2( 000) _= = =1 (1-)))) 82) U. (T 0', 02) = pU.(Z, + (1- (1, 02)
(4)
(5)
Our main theorem that NE in the dual curriculum game are approximate NE of both the base game for either of the original teachers and the base game with a teacher maximizing the jeint-reward of pU! + - pp, where the quality of the approximations depends on the mixing probability p.
Theorem 1. Let B be the maximum difference between U? and U?. and let (M, 0 62) be a NE for G. Then (IT, p00 (1 p)0²) is an approximate NE for the base game with either teacher or for teacher optimizing their joint objective. More precisely, it is a 2Bp(1 apprrxxiiee NE when U, = pU, + Up) a 2B(1 p) approximaaee NE when U. = U., and a Bp-apprrximmat NE when U, U??
The intuition behind this theorem that, since the two teachers do not affect each other's behavior, their best response to fixed Te is to choose a strategy 0 that maximizes U?! and U? respectively.

---

Moreover, the two teachers' strategies can be viewed as a single combined strategy for the base game with the joint-objective, or with each teacher's own objective. In fact, the teachers provide an approximate best-response to each case of the base game simply by playing their individual best responses. Thus, when we reach NE of the dual curriculum game, the teachers arrive at approximate best responses for both the hase game with the joint objective and with their own objectives, meaning they are also in an approximate NE of the base game with either teacher. The full details of this proof are outlined in Appendix A.
4 Robustifying PLR
In this section, we provide theoretical justification for the empirically observed effectiveness of PLR, and in the process, motivate counterintuitive adjustment the algorithm.
Algorithm 1: Robust PLR (PLR+)
Randomly initialize policy (()) and an empty level buffer, A of size K.
while not converged do
Sample replay-decision Bernoulli, (b(d)
d 0 then
Sample level 0 from level generator Collect It's trajectory on 6, with stop- coo-ggraieent d_
L.e. Suppress policy update
else
Use PLR to sample replay level from the level store, A ~ A
Collect policy trajectory T on 0 and update with rewards R(T)
end
Compute PL. score, S = score(T, m)
Update A with 0 using score $
end
4.1 Achieving Robustness Guarantees with PLR
PLR provides strong empirical gains in generalization, but lacks any theoretical guarantees of robustness. One step towards achieving such guarantee is to replace its L1 value-loss prioritizaton with a regret prioritization, using the methods we discuss in Section 4.2: While L1 value loss may be good for quickly training the value function, it can bias the long-term training behavior toward high-variance policies. However, even with this change, PLR holds weaker theoretical guarantees because the random generating teacher can bias the student away from minimax regret policies and instead, toward policies that sacrifice robustness in order to excel in unstructured levels. We formalize this intuitive argument in the following corollary of Theorem 1.
Corollary 1. Let G be the dual curriculum game in which the first teacher maximizes regret, so U? = U.R. and the second teacher plays randomly, so U² bounded in of G. Let R mill EII En (annmmaxe,,neee.. (ttp:eeeeennnRRERER (FAG TB)}} be the optimal worst-case regret. Then w is 2(B+ anxx, [REGRET (T x)} 2 R - - (1 Moreover, there exists environments for all values of p within constant factor of achieving this bound.
U. Let (² be for all 0, Further, suppose that (T,, 0² 02) is Nash equilibrium
(1
close to having optimal worst-case regret, or formally,
The proof of Corollary follows from a direct application of Theorem to show that a NE of an approximate NE for the base game of the first teacher, and through constructing simple example where the student's best response in G fails to attain the minimax regret in G. These arguments are described in full in Appendix A. This corollary provides some justification for why PLR improves robustness of the equilibrium policy, as it biases the resulting policy toward minimax regret policy, However, it also points a way towards further improving PLR: If the probability p of using a teacher- generated level directly set to 0, then in equilibrium, the resulting policy converges to minimax regret policy. Consequently, we arrive at the counterintuitive idea of avoiding gradient updates from trajectories collected from randomly sampled levels, to ensure that at NE, we find minimax regret policy. From robustness standpoint, it is therefore optimal to train on less data. The modified PLR algorithm PLR with this counterintuitive adjustment is summarized in Algorithm 1, in which this small change relative to the original algorithm is highlighted in blue.
5

---

4.2 Estimating Regret
In general, levels may differ in maximum achievable returns, making it impossible know the true regret of a level without access to an oracle. As the LI value loss typically employed by PLR does not generally correspond to regret, we turn to alternative scoring functions that better approximate regret. Two approaches, both effective in practice, are discussed below.
Positive Value Loss Averaging over all transitions with positive value loss amounts estimating regret as the difference between maximum achieved return and predicted return on an episodic basis. However, this estimate is highly biased, as the value largets are tied to the agent's current, potentially suboptimal policy. As it only considers positive value losses, this scoring function leads to optimistic sampling of levels with respect to the current policy. When using GAE [33] estimate bootstrapped value targets, this loss takes the following form, where À and yy are the GAE and MDP discount factors respectively, and d,, the TD-error at timestep
T E(TA)A 06n.0)
T
t=0
Maximum Monte Carlo (MaxMC) We can mitigate some of the bias of the positive value loss by replacing the value target with the highest return achieved on the given level so far during training. By using this maximal return, the regret estimates no longer depend on the agent's current policy. This estimator takes the simple form of (1/T) Et=o Rmax - Vs()). In dense-reward experiments, we compute this score as the difference between the maximum achieved return and V(so).
ReplaayEnhanced PAIRED (REPAIRED)
We can replace the random generator teacher used by PLR with the PAIRED teacher. This extension entails a second student agent, the antagonist, also equipped with its own PLR level buffer. In each episode, with probability p. the students evaluate their performances (but do not train) on newly generated level and, with probability 1 train on a level sampled from each student's 's own eggret-rriritiziing PLR buffer. Training only on the highest regret levels should mitigate inefficiencies in the PAIRED teacher's optimization procedure. We refer to this extension as PAIRED (REPAIRED). overview of REPAIRED is provided by black arrows in Figure 2, with the students being the protagonist and antagonist, while the full pseudocode is outlined in Appendix B.
Since PLR and PAIRED both promote regret in equilibrium, would be reasonable to believe that the combination of the two does the same. A straightforward corollary of Theorem which describe in Appendix I, shows that, in a theoretically ideal setting, combining these two algorithms is done in REPAIRED indeed finds minimax regret strategies equilibrium.
Corollary 2. Let G be the dual curriculum game in which both teachers maximize regret, so U. U? U.R. Further, suppose that (m, 0² B2) is Nash equilibrium of G. Then, argminzzent (max0, (REGGE (REGRET (F TB))].
This result gives some amount of assurance that, if our method arrives at NE, then the protagonist has converged to minimax regret strategy, which has the benefits outlined in [10]: Since a minimax regret policy solves all solvable environments, whenever this is possible and sufficiently well-defined, we should expect policies resulting from the equilibrium behavior of REPAIRED to be robust and versatile across all environments in the domain.
6 Experiments
Our experiments firstly aim to (I) assess the empirical performance of the theoretically motivated P and secondly, seek better understand the effect of replay on unsupervised environment design, specifically (2) its impact on the zero-shot generalization performance of the induced student policies, and (3) the complexity
the levels designed by the teacher. To do so, we compare PLR and REPAIRED against their replay-free counterparts, DR and PAIRED, in the two highly distinct settings of discrete control with sparse rewards and continuous control with dense rewards. We provide environment descriptions alongside model and hyperparameter choices in Appendix D.

---

6.1 Partially-Observable Navigation
Each navigation level is partially-observable maze requiring student agents take discrete actions to reach a goal and receive a sparse reward. Our agents use PPO [34] with an LSTM-bassd recurrent policy to handle partial observability. Before each episode, the teacher designs the level in this order: beginning with an empty maze, it places one obstructing block per time step up to a predefined block budget, and finally places the agent followed by the goal.
Roxteen
Labyrinth
Labyrinth2
Maze2
PerfectMaze"
LargeCorridor
Solved rate
0.5
9.0
DR
Minimax
PAIRED
REPAIRED
PLR
PLR-
Figure 3: Zero-shot transfer performance in challenging environments after 250M training steps. The plots show median and interquartile range solved rates over runs. An asterisk (*) next to maze name indicates the maze is procedurally-genett generated, and thus each attempt corresponds to a random configuration of the maze.
Zero-Shot Generalization We train policies with each method for 250M steps and evaluate zero- shot generalization on several challenging OOD environments, in addition to levels from the full distribution of two procedurally-generace compare against DR and minimax baselines. Our results in Figure 3 and 4 show that PLR and REPAIRED both achieve greater sample-efficieng and zero-shot generalization than their replay- counterparts. The improved test performance achieved by PLR over both DR and PLR when trained for an equivalent number of gradient updates, aggregated over test mazes, is statistically significant (p < 0.05), is the improved test performance of REPAIRED over PAIRED. Well before 250 million steps, both PIR and PLR significantly outperform PAIRED after 3 billion training steps, as reported in [10]. Further, both PLR variants lead to policies exhibiting greater zero-shot transfer than the PAIRED variants. Notably, the PLR- agent learns to solve mazes via an approximate right-han rule. Table 2 in Appendix C.1 reports performance across all test mazes. The success of designing segret-maximizing levels via random search (curation) over learning a generator with RL suggests that for some UPOMDPs, the regret landscape, as function of the free parameters 6, has a low effective dimensionality [3]. Foregoing gradient-based learning in favor of random search may then lead to faster adaptation to the changing regret landscape, as the policy evolves throughout training.
environments, PerfectMaze and LargeCorridor. We also
Emergent Complexity As the student agents improve, the teachers must generate more challenging levels to maintain regret. We measure the resultant emergent complexity by tracking the number of blocks in each level and the shortest path length the goal (where unsolvable levels are assigned length of O). These results, summarized in Figure 4. show that PAIRED slowly adapts the complexity over training while REPAIRED initially quickly grows complexity, before being overtaken by PAIRED. This more rapid onset of complexity may be due to REPAIRED's fast replay mechanism, and the long-term slowdown relative to PAIRED may be explained by its less frequent gradient updates. Our results over extended training period in Appendix C confirm that both PAIRED and REPAIRED slowly increase complexity over time, eventually matching that attained in just a fraction of the number of gradient steps by PLR and - This result shows that random search is surprisingly efficient at continually discovering levels of increasing complexity, given an appropriate curation mechanism such as PL.R. Figure shows that, similar to methods with regret-maximizing teacher, PLR finds levels exhibiting complex structure.
PAIRED
REPAIRED
PLR+
Examples of emergent structures generated by each method.
Figure 5:
7

---

DR
Minimax
PAIRED
REPAIRED
PLR
PLR
RooeenRRomms
Labyrinth
Maze
SodleenRooms
Labyrinth
0.0
PAIRED, 32 steps
Solved rate
Modian
0.5
0.2
Solved
Number blocks
Shortest path length
Block count
9
10
250M
250M
Steps
PPO updates
Zero-shot transfer performance during training for PAIRED and REPAIRED variants. The plots show mean and standard enror across 10 runs. The dotted lines mark the mean performance of PAIRED after 3B training steps, reported in [10], while dashed lines indicate median returns.
Figure 4:
6.2 Pixel-Based Car Racing with Continuous Control
To the versatility and scalability of our methods, we turn to an extended version of the CarRacing environment from OpenAl Gym [5]. This environment entails continuous control with dense rewards, a 3-dimensional action space, and partial, pixel observations, with the goal of driving a full lap around a track. To enable UED of any closed-loop track, we reparameterize CarRacing generate tracks as Bézier curves [22] with arbitrary control points. The teacher generates levels by choosing a sequence of up to 12 control points, which uniquely defines Bézier track within specific, predefined curvature constraints. After 5M steps of training, we test the zero-shot transfer performance of policies trained by each method on 20 levels replicating official human-designed Formula One (FI) tracks (see Figure in the Appendix for visualization of the tracks). Note that these tracks are significantly OOD, as they cannot be defined with just 12 control points. In Figure 6 show the progression of zero-shot transfer performance for the original CarRacing environment, as well three F1 tracks of varying difficulty, while also including the final performance on the full F1 benchmark. For the final performance, we also evaluated the state-of-the- CarRacing agent from [38] our F1 benchmark.
PAIRED
REPAIRED
PLR
PLR
Tang 2020
CarRacing-v
F1-Italy
F1-Singapore
F1-Germany
Full
900
900-
900
900
Test Testrelum retum
Test return
400
450
450
200
0
0
5M
SM
Steps
Figure 6: Zero-shot transfer performance. Plots show mean and standard error over 10 runs.
Unlike in the sparse, discrete navigation setting, we find DR leads to moderately successful policies for zero-shot transfer in CarRacing. Dense rewards simplify the learning problem and random Bezier tracks occasionally contain the challenges seen in F1 tracks, such as hairpin turns and observations showing parallel tracks due to high local curvature. Still, we see that policies trained by selectively sampling tracks to maximize regret significantly outperform those trained by uniformly sampling

---

from randomly generated tracks, in terms of zero-shot transfer to the OOD F1 tracks. Remarkably. with replay rate of 0.5, PLR sees statistically significant (p < 0.001) gains over PLR in zero-shot performance over the full Fl benchmark, despite directly training on only half the rollout data using half as many gradient updates, Once again, we see that random search with curation via PLR produces a rich selection of levels and an effective curriculum.
We also observe that PAIRED struggles to train a robust protagonist in CarRacing. Specifically, PAIRED overexploits the relative strengths of the antagonist over the protagonist, finding eurrieula that steer the protagonist towards policies that ultimately perform poorly even on simple tracks, leading to a gradual reduction in level complexity. We present training curves revealing this dynamic in Appendix C. As shown in Figure 6, REPAIRED mitigates this degeneracy substantially, though not completely, inducing a policy that significantly outperforms PAIRED (p < 0.001) mean performance on the full F1 benchmark, but underperforms DR. Notably, PLR- exceeds the performance of the state-of-the of-the-art AttentionAgent [38], despite not using self-attention policy and training on less than 0.25% of the number of environment steps in comparison. These gains come purely from the induced curriculum. Figure 17 in Appendix C further reveals that PLR produces CarRacing policies that tend to achieve higher minimum returns on average compared to the baseline methods, providing further evidence of the benefits of the minimax regret property coupled with fast ceplay-based mechanism for efficiently finding high-regret levels.
7 Related Work
In inducing parallel curricula, DCD follows rich lineage of curriculum learning methods [2, 32, 28, 23). Many previous curriculum learning algorithms resemble the curator in DCD, sharing similar underlying selective-sampling mechanisms as PLR- Most similar is TSCL [19], which prioritizes levels based on return rather than value loss, and has been shown to overfit training levels in some settings [17]. In our setting, replayed levels can be viewed as past strategies from a level-generating teacher. This links our replay-base based methods to fictitious self-play [FSP, 13], and more closely, Prioritized FSP [40], which selectively samples opponents based on historic win ratios.
Recent approaches that make use of generating adversary include Asymmetric Self-Play [37, 26), wherein one agent proposes tasks for another in the form of environment trajectories, and AMIGo [6], wherein the teacher is rewarded for proposing reachable goals. While our methods do not presuppose a goal-based setting, others have made progress here using generative modeling [12, 29I, latent skill learning [14], and exploiting model disagreement [45]. These methods are less generally applicable than PLR and unlike our DCD methods, they do not provide well-principeed robustness guarantees.
Other recent algorithms can be understood as forms of UED and like DCD, framed in the lens of decision theory. POET [41, 42], a coevolutionary approach [27], uses population of minimax (rather than minimax regret) adversaries construct terrain for a BipedalWalker agent. In contrast to our methods. POET requires training a large population of both agents and environments and consequently, a sizable compute overhead. APT-Gen [11] also procedurally generates tasks, but requires access to target tasks, whereas our methods seek to improve zero-shot transfer.
The DCD framework also encompasses adaptive domain randomization methods [DR, 20, 15], which have seen success in assisting sim2real transfer for robotics [39, 16, 1, 25). DR itself is subsumed by procedural content generation [30], for which UED and DCD may be seen as providing formal, decision-theoretic framework, enabling development of provably optimal algorithms.
8 Discussion
We established a novel connection between PLR and minimax regret UED approaches like PAIRED, by developing the theory of Dual Curriculum Design (DCD). In this setting, a student policy is challenged by a team of two co-adapting, regret- megrei-ma teachers: one, a generator that creates new levels, and the other, a curator that selectively samples previously generated levels for replay. This view unifies PLR and PAIRED, which are both instances DCD. Our theoretical results on DCD then enabled us to prove that PLR attains a minimax regret policy at NE, thereby providing the first theoretical characterization of the robustness of PL... Notably our theory leads to the counterintuitive result that PLR can be made provably robust by training on less data, specifically, by only using

---

the trajectories on levels sampled for replay. In addition, we developed Replay-Enhancee PAIRED (REPAIRED), which extends the selective replay-based updates of PLR to PAIRED, and proved shares the same robustness guarantee at NE. Empirically, in two highly distinct environments, we found that PLR- significantly improves zero-shot generalization over PLR, and REPAIRED, over PAIRED. As our methods solely modify the order of levels visited during training, they can, in principle, be combined with many other RL methods to yield potentially orthogonal improvements in sample-efficiency and generalization.
While these DCD-based improvements to PLR and PAIRED empirically lead to more robust policies, it is important to emphasize that our theoretical results only prove a minimax regret guarantee at NE for these methods; however, they provide no explicit guarantee of convergence to such NE, Further, it is worth highlighting that replay-based methods like PLR* are completely dependent on the quality of levels proposed by the generator. Our results show that simply curating high regret levels discovered via random search is enough to outperform the RL-based PAIRED teacher in the domains studied. We expect that advancing methods for defining or adapting the generator's 's proposal distribution holds great potential to improve the efficacy of our methods, especially in more complex, nigher-dimensione domains, where random search may prove ineffective for finding useful training levels. Importantly, methods assume appropriate choice of what constitutes the UPOMDP's free parameters. Our methods cannot be expected to produce robust policies for zero-shot transfer the set of environments defined by the free parameters does not sufficiently align with the transfer domain of interest. Designing the environment parameterization for successful zero-shot transfer to a specific target domain can be highly non-trivial, posing an important problem for future research.
Looking beyond environment design, we notice that long-running UED processes in expansive UPDOMPs closely resemble continual learning in open-ended domains. The congruency of these settings suggests our contributions around DCD may extend to more general continual learning problems in which agents must learn to master diverse sequence of tasks with predefined (or teacher.
inferred) episode boundaries- tasks are assumed to be designed by a Thus, DCD-based methods like PLR may yield more general policies for continual learning. We anticipate many exciting crossovers between these areas of research in the years to come.
Given the rapid progress in applying RL to ever more complex domains, we can confidently expect a continued rise in real-world deployments of RL systems in the coming years. Unlike in simulation, in the real world, the environment tends exhibit much more variability, which may not be explicitly coded into the associated simulator used for training. Deployed RL agents are thus liable to make many mistakes due to unexpected environment variations. Our methods for improving UED lead to more robust RL agents across a potentially wide range of changes to the environment. Thus, our work may prove to be a useful tool in attaining safer, more reliable RL agents, helping to enable the application of RL to more real-world problems.
By increasing the applicability of RL to real-world settings, our work may exacerbate the more general risks of deploying machine learning: increased unemployment; overreliance on biased models that potentially reinforce common misconceptions and societal inequalities; and the advancement of automated weapons. Particular to our methods, as discussed in Section 8, aligning the choice of free parameters for the UPOMDP the target domain of interest is important for successful transfer. While this choice of free parameters then acts as potential point of failure, the UPOMDP abstraction underlying UED reveals this problem generally impacts all RL methods aiming to train robust policies; a UPOMDP simply makes explicit the otherwise implicit space of environment configurations defined by standard POMDP. By forcing us to consider where our training environment departs from reality, UED methods encourage designing RL systems in a way that is more aware of the underlying assumptions about the environment, thereby leading to more principled, robust systems.
Acknowledgments and Disclosure of Funding
We would like to thank Natasha Jaques, Patrick Labatut, and Heinrich Küttler for fruitful discussions that helped inform this work. Further, we are grateful to our anonymous reviewers for their valuable feedback. MJ is supported by the FAIR PhD program. This work was funded by Facebook.
10

---

References
[1] O. M. Andrychowicz, B. Baker, M. Chociej, R. Józefowicz, B. McGrew, J. Pachocki, A. Petron, M. Plappert, G. Powell, A. Ray, J. Schneider, S. Sidor, J. Tobin, P. Welinder, L. Weng, and W. Zaremba. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 39(1):3-20) 2020.
[2] Y. Bengio, J. Louradour, R. Collobert, and J. Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, page 41-48, New York, NY, USA, 2009. Association for Computing Machinery.
[3] J. Bergstra and Y. Bengio. Random search for hyper-parameter optimization. Journal of Machine Learning Research, 13:281-305, 2012.
[4] C. Berner, G. Brockman, B. Chan, V. Cheung, Dębiak, C. Dennison, D. Farhi, Q. Fischer,
S. Hashme, C. Hesse, et al. Dota 2 with large scale deep reinforcement learning, arXiv preprint
wwXiv:1122.06680 2019.
[5] G. Brockman, V. Cheung, L. Pettersson, Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym. CoRR, abs/1606.0154pp 2016.
[6] A. Campero, R. Raileanu, H. Kuttler, J. B. Tenenbaum, T. Rocktäschel, and E. Grefenstette. Learning with AMIGo: Adversarially motivated intrinsic goals. In International Conference on Learning Representations, 2021.
[7] M. Chevalier-Boisver,, L. Willems, and S. Pal. Minimalistic gridworld environment for openai gym. https://githut. cow http//aximecb//eemoo geteeeeee//eeeeeeeeeeeegge gym-minigrid, 2018.
[8] K. Cobbe, C. Hesse, J. Hilton, and J. Schulman. Leveraging procedural generation to benchmark reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, pages 2048-2056 2020.
[9] K. Cobbe, O. Klimov, C. Hesse, T. Kim, and J. Schulman. Quantifying generalization in reinforcement learning. K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 20/9, 9-15 June 2019, Long Beach, California, USA, Proceedings of Machine Learning Research. PMLR, 2019.
[10] M. Dennis, N. Jaques, Vinitsky, A. Bayen, Russell, Critch, and Levine. Emergent complexity and zero-shot transfer via unsupervised environment design. In Advances in Neural Information Processing Systems, volume 33, 2020.
[11] K. Fang, Y. Zhu, S. Savarese, and F-FF, Li. Adaptive procedural task generation for hard- exploration problems. In International Conference on Learning Representations, 2021.
[12] C. Florensa, D. Held, X. Geng, and P. Abbeel. Automatic goal generation for reinforcement learning agents. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1515-1528. PMLR, 10 2018.
[13] J. Heinrich, M. Lanctot, and D. Silver. Fictitious self-play in extensive-form games. In Proceedings of the 32nd International Conference on Machine Learning, pages 805-813, 2015.
[14] A. Jabri, K. Hsu, A. Gupta, B. Eysenbach, S. Levine, and C. Finn. Unsupervised curricula for visual meta-reinforcement learning. In Advances in Neural Information Processing Systems, volume 32, 2019.
[15] N. Jakobi. Evolutionary robotics and the radical envelope-of-noie hypothesis. Adaptive Behavior, 6(2):325-366 -688 1997.
[16] S. James, A. J. Davison, and E. Johns. Transferring end-to-end visuomotor control from simulation to real world for multi-stage task. 1st Conference on Robot Learning, 2017.
[17] M. Jiang, E. Grefenstette, and T. Rocktäschel. Prioritized level replay. In Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 3940-4950 PMLR, 2021.
[18] X. Ma. Car racing with pytorch. https://githut: httpg/ggthubcooooooooo http://gggtttcccoo/////tttttrtrt
2019. [19] Matiisen, A. Oliver, T. Cohen, and Schulman. Teacher-student curriculum learning. IEFE Transactions on Neural Networks and Learning Systems, PP, 07 2017.

---

[20] B. Mehta, M. Diaz, F. Golemo, J. Pal, and L. Paull. Active domain randomization. In L. P. Kaelbling, D. Kragic, and K. Sugiura, editors, 3rd Annual Conference on Robot Learning. CoRL 2019, Osaka, Japan, October 30 - November 1, 2019, Proceedings, volume 100 of Proceedings of Machine Learning Research, pages 1162-1176. PMLR, 2019.
[21] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):22-533,, 2015.
[22] M. E. Mortenson. Mathematics for Computer Graphics Applications. Industrial Press Inc., 1999.
[23] S. Narvekar, B. Peng, M. Leonetti, J. Sinapov, M. E. Taylor, and P. Stone. Curriculum learning for reinforcement learning domains: A framework and survey. Journal of Machine Learning Research, 21:181:1-181:: 181:50, 2020.
[24] J. Nash et al. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48-45 49, 1950.
[25] OpenAI, I. Akkaya, M. Andrychowicz. M. Chociej, M. Litwin, B. McGrew, A. Petron, A. Paino, M. Plappert, G. Powell, R. Ribas, J. Schneider, N. Tezak, J. Tworek, P. Welinder, L. Weng, Q. Yuan, W. Zaremba, and L. Zhang. Solving rubik's cube with robot hand. CoRR,
abs/1910.07113, 2019.
[26] O. OpenAL, M. Plappert, R. Sampedro, T. Xu, I. Akkaya, V. Kosaraju, P. Welinder, R. D'Sa, A. Petron, H. P. de Oliveira Pinto, A. Paino, H. Noh, L. Weng, Q. Yuan, C. Chu, and W. Zaremba. Asymmetric self-play for automatic goal discovery in robotic manipulation, 2021.
[27] E. Popovici, A. Bucci, R. P. Wiegand, and E. D. De Jong. Coevolutionary Principles, pages 987-1033. Springer Berlin Heidelberg, 2012.
[28] R. Portelas, C. Colas, Weng. K. Hofmann, and P.-Y. Oudeyer. Automatic curriculum learning for deep rl: A short survey. In C. Bessiere, editor. Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 4819-4825. International Joint Conferences on Artificial Intelligence Organization, 7 2020. Survey track.
[29] S. Racaniere, A. Lampinen, A. Santoro, D. Reichert, V. Firoiu, and T. Lillicrap. Automated curriculum generation through setter-solver interactions. International Conference on Learning Representations, 2020.
[30] S. Risi and J. Togelius. Increasing generality in machine learning through procedural content generation. Nature Machine Intelligence, 2(8):428 436, 8 2020.
[31] L. J. Savage. The theory of statistical decision. Journal of the American Statistical association, 46(253):55-67, 1951
[32] Schmidhuber. Powerplay: Training an increasingly general problem solver by continually searching for the simplest still unsolvable problem. Frontiers in Psychology, 4:313, 06 2013.
[33] J. Schulman, P. Moritz, S. Levine, M. I. Jordan, and P. Abbeel. High-dimensional continuous control using generalized advantage estimation. In Y. Bengio and Y. LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juwn, Puerio Rico, May 2-4, 2016, Conference Truck Proceedings, 2016
[34] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. CoRR, abs/1707.06347, 2017.
[35] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittieeser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):844-489, 2016.
[36] D. Silver, T. Hubert, Schrittwieeer, I. Antonogiou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel. et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1 140-1 1144, 2018
[37] S. Sukhbaatar, Z. Lin, I. Kostrikov, G. Synnaeve, A. Szlam, and R. Fergus. Intrinsic motivation and automatic curricula via asymmetric self-play. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Truck Proceedings. OpenReview.net, 2018.
12

---

[38] Y. Tang, D. Nguyen, and D. Ha. Neuroevolution of self-interpretable agents. In Proceedings of the Genetic and Evolutionary Computation Conference, 2020.
[39] Tobin, R. Fong, A. Ray, Schneider, W. Zaremba, and Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 JEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pages 23-30, 2017.
[40] O. Vinyals. I. Babuschkin, W. M. Czameckk,, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev, et al. Grandmaster level in StarCraft using multi-agent reinforcement learning. Nature, 575(7782)3300333 355-3344, 2019.
[41] R. Wang. J. Lehman, J. Clune, and K. O. Stanley. Paired open-ended trailblazer (POET): endlessly generating increasingly complex and diverse learning environments and their solutions. CoRR, 0tss/1901.01750 2019.
[42] R. Wang. J. Lehman, A. Rawal, J. Zhi, Y. Li, J. Clune, and K. Stanley. Enhanced POET: Open-ended reinforcement learning through unbounded invention learning challenges and their solutions. In Proceedings of the 37th International Conference on Machine Learning, pages 1040-9999559 2020.
[43] B. L. Welch. The generalization of 'student's' problem when several different population variances are involved. Biometrika, (4(1-2):28-35, 1947.
[44] A. Zhang, N. Ballas, and Pineau. A dissection of overfitting and generalization in continuous reinforcement learning, arXiv preprint arXiv:1806. (0Xi::/806.07377, 2018.
[45] Y. Zhang, P. Abbeel, and L. Pinto. Automatic curriculum learning through value disagreement.
In Advances Neural Information Processing Systems, volume 33, pages 7648-7659 2020.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either the supplemental material or as URL)? [Yes] (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix D. and D.2.
(c) Did you report error bars (e.g.. with respect the random seed after running experiments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix D. and D.2.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] The MIT License.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "mZUIL5ZkO1", "reviewer": "Reviewer_HQZ9", "summary": "This paper proposes to theoretical analysis of the Prioritized Level Replay (PLR) from prior work and proposes an environment generation framework named Dual Curriculum Design (DCD). The proposed framework is composed of teacher agents that keep generating new environments and a student agent that learns to solve the generated environments. The teacher agents are co-adapted to generate new environments by maximizing the student's agent's regret. In a grid world domain and the CarRacing domain, the proposed method outperforms previous baselines such as PAIRD.", "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": "Strengths:\n\n-  Based on prior work, this paper proposes novel theoretical analysis as well as algorithmic solutions for generating environments as curricula. \n\n- The proposed technical solution and the theoretical analysis seem to be reasonable to me. \n\n-  The paper is clearly written and easy to follow. \n\n- This paper could provide interesting insights to future work on environment generation. However, the significance of the proposed method is not entirely convincing due to missing several important baselines. \n\nWeaknesses:\n\n- Several state-of-the-art curriculum learning methods should be compared as baselines, including  [Portelas et al. CoRL 2019], [Florensa et al. ICML 2018], and [Zhang et al. NeurIPS 2020]. It is also important to include the baseline that uniformly samples environments as curricula.\n\n- In Figure 4 and Figure 5, it seems that the learning curves often suffer from noticeable performance regressions during the later stage of training. Could the authors provide more detailed explanations about this phenomenon?\n\n- In some subfigures in Figure 4 (e.g. \"SixteenRooms\" and \"Maze\"), the learning curves are cut off before convergence is reached. \n\n- The GridWorld and the CarRacing domains are a little toyish. It would be better to include more challenging task domains for continuous space control as in [Portelas et al. CoRL 2019] and [Florensa et al. ICML 2018].", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It would be better if the authors could provide more discussions and explanations about why the proposed method cannot be evaluated in continuous domains in this paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "jXRr6zzgl-B", "reviewer": "Reviewer_amNM", "summary": "In this paper, the authors propose a common framework,  Dual Curriculum Design, that augments PAIRED with a PLR-based replay mechanism, named as REPAIRED. The theory also suggests convergence to Nash Equilibrium should be assisted by training on fewer data when using PLR—namely by only taking policy-gradient updates from data that originates from the PLR buffer, and only using samples from the environment distribution to populate the buffer. The authors further conducted experiments on a maze environment and on car-racing tracks. Results showed that the proposed approaches outperformed the PLR and other baselines in general.", "questions": "", "limitations": "", "rating": 7, "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:\nThe paper provides theoretical analysis on the robustness guarantees for PLR method and REPAIRED.\nThe performance of the new proposed algorithms in both experiments is better than the state-of-the-art benchmarks.\n\nConcerns:\nThe analysis is based on approximate Nash equilibria. The robustness is based on the accuracy of this approximation. However, the theoretical guarantee shows $\\pi$ is $4Bp$ close to having optimal worst-case regret. How significant is this distance in the landscape of the policy? It seems to me, both $B$ and $p$ could be big so I have concerns of the effectiveness of the analysis. It will be nice to analyze the sensitivity of this distance to the effectiveness for robustness analytically and experimentally.\n\nMinor things: Some notations are confusing:\n1. Line 107, in the left of the equation, the regret is on $\\pi_A$ and $\\pi_B$, on the right of the equation, the values become $\\pi_P$ and $\\pi_A$. Actually, throughout the whole paper, the mix of using $\\pi_P$ and $\\pi_B$ might confuse the readers. It will be great if the notation could be consistent.\n2. It will be nice if the authors could give further qualitative and numerical insights to the various performance with different maps. Particularly, why DR is the best among all the methods. Could this unveil some limitations of the proposed method/all PLA-based methods?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative social concerns.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "chCuJ9CCEj6", "reviewer": "Reviewer_Xs8e", "summary": "This paper considers two forms of curriculum design, unsupervised environment design and prioritized experience replay, and highlight their complementary nature.\nIt then considers the games induced by both these approaches and combines them into a dual curriculum game where the agent faces one teacher or the other with certain probability. Further, the paper analyzes the equilibria of this joint game and the equilibria of the two component games.\n\nThe paper then proposes two new algorithms, a robust version of PLR that does not learn on experienced trajectories but only on trajectories sampled by the PLR teacher, and a replay-enhanced PAIRED that improves the UED technique with PLR.\n\nThe various approaches are then compared on mazes and car racing domains.", "questions": "", "limitations": "", "rating": 7, "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": "## Technical Positives:\n* This paper show how UED/PAIRED and PLR can be seen as dual approaches and also how they can be combined.\n* These approaches fall into the larger space of automatic curriculum design for agents, and explore how different approaches can be combined effectively.\n* The game theoretic analysis of the equilibria of the combined game compared with the equilibria of the base games is shown to be an effective approach to analyze such a combination.\n* Notably, analyzing PLR through this lens allows principled modifications to the prioritization scheme and the agent update scheme.\n* REPAIRED seems to actually be the more explicit combination of the two approaches considered, and the successful combination of PLR and PAIRED is encouraging.\n* Despite the other errors alluded to in the supplementary material, overall the experiments on the maze and car racing domains show a fair bit of success for the above combinations. Both PAIRED and PLR seem to benefit from the modifications suggested.\n\n## Questions, Remarks and Drawbacks:\n* It seems the supplementary material and the main text are out of sync. On page 7 the main text repeatedly refers to a Figure 7 and the related text does not seem to match up with the discussion. Similarly in Section 6.2 Figure 11 is referred to as a visualization of the test tracks, which should probably refer to Figure 12.\n* The assertion that PLR and UED are dual problems seemed unclear and imprecise.\n* This \"duality\" also seems to not have much bearing on the game that is formulated for further analysis.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Societal impact is not discussed. The checklist asserts that this discussion is not applicable to their research. However some discussion of curriculum design and its impact on learning agents might have been useful.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "YMm5DdxBzfL", "reviewer": "Reviewer_58ME", "summary": "This paper studies the problem of automatically designing a distribution of environments that adjusts to the learning agent, called unsupervised environment design. Specifically, they propose Dual Curriculum Design in which two co-evolving teachers, i.e. one is a generator and another one is a replay teacher, introduce new levels/environments to the learning agent (a.k.a student) to learn a policy that can be effectively generalized to new and unseen environments. Besides, this paper proposes a new theory about PLR and REPAIRED robustness guarantees. The paper evaluates zero-shot generalization, emergent complexity, and scalability of their proposed method in multiple environments and scenarios.", "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": "While this paper studies an important and interesting problem of automatically designing the distribution of environments for a learning agent, unfortunately, the proposed method(s) is confusing and the main contribution of the paper is not clear and I don't fully understand what are the takeaways from this paper. Namely:\n\n       1. The main idea of the paper is built on top of PAIRED where a replay teacher is added to it and called REPAIRED. Although REPAIRED results are not good and not consistent across all experiments, this could have been the main story of the paper. \n\n       2. PLR and PLR+ ( for simplicity, I use PLR+ instead of PLR^\\perp): The discussions, theory, changes to PLR, and finally introduction of PLR+ are quite out of place in this paper. If the PLR+ is the contribution of this paper, then the paper should be about this not REPAIRED. It seems the authors decided to include both since neither one shows good results in all experiments and each doesn't have a significant contribution alone.\n\nWriting, results, and presentation: It is quite hard to follow the paper and get a clear picture of the experiments:\n\n       3. What does robustness mean here? Are you referring to generalization? or something else?  \n\n       4. Why are some methods used in some experiments but not in others? For instance, PLR+ is not in Figure 3, or part of Figure 4? \n\n       5. While I applauded authors to call out their bug in Figure 6, I am not sure what can I conclude about this paper since sometimes REPAIRED shows better results and some other time PLR+., take Figure 6 as an example, REPAIRED is better in F1-Italy and PLR+ is good in F1-Singapore and F1-Germany (both methods shows similar performance for CarRacing-v0 though) \n\n       6. What is B in line 164? \n\n       7.  What is the relationship between \\pi* and \\pi in Eq1? What is \\pi*?\n\n       8. What does context mean in 145? \"However, to formalize this game, we must first formalize the single-teacher context. Suppose the UPOMDP is clear from context.\"\n\n       9. What is \\theta_A in line 106? Is it a learnable parameter? Is it \\pi_A parameter? or something else?\n\n       10. Why maximum-regret objective (U^R) and uniform objective (U^U) are defined in line 152?   They are not referred to or used in section 3 and only referred later in section 4.1\n\n       11. Where is Figure 7 in the main text? (lines 264 and 283) Figure 7 in the appendix talks about something else and doesn't tell anything about replay rate of 0.5 for example.\n\n       12. What are the free parameters of an underspecified environment? what underspecified means (line 4)? \n\n       13. When this method generates a level, what are the mechanisms in place to make sure that there exists a solution and that level can be solved? \n\n\nIn summary, the significance and technical contributions of this work are not clear, the paper needs significant revision, and it is not ready for this conference. I'd highly recommend focusing on one concrete story in the paper rather than try to run two different narratives.   \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper discusses an approach for unsupervised environment design based on existing methods for toy/simulated environments ​which doesn't have a social impact. As such, I don't think this work has any negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4.5"}, "extra_text": {}}, {"review_id": "DACRReMRw9", "reviewer": "Reviewer_eYYy", "summary": "This paper considers a recent proposed problem, unsupervised environment design, that provides an environment selection scheme to enable the policy being trained under a curriculum learning setting. The proposed method combines two new approaches in this direction, PAIRED and PLR, where the former one learns to generate an environment while the latter one does not include a generator but instead gives a sampling scheme to choose previously encountered environments. The combined method is explained as a two-teacher dual curriculum game and explained theoretically. Experiments demonstrate the effectiveness of the combined method compared to PAIRED and PLR, respectively.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Some comments:\n\n1. The proposed method combines two new approaches, PAIRED and PLR, in the scope of environment designed and replay sampling, where the former one learns to generate an environment while the latter one does not include a generator but instead gives a sampling scheme to choose previously encountered environments. The combined method is explained as a two-teacher dual curriculum game and explained theoretically. I think such an explanation is reasonable and also the experiments are well-designed and sufficiently demonstrate the effectiveness of the combined method to me.\n\n2. The algorithm in Algorithm 1 implies that the combined method alternatively chooses PAIRED and PLR, relying on the sampled d. How is P_D(d) obtained? Moreover, PAIRED is chosen only when d=0. What is the distribution of P_D(d)?\n\n3. In section 6.1, the teacher works by placing one obstructing block per time step and finally places the agent and the goal. This is similar to the implementation of PAIRED, but in which the agent and the goal are placed first. Are there any differences of the designed orders for the teacher? Moreover, it is not very clear to me that as the placement is sequentially decided by the teacher, is this sequential decision progress treated as an MDP process and solved by RL? If so, it is a bit confused for me that in this sequential decision progress, there is no interaction between the teacher and the agents, and therefore the entire designment of the maze can be completed offline, such that the sequential decision problem can be transferred to an one-step decision (generating the entire maze). Of course, generating the entire maze in one step is impractical to be encoded in an action space in RL, and then the problem is cast to train a maze (environment) generator. I am not sure if my understanding is correct, so would the authors provide more explanations on this?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a unified approach for environmental design in RL. 

The reviewers positively evaluated the paper and recommended for acceptance. 

AC. 
Decision: Accept (Poster)