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: 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 decision complexity and the 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 ${ϵ}^{-2}$ sample complexity bound for soft $Q$-learning under partial coverage that improves [UKLS23]'s ${ϵ}^{-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.