Markov Decision Processes with Multiple Long-Run Average Objectives

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

Result on the web

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

Result language

angličtina

Original language name

Markov Decision Processes with Multiple Long-Run Average Objectives

Original language description

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.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/GPP202%2F12%2FP612" target="_blank" >GPP202/12/P612: Formal Verification of Stochastic Real-Time Systems</a><br>

Continuities

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

Publication year

2014

Confidentiality

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

Name of the periodical

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

—

Volume of the periodical

10

Issue of the periodical within the volume

1

Country of publishing house

DE - GERMANY

Number of pages

29

Pages from-to

1-29

UT code for WoS article

000333744700001

EID of the result in the Scopus database

—