AlberDICE: Addressing Out-Of-Distribution Joint Actions in Offline Multi-Agent RL via Alternating Stationary Distribution Correction Estimation
Authors: Daiki E. Matsunaga
Jongmin Lee
Jaeseok Yoon
Stefanos Leonardos
Pieter Abbeel
Kee-Eung Kim
Venue: NeurIPS 2023 poster (2023)
Keywords: Offline Reinforcement Learning
Multi-Agent Reinforcement Learning
TL;DR: We introduce an offline MARL algorithm which effectively avoids selection of OOD joint actions.

Abstract: One of the main challenges in offline Reinforcement Learning (RL) is the distribution shift that arises from the learned policy deviating from the data collection policy. This is often addressed by avoiding out-of-distribution (OOD) actions during policy improvement as their presence can lead to substantial performance degradation. This challenge is amplified in the offline Multi-Agent RL (MARL) setting since the joint action space grows exponentially with the number of agents.
To avoid this curse of dimensionality, existing MARL methods adopt either value decomposition methods or fully decentralized training of individual agents. However, even when combined with standard conservatism principles, these methods can still result in the selection of OOD joint actions in offline MARL. To this end, we introduce AlberDICE,
an offline MARL algorithm that alternatively performs centralized training of individual agents based on stationary distribution optimization. AlberDICE circumvents the exponential complexity of MARL by computing the best response of one agent at a time while effectively avoiding OOD joint action selection. Theoretically, we show that the alternating optimization procedure converges to Nash policies. In the experiments, we demonstrate that AlberDICE significantly outperforms baseline algorithms on a standard suite of MARL benchmarks.

AlberDICE:
Addressing Out-Of-Distribttio Joint Actions in Offline Multi-Agent RL via Alternating Stationary Distribution Correction Estimation
Daiki E. Matsunaga
Jongmin Lee
Jaeseok Yoon KAIST
KAIST dematsunaga@ai. kaist. ac kr. jongmin her.iinneeebbbeeeeeyycom edu jsyoonßai. jayoon ac.kr
UC Berkeley
Stefanos Leonardos
Pieter Abbeel
Kee-Eung Kim
King's College London
UC Berkeley
KAIST
stefanos. www.ardos@cnnnee....mcc ac. pabbeel@cs. bebbeel@cs..erreeeey berkeley....... edu
kekimokaist.ac ac. kr
Abstract
One of the main challenges in offline Reinforcement Learning (RL) is the distri- bution shift that arises from the learned policy deviating from the data collection policy. This is often addressed by avoiding out-of-distribution (OOD) actions during policy improvement their presence can lead to substantial performance degradation. This challenge amplified in the offline Multi- Agent RL (MARL) setting since the joint action space grows exponentially with the number of agents. To avoid this curse of dimensionality, existing MARL methods adopt either value decomposition methods or fully decentralized training of individual agents. How- ever, even when combined with standard conservatism principles, these methods still result in the selection of OOD joint actions in offline MARL. To this end, we introduce AlberDICE, an offline MARL algorithm that alternatively per- forms centralized training of individual agents based on stationary distribution optimization. AlberDICE circumvents the exponential complexity of MARL by computing the best response of agent at time while effectively avoiding OOD joint action selection. Theoretically, we show that the alternating optimization procedure converges Nash policies. In the experiments, demonstrate that AlberDICE significantly outperforms baseline algorithms on standard suite of MARL benchmarks.
1 Introduction
Offline Reinforcement Learning (RL) has emerged as a promising paradigm to train RL agents solely from pre-collected datasets [6]. Offline RL aims to address real-world settings in which further interaction with the environment during training is dangerous or prohibitively expensive, e.g.. autonomous-car driving, healthcare operations robotic control tasks 3
39 One of the main challenges for successful offline RI. is to address the distribution shift that arises from the difference between the policy being learned and the policy used for data collection. Conservatism is commonly adopted principle to mitigate the distribution shift, which prevents the selection of OOD actions via conservative action-value estimates [II] or direct policy constraints [6].
However, avoiding the selection OOD actions becomes very challenging in offline Multi-Agent RL (MARLP) the goal is now stay close to the states and joint actions in the dataset. This is
'Equal Contribution
We assume cooperative MARL for this paper in which agents have common rewards.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

not trivial since the joint action space scales exponentially with the number of agents, a problem known as the curse of dimensionality. Previous attempts address these issues include decomposing the joint action-value function under strict assumptions such as the Individual-GGooallMaa (IGM) principle AD [3 36 40], or decentralized training which ignores the non-stationarity caused by the changing policies of other agents [8] 25 38). While effective in avoiding the curse of dimensionality, these assumptions are insufficient in avoiding OOD joint action selection even when applying the conservatism principles.
To illustrate the problem of joint action OOD, consider the XOR game in Figure In this game, two agents need to coordinate to achieve optimal joint actions, here, either (A, B) or A). Despite its simple structure. the co-occurrence of two global optima causes many existing algo- rithms to degenerate in the XOR game [3]. To see this, suppose we have an offline dataset
{AA, A, O), (A, B, 1), (B, A, 1))- In this situation, IGM- methods 40) represent the joint Q(a1: (02) as combination of individual @1 (a1) ) and Q2(02), where action B is incentivized over action A by both agents in the individual Q functions. As consequence, IGM-based methods end up selecting (B, B). which is the OOD joint action. Similarly, decentralized training methods [25] also choose the OOD joint action (B, B), given that each agent assumes that another agent is fixed with a data policy of selecting A with probability 2 Furthermore, we can that even behavior-cloning cloniigg end up selecting OOD joint actions as well: each individual policy T1 (a1) and T. (a2) will be uniform over the two individual actions, leading to uniform action selection over the entire joint action space; thus, both (A, A) and (B, B) can be selected. Consequently, OOD joint actions can be hard to avoid especially in these types of environments with multiple global optima and/or when the offline dataset consists of trajectories generated by a mixture of data collection policies.
B
A B
1
0
Figure 1: XOR Game
3-
the expert-only dataset, i.e., D {(A, B), (B,A)) A)). may
Our approach and results To address these challenges, introduce AlberDICE (ALternate BEst Response Stationary DIstribution Correction Estimation), a novel offline MARL algorithm for avoiding OOD actions in the joint action space while circumventing the curse of dimensionality. We start by presenting a coordinate descent-like training procedure where each agent sequentially computes their best response policy while fixing the policies of others. In order do this in an offline manner, we utilize the linear programming (LP) formulation of RL for optimizing stationary distribution, which has been adapted in offline RL [4] stable training procedure where value estimations of OOD actions are eliminated. Furthermore, we introduce a regularization term to the LP objective which matches the stationary distributions of the dataset in the joint action space. This regularization term allows AlberDICE to avoid OOD joint actions as well as the curse of dimensionality without any restrictive assumptions such as factorization of value functions via IGM or fully decentralized training. Overall, our training procedure only requires the mild assumption of Centralized Training and Decentralized Execution (CTDE), popular paradigm in MARI. 17 28 30
where we assume access to all global information such as state and joint actions during training while agents act independently during execution.
Theoretically, we show that our regularization term preserves the common reward structure of the underlying task and that the sequence of generated policies converges to Nash policy (Theorem 4.2). We also conduct extensive experiments to evaluate our approach on a standard suite of MARL environments including the XOR Game, Bridge [5], Multi-Robot Warehouse (27), Google Research Football [12] and SMAC (3I], and show that AlberDICE significantly outperforms baselines. To the
best of our knowledge, AlberDICE is the first DICE-family algorithm successfully applied to the MARL setting while addressing the problem of OOD joint actions in principled manner
2 Background
Multi-Agent MDP (MMDP) We consider the fully cooperative MARL setting, which can be formalized as a Multi-Agent Markov Decision Process (MMDP) (4 An ---geett MMDP is defined by a tuple G (N, S,A, r, P. po. 7) where A' = {1, .,,,,...A ..N is the set of agent indices, E S is the state, A = Ar x x AN is the joint action space. Po A(S) is the initial state
2 "Our code is available at htttpss: / //gittttttubbb com comm//eematsunagg/lbbrrdd.
"We consider MMDPs rather than Dec- POMDP for simplicity. However, our method can be extended to the Dec-POMDP settings shown in the experiments. We provide further details in Appendix [.]
2

---

distribution, and y E (0, 1) is the discount factor. At each time step, every agent selects an action a, E A; via a policy (s()) given a state s E S, and receives a reward according joint (among all agents) reward function r: :S x A + IR. Then, the state is transitioned to the next state s' via the transition probability P S A - (S)) which depends on the global state 8 and the joint action a = {a1..... aN) } E A and the process repeats. We also use a_; to denote the actions taken by all agents other than i.
Given a joint policy श = [ n (or - {T., - when we single out agent i E N), we have that (aas)) = π (arls) ( a1) ......aaall ai,..... .N. If the n; 's can be factorized
into a product of individual policies, then π is factorizable, and we write π (alss) = [ - Ty (ayls), We denote the set of all policies as II, and the set of factorizable policies as Il.. Given joint policy T,, a state value function V and a vvauue function Q? are defined by:
V (s) = E Ei= at) s]; Q (s. a) E Ei= 7'((s,, as) 8, ag a]
The goal is to find factorizable policy ı E y that maximizes the joint rewards so that each agent can act in a decentralized manner during execution. We will consider solving MMDP in terms of optimizing stationary distribution. For given policy æ, its stationary distribution dx is defined by:
d' a) = (1- 1 7' = s, a, = =a), so ~ po: a ~ (5)), 8141 ~ P(st, ar), V 2 0.
In offline MARL, online interaction with the environment is not allowed, and the policy is optimized only using the offline dataset D = {(s, a,r, 87) )'))))) collected by diverse data-collection agents. We denote the dataset distribution as dD and abuse the notation dD for ~ dD, (s, a) ~ dD, and (s, a, s') dD
Nash Policy
We focus on finding the factorizable policy {T; : S - A(A))) E Iy during centralized training, which necessitate the notions of Nash and e-Nash policies.
Definition 2.1 (Nash and c-Nash Policy). A joint policy π r== (- is Nash policy if it holds
Vi Vili .. (ss) 2 ViT. '()), Vi ViEW, ni S
that for each Similarly, a joint policy π²' (m)) is an c-Nash policy if there exists an
cc for all m, s. In other words, π (m² m-,)) is a Nash policy, if each agent i E N has no incentive to deviate from oं to an alternative policy, mi. given that all other agents are playing "",-
agent E N. it holds that v.-im=-(s) (s) 2 Vi v= (s) e,
3 AlberDICE
In this section, we introduce AlberDICE, an offline MARL algorithm that optimizes the stationary distribution of each agent's factorizable policy while effectively avoiding OOD joint actions. Al- berDICE circumvents the exponential complexity of MARL by computing the best response of one agent at time in an alternating manner. In contrast to existing methods that adopt decentralized training of each agent (25) where other agents' policies are assumed to follow the dataset distribution, AlberDICE adopts centralized training of each agent, which takes into account the -tatssationa incurred by the changes in other agents' policies.
Regularized Linear Program (LP) for MMDP The derivation of our algorithm starts by augment- ing the standard linear program for MMDP with an additional KL-regularizztion term, where only a single agent: E N is being optimized while other agents' policies π are fixed:
max Σ a(), d.20
as a a DKL
(s,a,,a.)))
(2)
5,0,,a_.
Edis'a - (1 (s)) + Σ Plsls,a,, (a Vs', (3)
s.t.
a//a'',
where DKL (p(z)]la(z)) : E. p(z) log p()) is the KL-diiergence between probability distributions p and g, and a > is hyperparameter that controls the degree of conservatism, i.c., the amount of
((=)
3

---

penalty for deviating from the data distribution, which is commonly adopted principle in offline
22 42 Satisfying the Bellman- constraints (3) guarantees that d(s, ag a.:) == ds(s, 04 nt
RL
-|s) is a valid stationary distribution in the MMDP.
As show in our theoretical treatment of the regularized LP in Section 4 the selected regularization term defined in terms of joint action space critically ensures that every agent i E .N optimizes the same objective function (2). This ensures that when agents optimize alternately, the objective function always monotonically improves which, in turn, guarantees convergence (see Theorem 4.2) This is in contrast existing methods such as (25), where each agent optimizes the different objective functions. Importantly, this is achieved while ensuring conservatism. As can be seen from 2 the KL-regularization term is defined in terms of the joint stationary distribution of all agents which ensures that the optimization of the regularized LP effectively avoids OOD joint action selection.
The optimal solution of the regularized IPP 3 di corresponds to the stationary distribution for a best response policy n. against the fixed π -- and गद can be obtained by म.- mn; (ato))))
d.(a.)))
The (regularized) LP 2 can also be understood solving a (regularized) reduced MDP M: (S, Ai, P., Fi P.Po) for single agent i EN, where P; and F; are defined as follows
a, Pi(s'|s a.)))s.aa)) = Σ T_. a.;), Fi(s, a.) := Σ [a
Then, de is an optimal stationary distribution on the reduced MDP, M, but the reduced MDP non-stationary due to other agents' policy, π -hi. updates. Therefore, it is important to account for changes in ._ during training order to avoid selection of OOD joint actions.
Lagrangian Formulation The constrained optimization 2 is not directly solvable since we do not have a white-box model for the MMDP. In order make 2 amenable to offline learning in model-free manner, we consider Lagrangian of the constrained optimization problem:
min max E (s.a))avd (r(s, ai a-:) - aa Σ 2y 4.20 a_(xx_((s)
ds
log (5,(, (8800))
d=(s.0.)=-
5,0g 2
Σ (1
- - di((s,aa) + Σ ad(s,
(4)
where (s) the Lagrange multiplier for the Bellman flow constraints Still, is not directly solvable due to its requirement of P(s"|s, (s. ag am;) for (s, a;) ~ d; that are not accessible in the offline setting. To make progress, we re-arrange the terms in (4) as follows
min max (1 so (u + (oaas))d
log (..aa.)) (8.0..
(5)
Mi d:20
+ E ( a;, - a log x ((-()a)) + 7e((8') [x))
8 p(s.a,,)).))
miyy (esoe)
min max (1 - 7) sompp [+(() + E (e.or))dd M d:20
dala) (s,a,)
(er, (s, az) - log (s,a.) )]
(6)
d (s
=:w: (8,00)
min max (1 - Fp (us + E (raaaddd [wi(s, (s,, - a log wi(s, a:))]
2 w.20
where ex, (s) a;) is the advantage by n4, and wy a;) are the stationary distribution correction ratios between di and d Finally, to enable every term in (7) to be estimated from samples in the offline dataset D. we adopt importance sampling, which accounts for the distribution shift in other agents'
policies, π -ー:
min max (1 - Ep (1) (s0))+ ur, 20
+ E sa,aaa ad [ws(s, a:) T_r(م-مl=) " 7_,a__lb.a5) (êv, (s, ui a.,,))),))))) lo (s (o))
(8)
'The reduced MDP also used by 444, where it is termed averaged MDP. 'The use of min., maxa, 20 rather than maxa, min., is justified due to the convexity of the optimization problem in 2 which allows us invoke strong duality and Slater's condition.

---

where Evg (8, dz a,;;)) == r(8, di, a_;) a log k-((--18) (a,aa_(),a)) + (or((8)
- vc()). Every term in (8) can be now evaluated using only the samples in the offline dataset. Consequently, AlberDICE aims
to solve the unconstrained minimax optimization (8) for each agent E N. Once we compute the
optimal solution (4,, w;) of (8), we obtain the information about the optimal policy mं (i.e. the best
d"i (s.as) response policy against the fixed π. in the form of distribution correction ratios w (3.a))))
Pretraining autoregressive data policy To optimize g we should be able to evaluate (a_ils az) for each (s, 0g a-)) E D. To this end, we pretrain the data policy via behavior cloning. where we adopt an MLP-based autoregressive policy architecture, similar to the one in [43] The imput dimension of π only grows linearly with the number of agents. Then, for each E N. we optimize the following:
max (e d)aDD
Σ
log (ag ag aes))
While, in principle, the joint action space grows exponentially with the number of agents, learning a joint data distribution in autoregressive manner is known work quite well in practice 7 29
Practical Algorithm: Minimax Min Still, solving the nested minimax optimization 7 can be
numerically unstable in practice. In this section, we derive practical algorithm that solves a single minimization only using offline samples. For brevity, we denote each sample (s, ag a_;.s') in the
dataset as æ. Also, let Ex (x)] == To ΣxED (x) be a Monte-Carlo estimate of Ex- (f)),.
where D = {xxx) { p. First, we have unbiased estimator of 7
min max(1 7) E [v(()))] + EXED w as)p:())) E2, (x) - a log we (s))
(10)
24 w.20
where (x))) is defined as:
(n- L mslay]s)
p=(x)= = (0.00) =_(aa__0.a)
(11)
Optimizing 10 can suffer from large variance due to the large magnitude of p(z), which contains
products of N 1 policies. To remedy the large variance issue, we adopt Importance Resampling (IR) 32 to 10). Specifically, we sample a mini- batch of size from D with probabiiiyy proportional
to p(z). which constitutes resampled dataset Dp. {(s, as a.,, ) k=1- Then, solve the
following optimization, which now does not involve the importance ratio:
min max(1 7) 2) Dy (80) + ExED, w.:(s, as) (é,, (x) a log mx(ss a:)
(12)
2 2,20
where A EDED (x) It can be proven that 12 is still unbiased estimator of 7 thanks to the bias correction term of أ [32]. The resampling procedure can be understood as follows: for each data sample x (s, 0g a s'), if other agents' policy π selects the action a E D with low probability, i.e., ग (a_; ~ O, the sample x will be removed during the resampling procedure, which makes the samples in the resampled dataset D,, consistent with the reduced MDP M, 's dynamics. Finally, to avoid the numerical instability associated with solving a min-max optimization problem, exploit the properties of the innei-maximization problem in (22.. specifically, its concavity in w,, and derive its closed-form solution.
Proposition 3.1. The closed-form solution for the inner-maximization in 12 for each x is given by
o (x) = exp (d (x) -1)
(13)
By plugging equation 24
13 into 12
we obtain the following minimization problem:
min P.o exp &en (x) 1)] (1 (1-7)1E 200po [M((5))] I(v;).
(14)
As we show in Proposition B.1 in the Appendix, L(v;) is an unconstrained convex optimization problem where the function to learn 17 is dependeepnndnt. Furthermore, the terms in (14) are estimated only using the (s, ag a-;, s') samples in the dataset, making it free from the extrapolation error by bootstrapping OOD action values. Also, since (s)) does not involve joint actions, it is not required to adopt (GM-principle in i; network modeling; thus, there is no need to limit the expressiveness power of the function approximator. In practice, we parameterize vs using simple MI.Ps, which take the state an input and output scalar value.
5

---

Policy Extraction The final remaining step is to extract policy from the estimated distribution
correction ratio (s, as) = d (s.0.) optimizations by alternating between policy evaluation and policy improvement, solving (14) directly results in the optimal vy. However, this does not result in an executable policy. We therefore utilize
d= (s,az) Unlike actor-critic approaches which perform intertwined
the 1-projection policy extraction method from
[4] which we found to be most numerically stable
arg min DKL (dP T,
(a)ls) (amils))
(15)
arg min E Da |- - log (s, (s, + DKL (T (o:1s)))
(16)
In summary, AlberDICE computes the best response policy of agent by: (1) resampling data points based on the other agents' policy ratios p 11h where the data policy n (a-ias,, -s,,,,,, 0s) can be pretrained, (2) solving a minimization problem to find (s) (31 and finally, (3) extracting the policy using the obtained Vf by I-projection (15). In practice, rather than training vi until convergence at each iteration,
we perform a single gradieni update for each agent v, and T. alternatively. We outline the details of
policy extraction (Appendix E.2) and the full learning procedure in Algorithm [A (Appendix
4 Preservation of Common Rewards and Convergence to Nash Policies
In the previous sections, AlberDICE was derived as a practical algorithm in which agents alternately compute the best response DICE while avoiding OOD joint actions. We now prove formally that this procedure converges to Nash policies. While it is known that alternating best response can converge to Nash policies in common reward settings [1, it is not immediately clear whether the same result holds for the regularized LP 3 and hence the regularized reward function of the environment, preserves the common reward structure of the original MMDP. As we show in Lemma this is indeed the case, i.e., the modified reward in 2 B is shared across all agents. This directly implies that optimization of the corresponding LP yields the same value for all agents E N for any joint policy, R, with factorized individual policies, {T.)iEN.
Lemma 4.1. Consider a joint policy = (T:)se,, with factorized individual policies, i.e., π (als)) = (a:)seN. Then, the regularized objective in the LP
ThE (a,(s) for all a) E x A with formulation of AlberDICE, of. equation (2). can be evaluated to
Σ 8,01,8-1
d. 0g (a-;)))) ai, ai;),
('(smmaa))) for all (s,a) E S x A. In particular, for with F(s, ai, a-i) = r(s, ai am)) log (" .y. for any joint policy, LP formulation of AlberDICE attains the same value for all agents i N.
(TT (T)),,,, with factorized invdividual policies, the regularized objective in the
We can now use Lemma 4.1 to show that AlberDICE enjoys desirable convergence guarantees in tabular domains in which the policies, T; can be directly extracted from d, (s, a:) through the d((,.).)
expression क: (as|s) Σa, di(3.0,))
Theorem 4.2. Given an MMDP, G. and a regularization parameter a 2 O. consider the modified MMDP G with rewards 7 as defined in Lemma 4.1 and assume that each agent alternately solves the regularized LP defined in equations 2 3). Then, the sequence of policy updates, (x²") (x"))20, converges
Nash policy, π² (कद )ie) of G.
The proofs of Lemma 4.1 and Theorem 4.2 are given in Appendix D Intuitively, Theorem 4.2 relies
on the fact that the objectives in the alternating optimization problems 3 involve the same rewards for all agents for any value of the regularization parameter, 2 O. cf. Lemma 4.1 Accordingly. every update by any agent improves this common value function, (V= (V=(s)))<E)) (s)) and at some point the sequence of updates is bound to terminate at (local) maximum of V. At this point, no agent can improve by deviating to another policy which implies that the corresponding joint policy a Nash policy of the underlying (modified) MMDP. For practical purposes, it is also relevant to note that the process may terminate at an e-Nash policy (ef. Definition 2.1). since the improvements in the common value function may become arbitrarily small when solving the LPs numerically.

