Jan, 2024

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

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

    本研究讨论了线性二时间尺度随机逼近方法的收敛速度，证明了它们的渐进协方差和建立了渐近正态性，通过本文的一般结果，证明了著名的 Polyak-Ruppert 平均技术在线性随机逼近中的最优性。

    May, 2004

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

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

    Dec, 2023

  • 线性二时间尺度随机逼近在马尔可夫噪声下的有限时间分析

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

    Feb, 2020

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

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

    May, 2024

  • 一种适用于嵌套随机优化的单时间尺度随机逼近方法

    研究了一个名为 NASA 的算法，在约束嵌套随机优化问题中，通过估计梯度来找到近似的稳定点，并使用特殊 Lyapunov 函数证明了该算法的样本复杂度为 O (1/ε²)，同时提出了简化版 NASA 算法来解决约束单层随机优化问题。

    Dec, 2018

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

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

    Mar, 2015

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

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

    Nov, 2020

  • 零和随机博弈中带有函数逼近的两时间尺度 Q-Learning

    我们提出了一种两时间尺度 Q 学习算法，采用函数逼近，以找到两个玩家之间公平、收敛、理性且对称的纳什均衡。我们的方法在线性函数逼近的特殊情况下，建立了无限采样边界，从而对这类随机博弈中收敛到纳什均衡所需的样本量提供了多项式的上界。

    Dec, 2023

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

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

    May, 2019

  • 线性随机逼近和 TD 学习的有限时间误差界

    考虑由 Markovian 噪声驱动的线性随机逼近算法的动态特性，通过考虑适当选择的 Lyapunov 函数的漂移，获得常数步长算法的有限时间误差的二次矩的有限时间界限。我们还对逼近误差 2 范数的平方的矩进行了全面的处理。

    Feb, 2019