带控制的马尔科夫噪声和离线时差学习的两时间尺度随机逼近
本文提出了针对使用线性函数逼近器的时间差分学习算法TD(0)的非渐近界限。同时,也指出了除非我们对政策的马尔科夫链的稳态分布(部分)具有知识,否则步长反比于迭代次数不能保证最优收敛率。此外,我们为迭代平均的TD(0)变体提供了界限,同时消除了步长的依赖性,并表现出最优的收敛速度。此外,我们还提出了一种包含置中序列的TD(0)线性逼近器变型,并证明它在期望下表现出指数级的收敛速度。最后,我们在两个人工实验中展示了这些界限的有用性。
Nov, 2014
考虑由Markovian噪声驱动的线性随机逼近算法的动态特性,通过考虑适当选择的Lyapunov函数的漂移,获得常数步长算法的有限时间误差的二次矩的有限时间界限。我们还对逼近误差2范数的平方的矩进行了全面的处理。
Feb, 2019
本文对两时间尺度TDC算法在非独立同分布的马尔可夫抽样路径和线性函数逼近下的收敛性进行了非渐近收敛分析,并在此基础上提出了具有分块减小的步长的TDC算法,实验结果表明其具有与TDC常数步长收敛速度相当的收敛速度,并在减小步长的情况下仍保持与TDC相当的精度。
Sep, 2019
本文提供了一个线性双时间尺度随机逼近方法的有限时间分析,结果表明在马尔可夫噪声和鞅噪声下没有收敛速率的区别,只有马尔可夫链的混合时间会影响常数,并提出了一个匹配的下界。
Feb, 2020
本研究提出了一种新颖的多层蒙特卡罗渐进优化方法,针对含有Markov链随机数据的优化问题,能够在不知道Markov链混合时间的情况下获得最佳渐进收敛速率,并适用于非凸优化求解及在时间差分(TD)学习中获取更好的混合时间依赖性。
Feb, 2022
评估折扣马尔可夫决策过程中,使用线性函数逼近的时序差异(TD)方法的性能限界,我们证明,使用通用且独立于实例的步长算法,结合Polyak-Ruppert尾部平均,可以获得接近最优的方差和偏差项,同时给出了相应的样本复杂性限界。
Oct, 2023
用马尔可夫噪声对线性二时间尺度随机逼近算法进行了收敛性分析,得到了该算法各种步长选择下的收敛行为,应用结果到TDC算法得到了比之前工作更好的收敛性样本复杂度,该结果还适用于确定各种强化学习算法的收敛行为,如带有Polyak平均的TD学习,GTD和GTD2。
Dec, 2023
扩展Borkar-Meyn定理以适用于具有线性函数逼近和资格痕迹的离策略强化学习算法,分析随机逼近算法的稳定性和马尔可夫噪声条件下的边界性。
Jan, 2024
通过中心极限定理对双时间尺度随机逼近(TTSA)在受控马尔可夫噪声下进行了深入的渐近分析,揭示了受底层马尔可夫链影响的TTSA的耦合动态,从而扩展了其应用范围,并结合应用结果推断了使用马尔可夫样本的GTD算法的统计性质和渐近性能。
Jan, 2024
基于大规模和多智能体强化学习的应用,我们研究了在马尔可夫采样下具有延迟更新的随机逼近(SA)方案的非渐近性能。我们首先表明,在时间变化的有界延迟下,延迟的SA更新规则保证了“最后迭代”指数级快速收敛到SA操作符固定点周围的球体。与传统的延迟SA规则相比,我们的研究减缓了最大延迟对收敛速率的影响,并且不需要关于延迟序列的先验知识来进行步长调整。我们的理论发现揭示了延迟对一类算法的有限时间效果,包括TD学习、Q学习和马尔可夫采样下的随机梯度下降。
Feb, 2024