Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration

技術要約：一定の探索パラメータを用いた、時間変動型ガウス過程バンディットにおけるより鋭い後悔界

問題設定
本論文は、未知の報酬関数 $f_t: S \to \mathbb{R}$ が時間とともに進化する非定常環境におけるベイズ最適化を取り扱う。具体的には、著者らは Bogunovicら [2016] によって導入された、時間変動型ガウス過程（TV-GP）モデルを検討している。この設定では、潜在関数は、空間的ガウス過程 $g_t$ のイノベーションによって駆動されるマルコフ再帰に従って進化する：
$$f_{t+1}(x) = \sqrt{1-\epsilon} f_t(x) + \sqrt{\epsilon} g_{t+1}(x)$$
ここで、$g_t$ はカーネル $k_S$ を持つ独立同一分布（i.i.d.）の空間的ガウス過程からの描画であり、$\epsilon \in (0, 1]$ は時間的変化の速度を制御するドリフト・パラメータである。目標は、累積後悔 $R_T = \sum_{t=1}^T (f_t(x_t^*) - f_t(x_t))$ を最小化することである。静的な設定とは異なり、ここでは劣線形な累積後悔を達成することは一般に不可能であり、目的はドリフト率 $\epsilon$ の関数として平均後悔 $R_T/T$ を抑えることである。

手法
著者らは、この動的な設定におけるガウス過程上側信頼限界（GP-UCB）アルゴリズムを再検討している。TV-GPバンディットに関する標準的な解析では、全ホライゾンにわたって一様な信頼区間を維持するために、探索パラメータ $\beta_t$ が時間 $t$ とともに増加することを要求する場合が多い。本論文は、異なる解析的アプローチを提案している：

1. 局所的信頼イベント（Local Confidence Events）： ホライゾン全体で一様に成立する単一のグローバルな信頼イベント（これには時間とともに増大する $\beta_t$ が必要となる）に依存する代わりに、各ラウンド $t$ に対して局所的な信頼イベント $E_t$ を構築する。
2. 一定の探索パラメータ： これらの局所的イベントを利用することで、著者らは GP-UCB を一定の探索パラメータ $\beta_t \equiv \beta$ で実行できることを示している。
3. 離散化と裾（Tail）の境界： 証明は、局所的な信頼イベント上での毎ラウンドの UCB 後悔界と、稀な補集合イベントに対するアルゴリズムに依存しない境界を組み合わせるものである。これには以下が含まれる：
   • サイズ $\tau^d$ の空間グリッド離散化。
   • 離散化誤差を制御するための微分に関する裾の境界（仮定1）。
   • 関数のスパン $W_t = \sup f_t - \inf f_t$ に関する劣ガウス集中。
4. 時間減衰する情報利得： 著者らは、時間変動する最大情報利得 $\tilde{\gamma}_T$ に関するより鋭い境界を導出しており、これは事後分散の総和を制御する。彼らは、ブロック分解手法を用いて、$\tilde{\gamma}_T$ を静的な情報利得 $\gamma_N$ およびドリフトパラメータ $\epsilon$ に関連付ける。

主要な貢献と結果

• 一定探索による後悔界： 主要な理論的結果（定理1）は、一定-$\beta$ 型 TV-GP-UCB の期待累積後悔界を確立している：
  $$E[R_T] \le \sqrt{C_1 T \beta \tilde{\gamma}_T} + T C_2 + T \delta C_3$$
  ここで $\tilde{\gamma}_T$ は時間変動する最大情報利得である。この境界は、$\beta$ が $T$ に依存してスケールする必要なく、任意の固定されたドリフト率 $\epsilon > 0$ に対して成立する。
• より鋭い情報利得のスケーリング： 著者らは、時間変動する情報利得に関する新しい境界を導出している。もし静的な情報利得が $\gamma_N = \tilde{O}(N^q)$ を満たすならば、持続的ドリフト領域（ホライゾン $T$ が有効ブロック長を超える場合）において、平均情報利得は次のようにスケールする：
  $$\frac{\tilde{\gamma}_T}{T} = \tilde{O}\left(\epsilon^{\frac{2(1-q)}{4-q}}\right)$$
  したがって、期待平均後悔は次のようにスケールする：
  $$\frac{E[R_T]}{T} = \tilde{O}\left(\epsilon^{\frac{1-q}{4-q}}\right)$$
  二乗指数カーネル（$q=0$）の場合、これは平均後悔 $\tilde{O}(\epsilon^{1/4})$ を与える。
