論文の概要: On the Convergence of Single-Timescale Actor-Critic

• arxiv url: http://arxiv.org/abs/2410.08868v2
• Date: Wed, 04 Jun 2025 12:47:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 21:20:13.851636
• Title: On the Convergence of Single-Timescale Actor-Critic
• Title（参考訳）: 単時間アクター臨界の収束性について
• Authors: Navdeep Kumar, Priyank Agrawal, Giorgia Ramponi, Kfir Yehuda Levy, Shie Mannor,
• Abstract要約: 本研究では,有限状態空間を持つ無限水平割引決定過程(MD)に対して,単時間アクタークリティカル(AC)アルゴリズムのグローバル収束を解析する。 我々は,アクタと批評家の両方のステップサイズが (O(k-Pfrac12) として崩壊し,従来の (O(k-Pfrac12) ) レートから (非最適) の Markov フレームワーク最適化で一般的に使用される (O(k-Pfrac12) ) レートから$k$ になることを示した。
• 参考スコア（独自算出の注目度）: 49.19842488693726
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze the global convergence of the single-timescale actor-critic (AC) algorithm for the infinite-horizon discounted Markov Decision Processes (MDPs) with finite state spaces. To this end, we introduce an elegant analytical framework for handling complex, coupled recursions inherent in the algorithm. Leveraging this framework, we establish that the algorithm converges to an $\epsilon$-close \textbf{globally optimal} policy with a sample complexity of \( O(\epsilon^{-3}) \). This significantly improves upon the existing complexity of $O(\epsilon^{-2})$ to achieve $\epsilon$-close \textbf{stationary policy}, which is equivalent to the complexity of $O(\epsilon^{-4})$ to achieve $\epsilon$-close \textbf{globally optimal} policy using gradient domination lemma. Furthermore, we demonstrate that to achieve this improvement, the step sizes for both the actor and critic must decay as \( O(k^{-\frac{2}{3}}) \) with iteration $k$, diverging from the conventional \( O(k^{-\frac{1}{2}}) \) rates commonly used in (non)convex optimization.
• Abstract（参考訳）: 有限状態空間を持つ無限水平割引マルコフ決定過程 (MDP) に対する単時間アクタークリティカル (AC) アルゴリズムのグローバル収束を解析する。 この目的のために,アルゴリズムに固有の複雑で結合された再帰を扱うためのエレガントな分析フレームワークを提案する。 このフレームワークを活用すると、アルゴリズムは$\epsilon$-close \textbf{globally optimal} ポリシーに収束し、サンプル複雑性は \(O(\epsilon^{-3}) \。 これは、$O(\epsilon^{-2})$が$\epsilon$-close \textbf{stationary Policy}を達成するために既存の複雑さを大幅に改善し、$O(\epsilon^{-4})$が$\epsilon$-close \textbf{globally optimal} ポリシーを達成するために、勾配支配補題を用いて$O(\epsilon^{-4})$と等価である。 さらに、この改善を実現するためには、アクターと批評家の両方のステップサイズが、従来の(非)凸最適化で一般的に使用される(O(k^{-\frac{1}{2}}) \)レートから分岐した反復$k$で、 \(O(k^{-\frac{2}{3}}) \)として崩壊しなければならないことを実証する。

関連論文リスト

• 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)

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

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