Technical Summary: Discount Model Search for Optimizing Quality Diversity in High-Dimensional Measure Spaces

Problem Definition

Optimizing Quality Diversity (QD) aims to discover a collection of solutions that maximize an objective function $f$ while simultaneously covering a diverse range of outputs defined by a user-specified, vector-valued measure function $m$. The image of $m$ constitutes the measure space $S$. A critical limitation of current QD algorithms, particularly State-of-the-Art methods like Covariance Matrix Adaptation MAP-Annealing (CMA-MAE), is their inability to scale effectively to high-dimensional measure spaces.

In high-dimensional spaces, algorithms suffer from distortion, a phenomenon where large volumes of the solution space map to small regions of the measure space. CMA-MAE addresses the QD objective by maximizing "archive improvement," defined as $\Delta(\theta) = f(\theta) - f_A(m(\theta))$, where $f_A$ is a discount function. CMA-MAE represents $f_A$ as a discrete histogram (a tessellation of cells). In high-dimensional settings, distortion causes many distinct solutions to fall into the same histogram cell and be assigned identical discount values. Consequently, the algorithm cannot distinguish between solutions with similar measures, leading to inaccurate improvement signals and search stagnation. Furthermore, designing low-dimensional measure functions for complex domains (e.g., specifying "where a hiker is located") is often tedious and unintuitive.

Methodology: Discount Model Search (DMS)

To address these limitations, the authors propose Discount Model Search (DMS). Instead of a discrete histogram, DMS uses a neural network to learn a smooth, continuous representation of the discount function $f_A$.

Core Components

1. Discount Model ($\hat{f}_A$): A neural network, parameterized by $\psi$, which takes measure values $s = m(\theta)$ as input and outputs a scalar discount value. The architecture is flexible: Multi-Layer Perceptrons (MLPs) are used for low-dimensional vector measures, while Convolutional Networks or Transformers are suitable for high-dimensional data such as images.
2. Archive and Emitters: DMS maintains an archive in the MAP-Elites style, storing the best-found solutions. It utilizes CMA-ES-based emitters that sample solutions from a Gaussian distribution. Unlike CMA-MAE, the archive does not store discrete discount values; instead, the discount model is queried to compute improvement values: $\Delta_i = f(\theta_i) - \hat{f}_A(m(\theta_i))$.
3. Training the Discount Model: The model is trained to approximate the threshold update rule used in CMA-MAE. The training dataset $D_A$ consists of two sources:
   • Emitter Samples: For each sampled solution $\theta$, the target discount value $t_A$ is updated based on whether the solution's objective value $f(\theta)$ exceeds the model's current prediction $\hat{f}_A(s)$. If $f(\theta) > \hat{f}_A(s)$, the target is a linear combination of the objective value and the current discount value, controlled by an archive learning rate $\alpha$.
   • Empty Points: To prevent the model from arbitrarily assigning high values to unexplored regions of the measure space, the algorithm samples the centers of unoccupied archive cells and assigns them a target value of $f_{min}$ (the minimum objective value). This "pushes" the model down in unexplored areas and ensures emitters are directed toward exploring new regions.

Theoretical Insight

By replacing the discrete histogram with a continuous function, DMS can assign different discount values to solutions even when they map to similar measures in a high-dimensional space. This enables the algorithm to maintain a gradient of improvement signals, prevents stagnation, and allows for continued exploration long after histogram-based methods would have failed.

Main Contributions

1. Discount Model Search (DMS): A novel QD algorithm that uses a smooth, continuous discount model to guide exploration in distorted, high-dimensional measure spaces.
2. Quality Diversity with Datasets of Measures (QDDM): The authors introduce a new setting where users specify desired measures via a dataset (e.g., a collection of images) rather than manually designing a measure function. This treats the high-dimensional space of the dataset (e.g., the space of images) as the measure space.
3. New Domains: Two QDDM domains are proposed and evaluated:
   • Triangle Arrangement (TA): Arranging triangles to match images from MNIST or Fashion MNIST.
   • Latent Space Illumination (LSI) (Hiker): Generating face images of hikers in diverse landscapes using StyleGAN3, where the measure space is the space of landscape images.
4. Empirical Validation: Comprehensive benchmarks demonstrate that DMS outperforms CMA-MAE, DDS, and MAP-Elites variants on both standard benchmarks and the new QDDM domains.

Experimental Results

The authors evaluated DMS on 9 standard benchmarks (including Linear Projection and Arm Repertoire) and 3 QDDM domains.

• Benchmark Domains: DMS significantly outperformed all baselines in most high-dimensional settings (e.g., 10D, 20D, 50D LP benchmarks) regarding the QD score (sum of objective values in the archive) and coverage (percentage of filled archive cells). Notably, in the 10D LP (Sphere) benchmark, CMA-MAE's coverage dropped to 6.95%, while DMS achieved 89.21%.
• QDDM Domains:
  • In TA (F-MNIST), DMS significantly outperformed all baselines in both metrics.
  • In TA (MNIST), DMS matched CMA-MAE in coverage but significantly outperformed MAP-Elites variants in QD score. The authors note that DMS did not significantly outperform CMA-MAE in QD score here and speculate that noise introduced by the neural network approximation might hinder fine-grained objective optimization in tasks with low distortion and high precision.
  • In LSI (Hiker), DMS significantly outperformed CMA-MAE, achieving a QD score of 214.91 compared to 14.61, and a coverage of 3.77% (377 unique hiker images). The authors note that MAP-Elites variants achieved high coverage but with strongly negative QD scores due to generating images outside the generator's training distribution.
• Computational Cost: DMS incurs higher computational costs than CMA-MAE due to training the discount model, particularly in low-dimensional benchmarks. However, in QDDM domains where image generation is the bottleneck, this overhead is less noticeable.

Significance and Claims

The work claims that DMS offers two primary advantages:

1. Improved Performance: DMS improves performance in current QD applications by overcoming the distortion effects that plague high-dimensional measure spaces and outperforming State-of-the-Art black-box algorithms.
2. Accessibility and New Applications: By introducing the QDDM setting, DMS makes QD more accessible. It removes the need for manual, hand-crafted measure functions and allows users to specify diversity goals simply by providing a dataset. This enables the specification of complex, high-dimensional measures (such as visual styles or semantic locations) that are difficult to represent via low-dimensional vectors.

The authors conclude that given the ubiquity of datasets in machine learning, formulating problems as QDDM and solving them with DMS is a promising direction. They acknowledge limitations, including the computational cost of model training and the potential hindrance of fine-tuning by approximation noise, and suggest future work on more advanced model architectures and alternative training objectives.