論文の概要: Heterogeneous Multi-Agent Bandits with Parsimonious Hints
- arxiv url: http://arxiv.org/abs/2502.16128v1
- Date: Sat, 22 Feb 2025 07:46:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-25 15:56:15.544852
- Title: Heterogeneous Multi-Agent Bandits with Parsimonious Hints
- Title（参考訳）: 異種ヒントを有する異種マルチエージェントバンド
- Authors: Amirmahdi Mirfakhar, Xuchuang Wang, Jinhang Zuo, Yair Zick, Mohammad Hajiesmaili,
- Abstract要約: 異種多腕包帯問題 (HMA2B) について検討し, エージェントは腕を引っ張るだけでなく, 低コストの観測(隠れ)をクエリできる。
このフレームワークでは、M$エージェントはそれぞれ$K$のアームにユニークな報酬分布を持ち、$T$のラウンドでは、他のエージェントが腕を引っ張らない場合にのみ引き出すアームの報酬を観察することができる。
目標は、腕を引っ張ることなく必要最小限のヒントをクエリし、時間に依存しない後悔を達成することで、全ユーティリティを最大化することである。
- 参考スコア（独自算出の注目度）: 12.709437751500353
- License:
- Abstract: We study a hinted heterogeneous multi-agent multi-armed bandits problem (HMA2B), where agents can query low-cost observations (hints) in addition to pulling arms. In this framework, each of the $M$ agents has a unique reward distribution over $K$ arms, and in $T$ rounds, they can observe the reward of the arm they pull only if no other agent pulls that arm. The goal is to maximize the total utility by querying the minimal necessary hints without pulling arms, achieving time-independent regret. We study HMA2B in both centralized and decentralized setups. Our main centralized algorithm, GP-HCLA, which is an extension of HCLA, uses a central decision-maker for arm-pulling and hint queries, achieving $O(M^4K)$ regret with $O(MK\log T)$ adaptive hints. In decentralized setups, we propose two algorithms, HD-ETC and EBHD-ETC, that allow agents to choose actions independently through collision-based communication and query hints uniformly until stopping, yielding $O(M^3K^2)$ regret with $O(M^3K\log T)$ hints, where the former requires knowledge of the minimum gap and the latter does not. Finally, we establish lower bounds to prove the optimality of our results and verify them through numerical simulations.
- Abstract（参考訳）: 異種多腕包帯問題 (HMA2B) について検討し, エージェントは腕を引っ張るだけでなく, 低コストの観測(隠れ)をクエリできる。
このフレームワークでは、M$エージェントはそれぞれ$K$のアームにユニークな報酬分布を持ち、$T$のラウンドでは、他のエージェントが腕を引っ張らない場合にのみ引き出すアームの報酬を観察することができる。
目標は、腕を引っ張ることなく必要最小限のヒントをクエリし、時間に依存しない後悔を達成することで、全ユーティリティを最大化することである。
我々はHMA2Bを中央集権化と分散化の両方で研究する。
HCLAの拡張である主集中型アルゴリズムGP-HCLAは、アームプーリングとヒントクエリに中央決定器を使用し、$O(M^4K)$ regret with $O(MK\log T)$ adapt hintsを達成している。
分散化されたセットアップでは,HD-ETC と EBHD-ETC という2つのアルゴリズムが提案され,エージェントは衝突による通信やクエリヒントを停止するまで独立に選択でき,$O(M^3K^2)$ regret with $O(M^3K\log T)$ hints が得られる。
最後に,結果の最適性を証明するために下界を確立し,数値シミュレーションにより検証する。
関連論文リスト
- Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳（メタデータ） (2025-02-19T06:37:37Z) - An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration [3.9901365062418312]
我々は、K$$armed banditフレームワークにおける最適な腕識別問題を考察する。
エージェントは1つのアームではなく、各タイムスロットでアームのサブセットをプレイすることができる。
我々は、$log K$グループを構築し、最適なアームの存在を検出するための確率比テストを実行するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-02-03T15:10:08Z) - Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。
最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。
本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
論文 参考訳（メタデータ） (2025-01-23T12:28:09Z) - Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。
我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。
我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
論文 参考訳（メタデータ） (2024-10-22T19:34:53Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Representative Arm Identification: A fixed confidence approach to identify cluster representatives [7.459521930846415]
マルチアームバンディット(MAB)フレームワークにおける代表腕識別問題について検討する。
RAI問題は、最高の腕や、上位の$K$から$M$を識別するなど、いくつかのよく研究されたMAB問題としてカバーされている。
本稿では,信頼区間の概念に基づく2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-08-26T11:47:52Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。
本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。
Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文 参考訳（メタデータ） (2022-01-23T20:04:15Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z) - Multi-Armed Bandits with Dependent Arms [18.81667618369821]
我々は,従来のマルチアーマド・バンドイット問題(MABP)の変種について検討し,これを従属アームを持つマルチアーマド・バンドイット(Multi-Armed Bandits)と呼ぶ。
複数のアームをまとめてクラスタを形成し、同じクラスタに属するアームの報酬分布は、クラスタの特徴である未知のパラメータの既知の関数である。
UCBの原理に基づく学習アルゴリズムを開発し、これらの追加の側面観測を適切に活用し、探索・探索トレードオフを行う。
論文 参考訳（メタデータ） (2020-10-13T14:00:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。