arXiv：cs.LG· Yang Peng·· 13 小时前
异步 TD 学习用 Markov 数据达到近极小极大最优速率
Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data
AI 导读
研究单条轨迹下标准重要性加权 TD 学习最后一次迭代的收敛速率，证明在行为策略 b 不可约、可能周期性的状态链上，以高概率达到 sup-norm 误差不超过 ε 需 Õ(ϱH³/(μ_min ε²)+𝔥⋆) 次转移，统计项保持同步 TD 的三次有效时域依赖，初始化代价对 𝔥⋆ 可加。
正文
Abstract:We study the last iterate of standard importance-weighted temporal-difference (TD) learning from a single trajectory of a finite Markov decision process. The trajectory follows a behavior policy $b$ with an irreducible, possibly periodic state chain; a target policy $\pi$ covered by $b$ is evaluated with action importance ratios bounded by $\varrho$. Write $H=(1-\gamma)^{-1}$, with $\mu_{\min}$ the minimum stationary probability and $\mathfrak h_\star$ the largest expected hitting time of the reverse behavior state chain. We prove that the last iterate achieves sup-norm error at most $\varepsilon$ with high probability after $\widetilde O(\varrho H^3/(\mu_{\min}\varepsilon^2)+\mathfrak h_\star)$ transitions for $0<\varepsilon\le1$. The statistical term retains the cubic effective-horizon dependence of synchronous TD, while the initialization cost is additive in $\mathfrak h_\star$. Setting $b=\pi$ and $\varrho=1$ recovers the on-policy rate. For aperiodic behavior chains, $\mathfrak h_\star=\widetilde O(t_{\rm mix}/\mu_{\min})$ recovers a mixing-time bound. The proof combines an anchored local Poisson equation in reverse time to control fluctuations without a mixing-time factor, a compensation argument for successive hitting costs, and an expected cumulative propagation mass bound for decreasing step sizes. Given the policy ratios and their bound, an empirical state-count rule attains the same rate without prior knowledge of model parameters. The framework covers nonnegative affine importance-weighted prediction updates, including successor features, transition-dependent discounting, and coupled finite-mode predictions. A perturbation estimate yields a time-uniform guarantee for online return-variance estimation. A three-state, two-action construction gives matching minimax lower bounds for both terms up to logarithmic factors on the considered parameter classes.
| Subjects: | Machine Learning (stat.ML); Machine Learning (cs.LG) |
| Cite as: | arXiv:2609.38880 [stat.ML] |
| (or arXiv:2609.38880v2 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2609.38880 arXiv-issued DOI via DataCite |
Submission history
From: Yang Peng [view email]
[v1]
Wed, 30 Sep 2026 03:31:05 UTC (44 KB)
[v2]
Fri, 9 Oct 2026 17:16:04 UTC (61 KB)
来源：arXiv：cs.LG · arxiv.org