受限马尔可夫决策过程中的一般参数化策略的最后迭代收敛性
内容提要
本文探讨了策略优化算法在马尔可夫决策过程中的收敛性，提出了新的非渐进收敛保证方法。研究表明，算法在逼近最优价值函数时可实现线性或二次收敛，熵正则化有助于加速收敛。此外，开发了基于原始-对偶的算法，以解决约束问题，提高样本复杂度的效率。
延伸解读
从理论到算法：收敛保证的演进
文章梳理了策略优化算法在马尔可夫决策过程中收敛性研究的进展。早期工作针对折扣MDP，证明了比例调节策略梯度算法在softmax参数化下具有线性甚至二次收敛速度，并指出熵正则化能加速收敛。随后研究扩展到无限时间、连续状态动作空间及熵正则化MDP，证明了梯度流指数级收敛到唯一稳态解。这些理论结果为后续约束MDP的算法设计奠定了基础。
约束MDP的原始-对偶算法突破
针对凸约束马尔可夫决策过程，文章介绍了基于策略的原始-对偶算法，通过利用问题中的凸性证明了全局收敛性，并给出了O(T^{-1/3})的收敛速度。后续工作提出了C-NPG-PD算法，旨在达到全局最优并减少训练样例复杂度。特别地，单时间尺度的原始-对偶算法首次为非渐进策略最终迭代收敛提供了保证，采用正则化或乐观策略梯度，使策略迭代收敛到最优受限策略。
加速自然策略梯度与样本复杂度改进
文章重点介绍了加速自然策略梯度算法（ANPG），该算法应用加速随机梯度下降获取自然策略梯度，在一般参数化下实现了O(ε^-2)样本复杂度和O(ε^-1)迭代复杂度。相比现有技术，ANPG通过log(1/ε)因子改进了样本复杂度，且无需假设重要性采样权重的方差有上界。在无Hessian和无重要性采样算法类别中，其样本复杂度优于已知算法的O(ε^-1/2)倍，迭代复杂度与之匹配。
平均回报约束下的遗憾与约束违反分析
文章还探讨了无限时段平均回报约束马尔可夫决策过程，这是首个深入研究一般策略参数化下平均回报CMDP的遗憾和约束违反分析的工作。提出的原始-对偶策略梯度算法能确保低遗憾全局最优策略，同时灵活处理约束，实现了Õ(T^{3/4})的目标遗憾和Õ(T^{3/4})的约束违反界限。后续的PD-ANPG算法进一步保证了ε全局最优性差距和ε约束违反，样本复杂度为O(ε^-3)，在CMDP样本复杂度上取得了O(ε^-1)的进展。
Q&A
什么是受限马尔可夫决策过程中的非渐进收敛保证方法？
受限马尔可夫决策过程中的非渐进收敛保证方法是一种新的策略优化算法，提供了在逼近最优价值函数时的收敛性证明，强调了熵正则化的作用。
熵正则化在收敛性中起什么作用？
熵正则化有助于加速收敛，使算法在逼近最优价值函数时表现出更快的收敛速度。
C-NPG-PD算法的主要目标是什么？
C-NPG-PD算法旨在实现全局最优解并减少训练样例的复杂度，特别是在连续状态-动作空间的限制马尔可夫决策过程中。
ANPG算法相比于现有技术有什么优势？
ANPG算法在样本复杂度和迭代复杂度上优于现有技术，通过一个log(1/ε)因子改进了样本复杂度，且不需要假设重要性采样权重的方差有上界。
如何在无限时间折扣奖励的马尔可夫决策过程中实现约束满足？
通过零阶内点方法，可以在无限时间折扣奖励的马尔可夫决策过程中实现约束满足，以最大化预期累积奖励。
本文提出的算法在处理约束问题时有什么创新？
本文提出的基于原始-对偶的策略梯度算法能够灵活处理约束，同时确保低遗憾和全局最优策略。
