2026-08-17T07:43:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10907 2024-03-06T10:47:09Z ddc:004 open_access

Of Cores: A Partial-Exploration Framework for Markov Decision Processes Křetínský, Jan Meggendorfer, Tobias Markov Decision Processes Reachability Approximation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Křetínský and Tobias Meggendorfer 2019 Is Part Of LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2019.5 urn:nbn:de:0030-drops-109076 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.5 eng https://creativecommons.org/licenses/by/3.0/legalcode