Offline Decentralized Multi-Agent
Reinforcement Learning

If the behavior policies of some agents are low-performing during data collection, they usually take ‘bad’ actions to cooperate with the ‘good’ actions of other agents, which leads to high transition probabilities of low-value next states. When agent $i$ performs Q-learning with the dataset $\mathcal{B}_{i}$, the Bellman operator $\mathcal{T}$ is approximated by the transition probability $P_{\mathcal{B}_{i}}\left(s^{\prime}|s,a_{i}\right)$ to estimate the expectation over $s^{\prime}$:

If $P_{\mathcal{B}_{i}}$ of a high-value $s^{\prime}$ is lower than $P_{\mathcal{E}_{i}}$, the Q-value of the state-action pair $(s,a_{i})$ is underestimated, which will cause large extrapolation error.

However, as the policies of other agents are also updating towards maximizing the Q-values, $P_{\mathcal{E}_{i}}$ of high-value next states will grow higher than $P_{\mathcal{B}_{i}}$. Thus, we let each agent be optimistic towards other agents and modify $P_{\mathcal{B}_{i}}$ as

where the state value $V_{i}^{*}(s)=\max_{a_{i}}Q_{i}(s,a_{i})$, $1+\nicefrac{{V_{i}^{*}(s^{\prime})-\mathbb{E}_{\hat{s}^{\prime}}V_{i}^{*}(\hat{s}^{\prime})}}{{|\mathbb{E}_{\hat{s}^{\prime}}V_{i}^{*}(\hat{s}^{\prime})|}}$ is the deviation of the value of next state from the expected value over all next states, which increases the transition probabilities of high-value next states and decreases those of low-value next states, and $z_{i}^{vd}=\sum_{s^{\prime}}P_{\mathcal{B}_{i}}\left(s^{\prime}|s,a_{i}\right)*(1+\nicefrac{{V_{i}^{*}(s^{\prime})-\mathbb{E}_{\hat{s}^{\prime}}V_{i}^{*}(\hat{s}^{\prime})}}{{|\mathbb{E}_{\hat{s}^{\prime}}V_{i}^{*}(\hat{s}^{\prime})|}})$ is a normalization term to make sure the sum of the transition probabilities is one. Value deviation modifies the transition probabilities to be close to $P_{\mathcal{E}_{i}}$ and hence reduces the transition bias. The optimism towards other agents helps the agent discover potential good actions which are hidden by the poor behavior policies of other agents.

As $\mathcal{B}_{i}$ of each agent is individually collected by different behavior policies, the diverse combinations of behavior policies of all agents lead to the value of the same state $s$ being overestimated by some agents, while being underestimated by others. Since the agents are trained to reach high-value states, the large disagreement on state values will cause miscoordination of the learned policies. To overcome the problem, we normalize $P_{\mathcal{B}_{i}}$ to be uniform over next states,

where $z_{i}^{tn}$ is a normalization term that is the number of different $s^{\prime}$ given $(s,a_{i})$ in $\mathcal{B}_{i}$. Transition normalization enforces that each agent has the same $P_{\mathcal{B}_{i}}$ when it acts the learned action $a_{i}^{*}$ on the same state $s$, and we have the following proposition.

The proof is provided in Appendix⁵⁵5Appendix is available at https://arxiv.org/abs/2108.01832.. This proposition implies that transition normalization can enable agents to have the same state value estimate. However, to satisfy $P_{\mathcal{B}_{1}}\left(s^{\prime}|s,a_{1}^{*}\right)=P_{\mathcal{B}_{2}}\left(s^{\prime}|s,a_{2}^{*}\right)=\ldots=P_{\mathcal{B}_{N}}\left(s^{\prime}|s,a_{N}^{*}\right)$ for all $s^{\prime}\in\mathcal{S}$ in the datasets, the agents should have the same set of $s^{\prime}$ at $(s,a^{*})$, which is a strong assumption. In practice, although the assumption is not strictly satisfied, transition normalization can still normalize the transition probabilities, encouraging the estimated state value $V^{*}$ to be close to each other.

