Skip directly to content

Minimize RSR Award Detail

Research Spending & Results

Award Detail

Awardee:UNIVERSITY OF WASHINGTON
Doing Business As Name:University of Washington
PD/PI:
  • Simon Du
  • (408) 921-0192
  • ssdu@cs.washington.edu
Award Date:07/26/2021
Estimated Total Award Amount: $ 500,000
Funds Obligated to Date: $ 500,000
  • FY 2021=$500,000
Start Date:10/01/2021
End Date:09/30/2024
Transaction Type:Grant
Agency:NSF
Awarding Agency Code:4900
Funding Agency Code:4900
CFDA Number:47.070
Primary Program Source:040100 NSF RESEARCH & RELATED ACTIVIT
Award Title or Description:IIS:RI Theoretical Foundations of Reinforcement Learning: From Tabula Rasa to Function Approximation
Federal Award ID Number:2110170
DUNS ID:605799469
Parent DUNS ID:042803536
Program:Robust Intelligence
Program Officer:
  • Rebecca Hwa
  • (703) 292-7148
  • rhwa@nsf.gov

Awardee Location

Street:4333 Brooklyn Ave NE
City:Seattle
State:WA
ZIP:98195-0001
County:Seattle
Country:US
Awardee Cong. District:07

Primary Place of Performance

Organization Name:University of Washington
Street:4333 Brooklyn Ave NE
City:Seattle
State:WA
ZIP:98195-0001
County:Seattle
Country:US
Cong. District:07

Abstract at Time of Award

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.

For specific questions or comments about this information including the NSF Project Outcomes Report, contact us.