一阶 MDP 的近似线性规划
本文考虑了控制具有大状态空间的马尔可夫决策过程以最小化平均成本的问题,并使用线性规划和两种方法,即基于随机凸优化和基于约束采样的方法,将性能提高到与在低维策略类中的任何策略相比的最佳水平。
Feb, 2014
本文提出了一种针对状态空间较大的 MDP 问题进行优化的方法,该方法基于一小组策略的占用度量的低维度逼近,并提出了一个有效的算法,可用于在该类策略中找到低过度损失相对于最佳策略的策略。作者限定了平均成本和折扣成本情况下的过量损失,并在队列应用中展示了该方法的有效性。
Jan, 2019
本文提出了两种近似解决因子化马尔可夫决策过程的算法,利用基函数表示近似值函数,其中每个基函数仅涉及一个小的子集,使用类似于变量消除的线性规划分解技术将指数级的 LP 规模缩小到多项式级别。我们的动态规划算法使用 max-norm 近似技术,对于超过 10^40 个状态的问题,我们的算法展示了有希望的可扩展性,并将其与现有的最新技术方法进行了比较,在某些问题上计算时间得到了指数级的提升。
Jun, 2011
使用 LP 模型结合基于网格的近似方法生成近似策略,研究了解决限制观测 Markov 决策过程的效果。结果表明,LP 模型可有效地生成有限和无限时间段问题的近似策略,同时提供将各种附加约束集成到模型中的灵活性。
Jun, 2022
本文介绍了一种可对连续和离散变量的大决策问题进行紧凑表示的混合分解 Markov 决策过程(MDP)模型和一种新的混合近似线性规划(HALP)框架,HALP 的核心思想是通过一组基函数的线性组合来近似最优价值函数,并通过线性规划来优化其权重, 并证明其在多种混合优化问题中的可扩展潜力。
Sep, 2011
我们提出了适用于合作多智能体有限和无限时域折扣马尔可夫决策过程的逼近策略迭代算法,其中使用近似线性规划计算近似值函数并实施分散策略改进。
Nov, 2023
通过使用第一阶表示中的紧凑策略来选择大型马尔可夫决策过程的策略,我们通过训练数据来诱导第一阶策略,使用具有分类概念语言的决策列表的合集来表示我们的策略,我们发现此方法在概率领域中具有优越的效果,并讨论了此方法在关系加固学习问题上的应用。
Dec, 2012
线性马尔科夫决策过程(MDP)中的特征选择和零稀疏线性 MDP,以及通过凸规划有效计算的模拟器、低深度决策树上的区块 MDP 的学习算法。
Sep, 2023
提出一种新的随机线性规划算法,利用价值 - 策略对偶和二叉树数据结构,自适应地采样状态 - 动作 - 状态转移,并进行指数原始 - 对偶更新,从而以几乎线性的运行时间在最坏情况下找到一个 ε- 最优策略。当马尔可夫决策过程是遍历的并且以某些特殊的数据格式指定时,该算法使用线性的运行时间,在状态 - 动作对的总数中是次线性的,为解决随机动态规划问题提供了新的途径和复杂性基准。
Apr, 2017