論文の概要: Decentralized Learning Dynamics in the Gossip Model
- arxiv url: http://arxiv.org/abs/2306.08670v1
- Date: Wed, 14 Jun 2023 17:59:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-16 17:52:40.286948
- Title: Decentralized Learning Dynamics in the Gossip Model
- Title(参考訳): Gossipモデルにおける分散学習ダイナミクス
- Authors: John Lazarsfeld, Dan Alistarh
- Abstract要約: ゴシップモデルにおけるメモリ制限ノードの分散マルチアーム帯域設定について検討した。
我々は、これらの分散力学のグローバル進化と、ある種の「ゼロサム」乗算重み更新アルゴリズムとの関連性を示す。
- 参考スコア(独自算出の注目度): 27.761221746022365
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a distributed multi-armed bandit setting among a population of $n$
memory-constrained nodes in the gossip model: at each round, every node locally
adopts one of $m$ arms, observes a reward drawn from the arm's (adversarially
chosen) distribution, and then communicates with a randomly sampled neighbor,
exchanging information to determine its policy in the next round. We introduce
and analyze several families of dynamics for this task that are decentralized:
each node's decision is entirely local and depends only on its most recently
obtained reward and that of the neighbor it sampled. We show a connection
between the global evolution of these decentralized dynamics with a certain
class of "zero-sum" multiplicative weight update algorithms, and we develop a
general framework for analyzing the population-level regret of these natural
protocols. Using this framework, we derive sublinear regret bounds under a wide
range of parameter regimes (i.e., the size of the population and number of
arms) for both the stationary reward setting (where the mean of each arm's
distribution is fixed over time) and the adversarial reward setting (where
means can vary over time). Further, we show that these protocols can
approximately optimize convex functions over the simplex when the reward
distributions are generated from a stochastic gradient oracle.
- Abstract(参考訳): 我々は,ゴシップモデルにおけるメモリ制限ノード数$n$の分散マルチアームバンディットについて検討し,各ラウンドにおいて各ノードが$m$のアームの1つを局所的に採用し,アームの分布から引き出された報酬を観測し,次にランダムにサンプリングされた隣人と通信し,次のラウンドでその方針を決定する。
各ノードの決定は完全にローカルであり、最近取得した報酬とサンプルした隣接ノードのみに依存する。
我々は,これらの分散ダイナミクスのグローバル進化と,ある種の「ゼロサム」乗算重み更新アルゴリズムとの関係を示し,これらの自然プロトコルの集団レベルの後悔を分析するための汎用フレームワークを開発した。
この枠組みを用いて、固定的な報酬設定(各腕の分布の平均が時間とともに固定される)と敵対的な報酬設定(時間とともに変化しうる手段)について、幅広いパラメータ規則(すなわち、人口と武器の数)の下でサブ線形後悔境界を導出する。
さらに,これらのプロトコルは,確率的勾配 oracle から報酬分布が生成される場合に,simplex 上の凸関数を近似的に最適化できることを示した。
関連論文リスト
- 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) - Federated Natural Policy Gradient Methods for Multi-task Reinforcement
Learning [49.65958529941962]
フェデレート強化学習(RL)は、ローカルデータトラジェクトリを共有することなく、複数の分散エージェントの協調的な意思決定を可能にする。
本研究では,各エージェントがそれぞれのタスクに対応する個別の報酬関数を持つマルチタスク設定について考察する。
我々は、分散された方法で全てのエージェントの割引された全報酬の総和を最大化する、世界的な最適政策を学習する。
論文 参考訳(メタデータ) (2023-11-01T00:15:18Z) - Local Optimization Achieves Global Optimality in Multi-Agent
Reinforcement Learning [139.53668999720605]
本稿では,各エージェントのローカルポリシーをバニラPPOと同様に更新するマルチエージェントPPOアルゴリズムを提案する。
マルコフゲームにおける標準正則条件と問題依存量により、我々のアルゴリズムはサブリニアレートで大域的最適ポリシーに収束することを示す。
論文 参考訳(メタデータ) (2023-05-08T16:20:03Z) - Federated Learning for Heterogeneous Bandits with Unobserved Contexts [0.0]
我々は、未知のコンテキストを持つ多腕コンテキスト包帯のフェデレーション問題について検討する。
線形パラメタライズされた報酬関数に対して,除去に基づくアルゴリズムを提案し,後悔の束縛を証明した。
論文 参考訳(メタデータ) (2023-03-29T22:06:24Z) - Distributed Stochastic Bandit Learning with Context Distributions [0.0]
本研究では,未知のコンテキストを持つ分散マルチアームコンテキスト帯域幅の問題について検討する。
本モデルでは, エージェントはコンテキスト分布のみを観察し, エージェントに正確なコンテキストが不明である。
我々のゴールは、累積報酬を最大化するために最適な行動列を選択する分散アルゴリズムを開発することである。
論文 参考訳(メタデータ) (2022-07-28T22:00:11Z) - Convergence Rates of Average-Reward Multi-agent Reinforcement Learning
via Randomized Linear Programming [41.30044824711509]
我々は,グローバル報酬が地域報酬の総和であり,共同政策がエージェントの限界と州全体の可観測性に分解される場合に焦点を当てる。
エージェントが局所的なサドル点問題を解き、局所的な重み付き平均化を行うマルチエージェント拡張を開発する。
準グロブリー最適解を得るためのサンプルの複雑さは、状態空間と作用空間の濃度に対する厳密な依存と一致することを確かめる。
論文 参考訳(メタデータ) (2021-10-22T03:48:41Z) - Dimension-Free Rates for Natural Policy Gradient in Multi-Agent
Reinforcement Learning [22.310861786709538]
協調型マルチエージェント強化学習のためのスケーラブルなアルゴリズムを提案する。
このアルゴリズムは,次元自由な統計量と計算量とで,グローバルな最適ポリシーに収束することを示す。
論文 参考訳(メタデータ) (2021-09-23T23:38:15Z) - Locality Matters: A Scalable Value Decomposition Approach for
Cooperative Multi-Agent Reinforcement Learning [52.7873574425376]
協調型マルチエージェント強化学習(MARL)は,エージェント数で指数関数的に大きい状態空間と動作空間により,スケーラビリティの問題に直面する。
本稿では,学習分散実行パラダイムに局所報酬を組み込んだ,新しい価値に基づくマルチエージェントアルゴリズム LOMAQ を提案する。
論文 参考訳(メタデータ) (2021-09-22T10:08:15Z) - A Distributional Analysis of Sampling-Based Reinforcement Learning
Algorithms [67.67377846416106]
定常ステップサイズに対する強化学習アルゴリズムの理論解析に対する分布的アプローチを提案する。
本稿では,TD($lambda$)や$Q$-Learningのような値ベースの手法が,関数の分布空間で制約のある更新ルールを持つことを示す。
論文 参考訳(メタデータ) (2020-03-27T05:13:29Z) - Decentralized MCTS via Learned Teammate Models [89.24858306636816]
本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。
深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
論文 参考訳(メタデータ) (2020-03-19T13:10:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。