Sep, 2023

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

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

    该研究报告首次提出了有限时间全局收敛分析方法，针对无限时间平均奖励马尔可夫决策过程中的策略梯度方法。具体而言，我们关注的是具有有限状态和动作空间的遍历型表格型马尔可夫决策过程。我们的分析表明，策略梯度迭代以 O (log (T)) 的子线性速率收敛到最优策略，并获得了 O (log (T)) 的后悔度保证，其中 T 表示迭代次数。我们的研究工作主要贡献在于证明了策略梯度算法对于平均奖励马尔可夫决策过程的收敛性，以及得到了有限时间的性能保证。与现有的折扣奖励性能界限不同，我们的性能界限明确依赖于捕捉底层马尔可夫决策过程复杂性的常数。在此基础上，我们重新审视和改进了折扣奖励马尔可夫决策过程的性能界限，并通过模拟评估了平均奖励策略梯度算法的性能。

    Mar, 2024

  • 通过原始 - 对偶策略梯度算法学习无限时域平均奖励受限马尔可夫决策过程的通用参数化策略

    本文研究了无限时段平均回报约束马尔可夫决策过程（CMDP）。在我们的知识范围内，该工作是第一个深入探讨了具有一般策略参数化的平均回报 CMDP 的遗憾和约束违反分析。为了解决这个挑战，我们提出了一种基于原始对偶的策略梯度算法，能够在确保低遗憾全局最优策略的同时，灵活处理约束。特别地，我们证明了我们提出的算法实现了 $\tilde {\mathcal {O}}({T}^{3/4})$ 的目标遗憾和 $\tilde {\mathcal {O}}({T}^{3/4})$ 的约束违反界限。

    Feb, 2024

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

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

    Apr, 2024

  • 可证明高效的无限时间平均回报线性 MDP 的强化学习

    设计了一个计算有效的算法，通过将平均奖励设定近似为折扣设定，并且在适当调整贴现因子时，通过运行基于乐观值迭代的算法来实现无限时段平均奖励线性马尔可夫决策过程 (MDP) 的 O (sqrt (T)) 的遗憾。

    May, 2024

  • 无模型强化学习中的无限时域平均奖赏马尔可夫决策过程

    本文提出两种基于无模型的强化学习算法，用于学习无限时间持续的平均回报 MDP 问题，第一种算法在弱相互通信的 MDPs 中，将问题简化为折扣回报问题，在 T 步之后的遗憾为 O (T^(2/3)), 该算法是解决该问题的第一种无模型的算法；第二种算法利用了对抗多臂老虎机自适应算法的最新进展，将遗憾进一步改进至 O (sqrt (T))，但需要更强的符合人类定义的遍历条件。这个结果取代了 Abbasi-Yadkori 等人 2019 年只有在符合人类定义的遍历条件下的 ergodic MDP 才能达到 O (T^(3/4)) 的遗憾。

    Oct, 2019

  • 使用线性函数逼近学习无限时间平均回报马尔可夫决策过程

    开发多种学习用于 Markov Decision Processes 的无限时间平均奖励设置和线性函数逼近的算法，使用乐观原则和假设 MDP 具有线性结构，提出具有优化的计算效率的算法，并展开了详细的分析，改进了现有最佳结果。

    Jul, 2020

  • 具有约束条件的无限时间平均奖励马尔可夫决策过程学习

    本研究提出了一种政策优化算法，用于处理成本约束下的无限时间跨度平均奖励马尔可夫决策过程中的后悔最小化问题，该算法在符合一定条件的 MDP 下具有较低的后悔度和约束违反率，并将其推广到弱通信 MDP 领域，为该领域提供了复杂度可行的算法。

    Jan, 2022

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

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

    Mar, 2024

  • 无限时间视角的策略梯度估计

    本文提出了一种名为 GPOMDP 的基于模拟的算法，用于在部分可观测马尔可夫决策过程（POMDPs）中控制参数化随机策略，生成偏差估计的平均奖励梯度。

    Jun, 2011

  • 无限视角平均报酬强化学习的量子加速

    该研究探讨了量子加速在解决无限视界马尔可夫决策过程（MDP）以增强平均奖励结果方面的潜力。我们引入了一种创新的量子框架，用于代理与未知 MDP 的交互，扩展传统的交互范式。我们的方法包括设计一种基于乐观主义的表格型强化学习算法，通过高效的量子均值估计技术利用代理通过量子信号获取的数据。通过彻底的理论分析，我们证明了量子均值估计的量子优势能够在无限视界强化学习中实现指数级的遗憾保证。具体而言，所提出的量子算法实现了一个 $\tilde {\mathcal {O}}(1)$ 的遗憾上界，这是相对于经典对应方法展现的 $\tilde {\mathcal {O}}(\sqrt {T})$ 界限的显著改进。

    Oct, 2023