Year: 2021

Abstract:
In many real-world multi-agent cooperative tasks, due to high cost and risk, agents cannot continuously interact with the environment and collect experiences during learning, but have to learn from offline datasets. However, the transition probabilities calculated from the dataset can be much different from the transition probabilities induced by the learned policies of other agents, creating large errors in value estimates. Moreover, the experience distributions of agents’ datasets may vary wildly due to diverse behavior policies, causing large difference in value estimates between agents. Consequently, agents will learn uncoordinated suboptimal policies. In this paper, we propose MABCQ, which exploits value deviation and transition normalization to modify the transition probabilities. Value deviation optimistically increases the transition probabilities of high-value next states, and transition normalization normalizes the biased transition probabilities of next states. They together encourage agents to discover potential optimal and coordinated policies. Mathematically, we prove the convergence of Q-learning under the non-stationary transition probabilities after modification. Empirically, we show that MABCQ greatly outperforms baselines and reduces the difference in value estimates between agents.

heading: 1 INTRODUCTION
text: In multi-agent cooperative tasks, agents learn from the experiences generated by continuously interacting with the environment to maximize the cumulative shared reward. Recently, multi-agent reinforcement learning (MARL) has been applied to real-world cooperative systems (Bhalla et al., 2020; Xu et al., 2021). However, in many industrial applications, continuously interacting with the environment and collecting the experiences during learning is costly, risky, and time-consuming. One way to address this is offline RL, where the agent can only access a fixed dataset of experiences and learn the policy without further interacting with the environment. However, in multi-agent environments, the dataset of each agent is often pre-collected individually by different behavior policies, which are not necessary to be expert, and each dataset contains the individual action of the agent instead of the joint action of all agents, e.g., autonomous driving dataset. Therefore, the dataset does not satisfy the paradigm of centralized training, and the agent has to learn the coordinated policy in an offline and fully decentralized way.
The main challenge of offline RL is the extrapolation error, an error in value estimate incurred by the mismatch between the experience distributions of the learned policy and the dataset (Fujimoto et al., 2019), e.g., the distance of the learned action distribution to the behavior action distribution, and the bias of the transition dynamics estimated from the dataset to the true transition dynamics. Recently, almost all offline RL methods (Fujimoto et al., 2019; Levine et al., 2020; Jaques et al., 2019) focus on constraining the learned policy to be close to the behavior policy to avoid the overestimate of the values of out-of-distribution actions, but ignore to correct the transition bias since the deviation of estimated transition dynamics would not be too large if the single-agent environment is stationary.
However, in decentralized multi-agent environments, from the perspective of each agent, other agents are a part of the environment, and the transition dynamics experienced by each agent depend on the policies of other agents. Even in a stationary environment, the experienced transition dynamics of each agent will change as other agents update their policies (Foerster et al., 2017). Since the behavior policies of other agents would be inconsistent with their learned policies which
are unknowable in decentralized multi-agent environments, the transition dynamics estimated from the dataset by each agent would be different from the transition dynamics induced by the learned policies of other agents, causing large errors in value estimates. The extrapolation error would lead to suboptimal policies. Moreover, trained on different distributions of experiences collected by various behavior policies, the estimated values of the same state might be much different between agents, which causes that the learned policies cannot coordinate with each other.
To overcome the suboptimum and miscoordination caused by transition bias in decentralized learning, we introduce value deviation and transition normalization to deliberately modify the estimated transition probabilities from the dataset. During data collection, if one agent takes an optimal action while other agents take suboptimal actions at a state, the transition probabilities of low-value next states will become large. Thus, the Q-value of the optimal action will be underestimated, and the agents will fall into suboptimum. Since the other agents are also trained, the learned policies of other agents would become better than the behavior policies. For each agent, the transition probabilities of high-value next states induced by the learned policies would be larger than those estimated from the dataset. Therefore, we let each agent be optimistic toward other agents and multiply the transition probabilities by the deviation of the value of next state from the expected value over all next states, to make the estimated transition probabilities close to the transition probabilities induced by the learned policies of other agents.
Value deviation could decrease the extrapolation error and help the agents escape from the suboptimum. However, in some cases, the behavior policies of other agents might be highly deterministic, which makes the distribution of experiences unbalanced. If the transition probabilities of high-value next states are extremely low, value deviation may not remedy the underestimate. Moreover, due to the diversity in experience distributions of agents, the value of the same state might be overestimated by some agents while underestimated by others, which results in miscoordination of the learned policies. To address these two problems, we normalize the transition probability estimated from the dataset to be uniform. Transition normalization balances the extremely biased distribution of experiences and builds the consensus about value estimate. By combining value deviation and transition normalization, the agents would learn high-performing and coordinated policies in an offline and fully decentralized way.
Although value deviation and transition normalization make transition dynamics non-stationary, we mathematically prove the convergence of Q-learning under such non-stationary transition dynamics. By importance sampling, value deviation and transition normalization take effect only as the weights of the objective function, which makes our method easy to implement. We instantiate the proposed method on BCQ, termed MABCQ, to additionally avoid out-of-distribution actions. Nevertheless, it can also be implemented on other offline RL methods. We build the offline datasets and evaluate MABCQ in four multi-agent mujoco scenarios (Todorov et al., 2012). Experimental results show that MABCQ greatly outperforms BCQ, and ablation studies demonstrate the effectiveness of value deviation and transition normalization. To the best of our knowledge, MABCQ is the first method for offline and fully decentralized multi-agent reinforcement learning.

