Unifying Two Views on Multiple Mean-Payoff Objectives in Markov
Decision Processes

D 2015

Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes

CHATTERJEE, Krishnendu, Zuzana KOMÁRKOVÁ a Jan KŘETÍNSKÝ

Základní údaje

Originální název

Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes

Autoři

CHATTERJEE, Krishnendu (356 Indie), Zuzana KOMÁRKOVÁ (203 Česká republika, domácí) a Jan KŘETÍNSKÝ (203 Česká republika, garant, domácí)

Vydání

Los Alamitos, California, Thirtieth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), od s. 244-256, 13 s. 2015

Nakladatel

IEEE

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

tištěná verze "print"

Kód RIV

RIV/00216224:14330/15:00080917

Organizační jednotka

Fakulta informatiky

ISBN

978-1-4799-8875-4

ISSN

DOI

http://dx.doi.org/10.1109/LICS.2015.32

UT WoS

000380427100024

Klíčová slova anglicky

Markov decision process; mean payoff; optimization; probability

Štítky

core_A, firank_1, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 23. 10. 2017 12:46, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist two different views: (i)~the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii)~the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. We consider optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems, which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Second, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.

Návaznosti

GBP202/12/G061, projekt VaV

Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)

Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky

Citovat

CHATTERJEE, Krishnendu, Zuzana KOMÁRKOVÁ a Jan KŘETÍNSKÝ. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. In Thirtieth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). Los Alamitos, California: IEEE, 2015, s. 244-256. ISBN 978-1-4799-8875-4. Dostupné z: https://dx.doi.org/10.1109/LICS.2015.32.

@inproceedings{1306804,
   author = {Chatterjee, Krishnendu and Komárková, Zuzana and Křetínský, Jan},
   address = {Los Alamitos, California},
   booktitle = {Thirtieth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)},
   doi = {http://dx.doi.org/10.1109/LICS.2015.32},
   keywords = {Markov decision process; mean payoff; optimization; probability},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Los Alamitos, California},
   isbn = {978-1-4799-8875-4},
   pages = {244-256},
   publisher = {IEEE},
   title = {Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes},
   year = {2015}
}

TY  - JOUR
ID  - 1306804
AU  - Chatterjee, Krishnendu - Komárková, Zuzana - Křetínský, Jan
PY  - 2015
TI  - Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes
PB  - IEEE
CY  - Los Alamitos, California
SN  - 9781479988754
KW  - Markov decision process
KW  - mean payoff
KW  - optimization
KW  - probability
N2  - We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist two different views: (i)~the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii)~the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. We consider optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems, which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Second, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem.
ER  -

CHATTERJEE, Krishnendu, Zuzana KOMÁRKOVÁ a Jan KŘETÍNSKÝ. Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. In \textit{Thirtieth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)}. Los Alamitos, California: IEEE, 2015, s.~244-256. ISBN~978-1-4799-8875-4. Dostupné z: https://dx.doi.org/10.1109/LICS.2015.32.

Podrobný výpis o publikaci