Uncertainty handling CMA-ES for reinforcement learning

ABSTRACT

The covariance matrix adaptation evolution strategy (CMAES) has proven to be a powerful method for reinforcement learning (RL). Recently, the CMA-ES has been augmented with an adaptive uncertainty handling mechanism. Because uncertainty is a typical property of RL problems this new algorithm, termed UH-CMA-ES, is promising for RL. The UH-CMA-ES dynamically adjusts the number of episodes considered in each evaluation of a policy. It controls the signal to noise ratio such that it is just high enough for a sufficiently good ranking of candidate policies, which in turn allows the evolutionary learning to find better solutions. This significantly increases the learning speed as well as the robustness without impairing the quality of the final solutions. We evaluate the UH-CMA-ES on fully and partially observable Markov decision processes with random start states and noisy observations. A canonical natural policy gradient method and random search serve as a baseline for comparison.

REFERENCES

• 1: S. Amari and H. Nagaoka. Methods of Information Geometry. Number 191 in Translations of Mathematical Monographs. American Mathematical Society and Oxford University Press, 2000.
• 2: Dirk V. Arnold , Hans-Georg Beyer, Noisy Local Optimization with Evolution Strategies, Kluwer Academic Publishers, Norwell, MA, 2002
• 3: H.-G. Beyer. Evolution strategies. Scholarpedia, 2(8):1965, 2007.
• 4: C. Chen and E. Yucesan. An alternative simulation budget allocation scheme for efficient simulation. International Journal of Simulation and Process Modeling, 1(1):49--57, 2005.
• 5: R. Coulom. Apprentissage par renforcement utilisant des reseaux de neurones, avec des applications au controle moteur. These de doctorat, Institut National Polytechnique de Grenoble, 2002.
• 6: Tobias Glasmachers , Christian Igel, Uncertainty Handling in Model Selection for Support Vector Machines, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_19]
• 7: Faustino Gomez , Jürgen Schmidhuber , Risto Miikkulainen, Accelerated Neural Evolution through Cooperatively Coevolved Synapses, The Journal of Machine Learning Research, 9, p.937-965, 6/1/2008
• 8: Nikolaus Hansen , Sibylle D. Müller , Petros Koumoutsakos, Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES), Evolutionary Computation, v.11 n.1, p.1-18, Spring 2003 [doi>10.1162/106365603321828970]
• 9: N. Hansen, A. S. P. Niederberger, L. Guzzella, and P. Koumoutsakos. Evolutionary optimization of feedback controllers for thermoacoustic instabilities. In J. F. Morrison, D. M. Birch, and P. Lavoie, editors, IUTAM Symposium on Flow Control and MEMS. Springer-Verlag, 2008.
• 10: N. Hansen, A. S. P. Niederberger, L. Guzzella, and P. Koumoutsakos. A method for handling uncertainty in evolutionary optimization with an application to feedback control of combustion. IEEE Transactions on Evolutionary Computation, 13(1):180--197, 2009.
• 11: Nikolaus Hansen , Andreas Ostermeier, Completely Derandomized Self-Adaptation in Evolution Strategies, Evolutionary Computation, v.9 n.2, p.159-195, June 2001 [doi>10.1162/106365601750190398]
• 12: Verena Heidrich-Meisner , Christian Igel, Evolution Strategies for Direct Policy Search, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_43]
• 13: V. Heidrich-Meisner and C. Igel. Uncertainty handling in evolutionary direct policy search. In Y. Engel, M. Ghavamzadeh, P. Poupart, and S. Mannor, editors, NIPS-08 Workshop on Model Uncertainty and Risk in Reinforcement Learning. 2008.
• 14: Verena Heidrich-Meisner , Christian Igel, Variable Metric Reinforcement Learning Methods Applied to the Noisy Mountain Car Problem, Recent Advances in Reinforcement Learning: 8th European Workshop, EWRL 2008, Villeneuve d'Ascq, France, June 30-July 3, 2008, Revised and Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-89722-4_11]
• 15: C. Igel. Neuroevolution for reinforcement learning using evolution strategies. In Congress on Evolutionary Computation (CEC 2003), volume4, pages 2588--2595. IEEE Press, 2003.
• 16: Christian Igel , Verena Heidrich-Meisner , Tobias Glasmachers, Shark, The Journal of Machine Learning Research, 9, p.993-996, 6/1/2008
• 17: Leslie Pack Kaelbling , Michael L. Littman , Anthony R. Cassandra, Planning and acting in partially observable stochastic domains, Artificial Intelligence, v.101 n.1-2, p.99-134, May 1998 [doi>10.1016/S0004-3702(98)00023-X]
• 18: S. Kakade. A natural policy gradient. In T. G. Dietterich, S. Becker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems (NIPS14). MIT Press, 2002.
• 19: Antonio Pellecchia , Christian Igel , Johann Edelbrunner , Gregor Schoner, Making Driver Modeling Attractive, IEEE Intelligent Systems, v.20 n.2, p.8-12, March 2005 [doi>10.1109/MIS.2005.31]
• 20: Jan Peters , Stefan Schaal, Natural Actor-Critic, Neurocomputing, v.71 n.7-9, p.1180-1190, March, 2008 [doi>10.1016/j.neucom.2007.11.026]
• 21: J. Peters, S. Vijayakumar, and S. Schaal. Reinforcement learning for humanoid robotics. In Proc. 3rd IEEE-RAS Int 'l Conf. on Humanoid Robots, pages 29--30, 2003.
• 22: M. Riedmiller, J. Peters, and S. Schaal. Evaluation of policy gradient methods and variants on the cart-pole benchmark. In Proc. IEEE Int'l Symposium on Approximate Dynamic Programming and Reinforcement Learning (ADPRL 2007), pages 254--261, 2007.
• 23: C. Schmidt, J. Branke, and S. Chick. Integrating techniques from statistical ranking into evolutionary algorithms. In Applications of Evolutionary Computing, volume 3907 of LNCS, pages 752--763. Springer, 2006.
• 24: Nils T. Siebel , Gerald Sommer, Evolutionary reinforcement learning of artificial neural networks, International Journal of Hybrid Intelligent Systems, v.4 n.3, p.171-183, August 2007
• 25: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 26: R. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 12, pages 1057--1063, 2000.
• 27: Thorsten Suttorp , Nikolaus Hansen , Christian Igel, Efficient covariance matrix update for variable metric evolution strategies, Machine Learning, v.75 n.2, p.167-197, May 2009 [doi>10.1007/s10994-009-5102-1]
• 28: Shimon Whiteson , Peter Stone, Evolutionary Function Approximation for Reinforcement Learning, The Journal of Machine Learning Research, 7, p.877-917, 12/1/2006

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Performance

Keywords:
covariance matrix adaptation evolution strategy, direct policy search, reinforcement learning, uncertainty handling