Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

技術サマリー：ポアソン・モロドリフトによる確率近似および強化学習のほぼ確実収束率

問題定義
本論文は、マルコフノイズ下で動作する確率近似（SA）および強化学習（RL）アルゴリズムの、ほぼ確実な収束率を確立するという基本的な理論的課題に取り組む。古典的な理論（例えば、常微分方程式法）は、列 $\{\theta_n\}$ がほぼ確実に収束することを示すが、個々のサンプルパスにおけるこの収束の速度を定量化することにはしばしば失敗する。ほぼ確実な収束率に関する既存の文献には重大な限界がある：

1. 多くの結果は、RL における単一経路サンプリングを反映していない独立同分布（i.i.d.）ノイズに依存している。
2. マルコフノイズを扱う結果は、期待更新が線形であるか、あるいは制限的な学習率領域に依存することを要求することが多い。
3. Qian ら [2024] の最近の研究は、一般的な縮小写像を伴うマルコフノイズを扱うが、より遅い収束率しか導出せず、特定の学習率領域（具体的には $\eta \in (1/2, 2/3]$）をカバーできていない。

著者らは、期待更新が縮小（非ユークリッドノルム、例えば $\ell_\infty$ における縮小を含む）であり、ノイズがマルコフ連鎖を形成する SA アルゴリズムのクラスに焦点を当てている。この設定には、Q-learning や線形時間差（TD）学習といった中核的な RL アルゴリズムが含まれる。

手法：ポアソン・モロドリフト
核心的な技術的革新は、「ポアソン・モロドリフト」と呼ばれる新しいリアプノフドリフト関数の構築にある。著者らは、2 つの確立された手法を新しい補正メカニズムと組み合わせる：

1. モロエンベロープ平滑化：非ユークリッドノルム $\|\cdot\|$ 下で定義される可能性のある縮小写像 $T$ を扱うため、著者らはモロエンベロープ $M_\xi$ を利用する。これにより、微分不可能なノルムベースのエネルギー関数が、連続微分可能な関数 $M_\xi(x)$ に平滑化され、縮小性を保持しつつ勾配ベースの解析を可能にする。
2. ポアソン方程式補正：マルコフノイズに対処するため、著者らはポアソン方程式に基づく補正を適用する。ノイズ項 $F(\theta, Y) - f(\theta)$ は、ポアソン方程式の解 $H_\theta$ を用いて、$H_\theta(y) - (PH_\theta)(y) = F(\theta, y) - f(\theta)$ となるように、マルチンゲール差と望遠鏡的な剰余項に分解される。
3. 新規構築：従来の研究が全期待値を計算する（経路制御を失う）か、「スケルトン反復」（部分列）を使用するのに対し、著者らはポアソン補正をリアプノフ関数に直接組み込む。彼らは以下のドリフトを定義する：
   $$V_n^\xi = M_\xi(e_n) + \alpha_n \langle \nabla M_\xi(e_n), H_{\theta_n}(Y_n) \rangle + K \alpha_n^2$$
   ここで、$e_n = \theta_n - \theta^*$ は誤差、$\alpha_n$ は学習率、$K$ は十分に大きな定数である。
   • 中央の項（ポアソン補正）は、条件付きドリフトに生じるマルコフ依存性による主要なバイアス項を相殺する。
   • 最後の項（$K \alpha_n^2$）は、ドリフトが非負であり続けることを保証し、残余項を制御する。

この構築により、著者らは $V_n^\xi$ が条件付き期待値に対して直接ほぼスーパーマルチンゲール不等式を満たすことを示すことができ、これにより反復列全体（部分列のみではなく）に対して、最近のほぼスーパーマルチンゲール収束率定理（Liu and Yuan [2024]）を適用することが可能になる。

主要な結果
縮小する期待更新、リプシッツ連続性、およびマルコフ連鎖に対するポアソン方程式解の存在という仮定の下で、本論文は誤差 $\|\theta_n - \theta^*\|$ に対する以下のほぼ確実な収束率を導出する：

• べき乗則学習率 $\alpha_n = O(n^{-\eta})$ （$\eta \in (1/2, 1)$）：
  誤差は、ほぼ確実に $o(n^{-(2\eta - 1)})$ に任意に近い速度で収束する。
• 調和学習率 $\alpha_n = O(n^{-1})$ （すなわち $\eta = 1$）：
  誤差は、ほぼ確実に $o(n^{-1})$ に任意に近い速度で収束する。
  • 著者らは、これは i.i.d. ノイズに対する反復対数法則が与える最適な率 $O(n^{-1} \log \log n)$ に近づく強力な結果であると指摘している。

先行研究との比較

• Qian ら [2024] 対比：提案手法はより広範な学習率範囲（特に Qian らが収束率を提供しない $\eta \in (1/2, 2/3]$）をカバーし、$\eta \in (2/3, 1]$ に対して厳密に速い収束率を達成する。
• 期待値ベースの解析対比：本手法は、期待値または確率での収束だけでなく、経路別（ほぼ確実な）保証を提供する。
• 副次的結果：ドリフト不等式の無条件期待値を計算することで、著者らは $\eta \in (0, 1]$ の全範囲に対する $L_2$ 収束率も導出しており、$\eta < 1$ に対して $E[\|\theta_n - \theta^*\|^2] = O(n^{-\eta})$ となることを示している。

応用
この理論的枠組みは、一般化された重要度サンプリング因子を持つ一般化された表形式 TD アルゴリズムのファミリーに適用される。この統一されたテンプレートは、以下の標準的なアルゴリズムを回復する：

• オンポリシーおよびオフポリシーの $n$ ステップ TD。
• $Q^\pi(\lambda)$、Tree-Backup、Retrace、および Q-trace。

これらのアルゴリズムについて、本論文は構造的な条件（平均作用素に対するヒルベルト行列、有限状態連鎖に対するポアソン解の存在）が満たされることを検証し、マルコフサンプリング下におけるこれら一般化された TD 反復の単一経路バージョンに対する、最初の経路別ほぼ確実な収束率を確立する。

意義と主張
本論文は、マルコフノイズおよび非ユークリッド縮小性下での一般的な確率近似に対して、より鋭いほぼ確実な収束率を提供すると主張する。その意義は以下の点にある：

1. 技術的革新性：「ポアソン・モロドリフト」は、モロエンベロープを介した非ユークリッド縮小の処理と、ポアソン補正を介したマルコフノイズの処理を、単一のほぼスーパーマルチンゲール枠組み内で成功裡に橋渡しする新規構築として提示されている。
2. 緊密性：調和学習率（$\eta=1$）に対して導出された収束率は、理論的最適値に近いと論じられており、RL 文献における先行結果を上回る。
3. 完全性：この研究は、マルコフノイズと一般（非線形、非ユークリッド）縮小写像の特定の組み合わせに対処することで文献のギャップを埋めており、これは現代の RL アルゴリズムに特徴的な設定である。

著者らは、収束率の緊密性については慎重であり、既存の文献よりも結果が鋭いものの、反復対数法則の $O(n^{-1} \log \log n)$ 境界を完全に満たすわけではないことを認めている。また、ほぼ確実な収束率を $L_2$ に対して現在証明されている全範囲 $\eta \in (0, 1]$ に拡張することは、未解決の問題であると指摘している。