单一步长足以用于无投影线性TD(0)：通过Polyak--Ruppert平均同时实现鲁棒和快速收敛率

# 一个步长足以支持无投影线性 TD(0)：通过 Polyak–Ruppert 平均同时获得鲁棒和快速收敛率  
来源：https://arxiv.org/html/2606.24981  

**Wei-Cheng Lee**  
阿卜杜拉国王科技大学 (KAUST)  
图瓦勒，23955-6900，沙特阿拉伯王国  
[email protected]  

**Francesco Orabona**  
阿卜杜拉国王科技大学 (KAUST)  
图瓦勒，23955-6900，沙特阿拉伯王国  
[email protected]  

###### 摘要  
我们研究了在马尔可夫采样下的线性 TD(0)，其中数据沿单条轨迹生成。我们为一种使用 Polyak–Ruppert (PR) 平均的*无投影*线性 TD(0) 算法提供了高概率保证，该算法采用*单一*步长调度 η_t ∝ 1/(τ_mix log(t) √t)，其依赖于混合时间，但*不需要曲率参数 ω 的先验知识*。我们的第一个结果表明，这种步长选择保证了 TD(0) 迭代自动且一致地有界*具有高概率*，无需投影，也无需基于 ω 的任何稳定性论证。基于这一结果，我们为 PR 平均建立了同时的高概率收敛保证：相同的步长既能产生鲁棒的、与曲率无关的 Õ(τ_mix/√T) 收敛率，也能产生快速的、依赖于曲率的 Õ(τ_mix²/(ωT)) 收敛率，且最终边界取两者中的最小值。核心技术要素是一套适用于几何混合马尔可夫链的泊松方程工具包，它将马尔可夫噪声分解为鞅项加上可控余项，并实现了一种新的自边界归纳论证来保证路径稳定性。  

**关键词：** 强化学习，时序差分学习，有限时间分析，马尔可夫噪声，随机逼近  

## 1 引言  

时序差分 (TD) 学习是强化学习的核心算法原语之一，用于策略评估，并作为 Actor-Critic 等控制方法的基础模块。当状态空间很大时，TD 通常与函数逼近结合使用；在线性情况下，由此产生的 TD(0) 迭代可以看作是一种干净的随机逼近形式，并且在标准条件下渐近收敛 (Sutton, 1988; Tsitsiklis and Van Roy, 1996; Kushner, 2010)。然而，尽管有这些经典理论，为 TD(0) 获得*有限时间*、*高概率*的保证仍然具有挑战性，尤其是在实际相关的*马尔可夫采样*机制下（数据沿单条轨迹生成）。一个主要障碍是 TD(0) 并非标准的随机梯度方法：即使在线性设定下，其更新通常是有偏的、非对称的，且噪声在时间上是相关的。此外，TD(0) 更新的幅度取决于迭代量的幅度。因此，现有的非渐近分析依赖于额外的结构来控制迭代量。一种常见的方法是通过*投影*到已知球体上来强制有界性（例如，Bhandari 等, 2018），这简化了集中论证，但改变了算法，并且需要*先验*知道合适的半径（通常隐式地与问题曲率相关）。第二种方法是利用均值动力学的*收缩/曲率*结构来论证无投影下的稳定性；然而，这通常会产生依赖于未知曲率参数的步长条件或稳定性边界，当曲率任意小时，收敛会变得任意慢。理想情况下，我们希望使用*单一*步长规则，该规则可以*同时*获得 (i) *鲁棒*（与曲率无关）的收敛率和 (ii) 当曲率有利时*快速*的收敛率。这样的步长应该能够自适应地取鲁棒和快速高概率上界中的较优者，而无需曲率的先验知识。  

#### 鲁棒与快速收敛率。  

为了解释鲁棒收敛率和快速收敛率之间的区别，我们首先简要描述我们研究的势函数 (Ollivier, 2018; Liu and Olshevsky, 2021)（将在后面的公式 (2) 中正式引入），它自然地捕捉了马尔可夫采样下 TD 的固定点误差。该势函数总是具有正曲率 ω > 0，因此人们可以期望达到 Õ(1/(ωT)) 量级的“快速”收敛率（Õ 表示忽略对数因子）。另一方面，即使没有曲率假设，也总能达到 Õ(1/√T) 量级的“鲁棒”收敛率（同样忽略混合和对数因子）。显然，在有限时间范围内，哪种收敛率更好取决于 ω，因此在不同情况下两种收敛率都值得追求。  

