🤖 machine learning

A Banach-Space Theory of Markovian Halpern Iteration for Non-Expansive Maps

本文引入了一种方差缩减的马尔可夫 PAGE-Halpern 方法，用于寻找一般有限维巴拿赫空间中非扩张算子的不动点，通过利用泊松方程分析和范数平滑技术，实现了 $\tilde O(\epsilon^{-3})$ 的样本复杂度以及高概率保证。

原作者： Ege C. Kaya, Arda Fazla, M. Berk Sahin, Abolfazl Hashemi

发布于 2026-08-18

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Ege C. Kaya, Arda Fazla, M. Berk Sahin, Abolfazl Hashemi

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

在计算机学习的世界里，机器经常试图通过不断猜测并自我修正来寻找一个稳定的答案。想象一下，一名登山者正试图在浓雾中寻找山谷的底部。如果地面坡度平缓且持续向下，登山者只需沿着最陡峭的下降方向行走，最终就能到达谷底。这就是许多学习算法在处理简单问题时的运作方式：每一步都让他们离唯一的解更近一步。然而，许多现实世界的学习任务并不像一个简单的山谷。有时地面是平坦的，或者有许多不同的低洼处，或者前进的路径被无法消散的噪声所阻挡。在这些困难的情况下，标准的“持续向下走”的方法可能会陷入停滞或漫无目的地徘摆。为了解决这个问题，数学家开发了一种特定的策略，称为 Halpern 迭代。这种方法不仅仅是对即时坡度的反应，它还始终保持着一个固定的参考点——一个起始锚点——并不断将当前的猜测拉回到这个锚点。这种记住起点的方法帮助算法在平坦或复杂的地形中导航，并保证它最终会稳定在一个特定的、正确的答案上。

挑战在于计算机接收到的信息并不完美。在许多实际应用中，比如训练机器人走路或让程序玩游戏，数据来自于一个连续的、移动的事件序列，而不是一份干净的、随机的事实列表。这被称为马尔可夫轨迹（Markovian trajectory），其中下一个信息高度依赖于前一个信息。当研究人员尝试将 Hal了策略应用于这种带有噪声且具有依赖性的数据时，他们发现它确实有效，但速度极其缓慢。为了获得精确的答案，计算机必须处理海量的数据，这使得该方法在处理复杂问题时变得不切实际。本研究中的研究人员旨在解决这个速度问题，同时又不损失该方法的可靠性。他们想知道，是否可以通过让算法更聪明地利用已有的数据，特别是在数据来自单一且连续的事件流时，来提高效率。

团队发现，通过改变算法估计下一步的方式，他们可以显著减少所需的数据量。他们设计了一个系统，不再将每一条新信息都视为一个全新的开始，而是观察使用完全相同的一条数据所做出的两个非常相似的猜测之间的差异。这就像是在检查你的速度：如果你知道某一时刻的速度以及一瞬间之后的速度，你就可以计算出加速度，而无需知道你在地图上的确切位置。通过专注于这些微小的变化，而不是每次都从头开始构建整个图景，算法的学习速度可以大大加快。研究人员在数学上证明了，这种他们称之为“方差缩减”（variance-reduced）的方法，能够让计算机以比以前少得多的数据点达到精确的答案。

这种改进之所以意义重大，是因为它即使在数学规则非常复杂、不遵循标准山谷那种简单、平滑几何结构的情况下依然有效。在许多高级学习任务中（例如涉及最大值或特定类型平均值的任务），规则是“非平滑”的，这意味着地面可能存在会导致标准方法产生困惑的锐利边缘或平坦区域。研究人员展示了他们的新技术在这些困难的、锯齿状的环境中同样有效。他们证明，通过以一种尊重这些锐利边缘的方式来衡量算法的进展，该方法能保持稳定和高效。这是一个至关重要的进步，因为这意味着该理论可以应用于机器人技术和游戏 AI 中那些混乱的现实问题，在这些领域中，规则通常是由最大值和最小值定义的，而非平滑曲线。

为了测试他们的想法，研究人员使用一个关于机器人在一个小型八状态世界中移动的简单模型进行了模拟。他们将这种新的快速方法与旧的慢速方法进行了对比。在测试中，新方法在使用的步骤显著减少的情况下达到了预期的准确度水平。在一种场景下，旧的方法未能能在规定时间内达到高精度，而新方法每次都成功了。在另一个更困难的、“移动缓慢”的环境测试中，新方法所需的数据仅为旧方法的一小部分。结果证实，重复使用同一数据点来测量变化这一策略不仅是一个理论上的技巧，更是让学习算法变得高效的实用方法。

