論文の概要: Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms
- arxiv url: http://arxiv.org/abs/2011.05053v1
- Date: Tue, 10 Nov 2020 11:36:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-27 06:47:13.569387
- Title: Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms
- Title（参考訳）: 2つの時間スケール値に基づく強化学習アルゴリズムのサンプル複雑性境界
- Authors: Tengyu Xu, Yingbin Liang
- Abstract要約: 2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
- 参考スコア（独自算出の注目度）: 65.09383385484007
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Two timescale stochastic approximation (SA) has been widely used in
value-based reinforcement learning algorithms. In the policy evaluation
setting, it can model the linear and nonlinear temporal difference learning
with gradient correction (TDC) algorithms as linear SA and nonlinear SA,
respectively. In the policy optimization setting, two timescale nonlinear SA
can also model the greedy gradient-Q (Greedy-GQ) algorithm. In previous
studies, the non-asymptotic analysis of linear TDC and Greedy-GQ has been
studied in the Markovian setting, with diminishing or accuracy-dependent
stepsize. For the nonlinear TDC algorithm, only the asymptotic convergence has
been established. In this paper, we study the non-asymptotic convergence rate
of two timescale linear and nonlinear TDC and Greedy-GQ under Markovian
sampling and with accuracy-independent constant stepsize. For linear TDC, we
provide a novel non-asymptotic analysis and show that it attains an
$\epsilon$-accurate solution with the optimal sample complexity of
$\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$ under a constant stepsize. For
nonlinear TDC and Greedy-GQ, we show that both algorithms attain
$\epsilon$-accurate stationary solution with sample complexity
$\mathcal{O}(\epsilon^{-2})$. It is the first non-asymptotic convergence result
established for nonlinear TDC under Markovian sampling and our result for
Greedy-GQ outperforms the previous result orderwisely by a factor of
$\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$.
- Abstract（参考訳）: 2つの時間スケール確率近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
政策評価設定では、勾配補正(TDC)アルゴリズムを線形SAと非線形SAとして、線形および非線形時間差分学習をモデル化することができる。
ポリシー最適化設定では、2つの時間スケール非線形SAがグリーディ勾配-Q (Greedy-GQ) アルゴリズムをモデル化できる。
これまでの研究では、線形TDCとGreedy-GQの非漸近解析はマルコフのセッティングにおいて、減少または精度に依存したステップサイズで研究されてきた。
非線形TDCアルゴリズムでは漸近収束のみが確立されている。
本稿では,2つの時間スケール線形および非線形tdcとgreedy-gqの非漸近収束速度をマルコフサンプリングと精度に依存しない定数ステップで検討する。
線形 TDC に対して、新しい非漸近解析を提供し、一定のステップサイズで $\mathcal{O}(\epsilon^{-1}\log(1/\epsilon))$ の最適なサンプル複雑性を持つ $\epsilon$-正確な解が得られることを示す。
非線形 TDC と Greedy-GQ に対して、両方のアルゴリズムがサンプル複雑性$\mathcal{O}(\epsilon^{-2})$で$\epsilon$-正確な定常解を得ることを示す。
これはマルコフサンプリングの下で非線形 tdc に対して確立された最初の非漸近収束結果であり、greedy-gq の結果は$\mathcal{o}(\epsilon^{-1}\log(1/\epsilon))$ の係数によって順序的に前の結果を上回る。
関連論文リスト
- Gauss-Newton Temporal Difference Learning with Nonlinear Function Approximation [11.925232472331494]
非線形関数近似を用いたQラーニング問題を解くため,ガウスニュートン時間差分法(GNTD)学習法を提案する。
各イテレーションにおいて、我々の手法は1つのガウスニュートン(GN)ステップを踏んで平均二乗ベルマン誤差(MSBE)の変種を最適化する。
いくつかのRLベンチマークにおいて、GNTDはTD型よりも高い報酬と高速な収束を示す。
論文 参考訳（メタデータ） (2023-02-25T14:14:01Z) - Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳（メタデータ） (2022-09-06T15:04:57Z) - Stationary Behavior of Constant Stepsize SGD Type Algorithms: An
Asymptotic Characterization [4.932130498861987]
一定段差がゼロとなる極限において, 適切にスケールされた定常分布の挙動について検討する。
極限スケールの定常分布は積分方程式の解であることを示す。
論文 参考訳（メタデータ） (2021-11-11T17:39:50Z) - Finite-Sample Analysis for Two Time-scale Non-linear TDC with General
Smooth Function Approximation [27.149240954363496]
我々は,一般のオフ・ポリシー設定にバインドされた有限サンプル誤差を明示的に特徴付ける新しい手法を開発した。
本手法は,一般的なスムーズな関数近似を用いた広範囲なT型学習アルゴリズムに適用できる。
論文 参考訳（メタデータ） (2021-04-07T00:34:11Z) - 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) - 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) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z) - 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) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。