A Bayesian approach to learning classifier systems in uncertain environments

ABSTRACT

In this paper we propose a Bayesian framework for XCS [9], called BXCS. Following [4], we use probability distributions to represent the uncertainty over the classifier estimates of payoff. A novel interpretation of classifier and an extension of the accuracy concept are presented. The probabilistic approach is aimed at increasing XCS learning capabilities and tendency to evolve accurate, maximally general classifiers, especially when uncertainty affects the environment or the reward function. We show that BXCS can approximate optimal solutions in stochastic environments with a high level of uncertainty.

REFERENCES

• 1: M. Butz, T. Kovacs, P. Lanzi, and S. Wilson. Toward a theory of generalization and learning in XCS. IEEE Trans. On Evolutionary Computation, 8(1), 2004.
• 2: Martin Butz , Stewart W. Wilson, An Algorithmic Description of XCS, Revised Papers from the Third International Workshop on Advances in Learning Classifier Systems, p.253-272, September 15-16, 2000
• 3: G. Casella and R. Berger. Statistical Inference. Wadsworth & Brooks/Cole, 1990.
• 4: Richard Dearden , Nir Friedman , Stuart Russell, Bayesian Q-learning, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.761-768, July 1998, Madison, Wisconsin, United States
• 5: P. Lanzi. An analysis of the memory mechanism of XCS. In Proc. of the 3rd Annu. Genetic Programming Conference, pages 593--623. Morgan Kaufmann, 1998.
• 6: P. Lanzi. The XCS Library. 2003. http://xcslib.sourceforge.net.
• 7: P. Lanzi and M. Colombetti. An extension to the XCS classifier systems for stochastic environments. In Proc. of the Genetic and Evolutionary Computation Conference, pages 345--352. Morgan Kauffman:San Francisco, CA, 1999.
• 8: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 9: S. Wilson. Classifier fitness based on accuracy. Evol. Comput., 3(2):149--175, 1995.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Bayesian Q-learning, XCS, exploration strategy, learning classifier systems, value of information