📊 statistics

A Robust $\widetilde{\mathcal{O}}(1/\sqrt{T})$ Rate for Unprojected TD Learning with Linear Function Approximation

本文通过证明在马尔可夫噪声下，未投影的线性函数逼近 TD(0) 学习能够实现鲁棒的 $\widetilde{\mathcal{O}}(1/\sqrt{T})$ 收敛速率，且无需要求迭代有界或额外的正则性条件，而是依赖于一种新颖的更新自界定性质，从而解决了一个开放问题。

原作者： Wei-Cheng Lee, Francesco Orabona

发布于 2026-06-09

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Wei-Cheng Lee, Francesco Orabona

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大局观：没有安全网的学习

想象一下，你正在通过试错法来学习一项新技能，比如玩电子游戏或走迷宫。在人工智能领域，这被称为强化学习（Reinforcement Learning）。实现这一目标最常用的工具之一叫做 TD 学习（TD Learning，时序差分学习）。

把 TD 学习想象成一个正在做笔记的学生。每当学生做出一次移动，他们就会比较自己以为会发生的情况与实际发生的情况。然后，他们会调整自己的笔记（即他们的“模型”），以便下次能更准确。

长期以来，数学家们一直知道这个学生最终可以完美地学会游戏。然而，用于证明这一点的数学理论中存在一个大问题：

“安全网”问题： 为了证明这个学生不会发疯并写下不可能出现的数字，之前的理论需要一个“安全网”。这意味着数学上假设学生的笔记被强制保持在一个特定的、预定义的框内。如果笔记试图变得太大，数学就会直接将其切掉并强行压回框内。
现实世界的问题： 在现实生活中，没有人使用这种“安全网”。我们只是让学生自然地学习。
开放性问题： 多年来，研究人员一直在问：“我们能否证明这个学生在没有这种人工安全网的情况下，依然能学得很好且保持理智？”之前的尝试给出的回答是：“不行，除非我们对游戏的结构增加一些额外的、非常严格的规则。”

这篇论文说：“是的，我们可以。”

作者们证明了，这个学生（算法）在不需要安全网或额外严格规则的情况下，能够自然地保持在一个安全的范围内。他们证明了即使在数据杂乱且相互关联（就像一个动作会影响下一个动作的真实游戏）的情况下，该方法的学习速度也几乎达到了最优水平。

核心概念详解

1. “安全网”（投影/Projection）

在旧的数学理论中，为了证明算法不会爆炸，研究人员不得不假装在数字过大时对其进行物理上的裁剪。

类比： 想象一名登山者试图寻找山谷的底部。旧的数学理论说：“我们可以证明登山者不会掉下悬崖，但前提是我们要想象有一个神奇的栅栏挡住他们，不让他们走下边缘。”
论文的突破： 作者证明了登山者之所以能自然地留在路径上，是因为他们走路的方式，而不需要一个神奇的栅栏。

2. “曲率”陷阱

其他一些方法试图通过假设他们所处的山谷是非常陡峭且呈碗状（数学上称为“强凸”）来避开安全网。

类比： 如果山谷是一个完美的、陡峭的碗，那么很容易证明你会滚向底部。但如果地面是平坦的，或者有奇怪的凸起呢？
问题所在： 如果地面是平坦的（这在现实数据中经常发生），那些依赖“陡峭碗状”的方法会变得极其缓慢甚至完全失效。
论文的解决方案： 他们的算法无论是在陡峭的碗里还是在平坦的平原上都能工作。它是“鲁棒的（Robust）”，意味着它不依赖于地面具有特定的形状。

3. “自约束”的魔力

他们是如何证明在没有栅栏的情况下数字不会爆炸的？他们发现了一个被称为**自约束（Self-bounding）**的隐藏属性。

类比： 想象一根橡皮筋。如果你把学生的笔记拉离真相太远，那股“学习力”就会自然地将它们拉回。这就像算法自带一个内部指南针，只要你给予适当的“推力”（学习率），它就能防止自己偏离航道太远。
诀窍： 作者发现，如果通过添加一点点对数修正（一个非常小的数学微调）来稍微调整“推力”（学习率），算法就能自然地自我约束。

4. “噪声”数据

