{'fraction_non_alphanumeric': 0.03177792915531335, 'fraction_numerical': 0.005858310626702997, 'mean_word_length': 4.671431330886614, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Offline Decentralized Multi-Agent Reinforcement Learning

In many real-world multi-agent cooperative tasks, due to high cost and risk, agents cannot 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.


Introduction
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 [1,2]. 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. 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.
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 [6]. 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 estimate. 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. The proposed method is instantiated on BCQ [3], termed MABCQ, to additionally avoid out-of-distribution actions. We build the offline datasets and evaluate MABCQ in four multi-agent mujoco scenarios [7,8,9]. 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.
2 Related Work MARL. Many MARL methods have been proposed for learning to solve cooperative tasks in an online manner. Some methods [10,11,12] extend policy gradient into multi-agent cases. Value factorization methods [13,14,15] decompose the joint value function into individual value functions. Communication methods [16,17] share information between agents for better cooperation. All these methods follow the paradigm of centralized learning and decentralized execution (CTDE), 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 [6] deals with obsolete experience problems by conditioning the value function on a fingerprint that disambiguates the age of the sampled data. Lenient-DQN [18] extends the leniency concept and introduces optimism in the value function update by forgiving suboptimal actions. Concurrent experience replay [19] induces correlations 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-ofdistribution action [4] as the fundamental challenge, which is the main cause of the extrapolation error [3] in value estimate in the single-agent environment. To minimize the extrapolation error, recent methods first approximate the behavior policy π b with max-likelihood over the dataset and then enforce the learned policy π θ to be close to the behavior policy π b . Some methods introduce a regularization term to the objective function of π θ as, max where D is a sample-based divergence function. It could be Kernel MMD [20], Wasserstein distance, or KL divergence [5]. BCQ [3] does not use the regularization term but generates actions by sampling from the perturbed behavior policy. BCQ contains a Q-network, a perturbation network, and a conditional VAE. The conditional VAE [21,22] is trained to model the behavior policy, which outputs actions that follow the action distribution in the dataset given the state. The agent generates some actions from the VAE, adds small perturbations on the actions to increase the diversity using perturbation network, and then selects the action with the highest value in the Q-network. A finitesample analysis for offline MARL [23] 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.

Preliminaries
Considering N agents in an environment, there is a multi-agent MDP [24] M env < S, A, R, P env , γ > 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 a i , and the environment transitions to the next state s by taking the joint action a with the transition probability P env (s |s, a) and we assume the environment to be deterministic. The agents would get a shared reward r = R (s), which is simplified to just depending on state [25]. The agents learn to maximize the expected return E T t=0 γ t r t , where γ is a discount factor and T is the time horizon of the episode. However, in the fully decentralized learning, M env 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 M Ei < S, A i , R, P Ei , γ > with the individual action space A i and the transition probability 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, P Ei becomes non-stationary. Moreover, if the agent cannot interact with the environment, P Ei is unknown.
In offline and decentralized settings, each agent i could only access a fixed offline dataset B i , which is pre-collected by behavior policies and contains the tuples (s, a i , r, s ). As defined in BCQ [3], the visible MDP M Bi < S, A i , R, P Bi , γ > is constructed on B i , which has the transition probability 1  Table 2: Transition probabilities and expected returns calculated in the dataset.
where num(s, a i , s ) is the number of times the tuple (s, a i , s ) is observed in B i . However, since the learned policies of other agents might be greatly different from the behavior policies, P Bi would be biased from P Ei , which creates large extrapolation errors and differences in value estimate between agents, and eventually leads to uncoordinated suboptimal policies.
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 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 (a 1 , a 2 ), rather than the optimal policies (a 2 , a 1 ).

Value Deviation
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 B i , the Bellman operator T is approximated by the transition probability P Bi (s |s, a i ) to estimate the expectation over s : If P Bi of a high-value s is lower than P Ei , the Q-value of this (s, a i ) 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 P Ei and the environment is deterministic, thus P Ei (s |s, a i ) 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, P Ei of high-value next states would grow higher than P Bi . Based on this intuition, we let each agent be optimistic towards other agents and modify P Bi as 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 ) 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 P Ei 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.

