Heavy-Ball Q-Learning with Residual Weighting Correction

技術要約：残差重み付け補正を用いたヘビーボールQ学習

問題設定
Q学習は、明示的な遷移モデルを持たずに最適なQ関数を学習するための、強化学習における基本的な手法である。標準的なQ学習は、ベルマン最適作用素の縮小性に基づいて収束するが、割引率 $\gamma$ が1に近い場合、この縮小性が弱まり、収束が遅くなることがある。モーメンタムに基づく更新、PID型イテレーション、ランク1補正などの既存の加速手法は、特にアクティブな貪欲ポリシーが動的に変化する制御設定において、標準的なQ学習よりも優れているという厳密な理論的保証を欠いていることが多い。特定の課題として、非一様サンプリング重みを用いたヘビーボール・モーメンタムをQ学習に適用する場合、標準的な重み行列が、特定のスペクトル解析に必要となる「共通固有ベクトル」（具体的には、すべての要素が1のベクトル）の性質を破壊してしまうことが挙げられる。これにより、加速を理論的に証明することが困難になる。

手法
本論文では、**補正ヘビーボールQ学習（Corrected Heavy-Ball Q-Learning: HBCQL）**法を提案し、**スイッチング線形システム（Switched Linear System: SLS）**フレームワークを用いて、その収束性と加速特性を確立する。

1. 残差重み付け補正（Residual Weighting Correction: CQL）:
   著者らはまず、非一様サンプリングにおける共通固有ベクトルの喪失に対処するため、「補正された」Q学習更新（アルゴリズム2）を導入する。彼らは、標準的な対角サンプリング行列 $D$ を、補正行列 $H = \delta \Pi_d + D(I - \Pi_d)$ （ここで $\Pi_d = \mathbf{1}d^\top$）に置き換える。この行列 $H$ は、定数ベクトル $\mathbf{1}$ を自身のスカラー倍に写像する（$H\mathbf{1} = \delta\mathbf{1}$）ように設計されており、これにより、アルゴリズムの平均ダイナミクスに対する共通固有ベクトルを復元する。この補正は固定点 $Q^\star$ を保持しつつ、特定の構造的分解を可能にする。

2. ヘビーボール・モーメンタム:
   本手法は、ヘビーボール・モーメンタム項 $\eta(Q_k - Q_{k-1})$ を加えることで、補正されたQ学習を拡張する（アルゴリズム3）。これにより、一次の漸化式が二次系へと変換される。

3. SLSおよび共同スペクトル半径（JSR）解析:
   中核となる解析ツールは、Q学習のエラーダイナミクスをスイッチング線形システムとして表現することである。スイッチング信号は、ベルマン作用素における貪欲な行動選択によって決定される。収束率は、関連するスイッチング行列の族の**共同スペクトル半径（Joint Spectral Radius: JSR）**によって特徴付けられる。

   • 分解: 著者らは、状態空間を、共通の固有ベクトル（またはヘビーボールの場合の不変部分空間）によって生成される部分空間と、その直交補空間へと分解する。
   • 加速メカニズム: 解析によれば、フルシステムのJSRは、投影されたシステム（共通の方向に対して直交するもの）のJSRと、共通の方向におけるダイナミクスのスペクトル半径の最大値となる。補正行列 $H$ により、共通の方向におけるダイナミクスをパラメータ $\delta$ を通じて独立して調整することが可能になる。そして、$\eta$ が十分に小さい場合、ヘビーボール項は、投影されたダイナミクスに悪影響を与えることなく、この特定の方向に沿った収束を加速させることが示される。

4. 線形関数近似への拡張:
   このフレームワークは、線形関数近似（LQL）へと拡張される。特徴空間において、共通の固有ベクトル方向（$\Phi c = \mathbf{1}$ となるベクトル $c$ によって生成される）の存在を保証するために、同様の補正行列 $G$ が構築される。同様のSLSおよびJSR解析により、類似の収束および加速の結果が得られる。

主な貢献

• 補正Q学習（CQL）: 非一様サンプリングに対して共通の固有ベクトル特性を復元し、厳密なスペクトル解析を可能にする、Q学習更新への構造的補正の提案。
• 理論的な加速の保証: ヘビーボール補正Q学習が、標準的なQ学習および（モーメンタムのない）補正されたQ学習の両方よりも厳密に小さいJSRを持つための十分条件（仮定4.1、4.2、および5.1）の導出。これは、特定の解析的に識別可能な方向における加速の「認定されたレート」を提供する。
• SLS/JSRフレームワーク: スイッチング線形システムおよび共同スペクトル半径解析をQ学習に適用。このアプローチは、標準的な収束議論や確率近似の境界のみを用いる手法とは異なる視点を提供する。これは、貪欲ポリシーのスイッチング特性を明示的に扱うものである。
• 関数近似への拡張: 補正および加速理論を、線形関数近似の設定へと一般化。

結果

• 収束: 定められた仮定の下で、エラーの漸化式が（確率的なケースではノイズ近傍へ）JSRによって制限されるレートで一様に指数関数的にゼロへと収束することを証明している。
• 加速: 理論的解析（定理5.1および10.1）は、小さなモーメンタムパラメータ $\eta$ に対して、ヘビーボール補正システムのJSRが、標準的または補正されたベースラインよりも厳密に小さいことを示している。
• 数値例:
  • 決定論的なテーブル設定において、HBCQLはCQLよりも大幅に速く相対誤差の閾値に到達した。
  • 確率的なテーブル設定において、HBCQLは、標準的なQ学習およびCQLの両方と比較して、特定の誤差閾値に達するまでの中央値を減少させた。
  • 線形関数近似の設定（決定論的および確率的の両方）において、ヘビーボール補正法（HBCLQL）は、標準および補正された線形Q学習の手法と比較して、収束速度において一貫して優れた性能を示した。

意義と主張
本論文は、全方向の加速定理ではなく、一つの解析的に識別可能な方向（共通固有ベクトル方向）における精密な加速の証明を提供することを主張している。著者らは、その貢献が特定の幾何学的方向に対する理論的保証であり、それがQ学習の幾何学に関する新しい洞察を与えるものであることを強調している。

本研究は、以下の点で既存のモーメンタム関連の文献と一線を画している：

1. 単なる方策評価ではなく、制御設定（ポリシーが変化する設定）に焦点を当てていること。
2. 固定方策のスペクトル議論や確率近似の境界のみを用いるのではなく、SLSおよびJSR解析を用いていること。
3. 非一様サンプリングにおいて標準的なヘビーボールQ学習が共通の固有ベクトルを欠くシナリオに対し、構造的補正を提供していること。

著者らは、加速の保証が「投影されたギャップ」の仮定（投影されたダイナミクスが共通の方向のダイナミクスよりも速いという仮定）および小さなモーメンタムパラメータに依存していることを注記している。彼らは、あらゆるパラメータ選択やあらゆるMDPに対して普遍的な加速を主張しているのではなく、手法が理論的に高速になることが保証される領域を特定している。解析は主に決定論的な平均ダイナミクスに対して行われており、標準的な条件付き平均の議論を通じて確率的な設定へと拡張されている。