XCS with computed prediction in multistep environments

ABSTRACT

XCSF extends the typical concept of learning classifier systems through the introduction of computed classifier prediction. Initial results show that XCSF's computed prediction can be used to evolve accurate piecewise linear approximations of simple functions. In this paper, we take XCSF one step further and apply it to typical reinforcement learning problems involving delayed rewards. In essence, we use XCSF as a method of generalized (linear) reinforcement learning to evolve piecewise linear approximations of the payoff surfaces of typical multistep problems. Our results show that XCSF can easily evolve optimal and near optimal solutions for problems introduced in the literature to test linear reinforcement learning methods.

REFERENCES

• 1: J. A. Boyan and A. W. Moore. Generalization in reinforcement learning: Safely approximating the value function. In G. Tesauro, D. S. Touretzky, and T. K. Leen, editors, Advances in Neural Information Processing Systems 7, pages 369--376, Cambridge, MA, 1995. The MIT Press.
• 2: M. V. Butz and S. W. Wilson. An algorithmic description of xcs. Journal of Soft Computing, 6(3--4):144--153, 2002.
• 3: P. L. Lanzi and M. Colombetti. An Extension to the XCS Classifier System for Stochastic Environments. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO), pages 353--360, Orlando (FL), July 1999. Morgan Kaufmann.
• 4: T. J. Perkins and D. Precup. A convergent form of approximate policy iteration. pages 1595--1602, 2003.
• 5: R. S. Sutton. Generalization in reinforcement learning: Successful examples using sparse coarse coding. In D. S. Touretzky, M. C. Mozer, and M. E. Hasselmo, editors, Advances in Neural Information Processing Systems 8, pages 1038--1044. The MIT Press, Cambridge, MA., 1996.
• 6: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 7: 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]
• 8: S. Thrun and A. Schwartz. Issues in Using Function Approximation for Reinforcement Learning. 1993.
• 9: Bernard Widrow , Marcian E. Hoff, Adaptive switching circuits, Neurocomputing: foundations of research, MIT Press, Cambridge, MA, 1988
• 10: S. W. Wilson. Classifier Fitness Based on Accuracy. Evolutionary Computation, 3(2):149--175, 1995. http://prediction-dynamics.com/.
• 11: Stewart W. Wilson, Mining Oblique Data with XCS, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.158-176, September 15-16, 2000
• 12: Stewart W. Wilson, Classifiers that approximate functions, Natural Computing: an international journal, v.1 n.2-3, p.211-234, June 2002 [doi>10.1023/A:1016535925043]
• 13: S. W. Wilson. Classifier systems for continuous payoff environments. In K. Deb, R. Poli, W. Banzhaf, H.-G. Beyer, E. Burke, P. Darwen, D. Dasgupta, D. Floreano, J. Foster, M. Harman, O. Holland, P. L. Lanzi, L. Spector, A. Tettamanzi, D. Thierens, and A. Tyrrell, editors, Genetic and Evolutionary Computation -- GECCO-2004, Part II, volume 3103 of Lecture Notes in Computer Science, pages 824--835, Seattle, WA, USA, 26-30 June 2004. Springer-Verlag.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

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

General Terms:
Algorithms, Performance

Keywords:
LCS, RL, XCS, generalization