Differentiable Quality Diversity

Matthew Christopher Fontaine, Stefanos Nikolaidis

Abstract

Quality Diversity (QD) optimization aims to find a collection of high-performing, diverse solutions. Traditional QD methods treat functions as black boxes, limiting their scalability in high-dimensional spaces. This paper introduces Differentiable Quality Diversity (DQD), a framework that leverages gradient information from both objective and diversity measures. We present MEGA (MAP-Elites via a Gradient Arborescence), which uses these gradients to significantly outperform black-box baselines. Our results across robotics and generative modeling tasks demonstrate that DQD can achieve up to 100x improvements in efficiency and far greater archive coverage.

Introduction

Quality Diversity (QD) optimization is a paradigm that seeks not just a single global optimum, but a diverse set of high-performing solutions. This is crucial in fields like robotics, where multiple movement strategies might be needed, or creative design, where a variety of high-quality outputs is desired. However, traditional QD algorithms, such as MAP-Elites, treat the objective and diversity measures as "black boxes." This approach relies on random perturbations, which becomes prohibitively inefficient as the dimensionality of the search space increases.

Differentiable Quality Diversity (DQD)

In the era of deep learning, many objective and measure functions are implemented as neural networks, making them inherently differentiable. This paper proposes Differentiable Quality Diversity (DQD), a framework that utilizes these gradients to guide the search process. Instead of wandering blindly, the algorithm uses the "compass" of gradients to move towards regions of higher quality and greater diversity simultaneously.

The MEGA Framework

The authors introduce MEGA (MAP-Elites via a Gradient Arborescence) to implement the DQD framework. The central innovation is the Gradient Arborescence, a branching structure that explores the landscape by following various combinations of objective and measure gradients.

The CMA-MEGA algorithm loop: sampling coefficients, branching via gradients, updating the archive, and adapting the search distribution.

A key variant, CMA-MEGA, employs the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) to learn the optimal distribution of gradient coefficients. By adapting this distribution, the algorithm can discover narrow paths to unexplored regions of the feature space that would be nearly impossible to find via random search. Other variants include OMG-MEGA, which uses fixed linear combinations of gradients, and CMA-MEGA (Adam), which incorporates the Adam optimizer to handle ill-conditioned landscapes.

Experimental Evaluation

The effectiveness of DQD was evaluated across three challenging domains:

  1. Linear Projection: A synthetic benchmark using Sphere and Rastrigin functions to test archive coverage.
  2. 1000-DOF Arm: A robotics task finding joint configurations for a high-dimensional planar arm to reach all possible $(x, y)$ positions.
  3. Latent Space Illumination (LSI): Using StyleGAN and CLIP to find diverse latent codes that generate images matching a specific prompt while varying across semantic measures.

Key Results

The results show that DQD is a massive leap forward in efficiency and coverage. In the 1000-DOF arm task, MEGA achieved superior results in just 10,000 iterations compared to the 1,000,000 iterations required by traditional black-box methods—a 100x improvement.

Comparison of QD-Score and archive coverage across different tasks. CMA-MEGA variants consistently outperform black-box baselines like MAP-Elites and CMA-ME.

Furthermore, in the Linear Projection task, CMA-MEGA achieved 100% coverage of the archive, while standard MAP-Elites and even the adaptive CMA-ME struggled to reach 2%. In the StyleGAN domain, CMA-MEGA successfully generated a smooth, diverse grid of high-quality faces from a single optimization run, outperforming baselines that produced fewer and lower-quality variations.

Conclusion and Future Work

Differentiable Quality Diversity represents a significant advancement in optimization. By leveraging gradient information, DQD algorithms like MEGA can explore high-dimensional spaces with unprecedented efficiency. While challenges remain regarding ill-conditioned landscapes and the assumption of deterministic gradients, DQD opens new possibilities for complex design and discovery tasks where diversity and quality are both paramount. Future work will focus on adapting these methods for the stochastic gradients common in large-scale deep learning.

Summary updated

Abstract

Quality diversity (QD) is a growing branch of stochastic optimization research that studies the problem of generating an archive of solutions that maximize a given objective function but are also diverse with respect to a set of specified measure functions. However, even when these functions are differentiable, QD algorithms treat them as "black boxes", ignoring gradient information. We present the differentiable quality diversity (DQD) problem, a special case of QD, where both the objective and measure functions are first order differentiable. We then present MAP-Elites via a Gradient Arborescence (MEGA), a DQD algorithm that leverages gradient information to efficiently explore the joint range of the objective and measure functions. Results in two QD benchmark domains and in searching the latent space of a StyleGAN show that MEGA significantly outperforms state-of-the-art QD algorithms, highlighting DQD's promise for efficient quality diversity optimization when gradient information is available. Source code is available at https://github.com/icaros-usc/dqd.
BibTeX
@inproceedings{fontaine2021differentiable,
  author = {Matthew Christopher Fontaine and Stefanos Nikolaidis},
  title = {{Differentiable Quality Diversity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=uJGObgFU0lU},
}
Figure