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

点击翻译按钮获取中文摘要

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.