📊 statistics

Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis

本文介绍了鲁棒 Halpern 迭代（Robust Halpern Iteration, RHI），这是一种用于鲁棒平均奖励强化学习的模型无关算法，该算法利用一种新型的多层蒙特卡洛估计器，在各种不确定性模型下，为寻找 $\varepsilon$ -最优策略实现了最先进的有限样本复杂度。

原作者： Zachary Roch, George Atia, Yue Wang

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Zachary Roch, George Atia, Yue Wang

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

核心理念：“从模拟到现实”的问题

想象你正在训练一个机器人走路。你在一个完美的、无摩擦的视频游戏模拟器中教它。在游戏中，它学得走路非常完美。但当你把它放到现实世界时，地板很滑，风在吹，机器人摔倒了。

这就是 “从模拟到现实”（Sim-to-Real）的差距。机器人的训练环境（模拟器）与现实世界并不匹配。

大多数标准的 AI 训练都假设世界与所教的内容完全一致。而这篇论文探讨了一种不同的方法：鲁棒强化学习（Robust Reinforcement Learning）。这种方法不是寄希望于世界保持不变，而是教 AI 为最坏的情况做好准备。它在问：“这个环境最糟糕的版本是什么样的，我该如何在这种情况下表现得最好？”

具体挑战：“长线游戏”

这篇论文关注一种特定类型的奖励，称为平均奖励（Average-Reward）。

折扣奖励（旧方法）： 想象你在玩一款视频游戏，今天的得分价值 100%，明天的得分价值 99%，后天的价值 98%。这会让 AI 变得“近视”（短视）。它更在意眼前的分数，而不是长期的生存。
平均奖励（新方法）： 这是为了“长线游戏”设计的。想想出租车司机。他们不在乎第一小时赚了 100 美元还是第二小时赚了 0 美元；他们在乎的是一整年里的平均收入。这篇论文教 AI 如何最大化这种长期平均值，即使环境充满变数。

现有方法的问题

作者指出了现有解决方案的两个主要问题：

它们需要一张地图（基于模型/Model-Based）： 许多方法要求 AI 首先构建一个完美的关于世界的地图。如果地图错了，计划就会失败。
它们缓慢且仅停留在理论层面： 一些方法在理论上可行，但学习速度极慢，或者只能在无限长时间后才保证成功（渐进性），这在数据有限的情况下并无实际意义。

解决方案：鲁棒 Halpern 迭代 (RHI)

作者提出了一种名为鲁棒 Halpern 迭代 (RHI) 的新算法。以下是它的工作原理，分为三个简单的概念：

1. “黑盒”先知（神奇的试吃员）

在现实世界中，AI 并不知道游戏的精确规则。它只有一个“生成模型”——一个它可以提问的模拟器。

挑战： 为了实现鲁棒性，AI 需要知道某个动作的最坏情况结果。但模拟器展示的只是平均结果。
解决方法： 作者创建了一个“黑盒先知”（他们称之为 R-SAMPLE）。你可以把它想象成一个超级试吃员。如果你给它一个配方（一个动作），它不仅仅是品尝平均味道；它会模拟成千上万种变化（辛辣、清淡、焦糊），并告诉你最糟糕版本的味道。这使得 AI 无需预先了解世界的精确规则即可进行学习。

2. “商空间”（忽略噪声）

平均奖励背后的数学逻辑非常复杂，因为有两个未知数：动作的价值和长期的平均得分。这就像是在解一个有两个缺失数字的方程。

解决方法： 作者使用了一种叫做**商空间（Quotient Space）**的数学技巧。想象你在测量两座山之间的高度差。无论你是从海平面开始测量，还是从地心开始测量，高度差是一样的。他们忽略了“绝对高度”（未知的平均值），而只关注“差异”（相对价值）。这简化了数学问题，使其足以解开谜题。

3. “K 阶多层蒙特卡洛”（智能估计器）

这是该论文最大的技术创新。为了从试吃员那里获得那个“最坏情况”的味道，你需要运行多次模拟。

旧方法： 以前的方法就像是通过测量一个人、两个人、三个人来猜测人群的平均身高。它们很慢，而且往往带有“偏差”（系统性误差），比如总是稍微高估一点。
新方法： 作者创建了一个 K 阶多层蒙特卡洛（MLMLC） 估计器。
- 类比： 想象你想知道一个湖泊的平均温度。
  - 第 1 层： 你用手快速、粗略地蘸一下（成本低，误差大）。
  - 第 2 层： 你用温度计进行更精确的测量（成本中等，误差中等）。
  - 第 K 层： 你使用高科技卫星传感器（成本高，误差低）。
