跳转至

Sampling Complexity of TD and PPO in RKHS

讲者: Ding Liang
会场: Some Aspects Related to Feature Learning
报告题目: Sampling Complexity of Temporal Difference and PPO in RKHS
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

本文研究的根本问题是：在连续状态-动作空间的强化学习（RL）中，如何为策略优化算法（如PPO、TRPO、NPG）提供可证明的收敛保证，特别是当使用非线性函数逼近器（如神经网络、核方法）时。当前的理论成熟度是：对于表格（离散状态-动作）和线性函数逼近设定，收敛性已有较完整的理解；但对于非线性/非参数函数类，理论分析仍然碎片化，且常依赖于理想化的假设（如精确值函数估计、强可实现性条件）。本文试图在再生核希尔伯特空间（RKHS） 这一统一的函数空间框架下，弥合理论与实践的差距。

发展脉络

  1. 奠基工作：策略梯度与TD学习的理论起点

    • Sutton (1988)：提出TD学习，为策略评估奠定基础。
    • Kakade (2001)：提出自然策略梯度（NPG），引入Fisher信息矩阵作为预条件，加速收敛。
    • Schulman et al. (2015, 2017)：提出TRPO和PPO，通过KL散度约束或裁剪目标函数，实现稳定的策略更新，成为实践中的主流算法。本文引用语境指出，这些算法“与表达性强的函数逼近器兼容”，但理论理解“仍然碎片化”。

  2. 主要进展：线性与表格设定的理论成熟

    • TD学习：Bhandari et al. (2018) 和 Srikant & Ying (2019) 为线性TD建立了有限时间误差界，证明了其与在线梯度下降的深刻联系。本文引用语境称线性TD“已被充分理解”。
    • 策略优化：Agarwal et al. (2020) 证明了在表格和受限策略类下的全局收敛性。Mei et al. (2020) 分析了softmax参数化下策略梯度的收敛率。Cen et al. (2022) 证明了熵正则化NPG的快速线性收敛。本文引用语境指出，这些分析“通常只在表格/线性设定下建立收敛性”。

  3. 当前Frontier：非线性函数逼近与神经网络的挑战

    • 神经TD：Cai et al. (2019) 首次为过参数化神经网络下的TD学习提供了有限样本分析，证明了次线性收敛率。这是一个关键突破，但本文引用语境指出，其分析限于“离散动作（和连续状态）”。
    • 神经策略梯度：Liu et al. (2019) 证明了过参数化两层神经网络策略的镜像下降策略优化在连续状态、离散动作问题下的全局收敛。Wang et al. (2019) 证明了神经NPG的全局最优性和次线性收敛率。这些工作依赖于神经正切核（NTK）机制，将神经网络训练近似为RKHS中的核梯度下降。
    • 核方法在RL中的应用：Duan et al. (2024) 提出了正则化核LSTD估计器，并推导了非渐近误差界和匹配的minimax下界。这是与本文最直接相关的近期工作，但本文引用语境指出，其分析针对的是“与动作无关的马尔可夫链”，而本文处理的是与策略相关的Q函数。

  4. 本文的位置：本文试图将上述两条线索（核TD + 核NPG）统一在一个RKHS框架下，提供一个端到端的分析：从核TD评估器的非渐近误差，到核NPG策略更新的全局收敛率，并显式量化了每轮迭代所需的样本量。这填补了现有分析中“将期望项视为精确或未指定”的空白。

子线索聚类

  1. 策略优化理论：聚焦于NPG、TRPO、PPO的收敛性。代表工作：Kakade (2001), Schulman et al. (2015, 2017), Agarwal et al. (2020), Mei et al. (2020), Cen et al. (2022), Bhandari & Russo (2024), Liu et al. (2019), Wang et al. (2019)。这一簇的核心是分析策略梯度或自然梯度更新的动力学，通常依赖于性能差异引理和镜像下降分析。
  2. TD学习理论：聚焦于策略评估的收敛性。代表工作：Sutton (1988), Bhandari et al. (2018), Srikant & Ying (2019), Cai et al. (2019), Duan et al. (2024)。这一簇的核心是分析贝尔曼误差的衰减，通常使用线性随机逼近或经验过程理论。
  3. RKHS与核方法在RL中的应用：聚焦于使用核技巧处理连续空间。代表工作：Grunewalder et al. (2012), Feng et al. (2020), Koppel et al. (2020), Duan et al. (2024)。这一簇的核心是将值函数或策略嵌入RKHS，利用核函数的性质（如表示定理）进行学习和推断。

