Reinforcement Learning under a Multi-agent Predictive State Representation Model: Method and Theory
Authors: Zhi Zhang
Zhuoran Yang
Han Liu
Pratap Tokekar
Furong Huang
Venue: ICLR 2022 Spotlight (2022)
Keywords: Multi-agent Reinforcement Learning
Predictive State Representation
Dynamic Interaction Graph

Abstract: We study reinforcement learning for partially observable multi-agent systems where each agent only has access to its own observation and reward and aims to maximize its cumulative rewards. To handle partial observations, we propose graph-assisted predictive state representations (GAPSR), a scalable multi-agent representation learning framework that leverages the agent connectivity graphs to aggregate local representations computed by each agent. In addition, our representations are readily able to incorporate dynamic interaction graphs and kernel space embeddings of the predictive states, and thus have strong flexibility and representation power. 
Based on GAPSR, we propose an end-to-end  MARL algorithm that simultaneously infers the predictive representations and uses the representations as the input of a policy optimization algorithm. Empirically, we demonstrate the efficacy of the proposed algorithm provided on both a MAMuJoCo robotic learning experiment and a multi-agent particle learning environment.

Published as a conference paper at ICLR 2022
GRAPH- PREDICTIVE STATE REPRESENTA- TIONS FOR MULTI-AGENT PARTIALLY OBSERVABLE SYSTEMS
Zhi Zhang' Zhuoran Yang" Han Liu Pratap Tokekar* Furong Huang"
University of Maryland, College Park Yale University Worthwestern University
1 1zhi 2hang576389gg com, ('furongh, ttokkarr @umd eduu
2 2zhuoran. yangeyale. Shenlin@@orrhweseern... edu
ABSTRACT
We study reinforcement learning for partially observable multi-agent systems where each agent only has access its own observation and reward and aims maximize its cumulative rewards. To handle partial observations, we propose graph- -raph-assisted predictive state representations (GAPSR), a scalable multi-agent representation learning framework that leverages the agent connectivity graphs to aggregate local representations computed by each agent. In addition, our representations are readily able to incorporate dynamic interaction graphs and kernel space embeddings of the predictive states, and thus have strong flexibility and representation power. Based on GAPSR, we propose an end-to-end MARL algorithm that simultancously infers the predictive representations and uses the representations as the input of a policy optimization algorithm. Empirically, we demonstrate the efficacy of the proposed algorithm provided on both a MAMuJoCo robotic learning experiment and multi-agent particle learning environment.
INTRODUCTION
In partially observable decision-making systems, it is pivotal for the agents to infer the latent state of the system from past observations. The predictive state representation (PSR) (Littman al., 2001) is a representation of the history by a vector of predictions of set of tests conditioning on the history. In particular, history is sequence of part observations and actions. A test is sequences of future actions and future observations, which is true if and only if all the observations occur, given that all the actions taken. Each entry of the predictive state of representation of is given by the conditional probability that the corresponding test holds true given that history. A fundamental assumption of PSR model is that these representations of the history are sufficient statistics for predicting future observations and thus are able to represent the underlying state which is unobserved (Littman et al., 2001; Hefny et al., 2015; Sun al., 2016). A key feature of PSR is that it only involves observable actions and observations and also encodes the latent state. Thus, the system dynamics can be recovered from data without resorting to the estimation of the unobserved latent states. Furthermore, using kernel embeddings of conditional distributions, PSR can be embedded into reproducing kernel Hilbert spaces (RKHS) (Boots al., 2013), which further enhances the representation powerful of PSR. Furthermore, Littman et al. (2001); James & Singh (2004); Singh al. (2012) shows that PSR offers an alternatively more compact state representation than POMDP models. Therefore, PSR is considered as a powerful representation learning tool and has been used as an indispensable component of various model-based single-agent reinforcement learning methods (James& & Singh, 2004; Boots et al., 2011; 2013; Hamilton et al., 2014; Sun et al., 2016; Hefny et al., 2015; 2018a).
Furthermore, when it comes to multi-agent systems with partial observations, is desirable to construct predictive states for multi-agent reinforcement learning (MARL). However, directly extending single- agent PSR would require building tests based on joint observations and joint actions. As a result, learning the PSR involves tensor decomposition which is computationally prohibitive (Chen et al., 2020). Moreover, another drawback of such an approach is that oftentimes the agents only have local observations. Furthermore, in multi-agent systems, the observations of each agent influenced by the actions of other agents. As a result, the representations should also take the other agents into account. Specifically, we aim address the following question:

---

Published as a conference paper at ICLR 2022
Can we construct multi-agent predictive representations based on local information for reinforcement learning?
In this work, we provide a positive answer to this question. Specifically, we propose new framework of multi-agent PSR named as Graph-Assisted Predictive State Representations (GAPSR), which utilizes local information possessed by each agent to construct scalable representations. Specifically, we assume each agent has local observations but is able to observe joint actions. Let be the number of agents. For any agent i, we first construct y primitive interaction predictions (eee via single-agent PSR, where Qi.j is constructed using agent i's local observations and agent j local actions. Then agent i's final predictive representations qi is obtained by aggregating {qi., Jejn] according to the underlying agent connectivity graph which characterize the proximity among agents. Finally, these graph assisted representations are used as the proxy of state variable and fed into a standard MARL algorithm, e.g, agent actor-critic for decision making.
Our GAPSR framework enjoys a few desired properties. First, GAPSR aggregates the information about other agents via the agent connectivity graph, which encodes the interaction among agents. Such an aggregation mechanism enables us to implement GAPSR on a single-agent level while maintaining other agents' interactions through the encoding of the interactive graph topology. Second, the GAPSR of each agent involve the actions of all the other agents connected to that agent. In other words, GAPSR correctly captures the non-stationarity caused by the other agents' actions. Besides, the agent connectivity graphs can take various forms. In particular, we build our model under three common graphs, namely static complete graphs, static non-complete graphs, and dynamic graphs, covering as many real-world scenarios as possible. Third, utilizing kernel embedding of conditional distributions, the predictive representations lie in RKHS with strong representation power. Finally, GAPSR are readily to be incorporated into any state-of-the ofrt-e--rttttttto MARL algorithm as proxy of the state variable in an end-to-end fashion. Thus, we believe that GAPSR could be promising representation learning framework for multi-agent partially observable systems.
Finally, we implement instantiation of the proposed algorithm that combines GAPSR with multi- agent actor-critic, where we simultaneously learn GAPSR and the agents' policies in an end-to-end manner with fully differentiable neural network structures. We test our algorithm through systematic numerical experiments on MAMuloCo robotic learning experiments (de Witt et al., 2020) and multi- agent particle learning environments (Ryu al., 2020), and compare our proposed method against two baselines as detailed in Section 6. The results demonstrate the efficiency of our method.
2 RELATED WORKS
Partially Observable Environment. Real-world agents often experience situations that the observed signals are aliased and do not fully determine their state in the system. This is particularly true for multiple agents environments where agents have partial observability due limited communication (Oliehoek & Amato, 2016). In accommodation to the partially observable environment, POMDP has been adopted by Kaelbling al. (1998), and the algorithms (Kaelbling et al., 1998; Cassandra, 1998; Thrun, 1999; Pineau et al., 2003; Poupart & Vlassis, 2008; Platt Jr et al., 2010) for determining an optimal policy have shifted to using the probability distributions (belief state) over the state space instead of exact state space. In general they have high complexity or suffer from local optima. Moreover, the most common POMDP policy learning assumes the agent has access to priori knowledge of the system. The access to such prior knowledge has a premise that the agent has considerable domain knowledge (Kaelbling et al., 1998). However, it is expected that the real-world agents learn the system model and thus a planning policy further without knowledge of the domain.
Overview of PSR. Littman al. (2001); James& & Singh (2004) introduced the PSR over an expressive and robust framework for modeling dynamical systems and defined PSR as a representation of state by using vector of predictions of fully observable quantities (tests) conditioned on past events (histories). A predictive model is constructed directly from execution traces in the PSR framework, utilizing minimal prior information about the domain. The PSR paradigm subsumes POMDP as special case (Littman et al., 2001). PSR is considered much more compact than POMDP (Aberdeen et al., 2007). The spectral learning method has been proved to show success for learning the PSR (Boots et al., 2011: Jiang et al., 2018). There are other classes of dynamical system learning algorithms that are based on likelihood-based optimization or sampling approaches (Frigola et al., 2013), but they are prone to poor local optima. The spectral learning represents the estimated state by sufficient statistics of future observations and estimates the model parameters by method of moments. However,
2

---

Published as a conference paper at ICLR 2022
this line of algorithms is hard to incorporate prior information (Hefny al., 2015). Thus, Hefny et al. (2015; 2018a) introduce the supervised learning method to learn PSR and proves its convergence. Although many works study PSR in discrete action space (Hsu et al., 2012: Siddiqi et al., 2010; Boots et al., 2011), Boots et al. (2013) propose Hilbert space embedding (HSE)-PSR to deal with continuous actions. Hefny et al. (2018a) transform (RFF) and built a more principled generalization of PSR to deal with high dimensions. However, all of these studies aim for the single agent scenario.
approximation of HSE-PSB by Random Fourier
PSR and RL. The predictive states estimated by the PSR are considered as states in a fully observable Markov Decision Process so that the value function is learned on these states. This line of work has been done in the single-agent environment (Boots Gordon, 2010; Boots et al., 2011: Hamilton al., 2014; Venkatraman et al., 2017; Hefny al., 2018b). Especially, Hefny et al. (2018b) propose the recurrent predictive state in the RNN network. Moreover, the learning PSR and policy functions connected with the end-to-end training.
MAPSR and MARL. A close related work Chen et al. (2020), which proposes a multi-agent PSR n-way tensor, where is the number of agents. As result, learning the
model that is formulated parameters is achieved by decomposing the n-way tensor, which becomes computationally prohibitive when the number of agents is large. Moreover, it seems challenging to incorporate benign structures such as sparsity into the model, as doing so leads to a more complicated set of moment equations. Furthermore, our work belongs to the vast literature Games. See, e.g., Lyu & Amato (2020); Son et al. (2019); Zhang et al. (2019); Rashid et al. (2018); Foerster et al. (2018); Lowe al. (2017); Baker et al. (2019); Yu al. (2021) and the references therein. Also see Zhang et al. (2021); Gronauer & Diepold (2022); Canese et al. (2021) 1) for recent surveys MARL. Recent works propose more sophisticated deep MARL algorithms for multi-agent problems under the paradigm of centralized training with decentralized execution (Zhou et al., 2020; Sunchag al., 2017; Lowe et al., 2017; Foerster et al., 2018; Rashid et al., 2018). Our work seems not directly comparable to these works as our goal is to learn good representations in the partially observable multi-agent systems via model-based RL, whereas most of these works adopt model-free methods or focus on Markov games without partial observations.
MARL for (partially observable) Markov
3 BACKGROUND: SINGLE-AGENT PSR
In this section, we introduce the background on single-agent PSR. Also see $A.1 for more detailed
introduction.
Predictive State Representation (PSR). A prediction of state is defined as the conditional probabil- ity of seeing a test's observations in sequence given that actions of the test are taken in sequence from a history (Littman et al., 2001). Givn finite observation space O (o O) and action space A (a A). test of length at time f, is defined as a sequence of action-observation pairs that starts at time t t
and ends at time t + k- - 1, {(), at) }
for, at Ot+1, a++1. ... Ot, ai. OL+k-1, a(+b-1) 1] pairs that start from the beginning of time
A history, at time is sequence of [=t
and ends at time i 1, {(o,, ]=]== (01, a1. O1, Gt 0.-1: ()-1)-
Hilbert Space Embeddings of Predictive State Representations. In this work, we are interested in extending PSR to decision makings of controlled systems with continuous actions. So we use the model introduced by Hefny et al. (2018a). In this model, predictive state qe and extended predictive state pa satisfies
o = Elv Iof; vf),
P&Lt = El5i K7: v.',,
(1)
(i.e.. qe and Pt are conditional linear expectation operators which maps to the conditional expectation of future observations), where
v = $o 1++k11
: = (===(((a))=t)) 1+*-1).
(2)
feature maps by kernels ko. kA over future observation and action features. The extended predictive state compared to predictive state adds one more pair of {(o++k: o++))} to the prediction. The Et and En are the corresponding extended feature maps, which satisfy
E vi & of ç = ui @ of.
(3)
Here of (or) and of &h (ax) are the shorthands for one time feature map by ko and kig- We
use & to denote the transposed Khatri-Rao product for two matrices with the same number of rows, and each row of the resultant matrix is the vectorzied outer product of the corresponding row vectors
3