heading: 2 RELATED WORK
text: MARL. Many MARL methods have been proposed for learning to solve cooperative tasks in an online manner. Some methods (Lowe et al., 2017; Foerster et al., 2018; Iqbal & Sha, 2019) extend policy gradient into multi-agent cases. Value factorization methods (Sunehag et al., 2018; Rashid et al., 2018; Son et al., 2019) decompose the joint value function into individual value functions. Communication methods (Das et al., 2019; Ding et al., 2020) share information between agents for better cooperation. All these methods follow centralized learning and decentralized execution, where the agents could access the information from other agents during centralized training. However, in our offline and decentralized setting, the datasets of agents are different; each dataset contains individual actions instead of joint actions; and the agents cannot be trained in a centralized way.
For decentralized learning, the key challenge is the obsolete experiences in replay buffer. Fingerprints (Foerster et al., 2017) deals with obsolete experience problems by conditioning the value function on a fingerprint that disambiguates the age of the sampled data. Lenient-DQN (Palmer et al., 2018) extends the leniency concept and introduces optimism in the value function update by forgiving suboptimal actions. Concurrent experience replay (Omidshafiei et al., 2017) induces cor-
relations in local policy updates, making agents tend to converge to the same equilibrium. However, these methods require additional information, e.g., training iteration number, exploration rate, and timestamp, which often are not provided by the offline dataset.
Offline RL. Offline RL requires the agent to learn from a fixed batch of data {(s, a, s′, r)}, consisting of single-step transitions without exploration. Unlike imitation learning, offline RL does not assume that the offline data is provided by a high-performing expert but has to handle the data generated by suboptimal or multi-modal behavior policies. Most offline RL methods consider the out-of-distribution action (Levine et al., 2020) as the fundamental challenge, which is the main cause of the extrapolation error (Fujimoto et al., 2019) in value estimate in the single-agent environment. To minimize the extrapolation error, some recent methods introduce constraints to enforce the learned policy to be close to the behavior policy, which could be direct action constraint (Fujimoto et al., 2019), kernel MMD (Kumar et al., 2019), Wasserstein distance (Wu et al., 2019), and KL divergence (Peng et al., 2019). Some methods train a Q-function pessimistic to out-of-distribution actions to avoid overestimation by adding a reward penalty quantified by the learned environment model (Yu et al., 2020), by minimizing the Q-values of out-of-distribution actions (Kumar et al., 2020; Yu et al., 2021), or by weighting the update of Q-function via Monte Carlo dropout (Wu et al., 2021). A finite-sample analysis for offline MARL (Zhang et al., 2018) has been studied, but the agents are assumed to get individual rewards instead of the shared reward, and be connected by communication networks, which is not the fully decentralized setting. All these methods do not consider the extrapolation error introduced by the transition bias, which is a fatal problem in offline and decentralized MARL.

heading: 3 METHOD

