論文の概要: Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise

• arxiv url: http://arxiv.org/abs/2401.00364v1
• Date: Sun, 31 Dec 2023 01:30:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-03 17:56:25.077316
• Title: Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise
• Title（参考訳）: マルコフ雑音を伴う2時間スケール線形確率近似の厳密な有限時間境界
• Authors: Shaan Ul Haque, Sajad Khodadadian, Siva Theja Maguluri
• Abstract要約: マルコフ雑音を伴う線形2時間スケール近似 (SA) の反復に対して, 厳密な収束を特徴付ける。 この結果は,Polyak平均化を用いたTD学習,GTD,GTD2など,様々なRLアルゴリズムの収束挙動の確立に応用できる。
• 参考スコア（独自算出の注目度）: 9.82187447690297
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic approximation (SA) is an iterative algorithm to find the fixed point of an operator given noisy samples of this operator. SA appears in many areas such as optimization and Reinforcement Learning (RL). When implemented in practice, the noise that appears in the update of RL algorithms is naturally Markovian. Furthermore, in some settings, such as gradient TD, SA is employed in a two-time-scale manner. The mix of Markovian noise along with the two-time-scale structure results in an algorithm which is complex to analyze theoretically. In this paper, we characterize a tight convergence bound for the iterations of linear two-time-scale SA with Markovian noise. Our results show the convergence behavior of this algorithm given various choices of step sizes. Applying our result to the well-known TDC algorithm, we show the first $O(1/\epsilon)$ sample complexity for the convergence of this algorithm, outperforming all the previous work. Similarly, our results can be applied to establish the convergence behavior of a variety of RL algorithms, such as TD-learning with Polyak averaging, GTD, and GTD2.
• Abstract（参考訳）: 確率近似 (Stochastic Approximation, SA) は、この演算子の雑音のあるサンプルを与えられた演算子の定点を求める反復アルゴリズムである。 SAは最適化や強化学習(RL)など、多くの分野に現れる。 実際に実装する場合、RLアルゴリズムの更新に現れるノイズは自然にマルコビアンである。 さらに、勾配TDなどのいくつかの設定では、SAを2段階的に使用する。 マルコフ雑音と2つの時間スケール構造の組み合わせは、理論的に解析するのが複雑なアルゴリズムをもたらす。 本稿では,マルコフ雑音を伴う線形2時間スケールSAの繰り返しに対して,厳密な収束を特徴付ける。 本研究の結果は,ステップサイズを多種に選択したアルゴリズムの収束挙動を示す。 我々の結果をよく知られたTDCアルゴリズムに適用すると、このアルゴリズムの収束のために最初の$O(1/\epsilon)$サンプルの複雑さを示し、以前の全ての作業より優れていた。 同様に、この結果は、Polyak平均化を用いたTD学習、GTD、GTD2など、様々なRLアルゴリズムの収束挙動を確立するために応用できる。

関連論文リスト

• Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic [4.94128206910124]
  本稿では,アクタ,批評家,グローバル報酬推定器を交互に更新する,完全に分散化されたアクタ・クリティカル(AC)アルゴリズムを提案する。 このアルゴリズムは,Markovian サンプリングにおいて $tildemathcalO(epsilon-2)$ のサンプル複雑性を持つことを示す。 また、我々のアルゴリズムのローカルアクションプライバシ保護バージョンとその分析も提供する。
  論文  参考訳（メタデータ） (2022-06-12T13:14:14Z)
• Gradient Temporal Difference with Momentum: Stability and Convergence [4.780898954294901]
  重ボールグラディエントTDアルゴリズムを3つのステップサイズで分割する。 重ボールグラディエントTDアルゴリズムが3次元SA解析を用いて収束していることを証明する。
  論文  参考訳（メタデータ） (2021-11-22T06:17:11Z)
• 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)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• 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)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。 両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。 ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
  論文  参考訳（メタデータ） (2020-04-08T03:59:21Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。 マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
  論文  参考訳（メタデータ） (2020-03-06T16:17:24Z)
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling [56.394284787780364]
  本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。 一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。 線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
  論文  参考訳（メタデータ） (2020-02-15T00:26:49Z)

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

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