Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors consider the problem of finding an approximate extensive-form correlated equilibrium (EFCE) of a finite general-sum multiplayer extensive-form game under the perfect recall assumption. They propose an accelerated version via optimism of the algorithm by Farina et al. (2019a). Precisely it combines the framework by Gordon et al. (2008) for \Phi-regret minimization with the framework of optimistic regret minimization adapted to extensive form game. They prove that when all agents play T repetitions of the game according to the proposed algorithm the correlated distribution of play is an O(T ^−3/4 )-approximate EFCE where O hides quantities polynomial in the size of the game. The main technical point to obtain this result is to characterize the stability of certain fixed point strategies through a refined perturbation analysis of a structured Markov chain. They also provide preliminary experiments on simple two or three-players games.
main_review: The paper is well written (see specific comments and the concern below). The proofs seem correct (I did not check the appendices in detail). Providing an accelerated convergence rate for multiplayer extensive form games (and in particular proving the counterpart of what is known for normal-form game) is a valuable contribution. My main concern is that in the current form the paper is difficult to read. In particular, the proposed algorithm should be at least described in the main text (see main comments). Furthermore, some parts should be better introduced, e.g. the \Phi-regret minimization framework (see specific comments).

Main comments: 

-It is hard to find what is the final algorithm mentioned in Theorem 1.1 by reading the main text and even by looking at Appendix B. Thus without the big picture Section 3 looks a bit like a collection of unrelated technical results.

-Could you state clearly the complexity of the proposed algorithm (it seems that it scales at least quadratically with the size of the game?) and polynomial dependence on the size of the game hidden in Theorem 1.1. This is important since usually the size of the game is very large.
 
Specific comments:
-P1 Th 1.1: Is there any lower bound on the rate? For example, is there hope to improve the rate to O(1/T) as for two players? You should also clearly refer to the description of the algorithm in the paper.

-P3 End of section 1: Why normal-form coarse correlated equilibria is solution concept much less appealing than EFCE?

-P4, below (1): typo \cJ^{(i)}

-P5, Theorem 2.5: \psi^(i)-regret is not defined at this point.

-P6, Definition 3.1: does the point x_t necessarily coincide with the point played by the regret minimizer algorithm? Ok maybe you should describe the framework of Gordon et al. (x_t is the fixed point of a \phi_t obtained by another regret minimizer on an auxiliary task?).

-P6, Theorem 3.2: Maybe you should define clearly what you mean by a regret minimizer R_\Phi
for the set of transformation \Phi.  

-P6, end of Section 2: could you detail what you mean by entropic regularizer on \cX?

-P9, end of Section 3: Could point out precisely where is the final algorithm in Appendix B. 

-P9, Section 4: At this point, it is not clear at all what the OMWU algorithm is. Did you also experiment on Leduc Poker? Because it is usually the setting where there is a gap between multiplicative weights type of algorithms and RM+ (ith alternating updates). 

-P13, top of the page: \cJ is in the introduction the set of information set. Using the same notations for the sequential decision making setting is a bit confusing. Could you 

-P13, (13): is an observation node always followed by an action node?

-P16, above (24): typo

-P18, above (32): norm 1
summary_of_the_review: See Main Review
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proves a faster no-regret learning dynamics for extensive-form correlated equilibrium (EFCE) in multiplayer general-sum imperfect-information extensive-form games. When the game is played for T repetitions according to the accelerated dynamics, the correlated distribution of play for all players is an $O(T^{-3/4})$-approximated EFCE. This improves upon the previous best rate which is $O(T^{-1/2})$ for extensive-form games.
main_review: ## Strengths
The problem that the authors considered is an important problem for no-regret learning dynamics in games. Compared to existing literature on accelerated learning dynamics for correlated equilibria (CE) or coarse correlated equilibria in normal-form games, the convergence rate for extensive-form game is relatively less understood. 

This paper shows an improved convergence rate to extensive-form correlated equilibrium (EFCE): when the game is played for T repetitions, the correlated distribution of play for all players is an $O(T^{-3/4})$-approximated EFCE, which improves upon the previous best rate $O(T^{-1/2})$. To me this is a good and important theoretical contribution to the existing literature.

A main conceptual contribution is to establish a connection between the optimistic regret minimization to $\phi$-regret minimization problem. A main technical contribution is a characterization of the stability of certain fixed point strategies through a refined
perturbation analysis of the structured Markov chain. Other than that the proof utilized previous results in Farina et al.
(2021a), which casts the convergence to an EFCE as a $\phi$-regret minimization problem, and existing framework on optimistic regret minimization.

Numerical simulations are provided in support of the theoretical results.

## Weakness

First I think the summary of related works on no-regret learning dynamics for normal-form games are missing some most recent results. For example in [Daskalakis, Fishelson, Golowich, Near-Optimal No-Regret Learning in General Games, 2021] it is shown that one can achieve a O(1/T) convergence rate to coarse correlated equilibrium in multi-player general-sum games. Secondly I don't see much discussion on the technical difficulty of why the paper's framework could not be applied to normal-game. Given the many other existing rates for normal-games, it would be good to add more details on this point.

Regarding the technical contributions, the main concern is about novelty given that the main framework is built on previous results in Farina et al. (2021a) which casts the convergence to an EFCE as a $\phi$-regret minimization problem, and existing framework on optimistic regret minimization as in Gordon et al. (2008).



summary_of_the_review: Overall I think this paper provides nice theoretical contribution with an improved rate for no-regret learning dynamics that converge to extensive-form correlated equilibrium. The paper is well-written. However currently the related work is missing some recent relevant results, and on the technical contribution side there should be some more details differentiating the new results and existing frameworks.

Post rebuttal update: I have read the authors' response and will keep the original score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents an uncoupled no-regret learning dynamic provably converging to the extensive-form correlated equilibrium in general-sum n-player extensive-form games. The central claim of the paper is that the introduced approach results in the convergence rate of O(T^{-3/4}) to the equilibrium and hence supersedes the recent algorithm of Farina et al. which converges with rate O(T^{-1/2}). To achieve this, the authors follow the construction presented by Farina et al., but employ stable and predictive regret-minimizers from the class of Optimistic Follow the Regularized Leader algorithms instead of CFR/regret-matching used by Farina et al. The main portion of the paper is then dedicated to the theoretical analysis of the dynamic to arrive at the desired convergence rate. To this end, the authors first study how to construct stable-predictive regret minimizers for the convex hull of the set of trigger deviation functions for a given sequence, and consequently also for the composite regret minimizer. This enables them to bound the overall incurred regret. The construction also requires that every trigger deviation function admits a fixed point that is efficiently computable by a stable oracle. The stability is hence of the authors' interest in the second part. The paper is concluded by an experimental evaluation of the algorithm that shows that it is superior or performs on par with the algorithm of Farina et al. instantiated with regret matching or vanilla multiplicative weights updates.
main_review: Computing game-theoretic solution concepts that capture the idea that the players may coordinate their strategies based on external signals has become an increasingly active field in recent years, whether in the form of correlated equilibrium, team correlated equilibrium, or other related concepts. Correlation has several attractive properties, with efficient computability among the most prominent ones and enough applications to justify further research in this direction. Designing uncoupled dynamics to approximate an extensive-form correlated equilibrium faster is hence definitely a problem worth studying. The authors' result is interesting, and I am convinced that the presented experimental results provide enough evidence to support their claims. I went through some of the proofs included in the appendix, and I could not find any obvious mistakes. The authors cite the relevant literature, and I also appreciate that they mention that alternation and linear averaging were left out from the experiments because of their lack of guarantees, which I find to be a valid argument. I have a few concerns as well, though.

