論文の概要: Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2509.26442v1
• Date: Tue, 30 Sep 2025 16:00:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-01 17:09:04.609396
• Title: Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning
• Title（参考訳）: Robbins-Siegmund理論の拡張と強化学習への応用
• Authors: Xinyu Liu, Zixuan Xie, Shangtong Zhang,
• Abstract要約: 我々は、零次項が和可能ではなく、平方和可能であるような、ほとんど超行列に対してロビンス=ジークムントの定理を拡張する。 線形関数を持つ$Qp$学習に対する最初のほぼ確実な収束率、最初の高確率集中束縛、および最初の$Lp$収束率を得る。
• 参考スコア（独自算出の注目度）: 19.81737958703724
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Robbins-Siegmund theorem establishes the convergence of stochastic processes that are almost supermartingales and is foundational for analyzing a wide range of stochastic iterative algorithms in stochastic approximation and reinforcement learning (RL). However, its original form has a significant limitation as it requires the zero-order term to be summable. In many important RL applications, this summable condition, however, cannot be met. This limitation motivates us to extend the Robbins-Siegmund theorem for almost supermartingales where the zero-order term is not summable but only square summable. Particularly, we introduce a novel and mild assumption on the increments of the stochastic processes. This together with the square summable condition enables an almost sure convergence to a bounded set. Additionally, we further provide almost sure convergence rates, high probability concentration bounds, and $L^p$ convergence rates. We then apply the new results in stochastic approximation and RL. Notably, we obtain the first almost sure convergence rate, the first high probability concentration bound, and the first $L^p$ convergence rate for $Q$-learning with linear function approximation.
• Abstract（参考訳）: ロビンス=ジークムントの定理は、ほとんど超行列である確率過程の収束を確立し、確率近似と強化学習(RL)において幅広い確率反復アルゴリズムを解析するための基礎となる。 しかし、元の形式は、ゼロ次項を和可能であることを要求するため、かなりの制限がある。 しかし、多くの重要なRL応用において、この要約可能な条件は満たせない。 この制限は、零次項が総和可能ではなく、平方和可能であるようなほとんど超行列に対してロビンス=ジークムントの定理を拡張する動機となる。 特に,確率過程の増大について,新しい軽微な仮定を導入する。 これは平方和条件とともに、有界集合へのほぼ確実な収束を可能にする。 さらに、ほぼ確実に収束率、高い確率濃度境界、および$L^p$収束率を提供する。 次に,新しい結果を確率近似とRLに適用する。 特に、線形関数近似を用いたQ$学習において、最初のほぼ確実な収束率、第1の高確率濃度境界、第1の$L^p$収束率を得る。

関連論文リスト

• Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
  我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。 我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。 次に,新しい2段階クラスタリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-02T05:10:40Z)
• Nonasymptotic CLT and Error Bounds for Two-Time-Scale Stochastic Approximation [12.69327994479157]
  We consider linear two-time-scale approximation algorithm driven by martingale noise。 我々は、PolyakRuppert平均化を用いた2時間スケール近似のためのワッサーシュタイン-1距離に関する最初の漸近的中心極限定理を導出した。
  論文  参考訳（メタデータ） (2025-02-14T03:20:30Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
  最適解への初期距離に依存する有界収束を示す。 AdaGrad-Normのハイバウンドが得られることを示す。
  論文  参考訳（メタデータ） (2023-02-28T18:42:11Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning [3.655021726150368]
  マルチエージェント強化学習(MARL: Multi-Agent Reinforcement Learning)では、複数のエージェントが共通の環境と相互作用し、シーケンシャルな意思決定において共有問題を解く。 我々は、MARLで有用な分散非線形近似スキームの族を反復する新しい法則を導出する。
  論文  参考訳（メタデータ） (2021-10-27T08:01:17Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
  一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。 我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。 我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
  論文  参考訳（メタデータ） (2020-05-21T17:36:09Z)

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

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