---
res:
bibo_abstract:
- 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 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 single-objective case, both randomization and memory are necessary
for strategies, and that finite-memory randomized strategies are sufficient. Under
the satisfaction objective, in contrast to the single-objective case, infinite
memory is necessary for strategies, and that randomized memoryless strategies
are sufficient for epsilon-approximation, for all epsilon>;0. We further prove
that the decision problems for both expectation and satisfaction objectives can
be solved in polynomial time and the trade-off curve (Pareto curve) can be epsilon-approximated
in time polynomial in the size of the MDP and 1/epsilon, and exponential in the
number of reward functions, for all epsilon>;0. Our results also reveal flaws
in previous work for MDPs with multiple mean-payoff functions under the expectation
objective, correct the flaws and obtain improved results.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Tomáš
foaf_name: Brázdil, Tomáš
foaf_surname: Brázdil
- foaf_Person:
foaf_givenName: Václav
foaf_name: Brožek, Václav
foaf_surname: Brožek
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Vojtěch
foaf_name: Forejt, Vojtěch
foaf_surname: Forejt
- foaf_Person:
foaf_givenName: Antonín
foaf_name: Kučera, Antonín
foaf_surname: Kučera
bibo_doi: 10.1109/LICS.2011.10
dct_date: 2011^xs_gYear
dct_language: eng
dct_publisher: IEEE@
dct_title: Two views on multiple mean payoff objectives in Markov Decision Processes@
...