首次给出带马尔可夫噪声的强化学习算法几乎必然收敛速度与指数尾部集中界
Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise
- 用递减区间离散均值微分方程，突破传统恒定区间的限制
- 首次获得Q-learning和时序差分学习在马尔可夫样本下的几乎必然收敛速率
- 适合研究强化学习理论收敛性与概率分析的学者参考
本文首次建立了带有马尔可夫噪声的一般收缩型随机逼近算法的几乎必然收敛速率及具有指数尾部的最大集中界。作为推论，我们还获得了 $L^p$ 收敛速率。成功的关键在于提出一种新颖的均值微分方程离散化方法，采用长度递减的区间（而非恒定长度）。作为应用，我们首次给出了无需计数学习率的 $Q$-learning 在马尔可夫样本下的几乎必然收敛速率；同时，首次为使用马尔可夫样本的离策略时序差分学习提供了集中界。
原文摘要 · Abstract (English)
This paper establishes the first almost sure convergence rate and the first maximal concentration bound with exponential tails for general contractive stochastic approximation algorithms with Markovian noise. As a corollary, we also obtain convergence rates in $L^p$. Key to our successes is a novel discretization of the mean ODE of stochastic approximation algorithms using intervals with diminishing (instead of constant) length. As applications, we provide the first almost sure convergence rate for $Q$-learning with Markovian samples without count-based learning rates. We also provide the first concentration bound for off-policy temporal difference learning with Markovian samples.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。