Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies asynchronous gradient plays in zero-sum polymatrix games under delayed feedbacks, while significant efforts have been made to understand zero-sum two-player matrix games. They first establish that the last iterate of the entropy-regularized optimistic multiplicative weight updates (OMWU) method converges linearly to the quantal response equilibrium (QRE), the solution concept under bounded rationality, in the absence of delays or under the randomly delayed feedbacks with some assumptions. They further demonstrate that entropy-regularized OMWU with two-timescale learning rates enjoys faster last-iterate convergence under fixed delays and continues to converge provably even when the delays are arbitrarily bounded.
strength_and_weaknesses: This paper seems to propose a new problem and then use some technique to solve it, but the property of the proposed problem and intuition behind the technique is unclear:

Why are the zero-sum polymatrix games under delay feedback important? What does ‘delay feedback’ mean in zero-sum polymatrix games? What are real-world scenarios that can be modeled by zero-sum polymatrix games under delay feedback? Why do we need to care about NE and QRE in these games?

What is the challenge (e.g., complexity) for computing the Nash equilibrium and Quantal response equilibrium in zero-sum polymatrix games under delay feedback?

Why does synchronous optimization not work in zero-sum polymatrix games under delay feedback?

Are there any existing algorithms that can solve the new problem? 

How to obtain Eq.(8)? \pi in QRE and NE may not be the same due to Eq.(5). Is it possible to show the result for NE instead of using this formula and the results of QRE?

How to remove t in the rate, i.e., O, before Remark 1?

What is the intuition of Assumptions 1, 2, and 3? Are they realistic in real-world scenarios?

Why do we need to consider a two-timescale problem?

clarity,_quality,_novelty_and_reproducibility: Some parts of this paper are hard to read:

How to obtain Eq.(8). \pi in QRE and NE may not be the same due to Eq.(5)?

In Eq.(6), \tau is the regularization parameter or temperature, then what is u_i(\tau)?

How to remove t in the rate, i.e., O, before Remark 1?

What is the intuition of Assumptions 1, 2, and 3? Are they realistic in a real-world scenario?

Why does KL increase in Figures 1(b) and 1(c)?

Minor:
At the beginning of Section 1.2, ‘excessive gap technique  of Nesterov’ needs a reference.
summary_of_the_review: This paper seems to propose a new problem and then use some technique to solve it, but the property of the proposed problem and the intuition behind the technique is unclear.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper designs variants of the Multiplicative Weights Update algorithm to find epsilon-approximate equilibria (Nash and Quantal response) for zero-sum (multiplayer) polymatrix games. The main algorithm is called OMWU (optimistic multiplicative weight updates) and comes in two variants: single-timescale and two-timescale. The analysis shows that single-timescale OMWU converges linearly if feedback is instantaneous or delays come from a distribution that vanishes exponentially. two-timescale OMWU achieves last-iterate eps-Nash convergence and average-iterate eps-QRE convergence when there are bounded adversarial delays. Convergence rates are generally linear.
strength_and_weaknesses: Strengths:
(1) the problem seems fairly natural, and this is the first paper that is moving beyond the two-player regimes while studying asynchronous (delayed) dynamic.

(2) the introduction of the two-timescale algorithm that achieves better convergence rates under bounded adversarial delays adds some novelty to the paper.

Neither here, nor there
(1) the theorems are supported by some empirical experiments. On the other hand, the experiments seem to be on synthetic data that is created to meet the hypotheses of the theorem, rather than being experiments on real data.

Weaknesses:
(1) I feel the introduction and motivation of the paper could have been written better. While I don't directly work in this field, I am conversant in it, yet I was not able to identify *exactly* why this problem is of interest (beyond it being a, generally speaking, "natural question"). Even starting at the second sentence "While conventional wisdom leans towards the paradigm of centralized learning," I did not understand what this 'conventional wisdom' was or where it was coming from.

