Dec, 2023

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

PDF
TL;DR用马尔可夫噪声对线性二时间尺度随机逼近算法进行了收敛性分析，得到了该算法各种步长选择下的收敛行为，应用结果到 TDC 算法得到了比之前工作更好的收敛性样本复杂度，该结果还适用于确定各种强化学习算法的收敛行为，如带有 Polyak 平均的 TD 学习，GTD 和 GTD2。
stochastic approximationmarkovian noiseconvergence boundstep sizessample complexity
发现论文，激发创造
  • 线性二时间尺度随机逼近在马尔可夫噪声下的有限时间分析

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

    Feb, 2020

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

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

    Nov, 2020

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

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

    May, 2019

  • 具有马尔科夫噪声的双时间尺度随机逼近的中心极限定理：理论与应用

    通过中心极限定理对双时间尺度随机逼近（TTSA）在受控马尔可夫噪声下进行了深入的渐近分析，揭示了受底层马尔可夫链影响的 TTSA 的耦合动态，从而扩展了其应用范围，并结合应用结果推断了使用马尔可夫样本的 GTD 算法的统计性质和渐近性能。

    Jan, 2024

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

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

    Feb, 2024

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

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

    Mar, 2015

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

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

    Dec, 2023

  • 快速非线性两时间刻度随机逼近：达到 O (1/k) 有限样本复杂度

    提出了一种新的两时间尺度随机逼近方法，用于找到两个耦合非线性操作符的根，仅假定可以观察到这些操作符的噪声样本，并通过经典的 Ruppert-Polyak 平均技术动态估计操作符的样本，将所估计的平均步骤值用于两时间尺度随机逼近更新以找到所需的解，我们的主要理论结果是在强单调条件下，该方法生成的迭代序列的均方误差收敛到零的最优速率为 O (1/k)，其中 k 是迭代次数，这一结果显著改进了现有的两时间尺度随机逼近结果，其已知的有限时间收敛速率为 O (1/k^(2/3))。

    Jan, 2024

  • 利用平滑凸包的随机逼近的有限样本分析

    本文提出了一种基于广义 Moreau 信封的平滑 Lyapunov 函数方法，使用不同的步长展示了其在含噪声的固定点方程求解中的有限样本误差界，并将其应用于强化学习中的 V-trace 算法和 Q-learning，获得了现有最先进的结果，且收敛边界仅在状态空间大小上具有对数依赖。

    Feb, 2020

  • 快速二次时间尺度随机梯度法及其在强化学习中的应用

    提出了一种用于解决两时间尺度优化问题的新方法，通过利用平均化步骤改善算子的估计，消除了主要变量之间的直接耦合，从而大大加快了收敛速度，并在强凸性、凸性、Polyak-Lojasiewicz 条件和一般非凸性等各种情况下改进了传统两时间尺度随机逼近算法的复杂性，该算法在强化学习中表现出色，超越或与现有的最先进方法相匹配，并通过强化学习中的数值模拟验证了理论结果。

    May, 2024