Covariance Matrix Adaptation MAP-Annealing
Authors: Matthew Christopher Fontaine
Stefanos Nikolaidis
Venue: Submitted to ICLR 2023 (2023)
Keywords: quality diversity optimization
derivative-free optimization
latent space exploration

Abstract: Single-objective optimization algorithms search for the single highest-quality solution with respect to an objective. Quality diversity (QD) algorithms, such as Covariance Matrix Adaptation MAP-Elites (CMA-ME), search for a collection of solutions that are both high-quality with respect to an objective and diverse with respect to specified measure functions. However, CMA-ME suffers from three major limitations highlighted by the QD community: prematurely abandoning the objective in favor of exploration, struggling to explore flat objectives, and having poor performance for low-resolution archives. We propose a new quality diversity algorithm, Covariance Matrix Adaptation MAP-Annealing (CMA-MAE), that addresses all three limitations. We provide theoretical justifications for the new algorithm with respect to each limitation. Our theory informs our experiments, which support the theory and show that CMA-MAE achieves state-of-the-art performance.

COVARIANCE MATRIX ADAPTATION MAP-
Anonymous authors Paper under double-blind review
ABSTRACT
Singlc-objective optimization algorithms search for the single highest-quality so- lution with respect to an objective. Quality diversity (QD) algorithms, such as Covariance Matrix Adaptation MAP-Elites (CMA-ME), search for collection of solutions that are both high-quality with respect to an objective and diverse with respect specified measure functions. However, CMA-ME suffers from three major limitations highlighted by the QD community: prematurely abandoning the objective in favor of exploration, struggling explore flat objectives. and having poor performance for low-resolution archives. We propose new quality diver- sity algorithm, Covariance Matrix Adaptation MAP-Annelling (CMA-MAE), that addresses all three limitations. We provide theoretical justifications for the new al- gorithm with respect to each limitation. Our theory informs our experiments, which support the theory and show that CMA-MAE achieves ofte-of-the-art performance.
INTRODUCTION
Consider an example problem of searching for celebrity faces in the latent space of a generative model. As single-objective optimization problem, we specify an objective f that targets a celebrity such as Tom Cruise. A single-ohjective optimizer, such as CMA-ES (Hansen, 2016), will converge to single solution of high objective value, an image that looks like Tom Cruise as much possible.
However, this objective has ambiguity. How old was Tom Cruise in the photo? Did we want the person in the image to have short or long hair? By instead framing the problem optimization problem, we additionally specify a measure function mi that quantifies age and a measure function m2 that quantifies hair length. A quality diversity algorithm (Pugh et al. 2015 Chatzilygeroudis et al., 2021), , such as CMA-ME (Fontaine et al. 2020). can then optimize for a collection of images that diverse with respect age and hair length, but all look like Tom Cruise
quality diversity
While previous work (Fontaine et al. 2020 2021a b Earle et al. 2021 has shown that CMA-ME solves such QD problems efficiently, three important limitations of the algorithm have been discovered. First, on difficult to optimize objectives, variants of CMA-ME will abandon the objective too soon (Tjanaka et al. 2022), and instead favor exploring the measure space, the vector space defined by the measure function outputs. Second, the CMA-ME algorithm struggles to explore flat objective functions (Paolo et al. 202T). Third. CMA-ME works well on high-resolution archives, but struggles to explore low-resolution archives (Cully) 2021 Fontaine & Nikolaidis, (2011a). We note that the chosen archive resolution affects the performance all current QD algorithms.
We propose a new algorithm, CMA-MAE, that addresses these three limitations.
To address the first limitation, we derive an algorithm that smoothly blends between CMA-ES and CMA-ME. First, consider how CMA-ES and CMA-ME differ. At each step CMA-ES's ss objective ranking maximizes the objective function f by approximating the natural gradient of f at the current solution point (Akimoto et al. 2010). In contrast, CMA-ME's improvement ranking moves in the direction of the natural gradient of f - fA at the current solution point, where fA a discount function equal the objective of the best solution current solution point. The function f - fA quantifies the gap between a candidate solution and the best solution so far at the candidate solution's 's position in measure space.
far that has the same measure values as the
Our key insight is to anneal the function fA by a learning rate a. We observe that when a = 0, then discount function fA never increases and algorithm behaves like CMA-ES. However, when

---

0.0
0.01
Falor 1.01 fate 0.033
fata 0.0)
fA
SA
f SA
71
An example of how different a values affect the function f fA optimized by CMA-MAE after fixed number of iterations. Here f is a bimodal objective where mode X is harder to optimize than mode Y, requiring more optimization steps, and modes X and Y are separated by measure mi- For = 0, the objective / is equivalent to fA. as SA remains constant. For larger values of a, CMA-MAE discounts region Y favor of prioritizing the optimization of region X.
Figure 1:
1, then our discount function always maintains the best solution for each region in measure space and our algorithm behaves like CMA-ME. For 0 < a < 1, CMA-MAE smoothly blends between the two algorithms' behavior, allowing for an algorithm that spends more time on the optimization before transitioning to exploration. Figure is an illustrative example of varying the learning rate
Our proposed annealing method naturally addresses the flat objective limitation. Observe that both CMA-ES and CMA-ME struggle on flat objectives f as the natural gradient becomes 0 in this case and each algorithm will restart. However, we show that, when CMA-MAE optimizes f - fA for 0 1, the algorithm becomes descent method on the density histogram defined by the archive.
Finally, CMA-ME's poor performance on low resolution archives is likely caused by the non- stationary objective f f Sa changing too quickly for the adaptation mechanism keep up. Our archive learning rate a controls how quickly f - fA changes. We derive a conversion formula for that allows to derive equivalent for different archive resolutions. Our conversion formula guarantees that CMA-MAE is the first QD algorithm invariant to archive resolution.
Overall, our work shows how simple algorithmic change CMA-ME addresses all three major limitations affecting CMA-ME's performance and robustness. Our theoretical findings justify the aforementioned properties and inform our experiments, which show that CMA-MAE outperforms state-of-the-an QD algorithms and maintains robust performance across different archive resolutions.
2 PROBLEM DEFINITION
Quality Diversity. We adopt the quality diversity (QD) problem definition Fontainn & Nikolaidis (2021a). A QD problem consists of an objective f ; IR" + E that maps n-dimenssinal solution parameters scalar value denoting the quality of the solution and measures m, 8 - or, as a vector function, m R" > IR* that quantify behavior or attributes of each solution The range of m forms measure space S m [R... The QD objective find of solutions f R". such
that m m@0) = s for each s in S and f(0) is maximized.
The measure space is continuous, but solving algorithms need to produce finite collection of solutions. Therefore, QD algorithms in the MAP-Elites (Mouret & Clune 2015 Cully et al. 2015) family relax the QD objective by discretizing the space Given as the tessellation of S into M cells, the QD objective becomes to find solution 0; for each of the i E .l,...,M. .M) cells, such
that each Og maps to the cell corresponding to m m0;)) the tesselation T.. The QD objective then becomes maximizing the objective value f(t)) of all cells:
M
max
f(0))
The differentiable quality diversity (DQD) problem (Fontaine & Nikolaidis, 2021a) is special case of the QD problem where both the objective f and measures m, are first-order differentiable.
In agent-hased settings, such as reinforcement learning, the measure functions are sometimes called behavior functions and the outputs of cach measure function called behavioral characteristics behavior descriptors.
2

---

a 0.0
0,00001 0.001 0.1
1.0
CMA-ES
CMA-MAE
CMA-ME
Figure 2: Our proposed CMA-MAE algorithm smoothly blends between the behavior of CMA-ES and CMA-ME via an archive learning rate a. Each heatmap visualizes an archive of solutions across 2D measure space, where the color of each cell represents the objective value of the solution.
PRELIMINARIES
We present several QD algorithms that solve derivative-free QD problems to provide context for our proposed CMA-MAE algorithm. Appendix CMA-MEGA, which solves problems where exact gradient information is available.
[ Conttinns information about the DQD algorithm
MAP-Elites and MAP-Elites (line). The MAP-Elites QD algorithm produces an archive of solutions, where each cell in the archive corresponds to the provided tesselation T in the QD problem definition. The algorithm initializes the archive by sampling solutions from the solution space IR" from fixed distribution. After initialization, MAP-Elites produces new solutions by selecting occupied cells uniformly at random and perturbing them with isotropic Gaussian noise: O' 0, (0, I). For each new candidate solution 0', the algorithm computes an objective f(0") and measures m00)). MAP-Elites places 8' into the archive if the cell corresponding to m(0') is empty or obtains better objective value f(0') than the current occupant. The MAP-Elites algorithm results in archive of solutions that are diverse with respect to the measure function m. but also high quality with respect the objective f- Vassiliades & Mouret (2018) proposed the MAP-Elites (line) algorithm by augmenting the isotropic Gaussian perturbation with a linear interpolation between two solutions 0; and 0y: 0' 0; (0, 1) + (O, (); Oz).
CMA-ME. Covariance Matrix Adaptation MAP-Elites (CMA-ME) (Fontaine et al. 2020 combines the archiving mechanisms of MAP- with the adaptation mechanisms of CMA- Hansen (016)). Instead of perturbing archive solutions with Gaussian noise, CMA-ME maintains a multivarite Gaussian of search directions (0. Σ) and search point 0 R.. The algorithm updates the archive by sampling À solutions around the current search point 0; ~ NNO,, Σ). After updating the archive, CMA-ME ranks solutions via two stage ranking. Solutions that discover a new cell are ranked by the objective A; = f(O,), and solutions that map over the incumbent solution Oe that cell: A; = f(2,) -((0). CMA-ME prioritizes exploration by ranking all solutions that discover cell. Finally, CMA-ME moves towards the largest improvement in the archive, according to the CMA-ES update rules. FFotaane & Nikolaidis (2021a) showed that the improvement ranking of CMA-ME approximates natural gradient of a modified QD objective (see Eq. 1
occupied cell are ranked by the improvement
cell before all solutions that improve upon existing
PROPOSED ALGORITHMS
We present the CMA-MAE algorithm. While we focus CMA-MAF, the same augmentations apply to CMA-MEGA form the novel CMA-MAEGA algorithm (see Appendix DD}.
CMA-MAE. CMA-MAE is algorithm that adjusts the rate the objective f fA changes. First, consider at a high level how CMA-ME explores the measure space and discovers high quality solutions. The CMA-ME algorithm maintains a solution point 0 and archive A with previously discovered solutions. When CMA-ME samples a new solution 0', the algorithm computes the solution's objective value f(0') and maps the solution m00).. CMA-ME then computes the improvement of the objective value f(0') of the new solution, discount function fa R R. In CMA-ME, we define fx()') by computing the cell in
cell in the archive based on the measure
3

---

the archive corresponding to m(0) and letting fe f(ee), where 0. is the incumbent solution of cell e. The algorithm ranks candidate solutions by improvement f(0*) - fa((") = f(0') - f(ee) and moves the search in the direction of higher ranked solutions.
candidan
Assume that CMA-ME samples a new solution O' with a high objective value of f(0') = 99. If the current occupant Oe of the corresponding cell has low objective value of f(0z) 0.3, then the improvement in the archive A = f(0")= f(0e) = 98.7 is high and the algorithm will move the search point 0 towards O'. Now, assume that in the next iteration the algorithm discovers a new solution 0 with objective value f(0") = 100 that maps to the same cell as O'. The improvement as 0' replaced 0. in the archive in the previous iteration. CMA-ME
then is A f(0") f(0)) would likely move & away from 0" as the solution resulted in low improvement. In contrast, CMA-ES would move towards l as ranks only by the objective f. ignoring previously discovered solutions with similar measure values.
In the above example, CMA-ME moves away from high performing solutions in order to maximize how the archive changes. However, in domains with hard-to-optimizz objective functions, it is beneficial to perform more optimization steps in high-performing regions (Tjanaka et al., 2022). ).
Like CMA-ME, CMA-MAE maintains discount function LA (0") and ranks solutions by improve- ment f(0") - (0'). However, instead of setting fa(0" equal to f(O2), we set fO( = Le- where te is acceptance threshold maintained for each cell in the archive A. When adding candidate solution to the archive, we control the rate that le changes by the archive learning rate a as follows: (f')
te - attt at) +
The archive learning rate a in CMA-MAE allows us to control how quickly we leave a high- performing region of measure space. For example, consider discovering solutions in the same cell with objective value 100 in consecutive iterations. The improvement values computed by CMA-ME would be 100, O, O, O, O, thus CMA-ME would move rapidly away from this cell. The improvement values computed by CMA-MAE with a = 0.5 would diminish smoothly as follows: 100, 50, 25, 12.5, 6.25, enabling further exploitation of the
region.
Next, we walk through the CMA-MAE algorithm step-by-step. Algorithm shows the pseudo-code for CMA-MAE with the differences from CMA-ME highlighted in yellow. First, on line 2 we initialize the acceptance threshold to min/. In each iteration we sample À solutions around the current search point (line|5.. For each candidate solution 0₁. we evaluate the solution and compute the objective value f(fz) and measure values m0=)) (line 6). Next, we compute the cell in the archive that corresponds to the measure values and the improvement A; over the current threshold te (lines] 7 8
If the objective crosses the acceptance threshold t.. we replace the incumbent Oe Next, we rank all candidate solutions 0g by their improvement A, Finally, we step our search point 0 and adapt our covariance matrix Σ towards the direction of largest improvement (lines 14 15 according to CMA-ES's s update rules (Hansen 2016).
in the archive and increase the acceptance threshold te (lines 9
CMA-MAEGA. We note that our augmentations to the CMA-ME algorithm only affects how we replace solutions in the archive and how calculate A, CMA-ME: and CMA-MEGA replace solutions and calculate A identically, so we apply the same augmentations to CMA-MEGA to form a new DQD algorithm, CMA-MAEGA, in Appendix D
THEORETICAL PROPERTIES OF CMA-MAE
We provide insights about the behavior of CMA-MAE for different a values. We include all proofs in Appendix E CMA-MAEGA has similar theoretical properties discussed in Appendix IF
Theorem 5.1. The CMA-ES algorithm is equivalent to CMA-MAE when = 0, if CMA-ES restarts from an archive solution.
The next theorem states that CMA-ME is equivalent to CMA-MAE when a = 1 with the following caveats: First, we assume that CMA-ME restarts only by the CMA-ES restart rules, rather than the additional "no improvement" restart rule in prior work (Fontaine et al.) 2020). Second, we assume that both CMA-ME and CMA-MAE leverage μ selection (Hansen 2016) rather than filtering selection Fontaine et al. 2020).
4

---

Algorithm I Covariance Matrix Adaptation MAP-Annealing (CMA-MAE)
CMA-MAE (evaluate, Po. N, X, o, minf.a)
input :An evaluation function evaluate that computes the objective and measures, an initial solution 0g desired number of iterations N, a branching population size X, an initial step size d, a minimal acceptable solution quality min,, and an archive learning rate a. result:Generak N solutions storing elites in an archive A.
Initialize solution parameters 0 to Oo. CMA-ES parameters = and p. where we let p be the CMA-ES internal parameters.
Initialize the archive A and the acceptance threshold t. with miny for each cell e.
for iter <- N do
for i --111 1 to À do
0: ~ ~N,,
f,m evaluate(O,))
e - calculate caaluulate_cel(AA.. cel m)
A f
f > te then
Replace the current occupant in cell e of the archive A with 0₃
te - (1-a)t + af
end
13
end
14
rank O, by A
15
Adapt CMA-ES parameters 0, E.p based on improvement ranking A if CMA-ES converges then Restart CMA-ES with Σ = ol.
16
17
Set 0 to a randomly selected existing cell O; from the archive
end 19
20
end
Theorem 5.2. The CMA-ME algorithm is equivalent to CMA-MAE when a 1 and miny is an arbitrarily large negative number.
We next provide theoretical insights on how the discount function fA smoothly increases from constant function min, to the discount function used by CMA-ME, as increases from 0 to 1. We focus on the special case fixed sequence of candidate solutions.
Theorem 5.3. Let a; and oi be two archive learning rates for archives A; and Aj such that S a, a S For two runs of CMA-MAE that generate the same sequence of m candidate solutions {S} 0,, O2, .... Om follows that SA, (0) S S'A, (0) all 0 E IR"
Finally, we wish to provide insights about the exploration properties of CMA-MAE for archive learning rate between 0 and I, when the objective f is constant. Consider an approximate density descent algorithm that identical to CMA-ME, but differs by how solutions are ranked. Specifically, we assume that this algorithm maintains a density histogram of the occupancy counts o, for each cell e, with og representing the number of times a solution was generated that cell. This algorithm descends the density histogram by ranking solutions based the occupancy count of the cell that the solution maps to, where solutions that discover less frequently visited cells are ranked higher.
Theorem 5.4. The CMA-MAE algorithm optimizing constant objective function f() C for all R is equivalent to the approximate density descent algorithm, when a < and min, C.
While Theorem 5.4 assumes constant objective J, we conjecture that the theorem holds true generally when threshold I, each cell approaches the local optimum within the cell boundaries.
EXPERIMENTS
We compare the performance of CMA-MAE with the tftt--of-the-rr QD algorithms MAP-Elites, MAP-Elites (line), and CMA-ME, using existing Pyribs (Tjanaka et al. 202T) QD library imple- mentations. We 0.01 for CMA-MAE and include additional experiments for varying
5

