Game-Theoretic Decision Making in Imperfect-Information Games

<p>Designing machines that can reason strategically and make optimal decisions even in the presence of imperfect information and adversarial behavior is a fundamental goal of artificial intelligence. Our understanding of game-theoretic decision-making is fairly advanced in normal-form games, strategic interactions in which all players act once and simultaneously, selecting (possibly randomizing their choice) an action from a pre-determined finite set of possibilities. In contrast, this dissertation focuses on the more realistic imperfectinformation extensive-form games, tree-form decision-making problems in which decision makers can face multiple decisions interleaved with observations about the way previous decisions affected the (partially hidden and possibly adversarial) multiagent environment. </p> <p>This dissertation seeks to close some recognized open problems in this area, and provide solid theoretical and algorithmic foundations for strategic, game-theoretic decision-making in imperfect-information extensive-form games. We highlight the following contributions. </p> <ul> <li>We close the long-standing open question of whether extensive-form correlated equilibria can arise from efficient, uncoupled learning dynamics, establishing unconditional positive results. </li> <li>We settle the complexity of computing extensive-form perfect equilibria in two-player games, a recognized open problem, showing it matches that of Nash equilibrium. </li> <li>We establish learning dynamics with state-of-the-art OT (log T /T) convergence to coarse correlated equilibrium, improving as a corollary known bounds for normal-form games. </li> <li>We uncover a kernelized version of the classic multiplicative weights update algorithm. This algorithm leads to learning dynamics for coarse correlated equilibria with theoretical state-of-the-art dependence on the size of the imperfect-information game. </li> <li>We give fundamental results about the geometry of correlated strategies, identifying new important classes of games where optimal (e.g., welfare-maximizing) correlated solution concepts can be computed in polynomial time, yielding positive complexity results for extensive-form correlation. </li> <li>We give the first learning algorithm with guaranteed convergence to welfare-maximizing correlated solution concepts, and show their state-of-the-art empirical performance. </li> <li>We give state-of-the-art algorithms that enable, for the first time, finding exact tremblinghand refinements of Nash equilibrium in large games with up to half a billion terminal states. </li> <li>We study the problem of computing optimal team strategies in zero-sum adversarial team games, and give state-of-the-art algorithms and positive complexity results for that setting. </li> <li>We give learning dynamics that can incorporate a model of the player to produce strong, human-compatible strategies. These dynamics were a key component in training artificial intelligence for the game of Diplomacy, a 7-player game involving both cooperation and competition with humans. </li> </ul>