グラフ上の滑らかな関数に対するスペクトル・バンディット
arXiv stat.ML / 2026/4/21
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- 本論文は、各アームの期待報酬がグラフのノード上で滑らかに変化することを前提とした、グラフ構造付きマルチアーム・バンディット問題を扱っている。
- 推薦対象をグラフのノードとしてモデル化し、その期待評価が隣接ノードと類似するという性質を利用して、コンテンツベース推薦のようなオンライン学習に適用することを目指している。
- 実世界のグラフで小さくなり得る「有効次元（effective dimension）」の概念を導入し、総ノード数ではなく有効次元に対して累積レグレットが良好にスケールすることを狙う。
- 有効次元に対して線形および準線形（sublinear）にスケールする2つのアルゴリズムを提案し、大規模グラフでの効率的な学習を目標としている。
- 実データのコンテンツ推薦実験では、何千ものアイテムに対するユーザ嗜好の推定が、数十ノードの評価だけで学習できることを示している。