---

LP (ophere)
LP (Rastrigin)
LP ((plateuu)
Arm Repertoire
LSI
Algorithm
QD-score
Coverage
QD-sccore
Coverage
QD~score
Coverage
QD>score
Coverage
QD~4core
Coverage
MAP-Elites
41.64
50.80%
31.43
88%
47.07
47.07%
71,40
14.09%
12.85
19,42%
MAP-Elites (linc)
19.07
60.42%
38. 38.29
56.51%
52.20
52.20%
74.55
75.61%
14.40
21.11%
CMA-ME
36.50
42.
38,
53.09%
34.54
75.89%
19.57%
CMA-MAE
64.86
83.31%
52.65
80.46 %
79.27
79.29 %
79.03
79.24%
17.67
25.08%
Table
Mean QD-score and coverage values after 10,000 iterations for each algorithm per domain.
in section] 7 Because annealing methods replace solutions based on the threshold, we retain the
best solution each cell for comparison purposes. We include additional comparisons between
CMA-MEGA and CMA-MAEGA - the gradient-based counterpart of CMA-MAE - in Appendix K
We select the benchmark domains from Fontaine & Nikolaidis 2021a): linear projection (Fontaine et al. 2020), arm repertoire (Cully & Demiris 2017). and latent space illumination (Fontaine et al. 2021bb. To evaluate the good exploration properties of CMA-MAE on flat objectives, we introduce variant of the linear projection domain to include a "plateau" objective function that is constant everywhere for solutions within fixed range and has a quadratic penalty for solutions outside the range. We describe the domains in detail in Appendix B
6.1 EXPERIMENT DESIGN
Independent Variables. We follow a between-groups design with two independent variables: the algorithm and the domain.
Dependent Variables. We use the sum of f values of all cells in the archive, defined as the QD-score Pugh et al. (2015), as a metric for the quality and diversity of solutions. Following Fontaine Fontannnggootaanc & Nikolaidis (2021a), we normalize the QD-score metric by the archive size (the total number of cells from the tesselation of measure space) to make the metric invariant to archive resolution. We additionally compute the coverage, defined the number of occupied cells in the archive divided by the total number of cells.
6.2 ANALYSIS
Table showws the QD-score and coverage values for each algorithm and domain, averaged over 20 trials for the linear projection (LP) and repertoire domains and over 5 trials for the LSI domain. Fig. 3 shows the QD-score values for increasing number of iterations and example archives for CMA-MAE and CMA-ME, with 95% confidence intervals.
We conducted a two-way ANOVA to examine the effect of the algorithm and domain (LP (sphere),
LP (Rastrigin), LP (plateau), arm repertoire, and LSI) on the QD-score. There was a significant interaction between the search algorithm and the domain (F(12, 320) = 1958.344 34, p < 0.001). Simple main effects analysis with Bonferroni corrections showed that CMA-MAE outperformed all baselines in all benchmark domains.
For the arm repertoire domain, we can compute the optimal archive coverage by testing whether each cell overlaps with circle of radius equal to the maximum arm length (see Appendix [B). We observe that CMA-MAE approaches the computed optimal coverage 00.24% for a resolution of 100 x 100 and outperforms CMA-MEGA (Fontaine & Nikolaidis 2021a) (see Appendix K).
These results show that the archive learning rate a is particularly beneficial for CMA-MAE. We observe that CMA-MAE initially explores regions of the measure space that have high-objective values. Once the archive becomes saturated, CMA-MAE reduces to approximate density descent, we prove in Theorem 5.4] flat objectives. On the other hand, CMA-ME does not receive any exploration signal when the objective landscape becomes flat, resulting in poor performance.
While our results show improved quantitative results the LSI domain, Appendix discusses how to improve the visual quality by leveraging techniques from the generative art community. Fig. 4 shows example collage generated by adopting improvements for guiding StyleGAN with CL.IP.

---

CMA-MAE
100
65
QD-Score
CMA-MAE CMA-ME MAP-Elites (line)
MAP-Elites
5000 Iterations
10000
CMA-ME
100
80
QD-Score
5000 Iterations
10000
CMA-ME
100
QD-Score
5000
10000
Iterations
Figure 3: QD-score plot with 95% confidence intervals and heatmaps of generated archives by CMA-MAE and CMA-ME for the linear projection sphere (top), plateau (middle), and arm repertoire (bottom) domains. Each heatmap visualizes archive of solutions across 2D measure space.
LP (sphere)
LP (Rastrigin)
LP (plateau)
Arm Repertoire
(CMA-MAE)
QD-ccore
Coverage
QD-scare
Coverage
QD-score
Coverage
QD-score
Coverage
0.000
5.82
6.06%
5.33
6.24%
19.49
19.49%
65.91
66.25%
0.001
62.65
79.36%
47.87
68. 10%
77.60
77.68%
78.63
79.07%
0.010
64.86
83.31 %
52.65
80.56%
79.27
79.29%
79.03
79.24%
0.100
60.42
76.19%
48.74
72.50%
83.21
83.21
78.74
78.85%
1.000
37.01
43.50%
37.86
52.82%
34.00
34.00%
75.94
76.01%
Table 2: Mean QD metrics after 10,000 iterations for CMA-MAE at different learning rates.
7 ON THE ROBUSTNESS OF CMA-MAE
Next, we present two studies that evaluate the robustness of CMA-MAE across two hyperparameters that may affect algorithm performance: the archive learning and the archive resolution.
7

---

0.11
0.07
0.04
Hair Length.
-0.04
-0.07
-0.1 0.11
-0.07
0.0
0.04
0.07
Age. Figure 4: A latent space illumination collage for the objective "A photo of the face of Tom Cruise." " with hair length and age measures. See Appendix for more detail.
Linear Projection (sphere) Linear Projection (Rastrigin)
Linear Projection (plateau)
Repertoire
85
QD-Score
CMA MAA-MAE
CMA-ME
MAP Elites (ino)
MAP-Elltes
50
Resolution
500
0
Resolution
500
Resolution
500
50
Resolution
500
Figure 5: Final QD-score of each algorithm for 25 different archive resolutions.
Archive Learning Rate. We examine the effect of different archive learning rates the performance of CMA-MAE in the linear projection and arm repertoire domains. We vary the learning rate from on exponential scale, while keeping the resolution constant in each domain.
Table 2 shows that running CMA-MAE with the different < a < results in relatively similar performance, showing that CMA-MAE is fairly robust to a values. On the other hand, if a 0 or = 1 the performance drops drastically. Setting a results in very similar performance with CMA-ME, which supports our insight from Theorem 5.2
Archive Resolution. As noted by Cully 2222 and Fontaine & Nikolaidis (22 20)1a). quality diversity algorithms in the MAP-Elites family sometimes perform differently when run with different archive resolutions. For example, in the linear projection domain presented in Fontaine et al. (2020). CMA-ME outperformed MAP-Elites and MAP-Elites (line) for archives of resolution 500 x 500, while in this paper we observe that it performs worse for resolution 100 100. In this study, we investigate how CMA-MAE performs at different archive resolutions.
First, we note that the optimal archive learning rate is dependent on the resolution of the archive. Consider as an example a sequence of solution additions to two archives Ai and Ag of resolution 100 x 100 and 200 x 200, respectively. A₂ subdivides each cell in A₁ into four cells, thus archive Ay's 's thresholds t. should increase a four times faster rate than Aj. To account for this difference, compute ag for Ag via conversion formula a2 where r the ratio cell counts between archives A, and Az. We initialize aj = 0.01 for A, In the above example, 02 (1 0.01)* 0.0394.
(1 a1)" (see derivation in Appendix G
8

---

Fig. 5 shoows the QD-score of CMA-MAE with the cusolution-dependeee archive learning rate and the baselines for each benchmark domain. CMA-ME performs worse as the resolution decreases because the archive changes quickly at small resolutions, affecting CMA-ME's adaptation mechanism. On the contrary. MAP-Elites and MAP-Elites (line) perform worse as the resolution increases due to having more elites to perturb. CMA-MAE's performance is invariant the resolution of the archive.
RELATED WORK
Quality Diversity Optimization. The predecessor to quality diversity optimization, simply called di- versity optimization, originated with the Novelty Search algorithm (Lehman & Stanley 20),a), which searches for collection of solutions that are diverse in measure space. Later work introduced the Novelty Search with Local Competition (NSLC) (Lehman & Stanley 1b) and MAP-Elites (Cully et al., 2015 Mouret & Clune, 2015) algorithms, which combined single-objective optimization with diversity optimization and were the first QD algorithms. Since then, several QD algorithms have been proposed, based variety of single-objective optimization methods, such Bayesian optimization (Kent & Branke 2020), evolution strategies (Conti et al., 20188 Colas et al.) 2020
Fontaine al. (2020), differential evolution (Choi & Togelius [202]). Togeli and gradient ascent (Fontaine
& Nikolaidis 202la). Several works have improved selection mechanisms (Slikas et al. 202 2021|Cully
& Demiris 2017). archives (Fontaine et al. 2019 Vassiliades et al.
2018: Smith al. 2016). and 2018).
perturbation operators (Vassiliades & Mouret 2018 Nordmoen et al.
QD with Gradient Information. Several works combine gradient information with quality diversity optimization in ways that do not leverage the objective and measure gradients directly. For example, in model-based quality diversity optimization (Gaier et al. 2018 Hagg et al.) 2020 Cazenille et al.,
2019; Keller et al., 2020 Lim et al., 2021: Zhang et al. |021] Gaier et al. (020)) Rakicevic et al.
(2021 trains an autoencoder on the archive of solutions and leverages the Jacobian of the decoder
network to compute the covariance of the Gaussian perturbation. In quality diversity reinforcement learning (Q-RL), several works [Parker-Holder et al. 2020; Pierrot et al.) [2200] Nilsson & Cully)
2021 Janaka et al., 2022) approximate reward gradient diversity gradient via critic network, action space noise, or evolution strategies and incorporate those gradients into a QD-RL algorithm.
Acceptance Thresholds. Our proposed archive learning rate a loosely inspired by simulated annealing methods (Bertsimas & Tsitsiklis) 1993) that maintain an acceptance threshold that gradually becomes more selective the algorithm progresses. The notion of an acceptance threshold is also closely related to minimal criterion methods in evolutionary computation (Lehman & Stanley 2010 Brant & Stanley 2017; / 2020; [ttanley et al., 2016). Our work differs by both 1) maintaining an acceptance threshold per archive cell rather than a global threshold and 2) annealing the threshold.
9 LIMITATIONS AND FUTURE WORK
Our approach introduced two hyperparameters, a and miny, to control the rate that f f fA changes. We observed that an set strictly between 0 and yields theoretical exploration improvements and that CMA-MAE is robust with respect to the exact choice of a. We additionally derived a conversion formula that converts an ai for specific archive resolution to an equivalent ag for different resolution. However, the conversion formula still requires practitioners to specify a good initial value of a1 Future work will explore ways automatically initialize a, similar how CMA-ES automatically assigns internal parameters (Hansen 2016).
Quality diversity optimization is a rapidly growing branch of stochastic optimization with applications in generative design (Hagg et al., [221]] Gaier et al. [2020] 2018).
automatic scenario generation
in robotics (Fontaine & Nikolaidis! [201c]] Fontaine et al.) 2021a
Fontaine & Nikolaidis) 202Tb).
reinforcement learning (Parker-Holder et al. 2020
Pierrot et al.
2020; Nilsson & Cully 2021
Tjanaka et al.) 2022), damage recovery in robotics
(Cully et al.
2015). and procedural content
generation (Gravina et al. 22019; Fontaine et al., 2021b Zhang et al.
2021 Earle et al. 202 Khalifa
et al. 2018 Steckel & Schrum 2001: Schrum et al. 2020 Sarkar & Cooper] [022] Bhatt et al.
2022 Our paper introduces new quality diversity algorithm, CMA-MAE. Our theoretical findings
inform our experiments, which show that CMA-MAE addresses three major limitations affecting the
CMA-ME algorithm, leading to state-of-the-arr performance.
9

---

10 ETHICS STATEMENT
By controlling the trade-off between exploration and exploitation in QD algorithms,, we aim towards improving their performance and robustness, thus making these algorithms easier to apply in a wide range of domains and applications. One promising application is synthetically extracting datasets from generative models to train machine learning algorithms JJahanian et al. (202T); Besnier et al.) (2020). This can raise ethical considerations because generative models can reproduce and exacerbate existing biases in the datasets that they were trained on (Jain et al., 2020. Menon et al., 2020). On the other hand, quality diversity algorithmms with carefully selected measure functions diversity with desired attributes, thus we hypothesize that they can be effective in generating balanced datasets. Furthermore, by attempting to find diverse solutions, QD algorithms
target
step towards open-endednesss in Stanley et al.] (017) and will often result in unexpected and often surprising emergent behaviors (Lehman et al., 2020). We recognize that this presents several challenges in predictability and monitoring of Al systems (Hendrycks et al. 202T), and we highlight the importance of future work on balancing the tradeoff between open- endedness and control (Ecoffet al., 2020).
11 REPRODUCIBILITY STATEMENT
In the supplemental material we provide complete source code for all algorithms and experiments, as well as the Conda environments for installing project dependencies. The "README.md document provides complete instructions both setup and execution of all experiments. In Appendix [ we provide all hyperparameters. In Appendix B we provide domain-specific details for replicating all experimental domains. In Appendix C we provide information about the computational resources and hardware we used to run our experiments. In Appendix
D we provide the pseudocode for the CMA algorithm, the DQD counterpart of CMA-MAÉ. In Appendix E we provide the proofs of all theorems in the paper. Appendix [F] we provide the theoretical properties of CMA-MABGA. In Appendix G we provide the derivation of the conversion formula for the archive learning rate. In Appendix we provide a batch threshold update rule that is invariant to the order that the solutions are processes within batch update. In Appendix [ we discuss the implementation details for additional experiments that improve the quality of the generated images in the latent space illumination domain. In Appendix K we present all metries with standard errors for each algorithm and domain.
[H]
REFERENCES
Youhei Akimoto, Yuichi Nagata, Isao Ono, and Shigenobu Kobayashi. Bidirectional relation between ema evolution strategies and natural evolution strategies. In International Conference on Parallel Problem Solving from Nature, pp. 154 163. Springer, 2010.
Dimitris Bertsimas and John Tsitsiklis. Simulated annealing. Statistical science, 8(1):10-15, 1993.
Victor Besnier, Himalaya Jain, Andrei Bursuc, Matthieu Cord, and Patrick Pérez. This dataset does not exist: training models from generated images. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5. IEEE, 2020.
Varun Bhatt, Bryon Tjanala, Matthew Fontaine, and Stefanos Nikolaidis. Deep surrogate assisted generation of environments. Advances in Neural Information Processing Systems, 2022.
Jonathan C Brant and Kenneth O Stanley. Minimal criterion cocvolution: a new approach to open pedeee search. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 67-74, 2017.
Jonathan C Brant and Kenneth O Stanley. Diversity preservation in minimal criterion coevolution through resource limitation. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 58-66, 2020.
Leo Cazenille, Nicolas Bredeche, and Nathanael Aubert-Kato. Exploring self-assembling behaviors in of bio-micro-robots using surrogate-asse map-elites. 2019 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 238-246. IEEE, 2019.
Konstantinos Chatzilygeroudis, Antoine Cully, Vassilis Vassiliades, and Jean- optimization: novel branch of stochastic optimization. In Black Box Optimization, Machine Learning, and No-Free Lunch Theorems, pp. 109-135. Springer, 2021.
Jean-Baptist Baptiste Mouret. Quality-diverse
10

---

Tae Jong Choi and Julian Togelius. Self-Referential Quality Diversity through Differential MAP-Elites, pp. 502 509, Association for Computing Machinery, New York, NY, USA, 2021. ISBN 9781450383509 URL https: http://t..........1111..
org //0 11tg//...11/334493313.33 3459388
Cédric Colas, Vashisht Madhavan, Joost Huizinga, and Jeff Clune. Scaling map-elites to deep neuroevolution. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 67-75, 2020.
Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforeement learning via a population of novelty- seeking agents, Advances in neural information processing systems, 31, 2018.
Katherine Crowson, Stella Biderman, Daniel Kornis, Dashiell Stander, Eric Hallahan, Louis Castricato, and Edward Raff. Vggan-clip: Open domain image generation and editing with natural language guidance, arXiv preprint arXiv:2204.0858: 2022.
Antoine Cully. Multi-emitter map-elites: improving quality, diversity and data efficiency with heterogeneous sets of emitters. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 84 92, 2021.
Antoine Cully and Yiannis Demiris. Quality and diversity optimization: A unifying modular framework. IEEE Transactions on Evolutionary Computation, 22(2))245-25) 2017.
Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret. Robots that can adapt like animals. Nature, 521(7553)5503, 2015.
Sam Earle, Justin Snider, Matthew C Fontaine. Stefanos Nikolaidis, and Julian Togelius. Illuminating diverse neural cellular automata for level generation. arXiv preprint 1XXi:2109.05488 2021.
Adrien Ecoffet, Jeff Clune, and Joel Lehman. Open questions in creating safe open-ended ai: tensions between control and creativity. arXiv preprint arXiv:2006.025 07495, 2020.
Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Suciety, 29(4):983-1049, 2016.
Matthew Fontaine and Stefanos Nikolaidis, Differentiable quality diversity. Advances Neural Information Processing Systems, 34, 2021a.
Matthew Fontaine and Stefanos Nikolaidis. A quality diversity approach automatically generating human-robot interaction scenarios in shared autonomy. Robotics: Science and Systems, 2021b.
Matthew Fontaine, Sophie Hsu, Yulun Zhang, Bryon Tjanaka, and Stefanos Nikolaidis. On the importance of environments in numan-robot coordination. Robotics: Science and Systems (RSS), 2021a.
Matthew C. Fontaine and Stefanos Nikolaidis. Evaluating human-robot interaction algorithms in shared autonomy via quality diversity scenario generation. International Journal of Human--Rbot Interaction, jul 2021c, doi: 10. 10.1444/3476412. URL /tttps://dddtt htt. oro. 145/3476414
Matthew C Fontaine, Scott Lee, Lisa B Soros, Fernando de Mesentier Silva. Julian Togelius, and Amy K. Hoover. Mapping hearthstone deck spaces through map-elites with sliding boundaries. In Proceedings of The Genetic and Evolutionary Computation Conference, pp. 161-169, 2019.
Matthew C Fontaine, Julian Togelius, Stefanos Nikolaidis, and Amy K Hoover. Covariance matrix adaptation for the rapid illumination of behavior space. In Proceedings of the 2020 genetic and evolutionary computation conference, pp. 94- 2020.
Matthew C Fontaine, Ruilin Liu, Julian Togelius, Amy K Hoover, and Stefanos Nikolaidis. Illuminating mario scenes in the latent space of generative adversarial network. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021b.
Kevin Frans, LB Soros, and Olaf Witkowski. Clipdraw: Exploring text-to-drawing synthesis through language- image encoders. arXiv preprint arXiv:2 14843, 2021.
Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret. Data-efficient design exploration through surrogate- assisted illumination. Evolutionary computation, 26(3):381-410 2018.
Adam Gaier, Alexander Asteroth, and Jean-Baptiss Mouret. Discovering representations for black-bor opti- mization. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, GECCO '20, pp. 103-111, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 3781450371288 doi: 10. 00.1145/3379930339922
URL htt.ttttss:////tttttt //ottss://di... http:////w........00111//////3//

---

Ronald Graham, Donald E Knuth, Oren Patashmik, and Stanley Liu. Concrete mathematics: foundation for computer science. Computers in Physics, 3(5):106-100 1989.
Danicle Gravina, Ahmed Khalifa, Antonios Liapis, Julian Togelius, and Georgios N Yannakakis. Procedural content generation through quality diversity. In 2019 IEEE Conference on Games (CoG), pp. 1-8. IEEE, 2019.
Alexander Hagg, Dominik Wilde, Alexander Asteroth, Thomas Bäck. Designing air flow with surrogate- assisted phenotypic niching. International Conference on Parallel Problem Solving from Nature, pp. 140-153. Springer, 2020.
Alexander Hagg, Scbastian Berns, Alexander Asteroth, Simon Colton, and Thomas Bäck. Expressivity of
parameterized and data-driven representations in quality diversity search. In Proceedings of the Genetic and
Evolationary Computation Conference, GECCO '21, pp. 678-686 New York, NY. USA, 2021. Association for Computing Machinery. ISBN 9781450383509. doi: 10. 444444449999934592877
(tRps:tt:: //coi
org//0. 110.011445334333 3459287
N. Hansen, A. Auger, O. Mersmann, T. Tusar, and D. Brockhoff. Coco: A platform for comparing continuous optimizers a black-box setting. 2016.
Nikolaus Hansen. The cma evolution strategy: A tutorial. arXiv preprint arXiv:1604.0077: 2016.
Nikolaus Hansen and Andreas Ostermeier: Convergence properties of evolution strategies with the derandomized covariance matrix adaptation: The (/i.)-cs. Eigir, 97:650- 654, 1997.
Nikolaus Hansen. Sibylle D Müller, and Petros Koumoutsakos. Reducing the time complexity of the derandom- ized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary computation, 11(1):1-18. 2003.
Nikolaus Hansen, Anne Auger, Raymond Ros, Steffen Finck, and Petr Pošík. Comparing results of 31 algorithms from the black-box optimization benchmarking bbob-2009, pp. 1689-16999 1696, 07 2010. doi: 10.1145/183076.. 1830790.
Dan Hendrycks, Nicholas Carlini, John Schulman, and Jacob Steinhardt. Unsolved problems in safety, arXiv preprint 1rXiv:2109.1330 13916, 2021.
Ali Jahanian, Xavier Puig, Yonglong Tian, and Phillip Isola. Generative models as data source for multiview representation learning. arXiv preprint (xXiv:2106.05220 2021.
Niharika Jain, Alberto Olmo, Sailik Sengupta, Lydia Manikonda, and Subbarao Kambhampati. Imperfect imaganation: Implications gans exacerbating biases on facial data augmentation and snapchat selfie lenses. arXiv preprint arXiv:2001.00522 2020.
Norman L Johnson, Samuel Kotz, and Narayanaswamy Balakrishnan. Continuous univariate distributions, volume 2, volume 289. John wiley & sons, 1995.
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 1401-4410, 2019.
Tero Karras, Miik Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Training generative adversarial networks with limited data. In Proc. NeurlPS, 2020a.
Tero Karras, Samuli Laine, Miika Aittala, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. Analyzing and improving the image quality of stylegan. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), June 2020b.
Tero Karras, Miika Aittala, Samuli Laine, Erik Härkönen, Janne Hellsten, Jaakko Lehtinen, and Timo Aila. Alias-free generative adversarial networks. In Proc. NeurlPS, 2021.
Leon Keller, Daniel Tanneberg, Svenja Stark, and Jan Peters. Model-base quality-diversin search for efficient robot learning. 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 9675-9680, 2020.
Paul Kent and Juergen Branke, Bop-clites, bayesian optimisation algorithm for meality-diversity search. arXiv preprint arXiv:2005.0 04320, 2020.
Ahmed Khalifa, Scott Lee, Andy Nealen, and Julian Togelius. Talakat: Bullet hell generation through constrained map-elites. In Proceedings of The Genetic and Evolutionary Computation Conference, pp. 1047-1054, 2018.
12

---

Dynamics-aware quality-diversity for Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Joel Lehman and Kenneth O Stanley. Revising the evolutionary computation ahstraction: minimal criteria novelty search. Proceedings of the 12th annual conference on Genetic and evolutionary computation, pp- 103-110, 2010.
Joel Lehman and Kenneth O Stanley. Abandoning objectives: Evolution through search for novelty alone. Evolutionary computation, 19(2):18-222 2011a.
Joel Lehman and Kenneth Stanley. Evolving diversity virtual creatures through novelty search and local competition. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, pp. 211-218, 201
Joel Lehman, Jeff Clune, Dusan Misevic, Christoph Adami, Lee Altenberg, Julie Beaulieu, Peter Bentley, Samuel Bernard, Guillaume Beslon, David M Bryson, et al. The surprising creativity of digital evolution: A collection of anccdotes from the evolutionary computation and artificial life research communities. Artificial life, 26(2))274-306 2020.
Bryan Lim, Luca Grillotti, Lorenzo Bernasconi, and Antoine Cully. efficient learning of skill repertoires. ArXiv, 209.0222000222, 2021.
Bryan Lim, Maxime Allard, Luca Grillotti, and Antoine Cully. Accelerated
for robotics through
massive parallelism. In ICLR Workshop on Agent Learning in
2022.
Sachit Menon, Alexandru Damian, Shijia Hu, Nikhil Ravi, and Cynthia Rudin. Pulse: Self-supervised photo upsampling via latent space exploration of generative models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2437-2445, 2020.
Caan-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. 1504v 2015.
arXiv preprint
Olle Nilsson and Antoine Cully. Policy gradient assisted map-elites. Proceedings of the Genetic and Evolutionary Computation Conference, 2021.
Jørgen Nordmoen, Eivind Samuelsen, Kai Olav Ellefsen, and Kyrre Glette. Dynamic mutation map-elites for robotic repertoire generation. In Artificial Life Conference Proceedings, pp. 598-605. MIT Press, 2018.
Giuseppe Paolo, Alexandre Coninx, Stéphane Doncieux. and Alban Laflaquière. Sparse reward exploration via novelty search and emitters. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 154-162, 2021.
Jack Parder-Holder, Aldo Pacchiano, Krzysztof M Choromanski, and Stephen Roberts. Effective diversity in population based reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 18050- 18062. Curran Associates, Inc., 2020. URL https: /ttp:////cocccc....///...oo www.singn.........eeee www.ips....... wwwpeepp/pppppeeeeeeeeeeeee..eat Satppperr/22///11 2020/
#1d:3as270a6E394488888 (Ow.://----
Victor Perez. Generating images from prompts using clip and stylegan, 2021.
URL https://
lowardsdatascienne. com/
MIT License.
Thomas Pierrot, Valentin Macé, Geoffrey Cideron, Karim Beguir, Antoine Cully, Olivier Sigaud, and Nicolas Pelrin-Gilbert. Diversity policy gradient for sample efficient quality-diversity optimization. arXiv e-prints, pp. arXiv-2006, 2020.
Justin K Pugh, Lisa B Soros. Paul A Szerlip. and Kenneth O Stanley. Confronting the challenge of quality diversity. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 967-974, 2015.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and llya Sutskever. Learning transferable visual models from natural language supervision. In Proceedings of the 38th International Conference on Machine Learning ICML 2021, 2021.
Nemanja Rakicevic, Antoine Cully, and Petar Kormushev. Policy manifold search: Exploring the manifold hypothesis for diversity- based neuroevolution. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO '11, pp. 901-909, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 47814533335 doi: 10. 145/3449939.3459922
13

---

Anurag Sarkar and Seth Cooper. Generating and blending game levels via quality-diversity in the latent space of variational autoencoder. arXiv preprint arXiv:2102.1244 12466, 2021.
Jacob Schrum, Vanessa Volz, and Sebastian Risi. Cppn2gan: Combining compositional pattern producing networks and gans large-scale pattern generation. Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pp. 139-147, 2020.
Konstantinos Sfikas, Antonios Liapis, and Georgios Yannakakis. Monte carlo elites: Quality- selection as a multi armed bandit problem. In Proceedings of the Genetic and Evolutionary Computation Conference. GECCO '21, pp. 180- 188, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781-4033315000 doi: 10. 011144444499994559933
URl http::tttss..cp...... //oii wrw.10...o......... /10. 100.001115//3493330
3459321
Davy Smith, Laurissa Tokarchuk, and Geraint Wiggins. Rapid phenotypie landscape exploration through hierarchical spatial partitioning. In International conference parallel problem solving from nature, pp- 911-920. Springer, 2016.
Kenneth O Stanley, Nick Cheney, and LB Soros. How the strictness of the minimal criterion impacts open-ended evolution. ALIFE 2016, the Fifteenth International Conference on the Synthesis and Simulation of Living Systems, pp- 208-215 MIT Press, 2016.
Kenneth Stanley, Joel Lehman, and Lisa Soros. Open-endedness: The last grand challenge you've 'v never heard of. While open-endedness could be force for discovering intelligence, it could also be component of Al itself. 2017.
Kirby Steckel and Jacob Schrum. Illmiiatiing the space of beatable lode runner levels produced by various generative adversarial networks. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '21, pp. 111-112, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781453335166 doi: 10.1145/3449726.344 3459440
URL bttps:/::///ol wrg.:/oo..rrggo/ 1114/1100.14444472225
Bryon Tjanaka, Matthew C. Fontaine. Yulun Zhang, Sam Sommerer, Nathan Dennler, and Stefanos Niko- laidis. pyribs: A bare-bones python library for quality diversity optimization, https://githh: com/ icaros-use scaros-usc/pyribg. 2021.
Bryon Tjanaka, Matthew C Fontaine, Julian Togelius, and Stefanos Nikolaidis. Approximating gradients for differentiable quality diversity in reinforcement learning. GECCO, 2022.
Vassilis Vassiliades and Jean-Baptee Baptiste Mouret. Discovering the elite hypervolume by leveraging interspecics correlation. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 149- 156, 2018.
Vassilis Vassiliades, Konstantinos Chatuily and Jean-Baptiste Mouret. Using centroidal voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm. IEEE Transactions on Evolutionary Computation, 22(4):623-66 630, 2018. doi: 10. 10.1109/EVV.2201..22233
Yulun Zhang, Matthew C Fontaine, Amy K Hoover, and Stefanos Nikolaidis. Deep surrogate assisted map-elites for automated hearthstone deckbuilding, arXiv preprint arXiv:21 2021.
14

