論文の概要: Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2601.13642v1
• Date: Tue, 20 Jan 2026 06:21:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 22:47:23.179295
• Title: Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning
• Title（参考訳）: 平均逆Q-Learningの複雑さ:単一エージェントからフェデレーション強化学習へ
• Authors: Yuchen Jiao, Jiin Woo, Gen Li, Gauri Joshi, Yuejie Chi,
• Abstract要約: 有限状態と作用空間を持つ平均回帰型MDPに対して、弱い通信仮定の下で、単純だが効果的なQ-ラーニングアルゴリズムについて検討する。 We proof that the collaborations the per-agent sample complexitys to $widetildeOleft(frac|mathcalA||hstar|_mathsfsp3Mvarepsilon3right)$, with only $widetildeOleft(frac|hstar|_mathsfsp3Mvareps)。
• 参考スコア（独自算出の注目度）: 51.820005667020354
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Average-reward reinforcement learning offers a principled framework for long-term decision-making by maximizing the mean reward per time step. Although Q-learning is a widely used model-free algorithm with established sample complexity in discounted and finite-horizon Markov decision processes (MDPs), its theoretical guarantees for average-reward settings remain limited. This work studies a simple but effective Q-learning algorithm for average-reward MDPs with finite state and action spaces under the weakly communicating assumption, covering both single-agent and federated scenarios. For the single-agent case, we show that Q-learning with carefully chosen parameters achieves sample complexity $\widetilde{O}\left(\frac{|\mathcal{S}||\mathcal{A}|\|h^{\star}\|_{\mathsf{sp}}^3}{\varepsilon^3}\right)$, where $\|h^{\star}\|_{\mathsf{sp}}$ is the span norm of the bias function, improving previous results by at least a factor of $\frac{\|h^{\star}\|_{\mathsf{sp}}^2}{\varepsilon^2}$. In the federated setting with $M$ agents, we prove that collaboration reduces the per-agent sample complexity to $\widetilde{O}\left(\frac{|\mathcal{S}||\mathcal{A}|\|h^{\star}\|_{\mathsf{sp}}^3}{M\varepsilon^3}\right)$, with only $\widetilde{O}\left(\frac{\|h^{\star}\|_{\mathsf{sp}}}{\varepsilon}\right)$ communication rounds required. These results establish the first federated Q-learning algorithm for average-reward MDPs, with provable efficiency in both sample and communication complexity.
• Abstract（参考訳）: 平均回帰強化学習は、時間ステップ当たりの平均報酬を最大化することによって、長期的な意思決定のための原則化された枠組みを提供する。 Q-ラーニングは、割引および有限水平マルコフ決定過程 (MDP) において確立されたサンプル複雑性を持つモデルなしアルゴリズムとして広く用いられているが、平均回帰設定の理論的保証は限られている。 本研究は, 有限状態と作用空間を持つ平均回帰MDPに対して, 単一エージェントおよびフェデレーションシナリオの両方をカバーする, 単純だが効果的なQ-ラーニングアルゴリズムについて検討する。 単エージェントの場合、慎重に選択されたパラメータを持つQ-ラーニングはサンプル複雑性を$\widetilde{O}\left(\frac{|\mathcal{S}||\mathcal{A}|\|h^{\star}\|_{\mathsf{sp}}^3}{\varepsilon^3}\right)$, ここで$\|h^{\star}\|_{\mathsf{sp}}$はバイアス関数のスパンノルムであり、少なくとも$\frac{\|h^{\star}\|_{\mathsf{sp}}^2}{\varepsilon^2}$で前の結果を改善する。 M$エージェントによるフェデレート設定では、共同作業により、$\widetilde{O}\left(\frac{|\mathcal{S}||\mathcal{A}|\|h^{\star}\|_{\mathsf{sp}}^3}{M\varepsilon^3}\right)$,$$\widetilde{O}\left(\frac{\|h^{\star}\|_{\mathsf{sp}}}{\varepsilon}\right)$が必要とされる。 これらの結果から, サンプルと通信の複雑さの両面において, 有意な効率性を有する, 平均回帰MDPのための初となるQ-ラーニングアルゴリズムが確立された。

関連論文リスト

• A finite time analysis of distributed Q-learning [6.663174194579773]
  マルチエージェント強化学習(MARL)は、単一エージェント強化学習(RL)の適用において達成された経験的成功によって、目覚ましい関心の高まりを目撃している。 本研究では,多くのエージェントが局所報酬の平均値である中央報酬関数にアクセスせずに逐次意思決定問題を協調的に解決する分散Q-ラーニングシナリオについて考察する。
  論文  参考訳（メタデータ） (2024-05-23T00:52:38Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
  平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。 これは文学の下位境界に到達した最初のアルゴリズムと分析である。
  論文  参考訳（メタデータ） (2023-10-13T03:08:59Z)
• Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes [21.77276136591518]
  我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。 シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
  論文  参考訳（メタデータ） (2023-06-28T17:43:19Z)
• Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
  対戦型オンラインマルチタスク強化学習環境について考察する。 K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。 学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
  論文  参考訳（メタデータ） (2023-01-11T02:18:26Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• 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)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• 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)

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

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