Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper considers the Partially Observed (general-sum) Markov Game (POMG) model, and proposes a sub-linear regret online learning algorithm that achieves a game theoretic equilibria. The algorithm is based on optimism ideas, and an assumption of weak revealing POMGs is made (which was first made in [27,37], and is quite strong actually - it implies full observability for point state distributions. The proposed algorithm achieves regret that grows as \sqrt{K}, K=number of episodes.  
strengths_and_weaknesses: Strengths: The paper is nicely written, easy to understand and addresses a difficult problem.

Weaknesses: 
1. I think this paper is just a bit beyond incremental, builds as it does on [27] and [37].
2. There is a more fundamental issue whether these results are interesting at all: in a game setting, there are two types of results that are interesting: (i) offline (centralized or decentralized) algorithms that find the equilibrium, and (ii) online decentralized algorithms that minimize the regret w.r.t. the equilibrium. This paper proposes online  centralized algorithms for POMGs, which means in a game setting individual players can't really learn in a decentralized manner, i.e., learning of the equilibria is really happening via  centralized algorithm, which is hardly interesting. Actually, once you assume that an equilibria of the game can be computed by some algorithm, the results in this paper are hardly surprising building as they do on results for POMDPs in [27] and [37]. Thus, I would say the problem formulation in this paper is not interesting enough.
3. Any way to do an empirical evaluation of your proposed algorithms.
questions: Q.1 Is there a way to design decentralized learning algorithms?
limitations: No limitations mentioned.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper considers a Multi-Agent Reinforcement Learning problem where participants have private observations that are only partially available to others. In a setting where a central learner can control all players' actions and aims to achieve an equilibrium, the authors develop algorithms to approximate equilibria with a sample-efficiency bound. Moreover, in a setting where a single player aims to optimize their reward against adversarial opponents, they also create an algorithm to achieve a sublinear upper regret bound under a weak definition of the regret.
strengths_and_weaknesses: Strengths:

1. This is the first work that develops a sample efficiency algorithm to learn a large class of Partially Observable Markov Games. Moreover, the polynomial sample complexity is strong.

2. The motivation of their algorithms is clear.

Weakness:

1. For the setting with adversarial opponents, it is better to give more intuition of the reason to use their new regret. 
        
2. Their algorithms seems to be time-consuming.
        
3. There might be some typos and unclear parts that may affect understanding. Please see bullet 2 in the question section for more details.
questions: 1. Can I have more interpretation of why the regret in Section 5 is used. Besides, are there any practical applications of this new version of regret? 
        
2. There might be some typos and unclear parts. For example, in the definition of the POMG tuple, does $\mathbb{T}$ means $\mathbb{P}$? Moreover, in Definition 6, I wonder what the feasible set of strategy modifications is. Does it contain all maps from the deterministic action set to itself? 
limitations: I think there is no potential negative social impact of the 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: The paper identifies a rich subclass of  Partially Observable Markov Games (POMGs), weakly revealing POMGs, and proposes algorithms for finding approximate Nash equilibria for them. The algorithm is proven to be sample efficient in this kind of game.
strengths_and_weaknesses: Strengths:
1. The newly identified weakly revealing POMGs is interesting and practical.
2. The proposed algorithms are intuitive and interesting. The theoretical results seem sound.
3. The paper is well written, and the notation and definitions are clear.

Weaknesses:
1. Corollary 8 and Corollary 10, "with probability at least 1/2", I do not think a probability of at least 1/2 is enough.
2. As stated in the paper, "Algorithm 1 is computationally inefficient in general due to the steps of optimistic value estimation and equilibrium computation". By the way, this does not harm the significance of the paper, and thanks to the authors for declaring the weakness.
3. Lack of empirical results. Some experiments may help the readers to understand the algorithms better.
4. line 90, $\mathbb{T}$ is not defined, while $\mathbb{P}$ is not introduced.
5. line 113, the definition of $\pi_i$ is not a bit informal.
questions: In Algorithm 1, Why is the output strategy uniformly sampled from past strategies?
limitations: None.
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 is the first attempt to theoretically analyze the general-sum Markov games under partial observability. The contributions of this paper are as follows:
- It identify a rich subclass of POMGs, namely, the weakly revealing POMGs, which is statistically tackable (this is necessary as the POMGs are intackable in general as shown by the hardness results);
- It proposes an algorithm that combines the optimism-in-face-of-uncertainty principle and MLE;
- The proposed algorithm is shown to be efficient in the self-play setting, meaning that we can control all the agents' policies;
- The results are extened to the adversarial setting, which is novel and also interesting.

I believe that the topic of this paper is very interesting and is very relevant to the ML and RL community.
strengths_and_weaknesses: Strengths: 
Identifying a rich sub-class of tackable POMGs:
RL problems under partial observability are known to be statistically intractable in general, even in the single-agent case, mainly due to the non-Markovian nature and resulting curse of history. However, the hardness is in a worst-case fashion. Then, it is natural to identify certain natural (well-motivated) structural assumption that empowers efficient learning. 

Instead of assuming the perfect-recall structure of Imperfect Information Extensive-Form Games (IIEFG), this paper considers the weakly revealing POMGs, extended from the single-agent scenario. To me, the two assumptions are natural. Intuitively, the assumption ensures that a short window of recent observations contains certain amount of information of the latent states, whose idea is natural and common under the partial observability [1-3]. Interestingly, in terms of the challenges from multi-agent scenario, the paper shows that this condition only requires to be true for the joint observations, which is new to my knowledge. I believe that this paper provides enough insights and is a good starting point for the study of POMGs.

Algorithmic novelty:
I find that the proposed algorithms are quite clean, following the standard optimism-in-face-of-uncertainty principle. Although the algorithm is not computationally efficeint, but it seems this is a general problem on the literature, so I think this is acceptable. 

The key design of the confidence set is extended from the single-agent counterpart [4] that contains the models whose likelihood is roughly consistent on the historical data (in the sense that itis close to MLE), which is also natural. The use of MLE seems to be extended from the recent result in single-agent setting [4]. But the game nature requires extra efforts to deal with, which accounts for the use of subroutines in different settings. This again is new and is complementary to the single-agent counterpart. 

Weakness:
While I am satisfactory with the paper, I still have some minor comments and questions.

1 I think some examples or hardness results are helpful to motivate the assumptions used in this paper, for a clearer presentation.

2 The adversarial setting is interesting but it seems that the paper only considers the Assumption 1, which is true only for undercomplete case (O>=S). I am wondering whether efficient learning is possible for the overcomplete case? 

Overall, I enjoyed reading this paper and I think it contains enough insight, and interesting and non-trivial results, as compared to the single-agent works.

[1] Du, S., Krishnamurthy, A., Jiang, N., Agarwal, A., Dudik, M., & Langford, J. (2019, May). Provably efficient RL with rich observations via latent state decoding. In International Conference on Machine Learning (pp. 1665-1674). PMLR.
[2] Efroni, Yonathan, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. "Provable reinforcement learning with a short-term memory." arXiv preprint arXiv:2202.03983 (2022).
[3] Golowich, Noah, Ankur Moitra, and Dhruv Rohatgi. "Learning in Observable POMDPs, without Computationally Intractable Oracles." arXiv preprint arXiv:2206.03446 (2022).
[4] Qinghua Liu, Alan Chung, Csaba Szepesvari, and Chi Jin. When is partially observable reinforcement
learning not scary? arXiv preprint, 2022a.

questions: See weakness part.
limitations: yes
review_title: null

Meta-review: metareview: While most reviewers were positive about the paper, one reviewer expressed concerns on the assumption and the technical novelty of the paper. After reading the discussion, the AC believes that the main assumption of weakly revealing is standard. This is commonly used in control and learning in HMMs/PSRs (we just cannot learn efficiently without these type of assumptions). The AC is also satisfied by the authors response to the technical novelty. The results presented in this paper is certainly more than just replacing max by min-max in the Bellman equation. 

In summary, the AC would recommend for acceptance in this case.  
confidence: Certain
Decision: Accept