Computationally Efficient Algorithms for Markov Decision Processes

该奖项的研究目标是开发计算效率高的算法来求解某些类型的马尔可夫决策过程(MDP)。MDPS，也称为随机动态规划，为随机系统的动态优化提供了主要的运筹学方法和工具。它们广泛用于生产、服务、电信和军事系统的优化。除了运筹学之外，MDP还被用于许多其他学科，包括电气工程、计算机科学和经济学。该项目将用两个最常用的客观标准来调查问题：单位时间的平均成本和预期的总贴现成本，以及风险敏感标准。除了具有单一客观标准的问题外，它还将调查具有多个标准和约束的问题。将针对MDP的参数和相对于初始问题公式的参数来研究计算效率。如果成功，这项研究的结果将提供新的方法和计算机算法，为MDP建模应用到生产和服务系统找到准确和近似的解决方案。这些应用包括库存和排队控制、调度和资源分配。该项目还将有助于开发科学和工程领域的人力资源。首先，它将支持石溪大学的博士生开展与该项目相关的研究。其次，它将为研究生和本科生创建研究和教育项目，包括理工科少数民族和女性学生。这个项目的成果将用于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.