Illinois Genetic Algorithms Laboratory

Butz, M.V.,Lanzi, P.L. (2008)
TR No.: 2008007 | Download PDF | Download PS

We present an approach to build sequential decision making problems which can challenge the generalization capabilities of classifier systems. The approach can be applied to any sequential problem defined over a binary domain and it generates a new problem with bounded sequential difficulty and bounded generalization difficulty. As an example, the approach is used here to generate two problems with a 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 context-dependent structures that are necessary for optimal sequential behavior.