---

APPENDIX
A HYPERPARAMETER SELECTION
For all domains we mirror the hyperparameter selection of Fontaine & Nikolaidis (202 For CMA-MAE and CMA-MAEGA, we duplicate the hyperparameter selections of CMA-ME and CMA- MEGA, respectively. Following Fontaine et al. (2020), we run all algorithms with 15 emitters on the linear projection and arm repertoire domains. the latent space illumination domain, we run experiments with only one emitter, due to the computational expense of the domain. Emitters independent CMA-ES instances that run parallel with a shared archive. For each algorithm, we (202)1)))
Fontaine select a batch size À 36 FollowingFFontanee & Nikolaidis (2021a). For MAP-Elites and MAP-E A-Ettes (line), we initialize the archive with 100 random solutions, sampled from the distribution, N(O, Z). These initial solutions do not count in the evaluation budget for MAP-Elites and MAP-Elite (line). For algorithms in the CMA-ME family (CMA-ME, CMA-MAE, CMA-MEGA, and CMA-MAEGA), initialize 0g- for every domain.
In our experiments we want to directly compare the ranking mechanisms of CMA-ME and CMA-MAE. However, CMA-ME is typically run with a "no improvement" restart rule, where the algorithm will restart if no solution changes the archive. Due to CMA-MAE's annealed accep- tance threshold f.. a "no improvement" restart rule would cause CMA-ME and CMA-MAE restart at different rates, confounding the effects of restarts and rankings. Filter selection also has a similar confounding effect as solutions are selected they change the archive. For these reasons, in the main paper we run CMA-ME with basic restart rule (CMA-ES style restarts only (Hansen 2016)) and μ selection (Hansen 2016) (selecting the top half of the ranking). In Appendix Section K we run an extra CMA-ME with filter selection and the "no improvement" restart rule, which we denote CMA-ME*. We include, as an additional bascline, a configuration of CMA-ME that mixes emitters that optimize only for the objective with emitters that optimize for improvement, configuration first studied Cully (2021). We refer to this configuration as CMA-ME (imp, opt).
In the latent space illumination domain, due to the computational expense of the domain, we compare directly against the results from Fontaine & Nikolaidis (2021a), where we obtained the data (MIT license) with consent from the authors. For CMA-MAE and CMA-MAEGA improvement" restart rule to match CMA-ME and CMA-MEGA as closely as possible. For this domain, we take gradient steps with the Adam optimizer (Kingma & Ba 2015), following the recommendation of Fontaine & Nikolaidis (2021a). However, we run CMA-MAL with μ selection, since we found that small values of the archive learning rate makes filter selection worse.
include the "no
In Appendix ! we describe a second LSI experiment on StyleGAN2 (Karras et al., 2020b) configured by insights from the generative art community that improve the quality of single-objective latent space optimization. For this domain, we configure CMA-MAEGA and CMA-MEGA to use a "basic" restart rule because the latent space 1.2 regularization keeps solutions the StyleGAN2 training distribution. For this experiment, the latent space is large (n 9216), and CMA-MAE due to the size of the covariance matrix (9216 x 9216) and the prohibitive cost for computing eigendecomposition of large covariance matrix.
exclude CMA-ME
Linear Projection (sphere, Rastrigin, plateau).
MAP-Elites: o = 0.5
MAP-Elites (line): = 0.5, 02 0.2
CMA-ME: = 0.5. / selection, basic restart rule
CMA-ME*: 0.5, filter selection, improvement restart rule
CMA-ME (imp, opt): a = 0.5, μ selection, basic restart rule, 7 optimizing and 8 improvement emitters
CMA-MAB: o 0.5, a 0.01, min, 0, μ selection, basic restart rule
CMA-MEGA: og = 10.0, 7) 1.0, basic restart rule, gradient ascent optimizer
CMA-MAEGA: 0, = 10.0, 7 = 1.0, a = 0.01, min, = 0, basic restart rule, gradient ascent optimizer
15

---

