Scaling Policy Gradient Quality-Diversity with Massive Parallelization via Behavioral Variations
Konstantinos Mitsides, Maxence Faldor, Antoine Cully · 2025
Read Scaling Policy Gradient Quality-Diversity with Massive Parallelization via Behavioral Variations by Konstantinos Mitsides, Maxence Faldor, Antoine Cully (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18723.txt.
Introduction
Konstantinos Mitsides, Maxence Faldor, and Antoine Cully scale a diversity-seeking optimizer by letting gradient-trained variants flood modern parallel hardware. Quality-diversity methods build a whole collection of solutions that are both strong and different from each other, like MAP-Elites. Classic versions mutate at random, which stalls in high dimensions. Gradient-based variants learn better moves but train slowly or resist massive parallel runs. Their 2025 paper scales policy gradient quality-diversity through behavioral variations, differences in what a solution does, exploited across many parallel workers.
A diverse archive is insurance: when conditions change, some member already fits. Robotics uses such archives for damage recovery. The authors attack the speed wall that kept gradient versions small. Their scaling recipe aims at neuroevolution on big controllers. The work treats variety as an engineering resource worth computing at scale.
Catalog record
| CREATOR | Konstantinos Mitsides, Maxence Faldor, Antoine Cully |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18723
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scaling Policy Gradient Quality-Diversity with Massive Parallelization via Behavioral Variations Konstantinos Mitsides, Maxence Faldor, Antoine Cully Abstract . Quality-Diversity optimization comprises a family of evolutionary algorithms aimed at generating a collection of diverse and high-performing solutions. MAP-Elites (ME), a notable example, is used effectively in fields like evolutionary robotics. However, the reliance of ME on random mutations from Genetic Algorithms limits its ability to evolve high-dimensional solutions. Methods proposed to overcome this include using gradient-based operators like policy gradients or natural evolution strategies. While successful at scaling ME for neuroevolution, these methods often suffer from slow training speeds, or difficulties in scaling with massive parallelization due to high computational demands or reliance on centralized actor-critic training. In this work, we introduce a fast, sample-efficient ME based algorithm capable of scaling up with massive parallelization, significantly reducing runtimes without compromising performance. Our method, ASCII-ME, unlike existing policy gradient quality-diversity methods, does not rely on centralized actor-critic training. It performs behavioral variations based on time step performance metrics and maps these variations to solutions using policy gradients. Our experiments show that ASCII-ME can generate a diverse collection of high-performing deep neural network policies in less than 250 seconds on a single GPU. Additionally, it operates on average, five times faster than state-of-the-art algorithms while still maintaining competitive sample efficiency. Figure 1. The ASCII-ME method employs two distinct variation operators within the standard MAP-Elites loop: (1) Iso+LineDD, which mutates a parent genotype based on that of a randomly selected elite; (2) ASCII, which interpolates between the parent’s behavior and another behavior sampled from the buffer, using performance metrics encapsulated in \bm{Z} . The behavioral changes are then mapped to the genotypic space by \bm{J} to mutate the parent genotype. 1. Introduction Quality-Diversity (QD) optimization is a family of evolutionary algorithms designed to generate a collection of solutions that are diverse and high-performing ( Chatzilygeroudis et al., 2020 ; Cully and Demiris, 2017 ; Pugh et al., 2016 ) . Unlike traditional optimization methods that focus on identifying a single optimal solution, QD optimization encourages local competition among groups of solutions with similar characteristics to identify the fittest solution within each group. By maintaining a diverse collection of solutions — acting as “stepping stones” — QD avoids local optima and explores multiple search space regions. This approach reduces the risk of premature convergence, facilitates the discovery of innovative and globally optimal solutions that traditional methods often miss ( Chalumeau et al., 2023b ; Ecoffet et al., 2021 ; Gaier et al., 2019 ; Mouret and Clune, 2015 ) , and enables rapid adaptation to unforeseen downstream tasks ( Cully et al., 2015 ) . In general, QD has shown benefits across a variety of applications, from robotics ( Cully et al., 2015 ) to design ( Gaier et al., 2018 ) and content generation ( Gravina et al., 2019 ) . A prominent algorithm in QD is MAP-Elites (ME) ( Mouret and Clune, 2015 ) , which is a straightforward yet potent and versatile method ( Alvarez et al., 2022 ; Gaier et al., 2017 ) . Recently, it has been employed to generate diverse adversarial prompts ( Samvelyan et al., 2024 ) , significantly enhancing the adversarial resilience of large language models, such as Llama 3.1 ( et al., 2024 ) . ME utilizes Genetic Algorithms (GAs) and typically employs the Directional Variation (Iso+LineDD) operator to apply random mutations to solutions, facilitating navigation within the search space. Notably, although conducting more solution evaluations in parallel reduces the total number of iterations when the evaluation budget is fixed, ME’s performance remains stable and even drastically reduces its runtime, thereby showcasing strong scalability ( Lim et al., 2022 ) . Nevertheless, its reliance on genetic variation operators lead to slow convergence in expansive search spaces, making it less effective for evolving large deep neural networks (DNNs) ( Cully et al., 2015 ; Cully and Demiris, 2017 ; Mouret and Clune, 2015 ) . Methods proposed to overcome this limitation include replacing or augmenting the mutation operators of ME with other gradient-based variation operators, such as policy gradients (PG) ( Williams, 1992 ; Sutton et al., 1999 ) or natural gradients in the form of evolution strategies (ES) ( Wierstra et al., 2011 ; Salimans et al., 2017 ) . ES-based ME algorithms have successfully scaled ME to neuroevolution. However, their reliance on numerous samples to estimate gradients renders them sample-inefficient and computationally demanding, limiting their practicality compared to PG methods ( Colas et al., 2020 ; Flageat et al., 2024 ; Salimans et al., 2017 ) . Conversely, PG-based ME algorithms integrate ME with Deep Reinforcement Learning (DRL) ( Mnih et al., 2013 ; Mnih et al., 2015 ) by using PGs from a centralized actor-critic (AC) method ( Konda and Tsitsiklis, 1999 ; Sutton et al., 1999 ) to mutate solutions. While this AC training has helped ME achieve state-of-the-art performance in QD-RL tasks ( Flageat et al., 2022 ) in terms of sample efficiency ( Nilsson and Cully, 2021 ; Faldor et al., 2024 ; Faldor et al., 2023 ) , it undermines ME’s potential for speed and scalability. AC training is constrained by its reliance on numerous sequential iterations necessary for convergence, which inherently slows down performance enhancement. Moreover, within a fixed evaluation budget, the necessity to increase parallel evaluations consequently reduces the total number of iterations possible, thus limiting the training’s overall effectiveness and scalability. In this work, we aim to efficiently evolve a collection of diverse high-performing large DNN policies, while ensuring rapid execution and scalability with massive parallelization. Specifically, we make the following contributions: (1) We introduce a PG-based variation operator, ASCII, unique among PG-based QD methods as it does not rely on centralized AC training. Utilizing the Markov Decision Process (MDP) framework, it interpolates between solution behaviors based on time step performance metrics to generate new desired behaviors. This mirrors the Iso+LineDD approach but operates in the behavior space, allowing efficient biasing of variations. Employing PGs, it then maps these behavioral changes into the solution space to mutate the solutions. (2) We integrate ASCII with ME to develop ASCII-ME, which uses both the PG-based operator, ASCII, and the genetic operator, Iso+LineDD, to mutate solutions (see Figure 1 ). (3) We compare our method’s sample and runtime efficiency across five continuous control locomotion tasks, demonstrating that it consistently outperforms established baselines in balancing these efficiencies. (4) We conduct an extensive analysis of how parallel evaluations affect each baseline’s performance and runtime under a fixed evaluation budget. Our experimental results show that ASCII-ME robustly scales up with an increasing number of parallel evaluations, significantly decreasing runtimes without compromising performance. (5) We evaluate the synergy between our operator, ASCII, and Iso+LineDD, as well as their contribution to enhancing the collection of solutions in terms of both diversity and performance. To the best of our knowledge, ASCII-ME is the first PG-based QD algorithm that does not rely on AC methods, while still capable of evolving DNN policies with thousands of parameters at competitive sample and runtime efficiency. This, combined with its strong scalability on a single GPU, underscores the potential of this promising new framework for non-AC PG-based QD methods. 2. Background