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.