Markov Decision Processes with Multiple Long-Run Average Objectives

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

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

Year of publication 2014
Type Article in Periodical
Magazine / Source Logical Methods in Computer Science
MU Faculty or unit

Faculty of Informatics

Citation
Web http://www.lmcs-online.org/
Doi http://dx.doi.org/10.2168/LMCS-10(1:13)2014
Field Informatics
Keywords Markov decision processes; mean-payoff reward; multi-objective optimisation; formal verification
Description 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 limit-average 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 case of one limit-average function, both randomization and memory are necessary for strategies even for epsilon-approximation, and that finite-memory randomized strategies are sufficient for achieving Pareto optimal values. Under the satisfaction objective, in contrast to the case of one limit-average function, infinite memory is necessary for strategies achieving a specific value (i.e. randomized finite-memory strategies are not sufficient), whereas memoryless randomized 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 limit-average functions, for all epsilon>0. Our analysis also reveals flaws in previous work for MDPs with multiple mean-payoff functions under the expectation objective, corrects the flaws, and allows us to obtain improved results.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.