Robust Markov Decision Processes: Beyond Rectangularity
Robust Markov Decision Processes: Beyond Rectangularity
复制标题
鲁棒马尔可夫决策过程：超越矩形
DOI：
--
复制
发表时间：
2022
影响因子：
1.7
通讯作者：
Julien Grand
中科院分区：
文献类型：
--
作者：
Vineet Goyal;Julien Grand
我们考虑一种稳健的方法来解决马尔可夫决策过程（MDP）中模型参数的不确定性，该过程被广泛用于许多应用中的动态优化建模。大多数先前的工作考虑的情况是，与不同状态相关的转换的不确定性是解耦的，并且允许对手为与其他状态无关的每个状态选择最坏的可能实现，这可能导致高度保守的解决方案。另一方面，众所周知，一般不确定性集的情况很棘手。我们考虑概率转移的因子模型，其中转移概率是不确定的因子矩阵的线性函数，属于因子矩阵不确定性集。这是一个相当通用的概率转换不确定性模型，允许决策者对不同状态之间的概率转换之间的依赖关系进行建模，并且它比以前的方法明显不那么保守。我们证明，在基本的矩形假设下，我们可以在因子矩阵不确定性模型下有效地计算最优鲁棒策略。此外，我们表明存在一个确定性的最优鲁棒策略，从可解释性的角度来看，这是有意义的。我们还介绍了经典 MDP 的重要结构结果的稳健对应物，包括最大原理和布莱克韦尔最优性，并且我们提供了计算研究来证明我们的方法在减轻稳健政策保守性方面的有效性。
We consider a robust approach to address uncertainty in model parameters in Markov decision processes (MDPs), which are widely used to model dynamic optimization in many applications. Most prior works consider the case in which the uncertainty on transitions related to different states is uncoupled and the adversary is allowed to select the worst possible realization for each state unrelated to others, potentially leading to highly conservative solutions. On the other hand, the case of general uncertainty sets is known to be intractable. We consider a factor model for probability transitions in which the transition probability is a linear function of a factor matrix that is uncertain and belongs to a factor matrix uncertainty set. This is a fairly general model of uncertainty in probability transitions, allowing the decision maker to model dependence between probability transitions across different states, and it is significantly less conservative than prior approaches. We show that under an underlying rectangularity assumption, we can efficiently compute an optimal robust policy under the factor matrix uncertainty model. Furthermore, we show that there is an optimal robust policy that is deterministic, which is of interest from an interpretability standpoint. We also introduce the robust counterpart of important structural results of classical MDPs, including the maximum principle and Blackwell optimality, and we provide a computational study to demonstrate the effectiveness of our approach in mitigating the conservativeness of robust policies.