核心问题与瓶颈

  1. 如何设计一个可证明收敛的策略优化算法，使其在非线性函数逼近下也能工作？ 现有分析要么局限于线性/表格设定，要么依赖于过参数化神经网络（NTK）这一特殊情形。
  2. 如何控制函数逼近误差？ 当使用一个受限的函数类（如RKHS）来逼近真实值函数时，逼近误差（bias）和估计误差（variance）如何权衡？本文通过核岭回归（KRR）和正则化来处理。
  3. 如何量化策略更新所需的样本量？ 许多理论分析假设可以精确计算期望，或未指定每轮迭代需要多少数据。本文试图显式回答这个问题，给出了一个依赖于策略复杂度和RKHS熵的采样规则。
  4. 如何统一不同函数类（表格、Sobolev、NTK、高斯核）下的收敛率？ 本文通过RKHS的覆盖数（熵）来刻画函数类的复杂度，从而提供了一个统一的框架。

⚠️ 作者的Framing

  • 作者把缺口frame成什么？ 作者将现有工作的缺口总结为：“现有分析通常只在表格/线性设定下建立收敛性，或依赖于强可实现性和集中性条件”（引用Agarwal et al., 2020; Bhandari & Russo, 2024）。此外，许多策略改进界“将期望项视为精确计算或未指定”，留下了“每轮迭代所需数据量”的空白。本文通过将问题置于RKHS中，并显式量化采样复杂度，将自己定位为“显然的下一步”。
  • 哪些竞争路线被淡化或回避了？ 作者淡化了直接分析神经网络（而非其NTK）的路线。虽然引用了Cai et al. (2019)和Liu et al. (2019)等神经TD/NPG工作，但本文的核心是RKHS，并声称“因为核梯度下降模仿了宽网络的NTK动力学”，所以其分析“直接指导”了神经批评家/演员。这回避了分析有限宽度神经网络或非NTK机制的困难。
  • 什么明显该被引/该存在、却没出现在intro里？ 作者没有引用关于策略梯度方法的minimax下界或统计-计算权衡的工作。对于一个声称要分析“采样复杂度”的论文，讨论其下界（例如，是否存在算法能以更少的样本达到相同的收敛率？）是自然的延伸。此外，对于off-policy评估的核方法（如Feng et al. (2020)的Kernel Bellman Statistics），虽然被列为相关工作，但在正文中并未深入比较或利用其思想。

张力

