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., BatchhConsttained 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 (26) 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',a 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 μ 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 Ticq 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 a 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 TogTi 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)
Σ (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
Σ F
π arg max
(17)
('(Tt)
x "5..7
where (TT)) = Eas 1s (a(aa exp ( ( (T' aa))
is the normalizing partition function.
The decomposed multi-age 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 (')) (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(A) [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,
(TA))' (rr (1 a.+1) - Q(T,, ai)) 22
(20)
where P(T,, az) ((. exp( Q(T., a.)) 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 on 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 /00.v0/9900004555 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. PrX7::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,1111 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)277-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": "usfZ1yfTuLP", "reviewer": "Reviewer_5dG2", "summary": "The paper proposes ICQ, a batch RL method which is a modification of BCQ with an update rule that uses only the state-action pairs present in the dataset to fight overestimation error. It can be seen as performing constrained optimization to keep the learned policy close to the behavior policy in KL space.\n\nThe authors use their method in the multi-agent context, and show that as the number of agents grows, the extrapolation error grows exponentially if one doesn't control transition probabilities from seen to unseen pairs. An example of an MDP where BCQ's error grows exponentially is shown.\n\nUsing a technique similar to Value-Decomposition Networks (Sunehag et al., 2017), authors extend their method to the case of collaborative, multi-agent batch RL.\nThe method is tested on D4RL: standard single agent batch RL tasks, and Starcraft II for multi-agent evaluation.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "1. A big part of the paper is the introduction of the Implicit Constraint. The constraint itself is very similar to the one proposed in [Ghasemipour et al. (2020)](https://arxiv.org/abs/2007.11091) (EMaQ), which uses this update rule:\n$$TQ := r + \\gamma \\mathbb{E}_{s'} \\mathbb{E}\\_{a^\\prime\\sim \\mu} \\big[\\text{max}\\_{a'\\in \\text{dataset}} Q(s', a') \\big] $$\nIt feels necessary for the authors to compare ICQ to EMaQ in the text and in the experiments.\n2. In particular, I think EMaQ ablates against the exact version of IC in Appendix J. Comparison with Softmax Backup Operators, claiming superior performance of EMaQ. It would be useful if authors clarified differences between these two methods, if any.\n3. The single-agent results are presented on little tasks (7, with one difficulty (based on the quality of the behavior's policy) version each, compared to 45 in CQL or 25 in EMaQ).\n4. The presentation of results on a plot only, as opposed to a table makes it hard to compare with results reported by other papers, but it looks that at least authors' implementation of CQL doesn't reproduce the scores claimed by CQL's authors.\n5. In a number of domains performance of ICQ tracks BC, suggesting that either the domains are too simple, or the performance isn't very impressive.\n\nAssuming that the method of IC was indeed known in the community, the only methodical novelty that the paper presents is the use of VDNs to the case of multi-agent batch RL. The level of innovation there is limited, as the modification of BCQ, etc. is a relatively straightforward application of the ideas from VDN. Given also limited single-agent results and non-comprehensive experiment suite, I suggest rejection.\n\nMinor comments:\n- 24: \"the accurately estimated values\"\n- 111: \"Let us define\"\n- 128: \"We control... in different datasets to be equal\"\n- It would be worthwhile to try to bring Fig 4 and 5 closer to the place where they are referred to.\n\nedit: increasing time spent and score to 5 after authors included results on more domains and re-validated previous results of CQL.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "pC-oLnrsbS1", "reviewer": "Reviewer_Rr7B", "summary": "This work addresses the problem of reducing the error incurred by unseen state-action pairs in offline reinforcement learning. They additionally show that in multiagent reinforcement learning settings this error grows exponentially in the number of agents in the system. To remedy this problem, they introduce a new algorithm Implicit Constraint Q-Learning (ICQ) that modifies the expected Bellman update with importance sampling to remove the dependence on the current policy and behaviour policy. The update now need not consider actions not existing in the dataset that were previously considered when calculating the importance sampling ratio. The authors demonstrate this method in both the single- and multi-agent scenario, and include a brief ablation study. ", "questions": "", "limitations": "", "rating": 5, "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 work tackles an important problem in reinforcement learning: how to learn in the offline reinforcement learning setting. The key insight in this work is to separate the controllable error, resulting from the seen state-action pairs existing in the dataset, from the uncontrollable error, resulting from unseen state-action pairs. They provide an interesting theoretical analysis of this insight and its implications in Q-learning (Thm 1). \n\nHowever, past this point the manuscript does not seem to have a straightforward story to follow. I believe this is due to the fact that the paper motivates itself with an issue particular to multiagent RL (combinatorial explosion of unseen state-action pairs of data growing in the number of agents) but does not directly address this issue. Instead, focuses on the related single-agent RL problem of a single agent’s unseen state-action pairs. This subtle distinction in problem statements forgoes consideration of the increasing number of other-agents, nor considers methods that can leverage known components of the game to reduce said complexity (e.g., consider roles for agents, we can now reuse unseen state-action pairs within agents of the same role). As a result of trying to build a narrative that misses this point, the authors need to introduce ideas in a counter-intuitive ordering that is difficult to follow. \n\nIn regards to their previous ICML reviews:\nThe inclusion of the code in the submission improves the ability to reproduce their results. The paper itself is still not detailed enough to reimplement their performance. I would encourage the authors also to include their offline datasets and saved final policies in the code release. \nThe inclusion of the ablation study in Sec 6.3 greatly enhances the understanding of the contributions of each modification to the downstream performance. \nSingle-agent tasks results are provided but are effectively a footnote and not discussed. \n\nIn summary, I think there are several interesting ideas within this paper. Despite this, I think the primary focus of this work should be on the single-agent setting so that the main contribution of this paper, ICQ, can be studied in more depth. The extension of ICQ into multiagent settings should be left as a follow-up work, and focus study on modifications that incorporate the multiagent aspect of the problem. \n\n\nMajor Comments (affecting review score): \n\n - The organization of the paper is difficult to follow and should be revised. Examples: (a) Sec 3.2 introduces a toy example studying the differences between BCQ and ICQ however ICQ is not introduced at all at this point. (b) Sec 4.2, the need for the two new proposed extensions is not clearly motivated; moreover, Sec 4.2.1 appears again to be a single-agent algorithm instead of a multiagent algorithm. (c) the experimental results do not follow the logical order of complexity that was introduced in the methodology section.\n\n - Single-agent claimed results do not follow from the provided results and are not discussed. Sec 6.2 claims a comparison that across a large variety of offline tasks (L269-270) in the single-agent setting ICQ significantly outperforms baselines. Despite this, only four environments results are shown in Figure 5, and the claimed result difference is not demonstrated as statistically significant nor does it appear to be a large (or small in some cases) improvement upon inspection of the graphs. The authors should either remove the claim of significance or provide the corresponding statistical tests. Moreover, more analysis in the single-agent setting would be beneficial. Perhaps providing breakdowns across seen and unseen transitions? \n\n - Unsupported claims and lacking baselines in multi-agent tasks. The dataset that the offline agents are trained with is generated from DOP, this algorithm’s performance should be included in the results. This provides a baseline for the performance of independent RL and contextualizes the quality of the behaviour cloning algorithms. It is surprising to see that a suite of different baselines are all underperforming compared to behaviour cloning. This raises suspicion of the quality of the reproduction of these algorithms. Do the authors reuse the same codebase as the source algorithms and match the performance they report on their experiments? Currently the authors claim this is a result of the extrapolation error; however, the reward curves provided offer no indication as to the source of the error. Additional analysis is necessary to support this claim.\n\nMinor Comments (not affecting review score):\n\n- It would be advantageous if the authors could formally relate their ICQ algorithm’s error (Sec 4.1) with the error components introduced in Sec 3. \n\n- Sec 2, L73: it would be helpful to explain the perturbation model and its connection to ICQ. \n\n- Sec 3, L94-96: it’s not clear how e_u and e_b are able to be disentangled. Additional discussion would be helpful. \n\n- Sec 3.2, L122: “The optimal policy is all agents…”, this is not the optimal policy, but a particular equilibrium. Each agent’s optimal policy is to select A(1). \n\n- Sec 4.1, L145: Have you considered using a greedy Bellman update as opposed to the expected Bellman update?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I suggest the authors include a discussion about the impact of the large behavioural bias that is introduced as a result of trajectories mimicked in the offline dataset. Additional discussion as to how ICQ might influence this problem would be helpful.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "oXY1kA7eo3B", "reviewer": "Reviewer_xr9t", "summary": "This paper studies offline RL in multi-agent setting. The analysis shows that when the number of agents increases, the extrapolation error would increase. To alleviate this issue, the authors propose a method called Implicit Contraint Q learning (ICQ) that learns Q value while contraining the policy to be close to what have been seen in the dataset. Experimental results show that in MARL setting, the proposed method outperforms baselines such as MA-CQL and MA-BCQ. In the single-agent setting, the results seem comparable to the previous method.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper follows a popular intuition \"conservatism\" in this area. While this general idea has been explored many times, they are the first to work in multi-agent setting. \n\nThe paper is not well-written.  I believe they did not differentiate or clarify their key difference from past work such as CQL and MOPO [2]. Both of these works are doing \"believe what you have seen\" to some extend. Why do they fail in MARL setting but ICQ succeeds? \nThe toy example is great for understanding the error. But a comparison between ICQ and CQL would be great on that.  \n\nThe lack of improvements in the D4RL setting is surprising. A more detailed analysis should be made and some qualitative evidence can be useful for understanding the difference between D4RL and your MA environments.\n\nCan you specify the reason for the MA environments? There are multiple options from starcraft minigames. \n\nI think I would consider changing the score if you could run baselines properly and show that they match the performance in the original paper. \n\nMany typos such as \"find-tuned\" need to be adjusted.\n\n\n[1] Kumar, Aviral, et al. \"Conservative q-learning for offline reinforcement learning.\" arXiv preprint arXiv:2006.04779 (2020).\n[2] Yu, Tianhe, et al. \"Mopo: Model-based offline policy optimization.\" arXiv preprint arXiv:2005.13239 (2020).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Experimental results seem a bit unconvincing for CQL is significantly lower than BCQ in D4RL envs. This is not consistent with the reported results in the original paper. If baselines are not well implemented, it weakens the quality of the paper directly. Can you compare your results with the original paper and show they are comparable (no need to be the same)? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "KuAkPzWDOXP", "reviewer": "Reviewer_xuSQ", "summary": "The main contribution of the paper is to investigate multi-agent offline RL settings and highlighting the additional challenges in this settings compared to single-agent offline RL. Moreover, the paper proposes ICQ for offline RL, which combines importance sampling based off-policy approach with KL-constraint. ICQ empirically leads to good performance on challenging multi-agent offline tasks (StarCraft II) where existing offline RL approaches are reported to fail.", "questions": "", "limitations": "", "rating": 6, "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": "**Originality**: The submission seems to explore multi-agent settings for offline RL which haven't received much attention from the community. Furthermore, exponential error increase with the number of agents seem to be an insightful observation. That said, the proposed method ICQ, seems to fall under the broad category of methods which apply KL-divergence constraints, which has also been applied in the context of offline RL, including BRAC[1] and KL-control [2]. \n\n**Quality**: The submission seems to be theoretically sound as well as the claims seem to be supported by theoretical justifications in tabular settings (albeit with simplified assumptions). However, it is unclear to me whether the comparison to other methods is fair. I have some questions regarding the empirical section :\n- How were the hyperparameters selected for the baselines vs ICQ? It seems the hparams correspond to the default value used in prior work but those values correspond to different set of tasks.\n- Why is the reported CQL performance so poor on the D4RL tasks -- CQL was claimed to be much better than BCQ on a variety of D4RL tasks including AntMaze and Kitchen tasks. This seems to indicate either a bug in the CQL implementation or a poor selection of hyperparameters.\n- Since BRAC and KL-control are more closer to ICQ, could the authors elaborate on their choice to instead use BCQ as their baseline?\n- What if I had a dataset only containing just poor/medium performance behavior policies only? This experiment might empirically address the limitation of using importance sampling in ICQ (see limitation section below).\n\n\n**Clarity**: This paper as written currently is often not easy to parse and could be improved. \n- One major issue that sufficient intuition is not provided to the reader before the theoretical results are presented, for example, what are the implications of Theorem 1 and 2? Why would standard offline RL approaches are expected to fail in lieu of Theorem 2?\n- While I appreciate the details of derivation included in section 4.1 for the loss function, these details make it harder to read that section and could be presented more clearly.  One would be to work backwards from the final loss to its derivation, so that the reader is aware of what is being derived. Same issue exists with Theorem 4.\n\n**Significance**: It is likely that this paper might generate more interest in the multi-agent offline RL settings. It is hard to say if future work would build on top of ICQ as it is unclear if the baselines were implemented correctly and the comparisons were fair. \n\n\n\n[1] Wu, Yifan, George Tucker, and Ofir Nachum. \"Behavior regularized offline reinforcement learning.\" arXiv preprint arXiv:1911.11361 (2019).\n\n[2] Jaques, Natasha, et al. \"Way off-policy batch deep reinforcement learning of implicit human preferences in dialog.\" arXiv preprint arXiv:1907.00456 (2019).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Importance sampling based approaches are known to be fragile especially in the cases when the distribution of the learned policy is very different from the behavior (or data) distribution. I expect ICQ to suffer from similar issues and request the authors to clarify if they think otherwise. For example, [1] argues that he maximum improvement that can be reliably obtained via importance sampling is limited by (i) the suboptimality of the behavior policy; (ii) the dimensionality of the state and action space; (iii) the effective horizon of the task.  See the discussion in [1] for more details.\n\nAppendix F does a good job at mentioning other limitations in the appendix.\n\n[1] Levine, Sergey, et al. \"Offline reinforcement learning: Tutorial, review, and perspectives on open problems.\" arXiv preprint arXiv:2005.01643 (2020).\n\n--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n*Update*: Based on author response, I weakly recommend acceptance (updating my score to 6) despite the poor clarity of the initial version of the paper. I strongly advise the authors to revise the paper to clarify the relationship to BRAC and KL-control, include additional experiments on harder D4RL tasks, fixing results for their CQL baselines (mention of hyperparameter sensitivity of CQL) and a more thorough discussions of the limitations (including the ones pointed by xuSQ in their response).", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In the light of authors' response and additional experiments, some of the reviewers decided to increase their score but they are of the opinion that the paper could be improved in terms of presentation clarify. The additional results provide extra evidence for the method but they require a set of further edits which warrant another round of reviews. In addition, some of the reviewers are not fully convinced by the interpretation of the results by the authors. I suggest that the authors address the reviewers' points, include the extra results and improve the presentation of the paper and resubmit. 
Decision: Accept (Spotlight)