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

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GA18-11193S" target="_blank" >GA18-11193S: Algorithms for Infinite-State Discrete Systems and Games</a><br>

Continuities

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

Publication year

2019

Confidentiality

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

Article name in the collection

30th International Conference on Concurrency Theory (CONCUR 2019)

ISBN

9783959771214

ISSN

1868-8969

e-ISSN

—

Number of pages

17

Pages from-to

1-17

Publisher name

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Place of publication

Dagstuhl

Event location

Dagstuhl

Event date

Jan 1, 2019

Type of event by nationality

CST - Celostátní akce

UT code for WoS article

—