技術的サマリー：単一指標バンディットの最適後悔

問題定義

本論文は、報酬が高次元の文脈ベクトルの未知の一次元射影に依存し、かつ未知の非パラメトリックな報酬関数を通じて決定される逐次意思決定フレームワークである**単一指標バンディット（SIB）**問題を取り扱います。

形式的には、各ラウンド $t$ において、学習者は $K$ 個の文脈ベクトルの集合 $X_t = \{x_{t,a} \in \mathbb{R}^d\}_{a \in [K]}$ を観測します。学習者はアーム $x_{t,a}$ を選択し、確率的な報酬を観測します：
$$y_t = f(x_{t,a}^\top \theta^*) + \eta_t$$
ここで：

• $\theta^* \in \mathbb{R}^d$ は未知のパラメータベクトル（指標方向）です。
• $f: \mathbb{R} \to \mathbb{R}$ は未知の連続微分可能なリンク関数です。
• $\eta_t$ は分散が有界な平均ゼロのノイズです。

目的は、時間範囲 $T$ における最適アームの期待報酬と選択されたアームの期待報酬との差として定義される累積後悔を最小化することです。

背景とギャップ：
線形バンディット（$\tilde{O}(\sqrt{T})$）および一般化線形バンディット（$f$ が既知の場合）については最適後悔率が確立されていますが、SIB 設定では $f$ が未知であるため、より困難です。Kang ら [2025] の先行研究は、$f$ が未知だが単調である場合を取り扱い、Stein 推定量を用いて最適の $\tilde{O}(\sqrt{T})$ 後悔を達成しました。しかし、一般的な非単調な場合（$f$ の有界性とリプシッツ連続性のみを仮定）については、既知の最良の上限は $\tilde{O}(T^{3/4})$ でした。本研究の中心的な問いは、**一般（非単調）な単一指標バンディットにおける最適後悔のスケーリングは何か？**というものです。

手法：ZoomSIB-UCB

著者は、**Upper Confidence Bound を備えたズーム単一指標バンディット（ZoomSIB-UCB）**と呼ばれる二段階アルゴリズムを提案します。核心的な洞察は、射影方向 $\theta^*$ を推定し、その後射影された空間を離散化することにより、高次元の問題を一連の一次元バンディット問題に帰着させることです。

フェーズ 1：パラメータ推定

アルゴリズムは最初の $T_0$ ラウンドを未知の方向 $\theta^*$ の推定に費やします。

