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

KŘETÍNSKÝ, Jan a Tobias MEGGENDORFER. Of Cores: A Partial-Exploration Framework for Markov Decision Processes. Logical Methods in Computer Science. Technical University of Braunschweig, 2020, roč. 16, č. 4, s. 1-31. ISSN 1860-5974.

Základní údaje

Originální název

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

Autoři

KŘETÍNSKÝ, Jan a Tobias MEGGENDORFER

Vydání

Logical Methods in Computer Science, Technical University of Braunschweig, 2020, 1860-5974

---

Další údaje

Typ výsledku

Článek v odborném periodiku

Odkazy

URL

Impakt faktor

Impact factor: 0.438

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

---

Anotace

V originále

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.