Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of multi-agent RL under state uncertainty, by formulating the state uncertainties as an adversary and formulating the problem into a Markov game. Sufficient conditions are established under which an equilibrium exists for such a Markov game. Furthermore, both a value-based method and a policy-based method are proposed in search of such an equilibrium. Numerical experiments are also conducted to demonstrate the effectiveness of the proposed methods.
strength_and_weaknesses: Strength: 

I appreciate the paper's effort in modeling the state uncertainties as part of the Markov game and proving the existence of the equilibrium before proposing algorithms to find it. The motivation for studying state uncertainties is also clear and well articulated. Though the methods itself do not come with finite-time guarantees, having asymptotic convergence looks good enough for this challenging problem, and the empirical evidence provided in Section 4 looks convincing. I also appreciate the author's effort in highlighting important core arguments before presenting the main theorems in Section 3.2. 

Weakness:

There are some assumptions being posed with concrete context provided to the reader. For example, in Assumption 3.11, the last condition is posed without any explanation on why this is needed for the convergence of the RMAQ method. It is not immediate to me why this condition relates to the convergence of the Q-learning type method. 

Minor Comment:
Can the author comment on the per-iteration complexity of implementing the RMAQ method? Specifically, how does it scale with the number of agents in the system (does it suffer from the exponential blow-up in the state-action space)? 
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper has a clear motivation of the studied problem, and all the assumptions and main theoretical results are stated clearly. 

Quality: The formulation of the MARL problem with state uncertainty into a Markov game, together with the structural results on existence of equilibrium is one of the key and novel results in this paper, which I like the most. The experimental results on the actor-critic type method also look appealing. 

