Mar, 2023

解决广义博弈问题的平滑方法的收敛分析和加速

HTML
PDF
TL;DR本文针对广义博弈存在的问题，从改进强凸函数以提高理论界限和设计中心化技巧以加速收敛两个方面，提出一种平滑方法来解决大规模广义博弈问题，并将它与CFR+方法相结合，在传统平滑方法不适用的情况下实现较好的性能。
发现论文，激发创造
  • 大规模零和博弈均衡计算的统一视角

    本文研究如何在大型零和博弈中计算近似纳什均衡，提出两种方法：无悔在线学习和基于凸凹点公式的梯度方法，并尝试将两种方法进行整合。

    Nov, 2014

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

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

    Feb, 2017

  • 广义形式博弈中的鲁棒斯塔克伯格均衡及其在有限展望中的扩展

    本文研究了扩展形式博弈中存在不确定性的Stackelberg均衡及其鲁棒性问题，分别引入了关于对手收益以及对手节点估值函数的不确定性条件，并提出了一种新的混合整数规划模型计算此类问题，证明可以在特定情况下准确可靠地计算出鲁棒Stackelberg均衡。

    Nov, 2017

  • 应对策略限制的大规模扩展博弈求解

    研究表明，通过推广反事实遗憾最小化，我们可以解决一般约束下的最优策略问题，并且该算法可广泛应用于复杂博弈中，如安全博弈中的风险缓解和扑克游戏中的对手建模。

    Sep, 2018

  • 扩张式形式博弈中的扩张距离产生函数乐观遗憾最小化

    研究了在广泛形式博弈中最小化后悔和计算纳什均衡的乐观后悔最小化算法的性能，研究了扩展形式游戏距离生成函数的使用，证明了扩展欧几里德距离函数具有广义树片段的强凸性参数的第一个显式边界，提出了一种乐观算法可以优化计算效率，这在最小化后悔而不是计算纳什均衡时表现出很好的结果。

    Oct, 2019

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

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

    Jun, 2020

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

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

    Jun, 2021

  • 广义积和博弈中的最优相关均衡：固定参数算法，难度和双向列生成

    研究了针对不同类型的协同均衡的最优相关策略问题，提出了相关DAG表示方法和双面列生成算法来计算最优策略并探讨其复杂性分析，探究了一些新的基准博弈。

    Mar, 2022

  • 大规模完全信息博弈中求解领导者-追随者均衡的函数逼近

    本研究提出了一种基于神经网络的函数近似方法，应用于广义和博弈的Stackelberg博弈情景，以学习Enforceable Payoff Frontier，从而实现对博弈策略的近似计算和评估。

    Dec, 2022

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

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

    Oct, 2023