Year: 2021

Abstract:
Entropy regularization is a popular method in reinforcement learning (RL). Although it has many advantages, it alters the RL objective and makes the converged policy deviate from the optimal policy of the original Markov Decision Process. Though divergence regularization has been proposed to settle this problem, it cannot be trivially applied to cooperative multi-agent reinforcement learning (MARL). In this paper, we investigate divergence regularization in cooperative MARL and propose a novel off-policy cooperative MARL framework, divergence-regularized multi-agent actor-critic (DMAC). Mathematically, we derive the update rule of DMAC which is naturally off-policy, guarantees a monotonic policy improvement and is not biased by the regularization. DMAC is a flexible framework and can be combined with many existing MARL algorithms. We evaluate DMAC in a didactic stochastic game and StarCraft Multi-Agent Challenge and empirically show that DMAC substantially improves the performance of existing MARL algorithms.

heading: 1 INTRODUCTION
text: Regularization is a common method for single-agent reinforcement learning (RL). The optimal policy learned by traditional RL algorithm is always deterministic (Sutton and Barto, 2018). This property may result in the inflexibility of the policy facing with unknown environments (Yang et al., 2019). Entropy regularization is proposed to settle this problem by learning a policy according to the maximum-entropy principle (Haarnoja et al., 2017). Moreover, entropy regularization is beneficial to exploration and robustness for RL algorithms (Haarnoja et al., 2018). However, entropy regularization is imperfect. Eysenbach and Levine (2019) pointed out maximum-entropy RL is a modification of the original RL objective because of the entropy regularizer. Maximum-entropy RL is actually learning an optimal policy for the entropy-regularized Markov Decision Process (MDP) rather than the original MDP, i.e., the converged policy may be biased. Nachum et al. (2017) analysed a more general case for regularization in RL and proposed what we call divergence regularization. Divergence regularization can avoid the bias of the converged policy as well as be beneficial to exploration. Wang et al. (2019) employed divergence regularizer and proposed a single-agent RL algorithm, DAPO, which prevents the altering-objective drawback of entropy regularization.
Regularization can also be applied to cooperative multi-agent reinforcement learning (MARL) (Agarwal et al., 2020; Zhang et al., 2021). However, most of cooperative MARL algorithms do not use regularizer (Lowe et al., 2017; Foerster et al., 2018; Rashid et al., 2018; Son et al., 2019; Jiang et al., 2020; Wang et al., 2021a). Only few cooperative MARL algorithms such as FOP (Zhang et al., 2021) use entropy regularization, which may suffer from the drawback aforementioned. Divergence regularization, on the other hand, could potentially benefit cooperative MARL. In addition to its advantages mentioned above, divergence regularization can also help to control the step size of policy update which is similar to conservative policy iteration (Kakade and Langford, 2002) in single-agent RL. Conservative policy iteration and its successive methods such as TRPO (Schulman et al., 2015) and PPO (Schulman et al., 2017) can stabilize policy improvement (Touati et al., 2020). These methods use a surrogate objective for policy update, but decentralized policies in centralized training with decentralized execution (CTDE) paradigm may not preserve the properties of the surrogate objective. Moreover, DAPO (Wang et al., 2019) cannot be trivially extended to cooperative MARL settings. Even with some tricks like V-trace (Espeholt et al., 2018) for off-policy correction, DAPO is essentially an on-policy algorithm and thus may not be sample-efficient in cooperative MARL settings.
In the paper, we propose and analyze divergence policy iteration in general cooperative MARL settings and a special case combined with value decomposition. Based on divergence policy iteration, we derive the off-policy update rule for the critic, policy, and target policy and propose divergenceregularized multi-agent actor-critic (DMAC), a novel off-policy cooperative MARL framework. We theoretically show that DMAC guarantees a monotonic policy improvement and is not biased by the regularization. Besides, DMAC is beneficial to exploration and stable policy improvement by applying our update rule of target policy. Moreover, DMAC is a flexible framework and can be combined with many existing cooperative MARL algorithms to substantially improve their performance.
We empirically investigate DMAC in a didactic stochastic game and StarCraft Multi-Agent Challenge (Samvelyan et al., 2019). We combine DMAC with five representative MARL methods, i.e., COMA (Foerster et al., 2018) for on-policy multi-agent policy gradient, MAAC (Iqbal and Sha, 2019) for off-policy multi-agent actor-critic, QMIX (Rashid et al., 2018) for value decomposition, DOP (Wang et al., 2021b) for the combination of value decomposition and policy gradient, and FOP (Zhang et al., 2021) for the combination of value decomposition and entropy regularization. Experimental results show that DMAC indeed induces better performance, faster convergence, and better stability in most tasks, which verifies the benefits of DMAC and demonstrates the advantages of divergence regularization over entropy regularization in cooperative MARL.

