New Computational Approaches for Markov Decision Processes

马尔可夫决策过程的新计算方法

• 批准号: 0323220
• 负责人: Michael Fu
• 金额: --
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-01-01 至 2008-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0323220&HistoricalAwards=false
• 关键词: New; Computational; Approaches; Markov; Decision

Developing practical computational solution methods for large-scale Markov Decision Processes (MDPs), also known as stochastic dynamic programming problems, remains an important and challenging research area. The complexity of many modern systems that can in principle be modeled using MDPs have resulted in models for which it is not possible to explicitly enumerate the transition probabilities, but for which sample paths can be easily generated, e.g., via a stochastic simulation model. The project research addresses two other distinct but crucial issues that arise: how best to allocate a computational budget that is used to generate sample paths, and how to produce a robust set of good policies directly (rather than indirectly via value function approximations). In particular, the main thrusts of our proposed approaches center on two distinct paradigms: effective sampling-based methodologies using multi-armed bandit models and induced correlation for value function estimation; and population-based approaches for finding improving policies, in contrast to the traditional policy iteration method, which iterates on a single policy. The latter thrust will focus on infinite horizon problems, where there is assumed an optimal stationary policy, whereas the former approaches are intended for finite horizon problems, where backwards induction dynamic programming must be employed. Algorithms will be developed and then analyzed in terms of their properties such as convergence rate and theoretical bounds on performance, followed by testing on specific application areas to investigate their practical utility. Specific problem domains include the pricing of American-style financial derivatives; capacity planning and preventive maintenance in manufacturing systems; and communication networks.

开发用于大规模马尔可夫决策过程（MDP）（也称为随机动态编程问题）的实用计算解决方案方法仍然是一个重要且具有挑战性的研究领域。 原则上可以使用MDP建模的许多现代系统的复杂性导致模型无法明确列举过渡概率，但是可以轻松地通过随机模拟模型来轻松地生成样品路径。 该项目研究解决了出现的另外两个不同但至关重要的问题：如何最好地分配用于生成样本路径的计算预算，以及如何直接直接产生一组强大的良好策略（而不是通过价值函数近似值间接）。 特别是，我们提出的方法的主要推力以两个不同的范式为中心：使用多军匪徒模型的有效采样方法，并诱导相关性，以进行价值函数估计；与传统的政策迭代方法相比，基于人群的方法来寻找改进政策，该方法在单一政策上进行了迭代。 后者的推力将集中在无限的地平线问题上，如果假定具有最佳的固定政策，而前者的方法则用于有限的地平线问题，必须采用向后感应动态编程。 将开发算法，然后根据其属性（例如收敛率和性能的理论界限）进行分析，然后对特定的应用领域进行测试以研究其实际效用。 特定的问题领域包括美国风格的金融衍生品的定价；制造系统中的容量计划和预防性维护；和通信网络。