技術的要約：縮小的確率近似における集中度および平均二乗界

問題の定式化
本論文は、以下の反復式で定義される確率近似（Stochastic Approximation, SA）アルゴリズムの有限時間解析を扱っている：
$$x_{k+1} = x_k + \beta_k (f(x_k) - x_k + M_{k+1})$$
ここで、$x_k \in \mathbb{R}^d$ はイテレート、$\beta_k$ はステップサイズ、$f(\cdot)$ は一意の不動点 $x^*$ を持つ写像、$M_{k+1}$ はマルチンゲール差数列である。解析は、強化学習（RL）やその他のアプリケーションで頻繁に見られる以下の2つの特定の課題に焦点を当てている：

1. 任意のノルムによる縮小性: 写像 $f(\cdot)$ は、ユークリッドノルムではなく、任意のノルム $\|\cdot\|_c$（例：Q学習で使用される $\ell_\infty$ ノルム）に関して縮小的である。この性質は、二乗ノルムが非平滑である場合に、リアプノフ・ドリフト不等式の導出を困難にする。
2. 乗法的ノイズ: ノイズは一様に有界ではない。代わりに、条件付き二乗モーメントはイテレートのノルムに対してアフィンにスケールする：$\mathbb{E}[\|M_{k+1}\|_c^2 \mid \mathcal{F}_k] \leq \sigma^2 (1 + \|x_k\|_c^2)$。その結果、イテレート $x_k$ は潜在的に非有界となり、これが、ほぼ確実な（almost-sure）有界性を必要とする標準的なマルチンゲール集中不等式の直接的な適用を妨げる。

手法
著者らは、非平滑なノルムを平滑化するための一般化モロー・エンベロープ（Moreau envelopes）や、非有界なイテレートを扱うための多段階ブートストラップ引数といった、先行研究で使用されている複雑なメカニズムを回避する、統一的かつ初等的なフレームワークを提案している。核となる技術は以下の通りである：

1. 平均化ノイズと補助イテレート:
   著者らは、平均化ノイズ列 $\xi_{k+1} = (1-\beta_k)\xi_k + \beta_k M_{k+1}$ （ただし $\xi_0=0$）および補助イテレート $z_k = x_k - \xi_k$ を定義する。この変換により、元の反復式を $z_k$ に関して以下のように書き換えることができる：
   $$z_{k+1} = z_k + \beta_k (f(z_k) - z_k + \Delta_k)$$
   ここで $\Delta_k = f(x_k) - f(z_k)$ である。極めて重要な点は、この構成により、ノルムを平滑化したりエンベロープを構築したりすることなく、誤差 $\|z_k - x^*\|_c^2$ に対する一歩（one-step）リアプノフ・ドリフト不等式が直接得られることである。誤差 $\|x_k - x^*\|_c$ は、$\|z_k - x^*\|_c + \|\xi_k\|_c$ によって抑えられる。

2. 制御のための帰納的議論:
   ノイズがイテレートに依存するため、平均二乗および集中解析において $\|\xi_k\|_c$ は帰納法を用いて個別に抑えられなければならない：

   • 平均二乗界: 直截的な帰納法を用いて、イテレートが期待値において有界であること（$\mathbb{E}[\|x_k\|_c^2]$ が一様に有界であること）を示す。これは $\mathbb{E}[\|\xi_k\|_c^2]$ を抑えるのに十分である。
   • 集中界: 「良質な」イベント $\{C_k\}$ の列（ここで誤差が制御される）に対して、確率的な帰納法が用いられる。証明は、良質なイベントが失敗する最初の時点によって、悪いイベントの和集合の確率を分解する。これまでのイベントがすべて成立していたという条件下では、イテレート（およびしたがってノイズ）は実質的に有界であり、これにより、切り捨てられたマルチンゲール差列に対して標準的なアズマ・ホフディン不等式の適用が可能になる。

主要な結果
$f(\cdot)$ が縮小因子 $\lambda < 1$ を持ち、ステップサイズが $\beta_k = \beta / (k+h)$ であるという仮定の下で、本論文は2つの主要な定理を確立している。

1. 平均二乗誤差界 (Theorem 1):
   乗法的ノイズモデルの下で、$h$ が十分に大きい場合、以下の定数が存在して：
   $$\mathbb{E}[\|x_k - x^*\|_c^2] \leq \frac{\mathfrak{c}_2}{k+h}$$
   $\ell_\infty$ ノルムの場合、レートは $O(\frac{\sigma^2 \log d}{(1-\lambda)^3 k})$ であり、これはモロー・エンベロープを用いた Chenら [13] の結果と一致する。

2. 最大集中界 (Theorem 2):
   本論文は、すべての $k \geq 0$ に対して同時に成立する高確率な境界（最大値境界）を導出している。任意の信頼水準 $\delta \in (,1)$ に対して、ステップサイズパラメータ $h$ が $\delta$ に対して対数的に依存する場合（具体的には $h = \Omega(\log(1/\delta))$）、確率少なくとも $1 - \frac{\pi^2}{3}\delta$ で：
   $$\forall k \geq 0: \|x_k - x^*\|_c^2 \leq \frac{\mathfrak{c}_4 \log(d(k+1)/\delta)}{k+h}$$
   この境界は、劣ガウス・テイル（sub-Gaussian tail）（$\log(1/\delta)$ としてスケールする）を備えている。

意義と主張
著者らは、潜在的に非有界なイテレートを伴う乗法的ノイズモデルの下でのSAに対し、初の劣ガウス・テイルを持つ最大（全時間）集中界を提供すると主張している。

• 統一性: 本アプローチは、専門的なメカニズム（モロー・エンベロープなど）ではなく、初等的な技術（平均化ノイズと帰納法）を用いて、平均二乗界と集中界の解析を統一している。
• 劣ガウス・テイル vs 不可能性: 本論文は、先行研究（Chenら [15]）で特定されたトレードオフを強調している。すなわち、乗法的ノイズに対して劣ガウス・テイルを達成することは、$\delta$ と独立したステップサイズ列を用いる限り不可能である。ステップサイズ（$h$ を通じて）を $\delta$ に対して緩やかに依存させる（$h \propto \log(1/\delta)$）ことで、著者らは劣ガウス・テイルを回収できる。もし $h$ が固定されている場合、境界は過渡期 $k_0 = \Omega(\log(1/\delta))$ の後にのみ成立する。
• 汎用性: 著者らは、ノイズの平均化技術と確率的帰納法が、他のノイズモデル（例：ヘビーテイル・ノイズ）や、非有界なイテレートを持つ反復アルゴリズム（例：SSP Q-learning, RVI Q-learning）にも一般化可能であることを示唆している。

結論として、本論文の証明技術はより単純であるが、鋭さを犠牲にすることなく、乗法的ノイズの設定における平均二乗誤差の既存のレートを回収し、集中界の裾の挙動を改善している。