heading: 2 RELATED WORK
text: MARL. MARL has been a hot topic in the field of RL. In this paper, we focus on cooperative MARL. Cooperative MARL is usually modeled as Dec-POMDP (Oliehoek et al., 2016), where all agents share a reward and aim to maximize the long-term return. Centralized training with decentralized execution (CTDE) (Lowe et al., 2017) paradigm is widely used in cooperative MARL. CTDE usually utilizes a centralized value function to address the non-stationarity for multi-agent settings and decentralized policies for scalability. Many MARL algorithms adopt CTDE paradigm such as COMA, MAAC, QMIX, DOP and FOP. COMA (Foerster et al., 2018) employs the counterfactual baseline which can reduce the variance as well as settle the credit assignment problem. MAAC (Iqbal and Sha, 2019) uses self-attention mechanism to integrate local observation and action of each agent and provides the structured information for the centralized critic. Value decomposition (Sunehag et al., 2018; Rashid et al., 2018; Son et al., 2019; Yang et al., 2020; Wang et al., 2021a;b; Zhang et al., 2021) is a popular class of cooperative MARL algorithms. These methods express the global Q-function as a function of individual Q-functions to satisfy Individual-Global-Max (IGM), which means the optimal actions of individual Q-functions are corresponding to the optimal joint action of global Q-function. QMIX (Rashid et al., 2018) is a representative of value decomposition methods. It uses a hypernet to ensure the monotonicity of the global Q-function in terms of individual Q-functions, which is a sufficient condition of IGM. DOP (Wang et al., 2021b) is a method that combines value decomposition with policy gradient. DOP uses a linear value decomposition which is another sufficient condition of IGM and the linear value decomposition helps the compute of policy gradient. FOP (Zhang et al., 2021) is a method that combines value decomposition with entropy regularization and uses a more general condition, Individual-Global-Optimal, to replace IGM. In this paper, we will combine DMAC with these algorithms and show its improvement.
Regularization. Entropy regularization was first proposed in single-agent RL. Nachum et al. (2017) analyzed the entropy-regularized MDP and revealed the properties about the optimal policy and the corresponding Q-function and V-function. They also showed the equivalence of value-based methods and policy-based methods in entropy-regularized MDP. Haarnoja et al. (2018) pointed out maximum-entropy RL can achieve better exploration and stability facing with the model and estimation error. Although entropy regularization has many advantages, Eysenbach and Levine (2019) showed entropy regularization modifies the MDP and results in the bias of the convergent policy. Yang et al. (2019) revealed the drawbacks of the convergent policy of general RL and maximum-entropy RL. The former is usually a deterministic policy (Sutton and Barto, 2018) which is not flexible enough for unknown situations, while the latter is a policy with non-zero probability for all actions which may be dangerous in some scenarios. Neu et al. (2017) analyzed the entropy regularization method from several views. They revealed a more general form of regularization which is actually divergence regularization and showed entropy regularization is just a special case of divergence regularization. Wang et al. (2019) absorbed previous result and proposed an on-policy algorithm, i.e., DAPO. However, DAPO cannot be trivially applied to MARL. Moreover, its on-policy learning is
not sample-efficient for MARL settings and its off-policy correction trick V-trace (Espeholt et al., 2018) is also intractable in MARL. There are some previous studies in single-agent RL which use similar target policy to ours, but their purposes are quite different. Trust-PCL (Nachum et al., 2018) introduces a target policy as a trust region constraint for maximum-entropy RL, but the policy is still biased by entropy regularizer. MIRL (Grau-Moya et al., 2019) uses a distribution which is only related to actions as the target policy to compute a mutual-information regularizer, but it still changes the objective of the original RL.

heading: 3 PRELIMINARIES
text: Dec-POMDP is a general model for cooperative MARL. A Dec-POMDP is a tuple M = {S,A, P, Y,O, I, n, r, γ}. S is the state space, n is the number of agents, γ is the discount factor, and I = {1, 2 · · ·n} is the set of all agents. A = A1 ×A2 × · · · ×An represents the joint action space where Ai is the individual action space for agent i. P (s′|s,a) : S × A × S → [0, 1] is the transition function, and r(s,a) : S×A→ R is the reward function of state s and joint action a. Y is the observation space, and O(s, i) : S× I → Y is a mapping from state to observation for each agent. The objective of Dec-POMDP is to maximize J(π) = Eπ [ ∑ t=0 γ
tr(st,at)] , and thus we need to find the optimal joint policy π∗ = arg maxπ J(π). To settle the partial observable problem, history τi ∈ Ti = (Y × Ai)∗ is often used to replace observation oi ∈ Y . As for policies in CTDE, each agent i has an individual policy πi(ai|τi) and the joint policy π is the product of each πi. Though we calculate individual policy as πi(ai|τi) in practice, we will use πi(ai|s) in analysis and proofs for simplicity.
Entropy regularization adds the logarithm of current policy to the reward function. It modifies the optimization objective as Jent(π) = Eπ [ ∑ t=0 γ
t (r(st,at)− λ logπ(at|st))] . We also have the corresponding Q-function Qπent(s,a) = r(s,a) + γE [V πent(s′)] and V-function V πent(s) = E [Qπent(s,a)− λ logπ(a|s)]. Given these definitions, we can deduce an interesting property V πent(s) = E [Qπent(s,a)] + λH (π(·|s)), whereH (π(·|s)) represents the entropy of policy π(·|s). V πent(s) includes an entropy term which is the reason it is called entropy regularization.

heading: 4 METHOD
text: In this section, we first give the definition of divergence regularization. Then we propose and analyze divergence policy iteration. Finally, based on divergence policy iteration, we derive the update rules of the critic, policy, and target policy for divergence-regularized MARL.

heading: 4.1 DIVERGENCE REGULARIZATION
text: We maintain a target policy ρi for each agent i, which is different from the policy πi. Then we have a joint target policy ρ = ∏n i=1 ρi. This joint target policy ρ modifies the objective function
as Jρ(π) = Eπ [∑ t=0 γ t ( r(st,at)− λ log π(at|st)ρ(at|st) )] . That is, a regularizer log π(at|st)ρ(at|st) , which describes the discrepancy between policy π and target policy ρ, is added to the reward function just like entropy regularization.
Given ρ, we can define corresponding V-function and Q-function for divergence regularization as follows,
V πρ (s) = Eπ [∑ t=0 γt(r(st,at)− λ log π(at|st) ρ(at|st) )|s0 = s ] (1)
Qπρ (s,a) = r(s,a) + γEs′∼P (·|s,a) [ V πρ (s ′) ] . (2)
Further, by simple deduction, we have V πρ (s) = Ea∼π(·|s) [ Qπρ (s,a)− λ log
π(a|s) ρ(a|s)
] = Ea∼π(·|s) [ Qπρ (s,a) ] − λDKL (π(·|s)‖ρ(·|s)) .
V πρ (s) includes an extra term which is the KL divergence between π and ρ, and thus this regularizer is referred to as divergence regularization.

