广义式博弈中随机后悔最小化
基于 Counterfactual Regret Minimization(CFR)方法,该研究提出了一种名为 Pure CFR(PCFR)的新算法,扩展了 CFR 并结合了 Fictitious Play(FP)的概念,通过使用最佳响应策略而非遗憾匹配策略提高算法性能。PCFR 具备与 CFR 及其变种算法包括 Monte Carlo CFR(MCCFR)相结合的能力,实验证明了其能够通过 Blackwell 可达性来达到收敛,而 PMCCFR 能显著降低时间和空间复杂度,至少比 MCCFR 收敛速度快三倍。此外,由于 PMCCFR 不通过严格劣势策略路径,研究者还开发了一种新的启动算法,该算法受严格劣势策略消除方法的启发,结果表明使用新的启动算法的 PMCCFR 优化比 CFR + 算法收敛速度快两个数量级。
Sep, 2023
本文介绍了改进的 Counterfactual regret minimization(CFR)算法,包括折扣遗憾值、迭代加权和非标准遗憾值最小化等四个变量,我们的新算法在大规模现实环境下的每个游戏中都优于之前的方法 CFR+。另外,与 CFR + 相比,我们的算法更容易应用于现代的不完美信息游戏修剪技术和采样方法。
Sep, 2018
本文介绍了一种新的 CFR 形式:Deep CFR,它不再需要抽象,而是使用深度神经网络来近似 CFR 在完整游戏中的行为,并展示了它在大型扑克游戏中的成功表现。
Nov, 2018
本文介绍了一种方差缩减技术 VR-MCCFR,它可以应用于任何 MCCFR 的采样变型方法。这个新公式可以从同一事件中的其他估计值启动引导,即引导基线在采样轨迹上沿估计传递收益,而估计值保持不偏。实验结果表明,VR-MCCFR 可以提供一个数量级的加速,同时经验方差降低三个数量级。方差的降低使得 CFR + 可以和采样一起使用,加速两个数量级。
Sep, 2018
本文提出了一种称为 “laminar regret decomposition” 的新框架,该框架扩展了 CFR 算法,并使 regret minimization 能够适用于更广泛的决策点模型和损失函数模型。该框架适用于多种问题类型,例如:序贯决策制定、纳什均衡及其近似解、以及普遍化量子反应均衡。实验证明,该框架所开发的算法与 counterfactual regret minimization 相比,在计算纳什均衡时具有可比性,并且该方法是计算极大规模游戏中的量子反应均衡的第一个算法。此外,我们还展示了一种新类型的可伸缩对手利用方法。
Sep, 2018
本文提出无法完全回忆的游戏中,针对使用 CFR 算法的一般类游戏的第一个遗憾上限及其不适用性,同时证明使用 CFR 在任何抽象类游戏中都适用,且在三种情况下证明不完全回忆可用于交换少量遗憾和显著降低内存。
May, 2012
提出了一种适用于黑盒环境的极限情况的后悔最小化算法,通过以前保证仅实现的限制来实现亚线性的后悔率,并将其应用于逼近 Nash 均衡,学习最佳反应以及安全的对手利用等问题。
Mar, 2021
本文提出了第一个在 CFIR 基础上打破了迭代次数平方根的收敛速度的 CFR 变体,通过优化后的遗憾最小化器和新的稳定性概念,在 CFR 中引入了稳定可预测性,并将每个遗憾最小化器稳定性设置为所在决策树中的位置,实现了 $O (T^{-3/4})$ 的收敛速率。
Feb, 2019
本文研究了基于遗憾的算法在连续游戏中寻找近似的纳什均衡,针对反事实遗憾最小化(CFR)算法存在的表示收敛的缺陷,提出了一些基于树形复合结构的乐观遗憾最小化算法,并给出了实验证明其在求解连续游戏时的有效性。
Jun, 2021
使用 CFR 框架开发算法以解决行为约束的 extensive-form games,同时计算近似 Nash 平衡改进。比标准算法更好,收敛速率与最先进的 Nash 平衡计算算法相当。
Nov, 2017