Exploiting Structure in Offline Multi-Agent RL: The Benefits of Low Interaction Rank
Authors: Wenhao Zhan
Scott Fujimoto
Zheqing Zhu
Jason D. Lee
Daniel Jiang
Yonathan Efroni
Venue: ICLR 2025 Poster (2025)
Keywords: multi-agent reinforcement learning
offline learning
interaction rank
distribution shift
Primary area: reinforcement learning

Abstract: We study the problem of learning an approximate equilibrium in the offline multi-agent reinforcement learning (MARL) setting. We introduce a structural assumption---the interaction rank---and establish that functions with low interaction rank are significantly more robust to distribution shift compared to general ones. Leveraging this observation, we demonstrate that utilizing function classes with low interaction rank, when combined with regularization and no-regret learning, admits decentralized, computationally and statistically efficient learning in cooperative and competitive offline MARL. Our theoretical results are complemented by experiments that showcase the potential of critic architectures with low interaction rank in offline MARL, contrasting with commonly used single-agent value decomposition architectures.

Published as a conference paper at ICLR 2025
EXPLOITING STRUCTURE IN OFFLINE MULTI-AGENT RL: THE BENEFITS OF Low INTERACTION RANK
Wenhao Zhan'
Scott Fujimoto
Zheqing Zhu
Jason D. Lee
Daniel R. Jiang
Yonathan Efronit
ABSTRACT
We study the problem of learning approximate equilibrium in the offline multi-agent reinforcement learning (MARL) setting. We introduce a structural assumption- the interaction rank and establish that functions with low interac- tion rank are significantly more robust to distribution shift compared to general ones. Leveraging this observation, demonstrate that utilizing function classes with low interaction rank, when combined with regularization and no-regret learn- ing, admits decentralized, computationally and statistically efficient learning in offline cooperative and competitive MARL. Our theoretical results are comple- mented by experiments that showease the potential of critic architectures with low interaction rank in offline MARL, contrasting with commonly used single-agent value decomposition architectures.
INTRODUCTION
Multi-agent reinforcement learning (MARL) a general framework for interactive decision decision-making with multiple agents. Recent breakthroughs in this field include learning superhuman strategies in games like Go (Silver et al.] 2016), StarCraft (Vinyals et al.] 2019). Texas hold'en em poker (Brown and Sandholm, 2019), and Diplomacy (Bakhtin al. [0022). Additionally, MARL has been successfully applied in real-world domains, including auctions (Jin et al.) 2018). pricing systems (Nanduri and Das, 2007), and traffic control (Wu et al. 2017). However, most of these successes rely on online and iterative interaction with the environment, which enables the collection of diverse and exploratory data. In practice, online interaction with exploratory policies is often infeasible or prohibitive due to safety constraints, making it necessary to use offline datasets instead.
Several recent works have investigated the application of modern deep RI. algorithms to the offline MARL setting (Yang et al. [021] Tseng et al.) 2022] Wang et al.) 2024). Despite recent advances there remains a lack standardized methods that can effectively tackle complex, real-world problems beyond simulated or simplistic settings. Recent works (Cui and Du 2022al Zhang et al. 2023b) studied offline MARL from a sample complexity perspective. Specifically, Zhang et al. 2023b) designed the BCEL algorithm, sample-efficient algorithm for the offline general-sur MARL setting with general function classes. However, its implementation poses significant challenges due to the need to solve non-convex problem in the joint action space. Furthermore, the algorithm's sample complexity is tied to the unilateral coverage coefficient, which can scale exponentially with the number of agents in the worst-case scenario. This raises the following question, which becomes the focus of this work:
Are there any natural structural assumptions that allow for both sample efficient and computationally efficient algorithms in the offline MARL setting?
Recent lower bounds show that computing an cquilibrium in a MARL setting is hard in gen- eral (Daskalakis et al., 2009 2023). Nevertheless, for some specialized MARL classes, this need not
PPrinceton University. Work done at Meta.
Meta.
1 PPokee AL. Work done at Meta.
6 Sprinceton University.

---

