本文提供了一个线性双时间尺度随机逼近方法的有限时间分析,结果表明在马尔可夫噪声和鞅噪声下没有收敛速率的区别,只有马尔可夫链的混合时间会影响常数,并提出了一个匹配的下界。
Feb, 2020
TD 学习在马尔可夫采样下,通过线性函数逼近存在有限时间收敛性的研究证明。通过新颖的两步论证方法,我们证明了在常数步长和标准选择下,TD 学习生成的迭代在期望上保持统一有界。这种方法大大简化了现有证明,并推测我们归纳证明技术将在更复杂的随机逼近算法分析中找到应用。
Mar, 2024
评估折扣马尔可夫决策过程中,使用线性函数逼近的时序差异 (TD) 方法的性能限界,我们证明,使用通用且独立于实例的步长算法,结合 Polyak-Ruppert 尾部平均,可以获得接近最优的方差和偏差项,同时给出了相应的样本复杂性限界。
Oct, 2023
本文研究了受 Markov 扰动影响的递归方程的误差界限。研究显示,均方误差实现了参数估计的最优速率 $O (1/n)$,并获得了速率中的确切常数,这对算法设计非常有价值。
研究了一种在 Markovian 噪声下的非线性随机逼近算法,证明了其具有不同学习速率的有限样本收敛界限,并证明了其适用于 Q-learning 算法。
May, 2019
本文提出了针对使用线性函数逼近器的时间差分学习算法 TD (0) 的非渐近界限。同时,也指出了除非我们对政策的马尔科夫链的稳态分布(部分)具有知识,否则步长反比于迭代次数不能保证最优收敛率。此外,我们为迭代平均的 TD (0) 变体提供了界限,同时消除了步长的依赖性,并表现出最优的收敛速度。此外,我们还提出了一种包含置中序列的 TD (0) 线性逼近器变型,并证明它在期望下表现出指数级的收敛速度。最后,我们在两个人工实验中展示了这些界限的有用性。
Nov, 2014
该研究针对不稳定线性系统的参数识别问题进行了研究,建立了针对重尾噪声分布和转移矩阵的一类较大误差最小二乘估计的有限时间界限,并与问题维度和真实转移矩阵的关键特征及噪声分布函数的性质相关联,并使用随机矩阵和鞅差序列的适当浓度不等式来实现这些结果。
Oct, 2017
本文研究两种时间尺度线性随机逼近算法,并使用一个基于奇异扰动理论的李雅普诺夫函数来得出有限时间性能界限,最终设计出一种自适应学习速率方案,以显著提高收敛速度和表现。
Jul, 2019
扩展 Borkar-Meyn 定理以适用于具有线性函数逼近和资格痕迹的离策略强化学习算法,分析随机逼近算法的稳定性和马尔可夫噪声条件下的边界性。
Jan, 2024
本研究研究了结合尾平均的时序差分(TD)学习算法的有限时间行为。研究发现,尾平均的 TD 在不需要信息的情况下,可以在期望和高概率下以最优的 $O (1/t)$ 速率收敛,我们提出和分析了一个增加了正则化的 TD 变量,结论表明正则化的 TD 对于具有病态特征的问题是有用的。
Oct, 2022