Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization

以下は、論文「Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization」の詳細な技術的概要です。

1. 問題定義

本論文は、ガウス過程（GP）バンディット最適化の問題、特に非ベイズ設定（関数が固定されているが未知であり、再生核ヒルベルト空間、RKHS に属する）において取り扱います。目的は、ノイズのある観測 $y_t = f(x_t) + \epsilon_t$ に基づき、高価なブラックボックス関数 $f(x)$ を最大化するために、点 $x_t$ を逐次的に選択することです。

性能は累積後悔 $R_T = \sum_{t=1}^T (f(x^*) - f(x_t^+))$ によって測定されます。ここで、$x^*$ は大域最適解、$x_t^+$ は反復 $t$ までにアルゴリズムが報告した最良の点です。

核心的な課題:
**期待改善（EI）**アルゴリズムは、その単純さからベイズ最適化において人気のあるヒューリスティックですが、ノイズのある設定におけるその理論的収束特性は未解決の問題となっていました。

• ノイズのない設定では、「 incumbent（現在の最良値）」は単に観測された最大値であり、単調増加します。
• ノイズのある設定では、incumbent は通常、GP 予測平均（$\mu_t^+$）の最大値、または最大ノイズ観測値（$y_t^+$）として定義されます。
• ノイズのない場合とは異なり、GP 予測平均 $\mu_t^+$ は時間とともに単調ではありません。この単調性の欠如は、incumbent の単調性を用いて後悔を評価する標準的な理論分析を極めて困難にします。先行研究では、未知のパラメータ（RKHS ノルム上限 $B$ やノイズのサブガウス性 $R$ など）を知る必要があったり、高価な大域最適化ステップを必要とする非標準的な incumbent を用いたりしていました。

2. 手法

著者らは、これらの理論的および実用的なギャップに対処するために、2 つの主要なアルゴリズムを提案します。

A. 標準的 incumbent を用いた GP-EI

最初の貢献は、incumbent を観測点における GP 予測平均の最大値として定義する標準的な GP-EI アルゴリズムの厳密な分析です：
$$\xi_t = \mu_t^+ = \max_{x_i \in D_{t-1}} \mu_{t-1}(x_i)$$

• 獲得関数: アルゴリズムは、期待改善を最大化することで次の点 $x_t$ を選択します：
  $$\alpha_{EI}(x) = \mathbb{E}[\max\{0, f(x) - \mu_t^+\} | D_t]$$
  これは関数 $\rho(u, v) = u\Phi(u/v) + v\phi(u/v)$ を用いて閉形式で計算されます。
• 時間変化するスケール: ノイズに対処し、RKHS ノルム（$B$）やノイズパラメータ（$R$）を知らずに収束を確保するために、アルゴリズムは時間変化するスケールパラメータ $\omega_t = \sqrt{\gamma_{t-1} + 1 + \ln(1/\delta)}$ を使用します。ここで $\gamma_t$ は最大情報ゲインです。
• 主要な理論的革新: 著者らは、分散関数の単調性（$\sigma_t(x)$ は $t$ が増加するにつれて減少する）を利用することで、$\mu_t^+$ の非単調性を克服します。彼らは瞬間的後悔を分解し、この分散の性質を用いて「改善項」の和を評価します。これは、この手法で GP バンディット最適化に適用された前例のない技術です。

B. Improved-GP-EI

標準的な GP-EI の限界（具体的には、Matérn カーネルに対して後悔の上限が常に亜線形ではないこと、およびスケールパラメータ $\omega_t$ が急激に増加して不要な探索を引き起こすこと）に対処するため、著者らはImproved-GP-EIを提案します。

• 着想: $\pi$-GP-UCB アルゴリズム（Janz ら、2020）から適応されました。
• 分割戦略: 探索空間は超立方体（被覆）に分割されます。各超立方体には、局所データのみを使用して独立した GP が適合されます。
• グローバルスケール: 時間変化する $\omega_t$ の代わりに、多対数関数的にのみ増加する固定されたグローバルスケール $\omega_T = \sqrt{\ln(T)\ln\ln(T)}$ を使用します。
• メカニズム: 各ステップで、アルゴリズムは現在の最良候補を含む特定の超立方体内で EI を最大化する点を選択し、最適化を効果的に局所化します。

