Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2019.5
URN: urn:nbn:de:0030-drops-109076
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10907/
Kretínský, Jan ; Meggendorfer, Tobias
Of Cores: A Partial-Exploration Framework for Markov Decision Processes
| pdf-format: |
|
Abstract
We introduce a framework for approximate analysis of Markov decision processes (MDP) with bounded-, unbounded-, and infinite-horizon properties. The main idea is to identify a "core" of an MDP, i.e., a subsystem where we provably remain with high probability, and to avoid computation on the less relevant rest of the state space. Although we identify the core using simulations and statistical techniques, it allows for rigorous error bounds in the analysis. Consequently, we obtain efficient analysis algorithms based on partial exploration for various settings, including the challenging case of strongly connected systems.
BibTeX - Entry
@InProceedings{kretnsk_et_al:LIPIcs:2019:10907,
author = {Jan Kret{\'\i}nsk{\'y} and Tobias Meggendorfer},
title = {{Of Cores: A Partial-Exploration Framework for Markov Decision Processes}},
booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)},
pages = {5:1--5:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-121-4},
ISSN = {1868-8969},
year = {2019},
volume = {140},
editor = {Wan Fokkink and Rob van Glabbeek},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10907},
URN = {urn:nbn:de:0030-drops-109076},
doi = {10.4230/LIPIcs.CONCUR.2019.5},
annote = {Keywords: Markov Decision Processes, Reachability, Approximation}
}
| Keywords: | Markov Decision Processes, Reachability, Approximation | |
| Seminar: | 30th International Conference on Concurrency Theory (CONCUR 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 20.08.2019 |
