PAC statistical model checking of mean payoff in discrete- and continuous-time MDP

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

PAC statistical model checking of mean payoff in discrete- and continuous-time MDP

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

PAC statistical model checking of mean payoff in discrete- and continuous-time MDP

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Rok uplatnění

2025

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 periodika

Springer

ISSN

0925-9856

e-ISSN

1572-8102

Svazek periodika

66

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

43

Strana od-do

195-237

Kód UT WoS článku

001291928000001

EID výsledku v databázi Scopus

2-s2.0-85201395144