heading: 4.2 DIVERGENCE POLICY ITERATION
text: From the perspective of policy evaluation, we can define an operator Γπρ as ΓπρQ(s,a) = r(s,a) + γEs′∼P (·|s,a),a′∼π(·|s′) [ Q(s′,a′)− λ log π(a ′|s′) ρ(a′|s′) ] (3)
and have the following lemma. Note that all the proofs are given in Appendix A.
Lemma 1 (Divergence Policy Evaluation) For any initial Q-function Q0(s,a) : S × A→ R, we define a sequence { Qk }
given operator Γπρ as Q k+1 = ΓπρQ k. Then, the sequence will converge to Qπρ as k →∞.
After the evaluation of the policy, we need a method to improve the policy. We have the following lemma about policy improvement.
Lemma 2 (Divergence Policy Improvement) If we define πnew satisfying
πnew(·|s) = arg min π DKL (π(·|s)‖u(·|s)) , (4)
where u(·|s) = ρ(·|s) exp(Q πold ρ (s,·)/λ)
Zπold (s) and Z πold(s) is a normalization term, then for all actions a
and all states s we have Qπnewρ (s,a) ≥ Qπoldρ (s,a).
Lemma 1 and 2 could be seen as corollaries of the conclusion of Haarnoja et al. (2018). Lemma 2 indicates that given a policy πold, if we find a policy πnew according to (4), then the policy πnew is better than πold.
Lemma 2 does not make any assumption and is for general settings. Further, the policy improvement can be established and simplified based on value decomposition. In the following, we give an example for linear value decomposition like DOP (i.e., Q(s,a) = ∑ i ki(s)Qi(s, ai) + b(s)) (Wang et al., 2021b).
Lemma 3 (Divergence Policy Improvement with Linear Value Decomposition) If Q-functions satisfy Qπρ (s,a) = ∑ i ki(s)Q πi ρ (s, ai) + b(s) and we define π i new satisfying
πinew(·|s) = arg min πi DKL (πi(·|s)‖ui(·|s)) ∀i ∈ I,
where ui(·|s) = ρi(·|s) exp
( ki(s)Q πiold ρ (s,·)/λ ) Zπ i old (s) and Zπ i old(s) is a normalization term, then for all
actions a and all states s we have Qπnewρ (s,a) ≥ Qπoldρ (s,a).
Lemma 3 further tells us that if the MARL setting satisfies the linear value decomposition condition, then each agent can optimize its individual policy with an objective of its own individual Q-function, which immediately improves the joint policy. By combining divergence policy evaluation and divergence policy improvement, we have the following theorem of divergence policy iteration.
Theorem 1 (Divergence Policy Iteration) By iteratively using Divergence Policy Evaluation and Divergence Policy Improvement, we will get a sequence { Qk }
and this sequence will converge to the optimal Q-function Q∗ρ and the corresponding policy sequence will converge to the optimal policy π∗ρ.
Theorem 1 shows that with repeated application of divergence policy improvement and divergence policy evaluation, the policy can be monotonically improved and converge to the optimal policy. Let π∗ρ, V ∗ ρ (s), and Q ∗ ρ(s,a) denote the optimal policy, Q-function, and V-function respectively, given a target policy ρ. We have the following proposition.
Proposition 1 If π∗ρ = arg maxπ Jρ(π), and V ∗ρ (s) = V π∗ρ ρ (s) and Q∗ρ(s,a) = Q π∗ρ ρ (s,a) are respectively the corresponding Q-function and V-function of π∗ρ, then they satisfy the following
properties: π∗ρ(a|s) ∝ ρ(a|s) exp (( r(s,a) + γEs′∼P (·|s,a) [ V ∗ρ (s ′) ]) /λ )
(5) V ∗ρ (s) = λ log ∑ a ρ(a|s) exp (( r(s,a) + γEs′∼P (·|s,a) [ V ∗ρ (s ′) ]) /λ ) (6)
Q∗ρ(s,a) = r(s,a) + γλEs′∼P (·|s,a) [ log ∑ a′ ρ(a|s) exp ( Q∗ρ(s ′,a′)/λ ) ] . (7)
With all these results above, we have enough tools to obtain the practical update rule of the critic, policy and target policy of DMAC.

heading: 4.3 DIVERGENCE-REGULARIZED CRITIC
text: From Proposition 1, we can obtain
π∗ρ(a|s) = ρ(a|s) exp
(( r(s,a) + γEs′∼P (·|s,a) [ V ∗ρ (s ′) ]) /λ )∑
b ρ(b|s) exp (( r(s, b) + γEs′∼P (·|s,b) [ V ∗ρ (s ′) ]) /λ ) = ρ(a|s) exp (Q∗ρ(s,a)/λ) exp ( V ∗ρ (s)/λ
) = ρ(a|s) exp (( Q∗ρ(s,a)− V ∗ρ (s) ) /λ ) . (8)
By rearranging the equation, we have
V ∗ρ (s) = Q ∗ ρ(s,a)− λ log π∗ρ(a|s) ρ(a|s) , (9)
which is tenable for all actions a ∈ A. Therefore, we have the following corollary. Corollary 1
Q∗ρ(s,a) = r(s,a) + γEs′∼P (·|s,a),a′∼π∗ρ(·|s′) [ Q∗ρ(s ′,a′)− λ log π∗ρ(a ′|s′) ρ(a′|s′) ] is tenable for all actions a′ ∈ A.
Corollary 1 gives an iterative formula for Q∗ρ(s,a), with which we can design a loss function and update rule for learning the critic,
LQ = E [ (Qφ(s,a)− y)2 ] , where y = r(s,a) + γ ( Qφ̃ (s ′,a′)− λ log π (a ′|s′)
ρ (a′|s′)
) , (10)
where φ and φ̃ are respectively the weights of Q-function and target Q-function.The update of Q-function is similar to that in general MDP, except that the action for next state could be chosen arbitrarily while it must be the action that maximizes Q-function for next state in general MDP. This property greatly enhances the flexibility of learning Q-function, e.g., we can easily extend it to TD(λ).

