MARKOV DECISION PROCESSES WITH MULTIPLE LONG-RUN AVERAGE OBJECTIVES
MARKOV DECISION PROCESSES WITH MULTIPLE LONG-RUN AVERAGE OBJECTIVES
复制标题
DOI：
10.2168/lmcs-10(1:13)2014
复制
发表时间：
2014-01-01
影响因子：
0.6
通讯作者：
Kucera, Antonin
中科院分区：
文献类型：
--
作者：
Brazdil, Tomas;Brozek, Vaclav;Kucera, Antonin
研究了具有多个极限平均（或平均支付）函数的马尔可夫决策过程。我们考虑两个不同的目标，即期望和满意度目标。给定具有Kappa极限平均函数的MDP，在期望目标中，目标是最大化期望的极限平均值，并且在满意度目标中，目标是最大化运行的概率，使得极限平均值保持在给定向量之上。我们表明，在期望目标下，与一个极限平均函数的情况相反，即使对于ε逼近，随机化和记忆对于策略也是必要的，并且有限记忆随机化策略足以实现帕累托最优值。在满意度目标下，与一个极限平均函数的情况相反，无限记忆对于实现特定值的策略是必要的（即随机有限记忆策略是不够的），而无记忆随机策略对于ε近似是足够的，对于所有ε> 0。我们进一步证明了期望和满意度目标的决策问题都可以在多项式时间内解决，并且对于所有ε> 0，权衡曲线（Pareto曲线）可以在MDP和1/ε的大小下在时间多项式中ε近似，并且在极限平均函数的数量上呈指数。我们的分析还揭示了缺陷，在以前的工作中的MDPs与多个均值支付函数的期望目标，纠正了缺陷，并使我们能够获得改进的结果。
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 kappa 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.