論文の概要: Non-asymptotic Convergence of Adam-type Reinforcement Learning
Algorithms under Markovian Sampling
- arxiv url: http://arxiv.org/abs/2002.06286v2
- Date: Mon, 17 Aug 2020 15:28:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-31 23:01:27.049356
- Title: Non-asymptotic Convergence of Adam-type Reinforcement Learning
Algorithms under Markovian Sampling
- Title（参考訳）: マルコフサンプリングによるadam型強化学習アルゴリズムの非漸近収束
- Authors: Huaqing Xiong, Tengyu Xu, Yingbin Liang, Wei Zhang
- Abstract要約: 本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。
一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。
線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
- 参考スコア（独自算出の注目度）: 56.394284787780364
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Despite the wide applications of Adam in reinforcement learning (RL), the
theoretical convergence of Adam-type RL algorithms has not been established.
This paper provides the first such convergence analysis for two fundamental RL
algorithms of policy gradient (PG) and temporal difference (TD) learning that
incorporate AMSGrad updates (a standard alternative of Adam in theoretical
analysis), referred to as PG-AMSGrad and TD-AMSGrad, respectively. Moreover,
our analysis focuses on Markovian sampling for both algorithms. We show that
under general nonlinear function approximation, PG-AMSGrad with a constant
stepsize converges to a neighborhood of a stationary point at the rate of
$\mathcal{O}(1/T)$ (where $T$ denotes the number of iterations), and with a
diminishing stepsize converges exactly to a stationary point at the rate of
$\mathcal{O}(\log^2 T/\sqrt{T})$. Furthermore, under linear function
approximation, TD-AMSGrad with a constant stepsize converges to a neighborhood
of the global optimum at the rate of $\mathcal{O}(1/T)$, and with a diminishing
stepsize converges exactly to the global optimum at the rate of
$\mathcal{O}(\log T/\sqrt{T})$. Our study develops new techniques for analyzing
the Adam-type RL algorithms under Markovian sampling.
- Abstract（参考訳）: 強化学習(RL)におけるアダムの幅広い応用にもかかわらず、アダム型RLアルゴリズムの理論的収束は確立されていない。
本稿では,AMSGrad更新(理論解析におけるAdamの標準代替品)を組み込んだ政策勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して,それぞれPG-AMSGradおよびTD-AMSGradと呼ばれる最初の収束解析を行う。
さらに,両アルゴリズムのマルコフサンプリングに着目した分析を行った。
一般的な非線形関数近似の下では、定数ステップを持つ pg-amsgrad は $\mathcal{o}(1/t)$ の率で定常点の近傍に収束し(ここで $t$ は反復数を表す)、減少ステップ化は $\mathcal{o}(\log^2 t/\sqrt{t})$ の速度で定常点に正確に収束する。
さらに、線型関数近似の下では、定数のステップを持つtd-amsgradは、$\mathcal{o}(1/t)$の率で大域的最適の近傍に収束し、減少するステップでは$\mathcal{o}(\log t/\sqrt{t})$の速度で大域的最適に収束する。
本研究では,マルコフサンプリングに基づくAdam型RLアルゴリズムの新たな解析手法を開発した。
関連論文リスト
- MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。
最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。
一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
論文 参考訳（メタデータ） (2024-05-29T18:36:59Z) - Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。
また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
論文 参考訳（メタデータ） (2023-04-27T06:27:37Z) - A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous
Q-Learning and TD-Learning Variants [39.28675942566465]
本稿では,値に基づく非同期RLアルゴリズムのクラスに対する有限サンプル収束保証について検討する枠組みを開発する。
副産物として、偏差トレードオフ、すなわちRLにおけるブートストラップの効率に関する理論的知見を提供する。
論文 参考訳（メタデータ） (2021-02-02T15:48:19Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳（メタデータ） (2020-11-10T11:36:30Z) - Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence
Analysis [27.679514676804057]
オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。
実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
論文 参考訳（メタデータ） (2020-10-26T01:33:05Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - 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) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。