On Gap-dependent Bounds for Offline Reinforcement Learning
This work addresses sample efficiency for offline RL practitioners, offering theoretical improvements that are incremental but with specific gains in complexity bounds.
The paper tackles the problem of sample complexity in offline reinforcement learning by showing that under optimal policy coverage assumptions, the rate can be improved from O(1/ε²) to O(1/ε) with a positive sub-optimality gap, and under uniform coverage, optimal policy identification becomes independent of 1/ε, with nearly-matching lower bounds provided.
This paper presents a systematic study on gap-dependent sample complexity in offline reinforcement learning. Prior work showed when the density ratio between an optimal policy and the behavior policy is upper bounded (the optimal policy coverage assumption), then the agent can achieve an $O\left(\frac{1}{ε^2}\right)$ rate, which is also minimax optimal. We show under the optimal policy coverage assumption, the rate can be improved to $O\left(\frac{1}ε\right)$ when there is a positive sub-optimality gap in the optimal $Q$-function. Furthermore, we show when the visitation probabilities of the behavior policy are uniformly lower bounded for states where an optimal policy's visitation probabilities are positive (the uniform optimal policy coverage assumption), the sample complexity of identifying an optimal policy is independent of $\frac{1}ε$. Lastly, we present nearly-matching lower bounds to complement our gap-dependent upper bounds.