Adversarial combinatorial bandits for imperfect-information sequential games

Abstract:

This talk will focus on learning policies for tree-form decision problems (extensive-form games) from adversarial feedback. In principle, one could convert learning in any extensive-form game (EFG) into learning in an equivalent normal-form game (NFG), that is, a multi-armed bandit problem with one arm per tree-form policy. However, 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 (e.g., last-iterate convergence and predictive regret bounds) from the larger NFG community. In this talk, I will show that the combinatorial structure of EFGs enables simulating the multiplicative weights update algorithm over the set of tree-form strategies efficiently (i.e., in linear time in the size of the game tree instead of the number of tree-form policies) using a kernel trick. This reduction 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.

Bio:

Gabriele Farina is an Assistant Professor in the Laboratory for Information and Decision Systems at MIT EECS, and a member of the Operations Research Center. Before joining LIDS, he spent a year as a Research Scientist at Meta AI. His research interests are at the intersection of operations research, economics, and computation, with a focus on learning and optimization methods for sequential decision-making under imperfect information. He obtained his Ph.D. in computer science from Carnegie Mellon University.