論文の概要: 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)$) に収束することを示す。
本手法は, 一般的なスムーズな関数近似を用いた広範囲な値に基づく強化学習アルゴリズムに適用できる。
関連論文リスト
- A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。
i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。
その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
論文 参考訳(メタデータ) (2024-04-18T16:46:08Z) - 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 [20.51105692499517]
We show that Greedy-GQ algorithm converges fast-time error。
我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
論文 参考訳(メタデータ) (2022-09-06T15:04:57Z) - A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning [13.908826484332282]
最適化問題の解法として,新しい2段階勾配法を提案する。
最初の貢献は、提案した2時間スケール勾配アルゴリズムの有限時間複雑性を特徴づけることである。
我々は、強化学習における勾配に基づく政策評価アルゴリズムに適用する。
論文 参考訳(メタデータ) (2021-09-29T23:15:23Z) - 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 [8.087699764574788]
政治外の強化学習コンテキストにおける制御問題の解法として,2つのポリシー勾配アルゴリズムを提案する。
どちらのアルゴリズムも、スムーズな関数的勾配推定スキームを取り入れている。
論文 参考訳(メタデータ) (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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。