Jan Křetínský ; Tobias Meggendorfer - Of Cores: A Partial-Exploration Framework for Markov Decision Processes

lmcs:5978 - Logical Methods in Computer Science, October 9, 2020, Volume 16, Issue 4 - https://doi.org/10.23638/LMCS-16(4:3)2020
Of Cores: A Partial-Exploration Framework for Markov Decision ProcessesArticle

Authors: Jan Křetínský ; Tobias Meggendorfer ORCID

    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.


    Volume: Volume 16, Issue 4
    Published on: October 9, 2020
    Accepted on: September 13, 2020
    Submitted on: December 16, 2019
    Keywords: Electrical Engineering and Systems Science - Systems and Control,Computer Science - Artificial Intelligence,Computer Science - Logic in Computer Science

    1 Document citing this article

    Consultation statistics

    This page has been seen 1549 times.
    This article's PDF has been downloaded 422 times.