論文の概要: Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
- arxiv url: http://arxiv.org/abs/2004.12956v4
- Date: Fri, 12 Feb 2021 01:00:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-09 04:36:21.754204
- Title: Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms
- Title（参考訳）: ベクトルクリティカルアルゴリズムにおけるサンプル複素性境界の改善
- Authors: Tengyu Xu, Zhe Wang, Yingbin Liang
- Abstract要約: 本稿では, マルコフサンプリングにおけるACおよびNACの収束速度とサンプリング複雑性を特徴付ける。
本稿では,ACとNACがPGおよびNPGに対して,批判の組み合わさりにより,無限の地平線下での順に性能改善を実現していることを示す。
- 参考スコア（独自算出の注目度）: 58.57004511121862
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The actor-critic (AC) algorithm is a popular method to find an optimal policy
in reinforcement learning. In the infinite horizon scenario, the finite-sample
convergence rate for the AC and natural actor-critic (NAC) algorithms has been
established recently, but under independent and identically distributed
(i.i.d.) sampling and single-sample update at each iteration. In contrast, this
paper characterizes the convergence rate and sample complexity of AC and NAC
under Markovian sampling, with mini-batch data for each iteration, and with
actor having general policy class approximation. We show that the overall
sample complexity for a mini-batch AC to attain an $\epsilon$-accurate
stationary point improves the best known sample complexity of AC by an order of
$\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$, and the overall sample complexity
for a mini-batch NAC to attain an $\epsilon$-accurate globally optimal point
improves the existing sample complexity of NAC by an order of
$\mathcal{O}(\epsilon^{-1}/\log(1/\epsilon))$. Moreover, the sample complexity
of AC and NAC characterized in this work outperforms that of policy gradient
(PG) and natural policy gradient (NPG) by a factor of
$\mathcal{O}((1-\gamma)^{-3})$ and
$\mathcal{O}((1-\gamma)^{-4}\epsilon^{-1}/\log(1/\epsilon))$, respectively.
This is the first theoretical study establishing that AC and NAC attain
orderwise performance improvement over PG and NPG under infinite horizon due to
the incorporation of critic.
- Abstract（参考訳）: アクタ-クリティック(ac)アルゴリズムは、強化学習において最適な方針を見つけるための一般的な手法である。
無限の地平線シナリオでは、ACアルゴリズムとNACアルゴリズムの有限サンプル収束速度が最近確立されているが、各イテレーションにおいて独立で同一に分散されたサンプリング(すなわちd)と単一サンプル更新の下では確立されていない。
対照的に,本論文では,マルコフサンプリング下でのacとnacの収束率とサンプル複雑性を,各イテレーション毎のミニバッチデータ,一般ポリシークラス近似のアクタを用いて特徴付ける。
ミニバッチACが$\epsilon$-accurate定常点に達するためのサンプルの全体的な複雑さは、$\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$の順序でACの既知のサンプルの複雑さを向上し、$\epsilon$-accurate大域的最適点を得るためのミニバッチNACの全体的なサンプルの複雑さは、$\mathcal{O}(\epsilon^{-1}/\log(1/\epsilon)の順序でNACの既存のサンプルの複雑さを向上することを示した。
さらに、本研究で特徴付けられるacとnacのサンプル複雑性は、それぞれ$\mathcal{o}((1-\gamma)^{-3})$と$\mathcal{o}((1-\gamma)^{-4}\epsilon^{-1}/\log(1/\epsilon)$の係数によって、政策勾配(pg)と自然政策勾配(npg)のそれを上回る。
これは、ACとNACがPGとNPGを無限の地平線の下で順に性能改善できることを示す最初の理論的研究である。
関連論文リスト
- 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) - Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm
with General Parameterization for Infinite Horizon Discounted Reward Markov
Decision Processes [41.61653528766776]
本稿では, 自然政策勾配を求めるために, 加速勾配降下過程を利用する自然促進政策勾配(PGAN)アルゴリズムを提案する。
繰り返しは$mathcalO(epsilon-2)$サンプル複雑性と$mathcalO(epsilon-1)$複雑さを達成する。
Hessian-free および IS-free アルゴリズムのクラスでは、ANPG は $mathcalO(epsilon-frac12)$ の係数で最もよく知られたサンプルの複雑さを破り、それらの状態と同時に一致する。
論文 参考訳（メタデータ） (2023-10-18T03:00:15Z) - Finite-Time Analysis of Fully Decentralized Single-Timescale
Actor-Critic [4.94128206910124]
本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。
このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。
また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
論文 参考訳（メタデータ） (2022-06-12T13:14:14Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳（メタデータ） (2020-11-10T11:36:30Z) - 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) - 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) - Non-asymptotic Convergence of Adam-type Reinforcement Learning
Algorithms under Markovian Sampling [56.394284787780364]
本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。
一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。
線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
論文 参考訳（メタデータ） (2020-02-15T00:26:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。