目前，先前的工作通常通过*不同*的步长选择和额外的算法修改来实现这两种收敛率（例如，Bhandari 等, 2018）。此外，据我们所知，在马尔可夫噪声下无投影的高概率分析依赖于稳定性论证，其常数随 ω 恶化（例如，Samsonov 等, 2024; Durmus 等, 2025）。据我们所知，*对于 TD(0)，使用单一、与 ω 无关的步长选择，同时以高概率获得两种收敛率且无需投影，此前尚未建立*。具体来说，实现这一结果的关键技术难点在于*沿路径*控制随机迭代量 θ_t。没有投影，更新幅度与 ||θ_t|| 成比例，简单的集中分析会变得循环：为了界定量误差，我们需要有界的更新，但需要有界的更新又需要迭代量有界。此外，获得鲁棒收敛率（即与 ω 无关）的需求排除了任何通过基于 ω 的收缩论证来证明迭代量有界的策略。  

#### 我们的方法：通过泊松方程的自边界论证。  

在本文中，我们证明了一个简单的步长，与 1/(τ_mix log t √t) 成正比且与 ω 无关，能够保证 TD(0) 以高概率同时实现快速和鲁棒收敛率。我们解决上述问题的主要技术新颖之处在于一种新的*自边界*论证，该论证*以高概率*闭合了这个循环，*无需*诉诸曲率 ω，也*无需*人为投影。具体来说，我们为几何混合马尔可夫链开发了一套泊松方程工具包，该工具包将加性马尔可夫噪声分解为一个鞅项加上一个可控余项。这种分解使我们能够控制 TD 基本势展开中出现的马尔可夫偏置项，并运行一个归纳论证，其中在时间 ≤ t-1 的有界性蕴含着在时间 t 的有界性。由此产生的关于 sup_t ||θ_t|| 的一致界以高概率成立，并且与曲率 ω 无关。  

一旦建立了有界性，我们就可以分析收敛保证。有界迭代事件提供了必要的前提，通过泊松分解再次控制鞅项的二次变差，从而为平均迭代量 θ̄_T 提供高概率边界。重要的是，*相同*的步长提供：  

- • 一个与曲率无关的鲁棒收敛率 Õ(1/√T)，通过类似平均随机梯度下降的分析得到，正如从步长选择中预期的那样；  
- • 一个依赖于曲率的快速收敛率 Õ(1/(ωT))，通过 Polyak–Ruppert 平均分析实现，无需 ω 来设置步长。  

## 2 相关工作  

在本节中，我们简要概述线性函数逼近下 TD 学习收敛保证的主要结果，以及我们证明中使用的主要工具。稍后在第 5 节中，我们将给出关于收敛率的详细比较。  

线性函数逼近下 TD 学习的早期收敛结果可以追溯到 Tsitsiklis 和 Van Roy (1996)，他们通过随机逼近的视角解释了 TD 更新 (Kushner, 2010)。然而，该理论主要是渐近的，并未给出显式的非渐近收敛率。有限时间保证随后在一系列工作中得到发展 (Korda and La, 2015; Lakshminarayanan and Szepesvári, 2018; Dalal et al., 2018)，但这些分析通常假设样本是从平稳分布中独立同分布 (i.i.d.) 抽取的。这一假设回避了大多数强化学习流程中存在的时序依赖性，在强化学习中，数据是沿着单条马尔可夫链轨迹顺序生成的。考虑这种马尔可夫相关性会大大增加分析的复杂性，即使对于 TD(0) 也是如此。  

