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

技術要約：線形関数近似を用いた分布ロバストQ学習の有限時間収束

問題設定
本論文は、展開環境が訓練（ノミナル）環境と異なる状況下における、分布ロバスト強化学習（DRRL）における最適な方策学習の課題に取り組んでいる。具体的には、著者らは$(s, a)$-矩形カイ二乗不確実性集合下でのモデルフリー・割引ロバストQ学習に焦点を当てている。

設定としては、未知のノミナル遷移カーネル $P_0$ と行動方策 $\pi_b$ によって生成される単一のマルコフ軌跡上で学習者が動作する。学習者は生成的アクセス（任意の状態行動ペアをサンプリングできる能力）を持たず、$P_0$ も知らない。目標は、不確実性集合における最悪ケースの割引価値を最大化する最適なロバストQ関数 $Q^\star_\chi$ を学習することである。

この問題には、二つの結合した困難さが存在する：

1. 関数近似の困難さ： 正確なロバスト・ベルマン演算子は $\ell_\infty$ において縮小写像であるが、線形関数近似によって誘導される投影されたロバスト・ベルマン演算子は、一般的な割引因子 $\gamma \in (0, 1)$ に対して縮小写像になるとは限らない。
2. ロバスト推定の困難さ： カイ二乗・ロバスト・ベルマン更新は、遷移分布に関する内部最小化を伴う。その双対勾配は、条件付きモーメント（具体的には、ベルマン・ギャップとその二乗の正の部分）に依存しており、これらは単一の軌跡から推定されなければならない。標準的なタブラー形式のロバストQ学習や線形Q学習の解析は、この設定に直接適用することはできない。

手法
著者らは、ターゲットネットワークの外ループと双対関数近似スキームを組み合わせた多段階確率近似アルゴリズムであるアルゴリズム1を提案している。このアルゴリズムは、ターゲットQ関数が固定される「外側ブロック」内で動作する。各ブロック内では、以下の3つのステージが発生する：

1. ステージ1：モーメント追跡を伴う双対最適化。
   アルゴリズムは、カイ二乗・ロバスト・ベルマン更新のスカラ双対形式を介して内部最小化を解く。すべての状態行動ペアに対して個別の双対問題を解く代わりに、双対変数 $\eta$ を線形近似する（$\eta_\nu(i) = \psi(i)^\top \nu$）。

   • 二段階タイムスケール・スキーム： 双対変数 $\nu$ は遅いタイムスケールで更新され、一方で2つの「モーメント追跡クリティック」（$\omega_1, \omega_2$）が、必要な条件付きモーメント（$Z_1$ および $Z_2$）をより速いタイムスケールで推定する。
   • 平滑化（Smoothing）： カイ二乗双対目的関数のグローバルな滑らかさの欠如（これがマルコフノイズの解析において問題となる）に対処するため、著者らは調整可能なパラメータ $\tau > 0$ を用いた平滑化されたサロゲート目的関数を最適化する。これにより、双対勾配のリプシッツ連続性が保証される。
   • サフィックス平均化（Suffix Averaging）： 双対イテレートは、安定した推定値 $\bar{\nu}_t$ を得るためにサフィックス平均化される。

2. ステージ2：フレッシュ評価（Fresh Evaluation）。
   Q関数を更新する前に、アルゴリズムは平均化された双対パラメータ $\bar{\nu}_t$ を用いて、分散に類するモーメント（$Z_1$）の「フレッシュ評価」を行う。このステージにより、推定プロセスと最適化の軌跡を分離し、ステージ1のクリティック（$\nu$ が動いている間に学習されたもの）を直接再利用することで生じるバイアスの蓄積を防ぐ。

3. ステージ3：Q更新。
   アルゴリズムは、ステージ1と2から導出された固定された評価済みターゲットに対して、ロバストQ関数のパラメータ $\theta$ に対する遅いTD（Temporal Difference）更新を実行する。

主要な貢献

1. 有限時間収束の保証： 著者らは、小さな割引因子の制限を課すことなく、単一の軌跡データから線形関数近似を用いた割引モデルフリー・ロバストQ学習の、最初の有限時間収束境界を提供している。
2. ロバストRLのためのターゲットネットワーク解析： 著者らは、非ロバストなディープRLで一般的なターゲットネットワークの手法をロバストな設定に適応させている。ブロック内でターゲットQ関数を固定することにより、投影されたロバスト・ベルマン演算子の非縮小性を回避し、ブロック間での未投影演算子の縮小性に依存した解析を可能にしている。
3. スケーラブルな双対推定： 著者らは、モーメント追跡クリティックと組み合わせた線形関数クラスを用いて、双対変数自体を近似する方法を導入している。これにより、大規模な状態空間に対して独立した双対問題を解く際のスケーラビリティの問題を回避している。
4. 平滑化とバイアス制御： 論文では、カイ二乗双対目的関数のための平滑化されたサロゲートを導入している。これは、カイ二乗定式化に固有の非リプシッツ連続な勾配の問題を解決し、マルコフノイズ下での厳密な有限時間確率近似境界を可能にする。著者らは、従来のタブラー・ロバスト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}$$
ここで：

• 第1項はターゲットネットワークによる縮小誤差を表す。
• $E_{stat}$ は、Q更新、双対最適化、平滑化バイアス、およびフレッシュ評価からの有限サンプル誤差を捉える。
• $E_{app}$ は、関数近似および平滑化による近似誤差を捉える。

FrozenLake MDPを用いた実験は、理論を検証しており、ロバストなリファレンス値への収束を示し、同時に平滑化パラメータ $\tau$ によって導入されるトレードオフ（$\tau$ が小さいほどバイアスは減少するが、分散や最適化誤差が増大する）を明らかにしている。

意義と主張
本論文は、ロバストRLアルゴリズムの経験的な成功と、その非ロバストな対応物に対して利用可能な理論的保証との間の大きな隔たりを埋めるものであると主張している。従来のモデルフリー・ロバストRLの研究は、タブラー設定に限定されていたり、生成的アクセスを必要としたり、能動的な探索を仮定したり、あるいは制約の強い割引因子の条件を課したりしていた。

著者らは、本研究が、小さな割引因子の仮定を置かずに、単一の軌跡データから線形関数近似を用いた割引モデルフリー・ロババストQ学習に対する最初の有限時間収束保証を提供すると述べている。さらに、カイ二乗の場合（タブラー極限においても）の証明は、双対目的関数のグローバルな滑らかさの欠如に対処しており、以前の解析が見落としていた、あるいは仮定によって排除していた点に言及しているため、最初の正しい収束証明であると主張している。このフレームワークは、大規模なニューラルネットワーク実装へと拡張可能な、解析可能なテンプレートとして提示されている。