Hoeffding and Bernstein races for selecting policies in evolutionary direct policy search

ABSTRACT

Uncertainty arises in reinforcement learning from various sources, and therefore it is necessary to consider statistics based on several roll-outs for evaluating behavioral policies. We add an adaptive uncertainty handling based on Hoeffding and empirical Bernstein races to the CMA-ES, a variable metric evolution strategy proposed for direct policy search. The uncertainty handling adjusts individually the number of episodes considered for the evaluation of a policy. The performance estimation is kept just accurate enough for a sufficiently good ranking of candidate policies, which is in turn sufficient for the CMA-ES to find better solutions. This increases the learning speed as well as the robustness of the algorithm.

REFERENCES

• 1: Jean-Yves Audibert , Rémi Munos , Csaba Szepesvári, Tuning Bandit Algorithms in Stochastic Environments, Proceedings of the 18th international conference on Algorithmic Learning Theory, October 01-04, 2007, Sendai, Japan [doi>10.1007/978-3-540-75225-7_15]
• 2: Beyer, H.-G. (2007). Evolution strategies. Scholarpedia, 2, 1965.
• 3: Mauro Birattari , Thomas Stützle , Luis Paquete , Klaus Varrentrapp, A Racing Algorithm for Configuring Metaheuristics, Proceedings of the Genetic and Evolutionary Computation Conference, p.11-18, July 09-13, 2002
• 4: Coulom, R. (2002). Apprentissage par renforcement utilisant des reseaux de neurones, avec des applications au controle moteur. These de doctorat, Institut National Polytechnique de Grenoble.
• 5: 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
• 6: 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]
• 7: Hansen, N., Niederberger, A. S. P., Guzzella, L., & Koumoutsakos, P. (2009). A method for handling uncertainty in evolutionary optimization with an application to feedback control of combustion. IEEE Transactions on Evolutionary Computation, 13, 180--197.
• 8: 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]
• 9: Heidrich-Meisner, V., & Igel, C. (2009). Uncertainty handling CMA-ES for reinforcement learning. Genetic and Evolutionary Computation Conference (GECCO 2009). ACM Press.
• 10: Maron, O., & Moore, A. W. (1994). Hoeffding races: Accelerating model selection search for classification and function approximation. Advances in Neural Information Processing Systems (pp. 59--66). Morgan Kaufmann Publishers.
• 11: Oden Maron , Andrew W. Moore, The Racing Algorithm: Model Selection for Lazy Learners, Artificial Intelligence Review, v.11 n.1-5, p.193-225, Feb. 1997 [doi>10.1023/A:1006556606079]
• 12: Volodymyr Mnih , Csaba Szepesvári , Jean-Yves Audibert, Empirical Bernstein stopping, Proceedings of the 25th international conference on Machine learning, p.672-679, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390241]
• 13: 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]
• 14: 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]
• 15: Schmidt, C., Branke, J., & Chick, S. (2006). Integrating techniques from statistical ranking into evolutionary algorithms. Applications of Evolutionary Computing (pp. 752--763). Springer-Verlag.
• 16: 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
• 17: Peter Stagge, Averaging Efficiently in the Presence of Noise, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.188-200, September 27-30, 1998
• 18: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 19: 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]
• 20: Shimon Whiteson , Peter Stone, Evolutionary Function Approximation for Reinforcement Learning, The Journal of Machine Learning Research, 7, p.877-917, 12/1/2006
• 21: Yuan, B., & Gallagher, M. (2004). Statistical racing techniques for improved empirical evaluation of evolutionary algorithms. Parallel Problem Solving from Nature (PPSN VIII) (pp. 172--181). Springer-Verlag.

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.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory