Oct, 2023

自然策略梯度算法对无限时间折扣回报马尔可夫决策过程的参数化泛化的样本复杂度改进

HTML
PDF
TL;DR设计高效学习算法解决无限时间折扣奖励马尔可夫决策过程问题，提出了应用加速随机梯度下降过程获取自然策略梯度的加速自然策略梯度算法（ANPG）。ANPG在一般参数化情况下，实现了O(ε^-2)的样本复杂度和O(ε^-1)的迭代复杂度，其中ε定义了最优性误差。相比现有技术，ANPG通过一个log(1/ε)因子改进了样本复杂度。ANPG是一个一阶算法，并且不需要假设重要性采样权重的方差有上界，这与一些现有文献不同。在无Hessian和无重要性采样算法类别中，ANPG的样本复杂度超过了已知算法的O(ε^-1/2)倍，并与他们的迭代复杂度相匹配。
发现论文，激发创造
  • 自然策略梯度算法的线性收敛性

    本文研究了应用于马尔可夫决策过程中的自然策略梯度算法，在此基础上提出具有自适应步长的改进方法，并通过实验比较不同变种的策略梯度方法。

    May, 2021

  • 普通策略梯度的一般样本复杂性分析

    本文使用最近为非凸优化分析SGD开发的工具，获得了vanilla policy gradient（PG）的收敛性和样本复杂性保证。

    Jul, 2021

  • 自然策略梯度原始-对偶方法在约束MDPs上的收敛性和样本复杂度

    研究如何在满足预期总效用的约束条件下最大化预期总回报，提出了一种新的自然策略梯度原始-对偶方法来解决Constrained Markov决策过程（constrained MDPs）的折扣无限时域下的最优控制问题，在自然策略梯度上升和投影次梯度下降的影响下更新原始变量和对偶变量。

    Jun, 2022

  • 自然策略梯度法在对数-线性策略下的线性收敛

    本研究考虑了无限期折扣马尔可夫决策过程，并研究了自然策略梯度和Q-NPG方法在对数线性策略类下的收敛速度及样本复杂性，其在非自适应几何递增步长下可以实现线性收敛率和样本复杂度的约为O(1/epsilon^2)。

    Oct, 2022

  • 无限时标平均奖励马尔可夫决策过程中策略梯度算法的遗憾分析

    本文研究了无限时间段平均回报马尔可夫决策过程（MDP）。与现有研究不同的是，我们采用了基于通用策略梯度的算法，使其摆脱了线性MDP结构的约束。我们提出了一种基于策略梯度的算法，并证明了其全局收敛性质。然后我们证明该算法具有$\tilde{\mathcal{O}}({T}^{3/4})$的后悔度。值得注意的是，本文是第一次对于一般参数化策略梯度算法在平均回报情景下的后悔计算进行了探索性研究。

    Sep, 2023

  • 自然策略梯度在无限状态平均奖励马尔可夫决策过程上的收敛性

    该研究证明了自然策略梯度算法在无限状态的平均奖励马尔可夫决策过程中的收敛速度，如果采用良好的初始策略进行初始化，则收敛速度为O(1/√T)。此外，针对大类排队马尔可夫决策过程，最大权重策略足以满足我们的初始策略要求并实现O(1/√T)的收敛速度。关键是根据NPG算法的迭代策略所达到的相对值函数，我们得出了这一结果。

    Feb, 2024

  • 可证明的基于策略梯度法的平均奖励马尔可夫潜力博弈方法

    研究马尔可夫潜势博弈在无限时间平均回报准则下，证明基于独立策略梯度和独立自然策略梯度的算法都能在全局收敛到纳什均衡点，同时提出了渐进性和底座条件，通过梯度和微分值函数的灵敏度边界为梯度方法奠定了基础，并证明了三种算法的收敛性以及具体的时间复杂度，当需要估计策略梯度时，我们提出了一个算法并给出了样本复杂度分析，最后通过模拟研究来验证结果。

    Mar, 2024

  • 无限时间平均回报马尔可夫决策过程的方差减少政策梯度方法

    基于政策梯度的两种方法在无限时间平均奖励马尔可夫决策过程中引入了一般参数化。第一种方法采用隐式梯度传输进行方差降低，确保了预期后悔度为$\tilde{\mathcal{O}}(T^{3/5})$数量级。第二种方法以Hessian-based技术为基础，确保了预期后悔度为$\tilde{\mathcal{O}}(\sqrt{T})$数量级。这些结果显著提高了该问题的最新研究成果，其后悔度达到了$\tilde{\mathcal{O}}(T^{3/4})$数量级。

    Apr, 2024

  • 高效约束强化学习与普适参数化

    在受限制的马尔可夫决策问题（CMDP）中，我们开发了原始-对偶加速自然策略梯度（PD-ANPG）算法，它保证了ε全局最优性差距和ε约束违反，样本复杂度为O(ε^-3)，从而在CMDP的样本复杂度上取得了O(ε^-1)的进展。

    May, 2024

  • 受限马尔可夫决策过程中的一般参数化策略的最后迭代收敛性

    本研究旨在解决学习受限马尔可夫决策过程（CMDP）中的一般参数化问题，并提出了一种基于原始-对偶的正则化加速自然策略梯度（PDR-ANPG）算法。该算法在样本复杂度方面显著提升了当前CMDP的一般参数化策略的最后迭代保障，展示了具有潜在影响的高效收敛性。

    Aug, 2024