Timezone: »

 
Poster
Abstracting Imperfect Information Away from Two-Player Zero-Sum Games
Samuel Sokota · Ryan D'Orazio · Chun Kai Ling · David Wu · Zico Kolter · Noam Brown

Thu Jul 27 04:30 PM -- 06:00 PM (PDT) @ Exhibit Hall 1 #529
in Poster Session 6 »

In their seminal work, Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This insight underpins sound solvers and decision-time planning algorithms for common-payoff games. Unfortunately, a naive application of the same insight to two-player zero-sum games fails because Nash equilibria of the game with public policy announcements may not correspond to Nash equilibria of the original game. As a consequence, existing sound decision-time planning algorithms require complicated additional mechanisms that have unappealing properties. The main contribution of this work is showing that certain regularized equilibria do not possess the aforementioned non-correspondence problem---thus, computing them can be treated as perfect-information problems. Because these regularized equilibria can be made arbitrarily close to Nash equilibria, our result opens the door to a new perspective to solving two-player zero-sum games and yields a simplified framework for decision-time planning in two-player zero-sum games, void of the unappealing properties that plague existing decision-time planning approaches.

[ PDF]  [ Poster] 

Author Information

Samuel Sokota (Carnegie Mellon University)
Ryan D'Orazio (Mila, Université de Montréal)
Chun Kai Ling (School of Computer Science, Carnegie Mellon University)
David Wu (Facebook)
Zico Kolter (Carnegie Mellon University / Bosch Center for AI)
Noam Brown (OpenAI)

More from the Same Authors