ISyE Seminar Series: Yunzong Xu

"Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation"

Yunzong Xu

Assistant Professor in the Department of Industrial and Enterprise Systems Engineering
University of Illinois Urbana-Champaign

About the Seminar:

We consider the offline reinforcement learning problem, where the aim is to learn a decision making policy from logged data. Offline RL -- particularly when coupled with (value) function approximation to allow for generalization in large or continuous state spaces -- is becoming increasingly relevant in practice, because it avoids costly and time-consuming online data collection and is well suited to safety-critical domains. Existing sample complexity guarantees for offline value function approximation methods typically require both (1) distributional assumptions (i.e., good coverage) and (2) representational assumptions (i.e., ability to represent some or all Q-value functions) stronger than what is required for supervised learning. However, the necessity of these conditions and the fundamental limits of offline RL are not well understood in spite of decades of research. This led Chen and Jiang (2019) to conjecture that concentrability (the most standard notion of coverage) and realizability (the weakest representation condition) alone are not sufficient for sample-efficient offline RL. We resolve this conjecture in the positive by proving that in general, even if both concentrability and realizability are satisfied, any algorithm requires sample complexity polynomial in the size of the state space to learn a non-trivial policy.

Our results show that sample-efficient offline reinforcement learning requires either restrictive coverage conditions or representation conditions that go beyond supervised learning, and highlight a phenomenon called over-coverage which serves as a fundamental barrier for offline value function approximation methods. A consequence of our results for reinforcement learning with linear function approximation is that the separation between online and offline RL can be arbitrarily large, even in constant dimension.
 

Related Paper: Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation

About the Speaker:

Yunzong Xu is an Assistant Professor in the Department of Industrial and Enterprise Systems Engineering at the University of Illinois Urbana-Champaign, which he joined in 2024. His research focuses on the foundations of machine learning and decision making, their connections to operations research, optimization, and probability, and their applications in areas such as e-commerce and healthcare. Prior to joining Illinois, he was a postdoctoral researcher in the Machine Learning & AI group at Microsoft Research. He received his Ph.D. from MIT in 2023 and his B.S. from Tsinghua University in 2018. He is delighted to visit the University of Minnesota—where he was an exchange student in Fall 2016 and was introduced to operations research—after nearly nine years.

If you wish to be added to the ISyE Graduate Seminar Series emailing list, please email Event Coordinator Emily Rice at [email protected].