Discount Model Search for Quality Diversity Optimization in High-Dimensional Measure Spaces

AI summary

Overview

Research area: Quality diversity (QD) optimization — a branch of stochastic optimization that searches for a collection of solutions that are simultaneously high-performing on an objective and diverse along the outputs of a user-specified measure function. The paper sits at the intersection of evolutionary/black-box optimization, generative modeling, and representation learning.

Technical level: Advanced. The paper assumes familiarity with MAP-Elites-style archives, CMA-ES/CMA-MAE emitters, discount functions, centroidal Voronoi tessellations, and neural network regression.

Scope in one sentence: The paper introduces Discount Model Search (DMS), which replaces CMA-MAE's discrete histogram of discount values with a trained neural network that provides a smooth, continuous discount function, and shows this enables QD to operate in high-dimensional measure spaces — including measure spaces made of images.

What This Paper Is About

QD algorithms try to fill an archive with solutions that each maximize an objective while covering different regions of a measure space. Contemporary QD algorithms are limited to low-dimensional measures because high-dimensional measure spaces suffer from distortion: many solutions map to similar measures, so they fall into the same archive cell and receive identical discount values, giving the search no useful signal and causing it to stagnate. The paper's goal is to fix this stagnation by learning a smooth model of the discount function, which distinguishes between solutions with similar measures and keeps exploration going — even when the measure space is the high-dimensional space of images.

Key Contributions

1. Discount Model Search (DMS). A QD algorithm that searches over a smooth, continuous neural-network representation of the discount function instead of a histogram, so that solutions with similar measures still receive distinct discount values and thus distinct improvement values. A target rule mirroring CMA-MAE's threshold update (with archive learning rate α) is used to regress the model, and "empty points" at the centers of unoccupied archive cells are added to the training data with a target of the minimum objective to clamp the model down in unexplored regions.

2. Benchmarking on standard QD domains. DMS is evaluated on 9 benchmarks — eight instantiations of the Linear Projection (LP) domain (2D/10D/20D/50D LP with the Sphere objective, 2D/10D LP with Rastrigin, and 2D/10D LP with the Flat objective, all with n = 100) plus Arm Repertoire (a 2D planar arm with n = 100 joints) — and compared against CMA-MAE, DDS, MAP-Elites (line), and MAP-Elites.

3. The QDDM setting and two new image-measure domains. The authors propose Quality Diversity with Datasets of Measures (QDDM), in which users specify desired measures by providing a dataset of high-dimensional data (e.g., images) rather than hand-designing a measure function. They introduce Triangle Arrangement (TA), with a 784-dimensional measure space built from 1000 MNIST or Fashion MNIST images (28×28), and Latent Space Illumination (LSI, Hiker), where the measure space is 256×256×3 images and desired measures come from 10,000 LHQ256 landscape images.

Main Findings

• CMA-MAE collapses in high-dimensional measures. In the 10D LP (Sphere) benchmark, CMA-MAE reaches a mean QD Score of 608.53 with 6.95% coverage, versus 6,327.90 and 80.95% in 2D LP (Sphere). DMS reaches 6,409.50 and 89.21% in 10D and 6,978.20 and 95.89% in 2D.

• Distortion is quantified directly. In Figure 1(c), CMA-MAE samples 540 solutions per iteration, and over 20 trials the number of unique archive cells those solutions land in falls to only 30 in 10D LP (Sphere). Both the 2D and 10D benchmarks have archives with 10,000 cells, but the 10D cells are exponentially larger, so more solutions share a discount value.

• DMS outperforms all baselines in the benchmarks. Across the LP variants and Arm Repertoire, DMS had significantly better QD Score and Coverage than all baselines, with one exception: in Arm Repertoire, DDS achieved significantly better coverage (80.24% for DDS versus 80.15% for DMS, though DMS had higher QD Score, 7,963.44 versus 5,568.23).

• DMS beats diversity-only search even on diversity tasks. DDS is a diversity optimization algorithm (it ignores the objective), yet DMS had better coverage in almost all domains, including 2D and 10D LP (Flat), where the objective is always 1.0.

