{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T16:47:31Z","timestamp":1790786851750,"version":"4.1.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,3,29]],"date-time":"2023-03-29T00:00:00Z","timestamp":1680048000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/V006673\/1"],"award-info":[{"award-number":["EP\/V006673\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>Quality-Diversity algorithms, among which are the Multi-dimensional Archive of Phenotypic Elites (MAP-Elites), have emerged as powerful alternatives to performance-only optimisation approaches as they enable generating collections of diverse and high-performing solutions to an optimisation problem. However, they are often limited to low-dimensional search spaces and deterministic environments. The recently introduced Policy Gradient Assisted MAP-Elites (PGA-MAP-Elites) algorithm overcomes this limitation by pairing the traditional Genetic operator of MAP-Elites with a gradient-based operator inspired by deep reinforcement learning. This new operator guides mutations toward high-performing solutions using policy gradients (PG). In this work, we propose an in-depth study of PGA-MAP-Elites. We demonstrate the benefits of PG on the performance of the algorithm and the reproducibility of the generated solutions when considering uncertain domains. We firstly prove that PGA-MAP-Elites is highly performant in both deterministic and uncertain high-dimensional environments, decorrelating the two challenges it tackles. Secondly, we show that in addition to outperforming all the considered baselines, the collections of solutions generated by PGA-MAP-Elites are highly reproducible in uncertain environments, approaching the reproducibility of solutions found by Quality-Diversity approaches built specifically for uncertain applications. Finally, we propose an ablation and in-depth analysis of the dynamic of the PG-based variation. We demonstrate that the PG variation operator is determinant to guarantee the performance of PGA-MAP-Elites but is only essential during the early stage of the process, where it finds high-performing regions of the search space.<\/jats:p>","DOI":"10.1145\/3577203","type":"journal-article","created":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T13:13:22Z","timestamp":1673270002000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Empirical analysis of PGA-MAP-Elites for Neuroevolution in Uncertain Domains"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4601-2176","authenticated-orcid":false,"given":"Manon","family":"Flageat","sequence":"first","affiliation":[{"name":"Imperial College London, London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9476-2900","authenticated-orcid":false,"given":"F\u00e9lix","family":"Chalumeau","sequence":"additional","affiliation":[{"name":"Imperial College London, London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3190-7073","authenticated-orcid":false,"given":"Antoine","family":"Cully","sequence":"additional","affiliation":[{"name":"Imperial College London, London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,3,29]]},"reference":[{"issue":"6","key":"e_1_3_2_2_1","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/MSP.2017.2743240","article-title":"Deep reinforcement learning: A brief survey","volume":"34","author":"Arulkumaran Kai","year":"2017","unstructured":"Kai Arulkumaran, Marc Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. 2017. Deep reinforcement learning: A brief survey. IEEE Signal Processing Magazine 34, 6 (2017), 26\u201338.","journal-title":"IEEE Signal Processing Magazine"},{"key":"e_1_3_2_3_1","article-title":"OpenAI gym","volume":"1606","author":"Brockman Greg","year":"2016","unstructured":"Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. 2016. OpenAI gym. CoRR abs\/1606.01540 (2016). http:\/\/arxiv.org\/abs\/1606.01540.","journal-title":"CoRR"},{"key":"e_1_3_2_4_1","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/978-3-030-66515-9_4","volume-title":"Black Box Optimization, Machine Learning, and No-Free Lunch Theorems","author":"Chatzilygeroudis Konstantinos","year":"2021","unstructured":"Konstantinos Chatzilygeroudis, Antoine Cully, Vassilis Vassiliades, and Jean-Baptiste Mouret. 2021. Quality-diversity optimization: A novel branch of stochastic optimization. In Black Box Optimization, Machine Learning, and No-Free Lunch Theorems. Springer, 109\u2013135."},{"key":"e_1_3_2_5_1","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/3377930.3390217","volume-title":"Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO\u201920)","author":"Colas C\u00e9dric","year":"2020","unstructured":"C\u00e9dric Colas, Vashisht Madhavan, Joost Huizinga, and Jeff Clune. 2020. Scaling MAP-Elites to deep neuroevolution. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO\u201920). ACM, New York, NY, 67\u201375. DOI:10.1145\/3377930.3390217; Implementation: https:\/\/github.com\/uber-research\/Map-Elites-Evolutionary."},{"key":"e_1_3_2_6_1","article-title":"PyBullet, a Python Module for Physics Simulation for Games, Robotics and Machine Learning","author":"Coumans Erwin","year":"2019","unstructured":"Erwin Coumans and Yunfei Bai. 2019. PyBullet, a Python Module for Physics Simulation for Games, Robotics and Machine Learning. Retrieved January 18, 2023 from http:\/\/pybullet.org; Implementation: https:\/\/github.com\/bulletphysics\/bullet3\/blob\/master\/examples\/pybullet\/gym\/pybullet_envs\/gym_locomotion_envs.py.","journal-title":"http:\/\/pybullet.org"},{"key":"e_1_3_2_7_1","doi-asserted-by":"crossref","unstructured":"Antoine Cully. 2020. Multi-emitter MAP-Elites: Improving quality diversity and convergence speed with heterogeneous sets of emitters. arxiv:2007.05352 [cs.NE] (2020).","DOI":"10.1145\/3449639.3459326"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature14422"},{"key":"e_1_3_2_9_1","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1145\/3205455.3205571","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201918)","author":"Cully Antoine","year":"2018","unstructured":"Antoine Cully and Yiannis Demiris. 2018a. Hierarchical behavioral repertoires with unsupervised descriptors. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201918). ACM, New York, NY, 69\u201376. DOI:10.1145\/3205455.3205571"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2704781"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1162\/isal_a_00316"},{"key":"e_1_3_2_12_1","article-title":"Differentiable quality diversity","author":"Fontaine Matthew C.","year":"2021","unstructured":"Matthew C. Fontaine and Stefanos Nikolaidis. 2021. Differentiable quality diversity. arXiv e-prints (2021).","journal-title":"arXiv e-prints"},{"key":"e_1_3_2_13_1","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1145\/3377930.3390232","volume-title":"Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO\u201920)","author":"Fontaine Matthew C.","year":"2020","unstructured":"Matthew C. Fontaine, Julian Togelius, Stefanos Nikolaidis, and Amy K. Hoover. 2020a. Covariance matrix adaptation for the rapid illumination of behavior space. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO\u201920). ACM, New York, NY, 94\u2013102. DOI:10.1145\/3377930.3390232"},{"key":"e_1_3_2_14_1","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1145\/3377930.3390232","volume-title":"Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO\u201920)","author":"Fontaine Matthew C.","year":"2020","unstructured":"Matthew C. Fontaine, Julian Togelius, Stefanos Nikolaidis, and Amy K. Hoover. 2020b. Covariance matrix adaptation for the rapid illumination of behavior space. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO\u201920). 94\u2013102."},{"key":"e_1_3_2_15_1","series-title":"Proceedings of the 35th International Conference on Machine Learning","first-page":"1587","volume":"80","author":"Fujimoto Scott","year":"2018","unstructured":"Scott Fujimoto, Herke van Hoof, and David Meger. 2018. Addressing function approximation error in actor-critic methods. In Proceedings of the 35th International Conference on Machine Learning(Proceedings of Machine Learning Research, Vol. 80), Jennifer Dy and Andreas Krause (Eds.). PMLR, Stockholmsm\u00e4ssan, Stockholm, Sweden, 1587\u20131596. http:\/\/proceedings.mlr.press\/v80\/fujimoto18a.html;Implementation: https:\/\/github.com\/sfujim\/TD3."},{"key":"e_1_3_2_16_1","first-page":"3330","volume-title":"Proceedings of the 18th AIAA\/ISSMO Multidisciplinary Analysis and Optimization Conference","author":"Gaier Adam","year":"2017","unstructured":"Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret. 2017. Aerodynamic design exploration through surrogate-assisted illumination. In Proceedings of the 18th AIAA\/ISSMO Multidisciplinary Analysis and Optimization Conference. 3330."},{"key":"e_1_3_2_17_1","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/3377930.3390221","volume-title":"Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO\u201920)","author":"Gaier Adam","year":"2020","unstructured":"Adam Gaier, Alexander Asteroth, and Jean-Baptiste Mouret. 2020. Discovering representations for black-box optimization. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference (GECCO\u201920). 103\u2013111."},{"key":"e_1_3_2_18_1","first-page":"1","volume-title":"Proceedings of the 2019 IEEE Conference on Games (CoG\u201919)","author":"Gravina Daniele","year":"2019","unstructured":"Daniele Gravina, Ahmed Khalifa, Antonios Liapis, Julian Togelius, and Georgios N. Yannakakis. 2019. Procedural content generation through quality diversity. In Proceedings of the 2019 IEEE Conference on Games (CoG\u201919). 1\u20138. DOI:10.1109\/CIG.2019.8848053"},{"key":"e_1_3_2_19_1","article-title":"The CMA evolution strategy: A tutorial","author":"Hansen Nikolaus","year":"2016","unstructured":"Nikolaus Hansen. 2016. The CMA evolution strategy: A tutorial. arXiv preprint arXiv:1604.00772 (2016).","journal-title":"arXiv preprint arXiv:1604.00772"},{"issue":"3","key":"e_1_3_2_20_1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1109\/TEVC.2005.846356","article-title":"Evolutionary optimization in uncertain environments\u2014A survey","volume":"9","author":"Jin Yaochu","year":"2005","unstructured":"Yaochu Jin and J\u00fcrgen Branke. 2005. Evolutionary optimization in uncertain environments\u2014A survey. IEEE Transactions on Evolutionary Computation 9, 3 (2005), 303\u2013317.","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"e_1_3_2_21_1","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/3319619.3321904","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference Companion","author":"Justesen Niels","year":"2019","unstructured":"Niels Justesen, Sebastian Risi, and Jean-Baptiste Mouret. 2019. Map-Elites for noisy domains by adaptive sampling. In Proceedings of the Genetic and Evolutionary Computation Conference Companion(GECCO\u201919). 121\u2013122."},{"key":"e_1_3_2_22_1","first-page":"211","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201911)","author":"Lehman Joel","year":"2011","unstructured":"Joel Lehman and Kenneth O. Stanley. 2011. Evolving a diversity of creatures through novelty search and local competition. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201911). 211\u2013218. DOI:10.1145\/2001576.2001606"},{"key":"e_1_3_2_23_1","volume-title":"Proceedings of the 4th International Conference on Learning Representations (ICLR\u201916): Conference Track Proceedings","author":"Lillicrap Timothy P.","year":"2016","unstructured":"Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. 2016. Continuous control with deep reinforcement learning. In Proceedings of the 4th International Conference on Learning Representations (ICLR\u201916): Conference Track Proceedings."},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992699"},{"key":"e_1_3_2_25_1","unstructured":"Volodymyr Mnih Koray Kavukcuoglu David Silver Alex Graves Ioannis Antonoglou Daan Wierstra and Martin Riedmiller. 2013. Playing Atari with deep reinforcement learning. arxiv:1312.5602 (2013). http:\/\/arxiv.org\/abs\/1312.5602."},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature14236"},{"key":"e_1_3_2_27_1","unstructured":"Jean-Baptiste Mouret and Jeff Clune. 2015. Illuminating search spaces by mapping elites. arXiv:1504.04909 (2015). http:\/\/arxiv.org\/abs\/1504.04909."},{"key":"e_1_3_2_28_1","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1145\/3449639.3459304","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201921)","author":"Nilsson Olle","year":"2021","unstructured":"Olle Nilsson and Antoine Cully. 2021. Policy gradient assisted Map-Elites. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201921). 866\u2013875."},{"key":"e_1_3_2_29_1","doi-asserted-by":"crossref","unstructured":"Thomas Pierrot Valentin Mac\u00e9 F\u00e9lix Chalumeau Arthur Flajolet Geoffrey Cideron Karim Beguir Antoine Cully Olivier Sigaud and Nicolas Perrin. 2022. Diversity policy gradient for sample efficient quality-diversity optimization. In Proceedings of the Workshop on Agent Learning in Open-Endedness (ALOE) at ICLR 2022 .","DOI":"10.1145\/3512290.3528845"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.3389\/frobt.2016.00040"},{"key":"e_1_3_2_31_1","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1145\/3449639.3459320","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201921)","author":"Rakicevic Nemanja","year":"2021","unstructured":"Nemanja Rakicevic, Antoine Cully, and Petar Kormushev. 2021. Policy manifold search: Exploring the manifold hypothesis for diversity-based neuroevolution. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201921). 901\u2013909."},{"key":"e_1_3_2_32_1","unstructured":"Tim Salimans Jonathan Ho Xi Chen Szymon Sidor and Ilya Sutskever. 2017. Evolution strategies as a scalable alternative to reinforcement learning. arxiv:1703.03864 (2017). http:\/\/arxiv.org\/abs\/1703.03864."},{"key":"e_1_3_2_33_1","volume-title":"Proceedings of the 31st International Conference on Machine Learning (ICML\u201914)","author":"Silver David","year":"2014","unstructured":"David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. 2014. Deterministic policy gradient algorithms. In Proceedings of the 31st International Conference on Machine Learning (ICML\u201914)."},{"key":"e_1_3_2_34_1","article-title":"Deep neuroevolution: Genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning","author":"Such Felipe Petroski","year":"2017","unstructured":"Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. 2017. Deep neuroevolution: Genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning. arXiv preprint arXiv:1712.06567 (2017).","journal-title":"arXiv preprint arXiv:1712.06567"},{"key":"e_1_3_2_35_1","article-title":"Approximating gradients for differentiable quality diversity in reinforcement learning","author":"Tjanaka Bryon","year":"2022","unstructured":"Bryon Tjanaka, Matthew C. Fontaine, Julian Togelius, and Stefanos Nikolaidis. 2022. Approximating gradients for differentiable quality diversity in reinforcement learning. arXiv preprint arXiv:2202.03666 (2022).","journal-title":"arXiv preprint arXiv:2202.03666"},{"key":"e_1_3_2_36_1","article-title":"pyribs: A Bare-Bones Python Library for Quality Diversity Optimization","author":"Tjanaka Bryon","year":"2021","unstructured":"Bryon Tjanaka, Matthew C. Fontaine, Yulun Zhang, Sam Sommerer, Nathan Dennler, and Stefanos Nikolaidis. 2021. pyribs: A Bare-Bones Python Library for Quality Diversity Optimization. Retrieved January 18, 2023 from https:\/\/github.com\/icaros-usc\/pyribs.","journal-title":"https:\/\/github.com\/icaros-usc\/pyribs."},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2735550;"},{"key":"e_1_3_2_38_1","doi-asserted-by":"crossref","DOI":"10.1145\/3205455.3205602","article-title":"Discovering the elite hypervolume by leveraging interspecies correlation","author":"Vassiliades Vassilis","year":"2018","unstructured":"Vassilis Vassiliades and Jean-Baptiste Mouret. 2018. Discovering the elite hypervolume by leveraging interspecies correlation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201918).","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201918)."}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3577203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3577203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:32Z","timestamp":1750178852000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3577203"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,29]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3577203"],"URL":"https:\/\/doi.org\/10.1145\/3577203","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"value":"2688-299X","type":"print"},{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,29]]},"assertion":[{"value":"2022-03-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}