无需投影和先验知识，单一步长实现TD(0)快速稳健收敛。
A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging
- 使用普罗克-鲁珀特平均与单一步长调度，无需投影即可保证迭代稳定。
- 同时获得曲率无关的√T和曲率相关的T⁻¹收敛速率，自动取最优。
- 适用于马尔可夫采样场景，特别适合缺乏模型参数先验的强化学习应用。
我们研究在马尔可夫采样下（数据沿单一轨迹生成）的线性TD(0)算法。通过采用基于混合时间τ_mix但不依赖曲率参数ω的单一步长调度η_t ∝ τ_mix log(t)/√t，结合普罗克-鲁珀特（PR）平均，我们提供了高概率保证。首先，该步长能确保未投影的TD(0)迭代在高概率下自动且统一有界，无需稳定性分析或对ω的假设。在此基础上，我们建立了PR平均的同步高概率收敛性：同一步长同时实现曲率无关的~O(τ_mix / √T)和曲率相关~O(τ_mix² / (ωT))收敛率，并取两者最小值。核心技术是针对几何混合马尔可夫链的泊松方程工具包，将马尔可夫噪声分解为鞅项加可控余项，从而支持路径上的自归约归纳论证。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。