Inference of Deterministic Finite Automata via Q-Learning
This work addresses automaton inference for symbolic AI, offering a novel bridge between sub-symbolic and symbolic methods, though it appears incremental as it builds on existing Q-learning techniques.
The paper tackles the problem of inferring deterministic finite automata (DFA) by adapting Q-learning, a reinforcement learning algorithm, to reinterpret the Q-function as a DFA transition function, demonstrating this approach on several examples.
Traditional approaches to inference of deterministic finite-state automata (DFA) stem from symbolic AI, including both active learning methods (e.g., Angluin's L* algorithm and its variants) and passive techniques (e.g., Biermann and Feldman's method, RPNI). Meanwhile, sub-symbolic AI, particularly machine learning, offers alternative paradigms for learning from data, such as supervised, unsupervised, and reinforcement learning (RL). This paper investigates the use of Q-learning, a well-known reinforcement learning algorithm, for the passive inference of deterministic finite automata. It builds on the core insight that the learned Q-function, which maps state-action pairs to rewards, can be reinterpreted as the transition function of a DFA over a finite domain. This provides a novel bridge between sub-symbolic learning and symbolic representations. The paper demonstrates how Q-learning can be adapted for automaton inference and provides an evaluation on several examples.