技術的概要：平均報酬と割引 TD 学習の間のギャップの橋渡し

問題定義

時間差（TD）学習は強化学習の基盤であるが、その平均報酬設定における理論的解析は、割引設定に比べて著しく遅れている。割引の場合、ベルマン作用素は縮小写像であり、一意な解と単純な収束解析を保証する。一方、平均報酬設定では、ベルマン作用素は任意のノルムに対して縮小性を持たず、対応するベルマン方程式の解は一意ではない（加法定数までしか定義されない）。

平均報酬 TD に関する既存の文献は、割引の場合と比較していくつかの限界を有している：

1. 制限的な仮定: 多くの手法は、表形式（tabular）設定を除外する仮定（例：$\Phi\theta \neq ce$）を必要とする。
2. 収束保証: 一部の手法は、一意で決定論的な解ではなく、サンプルパスに依存する固定点または集合への収束のみを保証する。
3. 次元依存性: 収束 bound には、パラメータ次元 $d$ の明示的な因子が含まれることが多い。
4. 条件数スケーリング: 最先端のサンプル複雑性は、問題の条件数に対して4 乗依存（$O(\eta^{-4})$）を示すことが多いのに対し、割引設定では2 乗スケーリング（$O(\eta^{-2})$）が達成される。
5. アルゴリズム的複雑性: 先行研究でより良いスケーリングを達成するには、標準的な TD の単純さから外れる複雑な分散低減技術（例：ネストされたループ）が必要とされることが多かった。

手法

著者らは、ベルマン方程式の解を制約付き最適化問題として定式化することにより、平均報酬設定における方策評価に対する新たなアプローチを提案する。核心的な洞察は、相対価値関数 $W^*$ が定常状態の制約（$\mu^\top W^* = 0$）を満たさなければならないという点である。

1. ダブルチェーンアルゴリズム

$\Pi = I - e\mu^\top$ となる射影ベルマン方程式 $W^* = \Pi T_\pi W^*$ を解くため、著者らは確率的更新則を導出した。この設定における確率近似の主要な課題は「ダブルサンプリング」問題である：項 $\mu\mu^\top(R + W_t)$ を推定するには、確率変数の積の期待値が必要となるが、相関があるため単一の軌道からは推定できない。

これを解決するため、著者らは各反復で2 つの独立したマルコフ連鎖（$\{s_t\}$ と $\{\hat{s}_t\}$）を利用するダブルチェーンアルゴリズムを導入する。

