Title: From Knapsacks to Self-Driving: FPTAS Recipes for Constrained Reinforcement Learning
Abstract: In reinforcement learning applications such as autonomous vehicles, constraints are critical to achieve goals and ensure
safety. Many useful constraint formulations are generalizations of the knapsack problem. However, due to the stochastic environment and sequential nature of decisions, straightforward translations of classical FPTASs are not possible. In fact, unlike the knapsack
problem, our problem is NP-hard to approximate when more than one constraint is present. Despite these challenges, we use new techniques to devise FPTASs for many constraint criteria. Our work answers three open questions spanning two different lines of research:
polynomial-time approximability is possible for 1) anytime-constrained policies, 2) almost-sure-constrained policies, and 3) deterministic expectation-constrained policies, which has been open for nearly 25 years.
This work will appear at Neurips 2024 [Arxiv]
Best,
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}