技术摘要：关于 $Q^\star$-逼近与部分覆盖下离线强化学习复杂性的研究

问题陈述

本研究探讨了在 $Q^\star$-可实现性 ( $Q^\star$-realizability) 与 部分覆盖 (partial coverage) 设置下，离线强化学习 (Offline RL) 的理论极限。在这种范式中，智能体从一个固定的、预先收集的数据集中学习策略，而不再与环境进行进一步交互。该数据集由一个可能无法覆盖整个状态-动作空间的行为策略（即部分覆盖）生成。

本文解决的核心开放性问题是：$Q^\star$-可实现性（即真实的 $Q^\star$ 函数位于一个已知的函数类内）结合 贝尔曼完备性 (Bellman completeness)（即贝尔曼算子将该函数类映射到其超集）以及 部分覆盖，是否足以实现 样本高效 (sample-efficient) 的学习。虽然这些条件允许构建一个包含真实 $Q^\star$ 的置信集，但本文质疑这是否足以保证稳健的策略选择。

研究方法

1. 信息论下界

作者首先证明了上述条件对于样本高效学习是不充分的。他们构造了一族马尔可夫决策过程 (MDP)，其中：

• $Q^\star$-可实现性和贝尔曼完备性均成立。
• 最优策略的覆盖度为常数 ($\Theta(1)$)。
• 尽管真实的价值函数在函数类内被很好地定位，但学习者无法在导致灾难性错误的策略与安全策略之间做出区分。
• 所需的样本复杂度为 $\Omega(\frac{1}{\epsilon} \min\{\sqrt{|S|}, \frac{1}{\Delta^2}\})$，其中 $\Delta$ 是价值间隙 (value gap)。这表明即使间隙很小，样本复杂度也可能高得令人生畏；其难度不仅在于估计 $Q^\star$，更在于在歧义集内做出稳健的决策。

2. 决策-估计分解框架

为了解决识别出的差距，作者引入了一个受在线 RL 中决策-估计系数 (DEC) 启发的一般性 决策-估计框架。他们将离线 RL 的次优性分解为两个模块化组件：

1. 决策复杂度 (Decision Complexity)： 从一组可能的模型构成的置信集中选择稳健策略的难度。
2. 估计误差 (Estimation Error)： 从离线数据中估计价值函数或模型参数所产生的误差。

他们定义了 离线稳健决策-估计系数 ($Ordec$)：
$$Ordec\text{-}OD_\gamma(F_{conf}) := \min_{\rho \in \Delta(\Pi)} \max_{M \in \mathcal{M}_{conf}} \mathbb{E}_{\pi \sim \rho} \left[ J_M(\pi_M) - J_M(\pi) - \gamma \max_{f \in F_{conf}} D_\pi(f \| M) \right]$$
其中：

• $F_{conf}$ 是可能的 $Q^\star$ 函数的置信集。
• $\mathcal{M}_{conf}$ 是诱导出的可能模型集合。
• $\rho$ 是策略的分布。
• $D_\pi(f \| M)$ 是函数与模型之间的差异度量（例如贝尔曼误差），是在候选模型的最优策略 $\pi_M$ 下评估的（这与在线 DEC 使用学习者自身的策略不同）。

该框架提出了一个算法 (E2D.OR)，其输出的混合策略 $\hat{\pi}$ 满足：
$$J(\pi^\star) - \mathbb{E}[J(\hat{\pi})] \leq Ordec + \text{Estimation Error}$$

核心贡献

1. 关于充分性的否定结果

本文提供了一个信息论下界，证明了 $Q^\star$-可实现性、部分覆盖和贝尔曼完备性对于样本高效的离线 RL 而言是不充分的。这强调了在部分覆盖设置下的核心挑战是“决策”问题——即在置信集内区分安全策略与不安全策略——而不仅仅是“估计”问题。

2. 统一框架与改进界限

提出的 $Ordec$ 框架统一并改进了现有结果：

