論文の概要: A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging

• arxiv url: http://arxiv.org/abs/2606.24981v1
• Date: Tue, 23 Jun 2026 13:37:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-25 17:05:30.079645
• Title: A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging
• Title（参考訳）: 非射影線形TD(0)の1ステップサイズ:ポリアク-ラッパート平均化による同時ロバストと高速化
• Authors: Wei-Cheng Lee, Francesco Orabona,
• Abstract要約: 我々は、Polyak-Ruppert平均化を用いた非計画的TD(0)アルゴリズムの高確率保証を提供する。 この結果に基づいて,PR平均に対する同時高確率収束保証を確立する。
• 参考スコア（独自算出の注目度）: 11.513419525702924
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study linear TD(0) under Markovian sampling, where data are generated along a single trajectory. We provide high-probability guarantees for a plain unprojected TD(0) algorithm with Polyak-Ruppert (PR) averaging, using a single stepsize schedule $η_t \propto \frac{1}{τ_{\mathrm{mix}}\log(t)\sqrt{t}}$ that depends on the mixing time but requires no prior knowledge of the curvature parameter $ω$. Our first result shows that such a choice of the stepsize guarantees that the TD(0) iterates are automatically and uniformly bounded with high probability, without projections and without any stability argument based on $ω$. Building on this result, we establish a simultaneous high-probability convergence guarantee for the PR average: the same stepsize yields both a robust curvature-free $\widetilde{\mathcal{O}}\!\left(\frac{τ_{\mathrm{mix}}}{\sqrt{T}}\right)$ rate and a fast curvature-dependent $\widetilde{\mathcal{O}}\!\left(\frac{τ_{\mathrm{mix}}^2}{ωT}\right)$rate, with the bound taking the minimum of the two. The core technical ingredient is a Poisson-equation toolkit for geometrically mixing Markov chains, which decomposes Markov noise into a martingale term plus a controlled remainder and enables a new self-bounding inductive argument for pathwise stability.
• Abstract（参考訳）: 我々はマルコフサンプリングの下で線形TD(0)について検討し、そこでは1つの軌道に沿ってデータが生成される。 単段階スケジュール $η_t \propto \frac{1}{τ_{\mathrm{mix}}\log(t)\sqrt{t}}$ は混合時間に依存するが、曲率パラメータ $ω$ の事前知識を必要としない。 最初の結果は、ステップサイズのそのような選択は、TD(0) のイテレートが射影や$ω$に基づく安定性の議論なしに、自動的に一様かつ高い確率で有界であることを保証していることを示している。 この結果に基づいて、PR平均に対して同時に高確率収束保証を確立する:同じステップサイズは、ロバストな曲率のない$\widetilde{\mathcal{O}}\! \left(\frac{τ_{\mathrm{mix}}}{\sqrt{T}}\right)$ rate and a fast curvature-dependent $\widetilde{\mathcal{O}}\! \left(\frac{τ_{\mathrm{mix}}^2}{ωT}\right)$rate, with the bound take the minimum of the two。 中心となる技術要素は、マルコフ鎖を幾何学的に混合するポアソン方程式ツールキットであり、マルコフノイズをマルティンゲール項と制御された残余に分解し、経路安定性のための新たな自己有界帰納的議論を可能にする。

関連論文リスト

• Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition [7.186083931122418]
  本研究では,行列ベクトル積 (MVP) のオラクルによる行列フリー固有分解について検討した。 標準的な近似法では、安定性を$|C_k|$に結合する固定ステップを使用するか、あるいは更新の消滅によって遅くなる適応ステップを使用する。 対角化目標と入力-状態安定性解析のための厳密なサドルと、トレースフリーな摂動の下での複雑さのスケーリングを$O(|C_e|2 / (2))$とすることで、グローバル収束を確立する。
  論文  参考訳（メタデータ） (2026-02-14T13:09:29Z)
• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm [31.539921770584005]
  本研究では,高収束率を確保しつつ制約を適切に管理するPrimal-Dual Natural Actor-Criticアルゴリズムを提案する。 この結果はマルコフ決定過程の理論的下限と一致し、平均報酬CMDPの理論的探索において新しいベンチマークを確立する。
  論文  参考訳（メタデータ） (2025-05-21T05:49:11Z)
• Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation [49.1574468325115]
  時間差分学習(TD(0))は強化学習の基本である。 マルコフデータを混合したバニラTD(0)の最初の高確率有限サンプル解析を行う。
  論文  参考訳（メタデータ） (2025-02-08T22:01:02Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
  本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。 我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。 我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
  論文  参考訳（メタデータ） (2022-04-06T13:50:33Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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