马尔可夫噪声下随机逼近与强化学习的几乎必然收敛速率与集中不等式
Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise
Xiaochi Qian, Zixuan Xie, Xinyu Liu, Shangtong Zhang
AI 速读 基于摘要
该论文为马尔可夫噪声下的收缩随机逼近算法建立了首个几乎必然收敛速率和首个具有次Weibull尾部的最大集中不等式,并应用于Q学习和离策略时序差分学习。
cs.LG · math.OC · stat.ML
查看原文摘要
This paper establishes, to our knowledge, the first almost sure convergence rate and the first maximal concentration bound with sub-Weibull 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. Applications yield the first almost sure convergence rate for $Q$-learning without count-based learning rates and the first maximal concentration bound for off-policy temporal difference learning, both with Markovian samples.