本文提出了两种近似解决因子化马尔可夫决策过程的算法,利用基函数表示近似值函数,其中每个基函数仅涉及一个小的子集,使用类似于变量消除的线性规划分解技术将指数级的 LP 规模缩小到多项式级别。我们的动态规划算法使用 max-norm 近似技术,对于超过 10^40 个状态的问题,我们的算法展示了有希望的可扩展性,并将其与现有的最新技术方法进行了比较,在某些问题上计算时间得到了指数级的提升。
Jun, 2011
探讨了具有部分状态信息的分布式智能体的规划问题,介绍了对 MDP 和 POMDP 模型的推广,研究表明分散控制与集中控制在马尔可夫过程中的根本差异,相关问题不适合使用多项式时间算法来求解,需要使用双指数时间算法求解。
Jan, 2013
我们提出了适用于合作多智能体有限和无限时域折扣马尔可夫决策过程的逼近策略迭代算法,其中使用近似线性规划计算近似值函数并实施分散策略改进。
Nov, 2023
本文展示了如何在保持优化性的同时,通过分层信息共享来解开多个玩家的决策变量,应用最优性原理将一个单个阶段的子游戏进一步分解为更小的子游戏,从而使我们能够一次进行单个玩家的决策。我们的研究结果表明,利用这些发现的算法可以扩展到更大的多人游戏而不损害优化性。
Feb, 2024
该论文提出了一种新的价值确定方法,借助简单的闭合计算来直接计算价值函数的分解逼近,以及一个基于此方法的策略迭代过程。
该研究介绍了一种针对具有突发流量的有限队列的负载均衡和自动缩放的新模型和算法,通过线性规划解决了弱耦合的马尔可夫决策过程问题,进一步将其放松为可操作的松弛线性规划,并基于线性规划的拉格朗日函数提出了一个两时间尺度算法来解决在线参数学习和策略优化的问题。
Jun, 2024
通过引入 TranSDDP,一种基于 Transformer 的分阶段分解算法,我们有效地为大规模多阶段随机规划问题生成了分段线性逼近,显著减少了计算时间同时保持解决方案的质量,从而标志着在处理大规模多阶段随机规划问题方面的一个有希望的进展。
Apr, 2024
本文总结了解决 Markov 决策问题及其算法运行时间的复杂性,并讨论了需要进一步研究实际算法来快速解决大问题的问题。同时,本文提出了一些基于 MDP 结构的替代分析方法,以鼓励未来的研究。
Feb, 2013
本文提出了一种针对状态空间较大的 MDP 问题进行优化的方法,该方法基于一小组策略的占用度量的低维度逼近,并提出了一个有效的算法,可用于在该类策略中找到低过度损失相对于最佳策略的策略。作者限定了平均成本和折扣成本情况下的过量损失,并在队列应用中展示了该方法的有效性。
Jan, 2019
本文探讨了在考虑转移概率不确定性时,如何高效地解决具有 s - 和 sa - 矩形模糊集定义的鲁棒 MDP 问题,并提出了一种新的策略迭代方案和快速计算鲁棒 Bellman 算子的方法。实验结果表明,这些方法比使用线性规划求解器结合鲁棒值迭代的现有方法快得多。
Jun, 2020