Feb, 2024

具有延迟更新的随机逼近：马尔科夫采样下的有限时间收敛速率

PDF
TL;DR基于大规模和多智能体强化学习的应用，我们研究了在马尔可夫采样下具有延迟更新的随机逼近（SA）方案的非渐近性能。我们首先表明，在时间变化的有界延迟下，延迟的 SA 更新规则保证了 “最后迭代” 指数级快速收敛到 SA 操作符固定点周围的球体。与传统的延迟 SA 规则相比，我们的研究减缓了最大延迟对收敛速率的影响，并且不需要关于延迟序列的先验知识来进行步长调整。我们的理论发现揭示了延迟对一类算法的有限时间效果，包括 TD 学习、Q 学习和马尔可夫采样下的随机梯度下降。
发现论文，激发创造
  • 线性二时间尺度随机逼近在马尔可夫噪声下的有限时间分析

    本文提供了一个线性双时间尺度随机逼近方法的有限时间分析，结果表明在马尔可夫噪声和鞅噪声下没有收敛速率的区别，只有马尔可夫链的混合时间会影响常数，并提出了一个匹配的下界。

    Feb, 2020

  • 具有马尔可夫噪声的双时间尺度线性随机逼近的紧限定时间界

    用马尔可夫噪声对线性二时间尺度随机逼近算法进行了收敛性分析，得到了该算法各种步长选择下的收敛行为，应用结果到 TDC 算法得到了比之前工作更好的收敛性样本复杂度，该结果还适用于确定各种强化学习算法的收敛行为，如带有 Polyak 平均的 TD 学习，GTD 和 GTD2。

    Dec, 2023

  • 非线性随机逼近的有限样本分析及其在强化学习中的应用

    研究了一种在 Markovian 噪声下的非线性随机逼近算法，证明了其具有不同学习速率的有限样本收敛界限，并证明了其适用于 Q-learning 算法。

    May, 2019

  • DASA：延迟自适应多智能体随机逼近

    我们提出了一种延迟自适应的算法 exttt {DASA}，在多智能体随机逼近中实现了收敛速度的 $N$ 倍加速，同时仅依赖于混合时间 $ mix$ 和平均延迟 $ au_{avg}$，这一结果领先于现有研究。

    Mar, 2024

  • 异步随机逼近与 Q 学习的有限时间分析

    研究了一种异步随机逼近算法，并证明了在单轨迹上其有限时间收敛速率的上限，具体的将其应用到异步 Q-learning 中，得到了和同步 Q-learning 相同水平、优于先前已知的异步 Q-learning 的速率上限。

    Feb, 2020

  • 基于线性函数逼近的 SARSA 有限样本分析

    本文研究了在非独立同分布数据下具有线性函数逼近的 SARSA 算法，并开发了一种新的技术来显式表征随着时间变化的马尔科夫转移核的一类随机逼近过程的随机偏差，从而提供了基于有限样本的 SARSA 算法的均方误差有限样本分析以及配适的 SARSA 算法，后者包括原始 SARSA 算法及其变体，提供了比逐步更新策略迭代更高效的泛化框架。

    Feb, 2019

  • 带控制的马尔科夫噪声和离线时差学习的两时间尺度随机逼近

    本研究首次提出两个时间尺度随机逼近的渐近收敛性分析，其中包括非加性控制的马尔可夫噪声。通过与限制微分协同关系进行比较，分析了控制马尔可夫过程的基于随机逼近的渐近行为，最终提供了具有线性功能逼近的离策略收敛问题的解决方案。

    Mar, 2015

  • 带有延迟更新的随机梯度下降的紧密收敛分析

    本文提供基于生成函数的优化算法收敛性分析技巧，研究了梯度下降以及随机梯度下降在二次函数上的有限时间收敛性，证明了在有随机噪声的情况下，延迟对算法的影响可以被忽略，且在分布式优化问题上，加入延迟不会影响性能，且可和同步方法相媲美。

    Jun, 2018

  • 两时间尺度值基强化学习算法的样本复杂度界限

    本文研究了基于价值的强化学习算法中，线性和非线性时间差分学习和贪婪梯度 Q 算法的两个时间尺度随机逼近的非渐进收敛速率和样本复杂度，并给出了最优的样本复杂度和最优化误差控制速率。

    Nov, 2020

  • 随机逼近的收敛速度：有偏差噪声与无界方差，及其应用

    该研究论文主要讨论了随机逼近算法在嘈杂测量、凸凹优化、强化学习以及马尔可夫逼近方面的应用，并且扩展了该算法以包含具有非零条件均值和 / 或无界条件方差的错误，从而证明了算法在这些情况下的收敛性，并计算了 “优化步长序列” 以最大化估计的收敛速率。

    Dec, 2023