AI & ML
On the Complexity of Offline Reinforcement Learning with Q*-Approximation and Partial Coverage
arXiv stat.ML0 views
arXiv:2602.12107v3 Announce Type: replace-cross Abstract: 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 $\epsilon^{-2}$ sample complexity bound for soft $Q$-learning under partial coverage that improves Uehara et al.'s (2023) $\epsilon^{-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.
Source:https://arxiv.org/abs/2602.12107PreviousLearning Multinomial Logits in $O(n \log n)$ timeNextThe Value of Information in Resource-Constrained Pricing
Related posts
![Robot Foundation Models and VLA — Ch.03: Vision Language Models for Robotics [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2Fmezw012qznfr1y0dyk0f.png)
Robot Foundation Models and VLA — Ch.03: Vision Language Models for Robotics [EN]
0dev.to
![Robot Foundation Models and VLA — Ch.01: Foundation Model Fundamentals [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2F2ztem9n9rhhk6x17zs5l.png)
Robot Foundation Models and VLA — Ch.01: Foundation Model Fundamentals [EN]
0dev.to
![Robot Foundation Models and VLA — Ch.00: Introduction [EN]](https://media2.dev.to/dynamic/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Farticles%2F9dll4ks73ukbnxzg38wy.png)
Robot Foundation Models and VLA — Ch.00: Introduction [EN]
0dev.to
Best AI tools for SaaS product demo videos in 2026 (sorted by the job you need done)
0dev.to
‘Grand Theft Auto 6’ Is a Perfect Game. Rushing Through It Would Be a Mistake
0Wired
Frostbite: A new CPU architecture discovered, designed and verified by AI
0Hacker News