Limitations of learning in automata-based systems.

Oliveira, Fernando S.

Abstract

In this article, we aim to analyze the limitations of learning in automata-based systems by introducing the L+ algorithm to replicate quasi-perfect learning, i.e., a situation in which the learner can get the correct answer to any of his queries. This extreme assumption allows the generalization of any limitations of the learning algorithm to less sophisticated learning systems. We analyze the conditions under which the L+ infers the correct automaton and when it fails to do so. In the context of the repeated prisoners' dilemma, we exemplify how the L+ may fail to learn the correct automaton. We prove that a sufficient condition for the L+ algorithm to learn the correct automaton is to use a large number of look-ahead steps. Finally, we show empirically, in the product differentiation problem, that the computational time of the L+ algorithm is polynomial on the number of states but exponential on the number of agents.

Citation

OLIVEIRA, F.S. 2010. Limitations of learning in automata-based systems. European journal of operational research [online], 203(3), pages 684-691. Available from: https://doi.org/10.1016/j.ejor.2009.08.018

• Journal Article Type: Article
• Acceptance Date: Aug 27, 2009
• Online Publication Date: Jan 13, 2011
• Publication Date: Jun 16, 2010
• Deposit Date: Oct 21, 2023
• Publicly Available Date: Nov 15, 2023
• Journal: European journal of operational research
• Print ISSN: 0377-2217
• Electronic ISSN: 1872-6860
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 203
• Issue: 3
• Pages: 684-691
• DOI: https://doi.org/10.1016/j.ejor.2009.08.018
• Keywords: Artificial intelligence; Machine learning; Knowledge-based systems
• Public URL: https://rgu-repository.worktribe.com/output/2114774