論文の概要: Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise
- arxiv url: http://arxiv.org/abs/2401.00364v2
- Date: Sun, 11 May 2025 19:55:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-13 20:21:48.536424
- 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の繰り返しに対する誤差の上限を導出する。
広範に研究されている線形2時間スケールSAの特別な例は、Polyak-Ruppert平均値を持つ線形SAである。
- 参考スコア（独自算出の注目度）: 8.739101659113157
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic approximation (SA) is an iterative algorithm for finding the fixed point of an operator using noisy samples and widely used in optimization and Reinforcement Learning (RL). The noise in RL exhibits a Markovian structure, and in some cases, such as gradient temporal difference (GTD) methods, SA is employed in a two-time-scale framework. This combination introduces significant theoretical challenges for analysis. We derive an upper bound on the error for the iterations of linear two-time-scale SA with Markovian noise. We demonstrate that the mean squared error decreases as $trace (\Sigma^y)/k + o(1/k)$ where $k$ is the number of iterates, and $\Sigma^y$ is an appropriately defined covariance matrix. A key feature of our bounds is that the leading term, $\Sigma^y$, exactly matches with the covariance in the Central Limit Theorem (CLT) for the two-time-scale SA, and we call them tight finite-time bounds. We illustrate their use in RL by establishing sample complexity for off-policy algorithms, TDC, GTD, and GTD2. A special case of linear two-time-scale SA that is extensively studied is linear SA with Polyak-Ruppert averaging. We present tight finite time bounds corresponding to the covariance matrix of the CLT. Such bounds can be used to study TD-learning with Polyak-Ruppert averaging.
- Abstract（参考訳）: 確率近似 (Stochastic Approximation, SA) は、雑音のあるサンプルを用いて演算子の定点を求める反復アルゴリズムであり、最適化と強化学習 (RL) に広く用いられている。
RLのノイズはマルコフ構造を示し、勾配時間差法(GTD)のような場合、SAは2段階の枠組みで用いられる。
この組み合わせは分析に重大な理論的課題をもたらす。
マルコフ雑音を伴う線形2時間スケールSAの繰り返しに対する誤差の上限を導出する。
平均二乗誤差は $trace (\Sigma^y)/k + o(1/k)$ として減少し、$k$ は反復数であり、$\Sigma^y$ は適切に定義された共分散行列である。
我々の境界のキーとなる特徴は、中心項である$\Sigma^y$ が2時間スケールの SA に対する中央極限定理(CLT)の共分散と完全に一致することである。
オフポリティクスアルゴリズム、TDC、GTD、GTD2のサンプル複雑性を確立することにより、RLにおけるそれらの利用について説明する。
広範に研究されている線形2時間スケールSAの特別な例は、Polyak-Ruppert平均値を持つ線形SAである。
CLTの共分散行列に対応する厳密な有限時間境界を示す。
このような境界は、Polyak-Ruppert平均化を用いてTD学習を研究するのに使うことができる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。