Heavy-Ball Q-Learning with Residual Weighting Correction

技术摘要：带有残差权重修正的重球 Q-学习 (Heavy-Ball Q-Learning with Residual Weighting Correction)

问题陈述
Q-学习是强化学习（RL）中的一种基础方法，用于在没有显式转移模型的情况下学习最优 Q 函数。虽然标准 Q-学习基于贝尔曼最优算子的收缩性质实现收敛，但当折扣因子 $\gamma$ 接近 1 时，这种收缩可能非常微弱，导致收敛缓慢。现有的加速方法，如基于动量的更新、PID 型迭代和秩一修正，通常缺乏严谨的理论保证来证明其优于标准 Q-学习，特别是在主动贪婪策略（greedy policy）会动态变化的控制设置中。一个特定的挑战在于，将重球动量（heavy-ball momentum）应用于具有非均匀采样权重的 Q-学习时：标准的权重矩阵破坏了某些谱分析所要求的“共同特征向量”（特别是全 1 向量）属性，使得在理论上对加速进行认证变得困难。

方法论
本文提出了一种修正重球 Q-学习 (Corrected Heavy-Ball Q-Learning, HBCQL) 方法，并利用切换线性系统 (Switched Linear System, SLS) 框架建立了其收敛性和加速特性。

1. 残差权重修正 (Residual Weighting Correction, CQL)：
   作者首先引入了一种“修正”的 Q-学习更新（算法 2），以解决标准加权 Q-学习中共同特征向量丢失的问题。他们使用一个修正矩阵 $H = \delta \Pi_d + D(I - \Pi_d)$ 取代了标准的对角采样矩阵 $D$，其中 $\Pi_d = \mathbf{1}d^\top$。该矩阵 $H$ 的设计旨在将常数向量 $\mathbf{1}$ 映射为自身的标量倍数（即 $H\mathbf{1} = \delta\mathbf{1}$），从而为算法的平均动力学恢复了一个共同特征向量。这种修正保持了不动点 $Q^\star$，同时实现了特定的结构化分解。

2. 重球动量 (Heavy-Ball Momentum)：
   该方法通过添加重球动量项 $\eta(Q_k - Q_{k-1})$ 来扩展修正后的 Q-学习（算法 3）。这通过将一阶递归转化为二阶系统。

3. SLS 与联合谱半径 (JSR) 分析：
   核心分析工具是将 Q-学习误差动力学表示为一个切换线性系统。切换信号由贝尔曼算子中的贪婪动作选择决定。系统的收敛速率由相关切换矩阵族的联合谱半径 (Joint Spectral Radius, JSR) 来表征。

   • 分解： 作者将状态空间分解为由共同特征向量（或在重球情况下的不变子空间）生成的子空间及其正交补空间。
   • 加速机制： 分析表明，全系统的 JSR 是投影系统（正交于共同方向）的 JSR 与沿共同方向的动力学谱半径的最大值。修正矩阵 $H$ 允许通过参数 $\delta$ 独立地调节沿共同方向的动力学，而重球项 $\eta$ 则被证明可以在不负面影响投影动力学的前提下，加速沿该特定方向的收敛（前提是 $\eta$ 足够小）。

4. 向线性函数逼近的扩展：
   该框架被扩展到线性函数逼近 (LQL)。在特征空间中构建了类似的修正矩阵 $G$，以确保存在一个共同特征向量方向（由满足 $\Phi c = \mathbf{1}$ 的向量 $c$ 生成）。相同的 SLS 和 JSR 分析得出了类似的收敛和加速结果。

主要贡献

• 修正 Q-学习 (CQL)： 提出了对 Q-学习更新的结构化修正，恢复了非均匀采样下的共同特征向量属性，从而实现了严谨的谱分析。
• 理论加速保证： 推导了在满足特定假设（假设 4.1、4.2 和 5.1）的情况下，HBCQL 的 JSR 严格小于标准 Q-学习和（不带动量的）修正 Q-学习的条件。这为在特定可解析识别的方向上提供了“认证速率”的加速。
• SLS/JSR 框架： 将切换线性系统和联合谱半径分析应用于 Q-学习，为理解 Q-学习提供了一个补充视角。该方法显式地处理了由贪婪策略引起的切换特性。
• 向函数逼近的扩展： 将修正和加速理论推广到线性函数逼近设置中。

结果

• 收敛性： 本文证明，在所述假设下，误差递归一致指数级收敛至零（或在随机情况下的噪声邻域内），其速率受 JSR 限制。
• 加速性： 理论分析（定理 5.1 和 10.1）表明，对于小的动量参数 $\eta$，重球修正系统的 JSR 严格小于标准或修正基准。
• 数值演示：
  • 在确定性表格设置中，HBCQL 比 CQL 更快地达到了相对误差阈值。
  • 在随机表格设置中，与标准 Q-学习和 CQL 相比，HBCQL 降低了达到特定误差阈值的中位时间。
  • 在线性函数逼近设置（包括确定性和随机性）中，重球修正后的线性 Q-学习方法 (HBCLQL) 在收敛速度上始终优于标准和修正后的线性 Q-学习方法。

意义与主张
本文声称提供了一个在一个特定可解析识别方向（共同特征向量方向）上的精确加速证明，而非全方向加速定理。作者强调，其贡献是对特定几何方向的理论保证，这为重球 Q-学习的几何特性提供了新的见解。

该工作通过以下方式区别于现有的动量相关文献：

1. 侧重于控制设置（其中策略会发生变化），而非仅仅是策略评估。
2. 使用 SLS 和 JSR 分析，而非仅使用固定策略的谱分析或随机逼近界限。
3. 提供了一种结构化修正，使得在非均匀采样场景下的加速分析变得可行，而在这种场景下，标准的重球 Q-学习缺乏共同特征向量。

作者指出，加速保证取决于“投影间隙”假设（即投影动力学比共同方向动力学更快）以及较小的动量参数。他们并不声称对于所有参数选择或所有 MDP 都能实现通用加速，而是识别出了一个该方法在理论上保证更快的特定区间。分析主要针对确定性平均动力学进行，并通过标准的条件均值论证将其扩展到随机设置。