Schewe, S 
ORCID: 0000-0002-9093-9518, Tang, Q ORCID: 0000-0002-9265-3011 and Zhanabekova, T
(2023)
Deciding What Is Good-For-MDPs.
In: CONCUR 2023.
|
PDF
GFM_in_EXPTIME.pdf - Submitted version Download (1MB) | Preview |
Abstract
Nondeterministic good-for-MDPs (GFM) automata are for MDP model checking and reinforcement learning what good-for-games automata are for reactive synthesis: a more compact alternative to deterministic automata that displays nondeterminism, but only so much that it can be resolved locally, such that a syntactic product can be analysed. GFM has recently been introduced as a property for reinforcement learning, where the simpler Büchi acceptance conditions it allows to use is key. However, while there are classic and novel techniques to obtain automata that are GFM, there has not been a decision procedure for checking whether or not an automaton is GFM. We show that GFM-ness is decidable and provide an EXPTIME decision procedure as well as a PSPACE-hardness proof.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 21 Jul 2023 13:35 |
| Last Modified: | 11 Oct 2023 20:12 |
| DOI: | 10.4230/LIPIcs.CONCUR.2023.35 |
| Open Access URL: | https://arxiv.org/abs/2202.07629 |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3171819 |
Dimensions
Dimensions
