技術要約：非投影型TD学習における堅牢な $O(1/\sqrt{T})$ レート

問題設定

線形関数近似を用いた時間差分（TD）学習は、方策評価のための基本的なアルゴニズムである。漸近的な収束性はよく理解されているが、現実的な条件下、具体的には独立したサンプルではなくマルコフ連鎖によってデータが生成される場合（マルコフノイズ）、有限時間の収束レートを確立することは依然として困難である。

「堅牢な」収束レート $O(1/\sqrt{T})$ に関しては、理論的な空白が存在する。このレートを確立した先行研究（例：Bhandari et al., 2018）は、反復計算を有界集合に強制する投影ステップという人工的な手法に依存していた。この投影は実用上ほとんど行われず、また最適解 $\theta^*$ の境界に関する知識を必要とするが、そのような知識は通常入手不可能である。一方で、非投影型TD学習に対しては「高速な」収束レート $O(1/T)$ が存在するが、これはポテンシャル関数の最小曲率（$\omega$）の逆二乗に依存している。$\omega$ は任意に小さくなり得るため（不良設定問題）、高速なレートは非漸近的なレジームにおいて著しく劣化する可能性がある。

Bhandari et al. (2018) によって提起された未解決問題は、追加の正則性条件や人工的な投影なしに、非投影型TD(0)が堅牢な $O(1/\sqrt{T})$ レートを達成できるかどうかである。

手法

著者らは、マルコフサンプリング下での線形関数近似を用いた標準的な非投影型TD(0)アルゴリズムを分析している。彼らのアプローチは、縮小写像の性質や人工的な投影に依存する従来の分析とは根本的に異なる。

1. ポテンシャル関数の選択

標準的な $D$-ノルム距離 $\|V_{\bar{\theta}_T} - V_{\theta^*}\|_D^2$ の代わりに、著者らは Liu and Olshevsky (2021) が提案したポテンシャル関数を利用している：
$$f(\theta) := (1 - \gamma) \|V_\theta - V_{\theta^*}\|_D^2 + \gamma \|V_\theta - V_{\theta^*}\|_{\text{Dir}}^2$$
このポテンシャルには以下の利点がある：

• 割引因子 $\gamma \to 1$ となっても挙動が良好に保たれる。
• 定常更新場 $\bar{g}(\theta)$ が等式 $\langle -\bar{g}(\theta), \theta - \theta^* \rangle = f(\theta) - f(\theta^*)$ を満たすため、他の研究で使用されている不等式と比較して分析が簡素化される。

2. 帰納法による自己境界特性

核心となる技術的貢献は、TD更新の新しい**自己境界特性（self-bounding property）**である。著者らは、ステップサイズが慎重に選択されている限り、反復計算 $\{\theta_t\}$ が最適解 $\theta^*$ の周囲で期待値の意味で有界に留まることを証明している。

• ステップサイズの設計: ステップサイズは $\eta_t = \frac{1}{c \phi_\infty^2 \log(T) \log(t+3) \sqrt{t+1}}$ と定義される。ここで、$c$ は $c > 15 + 18\sqrt{2}$ を満たす定数である。
• 帰納的議論: 証明は帰納法によって進められる。時刻 $t-1$ までの反復が有界であることを仮定し、時刻 $t$ における更新が依然として有界であることを示す。これは、更新をマルチンゲール差数列（ノイズ）とバイアス項に分解することに基づいている。
• マルコフノイズへの対処: マルコフ的な相関によって導入されるバイアス（$E[g(\theta, Z_t) | \mathcal{F}_{t-1}] \neq \bar{g}(\theta)$）に対処するため、著者らは基礎となるマルコフ連鎖の幾何学的混合（Theorem 3.2）を利用する。ラグ $k'$ における現在の状態分布を定常分布に関連付けることで、バイアスを抑え込む。

3. 有界性分析

著者らは、反復計算が以下を満たすことを示している：
$$E[\|\theta_t\|^2] \leq \rho_c^2 \max\left(\frac{r_\infty^2}{\phi_\infty^2}, \|\theta^*\|^2\right)$$
この有界性は、反復計算を投影することなく達成されており、これにより帰納法のループが閉じられる。

主要な結果

理論的保証

定理 4.2: 指定されたステップサイズを用いて生成された加重平均イテレート $\bar{\theta}_T$ について、反復計算の期待二乗ノルムは、混合時間および曲率 $\omega$ に依存しない定数によって抑えられる。

系 4.3: アルゴリズムは以下の収束レートを達成する：
$$f(\bar{\theta}_T) - f(\theta^*) = \tilde{O}\left( \frac{c \rho_c^2 \max\{r_\infty^2, \phi_\infty^2 \|\theta^*\|^2\}}{\sqrt{T}} \right)$$
決定的なことに、$\tilde{O}$ 表記内の隠れた定数は $\|\theta^*\|$ や特徴量の境界には依存するが、最小曲率 $\omega$ や混合時間 $\alpha$ には依存しない（ステップサイズ条件における軽微な多項式対数補正を除く）。

先行研究との比較

• 投影型堅牢レートとの比較: Bhandari et al. (2018) とは異なり、本結果は投影ステップと $\theta^*$ の事前境界の要求を取り除いている。レートは同等（$\tilde{O}(1/\sqrt{T})$）であるが、人工的な制約なしに達成されている。
• 非投影型高速レートとの比較: $O(1/T)$ を達成する Srikant and Ying (2019) およびその後の研究とは異なり、本結果は未知の曲率パラメータ $\omega$ に依存しない。著者らは、反例を通じて $\omega$ が任意に小さくなり得ることを示しており、高速なレートは実用上、著しく低速化する可能性があるのに対し、堅牢なレートは安定していることを示している。

意義および主張

本論文は、Bhandari et al. (2018) によって特定された特定の未解決問題を解決したと主張している。すなわち、線形関数近似を用いた非投影型TD(0)の、堅牢な収束レートを実現する有限時間分析を提供したことである。

• 人工的な仮定の除去: 投影ステップが、堅牢な分析のために以前は必要であると考えられていたが、実際には必要ないことを本研究は示している。ステップサイズを対数因子で適切にスケールさせることで、反復の有界性はアルゴリズムのダイナミクスから自然に導かれる。
• 追加の正則性の不要: この結果は、問題の構造（既約性、非周期性、特徴量のフル列ランク）に関する標準的な仮定を超えた、追加の正則性条件を仮定することなく成立する。
• 実用的な関連性: 著者らは、理論的には証明を簡素化するために投影が使用されるが、実用では使用されないことを強調している。この分析は、理論的な保証と実用的なアルゴリズム設計の間の溝を埋めるものである。
• 安定性の閾値: 論文は、ステップサイズ定数 $c$ の閾値（具体的には $c > 15 + 18\sqrt{2}$）を、安定性のための十分条件として特定している。合成データを用いた実験結果は、この閾値が真の有限時間安定性効果を捉えていることを示唆している。すなわち、$c$ が小さすぎると反復は発散する。

著者らは、$c$ に対する閾値は（三角不等式、コーシー＝シュワルツの不等式、積分テストなどの）証明上の定数から導かれた保守的な十分条件であり、必ずしも厳密な実用的チューニング規則ではないことを注記している。また、未知の混合パラメータを必要とする「タイム・アニー（anytime）」形式の提示よりも、実行可能な仮定の提示を優先していることから、$T$ が混合時間 $\alpha$ に対して十分に大きい必要があるという点は、堅牢な境界に関する広範な文献に共通する制限事項として認められている。