技術要約：非投影型線形TD(0)における単一ステップサイズの十分性

問題設定

本論文は、マルコフ的なサンプリング下における、バイアスゼロの線形時間差（TD(0)）学習の有限時間・高確率収束解析に取り組んでいる。この設定では、データは独立同一分布（i.i.d.）のサンプルとしてではなく、マルコフ連鎖の単一の軌跡に沿って生成される。

核心となる課題は、TD(0)が標準的な確率的勾配法ではない点にある。その更新はバイアスがあり、非対称であり、ノイズには時間的な相関が存在する。既存の非漸近的解析の多くは、以下の2つの制約的なアプローチのいずれかに依存している：

1. 投影（Projections）: 反復計算を既知の球体内に投影することで有界性を強制する。これにより集中不等式の議論は簡素化されるが、アルゴリズム自体が変更され、問題の曲率に関連する適切な半径に関する事前知識が必要となる。
2. 曲率依存の安定性（Curvature-Dependent Stability）: 平均的なダイナミクスの収縮性を利用して、投影なしで安定性を論じる。しかし、これは通常、未知の曲率パラメータ（$\omega$）に依存するステップサイズ条件や安定性境界を生じさせる。$\omega$が小さい場合、これらの境界は極めて遅くなり、ステップサイズを$\omega$から独立して選択することができなくなる。

著者らは、以下の両方を同時に保証する、曲率パラメータ$\omega$に依存せず、かつ投影を必要としない単一のステップサイズ・スケジュールを確立することを目指している：

• 堅牢性（Robustness）: $\omega$に関わらず成立する収束レート $\tilde{O}(1/\sqrt{T})$。
• 高速性（Fastness）: 有利な曲率が存在する場合にそれを活用する収束レート $\tilde{O}(1/(\omega T))$。

手法

1. ポアソン方程式による自己境界引数（Self-Bounding Argument）

中心的な技術的独創性は、曲率$\omega$や人工的な投影に頼ることなく、反復計算 $\theta_t$ の経路上の有界性を制御する、新しい「自己境界」的な帰納的議論である。

• ループの課題: 素朴な集中解析は循環的である。誤差を抑えるには有界な更新が必要だが、有界な更新には有界な反復計算が必要である。
• 解決策: 著者らは、幾何学的混合特性を持つマルコフ連鎖に関連するポアソン方程式を用いて、マルコフ・ノイズを分解する。中心化された強制項 $h$ に対して、$u - P_Z u = \tilde{h}$ を解く。
• 分解: これにより、マルコフ・ノイズの蓄積を、マルチンゲール項（$M_t$）と制御された残差項（$R_t$）に分解できる。
• 帰納法: 彼らは、時刻 $t-1$ までの反復計算の有界性が時刻 $t$ における有界性を意味するという帰納的仮説を確立する。Pinelisの不等式を通じてマルチンゲール項を制御し、ポアソン解のリプシッツ特性を通じて残差項を制御することで、反復計算が高確率で、かつ$\omega$に依存せず一様に有界であることを証明する。

2. ポラック・ルパート（Polyak–Ruppert, PR）平均化

本論文では、ポラック・ルパート平均反復計算 $\bar{\theta}_T = \frac{1}{S_T} \sum_{t=1}^T \eta_{t-1} \theta_{t-1}$ （ここで $S_T = \sum \eta_{t-1}$）を分析している。

• $\theta_t$ の一様有界性が確立されると、著者らは収束解析におけるマルチンゲール項の二次変動およびバイアス項を制御できるようになる。
• 彼らは、ポテンシャル関数誤差 $f(\bar{\theta}_T) - f(\theta^*)$ に対して、2つの異なる上限を導出する：
  • 古典的な平均化確率的勾配降下法の解析から導かれた堅牢な境界（robust bound）。これは $\tilde{O}(1/\sqrt{T})$ を与える。
  • 誤差 $e_t = \theta_t - \theta^*$ の進化を分析し、TD行列の対称部分の正定値性（曲率 $\omega$）を活用した高速な境界（fast bound）。これは $\tilde{O}(1/(\omega T))$ を与える。

