Nov, 2014

关于函数逼近的 TD (0)：集中界限和具有指数收敛的居中变量

PDF
TL;DR本文提出了针对使用线性函数逼近器的时间差分学习算法 TD (0) 的非渐近界限。同时，也指出了除非我们对政策的马尔科夫链的稳态分布（部分）具有知识，否则步长反比于迭代次数不能保证最优收敛率。此外，我们为迭代平均的 TD (0) 变体提供了界限，同时消除了步长的依赖性，并表现出最优的收敛速度。此外，我们还提出了一种包含置中序列的 TD (0) 线性逼近器变型，并证明它在期望下表现出指数级的收敛速度。最后，我们在两个人工实验中展示了这些界限的有用性。
temporal difference learninglinear function approximatorsmarkov chainconvergence rateiterate averaging
发现论文，激发创造
  • TD (0) 函数逼近的集中界

    我们得到了一种关于使用线性函数逼近进行 TD (0) 的集中界限。我们通过从底层马尔科夫链的单个样本路径中获取样本来处理在线 TD 学习，这使得我们的分析与离线 TD 学习或使用来自马尔科夫链的稳态分布的独立样本进行 TD 学习的情况显着不同。我们将 TD (0) 视为一种具有收敛性的随机逼近算法，其中同时存在鞅和马尔科夫噪声。使用泊松方程处理马尔科夫噪声，而使用松弛的集中不等式概念处理迭代的有界性的几乎确定性保证的缺失。

    Dec, 2023

  • TD (0) 函数逼近的有限样本分析

    本文是首篇对 TD (0) 算法在线性情况下基于函数逼近进行有限采样分析的研究，并且通过利用 TD (0) 的强大属性，提供了期望和高概率的收敛速率，并使用最近开发的随机逼近技术采用了不同的方法来获得这两种收敛速率。

    Apr, 2017

  • 自适应线性函数逼近时间差分学习

    本文提出了一种自适应投影变体的临时差异 (TD) 学习算法 AdaTD (0)，它具有线性函数逼近和可证明稳定性，其实验结果表明其对于标准强化学习任务具有有效性。

    Feb, 2020

  • 几乎没有通信的分布式 TD (0)

    本文提出了一种新的分布式时间差异学习方法，该方法采用 “一次性平均” 策略，在分布式过程结束时平均结果，证明了并行优化对于时间差异方法收敛时间的提升。

    May, 2023

  • 非线性 TD 学习收敛性的几何洞见

    本研究旨在推广理论收敛保证到具有非线性函数逼近的 TD 学习，考虑 TD (0) 算法估计值的预期学习动态，使用具有良好几何形状的函数逼近器的集合，证明了在更可逆的环境下 TD 学习的收敛性，同时进行了非线性的收敛和发散案例的探讨。

    May, 2019

  • 关于利用方差缩减方法对于随机连续环境下的时差学习进行修正

    本文研究了使用时差学习算法评估连续时间进程的策略评估问题，并根据随机微分方程的时间离散化来学习连续值函数。通过为差分学习提供零均值修正，我们提出了一种鲁棒的算法，包括两种算法：一种是基于模型的算法，另一种是基于无模型的算法，其收敛性得到了证明。此外，该方法还可用于机器学习中求解非发散二阶椭圆方程的问题。

    Feb, 2022

  • TD 学习与线性函数逼近的简单有限时间分析

    TD 学习在马尔可夫采样下，通过线性函数逼近存在有限时间收敛性的研究证明。通过新颖的两步论证方法，我们证明了在常数步长和标准选择下，TD 学习生成的迭代在期望上保持统一有界。这种方法大大简化了现有证明，并推测我们归纳证明技术将在更复杂的随机逼近算法分析中找到应用。

    Mar, 2024

  • 时差学习的有限样本分析

    评估折扣马尔可夫决策过程中，使用线性函数逼近的时序差异 (TD) 方法的性能限界，我们证明，使用通用且独立于实例的步长算法，结合 Polyak-Ruppert 尾部平均，可以获得接近最优的方差和偏差项，同时给出了相应的样本复杂性限界。

    Oct, 2023

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

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

    Feb, 2019

  • 关于某些基于梯度的时间差分离线学习算法的收敛性

    本文考虑了有限状态和折扣回报标准下的马尔科夫决策过程策略评估问题中的离策略时间差分 (TD) 学习方法，并针对几个基于梯度的 TD 算法提出了一组收敛性结果。

    Dec, 2017