論文の概要: The Sample-Communication Complexity Trade-off in Federated Q-Learning
- arxiv url: http://arxiv.org/abs/2408.16981v2
- Date: Tue, 29 Oct 2024 20:37:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-08 04:08:49.193022
- Title: The Sample-Communication Complexity Trade-off in Federated Q-Learning
- Title（参考訳）: フェデレートQ-Learningにおけるサンプル・コミュニケーション複合性トレードオフ
- Authors: Sudeep Salgia, Yuejie Chi,
- Abstract要約: 広範に使われている間欠的通信アルゴリズムにおけるサンプルと通信複雑性のトレードオフについて検討する。
我々は、注文最適サンプルと通信の複雑さを同時に達成する最初のフェデレーションQ-ラーニングアルゴリズムであるFed-DVR-Qを提案する。
- 参考スコア（独自算出の注目度）: 31.644851830271755
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of federated Q-learning, where $M$ agents aim to collaboratively learn the optimal Q-function of an unknown infinite-horizon Markov decision process with finite state and action spaces. We investigate the trade-off between sample and communication complexities for the widely used class of intermittent communication algorithms. We first establish the converse result, where it is shown that a federated Q-learning algorithm that offers any speedup with respect to the number of agents in the per-agent sample complexity needs to incur a communication cost of at least an order of $\frac{1}{1-\gamma}$ up to logarithmic factors, where $\gamma$ is the discount factor. We also propose a new algorithm, called Fed-DVR-Q, which is the first federated Q-learning algorithm to simultaneously achieve order-optimal sample and communication complexities. Thus, together these results provide a complete characterization of the sample-communication complexity trade-off in federated Q-learning.
- Abstract（参考訳）: 我々は、M$エージェントが未知の無限水平マルコフ決定過程の最適Q-関数を有限状態と作用空間で協調的に学習することを目的とした、連合Q-ラーニングの問題を考察する。
広範に使われている間欠的通信アルゴリズムにおけるサンプルと通信複雑性のトレードオフについて検討する。
まず, 対数係数が$\gamma$である場合, 対数係数が$\frac{1}{1-\gamma}$の少なくとも1桁の通信コストを発生させる必要があることを示す。
また,Fed-DVR-Qと呼ばれる新しいアルゴリズムを提案する。このアルゴリズムは,注文-最適サンプルと通信の複雑さを同時に達成する最初のフェデレーションQ-ラーニングアルゴリズムである。
このようにして、これらの結果は、連合Q-ラーニングにおけるサンプル通信複雑性のトレードオフの完全な特徴を与える。
関連論文リスト
- Federated Q-Learning with Reference-Advantage Decomposition: Almost Optimal Regret and Logarithmic Communication Cost [4.895986534376972]
本稿では,FedQ-Advantageと呼ばれる新しいモデルフリーなフェデレーションQ-ラーニングアルゴリズムを提案する。
我々のアルゴリズムは対数通信コストを低くするだけでなく、時間的地平線が十分に大きい場合と比較して、対数係数に縛られた情報とほぼ直線的後悔のスピードアップに到達して、ほぼ最適の後悔を達成する。
論文 参考訳（メタデータ） (2024-05-29T06:26:52Z) - On the Necessity of Collaboration for Online Model Selection with Decentralized Data [53.244188985271606]
我々は,100万ドル以上の分散データを用いたオンラインモデル選択について検討し,クライアント間のコラボレーションの必要性について検討する。
i) クライアント上の計算コストが$o(K)$に制限された場合, (ii) クライアント上での計算制約がない場合, (i) 協調は不要であり, (ii) クライアント上での計算コストは$o(K)$に制限される。
論文 参考訳（メタデータ） (2024-04-15T06:32:28Z) - Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
Retrieval-augmented Large Language Models (LLMs) は、質問回答(QA)のようなタスクにおける応答精度を高めるための有望なアプローチとして登場した。
本稿では,クエリの複雑さに基づいて,LLMの最適戦略を動的に選択できる適応型QAフレームワークを提案する。
オープンドメインのQAデータセットを用いて、複数のクエリの複雑さを網羅し、QAシステムの全体的な効率性と精度を高めることを示す。
論文 参考訳（メタデータ） (2024-03-21T13:52:30Z) - Multi-Timescale Ensemble Q-learning for Markov Decision Process Policy
Optimization [21.30645601474163]
元々のQ-ラーニングは、非常に大きなネットワークにわたるパフォーマンスと複雑性の課題に悩まされている。
従来のQ-ラーニングに適応したモデルフリーアンサンブル強化学習アルゴリズムを提案する。
計算結果から,提案アルゴリズムは平均ポリシエラーを最大55%,実行時複雑性を最大50%削減できることがわかった。
論文 参考訳（メタデータ） (2024-02-08T08:08:23Z) - Federated Q-Learning: Linear Regret Speedup with Low Communication Cost [4.380110270510058]
本稿では,FedQ-HoeffdingとFedQ-Bernsteinという2つの連合Qラーニングアルゴリズムを提案する。
時間的地平線が十分に大きい場合, 対応する全後悔は, 単エージェントと比較して直線的なスピードアップを達成することを示す。
これらの結果は、エージェントとサーバ間のイベントトリガー同期機構に依存します。
論文 参考訳（メタデータ） (2023-12-22T19:14:09Z) - Pointer Networks with Q-Learning for Combinatorial Optimization [55.2480439325792]
我々は、モデルフリーQ値ポリシー近似をPointer Networks(Ptr-Nets)と統合したハイブリッドニューラルネットワークであるPointer Q-Network(PQN)を紹介する。
実験により,本手法の有効性を実証し,不安定な環境でモデルをテストする。
論文 参考訳（メタデータ） (2023-11-05T12:03:58Z) - The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup
and Beyond [44.43850105124659]
地域データだけで訓練された局所的なQ-推定を周期的に集約することで、最適なQ-関数を学習することを目的とした、連合型Q-ラーニングについて考察する。
フェデレートされたQ-ラーニングの同期型と非同期型の両方に対して,複雑性の保証を行う。
本稿では,より頻繁に訪れる状態-行動ペアに対して,重み付けを重要視する新しいQ-ラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-05-18T04:18:59Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。
我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。
実験結果から,アルゴリズムの性能が向上した。
論文 参考訳（メタデータ） (2023-02-13T21:28:53Z) - INTERACT: Achieving Low Sample and Communication Complexities in
Decentralized Bilevel Learning over Networks [24.02913189682224]
分散化された双方向最適化問題は、ネットワーク機械学習コミュニティで注目を集めている。
低サンプリングと通信の複雑さは、未調査のままである2つの基本的な課題である。
我々の研究は、ネットワーク上の分散化された二段階最適化問題を解決するために、低サンプリングと通信の複雑さの両方を初めて解決した。
論文 参考訳（メタデータ） (2022-07-27T04:19:28Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳（メタデータ） (2021-02-12T14:22:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。