On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
It addresses the statistical complexity of RL for researchers and practitioners, but is incremental as it reviews existing work.
This paper reviews recent advances in the statistical foundations of offline and low-adaptive reinforcement learning, focusing on offline policy evaluation and learning, and discusses the limitations of offline RL by introducing low-adaptive exploration as a middle ground.
This article reviews the recent advances on the statistical foundation of reinforcement learning (RL) in the offline and low-adaptive settings. We will start by arguing why offline RL is the appropriate model for almost any real-life ML problems, even if they have nothing to do with the recent AI breakthroughs that use RL. Then we will zoom into two fundamental problems of offline RL: offline policy evaluation (OPE) and offline policy learning (OPL). It may be surprising to people that tight bounds for these problems were not known even for tabular and linear cases until recently. We delineate the differences between worst-case minimax bounds and instance-dependent bounds. We also cover key algorithmic ideas and proof techniques behind near-optimal instance-dependent methods in OPE and OPL. Finally, we discuss the limitations of offline RL and review a burgeoning problem of \emph{low-adaptive exploration} which addresses these limitations by providing a sweet middle ground between offline and online RL.