論文の概要: Gap-Dependent Bounds for Federated $Q$-learning

• arxiv url: http://arxiv.org/abs/2502.02859v1
• Date: Wed, 05 Feb 2025 03:32:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-06 14:28:51.972761
• Title: Gap-Dependent Bounds for Federated $Q$-learning
• Title（参考訳）: フェデレーション付き$Q$ラーニングのためのギャップ依存境界
• Authors: Haochen Zhang, Zhong Zheng, Lingzhou Xue,
• Abstract要約: 有限水平マルコフ決定過程(MDPs)におけるオンラインフェデレーション$Q$Learningに対する後悔とコミュニケーションコストの最初のギャップ依存分析を提示する。 我々の新しいフレームワークは、厳密な正の準最適ギャップのようなMDPの良質な構造を利用して、$log T$-type regret boundと洗練された通信コストboundを達成する。
• 参考スコア（独自算出の注目度）: 4.895986534376972
• License:
• Abstract: We present the first gap-dependent analysis of regret and communication cost for on-policy federated $Q$-Learning in tabular episodic finite-horizon Markov decision processes (MDPs). Existing FRL methods focus on worst-case scenarios, leading to $\sqrt{T}$-type regret bounds and communication cost bounds with a $\log T$ term scaling with the number of agents $M$, states $S$, and actions $A$, where $T$ is the average total number of steps per agent. In contrast, our novel framework leverages the benign structures of MDPs, such as a strictly positive suboptimality gap, to achieve a $\log T$-type regret bound and a refined communication cost bound that disentangles exploration and exploitation. Our gap-dependent regret bound reveals a distinct multi-agent speedup pattern, and our gap-dependent communication cost bound removes the dependence on $MSA$ from the $\log T$ term. Notably, our gap-dependent communication cost bound also yields a better global switching cost when $M=1$, removing $SA$ from the $\log T$ term.
• Abstract（参考訳）: 表層表層有限水平マルコフ決定過程(MDPs)において,オンラインフェデレーションによるQ$-Learningに対する後悔とコミュニケーションコストのギャップ依存分析を行った。 既存のFRLメソッドは最悪のシナリオに重点を置いており、$\sqrt{T}$-type regret boundsと通信コストは$\log T$ term scale with the number of agent $M$, states $S$, and action $A$である。 対照的に、我々の新しいフレームワークは、厳密な正の準最適ギャップのようなMDPの良質な構造を活用して、$\log T$-type regret boundと、探究と搾取を阻害する洗練された通信コストboundを達成する。 我々のギャップ依存的後悔境界は、異なるマルチエージェント・スピードアップパターンを示し、ギャップ依存的な通信コスト境界は、$\log T$項から$MSA$への依存を除去する。 特に、ギャップ依存の通信コストは、$M=1$のときにより優れたグローバルスイッチングコストをもたらし、$\log T$の項から$SA$を取り除きます。

関連論文リスト

• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。 本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。 我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
  論文  参考訳（メタデータ） (2023-05-10T20:29:29Z)
• Reinforcement Learning in a Birth and Death Process: Breaking the Dependence on the State Space [0.0]
  我々は、出生・死亡構造を有するMDPにおける未報告の強化学習の後悔を再考する。 本研究の結果から,従来の学習アルゴリズム sc Ucrl2 のやや遅れたバージョンに対する後悔は,実際には $tildemathcalO(sqrtEAT)$ で表される。
  論文  参考訳（メタデータ） (2023-02-21T13:28:37Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
  我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。 この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
  論文  参考訳（メタデータ） (2022-03-24T08:14:12Z)
• Communication-efficient SGD: From Local SGD to One-Shot Averaging [16.00658606157781]
  複数の作業者に対して並列化することで,勾配降下(SGD)の高速化を検討する。 そこで本研究では,反復数の増加に伴って通信頻度を小さくすることで,全体の通信を減らし,局所的なSGD方式を提案する。
  論文  参考訳（メタデータ） (2021-06-09T01:10:34Z)
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret [144.6358229217845]
  エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
  論文  参考訳（メタデータ） (2021-04-22T17:20:48Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Communication Efficient Parallel Reinforcement Learning [34.77250498401055]
  我々は、$m$エージェントが$s$状態と$a$アクションを持つ$m$同一および独立環境と相互作用する問題を考える。 我々はエージェントが不適切なコミュニケーションラウンドで後悔を最小限に抑えるアルゴリズムを見つけることを目的としている。
  論文  参考訳（メタデータ） (2021-02-22T02:46:36Z)
• Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
  最短経路 (SSP) は計画と制御においてよく知られた問題である。 また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。 我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
  論文  参考訳（メタデータ） (2020-06-20T12:10:35Z)

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

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