3. ステップサイズ・スケジュール

提案されるステップサイズは以下の通りである：
$$\eta_t = \frac{1}{c \tau_{\text{mix}} \phi_\infty^2} \cdot \frac{1}{\sqrt{t+1} \log(t+3)}$$
ここで、$c$ は数値定数、$\tau_{\text{mix}}$ は混合時間、$\phi_\infty$ は特徴量のノルムの上限である。決定的なのは、このスケジュールが混合時間に依存するものの、曲率 $\omega$ には依存しない点である。

主な結果

1. 高確率の有界性（定理 4.1）

標準的な仮定（エルゴード的MRP、フルランクの特徴量）の下で、非投影型TD(0)の反復計算は、高確率（$1-\delta$）で一様に有界である：
$$\sup_{t \ge 0} \|\theta_t\|^2 \le \rho R_{\text{base}}$$
ここで、$R_{\text{base}}$ は初期誤差、最適解のノルム、および問題の定数に依存するが、$\omega$ には依存しない。これは、ステップサイズや安定性議論において $\omega$ を使用せずに、このような有界性を示した初の研究である。

2. 同時収束レート（定理 4.2）

同じステップサイズとPR平均化を用いることで、アルゴリズムはポテンシャル関数誤差に対して以下の高確率収束レートを達成する：
$$f(\bar{\theta}_T) - f(\theta^*) \le \min \left\{ \frac{C_{\text{fast}}}{\omega S_T^2}, \frac{C_{\text{robust}}}{S_T} \right\}$$
このステップサイズ・スケジュールを代入すると、以下のように変換される：

• 堅牢なレート: $\tilde{O}\left( \frac{\tau_{\text{mix}} R_{\text{base}}^2}{\sqrt{T}} \right)$
• 高速なレート: $\tilde{O}\left( \frac{\tau_{\text{mix}}^2 R_{\text{base}}^2}{\omega T} \right)$

この境界は、$\omega$ に関する事前知識なしに、これら2つのレートのうち小さい方へと自動的に適応する。

3. 混合フリーのバリアント（付録 E）

著者らは、$\tau_{\text{mix}}$ の知識を必要としない修正ステップサイズ $\eta_t \propto \frac{1}{\sqrt{t} \log^2 t}$ も提案している。しかし、これは収束境界の定数、具体的には初期プレフィックス境界 $B_{m^*}$ を通じて、$\tau_{\text{mix}}$ に対する二重指数関数的な依存という代償を伴う。

意義と主張

本論文は、線形TD(0)が、マルコフ的サンプリング下において、単一のステップサイズを用いて、曲率パラメータ $\omega$ に依存せず、かつ投影フリーで、堅牢かつ高速な高確率収束レートの両方を達成できることを示した最初の研究であると主張している。

著者らは、従来の先行研究は、投影を要求するか（アルゴリズムを変更する）、曲率依存のステップサイズに依存するか（$\omega$ が小さい場合に失敗する）、あるいは期待値の境界のみを提供している（例：Lee and Orabona [2025]）点を強調している。

その意義は、ポアソン方程式を用いた自己境界引数にある。これにより、平均的なダイナミクスの収縮特性に訴えることなく、反復計算の有界性と更新の大きさの間の循環依存関係を打破している。これにより、アルゴリズムは曲率が極めて小さい場合でも安定性を保ち、急速に収束することができる。これは、従来の投影フリーの解析が通常失敗するか、データのドロップ戦略を必要としたシナリオである。

論文は、混合時間 $\tau_{\text{mix}}$ への依存関係については控えめな表現を用いている。高速レートは $\tau_{\text{mix}}^2$ への依存を伴う（これは投影型やデータドロップ型の研究における線形な $\tau_{\text{mix}}$ 依存よりも劣る）。著者らは、投影やデータドロップを行わない状況における $\tau_{\text{mix}}$ の最適な依存関係は依然として未解決の問題であると述べている。また、収縮ベースの議論を避けた結果として、初期誤差項が指数関数的ではなく $1/T$ のレートで減衰することも認めている。