heading: 3.1 PRELIMINARIES
text: We consider N agents in multi-agent MDP (Oliehoek & Amato, 2016) Menv =< S,A, R, Penv, γ > with the state space S and the joint action space A. At each timestep, each agent i gets state s and performs an individual action ai, and the environment transitions to the next state s′ by taking the joint action ~a with the transition probability Penv (s′|s,~a). The agents would get a shared reward r = R (s), which is simplified to just depending on state (Schulman et al., 2015). The agents learn to maximize the expected return E ∑T t=0 γ
trt, where γ is a discount factor and T is the time horizon of the episode. However, in the fully decentralized learning, Menv is partially observable to the agent since the agent cannot observe the joint action ~a. During execution, from the perspective of each agent i, there is a viewed MDP MEi =< S,Ai, R, PEi , γ > with the individual action space Ai and the transition probability
PEi (s ′|s, ai) = ∑ ~a−i Penv (s ′|s,~a) N∏ j 6=i πj(aj |s),
where ~a−i denotes the joint action of all agents except agent i, and π denotes the policy of the agent. As the transition probability depends on the policies of other agents, if other agents are also updating their policies, PEi becomes non-stationary. Moreover, if the agent cannot interact with the environment, PEi is unknown. Since we only investigate the influence of other agents’ policies on PEi , we assume Penv to be deterministic.
In offline and decentralized settings, each agent i could only access a fixed offline dataset Bi, which is pre-collected by behavior policies and contains the tuples (s, ai, r, s′). As defined in BCQ (Fujimoto et al., 2019), the visible MDP MBi =< S,Ai, R, PBi , γ > is constructed on Bi, which has the transition probability1
PBi (s ′|s, ai) =
num(s, ai, s ′)∑
ŝ′ num(s, ai, ŝ ′) ,
where num(s, ai, s′) is the number of times the tuple (s, ai, s′) is observed in Bi. However, since the learned policies of other agents might be greatly different from the behavior policies, PBi would be biased from PEi , which creates large extrapolation errors and differences in value estimates between agents, and eventually leads to uncoordinated suboptimal policies.
1The transition probability in the following sections means the one calculated from Bi unless otherwise stated.
To intuitively illustrate the miscoordination caused by the transition bias, we devise offline datasets in a matrix game for two agents, with the payoff depicted in Table 1. The action distributions of the behavior polices of the two agents are [0.8, 0.2] and [0.4, 0.6], respectively. Table 2 shows the transition probabilities and expected returns calculated by the independent agents in the datasets. Since the datasets are collected by poor behavior policies, when one agent chooses the optimal action, the other agent would choose the suboptimal action with a high probability, which leads to low transition probabilities of high-value next states. Thus, the agents underestimate the optimal actions and converge to the suboptimal policies (a1, a2), rather than the optimal policies (a2, a1).

heading: 3.2 IMPORTANCE WEIGHTS

heading: 3.2.1 VALUE DEVIATION
text: If the behavior policies of some agents are low-performing during data collection, they usually take suboptimal actions to cooperate with the optimal actions of other agents, which leads to high transition probabilities of low-value next states. When agent i performs Q-learning with the dataset Bi, the Bellman operator T is approximated by the transition probability PBi (s′|s, ai) to estimate the expectation over s′:
T Qi(s, ai) = Es′∼PBi (s′|s,ai) [ r + γmax
âi Qi (s
′, âi) ] .
If PBi of a high-value s ′ is lower than PEi , the Q-value of this (s, ai) pair is underestimated, which would cause large extrapolation error and guide the agent to the convergence of suboptimal policy.
As discussed before, during execution, the transition probability viewed by agent i is PEi and the environment is deterministic, thus PEi (s
′|s, ai) only depends on the learned policies of other agents, which are unavailable. However, since the policies of other agents are also updating towards maximizing the Q-values, PEi of high-value next states would grow higher than PBi . Based on this intuition, we let each agent be optimistic towards other agents and modify PBi as
PBi (s ′|s, ai) ∗ (1 + V ∗i (s ′)− Eŝ′V ∗i (ŝ′) |Eŝ′V ∗i (ŝ′)|︸ ︷︷ ︸
value deviation
) ∗ 1 zvdi ,
where the state value V ∗i (s) = maxai Qi(s, ai), 1 + V ∗i (s ′)−Eŝ′V ∗ i (ŝ ′)
|Eŝ′V ∗i (ŝ′)| is the deviation of the
value of next state from the expected value over all next states, which increases the transition probabilities of the high-value next states and decreases those of the low-value next states, and zvdi = ∑ s′ PBi (s ′|s, ai) ∗ (1 + V ∗ i (s ′)−Eŝ′V ∗ i (ŝ ′)
|Eŝ′V ∗i (ŝ′)| ) is a normalization term to make sure the sum
of the transition probabilities is one. Value deviation makes the transition probability to be close to PEi and hence decreases the extrapolation error. The optimism towards other agents helps the agents escape from local optima and discover potential optimal actions which are hidden by the poor behavior policies.

