What is XCS?

XCS is a machine learning algorithm that effectively combines an evolutionary algorithm and reinforcement learning to solve the n-armed bandit problem. The algorithm belongs to a broad family of what are known as learning classifier systems, which evolve populations of matching rules that are tasked with competitively determining the optimal action to take in each iteration. It breaks from earlier learning classifier systems in that it bases its evolutionary fitness measure on the accuracies of the reward prediction rules rather than their predicted or accumulated rewards, which significantly improves the convergence and stability of the population. The net result is that the algorithm tends to find a (nearly) minimal set of matching rules which fully describe the solution to the problem in a maximally general way, within the constraints of the encoding used.