Elamur Research⌕
☰
home / papers / 2019 / Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions

Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions

Paper · 2019 · Rui Wang, Joel Lehman, Jeff Clune et al.

Summary

Progress in machine learning usually follows a fixed pattern: people choose a problem, and researchers build algorithms to solve it. Wang et al. (Uber AI Labs) ask whether one algorithm can invent its own problems while solving them, producing an open-ended curriculum it builds for itself. Their method, POET, maintains a population of environment–agent pairs. It creates new environments by mutating existing ones and improves each paired agent with evolution strategies (ES). It also periodically tries agents in other environments, adopting a transferred agent whenever it beats the local one. The testbed is a 2-D bipedal walking obstacle course in which a neural network controls the walker. The terrain can evolve from flat ground into mixtures of gaps, stumps and rough surfaces. In a single run, POET generates and solves many diverse, difficult courses. Agents optimized from scratch on those same courses fail to reach comparable results, and so do agents trained with a hand-built direct-path curriculum. Transfer between environments proves crucial. The work is a concrete step toward open-ended learning and automatic task generation.

Key points

  • POET combines three steps: generating environments, optimizing agents with ES, and transferring solutions across environments ("goal switching").
  • In the bipedal walker domain, obstacle types (gap width, stump height, roughness) and their difficulty evolve, yielding varied environment profiles within one run.
  • POET solved challenging courses that neither direct optimization nor a direct-path curriculum control could solve.
  • Ablation shows that cross-environment transfer is essential for POET's full performance.
  • The method draws on MCC, novelty search, MAP-Elites, Innovation Engines and CMOEA. Proposed extensions include:
    • CPPN/HyperNEAT encodings for terrain, body and controller
    • swapping ES for TRPO, PPO or genetic algorithms
    • generating task distributions for meta-learning

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢Uber AISan Francisco · United States3 works · 875 citations

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 works

Cite

Cite as Rui Wang, Joel Lehman, Jeff Clune and Kenneth O. Stanley. 2019. Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions. arXiv:1901.01753.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1901.01753 · arXiv 1901.01753

@misc{wang2019paired,
  title = {{Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions}},
  author = {Rui Wang, Joel Lehman, Jeff Clune and Kenneth O. Stanley},
  year = {2019},
  doi = {10.48550/arxiv.1901.01753},
  eprint = {1901.01753},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1901.01753}
}

References

