Sep, 2018

面向序列决策过程和广义博弈的在线凸优化

HTML
PDF
TL;DR本文提出了一种称为“laminar regret decomposition”的新框架，该框架扩展了CFR算法，并使 regret minimization 能够适用于更广泛的决策点模型和损失函数模型。该框架适用于多种问题类型，例如：序贯决策制定、纳什均衡及其近似解、以及普遍化量子反应均衡。实验证明，该框架所开发的算法与 counterfactual regret minimization 相比，在计算纳什均衡时具有可比性，并且该方法是计算极大规模游戏中的量子反应均衡的第一个算法。此外，我们还展示了一种新类型的可伸缩对手利用方法。
发现论文，激发创造
  • 使用函数遗憾估计来解决游戏

    本文提出了一种新的在线学习方法，用于在大型 extensive-form 游戏中最小化后悔。该方法通过在线学习函数逼近器来估计选择特定行动的后悔值，并使用无悔算法根据这些估计值来定义一系列策略。我们证明了该方法的正确性，并证明了只要逼近函数能够实现后悔值，方法就能自我学习并收敛到纳什均衡。我们的技术可以被理解为现有大型游戏中抽象工作的原则性推广；在我们的工作中，抽象和均衡都是在自我博弈中学习的。我们在实验中展示了该方法可以在相同资源条件下实现比最先进的抽象技术更高质量的策略。

    Nov, 2014

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

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

    Feb, 2017

  • 非凸博弈中高效的遗憾最小化

    本文探讨了在非凸损失函数的重复博弈中如何最小化遗憾，并给出了基于梯度下降的方法来实现最优遗憾并保证收敛到平衡点。

    Jul, 2017

  • 行为受限零和博弈中的遗憾最小化

    使用 CFR 框架开发算法以解决行为约束的 extensive-form games，同时计算近似 Nash 平衡改进。比标准算法更好，收敛速率与最先进的 Nash 平衡计算算法相当。

    Nov, 2017

  • 通过折现遗憾最小化解决不完美信息博弈

    本文介绍了改进的Counterfactual regret minimization（CFR）算法，包括折扣遗憾值、迭代加权和非标准遗憾值最小化等四个变量，我们的新算法在大规模现实环境下的每个游戏中都优于之前的方法CFR+。另外，与CFR+相比，我们的算法更容易应用于现代的不完美信息游戏修剪技术和采样方法。

    Sep, 2018

  • 稳定预测性乐观反事实遗憾最小化

    本文提出了第一个在 CFIR 基础上打破了迭代次数平方根的收敛速度的 CFR 变体，通过优化后的遗憾最小化器和新的稳定性概念，在 CFR 中引入了稳定可预测性，并将每个遗憾最小化器稳定性设置为所在决策树中的位置，实现了 $O(T^{-3/4})$ 的收敛速率。

    Feb, 2019

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

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

    Oct, 2019

  • 未知序贯决策问题和游戏的无模型在线学习

    提出了一种适用于黑盒环境的极限情况的后悔最小化算法，通过以前保证仅实现的限制来实现亚线性的后悔率，并将其应用于逼近Nash均衡，学习最佳反应以及安全的对手利用等问题。

    Mar, 2021

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

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

    Jun, 2021

  • 使用乐观在线镜像下降法来减小加权对策后悔

    利用乐观的在线镜像下降算法最小化加权的对策后悔，从而加速收敛并解决博弈问题。

    Apr, 2024