On Finding Compromise Solutions in Multiobjective Markov Decision Processes
On Finding Compromise Solutions in Multiobjective Markov Decision Processes
复制标题
多目标马尔可夫决策过程中寻找折衷解
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Paul Weng
中科院分区：
文献类型：
--
作者：
P. Perny;Paul Weng
马尔可夫决策过程(MDP)是解决不确定条件下规划问题的一般模型。它已经扩展到多目标MDP，以解决多准则或多主体问题，在这些问题中，决策的价值必须根据几个观点来评估，有时甚至相互冲突。虽然大多数研究集中于确定帕累托最优政策集，但这里我们关注的是一个更专门的问题，它涉及实现良好平衡的政策的直接确定。我们首先解释为什么这个问题不能简单地通过优化标准的线性组合来解决。这导致我们使用另一种最优概念，它形式化了最佳折衷解的概念，即产生尽可能接近的预期效用向量的策略(W.r.t.切比雪夫范数)到参考点。我们证明了这一最优性概念依赖于初始状态。此外，似乎不能通过直接调整价值迭代来找到最佳折衷策略。此外，我们观察到，在某些情况下(如果不是大多数情况下)，只有在随机策略下才能获得最优解。为了克服这些问题，我们提出了一种基于线性规划的求解方法，并给出了一些实验结果。
A Markov Decision Process (MDP) is a general model for solving planning problems under uncertainty. It has been extended to multiobjective MDP to address multicriteria or multiagent problems in which the value of a decision must be evaluated according to several viewpoints, sometimes conflicting. Although most of the studies concentrate on the determination of the set of Pareto-optimal policies, we focus here on a more specialized problem that concerns the direct determination of policies achieving well-balanced tradeoffs. We first explain why this problem cannot simply be solved by optimizing a linear combination of criteria. This leads us to use an alternative optimality concept which formalizes the notion of best compromise solution, i.e. a policy yielding an expected-utility vector as close as possible (w.r.t. Tchebycheff norm) to a reference point. We show that this notion of optimality depends on the initial state. Moreover, it appears that the best compromise policy cannot be found by a direct adaptation of value iteration. In addition, we observe that in some (if not most) situations, the optimal solution can only be obtained with a randomized policy. To overcome all these problems, we propose a solution method based on linear programming and give some experimental results.