Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an abstraction of the online Follow-the-(Blank)-Leader type of methods they call Follow-the-Generalized-Leader (FTGL) that not only incorporates various regularization functions but also different feedback models. The authors provide a general convergence analysis for the family of methods over the problem of finding *strict* Nash equilibria in *finite* games. The main insight of the work is to claim that the convergence rate in this problem only depends on the regularization function used and *not* on the different feedback models, e.g. full information feedback vs bandit feedback.
main_review: This submission was an interesting read given its somewhat surprising conclusions. It is clearly written and easy to follow. However, it seems like the authors aim to claim two contributions (this might not be true): (i) abstracting FTRL into FTGL and giving convergence analysis on a specific problem; (ii) new convergence results for the specific problem of strict Nash equilibria in finite games. I believe (i) is unnecessarily abstract and confusing for two reasons: first, we know how to do FTRL with different regularization functions (Bregman divergences as potential functions), so the fact that the regularization function is written more generally is not a contribution; second, it is not quite clear what the exact assumptions are w.r.t. different feedback models when they are all lumped in together into one.

More importantly, if the main contribution of this paper is showing new convergence results for finding strict Nash equilibria in finite games, then the authors should pick the specific algorithm(s) they use, prove and provide their convergence results, and draw conclusions. The unified framework might be appealing and seem elegant, but in this case, in my opinion, it doesn't contribute anything and obfuscates from the main problem at hand. In particular, the studied problem seems amenable to the Euclidean $l_2$ norm regularization given the geometry around the strict equilibria. The result suggests convergence to the desired points in a finite number of steps -- since the problem is solved in finite number of steps, for comparison one must look at the exact number of steps then instead of bringing in MW as another method to compare to. Now given $l_2$ regularization, is there any convergence rate difference between various feedback models, e.g. full information and bandit? I would be very surprised if not. And note that even if in your analysis you get identical rates, you cannot make any claims about these rates without any lower bounds -- maybe with your analysis they have the same rate but it's possible to do things much faster with full information. This same logic should apply to experiments, get rid of MW experiments, make the claim that there is convergence in finite number of steps, and compare the exact number for different methods with $l_2$ regularization.

Overall, the paper has interesting ideas, insights, and results, but, as presented, I don't think it's ready for publication. Weak reject.
limitations_and_societal_impact: The societal impact was adequately addressed. I would like to see more discussion around the limitations of this work. The authors could answer questions such as how much this exact problem has been studied, what results were known for it, and what can be done for future work (or what should be investigated).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: # Summary

The paper investigates the important issue of convergence in games. 
A local convergence result is shown in N player general sum games, where local 
means within a neighborhood of a strict Nash equilibria. 
Convergence is attained with the proposed follow the generalized leader (FTGL) 
framework, resembling the classical follow the regularized leader method
from online learning. Futhermore convergence is shown under a set of assumptions 
that includes various forms of feedback, from deterministic to bandit feedback.
Connections with FTGL and other well-known algorithms are also made. 

main_review: 
# Main Review

## Summary of Review

Overall the paper is well written with significant contributions to the field of learning in games. 
In particular, although only local convergence to a strict Nash equilibrium is considered, 
a convergence result for a large family of algorithms such as FTGL in general sum games is likely to be impactful. 
Furthermore, having a unified framework for studying various forms feedback (from deterministic to unbiased to bandit) and showing convergence is of great value. 
I would expect that similar techniques might be useful for examining stronger convergence results if more assumptions are made on the game such as two-player zero-sum.

I do however have some issues regarding the discussion of related work and the claimed connections of FTGL with other well-known algorithms (see clarity section below).


## Originality

I believe the results to be novel see summary above.

## Quality

The paper is complete in its investigation of local convergence for the FTGL method
and results are supported with extensive proofs, using well-known tools from probability theory and convex analysis. 
I would like to see more clarification of the fixed stepsize result referred to in lines 295-298. It is difficult to see where this result is located in Appendix C, it would be better to include a more exact pointer.
This result is important because other related works show convergence for a fixed stepsize [2]. 

## Clarity
I believe the paper to be well-written overall, however, improvements can be made with respect to discussion of related work, and connections between FTGL and other methods.

### Discussion of related work

