非凸博弈中高效的遗憾最小化
本文提出了一种称为 “laminar regret decomposition” 的新框架,该框架扩展了 CFR 算法,并使 regret minimization 能够适用于更广泛的决策点模型和损失函数模型。该框架适用于多种问题类型,例如:序贯决策制定、纳什均衡及其近似解、以及普遍化量子反应均衡。实验证明,该框架所开发的算法与 counterfactual regret minimization 相比,在计算纳什均衡时具有可比性,并且该方法是计算极大规模游戏中的量子反应均衡的第一个算法。此外,我们还展示了一种新类型的可伸缩对手利用方法。
Sep, 2018
简而言之,本文提出了一种针对广义和博弈的、分散、计算高效的算法,其保证所有代理都使用时可以提供次线性遗憾保证,并且不需要代理之间的通信。该算法的主要观察结果是,通过马尔可夫游戏的在线学习基本上可以归结为一种加权遗憾最小化。
Jul, 2022
本文提出了一种新的在线学习方法,用于在大型 extensive-form 游戏中最小化后悔。该方法通过在线学习函数逼近器来估计选择特定行动的后悔值,并使用无悔算法根据这些估计值来定义一系列策略。我们证明了该方法的正确性,并证明了只要逼近函数能够实现后悔值,方法就能自我学习并收敛到纳什均衡。我们的技术可以被理解为现有大型游戏中抽象工作的原则性推广;在我们的工作中,抽象和均衡都是在自我博弈中学习的。我们在实验中展示了该方法可以在相同资源条件下实现比最先进的抽象技术更高质量的策略。
Nov, 2014
本文提出了一种基于乐观的镜像下降的无悔策略算法,可以在非稳态环境下实现 O (sqrt (T)) 的后悔度,并可在变分稳定游戏中收敛到纳什均衡。
Apr, 2021
通过 von Neumann 最小极大定理,我们研究了在线凸优化游戏的最优策略的遗憾。我们证明了,在这种对抗性环境中,最优策略的遗憾与随机进程设置中经验最小化算法的行为密切相关:它等于最小期望损失的总和与最小经验损失之间的差的最大值。我们展示了最优策略的遗憾具有自然的几何解释,因为它可以被视为一个上凸函数的 Jensen 不等式中的差距。利用此表达式,我们对各种在线学习问题的最优策略给出了上下界限制。我们的方法提供了无需构建学习算法的上界,而提供了对抗者的明确最优策略的下界。
Mar, 2009
研究了凸优化问题,提出了基于无遗憾游戏动力学的算法框架,并讨论了多种无遗憾学习算法的选择策略及其拥有的收敛性质,证明了很多经典的凸一阶方法都可以被理解为该框架的特殊情况,并且提出了一些之前未被发现的用于特殊凸优化问题的一阶方法。
Nov, 2021
使用 CFR 框架开发算法以解决行为约束的 extensive-form games,同时计算近似 Nash 平衡改进。比标准算法更好,收敛速率与最先进的 Nash 平衡计算算法相当。
Nov, 2017
本文研究了基于遗憾的算法在连续游戏中寻找近似的纳什均衡,针对反事实遗憾最小化(CFR)算法存在的表示收敛的缺陷,提出了一些基于树形复合结构的乐观遗憾最小化算法,并给出了实验证明其在求解连续游戏时的有效性。
Jun, 2021