CAREER: Reinforcement Learning for Recursive Markov Decision Processes and Beyond

University Of Colorado At Boulder, Boulder CO

Investigators

Abstract

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). Reinforcement Learning (RL) is a sampling-based approach to optimization of Markov decision processes (MDPs), where agents rely on rewards to discover optimal solutions. When combined with powerful approximation schemes (e.g., deep neural networks), RL has been effective in highly complex tasks traditionally considered beyond reach of Artificial Intelligence. However, its sensitivity to the approximation parameters makes RL difficult to use (significant Machine Learning expertise is demanded of the programmer) and difficult to trust (manual approximations can invalidate guarantees). The vision of this project is to democratize RL by developing principled methodologies and powerful tools to improve the usability and trustworthiness of RL-based programming at scale. These research objectives are complemented by efforts to integrate the foundations of RL-based computability in CS education and to explore the role of RL-based programming in CS education. Approximation in RL is needed because RL algorithms with guaranteed convergence work on finite MDPs, and yet scale poorly. Approximation affects usability and trustworthiness. This proposal identifies two goals addressing both concerns: 1) to discover convergent RL beyond finite MDPs and 2) to develop abstraction-based approaches for RL with rigorous optimization guarantees. The success of the proposed approaches will be evaluated by their ability to handle systems at scale. The algorithms and datasets will be disseminated as open-source software. The proposed research makes fundamental contributions to three disciplines: formal methods, machine learning, and control theory; at the same time, it takes fundamental, concrete steps towards broadening participation in computing by making RL-based programming easier and more inclusive. 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.