跳转至

Finite-Sample Theory for Fitted Q-Iteration When Actions Are Functions

作者: Gefei Lin, Rui Miao, Xiaoke Zhang
主题: 因果推断
相关性: 7/10
链接: https://arxiv.org/abs/2609.36390


一、领域脉络与小综述

  • 这个方向是什么:本文属于离线强化学习(Offline Reinforcement Learning)的理论统计方向,核心问题是:给定由行为策略(behavior policy)预先收集的固定数据集(logged data),如何学习一个最优的决策策略(policy),并给出该策略的价值(value)与最优价值之间的差距(即 regret 或 value gap)的有限样本(finite-sample)上界。与在线强化学习不同,离线设定下无法与环境交互,因此必须处理数据覆盖(coverage)不足的问题——即行为策略可能没有访问过某些状态-动作对。本文的特殊之处在于,动作空间本身是函数空间(即每个动作是一个函数,如放疗中的通量图或机器人轨迹),这使得问题同时涉及强化学习、函数型数据分析(Functional Data Analysis)和高维/非参数统计。

  • 发展脉络(history):

    • 奠基工作:经典 fitted Q-iteration (FQI) 由 Ernst et al. (2005) 提出,其核心思想是通过迭代地回归 Bellman 目标来逼近最优 Q 函数。其有限样本分析框架由 Munos & Szepesvári (2008) 和 Farahmand et al. (2010) 建立,他们通过误差传播(error propagation)将每一步的回归误差累积为最终的价值差距。这些工作奠定了本文分析的基本框架。
    • 主要进展(连续动作与覆盖条件):Antos et al. (2007) 将 FQI 的分析推广到连续动作空间,但其关键假设是行为策略的密度在动作空间上有正下界(即全局覆盖),这要求行为策略能探索到所有可能的动作。后续工作如 Chen & Jiang (2019)、Xie & Jiang (2020) 引入了更弱的函数类相对覆盖(function-class-relative coverage)条件,例如通过 Bellman 残差比(Bellman residual ratio)来衡量覆盖程度,而不是要求密度处处为正。本文的 critic-relative coverage 条件正是这一思路在函数型动作空间上的延伸。
    • 当前 frontier(函数型动作与深度模型):Lin et al. (2026) 首次将 FQI 扩展到函数型动作空间,但只提供了算法和实证结果,没有理论保证。本文填补了这一理论空白。同时,深度强化学习的理论分析(如 Nguyen-Tang et al. (2022))强调了对数据依赖的(data-dependent)函数类进行统一控制(uniform control)的必要性,本文继承了这一思想,通过确定性函数类(deterministic classes)和覆盖数(covering numbers)来处理数据重用(data reuse)问题。
    • 本文的位置:本文是第一个为函数型动作空间的离线 FQI 提供有限样本价值差距上界的工作。它通过引入 critic-relative coverage 条件,绕过了函数型动作空间缺乏 Lebesgue 密度这一根本困难,并利用策略的 RKHS 光滑性(smoothness)来控制评估误差。
  • 子线索聚类:

    • 覆盖条件与误差传递:这一簇关注如何量化行为策略与目标策略之间的差异。代表工作包括 Antos et al. (2007)(密度下界)、Munos & Szepesvári (2008)(Lp 范数下的 concentrability)、Xie & Jiang (2020)(Bellman 残差比)、Uehara & Sun (2022)(模型误差比)。本文的 critic-relative coverage 属于这一簇,但针对函数型动作做了专门设计。
    • 函数型数据与核方法:这一簇关注如何对函数型输入进行回归和预测。代表工作包括 Ramsay & Silverman (2005)、Hsing & Eubank (2015) 的经典函数型数据分析,以及 Yao et al. (2021) 的自适应函数型神经网络(AdaFNN)。本文的 KRR 和 AdaFNN 分析分别对应核方法和深度学习方法。
    • 非参数回归的有限样本理论:这一簇关注在光滑性假设下,非参数回归估计量的收敛速度。代表工作包括 Caponnetto & De Vito (2007) 关于核回归的最优率,以及 Schmidt-Hieber (2020) 关于深度 ReLU 网络的逼近理论。本文的证明直接依赖于这些结果。
  • 这个方向在追问的核心问题(2-4 个):

    1. 如何定义并度量函数型动作空间下的覆盖条件? 由于函数型动作没有 Lebesgue 密度,传统的密度比或邻域条件失效。本文给出的答案是 critic-relative coverage,即要求行为数据在与 critic 误差相关的方向上提供足够的信息,而不是在动作空间的几何意义上。
    2. 如何将 critic 的回归误差转化为策略的价值差距? 这需要控制误差在 Bellman 迭代中的传播,并处理策略改进(policy improvement)步骤中贪心选择带来的误差放大。本文通过引入策略光滑性(RKHS 范数惩罚)和 critic-relative coverage 条件来解决。
    3. 在函数型动作空间中,如何实现可计算的策略改进? 精确的贪心最大化在函数空间中通常是不可行的。本文通过将策略限制在 RKHS 球内,并采用平均 Q 目标(average-Q objective)和光滑性惩罚,使得优化问题在数值上可解(如通过 B-spline 或 AdaFNN 参数化)。
    4. 如何获得最优的收敛速度? 给定 critic 的回归误差和覆盖条件,价值差距的最终收敛速度是多少?本文在几个例子中给出了具体的多项式衰减速度,并指出其与函数型数据的内在维度(如光滑性参数)有关。
  • ⚠️ 作者的 framing(必须明确标注成"这是作者的说法"):作者在引言和讨论中,将本文的贡献框架为"为函数型动作空间的离线 FQI 提供了首个有限样本理论保证"。他们强调,已有的覆盖条件(如密度下界)在函数型动作空间中"不适用",而他们提出的 critic-relative coverage 条件"自然且可验证"。作者还声称,他们的分析框架"统一了" KRR 和 AdaFNN 两种函数型动作的拟合方法,并指出其价值差距上界中的指数(如 2/9)是"在给定条件下最优的"。值得注意的是,作者在文中也承认,他们的主要定理依赖于一些较强的假设,例如策略的 RKHS 范数有界、Bellman 算子的稳定传播(γCB < 1)等,这些假设在一般问题中可能难以验证。此外,作者在附录 N 中对比了与 Uehara & Sun (2022) 和 Xie et al. (2021) 的覆盖条件,暗示其条件在某些情况下比这些已有条件更弱,但并未给出严格的比较定理。

  • 张力:未见明显对立引用。作者在附录 N 中详细对比了与已有覆盖条件(如 Uehara & Sun (2022) 的模型误差比和 Xie et al. (2021) 的 Bellman 残差比)的异同,但并未指出这些条件之间存在矛盾或相反结论。相反,作者试图表明其条件是这些已有概念在函数型动作空间中的自然推广。

