Finite-Time Convergence of Distributionally Robust Q-Learning with Linear Function Approximation

技术摘要：具有线性函数逼近的分布鲁棒 Q 学习的有限时间收敛性

问题陈述
本文解决了在部署环境与训练（标称）环境不同的情况下，进行分布鲁棒强化学习（DRRL）时学习最优策略的挑战。具体而言，作者研究了在 $(s, a)$-矩形 $\chi^2$ 不确定性集下的无模型、折扣鲁棒 Q 学习。

该设定涉及一个学习者在一个由未知的标称转移核 $P_0$ 和行为策略 $\pi_b$ 生成的单个马尔可夫轨迹上进行操作。学习者缺乏生成式访问能力（无法采样任意的状态-动作对），且不知道 $P_0$。目标是学习最优鲁棒 Q 函数 $Q^\star_\chi$，该函数在不确定性集内最大化最坏情况下的折扣值。

该问题呈现了两个耦合的困难：

1. 函数逼近困难： 虽然精确的鲁棒贝尔曼算子在 $\ell_\infty$ 范数下是收缩映射，但在线性函数逼近下，由投影后的鲁棒贝尔曼算子对于一般的折扣因子 $\gamma \in (0, 1)$ 并不保证是收缩的。
2. 鲁棒估计困难： $\chi^2$ 鲁棒贝尔曼更新涉及对转移分布的内层极小化。其对偶梯度依赖于条件矩（具体为贝尔曼间隙及其平方的正部），这些矩必须从单个轨迹中进行估计。标准的表格型鲁棒 Q 学习或线性 Q 学习的分析无法直接扩展到此设定。

方法论
作者提出了 算法 1，这是一种结合了目标网络外层循环与对偶函数逼近方案的多阶段随机逼近算法。该算法在每个外层块（outer blocks）中运行，其中目标 Q 函数被冻结。在每个块内，包含三个阶段：

1. 阶段 1：带有矩追踪的对偶优化。
   算法通过其标量对偶形式求解 $\chi^2$ 鲁棒贝尔曼更新的内层极小化问题。算法并非为每个状态-动作对分别求解独立的对偶问题，而是通过线性近似对偶变量 $\eta$（即 $\eta_\nu(i) = \psi(i)^\top \nu$）。

   • 双时间尺度方案： 对偶变量 $\nu$ 在慢时间尺度上更新，而两个“矩追踪评论家”（moment-tracking critics, $\omega_1, \omega_2$）在较快的时间尺度上估计所需的条件矩（$Z_1$ 和 $Z_2$）。
   • 平滑处理： 为了处理 $\chi^2$ 对偶目标函数缺乏全局光滑性（这会导致马尔可夫噪声分析出现问题）的问题，作者使用了一个可调参数 $\tau > 0$ 来优化一个平滑代理目标。这确保了对偶梯度是 Lipschitz 连续的。
   • 后缀平均（Suffix Averaging）： 对对偶迭代进行后缀平均，以获得稳定的估计值 $\bar{\nu}_t$。

2. 阶段 2：新鲜评估（Fresh Evaluation）。
   在更新 Q 函数之前，算法使用平均对偶参数 $\bar{\nu}_t$ 对方差类矩（$Z_1$）进行一次“新鲜评估”。这一阶段将矩的估计与优化轨迹分离，防止了如果直接复用阶段 1 中（在 $\nu$ 移动过程中学习到的）评论家所导致的偏差累积。

3. 阶段 3：Q 更新。
   算法针对由阶段 1 和阶段 2 得到的固定且经过评估的目标，执行缓慢的时序差分（TD）更新，以更新鲁棒 Q 函数的参数 $\theta$。

核心贡献

1. 有限时间收敛保证： 本文提供了在单轨迹数据下，具有线性函数逼近的折扣无模型鲁棒 Q 学习的首次有限时间收敛界限，且未施加小折扣因子的限制。
2. 针对鲁棒 RL 的目标网络分析： 作者将目标网络技术（常见于非鲁棒深度强化学习）引入鲁棒设定。通过在每个外层块内冻结目标 Q 函数，他们绕过了投影鲁棒贝尔曼算子的非收缩性问题，从而使分析可以依赖于跨块的未投影算子的收缩性。
3. 可扩展的对偶估计： 他们提出了一种使用线性函数类来近似对偶变量的方法，并结合了矩追踪评论家。这避免了为大规模状态空间求解独立对偶问题的可扩展性问题。
4. 平滑与偏差控制： 文中引入了 $\chi^2$ 对偶目标的平滑代理。这解决了 $\chi^2$ 形式中固有的非 Lipschitz 梯度问题，从而实现了在马尔可夫噪声下严谨的有限时间随机逼近分析。作者明确指出，以往针对 $\chi^2$ 不确定性的表格型鲁棒 Q 学习证明依赖于全局光滑性假设，而这些假设并不成立；其证明纠正了这一缺陷。

结果
主要的理论结果（定理 1）建立了一个端到端的收敛界限，形式如下：
$$\mathbb{E}[\| \hat{Q}_T - Q^\star_\chi \|_\infty] \leq \gamma^T \| \hat{Q}_0 - Q^\star_\chi \|_\infty + \frac{E_{stat}(N, M, K, \tau) + E_{app}(\tau)}{1 - \gamma}$$
其中：

• 第一项代表目标网络收缩误差。
• $E_{stat}$ 捕捉来自 Q 更新、对偶优化、平滑偏差和新鲜评估的有限样本误差。
• $E_{app}$ 捕捉由于函数逼近和平滑产生的近似误差。

在 FrozenLake MDP 上的实验验证了该理论，展示了向鲁棒参考值的收敛过程，并说明了由平滑参数 $\tau$ 引入的权衡（较小的 $\tau$ 会降低偏差，但会增加方差/优化误差）。

意义与主张
本文声称填补了鲁棒强化学习算法的经验成功与其非鲁棒对应算法可获得的理论保证之间的显著差距。之前的鲁棒 RL 工作局限于表格型设置、需要生成式访问、假设主动探索，或者施加了严格的折扣因子条件。

作者指出，其工作提供了在单轨迹数据下，无需小折扣因子假设的、具有线性函数逼近的折扣无模型鲁棒 Q 学习的首次有限时间收敛保证。此外，他们断言，即使在表格极限下，其针对 $\chi^2$ 情况的证明也是第一个正确的收敛证明，因为该证明解决了以往分析中所忽略或假设掉的对偶目标缺乏全局光滑性的问题。该框架被呈现为一个可分析的模板，可以扩展到大规模神经网络实现中。