---

Published as a conference paper at ICLR 2022
in the two matrices. Also,
(4) to define set of features extracted from previous observations and actions (typically from fixed length window ending at 1).
= (f(o, af}=))
3.1 NOTATION OF PSR FOR MULTI-AGEN SETTING
In the subsequent section, we will bring the HSE-PSR model to the multi-agent settings. In the following, we introduce the notation for the multi-agent setup. For any agent i in an n-agent system, given a set of kernels {ko, J / 1 (ka, Vi=1 for every agent, we define agent i's feature maps using the single-agent PSR presented in the previous section. In particular, for all i E [n], we let v and Vi, defined as in (2) using agent i's local observations and actions, respectively. Similarly, we let S2, and Si, be defined in (3), and let of, and &f,; be defined using 6o, and Po.- respectively. Furthermore, for all i.j E [n]. we let t be defined as in (4) using the observations of agent and the actions of agent Moreover, and extended predictive state, whose definitions will be presented in the next section.
the qr and pt. to denote its predictive state
4 DYNAMIC INTERACTION GRAPH FOR GAPSR MODEL
Many works have considered graph representation of the multi-agemt network (Liu et al., 2020b; Ryu et al., 2020). In general, the relationship between agents is characterized by undirected graph. We introduce dynamic interaction graph to represent the GAPSR by considering the interaction between agents.
Definition 1.
Let G = (V, E), including the set V of nodes and set E of the edges. Each node represents the agent entry, and the edge represents the relationship between the two adjacent agents.
Here suppose the graph structure is given, that means the number of nodes (n), the number of edges (m), the edge weights, and the maximum number degrees (k) are available to us. We think that this kind of presupposition is very reasonable because in the real world, for example, there are multiple robots; we can quickly get the geographic position of the robots through sensors, then calculate the structure of the graph formed by them.
4.1 STATIC COMPLETE GRAPH
We starts with a static complete graph Ge, where the relationship between nodes are invariant to time change. A complete graph has m = n - 1 edges, where m = -F). For each agent, we can represent PSR by considering other agents" interactions by
q = (fqr.1))) 1|=
(5)
same for Pr. To consider the interactive behavior between agents, we introduce two additional notations qra. and Pr,.j- Let {(i,)) represents a pair of agents on n multi-agent system. The qr primitive predictive state of i's observation (v)P)) by intervening agent j's action (15t,)
and observing agent i's observation history and agent j's action history (wf,,.). and Pt,s.j is the extended counterpart, where they satisfy the relationship for single agent
(1)
(6) i = j. then it becomes an exact single agent scenario. Similarly, we use the same approach to represent Pt. shown in (5). Each agent's 's PSR qr, and extended PSR Pt. are modeled by fully considering all other available agents.
Criigthff = E[vh ii vi, Pt.i.i C[E2,,15, wi V.agl
Based on equation (5), in practice, estimating qr, and pr. denoted as q., and Pr,: requires us to get J...j and Pr,c. at first
4.1.1 ESTIMATION OF qr,ij AND Pr.cj
To estimate the P. and qi for just one agent, Hefny et al. (2018a) use the supervised learning method.
They show that qi M wat Cee (C jot AT) -1, where M A: is linear operator that satisfies E[A B b: C = cj = MAIB;eb, and Cxy = E[ @ <(Y) ] is the uncentered covariance operator, and Cxyl= is covariance of X and Y given Z = They estimate Corvrled Oeregiot by sampling data, then get the estimation q. The same procedure used estimate P. by replacing the features eig and wif with their extend counterparts ç and &o.
4

---

Published as a conference paper at ICLR 2022
Similar to the single-agent case above, the representation of qe,i can be achieved
Pris = Ma See,eveyyin IiR,yihh = Cvg 10, (r,,ve,yet. + A7)
(7)
To estimate
learn two linear maps Tig and U2, such that CVy. vt, wh., s Tig (elfas) and Cut, wey wh.,, =o ULi (Vlas) The training examples for Ti, and U1 consist of pairs (v ( vif, & vig and (1/ ( Wi, @ vit.). The learning of Pr..jj can be done in similar way. More details can found in SA.2.1
and Cur, Cer,ve,lvhe viylehes"
After calculation of Qr.i and Pt.i.j. under the static complete graph setting where the interaction is considered, defined equation (5), we can get the estimate of Ir and Pr.i-
4.1.2 THEORETICAL GUARANTEE OF ESTIMATION q: AND P: UNDER THE STATIC COMPLETE GRAPH
Theoretically, show that the difference between qi and its estimator q is bounded with high probability.
Theorem 1. Let The be a data collection policy and H the range of тo on joint histories. If Py logg(dd,
Equation (5) and (7) used, then for all h H and any E (0, 1), such that N
v(Cug)
where is the number of time points we collect sample, then l| - q: bounded as below with probability at least - 3c, where
l1q. qill S nA,
Copintt
|Aill ( ||allIta (Cggut (1-7)+2
+ Cuovgiee
A A1ll Gogine H|AllA
( (ogists.)
of (Csgitt (2-7)2+a
Here D,, A2 are two other relevant bounds, we provide them in SE.1. v()), denote the largest, smallest eigenvalue of a matrix. And 7 12 log log(2da,
is a constant that depends on the magnitude of the norm of 3/ (we assume |w9ll S (Ay), the dimension of v/g (d,,)) ), the (uncentered) covariances (Cug = E [19 vigh ) and the sample size (N).
c(Cog)
Theorem says we need at least N samples for the bound in equation (8) to be valid. We give the proof's in $E. is not hard obtain a bound for Pt using the same approach. We omit that.
4.2 EXTENSION TO STATIC NON-COMPLETT GRAPH
In large-scale multi-agent systems, the number of agents is large, and all agents need interact with each other. A static non-completed graph can perfectly represent such a situation. For example, in given static non-complete graph G., we know its maximum number of degree k and we the binary n X n matrix with each entry as I to indicate the interaction between two agents. Then the GAPSR for each agent will be
q = (fqu))))=)) = EI.
Lemma 1. Under the same environment depicted in Theorem 1 and given G. with ls maxi- mum number of the degree to represent agents, then the bound in Theorem 1 can be rewritten as l|q. -q - KA.
The conclusion of Lemma is evident since we replace the n with the k neighbors, the total error bound is also decreased approximately &
4.3 DYNAMIC GRAPII
Real-world multi-agents can also formulate a time-dependens dynamic graph G5, rather than a static graph. A dynamic graph has its structure dynamically changing with time. In other words, the edges can be inserted or deleted across time. The dynamic graph brings more challenges to the representation the interaction relationship among agents changes constantly.
5

---

Published as a conference paper at ICLR 2022
Braha & Yam (2009), Ma et al. (2017) and Zhao et al. (2010) consider a dynamic graph as a set of ordered static graphs. For each time point, we are given a static graph such that G2 = {Gá1, .a..... , Gat), }. and a time-dependent given binary matrix with f,,., indicating the interaction between two agents at each time. Then we have the agent-wise PSR as
t 9 (19 = -E C1..
(10)
Compared to (9), the coefficient 1,,, is time- deeendeenn,en,, which brings a challenge to our theoretical bound. We consider dynamic graph experiences trajectory path, assuming every node has chance least p to interact by connection with another node at any time point. For example, for a node i, if we take the union set of the nodes interacted with i over the path, then the union set could form a static complete graph; in other words, if i connects j. then we can obtain a valid sample to estimate qi.j the complete static graph does, if not, then we skip to the next time point. For the complete static graph. we need the trajectory to at least N time points collect enough data to estimate our conditional operator qi, accurately. Furthermore, The total number of time points needed by i until the N interaction with j follows a negative binomial distribution (B p). On average, need time points before see i, completely connecting N times. Now we consider node could interact with every node in set of nodes (J : [J] = n - 1) for N number of time points. We assume the chances being interacted between two nodes (i.j E J) does not affect their interaction with other nodes. Thus we have a set of independent negative binomial random variables {Jr ~ NB(N, .) to characterize the interaction of i with j E J. So we are interested in the expectation of the maximum of Ji..... .ii.....,aa, Jn-1, i statistics that tells the expected maximum number of time points of collection of measurements needed for the node i to be able to connect with every node j E J for least N number of time points. We denote as J11....m-11 and we have
()) = F[max((1, Jnnz)) =-=))==E E +Nm (I
N +....
N (N-1) p 10
(11)
N20
Lemma 2. Under the same environment depicted in and given a dynamic gruph Ga with every node has chance at least p to interuct with another node in one-time point, let N be the number of time points we collect data of meusurements in order to get the bound Theorem 1, if Equation 10 and 7 used, then we need at least
N' = -(N- -NN22++
2 + K (4, n. N)
7
+ F (g.n, N,, + 0(1),
(12)
1og1/
total number of time points, where = - p. K (g. N) = logi/g(1 - 1) + (N 1) logs/4 [l081/g(n - 1)] + (N 1) log1/9 log1/ (N - 1)1, F is a periodic C - of period 1 and mean value whose Fourier--oefficeent are given by F(k) = [i)
I' Tog( ()
2kmrr
for k E Z [0}- Then l/q: - -qill achieves the same bound as in Theorem I with probability at least 1-3e. In other words, I1q - -qill I nd. Moreover, (12) is an asymptotic expansion of the right-hund of (11). We give the proof in $F.3.
Lemma 2 gives the corst-case bound for our estimation under the dynamic graph. The result tells us that if we need 1 more sample of measurement for our algorithm to converge on the complete static graph, we need roughly logi/a [log/ / (n h 1)] more samples on the dynamic graph. So as long as we allow enough learning time, the algorithm can converge with high probability.
Complexity with Increasing Agents. For the complete static graph, we need to evaluate qu, and Pa. every time point, which requires (n²)) operations and space. Overall, with an increased number of agents, our GAPSR has a polynomial On?)) scaled complexity, which is feasible for learning in a large number of agents environment and is more efficient compared to the centralized MAPSR (Chen et al., 2020) theoretically, which is combinatorially sample complex, the analysis is shown in $A.4. For non-complete static graph with k maximum number of degrees for k < n. which is more common in the real world, because very far-away robot will not likely affect the targeted robot, the operation will be significantly decreased (k2))
4.4 THE ESTIMATION FOR GAPSR MODEL COMPONENTS
As stated by Littman et al. (2001), a complete PSR model can build a recursive rule to update itself. In other words, given the qr.i.j. the GAPSR model can calculate qe-1.áj by incorporating new observation, so called filtering process in the dynamical system. We achieve this with

---

Published as a conference paper at ICLR 2022
three models proposed by Hefny et al. (2018a): For any agent i, Pt...j (o,()) qt+1,i, (P. Ot.s, dt.j), and Oz,; = Z (g.s.j. Qt.z). The last model is used to predict the observation oui with action az and PSR 9,,i.-- Typically, W Wa,,. Zr, learnable linear maps, and Fl, is non-linear and differentiable but known in advance. The Wt,;, Zu are learned from regression after estimate Ae,s.j and Pr,i., see $A.2.2 for details of estimation of W Wag. Z.j.
5 DECISION-MAKING FRAMEWORK WITH GAPSR MODEL
Previous work on single-agen agget proposed an end-to-end training algorithm (Hefny et al., 2018a) for PSR model and policy learning. Here we design an algorithm for multi-agent settings and incorporate our GAPSR model containing the interactive graph component.
We propose online learning algorithm to learn the GAPSR and agent policies simultaneously. Our algorithm is shown in $B.2. We use a diagram in $B.3 illustrate this process.
Our algorithm has three components. Firstly, we estimate the GAPSR the model parameters W and Zr, (line 4-1 The agents use an existed I length trajectory generated based on the iteration k - I's policy (a random policy is used if it is the first time), and learn the GAPSR parameters under the given interactive graph by regressions with details introduced in 4.4.
Secondly, we use the just learned GAPSR to generate the predictive state representations q and (line 13-28). In particular, by starting from the initialized GAPSR and executing the iteration k 1's policy, the agents experience a T length trajectory. The agents perform a series of extension, filtering, and prediction steps generate the q and Pt- Every agent also obtains action by executing its policy funetion that maps predictive states qr, action Or x (q..)). Agents then save trajectories (actions, observations, predictive states, and rewards) over the path.
Lastly, learning and planning via multi-agent actor-critic (line 30-34): agents use learned rep- resentations as the state and feed them into a MARL algorithm. c.g., MADDPG (Lowe et al., 2017). The MARL algorithm conducts the policy learning. Here give two examples of GAPSR based MARL algorithms, which are implemented for our experiments. They follow the actor-critic framework. We first develop ments, where each agent has its own critic and actor independently, it is analogous to the in- dependent actor-critic (IAC) (Foerster al., 2018). The gradient of the policy is written as ((,) Br:=p(r, (0,) ET Vo, log ne, (o../l...)(r + VV,; (9++1,)) Vo: (q..))]. and the independent critic updated by minimizing the loss L. = B (VV the predictive states qi generated by the GAPSR are considered as states to fit the value func- tion. Zg Q x A - [0. 1] is the stochastic policy that maps to the probability density of ac- tions with parameter 0. We call it GAPSR-1. As we know, IAC would not work well since the environment is not stationary under a multi-agent setting, the MADDPG by Lowe et al. (2017) solves non-stationary environment by considering other agents actions; however, every agent needs a separate critic that has the global information. We used centralized critic to minimize the loss L. = Bar. (Q (qi
algorithm under partially observable environ-
T
);) Here
9n. 01, an) y) So our policy gradient is written Eq.,,o Vo, To, (q: (q:) V., Q. (q)
9n, a1. an))o:=Fe.((.)) To fully consider other agents' information, it uses the joint predictive states as input. Here by abuse of notation, use ne Q - A to indicate the deterministic policy with parameter f. We call it GAPSR-2. We put integration details in $B.4.
as Vo, J(b,)
Our algorithm has the following characteristics. First, due to its decoupled structure, it is a general algorithm in the sense that planning can utilize any MARL algorithm for multi-agent MDP.
Second, our algorithm is an end-to-end framework, in the implementation, we build an additive loss function and fully differentiate it with respect model parameters. In particular, we update the MARL and GAPSR model parameter = (OGAPSR, OMARI.) (line 32) by minimizing the following additive objective function:
((O)= = 01 (9 + az (OGAPSR, OMARL), (0 (0) + Lo(w),
(13)
(14)
71
(2(OAARRR OMARL) = Σ
E )
Σ Zis
(80)) - - Φi, [, (15)
7

---

Published as a conference paper at ICLR 2022
Here the L1 (ARLL)) is the objective function for MARL, for example, if the actor-critic used, it will be the negative action value function with policy parameter 8 plus the critic loss with parameter w, and OMARL = (0, w). E2(GGArKK MARL)) is the MSE between prediction and actual observation. And p(T is the distribution over trajectories induced by the policy and GAPSR. @APSRR = {W., .. Zz,} denotes GAPSR's ' parameters. The a1 and 02 are hyper- apper-prramtters to penalize differently on two losses.
Third, PSR, function of action, can bring agents' action information into the policy gradient; our interactive GAPSR even brings the effect of other agents' actions to the policy gradient as well.
EXPERIMENTS
(a) 2-Agents Swimmer
(b) 3-Agents Hopper
Soo
Environments. We evaluate the performance of our GAPSR on collection of MARL tasks under some OpenAl Gym MAMuJoco environ- ments (de Witt et al., 2020), such as multi-agent swimmer, hopper, and ant. Each robotic agent represented as a body graph, where vertices (joints) are connected by adjacent edges (body segments) as shown Appendix Figure Each agent controls its joints based on the local infor- mation observed. All tasks are learned under the partially observable environments by manually hiding some observations for each agent. The goals of the multi-agent systems are aligned with their corresponding single-agent ones. How- ever, different from the single-agent system, the agents the multi-agent system need to collab- orate to reach their goals. For the interactive graph, for simplicity, we considered a complete static graph, where we assume every agent is connected with all other agents the graph. We defer the details of the robotic agents to I and the details of the experimental setup to $C.2.
60
seo
Buso
GAPER2
CAT5R22
1000
10
20 Sx
iterations "tupp(xiess
20
(c) 4-Agents Ant
(d) 2-Agents Swimmer
1250
20
1000
Aageog
2200
175A
Iterations x1es)
horasions stopsikles
40
(e) 3-Agents Hopper
(l 4-Agenss Ant
200
messee
GAPSRI2
200
GAPSA-1
Iterations
steestxlee3
Iterations Stepsixles
20
Figure 1: Performance of our method under MA- MuJoco partially observable environments, the ab- lation study- IPSR, in which we do not consider the agent interaction, and the baseline, which is not using GAPSR. GAPSS-- (It uses cen- tralized critic, and uses gradients of value function with respect to policy parameter, its baseline is MADDPG), (d)-(R):APSRRI (Its baseline is IAC). We run 10 times and the shaded area is the 95% confidence interval
Baselines and Evaluation. We run 50 iter- ations for each experiment and collect M = 100 trajectories in every iteration with max- imum of 1000 steps in every trajectory. After each iteration, we compute the average return R M7 En= EM Et= ri,s on batch of M trajectories, where, T, is the length of the 7tth trajectory. We repeat this process using ten different random seeds and report the average and standard deviation. To verify the effectiveness of interactive graph, we introduce a baseline called Independent PSR learning (IPSR); in this model, do not consider the graph, so formulate independent single PSR without considering their interactions, which means there are no qi any more but only q:- The architecture of GAPSR-1 1 and GAPSR-2 remains the same. To verify the advantage of PSR, introduce another baseline (MARL) where we take out the GAPSR entirely, so it matches with the MARL run on a partially observable environment, For GAPSR-1, its MARL baseline is IAC (Foerster et al., 2018), and for GAPSR-2, is MADDPG (Lowe et al., 2017).
Tb
Results And Discussion Figure 1 illustrates the empirical average return vs. the number of interactions with the environment measured in time steps. Our GAPSR methods consistently out- perform IPSR and get the highest rewards under partially observable environments, which justifies the representation power of the interactive graph to assist agents in learning in the non-stationary environment with limited observation when the MARL algorithm has defect (IAC). Moreover, it can also boost the performance of the existing good MARL algorithm (MADDPG). To further verify the effect of learning the PSR part, we also plotted the predicted trajectory to verify the GAPSR's performance for predicting the observations in Figure 2. We plotted the predicted observations actual observations in iterations 1, and 40, respectively, for GAPSR-2. We plotted a row x
8

---

Published as a conference paper at ICLR 2022
(a) 2- 2-Agents Swimmer
(b) 3-agents Hopper
(c) 4-agents Ant
4pent
Apert
Agent 0
Apent
Agent
Apent
Apent 1
Agent 2
Apent
as
M
200
30
8
8
(d) 2-Agents Swimmer
(c) 3-agents Hopper
(f) 4-agents Ant
Agento
Agent
Agent
Agent
Agent NAA
Agent
Agent
Agent2
Agent
WMW
WWWWV
prades
M
MwwA
WVM
MMW
Figure 2: Predicted Trajectories (colored) vs Actual Observations (black). (a)-(c) First iteration; (d) (f) Iteration 40. The X axis represents the part of steps encountered for one trajectory under that iteration, and the Y axis represents the numerical value of the observation, i.e. (a) has three rows to represent its three coordinates of its observation. We also provide iteration 10, 20 in $D.1
columns figure, with each row representing the observation feature and each column representing each agent. As we can see from the figures, the first iteration of the learning does not predict the actual observation very well; it has some mismatches. However, as learning progresses, the predic- tions get increasingly more accurate. Note that the actual trajectory is changing according to the current policy, and the current policy is optimized based on the further accurate learning of GAPSR.
To enrich our algorithm environment, we also test our algorithm (GAPSR-2) in multi-agent particle environ- ments, using the benchmark by (Lowe et al., 2017), please check $D.2 for experiment details. We test our algorithm for large n cases. In this environment, the agents can have cooperative goals such that all
Predutor Prey (n=3)
(b) Predator Prey (n=15)
FARHOO eptoode rewverd
PAA
GAPS8-2
GAY552
PSR
IPSR
Dase
Iterations
agents must maximize a shared return and conflict- ing competitive goals. We set up the environments where agents can only perform physical actions but not communication; however, to achieve the goals, agents need explicit communication about others' lo- cations to achieve the best reward. These partially observable environments give us the motivation to test our method. We report the rewards in Figure 3. We see that GAPSR outperforms IPSR and baseline, in terms of the convergence speed and final attained rewards, with a different number of agents. The pre- dictive states convey the information that can help communication between agents in limited communi- cation and observation environments.
(c) Predator Prey 100)
Cooperative Push (n=3)
Succs
Kartsge wotocoeeeeeeee reaars
Secess
GAPSA.2
Ir5n
PSR
Daneline
Bscel no
Iterations steps//1e6]
Iterations
stepsi 1ed)
(c) Cooperative Push(n=15)
(1) Cooperative Push (n=30)
Rayteliee
Itoration' stood)110)
Itorations atedd
02.5
Figure 3: Performance of our method (GAPSR 2) under multi-agent particle partially observable en- vironments. We use different number agents in predator-prey and cooperative push environments. We run ten times, and the shaded area is the 95% confidence interval.
7 CONCLUSION
We propose GAPSR model, extending ideas from single-agent predictive state representations to a multi-agent scenario, during the process, we intro- duce the dynamic interactive graph to model agents' theoretical guarantees of the GAPSR model. Finally, a learning algorithm that supports gradient- based deep MARL methods is developed. Our method provides a modell-based MARL framework under a partially observable environment. The experiments proved that our model assumption is valid by observing the highest return while reducing the observations' prediction error over trajectories.
interactions. Furthermore, we provide the

---

Published as a conference paper at ICLR 2022
REFERENCES
Douglas Aberdeen, Olivier Buffet, and Owen Thomas. Policy-gradients for psrs and pomdps. In Artificial Intelligence and Statistics, pp. 3-10. PMLR, 2007.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. arXiv preprint arXiv: 1909.07528, 2019.
Byron Boots and Geoffrey Gordon. Predictive state temporal difference learning. arXiv preprint arXiv:1011.0041, 2010.
Byron Boots, Sajid M Siddiqi. and Geoffrey J Gordon. Closing the predictive state representations. The International Journal of Robotics Research, 30(7):954-966, 2011.
loop with
Byron Boots, Geoffrey Gordon, and Arthur Gretton. Hilbert space embeddings of predictive state representations. arXiv preprint arXiv: 6819, 68,9,888 2013.
Dan Braha and Yaneer Bar- Yam. Time-dependent complex networks: Dynamic centrality, dynamic motifs, and cycles of social interactions. In Adaptive Networks, pp. 39-50. Springer, 2009.
Lorenzo Canese, Gian Carlo Cardarilli, Luca Di Nunzio, Rocco Fazzolari, Daniele Giardino, Marco Re, and Sergio Spanò. Multi-agent reinforcement learning: review of challenges and applications. Applied Sciences, 11(14);498,, 2021.
Anthony Rocco Cassandra. Exact and approximate algorithms for partially observable Markov decision processes. Brown University, 1998.
Bilian Chen, Biyang Ma, Yifeng Zeng, Langcai Cao, and Jing Tang. Tensor Decomposition for Multi-agent Predictive State Representation. 2rXiv:2005.13777 [cs], May 2020.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018.
Roger Frigola, Fredrik Lindsten, Thomas B. Schön, and Carl E. Rasmussen. Bayesian Inference and Learning in Gaussian Process State-Space Models with Particle MCMC. arXiv:1306.2888 2861 [cs, star], December 2013.
Peter Grabner and Helmut Prodinger. Maximum statistics of random variables distributed by the negative binomial distribution. Combinatorics, Probability and Computing, 6(2):179-183) 1997.
Sven Gronauer and Klaus Diepold. Multi-agent deep reinforcement learning: survey, Artificial Intelligence Review, 55(2):895-945 943., 2022.
William Hamilton, Mahdi Milani Fard, and Joelle Pineau. Efficient learning and planning with compressed predictive states. The Journal of Machine Learning Research, 15(1):339533439, 2014.
Ahmed Hefnyy, Carlton Downey, and Geoffrey J Gordon. Supervised learning for dynamical system learning. Advances in neural information processing systems, 28: 1es19-669977 2015.
Ahmed Hefny, Carlton Downey, and Geoffrey Gordon. An efficient, expressive and local minima-free method for learning controlled dynamical systems. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018a
Ahmed Hefny, Zita Marinho, Wen Sun, Siddhartha Srinivasa, and Geoffrey Gordon. Recurrent predictive state policy networks. In International Conference on Machine Learning, pp. 1949 1958. PMLR, 2018b.
Daniel Hsu, Sham M Kakade, and Tong Zhang. A spectral algorithm for learning hidden markov models. Journal of Computer and System Sciences, 1860)1140011888 2012.
Michael R James and Satinder Singh. Learning and discovery of predictive state representations in dynamical systems with reset. In Proceedings of the twenty-fist international conference on Machine learning, pp. 53, 2004.
10