Published as a conference paper at ICLR 2025
Offline Setting
Reward Assumption
Sample Complexity
Efficient
Algorithm
Markov Game
(C*))
x
Contextual Game
K Interaction Rank
0 (C*)
/
Markov Game w/
Interaction Rank
0 OC*K)
Decoupled Transition
Table I: Comparison of the results presented in this work (highlighted orange) and prior work. C is the single-agent coverage coefficient. Here we present the worst-case dependence of the sample complexity in the single-agent coverage coefficient, where N is the number of agents.
be the case. In this work, we study the MARL setting with low interaction rank (IR). In this setting the reward model decomposes sum of terms, each involving the interactions of only subset of the agents (Section[3) 3 Our key statistical result is that functions with low interaction rank are more robust to distribution shift compared to general functions. This result, which, as we show, has natural applications in offline MARL, may also be of general interest.
Assuming the reward model has low interaction rank, we leverage regularization and no-regret learning to develop decentralized computationally--ffiieee offline algorithms for the contextual game (CG) setting, and for Markov games (MG) with a decoupled transition model (Section and Section 5. Notably, prove that applying structures with low interaction rank allows these algorithms to achieve sample-efficient learning, avoiding the exponential dependence in the number of agents. Lastly, in Section [6] we empirically corroborate findings. This shows the potential of using reward architectures with low interaction rank in offline MARL setting, and the need to go beyond the standard single agent value decomposition architectures, which have been popularized for MARL (Sunehag et al. 2017 Rashid et al.) 2020: Yu et al. 2022).
Additional related works. Our work is related to the research on provable offline and decentralized MGs and factored critics in the empirical literature. See Appendix for more details.
2
PRELIMINARIES
We define the general offline multi-agent RL setting, which includes all of the models study.
General-sum contextual MG. A contextual MG is defined by the tuple M = (N, A:, {Ri, N.H (=1,A=1 where N is the number of agents and H is the horizon. C is the context space. In each episode, public context e E C, which is observed by all agents and stays invariant throughout the episode, is drawn from the distribution p. S; and A, are the local state and action spaces of the i-th agent. We assume the initial local state of each agent is fixed for simplicity, but our analysis can easily extended to accommodate stochastic initial states. Ri,, (c, 8, a) the reward distribution of agent at step h given the context c, joint state and joint action a. We assume the value of R,A lies in j0, 1] and denote the mean of R,,,, t by ri. In this paper, we study general-sum RL. (Littman 1994) and thus ri,,- C x S x A + [0, 1] can be an arbitrary reward function.
A= -
MGs with decoupled transitions. In this work we assume the transition of the local state only depends on the local state, public context and local action (Zhang al. 2023a DeWeese and Qu 2024 Jin et al. 2024), which can be characterized by the kernel PiA C x S x A. + As, for alli E Nj, E HH.. Note that the reward function R (c. 8, is still of a general-sum game and depends on the joint state and joint action.
The decoupled transitions property finds application many practical scenarios in- cluding sensor coverage, autonomous vehicles, and robotics, and has been studied under online decentralized learning setting (Zhang et al. 2023a DeWeese and Qu 2024 Jīn et al. 2024). For more general MGs, decentralized no-regret algorithms are hard to design even in full-informatton setting. As far as we know, Erez et al. (2023) is the only existing work which achieves sublinear regret in general MGs when all the agents adopt the decentralized algorithm. However, they only focus tabular cases in the full information setting or online setting with a minimum reachability assumption. Therefore, we leave it an important future direction to extend analysis to more general MGs.
Remark 1.
2

---

Published as a conference paper at ICLR 2025
Mr h==1 is mapping from C. x S to the simplex AA which determines the joint action selection probability under the public context and joint state at each step. Given
Policy and value functions. A joint policy = (
x,
{Tech [=
(Tthl== to denote the marginalized policy for agent i. In the
decentralized setting (Zhang et al. 2023a WeWeese and Qu 2024] Qu et al. 2020 Lin et al. [002]]
Jin al. 2024), each agent independently executes its local policy n, based only the public
context and its local state $1, i.e., II;= Ti where TiSh : xC + AA, for all In this case,
we call the joint policy a product policy.
Given reward function r; agent and joint policy и, we define the value function and Q-function as- sociated with agent i to be agent i's expected return conditioned on the current joint state (and action):
H
LA (c, (c,8) = E,
Σ
ra (c. 8IC, aw) 8,
H
(, (c, s. == Ex
Σ Tt,, SN,, aN.,
8, = 8, aj = a
Here. [.] denotes the expectation under the distribution of the trajectory when executing т in M. We will omit the superseript in Vith" and Q7 if is the ground truth reward y*
Decentralized offline equilibrium learning. For any joint policy æ, if each agent cannot increase its own expected reward by changing its policy while the other agents fix their policies, then π is a coarse correlated equilibrium (CCE) (Aumann, 1987p. More specifically, let II, == {ur C x S; + A denote the local policy class of the agent then an e-approximate CCE can be defined as follows:
Definition (Coarse Correlated Equilibrium). joint policy called an e-approximate CCE
(T), = max Ell
[V x x=- (c,, 81)] Ea-o (1, [N]
where π-₃ is the marginalized policy of x for all agents excluding i.
If π is a product policy and satisfies Definition T then π is the well-known Nash equilibrium (NE) Nash et al. 1950). Given the fact that NE can be hard to compute for even general-sum normal games (Daskalakis et al. 2009), our goal is to learn an e-approximate CCE.
In particular, we consider the decentralized setting where each agent executes its policy n. only based on the public context and its local state 8; (Zhang et al. 2023a De and Qu 2024 Qu al., 2020 Lin et al. [2021] Jin et al. 2024). For agent i, given a local policy म; [ Th(H and public context c, the transition of the local state is indeed independent from other agents and thus
we can define the local state visitation measure as follows:
0% (s|c) pa p (ss,n slc),
vh E [H] S,, E [N],
where Si,4 the local state of agent at step and pr (-lc) denotes the distribution of the trajectories under policy and public context c. We also define d (s,alc) := di ( (als). We want identify natural structural property for MARL, under which staristically and computationally efficient offline algorithm, which means that we assume access to an offline dataset D without allowing interaction with the environment beyond this.
can design decentralized
INTERACTION RANK IMPLIES ROBUSTNESS TO DISTRIBUTION SHIFT
In this section, we define the key structural property introduced in this work-the interaction rank (IR) of a function. We show that a function with low interaction rank is significantly more robust to distribution shift compared to general function in a standard offline supervised learning setting. This observation later enables us to derive sample efficient guarantees for the MARL setting. For an arbitrary function, define its interaction rank follows.
Definition 2 (Interaction Rank). A function f : X x Y1 x .... x Vw + [0, 1] has interaction rank K (K-IR) if there exists a positive integer K such that there exists a group of sub-functions Uocksk K ( (ginnni dx )n <.. which satisfies
K-1
far U1, 01,...,,W... ,W)
Σ
Σ
Ii. (x. Vi....... ........ W5.), .,,)) Vo E X E Ei,....
"h,...,yw, yw Vw.
0=
3

---

Published as a conference paper at ICLR 2025
Intuitively, the function can be decomposed into of 9. called sub-functions, each depending only on subset of the input variables. This structure is common in practice and finds application in fields including physics (Grana 2016). economics, (Asghari et al. 2022) and statistics (Vonesh et al. 2001).
Relation to Taylor series. When restricting the inputs of function to local neighborhood, Definition 2 can understood as a Taylor expansion function. To see this, fix an x E X' then any K K-differentiable function f in a local region of {Yw w==1 E II Vu can be approximated as
W
K
af v V............................... Ilw) θy,,
A
f(a ............. yw) = f(x 1/. vw)
Σ
II k'=1
Vie
Bys
Hence, the interaction rank of a K Korrder Taylor expansion is upper bounded by K ++ Further, if the Taylor series close to f. we can find a good approximation of f with low interaction rank.
Bounded interaction rank implies distribution shift robustness. The key property that makes functions with low interaction rank useful in the offline MARL is their robustness to distribution shift. Towards formalizing this statement, let us first consider an offline supervised learning setting. Suppose we wish to learn a target function f in an offline setting. The training distribution is p. 3/4 p-(-(z), Vi and the target distribution is p', Yi pf(()))), Vi. The distribution shift is quantified by the density ratio:
p' pxx ZEA p(x)
max
S CDs,
max ZEI. (b(
S Cos.
Let f denote the learned function. Standard guarantees imply that the training error (i.e., under p and p&) can be upper bounded by
M M................. )
S. ............))
E Euwpar lw (12))
(1)
When f' and f are general functions, the optimal worst-case learning error under the target distri- bution ((CDs)) ()))) which scales exponentially with the input size W. However, if f* and have bounded interaction rank, this result can be significantly improved; the error under distribution shift only scales exponentially with the interaction rank.
Theorem 1. If f and ff are K-IR, we have
(1-- "..)..........w)))) "w))" s
(2 - c.
Expop' an wpp (:lo))....wwwppp
Here for any two functions and g', g S g' means that there exists a constant e > 0 such that < eg' always holds. Theorem T indiicats that when K < W, function classes with bounded interaction rank are more robust to distribution shift and can significantly alleviate the curse of dimensionality due to multiple agents in offline learning. In MARI, W + will be the number of agents, while K is the interaction rank of the reward.
4 WARM UP: CONTEXTUAL GAMES
The robustness to distribution shift of low-IR functions suggests that such a property may be useful for offline MARL. Indeed, in the offline setting need to properly estimate quantities that deviate from the data distribution. To provide intuition for the benefits of low-IR reward classes and corresponding algorithmic design, we start by considering the contextual games (CG) setting as warm up.
Offline CG. The CG problem is general-sum contextual MG where S; = @ for all i and H = 1. To simplify notation, we omit the h subscript in Ts. and ni, for this setting. We assume the offline dataset D = DR where each sample (c, a = {a, 1. {r.)k=)) is i.i.d. sampled from
p, ~ va(-lc), T2 R (c, a) for all E [N]. We call 14 the offline behavior policy for each agent and use v to denote the product behavior policy [LEIN] 14. Let us assume for simplicity that we have learned
reward functions {fr E [0, 1]]ke[N] from the offline dataset with in-distribution training error
E Eerpary(-1o) (ri F3)2] S [ie
4

---

Published as a conference paper at ICLR 2025
Algorithm:
Decentralized <e-Reuulrd Policy Gradient. Given F, we propose decentralized, x² -rregularized, no-regret policy gradient based algorithm. As we show, this algorithm produces a set of policies which are near equilibrium. In each iteration t, each agent will update their policy via:
+ 1 (()
T. (c) = arg min mig AEAл:
(F(()) + x +xx(p,
(2)
rogularization
mo-regret learning
Here a.)) = (e) Fi(e, a)] is the expected reward of agent given that the other agents' policies are II my. The regularizer x2 v((c)) == E (eeeameeeelaataa/ll/e the x²-divergence between distribution and vi(c) and De,i(p, (c)) is the Bregman divergence between distribution p and (c):
- 1) is
Doslp, x((c)) = (p, - -2 x²(T((c) -
x())
(pla))=at1) xi(ale)) 21
) (i(a;le)
= =Ba
We denote the total number of iterations by T. Eq. 2 has two divergence terms, which serve different roles. We add the divvvvegee regularization term encourage the policy trajectory to stay close to the behavior policy 14 and thus lessen the distribution shift issue. On the other hand, to ensure the update enjoys no regret, we have Bregman divergence term which is motivated from the policy mirror descent literature (Zhan et al. optimization problem whose input size is only A, T Thus, for small action and state space we can solve it efficiently without incurring exponential computation cost as the number of agents increase.
2023a Lan 2023). Notably, Eq. (2) is a quadratic
The key ingredients of our algorithm are (1) regularization and (2) no-regret learning. We choose divergeen and its corresponding Bregman divergence for tractable theoretical analysis. In practice, other regularizers can also be utilized, such as KL. divergence (Rafailov et al.) (2024) or the La behavior cloning term in TD3 BC (Fujimoto and Gu [021]. Additionally, in practice, one-step online gradient (Zinkevich 2003 can be used as the no-regret learning algorithm.
Remark 2.
Theoretical analysis. Now we analyze the statistical sample complexity the above algorithm. the reward function class has no specific structure, the sample complexity can still scale exponentially with N due to distribution shift. To address this, we leverage a low-IR reward functiinn class:
Assumption 1 (K-IR Reward). Suppose that the interaction rank of rt and F. are upper bounded by K, with X C x A; and y;- = Aj in Definition for all E [N].
Assumption] T naturally holds in a variety of games. For example, polymatrix games (Howson Jr 1972. Kalogiannis and Panageas 2024 MacQueen and Wright (0024 characterize the reward function via pairwise interactions and, thus, for these settings Assumption T hholds with K = 2. In network games (Galcotti et al. 2010 DeWeese and Qul [024]] Park al., (024)), the reward only depends on the neighbors and thus Assumption [ holds with K equal to the degree of the network. Note that for all of these examples, we have K < N.
Now we introduce a bound on the maximum gap of the output policy गे under K-IR reward classes. Let r(=) be the expected reward under the distribution e p, a (--lc). Similar to existing offline RL analysis techniques (Xie et al. (02T], we split the bound into on-support and off-support components:
Theorem 2 (Informal). Suppose Assumption Tholds. Let II(C): == {14: EEao (xiroox((ns)) vx(c))] <
C} denote the policy class which has bounded xivvieergecce from the behavior policy v4, Fix any 8 E (0, 1] and select T,n, in Eq. (2) properly. Then, with probability at least 5, have
max Gap, S max min {c ((2N2) jx sx-1 subopt,(C.
(3)
xE[N] C21
where subopt, (C, 7) = el,, r (us, R-1) max max (1, R- .) is the off-support bias.
We call ICC a covered policy class because policies within it have bounded diverregee from the behavior policy which implies that can estimate their performance relatively accurately from the offline dataset. The right hand side of Eq. (3) can be viewed as a bias-variance decomposition of the gap. The first term is the variance term which
Optimal bias-variance tradeoff.
5

---

Published as a conference paper at ICLR 2025
measures the distribution-shie effect of comparing against policies from [C). The second term is the bias term which quantifies the performance difference between the global optimal policy and the optimal policy in the covered policy class. As C. increases, the considered covered policy class will expand and thus the variance term will grow while the bias term will diminish. Notably, our algorithm does not require any information about C' and the gap in Theorem 2 is upper bounded by the optimal C, which means that we can identify the best bias variance tradeoff automatically.
Polynomial sample complexity with single-agent concentrability. Let us consider the following
single-agent all all-policy concentrability coefficient Csin = max CEC. Mctaile)
(:(a:))) Note that
Can will not scale with N exponentially. Then Theorem 2 Iiplles that if Csin < oo, the maximum gap under the interaction rank structure can be upper bounded by
max (R) S Csin (2)2))-10)==T-
Therefore, given fixed K, we can learn an approximate CCE with polynomial sample complexity with respect to the number of agents N under single-agent all-poliey concentrability. This demonstrates the power of low-IR reward classes for MARI.. When combined with regularization and no-regret learning, the sample complexity is significantly improved, making computationally and statistically- efficient algorithm design possible in MARL.
Proof highlights. We provide a proof sketch of Theorem[2for K = 2, supplying intuition for how K- IR reward classes benefit theoretical sample complexity. For any agent i E [N] and policy μ4i E II(CC) where C' 1, we can bound the in-support gap Σ (rT x'.) - rz (m() as follows:
E pe-p)arr-pt).a... [1ri- (c)(c,
E Bespart ri (c, a)] + Σ Fi(m.Ti)) -T((T))
(3)
We need to bound terms (1), (2), and (3). Term (3) is the performance difference when changing the policy of agent i to μ4, Note that this is equivalent to the regret of agent i with loss function - and thus we can bound with similar techniques in policy mirror descent literature (Zhan et al. 2023a
Term (1) represents the reward learning error under the comparator policy l4: and learned policy x x-,- which different from v. To control it, we need tackle the distribution shift between the two. We use Fe. {g] Jiss and Po. ( Jise to denote the decomposition of r and f. and use Aj to denote g3 D7. Since we apply a K-IR reward class Assumption we can decompose term (1) follows
Bespariai
(1)))(r (e)
=Be-parmmii (c, + Σ Be EBeeparntth [j a, a,)
=
jii
Meanwhile, from the property of x² divvergee,, we have
E Beepparrm w (566) (+1e) [A) at a;)]
V V Berparas (-ee)
[A) (s,c,,,,,))) a;)) (1 x2 (po (1s x <2), o (vz v;)));
where we use oo p denote the joint distribution e P,a ~ p(-Ic) for some conditional distribution p. For the x" -divergeenc term, x² (c), (c)) bounded because μr is from the covered policy class; we can also upper bound x (c), (c)) due to the x² regularizer term in Eq. (2. Thus, we
only need to bound Ee-p, (ee))
(A) ai, a.)))))
This is non-trivial because we are only regressing with respect to r",, which is the summation of the sub-function g. and there exist infinite number of IR decompositions of r*. Fortunately, we are able to show that such an aligned decomposition exists:
Lemma (Sub-function Alignment for K = 2, informal). There exists a standardized IR decompo- sition of x* and f. denoted by 98.91.-. 91..... 9W and gu. "I...., .......0 ?: such that we have
Eeop (imp),ao(((())))ee [A] as (i, < 2e, Vj

---

Published as a conference paper at ICLR 2025
With Lemma 1 are able to bound term (1) efficiently. Term (2) can be handled similarly. Notably, Lemma Tholds for general K as shown in Lemma and the IR decomposition circumvents exponential scaling with N. The above discussion illustrates that fow-IR reward classes are quite effective when mitigating the learning error under distribution shift in MARI..
5 DECENTRALIZED REGULARIZED ACTOR-CRITI IN MARKOV GAMES WITH DECOUPLED TRANSITIONS
We ready investigate the benefits of low interaction rank in offline MGs. In partieular, will propose our main algorithmic framework to utilize low-IR function classes.
Offline dataset. We assume access offline dataset (Dn) Dr consists of M i.i.d. samples (c, {Si, aj & <<hE(N) (ri (re)))(N) where c ~ p. 8, ~ oiih d,,x(-1c), (-Ic),, ag ~ V (. s;), 8 ~ Pi,, (-cc, 8,, a;) and ra R,,, (c, {st, as hE(N)) Note that osh may not be the local state visitation measure d% (-lc). [IE[N] S.A.
We also use d% to denote
General function approximation. We consider the general function approximation setting, This makes the algorithm applicable potentially large or even infinite state space and action space. Suppose that we have function classes R = {R, to approximate the reward function ri where R. C fr C x A + [] for all i E [N]. In addition, we use function classes (P; HEENN where P. CP S; x A, - As;) to approximate the transition model. We assume here that R, and Pi are finite, but the analysis can extended infinite function classes naturally by replacing the cardinality of R, and P, with its covering bracketing number (Wainwright 2019). To simplify notation, we use [2] and (P| to denote max;e[N] RR and maX P.l
5.1 ALGORITHMIC FRAMEWORK
Algorithm 1 Decentralized Regularized Actor-Critic (DR-AC)
1: Initialize के be the behavior policy v4 for each agent
2: me Offline Reward & Transition Learning #a/
3: Compute for all [N], h E [W]]
Pinh arg min FER; (c.s,
Σ
(r()), Pr,a arg max PEP,
log (s, (ERD
Σ
4: for t = I,..,, do
5:
for i [ [ do you Critic Update #*/
6:
7:
Estimate the single-agent Q-function with the learned reward f; and transition P::
Ci Si, a.) L6
( ( (1o) Qi o sc, Vc C, E S. E A..
8:
fon Actor Update #w/
9:
Run mirror descent for all c C,
++1 (c. s) arg min - ( (c, + xx2(p, + 1 D Dosall, Pi (c,ss, PEAA,,
min
(4)
10: Return: the uniform mixture of [TEEN "
For general-sum MGs with decoupled transitions, we consider widely-used kind of algorithmic framework in practice, the actor-critic method (Barto et al. 1983). Arming it with regularization and no-regret learning, propose DR- AC for offline learning in MGs. The full algorithm is stated in Algorithm П Notably, DR-AC is a decentralized model-based algorithm which is computationally efficient given that estimation (MLE) problem. DR-AC consists two phases: offline reward and transition learning, followed by decentralized actor-critic updates.
able solve least squares regression (LSR) and maximum likelihood
7

---

Published as a conference paper at ICLR 2025
Offline reward and transition learning. We first learn the reward function F; for each agent using LSR on the offline dataset DR. In particular, here we will use a function class R, where all the functions have bounded IR that our learned reward has higher robustness distribution shift, as we have shown in the previous section. We also learn the transition model for each i via MLE on the offline dataset with function classes P.. Note that LSRR and MLE problems common in supervised learning and can be solved with simple methods like stochastic gradient descent (Jain et al. 2018)) The RL literature has also assumed the existence of efficient solutions these optimization problems. calling algorithms that depend on them oracle-efficient (Dann et al. 2018 Agarwal et al. 2020
Uehara et al., 2021] Song et al. 2022).
Critic update. In each iteration, for each agent i, we estimate its current single-agent Q-function, given other agents' policies, with the learned reward f and transition model P:
Di (c, St. a;) B (s), (+4)),5zi
O (c,
where we use T and 2h to denote the joint Q-function and local state visitation measure of π under reward F and transition P. In practice, we can simply use Monte-Carlo-type method to estimate @ be which only requires solving an LSR problem and is thus computationally efficient. See Appendix [oor more details.
Actor update. Given the estimated Q-function, we use regularized policy gradient to update each agent's policy. The update formula Eq. (4) is almost the same as the update in Eq. (2) for CGs, except the estimated reward is replaced with the estimated Q-function. We use divdieegeecce for regularization and Bregman divergence in Algorithm
Nevertheless, DR-AC allows other regularizers and no-regret learning techniques as mentioned in Remark [ Note that Eq. (4) is quadratic optimization problem with input size [A, and thus can be solved efficiently.
5.2 THEORETICAL ANALYSIS
We now present the sample complexity guarantee for DR-AC. We assume the function class (R.) and (PiheeN) are realizable.
Assumption 2. Suppose that we have ri,, E R2 and P E Poror all i [N], e [H].
In general, DR-AC can have exponentially large statistical complexity with respect to the number of agents N. However, similarly to the CG result, low-IR reward function class alleviates this. Assumption 3 (K-IR Reward). Suppose that the IR of is upper bounded by K with X' = CxS, and y, S Ay in Definition 2 for all j + i,r; & E R,,i,j E [N].
In addition, we assume that the offline dataset satisfies single all-policy concentrability for the local state distribution. Recall that osn is the dataset distribution.
(sle) Assumption 4. Suppose that for all E [N] we have cax, (.. S Cs < 00.
We need Assumption because bounded x" --divergeecce between the action probabilities of two policies does not imply bounded x² diveeregee between their state visitation measure. In DR-AC we can only regularize the action probability and therefore require additional concentrability for the local states. Nevertheless, here only need single-agent concentrability and thus Css does not scale exponentially with N. Now we can bound on the maximum gap of the output policy से by DR-AC: Theorem 3. Suppose Assumption 2 Assumption 3 and Assumption 4 hold. Let (C) = {ur Bo-perdd (-te) (Hs,n(c, s), V,, s))l S C, wh} denote the policy class which has bounded x². divergence from the behavior policy vi. Fix any 8 E (0, 1] and select
A
C 33
K-1 31443 H 3K (2N')
X
T
H² X2
RP
H
where ERP == R (8)
Then, with probubility at least 1 8 the output of DR-AC, म, satisfies:
max (ap, < max min KE[N] C21
CC H1 aw-2 (2N2) 3x
+ subopt (C,
RP
where subopt, (C, == max,; E BeNp(V '(c, 81)] max max (C) Bew V '(c,
8

---

Published as a conference paper at ICLR 2025
f an)
f(a ax)
A( ax)
Network
Network 1
Network N
Network N
Q
Joint-action
2nd order interaction rank (2-IR)
Single agent (1-IR)
reward critic
reward critic
reward critic
Figure Network diagrams for the ith agent.
Similarly Theorem 2
Theorem B indicates that DR-AC admits an optimal -ariinni tradeoff over the covered policy class (C). In addition, if we have single-agent all- all-policy concentrability
Csin CCE given sample complexity
0O, DR-AC capable of learning an c-approximate
25,6 (a; (0,8))))
C3++2 C5 ( K- log (N sin
M
3K
Therefore, given a fixed and single-agent all all-policy concentrability, DR-AC can learn an approxi- mate CCE in polynomial sample complexity with respect to N for general-sum MGs with decoupled transitions. This suggests that introducing low-IR structure to the reward class still beneficial for offline learning in general-sum MGs.
Remark 3. For (R), note that we require the function classes Ri to have IR bounded by K. This means that their complexity will al most only scale with K exponentially:
Comparison with existing works. To knowledge, Cui and Du (2022a) Zhang al. 2023b)
the only existing offline general-sun sum MARL works with provable statistical guarantees. However, the proposed methods are decentralized and require evaluating the gap for every possible candidate joint policies, resulting in an impractically high computational burden.
Statistically, although Cui and Du (022a)) achieves Ō(1/e²) complexity, they require stronger concentrability assumption, which the following unilateral concentrability with a target policy n*:
dhi (st, a.c)dd (s
max Cuni(==) h.i.p..c.aES,e S., aaE
((())))
where s.; and are the joint state and action of the agents excluding i. Note that the single-agent all-policy concentrability coefficient CsCain is indeed weaker than Cuni and we have CsCain S (T"i(T") for any x* In the worst case, Cuni can still scale exponentially with number of agents N. whereas our sample complexity scales with the IR K.
For Zhang et al. (023b), in CGs, they have the following concentrability assumption:
Bonggavsaa (e). 2
(u,,,, (R) = max E.
B
r+)
In their work R; can be general function class and thus C² (R, n can be as large as Cuni(T ( in the worst case. Notably, if we use function class with KIR instead, Theorem shows that Cy (R, ) < sin: Therefore, we indeed find a particular function class such that the concentrability in Zhang et al. (2023b) is not vacuous. For MGs, Zhang et al.] (2023b) uses function class to approximate the joint Q function while we use F to approximate the single-agent Q-function, and thus the results are not directly comparable.
EXPERIMENTS
In this section, we examine the practical implications of results. With this mind, our findings can be interpreted as providing the following guideline: Use reward or Q-function class with the smallest possible IR that can still represent the underlying true model. This approach strikes balance between two factors: it ensures realizability by requiring the model can be represented accurately. and it improves sample efficiency, as demonstrated in Theorem 2 and Theorem

---

Published as a conference paper at ICLR 2025
Maximum Gap
Implementation and experimental setting. To examine the usefulness of this observation, we study a simple of- fline CG environment. We implement the actor update in DR-AC to be a single gradient descent update with re- spect to TD3++G objective (Fujimoto and Gu 2021) from Tianshou library (Weng et al. (022). Further, recall that TD3+BC adds explicit La regularization term that keeps the policy close to the data collection policy and thus fits into the framework of DR-AC. To test the potential benefits of low rank reward critic architectures we exper- imented with three different types, depicted in Figure [ i) joint-action, ii) 2-IR, and iii) 1-IR reward critics. The reward critic is a general mapping from the joint action space to number, and, hence, is the most pressive; it can represent both 2-IR and I-IR. On the other hand, the 1-IR architecture is the least expressive, it can- not represent 2-IR reward models, since it only accesses single agent action. Notably, we choose the number of parameters of the 2-IR and joint-action architectures to be of the same order of magnitude for fair comparison.
6.0
4.0
1.0
100
200
300
Time Steps
2-IR critic Joint-action critic
1-IR critic
Comparison of TD3+BC in- stantiated with different critic architec- tures, i) 1-IR critic, ii) 2-IR critic, and iti) joint-action critic. The underlying true reward is 2-1R. This figure showcases the advantage of using 2-IR critic archi- tecture compared to 1-IR or the general joint-action crities when the underlying model is 2-IR. The shaded area repre- sents the standard error across trials.
Figure 2:
The details of our environment setting are as follows (see Appendix B for additional information). We consider the continuous action setting, where Vi E [N]. a; E [-1,1].
The underlying reward model is a 2-IR function of the form Vi = [N]. rf(s, = Σ}= a.ag/vN + where é ~ Uniform(-o о)) and o > O. Further, we set number of agents as N = 50. We collect offline data with the uniform policy and set the number of samples M such that oN/M - 0.1. In this noise regime, the reward model is learnable but the noise level may effect the training procedure. We experiment with few architectures for each reward critic type and report here the best one. We also experimented with an additional environment in which the underlying reward is a 1-IR model (see additional results Appendix B).
Results. Experiment results are depicted in Figure 2 The 2-1R critic approach leads to the best performing result by significant margin compared to the joint-action and 1-IR reward critics. For the 2-IR critic the maximum gap across agents is the smallest, meaning the joint policy is in near equilibrium point. Interestingly, the simpler 1-IR model has the worst performance among the three candidates. Such an approach for critic modeling is common in the online cooperative MARL setting (Sunchag et al., 2017; Rashid et al. 2020: Yu et al. 2022). Nevertheless, as our experiments show, it can dramatically fail in offline MARI. This because in the online setting, the agent can continually collect fresh samples to update the estimated 1-IR reward so that the critic can learn accurate local approximations of the current expected reward even if the other agents' policies change. However, in offline setting, a 1-IR critic cannot make such updates because iterative data collection is not allowed. In the offline MARL setting, single agent critic models may be severely biased and degrade the performance of the learned policies.
7 CONCLUSIONS
In this work, we investigated the benefits of using reward models with low IR in the offline MARL setting. We showed that learning an approximate equilibrium in offline MARL can scale exponentially with the IR instead of exponentially with the number of agents. Our proposed algorithm is decentralized, no-regret learning algorithm that can be implemented in practical settings while utilizing standard RL algorithms. The empirical results demonstrate superior performance of the critic with the smallest IR that can still represent the underlying true model in offline MARL, while the widely-used single-agent critic can fail catastrophically in this setting. Moving forward, building critics with low IR in MARL is a promising direction for future work, as well as exploring additional structural assumptions to alleviate the MARL problem.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020). Flambe: Structural complexity and representation learning of low rank mdps. arXiv preprint arXiv:2006. 108/4.
Asghari, M., Fathollahi-Fard, A. M., Mirzapour Al-E-Hashem, S., and Dulebenets, M. A. (2022). Transformation and linearization techniques in optimization: A state-of-the-art survey. Mathemat- ics, 10(2):283.
Aumann, R. (1987). Correlated equilibrium as an expression of bayesian rationality, Econometrica: Journal of the Econometric Society, pages 1-18.
Bakhtin, A., Brown, N., Dinan, E., Farina, G., Flaherty, C., Fried, D., Goff, A., Gray, J., Hu, H., et al. (2022). Human-level play in the game of diplomacy by combining language models with strategic reasoning, Science, (78(6624))1067-1000)
Barto, A. G., Sutton, R. S., and Anderson, C. W. (1983). Neuronlike adaptive elements that can solve difficult learning control problems. IEEE transactions on systems, man, and cybernetics, (5):834-846.
Brown, N. and Sandholm, (2019). Superhuman ai for multiplayer poker. Science, (65(6645)) 890.
Cui, Q. and Du, S. S. (2022a). Provably efficient offline multi-agent reinforcement learning via strategy-wise bonus. Advances in Neural Information Processing Systems, 35:11739-11711
Cui, Q. and Du, S. S. (2022b). When offline two-player zero-sum markov games solvable? Advances in Neural Information Processing Systems, 35:25779-25799..
Dann, C., Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2018). On oracle-efficient pac with rich observations. Advances in Neural Information Processing Systems, 1432-1422..
Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. (2009). The complexity of computing a nash equilibrium. SIAM Journal Computing, 39(1):195-255 259
Daskalakis, C., Golowich, N., and Zhang, K. (2023). The complexity of markov equilibrium in stochastic games. In The Thirty Sixth Annual Conference on Learning Theory, pages 4180-4234. PMLR.
DeWeese, A. and Qu, G. (2024). Locally interdependent multi-agent mdp: Theoretical framework for decentralized agents with dynamic dependencies. arXiv preprint arXiv:2406. 06823.
Erez, I.., Lancewicki, T., Sherman, U., Koren, T., and Mansour, Y. (2023). Regret minimization and convergence to equilibria in general-sum markov games. In International Conference on Machine Learning, pages 9343-9373. PMLR.
Fujimoto, and Gu, S. S. (2021). minimalist approach to offline reinforcement learning. Advances in neural information processing systems, 34:20132-20145.
Galeotti, A., Goyal, S., Jackson, M. O., Tega-Redondo, F,, and Yariv, L. (2010). Network games. The review of economic studies, 77(1):218-22) 244.
Grana, D. (2016). Bayesian lincarized rock-physics inversion. Geophysics, 8166))6225
Howson Jr, J. T. (1972). Equilibria of polymatrix games. Management Science, 18(5-part-1)3112-318
Jain, P., Kakade, S. M., Kidambi, R., Netrapalli, P., and Sidford, A. (2018). Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecificatioo. Journal of machine learning research, 18(223):1-42.
Jin. C.. Liu, Q. Wang, Y., and Yu, T. (2021). V-learning simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint ar 10.:2/100.15555
11

---

Published as a conference paper at ICLR 2025
Jin, J., Song, Li, H., Gai, K., Wang. J., and Zhang, W. (2018). Real-time bidding with reinforcement learning in display advertising. In Proceedings of the 27th ACM international conference on information and knowledge management, pages 2193-2201.
Jin, R., Chen, Z., Lin, Y., Song. J., and Wierman, A. (2024). Approximate global convergence of independent learning in multi-agent systems, arXiv preprini arXiv:2405.198/1
Kalogiannis, F. and Panageas, (2024). Zero-sum polymatrix markov games: Equilibrium collapse and efficient computation of nash equilibria, Advances in Neural Information Processing Systems, 36.
Lan, G. (2023). Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programmingg 198( 1):1199--1110
Lin, Y., Qu, G., Huang, L., and Wierman, A. (2021). Multi aaltit reinforcement learning in stochastic networked systems. Advances in neural information processing systems, 34:7825-7837,
Littman, M. L. (1994). Markov games as framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier.
Liu, Q.. Chung, A., Szepesvári, C., and Jin, C. (2022). When is partially observable reinforcement learning not scary? arXiv preprint arXiv:2204.08967.
MacQueen, R. and Wright, J. (2024). Guarantees for self-play in multiplayer games via polymatrix decomposability. Advances in Neural Information Processing Systems, 36.
Mao, and Başar, T. (2023). Provably efficient reinforcement learning in decentralized general-sum markov games. Dynamic Games and Applications, 13(1):165-186.
Nanduri, V. and Das, T. K. (2007). A reinforcement learning model to assess market power under auction-based energy pricing. IEEE transactions on Power Systems, 22(1):85-95.
Nash, J. F. et al. (1950). Non-cooperative games.
Park, C., Zhang, K., and Ozdaglar, A. (2024). Multi-player zero-sum markov games with networked separable interactions. Advances in Neural Information Processing Systems, 36.
Peng, B., Rashid, T., Schroeder de Witt, C., Kamienny, P.-A., Torr, P., Böhmer, W., and Whiteson, S.
(2021). Facmac: Factored multi-agent centralised policy gradients. Advances in Neural Information Processing Systems, 34: 14:012222222211
Qu, G.,, Wierman, A., and Li, N. (2020). Scalable reinforcement learning of localized policies for multi-agent networked systems. In Learning for Dynamics and Control, pages 256-266. PMLR.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. (2024). Direct preference optimization: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, 36.
Rashid, T., Samvelyan, M., De Witt, C. S., Farquhar, G., Foerster, J., and Whiteson, S. (2020). Monotonic value function factorisation for deep multi-agent reinforcement learning. Journal of Machine Learning Research, 21
Rashid, T., Samvelyan, M., Schroeder, C., Farquhar, G., Foerster, J., and Whiteson, S. (2018). Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. In International Conference Machine Learning, pages 4295-4304. PMLR.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre. L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016). Mastering the game Go with deep neural networks and tree search. nature, 529(7587):484 489.
Song. Y., Zhou, Y., Sekhari, A., Bagnell, J. A., Krishnamurthy, A., and Sun. W. (2022). Hybrid rl: Using both offline and online data can make rl efficient. arXiv preprint 22X.v:2210.067/6
Song. Z., Mei. S., and Bai, Y. (2021). When can we learn general-sum markov games with a large number of players sample-efficiently? arXiv preprint 10.04/44
12

---

Published as a conference paper at ICLR 2025
Sunehag, P., Lever, G., Gruslys, A., Czarnecki, W. M., Zambaldi, V., Jaderberg, M.. Lanctot, M., Sonnerat, N., Leibo, J. Z., Tuyls, K., et al. (2017). delomppccooooiiionn networks for cooperative multi-agent learning. arXiv preprint arXiv:1706.0522
Tseng, W.-C., Wang, T.-H. J., Lin, Y.-.., and Isola, (2022). Offline multi-agent reinforcement learning with knowledge distillation. Advances in Neural Information Processing Systems, 35:226- 237.
Uehara, M., Zhang, X., and Sun, W. (2021). Representation learning for online and offline rl in low-rank mdps. arXiv preprint 10.0665...
Vinyals, O., Babuschkin, I., Czarnecki, W. M.. Mathicu, M., Dudzik, A., Chung, J., Choi, D. H.,
Powell, R., Ewalds, T., Georgiev, P., et al. (2019), Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)350-3344
Vonesh, E. F., Wang, H., and Majumdar, D. (2001). Generalized least squares, taylor series lineariza- tion and fisher's scoring in multivariate nonlinear regression. Journal of the American Statistical Association, 96(453):282-91.
Wainwright, M. (2019). High- High-Dimmnssonal Statisties: Non-Asymptotic Viewpoint, volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
Wang, X., Xu, H., Zheng, Y., and Zhan, X. (2024). Offline multi-agent reinforcement learning with implicit global-to-local value regularization. Advances Neural Information Processing Systems, 36.
Weng, J., Chen, H., Yan, D., You, K., Dubureq, A., Zhang, M., Su, Y., Su, H., and Zhu, J. (2022). Tianshou: A highly modularized deep reinforcement learning library. Journal of Machine Learning Research, 23(267):1-6.
Wu, C., Kreidieh, A., Parvate, K., Vinitsky, E., and Bayen, A. M. (2017). Flow: Architecture and benchmarking for reinforcement learning in traffic control. arXiv preprint 1rXi::1710.05465, 10.
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning, arXiv preprint urXiv:2106.0694
Xiong, W., Zhong, H., Shi, C., Shen, C., Wang, L., and Zhang, T. (2022). Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint arXiv:2205.1555
Yan, Y., Li, G., Chen, Y., and Fan, J. (2022). Model-based reinforcement learning is minimax-optimal for offline zero-sum markov games. arXiv preprint arXiv:2206.04044, 5:21.
Yang, Y., Ma, X., Li. C., Zheng, Z., Zhang, Q., Huang, G., Yang, J., and Zhao, Q. (2021). Believe what you see: Implicit constraint approach for offline multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 14:10999-10311
Yu, C., Velu, A., Vinitsky, E., Gao, J., Wang, Y., Bayen, A., and Wu, Y. (2022). The surprising effectiveness of ppo in cooperative multi-agent games. Advances in Neural Information Processing Systems, 35:24611-24622
Zhan, W., Cen, S., Huang, B., Chen, Y., Lee, J. D., and Chi, Y. (2023a). Policy mirror descent for regularized reinforcement learning: A generalized framework with linear convergence. SIAM Journal on Optimization, 33(2):1061-100
Zhan, W. Uchara, M., Kallus, N., Lee, J. D., and Sun, W. (2023b). Provable offline preference-based reinforcement learning.
Zhan, W., Uehara, M., Sun, W., and Lee, D. (2022). Pac reinforcement learning for predictive state representations. arXiv preprint
Zhang, R., Zhang, Y., Konda, R.. Ferguson, B., Marden, J., and Li, N. (2023a). Markov games with decoupled dynamics: Price of anarchy and sample complexity. In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 8100-8107. IEFE.
13

---

Published as a conference paper at ICLR 2025
Zhang, Y., Bai, Y., and Jiang, N. (2023b). Offline learning in markov games with general function approximation. In International Conference on Machine Learning, pages 40804 40829. PMLR.
Zhong, H., Xiong, W. Tan, J., Wang, L., Zhang, T., Wang, Z., and Yang, Z. (2022). Pessimistic mini- max value iteration: Provably efficient equilibrium learning from offline datasets. In International Conference on Machine Learning, pages 27117-27142. PMLR.
Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (ieml-03), pages 928 928-936 238-936.
14

---

Published as a conference paper at ICLR 2025
A ADDITIONAL RELATED WORKS
We would like to point out that for offline general-sum Markov games, there are no existing decen- tralized and provably efficient algorithms and this field is under-explored. Our work can be viewed as a first attempt towards this objective. For more background information, the related works are stated in the following.
Provable offline MGs. Cui and Du (202bb) studies offline tabular zero-sum Markov games and Yan et al. (2022) improves the complexity to minimax optimal. [Zhong et al. p: Xiong et al. (2022) further extend the discussion to linear function approximation. However, the above works are all limited to two-agent zero-sum games. For multi-agent general-sum Markov games, the only existing works are Cui and Du (2022a); Zhang al. (2023b), where Cui and Du (2022a) investigates the tabular setting and later (Zhang et al. (2023b) proposes a centralized algorithm with function approximation. Nevertheless, both of them centralized and computationally inefficient since they need to evaluate each possible joint policy, whose complexity will scale with the number of agents exponentially. In comparison, our method is decentralized and computationally feasible.
Decentralized algorithms in general-sum MGs. In the online setting, to learn CCE for a general- sum MG, Jin et al. ): Song et al. (202T); Mao and Başar (2023) proposed V-learning and Daskalakis et al. (2023) introduced SPOMAR. However, these algorithms cannot achieve no-regret and depend heavily on collecting fresh samples, thus cannot be extended to the offline setting trivially. For specific no-regret decentralized algorithms, as far as know, |Erez et al. (2023) is the only existing decentralized work which achieves sublinear regret in general-sunt MGs (and thus is able to learn CCE). Nevertheless, they only focus tabular cases in the full information setting online setting with a minimum reachability assumption, which are drastically different from the offline setting.
Factored critics. Another closely related line of work is the utilization of factored critics in empirical studies. Since (uneehag al. (2017) proposed the value decomposition networks (VDN), factored critics have been widely applied in the online cooperative MARL setting. Rashid al. (2018) further proposed QMIX, Q-learning type algorithm which utilizes a non-linear mixing network to combine single-agent critics, and Peng al. (2021) extended the discussion into actor-critic methods. Nevertheless, most of these works focus on online cooperative MARL and lack thcoretical analysis. Our paper indeed formalizes and generalizes these efforts by introducing the interaction-rank structure. As matter of fact, VDNs are exactly a 1-IR critic. We further show that the idea of factorization in critics is also useful in offline general-sum MGs, but in general you need critics with higher IR than VDNs for offline learning, as discussed in Section 6
15

---

Published as a conference paper at ICLR 2025
B ADDITIONAL EXPERIMENTAL DETAILS
In this section we give additional information on the experiment design. Additional apper-paramttrrs related to training are given in Table
Our high-level implementation follows the framework of DR-AC and has three steps:
1. Data collection. Collect data via uniform policy, where each agent executes a random action aj ~ Uniform([-1, 1J) for E [N].
Learn critic. Learn N reward critic models using LSR and the collected offline data. Namely, for each agent E [NV] estimate reward critic by solving the following LSR:
arg min rER: (a,r.)DD
Σ (r(a)-ri)*
We experiment with three types of reward critic types, namely, different reward classes R,: I-IR, 2-IR, and joint-action critic models. We solve this by gradient descent, which iteratively samples a batch from Da, and takes gradient step. Our method returns the critic with the smallest validation loss, calculated with respect to a holdout validation dataset, through the course of training. Lastly, during the run the critic does not show improvement after number of steps specified by the 'patience" parameter we stop the run (see Table A for hyper- parameter values).
Learn actor. Apply TD3+ BC on all agents to get a policy per agent.
Next elaborate the critic architectures used and their implementation.
Joint-action critic. We experimented with architectures with 3 layers and 2 layers. Recall that N is the number of agents. The layer architectures of size N x width x width x width x 1 where width E [512, 1028, 2056], and the 2 layer architectures are size x width x width 1 where width E [128, 512, 2056].
2. 2-1R critic. We experimented with 2 layer architectures of size 2 x width x width X 1 where width E [64, 128, 256). For the 7t agent, there are N such networks, where each network represents the interaction term with the jth agent. Let this network be denoted as DNN,;
A A + IR. With these, the reward of the ith agent is given by
ia(a) = Σ DNN.y(a;,0))
3. 1-IR critic. We experimented with 2 layer architectures of size 1 x width x width x where width [128, 256, 512), where the only input to the network is the action of the 2t agent.
The metric which we measure is the maximum gap defined by
Σ Tj JE(N]
max max EE [E[N]aE(-1.1)
+
Hyperparameter
Value
Critic learning rate
le-4
Critic batch size
64
Patience parameter for critic
20
Actor learning rate
le-3
Actor batch size
64
Number of epochs
500
Optimizer
Adam
Policy architecture
MLP, layers, width 128, ReLu activations
TD3+BC parameter
# of trials per experiment
10
Table 2: Hyperparameters used in the experiments.
16

---

Published as a conference paper at ICLR 2025
2-1R Critic
Joint- Aiint-Action Critic
1-IR Critic
6.0
8.0
8.0
Maximum Gap
Maximum Gap
Maximum Gap
4.0
6.0
6.01
2.0
0.0
100
200
300
400
500
1000
200
300
400
500
100
200
800
400
500
Time Steps
Time Steps
Time Steps
2-1R critic (2 layers. 64)
Joint-action critic layers. 128)
1-IR critic (2 layers. 128)
2-IR critic (2 layers, 256)
Joint-action critic layers, 512)
1-IR critic (2 layers, 512)
Joint-action critic layers, 2048)
Joint-action critic (3 layers, 512)
Joint-action critic (3 layers, 1024)
Figure 3: Comparison of TD3+BC instantiated with different critic architectures, i) 1-IR critic, ii) 2-1R critic, and iii) joint-action critic. The underlying true reward is 2-IR. The shaded area represents the standard error computed across trials.
Joint-Actionn
1-IR Critic
Maxinam Gap
Moxinam Gap
0.995
0.8
0.990
Maximum
0.5
0.4
0.2
0.2
0,980
0.0
200
200
300
Time Steps
Time Steps
Time Steps
2-IR critic (2 layers, 64)
Joint-action critic (2 layers, 128)
1-IR critic (2 layers, 128)
2-IR critic (2 layers, 128)
Joint-action critic (2 layers, 512)
1-IR critic (2 layers, 256)
2-IR critic (2 layers, 256)
Joint-action critic layers, 2048)
1-IR critic (2 layers, 512)
Joint-action critic layers, 512)
Joint-action critic (3 layers, 1024)
loint-action critic (3 layers, 2048)
Figure Comparison of TD3 +BC instantiated with different critic architectures, i) 1-IR critic, 2-1R critic, and iii) joint-action critic. The underlying true reward is 1-IR. The shaded area represents the standard error computed across trials.
where ny is the policy for agent (note that here deterministic policies). In particular, the above expression obtains its maximum at +1.
Details of the environment with the underlying reward of 2-IR are presented in Section 6 Figure depicts additional results that measure the performance of various architectures for the 2-1R envi- ronment. As observed, the 2-IR critic consistently performs better compared to the joint-action architecture and the 1-IR architecture.
We experimented with an additional environment in which the underlying reward model is 1-IR reward model of the form Vi E [N), ri (s. a) a² + Additional parameters of the environment are similar to those described Section 6 Since the underlying reward model the 1-IR critic type result in good performance. Further, since the 2-IR critic is not significantly more expressive compared to the I-RR critic, we may expect it to have good performance as well. Figure depicts the results of this experiment for all reward critic types and architectures. These show that both the 1-IR and 2-IR reward critics have good performance, whereas the joint-action critic performs significantly worse with respect to the maximum gap metric.
1-IR, we expect
17

---

Published as a conference paper at ICLR 2025
C Q-FUNCTION ESTIMATION
In this section provide computationally efficient method estimate 0 in Algorithm We assume access function class (FF) where F; (ff C S; x A, - [0, H]} approximate the single-agent Q-functions. The full algorithm is shown in Algorithm 2
2 s,,)) (-(c) and then roll out the joint policy x' in P. can be observed that the cumulative reward is indeed an unbiased estimate Q2, (c. Si,,, ai,h). Notably, we sample the state Si,6 from the offline dataset to leverage the offline information. We also sample asa from 1 V + f such that the actions can cover the current policy oi, and the competing policy Mi,h- which has bounded -ivieeeeeecce from Vi Then only need to run LSR the collected batch to estimate the Q-function. summary, we can see that Algorithm can be implemented with LSR oracles.
Specifically, in Algorithm we will sample c P,Si,h
ax,
T 81,h), ) (8 (8-i,h, a a-iA))
Algorithm 2 Q-function Estimation
1: Input: Estimated reward f, estimated transition P. policy лL, step h, agent i, function class F;
2: Dsim + 0.
3: for m 1 Msim do
4: Sample c~ p.
5: Execute n' in P with public context until step h.
6: Denote the current joint local state excluding agent by s Reset the state of agent to
be $i.h ~ oiA (-Ic).
7:
Execute a; ~ (-le, s.,n) + T (-Ic, st,n) and a-i.h ~ (l,, s.))).
Continue to execute the joint policy n² P until step H.
8:
9:
Compute the cumulative reward staring from (c, 8h, an)) by q under the reward model F. Add (c. 8s by 9) into D Dsim-
Run LSR: Q arg minser, Eienn (f(c, Si ai,)) - q)
Return: Qi,
C.1 THEORETICAL GUARANTEE
Next we want to show that the estimated Øi, is close to Qi, We have the following lemma:
Lemma 2 (Q-function estimation error). Suppose Qi, E for all t, i, h and Assumption holds. With probability at least 1 - 8, we have for all i, h, H4 E [1,(C) that
E Eenppsii (lc) (0i - (c, ). 8:) - si) (-),ss,
CCsH2 log F1/6)
Msm
Recall that for any two functions g and g', g S g' means that there exsits a constant C > such
that g < og' always holds. Note that from the phoof of Theorem 3 Lemma
2 suggests that we can use Q as surrogate of Qi and Theorem 3 still holds as long as Msim 2 COsH' (og(NTH)
22 Therefore, Algorithm 2 is indeed computationally and statistically efficient Q-function estimator.
Proof of Lemma 2 From the guarantee of LSR (Lemma 13 we know with probability at least - that for all t [T] [H]
-in ( (Qin(rssa)) - 85, )
B Beg..troo..klllaeretaaa...... (ase.)))
Ha
Msim
18

