Learning classifier system equivalent with reinforcement learning with function approximation

ABSTRACT

We present an experimental comparison of the reinforcement process between Learning Classifier System (LCS) and Reinforcement Learning (RL) with function approximation (FA) method, regarding their generalization mechanisms. To validate our previous theoretical analysis that derived equivalence of reinforcement process between LCS and RL, we introduce a simple test environment named Gridworld, which can be applied to both LCS and RL with three different classes of generalization: (1) tabular representation; (2) state aggregation; and (3) linear approximation. From the simulation experiments comparing LCS with its GA-inactivated and corresponding RL method, all the cases regarding the class of generalization showed identical results with the criteria of performance and temporal difference (TD) error, thereby verifying the equivalence predicted from the theory.

REFERENCES

• 1: Butz, M., Kovacs, T., Lanzi, P. L., Wilson, S. W.: Toward a theory of generalization and learning in xcs. IEEE Transactions on Evolutionary Computation 8 (2004) 28--46
• 2: M. V. Butz, D. E. Goldberg, and P. L. Lanzi. Bounding learning time in XCS. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), 2004.
• 3: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 4: P. L. Lanzi. Learning classifier systems from a reinforcement learning perspective. Soft Computing, 6:162--170, 2002.
• 5: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 6: S. W. Wilson. ZCS: A zeroth level classifier system. Evolutionary Computation, 2(1):1--18, 1994.
• 7: S. W. Wilson. Classifier fitness based on accuracy. Evolutionary Computation, 3(2):149--175, 1995.

INDEX TERMS

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

General Terms:
Algorithms, Design, Theory

Keywords:
function approximation, genetic-based machine learning, learning classifier systems, reinforcement learning