---

Published as a conference paper at ICLR 2022
Nan Jiang, Alex Kulesza, and Satinder P Singh. Completing state representations using spectral learning. In NeurlPS, pp. 4332, 2018.
Leslie Pack Kaelbling, Michael Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99-134, 1998.
Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv 2015.
preprint
Michael L Littman, Richard S Sutton, and Satinder P Singh. Predictive representations of state, In NIPS, volume 14, pp. 30, 2001.
lou-Jen Liu, Raymond A Yeh, and Alexander G Schwing. Pic: permutation invariant critic for multi-agent deep reinforcement learning. In Conference Robot Learning, pp. 5900-002. PMLR, 2020a.
Yong Liu, Weixun Wang. Yujing Hu, Jianye Hao, Xingguo Chen, and Yang Gao. Multi-agent game abstraction via graph attention neural network. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 7211-7218 2020b.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Picter Abbecl, and Igor Mordatch. Multi-Agent Actor-Critic for Mixed Cooperative-Compettive Environments. arXiv:1706.0227. [cs], June 2017.
Xueguang Lyu and Christopher Amato. Likelihood Quantile Networks for Coordinating Multi-Agent Reinforcement Learning. arXiv:1812.06311 [cs, stat], June 2020.
Shuai Ma, Renjum Hu, Luoshu Wang, Xuelian Lin, and Jinpeng Huai. Fast computation of dense temporal subgraphs. 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp. 361-372. IEEE, 2017.
Frans A Oliehoek and Christopher Amato. A concise introduction to decentralized POMDn Springer, 2016.
Judea Pearl et al. Models, reasoning and inference. Cambridge, UK: CombridgeUniveerityyrresss 19, 2000.
Joelle Pineau, Geoff Gordon, Sebastian Thrun, et al. Point-based value iteration: An anytime algorithm for pomdps. In IJCAI, volume 3, pp. 1025-1032 Citeseer, 2003.
Robert Platt Jr, Russ Tedrake, Leslie Kaelbling, and Tomas Lozano-Perez. Belief space planning assuming maximum likelihood observations. 2010.
Pascal Poupart and Nikos Vlassis. Model-based bayesian reinforcement learning in partially observ- able domains. In Proc Int. Symp. on Artificial Intelligence and Mathematics, pp. 1-2, 2008
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shi- mon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 4295-4304. PMIR, 2018.
Heechang Ryu, Hayong Shin, and Jinkyoo Park. Multi-agent actor-critic with hierarchical graph attention network. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 7236-7243, 2020.
Sajid Siddiqi, Byron Boots, and Geoffrey Gordon. Reduced-Rann Rank Hidden Markov Models. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statisties, pp. 741-748 JMLR Workshop and Conference Proceedings, March 2010.
Satinder Singh, Michael James, and Matthew Rudary. Predictive state representations: new theory for modeling dynamical systems. arXiv preprint /207,4167 2012.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang. David Earl Hostallero, and Yung Yi. Qtran: Learning factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference Machine Learning, pp. 5887-5896. PMLR, 2019.
11

