Robust MDPs with k-Rectangular Uncertainty
Robust MDPs with k-Rectangular Uncertainty
复制标题
DOI：
10.1287/moor.2016.0786
复制
发表时间：
2016-09
期刊：
影响因子：
--
通讯作者：
Shie Mannor;O. Mebel;Huan Xu
中科院分区：
文献类型：
--
作者：
Shie Mannor;O. Mebel;Huan Xu
马尔可夫决策过程是不确定条件下序列规划问题建模的常用工具。在几乎所有的现实情况下，系统模型不可能完全已知，必须进行近似或估计。因此，我们考虑了参数不确定性下的马尔可夫决策过程，这有效地增加了第二层不确定性。以往的研究大多局限于不同状态之间的不确定性不耦合的情况，从而得到保守解。另一方面，已知具有一般耦合不确定性集的鲁棒mdp在计算上难以处理。在本文中，我们首次尝试识别耦合不确定性的子类，这些子类足够灵活，可以克服保守性，但仍然导致可处理的问题。我们提出了一类新的不确定性集，称为“k -矩形不确定性集”-一个由不确定性集的可能条件投影的基数定义的几何概念。所提出的方案可以对实践中自然产生的耦合不确定性的几种直观公式进行建模，并通过状态空间增广得到易于处理的公式。
Markov decision processes are a common tool for modeling sequential planning problems under uncertainty. In almost all realistic situations, the system model cannot be perfectly known and must be approximated or estimated. Thus, we consider Markov decision processes under parameter uncertainty, which effectively adds a second layer of uncertainty. Most previous studies restrict to the case that uncertainties among different states are uncoupled, which leads to conservative solutions. On the other hand, robust MDPs with general coupled uncertainty sets are known to be computationally intractable. In this paper we make a first attempt at identifying subclasses of coupled uncertainty that are flexible enough to overcome conservativeness yet still lead to tractable problems. We propose a new class of uncertainty sets termed “ k -rectangular uncertainty sets”—a geometric concept defined by the cardinality of possible conditional projections of the uncertainty set. The proposed scheme can model several intuitive formulations of coupled uncertainty that naturally arise in practice and leads to tractable formulations via state space augmentation.