New Simulation-Based Approaches to Solving Markov Decision Processes

解决马尔可夫决策过程的基于仿真的新方法

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

The research to be performed will develop simulation-based algorithms for numerical solution of Markov Decision Processes (MDPs), which can be used to model complex systems in manufacturing, telecommunications, and finance. Two new approaches that offer potential benefits not found in currently available methods will be explored. The first approach will use ordinal optimization (OO) for choosing actions in the backwards induction step for finite horizon problems, or in the policy iteration or value iteration step for infinite horizon problems. The second approach will use simultaneous perturbation stochastic approximation (SPSA) for optimizing high-dimensional parameterized MDPs.If successful, the results of the research will lead to dramatically more efficient algorithms for solving MDPs of practical interest in a number of application areas, from financial engineering to production systems. The impact of successfully applying high-dimensional solution methodologies to these problems would represent a major advance in developing computationally tractable methods for solving complex problems of sequential decision making under uncertainty. Furthermore, theoretical results are envisioned that would rigorously establish faster rates of convergence for the new algorithms over convergence rates from usual Monte Carlo simulation.

研究将开发基于模拟的算法，用于马尔可夫决策过程（MDP）的数值解，可用于模拟制造，电信和金融领域的复杂系统。 将探讨两种新的方法，这些方法提供了现有方法所没有的潜在好处。 第一种方法将使用顺序优化（OO）选择有限时间问题的向后归纳步骤中的动作，或在无限时间问题的策略迭代或值迭代步骤中的动作。 第二种方法将使用同步扰动随机逼近（SPSA）优化高维参数化MDP，如果成功的话，研究的结果将导致显着更有效的算法，解决MDP的实际利益在一些应用领域，从金融工程到生产系统。 成功地应用高维的解决方案的方法，这些问题的影响将代表一个重大的进步，在发展计算上易于处理的方法来解决复杂的问题，顺序决策的不确定性。 此外，理论结果设想，将严格建立更快的收敛速度的新算法的收敛速度从通常的蒙特卡罗模拟。