---
res:
bibo_abstract:
- '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. @eng'
bibo_authorlist:
- 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: Zuzana
foaf_name: Křetínská, Zuzana
foaf_surname: Křetínská
- foaf_Person:
foaf_givenName: Jan
foaf_name: Kretinsky, Jan
foaf_surname: Kretinsky
foaf_workInfoHomepage: http://www.librecat.org/personId=44CEF464-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-8122-2881
bibo_doi: 10.23638/LMCS-13(2:15)2017
bibo_issue: '2'
bibo_volume: 13
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/18605974
dct_language: eng
dct_publisher: International Federation of Computational Logic@
dct_title: Unifying two views on multiple mean-payoff objectives in Markov decision
processes@
...