Multiplicative Weight Updates for Extensive Form Games

Recent research in Nash equilibrium (NE) computation in extensive forms games (EFGs), such as poker, show that it is possible to compute strong solutions for two-player zero-sum games via regret minimization in theory and practice. Regret minimization is less well-understood in other classes of EFGs, even with perfect information. We introduce an approach based on converting the EFG into its corresponding normal form game (NFG). This faces two challenges. First, the exponential increase in the size of the NFG representation makes the straightforward use of regret minimization algorithms, like Multiplicative weights update (MWU) variants, on the resulting game impractical. Second, it is not clear how the updates in the normal form version of the game translate to the update in the behavioral strategies of the extensive form. We address these two challenges by introducing Extensive-form Implementation of Normal-form Regret minimization (EINR). Like CFR, it can be applied locally and recursively to the decision nodes in extensive form version. Further, we show a way to extend the EINR implementation to simultaneous move games where each agent knows the state of the game only when all the other players have acted in the game. Experiments on a zero-sum extensive form game and a cooperative simultaneous move game provide a comparison to CFR.