在现实生活中，数据不是随机的，而是相互关联的。如果你今天看到一只狮子，明天看到狮子的可能性就会增加。这被称为马尔可夫噪声（Markovian noise）。

类比： 这就像是在学习天气。如果现在在下雨，之后很可能也会下雨。这创造了一种依赖链，使得学习变得更加困难。
结果： 作者证明，即使在这种相互关联、带有噪声的数据下，他们的算法依然有效，且不需要知道天气模式到底有多“粘滞”。

他们究竟做了什么？

移除了栅栏： 他们分析了算法的“未投影（Unprojected）”版本（即没有安全网的版本）。
找到了速度： 他们证明了该算法的收敛（学习）速度大约为 1 除以时间的平方根 ( $1/\sqrt{T}$ $1/ T$ )。
- 注：这比那些依赖“陡峭碗”假设的“快速”方法稍慢，但它更加可靠，因为它在“碗”是平坦的时候依然有效。
无需额外规则： 他们不需要添加任何额外的“正则性条件”（关于数据的额外严格规则）。
学习率： 他们表明，只需通过添加一个微小的对数因子来稍微改变学习率公式，就足以保证算法保持稳定。

一句话总结

这篇论文解决了一个长期的谜题，它证明了通过稍微调整学习速度，一种流行的 AI 学习方法无需人工安全网或假设数据具有完美形状，也能保持稳定并高效学习。

技术摘要：无投影 TD 学习具有鲁棒的 $O(1/\sqrt{T})$ 收敛速率

问题陈述

带有线性函数逼近的时差（TD）学习是强化学习中策略评估的基础算法。虽然渐近收敛性已得到充分理解，但在现实条件下（即数据由马尔可夫链生成而非独立采样，即存在马尔可夫噪声）建立有限时间收敛速率仍然具有挑战性。

目前存在一个关键的理论差距，即关于“鲁棒”收敛速率 $O(1/\sqrt{T})$ 的研究。先前建立该速率的工作（例如 Bhandari 等人，2018）依赖于一个人工的投影步骤，即将迭代值强制限制在一个有界集合内以防止发散。这种投影在实践中很少使用，并且需要预先知道最优解 $\theta^*$ 的一个界限，而这通常是无法获得的。相反，“快”收敛速率 $O(1/T)$ 虽然存在于无投影 TD 学习中，但它们依赖于势函数最小曲率（ $\omega$ ）的平方倒数。由于 $\omega$ 可能任意小（在病态问题中），这种快速速率在非渐近机制下可能会显著退化。

Bhandari 等人 (2018) 提出的开放性问题是：无投影 TD(0) 是否可以在不引入额外正则性条件或人工投影的情况下，实现鲁棒的 $O(1/\sqrt{T})$ 速率。

方法论

作者分析了在马尔可夫采样下带有线性函数逼近的标准无投影 TD(0) 算法。其方法从根本上区别于以往依赖于收缩性质或人工投影的分析。

1. 势函数选择

作者没有使用标准的 $D$ -范数距离 $\|V_{\bar{\theta}_T} - V_{\theta^*}\|_D^2$ ，而是采用了 Liu 和 Olshevsky (2021) 提出的势函数：
$f(\theta) := (1 - \gamma) \|V_\theta - V_{\theta^*}\|_D^2 + \gamma \|V_\theta - V_{\theta^*}\|_{\text{Dir}}^2$
该势函数的优势在于：

即使当折扣因子 $\gamma \to 1$ 时，它依然保持良好行为。
平稳更新场 $\bar{g}(\theta)$ 满足等式 $\langle -\bar{g}(\theta), \theta - \theta^* \rangle = f(\theta) - f(\theta^*)$ ，这使得分析过程比其他工作中使用的不等式更加简化。

2. 通过归纳实现的自限制属性

核心技术贡献是 TD 更新的一个新颖的自限制属性（self-bounding property）。作者证明了，只要步长选择得当，在不投影迭代值的情况下，序列 $\{\theta_t\}$ 在期望意义下会围绕最优解 $\theta^*$ 保持有界。

