Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors first introduce a new equilibrium concept: K-EFCE in extensive-form games. Then the authors propose sample-efficient regret-minimization based algorithms to learn the equilibrium in both full-information and bandit feedback. When K=1 under the bandit feedback, this is the first sample-efficient algorithm to learn EFCE. 
strengths_and_weaknesses: To me it seems like the most important contribution of this paper is the first sample-efficient algorithm to learn EFCE under the bandit feedback. On the other hand, I don't really get why the authors introduce K-EFCE, a generalization of EFCE. Intuitively, we can definitely consider this generalization, but I don't know if the generalization induces interesting concepts or properties and the contribution I mentioned can completely hold without this generalization if I understand correctly.  

In terms of algorithms, it directly adapts WRHedge for the online learning literature, which is quite reasonable but I think this may limit the novelty of this paper. In the bandit setting, it looks like the balanced sampling idea also comes directly from another paper. Another weakness of this paper is probably the lack of experimental evaluations of the algorithms. 
questions: 1. While this is not specific to this paper, I think POMGs are much more general than the authors introduce. Specifically, a POMG, like a POMDP, should have an observation model $O(\cdot|s,a)$, which is a conditional probability given state s and action a. In the paper, the authors simplify this to a partition of the state space, which is sufficient for IIEFGs but I think POMGs are more than that and there is no need to bring up this term. 

2. Why is K-EFCE is an interesting extension to EFCE? Without this extension, can the reducing algorithms be further simplified? 

limitations: N/A
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the problem of learning extensive-form correlated equilibria (EFCE) in imperfect-information extensive-form games. In particular, the paper introduces a new notion of EFCE, called K-EFCE, in which a player does not stop receiving recommendation right after the first time they deviate, but they continue to receive them up to their K-th deviation. The paper studies the problem of learning K-EFCE, and it provides sample-efficient algorithms for both the full feedback and the bandit feedback settings.
strengths_and_weaknesses: ORIGINALITY

(+) To the best of my knowledge, this is the first paper that proposes sample-efficient no-regret learning dynamics that converge to EFCEs under the bandit feedback model.

QUALITY

(+) As far as I am concerned, the results in the paper are correct, though I did not check all the proofs in the details.

(-) I only have one major concern about the formalization of imperfect-information extensive-form games with perfect recall. In particular, the authors claim that in order to have perfect recall it should be possible to partition the information sets of one player according to the tilmestep they belong to. However, the fact that the game is perfect recall does not necessarily imply that the states in the same infoset all refer to the same timestep of the game. Indeed, this is not the case whenever the game is not timeable. As far as I am concerned, the results in the paper rely on the assumption that the game is timeable, which is a more restrictive assumption than perfect recall only. If this is correct, this would somehow limit the impact of the results. See the following paper for a reference on timeability of extensive-form games:

“Jakobsen, S. K., Sørensen, T. B., & Conitzer, V. (2016, January). Timeability of extensive-form games. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (pp. 191-199).”

CLARITY

(+) The paper is well written and all the concepts are well presented.

(-) My only concern regarding the presentation is that too many results are in the appendix, which renders the main paper (perhaps too much) high level in terms of technical details.

SIGNIFICANCE

(+) The problem of learning EFCEs is receiving considerable attention over the last few years from the algorithmic game theory community and beyond. Thus, this paper could be of interest for a considerable portion of the NeurIPS community (as also testified by the Best Paper Award at NeurIPS 2020).

questions: 1) Can you please address my concern in the second point of the quality assessment?
---------- AFTER AUTHORS' RESPONSE ----------
The authors clarified my concerns about the applicability of their algorithms to non-timeable perfect-recall games. As a result, I raised my score to 7 (from an original score of 6).
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper has 3 main contributions. First, the authors propose a generalization of extensive-form correlated equilibrium (EFCE), known as K-EFCE. In this generalization, players continue to receive recommendations even after they have deviated from their recommendations (received at each infoset, just like regular EFCE) for up to K deviations. K-EFCE encompass a number of common equilibrium concepts. A 1-efce is just a regular EFCE, while a 0-EFCE is a normal-form CCE.  The second key contribution is a self-play algorithm to compute K-EFCE, which the authors call K-EFR. The third contribution is the a variant of K-EFR that can handle bandit feedback. The authors claim that this is the first algorithm for learning EFCE from bandit feedback.
strengths_and_weaknesses: Generally, I felt there was too much content to follow and feels more suitable for a journal. In particular, the part on bandit feedback feels rather cramped (though it is an important contribution in its own right). Given the authors’ claim that K-EFR outperforms [11], [20], I felt it would be good to give a more detailed sketch on the key differences between these methods—-this is currently done in lines 233-240, which (at least to me) was rather opaque. This should help to make the paper more accessible.