heading: 4.4 DIVERGENCE-REGULARIZED ACTORS
text: DAPO (Wang et al., 2019) analyzes the divergence-regularized MDP from the perspective of policy gradient theorem (Sutton et al., 2000) and gives an on-policy update rule for single-agent RL. Unlike existing work, we focus on a different perspective and derive an off-policy update rule by taking into consideration the characteristics of MARL.
From Lemma 2, we can obtain an optimization target for policy improvement,
arg min π DKL
( π(·|s)‖ρ(·|s) exp ( Qπρ (s, ·)/λ ) Zπ(s) ) = arg max π ∑ a π(a|s) ( Qπρ (s,a)− λ log π(a|s) ρ(a|s) ) .
Then, we can define the objective of the actors,
Lπ = Es∼D [∑ a π(a|s) ( Qπρ (s,a)− λ log π(a|s) ρ(a|s) )] , (11)
where D is the replay buffer. Suppose each individual policy πi has a corresponding parameterization θi. We can obtain the following policy gradient for each agent with some derivation and the detail is given in Appendix A.6,
∇θiLπ = Es∼D,a∼π [ ∇θi log πi(ai|s) ( Qπρ (s,a)− λ log
π(a|s) ρ(a|s)
− λ )] . (12)
We need to point out that the key to off-policy update is that Lemma 2 does not limit the state distribution. It only requires the condition is satisfied for each state. Therefore, we can maintain a replay buffer to cover different states as much as possible, which is a common practice in off-policy learning. DAPO uses a similar formula to ours, but it obtains the formula from policy gradient theorem, which requires the state distribution of the current policy.
Further, we can add a counterfactual baseline to the gradient. First, we have the following equation about the counterfactual baseline (Foerster et al., 2018),
Es∼D,a∼π [∇θi log πi(ai|s)b(s, a−i)] = 0, (13) where a−i denotes the joint action of all agents except agent i. Next, we take the baseline as
b(s, a−i) = Eai∼πi [(Qπρ (s,a)− λ log π(a|s) ρ(a|s) − λ)]. (14)
Then, the gradient for each agent i can be modified as follows,
∇θiLπ = E[∇θi log πi(ai|s)(Qπρ (s,a)− λ log π(a|s) ρ(a|s) − λ− b(s, a−i))]
= E[∇θi log πi(ai|s)(Qπρ (s,a)− λ log πi(ai|s) ρi(ai|s) − Eai∼πi [Qπρ (s,a)] + λDKL(πi(·|s)‖ρi(·|s)))].
In addition to variance reduction and credit assignment, this counterfactual baseline eliminates the policies of other agents from the gradient. This property makes it convenient to calculate the gradient and easy to select the target policy for each agent. Moreover, if the linear value decomposition condition is satisfied, we have the following gradient formula,
∇θiLπ = E[∇θi log πi(ai|s)(ki(s)Aπiρ (s, ai)− λ log πi(ai|s) ρi(ai|s) + λDKL(πi(·|s)‖ρi(·|s)))], (15)
where Aπiρ (s, ai) = Q πi ρ (s, ai)− Eãi∼πi [ Qπiρ (s, ãi) ] .

heading: 4.5 TARGET POLICY
text: We have discussed the update rule of the critic and actors, and now we focus on the selection and update rule of the target policy. With the update rules above, we can obtain divergence policy iteration given a fixed target policy ρ. Then we need to devise the update rule of ρ to prevent the bias of regularization and benefit the learning procedure.
Intuitively, this regularizer log π(at|st)ρ(at|st) could help to balance exploration and exploitation. For example, for some action a, if ρ(a|s) > π(a|s), then the regularizer is equivalent to adding a positive value to the reward and vice versa. Therefore, if we choose previous policy as target policy, the regularizer will encourage agents to take actions whose probability has decreased and discourage agents to take actions whose probability has increased. Additionally, the regularizer actually controls the discrepancy between current policy and previous policy, which could stabilize the policy improvement (Kakade and Langford, 2002; Schulman et al., 2015; 2017).
To derive the update rule of target policy, we need to further analyze the regularizer theoretically. Let µπ denote the state-action distribution given a policy π. That is, µπ(s,a) = dπ(s)π(a|s), where dπ(s) = ∑ t=0 γ
t Pr(st = s|π) is the stationary distribution of states given π. With µπ, we can rewrite the optimization objective Jρ(π) as follows,
Jρ(π) = ∑ s,a µπ(s,a)r(s,a)− λ ∑ s,a µπ(s,a) log π(a|s) ρ(a|s)
= ∑ s,a µπ(s,a)r(s,a)− λDC (µπ‖µρ) , (16)
where DC (µπ‖µρ) = ∑ s,a µπ(s,a) log π(a|s) ρ(a|s) is a Bregman divergence (Neu et al., 2017). Therefore, the objective of the divergence regularized MDP can be represented as (17)
π∗ = arg max π ∑ s,a µπ(s,a)r(s,a)− λDC (µπ‖µρ) (17)
With this property, similar to Neu et al. (2017) and Wang et al. (2019), we can use the following iterative process,
πt+1 = arg max π ∑ s,a µπ(s,a)r(s,a)− λDC (µπ‖µπt) (18)
This iteration is a mirror descent process (Neu et al., 2017), so the convergence of the policy is guaranteed. This process also guarantees that when the policy converges, DC (µπt+1‖µπt)→ 0; i.e., the regularizer will vanish. Moreover, we can obtain the following inequalities:
J(πt+1) ≥ J(πt+1)− λDC (µπt+1‖µπt) ≥ J(πt)− λDC (µπt‖µπt) = J(πt),
The first inequality is from DC (µπ‖µρ) ≥ 0 and the second inequality is from the definition of πt+1. This conclusion means the policy sequence obtained by this iteration improves monotonically in the original MDP. With these deductions, we actually obtain the following theorem.
Theorem 2 By iteratively applying the divergence policy iteration and taking ρk as πk,the policy sequence {πk} will converge and improve monotonically in the original MDP.
However, it is intractable to perform this update rule in practice because every iteration in (18) needs a convergent policy. Thus, we propose an alternative approximate method. For each agent, we update the policy πi and the target policy ρi as θi = θi + β∇θiLπ and θ̃i = (1 − τ)θ̃i + τθi, where β is the learning rate, θ̃i is the weights of ρi, and τ is the hyperparameter for soft update. Here we use one gradient step to replace the max operator in (18). From Theorem 1 and previous discussion, we know that optimizing Lπ can maximize Jρ(π), so we use∇θiLπ in the gradient step for off-policy training instead of the gradient step directly optimizing Jρ(π) in (16). Moreover, as the convergence of (17) is guaranteed only if the target policy ρ is fixed, we softly update the target policy as the moving average of the policy to prevent the instability caused by the large change of the target policy and hence obtain stable policy improvement.
Now we have all the update rules of DMAC. The training of DMAC is a typical off-policy learning process, which is given in Appendix B for completeness.

heading: 5 EXPERIMENTS
text: In this section, we first empirically study the benefits of DMAC and investigate how DMAC improves the performance of existing MARL algorithms in a didactic stochastic game and five SMAC tasks. Then, we demonstrate the advantages of divergence regularizer over entropy regularizer in cooperative MARL.