• 更新則: パラメータベクトル $\theta_t$ は 2 つの成分を用いて更新される：
  • $g(s_t, s'_t, \theta_t)$: 標準的な TD 誤差項 $D(R + P\Phi\theta_t - \Phi\theta_t)$ を推定する。
  • $f(s_t, \hat{s}_t, \theta_t)$: 独立なサンプル $\hat{s}_t$ を用いて相関を断ち、制約項 $-\mu\mu^\top(R + \Phi\theta_t)$ を推定する。
• 線形近似: この手法は、更新を特徴空間に射影することにより、線形関数近似（$W \approx \Phi\theta$）に一般化される。

2. シングルチェーンアルゴリズム

2 つの連鎖を維持する計算オーバーヘッドを回避するため、著者らは Gradient TD (GTD) に着想を得たシングルチェーンアルゴリズムを提案する。

• メカニズム: 2 番目の独立した状態 $\hat{s}_t$ をサンプリングする代わりに、アルゴリズムは期待値 $E[\phi(s)] = \Phi^\top\mu$ を追跡する補助変数 $w_t$ を維持する。
• 更新: ダブルチェーン更新における $\phi(\hat{s}_t)$ の項を $w_t$ に置き換える。変数 $w_t$ は、$\Phi^\top\mu$ に収束するように、別の確率近似ステップを通じて更新される。
• トレードオフ: サンプリング要件を単一の軌道に簡素化する一方で、解析により、ダブルチェーン変種と比較して条件数への依存性がわずかに悪化することが示される。

3. 理論的枠組み：勾配分割

収束解析は、勾配分割（gradient splitting）[19] という手法に依存している。著者らは、アルゴリズムの期待更新方向が、特定の複合二次関数の「勾配分割」として機能することを示す：
$$f(\theta) = \|\Phi(\theta - \theta^*)\|_{\text{Dir}}^2 + (\mu^\top\Phi(\theta - \theta^*))^2$$
これにより、著者らは基礎となるベルマン作用素の非縮小性にもかかわらず、標準的な確率勾配降下法（SGD）の再帰手法を用いてアルゴリズムを解析できる。

主要な貢献

本論文は、以下の特性を同時に達成することで、平均報酬 TD 学習と割引 TD 学習の間の理論的ギャップを埋めると主張している：

1. 一意かつサンプルに依存しない固定点: 提案されたアルゴリズムは、確率軌道や初期化に依存しない単一の決定論的解 $\theta^*$ にほぼ確実に収束する。
2. 表形式および線形設定への適用性: 解析は、$\Phi = I$ となる表形式の場合と線形関数近似の両方に対して成り立ち、制限的な仮定 $e \notin \text{span}(\Phi)$ を必要としない。
3. 次元フリーの bound: 収束 bound には、$\|\theta^*\|$ または $\|\theta_0\|$ に内在するもの以外、明示的な次元 $d$ の因子が含まれない。
4. 最終反復収束: 結果は反復平均に依存するのではなく、割引 TD の標準に倣い、最終反復に対して保証される。
5. 改善された条件数スケーリング:
   • ダブルチェーンアルゴリズムは、$\eta_1 = \min_{\|x\|=1} (\|\Phi x\|_{\text{Dir}}^2 + (\mu^\top\Phi x)^2)$ として定義される条件数を用いて、サンプル複雑性 $\tilde{O}(\epsilon^{-1}\eta_1^{-2})$ を達成する。これは割引設定で見られる2 乗スケーリングと一致する。
   • シングルチェーンアルゴリズムは $\tilde{O}(\epsilon^{-1}\eta^{-4})$（4 乗）を達成し、先行研究の一部よりも改善されているが、ダブルチェーン変種よりはわずかに劣る。
6. アルゴリズム的単純性: 2 乗スケーリングは、分散低減技術（例：ネストされたループや周期的なフルバッチ）を用いることなく達成され、単純な TD 更新の単純さを維持している。

結果

著者らは、i.i.d. サンプリングおよびマルコフ的サンプリングの下で、一定ステップサイズおよび減衰ステップサイズの両方に対する、両アルゴリズムの有限サンプル解析を提供する。

• 理論的 bound: 定理 4.1–4.3 は、収束率とサンプル複雑性を確立する。ダブルチェーン手法は、パラメータスケーリングの点で、割引 TD における最先端の手法と一致する。
• 数値実験: アルゴリズムは、OpenAI Gym および MO-Gymnasium にある 15 の表形式 MDP でテストされた。
  • 結果は、提案された手法が、真の解に対する近似誤差の点で、先行するベースライン（[10], [11], [12], [17], [18], [21] を含む）を一般的に上回ることを示している。
  • 実験は、これらの手法が一意の解に収束することを確認するのに対し、いくつかのベースライン（集合またはサンプルに依存する点に収束するもの）は、表形式設定においてより高い分散または誤差を示すことを確認した。

意義

本論文は、平均報酬 TD 解析に関連する永続的な理論的留保を解決すると主張している。勾配分割と、2 つの連鎖（または補助変数を備えたシングルチェーン）サンプリング戦略を利用することで、著者らは平均報酬 TD が、割引 TD と同じ好ましい収束特性を達成し得ることを実証する：

• 一意性: 定義された一意の解への収束。
• 一般性: 制限的な仮定なしに、表形式および線形設定への適用性。
• 効率性: 複雑な分散低減機構を必要としない、条件数に対する 2 乗依存性。

この研究は、平均報酬設定の理論的困難さは、問題を制約付き最適化タスクとして再定式化し、ベルマン作用素の非縮小性を処理するための特定のサンプリング戦略を活用することで克服可能であることを示唆している。