未见明显对立引用。所有被引工作基本沿着“从简单设定到复杂设定”的脉络发展，彼此之间没有根本性的矛盾。不同设定下的收敛率差异（如表格 vs. Sobolev）被视为函数类复杂度的自然体现，而非理论冲突。

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

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

  • 符号：

    • S, A: 状态空间和动作空间，均为紧凸集。
    • s ∈ S, a ∈ A: 单个状态和动作。
    • ω = (s, a) ∈ S × A: 状态-动作对。
    • π(a|s): 策略，一个从状态到动作概率分布的映射。
    • P(s'|s, a): 转移核，给定当前状态-动作对，下一状态的分布。
    • r(s, a): 奖励函数。
    • γ ∈ [0, 1]: 折扣因子。
    • Q^π(s, a): 动作值函数（Q函数），是我们要估计的目标参数。
    • V^π(s): 状态值函数。
    • T[Q]: 贝尔曼评估算子，其不动点是 Q^π。
    • H: 一个由正定核 K 诱导的RKHS。我们假设 Q^π ∈ H。
    • K(ω, ω'): 核函数，定义了RKHS的内积和函数空间。
    • ∥·∥_H: RKHS范数，衡量函数的平滑性/复杂度。
    • ∥·∥_n: 经验范数，基于 n 个样本计算。
    • σ^π_0(s, a) = π(a|s) μ_0(s): 由初始状态分布 μ_0 和策略 π 诱导的状态-动作分布。
    • ν*: 最优策略 π* 下的平稳状态分布。
    • n: 每轮策略评估使用的样本量。
    • k: 策略迭代的轮数。
    • λ: 核岭回归的正则化参数。
    • α_t, η_t: 核TD更新中的权重衰减和学习率。

  • 模型：

    • 数据生成过程是一个马尔可夫决策过程（MDP）：(S, A, P, r, γ)。
    • 我们关注的是策略评估问题：给定一个策略 π，我们希望从数据中估计其Q函数 Q^π。
    • 我们假设 Q^π 属于一个已知的RKHS H。这是一个模型假设，它规定了函数的光滑性。
    • 我们使用核岭回归（KRR） 来估计 Q^π，其目标函数是经验贝尔曼残差平方和加上RKHS范数惩罚。

  • 可观测数据：

    • 对于给定的策略 π，我们能够观测到的是单步转移的样本：(s_0, a_0, r_0, s_1, a_1)。
    • 具体来说，我们从初始分布 μ_0 采样 s_0，然后根据策略 π 采样 a_0，接着环境根据转移核 P 给出 s_1 和奖励 r_0，最后再根据 π 采样 a_1。
    • 关键点：我们观测到的是 (s_0, a_0) 和 (s_1, a_1) 这一对状态-动作对，以及对应的奖励 r_0。我们无法直接观测到真实的Q函数 Q^π，也无法观测到未来的无限长轨迹。我们只能通过贝尔曼方程，利用单步样本来构建对 Q^π 的估计。

第二步：最小内核

本文的核心数学问题可以归结为：如何用单步转移样本，在RKHS中有效地估计Q函数，并保证估计误差随样本量增加而减小？

最简特例：离散状态-动作空间（表格设定）

在这个特例下，RKHS退化为一个有限维空间。设状态-动作空间大小为 M。核函数 K(ω, ω') = δ_{ω, ω'}（克罗内克δ函数）。那么： - H 中的函数 f 可以表示为一个 M 维向量 f ∈ R^M。 - RKHS内积 ⟨f, g⟩_H = f^T g。 - 经验范数 ∥f∥_n^2 = (1/n) Σ_i f(ω_0^{(i)})^2。 - 贝尔曼算子 T 是一个线性算子，可以表示为矩阵 T。 - 核TD更新（公式9）退化为： f_{t+1} = (1-α_t) f_t - η_t (f_t(ω_0) - r - γ f_t(ω_1))，其中 f_t(ω_0) 是一个向量，其元素是 f_t 在采样到的状态-动作对上的值。

在这个特例下，要证的命题退化成什么？ 定理9（收敛率）退化为：存在一个估计量 f_t，使得 ∥f_t - Q^π∥_n ≤ O_p( (1-cγ)^{-1} n^{-1/2} |log n|^{1/2} )。 这正是推论10中表格情形的结果。

证明怎么走？ 1. 误差分解：将 f_t - Q^π 分解为统计误差 (ˆQ^π - Q^π) 和优化误差 (f_t - ˆQ^π)。 2. 统计误差：ˆQ^π 是KRR的解。通过经验过程理论（Lemma 17），可以控制经验贝尔曼残差项，并结合正则化参数 λ 的选择，得到 ∥ˆQ^π - Q^π∥_n 的界。 3. 优化误差：核TD更新（公式9）是一个线性迭代。通过选择合适的 α 和 η，可以证明该迭代以几何级数收敛到 ˆQ^π（公式11）。只要迭代次数 T 足够大，优化误差就可以被统计误差所主导。 4. 合并：将两步的误差合并，就得到了最终的收敛率。

为什么成立？ - 表格设定下，问题本质上是线性的。贝尔曼算子、KRR解、TD更新都是线性运算。因此，整个分析可以简化为矩阵和向量的运算。 - 核心困难在于处理统计误差，即如何控制由有限样本引起的随机波动。这通过经验过程理论（处理经验均值与总体均值的偏差）和正则化（控制函数复杂度）来解决。 - 优化误差是相对简单的，因为线性迭代的收敛性分析是标准的。

一般情形（连续空间、一般RKHS）只是这个特例的“加壳”： - “加壳”1：函数空间是无限维的。这要求我们用算子理论（协方差算子 C_{ω_0, ω_0}）来重写KRR和TD更新，并用覆盖数（熵）来刻画函数类的复杂度，以应用经验过程理论。 - “加壳”2：样本不是独立同分布的。由于MDP的马尔可夫性，样本 (s_0, a_0, s_1, a_1) 之间存在依赖。本文通过假设1和6（分布有界、一步转移可控）来简化问题，使得中心极限定理和经验过程理论仍然适用。 - “加壳”3：需要从经验范数推广到总体L2范数。这通过采样不等式（Sampling Inequality，如公式79）来实现，该不等式将经验误差与总体误差联系起来，其形式依赖于RKHS的结构（如表格、Sobolev、高斯核）。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：在RKHS框架下，为策略评估（TD学习）和策略改进（NPG/PPO）提供了统一的非渐近收敛性分析，并显式量化了达到最优 O(1/√k) 收敛率所需的每轮采样复杂度。
  2. 核心工具/方法：使用核梯度下降进行TD学习（作为隐式预条件器），使用KL-正则化的函数空间近端更新进行策略改进（通过指数化评估的Q值），并利用经验过程理论和采样不等式进行误差分析。
  3. 主要结论：核TD估计器的误差以minimax最优率（对数项内）收敛；核NPG算法在适当选择每轮样本量 n(k) 和正则化参数 λ(k) 后，可以达到 O(1/√k) 的全局收敛率，该采样规则依赖于策略的RKHS范数和RKHS的熵。

关键设定与假设

  • Assumption 1 (分布有界)：σ* 和 σ^π_0 的密度有上下界。这确保了分布不会过于稀疏或集中，是应用经验过程理论和采样不等式的标准技术假设。
  • Assumption 2 (RKHS范数有界)：奖励函数 r 和转移核 P(s|·,·) 的RKHS范数有界。这保证了Q函数的RKHS范数也有界（Lemma 3），是控制函数复杂度的关键。
  • Assumption 5 (覆盖数/熵条件)：RKHS单位球的覆盖数满足 H(δ, L∞, B) ≤ C δ^{-2β} |log δ|^{2κ}。这是本文最核心的假设，它用一个简洁的参数 β 和 κ 刻画了RKHS的“容量”。β=0 对应表格/高斯核等“小”空间，β>0 对应Sobolev/NTK等“大”空间。这个假设比直接假设函数类维度更通用。
  • Assumption 6 (一步转移可控)：存在常数 c 使得 P(s'|s,a) ≤ c^2 μ_0(s') 且 cγ < 1。这确保了马尔可夫链的混合速度足够快，使得单步样本近似独立，是应用独立同分布理论的关键。常数 1-cγ 出现在收敛率中，反映了采样复杂度。

相比已有文献： - 放宽：相比线性TD分析（Bhandari et al., 2018），本文处理了无限维RKHS。 - 强化：相比神经TD分析（Cai et al., 2019），本文的假设（覆盖数）更一般，不依赖于过参数化结构。 - 补充：相比核LSTD分析（Duan et al., 2024），本文处理了与策略相关的Q函数，并耦合了策略改进步骤。

主要结果

  1. 定理9 (核TD的收敛率)：在假设1-6下，通过选择合适的参数，核TD估计器 f_t 在训练数据上的经验误差满足： ∥f_t - Q^π∥_n ≤ O_p( (1-cγ)^{-(2+β)/(2+2β)} n^{-1/(2+2β)} |log n|^{κ/(1+β)} )。

    • 直觉：收敛率由 n^{-1/(2+2β)} 主导。β 越大（函数类越复杂），收敛越慢。当 β=0 时，恢复出 n^{-1/2} 的经典率（表格/高斯核）。(1-cγ) 项反映了MDP的混合速度。
    • 技术难点：证明的核心是控制经验过程项（Lemma 17），这需要利用覆盖数假设来界定函数类的复杂度，并应用Geer (2000)的尾概率界。

  2. 推论10 (四种RKHS下的L2收敛率)：将定理9的经验误差通过采样不等式推广到总体L2误差，给出了表格、Sobolev、NTK、高斯核四种情形的具体收敛率。例如，Sobolev空间（光滑度 m，本征维数 d）的收敛率为 n^{-m/(2m+d)}，这与非参数回归的minimax最优率一致。

  3. 定理12 (核NPG的全局收敛界)：给出了算法1的次优性上界： inf_k [R[π*] - R[π_k]] ≤ ( Σ_k 2Δ_k ∥f^{(k)} - Q^{(k)}∥_{L∞} + Σ_k Δ_k^2 (1-γ)^{-1} ∥r∥_{L∞} + E[KL(π*||π_0)] ) / Σ_k Δ_k。

    • 直觉：这是一个典型的镜像下降分析。分子有三项：策略评估误差、步长引起的误差、初始策略与最优策略的KL散度。分母是累积步长。
    • 技术难点：证明需要将性能差异引理（Lemma 22）与KL散度的递推关系（公式93-95）结合，并处理L∞范数下的评估误差。

  4. 推论13 (达到O(1/√k)率的采样规则)：设置步长 Δ_k = 1/√k，并给出每轮所需样本量 n(k) 和正则化参数 λ(k) 的显式表达式（表1）。例如，在表格设定下，n(k) = O( (∥π_k∥_H^2 k) / (1-cγ)^2 * log(...) + (√k ∥π_k∥_H)^{4/(1+ν)} )。

    • 直觉：随着策略迭代 k 增加，为了达到更小的次优性，需要更精确的策略评估，因此样本量 n(k) 需要增加。策略的RKHS范数 ∥π_k∥_H 也出现在采样规则中，反映了策略本身的复杂度。
    • 技术难点：证明需要将定理9的L2误差通过Gagliardo-Nirenberg型不等式（公式101）提升到L∞误差，以确保定理12中的 ∥f^{(k)} - Q^{(k)}∥_{L∞} 项被控制。

证明路线与技术技巧

  • 整体路线：

    1. 策略评估：将核TD分析分解为统计误差（KRR）和优化误差（梯度下降）。
      • 统计误差：通过误差分解（Proposition 8）将问题转化为控制经验过程项，利用覆盖数假设（Assumption 5）和Geer (2000)的引理（Lemma 18）得到尾概率界，再通过选择最优 λ 得到收敛率（Theorem 16）。
      • 优化误差：证明核TD更新（公式9）是一个线性收缩迭代（公式11），通过选择 α, η 使其谱半径小于1，从而几何收敛到KRR解。
    2. 策略改进：将NPG更新（公式19）视为一个KL-正则化的近端步骤（Lemma 11）。利用性能差异引理（Lemma 22）和KL散度的递推关系，将策略的次优性与策略评估误差和步长联系起来（Theorem 12）。
    3. 耦合：将策略评估的L∞误差界（通过Gagliardo-Nirenberg不等式从L2界导出）代入策略改进的界中，并选择合适的步长和样本量，得到最终的全局收敛率（Corollary 13）。

  • 关键跳跃点：

    • 从经验误差到L2误差：定理9只给出了训练数据上的误差。要得到总体误差（推论10），需要采样不等式（公式79）。这个不等式的形式依赖于RKHS的具体结构（如表格的集中不等式、Sobolev空间的填充距离、高斯核的插值不等式），是连接有限样本分析和泛化性能的桥梁。
    • 从L2误差到L∞误差：定理12需要L∞误差来控制策略更新。这需要Gagliardo-Nirenberg型插值不等式（公式101），它将L∞范数与L2范数和RKHS范数联系起来。这个不等式的具体形式（指数 φ）依赖于RKHS的结构（如Sobolev空间的 φ = (2m-d)/(2m)）。

  • 技术技巧点名：

    • 经验过程理论 (Empirical Process Theory)：用于控制经验均值与总体均值的偏差（Lemma 17, 18）。这是处理统计误差的核心工具。
    • 覆盖数/熵 (Covering Number/Entropy)：用于刻画函数类的复杂度（Assumption 5），是应用经验过程理论的前提。
    • 采样不等式 (Sampling Inequality)：用于从离散样本上的误差推广到连续空间上的误差（公式79）。具体形式因RKHS而异（Proposition 20, 公式83, 87）。
    • Gagliardo-Nirenberg不等式：用于从L2范数界推导L∞范数界（公式101, 105, 106）。
    • 性能差异引理 (Performance Difference Lemma)：将策略的累积奖励差异与Q函数的期望差异联系起来（Lemma 22）。
    • 镜像下降分析 (Mirror Descent Analysis)：用于分析NPG更新，将策略更新视为在概率单纯形上的镜像下降步骤（Theorem 12证明）。

真实例子与应用

  • 数据/场景：使用OpenAI Gym中的经典控制任务 CartPole-v1（4维连续状态，2维离散动作）和 Acrobot-v1（6维连续状态，3维离散动作）。
  • 方法应用：作者用神经网络实例化了算法1中的非参数函数 f^{(k)}，即使用一个两层MLP作为Actor-Critic共享的网络。策略由 Softmax(f_θ) 给出。算法被实现为联合优化TD误差损失和NPG目标。
  • 结果：
    1. 收敛性分析（图1）：验证了步长调度 Δ_k = k^{-α} 的影响。α=0.5（即 1/√k）的调度稳定收敛到最优性能，而 α=0.2（步长衰减过慢）导致发散，α=1.5（步长衰减过快）导致收敛停滞。这直接支持了推论13中 Δ_k = 1/√k 的理论选择。
    2. 运行效率分析（图2）：将本文的NPG（使用单步TD误差）与标准PPO（使用GAE）对比。结果显示，本文的NPG在样本效率（更快达到最优奖励）和计算效率（每秒处理更多状态-动作对，约78.2%的提升）上均优于标准PPO。
  • 例子想说明什么：实验旨在验证理论预测的趋势，而非精确匹配理论常数。具体来说，它展示了步长调度对稳定性的关键作用，以及单步TD更新相比GAE在计算上的优势。作者也诚实地指出了理论与实践的差距，例如在实际中采用了联合优化（而非严格的两阶段过程），并观察到当网络变复杂时，1/√k 调度也会出现性能下降，这与理论中样本量需随 k 增加的预测一致。

🔎 结论是否比证明窄

  • 是。论文的标题和摘要声称分析了“PPO”，但正文中分析的策略更新是KL-正则化的NPG（公式19-20），它等价于一个软max参数化下的自然梯度步骤。虽然这与PPO的裁剪目标在直觉上相关（都是近端更新），但本文并未直接分析PPO的裁剪目标函数。作者在算法1的注释中承认，从NTK视角看，该算法可以“被视为”深度神经网络的演化，但并未给出严格证明。因此，论文的结论严格来说只适用于其提出的“RKHS-NPG”算法，而非通用的PPO算法。
  • 此外，推论13的采样规则依赖于策略的RKHS范数 ∥π_k∥_H，而作者在正文中承认“在NTK情形下，该范数难以估计”。这使得该采样规则在实际中难以直接应用，更像是一个理论上的存在性结果。作者建议使用“网络稳定性和架构”作为“实际代理”，但这并未被理论所覆盖。

四、开放问题

  1. 更紧的下界：本文给出了核TD的上界，但未证明其minimax下界。推论10中的收敛率是否是最优的？对于一般的RKHS，是否存在一个匹配的下界？这扎根于论文的结论部分，其声称的“匹配minimax率（对数项内）”需要更严格的证明。
  2. 放松假设：Assumption 6（P(s'|s,a) ≤ c^2 μ_0(s')）是一个很强的“均匀遍历性”假设。能否将其放松为更弱的混合条件（如几何遍历性）？这扎根于Assumption 6本身及其在收敛率中的关键作用。
  3. 连续动作空间：本文的分析（推论10）主要针对离散动作空间（A = {a}_a=1^A）。将分析扩展到连续动作空间，并处理由此带来的无限维动作值函数估计的挑战，是一个自然的开放问题。这扎根于推论10的四个特例均假设动作空间离散。
  4. Off-Policy分析：本文的分析是on-policy的（每次策略更新后重新采样）。能否将核TD和核NPG的分析扩展到off-policy设定，并处理由此带来的分布偏移问题？这扎根于相关工作部分引用了off-policy评估的核方法（Feng et al., 2020），但本文并未处理off-policy学习。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论