L*-Based Learning of Markov Decision Processes (Extended Version)
This work addresses the problem of efficient model generation for systems modeled as MDPs, which is incremental as it builds on existing L*-based techniques.
The authors tackled the problem of learning deterministic Markov decision processes (MDPs) from test observations, presenting a novel L*-based algorithm that samples system traces. The result showed that their algorithm achieves better accuracy than state-of-the-art passive learning techniques with the same amount of test data.
Automata learning techniques automatically generate system models from test observations. These techniques usually fall into two categories: passive and active. Passive learning uses a predetermined data set, e.g., system logs. In contrast, active learning actively queries the system under learning, which is considered more efficient. An influential active learning technique is Angluin's L* algorithm for regular languages which inspired several generalisations from DFAs to other automata-based modelling formalisms. In this work, we study L*-based learning of deterministic Markov decision processes, first assuming an ideal setting with perfect information. Then, we relax this assumption and present a novel learning algorithm that collects information by sampling system traces via testing. Experiments with the implementation of our sampling-based algorithm suggest that it achieves better accuracy than state-of-the-art passive learning techniques with the same amount of test data. Unlike existing learning algorithms with predefined states, our algorithm learns the complete model structure including the states.