heading: 5.1 IMPROVEMENTS OF EXISTING METHODS
text: DMAC is a flexible framework and can be combined with many existing MARL algorithms. In the experiments, we choose four representative algorithms for different types of methods: COMA (Foerster et al., 2018) for on-policy multi-agent policy gradients, MAAC (Iqbal and Sha, 2019) for off-policy multi-agent actor-critic, QMIX (Rashid et al., 2018) for value decomposition, DOP (Wang et al., 2021b) for the combination of value decomposition and policy gradient. These algorithms need minor modifications to fit the framework of DMAC. We denote these modified algorithms as COMA+DMAC, MAAC+DMAC, QMIX+DMAC, and DOP+DMAC. Generally, our modification is limited and tries to keep the original architecture so as to fairly demonstrate the improvement of DMAC. The details of the modifications are included in Appendix C.1. More details about hyperparameters are available in Appendix C. All the curves in our plots correspond to the mean value of five training runs with different random seeds, and shaded regions indicate 95% confidence interval.

heading: 5.1.1 A DIDACTIC EXAMPLE
text: We first test the four groups of methods in a stochastic game where agents share the reward. The stochastic game is generated randomly for the reward function and transition probabilities with 30 states, 3 agents and 5 actions for each agent. Each episode contains 30 steps in this game. The performance of these methods is illustrated in Figure 1. We could find that DMAC performs
better than the baseline at the end of the training in all the four groups. Moreover, COMA+DMAC, QMIX+DMAC and MAAC+DMAC learn faster than their baselines. Though DOP learns faster than DOP+DMAC at the start, it falls into a sub-optimal policy and DOP+DMAC finds a better policy in the end.
We also show the benefit of exploration in this stochastic game for the convenience of statistics. We evaluate the exploration in terms of the cover rate of all state-action pairs, i.e., the ratio of the explored state-action pairs to all state-action pairs. The cover rates of COMA and COMA+DMAC are illustrated in Figure 2. We use COMA here as a representation of the traditional policy gradient method in cooperative MARL. We could find that the cover rate of COMA+DMAC is higher than COMA, which can be an evidence for the benefit of exploration of DMAC. The cover rates of other three groups of algorithms are available in Appendix D.

heading: 5.1.2 SMAC
text: We test all the methods in five tasks of StarCraft Multi-Agent Challenge (SMAC) (Samvelyan et al., 2019). The introduction of the SMAC environment and the training details are included in Appendix C. The learning curves in terms of win rate of all the methods in the five SMAC tasks are illustrated in Figure 3 (four columns for four groups of algorithms and five rows for five different maps in SMAC). In addition, the learning curves in terms of rewards are available in Appendix D. We show the empirical result of DAPO in the map of 3m in the first figure of the second column in Figure 3. It can be seen that DAPO cannot obtain a good performance in the simple task of SMAC, so we skip it in other SMAC tasks. The reason for the low performance of DAPO may be that DAPO omits the correction for dπ(s)/dπt(s) in policy update which introduces bias in the gradient of policy, and uses V-trace as off-policy correction which however is biased. These drawbacks may be magnified
in MARL settings. The superiority of our naturally off-policy method over the biased off-policy correction method can be partly seen from the large performance gap between COMA+DMAC and DAPO.
In all the five tasks, MAAC+DMAC outperforms MAAC significantly, but MAAC+DMAC does not change the network architecture of MAAC, which shows the benefits of divergence regularizer. As for the result of COMA and COMA+DMAC. We find that COMA+DMAC has higher win rates than COMA in most cases at the end of the training, which can be attributed to the benefits of off-policy training and exploration of divergence regularizer. Though in some cases COMA learns faster than COMA+DMAC, it falls into sub-optimal in the end. This phenomenon can be observed more clearly in the plots of episode rewards in Appendix D, especially in the hard tasks like 3s5z. This can be an evidence for the advantage of divergence regularizer which helps the agents find a better policy.
The stable policy improvement of divergence regularizer can be showed in the variance of the learning curves especially in the comparison between QMIX and QMIX+DMAC. In most tasks, we find that QMIX+DMAC learns substantially faster than QMIX and gets higher win rates in harder tasks. The results of DOP groups are illustrated in the fourth column of Figure 3. DOP+DMAC learns faster than DOP in most cases and finally obtains a better performance. The difference of DOP and DOP+DMAC can also partly show the advantage of naturally off-policy method to the off-policy correction method, as DOP+DMAC replaces the tree backup loss with off-policy TD(λ).
DMAC improves the performance and/or convergence speed of the evaluated algorithms in most tasks. This empirically demonstrates the benefits of divergence regularizer. Moreover, the superiority of our naturally off-policy learning over the biased off-policy correction method can be partly witnessed from the empirical results.

heading: 5.2 COMPARISON WITH ENTROPY REGULARIZATION
text: FOP (Zhang et al., 2021) combines the value decomposition with entropy regularization, which obtained the state-of-the-art performance in SMAC tasks. FOP has a well tuned scheme for the temperature parameter of the entropy, so we take FOP as a strong baseline for entropy-regularized methods in cooperative MARL. We compare FOP and FOP+DMAC in three SMAC tasks, 3s_vs_3z, 2c_vs_64zg, and MMM2, which respectively correspond to the three levels of difficulties (i.e., easy, hard, and super hard) for SMAC tasks. These tasks are taken from the original paper of FOP. The modifications of FOP+DMAC are also included in Appendix C.1. The win rates of FOP and FOP+DMAC are illustrated in Figure 4. We could find that FOP+DMAC learns much faster than FOP in 3s_vs_3z, while it performs better than FOP in other two harder tasks. These results could be an evidence for the advantages of DMAC and the bias of entropy regularization.

heading: 6 CONCLUSION
text: We propose a multi-agent actor-critic framework, DMAC, for cooperative MARL. We investigate divergence regularization, derive divergence policy iteration, and deduce the update rules for the critic, policy, and target policy in multi-agent settings. DMAC is a naturally off-policy framework and the divergence regularizer is beneficial to exploration and stable policy improvement. Unlike entropy regularizer, the divergence regularizer will not bias the converged policy. DMAC is also a flexible framework and can be combined with many existing MARL algorithms with limited modification. It is empirically demonstrated that combining DMAC with existing MARL algorithms can improve the performance and convergence speed in a stochastic game and SMAC tasks.

