文章基本信息

标题：Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes
本地全文：下载
作者：Křetínský, Jan ; Křetínská, Zuzana ; Chatterjee, Krishnendu 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2017
卷号：13
期号：2
语种：English
出版社：Technical University of Braunschweig
摘要：We consider Markov decision processes (MDPs) with multiple limit-average (ormean-payoff) objectives. There exist two different views: (i) the expectationsemantics, where the goal is to optimize the expected mean-payoff objective,and (ii) the satisfaction semantics, where the goal is to maximize theprobability of runs such that the mean-payoff value stays above a given vector.We consider optimization with respect to both objectives at once, thus unifyingthe existing semantics. Precisely, the goal is to optimize the expectationwhile ensuring the satisfaction constraint. Our problem captures the notion ofoptimization with respect to strategies that are risk-averse (i.e., ensurecertain probabilistic guarantee). Our main results are as follows: First, wepresent algorithms for the decision problems which are always polynomial in thesize of the MDP. We also show that an approximation of the Pareto-curve can becomputed in time polynomial in the size of the MDP, and the approximationfactor, but exponential in the number of dimensions. Second, we present acomplete characterization of the strategy complexity (in terms of memory boundsand randomization) required to solve our problem.
关键词：Computer Science - Logic in Computer Science