Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper extends predictive state representation (PSR) for POMDP to multi-agent reinforcement learning (MARL) setting.
main_review: Strength:
The mathematical derivation appears sound and theoretical guarantee is given.
The two versions of the algorithms, MAPSR1 and 2, performed well in MAMuJoCo benchmark.
Weakness:
It needs a lot of background knowledge about PSR, MARL and graph-based approaches to understand the work, though that is inevitable...
Regarding statements like "PSR is more compact than POMDP": POMDP is a problem setting and PSR is one way to solve that. It makes better sense if you specify "belief-state approaches to POMDP".
The reference source for Littman et al. 2001 (NIPS 2001?) is missing.

summary_of_the_review: This paper presents practical algorithms for MARL by utilizing the data-driven dynamic modeling by PSR.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors present a framework and method in which predictive state representations for multiple agents simultatneously acting and interacting within an environment. This is presented in a general way, where predictive states are Hilbert space operators which when applied to sequences of observations and actions appropriately predict the predictions of these state representations. The key advance in this work is to apply this existing PSR framework to networks of agents, with 3 types of agent network: static complete graph (all agents affect all others experience); static non-complete graph (only some agents affect one another); and dynamic non-complete graph (agents affect one another in a time varying way). A number of theoretical results are presented, including PAC bounds for the approximators in the framework.

The authors then present two closely related methods to learn policies alongside these multi agent PSRs in an online way. The first MAPSRL-1 is akin to the independent actor critic (Foerster et al., 2017) and thus may suffer from the apparent non-stationarity of the environment from the perspective of any one agent. MAPSRL-2 addresses this by incorporating the PSR information from other agents into the policy gradient update.

The paper presents a series of experiments based on environments encoded in the  OpenAI Gym MAMujoco system. These are environments presented in previous papers and there are a broad selection of these. 

main_review: The work is clearly explained an the mathematical results and definitions are appropriately used and of a very high quality (by my assessment. One criticism I have is that some terminology could be introduced at the outset to assist the reader (see detailed comments). Another issue is that the language and phrasing is sometimes a little odd and the paper would benefit from a quick grammar check.

Nonetheless, the motivation is very clear to me. The idea of efficiently learning PSRs is a powerful one, and this work applies it to the multi-agent domain introducing some very general ways to account for the other agents' influences on the observations of a focal agent. One repeated theme in recent scalable MARL approaches is how to manage the apparent non-stationarity from the perspective of one agent induced by the other agents adapting alongside. This approach is arguably a natural way to do this, in terms of action conditioned predictions of observations and how these are influenced by other agents.

The methods are evaluated against some very sensible benchmarks, including a PSR method that omits the information sharing between agents part, and a direct independent actor critic that doesn't incorporate PSRs at all. As such the empirical evaluation seems to be sensible and robust to me. Results show a significant improvement over the methods without the newly proposed PSR learning components.

I am satisfied that the work is of a very high quality as far as I can assess it.

## More detailed comments

It's not clear what is meant by this: 

> Learning in this environment is challenging since
these partially observable observations bring the noise.

Or this:

> in the setting where the system model is not known a priori or the
model introduced by the domain expert is biased, it is always beneficial and safer to learn system models and develop policies based on the models.

Is it always beneficial to learn POMDP models, or can model free methods sometimes work more effectively?


In section 3 we start working with operators, and the notation is necessarily quite dense in order to get all the definitions and results in but it would assist the reader to have some guidance on how to read things on first presentation. For instance at the bottom of p3 where you say:
> In this model, predictive state Q t satisfies...

It would be helpful to know that $Q_t$ and $P_t$ are conditional expectation operators. The $\circtimes$ operator at the top of p4 could be better introduced too. I am guessing this is the kronecker product.


The phrasing is sometimes a little odd and the paper would benefit from a quick grammar check. For instance, there are a number of instances of things like this:
> We replace the partially observation o with PSR Q

I am not sure I fully follow what is being shown in Figure 2. Perhaps and example of how to decode one of these plots would help.
summary_of_the_review: The paper presents a clearly motivated and well founded approach for making multi-agent RL more stable and robust (in particular to non-stationarity) by use of predictive state representations that incorporate inter-agent interactions. In my opinion this paper is of very high quality, relevance and novelty.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a predictive state representation (PSR)-based MARL framework. The framework uses a graph representation to model the interactions between agents. Performance bounds are given for the learned predictive state representation.  With the MAPSR, individual policies are trained by replacing the partial observation o with PSR Q. The experiments results show the advantage of the proposed method compared with the baselines experimented in the paper. 
main_review: Strengths:
The paper proses a novel and complete PSR-based MARL method which also scales well with the use of graph structures. The performance of the MAPSR is analized both theoretically and empirically.  The quality of the learned policies are also verified by experiments.

Weaknesses:
I think the paper overall is good. It would be better to see some extensions or future thoughts on the unknown interaction structures which are not always trivial and need to be learned.
summary_of_the_review: The paper gives solid technical contributions and substantial experiments. I recommend acceptance of the paper.
review_title: null

Meta-review: This paper presents an extension of the Predictive State Representation (PSRs) to multi-agent systems, with a dynamic interaction graph represents each agent’s predictive state based on its “neighborhood” agents. Three types of agent networks are considered: static complete graphs (all agents affect all others experience); static non-complete graphs (only some agents affect one another); and dynamic non-complete graphs (agents affect one another in a time varying way). A number of theoretical results are presented, including PAC bounds for the approximations in the framework. The paper also contains a number of experiments that clearly show the advantages of the proposed technique over some related methods.

The reviewers unanimously agree that this is a strong paper, with a solid theoretical and empirical analysis.
Decision: Accept (Spotlight)