• 探索： アームは均一にランダムに引き抜かれます。
• 推定： アルゴリズムは正規化された Stein 推定量を採用します。文脈分布のスコア関数を $S(x)$ とすると、$E[y S(x)] = E[f'(x^\top \theta^*)] \theta^* = \mu^* \theta^*$ となる Stein の恒等式を利用し、$\theta^*$ の方向に対する不偏推定量を構築します。
• 正規化： スケールと符号の曖昧さを解決するため、推定量は $\ell_1$-ノルムを用いて正規化されます。
• 較正： 探索期間 $T_0$ は、推定誤差 $\|\hat{\theta}_0 - \theta^*\|_1$ が十分に小さくなるように（具体的には、ビン幅 $\Delta$ と文脈のリプシッツ定数 $L$ を用いて $\Delta / 2L$ 以下に）選択されます。

フェーズ 2：離散化 UCB

$\hat{\theta}_0$ が計算されると、アルゴリズムは射影されたスカラー値 $z = x^\top \hat{\theta}_0$ 上で動作します。

• 離散化： 実数直線は、幅 $\Delta = T^{-1/3}$ の $N = O(T^{1/3})$ 個のビンに分割されます。
• スリーピングバンディット： 各ラウンドにおいて、ランダムな部分集合のビンだけが「アクティブ」（少なくとも 1 つの利用可能なアームを含む）になります。これにより、利用可能なアームの集合が確率的に変化する「スリーピングバンディット」構造が導入されます。
• UCB 戦略： アルゴリズムは利用可能なビンに対して UCB アルゴリズムを実行します。最も高い Upper Confidence Bound インデックスを持つビンに属するアームを選択します。
• バイアスの処理： アルゴリズムは 2 つの誤差源を考慮します：
  1. 離散化バイアス： リプシッツ連続性によって有界となる、ビン中心による連続的な報酬の近似。
  2. 推定誤差： $\theta^*$ の推定誤差に起因する真の指標のずれ。
     これらの誤差は、膨張した信頼半径に吸収されます。

主要な貢献

1. 改善された後悔上限

本論文は、一般的な非単調な単一指標バンディットに対して$\tilde{O}(d^2 T^{2/3})$の後悔上限を確立します。

• これは、Kang ら [2025] による以前の最良の上限 $\tilde{O}(T^{3/4})$ を大幅に改善するものです。
• アルゴリズムは、離散化バイアス（$O(T\Delta)$）と 1 次元バンディット問題の探索コスト（$O(\sqrt{N T})$）のバランスを取ることでこれを達成します。$N \sim T^{1/3}$（したがって $\Delta \sim T^{-1/3}$）と設定することで、累積後悔を $O(T^{2/3})$ に最小化します。

2. 一致するミニマックス下限

著者は、一般的な非単調な設定に対して$\tilde{\Omega}(T^{2/3})$のミニマックス下限を証明します。

• 構成： 高さが $\sim T^{-1/3}$ の小さな局所的な「バンプ」を持つ関数の族を含む困難な問題インスタンスを構築します。
• 帰着： 各ビンにおいてアームが利用可能である確率を高く保つことで、SIB 問題を $N$ 腕バンディット問題（ここで $N \sim T^{1/3}$）に帰着させます。
• 情報理論的罠： Bretagnolle-Huber 不等式を用いて、帰無仮説と特定のビンが最適である「スパイク」仮説との識別には膨大な探索が必要であり、$\Omega(T^{2/3})$ の後悔を強いることを示します。
• 重要性： これは、$\tilde{O}(T^{2/3})$ の上限がタイトであり、提案されたアルゴリズムがミニマックス最適であることを確認します。

3. 実証的検証

合成データおよび実世界データセット（KDD Cup 99、Forest Cover Type）を用いた広範な実験は、以下を実証します：

• 優れた性能： ZoomSIB-UCB は、最先端の GSTOR（Kang ら [2025]）およびランダムベースラインを常に上回り、大幅に低い累積後悔を達成します。
• スケーリング： アルゴリズムは、理論的な最悪ケースの天井 $2/3$ を十分に下回る、実証的な指数 $\approx 0.53$（二次）および $0.57$（ジグザグ）を持つ部分線形後悔スケーリングを示します。
• 次元性： アルゴリズムは、初期推定フェーズ後に射影された 1 次元空間で動作し、カーネルベースの手法を悩ませる次元の呪いを効果的に回避するため、高次元の文脈（$d$）に対して堅牢です。
• 適応的停止： 適応的停止則により、パラメータ推定が安定したときに探索フェーズを早期に終了でき、$\mu^*$ や $T$ に関する事前知識を必要としません。

意義と主張

本論文は、一般的な非単調な単一指標バンディットに対する後悔の最初の鋭い特徴付けを提供することにより、逐次学習における未解決の問題を解決したと主張します。

• 最適性： 上限と一致する下限の両方を提供することで、著者は（対数因子を無視して）正しい後悔スケーリングが $\Theta(T^{2/3})$ であることを確立します。
• 一般性： 単調性や特定の滑らかさのクラス（RKHS など）に依存する先行手法とは異なり、この手法は関数の形状やパラメータ $\mu^*$ に関する知識を必要とせず、任意の有界なリプシッツ連続な報酬関数に対して機能します。
• 実用性： 適応的停止則の導入により、未知の定数に基づいて理論的な探索期間 $T_0$ を事前に固定する必要なく、アルゴリズムを実際に実装可能にします。

この研究は、非パラメトリック統計とバンディット理論の間のギャップを埋め、報酬関数が完全に未知で非単調であっても、単一指標構造を利用することで最適レートを実現できることを実証しています。