論文の概要: Graph Feedback Bandits with Similar Arms
- arxiv url: http://arxiv.org/abs/2405.11171v1
- Date: Sat, 18 May 2024 04:20:14 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-21 19:07:29.615021
- Title: Graph Feedback Bandits with Similar Arms
- Title（参考訳）: 類似アームを用いたグラフフィードバックバンド
- Authors: Han Qi, Guo Fei, Li Zhu,
- Abstract要約: グラフフィードバックを用いたマルチアームバンディット問題について検討する。
UCBに基づく2つのアルゴリズムを導入する: D-UCBは問題非依存の後悔上界、C-UCBは問題依存の上界である。
- 参考スコア（独自算出の注目度）: 9.701475722399646
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the stochastic multi-armed bandit problem with graph feedback. Motivated by the clinical trials and recommendation problem, we assume that two arms are connected if and only if they are similar (i.e., their means are close enough). We establish a regret lower bound for this novel feedback structure and introduce two UCB-based algorithms: D-UCB with problem-independent regret upper bounds and C-UCB with problem-dependent upper bounds. Leveraging the similarity structure, we also consider the scenario where the number of arms increases over time. Practical applications related to this scenario include Q\&A platforms (Reddit, Stack Overflow, Quora) and product reviews in Amazon and Flipkart. Answers (product reviews) continually appear on the website, and the goal is to display the best answers (product reviews) at the top. When the means of arms are independently generated from some distribution, we provide regret upper bounds for both algorithms and discuss the sub-linearity of bounds in relation to the distribution of means. Finally, we conduct experiments to validate the theoretical results.
- Abstract（参考訳）: 本稿では,グラフフィードバックを用いた確率的マルチアームバンディット問題について検討する。
臨床試験とレコメンデーションの問題に動機付けられ、2つの腕が類似している場合(つまり、その手段が十分近い場合)に繋がると仮定する。
我々は、この新たなフィードバック構造に対する後悔の低い境界を確立し、問題非依存の後悔の上限を持つD-UCBと問題依存の上限を持つC-UCBという2つの UCB ベースのアルゴリズムを導入する。
類似性構造を利用することで、時間とともに腕の数が増加するシナリオも検討する。
このシナリオに関連する実践的なアプリケーションとしては、Q\&Aプラットフォーム(Reddit、Stack Overflow、Quora)や、AmazonとFlipkartの製品レビューなどがある。
回答(製品レビュー)はWebサイトに継続的に表示され、そのゴールは、最高の回答(製品レビュー)をトップに表示することです。
ある分布からアームの手段が独立に生成されるとき、両アルゴリズムに後悔すべき上限を与え、手段の分布に関して境界の準線型性について議論する。
最後に,理論結果の検証実験を行った。
関連論文リスト
- PageRank Bandits for Link Prediction [72.61386754332776]
リンク予測は、リコメンダシステムやナレッジグラフ補完といった幅広いアプリケーションを用いたグラフ学習において重要な問題である。
本稿では,リンク予測を逐次的意思決定プロセスとして再構成し,各リンク予測インタラクションを逐次的に行う。
本稿では,PageRankとコンテキスト的帯域を結合した新しい融合アルゴリズム PRB (PageRank Bandits) を提案する。
論文 参考訳（メタデータ） (2024-11-03T02:39:28Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Combinatorial Bandits for Maximum Value Reward Function under Max
Value-Index Feedback [9.771002043127728]
本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。
有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。
我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
論文 参考訳（メタデータ） (2023-05-25T14:02:12Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms [59.8188496313214]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z) - Learning with Instance Bundles for Reading Comprehension [61.823444215188296]
質問応答スコアを複数の関連インスタンスで比較する新しい監視手法を提案する。
具体的には、密接に対照的な質問や回答のさまざまな近所でこれらのスコアを正規化します。
2つのデータセット上のインスタンスバンドルによるトレーニングの有効性を実証的に実証する。
論文 参考訳（メタデータ） (2021-04-18T06:17:54Z) - Contextual Blocking Bandits [35.235375147227124]
我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。
アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。
我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
論文 参考訳（メタデータ） (2020-03-06T20:34:42Z) - Pair-Matching: Links Prediction with Adaptive Queries [7.22341371511072]
グラフが2つのコミュニティを持つブロックモデル(SBM)に従って生成される場合、サブ線形後悔が達成可能であることを示す。
この論文は, コミュニティの数が2より多い場合に, 最適後悔に関する予想によって締めくくられる。
論文 参考訳（メタデータ） (2019-05-17T15:57:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。