heading: 3.2.2 TRANSITION NORMALIZATION
text: In real-world applications, the action distribution of behavior policy might be unbalanced, which makes the transition probabilities PBi biased, e.g., the transition probabilities of Agent 2 (i.e., action distribution of Agent 1) in Table 1. If the transition probability of a high-value next state is extremely low, value deviation cannot correct the underestimate. Moreover, since Bi of each agent is individually collected by different behavior policies, the diversity in transition probabilities of agents leads to that the value of the same state s will be overestimated by some agents, while be underestimated by others. Since the agents are trained to reach high-value states, the large divergences on state values will cause miscoordination of the learned policies. To overcome these problems, we normalize the biased transition probability PBi to be uniform over next states,
PBi (s ′|s, ai) ∗
1
PBi (s ′|s, ai)︸ ︷︷ ︸
transition normalization
∗ 1 ztni ,
where ztni is a normalization term that is the number of different s ′ given (s, ai) in Bi. Transition normalization enforces that each agent has the same PBi when it acts the learned action a ∗ i on the same state s, and we have the following proposition. Proposition 1. In episodic environments, if each agent i performs Q-learning on Bi, all agents will converge to the same V ∗ if they have the same transition probability on any state where each agent i acts the learned action a∗i .
Proof. The proof is provided in Appendix A.
However, to satisfy PB1 (s ′|s, a∗1) = PB2 (s′|s, a∗2) = . . . = PBN (s′|s, a∗N ) for all s′ ∈ S , the agents should have the same set of s′ at (s, a∗), which is a strong assumption. In practice, although the assumption is not strictly satisfied, transition normalization could still normalize the biased transition distribution, encouraging the estimated state value V ∗ to be close to each other.

heading: 3.2.3 OPTIMIZATION OBJECTIVE
text: We combine value deviation (1 + V ∗ i (s ′)−Eŝ′V ∗ i (ŝ ′)
|Eŝ′V ∗i (ŝ′)| ), which is denoted as λvdi , and transition nor-
malization 1PBi (s′|s,ai) , which is denoted as λtni , and modify PBi as,
P̂Bi (s ′|s, ai) = PBi (s′|s, ai) ∗ λtniλvdi zi ,
where zi = ∑ s′(1 + V ∗i (s ′)−Eŝ′V ∗ i (ŝ ′)
|Eŝ′V ∗i (ŝ′)| ) is the normalization term. In a sense, P̂Bi makes the offline
learning on Bi similar to the online decentralized MARL. In the initial stage, λvdi is close to 1 since Qi(s, ai) is not updated, and the transition probabilities are uniform, meaning other agents are acting randomly. During training, the transition probabilities of high-value states gradually grow under value deviation, which is an analogy of that other agents are improving their policies in the online learning. Starting from the normalized transition probabilities and changing the transition probabilities following the same optimism principle, the agents increase the values of potential optimal actions optimistically and unanimously, and build consensuses about value estimate. Therefore transition normalization and value deviation encourage the agents to learn high-performing policies and improve coordination. Moreover, although P̂Bi is non-stationary (i.e., λvdi changes over updates of Q-value), we have the following theorem about the convergence of Bellman operator T under P̂Bi ,
T Qi(s, ai) = Es′∼P̂Bi (s′|s,ai) [ r + γmax âi Qi (s ′, âi) ] .
Theorem 1. Under the non-stationary transition probability P̂Bi , the Bellman operator T is a contraction and converges to a unique fixed point when γ < rmin2rmax−rmin , if the reward is bounded by the positive region [rmin, rmax].
Proof. The proof is provided in Appendix A.
As positive affine transformation of the reward function does not change the optimal policy in the environments with fixed horizon (Zhang et al., 2021), Theorem 1 holds in general. We could rescale the reward to make rmin arbitrarily close to rmax so as to obtain a high upper bound of γ.
In deep reinforcement learning, directly modifying the transition probability is infeasible. However, we could modify the sampling probability to achieve the same effect. The optimization objective of decentralized deep Q-learning EpBi (s,ai,s′)|Qi(s, ai) − yi|
2 is calculated by sampling the batch from Bi according to the sampling probability pBi(s, ai, s′). By factorizing pBi(s, ai, s′), we have
pBi(s, ai, s ′)︸ ︷︷ ︸
sampling probability = pBi(s, ai) ∗ PBi(s′|s, ai)︸ ︷︷ ︸ transition probability .
Therefore, we can modify the transition probability as λtniλvdizi PBi (s ′|s, ai) and scale pBi(s, ai) with zi. Then, the sampling probability can be re-written as
λtniλvdipBi(s, ai, s ′)︸ ︷︷ ︸ modified sampling probability = zipBi(s, ai) ∗ λtniλvdi zi PBi(s ′|s, ai)︸ ︷︷ ︸ modified transition probability .
Since zi is independent from s′, it could be regarded as a scale factor on pBi(s, ai). Scaling pBi(s, ai) will not change the expected target value yi, so sampling batches for update according to the modified sampling probability could achieve the same effect of modifying the transition probability. Using importance sampling, the modified optimization objective is
EλtniλvdipBi (s,ai,s′)|Qi(s, ai)− yi| 2 = EpBi (s,ai,s′)
λtniλvdipBi(s, ai, s ′)
pBi(s, ai, s ′)
|Qi(s, ai)− yi|2
= EpBi (s,ai,s′)λtniλvdi |Qi(s, ai)− yi| 2,
where λtni and λvdi could be seen as the weights of the objective function.

