Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies a zero-sum team Markov game. In the game, a team of agents compete with an adversary. Agents in the team have the same reward function, and the sum of the team and the adversary's rewards is zero. The paper in particualr looks at a class of potential games. The main contribution of the paper is to propose a set of algorithms to compute a stationary epsilon-Nash equilibrium of the game. 
strength_and_weaknesses: Strength: 

The problem is well-motivated and the paper is written well overall. The proposed approach to computing an approximate Nash equilibrium looks non-trivial and brings in many interesting concepts. The authors also provide a good summary about the related work.

Weakness: 

- Section 3.3 could have been improved to make the main idea clearer. It is unclear to me what is the main advantage of the proposed methods? In particular, why not just solve Q-NLP without the regularizer in the objective function, which gives a Nash equilibrium directly and seems much more manageable than the current formulation?  

- The approach relies on an oracle to tackle a computational obstacle, which may be crucial. This further deepens the question of how meaningful the proposed methods are compared with solving Q-NLP without the regularizer --- now that there's an oracle to use, so supposedly it also simplifies the problem of solving Q-NLP without the regularizer.

clarity,_quality,_novelty_and_reproducibility: Clarity could be improved in some parts of the paper. The results look novel and very technical.
summary_of_the_review: A paper on a well-motivated problem, overall well written but with some issues on the clarifty. Results are comprehensive and very technical, but with some weaknesses that raise questions about how meaningful the results are, which may or may not be crucial.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers multi-agent Markov games; specifically, the problem of computing a Nash equilibrium. Even in normal-form games, it is computationally intractable to compute a Nash equilibrium in two-player general-sum games, much less in games with more players. In this paper, the game is restricted to coalition of players with a common adversary, so-called "adversarial team Markov games". In addition to the case when the coalition shares a common objective, the results extend to the case in which the objectives of the coalition share a common potential function (Markov potential games). 
strength_and_weaknesses: # Strengths
- The paper introduces the first poly-time algorithm to compute a Nash equilibrium in the setting of adversarial team Markov games. Computing a Nash equilibrium is an important practical problem, but unfortunately the general-case is difficult. Therefore, it is useful and relevant to consider special cases such as the coalition considered here.
- The algorithm has good scaling with the action sets of each agent; that is, it scales with their sum rather than the product.
- The techniques used to obtain this result are well described at an overview level and compared to the most relevant related work which is to compute a Nash equilibrium in the analogous normal-form setting. The challenges in generalizing the normal-form setting to Markov game include: nonlinear program with a set of nonconvex constraints, which requires the Arrow-Hurwiz-Uzawa constraint qualification technique.

# Weaknesses
- The type of game considered is very special. It is only a modest generalization of two-player zero-sum games. More practical would be algorithms that have exponential worst-case but still run on practical examples of n-player Markov games. Still, any generalizations from fully cooperative or competitive two-player games are welcome.
- The practical scalability of the algorithm is not evaluated. Although it is polynomial, the number of iterations looks very large from inspection of the pseudocode.  Still, this is a theoretical work, so this isn't too significant of a weakness.


clarity,_quality,_novelty_and_reproducibility: + The paper is written very clearly and is well organized.
+ The novelty is put into context well and is clear.
summary_of_the_review: Based on the above strengths and weaknesses, the paper clearly is in the "Accept" category.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper provides an efficient algorithm to compute the Nash Equilibria in an adversarial team Markov game. Specifially, in this zero sum Markov game, a team of players try to gain reward as much as possible, and an adversary tries to lose reward as less as possible. The authors propose an algorithm called IPGMAX. In this algorithm, all the team players will first do policy gradient descent for several steps, and this procedure returns the team players' policies in Nash Equilibria. Then the algorithm uses a procedure to look for the response of the adversarial policy (to the team players' policies). The authors show that, team players' policies as well as the the response of the adversarial policy form a Nash Equilibria, and the time cost of the algorithm is polynomial, which can be much better than the exponential ones in prior works. 
strength_and_weaknesses: Strength

Looking for Nash Equilibrias in Markov Game is an important task, and reducing the time complexity from exponential to polynomial is also a significant contribution.

Weaknesses

There are many parts not very clear in the IPGMAX algorithm (for details please see the questions below)

My Questions

1. Proposition 3.1 shows that there must exists such a $t^*$, and Corollary C.1 shows that with high probability, there is one such $t^*$ in the randomly chosen set. However, it is still not very clear to me that how you can find this $t^*$ is this set. Do you mean that it is easy (with low computation cost) to check whether $x^{t}$ is good or not? How much is the computation cost here?

2. In line 6 of Algorithm 1, we need to look for the best response of the adversary. What is the computation cost here?

3. In line 7 of Algorithm 1, we need to compute the gradient of $V_{\rho}$. What is the computation cost here?

4. It is mentioned that the IPGMAX algorithm is a decentralized one (which may avoid communications between players), but I am wondering whether line 6 and line 7 in Algorithm 1 could be done without any communications? Do you mean that these steps could be done even if all the players (e.g. the team players) do not know others' policies in the last time step?




clarity,_quality,_novelty_and_reproducibility: I think there are some problems about clarity (see the Questions above).
summary_of_the_review: Overall, I have some questions about the algorithm in this paper, and give the score of "weak accept". I'd like to see the answers from the authors and I will change my score if the answers are convincing. 

=========After Rebuttal=========

The rebuttal explains about the details, and now I can understand how the algorithm works. I believe those details should also be included in the final version, so that the readers can easily understand it as well. 

My remaining concerns (which are also mentioned by the other reviewers) are about the existance of the oracle and whether the given complexity upper bound is tight. I think some further works about the tightness could be done in the future. 

Overall, I agree that this work is an important step in efficiently looking for the Nash Equilibria in Marcov Games, and I would like change my score to "accept".
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: (a) Summary: This paper proposes a technique by which a team of agents playing a zero-sum Markov game against a single adversary can compute a Nash equilibrium.  The procedure is asymptotically efficient (polynomial in the largest action set, rather than in the size of action profile set).

(b) Strengths: The reviewers agreed that the scaling of the algorithm is a significant improvement.  The algorithm is a non-trivial contribution to a well-motivated problem.  There was a consensus that the paper is clearly presented (after the rebuttal period; one reviewer initially had some clarity concerns).

(c) Weaknesses: The situation studied is a very special case.  One reviewer also had concerns about the practical efficiency of the algorithm compared to its asymptotic scaling.
justification_for_why_not_higher_score: n/a
justification_for_why_not_lower_score: Two reviewers were were very positive, and the content of the marginally-negative reviewer's was very similar.  The reviewers agreed that the approach was non-trivial and a significant improvement on the state of the art.  The problem is a special case, but not contrived.
Decision: Accept: notable-top-5%