概要: グラフ上の滑らかな関数は、マニフォールド学習や半教師あり学習において幅広い応用があります。本研究では、腕の報酬がグラフ上で滑らかであるバンディット問題を扱います。この枠組みは、コンテンツに基づくレコメンドのような、グラフを含むオンライン学習問題を解くのに適しています。本問題では、推奨できる各アイテムは無向グラフの節点であり、その期待評価は近傍のものと類似しています。目的は、期待評価が高いアイテムを推薦することです。最適な方策に対する累積レグレットが、節点数に対して過度にスケールしないようなアルゴリズムを目指します。特に、実世界のグラフでは小さい「有効次元」の概念を導入し、この有効次元に対して線形および準線形にスケールする、問題を解くための3つのアルゴリズムを提案します。コンテンツ推薦の問題に関する実験では、数千アイテムに対するユーザの嗜好の良い推定器が、数十回の節点評価だけから学習できることを示します。
スペクトル・バンディット
arXiv stat.ML / 2026/4/29
📰 ニュースTools & Practical UsageModels & Research
要点
- この論文は、各アームの報酬が無向グラフ上の滑らかな関数で表される新しいバンディット設定を扱い、コンテンツレコメンドのようなグラフに基づくオンライン学習に適しているとしています。
- 推薦対象のアイテムはグラフのノード選択としてモデル化され、期待評価が近傍ノードと類似するという前提のもとで、最適方策に対する累積リグレットを抑えることを目標にしています。
- グラフのノード数に対して性能が急速に悪化しないようにするため、著者らは「有効次元（effective dimension）」という概念を導入し、実世界のグラフではこれが小さいと主張します。
- 有効次元に依存して有利なリグレットスケーリングを実現する3つのアルゴリズムを提案し、そこには有効次元に対して線形および準線形にスケールする手法が含まれます。
- 実験（コンテンツ推薦）では、数千アイテムに対するユーザ嗜好を、ノード評価は数十回程度で学習できる可能性が示されています。
