Collaborative Research: CIF: Medium: Statistical and Algorithmic Foundations of Efficient Reinforcement Learning

强化学习(RL)作为一种在未知环境下进行序贯决策的数据驱动范式，近年来因其潜在的解决与未来社会和科学发展相关的难题的能力而受到人们的广泛关注。然而，当前和新兴应用中模型维度和复杂性的爆炸性增长加剧了在样本匮乏的情况下实现高效RL的挑战，在这种情况下，数据收集是昂贵、耗时的，甚至是高风险的，例如在临床试验、在线广告和自主系统中。因此，理解和提高RL算法的样本和计算效率，有时在额外的资源和系统级限制下，被正确地理解为未来成功部署RL的关键。在这一项目中，公共关系研究所让具有不同电气和计算机工程和统计学背景的各级学生参与，正在开发关于可持续发展的教育模块，以丰富课程，并共同组织讲习班和外展活动，以使项目成果得以更广泛地传播。尽管进行了数十年的研究，但可持续发展的统计和计算基础仍远未得到很好的理解，特别是在具有关键操作价值的有限样本和有限时间问题上。本研究项目正在弥合现代RL算法方法的理论与实践之间的差距。它通过以下方式做到这一点：(I)表征各种RL设置中样本和计算复杂性的基本限制，(Ii)通过开发性能保证和不确定性量化方案，以及(Iii)通过设计新的计算高效算法，这些算法在单代理和多代理设置中的样本复杂性均被证明是近乎最佳的。预期的结果将使RL算法能够在样本匮乏的环境中可靠地采用。通过基于模型、基于政策和基于价值的方法，利用研究团队的互补专业知识来丰富RL的统计和算法基础。依赖于函数近似方案的新的高效算法正在被开发，以解决维度灾难；由此产生的技术旨在导致非渐近分析工具，以处理RL中存在的复杂的统计相关性。这一丰富的研究议程预计将促进高维统计、非凸优化、控制理论、信息论和机器学习的交叉领域的多学科努力。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

As a data-driven paradigm for sequential decision making in unknown environments, Reinforcement Learning (RL) has received significant interest in recent years owing to its potential ability to solve difficult problems associated with future societal and scientific developments. However, the explosion of both model dimensionality and complexity in current and emerging applications exacerbates the challenge of achieving efficient RL in sample-starved situations, where data collection is expensive, time-consuming, or even high-stake, e.g., in clinical trials, online advertising, and autonomous systems. As a result, understanding and improving the sample and computational efficiencies of RL algorithms, sometimes under additional resource and system-level constraints, are rightly understood as critical to the successful deployment of RL in the future. In this project the PIs are involving students at all levels with diverse backgrounds in Electrical and Computer Engineering, and in Statistics, are developing education modules on RL to enrich the curriculum, and are co-organizing workshops and outreach activities to enable the broader dissemination of the project outcomes.Despite decades-long research efforts, the statistical and computational underpinnings of RL are still far from being well understood, especially when it comes to finite-sample and finite-time issues which are of crucial operational value. This research project is bridging the theory-practice gap of modern algorithmic approaches to RL. It is doing so by (i) characterizing fundamental limits for the sample and computations complexities in various RL settings, (ii) by developing performance guarantees and uncertainty quantification schemes, and (iii) by designing new computationally efficient algorithms that are provably near-optimal in terms of sample complexity in both single-agent and multi-agent settings. The expected outcomes will enable the trustworthy adoption of RL algorithms in sample-starved environments. The complementary expertise of the research team is being leveraged to enrich the statistical and algorithmic foundations of RL through model-, policy-, and value-based approaches. New efficient algorithms that rely on function approximation schemes are being developed in order to address the curse of dimensionality; the resulting techniques are intended to lead to non-asymptotic analysis tools that deal with the complicated statistical dependencies present in RL. This rich research agenda is expected to foster multidisciplinary efforts at the intersection of high-dimensional statistics, non-convex optimization, control theory, information theory, and machine learning.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.