揭示离线强化学习在部分覆盖下的理论瓶颈，提出新框架提升样本效率。
On the Complexity of Offline Reinforcement Learning with $Q^\star$-Approximation and Partial Coverage
- 构建决策-估计框架，分离离线强化学习的复杂性
- 首次实现ε⁻²样本复杂度，优于已有ε⁻⁴结果
- 适用于更广的学习场景，为算法设计提供理论依据
本文研究在$Q^\star$-近似和部分覆盖条件下的离线强化学习，针对该设定下样本高效学习是否可能这一开放问题，通过信息论下界证明答案是否定的。为此，提出一种受在线决策-估计系数启发的通用决策-估计框架，将离线强化学习复杂性分解为决策复杂度与值函数估计误差。该框架不仅统一并改进了现有成果（Chen and Jiang, 2022; Uehara et al., 2023），还在决策复杂度方面取得突破：首次获得软$Q$-learning在部分覆盖下的$ε^{-2}$样本复杂度，优于Uehara等（2023）的$ε^{-4}$；消除陈与江（2022）中对额外在线交互的需求，并拓展至新可学习设定。在值估计方面，首次刻画贝尔曼完备性在部分覆盖下的作用，以及一般低贝尔曼秩MDP的离线可学习性。此外，首次分析了保守$Q$-学习（CQL）在函数近似下的表现。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。