- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper addresses the problem that the search during optimisation may stop pursuing good search directions due to using the same archive for search and solution storage. I.e. there is a need for stepping stones and measures of intermediate search progress. The proposed solution is to use an empirical measure of past evaluations as a fixed-dimensional state to guide the search to undersupported targets. On several benchmarks, the proposed algorithm outperforms previous algorithms and robot morphology adaptation is also successful.
Critical strengths
- Favourable results: the algorithm gives performance benefits on a wide variety of benchmarks.
- Generalisable method: the principle is generalisable so it can be applied quite generally for QD optimisation.
- Well-chosen baselines for comparison: the comparison includes standard QD algorithms and algorithms that include intermediate-progress based archive improvement evaluation. The authors demonstrate a good awareness of relevant algorithms and state-of-the-art concepts.
Critical weaknesses
- There are no formal guarantees although this is common in the field.
- The paper does not provide much insight into the reason for the success of the algorithm.
Questions for authors
- The Gaussian weights on nearest references. How are these weights and references determined? What advice would there be for practitioners wishing to use your technique?
- The MSG score weights the new behaviour and assigns it a score based on the share ratio (search state (support score) divided by the desired share). The marginal weights are set to decline exponentially with the support score, thereby encouraging the search over undersupported areas in the behaviour space. Are these choices mainly heuristic or is there a guarantee of some kind? A little bit more insight in the experiments comparing the different ways to measure archive process and how it affects the search may also be useful.
- The related work section in the main paper is particularly short. While there is more in the appendix, perhaps this can be slightly expanded.
6 comments
Author Response (Part 2)
4. CMA-ES turns the signal into search. CMA-ES is rank-based: it adapts the mean, step size, and covariance of its sampling distribution from the ordering of candidates alone (Hansen, 2016). It therefore requires only a reliable ordering in each batch, and QDEM provides one even when no candidate improves the archive. With soft assignment, a batch of 540 candidates receives 539–540 distinct credit values; with hard assignment this number drops, in some cases to one, and performance falls on all eleven tasks (Appendix C.10). CMA-ME, CMA-MAE, and DMS also use CMA-ES emitters (Fontaine et al., 2020; Fontaine & Nikolaidis, 2023; Tjanaka et al., 2026), allowing us to compare different search-feedback designs within the same optimizer family. As with these methods, we do not prove global convergence of the resulting search, and we state this explicitly in the revised Discussion (Section 6, L530–531). The evidence in the next step indicates that this does not limit QDEM in practice.
5. The resulting search behaves as the analysis predicts. Steps 1–4 yield a testable prediction: if the generator follows MSG, realized evaluation effort should track the prescribed target shares. Our unequal-target experiment (Appendix C.8) tests exactly this. Changing only the target shares to 25%, 50%, and 75% yields evaluation allocations of approximately 24%, 50%, and 76%.
To examine how different search signals shape search, we additionally analyzed the evaluation allocation of QDEM, DMS, and CMA-MAE on Rastrigin 2D over five seeds (Appendix C.12).
| Metric | CMA-MAE | DMS | QDEM |
|---|---|---|---|
| Final QD Score ↑ | 5,276.41 ± 14.38 | 5,723.88 ± 85.96 | 5,916.63 ± 36.07 |
| Coverage (%) ↑ | 80.13 ± 0.38 | 91.53 ± 2.64 | 93.34 ± 0.55 |
| Late top-10 cell evaluation share (%) ↓ | 21.83 ± 1.50 | 40.30 ± 5.28 | 7.84 ± 1.49 |
| Late effective cells ↑ | 139.93 ± 23.27 | 44.32 ± 8.97 | 676.51 ± 195.62 |
Mean ± sample SD over five seeds. “Late” refers to the final 540,000 evaluations. Effective cells are calculated as , where is the evaluation share of cell within this window.
QDEM allocates substantially less of its budget to the most-visited cells, maintains a broader visitation distribution, and achieves the highest mean final QD Score and Coverage. The heatmaps in Appendix C.12 show the same pattern over time: DMS increasingly concentrates evaluations near the boundaries, CMA-MAE shows less severe but still localized concentration, and QDEM remains broadly distributed. We interpret this as follows. Archive-relative signals evaluate candidates against archive-derived quality thresholds or estimates, which can concentrate search where such feedback continues to reward progress. QDEM can instead credit contributions to under-supported targets even without immediate archive improvement, consistent with the broader exploration observed here.
The same behavior appears on Hiker, where QDEM allocates 26% of its budget to the ten most-visited regions compared with 62% for DMS (Appendix C.1). Finally, replacing MSG with a kNN novelty score, with all other settings fixed, lowers QD Score and Coverage on all eleven tasks (Appendix C.11). Taken together, these results are consistent with the mechanism identified by the analysis and support it as a main source of the empirical gains.
We appreciate the reviewer's insightful comments, which helped us better articulate the mechanisms underlying QDEM's empirical success in the revised Discussion and strengthen the overall argument of our paper.
Author Response (Part 3)
Q1. The Gaussian weights on nearest references. How are these weights and references determined? What advice would there be for practitioners wishing to use your technique?
We appreciate the reviewer's questions about the implementation details and practical use of QDEM. Following your questions, we have also added explicit references in Section 4.1 (L183–188) to the detailed formulas and settings in the appendix, making them easier for readers to locate.
How references and weights are determined:
-
References: References are fixed before search, and their resolution can be chosen independently of the reporting archive. When a representative target dataset is available, we use its behavior representations, following the reference-defined target setting of QDDM (Tjanaka et al., 2026): the 10,000 test images for TA and the CLIP embeddings of 10,000 LHQ landscape images for Hiker. Otherwise, we cover the prescribed behavior range directly: 100,000 uniformly sampled points for each numerical descriptor dimensionality, shared across tasks of the same dimensionality and across seeds, and a regular 20 × 20 grid for discrete robot descriptors (Appendices B.3–B.5).
-
Gaussian weights: Each valid evaluation contributes one unit of support across its nearest references, with weights proportional to and normalized to sum to one (Eq. A.1). We use on numerical tasks, 64 on TA, and 160 on Hiker.
-
Bandwidth: The bandwidth is computed once from the reference set itself using a typical inter-reference distance (Eq. B.1), which sets the scale of Gaussian weight decay within each local neighborhood. It remains fixed throughout search.
Practical recommendations:
-
Reference resolution and neighborhood size. We recommend choosing references that cover the behavioral regions of interest relatively uniformly and densely enough to distinguish meaningful behaviors, while avoiding unnecessary computational cost. A useful starting point is to scale proportionally with the reference count . Our sensitivity results (Appendix C.6) show that larger reference configurations generally benefit higher-dimensional numerical tasks. We also recommend soft assignment for continuous behavior spaces.
-
Independence from the reporting archive. An important advantage of QDEM is that search-reference resolution can be chosen independently of the reporting archive. Fine-grained references can provide detailed search guidance while a coarser archive retains and reports results, making search more flexible without being constrained by archive resolution. Moreover, if evaluated solutions are logged, the reporting archive can be reconstructed at different resolutions after optimization through simple post-processing, without rerunning the search. We strongly encourage practitioners to take full advantage of this flexibility.
-
Quality–support balance. We recommend starting with a moderate , chosen according to the quality loss practitioners are willing to accept for additional exploration. Since the support term is normalized to , bounds the quality disadvantage that additional support can compensate. On our normalized numerical benchmarks, values around 0.35–0.5 generally perform well (Appendix C.5). An excessively large value may sacrifice the quality aspect of QD, while a value that is too small may compromise its diversity aspect.
We have also incorporated some of these practical considerations into Section 6 (Discussion, L524–530) to make QDEM easier to understand and apply.
Author Response (Part 1)
We sincerely thank you for your careful reading and your thoughtful, insightful review. We particularly appreciate your recognition of our favorable experimental results, the generalizability of our method, and the well-chosen baselines for comparison. We are also grateful for your detailed and constructive suggestions on how to provide deeper insights into why QDEM succeeds. We are pleased to address the points you raised.
We read these three points as asking two things: whether the design choices behind MSG are principled or mainly heuristic, and why QDEM succeeds, particularly how its feedback guides search differently from archive-progress signals.
In brief, MSG has a principled structure: it is derived from a utility that, for fixed total support, is maximized exactly at the desired target allocation (Proposition 2). The exponential weighting is one choice within this structure. Although these theoretical properties do not guarantee global convergence of the CMA-ES-based search, our experiments show that the intended guidance translates into effective search behavior in practice. MSG can continue to distinguish contributions to under-supported targets even when the archive is not improving, whereas archive-progress signals may provide limited guidance for continuing exploration in this situation.
Following your suggestions, we added an evaluation-allocation analysis with heatmaps on Rastrigin 2D (Appendix C.12), comparing how QDEM, DMS, and CMA-MAE distribute evaluations throughout search. We have also expanded the explanation of this mechanism in the Discussion (Section 6, L510–518). We explain these points in five steps below, with evidence at each step.
1. References let QDEM track how much support each target has received. QDEM places a fixed set of reference points in the behavior space as targets. Every valid evaluation, whether or not the archive retains it, adds one unit of support to the references near its behavior. Accumulating these contributions gives the search state St, where St,j is the total support that target j has received so far.
2. MSG identifies where support is lacking. For a candidate with behavior z,
MSGt(z)=∑jψt′(St,j/πj)wj(z),
where St,j/πj is the support that target j has received relative to its desired share, and ψt′ is a decreasing marginal weight. A candidate scores highly when its evaluation would contribute to targets that are behind their intended share. Both ingredients of this credit matter empirically. Shuffling MSG among candidates while keeping the same history sharply reduces coverage on every task (Appendix C.3), and restricting support to recent or top-quality evaluations also reduces coverage on every task (Appendix C.2).
3. Proposition 2 specifies what this signal aims at. MSG is not an ad hoc score. It is the directional derivative of the utility
Ut(S;T)=∑jπjψt(Sj/πj)
along the candidate’s support contribution. Proposition 2 shows that, for any fixed total support N, Ut(S;T)≤ψt(N), with equality if and only if S=Nπ under strict concavity. Intuitively, the evaluation budget is a resource shared among targets, and with diminishing returns it is best spent when every target has received its intended share. MSG therefore points toward the prescribed allocation, and once that allocation is reached it is identical for all candidates, so no region is favored further. The exponential decay is one smooth choice satisfying this diminishing-return principle, similar to concave saturation functions used in probabilistic coverage (Lv et al., 2026). Appendix C.7 shows that reciprocal weights perform similarly on most tasks, while linear-hinge weights are more task-dependent.