IJCAINov, 2015

增量式截断最小二乘法

PDF
TL;DR本文介绍了一种低秩 LSTD 算法，该算法能更好地平衡计算效率和采样效率，使过去的样本高效地实现对最少二乘法时间差分（LSTD）的采样复杂度，同时实现近似 LSTD 的样本复杂度。我们在模拟中给出了关于截断低秩逼近所得解的模拟界限，这表明一个偏差 - 方差折衷需要依赖秩的选择。我们证明了该算法在基准任务和高维能量分配领域的策略评估中有效地平衡了计算复杂性和采样效率。
reinforcement learningtemporal difference learninglstdcomputation efficiencysample efficiency
发现论文，激发创造
  • 一种基于 Dantzig Selector 的时序差分学习方法

    本文介绍了一种新的算法，通过将 LSTD 与 Dantzig Selector 结合，解决了 L1 正则化与 LSTD 整合的困难问题，该算法适用于高维问题。

    Jun, 2012

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

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

    May, 2014

  • 强化学习中 LSTD 和随机特征的双下降

    研究论文通过理论分析和数值实验，研究了深度强化学习中时间差分算法的表现受神经网络规模和 $l_2$- 正则化的影响，发现参数和状态的比例是一个关键因素，还观察到双谷现象，即当参数 / 状态比例为 1 时性能会突然下降。

    Oct, 2023

  • 基于随机投影和资格追踪的 LSTD 有限样本分析

    该研究提出了一种利用随机投影和资格痕迹策略处理高维特征空间下的政策评估问题的新算法，经过理论分析，证明其比之前的算法表现更好。

    May, 2018

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

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

    Oct, 2023

  • 时序差异学习在罕见事件预测中的令人惊讶的效率

    我们定量地评估了强化学习中政策评估的时间差异（TD）学习与直接或蒙特卡罗（MC）估计器的效率，重点在于对罕见事件的相关数量的估计。我们证明了有限状态马尔可夫链中最小二乘 TD（LSTD）预测相较于 MC 能够更有效地实现相对准确性，并且通过简单的数量来验证了 LSTD 估计器的中心极限定理和相对渐近方差的上界。利用这个界限，我们证明了即使在罕见事件的时间尺度和 MC 估计器的相对准确性对于状态数都是指数级增长的情况下，LSTD 仍然能够以仅与状态数呈多项式级增长的马尔可夫链观测转换总数维持固定水平的相对准确性。

    May, 2024

  • 深度强化学习的快速价值追踪

    我们的研究利用卡尔曼滤波范式引入了一种称为 Langevinized Kalman Temporal-Difference (LKTD) 的新颖且可扩展的采样算法，用于深度强化学习。通过 LKTD 算法，我们有效地从深度神经网络参数的后验分布中抽样，而且我们证明了在温和条件下，LKTD 算法生成的后验样本收敛到一个稳定分布。这种收敛不仅使我们能够量化价值函数和模型参数相关的不确定性，而且在训练阶段中允许我们监控这些不确定性。LKTD 算法为更加强健和适应性的强化学习方法打开了道路。

    Mar, 2024

  • 基于核的时间差分方法的最优策略评估

    本文提出一种基于重现核希尔伯特空间的方法来估算无限时间折扣马尔可夫奖励过程的值函数的方法，并使用经验过程理论技术导出了误差的上界，同时证明了在样本大小 n 和有效时间跨度 H = (1-gamma)^{-1} 方面具有最优的最小值。

    Sep, 2021

  • 面向重尾奖励的可证明鲁棒时序差分学习

    本文探讨了强化学习中，奖励分布呈现重尾分布时，采用动态梯度裁剪机制的 TD 学习和 NAC 方法能够应对此类问题，论证了采用动态梯度裁剪机制的 TD 学习可在偏置和随机梯度变化之间实现有利的权衡，对于一些 p（0<p<=1），都以期望和高的概率下 finie moment（1+p）的重尾收益实现样本复杂度，同时 Robust TD 学习具有相同的特征。

    Jun, 2023

  • 方差缩减时序差分学习的重新分析

    本文介绍了 variance reduced TD（VRTD）算法及其在非渐进情况下演化的方向收敛性和方差减少性，证明了 VRTD 具有线性收敛速度，在 Markov 采样的条件下能够显著降低方差误差和偏差误差。

    Jan, 2020