New Simulation-Based Approaches to Solving Markov Decision Processes

将开展的研究将开发基于模拟的马尔可夫决策过程(MDP)数值解的算法，该算法可用于对制造业、电信和金融等领域的复杂系统进行建模。将探索两种新的方法，它们提供了目前可用的方法所没有的潜在好处。第一种方法将使用序数优化(OO)来选择有限水平问题的反向归纳步骤中的动作，或者无限水平问题的策略迭代或数值迭代步骤中的动作。第二种方法将使用同时摄动随机逼近(SPSA)方法来优化高维参数MDP。如果研究成功，研究结果将导致在从金融工程到生产系统的许多应用领域中更有效地求解MDP的算法。成功地将高维求解方法应用于这些问题的影响将代表着在开发易于计算的方法来解决不确定情况下的顺序决策的复杂问题方面的重大进步。此外，理论结果将严格建立新算法的收敛速度比通常的蒙特卡罗模拟的收敛速度快。

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.