Reinforcement learning for games: failures and successes

ABSTRACT

We apply CMA-ES, an evolution strategy with covariance matrix adaptation, and TDL (Temporal Difference Learning) to reinforcement learning tasks. In both cases these algorithms seek to optimize a neural network which provides the policy for playing a simple game (TicTacToe). Our contribution is to study the effect of varying learning conditions on learning speed and quality. Certain initial failures with wrong fitness functions lead to the development of new fitness functions, which allow fast learning. These new fitness functions in combination with CMA-ES reduce the number of required games needed for training to the same order of magnitude as TDL.

The selection of suitable features is also of critical importance for the learning success. It could be shown that using the raw board position as an input feature is not very effective -- and it is orders of magnitudes slower than different feature sets which exploit the symmetry of the game. We develop a measure "feature set utility", F_U, which allows to characterize a given feature set in advance. We show that the lower bound provided by F_U is largely in accordance with the results from our repeated experiments for very different learning algorithms, CMA-ES and TDL.

REFERENCES

• 1: F. Gruau, D. Whitley, and L. Pyeatt. A comparison between cellular encoding and direct encoding for genetic neural networks.
• 2: In J.R.K. et al., editor, Genetic Programming 1996: Proceedings of the First Annual Conference, Stanford University, CA, USA, pages 81--89, 1996.
• 3: N. Hansen. CMA evolution strategy source code. http://www.lri.fr/ hansen/cmaes_inmatlab.html, 2008.
• 4: 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]
• 5: N. Hansen, A. Ostermeier, and A. Gawelczyk. Adapting arbitrary normal mutation distributions in evolution strategies: the covariance matrix adaptation. In Proc. IEEE International Conference on Evolutionary Computation, pages 312--317. Morgan Kaufmann, 1996.
• 6: C. Igel. Neuroevolution for reinforcement learning using evolution strategies. In R.S. et al., editor, Proc. Congress on Evolutionary Computation (CEC 2003), pages 2588--2595, 2003.
• 7: W. Kantschik. Genetische Programmierung und Schach. PhD thesis, Universität Dortmund, Germany, 2006.
• 8: K.-J. Kim and S.-B. Cho. Systematically incorporating domain-specific knowledge into evolutionary speciated checkers players. IEEE Transactions on evolutionary computation, 6:615--627, 2005.
• 9: Wolfgang Konen , Thomas Bartz---Beielstein, Reinforcement Learning: Insights from Interesting Failures in Parameter Selection, 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_48]
• 10: S. Lucas. Investigating learning rates for evolution and temporal difference learning. In Proc. IEEE Symposium on Computational Intelligence and Games CIG2008, Perth, Australia, December 2008. IEEE Press.
• 11: D.E. Moriarty and R. Miikkulainen. Discovering complex othello strategies through evolutionary neural networks. Connection Science, 7:195--209, 1995.
• 12: 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]
• 13: A. Samuel. Some studies in machine learning using the game of checkers. IBM journal of Research and Development, 3(3):210--229, 1959.
• 14: C. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27:379--423, 1948.
• 15: 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]
• 16: M. Stenmark. Synthesizing board evaluation functions for Connect4 using machine learning techniques. Master's thesis, Ostfold University College, Norway, 2005.
• 17: Richard Stuart Sutton, Temporal credit assignment in reinforcement learning, University of Massachusetts Amherst, 1984
• 18: Richard S. Sutton, Learning to Predict by the Methods of Temporal Differences, Machine Learning, v.3 n.1, p.9-44, August 1988 [doi>10.1023/A:1022633531479]
• 19: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 20: Gerald Tesauro, TD-Gammon, a self-teaching backgammon program, achieves master-level play, Neural Computation, v.6 n.2, p.215-219, March 1994 [doi>10.1162/neco.1994.6.2.215]
• 21: D. Whitley. Genetic algorithms and neural networks. In Genetic algorithms in Engineering and Computer Science, chapter 11. Wiley, 1995.
• 22: Darrell Whitley , Stephen Dominic , Rajarshi Das , Charles W. Anderson, Genetic Reinforcement Learning for Neurocontrol Problems, Machine Learning, v.13 n.2-3, p.259-284, Nov./Dec. 1993 [doi>10.1007/BF00993045]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Games

General Terms:
Algorithms, Experimentation

Keywords:
evolution strategies, failures, games, learning