技術的サマリー：敵対的カーネルバンディットにおける近最適後悔

1. 問題定式化

本論文は、損失関数が再生核ヒルベルト空間（RKHS）に属する敵対的線形バンディットの一般化である敵対的カーネルバンディット問題を取り扱います。

• 設定: 各ラウンド $t \in [T]$ において、学習者は有限の行動集合 $\mathcal{X} \subset \mathbb{R}^d$ から行動 $x_t$ を選択します。同時に、無視可能な敵対者が RKHS $\mathcal{H}$ 内のベクトル $w_t$ を選択します。
• 損失: 学習者は、対称正定値カーネル $K$ に関連する特徴写像 $\Phi: \mathcal{X} \to \mathcal{H}$ を用いて、損失 $\ell_t(x_t) = \langle \Phi(x_t), w_t \rangle_{\mathcal{H}}$ を被ります。
• フィードバック: 学習者は、ベクトル $w_t$ や完全な損失関数ではなく、スカラー損失 $\ell_t(x_t)$ のみを観測します。
• 目的: 事後における最良の固定行動 $x^*$ に対する期待後悔 $R_T$ を最小化することです：
  $$R_T = \mathbb{E}\left[ \sum_{t=1}^T \langle \Phi(x_t), w_t \rangle_{\mathcal{H}} - \sum_{t=1}^T \langle \Phi(x^*), w_t \rangle_{\mathcal{H}} \right]$$
• 仮定: 敵対者は有界であり（$\|w_t\|_{\mathcal{H}} \le B$）、カーネルも有界です（$K(x,x) \le 1$）。重要なのは、Chatterji ら [2019] の先行研究とは異なり、敵対者がランク 1 の損失に制限されていないことです（すなわち、$w_t$ は $\Phi(z_t)$ の形である必要はありません）。$w_t$ は有界ノルムを持つ $\mathcal{H}$ の任意の要素となり得ます。

2. 手法とアルゴリズム

著者らは、無限次元の特徴空間に適応させた**指数重み（Exp2）**に基づくアルゴリズムを提案します。核心的な課題は、共分散作用素の固有値がゼロに近づくため、無限次元 RKHS にある特徴写像の場合、線形バンディットにおける標準的な重要度重み付き推定量が有界とならないことです。

これを克服するため、著者らは 2 つの主要な修正を導入します：

1. 正則化された重要度重み付き推定量:
   経験共分散作用素 $\Sigma_t = \mathbb{E}_{x \sim p_t}[\Phi(x)\Phi(x)^\top]$ を反転する代わりに、アルゴリズムはリッジ正則化版 $\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}$ を使用します。推定量は以下のように定義されます：
   $$\hat{w}_t = y_t (\Sigma_t^\lambda)^{-1} \Phi(x_t)$$
   この正則化により、$\Sigma_t$ の固有値がゼロに近い場合でも推定量が有界に保たれます。しかし、これにより体系的なバイアスが導入されます：$\mathbb{E}[\hat{w}_t | \mathcal{F}_{t-1}] = (\Sigma_t^\lambda)^{-1}\Sigma_t w_t \neq w_t$。

2. 明示的なバイアス補正項:
   正則化によるバイアスを補うため、アルゴリズムは修正された損失代理 $\hat{\ell}_t(x)$ を構築します：
   $$\hat{\ell}_t(x) = \langle \hat{w}_t, \Phi(x) \rangle_{\mathcal{H}} - c_t(x)$$
   ここで、補正項は $c_t(x) = B\sqrt{\lambda} \|\Phi(x)\|_{(\Sigma_t^\lambda)^{-1}}$ です。

   • メカニズム: 補正項は、閉形式のバイアス式から直接導出されます。これはバイアスに対する点ごとの上界として機能し、比較対象（最良の固定行動）に対する期待損失代理が真の損失を過小評価することを保証します。この構造的な選択により、後悔分解における比較対象側の残差が非正となり、制御可能な学習者側の残差のみが残ることが保証されます。

3. 探索戦略:
   アルゴリズムは、現在の指数重み分布 $q_t$ と固定された探索分布 $\nu_G$ の混合である分布 $p_t$ を維持します。探索分布は、有効次元が制御されるように正則化された G-最適設計を通じて選択されます。

