Efficient Regret Minimization Algorithm for Extensive-Form Correlated
  Equilibrium
  Self-play methods based on regret minimization have become the state of the
art for computing Nash equilibria in large two-players zero-sum extensive-form
games. These methods fundamentally rely on the hierarchical structure of the
players' sequential strategy spaces to construct a regret minimizer that
recursively minimizes regret at each decision point in the game tree. In this
paper, we introduce the first efficient regret minimization algorithm for
computing extensive-form correlated equilibria in large two-player general-sum
games with no chance moves. Designing such an algorithm is significantly more
challenging than designing one for the Nash equilibrium counterpart, as the
constraints that define the space of correlation plans lack the hierarchical
structure and might even form cycles. We show that some of the constraints are
redundant and can be excluded from consideration, and present an efficient
algorithm that generates the space of extensive-form correlation plans
incrementally from the remaining constraints. This structural decomposition is
achieved via a special convexity-preserving operation that we coin scaled
extension. We show that a regret minimizer can be designed for a scaled
extension of any two convex sets, and that from the decomposition we then
obtain a global regret minimizer. Our algorithm produces feasible iterates.
Experiments show that it significantly outperforms prior approaches and for
larger problems it is the only viable option.