heading: 3.3 IMPLEMENTATION
text: We implement our method on BCQ (Fujimoto et al., 2019), termed MABCQ. To make it adapt to high-dimensional continuous spaces, for each agent i, we train a Q-network Qi, a perturbation network ξi, and a conditional VAE G1i = {E1i ( µ1, σ1|s, a ) , D1i ( a|s, z1 ∼ ( µ1, σ1 )) }. In execution, each agent i generates n actions by G1i , adds small perturbations ∈ [−Φ,Φ] on the actions using ξi, and then selects the action with the highest value in Qi. The policy can be written as
πi(s) = argmax aji+ξi(s,a j i) Qi
( s, aji + ξ ( s, aji )) , where { aji ∼ G1i (s) }n j=1 .
Qi is updated by minimizing
EpBi (s,ai,s′)λtniλvdi |Qi(s, ai)− yi| 2, where yi = r + γQ̂i(s′, π̂i(s′)). (1)
yi is calculated by the target networks Q̂i and ξ̂i, where π̂i is correspondingly the policy induced by Q̂i and ξ̂i.
ξi is updated by maximizing
EpBi (s,ai,s′)λtniλvdiQi (s, ai + ξi (s, ai)) . (2)
To estimate λvdi , we need V ∗ i (s ′) = Q̂i(s ′, π̂i(s ′)) and Es′ [V ∗i (s′)] = 1γ (Q̂i(s, ai) − r), which can be estimated from the sample without actually going through all s′. We estimate λvdi using the target networks to stabilize λvdi along with the updates of Qi and ξi. To avoid extreme values, we clip λvdi to the region [1− , 1 + ], where is the optimism level. To estimate λtni , we train a VAE G 2 i = {E2i ( µ2, σ2|s, a, s′ ) , D2i ( a|s, s′, z2 ∼ ( µ2, σ2 )) }. Since the latent variable of VAE follows the Gaussian distribution, we use the mean as the encoding of the input and estimate the probability density functions: ρi(s, a) ≈ ρN (0,1)(µ1i ) and ρi(s, a, s′) ≈
Algorithm 1 MABCQ 1: for i ∈ N do 2: Initialize the conditional VAEs:
G1i = {E1i ( µ1, σ1|s, a ) , D1i ( a|s, z1 ) }, G2i = {E2i ( µ2, σ2|s, a, s′ ) , D2i ( a|s, s′, z2 ) }.
3: Initialize Q-network Qi, perturbation network ξi, and their target networks Q̂i and ξ̂i. 4: Fit the VAEs G1i and G 2 i using Bi. 5: for t = 1, . . . ,max update do 6: Sample a mini-batch from Bi. 7: Update Qi by minimizing (1). 8: Update ξi by maximizing (2). 9: Update the target networks Q̂i and ξ̂i.
10: end for 11: end for
ρN (0,1)(µ 2 i ), where ρN (0,1) is the density of unit Gaussian distribution. The conditional density is ρi(s ′|a, s) ≈ ρN(0,1)(µ 2 i )
ρN(0,1)(µ 1 i )
and the transition probability is PBi(s ′|s, ai) ≈ ∫ s′+ 12 δS s′− 12 δS ρi(s ′|s, a)ds′ ≈
ρi(s ′|s, a) ‖δS‖ when the integral interval ‖δS‖ is a small constant. Approximately, we have
λtni = ρN (0,1)(µ
1 i )
ρN (0,1)(µ 2 i ) ,
and the constant ‖δS‖ is considered in zi. In practice, we find that λtni falls into the region [0.2, 1.4] for almost all samples. For completeness, we summarize the training procedure of MABCQ in Algorithm 1.

heading: 4 EXPERIMENTS

heading: 4.1 MATRIX GAME
text: We perform MABCQ on the matrix game in Table 1. As shown in Table 3, if we only use λvd without considering transition normalization, as the transition probabilities of high-value next states have been increased, for agent 1 the value of a2 becomes higher than that of a1. However, due to the unbalanced action distribution of agent 1, the initial transition probabilities of agent 2 are extremely biased. With λvd, agent 2 still underestimates the value of a1 and learns the action a2. The agents arrive at the joint action (a2, a2), which is a worse solution than the initial one (Table 2). Normalizing the biased distribution by λtn, the agents could learn the optimal solution (a2, a1) and build the consensus about the values of learned actions, as shown in Table 4.

