技术摘要：具有近最优速率的容错异步 Q 学习

问题表述

本文研究了在存在对抗性污染奖励的情况下，于折扣无限时域马尔可夫决策过程（MDP）中学习最优策略的问题。该设定涉及一个智能体与建模为 MDP $(S, A, P, R, \gamma)$ 的环境进行交互，其中数据通过行为策略 $\mu$ 在线收集，该策略诱导出一个马尔可夫链。

核心挑战在于应用于奖励的Huber 污染模型。在每个时间步 $t$，以概率 $1-\epsilon$，智能体观测到的奖励采样自真实分布 $R(s_t, a_t)$，该分布允许具有重尾特性（仅承认有限的二阶矩）。以概率 $\epsilon$，奖励采样自一个任意的、可能无界的对抗性分布 $Q$，该分布可以依赖于历史。目标是在存在污染且数据具有时间相关性（异步、单轨迹采样）的情况下，以高概率估计出具有有限时间误差界的最优状态 - 动作价值函数 $Q^*$。

方法论

作者提出了Robust Async-Q，这是一种旨在处理异步采样和对抗性污染的 Q 学习算法的新颖变体。该算法整合了两个主要机制：

1. 基于截尾均值的鲁棒奖励估计：
   算法不使用原始样本均值，而是为每个状态 - 动作对 $(s, a)$ 维护奖励历史。它采用单变量截尾均值估计量（基于 Lugosi & Mendelson, 2021）来计算期望奖励的鲁棒估计。该估计量将数据分为两半，利用其中一半计算经验分位数以进行过滤，然后对落在这些分位数范围内的另一半剩余样本取平均值。这种方法提供了对重尾分布和部分异常值的鲁棒性。

2. 自适应阈值：
   为了解决鲁棒均值估计保证的概率性质（可能在罕见的极端事件上失效）以及某些设定中奖励统计量未知的问题，算法采用了一种自适应阈值机制。

   • 已知统计量： 如果奖励均值和方差的上界（$\bar{R}, \bar{\sigma}$）已知，则构建一个自适应阈值 $G_t$。如果鲁棒估计超过该阈值，则丢弃该估计（设为零）。随着收集到的样本增多，阈值随时间收缩。
   • 奖励无关（未知统计量）： 当奖励统计量未知时，算法使用时间的“缓慢增长”函数 $m(t) = t^p$ 作为未知上界的代理。这确保阈值最终能主导任何真实常数上界，从而使算法能够在没有奖励分布尺度先验知识的情况下运行。

该算法在标准异步 Q 学习更新规则内，使用这些经过过滤和阈值处理的奖励代理来更新 Q 值。针对单轨迹马尔可夫设定，作者提出了一种子采样策略（使用每 $\tau$ 个样本，其中 $\tau$ 与混合时间相关），以解耦时间依赖性，有效地将问题简化为类独立同分布（i.i.d.）分析。

主要贡献

1. 新颖算法： 本文介绍了Robust Async-Q及其奖励无关变体Robust Async-RAQ。这是首批为对抗性污染和重尾噪声下的异步 Q 学习提供有限时间鲁棒性保证的算法。
2. 有限时间上界：
   • 在独立同分布采样下，作者证明该算法以 $\tilde{O}(1/\sqrt{T})$ 的速率收敛至 $Q^*$，与标准 Q 学习的最优速率相匹配，仅增加一个随 $\sqrt{\epsilon}$ 缩放的加性项。
   • 在马尔可夫（单轨迹）采样下，界限得以保持，仅受与底层链混合时间相关的膨胀因子影响，这与非鲁棒异步 Q 学习的结果一致。
3. 信息论下界： 作者建立了 $Q^*$ 估计误差的 $\Omega(\sqrt{\epsilon})$ 基本下界。这证明了其上界中的加性污染项是不可避免的，即使在所有状态 - 动作对同时被观测到的同步设定下也是如此。
4. 新颖证明技术：
   • 改进的 Azuma-Hoeffding 不等式： 一个关键的技术贡献是应用了改进版的 Azuma-Hoeffding 不等式（Shamir & Spencer, 1987）。由于奖励无关设定中的鞅差允许一个粗略的确定性界限（随时间缩放）但具有更精细的高概率界限，因此需要此工具。标准集中不等式在此背景下无法产生非平凡结果。
   • 马尔可夫数据的耦合： 分析利用耦合技术将子采样马尔可夫链与独立同分布序列联系起来，从而扩展到单轨迹数据。

结果

• 收敛速率： 所提出的算法实现了近最优的有限时间速率。具体而言，误差界的形式为：
  $$\|Q_T - Q^*\|_\infty \leq \tilde{O}\left(\frac{1}{\sqrt{T}}\right) + O(\sqrt{\epsilon})$$
  其中 $O(\sqrt{\epsilon})$ 项取决于污染分数和噪声方差，但与对抗性攻击的幅度无关。
• 对重尾的鲁棒性： 即使真实奖励分布是重尾的（仅具有有限二阶矩），算法也能正确运行，而标准 Q 学习在此设定下往往失效或需要次高斯假设。
• 无关性能： 奖励无关变体（Robust Async-RAQ）达到了与已知统计量变体相同的速率，仅在依赖未知尺度参数时略有多项式膨胀。
• 模拟： 在 Grid-world、FrozenLake、CliffWalking 和 Taxi 环境上的实证结果表明，标准 Q 学习在污染下会产生显著误差，而提出的鲁棒变体则收敛至最优价值函数的邻域。

意义与主张

本文声称提供了在异步、马尔可夫数据下的无限时域折扣强化学习设定中，对抗性鲁棒性的首个原则性且全面的研究。

• 理论完整性： 通过提供匹配的上界和下界（直至污染项），该工作描绘了此类对抗环境中学习基本限制的“相当完整的图景”。
• 弥合差距： 它弥合了鲁棒统计（特别是 Huber 模型和截尾均值）与异步随机逼近的非渐近分析之间的差距。
• 实际相关性： 该工作解决了现实世界中的关切，即反馈数据（奖励）可能是有噪声的、有偏的或被恶意污染的，例如大语言模型的人类反馈或自主系统中的传感器数据。
• 方法学进步： 引入改进的 Azuma-Hoeffding 不等式以处理“粗略确定性但精细概率”的界限，被强调为一种工具，其潜在更广泛的应用性在于超越此特定问题的强化学习算法研究。

作者指出，虽然他们的工作建立了强有力的理论保证，但未来的方向包括将框架扩展到完整反馈流（转换和奖励）中的污染以及函数逼近设定。