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

D 2011

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

BROŽEK, Václav, Tomáš BRÁZDIL, Krishnendu CHATTERJEE, Vojtěch FOREJT, Antonín KUČERA et. al.

Základní údaje

Originální název

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

Autoři

BROŽEK, Václav (203 Česká republika, domácí), Tomáš BRÁZDIL (203 Česká republika, domácí), Krishnendu CHATTERJEE (356 Indie), Vojtěch FOREJT (203 Česká republika, domácí) a Antonín KUČERA (203 Česká republika, garant, domácí)

Vydání

Los Alamitos, California, Proceedings 26th Annual IEEE Symposium on Logic in Computer Science, od s. 33-42, 10 s. 2011

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/11:00051963

Organizační jednotka

Fakulta informatiky

ISBN

978-0-7695-4412-0

DOI

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

UT WoS

000297350400006

Klíčová slova anglicky

Markov decision process; optimization with multiple objectives; mean payoff; Pareto curve; approximation

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 12. 4. 2013 01:40, RNDr. Vojtěch Forejt, Ph.D., LL.B. (Hons)

Anotace

ORIG CZ

V originále

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 reward functions, in the expectation objective the goal is to maximize the expected 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.

Česky

V článku jsou studovány Markovovy rozhodovací procesy s několika limit-average funkcemi. Uvažují se dva typy výherních podmínek a pro obě jsou podány základní výsledky o rozhodnutelnosti a složitosti příslušných rozhodovacích problémů.

Návaznosti

P202/10/1469, interní kód MU

Název: Formální metody pro analýzu a verifikaci komplexních systémů

1M0545, projekt VaV

Název: Institut Teoretické Informatiky

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky

Citovat

BROŽEK, Václav, Tomáš BRÁZDIL, Krishnendu CHATTERJEE, Vojtěch FOREJT a Antonín KUČERA. Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. In Martin Grohe. Proceedings 26th Annual IEEE Symposium on Logic in Computer Science. Los Alamitos, California: IEEE, 2011, s. 33-42. ISBN 978-0-7695-4412-0. Dostupné z: https://dx.doi.org/10.1109/LICS.2011.10.

@inproceedings{929376,
   author = {Brožek, Václav and Brázdil, Tomáš and Chatterjee, Krishnendu and Forejt, Vojtěch and Kučera, Antonín},
   address = {Los Alamitos, California},
   booktitle = {Proceedings 26th Annual IEEE Symposium on Logic in Computer Science},
   doi = {http://dx.doi.org/10.1109/LICS.2011.10},
   editor = {Martin Grohe},
   keywords = {Markov decision process; optimization with multiple objectives; mean payoff; Pareto curve; approximation},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Los Alamitos, California},
   isbn = {978-0-7695-4412-0},
   pages = {33-42},
   publisher = {IEEE},
   title = {Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes},
   year = {2011}
}

TY  - CONF
ID  - 929376
AU  - Brožek, Václav - Brázdil, Tomáš - Chatterjee, Krishnendu - Forejt, Vojtěch - Kučera, Antonín
PY  - 2011
TI  - Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes
PB  - IEEE
CY  - Los Alamitos, California
SN  - 9780769544120
KW  - Markov decision process
KW  - optimization with multiple objectives
KW  - mean payoff
KW  - Pareto curve
KW  - approximation
N2  - 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 reward functions, in the expectation objective the goal is to maximize the expected 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.
ER  -

BROŽEK, Václav, Tomáš BRÁZDIL, Krishnendu CHATTERJEE, Vojtěch FOREJT a Antonín KUČERA. Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes. In Martin Grohe. \textit{Proceedings 26th Annual IEEE Symposium on Logic in Computer Science}. Los Alamitos, California: IEEE, 2011, s.~33-42. ISBN~978-0-7695-4412-0. Dostupné z: https://dx.doi.org/10.1109/LICS.2011.10.

Přehled o publikaci