Transition Normalization
In real-world applications, the action distribution of behavior policy might be unbalanced, which makes the transition probabilities P Bi 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 B i 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 P Bi to be uniform over next states, where c 2 i is a normalization term that is the number of different s given (s, a i ) in B i . Transition normalization enforces that each agent has the same P Bi 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 B i , 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 P B1 (s |s, a * 1 ) = P B2 (s |s, a * 2 ) = . . . = P B N (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.

Optimization Objective
We combine value deviation (1 + ), which is denoted as λ vdi , and transition normalization 1 P B i (s |s,ai) , which is denoted as λ tni , and modify P Bi as, ) is the normalization term. In a sense,P Bi makes the offline learning on B i similar to the online decentralized MARL. In the initial stage, λ vdi is close to 1 since Q i (s, a i ) 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 help the emergence of coordination. Moreover, althoughP 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 underP Bi , Proof. The proof is provided in Appendix A.
As any positive affine transformation of the reward function does not change the optimal policy [26], Theorem 1 holds in general. Moreover, we could rescale the reward to make r min arbitrarily close to r max 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 E p B i (s,ai,s ) |Q i (s, a i ) − y i | 2 is calculated by sampling the batch from B i according to the sampling probability p Bi (s, a i , s ). By factorizing p Bi (s, a i , s ), we have Therefore, we can modify the transition probability as λtn i λ vd i ci P Bi (s |s, a i ) and scale p Bi (s, a i ) with c i . Then, the sampling probability can be re-written as Since c i is independent from s , it could be regarded as a scale factor on p Bi (s, a i ). Scaling p Bi (s, a i ) will not change the expected target value y i , 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 where λ tni and λ vdi could be seen as the weights of the objective function.

Implementation
To implement MABCQ in high-dimensional continuous spaces, for each agent i, we train a Q-network Q i , a perturbation network ξ i , and a conditional VAE G 1 In execution, each agent i generates n actions by G 1 i , adds small perturbations ∈ [−Φ, Φ] on the actions using ξ i , and then selects the action with the highest value in Q i . The policy can be written as . Q i is updated by minimizing y i is calculated by the target networksQ i andξ i , whereπ i is correspondingly the policy induced bŷ Q i andξ i . Initialize the conditional VAEs: |s, a, s , D 2 i a|s, s , z 2 }.

3:
Initialize Q-network Q i , perturbation network ξ i , and their target networksQ i andξ i .

4:
Fit the VAEs G 1 i and G 2 i using B i .

7:
Update Q i by minimizing (1). 8: Update ξ i by maximizing (2). 9: Update the target networksQ i andξ i . 10: end for 11: end for ξ i is updated by maximizing To estimate λ vdi , we need , 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 Q i 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 = {E 2 i µ 2 , σ 2 |s, a, s , D 2 i a|s, s , z 2 ∼ µ 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) (µ 1 i ) and ρ i (s, a, s ) ≈ ρ 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 P Bi (s |s, a i ) ≈ s + 1 2 δ S s − 1 2 δ S ρ i (s |s, a)ds ≈ ρ i (s |s, a) δ S when the integral interval δ S is a small constant. Approximately, we have , and the constant δ S is considered in c i . In practice, we find that λ tni falls into the region [0.

Environments and Datasets
To evaluate the effectiveness of MABCQ in high-dimensional complex environments, we adopt multi-agent mujoco [9], which splits the original action space of the mujoco tasks [7,8] into several sub-spaces (MIT License). 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, a i , r, s , done). For data collection, we train a joint policy, which controls all joints, using SAC algorithm [27] provided by OpenAI Spinning Up [28] (MIT License), and store an intermediate policy and an expert policy during the training. The offline dataset B i 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 policy, 35% transitions are generated from that agent i performs the expert policy while other agents act the intermediate policy, 10% transitions are generated from that all agents perform the expert policy. For the last three parts, we add a small noise to the policy to increase the diversity of the dataset.
We compare MABCQ against the following methods: • MABCQ w/o λ tn . Removing λ tn from MABCQ.
• DDPG [29]. Each agent i is trained using independent DDPG on the offline B i without action constraint and transition probability modification. • Behavior. Each agent i takes the action generated from the VAE G 1 i . 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 experimental settings and hyperparameters are available in Appendix D. 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 B i , 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.

Performance and Ablation
To interpret the effectiveness of transition normalization, we select a subset of states and calculate the difference in value estimates, The results are illustrated in Figure 3. The max i V * i − min i 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 .

Hyperparameter Tuning
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 4 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.

Conclusion and Discussion
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.
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 where transitions are defined on partial observations. However, if the partial observability is too limited, Q-value cannot be accurately estimated from the observation. Many MARL methods adopt recurrent neural networks to utilize the history information, which however is impractical if the timestamp is not included in the 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.
A Proofs 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 * .
Therefore, if γ < r min 2rmax−r min , the operator T is a contraction. By contraction mapping theorem, T converges to a unique fixed point.

B Matrix Game
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.

C Training Cost
To demonstrate the computation efficiency of our method, we record the average time taken by one update in Table 5. 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.

D Experimental Settings and Hyperparameters
The experimental settings and hyperparameters are summarized in Table 6.