論文の概要: Finite-Time Error Bounds for Greedy-GQ

• arxiv url: http://arxiv.org/abs/2209.02555v2
• Date: Thu, 2 May 2024 03:09:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-03 22:58:28.188121
• Title: Finite-Time Error Bounds for Greedy-GQ
• Title（参考訳）: グレディGQのための有限時間誤差境界
• Authors: Yue Wang, Yi Zhou, Shaofeng Zou,
• Abstract要約: We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
• 参考スコア（独自算出の注目度）: 20.51105692499517
• 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 the non-convex objective function. This paper develops its tightest 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, despite its additonal challenge in the two time-scale updates. 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 provide a general approach for finite-sample analysis of non-convex two timescale value-based reinforcement learning algorithms.
• Abstract（参考訳）: 線形関数近似を用いたGreedy-GQは、もともと \cite{maei2010toward} で提案され、強化学習における最適制御のための値ベースのオフポリティアルゴリズムであり、非凸目的関数を持つ非線形2時間スケール構造を持つ。 本稿では,最も厳密な有限時間誤差境界を開発する。 We show that the Greedy-GQ algorithm converges as $\mathcal{O}({1}/{\sqrt{T}})$ under the i.d.\ setting and $\mathcal{O}({\log T}/{\sqrt{T}})$ under the Markovian set。 さらに、ネストループ法を用いて、バニラグレディ-GQアルゴリズムの変種を設計し、サンプルの複雑さが$\mathcal{O}({\log(1/\epsilon)\epsilon^{-2}})$であることを示し、バニラグレディ-GQの変種と一致する。 我々の有限時間誤差境界は、2つの時間スケールの更新において付加的な課題があるにもかかわらず、一般的な滑らかな非凸最適化問題に対する確率勾配勾配勾配アルゴリズムの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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。