Approximating Equilibrium in Extensive Games with Imperfect Recall via Counterfactual Regret Minimization

Abstract

This paper aims to study Nash Equilibrium, a game theory solution concept, in the case of extensive-form games, where traditional methods of linear programming for equilibrium computation are difficult to apply due to exponentially increasing linear constraints. Recent literature focuses on approximating the upper bound of Nash Equilibrium through a technique called Counterfactual Regret Minimization. In particular, the Monte Carlo Counterfactual Regret Minimization (MCCFR) technique utilizes sampling to effectively minimize per-iteration regret in a large game tree. However even MCCFR has obvious limitations that prevent the algorithm from being suitable in the case of extensive games with imperfect recall. Therefore, in this study, a variant of the Outcome-Sampling MCCFR algorithm, which we call the Average-Outcome-Sampling MCCFR algorithm, is designed to account for imperfect recall, and its performance is tested through a classic extensive-form game called Goofspiel. The algorithm, though it fails to minimize counterfactual regret relative to the case with perfect recall, generates an average behavioral strategy with performance that is comparable to that of perfect recall. Thus, these results suggest that the effects of imperfect recall are not so significant at least for two-player smaller-sized games.