Believe What You See: Implicit Constraint Approach for Offline Multi-Agent Reinforcement Learning
Authors: Yiqin Yang
Xiaoteng Ma
Chenghao Li
Zewu Zheng
Qiyuan Zhang
Gao Huang
Jun Yang
Qianchuan Zhao
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Extrapolation Error
Offline Reinforcement Learning
Multi-Agent Reinforcement Learning

Abstract: Learning from datasets without interaction with environments (Offline Learning) is an essential step to apply Reinforcement Learning (RL) algorithms in real-world scenarios.	However, compared with the single-agent counterpart, offline multi-agent RL introduces more agents with the larger state and action space, which is more challenging but attracts little attention. We demonstrate current offline RL algorithms are ineffective in multi-agent systems due to the accumulated extrapolation error. In this paper, we propose a novel offline RL algorithm, named Implicit Constraint Q-learning (ICQ), which effectively alleviates the extrapolation error by only trusting the state-action pairs given in the dataset for value estimation.  Moreover, we extend ICQ to multi-agent tasks by decomposing the joint-policy under the implicit constraint.  Experimental results demonstrate that the extrapolation error is successfully controlled within a reasonable range and insensitive to the number of agents. We further show that ICQ achieves the state-of-the-art performance in the challenging multi-agent offline tasks (StarCraft II). Our code is public online at https://github.com/YiqinYang/ICQ.

