IJCAIMar, 2019

使用利用率下降算法计算序列对抗游戏的近似均衡

PDF
TL;DR本文提出了一种名为 “Exploitability Descent” 的新算法，通过直接针对最坏情况的对手进行策略优化，计算具有不完全信息的两人零和博弈的近似均衡。我们证明，当遵循此优化时，玩家策略的可利用性会渐近地收敛于零，因此当两个玩家同时使用此优化时，联合策略会收敛于纳什均衡。与虚拟实现（XFP）和反事实后悔（CFR）不同，我们的收敛结果涉及到被优化的策略而不是平均策略。我们的实验在纸面上就达到了 XFP 和 CFR 相当的收敛速率，利用函数逼近，我们发现我们的算法在两个游戏中优于纸面情况，这是在此类算法中不完全信息游戏中的首个结果。
发现论文，激发创造
  • 通过最小化最优响应集合的剥削度来计算平衡

    本文研究了在连续游戏中计算近似 Nash 均衡的问题，并提出了一种新的准则来最小化渗透性的近似值。

    Jan, 2023

  • 具有不完全信息的广义博弈的近最优学习

    本文提出两种新算法：平衡在线镜像下降和平衡对策后悔最小化，通过整合平衡探索策略到它们的经典对应物算法，解决学习不完美信息的广义零和游戏的近似 Nash 均衡问题。同时，将结果推广到学习多人游戏的粗略相关均衡。

    Feb, 2022

  • 广义广义扩展形式虚拟博弈算法

    我们介绍了一种简单的广义形式虚拟博弈算法，用于寻找二人零和游戏的均衡点，该算法实现等价于 Fictitious Play 的广义形式。与类似的广义形式虚拟博弈算法和反事实遗憾最小化算法相比，我们比较了其性能。这三种算法在减少存储需求和计算复杂度方面具有相同的优势，该新算法直观且容易实现，是寻求快速且简便的游戏求解工具的一个吸引人的选择。

    Oct, 2023

  • 近似廣泛型完美均衡的平滑方法

    通过发展更高效和可扩展的算法，使用稀疏迭代方法的行为扰动来解决不完全信息博弈中的纳什均衡问题，从而实现最优均衡，但不排除博弈树中未到达的子树中存在次优策略。 通过使用平滑方法，能够计算出一个近似的 extensive-form 完美均衡，以解决经典的纳什均衡算法中存在的精度问题。

    May, 2017

  • 用于零和平衡点求解的稀疏线性规划

    该论文提出了一种新颖的方法利用线性规划解决计算均衡的问题，这种方法比以往的算法更高效，并可以用于解决大型的信息不完备博弈，特别是在极限状态下。

    Jun, 2020

  • 广义博弈中的最后迭代收敛

    本文研究了基于遗憾的算法在连续游戏中寻找近似的纳什均衡，针对反事实遗憾最小化（CFR）算法存在的表示收敛的缺陷，提出了一些基于树形复合结构的乐观遗憾最小化算法，并给出了实验证明其在求解连续游戏时的有效性。

    Jun, 2021

  • 利用量子对手在大型双人游戏中的复杂性和算法

    本文旨在分析和提出可扩展的算法，以计算正常形式和广义形式下对量化对手的有效和稳健策略，通过对量化对手的剥削，定义了两种解决方案，分析了它们的特性，并证明了计算这些解决方案是计算上困难的，因此我们评估了几种基于可扩展的对偶后悔最小化的启发式近似方法，并且鉴别了比先前使用的变体更好地利用有界对手的 CFR 变体，同时被最坏情况的完全理性对手所利用。

    Sep, 2020

  • 相关对局的回顾性和序贯理性

    通过适应性算法的考虑以确保比修改行为所能达到的结果更好，我们可以基于相关学习动态产生新的博弈理论分析，这样做比基于平衡策略算法更加有效，因为前者可以处理非零和多人博弈问题。我们重新审视了博弈理论中的中介均衡和偏差类型，证明了没有可行的概念包含所有其他类型，并引出了一个追溯与规避策略算法的平衡类别的定义。

    Dec, 2020

  • 竞争性梯度下降

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

    May, 2019

  • 针对展开式博弈的平滑理论与实践进展

    本文主要研究如何通过改进膨胀熵函数的设计，加速第一阶段方法来解决 extensive-form games 问题，并提出了新的加权方案，实践证明本文方法比 CFR + 算法更快。

    Feb, 2017