On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coverage
On the map: Offline RL and imitation learning from data → Offline RL algorithms
Abstract (arXiv)
We study offline reinforcement learning under Q^star-approximation and partial coverage, a setting that motivates practical algorithms such as Conservative Q-Learning (CQL; Kumar et al., 2020) 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 in the negative via 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 (Foster et al., 2023b; Liu et al., 2025b). Our framework decomposes offline RL complexity into decision complexity and value estimation error. This allows modular study of both sub-problems. Our result not only unifies existing results (Chen and Jiang, 2022; Uehara et al., 2023), 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 Uehara et al.'s (2023) ε-4 bound, the removal of the need for additional online interaction in the value-gap setting of Chen and Jiang (2022), and new learnable settings beyond the above two cases. On the value estimation side, we provide a new characterization of the role of Bellman completeness under partial coverage, and the first characterization of offline learnability for general low-Bellman-rank MDPs (Jiang et al., 2017; Du et al., 2021; Jin et al., 2021). The latter is a canonical online RL setting that has remained unexplored in offline RL except for special cases. As a side contribution, our techniques give the first analysis of CQL in the function approximation setting.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 33 of its 36 references that are in the map. First posted on arXiv 12 Feb 2026.
Builds on
33 of 36 references.
Closest ancestors · 19
Same direction, newest first
- 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory11 Aug
- 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation17 Jun
- 2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data25 Mar
- 2024Harnessing Density Ratios for Online Reinforcement Learning18 Jan
- 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage5 Feb
- 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation23 Nov
- 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangian1 Nov
- 2022The Role of Coverage in Online Reinforcement Learning9 Oct
- 2022On Gap-dependent Bounds for Offline Reinforcement Learning1 Jun
- 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gaps25 Mar
- 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability9 Feb
- 2022Adversarially Trained Actor Critic for Offline Reinforcement Learning5 Feb
7 more
- 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation21 Nov
- 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
- 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
- 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
- 2020Batch Value-function Approximation with Only Realizability11 Aug
- 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
- 2019Behavior Regularized Offline Reinforcement Learning26 Nov
Other references · 14
- 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
- 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
- 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
- 2021The Statistical Complexity of Interactive Decision Makingcited by 208
- 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
- 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
- 2016The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Banditscited by 48
- 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
- 2015A Practical Guide to Robust Optimizationcited by 16
- 2024The Power of Resets in Online Reinforcement Learningcited by 14
- 2022Model-Free Reinforcement Learning with the Decision-Estimation Coefficientcited by 11
- 2025Decision Making in Hybrid Environments: A Model Aggregation Approachcited by 3
Built on by
Not cited yet.
Similar, not cited
Close in wording, no citation either way
- 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
- 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
- 2023Offline Reinforcement Learning with Additional Covering Distributions
- 2023What can online reinforcement learning with function approximation benefit from general coverage conditions?
- 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
- 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning
- 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
- 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient