論文の概要: Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

• arxiv url: http://arxiv.org/abs/2605.07104v1
• Date: Fri, 08 May 2026 01:32:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:38.719673
• Title: Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift
• Title（参考訳）: Poisson-Moreauドリフトを用いた確率近似と強化学習のほぼ確実に収束率
• Authors: Xinyu Liu, Zixuan Xie, Shangtong Zhang,
• Abstract要約: 我々はマルコフ雑音下で近似と強化学習の収束率をほぼ確実に確立する。 我々の分析の鍵となるのは、ポアソン方程式に基づくマルコフ雑音の補正を確立されたモロー・エンベロープ平滑化に適用した新しいリアプノフドリフト構造である。
• 参考スコア（独自算出の注目度）: 19.81737958703724
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Establishing almost sure convergence rates for stochastic approximation and reinforcement learning under Markovian noise is a fundamental theoretical challenge. We make progress towards this challenge for a class of stochastic approximation algorithms whose expected updates are contractive, a setting that arises in many reinforcement learning algorithms such as $Q$-learning and linear temporal difference learning. Specifically, for a power-law learning rate $O(n^{-η})$ with $η\in (1/2, 1)$, we obtain an almost sure convergence rate arbitrarily close to $o(n^{1 - 2η})$. For a harmonic learning rate $O(n^{-1})$, we obtain an almost sure convergence rate arbitrarily close to $o(n^{-1})$, which we argue is a strong result because it is close to the optimal rate $O(n^{-1}\log\log n)$ given by the law of the iterated logarithm (for a special case of i.i.d. noise). Key to our analysis is a novel Lyapunov drift construction that applies a Poisson-equation based correction for Markovian noise to the well-established Moreau-envelope smoothing for the contractive mapping.
• Abstract（参考訳）: マルコフ雑音下で確率近似と強化学習のほぼ確実に収束率を確立することは、基本的な理論的課題である。 提案手法は,Q$学習や線形時間差分学習といった多くの強化学習アルゴリズムで発生する。 具体的には、$O(n^{-η})$と$η\in (1/2, 1)$とすると、ほぼ確実に$o(n^{1 - 2η})$に近い収束率が得られる。 調和学習率 $O(n^{-1})$ に対して、ほぼ確実に$o(n^{-1})$ に近い収束率を得るが、これは最適な速度 $O(n^{-1}\log\log n)$ に近いので強い結果である。 我々の分析の鍵となるのは、ポアソン方程式に基づくマルコフ雑音の補正を、縮尺写像のために確立されたモロー・エンベロープ平滑化に応用する新しいリアプノフドリフト構造である。

関連論文リスト

• $O(1/k)$ Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation [0.0]
  非線形2時間スケール近似に対して$O (1/k)$の勾配境界を改良した。 この結果は、降下度や2時間スケールのラグランジアン最適化などのアルゴリズムに適用できる。
  論文  参考訳（メタデータ） (2025-04-27T22:45:00Z)
• Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise [5.7071219882414885]
  2時間スケール近似(英: Two-time-scale Approximation、SA)は、強化学習と最適化に応用した反復アルゴリズムである。 強化学習の応用により、非線型2時間スケール SA 上の最初の平均正方形を与える。
  論文  参考訳（メタデータ） (2025-03-24T07:03:23Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• 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)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• Adaptive Federated Learning Over the Air [108.62635460744109]
  オーバー・ザ・エア・モデル・トレーニングの枠組みの中で,適応勾配法,特にAdaGradとAdamの連合バージョンを提案する。 解析の結果,AdaGrad に基づくトレーニングアルゴリズムは $mathcalO(ln(T) / T 1 - frac1alpha の速度で定常点に収束することがわかった。
  論文  参考訳（メタデータ） (2024-03-11T09:10:37Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise [28.891930079358954]
  線形2時間スケールSAスキームに対して有限時間解析を行う。 我々の境界はマルコフ音とマルティンゲール音の収束速度に差がないことを示している。 一致した下界を持つ予測誤差の拡張を示す。
  論文  参考訳（メタデータ） (2020-02-04T13:03:17Z)

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

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