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.