• QDDM results are mixed but favorable. In TA (F-MNIST), DMS significantly outperformed all baselines on both metrics (QD Score 701.14, coverage 72.28%, versus 625.65/63.92% for CMA-MAE). In TA (MNIST), DMS significantly outperformed both MAP-Elites variants but did not significantly differ from CMA-MAE (DMS 951.56 QD / 99.84% coverage; CMA-MAE 954.27 / 99.48%). In LSI (Hiker), DMS significantly outperformed CMA-MAE (214.91 QD / 3.77% coverage vs. 14.61 / 1.56%) but did not significantly differ from the MAP-Elites algorithms, which obtained large negative QD Scores (−51,827.44 and −18,917.87) by generating latent vectors outside the StyleGAN3 training distribution and incurring large regularization losses.

• DMS has a suspected weakness under fine objective optimization. The authors speculate that because the discount model is a learned model, its errors act like noise added to discount values, which may interfere with improvement rankings in domains requiring precise objective optimization such as TA (MNIST). CMA-MAE's exact histogram values would not have this noise.

• DDS could not run in QDDM. The kernel density estimator's runtime grows linearly with measure space dimensionality, so DDS was not run in the QDDM domains.

• Ablation results. The archive learning rate α behaves similarly to CMA-MAE: intermediate values balance objective optimization and measure space exploration, while α = 0 makes DMS over-emphasize the objective. The "empty points" are necessary: setting n_empty = 0 causes performance to drop because the discount model takes arbitrary values in unexplored regions, while n_empty = 10, 100, or 1000 resolves this.

• Computation time. The paper states that wallclock times for all algorithms were recorded and summarized in Table 2, focusing on DMS versus CMA-MAE, but the specific timing numbers are not present in the available content because the text is truncated at that point.

• Statistical treatment. Results come from 20 trials in benchmark domains and 5 trials in QDDM domains. Levene's test showed most settings were non-homoscedastic, so the authors ran Welch's one-way ANOVA per domain per dependent variable (all significant, p < 0.001) followed by Games-Howell pairwise comparisons.

Methodology in Plain English

The researchers start from CMA-MAE, which keeps a histogram over the measure space where each cell stores a "discount value" (an acceptance threshold). A new solution's improvement is its objective minus the discount value at its measures, and this improvement ranks solutions for the CMA-ES emitters. The problem: in high-dimensional measure spaces the cells are enormous, so many solutions land in the same cell, receive the same discount value, and produce identical improvements — the search cannot tell which direction is better.

Their fix is to throw out the histogram and instead train a neural network that maps measure values to discount values. Because the network is continuous, two solutions with slightly different measures get slightly different discount values, preserving the gradient-like signal the emitters need. Architecture is chosen to match the measure type: an MLP for low-dimensional vectors, a convolutional network or transformer if measures are images or text.

Training data comes from two sources. First, every solution the emitters sample contributes a (measure, target) pair, where the target follows the same annealing rule as CMA-MAE's threshold update, parameterized by an archive learning rate α: if the solution's objective does not beat the current predicted discount value, the target stays at that value; otherwise the target is a weighted blend of the objective and the current discount value. This slowly raises discount values in explored regions so the search is pushed toward unexplored ones. Second, the centers (or centroids, for CVT archives) of unoccupied archive cells are added with a target of the minimum objective — this "clamps down" the model in unexplored regions, preventing it from outputting arbitrary high values there.

The archive itself remains MAP-Elites style (retaining the best solution per cell) but no longer stores discount or threshold values. Solutions are sampled from CMA-ES emitters, ranked by improvement as computed through the discount model, and used to update the emitters' Gaussian distributions; converged emitters restart from a random archive solution.

For the new QDDM domains, the archive is a centroidal Voronoi tessellation whose centroids are the points in the user-provided dataset, which partitions only the small region of measure space the user cares about (motivated by the manifold hypothesis — most high-dimensional data lie on a low-dimensional manifold). Distances are chosen per domain: Euclidean distance in TA, and CLIP score in LSI (Hiker) because it is more semantically meaningful. All algorithms were implemented with pyribs.