Perhaps the main one relates to the presentation of this work. Explaining the problem and techniques the authors study requires a lot of background. Already in the introduction, the authors mention different kinds of regrets and other fundamental notions without describing the main ideas behind these concepts or how they relate in general. This may make some readers confused. Several times I also found myself wondering how different claims relate together, e.g., why are "certain Markov chains" important, how are they used in the proofs, and what their stationary distributions relate to. This makes it difficult to follow the authors' thought processes, and the reader is forced to rely on the explanations in the appendix, which contradicts the idea of the main text being self-contained.

The work is also highly technical, which is an inherent problem of the framework of sequential decision-making. The problem is further aggravated by the plethora of notation, including upper and lower indexing. I believe a table of symbols similar to Table 1 in Farina et al. 2021a would be convenient. Moreover, the work is absolutely void of examples, despite containing many definitions and advanced concepts. The authors may consider providing some to help the readers familiarize themselves with the introduced notions.

The main result the authors present is indeed interesting. Still, after reading through the appendix, my impression is that many of the constructions and proofs (with the important exception of Lemma B.7) are directly inspired by previous works, especially the papers by Farina et al. May the authors elaborate what were the main difficulties they encountered when extending the results into the framework of optimistic regret minimizers?

Farina et al. also define approximation of extensive-form correlated equilibrium using regret minimizers on the set of deterministic sequence-form strategies (Theorem 3.7 in Farina et al. 2021a), and moving to the set's convex hull (i.e., mixed strategies) will result in a guarantee with high probability only. According to Section 3.1, the sequence-specific regret minimizers are constructed from the regret minimizers for the mixed strategies (Q^i_j). Should not the approximation mentioned, e.g., already in the abstract, be hence also probabilistic?

I understand that using the technique of Chen and Peng would result in a non-polynomial degradation in stability. May I ask how this would affect the overall rate of convergence to extensive-form correlated equilibrium and computational complexity of the algorithm computing fixed points? More specifically, would the convergence rate contain game-specific exponential constants and otherwise be similar, or would it change completely?

Lastly, I wonder how fast one iteration of the OMWU-based dynamic is, compared to the alternatives (regret-matching+ and vanilla MWU)?

Nits:
The proof of proposition 3.3 is missing a reference (it reads "??").
Equation 45 is missing a comma.
At the beginning of Section 3, should not (2) be 2) instead?
The word "coarse" is missing in Corollary C.7.

summary_of_the_review: Overall, I am slightly in favor of accepting this work. The problem is worth studying, the main result the authors present is exciting, and the empirical results support their claims. My main concerns relate to the presentation of this work. The text is extremely technical and notation-heavy, and I believe many concepts should be more adequately explained for a reader less familiar with no-regret learning to understand this work. The manuscript also completely lacks any examples. I remain unsure if a better exposition is possible given the ICLR's strict page limit and if this work would not be better suited for journals or conferences that allow longer narratives.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Previous work has identified uncoupled, regret-based dynamics that converge to extensive-form correlated equilibria in extensive-form games at a rate of O(T^{-0.5}) where T is the number of repetitions of the game.  This paper provides a new uncoupled, regret-based dynamics that achieves O(T^{-0.75}).  It does so by combining analysis techniques for regret-based dynamics that have shown such accelerated convergence in other settings with the framework used to achieve the  O(T^{-0.5}) rate.  Technical contributions in realizing this combination include a new analysis of a relevant Markov chain.  A limited set of experiments confirms faster convergence relative to prior approaches.
main_review: On the positive side the improved convergence rate is a clear theoretical contribution and the experiments suggest that a practical implementation of these techniques is possible.  On the negative side, as discussed in detail below, the techniques used to achieve it essentially boil down to combining the approach of Farina et al. 2021a with a line of work on slowly-changing regret minimizers which have been shown to achieve accelerated rates in a number of settings, so the acceleration here is not terribly surprising.  While such a combination may require substantial novel insights, the exposition does not currently make it clear what those are.

More broadly, the positioning of the contribution of this paper relative to related work needs to be clearer.  I will discuss several particular relationships which do not appear to be sufficiently clearly explained, and for some of them this appears to expose weaknesses in the paper.

Farina et al. 2021b [F21b].  This paper achieves a O(T^{-0.5|) rate to a weaker solution concept (EFCCE).  However, relative to EFCE it avoids an expensive computation at each step.  This paper is used as a baseline in the experiments Section 4, and thus has two differences (slower rate and different solution concept).  The discussion omits the second difference and appears to discuss it as converging to an EFCE.  So I am left wondering which factor is responsible for the worse performance in the experiments.  Furthermore, Appendix C of the supplemental materials (which does not appear to be referenced in the main text) discusses how the result of this paper can be combined with those of [F21b] to get accelerated convergence to EFCCE.  Give this, I am not sure why the experiments do not isolate the two factors (rate vs solution concept) and which version of the algorithm in the paper the experiments are actually testing (i.e. do they actually use the EFCCE version?).

The line of work on distance-generating functions (Hoda et al. 2010, Kroer et al. 2020, Farina et al. 2021c).  These techniques have achieved O(T^{-1}) in other settings but are mentioned only briefly.  Why not adopt these techniques rather than the ones that lead to O(T^{-0.75})?  I don’t a-priori see why they should be incompatible with the framework from Section 3 and if they can be achieved it makes the headline result of O(T^{-0.75}) less impressive unless there are other reasons to prefer this approach.

Farina et al. 2021a [F21a].  While this work is referenced throughout the paper, the technical approaches share so much overlap that I have some difficulty disentangling where exactly the technical contributions in this paper are.  In particular, I am not precisely clear what constitutes the “stable predictive \Phi template” referred to as being of independent interest.  [F21a] appear to use the same framework based on Gordon et al. 2008 which incorporates an arbitrary regret minimizing dynamics.  So it would be helpful to call out which specific results require new insights to apply it to a stable-predictive version (which have been explored in several previous works, although perhaps mostly for normal-form games).  The one result specifically mentioned is Lemma 3.9, and I could not find a proof of it in the supplementary material (there does seem to be a proof of the reference Corollary B.9 but it builds on different results, although they appear at least somewhat similar in spirit).  As a result I have a hard time evaluating the significance of the technical contribution of this paper.  Finally, as a minor note I am a bit confused about the status of [F21a].  This paper describes it simply as “very-recent follow-up work” to Celli et al. 2020, while [F21a] describes itself as an extended version of that paper in a note on the first page.

summary_of_the_review: While I appreciate the headline theoretical contribution, given my concerns I am not convinced that this version of the paper makes a sufficient novel technical contribution.  One possibility is that it does but the technical exposition needs to be improved to more clearly highlight the contribution.  Another path forward, since this paper is heavily based on the approach of [F21a], improves its results, and that paper appears to be still unpublished, would be to consider whether the authors of {F21a] would be amenable to merging the papers.  A third possibility to extend the results and demonstrate the power and flexibility of the approach would be to show that it can also be adapted to work with the line of work which uses dynamics based on carefully-designed distance-generating functions to achieve an O(T^{-1}) bound.
review_title: null

Meta-review: This paper builds upon existing works to prove that learning (correlated) equilibrium can be fast, i.e., faster than \sqrt{n} even in extensive form games.

Three reviewers are rather lukewarm, and one reviewer is more positive (but seems less confident in his score). The two major criticisms is that this paper is very difficult to read and that the results might seem rather incremental with respect to the literature.

I tend to agree with both points but the paper still as merits: the reason is that extensive form games are intrinsically way harder than normal form games and they more or less all have a burden of notations. We agreed  that the authors actually did some efforts to make it fit within the page limit. but another a conference or a journal would have been better suited than ICLR.

Our final conclusion is that the result is interesting yet maybe not breathtaking for the ICLR community; we are fairly certain that another venue for this paper will be more appropriate and that it will be accepted in the near future (I can only suggest journals based on the large amount of content and notations, such as OR, MOR, or GEB - yet, conferences such as EC should be more scoped too) . It does not, unfortunately, reach the ICLR bar.
Decision: Reject