IIS:RI Theoretical Foundations of Reinforcement Learning: From Tabula Rasa to Function Approximation

强化学习是一种训练智能代理做出决策的技术，已成为机器人、医疗保健、制造生产、游戏和交通等各种应用的中心算法范式。然而，强化学习同样因需要大量数据和计算资源而臭名昭著。本项目旨在帮助人们对强化学习有一个基本的了解，揭示其内在的困难，并开发出具有强大理论保障的高效算法。该项目的成果很容易应用于解决实际的资源匮乏问题。这个项目的成功还需要在各种学科中使用新的算法技术和数学工具。一个教育计划被整合到这个项目中；调查员将开发新的课程，指导学生，组织研讨会，并通过华盛顿大学的伙伴学校计划为高中生授课。该项目包括两个主要部分。第一个重点研究了最规范的设置--Tabula rasa强化学习。研究人员将确定基本限制，并为几个理论和实践感兴趣的问题开发最优算法：最坏情况的复杂性，对问题结构的适应，以及批量RL的数据收集。第二个推力是由RL的现代使用推动的，其中使用函数近似在大的状态空间上进行推广。研究人员将系统地研究允许三种最流行的函数逼近方案：基于值、基于策略和基于模型的高效学习算法的充要条件。对于这两个推力，研究人员将利用强化学习固有的组合结构来表征其基本难度，并设计有效的算法。除了理论发展，该项目还旨在实现所有作为开源软件开发的算法，并在基准模拟环境中对它们进行评估。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Reinforcement learning, a technique that trains intelligent agents to make decisions, has become the central algorithmic paradigm for various applications, such as robotics, healthcare, manufacturing production, game playing, and transportation. However, reinforcement learning is equally infamous for demanding significant amounts of data and computing resources. This project aims to contribute to the fundamental understanding of reinforcement learning to reveal its inherent difficulties and develop efficient algorithms with strong theoretical guarantees. The results of the project are readily applicable to solving practical resource-hungry problems. The success of this project also requires new algorithmic techniques and mathematical tools in a variety of disciplines. An education plan is integrated into this project; the investigator will develop new courses, mentor students, organize workshops, and deliver lessons to high school students through the University of Washington’s Partner School program.This project has two major components. The first thrust studies the most canonical setting, tabula rasa reinforcement learning. The investigator will identify fundamental limits and develop optimal algorithms for several problems of both theoretical and practical interests: worst-case complexity, adaptation to problem structure, and data collection for batch RL. The second thrust is motivated by the modern usage of RL, where function approximation is employed for generalization over a large state space. The investigator will systematically examine the necessary and sufficient conditions that permit efficient learning algorithms for three of the most popular function approximation schemes: value-based, policy-based, and model-based. For both thrusts, the investigator will utilize the inherent combinatorial structures of reinforcement learning to characterize its fundamental hardness and design efficient algorithms. In addition to theoretical developments, the project also aims to implement all algorithms developed as open-source software and evaluate them on benchmark simulation environments.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.