論文の概要: Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise

• arxiv url: http://arxiv.org/abs/2002.01268v1
• Date: Tue, 4 Feb 2020 13:03:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-04 02:31:13.765548
• Title: Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Title（参考訳）: マルコフ雑音による線形2時間確率近似の有限時間解析
• Authors: Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, Hoi-To Wai
• Abstract要約: 線形2時間スケールSAスキームに対して有限時間解析を行う。 我々の境界はマルコフ音とマルティンゲール音の収束速度に差がないことを示している。 一致した下界を持つ予測誤差の拡張を示す。
• 参考スコア（独自算出の注目度）: 28.891930079358954
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear two-timescale stochastic approximation (SA) scheme is an important class of algorithms which has become popular in reinforcement learning (RL), particularly for the policy evaluation problem. Recently, a number of works have been devoted to establishing the finite time analysis of the scheme, especially under the Markovian (non-i.i.d.) noise settings that are ubiquitous in practice. In this paper, we provide a finite-time analysis for linear two timescale SA. Our bounds show that there is no discrepancy in the convergence rate between Markovian and martingale noise, only the constants are affected by the mixing time of the Markov chain. With an appropriate step size schedule, the transient term in the expected error bound is $o(1/k^c)$ and the steady-state term is ${\cal O}(1/k)$, where $c>1$ and $k$ is the iteration number. Furthermore, we present an asymptotic expansion of the expected error with a matching lower bound of $\Omega(1/k)$. A simple numerical experiment is presented to support our theory.
• Abstract（参考訳）: 線形2時間スケール確率近似(SA)スキームは、特に政策評価問題において強化学習(RL)で人気を博したアルゴリズムの重要なクラスである。 近年、このスキームの有限時間解析の確立に、特に実際にユビキタスなマルコフ(非i.i.d.)ノイズ設定の下で、多くの研究がなされている。 本稿では,線形2時間スケールSAの有限時間解析について述べる。 我々の境界はマルコフとマルティンゲールノイズの収束速度に差がないことを示しているが、定数のみがマルコフ連鎖の混合時間に影響されている。 適切なステップサイズスケジュールでは、期待されるエラーバウンドの過渡項は$o(1/k^c)$であり、定常項は${\cal o}(1/k)$であり、ここで$c>1$と$k$はイテレーション番号である。 さらに、期待誤差の漸近的拡大を示し、一致する下限が$\omega(1/k)$ であることを示す。 我々の理論を支持するため、簡単な数値実験を行う。

関連論文リスト

• Non-Expansive Mappings in Two-Time-Scale Stochastic Approximation: Finite-Time Analysis [0.0]
  より遅い時間スケールが拡張性のないマッピングを持つ2段階のイテレーションについて検討する。 平均二乗誤差は$O (1/k1/4-epsilon)$で減衰し、$epsilon>0$は任意に小さくなる。
  論文  参考訳（メタデータ） (2025-01-18T16:00:14Z)
• Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way [12.331596909999764]
  マルコフ過程のレンズを通した等質化スキームについて検討する。 我々は、定段化によって導入された分散とバイアスと同様に、明示的な幾何学的および非漸近収束率を導出する。
  論文  参考訳（メタデータ） (2024-10-16T21:49:27Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation [22.51165277694864]
  本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。 LSAは$d$次元線形系の近似解を計算するために用いられる。
  論文  参考訳（メタデータ） (2022-07-10T14:36:04Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• 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)

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

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