論文の概要: Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence
Analysis
- arxiv url: http://arxiv.org/abs/2010.13272v4
- Date: Mon, 22 May 2023 15:12:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 06:53:24.440771
- Title: Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence
Analysis
- Title(参考訳): 変量再現型オフポリティTDC学習:非漸近収束解析
- Authors: Shaocong Ma, Yi Zhou, Shaofeng Zou
- Abstract要約: オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。
実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
- 参考スコア(独自算出の注目度): 27.679514676804057
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Variance reduction techniques have been successfully applied to
temporal-difference (TD) learning and help to improve the sample complexity in
policy evaluation. However, the existing work applied variance reduction to
either the less popular one time-scale TD algorithm or the two time-scale GTD
algorithm but with a finite number of i.i.d.\ samples, and both algorithms
apply to only the on-policy setting. In this work, we develop a variance
reduction scheme for the two time-scale TDC algorithm in the off-policy setting
and analyze its non-asymptotic convergence rate over both i.i.d.\ and Markovian
samples. In the i.i.d.\ setting, our algorithm {matches the best-known lower
bound $\tilde{O}(\epsilon^{-1}$).} In the Markovian setting, our algorithm
achieves the state-of-the-art sample complexity $O(\epsilon^{-1} \log
{\epsilon}^{-1})$ that is near-optimal. Experiments demonstrate that the
proposed variance-reduced TDC achieves a smaller asymptotic convergence error
than both the conventional TDC and the variance-reduced TD.
- Abstract(参考訳): 時間変化学習(td学習)に分散低減技術が応用され,政策評価におけるサンプル複雑性の向上に寄与している。
しかし、既存の研究は1つの時間スケールのtdアルゴリズムや2つの時間スケールのgtdアルゴリズムに分散還元を適用しているが、有限個のi.i.d.\サンプルがあり、両方のアルゴリズムはオンポリシー設定のみに適用される。
本研究では,2つの時間スケールTDCアルゴリズムの分散低減手法を開発し,その非漸近収束速度をi.d.\ と Markovian の両方で解析する。
i.d.\ 設定では、我々のアルゴリズムは最もよく知られた下界 $\tilde{O}(\epsilon^{-1}$ と一致する。
} Markovian 設定では,我々のアルゴリズムは最先端のサンプル複雑性 $O(\epsilon^{-1} \log {\epsilon}^{-1})$をほぼ最適とする。
実験により,提案した分散再現型TDCは,従来のTDCと分散還元型TDより漸近収束誤差が小さいことを示した。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Stochastic Dimension-reduced Second-order Methods for Policy
Optimization [11.19708535159457]
各イテレーションにおいて勾配とヘシアンベクトル積のみを必要とするポリシー最適化のための新しい2次アルゴリズムを提案する。
具体的には、投影された2次元信頼領域のサブプロブレムを繰り返す次元還元二階法(DR-SOPO)を提案する。
DR-SOPOはおよそ1次定常状態に到達するために$mathcalO(epsilon-3.5)$の複雑さが得られることを示す。
さらに,拡張アルゴリズム (DVR-SOPO) を提案する。
論文 参考訳(メタデータ) (2023-01-28T12:09:58Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Finite-Time Error Bounds for Greedy-GQ [25.655180037837766]
We show that Greedy-GQ algorithm converges under $1/s。
我々の分析は、実際の収束を早めるためのステップサイズの選択を提供し、貿易の複雑さと得られた政策の質を示唆する。
論文 参考訳(メタデータ) (2022-09-06T15:04:57Z) - Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with
Near-Optimal Sample Complexity and Communication Complexity [13.100926925535578]
マルチエージェントオフポリシーTD学習のための2つの分散型TD補正(TDC)アルゴリズムを開発しています。
提案アルゴリズムは,エージェントの行動,ポリシー,報酬の完全なプライバシを保持し,サンプリングのばらつきと通信頻度を低減するためにミニバッチサンプリングを採用する。
論文 参考訳(メタデータ) (2021-03-24T12:48:08Z) - 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) - 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) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳(メタデータ) (2020-03-16T17:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。