論文の概要: The Price of Decentralization in Top-$K$ Arm Identification
- arxiv url: http://arxiv.org/abs/2608.22120v1
- Date: Sat, 22 Aug 2026 22:22:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-25 18:24:36.947295
- Title: The Price of Decentralization in Top-$K$ Arm Identification
- Title（参考訳）: トップ$Kのアーム識別における分散化の価格
- Abstract要約: マルチエージェント・マルチアーム・バンディットにおけるトップ$K$のジョイントアーム識別について検討する。
エージェントは、ジョイントアームを構成する個々のアクションを同時に選択する。
共有逆同定は1つの普遍対数係数まで最適であることを示す。
- 参考スコア（独自算出の注目度）: 1.3700362496838856
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Cooperative teams often need to agree on the best few options rather than simply accumulate reward, and they must do so while each member sees only a fragment of the team's collective experience. We study this as top-$K$ joint-arm identification in multi-agent multi-armed bandits: at every round $M$ agents simultaneously choose individual actions that compose a joint arm, and the team must ultimately return the $K$ joint arms of highest mean reward. The difficulty is that an agent may not observe the actions of others, their rewards, or either. We treat three observability regimes---(A) shared rewards with hidden actions, (B) observed actions with private rewards, and (C) full asymmetry---and design communication-free elimination algorithms (UCB-Intervals) that reconstruct implicit coordination from whatever signal each regime leaves intact: a shared arm ordering in (A), observable deviations in (B), and enlarged confidence radii under (C). We give matching analyses in both the fixed-budget and fixed-confidence objectives, then fold all three regimes into a single meta-guarantee indexed by a multiplicity $c$ and a consensus factor $ρ$. Our central result is quantitative rather than merely algorithmic: change-of-measure lower bounds show that shared-reward identification is optimal up to one universal logarithmic factor, and that the entire statistical price of removing communication is a multiplicative $ρ^2$ in sample complexity---a fixed $4\times$ penalty under full asymmetry. The resulting stopping time scales as $O\!\left(\sum_{\mathbf{a}} \frac{\log(A^M/δ)}{Δ_{\mathbf{a}}^2}\right)$ and the fixed-budget error as $\exp(-Θ(T/H_1))$, with the dependence on the joint-action count $A^M$ shown to be unavoidable.
- Abstract（参考訳）: 協力チームは報酬を蓄積するよりも、最も少ない選択肢に合意する必要があり、各メンバはチームの集合的な経験の断片しか見ていないのに対して、それを行う必要があります。
我々は、これをマルチエージェントの多腕包帯におけるK$ジョイントアーム識別のトップとして研究し、各ラウンドでM$エージェントは、ジョイントアームを構成する個々のアクションを同時に選択し、チームは最終的に最高平均報酬のK$ジョイントアームを返さなければならない。
難しいのは、エージェントが他人の行動や報酬、あるいはそのどちらかを観察しないことだ。
A) 隠蔽行動による報酬の共有,(B) 私的報酬による行動の観測,(C) 完全な非対称性によるコミュニケーション自由除去アルゴリズム(UCB-Intervals) および(C) コミュニケーション自由除去アルゴリズム(UCB-Intervals) を用いて,各制度が残す信号から暗黙的な調整を再構築する。
固定予算目標と固定信頼目標の両方で一致する解析を行い、次に3つのレギュラーを1つのメタガータンティーに折り畳み、多重度$c$とコンセンサス係数$ρ$でインデックス付けする。
我々の中心的な結果は、単にアルゴリズムではなく定量的である: 測定値の変更 下限は、共有逆同定が1つの普遍対数係数まで最適であることを示し、通信を除去する全体の統計的価格が、完全非対称性の下で固定された4/times$ペナルティであることを示している。
その結果、停止時間は$O\!
\left(\sum_{\mathbf{a}} \frac{\log(A^M/δ)}{Δ_{\mathbf{a}}^2}\right)$ と固定予算誤差は $\exp(-*(T/H_1))$ である。
関連論文リスト
- Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection [48.83076933238825]
我々は,各ラウンドにおいてエージェントが$k$アームのスレートを選択し,それらの$d$次元報酬ベクトルを半帯域フィードバック下で観察する多目的バンディット問題を考える。
この目的を、選択されたアームのサブセットによって誘導される支配的な超体積を通して定式化し、最高のサイズに対して$$$-approximate hypervolume regretを定義する。
ギャップのない後悔境界を持つ$tildeO(dsqrtnkT)$を、ギャップとともにすべてのインスタンスに保持する。
論文 参考訳（メタデータ） (2026-07-28T21:10:39Z) - Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
このモデルは、$M$armと$K$playで構成されている。
各アームには複数の能力があり、各ユニットの能力は報酬関数に関連付けられている。
複数のプレーがアームキャパシティを競う場合、アームキャパシティは第1の優先重みで割り当てられる。
論文 参考訳（メタデータ） (2025-12-25T11:19:09Z) - Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks [16.410227280444285]
ランダム通信グラフ上の不均一報酬を用いた分散マルチエージェントマルチアームバンディット問題について検討する。
本稿では,腕の除去戦略をランダムなゴシップアルゴリズムと統合する完全分散アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-10-26T19:53:52Z) - Heterogeneous Multi-Agent Bandits with Parsimonious Hints [12.709437751500353]
異種多腕包帯問題 (HMA2B) について検討し, エージェントは腕を引っ張るだけでなく, 低コストの観測(隠れ)をクエリできる。
このフレームワークでは、M$エージェントはそれぞれ$K$のアームにユニークな報酬分布を持ち、$T$のラウンドでは、他のエージェントが腕を引っ張らない場合にのみ引き出すアームの報酬を観察することができる。
目標は、腕を引っ張ることなく必要最小限のヒントをクエリし、時間に依存しない後悔を達成することで、全ユーティリティを最大化することである。
論文 参考訳（メタデータ） (2025-02-22T07:46:41Z) - Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳（メタデータ） (2025-02-19T06:37:37Z) - Multi-Agent Stochastic Bandits Robust to Adversarial Corruptions [6.234292942334148]
敵の汚職に頑健なマルチエージェント協調学習アルゴリズムを提案する。
副産物として,本アルゴリズムは,単一エージェントと同種マルチエージェントの両方のシナリオに還元した場合の,最先端の後悔境界も改善する。
論文 参考訳（メタデータ） (2024-11-12T20:20:26Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Collaborative Mean Estimation Among Heterogeneous Strategic Agents: Individual Rationality, Fairness, and Truthful Contribution [11.371461065112422]
我々は、$m$エージェントがベクトル$mu =(mu_k, sigma2)_kin[d]$を推定しようとする協調学習問題を研究する。
独立して作業する代わりに、エージェントはデータを交換し、より安価なサンプルを収集し、コストのかかるデータと引き換えにそれらを共有できるため、コストと推定エラーの両方を削減できる。
論文 参考訳（メタデータ） (2024-07-20T17:45:40Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
本稿では,武器間の相関に関するドメイン知識を捉えた新しい相関バンディットフレームワークを提案する。
C-LUCBで得られた全サンプルは$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$であり、通常の$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$とは対照的である。
論文 参考訳（メタデータ） (2021-09-10T15:41:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。