Venue: NeurIPS 2022 Conference

Reviews:

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 congestion games which has wide application in practice. The authors propose novel algorithms for learning the congestion game with semi-bandit or bandit feedbacks, i.e., the centralized algorithm and the decentralized algorithm. They define a new problem, Markov congestion game, and propose a centralized algorithm to learn the Markov congestion game. They further derive the upper bounds of the learning regret and the sample complexity for the above problems, which are independent of the size of the action set.
strengths_and_weaknesses: This paper studies the congestion game learning with (semi-)bandit problems, whose regret and sample complexity are not well understood before. Novel algorithms different from the existing UCB-type method are proposed to solve the corresponding problem. And the theoretical results are novel, which does not depend on the size of the action set and thus avoids the curse of exponential action set. Therefore, the theoretical contribution of this submission is significant. Moreover, this paper is well written and the structure is clear to the readers. Besides these strengths, I also have several questions regarding this paper:

(1) Can we still propose a UCB-type algorithm for the decentralized case? If not, what is the major obstacle of designing the UCB-type algorithm and what is the technical advantage of using FW + G-optimal design to solve this problem comparing to the UCB-type algorithm?

(2) The sample complexity for the algorithms with FW still has high-order dependence on m and F. Is it possible to lower the order of powers in the dependence on m and F?
questions: Please see the above section.
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 studies the problem of learning Nash equilibria in congestion games and in independent Markov congestion games, where the latter are a simple and natural generalization of congestion games to the Markov setting. The authors propose both centralized and decentralized algorithms for congestion games, whose sample complexity does not depend on the number of players’ actions (which in this setting can be exponential in the size of the game representation). The algorithms work under both semi-bandit feedback (the players observe the cost of each facility they choose) and bandit feedback (the players only observe the overall cost of all the facilities they select). Then, the authors generalize their centralized algorithms to the independent Markov congestion game setting, obtaining sample complexities that do not depend on the number of players’ actions.

strengths_and_weaknesses: ORIGINALITY

(+) The paper provides the first algorithms for learning Nash equilibria with bandit feedback in congestion games whose sample complexities guarantees do not depend on the number of players’ actions.

(-) The tools used in order to derive the main results in the paper are rather straightforward adaptations of commonly-used techniques: the centralized algorithms work by exploiting the optimism in face of uncertainty principle, while the decentralized ones leverage the Frank-Wolfe method, the G-optimal design, and the specific structure of rewards in congestion games. 

QUALITY

(+) As far as I am concerned, the technical results are correct and adequately commented.

CLARITY

(+) The quality of writing is sufficiently good, even though there are some typos and grammatical errors that I invite the authors to spot by a simple applications of free spell checking tools.

(-) The presentation of the results is hard to follow in some parts. I think the main problem is that more than half of the paper is devoted to introducing models and notation, while only the last three pages are reserved for the main technical results. I think that maybe the authors should try to amend this issue by removing some notation that is not needed in the main paper and putting it in the appendix. 

SIGNIFICANCE

(+) The results presented in the paper are significant since they considerably improve over already known sample complexities results for learning Nash equilibria with bandit feedback in congestion games.

(-) One of the main drawback (in my opinion) of the paper is that the decentralized algorithms do not extend to independent Markov congestion games. I think this is a major missing point and I am questioning whether it is worth devoting so much space in the paper to them even if the main decentralized algorithms do not work in that setting. Maybe it is better to concentrate on the simple congestion games model where all the algorithms are shown to work.

(-) The results can be of interest only for a small portion of the NeurIPS community, in particular to those interested in algorithmic game theory and online learning.

questions: 1) Can you provide me some intuition as to why you techniques cannot be used if one wants to minimize the regret of each player rather than the (overall) Nash regret as you are doing?

limitations: I think there are not limitations and potential negative societal impact for this work.
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 work studies the problem of learning in repeated congestion games and proposes the first efficient algorithms with good regret guarantees for the following cases
- centralized case with both bandit and semi-bandit feedback
- decentralized case with both bandit and semi-bandit
- centralized case for Markov congestion games with both bandit and semi-bandit feedback
strengths_and_weaknesses: ---- Strengths ----

This work provides first good efficient algorithms for several version of online congestion games.
The used techniques are nice and natural. The claimed results seem sound.

---- Weaknesses ----

1) One of the main novelty of this paper comes from what is called "sample complexity" by the authors, but I am not even sure what they do refer by this word. It seems to me that they meant "computational complexity", but I might be wrong. In any case, there seems to be no further discussion on the "sample complexity" results after the introduction. It is a major point of this work as shown in the Table page 2, and I think the authors should explain in details (at least for one or two algorithms) why these complexity bounds do hold.

