Two views on multiple mean payoff objectives in Markov Decision Processes
Brázdil, Tomáš
Brožek, Václav
Chatterjee, Krishnendu
Forejt, Vojtěch
Kučera, Antonín
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.
IEEE
2011
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://research-explorer.app.ist.ac.at/record/3346
Brázdil T, Brožek V, Chatterjee K, Forejt V, Kučera A. Two views on multiple mean payoff objectives in Markov Decision Processes. In: IEEE; 2011. doi:<a href="https://doi.org/10.1109/LICS.2011.10">10.1109/LICS.2011.10</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1109/LICS.2011.10
info:eu-repo/grantAgreement/FWF//P 23499-N23
info:eu-repo/grantAgreement/FWF//S 11407_N23
info:eu-repo/grantAgreement/EC/FP7/279307
info:eu-repo/semantics/openAccess