技術的概要：自然方策勾配を二重平滑化方策反復として

問題定義

強化学習（RL）の問題は、通常マルコフ決定過程（MDP）としてモデル化される。方策反復（PI）や価値反復（VI）といった古典的な動的計画法がベルマン作用素の縮小性と単調性という性質に依存するのに対し、自然方策勾配（NPG）や方策双平均化（PDA）といった現代の勾配法は、方策空間上の連続最適化の観点から分析されることが多い。

文献には概念的な隔たりが存在する。NPG の分析は、古典的手法の強力な収束保証の根幹をなすベルマン作用素の基本的な$\ell_\infty$-ノルム縮小性を活用できていないことが多い。その結果、NPG に関する既存の理論的帰結は、以下の一つ以上の限界に悩まされることが多い。

1. 大域的な幾何学的収束の欠如。
2. 初期状態分布や集中度係数への依存。
3. 曲率を誘発させるための MDP あるいはアルゴリズムの追加的正則化の必要性。
4. 方策軌道やベルマン誤差に依存する適応的ステップサイズの依存。

本論文は、古典的な PI と現代の勾配法を結びつける統一的な枠組みを提供することでこの隔たりを埋め、MDP を修正したり適応的ステップを必要としたりすることなく、分布フリーかつ幾何学的な収束分析を可能にすることを目的としている。

手法：二重平滑化方策反復（DSPI）

著者らは、ベルマン作用素枠組みとして定式化された統一的なアルゴリズム枠組みである**二重平滑化方策反復（DSPI）**を導入する。DSPI は、過去の Q 関数の加重平均に対して適用される正則化された貪欲ステップを通じて方策を更新する。

DSPI の核心は、2 段階の平滑化にある。

1. 平均化平滑化：最新の Q 関数のみを使用するのではなく、アルゴリズムは過去のすべての Q 関数の移動平均（$\bar{Q}_k$）を維持する。
2. 正則化平滑化：貪欲な方策更新は、エントロピーなどの凹関数$\nu(\cdot)$を含む正則化ステップ（例えば softmax）に置き換えられる。

更新則は以下のように定義される。
$$\pi_{k+1}(s) \in \arg\max_{\mu \in \Delta(A)} \left\{ \mu^\top \bar{Q}_{k+1}(s) + \eta_k \nu(\mu) \right\}$$
ここで、$\bar{Q}_{k+1} = (1-\beta_k)\bar{Q}_k + \beta_k Q_{\pi_k}$であり、平滑化パラメータ$\eta_k$はステップサイズ$\beta_k$に基づいて幾何学的に減衰する。

重要なのは、著者らが DSPI が平滑化ベルマン作用素（$H_\eta$および$H^\pi_\eta$）を用いたコンパクトな定式化を許容することを示した点である。これにより、アルゴリズムは最適化理論のツールにのみ依存するのではなく、これらの作用素の単調性と縮小性を用いて分析可能となる。

主要な貢献

1. アルゴリズムの統合

本論文は、DSPI がいくつかの主要なアルゴリズムを特殊ケースとして包含する一般的な枠組みであることを確立する。

• 方策反復（PI）：ステップサイズ$\beta_k \equiv 1$（平均化なし）かつ正則化が消失する場合に再現される。
• 自然方策勾配（NPG）：$\nu(\cdot)$をシャノン・エントロピーに設定し、特定のステップサイズスケジュールを選択することで再現される。
• 方策双平均化（PDA）：$\nu(\cdot)$をシフトされた負の発散生成関数として選択することで再現される。
• 双平均化方策反復：方策が平均化された Q 関数に基づいて貪欲に更新される新しい変種（$\nu(\cdot) \equiv 0$）。

2. 統合された収束分析

平滑化ベルマン作用素の性質を活用することで、著者らは DSPI に対する統一的な収束分析を提供する。

• 漸近収束：非総和的なステップサイズ列に対して証明される。
• 大域的幾何学的収束：定数ステップサイズに対して証明される。誤差 bound は以下のように与えられる。
  $$\|V^* - V^{\pi_k}\|_\infty \leq (1 - (1-\gamma)\beta)^{k-1} (\gamma \|V^* - V^{\pi_0}\|_\infty + \tau \nu_{\max})$$
  ここで、$\gamma$は割引因子、$\beta$は定数ステップサイズである。

3. NPG および PDA に対する改善された理論的保証

DSPI 枠組みを NPG および PDA に適用することで、制限的な仮定を必要とせずに最先端の結果を改善、あるいは同等にする以下の結果が得られる。

• 分布フリー：収束 bound は、初期状態分布や集中度係数ではなく、価値関数のギャップの$\ell_\infty$-ノルムにのみ依存する。
• 追加的正則化の不要：分析は、MDP を修正したり、標準的な NPG に内在するエントロピー項を超えて追加の正則化項を加えたりすることなく成り立つ。
• 単純なステップサイズ：結果は、方策軌道やベルマン誤差に依存する適応的ステップサイズを必要としない、単純で事前に指定された幾何学的増加ステップサイズスケジュール（$\alpha_k = \beta \alpha_0 / (1-\beta)^k$）に対して成り立つ。
• 反復複雑性：NPG および PDA は、$O((1-\gamma)^{-1} \log((1-\gamma)^{-1}\epsilon^{-1}))$回の反復で$\epsilon$-最適方策を達成する。

4. 双平均化 PI の有限終了

正則化のない場合（双平均化 PI）について、著者らは有限終了を証明する。アルゴリズムは、状態空間と行動空間のサイズをそれぞれ$n$および$m$としたとき、最大で$O(mn(1-\gamma)^{-1} \log((1-\gamma)^{-1}))$回の反復で最適方策を見出す。これは、アルゴリズムが$k^*$回の反復ごとに少なくとも 1 つの非最適行動を排除することを示すことで達成される。

5. 拡張

この枠組みは、以下に自然に拡張することが示される。

• 線形関数近似：線形関数近似を用いた DSPI は、関数近似誤差項まで幾何学的収束を達成する。
• 確率的最短経路（SSP）問題：分析は割引のない SSP 問題に拡張され、すべての定常方策が適切であるという仮定の下で、分布フリーの大域的幾何学的収束が確立される。

結果と意義

本論文の主な意義は、古典的な動的計画法と現代の勾配ベースの RL を結びつける統合的な視点を提供することにある。NPG と PDA を方策反復の平滑化および平均化された変種として解釈することで、著者らは以下のことを可能にした。

1. 強力な保証の回復：ベルマン作用素の内在的な性質（単調性と縮小性）のみを用いて、NPG および PDA に対する大域的幾何学的収束を確立する。
2. 人工的な要素の除去：以前の最適化ベースの分析でしばしば必要とされた「曲率誘発」的な正則化や適応的ステップサイズの必要性を排除する。
3. 分析の簡素化：分布ミスマッチ係数の複雑さを回避する、より単純で原理的な分析を提供する。

著者らは、現在の分析が正確な Q 関数へのアクセスを仮定している（方策改善のダイナミクスを孤立させている）ことに留意しつつ、この枠組みが Q 関数を推定しなければならないモデルフリー設定における将来の作業の基礎を築いていると指摘する。彼らは、モデルフリー RL に対する鋭いサンプル複雑性の結果を達成するための次の非自明なステップとして、DSPI と有限時間方策評価保証の組み合わせを特定している。