A survey of formal theoretical advances regarding XCS
David Pätzel, Anthony Stein, Jörg Hähner · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2019
Learning Classifier Systems (LCSs) are a unique machine learning paradigm. The probably most well-known and investigated instance of these is XCS. LCSs, and with them, XCS, have developed in parallel to mathematically more rigorously founded paradigms such as today's reinforcement learning. This is probably the reason why XCS was initially defined without a formal basis. Nevertheless, the pursuit of a formal understanding of XCS has been one of the primary goals since its invention. Over the years, this led to a large and seemingly underestimated body of formal analysis of it. We present our try at a comprehensive overview of the various angles from which XCS was regarded formally. With this paper, we aim at (1) mitigating the misconception we sometimes observed that research on XCS contains some sort of 'formal theory gap', (2) supporting researchers interested in formal advances regarding XCS and (3) identifying future research directions.