Jun, 2011

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

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

    该论文提出了一种新的价值确定方法，借助简单的闭合计算来直接计算价值函数的分解逼近，以及一个基于此方法的策略迭代过程。

    Jan, 2013

  • 使用混合状态和动作变量解决分解的马尔可夫决策过程

    本文介绍了一种可对连续和离散变量的大决策问题进行紧凑表示的混合分解 Markov 决策过程（MDP）模型和一种新的混合近似线性规划（HALP）框架，HALP 的核心思想是通过一组基函数的线性组合来近似最优价值函数，并通过线性规划来优化其权重， 并证明其在多种混合优化问题中的可扩展潜力。

    Sep, 2011

  • 用连续和离散变量解决因式化马尔可夫决策过程

    我们提出了一个框架来处理离散和连续变量的混合模型的随机规划问题，使用混合马尔可夫决策过程的方法，通过线性规划近似来解决这些问题，并遵循混合动态贝叶斯网络的表示形式，已在一系列控制问题中进行了实验。

    Jul, 2012

  • 利用匿名性进行近似线性规划：扩展到大型多智能体 MDPs（扩展版）

    本研究提出了一种利用匿名影响的方法以提高多方系统的计算效率，尤其是在面对因交互密度增加而出现指数级价值部件大小增加的情况下，可以使之前无法求解的分解 MDP 的近似线性规划问题得到解决。

    Nov, 2015

  • 一阶 MDP 的近似线性规划

    本文提出了一种基于线性规划的解决方法，通过将价值函数在一组一阶基函数的线性表示中计算适当的权值，解决了一阶马尔科夫决策过程中与特定领域实例无关的解决方案。并将该解决方法应用于电梯调度方面，具有丰富的特征空间和多标准加性奖励，证明了其优于许多直观、启发式指导政策。

    Jul, 2012

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

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

    Feb, 2013

  • 面向因式化马尔可夫决策过程的极小极大最优强化学习

    本文研究了在 FMDP 中使用最小最大算法的强化学习，提出了两种基于模型的算法，并通过结构相关的阈值证明了其保证。

    Jun, 2020

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

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

    Jan, 2019

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

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

    Jan, 2023

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

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

    Feb, 2014