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.
- 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.]]Google Scholar
- M. V. Butz and S. W. Wilson. An algorithmic description of xcs. Journal of Soft Computing, 6(3--4):144--153, 2002.]]Google ScholarCross Ref
- 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.]]Google Scholar
- T. J. Perkins and D. Precup. A convergent form of approximate policy iteration. pages 1595--1602, 2003.]]Google Scholar
- 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.]]Google Scholar
- R. S. Sutton and A. G. Barto. Reinforcement Learning -- An Introduction. MIT Press, 1998.]] Google ScholarDigital Library
- G. Tesauro. TD-gammon, a self-teaching backgammon program, achieves master-level play. Neural Computation, 6(2):215--219, 1994.]] Google ScholarDigital Library
- S. Thrun and A. Schwartz. Issues in Using Function Approximation for Reinforcement Learning. 1993.]]Google Scholar
- B. Widrow and M. E. Hoff. Adaptive Switching Circuits, chapter Neurocomputing: Foundation of Research, pages 126--134. The MIT Press, Cambridge, 1988.]] Google ScholarDigital Library
- S. W. Wilson. Classifier Fitness Based on Accuracy. Evolutionary Computation, 3(2):149--175, 1995. http://prediction-dynamics.com/.]] Google ScholarDigital Library
- S. W. Wilson. Mining Oblique Data with XCS. volume 1996 of Lecture notes in Computer Science, pages 158--174. Springer-Verlag, Apr. 2001.]] Google ScholarDigital Library
- S. W. Wilson. Classifiers that approximate functions. Journal of Natural Computating, 1(2-3):211--234, 2002.]] Google ScholarDigital Library
- 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.]]Google Scholar
Index Terms
- XCS with computed prediction in multistep environments
Recommendations
Standard and averaging reinforcement learning in XCS
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computationThis paper investigates reinforcement learning (RL) in XCS. First, it formally shows that XCS implements a method of generalized RL based on linear approximators, in which the usual input mapping function translates the state-action space into a niche ...
Classifier prediction based on tile coding
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computationThis 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 ...
Empirical analysis of generalization and learning in XCS with gradient descent
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computationWe analyze generalization and learning in XCS with gradient descent. At first, we show that the addition of gradient in XCS may slow down learning because it indirectly decreases the learning rate. However, in contrast to what was suggested elsewhere, ...
Comments