Jan, 2019

通过线性规划对偶解决大规模马尔可夫决策问题

HTML
PDF
TL;DR本文提出了一种针对状态空间较大的MDP问题进行优化的方法，该方法基于一小组策略的占用度量的低维度逼近，并提出了一个有效的算法，可用于在该类策略中找到低过度损失相对于最佳策略的策略。作者限定了平均成本和折扣成本情况下的过量损失，并在队列应用中展示了该方法的有效性。
发现论文，激发创造
  • 动态策略编程

    本文提出了一种新的策略迭代方法——动态策略规划（DPP），用于在无限时间马尔可夫决策过程（MDP）中估计最优策略，证明了DPP在估计和近似误差存在的情况下的有限迭代和渐进l∞-norm性能损失边界，通过数值实验表明，与现有的强化学习方法相比，在所有情况下，基于DPP的算法表现出更好的性能。

    Apr, 2010

  • 基于因子的MDP高效解算算法

    本文提出了两种近似解决因子化马尔可夫决策过程的算法，利用基函数表示近似值函数，其中每个基函数仅涉及一个小的子集，使用类似于变量消除的线性规划分解技术将指数级的LP规模缩小到多项式级别。我们的动态规划算法使用max-norm 近似技术，对于超过10^40个状态的问题，我们的算法展示了有希望的可扩展性，并将其与现有的最新技术方法进行了比较，在某些问题上计算时间得到了指数级的提升。

    Jun, 2011

  • 搜索有限策略空间求解POMDPs

    本文研究部分可观察马尔可夫决策过程（POMDPs）的解决方案，探讨如何从有限状态自动机的限制集合中找到最佳策略，进而展示了通过分支定界法和梯度上升法寻找全局最优确定性策略和局部最优随机策略的优越实验结果。

    Jan, 2013

  • 弱耦合的马尔科夫决策问题的灵活分解算法

    本文提出了两种新的方法来分解和解决大型马尔可夫决策问题（MDPs），分别为部分解耦方法和完全解耦方法。这些方法可以用于发现最优策略或近似最优策略，并提供了一种有效的知识传递框架。

    Jan, 2013

  • 用于计算马尔可夫决策过程近似最优解的模型简化技术

    介绍了一种新方法，用于解决具有非常大状态空间的隐式（分解式）马尔可夫决策流程（MDPs）。该方法通过 epsilon-homogeneous 分区算法将大型 MDP 转化为较小的BMDP 以分析大型隐式MDPs。

    Feb, 2013

  • 大规模马尔可夫决策问题的线性规划

    本文考虑了控制具有大状态空间的马尔可夫决策过程以最小化平均成本的问题，并使用线性规划和两种方法，即基于随机凸优化和基于约束采样的方法，将性能提高到与在低维策略类中的任何策略相比的最佳水平。

    Feb, 2014

  • 解决大规模马尔可夫决策过程的更快鞍点优化

    本文研究在平均回报马尔科夫决策过程中计算最优策略的问题，使用鞍点优化方法直接构建一个可行的线性规划问题，但变量数目与状态数成线性关系，因此提出了线性松弛版本。论文从特征化的角度提出了一些潜在问题，设计了一个算法，可以获得快速的收敛率，不受状态空间大小的影响。

    Sep, 2019

  • 线性马尔可夫决策过程低切换成本可证效率算法

    本文着重于线性马尔可夫决策过程（MDP）问题中的低转换成本，并提出了第一个具有低转换成本的线性MDP算法，同时通过低转换成本较小而达到了大体积的泛化。

    Jan, 2021

  • 通过冻结慢状态实现更快的近似动态规划

    论文提出了一种基于动态规划算法框架的近似方法，针对具有快慢结构的无穷状态空间的马尔可夫决策过程，其中“冻结”慢状态，通过解决一组简单的有限时段MDP以及在一个慢时间尺度（上层MDP）上进行价值迭代的辅助MDP等步骤，生成有效策略，以更少的计算代价实现了决策建模中遗漏慢状态的可行性。

    Jan, 2023

  • 计数无限状态空间马尔可夫决策过程的贝叶斯学习最优策略

    该研究提出了一种基于贝叶斯思想和汤普森抽样的算法来解决优化数量可数的马尔可夫决策过程的控制问题，在未知参数和固定先验分布的情况下，能够稳定地获得近似最优解，适用于诸如通信网络和计算系统等不确定动力系统以及一些数量可数的排队模型。

    Jun, 2023