Abstract
We characterize the class of nondeterministic ω-automata that can be used for the analysis of finite Markov decision processes (MDPs). We call these automata ‘good-for-MDPs’ (GFM). We show that GFM automata are closed under classic simulation as well as under more powerful simulation relations that leverage properties of optimal control strategies for MDPs. This closure enables us to exploit state-space reduction techniques, such as those based on direct and delayed simulation, that guarantee simulation equivalence. We demonstrate the promise of GFM automata by defining a new class of automata with favorable properties—they are Büchi automata with low branching degree obtained through a simple construction—and show that going beyond limit-deterministic automata may significantly benefit reinforcement learning.
Original language | English |
---|---|
Title of host publication | Tools and Algorithms for the Construction and Analysis of Systems |
Subtitle of host publication | 26th International Conference, TACAS 2020, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Dublin, Ireland, April 25–30, 2020, Proceedings |
Editors | Armin Biere, David Parker |
Place of Publication | Cham |
Publisher | Springer |
Pages | 306-323 |
Number of pages | 18 |
Volume | Part I |
ISBN (Electronic) | 978-3-030-45190-5 |
ISBN (Print) | 978-3-030-45189-9 |
DOIs | |
Publication status | Published - 2020 |
Externally published | Yes |
Event | 26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2020 - Dublin, Ireland Duration: 25 Apr 2020 → 30 Apr 2020 Conference number: 26 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 12078 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2020 |
---|---|
Abbreviated title | TACAS |
Country/Territory | Ireland |
City | Dublin |
Period | 25/04/20 → 30/04/20 |