論文の概要: On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments

• arxiv url: http://arxiv.org/abs/2409.03897v1
• Date: Thu, 5 Sep 2024 20:09:56 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-09 17:20:24.164780
• Title: On the Convergence Rates of Federated Q-Learning across Heterogeneous Environments
• Title（参考訳）: 不均一環境におけるフェデレーションQ学習の収束率について
• Authors: Muxing Wang, Pengkun Yang, Lili Su,
• Abstract要約: 同期型Q-ラーニングについて検討し、K$エージェントをローカルQ-estimates per $E$ iterationsの平均値にすることで最適なQ-関数を学習することを目的とする。 収束速度に関する興味深い現象を、$K$と$E$という観点から観察する。 我々は、幅広い段階において、エラーの $ell_infty$ ノルムが $Theta (E/T)$ よりも早く崩壊できないことを証明している。
• 参考スコア（独自算出の注目度）: 6.6089456297043245
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large-scale multi-agent systems are often deployed across wide geographic areas, where agents interact with heterogeneous environments. There is an emerging interest in understanding the role of heterogeneity in the performance of the federated versions of classic reinforcement learning algorithms. In this paper, we study synchronous federated Q-learning, which aims to learn an optimal Q-function by having $K$ agents average their local Q-estimates per $E$ iterations. We observe an interesting phenomenon on the convergence speeds in terms of $K$ and $E$. Similar to the homogeneous environment settings, there is a linear speed-up concerning $K$ in reducing the errors that arise from sampling randomness. Yet, in sharp contrast to the homogeneous settings, $E>1$ leads to significant performance degradation. Specifically, we provide a fine-grained characterization of the error evolution in the presence of environmental heterogeneity, which decay to zero as the number of iterations $T$ increases. The slow convergence of having $E>1$ turns out to be fundamental rather than an artifact of our analysis. We prove that, for a wide range of stepsizes, the $\ell_{\infty}$ norm of the error cannot decay faster than $\Theta (E/T)$. In addition, our experiments demonstrate that the convergence exhibits an interesting two-phase phenomenon. For any given stepsize, there is a sharp phase-transition of the convergence: the error decays rapidly in the beginning yet later bounces up and stabilizes. Provided that the phase-transition time can be estimated, choosing different stepsizes for the two phases leads to faster overall convergence.
• Abstract（参考訳）: 大規模マルチエージェントシステムは、エージェントが異種環境と相互作用する広い地域にわたって展開されることが多い。 古典的強化学習アルゴリズムのフェデレーション版の性能における異種性の役割を理解することへの関心が高まっている。 本稿では,K$エージェントをローカルQ推定平均で$E$イテレーションあたりの平均値にすることで,最適なQ関数を学習することを目的とした同期型Q-ラーニングについて検討する。 収束速度に関する興味深い現象を、$K$と$E$という観点から観察する。 均質な環境設定と同様に、サンプリングランダム性から生じるエラーを減らすために$K$に関する線形スピードアップがある。 しかし、均質な設定とは対照的に、$E>1$は性能を著しく低下させる。 具体的には、環境不均一性の存在下でのエラー進化を詳細に評価し、反復数$T$が増加するにつれて0に減衰する。 E>1$を持つことの緩やかな収束は、我々の分析の成果物というよりは根本的なものであることが判明した。 我々は、幅広い段階において、エラーの$\ell_{\infty}$ノルムが$\Theta (E/T)$よりも早く崩壊できないことを証明している。 さらに,本実験では,この収束現象が興味深い2相現象を示すことを示した。 任意のステップサイズに対して、収束の急激な位相遷移があり、エラーは初めから急速に崩壊するが、後に跳ね上がり、安定化する。 相転移時間を推定でき、2つの相の異なる段階を選択すれば、全体の収束が早くなる。

関連論文リスト

• Dissipative phase transition: from qubits to qudits [0.0]
  量子多体系における散逸相転移の運命を、個々の成分がキュービットではなくキューディットであるときに検討する。 キュービットの代わりにキュービットを考えると、オープン多体系におけるリッチ位相図へのアクセスに関する新たな視点が開かれる。
  論文  参考訳（メタデータ） (2024-05-02T12:08:28Z)
• Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models [49.81937966106691]
  我々は拡散モデルのデータ生成過程を理解するための非漸近理論のスイートを開発する。 従来の研究とは対照的に,本理論は基本的だが多目的な非漸近的アプローチに基づいて開発されている。
  論文  参考訳（メタデータ） (2023-06-15T16:30:08Z)
• Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron [49.45105570960104]
  ランダム勾配降下のグローバル収束を$Oleft(T-3right)$ rateで証明する。 これら2つの境界は、収束率の正確な特徴づけを与える。 このポテンシャル関数は緩やかに収束し、損失関数の緩やかな収束率を示す。
  論文  参考訳（メタデータ） (2023-02-20T15:33:26Z)
• A globally convergent fast iterative shrinkage-thresholding algorithm with a new momentum factor for single and multi-objective convex optimization [0.0]
  提案手法はまた,任意の$(a,b)$に対して,大域収束率$O(1/k2)$を持つことを示す。 様々な$(a,b)$で数値結果を報告し、これらの選択のいくつかが古典的な運動量因子よりも良い結果をもたらすことを示す。
  論文  参考訳（メタデータ） (2022-05-11T04:26:00Z)
• Faster Convergence of Local SGD for Over-Parameterized Models [1.5504102675587357]
  現代の機械学習アーキテクチャは、しばしば非常に表現力が高い。 不均一なデータ設定における過パラメータ化関数に対する局所SGD(またはFedAvg)の収束を解析する。 一般凸損失関数に対しては、$O(K/T)$の誤差が成立する。 非剰余関数に対しては、どちらの場合も$O(K/T)$の誤差が証明される。 確立された収束率を、合理的に小さなステップサイズで一定の要因に密着した問題インスタンスを提供することで、結果を完成させる。
  論文  参考訳（メタデータ） (2022-01-30T04:05:56Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• An Analysis of the Adaptation Speed of Causal Models [80.77896315374747]
  最近、Bengioらは、すべての候補モデルの中で、$G$は、あるデータセットから別のデータセットに適応する最速のモデルであると推測した。 最適化からの収束率を用いた原因影響SCMの適応速度について検討する。 驚くべきことに、私たちは反因果モデルが有利である状況を見つけ、初期仮説を偽造する。
  論文  参考訳（メタデータ） (2020-05-18T23:48:56Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。