---

Published as a conference paper at ICLR 2025
Therefore, from Gauchy-Schwarle we have
CsH² log( (
E eo (+1))aaaa (1,ss) [ (c, s1, a.) Qin (c, Si, ai) 2
Maim
On the other hand, since ba [C),)), from Lemma 5 we know
COs H2 CCsHllogg(N NoTTH
E ofvpparddf (1e)), (leh)ammaa((ssss) [ (c, - -,, SV
Msim
Therefore we have
(-c, E Borporrndt (oth(e,s.)) 8t. (1 si))
CCs112 (
Mam
19

---

Published as a conference paper at ICLR 2025
D PROOFS IN SECTION 3
D.1 PROOF OF THEOREM
1
We first define specific IR decomposition for any function f in 2efinition that useful in the rest of the proof.
Lemma (Standardized IR Decomposition). For any function I with interaction rank K and training distribution p. Vi pi(-)z), Vi, there exists group of sub-functions UosksK-1L0/, S.hieeee where
(1)) 10 JN (1,9 .. ,, =
(5)
for all k E [K- - 11 E [k] x E X. X. E V/ + and
K-1
f(r,00 yn.
yw) Σ
Σ
Ly Sc (v, Yor." . Nb.),, Vo E X, E ".,,""., E Vw-
K=0
We call this group of sub-functions VoSRSK-Ild, 1o se biree the standardized IR decomposition of f.
The standardized decomposition separates the variations and mean of f under the training distribution. With Lemma we are able to provide an upper bound per-sub- function fitting error by simply fitting their summation
Lemma 4 (Sub-function Alignment). For any functions 8 and I with interaction rank K, let UbgagK 1 (Ih..- Jy his-<jj and Uogagk-1 Win... 1 "n ds Jn sis denote the standardized decom- position of f and f in Lemma 3 Assume that the following holds
((f*--)te (x) Vr. .. .Bw) ) Se.
E Serup.ii<iiiii ())))) pw (-1x)
Then for any K and S j1 < ... < W, have:
[A (z, Ujai ".,,,, my,))²] s 22",,
Bz-pan ri (12).. a9 ~p (1x)
where Ajjr.. == 9j..... -f 5
Lemma limpies that the learning error of standardized sub-functions can be upper bounded by the fitting error f efficiently when the interaction rank is small. This property the key reason why interaction rank is more precise measure of the function complexity than the input size.
Now let 1- de Ih Th...--je and decomposition of f* and Then from Lemma we know for any 0 < k S K-1 and ji jk
se bi....... <.... denote the standardized
that
Ex-p.nn Paj (12))) Ma mpn (-w)
(A (z, Mi.
-b,))) s 2%c,
which implies that
Eywo'' Mi wply (+1)) us rppn (-1x) (A (x. Mir... Mo v),)) s (CDs)*+122 (6)
On the other hand, we know
(f* - Vı, ,r,)),,
Eggee' un (11z), aw mh (:10)
27
- a' mepl (-1x)),- uw uppp (la)
Σ
Ajur de (2, Mir.... "....,ii -Mje)
K=0 18h SWW
K-1
SWK-1
Σ
Σ
Exep' on mpl, (110) Mys ~p/, (11) (An in (a, "h. ,),,)) ,)))))
K=0 154 SWeW
20

---

Published as a conference paper at ICLR 2025
where the last step is due to AM-GM inequality. Now substitute Eq. ( into the above inequality, have
E Ex en map (-le),. ww Myy (12) (10 -
Ma, (1, vi,
( CDsC.
This concludes proof.
D.2 PROOF OF LEMMA 3
From Definition which satisfies
2
know that there exists group of sub-functions Ub5AsK-110h Jehs
K-1
f(z, U1 ... vw)
Σ Σ
Iir de (z, W ... ..,,), VX E X, eV,, , E Dw.
0= IS
We prove the proposition with induction K. First for K 1, Lemma
3 holdd naturally. Now
suppose the proposition holds for K where K 2 2. Then for any (5 K-1 we can construct Gn JK
(I. Uir -ix-1) as follows:
L/ Jx_1 (x,, Vir""""" . Vix 1) = 9h i (1, Wir Vix .)
Σ -4sK-
Σ
Byn, ~pn, (la))) Mn ~nny (a) [9 Jx- (I, Uo. -ix-1
It can be verified that -..... (z, "y. Vik-.) satisfies the property of standardized decompo- sition, i... Eq. (5). Now consider the function f":
JK-
f' uw) = f(x "..... .yw)
Σ
Ln... jx 1 (Z. 1 -Mjx-1).
Note that f' satisfies Definition 2 with IR K 1. By induction hypothesis, we know there exists standardized decomposition for
K Σ Σ
f' (x, (1.,,,," ,,,)
Lnnt. au (1, Unr -..)). Vo E &. E . vw E Vw-
K=
where -ha,- satisfies the requirement in Eq. 5 for all k E [K - 2]. This implies that we have
K-1
f(r yn. vw) Σ
Σ
Ln de (z. (0. Yo. ... M5.). vx E X, E ",, ,y E Yw:
K= SSh
where Lf ....i satisfies the requirement in Eq. 5 for all k E [K - 1]. Therefore the argument holds for K as well. By induction we can prove the proposition.
D.3 PROOF OF LEMMA 4
Fix any 5 K 1 and 1 < f1 ... < S W. With slight abuse of notations, also use and f to denote the expected function value under the training distribution:
(" Mi. ". ,95)) = Ey (11)
f(x, Vy..... Bb.) : Enymps (n) vid F(x V1....
"e.eV......."". .
From Sauchy-Schwant inequality, we can observe that
[ Ma, Ui.... ..)))) (85)) <c
E Ex-pan mp (M))
21

---

Published as a conference paper at ICLR 2025
Since considering standardized decomposition, from Lemma
we have
(x, .1be))
Σ
(2, Mii""
"
Wiu )
k=01shh
far,yi .bh)) Σ
Σ
Ii Sig (0, Miny
Now we use symmetrization trick to prove the result. Consider the following symmetrization operation of function f:
(x, Mehhew (uh hew!
Σ
(-1)*
Σ
(a, tuy heth Jeb tus )ethi
W0=0
1sh C..
It can be verified that (Z)) Am Jem hew
Σ (-1)
Σ
Iir su (2, Wuc wen tu hetherr
k=
Ishe
This implies that we have
-G(
- (z, tu hew, he(w))
Σ
(-1)*
Σ clukk
A inr in henhhe Jub Ltrn Jee(h... 121))
k==0
(8)
On the one hand, from AM-GM inequality and Eq. 7 we have
Exop.vy MP (/ ~py, (l
(G((+-)) (yx heM, Ltl ((mh)))
9]
S 22k
On the other hand, we can expand the left hand side of the above inequality:
(rar- - (x) hEIN (2/ )1e ) "]
Egpppss, ~pn (100),,, - (t)
27
-B ~Pnn (-1)),, ME)
Σ
A so (z, fug heg deb (u (w)))r)))))
15h S....
=2" EeEnopuy ~Ps ([))) [A) de (z, Wi.
U 11,
where the second step is due to Eq. (8) and the third step is because the cross terms are 0 due to the independence between yj and v/ given x and Lemma Therefore we have
Ezzp,y, ~p,, (+x)) vs ~p (-1x) [ (z, Mir... .Mi)))² < 2he,
which concludes our proof.
22

---

Published as a conference paper at ICLR 2025
E PROOF OF THEOREM 2
We first present the formal statement of Theorem 2
Theorem 4, Suppose Assumption 7 hold. Ler [L((C) == {uy : (ec=plx2(uuee) & C} denote the policy class which has bounded x² -ddivergence from the behavior policy vi. Fix any (0, and select
T (2N2)
2K-2 3k-16 3k-1,
1 = == ==N== K 1
Then with probability at least 6, we have
max Gap, (T) S max min {o ((2N2)(-1) कर- + (U, SE|N] C21 C21
i
where subopt, (C, f) = m en, (1 k-1) max()en,(C) rf (14, R-1) is the ofp-support bias.
Proof of Theorem 4 Note that for any agent i [N] and policy μr II,(C) where C >
have
= Σ -
Σ B Be
-c)
T
T
Bespand [fA - r +
Σ
(fo(1s ( - -f((x'))
(2)
(3)
With slight abuse of the notations, we use UoS du and JocksK- ( g. Ju to denote the standardized decomposition of r and f., as defined in Lemma We also use A j1. .ju
to denote
-h -j.... Je First note that from Lemma 4, we have for all i E [N], S A S K 1 and
1 15 < ... j N where ji + i for all E [Ai] that:
Ber.p.areeettt)) wanh MEM
(A) in (c, ai, ,a,,))
s 2
(10)
Next bound terms (1), (2) and (3) in Eq. 9 respectively.
Bounding term (1). For term (I), from Lemma 3 we know for all policy μ4 E II((C) where C' 2 1 that:
Pexparrp..ee)e.... (Holl F.)(c,
K
Σ
Σ
Benpaarpp(t (o). [A (c, ai " ,a,))]
k= 1511 SEN.CHENNNNAAAM
To quantify the above transfer error, have the following lemma which leverages the -iveergee between the target distribution and training distribution:
Lemma 5. For two distributions d' d² A(Z) and any function f defined on Z, we have
E Exndi [f(2)] ( xxd)
Proof.
Note that we have
(d) x+)))²
(z))
1 I+ (d' (dd, Σ
(()))
d2
ZE2
2EZ
Then the lemma comes directly from Cauchy-Schwartz inequality.
23

---

Published as a conference paper at ICLR 2025
From Lemma we have
Bempar-aa(( (lo).
A (c, as 9p. ,.))))
20mpa (1),,) [A an aj.." .. (gr)))
1 1 x+
pa
14 x
"
po
U4 x
Vj
[E(K]
[E(M]
S 2
1+ x2
po
F4 x
Jt
po
14 X II
Vi
[E(R]
LE
where recall that we use p to denote the joint distribution e ~ Ps ~ p(-lc) for some conditional distribution p. In the last step we utilize Eq. (TO).
Now we only need to bound x²-divergence between po Me IIa Th. and p 14 o IIE Vi- We
achieve this with the following lemma:
Lemma 6. For any 2k policies {p,
1 and {gz } 1/-1. we have
1+x po
II
Pj.
Po II
4j j=1
Eovp
II [1+
Proof. Note that we have
1 1+x 2
Σ
po
Pj.
p
45
p(c) [Ij (z(a)(c)
j=1
C,LL a2
[ (IEEM))())))
Σ (ps(ayle))
E(()) p(c)
Σ
Eple) II
1I (a(a)(c)
(aylc)
R1 ak
SE(K)
Σ p(c) II (1+ ((())))))))))))))
Bewp
II (1 + x² (p)(c),
jE(k]
Therefore, from Lemma 6 we have
1+x²
po
14
.po
II Us [E(K]
lElK
(11)
= =Bevp
(x² (x²(4((c), +1) II
+1)
[E(K)
Meanwhile, from the policy update formula Eq. we have for E [T] and C:
- -FF((e 7. (c)) + Ax (m) (c), + D (c),
1
S -- (c) + Xx 2 (m)(c),
Dr, (((()( 7
Note that (c)( and デ [0. 1]. we know
(c. S (T
24

---

Published as a conference paper at ICLR 2025
Since (c) (v((c)
0, for all e [T] and S we have
x (m(r(c) (())
- WE(T+1
(12)
Substitute Eq.
12
into Eq.
11 and we have
T
x+ po x
po
14 X
V
<
E Ecup (x=((x())) 1)]
(C+
[E[R]
LE|M
where the second step due to μ E (C). Therefore, we have for all policies μ4; II)(C) where C 1 that
(T k
boo (. (A de a .amh) 2 V VCe
(7)
This implies that have
K-1 (1) E
C Ich-poas (T) S sTICe
2TN2 K-1
(13)
A
Here C is the combination number.
Bounding term (2). Similarly, for term (2), following the same arguments as bounding term (1),
we know for all policy μ4 E (C) where 2 that:
27
(. Ju (c, as, a ag,)] s V (E)) + 1)-
(e w (O)
Recall that (p) denote the chi-squared divergence x2 (c)).. Then with AM-GM inequality, we have
Bexp,arnn/(e)... ~T) (c).V [ A di (c, aijaa)i"""
_aj.]]
NK-1
27
27
NK- B (Tx
6 + V6.
A
)
1
Therefore, we have
T. X
(2TN2)
K-1
2T K-1
22) E (c)))))
A TETTVC
(14)
Bounding term (3). First we have the following lemma to characterize the no-regret guarantee of regularized policy gradient (see Appendix [.r proof):
Lemma 7 (No-Regret Regularized Policy Gradient). Given sequence of loss functions {l' heen
where 1. X' y + [0, B) for some > and a reference policy v X + Ay. Suppose we initialize p to be and run the following regularized policy gradient for T iterations:
p" p= arg min - (1, ))p) + xx (p. + Dz(ppp') pEAy
1
where (x(p.p') p¹) is the Bregman divergence between p(x) and p¹ (z). Then we have for all policy and x E X that
T+1 Σ ((M)) (2)) (x)) + Σ
T
(z) & TX+ 1) x² ((((=), +
nTB² 4
Note that (3) Σt, Exnp (F)(c), (c))). Thus, Lemma 7 implies that for any policy
#4 E (C), we have:
T (3) + A Σ
C -+ Ex-ol (e STCA + 1)
nf
(15)
t=1
25

---

Published as a conference paper at ICLR 2025
Putting all pieces together. Now substituting Eq H4 E (C) where 2 1 that
13
14 (5)
into Eq (
we have for all policy
C CA
2T K-1
2T
K-1
(1i, 7-))
n + + V
Ce
Therefore by setting
2k-2 T T= Jn- E -x-
7 y= = (2N2)
J उーー
K-1
we have for all policy ,r E (C) where C that
(1), - r. (R) (22N3)K-1)) 1
This concludes our proof.
E.1
PROOF OF LEMMA 7
Let (p) denote the diveeeggee x² (p(z), (z)). First due to first order optimality in the policy update step, we know for all p: X - Ay and all t [T], E X that:
(-)l + (1 (1)
(x)) 2 0.
(16)
This implies that for all t E [ E X' and any policy μ4, we have
(() + -
++ - x (z))
(VIL()'*) -V/l((")))-\//())),_r./ 1p0-' (s)) + (1pl (z), + (x) (x)
x² (xx)
(p' (2+ +
()) (na n1)s(()),
(12(x++1) - Vfz(D'), (a() - pp' (x)) + (z), ( (1))
(4)
(8)
(nAVS(('' ), m(x) (² - (
Next we bound terms (4), (5) and (6) respectively.
First for term (4), note that we have the following lemma:
Lemma 8. For any i [N] and pt, P2, Pa X - Ay, we have for all X
f V
px()) = D2(ps, P2) - (2s, P1) - Dr (P1,
Proof. By definition, we know
D') fx(p') (V -
Substitute the definition into Lemma and we can prove the lemma.
From Lemma we can rewrite (4) follows:
(4) = ('()'')) - Dz(up D=(ptt1,10
Then for term (5), from Cauchy-Schwartzz inequality, have
(5) < (ulx) (w)l=)) (1 u))²
4 S D.(0't..p)) 'D') 122 4
v(y|xr)
yEy
where the last step comes from the definition of D...
26

---

Published as a conference paper at ICLR 2025
Finally for term (6), Since fz is convex, know
- p(xx) = - -
This implies that
(6) S n ( - (z(ott)))
In summary, for a E [7], 8 E S and any policy ns we have
(nt(x), - pp)))) + n>f=(p") - n)f=(()
S (Dx(H,,') - DD(mpp'*)) nn (falo') + B²B²
4
Therefore, summing up from t = 1 to T. we have
T+1
Σ ((d) S (TA+ :)) (((())) t=1
+ nT'B² 4
Σ ((())) + X [=1
where we use the fact that D2 (1. p²) = (2, (()(())
27

---

Published as a conference paper at ICLR 2025
F PROOF OF THEOREM 3
Let fc..., to denote the x²-divergence and policy 1ss (C) where C 2 we have
Note that for any agent i [N]
T
Boup Vition"ur" (c, (c,81)] - Beup
V 2,1 Vii (c)
H
E
[r sn, an) Fcnlc,sn,
1= cop.8nndd
(1)
H
T
+
E
pompsn exppa (10)a))a))() [ 8h, an) + fan(c, sn, an)l
1= 1=1
T
Beup
Villor1:5
(c, s1)
Eeup
puuion J.P
(c, s1i]
11l
(3)
V (c,8))
[irl ((,' (c,
E
Bewp
Eoup
T
E Eonp
Duioo
(c, (c) Eeup
Pei (c,
t=1
(5)
T where we use i, to denote the joint value function under reward and transition P. Next we will bounded these terms separately. In particular, terms (I) and (2) are bounded by statistical guarantees on the reward model and the distribution shift robustness of low IR models; term (3) and (4) are bounded by the statistical guarantees of the transition model, while using the decoupling property, and term (5) is bounded by no-regret analysis while identifying proper value and Q functions that satisfies Bellman equation.
We use Uo -o) .n } and UOSkCK-I Ji to denote the standardized decomposition
of ri and Pi,k, as defined Lemma 3 We also use A A,, ji to denote "i di. S..h Js From Assumption 2 and the LSR guarantee Lemma
13 with probability at least 8/2 2 we have for all
i [N]. H] that:
Log(N /6)
E Combining the above inequality with Lemma 4 we have for all [N], E [H], k -1 and S f1 .... < jk I where o for all I E [k]
- Fn,lc, a,)) -
= ER.
M
that:
(n (c, Ros " ",,,,, .2/22) )² 2*ER.
Rerppsroanssteeeereettteet sost wos))))) ~y, (le,,,))
where we use z, denote (sj, az). Next we bound terms (1), (2) and (3) in Eq. respectively. For term (1), fix h E [H] and t E [T], then we know
E
pronf
(as am) [ri 8h, an) Prjn 8h, an)
coep, on
(10))
K
Σ
B
A Jhm (c, zi, "...".. (2)))
omp,e (10),,
(1oo) (10))3
K=O 1Sh
28