---

A
B
A
B
A
B
A
0.22
0.0
0.0
0.25
0.25
0.25
0.O
0.22
0.11
0.0
1.0
0.0
1.
0.25
0.25
0.25
0.25
0.0
0.0
MADIKD
OptDICE
Table 1: Policy values after convergence for the Matrix Game in Figure
for fAA, AB,,
direct implication from the construction of the AlberDICE algorithm, which is also utilized in the proof of Theorem 4.2 is that the AlberDICE algorithm maintains during its execution and, thus, also returns upon its termination, factorizable policy, i.e., policy that can be factorized.
Corollary 4.3. Let πt be the extracted joint policy that is returned from the AlberDICE algorithm. Then, π² is factorizable, i.e. there exist individual policies, {Tī )EE,, one for each agent, so that T (als) ILEx Th (a,]s) for all E A, S.S.
Experimental Results
We evaluate AlberDICE on series of benchmarks, namely the Penalty XOR Game and Bridge [5] as well as challenging high-dimensional domains such as Multi-Robot Warehouse (RWARE) 27
Google Research Football (GRF) [12 and StarCraft Multi-Agent Challenge (SMAC) 31 Our base- lines include Behavioral Cloning (BC), ICQ [40]. OMAR [25), MADTKD [35] and OptiDICE 14]
For fair comparison, all baseline algorithms use separate network parameters for each agent and the same policy structure, Further details on the dataset are provided in Appendix
5.1 Penalty XOR Game
We first evaluate AlberDICE on x Matrix Game called Penalty XOR shown in Fig-
ure 2 We construct four different datasets: (a) {AB}, (b) {AB, BAJ. (c) {AA, AB, BA].
(d) [A,,AB, BA, BB).
The full results showing the final joint policy values are
shown in Table 6 in the Appendix. We show the results for dataset (c) in Table [
AlberDICE is the only algorithm that converges a deterministic optimal
A
B
policy, BA or AB for all datasets.
On the other hand, OptiDICE and MATDKD converges stochastic policy where both agents choose A and B with equal probability. This expected for both algorithms which optimize over joint actions during centralized training which can still lead to joint action OOD if the joint policy is not factorizable. ICQ converges to AA for (b), (d) and BB for (c), which shows the tendency of the IGM constraint and value factorization approaches to converge to OOD joint actions. These results also suggest that the problem of joint action OOD becomes more severe when the dataset collection policy diverse and/or the environment has multiple global optima requiring higher levels of coordination.
B
2
Figure 2: Penalty XOR
5.2 Bridge
Bridge is a stateful extension of the XOR Game, where two agents must take turns crossing narrow bridge. We introduce harder version (Figure 3 where both agents start "on the bridge" rather than on the diagonal cells of the opponent goal states as the original game. This subtle change makes the task much harder because now there are only two optimal actions: (Left, Left) and (Right, Right) at the initial state. Conversely, the original game can be solved optimally as long as at least one agent goes on the bridge.
Figure 3:
Bridge (Hard)
The optimal dataset (500 trajectories) was constructed by mixture of deterministic optimal policies which randomizes between Agent crossing the bridge first while Agent 2 retreats, and vice-versa. The mix dataset further adds 500 trajectories by uniform random policy.
'OtiDICE can be naively extended to MARL by training single v(s) network and running Weighted BC the policy extraction procedure learn factorized policies, which does not require learning joint state-action value function. Still, has some issues (Appendix C).
Fuu et al. [5] showed that separating policy parameters are necessary for solving challenging coordination tasks such Bridge.
7

---

Table 2: Mean return and standard error (over random seeds) on the Bridge domain.
Dataset
BC
ICQ
OMAR
MADTKD
OptiDICE
AlberDICE
Optimal
-.26
-2.21
0.90
-1.81 = 0.12
-6.01 + 0.00
-4.31 + 0.27
-2.71 = 0.69 -1.27
Mix
-4.56
-5.88 0.49
-6.01 = 0.00
-6.01 + 0.00
-6.38 = 0.26
-1.76 = 0.17
-1.29 0.00
(a) AlberDICE 1) (b) AlberDICE (i
(c) BC
(d) BC
Figure 4: Visualization of learned policies the initial state for (from Left Right) AlberDICE (agent agent 2) and BC (agent 1, agent 2), for the Bridge (Hard) on the optimal datasct. The blue arrows indicate agent 2's policies when agent is at and red arrows indicate agent I's policy when agent 2 is at *.
Table 3: Mean performance and standard error (over random seeds) on the Warehouse domain.
Tiny (lIlll (N 4)
Small (lxx20)
(N
(N
(N 2)
(N 6)
BC
8.80 = 0.25
11.12 0.19
14.06
0.32
5.54
+ 0.06
7.88
0.14
8,90 0.13
ICQ
9.38
+ 0.75
12.13
1 0.44
14.59 0.16
5.43
1 0.19
7,93
1 0.19
8.87 1 0.22
OMAR
6.77 + 0.64
14.39
0.91
16.13 1.431121 121
4.40
1 0.34
7.12 1 0.38
8.41 1 0.49
MADTKD
6.24 0.60
9.90
0.21
13.06
0.11
3.65
0.34
6,80
2 0.36
7.85 0.52
OpdDICE
8.70 = 0.06
11.13 0.11
14.02
4 0.36
1.84
+ 0.32
7.68 = 0.09
8.17 + 0.26
AlbeDICE
0.35
15.72 0.36
Table 4: Mean success rate and standard error (over 5 random seeds) GRF
3vsl
CA-Hard (N = 4)
Comer (N 10)
(N 2)
(V 3)
BC
0.69 0,08
0.44 +: 0.07
0.70
0.07
0.24 1: 0.04
ICQ
0.53 : 0.39
0.00
+ 0.00
0.00 = 0.00
0.00 + 0.00
OMAR
0.00
0.01
0.07 0.06
MADTKD
0.56
1: 0.16
0,56 1 0.05
0.69
1 0.05
0.32 1 0.07
OptiDICE
0.71
0.67
0.26 0.04
AlberDICE
0.75 +: 0.12
0.59 - 0.12
0.83 0.04
0.36 = 0.04
The performance results Table show that AlberDICE can stably perform near-optimally both the optimal and mix datasets. Also, the learned policy visualizations for the optimal dataset in Figure show that AlberDICE the only algorithm which converges to the optimal deterministic policy in the initial state, similar the results in the Matrix game. We also include similar policy visualization results for all states and algorithms in Appendix H
5.3 High- Dimennionl MARL Benchmarks
We further evaluate AlberDICE standard MARL benchmarks including RWARE (2). GRF 12 and SMAC [3I]. For RWARE and GRF, we train an autoregressive policy using Multi-Agent Transformers (MAT) B7) in order to collect diverse trajectories for constructing offline datasets. For SMAC, we use the public dataset provided by Meng et al. [19].
RWARE simulates real-world warehouse in which robots move and deliver requested goods in partially observable environment (each agent can observe the 3 square centered on the agent). RWARE requires high levels of coordination, especially whenever the density of agents is high and there are narrow pathways where only a single agent can pass through (similar to Bridge).
The results in Table show that AlberDICE performs on on-par with OMAR in the Tiny (11 X 11) environment despite OMAR being decentralized training algorithm. As shown in Figure 9(a) of [6), large portion of the Tiny map contains wide passageways where agents can move around relatively freely without worrying about colliding with other agents. On the other hand. AlbErDICE outperforms baselines in the Small (11 x 20) environment (shown in Figure 9(b) of (26)), where precise coordination among agents becomes more critical since there are more narrow pathways and the probability of collision is significantly higher. We also note that the performance gap between AlberDICE and baselines is largest when there are more agents (N 6) in the confined space. This increases the probability of a collision, and thus, requires higher levels of coordination.

---

Table Mean success rate and standard eπror (over random seeds) on SMAC
3452 (Hanf)
5m_ys v._ 6m (Hard)
Corridor (SH)
6hvs8, (SH)
8m, vs. 9m (Hard)
3657 vs. 3sfz (SH)
(N 5)
(N 6)
(N
(N
(N 8)
BC
0.30 0.05
0.23 +
0.90 0.02
0.11 + 0.02
0.18 0.05
0.15 0.03
ICQ
0.18 1 0.08
0.18 1 0.10
0.78 1 0.03
0.00 + 0.00
0.12 0.21
0.31 + 0.04
OMAR
0.43 1: 0.04
0.18 1 0.02
0.92 1 0.02
0.15 0.03
0.45 1: 0.05
0.60 1: 0.05
MADTKD
0.12 0.02
0.19 + 0.02
0.67 0.01
0.09 0.02
0.14 0.04
0.18 0.02
OPtDICE
0.28 + 0.05
0.21 + 0.02
0.91 + 0.02
0.13 - 0.00
0.17 + 0.05
0.12 = 0.04
AlberDIC'
0.03
+:
Data
leb
$m__vx 9m (N 8)
355A_.ys__ 33_3 (N 8)
MAcTi::
MASTIC
AlberdicE Jours
ABArO Toeno
BC
0.1%
0.3%
ICQ
54.7%
26.2%
0C0 Drishoos
0C0 Beeshvte
OMAR
16.5%
5.7%
MADTKD
1.7%
0.8%
0.235
3,155
0%
OPEDICE
0.1%
0.3%
Uncurakity
AlbaDDICE
4.8%
1.6%
(a) Histogram uncertainty estimates (s. : E D, ~ (+)).
(b) Percentage of selecting OOD joint actions.
Figure 5: Experimental results how effectively AlberDICE avoids OOD joint actions.
Our results for GRF and SMAC in Tables 5 show that AlberDICE performs consistently well across all scenarios, and outperforms all baselines especially in the Super Hard maps, Corridor and 6h8z. The strong performance by AlberDICE corroborates the importance of avoiding OOD joint actions order avoid performance degradation.
5.4 Does AlberDICE reduce OOD joint actions?
In order to evaluate how effectively AlberDICE prevents selecting OOD joint actions, we conducted additional experiments on two SMAC domains (8m_ 9m and 3s5z vs 3s6z) as follows. First, trained an uncertainty estimator (s, a) via fitting random prior (2 f S x A x ... x AN + R using the dataset D {(s, } Then, U(s, a) [ a) h(s, a) outputs low values for in-distribution (s, a) samples and outputs high values for dut-of-distributioo (s. a) samples. Figure shows histogram of uncertainty estimates (1 -.. TN (s)) for each D and the joint action selected by each method. We set the threshold for determining OOD samples to 99, 9u--nnitiiee of (U(s, a): (s,a) E D}. Figure(5(b presents the percentage of selecting OOD joint actions by each method. AlberDICE selects OOD joint actions significantly less often than ICQ (IGM-based method) and OMAR (decentralized training method) while outperforming them in terms of success rate (see Table
6 Related Work
DICE for Offfine RL Numerous recent works utilize the LP formulation of RL to derive DICE algorithms for policy evaluation 22) OPtiDICE [14] was introduced as the first policy optimiza- tion algorithm for DICE and as stable offline RL algorithm which does not require value estimation be naively extended to offline MARL in principle, it can still
of OOD actions. While OptiDICE fail to avoid OOD joint actions since its primary focus to optimize over the joint action space the MMDP and does not consider the factorizability of policies. We detail the shortcomings of naive extension of OptiDICE to multi-agent settings in Appendix
Value-Based MARL A popular method in cooperative MARL is (state-action) value decomposition.
This approach can be viewed as way to model Q(x, a) implicitly by aggregating Q: in a specific manner, e.g., sum (34, or weighted sum 30 Thus, it avoids modelling Q(s, a) explicitly over the
joint action space. QTRAN (33] and QPLEX [36] further achieve full representativeness of IGM

---

These approaches have been shown to perform well in high sieh--imessional complex environments including SMAC [3T]. However, the IGM assumption and the value decomposition structure have been shown to perform poorly even in simple coordination tasks such as the XOR game S
Policy-Based MARL Recently, policy gradient methods such as MAPPO 41 have shown strong performance on many complex benchmarks including SMAC and GRF. Fu et al. [5] showed that independent policy gradient with separate parameters can solve the XOR game and the Bridge environment by converging to a deterministic policy for one of the optimal joint actions. However, it requires an autoregressive policy structure (centralized execution) to learn stochastic optimal policy which covers multiple optimal joint actions. These empirical findings are consistent with thcoretical results [15 44] showing that running independent policy gradient can converge to a Nash policy in cooperative MARL. On the downside, policy gradient methods are trained with on-policy samples and thus, cannot be extended to the offline RL settings due to the distribution shift problem [16]
Offline MARL ICQ [40] was the first MARL algorithm applied the offline setting. It proposed an actor-critic approach to overcome the extrapolation error caused by the evaluation of unseen state-action pairs, where the error is shown to grow exponentially with the number of agents. The centralized critic here uses QMIX [30 and thus, it inherits some of the weaknesses associated with value decomposition and IGM. OMAR (25) is decentralized training algorithm where each agent runs single-agent offline RL over the individual Q-functions and treats other agents as part of the environment. As consequence, it lacks theoretical motivation and convergence guaranteess in the underlying MMDP or Dec-POMDP. MADTKD (35) extends Multi-Agent Decision Transformers [19] incorporate credit assignment across agents by distilling the teacher policy learned over the joint action space to each agent (student). This approach can still lead to OOD joint actions since the teacher policy learns a joint policy over the joint action space and the actions are distilled individually
to students.
7 Limitations
AlberDICE relies on Nash policy convergence which is well-established solution concept in Game Theory, especially in the general non-cooperative case where each agent may have conflicting reward functions. One limitation of AlberDICE is that the Nash policy may not necessarily correspond to the global optima in cooperative settings. The outcome of the iterative best response depends the starting point (region of attraction of each Nash policy) and is, thus, generally not guaranteed to find the optimal Nash policy .I This is the notorious equilibrium selection problem which is an open problem in games with multiple equilibria, even if they have common reward structure (See Open Questions in [15).. Nonetheless, Nash policies have been used as a solution concept for iterative update of each agents as a way to ensure convergence to factorized policies in Cooperative MARL [10]. Furthermore, good equílibria tend to have larger regions of attraction and practical performance is typically very good as demonstrated by our extensive experiments.
8 Conclusion
In this paper, we presented AlberDICE, multi-agent RL algorithm which addresses the problem of distribution shift in offline MARL by avoiding both OOD joint actions and the exponential nature of the joint action space. AlberDICE leverages an alternating optimization procedure where each agent computes the best response DICE while fixing the policies of other agents. Furthermore, it introduces a regularization term over the stationary distribution of states and joint actions in the dataset. This regularization term preserves the common reward structure of the environment and together with the alternating optimization procedure, allows convergence to Nash policies. As a result, AlberDICE is able to perform robustly across many offline MARL settings, even in complex environments where agents can easily converge to sub-optimal policies and/or select OOD joint actions. As the first DICE algorithm applied to offline MARL with a principled approach to curbing distribution shift, this work provides a starting point for further applications of DICE in MARL and a promising perspective in addressing the main problems of offline MARL.
Details about IGM are provided in A.I
10

---

Acknowledgments and Disclosure of Funding
This work was partly supported by the ITTP grant funded by MSIT (No.2020-0-00940 Foundations of Safe Reinforcement Learning and Its Applications to Natural Language Processing: No. 00311, Development of Goal-Oriented Reinforcement Learning Techniques for Contact-Rich Robotic Manipulation of Everyday Objects; No.2019 10-2001-0--0075, AI Graduate School Program (KAIST); No.2021-0-02068, Al Innovation Hub), NRF of Korea (NRF200998 A2C1 D2C1087634) Field-oriented Technology Development Project for Customs Administration through NRF of Korea funded by the MSIT and Korea Customs Service PRRF202IM3I1AS 10099938) KAIST-NAVER Hypercreative AI Center, the BAIR Industrial Consortium, and NSF AI4OPT Al Centre.
References
[1] Dimitri Bertsekas. Multiagent value iteration algorithms dynamic programming and reinforcement learning, 2020.
[2] Kamil Ciosek, Vincent Fortuin, Ryota Tomioka, Katja Hofmann, and Richard Turner. Conservative uncertainty estimation by fitting prior networks. In International Conference Learning Representations, 2020.
[3] A. Dafoc, E. Hughes, Bachrach, Collins, R. McKee, Leibo, K. Larson, and Gracpel. Open Problems Cooperative Al. arXiv e-prints, December 2020.
[4] A. Dafoe, Y. Bachrach, G. Hadfield, E. Horvitz, K. Larson, and T. Graepel. Cooperative Al: machines must learn to find common ground. Nature, 7857:33- 36, 2021. doi: 10. 10.103/44118--100 186-1021-0-01111 12211-0110 01170-0.
[5] Wei Fu, Chao Yu, Zelai Xu, Jiaqi Yang, and Yi Wu. Revisiting some common practices in cooperative multi-agent reinforcement learning. In Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 6863 6877. PMLR, 17-23 Jul 2022.
[6] Scott Fujimoto, David Meger, and Doina Precup. Off-po deep reinforcement learning without ex- ploration. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages
PMLR, 09-15 15 Jun 2019.
[7] Michael Janner, Qiyang Li, and Sergey Levine. Ofline reinforcement learning modeling problem. In Advances in Neural Information Processing Syxtems, volume 34, pages 1273-1286. Curran Associates, Inc., 2021.
big sequence
[8] Rahul Kidambi, Aravind Rajeswaran, Praneeth Netrapalli, and Thorsten Joachims. MOReL:: Model-based offline reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[9] Geon-Hyeong Kim, Scokin Sco, Jongmin Lee, Wonscok Jeon, HycongJoo Hwang, Hongscok Yang, and Kee-Eung Kim. DemoDICE: Offline imitation learning with supplementary imperfect demonstrations. In International Conference on Learning Representations, 2022.
[10] Jakub Grudzien Kuba, Ruiqing Chen, Muning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. In International Conference on Learning Representations, 2022.
[11] Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative g-learning for offline reinforcement lcarning. Advances Neural Information Processing Systems, volume 33, pages 1179- 1191. Curran Associates. Inc., 2020.
[12] K. Kurach, A. Raichuk, P. Staáczyk, M. Zajac, O. Bachem, L. Espeholt, C. Riquelme, D. Vincent, M. Michalski, O. Bousquet, and S. Gelly. Google research football: A novel reinforcement learning environment, 2019.
[13] Sascha Lange, Thomas Gabel, and Martin Riedmiller. Batch Reinforcement Learning, pages 45-73. Springer Berlin Heidelberg, Berlin, Heidelberg. 2012.
[14] Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, Kee-Eung Kim. OptiDICE: Offfine policy optimization via stationary distribution correction estimation. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6120-610 6130. PMLR, 18 24 Jul 2021.

---

[15] Stefanos Leonardos. Will Overman, Ioannis Panageas, and Georgios Piliouras. Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games. In International Conference on Learning Representations, 2022.
[16] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems, 2020.
[17] Ryan Lowe, YI WU, Aviv Tamar, Jean Harb, OpenAl Picter Abbeel, and Igor Mordatch. Multi-agent actor- -eterraiiie-ooeeeiiiiiie environments. In I. Guyon, U. Von Luxburg, S. Bengio. H. Wallach,
critic for mixed R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[18] Xueguang Lyu, Yuchen Xiao, Brett Daley, and Christopher Amato, Contrasting centralized and decentral- ized crities in multi-agent reinforcement learning. In Proceedings of the 20th International Conference on Autonomous Agents and MuhtAAgett Systems, AAMAS '21, page 844-852, International Foundation for Autonomous Agents and Multiagent Systems, 2021.
[19] Linghui Meng, Muning Wen, Yaodong Yang. chenyang le, Xi yun Li, Haifeng Zhang, Ying Wen, Weinan Zhang. Jun Wang, and Bo XU. Offline pre-trained multi-agent decision transformer, 2022.
[20] Ofir Nachum and Bo Dai. Reinforcement learning via ronchel-rockafellar duality, 2020.
[21] Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. DuaIDICE: Behavior Behavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[22] Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. AlgaeDICE: Policy gradient from arbitrary experience. arXiv preprint
2019.
[23] Allen Nie, Yannis Flet-Berliac, Deon R. Jordan, William Steenbergen, and Emma Brunskill. Data-efficient pipeline for offline reinforcement learning with limited data, 2023.
[24] Frans A. Oliehock and Christopher Amato. A Concise Introduction to Decentralized POMDPs. Springer Publishing Company, Incorporated, 1st edition, 2016. ISBN 3319289276.
[25] Ling Pan, Longbo Huang, Tengyu Ma, and Huazhe Xu. Plan better amid conservatism: Offline multi-agent reinforcement learning with actor rectification. In Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 17221-17237 PMLR, 17-23 Jul 2022.
[26] Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V Albrecht. Benchmarking multi- agent deep reinforcement learning algorithms in cooperative tasks. In Thirty-fithh Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021.
(27] Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V. Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks. In Proceedings of the Neural Information Processing Systems Track Datasets and Benchmarks (NeurIPS), 2021.
[28] Bei Peng, Tabish Rashid, Christian Schroeder de Witt, Pierre-Alexandre Kamienny, Philip Torr. Wendelin Boehmer, and Shimon Whiteson. FACMAC: Factored multi-agent centralised policy gradients. In A. Beygelzimer, Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[29] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. Improving language understanding by generative pre-training. 2018.
[30] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 4295-4304. PMLR, 10-15 Jul 2018.
[31] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim G. Rudner, Chia-Man Hung, Philip H. S. Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge, 2019.
[32] Matthew Schlegel, Wesley Chung, Daniel Graves, Jian Qian, and Martha White. Importance resampling for off policy prediction. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
12

---

[33] Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. QTRAN: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In Proceedings the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learning Research, pages 3887-5896, PMLR, 09-15 Jun 2019.
[34] Peter Sunehag, Guy Lever, Audrunas Gruslys. Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z Leibo, Karl Tuyls, et al. value-decompooition networks for cooperative multi-agent learning. arXiv preprint
70te::776699999 2017.
[35] Wei- ChiiChhng Tseng, Suun-Hsuan Wang, Yen-Chen Lin, and Phillip Isola. Offiie multi-agent reinforcement learning with knowledge distillation. In Advances in Neural Information Processing Systems, 2022.
[36] Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. QPLEX: Duplex dueling multi- agent q-lcarning. In International Conference on Learning Representations, 2021.
[37] Muning Wen, Jakub Grudzien Kuba, Runji Lin, Weinan Zhang, Ying Wen, Jun Wang, and Yaodong Yang. Multi-agent reinforcement learning is a sequence modeling problem. In Advances in Neural Information Processing Systems, 2022.
[38] C. S. D. Witt, Tarun Gupta, Denys Makoviichuk, Viktor Makoviychuk, Philip H. S. Torr, Mingfei Sun, and Shimon Whiteson. Is independent learning all you need in the starcraft multi agent challenge? ArXiv, abs/201 I. 1.09533, 2020.
[39] Erfu Yang and Dongbing Gu. Multiagent reinforcement learning for multi-robot systems: A survey. 06 2004.
[40] Yiqin Yang, Xiaoteng Ma. Chenghao Li, Zewu Zheng. Qiyuan Zhang, Gao Huang. Jun Yang, and Qianchuan Zhao. Believe what you see: Implicit constraint approach for offline multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pages 10299-10312. Curran Associates, Inc., 2021.
[41] Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of PPO in cooperative multi-agent games. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
[42] Tianhe Yu, Garrett Thomas, Lantao Yu, Stefamo Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. MOPO: Model-based offline policy optimization. In Advances in Neural Information Processing Systems (NeurlPS), 2020.
[43] Michael R Zhang, Thomas Paine, Ofrr Nachum, Cosmin Paduraru, George Tucker, ziyu wang, and Mohammad Norouzi. Autoregressive dynamics models for offline policy evaluation and optimization. In International Conference on Learning Representations. 2021.
[44] Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in stochastic games: stationary points, convergence, and sample complexity, 2021.
13

---

A Individual-Global-Max (IGM) and its Limitations
Centralized Training with Decentralized Execution (CTDE) refers to paradigm in MARL where the training phase is permitted to utilize any global information such as the joint policy и = (T...... WN) and global state Practical CTDE algorithms avoid the combinatorial nature of the joint action space, and reduce the non-stationarity, which arises from agents' simultaneous policy updates during training.
However, an important challenge for CTDE algorithms is that during training they still need to learn joint policy that can be factorized into individual policies. During the execution phase, agents take individual actions, without conditioning on other agents" actions, a-;, or policies, T- This independence assumption poses a challenge for many pre-existing algorithms, especially for offline MARL when the dataset is generated by mixture of different data collection policies and/or the environment contains multiple global optima.
One popular way to learn factorizable policies from centralized training is to impose an Individual- Global-Max (IGM) assumption.
Definition A.1 Individual-Global-e (IGM) (3 33).. Individual utility functions {Q:) satisfies the IGM condition for a joint state-action value function Q: S x A the following condition holds:
arg max Q(s, a) = {arg max Qi(s, a,)
(17)
Intuitively, the IGM condition implies that the optimal Q-function Q" for given task environment can be decomposed into individual utility functions which only condition on the individual actions u, space of MARL tasks where decentralized policies (i.e. greedy policies over Qi) can be learned to collectively act optimally. The decomposed utility functions Qi can then be used for greedy action selection by individual agents [36].
This assumption results
It is easy to see that under the IGM assumption in Definition A. we cannot learn a set of individual utility functions {Q:} which can accurately represent the optimal Q-functions of many tasks with multiple global optima, including the XOR game. In fact, [5] showed formally that any algorithm under the IGM constraint cannot represent the underlying optimal Q-function in the XOR game.
14

---

B Proofs for AlberDICE
B.1 Proof of Proposition 3.1
Proposition 3.1. The closed-form solution for the inner-maxiiiiattion in (2) for each x is given by
iy (x) = eexp @v (x) -
(13)
Proof. Let
Mu,, wi) == D,, [rr(s, a:) (êv, (s, as, a-,,') - a log ws (s, (s(( + (1 - 7) Bu (s)()))
Note that L(vs, w;) is differentiable and strictly convex for w/. Therefore, we only need to find point where the gradient becomes zero. For any Dp.
(L ws) = Eng (8, ai a i, 86) - a log uy (3) - = 0
(18)
(w;(())
(x) = exp @1 (s, as a., -1)
(19)
B.2
Convexity of L(v;)
Proposition B.1. Let Livi) be a function, defined as:
I(v:): PraEuED, exp (s, az a', ('))))))))) -1)] ao (4((5))
(20)
Then, L (v:) is corvex with respect to
Proof. For any functions vs is and constant À E [0, 1]. we can derive the following equality:
((vc+(1-)11) (8, 0i, a-;
=r(s,a,,_;) a log n (a_
ι ia (1s)
(Av + (1- (1-A))14 (s) + (Apr + (1 (1-)) (5)
-r(s,a;,a - a log (a_
+ 7Av;(s') - (x)(s) + + - A)2((8)) - -A)x((s)
_. .18,a))
=Ar(s, 0i a.:) Aa log π _. ,|s,a;)
+ 7Av((s)) - -Av(ss)
(1 +1- ai a.)) (1 a)a log オ (a.1,aa)
7(1 A)m((s)) (1 A))((s))
-den (8, ais a 8') (1 X) e) / (8, ais a
Thus, ex, is the linear function with respect to us Furthermore, using the convexity of exp(-),
(a- (a_
(e(xe) (s, as a a.,, s')]
exp
(a :|ا) 7 (l3)
exp (Néys (8, as a 80) (1 2) 02 م,,
S (AB(s.a.a-.o
((=s)) v1s)
exp (êv, (8, ai
+ (1 -))E (), aa
عام [
exp (éyg a
Therefore, L (v:) is convex function with respect to
We also show that our practical algorithm minimizes the upper bound of the original optimization problem in equation (7) restated here:
L(v,, w;) = (1 - E (M(())) + Beaasaa [ur(s, (e), (s, a:) a log (s, (21)
15

---

Corollary B.2. L(v)) is an upper bound of L (v4, wi), where w arg max L(v,, wi), i.e. L [V,, ([) S L(vi) always holds, where equality holds when the MDP transition and other agents' policy π -i are deterministic.
Proof. We first note that the closed-form solution for arg max Lis, wx) is as follows:
/ (s, a:) exp (a cv os) 1).
(22)
By plugging this into equation 7 we obtain
min o B (s,a))a Texp ( (s, ai) 11] + - -11- mo) =: L L(w7, us)
From Jensen's inequality, we get
L (ws, v;) = alE (maa)ad
exp (s, -1) + - (1- sp [1)(5
alE (e.s)vi)
exp
LE a- s'mP(s,a;.a.)
(B (8. aie a 8')] - 1)] + (1 - (1-7)BBg upo (+6)]
(ييي-ااي (a..)))))
d 04, a,, 1)] (1 - 7) pp (5)
Sal mod
exp
L(4)
(23)
Also, the inequality becomes tight when the transition model and the opponent policies are determin- istic, since exp L a-p--- [é (s, a, a,;,,,),)))
E PI
eep ( (8, ai a-;;
x' P(sass s) should always hold for the deterministic transition P and opponent policies --
16

---

C Problems with Naive Extension of OptiDICE to Offline MARL
OptiDICE [4]
is a (single-agent) offline policy optimization algorithm which is derived from the regularized Linear Programming (LP) formulation for RL. For given MDP A, R, 7), the derivation of OptiDICE starts with the regularized dual of the LP:
max Σ
d(s,a)r(ss, (xI(dlld))
(24)
Σ
+7 Σ aa)
(25)
Here, d(s, a) should be a stationary distribution of some policy ι by the Bellman flow constraints 25 (d (s == (1-1) Ei= Y Pr(s, 8, 0g a: r)). and dd is the dataset distribution. The goal is to maximize the rewards while not deviating too much from the data distribution, following the conservatism principle in offline RI.. Without the regularization term (rl.(d)ldP) the optimal
solution of (4 25 is the stationary distribution for the optimal policy, d' = d=
One of the main contributions of OptiDICE a tractable re-formulation of the dual LP problem above into single convex optimization problem.
min(1 1 B) [s) + E (s)) [w) ()e, a) - aw, a) log (s)
(26)
where (s) exp (1 (r(ss (Es) -ss))ssss))(ss)))) 1).
(27)
Here, v(s) E R is the Lagrangian multiplier for the Bellman flow constraint (25). and it approaches the optimal state value function V*(s) as a - O. Once we obtain the optimal solution of (26). v*, it was shown that the stationary distribution corrections of the optimal policy is given by wy.:
d' (s. (s)
w (s, exp - -
+
1)
(28)
However, its extension to MARI. can cause number of subtle issues. While solving (26) does not suffer from the curse of dimensionality posed in MARL since v(s) is state-dependent function, V* itself is not an executable policy. We therefore should extract policy from it. However, once try to learn a parametric function for w(s, a), we encounter a combinatorial space of joint actions. We thus should avoid learning any state-action dependent functions for policy extraction. One feasible way to do so to perform policy extraction via Weighted Behavior-cloning (WBC):
Vi, max E (s,a,a wal)oa - (s, aj a_ s') log n, (a,ls) xo E(s.a. [log ग. (a,]s)] (29) Hi s.t. wt a, a. as, s') exp ( (r(s, O, i) + (s' 1² (s)) 1).
(30)
which corresponds to behavior-cloning of the factorized policy on the state-action visits by the optimal (joint) policy. However, if the optimal joint policy (by v²) is multi-modal distribution, this WBC policy extraction step can result in arbitrarily bad policy, selecting OOD joint actions. For example, consider the XOR matrix game in Figure [ with a dataset D {(A, A), (A, B), (B, A)), where the
optimal joint policy is given by ' (a) A, B) x" T"(a1 = A, B) 2. In this situation, WBC of OptiDICE
29 obtains the factorized policies of (a1 = A)
(a1 B) and
T2(a2- A) (2
B)
1.
2. which can select suboptimal (and OOD) joint actions:
π (a: A, 02 A) T (ai A)mz( = A)
π (0: = A, B) Ti (a1 A)Tz( (a2 = B)
(a: B, 02 A) T (al B) A)
π Taa 02 B) nΙ (a: B) B) 1
This analysis is consistent with our experimental results in Section which demonstrated the failure of OptiDICE in solving the Penalty XOR Game as well as Bridge by converging to sub-optimal OOD) joint actions.
17

---

D Proofs for Section
To prove Theorem 4.2
first need to show that the regularized objective in the LP formulation of AlberDICE, cf. equation preserves the common reward structure of G.
(Tz) with factorized individual policies, i.e., T(als) Nix (a)(ss) for all ().a) E S x A with a = (at)ieN. Then, the regularized objective in the L.P formulation of AlberDICE, cf. equation (2). can be evaluated
Lemma 4.1. Consider a joint policy
Σ di a. (a
(l for all (s, a) E S x A. In particular, for with f(ss (,,a,)) == r(5, a_:) a.;) a log P(.aaa.a-13"
any joint policy, = (T)EN with factorized invdividual policies, the regularized objective in the LP formulation of AlberDICE attains the same value for all agent N.
Proof. Recall that the KL-divergence, DKL (p(x)) between probability distributions p and q is defined as DKL (p(x)]l((x)) = p(x) log piz). Thus, the DKL term in the objective of
a(x).
equation can be written as
DKL. (dā (() (8, (8,0;, a-))
Σ d( log d d'(s.a,a_))
Since the T/S are factorized by assumption, the decomposition di (s,a;) = d= (s)m:(a;(()) implies that the numerator in the log-term of the previous expression can be written as
dī a,) JT_ ia (a_//s) d' (s) (a, (a d' (s) Substituting back in the initial expression of the objective function, obtain that
Σ 8,0;
a.)) a DKL (df (s, (a a; a.))
Σ 8_0;8_,,
Σ 8,a,88.;
(s,a))) log d' (dix(aa))) (s....)))
Σ (a
r(s,, ui, a.i) a log 2 (s,a.a=.)
(s)m(aa))
8,0,Ami
Thus, by setting F(s, a, a-)) r(s, a; a log (s.a,, for all (s,a) E S x A, obtain the claim. The equality the last expression for all i E N follows now immediately from application of the decomposition di all agent i N.
d (s)s((a))))
d (s)s(a)s), on the outer expectation for
Remark D.I. In the LP formulation of AlberDICE, ef. equation 2 and (3). used the notation ds(s, a;) rather than di (s, ai), since, in this case, the variables are di(s, ai) are decision variables that are not a-priori related any particular policy me However, once the di(s, az)'s fixed and d,(s,a,)
translated to policy, e.g., through the relation Tz(a, s) = E., di(s,az)
that holds in tabular domains,
then, we can apply Lemma 4.1 For the purposes of the alternating optimization procedure of the AlberDICE algorithm, Lemma 4.J ensures that after each update by any agent i N, the value of the objective function is the same for each agent. To evaluate the modified utilities, f(s, 0g a.;), during training, agents need to know both the action, a;, and the policy, ,; s), from whichi this action drawn for each agent E N. Thus, this regularization terms exploits to the fullest the knowledge available to agents in the centralized training setting.
To proceed, we can define a modified game, : = (N, A.F.F, which is the same as the original game in every respect, i.e., it has the same state space, agents, actions, transitions and discount factor, except for the rewards, r, which are replaced by the modified rewards r for any given value of the regularization parameter, > 0 (for
0, we simply have the rewards, r, of the original game, G). Despite this modification, Lemma 4.1 implies that G still has common reward structure. This can be used to prove that the AlberDICE a aggoritmm has monotonic updates which eventually converge to a Nash equilibrium of the modified game, G. For this part, we focus on tabular domains, in which the d:(s.a.)
policies, (;(a; s), can be directly extracted from d, (s, a;) as T. (T(a; s) Σn, d.(e,a,)
18

---

Theorem 4.2. Given an MMDP, G, and a regularization parameter 2 O, consider the modified MMDP G with rewards i as defined in Lemma 4.1 and assume that each agent alternately solves the regularized LP defined in equations 2 34. Then, the sequence of policy updates, (x* (22)) converges to Nash policy, π )EE) ofG
Proof of Theorem 4.2 Let T"
(TN denote the initial joint policy and let x' (m) denote the joint policy after iteration t E N in an execution of the AlberDICE algorithm. For will also write xi. to denote the joint policy at time after players 1 to i have updated their policies, i.e., पं ( Th T:t1:.... ") Let d; a.) == d. d. (8, a.) denote the stationary distribution for agent before the current optimization by player i. and let
i = ,,,,,,, N,
di (8, (2) := d (s, a:), ( |) denote the stationary policy derived as the optimal solution of the LP and the corresponding extracted policy for agent i, respectively, after the optimization by agent i at time t. Then,
T. (8)
E 8.0.ia
((),a:))-i(a) 8) az a.;)
Σ
diss,a:)
8) a.))
V. (s))
for each state E S, where we used Lemma for the equality the modified rewards among all agents in N. The inequality is strict unless agent i is already using an optimal policy, Te against T- Letting V to denote the common value function, i.e., V-2 V for all agents E N, then, the previous inequality implies that after the update of agent all agents have a higher value with the current policy .ं Thus, the sequence, n², of joint policies generated by the AlberDICE algorithm results in monotonic updates (increases) in the joint modified value function V(s), E S. Since, V is bounded (rewards bounded and discounted by assumption), this implies that also V is bounded and hence, at some point, the updates of the algorithm will reach a local maximum of V. Let x= (x,², x= denote the extracted policy that point. Then, for all agents i N and any mi.
holds that V.T (s) V claimed.
V (x.."" 2) for all S. Thus, nt Nash policy as Li
An important property of the AlberDICE algorithm is that it maintains a sequence of factorizable joint policies, x² = ( for any / 0. Thus, after termination of the algorithm, the agents are guaranteed not only to reach an optimal state of the value function, but also an extracted joint policy that will be factorizable. This eliminates the problem of learning correlated policies during centralized training, which even if optimal, may not be useful during decentralized execution. This property of the AlberDICE is formally stated of Corollary 4.3 Its proof is immediate by the construction of the algorithm.
19

---

First, note that for any constant C, the advantage for E Detailed Description of Practical Algorithm
E.1 Numerically Stable Optimization
The practical issue in optimizing (14) is that it is unstable due to its inclusion of exp(-), often causing exploding gradient problems:
L(v;) min p. 244
exp (e (s, a, a.;; -0 1)] + (1 - -)) [=)))))
where év (8, ais am;, 5') r8, ai, ami) a log [_((a_cla) (m,aa_ :ls,a;3
+ -u(('') ve(s). To address this
issue, we use the following alternative, which can be optimized stably.
[(i:)= == min or log Ez exp ( (s, as |ل, + (1 - Bso [Pc(s0)] (31)
D.
Note that the gradient v log (exp(((axr is given by E, exp(M((e))
E. (exp(h(r"))) V=h(rr) which normal-
izes the value of ex)()(z)) and thus it is numerically stable by preventing the exploding gradient issue. At first glance, it seems that optimizing (31) can result solution of (14). However, as we will show in the followings, their optimal objective function values are the same and their optimal solutions only differ in a constant shift.
completely different solution the
Proposition E.1. Let V = arg min L(vi) and V = arg ming, [(D)) be the sets of optimal solutions of 14 and (37). Then, L(v]) = [(b)) holds for any us V and iz V Also, for any of V and any C E RR vf + E*.
We follow the proof steps in DemoDICE + C is:
( a-, r(s, 0i; a) log x-1la_11s) (1.00))) (1)((' + (v:(8) CC)
ên (s, 0z a;, (1 7)
(32)
Lemma E.2. For arbitrary function vi and any constant C, the following equality holds, ī(v)) Σ(v, + C).
Proof. From the definition of Σ(v;).
Ž(4 + C)
(1 -o0 (80) CJ log P. Eu-D,, exp a
= (1 - B) M4 (8u) + C| + a log p. E.. Dp. exp (d (s,
D..
(1- -]]] (by (3))
(1 B)0 in (8o) C| a log
exp [1 -))) P. eep (s, 2
= (1 - 7) (50) + CJ - (1 - 7)0 + a log P. Do: exp (s, as,
(1 7)0 in (80)) log p EuwDpy eexp (s, a.,
[(v))
Lemma E.3. For any function vi, the following inequality always holds: I(vi)) 2 Z(ve).
Equality holds if and only if
py EnnDo [exp ( (8, ais a o0)]] =
20

---

Proof. For any 2 0
y - 2 log y and equality holds if and only if y Thus,
D Texp ( Eug (s, ac, a
2 log B.nDD exp (1 (s,
and equality holds if and only if
exp (o (n (s,,,
Dec
Finally, we obtain the following results:
[(v) (1 7) ko po Dy (su) + P.EE D,
_ (s, aj a.. - 1)]
exp
2 (1 - --7) E ~po (2 + log
Pr PrEEEDD
exp (8, a.,;; - b)}} +
2 (1 -- E B0 (1 + log
P. E.ED,
exp (s, -1) exp(1))
(1 >) B Bo ta
p; p.BrrDD,
exp (s, (s.0))))))))))
=: ((v.)
Lemma E.4. For any optimal solution 87 = arg ming, [(vi), there is a constant C such that 17, + an optimal solution of miny, L(v:).
Proof. Let D be an optimal solution of arg min,, Σ(v)) and exp [L (8, ai, a.)))
C
log p. Ben
Then, i4 = 17 + C satisfies
i. BrNDD
1 éú (8, (s,
exp
D.BrnDDy pM
exp
p.E.nDDy
(s,
exp
p.B.nDp
( (s, (s, exp (-
exp
1.
Furthermore, 0; is also an optimal solution of min,, Σ(vi) by Lemma E.2 condition in Lemma E.
Then, by the equality
M. = 2(0,) = m [(v,) S min I(x)).
Thus, Di is an optimal solution of min,, L(vs).
Lemma E.5. An optimal solution v," arg min,, L (v:) is also optimal solution of min,, [(v)
Proof. From Lemma
min L (v:)= L (v²) > 2 (vZ).
From Lemma E.4 minu, L (vs) and minu; L (v:) have the same minimum value, and thus,
[v4)) $ L (v²) = min L (vr) = min (v.)
25
holds.
21

---

The aforementioned Proposition E.1 can now be proved.
Proposition E.1. Let V arg min,, L(4)) and V arg ming, ((%) be the sets of optimal solutions of (4 and 3... Then, L(v))= = [(tt) holds for any vs E V and i/; E V Also. for any og EV and any C C R. ug CEV.
Proof. This holds from combining Lemma E.4 and Lemma E.5
E.2 Policy Extraction
Finally, our practical AlberDICE optimizes (31 that yields 8 However, Dy itself is not a directly executable policy, so we should extract policy from it. To this end, first note that the optimal policy ne is encoded in w. form of stationary distribution correction ratios:
d as) (optimal solution of Eq. 8
w (s. a) (s, a.)
(33)
Then, (s, a) can be represented in terms of is as follows:
( a) = exp e (s, (s) 1)
(Eq. 22
(34)
exp ( (s.
(by Proposition E.1
(35)
where Ep; (s, as) = E -_) [&vg (s, aj a. s')] and ég (s, a, s') = r(s, a, a.;)
5 P(maasa)
log x 16)) -. (s.a) (5, (s). Finally, we extract policy from w/ via I-projection policy
extraction method introduced in equation
min DKL (d (d2))))(olls)=
(a,ss) ((a,1s))
(36)
log d (0))m (P)))) s) .aa 18))
(37)
= -ENDDaN log d (s) + log sdalls) + log di (P(c))))
(38)
(s))
(()
constant for
-ESEDaIT
(r.a)) + DKL (Ta(as))) | (m + +1 log d' (s.a)
(39)
=BNEDaa
log u/ (s) + DKL (m](())))) |=] (a:ls)) + +c
(40)
=ESeDaarmn
a e a:) + DKL ( (a.[s)]]]] (a.s)) + C1 + C2 (by 355
(41)
where C1 and C2 denote some constants. by maximizing the log-likelihood:
T. (a:ls) is data policy for i-th agent, which is pretrained
max E (S.))DD [log -.P
(ong:(((a)) (a:1s)]
(42)
Eq. 11 can be understood as KL-regularized policy optimization, where we aim to maximize ep- (8 0;) (analogous to critic value) while not deviating too much from the data policy, whose trade-off is controlled by the hyperparameter a. Finally, to enable ep: to be evaluated at every action a; we train an additional parametric function e (implemented as an MLP that takes (s, a;) as input and outputs scalar value) by minimizing the mean squared error with conservative regularization term R(e;) introduced in CQL | to penalize OOD action values:
min É a D.D (eu(()aa)) - ésy (s, a s') + Requ(e;)
(43)
where (e.) == acqu E B,,DD, Eo, exp (e)(),)))) Barwa [s,()))))]]- We used acgr. 0.1 for all experiments.
22

