Computationally Efficient Algorithms for Markov Decision Processes

该奖项的研究目标是开发计算效率高的算法来解决某些类别的马尔可夫决策过程（MDP）。 MDP，也称为随机动态规划，为随机系统的动态优化提供了主要的运筹学方法和工具。它们广泛用于生产、服务、电信和军事系统的优化。除了运筹学之外，MDP还用于许多其他学科，包括电气工程，计算机科学和经济学。 该项目将调查两个最常用的客观标准的问题：每单位时间的平均成本和预期的总折扣成本以及风险敏感标准。 除了一个单一的目标标准的问题，它将调查多个标准和约束的问题。 将研究相对于MDP的参数和相对于初始问题配方的参数的计算效率。 如果成功的话，这项研究的结果将提供新的方法和计算机算法，找到精确和近似的解决方案MDP建模应用到生产和服务系统。 这些应用程序包括库存和库存控制，调度和资源分配。该项目还将有助于科学和工程领域人力资源的开发。首先，它将支持博士学位。学生在斯托尼布鲁克大学进行研究有关这个项目。第二，它将为研究生和本科生，包括理工科的少数民族学生和女生，创建研究和教育项目。 该项目的成果将用于PI教授的应用概率和动态规划课程。 该项目的结果将通过期刊出版物，互联网传播，并纳入PI目前正在编写的文本“马尔可夫决策过程介绍”。

The research objective of this award is to develop computationally efficient algorithms for solving certain classes of Markov Decision Processes (MDPs). MDPs, also known under the name of stochastic dynamic programming, provide major operations research methods and tools for dynamic optimization of stochastic systems. They are broadly used for the optimization of production, service, telecommunication, and military systems. In addition to operations research, MDPs are used in many other disciplines including electrical engineering, computer science, and economics. The project will investigate the problems with the two most often used objective criteria: average costs per unit of time and the expected total discounted costs as well as risk sensitive criteria. In addition to problems with a single objective criterion, it will investigate problems with multiple criteria and constraints. The computational efficiency will be studied with respect to the parameters of an MDP and with respect to the parameters of the initial problem formulation. If successful, the results of this research will provide new methodologies and computer algorithms for finding exact and approximate solutions to MDPs modeling applications to production and service systems. These applications include inventory and queueing control, scheduling, and resource allocation. This project will also contribute to the development of human resources in science and engineering. First, it will support Ph.D. students at the Stony Brook University to conduct research related to this project. Second, it will create research and educational projects for graduate and undergraduate students including minority and female students in science and engineering. The results of this project will be used in applied probability and dynamic programming courses that the PI teaches. The results of this project will be disseminated via journal publications, the internet, and included into the text "Introduction to Markov Decision Processes" the PI is currently working on.