- “K 阶”方法巧妙地结合了这些不同层级。它获取廉价、粗略的猜测，并减去它们与昂贵、精确的猜测所共享的误差。其结果是？一个超精确的估计值，且成本极低。这显著降低了“偏差”（误差），让 AI 学习得更快。

结果：快速且高效

论文证明了他们的新方法 (RHI) 非常高效。

样本复杂度（Sample Complexity）： 这是一个专业术语，指的是“AI 需要向模拟器寻求帮助多少次？”
结论： 他们的这种方法所需的样本量，大约与那些拥有完美地图的顶级理论方法的样本量相当。
为什么重要： 他们在不需要地图的情况下（无模型/Model-Free）实现了这一点。他们利用智能的“K 阶”估计器直接从数据中学习最坏情况，从而清理了噪声。

一句话总结

作者发明了一种教 AI 在不确定环境中玩转“长线游戏”的新方法，通过使用一种智能的、能修正偏差的估计器，让 AI 能够直接从数据中学习最坏情况，而无需预先构建一个完美的地图。

技术摘要：无模型鲁棒平均奖励强化学习及其样本复杂度分析

1. 问题定义

本文解决了在**平均奖励准则（average-reward criterion）下的鲁棒强化学习（Robust Reinforcement Learning, RL）**挑战。虽然强化学习在受控环境中取得了成功，但由于模型失配、环境扰动或对抗性攻击，现实世界的部署往往面临“从模拟到现实（Sim-to-Real）”的差距。鲁棒强化学习通过在不确定性集合内的最差性能表现进行优化来缓解这一问题。

具体研究重点是分布鲁棒平均奖励马尔可夫决策过程（Distributionally Robust Average-Reward MDPs, RAMDPs）。与折扣奖励设置不同，平均奖励准则对于排队控制和投资组合优化等应用中的长期稳态性能至关重要。然而，由于以下原因，鲁棒平均奖励 RL 比其折扣对应版本更具挑战性：

非收缩算子（Non-contractive operators）： 鲁棒贝尔曼算子通常是非扩张的而非收缩的，这使得标准的迭代收敛保证失效。
双重未知量（Dual unknowns）： 鲁棒贝尔曼方程涉及两个未知变量：价值函数（或偏差） $Q$ 以及最优平均奖励 $g^*_P$ 。
非线性（Non-linearity）： 从标称样本中估计最差情况期望（支撑函数）会引入偏差，尤其是在无模型（model-free）设置中。

现有文献主要依赖渐近保证、需要预知问题参数（如偏差跨度 $H$ ）的模型化方法，或会导致次优样本复杂度或需要强结构假设（例如具有特定收缩系数的不可约性）的归约法。

2. 方法论：鲁棒 Halpern 迭代 (RHI)

作者提出了 鲁棒 Hal前迭代 (Robust Halpern Iteration, RHI)，这是一种旨在解决鲁棒贝尔曼方程且无需预知 MDP 参数的无模型算法。

2.1. 算法核心

RHI 算法受到优化文献中 Halpern 迭代 的启发，并针对鲁棒平均奖励 RL 的特定挑战进行了改进：

商空间公式化（Quotient Space Formulation）： 为了解决“双重变量之咒”（未知量 $g^*_P$ ），作者将问题嵌入到商空间 $\mathbb{R}^{SA} / \sim$ 中，其中仅差一个常数偏移的向量被视为等价。这使得算法能够在不知道 $g^*_P$ 的情况下求解近端方程 $T_P(Q) - Q = ce$ 。
Halpern 更新： RHI 不使用标准的价值迭代，而是使用初始化值与算子更新的凸组合：
$[Q_{k+1}] = [(1 - \beta_{k+1})Q_0 + \beta_{k+1} T_P(Q_k)]$
其中 $\beta_k = k/(k+2)$ 。这种方法为非扩张算子提供了收敛保证，而不依赖于收缩系数。

2.2. 黑盒采样算子 (R-SAMPLE)

由于鲁棒算子 $T_P$ 是非线性的且涉及最差情况期望，作者引入了一个黑盒采样算子，即 R-SAMPLE。该算子仅利用来自标称核（nominal kernel）的样本，来估计连续迭代之间鲁棒支撑函数的差异。

