# L*-Based Learning of Markov Decision Processes (Extended Version)

arXiv: https://arxiv.org/abs/1906.12239 · HTML: https://mlsanity.com/paper/1906.12239/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2019.

## Built on by (most cited first, 4 of 4)

- [Online Shielding for Reinforcement Learning](https://mlsanity.com/paper/2212.01861/) (2022)
- [Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning](https://mlsanity.com/paper/2107.04633/) (2021)
- [Towards Efficient Active Learning of PDFA](https://mlsanity.com/paper/2206.09004/) (2022)
- [Probabilistic Black-Box Checking via Active MDP Learning](https://mlsanity.com/paper/2308.07930/) (2023)

## Abstract (arXiv)

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.