半无限约束马尔可夫决策过程与高效强化学习
本文提出一个深度强化学习的框架来解决受限的组合优化问题,将受约束的组合问题定义为完全可观的受约束马尔可夫决策过程(CMDP),并提出从不满足的约束产生惩罚信号,以推断作为启发式算法的策略。通过对约束工厂和资源分配问题进行的实验表明,本文的提议对于比较经典的启发式算法、元启发式算法和约束编程(CP)求解器来说,能更快地求得答案。
Jun, 2020
本文介绍了一种基于加权线性回归方案的计算有效算法,用于处理线性马尔可夫决策过程的强化学习问题。该算法实现了近似最小化最优遗憾,具有较好的效率,对参数化转换动态有良好的适应性,可以对研究领域进行更细致的探讨。
Dec, 2022
本文提出了一种基于Lagrangian方法的新型模型双重算法OptAug-CMDP,针对标签化的有限路径CMDP,证明了该算法在探索CMDP的K个周期内同时获得了目标和约束违规的期望性能敏感性,且无需进行错误取消。
Jun, 2023
我们引入并研究了具有任意时间限制的受限马尔可夫决策过程(cMDPs)。我们提出了一种固定参数可处理的方法,将具有任意时间限制的cMDPs转化为无约束的MDPs。我们设计出了适用于大表cMDPs的计划和学习算法,并设计了近似算法,可以高效地计算或学习一个近似可行策略。
Nov, 2023
在无限时间、约束的马尔科夫决策过程中,通过零阶内点方法实现约束满足,以最大化预期累积奖励,确保策略在学习过程中的可行性,并具有样本复杂度O(ε^(-6))
Dec, 2023
我们介绍了一种具有均匀概率近似正确性保证的新型策略梯度原始-对偶算法,同时保证了收敛至最优策略、次线性遗憾和多项式样本复杂度的理论保证,并在一个简单的CMDP示例中进行实证展示,证明了算法收敛至最优策略,而现有算法则表现出振荡性能和约束违规。
Jan, 2024
本文研究了无限时段平均回报约束马尔可夫决策过程(CMDP)。在我们的知识范围内,该工作是第一个深入探讨了具有一般策略参数化的平均回报CMDP的遗憾和约束违反分析。为了解决这个挑战,我们提出了一种基于原始对偶的策略梯度算法,能够在确保低遗憾全局最优策略的同时,灵活处理约束。特别地,我们证明了我们提出的算法实现了$\tilde{\mathcal{O}}({T}^{3/4})$的目标遗憾和$\tilde{\mathcal{O}}({T}^{3/4})$的约束违反界限。
Feb, 2024
我们研究了强化学习问题中的约束马尔可夫决策过程(CMDP),并通过优化算法对CMDP问题的样本复杂度提出了改进,实现了优化的问题相关保证。
Feb, 2024
这篇研究论文提出了一个新的基于受约束的马尔可夫决策过程(CMDP)框架的强化学习算法,通过离线数据评估和策略梯度更新来在线学习,实现了CMDP在线性设置中的多项式样本复杂度。
Jun, 2024
本研究解决了在大规模或无限状态和动作空间中设计高效样本和计算合理的强化学习算法的难题。我们提出了一种新算法,能够在给定特征映射下高效寻找近似最优策略,并在问题参数上呈多项式级别使用样本和成本敏感分类oracle。这一算法显著提升了现有方法的效能,尤其在处理无限状态和动作环境时,具有重要应用潜力。
Sep, 2024