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建模，导致模型不可能明确地枚举转移概率，但样本路径可以很容易地生成，例如，通过随机模拟模型。该项目研究解决了另外两个截然不同但至关重要的问题：如何最好地分配用于生成样本路径的计算预算，以及如何直接（而不是通过值函数近似间接）生成一组健壮的良好策略。特别是，我们提出的方法的主要重点集中在两个不同的范式上：有效的基于抽样的方法，使用多臂强盗模型和价值函数估计的诱导相关性；以及基于人口的方法来寻找改进的政策，与传统的政策迭代方法相反，传统的政策迭代方法是在单个政策上迭代。后一种方法将集中于无限视界问题，其中存在假设的最优平稳策略，而前一种方法旨在解决有限视界问题，其中必须采用向后归纳动态规划。将开发算法，然后根据其特性（如收敛速度和性能的理论界限）进行分析，然后在特定应用领域进行测试，以调查其实际效用。具体的问题领域包括美式金融衍生品的定价；生产系统的产能规划和预防性维护；还有通讯网络。