L*-Based Learning of Markov Decision Processes

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

*Kontaktforfatter

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TitelProc. of International Symposium on Formal Methods : FM 2019: Formal Methods – The Next 30 Years
RedaktørerMaurice H. ter Beek, Annabelle McIver, José N. Oliveira
Antal sider669
Vol/bind11800
Publikationsdato23 sep. 2019
Sider651
ISBN (Trykt)978-3-030-30941-1
ISBN (Elektronisk)978-3-030-30942-8
DOI
StatusUdgivet - 23 sep. 2019
BegivenhedInternational Symposium on Formal Methods: Formal Methods – The Next 30 Years - Porto, Portugal
Varighed: 7 okt. 201911 okt. 2019
http://formalmethods2019.inesctec.pt

Konference

KonferenceInternational Symposium on Formal Methods
LandPortugal
ByPorto
Periode07/10/201911/10/2019
Internetadresse
NavnLecture Notes in Computer Science
ISSN0302-9743

Fingerprint

Learning algorithms
Sampling
Formal languages
Model structures
Testing
Experiments
Problem-Based Learning

Citer dette

Tappler, M., Aichernig, B. K., Bacci, G., Eichlseder, M., & Larsen, K. G. (2019). L*-Based Learning of Markov Decision Processes. I M. H. ter Beek, A. McIver, & J. N. Oliveira (red.), Proc. of International Symposium on Formal Methods: FM 2019: Formal Methods – The Next 30 Years (Bind 11800, s. 651). Lecture Notes in Computer Science https://doi.org/10.1007/978-3-030-30942-8
Tappler, Martin ; Aichernig, Bernhard K. ; Bacci, Giovanni ; Eichlseder, Maria ; Larsen, Kim Guldstrand. / L*-Based Learning of Markov Decision Processes. Proc. of International Symposium on Formal Methods: FM 2019: Formal Methods – The Next 30 Years. red. / Maurice H. ter Beek ; Annabelle McIver ; José N. Oliveira. Bind 11800 2019. s. 651 (Lecture Notes in Computer Science).
@inproceedings{f52a42094195456a85144a3af53bfa16,
title = "L*-Based Learning of Markov Decision Processes",
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.",
author = "Martin Tappler and Aichernig, {Bernhard K.} and Giovanni Bacci and Maria Eichlseder and Larsen, {Kim Guldstrand}",
year = "2019",
month = "9",
day = "23",
doi = "10.1007/978-3-030-30942-8",
language = "English",
isbn = "978-3-030-30941-1",
volume = "11800",
series = "Lecture Notes in Computer Science",
publisher = "Physica-Verlag",
pages = "651",
editor = "{ ter Beek}, {Maurice H.} and Annabelle McIver and Oliveira, {Jos{\'e} N.}",
booktitle = "Proc. of International Symposium on Formal Methods",

}

Tappler, M, Aichernig, BK, Bacci, G, Eichlseder, M & Larsen, KG 2019, L*-Based Learning of Markov Decision Processes. i MH ter Beek, A McIver & JN Oliveira (red), Proc. of International Symposium on Formal Methods: FM 2019: Formal Methods – The Next 30 Years. bind 11800, Lecture Notes in Computer Science, s. 651, Porto, Portugal, 07/10/2019. https://doi.org/10.1007/978-3-030-30942-8

L*-Based Learning of Markov Decision Processes. / Tappler, Martin; Aichernig, Bernhard K.; Bacci, Giovanni; Eichlseder, Maria; Larsen, Kim Guldstrand.

Proc. of International Symposium on Formal Methods: FM 2019: Formal Methods – The Next 30 Years. red. / Maurice H. ter Beek; Annabelle McIver; José N. Oliveira. Bind 11800 2019. s. 651 (Lecture Notes in Computer Science).

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

TY - GEN

T1 - L*-Based Learning of Markov Decision Processes

AU - Tappler, Martin

AU - Aichernig, Bernhard K.

AU - Bacci, Giovanni

AU - Eichlseder, Maria

AU - Larsen, Kim Guldstrand

PY - 2019/9/23

Y1 - 2019/9/23

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-030-30942-8

DO - 10.1007/978-3-030-30942-8

M3 - Article in proceeding

SN - 978-3-030-30941-1

VL - 11800

T3 - Lecture Notes in Computer Science

SP - 651

BT - Proc. of International Symposium on Formal Methods

A2 - ter Beek, Maurice H.

A2 - McIver, Annabelle

A2 - Oliveira, José N.

ER -

Tappler M, Aichernig BK, Bacci G, Eichlseder M, Larsen KG. L*-Based Learning of Markov Decision Processes. I ter Beek MH, McIver A, Oliveira JN, red., Proc. of International Symposium on Formal Methods: FM 2019: Formal Methods – The Next 30 Years. Bind 11800. 2019. s. 651. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-030-30942-8