New Algorithms for Markov Decision Processes and Reinforcement Learning

马尔可夫决策过程和强化学习最近在应用方面取得了巨大成功，从在雅达利游戏中表现优于人类，到AlphaFold在预测蛋白质折叠方面盖过了竞争对手的方法。这一成功是几个基本发展的结果，包括深度神经网络为表示高维函数提供了强大的机制，图形处理单元和张量处理单元提供了前所未有的计算能力，以及用于预测和控制的新算法的开发。然而，在将这些最新技术应用于卫生、社会和经济规划以及国防方面的关键任务应用程序方面，仍然存在许多挑战。这个项目旨在开发和分析马尔可夫决策过程和强化学习的新算法，目的是使这些方法更广泛地适用。教育影响包括博士后和研究生培训，以及以机器学习为中心的本科课程发展。这个项目涉及到基于线性规划的马尔可夫决策过程的统一框架的开发，其中研究了正则化和非正则化情况下的原始、对偶和原始-对偶问题。然后，基于马尔可夫决策过程的现有算法将连接到这个统一的框架。对于表格设置，将开发一种适用于一般熵正则化的拟牛顿型策略梯度算法。对于原始-对偶问题，提出了一种基于非标准预条件度量的严格凸化形式的快速收敛的梯度上升下降算法。非线性近似设置将通过变分行动者-批评者算法来处理，该算法是稳定的，并且至少收敛到局部最小值。最后，为了解决双重抽样问题，将开发基于向未来借款的思想的新算法，以显著减少偏差。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Markov decision processes and reinforcement learning have had significant recent success in applications, ranging from outperforming humans in Atari games to AlphaFold overshadowing competing methods in predicting protein folding. This success results from several fundamental developments, including deep neural networks providing a powerful mechanism for representing high dimensional functions, unprecedented computing power provided by graphical processing units and tensor processing units, and the development of novel algorithms for both prediction and control. However, there are still many challenges in applying these recent techniques to mission-critical applications in health, social and economic planning, and defense. This project aims to develop and analyze novel algorithms for Markov decision processes and reinforcement learning with the intention of making these approaches more broadly applicable. Educational impacts include postdoctoral and graduate student training, as well as undergraduate course development centered around machine learning. This project involves the development of a unified framework for Markov decision processes based on linear programming, where the primal, dual, and primal-dual problems are studied for both the regularized and non-regularized cases. Existing algorithms based on Markov decision processes will then be connected to this unified framework. For the tabular setting, a quasi-Newton type policy gradient algorithm will be developed for general entropic regularizers. For the primal-dual problem, a rapidly converging gradient ascent descent algorithm based on a strictly convexified formulation with a non-standard preconditioning metric will be developed. The nonlinear approximation setting will be addressed by variational actor-critic algorithms that are stable and converge at least to a local minimum. Finally, to address the double sampling issue, new algorithms based on the borrowing-from-the-future idea will be developed to significantly reduce the bias.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.