論文の概要: Spectral Thompson sampling

• arxiv url: http://arxiv.org/abs/2604.13739v1
• Date: Wed, 15 Apr 2026 11:27:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-16 20:38:32.50694
• Title: Spectral Thompson sampling
• Title（参考訳）: スペクトルトンプソンサンプリング
• Authors: Tomas Kocak, Michal Valko, Remi Munos, Shipra Agrawal,
• Abstract要約: 帯域幅問題に対してSpectralTSアルゴリズムを記述・解析する。 我々のアルゴリズムは、合成データと実世界のデータの両方で競合することを示す。
• 参考スコア（独自算出の注目度）: 14.850644283055388
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Thompson Sampling (TS) has attracted a lot of interest due to its good empirical performance, in particular in the computational advertising. Though successful, the tools for its performance analysis appeared only recently. In this paper, we describe and analyze SpectralTS algorithm for a bandit problem, where the payoffs of the choices are smooth given an underlying graph. In this setting, each choice is a node of a graph and the expected payoffs of the neighboring nodes are assumed to be similar. Although the setting has application both in recommender systems and advertising, the traditional algorithms would scale poorly with the number of choices. For that purpose we consider an effective dimension d, which is small in real-world graphs. We deliver the analysis showing that the regret of SpectralTS scales as d*sqrt(T ln N) with high probability, where T is the time horizon and N is the number of choices. Since a d*sqrt(T ln N) regret is comparable to the known results, SpectralTS offers a computationally more efficient alternative. We also show that our algorithm is competitive on both synthetic and real-world data.
• Abstract（参考訳）: Thompson Sampling (TS) はその優れた経験的性能、特に計算広告によって多くの関心を集めている。 成功したものの、そのパフォーマンス分析のためのツールは、最近しか現れなかった。 本稿では,帯域幅問題に対するSpectralTSアルゴリズムについて述べる。 この設定では、それぞれの選択はグラフのノードであり、隣接するノードの期待された支払いは類似していると仮定される。 この設定はレコメンデーションシステムと広告の両方に応用できるが、従来のアルゴリズムは選択数に乏しい。 そのため、実世界のグラフでは小さい実次元 d を考える。 我々は、SpectralTS の後悔は高い確率で d*sqrt(T ln N) としてスケールし、T は時間的地平線、N は選択数であることを示す。 d*sqrt(T ln N)の後悔は既知の結果に匹敵するので、SpectralTSは計算的により効率的な代替手段を提供する。 また、我々のアルゴリズムは、合成データと実世界のデータの両方で競合することを示した。

関連論文リスト

• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  SWING: Space Walks for Implicit Network Graphsはグラフ上のグラフランダム特徴を含む計算アルゴリズムの新しいクラスである。 SWINGの詳細な解析を行い、様々なiグラフのクラスで徹底的な実験を行い、それを補完する。
  論文  参考訳（メタデータ） (2026-02-13T08:12:38Z)
• Graph Neural Thompson Sampling [18.83205413952483]
  グラフ構造データ上に定義された報酬関数を持つオンライン意思決定問題を考える。 次に,グラフニューラルネットワークを用いたトンプソンサンプリング(TS)アルゴリズムであるtextttGNN-TSを提案する。
  論文  参考訳（メタデータ） (2024-06-15T16:45:27Z)
• Feel-Good Thompson Sampling for Contextual Dueling Bandits [49.450050682705026]
  FGTS.CDBという名前のトンプソンサンプリングアルゴリズムを提案する。 われわれのアルゴリズムの核心は、デュエルバンディットに適した新しいFeel-Good探索用語である。 我々のアルゴリズムは最小限の誤差、すなわち $tildemathcalO(dsqrt T)$, $d$ はモデル次元、$T$ は時間水平線である。
  論文  参考訳（メタデータ） (2024-04-09T04:45:18Z)
• Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
  オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。 本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
  論文  参考訳（メタデータ） (2023-10-21T18:38:13Z)
• Multi-armed Bandit Learning on a Graph [0.0]
  そこで,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化するグラフバンドイットと呼ばれるMABの拡張について検討する。 我々は,楽観主義の原理を用いて長期探査・探索のバランスをとる学習アルゴリズムG-UCBを設計する。 提案アルゴリズムは,ノード数として$O(sqrt|S|Tlog(T)+D|S|log T)$学習後悔を実現する。
  論文  参考訳（メタデータ） (2022-09-20T02:31:42Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• Maillard Sampling: Boltzmann Exploration Done Optimally [11.282341369957216]
  この論文は、$K$武装バンディット問題に対するランダム化アルゴリズムを示す。 メイラードサンプリング(MS)は、各アームを閉じた形で選択する確率を計算する。 最適性を失わずに$sqrtKTlogK$に制限された最小値を改善するMS$+$というMSの変種を提案する。
  論文  参考訳（メタデータ） (2021-11-05T06:50:22Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling [83.48992319018147]
  プレイヤーが過去の観測結果に基づいて逐次意思決定を行い、累積報酬を最大化する文脈的帯域幅問題を考える。 この問題を解決する自然な方法は、ステップごとの時間とメモリの複雑さを一定に抑えるために、オンライン勾配降下(SGD)を適用することである。 本研究では,オンラインSGDが一般化線形帯域問題に適用可能であることを示す。 過去の情報を活用するためにシングルステップのSGD更新を利用するSGD-TSアルゴリズムは、全時間複雑度で$tildeO(sqrtT)$ regretを達成する。
  論文  参考訳（メタデータ） (2020-06-07T01:12:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。