这项研究还解决了计算机科学中的一个常见担忧：如何确保算法能够可靠地工作，而不只是在平均意义上有效。在现实世界中，一次倒霉的坏数据运行就可能导致标准算法失败。研究人员证明，他们的这种方法提供了一个强有力的保证，即算法即使在存在噪声的情况下也能以极高的概率取得成功。他们通过使用一种特殊的数学工具，在不改变计算机试图解决的实际问题的前提下，将数据的粗糙边缘进行了适度的平滑处理，从而使分析成为可能。这确保了快速性能并非偶然，而是该方法的一个一致特征。

最终，这项工作弥合了优雅的数学理论与连续数据流的混乱现实之间的鸿沟。它表明，通过仔细分析误差是如何累积的，并利用数据流本身的结构，我们可以构建出既稳健又高效的学习系统。研究结果表明，对于数据来自持续流动的问题（例如监控传感器或实时进行游戏），无需等待海量数据即可获得良好的答案。通过正确的方法，计算机可以从单一的、持续进行的旅程中进行有效的学习，这使得解决以前因速度太慢或不稳定而难以处理的复杂问题成为可能。

技术摘要：针对非扩张映射的马尔可夫型 Halpern 迭代的 Banach 空间理论

1. 问题陈述

本文研究了当预言机（oracle）采样的来源是一个持续的马尔可夫轨迹时，针对非扩张算子 $T$ 的随机逼近问题。与收缩算子不同，非扩张算子的不动点并不唯一，且误差不会呈几何级数衰减。

具体设置涉及一个生成算子 $H(x, y)$ 样本的马尔可夫链 $(Y_t)_{t \ge 0}$ ，其中平均算子 $Tx = \mathbb{E}_\pi[H(x, Y)]$ 在有限维范数空间 $(\mathbb{R}^d, \|\cdot\|)$ 中是非扩张的。目标是寻找一个近似不动点 $x$ ，使得 $\|x - Tx\|$ 足够小，且使用单一、不间断的马尔可夫轨迹。分析必须考虑到马尔可夫误差的鞅分量以及在块边界处的条件偏差，且不假设链在迭代之间进行重启或达到平稳分布。

2. 方法论

2.1 基准：马尔可夫块 Halfern 迭代

作者首先分析了直接的块小批量（block-minibatch）实现 Halpern 迭代的方法。给定锚点 $x_0$ 和步长 $\beta_n = n/(n+1)$ ，更新公式为：
$x_n = (1-\beta_n)x_0 + \beta_n G_n$
其中 $G_n$ 是从马尔可夫链中收集的 $k_n$ 个样本的块平均值。

分析： 利用扰动级界限，作者表明，为了使期望最后迭代残差达到 $O(\log N / N)$ 阶，块大小必须按 $k_n \sim n^4$ 增长，以控制马尔可夫偏差和方差。
复杂度： 这导致样本复杂度为 $\tilde{O}(\epsilon^{-5})$ 。

2.2 方差缩减：马尔可夫 PAGE-Halpern

为了提高样本复杂度，本文引入了一种基于 PAGE（概率自适应梯度估计器）框架的方差缩减方法，并将其适配于马尔可夫轨迹。

机制： 算子值（即 $Tx_n$ 或 $F(x_n) = (I-T)x_n$ ）的估计量 $v_n$ 通过递归方式更新。在每次迭代中，以概率 $p_n$ ，一个“刷新块”（refresh block）重新估计当前点的算子值。以概率 $1-p_n$ ，一个“差异块”（difference block）使用相同的马尔可夫状态来评估两个连续查询点（ $x_n$ 和 $x_{n-1}$ ）的算子值，从而估计差值 $Tx_n - Tx_{n-1}$ （或 $F(x_n) - F(x_{n-1})$ ）。
泊松分解： 分析依赖于马尔可夫噪声的泊松方程分解。这使得作者能够在不丢弃烧入（burn-in）段的情况下控制块平均值的条件偏差和二阶矩，将边界项视为 $O(k^{-1})$ 。

2.3 Hilbert 空间 vs. Banach 空间方法

方法论根据空间的几何性质而有所不同：

Hilbert 空间： 作者利用了 $F = I - T$ 的协同收缩性（cocoercivity）。在 Hilbert 空间中，非扩张性意味着 $F$ 是单调且 $1/2$ -协同收缩的。这使得固定点残差 $\|x - Tx\|$ 可以通过算子范数 $\|F(x)\|$ 直接控制，从而能够使用标准的 PAGE 残差界限。
Banach 空间： 在一般的 Banach 空间（例如在强化学习中常见的 $\ell_\infty$ 或块上确界范数）中，内积结构和协同收缩性是不存在的。作者引入了一个位移级界限（displacement-level bound）。他们不是估计 $F(x)$ ，而是直接估计 $T$ 。其收敛分析依赖于控制缩放后的 Halpern 位移（ $\Delta_n = \beta_n U_n - \beta_{n-1} U_{n-1}$ ）在原始非扩张范数下的增量。这避免了对隐藏内积几何的需求。

