Markov Decision Processes with Multiple Long-Run Average Objectives

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F14%3A00074494" target="_blank" >RIV/00216224:14330/14:00074494 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.lmcs-online.org/ojs/viewarticle.php?id=1109&layout=abstract" target="_blank" >http://www.lmcs-online.org/ojs/viewarticle.php?id=1109&layout=abstract</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.2168/LMCS-10(1:13)2014" target="_blank" >10.2168/LMCS-10(1:13)2014</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Markov Decision Processes with Multiple Long-Run Average Objectives

Popis výsledku v původním jazyce

We study Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) functions. We consider two different objectives, namely, expectation and satisfaction objectives. Given an MDP with k limit-average functions, in the expectation objective the goal is to maximize the expected limit-average value, and in the satisfaction objective the goal is to maximize the probability of runs such that the limit-average value stays above a given vector. We show that under the expectation objective, in contrast to the case of one limit-average function, both randomization and memory are necessary for strategies even for epsilon-approximation, and that finite-memory randomized strategies are sufficient for achieving Pareto optimal values. Under the satisfaction objective, in contrast to the case of one limit-average function, infinite memory is necessary for strategies achieving a specific value (i.e.

Název v anglickém jazyce

Markov Decision Processes with Multiple Long-Run Average Objectives

Popis výsledku anglicky

We study Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) functions. We consider two different objectives, namely, expectation and satisfaction objectives. Given an MDP with k limit-average functions, in the expectation objective the goal is to maximize the expected limit-average value, and in the satisfaction objective the goal is to maximize the probability of runs such that the limit-average value stays above a given vector. We show that under the expectation objective, in contrast to the case of one limit-average function, both randomization and memory are necessary for strategies even for epsilon-approximation, and that finite-memory randomized strategies are sufficient for achieving Pareto optimal values. Under the satisfaction objective, in contrast to the case of one limit-average function, infinite memory is necessary for strategies achieving a specific value (i.e.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GPP202%2F12%2FP612" target="_blank" >GPP202/12/P612: Formální verifikace stochastických systémů s reálným časem</a><br>

Návaznosti

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

Rok uplatnění

2014

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

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

—

Svazek periodika

10

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

29

Strana od-do

1-29

Kód UT WoS článku

000333744700001

EID výsledku v databázi Scopus

—