With the recent advances in solving large, zero-sum extensive form games, there is a growing interest in the inverse problem of inferring underlying game parameters given only access to agent actions. Although a recent work provides a powerful differentiable end-to-end learning frameworks which embed a game solver within a deep-learning framework, allowing unknown game parameters to be learned via backpropagation, this framework faces significant limitations when applied to boundedly rational human agents and large scale problems, leading to poor practicality. In this paper, we address these limitations and propose a framework that is applicable for more practical settings. First, seeking to learn the rationality of human agents in complex two-player zero-sum games, we draw upon well-known ideas in decision theory to obtain a concise and interpretable agent behavior model, and derive solvers and gradients for end-to-end learning. Second, to scale up to large, real-world scenarios, we propose an efficient first-order primal-dual method which exploits the structure of extensive-form games, yielding significantly faster computation for both game solving and gradient computation. When tested on randomly generated games, we report speedups of orders of magnitude over previous approaches. We also demonstrate the effectiveness of our model on both real-world one-player settings and synthetic data.
For a two-player extensive form game characterized by a game tree with information sets @math and @math for the min and max player respectively, ling2018game show that when @math , the QRE in reduced normal form of the game is equivalent to the solution of the following regularized min-max problem, where @math and @math are the players' strategies in @cite_15 . In the above, @math is the sequence form payoff matrix and @math and @math are the sequence form constraint matrices. @math denotes the possible actions at information set @math , while @math is the action (from the same player) preceding @math . In the sequence form, one works with @math as opposed to probability vectors. These realization plans represent probabilities of choosing a given sequence, while the constraint matrices @math are matrices containing @math and contain parent-child relationships in the game tree. The sequence form is significantly more compact than the normal form while retaining virtually all of its strategic elements.
@cite_15
2136427775
We propose thesequence formas a new strategic description for an extensive game with perfect recall. It is similar to the normal form but has linear instead of exponential complexity and allows a direct representation and efficient computation of behavior strategies. Pure strategies and their mixed strategy probabilities are replaced by sequences of consecutive choices and their realization probabilities. A zero-sum game is solved by a corresponding linear program that has linear size in the size of the game tree. General two-person games are studied in the paper by Kolleret al, 1996 (Games Econ. Behav.14, 247–259).Journal of Economic LiteratureClassification Number: C72.