2.4 高概率保证

为了在非光滑 Banach 空间中建立高概率界限，作者采用了一个辅助光滑范数 $\|\cdot\|_s$ 。递归估计量在这一光滑范数下受控（此处满足鞅集中不等式），然后通过范数比较常数将其映射回工作范数。这处理了上确界范数（sup-norms）的非光滑性，同时不改变固定点几何结构。

3. 核心贡献

扰动与位移界限： 作者证明了两类不精确 Halpern 残差界限。第一类使用预言机误差的大小（适用于块方法），第二类使用缩放误差的增量（对于方差缩减的 PAGE 方法至关重要）。
马尔可夫块基准： 他们确定了块小批量 Halpern 方法可以实现 $O(\log N / N)$ 的期望残差，但其样本复杂度为 $\tilde{O}(\epsilon^{-5})$ 。
Hilbert 空间 PAGE-Halpern： 他们利用刷新块和相同状态差异块，为 Hilbert 空间构建了 PAGE-Halpern 方法。通过利用泊松方程和协同收缩性，他们在无需重启链的情况下实现了 $O(\epsilon^{-3})$ 的样本复杂度。
Banach 空间扩展： 其主要的理论贡献是将 PAGE 构建扩展到一般的有限维 Banach 空间。通过将分析从算子 $F=I-T$ 转向 $T$ 的位移，他们在原始非扩张范数下实现了 $\tilde{O}(\epsilon^{-3})$ 的样本复杂度，涵盖了上确界及块上确界几何。
高概率保证： 他们通过在辅助光滑范数中衡量估计量，提供了 Banach 结果的高概率界限，显示出其领先的精度依赖关系仅具有对数维度的依赖。

4. 结果

理论复杂度

基准： $\tilde{O}(\epsilon^{-5})$ 样本。
PAGE-Halpern (Hilbert)： $O(\epsilon^{-3})$ 样本。
PAGE-Halpern (Banach)： $\tilde{O}(\epsilon^{-3})$ 样本。
从 $\epsilon^{-5}$ 到 $\epsilon^{-3}$ 的改进趋近于已知的 $\Omega(\epsilon^{-3})$ 线性跨度预言机模型的下界，尽管论文指出该下界适用于比 PAGE 使用的多点访问更弱的特定预言机模型。

实验验证

作者使用基于 8 状态马尔可夫链的两个受控示例验证了理论：

Hilbert 情况（策略评估）： 欧几里得范数下的线性非扩张算子。
Banach 情况（平均奖励控制）： 涉及极大化步骤的非线性算子，仅在上确界范数下是非扩张的。

发现：

在快速混合和慢速混合场景下，PAGE-Halpern 方法的表现均显著优于块 Halpern 基准。
对于 Banach 控制问题，Banach PAGE 方法在每个重复实验的预算内都能达到 0.05 的残差，而块方法在 20 次重复中仅成功了 8 次。
实验证实，随着目标精度提高或链的混合时间增长，相同状态的差异变得越来越有价值，因为它们避免了从头重建算子值的极高成本。

5. 意义与主张

本文声称提供了一个由单一持续马尔可夫轨迹驱动的随机 Halpern 迭代的有限样本理论。其意义在于：

弥合几何差距： 它将方差缩减固定点迭代从 Hilbert 空间扩展到一般的 Banach 空间，特别解决了强化学习和分布强化学习中盛行的非光滑几何（上确界范数）问题。
处理马尔可夫依赖： 它通过泊松方程显式地考虑了马尔可夫误差的条件偏差和鞅分量，避免了对平稳性假设或链重启的需求。
实际效率： 结果表明，结合了 Haling 锚定与相同状态方差缩减的方法，在自然的 RL 几何结构中提供了鲁棒的最后迭代保证，与块方法相比，在转换效率上实现了数量级的提升。
明确的信息结构： 该工作阐明了所需的信息结构，包括迭代的稳定性、基于泊松的偏差控制，以及重用单个马尔可夫状态进行多点预言机查询的能力。

作者谦虚地指出，虽然其 $\tilde{O}(\epsilon^{-3})$ 的上界在阶数上匹配了特定预言机模型的已知下界，但该下界并不构成对其特定的多点信息模型的匹配极小极大（minimax）陈述。然而，该构造提供了一个具体的、可实现的在线程序，实现了这种改进的速率。