(2) The main technical body of the paper is mostly a listing of theorems. I did not find any proofs or intuitions about how the theorems are proved; and I do not know how technically difficult or interesting the theorems are. On the positive side, sometimes these theorems are followed by some examples of scenarios that meet the hypotheses of the theorems. However, at the end of the paper, I am not entirely sure where these results are relevant and whether they are difficult to obtain. (Once again, I don't work specifically in this area, but I have some familiarity with the general area of TML+economics and computation and these flavors of results.)

clarity,_quality,_novelty_and_reproducibility: Studying MWU algorithms in the asynchronous (delayed feedback) setting for polymatrix games is novel. Previous studies have been limited to either two-player games or synchronous (i.e., real-time) feedback.

The novelty in the algorithm is limited. It is unclear from the paper, whether the two-timescale algorithm is novel. I am not familiar enough with the area to extrapolate.

EDIT: After further discussion with the committee, author responses, my own study etc., I am more convinced of the novelty of the results in this paper. I am increasing my rating of this paper to above the acceptance threshold.

I felt that the motivation of the introduction and motivation of the paper could have been more clearly presented. The introduction talked about the general importance of understanding games, iteration dynamics, and asynchronicty, but I'm not sure why this *particular* problem is of interest.


summary_of_the_review: The paper starts the journey towards understanding asynchronous MWU convergence for multiplayer games. The general direction seems promising. I am not sure how compelling the motivation is though, and it is hard to evaluate how difficult the results are to obtain / how interesting they are technically in the context of previous results.

The "Correctness" question below is hard to answer since there are no proofs in the paper. There are some experiments that seem to support the claims however. The theorems may well be true, I just don't see any proofs in the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies zero-sum polymatrix games where there are several kinds of delayed feedbacks. One such type is random delay, and another type is fixed delay. The paper gives new analyses for single-timescale and two-timescale OMWU proving last iterate convergence for the former and finite-time convergence for the latter.

The main conttribution is to systematically study the impact of having delays, when each player plays according to the entropy-regularized OMWU. Formally, for the case of synchronous updates single-timescale OMWU needs 1/epsilon iterations to reach an epsilon-Nash, and they extend it to the asynchronous setting with required number of iterations 1/epsilon^2. Furthermore, this requires several mild assumptions on the delays (roughly the delays are not completely adversarial, but are random). Moreover, if delays are constant and known, the authors obtain a 1/\epsilong guarantee to \epsilon Nash by adopting two-timescale OMWU. 
strength_and_weaknesses: + interesting setting for 0-sum polymatrix games with delays
+ delays are studied in several contexts and so this paper extends prior knowledge but in the case of random or fixed delays, under some assumptions

weaknesses:
- lack of comparison to previous works without delays in terms of technical details and novelty: I am not sure how technically challenging this "delays" setting is, given all prior works that have significantly studied the problem. Can the authors provide a comparison or an insight for how their analysis significantly differs from previous analyses? What do the authors perceive as their main technical contribution? 
clarity,_quality,_novelty_and_reproducibility: Overall, well-written. There is some lack of comparison to prior works in a meaningful way to understand the novelty of the setting with delays.
summary_of_the_review: Overall, this paper builds upon prior works and studies NE of standard algorithms, with the twist that there are delays, either random or fixed. The algorithms have been used before, which is both good and bad. Good because the algorithms are natural, bad in terms of the novelty. In some sense, the paper's main message is that delays can be handled and nothing goes too wrong with them, even using prior algorithms. My main concern has to do with the technical aspects of the paper: I am not too convinced that this is not an incremental set of results, given the extensive analyses for the setting without the delays. Perhaps the authors can address this concern.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies the convergence of gradient-based algorithms to quantal response equilibria in two-player zero-sum games (and their polymatrix generalizations). The algorithm studied by the authors is based on an entropic regularization template that was first studied in a game-theoretic setting by [1,2], and provides a range of convergence results for both fixed and random delays.

The delay model studied by the authors is not the one commonly followed in the literature. For example, in the standard works [3,4,5,6], it is assumed that an action at time $t$ triggers a delay $d_t$, so the information from action $t$ is observed at time $t+d_t$. By contrast, the authors assume that, at time $t$, a player observes information from round $t-d_t$. The two models may appear superficially similar but, in fact, they are fundamentally different: in the former, there may be rounds where the learner receives no information, others where information from many rounds is received at once, but the same piece of information is never received twice; in the latter, the learner always receives one piece of information from some previous round, but may receive the exact same piece of information several times. While the former model of delays has been extensively studied in the literature, the authors' model is much less common, and the authors did not discuss it at sufficient length - a fact which was criticized during the committee discussion phase.

Another issue concerns the fact that the authors seem to ignore several recent results regarding the convergence of asynchronous gradient play in games, see e.g., [7,8] below.

Despite these criticisms, the committee felt that the paper cleared the acceptance bar (albeit marginally so), so there were no objections to an accept recommendation - but with the explicit understanding that the above issues should be included in the camera-ready version of the paper.


*References*

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. 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. Kent Quanrud and Daniel Khashabi, Online learning with adversarial delays, NIPS ’15: Proceedings of the 29th International Conference on Neural Information Processing Systems, 2015.
1. Pooria Joulani, András György, and Csaba Szepesvári, Online learning under delayed feedback, ICML ’13: Proceedings of the 30th International Conference on Machine Learning, 2013.
1. Pooria Joulani, András György, and Csaba Szepesvári, Delay-tolerant online convex optimization: Unified analysis and adaptive-gradient algorithms, AAAI ’16: Proceedings of the 30th Conference on Artificial Intelligence, 2016.
1. Claire Vernade, Olivier Cappé, and Vianney Perchet, Stochastic bandit models for delayed conversions, UAI’ 17: Proceedings of the 33rd Annual Conference on Uncertainty in Artificial Intelligence, 2017.
1. Amélie Héliou, Panayotis Mertikopoulos, and Zhengyuan Zhou, Gradient-free online learning in continuous games with delayed rewards, ICML ’20: Proceedings of the 37th International Conference on Machine Learning, 2020.
1. Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter W. Glynn, and Claire Tomlin, Countering feedback delays in multi-agent learning, NIPS ’17: Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017.
justification_for_why_not_higher_score: The paper had several issues that would not warrant higher exposure.
justification_for_why_not_lower_score: Despite its problems, the paper provided new results which would be of interest to several ML subcommunities.
Decision: Accept: poster