---

Published as a conference paper at ICLR 2022
James H Stock, Mark W Watson, et al. Introduction econometrics,, volume 3. Pearson New York, 2012.
Wen Sun, Arun Venkatraman, Byron Boots, and J Andrew Bagnell. Learning to filter with predictive state inference machines. In International conference machine learning, pp. 1197-1205. PMLR, 2016.
Peter Sunchag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Marc Lanetot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, and Thore Graepel. Value- Selue-Decomposttion Networks For Cooperative Multi-Agent Learning, arXiv: 7026609666666 [cs], June 2017.
of the tenth international conference on machine learning, 330-337, 1993. Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings
Sebastian Thrun. Monte carlo pomdps. In NIPS, volume 12, pp. 1064-1070, 1999.
Joel A. Tropp. An Introduction to Matrix Concentration Inequalities. arXiv:1501.01571 [cs, math,
stat], January 2015.
Arun Venkatraman, Nicholas Rhinchart, Wen Sun, Lerrel Pinto, Martial Hebert, Byron Boots, Kris M Kitani, and J Andrew Bagnell. Predictive-state decoders: Encoding the future into recurrent networks. arXiv preprint arXiv: 709.0820,, 2017.
Christian Schroeder de Witt, Bei Peng, Pierre-Alexandre Kamienny, Philip Torr, Wendelin Böhmer, and Shimon Whiteson. Deep Multi-Agent Reinforcement Learning for Decentralized Continuous Cooperative Control. arXiv:2003.06709 [cs, star), December 2020.
Chao Yu, Akash Velu, Fugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness ppo in cooperative, multi-agent games. arXiv preprint arXiv21003.09555. 2021.
Kaiqing Zhang, Zhuoran Yang. and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp.
321-384, 2021.
Zhi Zhang, Jiachen Yang, and Hongyuan Zha. Integrating independent and centralized multi-agent reinforcement learning for traffic signal network optimization. arXiv:: 10651 fcs, stat), September 2019.
Qiankun Zhao, Yuan Tian, Qi He, Nuria Oliver, Ruoming Jin, and Wang-Chien Lee. Communication motifs: tool to characterize social communications. In Proceedings of the 19th ACM international conference on Information and knowledge management, pp. 1645-1648, 2010.
Meng Zhou, Ziyu Liu, Pengwei Sui, Yixuan Li, and Yuk Ying Chung. Learning Implicit Credit Assignment for Cooperative Multi-Agent Reinforcement Learning. arXiv:2007.02529 [cs, stat], October 2020.
12

---

