Settling the sample complexity of model-based offline reinforcement learning
本文证明基于模型的离线强化学习方法在表格型马尔可夫决策过程中无需额外成本即可达到最优样本复杂度，适用于数据有限的场景。
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.