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 paper proposes two algorithms for finding approximate local Nash equilibria in pseudo-games. The algorithms are based on a new function, which roughly measures each player’s regret in some strategy profile a to a strategy in some other strategy profile b. A strategy profile a is an equilibrium if and only if it minimizes the maximum of regret over b to 0. The algorithms are then based on optimizing a and b with gradient ascent/descent. Various technical problems are addressed, e.g., gradient steps taking the solutions out of the feasible sets. The authors show that under convexity/concavity of the regret (and a few other assumptions), the algorithm finds (approximate) local Nash equilibria. They also demonstrate that they algorithms converge faster than existing algorithms in a few experiments.
strengths_and_weaknesses: This paper’s contribution seems good as far as I can tell. Unfortunately, I don’t know this literature (pseudo-games, finding equilibria) very well. So I’m not very confident in my judgment.

Some minor comments:

Superfluous apostrophe in line 140.

Line 148: Are we assuming differentiability?

Line 229: “More generally, cumulative regret can be a non-convex-concave function, in which case a minimax theorem does not hold, which precludes the existence of a NE.“
I found this sentence hard to understand. I suppose you are talking about the game induced by \Psi, not the original game?

The sentence in Line 238ff. is not grammatical, I believe.

Line 262: I assume one of the \psi_\alpha should be \phi_alpha.

Line 270: This is a weird indicator function, especially with the blackboard-bold 1, but okay.
Also, how is this indicator function continuous (or convex)? It looks rather discontinuous. Is this just on X?

I don’t understand Line 2 and 3 of Algorithm 2. Why is line 3 performed n times, where n is the number of players?
questions: Most of the above questions seem relatively minor, but I’d still be interested in explanations.
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 discusses Nash equilibrium computation in pseudo-games, which are games in which the players' legal strategy spaces may depend on other players' strategies. The paper reduces the problem to solving a certain min-max problem which is not convex-concave in the general case, and then gives algorithms for computing solutions of that min-max problem. The paper analyzes these algorithms both theoretically and practically, and obtain state of the art results in both.
strengths_and_weaknesses: The results in the paper are, to my knowledge, new and interesting, though I admit that I am not familiar with pseudo-games. Perhaps to aid readers like myself, I would advise the authors to include some extra intuition for people familiar with regular games but not pseudo-games. In the "Questions" section below, I include some questions that I had while reading the paper that would help greatly in that direction. 

Along those lines, the paper generally seems a bit light on intuition. For example, the paper discusses the fact that algorithms are well known when the cumulative regret $\psi$ is convex-concave, and then introduces Assumption 3.3. How "far away" is Assumption 3.3 from convex-concavity? Is the analysis in the paper a straightforward extension of known analyses for convex-concave $\psi$, or do the weaker conditions introduce new technical problems to be resolved? If the latter, what are they?
questions: 1. Is there any intuition for variational equilibrium? For example: why, in deviations, do we enforce the condition $\boldsymbol{a} \in \mathcal{X}$? That seems to imply to me that somehow, we concern ourselves with ways that *all of the players can collectively deviate* (i.e., the "joint deviation strategy" $\boldsymbol{a}$ must be feasible), yet at the same time we only care about whether each player individually profits from such a deviation when the others are playing equilibrium? This seems extremely weird to me coming from regular game land; the GNE definition seems more principled. 
1. Why does the paper bother to define general pseudo-games, when all the results are seemingly restricted to pseudo-games with joint constraints? That seems like the more natural case anyway, and it simplifies a good amount of notation. 
1. Along those lines, why is Section 4 titled "Pseudo-games with jointly convex constraints"? It seems like the entire paper devoted to pseudo-games with jointly convex constraints (by Assumption 3.3). 
1. Does this paper give any new results for normal-form games, or are the results of this paper known for that particular case? It would be nice for such things to be explicitly discussed somewhere - perhaps the results can be framed as an extension of known normal-form results if that is true.

limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes methods for finding generalised Nash equilibria (GNE) for pseudo-games, which are a generalisation of classical games. They use a well known reformulation of the GNE problem as a min max problem. Then they show that a Extra-gradient method can be efficently used to find GNE in case in which the min max problem is convex-concave. Later that present a double loop gradient based algorithm to approximate the problem when the min-max reformulation is not convex concave. In this case the solution is a local Stackelberg equilibrium (stationary point of the minimal problem). They complement the theoretical analysis with an experimental evaluation
strengths_and_weaknesses: Form the point of view of the subject of study, the paper is original as not many papers in AI study pseudo-games. However, in the reviewer opinion, the technical contributions are not clear. 
Section 3 seems straightforward as Th 5 of [57] says that any method adapt to solve Variations Inequalities can be employed to find GNE. The author should maybe clarify such point. 
Section 4 seems more interesting but, again, the reformulation in terms of a min max problem seems to let us conclude that any algorithm that finds approximate stationary points of non-convex non concave min-max games can be used here and regularised exploitability was an already existing concept. However the the reformulation used here seems more involved as it needs to find the zeros the projected gradient operator. The authors should clarify such a point as it is central to the understanding of the contribution of the paper.

