論文の概要: Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms

• arxiv url: http://arxiv.org/abs/2410.08868v1
• Date: Fri, 11 Oct 2024 14:46:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 21:35:51.494893
• Title: Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms
• Title（参考訳）: Actor-Criticアルゴリズムの大域収束のための改良されたサンプル複雑性
• Authors: Navdeep Kumar, Priyank Agrawal, Giorgia Ramponi, Kfir Yehuda Levy, Shie Mannor,
• Abstract要約: 我々は,O(epsilon-3)$のサンプル複雑性を大幅に改善したアクター・クリティック・アルゴリズムのグローバル収束を確立した。 我々の発見は、一定のステップサイズに依存する多くのアルゴリズムに対する理論的支援を提供する。
• 参考スコア（独自算出の注目度）: 49.19842488693726
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we establish the global convergence of the actor-critic algorithm with a significantly improved sample complexity of $O(\epsilon^{-3})$, advancing beyond the existing local convergence results. Previous works provide local convergence guarantees with a sample complexity of $O(\epsilon^{-2})$ for bounding the squared gradient of the return, which translates to a global sample complexity of $O(\epsilon^{-4})$ using the gradient domination lemma. In contrast to traditional methods that employ decreasing step sizes for both the actor and critic, we demonstrate that a constant step size for the critic is sufficient to ensure convergence in expectation. This key insight reveals that using a decreasing step size for the actor alone is sufficient to handle the noise for both the actor and critic. Our findings provide theoretical support for the practical success of many algorithms that rely on constant step sizes.
• Abstract（参考訳）: 本稿では,既存の局所収束結果を超えて,O(\epsilon^{-3})$のサンプル複雑性を大幅に改善したアクタ・クリティック・アルゴリズムのグローバル収束を確立する。 以前の研究は、再帰の2乗勾配の有界化に対して$O(\epsilon^{-2})$の局所収束保証を提供しており、これは勾配支配補題を用いて$O(\epsilon^{-4})$の大域的なサンプル複雑性に変換する。 アクターと批評家の両方のステップサイズを減少させる従来の手法とは対照的に、批評家にとって一定のステップサイズは期待の収束を保証するのに十分であることを示す。 この重要な洞察は、アクター単独でステップサイズを小さくすることは、アクターと批評家の両方にとってノイズを扱うのに十分であることを示している。 本研究は,一定のステップサイズに依存する多くのアルゴリズムの実用的成功を理論的に支援するものである。

関連論文リスト

• On the Global Convergence of Natural Actor-Critic with Two-layer Neural Network Parametrization [38.32265770020665]
  本稿では,ニューラルネットワークを用いた自然なアクター批判アルゴリズムについて検討する。 本研究の目的は,本アルゴリズムの性能特性のより深い理解を実現することにある。
  論文  参考訳（メタデータ） (2023-06-18T06:22:04Z)
• Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulator [43.13238243240668]
  我々は、$epsilon$-optimal Solutionへのグローバル収束を確立するための新しい分析フレームワークを開発する。 これは、LQRを大域的最適で解くための単一のサンプル2時間スケールACに対する最初の有限時間収束解析である。
  論文  参考訳（メタデータ） (2022-08-18T09:57:03Z)
• Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic [4.94128206910124]
  本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。 このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。 また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
  論文  参考訳（メタデータ） (2022-06-12T13:14:14Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation [5.543220407902113]
  我々は,線形関数近似を用いた非政治的自然なアクター批判アルゴリズムの新たな変種を開発する。 我々は$mathcalO(epsilon-3)$のサンプル複雑性を確立し、そのようなアルゴリズムの既知収束境界を全て上回る。
  論文  参考訳（メタデータ） (2021-05-26T13:35:42Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。 有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
  論文  参考訳（メタデータ） (2021-02-23T18:56:13Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms [58.57004511121862]
  アクタークリティカル(AC)とナチュラルアクタークリティカル(NAC)のアルゴリズムは、最適なポリシーを見つけるために2つの方法で実行されることが多い。 2つの時間スケールACは、$mathcalO(epsilon-2.5log3(epsilon-1))$で、$epsilon$-accurateの定常点に達するために、全体のサンプルの複雑さを必要とすることを示す。 我々は,動的にマルコフサンプリングが変化するため,アクターのバイアス誤差をバウンドする新しい手法を開発した。
  論文  参考訳（メタデータ） (2020-05-07T15:42:31Z)
• Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms [58.57004511121862]
  本稿では, マルコフサンプリングにおけるACおよびNACの収束速度とサンプリング複雑性を特徴付ける。 本稿では,ACとNACがPGおよびNPGに対して,批判の組み合わさりにより,無限の地平線下での順に性能改善を実現していることを示す。
  論文  参考訳（メタデータ） (2020-04-27T17:11:06Z)

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

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