步长设计： 步长定义为 $\eta_t = \frac{1}{c \phi_\infty^2 \log(T) \log(t+3) \sqrt{t+1}}$ ，其中常数 $c$ 满足 $c > 15 + 18\sqrt{2}$ 。
归纳论证： 证明过程通过归纳法进行。假设迭代在时间 $t-1$ 时是有界的，作者展示了时间 $t$ 的更新仍将保持有界。这依赖于将更新分解为一个鞅差序列（噪声）和一个偏差项。
处理马尔可夫噪声： 为了解决马尔可夫相关性带来的偏差（即 $E[g(\theta, Z_t) | \mathcal{F}_{t-1}] \neq \bar{g}(\theta)$ ），作者利用了底层马尔可夫链的几何混合特性（定理 3.2）。他们通过将当前状态分布与滞后 $k'$ 后的平稳分布联系起来，并利用衰减率 $\alpha^k$ 来限制偏差。

3. 有界性分析

作者证明了迭代值满足：
$E[\|\theta_t\|^2] \leq \rho_c^2 \max\left(\frac{r_\infty^2}{\phi_\infty^2}, \|\theta^*\|^2\right)$
其中 $\rho_c$ 是取决于步长参数 $c$ 的常数。这种有界性是在没有投影迭代值的情况下实现的，从而有效地完成了归纳循环。

关键结果

理论保证

定理 4.2： 对于使用指定步长的无投影 TD(0) 生成的加权平均迭代值 $\bar{\theta}_T$ ，其迭代值的期望平方范数被一个与混合时间及曲率 $\omega$ 无关的常数所限制。

推论 4.3： 该算法实现了收敛速率：
$f(\bar{\theta}_T) - f(\theta^*) = \tilde{O}\left( \frac{c \rho_c^2 \max\{r_\infty^2, \phi_\infty^2 \|\theta^*\|^2\}}{\sqrt{T}} \right)$
至关重要的是， $\tilde{O}$ 符号中的隐藏常数取决于 $\|\theta^*\|$ 和特征界限，但不依赖于最小曲率 $\omega$ 或混合时间 $\alpha$ （除了步长条件中一个微小的多项式对数修正）。

与先前工作的比较

对比投影鲁棒速率： 与 Bhandari 等人 (2018) 不同，本研究移除了投影步骤以及预知 $\theta^*$ 界限的要求。该速率具有可比性（ $\tilde{O}(1/\sqrt{T})$ ），但无需人工约束即可实现。
对比无投影快速速率： 与 Srikant 和 Ying (2019) 以及随后取得 $O(1/T)$ 速率的工作不同，本结果不依赖于未知的曲率参数 $\omega$ 。作者通过一个反例证明了 $\omega$ 可以任意小，使得快速速率在实际中可能变得极其缓慢，而鲁棒速率则保持稳定。

意义与主张

本文声称解决了 Bhandari 等人 (2018) 提出的一个特定开放问题：即为带有线性函数逼近的无投影 TD(0) 提供一个能够实现鲁棒收敛速率的有限时间分析。

消除人工假设： 本工作表明，此前被认为对于鲁棒分析是必要的投影步骤实际上并非必需。当步长随对数因子适当缩放时，迭代的有界性会自然地从算法动力学中显现。
无需额外正则性： 该结果在不假设问题结构具有额外正则性（除标准的不可约性、非周期性和特征全列秩之外）的情况下依然成立。
实际相关性： 作者强调，虽然理论上使用投影是为了简化证明，但在实践中并不使用投影。本分析弥合了理论保证与实际算法设计之间的鸿沟。
稳定性阈值： 论文确定了步长常数 $c$ 的一个阈值（具体为 $c > 15 + 18\sqrt{2}$ ）作为稳定性充分条件。在合成数据上的实验结果表明，该阈值捕捉到了真实的有限时间稳定性效应；如果 $c$ 过小，迭代将会发散。

作者指出，关于 $c$ 的阈值是一个基于证明常数（三角不等式、柯西-施瓦茨不等式、积分测试）得出的保守充分条件，并不一定是紧凑的实际调优规则。此外，要求 $T$ 相对于混合时间 $\alpha$ 足够大这一限制，是所有关于鲁棒界限文献共同面临的问题，尽管作者更倾向于采用一种可执行的假设呈现方式，而非需要预知未知混合参数的“随时（anytime）”形式。