Improving Environment Novelty Quantification for Effective Unsupervised Environment Design
Authors: Jayden Teoh
Wenjun Li
Pradeep Varakantham
Venue: NeurIPS 2024 oral (2024)
Keywords: Unsupervised Environment Design
Novelty-driven Autocurricula
Primary area: reinforcement_learning
TL;DR: We proposed the CENIE framework, which offers a scalable, domain-agnostic, and curriculum-aware approach to quantifying environment novelty using the agent's state-action space coverage.

Abstract: Unsupervised Environment Design (UED) formalizes the problem of autocurricula through interactive training between a teacher agent and a student agent. The teacher generates new training environments with high learning potential, curating an adaptive curriculum that strengthens the student's ability to handle unseen scenarios. Existing UED methods mainly rely on *regret*, a metric that measures the difference between the agent's optimal and actual performance, to guide curriculum design. Regret-driven methods generate curricula that progressively increase environment complexity for the student but overlook environment *novelty* — a critical element for enhancing an agent's generalizability. Measuring environment novelty is especially challenging due to the underspecified nature of environment parameters in UED, and existing approaches face significant limitations. To address this, this paper introduces the *Coverage-based Evaluation of Novelty In Environment* (CENIE) framework. CENIE proposes a scalable, domain-agnostic, and curriculum-aware approach to quantifying environment novelty by leveraging the student's state-action space coverage from previous curriculum experiences. We then propose an implementation of CENIE that models this coverage and measures environment novelty using Gaussian Mixture Models. By integrating both regret and novelty as complementary objectives for curriculum design, CENIE facilitates effective exploration across the state-action space while progressively increasing curriculum complexity. Empirical evaluations demonstrate that augmenting existing regret-based UED algorithms with CENIE achieves state-of-the-art performance across multiple benchmarks, underscoring the effectiveness of novelty-driven autocurricula for robust generalization.

Improving Environment Novelty Quantification for Effective Unsupervised Environment Design
Jayden Teoh', Wenjun Li"t, Pradeep Varakantham
Singapore Management University (jxtech.2023, wjli.2020, pradeepv) edu.
Abstract
Unsupervised Environment Design (UED) formalizes the problem of autocur- ricula through interactive training between a teacher agent and a student agent. The teacher generates new training environments with high learning potential, curating an adaptive curriculum that strengthens the student's ability to handle unseen scenarios. Existing UED methods mainly rely regret, metric that measures the difference between the agent's optimal and actual performance, to guide curriculum design. Regret-driven methods generate curricula that progres- sively increase environment complexity for the student but overlook environment novelly-a critical element for enhancing agent's generalizability. Measuring environment novelty especially challenging due to the underspecified nature environment parameters in UED, and existing approaches face significant limi- tations. To address this, this paper introduces the Coverage-bass -bare Evaluation of Novelty In Environment (CENIE) framework. CENIE proposes scalable, domain- agnostic, and auriculuu-awaan approach to quantifying environment novelty by leveraging the student's state-action space coverage from previous curriculum experiences. We then propose an implementation of CENIE that models this cov- erage and measures environment novelty using Gaussian Mixture Models. By integrating both regret and novelty as complementary objectives for curriculum design, CENIE facilitates effective exploration across state-action space while progressively increasing curriculum complexity. Empirical evaluations demonstrate that augmenting existing regret-basee UED algorithms with CENIE achieves state- of-the-art performance across multiple benchmarks, underscoring the effectiveness novelty-driven autocurricula for robust generalization.
Introduction
Although recent advancements in Deep Reinforcement Learning (DRL) have led many successes,
e.g., super-human performance in games (26] 9 and reliable control in robotics 2 3. training generally-capable agents remains significant challenge. DRL agents often fail generalize well to environments only slightly different from those encountered during training [21 63). To address this problem. there has been a surge of interest in Unsupervised Environment Design (UED; [66] 23
37 33 7),, which formulates the autocurricula (32 generation problem as a two-player zero-sum game between teacher and student agent. UED, the teacher constantly adapts training environments (e.g., mazes with varying obstacles and car-racing games with different track designs) the curriculum improve the student's ability to generalize across all possible levels.
57 28
27
To design effective autocurricula, researchers have proposed various metrics to capture learning potential, enabling teacher agents to create training levels that adapt to the student's capabilities.
Equal contribution. Conresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The most popular metric, regret, measures the student's maximum improvement possible in level. While regret-based UED algorithms [23 27 28 are effective producing levels the frontier of the student's capability, they do not guarantee diversity in the student's 's experiences. limiting the training of generally-capable agents especially in large environment design spaces. Another line of work in UED recognizes this limitation, leading to methods exploring the prioritization of novel levels during curriculum generation [56] [57 33]. This strategic shift empowers the teacher to introduce novel levels into the curriculum such that the student agent can actively explore the environment space and enhance its generalization capabilities.
To more effectively evaluate environment novelty, we introduce the Coverage-based Evaluation of Novelty In Environment (CENIE) framework. CENIE operates on the intuition that a novel environment should induce unfamiliar experiences, pushing the student agent into unexplored regions of the state space and introducing variability in its actions. Therefore, signals about an environment's novelty can be derived by modeling and comparing its state-action space coverage with those of environments already encountered in the curriculum. We refer to this method of estimating novelty based on the agent's s past experiences the experiences induced by other environments within the curriculum, CENIE prevents redundant environments-those that elicit similar experiences as existing Currcullum-ware approaches ensure that levels in the student's ' curriculum collectively drive the agent toward novel experiences in sample-efficient manner.
curricklun-aware. By evaluating novelty in relation to
from being classified as novel.
Our contributions are threefold. First, we introduce CENIE, a scalable. curriculum-avee framework for quantifying environment novelty via the agent's 's state-action space coverage. CENIE addresses shortcomings in existing methods for environment novelty quantifi- cation, as discussed further in Sections and [ Second, we present implementations for CENIE using Gaussian Mixture Models (GMM) and integrated its novelty objective with PLR (28) and ACCEL the leading UED algorithms in zero-shot transfer performance. Finally, we conduct a comprehensive evaluation of the CENIE-augmented algorithms across three distinct benchmark domains. By incorporating CENIE into these leading UED algorithms, empirically validate that CENIE's novelty- -based objective not only exposes the student agent to a broader range of scenarios in the state-action space, but also contributes to achieving state-of- of-the-art zero-shot generalization performance. This paper underscores the importance of novelty and the effectiveness of the CENIE framework in enhancing UED.
and
2 Background
We briefly review the background of Unsupervised Environment Design (UED) in this section. UED problems are modeled as Underspecified Partilll Observable Markov Decision Process (UPOMDP) defined by the tuple:
(5.4,0,,,7,R,11,
where S, A and O are the sets of states, actions, and observations, respectively. Q represents set of free parameters where each 9 E θ defines a specific instantiation of an environment (also known
level). We use the terms "environments" and "levels" interchangeably throughout this paper. The level-conditional observation and transition functions are defined as I S x θ - O and T : S x A x θ ASS), respectively. The student agent, with policy π, receives reward based on the reward function R S x A + R with a discount factor E [0, 1]. The student seeks to maximize its expected value for each 0 denoted by (² E, E R(s,, a.)7''. The teacher's goal is to select levels forming the curriculum by maximizing a utility function U(T, 9), which depends on æ.
Different UED approaches vary primarily in the teacher's utility function. Domain Randomization (DR; (53) uniformly randomizes environment parameters, with constant utility (T(, 0) C. making it agnostic to the student's 's policy. Minimax training [39 adversarially generates challenging levels, with utility U-M(n (T, A) = -V*(()) to minimize the student's return. However, this approach incentivizes the teacher to make the levels completely unsolvable, limiting room for learning. Recent UED methods address this by using a teacher that maximizes regret, defined as the difference between the return of the optimal policy and the current policy. Regret-based utility is defined as ( 0) = REGRET (T, m²) V (*²)) -e"">>/((m (T)) where xt is the optimal policy on O. Regret-based objectives have been shown to promote the simplest levels that the student cannot solve optimally, and benefit from the thcoretical guarantee of minimax regret robust policy upon convergence in the

---

two-player sero-sum game. However, since π² is generally unknown, regret must be approximated. Dennis et al. [23]. the pioneer UED work, introduced principled level generation based on the regret objective and proposed the PAIRED algorithm, where regret is estimated by the difference between the returns attained by an antagonist agent and the protagonist (student) agent. Later on, Jiang et al. (27] introduced PLR- which combines DR with regret using Positive Value Loss (PVL.), an approximation of regret based on Generalized Advantage Estimation (GAE; 48
T
max EGSA (004--02.00 82.
2VL* (T)
where À and T are the GAE discount factor and MDP horizon, respectively. 5% is the TD-error at time step k for 0. The state-of-the-ar UED algorithm, ACCEL (37), improves PLR- (27) by replacing its
random level generation with editor that mutates previously curated levels to gradually introduce complexity into the curriculum.
3 Related Work
It is important to note that regret-based UED approaches provide a minimax regret guarantee at Nash Equilibrium; however, they provide no explicit guarantee of convergence to such equilibrium. Beukman et al. [10] demonstrated that the minimax regret objective does not necessarily align with learnability: an agent may encounter UPOMDPs with high regret on certain levels where it already performs optimally (given the partial observability constraints), while there exist other levels with lower regret where it could still improve. Consequently, selecting levels solely based on regret can lead to regret stagnation, where learning halts prematurely. This suggests that focusing exclusively on minimax regret may inhibit the exploration of levels where overall regret is non-man maximall but opportunities for acquiring transferable skills for generalization are significant. Thus, there is compelling need for a complementary objective, such as novelty, to explicitly guide level selection towards enhancing zero-shot generalization performance and mitigating regret stagnation.
The Paired Open-Eree Ended Trailblazer (POET; (56) algorithm computes novelty based on environment encodings- vector of parameters that define level configurations, POET maintains record of the encodings from previously generated levels and computes the novelty of new level by measuring the average distance between the k-nearest neighbors of its encoding. However, this method for computing novelty comainn-speciff and relies on human expertise in designing environment encodings, posing challenges for scalability to complex domains. Moreover, due to UED's underspecified nature, where free parameters may yield one-to-many mapping between parameters and environments instances, each inducing distinct agent behaviors, quantifying novelty based on parameters alone is futile.
Enhanced POET (EPOET; (57]) improves upon its predecessor by introducing a domain-agnosse approach to quantify a level's novelty. EPOET is grounded in the insight that novel levels offer new insights into how the behaviors of agents within them differ. EPOET evaluates both active and archived agents' performance in each environment, converting their performance rankings into rank- normnizmd vectors. The level's novelty is then computed by measuring the Euclidean distance between these vectors. Despite addressing POET's domain- domain-specific limitations, EPOET encounters its own challenges. The computation of rank- normalzzd vectors only works for population based ap- proaches as it requires evaluating multiple trained student agents and incurs substantial computational costs. Furthermore, EPOET remains curriculum-agnostic, as its novelty metric relies on the ordering of raw returns within the agent population, failing to directly assess whether the environment elicits rarely observed states and actions in the existing curriculum.
Diversity Induced Prioritized Level Replay (DIPLR; (33)), calculates novelty using the Wasserstein distance between occupancy distributions of agent trajectories from different levels. DIPLR maintains a level buffer and determines level's novelty as the minimum distance between the agent's 's trajectory on the candidate level and those in the buffer. While DIPLR incorporates the agent's 's experiences into its novelty calculation, it faces significant scalability and robustness issues. First, relying on the Wasserstein distance notoriously costly. Additionally, DIPLR requires pairwise distance computations between all levels in the buffer, causing computational costs to grow exponentially with more levels. Finally, although DIPLR promotes diversity within the active buffer, fails to evaluate whether state-action pairs in the current trajectory have already been adequately explored through
3

---

past curriculum experiences, making it arguably still curriculum curriculum-gnoottcc. Further discussions on relevant literature can be found Appendix B
4 Approach: CENIE
The limitations of prior approaches to quantifying environment novelty underscore the need for more robust framework, motivating the development of CENIE. CENIE quantifies environment novelty through state-action space coverage derived from the agent's accumulated experiences across previous environments in its curriculum. In aunle-enviroomenn online reinforcement learning, coverage within the training distribution is often linked to sample efficiency [59], providing inspiration for the CENIE framework. Given UED's objective to enhance student's generalizability across vast and often unseen (during training) environment space, quantifying novelty in terms of state-action space coverage has several benefits. By framing novelty in this way, CENIE enables sample-efficient exploration of the environment search space by prioritizing levels that drive the agent towards unfamiliar state-action combinations, This provides principled basis for directing the environment design towards enhancing the generalizability of the student agent. Additionally, distinctive benefit of this approach that is not confined to any particular UED or DRL algorithms since it solely involves modeling the agent's state-action space coverage. This flexibility allows to implement CENIE atop any UED algorithm.
CENIE's approach to novelty quantification through state-action coverage introduces three key attributes, effectively addressing the limitations of previous methods: (1) domain-agnostic, (2) curriculum-aware, and (3) scalable. CENIE is domainnagnostt as it quantifies novelty solely based on the state-action pairs of the student, thus eliminating any dependency on the encoding of the environment. CENIE achieves curriculum- student's s past aggregated experiences, i.e., state-action space coverage, ensuring that the selection of environments throughout the curriculum is sample-efficient with regards to expanding the student's s state-action coverage. Lastly, CENIE demonstrates scalability by avoiding the computational burden associated with exhaustive pairwise comparisons costly distance metrics.
by quantifying novelty using model of the
Level Buffer
Trsin selected levels
Genenate new levils
Student
Teacher AIVO
Environment Regret
CENIE
Callect (s. a)
Novelly
Update Coverage
Figure 1: An overview of the CENIE framework. The teacher will utilise environment regret and novelty for curating student's curriculum. I' contains past experiences and is the recent trajectory.
4.1 Measuring the Novelty of a Level
To evaluate the novelty of new environments using the agent's state-action pairs, the teacher needs to first model the student's past state-action space coverage distribution. We propose use GMMs as they are particularly effective due to their robustness in representing nigh-dimensional continuous distributions [4 51. A GMM is a probabilistic clustering model that represents the underlying distribution of data points using weighted combination of multivariate Gaussian components. Once the iate-action distribution is modeled using a GMM, we can leverage it for density estimation. Specifically, the GMM allows us to evaluate the likelihood of state-action pairs induced by new environments, where lower likelihoods indicate experiences that are less represented in the student's current state-action space. This likelihood provides quantitative measure of dissimilarity in state- action space coverage, enabling a direct comparison novelty between levels. It is important to note that CENIE defines general framework for quantifying novelty through state-action space coverage;

---

GMMs represent just one possible method for modeling this coverage. Future research may explore alternatives to model state-action space coverage within the CENIE framework (see Section appendix for more discussions).
C Çin the
Before detailing our approach, we first define the notations used in this section. Let ig be particular level conditioned by an environment parameter 0. We refer to le as the candidate level, for which we aim determine its novelty. The agent's trajectory on le is denoted as 7g, and can be decomposed into a set of sample points, represented as X9 = {i (s, a) ~ To). The set of past training levels is represented by L and I = fz = (s, a) ~ TL} is a buffer containing the state-action pairs collected from levels across L. We treat I' as the ground truth of the agent's 's state-action space coverage, against which we evaluate the novelty of state-action pairs from the candidate level Xg.
To fit a GMM on r we must find a set of Gaussian mixture parameters, denoted as Ar = {(an, ;1; E2),-..,(0 (a-,, PKK, {x)))) that best represents the underlying distribution. Here, K denotes the predefined number of Gaussians in the mixture, where each Gaussian component is character- ized by its weight (as),, mean vector (ux), and covariance matrix (Ex), with k {I, ..., K), We employ the kmeans++ algorithm [22 for fast and efficient initialization of År. The likelihood of observing I' given the initial GMM parameters dr is expressed as:
J K
P(T I = II j=1 1=1
Ar)
NN
I Mes 2in)
(2)
where zi is a state-action pair sample from r. (N;; /4k, Ex) represents the multi-dimennional Gaussian density function for the k-th component with mean vector 14, and covariance matrix Σx- To optimise Ar, we use the Expectation Maximization (EM) algorithm [22] 43) because Eq. 2 is non-linear function of År, making direct maximization infeasible. The EM algorithm iteratively refines the initial Ap to estimate a new X such that P(X X²) > P(X Ar). This process is
repeated iteratively until some convergence, i.e.. || X Arll < c, where E a small threshold.
Once the GMM is fitted, we can use Ar to perform density estimation and calculate the novelty of the candidate level l-- Specifically, we consider the set of state-action pairs from the agent's trajectory, Xo. and compute their posterior likelihood under the GMM. This likelihood indicates how similar the new state-action pairs are to the learned distribution of past state-action coverage. Consequently, the novelty score of la is represented as follows:
NOVELTY,, 1 Xoo
log L(Xo Ar)
log p(ra Ar)
XXo
where 3t is a sample state-action pair from X8. As shown in Eq. 3 we take the negative mean log-likelihood across all samples in Xo to attribute higher novelty scores to levels with state-action pairs that are less likely to originate from the aggregated past experiences, P. This novelty metric promotes candidate levels that induce more novel experiences for the agent during training. More details on fitting GMMs are explained in Appendix D.I
Design considerations for the GMM First, we specifically designate the state-action coverage buffer, i.e., r, as Furst--n-FirttOuu (FIFO) buffer with fixed window length. By focusing fixed window rather than the entire history of state-action pairs, our novelty metric avoids bias toward experiences that are outdated and have not appeared in recent trajectories. This design choice helps reduce the effects of catastrophic forgetting prevalent in DRL. Next, it is known that by allowing the adaptation of the number of Gaussians in the mixture, i.c., K in Eq. 2 any smooth density distribution can be approximated arbitrarily close [24]. Therefore, to optimize the GMM's representation of the agent's state-action coverage distribution, we fit multiple GMMs with varying numbers of Gaussians within a predefined range at each time step and select the best one based on the silhouette score [45), an approach inspired by Portelas et al. [40]. The silhouette score evaluates clustering quality by measuring both intra-cluster cohesion and inter-cluster separation. This approach enables CENIE to construct pseudo-online GMM model that dynamically adjusts its complexity to accommodate the agent's 's changing state-action coverage distribution.
4.2 State-Action Space Coverage Directed Training Agent
5

---

Algorithm ACCEL-CENIE
Input: Level buffer size N, Component range [Kmin Kmax] FIFO window size W, level generator g Initialize: Student policy Ta level buffer B, state-action buffer I', GMM parameters Ap
1: Generate N initial levels by G to populate B
2: Collect ", is trajectories on each level in and fill up
3: while not converged do
4: Sample replay decision, ~ U10, 1]
5: if'e 0.5 then
6:
Generate new level Ig by g
7:
Collect trajectories
lo. with stop-gradient 7 Compute novelty score for lg using Ar (Eq and Eq 4
8:
9:
Compute regret score for (Eq 1 and Eq
10:
Update B with lo if Preplay (4)) is greater than that of any levels in B (Fq
11:
else
12:
Sample replay level lo ~ B according to Preplay
Collect trajectories on
14:
Update Ty with rewards I((T) Update I' with and resize W for k in range minn to Kmax do
16:
Fit GMM; with l components on I' and compute its silhouette score end for
18:
Select GMM parameters with the highest silhouette score replace År Perform edits on lo to produce 1/
20:
Collect trajectories on lg. with stop-gradient 7).1 Compute novelty score for l/2 using Ar (Eg and Eq
22:
23:
Compute regret score for ly (Eq I and Eq 4)
24:
Update B with l/ if P Preplay (%)) greater than that of any levels in B (Eq
25:
end if
26:
end while
With a scalable method quantify the novelty of levels, we demonstrate its versatility and effective- ness by deploying it on top of the leading UED algorithms, PLR and ACCEL. For convenience, in subsequent sections, we will refer this CENIE augmented methodology of PLR and ACCEL using GMMs as PLR-CER CENII and ACNIL, respectively. Both PLR and ACCEL utilize replay mechanism train their students on the highest-regret levels curated within the level buffer. To integrate CENIE within these algorithms, we use normalized outputs of a prioritization function to convert the level scores (novelty and regret) into level replay probabilities (Ps):
1(S)))
Ps
h(S)3
where h is prioritization function (e.g. rank) with tunable temperature 3 that defines the prioriti- zation of levels with regards to any arbitrary score S. Following the implementations in PLR and ACCEL, employ
the rank prioritization function, i.e., f((S)) 1/rank(S,), where rank (S,) is the rank of level score S; among all scores sorted in descending order. In ACCEL-CENT and PLR-CENIE, we use both the novelty and regret scores determine the level replay probability:
Preplay
Px (1 a:) Pn
where Py and PR the prieott-pioittized probability and regret- prioritized probability respectively, and a allows us to adjust the weightage of each probability. The complete procedures for ACCEL- CENIE are provided in Algorithm I and for PLR-CENIE in the appendix (see Algorithm 2 Key steps specific to CENIE using GMMs are highlighted in blue.
Experiments
In this section, we benchmark PLR-CENIE and ACCEL-CENTE against their predecessors and set of bascline algorithms: Domain Randomization (DR), Minimax, PAIRED, and DIPLR. The

---

technical details of each algorithm are presented in Appendix E We empirically demonstrated the effectiveness of CENIE on three distinct domains: Minigrid. BipedalWalker, and CarRacing. Minigrid is partially observable navigation task under discrete control with sparse rewards, while Bipeda/Walker and CarRacing are partially observable continuous control tasks with dense rewards. Due to the complexity of mutating racing tracks, CarRacing is the only domain where ACCEL and ACCEL-CENIE are excluded. The experiment details are provided in Appendix [ Following standard UED practices, all agents were trained using Proximal Policy Optimization (PPO; (49 across the domains, and we present their zero-shot performance on held-out tasks. We also conducted ablation studies to assess the isolated effectiveness of CENIE's novelty metric (see Appendix (A).
For reliable comparison. we employ the standardized DRL evaluation metrics M. presenting the aggregate inter-quartile mean (IQM) and optimality gap plots after normalizing the performance with a min-max range of solved-raterreturns. Specifically, IQM focuses on the middle 50% of combined runs, discarding the bottom and top 25%, thereby providing robust measure of overall performance. Optimality gap captures the amount by which the algorithm fails to meet a desirable target (e.g.. 95% solved rate), beyond which further improvements are considered unimportant. Higher IQM and lower optimality gap scores are better. The hyperparameters for the algorithms in each experiment are specified in the appendix.
5.1 Minigrid Domain
First, we validated the augme-au methods in Minigrid 23 20 a popular benchmark due to
its case of interpretability and customizability, Given its sparse reward signals and partial observability, navigating Minigrid requires the agent to explore multiple possible paths before successfully solving the maze and receiving rewards for policy updates. Therefore, Minigrid is an ideal domain to validate the exploration capabilities of the MENIE--augmente algorithms.
RotteeRRome
RoteenRooms2
Lagyrinth
Lasyrinth2
Maze
Naoo2
PerfectMage
LargoComidor
Solvol
Netimx
RARRD
DILRR
PLA-CENI
ACCEL-CEVE
Figure 2: Zero-shot transfer performance in eight numan-designa test environments. The plots based on the median and interquartile range of solved rates across 5 independent runs.
Following prior UED works, we train all student agents for 30k PPO updates (approximately 250 million steps) and evaluate their generalization on eight held-out environments (see Figure 2}. Figure 2 demonstrates that ACCEL-CENIE outperforms ACCEL in all testing environments. Moreover, CENIE shows significantly better performance in seven test environments compared to PLR- This underscores the ability of CENIE's novelty metric to complement the UED framework, particularly in improving generalization performance beyond the conventional learning potential metric, regret. Further empirical validation in Figure ((a] confirms ACCEL-CENIRR superiority over ACCEL in both IQM and optimality gap. PLR-CENIE also outperforms its predecessor, PLR 1 by significant margin. Notably, PLR-CENIE's performance is able to match ACCEL's, which is significant considering PLR-CENIE uses a random generator while ACCEL uses an editing mechanism to introduce gradual complexity to environments.
Beyond the normal-size testing mazes, we consider a more challenging evaluation setting. We evaluate the fully-trained student policy of PLR PLR- I-CCIE,,,E ACCEL, and ACCEL-CENIE on PerfectMazzeLage (shown in Figure ((b).. an distribbuiiiooionn environment which has 51 51 tiles and a episode length of 5000 timesteps a much larger scale than training levels. We evaluate the agents for 100 episodes (per seed), using the same checkpoints Figure 2 ACCEL-CENIE and ACCEL achieved comparable zero-shot transfer performance. Notably, PLR-CENT achieved close
7

---

I0M
aptimality Gap
Siland
DR
Minimax PAIRED DIPLR
PLR-CENIE ACCEL
ACCEL
ACCEL-CENIE
0.00 0.25 0.50 0.75
0.25
0.50
0.75
1.50
Min-Max Normalized Score
Figure 3: (a) Aggregate zero-shot transfer performance in Minigrid domain across independent runs. (b) Zero-shot test performance of PLR- PLR-CENIE, ACCEL, and ACCEL-CENIE on PerfectMazel across independent runs.
50% solved rate, matching ACCEL's performance. This is significant improvement from PLR which had less than a 10% solved rate.
5.2 Bipedal Walker Domain
Figure 4: Student's generalization performance 6 Bipedal testing environments during training. Each curve is measured across 5 independent runs (mean and standard error).
We also evaluated the CENIE-augmented algorithms in the Bipeda/Walker Walker domain [56] 37 which is a partially observable continuous domain with dense rewards. We train all the algorithms for 30k PPO updates (~IB IB timesteps) and then evaluate their generalization performance six distinct test environments: BipkdalWalker (default), Hardcore, Stair, PitGap, Stump, and Roughness (visualized in Figure 6(a). To monitor the student's generalization performance evolution, assess the student policy every 100 PPO updates across six testing environments during the training period.
In Figure ACCEL-CENIE outperforms ACCEL in five testing environments, with both achieving parity in Roughness challenge, establishing ACCEL-CENTE as the leading UED algorithm in BipedalWalker. Similarly, PIR-CENIE consistently outperforms PLR across all testing instances, except for the Stump challenge, where both algorithms exhibit similar performance. We present the aggregate results after min-max normalization (with range=[O, 300] all test environments) in Figure 6(b) Both ACCEL-CENIE and RERCCENIE exhibit better performance compared to their predecessors in the IQM and optimality gap metrics. Notably, ACCEL-CENIE outperforms all benchmarks by substantial margin, achieving close to 55% of optimal performance.
Table 1: Coverage of state-action space across 30k PPO updates in the Bipedal domain.
PLR
PLR-CENIE
ACCEL
ACCEL-CENIE
State-action Space Coverage
43.4%
55.3%
42.5%
47.6%
Next, we tracked the evolution state-action space coverage throughout training to evaluate the impact of CENIE's novelty objective on the curriculum's exploration of the state-action space. During

---

training, state-action pairs encountered by the agent were collected for both PLR' and ACCEL, along with their CENIE--ugmentedd versions. To visualize the distribution of these high- sish-dimensionall state-action pairs, we applied t-distributed Stochastic Neighbor Embbedding (t-SNE; (54) to project them into a 2-D space. The resulting evolution plot and detailed implementation steps are provided in Appendix A.2 Afterwards, we quantified state-action space coverage by discretizing the 2-D scatterplot into cells and calculating the percentage of total cells occupied by each algorithm. As shown in Table I CENIE drives ACCEL-CENIE and PLR-CENIE to achieve significantly broader state-action coverage by the end of 30k PPO updates compared to their predecessors. This evidence supports that the inclusion of CENIE's novelty objective for level replay prioritization contributes to broader state-action space coverage.
ACCEL
ACCEL-ITME
X663
30.00
X60
80:00 Insoval
2008
Exty
Challegingg
lenging
Estremalyy Chellnging
Figure 5: Difficulty composition of levels replayed by ACCEL and ACCEL-CENIE during training.
To understand ACCEL-CENIE's improvement ACCEL, analyzed the difficulty composition of replayed levels at various training intervals across five seeds, as shown in Figure Level difficulty assessed based environment parameters such stump height and pit gap width, using metrics
adapted from Wang et al. (56) (details in Appendix A.2). It is evident that ACCEL predominantly favors "Easy" "Moderate" difficulty levels, whereas ACCEL-CENIE progressively incorporates "Challenging" levels into its replay selection throughout training.
The disparity in level difficulty distribution between ACCEL and ACCEL-CENDL is critical factor in understanding their observed performance differences. ACCEL's training curriculum tends to remain within comfort zone, consistently selecting limited subset of simpler levels where the agent experiences high regret. However, this can be problematic when considering the regret stagmation problem. Specifically, in the event where the easier levels exhibit irreducible regret, it restrict the agent's 's exposure to more complex scenarios, thereby constraining its generalization potential. In contrast, ACCEL-CENIE' integration of novelty objective actively selects challenging levels, pushing the agent beyond its comfort zone into unfamiliar, complex environments. This novelty-based regularization fosters the exploration of under-explored regions in the state-action space, if regret levels are low, thereby enhancing the agent's generalization capabilities. Furthermore, with mutation-bass based approach like ACCEL, this environment selection strategy may generate mutate new levels with high learning potential, further enriching the training curriculum.
ICM
Optimality Gap
DR
Minimax
PAIRED
DIPLA
PLR
PLR-C CENIE
ACCEL
ACCEL-CENIE
0.0
0.2
0.4
0.6
0.45
0.60
0.75 0.90
Min-Max Normalized Score
(b)
Figure 6: (a) Bipedal Walker domain and (b) Aggregate zero-shot transfer performance in Bipedal- Walker.
5.3
CarRacing Domain
Finally, we evaluated the effectiveness of CENIE by implementing on PI.R- within the CarRacing domain [16] 22). In this domain, the teacher manipulates the curvature of racing tracks using Bézier

---

curves defined by a sequence of 12 control points, while the student drives on the track under continuous control with dense rewards. We train the students in each algorithm for 2.75k PPO updates (~5..MM steps), after which we test the zero-shot transfer performance of the different algorithms on 20 levels replicating real-world Formula One (F1) tracks introduced by Jiang al. (27]. These tracks are guaranteed to be OOD as their configuration cannot be defined by Bézier curves with only 12 control points. The middle image in Figure 6p shows a track generated by domain randomization and the rightmost image shows bird's s-eye view of the FI-USA benchmark track.
IOM
Optimality lit Gap
PAIRED
DIPLR
PLR
PLR-CENIE
0.2
0.4
0.6
0.8
0.30
0.45
0.60
0.75
Min-Max Normalized Score
(a)
(b)
Figure 7: (a) CarRacing domain and (b) Aggregate zero-shot transfer performance in CarRacing.
The aggregate performance after min-max normalization of all algorithms is summarized in Figure 7p. Note that the min-max range varies across Fl tracks due to different specifications on the maximum episode steps (see Table S in the appendix for more details). Once again, the CENIE-augmented algorithm,
achieves the best generalization performance in both IQM and optimality gap scores. Table 3 in the appendix shows the zero-shot transfer returns on all 20 F1 tracks. PLR-CENIE consistently outperforms matches the best- pest-performin baseline on all tracks.
Figure g presents the total regret in the level replay buffer throughout the training pro-
for both PLR- and cess. Interestingly, PLR-C RENNIE maintains comparable, or even slightly higher, levels of regret across the training distribution, despite not directly optimizing for it. This outcome suggests that CENIE's novelty objective synergizes with the discovery of high-regret levels, providing counterintuitive evidence that optimizing solely for regret is not the only, nor necessarily the
1400
Total Regret in Reploy Butter
1200
800
500
400-
most effective, strategy for identifying levels with high learning potential (as approximated by regret). Intuitively, value predic- tions are inherently less reliable in regions of lower coverage density- areas characterized by higher entropy high uncer- tainty regarding optimal actions-since these regions are less frequently sampled for agent's 's learning. These high-entropy re- gions are prime candidates for high-regret outcomes, especially when using a bootstrapped regret estimate, as in Eq. T due to the value estimation еттоr in such states. By pursuing novel environments based on coverage, CENIE indirectly enhances the discovery of high-regret states. highlighting that novelty- driven autocurricula can effectively complement regret- based methods in uncovering diverse and
200-
1000
2000
Student Updates
PLR
PLR-CENIE
Figure 8: Total regret in level replay buffer for PLR and PLR- PLR-CENIE over training in CarRacing.
challenging training scenarios.
6 Conclusion
In this paper, we introduced Coverage-based Evaluation of Novelty In Environment (CENIE), scalable, domain-agnostic, and curriculum-aware framework for quantifying environment novelty in UED. We then proposed an implementation of CENIE that models this coverage and measures environment novelty using Gaussian Mixture Models. By incorporating CENIE with existing UED algorithms, we validated the framework's 's effectiveness in enhancing agent exploration capabilities and zero-shot transfer performance across three distinct benchmark domains. This promising approach marks a significant step towards unifying novelty-driven exploration and regret-driven exploitation for training generally capable RI. agents. We encourage motivated readers to refer to the appendix for further studies and discussions on CENIE.
10

---

Acknowledgments
This research/project is supported by the National Research Foundation Singapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: AISG2-RP-2000-0117 and Lee Kuan Yew Fellowship awarded Pradeep Varakantham.
References
[1] R. Agarwal, M. Schwarzer, P. S. Castro, A. C. Courville, and M. Bellemare. Deep reinforcement learning at the edge of the statistical precipice. Advances in neural information processing systems, 34:29304-29320, 2021.
[2] I. Akkaya, M. Andrychowicz, M. Chociej, M. Litwin, B. McGrew, A. Petron, A. Paino, M. Plappert, G. Powell, R. Ribas, et al. Solving rubik's 's cube with a robot hand. arXiv preprint arXiv:1910.07113, 2019.
[3] O. M. Andrychowicz, B. Baker, M. Chociej, R. Jozefowicz, B. McGrew, J. Pachocki, A. Petron, M. Plappert, G. Powell, A. Ray, et al. Learning dexterous in-hand manipulation. The Interna- tional Journal of Robotics Research, 39(1):3-20, 2020.
[4] D. Arthur, S. Vassilvitskii, et al. k-means++: The advantages of careful seeding. In Soda, volume 7, pages 1027-1035, 2007.
[5] Assent. Clustering high dimensional data. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2(4))340 2012.
[6] P. Auer, N. Cesa-Biand Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77. 2002. doi: 10.1 10.1137/509973370019999377 https:tts::// //doi. org/ 10. 1117 1137//00975337013988777777
[7] A. S. Azad, I. Gur, J. Emhoff, N. Alexis, A. Faust, P. Abbeel, and I. Stoica. Clutr: Curriculum learning via unsupervised task representation learning. In International Conference on Machine Learning, pages 1361-1395. PMLR, 2023.
[8] M. G. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos. Unifying count-based exploration and intrinsic motivation. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, page 1479-1487. Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
[9] C. Berner, G. Brockman, B. Chan, V. Cheung, Debiak, C. Dennison, D. Farhi, Q. Fischer, S. Hashme, C. Hesse, et al. Dota 2 with large scale deep reinforcement learning, arXiv preprint 1rXiv:1912.06680 2019.
[10] M. Beukman, S. Coward, M. Matthews, M. Fellows, M. Jiang, M. Dennis, and Foerster. Refining minimax regret for unsupervised environment design. In International Conference on Machine Learning. PMLR, 2024.
[11] D. Blei and M. Jordan. Variational inference for dirichlet process mixtures. Bayesian Analysis, 1, 03 2006. doi: 10. 10.1224/06-BA BA104.
[12] J. Blömer and K. Bujna. Simple methods for initializing the em algorithm for gaussian mixture models. CoRR, 2013.
[13] O. Borchert. Pycave, 2022. URL httttt/////tttubb http:s///gitt....oom/rrrrrrrrrrp
[14] C. Bouveyron, S. Girard, and C. Schmid. High-dimensional data clustering. Computational statistics & data analysis, 52(1):502-519 2007.
[15] H. Bozdogan. Model selection and Akaike's Information Criterion (AIC): The general theory and its analytical extensions. Psychometrika, 52(3):345-370, Sept. 1987. ISSN 1860-0980, doi: 10. 10.00//000229331..
[16] G. Brockman, V. Cheung, I.. Pettersson, Schneider, J. Schulman, Tang, and W. Zaremba. Openai gym. arXiv preprint arXiv: 104...0060.,1,,,0.. 2016.

---

[17] J. Bruce, M. Dennis, A. Edwards, J. worker-Holler, Y. Shi. E. Hughes, M. Lai, A. Mavalankar, R. Steigerwald, C. Apps. Y. Aytar, S. Bechtle, F. Behbahani, S. Chan, N. Heess, L. Gonzalez. S. Osindero, S. Ozair, S. Reed, J. Zhang. K. Zolna, J. Clune, N. de Freitas, S. Singh, and Rocktäschel. Genie: Generative interactive environments, 2024. URL. httth://p//aaii
org/ Brgg/bss/24e 20tp//240.115991
[18] Y. Burda, H. Edwards, D. Pathak, A. Storkey, T. Darrell, and A. A. Efros. Large-scale study of curiosity-driven learning. arXiv preprint 1808. 04355, 2018.
[19] Y. Burda, H. Edwards, Storkey, and O. Klimov. Exploration by random network distillation, 2018. httttttss///xiiiv wrgg/bs////t/ 12894
[20] M. Cheevalier-Boiseett B. Dai, M. Towers, R. de Lazcano, L. Willems, S. Lahlou, S. Pal, P. S. Castro, and J. Terry. Minigrid & miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks. CoRR, 0bs/2300.118311 2023.
[21] K. Cobbe, O. Klimov, C. Hesse, T. Kim, and J. Schulman. Quantifying generalization in reinforcement learning. In International Conference Machine Learning, pages 1282-1289. PMLR, 2019.
[22] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the algorithm. Journal of the royal statistical society: series B (methodological), 39(1): | 1-22, 1977.
[23] M. Dennis, N. Jaques, E. Vinitsky, A. Bayen, Russell, A. Critch, and Levine, Emergent complexity and zero-shot transfer via unsupervised environment design. Advances in neural information processing systems, 33: 33:13049 10133009-33665 13061, 2020.
[24] M. A. Figuciredo. On gaussian radial basis function approximations: Interpretation, extensions, and learning strategies. In Proceedings 15th International Conference on Pattern Recognition. ICPR-2000, volume 2, pages 618-621. IEEE, 2000.
[25] K. F.R.S. Liii. on lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559-577 1901. doi: 10. 00.100001488444004422729
[26] H. Hu and J. N. Foerster. Simplified action decoder for deep multi-agent reinforcement learning. arXiv preprint arXiv: 19122029222228 2019.
[27] M. Jiang, M. Dennis, J. Parker-Holder, J. Foerster, E. Grefenstette, and T. Rocktäschel. Replay- guided adversarial environment design. Advances Neural Information Processing Systems, 34:1884 111888848999,,,111 2021.
[28] M. Jiang, E. Grefenstette, and T. Rocktäschel. Prioritized level replay. In International Conference on Machine Learning, pages 4940-4950. PMLR, 2021.
[29] D. Kingma and M. Welling. Auto-encoding variational bayes, 2022. URL https://arxxv at/aaabb//11///////
[30] J. Lehman and K. Stanley. Exploiting open-endedness to solve problems through the search for novelty. Artificial Life- ALIFE, 01 2008.
[31] J. Lehman and K. O. Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation, 19(2):189) 189-223, 2011. doi: 10.1 20.116/0
[32] J. Z. Leibo, E. Hughes, M. Lanctot, and T. Graepel. Autocurricula and the emergence of innovation from social interaction: A manifesto for multi-agent intelligence research, 2019. URL htttt:://arxii org/ abs/ 19903.00744
[33] W. Li, P. Varakantham, and D. Li. Effective diversity in unsupervised environment design. arXiv preprint arXiv:2301.08023 2023.
[34] I. Mediratta, M. Jiang, J. Parker-Holder, M. Dennis, E. Vinitsky, and T. Rocktäschel. Stabilizing unsupervised environment design with a learned adversary, 2023. URL htR.ssts:::/ httpttttts///iiiv... abs/ abs/2308. 200//9778.07777
12

---

[35] K. Musgrave, S. J. Belongie, and S. N. Lim. Pytorch adapt. ArXiv,
2022.
[36] G. Ostrovski, M. G. Bellemare, A. van den Oord, and R. Munos. Count-based exploration with neural density models. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, ICML'17, page 2721-2730. JMLR.org, 2017.
[37] J. Parker-Holder, M. Jiang, M. Dennis, M. Samvelyan, J. Foerster, E. Grefenstette, and Rocktäschel. Evolving curricula with regret-based environment design. arXiv preprint arXiv:2203.01302, 2022.
[38] D. Pathak, P. Agrawal, A. Elros, and T. Darrell. Curiosity-driven exploration by self- supervised prediction. In International conference on machine learning, pages 2778-2787. PMLR, 2017.
[39] I.. Pinto, J. Davidson, R. Sukthankar, and Gupta. Robust adversarial reinforcement learning.
In International conference on machine learning, pages 2817-2826. PMLR, 2017.
[40] R. Portelas, C. Colas, K. Hofmann, and P.-Y. Oudeyer. Teacher algorithms for curriculum learning of deep rl in continuously parameterized environments, 2019. URL https://arxiv org/ htgg/bs///0 att//b1//191..... 1910. 07224
[41] R. Portelas, C. Colas, K. Hofmann, and P.-Y. Oudeyer. Teacher algorithms for curriculum learning of deep rl in continuously parameterized environments. In Conference on Robot Learning, pages 835-853, PMLR, 2020.
[42] R. Portelas, C. Colas, Weng. K. Hofmann, and P.-Y. Oudeyer. Automatic curriculum learning for deep rl: short survey. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI'20, 2021. ISBN 9780999241 165.
[43] R. A. Redner and H. F. Walker. Mixture densities, maximum likelihood and the em algorithm. SIAM review, 26(2): 1992 1984.
[44] D. J. Rezende and S. Mohamed. Variational inference with normalizing flows, 2016. URL 05770
[45] P. J. Rousseeuw. Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of computational and applied mathematics, 20:53-65, 1987.
[46] T. Schaul. Prioritized experience replay. arXiv preprint arXiv: 1.05955, 2015.
[47] J. Schmidhuber. A Possibility for Implementing Curiosity and Boredom in Model-Building Neural Controllers. In From Animals to Animats: Proceedings of the First International Confer- ence on Simulation of Adaptive Behavior. The MIT Press, 02 1991. ISBN 9780262256674. doi: 10.755 1/iipprs/irsss//111. 11.331155.0000000 0030
htRpat/:::/// //doi. org/ 10. 75177///mmmttprrra/331500000
[48] J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint urXiv:/5060024:. 2015.
[49] Schulman, Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint vrXiv:1707.06344 2017.
[50] S. Singh, R. L. Lewis, A. G. Barto, and J. Sorg. Intrinsically motivated reinforcement learningg An evolutionary perspective. IEEE Transactions on Autonomous Mental Development, 2(2): 70-82, 2010. doi: 10.1
1033.
[51] K. O. Stanley and J. Lehman. Why Greatness Cannot Be Planned: The Myth of the Objective. Springer Publishing Company, Incorporated, 2015, ISBN 3319155237.
[52] J. Teoh Jing Xiang, W. Li, and P. Varakantham. Unifying regret and state-action space coverage for effective unsupervised environment design. Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems, AAMAS '24, page 2507-2509, Richland, SC, 2024. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9798400704864.
13

---

[53] J. Tobin, R. Fong, A. Ray, J. Schneider, W. Zaremba, and P. Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. In 2017 IEEE/RS] international conference intelligent robots and systems (IROS), pages 23-30. IEFF, 2017.
[54] L. Van der Maaten and G. Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
[55] C. Viroli and G. J. McLachlan. Deep gaussian mixture models, 2017. URL https://aaae /arxivv org/ attpa/bss/11...1111 1tt.//111..00999
[56] R. Wang, Lehman, J. Clune, and K. O. Stanley, Paired open-ended trailblazer (poet): Endlessly generating increasingly complex and diverse learning environments and their solutions. arXiv preprint arXiv: 1901. 00753,,,,,, 2019.
[57] R. Wang, Lehman, A. Rawal, Zhi, Y. Li, J. Clune, and K. Stanley. Enhanced poet: Open- ended reinforcement learning through unbounded invention of learning challenges and their solutions. In International Conference on Machine Learning, pages 9940-9951. PMLR, 2020.
[58] M. Wattenberg, F. Viégas, and I. Johnson. How to use t-sne effectively. Distill, 1(10):e2, 2016.
[59] T. Xie, D. J. Foster, Y. Bai, N. Jiang, and S. M. Kakade. The role of coverage in online reinforcement learning. arXiv preprint arXiv:2210.04155: 2022.
[60] Zhang, J. Lehman, K. Stanley, and Clune. Omni: Open-endedness via models of human notions of interestingness, 2024. URL
01711
[61] R. Zhao and V. Tresp. Curiosity-drivee experience prioritization via density estimation, 2020. URL,
08039
[62] R. Zhao, Sun, and Tresp. Maximum retropy-reeullarized multi-goal reinforcement learning. In International Conference Machine Learning, pages 7553-7562, 2019.
[63] K. Zhou, Z. Liu, Y. Qiao, T. Xiang, and C. C. Loy. Domain generalization: A survey. IEEE Transactions on Patlern Analysis and Machine Intelligence, 2022.
14

---

A Extended Experiment Details and Ablation Studies
In this section, present extended experiment details regarding the results presented in the main body of the paper. To isolate the individual effects of regret and novelty, we conduct an ablation study in which only novelty is used to prioritize levels in the level buffer. We denote the DENIE-augmente versions of the PLR- and ACCEL. which use only novelty for level prioritization (set a = 1 in PLR-CENIE and ACCEL-CENIET, respectively.
Equation
Interestingly, we observed that in several instances, the ablation models, CENIE demonstrated comparable even superior zero-shot transfer performance compared to their regret metric counterparts, PLR- and ACCEL. This finding suggests that, in specific scenarios, prioritizing training levels based on novelty alone can effectively shape curricula. This is especially notable because our GMM-based novelty metric, unlike regret, does not rely on predefined domain- specific reward structures; rather, it is derived solely from the agent's 's trajectory data across different levels.
and ACCEL.
However, it is important to note that these ablation results do not imply that regret should be entirely replaced by novelty-based level selection. Novelty alone may encounter limitations in extremely large actein spaces where balance with regret is essential for effective exploration. By combining novelty and regret in CENIE to shape the training curriculum, we significantly enhance the agent's s generalization capabilities beyond those of previous algorithms, shown in our main experiments. This finding highlights the powerful synergy between CENIE's novelty metric and traditional regret-based approaches, resulting in more robust and effective training paradigm.
A.1 Minigrid Domain
After training all the student agents for 30k PPO updates (~250M steps), we evaluate their transfer capabilities on eight held-out testing environments (see the first row in Figure We summarize all the results in Figure 9 In addition to the zeoo transfer evaluation, we summarize the students' aggregate zero-shot transfer performance, i.e., IQM and Optimality Gap, in Figure I0
In Figure PLR-CENIE outperforms PLR+ in most of the testing environments (6 out of 8), indicating that the novelty metric plays a more significant role compared to regret in the Minigrid domain for the PLR- - algorithm. In contrast, ACCEL shows a marginal performance advantage over ACCEL-CENIEE in the testing environments, with two wins, four losses, and two ties. Importantly, for both cases ELL-CENIE and ACCEL-CENIE the combination of both regret and novelty yields the strongest performance, outperforming their individual metric counterparts. This finding supports the assertion that the CENIE framework effectively complements the regret metric, helping UED algorithms achieve better performance.
Rod
Sabter 2oomm2
Lasyrinth
Lacyrinth2
Nare
Namo2
PerfectManee
LanpeCaridto
Selved
PURCENE
PURCCENE"
ACCEL
ACCEL-CENIE
ACCEL-CENIE
Figure 9: Zero-shot transfer performances in Minigrid. The plots are based on the median and interquartile range of solved rates across 5 independent runs. All student models are evaluated after 30k student PPO updates.
The aggregate IQM and Optimality Gap results shown in Figure 10 further validates the above conclusion, ACCEL-CENIE and PiR-CENIE outperform their counterparts - (ACCEL, ACCEL- CENIE() and (PLR-, PLR-CENIE) in terms of both IQM and Optimality Gap. In particular,
15

---

within the PLR framework, the novelty-driven level selection strategy (PLR-CENIE') significantly surpasses the regret-based approach (PLR performance.
IQM
Optimality Gap
PLR 1
PLR-CENIE PLR-CENIET
ACCEL
ACCEL LECEE ACCEL-CENIET
0.45 0.60 0.75
0.90
0.15
0.30
0.45 0.60
Min-Max Normalized Score
Figure 10: IQM and Optimality Gap ablations in Minigrid domain. Results are measured across independent runs.
We also provide qualitative analysis of the effect of the novelty metric the level replay buffer of PLR-CENIE in Minigrid for the experiments detailed under Section in the main body. Specifically, we highlight levels that feature the lowest regret (bottom 10) yet exhibit the highest novelty (top 10); these are showcased in the first row of Figure IT Conversely, levels that score within the lowest 10 for both regret and novelty are displayed the second row of the same figure. Visually, we observe that levels with high novelty and low regret present complex and diverse scenarios that challenge the student. In contrast, the levels displayed in the second row, characterized by low regret and low novelty, often resemble simple, empty mazes that offer limited learning opportunities. While it is not feasible to present every example level here, the contrast between the two groups stark. Levels selected based on low regret but high novelty are significantly more varied and intricate than those chosen for their low novelty, despite both groups having low regret scores. This demonstrates that incorporating novelty alongside regret in the selection process enhances the ability to identify levels that present more interesting trajectories (experiences) for the student to learn from.
Low Regret and Novelty
Regret and Low Novelty
0k
10k
15k
20k
25k
30k
Figure 11: Levels in the level replay buffer of PLR-CENIE. X-axis: number of student PPO updates.
A.2 BipedalWalker Domain
We closely tracked the evolution of state-action space coverage during the training to reveal how the incorporation a novelty objective affected the curriculum generation. State-action pairs encountered by the agent during training are collected for PLR- ACCEL, PIR PLR-CENIE, and ACCEL-CENIEE Given the high-dimensionality of the state-action pairs in the BipedalWalker domain, we employed t-distributed Stochastic Neighbor Embedding (t-SNE; [54)) ), nonlinear dimensionality reduction technique, to project the state-action pairs onto a more manageable wwo-dimensional manifold. t- SNE captures much of the local structure of the high-dimensional data. while also revealing global structures, such as the presence of clusters at several scales [54] 58). The resulting embedded state-action pairs mapped onto 2-D scatterplot, allowing to visualize the exploration of the state-action space by each algorithm as the number policy updates increases. The evolution is illustrated in Figure 12
Furthermore, we quantified the occupancy of 2-D scatterplot by each method. To achieve this, discretized the scatterplot into cells and computed the percentage of total cells occupied by data
16

---

points generated by each method. in the main paper presents the state-action space coverage percentages for each method. Notably, both PLR-CENIE and ACCEL-CENIE exhibit significantly broader coverage of the state-action space compared to their predecessors. This evidence supports the assertion that the outperformance CENIE- algorithms is associated with the broader coverage of the state-action space. Note that although the PLRRbased algorithms exhibit higher state-action space coverage, they show poorer transfer performance compared to ACCEL-based algorithms. This discrepancy is likely because ACCEL initiates the curriculum with "easy" levels, and gradually introducing complexity via minor mutations, whereas PLR relies on DR, which lacks the fine-gras seee-graind control over difficulty progression that ACCEL's mutation based method offers. As a result, while CENIE enhances state-action space coverage for both ACCEL and PLR, it is likely that ACCEL's gradual complexity introduction mechanism capitalizes this enhancement more effectively.
1k Student Updates
Student Updates
20k Student Updates
Student Updates
ACCEL-CENIE
ACCEL
PLR-CENIE
PLR
Figure 12: Evolution of the state itatenaction space coverage of ACCEL-CENIE, ACCEL, PLR-CENIE,
and PLR for a seed. The checkpoints are 1k, 10k, 20k, and 30k policy updates during the training.
To plot the level difficulty composition of the replayed levels by ACCEL and ACCEL-CENIE in Figure 5 of the main paper, adapted the difficulty thresholds originally defined in Wang et al. [56]. This is because their thresholds were designed for a smaller 5-D encoding BipedalWalker environment, whereas our setting uses 8-D encoding, which allows for higher complexity of levels to be generated. Specifically, we introduced an additional threshold for maximum stairs height, shown in Table A level is classified as Easy if it meets none of the thresholds, and as Moderate, Challenging, Very Challenging, or Extremely Challenging if it meets one, two, three, or four thresholds, respectively.
Note that our Figure difffers from Figure 12 Parker-Holder al. 37 which shows the difficulty distribution of the levels generated and added into the buffer, but not the actual levels selected
17

---

Table 2: Environment encoding thresholds for 8D BiledalWalker.
Stump Height (High)
Pit Gap (High)
Ground Roughness
Stairs Height (High)
2.4
4.5
5
by the teacher for the student to replay/train on. Also, their figure is defined for the 5D encoding setting. On that note, this also demonstrates that CENIE remedies inefficiency in the original ACCEL algorithm, where mutation-based generation is capable of producing high complexity levels but not selected for student training due solely depending regret for level prioritization.
BipedsWWalter
Harocore
PhGop
Roughness
Student PPO Updates
Student PPO Updates
Student PPO Upcates
Student PPO Updaces
Student PPO Updates
Student PPO Updates
PLR-CENIE
PLR-CENIE
ACCEL
ACCEL-CENIE
Figure 13: Zero-shot transfer return ablations in Bipedal Walker domain. The plot is based on mean and standard error over 5 independent runs.
IQM
Optimality Gap
PLR PLR-CENIE PLR-CENIE
ACCEL
ACCEL-CENIE ACCEL-CENIE
0.15
0.30 0.45
0.60 0.45
0.60
0.75
Min-Max Normalized Score
Figure 14: IQM and Optimality Gap ablations in Bipedal Walker domain. Results are measured across
5 independent
In addition to the state-action space coverage, we also conduct the ablation study in the Bipedal domain. We repeat the same experiment settings as the Minigrid domain, where both ACCEL- CENIE and PLR-CENIE' utilize only novelty prioritize replay levels, and ACCEL-CENIE and PLR-CENIE integrate both novelty and regret for prioritization. We assess the algorithm performance with the same evaluations as in the main paper, providing both the transfer performance during training (Figure 13) and IQM and Optimality Gap (Figure 14)
Summarizing the observations from both Figure 13 and Figure 14] we observe that novelty-driven level replay selection exhibits a similar effect as regret on PLR but is not as effective as regret ACCEL. PLR-CENIE" performs par with the regret metric counterpart (i.e., PLR-) while ACCEL-CENIEI is outperformed by ACCEL and ACCHI-CENIE in this domain. The observations differ from the ablation studies conducted in the Minigrid domain. This discrepancy is possibly due to the greater importance of exploration in Minigrid, which features sparse reward setting, compared the dense reward, continuous control domain of BipedalWalke
A.3 CarRacing Domain
To monitor the evolution of the students' transfer performance, we evaluate the students every 100 PPO updates on four racing tracks throughout the training period and plot the results in Figure 15 PLR-CENIE outperforms both its predecessor, PIR- and the state-of-the-aa algorithm, DIPLR, in the CarRacing domain.
18

---

Since both DIPLR and PLR- CENIE achieve near-optimal performance on the four testing tracks, we conduct more extensive and rigorous evaluation by measuring the students' transfer performance on 20 human-designed F1 racing tracks from Jiang et al. [27] We also include the ablation model, PIR-CHNNIE which uses novelty alone to prioritize replay levels, in our evaluation. The detailed results of each algorithm are listed in Table For better visualization and straightforward comparison, we plotted the IQM and Optimality Gap performances in Figure
Table 3: Test returns of each method on all the CarRacing F1 benchmarks. Results are measured across 5 runs at 2.75k PPO updates and 50 trials per track. Bold indicates being within standard error of the best mean. Observe that PLR-CENIE consistently outperforms the other algorithms or matches the best-performing algorithm. PLR-CENIE! is the ablation model.
PLR- CENIE
PLR-
Track
DR
Minimax
PAIRED
DIPLR
PLR 1
CENIET
Australia
3041113
107:t97
224
7151:50
574169
745-32
616+:5
Austria
299::118
152+:106
159+160
587#49
458+44
566-38
496::46
Bahrain
208::136
1411001
118+159
5141:48
377
537
4534:38
Belgium
225+:104
1314-87
110+100
440-131
3624:36
500-41 41
436:::35
Brazil
192+:106
57-61
147+122
451-:39
368
485 27
312:+40
China
-35+-57
-294-80
-71+63
93--102
-23+-28
278 100
281 4-1--52
France
1241:11
48=129
81126
487=75
311198
564
435197
Germany
172+:105
94=100
2497
477:599
358
512-80
800
Hungary
3194155
1334113
139+161
6861150
597172
678 478-40
604
Italy
267+114
204489
198+135
676+33
559+633
708-26
588
Malaysia
142+:107
39-94
51=104
4041:30
265+
469
338#22
Mexico
331+199
193+123
102+1169
675+24
570=76
674=51
602=57
Monaco
80478
100499
341:111
369
1394112
641 46
476199
Netherlands
143+:109
104495
42:777
540133
400+-61
558 59
403 84
Portugal
174+-118
39-94
88+-133
412--22
353+-27
495 66
394+43
Russia
343+155
118+105
204+1133
609+-60
644+31
550+60
Singapore
209:100
75-93
88+153
479178
4231:1
530-48
454
Spain
296:1133
1811110
249+157
6191399
517141
583
499139
UK
303-+127
187+101
194+156
558:149
443::45
562-22
506
USA
173:99
-2484
2+161
191+110
155++90
416=143
363
Mean
2141115
99-122
105+1122
4991:20
392::28
553
465
we observe that the ablation model, PLR-CENT CAR-CEEIEE. outperforms PLR by significant margin, indicating that novelty is more important for level replay prioritization than the regret metric in PLR for the CarRacing domain. Moreover, PLR-CENIE surpasses DIPLR and achieves state-of-the-art transfer performance in the CarRacing domain by effectively combining the strength of both novelty and regret.
From both Table and Figure 16
B Extended Related Work
Curiosity-driven Approaches in RL CENIE and curiosity-driven RL 47 50 share a conceptual similarity in leveraging novelty unfamiliarity guide learning. However, they differ significantly in their application and theoretical foundations. Curiosity-driven learning seeks to quantify "curiosity" an intrinsic reward for the agent such that it learns prioritize the exploration of interesting experiences within a static environment (38), or across a set of predefined tasks [18]. In contrast, CENIE autocurricula approach that focuses curating environments interesting or useful for the agent's learning, shaping the learning curriculum itself rather than the exploration reward signal. This distinction is analogous to the difference between Prioritized Experience Replay [46] in traditional RL and Prioritized Level Replay (28) in UED. The former is an "inner-loop" method prioritizing past experiences for training, while latter an "outer-loop" method using past experiences inform the collection/generati experiences for policy updates, whereas CENIE focuses on generating and curating levels that induce these novel experiences. This fundamental difference in purposes makes theoretical and empirical
of future experiences. Similarly, curiosity-driven learning prioritizes novel
19

---

Vanilia
F1. F1-italy
Fi-iingapoee
FL.mmaynyy
542-
400
Test Roburn
480
300
203
362
112
182
110
-10
Student PPO Updates
Student PPO Upciates
Student PPO Updatees
Student PPO Updatees
DIPLR
PLR
PLRCCENIE
PLR-CENEE!
Figure 15: Complete training process of each algorithm on four CarRacing test environments. Plots show mean and standard error over independent runs, with evaluation interval of 100 PPO updates.
IQM
Optimality Gap
DIPLR PLR
PLR-CENIE PLR-CENIE
0.60 0.66 0.72
0.78
0.24
0.30
0.36
0.42
Min-Max Normalized Score
Figure 16: IQM and Optimality Gap ablations the full CarRacing benchmark (20 F1 tracks). Results are measured across 5 independent runs after 2.75k PPO updates.
comparisons between auriosity-drives approaches and CENIE less direct. However, many of the previous works curiosity-driven RL provide inspiration for the CENIE framework. Specifically, curiosity-driven RL methods often seek to represent the "visitation counts" of state-action to shape intrinsic reward. The use of GMMs to model state-action space coverage CENIE is motivated by successes in curiosity-driven RL approaches which have tackled the counting problem using density models. Notably, density models have been flexibly used to model state-action visitations for both large discrete state-action spaces (via pseudo-counts g (6] and continuous state-action spaces (62 61.
Automatic Curriculum Learning UED is related to Automated Curriculum Learning (ACL; (2:1442
which emcompasses a family of mechanisms that automatically adapt the distribution of training data by selecting learning situations tailored to the capabilities of DRL agents. Many ACL methods prioritize sampling of environment instances where the agent achieves high learning progress (LP). particular relevant method in this space is ALP-GMM, introduced by Portelas et al. [40]. ALP- GMM operates by periodically fitting a Gaussian Mixture Model to a dataset of previously sampled environment parameters, each associated with an Absolute Learning Progress (ALP) score. The approach employs an EXP4 (6) bandit algorithm to select Gaussians as arms, with each Gaussian's utility defined by its ALP score. ALP-GMM's approach fitting multiple GMMs using different number of Gaussian components and keeping the best one inspired our GMM approach. However, they evaluate the GMM's quality using the Akaike's Information Criterion [T] (AIC). AIC introduces penalty for the number of parameters in the model (which increases with the number of Gaussian components and dimensions of the data). This penalizes GMMs with more components, which may not be ideal for accurately modeling well-separated clusters in the state-action space which is crucial for identifying sparse regions and estimating novelty. To address this, our work uses the silhouette score 45 instead, which better evaluates clustering quality by considering both intra-cluster cohesion and inter-cluster separation, making better suited for modeling novelty in state-action spaces. Additionally, ALP-GMM uses GMMs to sample environment parameters that are likely to yield high
20

---

ALP scores, aligning task difficulty with the agent's progress. This approach contrasts with how GMMs are used in the CENIE framework, where the goal is to model the novelty of an environment based on state-action coverage, independent of specific environment parameters. ACL methods like ALP--GMM generally assume predefined target task distribution. This differs from the UED framework which only requires only an underspecified task space, i.e. f in the UPOMDP formalism. UED seeks to directly maximize the student's robustness over any possible environments, even those that are cul-of-distribution from training. Similarly, CENIE provides a general approach for quantifying novelty using state-action coverage, without relying on any predefined task distribution. Due to this generality, we believe the CENIE framework holds significant potential for crossover applications in the ACL domain, providing a robust method for assessing and prioritizing environment novelty to enhance curriculum learning.
Open-endedness and Novelty Search in Evolutionary Computation Long-running UED pro- cesses in expansive UPDOMPs closely resemble contimual learning in open-ended domains. As such, UED is fundamentally connected to the fields of open-endedness [51] and evolutionary computation. When the task space allows for unbounded complexity, autocurricula methods such as UED offer promising pathways to open-endedness by co-evolving an adaptive, infinite set of tasks for the agent. Traditionally, learning without extrinsic rewards or fitness functions has been studied in evolutionary computation where it is referred to as 'novelty search' 31). In novelty search, the novelty of an agent's 's behavior is typically quantified by measuring the distance between a user-defined feature or behavioral descriptor and its nearest neighbor in the population. Consistent with our findings, the open-ended learning literature has long recognized that -eithhhnrfrming solutions often emerge not through fitness optimization alone but through novelty-driven exploration. Despite these parallels. novelty search in environment design remains underdeveloped. Early work such as POET [56) and its successor [57] in open-ended RL have started drawing connections, linking environment design with principles of open-ended exploration. However, these approaches rely on a population of agents and distance-based novelty measures that lack curriculum-awarenn aawaeeeesss they do not adapt to the specific experiences induced by the curriculum nor improve the agent's is sample efficiency in reducing uncertainty across the state-action space. More recent work by Zhang et al. [60] proposed to leverage foundation models to quantiffy human notions of "iinterestingnes"" (c.g. tasks that are both novel and worthwhile) in order to narrow the environment search space. It unclear how to combine the insights from Zhang et al. [60] and this paper. Integrating these insights with our work presents intriguing challenge. On one hand, CENIE provides a principled, general approach to quantifying novelty through state-action coverage, circumventing the need for subjective evaluations of "interestingness" using foundation models. On the other hand, Zhang et al. [60] points out critical pitfalls in novelty search, such as the potential for agents to exploit novelty measures, generating superficial variations that fail to yield genuinely meaningful insights. This highlights numerous exciting research directions for aligning novelty search with the concept of "interestingness," potentially combining the strengths of principled coverage-based novelty measures with more nuanced assessments of task value.
C Future Work and Limitations
In this paper, we demonstrated the application of GMMs to quantify the novelty of environments generated under the UED paradigm. We then validated the effectiveness of this novelty metric in prioritizing levels. Nevertheless, our work has some limitations. First, while we demonstrated the utility of the CENIE framework for novelty quantification and level prioritization, we did not explore its potential for directly generating novel environments. We anticipate that with creative manipulations, the GMM likelihood scores could directly inform level generation, either through a principled level generator (as in PAIRED) or by guiding mutations (as in ACCEL). This approach may lead to a more sample-efficient generation process, reducing the variance inherent in random generation.
Second, we did not experiment with alternative weightings between regret and CENIE's novelty in level replay prioritization, as our experiments used a fixed 0.5-0.5 weighting (as in Eq We hypothesize that tuning these weights based on domain characteristics, such as the required level of exploration or reward sparsity, could improve performance. Additionally, employing dynamic weighting schemes, such as linearly decaying weight adjustments or adaptive strategies based on the agent's 's learning progress, may further enhance curriculum optimization.
21

---

Third, GMM-based clustering may encounter challenges due to the curse of dimensionality in high- dimensional state-action spaces, While our current -uggme-e algorithms demonstrated significant improvements, future work could explore dimensionality reduction techniques, such as Principal Component Analysis (PCA; (25)) or t-distributed Stochastic Neighbor Embedding (1-SNE; (54). D to improve coverage representation in higher-dimensional settings. However, even with dimensionality reduction, such representations may still struggle in environments where the observations contain exogenous information irrelevant to the agent's s control. Specifically, although our experiments showed strong empirical gains in simplified environments, the current approach is vulnerable to the noisy TV problem [9), where novelty-driven level prioritization may focus unpredictable noise elements of the environment, rather than beneficial learning experiences. This limitation highlights the importance of balancing level prioritization between novelty and regret to ensure the agent focuses on genuinely novel environments rich in learning potential.
Furthermore, effective state representation is crucial for the CENIE framework. The CENIE frame- work is not restricted to raw state inputs; it can operate on indirect encodings, such as latent-space representations obtained from a generative model of the environment. This approach would allow CENIE to capture action-relevant information and necessary temporal dependencies between states, providing more focused basis for novelty estimation. We expect that density-based novelty estima- tion could improve further by using latent representations from more expressive generative models, such Variational Autoencoders (VAEs) [29], which can capture richer, more informative structures in the state space.
Finally, while we used GMMs for environment novelty quantification, the CENIE framework is not limited to this model, as mentioned the main body of this paper. GMMs may face limitations in capturing more complex distributions in real-world settings, and our choice of GMMs was primarily intended to illustrate the empirical benefits of quantifying novelty using state-action coverage in simpler environment settings. It is important to point out that fitting multiple GMM on the updated state-action coverage distribution and selecting the best one every rollout can incur additional computational costs. For future work aiming to replicate our approach, exploring periodic refitting (similar to the strategy used in ALP-GMM) could be worthwhile, as it may achieve comparable effectiveness while significantly reducing computational demands. Future work could also investigate more ad advanced density models, such as Variational Gaussian Mixture Models [T]] Deep Gaussian Mixture Models (55), Normalizing Flow Models 444. Additionally, there may be alternative approaches beyond density models for representing state-action coverage that could further enhance CENIE's effectiveness. We believe there are many promising directions for the CENIE framework, and we leave these potential extensions to future work.
D Implementation Details
In this section, we provide the details about the experiments and implementations, including do- main properties and additional information about CENIE and the baseline algorithms. All of our experiments are run with a single V100 GPU or GeForce 3090 GPU, using 10 Intel Xeon E5-2698 v4 CPUs. The baseline algorithms and evaluation environments are implemented using the DCD codebase provided by Jiang et al. (27), Parker-Holder et al. (37] The CENIE framework and our current evaluations build upon and significantly extend a preliminary version of our work (52), where the framework was initially named "GENIE." We have since enhanced the framework and opted to rename it to CENIE, following the release of a similarly-namedt related work by Bruce al. [17). which appeared around the same time. This change was made to distinguish our contributions clearly and avoid confusion within the research community.
D.1 Fitting Gaussian Mixture Models
In this section, we provide more details about the GMM fitting process that was absent from the main body. Given an initial buffer containing past state-action pairs, r, and a selected number of Gaussians, K, we first use the k-means++ algorithm to perform a fast and efficient initialization of the GMM parameters 12 Ar = {(an, μ4, Σi),... ..., (OxR ,k,, )x)). We then optimize År using the Expectation Maximization (EM) algorithm [2 43 The EM algorithm uses the initial values
Ar to estimate a new X. such that P(X[X,) > P(X))r). This process is repeated iteratively until
some convergence threshold is fulfilled. Each iteration of the EM algorithm can be separated into the
22

---

E-step and M-step. In E-step, the posterior probability for each component generating the sample point 2, denoted by wh.s
Wt P(i]xt) Σi (xN(zel)
where f = 1, ...,,N .N and i = 1,,, K. M-step computes the maximum likelihood estimation (MLE) using W4,, following re-estimation formulas which are derived from the partial derivatives of the log-likelihood functions and guarantee monotonic increase in the model's likelihood value.
N
Σ 1= Wi,i
Wii
Hi
N
E
==1
Weii
0
=
Wesi
(It
1s) - p4)²
i=
Wt,
We iteratively apply the Etstep and M-step until the parameters converge, i.e., 11 Arll < 6, where 6 a small threshold.
As mentioned in the main paper, we deliberately employ a finite window for I' to account for the effects of catastrophic forgetting. This allows levels with state-action pairs encountered in the past but subsequently forgotten by the agent's policy to regain novelty and be included back in the agent's s training curriculum. Furthermore, ensure effectiveness in clustering the Stateacttion space, we utilized semi-online GMM model that is able to adapt its number of Gaussians, i.c. K, to that of the highest silhouette score.
We use the PyCave 13 Python library to fit the GMM using GPU acceleration, which also provides (EM) algorithm. We use the PyTorch Adapt [35] Python library to calculate the silhouette scores. The hyperparameters for fitting the GMM for all domains are shown in Table
an efficient abstraction for the Sospetation-Maximizaae
D.2 CENIE-Augmented Algorithms
Besides the algorithm for ACCEL-CENIE shown the main paper under Algorithm T we also provide the algorithm for PLR-CER PLR-CENIE here under Algorithm 2
D.3 Minigrid Domain
In the Minigrid domain, the teacher creates maze instances consisting of 15 15 grid, where each empty tile can be occupied by the agent, the goal, an obstacle (i.e. block), or empty space that can
navigate through. The student aware of its orientation and is limited by partial observability, i.e. only has 5 x 5 view in front of it. The student agent can only move forward and turn lefv/right, and will stay in place if hits an obstacle. The student agent is implemented based on PPO 49 with an Lased recurrent network structure to deal with partial observability. We use the LSTM hidden states as representations within our GMM, allowing the density model to capture temporal dependencies between states. The student agent receives reward upon reaching the goal, where H the episode length and Hman is the maximum length (set to 250 at training) for an episode, The agent receives reward of 1 (numsatep/ Hmar) when it reaches the goal position and 0 if it fails to reach the goal. The collection of states in this domain depicts the scenarios the agent needs to navigate through.
D.4 Bipedal Domain
In BipedalWalker, the teacher agent generates new levels by specifying the values of the eight environment parameters (e.g., ground roughness, number of stair steps, pit gap width, etc). As for the student agent, needs determine the torques applied on its joints and is constrained by partial observability where it only knows its horizontal speed, vertical speed, angular speed, positions of joints, etc. The student agent receives positive rewards as it walks towards the goal position and will receive large negative penalty if it falls down. The BipedalWalker domain is modified on top of the BipedalWalke Hardorr environment from OpenAl Gym, introduced by [56] and improved by
41 37]. The student agent receives 24-dimensional proprioceptive state corresponding inputs
23

---

Algorithm 2 PLR-CENIE
Input: Level buffer size N, Component range [Kinn Kmax, FIFO window size W, random level
generator G
Initialize: Student policy Ty level buffer B, state-action buffer I, GMM parameters Xp Generate N initial levels by to populate B
2: Collect n,y trajectories on each level in B and fill up I'
3: while not converged do
4: Sample replay decision, U10,1 1]
5: if 2 0.5 then
6:
Generate new level lo by G
7:
Collect trajectories on lg. with stop-gradiee 7 Compute novelty score for lo using Ar (Eq and Eq
8:
9:
Compute regret score for to (Eq and Eq 4
10:
Update B with lo if Preplay (lo) greater than that of any levels in B (Fq
11:
else
Sample replay level lo B according Preplay
13:
Collect trajectories on lg
Update Ty with rewards I((T)
15:
Compute novelty score for la using Ap (Eg and Eq
Compute regret score for (Eq I and Eq
17:
Update Prepla with novelty and regret scores
Update I' with and resize W for k in range Kiin to Kma do
19:
Fit a GMM; with l components on I and compute its silhouette score end for
21:
22:
Select GMM parameters with the highest silhouette score to replace År Collect trajectories on la, with stop-gradient 7).1 Update B with lg P Preplay (l4) greater than that any levels (Eq
23:
24:
25:
end if
26:
end while
from its lidar sensors, angles, and contacts, which also form the state representation for our GMM. The partial observability here means the agent does not have access to its positional coordinates. The environment parameters and their corresponding ranges be a singular value to specify Ground Roughness and the Number Stair Steps, and a min and a max value define the PitGap Width, Stump Height, and Stair Height, and thus will have eight environment parameters in total.
shown in Table Note, there will
Table 4: Environment parameters and their ranges in the Bipedal Walker domain. To define PitGap, StumpHeight, and StairHeight, we need a min and a max value. Hence, there are total of eight parameters.
Parameter
Roughness
Num of Stair Steps
PitGap Width [0.10]
Stump Height
Stair Height
Range
[0.10]
[1.9]
[0,5]
[0,5]
D.5
CarRacing Domain
The CarRacing domain was introduced and customized by (27). In CarRacing, the teacher creates tracks by using Bézier curves by control points within fixed radius the center of the playfield. A track consists of a sequence of L polygons and L is fixed on the training tracks and varies on different testing tracks. While driving on the tracks, the student receives reward equal to 1000/ L. The student additionally receives reward of -0.1 at each time step. The student observes an RBG image of size (96x96x3), where (96x96) is the (height x width) of the observed image and 3 is the number of RGB channels. Consistent with previous UED literature, we employ CNN model preprocess the raw image observations. The CNN extracts high-level features from the raw images, reducing their dimensionality and capturing important spatial patterns that are crucial for

---

Figure 17: Examples of testing levels in Biledal domain. (a) BipedalWalker, (b) Hardcore, (c) Stair, (d) PitGap, (e) Stump, and (f)uoughssss.
understanding the environment's dynamics. By feeding these feature representations into the GMM model instead of the raw image input, we ensure that the density estimation focuses on meaningful aspects of the state space rather than being overwhelmed by the complexity and noise of raw pixel data.
The 20 testing F1 tracks by 27 have various track lengths and different maximum episode steps. As such, different min-max normalization ranges are used for each track to produce the IQM and Optimality Gap plots. We list the 20 test tracks and their corresponding min-max normalization ranges in 5
Table 5: Min-max ranges for different CarRacing Fl tracks that are used for IQM and Optimality Gap plotting.
Track
Episode Steps
Min-Max Reward Range
Australia
Austria
Belgium
1500
[- 150, 850]
Italy
Monaco
Brazil
China
France
Germany
Hungary
Netherlands
2000
[-200, 800]
Russia
Singapore
Spain
UK
USA
Bahrain
Malaysia
2500 [-250, 750]
Portugal
Mexico
3000 [-300, 700]
E More Details On Baseline Algorithms
In this section, provide more technical details some of the baseline algorithms used in experiments, specifically Domain Randomization (DR), Minimax, PAIRED, PLR DIPLR, and ACCEL. We summarize the key differences between the baseline algorithms in Table
The Domain Randomization (DR) teacher uniformly randomizes each dimension the environment parameter space generate various environments.
25

---

Table 6: Overview of the fundamental UED algorithms and CENIE-augmented algorithms.
Generation
Generator
Curation
Algorithm
Setting
Strategy
Obj
Obj
POET
Mutation
Minimax
MCC
Population
PAIRED
RL
Minimax Regret
None
Single-agent
PLR
Random
None
Minimax Regret
Single-agent
Minimax Regret
DIPLR
Random
None
Single-agent
Diversity
Random
ACCEL
Minimax Regret
Minimax Regret
Single-agent
Mutation
Minimax Regret
PLR-CENIE
Random
None
Single-agent
Novelty
Random +
Minimax Regret
Minimax Regret
ACCEL-CENIE
Single-agent
Mutation
Novelty
Novelty
The PAIRED teacher estimates regret by leverage two agents: an antagonist agent and protagonist agent (student). In practice, PAIRED derives regret by taking the antagonist's (A) maximum perfor- mance and the protagonist's (P) average performance over several trajectories, allowing for more accurate approximations. Let U (r) denote the total reward obtained by a trajectory т produced by policy π on the level 0. Regret is measured in PAIRED via:
REGRET (TA, = max
B, [v+
where A and = are the antagonist's policy and the protagonist's policy, respectively. PAIRED teacher constantly creates levels that are slightly beyond the ability range of the protagonist and within the ability range of the antagonist such that the regret maximized. The pseudocode of the PAIRED algorithm is given in Algorithm 3
Algorithm 3 PAIRED
Rnnut:Randomly initialize Protagonist x.P Antagonist A and teacher
Initialize: replay buffers B
1: while not converge do
2: Use teacher to generate environment parameters: 0 ~ A. Use to create environments, lo
3: Collect Protagonist trajectory 7P in lg. Compute Protagonist's average return: [²(V(x
4: Collect Antagonist trajectory 7 in lg. Compute Antagonist's average return: E E[(((TA)
5:
Compute regret: REGRET = EE [V [V***]] E [V(xP)
6:
Train Protagonist policy xP with RL update and reward REEGRT
7: Train Antagonist policy I4 with RL update and reward = REGRET
8: Train teacher policy with RL update and reward REGRET
9: end while
However, the PAIRED algorithm faces several drawbacks 34 Both the antagonist and protagonist policies are constantly updating, making the problem nonstationary. Furthermore, PAIRED suffers from a long-horizon credit assignment problem since the teacher must fully specify an environment before receiving sparse reward in the form of feedback from the antagonist and protagonist agents. PLR seeks to circumvent this issue through the use of regret for prioritized selection of levels for replay rather than active generation. PLR uses Positive Value Loss (PVL), an approximation of regret based on Generalized Advantage Estimation (GAE; (48)::
T Σ max EGAA)--8800 02.00
PVL (T)
where 7, À and T are the MDP discount factor, GAE discount factor and MDP horizon, respectively. 5% the TD-error at time step & for 0. However, the use of PVL may introduce bias due to the bootstrapped value target. An alternate heuristic score function is Maximum Monte Carlo (MaxMC),
26

---

which replaces the bootstrapped value target with the highest return observed on the level during training, By using this maximal return, the regret estimates become independent of the agent's current policy:
T Rd max - -((T)))
MAXMC (T)
T
where R is the maximal return π on 8. We primarily focus on PVL because the original implementations of ACCEL and PLR- Jiang et al. [27], Parker-Holder et [37] found better success with the PVL scoring function for the experiments domains, i.c. Minigrid, BipedalWalker, and CarRacing, used in this paper. Future research could explore the potential of using the MaxMC scoring function to see if it yields different outcomes when combining ACCEL and PLR with CENIE. The Diversity Induced Prioritized Level Replay (DIPLR (33 algorithm extends PLR by prioritizing level replay based Wasserstein distance between the agent's s trajectories across levels in the replay buffer. The limitations of DIPLR are highlighted in the main body (see Section 3 The pseudocode of DIPLR is provided in Algorithm
both regret and diversity. Here, diversity is quantified using the
Algorithm DIPLR
Input: Level buffer size N, level generator G Initialize: student policy Typ level buffer trajectory buffer I
1: Generate N initial levels by to populate L
2: Collect trajectories each replay level in L and fill up r
3: while not converged do
4: Sample replay-decision
U(0, 1]
5: if 2 0.5 then
6: Generate
level lo, by g Collect trajectories T; on To,, with stop-gradient 7)
7:
8:
Compute the regret, staleness and distance for le.
9:
else
Sample replay level la, according to Preplay Collect trajectories Ty on lø, and update nh with rewards R(T,) Compute the regret, staleness and distance for l5
11:
12:
13:
end if
14:
Flush I and collect trajectories on all replay levels to fill up r
15:
Update regret, staleness, and distance for la, or to
16:
Update with new level lo, its replay probability is greater than any levels in
Update replay probability P Preplay
18:
end while
Finally, the state-of-the-art UED algorithm, ACCEL, improves PLR- by replacing its random level generation with an editor that mutates previously curated levels to gradually introduce complexity into the curriculum, ACCEL makes the key assumption that regret varies smoothly with the environment parameters 0, such that the regret of a level is close to the regret of others within a small edit distance. If this is the case, then small edits to a single high-regret level should lead the discovery of entire batches of high-regret levels which could be an otherwise challenging task in high-dimensional design spaces. An intriguing area for future exploration is the interaction between ACCEL's editing mechanism and the covelty-driven level prioritization introduced through CENIE. Specifically, it is worth investigating whether the editing mechanism does synergize with CENIE to produce levels that simultaneously maximize both novelty and regret, further enhancing the diversity and effectiveness of the generated curriculum.
F Hyperparameters
In this section, we provide the hyperparameters we used for both CENIE-angmented and baseline algorithms in our experiments. We employ the same set of CENIE parameters for both ACCEL- CENIE and PLR-CENIE We provide all the parameters for our implementations in Table 7
27

---

Table 7: Hyperparamelers used for training PLR-CENIE and ACCEL-CENIE in Minigrid, Bipedal-
Walker and CarRacing domains. Note that the inherit the original PLR and ACCEL hyperpa- rameters and only adjust the CENIE hyperparameters.
Parameter
Minigrid
Bipedal
CarRacing
PPO
0.995
0.99
0,99
AGAE
0.95
0.9
0.9
PPO rollout length
256
2048
125
PPO epochs
5
5
PPO minibatches per epoch
32
PPO clip range
0.2
0.2
0.2
PPO number of workers
32
16
Adam learning rate
le-4
3e-4
3e-4
Adam 6 PPO max gradient norm
le-5
le-5
1e-5
0.5
0.5
0.5
PPO value clipping
yes
no
no
return normalization
no
yes
yes
value loss coefficient
0.5
0.5
0.5
student entropy coefficient
0.0
1e-3
0.0
PLR
Scoring function
positive value loss
positive value loss
positive value loss
Replay rate,
0.5
0.5
0.5
Buffer size, K
4000
1000
8000
ACCEL
Edit rate,
1.0
1.0
N/A
Replay rate, p Buffer size, K Scoring function Edit method Number of edits Levels edited Prioritization, B
0.8
0.9
N/A
4000
1000
N/A
positive value loss random
positive value loss
N/A
random
N/A
3
N/A
batch
batch
N/A
0.3
0.1
N/A
Staleness coefficient, p
0.5
0.5
N/A
CENIE
Initialization strategy
k- +
k-means++
k-means++
Convergence threshold,
0.001
0.001
0.001
GMM components
[6,15]
[6,15]
[6,15]
Covariance regularization
le-2
le-6
le-1
Window size (no. of levels)
32
32
32
Novelty coefficient
0.5
0.5
0.5
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
We've described our claims and contributions clearly in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
Justification: We included the limitations and future directions of our paper under Section C of the appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiaatinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [NA]
Justification: In this paper, we prove our claims with extensive empirical results, instead of theoretical proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes].
Justification: We provided all information, i.c. hyperparameters, libraries, and algorithms, required to reproduce results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
30

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No].
Justification: At the time of submitting the camera-ready version of this paper, our code- base is not yet prepared for open-sourcing. However, we have provided comprehensive implementation details to ensure replicability.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
mublicc/gudees/CodSSubiiiss sow.essubbbmiiioooooooooo.. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/mipss.cc/pullc/giidde
wwwsssssiipyyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes].
Justification: We provided full implementations and Syper-parameee in the code submission and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the information about the statistical significance of the experiments?
paper report error bars suitably and correctly defined or other appropriate
Answer: [Yes].
Justification: Our results are obtained across multiple independent runs, and we plotted the results with variabce.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes].
Justification:
We provided the hardware details (GPUs and CPUs) in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /atn::/nneusisse http://pppp../........////////aa
Answer: [Yes]..
Justification:
We've read the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]-
Justification: The main application of our paper is to train generally capable RL agents. Societal impacts are limited and thus we omitted this discussion in paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
32

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: Our paper does not have such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]..
Justification: We' ve credited and cited the references and codebases properly in the paper. The resources are all open-sourced.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
33

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification:
We don't 't release any new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA].
Justification:
Our research does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA].
Justification: Our paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
34

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "cw79iow2AO", "reviewer": "Reviewer_qR9x", "summary": "This paper proposes adding a domain-general metric for promoting novelty to state of the art UED methods in order to help the environment generator better explore and cover the space of environments.  The novelty bonus is based on a surprise of a (state, action) pair model which is a learned Gaussian mixture model.", "questions": "What sort of qualitative difference do you see between ACCEL-GENIE and ACCEL levels?", "limitations": "See weaknesses.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method is clearly useful and easy to implement, fixing a limitation of existing UED approaches which are known to miss modes in the space of levels.  Empirically the method seems to perform strongly, matching or exceeding existing methods. This is a valuable direction to pursue as it is important for the UED community to have a sense for how novelty effects performance, and the approach addresses a well-known flaw in existing UED approaches.", "weaknesses": "The method would be more convincing if the generated levels for each method where visualised and compared directly.  Ideally one could demonstrate that there are a motif of level being generated which were not being generated before.  For instance, displaying the distribution over stump hight late in training of ACCEL and ACCEL-GENIE to show that ACCEL-GENIE has a more even coverage of the space, and sampling a few levels randomly from each so that this can be visually confirmed.  \n\nSimilarly, the paper would be much improved if the mechanism behind the results was dug into in more depth. If the theory is that the diversity term results in kinds of high-regret levels being presented which were left out of the buffer previously, it would be ideal to demonstrate that this happens directly.\n\nOn line 258 results are over-claimed, since ACCEL-GENIE is within the margin for error of ACCEL in all, or nearly all, of the environments. This claim should be corrected. I don't think this is essential for acceptance of the paper, as the minigrid benchmark appears pretty close to being saturated, and it serves largely as an MNIST for the field. The empirical results in the other two environments stand on their own.\n\n#### Clarity:\nIt would be good to have error bars in Table 1\nThe plots in Figure 7 should be fixed so the colors of the same method match\nThere is a stray parenthesis on line 303\nEquation 1 shows the PAIRED objective \"optimized\" for deterministic domains, the PAIRED objective as a direct comparison between the two expected returns is canonical. \n\nI would also suggest reconsidering the name, as another prominent environment-generating model named GENIE has been released recently. I expect that, in talking about this work, people will want to talk about how the two could be combined, which could get quite confusing.\n\nIn the abstract I think it is not clear that novelty, on it's own, is critical for agent's generalisation ability. Two situations which are different but not in a way that is relevant for the task and are processed by the network in the same way are effectively the same, and would not effect generalisation ability.\n\nIt also appears that in a few places the \"underspecified\" in UPOMDP is taken to mean that there is a one-to-many mapping between parameters and environments. In general this is not the case, as the minigrid environment has a one-to-one mapping between parameters and environments, the \"underspecified\" simply means that these parameters are not given by the designer. It is fair to want UED algorithms to work even when there is such a one-to-many mapping, but it is not required as part of the problem formulation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's insightful comments and recognition of the valuable direction of novelty-driven autocurriculum that GENIE is pushing for the UED field. Also, it is always refreshing to engage with a reviewer who has in-depth knowledge of UED. The new results within the global rebuttal and our following clarifications would be of interest to you and strengthen the case for our paper:\n\n### Weaknesses\n**Q: The method would be more convincing if the generated levels were visualized and directly compared. Ideally, demonstrate that new motifs are being generated. For example, display the distribution over stump height late in training of ACCEL and ACCEL-GENIE to show more even coverage by ACCEL-GENIE, and randomly sample a few levels from each for visual confirmation.**\n\nA: Answered in global rebuttal, refer to the section \"GENIE Introduces Level Complexity\" explanation.\n\n**Q: The paper would be improved by exploring the mechanism behind the results in more depth. If the theory is that the diversity term introduces high-regret levels previously excluded from the buffer, it should be demonstrated directly.**\n\nA: This is something we have thought about while working on GENIE. The main struggle with trying to demonstrate this is that both the regret and novelty metric are inherently policy-dependent. As such, it is impossible to directly measure whether prioritising or not prioritising a level via GENIE would lead to discovering a higher regret level down the road because the divergence in realities would result in different policies with non-commensurable subjective regrets. However, one way we can indirectly measure this is by observing whether a greedy selection of high regret levels (as in ACCEL and PLR) or a balanced regret-novelty prioritization (as in ACCEL-GENIE and PLR-GENIE) results in better cumulative/mean regret in the replay buffer across the training horizon. The section \"Prioritizing Novelty Actually Increases Regret\" in our global rebuttal demonstrates that GENIE actually results in higher regret across the replay buffer in the Car-Racing domain despite not directly optimising for it.\n\n\n**Q: On line 258, results are overstated, as ACCEL-GENIE's performance is within ACCEL's margin of error in nearly all environments. This claim should be corrected. This isn't essential for paper acceptance, as the minigrid benchmark is nearly saturated and serves as an MNIST for the field. The empirical results in the other two environments are sufficient.**\n\nA: We have amended line 258 to exclude the remark on ACCEL-GENIE's outperformance over its predecessor but the point on PLR-GENIE's clear improvement over PLR still holds.\n\n**Q: Add error bars to Table 1. Ensure matching colors for the same method in Figure 7. Fix the stray parenthesis on line 303. Equation 1 should reflect the canonical PAIRED objective, comparing the two expected returns directly, rather than being \"optimized\" for deterministic domains.**\n\nA: Thank you for the attentiveness to detail, we have addressed this in our revised manuscript.\n\n**Q: Consider renaming the model since another prominent environment-generating model named GENIE has been released recently. This will avoid confusion when discussing how the two could be combined.**\n\nA: Addressed in global rebuttal.\n\n**Q: In the abstract I think it is not clear that novelty, on its own, is critical for agent's generalisation ability. Two situations that are different but not in a way that is relevant for the task and are processed by the network in the same way are effectively the same, and would not affect generalisation ability.**\n\nA: We are actively refining our abstract to more effectively advocate for the benefits of novelty-driven autocurricula methods, while being mindful of the brevity throughout this rebuttal process. Regarding the notion that \"different situations processed similarly by the network do not affect generalization ability,\" we believe this holds true primarily for fixed curriculum methods but not necessarily for autocurricula methods. We hope to have a constructive discussion about this. \n\nAlthough the two situations present differently but provide similar learning experiences (with relation to the task) at the current moment, they both independently inform the collection/generation of future environments. The fact that these environments behave differently (in state-action distribution) indicates the potential that they can lead to totally different and novel environments down the training horizon, especially with mutation-based methods. Therefore, even if these scenarios yield similar learning signals initially, prioritizing them for the unique state-action distributions they cover via GENIE remains beneficial for generalisation. This is an exciting discussion which can be correspondingly highlighted in our revised manuscript.\n\n**Q: It also appears that in a few places the \"underspecified\" in UPOMDP is taken to mean that there is a one-to-many mapping between parameters and environments. In general this is not the case, as the minigrid environment has a one-to-one mapping between parameters and environments, the \"underspecified\" simply means that these parameters are not given by the designer. It is fair to want UED algorithms to work even when there is such a one-to-many mapping, but it is not required as part of the problem formulation.**\n\nA: We acknowledge that the one-to-many mapping between free parameters and environments, while common, is not a mandated characteristic of UED. We have amended the manuscript to reflect that nuance more clearly (e.g., \"entails there is a one-to-many mapping\" is revised to \"possibly entails a one-to-many mapping\"). \n\n\n### Questions\n**Q: What sort of qualitative difference do you see between ACCEL-GENIE and ACCEL levels?**\n\nA: Answered in global rebuttal, refer to the section \"GENIE Introduces Level Complexity\".", "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": "", "extra_scores": {}}, {"review_id": "Ics4B8G8VB", "reviewer": "Reviewer_KtoT", "summary": "This paper proposes using novelty quantification in an unsupervised environment design for training a more generalizable policy. Built on an intuition that environments with unfamiliar states are novel environments, their proposed algorithm uses Gaussian mixture models to allow an RL agent to explore novel environments. The authors of this paper compare their proposed method in various benchmarks against multiple baselines to show empirical improvement in performance.", "questions": "The questions I hope to be addressed by the authors are the ones listed above. 1) Explanations on how this paper fits in with curiosity-based approaches and the GENIE's contributions, 2) explanations and comparisons with Genetic Curriculum, and 3) Will the agents trained by GENIE reach a steady-state equilibrium?", "limitations": "The authors has addressed the limitations of this paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This is a well-written paper with a structure that is easy to follow. The key concepts are simple and easy to understand.", "weaknesses": "- The idea of using unfamiliar states to quantify uncertainty seems similar in concept to the curiosity-driven approaches in RL. However, this paper does not address the relevant literature. It would be much better if the authors could explain how their idea fits in with the findings and theory in curiosity-based RL approaches and what the paper contributes to this avenue of thinking.\n\n- When it comes to UED in curriculum learning to train a more generalizable policy, there is Genetic Curriculum (Song et al, 2022) which also uses UED in curriculum learning to train a generalizable policy. Since the paper was also evaluated on the BipedalWalker and BipedalWalkerHardcore environments, it would be better to compare and contrast how GENIE with Genetic Curriculum.\n\n- GENIE uses a fixed window FIFO buffer, but would this be able to reach an equilibrium? For example, if the agent explores level set A at the expanse of forgetting level set B, and goes back to exploring level set B at the expanse of forgetting C, and so on, would agents trained by GENIE converge to a steady-state behavior?\n\n- Finally, there are some minor typos and editorial mistakes. For example, line 63, PLR, and ACCEL are mentioned without explaining what those are.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's time and valuable feedback. We believe the concerns raised generally pertain to broader problems in RL and are not inherent problems of GENIE. The following clarifications will explain our stance and strengthen the case for our paper. We kindly request the reviewer to reconsider the score, given that the issues raised do not detract from the contributions of GENIE and the promising direction of novelty-driven autocurricula:\n\n### Questions\n\n**Q: Using unfamiliar states to measure uncertainty is conceptually similar to curiosity-driven approaches in RL. However, the paper doesn't review the relevant literature. It would be helpful if the authors explained how their idea aligns with curiosity-based RL theories and what their paper adds to this field.**\n\nA: We appreciate the reviewer's astute observation regarding the conceptual similarity between our approach and curiosity-driven RL. While we acknowledge that our original manuscript should have addressed this relationship more explicitly, we're grateful for the opportunity to clarify these connections and distinctions. Indeed, both curiosity-driven RL and our UED approach leverage the concept of novelty or unfamiliarity to guide learning. However, they differ significantly in their application and theoretical foundations. Curiosity-driven learning literature is build on prioritising interesting experiences in a **static environment** [1], or across a set of **predefined tasks** [2]. Meanwhile, UED is focussed on **generating environments** that are interesting/useful for learning. UED shapes the learning curriculum itself rather than the exploration strategy within environments. This is analagous to the difference between Prioritized Experience Replay [3] from traditional RL and Prioritized Level Replay [4] from UED. The former is an \"inner-loop\" method to prioritize past experiences for training and the latter is an \"outer-loop\" method that uses past experiences to inform the collection/generation of future experiences. In the same vein, curiosity-driven learning is focussed on prioritizing novel experiences for policy updates but GENIE is focussed on generating/curating levels that can induce these novel experiences. This fundamental difference in purposes means that theoretical and empirical comparison between curiosity-driven approaches and GENIE is not as direct. As such, we focussed our attention mostly towards current novelty measures in UED literature, which we are of more relevance. Still, we thank the reviewer for making this observation as the general audience would also appreciate clarity on this matter. We have included a short section clarifying the distinctions between curiosity-driven learning and GENIE in the appendix of the revised paper. \n\n[1] Pathak, D., Agrawal, P., Efros, A. A., & Darrell, T. (2017). Curiosity-driven exploration by self-supervised prediction.\n\n[2] Burda, Y., Edwards, H., Pathak, D., Storkey, A., Darrell, T., & Efros, A. A. (2018). Large-Scale Study of Curiosity-Driven Learning.\n\n[3] Schaul, T., Quan, J., Antonoglou, I., & Silver, D. (2016). Prioritized experience replay.\n\n[4] Jiang, M., Grefenstette, E., & Rocktäschel, T. (2021). Prioritized level replay.\n\n\n**Q: In UED for curriculum learning to train generalizable policies, Genetic Curriculum (Song et al., 2022) also employs UED. Since both papers were evaluated on BipedalWalker and BipedalWalkerHardcore, it would be useful to compare GENIE with Genetic Curriculum.**\n\nA: Thanks for pointing to the work by Song et al. (2022). The other UED papers had not referenced this work or compared against this work. This is likely due to the fact that their problem definition in their paper differs from the *Underspecified Partially Observable Markov Decision Process* (UPOMDP) setting in UED and there is not many parallels other than sharing a commonly-used domain. Also, the original POET [5] paper which they compare against used a 5D-BipedalWalker domain (we used 8D), and it is not clear in their paper which domain they use. To the best of our knowledge and thorough search, their code repository is not publicly accessible and we are unable to replicate their work to compare the results.\n\n[5] Wang, R., Lehman, J., Clune, J., \\& Stanley, K.O. (2019). Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions.\n\n**Q: GENIE uses a fixed window FIFO buffer. Will this achieve equilibrium? For instance, if the agent cycles through level sets A, B, and C, potentially forgetting each set as it explores others, will agents trained by GENIE converge to steady-state behavior?**\n\nA:  Your description of a potential \"mode collapse\" behavior is reasonable. However, this seems to be pointing at the general negative effects of catastrophic forgetting within the broader RL literature and function approximation methods. While GENIE does not explicitly guarantee convergence to a steady-state behavior with respect to novelty, it's important to note that this challenge is not unique to our approach. The leading approaches, PLR and ACCEL are also unable to provide robustness guarantees against such oscillatory exploration patterns. It would be interesting to start having conversations on how we can bridge insights from \"continual learning\" and \"stability-plasticity dilemma\" literature with UED, and see how minimax-regret and GENIE's novelty could possibly circumvent the negative effects of catastrophic forgetting.\n\n**Q: Finally, there are some minor typos and editorial mistakes. For example, line 63, PLR, and ACCEL are mentioned without explaining what those are.**\n\nA: Thank you for pointing this out, we have fixed this in the revised manuscript.", "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": "", "extra_scores": {}}, {"review_id": "BrciC5IWlJ", "reviewer": "Reviewer_kpCs", "summary": "This paper focus on the unsupervised environment design (UED) problem, whereby a student trains in an adaptive curriculum of environments proposed by a teacher. The authors propose GENIE, a method for assessing novelty of environments, which essentially means the teacher prioritizes environments with high exploration potential/info gain for the student. Experiments are conducted in three different relevant domains and the results are clear and show a reasonable gain. I thus favor acceptance. \n\nOne thing to note is the general idea of choosing environments based on novelty (rather than regret) is itself a new idea, thus, the authors do not need to focus as much on the use of GMMs, which may be limiting.", "questions": "What other approaches could be used to assess novelty at larger scale? Can you show any examples of levels that have high novelty but low regret, and turn out to be useful training levels for the agent?", "limitations": "Discussed in the Appendix.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The method makes sense as it is essentially an intrinsic reward for the policy, i.e. selecting environments where the agent will have higher information gain.\n* The empirical results are strong, with the method improving both PLR and ACCEL in three different domains.\n* The use of the evaluation protocol from Agarwal et al is always refreshing.\n* Ablations are sensible and easy to follow.", "weaknesses": "* There is a strong assumption that all transitions are independent, which is not always true. What if there is an environment where an agent needs to conduct some initial behavior (e.g. finding a key) and then using it to act later (e.g. opening a door)? It just feels like the method is designed based on the toy environments we use in RL research, and is not actually scalable for larger more complex domains in the future.\n* Hate to be that person, but the name GENIE is taken by multiple works already and recently by Bruce et al (2024) in a highly relevant paper. It would be recommended to find a more relevant acronym or simpler name.\n* The arrows in figure 2 are too small.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's feedback and the recognition of the key strengths of our method. The following clarifications will effectively address your concerns and further enhance our paper:\n\n### Weaknesses:\n\n**Q: There is a strong assumption that all transitions are independent, which is not always true. What if there is an environment where an agent needs to conduct some initial behavior (e.g. finding a key) and then using it to act later (e.g. opening a door)? It just feels like the method is designed based on the toy environments we use in RL research, and is not actually scalable for larger more complex domains in the future.**\n\nA: Temporal information can be accounted for by using the augmented states and it should be addressed by the underlying RL mechanism (hierarchical RL, constrained RL, etc.). We would like to highlight that GENIE's design to focus on individual *(s, a)* transitions and not entire trajectories is agnostic to these augmented state representations used by the policy. On this note, we would make this advantageous characteristic of GENIE's design clearer in the revised manuscript.\"\n\n\n**Q: Hate to be that person, but the name GENIE is taken by multiple works already and recently by Bruce et al. (2024) in a highly relevant paper. It would be recommended to find a more relevant acronym or simpler name.**\n\nA: Acknowledged in global rebuttal.\n\n**Q: The arrows in figure 2 are too small.**\n\nA: Thank you and we have fixed this in the revised manuscript.\n\n### Questions:\n\n**Q: What other approaches could be used to assess novelty at larger scale?**\n\nA: With regards to assessing novelty at a large scale, Section B in the appendix touches on how dimensionality-reduction techniques can be paired with GMMs for better scalability to higher-dimensional domains. As you pointed out, there is no need to restrict ourselves to GMMs. However, on the flip side, we showed that such a simple yet general method for quantifying novelty and combining it with regret could result in significant empirical gains. GENIE's main contribution lies in demonstrating the importance of novelty in UED and highlighting how it complements minimax regret. That opens the door to future UED research to look into incorporating novelty into their curriculum.\n\n**Q: Can you show any examples of levels that have high novelty but low regret, and turn out to be useful training levels for the agent?**\n\nA: Addressed in the global rebuttal (see section \"Low Regret but High Novelty Levels Provide Interesting Experiences\", i.e. Figure 2's explanation)", "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": "", "extra_scores": {}}, {"review_id": "RRoOVkOZDi", "reviewer": "Reviewer_jT1H", "summary": "After rebuttal\n\nI have upped my score to 7. I think this paper is good, as it makes a small, easy to implement and simple to understand change to existing UED methods, and it delivers improved empirical results.\n\n\n-----\n\n\nThis paper uses a GMM-based method to quantity novelty of levels in UED. It uses the state-action distribution (unordered, i.e., not trajectory distribution) induced by the agent on a level and fits a GMM to the data from previously sampled levels. A new level's novelty can be determined by computing the likelihood of its induced state-action distribution under the fitted GMM.", "questions": "- Algorithm 1, please indicate what the blue text means (I assume changes to ACCEL but being clear on this would be helpful.)\n- Please provide aggregate results averaged over all of the minigrid eval. levels. It is hard at a glance to see how the algorithms compare. \n- Do the GENIE generated levels actually look more diverse than those generated by e.g. ACCEL? Please show a sampling of levels.\n- In table 1, PLR-GENIE has the most state-action coverage, but performs much worse than the ACCEL-based methods. This seems to contradict the claim that the increased diversity is causing better performance. Could you explain this please?\n- There may be some confusion between your GENIE and [1]\n- For car racing you do use images, is the image simply flattened? Could this have problems with e.g. not being translationally invariant?\n\n[1] Bruce, Jake, et al. \"Genie: Generative interactive environments.\" _Forty-first International Conference on Machine Learning_. 2024.", "limitations": "- I think putting limitations in the main paper would be better. Figure 5 feels not super necessary and can be moved to the appendix if space is an issue.\n- Some other limitations I can think of, please comment/explain\n\t- Choosing the range of $K$ (number of GMM) kernels can be challenging?\n\t- Do I understand correctly that you just concatenate the observation and actions to form $x$, which is then used to fit the GMM? How can this scale to much larger observations?", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The idea of using state-action distributions to represent a level is not new, but it makes sense.\n- Using a fitted model and computing the likelihood using this also makes a lot of sense, compared to computing a pairwise novelty score between two levels.\n- Having the ability to have different numbers of GMM kernels is an interesting idea, and seems to provide a good way of allowing complexity to be dynamically altered.\n- Results demonstrate that the new method performs better than PLR/ACCEL, and the change in code is small.", "weaknesses": "- While the focus on unordered transition tuples is mentioned as a benefit, I would think that there are certain environments where the temporal nature of trajectories are important. Could you comment on this please?\n- Minor\n\t- Line 88, for minimax one also often cites [1]\n\t- The $\\tau$'s beneath the max/expectation in equation (1) don't have the A and P superscripts.\n\n[1] Pinto, Lerrel, et al. \"Robust adversarial reinforcement learning.\" _International Conference on Machine Learning_. PMLR, 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's careful attention to detail and the positive feedback provided. The following clarifications will hopefully address your concerns and strengthen the case for our paper:\n\n### Weaknesses\n\n**Q: While the focus on unordered transition tuples is mentioned as a benefit, I would think that there are certain environments where the temporal nature of trajectories are important. Could you comment on this please?**\n\nA: Revieiwer kpCs brought up the same point and we have answered it above (see question 1 in discussion with Revieiwer kpCs). TL;DR: agree and GENIE's design choice on prioritising individual transition tuples is flexible to accommodate non-Markovian states.\n\n**Q: Minor: 1. Line 88, for minimax one also often cites [1]; 2. The $\\tau$'s beneath the max/expectation in equation (1) don't have the A and P superscripts.**\n\nA: Appreciate the sharp eye, we have revised this.\n\n### Questions\n\n**Q: Algorithm 1, please indicate what the blue text means (I assume changes to ACCEL but being clear on this would be helpful.)**\n\nA: Thank you, we have made this clearer in the revised manuscript.\n\n**Q: Please provide aggregate results averaged over all of the minigrid eval. levels. It is hard at a glance to see how the algorithms compare.**\n\nA: Figure 4a is what you are looking for. The IQM and Optimality Gap are metrics introduced by the rliable library (Agarwal et al., 2021) used for fair aggregation of performances across different tasks (levels) and comparing the performance of algorithms.\n\n**Q: Do the GENIE generated levels actually look more diverse than those generated by e.g. ACCEL? Please show a sampling of levels.**\n\nA: Answered in our global rebuttal. The sections \"GENIE Introduces Level Complexity\", \"Low Regret but High Novelty Levels Provide Interesting Experiences\" and their accompanying plots visually demonstrates the diversity of the levels generated by GENIE.\n\n\n**Q: In table 1, PLR-GENIE has the most state-action coverage, but performs much worse than the ACCEL-based methods. This seems to contradict the claim that the increased diversity is causing better performance. Could you explain this please?**\n\nA: It is important to note that there are fundamental differences in the curriculum generation mechanisms of ACCEL and PLR outside of GENIE's control. ACCEL mechanism initiates the curriculum with \"easy\" levels (e.g. a Minigrid with no walls and only the goal) and leverages minor edits (mutation) to gradually introduce complexity to the levels. In contrast, PLR relies on domain randomization (DR) to generate new levels. DR lacks the fine-grained control over the difficulty progression that ACCEL's mutation-based method offers. As a result, even though GENIE exposes the PLR agent to a wider coverage of state-action pairs, the PLR teacher does not present these experiences to the student in an order that facilitates optimal learning. The inherent difference in curriculum generation mechanism between the two algorithms (i.e. ACCEL and PLR) admits a significant difference in performance from the get-go that cannot be recovered by GENIE. To summarize, GENIE enhances the state-action space coverage for both ACCEL and PLR, but ACCEL's gradual curriculum complexity introduction mechanism simply capitalizes on that better.\n\n**Q: There may be some confusion between your GENIE and [1]**\n\nA: Acknowledged in global rebuttal.\n\n**Q: For car racing you do use images, is the image simply flattened? Could this have problems with e.g. not being translationally invariant?**\n\nA: All algorithms incorporate a CNN model over the images, in accordance with previous UED literature. We thank you for bringing up this point and we have included a small section in the appendix to make this clear.\n\n**Q: Choosing the range of $K$ (number of GMM) kernels can be challenging?**\n\nA: Actually, $K$ does not need to be constricted to a fixed range and can be adapted online. Metrics like silhouette score (that we used) or other metrics such as AIC/BIC provide a score for the fit of the GMM and Bayesian methods can be applied to search for the $K$ (not bounded to a range) that fulfils a desired threshold of the metric. The reason why we used a fixed range for $K$ in GENIE is simply because we found that a range of 6-15 kernels already provided significant improvements to the GENIE-augmented algorithms and did not necessitate further optimization.\n\n**Q: Do I understand correctly that you just concatenate the observation and actions to form $x$, which is then used to fit the GMM? How can this scale to much larger observations?**\n\nA: Yes, your understanding is correct. Regarding the dimensionality issue, it is an issue which can be easily remedied. Dimensionality reduction techniques such as Principal Component Analysis (PCA) or learned autoencoders can be employed to scale down large observation spaces without significant loss of information. This is a direction that is also mentioned in the \"Future Work and Limitations\" section of the appendix of the main paper. High-dimensional state spaces present issues for deep learning methods in general, and remedies used by the policy algorithm to scale down the state space can be applied in parallel for the fitting of GMMs in GENIE.", "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": "", "extra_scores": {}}]

Author rebuttal:
# Global Rebuttal

## 1. Addressing GENIE's Name
There is a general consensus among the reviewers that "GENIE" might be confused with the method recently introduced by Bruce et. al. (2024). We agree that it would probably be wise to choose a different name for the framework, allowing both important works to receive their own deserved spotlights. However, in the meantime, we will still use the acronym "GENIE" when referencing our framework during this rebuttal phase to make things less confusing for everyone. We will definitely come up with a different name and implement it across the revised version of the paper.

## 2. Special Thanks to All Reviewers
We would like to express our gratitude to all the reviewers for their time in providing constructive evaluations and generally positive reception of our work. 

## 3. New Results and Explanation
We present new results that are collected in response to the reviewers' comments (please refer to the attached 1-page PDF). Note that due to limitations in time and computation, we were only able to selectively run experiments. 

### 3.1 GENIE Introduces Level Complexity
Figure 1 presents the difficulty composition (introduced by POET (Wang et al., 2019) of replayed levels for ACCEL and ACCEL-GENIE over various training intervals (based on metrics defined in Table 1).  It is clear that ACCEL predominantly favors "Easy" to "Moderate" difficulty levels. In contrast, ACCEL-GENIE increasingly incorporates "Challenging" levels into its replay set over time. This difference highlights the benefits of integrating GENIE's novelty metric into the level replay selection criteria. 

The disparity in level difficulty distribution between ACCEL and ACCEL-GENIE is a critical factor in their observed performance differences. ACCEL's training curriculum tends to remain within a comfort zone, where levels with high regret (approximated by TD-error) are greedily selected. This approach constrains the student to a limited subset of simplest environments where it can minimize its maximum prediction error. However, this narrow focus limits the student's ability to generalize, as it minimizes exposure to more complex scenarios. On the other hand, ACCEL-GENIE’s incorporation of the novelty metric actively selects more challenging levels. This strategy pushes the student beyond its comfort zone, exposing it to unfamiliar and more challenging environment parameters (e.g. higher stump heights and wider pit gaps). As a result, the student is forced to explore a broader state-action space, enhancing its robustness to out-of-distribution scenarios and leading to the discovery of higher regret levels.

Note that our figure differs from Figure 11 in Parker-Holder et al. (2022) which shows the difficulty distribution of the levels **generated and added into the buffer**, but not the actual levels selected by the teacher for the student to **replay/train on**. On that note, this also demonstrates that GENIE remedies an inefficiency in the original ACCEL algorithm, which is the fact that the mutation-based generation constantly produces high complexity levels ("Challenging" and above) but none are actually selected to train the student. 

At the moment, we currently lack statistics on the difficulty composition of levels replayed by PLR and PLR-GENIE but their similar performances suggest that the difficulty compositions are likely comparable.

[1] Parker-Holder, J., Jiang, M., Dennis, M., Samvelyan, M., Foerster, J.N., Grefenstette, E., \& Rocktaschel, T. (2022). Evolving Curricula with Regret-Based Environment Design.

### 3.2 Low Regret but High Novelty Levels Provide Interesting Experiences
Next, we visually present the effect of the novelty metric on Minigrid levels in the level replay buffer of PLR-GENIE by ablating regret. Specifically, we highlight levels that feature the lowest regret (bottom 10) yet exhibit the highest novelty (top 10); these are showcased in the first row of Figure 2. Conversely, levels that score within the lowest 10 for both regret and novelty are displayed in the second row of the same figure.

Visually, we can observe that levels with high novelty and low regret present complex and diverse scenarios that challenge the student. In contrast, the levels displayed in the second row, characterized by low regret and low novelty, often resemble simple, empty mazes that offer limited learning opportunities.

While it is not feasible to present every example level here, the contrast between the two groups is stark. Levels selected based on low regret but high novelty are significantly more varied and intricate than those chosen for their low novelty, despite both groups having low regret scores. This demonstrates that incorporating novelty alongside regret in the selection process enhances the ability to identify levels that present more interesting trajectories (experiences) to the student for learning.

### 3.3 Prioritizing Novelty Actually Increases Regret
Finally, Figure 3 shows the mean, median and summed regret in the level replay buffer of PLR$^\perp$ and PLR-GENIE across the training horizon. Surprisingly, PLR-GENIE results in comparable/slightly greater levels of regret across the training distribution despite not directly optimising for it. This observation demonstrates that prioritising novelty in the levels can actually lead to higher regret levels being discovered.

Meta-review: This paper introduces an algorithm for exploring environment spaces efficiently based on a new novelty metric. 
The authors provide compelling experimental results across a range of environments and were also able to address the concerns of the reviewers through the rebuttal phase. 
This resulted in a number of score increases and an strong consensus that the paper should be accepted. 
Given the relevance of the work I believe it would be great for this work to be highlighted as an oral at the conference.
Decision: Accept (oral)