Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors demonstrate a method to perform unsupervised amortized optimization of game solvers that seemingly leads to sharp speedups. They also design an architecture that respects the equivariances of the problem and perform ablations demonstrating that this is useful. 
strengths_and_weaknesses: Strengths:
- The technique seems useful and I could imagine it being helpful in MARL settings
- That the objective is "unsupervised" (i.e. you don't need the actual optimal strategy) is very neat
- The invariant architectures should be useful for other attempts at this problem.

The main weaknesses are in the writing of the paper, I highlight some problems below:

- The superscripts in Line 133 come out of nowhere; for example, why does $\hat{\sigma}$ have the $L_1$ norm as a superscript? I’m not sure what these superscripts mean on a first read.
- Someone from an adjacent field might not know what an NxN game is, I think it’d be worth explaining.
- The citation links are broken and link back to the title instead of to the actual citation
- Are Table 1 and 2 actually included in this paper? I see them in the supplement, are those the same tables you’re referring to in the paper body?
- On figure 4 it’s not clear what “left” and “right” mean
- In Figure 4 caption it’s worth pointing out (as you do in the text) that the arms correspond to worst, mean, best
- The term MECCE is introduced but not defined anywhere in the main paper
- The stack function in Equation 12 does not appear to be defined in the main text
- The equivariant architectures section was quite hard to follow; it is unclear what the underlying logic behind each of the transformations is. I would love to see a more expanded version of this section in the appendix or with the extra page if the paper is accepted.
- Equivariant is misspelled on line 193
- Figure 4 is somewhat hard to read where the bars overlap, you might consider using different colors and making the arm sizes of one of the bars different than the other?
questions: - Your solver gap has not asymptoted on any of the graphs. Is there a small experiment you can run to check if they do asymptote in any reasonable number of iterations? (I am not asking you to run this experiment to improve review score) This would make clear if there’s significant progress to be made or if simply continuing to run your solver training would lead to continual improvement.
- Is lower-case w (used throughout section 4.4) defined anywhere in the text?
- Is there a section comparing the run-time of conventional solvers to your method? If not, this would be neat to include.
- What is “naive payoff sampling” in the ablations?
limitations: Yes.
review_title: null

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: This paper aims to create a method for training NNs to solve for NE, CE, and CCE across a set of games with a fixed action space for each player.  This is achieved through considering the dual formulation of the LP resulting from each of these equilibria concepts, and preforming gradient decent on the NN given random games in with that action space size so that the strategies the network produce satisfy the constraints of the LP.
strengths_and_weaknesses: **Strengths:**
The strengths of this paper are 
* The novel (to my knowledge) idea to train solvers of games in the dual LP space rather than the primal.  This is an interesting approach, which could be promising and should be explored.
* The idea to train one solver for all games of a given shape rather than solving each game on-by-one
* Equivariant networks and payoff invariances which are shown to improve performance.

**Weaknesses:**
The main weaknesses I see are:
* The motivation that other approaches in the space cannot solve for CE seems weak since it seems easy to adapt PSRO or CFRM to such a class.
* The scaling argument seems weak as the approach of training on all games of a give size seems much much more difficult computationally than solving a particular game in that class.
* If the argument is that this method is scalable, then I would expect experiments that run on much larger than 8 by 8 games.

More broadly, as this paper is taking the approach of solving all N by N games at once, but most of the payoff matrices in this space are ones which we don't use in practice, I would expect an evaluation on a "transfer set" of games which we do care about to show that it works to solve them correctly.  Otherwise it is difficult to evaluate the method, as it could have "low error on average" but not low error on the problems we care about.  

In the same vein, since we usually care about getting the CE for a particular game, I would be useful to compare to finding the CE for that particular game directly rather than solving all games of that shape first.

**Minor Comments:**
Figure 4 is hard to understand, given that the  difference between the gray and black error bars are never described.

The appeal to "Occam's razor" on line 93 is very suspect.  It appears this is alluding to something specific (which should be cited), but regardless of what the citation is there has to be a miscommunication somewhere because there "maximum entropy" isn't well justified by "Occam's razor".  In some sense they could be seen to be the opposite, as "Occam's razor" is often phrased as "preferring the simplest solution" and "maximum entropy" is the most-random solution (under some measure) and thus the least-compressible (under that measure), which could be seen as the "most complicated" solution!  Regardless, none of this is necessary, because any method of choosing between equilibria is fine for the purposes of this paper.
questions: How were the hyperparmeters selected for your approach v.s the baselines? 

limitations: The limitations were adequately addressed except to the extent mentioned above.
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: Games are a useful formalism in machine learning. There are multiple notions of solution to a game; this paper focuses on Correlated Equilibria (CE) and Coarse Correlated Equilibria (CCE). Given the payoffs of a game, the set of all CE (resp. CCE) form a polytope, with number of constraints exponential in the number of players and actions. Thus, solving for a CE (CCE) can be computationally intractable.

This paper proposes to use a neural network to predict approximate CE (resp. CCE) given the payoffs of all players, as well as some auxiliary data. The authors propose several innovations to make the proposed neural equilibrium solver more efficient and flexible:
  - several choices of secondary criterion used to select a particular CE (resp. CCE) from within the polytope of all CE (resp. CCE).
  - A permutation-invariant network architecture, capable of exploiting symmetries in the game (e.g. exchangeability of players, permutations of a players action set).
  - Focusing on solving the dual problem, which has fewer optimization variables as compared to the primary problem.


strengths_and_weaknesses: ## Strengths
  - Predicting/ computing NE/CE/CCE is certainly a worthy topic.
  - I appreciated the use of strong duality for convex optimization! 
  - Experiments are thorough.

## Weaknesses
  - Overlooks certain important aspects of the literature.
  - I found it hard to follow how the proposed network is actually trained.
  - Scalability of proposed approach to even moderately sized games is unclear.

##Edit
Changed score to 7 after rebuttal.
questions: Let me elaborate on some of the weaknesses highlighted above. If you can clarify my confusions, I will consider raising my score.

## Training and experiments.

  1. **Training Loss and gradients** I don't quite understand how you trained the proposed network. What is the loss function? Also, how do you propose computing gradients with respect to the network parameters? (Eq. 11 gives a formula for a gradient, yes, but it is not with respect to the parameters of the neural network.)
 
  2. **Training data** Can you tell me more about the training data set you used? As far as I can understand, you randomly generated a fresh i.i.d batch of 4096 $8\times 8$ games (I guess by randomly sampling payoff matrices) each iteration. Is this correct? Also, I found Section 4.2 a bit hard to follow, for example, what is meant by the first sentence "Zero-mean and constant norm scale geometrically results in the edge of a disc."?  

3. **Train time and network size**  As you mention in Section 5, the train time is an important metric when evaluating learned solvers. Could you comment on how long (in wall-clock time) it took to train your NES for $8\times 8$ games? Also, how many parameters in total did this network have?

 3. **Scalability** I am a little skeptical that your approach will scale to large games. Indeed, your experiments seem to target small games ($4\times 4$, $8\times 8$). Could you run an experiment for truly large games, e.g. $100\times 100$ or $1000\times 1000$? If no, could you clarify the intended use-case of the proposed NES?

## Relation to Learn to Optimize literature

I appreciated the reduction of determining a CE/ CCE to a convex optimization problem. I also think the use of duality to reduce the number of variables is clever. However after this reduction, the problem you're proposing: learning a solver for an optimization problem is well-studied in the Learn-to-Optimize (L2O) literature. Thus, the relation of your work to this literature should be discussed (see, for example [1] and citations therein). Using some of the terminology in [1] may help to describe your training set-up and resolve my questions above.

## Relation to Learning to solve Games literature.

Several recent works [2,3,4] have proposed uses gradient-based learning in conjunction with game solvers. The focus of these papers is slightly different to yours---closer to the inverse game theory literature briefly alluded to in the conclusion. Nevertheless, the relation between your work and these papers should be discussed. 

## Minor Comments
  1. Lines 19--21 are needlessly repetitive: "take a non-deterministic amount of time to converge", "take a prohibitive amount of time to do so", and "do not scale" are all essentially the same point.

  2. Citation [10] should be updated. It seems the paper has changed name. A related comment: the citation numbers in the main article and the supplementary do not match. 

  3. In line 101, when introducing relative entropy, you should mention that this concept is also known as Kullback-Liebler divergence (you actually do this in the appendix). 

  4. Line 106. Typo in the word "hyperparameter".

  5. Line 113--114 I think it is more precise to say you solve the dual problem instead of "optimize the dual Lagrangian".

  6. In line 131--132 you mention $Z_m$, but it's not clear what this is yet. You could clarify that this is just some user-defined scale parameter.

  7. Line 137. I found this sentence hard to understand, as mentioned above.

  8. Line 215. Is "Maximum Utilitarian" the same as "Maximum welfare"?

  9. What do the axes mean in Figure 3? Is the y-axis average solver gap over a test set of games? Is the x-axis number of training iterations?

  10. Line 252--253. "would be otherwise be too time-expensive" has an extra "be".

## Bibliography
[1] Chen *et al* Learning to Optimize: A Primer and A Benchmark (2021)

[2] Ling *et al* What game are we playing? End-to-end learning in normal and extensive form games (2018)

[3] Li *et al* End-to-End Learning and Intervention in Games (2020)

[3] Heaton *et al* Learn to Predict Equilibria via Fixed Point Networks (2021)


limitations: These are adequately addressed.
review_title: null

Meta-review: metareview: This paper introduces an Neural Network based Equilibrium Solver which utilizes a special equivariant neural network architecture
to approximately predict NEs, CEs, and CCEs of normal-form games. Experiments show the effectiveness of the proposed methods across multiple dataset. All reviewers support the acceptance of this paper. 

While I agree on the merit of this paper worth acceptance, I'd also recommend authors to revise a bit in the final version regarding to the theoretical complexity of finding equilibrium. (1) in line 18 "solving for an equilibrium of a game can be computationally complex [9, 8]", in fact, the cited intractable results only apply to finding Nash in multiplayer general-sum games. Finding CE/CCE can be always done by LP, which is tractable, and can be guaranteed to finish in polynomial time; (2) this paper emphasize that prior methods may take an non-deterministic time to converge, while this method proposed in this paper gives determinism. However, it appears to be the methods proposed in this paper is not provided with guarantees to converge in certain time (thus without determinism either). It's better if the authors can clarify or modify corresponding arguments.


confidence: Less certain
Decision: Accept