通过协调提升和动态规划解决多模型马尔可夫决策过程
本文提出了两种近似解决因子化马尔可夫决策过程的算法,利用基函数表示近似值函数,其中每个基函数仅涉及一个小的子集,使用类似于变量消除的线性规划分解技术将指数级的LP规模缩小到多项式级别。我们的动态规划算法使用max-norm 近似技术,对于超过10^40个状态的问题,我们的算法展示了有希望的可扩展性,并将其与现有的最新技术方法进行了比较,在某些问题上计算时间得到了指数级的提升。
Jun, 2011
本文研究了面临参数不确定性的大规模马尔可夫决策过程(MDP),并基于鲁棒MDP范式,应用增强学习方法解决了规模巨大且无法使用动态规划技术的实际问题解决方法。该方法在特定技术条件下被证明可以成功,通过对期权定价问题的模拟的证明其有效性,是首次尝试扩大鲁棒MDPs范式的尝试。
Jun, 2013
本文考虑了控制具有大状态空间的马尔可夫决策过程以最小化平均成本的问题,并使用线性规划和两种方法,即基于随机凸优化和基于约束采样的方法,将性能提高到与在低维策略类中的任何策略相比的最佳水平。
Feb, 2014
本文提出了一种针对状态空间较大的MDP问题进行优化的方法,该方法基于一小组策略的占用度量的低维度逼近,并提出了一个有效的算法,可用于在该类策略中找到低过度损失相对于最佳策略的策略。作者限定了平均成本和折扣成本情况下的过量损失,并在队列应用中展示了该方法的有效性。
Jan, 2019
本论文介绍了一种基于动态规划的在线算法Real Time Dynamic Programming (RTDP),提出了一种多步贪心RTDP算法$h-RTDP$,比之前的算法在算法复杂度和样本复杂性方面有了明显改进。同时分析了在三种近似设置下的性能,并证明了在近似DP算法中与$h$-RTDP的渐进性能相同
Sep, 2019
本文探讨了在考虑转移概率不确定性时,如何高效地解决具有s-和sa-矩形模糊集定义的鲁棒MDP问题,并提出了一种新的策略迭代方案和快速计算鲁棒Bellman算子的方法。实验结果表明,这些方法比使用线性规划求解器结合鲁棒值迭代的现有方法快得多。
Jun, 2020
这篇论文介绍了一种结合动态规划和策略梯度的方法,称为动态策略梯度,其中参数是向后训练的。通过对表格softmax参数进行收敛性分析,我们发现动态策略梯度训练更好地利用了有限时间问题的结构,这反映在改进的收敛界限上。
Oct, 2023
通过将隐含于现有优化算法中的类比隐含为显性,借助统一的解决方案特征化,本文实现了对四个问题类的分析。选择已在现有文献中指出的等效优化和控制算法,并利用特定于MDP的两个线性结构约束对优化中的Hessian进行线性约束,通过加入两个新方向和自适应步长,将标准的值迭代算法改进为一种新的一阶控制算法,被称为准策略迭代,并且与折扣因子关系的敏感性很低。
Nov, 2023
本文研究了无限时段平均回报约束马尔可夫决策过程(CMDP)。在我们的知识范围内,该工作是第一个深入探讨了具有一般策略参数化的平均回报CMDP的遗憾和约束违反分析。为了解决这个挑战,我们提出了一种基于原始对偶的策略梯度算法,能够在确保低遗憾全局最优策略的同时,灵活处理约束。特别地,我们证明了我们提出的算法实现了$\tilde{\mathcal{O}}({T}^{3/4})$的目标遗憾和$\tilde{\mathcal{O}}({T}^{3/4})$的约束违反界限。
Feb, 2024