Solving Counterfactual Regret Minimization for Bayesian Games with Continuous Type Spaces

Bayesian games model interactive decision-making where players have incomplete information -- e.g., regarding payoffs of the game or private data on players' strategies/preferences. Thus, players must actively reason and update their beliefs about the game and about other players using the notion of type. Existing work on counterfactual regret (CFR) minimization have shown great success for solving games with complete or imperfect information. However, Bayesian games with continuous type spaces cannot be converted into an equivalent non-Bayesian extensive-form game and remain difficult to solve. To this end, we propose a new Bayesian-CFR minimization algorithm achieving a guaranteed regret bound with respect to Nash Equilibria in Bayesian games with continuous type spaces. In particular, we show that the cumulative regret is continuous with respect to type distribution and thus can be estimated using finite samples in the type space. We then propose a kernel-density estimate that is shown to converge to the true type distribution. These results allow us to efficiently solve Bayesian-CFR minimization with respect to the Bayesian Nash equilibrium. We finally extend this new approach to Bayesian-CFR+ and Deep Bayesian CFR. Experimental results show that our solution significantly outperforms existing methods with minimumexploitability in Bayesian games with continuous type spaces such as modified Texas Hold'em.