論文の概要: Stochastic Contextual Bandits with Graph-based Contexts

• arxiv url: http://arxiv.org/abs/2305.01470v1
• Date: Tue, 2 May 2023 14:51:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-03 14:07:00.246607
• Title: Stochastic Contextual Bandits with Graph-based Contexts
• Title（参考訳）: グラフベースコンテキストを用いた確率的文脈帯域
• Authors: Jittat Fakcharoenphol and Chayutpong Prompak
• Abstract要約: オンライングラフ予測問題を文脈的帯域問題に一般化する。 我々のアルゴリズムは Zimmert と Seldin[AISTAT'19, JMLR'21] による最適帯域幅アルゴリズムに依存している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We naturally generalize the on-line graph prediction problem to a version of stochastic contextual bandit problems where contexts are vertices in a graph and the structure of the graph provides information on the similarity of contexts. More specifically, we are given a graph $G=(V,E)$, whose vertex set $V$ represents contexts with {\em unknown} vertex label $y$. In our stochastic contextual bandit setting, vertices with the same label share the same reward distribution. The standard notion of instance difficulties in graph label prediction is the cutsize $f$ defined to be the number of edges whose end points having different labels. For line graphs and trees we present an algorithm with regret bound of $\tilde{O}(T^{2/3}K^{1/3}f^{1/3})$ where $K$ is the number of arms. Our algorithm relies on the optimal stochastic bandit algorithm by Zimmert and Seldin~[AISTAT'19, JMLR'21]. When the best arm outperforms the other arms, the regret improves to $\tilde{O}(\sqrt{KT\cdot f})$. The regret bound in the later case is comparable to other optimal contextual bandit results in more general cases, but our algorithm is easy to analyze, runs very efficiently, and does not require an i.i.d. assumption on the input context sequence. The algorithm also works with general graphs using a standard random spanning tree reduction.
• Abstract（参考訳）: 我々は、オンライングラフ予測問題を、文脈がグラフ内の頂点であり、グラフの構造がコンテキストの類似性に関する情報を提供する確率的文脈帯域問題のバージョンに自然に一般化する。 より具体的には、グラフ $G=(V,E)$ が与えられ、その頂点集合 $V$ は {\em unknown} の頂点ラベル $y$ の文脈を表す。 確率的文脈的バンディット設定では、同じラベルを持つ頂点は同じ報酬分布を共有する。 グラフラベル予測におけるインスタンス困難という標準的な概念は、ラベルが異なる端点を持つエッジの数として定義されるカットサイズ$f$である。 直線グラフや木に対して、$K$ は腕の数であるような $\tilde{O}(T^{2/3}K^{1/3}f^{1/3})$ の残差を持つアルゴリズムを示す。 本アルゴリズムはzimmert と seldin~ [aistat'19, jmlr'21] による最適確率バンディットアルゴリズムに依存する。 最高の腕が他の腕を上回ると、後悔は$\tilde{O}(\sqrt{KT\cdot f})$に改善される。 後者の場合の後悔のバウンドは、他の最適文脈バンディットと同等であるが、アルゴリズムは解析が容易で、非常に効率的に動作し、入力コンテキストシーケンスのi.i.d.仮定を必要としない。 このアルゴリズムは、標準的なランダムスパンニングツリーリダクションを用いて、一般的なグラフで動作する。

関連論文リスト

• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
  ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。 複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
  論文  参考訳（メタデータ） (2023-06-05T15:35:00Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
  そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。 これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
  論文  参考訳（メタデータ） (2022-09-25T20:00:28Z)
• A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs [21.563733343861713]
  フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。 本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-01T15:14:32Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。 我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。 これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
  論文  参考訳（メタデータ） (2021-01-28T02:39:27Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)

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

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