Jun, 2022

强化学习、量化响应均衡和二人零和博弈的统一方法

PDF
TL;DR研究磁镜下降算法作为均衡求解器和两人零和游戏强化学习的方法，并证明其在多种场景中都可以取得优秀的性能表现，包括在可扩展形式下的均衡求解和在表格设置下的竞争性结果与 CFR 相比。
发现论文，激发创造
  • 稀疏 Q 学习和镜像下降

    该论文探讨了基于在线凸优化的强化学习的新框架，特别是镜像下降及相关算法，提出了一种新的类似于梯度下降的迭代方法。其中，基于不同 Bregman 散度的抛物线梯度强化学习法比常规 TD 学习更为普适。还提出了一种新型的稀疏镜像下降强化学习方法，相比之前基于二阶矩阵方法的方法，在寻找一个 l1 正则化 Bellman 方程的稀疏不动点时具有显著的计算优势。

    Oct, 2012

  • 广义形式博弈中的本地化和自适应镜像下降

    我们研究了如何在带有轨迹反馈的零和不完全信息博弈中学习 ε- 最优策略，通过应用自适应在线镜像下降算法，在信息集中使用逐渐减小的学习率和正则化损失，我们证明了该方法在高概率下能够保证收敛速度为～T^(-1/2)，并且在理论上的最佳学习率和采样策略选择时，对于游戏参数的依赖性接近最优。为了实现这些结果，我们扩展了对 OMD 稳定性的概念，允许随时间变化的凸增量正则化。

    Sep, 2023

  • 基于深度强化学习的面向人口的在线镜像下降法求解均场博弈

    我们提出了一种深度强化学习算法，通过设计额外的内循环重放缓冲区，代理可以有效地学习如何从任何分布实现纳什均衡，从而在大规模多智能体系统中实现依赖于人口的纳什均衡。数值实验结果表明，我们的算法具有比现有技术的算法更好的收敛性质，特别是对于依赖于人口的策略的虚拟游戏的深度强化学习版本。

    Mar, 2024

  • 无限时段竞争马尔可夫博弈中分散乐观梯度下降 / 上升的最后迭代收敛

    研究无穷时间折扣二人零和马尔可夫博弈，开发了一种分散算法，自我对弈时能够收敛到 Nash 均衡点。

    Feb, 2021

  • 具有熵正则化的竞争性游戏的快速策略外推方法

    本文研究了竞争性游戏的均衡计算问题，提出了一种通过熵正则化实现的解法，可以在线性速率下找到量子反应均衡，并且可以实现分散式迭代更新，同时还可以在亚线性速率下找到非正则矩阵博弈的纳什均衡和解决零和 MDP。

    May, 2021

  • 诚实面对：零和博弈最优非后悔框架

    本文提出了针对分散式场景中双方零和博弈问题的算法，提供了最佳的诚实遗憾和对抗遗憾率，解决了收敛到游戏价值的对数项的开放问题，并通过乐观的镜像下降算法与鲁棒的乐观镜像下降算法的信号传递方案相结合，实现了最佳结果。

    Feb, 2018

  • 可预测序列的优化、学习和游戏

    提供了乐观镜面下降算法的几个应用：将其用于线下优化中的镜像近端算法、扩展到 Holder 平滑函数、并将结果应用于鞍点问题；将其用于有限零和矩阵博弈中，为两个强耦合玩家提供最小化最大值均衡的渐进速率 O ((log T)/T)；再考虑问题的部分信息版本并将结果应用于凸规划，展示了近似最大流问题的简单算法。

    Nov, 2013

  • 竞争性梯度下降

    本文提出了一种用于计算竞争性双人游戏纳什均衡的新算法，该算法基于正则化双线性局部逼近的纳什均衡，避免了交替梯度下降中出现的振荡和发散，而且在达到指数级 (局部) 收敛性的同时，其收敛和稳定性的性质对于玩家之间的强交互是稳健的，具有更快的收敛速度。

    May, 2019

  • 多智能体竞争性次优演示逆强化学习

    本文介绍一种新的逆强化学习算法，通过深度神经网络模型近似和零和随机博弈的对抗式训练来寻找纳什均衡和奖励函数，解决了以往基于表格表示无法解决的问题。

    Jan, 2018

  • 零和马尔可夫博弈中政策优化的更快收敛

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

    Oct, 2022