論文の概要: Sharp Statistical Rates for Asynchronous TD Learning with Markovian Data
- arxiv url: http://arxiv.org/abs/2609.38880v1
- Date: Wed, 30 Sep 2026 03:31:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-01 18:57:27.122677
- Title: Sharp Statistical Rates for Asynchronous TD Learning with Markovian Data
- Title（参考訳）: Markovianデータを用いた非同期TD学習におけるシャープ統計率
- Abstract要約: 最期TDが超ノーム誤差を最大$varepsilon$で高い確率で達成することを証明する。
既知の決定論的報酬を持つ三状態構成は、統計的および混合項に対して一致するミニマックス境界を低くする。
- 参考スコア（独自算出の注目度）: 11.004709593999296
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the last iterate of standard tabular temporal-difference (TD) learning from a single trajectory of a finite Markov reward process. For discount factor $γ$, write $H=(1-γ)^{-1}$, and let $μ_{\min}$ and $t_{\operatorname{mix}}$ denote the minimum stationary probability and total-variation mixing time. We prove that last-iterate TD achieves sup-norm error at most $\varepsilon$ with high probability using$\widetilde O\left( \frac{H^3}{μ_{\min}\varepsilon^2} +\frac{t_{\operatorname{mix}}}{μ_{\min}} \right)$ transitions, for $0<\varepsilon\leq1$. This rate holds both for a constant step size selected for the target accuracy and for a decreasing schedule independent of the target accuracy and terminal time. The latter gives a simultaneous guarantee over all times beyond an explicit transient threshold. The statistical term retains the cubic effective-horizon dependence of synchronous TD, and the additive mixing transient has no extra horizon factor. The result allows non-reversible chains, arbitrary initial state distributions, and bounded rewards that may depend on the next state. The proof uses an anchored local Poisson equation in reverse time to control stochastic fluctuations without a mixing-time factor, and a hitting-time compensation identity to bound initialization error. The latter also yields a finer transient in terms of the worst expected reverse hitting time. A bound on the expected cumulative propagation mass extends this argument to decreasing step sizes. A three-state construction with known deterministic rewards gives matching minimax lower bounds for the statistical and mixing terms, up to logarithms, over specified model classes in a slow-mixing parameter regime.
- Abstract（参考訳）: 有限マルコフ報酬過程の単一軌道からの標準表時差学習の最後の繰り返しについて検討する。
割引係数 $γ$, write $H=(1-γ)^{-1}$, and let $μ_{\min}$ and $t_{\operatorname{mix}}$ は最小の定常確率と全変量混合時間を表す。
終点の TD が sup-norm 誤差を最大$\varepsilon$ で達成し、高い確率で$\widetilde O\left( \frac{H^3}{μ_{\min}\varepsilon^2} +\frac{t_{\operatorname{mix}}}{μ_{\min}} \right)$ transitions, for $0<\varepsilon\leq1$ で証明する。
このレートは、目標精度に選択された一定のステップサイズと、目標精度と終点時間によらずスケジュールを減少させる。
後者は、明示的な過渡しきい値を超えて、常に同時に保証する。
統計項は同期性TDの立方的有効-水平依存性を保ち、加法混合過渡度は余分な水平係数を持たない。
その結果、可逆鎖、任意の初期状態分布、および次の状態に依存するかもしれない有界報酬が許される。
この証明は固定された局所ポアソン方程式を逆時間で使用し、混合時間係数を使わずに確率的変動を制御し、バウンド初期化誤差に対するヒット時間補償同一性を与える。
後者はまた、予想される最悪の逆打時間の観点から、より微妙な過渡性が得られる。
期待累積伝播質量に縛られると、この議論はステップサイズを減少させる。
既知の決定論的報酬を持つ3状態構成は、統計および混合項の最小値の下限を、遅い混合パラメータ状態の特定のモデルクラスに対して対数まで与える。
関連論文リスト
- The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives [26.189892200366895]
本研究では、非拘束な滑らかな凸対象に対する標準降下勾配(SGD)の原繰り返しの時間一様収束について検討する。
標準的な雑音仮定の下では、時間一様収束速度が$sqrtlog n / n$に任意に近づくが、それに到達することはないことを証明している。
論文 参考訳（メタデータ） (2026-09-08T10:24:19Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Time-Uniform Self-Normalized Concentration for Discounted Least Squares: Limits and Corrections [1.599072005190786]
自己正規化濃度の不等式は、バンドおよび強化学習分析における標準ツールである。
広く使われている重み付き拡張は、非定常問題における割引最小二乗推定器に対する類似の時間一様保証を主張する。
重み付き不等式は、固定決定論的時間毎に有効であることを示し、有効有限および無限水平補正を与え、下流解析の結果について議論する。
論文 参考訳（メタデータ） (2026-08-20T05:19:11Z) - Asymptotic-Preserving A Posteriori Analysis of Diffusion and Flow-Matching Samplers [0.6768558752130311]
拡散及びフローマッチングサンプリングは、学習した確率フローODEを、大きなノイズスケールから小さな終端フロア($_min$)まで統合し、スコアが硬く、フローが境界層を発達させる。
特異摂動パラメータとして$_min$を扱い、どの固定ステップサンプリングが解けるかを決定する。
論文 参考訳（メタデータ） (2026-07-05T04:48:33Z) - A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging [11.513419525702924]
我々は、Polyak-Ruppert平均化を用いた非計画的TD(0)アルゴリズムの高確率保証を提供する。
この結果に基づいて,PR平均に対する同時高確率収束保証を確立する。
論文 参考訳（メタデータ） (2026-06-23T13:37:01Z) - From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。
実現可能な最小二乗の設定において、新しい最上界を創出する。
我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
論文 参考訳（メタデータ） (2025-04-06T18:39:45Z) - Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation [49.1574468325115]
時間差分学習(TD(0))は強化学習の基本である。
マルコフデータを混合したバニラTD(0)の最初の高確率有限サンプル解析を行う。
論文 参考訳（メタデータ） (2025-02-08T22:01:02Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。