Home > Research > Publications & Outputs > Of Cores: A Partial-Exploration Framework for M...

Research

Links

Text available via DOI:

Keywords

View graph of relations

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

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Published

Standard

Of Cores: A Partial-Exploration Framework for Markov Decision Processes. / Kretínský, Jan; Meggendorfer, Tobias.
30th International Conference on Concurrency Theory, CONCUR 2019. ed. / Wan Fokkink; Rob van Glabbeek. 2019. p. 1-17 5 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 140).

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review

Harvard

Kretínský, J & Meggendorfer, T 2019, Of Cores: A Partial-Exploration Framework for Markov Decision Processes. in W Fokkink & R van Glabbeek (eds), 30th International Conference on Concurrency Theory, CONCUR 2019., 5, Leibniz International Proceedings in Informatics, LIPIcs, vol. 140, pp. 1-17. https://doi.org/10.4230/LIPIcs.CONCUR.2019.5

APA

Kretínský, J., & Meggendorfer, T. (2019). Of Cores: A Partial-Exploration Framework for Markov Decision Processes. In W. Fokkink, & R. van Glabbeek (Eds.), 30th International Conference on Concurrency Theory, CONCUR 2019 (pp. 1-17). Article 5 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 140). https://doi.org/10.4230/LIPIcs.CONCUR.2019.5

Vancouver

Kretínský J, Meggendorfer T. Of Cores: A Partial-Exploration Framework for Markov Decision Processes. In Fokkink W, van Glabbeek R, editors, 30th International Conference on Concurrency Theory, CONCUR 2019. 2019. p. 1-17. 5. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.CONCUR.2019.5

Author

Kretínský, Jan ; Meggendorfer, Tobias. / Of Cores: A Partial-Exploration Framework for Markov Decision Processes. 30th International Conference on Concurrency Theory, CONCUR 2019. editor / Wan Fokkink ; Rob van Glabbeek. 2019. pp. 1-17 (Leibniz International Proceedings in Informatics, LIPIcs).

Bibtex

@inproceedings{6084d426d41849a28bcb925a2ebcdc2a,
title = "Of Cores: A Partial-Exploration Framework for Markov Decision Processes.",
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.",
keywords = "Approximation, Markov decision processes, Reachability",
author = "Jan Kret{\'i}nsk{\'y} and Tobias Meggendorfer",
note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",
year = "2019",
month = aug,
day = "1",
doi = "10.4230/LIPIcs.CONCUR.2019.5",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
pages = "1--17",
editor = "Wan Fokkink and {van Glabbeek}, Rob",
booktitle = "30th International Conference on Concurrency Theory, CONCUR 2019",

}

RIS

TY - GEN

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

AU - Kretínský, Jan

AU - Meggendorfer, Tobias

N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2019/8/1

Y1 - 2019/8/1

N2 - 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.

AB - 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.

KW - Approximation

KW - Markov decision processes

KW - Reachability

U2 - 10.4230/LIPIcs.CONCUR.2019.5

DO - 10.4230/LIPIcs.CONCUR.2019.5

M3 - Conference contribution/Paper

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 17

BT - 30th International Conference on Concurrency Theory, CONCUR 2019

A2 - Fokkink, Wan

A2 - van Glabbeek, Rob

ER -