Self-Concordant Perturbations for Linear Bandits

技術要約：線形バンディットにおける自己共役摂動（Self-Concordant Perturbations）

問題設定
本論文は、アドバーサリアル線形バンディット（adversarial linear bandits）の問題を扱っている。これは、エージェントが凸体 $K \subset \mathbb{R}^d$ から逐次的に行動 $a_t$ を選択するオンライン最適化の設定である。各ラウンドにおいて、エージェントは未知の損失ベクトル $y_t$ によって決定される損失 $\langle y_t, a_t \rangle$ を被り、スカラー値のフィードバックのみを受け取る。目的は、エージェントの累積損失と、事後的に最適な固定行動の累積損失との差である「リグレット（regret）」を最小化することである。

この設定には、主に2つのアルゴリズム・ファミリーが存在する。Follow-the-Regularized-Leader (FTRL) と Follow-the-Perturbed-Leader (FTPL) である。完全情報設定においては、統一されたフレームワーク（GBPA）がこれらを結びつけるが、バンディット設定においてはその区別が極めて重要である。なぜなら、FTRLは明示的な確率的探索メカニズムを必要とするのに対し、FTPLは本質的に確率的であり、行動集合の端点から行動を選択するためである。既存の最適レートを実現するアルゴリズムの多くは、SCRIBLEアルゴリズムで使用される自己共役バリアのフレームワークから自然に導かれるのではなく、複雑でドメイン固有の前処理や探索スキーム（例：スパンニング楕円体）に依存している。SCRIBLEは、一般的な凸体に対して $O(d^{3/2}\sqrt{n \ln n})$、$\ell_2$ ボールに対して $O(d\sqrt{n \ln n})$ のリグレットを達成するが、ハイパーキューブ上での探索の分散が劣っている。

手法：SC-FTPL フレームワーク
著者らは、フル情報設定の GBPA をバンディット設定へと拡張した統一フレームワークである BANDITS-GBPA を導入している。このフレームワークは、アルゴリズムをポテンシャル関数 $\Phi$、サンプリング・スキーム $S$、および推定スキーム $E$ に分離する。

このフレームワーク内で、本論文は 自己共役FTPL (Self-Concordant Follow-the-Perturbed-Leader; SC-FTPL) アルゴリズムを提案している。核心となる革新は、自己共役摂動（self-concordant perturbations） の導入である。

• 定義: 確率分布 $D$ が凸体 $K$ に対する $\vartheta$-自己共役摂動であるとは、$K$ 上の $\vartheta$-自己共役バリア $R$ が存在し、$R$ のFenchel共役の勾配が、$K$ のサポート関数の勾近が摂動 $D$ の下での期待値に等しいことを指す：
  $$\nabla R^*(\theta) = \mathbb{E}_{\xi \sim D}[\nabla \phi_K(\theta + \xi)]$$
  この定義は、摂動分布 $D$ が FTPL の文脈において、自己共役バリア $R$ の幾何学的特性を「複製」することを保証する。

• アルゴリズム: SC-FTPL は累積損失の推定値 $\hat{Y}_{t-1}$ を保持する。各ステップにおいて、アルゴリズムは摂動 $\xi_t \sim D$ をサンプリングし、以下の行動を選択する：
  $$a_t = \arg \min_{a \in K} \langle a, \eta \hat{Y}_{t-1} - \xi_t \rangle$$
  損失ベクトルは、標準的な逆二次のモーメント行列推定量 $\hat{y}_t = Q_t^{-1} a_t \langle y_t, a_t \rangle$ を用いて推定される。ここで $Q_t = \mathbb{E}_{t-1}[a_t a_t^\top]$ である。

主な貢献

1. 統一フレームワーク (BANDITS-GBPA): 著者らは、線形バンディットのための FTRL と FTPL の両方のアプローチを包含するフレームワークを定式化し、GBPA の解析をフル情報設定からバンディット・フィードバックへと拡張した。バンディット設定では、FTPL は厳密には FTRL の部分集合ではないが、フレームワークは共通の解析構造を許容する。
2. 自己共役摂動: 本論文は、自己共役バリアの特性を複製する摂動分布の族を特定し、分析している。これにより、SCRIBLE の正則化特性と FTPL の固有の探索能力の間の溝を埋めている。
3. 具体的な構成: 著者らは、2つの典型的な行動集合に対して特定の自己共役摂動を構成している：
   • ハイパーキューブ $[-1, 1]^d$: エントロピー・バリアを用いて、独立な周辺分布を持つ摂動を導出している。
   • $\ell_2$ ボール $B_d$: 対数バリアを用い、スケーリングされた多変量 $t$ 分布に基づく摂動を構成している。

結果とリグレット境界
本論文は、適切な学習率とホライゾン条件（$n/\ln n$ が次元に対して十分に大きい場合）を仮定した、ハイパーキューブおよび $\ell_2$ ボールに対する SC-FTPL のリグレット保証を提供している。

• ハイパーキューブ: SC-FTPL はリグレット境界 $O(d\sqrt{n \ln n})$ を達成する。

  • これは、対数因子を除いて Dani et al. (2007) によって確立されたミニマックス下界と一致する。
  • これは、SCRIBLE アルゴリズム（ハイパーキューブ上で $O(d^{3/2}\sqrt{n \ln n})$ を達成）に対して $\sqrt{d}$ の改善 を意味する。
  • この改善は、FTPL のサンプリング・スキームが端点に集中することで、SCRIBLE で使用される Dikin 楕円体サンプリングと比較して、局所ノルムにおける損失ベクトルの推定量の分散を減少させていることに起因する。
  • 1ラウンドあたりの計算複雑度は $O(d)$ である。

• $\ell_2$ ボール: SC-FTPL はリグレット境界 $O(d\sqrt{n \ln n})$ を達成する。

  • これは、$\ell_2$ ボールにおける SCRIBLE の性能と一致する。
  • このケースの解析はより複雑である。なぜなら、推定量の局所ノルムが、累積損失推定値から独立した一様なほとんど確実に（almost-surely）の境界を持たないためである。著者らは、累積推定量の増大を制御し、一様境界の欠如に対処するために、超マルチンゲールと停止時間引数（Ville の不等式を使用）を用いた新しい議論を用いている。
  • 1ラウンドあたりの計算複雑度も $O(d)$ である。

意義と主張
本論文は、SC-FTPL が、FTR-ベースの手法が持つ明示的でしばしば複雑な探索メカニズムを必要とせずに、自己共役正則化の利点を回収する、統一された摂動ベースのアプローチを提供することを主張している。

• ハイパーキューブにおける最適性: 主な意義は、ドメイン固有のサンプリング・スキームなしに、ハイパーキューブ上で最適なレートを達成したことにある。これは SCRIBLE アルゴリズムを $\sqrt{d}$ の因子で上回るものである。
• 理論的架け橋: 本研究は、摂動がバリアの幾何学を複製するように選択される限り、FTPL を自己共役バリアのメカニズムを用いて厳密に分析できることを示している。

論文は、エントロピー・バリア（普遍的な自己共役バリア）が、一般的な凸体に対して対応する摂動分布を持つかどうかを調査することや、$\ell_2$ ボールにおいて $O(d\sqrt{n \ln n})$ のレートが あらゆる 摂動スキームに対してタイトであるかどうかを判断することなど、今後の方向性を特定して締めくくっている。