Of cores: A partial-exploration framework for Markov decision processes

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

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. We obtain efficient analysis algorithms based on partial exploration for various settings, including the challenging case of strongly connected systems.

Original languageEnglish
Pages (from-to)3:1-3:31
JournalLogical Methods in Computer Science
Volume16
Issue number4
DOIs
StatePublished - 2020

Fingerprint

Dive into the research topics of 'Of cores: A partial-exploration framework for Markov decision processes'. Together they form a unique fingerprint.

Cite this