論文の概要: Finite-Time Error Bounds for Greedy-GQ
- arxiv url: http://arxiv.org/abs/2209.02555v1
- Date: Tue, 6 Sep 2022 15:04:57 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-07 14:36:38.368577
- Title: Finite-Time Error Bounds for Greedy-GQ
- Title（参考訳）: greedy-gqの有限時間誤差境界
- Authors: Yue Wang, Yi Zhou, Shaofeng Zou
- Abstract要約: We show that Greedy-GQ algorithm converges under $1/s。
我々の分析は、実際の収束を早めるためのステップサイズの選択を提供し、貿易の複雑さと得られた政策の質を示唆する。
- 参考スコア（独自算出の注目度）: 25.655180037837766
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Greedy-GQ with linear function approximation, originally proposed in
\cite{maei2010toward}, is a value-based off-policy algorithm for optimal
control in reinforcement learning, and it has a non-linear two timescale
structure with a non-convex objective function. This paper develops its
finite-time error bounds. We show that the Greedy-GQ algorithm converges as
fast as $\mathcal{O}({1}/{\sqrt{T}})$ under the i.i.d.\ setting and
$\mathcal{O}({\log T}/{\sqrt{T}})$ under the Markovian setting. We further
design a variant of the vanilla Greedy-GQ algorithm using the nested-loop
approach, and show that its sample complexity is
$\mathcal{O}({\log(1/\epsilon)\epsilon^{-2}})$, which matches with the one of
the vanilla Greedy-GQ. Our finite-time error bounds match with one of the
stochastic gradient descent algorithms for general smooth non-convex
optimization problems. Our finite-sample analysis provides theoretical guidance
on choosing step-sizes for faster convergence in practice and suggests the
trade-off between the convergence rate and the quality of the obtained policy.
Our techniques in this paper provide a general approach for finite-sample
analysis of non-convex two timescale value-based reinforcement learning
algorithms.
- Abstract（参考訳）: 線形関数近似を用いたGreedy-GQは、もともと \cite{maei2010toward} で提案され、強化学習における最適制御のための値ベースのオフポリティアルゴリズムであり、非凸目的関数を持つ非線形2時間スケール構造を持つ。
本稿では,有限時間誤差境界を開発する。
greedy-gqアルゴリズムは、i.i.d.\設定下で$\mathcal{o}({1}/{\sqrt{t}})$、マルコフ設定下で$\mathcal{o}({\log t}/{\sqrt{t}})$で収束する。
さらに、ネストループ法を用いて、バニラグレディ-GQアルゴリズムの変種を設計し、サンプルの複雑さが$\mathcal{O}({\log(1/\epsilon)\epsilon^{-2}})$であることを示し、バニラグレディ-GQの変種と一致する。
我々の有限時間誤差境界は、一般の滑らかな非凸最適化問題に対する確率的勾配降下アルゴリズムの1つと一致する。
有限サンプル分析は, 収束を早めるためのステップサイズ選択に関する理論的指針を提供し, 収束率と得られた政策の品質のトレードオフを示唆する。
本稿では,非凸な2つの時間スケール値に基づく強化学習アルゴリズムの有限サンプル解析に対する一般的な手法を提案する。
関連論文リスト
- Improved Sample Complexity Analysis of Natural Policy Gradient Algorithm
with General Parameterization for Infinite Horizon Discounted Reward Markov
Decision Processes [41.61653528766776]
本稿では, 自然政策勾配を求めるために, 加速勾配降下過程を利用する自然促進政策勾配(PGAN)アルゴリズムを提案する。
繰り返しは$mathcalO(epsilon-2)$サンプル複雑性と$mathcalO(epsilon-1)$複雑さを達成する。
Hessian-free および IS-free アルゴリズムのクラスでは、ANPG は $mathcalO(epsilon-frac12)$ の係数で最もよく知られたサンプルの複雑さを破り、それらの状態と同時に一致する。
論文 参考訳（メタデータ） (2023-10-18T03:00:15Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳（メタデータ） (2022-09-12T06:53:24Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳（メタデータ） (2020-11-10T11:36:30Z) - Finite-Time Analysis for Double Q-learning [50.50058000948908]
二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。
同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
論文 参考訳（メタデータ） (2020-09-29T18:48:21Z) - 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) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。