Classifier prediction based on tile coding

ABSTRACT

This paper introduces XCSF extended with tile coding prediction: each classifier implements a tile coding approximator; the genetic algorithm is used to adapt both classifier conditions (i.e., to partition the problem) and the parameters of each approximator; thus XCSF evolves an ensemble of tile coding approximators instead of the typical monolithic approximator used in reinforcement learning. The paper reports a comparison between (i) XCSF with tile coding prediction and (ii) plain tile coding. The results show that XCSF with tile coding always reaches optimal performance, it usually learns as fast as the best parametrized tile coding, and it can be faster than the typical tile coding setting. In addition, the analysis of the evolved tile coding ensembles shows that XCSF actually adapts local approximators following what is currently considered the best strategy to adapt the tile coding parameters in a given problem.

REFERENCES

• 1: L. Booker. Approximating value functions in classifier systems. volume 183 of Studies in Fuzziness and Soft Computing, pages 45--61. Springer, 2005.
• 2: 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.
• 3: M. V. Butz and S. W. Wilson. An algorithmic description of XCS. Journal of Soft Computing, 6(3--4):144--153, 2002.
• 4: S. A. Glantz and B. K. Slinker. Primer of Applied Regression & Analysis of Variance. McGraw Hill, 2001. second edition.
• 5: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, Extending XCSF beyond linear approximation, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068319]
• 6: P. L. Lanzi, D. Loiacono, S. W. Wilson, and D. E. Goldberg. XCS with Computed Prediction for the Learning of Boolean Functions. In Proceedings of the IEEE Congress on Evolutionary Computation -- CEC-2005, Edinburgh, UK, 2005. IEEE.
• 7: Pier Luca Lanzi , Daniele Loiacono , Stewart W. Wilson , David E. Goldberg, XCS with computed prediction in multistep environments, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068323]
• 8: Justus H. Piater , Paul R. Cohen , Xiaoqin Zhang , Michael Atighetchi, A Randomized ANOVA Procedure for Comparing Performance Curves, Proceedings of the Fifteenth International Conference on Machine Learning, p.430-438, July 24-27, 1998
• 9: S. I. Reynolds. Reinforcement Learning with Exploration. PhD thesis, School of Computer Science. The University of Birmingham, Birmingham, B15 2TT, Dec. 2002.
• 10: A. A. Sherstov and P. Stone. Function approximation via tile coding: Automating parameter choice. In Proc. Symposium on Abstraction, Reformulation, and Approximation (SARA-05), Edinburgh, Scotland, UK, 2005.
• 11: 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.
• 12: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 13: 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]
• 14: 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]

INDEX TERMS

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

General Terms:
Algorithms, Performance

Keywords:
LCS, RL, XCS, tile coding