KDDJun, 2022

马尔可夫决策过程的几何策略迭代

PDF
TL;DR探究了有限状态 - 动作折扣马尔可夫决策过程的价值函数多面体结构，并使用超平面排列表征了多面体的边界。提出了一种新的算法 Geometric Policy Iteration (GPI) 来解决折扣 MDPs，它使用单个状态的策略更新，以更快的价值改进不影响计算效率，同时允许状态值的异步更新。证明了 GPI 的复杂度达到了策略迭代的最佳已知界限，并展示了 GPI 在各种大小的 MDPs 上的优越性。
markov decision processesvalue function polytopegeometric policy iterationasynchronous updatescomputational efficiency
发现论文，激发创造
  • 使用几何策略组合的广义策略改进

    本文介绍了一种基于几何地平线模型来提高政策表现的方法，该方法可以有效的评估非马尔科夫策略并通过广义策略提升来优化出新的马尔可夫策略，此方法证明了在深度强化学习中取得了不错的效果。同时，文章提供了对 GHM 训练方法的分析和收敛性研究。

    Jun, 2022

  • 强化学习中的价值函数多面体

    该研究论文探讨了有限状态动作 Markov 决策过程中价值函数空间的几何和拓扑性质，发现其形状为一个多面体，并介绍了与策略和价值函数之间的结构关系以及利用可视化方法来增强加强学习算法动态学习的理解。

    Jan, 2019

  • 合作多智能体马尔可夫决策过程中的近似线性规划和分散策略改进

    我们提出了适用于合作多智能体有限和无限时域折扣马尔可夫决策过程的逼近策略迭代算法，其中使用近似线性规划计算近似值函数并实施分散策略改进。

    Nov, 2023

  • 线性可行最优状态价值函数下的 MDP 查询效率规划

    本文考虑了使用生成模型进行有限轮次的 MDP 本地规划，并提出了一种名为 TensorPlan 算法的方法，在最优价值函数符合线性可实现性的情况下，能够以 poly ((dH/δ) 的复杂度找到相对于任何线性可实现性且存在界限参数的确定性策略的 δ 最优策略；此外，本文还将上限拓展到了近可实现性情况和无限时域折扣设置。

    Feb, 2021

  • 无记忆随机策略优化在无限时域 POMDP 中的几何

    本研究考虑了有限状态和动作空间的无穷时部分观察到的马尔可夫决策问题中，根据折扣或平均收益准则找到最佳的无记忆随机策略并描述了优化问题作为可行状态 - 动作频率空间中的线性优化问题并使用了多项式优化的最大化奖励来解决导航问题。

    Oct, 2021

  • 近似改进策略迭代

    本文旨在探讨 Modified Policy Iteration（MPI）算法的近似形式，提出了三种扩展的适应于大规模状态和动作空间的 DP 算法，包括拟合值迭代、拟合 Q 迭代和基于分类的策略迭代，并提供了统一的误差传播分析方法。同时，对于基于分类的实现，发展了有限样本分析，以显示 MPI 的主要参数如何控制分类器的估计误差和整体价值函数的近似程度。

    May, 2012

  • 策略迭代最坏情况复杂度的改进界

    本文主要探讨关于马尔可夫决策过程解决方案的复杂度问题，研究表明，虽然使用线性规划技术解决方案可以在多项式时间内完成，但使用迭代方法，如策略迭代算法，通常在实践中更高效。同时，本文提出了关于策略迭代算法收敛步数的改进，得出了一个更合理的上限。

    Oct, 2014

  • 策略迭代复杂度的改进和推广的上界

    本文研究了两种策略迭代算法在马尔可夫决策过程中收敛所需的迭代次数，并通过结构性质得到了与折扣因子无关的上界，在假设状态空间分为瞬态和常态状态的情况下，Howard's PI 和 Simplex-PI 都可以在强多项式时间内终止。

    Jun, 2013

  • 降低方差的价值迭代算法及用于求解马尔可夫决策流程的更快速算法

    提出了一种采用采样技术的快速算法来解决折扣马尔可夫决策过程的近似求解，并证明了算法的收敛性和复杂度。同时，结合经典的价值迭代与方差约减技术，改进了该算法的性能，使其具有线性收敛性和渐进最优性。

    Oct, 2017

  • 带政策语言偏差的近似策略迭代：解决关系马尔可夫决策过程

    研究大规模关系型马尔科夫决策过程（MDP）的政策选择方法，考虑一种近似政策迭代（API） 的变体，用学习步骤在政策空间中替换通常的值函数学习步骤，介绍一个关系型政策语言和相应的学习器，以及基于随机游走的面向目标的规划域的自举例行程序，实验结果表明，该系统能够解决一系列的规划域和其随机变体，但提出了一些局限性建议未来工作。

    Sep, 2011