Mar, 2023

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

PDF
TL;DR本文提出了一种对于零和马尔可夫游戏的学习策略 ——lookahead 策略，该策略使用简单的 naive policy iteration，在计划阶段实现高效的收敛，进一步阐述了在使用我们的算法进行计算规划时的时间复杂度和样本复杂度界限。
model-based reinforcement learningplanning phasepolicy iterationmarkov gameslookahead
发现论文，激发创造
  • 零和马尔可夫博弈中政策优化的更快收敛

    本文提出了一种基于 OMWU 方法的单环路政策优化算法，并在二人零和马尔可夫博弈中，通过控制正则化的程度，实现了有限时间的最后一次线性收敛到达量子响应均衡点，并在全信息离散设置中实现了收敛结果。

    Oct, 2022

  • 基于模型的自我对弈强化学习的严密分析

    本文针对多智能体马尔科夫博弈提出了一种基于模型的算法 Nash-VI，在理论上证明其具有较高的样本利用率，并且在实验中证明了其优于现有的基于模型的方法和一些基于无模型的算法，输出单个 Markov 策略且易于存储和执行。

    Oct, 2020

  • 关于回合制零和马尔可夫博弈的强化学习

    本文提出了一种基于强化学习的方法，结合 “探索，策略改进和监督学习”，以找到与纳什均衡相关的价值函数和策略。通过实验证明了该方法在特定情况下可以在近似值方面找到纳什均衡。

    Feb, 2020

  • 强化学习中超越单步贪心方法

    本文研究了改进策略和评估策略之间交替的着名 Policy Iteration 算法，以及其变体中多步向前的政策改进，形成了多步政策改进的变量，导出了新的算法并证明了其收敛性。此外，文章还展示了近期著名的强化学习算法实际上是我们框架的实例，阐明了它们的经验成功，为未来研究提供了推导新算法的方法。

    Feb, 2018

  • 零和马尔可夫博弈中的价值函数逼近

    研究了在零和 Markov 博弈中的价值函数逼近问题，提出了适用于 Markov 博弈的强化学习算法，并针对在两人同时进行移动的特殊问题，给出了 LSTD 和时间差分学习的线性价值函数逼近的收敛保障，通过 LSPI 算法，将该算法应用于足球领域和流量控制问题中，并证明了价值函数逼近在 Markov 博弈中的可行性。

    Dec, 2012

  • 无模型改进的零和马尔科夫博弈的高效样本算法

    为了解决两个玩家零和马尔可夫博弈问题，在多智能体强化学习的理论研究中引起了越来越多的关注。通过提出一种无模型的基于阶段的 Q 学习算法，我们展示了该算法能够与最佳的有模型算法达到相同的样本复杂度，进而首次证明了无模型算法在与模型有关的 $H$ 上的依赖性上能够达到相同的最优性。

    Aug, 2023

  • 基于策略迭代和蒙特卡罗策略评估的强化学习收敛性

    本文提出解决一种强化学习中的长期悬而未决的问题，通过使用前瞻而非简单的贪心策略迭代来提高策略，同时在表格和函数逼近设置中都提供了结果。我们证明了这种策略迭代方案收敛于最优策略。

    Jan, 2023

  • 策略迭代的指数下界

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

    Mar, 2010

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

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

    Aug, 2010

  • 弱可达情况下的零和马尔可夫博弈纳什均衡学习

    通过利用 Tsallis 熵正则化的值迭代方法，我们提出了一种合理且收敛的算法，在弱条件下以无耦合和单时间尺度算法的方式高效地实现了近似纳什均衡。该算法在多项式时间内学习近似纳什均衡，仅需要存在一个诱导不可约和非周期性马尔可夫链的策略对，从而明显减弱了过去的假设。我们的分析利用了负漂移不等式，并引入了 Tsallis 熵的新特性，这些特性具有独立的研究价值。

    Dec, 2023