論文の概要: Graph Feedback Bandits on Similar Arms: With and Without Graph Structures

• arxiv url: http://arxiv.org/abs/2501.14314v1
• Date: Fri, 24 Jan 2025 08:15:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-27 14:56:28.815284
• Title: Graph Feedback Bandits on Similar Arms: With and Without Graph Structures
• Title（参考訳）: グラフのフィードバックと類似のアーム - グラフ構造の有無
• Authors: Han Qi, Fei Guo, Li Zhu, Qiaosheng Zhang, Xuelong Li,
• Abstract要約: グラフフィードバックを用いたマルチアームバンディット問題について検討する。 本稿では,2つの上位信頼境界(UCB)に基づくアルゴリズムを提案する。 この2つの UCB ベースのアルゴリズムをバルーン設定に拡張する。
• 参考スコア（独自算出の注目度）: 49.02207254933986
• License:
• Abstract: In this paper, we study the stochastic multi-armed bandit problem with graph feedback. Motivated by applications in clinical trials and recommendation systems, we assume that two arms are connected if and only if they are similar (i.e., their means are close to each other). We establish a regret lower bound for this problem under the novel feedback structure and introduce two upper confidence bound (UCB)-based algorithms: Double-UCB, which has problem-independent regret upper bounds, and Conservative-UCB, which has problem-dependent upper bounds. Leveraging the similarity structure, we also explore a scenario where the number of arms increases over time (referred to as the \emph{ballooning setting}). Practical applications of this scenario include Q\&A platforms (e.g., Reddit, Stack Overflow, Quora) and product reviews on platforms like Amazon and Flipkart, where answers (or reviews) continuously appear, and the goal is to display the best ones at the top. We extend these two UCB-based algorithms to the ballooning setting. Under mild assumptions, we provide regret upper bounds for both algorithms and discuss their sub-linearity. Furthermore, we propose a new version of the corresponding algorithms that do not rely on prior knowledge of the graph's structural information and provide regret upper bounds. Finally, we conduct experiments to validate the theoretical results.
• Abstract（参考訳）: 本稿では,グラフフィードバックを用いた確率的マルチアームバンディット問題について検討する。 臨床試験やレコメンデーションシステムへの応用により、両腕が互いに類似している場合(すなわち、その手段が互いに近接している場合)にのみ接続されていると仮定する。 新たなフィードバック構造の下でこの問題に対する後悔の下位境界を確立し,問題非依存の後悔の上位境界を持つDouble-UCBと問題依存の上位境界を持つReserve-UCBという2つのアッパー信頼境界(UCB)ベースのアルゴリズムを導入する。 類似性構造を利用して、時間とともに腕の数が増加するシナリオも探求する(「emph{ballooning setting}」と呼ばれる)。 このシナリオの実践的な応用としては、Q\&Aプラットフォーム(Reddit、Stack Overflow、Quoraなど)や、AmazonやFlipkartのようなプラットフォーム上の製品レビューがある。 この2つの UCB ベースのアルゴリズムをバルーン設定に拡張する。 軽度の仮定では、両方のアルゴリズムに後悔の上限を与え、それらの部分線型性について議論する。 さらに,グラフの構造情報の事前知識に依存しない新しいアルゴリズムを提案する。 最後に,理論結果の検証実験を行った。

関連論文リスト

• PageRank Bandits for Link Prediction [72.61386754332776]
  リンク予測は、リコメンダシステムやナレッジグラフ補完といった幅広いアプリケーションを用いたグラフ学習において重要な問題である。 本稿では,リンク予測を逐次的意思決定プロセスとして再構成し,各リンク予測インタラクションを逐次的に行う。 本稿では,PageRankとコンテキスト的帯域を結合した新しい融合アルゴリズム PRB (PageRank Bandits) を提案する。
  論文  参考訳（メタデータ） (2024-11-03T02:39:28Z)
• Graph Feedback Bandits with Similar Arms [9.701475722399646]
  グラフフィードバックを用いたマルチアームバンディット問題について検討する。 UCBに基づく2つのアルゴリズムを導入する: D-UCBは問題非依存の後悔上界、C-UCBは問題依存の上界である。
  論文  参考訳（メタデータ） (2024-05-18T04:20:14Z)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。 学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。 コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
  論文  参考訳（メタデータ） (2021-06-18T15:01:01Z)
• Beyond Bandit Feedback in Online Multiclass Classification [17.07011090727996]
  学習者のフィードバックが任意の有向グラフによって決定されるような環境で,オンライン多クラス分類の問題について検討する。 任意のフィードバックグラフで動作する,初のオンラインマルチクラスアルゴリズムであるGappletronを紹介する。
  論文  参考訳（メタデータ） (2021-06-07T13:22:30Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)
• Pair-Matching: Links Prediction with Adaptive Queries [7.22341371511072]
  グラフが2つのコミュニティを持つブロックモデル(SBM)に従って生成される場合、サブ線形後悔が達成可能であることを示す。 この論文は, コミュニティの数が2より多い場合に, 最適後悔に関する予想によって締めくくられる。
  論文  参考訳（メタデータ） (2019-05-17T15:57:37Z)

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

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