Published as a conference paper at ICLR 2022
A
METHOD DETAILS
A.1 MATIEMATICAL MODEL OF PSR
az) 1++k-1 Here, we give the mathematical model for PSR. As in Section 3, we let == {(o,, 0:
1== as
test (a sequence of action-observation pairs) time t. then we have subset 7/ [oi 1++--1 for observations, and -"" {=t )++k- for actions. And we let h2 {(o), a,) as the history at time t. A test is executed at time t if we intervene to select the sequence of actions specified by the test. It said succeed at time t it is executed and the sequence of observations in the test matches the observations by the system (Boots et al., 2013).
The prediction of length-k test Te defined as the probability distribution that the test succeed at time t, given history hy: Pr(r,lrff h4) = Pr(rf Pr( (x)
Let T (Tz), E N is finite set of core tests. And we use T {71, -Tr and T {7f. ... (Tr indicate its observation and action parts.
A.1.1 LINEAR PSR
linear PSR is the prediction vector
q: Pr(TiTTf h.),... Pr.... ( hx)
(16)
that contains the probabilities of success of the tests in T, if and only if for any test 7
Pr(r"Ir", h2) fq(),,
(17)
where fr : [0, 1] + [o, 1] is linear projection function. For simplicity of notation, we use the same notations for qrP., W, F, which only follows the meaning defined in this section.
means that knowing the probabilities for the tests in T is sufficient for computing the probabilities for all other tests in the system. The prediction vector is sufficient statistic for the system at time t, so we call it as state for the PSR at time t. Therefore, PSR can represent state by using vector of predictions of fully observable quantities (tests) conditioned on past events (histories). The prediction function fo is linear and has one-to-one relationship a test 7 such that fr: = ff q: Vt. The linear PSR can still represent systems with nonlinear dynamics.
To maintain predictions in we need update the state qı- To do that, we predict the success of any core test prepended by a new action a and observation at time + k - 1, which we call oat.-
Based on Bayes rule, have
Pr(Te.411E hef1 (he, a))) Pr(org.--llrg,tt
faor, fao
(18)
Pr(ola,
and Soorg fao [RTT are linear operators such that (Vr, E T, Va A, Yo O). Then let Foor be
the matrix with its columns as faor, for all T2 E T. Then the updated state in PSR is obtained by
F FTo44
gr+1
fa.q:
(19)
Given the initial prediction vector qı, the PSR can update with equation 19, This recursive application of Bayes rule to a belief state is called the Bayes filter. Now we have seen the extended prediction vector, so we define extended predictive state as:
P Pr(arf ari (4), ... Pr(arfrylarip (aTr))
(20)
Clearly, we can see there exists a linear extension operator W such that P. = W (q:). And given the new observation, can have Bayes filter F such that qi+1 o, We also introduced these operators in section 4.4.
A.1.2 REPRESENTATION OF STATE AS CONDITIONAL EXPECTATION OF SUFFICIENT STATISTICS
Instead of learning the distribution, here we recover the idea of representation of states as a conditional expectation of sufficient statistics and using the supervised learning method to learn (Hefny et al.,
13

---

Published as a conference paper at ICLR 2022
2015). Let history hg is sequence of observation that starts from the beginning of time and ends at time 1.
We define the belief state b, ()(), where 8, is the current state of the world. bu+1 Pr(st-1|h(41 is the next time belief' state. We call b, as "belief state", which represents the probability distribution over state space, also represents the knowledge and uncertainty about the true state of the system. In dynamic system, the task of getting the updated 66+1 1 with given by and new observation or is called filtering. The task of estimating the Pr(s;-1lhg with given current b, without incorporating any new observation is called one-step prediction.
Instead maintaining a belief b, over states, spectral algorithms try to recover observable operators that can be used to perform filtering and prediction directly, by maintaining the expected value of sufficient statistic of future observations.
Let test Tf length sequence of observation defined before. As the recursive Bayes rule holds, we can get the next time prediction vector Pr(z4.1 ((g+1) using the new observation Ot+* and the current prediction Pr(r,1hg [hg), we also define an extended prediction vector Pr(ze, 1 These prediction vectors characterize the state of the system and they can be estimated by observ- able quantities. Given Pr(rf, 11 filtering becomes the task of getting the updated prediction vector 1 (h4+1) 1). "conditioning" on Oz. One-step prediction becomes getting the Pr(rf41 (4]),
"marginalizing" over Oz.
Therefore, the spectral algorithms avoid explicitly estimating the latent state or the initial, transition, or observation distributions. We let q: = E [Ms hg). where 244 vector of features that determines the distribution of future observations Pr(r:())) For simplicity of notation, we use the same notations for q: Pt, W, Let P. = E [5p, h2). where yer is a vector of features that determines the distribution of observations Pr( ())) We call is the transformed predictive state. So q++1 E [ [ is the updated predictive state, and P; is the extended predictive state. Let hy be the feature vector of history hg.
In Hidden Markov Models and Kalman filters, the extended state is linearly related to the predictive state qt- Which is Pt W. Estimation of the W can be done using linear regression with samples ie and fp., however, due to the overlap between observation windows, the noise terms are correlated, which will cause biased estimate. The instrumental regression (Pearl et al., 2000; Stock et al., 2012) is employed. hi is instrumental variable that do not overlap with sequence {1)==t+<> and [/)_=+* The correlation corr(h,, e(px)) 0 and corr(h, c(v))) O, where is measure of error. By taking the conditional expectation of p. = Wq given h2, we have E[p, [h]] E[W q: hh],
and po
(21)
E[E[pp h W [E([[r//)
E| [h]] WE[q, h.]]
Based on the above relationship, we first estimate the Elgp, and Ejq, [h]] by sample hū, M, and Pt,, we then use the estimates to compute W. So if we start with qi, we can compute p1 = Wqi and get the q++1 = o1), where F the Bayes filter to update the state.
A.2 LEARNING FOR GAPSR IN DETAILS
Here we introduce the details about learning GAPSR, which supplements the section 4.4 and 4.1.1.
A.2.1 LEARNING FOR qr.i.j AND Pr.a.d
To calculate qe.i.,, we introduce two sets of linear operators Tr, and U., such that T2, (v. se Oog,ve, ve, wh.,, and Un5(W/.)) = Owz, 22, Int,, We estimate them by using two ridge regressions:
arg min Tef
C(T.,
( + R(T.,)),
(22)
arg min Uig
((U Vi, @ v(t)) + R(U.s).
(23)
14

---

Published as a conference paper at ICLR 2022
L represents the ridge regression loss, and R represents the regularizer. After learning Ti, and U we can get the estimate of Cug, V2,,, let.,, and Cve, ve,,e,, IV,... Then we get the qe,., by equation Similarly, we extended features to obtain Pt.i.-
A.2.2 EXTENSION, FILTERING AND PREDICTION FUNCTIONS
Filtering. To obtain Qe- from Grsij. Pricj we use filtering. We denote Fi. the filtering function. We describe the filtering process as below. From {or and {a,}ā=1> we obtain the embedding { and (0% We then compute the observation covariance
Vor,,,.,, = M 1e,,1e2,,,v. Pi.3
(24)
We then multiply the extended state by inverse observation covariance to change predicting &f,; into conditioning on oi
M (i of
Meg oo Xag, Bee Oe., AT) (25)
x here to denote n - mode (matrix or vector) product, Xag, means multiplying the tensor by a matrix (or vector) in mode &8,--
We condition on oG, and of to obtain shifted state.
9++1.i Mar 1V df di. Man, i 12 "i X Oi, X Ti.
(26)
Based on the updating rule, 90+1a Fij 1 a.y)) and Pt. = Wiy(gn...). we write the filtering equation.
9.+1,6 (Pr.. 01,s at.)
(27)
= M 100,, Miyii X xog (M No, 100, 0h, + AT) x L2. x Ke Pi. where Pr, M Me4,, l oi Fūy usually is known because it is obtained through the above calculation using known quantities, however, W.,j. Zz, must have to be learned by using regressions.
Extension. The W.,; can be learned by kernel regression we know the qu,. and P...j. Previous work (Hefny et al., 2018a) (0) demonstrated the kernel regression model for learning single-agent PSR, here we extend to the GAPSR. We set the model parameter W...
We optimized ridge regression problem for Wij.
arg min Σ L(W,, (..s)) R(W,,).
(28)
Prediction. We can also get the prediction about the next one time observation o, by the regression function such
Tz.i = B(or../q...j, at,) Zzy(qr @ of,)).
(29)
We solve the prediction regression function Zi, by another ridge regression:
arg min Z
C(Zi,( + R(Z))
(30)
A.3 TENSOR DECOMPOSITION OF MAPSR
Existed Formulation. (Chen al., 2020) use a n + 1 multi-dimensional tensor called system dynamics tensor DD R/T//xx-xXT, x[X| to represent the system dynamics of the MAPSR, with [Ti
representing the cardinality of the tests for agent 1, n denoting the number of agents, and the H being the cardinality of the joint history. Each element of the tensor is probability of joint test given joint histories. Given the system dynamics tensor, finding the latent predictive state can be transferred into finding a minimal linearly independent set from the system dynamics tensor, and can be solved by spectral method such as tensor decomposition.
As mentioned earlier, this formulation can satisfy our needs. In Proposition 1 of Appendix A.4, we also give the sample complexity analysis such that the sample size needed to formulate D scales exponentially with the length of tests and number of agents.
15

---

Published as a conference paper at ICLR 2022
Here give summary of tensor decomposition of their method. Given system dynamic tensor D such that:
R
D ~ DA; ; D", Σ D, - ..... D....
(31)
Here is the outer product. D D'. D F are matrices. The factor matrices D', D", F consist of the vectors, i.e., D = [D]] Dig ... ... ERITIXRR A colon is used to indicate all elements of mode, thus, the Rt column D' is denoted by D.R- For any i E (T....,/TII... E {1..... (Tn and & [1,....,7[[])) after the decomposition,
get
Dis. Joik Σ
DD Firr
(32)
where (i,,... fn. ) are index corresponding to the specific dimension of the D. The last dimension of the tensor D is compressed in matrix F, and its row vector
[xx (1) ... Ix (R)) E RIx e {I...., } } is a summary of joint history and can be considered as a compressed version of the system predictive state vector p( Q h. the joint history h2 E H(k E [L, H1I) at time step where Q is the core joint test set. The whole fibers listed in the set Q form basis of the space spanned by the mode-(n+1) fibers of tensor D. Thus, by constructing the vector m = (A * D * *.. )"
h&
where * is Hadamard product. D denotes the itt row vector of D Then we could rewrite the previous equation as
A Σ m(r)=x(r) x& D D. m.m.
D Des
(33)
m(r) scalar that m(r) D.. ... And Fy the system state vector and is the prediction parameter, both of them are obtained by the tensor decomposition.
A.4 ANALYSIS OF SAMPLE COMPLEXITY FOR FORMULATING THE SYSTEM DYNAMIC TENSOR
The paper (Chen et al., 2020) does not analyze the sample complexity to construct DD which is multi-dimensional tensor D ( We give this analysis. The Pir....fn.. Pr(tig, ... tni, [2)) is an element of that tensor 'D such that fıg is the i,-th test of agent 1, similarly, the ln.., is the in -tt test of agent n, and h& is the joint history.
Proposition 1. In a n-ugents system, assume every agent has the same observation and action space [O), [A]. for length-k test, formulate complete system dynamics tensor D defined in equation 32. Assume each entry of the tensor needs samples to give a sufficient estimation using Monte- Carlo roll-out method, then the total sample size is at least (Ol) f S. if the agents are homogeneous, in other words, they are permutation invariant such that identity does not matter, then the total sample size is [(01L1)+t-1)0
Proof. At one time step, for any agent, it has || different combinations for the joint test, then for a length of & tests, it follows that ([O) number of different choices. Then the tensor D would need (A))) elements to cover all the possible length k tests. So the total sample size is ((OI)A)) S. If the agents are homogeneous, then the ordering does not matter, for each agent, we have ([O||A))* number different choices for length test, so the total choices for n agents are (10114 +
2) then need (10])A)*+ +n-)) samples.
The sample complexity is exponentially scaled with the number of agents and length of tests.
B ALGORITHM AND INTEGRATING WITH MARL METHOD
We first introduce some backgrounds on two multi-agent frameworks: Multi-agent Markov Decision Process (MMDP) and Multi-agent Partially observable Markov Decision Process (MPOMDP) since the algorithms in paper are developed based the framework of MPOMDP.
16

---

Published as a conference paper at ICLR 2022
B.1 AGENI-AGENT MDP AND MULTI-AGENT POMDP MODEL
B.1.1 MMDP
MMDP model is tuple N,, (0:) (A)) T, R), where S and N are finite sets of states and agents. A, is finite set of actions available to agent i; T S x Ai x ... x A., x S + [0, 1] is transition function; and R : S + is the reward function. Each agent i obtains reward as function of the state and agent's 8 action S x A R, and receives private observation from the state by the observation channel o; -> O,, The state has distribution d S + [0. 1]. Each agent aims to maximize its own total expected return ri >i= 7'r, where is a discounted factor and T is the time horizon. In shared reward situation, there is team reward function r S A.... An - R. agents aim maximize one shared total expected return Ei=o 7'r
B.1.2 MPOMDP
A MPOMDP model is a tuple (S (ve {A: (Rx) T, R). where (S, T., O., S4, R) describe single-agent POMDP. O the set of observations the agent can make. Ω2 S x A O; + [0, 1] is the agent's observation channel function, which specifies probabilities of observations given agent's actions and resulting states. (S, Ai, T;, R,) describes single agent MDP; and each agent i obtaines reward as function of the state and agetn's 'se action
S A, - R. Each agent aims to maximize its own total expected return r; Σr= Y'r where y is a discounted factor and T is the time horizon. In POMDP, an agent's 's belief about the sate is repre- sented probability distribution over S. The agent has prior belief bo. The agent's current belief, b,, over S. is continuously revised based on new observations and expected results of performed actions. The belief update takes into account changes in initial belief, b;-1, due to action at executed at time t - 1, and the new observation, Ot.z. The new time belief state can be obtained from basic probability theory follows: (s())) (o, 8t, at-1;i) Ex ( (St, ot St-1), where 3 is the normalizing factor.
B.2 ALGORITHM: GAPSR
We give the details of GAPSR in Algorithm 1.
B.3 GAPSR IN DIAGRAM
We also use a diagram (Fig 4) to depict the algorithm. The algorithm runs k iterations; each iteration first uses the policy to roll out data and uses the regressions to obtain the PSR parameters. Then it uses the PSR as the input of policy to generate action and using the current PSR parameters to update the predictive state. At the end of this phase, it updates both the PSR and policy parameters. The policy parameters and PSR parameters W; and Z; are parameterized by the neural network, section C.3 has the network architectures. The loss is composite loss that includes loss from actor-critic and the loss from the predictive state representation. The next iteration will re-learn the PSR parameters using the newly generated data based on the current policy obtained from the previous iteration; then, does soft update to update the PSR parameters with ones obtained at the previous iteration.
B.4 INTEGRATING TWO COMMON MARL ALGORITHMM INTO GAPSR MODEL
Here we provide a brief intuitive introduction about how we connect existed MARL algorithms with GAPSR. Please look Fig 4 for demonstration. v/ v. and v...,, embedding of (ou.+*-1,5 (:)+ and (01:1-1,5, (1)=115)) We also have embedding for extended part, labeled as &. qr..j and Pt.i.j are estimated by regression using the embedding vectors. G represents the given graph, the estimation of qt, and pt,; based on graph G and equation 5, equation 9 and equation 10 for reference. Please also go to section for detailed description. The policy network uses the predictive state input to return the action or its distribution. The agent takes the action to get the observation. The filter F.j takes predictive state, action, and observation as inputs to get the next predictive state. We present centralized critic and give the description in paragraph B.4.2. The loss is composed into two parts, we give a detailed explanation in section 5. Please also go to section 5 and Algorithm B.2 for more details about the framework.
17

---

Published as a conference paper at ICLR 2022
Algorithm 1 GAPSRL
1: Input: Learning rate 7) a graph G, static complete graph Ge or static non-compete graph G2 or dynamic graph G,
2: Initialize MARL Policy MAR. randomly
3: for == 1. 1,2,3 ",...... ..... iterations
4: GAPSR Model Estimation Phase
5: Sample b 1, 2, ... M batch of initial trajectories: ((og, d from existed policy
obtained from previous iteration k: - 1: { -m )
6: Let -. = - if available or the initial policy
7:
Given G. calculate Tr,i and Pt.i.j. and obtain the initial Wa. Zz Fl.
8:
(1) Regression qr = Ti o Uig (h), to get the Pr,ij and Pr.i.j
9:
(2) Given the Gr,. Pr,ij compute Wi.j. Zy.j. Fig
10:
(3) Get initial q1ii and Piçs by using the Tig and Us, with the early window of observa-
tions.
11:
(4) Given the graph G, using equation 5, 9, or 10 to obtain q P1,
12:
13:
Generation of Predictive Representations
Initialize GAPSR parameters θGAPSR = (Wi,. Z1,} from GAPSR Model Estimation Phase and previous iteration by soft-update:
Wi, , + (1- W)
t.j Zi = BZ., + +1--3)1 3),
Fis =
Fig
for b 1,2,3, ........... batch trajectories from { [,]-1)= Ji=1 do
Reset episode: a² of for all agents
17:
for t =
in each trajectory do for Each agent i do
19:
Get observation of,; and reward rf, and its neighbor's 's action of
20:
Extension P W Wij(gh...) (9f...)
Filtering 4: = Fa ao at of Wi))
22:
Predict oi. Zi.j oi.5)
23:
Given the graph G, obtain E+11.
24:
Execute ai+1, no k-- (al+1,) Collect oi oi ai rh Li
25:
26:
end for
27:
end for
28:
end for
29:
30:
Learning Multi-agent Actor-Critic
31:
Update & using D = {Hfo of ai rf. L., I... in - D
@ t Update(@@*11 D. 17) as Equation (13):
32:
((0) aj (
azL2 (QGAPSR, OARRL) (0 ((0) (w)
L. Eq. (1
qn. a1. an) - y) J. Eq.., Vo,TO. (1: (q:)
2Th (q), ;
Qu a1, ... an) (m))a:==e,(a4))
22 (GGAPRR MAARL. Ei= E, BTap(T(()
Eg Zis (Fi, (Wey( @ )i.5) 02,0 [1]
33: Get W W. and o5.
34: end for
35: Output: Return θ (QGAPSR, OMARL)
B.4.1 GAPSR-1
It is based the IAC (Foerster et al., 2018) which directly applies the single-agent policy gradient have each agent learn independently, with the idea behind independent Q-learning (Tan, 1993), with actor-critic in place of Q-learning.
18

---

Published as a conference paper at ICLR 2022
MAPSR Part
Agent
MARL Part
We 4
Pi
Pt,i,j
q
1.1.j
G
G
Ti (g(
Repression
Embadolin
W
irpi
4t+l,i-..
It Prçi.
h L.j L,ن
1
Ti
ii Zio
Vo, ((,))
Zi.
Zi 2.
it
at+1,1
F2.j
Ot, Ptçi
Oc+1,57t+1,8
01+1,i
Qa
(2(OMA))))
T (9t,1))
Agent
LI (IOMMAR)
Agent
TT (Qt.n)
Figure 4: GAPSR architecture combining GAPSR and MARL. The left part is the GAPSR model, which corresponds to the GAPSR Model Estimation Phase in Algorithm 1. The right part is the MARL, which corresponds to the generation of predictive representations and learning the multi- agent actor-critic. We use the actor-critic framework, which contains centralized critic and many decentralized actors. We could also give parameter sharing actor network that maps individual PSR to parameters of a Gaussian distribution over the individual action space if agents are homogeneous. Both actor and critic are parameterized by neural networks. Section B.4 and section C.3 give detailed description about this architecture.
IAC trains an actor-critic pair for each agent, resulting actors (aaaoo;;) and crities Vi(o;, a:).
((,.) Eo,a. Ve, log ni (o.,)) + +VV (o1+1, a.41.) (o {. (34)
While IAC agents display a strong ability to optimize individual rewards (Tan, 1993), the lack of global information and mechanism for cooperation means they are likely to settle for sub-optimal solutions.
Here we use the predictive state qi to the value and policy functions. And we train an actor-critic pair for each agent, resulting in actors ne, (a,/q:) and critics Vi(q:).
J(e,) = E,, (r.pp(r.(e.))
o, log ne, (ar,slu,;) + VVV, (q++1,) Vin (q..))
(35)
I=
the agents are homogeneous, we can share the critic and actor network. We have the critic loss as y/ = r; + 7 >iz (q+11s).
La = (nrop(r.e.)((V (q:) - })
(36)
Here V is the target value function. Thus, the update of parameters is given by:
δ = ri + 7/ (q++,.) (q:).
(37)
w = ws +
nw Se V (q:).
(38)
T
t=0
T
8. = 0
+
nodr, Va, log na (ar, :..))
(39)
T
B.4.2 GAPSR-2
The algorithm extends from MADDPG (Lowe al., 2017) using the deterministic policy gradient of the PSR-value function.
MADDPG is extension of deep deterministic actor-critic policy gradient (DDPG) (Lillicrap et al., 2015) to multi-agent setting such that let each agent's own critic is augmented with extra information about the actions of other agents, while their individual actor maintains local state or observation.
19

---

Published as a conference paper at ICLR 2022
The gradient of each agent is:
The critic loss ((,.) = E.. Vo. Va. "0 On. 01 a1. ,nn]aa = =(o.]].
(40)
y: = r 1 (o1+1,1, = Bo (Ot,1. Ot,o. 01,1 ... , y1
0411m
41+1,1 1. ((41n))
(41)
where {ỘT} is the set of target value functions with delayed parameters.
Our method considers the centralized critic. Also, in order to solve the non non-stationary environments when each agent is learning, uses the joint predictive states with joint actions as input.
(0.)) r.. V Te, (q:) V.) QT (qi.-.. In. a1, an)la,=x(q.))
(42)
The critic loss defined as below:
Le o (Q (q.1, Itn del ar.)) y)²}
= r 2Q (4+111 9t+1ns 0141.1" a1+1,n).
(43)
Thus, the update of parameters is given by:
- (9(+11) 9c+1a 4141.11" ((41m)) (T(,,, 90,000111 Ar,""" ,,,))
(44)
T
w' = w +
6e V V. W (".,
-r,. ",,1,- 1 ar,n),
(45)
T
8, 0 +
7e Vo, ne, (a: (.) (q). .g, a1 ,an)la;=
(46)
C ENVIRONMENT AND EXPERIMENT
C.I MAMUJOCO ENVIRONMENT SETUP
(a)
(c)
(d)
(c)
Figure 5: The illustration of three environments swimmer, hopper, ant, and their corresponding MAMuloCo version. (a) Single swimmer; (b) Single hopper; (c) Single ant; (d) n-agents swimmer; (e) 3-agents hopper; (f) 4-agents ant.
Here, we give the details of setting up our multi-agent environment MAMuJoCo, As introduced in section 6, the many agents are constructed by separating a existed single agent into parts, and each agent will only control part of the whole agent (Figure 5).
Partially Observable space: MAMuloCo a simulated robotic environment, the partially observable property achieved by only allowing partial information to the agents. For all environments, only the angles of the agent's 's joints are visible to the network; the velocities are hidden.
Action: Each agent's action space in MAMuJoCo is given by the joint action space overall motors controllable by that agent.
For each agent i, observations constructed by inferring which body segments and joints are observable by an agent i. Each agent can always observe all joints within its sub- bob-graph. A configurable parameter l: > 0 determines the maximum graph distance to the agent's subgraph which joints are observable. For example, k = 0 means agents can only observe their own joints and body parts, while k means observe its adjacent which has graph distance the
Observation:
20

---

Published as a conference paper at ICLR 2022
Table I: Configurations for MAMuJoCo environment
Environments
Swimmer
k
R
Σ A
+ 0.0001r
r =
|
2 2 is a regularizer for joint action a
Hopper 2
k
R
Ad + 0.001r 1.0
|a regularizer for joint action
Ant
k
R
Σ,
Ad:
At + 5 1e(-3))3)))))) ||external contact forces 2 + 0.0001r
|all2 regularizer for joint action
agent. The agent observation is then given by a fixed order concatenation of each observable graph element's representation vector. Depending on the environment and configuration, representation vectors may include attributes such as position, velocity, and external body forces. In addition to joint and body segment-specific observation categories, agents can also be configured to observe the robot's central torso's position and velocity attributes.
C.2 EXPERIMENT SETUP
We select three experiments from MAMuJoCo and give a detailed description of the experiments' setup. In all environments, the agent has the goal to maximize the velocity of the first coordinate for the team. We use & to denote the maximum observation distances to the subgraph. We use Ad to denote the first coordinate position difference between time difference At. Finally, we use R to denote the reward function. Table has the configuration details for these parameters.
C.3 NEURAL NETWORK ARCHITECTURE
We implement all algorithms using deep neural networks function approximators. We ensure that all policy and and action-value functions have the same neural network architecture among all algorithms the extent each algorithm allows for a fair comparison.
Usually, in a continuous environment, each agent's policy will be parameterized by its actor network that outputs the space. For our experiments with continuous action spaces, a Gaussian distribution with diagonal covariance matrix is used. The policy network maps from the input feature a Gaussian distribution vector μ. Moreover, μ [mean, std], where mean is a vector specifies the action means, and std vector specifies the standard deviation. For deterministic policy, maps to the action vector.
and diagonal covariance of Gaussian distribution the continuous action
In the implementation of actor-critic method, all the actor-network is parameterized by a multi-layer perceptron (MLP) with hidden layers of size 400 and 300 respectively and ReLU activation, which takes the individual agent's predictive state and outputs the mean and covariance Gaussian policy for stochastic policy, the action vector for deterministic policy. The critic network also an ML.P with two hidden layers with 400 and 300 units, respectively. For GAPSR-1, the critic network is used approximate per-agent utilities, which receives each agent's predictive state as input. For IAC, same as GAPSR-I, it receives agent local observation and individual action as input.
a
In GAPSR-2, there is shared critic network that approximates all agents utilities, which receives all agents' predictive states and the joint action of all agents as input. The global state consists of the complete state information from the environment. In MADDPG, the critic receives the global state and the joint action of all agents as input. Each decentralized actor (i.e., policy) network takes in each agent's observation and outputs the agent's action vector.
21

---

Published as a conference paper at ICLR 2022
Table 2: Model parameters for MAMuJoCo environment
Environments Hopper
Swimmer
Ant
71
2
3
0
0
0
0
0.1
0.1
0.1
?
0.99
0.99
0.99
Soft target network on 02
0.001
0.001
0.001
0.7
0.65
0.7
0.3
0.35
0.3
0.6
0.45
0.5
1 learning rate of Adam ridge regression regularization
0.001
0.001
0.001
0.01
0.01
0.01
Total iterations
50
50
50
Number of trajectories
100
100
100
Maximum number of steps per trajectory
1000
1000
1000
Length of test window
8
12
10
Length of history window
8
12
10
C.4 MODEL PARAMETERS
The hyper parameters for the the MAMuloCo environments are Table
D SUPPLEMENT EXPERIMENTS
D.1 MAMCJOCo SUPPLEMENT EXPERIMENTAL RESULTS
We plotted the predictive observations compared to actual observations in Figure 2 at the beginning of the learning process (iteration 1) and end of the learning (iteration 40). We also show the results of iteration ten and iteration 20 in Figure 6. By comparing with iterations 1 and iterations 40 in Figure 2, we see that the iteration 40 has the smallest difference between predictive observation and true observation, and the difference gets increased the iteration goes the earlier stage of the learning process. So the predictive accuracy is improved incrementally with the learning progresses.
D.2 MULTI-AGENT PARTICLE ENVIRONMENT
We also GAPSR into another environment, multi-agent particle environment (Lowe et al., 2017). The agents are displaced into a 2-dimensional coordinate. This environment does not assume that all agents have identical action and observation spaces. We run experiments using a different number of agents on two environments, the predator-prey, and cooperative-push. We use the same configuration in (Liu et al., 2020a). The network has the same design MAMuJoCo in section C.3, except use MLP with two hidden layers with the same 128 units respectively, so we do not repeat the description. In Table 3, we report the hyperparameters for multi-agent particle environments.
In the supplementary materials we provide the code and instructions.
22

---

Published as a conference paper at ICLR 2022
(a) 2-Agents Swimmer
(b) 3-agents hopper
(c) 4-agents Ant
Agent
Agent
Agent
Agert1
Agent
Agent
Agant
Agent
Agert
WWWW
pre
200
200
120
100
(d) 2-Agents Swimmer
(e) 3-agents hopper
(1) 4-agents Ant
Agento
Agent
Agent
Agent
Agent
Agent
Agant
Agent2
Agert
w
www
R5
-35
V-05-
280
200
100
20
Figure 6: Additional Experiments Results, Predicted Trajectories vs Actual Observations for Multi-
Agent Environments. (a) (c) Iteration 10; (d) - (f) Iteration 20; This is the supplement for Figure
Table 3: Model parameters for multi-agent particle environment
Environments
Predator-prey n=15
Cooperative-push n=15
n=3
n=100
n=3
n=30
0.99
0.99
0.99
0.99
0.99
0.99
Soft target network
0.001
0.001
0.001
0.001
0.001
0.001
On
0.8
0.75
0.5
0.8
0.75
0.7
0g
0.2
0.25
0.5
0.2
0.25
0.3
3
0.45
0.5
0.45
0.55
0.5
0.5
learning rate of Adam
0.05
0.05
0.05
0.05
0.05
0.05
À ridge regression regularization
0.01
0.01
0.01
0.01
0.01
0.01
Total iterations
30
30
30
30
30
30
Number of trajectories
100
100
100
100
100
100
Maximum number of steps per trajectory
500
500
500
500
500
500
Length of test window
5
5
5
5
Length of history window
5
5
5
E
DETAILED PROOFS
We give the proof of Theorem in Appendix E. and we first introduce the following Lemmas to prepare the proof.
Let X.... X be independent random variables of dimensionality dx, -.- dx, such that | < tzy. Let [(I1, Tk. ) be the N i.i.d samples from distribution of XI...., XR. the Cx, = [[X and Cx E and Cx,X, == E[X and Õx =
Definition 2.
1 N =1 2T 21, Also, we use the :), v(.) to denote the largest, smallest eigenvalue of a matrix. Lemma (CTropp, 2015)). Let aj be a finite sequence of independent random, Hermitian matrices with dimension d. Assume that 0 & v(az) and u(a;) & for each j. Let S E, a.j, then for any n E [0, 1), it follows that
Pr(v(S) (111))(11BB) ())S)) S
-
(R(S))) 2de (E(S)))
(47)
23

---

Published as a conference paper at ICLR 2022
1. (ogggddxx the v(Cx)
Corollary Let X be a random variable, for any E (0, such that N following holds with probability at least -
v((x)> 12 log(2dx/e)
v(Cx)N
In other words, if N large enough, then Öx and Cx will be close enough.
Proof. Define Sj. 1/N2,af. Then it follows that u(S)) S L e,/N and define
2dxe xNN(Cx)/1 which implies that a 12 log (nxg/x//)) fc) Then follows from Matrix Chernoff xCxIN
Inequality Lemma 3 that (,(x((x) & (1 (1-o))(Cx)) S..
Lemma 4 ((Tropp, 2015)). A finite sequence {az} of independent, random matrices with common dimensions b, and assume that E[a,] = and ||ayl| S L for each j. let S = matrix. Let Var(S) be the variance statistics such that Var(S) = max [[[S |[S then
3 a, as a random
22
Pr([[S] > c) S (a + b)e Var3)122373.
(48)
Corollary 2. With least probability that
|Crx-Crxx -rx =V log(dy dx)//Var + loog((dr + dxx//e)L N
3N
where I. lypbr + ||C S 2lybx and Var = max ||Cx|| 12 ||r + |Cyx|l S 20
Proof. Let X,Y be two random variables, and let finite sequence {ay} } of independent random matrices to satisfy aj yバ Cyx. So the a, will have dimensions dx x dy. Let random matrix S= S=E,a, az. E,aj. +|Cxxll
follows that Eja,] = and |ayl| |! Cyx|| I ||ylll | ||Cy s
||[SS*1||
(Bly 2,0ي1 CyxCxr) Σ i
E (Blllr11 yuuf' Cxx(xx)
Σ (Elya [Elna"][[ CrxCxy)
Σ Biil 1077 CxxXxx)
$ N
Similarly, |[[SST]]
S Nt Cxxl ||Cxx(l)). By applying lemma 4, we have e = Pr([|[] 2
N2
Ne) < (dx + dy
Vartter3
and therefore, it implies that
e es log((d, + dy )
+ (Jog(dx + Le) 2 log (dx + dy Var
+
3.V
9N2
N
blog((dx + dy I/cLL
21og (dx dy Ver
3N
N
Corollary 3. For random variable X with dimensionality dx and ||X|| < t. with probability 1 6, follows that
xxx12((xx - Cx s 21, 2 2log(2dx/)
2 log L
+
N
3N
where L +tz vo(Cx)
24

---

Published as a conference paper at ICLR 2022
Proof. The proof is similarly the the proof of corollary 2, define aj Ex1
1/2
Izzl
C
e
Σ aythen it follows that [R(a]] = 0 and
||yl| S Ve(Cx)
+ Las
|E|S" |1|| = ||]Ss"]| - N + ||xx|| 112) & 2N
(49)
Applying lemma 4 to get
N2
Pr([||| 2 Ne)= S 2dxe 213 +Lo8
(50)
it follows that
2 2 2log(2dx/c)) + 2t
log(2dx/c)
c c
(51)
3N
N
Lemma 5. For two random variables X, X,Y, let Õvx Cyx + Syx, and Cx Cx + Ax where
E| and x| are not necessarily zero and Cx is symmetric positive semidefinite. Define
A = CyxC* x and A = Oxx(Cx + + Then it follows that:
(Cr)
(xxx) Cx 1/2
A +
| v(xx)) +X
- A S 1 r(Cx)
+
v(Cx)
+
Proof.
A- -G
M1 + M2.
It follows that
DYX
|| S ((xx++
For M1, by using facts U-1 V-1 = (V - -UV and Crx = C//2PC where P is
correlation matrix with | |||
< 1,
M1 -Cxx (Ax XT)(C + Ax +A
= -V pCx 1/2 (Ax + +X)(Cx + +
CK Ax
+ | 1/2
|| S (Cr)
v(Cx)+ +1
((C)) VU(C)
12112 Ax +
S V o(xx)
v(xx) +
Corollary 4. Let { 2k 2 be i.idd samples from two random variables X, Y with dimensions dx and dy and (uncentered) covariances Cx and Cy. Assume [|X]] S L and || S by Define
A CxxC3' and Ā Čyx(Cx + +))-1. For any e E (0,1) such that N 1 log(2xx/e) the following holds with probability at least 1EE::
CCx)
((Cr) Vu(Cx)a +
3
A - s v(Cx) v(Cx)(1-2)++)))
o(Cx)(1-)) -))+))++)) +
where
2log(2dx/e /e)
2 (lgg(2xx/e)
2
= 2
+
+ +
N
3N
Ve(Cx)
log(dy + dx)/e
+ 36yle log((dy + dx dx)/e)
B = 2tytt
N
3N
12 log(2dx/c)
7=
cCC))
25

---

Published as a conference paper at ICLR 2022
Proof. It follows by applying Corollaries 1,2.3 to Lemma 5. By union bound, each condition has probability - e, so the total events are bounded by
3
Pr(bounds satisfied) := Pr 11)11 Σ Pr(A.) 3e.
Lemma 6. For two random variables X,Y, let Oxx Cyx + Dyx. and Òx Cx + Ax where x and x[ not necessarily and Cx is symmetrrc but not positive semidefinite.
Define A C and À OxxOx(O2 + =11) Then it follows that:
((y) || + 2u((xx ||xx|| + + ||Cxx|||XxX|++|| + ||xx |xxl|+++ |Axx|||Ax]] |Axx v(Cx) +
A A $ =(x)3
v(Ox)2 + +
Proof.
A + -
= =CyxCx(((Cx + Ax)² + -)) -0-1--xx)+- (CrxAx + AxxCx + AxxAx)((x++xx)))))
Mi + M2.
For M1. by using facts U-1 -- correlation matrix with || < follows that
and Crx 2 PC where P ass
M1 -Cy PCX
3/2 (A3 + CxAx + A + + Ax)2 AT)-
Therefore.
u(Cr) I [xxx 3(
|| S
V
+
|| < |Cx1I||Ax|| + ||rxxl |[x|| + ||Crx Ax|
0(Cx)2 +X
Corollary 5. Let {I yk) )k) be i..d samples from random variables X, Y with dimensions dx and dy and (uncentered) covariances Cx and Cy. The E and E. | x is not necessarily zero and C2 is symmetric but not necessarily positive semidefnite. Assume |X S tu and Y S ty.
Define A = CyxCx' and À = OxxOx xxxxx(C*+X) +X)== For any (0, 1) such that N the following holds with probability least 1 3e:
1 Zogg(2x /c)
CCC)
u(C)) || 2u(Cx) ||xx|| + ||Cxx|I|AX| + || |Cx|| | ||xx||
A Al S v(x
((Cx)(1- - +
v(Cx) -
where
7 12 log(2dx/e)
x(Cx)N
Proof. It follows by applying Corollaries 1,2,3 to Lemma Also by union bound, so the total events bounded 1 3e.
Theorem 2. Grabner 1997 (3.3) (Grabner & Prodinger, 1997) Consider there are n independent
copies X1....,, Xx, i.i.d negative binomial random variables, with parameters defined NBb p). and our goal is to calculate the expectation of the maximum of these N random variables E,, E(max(X, (I,.... X,)} then we have following asymptotic solution:
E, logg (n) + (b- 1) logg logg (n) (b - lllggg p + (b 1) - -log (b- (b- - 1)! 2 +
7
log (1/4)
+ F (n) + (b- log logg (n) + (b log | p logg (b 1)!) + o(1),
(52)
26

---

Published as a conference paper at ICLR 2022
(where F is periodic C function of period and mean value 0 whose Fourier-coeffcients given by F(k) log( (og(
2krs
for k 2 (0), and q p).
log(
We omit the proof, interested readers could go to (Grabner & Prodinger, 1997) for details.
E.1 PROOF THEOREM
We first prove the bound for ||q.. 9
Let me be data collection policy and H. is the range of ne joint histories. Equation used, then for all E H and any E (0, 1), (..(((")) (..(())) is bounded as below with probability at least 1 3c.
Proposition 2.
(wellot
|| 22 (Gugivs,) ) | A
[ - 9 s
Casy loft!
(Gegivts) (1 7) + A
Guppiy 10
|| + 1|A211 Gugginn
+ -1 ||
(Cugl wit ) (1 +
t9 log(2da, /c) ((oog)
where A follows the bound (55) and D follows the bound (53), and 7
Proof. Let Tig is the tensor such that Carogiets Tei Xn vh.y and Un is the tensor such that Cygiv,, Ung Xı wh, and for simplicity without loss meaning, use Cagiet, denote Cugogiet. Then we have
Ö @vevgieeh Cueyglot, s Teis Th. |
C (Qugint, Cuggiet, 5 | Uni ||
We finish the above proof by proofing the [[TE Tilll and | Uei'l are bounded by using Corollary 4.
Vo /C(CCt, Ja +
Ceppany
B
[T.s- Tho || s tn
+ 2
Cup
Crst ) (1 - +
(Cwt,,)
(1 (1-7)
(53)
where
2log(2dn/
2 llg(2dn//c) 3N
17
a = 2th
+ th
N
(
11
log(do, dr, + dn)/e
4to,t tn log log((oo,d,)) dA, + dn)/e)
3 = 200,
N
3N
E logg(dn/e))
7
(54)
and
27

---

Published as a conference paper at ICLR 2022
1 (C Ja.)a+1
| - Uno
|1 tn
c
8
+
v
Cest whi
(C
(1 7) + (1-
1
(1 (1- +
(55)
where
log (2dn///))
2 (og(2d//c)
t
a
2 V
+
+ th
N
3N
V (Cut,,)
log(dA, + dn)/e
4f tn log((dA, + di)/e)
8 = 2 4h
+
N
3N
13 log (og(2dn//))
7
(56)
Caat
N
Then using the equation (7) and corollary 5 to obtain the bound for qi,j
(Cugious)) ) ||,1| 2u Gugivt,,
| +
[.. - qu,l s
(ayy
(Cogive,
(1 7) + A
Curogien
| || Cuglue, 2
|| ||
(ugyvets) ) (1 7
89 1og(2da,/0) (Cogg) )
where A follows the bound (55) and A₂ follows the bound (53), and
Now we start to prove our Theorem 1.
Proof. The Equation (5) says:
:= = Σ =E9 qrs.
here we assume the agents are homogeneous, in other words, each pair of { a:)) coming from the same spaces O, A. They are permutation invariant and their identities do matter. Thus, the bound of quo is invariant to agents. Under the assumption of static fully complete graph, for any agent q, = -y qi,j, thus
l|q. qill
= =||E,00 q., -,, 9
I n [r. -
(57)
E.2
PROOF OF LEMMA
Here we prove Lemma 1.
Proof. Equation (9) says
qr : ((gr..i))]]
Σ Ar
28

---

Published as a conference paper at ICLR 2022
where I is indicator function to denote if two agents connected. Under the assumption that the static non-complete graph has maximum number of degrees and the agents are homogeneous, we have Σ3 Las <= k. Thus,
q qill
= |E t.u 1.
S k [9.. 9.ill
(58)
E.3 INFORMAL PROOF OF LEMMA 2
Here we make some intuitions for the proof of Lemma As we already give the proof sketch in our main paper. Lemma is direct application of Theorem 2. Here our random variable JI.....Jy Jn ~ ~V,(r,)), where {(J:)]== represents the number of time points node needs before it meets node j number of times.
For the complete static graph, we need least sample for the bound in equation 8 to be valid: in other words, we need the trajectory to run at least N time points to collect enough data to estimate our conditional operator accurately q.j--
For the dynamic graph, each time t, the two nodes are randomly connected with probability if it connects, then we can obtain valid sample estimate qr, not, then we skip to the next time step. For the dynamic graph node i, if we take the union set of the nodes i connected over the trajectory path, then the union set could form static complete graph. We say the two graphs are equivalent. The number of time points needed by until the n connection with for each of the pairs (i.j) follows the same distribution J NBB(N p). Then we are interested in the expectation of the maximum of J Jn-1, we denote it as J (1....a-1..
E(J(I.... } means on average, how many time points (N') we need for all nodes other than at least meets times with i. Obviously, this N' >= N since p E [0, 1]. The calculation of this expectation is solved by (Grabner & Prodinger, 1997). And we also put their result in Theorem 2.
29


Reviews:
[{"review_id": "eHZI07HDbvx", "reviewer": "Reviewer_6qEL", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe 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.\n\nWeaknesses:\nI 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_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. ", "summary_of_the_review": "The paper gives solid technical contributions and substantial experiments. I recommend acceptance of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LK491cyaR4r", "reviewer": "Reviewer_Jba3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nNonetheless, 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.\n\nThe 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.\n\nI am satisfied that the work is of a very high quality as far as I can assess it.\n\n## More detailed comments\n\nIt's not clear what is meant by this: \n\n> Learning in this environment is challenging since\nthese partially observable observations bring the noise.\n\nOr this:\n\n> in the setting where the system model is not known a priori or the\nmodel introduced by the domain expert is biased, it is always beneficial and safer to learn system models and develop policies based on the models.\n\nIs it always beneficial to learn POMDP models, or can model free methods sometimes work more effectively?\n\n\nIn 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:\n> In this model, predictive state Q t satisfies...\n\nIt 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.\n\n\nThe 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:\n> We replace the partially observation o with PSR Q\n\nI 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_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.\n\nThe 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.\n\nThe 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. \n", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "As0eDmLVSd_", "reviewer": "Reviewer_zgHd", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThe mathematical derivation appears sound and theoretical guarantee is given.\nThe two versions of the algorithms, MAPSR1 and 2, performed well in MAMuJoCo benchmark.\nWeakness:\nIt needs a lot of background knowledge about PSR, MARL and graph-based approaches to understand the work, though that is inevitable...\nRegarding 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\".\nThe reference source for Littman et al. 2001 (NIPS 2001?) is missing.\n", "summary_of_the_paper": "This paper extends predictive state representation (PSR) for POMDP to multi-agent reinforcement learning (MARL) setting.", "summary_of_the_review": "This paper presents practical algorithms for MARL by utilizing the data-driven dynamic modeling by PSR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

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)