技術的概要：時間非斉次マルコフ連鎖による確率近似の集中性を用いたオンライン Q 学習の後悔とサンプル複雑性

1. 問題定義

本研究は、無限時間割引マルコフ決定過程（MDP）における古典的・モデルフリーなオンライン Q 学習の理論的解析に取り組む。Q 学習は、Deep Q-Networks（DQN）などの現代的手法の基盤となる強化学習（RL）の基礎的アルゴリズムであるが、既存の有限時間解析には重大な限界がある：

• オフラインバイアス：ほとんどのサンプル複雑性の結果は、固定された行動方策によってデータが生成されるオフライン設定に焦点を当てている。これらの解析は推定誤差（$\|Q_n - Q^\star\|_\infty$）を制御するが、学習プロセス中の性能（後悔）を保証するものではない。
• 楽観性への依存：既存のオンライン Q 学習に対する後悔の上限は、通常、「不確実性に対する楽観性」（例えばボーナス項）やモデルベースのアプローチに依存している。
• 探索のギャップ：オンライン設定において、修正されていない Q 学習更新と組み合わせて使用される$\epsilon$-greedy やボルツマン（softmax）探索などの標準的な探索戦略に対する理論的保証は存在しない。

核心的な課題は、楽観性項を追加することなく標準的な探索方策を用いたオンライン Q 学習について後悔とサンプル複雑性の保証を確立することであり、その際、方策（ひいてはデータ分布）が時間とともに変化し、時間非斉次マルコフ的ノイズ構造を生み出す事実を考慮しなければならない。

2. 手法

著者は、Q 学習の収束と後悔を解析するために、**確率近似（SA）**に基づく新たな解析枠組みを開発した。

2.1 時間非斉次連鎖を伴う確率近似枠組み

Q 学習の更新は、縮小性 SA 反復として定式化される：
$$x_{n+1} = x_n + \beta_n (F(x_n, y_n) - x_n + M_{n+1})$$
ここで、$x_n$は Q 値を表し、$y_n = (s_n, a_n)$は現在の方策によって生成された状態 - 行動ペアであり、$M_{n+1}$はマルチンゲールノイズである。

主な革新点は、時間非斉次マルコフ連鎖$\{y_n\}$を扱う点にある。時間斉次連鎖または一様な混合時間を仮定する先行研究とは異なり、この枠組みでは以下の点を可能にする：

1. 時間変化する遷移ダイナミクス：遷移カーネル$p(\zeta_n, x_n)$は、反復値$x_n$と外部制御列$\zeta_n$（例えば温度$\lambda_n$または探索率$\epsilon_n$）に依存する。
2. 漸近的に消滅する縮小性：縮小係数$\alpha(\zeta_n)$は、$n \to \infty$とともに 1 に収束することが許容される。これは、非最適行動が確率 0 に収束して選択されるシナリオをモデル化し、誘導されたマルコフ連鎖の混合時間が発散することを表す。
3. リプシッツ敏感性：遷移カーネルの反復値$x$の変化に対する敏感性は、増加することが許容される（例えば、温度$\lambda_n \to 0$となるにつれて、softmax 方策は Q 値の差に対して極めて敏感になる）。

2.2 高確率集中 bound

著者は、SA 反復値に対する高確率集中 boundを導出した。証明手法は以下のものを含む：

• ポアソン方程式分解：マルコフ的ノイズを、時間変化する遷移カーネルに関連するポアソン方程式の解を用いて、マルチンゲール差分列と残差項に変換する。
• ノイズの平均化：縮小性の弱体化と変化する遷移カーネルにもかかわらず、ノイズの減衰を評価するための新たな論法を開発する。
• 結果：この bound は、$\|x_n - x^\star\|$がステップサイズスケジュールと、縮小係数が 1 に近づく速度および遷移カーネルが変化する速度に依存する速度で減衰することを示す。

2.3 解析された探索方式

この枠組みは、2 つの特定の探索方策に適用された：

