AF: Small: A New Approach to Analysis and Design of Algorithms for Stochastic Control and Optimization

用于随机优化和控制的随机算法支撑着许多发展中的技术，如人工智能（AI）、自主机器人和大数据分析。由于缺乏合适的数学工具，它们的发展受到阻碍。在许多情况下，现有的数学技术，如基于随机李雅普诺夫理论的数学技术，使用起来相当困难，因此需要为每个问题的算法设计和分析发明定制技术。这个项目将开发一种新的数学技术，称为概率收缩分析，它更容易使用，更广泛适用。该项目的目标不仅仅是分析现有的算法，而是开发着眼于设计的分析工具。项目成果可以加速在人工智能、自治、大数据分析等许多重要应用领域出现的随机控制和优化问题的新算法的开发。该项目将培养代表性不足的女性博士生和博士后，以及高中生和教师。给定随机优化和控制的随机算法，该项目将每次迭代视为应用随机算子，并开发了由研究者创建的新的“概率收缩”分析技术，该技术使用随机优势参数来显示收敛到概率不动点。具体来说，研究者将开发经验启发的算法，用于连续状态和行动空间马尔可夫决策过程的最优控制，以及无约束和约束随机优化问题。所开发的技术可能对更广泛的随机迭代算法有用，并导致Banach空间上随机算子的概率不动点理论的发展。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Randomized algorithms for stochastic optimization and control underpin many developing technologies such as Artificial Intelligence (AI), Autonomous Robotics, and Big Data Analytics. Their development is hampered by a lack of suitable mathematical tools. In many cases, current mathematical techniques such as those based on Stochastic Lyapunov theory are rather difficult to use, thus necessitating invention of customized techniques for algorithm design for each problem and its analysis. This project will develop a new class of mathematical techniques, called probabilistic contraction analysis, that are easier to use, and more broadly applicable. The project's aim is not just analysis of existing algorithms, but development of analysis tools with an eye on design. The project outcomes can accelerate development of new algorithms for stochastic control and optimization problems that arise in many important application fields such as AI, Autonomy, Big Data Analytics, etc. The project will train under-represented and/or female PhD students and postdocs, as well as high school students and teachers.Given a randomized algorithm for stochastic optimization and control, this project views each iteration as applying a random operator, and develops new "probabilistic contraction" analysis techniques, created by the investigator, that use stochastic dominance arguments to show convergence to probabilistic fixed points. Specifically, the investigator will develop empirically-inspired algorithms for optimal control of continuous state and action space Markov decision processes, and unconstrained and constrained stochastic optimization problems. The techniques to be developed may be useful for a broader class of stochastic iterative algorithms, and lead to development of a probabilistic fixed point theory of random operators on Banach spaces.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.