Two views on multiple mean payoff objectives in Markov Decision Processes Conference Paper


Author(s): Brázdil, Tomáš; Brožek, Václav; Chatterjee, Krishnendu; Forejt, Vojtěch; Kučera, Antonín
Title: Two views on multiple mean payoff objectives in Markov Decision Processes
Affiliation IST Austria
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.
Conference Title: LICS: Logic in Computer Science
Conference Dates: July 21-24, 2011
Conference Location: Toronto, ON, Canada
ISBN: 978-147998875-4
Publisher: IEEE  
Date Published: 2011-06-21
Start Page: 33
End Page: 42
Sponsor: K. Chatterjee is supported by the Austrian Science Fund (FWF) Grant No P 23499-N23; FWF NFN Grant No S11407-N23 (RiSE); ERC Start grant (279307: Graph Games); Microsoft faculty fellows award.
URL:
DOI: 10.1109/LICS.2011.10
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work