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