2) If my interpretation is correct and the authors did refer to computational complexity, it then seems that simulations (on a toy model) would be required to illustrate the fact that these methods can be efficiently implemented. Otherwise, this suggests that the claimed efficient algorithms are actually not that efficient.
questions: My main questions regard the claims of good "sample complexity" as explained in the weaknesses section.

----- Minor comments -----

1) In definition 3, I think it would be good to precise the dependency on pi of the Nash regret, as it depends on it both in the cumulated reward (second term), but also in the baseline reward (first term).

2) How can we efficiently compute the solution of eq (5) ? Also, there seems to be a typo line 283 as I believe the = sign should be an inequality?

3) In Theorems 1 and 2, what are the dependencies of the regret in delta ?
limitations: Not concerned
review_title: null

Meta-review: metareview: This paper examines the behavior of certain payoff-based learning algorithms in repeated congestion games.

The initial reviews were positive, but a more detailed reading of the paper and the discussion phase revealed the following issues:  

- In terms of technical results, the authors are not proving convergence to Nash equilibrium, but the minimization of "Nash regret" (a regret-like variant of the Nikaido-Isoda function) which, at best, means that among $K$ episodes, there exists one episode for which $\pi^k$ is close to Nash. This issue was discussed during both the author-reviewer and reviewer-AC phases, and there was consensus that the authors' results cannot be labeled as "convergence to a Nash equilibrium". The authors' revision was not satisfactory in this regard: the statement that the paper is using a "non-asymptotic notion of convergence" misses the crux of the issue and creates more confusion so it was not seen as a step in the right direction.  
    
- In terms of writing, the paper begins by treating repeated games in normal form, with polcies playing the role of mixed strategies; here, the episodes are single-shot instances of play. In the decentralized case however, the episodes are no longer single-shot instances of play, and the players are assumed to be using the same policy throughout this sampling period - in essence, playing the game in a stationary way. Finally, in Section 6, the authors treat stochastic / Markov games, where the notion of an episode is something still different. The inclusion of the algorithms in the revised makes things easier to follow, but it does not address why the UCB-based approach of the centralized case cannot be expected to work here - the authors are justifying the use of the FW update as a means to combat the curse of dimensionality but this does not explain why FW updates are not used in the relevant centralized updates as well. All this makes the paper quite difficult to follow at a technical level.  
    
- Finally, in terms of positioning, the authors seem to be motivated by the recent regret-based works of Ding et al. (2022) and Liu et al. (2021) but, at the same time, they seem to ignore the much wider literature on game-theoretic learning. This was also flagged as a cause for concern during the discussion phase.  

Despite the above shortcomings, the reviewers appreciated the paper's technical contributions and felt that they warrant acceptance. As a result, a decision was reached to make a "conditional accept" recommendation subject to the authors' revising their paper to account for the above issues. Specifically:
- The final version of the paper must make clear that the type of results obtained do not concern convergence to (or "learning of") Nash equilibrium, but the minimization of a regret-like measure based on the Nikaido-Isoda function. [In particular, the motivating question in L56 should be removed, and the abstract and introduction must be likewise amended]  
- The passage from single-stage to multiple-stage episodes must be justified, as well as the passage from repeated to stochastic congestion games.  
- The authors must improve the positioning of their paper in relation to existing works on multi-agent learning with bandit feedback; some relevant references are provided below.

These changes are quite extensive, but the quality of the paper did improve during the revision phase, so the committee felt confident that the authors can undertake the above required changes for the camera-ready submission.

**Relevant references:**
1. Sebastian Bervoets, Mario Bravo, and Mathieu Faure, Learning with minimal information in continuous games, Theoretical Economics 15 (2020), 1471–1508.
1. Mario Bravo, David S. Leslie, and Panayotis Mertikopoulos, Bandit learning in concave N-person games, NeurIPS ’18: Proceedings of the 32nd International Conference of Neural Information Processing Systems, 2018.
1. Roberto Cominetti, Emerson Melo, and Sylvain Sorin, A payoff-based learning procedure and its application to traffic games, Games and Economic Behavior 70 (2010), no. 1, 71–83.
1. Pierre Coucheney, Bruno Gaujal, and Panayotis Mertikopoulos, Penalty-regulated dynamics and robust learning procedures in games, Mathematics of Operations Research 40 (2015), no. 3, 611– 633.
1. Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragkounis, and Panayotis Mertikopoulos,
The convergence rate of regularized learning in games: From bandits and uncertainty to opti- mism and beyond, NeurIPS ’21: Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
1. David S. Leslie, Reinforcement learning in games, Ph.D. thesis, University of Bristol, 2004.
1. David S. Leslie and E. J. Collins, Individual Q-learning in normal form games, SIAM Journal on Control and Optimization 44 (2005), no. 2, 495–514.
1. David S. Leslie and E. J. Collins, Generalised weakened fictitious play, Games and Economic Behavior 56 (2006), no. 2, 285–298.
confidence: Less certain
Decision: Accept