Aug, 2012

简单形法解决确定性 Markov 决策问题的强多项式时间复杂度

PDF
TL;DR我们证明采用最高的增益 / 负减少成本枢轴规则的单纯形法在确定性马尔科夫决策过程 (MDPs) 中收敛于强多项式时间，无论折扣因子如何。对于具有 n 个状态和 m 个动作的确定性 MDP，我们证明如果折扣因子是均匀的，则单纯形法需要 O (n^3m^2log^2 n) 次迭代，在每个动作都有不同折扣因子的情况下，它需要 O (n^5m^3log^2 n) 次迭代。
发现论文，激发创造
  • 策略迭代在常数贴现率下的 2 人回合制随机博弈中具有强多项式时间复杂度

    本文利用改进的单纯形法、策略迭代算法及策略提升算法的收敛速度，利用最小化操作步数的方法，解决了两人纯策略有限的保底价值为零的零和收益随机博弈的问题。

    Aug, 2010

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

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

    Jun, 2013

  • 随机线性规划以几乎线性（有时是亚线性）的运行时间解决折扣马尔科夫决策问题

    提出一种新的随机线性规划算法，利用价值 - 策略对偶和二叉树数据结构，自适应地采样状态 - 动作 - 状态转移，并进行指数原始 - 对偶更新，从而以几乎线性的运行时间在最坏情况下找到一个 ε- 最优策略。当马尔可夫决策过程是遍历的并且以某些特殊的数据格式指定时，该算法使用线性的运行时间，在状态 - 动作对的总数中是次线性的，为解决随机动态规划问题提供了新的途径和复杂性基准。

    Apr, 2017

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

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

    Oct, 2017

  • 鲁棒马尔科夫决策过程的一阶策略优化

    研究如何解决具有不确定转移内核的折现，有限状态，有限行动空间 MDP 的强鲁棒性问题，旨在寻找一个抵抗传递不确定性的最佳策略。与标准 MDP 规划相比，本文提出了一个名为 RPMD 的策略型一阶方法，并对于两种递增步长的情形，建立了寻找 ε- 最优策略的 O (log (1/ε)) 和 O (1/ε) 迭代复杂度。本文还提出了一种名为 SRPMD 的随机变量。

    Sep, 2022

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

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

    Oct, 2014

  • 随机镜像下降法高效求解 MDPs

    通过基于原始 - 对偶随机镜像下降的统一框架，提供了一种近似求解具有生成模型的无限时域马尔可夫决策过程，同时提出了解决双线性鞍点问题与约束 MDPs 的方法。

    Aug, 2020

  • 大规模马尔可夫决策问题的线性规划

    本文考虑了控制具有大状态空间的马尔可夫决策过程以最小化平均成本的问题，并使用线性规划和两种方法，即基于随机凸优化和基于约束采样的方法，将性能提高到与在低维策略类中的任何策略相比的最佳水平。

    Feb, 2014

  • 通过线性规划对偶解决大规模马尔可夫决策问题

    本文提出了一种针对状态空间较大的 MDP 问题进行优化的方法，该方法基于一小组策略的占用度量的低维度逼近，并提出了一个有效的算法，可用于在该类策略中找到低过度损失相对于最佳策略的策略。作者限定了平均成本和折扣成本情况下的过量损失，并在队列应用中展示了该方法的有效性。

    Jan, 2019

  • 政策迭代的复杂性

    本文研究关于 Markov 决策过程的策略迭代算法的收敛性和复杂度，提出了一种复杂度上界的限制方法，不依赖于折扣因子的价值，有效地限制了策略迭代算法收敛至最优策略所需的迭代次数。

    Jan, 2013