广义博弈中的最后迭代收敛
本文主要研究如何通过改进膨胀熵函数的设计,加速第一阶段方法来解决 extensive-form games 问题,并提出了新的加权方案,实践证明本文方法比 CFR+算法更快。
Feb, 2017
使用 CFR 框架开发算法以解决行为约束的 extensive-form games,同时计算近似 Nash 平衡改进。比标准算法更好,收敛速率与最先进的 Nash 平衡计算算法相当。
Nov, 2017
本文提出了一种称为“laminar regret decomposition”的新框架,该框架扩展了CFR算法,并使 regret minimization 能够适用于更广泛的决策点模型和损失函数模型。该框架适用于多种问题类型,例如:序贯决策制定、纳什均衡及其近似解、以及普遍化量子反应均衡。实验证明,该框架所开发的算法与 counterfactual regret minimization 相比,在计算纳什均衡时具有可比性,并且该方法是计算极大规模游戏中的量子反应均衡的第一个算法。此外,我们还展示了一种新类型的可伸缩对手利用方法。
Sep, 2018
本文提出了第一个在 CFIR 基础上打破了迭代次数平方根的收敛速度的 CFR 变体,通过优化后的遗憾最小化器和新的稳定性概念,在 CFR 中引入了稳定可预测性,并将每个遗憾最小化器稳定性设置为所在决策树中的位置,实现了 $O(T^{-3/4})$ 的收敛速率。
Feb, 2019
研究了在广泛形式博弈中最小化后悔和计算纳什均衡的乐观后悔最小化算法的性能,研究了扩展形式游戏距离生成函数的使用,证明了扩展欧几里德距离函数具有广义树片段的强凸性参数的第一个显式边界,提出了一种乐观算法可以优化计算效率,这在最小化后悔而不是计算纳什均衡时表现出很好的结果。
Oct, 2019
提出了一种适用于黑盒环境的极限情况的后悔最小化算法,通过以前保证仅实现的限制来实现亚线性的后悔率,并将其应用于逼近Nash均衡,学习最佳反应以及安全的对手利用等问题。
Mar, 2021
研究了基于遗憾匹配(RM+)及其变种的算法在求解大规模两人零和博弈中的最优策略时的迭代收敛性,并通过数值实验证明了部分实际变种算法在简单的3×3游戏中无法保证迭代收敛。进一步证明了基于平滑技术的最新变种算法,如extragradient RM+ 和 smooth Predictive RM+ 在最优策略上存在渐进收敛以及1/√t的最优策略收敛。最后,引入了重启变种算法,并证明它们在最优策略上可达到线性级别的收敛速度。
Nov, 2023
通过在线学习的自我对弈是解决大规模两人零和游戏的主要方法之一,尤其流行的算法包括乐观的乘积权重更新(OMWU)和乐观的梯度下降-梯度上升(OGDA),本文证明了OMWU存在潜在的较慢的最后迭代收敛问题。
Jun, 2024