Toward Generality: Building Better Counterfactual Regret Minimization for Imperfect Information Games

Abstract

The imperfect information game is a mathematical model that is very useful for modeling interactions in a wide variety of domains, and algorithms that compute the solutions of such games are extremely valuable. Counterfactual regret minimization (CFR) is a very promising algorithmic paradigm for this setting. However, current high-performance CFR algorithms are designed to work well for only a limited subset of games with a small number of available actions, such as poker, and thus have narrow applicability. This thesis discusses the importance of developing more general algorithms to solve mathematical games, justifies why CFR is a promising path forward for creating these solutions, and ultimately addresses this situation by proposing two novel variants of CFR, one of which in particular is especially promising as a general solution. By approximating the value of information to be gained at different times and states of the game, these algorithms match the performance of current best methods on small games while also, for one algorithm, extending to large games by performing faster than current high-performance methods by an exponential factor, serving as an example of a more general solution for imperfect information games.