二、最核心、最简单的例子 / 数学问题

第一步:把符号、模型、可观测数据交代清楚

  • 符号:

    • 状态与动作:\( S \in \mathcal{S} \) 为状态,\( A \in \mathcal{A} \subset L^2([0,1]) \) 为动作,是一个定义在 \( [0,1] \) 上的平方可积函数。
    • 策略:\( \pi: \mathcal{S} \to \mathcal{A} \) 是一个确定性策略,将状态映射到动作函数。策略类 \( \Pi \) 是 RKHS \( \mathcal{H} \) 中的一个球,即 \( \Pi = \{\pi \in \mathcal{H} : \|\pi\|_{\mathcal{H}} \le B_H\} \),其中 \( \|\cdot\|_{\mathcal{H}} \) 是 RKHS 范数。
    • 奖励与转移:\( R_t \in [0,1] \) 为奖励,\( S_{t+1} \) 为下一状态。环境由条件分布 \( P_{\text{env}}(\cdot, \cdot | s, a) \) 刻画,即给定当前状态和动作函数,奖励和下一状态的联合分布。
    • 价值函数:对于策略 \( \pi \),其价值函数为 \( J(\pi) = \mathbb{E}^\pi_{S_0 \sim \rho} \left[ \sum_{t \ge 0} \gamma^t R_t \right] \),其中 \( \rho \) 是初始状态分布,\( \gamma \in (0,1) \) 是折扣因子。
    • Q 函数:\( Q^\pi(s, a) = \mathbb{E}^\pi \left[ \sum_{t \ge 0} \gamma^t R_t \mid S_0 = s, A_0 = a \right] \),表示在状态 \( s \) 采取动作 \( a \) 后遵循策略 \( \pi \) 的期望折扣回报。
    • Bellman 算子:\( [T^\pi Q](s, a) = \mathbb{E}[R + \gamma Q(S', \pi(S')) \mid s, a] \),\( [T Q](s, a) = \mathbb{E}[R + \gamma \max_{\pi' \in \Pi} Q(S', \pi'(S')) \mid s, a] \)。
    • 数据:观测数据 \( \mathcal{D} = \{(S_{i,t}, A_{i,t}, R_{i,t}, S_{i,t+1}) : i \le N, t \le T\} \),来自 \( N \) 条独立轨迹,每条轨迹长度为 \( T \)。总样本量 \( n = NT \)。
    • 经验分布:\( \nu_X = \frac{1}{n} \sum_{i,t} \delta_{(S_{i,t}, A_{i,t})} \) 是状态-动作对的联合经验分布,\( \nu^+ = \frac{1}{n} \sum_{i,t} \delta_{S_{i,t+1}} \) 是下一状态的经验分布。
    • critic 误差:对于 critic \( Q \) 和目标 \( Q^\circ \),其平方误差为 \( \|Q - Q^\circ\|^2_{L^2(\nu_X)} = \int (Q(s,a) - Q^\circ(s,a))^2 \nu_X(ds, da) \)。
    • 策略评估误差:\( \|Q - Q^\circ\|^2_{\nu^+, \Pi} = \int \sup_{\pi \in \Pi} |Q(s, \pi(s)) - Q^\circ(s, \pi(s))|^2 \nu^+(ds) \)。
  • 模型:

    • 数据生成机制:数据由行为策略 \( \pi_b \) 生成,即 \( A_{i,t} \sim \pi_b(\cdot | S_{i,t}) \),但本文考虑确定性行为策略,即 \( A_{i,t} = \pi_b(S_{i,t}) \)。状态转移和奖励由环境 \( P_{\text{env}} \) 决定。
    • 目标:学习一个策略 \( \hat{\pi} \),使得其价值 \( J(\hat{\pi}) \) 尽可能接近最优价值 \( J^\star = \sup_{\pi \in \Pi} J(\pi) \)。本文分析的是 \( \hat{\pi} \) 相对于 \( J^\star \) 的 regret,即 \( J^\star - J(\hat{\pi}) \)。
  • 可观测数据:研究者实际能观测到的是 \( N \) 条长度为 \( T \) 的轨迹,每条轨迹包含状态、动作函数、奖励和下一状态。动作函数 \( A_{i,t} \) 是 \( L^2([0,1]) \) 中的元素,在实际中可能通过离散采样或函数型数据记录得到。关键点:研究者无法观测到行为策略 \( \pi_b \) 的显式形式,也无法观测到环境模型 \( P_{\text{env}} \),只能通过数据来估计 Q 函数和策略。