1. ボルツマン Q 学習：減衰する温度$\lambda_n$を用いた softmax 分布$\sigma(Q_n/\lambda_n)$を通じて行動が選択される。
2. 平滑化$\epsilon_n$-greedy（S$\epsilon$G）：一様方策と softmax 方策の凸結合。この平滑化は、遷移カーネルが Q 値に対して滑らかであることを保証し解析を容易にするために導入されたが、実質的には標準的な$\epsilon$-greedy の振る舞いを模倣する。

3. 主要な貢献と結果

3.1 古典的オンライン Q 学習に対する最初の後悔 bound

本論文は、楽観性項を含まない古典的・完全モデルフリー Q 学習に対する最初の後悔 boundを提供する。

• ボルツマン Q 学習：後悔は、MDP の非最適性ギャップ（$\text{gap}(M)$）に決定的に依存する。
  • ギャップが大きい場合、後悔は部分線形である。
  • ギャップが小さい場合、後悔は悪化し線形成長（$O(N)$）に近づく可能性があり、これはバンドットにおけるボルツマン探索の既知の限界と一致する。
• 平滑化$\epsilon_n$-greedy（S$\epsilon$G）：この方式は、近$\tilde{O}(N^{9/10})$のギャップ頑健な後悔 boundを達成する。これは楽観性ベースの手法が達成する$\tilde{O}(\sqrt{N})$よりも劣るが、修正されていないオンライン Q 学習でも部分線形な後悔が達成可能であることを示している。

3.2 サンプル複雑性の保証

著者は、サブガウス型の尾部挙動を示す高確率サンプル複雑性 bound を確立した：

• ボルツマン：特定のパラメータ選択の下、サンプル複雑性は$\tilde{O}((1-\gamma)^{-4}\epsilon^{-2})$であり、温度減衰パラメータ$b \to 0$となるにつれて最適なオフラインレートに近づく。
• S$\epsilon$G：サンプル複雑性は$\tilde{O}((1-\gamma)^{-5}\epsilon^{-2})$であり、SA 手法を通じて導出された既知のオフライン Q 学習の bound と一致しつつ、それらをオンライン設定に拡張している。

3.3 SA に対する新たな集中 bound

主要な技術的貢献は、時間非斉次ダイナミクスを伴う縮小性マルコフ的 SAに対する集中 bound である。

• この bound は高確率で成立し、縮小係数が漸近的に 1 に近づくことを許容する。
• 混合時間が発散し、遷移カーネルが反復値とともに変化するケースを扱う。
• この結果は、制御されたマルコフ的ノイズを伴う RL や最適化アルゴリズムに対して、独立した関心を持つ可能性があると提示されている。

4. 意義と主張

本論文は、実務で広く使用されている標準的な Q 学習アルゴリズム（例えば、$\epsilon$-greedy またはボルツマン探索を伴う DQN）に対して厳密な有限時間保証を提供することで、RL 理論における重要なギャップを埋めると主張している。これらは以前、オンライン設定において理論的根拠を欠いていた。

• 実用性：この結果は、モデルベースのコンポーネントや複雑な楽観性ボーナスを必要としないアルゴリズムに適用可能であり、多くの成功した現代の RL システムの「モデルフリー」な性質と整合する。
• 理論的限界：著者は、達成された後悔レート（$\tilde{O}(N^{9/10})$）が楽観性ベースの手法（$\tilde{O}(\sqrt{N})$）と比較して最適ではないことを認めている。これは、楽観性なしの探索の根本的な限界に起因するとされ、$\epsilon$-greedy やボルツマン戦略が UCB よりも悪いレートをもたらすマルチアームバンドットの結果との類似性が指摘されている。
• 将来の方向性：本論文は、バンドット結果（$\tilde{O}(N^{2/3})$）に一致するように後悔レートを改善すること、関数近似への解析を拡張すること、および平均報酬 RL への bound の適用を含む、潜在的な拡張を特定している。

要約すると、この研究は、探索パラメータを慎重に調整し、時間非斉次確率近似のための新たな解析ツールを活用することで、古典的オンライン Q 学習がアルゴリズム的修正なしに部分線形な後悔と高確率収束を達成し得ることを確立している。