論文の概要: QuACK: A Multipurpose Queuing Algorithm for Cooperative $k$-Armed Bandits

• arxiv url: http://arxiv.org/abs/2410.23867v1
• Date: Thu, 31 Oct 2024 12:20:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-01 17:01:03.207258
• Title: QuACK: A Multipurpose Queuing Algorithm for Cooperative $k$-Armed Bandits
• Title（参考訳）: QuACK: 協調的な$k$-Armedバンドのための多目的キューアルゴリズム
• Authors: Benjamin Howson, Sarah Filippi, Ciara Pike-Burke,
• Abstract要約: 我々は、$m$エージェントのネットワークが協調して最適な行動を見つける、協調的な$k$武器の盗賊問題を研究する。 単一エージェントのバンディットアルゴリズムをマルチエージェント設定に拡張できるブラックボックスリダクションを提供する。
• 参考スコア（独自算出の注目度）: 5.530212768657544
• License:
• Abstract: We study the cooperative stochastic $k$-armed bandit problem, where a network of $m$ agents collaborate to find the optimal action. In contrast to most prior work on this problem, which focuses on extending a specific algorithm to the multi-agent setting, we provide a black-box reduction that allows us to extend any single-agent bandit algorithm to the multi-agent setting. Under mild assumptions on the bandit environment, we prove that our reduction transfers the regret guarantees of the single-agent algorithm to the multi-agent setting. These guarantees are tight in subgaussian environments, in that using a near minimax optimal single-player algorithm is near minimax optimal in the multi-player setting up to an additive graph-dependent quantity. Our reduction and theoretical results are also general, and apply to many different bandit settings. By plugging in appropriate single-player algorithms, we can easily develop provably efficient algorithms for many multi-player settings such as heavy-tailed bandits, duelling bandits and bandits with local differential privacy, among others. Experimentally, our approach is competitive with or outperforms specialised multi-agent algorithms.
• Abstract（参考訳）: 協調的確率的$k$武器の盗聴問題について検討し、$m$エージェントのネットワークが協調して最適な行動を見つける。 特定のアルゴリズムをマルチエージェント設定に拡張することに焦点を当てた、この問題に関するこれまでのほとんどの研究とは対照的に、単一エージェントのバンディットアルゴリズムをマルチエージェント設定に拡張できるブラックボックスの削減を提供する。 バンドイット環境の軽度な仮定の下では、この削減が単一エージェントアルゴリズムの後悔の保証をマルチエージェント設定に転送することを証明している。 これらの保証は、準ガウス環境では厳密であり、加算グラフ依存量までのマルチプレイヤー設定において、近似ミニマックス最適シングルプレイヤーアルゴリズムが極小に近い。 我々の減少と理論的結果も一般的であり、多くの異なる帯域設定に適用できる。 適切なシングルプレイヤーアルゴリズムを組み込むことで、重み付けのバンディットや、局所的な差分プライバシーを持つバンディットのデュエルなど、多数のマルチプレイヤー設定に対して、証明可能な効率のよいアルゴリズムを容易に開発することができる。 実験により,本手法は特殊化マルチエージェントアルゴリズムと競合し,性能が優れていた。

関連論文リスト

• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。 課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。 我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-08-20T13:57:00Z)
• Multi-Player Approaches for Dueling Bandits [58.442742345319225]
  Follow Your Leaderのブラックボックスアプローチの直接的な使用は、この設定の低いバウンダリと一致することを示す。 また,Condorcet-Winnerレコメンデーションプロトコルを用いて,メッセージパッシングによる完全分散アプローチも分析する。
  論文  参考訳（メタデータ） (2024-05-25T10:25:48Z)
• Cooperative Multi-agent Bandits: Distributed Algorithms with Optimal Individual Regret and Constant Communication Costs [46.068883750876886]
  本稿では,単純だが効果的な通信方針を提示し,それを協調的盗賊学習アルゴリズムに統合する。 我々のアルゴリズムは、最適な個人の後悔と絶え間ないコミュニケーションコストという、両方のパラダイムの長所を達成している。
  論文  参考訳（メタデータ） (2023-08-08T15:02:50Z)
• Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences [28.79598714109439]
  両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。 まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。 提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
  論文  参考訳（メタデータ） (2022-02-14T13:37:23Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Multitask Bandit Learning Through Heterogeneous Feedback Aggregation [35.923544685900055]
  我々は,この問題を,一組のプレイヤーが一組のアームと同時に相互作用する,$epsilon$-multi-player multi-armed bandit問題として定式化する。 我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼な有界アルゴリズム、RobostAgg$(epsilon)$を開発する。
  論文  参考訳（メタデータ） (2020-10-29T07:13:28Z)
• Cooperative Multi-Agent Bandits with Heavy Tails [15.609414012418043]
  エージェント群が共通のバンドイット問題と相互作用する,協調的マルチエージェント設定におけるヘビーテールバンドイット問題について検討する。 この設定における既存のバンディットのアルゴリズムは、平均化ベースの通信プロトコルから生じる信頼区間を利用する。 我々は,メッセージパッシングプロトコルを用いたロバストな推定を組み込んだ協調帯域の分散マルチエージェントアルゴリズムであるtextscMP-UCB を提案する。
  論文  参考訳（メタデータ） (2020-08-14T08:34:32Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)

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

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