Regret Minimization in Extensive-Form Games


Amy Greenwald

Event Details
Thursday, October 28, 2021
Talk:
3:30 p.m., Zoom

Reception:
N/A, N/A

Amy Greenwald, Ph.D.

Professor, Brown University

Abstract

It is well known that regret minimization in repeated normal-form games generates mediated equilibrium behavior.  More specifically, external regret minimization converges to coarse correlated equilibrium, while internal regret minimization converges to correlated equilibrium.  In this work, we explore the much richer space of possible deviations in extensive-form games (external, internal, counterfactual, causal, etc.), and establish the relationships among the mediated equilibria that arise when regret is minimized with respect to these deviation sets.  Additionally, we define a generic algorithm, called extensive-form regret minimization (EFR), which minimizes the regret of a given deviation set chosen from a natural class -- the behavioral deviations -- that subsumes all of the aforementioned classes.  EFR's computational requirements and regret bound scale closely with the complexity of the given deviation set, so we focus on a subset of the class of behavioral deviations, which we call partial sequence deviations, that is both efficient to work with and subsumes previously studied sets.  Experimentally, EFR with partial sequence deviations outperforms existing regret minimization algorithms (e.g., counterfactual regret minimization) when playing games in the OpenSpiel environment.

Joint work with Dustin Morrill, Ryan D'Orazio, Marc Lanctot, James R. Wright, Reca Sarfati, and Michael Bowling

Speaker Bio

Amy Greenwald is Professor of Computer Science at Brown University in Providence, Rhode Island.  Her research focus is on game-theoretic and economic interactions among computational agents, applied to areas like autonomous bidding in wireless spectrum auctions and ad exchanges.  Before joining Brown, Greenwald was a postdoc at IBM's T.J. Watson Research Center, where her "Shopbots and Pricebots" paper was named Best Paper at IBM Research.  Her honors include the Presidential Early Career Award for Scientists and Engineers (PECASE), a Fulbright nomination, and a Sloan Fellowship.  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.