• 境界から示唆される探索パラメータ： 解析により、後悔境界の項のバランスを取ることで示唆される最適な一定 $\beta$（$\beta_{opt}$ と表記）は、ドリフト率の逆数に対して対数的に依存することが明らかになった：
  $$\beta_{opt} \propto \log(1/\epsilon)$$
  これは、$\beta_t$ が $\epsilon$ と独立していた従来のスケジュールとは対照的である。論文では、ドリフトが緩やかになるにつれ（$\epsilon \to 0$）、過去の観測がより長く情報を保持するため、事後分散が減少すること、そしてより大きな $\beta$ が残存する不確実性を減らすことへの価値を高めることでこれを補償すると論じている。
• 実現後悔の保証： 論文は、実現された後悔に関する事後（post-hoc）および規定信頼（prescribed-confidence）の両方の保証を提供している。規定信頼の設定では、アルゴリズムは一定の $\beta$ で動作しながら、失敗確率 $\omega$ に対する対数依存性を持つ高確率の後悔境界を達成できる。
• サンプリング頻度の適応： 本フレームワークは、サンプリング頻度が変化する場合の $\beta$ の調整に関するヒューリスティックを提供する。もし観測が $\Delta$ 時間単位ごとに収集される場合、有効なドリフトは $\epsilon_\Delta = 1 - (1-\epsilon)^\Delta$ となり、示唆される $\beta$ は $\log(1/\epsilon_\Delta)$ に比例してスケールする。

意義と主張
本論文は、その解析が、時間とともに増大する探索スケジュール（これが長いホライゾンにおいて性能を悪化させ、チューニングを困難にする）を必要とするという、時間変動型 GP バンディット文献における繰り返される制限を解決することを主張している。グローバルな信頼イベントから局所的な信頼イベントへと移行することで、一定の探索パラメータを用いても厳密な性能保証を維持できることを著者らは示している。

その意義は以下の点にある：

1. 長期ホライゾンにおけるスケーリングの改善： 時間に関する和による和集合（union bound）によって、主要な後悔項にしばしば導入される $\sqrt{\log T}$ という因子を取り除いたこと。
2. 明示的なドリフト依存性： 探索パラメータが、単に時間 $t$ だけでなく、環境のドリフト率 $\epsilon$ に対してどのようにスケールすべきかについての理論的根拠を提供したこと。
3. より鋭い境界： 以前の研究（例：Bogunovic et al. [2016], Imamura et al. [2020]）と比較して、時間変動する情報利得に対してよりタイトなレートを提供したこと。

実証的検証
著者らは、二乗指数カーネルを用いた2次元ドメインにおけるシミュレーション研究によって、理論的知見を裏付けている。時間変動する事後分布を効率的に扱うためにカルマンフィルタの実装を用い、$T=10,000$ ラウンドをシミュレートしている。結果は以下を確認している：

• 広範な一定 $\beta$ の値が、時間とともに対数的に増大するヒューリスティックを凌駕すること。
• 経験的に最適な一定 $\hat{\beta}_{opt}$ が $-\log(\epsilon)$ に対して線形に増加することであり、これは理論的予測 $\beta_{opt} \propto \log(1/\epsilon)$ を検証している。

限界と今後の方向性
著者らは、自身の解析が、マルコフ・ドリフト・モデルによって誘導される特定の幾何学的時間カーネルに依存していることを指摘している。これらの保証をより一般的な時間カーネルに拡張することは、未解決の課題である。さらに、現在の解析はドリフトパラメータ $\epsilon$ が既知であることを前提としているため、$\epsilon$ が未知の場合に $\beta$ をオンラインで適応させることは、今後の研究課題として示唆されている。また、論文では、一定探索の結果は「正のドリフト（positive-drift）」に関する結果であり、$\epsilon=0$ における標準的な静的劣線形後悔の保証を回復するものではない（それには別途の解析が必要である）ことも認めている。