📊 statistics

Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

本文确立了在分布鲁棒平均奖励马尔可夫决策过程中学习 $\varepsilon$ -最优策略的极小极大最优样本复杂度，揭示了一个基于扰动规模 $\sigma H_0$ 在名义行为与鲁棒行为之间转换的依赖于机制的复杂度界限，并通过新颖的基于跨度知情与跨度无关的插件缩减程序实现了这些速率。

原作者： Yuepeng Yang, Yuxin Chen, Yuejie Chi

发布于 2026-08-10

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Yuepeng Yang, Yuxin Chen, Yuejie Chi

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

想象一下你正在训练一个机器人在迷宫中导航。在视频游戏那个完美的世界里，墙壁纹丝不动，地板始终干燥，机器人也确切知道每一步会落在哪里。但在现实世界中，情况总是很混乱。地板可能会很滑，门可能会卡住，或者一阵风可能会把机器人吹离航道。如果你只在“完美”的地图上训练你的机器人，它在遇到现实世界的波动时可能会立刻撞车。这就是**强化学习（Reinforcement Learning）**这一领域的核心——智能体通过试错法来学习做出最佳决策。

通常，这些智能体会试图在很长一段时间内最大化总分，就像马拉松选手追求最佳平均速度一样。但问题在于：如果它们学习到的地图并不是它们正在奔跑的地图呢？这就是**分布鲁棒（Distributionally Robust）**思维发挥作用的地方。智能体不再假设世界完全如其所见，而是为合理误差范围内的“最坏情况”做准备。它会问：“如果地板有点滑怎么办？如果门重了一些怎么办？”它学习的是一种即使在情况略有偏差时也能行之有效的策略。科学家们一直在问的一个大问题是：一个机器人究竟需要多少练习（数据）才能学会这种“安全”的策略？ 是只需要一点额外的练习，还是需要海量的数据才能实现真正的鲁棒性？

这篇题为《鲁棒平均奖励马尔可夫决策过程：通过插件简化实现极小极大最优学习》（Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions）的论文深入探讨了这个问题。作者是来自耶鲁大学和宾夕法尼亚大学的研究人员，他们扮演着侦探的角色，试图弄清楚这种“安全”的精确“代价”。他们发现，所需的数据量取决于两个主要因素：环境有多“扭曲”或不可预测（不确定性），以及机器人的表现如何随起始位置而变化（“偏差跨度”）。

他们发现了两个截然不同的学习“区域”。在高容忍区域（High-Tolerance Zone），机器人被允许有一点点不完美。在这里，所需的数据相对较少，与学习普通的、非鲁棒策略所需的数据量相似。这就像是在平坦平静的日子里学骑自行车；你不需要太担心风的影响。然而，在低容忍区域（Low-Tolerance Zone），即使狂风大作，机器人也必须保持完美。在这里，数据需求量大幅跳升。作者证明，为了达到这种安全性，机器人需要与不确定性的平方成比例的额外数据。这是为绝对安全支付的沉重代价，但他们证明了这就是数学上的最低必要成本——你无法绕过这个数学规律。

该论文还引入了一种巧妙的“插件（plug-in）”方法。想象一下你有一个蛋糕食谱。有时，你只需要按照食谱进行烘焙（“名义”方法）。而有时，你需要添加额外的稳定剂，以确保如果烤箱温度波动，蛋糕不会塌陷（“鲁棒”方法）。作者创建了一个智能系统，能够观察情况并决定：“我是直接遵循食谱，还是需要添加稳定剂？”如果机器人知道“跨度”（span），它就可以选择最高效的路径。如果它不知道跨度，该系统也有一个备份计划，可以从数据本身中学习，从而做出正确的选择。

简而言之，这篇论文并不只是在猜测；它通过数学证明，精确地给出了学习鲁棒策略所需的样本量。他们表明，之前的方法有时使用的数据过多，有时又不足，而他们提供了“金发姑娘（恰到好处）”式的解决方案：无论环境是平静还是混乱，都提供恰好合适的数据量。他们的研究结果既有严密的数学证明支持，也有计算机模拟验证，证实了他们的理论在实践中确实成立。

技术摘要：鲁棒平均奖励马尔可夫决策过程

问题定义
本研究探讨了在生成模型设置下，学习 $\epsilon$ -最优策略的分布鲁棒平均奖励马尔可夫决策过程（AMDP）的统计复杂度。智能体在一个由转移核 $P^0$ 和奖励函数 $r$ 定义的标称环境（nominal environment）中运行。然而，真实的决策环境具有不确定性，可能位于以 $P^0$ 为中心的预设不确定集 $\mathcal{P}$ 内。具体而言，本文考虑的是半径至多为 $\sigma$ 的 $(s, a)$ -矩形全变差（TV）不确定集。

目标是最大化鲁棒平均奖励，其定义为在 $\mathcal{P}$ 中所有转移核下的最坏情况长期平均奖励：
$\rho^{\pi, \sigma} := \inf_{P \in \mathcal{P}} \lim_{T \to \infty} \mathbb{E}^\pi_P \left[ \frac{1}{T} \sum_{t=0}^{T-1} r(s_t, a_t) \right]$
学习目标是利用每个状态-动作对 $N$ 个样本来计算一个策略 $\hat{\pi}$ ，使得 $\rho^{\star, \sigma} - \rho^{\hat{\pi}, \sigma} \leq \epsilon$ ，其中 $\rho^{\star, \sigma}$ 是最优鲁棒平均奖励。

