Benchmark Tasks for Quality-Diversity Applied to Uncertain Domains

Manon Flageat, Luca Grillotti, Antoine Cully

TL;DR

This paper introduces the first systematic benchmark suite for Uncertain Quality-Diversity (UQD), a subfield of optimization that seeks diverse, high-performing solutions in noisy environments. By providing eight standardized tasks based on the "Redundant Arm" environment, the authors offer a rigorous way to evaluate how well algorithms estimate performance and prioritize reproducible solutions in the face of stochasticity.

What Problem Does This Paper Address?

Quality-Diversity (QD) algorithms, like the popular MAP-Elites, are designed to find a "collection" of solutions that are both high-performing (quality) and behaviorally different (diversity). For example, in robotics, a QD algorithm might find 1,000 different ways for a robot arm to reach a specific point.

However, most QD algorithms assume the world is deterministic. In reality, environments are "uncertain": evaluating the same solution twice might yield different fitness scores or different behavioral descriptors due to sensor noise or physical variability. Standard QD algorithms often fall into the "lucky outlier" trap—they keep solutions that performed well once by chance but are actually mediocre. This paper addresses the lack of standardized benchmarks to test how UQD algorithms handle these "illusory" results.

Methods

The authors propose a framework for defining UQD tasks based on three key properties:

  1. Uncertainty Location: Where the noise is introduced (e.g., on the fitness score after evaluation, on the behavioral descriptor, or on the "phenotype" parameters like joint angles).
  2. Distribution Type: The shape of the noise (e.g., Gaussian/Normal distribution vs. Bimodal distributions with two peaks).
  3. Parameters: The scale of the noise (e.g., variance).

Using these properties, they created 8 benchmark tasks categorized into three goals:

  • Performance Estimation: Testing if an algorithm can correctly estimate the expected fitness and descriptor of a solution.
  • Reproducibility Maximization: Testing if an algorithm can find solutions that consistently end up in the same behavioral niche (low variance).
  • Realistic Combination: A task that blends both challenges by applying noise directly to the robot's joint angles (phenotype noise).

Datasets

The benchmarks are built upon the Redundant Arm environment, a standard in the QD community. It involves a simulated planar robotic arm with multiple joints. The goal is to reach as many points in its workspace as possible.

  • The Base Task: A 2D workspace where the "descriptor" is the (x, y) position of the arm's tip.
  • The New Benchmarks: The authors released their code as part of the QDax library, making these 8 noisy variants easily accessible for researchers.

Key Insights and Ideas

  • The "Lucky" Problem: In noisy domains, standard MAP-Elites creates an "Illusory Archive"—a map that looks full of high performers but collapses when those solutions are re-evaluated (the "Corrected Archive").
  • Sampling isn't a Silver Bullet: While taking multiple samples and averaging them helps with Gaussian (Normal) noise, the authors show it can actually be detrimental in bimodal noise scenarios. If a solution has a small chance of a very bad outcome, a few samples might miss it entirely, leading the algorithm to over-trust a risky solution.
  • Reproducibility as a Feature: The paper highlights that in many real-world tasks, we don't just want the "best" solution on average; we want the one that is most likely to behave the same way every time. They show that standard algorithms fail to distinguish between a "reliable" solution and a "jittery" one if they both have the same average behavior.

Key Results

The authors evaluated standard MAP-Elites and a sampling-based version (MAP-Elites-sampling) across their tasks:

  • Descriptor Noise is Hard: When noise is applied to the behavioral descriptor (where the solution "lives" in the archive), performance drops significantly. If the noise is large enough, solutions are almost never placed in the correct niche.
  • Bimodal Failure: In the "Bimodal Fitness" task, MAP-Elites-sampling actually performed worse than the standard version because it was more likely to be misled by the complex distribution of the noise.
  • The Gap: The results quantitatively demonstrate a massive gap between "Illusory" performance (what the algorithm thinks it found) and "Corrected" performance (what is actually true), providing a clear baseline for future UQD algorithms to improve upon.

Limitations and Future Work

The primary limitation is that all eight tasks are based on the Redundant Arm, which is a relatively simple, low-dimensional environment. While this makes the benchmarks lightweight and easy to run, it doesn't capture the complexities of high-dimensional "Deep RL" style tasks or environments with dynamic, changing noise.

The authors suggest that future work should expand these uncertainty definitions to more complex simulators (like those used in evolutionary robotics) and develop new algorithms specifically designed to maximize the "Reproducibility-Score" introduced in this paper.

Summary updated

Abstract

While standard approaches to optimisation focus on producing a single high-performing solution, Quality-Diversity (QD) algorithms allow large diverse collections of such solutions to be found. If QD has proven promising across a large variety of domains, it still struggles when faced with uncertain domains, where quantification of performance and diversity are non-deterministic. Previous work in Uncertain Quality-Diversity (UQD) has proposed methods and metrics designed for such uncertain domains. In this paper, we propose a first set of benchmark tasks to analyse and estimate the performance of UQD algorithms. We identify the key uncertainty properties to easily define UQD benchmark tasks: the uncertainty location, the type of distribution and its parameters. By varying the nature of those key UQD components, we introduce a set of 8 easy-to-implement and lightweight tasks, split into 3 main categories. All our tasks build on the Redundant Arm: a common QD environment that is lightweight and easily replicable. Each one of these tasks highlights one specific limitation that arises when considering UQD domains. With this first benchmark, we hope to facilitate later advances in UQD.
BibTeX
@inproceedings{flageat2023benchmark,
  author = {Manon Flageat and Luca Grillotti and Antoine Cully},
  title = {{Benchmark Tasks for Quality-Diversity Applied to Uncertain Domains}},
  booktitle = {Gecco Companion},
  year = {2023},
  doi = {10.1145/3583133.3596326},
}

Loading related content...

Figure