Singularly Perturbed Markov Decision Processes: A Multiresolution Algorithm
Singularly Perturbed Markov Decision Processes: A Multiresolution Algorithm
复制标题
奇异扰动马尔可夫决策过程：一种多分辨率算法
DOI：
10.1137/130944254
复制
发表时间：
2014
影响因子：
2.2
通讯作者：
Ho C
中科院分区：
文献类型：
--
作者：
Ho C
奇异扰动技术允许导出聚合模型，其解对于具有强相互作用和弱相互作用的马尔可夫决策过程是渐近最优的。我们开发了一种算法，利用聚合模型的渐近最优性来计算原始模型的解。我们推导了所提出的算法比传统收缩算法具有更好的最坏情况复杂度的条件。根据我们的复杂性分析，我们表明聚合的主要好处是降阶模型不再是病态的。状态数量的减少（由于聚合）是次要的好处。这是一个令人惊讶的结果，因为直觉表明降阶模型可以更有效地求解，因为它具有更少的状态。然而，我们表明情况并非一定如此。我们的理论分析和数值实验表明，所提出的算法可以计算最优解，同时降低计算复杂度，并且不会影响准确性。
Singular perturbation techniques allow the derivation of an aggregate model whose solution is asymptotically optimal for Markov decision processes with strong and weak interactions. We develop an algorithm that takes advantage of the asymptotic optimality of the aggregate model in order to compute the solution of the original model. We derive conditions for which the proposed algorithm has better worst case complexity than conventional contraction algorithms. Based on our complexity analysis, we show that the major benefit of aggregation is that the reduced order model is no longer ill conditioned. The reduction in the number of states (due to aggregation) is a secondary benefit. This is a surprising result since intuition would suggest that the reduced order model can be solved more efficiently because it has fewer states. However, we show that this is not necessarily the case. Our theoretical analysis and numerical experiments show that the proposed algorithm can compute the optimal solution with a reduction in computational complexity and without any penalty in accuracy.
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
O. Alvarez;M. Bardi;Claudio Marchi;P. Bucci
通讯作者：
P. Bucci
《1985年教育部遗传性代谢病专项研究委员会报告》（1986）
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--
使用马尔可夫状态模型优化分子动力学控制
影响因子：
2.7
作者：
C. Schütte;S. Winkelmann;C. Hartmann
通讯作者：
C. Hartmann