Sequential problems that test generalization in learning classifier systems

摘要

We present an approach to build sequential decision making problems which can test the generalization capabilities of classifier systems. The approach can be applied to any sequential problem denned over a binary domain and it generates a new problem with bounded sequential difficulty and bounded generalization difficulty. As an example, we applied the approach to generate two problems with simple sequential structure, huge number of states (more than a million), and many generalizations. These problems are used to compare a classifier system with effective generalization (XCS) and a learner without generalization (Q-learning). The experimental results confirm what was previously found mainly using single-step problems: also in sequential problems with huge state spaces, XCS can generalize effectively by detecting those substructures that are necessary for optimal sequential behavior.