L*-Based Learning of Markov Decision Processes

Martin Tappler*, Bernhard K. Aichernig, Giovanni Bacci, Maria Eichlseder, Kim Guldstrand Larsen

*Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

13 Citations (Scopus)
169 Downloads (Pure)

Abstract

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.
Original languageEnglish
Title of host publicationFormal Methods – The Next 30 Years - 3rd World Congress, FM 2019, Proceedings : FM 2019: Formal Methods – The Next 30 Years
EditorsMaurice H. ter Beek, Annabelle McIver, José N. Oliveira
Number of pages19
PublisherSpringer
Publication date23 Sept 2019
Pages651-669
ISBN (Print)978-3-030-30941-1
ISBN (Electronic)978-3-030-30942-8
DOIs
Publication statusPublished - 23 Sept 2019
EventInternational Symposium on Formal Methods: Formal Methods – The Next 30 Years - Porto, Portugal
Duration: 7 Oct 201911 Oct 2019
http://formalmethods2019.inesctec.pt

Conference

ConferenceInternational Symposium on Formal Methods
Country/TerritoryPortugal
CityPorto
Period07/10/201911/10/2019
Internet address
SeriesLecture Notes in Computer Science
Volume11800
ISSN0302-9743

Keywords

  • Active automata learning
  • Markov decision processes
  • Model inference

Fingerprint

Dive into the research topics of 'L*-Based Learning of Markov Decision Processes'. Together they form a unique fingerprint.

Cite this