The paper is in general well written and well structured. However, in the reviewer’s opinion clarity could be slighly improved. I would suggest to include in the introduction a small toy example of a pseudo-game with jointly convex constraints. 
The “min-max Stackelberg game” paragraph does not contribuite to the exposition of the paper. It’s almost never referenced later and I would suggest it to be moved in the appendix (maybe enlarged). 
I would suggest to remove the general definition of a pseudo-game and just expose the case of joint constraint as the more general version is never actually used.
questions: Questions:
1) Are the results of Section 3 straightforward once one reformulates GNE as a VI problem and can any algorithm that solves VI be used here?
2) Is the main contribution of Section 4 the original reformulation of non-convex-non-concave pseudo games by means of the projected gradient operator? Can any algorithm that solves non-convex-non-concave min-max problem be used here?
3) Is the introduction of min max Stackelberg equilibrium necessary to the exposition? 

Suggestions (minor):
3) Introduce early on an example of a pseudo game.
4) Define only jointly constrained pseudo-games.

See the Strengths And Weaknesses section for more detailed description of the questions.
limitations: N/A
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 introduces two algorithms for finding an approximate variational equilbrium in pseudo-games with jointly convex constraints. Both algorithms look at setting up exploitability as a min-max problem with the regret-maxmizing strategy being an optimized variable, rather than a non-smooth max-regret objective. The authors provide theoretical bounds for the algorithms, and compare the performance to an existing algorithm on a three classes of random test problems.

strengths_and_weaknesses: This work introduces two new algorithms EDA and ADA, with looser theoretical requirements than an existing algorithm, and the ability to find a stationary point in non-convex games, respectively.  On a set of randomized test problems, EDA is slightly worse and ADA is notably better, while both appear to be more likely to non-deterministically work than the baseline algorithm in situations where convergence isn't guaranteed.

I found the paper to be generally readable, but there were a number of sections that were less clear. One major piece that was less clear was exactly what the contributions of the paper were. Is it theoretical, reducing the bounds of AMPQP by a log factor -- although possibly working in a smaller set of games? Is it finding stationary points in a larger class of games -- why not test that?  Is it the empirical performance -- why introduce EDA then, when it is slightly outperformed on the test games chosen?


---- edited after author response
Clarifying the distinction between EDA and ADA,  EDA is a 1/epsilon method for finding a VE (and thus GNE) when regret is convex/concave, and ADA is a log(1/epsilon)/epsilon method for finding a stationary point as long as u is smooth and the feasible set is convex, or a VE if regret is invex.  This is described by lines 73-80.

questions: How is this work providing methods for exact computation of GNEs?  Both algorithms are iterative methods with bounds on solution quality after T iterations.

131: g>=0 iff g_i>=0 for all i?

132: d is some arbitrary, game-specific choice?  Is there intended to be some difference understood between describing it as g(x,y) = (g_1(x,y),...,g_d(x,y))T and g(x,y):XxY -> R^d similar to other functions?

135: min-max SE definition missing text describing leader (x) and follower (y) distinction?  Odd phrasing of definition, with the inequalities.  Those same inequalities make sense in the Goktas and Greenwald paper introducing min-max inequalities, where there are delta and epsilon approximations, but are non-intuitive choice here without the delta,epsilon. max_y f(x*,y) can not be greater than f(x*,y*).

144: is this the same d as on line 132?

150: "in which case X is simply a set"
Some other phrasing? X_i(a) is a common set across all i, but that's a subset of X -- as noted on 159.  Regardless of joint constraints, X(a) is also a set, as is the same {a | a in X(a)} set.  Saying "simply a set" seems to imply seem obvious reason to consider this set X, which is at least not obvious to this reader.

173, 178, 195, ...: Psi(b;a) is sometimes Psi(a,b), mostly later in the paper.  Psi(b;a) != Psi(a;b), so consistency here matters.

193: Key insight (also? rather?) is switch to looking at VEs instead of GNEs? Without the issue of a* being within X(a*), finding a VE with joint convex constraints seems to be a standard optimization problem. phi is non-smooth -- but with that switch, wouldn't something like Nesterov smoothing also work, with similar bounds as EDA?

204: What are those assumptions? Should also be included in the text, for contrast.

219: O(1/epsilon^(1/2)), rather than O(1/epsilon^2)?

249: How is b*=a a solution to the inner maximization? Is this max_{b in X} Psi(a,b)? For an arbitrary a, Psi(a,b=a)=0 seems unlikely to be a maximum.  The prior case where b=a* is in the argmax only seems to hold because Psi(a*,b) <= 0.

Algorithm 2: missing use of i in step 3?

Figure 1b: The scale required to contain the spikes in exploitability makes it hard to tell how close to 0 are things in the tails. Are the different methods notably different, or are they all inconsequentially close to 0?  Possibly solved by including a log-scale version of this plot instead / as well.

352: The paper states EDA has weaker assumptions on line 205, however here at line 353 AMPQP is expected to converge, while EDA is not. How do these two pieces fit together?


320: psuedo
330: we us -> we use a
349: methodsEDA
350: objectivesAMPQP

limitations: yes
review_title: null

Meta-review: metareview: On the one hand, this paper does not suffer from important criticisms. On the other hand, the paper has not a champion as all the Reviewers set their score between Borderline and Weak Accept.

The main weakness concerns the need to improve the presentation and clarify the contributions. I believe this issue can be addressed in a minor revision which does not require a further step of revision. Therefore, I don't see crucial reasons to reject the paper. 
confidence: Certain
Decision: Accept