Despite two decades of work learning classifier systems researchers have had relatively little to say on the subject of what makes a problem difficult for a classifier system. Wilson's accuracy-based XCS, a promising and increasingly popular classifier system, is, we feel, the natural first choice of classifier system with which to address this issue. To make the task more tractable we limit our considerations to a restricted, but very important, class of problems. Most significantly, we consider only single step reinforcement learning problems and the use of the standard binary/ternary classifier systems language. In addition to distinguishing several dimensions of problem complexity for XCS, we consider their interactions, identify bounding cases of difficulty, and consider complexity metrics for XCS. Based on these results we suggest a simple template for ternary single step test suites to more comprehensively evaluate classifier systems.
|Translated title of the contribution||What Makes a Problem Hard for XCS?|
|Title of host publication||Advances in Learning Classifier Systems|
|Publication status||Published - 2001|
Bibliographical noteOther page information: 80-99
Other identifier: 1000606
Kovacs, T., P. L., L., Manfred, K., W., S., & S. W., W. (2001). What Makes a Problem Hard for XCS? In Advances in Learning Classifier Systems (Vol. 1996). Springer. http://www.cs.bris.ac.uk/Publications/pub_master.jsp?id=1000606