AAAIDec, 2020

梯度预期 Sarsa ($λ$) 的收敛性

PDF
TL;DR本研究针对线性函数近似下的 Expected Sarsa 算法的收敛问题，通过提出收敛性较好的 Gradient Expected Sarsa 算法，并应用 Lyapunov 函数技术分析其性能，得到较优实验结果。
expected sarsalinear function approximationoff-policy learninggradient expected sarsalyapunov function
发现论文，激发创造
  • 关于某些基于梯度的时间差分离线学习算法的收敛性

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

    Dec, 2017

  • 一种仅使用一个步长的新渐变 TD 算法：使用 $L$-$λ$ 平滑性进行收敛速率分析

    本文介绍了一种名为 Impression GTD 的全新 GTD 算法，通过最小化期望 TD 更新的范数目标实现单时间尺度，并证明该算法的收敛速度至少为 O (1/t)，甚至更快。同时，与现有的 GTD 算法相比，该算法在在线学习和离线学习问题中表现更快，具有比较稳定的步长范围。

    Jul, 2023

  • 带函数逼近的收敛树备份和 Retrace 方法

    该论文通过分析 extsc {Tree Backup} 和 extsc {Retrace} 算法在线性函数逼近下的不稳定性，提出了一种基于二次凸凹鞍点公式的稳定高效梯度下降算法，并证明了其收敛性和有限样本上界，同时还提供了对其他算法收敛速度的新证明。

    May, 2017

  • 状态依赖噪声的加速随机逼近

    本文讨论了一类随机光滑凸优化问题，其噪声的方差与算法产生的近似解的次优性有关，提出了两个非欧几里德加速随机逼近算法，即随机加速梯度下降（SAGD）和随机梯度外推（SGE），并证明了在适当的条件下，这两个算法可以同时达到最优的迭代和样本复杂度。同时本文还提出了应用 SGE 进行恢复稀疏解的方法。

    Jul, 2023

  • LSTD ($λ$) 的收敛速率和误差界

    本文考虑 LSTD (λ) 算法，推导出了任意 λ 及 β-mixing 条件下该算法收敛速率的高概率估计及误差的高概率界，探究了 λ 值选择对线性空间质量和样本数的影响。

    May, 2014

  • 马尔可夫环境下有限样本分析 GTD 策略评估算法

    本文首次针对 Markov 过程下 GTD 算法进行了有限样本边界分析，证明了变体步长的 GTD 算法会收敛且收敛速度与步长和混合时间有关，说明经验回放技巧通过改善 Markov 过程的混合性能有利于算法收敛。

    Sep, 2018

  • Proximal Gradient TD 算法的有限样本分析

    本文旨在分析梯度时序差分学习（GTD）算法族的收敛速率，将 GTD 方法制定为原始 - 对偶鞍点目标函数的随机梯度算法，并进行鞍点误差分析以获得其性能的有限样本界限，提出了两种改进的算法，即投影 GTD2 和 GTD2-MP，理论分析结果表明，GTD 算法族在脱离政策学习场景中与现有的 LSTD 方法相当。

    Jun, 2020

  • 线性函数逼近 SARSA 算法的收敛性：随机时限情况

    本研究探究了强化学习算法 SARSA 与线性函数逼近的收敛性问题，将算法应用于随机时长的马尔可夫决策问题中，证明了当行为策略为 ε-soft 且与线性函数逼近的权重向量 Lipschitz 连续时，该算法随机收敛的概率为 1。

    Jun, 2023

  • 强调时间差分学习的收敛性

    本文研究了在带有有限状态的折扣马尔可夫决策过程中对策略进行强调时间差分学习的算法。我们提出了 ELSTD（λ）和 ETD（λ）的首个收敛性证明，并针对一般的离线策略研究了 ELSTD（λ）迭代的 $L^1$ 收敛和使用单个无限长轨迹计算的近似值函数的两种算法的几乎必然收敛性。

    Jun, 2015

  • 面向噪声自适应、问题自适应（加速）随机梯度下降

    通过利用指数步长和随机线性搜索等技术，使得随机梯度下降算法适应不同噪声水平和问题相关的常数，可以在强凸函数的条件下，取得与理论最优相近的收敛速度，同时能够有效地处理噪声和数据不凸的情况。

    Oct, 2021