Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper examines the problem of completely decentralised agent cooperation in a Markov game environment, where there is no communication between agents. They propose a stage based learning algorithm to explore an unknown environment using this approach.
main_review: This is an interesting subclass of problem, I found the paper was well written and explained the approach clearly. The authors correctly point out the considerable scaling issues with communication in agent based cooperative tasks that attempt to exchange information between the agents, and since it is easy for those to be intractable, it is very useful to identify alternatives. 

I take mild issue with the claim that there is "no communication" between agents in this kind of approach though - there is, it is the information distributed to all the agents at the beginning of the algorithm in the form of the reward function. The agents then don't rely on any further exchanges of information to achieve a local optimum that achieves a global approximate Nash equilibrium policy. This in no way discredits the approach, and there is an interesting sub-class of problems that can be solved this way (for example American Football´s play books somewhat fit this model), but I would like to see this pointed out in the discussion. There is a danger, especially in simulating this problem, that the reward function contains enough information to in some sense encode the solution, and It would improve the paper significantly if there was a discussion of the size of the information communicated by the reward function, versus the settling time of the algorithm. It would also be nice to see concrete real world examples where this approach is useful, although I appreciate that this is a theoretical paper, making that in some sense somebody else's job.
summary_of_the_review: I think this paper is a useful contribution, and although I don't think the issues I raise are completely minor, they shouldn't be too hard to address by the authors.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors establish a variety of novel theoretical results for Markov team problems. First of all, they present a novel non-asymptotic convergence bound for single-step Markov teams, using a no-regret independent learning variant of stochastic gradient descent (SGD-IX). Secondly, they extend SGD-IX with a stage-based design to arrive at a novel, decentralized MARL algorithm (Stage-based V-learning). For Stage-based V-learning, the authors additionally proceed to establish a novel non-asymptotic convergence bounds that do not depend on the size of the centralised joint policy, but instead just the largest individual action space. The authors also show how their algorithm sidesteps technical difficulties inherent to establishing convergence bounds for Optimistic Q-learning [Jin et al, 2018]. Using a simple matrix team task, as well as a Markov team task as an example, the authors demonstrate empirically that their algorithms can end up selecting favourable Nash equilibria.
main_review: The paper is extraordinarily well written; I did not find any issues with spelling, grammar nor presentation.
The authors provide a variety of interesting theoretical results. 

The O(1/epsilon^4) result from Theorem 2 is particularly exciting. An extension to continuous action spaces (with some reasonable structural assumptions) would be interesting.

The use of a stage-based approach to tackle multi-agent learning non-stationarity is by itself refreshing (even without the perks of establishing unique non-asymptotic convergence bounds), and I expect it will resonate within the deep MARL community.

In section 4, I would suggest using a letter other than \mathcal{L} for denoting the partial sums over stage lengths, as \mathcal{L} is frequently used to denote loss objectives in MARL literature.

To further improve the paper, I believe the authors should compare their empirical results against other methods that aim to tackle nonstationarity in multi-agent learning. These include CTDE algorithms, such as tabular variants of QMIX [Rashid et al] or VDN [Sunehag et al]. This also includes tabular variants of policy-gradient algorithms, such as IPPO [Schroeder de Witt et al]. 

I see two major opportunities for future work:
1. Extend V-learning SGD to Q-learning with function approximation, ideally with theoretical guarantees, but an empirical demonstration would also be extremely interesting
2. Can V-learning SGD additionally benefit from CTDE settings, i.e. can the availability of extra state information during training be exploited? What about parameter-sharing in function approximation settings?
summary_of_the_review: I recommend the paper be accepted as is. The paper's writing and presentation are very clear and polished, and the results are both sound and significant. I expect this paper to stimulate the cooperative MARL community.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Authors tackles the cooperative multi-agent reinforcement learning problem with stochastic dynamics. They introduced V-learning Stochastic Gradient Descent (SGD) with theoretical proofs of convergence to the optimal policy with desired e probability. The resulting sample complexity is O(1/e^4) * Poly (A,S,H), where H is the episode horizon. Authors also empirically tested the algorithm in a toy 2 agent matrix game showing convergence to the optimal policy.
main_review: Pros
+ The paper is theoretically strong. Theorem 4, shows a 60% convergence probability of their algorithm on expectation, yet with two more iterations (if I did the math right) it bumps it to 99%.
+ The sample complexity reduction compared to the previous work is impressive.

Room for Improvement
- The paper is difficult to follow. I recommend pushing more sections into the Appendix so you can explain the existing content well in the main body. For example, Algorithm 2 was mentioned without enough discussion. How certain constants where picked, etc.
- Given the strong promise of the paper, I was underwhelmed with the simulation results. Why did you pick a simple 2 player game? Why not going for something much larger? After all that is the main catch of your bound. 
- For the simulation result, I think you could also calculate he optimal policy for the centralized case using backward dynamic programming in time since your H is fixed. How come you did not include that?

Details
- "Oblivious to the presence of agents" => Does this limit the applicability of the method? For example if multiple agents are trying to do something together, often their location would heavily impact each other.
- O(1/e^4) samples (paper) or episodes (abstract)? While given the fixed H and Poly part of the theorem it does not matter, it would be great to make ti consistent.
- Any thoughts of expanding this to infinite horizon problem?
- recommend using t instead of h for tilmestep.
summary_of_the_review: I think the theoretical contributions of the paper are great and would benefit the community. I was hoping to see much bigger domain in the simulation part. The writing is currently very dense.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies sample complexity bound for finding approximate Nash equilibrium in two-player Markov cooperative games using decentralized algorithms. The authors designed a stage-based V-learning algorithm, which achieves eps approximate Nash equilibrium in $1/eps^8$ episodes. Under the smoothness conditions, such equilibrium is a team-optimal Nash. 


main_review: There are the following problems of this paper. 
- Typically, a Nash equilibrium is required to be a product policy (the players cannot have shared randomness). The policy pairs $(\mu_h^\kappa, \nu_h^\kappa)$ generated by Algorithm 3 is not a product policy, so this is not a Nash-equilibrium. In line 6, the authors propose to use a shared random variable $i$ among all the players (this is essential for the value iteration equation above Theorem 3 to hold; if the value iteration equation does not hold, the whole proof is wrong), and such shared randomness makes the policy correlated. Such a correlated policy is a CCE, but not Nash-equilibrium. The authors can argue that, by Markov inequality, the first step randomness $\kappa$ can be de-randomized, so theorem 1 and 2 may be valid (but these are just single step Markov games). But for Markov games, the later steps' randomness cannot be decoupled by the Markov inequality. 

- Even if the issue can be fixed, the authors just considered two players Markov cooperative games, instead of multi-players Markov cooperative games. It is not clear whether it can be generalized to multi-players games with similar bounds. 


Minor problems: 
1. In the abstract the author wrote that their sample complexity is O(1/eps^4) for Markov team. However, it is O(1/eps^4) for Matrix team and O(1/eps^8) for Markov team. 
2. The paper by Leonardos et.al. 2021 considered "the aspect of exploring the unknown environment" and had a sample complexity guarantee (in the related work section). 



summary_of_the_review: The main theorem is wrong.
review_title: null

Meta-review: This paper presents a decentralized cooperative approach in multi-agents using Markov games theory. After reviewing the paper and reading the comments from the reviewers, here are my comments:
 
- The paper is well-written, quite difficult to follow, but very informative.
- The contribution is clearly stated and the results support it.
- Theoretical results are interesting for the RL community.
- The main concern is about learning the epsilon-approximate Nash equilibrium policy which is a fundamental part of the paper.
Decision: Reject