Source-linked AI summary
Covariance Matrix Adaptation for the Rapid Illumination of Behavior Space
Matthew C. Fontaine, Julian Togelius, Stefanos Nikolaidis, Amy K. Hoover
TL;DR
The paper addresses the challenge of finding diverse, high-quality solutions efficiently in complex continuous domains. It introduces CMA-ME, which combines CMA-ES adaptation with MAP-Elites archiving and behavioral mapping. Across toy optimization and Hearthstone experiments, CMA-ME improves solution quality and behavioral coverage relative to established baselines.
Problem
Quality-diversity methods seek diverse quality solutions but require many evaluations in continuous spaces, while CMA-ES primarily targets a single optimum.
Method
CMA-ME combines CMA-ES self-adaptation with MAP-Elites archiving, using CMA-ES seeded by archived solutions to explore and optimize behavior space.
Results
CMA-ME improves both coverage and solution quality over MAP-Elites, while Hearthstone results show better quality and diversity than standard CMA-ES and MAP-Elites.
Takeaways & Limitations
The results support augmenting quality-diversity algorithms with modern optimization mechanisms for simultaneous exploration and optimization of continuous spaces.
Takeaways & Limitations
The distorted-behavior-space experiment uses parameters selected to allow parallelized evaluation in a distributed setting.
Abstract
from arXiv · showhide
We focus on the challenge of finding a diverse collection of quality solutions on complex continuous domains. While quality diver-sity (QD) algorithms like Novelty Search with Local Competition (NSLC) and MAP-Elites are designed to generate a diverse range of solutions, these algorithms require a large number of evaluations for exploration of continuous spaces. Meanwhile, variants of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) are among the best-performing derivative-free optimizers in single-objective continuous domains. This paper proposes a new QD algorithm called Covariance Matrix Adaptation MAP-Elites (CMA-ME). Our new algorithm combines the self-adaptation techniques of CMA-ES with archiving and mapping techniques for maintaining diversity in QD. Results from experiments based on standard continuous optimization benchmarks show that CMA-ME finds better-quality solutions than MAP-Elites; similarly, results on the strategic game Hearthstone show that CMA-ME finds both a higher overall quality and broader diversity of strategies than both CMA-ES and MAP-Elites. Overall, CMA-ME more than doubles the performance of MAP-Elites using standard QD performance metrics. These results suggest that QD algorithms augmented by operators from state-of-the-art optimization algorithms can yield high-performing methods for simultaneously exploring and optimizing continuous search spaces, with significant applications to design, testing, and reinforcement learning among other domains.
1 INTRODUCTION
The paper targets quality-diversity search for diverse, high-quality solutions in complex continuous domains, where QD methods explore broadly but CMA-ES excels at continuous optimization. CMA-ME combines CMA-ES adaptation with MAP-Elites archiving to improve exploration and optimization.
- Motivation: Continuous strategy search must navigate neural-network parameters while exploring diverse behaviors.In game strategies, behavior can vary by properties such as game duration.
- Motivation: Quality-diversity algorithms seek multiple good solutions with meaningfully different behaviors rather than one optimum.MAP-Elites and NSLC use archiving and behavioral mapping to support divergent search.
- Motivation: CMA-ES variants are among the best-performing derivative-free optimizers for finding a single global optimum in continuous spaces.Their self-adaptation and cumulation techniques had not yet successfully powered a QD algorithm.
- Contribution: CMA-ME seeds CMA-ES search with MAP-Elites archive solutions and maintains emitters that focus on different behavior-space regions.The emitters form a dynamically adapted mixture of normal distributions.
- Evaluation: Two experiments evaluate CMA-ME on a continuous toy domain and the Hearthstone strategy-game domain.The experiments assess exploration of continuous spaces and diversity of agent policies.
2 BACKGROUND
The background distinguishes quality-diversity search from conventional optimization by emphasizing behavioral diversity and archive coverage. It motivates improving MAP-Elites’ solution-generation process with CMA-ES mechanisms rather than changing behavior-space tessellation.
- Quality diversity: QD algorithms maintain collections of good solutions that differ in behavior, supporting applications such as robot repertoires and diverse game levels.Their goal is not merely diversity in parameter encodings.
- MAP-Elites: MAP-Elites tessellates behavior characteristics into uniformly spaced grid cells and seeks both broad occupancy and high-quality elites.Each cell represents a behavioral niche.
- MAP-Elites: MAP-Elites initializes an archive, perturbs randomly selected elites with Gaussian noise, and replaces a cell’s elite when the new solution has higher fitness.Empty cells can also be filled by new solutions.
- CMA-ES: CMA-ES samples continuous solutions from a multivariate normal distribution and updates its mean and covariance using highly fit solutions and an evolution path.It is a competitive derivative-free optimizer for single-objective continuous optimization.
- Motivation for CMA-ME: CMA-ME extends MAP-Elites through solution generation, addressing prior approaches that used static noise or globally adapted mutation power.Related work had not adapted covariances between search variables in the same way.
3 APPROACH: THE CMA-ME ALGORITHM
CMA-ME organizes modified CMA-ES instances as emitters that sample, evaluate, and adapt distributions while sharing a behavioral archive. Different emitter rules trade off optimization, directional exploration, and archive improvement.
- Emitter architecture: CMA-ME schedules a population of emitters that generate solutions round-robin from distributions N(m,C).Each emitter maintains its own sampling mean, covariance matrix, and adaptation parameters.
- Emitter architecture: Emitters differ from CMA-ES by adapting covariance-update rankings to increase the likelihood of archive improvements in selected directions.Their shared archive provides feedback for distribution adaptation.
- Emitter types: Optimizing emitters resemble CMA-ES but restart from elite locations rather than from only the best solution found.This tests whether restarts alone can promote exploration.
- Emitter types: Random-direction emitters choose a behavior-space direction, bias search toward it, and restart from a random elite with a new direction when progress fails.They use behavior-space mappings to construct search biases.
- Emitter types: Improvement emitters rank solutions by fitness improvement within niches, prioritizing new-cell discoveries before replacements.After λ solutions, the sampling distribution adapts toward regions producing the greatest improvement.
- Archive interaction: The shared archive updates when evaluated solutions fill empty cells or outperform existing elites, then supplies parents for emitter adaptation.The procedure tracks behaviors, fitness, parents, and distribution updates across generations.
4 TOY DOMAIN
The toy domain examines how linear projection distorts high-dimensional behavior spaces and tests whether CMA-ME’s adaptive search improves quality-diversity coverage under this challenge.
- 4.1 Distorted Behavior Spaces: Linear projection can highly distort behavior spaces, making extreme behaviors difficult to reach as search-space dimensionality increases.Equal dependence of each behavior characteristic on every parameter forces algorithms to navigate all parameters to reach behavior-space extremes.
- 4.2 Experiments: CMA-ME is hypothesized to improve behavior-space coverage because it adapts each parameter with a separate variance instead of using MAP-Elites’ fixed global mutation rate.The experiment also selects parameters suitable for parallel evaluation in a distributed setting.
- 4.2 Experiments: The toy domain compares MAP-Elites, ME (line), CMA-ES, and three CMA-ME emitter variants on sphere and Rastrigin objectives.Each algorithm runs for 2.5M evaluations, with a 500 × 500 map; CMA-ME uses 15 emitters with λ = 37 2, while CMA-ES uses λ = 500.
- 4.2 Experiments: Behavior characteristics are produced by an equally weighted linear projection from IRn to IR2, with clipping restricting each component’s contribution to [−5.12, 5.12].The projection computes sums over the first and second halves of the search-space components.
- 4.3 Results: CMA-ES achieves the best optimal fitness, whereas CMA-ME (rd) and CMA-ME (imp) obtain the highest QD-Scores and fill the most unique behavior-space cells.CMA-ME (opt) performs worse in maximum fitness than CMA-ES; CMA-ME (rd) retains more lower-quality solutions, while CMA-ME (imp) fills fewer cells with higher quality.
5 HEARTHSTONE DOMAIN
The Hearthstone experiment searches for diverse, high-quality strategies against fixed opponents using behavior characteristics that distinguish aggressive from controlling play. CMA-ME outperforms MAP-Elites and CMA-ES across quality, win rate, coverage, and QD-Score.
- The study searches for diverse strategies against fixed opponents rather than only maximizing performance.
- Hearthstone presents large branching, partial observability, stochastic actions, and planning under uncertainty.
- The search uses a 109-parameter feed-forward neural network to score observable game states.
- Behavior is characterized by average hand size per turn and average game duration, spanning aggressive and controlling strategies.
- CMA-ME outperforms MAP-Elites and CMA-ES in maximum fitness, maximum win rate, filled cells, and QD-Score.
- CMA-ME more than doubles MAP-Elites’ QD-Score and maintains a higher win rate throughout evaluation.
6 DISCUSSION
The discussion attributes CMA-ME’s advantage to better exploration of distorted behavior spaces while preserving quality optimization. It also contrasts the sustained diversity of QD methods with CMA-ES convergence.
- CMA-ME explores more of Hearthstone’s distorted behavior space, especially toward the tails of game-duration behavior.
- When maximal coverage is desired, the authors recommend CMA-ME for efficiently exploring distorted behavior spaces.
- CMA-ME and MAP-Elites optimize win rate better than CMA-ES in Hearthstone.
- CMA-ES initially explores well but later converges toward a single strategy, potentially favoring early aggressive solutions over complex control strategies.
- Improvement emitters provide higher solution quality, whereas random-direction emitters cover more behavior space and optimizing emitters explore less.
7 CONCLUSIONS
The paper concludes that CMA-ME combines CMA-ES optimization with MAP-Elites diversity to improve both coverage and solution quality. It frames behavioral characteristics as a way to obtain diverse behavior and better objective performance.
- CMA-ME combines the strengths of CMA-ES and MAP-Elites for quality-diversity search.
- Across the toy and Hearthstone domains, CMA-ES components improve MAP-Elites’ coverage and solution quality.
- Adding behavioral characteristics to an objective can yield useful behavioral diversity alongside better performance on the original objective.