82 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255, 2009. find
  2. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. arXiv preprint arXiv:1512.03385, 2015.
  3. O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, and M. Bernstein et al. Imagenet large scale visual recognition challenge. arXiv preprint arXiv:1409.0575, 2014.
  4. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. arXiv preprint arXiv:1502.01852, 2015. find
  5. Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction, volume 1. 1998. find
  6. Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. J. Artif. Intell. Res.(JAIR), 47:253–279, 2013.
  7. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, 2015. find
  8. Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Iain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. arXiv preprint arXiv:1802.01561, 2018. find
  9. Dan Horgan, John Quan, David Budden, Gabriel Barth-Maron, Matteo Hessel, Hado Van Hasselt, and David Silver. Distributed prioritized experience replay. arXiv preprint arXiv:1803.00933, 2018. — [arXiv:1803.00933](https://arxiv.org/abs/1803.00933) find
  10. Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojciech Czarnecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with popart. arXiv preprint arXiv:1809.04474, 2018. find
  11. Steven Kapturowski, Georg Ostrovski, Will Dabney, John Quan, and Remi Munos. Recurrent experience replay in distributed reinforcement learning. In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=r1lyTjAqYX. ↗
  12. Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. Montezuma’s revenge solved by go-explore, a new algorithm for hard-exploration problems (sets records on pitfall, too). https://eng.uber.com/go-explore/, 2018. ↗
  13. David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016. find
  14. David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354, 2017. find
  15. David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140–1144, 2018. find
  16. Sébastien Forestier, Yoan Mollard, and Pierre-Yves Oudeyer. Intrinsically motivated goal exploration processes with automatic curriculum learning. arXiv preprint arXiv:1708.02190, 2017. find
  17. Jürgen Schmidhuber. Powerplay: Training an increasingly general problem solver by continually searching for the simplest still unsolvable problem. Frontiers in psychology, 4:313, 2013. find
  18. Russell K Standish. Open-ended artificial evolution. International Journal of Computational Intelligence and Applications, 3(02):167–175, 2003. find
  19. W. B. Langdon. Pfeiffer – A distributed open-ended evolutionary system. In Bruce Edmonds, Nigel Gilbert, Steven Gustafson, David Hales, and Natalio Krasnogor, editors, AISB’05: Proceedings of the Joint Symposium on Socially Inspired Computing (METAS 2005), pages 7–13, 2005. URL http://www.cs. ucl.ac… ↗
  20. Mark Bedau. The arrow of complexity hypothesis (abstract). In Seth Bullock, Jason Noble, Richard Watson, and Mark Bedau, editors, Proceedings of the Eleventh International Conference on Artificial Life (Alife XI), page 750, Cambridge, MA, 2008. MIT Press. URL http://www.alifexi.org/papers/ALIFExi-ab… ↗
  21. Kenneth O. Stanley, Joel Lehman, and Lisa Soros. Open-endedness: The last grand challenge you’ve never heard of. O’Reilly Online, 2017. URL https://www.oreilly.com/ideas/open-endedness-the-last-grand-challenge-youve-never-heard-of. ↗
  22. Tim Taylor, Mark Bedau, Alastair Channon, and David Ackley et al. Open-ended evolution: Perspectives from the oee workshop in york. Artificial life, 22(3):408–423, 2016. find
  23. Joel Lehman and Kenneth O. Stanley. Exploiting open-endedness to solve problems through the search for novelty. In Seth Bullock, Jason Noble, Richard Watson, and Mark Bedau, editors, Proceedings of the Eleventh International Conference on Artificial Life (Alife XI), Cambridge, MA, 2008. MIT Press. U… find
  24. Lars Graening, Nikola Aulig, and Markus Olhofer. Towards directed open-ended search by a novelty guided evolution strategy. In Robert Schaefer, Carlos Cotta, Joanna Kołodziej, and Günter Rudolph, editors, Parallel Problem Solving from Nature – PPSN XI, volume 6239 of Lecture Notes in Computer Scienc… find
  25. L.B. Soros and Kenneth O Stanley. Identifying necessary conditions for open-ended evolution through the artificial life world of chromaria. In ALIFE 14: The Fourteenth International Conference on the Synthesis and Simulation of Living Systems, pages 793–800, 2014. find
  26. L.B. Soros, Nick Cheney, and Kenneth O Stanley. How the strictness of the minimal criterion impacts open-ended evolution. In ALIFE 15: The Fifteenth International Conference on the Synthesis and Simulation of Living Systems, pages 208–215, 2016. find
  27. Jonathan C. Brant and Kenneth O. Stanley. Minimal criterion coevolution: A new approach to open-ended search. In Proceedings of the 2017 on Genetic and Evolutionary Computation Conference (GECCO), pages 67–74, 2017. find
  28. Thomas S Ray. An approach to the synthesis of life. In Artificial Life II, pages 371–408. Addison-Wesley, 1991. find
  29. S.G. Ficici and J.B. Pollack. Challenges in coevolutionary learning: Arms-race dynamics, open-endedness, and mediocre stable states. Artificial life VI, page 238, 1998. find
  30. R. Paul Wiegand, William C. Liles, and Kenneth A. De Jong. An empirical analysis of collaboration methods in cooperative coevolutionary algorithms. In Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, GECCO’01, pages 1235–1242, San Francisco, CA, USA, 2001. Morgan Kau… find
  31. Elena Popovici, Anthony Bucci, R. Paul Wiegand, and Edwin D. De Jong. Coevolutionary Principles, pages 987–1033. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. ISBN 978-3-540-92910-9. doi: 10.1007/978-3-540-92910-9_31. URL http://dx.doi.org/10.1007/978-3-540-92910-9_31. — [doi:10.1007/978-3-540-92910-9_31](https://doi.org/10.1007/978-3-540-92910-9_31) ↗
  32. Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. Emergent complexity via multi-agent competition. arXiv preprint arXiv:1710.03748, 2018. — [arXiv:1710.03748](https://arxiv.org/abs/1710.03748) find
  33. Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672–2680, 2014.
  34. Nick Moran and Jordan B. Pollack. Coevolutionary neural population models. CoRR, abs/1804.04187, 2018. URL http://arxiv.org/abs/1804.04187. — [arXiv:1804.04187](https://arxiv.org/abs/1804.04187) ↗
  35. Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In International Conference on Machine Learning, pages 1514–1523, 2018.
  36. Carlos Florensa, David Held, Markus Wulfmeier, Michael Zhang, and Pieter Abbeel. Reverse curriculum generation for reinforcement learning. In Proceedings of the 1st Annual Conference on Robot Learning, pages 482–495, 2017. find
  37. Tambet Matiisen, Avital Oliver, Taco Cohen, and John Schulman. Teacher-student curriculum learning. arXiv preprint arXiv:1707.00183, 2017. find
  38. Julian Togelius, Georgios N Yannakakis, Kenneth O Stanley, and Cameron Browne. Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games, 3(3):172–186, 2011. find
  39. Noor Shaker, Julian Togelius, and Mark J Nelson. Procedural content generation in games. Springer, 2016. find
  40. Niels Justesen, Ruben Rodriguez Torrado, Philip Bontrager, Ahmed Khalifa, Julian Togelius, and Sebastian Risi. Illuminating generalization in deep reinforcement learning through procedural level generation. arXiv preprint arXiv:1806.10729, 2018. — [arXiv:1806.10729](https://arxiv.org/abs/1806.10729) find
  41. Joel Lehman and Kenneth O. Stanley. Evolving a diversity of virtual creatures through novelty search and local competition. In GECCO ’11: Proceedings of the 13th annual conference on Genetic and evolutionary computation, pages 211–218, 2011. find
  42. Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909, 2015. — [arXiv:1504.04909](https://arxiv.org/abs/1504.04909) find
  43. A. Cully, J. Clune, D. Tarapore, and J.-B. Mouret. Robots that can adapt like animals. Nature, 521:503–507, 2015. doi: 10.1038/nature14422. — [doi:10.1038/nature14422](https://doi.org/10.1038/nature14422) find
  44. Anh Nguyen, Jason Yosinski, and Jeff Clune. Understanding innovation engines: Automated creativity and improved stochastic optimization via deep learning. Evolutionary Computation, 24(3):545–572, 2016. find
  45. Joost Huizinga, Jean-Baptiste Mouret, and Jeff Clune. Does aligning phenotypic and genotypic modularity improve the evolution of neural networks? In Proceedings of the 2016 on Genetic and Evolutionary Computation Conference (GECCO), pages 125–132, 2016. find
  46. Joost Huizinga and Jeff Clune. Evolving multimodal robot behavior via many stepping stones with the combinatorial multi-objective evolutionary algorithm. arXiv preprint arXiv:1807.03392, 2018. — [arXiv:1807.03392](https://arxiv.org/abs/1807.03392) find
  47. Tim Salimans, Jonathan Ho, Xi Chen, and Ilya Sutskever. Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.03864, 2017. find
  48. Joel Lehman and Kenneth O. Stanley. Novelty search and the problem with objectives. In Genetic Programming Theory and Practice IX (GPTP 2011), 2011. find
  49. Justin K Pugh, Lisa B. Soros, and Kenneth O. Stanley. Quality diversity: A new frontier for evolutionary computation. 3(40), 2016. ISSN 2296-9144. find
  50. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097–1105, 2012.
  51. Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. arXiv preprint arXiv:1802.06070, 2018.
  52. Nikolay Savinov, Anton Raichuk, Raphael Marinier, Damien Vincent, Marc Pollefeys, Timothy Lillicrap, and Sylvain Gelly. Episodic curiosity through reachability. arXiv preprint arXiv:1810.0227, 2018. — [arXiv:1810.0227](https://arxiv.org/abs/1810.0227) find
  53. Joel Lehman and Kenneth O. Stanley. Revising the evolutionary computation abstraction: minimal criteria novelty search. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, GECCO ’10, pages 103–110, New York, NY, USA, 2010. ACM. ISBN 978-1-4503-0072-8. doi: http://d… — [doi:10.1145/1830483.1830503](https://doi.org/10.1145/1830483.1830503) find
  54. Ingo Rechenberg. Evolutionsstrategien. In Simulationsmethoden in der Medizin und Biologie, pages 83–114. 1978. find
  55. Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229–256, 1992. find
  56. Daan Wierstra, Tom Schaul, Jan Peters, and Juergen Schmidhuber. Natural evolution strategies. In Evolutionary Computation, 2008., pages 3381–3387, 2008. find
  57. Frank Sehnke, Christian Osendorfer, Thomas Rückstieß, Alex Graves, Jan Peters, and Jürgen Schmidhuber. Parameter-exploring policy gradients. Neural Networks, 23(4):551–559, 2010. find
  58. Joel Lehman, Jay Chen, Jeff Clune, and Kenneth O. Stanley. Es is more than just a traditional finite-difference approximator. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’18, pages 450–457, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5618-3. doi: 10.1145/3205455.32… — [doi:10.1145/3205455.3205474](https://doi.org/10.1145/3205455.3205474) find
  59. Xingwen Zhang, Jeff Clune, and Kenneth O. Stanley. On the relationship between the openai evolution strategy and stochastic gradient descent. arXiv preprint arXiv:1712.06564, 2017. — [arXiv:1712.06564](https://arxiv.org/abs/1712.06564) find
  60. Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In ICML, pages 1928–1937, 2016. find
  61. Edoardo Conti, Vashisht Madhavan, Felipe Petroski Such, Joel Lehman, Kenneth Stanley, and Jeff Clune. Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents. In Advances in Neural Information Processing Systems (NeurIPS) 31, pages 503… find
  62. Kenneth O Stanley and Joel Lehman. Why greatness cannot be planned. 2015. find
  63. Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016. find
  64. David Ha. Reinforcement learning for improving agent design. arXiv preprint arXiv:1810.03779, 2018. — [arXiv:1810.03779](https://arxiv.org/abs/1810.03779) find
  65. Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
  66. David Ha. Evolving stable strategies. http://blog.otoro.net/, 2017. ↗
  67. Faustino Gomez and Risto Miikkulainen. Incremental evolution of complex general behavior. Adaptive Behavior, 5:317–342, 1997. URL gomez:ab97. find
  68. Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pages 41–48. ACM, 2009.
  69. Andrej Karpathy and Michiel Van De Panne. Curriculum learning for motor skills. In Canadian Conference on Artificial Intelligence, pages 325–330. Springer, 2012. find
  70. Nicolas Heess, Srinivasan Sriram, Jay Lemmon, Josh Merel, Greg Wayne, Yuval Tassa, Tom Erez, Ziyu Wang, Ali Eslami, Martin Riedmiller, et al. Emergence of locomotion behaviours in rich environments. arXiv preprint arXiv:1707.02286, 2017. — [arXiv:1707.02286](https://arxiv.org/abs/1707.02286) find
  71. O. Klimov. Bipedalwalkerhardcore-v2. https://gym.openai.com, 2016. ↗
  72. Kenneth O. Stanley. Compositional pattern producing networks: A novel abstraction of development. Genetic Programming and Evolvable Machines Special Issue on Developmental Systems, 8(2):131–162, 2007. find
  73. N. Cheney, R. MacCurdy, J. Clune, and H. Lipson. Unshackling evolution: evolving soft robots with multiple materials and a powerful generative encoding. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2013), New York, NY, 2013. ACM Press. find
  74. Kenneth O. Stanley, David B. D’Ambrosio, and Jason Gauci. A hypercube-based indirect encoding for evolving large-scale neural networks. Artificial Life, 15(2):185–212, 2009. URL http://eplex.cs.ucf.edu/publications/2009/stanley.alife09.html. ↗
  75. Jeff Clune, Kenneth O. Stanley, Robert T. Pennock, and Charles Ofria. On the performance of indirect encoding across the continuum of regularity. IEEE Transactions on Evolutionary Computation, 2011. find
  76. Jeff Clune, Benjamin E. Beckmann, Charles Ofria, and Robert T. Pennock. Evolving coordinated quadruped gaits with the HyperNEAT generative encoding. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC-2009) Special Session on Evolutionary Robotics, Piscataway, NJ, USA, 2009. IEEE Pr… find
  77. Jason Yosinski, Jeff Clune, Diana Hidalgo, Sarah Nguyen, Juan Cristobal Zagal, and Hod Lipson. Evolving robot gaits in hardware: the hyperneat generative encoding vs. parameter optimization. In Proceedings of the 20th European Conference on Artificial Life, August 2011. find
  78. John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pages 1889–1897, 2015. find
  79. J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. find
  80. Abhishek Gupta, Benjamin Eysenbach, Chelsea Finn, and Sergey Levine. Unsupervised meta-learning for reinforcement learning. arXiv, 2018. URL http://arxiv.org/abs/1806.04640. — [arXiv:1806.04640](https://arxiv.org/abs/1806.04640) ↗
  81. Nicolas Heess, Dhruva TB, Srinivasan Sriram, Jay Lemmon, Josh Merel, Greg Wayne, Yuval Tassa, Tom Erez, Ziyu Wang, S. M. Ali Eslami, Martin A. Riedmiller, and David Silver. Emergence of locomotion behaviours in rich environments. CoRR, abs/1707.02286, 2017. URL http://arxiv.org/abs/1707.02286. — [arXiv:1707.02286](https://arxiv.org/abs/1707.02286) ↗
  82. Joel Lehman and Kenneth O. Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolutionary Computation, 19(2):189–223, 2011. URL http://www.mitpressjournals.org/doi/pdf/10.1162/EVCO_a_00025. Supplemental Information The first section in this supplement details the proced… — [doi:10.1162/evco_a_00025](https://doi.org/10.1162/evco_a_00025) ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wang-2019-paired-open-ended-trailblazer-poet/