heading: 4.2 ENVIRONMENTS AND DATASETS
text: To evaluate the effectiveness of MABCQ in high-dimensional complex environments, we adopt multi-agent mujoco (de Witt et al., 2020), which splits the original action space of the mujoco tasks (Todorov et al., 2012; Brockman et al., 2016) into several sub-spaces. We consider four tasks, which are HalfCheetah, Walker, Hopper, and Ant. As illustrated in Figure 1, different colors indicate different agents. Each agent independently controls one or some joints of the robot and could get the state and reward of the robot, which are defined in the original tasks.
For each environment, we collect N datasets for the N agents. Each dataset contains 1 million transitions (s, ai, r, s′, done). For data collection, we train an intermediate policy and an expert policy for each agent using SAC algorithm (Haarnoja et al., 2018) provided by OpenAI Spinning Up (Achiam, 2018). The offline dataset Bi is a mixture of four parts: 20% transitions are split from the experiences generated by the SAC agent at the early training, 35% transitions are generated from that the agent i acts the intermediate policy while other agents act the expert policies, 35% transitions are generated from that agent i performs the expert policy while other agents act the intermediate policies, 10% transitions are generated from that all agents perform the expert policies. For the last three parts, we add a small noise to the policies to increase the diversity of the dataset.
We compare MABCQ against the following methods:
• MABCQ w/o λtn. Removing λtn from MABCQ. • MABCQ w/o λvd. Removing λvd from MABCQ. • BCQ. Removing both λtn and λvd from MABCQ. • DDPG (Lillicrap et al., 2016). Each agent i is trained using independent DDPG on the
offline Bi without action constraint and transition probability modification. • Behavior. Each agent i takes the action generated from the VAE G1i .
The baselines have the same neural network architectures and hyperparameters as MABCQ. All the models are trained for five runs with different random seeds. All the learning curves are plotted using mean and standard deviation. More details about hyperparameters are available in Appendix C.

heading: 4.3 PERFORMANCE AND ABLATION
text: Figure 2 shows the learning curves of all the methods in the four tasks. Without action constraint and transition probability modification, DDPG severely suffers from the large extrapolation error and can hardly improve the performance throughout the training. BCQ outperforms the behavior policies
but only arrives at the mediocre performance. In Figure 2(a) and Figure 2(c), the performance of BCQ even descends in the later stage of learning. During the collection of Bi, when agent i takes a “good” action, other agents usually take “bad” actions, making BCQ underestimate the “good” actions, especially in the latter stage. The learning curves of MABCQ w/o λvd are similar to those of BCQ in the first three tasks. That is because other agents’ policies are assumed to be random using only transition normalization, which is far from the learned policies and leads to large extrapolation errors. But in Ant, MABCQ w/o λvd outperforms BCQ in the later stage, which is attributed to the value consensus built by the normalized transition probabilities. By optimistically increasing the transition probabilities of high-value next states, MABCQ w/o λtn encourages the agents to learn potential optimal actions and obviously boosts the performance. MABCQ combines the advantages of both value deviation and transition normalization and outperforms other baselines.
To interpret the effectiveness of transition normalization, we uniformly sample a subset from the union of all agents’ states and calculate the difference in value estimates, maxi V ∗i − mini V ∗i , on this subset, where V ∗i is calculated as Qi(s, πi(s)). The results are illustrated in Figure 3. The maxi V ∗ i −mini V ∗i of MABCQ is lower than that of MABCQ w/o λtn, which verifies that transition normalization could decrease the difference in value estimates among agents. If there is a consensus among agents about which states are high-value, the agents would select the actions that most likely lead to the common high-value states. This promotes the coordination of policies and helps MABCQ outperform MABCQ w/o λtn.
In Table 5, we present the extrapolation errors of MABCQ and BCQ, | 1N ∑ iQi(s, ai)−R|, where R is the true value evaluated by Monte Carlo return. Although MABCQ greatly outperforms BCQ (i.e., higher return), it still achieves smaller extrapolation errors than BCQ in Walker, Hopper, and Ant, which empirically verifies our claim that the proposed weights could decrease the extrapolation error.
We also investigate the effect of optimism level , the computation efficiency of MABCQ, and the performance of the proposed weights on other datasets and another offline RL algorithm, i.e., CQL (Kumar et al., 2020). Due to the space limit, these results are given in Appendix B.

heading: 5 CONCLUSION
text: In this paper, we proposed MABCQ for offline and fully decentralized multi-agent reinforcement learning. MABCQ modifies the transition probability by value deviation that increases the transition probabilities of high-value next states, and by transition normalization that normalizes the biased transition probabilities. Mathematically, we show that under the non-stationary transition probability after modification, offline decentralized Q-learning converges to a unique fixed point. Empirically, we show that MABCQ could help the agents escape from the suboptimum, learn coordinated policies, and greatly outperform the baselines in a variety of multi-agent offline datasets.

