論文の概要: Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise

• arxiv url: http://arxiv.org/abs/2409.19546v4
• Date: Mon, 03 Feb 2025 22:14:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 14:56:04.808685
• Title: Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise
• Title（参考訳）: マルコフ雑音による非拡張確率近似の漸近的・有限的サンプル解析
• Authors: Ethan Blaser, Shangtong Zhang,
• Abstract要約: 本研究は、単に拡張的でない作用素との近似を研究する。 特にマルコフ雑音による非拡張近似について検討する。 応用として、古典的な平均報酬時間差学習が標本経路依存の固定点に収束することを初めて証明する。
• 参考スコア（独自算出の注目度）: 20.474661995490365
• License:
• Abstract: Stochastic approximation is an important class of algorithms, and a large body of previous analysis focuses on stochastic approximations driven by contractive operators, which is not applicable in some important reinforcement learning settings. This work instead investigates stochastic approximations with merely nonexpansive operators. In particular, we study nonexpansive stochastic approximations with Markovian noise, providing both asymptotic and finite sample analysis. Key to our analysis are a few novel bounds of noise terms resulting from the Poisson equation. As an application, we prove, for the first time, that the classical tabular average reward temporal difference learning converges to a sample path dependent fixed point.
• Abstract（参考訳）: 確率近似は重要なアルゴリズムのクラスであり、以前の分析では、いくつかの重要な強化学習環境では適用できない契約演算子によって駆動される確率近似に焦点が当てられている。 この研究は、単に拡張的でない作用素による確率近似を研究する。 特に,マルコフ雑音による非拡張確率近似について検討し,漸近的および有限的サンプル解析を行った。 我々の分析の鍵は、ポアソン方程式から生じるいくつかの新しいノイズ項の境界である。 応用として、古典的な表平均報酬時間差学習がサンプルパス依存の固定点に収束することを初めて証明する。

関連論文リスト

• Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise [31.241889735283166]
  カウントベース学習率を使わずにMarkovianサンプルを用いてQ$-learningの収束率を示す。 また、マルコフサンプルを用いた非政治時間差学習のための第1の集中度も提供する。
  論文  参考訳（メタデータ） (2024-11-20T21:09:09Z)
• Finite Sample and Large Deviations Analysis of Stochastic Gradient Algorithm with Correlated Noise [15.724207170366846]
  我々は,ステップサイズ勾配アルゴリズムの有限標本残差を解析した。 相関雑音を仮定し,解析の体系的アプローチとして摂動リアプノフ関数を用いる。
  論文  参考訳（メタデータ） (2024-10-11T01:38:27Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。 クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
  論文  参考訳（メタデータ） (2023-10-03T07:49:17Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic Analysis For DDIM-Type Samplers [90.45898746733397]
  本研究では拡散生成モデルに用いる決定論的サンプリング器の非漸近解析のためのフレームワークを開発する。 確率フローODEに沿った1ステップは,1) 条件付き対数線上を無限に先行して上昇する回復ステップ,2) 雑音を現在の勾配に向けて前向きに進行する劣化ステップの2段階で表すことができる。
  論文  参考訳（メタデータ） (2023-03-06T18:59:19Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。 演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
  論文  参考訳（メタデータ） (2022-01-21T02:46:57Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Convergence rates and approximation results for SGD and its continuous-time counterpart [16.70533901524849]
  本稿では,非増加ステップサイズを有する凸勾配Descent (SGD) の完全理論的解析を提案する。 まず、結合を用いた不均一微分方程式(SDE)の解により、SGDを確実に近似できることを示す。 連続的手法による決定論的および最適化手法の最近の分析において, 連続過程の長期的挙動と非漸近的境界について検討する。
  論文  参考訳（メタデータ） (2020-04-08T18:31:34Z)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。 両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。 ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
  論文  参考訳（メタデータ） (2020-04-08T03:59:21Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)

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

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