On the Complexity of Offline Reinforcement Learning with Q*-Approximation and Partial Coverage

We study offline reinforcement learning under $Q^\star$-approximation and partial coverage, a setting that motivates practical algorithms such as Conservative $Q$-Learning (CQL) [KZTL20] but has received limited theoretical attention. Our work is inspired by the following open question: \emph{Are $Q^\star$-realizability and Bellman completeness sufficient for sample-efficient offline RL under partial coverage?} We answer this question in the negative through an information-theoretic lower bound. To identify additional structure that enables sample-efficient offline RL under partial coverage, we introduce a general decision-estimation framework, inspired by model-free decision-estimation coefficients (DEC) for online RL [FGO$^+$23, LWZ25b]. Our framework decomposes the complexity of offline RL into two parts: the \emph{decision complexity} and the \emph{value estimation error}. This decomposition allows us to study the two sub-problems in a modular way. Our result not only unifies existing results in the $Q^\star$-approximation and partial coverage regime [CJ22, UKLS23], but further improves and generalizes them. On the decision complexity side, our improvement includes: the first $\epsilon^{-2}$ sample complexity bound for soft $Q$-learning under partial coverage that improves [UKLS23]'s $\epsilon^{-4}$ bound, the removal of the need for additional online interaction in the gap-dependent setting of [CJ22], and new learnable settings beyond the above two cases. On the value estimation side, we provide the first characterization of offline learnability for general low-Bellman-rank MDPs [JKA$^+$17, DKL$^+$21, JLM21], a canonical online RL setting that has remained unexplored in offline RL outside special cases. As a side contribution, our techniques give the first analysis of CQL in the function approximation setting.