論文の概要: Finite-Sample Analysis for Two Time-scale Non-linear TDC with General
Smooth Function Approximation
- arxiv url: http://arxiv.org/abs/2104.02836v1
- Date: Wed, 7 Apr 2021 00:34:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-08 12:43:03.383689
- Title: Finite-Sample Analysis for Two Time-scale Non-linear TDC with General
Smooth Function Approximation
- Title(参考訳): 一般平滑関数近似を用いた2次元時間スケール非線形TDCの有限サンプル解析
- Authors: Yue Wang, Shaofeng Zou, Yi Zhou
- Abstract要約: 我々は,一般のオフ・ポリシー設定にバインドされた有限サンプル誤差を明示的に特徴付ける新しい手法を開発した。
本手法は,一般的なスムーズな関数近似を用いた広範囲なT型学習アルゴリズムに適用できる。
- 参考スコア(独自算出の注目度): 27.149240954363496
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Temporal-difference learning with gradient correction (TDC) is a two
time-scale algorithm for policy evaluation in reinforcement learning. This
algorithm was initially proposed with linear function approximation, and was
later extended to the one with general smooth function approximation. The
asymptotic convergence for the on-policy setting with general smooth function
approximation was established in [bhatnagar2009convergent], however, the
finite-sample analysis remains unsolved due to challenges in the non-linear and
two-time-scale update structure, non-convex objective function and the
time-varying projection onto a tangent plane. In this paper, we develop novel
techniques to explicitly characterize the finite-sample error bound for the
general off-policy setting with i.i.d.\ or Markovian samples, and show that it
converges as fast as $\mathcal O(1/\sqrt T)$ (up to a factor of $\mathcal
O(\log T)$). Our approach can be applied to a wide range of value-based
reinforcement learning algorithms with general smooth function approximation.
- Abstract(参考訳): 勾配補正付き時間差学習(TDC)は、強化学習における政策評価のための2つの時間スケールアルゴリズムである。
このアルゴリズムは当初線形関数近似を用いて提案され、後に一般の滑らか関数近似に拡張された。
bhatnagar2009convergent] では, 一般的な滑らかな関数近似を伴うオンポリシー設定の漸近収束が確立されたが, 非線形および2時間スケールの更新構造, 非凸目的関数, および接平面への時変射影の問題により, 有限サンプル解析は未解決のままである。
本稿では,<i>d.\ あるいは Markovian のサンプルを用いて,一般のオフポリティ設定に対して有界な有限サンプル誤差を明示的に特徴付ける新しい手法を開発し,$\mathcal O(1/\sqrt T)$ ($\mathcal O(\log T)$) に収束することを示す。
本手法は, 一般的なスムーズな関数近似を用いた広範囲な値に基づく強化学習アルゴリズムに適用できる。
関連論文リスト
- Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - Finite-Time Error Bounds for Greedy-GQ [25.655180037837766]
We show that Greedy-GQ algorithm converges under $1/s。
我々の分析は、実際の収束を早めるためのステップサイズの選択を提供し、貿易の複雑さと得られた政策の質を示唆する。
論文 参考訳(メタデータ) (2022-09-06T15:04:57Z) - Improving the Transient Times for Distributed Stochastic Gradient
Methods [5.215491794707911]
拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。
EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。
我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
論文 参考訳(メタデータ) (2021-05-11T08:09:31Z) - Smoothed functional-based gradient algorithms for off-policy
reinforcement learning: A non-asymptotic viewpoint [9.734033555407406]
オフポリシ強化学習コンテキストにおける制御の問題を解決するための2つのポリシーグラデーションアルゴリズムを提案する。
どちらのアルゴリズムも、スムース機能(SF)ベースの勾配推定スキームを組み込む。
論文 参考訳(メタデータ) (2021-01-06T17:06:42Z) - 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) - ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm [77.71051081132912]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
emphRecursive One-Over-T Root (ROOTSGD) と呼ばれる小説を考案する。
有限サンプル勾配, 漸近感覚, 感覚を同時に達成することを証明する。
論文 参考訳(メタデータ) (2020-08-28T14:46:56Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳(メタデータ) (2020-07-10T05:20:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。