Comparing evolutionary and temporal difference methods in a reinforcement learning domain

ABSTRACT

Both genetic algorithms (GAs) and temporal difference (TD) methods have proven effective at solving reinforcement learning (RL) problems. However, since few rigorous empirical comparisons have been conducted, there are no general guidelines describing the methods' relative strengths and weaknesses. This paper presents the results of a detailed empirical comparison between a GA and a TD method in Keepaway, a standard RL benchmark domain based on robot soccer. In particular, we compare the performance of NEAT [19], a GA that evolves neural networks, with Sarsa [16, 17], a popular TD method. The results demonstrate that NEAT can learn better policies in this task, though it requires more evaluations to do so. Additional experiments in two variations of Keepaway demonstrate that Sarsa learns better policies when the task is fully observable and NEAT learns faster when the task is deterministic. Together, these results help isolate the factors critical to the performance of each method and yield insights into their general strengths and weaknesses.

REFERENCES

• 1: T. Beielstein and S. Markon. Threshold selection, hypothesis tests and DOE methods. In 2002 Congresss on Evolutionary Computation, pages 777--782, 2002.
• 2: S. J. Bradtke and M. O. Duff. Reinforcement learning methods for continuous-time Markov decision problems. In G. Tesauro, D. Touretzky, and T. Leen, editors, Advances in Neural Information Processing Systems 7, pages 393--400, San Mateo, CA, 1995. Morgan Kaufmann.
• 3: David E. Goldberg , Jon Richardson, Genetic algorithms with sharing for multimodal function optimization, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.41-49, October 1987, Cambridge, Massachusetts, United States
• 4: F. Gomez and R. Miikkulainen. Robust nonlinear control through neuroevolution. Technical Report AI02-292, Department of Computer Sciences, University of Texas at Austin, 2002.
• 5: Faustino J. Gomez , Jürgen Schmidhuber, Co-evolving recurrent neurons learn deep memory POMDPs, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068092]
• 6: F. Gruau, D. Whitley, and L. Pyeatt. A comparison between cellular encoding and direct encoding for genetic neural networks. In J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo, editors, Genetic Programming 1996: Proceedings of the First Annual Conference, pages 81--89. MIT Press, 1996.
• 7: William H. Hsu , Steven M. Gustafson, Genetic Programming And Multi-agent Layered Learning By Reinforcements, Proceedings of the Genetic and Evolutionary Computation Conference, p.764-771, July 09-13, 2002
• 8: K. Kostiadis and H. Hu. KaBaGe-RL: Kanerva-based generalisation and reinforcement learning for possession football. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2001), October 2001.
• 9: David E. Moriarty , Risto Mikkulainen, Efficient reinforcement learning through symbiotic evolution, Machine Learning, v.22 n.1-3, p.11-32, Jan./Feb./March 1996 [doi>10.1007/BF00114722]
• 10: I. Noda, H. Matsubara, K. Hiraki, and I. Frank. Soccer server: A tool for research on multiagent systems. Applied Artificial Intelligence, 12:233--250, 1998.
• 11: J. B. Pollack, A. D. Blair, and M. Land. Coevolution of a backgammon player. In C. G. Langton and K. Shimohara, editors, Artificial Life V: Proc. of the Fifth Int. Workshop on the Synthesis and Simulation of Living Systems, pages 92--98, Cambridge, MA, 1997. The MIT Press.
• 12: Mitchell A. Potter , Kenneth A. De Jong, Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents, Evolutionary Computation, v.8 n.1, p.1-29, March 2000 [doi>10.1162/106365600568086]
• 13: M. J. D. Powell, Radial basis functions for multivariable interpolation: a review, Algorithms for approximation, Clarendon Press, New York, NY, 1987
• 14: Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, John Wiley & Sons, Inc., New York, NY, 1994
• 15: N. J. Radcliffe. Genetic set recombination and its application to neural network topology optimization. Neural computing and applications, 1(1):67--90, 1993.
• 16: G. A. Rummery and M. Niranjan. On-line Q-learning using connectionist systems. Technical Report CUED/F-INFENG-RT 116, Engineering Department, Cambridge University, 1994.
• 17: Satinder P. Singh , Richard S. Sutton, Reinforcement learning with replacing eligibility traces, Machine Learning, v.22 n.1-3, p.123-158, Jan./Feb./March 1996 [doi>10.1007/BF00114726]
• 18: 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
• 19: Kenneth O. Stanley , Risto Miikkulainen, Evolving neural networks through augmenting topologies, Evolutionary Computation, v.10 n.2, p.99-127, Summer 2002 [doi>10.1162/106365602320169811 ]
• 20: K. O. Stanley and R. Miikkulainen. Competitive coevolution through evolutionary complexification. Journal of Artificial Intelligence Research, 21:63--100, 2004.
• 21: K. O. Stanley and R. Miikkulainen. Evolving a roving eye for go. In Proceedinngs of the Genetic and Evolutionary Computation Conference, 2004.
• 22: P. Stone, G. Kuhlmann, M. E. Taylor, and Y. Liu. Keepaway soccer: From machine learning testbed to benchmark. In I. Noda, A. Jacoff, A. Bredenfeld, and Y. Takahashi, editors, RoboCup-2005: Robot Soccer World Cup IX. Springer Verlag, Berlin, 2006. To appear.
• 23: P. Stone, R. S. Sutton, and G. Kuhlmann. Reinforcement learning for RoboCup-soccer keepaway. Adaptive Behavior, 13(3):165--188, 2005.
• 24: R. S. Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding. In Advances in Neural Information Processing Systems 8, pages 1038--1044, 1996.
• 25: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 26: Shimon Whiteson , Nate Kohl , Risto Miikkulainen , Peter Stone, Evolving Soccer Keepaway Players Through Task Decomposition, Machine Learning, v.59 n.1-2, p.5-30, May 2005 [doi>10.1007/s10994-005-0460-9]
• 27: S. Whiteson and P. Stone. Evolutionary function approximation for reinforcement learning. Journal of Machine Learning Research, 2006. To appear.
• 28: X. Yao. Evolving artificial neural networks. Proceedings of the IEEE, 87(9):1423--1447, 1999.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
empirical study, genetic algorithms, machine learning, performance analysis