Deep Surrogate Assisted Generation of Environments
Authors: Varun Bhatt
Bryon Tjanaka
Matthew Christopher Fontaine
Stefanos Nikolaidis
Venue: NeurIPS 2022 Accept (2022)
Keywords: Automatic Environment Generation
Surrogate Models
Quality Diversity Optimization

Abstract: Recent progress in reinforcement learning (RL) has started producing generally capable agents that can solve a distribution of complex environments. These agents are typically tested on fixed, human-authored environments. On the other hand, quality diversity (QD) optimization has been proven to be an effective component of environment generation algorithms, which can generate collections of high-quality environments that are diverse in the resulting agent behaviors. However, these algorithms require potentially expensive simulations of agents on newly generated environments. We propose Deep Surrogate Assisted Generation of Environments (DSAGE), a sample-efficient QD environment generation algorithm that maintains a deep surrogate model for predicting agent behaviors in new environments. Results in two benchmark domains show that DSAGE significantly outperforms existing QD environment generation algorithms in discovering collections of environments that elicit diverse behaviors of a state-of-the-art RL agent and a planning agent. Our source code and videos are available at https://dsagepaper.github.io/.

Deep Surrogate Assisted Generation of Environments
Varun Bhatt"
Bryon Tjanaka"
University of Southern California
University of Southern California
Los Angeles, CA vsbhattQusc.edu
Los Angeles, CA tj janakaBusc.edo
Matthew C. Fontaine"
Stefanos Nikolaidis University of Southern California
University of Southern California
Los Angeles, CA mf mfontaindusc..el edu
Los Angeles, CA nikolaid@ussc.er
Abstract
Recent progress in reinforcement learning (RL) has started producing generally capable agents that can solve a distribution of complex environments, These agents are typically tested fixed, human-authored environments. On the other hand, quality diversity (QD) optimization has been proven to be an effective component of environment generation algorithms, which can generate collections of high-quality environments that are diverse in the resulting agent behaviors. However, these algorithms require potentially expensive simulations of agents on newly generated environments. We propose Deep Surrogate Assisted Generation of Environments (DSAGE), sample-efficient QD environment generation algorithm that maintains deep surrogate model for predicting agent behaviors in environments. Results in two benchmark domains show that DSAGE significantly outperforms existing QD environment generation algorithms in discovering collections of environments that elicit diverse behaviors of a state-of-the-arr RL agent and a planning agent. Our source code and videos are available at httts:: https://dsaagpaper htt.epppaer.iithbbb.... -iw.gb..iiii.
1 Introduction
We present an efficient method of automatically generating a collection of environments that elicit diverse agent behaviors. As a motivating example, consider deploying a robot agent at scale in variety of home environments. The robot should generalize by performing robustly not only in test homes, but in any end user's s home. To validate agent generalization, the test environments should have good coverage for the robot agent. However, obtaining such coverage may be difficult, as the generated environments would depend on the application domain, e.g. kitchen or living room, and on the specific agent want to test, since different agents exhibit different behaviors.
To enable generalization of autonomous agents new environments with differing levels of complex- ity, previous work on open-ended learning 2 has integrated the environment generation and the agent training processes. The interplay between the two processes acts natural curriculum for the agents to learn robust skills that generalize to new, unseen environments (313). The performance of these agents has been evaluated either in environments from the training distribution 1 or in suites of manually authored environments 3
As step towards testing generalizable agents, there has been increasing interest in competitions 7 that require agents to generalize to new game layouts. Despite the recent progress of deep learning
Equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Update Surrogate Archive
Adapt Ni, E) via CMA-ME
(z, f f,m)
Downsample Archive
Extract Predicted Agent Performance and Measured Behavior
Sample Solution Mp, X)
Generate Environments from Solutions and Evaluate
Generate Environment
(z, f m)
Update Dataset
Train the Surrogate Vooel the Dataset
Extract Ground Truth Agent Performance and Behavior Data
Model Improvement
Model Exploitation
Update Ground Truth Archive
Agent Simulation
Self-supervised Agent Occupancy Prediction
(f, f)
Environment Generation
Occupancy Prediction
Stack with Occupancy Grid
Figure An overview of the Deep Surrogate Assisted Generation of Environments (DSAGE) algorithm. The algorithm begins by generating and evaluating random environments initialize the dataset and the surrogate model (not shown in the figure). An archive of solutions is generated by exploiting deep surrogate model (blue arrows) with QD optimizer, e-g., CMA-ME [14), A subset of solutions from this archive are chosen by downsampling and evaluated by generating the corresponding environment and simulating agent (red arrows). The surrogate model is then trained on the data from the simulations (yellow arrows). While the images show Mario levels, the algorithm structure is similar for mazes.
13] it has agents in fixed game domains, e.g. in Chess 91, Go [00, Starcraft [11], and Poker 12
been rule-based agents that have succeeded in these competitions ( Such competitions also rely on manually authored game levels test handcrafted by human designer.
While manually authored environments are important for standardized testing, creating these envi- ronments be tedious and time-consuming. Additionally, manually authored test suites are often insufficient for eliciting the diverse range of possible agent behaviors. Instead, we would like an interactive test that proposes environment, observes the agent's performance and behavior, and then proposes new environments that diversify the agent behaviors, based on what the system has learned from previous execution traces of the agent.
To address collecting environments with diverse agent behaviors, prior work frames the problem as quality diversity (QD) problem [15 A QD problem consists of objective function, e.g. whether the agent can solve the environment, and measure functions, c.g. how long the agent takes to complete their task. The measure functions quantify the behavior would like to vary in the agent, allowing practitioners to specify the case coverage they would like to see the domain they testing. While QD algorithms generate diverse collections of environments, they require large number of environment evaluations to produce the collection, and each of these evaluations requires multiple tine-conuuming simulated executions of potentially stochastic agent policies.
study how deep surrogate models that predict agent performance can accelerate the generation of environments that are diverse in agent behuviors. We draw upon insights from model-based quality diversity algorithms that have been previously shown to improve sample efficiency in design optimization [18] and Hearthstone deckbuilding [19]. Environments present much more complex

---

prediction task because the evaluation of environments involves simulating stochastic agent policies, and small changes in the environment may result in large changes in the emergent agent behaviors 220]
We make the following contributions: (1) We propose the use of deep surrogate models to predict agent performance in new environments. Our algorithm, Deep Surrogate Assisted Generation of Environments (DSAGE) (Fig. D. integrates deep surrogate models into quality diversity optimization efficiently generate diverse environments. (2) We show in two benchmark domains from previous work, a Maze domain 3 with a trained ACCEL agent 4 and a Mario domain 21 T6 with an
A agent [22], that DSAGE outperforms state-of- vate-of-the-ar thetheert QD algorithms in discovering diverse agent behaviors. (3) We show with ablation studies that training the surrogate model with ancillary agent behavior data and downsampling subset of solutions from the surrogate archive results in substantial
improvements in performance, compared to the surrogate models of previous work [9]
2 Problem Definition
Quality diversity (QD) optimization. We adopt the QD problem definition from previous work 23 A QD optimization problem specifies an objective function f IR" + R and joint measure function m : I2" + R". For each element s E S. where S C R is the range of the measure function, the QD goal is to find a solution 0 R" such that m00) and f()) is maximized.
Since the range of the measure function can be continuous, we restrict ourselves algorithms from the MAP-Elites family 24 2 that discretize this space into a finite number of M cells. A solution is mapped to a cell based on its measure m m0). The solutions that occupy cells form an archive of solutions. Our goal is to find solutions 0,, i E {1,... .... 3 that maximize the objective f for all cells the measure space.
M
max O:
f(0.)
The computed sum in ii defined as the QD-score (26). where empty cells have an objective value of Ó. A second metric of the performance of a QD algorithm is coverage of the measure space, defined as the proportion of cells that are filled in by solutions: 1 T Σ 1e.
QD for environment generation. We assume single agent acting in environment parameterized by E IR.. The environment parameters can be locations of different objects or latent variables that passed inputs to a generative model 27 A QD algorithm generates new solutions O and evaluates them by simulating the agent on the environment parameterized by 0. The evaluation returns an objective value / and measure values m. The QD algorithm attempts to generate environments that maximize f but are diverse with respect to the measures m.
3 Background and Related Work
Quality diversity (QD) optimization. QD optimization originated in the genetic algorithm com- munity with diversity optimization (28), the predecessor to QD. Later work introduced objectives to diversity optimization and resulted in the first QD algorithms: Novelty Search with Local Compe- tition (29) and MAP-Elites 25] 24) The QD community has grown beyond its genetic algorithm Bayesian optimization 30),
roots, with algorithms being proposed based on gradient ascent
differential evolution [11, and evolution strategies [4]
32
33
QD algorithms have applications in
damage recovery in robotics
reinforcement learning 34
36 and generative design [8 37].
Among the QD algorithms, those of particular interest to us are the model-based ones. Current QD algorithms either (1) learn a surrogate model of the objective and measure e.g. a Gaussian process or neural network, (2) learn a generative model of the representation parameters 42 43 or (3) draw inspiration from model-based RL 44 45)
model-based [38 39]
functions [18 40
In particular, Deep Surrogate Assisted MAP-Elites (DSA-ME) [19 trains deep surrogate model on diverse dataset of solutions generated by MAP-Elites and then leverages the model to guide MAP-Elites. However, DSA-ME has only been applied to Hearthstone deck building, a simpler prediction problem than predicting agent behavior in generated environments. Additionally, DSA-ME is specific to MAP-Elite only and cannot run other QD algorithms to exploit the surrogate model.
For consistency with the generative model literature, we instead of 0 when denoting latent vectors
3

---

Furthermore, DSA-ME restricted to direct search and cannot integrate generative models to generate environments that match a provided dataset.
Automatic environment generation. Automatic environment generation algorithms have been proposed in a variety of fields. Methods between multiple communities often share generation techniques, but differ in how each community applies the generation algorithms.
For example, in the procedural content generation (PCG) field [46], environment generator produces video game levels that result in player enjoyment. Since diversity of player experience and game mechanics is valued in games, many level generation systems incorporate QD optimiza- tion [47] [6 [ [5].. The procedural content generation via machine learning (PCGML) [53] 54] subfield studies enviromment generators that incorporate machine learning techniques such Markov Chains (55) probabilistic graphical models [56]. LSTMs [57], generative models [18)1]) and
reinforcement learning [62 63]. Prior work [64] has leveraged surrogate models trained offline
data to accelerate search-based PCG (65)
Environment generation methods have also been proposed by the scenario generation community in robotics. Early work explored automated methods for generating road layouts, vehicle arrangements, and vehicle behaviors for testing autonomous vehicles [66 Outside of autonomous vehicles, prior work [73 evaluates robot motion planning algorithms by generating environments that target specific motion planning behaviors. In human-robot interaction, QD algorithms have been applied as environment generators to find failures in shared autonomy systems and auman-aware planners tested in the collaborative Overcooked domain
[5]
Environment generation can also help improve the generality of RL. agents. Prior work proposes directly applying PCG level generation algorithms to improve the robustness of RL [74] 75 or to benchmark RL agents [76]. Paired Open-ended Trailblazer (POET) [ coevolves a population of both agents and environments to discover specialized agents that solve complex tasks. POET inspired a variety of open-ended coevolution algorithms (77779 [5) Later work proposes the PAIRED 3
PLR 180 61. and ACCEL 4 algorithms that train a single generally capable agent by maximizing the regret between a pair of agents. These methods generate environments in parallel with an agent to create an automatic training curriculum. However, the authors validate these methods human-designed environments [8]] Our work proposes a method that automatically generates valid environments that reveal diverse behaviors of these more general RL agents.
Deep Surrogate Assisted Generation of Environments (DSAGE)
Algorithm. We propose the Deep Surrogate Assisted Generation of Environments (DSAGE) algo- rithm for discovering environments that elicit diverse agent behaviors. Akin to the MAP-Elites family of QD algorithms, DSAGE maintains ground-truth archive where solutions are stored based on their ground-truth evaluations. Simultaneously, DSAGE also trains and exploits deep surrogate model for predicting the behavior of a fixed agent in new environments. The QD optimization occurs in three phases that take place an outer loop: model exploitation, agent simulation, and model improvement (Fig.)) D [eporitthm[prriieeee
the pseudocode for the DSAGE algorithm.
The model exploitation phase (lines I1 20 is an inner loop that leverages existing QD optimization algorithms and the predictions of the deep surrogate model to build an archive - referred to as the surrogate archive of solutions. The first step of this phase to query a list of B candidate solutions through the QD algorithm's 's ask method. These solutions are environment parameters, e.g., latent vectors of a GAN, which are passed through the environment generator, e.g., a GAN, create an environment (line 15). Next, we make predictions with the surrogate model. The surrogate model first predicts data representing the agent's behavior, e.g., the probability of occupying each discretized tile in the environment (line 16). referred to as "ancillary agent behavior data" (y). The predicted ancillary agent behavior data (z)) then guides the surrogate model's 's downstream prediction of the
objective (f) and the measure values (mz) (line 17) Finally, the QD algorithm's 's tell method adds the solution to the surrogate archive based on the predicted objective and measure values.
Note that since DSAGE is independent of the QD algorithm, the ask and tell methods abstract out the QD algorithm's 's details. For example, when the QD algorithm is MAP-Elites or CMA-ME, tell adds solutions if the cell the measure space that they belong to empty or the existing solution in that cell has lower objective. For CMA-ME, tell also includes updating internal CMA-ES parameters.

---

The agent simulation phase (lines 21 28
inserts subset of solutions from the surrogate archive into the ground- truth archive. This phase begins by selecting the subset of solutions from the surrogate archive (line 21. The selected solutions are evaluated by generating the corresponding environment (line 23) and simulating a fixed agent to obtain the true objective and measure values, as well as ancillary agent behavior data (line 24). Evaluation data is appended to the dataset, and solutions that improve their corresponding cell the ground-trutt truth archive are added to that archive (lines 25 26).
In the model improvement phase (line 29). the surrogate model is trained in self-supervised manner through the supervision provided by the agent simulations and the ancillary agent behavior data.
The algorithm is initialized by generating random solutions and simulating the agent in the corre- sponding enviromments (lines 2 g Subsequently. every outer iteration (lines 10 30) consists of model exploitation followed by agent simulation and ending with model improvement.
Algorithm 1: Deep Surrogate Assisted Generation of Environments (DSAGE)
Input:
N: Maximum number of evaluations, Arand" Number of initial random solutions, Nezploit: Number of iterations in the model exploitation phase, B: Batch size for the model exploitation QD optimizer
Output: Final version of the ground-truth archive Agt
Initialize the ground-truth archive Agt, the dataset D, and the deep surrogate model sm
θ + generate pennerateranddmm__ee
3
E
env <- g(0)
f. f.m. m. y f- evaluate(ene)
D DU (0, f. m. y)
Agt + add solution( f...)
end
evals Rrand while evals < do Initialize QD optimizer qd with the surrogate archive Asurrogate
10
12
for itr E (1. Nexplostt do
θ < qd..s(B((B for 0 E do
14
env g())
16
i - sww.prediettannnilarttnnn f. sm.predict(enr, 9) gd.tell(O. f. m
Model Exploitation
18
19
end
20
end
21
θ +
for 0 E θ do
23
env + g(0) f.m. m. y t evaluate(envv)
24
25
D D DU, m. y)
Agent Simulation
26
Agt t add coddd_solutionAAA (0, S, m))
27
evals <- evals +
28
end
29
sm.train(D)
Model Improvement
end
Self-supervised prediction of ancillary agent behavior data. By default, a surrogate model directly predicts the objective and measure values based on the initial state of the environment and the agent (provided the form one-hot encoded image). However, we anticipate that direct prediction will be challenging in some domains, as it requires understanding the agent's trajectory in the environment. Thus, we provide additional supervision to the surrogate model DSAGE via two-stage self-supervised process.
5

---

First, a deep neural network predicts ancillary agent behavior data. In our work, we obtain this data by recording the expected number of times the agent visits each discretized tile in the environment, resulting in an "occupancy grid." We then concatenate the predicted ancillary information, i.e., the predicted occupancy grid, with the one-hot encoded image of the environment and pass them through another deep neural network to obtain the predicted objective and measure values. We use CNNs for both predictors and include architecture details in Appendix B. As a baseline, we compare our model with CNN that directly predicts the objective and measure values without the help of ancillary data.
Downsampling to select solutions from the surrogate archive. After the model exploitation phase, the surrogate archive is populated with solutions that were predicted to be high-periie performing and diverse. Hence, a basic selection mechanism (line (T) would select all solutions from the surrogate archive identical to DSA-ME [19]. However, if the surrogate archive is overly populated, full selection may result a large number of ground-truth evaluations per outer-loop iteration, leading to fewer outer loops and less surrogate model training. To balance the trade-off between evaluating solutions from the surrogate archive and training the surrogate model, we only select a subset of solutions for evaluation by downsampling the surrogate archive. Downsampling uniformly divides the surrogate archive into sub-regions of cells and selects random solution from each area.
5 Domains
We test our algorithms in two benchmark domains from prior work: a Maze domain 82 3 4 with a trained ACCEL agent [4] and Mario domain [83] [6) with an A* agent (22). We select these domains because, despite their relative simplicity (each environment is represented as 2D grid of
tiles), agents in these environments exhibit complex and diverse behaviors.
In the Maze domain, we directly search for different mazes, with the QD algorithm returning the layout of the maze. In the Mario domain, we search for latent codes that are passed through pre-trained GAN, similar to the corresponding previous work.
We select the objective and measure functions as described below. Since the agent or the environment dynamics are stochastic in each domain, we average the objective and measure values over 50 episodes in the Maze domain and 5 episodes in the Mario domain.
Maze. We set binary objective function f that is if the generated environment is solvable and 0 otherwise, indicating the validity of the environment. Since we wish to generate visually diverse levels that offer range of difficulty level for the agent, we select as measures (1) number of wall cells (range: [0, 256]), and (2) mean agent path length (range: [0, 648), where 648 indicates failure to reach the goal).
Mario. Since we wish to generate playable levels, we set the objective as the completion rate, i.e.,
the proportion of the level that the agent completes before dying. We additionally want to generate environments that result in qualitatively different agent behaviors, thus we selected as measures: (1)
sky tiles, the number of tiles of a certain type that are in the top half of the 2D grid (range: [0, 150)). (2) number of jumps, the number of times that the A* agent jumps during its execution (range: [0, 100)).
See Appendix A for further environment details.
6 Experiments
6.1 Experiment Design
Independent variables. In each domain (Maze and Mario), we follow a fetween-groupe design, where the independent variable is the algorithm. We test the following algorithms:
DSAGE: The proposed algorithm that includes predicting ancillary agent behavior data and downsam- pling the surrogate archive (Sec.
The proposed algorithm with ancillary data prediction and downsampling. i.e., selecting all solutions from the surrogate archive.
DSAGE-Only Anc:
DSAGE- OSAGE-Only Down: The proposed algorithm with downsampling and no ancillary data prediction.

---

(a) Maze
(b) Mario
DSAGE
DSAGF-OOll Down
MAP-Elites
DSAGE
DSAGI--Oely Down
CMA-ME
DSAGE-Only Only
DSAGE
DSAGE-Oniy Only Ane
Archive Coverage
QD-score
Archive Coverage
0.4
0.4
10K
0.2
2.5%
0.2
0-
0.0
0
0.0
50k
100k
50k Evaluations
100k
5k
10k
Sk
10k
Evaluations
Evaluations
Evaluations
Archive Caverage
Archive Coverage
Algorithm
QD score
Algorichm
QD scurr
DSAGE
16,446.60 +: 42.27
0.40
DSAGE
4,362.29
0.30 0.00
DSAGE-Ooly Ane
14,568.00 + 434.56
0.35 = 0.01
DSAGE-Only Ane
2,045.28 + 201.64
0.16 0.01
DSAGE-Oaly Down
14,205.20 + 40.86
0.34 = 0.00
DSAGEE-Oll Down
4,067.42
102.06
0.30 0.01
DSAGE Busic
11,740.00 1 84.13
0.28 1: 0.00
DSAGE Basic
1.306.11
50.90
0.11 0.01
MAP-Flites
10,480 80 + 150.13
0.25 2 0.00
CMA-ME
1.840.17 + 95.76
0.13 0.01
DR
5,199.60
30.32
0.13
DR
92.75 00.75-230 3.01
0.01 0.00
Figure 2: QD-score and archive coverage attained by baseline QD algorithms and DSAGE in the Maze and Mario domains over 5 trials. Tables and plots show mean and standard error of the mean.
DSAGE Basic: The basic version of the proposed algorithm that selects all solutions from the surrogate archive and does not predict ancillary data.
Baseline QD: The QD algorithm without surrogate assistance. We follow previous work [16] and use CMA-ME for the Mario domain. Since CMA-ME operates only in continuous spaces, we use MAP-Elites in the discrete Maze domain.
Domain Randomization (DR) 84-86) Algorithm that generates and evaluates random solutions, i.c., wall locations in the maze domain and the latent code to pass through the GAN in the Mario domain.
Dependent variables. We measure the quality and diversity of the solutions with the QD-score metric (Eq. T. As an additional metric of diversity, we also report the archive coverage. We run each algorithm for 5 trials in each domain.
Hypothesis. We hypothesize that DSAGE will result in a better QD-score than DSAGE Basic in all domains, which in lurn will result in belter performance than the baseline QD algorithm. DSAGE, DSAGE Basic, and the baseline QD algorithm will all exceed DR. We base this hypothesis on previous work 17] which shows that QD algorithms outperform random sampling in a variety of domains, as well as previous work [18 19 which shows that surrogate- asssssted MAP-Elites outperforms standard MAP-Elites design optimization and Hearthstone domains. Furthermore, we expect that the additional supervision through ancillary agent behavior data and downsampling will result in DSAGE performing significantly better than DSAGE Basic.
6.2 Analysis
Fig.1
summarizes the results obtained by the six algorithms on the Maze and the Mario domains.
One-way ANOVA tests showed significant effect of the algorithm on the QD-score for the Maze (F 24) = 430.98, p < 0.001) and Mario (F(5, 24) = 238.09,, < 0.001) domains.
Post-hoc pairwise comparisons with Bonferroni corrections showed that DSAGE outperformed DSAGE Basic, Baseline QD, and DR in both the Maze and the Mario domains (p < 0.001).
Additionally, DSAGE Basic outperformed MAP-Elites and DR in the Maze domain (p < 0.001).
while it performed significantly worse than the QD counterpart, CMA-ME, in the Mario domain (p- = 0.003). Finally, Baseline QD outperformed DR in both the Maze and Mario domains (p 0.001).
These results show that deep surrogate assisted generation of environments results significant improvements compared to quality diversity algorithms without surrogate assistance. They also show that adding ancillary agent behavior data and downsampling is important both domains. Without these components, DSAGE Basic has limited or improvement compared to the QD algorithm
7

---

Table 1: Number of evaluations required to reach QD-score of 10480.8 in the Maze domain and 1306.11 in the Mario domain.
(a) Maze
(b) Mario
Algorilim
Evaluations
Algorilhm
Evaluations
DSAGE
33,930.40 1: 1,411.04
DSAGE
2,464.40 = 336.36
DSAGE-Only Ane
51,919.6 60 8,254.24
ASAG--nlly Ane
7,727 20
1,433.33
DSAGE-Only Down
42,816.60 60 + 691.38
DSAGE-Oaly Down
2,768.60
586.34
DSAGE Basic
85,328.60
+: 2,947.24
DSAGE Basic
10,000
MAP Elites
100,000
CMA ME
5,760.00
516.14
Table 2: Mean absolute error of the objective and measure predictions by the surrogate models.
Mario
Algorithm
Objective MAF
Number of Wall Cells MAF
Mean Agent Path Length MAF
Objective MAE
Number of Sky Tiles MAF
Number of Jumps MAF
DSAGE
0.03
0.37
96.58
0.10
1.10
7.16
DSAGE--Olly Ane
0.04
0.96
95.14
0,20
1.11
9.97
DSAGE Only Down
0.10
0.95
151.50
0.11
0.87
6.52
DSAGE Basic
0.18
5.48
157.69
0.20
2.16
10.71
without surrogate assistance. Additionally, domain randomization is significantly worse than DSAGE as well as the baselines. The archive coverage and consequently the QD-score is negligible in the Mario domain since randomly sampled latent codes led to little diversity in the levels.
Table shows another metric of the speed-up provided by DSAGE: the number of evaluations (agent simulations) required to reach fixed QD-score. We set this fixed QD-score to be 10480.8 in the Maze domain and 1306.1 in the Mario domain, which are the mean QD-scores of MAP-Elites and DSAGE Basic, respectively, in those domains. DSAGE reaches these QD-scores faster than the baselines do.
To assess the quality of the trained surrogate model, we create combined dataset consisting of data from one run of each surrogate assisted algorithm. We use this dataset to evaluate the surrogate models trained from separate runs of DSAGE and its variants. Table mbble2showe shows the mean absolute (MAE) of the predictions by the surrogate models. The model learned by DSAGE Basic fails to predict the agent-based measures well. It has MAE of 157.69 for the mean agent path length in Maze and MAE = 10.71 for the number of jumps in Mario. In contrast, the model learned by DSAGE makes more accurate predictions, with MAE 96.58 for mean agent path length and MAE 7.16 for number of jumps. We provide detailed results of the surrogate model predictions in Appendix B.
6.3 Ablation Study
Sec. describes two key components of DSAGE: (1) self-supervised prediction of ancillary agent behavior data, and (2) downsampling to select solutions from the surrogate archive. We perform an ablation study by treating the inclusion of ancillary data prediction (ancillary data / no ancillary data) and the method of selecting solutions from the surrogate archive (downsampling / full selection) as independent variables. A two-way ANOVA for each domain showed no significant interaction effects. We perform a main effects analysis for each independent variable.
Inclusion of ancillary data prediction. A main effects analysis for the inclusion of ancil- lary data prediction showed that algorithms that predict ancillary agent behavior data (DSAGE, DSAGE-Only Anc) performed significantly better than their counterparts with ancillary data prediction (DSAGE-Only Down, DSAGE Basic) in both domains (p < 0.001).
Fig. shows that predicting ancillary agent behavior data also resulted in a larger mean coverage for Maze, while it has little or no improvement for Mario. Additionally, as shown Table 2 predicting ancillary agent behavior data helped improve the prediction of the mean agent path length in the Maze domain but provided little improvement to the prediction of the number of jumps in the Mario domain. The reason is that in the Maze domain, the mean agent path length is scaled version of the sum of the agent's tile occupancy frequency, hence the two-stage process which predicts the occupancy grid first is essential for improving the accuracy of the model. On the other hand, the
8

---

presence of jump in Mario depends not only on cell occupancy, but also on the structure of the level and the sequence of the occupied cells.
Method of selecting solutions from the surrogate archive. A main effects analysis for the method of selecting solutions from the surrogate archive showed that the algorithms with downsampling (DSAGE, DSAGE-Only Down) performed significantly better than their counterparts with no down- sampling (DsAGE-Only Anc, DSAGE Basic) in both domains (p < 0.001).
major advantage of downsampling is that it decreases the number of ground-truit evaluations in each outer iteration. Thus, for fixed evaluation budget, downsampling results in greater number of outer iterations. For instance, in the Maze domain, runs without downsampling had only 6-7 outer iterations, while runs with downsampling had approximately 220 outer iterations. More outer iterations leads to more training and thus higher accuracy of the surrogate model. In turn, a more accurate surrogate model will generate better surrogate archive in the inner loop.
We include an ablation in Appendix outer iterations helps with performance: (I) larger number of training epochs, (2) more updates to the dataset allowing the surrogate model to iteratively correct its own errors. We observed that iterative correction accounted for most of the performance increase with downsampling.
test between two possible explanations for why having more
The second advantage of downsampling that selects solutions evenly from all regions of the measure space, thus creating a more balanced dataset. This helps train the surrogate model in parts of the measure space that are not frequently visited. We include an additional baseline in Appendix in which we select a subset of solutions uniformly at random from the surrogate archive instead of downsampling. We observe that downsampling has slight advantage over uniform random sampling in the Maze domain.
Furthermore, if instead of downsampling we sampled multiple solutions from nearby regions of the surrogate archive, the prediction errors could cause the solutions to collapse to a single cell in the ground-truth archive, resulting in many solutions being discarded.
Overall, our ablation study shows that both predicting the occupancy grid as ancillary data and downsampling the surrogate archive independently help improve the performance of DSAGE.
6.4
Qualitative Results
Fig. 3 and Fig. show example environments generated by DSAGE in the Maze and Mario domains.
Having the mean agent path length measure in the Maze domain results in environments of varying difficulty for the ACCEL agent. For instance, we observe that the environment in Fig. (]a) a) has very few walls, yet the ACCEL agent gets stuck in the top half of the maze and is unable to find the goal within the allotted time. On the other hand, the environment in Fig. 3 d) is cluttered and there multiple dead-ends, yet the ACCEL agent is able reach the goal.
Fig. 4 shows that the generated environments result in qualitatively diverse behaviors for the Mario agent too. Level (b) only has a few sky tiles and is mostly flat, resulting in a small number of jumps. Level (c) has a "staircase trap" on the right side, forcing the agent to perform continuous jumps to escape and complete the level. We include videos of the playthroughs in the supplemental material.
7 Societal Impacts
By introducing surrogate models into quality diversity algorithms, we can efficiently generate environments that result in diverse agent behaviors. While we focused on an RL agent in Maze domain and symbolic agent in a Mario game domain, method can be applied to variety of agents and domains. This can help with testing the robustness of agents, attaining insights about their behavior, and discovering edge cases before real-world deployment. Furthermore, in the future, closing the loop between environment generation and agent training can improve the ability of agents to generalize new settings and thus increase their widespread use.
anticipate that
Our work may also have negative impacts. Training agents in diverse environments can considered as step towards open-ended evolution [87] which raises concerns about the predictability and safety of the emergent agent behaviors [8 89]. Discovering corner cases that result in unwanted behaviors or catastrophic failures may also be used maliciously to reveal vulnerabilities in deployed agents 190).

---

(e)
Number of wall colls:43 Mean agent path length: MAX
Number wall cells: 72
Number wall cells: Number of wall cells: 188
Moan ageat path length: 610
Mean agent path length: 369
Mean agent path length: 636
DSAGE
LD
Mcnn ogeat path length
003
500-
.00
(c) Number wall cells: 50 Mean agent path longth: 81
(8)
(b)
Number of wall cells: 100
200
Number wall cells: 121 Mean agent path length: 200
Number of wall cells: 214
Mean agent path length: 297
Mean agent path length: 8
02
2.0
Number of wall cells
Figure 3: Archive and levels generated by DSAGE in the Maze domain. The agent's 's initial position shown orange triangle, while the goal is green square.
DSAGE
(c)
Sky tiles: 40, Number of jumps: 40
Sky tiles: 100, Number of jumps: 50
Number of jumps
80
60
36
(b)
Sky tiles: I, Number jumps:
Sky tiles: 140, Number jumps:
20
100
120
140
Sky tiles
Figure 4: Archive and levels generated by DSAGE in the Mario domain. Each level shows the path Mario takes, starting on the left of the level and finishing on the right.
Limitations and Future Work
Automatic environment generation a rapidly growing research area with a wide range of applications, including designing video game levels (3] 54. training and testing autonomous agents [74, 76
13 41, and discovering failures human-robot interaction [17 [66]. We introduce the DSAGE algorithm, which efficiently generates diverse collection of environments via deep surrogate models of agent behavior.
Our paper has several limitations. First, occupancy grid prediction does not encode temporal information about the agent. While this prediction allows us avoid the compounding error problem of model-based RL [9I]. forgoing temporal information makes it harder to predict some behaviors, such the number jumps Mario. We will explore this trade-off in future work.
Furthermore, we have studied 2D domains where a single ground-truth evaluation lasts between a few seconds and a few minutes. We excited about the use of surrogate models to predict the performance of agents in more complex domains with expensive, high-fidelity simulations [92].
Acknowledgments and Disclosure of Funding
This work was partially funded by NSF CAREER (#2145077) and NSF GRFP (#DGE-1842487) One of the GPUs used in the experiments was awarded by the NVIDIA Academic Hardware Grant. We thank J. Parker-Holder et al., the authors of the ACCEL agent, providing a pre-trained model of the agent for experiments. We also thank Ya- Ya-Chuan Hsu for providing invaluable feedback.
10

---

References
[1] R. Wang. J. Lehman, J. Clune, and K. O. Stanley, "Paired open-ended trailblazer (POET): end- lessly generating incrcasingly complex and diverse learning environments and their solutions, CoRR, vol. abbs/190..01755 2019.
[2] Wang, Lehman, Rawal, J. Zhi, Li, Clune, and O. Stanley, "Enhanced POET: open-ended reinforcement learning through unbounded invention of learning challenges and their solutions," in Proceedings of the 37th International Conference on Machine Learning, ICML, 2020.
[3] M. Dennis, N. Jaques, E. Vinitsky, A. M. Bayen, S. Russell, A. Critch, and S. Levine, "Emergent com- plexity and zero-shot transfer via unsupervised environment design," in Advances in Neural Information Processing Systems 33, 2020.
[4] J. Parker-Holder, M. Jiang. M. Dennis, M. Samvelyan, J. N. Foerster, E. Grefenstette, and T. Rocktäschel, "Evolving curricula with regret-based environment design." CoRR, vol. abs/2203.01302, 2022.
[5] A. Dharna, A. K. Hoover, J. Togelius, and L. Soros, "Transfer dynamics in emergent evolutionary curricula," " IEEE Transactions on Games, 2022.
[6] M. Jiang, M. Dennis, J. Parker-Holder, J. N. Foerster, E. Grefenstette, and T. Rocktäschel, "Replay-guided" adversarial environment design," in Advances in Neural Information Processing Systems 34, 2021.
[7] D. P. Liebana, S. Samothrakis, J. Togelius, T. Schaul, and S. M. Lucas, "General video game Al: competition, challenges and opportunitics." in Proceedings of the 30th AAAI Conference on Artificial Intelligence, 2016.
[8] Hambro, Mohanty, D. Babaev, Byeon, D. Chakraborty, E. Grefenstette, M. Jiang, er al., "Insights from the NeurlPS 2021 NetHack challenge," CoRR, vol. abs/2203. 11889, 2022.
[9] D. Silver. T. Hubert, Schrittweeeer. Antonoglou, Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel. et al., "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play, Science, 2018.
[10] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schritwieser, et al., "Mastering the game of Go with deep neural networks and tree search," Nature, 2016.
[11] O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev, et al., "Grandmaster level in StarCraft II using multi-agent reinforcement learning," Nature, 2019.
[12] M. Moraveík, M. Schmid, N. Burch, V. Lisy, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, and M. H. Bowling, "Deepstack: Expert-level antificial intelligence in no-limit poker," Science, 2017.
[13] N. Brown and T. Sandholm, "Superhuman Al for multiplayer poker." Science, 2019.
[14] M. C. Fontaine. J. Togelius. S. Nikolaidis, and A. K. Hoover, "Covariance matrix adaptation for the rapid
illumination of behavior space," in Proceedings of the Genetic and Evolutionary Computation Conference, 2020.
[15] M. C. Fontaine, Y. Hsu. Y. Zhang, B. Tjanaka, and S. Nikolaidis, "On the importance of environments in human-robee coordination." Robotics: Science and Systems, 2021.
[16] M. C. Fontaine, R. Liu, A. Khalifa, J. Modi, J. Togelius, A. K. Hoover, and S. Nikolaidis, "Iluminating mario scenes in the latent space of generative adversarial network," Proceedings of the Thirty-Fifih AAAI Conference on Artificial Intelligence, 2021.
[17] M. C. Fontaine and S. Nikolaidis, "A quality diversity approach to automatically generating human-robot interaction scenarios in shared autonomy," in Robotics: Science and Systems, 2021.
[18] A. Gaier, A. Asteroth, and J.-B. Mouret, "Data-efficient design exploration through surrogate- assisted illumination," Evolutionary Computation, 2018
[19] Zhang, M. C. Fontaine, A. K. Hoover, and S. Nikolaidis, "Deep surrogate assisted MAP-Elites for automated hearthstone deckbuilding." CoRR, vol. abs/2112.035:: 2021.
[20] N. Sturtevant, N. Decroocq. A. Tripodi, and M. Guzdial, "The unexpected consequence of incremental design changes," in Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2020.

---

[21] S. Karakovskiy and J. Togelius. "The mario Al benchmark and competitions." IEEE Transactions on Computational Intelligence and Al in Games, 2012.
[22] Baumgarten, "Infinite super mario AI," 2009.
[23] M. C. Fontaine and Nikolaidis, "Differentiable quality diversity," Advances in Neural Information Processing Systems, vol. 34, 2021.
[24] A. Cully, J. Clune, D. Tarapore, and J.-B. Mouret, "Robots that can adapt like animals," Nature, 2015.
[25]] J. Mouret and J. Clune, "Illuminating search spaces by mapping elites," CoRR, vol. abs/1.504.0990
2015.
[26] J. Pugh, Soros, and K. O. Stanlcy, "Quality diversity: new frontier for evolutionary computationn" Frontiers in Robotics and AI, 2016.
[27] I. Goodfelllww J. Pouget- M. Mirza, B. Xu, D. Farde-Farley, S. Ozair, A. Courville, and Y. Bengio, "Gencrative adversarial nets," in Advances in Neural Information Processing Systems, 2014.
[28] J. Lehman and K. O. Stanley, "Abandoning objectives: Evolution through the search for novelty alone," Evolutionary Computation, 2011.
[29] J. Lehman and K. O. Stanley, "Evolving a diversity virtual creatures through novelty search and local competition," in Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, 2011.
[30] P. Kent and J. Branke, "Bop-elites, bayesian optimisation algorithm for quality-diversity search," CoRR, vol. abs/2005.0455 04320, 2020.
[31] T. J. Choi and J. Togelius, "Self-referential quality diversity through differential map-clites," in Proceed- ings of the Genetic and Evolutionary Computation Conference, 2021.
[32] E. Conti, V. Madhavan, F. P. Such, J. Lehman, K. O. Stanley, and J. Clune, "Improving exploration in evolution strategies for deep reinforcement learning via population of novelty- agents," in Advances in Neural Information Processing Systems 31, 2018
[33] C. Colas. V. Madhavan, J. Huizinga. and J. Clune, "Scaling map-elites deep neuroevolution." in Proceedings of the Genetic and Evolutionary Computation Conference. 2020.
[34] B. Tjanaka, M. C. Fontaine, J. Togelius, and S. Nikolaidis, "Approximating gradients for diffcrentiable quality diversity in reinforcement learning," CoRR, vol. abs/2202.03 003666, 2022.
[35] O. Nilsson and A. Cully, "Policy gradient assisted map-elites." in Proceedings of the Genetic and Evolutionary Computation Conference, 2021.
[36] G. Cideron, T. Pierrot, N. Perrin, K. Beguir, and O. Sigaud, "QD-RL: efficient mixing of quality and diversity in reinforcement learning." CoRR, vol. 08500,,6.08505, 2020.
[37] A. Hagg. S. Berns, A. Asteroth, S. Colton, and T. Bäck, "Expressivity of parameterized and data-driven representations in quality diversity search," in Proceedings of the Genetic and Evolutionary Computation Conference, 2021.
[38] T. Bartz-Beiellteen. "A survey of model-based methods for global optimization."" Bioinspired Optimization Methods and Their Applications, 2016.
[39] T. M. Mocrland, J. Brockens, and C. M. Jonker, "Model-basee reinforcement learning: A survey," CoRR, vol. abs/2006. 16712, 2020.
[40] A. Hagg. D. Wilde, A. Asteroth, and T. Bäck, "Designing air flow with surrogate- assisted phenotypic niching." in Proceedings the International Conference Parallel Problem Solving from Nature, 2020.
[41] Cazenille, N. Bredeche, and N. Aubert-Kator "Exploring self-assembling behaviors in swarm of bio-micro-robots using surrogate-assisted map-elites." " in IEEE Symposium Series on Computational Intelligence (SSCI), 2019.
[42] A. Gaier, A. Asteroth, and J.-B. Mouret, "Discovering representations for black-box optimization," in Proceedings the Genetic and Evolutionary Computation Conference, 2020.
12

---

[43] N. Rakicevic, A. Cully, and P. Kormushev. "Policy manifold search: Exploring the manifold hypothesis for diversity-based neuroevolution," in Proceedings of the Genetic and Evolationary Computation Conference, 2021.
[44] I.. Keller, D. Tanneberg. S. Stark, and J. Peters, "Model-based quality-diversity search for efficient rohot lcarning." " in Proceedings of the IEFF/RSJ International Conference on Intelligent Robots and Systems, IROS, 2020.
[45] B. Lim, L. Grillotti, L. Bernasconi, and A. Cully, "Dynamics-aware quality-diversie for efficient learning skill repertoires." " CoRR, vol. abss2209.08522. 2021.
[46] N. Shaker, J. Togelius, and M. J. Nelson, Procedural Content Generation in Games. Springer, 2016.
[47] D. Gravina, A. Khalifa, A. Liapis. J. Togelius, and G. N. Yannakakis, "Procedural content generation through quality diversity," in Proceedings of the IEEE Conference on Games (CoG), 2019.
[48] Farle, J. Snider, M. C. Fontaine, S. Nikolaidis, and Togelius, "Illuminating diverse neural cellular automata for level generation." CoRR, vol. abs/2109.05489, 2021.
[49] A. Khalifa, S. Lee, Nealen, and J. Togelius, "Talakat: Bullet hell generation through constrained map-elites," in Proceedings of the Genetic and Evolutionary Computation Conference, 2018.
[50] K. Steckel and Schrum, "Illuminating the space of beatable lode runner levels produced by various gen- erative adversarial networks," " Proceedings of the Genetic and Evolutionary Computation Conference, 2021.
[51] J. Schrum, V. Volz, and S. Risi, "CPPN2GAN: combining compositional pattern producing networks and gans for large-scale pattern generation," in Proceedings of the Genetic and Evolutionary Computation Conference, 2020.
[52] A. Sarkar and S. Cooper, "Generating and blending game levels via quality diverrityy in the latent space of a variational autoencoder," Proceedings of the 16th International Conference on the Foundations of Digital Games, 2021.
[53] A. Summerville, S. Snodgrass, M. Guzdial, Holmgård, A. K. Hoover, A. Isaksen, A. Nealen, and J. Togelius, "Procedural content generation via machine learning (PCGML)"" IEEE Transactions on Games, 2018.
[54] J. Liu, S. Snodgrass, A. Khalifa, Risi, G. N. Yannakakis, and Togelius, "Deep learning for procedural content generation." Neural Computing and Applications, 2021.
[55] Snodgrass and S. Ontañónn "Experiments in map generation using markov chains." in Proceedings of the 9th International Conference on the Foundations of Digital Games, FDG, 2014.
[56] M. Guzdial and M. Riedl, "Game level generation from gameplay videos," " in Proceedings of the 12th Artificial Intelligence and Interactive Digital Entertainment Conference. 2016.
[57] A. Summerville and M. Mateas, "Super mario as string: Platformer level generation via LSTMs," in Proceedings of the First Joint International Conference of Digital Games Research Association and Foundation of Digital Games, DiGRA/FDG, 2016.
[58] V. Volz, J. Schrum, J. Liu, S. M. Lucas, A. Smith, and S. Risi, "Evolving mario levels in the latent space of a deep convolutional generative adversarial network," " in Proceedings of the Genetic and Evolutionary Computation Conference, 2018.
[59] F. Giacomello, P. L.. Lanii, and D. Loiacono, "DOOM level generation using generative adversarial networks," " Proceedings of the IEEE Games, Entertainment, Media Conference (GEM), 2018
[60] R. R. Torrado, A. Khalifa, M. C. Green, N. Justesen, S. Risi, and J. Togelius, "Bootstrapping conditional gans for video game level generation," " in Proceedings of the IEEE Conference on Games, 2020.
[61] A. Sarkar, Z. Yang, and S. Cooper, "Conditional level generation and game blending," CoRR. vol. abs/2010.07735, 2020.
[62] A. Khalifa, P. Bontrager, S. Earle, and J. Togelius, "PCGRI: procedural content generation via reinforce- ment lcarning," in Proceedings of the AAAI Conference Artificial Intelligence and Interactive Digital Entertainment, 2020.
[63] S. Earle, M. Edwards, A. Khalifa, P. Bontrager, and J. Togelius, "Learning controllable content generators." in Proceedings of the IEEE Conference on Games (CoG), 2021.
13

---

[64] D. Karavolos, A. Liapis. and G. N. Yannakakis, "A multifaceted surrogate model for search-based procedural content generation." " IEEE Transactions Gamex, 2021.
[65] J. Togelius, G. N. Yannakakis, K. O. Stanley, and C. Browne, "Search-hased procedural content generation: A taxonomy and survey," IEEF Transactions on Computaaionnal Intelligence and Al in Games, 2011.
[66] J. Arold and R. Alexander, "Testing autonomous robot control software using procedural content generation." in Proceedings of the 32nd International Conference on Computer Safety, Reliability, and Security, 2013.
[67] G. E. Mullins, P. G. Stankiewicz, R. C. Hawthorne, and S. K. Gupta, "Adaptive generation of challenging scenarios for testing and evaluation of autonomous vehicles," Journal of Systems and Software, 2018.
[68] Y. Abeysirigoonwwadeea. F. Shkurti, and G. Dudek, "Generating adversarial driving scenarios in high- fidelity simulators," in Proceedings of the International Conference on Robotics and Automattio (ICRA), 2019.
[69] E. Rocklage, H. Kraft, A. Karatas, and J. Seewig, "Automated scenario generation for regression testing of autonomous vehicles." in Proceedings of the 20th IEEE International Conference on Intelligent Transportation Systems (ITSC). 2017.
[70] A. Gambi, M. Mueller, and G. Fraser, "Automatically testing self-driving cars with search-based procedu- ral content generation," in Proceedings of the 28th ACM SIGSOFT International Symposiun on Software Testing and Analysis, 2019.
[71] D. Sadigh, S. S. Sastry, and S. A. Seshia, "Verifying robustness of human-aware autonomous cars," IFAC- Papersspes 2019.
[72] D. J. Fremont, T. Dreossi, S. Ghosh, X. Yue, A. L. Sangiovamni-Vnnceeelli, and S. A. Seshia, "Scenic: a language for scenario specification and scene generation." in Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. 2019.
[73] Y. Zhou, S. Booth, N. Figueroa, and J. Shah, "RoCUS: rohot controller understanding via sampling," in Proceedings of the Conference on Robot Learning, 2021.
[74] S. Risi and J. Togelius, "Increasing generality in machine learning through procedural content generation." " Nature Machine Intelligence. 2020.
[75] Justesen, R. R. Torrado, P. Bontrager, Khalifa, Togelius, and S. Risi, "Illuiinating generalization in deep reinforcement learning through procedural level generation," arXiv preprint 1806. 10729, 2018.
[76] K. Cobbe, C. Hesse Hilton, and J. Schulman, "Leveraging procedural generation to benchmark reinforcement learning." in Proceedings of the International Conference on Machine Learning, 2020.
[77] Gabor, A. Sedlmeier, M. Kiermeier, Phan, M. Henrich, M. Pichlmair. B. Kempter, Klein, Sauer. R. AG, et al. "Scenario co-evolution for reinforcement learning on a grid world smart factory domain." in Proceedings of the Genetic and Evolutionary Computation Conference, 2019.
[78] D. M. Bossens and D. Tarapore, "QED: using qualtty-awirromenn--iieeiii to evolve resilient robot swarms," IEEE Transactions on Evolutionary Computation, 2020.
[79] A. Dhara,, J. Togelius, and L. B. Soros, "Co-generation of game levels and game-playing agents," in Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2020.
[80] M. Jiang, E. Grefenstette, and Rocktäschel, "Prioritized level replay." Proceedings of the 38th International Conference on Machine Learning, ICML, 2021.
[81] R. Kirk, A. Zhang, F. Grefenstette, and T. Rocktäschel, "A survey of generalisation in deep reinforcement learning," " CoRR, vol. abs/21 11.0919,,, 2021.
[82] M. Chevalier- L. Willems, and S. Pal, "Minimalistic gridworld environment for OpenAl gym." https://github. httt:s////ggttiieecccoo///ammmms wttp://///ggmmimiinnnnnnm. 2018
[83] J. Togelius, S. Karakovskiy, and R. Baumgarten, "The 2009 mario Al competition," in Proceedings of the IEEE Congress on Evolutionary Computation, CEC, 2010.
[84] N. Jakobi, "Evolutionary robotics and the radical envelope- mnvelope-of-note noise hypothesis." Adaptive Behavior. 1998.
14

---

[85] F. Sadeghi and S. Levine, "CAD2RL: real single-image flight without single real image." in Proceedings Robotics: Science and Systems XIII. 2017.
[86] J. Tobin, R. Fong, A. Ray. J. Schneider, W. Zaremba, and P. Abheel, "Domain randomization for transferring deep neural networks from simulation the real world," in Proceedings of the IEEE/RS) International Conference on Intelligent Robots and Systems, IROS, 2017.
[87] K. O. Stanley, J. Lehman, and L. Soros, "Open-endedness: The last grand challenge you' never heard of," 2017.
[88] A. Ecoffet, Clune, and Lehmann "Open questions creating safe open-ended AI: tensions between control and creativity," CoRR, vol. abs/2006.07495 2020.
[89] D. Hendrycks, N. Carlini, J. Schulman, and J. Steinhardt, "Unsolved problems in ML safety," CoRR, vol. abs/2109.13911 2021.
[90] A. Roy, N. Memon, J. Togelius, and Ross, "Evolutionary methods for generating synthetic masterprint templates: Dictionary attack in fingerprint recognition," in 2018 International Conference on Biometrics (ICB), pp. 39 49, IEEE, 2018.
[91] C. Xiao, Y. Wu, C. Ma, D. Schuurmans, and M. Müller, "Learning to comhat compounding-crror in model-hased reinforcement learning," CoRR, vol. abs/1912.1 1206, 2019.
[92] P. R. Wurman, S. Barrett, K. Kawamoto, J. MacGlashan, K. Subramanian, T. J. Walsh, R. Capobianco, A. Devlic, F. Eckert, F. Fuchs, et al., "Outracing champion gran turismo drivers with deep reinforcement lcarning," Nature, 2022.
[93] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and Stein, Introduction algorithmss MIT press. 2022.
[94] A. Khalifa, "Mario AI framework." 2019.
[95] M. Arjovsky, S. Chintala, and L. Bottou, "Wasserstein generative adversarial networks," in Proceedings of the 34th International Conference on Machine Learning, 2017.
[96] L. Guirajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. Courville, "Improved training of wasserstein GANs," in Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
[97] loffe and C. Szegedy, "Batch normalization: Accelerating deep network training by reducing internal covariate shift," in Proceedings of the 32nd International Conference on Machine Learning, ICML, 2015.
[98] K. He, X. Zhang, S. Ren, and J. Sun, "Deep residual learning for image recognition," in Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition, 2016.
[99] B. Tjanaka, M. C. Fontaine, D. H. Lee, T. T. M. Vu, Y. Zhang. S. Sommerer, N. Dennler, and S. Niko- laidis, "pyribs: A bare-bones python library for quality diversity optimization." pppimiiationnatttss///gggaaaaa /otp://./gthuu.cm//o/ icaros-usc/piie usaros- 2021.
[100] D. P. Kingma and J. Ba, "Adam: A method for stochastic optimization," in Proceedings of the 3rd International Conference Learning Representations, ICLR, 2015.
[101] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, et al., "PyTorch: imperative style, perforerformncc deep learning library." in Advances in Neural Information Processing Systems, 2019.
[102] A. Power, Y. Burda, H. Edwards, I. Babuschkin, and V. Misra, "Grokking: Generalization beyond overfitting on small algorithmic datasets," CoRR, vol. abs/2201.02177, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] We claim that our algorithm significantly outperforms QD environment generation algorithms. The claim supported by results and the statistical tests shown in Sec. 6.2
15

---

(b) Did you describe the limitations of your work? [Yes] We list the limitations of our work in Sec. g
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discuss the potential positive and negative impacts of this work in See. 7
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] We provide the code in the supplemental material for running all the experiments specified in Sec. 6 The code contains a README file with the instructions to reproduce the experiments.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The main details are presented Sec. Sec.5)and and Sec. Other details are provided in Appendix C and also available in the attached code.
(c) Did you report error bars (e.g., with respect to the random seed after rumning exper- iments multiple times)? [Yes] All results shown in Sec. 66.2 and Sec. 6.3. have the corresponding standard error and the inferences are supported by relevant statistical tests.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] We include the description of the computational resources used for the runs in Appendix C.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We have used existing open source code for the Mario simulator and the A agent, the Maze environment, and QD algorithm implementation. We have cited the creators either in Sec. [5] or in Appendix A. We obtained ACCEL agents directly from the original authors with their consent. We have cited the paper which introduced the algorithm and have acknowledged the authors for providing the pre-trained agents.
(b) Did you mention the license of the assets? [Yes] The licenses to the external code and assets are added to the README file in the code that we provide with the supplemental material.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] We include videos of the agent's playthrough in the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "wcU3JDPY72w", "reviewer": "Reviewer_KEnX", "summary": "This paper presents DSAGE, a new approach for generating environments that elicit diverse behaviors for a given agent. The authors consider two settings: 1) a maze environment using an RL agent and 2) Mario with an A* planner. In both cases, DSAGE does exactly as intended. In a set of comprehensive experiments the authors show that each individual component in DSAGE plays an important role, which will be helpful for future work. This paper could have a high impact as an approach for evaluating the robustness for RL agents, and thus I believe it is a useful contribution and should be presented at NeurIPS. ", "questions": "1. The environments considered are both 2D navigation tasks where DSAGE is essentially “landscaping”. Does this approach work for other settings such as continuous control of robotic environments?\n2. Hate to ask for experiments in the rebuttal, but, is it possible to include a random environment generation baseline (i.e. just Domain Randomization)? I would be curious to see how much variation in behavior occurs just using random samples. ", "limitations": "Limitations are discussed in Section 8. This meets the requirement.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\\+ The environments generated by DSAGE are qualitatively diverse, and watching the videos there are clearly some interesting settings that break both of the agents. This provides us with a greater understanding of their respective robustness. \n\n\\+ The experimental design is rigorous with many baselines and ablations.\n\n\\+ The work is on an important topic that is currently receiving significant interest. This work could have an elevated impact as a result.\n\n\\- I was hoping to see some sort of \"summary\" of the coverage/success of each agent with different regions of failure. For example, some way to analyze how much of the total environment space can be solved by an agent and what types of environments it typically does well/poorly on. It would be super interesting to then use this as a means to compare agents in the same environment. For example, how does ACCEL compare to other RL agents/planners such as PAIRED or A*? If DSAGE is capable of producing a summary like this, then that would increase its impact and I would move to a stronger accept.\n\nMinor:\n- I think the citation for MiniGrid is missing, which is the environment for the Maze experiments.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "uaQ4AqIaP22", "reviewer": "Reviewer_LA7A", "summary": "This paper proposes a sample-efficient QD environment generation algorithm that maintains a deep surrogate model for predicting agent behaviors in new environments. Results in two benchmark domains show that this method outperforms existing QD environment generation algorithms.", "questions": "See weakness 2", "limitations": "1. Not scalable to some tasks where the measure functions are inconvenient/impossible to define\n2. Need a pre-trained agent\n3. Need to compare with more baselines, e.g. PAIRED, ACCEL", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nClean method with experimental results and ablations to demonstrate the effectiveness of their method compared with QD baselines\n\nWeakness:\n1. Unclear presentation: \n    a. Figure 1 is confusing with many arrows and no starting point, while the illustration is not intuitive too\n    b. Undefined symbols and operations in pseudo-code, e.g. $y$, qd.ask, qd.tell\n2. Lack of efficiency analysis: the experimental results only show the evaluation of solutions, but not how many iterations to take in order to get these solutions.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "TBXbvWIa-FQ", "reviewer": "Reviewer_PfHr", "summary": "This paper accelerates the quality diversity procedure for environment generation by using a learned predictor rather than agent evaluations. They add auxiliary losses on occupancy measures to improve the prediction process and a downsampling procedure to decrease the number of candidates.  ", "questions": "- The agents are stochastic, why are the surrogate predictors deterministic? Would some of the challenges in prediction go away with a stochastic predictor?\n- Why would downsampling help with prediction accuracy as it appears to?", "limitations": "The authors adequately address the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n- This paper appears to be a real accelerator for QD algorithms and the authors carefully demonstrate that each component of the algorithm contributes to the improvement. The algorithm seems very useful.\n- The paper is very clearly written.\n\n### Weaknesses:\n- The paper is quite similar to a related work and the addition of an auxiliary prediction loss is not a huge novelty.\n\n### A few writing comments:\n- In line 138 I’m not sure that “ancillary agent behavior” is a phrase whose meaning is universally known and I’m not sure it was defined before this point? It’s explained in 152 but when I read it on 138 I didn’t understand at the moment and was just confused instead.\n- Perhaps I missed it but I didn’t see anywhere where $y$ was defined. I understand that it’s the ancillary but I don’t think that fact is in the paper except in algorithm 1.\n- The CMA-ES step seems to be missing from algorithm 1?\n- This is a personal preference but given that the method performing better than baselines is the point of the paper, the inclusion of the “hypothesis” in line 222 seems very unnecessary.\n- I think either Figure 7 or Table 1 from the supplement should be in the main paper, since improved prediction is one of the main contributions of the paper\n- The method seems similar to “Deep surrogate assisted MAP-Elites for automated hearthstone deckbuilding” which is acknowledged in the related work. There the differentiating claim is that that work applies prediction to the decks rather than the agent performance. In that case, it seems the differentiating factor of this work is a series of tools that enable these methods to work in the agent-based case (namely the ancillary information and the downsampling helping with prediction) rather than a new method. This is not super clear from the paper as it seems DSAGE-BASIC is essentially the method from the hearthstone paper? If these are the main differentiating factors, then more analysis of the impact of these tools should probably be in the main paper rather than in the supplement and claiming that a new algorithm has been constructed seems unnecessary. For example, that downsampling improved run-time by 4x is pretty neat and the speedup of the surrogate loop is worth mentioning!", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MBaQk90-XcP", "reviewer": "Reviewer_6K7J", "summary": "This paper addresses the problem of auto-generating RL environments. Classic environment generation methods could be slow due to expensive and time-consuming simulations. The authors proposed DSAGE, which leverages a surrogate model to predict the behaviors of an agent in new environments. The surrogate model is used to accelerate the generation of environments. The proposed DSAGE is evaluated on two benchmark domains and achieves better QD scores and coverage than the baselines. \n", "questions": "- Could the proposed approach scale to more complex environments beyond 2D grid-based maze and 2D Mario?   \n\n\n\n- How is the solution quality of the proposed method compared with the classic QD method that needs lots of simulation and long time? The reviewer expected there is a trade-off between solution quality and time. \n- Reporting the time needed for each method would be very helpful. \n- The symbol $\\hat{y}$, $\\hat{f}$, $\\hat{m}$ are undefined. \n- In figure 1, “CMA-ME” and the “Sample latent code” are not explained in the text, which is confusing. \n- The term “ancillary agent” is used throughout the paper without formal definition. It confuses the reviewer while reading the paper. \n- L 139 reads “The tell method adds the solution to the surrogate archive based on the predicted objective and measure values”. How exactly does the tell method add  solutions? Is there a threshold that is used to determine whether to add a solution or not?\n- The selection of the objective f and measures m seem critical. How do you make the selections? In addition, in more complex environments, the number of different measure functions may increase. How does the increased number of measure functions affect the performance of the proposed approach? ", "limitations": "The authors adequately addressed the limitations and potential negative impact in the paper. \n\n", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality  /  Significance:   \nExisting works that rely on QD require lots of simulations which are expensive and slow.  The ideal of using a surrogate model to predict the behavior of an agent and thus reduce simulation time is intriguing and reasonable. This is an interesting combination of behavior prediction and QD approaches.   \n\nQuality:  \nThe reviewer has some concern regarding the experimental results.   \n\n1.The author claims that the proposed DSAGE could accelerate the environment generation process. However, the claim is not supported by experimental results. In the experimental section, no speed information is reported. It would be helpful to compare the speed of the proposed DSAGE with baselines.   \n2.The author claims that diverse auto-generated environments could improve agent’s capability of generalizing to new environments. The claim is also not supported by experiments.   \n3. The proposed method is evaluated on two simple domains: grid-based maze and 2D Mario. It is unclear if the proposed approach could salce to more complex domains.   \n\nClarity:   \nThe reviewer is not an expert in environment generation but has expertise in RL. However, the reviewer found the paper somewhat difficult to follow. Improvements may be required. Please see the Question section for details.   \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept