論文の概要: $O(1/n)$ Convergence Rate for RVI $Q$-Learning

• arxiv url: http://arxiv.org/abs/2611.07676v1
• Date: Thu, 05 Nov 2026 09:05:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-06 21:50:50.612365
• Title: $O(1/n)$ Convergence Rate for RVI $Q$-Learning
• Title（参考訳）: $O(1/n)$ Convergence Rate for RVI $Q$-Learning
• Abstract要約: 同期相対値反復に対する有限時間収束保証を確立する。 これらの保証はインスタンス依存であり、ヒットタイムパラメータと第2のベストポリシーの最適値以下のギャップに依存する定数を持つ。
• 参考スコア（独自算出の注目度）: 6.8909174388650785
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish finite-time convergence guarantee for synchronous relative value iteration (RVI) $Q$-learning for finite weakly communicating Markov decision processes (MDPs). For stochastic Krasnosel'skiĭ--Mann iterations driven by a non-expansive, linearly regular map on a finite-dimensional normed space, we establish last-iterate mean-squared residual bounds under martingale-difference noise whose conditional second moment grows at most linearly with the squared residual. Suitable polynomial stepsizes of order $n^{-a}$ yield an $O(n^{-a})$ rate for $0<a\leq1$. We verify linear regularity and the noise condition for the centered Bellman operator for finite weakly communicating MDPs. Applying the general result gives an $O(n^{-1})$ bound on the mean-squared Bellman span residual of RVI $Q$-learning iterates when a suitable stepsize sequence is used. The positive gap between optimal and suboptimal stationary deterministic policies then yields an $O(n^{-1})$ bound on the expected suboptimality of the greedy policy. Consequently, $O(ε^{-1})$ synchronous iterations suffice for an $ε$-optimal policy in expectation. These guarantees are instance-dependent, with constants that depend on the hitting-time parameters and the suboptimality gap of the second-best policy.
• Abstract（参考訳）: 同期相対値反復 (RVI) に対する有限時間収束保証を有限弱通信マルコフ決定過程 (MDP) に対して$Q$-learning で確立する。 有限次元ノルム空間上の非拡大線型正則写像によって駆動される確率的クラスノゼル・スキー-マンの反復に対して、条件付き第二モーメントが正方形残差とともに最も線型に成長するマルティンゲール微分雑音の下で、最終定位平均二乗残差を確立する。 適当な多項式は位数$n^{-a}$の次数$0<a\leq1$の$O(n^{-a})$レートを段階化する。 有限弱通信MDPに対する中心ベルマン作用素の線形正則性と雑音条件を検証する。 一般結果を適用すると、RVI $Q$-learning の残余を平均二乗ベルマン上の$O(n^{-1})$バウンドが、適切なステップサイズシーケンスを使用するときに反復する。 最適および準最適定常決定性ポリシーの間の正のギャップは、グリーディポリシーの期待される準最適性に依存する$O(n^{-1})$となる。 その結果、$O(ε^{-1})$ sync iterations は期待する$ε$-optimal policy に十分である。 これらの保証はインスタンス依存であり、ヒットタイムパラメータと第2のベストポリシーの最適値以下のギャップに依存する定数を持つ。

関連論文リスト

• Convergence Analysis of STORM Under Different Geometries [54.00747543528431]
  分散低減効果により,STORMは非最適化のための高速収束を実現することを示す。 すべての結果は同じです。 同じ選択をしました
  論文  参考訳（メタデータ） (2026-10-01T12:46:42Z)
• Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
  オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。 長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
  論文  参考訳（メタデータ） (2026-09-30T21:03:03Z)
• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• A Convergence Framework for Deep $V$-Learning: Error Propagation and Sharp Action-Gap Bounds [0.0]
  更新エラーを、フィッティング、遷移再利用、ターゲット構築、リプレイ、アクション選択、探索の6つの残差に分解する。 次数$n-$の統計的誤差境界に対して、最適連続割り当てと、制約された最適値の係数2$以内の整数割り当てを導出する。 これらの結果から, FIFO/インターリーブされたSGDに対して, 厳密な動作スコアを有する固定水平生成-リセット近似-ERM法に対して, 期待されるポリシ-ロス一貫性が得られた。
  論文  参考訳（メタデータ） (2026-09-16T15:03:46Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)

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

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