Hi everyone,
This week we have our very own Jeremy McMahan
giving a talk. It will be in CS 3310 2-3pm.
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]
See you then!
Sandeep
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}