---

Published as a conference paper at ICLR 2025
With similar arguments in the proof of Theorem
2 from Lemma 5
we have
E
exp,zardd (16)),2; (-1c),01 A (c, R1. 2gh
(Hsoraaaaaassarorraaaaaa)aaaa)a) a (A Jem Se (c, (s, .. :.,,,,,,,,, ,2,ee)
27
1 x+
po
dl
X
II
P4 x
j
p
d
о
x II V/
[E[K]
[E[K]
[E[K]
LE
(C5)&+I2SER
x+ po
d
II [E|K]
h
P4 X
T
p
d
Th
X
II
[E[K]
[E[K]
LE(R
On the other hand, from Lemma
6
we know
TH
x² po
dh
II LE[K]
d
pi
po
d
II [E[K]
d
Vi
Va
SC
(E(A)
[E(R)
This implies that
2TH
31 Sk (c, R4, 2511 ... ...,))) S o
a of (16)) ddy" (-6)).
Therefore we have
22 K-1
(1) S TH
CCK
CR-
Similarly, term (2) is bounded by
CSTH A
(2) TH
(2N2) ERR
For term (3), note that we have
Σ
Fe,ble, sh. an)
Mponl
with
((o))a))maaallaaaea (ont in)
E
coup,nn No
groont
[r (h, 8h, ax)l
T
Eeup
Σ
mooT hp
alc - ar -s (s, alc)
quos
h=1
R.G
At the same time, due to decoupled transition, we have the following lemma: Lemma 9. For any policy product n, we have for all [H] that
N
Eexp Σ
d. alc)
E
Eawp
Σ Asiay
1h (s)
a.a
Thus, from Lemma we only need to bound Benp Esj,o, (s). (s,, asl0) for any agent j and single-agent policy πy. This is achieved in the following lemma:
29

---

Published as a conference paper at ICLR 2025
Lemma 10. For any j [N] and single-agent policy Ty, have for all h [H] that
Beup
Σ K5:4g
dh
(s),,alo - T2 (s), aslo)
( (10) || (14
PjN (tc,s,))))
On the other hand, from the guarantee MLE the literature (Liu et al. 2022 Zhan et al. 2022 2023b) (Lemma 14), we know with probability at least 5./2 that for all [N [H]
||| P3n(-1e,33.a) P,, 85,
No P1/))
M
(17)
From Lemma 5 this implies that with probability at least 5/2, we have for all j E [N], h [H] t M4 E (C) that
e
[| Pan (11,,,1,8) (ta (1, st |11] 2 VCsCep,
(18)
P3n (ac)))Pj,,(kc Pj 8j. ag) |11 -
CSTHEp
(=p(s (10)
A
Therefore, we have
OSTHEP
(3) S HTTVCCCCPp + H A
For term (4), following the same arguments for term (3), we have
CsTHep
(4) (
For term (5), we first need to show that the expected single-agent Q function Qi, satisfies Bellman
equation. In particular, let Q == E8 اا (1o))ii
@ (c, 8, a)] for any product policy
and we have the following lemma:
Lemma 11. Given a joint policy m_s for agents except for all [N], e [H]. C, S, a E A, and policy pt, we have
PMOOT GA
(c, 81) = Fampia((ee)))
(c, (C,,84,0
QuoT-I.F 1,
(c, Bi, a;) = i. an (in a)l + 1E Pe
D (c, st)
4hh+1
Lemma 11 indeed implies that Quien i5 (c, is valid Q function w.r.t. to the reward func-
tion E a ()),,,))-6 ((-le (F, s, a)] under transition model P and thus have the following performance difference lemma:
Lemma 12. Given a joint policy - for agents except for any policies μs and plg we have
H
Dalon oF (c, Darox i (c,8).1=
Σ
E 8i
KQuee (c, P. 82,6) - me, (l)(())))))
h=1
Now given Lemma
12
we have
T
5
Eowp
D.
(c, (c.)).)) - Eewp
Vi1
30

