Timezone: »

 
Poster
Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games
Gabriele Farina · Chung-Wei Lee · Haipeng Luo · Christian Kroer

Thu Jul 21 03:00 PM -- 05:00 PM (PDT) @ Hall E #1210
in Poster Session 3 »
While extensive-form games (EFGs) can be converted into normal-form games (NFGs), doing so comes at the cost of an exponential blowup of the strategy space. So, progress on NFGs and EFGs has historically followed separate tracks, with the EFG community often having to catch up with advances (\eg last-iterate convergence and predictive regret bounds) from the larger NFG community. In this paper we show that the Optimistic Multiplicative Weights Update (OMWU) algorithm---the premier learning algorithm for NFGs---can be simulated on the normal-form equivalent of an EFG in linear time per iteration in the game tree size using a kernel trick. The resulting algorithm, \emph{Kernelized OMWU (KOMWU)}, applies more broadly to all convex games whose strategy space is a polytope with 0/1 integral vertices, as long as the kernel can be evaluated efficiently. In the particular case of EFGs, KOMWU closes several standing gaps between NFG and EFG learning, by enabling direct, black-box transfer to EFGs of desirable properties of learning dynamics that were so far known to be achievable only in NFGs. Specifically, KOMWU gives the first algorithm that guarantees at the same time last-iterate convergence, lower dependence on the size of the game tree than all prior algorithms, and $\tilde{\bigOh}(1)$ regret when followed by all players.
Keywords: T: Game Theory · T: Online Learning and Bandits

Author Information

Gabriele Farina (Carnegie Mellon University)

I am currently a first-year Ph.D. student in the Computer Science Department at Carnegie Mellon University, where I am fortunate to be advised by Tuomas Sandholm. I am part of the Electronics Marketplaces Lab. I mostly work on Kidney Exchange and Algorithmic Game Theory.

Chung-Wei Lee (University of Southern California)
Haipeng Luo (University of Southern California)
Christian Kroer (Columbia University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors