Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARL
Authors: Fengzhuo Zhang
Boyi Liu
Kaixin Wang
Vincent Tan
Zhuoran Yang
Zhaoran Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-Agent Reinforcement Learning
Transformer
generalization

Abstract: The cooperative Multi-Agent Reinforcement Learning (MARL) with permutation invariant agents framework has achieved tremendous empirical successes in real-world applications. Unfortunately, the theoretical understanding of this MARL problem is lacking due to the curse of many agents and the limited exploration of the relational reasoning in existing works. In this paper, we verify that the transformer implements complex relational reasoning, and we propose and analyze model-free and model-based offline MARL algorithms with the transformer approximators. We prove that the suboptimality gaps of the model-free and model-based algorithms are independent of and logarithmic in the number of agents respectively, which mitigates the curse of many agents. These results are consequences of a  novel generalization error bound of the transformer and a novel analysis of the Maximum Likelihood Estimate (MLE) of the system dynamics with the transformer. Our model-based algorithm is the first provably efficient MARL algorithm that explicitly exploits the permutation invariance of the agents. Our improved generalization bound may be of independent interest and is applicable  to other regression problems related to the transformer beyond MARL.

Relational Reasoning via Set Transformers: Provable Efficiency and Applications to MARL
Fengzhuo Zhang'
Boyi Liu
Kaixin Wang'
Vincent Y. F. Tan'
Zhuoran Yang*
Zhaoran Wang
National University of Singapore
2 Northwestern University Yale University
www.nnwwteen.nn.ommm {fzzhang, kaixin. wang)/ edu, 0or11u00008B...rrrtttstrrr..ee edu, vtan@nus. ed. zhuoranyang, work@gmail com, zhaoranvangggmail.. com
Abstract
The cooperative Multi-Agent Reinforcement Learning (MARL) with permutation invariant agents framework has achieved tremendous empirical successes in real- world applications. Unfortunately. the theoretical understanding of this MARL problem is lacking due to the curse of many agents and the limited exploration of the relational reasoning in existing works. In this paper, we verify that the transformer implements complex relational reasoning, and we propose and analyze model-free and model-based offline MARL algorithms with the transformer approx- imators. We prove that the suboptimality gaps of the model-free and model-based algorithms are independent of and logarithmic in the number of agents respectively, which mitigates the curse of many agents. These results are consequences of a novel generalization error bound of the transformer and novel analysis of the Maximum Likelihood Estimate (MLE) of the system dynamics with the trans- former. Our model-basn based algorithm is the first provably efficient MARL algorithm that explicitly exploits the permutation invariance of the agents. Our improved generalization bound may be of independent interest and is applicable to other regression problems related to the transformer beyond MARL.
Introduction
Cooperative MARL algorithms have achieved tremendous successes across a wide range of real- world applications including robotics (1 games 3 4) and finance (5). In most of these works, the permutation invariance of the agents is embedded into the problem setup, and the successes of these works hinge leveraging this property. However, the theoretical understanding of why the permutation invariant MARL has been so successful is lacking due to the following two reasons. First, the size of the state-action space grows exponentially with the number of agents; this is known as "the curse of many agents" [6] (7]. The exponentially large statc-action space prohibits the learning of value functions and policies due to the curse of dimensionality. Second, although the mean-field approximation is widely adopted to mitigate the curse of many agents [6] g) this approximation fails to capture the complex interplay between the agents. In the mean-field approximation, the influence of all the other agents on fixed agent is captured only through the empirical distribution of the local states and/or local actions 6 g). This induces restricted class of function approximators. which nullifies the possibly complicated relational structure of the agents, and thus fails to incorporate the complex interaction between agents. Therefore, designing provably efficient MARL algorithms that incorporate the efficient relational reasoning and break the curse of many agents remains an interesting and meaningful question.
In this paper, we regard transformer networks as the representation learning module to incorporate relational reasoning among the agents. In particular, focus on the offline MARL problem with
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the transformer approximators in the cooperative setting. In this setting, all the agents learn policies cooperatively to maximize a common reward function. More specifically, in the offline setting, the learner only has access to pre-collected dataset and cannot interact adaptively with the environment. Moreover, we assume that the underlying Markov Decision Process (MDP) is homogeneous, which means that the reward and the transition kernel are permutation invariant functions of the state-action pairs of the agents, Our goal is to learn an optimal policy that is also permutation invariant.
To design provably efficient offline MARL algorithms, we need to overcome three key challenges. (i) To estimate the action-valee function and the system dynamics, the approximator function needs to implement efficient relational reasoning among the agents. However, the theoretically- grounded function structure that incorporates the complex relational reasoning needs be carefully designed. (ii) To mitigate the curse of many agents, the generalization bound of the transformer should be independent of the number of agents. Existing results in (9) thus require rethinking and improvements. (iii) In offline Reinforcement Learning (RL., the mismatch between the sampling and visitation distributions induced by the optimal policy (i.e., "distribution shift") greatly restricts the application of the offline RL algorithm. Existing works adopt the "pessimism" principle to mitigate such challenge. However, this requires the quantification of the uncertainty in the value function estimation and the estimation of the dynamics in the model-free and model-based methods respectively. The quantification of the estimation error with the transformer function class is a key open question.
We organize our work by addressing the abovementioned three challenges.
First, we theoretically identify the function class that can implement complex relational reasoning. We demonstrate the relational reasoning ability of the attention mechanism by showing that approximating the self-attention structure with the permutation invariant fully-connected neural networks (i.e., deep sets (IO) requires an exponentially large number of hidden nodes in the input dimension of each channel (Theorem D This result necessitates the self-attention structure in the set transformer.
Second, we design offline model-free and model-based RL algorithms with the transformer ap- proximators. In the former, the transformer is adopted to estimate the vatuue-value function of the policy. The pessimism is encoded in that we learn the policy according to the minimal estimate of the action-value function in the set of functions with bounded empirical Bellman error. In the model- based algorithm, we estimate the system dynamics with the transformer structure. The policy is learned pessimistically according to the estimate of the system dynamies in the confidence region that induces the conservative value function.
Finally, we analyze the suboptimality gaps of our proposed algorithms, which indicate that the pro- posed algorithms mitigate the curse of many agents. For the model-free algorithm, the suboptimality gap in Theorem is independent of the number of agents, which is a consequence of the fact that the generalization bound of the transformer (Theorem is independent of the number of channels. For the model-ber bodell-bsed algorithm, the bound the suboptimality gap in Theorem is logarithmic in the number of agents; this follows from the analysis of the MLE of the system dynamics in Proposition 3 We emphasize that our model-based algorithm is the first provably efficient MARL algorithm that exploits the permutation equivariance when estimating the dynamics.
Technical Novelties. In Theorem 2 we leverage PAC-Bayesian framework to derive generalization error bound of the transformer. Compared to 9 Theorem 4.6), the result is a significant improvement in the dependence on the number of channels N and the depth of neural network L. This result may be of independent interest for enhancing our theoretical understanding of the attention mechanism and is applicable to other regression problems related to the transformer. In Proposition 3 first estimation uncertainty quantification of the system dynamics with the transformer approximators, which can be also be used to analyze other RL algorithms with such approximators.
we derive the
More Related Work. In this paper, we consider the offline RL problem, and the insufficient coverage lies at the core of this problem. With the global coverage assumption, number of works have been proposed from both the model-free 1i.15) and model- based [11 [6] perspectives. To weaken the global coverage assumption, we leverage the "pessimism" principle in the algorithms: the model- free algorithms impose additional penalty terms on the estimate of the value function [1 [8] or regard the function that attains the minimum in the confidence region as the estimate of the value function [9]; the model-based algorithms estimate the system dynamics by incorporating additional penalty terms 20 or minimizing in the region around MLE 21). For the MARL setting, the offline MARL with the mean field approximation has been studied in [8] 22).
2

---

The analysis of the MARL algorithm with the transformer approximators requires the generalization bound of the transformer. The transformer is an element of the group equi/invariant functions, whose benefit in terms of its generalization capabilities has attracted extensive recent attention. Generalization bounds have been successively improved by analyzing the cardinality of the "effective" input field and Lipschitz constants of functions [23] 24 However, these methods result in loose generalization bounds when applied to deep neural networks [25]. Zhu, An, and Huang [26] empirically demonstrated the benefits of the invariance in the model by refining the covering number of the function class, but unified theoretical understanding is still lacking. The covering number of the norm-bounde, transformer We show that this can be further improved using a PAC- -AC-eaaeii framework. In addition, we refer to the related concurrent work (27] for Rademacher complexity- -aaeed generalization bound of the transformer that is independent of the length of the sequence for the tasks such as computer vision.
shown by [9] to be at most logarithmic in the number of channels.
2 Preliminaries
Notation, Let [x] = (1,..., n). The 7th entry of the vector x is denoted as Ij or [a]s. The 7th row and the jth column of matrix are denoted as X,, and X., respectively. The f--norm of the vector x is ||0]|p- The norm of the matrix X E R is defined as ||X = =Σ,= || (l)))// and the Frobenius norm of X is defined as || |F = | 12.22 The total variation distance between two (V(P, Q) = ACA IP(A) - Q(4)). For set X,, use
distributions P and Q A is defined ((X) to denote the set of distributions on X. For two conditional distributions P. P.Q: X - A()). the dxe distance between them is defined as dze (P, Q) = 2 sup TV(
Q(- z)). Given a metric space (.V, || II). for set A C X. E-COver of A is a finite set C C X such that for any a E A. there exists e E C and ||c all < E. The E-covering number of A is the cardinality of the smallest e-cover, which is denoted as N(A, e; || II)-
Attention Mechanism and Transformers. The attention mechanism is technique that mimics cognitive attention to process multi-channel inputs (28) Compared with the Convolutional Neural Network (CNN), the transformer has been empirically shown to possess outstanding robustness against occlusions and preserve the global context due to its special relational structure [29]. Assume we have N query vectors that are in IR do These vectors are stacked to form the matrix Q E gdd With Ny key vectors in the matrix K R.Nyxd and Ny value vectors in the matrix V E Xdy, the attention mechanism maps the queries Q using the function (t K, V) = SM(QK )V. where SM(() is the row-wise softmax operator that normalizes each using the exponential function, i.e. for x E Rd, [SM(x)) = exp(x;)/ Σز= exp(2,) for i E [d]. The product QK measures the similarity between the queries and the keys, which then passed through the activation function SM(.). Thus, SM(QK VV essentially outputs weighted sum of V where a value vector has greater weight if the corresponding query and key are more similar. The self-attention mechanism is defindd as the attention that takes Q = XWq, K = XWK and V = XWv as inputs, where X E IR Nxd is the input of self-attention, and Wo. WK E dexda and Wv E Rdxdy are the parameters. Intuitively, self-attention weighs the inputs with the correlations among N different channels. This mechanism demonstrates a special pattern of relational reasoning among the channels of X.
In addition, the self-attention mechanism is permutation invariant in the channels in X. This implies that for any row-wise permutation function (--), which swaps the rows of the input ma- trix according a given permutation of [NV. we have Ax)()(X)Wo (())) K, (x)) Rb (Att(XX Wo, XWK. XW))). The permutation equivariance of the self-attention renders it suitable for inference tasks where the output equivariant with respect the ordering of inputs. For example, in image segmentation. the result should be invariant to the permutation of the objects in the input im- age [30] The resultant transformer structure combines the self- atteetttntoon with multi-layer perceptrons and composes them to form deep neural networks. It remains permutation equi/invariant with respect to the order of the channels and has achieved excellent performance in many tasks 33).
Offline Cooperative MARL. In this paper, we consider the cooperative MARL problem, where all agents aim to maximize a common reward function. The corresponding MDP is characterized by the tuple (So, S,A, P* r, 7) and the number of agents is N. The state space S = S is the Cartesian product of the state spaces of each agent S, and = [si,..., "9,....,Sy) SN] is the state, where 8; ds the state of the ,th agent. The initial state is Sg- The action space A = A is the Cartesian product of the action spaces A of each agent, and A [ai,...,,ay av]] is the action, where
3

---

W
21
31
Wa
K22
Att(X,X,X)
(a) pRotu ( (24)) with pRotu and PReLU as single-hidden layer neural networks.
(b) Sclf-attention mechanism I Att(X, X, X)w.
Figure 1: The blocks with the same color share the same parameters. The left figure shows that PReLU Ex= (2,))(Zz) first sums the outputs of ΦRELU()z)) and it implements the relational reasoning only through the single- sidden layer network PReLU. contrast, the self-attention block in the right figure captures the relationship among channels and then sums the outputs of each channel.
aj Rdd is the action of the 7th agent. The transition kernel is P SN AAN A(S*), ), and E (0, is the discount factor. Without loss of generality, we assume that the reward function r deterministic and bounded, i.e., S: x A + [-Rmax, Rmax] We define the the state-value function V SN +
I Vaxx Vima]. where Vinax = Hmax/ - 7), and the action-value function Qp :SN A + [- maxx, Vima] of policy æ and a transition kernel P as
VB(S)= F
Σ y rr(SS, A,) 55=5 and () Σ rr(S,, A,) 50= Ao= À
respectively. Here, the expectation taken with respect to the Markov process induced by the policy Ae ~ Se) and the transition kernel P. The action- value function QT. is the unique fixed point of the operator (T (S, A) r(S, + s ( (f ,T) A.A where the term in the expectation defined as f(5, T) E 1 (f A)]. We further define the visitation measure of the state and action pair induced the policy π and transition kernel P as d5, A) = Zi 7 d'p,, where dzp,, is the distribution of the state and the action step
In offline RI., the learner only has access to a pre-collected dataset and cannot interact with the environment. The dataset D {(S, A Ti,
$ 1 is collected in an i.i.d. manner, i.e. (S., A,) is
independently sampled from # E ASS A), and S ~ P ( A.). This i.i.d. assumption is made to simplify our theoretical results; see Appendix N.2 for extensions to the non i.i.d. case. Given policy class II, our goal is to find an optimal policy that maximizes the staue- function T² = argmax, Vj.. (So). For any ı IT, the suboptimality gap of a is defined as Vp." (So) Vg. (So).
3 Provable Efficiency of Transformer on Relational Reasoning
In this section, we provide the theoretical understanding of the outstanding relational reasoning ability of transformer. These theoretical results serves firm base for adopting set transformer to estimate the value function and system dynamics in RL algorithms in the following sections.
3.1 Relational Reasoning Superiority of Transformer Over MLP
The transformer neural network combines the self-attention mechanism and the fully-connected neural network, which includes the MultiLayer Perceptrons (MLP) function class as subset. On the inverse direction, we show that permutation invariant MLP can not approximate transformer unless its width is exponential in the input dimension due to the poor relational reasoning ability of MLP.
Zaheer al. 110 Theorem 2] showed that all permutation invariant functions take the form IEN ((x;)) with X [x1, ... ., _N]" Nxd as the input. Since the single-hidden layer RcLU neural network is an universal approximator for continuous functions (34, we set Φ N - RW: and IR2, + R to be single-hidden layer neural networks with ReLU activation functions as shown Figure where W2 the dimension of the intermediate outputs. The widths of the hidden layers in ΦReLU and PReLU are W, and W3 respectively. For the formal definition of ÓReLU and PReLU.

---

please refer to Appendix A
Then the function class with PReLU and ØReLU as width-constrained ReLU networks is defined
{ Nxd S(X) - PRELU
N
M(W)
Σ
( with max W; S W (E
We would like to use functions in (WW) to approximate the self-attention function class
F= [f::RN: I f(X) I, Att(x, X. X for some E [0.
Figure ((a) shows that PROLU (z.) first processes each channel with ΦNeLU, and the relationship between channels is only reasoned with PReLU. The captured relationship in (2+) cannot be too complex due to the simple structure of PReLU- In con-
PReLU -i=1 (X=] trast, the self-attention structure shown in Figure [[b) captures the relationship between channels with the self-attention structure and then weighs the results derive the final output. Consequently, it difficult approximate the self-attention structure with PRtLU > (R:LU(())) due its poor relational reasoning ability. This observation is formally quantified in the following theorem. Theorem 1. Let W* W' d, F) be the smallest width of the neural network such that
vf F, 3g E N(W)
S.T.
X Nx4 f((X) 9(X) E.
sup
With sufficient number of channels N, it holds that W (S, = Q(exp (ed) ( for some >> 0.
Theorem T shows that the fully-connected neural network cannot approximate the relational reasoning process in the self-attention mechanism unless the width is exponential in the input dimension. This exponential lower bound of the width of the connecco neural network implies that the relational reasoning process embedded within the self-attention structure is complicated, and it further motivates us to explicitly incorporate the self-attention structure in the neural networks in order to reason the complex relationship among the channels.
3.2 Channel Number-independen Generalization Error Bound
In this section, derive the generalization error bound of transformer. We take X E TR. Nxd as the input of the neural network. In the 7th layer, as shown in Figure 3.2 we combine the self-attention mech- anism Au(XX=(0) QK: X, XW.()) with the row-wise FeedForward (rFF) single-hidden layer neural net- work rFF (()))(()))))))))))))) with width m. We combine w:(0) and w-(() to w-(6) for ease of calculation, and 3(0) and a are the parameters of the first and second layer of rFF. The output of each layer is normalized by the row-wise normalization function 11 (-), which projects each row of the input into the unit ba-b (for some 2 1). For the last layer, we derive the scalar estimate of the action-value function by averaging the outputs of all the channels, and the "clipping" function II (x) is applied to normalize the output to V-V, VJ. We note that such structures are also known as set transformers in 33 For the formal definition of the transformer, please refer to Appendix B
Layer
Layer L
=FP(X ( (i))
C
X
A
GR- X.X.
Ausxwiil QN. X.
Figure 2: Structure of the transformer func- tion class, where the row-wise feedforward function is specified as fully-connected net- works.
We consider a transformer with bounded parameters. For pair of conjugate numbers p, g E RR i.e., 1/p + 1/q = 1 and p, q 2 1, the transformer function class with bounded parameters is defined as
Ba)(B) = (X; Woik. WhiL, 1.L ",,L,,,,,,, w) [og]]
Ba,
< Bo.
| 1p. < Bok ( 1|.. < Bv, Bllllu < B,, for i E [T],] E [m]] & E [d]]
where B B= [Ba, Bb, BoK, By, Bul are the parameters of the function class, and WI:L and bL are the stacked parameters in each layer. We only consider the non-trivial case where
QK Who a
5

---

Ba, Bb, BQK. Bv, Bw are larger than one, otherwise the norms of the outputs decrease exponentially with growing depth. For ease of notation, we denote (ir(B) as Fer when the parameters are clear.
Consider the regression problem where we aim to predict the value of the response variable y E IR from the observation matrix X E RR where (X,y) v, and lyl S V. We derive our estimate f: f: + R from i..d. observations Dreg {(X,,, 14) generated from The risk of using E Fir (B) as a regressor on sample (X.1) is defined as (J(X) w)². Then the excess risk of functions the transformer function class Fu can be bounded as in the following proposition.
Proposition 1. Let B = Box Ba BrBrBw. For all f Fes, with probability at least 1 - ô, we have
n
EE (((X)-
Σ
(J(X.) wi)
2 | 3 [)(x)) - w) +0
V2 n
mf log mdLBB 1 + log 8 )
Proposition] is a corollary of Theorem 2 We state here since the generalization error bound of transformer may be interesting for other regression problems. We compare our generalization error bound in Proposition [ with [ Theorem 4.6). For the dependence on the number of agents N, the result in [ Theorem 4.6] shows that the logarithm of the covering number of the transformer function class is logarithmic in N. Combined with the use of the Dudley integral [35], [9] Theorem 4.6] implies that the generalization errоr bound logarithmic in N. In contrast, our result is independent of N. This superiority is attributed to our use of the PAC-Bayesian framework, in which we measure the distance between functions using the KL divergence of the distributions on the function parameter space. For the transformer structure, the size of the parameter space is independent of the number of agents N, which helps us to remove the dependence on N.
Concerning the dependence on the depth of the neural network, 9 Theorem 4.6] shows that the logarithm of the covering number of the transformer function class scales exponentially in L. In contrast, Proposition [ shows that the generalization bound is polynomial in L. We note that Proposition D does not contradict the exponential dependence shown in [36] 37), since we implement the layer normalization to restrict the range of the output. As byproduct, Proposition shows that the invariant of the layer normalization adopted in our paper can greatly reduce the dependence of the generalization error on the depth of the neural network L. We note that our results can be generalized the multi-head attention structure, and the extensions are provided in Appendix(N]
4 Offline Multi-Agent Reinforcement Learning with Set Transformers
In this section, we apply the results in Section to MARL. We implement efficient relational reasoning via the set transformer to obtain improved suboptimality bounds of the MARL problem. In particular, we consider the homogeneous MDP, where the transition kernel and the reward function invariant to permutations of the agents, i.e., for any row-wise permutation function (-(.), we have = P" (v(5") v (A)) and r(S, = r ((v(5), v(A)
for all 5,5' E SN and À E AN. A key property of the homogeneous MDP is that there exists permutation invariant optimal policy, and the corresponding state-value function and the action-value function are also permutation invariant (22)
Proposition 2. For the cooperative homogeneous MDP, there exists an optimal policy that is permutation invariant. Also, for any permutation invariant policy n, the corresponding value function VØ. and action-value function Qp. are permulation invariant.
Thus, we restrict our attention to the class of permutation invariant policies II, where ((A|S) = T (A)A) (S)) for all A E A. 5 S, π II and all permutations d). For example, if (Ā 5) hh p(a; (s) for some μ., then æ permutation invariant. optimal policy is any x E argmax V..())).
4.1 Pessimistic Model-Free Offline Reinforcement Learning
In this subsection, we present model-free algorithm, in which we adopt the transformer to estimate the action-value function. We also learn policy based such an estimate.

