Spectral bandits for smooth graph functions with applications in recommender systems

技術的概要：滑らかなグラフ関数に対するスペクトルバンディット

問題定式化
本論文は、アームが既知のグラフ $G=(V, E)$ のノードに対応し、アームを引くことによる期待利得がグラフ上で定義された滑らかな関数によって決定される多腕バンディット問題を取り扱います。この設定において、報酬関数 $f$ は、グラフラプラシアン $L$ の固有ベクトルの線形結合であると仮定されます。具体的には、$Q$ が $L$ の固有ベクトルを列として含む場合、ノード $v$ に対する報酬は $f_\alpha(v) = \langle x_v, \alpha^* \rangle$ となります。ここで、$x_v$ は $Q$ の $v$ 行目、$\alpha^*$ は未知の重みベクトルです。

核心的な課題は、ノード数 $N$（したがって特徴空間の次元 $D=N$）が学習プロセスの時間地平 $T$ を大幅に上回る可能性があり（$T < N$）、非常に大きい場合に生じます。通常、累積後悔を環境次元 $D$ またはアーム数 $K$ に比例してスケールさせる標準的な線形バンディットアルゴリズムは、この領域では性能が劣ります。本論文は、真の関数が「滑らか」であると仮定しており、これは大きな固有値に対応する固有ベクトルに関連する係数 $\alpha^*$ が小さく、小さな固有値に対応するものの方が大きいことを意味します。

手法
著者らは、グラフのスペクトル特性を活用して、完全な次元 $N$ ではなく「実効次元」$d$ に比例する後悔の上限を達成する 2 つのアルゴリズムを提案します。

1. 実効次元（$d$）： 本論文は、正則化ラプラシアン $\Lambda = \Lambda_L + \lambda I$ の固有値の成長に基づき、実効次元 $d$ の形式的な定義を導入します。$d$ は、$(d-1)\lambda_d \leq T / \log(1 + T/\lambda)$ を満たす最大の整数として定義されます。この指標は、現実世界のグラフでは通常 $N$ よりもはるかに小さい、問題における「関連する」次元の数を捉えます。

2. SpectralUCB： このアルゴリズムは LinUCB アルゴリズムの修正版です。スペクトル基底を用いて $\alpha^*$ に対する正則化最小二乗推定量を採用します。重要なのは、予測報酬に対する信頼区間を環境次元 $D$ ではなく、実効次元 $d$ を用いて構築することです。アルゴリズムは、$\hat{f}_{\alpha}(v) + c_t \|x_v\|_{V_t^{-1}}$ を最大化するノードを選択します。ここで、$c_t$ は $d$ に依存します。

3. スペクトルトンプソンサンプリング（SpectralTS）： このアルゴリズムはベイズ的アプローチを利用します。$\alpha^*$ に関する事後分布をガウス分布 $N(\hat{\alpha}_t, v^2 V_t^{-1})$ としてモデル化し、維持します。事前共分散は正則化ラプラシアン $\Lambda$ に設定され、滑らかな関数（低固有値成分）の方がより確からしいという仮定を符号化します。各ステップで、事後分布からサンプル $\tilde{\alpha}$ を引き、$x_v^T \tilde{\alpha}$ を最大化するノードを選択します。

主要な貢献と理論的結果

• 新規フレームワーク： これは、利得がグラフ上の滑らかな関数であるバンディット問題を定式化した最初の研究であり、多様体学習・半教師あり学習とオンライン学習を架橋するものです。
• 後悔の上限： 本論文は、SpectralUCB と SpectralTS の両方が、実効次元 $d$ に比例する累積後悔の上限を達成することを証明しています。
  • SpectralUCB： $O(d\sqrt{T \ln T})$。
  • SpectralTS： $O(d\sqrt{T \ln N})$。
    これらの上限は、$d$ がしばしば $N$ よりもはるかに小さいため、$T < N$ の場合でもアルゴリズムが良好に機能することを可能にする点で重要です。
• 計算効率： 著者らは、SpectralTS における計算上の利点を強調しています。SpectralUCB はすべての $N$ 個のアームに対して信頼区間を計算する必要があり（最悪の場合 $D=N$ においてステップあたり $O(N^3)$ の複雑さ）、SpectralTS はパラメータベクトルをサンプリングし、最大値を見つけるだけでよく、これはより効率的に実行可能です（ステップあたり $O(N^2)$）。

実験結果
著者らは、合成データおよび実世界データセットの両方でアルゴリズムを評価しました。

• 合成データ： 真の報酬関数が最初の 3 つの最も滑らかな固有ベクトルの線形結合である Barabási-Albert グラフ（$N=250$）を使用しました。$T < N$ の領域において、SpectralUCB と SpectralTS の両方は、累積後悔の点で、その線形対応物（LinUCB および LinearTS）を大幅に上回りました。SpectralTS はまた、より高速な計算時間を示しました。
• 実世界データ： 映画評価から構築された類似性グラフ上の滑らかな関数としてユーザーの好みをモデル化した MovieLens データセット（$N=2019$ 本の映画）で実験を行いました。結果は合成データでの知見を反映しており、スペクトルアルゴリズムは線形バンディットベースラインよりも低い累積後悔を達成しました。本論文は、数千のアイテムに対するユーザーの好みの良い推定量が、わずか数十のノード評価から学習可能であると指摘しています。

意義と主張
本論文は、スペクトル分解を介してグラフ上の関数の滑らかさを活用することで、ノード数に依存して後悔が悪化することなく、多数のアームを持つオンライン学習問題を解決可能であると主張しています。実効次元 $d$ の導入により、アルゴリズムはグラフ構造の内在的な複雑さに適応できるようになります。この研究は、ユーザーの好みや関心が接続されたノード間で滑らかに変化する傾向がある、コンテンツベースの推薦やソーシャルネットワークにおけるターゲティング広告などの応用を動機としています。著者らは、利用可能な相互作用の数（$T$）が利用可能なアイテムの数（$N$）と比較して小さいシナリオにおいて、彼らのアプローチが特に関連性が高いことを強調しています。