ICMLJun, 2021

共识乘权更新：使用基于投影器的游戏签名学习学习

PDF
TL;DR本研究介绍了一种新的以学习系数的增量式更新规则为主要方法的强化学习策略，该策略依据游戏的本质 —— 游戏签名进行调整，用于学习在游戏中达到最优状态的方法，其中游戏的多个方面分解成具有交换性的投影算子，介绍了一个新的算法 CMWU，在零和双矩阵游戏中具有局部收敛的保证。
multiplicative weights updatenash equilibriareinforcement learninggame signaturecmwu
发现论文，激发创造
  • 游戏中的混沌、极端主义和乐观主义：学习的量化分析

    本文研究了 MWU 和 OMWU 在零和博弈和协调博弈中的体积分析，并通过对初值集合的变换证明了其新颖的收敛或发散特性。

    May, 2020

  • 基于矩阵乘法权重的量子博弈中的回报学习

    研究了量子博弈和其他类别的半定博弈中基于标量、基于回馈的学习问题。介绍了一套适用于不同信息框架的最小信息矩阵乘法权重（3MW）方法，并设计了适用于半定几何问题的零阶梯度采样器。展示了确定性回馈和随机回报可观察的 3MW 方法的收敛性，以及对满足一定一阶稳定条件的全部均衡点局部收敛的正则化变体。

    Nov, 2023

  • 快速学习游戏的最后迭代收敛需要健忘算法

    通过在线学习的自我对弈是解决大规模两人零和游戏的主要方法之一，尤其流行的算法包括乐观的乘积权重更新（OMWU）和乐观的梯度下降 - 梯度上升（OGDA），本文证明了 OMWU 存在潜在的较慢的最后迭代收敛问题。

    Jun, 2024

  • 量子零和游戏中寻找纳什均衡的二次加速

    通过引入一种新的算法层次结构中的 Optimistic Matrix Multiplicative Weights Update (OMMWU) 算法，本研究在计算量子零和博弈中的 ε-Nash 均衡方面取得了二次速度提升，并为量子游戏理论中的主要议题提供了新的基准。

    Nov, 2023

  • 对称锥体上的在线凸优化的乘法更新

    对在线凸优化问题进行研究，采用对称锥中一对称切片的投影无关算法 Symmetric-Cone Multiplicative Weights Update (SCMWU)，通过使用欧几里德 - 约旦代数的工具，将其等价于 Follow-the-Regularized-Leader 和 Online Mirror Descent 算法，证明了其是一种无悔算法，并通过大量实验验证了理论结果。

    Jul, 2023

  • 末次迭代收敛：零和博弈与约束极小极大优化

    本文研究了一种叫做 OMWU 的算法，该算法在约束的 min-max 最优化问题中表现出优秀的收敛性以及稳定性。该算法与先前的梯度下降法及其他学习算法不同，且需要使用新的技术和思路。

    Jul, 2018

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

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

    Oct, 2022

  • 学习的混沌：通过游戏分解实现零和协调之外的协作

    研究发现，使用某些学习算法在若干个游戏子空间中导致了 Lyapunov 混沌现象，此现象对于游戏中的学习来说是一个重要问题，并且作者提出了一个矩阵支配的概念，设计了一个线性方案来表征使 MWU 在 Bimatrix 游戏空间中几乎处处都是 Lyapunov 混沌的 Bimatrix 游戏集系。

    Aug, 2020

  • 解决博弈中的高效收敛算法

    通过转换问题为一系列凸凹优化问题， ' 无悔算法 ' 在学习纳什均衡中取得竞争性表现，在离散时间反馈设置下实现最后迭代收敛。

    Aug, 2023

  • 有约束鞍点优化中的线性最后迭代收敛性

    本研究对 OGDA 和 OMWU 在约束优化问题中的后迭代收敛性进行了显著扩展，提出了一种足够条件来保证 OGDA 在多面体上的双线性博弈问题中展现出线性的后迭代收敛性，并且没有唯一均衡假设，同时在强凸 - 强凹函数上也保持收敛性，这种条件也适用于多个一般目标和可行集合的约束下的 OGDA 算法，并通过实验结果验证了理论。

    Jun, 2020