Combining value deviation $1+\nicefrac{{(V_{i}^{*}(s^{\prime})-\mathbb{E}_{\hat{s}^{\prime}}V_{i}^{*}(\hat{s}^{\prime}))}}{{|\mathbb{E}_{\hat{s}^{\prime}}V_{i}^{*}(\hat{s}^{\prime})|}}$, denoted as $\lambda_{{vd}_{i}}$, and transition normalization $\nicefrac{{1}}{{P_{\mathcal{B}_{i}}\left(s^{\prime}|s,a_{i}\right)}}$, denoted as $\lambda_{{tn}_{i}}$, we modify $P_{\mathcal{B}_{i}}$ as

where $z_{i}=\sum_{s^{\prime}}(1+\nicefrac{{(V_{i}^{*}(s^{\prime})-\mathbb{E}_{\hat{s}^{\prime}}V_{i}^{*}(\hat{s}^{\prime}))}}{{|\mathbb{E}_{\hat{s}^{\prime}}V_{i}^{*}(\hat{s}^{\prime})|}})$ is the normalization term. Indeed, $\hat{P}_{\mathcal{B}_{i}}$ makes offline learning on $\mathcal{B}_{i}$ similar to online decentralized MARL. In the initial stage, $\lambda_{{vd}_{i}}$ is close to $1$ since $Q_{i}(s,a_{i})$ is not learned yet, and the transition probabilities are uniform, resembling the start stage in online learning where all agents are acting randomly. During training, the transition probabilities of high-value states gradually grow by value deviation, which is an analogy of other agents improving their policies in online learning. Therefore, $\hat{P}_{\mathcal{B}_{i}}$ encourages the agents to learn high-performing policies and improves coordination.

Although $\hat{P}_{\mathcal{B}_{i}}$ is non-stationary (i.e., $\lambda_{{vd}_{i}}$ changes along with the updates of Q-value), we have the following theorem that guarantees the convergence of Bellman operator $\mathcal{T}$ under $\hat{P}_{\mathcal{B}_{i}}$,

The proof is provided in Appendix. As any positive affine transformation of the reward function does not change the optimal policy in the fixed-horizon environments [36], Theorem 1 holds in general, and we can rescale the reward to make $r_{\min}$ arbitrarily close to $r_{\max}$ so as to make the upper bound of $\gamma$ close to $1$.

In deep reinforcement learning, directly modifying the transition probability is infeasible. However, we can instead modify the sampling probability to achieve the same effect. The optimization objective of decentralized deep Q-learning $\mathbb{E}_{p_{\mathcal{B}_{i}}(s,a_{i},s^{\prime})}|Q_{i}(s,a_{i})-y_{i}|^{2}$ is calculated by sampling the batch from $\mathcal{B}_{i}$ according to the sampling probability $p_{\mathcal{B}_{i}}(s,a_{i},s^{\prime})$. By factorizing $p_{\mathcal{B}_{i}}(s,a_{i},s^{\prime})$, we have

Therefore, we can modify the transition probability as $\frac{\lambda_{{tn}_{i}}\lambda_{{vd}_{i}}}{z_{i}}P_{\mathcal{B}_{i}}\left(s^{\prime}|s,a_{i}\right)$ and scale $p_{\mathcal{B}_{i}}(s,a_{i})$ with $z_{i}$. Then, the sampling probability can be re-written as

Since $z_{i}$ is independent of $s^{\prime}$, it can be regarded as a scale factor on $p_{\mathcal{B}_{i}}(s,a_{i})$, which will not change the expected target value $y_{i}$. Thus, sampling batches according to the modified sampling probability can achieve the same effect as modifying the transition probability. Using importance sampling, the modified optimization objective is

We can see that $\lambda_{{tn}_{i}}$ and $\lambda_{{vd}_{i}}$ simply take effect as the weights of the objective function, which makes them easily integrated with existing offline RL methods.