关键参数与结构假设
分析依赖于两个关键的结构参数：

标称最优偏差跨度 ( $H_0$ )： 满足标称贝尔曼最优方程的偏差函数（bias function）的跨度。
鲁棒最优偏差跨度 ( $H_\sigma$ )： 满足鲁棒贝尔曼最优方程的偏差函数的跨度。

研究表明 $H_0$ 和 $H_\sigma$ 通常是相互独立的；两者互不控制。文中确定了一个关键的扰动尺度 $\sigma H_0$ ，它将学习问题划分为两个不同的机制（regimes）：

高容忍度机制 ( $\epsilon \gtrsim \sigma H_0$ )： 不确定性引起的扰动相对于目标精度较小。
低容忍度机制 ( $\epsilon \lesssim \sigma H_0$ )： 扰动显著，仅靠标称优化不足以保证鲁棒最优性。

方法论：基于约简的插件式程序 (Reduction-Based Plug-in Procedures)
核心方法论贡献是一个约简框架，该框架将困难的鲁棒平均奖励问题转化为一个更易处理的鲁棒折扣马尔可夫决策过程（DMDP）问题。作者基于此约简提出了两种算法：

跨度感知程序 (Algorithm 1)： 假设已知 $H_0$ 和 $H_\sigma$ 。它根据 $H_0$ 与 $H_\sigma$ 的大小关系以及容忍度机制，自适应地在标称约简（求解一个基于经验转移核的标准 DMDP）和鲁棒约简（求解一个在不确定集上的 DMDP）之间进行选择。折扣因子 $\gamma$ 根据相关的跨度参数进行校准（例如 $\gamma = 1 - \epsilon/(3H_\sigma)$ ）。
跨度无关程序 (Algorithm 2)： 在不知道 $H_0$ 或 $H_\sigma$ 的情况下运行。它通过在折扣因子的二进格点（dyadic grid）上构建来自标称约简和鲁棒约选的候选策略集合，然后使用基于“锚点证书”（anchor certificate，由另一批数据计算得出）的鲁棒平均奖励下置信界（LCB）来选择最优策略。这使得算法能够根据数据自适应地选择正确的约简方式和折扣因子。

分析利用了三个关键的技术改进来实现紧致界限：

通过将鲁棒折扣问题与标称参考解（锚点）进行比较，以收紧方差项。
通过其跨度（ $H_\sigma$ ）而非有效时界（effective horizon）来控制折扣价值函数。
使用受其跨度控制的局部集中不等式。

主要结果：极小极大样本复杂度
本文提供了匹配的极小极大样本复杂度 $N_{SA}$ （每个状态-动作对的样本数）的上界和下界（忽略对数因子）。该复杂度由基于 $H_0$ 与 $H_\sigma$ 的排序以及容忍度机制的四种情形总结而成：

$N_{SA} \asymp \frac{SA}{\epsilon^2} \times \begin{cases} \min\{H_0, H_\sigma\} & \text{若 } \epsilon \gtrsim \sigma H_0 \quad (\text{高容忍度}) \\ \min\{H_0, H_\sigma\} + \sigma H_\sigma^2 & \text{若 } \epsilon \lesssim \sigma H_0 \quad (\text{低容忍度}) \end{cases}$

高容忍度机制： 复杂度由线性跨度项 $\min\{H_0, H_\sigma\}$ 主导。若 $H_\sigma \leq H_0$ ，则鲁棒约简比标称约简产生更紧的界限。
低容忍度机制： 出现了一个额外的“鲁棒性特有”项 $\sigma H_\sigma^2$ ，代表了当需要高精度时处理分布不确定性的代价。
下界： 作者证明了一个与上界匹配的极小极大下界，确立了 $\sigma H_\sigma^2$ 项在低容忍度机制下是基础性的且无法避免。这是第一个刻画分布鲁棒 AMDP 统计极限的下界。

意义与主张
本文声称提供了第一个关于分布鲁棒 AMDP 样本复杂度的极小极大最优表征。主要贡献包括：

解决样本复杂度差距： 先前的鲁棒上界（例如 Roch 等人，2025, 2026）依赖于鲁棒跨度的平方（ $H_{Roch}^2$ 或 $H_{RHI}^2$ ），而未能区分高/低容忍度。本研究将依赖关系精炼为在高容忍度机制下的 $\min\{H_0, H_\sigma\}$ ，并识别了低容忍度机制下精确的 $\sigma H_\sigma^2$ 代价。
自适应算法： 所提出的跨度无关程序（Algorithm 2）无需预先知道跨度参数，即可实现这些最优速率，并能自动适应不同的机制以及 $H_0$ 与 $H_\sigma$ 的相对大小。
通用性： 即使仅假设 $H_\sigma$ 有界，结果依然成立，其复杂度为 $\tilde{\Theta}(SA(H_\sigma + \sigma H_\sigma^2)\epsilon^{-2})$ 。

实验结果通过受控模拟验证了预测的对 $\min\{H_0, H_\sigma\}$ 的线性依赖关系，以及在低容忍度机制下对 $\sigma H_\sigma^2$ 的二次依赖关系，同时也验证了跨度无关算法的自适应性。作者指出，未来的工作可以探索耦合的不确定性结构和在线（基于遗憾值）设置，但目前的工作严格聚焦于生成模型设置。

技术摘要：鲁棒平均奖励马尔可夫决策过程

类似论文