heading: A PROOFS
text: A.1 LEMMA 1
Proof. We define a new reward function rπρ (s,a) = r(s,a)− λEs′∼P (·|s,a) [DKL (π(·|s′)‖ρ(·|s′))] ,
then we can rewrite the definition of operator Γπρ as
ΓπρQ(s,a) = r π ρ (s,a) + γEs′∼P (·|s,a),a′∼π(·|s′) [Q(s′,a′)] .
With this formula, we can apply the traditional convergence result of policy evaluation in Sutton and Barto (2018).
A.2 LEMMA 2
For the proof of Lemma 2, we need the following lemma (Haarnoja et al., 2018) about improving policy in entropy-regularized MDP.
Lemma 4 If we have a new policy πnew and
πnew = arg min π DKL
( π(·|s)‖exp (Q πold ent (s, ·)/λ)
Zπold(s)
) ,
where Zπold(s) represents the normalization term, then we have
Qπnewent (s, a) ≥ Q πold ent (s, a), ∀s ∈ S, a ∈ A.
With Lemma 4, we have the following proof of Lemma 2.
Proof. Let Q̂ be the same as the definition in Proof A.5. Then we have Q̂π(s,a) = Qπρ (s,a) + λ logρ(a|s), ∀π. According to Lemma 4,
π̂new(s, ·) = arg min π DKL
π(·|s)‖exp ( Q̂πold(s, ·)/λ ) Zπold(s)  Q̂π̂new(s,a) ≥ Q̂πold(s,a), ∀a ∈ A.
With the definition, we have
DKL
( π(·|s)‖exp(Q̂
πold(s, ·)/λ) Zπold(s)
) = DKL ( π(·|s)‖ρ(·|s)
exp(Qπoldρ (s, ·)/λ) Zπold(s) ) πnew = π̂new
Qπnewρ (s,a) = Q̂ πnew(s,a)− λ logρ(a|s) ≥ Q̂πold(s,a)− λ logρ(a|s) = Qπoldρ (s,a).
A.3 LEMMA 3
Proof. From the equation
πinew = arg max πi ∑ ai πi(ai|s) ( ki(s)Q πiold ρ (s, ai)− λ log πi(ai|s) ρi(ai|s) ) ,
we can obtain ∑ ai πinew(ai|s) ( ki(s)Q πiold ρ (s, ai)− λ log πinew(ai|s) ρi(ai|s) ) ≥ ∑ ai πiold(ai|s) ( ki(s)Q πiold ρ (s, ai)− λ log πiold(ai|s) ρi(ai|s) ) .
(19)
By taking expectation on the both side of (19), we can obtain the followings.
∑ a−i π̃−i(a−i|s) ∑ ai πinew(ai|s) ( ki(s)Q πiold ρ (s, ai)− λ log πinew(ai|s) ρi(ai|s) )
≥ ∑ a−i π̃−i(a−i|s) ∑ ai πiold(ai|s) ( ki(s)Q πiold ρ (s, ai)− λ log πiold(ai|s) ρi(ai|s) ) ∀i ∈ I ∀π̃−i
(20)
Moreover, we can easily have the following derivation,
∑ ai πinew(ai|s) ( ki(s)Q πiold ρ (s, ai) + b(s)− λ log πinew(ai|s) ρi(ai|s) ) = ∑ a−i u1(a−i|s) ∑ ai πinew(ai|s) ( ki(s)Q πiold ρ (s, ai) + b(s)− λ log πinew(ai|s) ρi(ai|s) )
= ∑ a−i u2(a−i|s) ∑ ai πinew(ai|s) ( ki(s)Q πiold ρ (s, ai) + b(s)− λ log πinew(ai|s) ρi(ai|s) ) ∀u1, u2.
(21)
Then we have Ea∼πnew [ Qπoldρ (s,a)− log
πnew(a|s) ρ(a|s) ] = ∑ a πnew(a|s) ∑ i ( ki(s)Q πiold ρ (s, ai) + b(s)− λ log πinew(ai|s) ρi(ai|s)
) = ∑ a πnew(a|s) ∑ i ( ki(s)Q πiold ρ (s, ai) + b(s)− λ log πinew(ai|s) ρi(ai|s)
) = ∑ i ∑ a−i π−inew(a−i|s) ∑ ai πinew(ai|s) ( ki(s)Q πiold ρ (s, ai) + b(s)− λ log πinew(ai|s) ρi(ai|s) )
= ∑ i ∑ a−i π−iold(a−i|s) ∑ ai πinew(ai|s) ( ki(s)Q πiold ρ (s, ai) + b(s)− λ log πinew(ai|s) ρi(ai|s) )
≥ ∑ i ∑ a−i π−iold(a−i|s) ∑ ai πiold(ai|s) ( ki(s)Q πiold ρ (s, ai) + b(s)− λ log πiold(ai|s) ρi(ai|s) ) = V πoldρ (s)
(22)
The fourth equation is from (21) and the fifth inequality is from (20). By repeatedly applying (22) and the relation Qπoldρ (s,a) = r(s,a) + γEs′ [ V πoldρ (s ′) ] , we can complete the proof as followings.
Qπoldρ (s,a) = r(s,a) + γEs′ [ V πoldρ (s ′) ]
≤ r(s,a) + γEs′ [ Ea′∼πnew [ Qπoldρ (s ′, ,a′)− log πnew(a ′|s′)
ρ(a′|s′) ]] = r(s,a) + γEs′ [ Ea′∼πnew [ r(s′,a′) + γEs′′ [ V πoldρ (s ′′) ] − log πnew(a ′|s′) ρ(a′|s′)
]] · · · ≤ Qπnewρ (s,a)
A.4 THEOREM 1
Proof. First, we will show that Divergence Policy Iteration will monotonically improve the policy. From Lemma 2, we know that
V πnewρ (s) = Ea∼πnew(·|s) [ Qπnewρ (s,a)− λ log πnew(a|s) ρ(a|s) ] ≥ Ea∼πnew(·|s) [ Qπoldρ (s,a)− λ log πnew(a|s) ρ(a|s)
] ≥ Ea∼πold(·|s) [ Qπoldρ (s,a)− λ log πold(a|s) ρ(a|s)
] = V πoldρ (s).
The first inequality is from the conclusion of Lemma 2 that
Qπnewρ (s,a) ≥ Qπoldρ (s,a) ∀a ∈ A,
and the second inequality is from the definition of πnew that
πnew = arg min π DKL
( π(·|s)‖ exp ( Qπoldρ (s, ·)/λ ) Zπold(s) ) .
Here we have V πnew(s) ≥ V πold(s), ∀s ∈ S, and thus Jρ(πnew) ≥ Jρ(πold). So, Divergence Policy Iteration will monotonically improve the policy.
Since the Qπρ is bounded above (the reward function is bounded), the sequence of Q-function { Qk } of Divergence Policy Iteration will converge and the corresponding policy sequence will also converge to some policy πconv. We need to show πconv = π∗ρ.
V πconvρ (s) = Ea∼πconv(·|s) [ Qπconvρ (s,a)− λ log πconv(a|s) ρ(a|s) ] ≥ Ea∼π(·|s) [ Qπconvρ (s,a)− λ log
π(a|s) ρ(a|s) ] ≥ Ea∼π(·|s) [ r(s,a) + γEa′∼π(·|s′) [ Qπconvρ (s ′,a′)− λ log π(a ′|s′)
ρ(a′|s′)
] − λ log π(a|s)
ρ(a|s) ] · · · ≥ V πρ (s).
The first inequality is from the definition of πconv that
πconv = arg min π DKL
( π(·|s)‖ exp ( Qπconvρ (s, ·)/λ ) Zπconv(s) ) and all the other inequalities are just iteratively using the first inequality and the relation of Qπρ and V πρ . With iterations, we replace all the πconv with π in the expression of V πconv ρ (s) and finally we get V πρ (s). Therefore, we have
V πconvρ (s) ≥ V πρ (s) ∀s ∈ S ∀π ∈ Π Jρ(πconv) ≥ Jρ(π) ∀π ∈ Π πconv = π ∗ ρ.
A.5 PROPOSITION 1
Before the proof of Proposition 1, we need some results about the optimal Q-function Q∗ent, the optimal V-function V ∗ent, and the optimal policy π ∗ ent in entropy-regularized MDP. We have the following lemma (Nachum et al., 2017).
Lemma 5
π∗ent(s, a) ∝ exp (( r(s, a) + γEs′∼P (·|s,a) [V ∗ent(s′)] ) /λ )
V ∗ent(s) = λ log ∑ a exp (( r(s, a) + γEs′∼P (·|s,a) [V ∗ent(s′)] ) /λ )
Q∗ent(s, a) = r(s, a) + γλEs′∼P (·|s,a) [ log ∑ a′ exp (Q∗ent(s ′, a′)/λ) ]
With Lemma 5, we can complete the proof of Proposition 1.
Proof. Let r̂(s,a) = r(s,a) + λ logρ(a|s), we consider the objective function
Ĵ(π) = Eπ [∑ t=0 γt (r̂(st,at)− λ logπ(at|st)) ] .
Let π̂∗(a|s),V̂ ∗(s) and Q̂∗(s,a) be the corresponding optimal policy, V-function and Q-function of Ĵ(π). By definition we can obtain
π̂∗(a|s) = π∗ρ(a|s) V̂ ∗(s) = E a∼π̂∗(·|s),s′∼P (·|s,a) [ r̂(s,a) + γV̂ ∗(s′)− λ log π̂∗(a|s) ] = E a∼π∗ρ(·|s),s′∼P (·|s,a) [ r(s,a) + γV̂ ∗(s′)− λ log π∗ρ(a|s) ρ(a|s)
] = V ∗ρ (s)
Q̂∗(s,a) = r̂(s,a) + Es′∼P (·|s,a) [ V̂ ∗(s′) ] = r(s,a) + Es′∼P (·|s,a) [ V ∗ρ (s ′) ]
+ λ logρ(a|s) = Q∗ρ(s,a) + λ logρ(a|s).
According to Lemma 5, we have
π∗ρ(a|s) = π̂∗(a|s) ∝ exp (( r̂(s,a) + γEs′∼P (·|s,a) [ V̂ ∗(s′) ]) /λ )
= ρ(a|s) exp (( r(s,a) + γEs′∼P (·|s,a) [ V ∗ρ (s ′) ]) /λ )
V ∗ρ (s) = V̂ ∗(s) = λ log ∑ a exp (( r̂(s,a) + γEs′∼P (·|s,a) [ V̂ ∗(s′) ]) /λ )
= λ log ∑ a ρ(a|s) exp (( r(s,a) + γEs′∼P (·|s,a) [ V ∗ρ (s ′) ]) /λ )
Q∗ρ(s,a) = Q̂ ∗(s,a)− λ logρ(a|s)
= r̂(s,a) + γλEs′∼P (·|s,a) [ log ∑ a′ exp ( Q̂∗(s′,a′)/λ )] − λ logρ(a|s)
= r(s,a) + γλEs′∼P (·|s,a) [ log ∑ a′ ρ(a|s) exp ( Q∗ρ(s ′,a′)/λ )] .
A.6 DERIVATION OF GRADIENT
∇θiLπ = Es∼D [∑ a ∇θiπ(a|s) ( Qπρ (s,a)− λ log π(a|s) ρ(a|s) ) + π(a|s)∇θi(−λ log π(a|s) ρ(a|s) ) ]
= Es∼D [∑ a π(a|s)∇θi log πi(ai|s) ( Qπρ (s,a)− λ log π(a|s) ρ(a|s) ) − λπ(a|s)∇θi log πi(ai|s) ]
= Es∼D,a∼π [ ∇θi log πi(ai|s) ( Qπρ (s,a)− λ log
π(a|s) ρ(a|s)
− λ )]