Our framework can be practically instantiated on many offline single-agent RL algorithms that address the overestimation incurred by out-of-distribution actions. Here, we give the instantiation of the framework on BCQ [5], termed MABCQ. To make MABCQ adapt to high-dimensional continuous spaces, for each agent $i$, we train a Q-network $Q_{i}$, a perturbation network $\xi_{i}$, and a conditional VAE $G^{1}_{i}=\{E^{1}_{i}\left(\mu^{1},\sigma^{1}|s,a\right),D^{1}_{i}\left(a|s,z^{1}\sim\left(\mu^{1},\sigma^{1}\right)\right)\}$. In execution, each agent $i$ generates $n$ actions by $G_{i}^{1}$, adds small perturbations $\in[-\Phi,\Phi]$ on the actions using $\xi_{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 networks $\hat{Q}_{i}$ and $\hat{\xi}_{i}$, where $\hat{\pi}_{i}$ is correspondingly the policy induced by $\hat{Q}_{i}$ and $\hat{\xi}_{i}$. $\xi_{i}$ is updated by maximizing

To estimate $\lambda_{{vd}_{i}}$, we need $V_{i}^{*}(s^{\prime})=\hat{Q}_{i}(s^{\prime},\hat{\pi}_{i}(s^{\prime}))$ and $\mathbb{E}_{s^{\prime}}[V_{i}^{*}\left(s^{\prime}\right)]=\frac{1}{\gamma}(\hat{Q}_{i}(s,a_{i})-r)$, which can be estimated from the sample without actually going through all $s^{\prime}$. We estimate $\lambda_{{vd}_{i}}$ using the target networks to stabilize $\lambda_{{vd}_{i}}$ along with the updates of $Q_{i}$ and $\xi_{i}$. To avoid extreme values, we clip $\lambda_{{vd}_{i}}$ to the region $[1-\epsilon,1+\epsilon]$, where $\epsilon$ is the optimism level.

To estimate $\lambda_{{tn}_{i}}$, we train a VAE $G^{2}_{i}=\{E^{2}_{i}\left(\mu^{2},\sigma^{2}|s,a,s^{\prime}\right),D^{2}_{i}\left(a|s,s^{\prime},z^{2}\sim\left(\mu^{2},\sigma^{2}\right)\right)\}$. 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: $\rho_{i}(s,a)\approx\rho_{\mathcal{N}(0,1)}(\mu^{1}_{i})$ and $\rho_{i}(s,a,s^{\prime})\approx\rho_{\mathcal{N}(0,1)}(\mu^{2}_{i})$, where $\rho_{\mathcal{N}(0,1)}$ is the density of unit Gaussian distribution. The conditional density is $\rho_{i}(s^{\prime}|a,s)\approx\nicefrac{{\rho_{\mathcal{N}(0,1)}(\mu^{2}_{i})}}{{\rho_{\mathcal{N}(0,1)}(\mu^{1}_{i})}}$ and the transition probability is $P_{\mathcal{B}_{i}}(s^{\prime}|s,a_{i})\approx\int_{s^{\prime}-\frac{1}{2}\delta_{\mathcal{S}}}^{s^{\prime}+\frac{1}{2}\delta_{\mathcal{S}}}\rho_{i}(s^{\prime}|s,a)\mathrm{d}s^{\prime}\approx\rho_{i}(s^{\prime}|s,a)\left\|\delta_{\mathcal{S}}\right\|$ when $\left\|\delta_{\mathcal{S}}\right\|$ is a small constant. Approximately, we have

and the constant $\left\|\delta_{\mathcal{S}}\right\|$ is considered in $z_{i}$. In practice, we find that $\lambda_{{tn}_{i}}$ falls into the region $[0.2,1.4]$ for almost all samples. For completeness, we summarize the training of MABCQ in Algorithm 1.

Many off-policy MARL methods have been proposed for learning to solve cooperative tasks in an online manner. Policy-based methods [15, 8, 37, 26, 29] extend actor-critic into multi-agent cases. Value factorization methods [27, 22, 25, 30] decompose the joint value function into individual value functions. All these methods follow CTDE, where the information of all agents can be accessed in a centralized way during training. Unlike these studies, we consider decentralized settings where global information is not available. For decentralized learning, the key challenge is the obsolete experiences in the replay buffer, which is considered in Fingerprints [2], Lenient-DQN [19], and concurrent experience replay [18]. However, these methods require additional information, e.g., training iteration number and exploration rate, which are often not provided by the offline dataset.

Offline RL requires the agent to learn from a fixed batch of data consisting of single-step transitions, without exploration. Most offline RL methods consider the out-of-distribution action [12] as the fundamental challenge, which is the main cause of the extrapolation error [5] 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 can be direct action constraint [5], kernel MMD [10], Wasserstein distance [31], KL divergence [21], or $l2$ distance [4, 20]. 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 [35], by minimizing the Q-values of out-of-distribution actions [11, 34], by weighting the update of Q-function via Monte Carlo dropout [32], or by explicitly assigning and training pseudo Q-values for out-of-distribution actions [16]. Our framework can be built on these methods.

MAICQ [33] studies offline MARL in the CTDE setting, which requires the joint actions of all agents in the dataset and cannot be applied to decentralized settings where datasets contain only individual actions. All the methods aforementioned do not consider the extrapolation error introduced by the transition bias, which is a fatal problem in offline decentralized MARL.

We perform MABCQ on the matrix game in Table 1. As shown in Table 3, if we only use $\lambda_{vd}$ without considering transition normalization, since the transition probabilities of high-value next states have been increased, for agent $1$ the value of ${\color[rgb]{0.60546875,0,0}a_{2}}$ becomes higher than that of ${\color[rgb]{0.60546875,0,0}a_{1}}$. However, due to the unbalanced action distribution of agent $1$, the initial transition probabilities of agent $2$ are extremely unbalanced. With $\lambda_{vd}$, agent $2$ still underestimates the value of ${\color[rgb]{0,0,0.609375}a_{1}}$ and learns the action ${\color[rgb]{0,0,0.609375}a_{2}}$. The agents arrive at the joint action $({\color[rgb]{0.60546875,0,0}a_{2}},{\color[rgb]{0,0,0.609375}a_{2}})$, which is a worse solution than the initial one (Table 2). Further, by normalizing the transition probabilities by $\lambda_{tn}$, the agents can learn the optimal solution $({\color[rgb]{0.60546875,0,0}a_{2}},{\color[rgb]{0,0,0.609375}a_{1}})$ and build the consensus about the values of learned actions, as shown in Table 4.

To evaluate MABCQ in high-dimensional complex environments, we adopt multi-agent mujoco [1], where each agent independently controls one or some joints of the robot and can get the state [9] and reward of the robot. The task illustration and the collection of offline datasets are given in Appendix.

Baselines. We compare MABCQ against

• •

  BCQ w/ ${\lambda_{vd}}$. Using $\lambda_{vd}$ alone on BCQ.

• •

  BCQ w/ ${\lambda_{tn}}$. Using $\lambda_{tn}$ alone on BCQ.

• •

  BCQ. Removing both $\lambda_{tn}$ and $\lambda_{vd}$ from MABCQ.

• •

  DDPG [14]. Each agent $i$ is trained using independent DDPG on the offline $\mathcal{B}_{i}$ without action constraint and transition probability modification.

• •

  Behavior. Each agent $i$ takes the action generated from the VAE $G_{i}^{1}$.

Ablation. Table 5 shows the normalized scores [3] of all the methods in the four tasks. Without action constraint, DDPG severely suffers from the large extrapolation error and hardly learns. BCQ outperforms the behavior policies but only arrives at mediocre performance. Using $\lambda_{tn}$ alone does not always improve the performance, e.g., in HalfCheetah and Hopper. This is because $\lambda_{tn}$ makes transition probabilities be uniform, which can be far from the ones in execution, leading to large extrapolation errors. In Ant, BCQ w/ $\lambda_{tn}$ outperforms BCQ, which is attributed to the value consensus built by the normalized transition probabilities. By optimistically increasing the transition probabilities of high-value next states, $\lambda_{vd}$ mitigates the underestimation of potential good actions and thus boosts the performance. MABCQ combines the advantages of value deviation and transition normalization and outperforms other baselines.

Consensus on value estimates. To verify that transition normalization can decrease the difference in value estimates among agents, we uniformly sample a subset from the union of all agents’ states and calculate the difference in value estimates, $\max_{i}V^{*}_{i}-\min_{i}V^{*}_{i}$, on this subset. The mean differences during training are illustrated in Table 6. The $\max_{i}V^{*}_{i}-\min_{i}V^{*}_{i}$ of MABCQ is indeed lower than that of BCQ w/ $\lambda_{vd}$. If there is a consensus among agents about which states are high-value, the agents will select the actions that most likely lead to the common high-value states. This promotes the coordination of policies and helps MABCQ outperform BCQ w/ $\lambda_{vd}$.

Extrapolation error. In Table 7, we present the extrapolation errors of MABCQ and BCQ, measured by $|\frac{1}{N}\sum_{i}Q_{i}(s,a_{i})-G|$, where $G$ is the true return evaluated by Monte Carlo. Although MABCQ greatly outperforms BCQ (i.e., much higher return), it still achieves much smaller extrapolation errors than BCQ in Walker, Hopper, and Ant. This empirically verifies the claim that our method can decrease the extrapolation error.

We also investigate the proposed framework on SMAC [23] tasks, including 3m, 8m, 3s_vs_3z, and 3s_vs_4z. We build random datasets that are generated by uniform policies, medium datasets that are generated by mixed medium and uniform policies, replay datasets that are collected in the training process of QMIX [22], and expert datasets that are generated by expert policies trained by QMIX. Each dataset contains $1\times 10^{4}$ episodes. We also build our framework on CQL [11], as MACQL. As shown in Table 8. MABCQ and MACQL achieve great performance improvement compared with the baselines, especially in random and medium datasets, where the transition dynamics in execution are much different from the ones in offline datasets. In expert datasets, since the behavior policies are much deterministic, offline RL methods avoid selecting out-of-distribution actions and thus degenerate to behavior cloning. Therefore, all the methods perform similarly.

Offline CTDE settings. Although offline CTDE method [33] does not fit our offline decentralized setting, our framework can work in offline CTDE datasets. To verify, we select two replay datasets (jointly collected) in MAICQ [33], split them into individual datasets, and test MACQL on them. As shown in Figures 1(a) and 1(b), our decentralized method can obtain competitive performance compared with the centralized method, MAICQ.

We additionally evaluate our framework in an MPE-based [15] Differential Game (DG), where the transition bias greatly affects the performance. Two agents can move in the range $[-1,1]$. The action is the speed, which is in the range $[-0.1,0.1]$. Define $l=\sqrt{x_{1}^{2}+x_{2}^{2}}$, where $x_{1}$ and $x_{2}$ are the positions of the two agents, respectively. The shared reward is set as

The visualization of reward function is shown in Figure 2.

Partial observation vs full observation. The offline datasets are collected by uniform random policies, containing $1\times 10^{6}$ transitions. In the full observation setting, the dataset of each agent contains the positions of both agents. In the partial observation setting, the dataset of each agent only contains its own position. In both settings, the datasets do not contain the actions of the other agent. We add $\lambda_{vd}$ and $\lambda_{tn}$ to TD3+BC [4], as MATD3+BC. As shown in Table 9, MATD3+BC obtains the substantial improvement in both full and partial observation settings.

Hyperparameter $\bm{\epsilon}$. The optimism level $\epsilon$ controls the strength of value deviation. If $\epsilon$ is too small, value deviation has weak effects on the objective function. On the other hand, if $\epsilon$ is too large, the agent will be overoptimistic about other agents’ learned policies. Figure 1(c) shows that the performance of MATD3+BC with different $\epsilon$, which verifies our framework is robust to $\epsilon$.

We test MATD3+BC on Cooperative Navigation in MPE, where $4$ agents learn to cover $4$ landmarks. The reward is $-\text{sum}(\mathrm{distance}_{j})$, where $\mathrm{distance}_{j}$ is the distance from landmark $j$ to the closest agent. The offline datasets are collected by uniform random policies, containing $1\times 10^{6}$ transitions. Figure 1(d) shows our framework significantly outperforms the baseline.

We also split the D4RL [3] Mujoco datasets into decentralized multi-agent datasets, and test MATD3+BC on them. The results are summarized in Table 10. We find the results of decentralized methods, where the joints are controlled by different agents, are very close to the results of single-agent method, TD3+BC (single), where a single agent controls all joints, which could be seen as the “upper-bound” of the decentralized methods. That is the reason that our method does not bring significant improvement in these tasks. However, MATD3+BC still outperforms TD3+BC on several tasks, e.g., halfcheetah-random and walker2d-medium.

To demonstrate the computation efficiency of our method, in Table 11, we record the average time taken by one update in Halfcheetah. The experiments are carried out on Intel i7-8700 CPU and NVIDIA GTX 1080Ti GPU. Since $\lambda_{vd}$ and $\lambda_{tn}$ could be calculated from the sampled experience without actually going through all next states, our framework additionally needs only two forward passes for computing $\lambda_{vd}$ and $\lambda_{tn}$ in the update. Since the value computation is very efficient in TD3+BC, our framework is also efficient on it.