Arm Repertoire.
MAP-Elites: o 0.1
MAP-Elites (line): 01 0.1, 02 = 0.2
CMA-ME: 0.2, μl selection, basic restart rule
CMA-ME*: 0.2, filter selection, improvement restart rule
CMA-ME (imp, opt): 0.2, μ selection, basic restart rule, optimizing and improvement emitters
CMA-MAE: 0.2, a 0.01, miny 0, μ selection, basic restart rule
CMA-MEGA: 0g 0.05, 1/ 1.0, basic restart rule, gradient ascent optimizer
CMA-MAAGA: dg 0.05, 1.0, = 0.01, miny 0, basic restart rule, gradient ascent optimizer
Latent Space Illumination. (StyleGAN)
MAP-Elites: 0.2
MAP-Elites (line): 0.1, 02 0.2
CMA-ME: 5 = 0.02. filter selection, no improvement restart rule
CMA-MAE: 0.02, a 0.1, miny 55, μ selection, no improvement restart rule, 50 iteration timeout
CMA-MEGA: 0g = 0.002, 1/ = 0.002, Adam optimizer, no improvement restart rule
CMA-MMAGA: 0g = 0.002, 1 0.002, a 0.1, miny 55, Adam optimizer, no improvement restart rule, 50 iteration timeout
Latent Space Illumination. (StyleGAN 2)
MAP-Elites: a= =
MAP-Elites (line): 01 0.1, 02 0.2
CMA-MEGA: 0g 0.01, 17 0.05, Adam optimizer, basic restart rule
CMA-MAEGA: dg = 0.01, 0.05, 0.02, miny 0, Adam optimizer, basic restart rule
Adam Hyperparameters. We use the same hyperparameters previous work Perez (022 Nikolaidis (2021a).
Fontaine
0.9
.2 0.999
Archives. For the linear projection and arm repertoire domains, we initialize an archive of 100 x 100 cells for all algorithms. For latent space illumination we initialize an archive 200 200 cells for all algorithms, following Fontaine & Nikolaidis (2021a).
B DOMAIN DETAILS
To experimentally evaluate both CMA-MAE and CMA-MAEGA, we select domains from Fontaine & Nikolaidis (2021a): linear projection (Fontaine et al. (020), arm repertoire (Cully Demiris 2017). and latent space illumination (Fontaine et al.) 2b) While many quality diversity optimization domains exist, we select these because gradients of j and m are casy to compute analytically and allow evaluate DQD algorithms in addition to derivative-free QD algorithms. To evaluate the good exploration properties of CMA-MAE on flat objectives, we introduce a variant of the linear projection domain to include "plateau" objective function.
Linear Projection. The linear projection domain (Fontaine et al. 2020) was introduced benchmark distortions caused by mapping high-dimensional search space dow-dimensional measure space.
16

---

n
1=10
n=
8
8
(b)
Figure 6: Measure function figures reproduced from prior work (Fontaine et al. 2020 Fontaine Nikolaidis, 2021a) with the authors' permission. (a) Bates distribution. (b) clip function for defining the measures in the linear projection domain.
The domain forms a 2D measure space by a linear projection that bounds the contribution of each component 0g of the projection to the range [-5.12, 5.1 QD algorithms must adapt the step size of each component 0 to slowly approach the extremes of the mcasure space, with a harsh penalty for components outside [-5.12, 5.12]. As QD domains must provide objective, the linear projection domain included two objectives from the black-box optimization benchmarks (Hansen et al. 2016 2010 sphere and Rastrigin. Following Fontaine et al. (2020), run all experiments for 100.
Formally, the measure functions are defined as a linear projection, a weighted sum the components 0 E R of solution 0 R The first measure function m. is weighted the solution 0, and the second measure function mg is a weighted sum of the second half of the solution (see Eq. 3}. To ensure that all solutions mapped measure space occupy finite volume, the contribution in measure space of each component 6, is bounded to the range [-5.12, 5.12] via clip function (see Eq. (2 that applies harsh penalty for solution components 0; stepping outside the range 1-5.12, 5.1
of the first half of
clip(0,) = [0:
if - S 0, S 5.12
(2)
15.12/0,
otherwise
1 Σ O..) clip(O:)
(()) =
(3)
i= ++
Fig. [6) visualizes why the linear projection domain is challenging. First, we note that the density of solutions in search space mapped measure space mostly occupies the region close 0. To justify why, consider sampling uniformly in the hypercube 1, 5.12)" in search space. We note that each of these points maps the linear region of the measure functions and each of our measures becomes sum of random variables. If we divide by n, we normalize by the dimensions of the search space, then the measure functions become an average random variables. The average of uniform random variables is the Bates distribution (Johnson et al. 1995). distribution that narrows in variance as n grows larger. Without the clip function, a QD algorithm could simply increase single 0 to reach any point in the measure space. However, the clip function prevents this by bounding the contribution of each component of 0 to the range 5-5.12, 5.12]. To reach the extremes of measure space all components 8, must converge to the extremums 12.12. The linear projection domain is challenging to explore due to both the clustering of solutions a small region of measure space and the heavy measure space penalties applied by the clip function when component leaves the region [-5.12, 5.1
Next, describe the linear projection domain's 's objective functions visualized in Fig.
17

---

-9
(a)
(b)
(c)
Figure 7: Objective functions for the linear projection domain in their minimization form for n (a) sphere function. (b) the Rastrigin function. (c) plateau function.
The objectives of the linear projection domain satisfy the requirements that QD domain needs to have an objective and are of lesser importance than measure function definitions, since benchmark primarily evaluates exploration capabilities. |Fontaine et al. (2020) selected two objectives from the black-bov optimization benchmarks competition (Hansen et al. 2016)] 2010): sphere and Rastrigin. The sphere function (Eq. 4 is quadratic function while the Rastrigin function (Eq, | is a multi-modal function that when smoothed is quadratic. The domain shifts the global optimum to the position 8; 5.12 0.4 2.048.
1
f Saphere (0)
Σ0
0²
(4)
[Rastrigin (0) 10n
>
00 10 cos (2+0))
(5)
We introduce an additional objective to evaluate the good exploration properties CMA-MAE on flat objectives. Our "plateau" objective function (Eq. 7p is constant everywhere, but with a quadratic penalty for each component outside the range [-5.12, 5.12]. The penalty acts as a regularizer to encourage algorithms to search in the linear region of measure space.
Splateau (0.) f0
if 5 5.12 otherwise
(6)
111/ 5.12)²
Spiateau (0)
Σ fplateau (0,)
(7)
Arm Repertoire. The arm repertoire domain Cully & Demiris (017); Vassiliades & Mouret (2018) tasks QD algorithms to find diverse collection arm positions for an r--imensiinal planar robotic arm with revolute joints. The measures in this domain are the 2D coordinates of the robot's s end-effector and the objective to minimize the variance the joint angles.
In Fig. 8 visualize example arms for 5 (5-DOF). The optimal solutions in this domain have variance between all joint angles. The measure functions are bounded to the range [-n, rı] as each arm segment has unit length. The reachable cells form circle of radius n. Therefore, the optimal archive coverage is approximately In Rs 78.5%. An archive can achieve an upper-bound this ratio that becomes tighter at higher resolutions. We select 100 (100-DOF) arms for the experiments.
an
Latent Space Illumination. Prior work introduced the latent space illumination problem (Fontaine) et al. 202Tb), the problem of searching the latent space of generative model with quality diversity algorithm. We evaluate on the StyleGAN+CLIP version of this problem (Fontaine & Nikolaidis
II derivative-fres optimization many of the benchmark functions named after the shape of the contour lines. In the of quadratic functions with identity Hessian matrix, the contour lines form hyperspheres.
18

---

-5
-5
-5
5
5
-
(a)
(b)
(c)
Figure 8: Examples of the Arm Repertoire domain for n 5. The figures are reproduced from previous work (Fontaine Nikolaidis, (021a) with the authors' permission. (a) An optimal grasp with 0 variance between joint angles. (b) A sub-optimal grasp. (c) An ensemble of 0 variance optimal grasps.
2021a), by searching the latent space of StyleGAN (Karras et al. 2019) with QD algorithm. We form the differentiable objective and measures in this domain by specifying text prompts to the CLIP model (Radford et al., 2021) that can determine the similarity of an image and text. We specify an objective prompt of "A photo of Beyonce". For measures, we would like to have CLIP quantify abstract concepts like the hair length or age of the person in the photo. However, CLIP can only determine similarity of image and
prompt. As surrogates for age and hair length, we specify the measure prompts of "A small child" and "A woman with long blonde hair". The objective and measure functions guide the QD algorithms towards discovering collection of photos of Beyoncé with varying age and hair length.
For our additional L.SI experiment on StyleGAN2 with setup improvements, see Appendix
Transformations of the Objective Function. We highlight two issues that must be addressed by transforming the objective each domain. First, we note that the problem definition in each of our domains contains an objective f that must be minimized. In contrast, the QD problem definition specifies an objective that must maximized. Second, the QD-score metric, which measures the performance of QD algorithms, requires non-negative objective function. Following prior work (Fontaine et al. 2020 Fontaine Nikolaidis 202Ia), we transform the objective via a linear af b. The linear transtormation maps function outputs the range [0, 100).
transformation:
In the linear projection domain, we estimate the largest objective value for the sphere and Ras- trigin function within the region 12,, 5.12] for each solution component 0,- We compute f(-5.12, 5..2.... 5.12) for each objective as the maximum. The minimum each function 0. We calculate the linear transformation as:
f(O) fmax smin fmaz
(())) 100
(8)
For our new plateau objective, all solution points within the region 1-5112,5.121 have objective value of For this objective we fmin and fmaz 100 and apply the transformation Eq.
For the arm domain we select fmin and fmae 1, and in the LSI domain we select fmin 0 and fmar 10. We select these values to match Fontaine & Nikolaidis (2021a).
C IMPLEMENTATION
We replicate the implementation details prior work (Fontaine Nikolaidis 2021a).
Archives. For the linear projection and arm repertoire domains, initialize archive of 100 100 cells for all algorithms. For latent space illumination we initialize an archive 200 x 200 cells for all algorithms, following previous work (Fontaine & Nikolaidis. 2021a)
19

---

I.P (sphere)
T.P (Rastrigin)
T.P (plateau)
Arm Repertoire
Algorithm
QD-score
Coverage
QD-score
Coverage
QD-score
Coverage
QD-score
Coverage
CMA-MEGA
75.32
100.00 %
63.07
100.00%
100.00
100.00%
75.21 79.27
75.25% 79.35 %
CMA-MAEGA
75.39
100.00 %
63.06
100.00%
100.00
100.00%
Table Mean QD-score and coverage values after 10,000 iterations for each DQD algorithm in the LP and arm repertoire domains.
LSI (StyleGAN)
LST (StyleGANN2
Algorithm
QD-score
Coverage
QD-score
Coverage
CMA-MEGA
16.08
22.58%
9.17
CMA-MAEGA
16.20
23.83%
11.51
18.62%
Table 4: Mean QD-score and coverage values after 10,000 iterations for each DQD algorithm in the LSI (StyleGAN) and LSI (StyleGAN2) domains.
Metrics. We the sum of f values of all cells in the archive, defined the QD-score Pugh ctt al. (2015), as a metric for the quality and diversity of solutions. Following Fontaine & Nikolaidis (202 la), we normalize the QD-score by the total number of cells, both occupied and unoccupied, to make QD-score invariant to the resolution of the archive. We additionally compute the coverage, defined as the number of occupied cells in the archive divided by the total number of cells.
Computational Resources. We ran all trials of the linear projection and arm repertoire domains on AMD Ryzen Threadripper 32-core (64 threads) processor.
of 20 trials in parallel takes about 20 minutes for the linear projection domain and 25 minutes for the arm repertoire domain. For the latent space illumination domain, we accelerate the StyleGAN+CLIP pipeline on GeForce RTX 3090 Nvidia GPU. One trial for latent space illumination takes approximately 2 hours and 30 minutes for StyleGAN and approximately hours and 30 minutes for StyleGAN2. In all domains, runtime increases when an algorithm obtains better coverage, because we iterate over the archive when QD statistics are calculated.
Software Implementation. We use the open source Pyribs (Tjanaka et al., 2021 library for all algorithms. We implemented the CMA-MAE and CMA-MAEGA algorithms using the same library.
D COVARIANCE MATRIX ADAPTATION MAP-ELITES VIA A GRADIENT ARBORESCENCE (CMA-MAEGA)
In this section. we provide information of the CMA-MEGA differentiable quality diversity (DQD) algorithm, and we derive CMA-MAF's DQD counterpart: CMA-MAEGA.
CMA-MEGA.
Covariance Matrix Adaptation MAP-Elites via Gradient Arborescence (CMA-MEGA) solves the DQD problem, where the objective f and measures m are first-order differentiable. Like CMA-ME, the algorithm maintains solution point
R and MAP-Elites archive.
CMA-MEGA samples new solutions by perturbing the search point O via the objective and mea- sure gradients. However, the contribution of each gradient is balanced by gradient coefficients
0, - 0 co co f(0) DZ Cj Vm, These coefficients are sampled from a multivariate Gaus- sian distribution N(,, Σ) maintained by the algorithm. After sampling new candidate solutions 0, the solutions are ranked via the improvement ranking from CMA-ME. CMA-MEGA updates N(,, Σ) via the CMA-ES update rules and the algorithm steps also in the direction of largest archive improvement. The authors showed that CMA-MEGA approximates natural gradient step of the QD objective (Eq. I. but with respect to the gradient coefficients.
CMA-MAEGA. We note that our augmentations to the CMA-ME algorithm only affects how replace solutions in the archive and how we calculate A, Both CMA-ME and CMA-MAEGA replace solutions and calculate A, identically, we apply the augmentations from CMA-ME to CMA-MEGA to form a new DQD algorithm, CMA-MAEGA Algorithm P for CMA-MAEGA with the differences from CMA-MEGA highlighted in yellow.
Shatthmmmsswwwsssss shows the podudo-code
20

---

Algorithm 2 Covariance Matrix Adaptation MAP-Annealing via Gradient Arborescence (CMA-MAEGA)
CMA-MAEGA (evaluate, N, A, ag a))
input An evaluation function evaluate that computes the objective, the measures, and the gradients of the objectíve and measures, an initial solution Oo. a desired number of iterations N, a branching population size X, a learning rate 77, an initial step size for CMA-ES g.. minimal acceptable solution quality min and an archive learning rate
result: Generate (A (A- solutions storing elites in an archive A.
Initialize solution parameters 0 to Po. CMA-ES parameters = 0, = ogl, and p, where we let p be the CMA-ES internal parameters.
Initialize the archive A and the acceptance threshold te with min, for each cell e. for iter < to N do f. V f, m, V m + evaluate(()) normalize f), Vm f- normalize (
tg then Replace the current elite in cell e of the archive A with 0;
(1- atte of
end for
f- 1 to h do
C ~ N(,, ))
V. - cu + - Cj my
13
0 + 0 Vi
f ml, *
evaluate
Le
if
le then
Replace the current occupant in cell e of the archive A with 0
(1 a)te af
end
end
rank V. by A
22
step
W/
rank|i]
17
step
24
Adapt CMA-ES parameters μ. Σ, based on improvement ranking A; if there no change in the archive then
15
26
Restart CMA-ES with μl 0, T.
27
Set 0 a randomly selected existing cell 0g from the archive
end
end
Experiments. We compare CMA-MEGA and CMA-MAEGA the five benchmark domains. Table and Tsole the QD-score and coverage values for each algorithm and domain, averaged over 20 trials for the linear projection (LP) and arm repertoire domains and over 5 trials for the LSI domains. We conducted two-way ANOVA examine the effect of the algorithm and domain (LP (sphere), LP (Rastrigin). LP (plateau), arm repertoire, LSI (StyleGAN), and LSI (StyleGAN2) on the QD-score. There was a significant interaction between the search algorithm and the domain (F(5, 168) 165.7. < 0.001). Simple main effects analysis with Bonferroni corrections showed that CMA- MAEGA outperformed CMA-MEGA in the LP (sphere), arm repertoire, and L.SI (StyleGAN2) domains. There (Rastrigin), LP (plateau), and LSI (StyleGAN) domains.
statistically significance difference between the two algorithms in the LP
We attribute the absence of statistical difference in the QD-score between the two algorithms the LP (Rastrigin) and LP (plateau) domains on the perfect coverage obtained by both algorithms. Thus, any differences in QD-score based on the objective values of the solutions returned by each algorithm. In LP (platcau), the optimal objective for each cell easily obtainable for both methods. The LP (Rastrigin) domain contains many local optima, because of the form of the objective function
21

---

(Eq. 5). CMA-MEGA will converge to these optima before restarting, behaving as single-objective optimizer within each local optimum. Because of the large number local optima in the domain, results in higher QD-score.
In the LSI (StyleGAN) domain, we attribute similar performance between CMA-MEGA and CMA-MAEGA to the restart rules used keep each search within the training distribution of StyleGAN. On the other hand, in the LSI (StyleGAN2) domain, we regularize the search space by an L2 penalty in latent space, allowing for larger learning rate and a basic restart rule for both algorithms, while still preventing drift out of the training distribution of StyleGAN2. Because of the fewer restarts, CMA-MAEGA can take advantage of the density descent property, which was shown to improve exploation in CMA-MAE, and outperform CMA-MEGA. We note that because StyleGAN2 has a better conditioning on the latent space (Karras et al. 2020b), is better suited for gradient-based optimizers, which helps better distinguish between the two algorithms.
E THEORETICAL PROPERTIES OF CMA-MAE
Theorem E.1. The CMA-ES algorithm is equivalent to CMA-MAE when 0, if CMA-ES restarts from an archive solution.
Proof. CMA-ES and CMA-MAE differ only on how they rank solutions. CMA-ES ranks solutions purely based the objective f, while CMA-MAE ranks solutions by f te, where te is the acceptance threshold initialized by miny. Thus, to show that CMA-ES is equivalent to CMA-MAE for a only need to show that they result in identical rankings.
In CMA-MAF, Le is updated as follows: 4, < (1 - aile + aaf. For = O, le miny is invariant for the whole algorithm:
1he + +0 le- Therefore, CMA-MAE ranks solutions based on
f --nn However, comparison- sorting is invariant to order-preserving transformations of the
values being sorted Hansen (0116). Thus, CMA-ES and CMA-MAE rank solutions identically. C
Next, we prove that CMA-ME is equivalent to CMA-MAE with the following caveats. First, we assume that CMA-ME restarts only with the CMA- ES restart rules, rather than the additional "no improvement" restart condition from Fontaine et al. 2020). Second, we assume that both CMA-ME and CMA-MAE leverage μ selection rather than filtering selection.
Lemma E.2. During execution of the CMA-MAE algorithm with a = 1, the threshold te is equal to f(0e) (00)for for cells that are occupied by a solution Og and to min, for all empty cells.
Proof. We will prove the lemma by induction. All empty cells are initialized with te minf. satisfying the basis step. Then, we will show that if the statement holds after i archive updates, it will hold after a subsequent update le +
Assume that at step k we generate a new solution 0; mapped to cell e. We consider two cases:
Case The archive cell e is empty. Then, f(O+) > min and both CMA-ME and CMA-MAE will place 0g in the archive as the new cell occupant 0.. The threshold t. is updated as l. (1 - attt + (0.) = Omin, + (f2) f(0)).
Case 2: The archive cell e contains an incumbent solution Oe. Then, either f(0)) < f(0z) or
f(O,) > f(O.). If (0:) S f(0.,, then the archive does not change and the inductive step holds via the inductive hypothesis. If ((,,) f(O,), then O becomes the new cell occupant O, and La is updated as le = (1 a/ + (((0 = 04, + 10())) = [0a).
Theorem E.3. The CMA-ME algorithm is equivalent to CMA-MAE when a = 1 and miny is an arbitrarily large negative number.
Proof. Both CMA-ME and CMA-MAE rank candidate solutions 0 based improvement values A, While CMA-ME and CMA-MAE compute A, differently, we will show that for a = 1, the rankings are identical for the two algorithms.
We assume a new candidate solution mapped to a cell e. We describe first the computation of A, for CMA-ME. CMA-ME ranks solutions that discover empty cell based on their objective value. Thus,
22

---

if 0, discovers an empty cell, A; f(0,). On the other hand, if 0, is mapped cell occupied by another solution e. will rank 0g based on the improvement A, = f(0,) f(02). CMA-ME performs two-stage ranking, where it ranks all solutions that discover empty cells before solutions that improve occupied cells.
We now show the computation of A. for CMA-MAE with a 1. If 0g discovers an empty cell
A; = f(0:) - te and by Lemma E.2 A = f(0,) min f- If 0; is mapped to a cell occupied by
another solution Oe. A; - (O.) le and by Lemma E.2 A - f((O) f(O.).
Comparing the values A, between the two algorithms we observe the following: (1) If 0g discovers an empty cell, A, f(;;) miny for CMA-MAF. However, min, is constant and comparison- based sorting is invariant to order preserving transformations (Hansen 2016), thus ranking by
A; = =(20)) min f is identical to ranking by A f(0)) performed by CMA-ME. (2) If O is mapped to cell occupied by another solution t.. A; f())) f(0z) for both algorithms.
(3) Because miny an arbitrarily large negative number f(0:) miny > f(0,) f(0e). Thus,
CMA-MAE will always rank solutions that discover empty cells before solutions that are mapped to occupied cells, identically to CMA-ME.
We next provide theoretical insights how the discount function fA smoothly increases from constant function miny to CMA-ME's discount function as a increases from 0 to 1. We show this for the special case of a fixed sequence of candidate solutions.
Theorem E.4. Let ai and aj be two archive learning rates for archives As and A₁ such that < ag < aj S 1. For two runs of CMA-MAE that generate the same sequence of m candidate solutions {S} 01, 02 .... Om, follows that fA, (0) fA, (0) for all A E R
Proof. We prove the theorem via induction over the sequence of solution additions. fA is the histogram formed by the thresholds te over all archive cells e in the archive. Thus, we prove fA, $ fA, by showing that (A,) I (AA) for all archive cells e after m archive additions.
As basis step, we note that A, equals A, as both archives are initialized with miny.
Our inductive hypothesis states that after & archive additions we have t. (A,,) S te (Ay), and we need to show that te (A,) S (AA) after solution 0k41 is added to each archive.
Our solution 0x+1 has three cases with respect to the acceptance thresholds:
Case 1: f(0k+1) S (A,)) S (Ay)). The solution is added to either archive and our property holds from the inductive hypothesis.
Case 2: (A,) S f0x+11) S te (A,). The solution is added to A,, but not Ay, thus (A,)) to (A,). ). We follow the threshold update: t. (A,) = (1 - a:)t. + ((0+t). Next, we need to show that (A..) < t. (A₂) to complete the inductive step:
(1 --ar)(((Ai) + az S [(0++1)
(1 - au (A,)) < (1 -xx)((xx11
te (A,) S f(0++1) as 0; 2 0
The last inequality holds true per our initial assumption for Case 2. From the inductive hypothesis, we have [(0++1) (A() = (A,))
Case 3: (A,) < (A,) S (0x+11) The solution ou+1 is added to both archives. We need to show that &. (A:) s (A))
(A(AA) & ((A)
(1 - ()),))((AA)) + oz 5 (1-aa)) (o,
(9)
We can rewrite Eq. 9 as:
(1 - az)t - -(1-a:)te(A) - 20
(10)
23

---

First, note that:
(1 (1-0))6e(A)) - (11a)))
(A)))(A)) (1 (1-a,)tele (A (1 (Ai)
= (1 aj - 1 (A()
(az (A)).
Thus:
(1 - (1-)))((A)-(1--)))))) (11-a)((141))) 2 (a: ay))a(A))
(II)
From Eq. 10 and 11
we have:
(1 - (-))))t(AA) + +aff(xx+1) - -(1-a))te(AA) -atf(O++1)
2 (a; ())(c(A)) + ( ((k+t))))))
= =aa - (f(xt)) -te(Ai)
As aj > a; and f(0x+1) 2 te (At), we have (az - (f te((i)) 2 0. This completes the proof that Eq. 1Ohholds.
As all cases in our inductive step hold, our proof by induction is complete.
Next, we wish to provide insights about the exploration properties of CMA-MAE for archive learning rate a between and I, when the objective f is constant. Consider an approximate density descent algorithm that is identical to CMA-ME, but differs by how solutions are ranked. Specifically, the algorithm maintains a histogram of occupancy counts Oe for each cell e, with og representing the number of times solution was generated in that cell. This algorithm descends the density histogram by ranking solutions based on the occupancy count of the cell that the solution maps to, where solutions that discover less frequently visited cells are ranked higher.
Lemma E.S. The threshold be after k additions cell e forms strictly increasing sequence for constant objective function f() = C for all O E TR"", when 0 < a < and miny < C.
Proof. To show that le after l additions to cell forms strictly increasing sequence, write recurrence relation for te after k solutions have been added to cell e. Let (e(k) = (1 - (k 1) + (0.) and (0) min, be that recurrence relation. To show the recurrence an increasing function, we need to show that (k) > te (k- 1) for all 1: 2 0.
We prove the inequality via induction over cell additions k. As basis step, we show (1) > t (0): miny + aC + aC > a minj. As
(1 - a + aC > min, < miny- miny
C > min, and a > 0, the basis step holds.
For the inductive step, we assume that to (k) > te (k- 1) and need to show that (k + 1) > t (k):
(k + 1) > (k)
(t) + aC > (1 akte 1) aC
(1 a (kk)
- ak, 1)
te (k) (k
Theorem E.6. The CMA-MAE algorithm optimizing a constant objective function functioon f(0) = C for all 0 E I is equivalent to the approximate density descent algorithm, when 0 < < 1 and ming C.
Proof. We will prove that for an arbitrary archive with both the occupancy count for each cell oa and the threshold value computed with arbitrary learning rate 0 < < 1, CMA-MAE results in the same ranking for an arbitrary batch of solutions {0,} as the approximate density descent algorithm.
We let O; and O2 be two arbitrary solutions in the batch mapped cells e; and ej. Without of loss of generality, we let o,, S Oe,- The approximate density descent algorithm will thus rank 0g before 0,. We will show that CMA-MAE results in the same ranking.
If Oe; < Oey. and since te is a strictly increasing function from Lemma E.5 te: (oe.) S tey (oe,). ). We have te, (Oe.) I te, (Oe,).
C te. (o..) 2 C te, (or,). ). Thus, the archive improvement by adding 0; to the archive is larger than the improvement by adding 0, and CMA-MAE will rank 0, higher than 0z. identically with density descent.
24

---

While Theorem E.6 assumes a constant objective f. generally when threshold te in each cell e approaches the local optimum within the cell boundaries.
we conjecture that the theorem holds true
Conjecture E.7. The CMA-MAE algorithm becomes equivalent to the density descent algorithm for a subset of archive cells for an arbitrary convex objective f, where the cardinality of the subset of cells increases as the number of iterations increases.
We provide intuition for our conjecture through the lense of the elite hypervolume hypothesis (Vas siliades Mouret 2018). The elite hypervolume hypothesis states that optimal solutions for the MAP-Elites archive form connected region in search space. Later work (Rakicevic et al., 202I) ), connected the elite hypervolume hypothesis to the manifold hypothesis (Fefferman et al., 2016 in machine learning, stating that the clite hypervolume be represented by low dimensional manifold in search space.
For our conjecture, assume that the clite hypervolume hypothesis holds and there exists smooth manifold that represents the hypervolume. Next, we assume in the conjecture that f is an arbitrary convex function. As f is convex, early in the CMA-MAE search the discount function fA will be flat and the search point will approach the global optimum following CMA-ES's convergence properties (Hansen & Ostermeier 1997 Hansen et al. 2003), where the precision of convergence is controlled by archive learning rate By definition, the global optimum 0 is within the elite hypervolume as no other solution of higher quality exists within its archive cell. Assuming the elite hypervolume hypothesis holds, a subset of adjacent solutions in search space will also be in the hypervolume due to the connectedness of the hypervolume. As fa increases around the global optimum, we conjecture that the function f f(0*)
fA") will form plateau around the optimum, since it will approach the value f(0;) - fA(O,, (0:) of adjacent solutions Og. By Theorem E.6 we have density descent algorithm within the plateau, pushing CMA-MAE to discover solutions on the frontier of the known hypervolume.
Finally, we remark that conjecture implies that f fA tends towards constant function in the limit, resulting in a density descent algorithm across the clite hypervolume manifold as the number of generated solutions approaches infinity. We leave formal proof of this conjecture for future work.
F THEORETICAL PROPERTIES OF CMA-MAEGA
In this section, we investigate how the theoretical properties of CMA-MAE apply to CMA-MAEGA. While many of the properties are nearly a direct mapping, we note that, while CMA-MAE is equivalent to the singlc-objective optimization algorithm CMA-ES for a O, there is no single-objective counterpart to CMA-MAEGA. To make the direct mapping easier, we introduce a counterpart: the gradient arborescence ascent algorithm.
The gradient arborescence ascent algorithm is similar to CMA-MEGA, but without an archive. Like CMA-MEGA, the algorithm assumes a differentiable objective ʃ and differentiable measures m. However, the algorithm leverages the objective and measure function gradients only to improve the optimization of the objective f. rather than to find solutions that are diverse with respect to measures As with CMA-MEGA, the gradient arborescence algorithm branches in objective-measur space. However, the algorithm ranks solutions purely by the objective function f and adapts the coefficient distribution N Σ) towards the natural gradient of the objective f-
Next, we prove properties of CMA-MAEGA that directly follow from the properties of CMA-MAE
Theorem F.I. The gradient arborescence ascent algorithm is equivalent to CMA-MAEGA when -=0 0, if gradient arborescence ascent restarts from an archive elite.
Proof. We note that CMA-MAEGA and the gradient arborescence ascent algorithm differ only in how they rank solutions, and we note that the differences between CMA-MAE and CMA-ES mirror the differences between CMA-MAEGA and gradient arborescence ascent algorithm. So by directly adapting the proof of Theorem E.] we complete our proof.
Theorem F.2. The CMA-MEGA algorithm is equivalent to CMA-MAEGA when a = and miny is an arbitrarily large negative number.
25

---

Proof. We note that CMA-MAEGA and the CMA-MEGA algorithm differ only in how they rank solutions and how they update the archive A, and we note that the differences between CMA-MAE and CMA-ME mirror the differences between CMA-MAEGA and CMA-MEGA. So by directly adapting the proof of Theorem E.. we complete our proof.
Theorem F.3. Let a; and 0 be two archive learning rates for archives A, and A₁ such that 0 S ai < j < 1. For two runs of CMA-MAEGA that generate the sume sequence of i candidate solutions {S} 01, 02 ..., Oms it follows that SA, (0) S JA (0) for all E "R...
Proof. We note that CMA-MAE and CMA-MAEGA update the archive A in exactly the same way. Therefore, the proof follows directly by adapting the proof of Theorem E.4 to CMA-MAEGA. O
Next, we wish show that CMA-MAEGA results in density descent in measure space. However, we need a counterpart to the approximate density descent algorithm we defined in Theorem E.6
Consider an approximate density descending arborescence algorithm that is identical CMA-MEGA, but differs by how solutions are ranked. Specifically, we assume that this algorithm maintains occupancy count oe for each cell e, which the number of times solution was generated in that cell. The density descent algorithm ranks solutions based on the occupancy count of the cell that the solution maps to, where solutions that discover less frequently visited cells are ranked higher. The algorithm takes steps in search space I" that minimize the approximate density function defined by the archive and adapts the coefficient distribution N( Σ) towards coefficients that minimize the density function.
Theorem F44 The CMA-MAEGA algoritium optimizing constant objective function f(0) C for all 0 E _ is equivalent to the approximate density descending arborescence algorithm, when 0 < < and miny < C.
Proof. The proof of Theorem relies only on how CMA-MAE updates the archive A and accep- tance threshold te. The proof of this theorem follows directly by adapting the proof of Theorem E.6 to CMA-MARGA.
G DERIVATION OF THE CONVERSION FORMULA FOR THE ARCHIVE LEARNING RATE
In this section, we derive the archive learning rate conversion formula 022 1 - (1 a1)" mentioned in Section of the main paper, where r the ratio between archive cell counts, and aa and 0g are archive learning rates for two archives A1 and A2.
Given an archive learning rate a for A,, we want to derive an equivalent archive learning rate as for Ag that results in robust performance when CMA-MAE is run with either A₁ or Ag. A principled way to derive a conversion formula for a is to look for an invariance property that affects the performance of CMA-MAE and that holds when CMA-MAE generates solutions in archives A₁ and A2.
Since CMA-MAE ranks solutions by f fA. we wish for fA to increase at the same rate in the two archives. Since (0) le, where te is the cell that solution O maps to, we select the average value of the acceptance thresholds f, over all cells in each archive as our invariant property.
We assume arbitrary sequence of N solution additions 01, 01,02..... 02..... ON evenly dispersed across the archive cells. We then specify le as a function that maps k cell additions to a value Le in archive cell Equation 12 then defines the average value of across the archive after N additions an archive A with M cells.
N M
(12)
Then, equation 13 defines the invariance we want to guarantee between archives A₁ and A2.
'Here we abuse notation and view tg as function instead of threshold for simplicity and highlight the connection to the threshold value tc.
26

---

M1
M2
N
1
N
(13)
M1
M
M2
In Eq. 13 we let Mi and M2 the number of cells in archives A and A2, and we assume that M1 and M2 divide N. To solve for closed form 02 subject to our invariance, we need formula for the function te. Similar to Lemma E.5 can represent the function te recurrence relation after adding & solutions to cell an archive A.
(0) minf (k) (1 a.6.
a0))
(14)
Next, we look derive closed form for te (A) for an archive A as a way manipulate Equation 13 However, solving for te (k) when f is an arbitrary function is difficult, because different regions of the archive will change different rates. Instead, we solve for the special case when (()) C and miny < C, where C E R is a constant scalar. To solve for closed form of the recurrence te (k), we leverage the recurrence unrolling method (Graham al. 1989). allowing us to guess the closed form in Equation 15
(2(1) = (1 a)). + aC = +
(2) (1 a))x((1) aC (1 004-aj1 a) a))(i
a)min + aC| + aC
(1 a) m)mmn + - a)aC + aC
(.33) (1 a (2) +aC
(1 a) a){(1
+ (1 +
(1 a M + a) (1- al-a +aC
k 1
(k) = (1 - -a) ming +
Σ
(1 a)
(15)
We recognize the summation in Equation summation as follows.
15
geometric series. As 0 <
rewrite the
(kk) (1 a) min Σ
(1 (1-a)'aC
1=0
(1 a+)
(1 a) m + aC
1 (1 - aa)
(1- a
(1 > + aC
(1 a C C(1 a)*
(min, C1 (1) +C
CC - (C (1
(16)
Next, we prove that the closed form we guessed is the closed form of the recurrence relation.
Theorem G.I. The recurrence relation te (0) = miny and (k) (1 - atte (k - 1) + aC has the closed form (k) C - (C minn) a²*, where 0 < a and min, < C.
Proof. We show the closed form holds via induction cell additions k.
27

---

As basis step show that (0) th
C (C miny) -i))) C (C miny) miny.
For the inductive step, suppose after j insertions into the archive in cell e our closed form holds. We show that the closed form holds for + insertions.
=0++1)= a)te +aC
(1 a)(C - (C min, a)1 aC
C(1 a) (C min 1) +
C aC aC' (Cm-ming)(L a)
CC - (C (1
(17)
As our basis and inductive steps hold, our proof is complete.
The closed form from Theorem G.I allows us to derive a conversion formula for a2 via our invariance formula in Equation B
M
M2
N
1
Σ
N
te
te
M
M1
M2 i=1
M2
i=1
M1 (c- (C minj (1 a1) J
M2
C (C -mmnn ()imn)(11 02) 1
Mj
M2
(C (1 (1 - (2)) N
(C - (C-mmin minn)(11 - 01)
M
N
(1 - a1
M
(1 a2) Xi
M2
(1 01
M..
(1 (:2)
M2
02
a1)
(18)
We remark that our conversion formula is not dependent on the number archive additions N. Although our conversion formula assumes f to be constant objective, we conjecture that the formula holds generally for a convex objective f.
Conjecture G.2. The archive learning rate conversion formull results in invariant behavior of CMA-MAE for two arbitrary archives A₁ and A2 with archive resolutions M1 and for a convex objective f.
Our intuition similar to the intuition behind Conjecture H.7 where we assume the elite hypervolume hypothesis holds (Vassiliades & Mouret 20088). the beginning of the CMA-MAE search, fA is a constant function and CMA-MAE optimizes for the global optimum, following the convergence properties of CMA-ES (Hansen & Ostermeier 1997 Hansen et al. 2003). Eventually, the cells around the global optimum become saturated and the function f fA forms plateau around the global optimum. The invariance described in Eq. implies that the fA, and fA, will increase at the same rate within the flat region of the plateau. Let Op be an arbitrary solution in the plateau and 0' be solution on the frontier of the known hypervolume. The plateau of each archive A, expands when the solutions the frontier of the clite hypervolume achieve larger f(0') fA, (0') than the plateau f(O)) - fA, (0p). We conjecture that the plateau will expand at the same rate in the two archives fA, and fA, increase at the same rate for the plateau region, due to invariance in Eq. [3]
We speculate that our conjecture explains why observe invariant behavior across archive resolutions in the experiments of Section even though f is not a constant function in the linear projection and arm repertoire domains.
28

---

H A BATCH THRESHOLD UPDATE RULE FOR MAP-ANNEALING
In this paper, we presented an annealing method for updating a QD archive in the CMA-MAB algorithm, following the standard QD formulation where we add single solution to the archive at time. However, the recently developed Qaa library (Lim et al. (2022) assumes that the updates to the archive happen in batch. In this section, we show that the archive update within a batch dependent on the order that the solutions are processed. We then propose candidate threshold update rule that invariant the order the solutions are processed within a batch update.
First, we show that the order solutions are added to the archive affects the current threshold update. Consider two solutions 0 and 02 that we add to the archive in single batch. 0₁ is added before 02, then the threshold update becomes ty = (1 [1 - at) + a + ( = If 02 is added before 01, then the threshold update becomes 1" (1 [)1 ailee + a (02) + af(0,) = (1 ae + (1 a)))((02) + (O,)).
a02) at + (1 a (01) +
To compare ig to 1" we compute 12- I
(1 a) te + (1 (1-))((((()))
[[1 t, + (11a))a(0))+af(00
(1 ( +((((2)) falf
[(1 a)a a ((2))
-a) - f(02)
From the above derivation, see that the difference between thresholds is dependent the solution's 's objective values when added to the archive in different order. This means when adding solutions to the archive in batch, the update is dependent on the solution order in the batch.
Our goal is to make the threshold update invariant to the order the solutions are added to the archive. First, consider a subset of the batch that contains solutions all landing in the same cell of the archive and exceeding the current threshold fe- Adding the solutions in batch order results in the following threshold update:
1' - a
Σ aa-aa)aaa00 J=1
Let X be random variable corresponding the threshold for given permutation of the batch. To become invariant to the batch addition, we will change the threshold update to be [[X], the expected value of l across all random permutations of the batch.
Let X, be a random variable corresponding to the contribution of only f(2s) to the threshold update and Y be constant random variable corresponding the contribution of the previous threshold. As expectation is linear, we have [[X] = E[Y] Σラ= [[]2]] Next, we compute the value of E[X,] for an arbitrary solution 0, in the batch:
Pr(O; is at position j in the aa)
j=1
(c 1)!
c
1=1
(1 a)- (af())
Next, we rework E[X] into simpler formula, where f Di f(0x),
29

---

= + Σ B[X,]
==1
= (1- - +
a) a022
k=1j=1
1 Σ (kk
10-
j=l
k=1
(1 a te +
af
= (1 0) 4/ +
j=0
a
te + af
a at + f (1 (1-a))
We propose the above expectation as the batch threshold update rule, where f is the average objective value for all solutions in the batch that exceed the threshold L. for a given cell. We observe that the rule is independent of the solution order. Furthermore, if a 0, the update becomes le. and Theorem [5. still holds. If a 1. the update becomes f", which is the average of solutions that increase the threshold. We view this update smooth parallel addition compared to CMA-ME, which would add the best solution from the batch for any solution order. We leave exploring alternative batch update rules for future work.
I ON IMPROVING THE QUALITY LATENT SPACE ILLUMINATION
We describe the limitations arising from the exact problem setup for our main experiments, adopted from previous work (Fontaine & Nikolaidis (021a), on producing high-quality images. We then discuss ideas from the generative art community for improving the setup and an additional experiment that incorporates these ideas to generate high-quality and diverse images.
I.1 MAIN LSI EXPERIMENTS
In the main latent space illumination (LSI) experiments in section 6 we showed that CMA-MAE outperformed the other QD algorithms according to standard QD metrics following the exact setup of prior work (Fontaine & Nikolaidis, 2021a)
In the these experiments, we used latent space illumination purely an optimization benchmark. However, obtaining high performance on LSI as a benchmark can be competing objective with producing high quality images.
First, finding solutions that result high objective value does not always result high quality images that match the text prompt. For example, QD algorithm can find images that result in CLIP reporting a high similarity score by leaving the training distribution of StyleGAN.
Furthermore, use the CLIP loss measure function, thus QD algorithm attempts to both decrease and increase the loss function to cover the measure space. Increasing the loss function results in minimizing similarity with the text prompt, which can be attained by unrealistic images.
In the main LSI experiments all derivative- free QD algorithms would drift out of the latent distribution and produce archives of low image quality. We found that CMA-MAE would stay in the latent distribution longer before drifting out of distribution during exploration, due to the low archive learning rate prioritizing the objective.
30

---

To address drifting out of distribution, we adopt "timeout" restart rule proposed by other evolution strategy-bard based quality diversity algorithms (Colas et al.) 2020 Paolo et al. 202T). J. A timeout restart rule runs for fixed number of iterations before restarting. We add to the basic restart rule of CMA-MAE (Appendix A) an additional criterion for restarting based on the timeout restart rule. To generate all the LSI collages in section K use timeout of 50 iterations for both CMA-MAE and CMA-MAEGA.
While we retained the same setup as previous work for comparison purposes, can change the setup by adopting ideas from the generative art community to produce very high quality images. We describe these ideas in section L.2
1.2 INNOVATIONS FROM THE GENERATIVE ART COMMUNITY
Beyond the specifies of the QD optimization algorithm, many aspects of latent space illumination can be improved. For example, prior work Frans et al. (202I) on guiding single-objective optimization with CLIP notes that the gradients that CLIP provides can be noisy and recommends data augmenta- tions of the generated images, such as tiling or translating each image, before being passed to CLIP. This change can help smooth the gradients for gradient descent optimizers like Adam and can make the generated images retained by the archive match their text prompts more accurately.
Prior work on optimizing the latent space of VQ-GAN (Crowson et al. 2022) also notes that CLIP will not always provide smooth optimization gradients, nor accurate objective values. The authors recommend different data augmentation, by creating a batch of random cutouts of the generated image and passing those images to CLIP, which produces smoother gradients and objective values. The paper also recommends regularizing the latent codes so that they become attracted to the Gaussian ball that captures the training disribution of the GAN. Both these techniques could improve the qualitaaiive performance of latent space illumination.
Finally, we used the first version of StyleGAN Karras et al. 2019) that was used in previous work (Fontaine Nikolaidis) (021a). Recent versions of StyleGAN (Karras et al., 2020b 2021 can further improve the quality of the generated images.
We describe details of the improved setup in section
1.3 IMPROVING QUALITY OF GENERATED IMAGES
To improve image quality, include additional experiment where each QD algorithm with a configuration inspired by the above findings from the generative art community.
First, replace StyleGAN (Karras al. 2019) with StyleGAN2 (Karras et al. 2020b). which produces better images and has a well-conditioned latent space for optimization.
Next, we change the latent space being optimized by QD. First note, that the StyleGAN architecture has multiple latent spaces to be optimized. StyleGAN consists of both a z-space latent space of size 512 and a mapping network that maps to 18 latent codes of size 512 different levels of detail in the final image. This 18 x 512 tensor is known as w-space. The original LSI experiments of Fontaine & Nikolaidis a2 were based of blogpost (Perez 202I) that respresented the search space for LSI as single 512 dimensional vector whose weights were shared for each level of detail in w-space. In this experiment, we will optimize the full 18 x 512 9216 w-space with each QD algorithm for fine grain control of the generated images.
Instead of using restarts in the StyleGAN experiments to keep the search within latent space, we adopt the w-space regularization of Crowson et al. (2022). We compute an average w-space position by sampling 10 points sampled from ((0 0, 7) in z-space, then passing these points through the mapping network to find their position in w-space. We compute the standard error across each dimension. To regularize the latent space, we compute the distance from this w-space Gaussian distribution. If the distance from mean exceeds the Gaussian ball of highest density, we apply an L.2 penalty to the objective of to move the search back into the training distribution.
The LSI experiments from prior work (Fontaine & Nikolaidis 202 downsample from the 1024 x 1024 images produced by StyleGAN to the 224 x 224 images required for input to the CLIP model. Following prior work (Crowson et al. 2022). we adopt the cutout technique that clips
31

---

32 images from the StyleGAN output of varying sizes, downsamples each cutout to 224 x 224, and passes each of these 224 x 224 cutouts to CLIP for evaluation. The loss becomes the average of the CLIP loss for all cutouts. This technique has been shown to smooth gradients for CLIP in single-objective latent space optimization.
Instead of starting the search the latent code 0, sample 512 latent codes from (00 I) in 2-space then select the image resulting in the highest objective value as the starting w-space latent code.
Finally, the prior LSI experiments leveraged the text prompt "A small child." However, this text prompt only specifies one end of the age measure. To correct this issue, we can pair a positive text prompt "A small child." with negative text prompt "An elderly person." proxy for age. We compute the measure output by subtracting one CLIP loss from the other.
proxy for age.
We run the improved LSI experiment with the text descriptor "A photo of the face of Tom Cruise." as an objective, the text pair "A photo of Tom Cruise as a small child." and "A photo of Tom Cruise as an elderly person." as proxy measure for age, and "A photo of Tom Cruise with short hair." and "A photo of Tom Cruise with long hair." as a proxy measure for hair length.
Fig. 4 shows photos of Tom Cruise varying hair lengths and ages, generated by the CMA-MAEGA algorithm in single run.
J ON THE EFFECT OF THRESHOLD INITIALIZATION
In this paper we introduce two hyperparameters for our proposed CMA-MAE algorithm: the archive learning rate a and a threshold initialization miny. In this section we discuss the effect of different miny initializations on the performance and behavior of CMA-MAE. Finally, we run an ablation on miny. similar to the ablation on archive learning rate a in Section 7
First, consider the effect of min y on the extreme cases of the CMA-MAE. When a 0, then according to Theorem E. CMA-MAE behaves identically to CMA-ES, and min, has no effect on the behavior of CMA-MAE Conversely when a 1, then according to Theorem E.3 CMA-MAE behaves identically to CMA-ME when min, approaches an arbitrarily large negative number. As miny increases for a = 1, CMA-MAE will rank some solutions that discover existing cells higher than solutions that discover new, empty cells, thus it will behave differently than CMA-ME.
Next, we discuss the behavior for 0 < a < 1, Recall the elite hypervolume hypothesis (Fefferman eet al., 20166). which states that optimal solutions for the MAP-Elite, archive form a connected region in search space, the elite hypervolume. According to the proof sketch of Conjecture E.7 early in the search CMA-MAE behaves identically to CMA-ES to find solution point on the elite hypervolume. As the thresholds of cells around this solution point become saturated, the objective f fA forms plateau around the local optimum. Within the plateau, CMA-MAE triggers the density descent property of Theorem E.6 and evenly explores the known elite hypervolume until the plateau in f- S'A dips below the frontier of the known hypervolume. This causes the known hypervolume to expand until all cells of the archive are filled.
Next, we discuss how the selection of min, affects the rate of expansion of the clite hypervolume. First, we consider two solution points: 0₂ represents a local optimum in the elite hypervolume and 02 represents a nearby point mapped
different archive cell with a smaller objective value, or formally f(0)) > f(22) and |[0 02 lz I We let (01) = te, and fa (02)) = te,, where te, and leg represent the thresholds of the cells that O, and 0₂ map to, respectively. Both thresholds leg and leg are initialized with mannf.
We first examine the case where min, > ʃ(0,) > f(2)). Here, the thresholds le, and leg will not change and none of the two solutions points will be added to the archive. CMA-MAE will then only optimize for the objective value and behave identically to CMA-ES.
The second case is f(Or) > ming > f(02). Here, O2 will not get added to the archive and tez = min, y will not change, while te, will increase based on the update rule fej + (1 Recall that CMA-MAE ranks solutions based on improvement A, f(0.) tey. We observe that A2 f(2)) min, < O, while A = f()) te, > 0, thus there is no incentive for CMA-MAE
to optimize for O2 and it will instead optimize for the solution point 0, that has the highest objective
32

---

value. We observe that min, then acts constraint that prevent exploration of measure space regions with objective values below miny.
Finally, we let f(01) f(02) miny. Initially, 01 will be ranked higher than 02. since A1 f(01)- te, =
) -- m and A2 = f(02) - tez = f(02) - y.mnn. thus A > 42. CMA-MAE will thus optimize for 01. but A will decrease because of the update rule fe, (1 after f(01).
Next, we compute how many steps it will take for A = A2. When A = A2. a plateau forms for f- fa and CMA-MAE transitions from optimizing like CMA-ES to expanding the frontier of the known hypervolume via density descent. We leverage Theorem G. that yields closed form for updating cell I times for fixed objective value C: (k(k
(C minn)) a))*
Let 1 and & be the number of times the cells containing 0 and 0 are sampled, respectively. We note that CMA-MAE behaves like CMA-ES until we reach the density descent property, therefore the cell containing 0 will be sampled more times than the cell containing O2 and kj > k2, where the gap 1 2/ grows more optimization steps are taken.
A1 A2
f(01) la = f(02) Lez
f(0,) - (5(0)) (S(01) m1 a) } f(02) [f(02) - (f(02) - m1nz)) =
(1(61) min)) (1 a) (f(02) min )1 - k²
(1 a)
f(02) mins
(1 - ) f(01) - minj
(1 -0)) a) kk l(02) minj
f(01) minf
log ) m
f(02)-ming
k 1:2
log (1 a)
log [ 1 ming
f(0, 1- min
k1
102
(19)
log (1 a)
We note that log (1 a)) is positive value as 1. We see that the number of times that 01 needs to be sampled more than 0₂ depends on the log ratio of the gaps between the objective values and miny and on the learning rate a.
As miny decreases, number of optimization steps required to reach the plateau property approaches O asymptotically. While this shows that min, does have an effect on the behavior of the algorithm, since min, appears the log ratio, we expect the effect of changing miny to be small.
We ran an ablations study by varying miny on the linear projection and arm repertoire domains. We explore different values of miny E {-80. -40, 0, 40, 80). We ran each experimental setup for 20 trials each and report the results in Table 5
We note that each domain remaps the objective values the range [0, 100). For mén, smaller than the range, we observe that changing minn has a negligible effect on performance. On the other hand, positive values for min, constrain the search to solutions with min, (see Fig. 9 thus coverage decreases. These results match our theoretical analysis.
We note that in the LP (plateau) all optimal solutions for each cell are 100 and Arm Repertoire domain all optimal solutions for each cell are close to 100. Since all miny values in our range are below 100, do not observe any effects on performance, even for positive values of minj.
33

---

I. (sphere)
I. (Rastrigin)
LP (plateau)
Arm Repertoine
miny (CMA-MAB)
QD-score
Coverage
QD-score
Coverage
QD-score
Coverage
QD-score
Coverage
-80
64.74
83.73%
52.23
81.65%
77.20
77.24%
78.97
79.25%
-40
64,94
83.83%
52.53
81.40%
78.25
78.28%
79.02
79.26%
0 64,99
83.52%
$2.69
80.56%
79.29
79.31%
79.06
79.27%
63.82
80.08%
68.45%
80.18
80.19%
79.23%
39.41
43.92%
10.03
11.04%
81.42
81.42%
78.99
79.11%
Table 5: Mean QD metrics after 10,000 iterations for CMA-MAE with varying miny initialization.
LP (sphere)
(Rastrigin)
y -00
miny
maRy
miny =
miny
Figure 9: Example heatmaps from the miny ablation. When miny exceeds the objective value for solutions in the elite hypervolume, min, acts constraint on exploration and CMA-MAN focuses on regions of the clite hypervolume that exceed miny y in objective value.
(sphere)
(Rastrigin)
IP (plateau)
Ann Repertoire
1S11
100
Thresbold Percentagg
CMA-ME
MAP-Rllte [lins]
Objective
Objective
50
100
50 Objective
96
98 Objective
1000
50 Objjctive
The percentage of cells in the y-axis with objective values larger than or equal to threshold specified in the x-axis, with 95% confidence intervals. The percentage is the number of filled cells (filtered by the threshold) over the archive size. A larger area under each curve indicates better performance.
Figure 10:
K ADDITIONAL RESULTS
K.1 GENERATED ARCHIVES AND ADDITIONAL METRICS
Table presents the values of the QD-score, coverage, and best solution for each algorithm and domain. We used
0.01 for CMA-MAE, identically the main experiments. Similarly to Fontaine & Nikolaidis 2202 we disambiguate the quality of solutions found and coverage by showing for Elttel MAP-Elites (line), CMA-ME and CMA-MAE the percentage of cells (y-axis) that have objective value greater than the threshold specified in the x-axis (Fig. 10
K.2 EXAMPLE ARCHIVES
Fig.
15
show example archives for each algorithm and domain.
34

---

Linear Projection (sphere)
MAP-Elites
CMA-ME
CMA-MEGA
100
MAP-Elites (line)
CMA-MAE
CMA-MAEGA
Figure 11: Example archives each algorithm for the linear projection (sphere) domain.
Linear Projection (Rastrigin)
MAP-Elites
CMA-ME
CMA-MEGA
100
MAP-Elites (line)
CMA-MAE
CMA-MAEGA
Figure 12: Example archives for each algorithm for the linear projection (Rastrigin) domain.
35

---

Linear Projection (Plateau)
MAP-Elites
CMA-ME
CMA-MEGA
100
MAP-Elites (line)
CMA-MAE
CMA-MAEGA
Figure Example archives for each algorithm for the linear projection (plateau) domain.
Arm Repertoire
MAP-Elites
CMA-ME
CMA-MEGA
100
MAP-Elites (line)
CMA-MAE
CMA-MAEGA
99
Figure 14: Example archives for each algorithm for the arm repertoire domain.
K.3 ADDITIONAL EXPERIMENTS IN THE LSI DOMAIN
We include the same additional experiments in the L.S (StyleGAN) domain as Fontaine & Nikolaidis (222 The first additional experiment has objective prompt "A photo of Jennifer Lopez" and
36

---

Latent Space Illumination (StyleGAN)
MAP-Elites
CMA-ME
CMA-MEGA
100
MAP-Elites (line)
CMA-MAE
CMA-MAEGA
Figure Example archives for each algorithm the LSI (StyleGAN) domain.
Latent Space Illumination (StyleGAN2)
MAP-Elites
MAP-Elites (linc)
CMA-MEGA
CMA-MAEGA
100
Figure 16: Example archives for each algorithm for the LSI (StyleGAN2) domain.
measure prompts "A small child." and "A woman with long blonde hair." The second has objective prompt "A photo of Elon Musk" and measure prompts "A person with red hair." and "A man with blue eyes." T shows the results of the additional runs, as well as the Beyoncé run, with objective prompt "A photo of Beyonce.", from the main paper.
K.4 ADDITIONAL RESULTS FOR VARYING RESOLUTIONS
Fig. 17 shows the QD-score and coverage of CMA-MAE with resolution-dependent archive learning rate and the baselines, for each benchmark domain. For CMA-MAE, set the resolution dependent archive learning rate a using the conversion formula from Appendix G with aj = 0.01 for resolution 100 x 100.
37

---

Lincar Projection (sphere)
Lincar Projection (Rastrigin)
Linear Projection (plateau)
Arm Repertoire
Qoore
CMA-ME ME
MAP-Flites (ine)
100
100
100
Coverage
50
Resolution
500
50
Resolution
500
50
Resolution
500
50
Resolution
500
Figure 17: Final QD-score and coverage of each algorithm for 25 different archive resolutions.
6.0
5.0
A small child.
4.0
3.5
3.0 3.0
3.5
4.0
4,5
5.0
5.5
6.0
A woman with long blonde hair.
Figure 18: latent space illumination collage generated by CMA-MAE for the objective "A photo of Beyonce." and for measures "A small child." and "A woman with long blonde hair." The axis values indicate the score returned by the CLIP model, where lower score indicates better match.
K.5 QUALITATIVE RESULTS IN THE LSI DOMAIN
We present example collages for CMA-MAE (Fig. 99
18 and for CMA-MAEGA (Fig. 21 22
for the LSI (StyleGAN) domain. We also include collages of each run of all algorithms for runs of LSI (StyleGAN) and LSI (StyleGAN2) in the anonymous Dropbox link: https:/ www ACCCAAKK Xg 4TMrhaaxcC25cc77ll
wwtp:///////ch/c//eeee dropbox cwm/ wh/ http:///e22220033332aaaeae/eeee
38

---

6.0
5.0
A small child.
4.0
3.5
3.Q
3.5
4.0
4.5 A woman with lang blonde hair.
5.0
5.5
6.0
Figure latent space illumination (StyleGAN) collage generated by CMA-MAE for the objective "A photo of Jennifer Lopez." and for measures "A small child." and "A woman with long blonde hair." The axes values indicate score returned by the CLIP model, where lower score indicates better match.
6.0
5.5
6
6
A person with red hair.
5.0
4.5
3.5
3.Q
3.0
3.5
4.0
4.5 man with blue eyes.
5.0
5.5
6.0
Figure 20: A latent space illumination (StyleGAN) collage generated by CMA-MAE for the objective "Elon Musk with short hair." and for measures "A man with blue eyes." and "A person with red hair." The axes indicate the returned by the CLIP model, where lower score indicates better match.
39

---

Linear Projection (sphere)
Algorithm
QD-score
Coverage
Best
MAP-Eli
41.64 0.06
50.80
0.09%
98.63 + 0.01
MAP-Elites (line)
49.07 = 0.03
60.42
0.05%
99.43 + 0.01
CMA-ME
36.50 = 0.31
42.82 + 0.40%
100.00 + 0.00
CMA-ME"
45.07 + 0.07
55.11 + 0.10%
99.23 + 0.02
CMA-ME (imp, opt)
37.10 = 0.37
43.62 + 0.45%
100.00 = 0,00
CMA-MAE
64.86 0.04
83.31 + 0.07%
99.59 = 0.01
CMA-MEGA
75.32 0.00
100.00
0.00%
100.00 0.00
CMA-MAEGA
75.39
0.00
100.00 0.00%
100.00 = 0.00
Linear Projection (Rastrigin)
Algorithm
QD-score
Coverage
Best
MAP-Elites
31,43 + 0.07
47.88 + 0.12%
82.16 + 9,11
MAP-Elice (line)
38.29 + 0.05
56.51 + 0.09%
85.71 + 0.07
CMA-ME
38.02 0.11
53.09 + 0.16%
97.59 + 0.06
CMA-ME*
35.06 0.05
53.01 +1 0.12%
83.47 = 0.08
CMA-ME (imp, opt)
34.87 0.24
48.93 0.40%
98.18 = 0.03
CMA-MAE
52.65 = 0.06
80.46 0.11%
95.90 + 0.25
CMA-MEGA
63.07 = 0.00
100.00 + 0.00%
100.00 = 0.00
CMA-MARGA
63.06 + 0.00
100.00 + 0.00% 100.00 + 0.00
Linear Projection (plateau)
Algorithm
QD-score
Coverage
Best
MAP-Elites
47.07 0.17
47.07 + 0.17%
100.00 + 0.00
MAP-Elites (line)
$2.20
52.20 + 0.19%
100.00 + 0.00
CMA-ME
34.54 +: 0.35%
100.00 + 0.00
CMA-ME*
51.11
51.11 + 0.25%
100.00 + 0.00
CMA-ME (imp, opt)
31.91 0.43
31.91 + 0.43%
100.00 + 0.00
CMA-MAE
79.27 0.21
79.29 1 0.21%
100.00 + 0.00
CMA-MEGA
100.00 - 0.00
100.00 1 0.00%
100.00 + 0.00
CMA-MAHGA
100.00 0.00
100.00 0.00%
100.00 + 0.00
Amm Repertoire
Algorithm
QD-score
Coverage
Best
MAP-Elites
71.40
74.09
0.04%
97.38 0.03
MAP-Elites (line)
74.55 0.02
75.61 1 0.02%
99.16 1 0.01
CMA-ME
75.82
75.89 + 0.11%
100.00 + 0.00
CMA-ME'
75.68 0.04
76.13 0.03%
99.78 0.01
CMA-ME (imp. opt)
75.91 0.07
75.99 + 0.07%
100.00 0.00
CMA-MAE
79.03 + 0.02
79.24 + 0.02%
99.93 0.00
CMA-MEGA
75.21 0.13
75.25 + 0.13%
100.00 + 0.00
CMA-MARGA
79.27 + 0.02
79.35 + 0.02%
100.00 + 0.00
Latent Space Illumination (StyleGAN)
Algorithm
QD-score
Coverage
Best
MAP-Elites
12.85 + 0.10
19.42 + 0.16%
71.42
0.14
MAP-Elites (line)
14.40 = 0.09
21.11 0.11%
73.04
0.05
CMA-ME
14.00 + 0.62
19.57 + 0.90%
74.11 0.08
CMA-MAE
17.67 + 0.27
25.08 - 0.40%
73.48 0.18
CMA-MEGA
16.08 0.37
22.58 + 0.57%
74.95 0.27
CMA-MAEGA
16.20 + 0.41
23.83 - 0.46%
75.52 = 0.22
Latent Space Numination (StyleGAN2)
Algorithm
QD-score
Coverage
Best
MAP-ElI Elites
-276.18 + 32.00
4.48 + 0.18%
.936.96 1 35.91
MAP-Elite (line)
-827.25 + 25.99
8.81 - 0.04%
-236.65 1 13.35
CMA-MEGA
9.18 + 0.18
14.91 + 0.12%
67.48 + 0.09
CMA-MAEGA
11.51 + 0.09
18.62 + 0.16%
66.17 + 0.08
Table 6: Results: The QD-rcore, coverage, and best solution after 10,000 iterations for each algorithm and domain with standard errors. Larger values are better across all metrics.
40

---

LSI (StyleGAN): Beyoncé
Algorithm
QD-score
Coverage
Best
MAP-Elites
12.85 0.10
19.42 + 0.16%
71.42
0.14
MAP-Elites (line)
14,40 0.09
21.11 + 0.11%
73.04 1 0.05
CMA-ME
14.00 + 0.62
19.57 + 0.90%
74.11 + 0.08
CMA-MAE
17.67 0.27
25.08 0.40%
73.48 0.18
CMA-MEGA
16.08 + 0.37
22.58
+ 0.57%
74.95 1 0.27
CMA-MAEGA
16.20 + 0.41
23.83 + 0.46%
75.52 + 0.22
1.SI (StyleGAN): Jennifer Lopez
Algorithm
QD-score
Coverage
Best
MAP-Elites
12.51 +: 0.28
19.18 + 0.48%
70.87
0.27
MAP-Elites (line)
14.73 + 0.06
21.60 0.08%
73.50 0.13
CMA-ME
15.24 + 0.37
20.86 0.50%
75.39 = 0.09
CMA-MAE
18.33 + 0.16
25.42 = 0.24%
75.10 0.17
CMA-MEGA
17.06 + 0.10
23.40 = 0.14%
76.02 0.08
CMA-MAEGA
16.45 + 0.27
23.60 + 0.49%
76.42 0.13
LSI (StylcGAN): Elon Musk
Algorithm
QD-score
Coverage
Best
MAP-Elites
13.88 + 0.11
23.15 + 0.14%
69.76
0.07
MAP-Elites (line)
16.54 + 0.28
25.73 + 0.31%
72.63 0.28
CMA-ME
18.96 + 0.17
26.18 0 0.24%
75.84 = 0.10
CMA-MAE
22.10 + 0.31
30.89 + 0.44%
75.25 0.20
CMA-MEGA
21.82 + 0.18
30.73 = 0.15%
76.89 0.15
CMA-MAEGA
19.99 + 0.21
30.12 + 0.42%
77.25 0.18
Table 7: Results from additional runs for Beyoncé, Jennifer Lopez, and Elon Musk
5.5
A small child.
4.5
4.0
3.5
3.0
3.5
4.0
4.5
5.0
5.5
6.0
woman with long blonde hair.
Figure 21: A latent space illumination (StyleGAN) collage generated by CMA-MAEGA for the objective "A photo of Jennifer Lopez." and for measures "A small child." and "A woman with long blonde hair." The axes values indicate the score returned by the CLIP model, where lower score indicates better match.
41

---

6.0
5.5
A &persn with red hair.
5.0
4.0
3.5
9.0
3.5
4.0
4.5 A man with blue eyes.
5.0
5.5
6.0
Figure 22: A latent space illumination (StyleGAN) collage generated by CMA-MAEGA for the objective "Elon Musk with short hair." and for measures "A man with blue eyes." and "A person with red hair." The axes values indicate the score returned by the CLIP model, where lower score indicates better match.
42


Reviews:
[{"review_id": "n8nKsPI0VM", "reviewer": "Reviewer_9oqX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a variant of an already existing algorithm CMA-ME for Qualty-Diversity (QD) problems by introducing a learning rate based annealing function.", "summary_of_the_review": "The paper presents an interesting study with appreciable set of experiments. However, the novelty and innovative content seem somewhat less for a conference like ICLR. ", "strength_and_weaknesses": "Strength:\n\n1) The paper presents a systematic study with adequate empirical experiments.\n\nWeakness:\n\n1) Significance and relevance of QD problem in machine learning along with some warm-up examples should have been given in the introduction.\n\n2) The simple algorithmic change in CMA-ME is seemingly not significant enough to warrant a publication in ICLR. The theoretical proofs seem quite standard and straightforward.\n\n3) For Figure 3, why are you plotting the QD score of different algorithms against number of iterations? WOn't it be such that these different algorithms will perform different amounts of jobs in their inner loops and hence, their \"iterations\" will not consume same amount of time?\n\n4) The proposal was not adequatey validated through comparison against evolutionary algorithms of different genre than CMA-ES, like DE for QD problems. Also the multi-objective optimization approaches like the following one should have been compared:\n\nThomas Pierrot, Guillaume Richard, Karim Beguir, and Antoine Cully. 2022. Multi-objective quality diversity optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '22). Association for Computing Machinery, New York, NY, USA, 139–147. https://doi.org/10.1145/3512290.3528823\n\n5) Why the parametric ANOVA test was used instead of non-parametric statistical tests?\n\n6) Despite focusing on derivative-free QD algorithms, did you really handle a non-dfferentiable function like Weirstrass? Or I am missing something here?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iW-es3P86t", "reviewer": "Reviewer_KKju", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims at improving CMA-ME, a quality-diversity (QD) algorithm. The authors focus on the way that the CMA-ME ranks candidate solutions. The authors hypothesize that the rapid change of the fitness threshold value, denoted by t_e, is the cause of three limitation highlighted in the QD community: prematurely abandoning the objective, struggling to explore flat objectives, and having poor performance for low-resolution archives. The proposed approach changes only the way to update the threshold: introducing a damping factor. \n\nThe proposed approach, CMA-MAE, is compared with CMA-ME, MAP-Elites (line) and MAP-Elites on 5 test problems. Higher QD-score and coverage are observed for all test problems.\n\n", "summary_of_the_review": "It is hard to judge this paper. The technical contribution is minimal. However, this minimal change leads to a statistically significant improvement over the existing approaches. It is not clear how it contributes to ML communities. Probably because of the lack of my knowledge in QD, the significance of the proposed approach may be underestimated. I would currently suggest weak reject, but it may be increased if the authors response convinces me.", "strength_and_weaknesses": "# Strength\n\n* A minimal change to the existing approach, CMA-ME, has been proposed, but a statistically significant improvement has been observed in the benchmark problems.\n\n# Weaknesses\n\nTechnical contribution: A simple approach is nice. However, at the same time, the proposal is incremental and its difference is minimal. \n\nTest problem choice: It has not been discussed why these 5 test problems are selected. Because the selection of test problems is a very important part of the experimental design, this must be carefully explained. In this work, why are these 5 test problems are sufficient to reveal the goodness and limitation of the proposed approaches? \n\nDiscussion on the significance: I understand that the results are statistically significant. However, because I am not very familiar with QD community, it is hard to see whether this improvement is meaningful. A discussion on how meaningful these improvements are would improve the readers' understanding, especially for those who are not familiar with QD, which I guess the most audiences in this conference are.\n\nSignificance of this topic: Because the test problems are selected from the existing work where differentiability is assumed, a possible application of the proposed approach is not clear.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9QGWwkZSdF", "reviewer": "Reviewer_prZ5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a new quality diversity algorithm, CMA-MAE, that try to address some limitations of the baseline algorithm CMA-ME. The authors introduce a learning rate $\\alpha$ into the acceptance threshold, which encourages CMA-MAE to spend more time on the promising zones before transitioning to exploration. The performance of the proposed algorithm is evaluated in three QD benchmark domains and the results show that the proposed algorithm outperforms state-of-the-art QD algorithms.", "summary_of_the_review": "The paper is overall well written and easy to understand. However, the proposed method is very incremental compared with the baseline algorithm, and more convincing experiments are needed to demonstrate the advantages of the method.", "strength_and_weaknesses": "Strength\n\n- The paper is overall well written and easy to understand.\n- The experimental results show that the proposed method is robust and superior to other QD algorithms.\n\nWeaknesses\n\n- The proposed method is very incremental. Compared with CMA-ME, it just adds the smoothing factor to update the acceptance threshold. \n- The experiments are not very convincing. The authors claimed that the modification allows CMA-MAE to spend more time on the promising zones before transitioning to exploration, thus can make CMA-MAE do better on domains with objectives that are hard to optimize as well as domains with flat objective functions. However, in the experiments, in addition to the common benchmarks, the authors only tested the methods on a simple function with the flat property, which makes the results not very convincing. I suggest the authors to conduct experiments on more problems with the mentioned properties.\n- More ablation studies are needed. The performance of CMA-MAE depends on not only the setting of $\\alpha$ but also that of $min_f$. What is the impact of the setting of $min_f$ on the performance?\n- There are some minor problems, for example, in the section on limitations and future work, the order of the two paragraphs may be wrong.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject