Jul, 2024

指数权重算法的游戏

HTML
PDF
TL;DR本研究研究了具有恒定学习率的指数权重算法的最后迭代收敛性质，通过在离散时间中考虑重复互动，每个参与者使用一个具有初始混合行动和固定学习率的指数权重算法，以使在时间t处开始播放的混合行动概率为$p^t$，遵循齐次马尔科夫链。首先，我们证明了在存在严格纳什均衡时，播放下一阶段的严格纳什均衡的概率几乎必定收敛于0或1。其次，我们证明了$p^t$的极限（如果存在）属于“具有均等化收益的纳什均衡集合”。第三，我们证明在强协调博弈中，其中玩家的收益在对角线上是正数，在其他地方为0，$p^t$几乎必定收敛于其中一个严格纳什均衡。最后，我们提出了一些开放性问题。
发现论文，激发创造
  • 斯塔克贝格博弈中的学习动态收敛

    本文研究了斯塔克伯格博弈中学习动态的收敛性，并提出了一种基于梯度的学习更新规则，用于训练生成对抗网络。

    Jun, 2019

  • 无遗憾学习和混合纳什均衡：不能相互混合

    本文研究了no-regret动力学中最常被考虑的动态系统之一 - Follow-the-regularized-leader的行为，证明了非严格的纳什均衡对于no-regret学习是不稳定的且不能吸引该动态系统的稳定状态，因此只有严格的纳什均衡是no-regret动力学的稳定限制点。

    Oct, 2020

  • 何时才能高效学习具有多个玩家的广义和马尔可夫博弈？

    本文探讨了多人博弈中学习的样本复杂性问题, 并设计算法在样本复杂度多项式级别下, 求解多人一般和马尔可夫博弈的粗略关联均衡和关联均衡, 同时提出了针对特定条件下的学习算法, 显著提高了现有算法的效率和精度。

    Oct, 2021

  • 驯服指数级行动集：在在线拥塞博弈中实现次线性遗憾和快速收敛到纳什均衡

    本研究通过提出CongestEXP算法来解决在线拥塞博弈问题，通过在设施级别上维护权重，创新性地规避了指数级依赖于可能的设施集合大小的遗憾界，并且适用于任何个体玩家，并在存在严格纳什均衡时，能以近似指数速度收敛至纳什策略。

    Jun, 2023

  • 正则化学习下游戏中动态稳定性和战略稳定性的等效性

    通过研究正则化的无悔学习方法在有限游戏中的长期行为，我们发现玩家的实际策略如何随时间演变的理解非常有限，同时发现只有严格纳什均衡是稳定吸引的，进而揭示了玩家的日常对策的集合有理性的特性。我们进一步刻画了相应集合的稳定和收敛速率，并表明基于熵正则化的方法以几何速度收敛，而基于投影的方法在有限次迭代内收敛，即使是在带有被动反馈的并发奖励的情况下。

    Nov, 2023

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

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

    Dec, 2023

  • 有限游戏的几何分解：无遗憾学习下的收敛与循环

    基于Riemannian框架和Shahshahani度量，在无悔学习中研究了复杂动力学的分解，发现无悔动力学在体积保持和收敛性方面具有特殊特征，并与潜势和谐波分解存在深层关联。

    May, 2024

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

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

    Jun, 2024

  • 基于收益的独立学习在零和随机博弈中的最后迭代收敛

    本文研究了两人零和矩阵博弈和随机博弈，通过收益驱动的学习动态实现了收敛且对称的学习过程。我们首次进行了有限样本分析，结果表明在矩阵博弈中找到纳什分布的样本复杂度为$O(\epsilon^{-1})$，而找到纳什均衡的样本复杂度为$O(\epsilon^{-8})$，具有重要的理论和实践意义。

    Sep, 2024

  • 基于收益的独立学习在零和随机博弈中的最后迭代收敛性

    本研究解决了两玩家零和矩阵和随机博弈中的学习动力学问题，提出了一种基于收益的收敛性学习方法。该方法首次提供了具有最后迭代收敛保证的有限样本分析，发现矩阵博弈寻找纳什分布的样本复杂度为$O(\epsilon^{-1})$，而寻求纳什均衡的复杂度为$O(\epsilon^{-8})$。此工作为随机近似算法的收敛行为提供了新的视角。

    Sep, 2024