---

E.3 Pseudocode of AlberDICE
To sum up, AlberDICE computes the best response of agent by optimizing Vt, which corresponds to obtaining a stationary distribution correction ratios of the optimal policy. Then, we extract a policy by training e-network and performing I-projection as described in Section E.
We assume nP. π. T Vi, Gi and के are parameterized by Bi. B_ 0s. thi, and di, respectively T0 Then, optimize the parameters via stochastic gradient descent (SGD). The entire loss functions to optimize the parameters are summarized in the following:
J(8.) == (e.D))D loog Tp. (a:1s)]
(44)
J(B.)) È (e E) ;)DD
Σ
N
log 1 ag (cs)))
(45)
J(0,) log pi
E EENDD,
exp
(2emm (s, ais ".; + (1
Esp (oo (so))
(46)
J(W) E (s.ann a: )
(ew (s) Eoe, (0, u2 a 11))
(47)
(10g E exp (e (s, Barrg acou ErED
B le (s, a+))
Ri
J(o:) = ESED Σ no. (ais))) (ar as) + a log 7. ((,()))))
ne, (ailo)
(48)
ac
The pseudocode of AlberDICE is presented Algorithm T
Algorithm AlberDICE
Input: A dataset D == {(s, r, s') a set of initial states Do == { data policy
networks {T,,; T )) with parameters {(S,, B-:) v-networks {uo, ) with param-
IN
eters [0.),= e-networks (ew with parameters {1i) policy networks { J with parameters { and a learning rate
1: Pretrain (auto-regressive) data policies
T (a a.))) by minimizing 44
45).
2: for each iteration until convergence do
3: for each agent i A do
4: Sample mini-batches from 8p ~ Do and x ~ D.
Compute the importance ratio p: (x) = I ma, (ayls)
5:
"े (a :1s,0;) for each sample x. (Eq. (11)
6: Perform resampling with probability proportional to (z which constitutes the resampled
dataset Dp.-
7:
Perform SGD updates using Do and DpL:
0 + 0, J(O.)) (Eq. 46
Φ t w. V/ v. (1b.)
(Eq.
Φ + Φ: J(bi)
(Eq. 48
8: end for
9: end for
Output: Factorized policies {TT (a.ls))
NTo increase scalability, we use shared parameters and an additional agent ID input train 3, for of in all experiments.
23

---

Dataset Details
F1
Bridge
The optimal dataset (500 trajectories) was constructed by hand-crafted (multi-modal) optimal policy which randomizes between Agent 1 crossing the bridge first while Agent retreats, and vice-versa. The mix dataset is a mixture between 500 trajectories from the optimal dataset and 500 trajectories generated by uniform random policy.
F.2 Multi-Robot Warehouse (RWARE)
For the data collection policy used to construct the dataset, we train Multi-Agent Transformers (MAT) [37] which takes an autoregressive policy structure and thus is able generate diverse behavior. We further train MAT over random seeds, and generate expert dataset with mixture of diverse behaviors.
F.3
Google Research Football
Similar to the dataset collection procedure in RWARE, we use MAT to generate a medium-expert dataset in order ensure that agents score goals in different ways. Similar Bridge, construct a dataset of 2000 trajectories where 1000 trajectories have medium performance (roughly 60%
performance of the expert policies) and another 1000 from fully trained "expert" MAT policies.
E.4 SMAC
We use the public dataset provided by
24

---

G Matrix Game Results
In Table we show results for the converged policies the Matrix Game presented in Section of the main text and shown again in Figure
B 2
B
Figure 6: XOR Game with Penalty
As expected, all algorithms converge to the optimal action AB for the dataset D(a)- However, AlberDICE the only algorithm which can choose the optimal action deterministically for all datasets, showing robustness even when the environment has multiple global optima and the dataset generated by mixture of diverse policies. Here we can consider any dataset containing both AB and BA as a mixture of diverse data collection policies where the two agents cooperate to select the optimal actions but different ways. For OMAR, we see that it is able to learn the optimal policy for D(D)- However, as discussed in the Introduction of the main text, OMAR degenerates to the sub-optimal action BB for dataset ((e) because each agent acts independently and assumes the other agent chooses the individual action A with a probability. Finally, we also note that BC can fail and converge to OOD joint actions even in (()) where the dataset optimal.
B
A
A
B
B
A
0.00
1.00
0.25
0.24
0.45
0.22
0.25
0.26
BC
0.00
0.00
0.26
0.25
0.22
0.11
0.24
0.25
((a)
((6)
((e)
D(a)
A
B
A
B
A
B
A
B
0.00
1.00
1.00
0.00
0.00
0.00
1.00
0.00
ICQ
0.00
0.00
0.00
0.00
0.00
1.00
0.00
0.00
((a))
D(6)
D(e)
D(d)
B
A
A
A
B
A 0.00
1.00
0.00
0.00
0.00
0.00
1.00
0.00
OMAR
0.00
0.00
1.00
0.00
0.00
1.00
0.00
0.00
D(a)
(())
((e)
D(a)
B
A
B
A
B
A
B
0.00
1.00
0.25
0.24
0.25
0.25
0.25
0.26
MADTKD
B
0.00
0.00
0.26
0.25
0.25
0.25
0.24
0.25
((a)
D
((e)
D(u)
B
A
A
B
B
A
0.00
1.00
0.25
0.24
0.25
0..5
0.25
0.26
OptiDICE
0.00
0.00
0.26
0.25
0.25
0.25
0.24
0.25
((a)
(())
((e)
D(a)
A
B
A
B
A
B
A
B
0.00
1.00
0.00
0.00
0.00
1.00
0.00
1.00
AlberDICE
0.00
0.00
1.00
0.00
0.00
0.00
0.00
0.00
((a))
D
D (c)
D(d)
Table 6: Policy values after convergence for the Matrix Game Figure
The policy values are caleu-
lated by multiplying the individual policy values for each agent i.e. π
na T2. The datasets consist
of (() (AB), D(o) {AB, BA), D(o) = {A4, AB, BA), D(a)
(AA, AB, BA, BB).
25

---

H Bridge Policy Visualizations
The visualizations for learned policies AlberDICE, OptiDICE, ICQ, OMAR, BC, and MADTKD are shown for all state possibilities. From Figure 7 it is clear that AlberDICE is the only algorithm which reliably chooses deterministic action (Left, Left) the initial state. However, since the visualizations are provided for the optimal dataset which has a small coverage of states, the policy values may still be sub-optimal at OOD states, The results agents are acting independently without regard for the other agents, and converges to (Left, Right) at the initial state which results in a collision. Finally, we note that the visualizations for MADTKD may not exactly correspond to the policy values used in the experimental results in Section 5 This is because MADTKD uses history-dependent Transformer policy and it is not clear how to visualize the policy values depending the history. The visualizations shown in Figure II assume that each agent is at the given state in the initial timestep, which is different from encountering that state after many timesteps. Nonetheless, the results for the true initial state shown in the central portions of the figure are consistent with the quantitative results in Section
OMAR in Figure [0 shows that
Figure 7: Policy Visualizations for AlberDICE the Bridge (Hard) environment for the optimal dataset where arrows show probability of choosing a particular action given that the other agents are and for agents and 2, respectively.
26

---

Figure 8: Policy Visualizations for OptiDICE on the Bridge (Hard) environment for the optimal dataset where the arrows show the probability of choosing particular action given that the other agents are in and for agents and respectively.
Figure 9: Policy Visualizations for ICQ on the Bridge (Hard) environment for the optimal dataset where the arrows show the probability of choosing particular action given that the other agents are in and for agents and 2, respectively.
27

---

Figure 10: Policy Visualizations for OMAR on the Bridge (Hard) environment for the optimal dataset where the arrows show the probability of choosing particular action given that the other agents are in and for agents and 2, respectively.
Figure 11: Policy Visualizations for MADTKD on the Bridge (Hard) environment for the optimal dataset where the arrows show the probability of choosing a particular action given that the other agents are in and for agents and 2, respectively.
28

---

Figure 12:
Policy Visualizations for BC on the Bridge (Hard) environment for the optimal dataset where the arrows show the probability of choosing particular action given that the other agents are in and for agents and 2, respectively.
29

---

I Additional Ablation Results
Here we show ablation results for hyperparameter a which controls the degree conservatism. 7 that AlberDICE is not too sensitive the hyperparameter as long as it is within reasonable range.
0.001
0.01
0.1
10
100
1000
CA-Hard (GRF)
0.00 # 0.00
0.08 = 0.11
0.82 = 0.03
0 0.06
0.78 = 0.09
0.78
0.79 = 0.11
(N
Corridor (SMAC)
0.00 0.00
0.00 = 0.00
0.92 = 0.02
0.97 0.01
0.95 0.03
0.92 + 0.03
0.91 = 0.04
(N = 8)
Table Ablation Study for Conservatism Hyperparameter a (over 3 random seeds)
J Implementation Details
J.1 AlberDICE for Dec-POMDP
While our paper focuses on MMDPs, our experimental results show that we can extend AlberDICE to Dec-POMDDPs G = (N, S, A,r, P. 7, S2, O) by using partial observations and a history-dependent policy in place of a state-dependent policy for each agent. In Dec-POMDP, each agent observes individual observations o; S which is given by the observation function O S x A - S2. Each agent makes decision based on the observation-action history Ti E (52 x A) x Ω2 where each agent's 's (decentralized) policy is represented as (a:/TT)).
For the Matrix Game, Bridge and GRF, we used an MLP policy since the partial observations for each agent correspond with the global state (i.e., each individual policy is conditioned only on its current observation o₁ rather than the entire history). For Warehouse, each individual policy uses the partial observations as input, which is the 3x3 neighborhood surrounding each agent. We utilize Transformer-bane based policy in order for the agent to condition on the history of local observations and actions, while speeding up training in comparison to Recurrent Neural Networks (RNNs). This same Transformer-bast policy is used for all baselines as well.
During centralized training, AlberDICE uses the global state for training T. (a-ils, a:), 19, (s), and esj, (s, a) for all environments, where its training procedure is identical to the MMDP training procedure described in Appendix E.3 Only the policy extraction step is different for Dec-POMDP, where each agent's ' distory-dependent policies are trained by:
min E (J.D))D [log T (a.[T:)] A
(49)
min JEDD
Te. (a./T)) - es, + log Σ R2
no, (a: (7s) =1 (as 71)
(50)
J.2 Hyperparameter Details
We conduct minimal hyperparameter tuning for all algorithms for fair comparisons. It is also worth noting that in offline RL, is important to develop algorithms which require minimal hyperparameter tuning (23). We chose the best values for for both AlberDICE and OptiDICE between [0.1, 1, 5, 10) on N=2 (Tiny) for RWARE and RPS (2 agents) for GRF The best values were then used for all scenarios thereafter. The final values used were 0.1 (GRF) and = 1 (RWARE) for AlberDICE and a = (GRF, RWARE) for OptiDICE. We found that the performance gaps between different hyperparameters were minimal as long they were within reasonable range where training is numerically stable.
For ICQ 40 we found that the algorithm tends to become numerically unstable after certain number of training epochs even with sufficient hyperparameter tuning due the exploding Q values, especially in the GRF and SMAC environment.
30

---

K
Computational Resources
For Warehouse experiments, utilized single NVIDIA Geforce RTX 3090 graphics processing unit (GPU). The experiments for running AlberDICE took 5H, 14H, and 29H for 2, 4, 6 agent environments, respectively.
31


Reviews:
[{"review_id": "KHsKLApKXg", "reviewer": "Reviewer_s9Ry", "summary": "This paper introduces the AlberDICE framework that targets to address the out-of-distribution challenge (or distributional shift) in off-policy MARL. AlberDICE addresses this challenge by the alternating optimization procedure along with the regularization term. Also, AlberDICE addresses the curse of dimensionality in multi-agent settings with the autoregressive policy architecture. Empirical evaluations show that AlberDICE can find a more optimal solution than baselines in multiple multi-agent benchmark domains. ", "questions": "In addition to my concerns in the weaknesses section, I would like to ask the following questions:\n\n1. I appreciate the intuitive example (Figure 1) in the Introduction. If a centralized critic is employed with a decentralized actor, would the sub-optimality problem still happen?\n2. Section 3 states that \"when each agent is optimized alternatively, the objective function will always be monotonically improved and convergence is guaranteed.\" Would there be a proof or reference to this statement?\n3. Related to #2, while the monotonic improvement is guaranteed, would convergence to an optimal (Nash) equilibrium be guaranteed?\n4. According to Levine et al., 2020, the main challenge of off-policy learning is the distributional shift: a policy is trained under one distribution and it will be evaluated on a different distribution. In the evaluation section, it is unclear whether the learned cooperative policies are evaluated under a different distribution/environment/setting compared to the training dataset.\n5. Because the authors focus on cooperative settings, wouldn't it be better to target to converge to a correlated equilibrium instead of a Nash equilibrium as correlated equilibria are a superset of Nash equilibria (i.e., possible to converge to a more optimal solution). \n\nReference:\nLevine et al., Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems, 2020", "limitations": "Yes, the authors have adequately addressed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Theoretical contribution about showing how AlberDICE converges to a Nash equilibrium. \n2. Evaluations are performed across multiple domains, showing the empirical evidence of AlberDICE. ", "weaknesses": "1. A possible concern about alternatively finding the best response policy while fixing others is that this approach effectively solves a static single-agent problem from each agent's perspective. As a result, in some cooperative settings, this method may learn some sub-optimal joint collaborative policy. \n2. Related to #1, the approach of alternatively finding the best response may not work or be effective in competitive/mixed-sum game settings, limiting the scope of the proposed method. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer $\\text{\\textcolor{purple}{s9Ry}}$\n\nThank you for taking the time to provide feedback on our paper. Please feel free to let us know if any of our responses below need further clarification. We’d be more than happy to address them during the reviewer-author discussion period.\n \n> **W1. …in some cooperative settings, this method may learn some sub-optimal joint collaborative policy.**\n\nAs discussed in the Limitations section (Appendix A.10), our method that computes a Nash policy does not necessarily converge to the globally optimal joint policy, but instead it can converge to a local optimum. However, we have empirically demonstrated that AlberDICE performs well when just starting from a randomly initialized policy, significantly outperforming baseline algorithms on an extensive set of MARL benchmarks (Penalty XOR, Bridge, RWARE, GRF, and SMAC). Please also note that existing offline MARL algorithms relying either on IGM-principle (e.g. ICQ) or on decentralized training (e.g. OMAR) may struggle to solve even very simple problems (XOR, Bridge), whereas AlberDICE is capable of computing an optimal joint policy for these problems.\n\n\n> **W2. the approach of alternatively finding the best response may not work or be effective in competitive/mixed-sum game settings, limiting the scope of the proposed method.**\n\nIn this paper, we primarily focus on the fully cooperative MARL in an offline setting, in line with previous works [5-8]. Our main goal is to tackle the challenge of avoiding OOD joint actions, which can occur even in a fully cooperative setting and also has not yet been precisely addressed in the existing works, to the best of our knowledge. Furthermore, there are currently no standard high-dimensional benchmarks and datasets for general-sum MARL. Thus, we leave the extension of AlberDICE to solving general-sum settings in MARL as future work.\n\n> **Q1. If a centralized critic is employed with a decentralized actor, would the sub-optimality problem still happen?**\n\nIf the centralized critic is employed without limiting expressiveness, it may not suffer from the sub-optimality problem in principle. Still, it suffers from the exponential complexity with respect to the number of agents (i.e. curse of dimensionality), which makes it not scalable. Thus, to improve scalability, existing offline MARL algorithms such as ICQ [8] adopts (IGM-based) value decomposition structures with limited expressiveness for the centralized critic. Consequently, as can be seen in Table 1, ICQ, a representative offline MARL algorithm using a centralized critic and decentralized actor, suffers from the sub-optimality problem. Please see the Introduction (Lines 26-52) for an illustrative explanation for how ICQ can converge to sub-optimal OOD joint actions.\n\n> **Q2. Section 3 states that \"when each agent is optimized alternatively, the objective function will always be monotonically improved and convergence is guaranteed.\" Would there be a proof or reference to this statement?**\n\nYes, this is shown in the proof of Theorem 4.2 in Appendix A.4. A reference to Section 4 is indeed appropriate here and we will include this in the final version of the paper.\n\n> **Q3. Related to #2, while the monotonic improvement is guaranteed, would convergence to an optimal (Nash) equilibrium be guaranteed?**\n\nConvergence to a Nash policy is guaranteed, as shown in Theorem 4.2. However, please note that this Nash policy may not be optimal, as we discuss in the Limitations in Section A.10 in the Appendix. The outcome of the iterative best response depends on the starting point (region of attraction of each Nash policy) and is, thus, generally not guaranteed to find the optimal Nash policy [1]. This is the notorious equilibrium selection problem which is an open problem in games with multiple equilibria, even if they have common reward structure (See Open Questions in [2]). Nevertheless, good equilibria tend to have larger regions of attraction and practical performance is typically very good as demonstrated by our extensive experiments.\n\n> **Q4. In the evaluation section, it is unclear whether the learned cooperative policies are evaluated under a different distribution/environment/setting compared to the training dataset.**\n\nWe followed the evaluation protocol of standard offline (MA)RL [3]. The training dataset was collected by (multiple) data-collection policies in MMDP (or Dec-POMDP). Then, each offline MARL algorithm optimizes its target policy only using the offline training dataset, where distribution shift occurs since the target policy will be deviated from the data distribution to maximize the rewards. Finally, the learned (cooperative) policies are evaluated under the same MMDP (or Dec-POMDP) environment as in the data-collection procedure. We are not considering multi-task RL or domain transfer in this paper. Please refer to Section A.6 in the Appendix for a detailed explanation of how the dataset was constructed for all environments.\n\n> **Q5. [Why not Correlated Equilibria]**\n\nThe problem with correlated equilibria is that they are defined in the joint policy space, i.e., they can be non-factorizable (unless they are Nash equilibria) and hence, problematic for decentralized execution. For instance, the distribution 0.5/0.5 over (A,B) and (B,A) in the XOR game (Figure 1) is an (optimal) correlated equilibrium, but such a policy is not in a form that allows decentralized execution. Naively making a factorized policy from the correlated equilibria policy by considering its marginal distributions (0.5,0.5 for each player) leads to a (very) suboptimal set of policies for decentralized execution. In fact, maintaining a factorizable policy throughout its iterations, and ultimately, finding a Nash equilibrium (suitable for decentralized execution), rather than a correlated or coarse correlated equilibrium is one of the major contributions of AlberDICE.\n"}, {"review_id": "1ZWq7gjht7", "reviewer": "Reviewer_gucm", "summary": "The authors consider the offline multi-agent reinforcement learning setting. They provide an example to demonstrate that decentralisation can lead to out of distribution actions at test time. They derive AlberDICE, an offline RL method based on computing alternating best responses to the other agents' policies. Starting from the linear program for an MMDP, they learn a policy by:\n\n1. Pretraining a data policy $\\pi^D_{-i}(a_{-i} | s, a_i)$\n2. Using the current policy and current data policy to resample the dataset\n3. Solve a minimisation problem to find $\\nu^*$ \n4. Extracting the policy from $\\nu^*$ using I-projection. \n\nThis method prevents out of distribution actions by optimising each agent alternately and assuming the other agents' policies are fixed. A KL penalty is used to ensure that the resulting learned policy stationary distribution stays faithful to the dataset's distribution. By alternately optimising each agent, issues of producing out-of-distribution actions due to simultaneous updates do not arise. ", "questions": "I have a few clarifying questions. \n\n- How does the method scale to larger numbers of agents? Is the relatively small number of units in each scenario because of computational constraints running this method for more units? \n\n- In equation (4), the $\\pi_{-i}(a'_{-i} | s')$ from equation (3) seems to have disappeared. It reappears later in equation (5) so I think this is just a typo. Is this correct or have I missed a detail here?\n", "limitations": "The author discuss the limitations briefly in the appendix. The discussion there seems fine to me but of course more discussion of limitations is always appreciated.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall I enjoyed reading this paper. In particular:\n* The paper evaluates their algorithm on a wide range of domains and performs strongly across most tasks.\n* The authors explain the problem setting clearly and point out some problems with naive approaches to the problem.\n* The paper is generally well-written and clearly presented.", "weaknesses": "While the paper is good overall, there are some weaknesses of the work.\n* It would have been nice to see an explicit demonstration that the proposed method reduces out-of-distribution actions in the more complex environments and therefore that the mechanism proposed is the reason for the better performance.\n* The evaluations mostly focus on a small number of agents ($\\leq 10$). \n* Although the authors evaluate on a wide range of domains, they only evaluate on a small number of SMAC maps. This is a well-documented problem with MARL evaluation [1].\n* The discussion in lines 125--131 doesn't seem to make clear the presence of the KL penalty term in (2). For example, $\\pi^*$ is only the optimal policy *for the MMDP with a penalty as the reward*. Adding a few words in key places clarifying this point would make this section easier to read -- I was a little confused on first reading.\n\n\n\n[1] Gorsane, Rihab, et al. \"Towards a standardised performance evaluation protocol for cooperative marl.\" Advances in Neural Information Processing Systems 35 (2022): 5510-5521.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer $\\text{\\textcolor{magenta}{gucm}}$\n\nThank you for taking the time to provide detailed feedback on our work. We are happy to hear that you have enjoyed reading our paper. Please feel free to let us know if any of our responses below need further clarification. We’d be more than happy to address them during the reviewer-author discussion period.\n\n\n> **W1. It would have been nice to see an explicit demonstration that the proposed method reduces out-of-distribution actions in the more complex environments and therefore that the mechanism proposed is the reason for the better performance.**\n\nWe conducted additional experiments to quantitatively see that AlberDICE reduces OOD joint actions, compared with baselines in SMAC domains (see the PDF in the general response). In short, we first trained an uncertainty estimator $U(s, a)$ using the dataset $D$. Then, we evaluate $U(s, \\pi(s))$ for each $s \\in D$ and each algorithm's resulting policy $\\pi$ and draw a histogram of the estimated uncertainties. As can be seen in Figure B1 in the PDF, AlberDICE selects OOD joint actions significantly less frequently  than ICQ and OMAR while outperforming the baselines in terms of success rate.\n\n> **W2. The evaluations mostly focus on a small number of agents ($\\leq 10$).**\n\nCurrently, evaluating on a maximum of 10 agents is considered to be the state-of-the-art in Offline MARL [5-8]. Scaling to $> 10$ agents in an efficient way remains to be an important challenge in MARL in general, as described by Section 1.4 (Challenges of MARL) in [4].  In this work, we focus on the problem of joint action OOD and as we show in our experiments in Section 5 (especially in the Multi-Robot Warehouse domain) the performance gap between AlberDICE and other baselines widens as the *density* of the agents in an environment increases and more coordination is required to avoid sub-optimal behavior such as collisions. We leave the scalability to a large # of agents as future work. \n\n> **W3. Although the authors evaluate on a wide range of domains, they only evaluate on a small number of SMAC maps. This is a well-documented problem with MARL evaluation [1].**\n\nWe conducted additional experiments for two more SMAC maps, and please see below the results: 8m_vs_9m (Hard) and 3s5z_vs_3s6z (Super Hard) where AlberDICE still outperforms the baseline algorithms.\n\n| Scenario |      BC     |    ICQ     |  OMAR     |    MADTKD     |  OptiDICE  | AlberDICE |\n| :------------------:| :---------:|:---------:|:----------:|:-----------:|:----------:|:-----------:|\n| 8m_vs_9m (Hard) | 0.48±0.05|  0.12±0.21|   0.45±0.05| 0.14±0.04| 0.47±0.05| **0.67±0.06**|\n| 3s5z_vs_3s6z (Super Hard)|   0.45±0.03|  0.31 ± 0.04 | **0.60±0.05** | 0.18±0.02 | 0.42±0.04| **0.63±0.03**|\n\nHowever, we would like to point out that the problem raised by the reviewer is written in context to the larger problem that many papers use a single domain (such as SMAC) as their high-dimensional benchmark. On the other hand, we have provided extensive experiments on a wide variety of low to high-dimensional coordination tasks (XOR Game, Bridge, Google Research Football and Multi-Robot Warehouse) which are still challenging for many existing algorithms. Thus, we have focused on 6 (3 Hard, 3 Super Hard) maps which are relatively more difficult than other SMAC maps.\n\n> **W4. The discussion in lines 125-131 doesn't seem to make clear the presence of the KL penalty term in (2). For example,  $\\pi^\\ast$ is only the optimal policy for the MMDP with a penalty as the reward..**\n\nThank you for the suggestion. We will make it clear in the final version of the paper to improve readability.\n\n> **Q1. How does the method scale to larger numbers of agents? Is the relatively small number of units in each scenario because of computational constraints running this method for more units?**\n\nThe computational cost of our method grows linearly with the number of agents, thus it can solve the problems with a larger number of agents in principle. In our current implementation and computational resources, running experiments with 10 agents took around a few days, thus conducting experiments with tens or hundreds of agents is expected to take a few weeks, which is beyond our computational capabilities. Still, the main focus of this paper is to address the issue of OOD joint actions in offline MARL. To this end, we conducted experiments on an extensive set of MARL benchmarks up to 10 agents, where AlberDICE consistently outperforms the baselines while effectively avoiding OOD joint actions (see the PDF in the general response).\n\n> **Q2. In equation (4), the $\\pi_{-i}(a_{-i}’|s’)$  from equation (3) seems to have disappeared. It reappears later in equation (5) so I think this is just a typo. Is this correct or have I missed a detail here?**\n\n$-\\sum_{a_i^\\prime} d_i(s’, a_i’)$ in (4) is equal to $-\\sum_{a_i^\\prime, a_{-i}^\\prime} \\pi_{-i}(a_{-i}^\\prime | s’) d_i(s’, a_i’)$, given that $\\sum_{a_{-i}} \\pi_{-i}(a_{-i} | s') = 1$ since $\\pi_{-i}$ should be a valid probability distribution over $a_{-i}$.\n"}, {"review_id": "d9QqY6LG2Z", "reviewer": "Reviewer_82R1", "summary": "In this paper, the authors propose an alternative multi-agent offline reinforcement learning algorithm, where each agent is optimized for the best response policy and avoiding the out-of- distribution joint actions. The theoretical part proves the nash policies convergence after the presented training paradigm. The empirical results show promissing results on several well- known environments over existing offline MARL algorithms.", "questions": "See the weakness part.", "limitations": "In the practical scenarios, the observation and action space may have some noise that is not computable and may obstacle to the presented method.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "● The paper is well-written and easy to follow.\n\n● The theoretical results show the Nash policy convergence which integrates the trackable theory, relaxing the conventional IGM regularization.\n\n● The joint-action problem is novelly addressed in the offline MARL algorithm.", "weaknesses": "● The solution of the XOR game shown in the introduction for IGM-based and decentralized methods may not converge to (B,B) from the reviewer's perspective. These two categories of methods will connect the agents' policies by the mixing network for example, which is not\n totally individually be executed.\n\n● The claim from the authors for circumventing the curse of dimensionality in MARL is somewhat overclaimed. The curse of dimensionality also includes the explosion in the joint policy space due to the increasing agent number.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer $\\text{\\textcolor{green}{82R1}}$\n\nThank you for taking the time to review our paper. Please feel free to let us know if any of our responses below need further clarification. We’d be more than happy to address them during the reviewer-author discussion period.\n\n> **W1. The solution of the XOR game shown in the introduction for IGM-based and decentralized methods may not converge to (B,B) from the reviewer's perspective. These two categories of methods will connect the agents' policies by the mixing network for example, which is not totally individually be executed.**\n\nAs we have shown in the experiments, both IGM-based and decentralized methods converge to $(B, B)$ in the XOR Game (see Table 1 in Section 5.1 and the full results in Table 5 of Appendix Section A.7). The mixing network the reviewer refers to is used during training as a mechanism to aggregate the individual Q-functions to represent the global Q-function. However, since we are in the Centralized Training Decentralized Execution (CTDE) setting, the mixing network cannot be used during execution, and the policies must act independently (e.g. using only individual Q for each agent) without any correlation mechanism or centralized information. \n\n> **W2. The claim from the authors for circumventing the curse of dimensionality in MARL is somewhat overclaimed. The curse of dimensionality also includes the explosion in the joint policy space due to the increasing agent number.**\n\nWe respectfully disagree with the reviewer that we have overstated our claims of avoiding the curse of dimensionality. AlberDICE offers a principled mechanism to avoid the explosion in the joint action space by using an alternating optimization approach to finding the best response for each agent. This automatically reduces the policy space as well, since, at each optimization step, each agent is solving a reduced MDP (see Line 127-131) that is defined over the *individual* action space. Finally, we have shown in our experiments (especially in the Multi-Robot Warehouse results in Section 5.3) that AlberDICE significantly outperforms other baselines when the number of agents increases and the probability of the agents colliding increases.\nPlease let us know if our understanding of this concern is correct and we’d be more than happy to provide further clarifications if necessary.  \n\n> **(Limitations) In the practical scenarios, the observation and action space may have some noise that is not computable and may obstacle to the presented method.**\n\nWe are slightly confused regarding this statement. It would be very helpful for us if the reviewer can elaborate on this point. For example, is this referring to having noisy observations? If the comment is about the fact that we are considering MMDPs rather than Dec-POMDPs in the paper, please see the footnote for Line 77 in the Background section. To reiterate, we consider MMDPs for simplicity but our algorithm can be extended to partially observable settings, as we show in our experiments. \n\n"}, {"review_id": "0lGrH2WzP5", "reviewer": "Reviewer_aFwQ", "summary": "This paper proposes a new algorithm called AlberDICE for addressing the challenge of out-of-distribution joint actions in offline Multi-Agent Reinforcement Learning (MARL). The proposed algorithm performs centralized training of individual agents based on stationary distribution optimization, which circumvents the exponential complexity of MARL by computing the best response of one agent at a time while effectively avoiding OOD joint action selection. The authors show that the alternating optimization procedure converges to Nash policies theoretically and demonstrate that AlberDICE significantly outperforms baseline algorithms on a standard suite of MARL benchmarks in experiments.", "questions": "- $x$ in eq.10-14 is sample $(s, a, s')$, $e_v$ is also a function of $(s,a)$. How eq.14 is state-dependent instead of state-action-dependent?\n\n", "limitations": "The paper does not explicitly mention any limitations of the proposed method. The paper has no potential negative societal impact.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Nice writing flow for solving the original LP problem. The paper provides a clear and concise explanation of the proposed approach and its implementation.\n- AlberDICE is shown to produce much stronger policies than baselines in experiments conducted in many multi-agent environments.", "weaknesses": "- Since $\\pi_{-i}$ is fixed, the process in Section 3 is quite similar to that of OptiDICE, including Lagrangian formation, the closed-form solution, and I-projection used in policy extraction. Also, the distribution shift/OOD problem is solved by the series of DICE. It weakens the contributions of this paper.\n- The key point for AlberDICE is Theorem 4.2 which NE can be achieved. However, it is theoretically unclear to me why after the optimization, the inequality between lines 591-592 in the appendix holds. Let's consider an extreme case in the Rock Paper Scissors game. If the dataset only contains draw cases, how does AlberDICE reach NE? Maybe Theorem 4.2 lacks the necessary assumptions.\n\nminors/typos\n- \"+\" before the second line of eq.5\n- In line 188, \"pretrained.\" -> \"pretrained,\"\n- \"=\" before eq.16 -> \"$min_{\\pi_i}$\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer $\\text{\\textcolor{red}{aFwQ}}$\n\nThank you very much for the detailed review. Please feel free to let us know if any of our responses below need further clarification. We’d be more than happy to address them during the reviewer-author discussion period.\n\n\n> **W1. Since $\\pi_{-i}$ is fixed, the process in Section 3 is quite similar to that of OptiDICE, including Lagrangian formation, the closed-form solution, and I-projection used in policy extraction. Also, the distribution shift/OOD problem is solved by the series of DICE. It weakens the contributions of this paper.**\n\nTo the best of our knowledge, AlberDICE is the first offline multi-agent RL algorithm that precisely addresses the issue of selecting **joint** out-of-distribution action in a principled manner. While it is true that fixing other agents results in a single-agent RL problem, solving the induced single-agent problem in an \"offline\" manner is NOT trivial. Note that other agents' policy updates entail changes in the transition/reward dynamics of the (reduced) single-agent problem, but we do not have any samples for the 'shifted' dynamics in each reduced single-agent MDP. This is particularly problematic when applying regularization for conservatism in the joint action space. If we naively apply conservatism using single-agent offline RL methods to each single-agent MDP (e.g. $D_{KL}( d_i(s, a_i) || d^D_i(s,a_i) )$ term in OptiDICE's objective function or $E_{s \\sim D, a \\sim \\mu}[Q(s,a_i)] - E_{s \\sim D, a \\sim \\pi_D}[Q(s, a_i)]$ term in CQL's policy evaluation loss), each agent ends up optimizing a different objective function, which makes it challenging to ensure convergence to a Nash policy. It is also unclear if the obtained joint factorized policy can effectively prevent the OOD joint actions. In contrast, AlberDICE unifies the objective functions of all agents by adopting *conservatism on joint actions* (i.e. $D_{KL}(d_i(s, a_i) \\pi_{-i}(a_{-i}|s) || d^D(s, a_i, a_{-i}) )$), which explicitly prevents the OOD joint actions while providing a convergence guarantee to a Nash policy. Please also see Section A.3 in the Appendix for a detailed analysis on how a naive extension of OptiDICE is problematic in the multi-agent setting. Finally, we present extensive experiments on a wide range of domains and levels of difficulty where avoiding the selection of OOD joint actions and/or convergence to sub-optimal joint policies is challenging. In these environments, we  (1) identify the shortcomings of common approaches such as fully decentralized training and value factorization and (2) introduce the first DICE approach as a principled approach to avoiding distribution shift in Offline MARL.\n\n> **W2. The key point for AlberDICE is Theorem 4.2 which NE can be achieved. However, it is theoretically unclear to me why after the optimization, the inequality between lines 591-592 in the appendix holds. Let's consider an extreme case in the Rock Paper Scissors game. If the dataset only contains draw cases, how does AlberDICE reach NE? Maybe Theorem 4.2 lacks the necessary assumptions.**\n\nThe inequality in the proof of Theorem 4.2 holds because, after optimizing, agent $i$ cannot be worse off than before the optimization. Please note that the Rock Paper Scissors game is NOT an MMDP with a common reward structure, but rather it is a *zero-sum game*. In the case of non-cooperative MARL setting like zero-sum game, monotonic improvement cannot be guaranteed in general. In this paper, we are considering the cooperative MARL with common reward setting.\n\n> **Q1. $x$ in eq. 10-14 is sample $(s, a, s’), e_v$ is also a function of $(s,a)$.How eq.14 is state-dependent instead of state-action-dependent?**\n\nIn line 175, we mentioned that \"the function to learn\" is state-dependent. The function that we are optimizing, i.e. $\\nu: S \\rightarrow \\mathbb{R}$, is state-dependent (in contrast to Q-function which is state-action dependent). In (14), we are not optimizing $e$ function but only $\\nu_i$ function. We introduced $\\hat e_{\\nu_i}(x) := r(s,a) - \\alpha \\log \\frac{ \\pi_{-i}(a_{-i} |s) }{ \\pi_{-i}^D(a_{-i} | s, a_i) } + \\gamma \\nu_i(s') - \\nu_i(s)$ for notational brevity (line 141).\n\n> **(Limitations) The paper does not explicitly mention any limitations of the proposed method.**\n\nPlease see Section A.10 of the Appendix. \n"}, {"review_id": "p7oVS1Vz2P", "reviewer": "Reviewer_5Yz6", "summary": "the paper presents a novel approach, AlberDICE, an offline MARL algorithm that performs centralized training of individual agents based on stationary distribution optimization, to tackle the distribution shift challenge in offline MARL. The proposed method avoids OOD joint action selection by computing the best response of one agent at a time, thereby circumventing the exponential complexity of MARL. The authors provide theoretical proof of convergence to Nash policies and demonstrate through experiments that AlberDICE outperforms baseline algorithms on standard MARL benchmarks. \n\n", "questions": "Please refer to the weakness.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tIt proposes a novel solution to address the distribution shift problem in offline reinforcement learning by performing centralized training of individual agents and optimizing the stationary distribution. This approach effectively mitigates the issue of excessive distribution shift in offline multi-agent reinforcement learning.\n2.\tThe authors avoid the exponential complexity challenge in multi-agent reinforcement learning by computing the best response of individual agents in a sequential manner, reducing the computational burden.\n3.\tThe paper provides theoretical proof of convergence to Nash policies through the alternating optimization process, offering a theoretical guarantee for the effectiveness of the algorithm.\n4.\tExperimental results demonstrate that AlberDICE outperforms baseline algorithms significantly on standard multi-agent reinforcement learning benchmarks, validating the performance and effectiveness of the algorithm.\n", "weaknesses": "1.\tThis paper considers the other agents’ policies are fixed and optimized based on the distribution correction technique. However, what if the data set contains multiple cooperation strategies?\n2.\tEven though there are many derivations in Section 3, many are derived from existing work [1-3]. Section 3 should be simplified to highlight the contribution of this work.\n3.\tThis works adopt BC(Behavioral Cloning) to learn \\pi^D_{-i}. When the quality of the data set is not high, such as the medium data set, the effect of BC is very poor. Will this affect the performance of the algorithm?\n4.\tThere is little discussion on the limitations and applicability of the algorithm, and there is a lack of in-depth exploration of special cases or problems, which may restrict the generalization and application of the algorithm.\n5.\tNecessary ablation experiments are required, such as the robustness of parameters, the selection of network models, etc.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer $\\text{\\textcolor{blue}{5Yz6}}$\n\n\nThank you for taking the time to provide detailed feedback on our paper. Please feel free to let us know if any of our responses below need further clarification. We’d be more than happy to address them during the reviewer-author discussion period.\n\n\n> **W1. This paper considers the other agents’ policies are fixed and optimized based on the distribution correction technique. However, what if the data set contains multiple cooperation strategies?**\n\n\nFixed other agents' policies refer to our optimizing target policy (which changes over iterations), not the data-collection policy for other agents. Our method is not limited to the case where the dataset was collected by a single agent. In the experiments, we are already using the dataset *containing multiple cooperative strategies*. For example, in RWARE and GRF, we used 3 different agents to construct medium/expert dataset respectively. For Bridge-mix, we are using the dataset, which is a mixture of expert and random agents' experiences. We have discussed the details about the datasets in Section A.6 of the Appendix. Finally, even with the dataset that contains multiple strategies, AlberDICE outperforms the baselines.\n\n\n> **W2. Even though there are many derivations in Section 3, many are derived from existing work [1-3]. Section 3 should be simplified to highlight the contribution of this work.**\n\n\nAlthough the derivation of AlberDICE shares similarity with OptiDICE, its derivation is not identical nor trivial. While it is true that fixing other agents results in a single-agent RL problem, in *offline multi-agent* RL, we should additionally consider the distribution shift of other agents' policy, which corresponds to the case where transition/reward dynamics change in the reduced single-agent problem. The additional challenge here is that we do not have any samples for the 'shifted' dynamics for the reduced single-agent MDP. Importance sampling can address such a distribution shift in principle, but it suffers from large variance especially when the number of agents is large. To alleviate the large variance issue, we adopt importance resampling (IR) and fully derive the objective function that can be optimized very stably, which is one of our main contributions of this work. We will simplify Section 3 to make these points clear in the final version of the paper. \n\n> **W3. This works adopt BC(Behavioral Cloning) to learn $\\pi^D_{-i}$. When the quality of the data set is not high, such as the medium data set, the effect of BC is very poor. Will this affect the performance of the algorithm?**\n\nEvery offline (MA)RL algorithm is affected by the quality of the dataset. Still, if the dataset coverage over state-action space is sufficiently large and diverse, we can obtain a well-performing policy by controlling the conservatism hyperparameter (e.g. $\\alpha$ in AlberDICE). When we tested AlberDICE on a random dataset (very poor in terms of data-collection policy's performance) in Bridge, it still could converge to an optimal joint policy. We believe that there is no reason why AlberDICE should suffer much more adversely from bad dataset quality than other algorithms. Please also note that $\\pi^D_{-i}$ is only used for importance resampling which is to correct the distribution shift between the policy being learned and the policy used for data collection. For more details about how the datasets were constructed, please refer to Section A.6 of the Appendix.\n\n\n> **W4. There is little discussion on the limitations and applicability of the algorithm, and there is a lack of in-depth exploration of special cases or problems, which may restrict the generalization and application of the algorithm.**\n\n\nWe have provided a discussion on the limitations of our approach in Section A.10 in the Appendix regarding the use of Nash policies, and how it may not necessarily converge to the global optimum. For example, consider the following matrix game:\n```\n~ A B\nA 1 0\nB 0 2\n```\nIf AlberDICE starts its optimization from a deterministic target policy that selects (A,A), it may not be able to escape from the local optimum due to its nature of computing the best response. Still, AlberDICE starting from a randomly initialized policy works well in practice, yielding better-performing policies than the baselines across multiple domains. Finally, throughout the paper we have stayed consistent in our problem setting (i.e. common reward settings and Multi-Agent MDPs), which is commonly used in all previous offline MARL baselines [5-8]. Please let us know if there are any specific limitations and we would be happy to provide any further clarifications.\n\n> **W5. Necessary ablation experiments are required**\n\n\nWe have added additional ablation results for the choice of hyperparameter $\\alpha$ that controls conservatism in the PDF in the general response, which is also shown below:\n\n| $\\alpha$ |     CA-Hard (GRF)    | Corridor (SMAC)| \n| :------------------:| :---------:| :---------:|\n| 0.001 | 0.00 ± 0.00| 0.00 ± 0.00 |\n| 0.01 | 0.08 ± 0.11 | 0.00 ± 0.00 |\n| 0.1 | 0.82 ± 0.03| 0.92 ± 0.02 |\n| 1 | 0.84 ± 0.06| 0.97 ± 0.01|\n| 10 | 0.78 ± 0.09|  0.95 ± 0.03 |\n| 100 | 0.78 ± 0.11 | 0.92 ± 0.03 |\n| 1000 | 0.79 ± 0.11| 0.91 ± 0.04 |\n\nTable B2: Ablation results for the conservatism hyperparameter $\\alpha$. Mean success rate and standard error shown over 3 random seeds. \n\nHere the results show that AlberDICE is not too sensitive to the hyperparameter $\\alpha$ as long as it is within a reasonable range. \n"}]

Author rebuttal:
# General Response 

We thank all reviewers for taking the time to provide constructive feedback on our paper. We are encouraged that they find the following strengths in our work:

- Clear presentation of the problem with OOD joint actions and the failures of previous approaches (Reviewers $\text{\textcolor{magenta}{gucm}}$, $\text{\textcolor{green}{82R1}}$)
- Novel approach to solving the joint action OOD problem (Reviewers $\text{\textcolor{green}{82R1}}$, $\text{\textcolor{blue}{5Yz6}}$)
- Theoretical contribution showing convergence to Nash policies (Reviewers  $\text{\textcolor{green}{82R1}}$, $\text{\textcolor{purple}{s9Ry}}$, $\text{\textcolor{blue}{5Yz6}}$)
- Strong empirical performance over baselines on a wide range of MARL environments (Reviewers  $\text{\textcolor{magenta}{gucm}}$, $\text{\textcolor{purple}{s9Ry}}$ $\text{\textcolor{green}{82R1}}$, $\text{\textcolor{red}{aFwQ}}$, $\text{\textcolor{blue}{5Yz6}}$)
- Well-written and easy to follow (Reviewers $\text{\textcolor{magenta}{gucm}}$, $\text{\textcolor{green}{82R1}}$, $\text{\textcolor{red}{aFwQ}}$) 

Since the reviewers raised concerns which were mostly different, we reply to each reviewer separately. We also provide additional experimental results in the attached single-page PDF which include the following: 

- Demonstration of AlberDICE reducing OOD joint actions in complex domains (Reviewer $\text{\textcolor{purple}{s9Ry}}$)
- SMAC results on 2 additional maps (Reviewer $\text{\textcolor{purple}{s9Ry}}$) 
- Ablation results (Reviewer $\text{\textcolor{blue}{5Yz6}}$)

Please let us know if further clarifications are needed as we would be more than happy to answer them during the reviewer-author discussion phase.

Finally, we list below the references which are used throughout the responses.

## References 

[1] Multiagent Value Iteration Algorithms in Dynamic Programming and Reinforcement Learning (Bertsekas 2020)

[2] Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games (Leonardos et, al. ICLR 2022)

[3] D4RL: Datasets for Deep Data-Driven Reinforcement Learning (Fu et, al. 2021)

[4] Multi-Agent Reinforcement Learning: Foundations and Modern Approaches (Albrecht et, al. Preprint MIT 2023)

[5] Offline pre-trained multi-agent decision transformer (Meng et, al. Arxiv 2022)

[6] Plan better amid conservatism: Offline multi-agent reinforcement learning with actor rectification (Pan et, al. ICML 2021) 

[7] Offline multi-agent reinforcement learning with knowledge distillation (Tseng et, al. NeurIPS 2022)

[8] Believe what you see: Implicit constraint approach for offline multi-agent reinforcement learning (Yang et, al. NeurIPS 2021)




Meta-review: The authors present a novel method, AlbertDICE, for training offline policies in fully cooperative multi-agent RL settings. 

Specifically, the authors apply a coordinate ascent type strategy, but optimising one agent at a time. 
They also provide a novel mechanism to deal with the ood problem of action selection in offline RL and provide theoretical guarantees. 

Overall, the reviewers agreed that the paper makes valuable contributions and that the empirical results are impressive, in particular on the super-hard SMAC maps. 

Based on taking a look at the paper I have a few suggestions for improvement:
1) The paper introduces MMDPs (fully observable) but evaluates on SMAC (Dec-POMDP). It would be great to resolve this inconsistency.
2) SMAC has largely become obsolete, at least for online RL. Time permitting, it would be great to test on SMACv2 instead (https://sites.google.com/view/smacv2). 
3) Authors should also take the suggestions for the reviewers to hard and include the new results and ablations from the rebuttals. 

Assuming those changes I recommend that the paper is accepted for publication if there is space.
Decision: Accept (poster)