随机镜像下降法高效求解 MDPs
本文所提出的新算法不依赖于探索策略,通过引入两个新的基于策略的评估算符和对 SPMD 算法的新颖分析,实现了在线策略梯度方法的样本复杂度的近似上界,无需显式探索,可以避免在寻找最优策略时反复执行潜在的高风险动作,具有更强的收敛性能。
Mar, 2023
本文研究了马尔可夫决策过程 (MDP) 的最优策略在线估计问题,并提出了一类基于随机原始对偶法的方法,利用 Bellman 方程的内在极小极大对偶性进行优化。 这些方法具有小的存储空间和低的计算复杂度,通过观察新的状态转移更新值和策略估计的少数坐标。 对于无限时间折扣奖励 MDP,这些 SPD 方法使用 O (|S|^4 |A|^2σ^2/(1-γ)^6ε^2) 的迭代 / 样本数可以高概率地找到绝对 ε- 最优策略,对于有限时间 MDP,迭代次数为 O (|S|^4 |A|^2H^6σ^2/ε^2)。
Dec, 2016
我们研究了如何在带有轨迹反馈的零和不完全信息博弈中学习 ε- 最优策略,通过应用自适应在线镜像下降算法,在信息集中使用逐渐减小的学习率和正则化损失,我们证明了该方法在高概率下能够保证收敛速度为~T^(-1/2),并且在理论上的最佳学习率和采样策略选择时,对于游戏参数的依赖性接近最优。为了实现这些结果,我们扩展了对 OMD 稳定性的概念,允许随时间变化的凸增量正则化。
Sep, 2023
提出了一种新的策略梯度方法 —— 同伦策略镜像下降 (HPMD),用于解决具有有限状态和动作空间的折扣、无限时间 MDPs,并具有多种计算性质。该方法在全局和局部上均具有收敛性,并且能够在一定条件下证明和表征极限策略。同时,使用该方法可同时获得非渐近最优策略和极大信息熵的极限策略,在不同 Bregman 散度之间进行扩展,以及是一些常见 Bregman 散度的有限时间精确收敛。
Jan, 2022
提出了一种采用采样技术的快速算法来解决折扣马尔可夫决策过程的近似求解,并证明了算法的收敛性和复杂度。同时,结合经典的价值迭代与方差约减技术,改进了该算法的性能,使其具有线性收敛性和渐进最优性。
Oct, 2017
本文提出了一种基于 Primal-Dual π Learning 的方法,利用线性对偶性更新价值与策略向量以逼近无穷时间和折扣因子为 1 的马尔可夫决策过程的最优策略,并给出了复杂度上界,并且这种方法还能应用于有限状态、有限动作空间以及随机转移概率模型下的计算问题,当情况许可下,此方法可以在次线性时间内解决平均奖励最大化的问题。
Oct, 2017
研究如何解决具有不确定转移内核的折现,有限状态,有限行动空间 MDP 的强鲁棒性问题,旨在寻找一个抵抗传递不确定性的最佳策略。与标准 MDP 规划相比,本文提出了一个名为 RPMD 的策略型一阶方法,并对于两种递增步长的情形,建立了寻找 ε- 最优策略的 O (log (1/ε)) 和 O (1/ε) 迭代复杂度。本文还提出了一种名为 SRPMD 的随机变量。
Sep, 2022
研究无限时间折扣马尔可夫决策问题,并以策略空间的直接参数化研究投影策略梯度方法和一般类别的策略镜像下降方法的收敛速度,包括不需要熵或其他强凸正则化的自然策略梯度方法及投影 Q - 下降方法,并分析近似策略镜像下降方法的收敛速度和样本复杂性估计。
Jan, 2022