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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00108293" target="_blank" >RIV/00216224:14330/19:00108293 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.4230/LIPIcs.CONCUR.2019.5" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.CONCUR.2019.5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.CONCUR.2019.5" target="_blank" >10.4230/LIPIcs.CONCUR.2019.5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA18-11193S" target="_blank" >GA18-11193S: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

30th International Conference on Concurrency Theory (CONCUR 2019)

ISBN

9783959771214

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

17

Strana od-do

1-17

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl

Místo konání akce

Dagstuhl

Datum konání akce

1. 1. 2019

Typ akce podle státní příslušnosti

CST - Celostátní akce

Kód UT WoS článku

—