Author(s):

Chatterjee, Krishnendu; Komárková, Zuzana; Křetínský, Jan

Title: 
Unifying two views on multiple meanpayoff objectives in Markov decision processes

Affiliation 
IST Austria 
Abstract: 
We consider Markov decision processes (MDPs) with multiple limitaverage (or meanpayoff) objectives. There exist two different views: (i) ~the expectation semantics, where the goal is to optimize the expected meanpayoff objective, and (ii) ~the satisfaction semantics, where the goal is to maximize the probability of runs such that the meanpayoff 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 riskaverse (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.

Keywords: 
Markov Decision Processes; mean payoff; Limit average reward

Conference Title:

LICS: Logic in Computer Science

Conference Dates:

July 610, 2015

Conference Location:

Kyoto, Japan

ISBN:

9781479988754

Publisher:

IEEE

Date Published:

20150701

Start Page: 
244

End Page:

256

DOI: 
10.1109/LICS.2015.32

Notes: 
This research was funded in part by Austrian Science Fund (FWF) Grant No P 23499N23, FWF NFN Grant No S11407N23 (RiSE) and Z211N23 (Wittgenstein Award), European Research Council (ERC) Grant No 279307 (Graph Games), ERC Grant No 267989 (QUAREM), the Czech Science Foundation Grant No P202/12/G061, and People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/20072013) REA Grant No 291734.
A Technical Report of this paper is available at: https://repository.ist.ac.at/327

Open access: 
yes (repository) 