heading: A PROOFS
text: Proposition 1. In episodic environments, if each agent i performs Q-learning on Bi, all agents will converge to the same V ∗ if they have the same transition probability on any state where each agent i acts the learned action a∗i .
Proof. Considering the two-agent case, we define δ(s) as the difference in the V ∗.
δ(s) = V ∗1 (s)− V ∗2 (s) = ∑ s′ PB1 (s ′|s, a∗1) (r + γV ∗1 (s′))− ∑ s′ PB2 (s ′|s, a∗2) (r + γV ∗2 (s′))
= ∑ s′ PB1 (s ′|s, a∗1) (r + γV ∗2 (s′) + γV ∗1 (s′)− γV ∗2 (s′))− ∑ s′ PB2 (s ′|s, a∗2) (r + γV ∗2 (s′))
= ∑ s′ (PB1 (s ′|s, a∗1)− PB2 (s′|s, a∗2)) (r + γV ∗2 (s′)) + γPB1 (s′|s, a∗1) δ (s′)
For the terminal state send, we have δ(send) = 0. If PB1 (s ′|s, a∗1) = PB2 (s′|s, a∗2) , ∀s′ ∈ S, recursively expanding the δ term, we arrive at δ(s) = 0 + γ0 + γ20 + ... + 0 = 0. We can easily show that it also holds in the N -agent case.
Theorem 1. Under the non-stationary transition probability P̂Bi , the Bellman operator T is a contraction and converges to a unique fixed point when γ < rmin2rmax−rmin , if the reward is bounded by the positive region [rmin, rmax].
Proof. We initialize the Q-value to be ηrmin, where η denotes 1−γ T+1
1−γ . Since the reward is bounded by the positive region [rmin, rmax], the Q-value under the operator T is bounded to [ηrmin, ηrmax]. Based on the definition of P̂Bi (s ′|s, ai), it can be written as V ∗ i (s ′)∑
ŝ′ V ∗ i (s ′) , where
V ∗i (s ′) = maxâi Qi (s ′, âi). Then, we have the following,∥∥T Q1i − T Q2i∥∥∞ = max
s,ai ∣∣∣∣∣∑ s′∈S P̂ 1Bi (s ′|s, ai) [ r + γmax âi Q1i (s ′, âi) ] − ∑ s′∈S P̂ 2Bi (s ′|s, ai) [ r + γmax âi Q2i (s ′, âi) ]∣∣∣∣∣ = max
s,ai γ ∣∣∣∣∣ ∑ s′∈S(V ∗1 i (s ′))2∑ s′∈S V ∗1 i (s ′) − ∑ s′∈S(V ∗2 i (s ′))2∑ s′∈S V ∗2 i (s ′) ∣∣∣∣∣ = max
s,ai γ ∣∣∣∣∣ ∑ s′∈S(V ∗1 i (s ′))2 − (V ∗2i (s′))2∑ s′∈S V ∗1 i (s ′) − ∑ s′∈S (V ∗ 2 i (s ′))2 ( 1∑ s′∈S V ∗2 i (s ′) − 1∑ s′∈S V ∗1 i (s ′) )∣∣∣∣∣ = max
s,ai γ ∣∣∣∣∣ ∑ s′∈S(V ∗1 i (s ′)− V ∗2i (s′))(V ∗ 1 i (s ′) + V ∗ 2 i (s ′))∑
s′∈S V ∗1 i (s ′) − ∑ s′∈S (V ∗ 2 i (s ′))2 ∑ s′∈S V ∗1 i (s ′)− V ∗2i (s′)∑ s′ V ∗1 i (s ′) ∑ s′∈S V ∗2 i (s ′) ∣∣∣∣∣ ≤ max
s,ai γ ∣∣∣∣∣∑ s′∈S (V ∗ 1 i (s ′)− V ∗2i (s′)) ∣∣∣∣∣ ∗ 1∑ s′∈S V ∗1 i (s ′) ∗max ∣∣∣∣∣(V ∗1i (s′) + V ∗2i (s′))− ∑ s′∈S(V ∗2 i (s ′))2∑ s′∈S V ∗2 i (s ′) ∣∣∣∣∣ ≤ γ|S|
∥∥Q1i −Q2i∥∥∞ ∗ 1|S|ηrmin ∗ η(2rmax − rmin) = γ(
2rmax rmin
− 1) ∥∥Q1i −Q2i∥∥∞ .
The third term of the penultimate line is because: if V ∗ 1 i (s ′) + V ∗ 2 i (s ′) >
∑ s′∈S(V ∗2 i (s
′))2∑ s′∈S V ∗2 i (s ′) ,
V ∗ 1 i (s ′)+V ∗ 2 i (s ′)− ∑ s′∈S(V ∗2 i (s
′))2∑ s′∈S V ∗2 i (s ′) ≤ V ∗1i (s′)+V ∗ 2
i (s ′)− ∑ s′∈S(V ∗2 i (s
′)) ∗ ηrmin∑ s′∈S V ∗2 i (s ′) ≤ 2ηrmax−ηrmin,
else, ∑ s′∈S(V ∗2 i (s
′))2∑ s′∈S V ∗2 i (s ′) − (V ∗1i (s′) + V ∗ 2 i (s ′)) ≤
∑ s′∈S(V ∗2 i (s
′)) ∗ ηrmax∑ s′∈S V ∗2 i (s ′) ≤ ηrmax.
Since 2ηrmax − ηrmin ≥ ηrmax, we have
|(V ∗1i (s′) + V ∗ 2 i (s ′))−
∑ s′∈S(V ∗2 i (s
′))2∑ s′∈S V ∗2 i (s ′) | ≤ 2ηrmax − ηrmin.
Therefore, if γ < rmin2rmax−rmin , the operator T is a contraction. By contraction mapping theorem, T converges to a unique fixed point.

