AutoCFR: Learning to Design Counterfactual Regret Minimization Algorithms

Authors

  • Hang Xu Institute of Automation, Chinese Academy of Sciences School of Artificial Intelligence, University of Chinese Academy of Sciences
  • Kai Li Institute of Automation, Chinese Academy of Sciences School of Artificial Intelligence, University of Chinese Academy of Sciences
  • Haobo Fu Tencent AI Lab
  • Qiang Fu Tencent AI Lab
  • Junliang Xing Institute of Automation, Chinese Academy of Sciences School of Artificial Intelligence, University of Chinese Academy of Sciences Tsinghua University

DOI:

https://doi.org/10.1609/aaai.v36i5.20460

Keywords:

Game Theory And Economic Paradigms (GTEP)

Abstract

Counterfactual regret minimization (CFR) is the most commonly used algorithm to approximately solving two-player zero-sum imperfect-information games (IIGs). In recent years, a series of novel CFR variants such as CFR+, Linear CFR, DCFR have been proposed and have significantly improved the convergence rate of the vanilla CFR. However, most of these new variants are hand-designed by researchers through trial and error based on different motivations, which generally requires a tremendous amount of efforts and insights. This work proposes to meta-learn novel CFR algorithms through evolution to ease the burden of manual algorithm design. We first design a search language that is rich enough to represent many existing hand-designed CFR variants. We then exploit a scalable regularized evolution algorithm with a bag of acceleration techniques to efficiently search over the combinatorial space of algorithms defined by this language. The learned novel CFR algorithm can generalize to new IIGs not seen during training and performs on par with or better than existing state-of-the-art CFR variants. The code is available at https://github.com/rpSebastian/AutoCFR.

Downloads

Published

2022-06-28

How to Cite

Xu, H., Li, K., Fu, H., Fu, Q., & Xing, J. (2022). AutoCFR: Learning to Design Counterfactual Regret Minimization Algorithms. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5244-5251. https://doi.org/10.1609/aaai.v36i5.20460

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms