Of Cores: A Partial-Exploration Framework for Markov Decision Processes

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

KŘETÍNSKÝ Jan MEGGENDORFER Tobias

Year of publication 2019
Type Article in Proceedings
Conference 30th International Conference on Concurrency Theory (CONCUR 2019)
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.4230/LIPIcs.CONCUR.2019.5
Keywords Partial Exploration; Markov Decision Processes; Verification
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.