通过步长不对称性提升博弈求解鲁棒性,解决预测不准导致的收敛变慢问题。
Faster Game Solving via Asymmetry of Step Sizes
- 引入更新步长的不对称设计,缓解预测误差对收敛的影响。
- 在5个标准博弈和2个德州扑克子任务中均优于PCFR+,收敛更快更稳定。
- 方法简单易用,可推广至其他CFR算法,仅需一行代码修改。
计策反悔最小化(CFR)算法广泛用于求解两人零和不完美信息扩展形式博弈(IIG)的纳什均衡。其中,预测型CFR+(PCFR+)凭借预测机制在多数游戏中实现了极快的实证收敛速度。然而,当预测不准确时,其收敛性能会显著下降,导致某些博弈上表现不稳定。为此,本文提出非对称型PCFR+(APCFR+),通过在隐式与显式累积反悔值更新中采用自适应步长不对称性,降低预测误差对收敛的影响。我们给出了理论分析,证明了该设计的合理性。据我们所知,这是首次提出步长不对称性这一简单而新颖的技术,有效提升了PCFR+的鲁棒性。为降低实现复杂度,我们进一步提出简化版APCFR+(SAPCFR+),使用固定步长不对称性,仅需对原始PCFR+做一行代码修改即可。在五个标准IIG基准和两个头对头无限制德州扑克子任务上的实验表明:(i) APCFR+与SAPCFR+在多数测试游戏中均优于PCFR+;(ii) SAPCFR+的实证收敛速度与APCFR+相当;(iii) 本方法可推广至其他CFR算法,如折扣型CFR(DCFR)。
原文摘要 · Abstract (English)
Counterfactual Regret Minimization (CFR) algorithms are widely used to compute a Nash equilibrium (NE) in two-player zero-sum imperfect-information extensive-form games (IIGs). Among them, Predictive CFR$^+$ (PCFR$^+$) is particularly powerful, achieving an exceptionally fast empirical convergence rate via the prediction in many games.However, the empirical convergence rate of PCFR$^+$ would significantly degrade if the prediction is inaccurate, leading to unstable performance on certain IIGs. To enhance the robustness of PCFR$^+$, we propose Asymmetric PCFR$^+$ (APCFR$^+$), which employs an adaptive asymmetry of step sizes between the updates of implicit and explicit accumulated counterfactual regrets to mitigate the impact of the prediction inaccuracy on convergence. We present a theoretical analysis demonstrating why APCFR$^+$ can enhance the robustness. To the best of our knowledge, we are the first to propose the asymmetry of step sizes, a simple yet novel technique that effectively improves the robustness of PCFR$^+$. Then, to reduce the difficulty of implementing APCFR$^+$ caused by the adaptive asymmetry, we propose a simplified version of APCFR$^+$ called Simple APCFR$^+$ (SAPCFR$^+$), which uses a fixed asymmetry of step sizes to enable only a single-line modification compared to original PCFR$^+$.Experimental results on five standard IIG benchmarks and two heads-up no-limit Texas Hold' em (HUNL) Subagems show that (i) both APCFR$^+$ and SAPCFR$^+$ outperform PCFR$^+$ in most of the tested games, (ii) SAPCFR$^+$ achieves a comparable empirical convergence rate with APCFR$^+$,and (iii) our approach can be generalized to improve other CFR algorithms, e.g., Discount CFR (DCFR).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。