---

4.1.1 Algorithm
We modify the single-agent offline RL algorithm in [19 to be applicable to the multi-agent case with the transformer approximators, but the analysis is rather different from that [T9]. Given the dataset D {(St, A, ry, S!) we define the mismatch between two functions, I and I on DD for a fixed policy π as [(f, J. ; D) = E(s S') A) - ---7 + We adopt the transformer function class Fer(B) in Section 3.2 to estimate the action- function and regard X x= [S E RRNx xd as the input of the neural network. The dimension d = ds + A and each agent corresponds
channel X. The Bellman error of function f with respect to the policy 'T is defined as Ef; m,; LU, m D) inf J,
For a fixed policy we construct the confidence region of the action-value function of æ by selecting the functions in Fir with the e-controlled Bellman error. We regard the function attaining the minimum in the confidence region the estimate of the action-value function of the policy; this reflects the terminology "pessimism". Then the optimal policy is learned by maximizing the action-value function estimate. The algorithm can be written formally
f arggax min f(S,, where F(H,,) { Fu((B) E(f. Sc #ell /EF(xxE)
(1)
The motivation for the pessimism originates from the distribution shift, where the induced distribution of the learned policy is different from the sampling distribution v. Such an issue is severe when there is no guarantee that the sampling distribution supports the visitation distribution d7. induced by the optimal policy n². In fact, the algorithm in Eqn. { does not require the global coverage of the sampling distribution v, where the global coverage means that d'- (S, A)/u(S, A) is upper bounded by some constant for all (S, E S x A and π E II. Instead, only requires partial coverage, and the mismatch between the distribution induced by the optimal policy d'. and the sampling distribution is captured by
CF.
max E sp: [(f JEFU
T -T ((B.A))
T -" A))
(2)
(), We note that CF. I max (S. Ā)Ešx A5, A), so the suboptimality bound involving Cz in Theorem iss tighter than the bound requiring global convergence (38). Similar coefficients also appear in many existing works such as 19 and (39]
4.1.2 Bound on the Suboptimality Gap
Before stating the suboptimality bound, We require two assumptions Fi and the sampling distribution v. We first state the standard regularity assumption of the transformer function class.
Assumption 1. For any II, have inf JEFu, suppean (S, A) T (5, A)) S ey and SuP inf jeF, E. [x[(F(S,A) A) T ((5, A S Ey where du = {n | 3 E πI s.t. l = di..) is the set of distributions of the state and the action pair induced by any policy π E II.
This assumption, including the realizability and the completeness, states that for any policy π E II there is function in the transformer function class F,r such that the Bellman error controlled by ex, and the transformer function class is approximately closed under the Bellman operator 7 for any æ E II. addition, we require that the mismatch between the sampling distribution and the visitation distribution of the optimal policy is bounded.
Assumption 2. For the sampling distribution v, the coefficient CF. defined Eqn.
is finite.
We note that similar assumptions also appear in many existing works
19
39
In the analysis of the algorithm in Eqn. T.. we first derive generalization error bound of the estimate of the Bellman error using the MMC-Bayeiian framework [40] 41).
Theorem 2. Let B- = By BoK B, By For all f. E Fie(B) and all policies æ E II, with probability at least - 8. we have
E (f(S, A) - T 1 F(S, A))
T + L(T f.f,T:
s -E, E, (f(S, f(8. A)) +0
V2
max n
mf log
mdLBn Vinax
+ log
NII, 1/n, doo) 1)
7

---

For case of notation, we define e(Fu,, ô, n) to be n times the second term of the generalization error bound. We note that the generalization error bound Theorem i independent of the number of agents, which will help us to remove the dependence on the number of agents in the suboptimality of the learned policy. The suboptimality gap of the learned policy मे can be upper bounded as the following.
Theorem 3. If Assumptions 7 aandZ and we take Fe + Fe(Fit, I1, 1,6,n) n)/n, then with probability at least - 6, the suboptimality gap of the policy derived in the algorithm shown in Eqn. ① is upper bounded as
VCRL 1-7
Vmax CFr
mdL.Bn
2T(II, 1/n,1/n,.
VI. (5o) 5
mL2d log
+ +log
(1-?) 1--))//
Vmax
where d = ds + dA. EFF and B is defined in Proposition
Theorem 3 shows that the upper bound of the suboptimality gap does not scale with the number of agents N. which demonstrates that the proposed model-free algorithm breaks the curse of many agents. We note that the model-free offline/batch MARL with homogeneous agents has been studied in & and 22], and the suboptimality upper bounds in Theorem and 22 Theorem 4. 1] are also independent of N. However, these works adopt the mean-field field approximation of the original MDP, in which the influence of all the other agents on a specific agent only coarsely considered through the distribution of the state. The approximation error between the action-value function of the mean-field MDP and that of the original MDP not analyzed therein. Thus, the independence of N in their works comes with the cost of the poor relational reasoning ability and the unspecified approximation error. In contrast, we analyze the suboptimality gap of the learned policy in the original MDP, and the interaction among agents is captured by the transformer network.
4.2 Pessimistic Model-based Offline Reinforcement Learning
In this subsection, we present the model-based algorithm, where we adopt the transformer to estimate the system dynamics and learn the policy based on such an estimate.
4.2.1 Neural Nonlinear Regulator
In this section, consider the Neural Nonlinear Regulator (NNR), in which use the trans- former to estimate the system dynamics. The ground truth transition P* (*' S, A) is defined as S" (*( A) + é, where F* is a nonlinear function, & = [e....., &N] ] the noise, and e, (N oálax) for i E [N] are independent random vectors. We note that the function F and the transition kernel P are equivalent, and we denote the transition kernel corresponding to the function J' as PF. Since the transition kernel (S S, A) is permutation invariant, F should be permutation equivariant, i.e., F* (V((,, (A)) = + F (S, for all row-wise permutation functions (.)).
We take X = 15, A E &RNxdd as the input of the network and adopt a similar network structure as the transformer specified in Section 3.2] However, predict the next state instead of the action-value function with the transformer, we remove the average aggregation module in the final layer of the structure Section 3.2 Please refer Appendix [ for the formal definition. The permutation equiv- ariance of the proposed transformer structure can be easily proved with the permutation equivariance of the self-attention mechanism. We consider the transformer function class with bounded parameters, which is defined as
Mu((B)=
{ Fux(X; Wi w.l... a.t. I...., bI..) |al3|
Ba. 16.1666)1 Bo.
W l| < Box, | O 1b < By for e [A], E [m],k E }
where B' [Ba, By, BoK. Bv] is the vector of parameters of the function class. We denote Ma(BB) as Mir when the parameters are clear from the context.
4.2.2 Algorithm
Given the offline dataset = ((S., A,, rı, 8 we first derive the MI_E of the system dynamics. Next, we learn the optimal policy according to the confidence region of the dynamics that are
8

---

constructed around the MLE. The term "pessimism" is reflected in the procedure that we choose the system dynamics that induce the smallest value function, i.e.
1 Σ - F(S,, A.)lEE
FMLE argmin FEM 72
and argmax min VP (So),
(3)
Tell FEMMn.(()
where MMLF(()= (F Mar |1/ E TV(Pp(-155 A.), PMI.( ( ( A.)) 3 < () is the confidence region, which has closed-form expression in terms of the difference between and FMLE as stated in in Appendix C The transition kernel induced by FMLE is denoted as PMIE. The parameter Ç is used to measure the tolerance of estimation error of the system dynamics, and it is set according to the parameters of Mur(B') such that F" belongs to MMLE (C) with high probability.
Similar to the model-free algorithm, the model-based algorithm specified in Eqn. does not require global coverage. Instead, the mismatch between the distribution induced by the optimal policy di. and the sampling distribution captured by the constant
(TV(PF(11S.)) CM. max Euz: [TV A), PT ()) (TV (T
P'(1S,,,)
(4)
FEMI
We note that CM S m (S.)E dz. (S, A)/v(S, A), so the suboptimality bound involving CPy in Theorem 4 is tighter than the bound requiring global convergence. Similar coefficients also appear in many existing works such
[2 and 20
4.2.3 Analysis of the Maximum I Likelihood Estimate
Every F (MLL(() is near the MLE in the total variation sense and thus well approximates the ground truth system dynamics. Therefore, to derive an upper bound of the suboptimality gap of the learned policy, we first analyze the convergence rate of the MLE PMLE to P*.
Proposition 3. Let B By BoK Ba For the maximum likelihood estimate PILLE in Eqn. 33) the following inequality holds with probability at least 1-8 8.
Ey [V (-1 (,,,, PMLE(. (5, A)) s { (= log (N LmddB)) + n2
log 2
We define e' e'(Mr,, n) to be n times the total variation bound. Proposition Jssows that the total variation estimation error is polynomial in the depth of the neural network L. However, different from the model-free RL results in Section 4.1 the estimation error of MLE PALE is logarithmic in the number of agents N. We note that this logarithm dependency on N comes from the fact that TV(P* ( A), 5 the states of N agents, different from the scalar estimate of the value function in Section 4.1 To prove the result, we adopt PAC-Bayesian framework to analyze the convergence rate of ML.E, which is inspired by the analysis of density estimation 4R more details are presented in Appendix
measures the distance between two transition kernels that involves
4.2.4 Bound on the Suboptimality Gap
To analyze the error of the learned model, we make the following realizability assumption. Assumption 3. The nominal system dynamics belongs to the function class Mus ie., F* E Mir(B').
In addition, we require that the mismatch between the sampling distribution and the visitation distribution of the optimal policy is bounded. Assumption 4. For the sampling distribution v, the coefficient CM² defined in finite.
We note that these two assumptions are also made in many existing works, egg.
20 21
Theorem 4. If Afssumptions 3 hold, and we take Ç = (ie'(Mut n)/n for some constant > 0. then with probability least 0, the suboptimality gap of the policy learned in the algorithm in Eqn. 3 is upper bounded as
5 VIAX V
( mLL log LN
V (So) VB.. (So)
(1 (1-
+ log 8 n
where d= ds d and B is defined in Proposition

---

Cooperative Novigation, No3
Cooperative Navigetion, No:30
-200
-20003
-300
Awerag Sewnert
15403
-400
sdto set treeeberee
-25003
snt Innditmme
GCN
GCV
5500
-30000
.8000
20022
32200
40030
30200
00022
20002
20200
50000
40200
25000
02500
Tuaning Stapo
Tuaring Siits
Figure 3: Average rewards of model-free RL algorithms with their standard deviations for N 3, 30. Theorem 4 presents an upper bound on the suboptimality gap of the offline model-based RL with the transformer approximators. The suboptimality gap depends on the number of agents only as OVVlog N), which shows that the proposed model-based MARL algorithm mitigates the curse of many agents. This weak dependence on originates from measuring the distance between two system dynamics of N agents in the learning of the dynamics. To the best of our knowledge. there is no prior work on analyzing the model-based algorithm for the homogeneous MARL, even from the mean-field approximation perspective. The proof of Theorem 4 leverages novel analysis of the MLE For more details, please refer to Appendix
in Proposition 3
5 Experimental Results
We evaluate the performance of the algorithms on the Multiple Particle Environment (MPE) 44
45.. We focus on the cooperative navigation task, where N agents move cooperatively to cover landmarks in an environment. Given the positions of the agents H; R2 (for i E [N] and the positions of the L landmarks Yj E R2 (for j E [L], the agents receive reward
- E min Ily; x; 22. This reward encourages the agents to move closer to the landmarks.
We the number of agents as N 3, 6, 15, 30 and the number of landmarks as = N. Here, we only present the result for N 3, 30. Please refer to Appendix for more numerical results. To collect an offline dataset, we learn a policy in the online setting. Then the offline dataset is collected from the induced stationary distribution of such a policy. We use MIP,, deep sets, Graph Convolutional Network (GCN) [46), and set transformer to estimate the value function. We note that the deep sets, GCN, and set transformer are permutation invariant functions. For the implementation details, please refer to Appendix
Figure 3 shows that the performances of the MLP and deep sets are worse than that of the set transformer. This is due the poor relational reasoning abilities of MLP and deep sets, which corroborates Theorem []] Figure 3 indicates that when the number of agents N increases, the superiority of the algorithm with set transformer becomes more pronounced, which strongly aligned with our theoretical result in Theorem 3
Concluding remarks
In view of the tremendous empirical successes of cooperative MARL with permutation invariant agents, is imperative to develop firm theoretical understanding of this MARL problem because it will inspire the design of even more efficient algorithms. In this work, we design and analyze algorithms that break the curse of many agents and, at the same time, implement efficient relational reasoning. Our algorithms and analyses serve as first step towards developing provably efficient MARL algorithms with permutation invariant approximators. We leave the extension of our results of the transformer to general permutation invariant approximators as future works.
Acknowledgments and Disclosure of Funding
Fengzhuo Zhang and Vincent Tan acknowledge funding by the National Research Foundation Sin- gapore and DSO National Laboratories under the AI Singapore Programme (AISG Award No: AISG2-RP-204 RP-2020-008 and by Singapore Ministry of Education (MOE) AcRF Tier Grants (A- 0009042-01- and 4-8000189-01 tion (Awards 2048075, 2008827, 201 2015568, 1934931), Simons Institute (Theory of Reinforcement Learning), Amazon, J. P. Morgan, and Two Sigma for their support.
Zhaoran Wang acknowledges the National Science Founda-
10

---

References
[1] D. Wang, R. Walters, X. Zhu, and R. Platt. Equivariant Q Learning in Spatial Action Spaces. In Conference Robot Learning, pages 77231123. PMLR, 2022.
[2] D. Wang, R. Walters, and R. Platt. SO(2) -equivariant reinforcement learning. arXiv preprint arXiv:2203.04439 2022.
[3] Y. Tang and D. Ha. The sensory neuron a transformer: innuutaaioonnnvariann neural networks for reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
[4] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing atari with deep reinforcement learning. arXiv preprini arXiv: 1312.5602, 2013.
[5] K. Xu, Y. Zhang, D. Ye, P. Zhao, and M. Tan. Relation-awaan transformer for portfolio policy learning. In Proceedings of the Twenty-Nimh International Conference on International Joint Conferences on Artificial Intelligence, pages 4647-4653, 2021.
[6] L. Wang, Z. Yang, and Z. Wang. Breaking the curse of many agents: Provable mean embedding q-iteration for mean-field reinforcement learning. In International Conference on Machine Learning, pages 10092-10103. PMLR, 2020.
[7] K. Menda, Y. Chen, J. Grana, J. W. Bono, D. Tracey, M. Kochenderfer, and D. Wolpert. Deep reinforcement learning for event-driven multi-agent decision processes. IEEE Transactions on Intelligent Transportation Systems, 20(4): 1259)):22291166666 1268, 2018.
[8] M. Chen, Y. Li, E. Wang, Z. Yang, Z. Wang, and T. Zhao, Pessimism meets invariance: Provably efficient offline mean-field multi-agent RL. Advances in Neural Information Processing Systems, 34, 2021.
[9] B. Edelman, S. Goel, S. Kakade, and C. Zhang. Inductive biases and variable creation in self-attention mechanisms. arXiv preprint 10. 10090, 2021.
[10] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. Smola. Deep sets, Advances in Neural Information Processing Systems, 30, 2017.
[11] Chen and N. Jiang. coormatiio-tthoredde considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR, 2019.
[12] A. Antos, C. Szepesvári, and R. Munos. Learning near-optimal policies with bellman-residee residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71(1):89- 129, 2008
[13] O. Nachum, B. Dai, Kostrikov, Chow, L. Li, and D. Schuurmans. Algaedice: Policy gradient from arbitrary experience. arXiv preprint arXiv: 1912.0209 2019.
[14] Y. Duan, C. Jin, and Z. Li. Risk bounds and rademacher complexity in batch reinforcement learning. In International Conference on Machine Learning, pages 2892-2902. PMLR, 2021.
[15] T. Xie and N. Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, pages 550-559. PMLR, 2020.
[16] S. Ross and J. A. Bagnell. Agnostic system identification for model-based reinforcement learning, arXiv preprint arXiv: 1007, 2012.
[17] Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pages 5084-5096. PMLR, 2021.
[18] N. Rajaraman, L.. Yang, J. Jiao, and K. Ramchandran. Toward the fundamental limits of imitation learning. Advances in Neural Information Processing Systems, 33:2914-2924, 2020.
[19] Xie, C. Cheng, N. Jiang, P. Mineiro, and A. Agarwal. Bellman-consistent pessimism for offline reinforeement learning, Advances in Neural Information Processing Systems, 34, 2021.
11

---

[20] J. Chang, M. Uehara, D. Sreenivas, R. Kidambi, and W. Sun. Mitigating covariate shift in imitation learning via offline data with partial coverage. Advances in Neural Information Processing Systems, 34, 2021.
[21] M. Uehara and W. Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226, 2021.
[22] Y. L., optimization for mean-field multi-agent reinforcement learning: A principled approach. arXiv preprint arXiv: 105. 08268, 2021.
L. Wang. J. Yang. E. Wang, Z. Wang, T. Zhao, and H. Zha. Permutation invariant policy
[23] J. Sokolic, R. Giryes, G. Sapiro, and M. Rodrigues. Generalization error of invariant classifiers. In Artificial Intelligence and Statistics, pages 1094-1103. PMLR, 2017.
[24] A. Sannai, M. Imaizumi, and M. Kawano. Improved generalization bounds of group in- variant/equivariant deep networks via quotient feature spaces. In Uncerlainty in Artificial Intelligence, pages 771-780. PMLR, 2021.
[25] D. Jakubovitz, R. Giryes, and M. R. D. Rodrigues. Generalization error in deep learning. In Compressed Sensing and Its Applications, pages 153-193. Springer. 2019.
[26] S. Zhu, B. An, and F. Huang. Understanding the generalization benefit of model invariance from a data perspective. Advances in Neural Information Processing Systems, 34, 2021.
[27] Anonymous. An analysis of attention via the lens of invariance: Approximation, generalization, and optimization. Technical Report, 2022.
[28] D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint 1rXiv:1409.0495 2014.
[29] M. M. Naseer, K. Ranasinghe, S. H Khan, M. Hayat, F. Shahbaz Khan, and M. Yang. Intriguing properties of vision transformers. Advances in Neural Information Processing Systems, 34, 2021.
[30] M. M. Bronstein, J. Bruna, T. Cohen, and P. Veličković. Geometric deep learning: Grids, groups, graphs geodesics, and gauges. arXiv preprint arXiv:2104.1 134.1388, 2021.
[31] A. Dosovitskiy, L.. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
[32] L. Yuan, Y. Chen, T. Wang, W. Yu, Y. Shi, Z. Jiang, F. E. H. Tay, J. Feng, and S. Yan. Tokens- to-token vit: Training vision transformers from scratch on Imagenet. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 558-567, 2021.
[33] J. Lee, Y. Lee, Kim, A. Kosiorek, S. Choi, and Y. W. Teh. Set transformer: A framework for attention-based permutation-invarian neural networks, In International Conference on Machine Learning, pages 3744-3753. PMLR, 2019.
[34] S. Sonoda and N. Murata. Neural network with unbounded activation functions is universal approximator. Applied and Computational Harmonic Analysis, 43(2))233-268, 2017.
[35] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. MIT press, 2018.
[36] I.. Bartlett, J. Foster, and M. Telgarsky. Speettaaly-norrmaiized margin bounds for neural networks. Advances in Neural Information Processing Systems, 30, 2017.
[37] B. Neyshabur, S. Bhojanapalli, and N. Srebro. A PAC-Bayesian approach to spectrally- normalized margin bounds for neural networks. arXiv preprint arXiv: 2017.
[38] M. Uehara, J. Huang, and N. Jiang. Minimax weight and Q-function learning for off-policy evaluation. In International Conference on Machine Learning, pages 9659-9668. PMLR, 2020.
12

---

[39] M. Yin. Y. Duan, M. Wang, and Y.-X. Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint ar arXiv:223.005804, 2022.
[40] D. A. McAllester. Some PAC-Bayesian theorems. Machine Learning, 37(3):355 -1335--63,,-- 1999.
[41] D. A. McAllester. Simplified PAC-Bayesian margin bounds. In Learning Theory and Kernel Machines, pages 203-215. Springer, 2003.
[42] W. Sun, N. Jiang, Krishnamurthy, A. Agarwal, and J. Langford. Model-based RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Conference on Learning Theory, pages 2898-2933. PMIR, 2019.
[43] Zhang. From e-entropy to KL-entropy: Analysis of minimum information complexity density estimation. The Annals of Statistics, 34(5):21 (11(5))21802220 80-2210, 2006.
[44] R. Lowe, Y. L. Wu, A. Tamar, J. Harb, OpenAl Pieter A., and I. Mordatch. Multi-agent actor-critic for mixed cooperative-compettive environments. Advances in neural information processing systems, 30, 2017.
[45] I. Mordatch and P. Abbeel. Emergence of grounded compositional language in multi-agent populations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[46] I. Liu, R. A. Yeh, and A. G. Schwing. PIC: permutation invariant critic for multi-agent deep reinforcement learning. In Conference Robot Learning, pages 590-602. PMLR, 2020.
[47] L. Devroye, A. Mehrabian, and T. Reddad. The total variation distance between high- dimensional Gaussians. arXiv preprint arXiv: 2018.
[48] M. Telgarsky. Representation benefits of deep feedforward networks. arXiv preprint arXiv:1509.08100 2015.
[49] A. Agarwal, S. Kakade, A. Krishnamurthy, and W. Sun. Flambe: Structural complexity and representation learning of low rank MDPs. Advances in Neural Information Processing Systems, 33:20095-200 20107, 2020.
[50] M. Tsagris, C. Beneki, and H. Hassani. On the folded normal distribution. Mathematics, 2(1):12-28, 28, 2014.
[51] M. I. Belghazi, A. Baratin, S. Rajeshwar, S. Ozair, Y. Bengio, A. Courville, and D. Hjelm. Mutual information neural estimation. In International Conference on Machine Learning, pages 531-540, PMLR, 2018.
[52] M. J. Wainwright. High-Dimension Statistics: Non-Asymptotic Viewpoint, volume 48. Cambridge University Press, 2019.
[53] B. Jiang, Q. Sun, and Fan. Bernstein's inequality for general Markov chains. arXiv preprint arXiv: 10721, 2018.
[54] D. Paulin. Concentration inequalities for Markov chains by Marton couplings and spectral methods. Electronic Journal of Probability, 20:1-32, 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
13

---

(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof' of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URI.)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report enror bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals. if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "KGdsaryiTb4", "reviewer": "Reviewer_TVHt", "summary": "This paper presents theoretical analysis on the use of transformers for offline multi-agent reinforcement learning. The main contributions are: i) a proof that approximating the \"relational reasoning\" of set transformers using feed-forward neural nets requires exponential width, ii) model-free and model-based algorithms for offline MARL using transformers and pessimistic policies, which minimize the effect of distribution shift, and iii) suboptimality gaps for the proposed algorithms showing that they scale well with the number of agents. ", "questions": "No questions. ", "limitations": "I didn't see any discussion on limitations in this paper, which in fact doesn't have a final discussion/conclusion section. ", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Unfortunately, I found this paper very hard to understand, even after spending several hours on it and multiple reads. Not only it is theory intensive, but it often introduces ideas and terminology too suddenly and with very sparse explanations. Since this is not my area of expertise, I will opt for assuming that the math and derivations are correct, in which case I think this paper is probably a good contribution to the conference. The topic is clearly relevant, and the use of transformers is gaining prominence in in reinforcement learning, so analysis such as the one presented in this paper are of great interest. But again, I must qualify this opinion with the caveat that I'm taking the results offered at face value. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "D2QzKqBJaOX", "reviewer": "Reviewer_eLHD", "summary": "This paper concerns the theoretical understanding and relational reasoning of permutation invariant agents framework in MARL. It proposes offline MARL with the transformer and analyze the error bound.", "questions": "- The paper compares relational reasoning between self-attention and MLP through the width of NN, what about the parameters and computation?\n- Could the method execution decentralized?", "limitations": "- The environment is simple and can't empirically demonstrate the performance of the method.\n- The novelty is not enough. The paper extends single-agent offline RL and utilize set transformers as neural network structure.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- It utilizes self-attention mechanism that is widely used in cv and nlp to model relational reasoning between agents\n- It proposes both model-free and model-based offline MARL\n- It theoretically prove the gap does not scale with the number of agents and the proof is complete ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0L8achOwmf", "reviewer": "Reviewer_gWc2", "summary": "The paper tackles the problem of efficient offline RL in the multi-agent setting (MARL) that typically suffers from the curse of dimensionality as the number of agents grows. They argue that transformers are ideally suited for estimating the RL components (value functions/dynamics models) and are able to implement efficient relational reasoning between agents.\nThey combine model-free and model-based RL algorithms with transformers as function approximators for the value function and dynamics model respectively, and present theoretical results for the generalisation and suboptimality gaps for the resulting algorithms.", "questions": "See comments above regarding assumptions and applicability in more realistic settings. I would be also curious to know if the authors can say something about the online MARL setting when using transformers?\n\nGiven the topic of the paper (how a neural network architecture can give rise to efficient algorithms), it could greatly benefit from an experimental demonstration of the theoretical results.\n\nThe conclusions discussion should be part of the main text, not supplementary.\n\n", "limitations": "As mentioned before, the authors should elaborate on the assumptions necessary for the results and what we can expect in practice when they don't hold.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The papers main contribution is the theoretical analysis of MARL algorithms when using transformers for function approximation, showing that they can get significantly tighter bounds on the generalisation error e.g. for the model-free algorithm the error bound becomes independent of the number of agents.\n\nI am not familiar with details of prior work on offline MARL and the presentation of the paper made it often difficult to judge the significance and the originality of some of the contributions. E.g. \"we design offline model-free and model-based RL algorithms with the transformer approximators\" It seemed to me that the authors modified existing RL algorithms by simply replacing the function approximator used with transformers?\n\nI would have appreciated more discussion on the assumptions required for the results (to be able to identify which ones are the strongest), instead of simply referring to other works that make similar assumptions. E.g. the IID assumption (instead of sequential) on the offline data.\n\nThe paper is missing a discussion and/or experimental demonstration of how much of the favourable scaling properties would carry over to more realistic settings which would make the significance of the results a lot more clear.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept