論文の概要: Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling
- arxiv url: http://arxiv.org/abs/2504.11645v1
- Date: Tue, 15 Apr 2025 22:13:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-17 14:40:15.148298
- Title: Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling
- Title（参考訳）: マルコフサンプリングによる不均一フェデレート確率近似におけるタイター有限時間率の達成
- Authors: Feng Zhu, Aritra Mitra, Robert W. Heath,
- Abstract要約: 我々は,M$エージェントを含む汎用的な近似問題について検討した。
目標は、エージェントがサーバを介して断続的に通信し、エージェントのローカルオペレータの平均のルートを見つけることである。
我々はtexttFedHSA という名の新しいアルゴリズムを開発し、正しい点への収束を保証することを証明した。
- 参考スコア（独自算出の注目度）: 6.549288471493216
- License:
- Abstract: Motivated by collaborative reinforcement learning (RL) and optimization with time-correlated data, we study a generic federated stochastic approximation problem involving $M$ agents, where each agent is characterized by an agent-specific (potentially nonlinear) local operator. The goal is for the agents to communicate intermittently via a server to find the root of the average of the agents' local operators. The generality of our setting stems from allowing for (i) Markovian data at each agent and (ii) heterogeneity in the roots of the agents' local operators. The limited recent work that has accounted for both these features in a federated setting fails to guarantee convergence to the desired point or to show any benefit of collaboration; furthermore, they rely on projection steps in their algorithms to guarantee bounded iterates. Our work overcomes each of these limitations. We develop a novel algorithm titled \texttt{FedHSA}, and prove that it guarantees convergence to the correct point, while enjoying an $M$-fold linear speedup in sample-complexity due to collaboration. To our knowledge, \emph{this is the first finite-time result of its kind}, and establishing it (without relying on a projection step) entails a fairly intricate argument that accounts for the interplay between complex temporal correlations due to Markovian sampling, multiple local steps to save communication, and the drift-effects induced by heterogeneous local operators. Our results have implications for a broad class of heterogeneous federated RL problems (e.g., policy evaluation and control) with function approximation, where the agents' Markov decision processes can differ in their probability transition kernels and reward functions.
- Abstract（参考訳）: 協調強化学習(RL)と時間関連データを用いた最適化により,M$エージェントを含む汎用的確率近似問題について検討し,エージェント固有の(潜在的に非線形な)局所演算子を特徴付ける。
目標は、エージェントがサーバを介して断続的に通信し、エージェントのローカルオペレータの平均のルートを見つけることである。
我々の設定の一般性は許容することに由来する
一 各代理人のマルコフデータ及び
(ii)エージェントの局所作用素の根における不均一性。
これら2つの機能をフェデレートした設定で考慮した最近の限定的な作業は、望ましい点への収束を保証するか、コラボレーションのメリットを示すことに失敗している。
私たちの仕事はこれらの制限を克服します。
提案手法は, 共用によるサンプル複雑度が$M$-foldの線形高速化を享受しながら, 正しい点への収束を保証する新しいアルゴリズムを開発した。
我々の知る限り、 \emph{this はこの種の最初の有限時間結果であり、(射影ステップに依存しない)それを確立するには、マルコフ的サンプリングによる複雑な時間的相関、通信の節約のための複数の局所的なステップ、および異種局所作用素によって誘導されるドリフト効果の間の相互作用を考慮に入れたかなり複雑な議論が必要となる。
この結果は, エージェントのマルコフ決定過程が確率遷移カーネルと報酬関数で異なるような, 関数近似を用いた多種多元連合RL問題(例えば, 政策評価と制御)の幅広いクラスに影響を及ぼす。
関連論文リスト
- Federated Sinkhorn [2.589644824000165]
連合学習環境におけるエントロピー正規化による離散最適輸送問題の解法の可能性について検討する。
同期型と非同期型の両方、およびオール・ツー・オールおよびサーバ・クライアント型通信プロトコルを検討します。
合成データセットのアルゴリズム性能と実世界の金融リスク評価アプリケーションについて実証実験を行った。
論文 参考訳（メタデータ） (2025-02-10T20:29:57Z) - Towards Fast Rates for Federated and Multi-Task Reinforcement Learning [34.34798425737858]
我々は、慎重に設計されたバイアス補正機構を備えた新しいフェデレーションポリシーアルゴリズムであるFast-FedPGを提案する。
勾配支配条件下では,本アルゴリズムは (i) 厳密な勾配で高速な線形収束を保証し, (ii) 雑音に富んだ政策勾配を持つエージェントの数に比例して線形スピードアップを楽しむサブ線形速度を保証している。
論文 参考訳（メタデータ） (2024-09-09T02:59:17Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - Federated Contextual Cascading Bandits with Asynchronous Communication
and Heterogeneous Users [95.77678166036561]
繊細な通信プロトコルを用いたUPB型アルゴリズムを提案する。
同期フレームワークで達成されたものと同等のサブ線形後悔境界を与えます。
合成および実世界のデータセットに関する実証評価は、後悔と通信コストの観点から、我々のアルゴリズムの優れた性能を検証する。
論文 参考訳（メタデータ） (2024-02-26T05:31:14Z) - The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup
and Beyond [44.43850105124659]
地域データだけで訓練された局所的なQ-推定を周期的に集約することで、最適なQ-関数を学習することを目的とした、連合型Q-ラーニングについて考察する。
フェデレートされたQ-ラーニングの同期型と非同期型の両方に対して,複雑性の保証を行う。
本稿では,より頻繁に訪れる状態-行動ペアに対して,重み付けを重要視する新しいQ-ラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-05-18T04:18:59Z) - Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity [44.2308932471393]
モデル推定の交換により,エージェント数の線形収束速度が向上することを示す。
低ヘテロジニティ系では、モデル推定を交換すると、エージェントの数で線形収束速度が向上する。
論文 参考訳（メタデータ） (2023-02-04T17:53:55Z) - Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learning [24.567125948995834]
フェデレーション強化学習は、N$エージェントが協力してグローバルモデルを学ぶためのフレームワークである。
この連立固定点問題の解法において, エージェントの綿密な協調によって, グローバルモデルのN$倍の高速化が期待できることを示す。
論文 参考訳（メタデータ） (2022-06-21T08:39:12Z) - Cooperative Online Learning in Stochastic and Adversarial MDPs [50.62439652257712]
我々は、協調的オンライン学習と敵対的マルコフ決定過程(MDP)について研究する。
各エピソードでは、$m$エージェントが同時にMDPと対話し、個人の後悔を最小限に抑えるために情報を共有する。
協調強化学習(RL)を非フレッシュランダム性, あるいは敵対的MDPで検討したのは, 初めてである。
論文 参考訳（メタデータ） (2022-01-31T12:32:11Z) - Distributed Adaptive Learning Under Communication Constraints [54.22472738551687]
本研究では,コミュニケーション制約下での運用を目的とした適応型分散学習戦略について検討する。
我々は,ストリーミングデータの連続的な観察から,オンライン最適化問題を解決しなければならないエージェントのネットワークを考える。
論文 参考訳（メタデータ） (2021-12-03T19:23:48Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - UneVEn: Universal Value Exploration for Multi-Agent Reinforcement
Learning [53.73686229912562]
我々はUniversal Value Exploration(UneVEn)と呼ばれる新しいMARLアプローチを提案する。
UneVEnは、一連の関連するタスクと、普遍的な後継機能の線形分解を同時に学習する。
一連の探索ゲームにおける実証的な結果、エージェント間の重要な調整を必要とする協調捕食・捕食作業への挑戦、およびStarCraft IIのマイクロマネジメントベンチマークは、UneVEnが他の最先端のMARLメソッドが失敗するタスクを解決できることを示している。
論文 参考訳（メタデータ） (2020-10-06T19:08:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。