論文の概要: Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples
- arxiv url: http://arxiv.org/abs/2606.05967v1
- Date: Thu, 04 Jun 2026 10:10:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-05 22:39:44.714751
- Title: Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples
- Title（参考訳）: 線形関数近似, ユニバーサル学習ステップ, I.I.D.サンプルを用いたTD(0)の高速・ロバスト収束率
- Authors: Ziad Kobeissi, Éloïse Berthier,
- Abstract要約: 線形関数近似(LFA)を用いたTD(0)時間差分法の有限時間挙動について検討する。
近似関数上の平均二乗誤差 (MSE) に対して新たな収束率を確立し、(i) 反復数 k における最適依存を許容するという意味で、(i) 高速である。
- 参考スコア（独自算出の注目度）: 0.8594140167290097
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the finite-time behavior of the TD(0) temporal-difference method with linear function approximation (LFA). We consider on-policy independent and identically distributed (i.i.d.) samples, a constant learning step, and the Polyak-Juditsky averaging method. We establish a new convergence rate, for the Mean-Square Error (MSE) on the approximated function, that is (i) fast in the sense that it admits an optimal dependency in the number of iterations k (i.e., of order 1/k), (ii) robust to ill-conditioning: it only depends on an initial error and modelindependent constants and (iii) sharp up to a multiplicative constant lower than 11. In particular, it does not depend on the smallest eigenvalue of the uncentered covariance matrix of the linear parametrization, unlike all pre-existing O(1/k) rates in the TD(0) literature. We also introduce PCTD(0), a variant of TD(0), which benefits from better convergence properties under an additional assumption of strong mixing on the Markov Chain.
- Abstract（参考訳）: 本稿では,線形関数近似(LFA)を用いたTD(0)時間差分法の有限時間挙動について検討する。
我々は、独立・同一分布(すなわち、一定の学習段階)とPolyak-Juditsky平均化法について考察する。
我々は、近似関数上の平均二乗誤差(MSE)に対して、新しい収束率を確立する。
(i) k の反復数(すなわち 1/k の次数)に最適な依存が認められるという意味では、速い。
(ii) 条件不履行に対する堅牢性: 初期エラーとモデルに依存しない定数にのみ依存する。
(iii)11未満の乗算定数まで鋭くする。
特に、TD(0) の文献における既存のすべての O(1/k) レートとは異なり、線型パラメトリゼーションの非中心共分散行列の最小固有値に依存しない。
また,TD(0) の変種である PCTD(0) も導入し,マルコフ連鎖上での強い混合の仮定の下で,より良い収束特性の恩恵を受ける。
関連論文リスト
- Stability and Sensitivity Analysis of Relative Temporal-Difference Learning: Extended Version [0.0]
相対時間差学習(TD)は、割引係数が1に近づくと、TD法の緩やかな収束に導入された。
本稿では,線形関数近似を用いて相対的TD学習を分析する。
論文 参考訳（メタデータ） (2026-03-29T21:19:19Z) - Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。
PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。
得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
論文 参考訳（メタデータ） (2025-12-01T02:52:33Z) - Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation [49.1574468325115]
時間差分学習(TD(0))は強化学習の基本である。
マルコフデータを混合したバニラTD(0)の最初の高確率有限サンプル解析を行う。
論文 参考訳（メタデータ） (2025-02-08T22:01:02Z) - Statistical Inference for Temporal Difference Learning with Linear Function Approximation [55.80276145563105]
The statistics properties of Temporal difference learning with Polyak-Ruppert averaging。
3つの理論的な貢献により、現在の最先端の成果が向上する。
論文 参考訳（メタデータ） (2024-10-21T15:34:44Z) - Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability [17.771354881467435]
一般化された, インスタンスに依存しないステップサイズを持つ単純なアルゴリズムは, ほぼ最適分散とバイアス項を得るのに十分であることを示す。
本手法は, 線形近似のための洗練された誤差境界と, ランダム行列の積に対する新しい安定性結果に基づく。
論文 参考訳（メタデータ） (2023-10-22T12:37:25Z) - Distributed TD(0) with Almost No Communication [15.321579527891457]
線形関数近似を用いた時間差分学習の非漸近解析法を提案する。
分散過程の収束時間がTD(0)の収束時間よりもN$の係数である線形時間高速化現象のバージョンを実証する。
論文 参考訳（メタデータ） (2023-05-25T17:00:46Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z) - Adaptive Temporal Difference Learning with Linear Function Approximation [29.741034258674205]
本稿では,強化学習における政策評価タスクにおける時間差(TD)学習アルゴリズムを再検討する。
線形関数近似を用いたTD(0)学習アルゴリズムの確率収束適応型射影多様体を開発した。
いくつかの標準強化学習タスクにおいて,AdaTD(0)とAdaTD($lambda$)の性能を評価する。
論文 参考訳（メタデータ） (2020-02-20T02:32:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。