3. 主要な貢献

• アルゴリズム設計: 指数重み、正則化推定量、明示的なバイアス補正項を組み合わせた原理的なアルゴリズム。このアプローチは、Chatterji ら [2019] が要求した制限的なランク 1 の敵対者仮定を回避します。
• 有効次元を通じた後悔分析: 著者らは、カーネルの有効次元 $d^*(\lambda)$ に依存する後悔 bound を導出します。これは以下のように定義されます：
  $$d^*(\lambda) = \max_{\nu \in \Delta(\mathcal{X})} \text{Tr}\left( (\Sigma(\nu) + \lambda I_{\mathcal{H}})^{-1} \Sigma(\nu) \right)$$
• ランク 1 仮定の除去: この枠組みは任意の有界 RKHS 損失を許可し、ランク 1 制約を必要とする射影ベースの推定量に依存した先行研究と比較して、適用範囲を大幅に拡大します。

4. 主要な結果

本論文は、以下の形式の後悔 bound を確立します：
$$R_T = \tilde{O}\left( B \sqrt{T d^*(\lambda) \log |\mathcal{X}|} \right)$$
ここで、$d^*(\lambda)$ はカーネルの複雑さを捉えます。このレートは、対数因子を除いて、既知の確率的カーネルバンディット問題の最適レートと一致します。

特定のカーネルレート:

• Matérn$(\nu, d)$ カーネル: $\mathbb{R}^d$ 上の滑らかさ $\nu$ を持つ Matérn カーネルの場合、有効次元は以下の後悔 bound を生み出します：
  $$R_T = \tilde{O}\left( T^{\frac{\nu+d}{2\nu+d}} \right)$$
  これは、Chatterji ら [2019] による先行する既知の最良レート $\tilde{O}(T^{\frac{2\nu+d}{4\nu}})$ を改善し、対数因子を除いて同時進行の研究 [Iwazaki, 2026] からの下限と一致します。特に、先行レートは $\nu < d/2$ の場合、さえも亜線形ではありませんでしたが、新しい bound は常に亜線形です。
• 二乗指数（SE）カーネル: この bound は、ランク 1 制限なしに、Chatterji ら [2019] と一致する近最適の $\tilde{O}(\sqrt{T})$ レートを回復します。
• 一般的な固有値減衰:
  • 多項式減衰（$\mu_j \le C j^{-\beta}$）: $R_T = \tilde{O}(T^{\frac{\beta+1}{2\beta}})$ を達成します。
  • 指数減衰（$\mu_j \le C e^{-\beta j}$）: $R_T = \tilde{O}(\sqrt{T})$ を達成します。

5. 意義と主張

本論文は、敵対的カーネルバンディットと確率的カーネルバンディットのパフォーマンス間のギャップを埋めると主張しています。具体的には：

• 最適性: 導出されたレートは、対数因子を除いて、確率的カーネルバンディット（SupKernelUCB やベイズ最適化手法などを通じて）で既知の最適レートと一致します。
• 理論的進展: ランク 1 の敵対者仮定を除去することにより、結果は、損失関数が RKHS の任意の有界要素である、より一般的で現実的な敵対的環境のクラスに適用可能です。
• 先行研究との比較: 本研究は、Matérn カーネルおよび一般的な多項式減衰において Chatterji ら [2019] を改善し、以前の bound が亜線形ではなかった条件下で、より tight な亜線形 bound を提供します。
• 同時進行研究: 著者らは、Iwazaki [2026] による独立した同時進行研究を認めています。これは、密接に関連するアプローチ（正則化推定量とバイアス補正を備えた指数重み）を使用して同様の結果を達成します。論文は、問題設定（例：無視可能な敵対者対適応的敵対者、特定の複雑さ尺度）に minor な違いがあることを指摘しつつ、核心的なアルゴリズム的および分析的貢献は本質的に同等であると主張しています。

本論文は、提案された手法が正則化と明示的なバイアス補正を通じて無限次元特徴空間の課題を効果的に処理し、敵対的カーネルバンディット問題に対する近最適な解決策を提供すると結論付けています。