Atsushi WADA, Keiki TAKADAMA, Katsunori SHIMOHARA, Osamu KATAI
Convergence and Generalization in
Learning Classifier Systems:
ZCS with Residual Gradient Algorithms
Abstract:Learning Classifier Systems (LCSs) are rule-based
systems possessing essential functions
of (a) reinforcement learning, (b) state generalization
and (c) rule discovery. As the first
step toward developing a theoretical basis of
LCSs, here we focus on a strong relation between
LCSs' learning process with generalization
and reinforcement learning methods
with function approximations, and aim at introducing
a proof of convergence for LCSs.
Based on our previous work, which showed
an equivalence of learning processes between
a zeroth-level classifier system (ZCS) and Q-learning
with linear function approximation,
in this paper, we apply a residual gradient algorithm
for Q-learning to ZCS. As for the result,
we obtained an LCS with generalization
ability that guarantees convergence due to
the proof of the residual gradient algorithm
under the condition of its rule discovery process
being suppressed.