• 价值间隙设置 (Value-Gap Setting)： 恢复了 Chen 和 Jiang (2022) 的结果，但无需预知间隙值或进行额外的在线交互。该界限能自动适应真实的间隙。
• 正则化设置 (Regularized Setting)： 将部分覆盖下 Soft Q-learning 的样本复杂度从 $\epsilon^{-4}$ (Uehara et al., 2023) 提升至 $\epsilon^{-2}$。这是通过一种针对正则化 MDP 的新型二阶性能差异引理实现的。
• 弯曲决策边界 (Curved Decision Boundary)： 基于连续动作空间中决策边界的曲率引入了一种新的可学习设置，解决了对严格价值间隙假设的实际担忧。

3. 估计误差的新可学习机制

本文刻画了结构性假设在控制估计误差项中的作用：

• 贝尔曼完备性： 提供了 保守 Q 学习 (CQL) 在一般函数逼近下的首次样本复杂度分析（此前仅限于表格型情况）。
• 低贝尔曼秩 (Low Bellman Rank)： 研究了低贝尔曼秩 MDP 的离线可学习性（这是一个经典的在线 RL 设置）。作者指出，在标准数据假设下，低贝尔曼秩对于离线学习是不足够的。他们引入了该机制下学习所需的两个必要条件：
  1. 双重策略采样 (Double Policy Sampling)： 数据必须通过采样一个策略并随后产生两个独立的转移来生成。
  2. 策略特征覆盖 (Policy Feature Coverage)： 对策略特征空间的一种特定覆盖条件。
     放宽其中任何一个条件都会破坏多项式样本复杂度的保证。

结果总结

• 下界： 证明了 $Q^\star$-可实现性 + 贝尔曼完备性 + 部分覆盖 $\nRightarrow$ 样本高效学习。
• 上界： 建立了一个通用的次优性界限，分解为 $Ordec$（决策复杂度）和估计误差。
• 具体界限：
  • 非正则化 (价值间隙)： $\tilde{O}(\frac{H^2}{\gamma \Delta^2} + \gamma \frac{C_{\pi^\star}}{n})$。能够适应未知的间隙。
  • 正则化： $\tilde{O}(\sqrt{\frac{C_{\pi^\star}}{n}})$，实现了 $\epsilon^{-2}$ 的样本复杂度。
  • CQL： 首次给出 CQL 在部分覆盖下的一般函数逼近保证。
  • 低贝尔曼秩： 证明了在标准假设下的不可行性；并确定了双重策略采样和策略特征覆盖是实现学习性的必要条件。

意义与主张

本文声称提供了一个更全面的理解，阐明了在 $Q^\star$-逼近和部分覆盖下离线 RL 的潜力与局限性。其意义在于：

1. 澄清困难的来源： 它将理论焦点从纯粹的估计误差转向了部分覆盖设置中固有的决策复杂度，表明即使在完美估计的情况下，如果没有额外的结构性假设，稳健决策也可能是不可能实现的。
2. 统一性： 它提供了一个模块化框架，通过分离决策复杂度和估计复杂度，恢复、改进并扩展了先前的工作 (Chen and Jiang, 2022; Uehara et al., 2023)。
3. 实际相关性： 通过分析一般函数逼近下的 CQL 以及识别 低贝尔曼秩 问题所需的特定结构要求，这项工作弥合了实际算法与理论保证之间的鸿沟，这些设置在以前被认为是难以处理或理解不足的。
4. 新颖的设置： 它建立了低贝尔曼秩 MDP 在离线 RL 中的首个可学习性条件，并提供了正则化 Soft Q-learning 在部分覆盖下的首个 $\epsilon^{-2}$ 界限。

作者指出，虽然该框架在理论上是完备的，但精确求解极大极小算法在计算上是困难的，不过可以通过 Actor-Critic 方法进行近似。这项工作的主要目的是识别新的可学习机制并刻画实现学习所需的结构性条件。