heading: B ADDITIONAL RESULTS
text: To clearly present the performance gain of MABCQ over BCQ, we summarize the mean value and standard deviation after 5× 104 updates in Table 6, where we can see that MABCQ performs more than one standard deviation better than BCQ.
To evaluate MABCQ in low-quality dataset, we carried out an additional experiment on 2-agent Swimmer with another data collection approach, where each dataset only contains the experiences at the early training and the experiences generated by intermediate policies. As shown in Figure 4, after removing the expert experiences, MABCQ greatly outperforms BCQ, and BCQ even cannot outperform the behavior policies.
The optimism level controls the strength of value deviation. If is too small, value deviation has weak effects on the objective function. But if is too large, the agent will be over optimistic about other agents’ learned policies, which could result in large extrapolation errors and uncoordinated policies. Figure 5 shows the learning curves of MABCQ with different . It is commonly observed that increasing elevates the performance, especially in HalfCheetah. However, in Walker and Ant,
if we set a large (0.8), the performance slightly drops due to overoptimism. Even so, with any positive , MABCQ does not underperform that without value deviation.
To demonstrate the computation efficiency of our method, we record the average time taken by one update in Table 7. The experiments are carried out on Intel i7-8700 CPU and NVIDIA GTX 1080Ti GPU. Since λvd and λtn could be calculated from the sampled experience without actually going through all next states, MABCQ additionally needs only two forward passes for computing λvd and λtn in the update and costs less than twice the training time of BCQ. Moreover, since MABCQ is fully decentralized, the learning of agents can be entirely parallelized. Therefore, MABCQ scales well with the number of agents.
The two proposed weights λvd and λtn could also be extended to other offline RL methods. We introduce the two weights to CQL (Kumar et al., 2020), as MACQL, and test them in D4RL mediumreplay datasets (Fu et al., 2020). CQL augments the standard Bellman error objective with conservative regularizer, thus the learned Q-value may not represent the original meaning and thus not theoretically match value deviation. However, MACQL still outperforms CQL, as shown in Figure 6.

heading: C EXPERIMENTAL SETTINGS AND HYPERPARAMETERS
text: The experimental settings and hyperparameters are summarized in Table 8.

heading: D LIMITATION AND FUTURE WORK
text: Although we consider the setting where each agent can get the state of the environment, MABCQ could also be potentially applied to partially observable environments. However, if the partial observability is too limited, Q-value may not be accurately estimated from the observation. Many MARL methods adopt recurrent neural networks to utilize the historical information, which however is impractical if the timestamp is not included in the offline dataset. Moreover, if a state is estimated as a high-value state by an agent but not included in the datasets of other agents, the other agents cannot learn corresponding optimal actions to cooperate with that agent at that state, and thus miscoordination may occur. In this case, each agent should conservatively estimate the values of states that are absent from the datasets of other agents to avoid miscoordination. We leave the observation limitation and the state absence to future work.

Review summaries:
The paper studies an offline MARL setting, with a focus on the decentralized case, and discovers that the difference between transitions in the dataset and other agents can be very large. Authors propose two techniques, value deviation and transition normalization, to modify the transition probabilities. Experimental results validate its performance improvement over BCQ on multi-agent MuJoCo tasks. 

The authors propose a scheme to modify the transition probabilities in the learning process in a fully decentralised MARL setting. The authors show that the method is still converging to the optimal solution. They also provide some experiments on synthetic environments.

This paper proposes a method named MABCQ to utilize offline data in the MARL environment via (1) value deviation and (2) transition normalization. These two techniques are used to correct the bias in the individual observation of the transition probability and improve the discovery of optimal policy. The authors showed the convergence of the Q-learning under the non-stationary transition probabilities after modification.  

This paper studies a MARL offline setting, where each agent is trained independently. value deviation and transition normalization techniques are proposed to modify the transition probabilities. Experimental results on four benchmarks show MABCQ's performance improvement over BCQ.