组合无遗憾和 Q 学习
本文提出无法完全回忆的游戏中,针对使用 CFR 算法的一般类游戏的第一个遗憾上限及其不适用性,同时证明使用 CFR 在任何抽象类游戏中都适用,且在三种情况下证明不完全回忆可用于交换少量遗憾和显著降低内存。
May, 2012
提出了一种适用于黑盒环境的极限情况的后悔最小化算法,通过以前保证仅实现的限制来实现亚线性的后悔率,并将其应用于逼近 Nash 均衡,学习最佳反应以及安全的对手利用等问题。
Mar, 2021
使用 CFR 框架开发算法以解决行为约束的 extensive-form games,同时计算近似 Nash 平衡改进。比标准算法更好,收敛速率与最先进的 Nash 平衡计算算法相当。
Nov, 2017
本文介绍了一种新的 CFR 形式:Deep CFR,它不再需要抽象,而是使用深度神经网络来近似 CFR 在完整游戏中的行为,并展示了它在大型扑克游戏中的成功表现。
Nov, 2018
本文介绍了改进的 Counterfactual regret minimization(CFR)算法,包括折扣遗憾值、迭代加权和非标准遗憾值最小化等四个变量,我们的新算法在大规模现实环境下的每个游戏中都优于之前的方法 CFR+。另外,与 CFR + 相比,我们的算法更容易应用于现代的不完美信息游戏修剪技术和采样方法。
Sep, 2018
本文研究了基于遗憾的算法在连续游戏中寻找近似的纳什均衡,针对反事实遗憾最小化(CFR)算法存在的表示收敛的缺陷,提出了一些基于树形复合结构的乐观遗憾最小化算法,并给出了实验证明其在求解连续游戏时的有效性。
Jun, 2021
本文提出了一种新的在线学习方法,用于在大型 extensive-form 游戏中最小化后悔。该方法通过在线学习函数逼近器来估计选择特定行动的后悔值,并使用无悔算法根据这些估计值来定义一系列策略。我们证明了该方法的正确性,并证明了只要逼近函数能够实现后悔值,方法就能自我学习并收敛到纳什均衡。我们的技术可以被理解为现有大型游戏中抽象工作的原则性推广;在我们的工作中,抽象和均衡都是在自我博弈中学习的。我们在实验中展示了该方法可以在相同资源条件下实现比最先进的抽象技术更高质量的策略。
Nov, 2014
本文介绍了 CFR$^+$ 算法,它通常在计算时间上比以前已知算法快一个数量级或更多,同时可能需要更少的内存。该算法可用于不完美信息博弈中,是近似纳什均衡解的最佳方法之一。
Jul, 2014
本文提出了一种基于乐观的镜像下降的无悔策略算法,可以在非稳态环境下实现 O (sqrt (T)) 的后悔度,并可在变分稳定游戏中收敛到纳什均衡。
Apr, 2021
应用反事实遗憾最小化(CFR)算法于麻将这一不完全信息游戏,通过进行博弈论分析、基于获胜策略的分级抽象,研究了两人麻将的复杂性及其与扑克游戏的差异,此框架可以推广到其他不完全信息游戏。
Jul, 2023