論文の概要: Multi-agent Multi-armed Bandit with Fully Heavy-tailed Dynamics
- arxiv url: http://arxiv.org/abs/2501.19239v1
- Date: Fri, 31 Jan 2025 15:53:14 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-03 14:03:28.318985
- Title: Multi-agent Multi-armed Bandit with Fully Heavy-tailed Dynamics
- Title（参考訳）: フルヘビーテールダイナミクスを有するマルチエージェントマルチアームバンド
- Authors: Xingyu Wang, Mengfan Xu,
- Abstract要約: 分散マルチエージェント・マルチアーム・バンディットを重み付き設定で検討し、クライアントが重み付き次数分布を持つスパースランダムグラフ上で通信する。
私たちは、現実世界のシステムにおける複数のクライアント間の通信と推論のダイナミクスと課題を捉えた、このような完全にヘビーテールのシナリオに最初に取り組みました。
- 参考スコア（独自算出の注目度）: 5.54892060291103
- License:
- Abstract: We study decentralized multi-agent multi-armed bandits in fully heavy-tailed settings, where clients communicate over sparse random graphs with heavy-tailed degree distributions and observe heavy-tailed (homogeneous or heterogeneous) reward distributions with potentially infinite variance. The objective is to maximize system performance by pulling the globally optimal arm with the highest global reward mean across all clients. We are the first to address such fully heavy-tailed scenarios, which capture the dynamics and challenges in communication and inference among multiple clients in real-world systems. In homogeneous settings, our algorithmic framework exploits hub-like structures unique to heavy-tailed graphs, allowing clients to aggregate rewards and reduce noises via hub estimators when constructing UCB indices; under $M$ clients and degree distributions with power-law index $\alpha > 1$, our algorithm attains a regret bound (almost) of order $O(M^{1 -\frac{1}{\alpha}} \log{T})$. Under heterogeneous rewards, clients synchronize by communicating with neighbors, aggregating exchanged estimators in UCB indices; With our newly established information delay bounds on sparse random graphs, we prove a regret bound of $O(M \log{T})$. Our results improve upon existing work, which only address time-invariant connected graphs, or light-tailed dynamics in dense graphs and rewards.
- Abstract（参考訳）: 分散マルチエージェント・マルチアーム・バンディットをフルヘビーテールの環境で研究し、クライアントはヘビーテールの次数分布を持つスパースランダムグラフ上で通信し、潜在的に無限のばらつきを伴うヘビーテール(均質または異質)報酬分布を観測する。
システム性能を最大化するためには,全クライアントで最上位のグローバル報酬で,グローバルな最適なアームを引っ張ることである。
私たちは、現実世界のシステムにおける複数のクライアント間の通信と推論のダイナミクスと課題を捉えた、このような完全にヘビーテールのシナリオに最初に取り組みました。
均質な設定では、アルゴリズムは重み付きグラフに特有のハブ構造を利用し、クライアントは UCB インデックスを構築する際に、ハブ推定器を介して報酬を集計しノイズを低減できる。
不均一な報酬の下では、クライアントは隣人と通信し、UTB指標で交換推定器を集約することで同期する; 新たに確立された情報遅延境界がスパースランダムグラフに基いて、後悔境界が$O(M \log{T})$であることを証明する。
この結果は、時間不変な連結グラフのみに対処する既存の作業や、高密度グラフや報酬における光尾ダイナミックスに改善される。
関連論文リスト
- Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳（メタデータ） (2025-02-19T06:37:37Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - 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) - Communication-Efficient Federated Group Distributionally Robust Optimization [49.14751984342068]
フェデレーション学習は、異なるクライアントにおけるデータボリュームと分散の不均一性のために、課題に直面します。
グループ分散ロバスト最適化(GDRO)に基づいてこの問題に対処するための既存のアプローチは、しばしば高い通信とサンプルの複雑さをもたらす。
本研究では, 通信効率の高いFederated Group Distributionally Robust Optimizationに適したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-10-08T21:07:53Z) - Distributed Optimization via Kernelized Multi-armed Bandits [6.04275169308491]
分散最適化問題を異種報酬設定によるマルチエージェントカーネル化されたマルチアームバンディット問題としてモデル化する。
我々は,カーネルの一般的なクラスに対して,サブ線形なリフレッシュバウンドを実現するために,完全に分散化されたアルゴリズムであるマルチエージェントIGP-UCB(MA-IGP-UCB)を提案する。
また,Multi-agent Delayed IGP-UCB (MAD-IGP-UCB)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-07T21:57:48Z) - Fed-GraB: Federated Long-tailed Learning with Self-Adjusting Gradient
Balancer [47.82735112096587]
本稿では,各クライアントが局所的にヘテロジニアスなデータセットを保持するFed-LT(Federated Long-tailed Learning)タスクについて検討する。
本稿では,SGB(Self-Natural Gradient Balancer)モジュールからなる$textttFed-GraB$という手法を提案する。
我々は、CIFAR-10-LT、CIFAR-100-LT、ImageNet-LT、iistなどの代表的なデータセットに対して、textttFed-GraB$が最先端のパフォーマンスを達成することを示す。
論文 参考訳（メタデータ） (2023-10-11T15:28:39Z) - Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with
Heterogeneous Rewards [14.822625665220068]
環境によって提供される時間依存ランダムグラフによって複数のクライアントが接続される分散マルチエージェントマルチアームバンディット問題について検討する。
目標は、コラボレーションを通じてシステム全体の後悔を最小化することです。
論文 参考訳（メタデータ） (2023-06-08T22:37:24Z) - Rate-Distortion Theoretic Bounds on Generalization Error for Distributed
Learning [9.00236182523638]
本稿では,統計的分散学習アルゴリズムの一般化誤差の新しい上限を確立するために,レート歪み理論のツールを用いる。
境界は各クライアントのアルゴリズムの圧縮性に依存し、他のクライアントのアルゴリズムは圧縮されない。
論文 参考訳（メタデータ） (2022-06-06T13:21:52Z) - Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。
すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
論文 参考訳（メタデータ） (2022-05-12T19:46:35Z) - Low-Latency Federated Learning over Wireless Channels with Differential
Privacy [142.5983499872664]
フェデレートラーニング(FL)では、モデルトレーニングはクライアントに分散し、ローカルモデルは中央サーバによって集約される。
本稿では,各クライアントの差分プライバシ(DP)要件だけでなく,全体としてのトレーニング性能に制約された無線チャネル上でのFLトレーニング遅延を最小限に抑えることを目的とする。
論文 参考訳（メタデータ） (2021-06-20T13:51:18Z) - Faster Non-Convex Federated Learning via Global and Local Momentum [57.52663209739171]
textttFedGLOMOは最初の(一階)FLtexttFedGLOMOアルゴリズムです。
クライアントとサーバ間の通信においても,我々のアルゴリズムは確実に最適である。
論文 参考訳（メタデータ） (2020-12-07T21:05:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。