Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPs

技術的サマリー：連続状態・行動空間におけるエントロピー正則化付きソフトマックス方策勾配のグローバル線形収束性

問題定義
本論文は、連続状態空間および連続行動空間を有する無限時間エントロピー正則化マルコフ決定過程（MDP）における方策勾配（PG）法のグローバル収束性を調査する。エントロピー正則化（強度 $\tau > 0$ の KL 発散項の導入）は、表形式の設定（有限の $S$ および $A$）におけるソフトマックス方策の収束性を改善することが知られているが、関数近似を伴う連続空間へこれらの保証を拡張することは、依然として重大な理論的課題である。

具体的には、著者らは以下で定義される線形結合ソフトマックス方策を考慮する：
$$\pi_\theta(da|s) \propto \exp(\langle \theta, g(s, a) \rangle) \mu(da)$$
ここで、$g: S \times A \to \mathbb{R}^p$ は特徴基底を表し、$\theta \in \mathbb{R}^p$ はパラメータ、$\mu$ は参照測度である。目的は、正則化された価値関数 $V^\pi_\tau(\rho)$ を最小化することである。核心的な難しさは、エントロピー正則化を施しても $\theta$ に関する目的関数の非凸性、および連続設定におけるフィッシャー情報行列（FIM）または特徴共分散行列の潜在的な特異性にある。これらは、標準的な収束証明が成立するのを妨げる要因となり得る。

手法
解析は、連続時間勾配フローの定式化に依存する：
$$\frac{d}{dt}\theta_t = -\nabla_\theta V^{\pi_{\theta_t}}_\tau(\rho)$$
証明戦略は、主に 3 つの段階で進行する。

1. 非一様 Polyak–Łojasiewicz (PŁ) 不等式:
   著者らは、以下の形式の非一様 PŁ 不等式を確立する：
   $$V^{\pi_\theta}_\tau(\rho) - V^{\pi^*_\tau}_\tau(\rho) \leq C(\theta) \|\nabla_\theta V^{\pi_\theta}_\tau(\rho)\|^2$$
   この不等式は、最適性のギャップを勾配ノルムの二乗に結びつける。決定的な点は、定数 $C(\theta)$ が方策の幾何学、具体的には FIM の最小固有値（または単体特徴の場合の中心化されていない特徴共分散行列）および方策の密度の境界に依存することである。表形式の場合には $C$ を一様に取れるのに対し、ここでは $C(\theta)$ は非一様であり、理論的には $\|\theta\| \to \infty$ として退化する可能性がある。

2. $Q^\pi_\tau$-実現可能性仮定:
   解析は、任意の方策 $\pi$ に対して、正則化された状態行動価値関数 $Q^\pi_\tau$ が線形特徴基底によって正確に表現可能であると仮定する：
   $$\langle \theta(\pi), g(s, a) \rangle = -\frac{1}{\tau} Q^\pi_\tau(s, a)$$
   この仮定により、最適方策 $\pi^*_\tau$ がパラメータ化されたクラス内に存在することが保証され、すなわちある $\theta^*$ に対して $\pi^*_\tau = \pi_{\theta^*}$ となる。

3. リアプノフ解析と放射状非有界性:
   グローバル線形収束を証明するために、著者らは非一様定数 $C(\theta_t)$ が勾配フロー軌道に沿って有界に留まることを示さなければならない。これには、軌道 $\{\theta_t\}$ がコンパクト集合内に留まることを証明する必要がある。

   • 彼らは、正則化された目的関数 $V^{\pi_\theta}_\tau(\rho)$ をリアプノフ関数として利用し、それが単調減少することを指摘する。
   • 特徴基底 $g$ に関する特定の条件下で、KL 発散項 $KL(\pi_\theta | \mu)$ が放射状に非有界（すなわち $\|\theta\| \to \infty$ として $KL \to \infty$）であることを証明する。この性質により、価値関数が有界である間にパラメータが無限大に発散することが防がれ、軌道が関連する行列の固有値がゼロから離れて有界であるようなコンパクト領域内に留まることが保証される。

主要な貢献と結果

本論文は、グローバル線形収束が達成される特徴基底の 2 つの異なる領域を特定する。

1. 完全アフィン・スパン特徴:

   • 仮定: 特徴写像 $g(s, \cdot)$ が完全なアフィン次元を持ち、$g$ の任意の線形射影の最大値集合が $\mu$ に対して零測度であること。
   • 結果: KL 発散はすべての方向で放射状に非有界である。その結果、FIM の最小固有値は初期値に依存する正の定数によって下方から有界に保たれる。
   • 収束: 最適性の欠如は、ある $C > 0$ に対して $O(e^{-Ct})$ として減衰する。

2. 単体値特徴:

   • 仮定: 特徴が確率単体内にある（$\sum g_i = 1, g_i \geq 0$）。最大値集合に関する条件は、すべての 1 のベクトルに直交するベクトルに対してのみ適用されるように緩和される。
   • 結果: KL 発散は、パラメータの冗長性の方向であるすべての 1 のベクトルに直交する部分空間内でのみ放射状に非有界である。著者らは、勾配フローがすべての 1 のベクトルへの $\theta$ の射影を保存することを証明し、結果としてダイナミクスを関連する部分空間内に制限することを示す。
   • 収束: FIM の代わりに中心化されていない特徴共分散行列を用いることで、固有値に対する一様な下限を確立し、同じグローバル線形収束率 $O(e^{-Ct})$ を得る。

意義と主張
著者らは、この研究が Agarwal ら (2020)、Bhandari および Russo (2024)、Mei ら (2020) によって確立された表形式の設定を超えて、エントロピー正則化付きソフトマックス方策勾配のグローバル収束理論を拡張すると主張する。

• 連続設定における新規性: 本論文は、線形関数近似を厳密に解析することで、連続空間における表形式手法の計算的非実行可能性に取り組んでいる。
• 非凸性の処理: 非一様 PŁ 不等式を確立し、リアプノフ手法を通じて非一様定数を制御することにより、著者らは連続空間におけるソフトマックスパラメータ化の非凸性を克服している。
• KL 正則化の役割: 本論文は、KL 発散を放射状非有界性を保証するリアプノフ関数として使用する新たな手法を強調している。これは、任意の全支持方策に対して KL 項が有限となる標準的な表形式の場合には成立しない性質である。
• 特徴の感応性: 本作業は、収束条件を満たす具体的な例（例：三角関数特徴、ベルンシュタイン多項式）と、放射状非有界性が失敗する反例（例：ハット関数）を提供し、線形収束に必要な特徴基底の幾何学的性質を明確にしている。

これらの結果は、$Q^\pi_\tau$-実現可能性と適切な特徴条件の下では、エントロピー正則化付き方策勾配が、一般的な状態・行動空間において最適方策へグローバルかつ線形に収束することを示唆しており、これまでに表形式または線形二次設定でのみ知られていた有利な収束率と一致する。