第二步:讲最小内核

本文的核心数学困难在于:如何从行为策略的数据中,估计出在行为策略未访问过的动作函数上的 Q 值,并保证估计误差可控。

  • 最小例子(一维线性动作):假设状态空间只有一个点 \( \mathcal{S} = \{s_0\} \),动作空间为 \( L^2([0,1]) \),行为策略 \( \pi_b \) 只产生一个固定的动作函数 \( a_b(\cdot) \)。目标策略类 \( \Pi \) 包含所有满足 \( \|a\|_{L^2} \le B_A \) 且 \( \|a\|_{\mathcal{H}} \le B_H \) 的动作函数。Q 函数假设为线性形式:\( Q(s_0, a) = \langle d, a \rangle_{L^2} \),其中 \( d \in L^2([0,1]) \) 是未知的斜率函数。

    • 可观测数据:我们只观测到 \( (s_0, a_b, R, s_0) \) 的重复样本,其中 \( R \) 是奖励。由于状态不变,问题退化为一个函数型回归问题:\( R = \langle d, a_b \rangle + \text{noise} \)。
    • 问题:我们只能估计 \( \langle d, a_b \rangle \),即斜率函数 \( d \) 在方向 \( a_b \) 上的投影。对于任意其他动作 \( a \neq a_b \),我们无法直接估计 \( \langle d, a \rangle \),因为数据中没有关于 \( d \) 在其他方向上信息。
    • critic-relative coverage 的作用:本文的条件 (26) 要求,对于任意两个 critic \( Q, Q' \),其差异 \( h = Q - Q' \) 在行为策略下的平方误差 \( \|h\|^2_{L^2(\nu_X)} \) 能够控制其在策略评估下的误差 \( \|h\|^2_{\nu^+, \Pi} \)。在这个例子中,这意味着我们需要 \( \sup_{a \in \Pi} |\langle d, a \rangle - \langle d', a \rangle|^2 \le C \cdot |\langle d - d', a_b \rangle|^2 \)。这要求目标策略类 \( \Pi \) 中的动作函数与行为动作 \( a_b \) 在方向上不能相差太远,或者要求斜率函数 \( d \) 的光滑性足够强,使得其在 \( a_b \) 上的投影能够控制其在其他方向上的投影。
    • 为什么光滑性有帮助:如果 \( d \) 是光滑的(例如,\( d \in H^2 \)),那么 \( \langle d, a \rangle \) 对 \( a \) 的变化是 Lipschitz 连续的。如果 \( \Pi \) 中的动作函数在 \( L^2 \) 范数下与 \( a_b \) 接近,那么 \( \langle d, a \rangle \) 与 \( \langle d, a_b \rangle \) 的差可以被 \( \|a - a_b\|_{L^2} \) 控制。这样,即使行为策略只覆盖了一个点,只要目标策略类中的动作函数都靠近这个点,我们就能通过估计 \( \langle d, a_b \rangle \) 来近似估计所有 \( \langle d, a \rangle \)。这正是本文 Assumption 2(iii) 中"光滑评估"(smooth evaluation)条件的作用。
  • 核心思想:本文的 critic-relative coverage 条件本质上是在说:我们不需要行为策略覆盖整个动作空间,只需要它在"与 critic 误差相关的方向"上提供足够的信息。这个方向由 critic 的差异 \( h = Q - Q' \) 决定。如果 \( h \) 在行为策略下很小,那么它在策略评估下也必须很小。这比要求行为策略的密度处处为正要弱得多,因为它允许行为策略在某些方向上完全没有信息,只要这些方向对最终的策略评估不重要即可。

三、这篇论文做了什么

  • 三句话:

    1. 研究了什么问题:本文研究了在动作空间为函数空间(如放疗通量图、机器人轨迹)的离线强化学习中,fitted Q-iteration (FQI) 算法的有限样本价值差距(regret)上界。
    2. 核心工具/方法:本文提出了一个名为 critic-relative coverage 的新覆盖条件,该条件通过比较 critic 误差在行为策略分布和策略评估分布下的差异,绕过了函数型动作空间缺乏 Lebesgue 密度的问题。结合策略的 RKHS 光滑性、函数型核回归(KRR)或自适应函数神经网络(AdaFNN)的逼近理论,以及误差传播分析。
    3. 主要结论:在 critic-relative coverage、策略光滑性、稳定传播(γCB < 1)等条件下,FQI 算法学习到的策略的价值差距以高概率收敛到零,其收敛速度由 critic 的回归误差和覆盖条件共同决定。在几个具体例子中,得到了多项式衰减的 regret 界,例如 \( (NT)^{-2/9} \)(两状态例子)和 \( (NT)^{-1/6} \)(AdaFNN 单分数例子)。
  • 关键设定与假设:

    • 策略类:策略被限制在一个 RKHS 球 \( \Pi_H(B_H) \) 内,其范数惩罚 \( \lambda_{\pi,n} \|\pi\|_{\mathcal{H}}^2 \) 用于控制策略的光滑性。这是处理函数型动作空间的关键,因为它使得策略评估和优化在数值上可行,并提供了所需的熵界(entropy bounds)。
    • critic-relative coverage (Assumption 2):这是本文的核心假设。它要求对于任意 critic 差异 \( h \),其策略评估误差 \( \|h\|_{\nu^+, \Pi, 2} \) 可以被行为策略下的误差 \( \|h\|_{L^2(\nu_X)} \) 的 \( \vartheta \) 次幂(乘以一个系数)所控制。这个条件比传统的密度比条件更弱,因为它不要求行为策略覆盖所有动作,只要求它在"相关方向"上提供信息。
    • 稳定传播 (Assumption 4):要求状态转移算子在策略评估范数下是稳定的,即 \( \gamma C_B < 1 \)。这保证了误差在 Bellman 迭代中不会指数级放大。
    • 函数型数据假设:对于 KRR,假设 critic 属于一个已知的 RKHS,且 Bellman 目标可以被该 RKHS 中的函数逼近(逼近误差 \( \eta_Q \) 可控)。对于 AdaFNN,假设 Bellman 目标具有某种光滑性(如 Sobolev 光滑),且网络可以逼近。
    • 行为策略:行为策略是确定性的,且其产生的动作函数满足一定的矩条件(如 \( \mathbb{E}\|A\|_{L^2}^2 < \infty \))。行为策略的分布可以随时间变化,但必须满足一定的混合条件(Assumption 5)。
  • 主要结果:

    • 定理 1(一般价值差距界):在 Assumptions 3 和 4 下,FQI 算法返回的策略 \( \hat{\pi}_M \) 的价值差距满足:
      \[J^\star - J(\hat{\pi}_M) \le a_H + C \left\{ (\gamma C_B)^M + \varepsilon_{Q,n} + \varepsilon_{\pi,n} \right\}\]
      其中 \( a_H \) 是策略类逼近误差,\( (\gamma C_B)^M \) 是有限迭代误差,\( \varepsilon_{Q,n} \) 是 critic 回归误差,\( \varepsilon_{\pi,n} \) 是策略优化误差。
    • 定理 2(KRR 特化):在 KRR 下,critic 回归误差 \( \varepsilon_{Q,n} \) 可以进一步分解为逼近误差和估计误差,最终得到 regret 界为 \( \tilde{O}(n^{-\vartheta(1-p_K)/4}) \),其中 \( p_K \) 是覆盖数的多项式指数。
    • 定理 3(AdaFNN 特化):在 AdaFNN 下,regret 界为 \( \tilde{O}(n^{-\min\{\vartheta,1/2\}/(2+D)}) \),其中 \( D \) 是网络复杂度指数。
    • 例子 1(两状态模型):验证了所有条件,得到了 \( (NT)^{-2/9} \) 的 regret 率。
  • 证明路线与技术技巧:

    1. 误差分解:将价值差距分解为策略类逼近误差 \( a_H \)、有限迭代误差、critic 回归误差和策略优化误差。这是 FQI 分析的标准步骤。
    2. critic 误差传播:利用 Bellman 算子的收缩性质和 Assumption 4 的稳定传播条件,将每一步的 critic 误差累积为最终的价值差距。关键技巧是使用 \( \| \cdot \|_{\nu^+, \Pi, 2} \) 范数来衡量 critic 误差,并利用 Assumption 2 的 critic-relative coverage 条件将其与行为策略下的误差联系起来。
    3. 函数型回归的有限样本界:
      • KRR:利用核函数的特征分解(谱理论),将回归问题转化为一个有限维问题。通过控制经验过程(empirical process)的覆盖数,得到估计误差的界。关键技巧是使用插值不等式(interpolation inequality)将 \( L^2(\nu_X) \) 误差转化为 \( L^2(\nu^+) \) 误差,这依赖于 Assumption 2 的 Hölder 条件。
      • AdaFNN:利用深度网络的逼近理论(Schmidt-Hieber, 2020),将 Bellman 目标函数分解为网络逼近部分和估计部分。通过控制网络参数的覆盖数,得到估计误差的界。
    4. 策略改进误差:由于策略优化是在 RKHS 球内进行的,通过 RKHS 的再生性质,可以将策略改进误差转化为 critic 在策略评估范数下的误差。关键技巧是使用凸对偶或变分不等式来处理最大化问题。
    5. 处理数据重用:由于 FQI 迭代中反复使用同一数据集,需要处理数据依赖(data-dependent)的标签。作者采用确定性函数类(deterministic function classes)和覆盖数(covering numbers)来统一控制所有可能的 critic 和策略,从而避免了复杂的概率工具(如 empirical process 的局部 Rademacher 复杂度)。
  • 真实例子与应用:

    • 例子 1(两状态模型):这是一个理论验证例子,用于说明 critic-relative coverage 条件在行为策略支持与目标策略支持不重叠时仍然可以成立。它展示了即使行为策略的动作与最优动作在 \( L^2 \) 距离上相距很远,只要 critic 差异在行为策略下可观测,就能保证策略评估的准确性。
    • 实验(OpenAI Gym Pendulum):作者修改了 Pendulum 环境,将标量扭矩动作改为函数动作(即每个决策间隔内施加一个随时间变化的扭矩函数)。实验比较了 FQI 使用函数型动作和常数动作的性能,结果显示函数型动作能获得更高的价值。实验还计算了 critic-relative coverage 的诊断指标(如 critic 能量比),发现该指标与策略性能相关,从而为理论条件提供了实证支持。
  • 🔎 结论是否比证明窄:

    • 是。作者在定理 1 中给出了一个一般性的价值差距上界,但该上界依赖于一些隐式的常数(如 \( C \)),这些常数可能依赖于问题参数(如状态空间大小、动作空间的 RKHS 结构等),但作者没有给出这些常数的显式表达式。这使得定理的结论在形式上比证明更"宽",但在实际应用中难以直接使用。
    • 更具体地,作者在定理 2 和 3 中给出的收敛速度依赖于一些假设,如覆盖数指数 \( p_K \)、光滑性参数 \( s_h, s_b \) 等。这些参数的具体值取决于函数类(如 RKHS 的谱衰减、神经网络的宽度和深度),但作者没有给出如何根据实际问题选择这些参数的指导。因此,结论中的"多项式衰减"是一个定性结果,而非定量结果。
    • 此外,作者在定理 1 中假设了 \( \gamma C_B < 1 \),这是一个很强的条件,它要求状态转移的稳定性。在一般强化学习问题中,这个条件可能不满足,但作者没有讨论如何放松这个条件。
    • 最后,作者在实验部分承认,他们的实验"does not verify all conditions of the value guarantee",即实验只是提供了启发性的证据,而非对理论条件的严格验证。

四、开放问题

  1. critic-relative coverage 条件的可验证性:作者在文中给出了该条件的定义,但没有给出如何从数据中验证或估计该条件的方法。一个开放问题是:是否存在一个数据驱动的程序,可以检验给定的数据集和策略类是否满足 critic-relative coverage?这类似于强化学习中的"concentrability coefficient"估计问题。
  2. 最优收敛速度:作者在几个例子中给出了具体的收敛速度,但并未证明这些速度是最优的。一个开放问题是:在函数型动作空间的离线 FQI 中,价值差距的 minimax 最优收敛速度是什么?这需要建立相应的下界。
  3. 策略优化算法的计算复杂性:本文的理论分析假设策略优化步骤可以精确求解(或达到给定的误差容限)。但在实践中,函数型动作空间的策略优化本身就是一个困难的优化问题。一个开放问题是:如何设计高效的算法来求解带 RKHS 范数惩罚的平均 Q 目标,并保证其计算误差可控?
  4. 扩展到随机策略与部分可观测:本文只考虑了确定性策略和完全可观测的 MDP。一个自然的扩展是:如何将 critic-relative coverage 条件推广到随机策略(stochastic policies)或部分可观测 MDP(POMDP)?这可能需要新的覆盖定义和误差传播分析。
  5. 与其他覆盖条件的比较:作者在附录 N 中对比了与已有覆盖条件(如 Bellman 残差比)的异同,但没有给出严格的包含关系或反例。一个开放问题是:在函数型动作空间中,critic-relative coverage 是否严格弱于已有的覆盖条件?是否存在一个例子,使得前者成立而后者不成立?

提示:要确认上述问题是否为真 gap,建议去读同子领域(offline RL with function approximation, functional data analysis in RL)近期约 5 篇论文的引言和讨论部分。如果多篇论文都提到"缺乏可验证的覆盖条件"或"函数型动作空间的策略优化计算困难",那么这些问题就是共识性的 gap。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论