論文の概要: 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)
• Almost sure convergence rates of stochastic gradient methods under gradient domination [2.96614015844317]
  大域的および局所的な勾配支配特性は、強い凸性のより現実的な置き換えであることが示されている。 収束率 $f(X_n)-f*in obig(n-frac14beta-1+epsilonbig)$ は勾配降下の最終反復である。 教師付き学習と強化学習の両方において,本研究結果をトレーニングタスクに適用する方法を示す。
  論文  参考訳（メタデータ） (2024-05-22T12:40:57Z)
• On the Last-Iterate Convergence of Shuffling Gradient Methods [21.865728815935665]
  対象値に関して勾配法をシャッフルする際の最終点収束率を初めて証明する。 我々の結果は、(ほぼ)既存のラストイテレートの下限と一致するか、あるいは、平均的なイテレートの前の最高の上限と同速である。
  論文  参考訳（メタデータ） (2024-03-12T15:01:17Z)
• Stochastic Gradient Succeeds for Bandits [64.17904367852563]
  エンフィスト確率勾配帯域幅アルゴリズムは,O (1/t)$レートで,エンフィグロブな最適ポリシに収束することを示す。 興味深いことに、勾配帯域アルゴリズムのグローバル収束は以前に確立されていない。
  論文  参考訳（メタデータ） (2024-02-27T06:05:01Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency [83.02999769628593]
  強化学習におけるオフ・ポリティィ・アセスメント(OPE)の理論的特徴について述べる。 ミニマックス法により、重みと品質関数の高速収束を実現することができることを示す。 非タブラル環境における1次効率を持つ最初の有限サンプル結果を示す。
  論文  参考訳（メタデータ） (2021-02-05T03:20:39Z)
• Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning [9.359939442911127]
  本稿ではマルコフ雑音下での変分不等式(VI)のリセットに着目する。 我々のアルゴリズム開発における顕著な応用は、強化学習における政策評価問題である。
  論文  参考訳（メタデータ） (2020-11-15T04:05:22Z)
• Proximal Gradient Temporal Difference Learning: Stable Reinforcement Learning with Polynomial Sample Complexity [40.73281056650241]
  本稿では,真の勾配時間差学習アルゴリズムを設計・解析する原理的な方法として,近位勾配時間差学習を導入する。 本研究では, 従来の目的関数からではなく, 主目的関数から始めることによって, 勾配性TD強化学習法を公式に導出する方法を示す。
  論文  参考訳（メタデータ） (2020-06-06T21:04:21Z)

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

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