PAC statistical model checking of mean payoff in discrete- and continuous-time MDP
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F25%3A00142466" target="_blank" >RIV/00216224:14330/25:00142466 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/article/10.1007/s10703-024-00463-0#ethics" target="_blank" >https://link.springer.com/article/10.1007/s10703-024-00463-0#ethics</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s10703-024-00463-0" target="_blank" >10.1007/s10703-024-00463-0</a>
Alternative languages
Result language
angličtina
Original language name
PAC statistical model checking of mean payoff in discrete- and continuous-time MDP
Original language description
Markov decision processes (MDPs) and continuous-time MDP (CTMDPs) are the fundamental models for non-deterministic systems with probabilistic uncertainty. Mean payoff (a.k.a. long-run average reward) is one of the most classic objectives considered in their context. We provide the first practical algorithm to compute mean payoff probably approximately correctly in unknown MDPs. Our algorithm is anytime in the sense that if terminated prematurely, it returns an approximate value with the required confidence. Further, we extend it to unknown CTMDPs. We do not require any knowledge of the state or number of successors of a state, but only a lower bound on the minimum transition probability, which has been advocated in literature. Our algorithm learns the unknown MDP/CTMDP through repeated, directed sampling; thus spending less time on learning components with smaller impact on the mean payoff. In addition to providing probably approximately correct (PAC) bounds for our algorithm, we also demonstrate its practical nature by running experiments on standard benchmarks.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10200 - Computer and information sciences
Result continuities
Project
—
Continuities
V - Vyzkumna aktivita podporovana z jinych verejnych zdroju
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Springer
ISSN
0925-9856
e-ISSN
1572-8102
Volume of the periodical
66
Issue of the periodical within the volume
2
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
43
Pages from-to
195-237
UT code for WoS article
001291928000001
EID of the result in the Scopus database
2-s2.0-85201395144