为异步Q学习提供高维中心极限定理的收敛速率分析。
Gaussian Approximation for Asynchronous Q-learning
- 基于多项式步长的Polyak-Ruppert平均迭代，推导出收敛速率。
- 在n次采样下，收敛速率可达n^{-1/6} log⁴(nSA)。
- 结果适用于状态-动作-下一状态序列满足几何遍历性的场景。
本文推导了在多项式步长k^{-ω}（ω∈(1/2,1]）下，异步Q学习算法生成的Polyak-Ruppert平均迭代的高维中心极限定理收敛速率。假设状态-动作-下一状态三元组序列{(s_k,a_k,s_{k+1})}_{k≥0}构成统一几何遍历马尔可夫链，建立了在超矩形类上收敛速率高达n^{-1/6} log⁴(nSA)的结果，其中n为算法使用样本数，S和A分别为状态数与动作数。为此，我们证明了一个关于鞅差和的高维中心极限定理，可能具有独立研究价值。最后，给出了算法最终迭代项的高阶矩界。
原文摘要 · Abstract (English)
In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak-Ruppert averaged iterates generated by the asynchronous Q-learning algorithm with a polynomial stepsize $k^{-ω},\, ω\in (1/2, 1]$. Assuming that the sequence of state-action-next-state triples $(s_k, a_k, s_{k+1})_{k \geq 0}$ forms a uniformly geometrically ergodic Markov chain, we establish a rate of order up to $n^{-1/6} \log^{4} (nS A)$ over the class of hyper-rectangles, where $n$ is the number of samples used by the algorithm and $S$ and $A$ denote the numbers of states and actions, respectively. To obtain this result, we prove a high-dimensional central limit theorem for sums of martingale differences, which may be of independent interest. Finally, we present bounds for high-order moments for the algorithm's last iterate.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。