策略迭代最坏情况复杂度的改进界
本文研究关于 Markov 决策过程的策略迭代算法的收敛性和复杂度,提出了一种复杂度上界的限制方法,不依赖于折扣因子的价值,有效地限制了策略迭代算法收敛至最优策略所需的迭代次数。
Jan, 2013
本文研究了两种策略迭代算法在马尔可夫决策过程中收敛所需的迭代次数,并通过结构性质得到了与折扣因子无关的上界,在假设状态空间分为瞬态和常态状态的情况下,Howard's PI 和 Simplex-PI 都可以在强多项式时间内终止。
Jun, 2013
本篇研究考虑了马尔科夫决策过程 (Markov Decision Processes) 的无限时间折扣优化控制问题,并提供了 Policy Search 算法以及 Direct Policy Iteration 和 Conservative Policy Iteration 的性能保证,同时提出了 Non-Stationary Direct Policy Iteration 算法,并证明其时间复杂度类似于 DPI,性能保证好于 DPI,且与 CPI 相当。
Jun, 2013
本文利用改进的单纯形法、策略迭代算法及策略提升算法的收敛速度,利用最小化操作步数的方法,解决了两人纯策略有限的保底价值为零的零和收益随机博弈的问题。
Aug, 2010
本文考虑了马尔可夫决策过程所形式化的无限时间折扣率下的最优控制问题,研究了几种近似策略迭代算法,对它们进行了性能分析,显示了非静态策略迭代算法可以在内存和性能之间进行平衡。
May, 2014
提出了一种采用采样技术的快速算法来解决折扣马尔可夫决策过程的近似求解,并证明了算法的收敛性和复杂度。同时,结合经典的价值迭代与方差约减技术,改进了该算法的性能,使其具有线性收敛性和渐进最优性。
Oct, 2017
研究如何解决具有不确定转移内核的折现,有限状态,有限行动空间 MDP 的强鲁棒性问题,旨在寻找一个抵抗传递不确定性的最佳策略。与标准 MDP 规划相比,本文提出了一个名为 RPMD 的策略型一阶方法,并对于两种递增步长的情形,建立了寻找 ε- 最优策略的 O (log (1/ε)) 和 O (1/ε) 迭代复杂度。本文还提出了一种名为 SRPMD 的随机变量。
Sep, 2022
我们提出了适用于合作多智能体有限和无限时域折扣马尔可夫决策过程的逼近策略迭代算法,其中使用近似线性规划计算近似值函数并实施分散策略改进。
Nov, 2023
本文提出了一种对于零和马尔可夫游戏的学习策略 ——lookahead 策略,该策略使用简单的 naive policy iteration,在计划阶段实现高效的收敛,进一步阐述了在使用我们的算法进行计算规划时的时间复杂度和样本复杂度界限。
Mar, 2023