Settling the sample complexity of model-based offline reinforcement learning
Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, Yuting Wei
The Annals of Statistics · 2024 · Volume 52 · Issue 1
Abstract
This paper is concerned with offline reinforcement learning (RL), which learns using precollected data without further exploration. Effective offline RL would be able to accommodate distribution shift and limited data coverage. However, prior results either suffer from suboptimal sample complexities or incur high burn-in cost to reach sample optimality, thus posing an impediment to efficient offline RL in sample-starved applications. We demonstrate that the model-based (or “plug-in”) approach achieves minimax-optimal sample complexity without any burn-in cost for tabular Markov decision processes (MDPs). Concretely, consider a γ-discounted infinite-horizon (resp., finite-horizon) MDP with S states and effective horizon 11−γ (resp., horizon H), and suppose the distribution shift of data is reflected by some single-policy clipped concentrability coefficient Cclipped⋆. We prove that model-based offline RL yields ε-accuracy with a sample complexity of SCclipped⋆ (1−γ)3ε2(infinite-horizon MDPs),H4SCclipped⋆ ε2(finite-horizon MDPs), up to log factor, which is minimax optimal for the entire ε-range. The proposed algorithms are “pessimistic” variants of value iteration with Bernstein-style penalties, and do not require sophisticated variance reduction. Our analysis framework is established upon delicate leave-one-out decoupling arguments in conjunction with careful self-bounding techniques tailored to MDPs.
Keywords
62C20, distribution shift, Markov decision process, Minimax optimality, offline reinforcement learning, sample complexity
Enable JavaScript for citation tools and additional paper interactions.