Why This Matters

Impact on research. The paper reframes a core limitation of QD — distortion in high-dimensional measure spaces — as a modeling problem rather than a resolution problem, unlike the prior suggestion of simply adding more archive cells, whose memory cost grows exponentially with dimensionality. It also proposes QDDM as a new problem setting that shifts measure-function design from hand-crafted code to dataset curation, and shows a learned, smooth discount function can outperform exact discrete histograms in distorted domains while also beating a diversity-only method (DDS) on coverage in nearly every domain tested.

Real-world applications (as motivated or cited in the paper):

• Robotics, e.g., generating diverse behaviors or morphologies (cited as a standard QD application).
• Generative modeling, e.g., producing a variety of images satisfying one prompt rather than a single best image.
• LLM red-teaming, i.e., finding diverse failure modes rather than one.
• Image generation with prompt-like objectives: in LSI (Hiker), specifying "A photo of the face of a hiker" plus a dataset of 10,000 landscape images yields hikers dressed for mountains, beaches, and snow — a natural-language-plus-dataset interface for creative generation.

Industry relevance. Because QDDM uses datasets and foundation-model-style components (StyleGAN3 latent vectors, CLIP scores, LHQ256 images), it connects QD to workflows that machine learning practitioners already run — curating datasets and prompting generative models — potentially lowering the barrier to applying QD in content generation, design exploration, and testing. The paper also flags the compute tradeoff of training a model inside the optimization loop, though the specific wallclock figures appear in Table 2, whose numbers are not in the available content.

Future Directions

• Reduce discount model error. The authors explicitly identify model errors (functioning like noise in discount values) as a likely limitation that hurts DMS in domains requiring fine objective optimization such as TA (MNIST), and call this a suitable target for future exploration.
• Better distance functions for QDDM. The paper notes that Euclidean distance is not always ideal for CVT archive cell assignment, which may be especially true when measures are as high-dimensional as images or text; they used CLIP score for LSI, leaving the general choice open.
• Broaden QDDM beyond images. QDDM is defined for high-dimensional data generally — the paper mentions images, audio, and text — but only image-based domains are demonstrated, and the authors express excitement for other applications that can be framed as QDDM problems.
• Scale to more complex domains. LSI (Hiker) coverage was only 3.77% of the archive (377 hiker images), highlighting how difficult complex QDDM domains remain.

Target Audience

Researchers and practitioners in evolutionary computation and quality diversity optimization who work on MAP-Elites, CMA-MAE, or archive-based methods and are hitting the limits of low-dimensional measure spaces. It is also relevant to machine learning researchers interested in combining black-box optimization with generative models (StyleGAN3), vision-language similarity (CLIP), and dataset-driven task specification. Practitioners applying QD to creative generation, robotics, generative modeling, or red-teaming will find the QDDM framing most directly useful, though the paper requires comfort with CMA-ES internals and statistical benchmarking.

Authors’ abstract

Quality diversity (QD) optimization searches for a collection of solutions that optimize an objective while attaining diverse outputs of a user-specified, vector-valued measure function. Contemporary QD algorithms are typically limited to low-dimensional measures because high-dimensional measures are prone to distortion, where many solutions found by the QD algorithm map to similar measures. For example, the state-of-the-art CMA-MAE algorithm guides measure space exploration with a histogram in measure space that records so-called discount values. However, CMA-MAE stagnates in domains with high-dimensional measure spaces because solutions with similar measures fall into the same histogram cell and hence receive the same discount value. To address these limitations, we propose Discount Model Search (DMS), which guides exploration with a model that provides a smooth, continuous representation of discount values. In high-dimensional measure spaces, this model enables DMS to distinguish between solutions with similar measures and thus continue exploration. We show that DMS facilitates new capabilities for QD algorithms by introducing two new domains where the measure space is the high-dimensional space of images, which enables users to specify their desired measures by providing a dataset of images rather than hand-designing the measure function. Results in these domains and on high-dimensional benchmarks show that DMS outperforms CMA-MAE and other existing black-box QD algorithms.