关于连接型 MDP 中价值迭代的收敛性
该研究报告首次提出了有限时间全局收敛分析方法,针对无限时间平均奖励马尔可夫决策过程中的策略梯度方法。具体而言,我们关注的是具有有限状态和动作空间的遍历型表格型马尔可夫决策过程。我们的分析表明,策略梯度迭代以 O (log (T)) 的子线性速率收敛到最优策略,并获得了 O (log (T)) 的后悔度保证,其中 T 表示迭代次数。我们的研究工作主要贡献在于证明了策略梯度算法对于平均奖励马尔可夫决策过程的收敛性,以及得到了有限时间的性能保证。与现有的折扣奖励性能界限不同,我们的性能界限明确依赖于捕捉底层马尔可夫决策过程复杂性的常数。在此基础上,我们重新审视和改进了折扣奖励马尔可夫决策过程的性能界限,并通过模拟评估了平均奖励策略梯度算法的性能。
Mar, 2024
提出了一种采用采样技术的快速算法来解决折扣马尔可夫决策过程的近似求解,并证明了算法的收敛性和复杂度。同时,结合经典的价值迭代与方差约减技术,改进了该算法的性能,使其具有线性收敛性和渐进最优性。
Oct, 2017
本文重新审视了策略梯度法在有限状态和动作 MDPs 中的有限时间分析,并基于与策略迭代的关系展示出许多策略梯度法变体使用大步长成功并达到线性收敛率。
Jul, 2020
本篇论文研究鲁棒平均回报 MDP 问题,旨在找到一种策略,使其在不确定性的 MDP 集合中的最坏平均回报最优化。作者探讨了利用折扣 MDP 实现这个问题,证明了当折扣因子趋近于 1 时,鲁棒折扣价值函数收敛于鲁棒平均回报,并设计了鲁棒动态规划方法。同时,也考虑了直接处理鲁棒平均回报 MDP 问题的情况,并导出了其鲁棒 Bellman 方程,设计了一种鲁棒相对价值迭代算法来求解其策略。
Jan, 2023
本文介绍了利用 Lagrangian 方法将约束马尔可夫决策过程转化为有约束鞍点问题的优化方法,提出了两种单时间尺度的基于原始对偶算法的策略算法,可以使策略迭代收敛到一个最优受限策略。其中一个采用了一种正则化策略梯度算法,另一个采用了一种乐观的策略梯度算法。这是约束 MDPs 单时间尺度算法中第一个非渐进策略最终迭代收敛结果。
Jun, 2023
本研究提出了一种基于平均报酬 MDPs 的学习和规划算法,其中包括第一种无参考状态的普遍证明收敛的无模型控制算法、第一个证明收敛的无政策自由预测算法,以及第一个离线学习算法,其收敛于实际值函数而不是值函数增加一个偏移量。在使用时间差错错误而不是常规错误更新平均报酬估计时,我们的所有算法都基于此。
Jun, 2020
探究了有限状态 - 动作折扣马尔可夫决策过程的价值函数多面体结构,并使用超平面排列表征了多面体的边界。提出了一种新的算法 Geometric Policy Iteration (GPI) 来解决折扣 MDPs,它使用单个状态的策略更新,以更快的价值改进不影响计算效率,同时允许状态值的异步更新。证明了 GPI 的复杂度达到了策略迭代的最佳已知界限,并展示了 GPI 在各种大小的 MDPs 上的优越性。
Jun, 2022
用假均值将混合风险下的 MDP 转化为标准 MDP,并提出一种基于二级优化结构的统一算法框架,该框架还允许收敛性分析。通过数值实验,验证了该算法的有效性。
Jan, 2022
本文研究了策略梯度在无限时间,连续状态和动作空间,及熵正则化的马尔可夫决策过程中的全局收敛性,并证明了在符合足够正则化的情况下,梯度流指数级收敛到唯一的稳态解。
Jan, 2022
本文针对指数成本的风险敏感 MDP 问题,首次提供了 MPI 在有限状态和动作空间中收敛的证明,其收敛证明与已有的折扣和风险中性平均费用问题不同,也提供了风险敏感 MDP 的近似 MPI 证明。
Feb, 2023