Bhandari 等人 (2018) 的开创性工作首次提供了在马尔可夫采样下的有限时间处理。他们使用两种不同的步长，同时获得了快速和鲁棒的收敛率。然而，他们的论证（甚至是后续对鲁棒收敛率的改进，如 Liu 和 Olshevsky (2021)）依赖于一个显式的投影步骤来保持迭代量可控。在快速收敛率机制下，后续工作通过利用更新由于曲率而具有的收缩性质，移除了对投影的需求。特别是，Srikant 和 Ying (2019) 使用控制理论框架，通过 Lyapunov 理论建立了类似收缩的行为，从而在不使用投影的情况下推导出线性 TD 在马尔可夫数据下的有限时间误差界。然而，他们的步长依赖于势函数的曲率，这在实践中通常是未知的。沿着这一方向，Patil 等人 (2023) 通过引入一种数据丢弃的 TD 修改，消除了在选择步长时了解曲率参数的需求。  

相关进展也集中在简化证明和放松算法修改上：Mitra (2025) 提出了一种简化的归纳两步分析，Li 等人 (2026) 使用指数衰减步长来避免数据丢弃，Sun 等人 (2022) 将快速收敛率分析扩展到 NTK 机制下的神经网络。最近，Samsonov 等人 (2024) 强化了 Patil 等人 (2023) 的分析，并获得了无投影的高概率边界。与这一高概率无投影路线最接近的是 Chandak 和 Borkar (2025)，他们为无丢弃的无投影 TD(0) 获得了全时高概率控制。然而，他们的分析本质上仍然是收缩性的，并且得到的常数和启动时间依赖于曲率。  

唯一一个使用与势函数曲率无关的步长且无需在分析中使用曲率，就移除了对投影需求的结果来自 Lee 和 Orabona (2025)，他们证明了 TD(0) 的迭代量在期望上有界。我们的方法受到他们方法的启发，但有很大不同，因为我们要求高概率边界。  

有几个密切相关的工作研究了廉价线性更新方法，这些方法具有参考价值，但不是纯 TD(0) 的直接基准。Raj 等人 (2022) 分析了线性组合优化和用于离策略 MSPBE 最小化的梯度 TD 方法，使用原始-对偶更新而非此处研究的半梯度 TD(0) 迭代，并获得了自适应有限时间保证，但要求迭代量有界或曲率的先验知识。在表格化设定下，Li 等人 (2020) 表明异步 Q 学习（因此包括表格化 TD）的主导统计项可以匹配 i.i.d. 采样的复杂度，混合仅作为加性瞬态成本进入；他们还提供了数据驱动的步长，避免了 τ_mix 的先验知识。这些结果解决了在有限调参信息下获得快速、稳定、廉价线性更新的相同广泛实际问题，但它们并不直接适用于无投影的线性 TD(0)。  

据我们所知，之前没有工作分析线性 TD 学习能否使用独立于曲率且无投影的步长调度同时获得快速和鲁棒收敛率。  

Polyak–Ruppert 平均在 TD 学习分析中的应用至少可以追溯到 Konda (2002)。据我们所知，Korda 和 La (2015) 是第一个利用这一技术建立有限时间保证的工作。特别是，Polyak–Ruppert（尾部）平均已被用于允许步长选择避免显式依赖于曲率参数 ω（参见，例如，Lakshminarayanan 和 Szepesvári, 2018; Patil 等, 2023; Samsonov 等, 2024）。  

最后，我们利用泊松方程来获得高概率界。这是一个标准工具，在 TD 学习和具有马尔可夫噪声的随机逼近文献中被广泛使用（参见，例如，Chandak 和 Borkar, 2025; Blaser 和 Zhang, 2024）。  

## 3 设置与假设  

我们直接处理由固定策略 μ 诱导的有限折扣马尔可夫奖励过程 (MRP)。因此，动作变量已经在 μ 下被平均。设 S ≔ {1, …, n} 为有限状态空间，设 P^μ: S × S → [0, 1] 为诱导的转移核，设 r: S × S → R 为单步奖励函数。给定初始状态 s_0，状态过程满足 P(s_{t+1}=j | s_t=i) = P^μ(i, j) 对于 i, j ∈ S。我们将 P^μ ∈ R^{n×n} 记为相应的转移矩阵，其元素为 P^μ(i, j) = P^μ(i, j)，并固定折扣因子 0 < γ < 1。我们关心在