heading: B ALGORITHM
text: Algorithm 1 gives the training procedure of DMAC.
Algorithm 1 DMAC 1: for episode = 1 to m do 2: Initialize the environment and receive initial state s 3: for t = 1 to max-episode-length do 4: For each agent i, select action ai ∼ πi(·|s) 5: Execute joint-action a = (a1, a2, · · · , an) and observe reward r and next state s′ 6: Store (s,a, r, s′) in replay buffer D 7: end for 8: Sample a random minibatch of K samples from D, {(sk,ak, rk, s′k)}K 9: for agent i = 1 to n do 10: Update policy πi: θi = θi + β∇θiLπ 11: Update target policy ρi: θ̃i = (1− τ)θ̃i + τθi 12: end for 13: Update critic: φ = φ− α∇φLQ 14: Update target critic: φ̃ = (1− τ)φ̃+ τφ 15: end for
C IMPLEMENTATION DETAILS
SMAC is a MARL environment based on the game StarCraft II (SC2). Agents control different units in SC2 and can attack, move or take other actions. The general mode of SMAC tasks is that agents control a team of units to counter another team controlled by built-in AI. The target of agents is to wipe out all the enemy units and agents will gain rewards when hurting or killing enemy units. Agents have an observation range and can only observe information of units in this range, but the information of all the units can be accessed in training. We test all the methods in totally 8 tasks/maps: 3m, 2s3z, 3s5z, 8m,1c3s5z,3s_vs_3z,2c_vs_64zg, and MMM2.
In SMAC tasks, we evaluate 20 episodes in every 10000 training steps in the one million steps training procedure for COMA, MAAC, QMIX and in every 20000 time steps for DOP and FOP. In evaluation, we select greedy actions for QMIX and FOP (following the setting in the FOP paper) and sample actions according to action distribution for stochastic policy (COMA, MAAC, DOP and divergence-regularized methods).
C.1 MODIFICATIONS OF THE BASELINE METHODS
The modifications of the baseline methods, COMA,MAAC,QMIX,DOP and FOP, are as follows.
• COMA. We keep the original critic and actor networks and add a target policy network with the same architecture as the actor. As COMA is on-policy but COMA+DMAC is off-policy, we add a replay buffer for experience replay.
• MAAC already has a target policy for stability, so we do not need to modify the network architecture. We only change the update rule for the critic and actors.
• QMIX is a value-based method, so we need to add a policy network and a target policy network for each agent. We keep the original individual Q-functions to learn the critic in QMIX+DMAC. In divergence-regularized MDP, the max operator is not needed in the critic update, so we abandon the hypernet and use an MLP, which takes individual Q-values and state as input and produces the joint Q-value. This architecture is simple and its expressive capability is not limited by QMIX’s IGM condition.
• DOP. We keep the original critic and actor networks and add a target policy network with the same architecture as the actor. We keep the value decomposition structure and use off-policy TD(λ) for all samples in training to replace the tree backup loss and on-policy TD(λ) loss.
• FOP. We replace the entropy regularizers with divergence regularizers in FOP and use the update rules of DMAC. We keep the original architecture of FOP.
C.2 HYPERPARAMETERS
As all tasks in our experiments are cooperative with shared reward, so we use parameter-sharing policy network and critic network for MAAC and MAAC+DMAC to accelerate training. Besides, we add a RNN layer to the policy network and critic network in MAAC and MAAC+DMAC to settle the partial observability.
All the policy networks are the same as two linear layers and one GRUCell layer with ReLU activation and the number of hidden units is 64. The individual Q-networks for QMIX group is the same as the policy network mentioned before. The critic network for COMA group is a MLP with three 128-unit hidden layers and ReLU activation. The attention dimension in the critic networks of MAAC group is 32. The number of hidden units of mixer network in QMIX group is 32. The learning rate for critic is 10−3 and the learning rate for actor is 10−4. We train all networks with RMSprop optimizer. The discouted factor is γ = 0.99. The coefficient of regularizer is λ = 0.01. The td_lambda factor used in COMA group is 0.8. The parameter used for soft updating target policy is τ = 0.01. Our
code is based on the implementation of PyMARL (Samvelyan et al., 2019), MAAC (Iqbal and Sha, 2019), DOP (Wang et al., 2021b), FOP (Zhang et al., 2021) and an open source code for algorithms in SMAC (https://github.com/starry-sky6688/StarCraft).
C.3 EXPERIMENT SETTINGS
We trained each algorithms for five runs with different random seeds. In SMAC tasks, we train each algorithm for one million time steps in each run for COMA, QMIX, MAAC, and DOP groups and two million timesteps for FOP groups. We do all the experiments by a server with 2 NVIDIA A100 GPUs.

heading: D ADDITIONAL RESULTS
text: Figure 5 shows the learning curves in terms of cover rates of COMA, QMIX, MAAC and DOP groups in the randomly generated stochastic game.
Figure 6 shows the learning curves of COMA, MAAC, QMIX and DOP groups in terms of mean episode rewards in each SMAC map.
Figure 7 shows the learning curves of FOP+DMAC and FOP in terms of mean episode rewards in 3s_vs_3z, 2c_vs_64zg and MMM2.
Figure 8 shows the learning curves in terms of mean episode rewards of COMA and DOP groups in the CDM environment used by the DOP paper.
Figure 9 shows the learning curves of QMIX and DOP groups in terms of win rate, and COMA and MAAC groups in terms of episode reward on the map MMM2 in SMAC.

Review summaries:
For cooperative multi-agent reinforcement learning, they propose an off-policy(?) learning method that is reqularized by the KL divergence to some target policy, which, in contrast to classic max entropy RL, allows to circumvent(?) the bias that the regularizer introduces (eq18). They give several special cases / tricks of how the learning can be somewhat decoupled between the agent (Lem 3, end of sec4.4). They paper comprises theory about convergence of the method, as well as experiments in toy envs.

This paper develops a new multiagent framework with regulated divergence to address the learning of biased policies in the maximum-entropy approach. Specifically, the main contributions include the developments of the divergence policy iteration for general cooperative MARL settings and the off-policy divergence regularized multiagent actor-critic framework (DMAC). Empirical results show that DMAC can improve the performance of existing MARL frameworks in various multiagent domains.

This paper suggests a DMAC learning framework by introducing a divergence penalty between the learning policy between a target policy into the RL framework instead of the commonly used entropy penalty. It can be shown that the proposed objective can be easily combined with various MARL algorithms and can eventually lead to the optimal policy of the underlying unmodified MDP with properly set target policies. The paper rigorously studies the mathematical foundation of the algorithm following a standard workflow and presents a few experiments showing that DMAC could improve the learning efficiency of various MARL algorithms.