---

Published as a conference paper at ICLR 2025
H
8,,
- =L. (-c, (i))
Comp. (-lc)
B p.00 (110
(c (L - mtn(tesss))
(6)
TH
Beou
Σ
dh (s:lc)
dh (silc)
h=1
(7)
Apply Lemma and since μ4 E IT((C), we have
HC N (6) THAC+
4
From Lemma 10 and Eq. 18
we have
(7) TTHSHSCCCCPP..
Therefore, we have
Beep
Vuro arr (c,81)
Eewu Vi1 (c,s1)
CsTH
K
HC nH3
CSTHEp
S H C
(2N2)K--ER + HAC +
H CsCep + H2N
A
Tn
4
A
Let
2K T = Cs
H 3x (2N2)
3K#7
ERP
1)
Cake
3x-2 (2N2)
3n-22 ERP
C C. H. 1x (2N2)
K-1 3r+2
where ERP
and then we have for all μr E II,(C) that
M7
Ecup Vilie- (c, (c. Boup (,1((,,,)) & &00 T0 H 3 (2N2)
K
1,1
RP
This concludes our proof.
F.1 PROOF OF LEMMA 9
Note that given the distribution of (sj, (j) is independent from each other due to the decoupled transition. Therefore we have
Egoo
Σ
(s. (T alc)
Eaup
Σ
II JE(N]
The (s)))
JE[M]
Now for any 0 S k N- consider the following difference:
T = Boop
Σ
II 15J5k
de (1))
II K+1S
(sg,
II 15/5k+1
(33,
II k+251EN
8.a
Note that we have
4. Eexp
(s),a())))
II
(s), 2
J. (x+1))
g d ax+1le)
18iSk
k+2SiSN
=Eewpp
Σ
(8441,
the (8++1,00+11c)
Sk+1.0411
31

---

Published as a conference paper at ICLR 2025
Σ
II
II
*- -k(+1) a- (k-1) 15iSk
k+2SISN
Σ
T 18441,04110 dp
dn dxttt (sk+1, ax+1l))
8k+11004+1
Therefore we have
N-1 I
Bexp
Σ
-
Σ 1s Σ Bexp
Σ
dh (s),
-dh Th (2)) (sse
This concludes our proof.
F.2 PROOF OF LEMMA 10
Let òn denote Beup EEs,ay
(83. - dx (sy, agle)]
Then we know 51 = 0. In addition,
for any S h S H. we have
6n Bomp
Σ
Σ
( (0
-Eeup
Σ
h
3. (5))
sjjia'
Σ (1 sy
< &ooup
Σ
Σ
Mjing
s'jia'
Ee-p
Σ
85.05
< Eoxp Σ
(110 (3 ( (asci))-ppnnsa s)
Eaep
{= - (5,,
32

---

Published as a conference paper at ICLR 2025
Σ
(3)())l(8)), (000s(())))
Pyn(ssle, af)
Σ
Tan(ayle
Asiasios
+ Eeup
Σ
-
Σ
85.0g
Bexp
Σ dgy1
P3a(tglc(8),,a) Paalssle,ol..ip
Σ Tan(asles
Σ
(5- (5.1 Σ Panlsyle,
Eexp
Syiing
05,05
cmplls a,d 22 [ Pl P),-1(-1,, 85 ag) [|]
+ 5
Therefore, we have
Ecop
Σ
(s) aglc) ao (s), (1)
om (Hkc) ||| (1c, (1,85);)))) - (1c,, I.]
This concludes our proof.
F.3 PROOF OF LEMMA
First it can be observed that D.u.o-11P (c,85,h) E Bendd Dunox-n (c, 8n)]
Note that we have
Qu1 (io Si., = B B ((11)
E
(c, an) sn.
=/=hh
E (e ((1)) (r,n Sh, ax)l
H
(i 88 an) I
+ R (e (11))
R B
Σ
W=++1
where we use E,, { to denote the distribution of the trajectory when executing joint policy n with transition model P.
On the other hand we know
H
E poo
Σ
Pe,ale, Sw, an) aw))c, (alle,,,,.ww)e
c, 8h, an
W=++1
-I -- P P.t.ir
E EpoT
Σ
fr, sw, sww sht11
sht1
W=i+1
DIoo (c, (c)
_E B
Therefore we know
Qu:oT-1i (c, Si,h, aijh)
= (x - (11) FFin 8h, an)
Dmoo- 1,41 (c, 88+1)
+ E M Pt u.) - (1lh (ww.swanaaaeeeeeeeee
33

---

Published as a conference paper at ICLR 2025
[iioo (c, (c,
E (a i a in in (1e) Pi,n (c, Sh, an) + E Ralaaaaaaall ant
B (a- '(1c) Fi,n 8h, an) + E Ruanr-Ralllaassaan
pho (c,
(c,88,011) s1,bttt
1
This concludes our proof.
F.4 PROOF OF LEMMA 12
Let (c, st, a.) denote E (a= (t,(c,,,,)) From Lemma
11
we have
H
1,2 81,1)
Vuuox-ii -1 (c, = Eyi
Σ
Fanle, Fe SLA,
vu (c,
4,1
1,1
(c, SLA,
+ Eby (8.11) Vi V (c.
2=
Rgg
Σ
+ BRy [oute " "(e, (6,1111)111) - Vilann is "e,,,, (1,2) - Villo i "( (c))
2
Exg
(e
St,,, ann) e
- Egg
(c, 81,2)
E
[1 (c, ), (-l,, 81,1) μ4, (-le, st,1))]
$,.1 (1))
Here the first step is due the definition of value function and the third step is due to Lemma 11 Now apply the above arguments recursively to Eng and we have
E (c, sa,b
s... ann) Bug [V (c, s12)
11
Vilio yo - (c, 86,1) V
V.NOR-
(c, 81,1)
Σ
E
(e ), (1c, - me, (11,
a (110
h=1
This concludes proof.
34

---

Published as a conference paper at ICLR 2025
G AUXILIARY LEMMAS
Lemma 13 (Song et al. (022 ). Let {I Um))m= be M samples that are independently sampled from 2m p and Ym ql- [mm) f (Imm em where em random noise. Suppose that ym E [0, for all m E [M] and we have access to function class G X + [0, 1] which satisfies
f E G. Then if {cm]me are independent and (mmmmmll= f (Im), we have with probability at
least 1 8 that
-f (gg(())/))
M where ] = arg min seg Em=1 (mm) vm)² is the LSR solution.
Lemma 14 Zhann et al. (2023b)). Let {(Im, Fm) } be M samples that are i.i.d. sampled from Im p and ym q-(--2a( (m)m)) Suppose we have access probability model class Q which satisfies qº' Q Then we have with probability at least 5 that
10g()
Ex-p [177-100) gt (110)) S
M
where q = arg min gE@ Em=1 log (10ml (m))
the MLE solution.
35


Reviews:
[{"review_id": "L4DgSDvkM6", "reviewer": "Reviewer_nwcs", "summary": "This paper proposes a new notion of interaction rank to characterize the structure of a Markov game. If the true reward function and the learned reward function has a low interaction rank, then the authors designed decentralized \\chi^2 regularized policy gradient approach and prove it converges to a CCE. The idea of low interaction rank is interesting. It may have potential in practice to help understand a wide range of multi-agent RL problems.", "questions": "1. Can the authors explain the on-support and off-support components in Theorem 2? The off-support component depends on the gap between the best response policy of agent i over the entire probability simplex and the best response policy within a bounded $\\chi^2$ divergence ball. This seems to be due to the $\\chi^2$ divergence regularizer in the algorithm. It is not clear here whether such a $\\chi^2$ divergence regularizer is a wise choice, though it may provide some convenience for the analysis, it limits the performance of the obtained policy.\n\n2. The authors then define the C_sin, which can be infinity due to taking the max over $\\mu_i$ if $\\nu_i$ is zero for some action a_i and context c. This reviewer is curious whether the single policy concentration coefficient can be defined here, and the optimality gap can be derived as a function of the single policy concentration coefficient. (similar comment for assumption 4).\n\n3. Can the authors provide some examples where the low interaction rank assumption can be satisfied? If given unknown environment, how to verify such a low interaction rank assumption?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The notion of interaction rank is new and interesting. The authors provide statistical convergence and sample complexity guarantee under the assumption of low interaction rank for decentralized Markov game.", "weaknesses": "1. The assumption MGs with decoupled transitions is very restrictive.\n\n2. Assumption that the reward function and transition kernel belong to the function class is restrictive. Further assumption that the function classes are finite are not practical at all. \n\n3. The algorithm 1, line 3, estimating the transition kernel may not be as easy as it looks to be. Solving for the arg max in practice will be difficult. \n\n4. In the discussion on page 9, the authors claim that existing studies are not decentralized. However, it looks to this reviewer that the advantage in this paper may come from the assumption of decoupled transition.", "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": "", "extra_scores": {}}, {"review_id": "lf5cjUABTM", "reviewer": "Reviewer_8HY6", "summary": "This paper introduces a structural assumption -- the interaction rank (IR), and establishes that functions with low interaction rank are more robust to distribution shift compared to general ones. The authors show that learning an approximate equilibrium in offline MARL can scale exponentially with the IR instead of exponentially with the number of agents. The proposed algorithm is a decentralized, no-regret learning algorithm that can be implemented in practical settings while utilizing standard RL algorithms.", "questions": "* By leveraging the low interaction rank assumption, the proposed algorithm achieves a sample complexity that scales exponentially\n with the interaction rank instead of number of agents. Meanwhile, there exists a constant as the coefficient of the sample complexity that hides behind the operator \"$\\lesssim$\". How to understand the constant? Does it scales with the problem size?\n* In extreme case where the problem has full interaction rank, does the proposed sample complexity orderly equal to the case that scales with number of agents? If not what makes the difference?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper leverages a structural assumption that shows the potential of using reward architectures with low interaction rank in offline MARL setting with an orderly better sample complexity, which seems to be a promising future direction.\n* The paper is well-written and easy to follow.", "weaknesses": "* I don't see much discussion on related MARL or RL literature regarding interaction rank or similar assumptions. Discussion on literature of related topic would help determine the novelty of the idea and quantify the contribution.", "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": "", "extra_scores": {}}, {"review_id": "Sx8TyTc7Vo", "reviewer": "Reviewer_MR2u", "summary": "The paper first shows that if the underlying problem has low interaction rank then it is robust to distribution shifts coming from the mismatch between training and target distributions. Then the authors propose a decentralised algorithm for multi-agent offline reinforcement learning and explicitly derive a performance guarantee that depends on the interaction rank of the function K. The theoretical results are verified with experiments on a toy problem.", "questions": "- The authors considered specifically the decentralised setting. I wonder if a better performance guarantee can be obtained if we assumed centralised setting.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper states a clear research question and draws clear conclusions that explicitly show low interaction rank games are easier to learn. While this result is not surprising, it is good that the paper explicitly derives it and quantifies this dependence.\n-  The paper proposes a novel algorithm, which is decentralised and can learn from offline data.", "weaknesses": "- The empirical evaluation is limited to one toy problem only, with no real-world experiments\n- The paper could use a more explicit related work section. For example, currently when reading the paper it is not clear what is the state of the art when it comes to offline, decentralised, MARL and how does the proposed algorithm compares to it.", "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": "", "extra_scores": {}}, {"review_id": "fRAJ5otP07", "reviewer": "Reviewer_oM8M", "summary": "The paper studies learning a coarse correlated equilibrium in the offline multi-agent reinforcement learning. By imposing assumptions on the interaction rank of reward models, the paper establishes a sample complexity bound that grows exponentially with respect to the interaction rank, instead of the number of agents. Finally, the author use numerical experiments to examine the effectiveness of the proposed algorithm.", "questions": "* I wonder does similar property applies to the cooperative setting? I would like to hear the author's insight on the difference between these two settings (cooperative and competitive).\n* In MARL, another widely-used property is the exponential decay of transition dynamics, e.g., [1,2]. From a intuitive perspective, is \"low interaction rank\" basically assumes a similar property, instead of on the transition dynamics, but on the reward structure? If they do share relevant ideas, I suggest the authors also discuss in the paper. Also, do you think the exponential decay property can be used to alleviate the current decoupled transition property in the paper? \n\n[1] Qu, G., Wierman, A., & Li, N. (2022). Scalable reinforcement learning for multiagent networked systems. Operations Research, 70(6), 3601-3628.\n\n[2] Ying, D., Zhang, Y., Ding, Y., Koppel, A., & Lavaei, J. (2024). Scalable primal-dual actor-critic method for safe multi-agent rl with general utilities. Advances in Neural Information Processing Systems, 36.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper is the first that proposes a decentralized algorithm for offline general-sum MARL games and establishes its probable statistical guarantees.\n* The integration of interaction rank to MARL provides an interesting yet also technically non-trivial angle. \n* The paper flow is good, and the author uses contextual games to serve as a toy example to help readers understand the idea of the paper. I like the proof sketch provided for the contextual game when K = 2.", "weaknesses": "* The authors are encouraged to release the codes of the numerical experiments.\n* Just a suggestion, maybe the author can consider using Markov Game or MG to replace RL in the title or in the abstract. I feel like people usually refers to the cooperative setting when saying MARL.\n* The considered problems are contextual game, which does not have the notion of state, and transition-decoupled MG. I believe the author could directly brought up the transition decouple assumption in the problem formulation, since it is an assumption on the setting instead of technical assumptions.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)