Other than that, the paper seems good, except for the aforementioned points about it not being as accessible to readers not already familiar with EFR.

Small quips:
In the definition of Type-I rechistories, $\mathcal{A}_i^{h-1}$ is not defined.

Note: The paper is entirely theoretical with many pages of proof. I did not go through all the proofs, especially those in the appendix. I am not familiar with the state of the art EFCE solvers, and am unable to definitively comment on the authors’ claims with regard to comparison with other works.

questions: 1. I would have liked a discussion on how K-EFCE could be implemented. In the original EFCE paper by von Stengel, EFCEs were implemented by means of sealed recommendations, even though the more popular formulation today is based on [13, 16], which use an equivalent formulation based on trigger sequences. How can a mediator (practically) achieve a K-EFCE where K > 1?

2. The authors use POMG as their choice of framework, rather than extensive form games. Is there a difference between the 2, given that the POMG is restricted to be tree structured?


limitations: -
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper's main contributions are threefold:

1. The notion of K-EFCE is defined. It is a generalization of EFCE, whereby the mediator (correlation device) can condition their recommendation based on the number of deviations of each player, which can be any number between 0 and K. After K deviations have been reached, the mediator will stop issuing recommendations. K-EFCE is a natural generalization of EFCE: in fact, EFCE is simply a 1-EFCE.

2. The paper shows that, within the *full-information* setting, an $\epsilon$-approximated K-EFCE can be computed by means of uncoupled no-regret dynamics after running $\tilde O(A^K / \epsilon^2)$ iterations where $A$ is the maximum number of player actions (equivalently, each player is guaranteed to cumulate $\tilde O(A^K \sqrt T)$ regret after $T$ iterations).

3. The paper shows that, withing the *trajectory-bandit setting*, an $\epsilon$-approximated K-EFCE can be computed by means of uncoupled no-regret dynamics after running $\tilde O(A^{K+1} / \epsilon^2)$ iterations where $A$ is the maximum number of player actions (equivalently, each player is guaranteed to cumulate $\tilde O(A^{K+1} \sqrt T)$ regret after $T$ iterations).

strengths_and_weaknesses: I want to start by saying that I think the paper represents interesting, well-executed, high-quality work. Despite the very tight page limits, the body is well-organized and easy to follow. The appendix is also well-organized, and contains a trove of additional interesting results---I especially enjoyed browsing through appendix C.

Significance: I believe the paper contributes interesting results that fit well within the current research trend around extensive-form games. For example, learning EFCE with bandit feedback is a natural and interesting question.

Originality: The extension from EFCE to K-EFCE is interesting conceptually, and like I said I believe the paper is well executed and addresses relevant questions. In terms of significance, my impression is that the paper does not introduce any groundbreaking tool in the space. Rather, it fundamentally combines several expected existing techniques, such as balanced exploration policies and standard decompositions of Phi-regret for EFCE, obtaining results that were perhaps easy to guess for an expert in the field. I want to be clear that I am not saying that the paper is trivial---the authors put together and master several specialized tools, creating a paper that I expect will be very well received in the community. 

Clarity and quality: the paper is very well executed and polished, both in the body and in the appendix. There is only one point that I found was slightly confusing: on lines 40-41, the bandit feedback setting is introduced as the opposite of the case in which "the full game is known". Just to be clear: your bandit algorithm still requires that at least the *decision space* (treeplex) of each player be known so that the balanced exploration strategy can be instantiated, correct? So, this bandit algorithm is not akin to, say, that of the cited works by Farina and Sandholm ("Model-Free Online Learning...") or Kozuno et al. ("Model-free learning"), which instead address both an unknown structure *and* bandit feedback on the utilities?

Minor nits:
- Abstract, line 9: I would avoid "more generalized" in favor of either "generalized" or "more general".
questions: 1. Can you please respond to my questions in the "Clarity and quality" assessment above?

2. Currently, the main factor driving my (positive!) score is the originality of the work. While I also gave a good look in the appendix, it is possible---especially given the volume of a 60-page paper---that I might have missed some particularly innovative analysis tool that was used in this paper. If that's the case, please push back on my assessment above.

3. Can you please confirm that your algorithm cannot be used in adversarial bandit-feedback settings (as it requires exploring the opponent for several episodes assuming the opponent's strategy does not change)?
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: Reviews on this paper are uniformly positive, and all reviewers feel that it is
an interesting set of results. One minor criticism is that  some reviewers felt the presentation
could be improved, and the authors should try to address this for the camera ready.

confidence: Certain
Decision: Accept