一句话：统一 MDP 中多均值收益目标的期望语义与满足语义，并给出多项式时间算法与策略复杂度刻画。
本文研究带多个 limit-average（均值收益）目标的马尔可夫决策过程（MDP）。已有两种视角：期望语义优化期望均值收益，满足语义最大化使均值收益向量保持在给定阈值之上的运行概率。作者同时考虑二者：在满足概率约束下优化期望，从而统一现有语义，并刻画风险规避策略。主要结果包括：判定问题算法在 MDP 规模上总是多项式时间；Pareto 曲线的近似可在 MDP 规模与近似因子的多项式时间内计算，但对维数呈指数；此外给出求解该问题所需策略复杂度的完整刻画，包括内存界与随机化需求。
We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff 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 risk-averse (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. Comment: Extended journal version of the LICS'15 paper
@article{paperbot152,
title = {Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes},
author = {Krishnendu Chatterjee and Zuzana Křetínská and Jan Křetínský},
journal = {Logical Methods in Computer Science},
volume = {Volume 13, Issue 2},
year = {2017},
doi = {10.23638/lmcs-13(2:15)2017}
}