Language Inference with Multi-head Automata through Reinforcement Learning
This work addresses language inference for computational linguistics and AI, but it is incremental as it applies existing reinforcement learning methods to a new automaton model.
The paper tackled the problem of recognizing formal languages by modeling agents as multi-head automata and training them with reinforcement learning, achieving results where genetic algorithms generally outperformed Q-learning, though Q-learning was faster for regular languages.
The purpose of this paper is to use reinforcement learning to model learning agents which can recognize formal languages. Agents are modeled as simple multi-head automaton, a new model of finite automaton that uses multiple heads, and six different languages are formulated as reinforcement learning problems. Two different algorithms are used for optimization. First algorithm is Q-learning which trains gated recurrent units to learn optimal policies. The second one is genetic algorithm which searches for the optimal solution by using evolution inspired operations. The results show that genetic algorithm performs better than Q-learning algorithm in general but Q-learning algorithm finds solutions faster for regular languages.