Believe What You See: Implicit Constraint Approach for Offline Multi-Agent Reinforcement Learning
Yiqin Yang"; Xiaoteng Ma Mj Chenghao Li', Zewu Zheng's Qiyuan Zhang", Gao Huang', Jun Yang' ; Qianchuan Zhao' 'Tsinguua University. "Harbin Institute of Technology [yangyiqi19 19, ma-xti7, lich18) tsiiiuu.tinngua..ee zhangqiyuan 19 @ hit.edu.cn, (gaohuang, yangjun603, zhaoqe] @ @tsunghua.edu.cn
zzheng 17@ 126.com,
Abstract
Learning from datasets without interaction with environments (Offline Learning) is essential step apply Reinforcement Learning (RL) algorithms in real-world scenarios. However, compared with the single-agent counterpart, offline multi- agent RL introduces more agents with the larger state and action space, which is more challenging but attracts little attention. We demonstrate current offline RL algorithms are ineffective in multi-agent systems due to the accumulated extrapola- tion error. In this paper, we propose novel offline RL. algorithm, named Implicit Constraint Q-learning (ICQ), which effectively alleviates the extrapolation error by only trusting the state-action pairs given in the dataset for value estimation. Moreover, we extend ICQ to multi-agent tasks by decomposing the joint-policy under the implicit constraint. Experimental results demonstrate that the extrapo- lation error is successfully controlled within a reasonable range and insensitive to the number of agents. We further show that ICQ achieves the state-of-the--e art performance in the challenging multi-agent offline tasks (StarCraft II). Our code is public online at https://github.com Yiqin Yang/ICQ
Introduction
Recently, reinforcement learning (RL), active learning process, has achieved massive success in various domains ranging from strategy games [59] to recommendation systems [8] However, applying RL real-world scenarios poses practical challenges: interaction with the real world, such as autonomous driving, is usually expensive or risky. To solve these issues, offline RL is an excellent
choice deal with practical problems 3 24 35 42
[5
28
aiming at learning from
fixed dataset without interaction with environments.
The greatest obstacle of offline RL is the distribution shift issue [16]. which leads to extrapolation error, a phenomenon in which unseen state-action pairs are erroneously estimated. Unlike the online setting, the inaccurate estimated values of unseen pairs cannot be corrected by interacting with the environment. Therefore, most off-policy RI. algorithms fail in the offline tasks due to intractable over- generalization. Modern offline methods (e.g., BatchhConsttrined deep Q-learning (BCQ) (16) aim to enforce the learned policy to be close to the behavior policy or suppress the Q-value directly. These methods have achieved massive success in challenging single-agent offline tasks like D4RL (14]
However, many decision processes in real-world scenarios belong to multi-agent systems, such as intelligent transportation systems (2) sensor networks [37], and power grids [7]. Compared with the single-agent counterpart, the multi-agen system has a much larger action space, which grows
Equal Contribution.
Equal Corresponding.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

QU 7
max (16) a
possible trajectories pairs pairs
9 actions considered by
Ao+1
P9
of"
actions considered by BCQ
(a) BCQ.
(b) ICQ
The comparison between ICQ and BCQ for the target Q-value estimation. The spots denote states, and the connections between spots indicate actions. The red solid-lines denote seen pairs, and the gray dotted-lines are unseen pairs. (a) BCQ estimates Q-value in defined similar action set (orange) while unseen pairs still exist in the set with low probability. (b) ICQ only adopts seen pairs (orange) in the training set for Q-value estimation.
Figure I:
exponentially with the increasing of the agent number. When coming into the offline scenario, the unseen state-action pairs will grow exponentially as the number of agents increases, accumulating the extrapolation quickly. The current offline algorithms are unsuccessful in multi-agent tasks though they adopt the modern value-decomposition structure [26 48 255. As shown in Figure our simple
results indicate that BCQ, state-of-the of-the-art offline algorithm, has divergent Qesttimates multi-agent MDP environment (e.g., BCQ (4 agents)). The extrapolation eтror for value estimation is accumulated quickly as the number of agents increases, significantly impairing the performance.
Based on these analyses, we propose the Implicit Constraint Q-learning (ICQ) algorithm, which effectively alleviates the extrapolation enror Motivated by an implicit constraint optimization problem, ICQ adopts a SARSA-like approach 49 evaluate Q-values and then converts the policy learning into supervised regression problem. By decomposing the joint-policy under the implicit constraint, we extend ICQ to the multi-agent tasks successfully. To the best of our knowledge, work is the first study analyzing and addressing the extrapolation error multi-agent reinforcement learning.
unseen pairs involved in estimating Q-value.
We evaluate algorithm the challenging multi-agent offline tasks based on StarCraft II 40). where a large number of agents cooperatively complete task. Experimental results show that ICQ control the extrapolation error within reasonable range under any number of agents and learn from complex multi-agen datasets. Further, we evaluate the single-agent version of ICQ in D4RL, a standard single-agent offline benchmark. The results demonstrate the generality of ICQ for wide range of task scenarios, from single-agent to multi-agent, from discrete to continuous control.
2 Background
Notation. The fully cooperative multi-agent tasks are usually modeled as the Dec-POMDP B1
consisting of the tuple G = (S, A, P, r. O, n, 7). Let E denote the true state of the environment. At each time step t Z+, each agent i N {I, ... n) chooses action a' A, forming a joint action a E = A". Let P(s' s, a) S x x S + [0 denote the state transition function. All agents share the same reward function r(s, a) S A IR
consider a partially observable scenario which each agent draws individual observations of E Ω according to the observation function O(s,a) S A - Ω. Each agent has an action-observation history T² E T (Ω x A)', on which it conditions a stochastic policy ra(" r²) parameterized by 0 T + [0, 1]. The joint action-value function is defined Su = s, du a, π.) where is the poitty with param- eters 0 = (f,,..., ..,... B.). Let denote the offline dataset, which contains trajectories of the behavior policy μ..
( (T, a) E Eg agone -== 1'r
We adopt the centralized training and decentralized execution (CTDE) paradigm During training, the algorithm has access to the true state and every agent's 's action-observation history 7.

---

as well as the freedom to share all information between agents. However, during execution, each agent has access only to its action-obserrattio history.
Batch-constrained deep Q-learning (BCQ) is a state-of-the-art offline RI method, which aims to avoid selecting unfamiliar action the next state during value update. Specifically, BCQ optimizes π by introducing perturbation model E(T, a, 2 and generative model G(T; as follows
π (T) abi a67,+((7,a6)))))
arg max Q" (T, E(T; a 4): d)) s.l. {alt G(Ts+))
where π selects the highest valued action from a collection of actions sampled from the generative model G(T; pp), which aims to produce only previously seen actions. The perturbation model E(T, al1,, @) is adopted to adjust action all in the range [-4, Φ] to increase the diversity of actions.
3 Analysis of Accumulated Extrapolation Error in Multi-Agent RL
In this section, we theoretically analyze the extrapolation error propagation in offline RL, which lays the basis for Section 4 The extrapolation error mainly attributes the out-of-distribuias (OOD) actions in the evaluation Q" x [16 21. To quantify the effect of OOD actions, we define the state-action pairs within the dataset as seen pairs. Otherwise, we name them as unseen pairs. We demonstrate that the extrapolation error propagation from the unseen pairs to the seen pairs is related to the size the action space, which grows exponentially with the increasing number of agents. We further design toy example to illustrate the inefficiency of current offline methods in multi-agent tasks.
3.1 Extrapolation Error Propagation in Offline RL
Following the analysis in BCQ [16], define the tabular estimation error as eMPP(T, a) A - (%(T,a) (here we abuse to denote the state for analytical clarity.. where the M denotes the true MDP and B denotes a new MDP computed from the batch by PB(T' T. W a, r')/ E W(T, a, f). BCQ [16] has shown that EMDP(T, a) has a Bellman-lik, form with the extrapolation error EEXT (T, a) the "reward function":
EMDP(T, a) e EEXT(TT,) + Σ PM [,,a) ET(a' T(a' s')eMDD(F',a'),
(2)
() = Σ (Par(T' aT,)) Ps(T' [T,))) (r(T,a,7')+7 + + n(d I 17))%((r,a))
For the seen state-action pairs, 6EXT(T, a) 0 since (M a, Ps(T' r. a) 0 in the deterministic environment. In contrast, the <xxT(T, (T, a) of unseen pairs uncontrollable and depends entirely on the initial values in tabular setting or the network generalization in DRL.
To further analyze how the extrapolation error the unseen pairs impacts the estimation of actions in the dataset, we partition ÉMDP and ÉEXT as ÉMDP = |Es, 6u]" and ÉEXT = [0, eb]² respectively according seen and unseen state-action pairs. Let denote the transition matrix of the state-action pairs as (T f',d a'
(M T, (a' | r'). We decompose the transition matrix as s,s s.i pT unu according to state-action pairs' property (c.g., pr (Tu, a' Tax 0g) = (M Ta (a)T(e (a', T denotes the transition probability from seen to unseen pairs). Then the extrapolation error propagation can be described by the following linear system:
T.
PT P pr
Es Eu
pm
u.s
pi n,u
P
Es cu
+
Eb
0
(3)
Based on the above definitions, we have the following conclusion.
Theorem 1. Given deterministic MDP, the propagation of to es is proportional to p P
? P
||x 5 (1 71-7) 1-
|bbllao
(4)
P 8.5
"Note that we adopt different definition of extrapolation error with BCQ. The CMDP (T, a) is regraded as the extrapolation error in BCQ, while the generalization error of unseen pairs eEXT (T, a) is considered in this work.
3

---

Estimated Value
BCQ (2 agents)
0
*
BCQ (4 agents)
a: 5
Ours: ICQ agents)
agents)
Value
7
0-
0.0
1.0
1.5
2.0
= On = a11.. =1
Million Steps
(a) Two-state MMDP.
(b) Estimated value of the joint action-value fuunction
Figure 2: (a) An MMDP where Q-estimates of BCQ will diverge as the number of agents increases. (b) The learning curve of the joint action-value function while running several agents in the given MMDP. The true values are similar in this task with different agent numbers, calculated by averaging the Monte-Carke Carlo estimation under different agents. The Qesstmmates of BCQ (4 agents) diverge while our algorithm (ICQ) has accurate Q-estimates. Please refer to Appendix C.2 for the complete results.
The above theorem indicates the effect of extrapolation error on seen state-action pairs is directly proportional to PI In the practice. || oc related to the size of action space and the dataset. If the action space is enormous, such as multi-agent task with number of agents, we need larger amount of data to reduce [| lo. However, the dataset size in offline learning tasks is generally limited. Moreover, when using the networks to approximate the value function, éb does not remain constant as QT(Tu, an) could be arbitrary during training, making the Q-values extreme large even for the seen pairs. For these reasons, we have to enforce the P - 0 by avoiding using OOD actions. For example, BCQ utilizes an auxiliary generative model to constrain the target actions within a familiar action set (see Section 2 for detailed description). However, the error propagation heavily depends on the accuracy of the generative model and is intolerable with the agent number increasing. We will demonstrate this effect in the following toy example.
3.2
Toy Example
We design a toy two states Multi-Agent Markov Decision Process (MMDP) to illustrate the accumu- lated extrapolation error in multi-agent tasks (see Figure 2a All agents start at state 72 and explore rewards for 100 environment steps by taking actions d[1 = or dgg = 1. The optimal policy is that all agents select d[j). The MMDP task has sparse rewards. The reward is I when following the optimal policy, otherwise, the reward is O. The state 72 will transfer to Tı if the joint policy satisfies
D ag S 2 at 72, while the state Tj will never return to 72.
We run BCQ and our method ICQ on a limited dataset, which only contain 32 trajectories generated by QMIX. Obviously, the number of unseen state-action pairs exponentially grows as the number of agents increases. We control the amount of valuable trajectories (r 1) in different datasets equal for fair comparisons. The multi-agent version of BCQ shares the same value-decomposition structure as ICQ (see Appendix D.2).
As shown in Figure 26] the joint action-value function learned by BCQ gradually diverges as the number of agents increases while ICQ maintains reasonable Q-value. The experimental result is consistent with Theorem and we provide an additional analysis for the toy example in Appendix [.2] In summary, we show theoretically and empirically that the extrapolation error accumulated quickly as the number of agents increases and makes the Q-estimates easier to diverge.
4 Implicit Constraint Approach for Offline Multi-Agent RL
In this section, we give an effective method to solve the accumulated extrapolation error in offline Multi-Agent RL based on the analysis of Section 3] From the implementation perspective, we find that a practical approach towards offline RL is to estimate target Q-value without sampled actions from the policy in training. We propose Implicit Constraint Q-learning (ICQ), which only trusts the seen state-action pairs in datasets for value estimation. Further, we extend ICQ to multi-agent tasks with value decomposition framework and utilize a A-return method to balance the variance and bias.

---

4.1 The Implicit Constraint Q-learning (ICQ) Approach
Based on the analysis of Section B] we find that the extrapolation error can be effectively alleviated by enforcing the actions within the dataset when calculating the target values, which is the most significant difference between offline and off policy RL. For a formal comparison of off policy and offline algorithms, we first introduce the standard Bellman operator T as follows:
(5) Many off-policy evaluation methods, such as the Tree Backup [10] and Expected SARSA 41 are designed based on this operator. However, when coming into the offline setting, the standard Bellman operator suffers from the OOD issue as the actions sampled from current policy ा are adopted for target Q-value estimation. A natural way to avoid the OOD issue is adopting the importance sampling measure (30
(T,) - Q(T,a) + E,, + y 1Q(T', a')] Q(T, a)).
(T* Q(T,a) + Er + y a') a(T,a)],
where p(T', m(alr')
p(aa(r") denotes the importance sampling weight. If we can calculate p(T', .d)) with action a' sampled from p. rather than x, the unseen pairs will be avoided for target Q-value estimation. In this case, the extrapolation error theoretically avoided since PE, - The estimated Q-value based on the above operation would be stable even in complex tasks with enormous action space. However, in most real-world scenarios, it is hard to obtain the exact behavior policy to calculate p(r', ,'), e.g., using expert demonstrations. Fortunately, constraint optimization problem is efficient to compute the desired importance sampling weight.
find that the solution of following implicit
4.1.1 Implicit Constraint Q-learning
In offline tasks, the policies similar to the behavior policy are preferred while maximizing the accumulated reward (T, a). i.e., DKL [)[r] S e. The policy optimization with the behavior regularized constraint can be described in the following problem:
Tk+1 arg max E. (-> Q a)).
s.t.
D p)[T] Sc
This problem has well studied in many previous works 36 1 58
Note that the objective is a linear function of the decision variables and all constraints convex functions. Thus obtain the optimal policy n² related to μ through the KKT condition (9, for which the proof is in Appendix B.4
1
QTH (T)
x (a (T Z(7)
uuaa
T) exp
where a is the Lagrangian coefficient and Z(r) Ea p(ā 7) exp (2.Q* (r, â)) is the normalizing partition function. Next, we calculate the ratio between and f by relocating to the left-hand side:
p(T, = Th+1 () m(a ()) Z(T)
tThh (Tt(aa))
exp
(9)
a
Motivated on Equation
we define the Implicit Constraint Q-learning operator
1 [ (T',a') ((7") exp
Q Q((d)).
= + 7
(10)
a
Thus we obtain SARAR-like algorithm which not uses any unseen pairs.
Comparison with previous methods. While BCQ learns an action generator to filter unseen pairs in Q-value estimation, it cannot work in enormous action space due to the error of the generator (see Figure DT. Instead, in the value update of ICQ, we do not use the sampled actions to compute the target values, thus we alleviate extrapolation error effectively. There are some previous works, such as AWAC [29] and AWR [35), addressing the offline problem with similar constrained problem in Equation 7 However, these methods only impose the constraint on the policy loss and adopt the standard Bellman operator to evaluate Q-function, which involves the unseen actions or converges to the value of behavior policy μ. Differently, we re-weight the target Q(r', a') with the importance sampling weight derived from the optimization problem, which makes the estimated value closer to the optimal value function.
5

---

4.1.2 Theoretical Analysis
The ICQ operator in Equation 10 results in a SARSA-like algorithm, which be re- re-written as:
1 Z(p (7) exp (derr.0t) Q
TicQQ(T, - -
Σ A'EB
(11)
This update rule can be viewed as regularized softmax operator [4] in the offline setting. When - Jc. TicQ approaches TV. When + 0. Tic becomes the batch-constrained Bellman optimal operator TBCQ [16], which constrains the possible actions with respect to the batch:
TBCQQ(T,a)
+ y max Q(T', a'ER
(12)
TECQ has been shown converge to the optimal vetion-value function Q" of the batch, which means limg--oo BBQ Qo Q" for arbitrary Qo- Based on this result, show that iteratively applying TiCQ will result in Q-function not far away from Q":
Theorem 2. Let TioQ Qo denote that the operator Tioq iteratively applied over an initial state- action value function Qo for & times. Then, we have V(T, u). lim supk TeqQo(TT S Q" (T,
lim inf TiQ (o(CQQ)(Fra)) (0, - -(A|--1) max 71-7)
1 (1C 1+ Cexp(a)
2Q max
(13)
R-+00
where |A| is the action space, |Azl is the action space for state T, C f infres inf inf plaglr)
p(ep)r)
and planp 7) denotes the probability of choosing the expert action according to behavioral policy μ.. Moreover, the upper bound of T TiqQu Qo decays exponentially fast in terms of a.
While Tieq is not a contraction 5 (similar with the softmax operator), the Q- Qaluuuss are still within reasonable range. Further, Ticq converges to TBCQ with an exponential rate in terms of a. Our result also quantifies the difficulty in offline RL problems. Based on the definition of p p(aglT)) C shows the proportion of the expert experience in the dataset. A larger corresponds to more expert experience, which induces a smaller distance between TicQQo(z a) and Q" (T, a). In contrast, with a small C, the expert experience is few and the conservatism learning is necessary.
4.1.3 Algorithm
Based on the derived operator Ticq in Equation 9 we can learn Q(T, a: Φ) by minimizing
Q (2((aa:0)
) Q (T','';; Q (T)
(Ø) E F'' 7 ((r)) exp
(14)
where the Q-network and the target Q-network are parameterized by Φ and ø respectively.
As for the policy training, we project the non- parameametticc optimal policy T in Equation & into the parameterized policy space by minimizing the following KL distance, which implemented on the data distribution of the batch:
To(a 7) T a (T)
In (0) = ETTB [DKL (1=))))T0) [r]] = ETTB - Σ n Th+ila (a (T) log log
Tktz(a
(0) Ep=
u(a [T) p(a (- (a T))
(15)
b E Ba B
Z(T) log(T(( T)))) exp Q(T,
where (a) ignores E,~8 [E, + (a r) log Togri T (a 7)] that is not related to and (b) applies the importance sampling weight derived in Equation 9 under forward KL constraint. Note that tuning the a parameter in Equation 13 between 0 and oo interpolates between Q-learning and behavioral cloning. See Appendix A for the complete workflow of the ICQ algorithm. We provide two implementation options to compute the normalizing partition function ((T), which is discussed in detail in Appendix D.I D.I

---

4.2 Extending ICQ to Multi-Agent Tasks
In the previous section, we propose an implicit constraint Q-learning framework by re-weighting target Q-value Q(T', a') in the critic loss, which is efficient to alleviate the extrapolation error. We next extend ICQ to multi-agent tasks. For notational clarity, we name the Multi- Agent version of ICQ as ICQ-MA.
4.2.1
Decomposed Multi-Agent Joint-Policy under Implicit Constraint
Under the CTDE framework, have train individual poli- cies for decentralized execution. Besides, it is also challeng- ing compute y [p(T', aa')Q" (('''''))) a') in multi-agent policy evaluation as its computational complexity is O([A|"). To address the above issues, we first define the joint-policy as
Qa (T, a,
ICQ-MA Loss
MLP S
Ta T) - I' T²), and then introduce mild value-decomposition assumption:
W1, W2 ... Wn
Q (T) Σ w0' (F b(T),,
(16)
Q' (T (T',aa) Q" (r",a")
where (T) 2 0 and b(T) generated by the Mixer Net- work whose inputs are global observation-action history (see Figure (}. Based on the above assumptions, we propose the decomposed multi-agent joint-policy under implicit constraint in the following theorem:
Figure 3: Mixer Network.
Theorem 3. Assuming the joint action-value function is linearly decomposed, can decompose the multi-agent joint-policy under implicit constraint as follows
log(n' (²)) exp w
Σ E
π arg max
(17)
('(Tt)
x "5..7
where (TT)) = Eas 1s (a(aa exp ( ( (T' aa))
is the normalizing partition function.
The decomposed multi-aue agent point-policy has a concise form. We can train individual policies n by minimizing
(x) = Σ Fy a'
-0)
1 ('(++)
log(="(() (at 1+)) exp ( w
( (T)
(18)
Besides, wi (T) achieves the trade-off between the roles of agents. If some agents have important roles, the value of corresponding w'(T) relatively large. Also, if w'()) 0, æ² is approximately considered as the behavior cloning policy. As for the policy evaluation, we train Q(T a: (, vb) by minimizing
1
exp (Q(TH))) Q(T(+1, - Q(T,,((TT, at)
Told, w) = -Es
ΣGAAj
rr +
7(T(41)
120
(19)
where Q(T(+1) a.+1) = E, w² (T ('Q) (T ((41560) - b(T(+185).
4.2.2 Multi-Agent Value Estimation with A-return
As the offline dataset contains complete behavior trajectories, is natural to accelerate the convergence of ICQ with the n-step method. Here we adopt Q()) [27) to improve the estimation of ICQ, which weights the future temporal difference signal with decay sequence X.. Further, the constraint in Equation 7 implicitly meets the convergence condition of Q(A). Therefore, we extend the ICQ operator in Equation 10 to n-step estimation, which is similar to Q(A):
(TicQ Q(T, a) + E,
(TT))' (rr (1 a.+1) - Q(T,, ai)) 22
(20)
where P(T,, az) ((. exp( ((T.,.,)) and hyper-parameter 0 A < provides the balance between bias and variance.
7

---

BCQ-MA
CQI-MA
MMM
10m vs 11m
3o 15 32
2:32
10
Averag
20 Thossand Ecloodes
Thousand Epsodes
Thousand Epioodes
Thouaand Episodes
Figure 4: Performance comparison in offline StarCraft II tasks.
Table 1: Performance of ICQ with five offline RL baselines on the single-agent offline tasks with the normalized score metric proposed by D4RL benchmark [14), averaged over three random seeds with standard deviation. Scores roughly range from 0 to 100, where O corresponds to a random policy performance and 100 indicates an expert. The results for BC, BCQ, CQL, AWR and BRAC-p are
taken from 14 22
Dataset type
Environment
ICQ (ours)
BC
BCQ
CQL
AWR
BRAC-p
fixed
antmaze-umaze
85.0 + 2.7
65.0
78.9
74.0
56.0
50.0
play
antmaze-medium
80.0 1.3
0.0
0.0
61.2
0.0
0.0
play
antmaze-large
51.0 4.8
0.0
6.7
15.8
0.0
0.0
diverse
antmaze-umaze
65.0:13.3
55.0
55.0
84.0
70.3
40.0
diverse
antmaze-medium
65.0 3.9
0.0
0.0
53.7
0.0
0.0
diverse
antmaze-large
44.0 4.2
0.0
2.2
14.9
0.0
0.0
expert
adroit-door
103.9
101.2
99.0
102.9
-0.3
expert
adroit-relocate
109.5
101.3
41.6
91.5
-0.3
expert adroit-pen
123.8 22.1
85.1
114.9
111.0
-3.5
expert
hammmr
2.5
125.6
107.2
39.0
0.3
human
adroit-door
6.442.4
0.5
-0.0
9.1
0.4
-0.3
human
adroit-relocate
1.7
-0.0
-0.1
0.35
-0.0
-0.3
human
adroit-ped
91.3 10.3
34.4
68.9
55.8
12.3
8.1
human
adroit-hammen
2.0++0.9
1.5
0.5
1.2
0.3
medium
walker2d
71.8=10077
66.6
53.1
79.2
17.4
77.5
medium
hopper
55,6:15.7
49.0
54.5
58.0
35.9
32.7
medium
halfcheetah
42,5+113
36.1
40.7
44.4
37.4
43.8
med-expert
walker2d
98.9 + 5.2
66.8
57.5
98.7
53.8
76.9
med-expert
hopper
109.0+13.6
111.9
110.9
111.0
27.1
1.9
med-expert
halfcheetah
110.3
35.8
64.7
104.8
52.7
44.2
5
Related Work
As ICQ-MA seems be the first work addressing the accumulated extrapolation eтrоr issue in offline MARL, we briefly review the prior single-agent offline RL works here, which can be divided into three categories: dynamic programming. model-based, and safe policy improvement methods.
Dynamic Programming. Policy constraint methods in dynamic programming 20 58 51 are most closely related our work. They attempt to enforce
be close to f under KL-divergence, Wasserstein distance [53), or MMD [47). and then only use actions sampled from in dynamic programming. For example, BCQ [16] constrains the mismatch between the state-action visitation of the policy and the state-action pairs contained in the batch by using a state-condites contte-codiiooeed generative model to produce only previously seen actions. AWR [35] and ABM 42 attempt to estimate the value function of the behavior policy via Monte-Carie or TD(A). Unlike these methods, our algorithm, ICQ, estimates Q-function of the current policy using actions sampled from μ., enabling much more efficient learning. Another series of methods [52 32 33 aim to estimate uncertainty to determine the trustworthiness of a Q-value prediction. However, the high-fidelity requirements for uncertainty estimates limit the performance of algorithms.

---

Average Return
15
Estimated Value
ICQ-MA
20
ICQ-MA (w/o decom)
ICQ-MA (one step)
ICQ-MA Backup)
ICQ-MA (Q(A))
True Value
0
10
20
30
10
30
Thousand Episodes
Thousand Episodes
Performance comparison.
(b) Q-value estimation and True values.
Figure 5: Module ablation study on MMM map.
Model-based and Safe Policy Improvement. Model-based methods [18 50 13 56 19 attempt learn the model from offline data, with minimal modification the algorithm. Nevertheless, modeling MDPs with very high-dimensional image observations and long horizons is a major open problem, which leads limited algorithm performance 24 Besides, safe policy improvement
methods [23] 44 6 [1] require separately estimated model to f to deal with unseen actions.
However, accurately estimating μl especially hard if the data come from multiple sources (29
Experiments
In this section, evaluate ICQ-MA and ICQ multi-agent (StarCraft II) and single-agent (D4RL. offline benchmarks and compare them with state-of-the-art methods. Then, we conduct ablation studies ICQ-MA. We aim to better understand each component's effect and further analyze the main driver for the performance improvement.
6.1 Multi-Agent Offline Tasks on StarCraft II
We first construct the multi-agent offline datasets based maps in StarCraft II (see Table Appendix(E) [E. The datasets are made by collecting DOP (55) training data. All maps share the same reward function, and each map includes 3000 trajectories. We are interested in non-expert data or multi-source data. Therefore, we artificially divide behavior policies into three levels based on the Eb. Then, we evenly mix data of three levels.
average episode return (see Table 3 Appendix
We compare our method against QMIX [39], multi-agent version of BCQ (BCQ-MA), CQL (CQL- MA), and behavior cloning (BC-MA). To maintain consistency, BCQ-MA, CQL-MA, and BC-MA share the same linear value decomposition structure with ICQ-MA. Details for baseline implementa- tions in Appendix D.2 Each algorithm runs with five seeds, where the performance is evaluated ten times every 50 episodes. Details for hyper-parameters are in Appendix
We investigate ICQ-MA's performance compared to common baselines in different scenarios. Results in Figure show that ICQ-MA significantly outperforms baselines and achieves state-of-the-ar performance in all maps. QMIX, BCQ-MA, and CQL-MA have poor performances due to the accumulated extrapolation error. Interestingly, since BC does not depend on the policy evaluation, not subject to extrapolation error. Thus BC-MA has sound performance StarCraft II is near deterministic. We implement BCQ and CQL according to their official code")
6.2 Single-Agent Offline Tasks on D4RL
To compare with current offline methods, evaluate ICQ in the single offline tasks (e.g., D4RL), including gym domains, Adroit tasks (38] and AntMaze. Specifically, adroit tasks require controlling 24-DoF robotic hand to imitate human behavior. AntMaze requires composing parts of sub-optimal trajectories to form more optimal policies for reaching goals on a Muloco Ant robot. Experimental result in [ that ICQ achieves the state-of-the-art performance in many tasks compared with the current offline methods.
"BQQ: https://gihubb.om//ttjinn//////
CQL: CQL.hhg.s/yiibbbboooo//wkmmmmmee

---

6.3 Ablation Study
We conduct ablation studies of ICQ-MA in the MMM map of StarCraft to study the effect of different modules, value estimation, important
and data quality.
Module and Value Estimation Analysis. From Figure 5 find that if we adopt other Q-value
estimation methods in implicit constraint policies (e.g.. Q()) [2 or Tree Backup), the corresponding algorithms (ICQ-MA (Q())) ICQ-MA (Tree Backup)) have poor performances and incorrect estimated values. Suppose we train ICQ-MA without decomposed implicit constraint module (e.g.. ICQ-MA (w /o decom)). In that case, the algorithm's performance is poor, although the estimated value is smaller than the true value, confirming the necessity of decomposed policy. Besides, the performance of one-step estimation (ICQ-MA (one step)) indicates n-step estimation factor for improving ICQ-MA, while one-step estimation will introduce more bias.
the critical
The Parameter a. The Lagrangian coefficient of implicit constraint operator directly affects the intensity of constraint, which a critical parameter for the performance. A smaller a leads relaxing constraint and tends maximize reward. If a learning 157 while a - oc results that ICQ-MA is equivalent to behavior cloning. Indeed, there is an intermediate value that performs best that can best provide the trade-off in Appendix C.4
ICQ-MA is simplified to Q-
Data Quality. It is also worth studying the performance of ICQ-MA and BC-MA with varying data quality, Specifically, we make the datasets from behavior policies of different levels (e.g.. Good, Medium, and Poor). As shown Figure 9 quality, while the performance of BC-MA drops drastically with the data quality deteriorates. Results confirm that ICQ-MA robust to the data quality while BC-MA strongly relies on the data quality.
in Appendix [C.4] ICQ-MA is not sensitive to the data
Computational Complexity. With the same training steps in SMAC, BCQ-MA consumes 70% time of ICQ-MA. Although ICQ-MA takes little long time compared with BCQ-MA, achieves excellent performance in benchmarks. The computing infrastructure for running experiments is server with an AMD EPYC 7702 64-Core Processor CPU.
Conclusion
In this work, demonstrate a critical problem in multi-agent off-policy reinforcement learning with finite data, where it introduces accumulated extrapolation error in the number agents. We empirically show the current offline algorithms Therefore, we propose the Implicit Constraint Q-learning (ICQ) method, which effectively alleviates extrapolation error by only trusting the state-action pairs in datasets. To the best of our knowledge, the multi-agent version of ICQ is the first multi-agent offline algorithm capable of learning from complex multi-agent datasets. Due the importance of offline tasks and multi-agent systems, sincerely hope our algorithms can be solid foothold for applying RL to practical applications.
ineffective in the multi-agent offline setting.
Acknowledgments and Disclosure of Funding
This work was funded by the National Natural Science Foundation of China (ID:U1813216), Na- tional Key Research and Development Project of China under Grant 2017YFC0704100 and Grant 2016YFB0901999 900, in part by the National Natural Science Foundation of China under Grant 61425027, the 111 International Collaboration Program of China under Grant BP2018006, and BNRist Program (BNR2019TDD0100) and the National Innovation Center High Speed Train R&D project (CX/KJ-2020-0006),
We sincerely appreciate reviewers, whose valuable comments have benefited our paper significantly!
10

---

References
[1] Abbas Abdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum a posteriori policy optimisation. In International Conference on Learning Representations, 2018.
[2] Jeffrey L Adler and Victor J Blue. A cooperative multi-agent transportation management and route guidance system. Transportation Research Part C: Emerging Technologies, 10(5-6):433- 454, 2002.
[3] Rishabh Agarwal, Dale Schuurmans, and Mohammad Norouzi. An optimistic perspective on offline reinforcement learning. In International Conference on Machine Leaming, pages 104-114. PMLR, 2020.
[4] Anurag Ajay, Aviral Kumar, Pulkit Agrawal, Sergey Levine, and Ofir Nachum. OPAL: Offline primitive discovery accelerating offline reinforcement learning. International Conference on Learning Representations, 2020.
[5] Kavosh Asadi and Michael L Littman. An alternative softmax operator for reinforcement learning. In International Conference on Machine Learning, pages 243-252. PMLR, 2017.
[6] Felix Berkenkamp, Matteo Turchetta, Angela P Schoellig, and Andreas Krause. Safe model- based reinforcement learning with stability guarantees. arXiv preprint 1rX5v:/705.08555 2017.
[7] Duncan S Callaway and Ian A Hiskens. Achieving controllability of electric loads. Proceedings of the IEEE, 1941):184-199 2010.
[8] Yuanjiang Cao, Xiaocong Chen, Lina Yao, Xianzhi Wang, and Wei Emma Zhang. Adversarial attacks and detection reinforcement learning-basse interactive recommender systems. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1669-1672 1672, 2020.
[9] Axel Dreves, Francisco Facchinei, Christian Kanzow, and Simone Sagratella. On the solution of the KKT conditions of generalized nash equilibrium problems. SIAM Journal on Optimization,
21 1083:1008-, 2011.
[10] Damien Ernst, Pierre Geurts, and Louis Wehenkel. based batch mode reinforcement 556, 2005.
learning. Journal of Machine Learning Research,
[11] Benjamin Eysenbach, Shixiang Gu, Julian Ibarz, and Sergey Levine. Leave trace: Learning to reset for safe and autonomous reinforcement learning. arXiv preprint 0rXiv:1711.06755
2017.
[12] Rasool Fakoor, Pratik Chaudhari, and Alexander J Smola. P3O: Policy-on policy-off policy optimization. In Uncertainty Artificial Intelligence, pages 1017-1027. PMLR, 2020.
[13] Mehrdad Farajtabar, Yinlam Chow, and Mohammad Ghavamzadeh. More robust doubly robust off-policy evaluation. In International Conference on Machine Learning, pages 1447-1456. PMLR, 2018.
[14] Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4RL: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219. 2020.
[15] Scott Fujimoto, Edoardo Conti, Mohammad Ghavamzadeh, and Joelle Pineau, Benchmarking batch deep reinforcement learning algorithms. arXiv preprint
2019. [16] Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International Conference on Machine Learning, pages 2052-2062. PMLR, 2019.
[17] Natasha Jaques, Asma Ghandeharioun, Judy Hanwen Shen, Craig Ferguson, Agata Lapedriza, Noah Jones, Shixiang Gu, and Rosalind Picard. Way off-policy batch deep reinforcement learning of implicit human preferences in dialog. arXiv preprint arXiv: 1907,00450 2019.
[18] Nan Jiang and Lihong Li. Doubly robust off- pof-cy value evaluation for reinforcement learning. In International Conference on Machine Learning, pages 652-661. PMLR, 2016.
[19] Gregory Kahn, Adam Villaflor, Pieter Abbeel, and Sergey Levine. Composable action- conditioned predictors: Flexible off-policy learning for robot navigation. In Conference on Robot Learning, pages 806-816. PMLR, 2018.

---

[20]
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robot Learning. pages 651-673. PMI.R, 2018.
[21] Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off off-policy q-learning via bootstrapping error reduction. In Advances in Neural Information Processing Systems, pages 11784-11794, 2019.
[22]
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative q-learning for offline reinforcement learning, arXiv preprint arXiv:2006. FrX7::2006.04779, 2020.
[23] Romain Laroche, Paul Trichelair, and Remi Tachet Des Combes. Safe policy improvement with baseline bootstrapping. In International Conference on Machine Learning, pages 3652-3661.
PMLR, 2019.
[24] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.0164. 2020.
[25] Chenghao Li, Chengjie Wu, Tonghan Wang, Jun Yang. Qianchuan Zhao, and Chongjie Zhang. Celebrating diversity in shared multi-agent reinforcement learning. arXiv preprint arXiv:2106.0211 02910, 2021.
[26] Xiaoteng Ma. Yiqin Yang. Chenghao Li, Yiwen Lu, Qianchuan Zhao, and Jun Yang. Modeling the interaction between agents in cooperative multi-agent reinforcement learning. In Proceedings of the 20th International Conference on Autonomous Agents and AultiAgent Systems, pages
853 353-861,22 2021.
(27] Rémi Munos. Q()) with off-policy corrections. In Algorithmic Learning Theory: International Conference, ALT 2016, Bari, Italy, October 19-21, 2016, Proceedings, volume 9925, page 305. Springer, 2016.
[28] Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. DualDICE: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems, 22:2318-2328, 2019.
[29] Ashvin Nair, Murtaza Dalal, Abhishek Gupta, and Sergey Levine Accelerating online rein- forcement learning with offline datasets. arXiv preprini arXiv:2006.09339, 2020.
[30] Radford M Neal. Annealed importance sampling. Statistics and computing, 11(2):125-139, 2001.
[31] Frans A Oliehoek, Christopher Amato, et al. A concise introduction decentralized POMDPs, volume 1. Springer, 2016.
[32] Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforce- ment learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 0822-8638, 2018.
[33] Brendan O'Donoghue, Ian Osband, Remi Munos, and Volodymyr Mnih. The uncertainty bellman equation and exploration. In International Conference on Machine Learning, pages 1836-3845, 2018.
[34] Ling Pan, Qingpeng Cai, and Longbo Huang. Softmax deep double deterministic policy gradients. In Advances Neural Information Processing Systems, volume 33, pages 11767- 11777, 2020.
[35] Xue Bin Peng, Aviral Kumar, Grace Zhang, and Sergey Levine. Advintagg-weiighted regression: Simple and scalable off-policy reinforcement learning. arXiv preprint arXiv:1910.00 2019.
[36] Jan Peters, Katharina Mulling, and Yasemin Altun. Relative entropy policy search. In AAAI Conference on Artificial Intelligence, volume 24, 2010.
[37] Michael Rabbat and Robert Nowak. Distributed optimization in sensor networks. In Proceedings of the 3rd international symposium on Information processing in sensor networks, pages 20-27, 2004.
[38] Aravind Rajeswaran, Vikash Kumar, Abhishek Gupta, Giulia Vezzani, John Schulman, Emanuel Todorov, and Sergey Levine. Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. arXiv preprint arXiv: 1709::1709.1088/ 2017.
12

---

[39] Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson, QMIX: Monotonic value function factorisation for deep multi- agget reinforcement learning. In International Conference on Machine Learning, pages -204-4304, 2018.
[40] Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon White- son. The StarCraft multi-agent challenge. In International Conference on Autonomous Agents and Multiagent Systems, pages
2019.
[41] Juan C Santamaria, Richard S Sutton, and Ashwin Ram. Experiments with reinforcement learning in problems with continuous state and action spaces. Adaptive behavior, 6(2):163-217, 1997.
[42] Noah Siegel, Jost Tobias Springenberg, Felix Berkenkamp, Abbas Abdolmaleki, Michael Neunert, Thomas Lampe, Roland Hafner, Nicolas Heess, and Martin Riedmiller. Keep doing what worked: Behavior modelling priors for offline reinforcement learning. In International Conference Learning Representations, 2019.
[43] 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 International Conference on Machine Learning, pages 5887-5896 1896-599,1100 2019.
[44] Aaron Sonabend-V W. Junwei Lu, Leo A Celi, Tianxi Cai, and Peter Szolovits. Expert- supervised reinforcement learning for offline policy learning and evaluation. arXiv preprint MXXiv:2006.33199 2020.
[45] H Francis Song, Abbas Abdolmaleki, Jost Tobias Springenberg, Aidan Clark, Hubert Soyer, Jack W Rae, Seb Noury, Arun Ahuja, Siqi Liu, Dhruva Tirumala, et al. V-mpo: On-policy maximum a posteriori policy optimization for discrete and continuous control. In International Conference on Learning Representations, 2019.
[46] Zhao Song, Ron Parr, and Lawrence Carin. Revisiting the softmax bellman operator: New benefits and new perspective. In International Conference on Machine Learning, pages 5916- 5925. PMLR, 2019.
[47] Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, Gert RG Lanckriet, al. On the empirical estimation of integral probability metrics. Electronic Journal of Statistics, 6: 6:155001599 2012.
[48] Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanetot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. Value- decomposition networks for cooperative multi-agent learning based on team reward. In In- ternational Conference on Autonomous Agents and MultiAgent Systems, pages 2085-2087, 2018.
[49] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
[50] Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforce- ment learning. In International Conference on Machine Learning, pages 2139-2148. PMLR, 2016.
[51] Emanuel Todorov. Linearly-solvable markov decision problems. In Advances in neural information processing systems, pages 1369-1376, 2007.
[52] Ahmed Touati, Harsh Satija, Joshua Romoff, Joelle Pineau, and Pascal Vincent. Randomized value functions via multiplicative normalizing flows. In Uncertainty in Artificial Intelligence pages 422-432. PMLR, 2020.
[53] SS Vallender. Calculation of the wasserstein distance between probability distributions on the line. Theory of Probability & Its Applications, 18(4):784-786, 1974.
[54] Quan Vuong, Yiming Zhang, and Keith W Ross. Supervised policy update for deep reinforce- ment learning. In International Conference on Learning Representations, 2018.
[55] Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. Off-policy multi-agent decomposed policy gradients. arXiv preprint frXiv:2007.12322,, 2020.
13

---

[56]
Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudik. Optimal and adaptive off off-policy evalua- tion in contextual bandits. International Conference on Machine Learning. pages 3589-3597. PMLR, 2017.
[57]
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):77-292, 1992.
[58] Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement
learning. arXiv preprint arXiv:1911.11311, 2019.
[59] Deheng Ye, Zhao Liu, Mingfei Sun, Bei Shi, Peilin Zhao, Hao Wu, Hongsheng Yu, Shaojie Yang. Xipeng Wu, Qingwei Guo, et al. Mastering complex control in MOBA games with deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6672-6679, 2020.
14


Reviews:
[{"review_id": "u7Sen8QrJ6b", "reviewer": "Reviewer_P8yc", "summary": "Summary:\nExtrapolation error is a vital issue in offline reinforcement learning, and this paper addresses its impact and solution on both the single-agent and  multi-agent scenario. The paper analyzed the root cause of extrapolation error with Batch Constrained Q learning as a starting example by analyzing the Bellman-like extrapolation error propagation. The state action transition pairs are divided into seen to unseen, seen to seen, unseen to seen, and unseen to unseen.\nThe authors further showed that the extrapolation error accumulated with the growth of number of agents, both theoretically and with a toy example.\nTo address the issue, the authors proposed a constrained optimization objective where the constraint is KL divergence between the policy to be optimized and the behavioral policy, using this objective, the author derived the off-policy important sampling weight that does not involve the policy to be optimized, and the IS is used to regulate the critic loss, while the actor is learned through the IS weighted log policy probability. Similar to the Q function decomposition in  VDN, the author decompose the extrapolation error and policy agent wise, and use centralized training and decentralized execution. Different from VDN, the author proposed to use a mixture network to generate weight to decompose the Q function, where the weight is also conditioned on state.\n\nThe multi-agent ICQ is evaluated on Starcraft benchmark, and the single agent version is evaluated on the D4RL task. Both seem to gain improved performance compared to baselines.\n\nThe multi-agent ICQ is evaluated on Starcraft benchmark, and the single agent version is evaluated on the D4RL task. Both seem to gain improved performance compared to baselines.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "These issues should be addressed:\n1. In Section 4.2.1, in the inline equation in the second line, what is $o$?\n\n2. In Figure 4, the behavioral cloning overrate the rest of the competitor algorithms except ICQ-MA, which seems to be due to the deterministic nature of the SMAC environment. Thus, the success of ICQ-MA seems to be a weighted loss trading off the behavior cloning error and the implicitly constrained Bellmann error. That means, if ICQ-MA does not exist, behaviorial cloning is the best way to do multi-agent offline RL?\n\n3. I feel there is a lack of explanations to the theorems in the main text, one has to go to the proof to understand what is the intention, although some details can be guessed, but it might be better for them to be elaborated in the main text.\n\n4. The partition function Z is approximated in a min-batch, is there some analysis on the potential effect? How is Z calculated exactly?\n\n5. Eqn (11), the loss is the KL divergence between $\\pi_{k+1}$ and $\\pi_{\\theta}$, taking expectation with respect to the state distribution of the behavior policy, can this be roughly described as making as little change to the current policy?  \n\n\n6. In the derivation of Eqn (11) in step (a), the entropy term of $\\pi_{k+1}$ is dropped in the optimization due to it is not related to $\\theta$, I have not fully understood why this entropy part has no theta involved?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "14"}, "extra_text": {}}, {"review_id": "pMl3h_etUat", "reviewer": "Reviewer_559w", "summary": "The authors propose a new algorithm that investigates centrally trained, decentrally executed coordinated offline multiagent RL (MARL) tasks. The main insight in this papers approach is that in offline MARL, out of distribution errors accumulate exponentially as the number of agents grows and alleviate this issue by only trusting state action pairs in the training dataset (offline trajectories). They first demonstrate the error accumulation theoretically and motivate their Implicit Constraint Q-learning (ICQ) algorithm with the theory. Finally, they show that existing offline RL algorithms fail to scale to the multi-agent setting while ICQ is able to, in addition to improving offline RL in the single-agent setting. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is well-motivated - the problem of offline learning from a static dataset is well known and its challenges have been studied in terms of unseen actions during value-function training. The authors also state in the appendix that the coordinated setting is a limitation, but this is a reasonable starting point for this work. The results and experiments are extensive and very convincing. I also appreciate the simplification of the algorithm over the BCQ baseline, which requires training an additional generative model and perturbation model. The main concern I have is surrounding the clarity. \n\nMy main questions are around the derivation of the forward KL objective. Specifically, I am not clear on what the target of the normalization constant should be. It is also not clear from the B.4 section of the appendix, and I would like to have seen a more detailed derivation from equations 31 to 32. There are other works that derive a policy optimization objective from the forward KL, the partition function is computed by integrating over actions, for example in the M-step of MPO algorithm (Abdolmaleki 2018). In the practical algorithm, this is approximated by sampling several actions for a given state and taking the softmax. In this paper, however, I am not sure what the normalizing constant should be capturing. In the practical algorithm, it seems you are taking a softmax accross the batch dimension as you state, which I interpret as integrating over actions and states. However, the motivation behind this is confusing to me without seeing more detailed steps. Finally, this raises a question for me in terms of the practical consideration of batch-size. I imagine that given the weights are computed as a softmax operation on the minibatch Q-values, this would mean that small batch sizes are preferable for stronger learning signal. It would be interesting to see this explored and/or expanded on. \n\nIf this can be cleared up, I think the experimental results and comparisons to baselines (and even in the single-agent case) makes this a strong paper. \n\nOriginality: This seems novel as far as I know. There are some works that utilize the forward KL in RL whereas most policy gradient objectives can be viewed as derived from the reverse KL. However, this is a specific case of utilizing it in order to avoid sampling from the trained policy for the updates, which seems very clever. Additionally, in the policy update, tuning the alpha parameter between 0 and \\inf interpolates between Q-learning and behavior cloning, but an intermediate value works best for high reward. \n\nQuality: This is a dense paper, but there are several ablation studies and intuitions given for the implementation details. The experiments on the multi-agent settings are especially extensive and impressive. \n\nClarity: See above. \n\nSignificance: Offline RL is an important topic in RL, and that this is able to outperform existing baselines in the single agent case is already impressive to see. The significance is greatly improved given the results in the multi agent settings. \n\nMisc: minor typo - the perturbation model takes tau' instead of tau in the Bellman target. Also, CQL (Conservative Q-Learning for Offline RL) is not cited but used as a baseline. I would also discuss how this is a much simpler version of the existing methods, namely CQL and BCQ. Effectively, by applying the constraint implicitly, the authors avoid an additional regularization term (as most offline RL papers use to enforce similarity to the behavior policy) or even training a separate network as BCQ does.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are addressed in the appendix. It is fairly comprehensive there and does not take away from the papers contributions. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "6IXqqNyNeam", "reviewer": "Reviewer_icWA", "summary": " \nThe paper focuses on the distribution shift issue of offline RL in multi-agent systems. It is an important problem because 1. Offline RL trains on a fixed dataset and thus is hard correct the overestimation error of the Q function on unseen (s,a) pairs. 2. Offline RL multi-agent environment is an under-explored area. \n \nThe paper first proved that under some assumptions (including 1. all agents share the same reward function. 2. the joint value function can be decomposed into value functions across agents) the extrapolation error grows linearly with the number of players. Current SOTA offline RL methods such as BCQ is shown to perform poorly under this setup.\n \nThe authors proposed ICQ, a general offline RL algorithm that only trusts the (s,a,r,s’,a’) pairs from the collected data and uses an estimation of the importance sampling ratio to learn the Q value of the policy under training. They then extends ICQ to the multi-agent setting (ICQ-MA). The algorithms are evaluated first on a toy tabular multiplayer environment, then on several StarCraftII two-player mini-games and on the single-agent D4RL tasks. The experiments showed that ICQ and ICQ-MA do not suffer from exploding Q values and overestimation. It outperforms other Offline RL and Off-policy RL baselines.\n\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": " \nThe proposed method ICQ for single-agent RL bears some resemblance to AWR and the main novelty comes from the critic loss, where the target Q(s’, a’) is reweighed by the importance sampling weight. The paper had a good theoretical analysis of most of the claims it made. The experiments clearly shows that the proposed method ICQ and ICQ-MA does not suffer from Q function over-estimation problem. \n \nThis paper contains several strong aspects. The usage of the importance sampling ratio in the update of the Q function is novel afaik. The intersection of Offline RL and Multi-agent RL is novel and deserves more consideration. And the long standing problem of value overestimation can benefit from the contributions of this paper. The experimental and the ablation study results look sound -- starting with a toy environment as a motivation, then moving on to more complicated benchmarks.\n \nOne major point that was unclear was whether ICQ should be solely used in a multi-agent env, or does the method work equally well in a single-agent env. More specifically, In l127, you mentioned that the unseen (s,a) pairs grow exponentially with the number of agents. Is that because the amount of data collected is held fixed while the joint action space A of all of the agents increases exponentially with the number of agents? If so, I wonder whether the better performance is because ICQ is better than BCQ at handling additional dimensionality in the state-action space, or because it is better at multi-agent data specifically. I imagine a relatively straightforward way to test this is to hold the dimensionality of (s,a) constant by add dummy observation dimensions to the two-agent toy env and compare two-agent+dummy v.s. four-agent. \n \n \nAdditionally, I am uncertain around the following points\n \n1. In l87, what is $Q^\\pi_B$ exactly? Is that just the expected value of $r + Q(s’, a’)$ over the batch of $(s,a,r,s’)$ and $a’\\sim\\pi(s,a)$? Or is that what $Q^\\pi$ converges to when only using data from B?\n2. In l96 around the fixed additional error. Do you assume here that seen pairs will have an exact estimate and 0 or close to 0 error?\n3. In l56, it is not immediately obvious what does “all agents share the same reward function” may imply. Does that restrict us to a cooperative environment? Because the given reward function is a function of the env state, not the agent’s observation. I think you may have meant the latter.\n\n\nOther suggestions for better readability/clarity: \n1. In the paper, it is not clear that the optimal policy in eq 8 is already proposed in AWR (Peng et al. 2019). \n2. L31-32  “unseen state-action pairs will grow exponentially as the number of agents increases in multi-agent systems” It is not immediately clear why it is exponential and I think it’s only mentioned once in l127. You’ve shown that the error grows linearly with the number of agents in Theorem 2. It might be more clear if you drop the exponential part.\n3. In 6.1 you mentioned that StarCraft II is deterministic. That is in fact not the case. See [this link](https://github.com/deepmind/pysc2/blob/master/docs/environment.md#determinism-and-randomness)\n4. In 6.1 and elsewhere, it is unclear from the paper whether a) the paper tested its agents on the full StarCraft II game or specialized maps; b) whether the environment is two-player or 2+; c) whether the goal is competitive or cooperative.  That information is available in the DOP, but is worth specifying again for the readers unfamiliar with that work or with StarCraft. \n5. There is a typo in l104 I believe. Did you mean “by optimizing $\\pi(a'_u | s'_s)$”?\n\n-------Updated review----\n\nAfter the rebuttal, the author added results for the single agent use cases, which makes the proposed algorithm (ICQ) applicable to more domains beyond the multi-agent use case. The authors also improved the clarity of the paper and added discussions around the pros and cons of ICQ. The changes made the paper stronger and thus merit a re-evaluation of the score. I’ve changed my ratings accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "A missing part to the discussion is the strength and the weakness of the algorithm. The authors only discussed the tradeoff between higher training cost and better performance.  It would benefit the readers to have more discussion for the question: should we all stop using AWR, BCQ, and BC in favor of ICQ?", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "3hW_Dpfxk9q", "reviewer": "Reviewer_uost", "summary": "This paper tackles the problem of offline multi-agent reinforcement learning (MARL). The relation between extrapolation error and transition probabilities of unseen states is first derived for the single-agent case. It is then extended to the paradigm of centralized training with decentralized execution (CTDE) in MARL, under the assumption of a linear decomposition of the joint action-value function, such as in methods like Value Decomposition Networks. The derived relations motivate the idea of setting the action probabilities of unseen actions at unseen states to be zero. In contrast to previous work, the proposed method called \"ICQ\" uses the KKT conditions to reformulate the constrained optimization viewpoint of offline RL, so that unseen state-action pairs are not used in the loss function. This single-agent result is again extended to MARL with linear decomposition of the joint action-value function. Convergence is shown for the finite case. Experiments on a finite synthetic game and the high-dimensional StarCraft II micromanagement environment show that ICQ outperforms the multi-agent extensions of existing single-agent methods, while ablations show that various design choices are necessary for performance. The single-agent version of ICQ is shown to meet or exceed baselines in single-agent environments.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the proposed method is well-motivated by theoretical results and appears to have strong experimental evidence, but there is a concern about experimental protocol and there are various claims that need more justification and clarification.\n\nThe proposed reformulation of offline RL using the viewpoint of convex optimization appears to be novel, given the accuracy of the summary of related work. This motivates the proposed method, ICQ, to avoid the use of unseen state-action pairs, which would have contributed to error in previous methods. The improvement due to avoiding the use of unseen pairs is shown in a didactic finite game, and further validated in higher dimensional environments.\n\nTheorems 1 and 2 are useful for motivating the method. I am slightly concerned about the author's claim in line 165 that the importance sampling weight does not involve $\\pi$. How can $Q^{\\pi_k}$ in equation (9) be accurately estimated if not all possible state-action pairs, which involves unseen pairs, are used? This doesn't seem to be a serious issue because $Q^{\\pi_k}$ is evaluated only under the behavioral distribution when it appears in equation (11). Nonetheless, the authors may wish to rephrase line 165.\n\nLines 30-32 says \"we demonstrate that unseen state-action pairs will grow exponentially as the number of agents increases...\". Where does this paper demonstrate it? The exponential growth is obvious and I don't think it needs justification, but I didn't see the \"demonstration\" anywhere in the paper (the 2-state game in Figure 1 is just an example). The phrasing makes it seem that the authors are claiming something more than this obvious fact, but I don't think that's the case, so I recommend rewording it.\n\nLine 76-77: it's not clear what is the exact operation that \"mask\" means. Does BCQ avoid using unseen pairs by \"masking\" (i.e. setting to those Q values to zero)? If so, how is that fundamentally different from the way ICQ avoids using unseen pairs?\n\nIn line 95-96, how is $\\epsilon_b$ different from $\\epsilon_u$? Are they actually the same? Are you saying that $\\epsilon_s$ for seen pairs is set to zero? This is confusing.\n\nLine 162-163: computing the partition function in ICQ seems to be a hard subtask. How is this tractable for continuous state and continuous action spaces?\n\nLine 184: Does $n$-step evaluation strictly lead to zero bias, i.e. \"eliminate\", as the paper says?\n\nLine 228-231: Since this paper does not compare with the methods AWR and ABM, how can the authors claim that their method has \"much more efficient learning\"?\n\nI am concerned about the experimental protocol. In section 6.1, the paper says that the hyperparameters for the baseline methods BCQ and CQL were taken from those that the original papers provided. Were the hyperparameters of BCQ and CQL already tuned for StarCraft II? If not, and if this paper did not tune the baselines for the tasks used in this paper, then the comparisons are not fair. Could the authors address this issue?\n\nThe organization of the paper needs improvement. Section 3.2 Toy Example compares the proposed method ICQ with the baseline BCQ, but ICQ hasn't even been described yet.\n\nMinor comments:\n1. The acronym \"MMDP\" first occurs in Figure 1 without saying what it stands for.\n2. Line 126: \"QMIX\" appears for the first time here without saying what it stands for, and without a citation to the QMIX paper.\n\n-----------------------------------------------------------------------------\nAfter rebuttal: the authors have addressed all of my original questions and have promised to update the paper with extra experimental results and explanations based on the discussion during this review process, so I am raising the score from 6 to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations were placed in supplementary material, which was not reviewed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses the problem of offline multi-agent reinforcement learning (MARL) and identifies a key challenge in that the accumulated extrapolation error increases with the number of agents. The authors propose a principled approach to address this problem, based on the idea of constraining Q-value estimations to only "seen" state-action pairs observed in the offline data. The approach is well motivated conceptually and shows strong empirical performance, detailed ablations provide deeper insights.

Initial reviews of this paper were positive about the originality of the proposed approach and its strong grounding in the theoretical analysis, in addition to the strong empirical results. Several aspects required clarification, including notation, interpretation of loss terms / derivation of the KL objective. Reviewers suggested several readability improvements. Finally there were questions on whether the approach would be expected to only improve performance on multi-agent tasks, or if improvements could also be expected in single-agent settings.

The authors provided detailed responses to clarification questions and committed to incorporating readability and other improvements in the next version of the paper. They also provided substantial additional empirical evidence for single agent tasks. In the follow up discussion, all reviewers indicated they were satisfied with the responses, and confident that the authors would be able to incorporate the suggestions into the camera ready version. Some reviewers raised their scores, resulting in a consensus recommendation to accept the paper.

The AC recommends acceptance as a spotlight paper, based on the strong theoretical insight and empirical results, as well as the timeliness of this work's focus on multi-agent and offline RL settings.
Decision: Accept (Spotlight)