Colloquium: Amy Greenwald
Thursday, October 28, 2021
3:30-4:30 CST
Via Zoom: https://unl.zoom.us/j/98021741789?pwd=Ykk2WXBWUEhJaXNKNGcrNUg1VjhZQT09
Meeting ID: 980 2174 1789
Passcode: cse
Amy Greenwald
Professor
Computer Science
Brown University
"Regret Minimization in Extensive-form Games"
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
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.