3. 主要な貢献

1. 標準的 GP-EI に対する初の理論的保証:
   本論文は、標準的 incumbent（$\xi = \mu_t^+$）を用いた GP-EI がノイズのある設定で収束することを初めて証明しました。

   • 後悔の上限: 累積後悔は $O(\gamma_T \sqrt{T})$ によって評価されます。
   • パラメータ非依存: 重要なのは、このアルゴリズムが RKHS ノルム上限（$B$）やノイズのサブガウス性パラメータ（$R$）の知識を必要としないことです。これらは現実の応用では通常未知です。

2. Improved-GP-EI アルゴリズム:
   Matérn カーネルに対してより高速な収束率を達成する新しい変種です。

   • 後悔の上限: 滑らかさ $\nu > 1$ を持つ Matérn カーネルに対して、後悔は $\tilde{O}(T^{\frac{d(2d+3)+2\nu}{d(2d+4)+4\nu}})$ です。これはすべての $\nu > 1$ および $d \geq 1$ に対して亜線形であり、標準的 GP-EI の限界を改善します。
   • 効率性: 分割戦略と多対数関数的なスケールパラメータを使用することで、従来手法で見られた分散スケールの急激な増加を回避し、不要な探索を削減します。

3. 新規な証明手法:
   著者らは、GP 分散関数の減少する単調性を利用して改善項の和を評価することで、GP 予測平均 incumbent の非単調性を処理する証明戦略を導入しました。

4. 結果

理論的結果

• 標準的 GP-EI: $O(\gamma_T \sqrt{T})$ の後悔を達成します。二乗指数（SE）カーネルの場合、これは亜線形です。Matérn カーネルの場合、亜線形となるには $2\nu > d$ が必要です。
• Improved-GP-EI: すべての $\nu > 1$ に対して亜線形であるより tight な後悔の上限を達成します。これは $\pi$-GP-UCB の後悔率と一致しますが、$B$ と $R$ を知る必要を排除します。

実証結果

著者らは、合成関数（Hartmann3, Shekel, Hartmann6, Ackley）および RKHS 空間から生成された関数に対して、これらのアルゴリズムをテストしました。

• 性能: Improved-GP-EI は、標準的 GP-EI、Modified-GP-EI、そして最先端の $\pi$-GP-UCB を一貫して上回りました。
• 頑健性: 未知パラメータ（$B$ と $R$）のヒューリスティックな調整を必要とし、これらが誤って推定された場合に性能が低下する $\pi$-GP-UCB とは異なり、Improved-GP-EI はこれらの上限に関してパラメータフリーであり、優れた安定性を示しました。
• 効率性: Improved-GP-EI の分割戦略は計算複雑性を削減しました。例えば、Hartmann3 において、Improved-GP-EI の反復あたりの平均実行時間は 1.21 分であったのに対し、標準的 GP-EI は 1.37 分でした。この差は、カーネル行列の逆行列計算（1 つの巨大な行列ではなく、より小さな局所行列の逆行列を計算する）のサイズ削減により、より大きな地平線（horizon）において拡大しました。

5. 意義

本論文は、ガウス過程バンディットに対する期待改善の理論的分析における長年の未解決問題を解決しました。

• 理論と実践の架け橋: 最も人気のあるヒューリスティック（EI）が、関数の滑らかさやノイズレベルに関する「オラクル」的な知識を必要とせず、ノイズのある環境で理論的に健全であることを証明しました。
• 実用性: 未知パラメータ（$B$ と $R$）への依存性を排除することで、提案されたアルゴリズムは、これらの値を事前に推定することが困難または不可能な現実世界のシナリオ（ロボット工学、ハイパーパラメータ調整など）に即座に適用可能です。
• アルゴリズムの進展: Improved-GP-EI は、UCB ベースの手法に対する堅牢でパラメータフリーな代替案を提供し、EI ベースの戦略が最適な後悔率を達成しつつ、カーネルの選択やパラメータの不確実性に対してより堅牢であることを実証しました。