論文の概要: Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise

• arxiv url: http://arxiv.org/abs/2503.18391v1
• Date: Mon, 24 Mar 2025 07:03:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-25 14:37:28.503191
• Title: Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise
• Title（参考訳）: 任意ノルム収縮とマルコフ雑音による2時間スケール確率近似のための有限時間境界
• Authors: Siddharth Chandak, Shaan Ul Haque, Nicholas Bambos,
• Abstract要約: 2時間スケール近似(英: Two-time-scale Approximation、SA)は、強化学習と最適化に応用した反復アルゴリズムである。 強化学習の応用により、非線型2時間スケール SA 上の最初の平均正方形を与える。
• 参考スコア（独自算出の注目度）: 7.770605097524015
• License:
• Abstract: Two-time-scale Stochastic Approximation (SA) is an iterative algorithm with applications in reinforcement learning and optimization. Prior finite time analysis of such algorithms has focused on fixed point iterations with mappings contractive under Euclidean norm. Motivated by applications in reinforcement learning, we give the first mean square bound on non linear two-time-scale SA where the iterations have arbitrary norm contractive mappings and Markovian noise. We show that the mean square error decays at a rate of $O(1/n^{2/3})$ in the general case, and at a rate of $O(1/n)$ in a special case where the slower timescale is noiseless. Our analysis uses the generalized Moreau envelope to handle the arbitrary norm contractions and solutions of Poisson equation to deal with the Markovian noise. By analyzing the SSP Q-Learning algorithm, we give the first $O(1/n)$ bound for an algorithm for asynchronous control of MDPs under the average reward criterion. We also obtain a rate of $O(1/n)$ for Q-Learning with Polyak-averaging and provide an algorithm for learning Generalized Nash Equilibrium (GNE) for strongly monotone games which converges at a rate of $O(1/n^{2/3})$.
• Abstract（参考訳）: 2時間スケール確率近似(英: Two-time-scale Stochastic Approximation、SA)は、強化学習と最適化に応用した反復アルゴリズムである。 そのようなアルゴリズムの以前の有限時間解析は、ユークリッドノルムの下で縮約された写像を持つ固定点反復に焦点を合わせてきた。 強化学習の応用により、反復が任意のノルム縮約写像とマルコフ雑音を持つ非線型2時間スケール SA 上の最初の平均正方形を与える。 平均二乗誤差は一般の場合$O(1/n^{2/3}) と、より遅い時間スケールがノイズのない特別の場合$O(1/n) で減衰することを示す。 解析では一般化モローエンベロープを用いて任意のノルム収縮とポアソン方程式の解を処理し、マルコフ雑音に対処する。 SSP Q-Learning アルゴリズムを解析することにより,平均報酬基準の下での MDP の非同期制御を行うアルゴリズムに対して,最初の$O(1/n)$バウンドを与える。 また,ポリアクアラグを用いたQ-ラーニングでは$O(1/n)$,強い単調ゲームでは$O(1/n^{2/3})$で収束する一般化ナッシュ平衡(GNE)を学習するためのアルゴリズムを提供する。

関連論文リスト

• 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)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。 我々はモンテカルロ法と量子ウォークの量子アナログを利用する。 また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
  論文  参考訳（メタデータ） (2022-10-12T19:10:43Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• 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)
• 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)
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise [28.891930079358954]
  線形2時間スケールSAスキームに対して有限時間解析を行う。 我々の境界はマルコフ音とマルティンゲール音の収束速度に差がないことを示している。 一致した下界を持つ予測誤差の拡張を示す。
  論文  参考訳（メタデータ） (2020-02-04T13:03:17Z)

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

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