論文の概要: Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks
- arxiv url: http://arxiv.org/abs/2510.22811v1
- Date: Sun, 26 Oct 2025 19:53:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-28 19:54:32.562321
- Title: Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks
- Title（参考訳）: Erdés-Rényiランダムネットワーク上の分散マルチエージェントバンド
- Authors: Jingyuan Liu, Hao Qiu, Lin Yang, Mengfan Xu,
- Abstract要約: ランダム通信グラフ上の不均一報酬を用いた分散マルチエージェントマルチアームバンディット問題について検討する。
本稿では,腕の除去戦略をランダムなゴシップアルゴリズムと統合する完全分散アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 16.410227280444285
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the distributed multi-agent multi-armed bandit problem with heterogeneous rewards over random communication graphs. Uniquely, at each time step $t$ agents communicate over a time-varying random graph $G_t$ generated by applying the Erd\H{o}s-R\'enyi model to a fixed connected base graph $G$ (for classical Erd\H{o}s-R\'enyi graphs, $G$ is a complete graph), where each potential edge in $G$ is randomly and independently present with the link probability $p$. Notably, the resulting random graph is not necessarily connected at each time step. Each agent's arm rewards follow time-invariant distributions, and the reward distribution for the same arm may differ across agents. The goal is to minimize the cumulative expected regret relative to the global mean reward of each arm, defined as the average of that arm's mean rewards across all agents. To this end, we propose a fully distributed algorithm that integrates the arm elimination strategy with the random gossip algorithm. We theoretically show that the regret upper bound is of order $\log T$ and is highly interpretable, where $T$ is the time horizon. It includes the optimal centralized regret $O\left(\sum_{k: \Delta_k>0} \frac{\log T}{\Delta_k}\right)$ and an additional term $O\left(\frac{N^2 \log T}{p \lambda_{N-1}(Lap(G))} + \frac{KN^2 \log T}{p}\right)$ where $N$ and $K$ denote the total number of agents and arms, respectively. This term reflects the impact of $G$'s algebraic connectivity $\lambda_{N-1}(Lap(G))$ and the link probability $p$, and thus highlights a fundamental trade-off between communication efficiency and regret. As a by-product, we show a nearly optimal regret lower bound. Finally, our numerical experiments not only show the superiority of our algorithm over existing benchmarks, but also validate the theoretical regret scaling with problem complexity.
- Abstract（参考訳）: ランダム通信グラフ上の不均一報酬を用いた分散マルチエージェントマルチアームバンディット問題について検討する。
同様に、各ステップにおいて$t$エージェントは、固定連結基底グラフにErd\H{o}s-R\'enyiモデルを適用して生成された時間変化ランダムグラフ$G_t$(古典的Erd\H{o}s-R\'enyi graphsの場合、$G$は完全グラフ)で通信する。
特に、結果のランダムグラフは各ステップで必ずしも接続されない。
各エージェントの腕の報酬は時間不変の分布に従っており、同じアームの報酬分布はエージェントによって異なる場合がある。
目標は、各アームの平均報酬に対する累積的後悔を最小化し、各エージェントの平均報酬の平均として定義することである。
そこで本研究では,アーム除去戦略をランダムなゴシップアルゴリズムと統合した完全分散アルゴリズムを提案する。
理論的には、後悔の上限は次数$\log T$ であり、高い解釈可能であり、そこでは$T$ が時間的地平線である。
O\left(\sum_{k: \Delta_k>0} \frac{\log T}{\Delta_k}\right)$と追加の$O\left(\frac{N^2 \log T}{p \lambda_{N-1}(Lap(G))} + \frac{KN^2 \log T}{p}\right)$である。
この用語は、$G$の代数接続$\lambda_{N-1}(Lap(G))$とリンク確率$p$の影響を反映しており、通信効率と後悔の基本的なトレードオフを強調している。
副産物として、ほぼ最適な後悔の少ない境界を示す。
最後に、我々の数値実験は、既存のベンチマークよりもアルゴリズムの優位性を示すだけでなく、問題複雑性に対する理論的後悔のスケーリングを検証した。
関連論文リスト
- Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文 参考訳（メタデータ） (2025-06-30T13:27:39Z) - On the optimal regret of collaborative personalized linear bandits [15.661920010658626]
本稿では,協調的パーソナライズされたリニアバンディットにおける最適後悔について検討する。
我々は,エージェント数,相互作用ラウンド,不均一性の程度が共に後悔にどう影響するかを特徴付ける情報理論の下限を提供する。
私たちの結果は、いつ、いつ、コラボレーションが最適な後悔の束縛でどのように役立つか、完全な特徴を与えます。
論文 参考訳（メタデータ） (2025-06-19T00:56:31Z) - p-Mean Regret for Stochastic Bandits [52.828710025519996]
単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。
我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
論文 参考訳（メタデータ） (2024-12-14T08:38:26Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Cooperative Multi-Agent Graph Bandits: UCB Algorithm and Regret Analysis [5.02063914741425]
Zhang, Johansson, Li が導入したグラフバンディット問題のマルチエージェント拡張として,マルチエージェントグラフバンディット問題を定式化する。
上信頼境界(UCB)に基づく学習アルゴリズムであるMulti-G-UCBを提案し、T$のステップに対する期待された後悔が$O(gamma Nlog(T)[sqrtKT + DK])$で束縛されていることを証明した。
論文 参考訳（メタデータ） (2024-01-18T21:36:17Z) - Fair Multi-Agent Bandits [14.614647884175657]
残念な$Oleft(N3 log fracBDelta f(log T) log T right)$, where $f(t)$ は infinity に $t$ で分岐する任意の関数である。
これにより、オーダー$O(f(log T) log T )$と同じ上限を持つ前の結果を大幅に改善するが、エージェントの数に指数関数的に依存する。
論文 参考訳（メタデータ） (2023-06-07T15:05:53Z) - Improved High-Probability Regret for Adversarial Bandits with
Time-Varying Feedback Graphs [62.52390282012508]
我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。
提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。
また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T04:36:15Z) - Robust Multi-Agent Bandits Over Undirected Graphs [26.26185074977412]
我々は、正直なエージェントがネットワーク上で協力し、後悔を最小限に抑えるマルチエージェント・マルチアーム・バンディット・セッティングを考える。
完全なグラフのケース以上に状況が悪くなることを示す。
我々は,$i$-thエージェントが任意の連結および無向グラフ上で$O(d_textmal(i) + K/n) log(T)/Delta)$を後悔する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-28T20:21:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。