論文の概要: Non-asymptotic Convergence Analysis of Two Time-scale (Natural)
Actor-Critic Algorithms
- arxiv url: http://arxiv.org/abs/2005.03557v2
- Date: Fri, 8 May 2020 02:06:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-05 22:38:53.070861
- Title: Non-asymptotic Convergence Analysis of Two Time-scale (Natural)
Actor-Critic Algorithms
- Title（参考訳）: 2つの時間スケール(自然)アクタ-クリティックアルゴリズムの非漸近収束解析
- Authors: Tengyu Xu, Zhe Wang, Yingbin Liang
- Abstract要約: アクタークリティカル(AC)とナチュラルアクタークリティカル(NAC)のアルゴリズムは、最適なポリシーを見つけるために2つの方法で実行されることが多い。
2つの時間スケールACは、$mathcalO(epsilon-2.5log3(epsilon-1))$で、$epsilon$-accurateの定常点に達するために、全体のサンプルの複雑さを必要とすることを示す。
我々は,動的にマルコフサンプリングが変化するため,アクターのバイアス誤差をバウンドする新しい手法を開発した。
- 参考スコア（独自算出の注目度）: 58.57004511121862
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As an important type of reinforcement learning algorithms, actor-critic (AC)
and natural actor-critic (NAC) algorithms are often executed in two ways for
finding optimal policies. In the first nested-loop design, actor's one update
of policy is followed by an entire loop of critic's updates of the value
function, and the finite-sample analysis of such AC and NAC algorithms have
been recently well established. The second two time-scale design, in which
actor and critic update simultaneously but with different learning rates, has
much fewer tuning parameters than the nested-loop design and is hence
substantially easier to implement. Although two time-scale AC and NAC have been
shown to converge in the literature, the finite-sample convergence rate has not
been established. In this paper, we provide the first such non-asymptotic
convergence rate for two time-scale AC and NAC under Markovian sampling and
with actor having general policy class approximation. We show that two
time-scale AC requires the overall sample complexity at the order of
$\mathcal{O}(\epsilon^{-2.5}\log^3(\epsilon^{-1}))$ to attain an
$\epsilon$-accurate stationary point, and two time-scale NAC requires the
overall sample complexity at the order of
$\mathcal{O}(\epsilon^{-4}\log^2(\epsilon^{-1}))$ to attain an
$\epsilon$-accurate global optimal point. We develop novel techniques for
bounding the bias error of the actor due to dynamically changing Markovian
sampling and for analyzing the convergence rate of the linear critic with
dynamically changing base functions and transition kernel.
- Abstract（参考訳）: 重要な種類の強化学習アルゴリズムとして、アクター・クリティカル(AC)とナチュラル・アクター・クリティカル(NAC)アルゴリズムが最適なポリシーを見つけるために2つの方法で実行されることが多い。
最初のネストループ設計では、アクターの1つのポリシー更新に続いて、批判者の値関数のアップデートの全ループが続き、ACアルゴリズムとNACアルゴリズムの有限サンプル解析が最近確立されている。
第2のタイムスケール設計ではアクターと批評家が同時に更新するが、学習率が異なるため、ネストループ設計よりもチューニングパラメータがはるかに少なく、実装が非常に容易である。
2つの時間スケールACとNACが文献に収束することが示されているが、有限サンプル収束速度は確立されていない。
本稿では,マルコフサンプリングと一般ポリシークラス近似を持つアクターによる2つの時間スケールACとNACに対して,このような非漸近収束率を示す。
2つの時間スケールACは、$\mathcal{O}(\epsilon^{-2.5}\log^3(\epsilon^{-1}))$が$\epsilon$-accurateな定常点を達成するために、そして2つの時間スケールNACが$\mathcal{O}(\epsilon^{-4}\log^2(\epsilon^{-1})$が$\epsilon$-accurateな大域的最適点を得るために、全体のサンプル複雑性を必要とすることを示す。
本稿では,マルコフサンプリングの動的変化によるアクタのバイアス誤差のバウンドと,ベース関数とトランジションカーネルを動的に変化させた線形批判者の収束率の解析手法を開発した。
関連論文リスト
- Improved Sample Complexity for Global Convergence of Actor-Critic Algorithms [49.19842488693726]
我々は,O(epsilon-3)$のサンプル複雑性を大幅に改善したアクター・クリティック・アルゴリズムのグローバル収束を確立した。
我々の発見は、一定のステップサイズに依存する多くのアルゴリズムに対する理論的支援を提供する。
論文 参考訳（メタデータ） (2024-10-11T14:46:29Z) - Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation [18.77565744533582]
アクタークリティカル (AC) は、強化学習において最適な政策を学ぶための強力な方法である。
AC は $epsilon +varepsilon_textcritic$ 定常点の近傍に収束する。
本稿では,ACアルゴリズムとNACアルゴリズムのコンバージェンスを,相反する関数近似を用いて解析する。
論文 参考訳（メタデータ） (2024-06-03T20:05:04Z) - Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation [5.945710235932345]
本稿では,長期平均報酬設定における関数近似を用いた最初の2段階の批評家・アクターアルゴリズムを提案する。
我々の分析の特筆すべき特徴は、最近のシングルタイムスケールアクター批判アルゴリズムとは異なり、我々のスキームの完全な収束解析を提示することである。
論文 参考訳（メタデータ） (2024-02-02T12:48:49Z) - Finite-Time Analysis of Fully Decentralized Single-Timescale
Actor-Critic [4.94128206910124]
本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。
このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。
また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
論文 参考訳（メタデータ） (2022-06-12T13:14:14Z) - 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) - Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence
Analysis [27.679514676804057]
オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。
実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
論文 参考訳（メタデータ） (2020-10-26T01:33:05Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - A Finite Time Analysis of Two Time-Scale Actor Critic Methods [87.69128666220016]
我々は,2つの時間スケールのアクター批判的手法に対する非漸近的解析を行う。
本研究では,アクター批判法が一階定常点を見つけることが保証されていることを証明した。
有限時間解析とサンプルの複雑さを2つの時間スケールアクター批判的手法に限定した最初の作品である。
論文 参考訳（メタデータ） (2020-05-04T09:45:18Z) - Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms [58.57004511121862]
本稿では, マルコフサンプリングにおけるACおよびNACの収束速度とサンプリング複雑性を特徴付ける。
本稿では,ACとNACがPGおよびNPGに対して,批判の組み合わさりにより,無限の地平線下での順に性能改善を実現していることを示す。
論文 参考訳（メタデータ） (2020-04-27T17:11:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。