该算子返回一个随机增量 $D_k$ ，其期望值近似于鲁棒贝尔曼算子值的差异。
算法的样本复杂度基于该算子的性质（利普希茨常数、偏差和样本成本）进行推导。

.3. K 阶多层蒙特卡洛 (MLMC) 估计器

为了具体实现具有低偏差的 R-SAMPLE 算子，作者提出了一个 K 阶 MLMC 估计器。

动机： 用于鲁棒支撑函数的标准插件估计器和普通 MLMC 估计器存在 $O(1/N)$ 的偏差，导致样本复杂度为 $\tilde{O}(\epsilon^{-3})$ 。
机制： K 阶估计器通过构建不同样本规模（ $N_\ell = 2^\ell N_0$ ）下的单层估计器的线性组合来实现。通过精心选择权重 $w^{(K)}_\ell$ ，该估计器可以抵消偏差展开的前 $K$ 项。
结果： 这将偏差降低至 $\tilde{O}(N_0^{-(K+1)})$ ，从而实现了更紧凑的整体样本复杂度。

3. 主要贡献

一种通用的无模型算法： RHI 是第一个不需要预知鲁棒最优跨度 $H$ 或混合时间的鲁棒平均奖励 RL 无模型算法，绕过了基于归约法的局限性。
K 阶 MLMC 估计器： 作者设计了一种新型估计器，与之前的 MLLS 方法相比显著降低了偏差。这对于在非线性鲁棒支撑函数存在的情况下实现近乎最优的样本复杂度至关重要。
有限样本复杂度分析： 本文在生成模型设置下为 RHI 提供了严格的有限样本分析。
- 对于 KL 和 $\chi^2$ 散度 不确定性集合，寻找 $\epsilon$ -最优策略的样本复杂度为 $\tilde{O}\left(SAH^2 \epsilon^{-(2+o(1))}\right)$ 。
- 对于 $\ell_p$ -范数和污染（contamination） 集合，复杂度为 $\tilde{O}\left(SAH^2 \epsilon^{-2}\right)$ 。
- 此处， $S$ 和 $A$ 分别是状态和动作的数量， $H$ 是鲁棒最优偏差跨度。
无参数变体 (PF-RHI)： 作者提出了 RHI 的一个变体，使用倍增技巧（doubling trick）动态确定迭代次数，从而在不预先指定基于未知参数 $H$ 的时间界限的情况下，保持相同的样本复杂度。

4. 结果与理论保证

收敛性： 证明了精确的 RHI 算法具有渐近收敛性，即随着迭代次数增加，贝尔曼残差的跨度和次优差距都会消失。
样本复杂度： 推导出的样本复杂度在 KL 和 $\chi^2$ 集合下，渐近匹配了已知最好的**基于模型（model-based）**方法的界限（例如 Roch 等人, 2025; Chen 等人, 2025）。指数中的 $o(1)$ 项代表一个随 $\epsilon \to 0$ 而消失的次多项式惩罚，这将其与使用标准 MLMC 的方法（复杂度为 $\epsilon^{-3}$ ）区分开来。
实验验证： 在 Garnet 问题及各种不确定性集合（污染、 $\ell_\infty$ 、 $\ell_2$ ）上的数值实验表明，RHI 收敛至最优鲁棒平均奖励，并且 K 阶 MLMC 估计器相比标准方法能有效降低偏差。

5. 意义与主张

本文声称将 RHI 确立为鲁棒平均奖励 RL 的最先进无模型算法。其意义在于：

弥合差距： 它弥合了鲁棒平均奖励 RL 中渐近保证与有限样本分析之间的差距。
实用性： 由于它是无模型的且不需要预知 $H$ ，该算法对于无法获知此类参数的现实世界部署更加实用。
最优性： 其样本复杂度渐近匹配了已知最紧的基于模型方法的界限，证明了无模型方法可以在无需构建模型开销的情况下达到类似的效率。
偏差降低： K 阶 MLMC 设计提供了对以往鲁棒 RL 估计器的根本性改进，解决了由非线性函数估计中未受控偏差导致的高样本复杂度问题。

作者指出，其分析假设了一个生成模型（可访问模拟器）以隔离统计复杂度。向在线（探索-利用）或离线（数据驱动）设置的扩展被列为未来的工作。此外，KL/ $\chi^2$ 集合中样本复杂度的次多项式差距归因于估计非线性泛函时固有的偏差-方差权衡，这在无模型设置中仍是一个尚未完全解决的挑战。