論文の概要: 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})$であることを証明する。
この結果は、時間不変な連結グラフのみに対処する既存の作業や、高密度グラフや報酬における光尾ダイナミックスに改善される。
関連論文リスト
- Optimal Decentralized Smoothed Online Convex Optimization [9.449153668916098]
マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。
そこで本研究では,マルチエージェントSOCOのための,真に分散化されたアルゴリズムACORDを提案する。
通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
論文 参考訳（メタデータ） (2024-11-13T05:59:04Z) - 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) - Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。
予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。
本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
論文 参考訳（メタデータ） (2022-10-14T13:09:11Z) - 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) - Distributed Optimization over Block-Cyclic Data [48.317899174302305]
本研究では,クライアントの非平衡データと非等化データをブロック循環構造とするフェデレート学習の基礎となる実践的データ特性について考察する。
マルチモデル並列SGD(MM-PSGD)とマルチチェーン並列SGD(MC-PSGD)という2つの新しい分散最適化アルゴリズムを提案する。
提案アルゴリズムは, 従来のフェデレーション平均化アルゴリズムよりも精度が高く, 臨界パラメータの分散に対するロバスト性を保っている。
論文 参考訳（メタデータ） (2020-02-18T09:47:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。