Comparisons of related work are made in the related work section and throughout the paper.
There is an emphasis on stohcastic vs determinstic (See footnote 2 for example). It is claimed that a lot the related works depend on deterministic feedback for convergence as opposed to this paper studying a more general feedback model for which results from the related work do not apply (expect the works of [1] for example). 
I too believe this statement to be true, however, I believe an important main driver of convergence in a lot of the works cited in these cases like those in footnote 2 or like [2], is not just the fact that it is determinstic but also because the games are monotone and Lipschitz smooth (don't need strongly monotone in the most general settings). But it should be mentioned that there is a significant important distinction in the quality of the results attained in these works, that they are global convergence guarantees. 
Take the original extra gradient method from [3] for example, it is shown that the procedure will converge to an equilibrium without assuming starting in a neighbourhood of an equilibrium. 
Or take for example an even closer related work [2], where convergence of the optimistic multiplicative weights algorithm (an example of optimistic follow the regularized leader) is shown to converge in zero-sum matrix games with unique equilibrium if a sufficiently small constant stepsize is used.
Therefore, I would suggest to emphasize that tho the paper investigates convergence in general sum games with possibly stochastic feedback the convergence results are local while a lot of the related works focus on global convergence with determistic feedback; except perhaps for the mentioned related work [1] where I believe global convergence is shown in potential games even with bandit feedback.

### Connections between FTGL and other methods

#### FTGL vs FTRL
Although FTGL resembles FTRL I believe it is different in a fundamental way by how the stepsizes are used. FTRL with a sequence stepsizes is generally understood to mean that at a each round when a stepsize is selected it is applied to all the past feedback vectors in the same way (see for example [4]). This is different that FTGL unless constant stepsizes are used.

#### FTGL and Mirror Prox or Mirror Descent

I believe that FTGL is more closely related to FTRL than mirror descent since it maintains an average in the dual space $Y_{i,n}$ and then projects back to the primal space when needed. This setup can sometimes be equivalent to mirror descent  (for example see [4]), but without further assumptions this approach is different 
than mirror descent (projected gradient descent as an example) which maps the primal iterate to the dual space before taking
a gradient step. For example in the case of example 3.1 they are equivalent but in the case of example 3.2 they are not. Therefore, I do not see how the FTGL framework can capture mirror prox in general (which can be written as optimistic mirror descent [5]). I see there are discussions in the appendix to justify this connection, however, I do not believe mirror prox or extra gradient can be recovered if one averages in the dual space like FTGL. 



## Significance
See summary above.

## Other minor suggested improvements

* I think there is a typo on line 134 $supp(x_i^\ast)$ should be $supp(x^\ast)$ ?
* What is the value of $q$ in assumption A3? is it the same $q$ as in A2?
* Why is it assumed that $h_i$ is decomposable? For example do you expect $h_i(x_i) = <x_i, M x_i>$ the matrix norm for an arbitrary positive definite matrix (hence $h_i$ is strongly convex) to also work? what is the difficulty when we cannot decompose $h_i$? A discussion would be nice.
* On remarkk 3.1. This remark seems to be closely related to the Legendre assumption that is commonly used when defining mirror descent in online learning, see for example [4]. This might be interesting to mention or investigate.
* On model 3 for OptFTRL. This perspective suggests that optimism is a nuissance to deal with since it contributes to bias. However, in online learning optimism improves regret bounds for predicatble problems and so helps with convergence [5,6].
A comment on these two different perspectives would be interesting.


References

1. Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. In
NIPS ’17: Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.

2. Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max
optimization. In ITCS ’19: Proceedings of the 10th Conference on Innovations in Theoretical Computer Science, 2019.

3. G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Èkonom. i Mat. Metody, 12:
747–756, 1976.

4. Orabona, F., 2019. A modern introduction to online learning. arXiv preprint arXiv:1912.13213.

5. Rakhlin, S. and Sridharan, K., 2013. Optimization, Learning, and Games with Predictable Sequences. Advances in Neural Information Processing Systems, 26, pp.3066-3074.

6. Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in
games. In NIPS ’15: Proceedings of the 29th International Conference on Neural Information Processing Systems, pages
2989–2997, 2015.
limitations_and_societal_impact: Limitations are discussed throughout the paper. There is not discussion of potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper focused on normal-form games and proposed an algorithm framework called "follow the generalized leader" (FTGL). The framework covers the well-known "follow the regularized leader" methods as well as many other variants. The authors established FTGL's local convergence to strict Nash equilibria and further demonstrated that MWU converged linearly, while Euclidean projection methods converge within finite steps.
main_review: This paper focused on normal-form games and proposed an algorithm framework called "follow the generalized leader" (FTGL). The framework covers the well-known "follow the regularized leader" methods as well as many other variants. In particular, the FTGL method updates a score vector with the payoff observed in every iteration and the strategy is induced by the score vector via a choice map function. This include well-known MWU method as a special case.

The main result states that as long as the score vector lies in a proper initialization zone, FTGL methods are guaranteed to converge. The convergence rate depends on the choice of step size as well as the choice map. In particular, MWU with constant step size converges linearly and Euclidean projection methods converges within finite steps.

While the results appear to be new, the fast convergence does not seem to be surprising under the assumption of strict Nash equilibrium and initialization condition. Actually the assumptions may have revealed extra information: as long as $\\|X_i - x_i^*\\|_\{1} < 1$, one can immediately recover $x_i^\*$ by simply picking the action with largest probability in $X_i$. Therefore, providing some discussion on how large  $W_\{init}$ is would make the result more solid. Showing $W_\{init}$ is unbounded alone doesn't necessarily leads to larger $\\{X_\{i, 1} = Q_i(Y_\{i,1}), Y_1 \in Q_\{init}\\}$, as scaling (or shifting, depending on the choice map) the score vector leads to exactly the same strategy. 

Typos:

line 246, "thatthat";

line 248, "consdier"
limitations_and_societal_impact: See main review
review_title: null

Meta-review: After discussions, reviewers agree that this paper makes solid contribution for 
advancing the understanding of the convergence rate for regularized learning in games.
Please do incorporate all the suggestions/discussions from the reviews into the final version.
Decision: Accept (Poster)