Amy Greenwald, Brown University

Abstract

The convergence of $Phi$-regret-minimization algorithms in self-play to $Phi$-equilibria is well understood in normal-form games (NFGs), where $Phi$ is the set of deviation strategies. This talk investigates the analogous relationship in extensive-form games (EFGs). While the primary choices for $Phi$ in NFGs are internal and external regret, the space of possible deviations in EFGs is much richer. We restrict attention to a class of deviations known as behavioral deviations, inspired by von Stengel and Forges' deviation player, which they introduced when defining extensive-form correlated equilibria (EFCE). We then propose extensive-form regret minimization (EFR), a regret-minimizing learning algorithm whose complexity scales with the complexity of $Phi$, and which converges in self-play to EFCE when $Phi$ is the set of behavioral deviations. Von Stengel and Forges, Zinkevich et al., and Celli et al. all weaken the deviation player in various ways, and then derive corresponding efficient equilibrium-finding algorithms. These weakenings (and others) can be seamlessly encoded into EFR at runtime, by simply defining an appropriate $Phi$. The result is a class of efficient $Phi$-equilibrium finding algorithms for EFGs.

Speaker Bio: Amy Greenwald is Professor of Computer Science at Brown University in Providence, Rhode Island. Greenwald was also a visiting researcher at the Artificial Intelligence Research Center at the Japanese National Institute of Advanced Industrial Science and Technology in Tokyo in 2018-19; a visiting researcher in the Algorithmic Economics Lab at Microsoft Research in New York City in 2015; and a visiting professor at the Erasmus Research Institute of Management in Rotterdam in 2011. She was named a Fulbright Scholar in 2011 (though she declined the award); she was awarded a Sloan Fellowship in 2006; she was nominated for the 2002 Presidential Early Career Award for Scientists and Engineers; and she was named one of the Computing Research Association's Digital Government Fellows in 2001. Before joining Brown University, she worked for a short time as a post-doc at IBM's T.J. Watson Research Center, where her "Shopbots and Pricebots" paper was named Best Paper at IBM Research in 2000. Finally, Greenwald is active in promoting diversity in Computer Science, leading multiple K-12 initiatives in which Brown undergraduates teach computer science to Providence public school students.