D 2019

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

KŘETÍNSKÝ, Jan a Tobias MEGGENDORFER

Základní údaje

Originální název

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

Autoři

KŘETÍNSKÝ, Jan (203 Česká republika, garant, domácí) a Tobias MEGGENDORFER (276 Německo)

Vydání

Dagstuhl, 30th International Conference on Concurrency Theory (CONCUR 2019), od s. 1-17, 17 s. 2019

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/19:00108293

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-121-4

ISSN

DOI

Klíčová slova anglicky

Partial Exploration; Markov Decision Processes; Verification

Štítky

Změněno: 27. 4. 2020 23:16, RNDr. Pavel Šmerk, Ph.D.

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.

Návaznosti

GA18-11193S, projekt VaV
Název: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy
Investor: Grantová agentura ČR, Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy