スペクトル・トンプソン・サンプリング

arXiv cs.LG / 2026/4/16

💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、隣接するノードで期待報酬が類似しているグラフ構造のバンディット問題に対するトンプソン・サンプリングの変種であるSpectral Thompson Sampling（SpectralTS）を提案する。
従来のTSの解析・ツールは、選択肢の数に対してスケールしづらいことがあると主張し、実世界のグラフで小さくなることが期待される「有効次元（effective dimension）」d を用いてこの問題に対処する。
理論結果により、SpectralTSは高い確率でおおよそ d*√(T ln N) の後悔（regret）スケーリングを達成し、既知の最良水準の上界のオーダーに一致しつつ、計算効率を改善することが示される。
著者らは、SpectralTSが合成実験と実データの両方で競争力があることを報告しており、レコメンドシステムや計算広告といった応用に実用的価値があることを示唆している。