Aug, 2010

策略迭代在常数贴现率下的 2 人回合制随机博弈中具有强多项式时间复杂度

PDF
TL;DR本文利用改进的单纯形法、策略迭代算法及策略提升算法的收敛速度，利用最小化操作步数的方法，解决了两人纯策略有限的保底价值为零的零和收益随机博弈的问题。
simplex methoddiscounted markov decision processespolicy iteration algorithmstrategy iterationstochastic games
发现论文，激发创造
  • 策略迭代复杂度的改进和推广的上界

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

    Jun, 2013

  • 具有有界首次回归时间的完全信息随机平均收益博弈的策略迭代是强多项式的

    这篇论文采用非线性 Perron-Frobenius 理论的方法，将 mean-payoff 问题转化为一个具有状态依赖性折现率的折扣问题，从而证明了一个有界的第一次均值回报时间的固定状态，是广义策略迭代强多项式可解的，同时如果所有策略涉及的非负矩阵的谱半径都小于某个值，则折扣问题中折扣率可以是具有状态依赖性（甚至是负值）的。

    Oct, 2013

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

    我们证明采用最高的增益 / 负减少成本枢轴规则的单纯形法在确定性马尔科夫决策过程 (MDPs) 中收敛于强多项式时间，无论折扣因子如何。对于具有 n 个状态和 m 个动作的确定性 MDP，我们证明如果折扣因子是均匀的，则单纯形法需要 O (n^3m^2log^2 n) 次迭代，在每个动作都有不同折扣因子的情况下，它需要 O (n^5m^3log^2 n) 次迭代。

    Aug, 2012

  • 政策迭代的复杂性

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

    Jan, 2013

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

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

    Oct, 2014

  • 策略迭代的指数下界

    本文研究无限期 Markov 决策过程的策略迭代，扩展了两个玩家博弈中策略迭代算法的指数下界到具有总奖励和平均奖励优化标准的 Markov 决策过程。

    Mar, 2010

  • 零和马尔可夫博弈强化学习的一种新政策迭代算法

    本文提出了一种对于零和马尔可夫游戏的学习策略 ——lookahead 策略，该策略使用简单的 naive policy iteration，在计划阶段实现高效的收敛，进一步阐述了在使用我们的算法进行计算规划时的时间复杂度和样本复杂度界限。

    Mar, 2023

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

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

    Oct, 2017

  • 解决折扣随机二人博弈问题的近似最优时间和样本复杂度

    本文研究解决折扣二人零和随机游戏的采样复杂度，并提出一种计算策略的算法以及推广现有的 MDP 算法到多代理设置。

    Aug, 2019

  • 近似策略迭代方案对比

    本文考虑了马尔可夫决策过程所形式化的无限时间折扣率下的最优控制问题，研究了几种近似策略迭代算法，对它们进行了性能分析，显示了非静态策略迭代算法可以在内存和性能之间进行平衡。

    May, 2014