Originality: Both the theoretical and experimental part of this paper looks original. 
summary_of_the_review: This paper provides a rigorous formulation to a problem (MARL with state uncertainties) that is gaining interest in recent literature. The proposed Q-learning type method, although not scalable in its current form, does come with convergence guarantees. The proposed actor-critic type method enjoys favorable empirical performances. I believe this paper contains enough original contributions to this field.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers multi-agent RL setting where agents' observations are corrupted at test-time. The paper proposes a novel optimization framework that models adversarial perturbations on agents' observations as additional players in the underlying Markov game. The authors provide characterization results for the considered framework, deriving a version of Bellman conditions for this framework, as well as a sufficient conditions for the existence of a robust equilibrium. They further propose two algorithms for finding equilibrium policies, based on Q-learning and actor-critic approaches, and experimentally test their efficacy in standard MARL environments. 
strength_and_weaknesses: Arguably, the main strength of the paper is that it studies what appears to be a novel setting - robustness to perturbations of agents' observations in MARL. The results include a theoretical characterization of the formal setting, algorithmic approaches for deriving equilibrium policies, and experimental validation of the proposed algorithms. In other words, the paper contains a rather complete set of results for this framework. Having said that, I have several concerns about the following submission, listed below:   
- First, it is not clear to me whether this optimization framework leads to optimally robust policies. More specifically, considering only stochastic stationary policies, as assumed in the preliminaries, may not suffice in this case. Namely, an agent/victim decides on its actions based on corrupted observations, which are correlated across time since adversarial perturbations have a bounded budget and have a functional form. Hence, agents can benefit from having history-dependent policies, e.g., form a belief about the underlying state. Due to this, it is also not clear that the equilibrium notion in Def 3.2 is the right solution concept - shouldn't agent be deciding based on their beliefs about the underlying state, and if so, why is it important to consider a robust version of MPE (Markov perfect equilibrium)? 
- Some parts of the formal setting/characterization results may not be precise enough. I tried to check some of the results, but the notation is quite confusing. I give examples in the next section. Some of the results are also not clear to me. E.g., in the proof of Prop. 3.5., I didn't follow why the 3rd equation is due to the NE of the corresponding EFG - why  are $\pi_*^v$ and $\rho_*^v$ important for this inequality and why does the inequality hold if we have $v^i = [1, 1, 1, ..]$ and $u^i = [0, 0, 0, ...]$? 
- I'm puzzled by potential implications of Theorem 3.8 and Theorem 3.9. Wouldn't they imply that there always exists an RE? If $v^*$ always exists and given Theorem 3.9, can't we  find an equilibrium by solving the EFG corresponding to $v^*$? If yes, why is Theorem 3.10 important since it covers very specific case of the setting? If not, how does the algorithm from section 3.3 work? It would be helpful to have an additional discussion that compares the theoretical aspects of this work to those from Hu & Wellman (2003), including the assumption needed for convergence (e.g., assumption 3.11c this work vs assumption 3 from Hu & Wellman (2003)). 
- Robustness in this paper is measured against adversarial perturbations that have a specific form, given via function $f$. I'm wondering whether the corresponding robust policies generalize across different functions $f$. Judging by Fig. 12, they don't appear to be consistently better than the baselines. In practice, we presumable wouldn't know the exact form of adversarial perturbations that will occur at test-time, so it would be good to include results that show performance under noise models which were not used in training. Furthermore, why weren't policies that optimally disturb the environment trained for each algorithm separately (keeping these algorithms fixed)? It seems that the current adversarial perturbation policies may favor RMAAC, especially if an equilibrium point was not reached in the training phase. 
clarity,_quality,_novelty_and_reproducibility: - Quality: The set of results are interesting at the fist glance. However, the formal setting may not be adequate for the problem at hand as explained above. In addition, it is not clear whether the characterization results are entirely precise/correct. The experimental results could also be further expanded, as I indicated in my previous comments.  
---
- Clarity: In my option, the paper can be considerably improved in terms of clarity. I was able to follow the main ideas, but the problem is that the technical content was a bit hard to follow due to confusing notation. For example, Definition 3.3 uses $v_*$ notation, without stating what it refers to - does it refer to the RE quantities in definition 3.2 or to the equilibrium of the corresponding EFG? Note that in the proofs $v^*$ is used for EFG equilibria. Similarly, it seems that Theorem 3.13 considers deterministic policies without explicitly stating this, whereas the setting of the paper uses stochastic policies. Also, the theorem considers continuous actions, without stating this, whereas Eq. (4) considers discrete actions. Apart from that, the submission contains quite a few typos. 
---
- Novelty: The problem setting appears to be novel and builds on recent works in single-agent adversarial RL and robust multi-agent RL, complementing the latter. This is arguably the main strength of the paper. 
---
- Reproducibility: In terms of experimental results, the paper provides a sufficient description of the experimental test-bed. One part that could be improved is the description of the network architectures used in the novel algorithms. This seems to be somewhat hidden in the appendix. In terms of the theoretical results, as I explained in my comments above, some of the proofs would benefit from more detailed descriptions. 
summary_of_the_review: The paper explores a novel MARL setting, and reports a set of results that is of potential interest to researcher working on robust RL. On the flip side, the current submission could benefit from additional discussion points that would clearly explain why more general settings are not needed in this setting. The current set of results, although looking promising, could be extended. The clarity of the paper could be improved as well.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work investigates the robustness of MARL under state uncertainty. The authors try to formally define the state uncertainty problem and provide a theoretical analysis. Based on the state uncertainty formulation, two algorithms (RMAQ and RMAAC) are designed to improve the robustness of MARL where there is state uncertainty.
strength_and_weaknesses: Strength:
- The authors provide a theoretical analysis of the MARL state uncertainty problem, which provides a theoretical base for the two designed algorithms. 

Questions and concerns:
- In the evaluation section, it seems the results are based on a fixed mean and variance of the gaussian noise. How does the proposed algorithm perform under magnitude of perturbation compared to other algorithms?
- In the evaluation section, the attack policy seems only be the one trained with RMAAC, how does the algorithm perform under other types of attacked proposed in the existing literature?
- This might be within the scope of the work, but is it possible that the proposed algorithms find a Robust Equilibrium that is sub-optimal (e.g. if the problem has multiple RE)? 
- What happens if the team only receive one single team reward at each time step? Can the current formulation still work?


clarity,_quality,_novelty_and_reproducibility: The manuscript is overall easy to follow. Proper examples are provided to help the readers understand the context and problem. Algorithm code is provided so it should be reproducible.

summary_of_the_review: This work is overall interesting as it is looking at an important problem to improve the robustness of MARL. I think further improving the evaluation section of this work can improve its quality. See above for more details.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper develops a robust MARL framework that considers state uncertainty. The paper first formulates the MARL problem with state uncertainty as MG-SPA and develops theoretical contributions, including the new solution concept of Robust equilibrium and the equilibrium's existence. Then, based on the Bellman equations of MG-SPA, the Q-learning method (RMAQ) and actor-critic method (RMAAC) are developed. Finally, evaluations in the two-player game and MPE show robust performance against the adversaries' perturbations. 
strength_and_weaknesses: **Strengths:**
1. This paper develops important theoretical contributions based on MG-SPA. 
2. The algorithms are also developed in a principled way based on MG-SPA, and RMAAC shows the scalability. 
3. The paper is generally well-written and conveys the methods clearly. 

**Weakness:**
Because this paper's contribution focuses on robustness, adding robust MARL baselines in the evaluations would strengthen the paper.


**Questions:**
1. In Section 3.1, using the same notation $i$ for the adversary can be confusing compared to the agent $i$. Following the consistency, what about using $\tilde{i}$ for the adversary?
2. Which perturbation behaviors did adversaries learn in the MPE experiments (i.e., the amount of noise in the linear and Gaussian noise formats)?
3. How is the robustness performance affected by varying $\epsilon$?
clarity,_quality,_novelty_and_reproducibility: **Clarity:** The paper is generally well-written and conveys the main insights well.  
**Quality & Novelty:** I agree that the framework of MG-SPA is new, and its related theoretical contributions are novel.  
**Reproducibility:** The source code is provided in the supplementary material to reproduce the results.  
summary_of_the_review: Overall, I have a positive evaluation of this paper because the paper formalizes state uncertainties as MG-SPA and develops its theoretical and practical contributions. However, I have a concern regarding the absence of robust MARL baselines, and I will make a final decision on the recommendation after the authors' response.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper introduces a theoretical framework for robustifying multi-agent reinforcement learning against adversarial perturbations of the state. The topic is highly relevant and most of the reviewers saw clear merit in the theoretical contributions of the paper. There is also some amount of experimental work. The paper contains both an extensive amount of theory and an empirical method that uses a novel robust policy gradient for policy improvement.

There was a considerable amount of discussion between the authors and the reviewers that managed to address some of the concerns. However, the changes introduced by the authors also led to follow-up questions and ultimately there remained sufficient unresolved questions (see in particular “Justification For Why Not Higher Score” below) for me to recommend a resubmission of the work at a future venue. I do think the paper could be included if there is sufficient space, assuming that the open issues can be addressed in the camera ready copy or through the scientific community in follow-up work.


justification_for_why_not_higher_score: There were some unresolved reviewer concerns from one of the reviewers regarding the specific assumptions required for the theory of the paper to hold.
A major open concern is around history dependent policies, which is currently not at all covered in the paper and could potentially change both the theory and the experimental results.
Specifically, in the updated version of the paper, “h” is now treated as a parameter and all the assumptions have to be satisfied w.r.t. this parameter. E.g., the assumption 3.4.(4), which appears to be critical for the theory, making the theory even more restrictive, if for nothing else then because the "effective" state space becomes larger. 
Another unresolved / unclear aspect is that it now appears that the agents, including the attacker, may need to coordinate on h; at least this is what I would now conclude from the new definitions of value functions. 

So to summarise: To address some of the reviewers’ concerns the authors had to make substantial changes to the paper which in turn created more follow-up questions. Some of these are substantial enough to warrant a new review of the entire work. While this might seem unfortunate I am optimistic that this process will strengthen the paper overall. 

justification_for_why_not_lower_score: NA
Decision: Reject